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 // This transformation makes the following changes to each loop with an
15 // identifiable induction variable:
16 // 1. All loops are transformed to have a SINGLE canonical induction variable
17 // which starts at zero and steps by one.
18 // 2. The canonical induction variable is guaranteed to be the first PHI node
19 // in the loop header block.
20 // 3. Any pointer arithmetic recurrences are raised to use array subscripts.
22 // If the trip count of a loop is computable, this pass also makes the following
24 // 1. The exit condition for the loop is canonicalized to compare the
25 // induction value against the exit value. This turns loops like:
26 // 'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'
27 // 2. Any use outside of the loop of an expression derived from the indvar
28 // is changed to compute the derived value outside of the loop, eliminating
29 // the dependence on the exit value of the induction variable. If the only
30 // purpose of the loop is to compute the exit value of some derived
31 // expression, this transformation will make the loop dead.
33 // This transformation should be followed by strength reduction after all of the
34 // desired loop transformations have been performed.
36 //===----------------------------------------------------------------------===//
38 #define DEBUG_TYPE "indvars"
39 #include "llvm/Transforms/Scalar.h"
40 #include "llvm/BasicBlock.h"
41 #include "llvm/Constants.h"
42 #include "llvm/Instructions.h"
43 #include "llvm/Type.h"
44 #include "llvm/Analysis/Dominators.h"
45 #include "llvm/Analysis/IVUsers.h"
46 #include "llvm/Analysis/ScalarEvolutionExpander.h"
47 #include "llvm/Analysis/LoopInfo.h"
48 #include "llvm/Analysis/LoopPass.h"
49 #include "llvm/Support/CFG.h"
50 #include "llvm/Support/Compiler.h"
51 #include "llvm/Support/Debug.h"
52 #include "llvm/Transforms/Utils/Local.h"
53 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
54 #include "llvm/Support/CommandLine.h"
55 #include "llvm/ADT/SmallVector.h"
56 #include "llvm/ADT/Statistic.h"
57 #include "llvm/ADT/STLExtras.h"
60 STATISTIC(NumRemoved , "Number of aux indvars removed");
61 STATISTIC(NumInserted, "Number of canonical indvars added");
62 STATISTIC(NumReplaced, "Number of exit values replaced");
63 STATISTIC(NumLFTR , "Number of loop exit tests replaced");
66 class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
73 static char ID; // Pass identification, replacement for typeid
74 IndVarSimplify() : LoopPass(&ID) {}
76 virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
78 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
79 AU.addRequired<DominatorTree>();
80 AU.addRequired<ScalarEvolution>();
81 AU.addRequiredID(LCSSAID);
82 AU.addRequiredID(LoopSimplifyID);
83 AU.addRequired<LoopInfo>();
84 AU.addRequired<IVUsers>();
85 AU.addPreserved<ScalarEvolution>();
86 AU.addPreservedID(LoopSimplifyID);
87 AU.addPreserved<IVUsers>();
88 AU.addPreservedID(LCSSAID);
94 void RewriteNonIntegerIVs(Loop *L);
96 ICmpInst *LinearFunctionTestReplace(Loop *L, SCEVHandle BackedgeTakenCount,
98 BasicBlock *ExitingBlock,
100 SCEVExpander &Rewriter);
101 void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount);
103 void RewriteIVExpressions(Loop *L, const Type *LargestType,
104 SCEVExpander &Rewriter);
106 void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter);
108 void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter);
110 void HandleFloatingPointIV(Loop *L, PHINode *PH);
114 char IndVarSimplify::ID = 0;
115 static RegisterPass<IndVarSimplify>
116 X("indvars", "Canonicalize Induction Variables");
118 Pass *llvm::createIndVarSimplifyPass() {
119 return new IndVarSimplify();
122 /// LinearFunctionTestReplace - This method rewrites the exit condition of the
123 /// loop to be a canonical != comparison against the incremented loop induction
124 /// variable. This pass is able to rewrite the exit tests of any loop where the
125 /// SCEV analysis can determine a loop-invariant trip count of the loop, which
126 /// is actually a much broader range than just linear tests.
127 ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
128 SCEVHandle BackedgeTakenCount,
130 BasicBlock *ExitingBlock,
132 SCEVExpander &Rewriter) {
133 // If the exiting block is not the same as the backedge block, we must compare
134 // against the preincremented value, otherwise we prefer to compare against
135 // the post-incremented value.
137 SCEVHandle RHS = BackedgeTakenCount;
138 if (ExitingBlock == L->getLoopLatch()) {
139 // Add one to the "backedge-taken" count to get the trip count.
140 // If this addition may overflow, we have to be more pessimistic and
141 // cast the induction variable before doing the add.
142 SCEVHandle Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
144 SE->getAddExpr(BackedgeTakenCount,
145 SE->getIntegerSCEV(1, BackedgeTakenCount->getType()));
146 if ((isa<SCEVConstant>(N) && !N->isZero()) ||
147 SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) {
148 // No overflow. Cast the sum.
149 RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType());
151 // Potential overflow. Cast before doing the add.
152 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
154 RHS = SE->getAddExpr(RHS,
155 SE->getIntegerSCEV(1, IndVar->getType()));
158 // The BackedgeTaken expression contains the number of times that the
159 // backedge branches to the loop header. This is one less than the
160 // number of times the loop executes, so use the incremented indvar.
161 CmpIndVar = L->getCanonicalInductionVariableIncrement();
163 // We have to use the preincremented value...
164 RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
169 // Expand the code for the iteration count into the preheader of the loop.
170 BasicBlock *Preheader = L->getLoopPreheader();
171 Value *ExitCnt = Rewriter.expandCodeFor(RHS, CmpIndVar->getType(),
172 Preheader->getTerminator());
174 // Insert a new icmp_ne or icmp_eq instruction before the branch.
175 ICmpInst::Predicate Opcode;
176 if (L->contains(BI->getSuccessor(0)))
177 Opcode = ICmpInst::ICMP_NE;
179 Opcode = ICmpInst::ICMP_EQ;
181 DOUT << "INDVARS: Rewriting loop exit condition to:\n"
182 << " LHS:" << *CmpIndVar // includes a newline
184 << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
185 << " RHS:\t" << *RHS << "\n";
187 ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
189 Instruction *OrigCond = cast<Instruction>(BI->getCondition());
190 // It's tempting to use replaceAllUsesWith here to fully replace the old
191 // comparison, but that's not immediately safe, since users of the old
192 // comparison may not be dominated by the new comparison. Instead, just
193 // update the branch to use the new comparison; in the common case this
194 // will make old comparison dead.
195 BI->setCondition(Cond);
196 RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
203 /// RewriteLoopExitValues - Check to see if this loop has a computable
204 /// loop-invariant execution count. If so, this means that we can compute the
205 /// final value of any expressions that are recurrent in the loop, and
206 /// substitute the exit values from the loop into any instructions outside of
207 /// the loop that use the final values of the current expressions.
209 /// This is mostly redundant with the regular IndVarSimplify activities that
210 /// happen later, except that it's more powerful in some cases, because it's
211 /// able to brute-force evaluate arbitrary instructions as long as they have
212 /// constant operands at the beginning of the loop.
213 void IndVarSimplify::RewriteLoopExitValues(Loop *L,
214 const SCEV *BackedgeTakenCount) {
215 // Verify the input to the pass in already in LCSSA form.
216 assert(L->isLCSSAForm());
218 BasicBlock *Preheader = L->getLoopPreheader();
220 // Scan all of the instructions in the loop, looking at those that have
221 // extra-loop users and which are recurrences.
222 SCEVExpander Rewriter(*SE);
224 // We insert the code into the preheader of the loop if the loop contains
225 // multiple exit blocks, or in the exit block if there is exactly one.
226 BasicBlock *BlockToInsertInto;
227 SmallVector<BasicBlock*, 8> ExitBlocks;
228 L->getUniqueExitBlocks(ExitBlocks);
229 if (ExitBlocks.size() == 1)
230 BlockToInsertInto = ExitBlocks[0];
232 BlockToInsertInto = Preheader;
233 BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
235 std::map<Instruction*, Value*> ExitValues;
237 // Find all values that are computed inside the loop, but used outside of it.
238 // Because of LCSSA, these values will only occur in LCSSA PHI Nodes. Scan
239 // the exit blocks of the loop to find them.
240 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
241 BasicBlock *ExitBB = ExitBlocks[i];
243 // If there are no PHI nodes in this exit block, then no values defined
244 // inside the loop are used on this path, skip it.
245 PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
248 unsigned NumPreds = PN->getNumIncomingValues();
250 // Iterate over all of the PHI nodes.
251 BasicBlock::iterator BBI = ExitBB->begin();
252 while ((PN = dyn_cast<PHINode>(BBI++))) {
254 continue; // dead use, don't replace it
255 // Iterate over all of the values in all the PHI nodes.
256 for (unsigned i = 0; i != NumPreds; ++i) {
257 // If the value being merged in is not integer or is not defined
258 // in the loop, skip it.
259 Value *InVal = PN->getIncomingValue(i);
260 if (!isa<Instruction>(InVal) ||
261 // SCEV only supports integer expressions for now.
262 (!isa<IntegerType>(InVal->getType()) &&
263 !isa<PointerType>(InVal->getType())))
266 // If this pred is for a subloop, not L itself, skip it.
267 if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
268 continue; // The Block is in a subloop, skip it.
270 // Check that InVal is defined in the loop.
271 Instruction *Inst = cast<Instruction>(InVal);
272 if (!L->contains(Inst->getParent()))
275 // Okay, this instruction has a user outside of the current loop
276 // and varies predictably *inside* the loop. Evaluate the value it
277 // contains when the loop exits, if possible.
278 SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
279 if (!ExitValue->isLoopInvariant(L))
285 // See if we already computed the exit value for the instruction, if so,
287 Value *&ExitVal = ExitValues[Inst];
289 ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt);
291 DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
292 << " LoopVal = " << *Inst << "\n";
294 PN->setIncomingValue(i, ExitVal);
296 // If this instruction is dead now, delete it.
297 RecursivelyDeleteTriviallyDeadInstructions(Inst);
299 // See if this is a single-entry LCSSA PHI node. If so, we can (and
301 // the PHI entirely. This is safe, because the NewVal won't be variant
302 // in the loop, so we don't need an LCSSA phi node anymore.
304 PN->replaceAllUsesWith(ExitVal);
305 RecursivelyDeleteTriviallyDeadInstructions(PN);
313 void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
314 // First step. Check to see if there are any floating-point recurrences.
315 // If there are, change them into integer recurrences, permitting analysis by
316 // the SCEV routines.
318 BasicBlock *Header = L->getHeader();
320 SmallVector<WeakVH, 8> PHIs;
321 for (BasicBlock::iterator I = Header->begin();
322 PHINode *PN = dyn_cast<PHINode>(I); ++I)
325 for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
326 if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
327 HandleFloatingPointIV(L, PN);
329 // If the loop previously had floating-point IV, ScalarEvolution
330 // may not have been able to compute a trip count. Now that we've done some
331 // re-writing, the trip count may be computable.
333 SE->forgetLoopBackedgeTakenCount(L);
336 bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
337 IU = &getAnalysis<IVUsers>();
338 LI = &getAnalysis<LoopInfo>();
339 SE = &getAnalysis<ScalarEvolution>();
342 // If there are any floating-point recurrences, attempt to
343 // transform them to use integer recurrences.
344 RewriteNonIntegerIVs(L);
346 BasicBlock *Header = L->getHeader();
347 BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
348 SCEVHandle BackedgeTakenCount = SE->getBackedgeTakenCount(L);
350 // Check to see if this loop has a computable loop-invariant execution count.
351 // If so, this means that we can compute the final value of any expressions
352 // that are recurrent in the loop, and substitute the exit values from the
353 // loop into any instructions outside of the loop that use the final values of
354 // the current expressions.
356 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
357 RewriteLoopExitValues(L, BackedgeTakenCount);
359 // Compute the type of the largest recurrence expression, and decide whether
360 // a canonical induction variable should be inserted.
361 const Type *LargestType = 0;
362 bool NeedCannIV = false;
363 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
364 LargestType = BackedgeTakenCount->getType();
365 LargestType = SE->getEffectiveSCEVType(LargestType);
366 // If we have a known trip count and a single exit block, we'll be
367 // rewriting the loop exit test condition below, which requires a
368 // canonical induction variable.
372 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
373 SCEVHandle Stride = IU->StrideOrder[i];
374 const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
376 SE->getTypeSizeInBits(Ty) >
377 SE->getTypeSizeInBits(LargestType))
380 std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
381 IU->IVUsesByStride.find(IU->StrideOrder[i]);
382 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
384 if (!SI->second->Users.empty())
388 // Create a rewriter object which we'll use to transform the code with.
389 SCEVExpander Rewriter(*SE);
391 // Now that we know the largest of of the induction variable expressions
392 // in this loop, insert a canonical induction variable of the largest size.
395 IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType);
398 DOUT << "INDVARS: New CanIV: " << *IndVar;
401 // If we have a trip count expression, rewrite the loop's exit condition
402 // using it. We can currently only handle loops with a single exit.
403 ICmpInst *NewICmp = 0;
404 if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
406 "LinearFunctionTestReplace requires a canonical induction variable");
407 // Can't rewrite non-branch yet.
408 if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
409 NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
410 ExitingBlock, BI, Rewriter);
413 Rewriter.setInsertionPoint(Header->getFirstNonPHI());
415 // Rewrite IV-derived expressions. Clears the rewriter cache.
416 RewriteIVExpressions(L, LargestType, Rewriter);
418 // The Rewriter may only be used for isInsertedInstruction queries from this
421 // Loop-invariant instructions in the preheader that aren't used in the
422 // loop may be sunk below the loop to reduce register pressure.
423 SinkUnusedInvariants(L, Rewriter);
425 // Reorder instructions to avoid use-before-def conditions.
426 FixUsesBeforeDefs(L, Rewriter);
428 // For completeness, inform IVUsers of the IV use in the newly-created
429 // loop exit test instruction.
431 IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
433 // Clean up dead instructions.
434 DeleteDeadPHIs(L->getHeader());
435 // Check a post-condition.
436 assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
440 void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
441 SCEVExpander &Rewriter) {
442 SmallVector<WeakVH, 16> DeadInsts;
444 // Rewrite all induction variable expressions in terms of the canonical
445 // induction variable.
447 // If there were induction variables of other sizes or offsets, manually
448 // add the offsets to the primary induction variable and cast, avoiding
449 // the need for the code evaluation methods to insert induction variables
450 // of different sizes.
451 for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
452 SCEVHandle Stride = IU->StrideOrder[i];
454 std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
455 IU->IVUsesByStride.find(IU->StrideOrder[i]);
456 assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
457 ilist<IVStrideUse> &List = SI->second->Users;
458 for (ilist<IVStrideUse>::iterator UI = List.begin(),
459 E = List.end(); UI != E; ++UI) {
460 SCEVHandle Offset = UI->getOffset();
461 Value *Op = UI->getOperandValToReplace();
462 Instruction *User = UI->getUser();
463 bool isSigned = UI->isSigned();
465 // Compute the final addrec to expand into code.
466 SCEVHandle AR = IU->getReplacementExpr(*UI);
469 if (AR->isLoopInvariant(L)) {
470 BasicBlock::iterator I = Rewriter.getInsertionPoint();
471 // Expand loop-invariant values in the loop preheader. They will
472 // be sunk to the exit block later, if possible.
474 Rewriter.expandCodeFor(AR, LargestType,
475 L->getLoopPreheader()->getTerminator());
476 Rewriter.setInsertionPoint(I);
479 // FIXME: It is an extremely bad idea to indvar substitute anything more
480 // complex than affine induction variables. Doing so will put expensive
481 // polynomial evaluations inside of the loop, and the str reduction pass
482 // currently can only reduce affine polynomials. For now just disable
483 // indvar subst on anything more complex than an affine addrec, unless
484 // it can be expanded to a trivial value.
485 if (!Stride->isLoopInvariant(L))
488 const Type *IVTy = Offset->getType();
489 const Type *UseTy = Op->getType();
491 // Promote the Offset and Stride up to the canonical induction
492 // variable's bit width.
493 SCEVHandle PromotedOffset = Offset;
494 SCEVHandle PromotedStride = Stride;
495 if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType)) {
496 // It doesn't matter for correctness whether zero or sign extension
497 // is used here, since the value is truncated away below, but if the
498 // value is signed, sign extension is more likely to be folded.
500 PromotedOffset = SE->getSignExtendExpr(PromotedOffset, LargestType);
501 PromotedStride = SE->getSignExtendExpr(PromotedStride, LargestType);
503 PromotedOffset = SE->getZeroExtendExpr(PromotedOffset, LargestType);
504 // If the stride is obviously negative, use sign extension to
505 // produce things like x-1 instead of x+255.
506 if (isa<SCEVConstant>(PromotedStride) &&
507 cast<SCEVConstant>(PromotedStride)
508 ->getValue()->getValue().isNegative())
509 PromotedStride = SE->getSignExtendExpr(PromotedStride,
512 PromotedStride = SE->getZeroExtendExpr(PromotedStride,
517 // Create the SCEV representing the offset from the canonical
518 // induction variable, still in the canonical induction variable's
519 // type, so that all expanded arithmetic is done in the same type.
520 SCEVHandle NewAR = SE->getAddRecExpr(SE->getIntegerSCEV(0, LargestType),
522 // Add the PromotedOffset as a separate step, because it may not be
524 NewAR = SE->getAddExpr(NewAR, PromotedOffset);
526 // Expand the addrec into instructions.
527 Value *V = Rewriter.expandCodeFor(NewAR);
529 // Insert an explicit cast if necessary to truncate the value
530 // down to the original stride type. This is done outside of
531 // SCEVExpander because in SCEV expressions, a truncate of an
532 // addrec is always folded.
533 if (LargestType != IVTy) {
534 if (SE->getTypeSizeInBits(IVTy) != SE->getTypeSizeInBits(LargestType))
535 NewAR = SE->getTruncateExpr(NewAR, IVTy);
536 if (Rewriter.isInsertedExpression(NewAR))
537 V = Rewriter.expandCodeFor(NewAR);
539 V = Rewriter.InsertCastOfTo(CastInst::getCastOpcode(V, false,
542 assert(!isa<SExtInst>(V) && !isa<ZExtInst>(V) &&
543 "LargestType wasn't actually the largest type!");
544 // Force the rewriter to use this trunc whenever this addrec
545 // appears so that it doesn't insert new phi nodes or
546 // arithmetic in a different type.
547 Rewriter.addInsertedValue(V, NewAR);
551 DOUT << "INDVARS: Made offset-and-trunc IV for offset "
552 << *IVTy << " " << *Offset << ": ";
553 DEBUG(WriteAsOperand(*DOUT, V, false));
556 // Now expand it into actual Instructions and patch it into place.
557 NewVal = Rewriter.expandCodeFor(AR, UseTy);
560 // Patch the new value into place.
562 NewVal->takeName(Op);
563 User->replaceUsesOfWith(Op, NewVal);
564 UI->setOperandValToReplace(NewVal);
565 DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op
566 << " into = " << *NewVal << "\n";
570 // The old value may be dead now.
571 DeadInsts.push_back(Op);
575 // Clear the rewriter cache, because values that are in the rewriter's cache
576 // can be deleted in the loop below, causing the AssertingVH in the cache to
579 // Now that we're done iterating through lists, clean up any instructions
580 // which are now dead.
581 while (!DeadInsts.empty()) {
582 Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
584 RecursivelyDeleteTriviallyDeadInstructions(Inst);
588 /// If there's a single exit block, sink any loop-invariant values that
589 /// were defined in the preheader but not used inside the loop into the
590 /// exit block to reduce register pressure in the loop.
591 void IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) {
592 BasicBlock *ExitBlock = L->getExitBlock();
593 if (!ExitBlock) return;
595 Instruction *NonPHI = ExitBlock->getFirstNonPHI();
596 BasicBlock *Preheader = L->getLoopPreheader();
597 BasicBlock::iterator I = Preheader->getTerminator();
598 while (I != Preheader->begin()) {
600 // New instructions were inserted at the end of the preheader. Only
601 // consider those new instructions.
602 if (!Rewriter.isInsertedInstruction(I))
604 // Determine if there is a use in or before the loop (direct or
606 bool UsedInLoop = false;
607 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
609 BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
610 if (PHINode *P = dyn_cast<PHINode>(UI)) {
612 PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
613 UseBB = P->getIncomingBlock(i);
615 if (UseBB == Preheader || L->contains(UseBB)) {
620 // If there is, the def must remain in the preheader.
623 // Otherwise, sink it to the exit block.
624 Instruction *ToMove = I;
626 if (I != Preheader->begin())
630 ToMove->moveBefore(NonPHI);
636 /// Re-schedule the inserted instructions to put defs before uses. This
637 /// fixes problems that arrise when SCEV expressions contain loop-variant
638 /// values unrelated to the induction variable which are defined inside the
639 /// loop. FIXME: It would be better to insert instructions in the right
640 /// place so that this step isn't needed.
641 void IndVarSimplify::FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter) {
642 // Visit all the blocks in the loop in pre-order dom-tree dfs order.
643 DominatorTree *DT = &getAnalysis<DominatorTree>();
644 std::map<Instruction *, unsigned> NumPredsLeft;
645 SmallVector<DomTreeNode *, 16> Worklist;
646 Worklist.push_back(DT->getNode(L->getHeader()));
648 DomTreeNode *Node = Worklist.pop_back_val();
649 for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
650 if (L->contains((*I)->getBlock()))
651 Worklist.push_back(*I);
652 BasicBlock *BB = Node->getBlock();
653 // Visit all the instructions in the block top down.
654 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
655 // Count the number of operands that aren't properly dominating.
656 unsigned NumPreds = 0;
657 if (Rewriter.isInsertedInstruction(I) && !isa<PHINode>(I))
658 for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
660 if (Instruction *Inst = dyn_cast<Instruction>(OI))
661 if (L->contains(Inst->getParent()) && !NumPredsLeft.count(Inst))
663 NumPredsLeft[I] = NumPreds;
664 // Notify uses of the position of this instruction, and move the
665 // users (and their dependents, recursively) into place after this
666 // instruction if it is their last outstanding operand.
667 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
669 Instruction *Inst = cast<Instruction>(UI);
670 std::map<Instruction *, unsigned>::iterator Z = NumPredsLeft.find(Inst);
671 if (Z != NumPredsLeft.end() && Z->second != 0 && --Z->second == 0) {
672 SmallVector<Instruction *, 4> UseWorkList;
673 UseWorkList.push_back(Inst);
674 BasicBlock::iterator InsertPt = I;
675 if (InvokeInst *II = dyn_cast<InvokeInst>(InsertPt))
676 InsertPt = II->getNormalDest()->begin();
679 while (isa<PHINode>(InsertPt)) ++InsertPt;
681 Instruction *Use = UseWorkList.pop_back_val();
682 Use->moveBefore(InsertPt);
683 NumPredsLeft.erase(Use);
684 for (Value::use_iterator IUI = Use->use_begin(),
685 IUE = Use->use_end(); IUI != IUE; ++IUI) {
686 Instruction *IUIInst = cast<Instruction>(IUI);
687 if (L->contains(IUIInst->getParent()) &&
688 Rewriter.isInsertedInstruction(IUIInst) &&
689 !isa<PHINode>(IUIInst))
690 UseWorkList.push_back(IUIInst);
692 } while (!UseWorkList.empty());
696 } while (!Worklist.empty());
699 /// Return true if it is OK to use SIToFPInst for an inducation variable
700 /// with given inital and exit values.
701 static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV,
702 uint64_t intIV, uint64_t intEV) {
704 if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative())
707 // If the iteration range can be handled by SIToFPInst then use it.
708 APInt Max = APInt::getSignedMaxValue(32);
709 if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV)))
715 /// convertToInt - Convert APF to an integer, if possible.
716 static bool convertToInt(const APFloat &APF, uint64_t *intVal) {
718 bool isExact = false;
719 if (&APF.getSemantics() == &APFloat::PPCDoubleDouble)
721 if (APF.convertToInteger(intVal, 32, APF.isNegative(),
722 APFloat::rmTowardZero, &isExact)
731 /// HandleFloatingPointIV - If the loop has floating induction variable
732 /// then insert corresponding integer induction variable if possible.
734 /// for(double i = 0; i < 10000; ++i)
736 /// is converted into
737 /// for(int i = 0; i < 10000; ++i)
740 void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
742 unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
743 unsigned BackEdge = IncomingEdge^1;
745 // Check incoming value.
746 ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge));
747 if (!InitValue) return;
748 uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits();
749 if (!convertToInt(InitValue->getValueAPF(), &newInitValue))
752 // Check IV increment. Reject this PH if increement operation is not
753 // an add or increment value can not be represented by an integer.
754 BinaryOperator *Incr =
755 dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge));
757 if (Incr->getOpcode() != Instruction::FAdd) return;
758 ConstantFP *IncrValue = NULL;
759 unsigned IncrVIndex = 1;
760 if (Incr->getOperand(1) == PH)
762 IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex));
763 if (!IncrValue) return;
764 uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits();
765 if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue))
768 // Check Incr uses. One user is PH and the other users is exit condition used
769 // by the conditional terminator.
770 Value::use_iterator IncrUse = Incr->use_begin();
771 Instruction *U1 = cast<Instruction>(IncrUse++);
772 if (IncrUse == Incr->use_end()) return;
773 Instruction *U2 = cast<Instruction>(IncrUse++);
774 if (IncrUse != Incr->use_end()) return;
776 // Find exit condition.
777 FCmpInst *EC = dyn_cast<FCmpInst>(U1);
779 EC = dyn_cast<FCmpInst>(U2);
782 if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) {
783 if (!BI->isConditional()) return;
784 if (BI->getCondition() != EC) return;
787 // Find exit value. If exit value can not be represented as an interger then
788 // do not handle this floating point PH.
789 ConstantFP *EV = NULL;
790 unsigned EVIndex = 1;
791 if (EC->getOperand(1) == Incr)
793 EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex));
795 uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits();
796 if (!convertToInt(EV->getValueAPF(), &intEV))
799 // Find new predicate for integer comparison.
800 CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
801 switch (EC->getPredicate()) {
802 case CmpInst::FCMP_OEQ:
803 case CmpInst::FCMP_UEQ:
804 NewPred = CmpInst::ICMP_EQ;
806 case CmpInst::FCMP_OGT:
807 case CmpInst::FCMP_UGT:
808 NewPred = CmpInst::ICMP_UGT;
810 case CmpInst::FCMP_OGE:
811 case CmpInst::FCMP_UGE:
812 NewPred = CmpInst::ICMP_UGE;
814 case CmpInst::FCMP_OLT:
815 case CmpInst::FCMP_ULT:
816 NewPred = CmpInst::ICMP_ULT;
818 case CmpInst::FCMP_OLE:
819 case CmpInst::FCMP_ULE:
820 NewPred = CmpInst::ICMP_ULE;
825 if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return;
827 // Insert new integer induction variable.
828 PHINode *NewPHI = PHINode::Create(Type::Int32Ty,
829 PH->getName()+".int", PH);
830 NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue),
831 PH->getIncomingBlock(IncomingEdge));
833 Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
834 ConstantInt::get(Type::Int32Ty,
836 Incr->getName()+".int", Incr);
837 NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
839 // The back edge is edge 1 of newPHI, whatever it may have been in the
841 ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV);
842 Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
843 Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
844 ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(),
845 EC->getParent()->getTerminator());
847 // In the following deltions, PH may become dead and may be deleted.
848 // Use a WeakVH to observe whether this happens.
851 // Delete old, floating point, exit comparision instruction.
853 EC->replaceAllUsesWith(NewEC);
854 RecursivelyDeleteTriviallyDeadInstructions(EC);
856 // Delete old, floating point, increment instruction.
857 Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
858 RecursivelyDeleteTriviallyDeadInstructions(Incr);
860 // Replace floating induction variable, if it isn't already deleted.
861 // Give SIToFPInst preference over UIToFPInst because it is faster on
862 // platforms that are widely used.
863 if (WeakPH && !PH->use_empty()) {
864 if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
865 SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
866 PH->getParent()->getFirstNonPHI());
867 PH->replaceAllUsesWith(Conv);
869 UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
870 PH->getParent()->getFirstNonPHI());
871 PH->replaceAllUsesWith(Conv);
873 RecursivelyDeleteTriviallyDeadInstructions(PH);
876 // Add a new IVUsers entry for the newly-created integer PHI.
877 IU->AddUsersIfInteresting(NewPHI);