1 //===- IndVarSimplify.cpp - Induction Variable Elimination ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 // If the trip count of a loop is computable, this pass also makes the following
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.
25 //===----------------------------------------------------------------------===//
27 #include "llvm/Transforms/Scalar/IndVarSimplify.h"
28 #include "llvm/ADT/APFloat.h"
29 #include "llvm/ADT/APInt.h"
30 #include "llvm/ADT/ArrayRef.h"
31 #include "llvm/ADT/DenseMap.h"
32 #include "llvm/ADT/None.h"
33 #include "llvm/ADT/Optional.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/ADT/SmallPtrSet.h"
36 #include "llvm/ADT/SmallVector.h"
37 #include "llvm/ADT/Statistic.h"
38 #include "llvm/ADT/iterator_range.h"
39 #include "llvm/Analysis/LoopInfo.h"
40 #include "llvm/Analysis/LoopPass.h"
41 #include "llvm/Analysis/ScalarEvolution.h"
42 #include "llvm/Analysis/ScalarEvolutionExpander.h"
43 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
44 #include "llvm/Analysis/TargetLibraryInfo.h"
45 #include "llvm/Analysis/TargetTransformInfo.h"
46 #include "llvm/Transforms/Utils/Local.h"
47 #include "llvm/IR/BasicBlock.h"
48 #include "llvm/IR/Constant.h"
49 #include "llvm/IR/ConstantRange.h"
50 #include "llvm/IR/Constants.h"
51 #include "llvm/IR/DataLayout.h"
52 #include "llvm/IR/DerivedTypes.h"
53 #include "llvm/IR/Dominators.h"
54 #include "llvm/IR/Function.h"
55 #include "llvm/IR/IRBuilder.h"
56 #include "llvm/IR/InstrTypes.h"
57 #include "llvm/IR/Instruction.h"
58 #include "llvm/IR/Instructions.h"
59 #include "llvm/IR/IntrinsicInst.h"
60 #include "llvm/IR/Intrinsics.h"
61 #include "llvm/IR/Module.h"
62 #include "llvm/IR/Operator.h"
63 #include "llvm/IR/PassManager.h"
64 #include "llvm/IR/PatternMatch.h"
65 #include "llvm/IR/Type.h"
66 #include "llvm/IR/Use.h"
67 #include "llvm/IR/User.h"
68 #include "llvm/IR/Value.h"
69 #include "llvm/IR/ValueHandle.h"
70 #include "llvm/Pass.h"
71 #include "llvm/Support/Casting.h"
72 #include "llvm/Support/CommandLine.h"
73 #include "llvm/Support/Compiler.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/ErrorHandling.h"
76 #include "llvm/Support/MathExtras.h"
77 #include "llvm/Support/raw_ostream.h"
78 #include "llvm/Transforms/Scalar.h"
79 #include "llvm/Transforms/Scalar/LoopPassManager.h"
80 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
81 #include "llvm/Transforms/Utils/LoopUtils.h"
82 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
89 #define DEBUG_TYPE "indvars"
91 STATISTIC(NumWidened , "Number of indvars widened");
92 STATISTIC(NumReplaced , "Number of exit values replaced");
93 STATISTIC(NumLFTR , "Number of loop exit tests replaced");
94 STATISTIC(NumElimExt , "Number of IV sign/zero extends eliminated");
95 STATISTIC(NumElimIV , "Number of congruent IVs eliminated");
97 // Trip count verification can be enabled by default under NDEBUG if we
98 // implement a strong expression equivalence checker in SCEV. Until then, we
99 // use the verify-indvars flag, which may assert in some cases.
100 static cl::opt<bool> VerifyIndvars(
101 "verify-indvars", cl::Hidden,
102 cl::desc("Verify the ScalarEvolution result after running indvars"));
104 enum ReplaceExitVal { NeverRepl, OnlyCheapRepl, AlwaysRepl };
106 static cl::opt<ReplaceExitVal> ReplaceExitValue(
107 "replexitval", cl::Hidden, cl::init(OnlyCheapRepl),
108 cl::desc("Choose the strategy to replace exit value in IndVarSimplify"),
109 cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"),
110 clEnumValN(OnlyCheapRepl, "cheap",
111 "only replace exit value when the cost is cheap"),
112 clEnumValN(AlwaysRepl, "always",
113 "always replace exit value whenever possible")));
115 static cl::opt<bool> UsePostIncrementRanges(
116 "indvars-post-increment-ranges", cl::Hidden,
117 cl::desc("Use post increment control-dependent ranges in IndVarSimplify"),
121 DisableLFTR("disable-lftr", cl::Hidden, cl::init(false),
122 cl::desc("Disable Linear Function Test Replace optimization"));
128 class IndVarSimplify {
132 const DataLayout &DL;
133 TargetLibraryInfo *TLI;
134 const TargetTransformInfo *TTI;
136 SmallVector<WeakTrackingVH, 16> DeadInsts;
137 bool Changed = false;
139 bool isValidRewrite(Value *FromVal, Value *ToVal);
141 void handleFloatingPointIV(Loop *L, PHINode *PH);
142 void rewriteNonIntegerIVs(Loop *L);
144 void simplifyAndExtend(Loop *L, SCEVExpander &Rewriter, LoopInfo *LI);
146 bool canLoopBeDeleted(Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet);
147 void rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter);
148 void rewriteFirstIterationLoopExitValues(Loop *L);
150 Value *linearFunctionTestReplace(Loop *L, const SCEV *BackedgeTakenCount,
151 PHINode *IndVar, SCEVExpander &Rewriter);
153 void sinkUnusedInvariants(Loop *L);
155 Value *expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S, Loop *L,
156 Instruction *InsertPt, Type *Ty);
159 IndVarSimplify(LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
160 const DataLayout &DL, TargetLibraryInfo *TLI,
161 TargetTransformInfo *TTI)
162 : LI(LI), SE(SE), DT(DT), DL(DL), TLI(TLI), TTI(TTI) {}
167 } // end anonymous namespace
169 /// Return true if the SCEV expansion generated by the rewriter can replace the
170 /// original value. SCEV guarantees that it produces the same value, but the way
171 /// it is produced may be illegal IR. Ideally, this function will only be
172 /// called for verification.
173 bool IndVarSimplify::isValidRewrite(Value *FromVal, Value *ToVal) {
174 // If an SCEV expression subsumed multiple pointers, its expansion could
175 // reassociate the GEP changing the base pointer. This is illegal because the
176 // final address produced by a GEP chain must be inbounds relative to its
177 // underlying object. Otherwise basic alias analysis, among other things,
178 // could fail in a dangerous way. Ultimately, SCEV will be improved to avoid
179 // producing an expression involving multiple pointers. Until then, we must
182 // Retrieve the pointer operand of the GEP. Don't use GetUnderlyingObject
183 // because it understands lcssa phis while SCEV does not.
184 Value *FromPtr = FromVal;
185 Value *ToPtr = ToVal;
186 if (auto *GEP = dyn_cast<GEPOperator>(FromVal)) {
187 FromPtr = GEP->getPointerOperand();
189 if (auto *GEP = dyn_cast<GEPOperator>(ToVal)) {
190 ToPtr = GEP->getPointerOperand();
192 if (FromPtr != FromVal || ToPtr != ToVal) {
193 // Quickly check the common case
194 if (FromPtr == ToPtr)
197 // SCEV may have rewritten an expression that produces the GEP's pointer
198 // operand. That's ok as long as the pointer operand has the same base
199 // pointer. Unlike GetUnderlyingObject(), getPointerBase() will find the
200 // base of a recurrence. This handles the case in which SCEV expansion
201 // converts a pointer type recurrence into a nonrecurrent pointer base
202 // indexed by an integer recurrence.
204 // If the GEP base pointer is a vector of pointers, abort.
205 if (!FromPtr->getType()->isPointerTy() || !ToPtr->getType()->isPointerTy())
208 const SCEV *FromBase = SE->getPointerBase(SE->getSCEV(FromPtr));
209 const SCEV *ToBase = SE->getPointerBase(SE->getSCEV(ToPtr));
210 if (FromBase == ToBase)
213 LLVM_DEBUG(dbgs() << "INDVARS: GEP rewrite bail out " << *FromBase
214 << " != " << *ToBase << "\n");
221 /// Determine the insertion point for this user. By default, insert immediately
222 /// before the user. SCEVExpander or LICM will hoist loop invariants out of the
223 /// loop. For PHI nodes, there may be multiple uses, so compute the nearest
224 /// common dominator for the incoming blocks.
225 static Instruction *getInsertPointForUses(Instruction *User, Value *Def,
226 DominatorTree *DT, LoopInfo *LI) {
227 PHINode *PHI = dyn_cast<PHINode>(User);
231 Instruction *InsertPt = nullptr;
232 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) {
233 if (PHI->getIncomingValue(i) != Def)
236 BasicBlock *InsertBB = PHI->getIncomingBlock(i);
238 InsertPt = InsertBB->getTerminator();
241 InsertBB = DT->findNearestCommonDominator(InsertPt->getParent(), InsertBB);
242 InsertPt = InsertBB->getTerminator();
244 assert(InsertPt && "Missing phi operand");
246 auto *DefI = dyn_cast<Instruction>(Def);
250 assert(DT->dominates(DefI, InsertPt) && "def does not dominate all uses");
252 auto *L = LI->getLoopFor(DefI->getParent());
253 assert(!L || L->contains(LI->getLoopFor(InsertPt->getParent())));
255 for (auto *DTN = (*DT)[InsertPt->getParent()]; DTN; DTN = DTN->getIDom())
256 if (LI->getLoopFor(DTN->getBlock()) == L)
257 return DTN->getBlock()->getTerminator();
259 llvm_unreachable("DefI dominates InsertPt!");
262 //===----------------------------------------------------------------------===//
263 // rewriteNonIntegerIVs and helpers. Prefer integer IVs.
264 //===----------------------------------------------------------------------===//
266 /// Convert APF to an integer, if possible.
267 static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal) {
268 bool isExact = false;
269 // See if we can convert this to an int64_t
271 if (APF.convertToInteger(makeMutableArrayRef(UIntVal), 64, true,
272 APFloat::rmTowardZero, &isExact) != APFloat::opOK ||
279 /// If the loop has floating induction variable then insert corresponding
280 /// integer induction variable if possible.
282 /// for(double i = 0; i < 10000; ++i)
284 /// is converted into
285 /// for(int i = 0; i < 10000; ++i)
287 void IndVarSimplify::handleFloatingPointIV(Loop *L, PHINode *PN) {
288 unsigned IncomingEdge = L->contains(PN->getIncomingBlock(0));
289 unsigned BackEdge = IncomingEdge^1;
291 // Check incoming value.
292 auto *InitValueVal = dyn_cast<ConstantFP>(PN->getIncomingValue(IncomingEdge));
295 if (!InitValueVal || !ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
298 // Check IV increment. Reject this PN if increment operation is not
299 // an add or increment value can not be represented by an integer.
300 auto *Incr = dyn_cast<BinaryOperator>(PN->getIncomingValue(BackEdge));
301 if (Incr == nullptr || Incr->getOpcode() != Instruction::FAdd) return;
303 // If this is not an add of the PHI with a constantfp, or if the constant fp
304 // is not an integer, bail out.
305 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
307 if (IncValueVal == nullptr || Incr->getOperand(0) != PN ||
308 !ConvertToSInt(IncValueVal->getValueAPF(), IncValue))
311 // Check Incr uses. One user is PN and the other user is an exit condition
312 // used by the conditional terminator.
313 Value::user_iterator IncrUse = Incr->user_begin();
314 Instruction *U1 = cast<Instruction>(*IncrUse++);
315 if (IncrUse == Incr->user_end()) return;
316 Instruction *U2 = cast<Instruction>(*IncrUse++);
317 if (IncrUse != Incr->user_end()) return;
319 // Find exit condition, which is an fcmp. If it doesn't exist, or if it isn't
320 // only used by a branch, we can't transform it.
321 FCmpInst *Compare = dyn_cast<FCmpInst>(U1);
323 Compare = dyn_cast<FCmpInst>(U2);
324 if (!Compare || !Compare->hasOneUse() ||
325 !isa<BranchInst>(Compare->user_back()))
328 BranchInst *TheBr = cast<BranchInst>(Compare->user_back());
330 // We need to verify that the branch actually controls the iteration count
331 // of the loop. If not, the new IV can overflow and no one will notice.
332 // The branch block must be in the loop and one of the successors must be out
334 assert(TheBr->isConditional() && "Can't use fcmp if not conditional");
335 if (!L->contains(TheBr->getParent()) ||
336 (L->contains(TheBr->getSuccessor(0)) &&
337 L->contains(TheBr->getSuccessor(1))))
340 // If it isn't a comparison with an integer-as-fp (the exit value), we can't
342 ConstantFP *ExitValueVal = dyn_cast<ConstantFP>(Compare->getOperand(1));
344 if (ExitValueVal == nullptr ||
345 !ConvertToSInt(ExitValueVal->getValueAPF(), ExitValue))
348 // Find new predicate for integer comparison.
349 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
350 switch (Compare->getPredicate()) {
351 default: return; // Unknown comparison.
352 case CmpInst::FCMP_OEQ:
353 case CmpInst::FCMP_UEQ: NewPred = CmpInst::ICMP_EQ; break;
354 case CmpInst::FCMP_ONE:
355 case CmpInst::FCMP_UNE: NewPred = CmpInst::ICMP_NE; break;
356 case CmpInst::FCMP_OGT:
357 case CmpInst::FCMP_UGT: NewPred = CmpInst::ICMP_SGT; break;
358 case CmpInst::FCMP_OGE:
359 case CmpInst::FCMP_UGE: NewPred = CmpInst::ICMP_SGE; break;
360 case CmpInst::FCMP_OLT:
361 case CmpInst::FCMP_ULT: NewPred = CmpInst::ICMP_SLT; break;
362 case CmpInst::FCMP_OLE:
363 case CmpInst::FCMP_ULE: NewPred = CmpInst::ICMP_SLE; break;
366 // We convert the floating point induction variable to a signed i32 value if
367 // we can. This is only safe if the comparison will not overflow in a way
368 // that won't be trapped by the integer equivalent operations. Check for this
370 // TODO: We could use i64 if it is native and the range requires it.
372 // The start/stride/exit values must all fit in signed i32.
373 if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
376 // If not actually striding (add x, 0.0), avoid touching the code.
380 // Positive and negative strides have different safety conditions.
382 // If we have a positive stride, we require the init to be less than the
384 if (InitValue >= ExitValue)
387 uint32_t Range = uint32_t(ExitValue-InitValue);
388 // Check for infinite loop, either:
389 // while (i <= Exit) or until (i > Exit)
390 if (NewPred == CmpInst::ICMP_SLE || NewPred == CmpInst::ICMP_SGT) {
391 if (++Range == 0) return; // Range overflows.
394 unsigned Leftover = Range % uint32_t(IncValue);
396 // If this is an equality comparison, we require that the strided value
397 // exactly land on the exit value, otherwise the IV condition will wrap
398 // around and do things the fp IV wouldn't.
399 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
403 // If the stride would wrap around the i32 before exiting, we can't
405 if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
408 // If we have a negative stride, we require the init to be greater than the
410 if (InitValue <= ExitValue)
413 uint32_t Range = uint32_t(InitValue-ExitValue);
414 // Check for infinite loop, either:
415 // while (i >= Exit) or until (i < Exit)
416 if (NewPred == CmpInst::ICMP_SGE || NewPred == CmpInst::ICMP_SLT) {
417 if (++Range == 0) return; // Range overflows.
420 unsigned Leftover = Range % uint32_t(-IncValue);
422 // If this is an equality comparison, we require that the strided value
423 // exactly land on the exit value, otherwise the IV condition will wrap
424 // around and do things the fp IV wouldn't.
425 if ((NewPred == CmpInst::ICMP_EQ || NewPred == CmpInst::ICMP_NE) &&
429 // If the stride would wrap around the i32 before exiting, we can't
431 if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
435 IntegerType *Int32Ty = Type::getInt32Ty(PN->getContext());
437 // Insert new integer induction variable.
438 PHINode *NewPHI = PHINode::Create(Int32Ty, 2, PN->getName()+".int", PN);
439 NewPHI->addIncoming(ConstantInt::get(Int32Ty, InitValue),
440 PN->getIncomingBlock(IncomingEdge));
443 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(Int32Ty, IncValue),
444 Incr->getName()+".int", Incr);
445 NewPHI->addIncoming(NewAdd, PN->getIncomingBlock(BackEdge));
447 ICmpInst *NewCompare = new ICmpInst(TheBr, NewPred, NewAdd,
448 ConstantInt::get(Int32Ty, ExitValue),
451 // In the following deletions, PN may become dead and may be deleted.
452 // Use a WeakTrackingVH to observe whether this happens.
453 WeakTrackingVH WeakPH = PN;
455 // Delete the old floating point exit comparison. The branch starts using the
457 NewCompare->takeName(Compare);
458 Compare->replaceAllUsesWith(NewCompare);
459 RecursivelyDeleteTriviallyDeadInstructions(Compare, TLI);
461 // Delete the old floating point increment.
462 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
463 RecursivelyDeleteTriviallyDeadInstructions(Incr, TLI);
465 // If the FP induction variable still has uses, this is because something else
466 // in the loop uses its value. In order to canonicalize the induction
467 // variable, we chose to eliminate the IV and rewrite it in terms of an
470 // We give preference to sitofp over uitofp because it is faster on most
473 Value *Conv = new SIToFPInst(NewPHI, PN->getType(), "indvar.conv",
474 &*PN->getParent()->getFirstInsertionPt());
475 PN->replaceAllUsesWith(Conv);
476 RecursivelyDeleteTriviallyDeadInstructions(PN, TLI);
481 void IndVarSimplify::rewriteNonIntegerIVs(Loop *L) {
482 // First step. Check to see if there are any floating-point recurrences.
483 // If there are, change them into integer recurrences, permitting analysis by
484 // the SCEV routines.
485 BasicBlock *Header = L->getHeader();
487 SmallVector<WeakTrackingVH, 8> PHIs;
488 for (PHINode &PN : Header->phis())
491 for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
492 if (PHINode *PN = dyn_cast_or_null<PHINode>(&*PHIs[i]))
493 handleFloatingPointIV(L, PN);
495 // If the loop previously had floating-point IV, ScalarEvolution
496 // may not have been able to compute a trip count. Now that we've done some
497 // re-writing, the trip count may be computable.
504 // Collect information about PHI nodes which can be transformed in
505 // rewriteLoopExitValues.
509 // Ith incoming value.
512 // Exit value after expansion.
515 // High Cost when expansion.
518 RewritePhi(PHINode *P, unsigned I, Value *V, bool H)
519 : PN(P), Ith(I), Val(V), HighCost(H) {}
522 } // end anonymous namespace
524 Value *IndVarSimplify::expandSCEVIfNeeded(SCEVExpander &Rewriter, const SCEV *S,
525 Loop *L, Instruction *InsertPt,
527 // Before expanding S into an expensive LLVM expression, see if we can use an
528 // already existing value as the expansion for S.
529 if (Value *ExistingValue = Rewriter.getExactExistingExpansion(S, InsertPt, L))
530 if (ExistingValue->getType() == ResultTy)
531 return ExistingValue;
533 // We didn't find anything, fall back to using SCEVExpander.
534 return Rewriter.expandCodeFor(S, ResultTy, InsertPt);
537 //===----------------------------------------------------------------------===//
538 // rewriteLoopExitValues - Optimize IV users outside the loop.
539 // As a side effect, reduces the amount of IV processing within the loop.
540 //===----------------------------------------------------------------------===//
542 /// Check to see if this loop has a computable loop-invariant execution count.
543 /// If so, this means that we can compute the final value of any expressions
544 /// that are recurrent in the loop, and substitute the exit values from the loop
545 /// into any instructions outside of the loop that use the final values of the
546 /// current expressions.
548 /// This is mostly redundant with the regular IndVarSimplify activities that
549 /// happen later, except that it's more powerful in some cases, because it's
550 /// able to brute-force evaluate arbitrary instructions as long as they have
551 /// constant operands at the beginning of the loop.
552 void IndVarSimplify::rewriteLoopExitValues(Loop *L, SCEVExpander &Rewriter) {
553 // Check a pre-condition.
554 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
555 "Indvars did not preserve LCSSA!");
557 SmallVector<BasicBlock*, 8> ExitBlocks;
558 L->getUniqueExitBlocks(ExitBlocks);
560 SmallVector<RewritePhi, 8> RewritePhiSet;
561 // Find all values that are computed inside the loop, but used outside of it.
562 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
563 // the exit blocks of the loop to find them.
564 for (BasicBlock *ExitBB : ExitBlocks) {
565 // If there are no PHI nodes in this exit block, then no values defined
566 // inside the loop are used on this path, skip it.
567 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
570 unsigned NumPreds = PN->getNumIncomingValues();
572 // Iterate over all of the PHI nodes.
573 BasicBlock::iterator BBI = ExitBB->begin();
574 while ((PN = dyn_cast<PHINode>(BBI++))) {
576 continue; // dead use, don't replace it
578 if (!SE->isSCEVable(PN->getType()))
581 // It's necessary to tell ScalarEvolution about this explicitly so that
582 // it can walk the def-use list and forget all SCEVs, as it may not be
583 // watching the PHI itself. Once the new exit value is in place, there
584 // may not be a def-use connection between the loop and every instruction
585 // which got a SCEVAddRecExpr for that loop.
588 // Iterate over all of the values in all the PHI nodes.
589 for (unsigned i = 0; i != NumPreds; ++i) {
590 // If the value being merged in is not integer or is not defined
591 // in the loop, skip it.
592 Value *InVal = PN->getIncomingValue(i);
593 if (!isa<Instruction>(InVal))
596 // If this pred is for a subloop, not L itself, skip it.
597 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
598 continue; // The Block is in a subloop, skip it.
600 // Check that InVal is defined in the loop.
601 Instruction *Inst = cast<Instruction>(InVal);
602 if (!L->contains(Inst))
605 // Okay, this instruction has a user outside of the current loop
606 // and varies predictably *inside* the loop. Evaluate the value it
607 // contains when the loop exits, if possible.
608 const SCEV *ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
609 if (!SE->isLoopInvariant(ExitValue, L) ||
610 !isSafeToExpand(ExitValue, *SE))
613 // Computing the value outside of the loop brings no benefit if :
614 // - it is definitely used inside the loop in a way which can not be
616 // - no use outside of the loop can take advantage of hoisting the
617 // computation out of the loop
618 if (ExitValue->getSCEVType()>=scMulExpr) {
619 unsigned NumHardInternalUses = 0;
620 unsigned NumSoftExternalUses = 0;
621 unsigned NumUses = 0;
622 for (auto IB = Inst->user_begin(), IE = Inst->user_end();
623 IB != IE && NumUses <= 6; ++IB) {
624 Instruction *UseInstr = cast<Instruction>(*IB);
625 unsigned Opc = UseInstr->getOpcode();
627 if (L->contains(UseInstr)) {
628 if (Opc == Instruction::Call || Opc == Instruction::Ret)
629 NumHardInternalUses++;
631 if (Opc == Instruction::PHI) {
632 // Do not count the Phi as a use. LCSSA may have inserted
633 // plenty of trivial ones.
635 for (auto PB = UseInstr->user_begin(),
636 PE = UseInstr->user_end();
637 PB != PE && NumUses <= 6; ++PB, ++NumUses) {
638 unsigned PhiOpc = cast<Instruction>(*PB)->getOpcode();
639 if (PhiOpc != Instruction::Call && PhiOpc != Instruction::Ret)
640 NumSoftExternalUses++;
644 if (Opc != Instruction::Call && Opc != Instruction::Ret)
645 NumSoftExternalUses++;
648 if (NumUses <= 6 && NumHardInternalUses && !NumSoftExternalUses)
652 bool HighCost = Rewriter.isHighCostExpansion(ExitValue, L, Inst);
654 expandSCEVIfNeeded(Rewriter, ExitValue, L, Inst, PN->getType());
656 LLVM_DEBUG(dbgs() << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
658 << " LoopVal = " << *Inst << "\n");
660 if (!isValidRewrite(Inst, ExitVal)) {
661 DeadInsts.push_back(ExitVal);
665 // Collect all the candidate PHINodes to be rewritten.
666 RewritePhiSet.emplace_back(PN, i, ExitVal, HighCost);
671 bool LoopCanBeDel = canLoopBeDeleted(L, RewritePhiSet);
674 for (const RewritePhi &Phi : RewritePhiSet) {
675 PHINode *PN = Phi.PN;
676 Value *ExitVal = Phi.Val;
678 // Only do the rewrite when the ExitValue can be expanded cheaply.
679 // If LoopCanBeDel is true, rewrite exit value aggressively.
680 if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
681 DeadInsts.push_back(ExitVal);
687 Instruction *Inst = cast<Instruction>(PN->getIncomingValue(Phi.Ith));
688 PN->setIncomingValue(Phi.Ith, ExitVal);
690 // If this instruction is dead now, delete it. Don't do it now to avoid
691 // invalidating iterators.
692 if (isInstructionTriviallyDead(Inst, TLI))
693 DeadInsts.push_back(Inst);
695 // Replace PN with ExitVal if that is legal and does not break LCSSA.
696 if (PN->getNumIncomingValues() == 1 &&
697 LI->replacementPreservesLCSSAForm(PN, ExitVal)) {
698 PN->replaceAllUsesWith(ExitVal);
699 PN->eraseFromParent();
703 // The insertion point instruction may have been deleted; clear it out
704 // so that the rewriter doesn't trip over it later.
705 Rewriter.clearInsertPoint();
708 //===---------------------------------------------------------------------===//
709 // rewriteFirstIterationLoopExitValues: Rewrite loop exit values if we know
710 // they will exit at the first iteration.
711 //===---------------------------------------------------------------------===//
713 /// Check to see if this loop has loop invariant conditions which lead to loop
714 /// exits. If so, we know that if the exit path is taken, it is at the first
715 /// loop iteration. This lets us predict exit values of PHI nodes that live in
717 void IndVarSimplify::rewriteFirstIterationLoopExitValues(Loop *L) {
718 // Verify the input to the pass is already in LCSSA form.
719 assert(L->isLCSSAForm(*DT));
721 SmallVector<BasicBlock *, 8> ExitBlocks;
722 L->getUniqueExitBlocks(ExitBlocks);
723 auto *LoopHeader = L->getHeader();
724 assert(LoopHeader && "Invalid loop");
726 for (auto *ExitBB : ExitBlocks) {
727 // If there are no more PHI nodes in this exit block, then no more
728 // values defined inside the loop are used on this path.
729 for (PHINode &PN : ExitBB->phis()) {
730 for (unsigned IncomingValIdx = 0, E = PN.getNumIncomingValues();
731 IncomingValIdx != E; ++IncomingValIdx) {
732 auto *IncomingBB = PN.getIncomingBlock(IncomingValIdx);
734 // We currently only support loop exits from loop header. If the
735 // incoming block is not loop header, we need to recursively check
736 // all conditions starting from loop header are loop invariants.
737 // Additional support might be added in the future.
738 if (IncomingBB != LoopHeader)
741 // Get condition that leads to the exit path.
742 auto *TermInst = IncomingBB->getTerminator();
744 Value *Cond = nullptr;
745 if (auto *BI = dyn_cast<BranchInst>(TermInst)) {
746 // Must be a conditional branch, otherwise the block
747 // should not be in the loop.
748 Cond = BI->getCondition();
749 } else if (auto *SI = dyn_cast<SwitchInst>(TermInst))
750 Cond = SI->getCondition();
754 if (!L->isLoopInvariant(Cond))
757 auto *ExitVal = dyn_cast<PHINode>(PN.getIncomingValue(IncomingValIdx));
759 // Only deal with PHIs.
763 // If ExitVal is a PHI on the loop header, then we know its
764 // value along this exit because the exit can only be taken
765 // on the first iteration.
766 auto *LoopPreheader = L->getLoopPreheader();
767 assert(LoopPreheader && "Invalid loop");
768 int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
769 if (PreheaderIdx != -1) {
770 assert(ExitVal->getParent() == LoopHeader &&
771 "ExitVal must be in loop header");
772 PN.setIncomingValue(IncomingValIdx,
773 ExitVal->getIncomingValue(PreheaderIdx));
780 /// Check whether it is possible to delete the loop after rewriting exit
781 /// value. If it is possible, ignore ReplaceExitValue and do rewriting
783 bool IndVarSimplify::canLoopBeDeleted(
784 Loop *L, SmallVector<RewritePhi, 8> &RewritePhiSet) {
785 BasicBlock *Preheader = L->getLoopPreheader();
786 // If there is no preheader, the loop will not be deleted.
790 // In LoopDeletion pass Loop can be deleted when ExitingBlocks.size() > 1.
791 // We obviate multiple ExitingBlocks case for simplicity.
792 // TODO: If we see testcase with multiple ExitingBlocks can be deleted
793 // after exit value rewriting, we can enhance the logic here.
794 SmallVector<BasicBlock *, 4> ExitingBlocks;
795 L->getExitingBlocks(ExitingBlocks);
796 SmallVector<BasicBlock *, 8> ExitBlocks;
797 L->getUniqueExitBlocks(ExitBlocks);
798 if (ExitBlocks.size() > 1 || ExitingBlocks.size() > 1)
801 BasicBlock *ExitBlock = ExitBlocks[0];
802 BasicBlock::iterator BI = ExitBlock->begin();
803 while (PHINode *P = dyn_cast<PHINode>(BI)) {
804 Value *Incoming = P->getIncomingValueForBlock(ExitingBlocks[0]);
806 // If the Incoming value of P is found in RewritePhiSet, we know it
807 // could be rewritten to use a loop invariant value in transformation
808 // phase later. Skip it in the loop invariant check below.
810 for (const RewritePhi &Phi : RewritePhiSet) {
811 unsigned i = Phi.Ith;
812 if (Phi.PN == P && (Phi.PN)->getIncomingValue(i) == Incoming) {
819 if (!found && (I = dyn_cast<Instruction>(Incoming)))
820 if (!L->hasLoopInvariantOperands(I))
826 for (auto *BB : L->blocks())
827 if (llvm::any_of(*BB, [](Instruction &I) {
828 return I.mayHaveSideEffects();
835 //===----------------------------------------------------------------------===//
836 // IV Widening - Extend the width of an IV to cover its widest uses.
837 //===----------------------------------------------------------------------===//
841 // Collect information about induction variables that are used by sign/zero
842 // extend operations. This information is recorded by CollectExtend and provides
843 // the input to WidenIV.
845 PHINode *NarrowIV = nullptr;
847 // Widest integer type created [sz]ext
848 Type *WidestNativeType = nullptr;
850 // Was a sext user seen before a zext?
851 bool IsSigned = false;
854 } // end anonymous namespace
856 /// Update information about the induction variable that is extended by this
857 /// sign or zero extend operation. This is used to determine the final width of
858 /// the IV before actually widening it.
859 static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE,
860 const TargetTransformInfo *TTI) {
861 bool IsSigned = Cast->getOpcode() == Instruction::SExt;
862 if (!IsSigned && Cast->getOpcode() != Instruction::ZExt)
865 Type *Ty = Cast->getType();
866 uint64_t Width = SE->getTypeSizeInBits(Ty);
867 if (!Cast->getModule()->getDataLayout().isLegalInteger(Width))
870 // Check that `Cast` actually extends the induction variable (we rely on this
871 // later). This takes care of cases where `Cast` is extending a truncation of
872 // the narrow induction variable, and thus can end up being narrower than the
873 // "narrow" induction variable.
874 uint64_t NarrowIVWidth = SE->getTypeSizeInBits(WI.NarrowIV->getType());
875 if (NarrowIVWidth >= Width)
878 // Cast is either an sext or zext up to this point.
879 // We should not widen an indvar if arithmetics on the wider indvar are more
880 // expensive than those on the narrower indvar. We check only the cost of ADD
881 // because at least an ADD is required to increment the induction variable. We
882 // could compute more comprehensively the cost of all instructions on the
883 // induction variable when necessary.
885 TTI->getArithmeticInstrCost(Instruction::Add, Ty) >
886 TTI->getArithmeticInstrCost(Instruction::Add,
887 Cast->getOperand(0)->getType())) {
891 if (!WI.WidestNativeType) {
892 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
893 WI.IsSigned = IsSigned;
897 // We extend the IV to satisfy the sign of its first user, arbitrarily.
898 if (WI.IsSigned != IsSigned)
901 if (Width > SE->getTypeSizeInBits(WI.WidestNativeType))
902 WI.WidestNativeType = SE->getEffectiveSCEVType(Ty);
907 /// Record a link in the Narrow IV def-use chain along with the WideIV that
908 /// computes the same value as the Narrow IV def. This avoids caching Use*
910 struct NarrowIVDefUse {
911 Instruction *NarrowDef = nullptr;
912 Instruction *NarrowUse = nullptr;
913 Instruction *WideDef = nullptr;
915 // True if the narrow def is never negative. Tracking this information lets
916 // us use a sign extension instead of a zero extension or vice versa, when
917 // profitable and legal.
918 bool NeverNegative = false;
920 NarrowIVDefUse(Instruction *ND, Instruction *NU, Instruction *WD,
922 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
923 NeverNegative(NeverNegative) {}
926 /// The goal of this transform is to remove sign and zero extends without
927 /// creating any new induction variables. To do this, it creates a new phi of
928 /// the wider type and redirects all users, either removing extends or inserting
929 /// truncs whenever we stop propagating the type.
941 // Does the module have any calls to the llvm.experimental.guard intrinsic
942 // at all? If not we can avoid scanning instructions looking for guards.
946 PHINode *WidePhi = nullptr;
947 Instruction *WideInc = nullptr;
948 const SCEV *WideIncExpr = nullptr;
949 SmallVectorImpl<WeakTrackingVH> &DeadInsts;
951 SmallPtrSet<Instruction *,16> Widened;
952 SmallVector<NarrowIVDefUse, 8> NarrowIVUsers;
954 enum ExtendKind { ZeroExtended, SignExtended, Unknown };
956 // A map tracking the kind of extension used to widen each narrow IV
957 // and narrow IV user.
958 // Key: pointer to a narrow IV or IV user.
959 // Value: the kind of extension used to widen this Instruction.
960 DenseMap<AssertingVH<Instruction>, ExtendKind> ExtendKindMap;
962 using DefUserPair = std::pair<AssertingVH<Value>, AssertingVH<Instruction>>;
964 // A map with control-dependent ranges for post increment IV uses. The key is
965 // a pair of IV def and a use of this def denoting the context. The value is
966 // a ConstantRange representing possible values of the def at the given
968 DenseMap<DefUserPair, ConstantRange> PostIncRangeInfos;
970 Optional<ConstantRange> getPostIncRangeInfo(Value *Def,
972 DefUserPair Key(Def, UseI);
973 auto It = PostIncRangeInfos.find(Key);
974 return It == PostIncRangeInfos.end()
975 ? Optional<ConstantRange>(None)
976 : Optional<ConstantRange>(It->second);
979 void calculatePostIncRanges(PHINode *OrigPhi);
980 void calculatePostIncRange(Instruction *NarrowDef, Instruction *NarrowUser);
982 void updatePostIncRangeInfo(Value *Def, Instruction *UseI, ConstantRange R) {
983 DefUserPair Key(Def, UseI);
984 auto It = PostIncRangeInfos.find(Key);
985 if (It == PostIncRangeInfos.end())
986 PostIncRangeInfos.insert({Key, R});
988 It->second = R.intersectWith(It->second);
992 WidenIV(const WideIVInfo &WI, LoopInfo *LInfo, ScalarEvolution *SEv,
993 DominatorTree *DTree, SmallVectorImpl<WeakTrackingVH> &DI,
995 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
996 L(LI->getLoopFor(OrigPhi->getParent())), SE(SEv), DT(DTree),
997 HasGuards(HasGuards), DeadInsts(DI) {
998 assert(L->getHeader() == OrigPhi->getParent() && "Phi must be an IV");
999 ExtendKindMap[OrigPhi] = WI.IsSigned ? SignExtended : ZeroExtended;
1002 PHINode *createWideIV(SCEVExpander &Rewriter);
1005 Value *createExtendInst(Value *NarrowOper, Type *WideType, bool IsSigned,
1008 Instruction *cloneIVUser(NarrowIVDefUse DU, const SCEVAddRecExpr *WideAR);
1009 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1010 const SCEVAddRecExpr *WideAR);
1011 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1013 ExtendKind getExtendKind(Instruction *I);
1015 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1017 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1019 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1021 const SCEV *getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1022 unsigned OpCode) const;
1024 Instruction *widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter);
1026 bool widenLoopCompare(NarrowIVDefUse DU);
1028 void pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef);
1031 } // end anonymous namespace
1033 /// Perform a quick domtree based check for loop invariance assuming that V is
1034 /// used within the loop. LoopInfo::isLoopInvariant() seems gratuitous for this
1036 static bool isLoopInvariant(Value *V, const Loop *L, const DominatorTree *DT) {
1037 Instruction *Inst = dyn_cast<Instruction>(V);
1041 return DT->properlyDominates(Inst->getParent(), L->getHeader());
1044 Value *WidenIV::createExtendInst(Value *NarrowOper, Type *WideType,
1045 bool IsSigned, Instruction *Use) {
1046 // Set the debug location and conservative insertion point.
1047 IRBuilder<> Builder(Use);
1048 // Hoist the insertion point into loop preheaders as far as possible.
1049 for (const Loop *L = LI->getLoopFor(Use->getParent());
1050 L && L->getLoopPreheader() && isLoopInvariant(NarrowOper, L, DT);
1051 L = L->getParentLoop())
1052 Builder.SetInsertPoint(L->getLoopPreheader()->getTerminator());
1054 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1055 Builder.CreateZExt(NarrowOper, WideType);
1058 /// Instantiate a wide operation to replace a narrow operation. This only needs
1059 /// to handle operations that can evaluation to SCEVAddRec. It can safely return
1060 /// 0 for any operation we decide not to clone.
1061 Instruction *WidenIV::cloneIVUser(NarrowIVDefUse DU,
1062 const SCEVAddRecExpr *WideAR) {
1063 unsigned Opcode = DU.NarrowUse->getOpcode();
1067 case Instruction::Add:
1068 case Instruction::Mul:
1069 case Instruction::UDiv:
1070 case Instruction::Sub:
1071 return cloneArithmeticIVUser(DU, WideAR);
1073 case Instruction::And:
1074 case Instruction::Or:
1075 case Instruction::Xor:
1076 case Instruction::Shl:
1077 case Instruction::LShr:
1078 case Instruction::AShr:
1079 return cloneBitwiseIVUser(DU);
1083 Instruction *WidenIV::cloneBitwiseIVUser(NarrowIVDefUse DU) {
1084 Instruction *NarrowUse = DU.NarrowUse;
1085 Instruction *NarrowDef = DU.NarrowDef;
1086 Instruction *WideDef = DU.WideDef;
1088 LLVM_DEBUG(dbgs() << "Cloning bitwise IVUser: " << *NarrowUse << "\n");
1090 // Replace NarrowDef operands with WideDef. Otherwise, we don't know anything
1091 // about the narrow operand yet so must insert a [sz]ext. It is probably loop
1092 // invariant and will be folded or hoisted. If it actually comes from a
1093 // widened IV, it should be removed during a future call to widenIVUse.
1094 bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1095 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1097 : createExtendInst(NarrowUse->getOperand(0), WideType,
1098 IsSigned, NarrowUse);
1099 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1101 : createExtendInst(NarrowUse->getOperand(1), WideType,
1102 IsSigned, NarrowUse);
1104 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1105 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1106 NarrowBO->getName());
1107 IRBuilder<> Builder(NarrowUse);
1108 Builder.Insert(WideBO);
1109 WideBO->copyIRFlags(NarrowBO);
1113 Instruction *WidenIV::cloneArithmeticIVUser(NarrowIVDefUse DU,
1114 const SCEVAddRecExpr *WideAR) {
1115 Instruction *NarrowUse = DU.NarrowUse;
1116 Instruction *NarrowDef = DU.NarrowDef;
1117 Instruction *WideDef = DU.WideDef;
1119 LLVM_DEBUG(dbgs() << "Cloning arithmetic IVUser: " << *NarrowUse << "\n");
1121 unsigned IVOpIdx = (NarrowUse->getOperand(0) == NarrowDef) ? 0 : 1;
1123 // We're trying to find X such that
1125 // Widen(NarrowDef `op` NonIVNarrowDef) == WideAR == WideDef `op.wide` X
1127 // We guess two solutions to X, sext(NonIVNarrowDef) and zext(NonIVNarrowDef),
1128 // and check using SCEV if any of them are correct.
1130 // Returns true if extending NonIVNarrowDef according to `SignExt` is a
1131 // correct solution to X.
1132 auto GuessNonIVOperand = [&](bool SignExt) {
1133 const SCEV *WideLHS;
1134 const SCEV *WideRHS;
1136 auto GetExtend = [this, SignExt](const SCEV *S, Type *Ty) {
1138 return SE->getSignExtendExpr(S, Ty);
1139 return SE->getZeroExtendExpr(S, Ty);
1143 WideLHS = SE->getSCEV(WideDef);
1144 const SCEV *NarrowRHS = SE->getSCEV(NarrowUse->getOperand(1));
1145 WideRHS = GetExtend(NarrowRHS, WideType);
1147 const SCEV *NarrowLHS = SE->getSCEV(NarrowUse->getOperand(0));
1148 WideLHS = GetExtend(NarrowLHS, WideType);
1149 WideRHS = SE->getSCEV(WideDef);
1152 // WideUse is "WideDef `op.wide` X" as described in the comment.
1153 const SCEV *WideUse = nullptr;
1155 switch (NarrowUse->getOpcode()) {
1157 llvm_unreachable("No other possibility!");
1159 case Instruction::Add:
1160 WideUse = SE->getAddExpr(WideLHS, WideRHS);
1163 case Instruction::Mul:
1164 WideUse = SE->getMulExpr(WideLHS, WideRHS);
1167 case Instruction::UDiv:
1168 WideUse = SE->getUDivExpr(WideLHS, WideRHS);
1171 case Instruction::Sub:
1172 WideUse = SE->getMinusSCEV(WideLHS, WideRHS);
1176 return WideUse == WideAR;
1179 bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1180 if (!GuessNonIVOperand(SignExtend)) {
1181 SignExtend = !SignExtend;
1182 if (!GuessNonIVOperand(SignExtend))
1186 Value *LHS = (NarrowUse->getOperand(0) == NarrowDef)
1188 : createExtendInst(NarrowUse->getOperand(0), WideType,
1189 SignExtend, NarrowUse);
1190 Value *RHS = (NarrowUse->getOperand(1) == NarrowDef)
1192 : createExtendInst(NarrowUse->getOperand(1), WideType,
1193 SignExtend, NarrowUse);
1195 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1196 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(), LHS, RHS,
1197 NarrowBO->getName());
1199 IRBuilder<> Builder(NarrowUse);
1200 Builder.Insert(WideBO);
1201 WideBO->copyIRFlags(NarrowBO);
1205 WidenIV::ExtendKind WidenIV::getExtendKind(Instruction *I) {
1206 auto It = ExtendKindMap.find(I);
1207 assert(It != ExtendKindMap.end() && "Instruction not yet extended!");
1211 const SCEV *WidenIV::getSCEVByOpCode(const SCEV *LHS, const SCEV *RHS,
1212 unsigned OpCode) const {
1213 if (OpCode == Instruction::Add)
1214 return SE->getAddExpr(LHS, RHS);
1215 if (OpCode == Instruction::Sub)
1216 return SE->getMinusSCEV(LHS, RHS);
1217 if (OpCode == Instruction::Mul)
1218 return SE->getMulExpr(LHS, RHS);
1220 llvm_unreachable("Unsupported opcode.");
1223 /// No-wrap operations can transfer sign extension of their result to their
1224 /// operands. Generate the SCEV value for the widened operation without
1225 /// actually modifying the IR yet. If the expression after extending the
1226 /// operands is an AddRec for this loop, return the AddRec and the kind of
1228 WidenIV::WidenedRecTy WidenIV::getExtendedOperandRecurrence(NarrowIVDefUse DU) {
1229 // Handle the common case of add<nsw/nuw>
1230 const unsigned OpCode = DU.NarrowUse->getOpcode();
1231 // Only Add/Sub/Mul instructions supported yet.
1232 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1233 OpCode != Instruction::Mul)
1234 return {nullptr, Unknown};
1236 // One operand (NarrowDef) has already been extended to WideDef. Now determine
1237 // if extending the other will lead to a recurrence.
1238 const unsigned ExtendOperIdx =
1239 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1240 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef && "bad DU");
1242 const SCEV *ExtendOperExpr = nullptr;
1243 const OverflowingBinaryOperator *OBO =
1244 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1245 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1246 if (ExtKind == SignExtended && OBO->hasNoSignedWrap())
1247 ExtendOperExpr = SE->getSignExtendExpr(
1248 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1249 else if(ExtKind == ZeroExtended && OBO->hasNoUnsignedWrap())
1250 ExtendOperExpr = SE->getZeroExtendExpr(
1251 SE->getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1253 return {nullptr, Unknown};
1255 // When creating this SCEV expr, don't apply the current operations NSW or NUW
1256 // flags. This instruction may be guarded by control flow that the no-wrap
1257 // behavior depends on. Non-control-equivalent instructions can be mapped to
1258 // the same SCEV expression, and it would be incorrect to transfer NSW/NUW
1259 // semantics to those operations.
1260 const SCEV *lhs = SE->getSCEV(DU.WideDef);
1261 const SCEV *rhs = ExtendOperExpr;
1263 // Let's swap operands to the initial order for the case of non-commutative
1264 // operations, like SUB. See PR21014.
1265 if (ExtendOperIdx == 0)
1266 std::swap(lhs, rhs);
1267 const SCEVAddRecExpr *AddRec =
1268 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1270 if (!AddRec || AddRec->getLoop() != L)
1271 return {nullptr, Unknown};
1273 return {AddRec, ExtKind};
1276 /// Is this instruction potentially interesting for further simplification after
1277 /// widening it's type? In other words, can the extend be safely hoisted out of
1278 /// the loop with SCEV reducing the value to a recurrence on the same loop. If
1279 /// so, return the extended recurrence and the kind of extension used. Otherwise
1280 /// return {nullptr, Unknown}.
1281 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(NarrowIVDefUse DU) {
1282 if (!SE->isSCEVable(DU.NarrowUse->getType()))
1283 return {nullptr, Unknown};
1285 const SCEV *NarrowExpr = SE->getSCEV(DU.NarrowUse);
1286 if (SE->getTypeSizeInBits(NarrowExpr->getType()) >=
1287 SE->getTypeSizeInBits(WideType)) {
1288 // NarrowUse implicitly widens its operand. e.g. a gep with a narrow
1289 // index. So don't follow this use.
1290 return {nullptr, Unknown};
1293 const SCEV *WideExpr;
1295 if (DU.NeverNegative) {
1296 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1297 if (isa<SCEVAddRecExpr>(WideExpr))
1298 ExtKind = SignExtended;
1300 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1301 ExtKind = ZeroExtended;
1303 } else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1304 WideExpr = SE->getSignExtendExpr(NarrowExpr, WideType);
1305 ExtKind = SignExtended;
1307 WideExpr = SE->getZeroExtendExpr(NarrowExpr, WideType);
1308 ExtKind = ZeroExtended;
1310 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1311 if (!AddRec || AddRec->getLoop() != L)
1312 return {nullptr, Unknown};
1313 return {AddRec, ExtKind};
1316 /// This IV user cannot be widen. Replace this use of the original narrow IV
1317 /// with a truncation of the new wide IV to isolate and eliminate the narrow IV.
1318 static void truncateIVUse(NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI) {
1319 LLVM_DEBUG(dbgs() << "INDVARS: Truncate IV " << *DU.WideDef << " for user "
1320 << *DU.NarrowUse << "\n");
1321 IRBuilder<> Builder(
1322 getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
1323 Value *Trunc = Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1324 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1327 /// If the narrow use is a compare instruction, then widen the compare
1328 // (and possibly the other operand). The extend operation is hoisted into the
1329 // loop preheader as far as possible.
1330 bool WidenIV::widenLoopCompare(NarrowIVDefUse DU) {
1331 ICmpInst *Cmp = dyn_cast<ICmpInst>(DU.NarrowUse);
1335 // We can legally widen the comparison in the following two cases:
1337 // - The signedness of the IV extension and comparison match
1339 // - The narrow IV is always positive (and thus its sign extension is equal
1340 // to its zero extension). For instance, let's say we're zero extending
1341 // %narrow for the following use
1343 // icmp slt i32 %narrow, %val ... (A)
1345 // and %narrow is always positive. Then
1347 // (A) == icmp slt i32 sext(%narrow), sext(%val)
1348 // == icmp slt i32 zext(%narrow), sext(%val)
1349 bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1350 if (!(DU.NeverNegative || IsSigned == Cmp->isSigned()))
1353 Value *Op = Cmp->getOperand(Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1354 unsigned CastWidth = SE->getTypeSizeInBits(Op->getType());
1355 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1356 assert(CastWidth <= IVWidth && "Unexpected width while widening compare.");
1358 // Widen the compare instruction.
1359 IRBuilder<> Builder(
1360 getInsertPointForUses(DU.NarrowUse, DU.NarrowDef, DT, LI));
1361 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1363 // Widen the other operand of the compare, if necessary.
1364 if (CastWidth < IVWidth) {
1365 Value *ExtOp = createExtendInst(Op, WideType, Cmp->isSigned(), Cmp);
1366 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1371 /// Determine whether an individual user of the narrow IV can be widened. If so,
1372 /// return the wide clone of the user.
1373 Instruction *WidenIV::widenIVUse(NarrowIVDefUse DU, SCEVExpander &Rewriter) {
1374 assert(ExtendKindMap.count(DU.NarrowDef) &&
1375 "Should already know the kind of extension used to widen NarrowDef");
1377 // Stop traversing the def-use chain at inner-loop phis or post-loop phis.
1378 if (PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1379 if (LI->getLoopFor(UsePhi->getParent()) != L) {
1380 // For LCSSA phis, sink the truncate outside the loop.
1381 // After SimplifyCFG most loop exit targets have a single predecessor.
1382 // Otherwise fall back to a truncate within the loop.
1383 if (UsePhi->getNumOperands() != 1)
1384 truncateIVUse(DU, DT, LI);
1386 // Widening the PHI requires us to insert a trunc. The logical place
1387 // for this trunc is in the same BB as the PHI. This is not possible if
1388 // the BB is terminated by a catchswitch.
1389 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1393 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() + ".wide",
1395 WidePhi->addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1396 IRBuilder<> Builder(&*WidePhi->getParent()->getFirstInsertionPt());
1397 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1398 UsePhi->replaceAllUsesWith(Trunc);
1399 DeadInsts.emplace_back(UsePhi);
1400 LLVM_DEBUG(dbgs() << "INDVARS: Widen lcssa phi " << *UsePhi << " to "
1401 << *WidePhi << "\n");
1407 // This narrow use can be widened by a sext if it's non-negative or its narrow
1408 // def was widended by a sext. Same for zext.
1409 auto canWidenBySExt = [&]() {
1410 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1412 auto canWidenByZExt = [&]() {
1413 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1416 // Our raison d'etre! Eliminate sign and zero extension.
1417 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1418 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1419 Value *NewDef = DU.WideDef;
1420 if (DU.NarrowUse->getType() != WideType) {
1421 unsigned CastWidth = SE->getTypeSizeInBits(DU.NarrowUse->getType());
1422 unsigned IVWidth = SE->getTypeSizeInBits(WideType);
1423 if (CastWidth < IVWidth) {
1424 // The cast isn't as wide as the IV, so insert a Trunc.
1425 IRBuilder<> Builder(DU.NarrowUse);
1426 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1429 // A wider extend was hidden behind a narrower one. This may induce
1430 // another round of IV widening in which the intermediate IV becomes
1431 // dead. It should be very rare.
1432 LLVM_DEBUG(dbgs() << "INDVARS: New IV " << *WidePhi
1433 << " not wide enough to subsume " << *DU.NarrowUse
1435 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1436 NewDef = DU.NarrowUse;
1439 if (NewDef != DU.NarrowUse) {
1440 LLVM_DEBUG(dbgs() << "INDVARS: eliminating " << *DU.NarrowUse
1441 << " replaced by " << *DU.WideDef << "\n");
1443 DU.NarrowUse->replaceAllUsesWith(NewDef);
1444 DeadInsts.emplace_back(DU.NarrowUse);
1446 // Now that the extend is gone, we want to expose it's uses for potential
1447 // further simplification. We don't need to directly inform SimplifyIVUsers
1448 // of the new users, because their parent IV will be processed later as a
1449 // new loop phi. If we preserved IVUsers analysis, we would also want to
1450 // push the uses of WideDef here.
1452 // No further widening is needed. The deceased [sz]ext had done it for us.
1456 // Does this user itself evaluate to a recurrence after widening?
1457 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1458 if (!WideAddRec.first)
1459 WideAddRec = getWideRecurrence(DU);
1461 assert((WideAddRec.first == nullptr) == (WideAddRec.second == Unknown));
1462 if (!WideAddRec.first) {
1463 // If use is a loop condition, try to promote the condition instead of
1464 // truncating the IV first.
1465 if (widenLoopCompare(DU))
1468 // This user does not evaluate to a recurrence after widening, so don't
1469 // follow it. Instead insert a Trunc to kill off the original use,
1470 // eventually isolating the original narrow IV so it can be removed.
1471 truncateIVUse(DU, DT, LI);
1474 // Assume block terminators cannot evaluate to a recurrence. We can't to
1475 // insert a Trunc after a terminator if there happens to be a critical edge.
1476 assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
1477 "SCEV is not expected to evaluate a block terminator");
1479 // Reuse the IV increment that SCEVExpander created as long as it dominates
1481 Instruction *WideUse = nullptr;
1482 if (WideAddRec.first == WideIncExpr &&
1483 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1486 WideUse = cloneIVUser(DU, WideAddRec.first);
1490 // Evaluation of WideAddRec ensured that the narrow expression could be
1491 // extended outside the loop without overflow. This suggests that the wide use
1492 // evaluates to the same expression as the extended narrow use, but doesn't
1493 // absolutely guarantee it. Hence the following failsafe check. In rare cases
1494 // where it fails, we simply throw away the newly created wide use.
1495 if (WideAddRec.first != SE->getSCEV(WideUse)) {
1496 LLVM_DEBUG(dbgs() << "Wide use expression mismatch: " << *WideUse << ": "
1497 << *SE->getSCEV(WideUse) << " != " << *WideAddRec.first
1499 DeadInsts.emplace_back(WideUse);
1503 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1504 // Returning WideUse pushes it on the worklist.
1508 /// Add eligible users of NarrowDef to NarrowIVUsers.
1509 void WidenIV::pushNarrowIVUsers(Instruction *NarrowDef, Instruction *WideDef) {
1510 const SCEV *NarrowSCEV = SE->getSCEV(NarrowDef);
1511 bool NonNegativeDef =
1512 SE->isKnownPredicate(ICmpInst::ICMP_SGE, NarrowSCEV,
1513 SE->getConstant(NarrowSCEV->getType(), 0));
1514 for (User *U : NarrowDef->users()) {
1515 Instruction *NarrowUser = cast<Instruction>(U);
1517 // Handle data flow merges and bizarre phi cycles.
1518 if (!Widened.insert(NarrowUser).second)
1521 bool NonNegativeUse = false;
1522 if (!NonNegativeDef) {
1523 // We might have a control-dependent range information for this context.
1524 if (auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1525 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1528 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1529 NonNegativeDef || NonNegativeUse);
1533 /// Process a single induction variable. First use the SCEVExpander to create a
1534 /// wide induction variable that evaluates to the same recurrence as the
1535 /// original narrow IV. Then use a worklist to forward traverse the narrow IV's
1536 /// def-use chain. After widenIVUse has processed all interesting IV users, the
1537 /// narrow IV will be isolated for removal by DeleteDeadPHIs.
1539 /// It would be simpler to delete uses as they are processed, but we must avoid
1540 /// invalidating SCEV expressions.
1541 PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
1542 // Is this phi an induction variable?
1543 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(OrigPhi));
1547 // Widen the induction variable expression.
1548 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1549 ? SE->getSignExtendExpr(AddRec, WideType)
1550 : SE->getZeroExtendExpr(AddRec, WideType);
1552 assert(SE->getEffectiveSCEVType(WideIVExpr->getType()) == WideType &&
1553 "Expect the new IV expression to preserve its type");
1555 // Can the IV be extended outside the loop without overflow?
1556 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1557 if (!AddRec || AddRec->getLoop() != L)
1560 // An AddRec must have loop-invariant operands. Since this AddRec is
1561 // materialized by a loop header phi, the expression cannot have any post-loop
1562 // operands, so they must dominate the loop header.
1564 SE->properlyDominates(AddRec->getStart(), L->getHeader()) &&
1565 SE->properlyDominates(AddRec->getStepRecurrence(*SE), L->getHeader()) &&
1566 "Loop header phi recurrence inputs do not dominate the loop");
1568 // Iterate over IV uses (including transitive ones) looking for IV increments
1569 // of the form 'add nsw %iv, <const>'. For each increment and each use of
1570 // the increment calculate control-dependent range information basing on
1571 // dominating conditions inside of the loop (e.g. a range check inside of the
1572 // loop). Calculated ranges are stored in PostIncRangeInfos map.
1574 // Control-dependent range information is later used to prove that a narrow
1575 // definition is not negative (see pushNarrowIVUsers). It's difficult to do
1576 // this on demand because when pushNarrowIVUsers needs this information some
1577 // of the dominating conditions might be already widened.
1578 if (UsePostIncrementRanges)
1579 calculatePostIncRanges(OrigPhi);
1581 // The rewriter provides a value for the desired IV expression. This may
1582 // either find an existing phi or materialize a new one. Either way, we
1583 // expect a well-formed cyclic phi-with-increments. i.e. any operand not part
1584 // of the phi-SCC dominates the loop entry.
1585 Instruction *InsertPt = &L->getHeader()->front();
1586 WidePhi = cast<PHINode>(Rewriter.expandCodeFor(AddRec, WideType, InsertPt));
1588 // Remembering the WideIV increment generated by SCEVExpander allows
1589 // widenIVUse to reuse it when widening the narrow IV's increment. We don't
1590 // employ a general reuse mechanism because the call above is the only call to
1591 // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
1592 if (BasicBlock *LatchBlock = L->getLoopLatch()) {
1594 cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
1595 WideIncExpr = SE->getSCEV(WideInc);
1596 // Propagate the debug location associated with the original loop increment
1597 // to the new (widened) increment.
1599 cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
1600 WideInc->setDebugLoc(OrigInc->getDebugLoc());
1603 LLVM_DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
1606 // Traverse the def-use chain using a worklist starting at the original IV.
1607 assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
1609 Widened.insert(OrigPhi);
1610 pushNarrowIVUsers(OrigPhi, WidePhi);
1612 while (!NarrowIVUsers.empty()) {
1613 NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1615 // Process a def-use edge. This may replace the use, so don't hold a
1616 // use_iterator across it.
1617 Instruction *WideUse = widenIVUse(DU, Rewriter);
1619 // Follow all def-use edges from the previous narrow use.
1621 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1623 // widenIVUse may have removed the def-use edge.
1624 if (DU.NarrowDef->use_empty())
1625 DeadInsts.emplace_back(DU.NarrowDef);
1628 // Attach any debug information to the new PHI. Since OrigPhi and WidePHI
1629 // evaluate the same recurrence, we can just copy the debug info over.
1630 SmallVector<DbgValueInst *, 1> DbgValues;
1631 llvm::findDbgValues(DbgValues, OrigPhi);
1632 auto *MDPhi = MetadataAsValue::get(WidePhi->getContext(),
1633 ValueAsMetadata::get(WidePhi));
1634 for (auto &DbgValue : DbgValues)
1635 DbgValue->setOperand(0, MDPhi);
1639 /// Calculates control-dependent range for the given def at the given context
1640 /// by looking at dominating conditions inside of the loop
1641 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
1642 Instruction *NarrowUser) {
1643 using namespace llvm::PatternMatch;
1645 Value *NarrowDefLHS;
1646 const APInt *NarrowDefRHS;
1647 if (!match(NarrowDef, m_NSWAdd(m_Value(NarrowDefLHS),
1648 m_APInt(NarrowDefRHS))) ||
1649 !NarrowDefRHS->isNonNegative())
1652 auto UpdateRangeFromCondition = [&] (Value *Condition,
1654 CmpInst::Predicate Pred;
1656 if (!match(Condition, m_ICmp(Pred, m_Specific(NarrowDefLHS),
1660 CmpInst::Predicate P =
1661 TrueDest ? Pred : CmpInst::getInversePredicate(Pred);
1663 auto CmpRHSRange = SE->getSignedRange(SE->getSCEV(CmpRHS));
1664 auto CmpConstrainedLHSRange =
1665 ConstantRange::makeAllowedICmpRegion(P, CmpRHSRange);
1666 auto NarrowDefRange =
1667 CmpConstrainedLHSRange.addWithNoSignedWrap(*NarrowDefRHS);
1669 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
1672 auto UpdateRangeFromGuards = [&](Instruction *Ctx) {
1676 for (Instruction &I : make_range(Ctx->getIterator().getReverse(),
1677 Ctx->getParent()->rend())) {
1679 if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(C))))
1680 UpdateRangeFromCondition(C, /*TrueDest=*/true);
1684 UpdateRangeFromGuards(NarrowUser);
1686 BasicBlock *NarrowUserBB = NarrowUser->getParent();
1687 // If NarrowUserBB is statically unreachable asking dominator queries may
1688 // yield surprising results. (e.g. the block may not have a dom tree node)
1689 if (!DT->isReachableFromEntry(NarrowUserBB))
1692 for (auto *DTB = (*DT)[NarrowUserBB]->getIDom();
1693 L->contains(DTB->getBlock());
1694 DTB = DTB->getIDom()) {
1695 auto *BB = DTB->getBlock();
1696 auto *TI = BB->getTerminator();
1697 UpdateRangeFromGuards(TI);
1699 auto *BI = dyn_cast<BranchInst>(TI);
1700 if (!BI || !BI->isConditional())
1703 auto *TrueSuccessor = BI->getSuccessor(0);
1704 auto *FalseSuccessor = BI->getSuccessor(1);
1706 auto DominatesNarrowUser = [this, NarrowUser] (BasicBlockEdge BBE) {
1707 return BBE.isSingleEdge() &&
1708 DT->dominates(BBE, NarrowUser->getParent());
1711 if (DominatesNarrowUser(BasicBlockEdge(BB, TrueSuccessor)))
1712 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/true);
1714 if (DominatesNarrowUser(BasicBlockEdge(BB, FalseSuccessor)))
1715 UpdateRangeFromCondition(BI->getCondition(), /*TrueDest=*/false);
1719 /// Calculates PostIncRangeInfos map for the given IV
1720 void WidenIV::calculatePostIncRanges(PHINode *OrigPhi) {
1721 SmallPtrSet<Instruction *, 16> Visited;
1722 SmallVector<Instruction *, 6> Worklist;
1723 Worklist.push_back(OrigPhi);
1724 Visited.insert(OrigPhi);
1726 while (!Worklist.empty()) {
1727 Instruction *NarrowDef = Worklist.pop_back_val();
1729 for (Use &U : NarrowDef->uses()) {
1730 auto *NarrowUser = cast<Instruction>(U.getUser());
1732 // Don't go looking outside the current loop.
1733 auto *NarrowUserLoop = (*LI)[NarrowUser->getParent()];
1734 if (!NarrowUserLoop || !L->contains(NarrowUserLoop))
1737 if (!Visited.insert(NarrowUser).second)
1740 Worklist.push_back(NarrowUser);
1742 calculatePostIncRange(NarrowDef, NarrowUser);
1747 //===----------------------------------------------------------------------===//
1748 // Live IV Reduction - Minimize IVs live across the loop.
1749 //===----------------------------------------------------------------------===//
1751 //===----------------------------------------------------------------------===//
1752 // Simplification of IV users based on SCEV evaluation.
1753 //===----------------------------------------------------------------------===//
1757 class IndVarSimplifyVisitor : public IVVisitor {
1758 ScalarEvolution *SE;
1759 const TargetTransformInfo *TTI;
1765 IndVarSimplifyVisitor(PHINode *IV, ScalarEvolution *SCEV,
1766 const TargetTransformInfo *TTI,
1767 const DominatorTree *DTree)
1768 : SE(SCEV), TTI(TTI), IVPhi(IV) {
1770 WI.NarrowIV = IVPhi;
1773 // Implement the interface used by simplifyUsersOfIV.
1774 void visitCast(CastInst *Cast) override { visitIVCast(Cast, WI, SE, TTI); }
1777 } // end anonymous namespace
1779 /// Iteratively perform simplification on a worklist of IV users. Each
1780 /// successive simplification may push more users which may themselves be
1781 /// candidates for simplification.
1783 /// Sign/Zero extend elimination is interleaved with IV simplification.
1784 void IndVarSimplify::simplifyAndExtend(Loop *L,
1785 SCEVExpander &Rewriter,
1787 SmallVector<WideIVInfo, 8> WideIVs;
1789 auto *GuardDecl = L->getBlocks()[0]->getModule()->getFunction(
1790 Intrinsic::getName(Intrinsic::experimental_guard));
1791 bool HasGuards = GuardDecl && !GuardDecl->use_empty();
1793 SmallVector<PHINode*, 8> LoopPhis;
1794 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
1795 LoopPhis.push_back(cast<PHINode>(I));
1797 // Each round of simplification iterates through the SimplifyIVUsers worklist
1798 // for all current phis, then determines whether any IVs can be
1799 // widened. Widening adds new phis to LoopPhis, inducing another round of
1800 // simplification on the wide IVs.
1801 while (!LoopPhis.empty()) {
1802 // Evaluate as many IV expressions as possible before widening any IVs. This
1803 // forces SCEV to set no-wrap flags before evaluating sign/zero
1804 // extension. The first time SCEV attempts to normalize sign/zero extension,
1805 // the result becomes final. So for the most predictable results, we delay
1806 // evaluation of sign/zero extend evaluation until needed, and avoid running
1807 // other SCEV based analysis prior to simplifyAndExtend.
1809 PHINode *CurrIV = LoopPhis.pop_back_val();
1811 // Information about sign/zero extensions of CurrIV.
1812 IndVarSimplifyVisitor Visitor(CurrIV, SE, TTI, DT);
1815 simplifyUsersOfIV(CurrIV, SE, DT, LI, DeadInsts, Rewriter, &Visitor);
1817 if (Visitor.WI.WidestNativeType) {
1818 WideIVs.push_back(Visitor.WI);
1820 } while(!LoopPhis.empty());
1822 for (; !WideIVs.empty(); WideIVs.pop_back()) {
1823 WidenIV Widener(WideIVs.back(), LI, SE, DT, DeadInsts, HasGuards);
1824 if (PHINode *WidePhi = Widener.createWideIV(Rewriter)) {
1826 LoopPhis.push_back(WidePhi);
1832 //===----------------------------------------------------------------------===//
1833 // linearFunctionTestReplace and its kin. Rewrite the loop exit condition.
1834 //===----------------------------------------------------------------------===//
1836 /// Return true if this loop's backedge taken count expression can be safely and
1837 /// cheaply expanded into an instruction sequence that can be used by
1838 /// linearFunctionTestReplace.
1840 /// TODO: This fails for pointer-type loop counters with greater than one byte
1841 /// strides, consequently preventing LFTR from running. For the purpose of LFTR
1842 /// we could skip this check in the case that the LFTR loop counter (chosen by
1843 /// FindLoopCounter) is also pointer type. Instead, we could directly convert
1844 /// the loop test to an inequality test by checking the target data's alignment
1845 /// of element types (given that the initial pointer value originates from or is
1846 /// used by ABI constrained operation, as opposed to inttoptr/ptrtoint).
1847 /// However, we don't yet have a strong motivation for converting loop tests
1848 /// into inequality tests.
1849 static bool canExpandBackedgeTakenCount(Loop *L, ScalarEvolution *SE,
1850 SCEVExpander &Rewriter) {
1851 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
1852 if (isa<SCEVCouldNotCompute>(BackedgeTakenCount) ||
1853 BackedgeTakenCount->isZero())
1856 if (!L->getExitingBlock())
1859 // Can't rewrite non-branch yet.
1860 if (!isa<BranchInst>(L->getExitingBlock()->getTerminator()))
1863 if (Rewriter.isHighCostExpansion(BackedgeTakenCount, L))
1869 /// Return the loop header phi IFF IncV adds a loop invariant value to the phi.
1870 static PHINode *getLoopPhiForCounter(Value *IncV, Loop *L, DominatorTree *DT) {
1871 Instruction *IncI = dyn_cast<Instruction>(IncV);
1875 switch (IncI->getOpcode()) {
1876 case Instruction::Add:
1877 case Instruction::Sub:
1879 case Instruction::GetElementPtr:
1880 // An IV counter must preserve its type.
1881 if (IncI->getNumOperands() == 2)
1888 PHINode *Phi = dyn_cast<PHINode>(IncI->getOperand(0));
1889 if (Phi && Phi->getParent() == L->getHeader()) {
1890 if (isLoopInvariant(IncI->getOperand(1), L, DT))
1894 if (IncI->getOpcode() == Instruction::GetElementPtr)
1897 // Allow add/sub to be commuted.
1898 Phi = dyn_cast<PHINode>(IncI->getOperand(1));
1899 if (Phi && Phi->getParent() == L->getHeader()) {
1900 if (isLoopInvariant(IncI->getOperand(0), L, DT))
1906 /// Return the compare guarding the loop latch, or NULL for unrecognized tests.
1907 static ICmpInst *getLoopTest(Loop *L) {
1908 assert(L->getExitingBlock() && "expected loop exit");
1910 BasicBlock *LatchBlock = L->getLoopLatch();
1911 // Don't bother with LFTR if the loop is not properly simplified.
1915 BranchInst *BI = dyn_cast<BranchInst>(L->getExitingBlock()->getTerminator());
1916 assert(BI && "expected exit branch");
1918 return dyn_cast<ICmpInst>(BI->getCondition());
1921 /// linearFunctionTestReplace policy. Return true unless we can show that the
1922 /// current exit test is already sufficiently canonical.
1923 static bool needsLFTR(Loop *L, DominatorTree *DT) {
1924 // Do LFTR to simplify the exit condition to an ICMP.
1925 ICmpInst *Cond = getLoopTest(L);
1929 // Do LFTR to simplify the exit ICMP to EQ/NE
1930 ICmpInst::Predicate Pred = Cond->getPredicate();
1931 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
1934 // Look for a loop invariant RHS
1935 Value *LHS = Cond->getOperand(0);
1936 Value *RHS = Cond->getOperand(1);
1937 if (!isLoopInvariant(RHS, L, DT)) {
1938 if (!isLoopInvariant(LHS, L, DT))
1940 std::swap(LHS, RHS);
1942 // Look for a simple IV counter LHS
1943 PHINode *Phi = dyn_cast<PHINode>(LHS);
1945 Phi = getLoopPhiForCounter(LHS, L, DT);
1950 // Do LFTR if PHI node is defined in the loop, but is *not* a counter.
1951 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
1955 // Do LFTR if the exit condition's IV is *not* a simple counter.
1956 Value *IncV = Phi->getIncomingValue(Idx);
1957 return Phi != getLoopPhiForCounter(IncV, L, DT);
1960 /// Recursive helper for hasConcreteDef(). Unfortunately, this currently boils
1961 /// down to checking that all operands are constant and listing instructions
1962 /// that may hide undef.
1963 static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl<Value*> &Visited,
1965 if (isa<Constant>(V))
1966 return !isa<UndefValue>(V);
1971 // Conservatively handle non-constant non-instructions. For example, Arguments
1973 Instruction *I = dyn_cast<Instruction>(V);
1977 // Load and return values may be undef.
1978 if(I->mayReadFromMemory() || isa<CallInst>(I) || isa<InvokeInst>(I))
1981 // Optimistically handle other instructions.
1982 for (Value *Op : I->operands()) {
1983 if (!Visited.insert(Op).second)
1985 if (!hasConcreteDefImpl(Op, Visited, Depth+1))
1991 /// Return true if the given value is concrete. We must prove that undef can
1994 /// TODO: If we decide that this is a good approach to checking for undef, we
1995 /// may factor it into a common location.
1996 static bool hasConcreteDef(Value *V) {
1997 SmallPtrSet<Value*, 8> Visited;
1999 return hasConcreteDefImpl(V, Visited, 0);
2002 /// Return true if this IV has any uses other than the (soon to be rewritten)
2004 static bool AlmostDeadIV(PHINode *Phi, BasicBlock *LatchBlock, Value *Cond) {
2005 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
2006 Value *IncV = Phi->getIncomingValue(LatchIdx);
2008 for (User *U : Phi->users())
2009 if (U != Cond && U != IncV) return false;
2011 for (User *U : IncV->users())
2012 if (U != Cond && U != Phi) return false;
2016 /// Find an affine IV in canonical form.
2018 /// BECount may be an i8* pointer type. The pointer difference is already
2019 /// valid count without scaling the address stride, so it remains a pointer
2020 /// expression as far as SCEV is concerned.
2022 /// Currently only valid for LFTR. See the comments on hasConcreteDef below.
2024 /// FIXME: Accept -1 stride and set IVLimit = IVInit - BECount
2026 /// FIXME: Accept non-unit stride as long as SCEV can reduce BECount * Stride.
2027 /// This is difficult in general for SCEV because of potential overflow. But we
2028 /// could at least handle constant BECounts.
2029 static PHINode *FindLoopCounter(Loop *L, const SCEV *BECount,
2030 ScalarEvolution *SE, DominatorTree *DT) {
2031 uint64_t BCWidth = SE->getTypeSizeInBits(BECount->getType());
2034 cast<BranchInst>(L->getExitingBlock()->getTerminator())->getCondition();
2036 // Loop over all of the PHI nodes, looking for a simple counter.
2037 PHINode *BestPhi = nullptr;
2038 const SCEV *BestInit = nullptr;
2039 BasicBlock *LatchBlock = L->getLoopLatch();
2040 assert(LatchBlock && "needsLFTR should guarantee a loop latch");
2041 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2043 for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I) {
2044 PHINode *Phi = cast<PHINode>(I);
2045 if (!SE->isSCEVable(Phi->getType()))
2048 // Avoid comparing an integer IV against a pointer Limit.
2049 if (BECount->getType()->isPointerTy() && !Phi->getType()->isPointerTy())
2052 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Phi));
2053 if (!AR || AR->getLoop() != L || !AR->isAffine())
2056 // AR may be a pointer type, while BECount is an integer type.
2057 // AR may be wider than BECount. With eq/ne tests overflow is immaterial.
2058 // AR may not be a narrower type, or we may never exit.
2059 uint64_t PhiWidth = SE->getTypeSizeInBits(AR->getType());
2060 if (PhiWidth < BCWidth || !DL.isLegalInteger(PhiWidth))
2063 const SCEV *Step = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
2064 if (!Step || !Step->isOne())
2067 int LatchIdx = Phi->getBasicBlockIndex(LatchBlock);
2068 Value *IncV = Phi->getIncomingValue(LatchIdx);
2069 if (getLoopPhiForCounter(IncV, L, DT) != Phi)
2072 // Avoid reusing a potentially undef value to compute other values that may
2073 // have originally had a concrete definition.
2074 if (!hasConcreteDef(Phi)) {
2075 // We explicitly allow unknown phis as long as they are already used by
2076 // the loop test. In this case we assume that performing LFTR could not
2077 // increase the number of undef users.
2078 if (ICmpInst *Cond = getLoopTest(L)) {
2079 if (Phi != getLoopPhiForCounter(Cond->getOperand(0), L, DT) &&
2080 Phi != getLoopPhiForCounter(Cond->getOperand(1), L, DT)) {
2085 const SCEV *Init = AR->getStart();
2087 if (BestPhi && !AlmostDeadIV(BestPhi, LatchBlock, Cond)) {
2088 // Don't force a live loop counter if another IV can be used.
2089 if (AlmostDeadIV(Phi, LatchBlock, Cond))
2092 // Prefer to count-from-zero. This is a more "canonical" counter form. It
2093 // also prefers integer to pointer IVs.
2094 if (BestInit->isZero() != Init->isZero()) {
2095 if (BestInit->isZero())
2098 // If two IVs both count from zero or both count from nonzero then the
2099 // narrower is likely a dead phi that has been widened. Use the wider phi
2100 // to allow the other to be eliminated.
2101 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->getType()))
2110 /// Help linearFunctionTestReplace by generating a value that holds the RHS of
2111 /// the new loop test.
2112 static Value *genLoopLimit(PHINode *IndVar, const SCEV *IVCount, Loop *L,
2113 SCEVExpander &Rewriter, ScalarEvolution *SE) {
2114 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2115 assert(AR && AR->getLoop() == L && AR->isAffine() && "bad loop counter");
2116 const SCEV *IVInit = AR->getStart();
2118 // IVInit may be a pointer while IVCount is an integer when FindLoopCounter
2119 // finds a valid pointer IV. Sign extend BECount in order to materialize a
2120 // GEP. Avoid running SCEVExpander on a new pointer value, instead reusing
2121 // the existing GEPs whenever possible.
2122 if (IndVar->getType()->isPointerTy() && !IVCount->getType()->isPointerTy()) {
2123 // IVOffset will be the new GEP offset that is interpreted by GEP as a
2124 // signed value. IVCount on the other hand represents the loop trip count,
2125 // which is an unsigned value. FindLoopCounter only allows induction
2126 // variables that have a positive unit stride of one. This means we don't
2127 // have to handle the case of negative offsets (yet) and just need to zero
2129 Type *OfsTy = SE->getEffectiveSCEVType(IVInit->getType());
2130 const SCEV *IVOffset = SE->getTruncateOrZeroExtend(IVCount, OfsTy);
2132 // Expand the code for the iteration count.
2133 assert(SE->isLoopInvariant(IVOffset, L) &&
2134 "Computed iteration count is not loop invariant!");
2135 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2136 Value *GEPOffset = Rewriter.expandCodeFor(IVOffset, OfsTy, BI);
2138 Value *GEPBase = IndVar->getIncomingValueForBlock(L->getLoopPreheader());
2139 assert(AR->getStart() == SE->getSCEV(GEPBase) && "bad loop counter");
2140 // We could handle pointer IVs other than i8*, but we need to compensate for
2141 // gep index scaling. See canExpandBackedgeTakenCount comments.
2142 assert(SE->getSizeOfExpr(IntegerType::getInt64Ty(IndVar->getContext()),
2143 cast<PointerType>(GEPBase->getType())
2144 ->getElementType())->isOne() &&
2145 "unit stride pointer IV must be i8*");
2147 IRBuilder<> Builder(L->getLoopPreheader()->getTerminator());
2148 return Builder.CreateGEP(nullptr, GEPBase, GEPOffset, "lftr.limit");
2150 // In any other case, convert both IVInit and IVCount to integers before
2151 // comparing. This may result in SCEV expansion of pointers, but in practice
2152 // SCEV will fold the pointer arithmetic away as such:
2153 // BECount = (IVEnd - IVInit - 1) => IVLimit = IVInit (postinc).
2155 // Valid Cases: (1) both integers is most common; (2) both may be pointers
2156 // for simple memset-style loops.
2158 // IVInit integer and IVCount pointer would only occur if a canonical IV
2159 // were generated on top of case #2, which is not expected.
2161 const SCEV *IVLimit = nullptr;
2162 // For unit stride, IVCount = Start + BECount with 2's complement overflow.
2163 // For non-zero Start, compute IVCount here.
2164 if (AR->getStart()->isZero())
2167 assert(AR->getStepRecurrence(*SE)->isOne() && "only handles unit stride");
2168 const SCEV *IVInit = AR->getStart();
2170 // For integer IVs, truncate the IV before computing IVInit + BECount.
2171 if (SE->getTypeSizeInBits(IVInit->getType())
2172 > SE->getTypeSizeInBits(IVCount->getType()))
2173 IVInit = SE->getTruncateExpr(IVInit, IVCount->getType());
2175 IVLimit = SE->getAddExpr(IVInit, IVCount);
2177 // Expand the code for the iteration count.
2178 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2179 IRBuilder<> Builder(BI);
2180 assert(SE->isLoopInvariant(IVLimit, L) &&
2181 "Computed iteration count is not loop invariant!");
2182 // Ensure that we generate the same type as IndVar, or a smaller integer
2183 // type. In the presence of null pointer values, we have an integer type
2184 // SCEV expression (IVInit) for a pointer type IV value (IndVar).
2185 Type *LimitTy = IVCount->getType()->isPointerTy() ?
2186 IndVar->getType() : IVCount->getType();
2187 return Rewriter.expandCodeFor(IVLimit, LimitTy, BI);
2191 /// This method rewrites the exit condition of the loop to be a canonical !=
2192 /// comparison against the incremented loop induction variable. This pass is
2193 /// able to rewrite the exit tests of any loop where the SCEV analysis can
2194 /// determine a loop-invariant trip count of the loop, which is actually a much
2195 /// broader range than just linear tests.
2196 Value *IndVarSimplify::
2197 linearFunctionTestReplace(Loop *L,
2198 const SCEV *BackedgeTakenCount,
2200 SCEVExpander &Rewriter) {
2201 assert(canExpandBackedgeTakenCount(L, SE, Rewriter) && "precondition");
2203 // Initialize CmpIndVar and IVCount to their preincremented values.
2204 Value *CmpIndVar = IndVar;
2205 const SCEV *IVCount = BackedgeTakenCount;
2207 assert(L->getLoopLatch() && "Loop no longer in simplified form?");
2209 // If the exiting block is the same as the backedge block, we prefer to
2210 // compare against the post-incremented value, otherwise we must compare
2211 // against the preincremented value.
2212 if (L->getExitingBlock() == L->getLoopLatch()) {
2213 // Add one to the "backedge-taken" count to get the trip count.
2214 // This addition may overflow, which is valid as long as the comparison is
2215 // truncated to BackedgeTakenCount->getType().
2216 IVCount = SE->getAddExpr(BackedgeTakenCount,
2217 SE->getOne(BackedgeTakenCount->getType()));
2218 // The BackedgeTaken expression contains the number of times that the
2219 // backedge branches to the loop header. This is one less than the
2220 // number of times the loop executes, so use the incremented indvar.
2221 CmpIndVar = IndVar->getIncomingValueForBlock(L->getExitingBlock());
2224 Value *ExitCnt = genLoopLimit(IndVar, IVCount, L, Rewriter, SE);
2225 assert(ExitCnt->getType()->isPointerTy() ==
2226 IndVar->getType()->isPointerTy() &&
2227 "genLoopLimit missed a cast");
2229 // Insert a new icmp_ne or icmp_eq instruction before the branch.
2230 BranchInst *BI = cast<BranchInst>(L->getExitingBlock()->getTerminator());
2231 ICmpInst::Predicate P;
2232 if (L->contains(BI->getSuccessor(0)))
2233 P = ICmpInst::ICMP_NE;
2235 P = ICmpInst::ICMP_EQ;
2237 LLVM_DEBUG(dbgs() << "INDVARS: Rewriting loop exit condition to:\n"
2238 << " LHS:" << *CmpIndVar << '\n'
2239 << " op:\t" << (P == ICmpInst::ICMP_NE ? "!=" : "==")
2241 << " RHS:\t" << *ExitCnt << "\n"
2242 << " IVCount:\t" << *IVCount << "\n");
2244 IRBuilder<> Builder(BI);
2246 // The new loop exit condition should reuse the debug location of the
2247 // original loop exit condition.
2248 if (auto *Cond = dyn_cast<Instruction>(BI->getCondition()))
2249 Builder.SetCurrentDebugLocation(Cond->getDebugLoc());
2251 // LFTR can ignore IV overflow and truncate to the width of
2252 // BECount. This avoids materializing the add(zext(add)) expression.
2253 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->getType());
2254 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->getType());
2255 if (CmpIndVarSize > ExitCntSize) {
2256 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IndVar));
2257 const SCEV *ARStart = AR->getStart();
2258 const SCEV *ARStep = AR->getStepRecurrence(*SE);
2259 // For constant IVCount, avoid truncation.
2260 if (isa<SCEVConstant>(ARStart) && isa<SCEVConstant>(IVCount)) {
2261 const APInt &Start = cast<SCEVConstant>(ARStart)->getAPInt();
2262 APInt Count = cast<SCEVConstant>(IVCount)->getAPInt();
2263 // Note that the post-inc value of BackedgeTakenCount may have overflowed
2264 // above such that IVCount is now zero.
2265 if (IVCount != BackedgeTakenCount && Count == 0) {
2266 Count = APInt::getMaxValue(Count.getBitWidth()).zext(CmpIndVarSize);
2270 Count = Count.zext(CmpIndVarSize);
2272 if (cast<SCEVConstant>(ARStep)->getValue()->isNegative())
2273 NewLimit = Start - Count;
2275 NewLimit = Start + Count;
2276 ExitCnt = ConstantInt::get(CmpIndVar->getType(), NewLimit);
2278 LLVM_DEBUG(dbgs() << " Widen RHS:\t" << *ExitCnt << "\n");
2280 // We try to extend trip count first. If that doesn't work we truncate IV.
2281 // Zext(trunc(IV)) == IV implies equivalence of the following two:
2282 // Trunc(IV) == ExitCnt and IV == zext(ExitCnt). Similarly for sext. If
2283 // one of the two holds, extend the trip count, otherwise we truncate IV.
2284 bool Extended = false;
2285 const SCEV *IV = SE->getSCEV(CmpIndVar);
2286 const SCEV *ZExtTrunc =
2287 SE->getZeroExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2288 ExitCnt->getType()),
2289 CmpIndVar->getType());
2291 if (ZExtTrunc == IV) {
2293 ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->getType(),
2296 const SCEV *SExtTrunc =
2297 SE->getSignExtendExpr(SE->getTruncateExpr(SE->getSCEV(CmpIndVar),
2298 ExitCnt->getType()),
2299 CmpIndVar->getType());
2300 if (SExtTrunc == IV) {
2302 ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->getType(),
2308 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->getType(),
2312 Value *Cond = Builder.CreateICmp(P, CmpIndVar, ExitCnt, "exitcond");
2313 Value *OrigCond = BI->getCondition();
2314 // It's tempting to use replaceAllUsesWith here to fully replace the old
2315 // comparison, but that's not immediately safe, since users of the old
2316 // comparison may not be dominated by the new comparison. Instead, just
2317 // update the branch to use the new comparison; in the common case this
2318 // will make old comparison dead.
2319 BI->setCondition(Cond);
2320 DeadInsts.push_back(OrigCond);
2327 //===----------------------------------------------------------------------===//
2328 // sinkUnusedInvariants. A late subpass to cleanup loop preheaders.
2329 //===----------------------------------------------------------------------===//
2331 /// If there's a single exit block, sink any loop-invariant values that
2332 /// were defined in the preheader but not used inside the loop into the
2333 /// exit block to reduce register pressure in the loop.
2334 void IndVarSimplify::sinkUnusedInvariants(Loop *L) {
2335 BasicBlock *ExitBlock = L->getExitBlock();
2336 if (!ExitBlock) return;
2338 BasicBlock *Preheader = L->getLoopPreheader();
2339 if (!Preheader) return;
2341 BasicBlock::iterator InsertPt = ExitBlock->getFirstInsertionPt();
2342 BasicBlock::iterator I(Preheader->getTerminator());
2343 while (I != Preheader->begin()) {
2345 // New instructions were inserted at the end of the preheader.
2346 if (isa<PHINode>(I))
2349 // Don't move instructions which might have side effects, since the side
2350 // effects need to complete before instructions inside the loop. Also don't
2351 // move instructions which might read memory, since the loop may modify
2352 // memory. Note that it's okay if the instruction might have undefined
2353 // behavior: LoopSimplify guarantees that the preheader dominates the exit
2355 if (I->mayHaveSideEffects() || I->mayReadFromMemory())
2358 // Skip debug info intrinsics.
2359 if (isa<DbgInfoIntrinsic>(I))
2362 // Skip eh pad instructions.
2366 // Don't sink alloca: we never want to sink static alloca's out of the
2367 // entry block, and correctly sinking dynamic alloca's requires
2368 // checks for stacksave/stackrestore intrinsics.
2369 // FIXME: Refactor this check somehow?
2370 if (isa<AllocaInst>(I))
2373 // Determine if there is a use in or before the loop (direct or
2375 bool UsedInLoop = false;
2376 for (Use &U : I->uses()) {
2377 Instruction *User = cast<Instruction>(U.getUser());
2378 BasicBlock *UseBB = User->getParent();
2379 if (PHINode *P = dyn_cast<PHINode>(User)) {
2381 PHINode::getIncomingValueNumForOperand(U.getOperandNo());
2382 UseBB = P->getIncomingBlock(i);
2384 if (UseBB == Preheader || L->contains(UseBB)) {
2390 // If there is, the def must remain in the preheader.
2394 // Otherwise, sink it to the exit block.
2395 Instruction *ToMove = &*I;
2398 if (I != Preheader->begin()) {
2399 // Skip debug info intrinsics.
2402 } while (isa<DbgInfoIntrinsic>(I) && I != Preheader->begin());
2404 if (isa<DbgInfoIntrinsic>(I) && I == Preheader->begin())
2410 ToMove->moveBefore(*ExitBlock, InsertPt);
2412 InsertPt = ToMove->getIterator();
2416 //===----------------------------------------------------------------------===//
2417 // IndVarSimplify driver. Manage several subpasses of IV simplification.
2418 //===----------------------------------------------------------------------===//
2420 bool IndVarSimplify::run(Loop *L) {
2421 // We need (and expect!) the incoming loop to be in LCSSA.
2422 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2423 "LCSSA required to run indvars!");
2425 // If LoopSimplify form is not available, stay out of trouble. Some notes:
2426 // - LSR currently only supports LoopSimplify-form loops. Indvars'
2427 // canonicalization can be a pessimization without LSR to "clean up"
2429 // - We depend on having a preheader; in particular,
2430 // Loop::getCanonicalInductionVariable only supports loops with preheaders,
2431 // and we're in trouble if we can't find the induction variable even when
2432 // we've manually inserted one.
2433 // - LFTR relies on having a single backedge.
2434 if (!L->isLoopSimplifyForm())
2437 // If there are any floating-point recurrences, attempt to
2438 // transform them to use integer recurrences.
2439 rewriteNonIntegerIVs(L);
2441 const SCEV *BackedgeTakenCount = SE->getBackedgeTakenCount(L);
2443 // Create a rewriter object which we'll use to transform the code with.
2444 SCEVExpander Rewriter(*SE, DL, "indvars");
2446 Rewriter.setDebugType(DEBUG_TYPE);
2449 // Eliminate redundant IV users.
2451 // Simplification works best when run before other consumers of SCEV. We
2452 // attempt to avoid evaluating SCEVs for sign/zero extend operations until
2453 // other expressions involving loop IVs have been evaluated. This helps SCEV
2454 // set no-wrap flags before normalizing sign/zero extension.
2455 Rewriter.disableCanonicalMode();
2456 simplifyAndExtend(L, Rewriter, LI);
2458 // Check to see if this loop has a computable loop-invariant execution count.
2459 // If so, this means that we can compute the final value of any expressions
2460 // that are recurrent in the loop, and substitute the exit values from the
2461 // loop into any instructions outside of the loop that use the final values of
2462 // the current expressions.
2464 if (ReplaceExitValue != NeverRepl &&
2465 !isa<SCEVCouldNotCompute>(BackedgeTakenCount))
2466 rewriteLoopExitValues(L, Rewriter);
2468 // Eliminate redundant IV cycles.
2469 NumElimIV += Rewriter.replaceCongruentIVs(L, DT, DeadInsts);
2471 // If we have a trip count expression, rewrite the loop's exit condition
2472 // using it. We can currently only handle loops with a single exit.
2473 if (!DisableLFTR && canExpandBackedgeTakenCount(L, SE, Rewriter) &&
2475 PHINode *IndVar = FindLoopCounter(L, BackedgeTakenCount, SE, DT);
2477 // Check preconditions for proper SCEVExpander operation. SCEV does not
2478 // express SCEVExpander's dependencies, such as LoopSimplify. Instead any
2479 // pass that uses the SCEVExpander must do it. This does not work well for
2480 // loop passes because SCEVExpander makes assumptions about all loops,
2481 // while LoopPassManager only forces the current loop to be simplified.
2483 // FIXME: SCEV expansion has no way to bail out, so the caller must
2484 // explicitly check any assumptions made by SCEV. Brittle.
2485 const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(BackedgeTakenCount);
2486 if (!AR || AR->getLoop()->getLoopPreheader())
2487 (void)linearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
2491 // Clear the rewriter cache, because values that are in the rewriter's cache
2492 // can be deleted in the loop below, causing the AssertingVH in the cache to
2496 // Now that we're done iterating through lists, clean up any instructions
2497 // which are now dead.
2498 while (!DeadInsts.empty())
2499 if (Instruction *Inst =
2500 dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val()))
2501 RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
2503 // The Rewriter may not be used from this point on.
2505 // Loop-invariant instructions in the preheader that aren't used in the
2506 // loop may be sunk below the loop to reduce register pressure.
2507 sinkUnusedInvariants(L);
2509 // rewriteFirstIterationLoopExitValues does not rely on the computation of
2510 // trip count and therefore can further simplify exit values in addition to
2511 // rewriteLoopExitValues.
2512 rewriteFirstIterationLoopExitValues(L);
2514 // Clean up dead instructions.
2515 Changed |= DeleteDeadPHIs(L->getHeader(), TLI);
2517 // Check a post-condition.
2518 assert(L->isRecursivelyLCSSAForm(*DT, *LI) &&
2519 "Indvars did not preserve LCSSA!");
2521 // Verify that LFTR, and any other change have not interfered with SCEV's
2522 // ability to compute trip count.
2524 if (VerifyIndvars && !isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
2526 const SCEV *NewBECount = SE->getBackedgeTakenCount(L);
2527 if (SE->getTypeSizeInBits(BackedgeTakenCount->getType()) <
2528 SE->getTypeSizeInBits(NewBECount->getType()))
2529 NewBECount = SE->getTruncateOrNoop(NewBECount,
2530 BackedgeTakenCount->getType());
2532 BackedgeTakenCount = SE->getTruncateOrNoop(BackedgeTakenCount,
2533 NewBECount->getType());
2534 assert(BackedgeTakenCount == NewBECount && "indvars must preserve SCEV");
2541 PreservedAnalyses IndVarSimplifyPass::run(Loop &L, LoopAnalysisManager &AM,
2542 LoopStandardAnalysisResults &AR,
2544 Function *F = L.getHeader()->getParent();
2545 const DataLayout &DL = F->getParent()->getDataLayout();
2547 IndVarSimplify IVS(&AR.LI, &AR.SE, &AR.DT, DL, &AR.TLI, &AR.TTI);
2549 return PreservedAnalyses::all();
2551 auto PA = getLoopPassPreservedAnalyses();
2552 PA.preserveSet<CFGAnalyses>();
2558 struct IndVarSimplifyLegacyPass : public LoopPass {
2559 static char ID; // Pass identification, replacement for typeid
2561 IndVarSimplifyLegacyPass() : LoopPass(ID) {
2562 initializeIndVarSimplifyLegacyPassPass(*PassRegistry::getPassRegistry());
2565 bool runOnLoop(Loop *L, LPPassManager &LPM) override {
2569 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2570 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2571 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2572 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
2573 auto *TLI = TLIP ? &TLIP->getTLI() : nullptr;
2574 auto *TTIP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
2575 auto *TTI = TTIP ? &TTIP->getTTI(*L->getHeader()->getParent()) : nullptr;
2576 const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
2578 IndVarSimplify IVS(LI, SE, DT, DL, TLI, TTI);
2582 void getAnalysisUsage(AnalysisUsage &AU) const override {
2583 AU.setPreservesCFG();
2584 getLoopAnalysisUsage(AU);
2588 } // end anonymous namespace
2590 char IndVarSimplifyLegacyPass::ID = 0;
2592 INITIALIZE_PASS_BEGIN(IndVarSimplifyLegacyPass, "indvars",
2593 "Induction Variable Simplification", false, false)
2594 INITIALIZE_PASS_DEPENDENCY(LoopPass)
2595 INITIALIZE_PASS_END(IndVarSimplifyLegacyPass, "indvars",
2596 "Induction Variable Simplification", false, false)
2598 Pass *llvm::createIndVarSimplifyPass() {
2599 return new IndVarSimplifyLegacyPass();