1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===// 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 transformation analyzes and transforms the induction variables (and 11 // computations derived from them) into simpler forms suitable for subsequent 12 // analysis and transformation. 13 // 14 // If the trip count of a loop is computable, this pass also makes the following 15 // changes: 16 // 1. The exit condition for the loop is canonicalized to compare the 17 // induction value against the exit value. This turns loops like: 18 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)' 19 // 2. Any use outside of the loop of an expression derived from the indvar 20 // is changed to compute the derived value outside of the loop, eliminating 21 // the dependence on the exit value of the induction variable. If the only 22 // purpose of the loop is to compute the exit value of some derived 23 // expression, this transformation will make the loop dead. 24 // 25 //===----------------------------------------------------------------------===// 26 27 #include "llvm/Transforms/Scalar.h" 28 #include "llvm/ADT/DenseMap.h" 29 #include "llvm/ADT/SmallVector.h" 30 #include "llvm/ADT/Statistic.h" 31 #include "llvm/Analysis/LoopInfo.h" 32 #include "llvm/Analysis/LoopPass.h" 33 #include "llvm/Analysis/ScalarEvolutionExpander.h" 34 #include "llvm/Analysis/TargetLibraryInfo.h" 35 #include "llvm/Analysis/TargetTransformInfo.h" 36 #include "llvm/IR/BasicBlock.h" 37 #include "llvm/IR/CFG.h" 38 #include "llvm/IR/Constants.h" 39 #include "llvm/IR/DataLayout.h" 40 #include "llvm/IR/Dominators.h" 41 #include "llvm/IR/Instructions.h" 42 #include "llvm/IR/IntrinsicInst.h" 43 #include "llvm/IR/LLVMContext.h" 44 #include "llvm/IR/Type.h" 45 #include "llvm/Support/CommandLine.h" 46 #include "llvm/Support/Debug.h" 47 #include "llvm/Support/raw_ostream.h" 48 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 49 #include "llvm/Transforms/Utils/Local.h" 50 #include "llvm/Transforms/Utils/SimplifyIndVar.h" 51 using namespace llvm; 52 53 #define DEBUG_TYPE "indvars" 54 55 STATISTIC(NumWidened , "Number of indvars widened"); 56 STATISTIC(NumReplaced , "Number of exit values replaced"); 57 STATISTIC(NumLFTR , "Number of loop exit tests replaced"); 58 STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated"); 59 STATISTIC(NumElimIV , "Number of congruent IVs eliminated"); 60 61 // Trip count verification can be enabled by default under NDEBUG if we 62 // implement a strong expression equivalence checker in SCEV. Until then, we 63 // use the verify-indvars flag, which may assert in some cases. 64 static cl::opt<bool> VerifyIndvars( 65 "verify-indvars", cl::Hidden, 66 cl::desc("Verify the ScalarEvolution result after running indvars")); 67 68 static cl::opt<bool> ReduceLiveIVs("liv-reduce", cl::Hidden, 69 cl::desc("Reduce live induction variables.")); 70 71 namespace { 72 class IndVarSimplify : public LoopPass { 73 LoopInfo *LI; 74 ScalarEvolution *SE; 75 DominatorTree *DT; 76 TargetLibraryInfo *TLI; 77 const TargetTransformInfo *TTI; 78 79 SmallVector<WeakVH, 16> DeadInsts; 80 bool Changed; 81 public: 82 83 static char ID; // Pass identification, replacement for typeid 84 IndVarSimplify() 85 : LoopPass(ID), LI(nullptr), SE(nullptr), DT(nullptr), Changed(false) { 86 initializeIndVarSimplifyPass(*PassRegistry::getPassRegistry()); 87 } 88 89 bool runOnLoop(Loop *L, LPPassManager &LPM) override; 90 91 void getAnalysisUsage(AnalysisUsage &AU) const override { 92 AU.addRequired<DominatorTreeWrapperPass>(); 93 AU.addRequired<LoopInfoWrapperPass>(); 94 AU.addRequired<ScalarEvolution>(); 95 AU.addRequiredID(LoopSimplifyID); 96 AU.addRequiredID(LCSSAID); 97 AU.addPreserved<ScalarEvolution>(); 98 AU.addPreservedID(LoopSimplifyID); 99 AU.addPreservedID(LCSSAID); 100 AU.setPreservesCFG(); 101 } 102 103 private: 104 void releaseMemory() override { 105 DeadInsts.clear(); 106 } 107 108 bool isValidRewrite(Value *FromVal, Value *ToVal); 109 110 void HandleFloatingPointIV(Loop *L, PHINode *PH); 111 void RewriteNonIntegerIVs(Loop *L); 112 113 void SimplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LPPassManager &LPM); 114 115 void RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter); 116 117 Value *LinearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount, 118 PHINode *IndVar, SCEVExpander &Rewriter); 119 120 void SinkUnusedInvariants(Loop *L); 121 }; 122 } 123 124 char IndVarSimplify::ID = 0; 125 INITIALIZE_PASS_BEGIN(IndVarSimplify, "indvars", 126 "Induction Variable Simplification", false, false) 127 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 128 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 129 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 130 INITIALIZE_PASS_DEPENDENCY(LoopSimplify) 131 INITIALIZE_PASS_DEPENDENCY(LCSSA) 132 INITIALIZE_PASS_END(IndVarSimplify, "indvars", 133 "Induction Variable Simplification", false, false) 134 135 Pass *llvm::createIndVarSimplifyPass() { 136 return new IndVarSimplify(); 137 } 138 139 /// isValidRewrite - Return true if the SCEV expansion generated by the 140 /// rewriter can replace the original value. SCEV guarantees that it 141 /// produces the same value, but the way it is produced may be illegal IR. 142 /// Ideally, this function will only be called for verification. 143 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) { 144 // If an SCEV expression subsumed multiple pointers, its expansion could 145 // reassociate the GEP changing the base pointer. This is illegal because the 146 // final address produced by a GEP chain must be inbounds relative to its 147 // underlying object. Otherwise basic alias analysis, among other things, 148 // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid 149 // producing an expression involving multiple pointers. Until then, we must 150 // bail out here. 151 // 152 // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject 153 // because it understands lcssa phis while SCEV does not. 154 Value *FromPtr = FromVal; 155 Value *ToPtr = ToVal; 156 if (GEPOperator *GEP = dyn_cast<GEPOperator>(FromVal)) { 157 FromPtr = GEP->getPointerOperand(); 158 } 159 if (GEPOperator *GEP = dyn_cast<GEPOperator>(ToVal)) { 160 ToPtr = GEP->getPointerOperand(); 161 } 162 if (FromPtr != FromVal || ToPtr != ToVal) { 163 // Quickly check the common case 164 if (FromPtr == ToPtr) 165 return true; 166 167 // SCEV may have rewritten an expression that produces the GEP's pointer 168 // operand. That's ok as long as the pointer operand has the same base 169 // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the 170 // base of a recurrence. This handles the case in which SCEV expansion 171 // converts a pointer type recurrence into a nonrecurrent pointer base 172 // indexed by an integer recurrence. 173 174 // If the GEP base pointer is a vector of pointers, abort. 175 if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy()) 176 return false; 177 178 const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr)); 179 const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr)); 180 if (FromBase == ToBase) 181 return true; 182 183 DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " 184 << *FromBase << " != " << *ToBase << "\n"); 185 186 return false; 187 } 188 return true; 189 } 190 191 /// Determine the insertion point for this user. By default, insert immediately 192 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the 193 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest 194 /// common dominator for the incoming blocks. 195 static Instruction *getInsertPointForUses(Instruction *User, Value *Def, 196 DominatorTree *DT) { 197 PHINode *PHI = dyn_cast<PHINode>(User); 198 if (!PHI) 199 return User; 200 201 Instruction *InsertPt = nullptr; 202 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) { 203 if (PHI->getIncomingValue(i) != Def) 204 continue; 205 206 BasicBlock *InsertBB = PHI->getIncomingBlock(i); 207 if (!InsertPt) { 208 InsertPt = InsertBB->getTerminator(); 209 continue; 210 } 211 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB); 212 InsertPt = InsertBB->getTerminator(); 213 } 214 assert(InsertPt && "Missing phi operand"); 215 assert((!isa<Instruction>(Def) || 216 DT->dominates(cast<Instruction>(Def), InsertPt)) && 217 "def does not dominate all uses"); 218 return InsertPt; 219 } 220 221 //===----------------------------------------------------------------------===// 222 // RewriteNonIntegerIVs and helpers. Prefer integer IVs. 223 //===----------------------------------------------------------------------===// 224 225 /// ConvertToSInt - Convert APF to an integer, if possible. 226 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) { 227 bool isExact = false; 228 // See if we can convert this to an int64_t 229 uint64_t UIntVal; 230 if (APF.convertToInteger(&UIntVal, 64, true, APFloat::rmTowardZero, 231 &isExact) != APFloat::opOK || !isExact) 232 return false; 233 IntVal = UIntVal; 234 return true; 235 } 236 237 /// HandleFloatingPointIV - If the loop has floating induction variable 238 /// then insert corresponding integer induction variable if possible. 239 /// For example, 240 /// for(double i = 0; i < 10000; ++i) 241 /// bar(i) 242 /// is converted into 243 /// for(int i = 0; i < 10000; ++i) 244 /// bar((double)i); 245 /// 246 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PN) { 247 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0)); 248 unsigned BackEdge = IncomingEdge^1; 249 250 // Check incoming value. 251 ConstantFP *InitValueVal = 252 dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge)); 253 254 int64_t InitValue; 255 if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue)) 256 return; 257 258 // Check IV increment. Reject this PN if increment operation is not 259 // an add or increment value can not be represented by an integer. 260 BinaryOperator *Incr = 261 dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge)); 262 if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return; 263 264 // If this is not an add of the PHI with a constantfp, or if the constant fp 265 // is not an integer, bail out. 266 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1)); 267 int64_t IncValue; 268 if (IncValueVal == nullptr || Incr->getOperand(0) != PN || 269 !ConvertToSInt(IncValueVal->getValueAPF(), IncValue)) 270 return; 271 272 // Check Incr uses. One user is PN and the other user is an exit condition 273 // used by the conditional terminator. 274 Value::user_iterator IncrUse = Incr->user_begin(); 275 Instruction *U1 = cast<Instruction>(*IncrUse++); 276 if (IncrUse == Incr->user_end()) return; 277 Instruction *U2 = cast<Instruction>(*IncrUse++); 278 if (IncrUse != Incr->user_end()) return; 279 280 // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't 281 // only used by a branch, we can't transform it. 282 FCmpInst *Compare = dyn_cast<FCmpInst>(U1); 283 if (!Compare) 284 Compare = dyn_cast<FCmpInst>(U2); 285 if (!Compare || !Compare->hasOneUse() || 286 !isa<BranchInst>(Compare->user_back())) 287 return; 288 289 BranchInst *TheBr = cast<BranchInst>(Compare->user_back()); 290 291 // We need to verify that the branch actually controls the iteration count 292 // of the loop. If not, the new IV can overflow and no one will notice. 293 // The branch block must be in the loop and one of the successors must be out 294 // of the loop. 295 assert(TheBr->isConditional() && "Can't use fcmp if not conditional"); 296 if (!L->contains(TheBr->getParent()) || 297 (L->contains(TheBr->getSuccessor(0)) && 298 L->contains(TheBr->getSuccessor(1)))) 299 return; 300 301 302 // If it isn't a comparison with an integer-as-fp (the exit value), we can't 303 // transform it. 304 ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1)); 305 int64_t ExitValue; 306 if (ExitValueVal == nullptr || 307 !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue)) 308 return; 309 310 // Find new predicate for integer comparison. 311 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE; 312 switch (Compare->getPredicate()) { 313 default: return; // Unknown comparison. 314 case CmpInst::FCMP_OEQ: 315 case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break; 316 case CmpInst::FCMP_ONE: 317 case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break; 318 case CmpInst::FCMP_OGT: 319 case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break; 320 case CmpInst::FCMP_OGE: 321 case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break; 322 case CmpInst::FCMP_OLT: 323 case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break; 324 case CmpInst::FCMP_OLE: 325 case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break; 326 } 327 328 // We convert the floating point induction variable to a signed i32 value if 329 // we can. This is only safe if the comparison will not overflow in a way 330 // that won't be trapped by the integer equivalent operations. Check for this 331 // now. 332 // TODO: We could use i64 if it is native and the range requires it. 333 334 // The start/stride/exit values must all fit in signed i32. 335 if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue)) 336 return; 337 338 // If not actually striding (add x, 0.0), avoid touching the code. 339 if (IncValue == 0) 340 return; 341 342 // Positive and negative strides have different safety conditions. 343 if (IncValue > 0) { 344 // If we have a positive stride, we require the init to be less than the 345 // exit value. 346 if (InitValue >= ExitValue) 347 return; 348 349 uint32_t Range = uint32_t(ExitValue-InitValue); 350 // Check for infinite loop, either: 351 // while (i <= Exit) or until (i > Exit) 352 if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) { 353 if (++Range == 0) return; // Range overflows. 354 } 355 356 unsigned Leftover = Range % uint32_t(IncValue); 357 358 // If this is an equality comparison, we require that the strided value 359 // exactly land on the exit value, otherwise the IV condition will wrap 360 // around and do things the fp IV wouldn't. 361 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 362 Leftover != 0) 363 return; 364 365 // If the stride would wrap around the i32 before exiting, we can't 366 // transform the IV. 367 if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue) 368 return; 369 370 } else { 371 // If we have a negative stride, we require the init to be greater than the 372 // exit value. 373 if (InitValue <= ExitValue) 374 return; 375 376 uint32_t Range = uint32_t(InitValue-ExitValue); 377 // Check for infinite loop, either: 378 // while (i >= Exit) or until (i < Exit) 379 if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) { 380 if (++Range == 0) return; // Range overflows. 381 } 382 383 unsigned Leftover = Range % uint32_t(-IncValue); 384 385 // If this is an equality comparison, we require that the strided value 386 // exactly land on the exit value, otherwise the IV condition will wrap 387 // around and do things the fp IV wouldn't. 388 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) && 389 Leftover != 0) 390 return; 391 392 // If the stride would wrap around the i32 before exiting, we can't 393 // transform the IV. 394 if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue) 395 return; 396 } 397 398 IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext()); 399 400 // Insert new integer induction variable. 401 PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN); 402 NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue), 403 PN->getIncomingBlock(IncomingEdge)); 404 405 Value *NewAdd = 406 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue), 407 Incr->getName()+".int", Incr); 408 NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge)); 409 410 ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd, 411 ConstantInt::get(Int32Ty, ExitValue), 412 Compare->getName()); 413 414 // In the following deletions, PN may become dead and may be deleted. 415 // Use a WeakVH to observe whether this happens. 416 WeakVH WeakPH = PN; 417 418 // Delete the old floating point exit comparison. The branch starts using the 419 // new comparison. 420 NewCompare->takeName(Compare); 421 Compare->replaceAllUsesWith(NewCompare); 422 RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI); 423 424 // Delete the old floating point increment. 425 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType())); 426 RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI); 427 428 // If the FP induction variable still has uses, this is because something else 429 // in the loop uses its value. In order to canonicalize the induction 430 // variable, we chose to eliminate the IV and rewrite it in terms of an 431 // int->fp cast. 432 // 433 // We give preference to sitofp over uitofp because it is faster on most 434 // platforms. 435 if (WeakPH) { 436 Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv", 437 PN->getParent()->getFirstInsertionPt()); 438 PN->replaceAllUsesWith(Conv); 439 RecursivelyDeleteTriviallyDeadInstructions(PN, TLI); 440 } 441 Changed = true; 442 } 443 444 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) { 445 // First step. Check to see if there are any floating-point recurrences. 446 // If there are, change them into integer recurrences, permitting analysis by 447 // the SCEV routines. 448 // 449 BasicBlock *Header = L->getHeader(); 450 451 SmallVector<WeakVH, 8> PHIs; 452 for (BasicBlock::iterator I = Header->begin(); 453 PHINode *PN = dyn_cast<PHINode>(I); ++I) 454 PHIs.push_back(PN); 455 456 for (unsigned i = 0, e = PHIs.size(); i != e; ++i) 457 if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i])) 458 HandleFloatingPointIV(L, PN); 459 460 // If the loop previously had floating-point IV, ScalarEvolution 461 // may not have been able to compute a trip count. Now that we've done some 462 // re-writing, the trip count may be computable. 463 if (Changed) 464 SE->forgetLoop(L); 465 } 466 467 //===----------------------------------------------------------------------===// 468 // RewriteLoopExitValues - Optimize IV users outside the loop. 469 // As a side effect, reduces the amount of IV processing within the loop. 470 //===----------------------------------------------------------------------===// 471 472 /// RewriteLoopExitValues - Check to see if this loop has a computable 473 /// loop-invariant execution count. If so, this means that we can compute the 474 /// final value of any expressions that are recurrent in the loop, and 475 /// substitute the exit values from the loop into any instructions outside of 476 /// the loop that use the final values of the current expressions. 477 /// 478 /// This is mostly redundant with the regular IndVarSimplify activities that 479 /// happen later, except that it's more powerful in some cases, because it's 480 /// able to brute-force evaluate arbitrary instructions as long as they have 481 /// constant operands at the beginning of the loop. 482 void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) { 483 // Verify the input to the pass in already in LCSSA form. 484 assert(L->isLCSSAForm(*DT)); 485 486 SmallVector<BasicBlock*, 8> ExitBlocks; 487 L->getUniqueExitBlocks(ExitBlocks); 488 489 // Find all values that are computed inside the loop, but used outside of it. 490 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan 491 // the exit blocks of the loop to find them. 492 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 493 BasicBlock *ExitBB = ExitBlocks[i]; 494 495 // If there are no PHI nodes in this exit block, then no values defined 496 // inside the loop are used on this path, skip it. 497 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin()); 498 if (!PN) continue; 499 500 unsigned NumPreds = PN->getNumIncomingValues(); 501 502 // We would like to be able to RAUW single-incoming value PHI nodes. We 503 // have to be certain this is safe even when this is an LCSSA PHI node. 504 // While the computed exit value is no longer varying in *this* loop, the 505 // exit block may be an exit block for an outer containing loop as well, 506 // the exit value may be varying in the outer loop, and thus it may still 507 // require an LCSSA PHI node. The safe case is when this is 508 // single-predecessor PHI node (LCSSA) and the exit block containing it is 509 // part of the enclosing loop, or this is the outer most loop of the nest. 510 // In either case the exit value could (at most) be varying in the same 511 // loop body as the phi node itself. Thus if it is in turn used outside of 512 // an enclosing loop it will only be via a separate LCSSA node. 513 bool LCSSASafePhiForRAUW = 514 NumPreds == 1 && 515 (!L->getParentLoop() || L->getParentLoop() == LI->getLoopFor(ExitBB)); 516 517 // Iterate over all of the PHI nodes. 518 BasicBlock::iterator BBI = ExitBB->begin(); 519 while ((PN = dyn_cast<PHINode>(BBI++))) { 520 if (PN->use_empty()) 521 continue; // dead use, don't replace it 522 523 // SCEV only supports integer expressions for now. 524 if (!PN->getType()->isIntegerTy() && !PN->getType()->isPointerTy()) 525 continue; 526 527 // It's necessary to tell ScalarEvolution about this explicitly so that 528 // it can walk the def-use list and forget all SCEVs, as it may not be 529 // watching the PHI itself. Once the new exit value is in place, there 530 // may not be a def-use connection between the loop and every instruction 531 // which got a SCEVAddRecExpr for that loop. 532 SE->forgetValue(PN); 533 534 // Iterate over all of the values in all the PHI nodes. 535 for (unsigned i = 0; i != NumPreds; ++i) { 536 // If the value being merged in is not integer or is not defined 537 // in the loop, skip it. 538 Value *InVal = PN->getIncomingValue(i); 539 if (!isa<Instruction>(InVal)) 540 continue; 541 542 // If this pred is for a subloop, not L itself, skip it. 543 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L) 544 continue; // The Block is in a subloop, skip it. 545 546 // Check that InVal is defined in the loop. 547 Instruction *Inst = cast<Instruction>(InVal); 548 if (!L->contains(Inst)) 549 continue; 550 551 // Okay, this instruction has a user outside of the current loop 552 // and varies predictably *inside* the loop. Evaluate the value it 553 // contains when the loop exits, if possible. 554 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop()); 555 if (!SE->isLoopInvariant(ExitValue, L) || 556 !isSafeToExpand(ExitValue, *SE)) 557 continue; 558 559 // Computing the value outside of the loop brings no benefit if : 560 // - it is definitely used inside the loop in a way which can not be 561 // optimized away. 562 // - no use outside of the loop can take advantage of hoisting the 563 // computation out of the loop 564 if (ExitValue->getSCEVType()>=scMulExpr) { 565 unsigned NumHardInternalUses = 0; 566 unsigned NumSoftExternalUses = 0; 567 unsigned NumUses = 0; 568 for (auto IB = Inst->user_begin(), IE = Inst->user_end(); 569 IB != IE && NumUses <= 6; ++IB) { 570 Instruction *UseInstr = cast<Instruction>(*IB); 571 unsigned Opc = UseInstr->getOpcode(); 572 NumUses++; 573 if (L->contains(UseInstr)) { 574 if (Opc == Instruction::Call || Opc == Instruction::Ret) 575 NumHardInternalUses++; 576 } else { 577 if (Opc == Instruction::PHI) { 578 // Do not count the Phi as a use. LCSSA may have inserted 579 // plenty of trivial ones. 580 NumUses--; 581 for (auto PB = UseInstr->user_begin(), 582 PE = UseInstr->user_end(); 583 PB != PE && NumUses <= 6; ++PB, ++NumUses) { 584 unsigned PhiOpc = cast<Instruction>(*PB)->getOpcode(); 585 if (PhiOpc != Instruction::Call && PhiOpc != Instruction::Ret) 586 NumSoftExternalUses++; 587 } 588 continue; 589 } 590 if (Opc != Instruction::Call && Opc != Instruction::Ret) 591 NumSoftExternalUses++; 592 } 593 } 594 if (NumUses <= 6 && NumHardInternalUses && !NumSoftExternalUses) 595 continue; 596 } 597 598 Value *ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), Inst); 599 600 DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal << '\n' 601 << " LoopVal = " << *Inst << "\n"); 602 603 if (!isValidRewrite(Inst, ExitVal)) { 604 DeadInsts.push_back(ExitVal); 605 continue; 606 } 607 Changed = true; 608 ++NumReplaced; 609 610 PN->setIncomingValue(i, ExitVal); 611 612 // If this instruction is dead now, delete it. Don't do it now to avoid 613 // invalidating iterators. 614 if (isInstructionTriviallyDead(Inst, TLI)) 615 DeadInsts.push_back(Inst); 616 617 // If we determined that this PHI is safe to replace even if an LCSSA 618 // PHI, do so. 619 if (LCSSASafePhiForRAUW) { 620 PN->replaceAllUsesWith(ExitVal); 621 PN->eraseFromParent(); 622 } 623 } 624 625 // If we were unable to completely replace the PHI node, clone the PHI 626 // and delete the original one. This lets IVUsers and any other maps 627 // purge the original user from their records. 628 if (!LCSSASafePhiForRAUW) { 629 PHINode *NewPN = cast<PHINode>(PN->clone()); 630 NewPN->takeName(PN); 631 NewPN->insertBefore(PN); 632 PN->replaceAllUsesWith(NewPN); 633 PN->eraseFromParent(); 634 } 635 } 636 } 637 638 // The insertion point instruction may have been deleted; clear it out 639 // so that the rewriter doesn't trip over it later. 640 Rewriter.clearInsertPoint(); 641 } 642 643 //===----------------------------------------------------------------------===// 644 // IV Widening - Extend the width of an IV to cover its widest uses. 645 //===----------------------------------------------------------------------===// 646 647 namespace { 648 // Collect information about induction variables that are used by sign/zero 649 // extend operations. This information is recorded by CollectExtend and 650 // provides the input to WidenIV. 651 struct WideIVInfo { 652 PHINode *NarrowIV; 653 Type *WidestNativeType; // Widest integer type created [sz]ext 654 bool IsSigned; // Was a sext user seen before a zext? 655 656 WideIVInfo() : NarrowIV(nullptr), WidestNativeType(nullptr), 657 IsSigned(false) {} 658 }; 659 } 660 661 /// visitCast - Update information about the induction variable that is 662 /// extended by this sign or zero extend operation. This is used to determine 663 /// the final width of the IV before actually widening it. 664 static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, 665 const TargetTransformInfo *TTI) { 666 bool IsSigned = Cast->getOpcode() == Instruction::SExt; 667 if (!IsSigned && Cast->getOpcode() != Instruction::ZExt) 668 return; 669 670 Type *Ty = Cast->getType(); 671 uint64_t Width = SE->getTypeSizeInBits(Ty); 672 if (!Cast->getModule()->getDataLayout().isLegalInteger(Width)) 673 return; 674 675 // Cast is either an sext or zext up to this point. 676 // We should not widen an indvar if arithmetics on the wider indvar are more 677 // expensive than those on the narrower indvar. We check only the cost of ADD 678 // because at least an ADD is required to increment the induction variable. We 679 // could compute more comprehensively the cost of all instructions on the 680 // induction variable when necessary. 681 if (TTI && 682 TTI->getArithmeticInstrCost(Instruction::Add, Ty) > 683 TTI->getArithmeticInstrCost(Instruction::Add, 684 Cast->getOperand(0)->getType())) { 685 return; 686 } 687 688 if (!WI.WidestNativeType) { 689 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 690 WI.IsSigned = IsSigned; 691 return; 692 } 693 694 // We extend the IV to satisfy the sign of its first user, arbitrarily. 695 if (WI.IsSigned != IsSigned) 696 return; 697 698 if (Width > SE->getTypeSizeInBits(WI.WidestNativeType)) 699 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty); 700 } 701 702 namespace { 703 704 /// NarrowIVDefUse - Record a link in the Narrow IV def-use chain along with the 705 /// WideIV that computes the same value as the Narrow IV def. This avoids 706 /// caching Use* pointers. 707 struct NarrowIVDefUse { 708 Instruction *NarrowDef; 709 Instruction *NarrowUse; 710 Instruction *WideDef; 711 712 NarrowIVDefUse(): NarrowDef(nullptr), NarrowUse(nullptr), WideDef(nullptr) {} 713 714 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD): 715 NarrowDef(ND), NarrowUse(NU), WideDef(WD) {} 716 }; 717 718 /// WidenIV - The goal of this transform is to remove sign and zero extends 719 /// without creating any new induction variables. To do this, it creates a new 720 /// phi of the wider type and redirects all users, either removing extends or 721 /// inserting truncs whenever we stop propagating the type. 722 /// 723 class WidenIV { 724 // Parameters 725 PHINode *OrigPhi; 726 Type *WideType; 727 bool IsSigned; 728 729 // Context 730 LoopInfo *LI; 731 Loop *L; 732 ScalarEvolution *SE; 733 DominatorTree *DT; 734 735 // Result 736 PHINode *WidePhi; 737 Instruction *WideInc; 738 const SCEV *WideIncExpr; 739 SmallVectorImpl<WeakVH> &DeadInsts; 740 741 SmallPtrSet<Instruction*,16> Widened; 742 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers; 743 744 public: 745 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, 746 ScalarEvolution *SEv, DominatorTree *DTree, 747 SmallVectorImpl<WeakVH> &DI) : 748 OrigPhi(WI.NarrowIV), 749 WideType(WI.WidestNativeType), 750 IsSigned(WI.IsSigned), 751 LI(LInfo), 752 L(LI->getLoopFor(OrigPhi->getParent())), 753 SE(SEv), 754 DT(DTree), 755 WidePhi(nullptr), 756 WideInc(nullptr), 757 WideIncExpr(nullptr), 758 DeadInsts(DI) { 759 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV"); 760 } 761 762 PHINode *CreateWideIV(SCEVExpander &Rewriter); 763 764 protected: 765 Value *getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 766 Instruction *Use); 767 768 Instruction *CloneIVUser(NarrowIVDefUse DU); 769 770 const SCEVAddRecExpr *GetWideRecurrence(Instruction *NarrowUse); 771 772 const SCEVAddRecExpr* GetExtendedOperandRecurrence(NarrowIVDefUse DU); 773 774 const SCEV *GetSCEVByOpCode(const SCEV *LHS, const SCEV *RHS, 775 unsigned OpCode) const; 776 777 Instruction *WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter); 778 779 bool WidenLoopCompare(NarrowIVDefUse DU); 780 781 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef); 782 }; 783 } // anonymous namespace 784 785 /// isLoopInvariant - Perform a quick domtree based check for loop invariance 786 /// assuming that V is used within the loop. LoopInfo::isLoopInvariant() seems 787 /// gratuitous for this purpose. 788 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) { 789 Instruction *Inst = dyn_cast<Instruction>(V); 790 if (!Inst) 791 return true; 792 793 return DT->properlyDominates(Inst->getParent(), L->getHeader()); 794 } 795 796 Value *WidenIV::getExtend(Value *NarrowOper, Type *WideType, bool IsSigned, 797 Instruction *Use) { 798 // Set the debug location and conservative insertion point. 799 IRBuilder<> Builder(Use); 800 // Hoist the insertion point into loop preheaders as far as possible. 801 for (const Loop *L = LI->getLoopFor(Use->getParent()); 802 L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT); 803 L = L->getParentLoop()) 804 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator()); 805 806 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) : 807 Builder.CreateZExt(NarrowOper, WideType); 808 } 809 810 /// CloneIVUser - Instantiate a wide operation to replace a narrow 811 /// operation. This only needs to handle operations that can evaluation to 812 /// SCEVAddRec. It can safely return 0 for any operation we decide not to clone. 813 Instruction *WidenIV::CloneIVUser(NarrowIVDefUse DU) { 814 unsigned Opcode = DU.NarrowUse->getOpcode(); 815 switch (Opcode) { 816 default: 817 return nullptr; 818 case Instruction::Add: 819 case Instruction::Mul: 820 case Instruction::UDiv: 821 case Instruction::Sub: 822 case Instruction::And: 823 case Instruction::Or: 824 case Instruction::Xor: 825 case Instruction::Shl: 826 case Instruction::LShr: 827 case Instruction::AShr: 828 DEBUG(dbgs() << "Cloning IVUser: " << *DU.NarrowUse << "\n"); 829 830 // Replace NarrowDef operands with WideDef. Otherwise, we don't know 831 // anything about the narrow operand yet so must insert a [sz]ext. It is 832 // probably loop invariant and will be folded or hoisted. If it actually 833 // comes from a widened IV, it should be removed during a future call to 834 // WidenIVUse. 835 Value *LHS = (DU.NarrowUse->getOperand(0) == DU.NarrowDef) ? DU.WideDef : 836 getExtend(DU.NarrowUse->getOperand(0), WideType, IsSigned, DU.NarrowUse); 837 Value *RHS = (DU.NarrowUse->getOperand(1) == DU.NarrowDef) ? DU.WideDef : 838 getExtend(DU.NarrowUse->getOperand(1), WideType, IsSigned, DU.NarrowUse); 839 840 BinaryOperator *NarrowBO = cast<BinaryOperator>(DU.NarrowUse); 841 BinaryOperator *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), 842 LHS, RHS, 843 NarrowBO->getName()); 844 IRBuilder<> Builder(DU.NarrowUse); 845 Builder.Insert(WideBO); 846 if (const OverflowingBinaryOperator *OBO = 847 dyn_cast<OverflowingBinaryOperator>(NarrowBO)) { 848 if (OBO->hasNoUnsignedWrap()) WideBO->setHasNoUnsignedWrap(); 849 if (OBO->hasNoSignedWrap()) WideBO->setHasNoSignedWrap(); 850 } 851 return WideBO; 852 } 853 } 854 855 const SCEV *WidenIV::GetSCEVByOpCode(const SCEV *LHS, const SCEV *RHS, 856 unsigned OpCode) const { 857 if (OpCode == Instruction::Add) 858 return SE->getAddExpr(LHS, RHS); 859 if (OpCode == Instruction::Sub) 860 return SE->getMinusSCEV(LHS, RHS); 861 if (OpCode == Instruction::Mul) 862 return SE->getMulExpr(LHS, RHS); 863 864 llvm_unreachable("Unsupported opcode."); 865 } 866 867 /// No-wrap operations can transfer sign extension of their result to their 868 /// operands. Generate the SCEV value for the widened operation without 869 /// actually modifying the IR yet. If the expression after extending the 870 /// operands is an AddRec for this loop, return it. 871 const SCEVAddRecExpr* WidenIV::GetExtendedOperandRecurrence(NarrowIVDefUse DU) { 872 873 // Handle the common case of add<nsw/nuw> 874 const unsigned OpCode = DU.NarrowUse->getOpcode(); 875 // Only Add/Sub/Mul instructions supported yet. 876 if (OpCode != Instruction::Add && OpCode != Instruction::Sub && 877 OpCode != Instruction::Mul) 878 return nullptr; 879 880 // One operand (NarrowDef) has already been extended to WideDef. Now determine 881 // if extending the other will lead to a recurrence. 882 const unsigned ExtendOperIdx = 883 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0; 884 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU"); 885 886 const SCEV *ExtendOperExpr = nullptr; 887 const OverflowingBinaryOperator *OBO = 888 cast<OverflowingBinaryOperator>(DU.NarrowUse); 889 if (IsSigned && OBO->hasNoSignedWrap()) 890 ExtendOperExpr = SE->getSignExtendExpr( 891 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 892 else if(!IsSigned && OBO->hasNoUnsignedWrap()) 893 ExtendOperExpr = SE->getZeroExtendExpr( 894 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType); 895 else 896 return nullptr; 897 898 // When creating this SCEV expr, don't apply the current operations NSW or NUW 899 // flags. This instruction may be guarded by control flow that the no-wrap 900 // behavior depends on. Non-control-equivalent instructions can be mapped to 901 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW 902 // semantics to those operations. 903 const SCEV *lhs = SE->getSCEV(DU.WideDef); 904 const SCEV *rhs = ExtendOperExpr; 905 906 // Let's swap operands to the initial order for the case of non-commutative 907 // operations, like SUB. See PR21014. 908 if (ExtendOperIdx == 0) 909 std::swap(lhs, rhs); 910 const SCEVAddRecExpr *AddRec = 911 dyn_cast<SCEVAddRecExpr>(GetSCEVByOpCode(lhs, rhs, OpCode)); 912 913 if (!AddRec || AddRec->getLoop() != L) 914 return nullptr; 915 return AddRec; 916 } 917 918 /// GetWideRecurrence - Is this instruction potentially interesting from 919 /// IVUsers' perspective after widening it's type? In other words, can the 920 /// extend be safely hoisted out of the loop with SCEV reducing the value to a 921 /// recurrence on the same loop. If so, return the sign or zero extended 922 /// recurrence. Otherwise return NULL. 923 const SCEVAddRecExpr *WidenIV::GetWideRecurrence(Instruction *NarrowUse) { 924 if (!SE->isSCEVable(NarrowUse->getType())) 925 return nullptr; 926 927 const SCEV *NarrowExpr = SE->getSCEV(NarrowUse); 928 if (SE->getTypeSizeInBits(NarrowExpr->getType()) 929 >= SE->getTypeSizeInBits(WideType)) { 930 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow 931 // index. So don't follow this use. 932 return nullptr; 933 } 934 935 const SCEV *WideExpr = IsSigned ? 936 SE->getSignExtendExpr(NarrowExpr, WideType) : 937 SE->getZeroExtendExpr(NarrowExpr, WideType); 938 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr); 939 if (!AddRec || AddRec->getLoop() != L) 940 return nullptr; 941 return AddRec; 942 } 943 944 /// This IV user cannot be widen. Replace this use of the original narrow IV 945 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV. 946 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT) { 947 DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef 948 << " for user " << *DU.NarrowUse << "\n"); 949 IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT)); 950 Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType()); 951 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc); 952 } 953 954 /// If the narrow use is a compare instruction, then widen the compare 955 // (and possibly the other operand). The extend operation is hoisted into the 956 // loop preheader as far as possible. 957 bool WidenIV::WidenLoopCompare(NarrowIVDefUse DU) { 958 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse); 959 if (!Cmp) 960 return false; 961 962 // Sign of IV user and compare must match. 963 if (IsSigned != CmpInst::isSigned(Cmp->getPredicate())) 964 return false; 965 966 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0); 967 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType()); 968 unsigned IVWidth = SE->getTypeSizeInBits(WideType); 969 assert (CastWidth <= IVWidth && "Unexpected width while widening compare."); 970 971 // Widen the compare instruction. 972 IRBuilder<> Builder(getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT)); 973 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef); 974 975 // Widen the other operand of the compare, if necessary. 976 if (CastWidth < IVWidth) { 977 Value *ExtOp = getExtend(Op, WideType, IsSigned, Cmp); 978 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp); 979 } 980 return true; 981 } 982 983 /// WidenIVUse - Determine whether an individual user of the narrow IV can be 984 /// widened. If so, return the wide clone of the user. 985 Instruction *WidenIV::WidenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) { 986 987 // Stop traversing the def-use chain at inner-loop phis or post-loop phis. 988 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) { 989 if (LI->getLoopFor(UsePhi->getParent()) != L) { 990 // For LCSSA phis, sink the truncate outside the loop. 991 // After SimplifyCFG most loop exit targets have a single predecessor. 992 // Otherwise fall back to a truncate within the loop. 993 if (UsePhi->getNumOperands() != 1) 994 truncateIVUse(DU, DT); 995 else { 996 PHINode *WidePhi = 997 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide", 998 UsePhi); 999 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0)); 1000 IRBuilder<> Builder(WidePhi->getParent()->getFirstInsertionPt()); 1001 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType()); 1002 UsePhi->replaceAllUsesWith(Trunc); 1003 DeadInsts.push_back(UsePhi); 1004 DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi 1005 << " to " << *WidePhi << "\n"); 1006 } 1007 return nullptr; 1008 } 1009 } 1010 // Our raison d'etre! Eliminate sign and zero extension. 1011 if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)) { 1012 Value *NewDef = DU.WideDef; 1013 if (DU.NarrowUse->getType() != WideType) { 1014 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType()); 1015 unsigned IVWidth = SE->getTypeSizeInBits(WideType); 1016 if (CastWidth < IVWidth) { 1017 // The cast isn't as wide as the IV, so insert a Trunc. 1018 IRBuilder<> Builder(DU.NarrowUse); 1019 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType()); 1020 } 1021 else { 1022 // A wider extend was hidden behind a narrower one. This may induce 1023 // another round of IV widening in which the intermediate IV becomes 1024 // dead. It should be very rare. 1025 DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi 1026 << " not wide enough to subsume " << *DU.NarrowUse << "\n"); 1027 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef); 1028 NewDef = DU.NarrowUse; 1029 } 1030 } 1031 if (NewDef != DU.NarrowUse) { 1032 DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse 1033 << " replaced by " << *DU.WideDef << "\n"); 1034 ++NumElimExt; 1035 DU.NarrowUse->replaceAllUsesWith(NewDef); 1036 DeadInsts.push_back(DU.NarrowUse); 1037 } 1038 // Now that the extend is gone, we want to expose it's uses for potential 1039 // further simplification. We don't need to directly inform SimplifyIVUsers 1040 // of the new users, because their parent IV will be processed later as a 1041 // new loop phi. If we preserved IVUsers analysis, we would also want to 1042 // push the uses of WideDef here. 1043 1044 // No further widening is needed. The deceased [sz]ext had done it for us. 1045 return nullptr; 1046 } 1047 1048 // Does this user itself evaluate to a recurrence after widening? 1049 const SCEVAddRecExpr *WideAddRec = GetWideRecurrence(DU.NarrowUse); 1050 if (!WideAddRec) 1051 WideAddRec = GetExtendedOperandRecurrence(DU); 1052 1053 if (!WideAddRec) { 1054 // If use is a loop condition, try to promote the condition instead of 1055 // truncating the IV first. 1056 if (WidenLoopCompare(DU)) 1057 return nullptr; 1058 1059 // This user does not evaluate to a recurence after widening, so don't 1060 // follow it. Instead insert a Trunc to kill off the original use, 1061 // eventually isolating the original narrow IV so it can be removed. 1062 truncateIVUse(DU, DT); 1063 return nullptr; 1064 } 1065 // Assume block terminators cannot evaluate to a recurrence. We can't to 1066 // insert a Trunc after a terminator if there happens to be a critical edge. 1067 assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() && 1068 "SCEV is not expected to evaluate a block terminator"); 1069 1070 // Reuse the IV increment that SCEVExpander created as long as it dominates 1071 // NarrowUse. 1072 Instruction *WideUse = nullptr; 1073 if (WideAddRec == WideIncExpr 1074 && Rewriter.hoistIVInc(WideInc, DU.NarrowUse)) 1075 WideUse = WideInc; 1076 else { 1077 WideUse = CloneIVUser(DU); 1078 if (!WideUse) 1079 return nullptr; 1080 } 1081 // Evaluation of WideAddRec ensured that the narrow expression could be 1082 // extended outside the loop without overflow. This suggests that the wide use 1083 // evaluates to the same expression as the extended narrow use, but doesn't 1084 // absolutely guarantee it. Hence the following failsafe check. In rare cases 1085 // where it fails, we simply throw away the newly created wide use. 1086 if (WideAddRec != SE->getSCEV(WideUse)) { 1087 DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse 1088 << ": " << *SE->getSCEV(WideUse) << " != " << *WideAddRec << "\n"); 1089 DeadInsts.push_back(WideUse); 1090 return nullptr; 1091 } 1092 1093 // Returning WideUse pushes it on the worklist. 1094 return WideUse; 1095 } 1096 1097 /// pushNarrowIVUsers - Add eligible users of NarrowDef to NarrowIVUsers. 1098 /// 1099 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) { 1100 for (User *U : NarrowDef->users()) { 1101 Instruction *NarrowUser = cast<Instruction>(U); 1102 1103 // Handle data flow merges and bizarre phi cycles. 1104 if (!Widened.insert(NarrowUser).second) 1105 continue; 1106 1107 NarrowIVUsers.push_back(NarrowIVDefUse(NarrowDef, NarrowUser, WideDef)); 1108 } 1109 } 1110 1111 /// CreateWideIV - Process a single induction variable. First use the 1112 /// SCEVExpander to create a wide induction variable that evaluates to the same 1113 /// recurrence as the original narrow IV. Then use a worklist to forward 1114 /// traverse the narrow IV's def-use chain. After WidenIVUse has processed all 1115 /// interesting IV users, the narrow IV will be isolated for removal by 1116 /// DeleteDeadPHIs. 1117 /// 1118 /// It would be simpler to delete uses as they are processed, but we must avoid 1119 /// invalidating SCEV expressions. 1120 /// 1121 PHINode *WidenIV::CreateWideIV(SCEVExpander &Rewriter) { 1122 // Is this phi an induction variable? 1123 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi)); 1124 if (!AddRec) 1125 return nullptr; 1126 1127 // Widen the induction variable expression. 1128 const SCEV *WideIVExpr = IsSigned ? 1129 SE->getSignExtendExpr(AddRec, WideType) : 1130 SE->getZeroExtendExpr(AddRec, WideType); 1131 1132 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType && 1133 "Expect the new IV expression to preserve its type"); 1134 1135 // Can the IV be extended outside the loop without overflow? 1136 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr); 1137 if (!AddRec || AddRec->getLoop() != L) 1138 return nullptr; 1139 1140 // An AddRec must have loop-invariant operands. Since this AddRec is 1141 // materialized by a loop header phi, the expression cannot have any post-loop 1142 // operands, so they must dominate the loop header. 1143 assert(SE->properlyDominates(AddRec->getStart(), L->getHeader()) && 1144 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) 1145 && "Loop header phi recurrence inputs do not dominate the loop"); 1146 1147 // The rewriter provides a value for the desired IV expression. This may 1148 // either find an existing phi or materialize a new one. Either way, we 1149 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part 1150 // of the phi-SCC dominates the loop entry. 1151 Instruction *InsertPt = L->getHeader()->begin(); 1152 WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt)); 1153 1154 // Remembering the WideIV increment generated by SCEVExpander allows 1155 // WidenIVUse to reuse it when widening the narrow IV's increment. We don't 1156 // employ a general reuse mechanism because the call above is the only call to 1157 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses. 1158 if (BasicBlock *LatchBlock = L->getLoopLatch()) { 1159 WideInc = 1160 cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock)); 1161 WideIncExpr = SE->getSCEV(WideInc); 1162 } 1163 1164 DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n"); 1165 ++NumWidened; 1166 1167 // Traverse the def-use chain using a worklist starting at the original IV. 1168 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" ); 1169 1170 Widened.insert(OrigPhi); 1171 pushNarrowIVUsers(OrigPhi, WidePhi); 1172 1173 while (!NarrowIVUsers.empty()) { 1174 NarrowIVDefUse DU = NarrowIVUsers.pop_back_val(); 1175 1176 // Process a def-use edge. This may replace the use, so don't hold a 1177 // use_iterator across it. 1178 Instruction *WideUse = WidenIVUse(DU, Rewriter); 1179 1180 // Follow all def-use edges from the previous narrow use. 1181 if (WideUse) 1182 pushNarrowIVUsers(DU.NarrowUse, WideUse); 1183 1184 // WidenIVUse may have removed the def-use edge. 1185 if (DU.NarrowDef->use_empty()) 1186 DeadInsts.push_back(DU.NarrowDef); 1187 } 1188 return WidePhi; 1189 } 1190 1191 //===----------------------------------------------------------------------===// 1192 // Live IV Reduction - Minimize IVs live across the loop. 1193 //===----------------------------------------------------------------------===// 1194 1195 1196 //===----------------------------------------------------------------------===// 1197 // Simplification of IV users based on SCEV evaluation. 1198 //===----------------------------------------------------------------------===// 1199 1200 namespace { 1201 class IndVarSimplifyVisitor : public IVVisitor { 1202 ScalarEvolution *SE; 1203 const TargetTransformInfo *TTI; 1204 PHINode *IVPhi; 1205 1206 public: 1207 WideIVInfo WI; 1208 1209 IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV, 1210 const TargetTransformInfo *TTI, 1211 const DominatorTree *DTree) 1212 : SE(SCEV), TTI(TTI), IVPhi(IV) { 1213 DT = DTree; 1214 WI.NarrowIV = IVPhi; 1215 if (ReduceLiveIVs) 1216 setSplitOverflowIntrinsics(); 1217 } 1218 1219 // Implement the interface used by simplifyUsersOfIV. 1220 void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); } 1221 }; 1222 } 1223 1224 /// SimplifyAndExtend - Iteratively perform simplification on a worklist of IV 1225 /// users. Each successive simplification may push more users which may 1226 /// themselves be candidates for simplification. 1227 /// 1228 /// Sign/Zero extend elimination is interleaved with IV simplification. 1229 /// 1230 void IndVarSimplify::SimplifyAndExtend(Loop *L, 1231 SCEVExpander &Rewriter, 1232 LPPassManager &LPM) { 1233 SmallVector<WideIVInfo, 8> WideIVs; 1234 1235 SmallVector<PHINode*, 8> LoopPhis; 1236 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 1237 LoopPhis.push_back(cast<PHINode>(I)); 1238 } 1239 // Each round of simplification iterates through the SimplifyIVUsers worklist 1240 // for all current phis, then determines whether any IVs can be 1241 // widened. Widening adds new phis to LoopPhis, inducing another round of 1242 // simplification on the wide IVs. 1243 while (!LoopPhis.empty()) { 1244 // Evaluate as many IV expressions as possible before widening any IVs. This 1245 // forces SCEV to set no-wrap flags before evaluating sign/zero 1246 // extension. The first time SCEV attempts to normalize sign/zero extension, 1247 // the result becomes final. So for the most predictable results, we delay 1248 // evaluation of sign/zero extend evaluation until needed, and avoid running 1249 // other SCEV based analysis prior to SimplifyAndExtend. 1250 do { 1251 PHINode *CurrIV = LoopPhis.pop_back_val(); 1252 1253 // Information about sign/zero extensions of CurrIV. 1254 IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT); 1255 1256 Changed |= simplifyUsersOfIV(CurrIV, SE, &LPM, DeadInsts, &Visitor); 1257 1258 if (Visitor.WI.WidestNativeType) { 1259 WideIVs.push_back(Visitor.WI); 1260 } 1261 } while(!LoopPhis.empty()); 1262 1263 for (; !WideIVs.empty(); WideIVs.pop_back()) { 1264 WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts); 1265 if (PHINode *WidePhi = Widener.CreateWideIV(Rewriter)) { 1266 Changed = true; 1267 LoopPhis.push_back(WidePhi); 1268 } 1269 } 1270 } 1271 } 1272 1273 //===----------------------------------------------------------------------===// 1274 // LinearFunctionTestReplace and its kin. Rewrite the loop exit condition. 1275 //===----------------------------------------------------------------------===// 1276 1277 /// canExpandBackedgeTakenCount - Return true if this loop's backedge taken 1278 /// count expression can be safely and cheaply expanded into an instruction 1279 /// sequence that can be used by LinearFunctionTestReplace. 1280 /// 1281 /// TODO: This fails for pointer-type loop counters with greater than one byte 1282 /// strides, consequently preventing LFTR from running. For the purpose of LFTR 1283 /// we could skip this check in the case that the LFTR loop counter (chosen by 1284 /// FindLoopCounter) is also pointer type. Instead, we could directly convert 1285 /// the loop test to an inequality test by checking the target data's alignment 1286 /// of element types (given that the initial pointer value originates from or is 1287 /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint). 1288 /// However, we don't yet have a strong motivation for converting loop tests 1289 /// into inequality tests. 1290 static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE, 1291 SCEVExpander &Rewriter) { 1292 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 1293 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) || 1294 BackedgeTakenCount->isZero()) 1295 return false; 1296 1297 if (!L->getExitingBlock()) 1298 return false; 1299 1300 // Can't rewrite non-branch yet. 1301 if (!isa<BranchInst>(L->getExitingBlock()->getTerminator())) 1302 return false; 1303 1304 if (Rewriter.isHighCostExpansion(BackedgeTakenCount, L)) 1305 return false; 1306 1307 return true; 1308 } 1309 1310 /// getLoopPhiForCounter - Return the loop header phi IFF IncV adds a loop 1311 /// invariant value to the phi. 1312 static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) { 1313 Instruction *IncI = dyn_cast<Instruction>(IncV); 1314 if (!IncI) 1315 return nullptr; 1316 1317 switch (IncI->getOpcode()) { 1318 case Instruction::Add: 1319 case Instruction::Sub: 1320 break; 1321 case Instruction::GetElementPtr: 1322 // An IV counter must preserve its type. 1323 if (IncI->getNumOperands() == 2) 1324 break; 1325 default: 1326 return nullptr; 1327 } 1328 1329 PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0)); 1330 if (Phi && Phi->getParent() == L->getHeader()) { 1331 if (isLoopInvariant(IncI->getOperand(1), L, DT)) 1332 return Phi; 1333 return nullptr; 1334 } 1335 if (IncI->getOpcode() == Instruction::GetElementPtr) 1336 return nullptr; 1337 1338 // Allow add/sub to be commuted. 1339 Phi = dyn_cast<PHINode>(IncI->getOperand(1)); 1340 if (Phi && Phi->getParent() == L->getHeader()) { 1341 if (isLoopInvariant(IncI->getOperand(0), L, DT)) 1342 return Phi; 1343 } 1344 return nullptr; 1345 } 1346 1347 /// Return the compare guarding the loop latch, or NULL for unrecognized tests. 1348 static ICmpInst *getLoopTest(Loop *L) { 1349 assert(L->getExitingBlock() && "expected loop exit"); 1350 1351 BasicBlock *LatchBlock = L->getLoopLatch(); 1352 // Don't bother with LFTR if the loop is not properly simplified. 1353 if (!LatchBlock) 1354 return nullptr; 1355 1356 BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1357 assert(BI && "expected exit branch"); 1358 1359 return dyn_cast<ICmpInst>(BI->getCondition()); 1360 } 1361 1362 /// needsLFTR - LinearFunctionTestReplace policy. Return true unless we can show 1363 /// that the current exit test is already sufficiently canonical. 1364 static bool needsLFTR(Loop *L, DominatorTree *DT) { 1365 // Do LFTR to simplify the exit condition to an ICMP. 1366 ICmpInst *Cond = getLoopTest(L); 1367 if (!Cond) 1368 return true; 1369 1370 // Do LFTR to simplify the exit ICMP to EQ/NE 1371 ICmpInst::Predicate Pred = Cond->getPredicate(); 1372 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ) 1373 return true; 1374 1375 // Look for a loop invariant RHS 1376 Value *LHS = Cond->getOperand(0); 1377 Value *RHS = Cond->getOperand(1); 1378 if (!isLoopInvariant(RHS, L, DT)) { 1379 if (!isLoopInvariant(LHS, L, DT)) 1380 return true; 1381 std::swap(LHS, RHS); 1382 } 1383 // Look for a simple IV counter LHS 1384 PHINode *Phi = dyn_cast<PHINode>(LHS); 1385 if (!Phi) 1386 Phi = getLoopPhiForCounter(LHS, L, DT); 1387 1388 if (!Phi) 1389 return true; 1390 1391 // Do LFTR if PHI node is defined in the loop, but is *not* a counter. 1392 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch()); 1393 if (Idx < 0) 1394 return true; 1395 1396 // Do LFTR if the exit condition's IV is *not* a simple counter. 1397 Value *IncV = Phi->getIncomingValue(Idx); 1398 return Phi != getLoopPhiForCounter(IncV, L, DT); 1399 } 1400 1401 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils 1402 /// down to checking that all operands are constant and listing instructions 1403 /// that may hide undef. 1404 static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited, 1405 unsigned Depth) { 1406 if (isa<Constant>(V)) 1407 return !isa<UndefValue>(V); 1408 1409 if (Depth >= 6) 1410 return false; 1411 1412 // Conservatively handle non-constant non-instructions. For example, Arguments 1413 // may be undef. 1414 Instruction *I = dyn_cast<Instruction>(V); 1415 if (!I) 1416 return false; 1417 1418 // Load and return values may be undef. 1419 if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I)) 1420 return false; 1421 1422 // Optimistically handle other instructions. 1423 for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI) { 1424 if (!Visited.insert(*OI).second) 1425 continue; 1426 if (!hasConcreteDefImpl(*OI, Visited, Depth+1)) 1427 return false; 1428 } 1429 return true; 1430 } 1431 1432 /// Return true if the given value is concrete. We must prove that undef can 1433 /// never reach it. 1434 /// 1435 /// TODO: If we decide that this is a good approach to checking for undef, we 1436 /// may factor it into a common location. 1437 static bool hasConcreteDef(Value *V) { 1438 SmallPtrSet<Value*, 8> Visited; 1439 Visited.insert(V); 1440 return hasConcreteDefImpl(V, Visited, 0); 1441 } 1442 1443 /// AlmostDeadIV - Return true if this IV has any uses other than the (soon to 1444 /// be rewritten) loop exit test. 1445 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) { 1446 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1447 Value *IncV = Phi->getIncomingValue(LatchIdx); 1448 1449 for (User *U : Phi->users()) 1450 if (U != Cond && U != IncV) return false; 1451 1452 for (User *U : IncV->users()) 1453 if (U != Cond && U != Phi) return false; 1454 return true; 1455 } 1456 1457 /// FindLoopCounter - Find an affine IV in canonical form. 1458 /// 1459 /// BECount may be an i8* pointer type. The pointer difference is already 1460 /// valid count without scaling the address stride, so it remains a pointer 1461 /// expression as far as SCEV is concerned. 1462 /// 1463 /// Currently only valid for LFTR. See the comments on hasConcreteDef below. 1464 /// 1465 /// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount 1466 /// 1467 /// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride. 1468 /// This is difficult in general for SCEV because of potential overflow. But we 1469 /// could at least handle constant BECounts. 1470 static PHINode *FindLoopCounter(Loop *L, const SCEV *BECount, 1471 ScalarEvolution *SE, DominatorTree *DT) { 1472 uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType()); 1473 1474 Value *Cond = 1475 cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition(); 1476 1477 // Loop over all of the PHI nodes, looking for a simple counter. 1478 PHINode *BestPhi = nullptr; 1479 const SCEV *BestInit = nullptr; 1480 BasicBlock *LatchBlock = L->getLoopLatch(); 1481 assert(LatchBlock && "needsLFTR should guarantee a loop latch"); 1482 1483 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) { 1484 PHINode *Phi = cast<PHINode>(I); 1485 if (!SE->isSCEVable(Phi->getType())) 1486 continue; 1487 1488 // Avoid comparing an integer IV against a pointer Limit. 1489 if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy()) 1490 continue; 1491 1492 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi)); 1493 if (!AR || AR->getLoop() != L || !AR->isAffine()) 1494 continue; 1495 1496 // AR may be a pointer type, while BECount is an integer type. 1497 // AR may be wider than BECount. With eq/ne tests overflow is immaterial. 1498 // AR may not be a narrower type, or we may never exit. 1499 uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType()); 1500 if (PhiWidth < BCWidth || 1501 !L->getHeader()->getModule()->getDataLayout().isLegalInteger(PhiWidth)) 1502 continue; 1503 1504 const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 1505 if (!Step || !Step->isOne()) 1506 continue; 1507 1508 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock); 1509 Value *IncV = Phi->getIncomingValue(LatchIdx); 1510 if (getLoopPhiForCounter(IncV, L, DT) != Phi) 1511 continue; 1512 1513 // Avoid reusing a potentially undef value to compute other values that may 1514 // have originally had a concrete definition. 1515 if (!hasConcreteDef(Phi)) { 1516 // We explicitly allow unknown phis as long as they are already used by 1517 // the loop test. In this case we assume that performing LFTR could not 1518 // increase the number of undef users. 1519 if (ICmpInst *Cond = getLoopTest(L)) { 1520 if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT) 1521 && Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) { 1522 continue; 1523 } 1524 } 1525 } 1526 const SCEV *Init = AR->getStart(); 1527 1528 if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) { 1529 // Don't force a live loop counter if another IV can be used. 1530 if (AlmostDeadIV(Phi, LatchBlock, Cond)) 1531 continue; 1532 1533 // Prefer to count-from-zero. This is a more "canonical" counter form. It 1534 // also prefers integer to pointer IVs. 1535 if (BestInit->isZero() != Init->isZero()) { 1536 if (BestInit->isZero()) 1537 continue; 1538 } 1539 // If two IVs both count from zero or both count from nonzero then the 1540 // narrower is likely a dead phi that has been widened. Use the wider phi 1541 // to allow the other to be eliminated. 1542 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType())) 1543 continue; 1544 } 1545 BestPhi = Phi; 1546 BestInit = Init; 1547 } 1548 return BestPhi; 1549 } 1550 1551 /// genLoopLimit - Help LinearFunctionTestReplace by generating a value that 1552 /// holds the RHS of the new loop test. 1553 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L, 1554 SCEVExpander &Rewriter, ScalarEvolution *SE) { 1555 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 1556 assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter"); 1557 const SCEV *IVInit = AR->getStart(); 1558 1559 // IVInit may be a pointer while IVCount is an integer when FindLoopCounter 1560 // finds a valid pointer IV. Sign extend BECount in order to materialize a 1561 // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing 1562 // the existing GEPs whenever possible. 1563 if (IndVar->getType()->isPointerTy() 1564 && !IVCount->getType()->isPointerTy()) { 1565 1566 // IVOffset will be the new GEP offset that is interpreted by GEP as a 1567 // signed value. IVCount on the other hand represents the loop trip count, 1568 // which is an unsigned value. FindLoopCounter only allows induction 1569 // variables that have a positive unit stride of one. This means we don't 1570 // have to handle the case of negative offsets (yet) and just need to zero 1571 // extend IVCount. 1572 Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType()); 1573 const SCEV *IVOffset = SE->getTruncateOrZeroExtend(IVCount, OfsTy); 1574 1575 // Expand the code for the iteration count. 1576 assert(SE->isLoopInvariant(IVOffset, L) && 1577 "Computed iteration count is not loop invariant!"); 1578 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1579 Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI); 1580 1581 Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader()); 1582 assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter"); 1583 // We could handle pointer IVs other than i8*, but we need to compensate for 1584 // gep index scaling. See canExpandBackedgeTakenCount comments. 1585 assert(SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()), 1586 cast<PointerType>(GEPBase->getType())->getElementType())->isOne() 1587 && "unit stride pointer IV must be i8*"); 1588 1589 IRBuilder<> Builder(L->getLoopPreheader()->getTerminator()); 1590 return Builder.CreateGEP(nullptr, GEPBase, GEPOffset, "lftr.limit"); 1591 } 1592 else { 1593 // In any other case, convert both IVInit and IVCount to integers before 1594 // comparing. This may result in SCEV expension of pointers, but in practice 1595 // SCEV will fold the pointer arithmetic away as such: 1596 // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc). 1597 // 1598 // Valid Cases: (1) both integers is most common; (2) both may be pointers 1599 // for simple memset-style loops. 1600 // 1601 // IVInit integer and IVCount pointer would only occur if a canonical IV 1602 // were generated on top of case #2, which is not expected. 1603 1604 const SCEV *IVLimit = nullptr; 1605 // For unit stride, IVCount = Start + BECount with 2's complement overflow. 1606 // For non-zero Start, compute IVCount here. 1607 if (AR->getStart()->isZero()) 1608 IVLimit = IVCount; 1609 else { 1610 assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride"); 1611 const SCEV *IVInit = AR->getStart(); 1612 1613 // For integer IVs, truncate the IV before computing IVInit + BECount. 1614 if (SE->getTypeSizeInBits(IVInit->getType()) 1615 > SE->getTypeSizeInBits(IVCount->getType())) 1616 IVInit = SE->getTruncateExpr(IVInit, IVCount->getType()); 1617 1618 IVLimit = SE->getAddExpr(IVInit, IVCount); 1619 } 1620 // Expand the code for the iteration count. 1621 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1622 IRBuilder<> Builder(BI); 1623 assert(SE->isLoopInvariant(IVLimit, L) && 1624 "Computed iteration count is not loop invariant!"); 1625 // Ensure that we generate the same type as IndVar, or a smaller integer 1626 // type. In the presence of null pointer values, we have an integer type 1627 // SCEV expression (IVInit) for a pointer type IV value (IndVar). 1628 Type *LimitTy = IVCount->getType()->isPointerTy() ? 1629 IndVar->getType() : IVCount->getType(); 1630 return Rewriter.expandCodeFor(IVLimit, LimitTy, BI); 1631 } 1632 } 1633 1634 /// LinearFunctionTestReplace - This method rewrites the exit condition of the 1635 /// loop to be a canonical != comparison against the incremented loop induction 1636 /// variable. This pass is able to rewrite the exit tests of any loop where the 1637 /// SCEV analysis can determine a loop-invariant trip count of the loop, which 1638 /// is actually a much broader range than just linear tests. 1639 Value *IndVarSimplify:: 1640 LinearFunctionTestReplace(Loop *L, 1641 const SCEV *BackedgeTakenCount, 1642 PHINode *IndVar, 1643 SCEVExpander &Rewriter) { 1644 assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition"); 1645 1646 // Initialize CmpIndVar and IVCount to their preincremented values. 1647 Value *CmpIndVar = IndVar; 1648 const SCEV *IVCount = BackedgeTakenCount; 1649 1650 // If the exiting block is the same as the backedge block, we prefer to 1651 // compare against the post-incremented value, otherwise we must compare 1652 // against the preincremented value. 1653 if (L->getExitingBlock() == L->getLoopLatch()) { 1654 // Add one to the "backedge-taken" count to get the trip count. 1655 // This addition may overflow, which is valid as long as the comparison is 1656 // truncated to BackedgeTakenCount->getType(). 1657 IVCount = SE->getAddExpr(BackedgeTakenCount, 1658 SE->getConstant(BackedgeTakenCount->getType(), 1)); 1659 // The BackedgeTaken expression contains the number of times that the 1660 // backedge branches to the loop header. This is one less than the 1661 // number of times the loop executes, so use the incremented indvar. 1662 CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock()); 1663 } 1664 1665 Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE); 1666 assert(ExitCnt->getType()->isPointerTy() == IndVar->getType()->isPointerTy() 1667 && "genLoopLimit missed a cast"); 1668 1669 // Insert a new icmp_ne or icmp_eq instruction before the branch. 1670 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator()); 1671 ICmpInst::Predicate P; 1672 if (L->contains(BI->getSuccessor(0))) 1673 P = ICmpInst::ICMP_NE; 1674 else 1675 P = ICmpInst::ICMP_EQ; 1676 1677 DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n" 1678 << " LHS:" << *CmpIndVar << '\n' 1679 << " op:\t" 1680 << (P == ICmpInst::ICMP_NE ? "!=" : "==") << "\n" 1681 << " RHS:\t" << *ExitCnt << "\n" 1682 << " IVCount:\t" << *IVCount << "\n"); 1683 1684 IRBuilder<> Builder(BI); 1685 1686 // LFTR can ignore IV overflow and truncate to the width of 1687 // BECount. This avoids materializing the add(zext(add)) expression. 1688 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType()); 1689 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType()); 1690 if (CmpIndVarSize > ExitCntSize) { 1691 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar)); 1692 const SCEV *ARStart = AR->getStart(); 1693 const SCEV *ARStep = AR->getStepRecurrence(*SE); 1694 // For constant IVCount, avoid truncation. 1695 if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) { 1696 const APInt &Start = cast<SCEVConstant>(ARStart)->getValue()->getValue(); 1697 APInt Count = cast<SCEVConstant>(IVCount)->getValue()->getValue(); 1698 // Note that the post-inc value of BackedgeTakenCount may have overflowed 1699 // above such that IVCount is now zero. 1700 if (IVCount != BackedgeTakenCount && Count == 0) { 1701 Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize); 1702 ++Count; 1703 } 1704 else 1705 Count = Count.zext(CmpIndVarSize); 1706 APInt NewLimit; 1707 if (cast<SCEVConstant>(ARStep)->getValue()->isNegative()) 1708 NewLimit = Start - Count; 1709 else 1710 NewLimit = Start + Count; 1711 ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit); 1712 1713 DEBUG(dbgs() << " Widen RHS:\t" << *ExitCnt << "\n"); 1714 } else { 1715 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(), 1716 "lftr.wideiv"); 1717 } 1718 } 1719 Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond"); 1720 Value *OrigCond = BI->getCondition(); 1721 // It's tempting to use replaceAllUsesWith here to fully replace the old 1722 // comparison, but that's not immediately safe, since users of the old 1723 // comparison may not be dominated by the new comparison. Instead, just 1724 // update the branch to use the new comparison; in the common case this 1725 // will make old comparison dead. 1726 BI->setCondition(Cond); 1727 DeadInsts.push_back(OrigCond); 1728 1729 ++NumLFTR; 1730 Changed = true; 1731 return Cond; 1732 } 1733 1734 //===----------------------------------------------------------------------===// 1735 // SinkUnusedInvariants. A late subpass to cleanup loop preheaders. 1736 //===----------------------------------------------------------------------===// 1737 1738 /// If there's a single exit block, sink any loop-invariant values that 1739 /// were defined in the preheader but not used inside the loop into the 1740 /// exit block to reduce register pressure in the loop. 1741 void IndVarSimplify::SinkUnusedInvariants(Loop *L) { 1742 BasicBlock *ExitBlock = L->getExitBlock(); 1743 if (!ExitBlock) return; 1744 1745 BasicBlock *Preheader = L->getLoopPreheader(); 1746 if (!Preheader) return; 1747 1748 Instruction *InsertPt = ExitBlock->getFirstInsertionPt(); 1749 BasicBlock::iterator I = Preheader->getTerminator(); 1750 while (I != Preheader->begin()) { 1751 --I; 1752 // New instructions were inserted at the end of the preheader. 1753 if (isa<PHINode>(I)) 1754 break; 1755 1756 // Don't move instructions which might have side effects, since the side 1757 // effects need to complete before instructions inside the loop. Also don't 1758 // move instructions which might read memory, since the loop may modify 1759 // memory. Note that it's okay if the instruction might have undefined 1760 // behavior: LoopSimplify guarantees that the preheader dominates the exit 1761 // block. 1762 if (I->mayHaveSideEffects() || I->mayReadFromMemory()) 1763 continue; 1764 1765 // Skip debug info intrinsics. 1766 if (isa<DbgInfoIntrinsic>(I)) 1767 continue; 1768 1769 // Skip landingpad instructions. 1770 if (isa<LandingPadInst>(I)) 1771 continue; 1772 1773 // Don't sink alloca: we never want to sink static alloca's out of the 1774 // entry block, and correctly sinking dynamic alloca's requires 1775 // checks for stacksave/stackrestore intrinsics. 1776 // FIXME: Refactor this check somehow? 1777 if (isa<AllocaInst>(I)) 1778 continue; 1779 1780 // Determine if there is a use in or before the loop (direct or 1781 // otherwise). 1782 bool UsedInLoop = false; 1783 for (Use &U : I->uses()) { 1784 Instruction *User = cast<Instruction>(U.getUser()); 1785 BasicBlock *UseBB = User->getParent(); 1786 if (PHINode *P = dyn_cast<PHINode>(User)) { 1787 unsigned i = 1788 PHINode::getIncomingValueNumForOperand(U.getOperandNo()); 1789 UseBB = P->getIncomingBlock(i); 1790 } 1791 if (UseBB == Preheader || L->contains(UseBB)) { 1792 UsedInLoop = true; 1793 break; 1794 } 1795 } 1796 1797 // If there is, the def must remain in the preheader. 1798 if (UsedInLoop) 1799 continue; 1800 1801 // Otherwise, sink it to the exit block. 1802 Instruction *ToMove = I; 1803 bool Done = false; 1804 1805 if (I != Preheader->begin()) { 1806 // Skip debug info intrinsics. 1807 do { 1808 --I; 1809 } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin()); 1810 1811 if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin()) 1812 Done = true; 1813 } else { 1814 Done = true; 1815 } 1816 1817 ToMove->moveBefore(InsertPt); 1818 if (Done) break; 1819 InsertPt = ToMove; 1820 } 1821 } 1822 1823 //===----------------------------------------------------------------------===// 1824 // IndVarSimplify driver. Manage several subpasses of IV simplification. 1825 //===----------------------------------------------------------------------===// 1826 1827 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 1828 if (skipOptnoneFunction(L)) 1829 return false; 1830 1831 // If LoopSimplify form is not available, stay out of trouble. Some notes: 1832 // - LSR currently only supports LoopSimplify-form loops. Indvars' 1833 // canonicalization can be a pessimization without LSR to "clean up" 1834 // afterwards. 1835 // - We depend on having a preheader; in particular, 1836 // Loop::getCanonicalInductionVariable only supports loops with preheaders, 1837 // and we're in trouble if we can't find the induction variable even when 1838 // we've manually inserted one. 1839 if (!L->isLoopSimplifyForm()) 1840 return false; 1841 1842 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1843 SE = &getAnalysis<ScalarEvolution>(); 1844 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1845 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>(); 1846 TLI = TLIP ? &TLIP->getTLI() : nullptr; 1847 auto *TTIP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>(); 1848 TTI = TTIP ? &TTIP->getTTI(*L->getHeader()->getParent()) : nullptr; 1849 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); 1850 1851 DeadInsts.clear(); 1852 Changed = false; 1853 1854 // If there are any floating-point recurrences, attempt to 1855 // transform them to use integer recurrences. 1856 RewriteNonIntegerIVs(L); 1857 1858 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L); 1859 1860 // Create a rewriter object which we'll use to transform the code with. 1861 SCEVExpander Rewriter(*SE, DL, "indvars"); 1862 #ifndef NDEBUG 1863 Rewriter.setDebugType(DEBUG_TYPE); 1864 #endif 1865 1866 // Eliminate redundant IV users. 1867 // 1868 // Simplification works best when run before other consumers of SCEV. We 1869 // attempt to avoid evaluating SCEVs for sign/zero extend operations until 1870 // other expressions involving loop IVs have been evaluated. This helps SCEV 1871 // set no-wrap flags before normalizing sign/zero extension. 1872 Rewriter.disableCanonicalMode(); 1873 SimplifyAndExtend(L, Rewriter, LPM); 1874 1875 // Check to see if this loop has a computable loop-invariant execution count. 1876 // If so, this means that we can compute the final value of any expressions 1877 // that are recurrent in the loop, and substitute the exit values from the 1878 // loop into any instructions outside of the loop that use the final values of 1879 // the current expressions. 1880 // 1881 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) 1882 RewriteLoopExitValues(L, Rewriter); 1883 1884 // Eliminate redundant IV cycles. 1885 NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts); 1886 1887 // If we have a trip count expression, rewrite the loop's exit condition 1888 // using it. We can currently only handle loops with a single exit. 1889 if (canExpandBackedgeTakenCount(L, SE, Rewriter) && needsLFTR(L, DT)) { 1890 PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT); 1891 if (IndVar) { 1892 // Check preconditions for proper SCEVExpander operation. SCEV does not 1893 // express SCEVExpander's dependencies, such as LoopSimplify. Instead any 1894 // pass that uses the SCEVExpander must do it. This does not work well for 1895 // loop passes because SCEVExpander makes assumptions about all loops, 1896 // while LoopPassManager only forces the current loop to be simplified. 1897 // 1898 // FIXME: SCEV expansion has no way to bail out, so the caller must 1899 // explicitly check any assumptions made by SCEV. Brittle. 1900 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount); 1901 if (!AR || AR->getLoop()->getLoopPreheader()) 1902 (void)LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar, 1903 Rewriter); 1904 } 1905 } 1906 // Clear the rewriter cache, because values that are in the rewriter's cache 1907 // can be deleted in the loop below, causing the AssertingVH in the cache to 1908 // trigger. 1909 Rewriter.clear(); 1910 1911 // Now that we're done iterating through lists, clean up any instructions 1912 // which are now dead. 1913 while (!DeadInsts.empty()) 1914 if (Instruction *Inst = 1915 dyn_cast_or_null<Instruction>(&*DeadInsts.pop_back_val())) 1916 RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI); 1917 1918 // The Rewriter may not be used from this point on. 1919 1920 // Loop-invariant instructions in the preheader that aren't used in the 1921 // loop may be sunk below the loop to reduce register pressure. 1922 SinkUnusedInvariants(L); 1923 1924 // Clean up dead instructions. 1925 Changed |= DeleteDeadPHIs(L->getHeader(), TLI); 1926 // Check a post-condition. 1927 assert(L->isLCSSAForm(*DT) && 1928 "Indvars did not leave the loop in lcssa form!"); 1929 1930 // Verify that LFTR, and any other change have not interfered with SCEV's 1931 // ability to compute trip count. 1932 #ifndef NDEBUG 1933 if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) { 1934 SE->forgetLoop(L); 1935 const SCEV *NewBECount = SE->getBackedgeTakenCount(L); 1936 if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) < 1937 SE->getTypeSizeInBits(NewBECount->getType())) 1938 NewBECount = SE->getTruncateOrNoop(NewBECount, 1939 BackedgeTakenCount->getType()); 1940 else 1941 BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount, 1942 NewBECount->getType()); 1943 assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV"); 1944 } 1945 #endif 1946 1947 return Changed; 1948 } 1949