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/Target/TargetData.h" 25 #include "llvm/Assembly/Writer.h" 26 #include "llvm/ADT/STLExtras.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/raw_ostream.h" 29 #include <algorithm> 30 using namespace llvm; 31 32 char IVUsers::ID = 0; 33 INITIALIZE_PASS_BEGIN(IVUsers, "iv-users", 34 "Induction Variable Users", false, true) 35 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 36 INITIALIZE_PASS_DEPENDENCY(DominatorTree) 37 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 38 INITIALIZE_PASS_END(IVUsers, "iv-users", 39 "Induction Variable Users", false, true) 40 41 Pass *llvm::createIVUsersPass() { 42 return new IVUsers(); 43 } 44 45 /// isInteresting - Test whether the given expression is "interesting" when 46 /// used by the given expression, within the context of analyzing the 47 /// given loop. 48 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L, 49 ScalarEvolution *SE, LoopInfo *LI) { 50 // An addrec is interesting if it's affine or if it has an interesting start. 51 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 52 // Keep things simple. Don't touch loop-variant strides unless they're 53 // only used outside the loop and we can simplify them. 54 if (AR->getLoop() == L) 55 return AR->isAffine() || 56 (!L->contains(I) && 57 SE->getSCEVAtScope(AR, LI->getLoopFor(I->getParent())) != AR); 58 // Otherwise recurse to see if the start value is interesting, and that 59 // the step value is not interesting, since we don't yet know how to 60 // do effective SCEV expansions for addrecs with interesting steps. 61 return isInteresting(AR->getStart(), I, L, SE, LI) && 62 !isInteresting(AR->getStepRecurrence(*SE), I, L, SE, LI); 63 } 64 65 // An add is interesting if exactly one of its operands is interesting. 66 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 67 bool AnyInterestingYet = false; 68 for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end(); 69 OI != OE; ++OI) 70 if (isInteresting(*OI, I, L, SE, LI)) { 71 if (AnyInterestingYet) 72 return false; 73 AnyInterestingYet = true; 74 } 75 return AnyInterestingYet; 76 } 77 78 // Nothing else is interesting here. 79 return false; 80 } 81 82 /// Return true if all loop headers that dominate this block are in simplified 83 /// form. 84 static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, 85 const LoopInfo *LI, 86 SmallPtrSet<Loop*,16> &SimpleLoopNests) { 87 Loop *NearestLoop = 0; 88 for (DomTreeNode *Rung = DT->getNode(BB); 89 Rung; Rung = Rung->getIDom()) { 90 BasicBlock *DomBB = Rung->getBlock(); 91 Loop *DomLoop = LI->getLoopFor(DomBB); 92 if (DomLoop && DomLoop->getHeader() == DomBB) { 93 // If the domtree walk reaches a loop with no preheader, return false. 94 if (!DomLoop->isLoopSimplifyForm()) 95 return false; 96 // If we have already checked this loop nest, stop checking. 97 if (SimpleLoopNests.count(DomLoop)) 98 break; 99 // If we have not already checked this loop nest, remember the loop 100 // header nearest to BB. The nearest loop may not contain BB. 101 if (!NearestLoop) 102 NearestLoop = DomLoop; 103 } 104 } 105 if (NearestLoop) 106 SimpleLoopNests.insert(NearestLoop); 107 return true; 108 } 109 110 /// AddUsersImpl - Inspect the specified instruction. If it is a 111 /// reducible SCEV, recursively add its users to the IVUsesByStride set and 112 /// return true. Otherwise, return false. 113 bool IVUsers::AddUsersImpl(Instruction *I, 114 SmallPtrSet<Loop*,16> &SimpleLoopNests) { 115 // Add this IV user to the Processed set before returning false to ensure that 116 // all IV users are members of the set. See IVUsers::isIVUserOrOperand. 117 if (!Processed.insert(I)) 118 return true; // Instruction already handled. 119 120 if (!SE->isSCEVable(I->getType())) 121 return false; // Void and FP expressions cannot be reduced. 122 123 // LSR is not APInt clean, do not touch integers bigger than 64-bits. 124 // Also avoid creating IVs of non-native types. For example, we don't want a 125 // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. 126 uint64_t Width = SE->getTypeSizeInBits(I->getType()); 127 if (Width > 64 || (TD && !TD->isLegalInteger(Width))) 128 return false; 129 130 // Get the symbolic expression for this instruction. 131 const SCEV *ISE = SE->getSCEV(I); 132 133 // If we've come to an uninteresting expression, stop the traversal and 134 // call this a user. 135 if (!isInteresting(ISE, I, L, SE, LI)) 136 return false; 137 138 SmallPtrSet<Instruction *, 4> UniqueUsers; 139 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 140 UI != E; ++UI) { 141 Instruction *User = cast<Instruction>(*UI); 142 if (!UniqueUsers.insert(User)) 143 continue; 144 145 // Do not infinitely recurse on PHI nodes. 146 if (isa<PHINode>(User) && Processed.count(User)) 147 continue; 148 149 // Only consider IVUsers that are dominated by simplified loop 150 // headers. Otherwise, SCEVExpander will crash. 151 BasicBlock *UseBB = User->getParent(); 152 // A phi's use is live out of its predecessor block. 153 if (PHINode *PHI = dyn_cast<PHINode>(User)) { 154 unsigned OperandNo = UI.getOperandNo(); 155 unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); 156 UseBB = PHI->getIncomingBlock(ValNo); 157 } 158 if (!isSimplifiedLoopNest(UseBB, DT, LI, SimpleLoopNests)) 159 return false; 160 161 // Descend recursively, but not into PHI nodes outside the current loop. 162 // It's important to see the entire expression outside the loop to get 163 // choices that depend on addressing mode use right, although we won't 164 // consider references outside the loop in all cases. 165 // If User is already in Processed, we don't want to recurse into it again, 166 // but do want to record a second reference in the same instruction. 167 bool AddUserToIVUsers = false; 168 if (LI->getLoopFor(User->getParent()) != L) { 169 if (isa<PHINode>(User) || Processed.count(User) || 170 !AddUsersImpl(User, SimpleLoopNests)) { 171 DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n' 172 << " OF SCEV: " << *ISE << '\n'); 173 AddUserToIVUsers = true; 174 } 175 } else if (Processed.count(User) || !AddUsersImpl(User, SimpleLoopNests)) { 176 DEBUG(dbgs() << "FOUND USER: " << *User << '\n' 177 << " OF SCEV: " << *ISE << '\n'); 178 AddUserToIVUsers = true; 179 } 180 181 if (AddUserToIVUsers) { 182 // Okay, we found a user that we cannot reduce. 183 IVUses.push_back(new IVStrideUse(this, User, I)); 184 IVStrideUse &NewUse = IVUses.back(); 185 // Autodetect the post-inc loop set, populating NewUse.PostIncLoops. 186 // The regular return value here is discarded; instead of recording 187 // it, we just recompute it when we need it. 188 ISE = TransformForPostIncUse(NormalizeAutodetect, 189 ISE, User, I, 190 NewUse.PostIncLoops, 191 *SE, *DT); 192 DEBUG(if (SE->getSCEV(I) != ISE) 193 dbgs() << " NORMALIZED TO: " << *ISE << '\n'); 194 } 195 } 196 return true; 197 } 198 199 bool IVUsers::AddUsersIfInteresting(Instruction *I) { 200 // SCEVExpander can only handle users that are dominated by simplified loop 201 // entries. Keep track of all loops that are only dominated by other simple 202 // loops so we don't traverse the domtree for each user. 203 SmallPtrSet<Loop*,16> SimpleLoopNests; 204 205 return AddUsersImpl(I, SimpleLoopNests); 206 } 207 208 IVStrideUse &IVUsers::AddUser(Instruction *User, Value *Operand) { 209 IVUses.push_back(new IVStrideUse(this, User, Operand)); 210 return IVUses.back(); 211 } 212 213 IVUsers::IVUsers() 214 : LoopPass(ID) { 215 initializeIVUsersPass(*PassRegistry::getPassRegistry()); 216 } 217 218 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { 219 AU.addRequired<LoopInfo>(); 220 AU.addRequired<DominatorTree>(); 221 AU.addRequired<ScalarEvolution>(); 222 AU.setPreservesAll(); 223 } 224 225 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) { 226 227 L = l; 228 LI = &getAnalysis<LoopInfo>(); 229 DT = &getAnalysis<DominatorTree>(); 230 SE = &getAnalysis<ScalarEvolution>(); 231 TD = getAnalysisIfAvailable<TargetData>(); 232 233 // Find all uses of induction variables in this loop, and categorize 234 // them by stride. Start by finding all of the PHI nodes in the header for 235 // this loop. If they are induction variables, inspect their uses. 236 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) 237 (void)AddUsersIfInteresting(I); 238 239 return false; 240 } 241 242 void IVUsers::print(raw_ostream &OS, const Module *M) const { 243 OS << "IV Users for loop "; 244 WriteAsOperand(OS, L->getHeader(), false); 245 if (SE->hasLoopInvariantBackedgeTakenCount(L)) { 246 OS << " with backedge-taken count " 247 << *SE->getBackedgeTakenCount(L); 248 } 249 OS << ":\n"; 250 251 for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(), 252 E = IVUses.end(); UI != E; ++UI) { 253 OS << " "; 254 WriteAsOperand(OS, UI->getOperandValToReplace(), false); 255 OS << " = " << *getReplacementExpr(*UI); 256 for (PostIncLoopSet::const_iterator 257 I = UI->PostIncLoops.begin(), 258 E = UI->PostIncLoops.end(); I != E; ++I) { 259 OS << " (post-inc with loop "; 260 WriteAsOperand(OS, (*I)->getHeader(), false); 261 OS << ")"; 262 } 263 OS << " in "; 264 UI->getUser()->print(OS); 265 OS << '\n'; 266 } 267 } 268 269 void IVUsers::dump() const { 270 print(dbgs()); 271 } 272 273 void IVUsers::releaseMemory() { 274 Processed.clear(); 275 IVUses.clear(); 276 } 277 278 /// getReplacementExpr - Return a SCEV expression which computes the 279 /// value of the OperandValToReplace. 280 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &IU) const { 281 return SE->getSCEV(IU.getOperandValToReplace()); 282 } 283 284 /// getExpr - Return the expression for the use. 285 const SCEV *IVUsers::getExpr(const IVStrideUse &IU) const { 286 return 287 TransformForPostIncUse(Normalize, getReplacementExpr(IU), 288 IU.getUser(), IU.getOperandValToReplace(), 289 const_cast<PostIncLoopSet &>(IU.getPostIncLoops()), 290 *SE, *DT); 291 } 292 293 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) { 294 if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) { 295 if (AR->getLoop() == L) 296 return AR; 297 return findAddRecForLoop(AR->getStart(), L); 298 } 299 300 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 301 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 302 I != E; ++I) 303 if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) 304 return AR; 305 return 0; 306 } 307 308 return 0; 309 } 310 311 const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { 312 if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) 313 return AR->getStepRecurrence(*SE); 314 return 0; 315 } 316 317 void IVStrideUse::transformToPostInc(const Loop *L) { 318 PostIncLoops.insert(L); 319 } 320 321 void IVStrideUse::deleted() { 322 // Remove this user from the list. 323 Parent->Processed.erase(this->getUser()); 324 Parent->IVUses.erase(this); 325 // this now dangles! 326 } 327