IVUsers.cpp revision 207618
1//===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements bookkeeping for "interesting" users of expressions 11// computed from induction variables. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "iv-users" 16#include "llvm/Analysis/IVUsers.h" 17#include "llvm/Constants.h" 18#include "llvm/Instructions.h" 19#include "llvm/Type.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Analysis/Dominators.h" 22#include "llvm/Analysis/LoopPass.h" 23#include "llvm/Analysis/ScalarEvolutionExpressions.h" 24#include "llvm/Assembly/AsmAnnotationWriter.h" 25#include "llvm/ADT/STLExtras.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/raw_ostream.h" 28#include <algorithm> 29using namespace llvm; 30 31char IVUsers::ID = 0; 32static RegisterPass<IVUsers> 33X("iv-users", "Induction Variable Users", false, true); 34 35Pass *llvm::createIVUsersPass() { 36 return new IVUsers(); 37} 38 39/// isInteresting - Test whether the given expression is "interesting" when 40/// used by the given expression, within the context of analyzing the 41/// given loop. 42static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L) { 43 // Anything loop-invariant is interesting. 44 if (!isa<SCEVUnknown>(S) && S->isLoopInvariant(L)) 45 return true; 46 47 // An addrec is interesting if it's affine or if it has an interesting start. 48 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 49 // Keep things simple. Don't touch loop-variant strides. 50 if (AR->getLoop() == L) 51 return AR->isAffine() || !L->contains(I); 52 // Otherwise recurse to see if the start value is interesting. 53 return isInteresting(AR->getStart(), I, L); 54 } 55 56 // An add is interesting if any of its operands is. 57 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 58 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); 59 OI != OE; ++OI) 60 if (isInteresting(*OI, I, L)) 61 return true; 62 return false; 63 } 64 65 // Nothing else is interesting here. 66 return false; 67} 68 69/// AddUsersIfInteresting - Inspect the specified instruction. If it is a 70/// reducible SCEV, recursively add its users to the IVUsesByStride set and 71/// return true. Otherwise, return false. 72bool IVUsers::AddUsersIfInteresting(Instruction *I) { 73 if (!SE->isSCEVable(I->getType())) 74 return false; // Void and FP expressions cannot be reduced. 75 76 // LSR is not APInt clean, do not touch integers bigger than 64-bits. 77 if (SE->getTypeSizeInBits(I->getType()) > 64) 78 return false; 79 80 if (!Processed.insert(I)) 81 return true; // Instruction already handled. 82 83 // Get the symbolic expression for this instruction. 84 const SCEV *ISE = SE->getSCEV(I); 85 86 // If we've come to an uninteresting expression, stop the traversal and 87 // call this a user. 88 if (!isInteresting(ISE, I, L)) 89 return false; 90 91 SmallPtrSet<Instruction *, 4> UniqueUsers; 92 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 93 UI != E; ++UI) { 94 Instruction *User = cast<Instruction>(*UI); 95 if (!UniqueUsers.insert(User)) 96 continue; 97 98 // Do not infinitely recurse on PHI nodes. 99 if (isa<PHINode>(User) && Processed.count(User)) 100 continue; 101 102 // Descend recursively, but not into PHI nodes outside the current loop. 103 // It's important to see the entire expression outside the loop to get 104 // choices that depend on addressing mode use right, although we won't 105 // consider references outside the loop in all cases. 106 // If User is already in Processed, we don't want to recurse into it again, 107 // but do want to record a second reference in the same instruction. 108 bool AddUserToIVUsers = false; 109 if (LI->getLoopFor(User->getParent()) != L) { 110 if (isa<PHINode>(User) || Processed.count(User) || 111 !AddUsersIfInteresting(User)) { 112 DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' 113 << " OF SCEV: " << *ISE << '\n'); 114 AddUserToIVUsers = true; 115 } 116 } else if (Processed.count(User) || 117 !AddUsersIfInteresting(User)) { 118 DEBUG(dbgs() << "FOUND USER: " << *User << '\n' 119 << " OF SCEV: " << *ISE << '\n'); 120 AddUserToIVUsers = true; 121 } 122 123 if (AddUserToIVUsers) { 124 // Okay, we found a user that we cannot reduce. 125 IVUses.push_back(new IVStrideUse(this, User, I)); 126 IVStrideUse &NewUse = IVUses.back(); 127 // Transform the expression into a normalized form. 128 ISE = TransformForPostIncUse(NormalizeAutodetect, 129 ISE, User, I, 130 NewUse.PostIncLoops, 131 *SE, *DT); 132 DEBUG(dbgs() << " NORMALIZED TO: " << *ISE << '\n'); 133 } 134 } 135 return true; 136} 137 138IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { 139 IVUses.push_back(new IVStrideUse(this, User, Operand)); 140 return IVUses.back(); 141} 142 143IVUsers::IVUsers() 144 : LoopPass(&ID) { 145} 146 147void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { 148 AU.addRequired<LoopInfo>(); 149 AU.addRequired<DominatorTree>(); 150 AU.addRequired<ScalarEvolution>(); 151 AU.setPreservesAll(); 152} 153 154bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { 155 156 L = l; 157 LI = &getAnalysis<LoopInfo>(); 158 DT = &getAnalysis<DominatorTree>(); 159 SE = &getAnalysis<ScalarEvolution>(); 160 161 // Find all uses of induction variables in this loop, and categorize 162 // them by stride. Start by finding all of the PHI nodes in the header for 163 // this loop. If they are induction variables, inspect their uses. 164 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) 165 (void)AddUsersIfInteresting(I); 166 167 return false; 168} 169 170void IVUsers::print(raw_ostream &OS, const Module *M) const { 171 OS << "IV Users for loop "; 172 WriteAsOperand(OS, L->getHeader(), false); 173 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 174 OS << " with backedge-taken count " 175 << *SE->getBackedgeTakenCount(L); 176 } 177 OS << ":\n"; 178 179 // Use a default AssemblyAnnotationWriter to suppress the default info 180 // comments, which aren't relevant here. 181 AssemblyAnnotationWriter Annotator; 182 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(), 183 E = IVUses.end(); UI != E; ++UI) { 184 OS << " "; 185 WriteAsOperand(OS, UI->getOperandValToReplace(), false); 186 OS << " = " << *getReplacementExpr(*UI); 187 for (PostIncLoopSet::const_iterator 188 I = UI->PostIncLoops.begin(), 189 E = UI->PostIncLoops.end(); I != E; ++I) { 190 OS << " (post-inc with loop "; 191 WriteAsOperand(OS, (*I)->getHeader(), false); 192 OS << ")"; 193 } 194 OS << " in "; 195 UI->getUser()->print(OS, &Annotator); 196 OS << '\n'; 197 } 198} 199 200void IVUsers::dump() const { 201 print(dbgs()); 202} 203 204void IVUsers::releaseMemory() { 205 Processed.clear(); 206 IVUses.clear(); 207} 208 209/// getReplacementExpr - Return a SCEV expression which computes the 210/// value of the OperandValToReplace. 211const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { 212 return SE->getSCEV(IU.getOperandValToReplace()); 213} 214 215/// getExpr - Return the expression for the use. 216const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const { 217 return 218 TransformForPostIncUse(Normalize, getReplacementExpr(IU), 219 IU.getUser(), IU.getOperandValToReplace(), 220 const_cast<PostIncLoopSet &>(IU.getPostIncLoops()), 221 *SE, *DT); 222} 223 224static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { 225 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 226 if (AR->getLoop() == L) 227 return AR; 228 return findAddRecForLoop(AR->getStart(), L); 229 } 230 231 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 232 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 233 I != E; ++I) 234 if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) 235 return AR; 236 return 0; 237 } 238 239 return 0; 240} 241 242const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { 243 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) 244 return AR->getStepRecurrence(*SE); 245 return 0; 246} 247 248void IVStrideUse::transformToPostInc(const Loop *L) { 249 PostIncLoops.insert(L); 250} 251 252void IVStrideUse::deleted() { 253 // Remove this user from the list. 254 Parent->IVUses.erase(this); 255 // this now dangles! 256} 257