LLVM API Documentation
00001 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This transformation analyzes and transforms the induction variables (and 00011 // computations derived from them) into simpler forms suitable for subsequent 00012 // analysis and transformation. 00013 // 00014 // If the trip count of a loop is computable, this pass also makes the following 00015 // changes: 00016 // 1. The exit condition for the loop is canonicalized to compare the 00017 // induction value against the exit value. This turns loops like: 00018 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 00019 // 2. Any use outside of the loop of an expression derived from the indvar 00020 // is changed to compute the derived value outside of the loop, eliminating 00021 // the dependence on the exit value of the induction variable. If the only 00022 // purpose of the loop is to compute the exit value of some derived 00023 // expression, this transformation will make the loop dead. 00024 // 00025 //===----------------------------------------------------------------------===// 00026 00027 #include "llvm/Transforms/Scalar.h" 00028 #include "llvm/ADT/DenseMap.h" 00029 #include "llvm/ADT/SmallVector.h" 00030 #include "llvm/ADT/Statistic.h" 00031 #include "llvm/Analysis/LoopInfo.h" 00032 #include "llvm/Analysis/LoopPass.h" 00033 #include "llvm/Analysis/ScalarEvolutionExpander.h" 00034 #include "llvm/IR/BasicBlock.h" 00035 #include "llvm/IR/CFG.h" 00036 #include "llvm/IR/Constants.h" 00037 #include "llvm/IR/DataLayout.h" 00038 #include "llvm/IR/Dominators.h" 00039 #include "llvm/IR/Instructions.h" 00040 #include "llvm/IR/IntrinsicInst.h" 00041 #include "llvm/IR/LLVMContext.h" 00042 #include "llvm/IR/Type.h" 00043 #include "llvm/Support/CommandLine.h" 00044 #include "llvm/Support/Debug.h" 00045 #include "llvm/Support/raw_ostream.h" 00046 #include "llvm/Target/TargetLibraryInfo.h" 00047 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00048 #include "llvm/Transforms/Utils/Local.h" 00049 #include "llvm/Transforms/Utils/SimplifyIndVar.h" 00050 using namespace llvm; 00051 00052 #define DEBUG_TYPE "indvars" 00053 00054 STATISTIC(NumWidened , "Number of indvars widened"); 00055 STATISTIC(NumReplaced , "Number of exit values replaced"); 00056 STATISTIC(NumLFTR , "Number of loop exit tests replaced"); 00057 STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); 00058 STATISTIC(NumElimIV , "Number of congruent IVs eliminated"); 00059 00060 // Trip count verification can be enabled by default under NDEBUG if we 00061 // implement a strong expression equivalence checker in SCEV. Until then, we 00062 // use the verify-indvars flag, which may assert in some cases. 00063 static cl::opt<bool> VerifyIndvars( 00064 "verify-indvars", cl::Hidden, 00065 cl::desc("Verify the ScalarEvolution result after running indvars")); 00066 00067 static cl::opt<bool> ReduceLiveIVs("liv-reduce", cl::Hidden, 00068 cl::desc("Reduce live induction variables.")); 00069 00070 namespace { 00071 class IndVarSimplify : public LoopPass { 00072 LoopInfo *LI; 00073 ScalarEvolution *SE; 00074 DominatorTree *DT; 00075 const DataLayout *DL; 00076 TargetLibraryInfo *TLI; 00077 00078 SmallVector<WeakVH, 16> DeadInsts; 00079 bool Changed; 00080 public: 00081 00082 static char ID; // Pass identification, replacement for typeid 00083 IndVarSimplify() : LoopPass(ID), LI(nullptr), SE(nullptr), DT(nullptr), 00084 DL(nullptr), Changed(false) { 00085 initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); 00086 } 00087 00088 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 00089 00090 void getAnalysisUsage(AnalysisUsage &AU) const override { 00091 AU.addRequired<DominatorTreeWrapperPass>(); 00092 AU.addRequired<LoopInfo>(); 00093 AU.addRequired<ScalarEvolution>(); 00094 AU.addRequiredID(LoopSimplifyID); 00095 AU.addRequiredID(LCSSAID); 00096 AU.addPreserved<ScalarEvolution>(); 00097 AU.addPreservedID(LoopSimplifyID); 00098 AU.addPreservedID(LCSSAID); 00099 AU.setPreservesCFG(); 00100 } 00101 00102 private: 00103 void releaseMemory() override { 00104 DeadInsts.clear(); 00105 } 00106 00107 bool isValidRewrite(Value *FromVal, Value *ToVal); 00108 00109 void HandleFloatingPointIV(Loop *L, PHINode *PH); 00110 void RewriteNonIntegerIVs(Loop *L); 00111 00112 void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM); 00113 00114 void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 00115 00116 Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 00117 PHINode *IndVar, SCEVExpander &Rewriter); 00118 00119 void SinkUnusedInvariants(Loop *L); 00120 }; 00121 } 00122 00123 char IndVarSimplify::ID = 0; 00124 INITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", 00125 "Induction Variable Simplification", false, false) 00126 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 00127 INITIALIZE_PASS_DEPENDENCY(LoopInfo) 00128 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 00129 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 00130 INITIALIZE_PASS_DEPENDENCY(LCSSA) 00131 INITIALIZE_PASS_END(IndVarSimplify, "indvars", 00132 "Induction Variable Simplification", false, false) 00133 00134 Pass *llvm::createIndVarSimplifyPass() { 00135 return new IndVarSimplify(); 00136 } 00137 00138 /// isValidRewrite - Return true if the SCEV expansion generated by the 00139 /// rewriter can replace the original value. SCEV guarantees that it 00140 /// produces the same value, but the way it is produced may be illegal IR. 00141 /// Ideally, this function will only be called for verification. 00142 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { 00143 // If an SCEV expression subsumed multiple pointers, its expansion could 00144 // reassociate the GEP changing the base pointer. This is illegal because the 00145 // final address produced by a GEP chain must be inbounds relative to its 00146 // underlying object. Otherwise basic alias analysis, among other things, 00147 // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 00148 // producing an expression involving multiple pointers. Until then, we must 00149 // bail out here. 00150 // 00151 // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject 00152 // because it understands lcssa phis while SCEV does not. 00153 Value *FromPtr = FromVal; 00154 Value *ToPtr = ToVal; 00155 if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) { 00156 FromPtr = GEP->getPointerOperand(); 00157 } 00158 if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) { 00159 ToPtr = GEP->getPointerOperand(); 00160 } 00161 if (FromPtr != FromVal || ToPtr != ToVal) { 00162 // Quickly check the common case 00163 if (FromPtr == ToPtr) 00164 return true; 00165 00166 // SCEV may have rewritten an expression that produces the GEP's pointer 00167 // operand. That's ok as long as the pointer operand has the same base 00168 // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the 00169 // base of a recurrence. This handles the case in which SCEV expansion 00170 // converts a pointer type recurrence into a nonrecurrent pointer base 00171 // indexed by an integer recurrence. 00172 00173 // If the GEP base pointer is a vector of pointers, abort. 00174 if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy()) 00175 return false; 00176 00177 const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 00178 const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 00179 if (FromBase == ToBase) 00180 return true; 00181 00182 DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " 00183 << *FromBase << " != " << *ToBase << "\n"); 00184 00185 return false; 00186 } 00187 return true; 00188 } 00189 00190 /// Determine the insertion point for this user. By default, insert immediately 00191 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the 00192 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest 00193 /// common dominator for the incoming blocks. 00194 static Instruction *getInsertPointForUses(Instruction *User, Value *Def, 00195 DominatorTree *DT) { 00196 PHINode *PHI = dyn_cast<PHINode>(User); 00197 if (!PHI) 00198 return User; 00199 00200 Instruction *InsertPt = nullptr; 00201 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 00202 if (PHI->getIncomingValue(i) != Def) 00203 continue; 00204 00205 BasicBlock *InsertBB = PHI->getIncomingBlock(i); 00206 if (!InsertPt) { 00207 InsertPt = InsertBB->getTerminator(); 00208 continue; 00209 } 00210 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB); 00211 InsertPt = InsertBB->getTerminator(); 00212 } 00213 assert(InsertPt && "Missing phi operand"); 00214 assert((!isa<Instruction>(Def) || 00215 DT->dominates(cast<Instruction>(Def), InsertPt)) && 00216 "def does not dominate all uses"); 00217 return InsertPt; 00218 } 00219 00220 //===----------------------------------------------------------------------===// 00221 // RewriteNonIntegerIVs and helpers. Prefer integer IVs. 00222 //===----------------------------------------------------------------------===// 00223 00224 /// ConvertToSInt - Convert APF to an integer, if possible. 00225 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 00226 bool isExact = false; 00227 // See if we can convert this to an int64_t 00228 uint64_t UIntVal; 00229 if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 00230 &isExact) != APFloat::opOK || !isExact) 00231 return false; 00232 IntVal = UIntVal; 00233 return true; 00234 } 00235 00236 /// HandleFloatingPointIV - If the loop has floating induction variable 00237 /// then insert corresponding integer induction variable if possible. 00238 /// For example, 00239 /// for(double i = 0; i < 10000; ++i) 00240 /// bar(i) 00241 /// is converted into 00242 /// for(int i = 0; i < 10000; ++i) 00243 /// bar((double)i); 00244 /// 00245 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 00246 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 00247 unsigned BackEdge = IncomingEdge^1; 00248 00249 // Check incoming value. 00250 ConstantFP *InitValueVal = 00251 dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 00252 00253 int64_t InitValue; 00254 if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 00255 return; 00256 00257 // Check IV increment. Reject this PN if increment operation is not 00258 // an add or increment value can not be represented by an integer. 00259 BinaryOperator *Incr = 00260 dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 00261 if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return; 00262 00263 // If this is not an add of the PHI with a constantfp, or if the constant fp 00264 // is not an integer, bail out. 00265 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 00266 int64_t IncValue; 00267 if (IncValueVal == nullptr || Incr->getOperand(0) != PN || 00268 !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 00269 return; 00270 00271 // Check Incr uses. One user is PN and the other user is an exit condition 00272 // used by the conditional terminator. 00273 Value::user_iterator IncrUse = Incr->user_begin(); 00274 Instruction *U1 = cast<Instruction>(*IncrUse++); 00275 if (IncrUse == Incr->user_end()) return; 00276 Instruction *U2 = cast<Instruction>(*IncrUse++); 00277 if (IncrUse != Incr->user_end()) return; 00278 00279 // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 00280 // only used by a branch, we can't transform it. 00281 FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 00282 if (!Compare) 00283 Compare = dyn_cast<FCmpInst>(U2); 00284 if (!Compare || !Compare->hasOneUse() || 00285 !isa<BranchInst>(Compare->user_back())) 00286 return; 00287 00288 BranchInst *TheBr = cast<BranchInst>(Compare->user_back()); 00289 00290 // We need to verify that the branch actually controls the iteration count 00291 // of the loop. If not, the new IV can overflow and no one will notice. 00292 // The branch block must be in the loop and one of the successors must be out 00293 // of the loop. 00294 assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 00295 if (!L->contains(TheBr->getParent()) || 00296 (L->contains(TheBr->getSuccessor(0)) && 00297 L->contains(TheBr->getSuccessor(1)))) 00298 return; 00299 00300 00301 // If it isn't a comparison with an integer-as-fp (the exit value), we can't 00302 // transform it. 00303 ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 00304 int64_t ExitValue; 00305 if (ExitValueVal == nullptr || 00306 !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 00307 return; 00308 00309 // Find new predicate for integer comparison. 00310 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 00311 switch (Compare->getPredicate()) { 00312 default: return; // Unknown comparison. 00313 case CmpInst::FCMP_OEQ: 00314 case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 00315 case CmpInst::FCMP_ONE: 00316 case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 00317 case CmpInst::FCMP_OGT: 00318 case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 00319 case CmpInst::FCMP_OGE: 00320 case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 00321 case CmpInst::FCMP_OLT: 00322 case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 00323 case CmpInst::FCMP_OLE: 00324 case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 00325 } 00326 00327 // We convert the floating point induction variable to a signed i32 value if 00328 // we can. This is only safe if the comparison will not overflow in a way 00329 // that won't be trapped by the integer equivalent operations. Check for this 00330 // now. 00331 // TODO: We could use i64 if it is native and the range requires it. 00332 00333 // The start/stride/exit values must all fit in signed i32. 00334 if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 00335 return; 00336 00337 // If not actually striding (add x, 0.0), avoid touching the code. 00338 if (IncValue == 0) 00339 return; 00340 00341 // Positive and negative strides have different safety conditions. 00342 if (IncValue > 0) { 00343 // If we have a positive stride, we require the init to be less than the 00344 // exit value. 00345 if (InitValue >= ExitValue) 00346 return; 00347 00348 uint32_t Range = uint32_t(ExitValue-InitValue); 00349 // Check for infinite loop, either: 00350 // while (i <= Exit) or until (i > Exit) 00351 if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) { 00352 if (++Range == 0) return; // Range overflows. 00353 } 00354 00355 unsigned Leftover = Range % uint32_t(IncValue); 00356 00357 // If this is an equality comparison, we require that the strided value 00358 // exactly land on the exit value, otherwise the IV condition will wrap 00359 // around and do things the fp IV wouldn't. 00360 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 00361 Leftover != 0) 00362 return; 00363 00364 // If the stride would wrap around the i32 before exiting, we can't 00365 // transform the IV. 00366 if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 00367 return; 00368 00369 } else { 00370 // If we have a negative stride, we require the init to be greater than the 00371 // exit value. 00372 if (InitValue <= ExitValue) 00373 return; 00374 00375 uint32_t Range = uint32_t(InitValue-ExitValue); 00376 // Check for infinite loop, either: 00377 // while (i >= Exit) or until (i < Exit) 00378 if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) { 00379 if (++Range == 0) return; // Range overflows. 00380 } 00381 00382 unsigned Leftover = Range % uint32_t(-IncValue); 00383 00384 // If this is an equality comparison, we require that the strided value 00385 // exactly land on the exit value, otherwise the IV condition will wrap 00386 // around and do things the fp IV wouldn't. 00387 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 00388 Leftover != 0) 00389 return; 00390 00391 // If the stride would wrap around the i32 before exiting, we can't 00392 // transform the IV. 00393 if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 00394 return; 00395 } 00396 00397 IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 00398 00399 // Insert new integer induction variable. 00400 PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 00401 NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 00402 PN->getIncomingBlock(IncomingEdge)); 00403 00404 Value *NewAdd = 00405 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 00406 Incr->getName()+".int", Incr); 00407 NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 00408 00409 ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 00410 ConstantInt::get(Int32Ty, ExitValue), 00411 Compare->getName()); 00412 00413 // In the following deletions, PN may become dead and may be deleted. 00414 // Use a WeakVH to observe whether this happens. 00415 WeakVH WeakPH = PN; 00416 00417 // Delete the old floating point exit comparison. The branch starts using the 00418 // new comparison. 00419 NewCompare->takeName(Compare); 00420 Compare->replaceAllUsesWith(NewCompare); 00421 RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI); 00422 00423 // Delete the old floating point increment. 00424 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 00425 RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI); 00426 00427 // If the FP induction variable still has uses, this is because something else 00428 // in the loop uses its value. In order to canonicalize the induction 00429 // variable, we chose to eliminate the IV and rewrite it in terms of an 00430 // int->fp cast. 00431 // 00432 // We give preference to sitofp over uitofp because it is faster on most 00433 // platforms. 00434 if (WeakPH) { 00435 Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 00436 PN->getParent()->getFirstInsertionPt()); 00437 PN->replaceAllUsesWith(Conv); 00438 RecursivelyDeleteTriviallyDeadInstructions(PN, TLI); 00439 } 00440 Changed = true; 00441 } 00442 00443 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 00444 // First step. Check to see if there are any floating-point recurrences. 00445 // If there are, change them into integer recurrences, permitting analysis by 00446 // the SCEV routines. 00447 // 00448 BasicBlock *Header = L->getHeader(); 00449 00450 SmallVector<WeakVH, 8> PHIs; 00451 for (BasicBlock::iterator I = Header->begin(); 00452 PHINode *PN = dyn_cast<PHINode>(I); ++I) 00453 PHIs.push_back(PN); 00454 00455 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 00456 if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i])) 00457 HandleFloatingPointIV(L, PN); 00458 00459 // If the loop previously had floating-point IV, ScalarEvolution 00460 // may not have been able to compute a trip count. Now that we've done some 00461 // re-writing, the trip count may be computable. 00462 if (Changed) 00463 SE->forgetLoop(L); 00464 } 00465 00466 //===----------------------------------------------------------------------===// 00467 // RewriteLoopExitValues - Optimize IV users outside the loop. 00468 // As a side effect, reduces the amount of IV processing within the loop. 00469 //===----------------------------------------------------------------------===// 00470 00471 /// RewriteLoopExitValues - Check to see if this loop has a computable 00472 /// loop-invariant execution count. If so, this means that we can compute the 00473 /// final value of any expressions that are recurrent in the loop, and 00474 /// substitute the exit values from the loop into any instructions outside of 00475 /// the loop that use the final values of the current expressions. 00476 /// 00477 /// This is mostly redundant with the regular IndVarSimplify activities that 00478 /// happen later, except that it's more powerful in some cases, because it's 00479 /// able to brute-force evaluate arbitrary instructions as long as they have 00480 /// constant operands at the beginning of the loop. 00481 void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) { 00482 // Verify the input to the pass in already in LCSSA form. 00483 assert(L->isLCSSAForm(*DT)); 00484 00485 SmallVector<BasicBlock*, 8> ExitBlocks; 00486 L->getUniqueExitBlocks(ExitBlocks); 00487 00488 // Find all values that are computed inside the loop, but used outside of it. 00489 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 00490 // the exit blocks of the loop to find them. 00491 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 00492 BasicBlock *ExitBB = ExitBlocks[i]; 00493 00494 // If there are no PHI nodes in this exit block, then no values defined 00495 // inside the loop are used on this path, skip it. 00496 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 00497 if (!PN) continue; 00498 00499 unsigned NumPreds = PN->getNumIncomingValues(); 00500 00501 // We would like to be able to RAUW single-incoming value PHI nodes. We 00502 // have to be certain this is safe even when this is an LCSSA PHI node. 00503 // While the computed exit value is no longer varying in *this* loop, the 00504 // exit block may be an exit block for an outer containing loop as well, 00505 // the exit value may be varying in the outer loop, and thus it may still 00506 // require an LCSSA PHI node. The safe case is when this is 00507 // single-predecessor PHI node (LCSSA) and the exit block containing it is 00508 // part of the enclosing loop, or this is the outer most loop of the nest. 00509 // In either case the exit value could (at most) be varying in the same 00510 // loop body as the phi node itself. Thus if it is in turn used outside of 00511 // an enclosing loop it will only be via a separate LCSSA node. 00512 bool LCSSASafePhiForRAUW = 00513 NumPreds == 1 && 00514 (!L->getParentLoop() || L->getParentLoop() == LI->getLoopFor(ExitBB)); 00515 00516 // Iterate over all of the PHI nodes. 00517 BasicBlock::iterator BBI = ExitBB->begin(); 00518 while ((PN = dyn_cast<PHINode>(BBI++))) { 00519 if (PN->use_empty()) 00520 continue; // dead use, don't replace it 00521 00522 // SCEV only supports integer expressions for now. 00523 if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 00524 continue; 00525 00526 // It's necessary to tell ScalarEvolution about this explicitly so that 00527 // it can walk the def-use list and forget all SCEVs, as it may not be 00528 // watching the PHI itself. Once the new exit value is in place, there 00529 // may not be a def-use connection between the loop and every instruction 00530 // which got a SCEVAddRecExpr for that loop. 00531 SE->forgetValue(PN); 00532 00533 // Iterate over all of the values in all the PHI nodes. 00534 for (unsigned i = 0; i != NumPreds; ++i) { 00535 // If the value being merged in is not integer or is not defined 00536 // in the loop, skip it. 00537 Value *InVal = PN->getIncomingValue(i); 00538 if (!isa<Instruction>(InVal)) 00539 continue; 00540 00541 // If this pred is for a subloop, not L itself, skip it. 00542 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 00543 continue; // The Block is in a subloop, skip it. 00544 00545 // Check that InVal is defined in the loop. 00546 Instruction *Inst = cast<Instruction>(InVal); 00547 if (!L->contains(Inst)) 00548 continue; 00549 00550 // Okay, this instruction has a user outside of the current loop 00551 // and varies predictably *inside* the loop. Evaluate the value it 00552 // contains when the loop exits, if possible. 00553 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 00554 if (!SE->isLoopInvariant(ExitValue, L) || 00555 !isSafeToExpand(ExitValue, *SE)) 00556 continue; 00557 00558 // Computing the value outside of the loop brings no benefit if : 00559 // - it is definitely used inside the loop in a way which can not be 00560 // optimized away. 00561 // - no use outside of the loop can take advantage of hoisting the 00562 // computation out of the loop 00563 if (ExitValue->getSCEVType()>=scMulExpr) { 00564 unsigned NumHardInternalUses = 0; 00565 unsigned NumSoftExternalUses = 0; 00566 unsigned NumUses = 0; 00567 for (auto IB = Inst->user_begin(), IE = Inst->user_end(); 00568 IB != IE && NumUses <= 6; ++IB) { 00569 Instruction *UseInstr = cast<Instruction>(*IB); 00570 unsigned Opc = UseInstr->getOpcode(); 00571 NumUses++; 00572 if (L->contains(UseInstr)) { 00573 if (Opc == Instruction::Call || Opc == Instruction::Ret) 00574 NumHardInternalUses++; 00575 } else { 00576 if (Opc == Instruction::PHI) { 00577 // Do not count the Phi as a use. LCSSA may have inserted 00578 // plenty of trivial ones. 00579 NumUses--; 00580 for (auto PB = UseInstr->user_begin(), 00581 PE = UseInstr->user_end(); 00582 PB != PE && NumUses <= 6; ++PB, ++NumUses) { 00583 unsigned PhiOpc = cast<Instruction>(*PB)->getOpcode(); 00584 if (PhiOpc != Instruction::Call && PhiOpc != Instruction::Ret) 00585 NumSoftExternalUses++; 00586 } 00587 continue; 00588 } 00589 if (Opc != Instruction::Call && Opc != Instruction::Ret) 00590 NumSoftExternalUses++; 00591 } 00592 } 00593 if (NumUses <= 6 && NumHardInternalUses && !NumSoftExternalUses) 00594 continue; 00595 } 00596 00597 Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 00598 00599 DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 00600 << " LoopVal = " << *Inst << "\n"); 00601 00602 if (!isValidRewrite(Inst, ExitVal)) { 00603 DeadInsts.push_back(ExitVal); 00604 continue; 00605 } 00606 Changed = true; 00607 ++NumReplaced; 00608 00609 PN->setIncomingValue(i, ExitVal); 00610 00611 // If this instruction is dead now, delete it. Don't do it now to avoid 00612 // invalidating iterators. 00613 if (isInstructionTriviallyDead(Inst, TLI)) 00614 DeadInsts.push_back(Inst); 00615 00616 // If we determined that this PHI is safe to replace even if an LCSSA 00617 // PHI, do so. 00618 if (LCSSASafePhiForRAUW) { 00619 PN->replaceAllUsesWith(ExitVal); 00620 PN->eraseFromParent(); 00621 } 00622 } 00623 00624 // If we were unable to completely replace the PHI node, clone the PHI 00625 // and delete the original one. This lets IVUsers and any other maps 00626 // purge the original user from their records. 00627 if (!LCSSASafePhiForRAUW) { 00628 PHINode *NewPN = cast<PHINode>(PN->clone()); 00629 NewPN->takeName(PN); 00630 NewPN->insertBefore(PN); 00631 PN->replaceAllUsesWith(NewPN); 00632 PN->eraseFromParent(); 00633 } 00634 } 00635 } 00636 00637 // The insertion point instruction may have been deleted; clear it out 00638 // so that the rewriter doesn't trip over it later. 00639 Rewriter.clearInsertPoint(); 00640 } 00641 00642 //===----------------------------------------------------------------------===// 00643 // IV Widening - Extend the width of an IV to cover its widest uses. 00644 //===----------------------------------------------------------------------===// 00645 00646 namespace { 00647 // Collect information about induction variables that are used by sign/zero 00648 // extend operations. This information is recorded by CollectExtend and 00649 // provides the input to WidenIV. 00650 struct WideIVInfo { 00651 PHINode *NarrowIV; 00652 Type *WidestNativeType; // Widest integer type created [sz]ext 00653 bool IsSigned; // Was an sext user seen before a zext? 00654 00655 WideIVInfo() : NarrowIV(nullptr), WidestNativeType(nullptr), 00656 IsSigned(false) {} 00657 }; 00658 } 00659 00660 /// visitCast - Update information about the induction variable that is 00661 /// extended by this sign or zero extend operation. This is used to determine 00662 /// the final width of the IV before actually widening it. 00663 static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, 00664 const DataLayout *DL) { 00665 bool IsSigned = Cast->getOpcode() == Instruction::SExt; 00666 if (!IsSigned && Cast->getOpcode() != Instruction::ZExt) 00667 return; 00668 00669 Type *Ty = Cast->getType(); 00670 uint64_t Width = SE->getTypeSizeInBits(Ty); 00671 if (DL && !DL->isLegalInteger(Width)) 00672 return; 00673 00674 if (!WI.WidestNativeType) { 00675 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 00676 WI.IsSigned = IsSigned; 00677 return; 00678 } 00679 00680 // We extend the IV to satisfy the sign of its first user, arbitrarily. 00681 if (WI.IsSigned != IsSigned) 00682 return; 00683 00684 if (Width > SE->getTypeSizeInBits(WI.WidestNativeType)) 00685 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 00686 } 00687 00688 namespace { 00689 00690 /// NarrowIVDefUse - Record a link in the Narrow IV def-use chain along with the 00691 /// WideIV that computes the same value as the Narrow IV def. This avoids 00692 /// caching Use* pointers. 00693 struct NarrowIVDefUse { 00694 Instruction *NarrowDef; 00695 Instruction *NarrowUse; 00696 Instruction *WideDef; 00697 00698 NarrowIVDefUse(): NarrowDef(nullptr), NarrowUse(nullptr), WideDef(nullptr) {} 00699 00700 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD): 00701 NarrowDef(ND), NarrowUse(NU), WideDef(WD) {} 00702 }; 00703 00704 /// WidenIV - The goal of this transform is to remove sign and zero extends 00705 /// without creating any new induction variables. To do this, it creates a new 00706 /// phi of the wider type and redirects all users, either removing extends or 00707 /// inserting truncs whenever we stop propagating the type. 00708 /// 00709 class WidenIV { 00710 // Parameters 00711 PHINode *OrigPhi; 00712 Type *WideType; 00713 bool IsSigned; 00714 00715 // Context 00716 LoopInfo *LI; 00717 Loop *L; 00718 ScalarEvolution *SE; 00719 DominatorTree *DT; 00720 00721 // Result 00722 PHINode *WidePhi; 00723 Instruction *WideInc; 00724 const SCEV *WideIncExpr; 00725 SmallVectorImpl<WeakVH> &DeadInsts; 00726 00727 SmallPtrSet<Instruction*,16> Widened; 00728 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers; 00729 00730 public: 00731 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, 00732 ScalarEvolution *SEv, DominatorTree *DTree, 00733 SmallVectorImpl<WeakVH> &DI) : 00734 OrigPhi(WI.NarrowIV), 00735 WideType(WI.WidestNativeType), 00736 IsSigned(WI.IsSigned), 00737 LI(LInfo), 00738 L(LI->getLoopFor(OrigPhi->getParent())), 00739 SE(SEv), 00740 DT(DTree), 00741 WidePhi(nullptr), 00742 WideInc(nullptr), 00743 WideIncExpr(nullptr), 00744 DeadInsts(DI) { 00745 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); 00746 } 00747 00748 PHINode *CreateWideIV(SCEVExpander &Rewriter); 00749 00750 protected: 00751 Value *getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 00752 Instruction *Use); 00753 00754 Instruction *CloneIVUser(NarrowIVDefUse DU); 00755 00756 const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); 00757 00758 const SCEVAddRecExpr* GetExtendedOperandRecurrence(NarrowIVDefUse DU); 00759 00760 const SCEV *GetSCEVByOpCode(const SCEV *LHS, const SCEV *RHS, 00761 unsigned OpCode) const; 00762 00763 Instruction *WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter); 00764 00765 bool WidenLoopCompare(NarrowIVDefUse DU); 00766 00767 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef); 00768 }; 00769 } // anonymous namespace 00770 00771 /// isLoopInvariant - Perform a quick domtree based check for loop invariance 00772 /// assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems 00773 /// gratuitous for this purpose. 00774 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) { 00775 Instruction *Inst = dyn_cast<Instruction>(V); 00776 if (!Inst) 00777 return true; 00778 00779 return DT->properlyDominates(Inst->getParent(), L->getHeader()); 00780 } 00781 00782 Value *WidenIV::getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 00783 Instruction *Use) { 00784 // Set the debug location and conservative insertion point. 00785 IRBuilder<> Builder(Use); 00786 // Hoist the insertion point into loop preheaders as far as possible. 00787 for (const Loop *L = LI->getLoopFor(Use->getParent()); 00788 L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT); 00789 L = L->getParentLoop()) 00790 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator()); 00791 00792 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 00793 Builder.CreateZExt(NarrowOper, WideType); 00794 } 00795 00796 /// CloneIVUser - Instantiate a wide operation to replace a narrow 00797 /// operation. This only needs to handle operations that can evaluation to 00798 /// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 00799 Instruction *WidenIV::CloneIVUser(NarrowIVDefUse DU) { 00800 unsigned Opcode = DU.NarrowUse->getOpcode(); 00801 switch (Opcode) { 00802 default: 00803 return nullptr; 00804 case Instruction::Add: 00805 case Instruction::Mul: 00806 case Instruction::UDiv: 00807 case Instruction::Sub: 00808 case Instruction::And: 00809 case Instruction::Or: 00810 case Instruction::Xor: 00811 case Instruction::Shl: 00812 case Instruction::LShr: 00813 case Instruction::AShr: 00814 DEBUG(dbgs() << "Cloning IVUser: " << *DU.NarrowUse << "\n"); 00815 00816 // Replace NarrowDef operands with WideDef. Otherwise, we don't know 00817 // anything about the narrow operand yet so must insert a [sz]ext. It is 00818 // probably loop invariant and will be folded or hoisted. If it actually 00819 // comes from a widened IV, it should be removed during a future call to 00820 // WidenIVUse. 00821 Value *LHS = (DU.NarrowUse->getOperand(0) == DU.NarrowDef) ? DU.WideDef : 00822 getExtend(DU.NarrowUse->getOperand(0), WideType, IsSigned, DU.NarrowUse); 00823 Value *RHS = (DU.NarrowUse->getOperand(1) == DU.NarrowDef) ? DU.WideDef : 00824 getExtend(DU.NarrowUse->getOperand(1), WideType, IsSigned, DU.NarrowUse); 00825 00826 BinaryOperator *NarrowBO = cast<BinaryOperator>(DU.NarrowUse); 00827 BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 00828 LHS, RHS, 00829 NarrowBO->getName()); 00830 IRBuilder<> Builder(DU.NarrowUse); 00831 Builder.Insert(WideBO); 00832 if (const OverflowingBinaryOperator *OBO = 00833 dyn_cast<OverflowingBinaryOperator>(NarrowBO)) { 00834 if (OBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 00835 if (OBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 00836 } 00837 return WideBO; 00838 } 00839 } 00840 00841 const SCEV *WidenIV::GetSCEVByOpCode(const SCEV *LHS, const SCEV *RHS, 00842 unsigned OpCode) const { 00843 if (OpCode == Instruction::Add) 00844 return SE->getAddExpr(LHS, RHS); 00845 if (OpCode == Instruction::Sub) 00846 return SE->getMinusSCEV(LHS, RHS); 00847 if (OpCode == Instruction::Mul) 00848 return SE->getMulExpr(LHS, RHS); 00849 00850 llvm_unreachable("Unsupported opcode."); 00851 } 00852 00853 /// No-wrap operations can transfer sign extension of their result to their 00854 /// operands. Generate the SCEV value for the widened operation without 00855 /// actually modifying the IR yet. If the expression after extending the 00856 /// operands is an AddRec for this loop, return it. 00857 const SCEVAddRecExpr* WidenIV::GetExtendedOperandRecurrence(NarrowIVDefUse DU) { 00858 00859 // Handle the common case of add<nsw/nuw> 00860 const unsigned OpCode = DU.NarrowUse->getOpcode(); 00861 // Only Add/Sub/Mul instructions supported yet. 00862 if (OpCode != Instruction::Add && OpCode != Instruction::Sub && 00863 OpCode != Instruction::Mul) 00864 return nullptr; 00865 00866 // One operand (NarrowDef) has already been extended to WideDef. Now determine 00867 // if extending the other will lead to a recurrence. 00868 unsigned ExtendOperIdx = DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0; 00869 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU"); 00870 00871 const SCEV *ExtendOperExpr = nullptr; 00872 const OverflowingBinaryOperator *OBO = 00873 cast<OverflowingBinaryOperator>(DU.NarrowUse); 00874 if (IsSigned && OBO->hasNoSignedWrap()) 00875 ExtendOperExpr = SE->getSignExtendExpr( 00876 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 00877 else if(!IsSigned && OBO->hasNoUnsignedWrap()) 00878 ExtendOperExpr = SE->getZeroExtendExpr( 00879 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 00880 else 00881 return nullptr; 00882 00883 // When creating this SCEV expr, don't apply the current operations NSW or NUW 00884 // flags. This instruction may be guarded by control flow that the no-wrap 00885 // behavior depends on. Non-control-equivalent instructions can be mapped to 00886 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW 00887 // semantics to those operations. 00888 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>( 00889 GetSCEVByOpCode(SE->getSCEV(DU.WideDef), ExtendOperExpr, OpCode)); 00890 if (!AddRec || AddRec->getLoop() != L) 00891 return nullptr; 00892 return AddRec; 00893 } 00894 00895 /// GetWideRecurrence - Is this instruction potentially interesting from 00896 /// IVUsers' perspective after widening it's type? In other words, can the 00897 /// extend be safely hoisted out of the loop with SCEV reducing the value to a 00898 /// recurrence on the same loop. If so, return the sign or zero extended 00899 /// recurrence. Otherwise return NULL. 00900 const SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 00901 if (!SE->isSCEVable(NarrowUse->getType())) 00902 return nullptr; 00903 00904 const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 00905 if (SE->getTypeSizeInBits(NarrowExpr->getType()) 00906 >= SE->getTypeSizeInBits(WideType)) { 00907 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow 00908 // index. So don't follow this use. 00909 return nullptr; 00910 } 00911 00912 const SCEV *WideExpr = IsSigned ? 00913 SE->getSignExtendExpr(NarrowExpr, WideType) : 00914 SE->getZeroExtendExpr(NarrowExpr, WideType); 00915 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 00916 if (!AddRec || AddRec->getLoop() != L) 00917 return nullptr; 00918 return AddRec; 00919 } 00920 00921 /// This IV user cannot be widen. Replace this use of the original narrow IV 00922 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV. 00923 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT) { 00924 DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef 00925 << " for user " << *DU.NarrowUse << "\n"); 00926 IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT)); 00927 Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType()); 00928 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc); 00929 } 00930 00931 /// If the narrow use is a compare instruction, then widen the compare 00932 // (and possibly the other operand). The extend operation is hoisted into the 00933 // loop preheader as far as possible. 00934 bool WidenIV::WidenLoopCompare(NarrowIVDefUse DU) { 00935 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse); 00936 if (!Cmp) 00937 return false; 00938 00939 bool IsSigned = CmpInst::isSigned(Cmp->getPredicate()); 00940 if (!IsSigned) 00941 return false; 00942 00943 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0); 00944 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType()); 00945 unsigned IVWidth = SE->getTypeSizeInBits(WideType); 00946 assert (CastWidth <= IVWidth && "Unexpected width while widening compare."); 00947 00948 // Widen the compare instruction. 00949 IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT)); 00950 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef); 00951 00952 // Widen the other operand of the compare, if necessary. 00953 if (CastWidth < IVWidth) { 00954 Value *ExtOp = getExtend(Op, WideType, IsSigned, Cmp); 00955 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp); 00956 } 00957 return true; 00958 } 00959 00960 /// WidenIVUse - Determine whether an individual user of the narrow IV can be 00961 /// widened. If so, return the wide clone of the user. 00962 Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) { 00963 00964 // Stop traversing the def-use chain at inner-loop phis or post-loop phis. 00965 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) { 00966 if (LI->getLoopFor(UsePhi->getParent()) != L) { 00967 // For LCSSA phis, sink the truncate outside the loop. 00968 // After SimplifyCFG most loop exit targets have a single predecessor. 00969 // Otherwise fall back to a truncate within the loop. 00970 if (UsePhi->getNumOperands() != 1) 00971 truncateIVUse(DU, DT); 00972 else { 00973 PHINode *WidePhi = 00974 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide", 00975 UsePhi); 00976 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0)); 00977 IRBuilder<> Builder(WidePhi->getParent()->getFirstInsertionPt()); 00978 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType()); 00979 UsePhi->replaceAllUsesWith(Trunc); 00980 DeadInsts.push_back(UsePhi); 00981 DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi 00982 << " to " << *WidePhi << "\n"); 00983 } 00984 return nullptr; 00985 } 00986 } 00987 // Our raison d'etre! Eliminate sign and zero extension. 00988 if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) { 00989 Value *NewDef = DU.WideDef; 00990 if (DU.NarrowUse->getType() != WideType) { 00991 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType()); 00992 unsigned IVWidth = SE->getTypeSizeInBits(WideType); 00993 if (CastWidth < IVWidth) { 00994 // The cast isn't as wide as the IV, so insert a Trunc. 00995 IRBuilder<> Builder(DU.NarrowUse); 00996 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType()); 00997 } 00998 else { 00999 // A wider extend was hidden behind a narrower one. This may induce 01000 // another round of IV widening in which the intermediate IV becomes 01001 // dead. It should be very rare. 01002 DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi 01003 << " not wide enough to subsume " << *DU.NarrowUse << "\n"); 01004 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef); 01005 NewDef = DU.NarrowUse; 01006 } 01007 } 01008 if (NewDef != DU.NarrowUse) { 01009 DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse 01010 << " replaced by " << *DU.WideDef << "\n"); 01011 ++NumElimExt; 01012 DU.NarrowUse->replaceAllUsesWith(NewDef); 01013 DeadInsts.push_back(DU.NarrowUse); 01014 } 01015 // Now that the extend is gone, we want to expose it's uses for potential 01016 // further simplification. We don't need to directly inform SimplifyIVUsers 01017 // of the new users, because their parent IV will be processed later as a 01018 // new loop phi. If we preserved IVUsers analysis, we would also want to 01019 // push the uses of WideDef here. 01020 01021 // No further widening is needed. The deceased [sz]ext had done it for us. 01022 return nullptr; 01023 } 01024 01025 // Does this user itself evaluate to a recurrence after widening? 01026 const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(DU.NarrowUse); 01027 if (!WideAddRec) 01028 WideAddRec = GetExtendedOperandRecurrence(DU); 01029 01030 if (!WideAddRec) { 01031 // If use is a loop condition, try to promote the condition instead of 01032 // truncating the IV first. 01033 if (WidenLoopCompare(DU)) 01034 return nullptr; 01035 01036 // This user does not evaluate to a recurence after widening, so don't 01037 // follow it. Instead insert a Trunc to kill off the original use, 01038 // eventually isolating the original narrow IV so it can be removed. 01039 truncateIVUse(DU, DT); 01040 return nullptr; 01041 } 01042 // Assume block terminators cannot evaluate to a recurrence. We can't to 01043 // insert a Trunc after a terminator if there happens to be a critical edge. 01044 assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() && 01045 "SCEV is not expected to evaluate a block terminator"); 01046 01047 // Reuse the IV increment that SCEVExpander created as long as it dominates 01048 // NarrowUse. 01049 Instruction *WideUse = nullptr; 01050 if (WideAddRec == WideIncExpr 01051 && Rewriter.hoistIVInc(WideInc, DU.NarrowUse)) 01052 WideUse = WideInc; 01053 else { 01054 WideUse = CloneIVUser(DU); 01055 if (!WideUse) 01056 return nullptr; 01057 } 01058 // Evaluation of WideAddRec ensured that the narrow expression could be 01059 // extended outside the loop without overflow. This suggests that the wide use 01060 // evaluates to the same expression as the extended narrow use, but doesn't 01061 // absolutely guarantee it. Hence the following failsafe check. In rare cases 01062 // where it fails, we simply throw away the newly created wide use. 01063 if (WideAddRec != SE->getSCEV(WideUse)) { 01064 DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 01065 << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 01066 DeadInsts.push_back(WideUse); 01067 return nullptr; 01068 } 01069 01070 // Returning WideUse pushes it on the worklist. 01071 return WideUse; 01072 } 01073 01074 /// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers. 01075 /// 01076 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) { 01077 for (User *U : NarrowDef->users()) { 01078 Instruction *NarrowUser = cast<Instruction>(U); 01079 01080 // Handle data flow merges and bizarre phi cycles. 01081 if (!Widened.insert(NarrowUser)) 01082 continue; 01083 01084 NarrowIVUsers.push_back(NarrowIVDefUse(NarrowDef, NarrowUser, WideDef)); 01085 } 01086 } 01087 01088 /// CreateWideIV - Process a single induction variable. First use the 01089 /// SCEVExpander to create a wide induction variable that evaluates to the same 01090 /// recurrence as the original narrow IV. Then use a worklist to forward 01091 /// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 01092 /// interesting IV users, the narrow IV will be isolated for removal by 01093 /// DeleteDeadPHIs. 01094 /// 01095 /// It would be simpler to delete uses as they are processed, but we must avoid 01096 /// invalidating SCEV expressions. 01097 /// 01098 PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 01099 // Is this phi an induction variable? 01100 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 01101 if (!AddRec) 01102 return nullptr; 01103 01104 // Widen the induction variable expression. 01105 const SCEV *WideIVExpr = IsSigned ? 01106 SE->getSignExtendExpr(AddRec, WideType) : 01107 SE->getZeroExtendExpr(AddRec, WideType); 01108 01109 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 01110 "Expect the new IV expression to preserve its type"); 01111 01112 // Can the IV be extended outside the loop without overflow? 01113 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 01114 if (!AddRec || AddRec->getLoop() != L) 01115 return nullptr; 01116 01117 // An AddRec must have loop-invariant operands. Since this AddRec is 01118 // materialized by a loop header phi, the expression cannot have any post-loop 01119 // operands, so they must dominate the loop header. 01120 assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 01121 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 01122 && "Loop header phi recurrence inputs do not dominate the loop"); 01123 01124 // The rewriter provides a value for the desired IV expression. This may 01125 // either find an existing phi or materialize a new one. Either way, we 01126 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 01127 // of the phi-SCC dominates the loop entry. 01128 Instruction *InsertPt = L->getHeader()->begin(); 01129 WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 01130 01131 // Remembering the WideIV increment generated by SCEVExpander allows 01132 // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 01133 // employ a general reuse mechanism because the call above is the only call to 01134 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 01135 if (BasicBlock *LatchBlock = L->getLoopLatch()) { 01136 WideInc = 01137 cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 01138 WideIncExpr = SE->getSCEV(WideInc); 01139 } 01140 01141 DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 01142 ++NumWidened; 01143 01144 // Traverse the def-use chain using a worklist starting at the original IV. 01145 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" ); 01146 01147 Widened.insert(OrigPhi); 01148 pushNarrowIVUsers(OrigPhi, WidePhi); 01149 01150 while (!NarrowIVUsers.empty()) { 01151 NarrowIVDefUse DU = NarrowIVUsers.pop_back_val(); 01152 01153 // Process a def-use edge. This may replace the use, so don't hold a 01154 // use_iterator across it. 01155 Instruction *WideUse = WidenIVUse(DU, Rewriter); 01156 01157 // Follow all def-use edges from the previous narrow use. 01158 if (WideUse) 01159 pushNarrowIVUsers(DU.NarrowUse, WideUse); 01160 01161 // WidenIVUse may have removed the def-use edge. 01162 if (DU.NarrowDef->use_empty()) 01163 DeadInsts.push_back(DU.NarrowDef); 01164 } 01165 return WidePhi; 01166 } 01167 01168 //===----------------------------------------------------------------------===// 01169 // Live IV Reduction - Minimize IVs live across the loop. 01170 //===----------------------------------------------------------------------===// 01171 01172 01173 //===----------------------------------------------------------------------===// 01174 // Simplification of IV users based on SCEV evaluation. 01175 //===----------------------------------------------------------------------===// 01176 01177 namespace { 01178 class IndVarSimplifyVisitor : public IVVisitor { 01179 ScalarEvolution *SE; 01180 const DataLayout *DL; 01181 PHINode *IVPhi; 01182 01183 public: 01184 WideIVInfo WI; 01185 01186 IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV, 01187 const DataLayout *DL, const DominatorTree *DTree): 01188 SE(SCEV), DL(DL), IVPhi(IV) { 01189 DT = DTree; 01190 WI.NarrowIV = IVPhi; 01191 if (ReduceLiveIVs) 01192 setSplitOverflowIntrinsics(); 01193 } 01194 01195 // Implement the interface used by simplifyUsersOfIV. 01196 void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, DL); } 01197 }; 01198 } 01199 01200 /// SimplifyAndExtend - Iteratively perform simplification on a worklist of IV 01201 /// users. Each successive simplification may push more users which may 01202 /// themselves be candidates for simplification. 01203 /// 01204 /// Sign/Zero extend elimination is interleaved with IV simplification. 01205 /// 01206 void IndVarSimplify::SimplifyAndExtend(Loop *L, 01207 SCEVExpander &Rewriter, 01208 LPPassManager &LPM) { 01209 SmallVector<WideIVInfo, 8> WideIVs; 01210 01211 SmallVector<PHINode*, 8> LoopPhis; 01212 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 01213 LoopPhis.push_back(cast<PHINode>(I)); 01214 } 01215 // Each round of simplification iterates through the SimplifyIVUsers worklist 01216 // for all current phis, then determines whether any IVs can be 01217 // widened. Widening adds new phis to LoopPhis, inducing another round of 01218 // simplification on the wide IVs. 01219 while (!LoopPhis.empty()) { 01220 // Evaluate as many IV expressions as possible before widening any IVs. This 01221 // forces SCEV to set no-wrap flags before evaluating sign/zero 01222 // extension. The first time SCEV attempts to normalize sign/zero extension, 01223 // the result becomes final. So for the most predictable results, we delay 01224 // evaluation of sign/zero extend evaluation until needed, and avoid running 01225 // other SCEV based analysis prior to SimplifyAndExtend. 01226 do { 01227 PHINode *CurrIV = LoopPhis.pop_back_val(); 01228 01229 // Information about sign/zero extensions of CurrIV. 01230 IndVarSimplifyVisitor Visitor(CurrIV, SE, DL, DT); 01231 01232 Changed |= simplifyUsersOfIV(CurrIV, SE, &LPM, DeadInsts, &Visitor); 01233 01234 if (Visitor.WI.WidestNativeType) { 01235 WideIVs.push_back(Visitor.WI); 01236 } 01237 } while(!LoopPhis.empty()); 01238 01239 for (; !WideIVs.empty(); WideIVs.pop_back()) { 01240 WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts); 01241 if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 01242 Changed = true; 01243 LoopPhis.push_back(WidePhi); 01244 } 01245 } 01246 } 01247 } 01248 01249 //===----------------------------------------------------------------------===// 01250 // LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. 01251 //===----------------------------------------------------------------------===// 01252 01253 /// Check for expressions that ScalarEvolution generates to compute 01254 /// BackedgeTakenInfo. If these expressions have not been reduced, then 01255 /// expanding them may incur additional cost (albeit in the loop preheader). 01256 static bool isHighCostExpansion(const SCEV *S, BranchInst *BI, 01257 SmallPtrSetImpl<const SCEV*> &Processed, 01258 ScalarEvolution *SE) { 01259 if (!Processed.insert(S)) 01260 return false; 01261 01262 // If the backedge-taken count is a UDiv, it's very likely a UDiv that 01263 // ScalarEvolution's HowFarToZero or HowManyLessThans produced to compute a 01264 // precise expression, rather than a UDiv from the user's code. If we can't 01265 // find a UDiv in the code with some simple searching, assume the former and 01266 // forego rewriting the loop. 01267 if (isa<SCEVUDivExpr>(S)) { 01268 ICmpInst *OrigCond = dyn_cast<ICmpInst>(BI->getCondition()); 01269 if (!OrigCond) return true; 01270 const SCEV *R = SE->getSCEV(OrigCond->getOperand(1)); 01271 R = SE->getMinusSCEV(R, SE->getConstant(R->getType(), 1)); 01272 if (R != S) { 01273 const SCEV *L = SE->getSCEV(OrigCond->getOperand(0)); 01274 L = SE->getMinusSCEV(L, SE->getConstant(L->getType(), 1)); 01275 if (L != S) 01276 return true; 01277 } 01278 } 01279 01280 // Recurse past add expressions, which commonly occur in the 01281 // BackedgeTakenCount. They may already exist in program code, and if not, 01282 // they are not too expensive rematerialize. 01283 if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) { 01284 for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end(); 01285 I != E; ++I) { 01286 if (isHighCostExpansion(*I, BI, Processed, SE)) 01287 return true; 01288 } 01289 return false; 01290 } 01291 01292 // HowManyLessThans uses a Max expression whenever the loop is not guarded by 01293 // the exit condition. 01294 if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S)) 01295 return true; 01296 01297 // If we haven't recognized an expensive SCEV pattern, assume it's an 01298 // expression produced by program code. 01299 return false; 01300 } 01301 01302 /// canExpandBackedgeTakenCount - Return true if this loop's backedge taken 01303 /// count expression can be safely and cheaply expanded into an instruction 01304 /// sequence that can be used by LinearFunctionTestReplace. 01305 /// 01306 /// TODO: This fails for pointer-type loop counters with greater than one byte 01307 /// strides, consequently preventing LFTR from running. For the purpose of LFTR 01308 /// we could skip this check in the case that the LFTR loop counter (chosen by 01309 /// FindLoopCounter) is also pointer type. Instead, we could directly convert 01310 /// the loop test to an inequality test by checking the target data's alignment 01311 /// of element types (given that the initial pointer value originates from or is 01312 /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint). 01313 /// However, we don't yet have a strong motivation for converting loop tests 01314 /// into inequality tests. 01315 static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE) { 01316 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 01317 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || 01318 BackedgeTakenCount->isZero()) 01319 return false; 01320 01321 if (!L->getExitingBlock()) 01322 return false; 01323 01324 // Can't rewrite non-branch yet. 01325 BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 01326 if (!BI) 01327 return false; 01328 01329 SmallPtrSet<const SCEV*, 8> Processed; 01330 if (isHighCostExpansion(BackedgeTakenCount, BI, Processed, SE)) 01331 return false; 01332 01333 return true; 01334 } 01335 01336 /// getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop 01337 /// invariant value to the phi. 01338 static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) { 01339 Instruction *IncI = dyn_cast<Instruction>(IncV); 01340 if (!IncI) 01341 return nullptr; 01342 01343 switch (IncI->getOpcode()) { 01344 case Instruction::Add: 01345 case Instruction::Sub: 01346 break; 01347 case Instruction::GetElementPtr: 01348 // An IV counter must preserve its type. 01349 if (IncI->getNumOperands() == 2) 01350 break; 01351 default: 01352 return nullptr; 01353 } 01354 01355 PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0)); 01356 if (Phi && Phi->getParent() == L->getHeader()) { 01357 if (isLoopInvariant(IncI->getOperand(1), L, DT)) 01358 return Phi; 01359 return nullptr; 01360 } 01361 if (IncI->getOpcode() == Instruction::GetElementPtr) 01362 return nullptr; 01363 01364 // Allow add/sub to be commuted. 01365 Phi = dyn_cast<PHINode>(IncI->getOperand(1)); 01366 if (Phi && Phi->getParent() == L->getHeader()) { 01367 if (isLoopInvariant(IncI->getOperand(0), L, DT)) 01368 return Phi; 01369 } 01370 return nullptr; 01371 } 01372 01373 /// Return the compare guarding the loop latch, or NULL for unrecognized tests. 01374 static ICmpInst *getLoopTest(Loop *L) { 01375 assert(L->getExitingBlock() && "expected loop exit"); 01376 01377 BasicBlock *LatchBlock = L->getLoopLatch(); 01378 // Don't bother with LFTR if the loop is not properly simplified. 01379 if (!LatchBlock) 01380 return nullptr; 01381 01382 BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 01383 assert(BI && "expected exit branch"); 01384 01385 return dyn_cast<ICmpInst>(BI->getCondition()); 01386 } 01387 01388 /// needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show 01389 /// that the current exit test is already sufficiently canonical. 01390 static bool needsLFTR(Loop *L, DominatorTree *DT) { 01391 // Do LFTR to simplify the exit condition to an ICMP. 01392 ICmpInst *Cond = getLoopTest(L); 01393 if (!Cond) 01394 return true; 01395 01396 // Do LFTR to simplify the exit ICMP to EQ/NE 01397 ICmpInst::Predicate Pred = Cond->getPredicate(); 01398 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) 01399 return true; 01400 01401 // Look for a loop invariant RHS 01402 Value *LHS = Cond->getOperand(0); 01403 Value *RHS = Cond->getOperand(1); 01404 if (!isLoopInvariant(RHS, L, DT)) { 01405 if (!isLoopInvariant(LHS, L, DT)) 01406 return true; 01407 std::swap(LHS, RHS); 01408 } 01409 // Look for a simple IV counter LHS 01410 PHINode *Phi = dyn_cast<PHINode>(LHS); 01411 if (!Phi) 01412 Phi = getLoopPhiForCounter(LHS, L, DT); 01413 01414 if (!Phi) 01415 return true; 01416 01417 // Do LFTR if PHI node is defined in the loop, but is *not* a counter. 01418 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch()); 01419 if (Idx < 0) 01420 return true; 01421 01422 // Do LFTR if the exit condition's IV is *not* a simple counter. 01423 Value *IncV = Phi->getIncomingValue(Idx); 01424 return Phi != getLoopPhiForCounter(IncV, L, DT); 01425 } 01426 01427 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils 01428 /// down to checking that all operands are constant and listing instructions 01429 /// that may hide undef. 01430 static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited, 01431 unsigned Depth) { 01432 if (isa<Constant>(V)) 01433 return !isa<UndefValue>(V); 01434 01435 if (Depth >= 6) 01436 return false; 01437 01438 // Conservatively handle non-constant non-instructions. For example, Arguments 01439 // may be undef. 01440 Instruction *I = dyn_cast<Instruction>(V); 01441 if (!I) 01442 return false; 01443 01444 // Load and return values may be undef. 01445 if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I)) 01446 return false; 01447 01448 // Optimistically handle other instructions. 01449 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { 01450 if (!Visited.insert(*OI)) 01451 continue; 01452 if (!hasConcreteDefImpl(*OI, Visited, Depth+1)) 01453 return false; 01454 } 01455 return true; 01456 } 01457 01458 /// Return true if the given value is concrete. We must prove that undef can 01459 /// never reach it. 01460 /// 01461 /// TODO: If we decide that this is a good approach to checking for undef, we 01462 /// may factor it into a common location. 01463 static bool hasConcreteDef(Value *V) { 01464 SmallPtrSet<Value*, 8> Visited; 01465 Visited.insert(V); 01466 return hasConcreteDefImpl(V, Visited, 0); 01467 } 01468 01469 /// AlmostDeadIV - Return true if this IV has any uses other than the (soon to 01470 /// be rewritten) loop exit test. 01471 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) { 01472 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 01473 Value *IncV = Phi->getIncomingValue(LatchIdx); 01474 01475 for (User *U : Phi->users()) 01476 if (U != Cond && U != IncV) return false; 01477 01478 for (User *U : IncV->users()) 01479 if (U != Cond && U != Phi) return false; 01480 return true; 01481 } 01482 01483 /// FindLoopCounter - Find an affine IV in canonical form. 01484 /// 01485 /// BECount may be an i8* pointer type. The pointer difference is already 01486 /// valid count without scaling the address stride, so it remains a pointer 01487 /// expression as far as SCEV is concerned. 01488 /// 01489 /// Currently only valid for LFTR. See the comments on hasConcreteDef below. 01490 /// 01491 /// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount 01492 /// 01493 /// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride. 01494 /// This is difficult in general for SCEV because of potential overflow. But we 01495 /// could at least handle constant BECounts. 01496 static PHINode * 01497 FindLoopCounter(Loop *L, const SCEV *BECount, 01498 ScalarEvolution *SE, DominatorTree *DT, const DataLayout *DL) { 01499 uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType()); 01500 01501 Value *Cond = 01502 cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition(); 01503 01504 // Loop over all of the PHI nodes, looking for a simple counter. 01505 PHINode *BestPhi = nullptr; 01506 const SCEV *BestInit = nullptr; 01507 BasicBlock *LatchBlock = L->getLoopLatch(); 01508 assert(LatchBlock && "needsLFTR should guarantee a loop latch"); 01509 01510 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 01511 PHINode *Phi = cast<PHINode>(I); 01512 if (!SE->isSCEVable(Phi->getType())) 01513 continue; 01514 01515 // Avoid comparing an integer IV against a pointer Limit. 01516 if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy()) 01517 continue; 01518 01519 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi)); 01520 if (!AR || AR->getLoop() != L || !AR->isAffine()) 01521 continue; 01522 01523 // AR may be a pointer type, while BECount is an integer type. 01524 // AR may be wider than BECount. With eq/ne tests overflow is immaterial. 01525 // AR may not be a narrower type, or we may never exit. 01526 uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType()); 01527 if (PhiWidth < BCWidth || (DL && !DL->isLegalInteger(PhiWidth))) 01528 continue; 01529 01530 const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 01531 if (!Step || !Step->isOne()) 01532 continue; 01533 01534 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 01535 Value *IncV = Phi->getIncomingValue(LatchIdx); 01536 if (getLoopPhiForCounter(IncV, L, DT) != Phi) 01537 continue; 01538 01539 // Avoid reusing a potentially undef value to compute other values that may 01540 // have originally had a concrete definition. 01541 if (!hasConcreteDef(Phi)) { 01542 // We explicitly allow unknown phis as long as they are already used by 01543 // the loop test. In this case we assume that performing LFTR could not 01544 // increase the number of undef users. 01545 if (ICmpInst *Cond = getLoopTest(L)) { 01546 if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT) 01547 && Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) { 01548 continue; 01549 } 01550 } 01551 } 01552 const SCEV *Init = AR->getStart(); 01553 01554 if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) { 01555 // Don't force a live loop counter if another IV can be used. 01556 if (AlmostDeadIV(Phi, LatchBlock, Cond)) 01557 continue; 01558 01559 // Prefer to count-from-zero. This is a more "canonical" counter form. It 01560 // also prefers integer to pointer IVs. 01561 if (BestInit->isZero() != Init->isZero()) { 01562 if (BestInit->isZero()) 01563 continue; 01564 } 01565 // If two IVs both count from zero or both count from nonzero then the 01566 // narrower is likely a dead phi that has been widened. Use the wider phi 01567 // to allow the other to be eliminated. 01568 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType())) 01569 continue; 01570 } 01571 BestPhi = Phi; 01572 BestInit = Init; 01573 } 01574 return BestPhi; 01575 } 01576 01577 /// genLoopLimit - Help LinearFunctionTestReplace by generating a value that 01578 /// holds the RHS of the new loop test. 01579 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L, 01580 SCEVExpander &Rewriter, ScalarEvolution *SE) { 01581 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 01582 assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter"); 01583 const SCEV *IVInit = AR->getStart(); 01584 01585 // IVInit may be a pointer while IVCount is an integer when FindLoopCounter 01586 // finds a valid pointer IV. Sign extend BECount in order to materialize a 01587 // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing 01588 // the existing GEPs whenever possible. 01589 if (IndVar->getType()->isPointerTy() 01590 && !IVCount->getType()->isPointerTy()) { 01591 01592 // IVOffset will be the new GEP offset that is interpreted by GEP as a 01593 // signed value. IVCount on the other hand represents the loop trip count, 01594 // which is an unsigned value. FindLoopCounter only allows induction 01595 // variables that have a positive unit stride of one. This means we don't 01596 // have to handle the case of negative offsets (yet) and just need to zero 01597 // extend IVCount. 01598 Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType()); 01599 const SCEV *IVOffset = SE->getTruncateOrZeroExtend(IVCount, OfsTy); 01600 01601 // Expand the code for the iteration count. 01602 assert(SE->isLoopInvariant(IVOffset, L) && 01603 "Computed iteration count is not loop invariant!"); 01604 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 01605 Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI); 01606 01607 Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader()); 01608 assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter"); 01609 // We could handle pointer IVs other than i8*, but we need to compensate for 01610 // gep index scaling. See canExpandBackedgeTakenCount comments. 01611 assert(SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), 01612 cast<PointerType>(GEPBase->getType())->getElementType())->isOne() 01613 && "unit stride pointer IV must be i8*"); 01614 01615 IRBuilder<> Builder(L->getLoopPreheader()->getTerminator()); 01616 return Builder.CreateGEP(GEPBase, GEPOffset, "lftr.limit"); 01617 } 01618 else { 01619 // In any other case, convert both IVInit and IVCount to integers before 01620 // comparing. This may result in SCEV expension of pointers, but in practice 01621 // SCEV will fold the pointer arithmetic away as such: 01622 // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc). 01623 // 01624 // Valid Cases: (1) both integers is most common; (2) both may be pointers 01625 // for simple memset-style loops. 01626 // 01627 // IVInit integer and IVCount pointer would only occur if a canonical IV 01628 // were generated on top of case #2, which is not expected. 01629 01630 const SCEV *IVLimit = nullptr; 01631 // For unit stride, IVCount = Start + BECount with 2's complement overflow. 01632 // For non-zero Start, compute IVCount here. 01633 if (AR->getStart()->isZero()) 01634 IVLimit = IVCount; 01635 else { 01636 assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride"); 01637 const SCEV *IVInit = AR->getStart(); 01638 01639 // For integer IVs, truncate the IV before computing IVInit + BECount. 01640 if (SE->getTypeSizeInBits(IVInit->getType()) 01641 > SE->getTypeSizeInBits(IVCount->getType())) 01642 IVInit = SE->getTruncateExpr(IVInit, IVCount->getType()); 01643 01644 IVLimit = SE->getAddExpr(IVInit, IVCount); 01645 } 01646 // Expand the code for the iteration count. 01647 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 01648 IRBuilder<> Builder(BI); 01649 assert(SE->isLoopInvariant(IVLimit, L) && 01650 "Computed iteration count is not loop invariant!"); 01651 // Ensure that we generate the same type as IndVar, or a smaller integer 01652 // type. In the presence of null pointer values, we have an integer type 01653 // SCEV expression (IVInit) for a pointer type IV value (IndVar). 01654 Type *LimitTy = IVCount->getType()->isPointerTy() ? 01655 IndVar->getType() : IVCount->getType(); 01656 return Rewriter.expandCodeFor(IVLimit, LimitTy, BI); 01657 } 01658 } 01659 01660 /// LinearFunctionTestReplace - This method rewrites the exit condition of the 01661 /// loop to be a canonical != comparison against the incremented loop induction 01662 /// variable. This pass is able to rewrite the exit tests of any loop where the 01663 /// SCEV analysis can determine a loop-invariant trip count of the loop, which 01664 /// is actually a much broader range than just linear tests. 01665 Value *IndVarSimplify:: 01666 LinearFunctionTestReplace(Loop *L, 01667 const SCEV *BackedgeTakenCount, 01668 PHINode *IndVar, 01669 SCEVExpander &Rewriter) { 01670 assert(canExpandBackedgeTakenCount(L, SE) && "precondition"); 01671 01672 // Initialize CmpIndVar and IVCount to their preincremented values. 01673 Value *CmpIndVar = IndVar; 01674 const SCEV *IVCount = BackedgeTakenCount; 01675 01676 // If the exiting block is the same as the backedge block, we prefer to 01677 // compare against the post-incremented value, otherwise we must compare 01678 // against the preincremented value. 01679 if (L->getExitingBlock() == L->getLoopLatch()) { 01680 // The BackedgeTaken expression contains the number of times that the 01681 // backedge branches to the loop header. This is one less than the 01682 // number of times the loop executes, so use the incremented indvar. 01683 llvm::Value *IncrementedIndvar = 01684 IndVar->getIncomingValueForBlock(L->getExitingBlock()); 01685 const auto *IncrementedIndvarSCEV = 01686 cast<SCEVAddRecExpr>(SE->getSCEV(IncrementedIndvar)); 01687 // It is unsafe to use the incremented indvar if it has a wrapping flag, we 01688 // don't want to compare against a poison value. Check the SCEV that 01689 // corresponds to the incremented indvar, the SCEVExpander will only insert 01690 // flags in the IR if the SCEV originally had wrapping flags. 01691 // FIXME: In theory, SCEV could drop flags even though they exist in IR. 01692 // A more robust solution would involve getting a new expression for 01693 // CmpIndVar by applying non-NSW/NUW AddExprs. 01694 if (!ScalarEvolution::maskFlags(IncrementedIndvarSCEV->getNoWrapFlags(), 01695 SCEV::FlagNUW | SCEV::FlagNSW)) { 01696 // Add one to the "backedge-taken" count to get the trip count. 01697 // This addition may overflow, which is valid as long as the comparison is 01698 // truncated to BackedgeTakenCount->getType(). 01699 IVCount = 01700 SE->getAddExpr(BackedgeTakenCount, 01701 SE->getConstant(BackedgeTakenCount->getType(), 1)); 01702 CmpIndVar = IncrementedIndvar; 01703 } 01704 } 01705 01706 Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE); 01707 assert(ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() 01708 && "genLoopLimit missed a cast"); 01709 01710 // Insert a new icmp_ne or icmp_eq instruction before the branch. 01711 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 01712 ICmpInst::Predicate P; 01713 if (L->contains(BI->getSuccessor(0))) 01714 P = ICmpInst::ICMP_NE; 01715 else 01716 P = ICmpInst::ICMP_EQ; 01717 01718 DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 01719 << " LHS:" << *CmpIndVar << '\n' 01720 << " op:\t" 01721 << (P == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 01722 << " RHS:\t" << *ExitCnt << "\n" 01723 << " IVCount:\t" << *IVCount << "\n"); 01724 01725 IRBuilder<> Builder(BI); 01726 01727 // LFTR can ignore IV overflow and truncate to the width of 01728 // BECount. This avoids materializing the add(zext(add)) expression. 01729 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType()); 01730 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType()); 01731 if (CmpIndVarSize > ExitCntSize) { 01732 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 01733 const SCEV *ARStart = AR->getStart(); 01734 const SCEV *ARStep = AR->getStepRecurrence(*SE); 01735 // For constant IVCount, avoid truncation. 01736 if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) { 01737 const APInt &Start = cast<SCEVConstant>(ARStart)->getValue()->getValue(); 01738 APInt Count = cast<SCEVConstant>(IVCount)->getValue()->getValue(); 01739 // Note that the post-inc value of BackedgeTakenCount may have overflowed 01740 // above such that IVCount is now zero. 01741 if (IVCount != BackedgeTakenCount && Count == 0) { 01742 Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize); 01743 ++Count; 01744 } 01745 else 01746 Count = Count.zext(CmpIndVarSize); 01747 APInt NewLimit; 01748 if (cast<SCEVConstant>(ARStep)->getValue()->isNegative()) 01749 NewLimit = Start - Count; 01750 else 01751 NewLimit = Start + Count; 01752 ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit); 01753 01754 DEBUG(dbgs() << " Widen RHS:\t" << *ExitCnt << "\n"); 01755 } else { 01756 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(), 01757 "lftr.wideiv"); 01758 } 01759 } 01760 Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond"); 01761 Value *OrigCond = BI->getCondition(); 01762 // It's tempting to use replaceAllUsesWith here to fully replace the old 01763 // comparison, but that's not immediately safe, since users of the old 01764 // comparison may not be dominated by the new comparison. Instead, just 01765 // update the branch to use the new comparison; in the common case this 01766 // will make old comparison dead. 01767 BI->setCondition(Cond); 01768 DeadInsts.push_back(OrigCond); 01769 01770 ++NumLFTR; 01771 Changed = true; 01772 return Cond; 01773 } 01774 01775 //===----------------------------------------------------------------------===// 01776 // SinkUnusedInvariants. A late subpass to cleanup loop preheaders. 01777 //===----------------------------------------------------------------------===// 01778 01779 /// If there's a single exit block, sink any loop-invariant values that 01780 /// were defined in the preheader but not used inside the loop into the 01781 /// exit block to reduce register pressure in the loop. 01782 void IndVarSimplify::SinkUnusedInvariants(Loop *L) { 01783 BasicBlock *ExitBlock = L->getExitBlock(); 01784 if (!ExitBlock) return; 01785 01786 BasicBlock *Preheader = L->getLoopPreheader(); 01787 if (!Preheader) return; 01788 01789 Instruction *InsertPt = ExitBlock->getFirstInsertionPt(); 01790 BasicBlock::iterator I = Preheader->getTerminator(); 01791 while (I != Preheader->begin()) { 01792 --I; 01793 // New instructions were inserted at the end of the preheader. 01794 if (isa<PHINode>(I)) 01795 break; 01796 01797 // Don't move instructions which might have side effects, since the side 01798 // effects need to complete before instructions inside the loop. Also don't 01799 // move instructions which might read memory, since the loop may modify 01800 // memory. Note that it's okay if the instruction might have undefined 01801 // behavior: LoopSimplify guarantees that the preheader dominates the exit 01802 // block. 01803 if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 01804 continue; 01805 01806 // Skip debug info intrinsics. 01807 if (isa<DbgInfoIntrinsic>(I)) 01808 continue; 01809 01810 // Skip landingpad instructions. 01811 if (isa<LandingPadInst>(I)) 01812 continue; 01813 01814 // Don't sink alloca: we never want to sink static alloca's out of the 01815 // entry block, and correctly sinking dynamic alloca's requires 01816 // checks for stacksave/stackrestore intrinsics. 01817 // FIXME: Refactor this check somehow? 01818 if (isa<AllocaInst>(I)) 01819 continue; 01820 01821 // Determine if there is a use in or before the loop (direct or 01822 // otherwise). 01823 bool UsedInLoop = false; 01824 for (Use &U : I->uses()) { 01825 Instruction *User = cast<Instruction>(U.getUser()); 01826 BasicBlock *UseBB = User->getParent(); 01827 if (PHINode *P = dyn_cast<PHINode>(User)) { 01828 unsigned i = 01829 PHINode::getIncomingValueNumForOperand(U.getOperandNo()); 01830 UseBB = P->getIncomingBlock(i); 01831 } 01832 if (UseBB == Preheader || L->contains(UseBB)) { 01833 UsedInLoop = true; 01834 break; 01835 } 01836 } 01837 01838 // If there is, the def must remain in the preheader. 01839 if (UsedInLoop) 01840 continue; 01841 01842 // Otherwise, sink it to the exit block. 01843 Instruction *ToMove = I; 01844 bool Done = false; 01845 01846 if (I != Preheader->begin()) { 01847 // Skip debug info intrinsics. 01848 do { 01849 --I; 01850 } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 01851 01852 if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 01853 Done = true; 01854 } else { 01855 Done = true; 01856 } 01857 01858 ToMove->moveBefore(InsertPt); 01859 if (Done) break; 01860 InsertPt = ToMove; 01861 } 01862 } 01863 01864 //===----------------------------------------------------------------------===// 01865 // IndVarSimplify driver. Manage several subpasses of IV simplification. 01866 //===----------------------------------------------------------------------===// 01867 01868 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 01869 if (skipOptnoneFunction(L)) 01870 return false; 01871 01872 // If LoopSimplify form is not available, stay out of trouble. Some notes: 01873 // - LSR currently only supports LoopSimplify-form loops. Indvars' 01874 // canonicalization can be a pessimization without LSR to "clean up" 01875 // afterwards. 01876 // - We depend on having a preheader; in particular, 01877 // Loop::getCanonicalInductionVariable only supports loops with preheaders, 01878 // and we're in trouble if we can't find the induction variable even when 01879 // we've manually inserted one. 01880 if (!L->isLoopSimplifyForm()) 01881 return false; 01882 01883 LI = &getAnalysis<LoopInfo>(); 01884 SE = &getAnalysis<ScalarEvolution>(); 01885 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 01886 DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 01887 DL = DLP ? &DLP->getDataLayout() : nullptr; 01888 TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); 01889 01890 DeadInsts.clear(); 01891 Changed = false; 01892 01893 // If there are any floating-point recurrences, attempt to 01894 // transform them to use integer recurrences. 01895 RewriteNonIntegerIVs(L); 01896 01897 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 01898 01899 // Create a rewriter object which we'll use to transform the code with. 01900 SCEVExpander Rewriter(*SE, "indvars"); 01901 #ifndef NDEBUG 01902 Rewriter.setDebugType(DEBUG_TYPE); 01903 #endif 01904 01905 // Eliminate redundant IV users. 01906 // 01907 // Simplification works best when run before other consumers of SCEV. We 01908 // attempt to avoid evaluating SCEVs for sign/zero extend operations until 01909 // other expressions involving loop IVs have been evaluated. This helps SCEV 01910 // set no-wrap flags before normalizing sign/zero extension. 01911 Rewriter.disableCanonicalMode(); 01912 SimplifyAndExtend(L, Rewriter, LPM); 01913 01914 // Check to see if this loop has a computable loop-invariant execution count. 01915 // If so, this means that we can compute the final value of any expressions 01916 // that are recurrent in the loop, and substitute the exit values from the 01917 // loop into any instructions outside of the loop that use the final values of 01918 // the current expressions. 01919 // 01920 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 01921 RewriteLoopExitValues(L, Rewriter); 01922 01923 // Eliminate redundant IV cycles. 01924 NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts); 01925 01926 // If we have a trip count expression, rewrite the loop's exit condition 01927 // using it. We can currently only handle loops with a single exit. 01928 if (canExpandBackedgeTakenCount(L, SE) && needsLFTR(L, DT)) { 01929 PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT, DL); 01930 if (IndVar) { 01931 // Check preconditions for proper SCEVExpander operation. SCEV does not 01932 // express SCEVExpander's dependencies, such as LoopSimplify. Instead any 01933 // pass that uses the SCEVExpander must do it. This does not work well for 01934 // loop passes because SCEVExpander makes assumptions about all loops, 01935 // while LoopPassManager only forces the current loop to be simplified. 01936 // 01937 // FIXME: SCEV expansion has no way to bail out, so the caller must 01938 // explicitly check any assumptions made by SCEV. Brittle. 01939 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount); 01940 if (!AR || AR->getLoop()->getLoopPreheader()) 01941 (void)LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 01942 Rewriter); 01943 } 01944 } 01945 // Clear the rewriter cache, because values that are in the rewriter's cache 01946 // can be deleted in the loop below, causing the AssertingVH in the cache to 01947 // trigger. 01948 Rewriter.clear(); 01949 01950 // Now that we're done iterating through lists, clean up any instructions 01951 // which are now dead. 01952 while (!DeadInsts.empty()) 01953 if (Instruction *Inst = 01954 dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 01955 RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 01956 01957 // The Rewriter may not be used from this point on. 01958 01959 // Loop-invariant instructions in the preheader that aren't used in the 01960 // loop may be sunk below the loop to reduce register pressure. 01961 SinkUnusedInvariants(L); 01962 01963 // Clean up dead instructions. 01964 Changed |= DeleteDeadPHIs(L->getHeader(), TLI); 01965 // Check a post-condition. 01966 assert(L->isLCSSAForm(*DT) && 01967 "Indvars did not leave the loop in lcssa form!"); 01968 01969 // Verify that LFTR, and any other change have not interfered with SCEV's 01970 // ability to compute trip count. 01971 #ifndef NDEBUG 01972 if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 01973 SE->forgetLoop(L); 01974 const SCEV *NewBECount = SE->getBackedgeTakenCount(L); 01975 if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) < 01976 SE->getTypeSizeInBits(NewBECount->getType())) 01977 NewBECount = SE->getTruncateOrNoop(NewBECount, 01978 BackedgeTakenCount->getType()); 01979 else 01980 BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount, 01981 NewBECount->getType()); 01982 assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV"); 01983 } 01984 #endif 01985 01986 return Changed; 01987 }