1 //===-- SimplifyIndVar.cpp - Induction variable simplification ------------===//
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 file implements induction variable simplification. It does
11 // not define any actual pass or policy, but provides a single function to
12 // simplify a loop's induction variables based on ScalarEvolution.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Transforms/Utils/SimplifyIndVar.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/IVUsers.h"
21 #include "llvm/Analysis/LoopInfo.h"
22 #include "llvm/Analysis/LoopPass.h"
23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/Dominators.h"
26 #include "llvm/IR/IRBuilder.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
35 #define DEBUG_TYPE "indvars"
37 STATISTIC(NumElimIdentity
, "Number of IV identities eliminated");
38 STATISTIC(NumElimOperand
, "Number of IV operands folded into a use");
39 STATISTIC(NumElimRem
, "Number of IV remainder operations eliminated");
40 STATISTIC(NumElimCmp
, "Number of IV comparisons eliminated");
43 /// This is a utility for simplifying induction variables
44 /// based on ScalarEvolution. It is the primary instrument of the
45 /// IndvarSimplify pass, but it may also be directly invoked to cleanup after
46 /// other loop passes that preserve SCEV.
47 class SimplifyIndvar
{
51 const DataLayout
*DL
; // May be NULL
53 SmallVectorImpl
<WeakVH
> &DeadInsts
;
58 SimplifyIndvar(Loop
*Loop
, ScalarEvolution
*SE
, LPPassManager
*LPM
,
59 SmallVectorImpl
<WeakVH
> &Dead
, IVUsers
*IVU
= nullptr) :
61 LI(LPM
->getAnalysisIfAvailable
<LoopInfo
>()),
65 DataLayoutPass
*DLP
= LPM
->getAnalysisIfAvailable
<DataLayoutPass
>();
66 DL
= DLP
? &DLP
->getDataLayout() : nullptr;
67 assert(LI
&& "IV simplification requires LoopInfo");
70 bool hasChanged() const { return Changed
; }
72 /// Iteratively perform simplification on a worklist of users of the
73 /// specified induction variable. This is the top-level driver that applies
74 /// all simplicitions to users of an IV.
75 void simplifyUsers(PHINode
*CurrIV
, IVVisitor
*V
= nullptr);
77 Value
*foldIVUser(Instruction
*UseInst
, Instruction
*IVOperand
);
79 bool eliminateIVUser(Instruction
*UseInst
, Instruction
*IVOperand
);
80 void eliminateIVComparison(ICmpInst
*ICmp
, Value
*IVOperand
);
81 void eliminateIVRemainder(BinaryOperator
*Rem
, Value
*IVOperand
,
83 bool strengthenOverflowingOperation(BinaryOperator
*OBO
, Value
*IVOperand
);
85 Instruction
*splitOverflowIntrinsic(Instruction
*IVUser
,
86 const DominatorTree
*DT
);
90 /// Fold an IV operand into its use. This removes increments of an
91 /// aligned IV when used by a instruction that ignores the low bits.
93 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
95 /// Return the operand of IVOperand for this induction variable if IVOperand can
96 /// be folded (in case more folding opportunities have been exposed).
97 /// Otherwise return null.
98 Value
*SimplifyIndvar::foldIVUser(Instruction
*UseInst
, Instruction
*IVOperand
) {
99 Value
*IVSrc
= nullptr;
100 unsigned OperIdx
= 0;
101 const SCEV
*FoldedExpr
= nullptr;
102 switch (UseInst
->getOpcode()) {
105 case Instruction::UDiv
:
106 case Instruction::LShr
:
107 // We're only interested in the case where we know something about
108 // the numerator and have a constant denominator.
109 if (IVOperand
!= UseInst
->getOperand(OperIdx
) ||
110 !isa
<ConstantInt
>(UseInst
->getOperand(1)))
113 // Attempt to fold a binary operator with constant operand.
114 // e.g. ((I + 1) >> 2) => I >> 2
115 if (!isa
<BinaryOperator
>(IVOperand
)
116 || !isa
<ConstantInt
>(IVOperand
->getOperand(1)))
119 IVSrc
= IVOperand
->getOperand(0);
120 // IVSrc must be the (SCEVable) IV, since the other operand is const.
121 assert(SE
->isSCEVable(IVSrc
->getType()) && "Expect SCEVable IV operand");
123 ConstantInt
*D
= cast
<ConstantInt
>(UseInst
->getOperand(1));
124 if (UseInst
->getOpcode() == Instruction::LShr
) {
125 // Get a constant for the divisor. See createSCEV.
126 uint32_t BitWidth
= cast
<IntegerType
>(UseInst
->getType())->getBitWidth();
127 if (D
->getValue().uge(BitWidth
))
130 D
= ConstantInt::get(UseInst
->getContext(),
131 APInt::getOneBitSet(BitWidth
, D
->getZExtValue()));
133 FoldedExpr
= SE
->getUDivExpr(SE
->getSCEV(IVSrc
), SE
->getSCEV(D
));
135 // We have something that might fold it's operand. Compare SCEVs.
136 if (!SE
->isSCEVable(UseInst
->getType()))
139 // Bypass the operand if SCEV can prove it has no effect.
140 if (SE
->getSCEV(UseInst
) != FoldedExpr
)
143 DEBUG(dbgs() << "INDVARS: Eliminated IV operand: " << *IVOperand
144 << " -> " << *UseInst
<< '\n');
146 UseInst
->setOperand(OperIdx
, IVSrc
);
147 assert(SE
->getSCEV(UseInst
) == FoldedExpr
&& "bad SCEV with folded oper");
151 if (IVOperand
->use_empty())
152 DeadInsts
.push_back(IVOperand
);
156 /// SimplifyIVUsers helper for eliminating useless
157 /// comparisons against an induction variable.
158 void SimplifyIndvar::eliminateIVComparison(ICmpInst
*ICmp
, Value
*IVOperand
) {
159 unsigned IVOperIdx
= 0;
160 ICmpInst::Predicate Pred
= ICmp
->getPredicate();
161 if (IVOperand
!= ICmp
->getOperand(0)) {
163 assert(IVOperand
== ICmp
->getOperand(1) && "Can't find IVOperand");
165 Pred
= ICmpInst::getSwappedPredicate(Pred
);
168 // Get the SCEVs for the ICmp operands.
169 const SCEV
*S
= SE
->getSCEV(ICmp
->getOperand(IVOperIdx
));
170 const SCEV
*X
= SE
->getSCEV(ICmp
->getOperand(1 - IVOperIdx
));
172 // Simplify unnecessary loops away.
173 const Loop
*ICmpLoop
= LI
->getLoopFor(ICmp
->getParent());
174 S
= SE
->getSCEVAtScope(S
, ICmpLoop
);
175 X
= SE
->getSCEVAtScope(X
, ICmpLoop
);
177 // If the condition is always true or always false, replace it with
179 if (SE
->isKnownPredicate(Pred
, S
, X
))
180 ICmp
->replaceAllUsesWith(ConstantInt::getTrue(ICmp
->getContext()));
181 else if (SE
->isKnownPredicate(ICmpInst::getInversePredicate(Pred
), S
, X
))
182 ICmp
->replaceAllUsesWith(ConstantInt::getFalse(ICmp
->getContext()));
186 DEBUG(dbgs() << "INDVARS: Eliminated comparison: " << *ICmp
<< '\n');
189 DeadInsts
.push_back(ICmp
);
192 /// SimplifyIVUsers helper for eliminating useless
193 /// remainder operations operating on an induction variable.
194 void SimplifyIndvar::eliminateIVRemainder(BinaryOperator
*Rem
,
197 // We're only interested in the case where we know something about
199 if (IVOperand
!= Rem
->getOperand(0))
202 // Get the SCEVs for the ICmp operands.
203 const SCEV
*S
= SE
->getSCEV(Rem
->getOperand(0));
204 const SCEV
*X
= SE
->getSCEV(Rem
->getOperand(1));
206 // Simplify unnecessary loops away.
207 const Loop
*ICmpLoop
= LI
->getLoopFor(Rem
->getParent());
208 S
= SE
->getSCEVAtScope(S
, ICmpLoop
);
209 X
= SE
->getSCEVAtScope(X
, ICmpLoop
);
211 // i % n --> i if i is in [0,n).
212 if ((!IsSigned
|| SE
->isKnownNonNegative(S
)) &&
213 SE
->isKnownPredicate(IsSigned
? ICmpInst::ICMP_SLT
: ICmpInst::ICMP_ULT
,
215 Rem
->replaceAllUsesWith(Rem
->getOperand(0));
217 // (i+1) % n --> (i+1)==n?0:(i+1) if i is in [0,n).
218 const SCEV
*LessOne
=
219 SE
->getMinusSCEV(S
, SE
->getConstant(S
->getType(), 1));
220 if (IsSigned
&& !SE
->isKnownNonNegative(LessOne
))
223 if (!SE
->isKnownPredicate(IsSigned
?
224 ICmpInst::ICMP_SLT
: ICmpInst::ICMP_ULT
,
228 ICmpInst
*ICmp
= new ICmpInst(Rem
, ICmpInst::ICMP_EQ
,
229 Rem
->getOperand(0), Rem
->getOperand(1));
231 SelectInst::Create(ICmp
,
232 ConstantInt::get(Rem
->getType(), 0),
233 Rem
->getOperand(0), "tmp", Rem
);
234 Rem
->replaceAllUsesWith(Sel
);
237 DEBUG(dbgs() << "INDVARS: Simplified rem: " << *Rem
<< '\n');
240 DeadInsts
.push_back(Rem
);
243 /// Eliminate an operation that consumes a simple IV and has
244 /// no observable side-effect given the range of IV values.
245 /// IVOperand is guaranteed SCEVable, but UseInst may not be.
246 bool SimplifyIndvar::eliminateIVUser(Instruction
*UseInst
,
247 Instruction
*IVOperand
) {
248 if (ICmpInst
*ICmp
= dyn_cast
<ICmpInst
>(UseInst
)) {
249 eliminateIVComparison(ICmp
, IVOperand
);
252 if (BinaryOperator
*Rem
= dyn_cast
<BinaryOperator
>(UseInst
)) {
253 bool IsSigned
= Rem
->getOpcode() == Instruction::SRem
;
254 if (IsSigned
|| Rem
->getOpcode() == Instruction::URem
) {
255 eliminateIVRemainder(Rem
, IVOperand
, IsSigned
);
260 // Eliminate any operation that SCEV can prove is an identity function.
261 if (!SE
->isSCEVable(UseInst
->getType()) ||
262 (UseInst
->getType() != IVOperand
->getType()) ||
263 (SE
->getSCEV(UseInst
) != SE
->getSCEV(IVOperand
)))
266 DEBUG(dbgs() << "INDVARS: Eliminated identity: " << *UseInst
<< '\n');
268 UseInst
->replaceAllUsesWith(IVOperand
);
271 DeadInsts
.push_back(UseInst
);
275 /// Annotate BO with nsw / nuw if it provably does not signed-overflow /
276 /// unsigned-overflow. Returns true if anything changed, false otherwise.
277 bool SimplifyIndvar::strengthenOverflowingOperation(BinaryOperator
*BO
,
280 // Currently we only handle instructions of the form "add <indvar> <value>"
281 unsigned Op
= BO
->getOpcode();
282 if (Op
!= Instruction::Add
)
285 // If BO is already both nuw and nsw then there is nothing left to do
286 if (BO
->hasNoUnsignedWrap() && BO
->hasNoSignedWrap())
289 IntegerType
*IT
= cast
<IntegerType
>(IVOperand
->getType());
290 Value
*OtherOperand
= nullptr;
291 int OtherOperandIdx
= -1;
292 if (BO
->getOperand(0) == IVOperand
) {
293 OtherOperand
= BO
->getOperand(1);
296 assert(BO
->getOperand(1) == IVOperand
&& "only other use!");
297 OtherOperand
= BO
->getOperand(0);
301 bool Changed
= false;
302 const SCEV
*OtherOpSCEV
= SE
->getSCEV(OtherOperand
);
303 if (OtherOpSCEV
== SE
->getCouldNotCompute())
306 const SCEV
*IVOpSCEV
= SE
->getSCEV(IVOperand
);
307 const SCEV
*ZeroSCEV
= SE
->getConstant(IVOpSCEV
->getType(), 0);
309 if (!BO
->hasNoSignedWrap()) {
310 // Upgrade the add to an "add nsw" if we can prove that it will never
311 // sign-overflow or sign-underflow.
313 const SCEV
*SignedMax
=
314 SE
->getConstant(APInt::getSignedMaxValue(IT
->getBitWidth()));
315 const SCEV
*SignedMin
=
316 SE
->getConstant(APInt::getSignedMinValue(IT
->getBitWidth()));
318 // The addition "IVOperand + OtherOp" does not sign-overflow if the result
319 // is sign-representable in 2's complement in the given bit-width.
321 // If OtherOp is SLT 0, then for an IVOperand in [SignedMin - OtherOp,
322 // SignedMax], "IVOperand + OtherOp" is in [SignedMin, SignedMax + OtherOp].
323 // Everything in [SignedMin, SignedMax + OtherOp] is representable since
324 // SignedMax + OtherOp is at least -1.
326 // If OtherOp is SGE 0, then for an IVOperand in [SignedMin, SignedMax -
327 // OtherOp], "IVOperand + OtherOp" is in [SignedMin + OtherOp, SignedMax].
328 // Everything in [SignedMin + OtherOp, SignedMax] is representable since
329 // SignedMin + OtherOp is at most -1.
331 // It follows that for all values of IVOperand in [SignedMin - smin(0,
332 // OtherOp), SignedMax - smax(0, OtherOp)] the result of the add is
333 // representable (i.e. there is no sign-overflow).
335 const SCEV
*UpperDelta
= SE
->getSMaxExpr(ZeroSCEV
, OtherOpSCEV
);
336 const SCEV
*UpperLimit
= SE
->getMinusSCEV(SignedMax
, UpperDelta
);
338 bool NeverSignedOverflows
=
339 SE
->isKnownPredicate(ICmpInst::ICMP_SLE
, IVOpSCEV
, UpperLimit
);
341 if (NeverSignedOverflows
) {
342 const SCEV
*LowerDelta
= SE
->getSMinExpr(ZeroSCEV
, OtherOpSCEV
);
343 const SCEV
*LowerLimit
= SE
->getMinusSCEV(SignedMin
, LowerDelta
);
345 bool NeverSignedUnderflows
=
346 SE
->isKnownPredicate(ICmpInst::ICMP_SGE
, IVOpSCEV
, LowerLimit
);
347 if (NeverSignedUnderflows
) {
348 BO
->setHasNoSignedWrap(true);
354 if (!BO
->hasNoUnsignedWrap()) {
355 // Upgrade the add computing "IVOperand + OtherOp" to an "add nuw" if we can
356 // prove that it will never unsigned-overflow (i.e. the result will always
357 // be representable in the given bit-width).
359 // "IVOperand + OtherOp" is unsigned-representable in 2's complement iff it
360 // does not produce a carry. "IVOperand + OtherOp" produces no carry iff
361 // IVOperand ULE (UnsignedMax - OtherOp).
363 const SCEV
*UnsignedMax
=
364 SE
->getConstant(APInt::getMaxValue(IT
->getBitWidth()));
365 const SCEV
*UpperLimit
= SE
->getMinusSCEV(UnsignedMax
, OtherOpSCEV
);
367 bool NeverUnsignedOverflows
=
368 SE
->isKnownPredicate(ICmpInst::ICMP_ULE
, IVOpSCEV
, UpperLimit
);
370 if (NeverUnsignedOverflows
) {
371 BO
->setHasNoUnsignedWrap(true);
379 /// \brief Split sadd.with.overflow into add + sadd.with.overflow to allow
380 /// analysis and optimization.
382 /// \return A new value representing the non-overflowing add if possible,
383 /// otherwise return the original value.
384 Instruction
*SimplifyIndvar::splitOverflowIntrinsic(Instruction
*IVUser
,
385 const DominatorTree
*DT
) {
386 IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(IVUser
);
387 if (!II
|| II
->getIntrinsicID() != Intrinsic::sadd_with_overflow
)
390 // Find a branch guarded by the overflow check.
391 BranchInst
*Branch
= nullptr;
392 Instruction
*AddVal
= nullptr;
393 for (User
*U
: II
->users()) {
394 if (ExtractValueInst
*ExtractInst
= dyn_cast
<ExtractValueInst
>(U
)) {
395 if (ExtractInst
->getNumIndices() != 1)
397 if (ExtractInst
->getIndices()[0] == 0)
398 AddVal
= ExtractInst
;
399 else if (ExtractInst
->getIndices()[0] == 1 && ExtractInst
->hasOneUse())
400 Branch
= dyn_cast
<BranchInst
>(ExtractInst
->user_back());
403 if (!AddVal
|| !Branch
)
406 BasicBlock
*ContinueBB
= Branch
->getSuccessor(1);
407 if (std::next(pred_begin(ContinueBB
)) != pred_end(ContinueBB
))
410 // Check if all users of the add are provably NSW.
412 for (Use
&U
: AddVal
->uses()) {
413 if (Instruction
*UseInst
= dyn_cast
<Instruction
>(U
.getUser())) {
414 BasicBlock
*UseBB
= UseInst
->getParent();
415 if (PHINode
*PHI
= dyn_cast
<PHINode
>(UseInst
))
416 UseBB
= PHI
->getIncomingBlock(U
);
417 if (!DT
->dominates(ContinueBB
, UseBB
)) {
427 IRBuilder
<> Builder(IVUser
);
428 Instruction
*AddInst
= dyn_cast
<Instruction
>(
429 Builder
.CreateNSWAdd(II
->getOperand(0), II
->getOperand(1)));
431 // The caller expects the new add to have the same form as the intrinsic. The
432 // IV operand position must be the same.
433 assert((AddInst
->getOpcode() == Instruction::Add
&&
434 AddInst
->getOperand(0) == II
->getOperand(0)) &&
435 "Bad add instruction created from overflow intrinsic.");
437 AddVal
->replaceAllUsesWith(AddInst
);
438 DeadInsts
.push_back(AddVal
);
442 /// Add all uses of Def to the current IV's worklist.
443 static void pushIVUsers(
445 SmallPtrSet
<Instruction
*,16> &Simplified
,
446 SmallVectorImpl
< std::pair
<Instruction
*,Instruction
*> > &SimpleIVUsers
) {
448 for (User
*U
: Def
->users()) {
449 Instruction
*UI
= cast
<Instruction
>(U
);
451 // Avoid infinite or exponential worklist processing.
452 // Also ensure unique worklist users.
453 // If Def is a LoopPhi, it may not be in the Simplified set, so check for
455 if (UI
!= Def
&& Simplified
.insert(UI
).second
)
456 SimpleIVUsers
.push_back(std::make_pair(UI
, Def
));
460 /// Return true if this instruction generates a simple SCEV
461 /// expression in terms of that IV.
463 /// This is similar to IVUsers' isInteresting() but processes each instruction
464 /// non-recursively when the operand is already known to be a simpleIVUser.
466 static bool isSimpleIVUser(Instruction
*I
, const Loop
*L
, ScalarEvolution
*SE
) {
467 if (!SE
->isSCEVable(I
->getType()))
470 // Get the symbolic expression for this instruction.
471 const SCEV
*S
= SE
->getSCEV(I
);
473 // Only consider affine recurrences.
474 const SCEVAddRecExpr
*AR
= dyn_cast
<SCEVAddRecExpr
>(S
);
475 if (AR
&& AR
->getLoop() == L
)
481 /// Iteratively perform simplification on a worklist of users
482 /// of the specified induction variable. Each successive simplification may push
483 /// more users which may themselves be candidates for simplification.
485 /// This algorithm does not require IVUsers analysis. Instead, it simplifies
486 /// instructions in-place during analysis. Rather than rewriting induction
487 /// variables bottom-up from their users, it transforms a chain of IVUsers
488 /// top-down, updating the IR only when it encouters a clear optimization
491 /// Once DisableIVRewrite is default, LSR will be the only client of IVUsers.
493 void SimplifyIndvar::simplifyUsers(PHINode
*CurrIV
, IVVisitor
*V
) {
494 if (!SE
->isSCEVable(CurrIV
->getType()))
497 // Instructions processed by SimplifyIndvar for CurrIV.
498 SmallPtrSet
<Instruction
*,16> Simplified
;
500 // Use-def pairs if IV users waiting to be processed for CurrIV.
501 SmallVector
<std::pair
<Instruction
*, Instruction
*>, 8> SimpleIVUsers
;
503 // Push users of the current LoopPhi. In rare cases, pushIVUsers may be
504 // called multiple times for the same LoopPhi. This is the proper thing to
505 // do for loop header phis that use each other.
506 pushIVUsers(CurrIV
, Simplified
, SimpleIVUsers
);
508 while (!SimpleIVUsers
.empty()) {
509 std::pair
<Instruction
*, Instruction
*> UseOper
=
510 SimpleIVUsers
.pop_back_val();
511 Instruction
*UseInst
= UseOper
.first
;
513 // Bypass back edges to avoid extra work.
514 if (UseInst
== CurrIV
) continue;
516 if (V
&& V
->shouldSplitOverflowInstrinsics()) {
517 UseInst
= splitOverflowIntrinsic(UseInst
, V
->getDomTree());
522 Instruction
*IVOperand
= UseOper
.second
;
523 for (unsigned N
= 0; IVOperand
; ++N
) {
524 assert(N
<= Simplified
.size() && "runaway iteration");
526 Value
*NewOper
= foldIVUser(UseOper
.first
, IVOperand
);
528 break; // done folding
529 IVOperand
= dyn_cast
<Instruction
>(NewOper
);
534 if (eliminateIVUser(UseOper
.first
, IVOperand
)) {
535 pushIVUsers(IVOperand
, Simplified
, SimpleIVUsers
);
539 if (BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(UseOper
.first
)) {
540 if (isa
<OverflowingBinaryOperator
>(BO
) &&
541 strengthenOverflowingOperation(BO
, IVOperand
)) {
542 // re-queue uses of the now modified binary operator and fall
543 // through to the checks that remain.
544 pushIVUsers(IVOperand
, Simplified
, SimpleIVUsers
);
548 CastInst
*Cast
= dyn_cast
<CastInst
>(UseOper
.first
);
553 if (isSimpleIVUser(UseOper
.first
, L
, SE
)) {
554 pushIVUsers(UseOper
.first
, Simplified
, SimpleIVUsers
);
561 void IVVisitor::anchor() { }
563 /// Simplify instructions that use this induction variable
564 /// by using ScalarEvolution to analyze the IV's recurrence.
565 bool simplifyUsersOfIV(PHINode
*CurrIV
, ScalarEvolution
*SE
, LPPassManager
*LPM
,
566 SmallVectorImpl
<WeakVH
> &Dead
, IVVisitor
*V
)
568 LoopInfo
*LI
= &LPM
->getAnalysis
<LoopInfo
>();
569 SimplifyIndvar
SIV(LI
->getLoopFor(CurrIV
->getParent()), SE
, LPM
, Dead
);
570 SIV
.simplifyUsers(CurrIV
, V
);
571 return SIV
.hasChanged();
574 /// Simplify users of induction variables within this
575 /// loop. This does not actually change or add IVs.
576 bool simplifyLoopIVs(Loop
*L
, ScalarEvolution
*SE
, LPPassManager
*LPM
,
577 SmallVectorImpl
<WeakVH
> &Dead
) {
578 bool Changed
= false;
579 for (BasicBlock::iterator I
= L
->getHeader()->begin(); isa
<PHINode
>(I
); ++I
) {
580 Changed
|= simplifyUsersOfIV(cast
<PHINode
>(I
), SE
, LPM
, Dead
);