//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// which starts at zero and steps by one.
// 2. The canonical induction variable is guaranteed to be the first PHI node
// in the loop header block.
-// 3. Any pointer arithmetic recurrences are raised to use array subscripts.
+// 3. The canonical induction variable is guaranteed to be in a wide enough
+// type so that IV expressions need not be (directly) zero-extended or
+// sign-extended.
+// 4. Any pointer arithmetic recurrences are raised to use array subscripts.
//
// If the trip count of a loop is computable, this pass also makes the following
// changes:
// expression, this transformation will make the loop dead.
//
// This transformation should be followed by strength reduction after all of the
-// desired loop transformations have been performed. Additionally, on targets
-// where it is profitable, the loop could be transformed to count down to zero
-// (the "do loop" optimization).
+// desired loop transformations have been performed.
//
//===----------------------------------------------------------------------===//
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Type.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/IVUsers.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
-#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
using namespace llvm;
STATISTIC(NumRemoved , "Number of aux indvars removed");
-STATISTIC(NumPointer , "Number of pointer indvars promoted");
STATISTIC(NumInserted, "Number of canonical indvars added");
STATISTIC(NumReplaced, "Number of exit values replaced");
STATISTIC(NumLFTR , "Number of loop exit tests replaced");
namespace {
class VISIBILITY_HIDDEN IndVarSimplify : public LoopPass {
+ IVUsers *IU;
LoopInfo *LI;
ScalarEvolution *SE;
bool Changed;
public:
- static const int ID; // Pass identifcation, replacement for typeid
- IndVarSimplify() : LoopPass((intptr_t)&ID) {}
+ static char ID; // Pass identification, replacement for typeid
+ IndVarSimplify() : LoopPass(&ID) {}
+
+ virtual bool runOnLoop(Loop *L, LPPassManager &LPM);
- bool runOnLoop(Loop *L, LPPassManager &LPM);
- bool doInitialization(Loop *L, LPPassManager &LPM);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<DominatorTree>();
+ AU.addRequired<ScalarEvolution>();
AU.addRequiredID(LCSSAID);
AU.addRequiredID(LoopSimplifyID);
- AU.addRequired<ScalarEvolution>();
AU.addRequired<LoopInfo>();
+ AU.addRequired<IVUsers>();
+ AU.addPreserved<ScalarEvolution>();
AU.addPreservedID(LoopSimplifyID);
+ AU.addPreserved<IVUsers>();
AU.addPreservedID(LCSSAID);
AU.setPreservesCFG();
}
private:
- void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
- std::set<Instruction*> &DeadInsts);
- Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
- SCEVExpander &RW);
- void RewriteLoopExitValues(Loop *L);
+ void RewriteNonIntegerIVs(Loop *L);
- void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
- };
+ ICmpInst *LinearFunctionTestReplace(Loop *L, const SCEV* BackedgeTakenCount,
+ Value *IndVar,
+ BasicBlock *ExitingBlock,
+ BranchInst *BI,
+ SCEVExpander &Rewriter);
+ void RewriteLoopExitValues(Loop *L, const SCEV *BackedgeTakenCount);
- const int IndVarSimplify::ID = 0;
- RegisterPass<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
-}
+ void RewriteIVExpressions(Loop *L, const Type *LargestType,
+ SCEVExpander &Rewriter,
+ BasicBlock::iterator InsertPt);
-LoopPass *llvm::createIndVarSimplifyPass() {
- return new IndVarSimplify();
-}
+ void SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter);
-/// DeleteTriviallyDeadInstructions - If any of the instructions is the
-/// specified set are trivially dead, delete them and see if this makes any of
-/// their operands subsequently dead.
-void IndVarSimplify::
-DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts) {
- while (!Insts.empty()) {
- Instruction *I = *Insts.begin();
- Insts.erase(Insts.begin());
- if (isInstructionTriviallyDead(I)) {
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
- Insts.insert(U);
- SE->deleteInstructionFromRecords(I);
- DOUT << "INDVARS: Deleting: " << *I;
- I->eraseFromParent();
- Changed = true;
- }
- }
-}
-
-
-/// EliminatePointerRecurrence - Check to see if this is a trivial GEP pointer
-/// recurrence. If so, change it into an integer recurrence, permitting
-/// analysis by the SCEV routines.
-void IndVarSimplify::EliminatePointerRecurrence(PHINode *PN,
- BasicBlock *Preheader,
- std::set<Instruction*> &DeadInsts) {
- assert(PN->getNumIncomingValues() == 2 && "Noncanonicalized loop!");
- unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
- unsigned BackedgeIdx = PreheaderIdx^1;
- if (GetElementPtrInst *GEPI =
- dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
- if (GEPI->getOperand(0) == PN) {
- assert(GEPI->getNumOperands() == 2 && "GEP types must match!");
- DOUT << "INDVARS: Eliminating pointer recurrence: " << *GEPI;
-
- // Okay, we found a pointer recurrence. Transform this pointer
- // recurrence into an integer recurrence. Compute the value that gets
- // added to the pointer at every iteration.
- Value *AddedVal = GEPI->getOperand(1);
-
- // Insert a new integer PHI node into the top of the block.
- PHINode *NewPhi = new PHINode(AddedVal->getType(),
- PN->getName()+".rec", PN);
- NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);
-
- // Create the new add instruction.
- Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal,
- GEPI->getName()+".rec", GEPI);
- NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));
-
- // Update the existing GEP to use the recurrence.
- GEPI->setOperand(0, PN->getIncomingValue(PreheaderIdx));
-
- // Update the GEP to use the new recurrence we just inserted.
- GEPI->setOperand(1, NewAdd);
-
- // If the incoming value is a constant expr GEP, try peeling out the array
- // 0 index if possible to make things simpler.
- if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEPI->getOperand(0)))
- if (CE->getOpcode() == Instruction::GetElementPtr) {
- unsigned NumOps = CE->getNumOperands();
- assert(NumOps > 1 && "CE folding didn't work!");
- if (CE->getOperand(NumOps-1)->isNullValue()) {
- // Check to make sure the last index really is an array index.
- gep_type_iterator GTI = gep_type_begin(CE);
- for (unsigned i = 1, e = CE->getNumOperands()-1;
- i != e; ++i, ++GTI)
- /*empty*/;
- if (isa<SequentialType>(*GTI)) {
- // Pull the last index out of the constant expr GEP.
- SmallVector<Value*, 8> CEIdxs(CE->op_begin()+1, CE->op_end()-1);
- Constant *NCE = ConstantExpr::getGetElementPtr(CE->getOperand(0),
- &CEIdxs[0],
- CEIdxs.size());
- GetElementPtrInst *NGEPI = new GetElementPtrInst(
- NCE, Constant::getNullValue(Type::Int32Ty), NewAdd,
- GEPI->getName(), GEPI);
- GEPI->replaceAllUsesWith(NGEPI);
- GEPI->eraseFromParent();
- GEPI = NGEPI;
- }
- }
- }
+ void FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter);
+ void HandleFloatingPointIV(Loop *L, PHINode *PH);
+ };
+}
- // Finally, if there are any other users of the PHI node, we must
- // insert a new GEP instruction that uses the pre-incremented version
- // of the induction amount.
- if (!PN->use_empty()) {
- BasicBlock::iterator InsertPos = PN; ++InsertPos;
- while (isa<PHINode>(InsertPos)) ++InsertPos;
- Value *PreInc =
- new GetElementPtrInst(PN->getIncomingValue(PreheaderIdx),
- NewPhi, "", InsertPos);
- PreInc->takeName(PN);
- PN->replaceAllUsesWith(PreInc);
- }
-
- // Delete the old PHI for sure, and the GEP if its otherwise unused.
- DeadInsts.insert(PN);
+char IndVarSimplify::ID = 0;
+static RegisterPass<IndVarSimplify>
+X("indvars", "Canonicalize Induction Variables");
- ++NumPointer;
- Changed = true;
- }
+Pass *llvm::createIndVarSimplifyPass() {
+ return new IndVarSimplify();
}
/// LinearFunctionTestReplace - This method rewrites the exit condition of the
/// variable. This pass is able to rewrite the exit tests of any loop where the
/// SCEV analysis can determine a loop-invariant trip count of the loop, which
/// is actually a much broader range than just linear tests.
-///
-/// This method returns a "potentially dead" instruction whose computation chain
-/// should be deleted when convenient.
-Instruction *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
- SCEV *IterationCount,
- SCEVExpander &RW) {
- // Find the exit block for the loop. We can currently only handle loops with
- // a single exit.
- std::vector<BasicBlock*> ExitBlocks;
- L->getExitBlocks(ExitBlocks);
- if (ExitBlocks.size() != 1) return 0;
- BasicBlock *ExitBlock = ExitBlocks[0];
-
- // Make sure there is only one predecessor block in the loop.
- BasicBlock *ExitingBlock = 0;
- for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
- PI != PE; ++PI)
- if (L->contains(*PI)) {
- if (ExitingBlock == 0)
- ExitingBlock = *PI;
- else
- return 0; // Multiple exits from loop to this block.
- }
- assert(ExitingBlock && "Loop info is broken");
-
- if (!isa<BranchInst>(ExitingBlock->getTerminator()))
- return 0; // Can't rewrite non-branch yet
- BranchInst *BI = cast<BranchInst>(ExitingBlock->getTerminator());
- assert(BI->isConditional() && "Must be conditional to be part of loop!");
-
- Instruction *PotentiallyDeadInst = dyn_cast<Instruction>(BI->getCondition());
-
+ICmpInst *IndVarSimplify::LinearFunctionTestReplace(Loop *L,
+ const SCEV* BackedgeTakenCount,
+ Value *IndVar,
+ BasicBlock *ExitingBlock,
+ BranchInst *BI,
+ SCEVExpander &Rewriter) {
// If the exiting block is not the same as the backedge block, we must compare
// against the preincremented value, otherwise we prefer to compare against
// the post-incremented value.
- BasicBlock *Header = L->getHeader();
- pred_iterator HPI = pred_begin(Header);
- assert(HPI != pred_end(Header) && "Loop with zero preds???");
- if (!L->contains(*HPI)) ++HPI;
- assert(HPI != pred_end(Header) && L->contains(*HPI) &&
- "No backedge in loop?");
-
- SCEVHandle TripCount = IterationCount;
- Value *IndVar;
- if (*HPI == ExitingBlock) {
- // The IterationCount expression contains the number of times that the
- // backedge actually branches to the loop header. This is one less than the
- // number of times the loop executes, so add one to it.
- Constant *OneC = ConstantInt::get(IterationCount->getType(), 1);
- TripCount = SCEVAddExpr::get(IterationCount, SCEVUnknown::get(OneC));
- IndVar = L->getCanonicalInductionVariableIncrement();
+ Value *CmpIndVar;
+ const SCEV* RHS = BackedgeTakenCount;
+ if (ExitingBlock == L->getLoopLatch()) {
+ // Add one to the "backedge-taken" count to get the trip count.
+ // If this addition may overflow, we have to be more pessimistic and
+ // cast the induction variable before doing the add.
+ const SCEV* Zero = SE->getIntegerSCEV(0, BackedgeTakenCount->getType());
+ const SCEV* N =
+ SE->getAddExpr(BackedgeTakenCount,
+ SE->getIntegerSCEV(1, BackedgeTakenCount->getType()));
+ if ((isa<SCEVConstant>(N) && !N->isZero()) ||
+ SE->isLoopGuardedByCond(L, ICmpInst::ICMP_NE, N, Zero)) {
+ // No overflow. Cast the sum.
+ RHS = SE->getTruncateOrZeroExtend(N, IndVar->getType());
+ } else {
+ // Potential overflow. Cast before doing the add.
+ RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
+ IndVar->getType());
+ RHS = SE->getAddExpr(RHS,
+ SE->getIntegerSCEV(1, IndVar->getType()));
+ }
+
+ // The BackedgeTaken expression contains the number of times that the
+ // backedge branches to the loop header. This is one less than the
+ // number of times the loop executes, so use the incremented indvar.
+ CmpIndVar = L->getCanonicalInductionVariableIncrement();
} else {
// We have to use the preincremented value...
- IndVar = L->getCanonicalInductionVariable();
+ RHS = SE->getTruncateOrZeroExtend(BackedgeTakenCount,
+ IndVar->getType());
+ CmpIndVar = IndVar;
}
-
- DOUT << "INDVARS: LFTR: TripCount = " << *TripCount
- << " IndVar = " << *IndVar << "\n";
// Expand the code for the iteration count into the preheader of the loop.
+ assert(RHS->isLoopInvariant(L) &&
+ "Computed iteration count is not loop invariant!");
BasicBlock *Preheader = L->getLoopPreheader();
- Value *ExitCnt = RW.expandCodeFor(TripCount, Preheader->getTerminator(),
- IndVar->getType());
+ Value *ExitCnt = Rewriter.expandCodeFor(RHS, IndVar->getType(),
+ Preheader->getTerminator());
// Insert a new icmp_ne or icmp_eq instruction before the branch.
ICmpInst::Predicate Opcode;
else
Opcode = ICmpInst::ICMP_EQ;
- Value *Cond = new ICmpInst(Opcode, IndVar, ExitCnt, "exitcond", BI);
+ DOUT << "INDVARS: Rewriting loop exit condition to:\n"
+ << " LHS:" << *CmpIndVar // includes a newline
+ << " op:\t"
+ << (Opcode == ICmpInst::ICMP_NE ? "!=" : "==") << "\n"
+ << " RHS:\t" << *RHS << "\n";
+
+ ICmpInst *Cond = new ICmpInst(Opcode, CmpIndVar, ExitCnt, "exitcond", BI);
+
+ Instruction *OrigCond = cast<Instruction>(BI->getCondition());
+ // It's tempting to use replaceAllUsesWith here to fully replace the old
+ // comparison, but that's not immediately safe, since users of the old
+ // comparison may not be dominated by the new comparison. Instead, just
+ // update the branch to use the new comparison; in the common case this
+ // will make old comparison dead.
BI->setCondition(Cond);
+ RecursivelyDeleteTriviallyDeadInstructions(OrigCond);
+
++NumLFTR;
Changed = true;
- return PotentiallyDeadInst;
+ return Cond;
}
-
/// RewriteLoopExitValues - Check to see if this loop has a computable
/// loop-invariant execution count. If so, this means that we can compute the
/// final value of any expressions that are recurrent in the loop, and
/// substitute the exit values from the loop into any instructions outside of
/// the loop that use the final values of the current expressions.
-void IndVarSimplify::RewriteLoopExitValues(Loop *L) {
+///
+/// This is mostly redundant with the regular IndVarSimplify activities that
+/// happen later, except that it's more powerful in some cases, because it's
+/// able to brute-force evaluate arbitrary instructions as long as they have
+/// constant operands at the beginning of the loop.
+void IndVarSimplify::RewriteLoopExitValues(Loop *L,
+ const SCEV *BackedgeTakenCount) {
+ // Verify the input to the pass in already in LCSSA form.
+ assert(L->isLCSSAForm());
+
BasicBlock *Preheader = L->getLoopPreheader();
// Scan all of the instructions in the loop, looking at those that have
// extra-loop users and which are recurrences.
- SCEVExpander Rewriter(*SE, *LI);
+ SCEVExpander Rewriter(*SE);
// We insert the code into the preheader of the loop if the loop contains
// multiple exit blocks, or in the exit block if there is exactly one.
BasicBlock *BlockToInsertInto;
- std::vector<BasicBlock*> ExitBlocks;
+ SmallVector<BasicBlock*, 8> ExitBlocks;
L->getUniqueExitBlocks(ExitBlocks);
if (ExitBlocks.size() == 1)
BlockToInsertInto = ExitBlocks[0];
else
BlockToInsertInto = Preheader;
- BasicBlock::iterator InsertPt = BlockToInsertInto->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
+ BasicBlock::iterator InsertPt = BlockToInsertInto->getFirstNonPHI();
- bool HasConstantItCount = isa<SCEVConstant>(SE->getIterationCount(L));
-
- std::set<Instruction*> InstructionsToDelete;
std::map<Instruction*, Value*> ExitValues;
// Find all values that are computed inside the loop, but used outside of it.
// the exit blocks of the loop to find them.
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
BasicBlock *ExitBB = ExitBlocks[i];
-
+
// If there are no PHI nodes in this exit block, then no values defined
// inside the loop are used on this path, skip it.
PHINode *PN = dyn_cast<PHINode>(ExitBB->begin());
if (!PN) continue;
-
+
unsigned NumPreds = PN->getNumIncomingValues();
-
+
// Iterate over all of the PHI nodes.
BasicBlock::iterator BBI = ExitBB->begin();
while ((PN = dyn_cast<PHINode>(BBI++))) {
-
+ if (PN->use_empty())
+ continue; // dead use, don't replace it
// Iterate over all of the values in all the PHI nodes.
for (unsigned i = 0; i != NumPreds; ++i) {
// If the value being merged in is not integer or is not defined
Value *InVal = PN->getIncomingValue(i);
if (!isa<Instruction>(InVal) ||
// SCEV only supports integer expressions for now.
- !isa<IntegerType>(InVal->getType()))
+ (!isa<IntegerType>(InVal->getType()) &&
+ !isa<PointerType>(InVal->getType())))
continue;
// If this pred is for a subloop, not L itself, skip it.
- if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
+ if (LI->getLoopFor(PN->getIncomingBlock(i)) != L)
continue; // The Block is in a subloop, skip it.
// Check that InVal is defined in the loop.
Instruction *Inst = cast<Instruction>(InVal);
if (!L->contains(Inst->getParent()))
continue;
-
- // We require that this value either have a computable evolution or that
- // the loop have a constant iteration count. In the case where the loop
- // has a constant iteration count, we can sometimes force evaluation of
- // the exit value through brute force.
- SCEVHandle SH = SE->getSCEV(Inst);
- if (!SH->hasComputableLoopEvolution(L) && !HasConstantItCount)
- continue; // Cannot get exit evolution for the loop value.
-
+
// Okay, this instruction has a user outside of the current loop
// and varies predictably *inside* the loop. Evaluate the value it
// contains when the loop exits, if possible.
- SCEVHandle ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
- if (isa<SCEVCouldNotCompute>(ExitValue) ||
- !ExitValue->isLoopInvariant(L))
+ const SCEV* ExitValue = SE->getSCEVAtScope(Inst, L->getParentLoop());
+ if (!ExitValue->isLoopInvariant(L))
continue;
Changed = true;
++NumReplaced;
-
+
// See if we already computed the exit value for the instruction, if so,
// just reuse it.
Value *&ExitVal = ExitValues[Inst];
if (!ExitVal)
- ExitVal = Rewriter.expandCodeFor(ExitValue, InsertPt,Inst->getType());
-
+ ExitVal = Rewriter.expandCodeFor(ExitValue, PN->getType(), InsertPt);
+
DOUT << "INDVARS: RLEV: AfterLoopVal = " << *ExitVal
<< " LoopVal = " << *Inst << "\n";
PN->setIncomingValue(i, ExitVal);
-
- // If this instruction is dead now, schedule it to be removed.
- if (Inst->use_empty())
- InstructionsToDelete.insert(Inst);
-
- // See if this is a single-entry LCSSA PHI node. If so, we can (and
- // have to) remove
- // the PHI entirely. This is safe, because the NewVal won't be variant
+
+ // If this instruction is dead now, delete it.
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
+
+ // If we're inserting code into the exit block rather than the
+ // preheader, we can (and have to) remove the PHI entirely.
+ // This is safe, because the NewVal won't be variant
// in the loop, so we don't need an LCSSA phi node anymore.
- if (NumPreds == 1) {
+ if (ExitBlocks.size() == 1) {
PN->replaceAllUsesWith(ExitVal);
- PN->eraseFromParent();
+ RecursivelyDeleteTriviallyDeadInstructions(PN);
break;
}
}
}
}
-
- DeleteTriviallyDeadInstructions(InstructionsToDelete);
}
-bool IndVarSimplify::doInitialization(Loop *L, LPPassManager &LPM) {
-
- Changed = false;
- // First step. Check to see if there are any trivial GEP pointer recurrences.
+void IndVarSimplify::RewriteNonIntegerIVs(Loop *L) {
+ // First step. Check to see if there are any floating-point recurrences.
// If there are, change them into integer recurrences, permitting analysis by
// the SCEV routines.
//
BasicBlock *Header = L->getHeader();
- BasicBlock *Preheader = L->getLoopPreheader();
- SE = &LPM.getAnalysis<ScalarEvolution>();
- std::set<Instruction*> DeadInsts;
- for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- if (isa<PointerType>(PN->getType()))
- EliminatePointerRecurrence(PN, Preheader, DeadInsts);
- }
+ SmallVector<WeakVH, 8> PHIs;
+ for (BasicBlock::iterator I = Header->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I)
+ PHIs.push_back(PN);
- if (!DeadInsts.empty())
- DeleteTriviallyDeadInstructions(DeadInsts);
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
+ if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i]))
+ HandleFloatingPointIV(L, PN);
- return Changed;
+ // If the loop previously had floating-point IV, ScalarEvolution
+ // may not have been able to compute a trip count. Now that we've done some
+ // re-writing, the trip count may be computable.
+ if (Changed)
+ SE->forgetLoopBackedgeTakenCount(L);
}
bool IndVarSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
-
-
+ IU = &getAnalysis<IVUsers>();
LI = &getAnalysis<LoopInfo>();
SE = &getAnalysis<ScalarEvolution>();
-
Changed = false;
- BasicBlock *Header = L->getHeader();
- std::set<Instruction*> DeadInsts;
-
- // Verify the input to the pass in already in LCSSA form.
- assert(L->isLCSSAForm());
+
+ // If there are any floating-point recurrences, attempt to
+ // transform them to use integer recurrences.
+ RewriteNonIntegerIVs(L);
+
+ BasicBlock *Header = L->getHeader();
+ BasicBlock *ExitingBlock = L->getExitingBlock(); // may be null
+ const SCEV* BackedgeTakenCount = SE->getBackedgeTakenCount(L);
// Check to see if this loop has a computable loop-invariant execution count.
// If so, this means that we can compute the final value of any expressions
// loop into any instructions outside of the loop that use the final values of
// the current expressions.
//
- SCEVHandle IterationCount = SE->getIterationCount(L);
- if (!isa<SCEVCouldNotCompute>(IterationCount))
- RewriteLoopExitValues(L);
-
- // Next, analyze all of the induction variables in the loop, canonicalizing
- // auxillary induction variables.
- std::vector<std::pair<PHINode*, SCEVHandle> > IndVars;
-
- for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
- PHINode *PN = cast<PHINode>(I);
- if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
- SCEVHandle SCEV = SE->getSCEV(PN);
- if (SCEV->hasComputableLoopEvolution(L))
- // FIXME: It is an extremely bad idea to indvar substitute anything more
- // complex than affine induction variables. Doing so will put expensive
- // polynomial evaluations inside of the loop, and the str reduction pass
- // currently can only reduce affine polynomials. For now just disable
- // indvar subst on anything more complex than an affine addrec.
- if (SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(SCEV))
- if (AR->isAffine())
- IndVars.push_back(std::make_pair(PN, SCEV));
- }
+ if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount))
+ RewriteLoopExitValues(L, BackedgeTakenCount);
+
+ // Compute the type of the largest recurrence expression, and decide whether
+ // a canonical induction variable should be inserted.
+ const Type *LargestType = 0;
+ bool NeedCannIV = false;
+ if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount)) {
+ LargestType = BackedgeTakenCount->getType();
+ LargestType = SE->getEffectiveSCEVType(LargestType);
+ // If we have a known trip count and a single exit block, we'll be
+ // rewriting the loop exit test condition below, which requires a
+ // canonical induction variable.
+ if (ExitingBlock)
+ NeedCannIV = true;
}
+ for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
+ const SCEV* Stride = IU->StrideOrder[i];
+ const Type *Ty = SE->getEffectiveSCEVType(Stride->getType());
+ if (!LargestType ||
+ SE->getTypeSizeInBits(Ty) >
+ SE->getTypeSizeInBits(LargestType))
+ LargestType = Ty;
- // If there are no induction variables in the loop, there is nothing more to
- // do.
- if (IndVars.empty()) {
- // Actually, if we know how many times the loop iterates, lets insert a
- // canonical induction variable to help subsequent passes.
- if (!isa<SCEVCouldNotCompute>(IterationCount)) {
- SCEVExpander Rewriter(*SE, *LI);
- Rewriter.getOrInsertCanonicalInductionVariable(L,
- IterationCount->getType());
- if (Instruction *I = LinearFunctionTestReplace(L, IterationCount,
- Rewriter)) {
- std::set<Instruction*> InstructionsToDelete;
- InstructionsToDelete.insert(I);
- DeleteTriviallyDeadInstructions(InstructionsToDelete);
- }
+ std::map<const SCEV*, IVUsersOfOneStride *>::iterator SI =
+ IU->IVUsesByStride.find(IU->StrideOrder[i]);
+ assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
+
+ if (!SI->second->Users.empty())
+ NeedCannIV = true;
+ }
+
+ // Create a rewriter object which we'll use to transform the code with.
+ SCEVExpander Rewriter(*SE);
+
+ // Now that we know the largest of of the induction variable expressions
+ // in this loop, insert a canonical induction variable of the largest size.
+ Value *IndVar = 0;
+ if (NeedCannIV) {
+ // Check to see if the loop already has a canonical-looking induction
+ // variable. If one is present and it's wider than the planned canonical
+ // induction variable, temporarily remove it, so that the Rewriter
+ // doesn't attempt to reuse it.
+ PHINode *OldCannIV = L->getCanonicalInductionVariable();
+ if (OldCannIV) {
+ if (SE->getTypeSizeInBits(OldCannIV->getType()) >
+ SE->getTypeSizeInBits(LargestType))
+ OldCannIV->removeFromParent();
+ else
+ OldCannIV = 0;
}
- return Changed;
+
+ IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType);
+
+ ++NumInserted;
+ Changed = true;
+ DOUT << "INDVARS: New CanIV: " << *IndVar;
+
+ // Now that the official induction variable is established, reinsert
+ // the old canonical-looking variable after it so that the IR remains
+ // consistent. It will be deleted as part of the dead-PHI deletion at
+ // the end of the pass.
+ if (OldCannIV)
+ OldCannIV->insertAfter(cast<Instruction>(IndVar));
}
- // Compute the type of the largest recurrence expression.
+ // If we have a trip count expression, rewrite the loop's exit condition
+ // using it. We can currently only handle loops with a single exit.
+ ICmpInst *NewICmp = 0;
+ if (!isa<SCEVCouldNotCompute>(BackedgeTakenCount) && ExitingBlock) {
+ assert(NeedCannIV &&
+ "LinearFunctionTestReplace requires a canonical induction variable");
+ // Can't rewrite non-branch yet.
+ if (BranchInst *BI = dyn_cast<BranchInst>(ExitingBlock->getTerminator()))
+ NewICmp = LinearFunctionTestReplace(L, BackedgeTakenCount, IndVar,
+ ExitingBlock, BI, Rewriter);
+ }
+
+ BasicBlock::iterator InsertPt = Header->getFirstNonPHI();
+
+ // Rewrite IV-derived expressions. Clears the rewriter cache.
+ RewriteIVExpressions(L, LargestType, Rewriter, InsertPt);
+
+ // The Rewriter may only be used for isInsertedInstruction queries from this
+ // point on.
+
+ // Loop-invariant instructions in the preheader that aren't used in the
+ // loop may be sunk below the loop to reduce register pressure.
+ SinkUnusedInvariants(L, Rewriter);
+
+ // Reorder instructions to avoid use-before-def conditions.
+ FixUsesBeforeDefs(L, Rewriter);
+
+ // For completeness, inform IVUsers of the IV use in the newly-created
+ // loop exit test instruction.
+ if (NewICmp)
+ IU->AddUsersIfInteresting(cast<Instruction>(NewICmp->getOperand(0)));
+
+ // Clean up dead instructions.
+ DeleteDeadPHIs(L->getHeader());
+ // Check a post-condition.
+ assert(L->isLCSSAForm() && "Indvars did not leave the loop in lcssa form!");
+ return Changed;
+}
+
+void IndVarSimplify::RewriteIVExpressions(Loop *L, const Type *LargestType,
+ SCEVExpander &Rewriter,
+ BasicBlock::iterator InsertPt) {
+ SmallVector<WeakVH, 16> DeadInsts;
+
+ // Rewrite all induction variable expressions in terms of the canonical
+ // induction variable.
//
- const Type *LargestType = IndVars[0].first->getType();
- bool DifferingSizes = false;
- for (unsigned i = 1, e = IndVars.size(); i != e; ++i) {
- const Type *Ty = IndVars[i].first->getType();
- DifferingSizes |=
- Ty->getPrimitiveSizeInBits() != LargestType->getPrimitiveSizeInBits();
- if (Ty->getPrimitiveSizeInBits() > LargestType->getPrimitiveSizeInBits())
- LargestType = Ty;
+ // If there were induction variables of other sizes or offsets, manually
+ // add the offsets to the primary induction variable and cast, avoiding
+ // the need for the code evaluation methods to insert induction variables
+ // of different sizes.
+ for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
+ const SCEV* Stride = IU->StrideOrder[i];
+
+ std::map<const SCEV*, IVUsersOfOneStride *>::iterator SI =
+ IU->IVUsesByStride.find(IU->StrideOrder[i]);
+ assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
+ ilist<IVStrideUse> &List = SI->second->Users;
+ for (ilist<IVStrideUse>::iterator UI = List.begin(),
+ E = List.end(); UI != E; ++UI) {
+ Value *Op = UI->getOperandValToReplace();
+ const Type *UseTy = Op->getType();
+ Instruction *User = UI->getUser();
+
+ // Compute the final addrec to expand into code.
+ const SCEV* AR = IU->getReplacementExpr(*UI);
+
+ // FIXME: It is an extremely bad idea to indvar substitute anything more
+ // complex than affine induction variables. Doing so will put expensive
+ // polynomial evaluations inside of the loop, and the str reduction pass
+ // currently can only reduce affine polynomials. For now just disable
+ // indvar subst on anything more complex than an affine addrec, unless
+ // it can be expanded to a trivial value.
+ if (!AR->isLoopInvariant(L) && !Stride->isLoopInvariant(L))
+ continue;
+
+ // Now expand it into actual Instructions and patch it into place.
+ Value *NewVal = Rewriter.expandCodeFor(AR, UseTy, InsertPt);
+
+ // Patch the new value into place.
+ if (Op->hasName())
+ NewVal->takeName(Op);
+ User->replaceUsesOfWith(Op, NewVal);
+ UI->setOperandValToReplace(NewVal);
+ DOUT << "INDVARS: Rewrote IV '" << *AR << "' " << *Op
+ << " into = " << *NewVal << "\n";
+ ++NumRemoved;
+ Changed = true;
+
+ // The old value may be dead now.
+ DeadInsts.push_back(Op);
+ }
}
- // Create a rewriter object which we'll use to transform the code with.
- SCEVExpander Rewriter(*SE, *LI);
+ // Clear the rewriter cache, because values that are in the rewriter's cache
+ // can be deleted in the loop below, causing the AssertingVH in the cache to
+ // trigger.
+ Rewriter.clear();
+ // Now that we're done iterating through lists, clean up any instructions
+ // which are now dead.
+ while (!DeadInsts.empty()) {
+ Instruction *Inst = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
+ if (Inst)
+ RecursivelyDeleteTriviallyDeadInstructions(Inst);
+ }
+}
- // Now that we know the largest of of the induction variables in this loop,
- // insert a canonical induction variable of the largest size.
- Value *IndVar = Rewriter.getOrInsertCanonicalInductionVariable(L,LargestType);
- ++NumInserted;
- Changed = true;
- DOUT << "INDVARS: New CanIV: " << *IndVar;
-
- if (!isa<SCEVCouldNotCompute>(IterationCount))
- if (Instruction *DI = LinearFunctionTestReplace(L, IterationCount,Rewriter))
- DeadInsts.insert(DI);
-
- // Now that we have a canonical induction variable, we can rewrite any
- // recurrences in terms of the induction variable. Start with the auxillary
- // induction variables, and recursively rewrite any of their uses.
- BasicBlock::iterator InsertPt = Header->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
-
- // If there were induction variables of other sizes, cast the primary
- // induction variable to the right size for them, avoiding the need for the
- // code evaluation methods to insert induction variables of different sizes.
- if (DifferingSizes) {
- SmallVector<unsigned,4> InsertedSizes;
- InsertedSizes.push_back(LargestType->getPrimitiveSizeInBits());
- for (unsigned i = 0, e = IndVars.size(); i != e; ++i) {
- unsigned ithSize = IndVars[i].first->getType()->getPrimitiveSizeInBits();
- if (std::find(InsertedSizes.begin(), InsertedSizes.end(), ithSize)
- == InsertedSizes.end()) {
- PHINode *PN = IndVars[i].first;
- InsertedSizes.push_back(ithSize);
- Instruction *New = new TruncInst(IndVar, PN->getType(), "indvar",
- InsertPt);
- Rewriter.addInsertedValue(New, SE->getSCEV(New));
- DOUT << "INDVARS: Made trunc IV for " << *PN
- << " NewVal = " << *New << "\n";
+/// If there's a single exit block, sink any loop-invariant values that
+/// were defined in the preheader but not used inside the loop into the
+/// exit block to reduce register pressure in the loop.
+void IndVarSimplify::SinkUnusedInvariants(Loop *L, SCEVExpander &Rewriter) {
+ BasicBlock *ExitBlock = L->getExitBlock();
+ if (!ExitBlock) return;
+
+ Instruction *NonPHI = ExitBlock->getFirstNonPHI();
+ BasicBlock *Preheader = L->getLoopPreheader();
+ BasicBlock::iterator I = Preheader->getTerminator();
+ while (I != Preheader->begin()) {
+ --I;
+ // New instructions were inserted at the end of the preheader. Only
+ // consider those new instructions.
+ if (!Rewriter.isInsertedInstruction(I))
+ break;
+ // Determine if there is a use in or before the loop (direct or
+ // otherwise).
+ bool UsedInLoop = false;
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI) {
+ BasicBlock *UseBB = cast<Instruction>(UI)->getParent();
+ if (PHINode *P = dyn_cast<PHINode>(UI)) {
+ unsigned i =
+ PHINode::getIncomingValueNumForOperand(UI.getOperandNo());
+ UseBB = P->getIncomingBlock(i);
+ }
+ if (UseBB == Preheader || L->contains(UseBB)) {
+ UsedInLoop = true;
+ break;
}
}
+ // If there is, the def must remain in the preheader.
+ if (UsedInLoop)
+ continue;
+ // Otherwise, sink it to the exit block.
+ Instruction *ToMove = I;
+ bool Done = false;
+ if (I != Preheader->begin())
+ --I;
+ else
+ Done = true;
+ ToMove->moveBefore(NonPHI);
+ if (Done)
+ break;
}
+}
- // Rewrite all induction variables in terms of the canonical induction
- // variable.
- std::map<unsigned, Value*> InsertedSizes;
- while (!IndVars.empty()) {
- PHINode *PN = IndVars.back().first;
- Value *NewVal = Rewriter.expandCodeFor(IndVars.back().second, InsertPt,
- PN->getType());
- DOUT << "INDVARS: Rewrote IV '" << *IndVars.back().second << "' " << *PN
- << " into = " << *NewVal << "\n";
- NewVal->takeName(PN);
-
- // Replace the old PHI Node with the inserted computation.
- PN->replaceAllUsesWith(NewVal);
- DeadInsts.insert(PN);
- IndVars.pop_back();
- ++NumRemoved;
- Changed = true;
+/// Re-schedule the inserted instructions to put defs before uses. This
+/// fixes problems that arrise when SCEV expressions contain loop-variant
+/// values unrelated to the induction variable which are defined inside the
+/// loop. FIXME: It would be better to insert instructions in the right
+/// place so that this step isn't needed.
+void IndVarSimplify::FixUsesBeforeDefs(Loop *L, SCEVExpander &Rewriter) {
+ // Visit all the blocks in the loop in pre-order dom-tree dfs order.
+ DominatorTree *DT = &getAnalysis<DominatorTree>();
+ std::map<Instruction *, unsigned> NumPredsLeft;
+ SmallVector<DomTreeNode *, 16> Worklist;
+ Worklist.push_back(DT->getNode(L->getHeader()));
+ do {
+ DomTreeNode *Node = Worklist.pop_back_val();
+ for (DomTreeNode::iterator I = Node->begin(), E = Node->end(); I != E; ++I)
+ if (L->contains((*I)->getBlock()))
+ Worklist.push_back(*I);
+ BasicBlock *BB = Node->getBlock();
+ // Visit all the instructions in the block top down.
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+ // Count the number of operands that aren't properly dominating.
+ unsigned NumPreds = 0;
+ if (Rewriter.isInsertedInstruction(I) && !isa<PHINode>(I))
+ for (User::op_iterator OI = I->op_begin(), OE = I->op_end();
+ OI != OE; ++OI)
+ if (Instruction *Inst = dyn_cast<Instruction>(OI))
+ if (L->contains(Inst->getParent()) && !NumPredsLeft.count(Inst))
+ ++NumPreds;
+ NumPredsLeft[I] = NumPreds;
+ // Notify uses of the position of this instruction, and move the
+ // users (and their dependents, recursively) into place after this
+ // instruction if it is their last outstanding operand.
+ for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+ UI != UE; ++UI) {
+ Instruction *Inst = cast<Instruction>(UI);
+ std::map<Instruction *, unsigned>::iterator Z = NumPredsLeft.find(Inst);
+ if (Z != NumPredsLeft.end() && Z->second != 0 && --Z->second == 0) {
+ SmallVector<Instruction *, 4> UseWorkList;
+ UseWorkList.push_back(Inst);
+ BasicBlock::iterator InsertPt = I;
+ if (InvokeInst *II = dyn_cast<InvokeInst>(InsertPt))
+ InsertPt = II->getNormalDest()->begin();
+ else
+ ++InsertPt;
+ while (isa<PHINode>(InsertPt)) ++InsertPt;
+ do {
+ Instruction *Use = UseWorkList.pop_back_val();
+ Use->moveBefore(InsertPt);
+ NumPredsLeft.erase(Use);
+ for (Value::use_iterator IUI = Use->use_begin(),
+ IUE = Use->use_end(); IUI != IUE; ++IUI) {
+ Instruction *IUIInst = cast<Instruction>(IUI);
+ if (L->contains(IUIInst->getParent()) &&
+ Rewriter.isInsertedInstruction(IUIInst) &&
+ !isa<PHINode>(IUIInst))
+ UseWorkList.push_back(IUIInst);
+ }
+ } while (!UseWorkList.empty());
+ }
+ }
+ }
+ } while (!Worklist.empty());
+}
+
+/// Return true if it is OK to use SIToFPInst for an inducation variable
+/// with given inital and exit values.
+static bool useSIToFPInst(ConstantFP &InitV, ConstantFP &ExitV,
+ uint64_t intIV, uint64_t intEV) {
+
+ if (InitV.getValueAPF().isNegative() || ExitV.getValueAPF().isNegative())
+ return true;
+
+ // If the iteration range can be handled by SIToFPInst then use it.
+ APInt Max = APInt::getSignedMaxValue(32);
+ if (Max.getZExtValue() > static_cast<uint64_t>(abs64(intEV - intIV)))
+ return true;
+
+ return false;
+}
+
+/// convertToInt - Convert APF to an integer, if possible.
+static bool convertToInt(const APFloat &APF, uint64_t *intVal) {
+
+ bool isExact = false;
+ if (&APF.getSemantics() == &APFloat::PPCDoubleDouble)
+ return false;
+ if (APF.convertToInteger(intVal, 32, APF.isNegative(),
+ APFloat::rmTowardZero, &isExact)
+ != APFloat::opOK)
+ return false;
+ if (!isExact)
+ return false;
+ return true;
+
+}
+
+/// HandleFloatingPointIV - If the loop has floating induction variable
+/// then insert corresponding integer induction variable if possible.
+/// For example,
+/// for(double i = 0; i < 10000; ++i)
+/// bar(i)
+/// is converted into
+/// for(int i = 0; i < 10000; ++i)
+/// bar((double)i);
+///
+void IndVarSimplify::HandleFloatingPointIV(Loop *L, PHINode *PH) {
+
+ unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
+ unsigned BackEdge = IncomingEdge^1;
+
+ // Check incoming value.
+ ConstantFP *InitValue = dyn_cast<ConstantFP>(PH->getIncomingValue(IncomingEdge));
+ if (!InitValue) return;
+ uint64_t newInitValue = Type::Int32Ty->getPrimitiveSizeInBits();
+ if (!convertToInt(InitValue->getValueAPF(), &newInitValue))
+ return;
+
+ // Check IV increment. Reject this PH if increement operation is not
+ // an add or increment value can not be represented by an integer.
+ BinaryOperator *Incr =
+ dyn_cast<BinaryOperator>(PH->getIncomingValue(BackEdge));
+ if (!Incr) return;
+ if (Incr->getOpcode() != Instruction::FAdd) return;
+ ConstantFP *IncrValue = NULL;
+ unsigned IncrVIndex = 1;
+ if (Incr->getOperand(1) == PH)
+ IncrVIndex = 0;
+ IncrValue = dyn_cast<ConstantFP>(Incr->getOperand(IncrVIndex));
+ if (!IncrValue) return;
+ uint64_t newIncrValue = Type::Int32Ty->getPrimitiveSizeInBits();
+ if (!convertToInt(IncrValue->getValueAPF(), &newIncrValue))
+ return;
+
+ // Check Incr uses. One user is PH and the other users is exit condition used
+ // by the conditional terminator.
+ Value::use_iterator IncrUse = Incr->use_begin();
+ Instruction *U1 = cast<Instruction>(IncrUse++);
+ if (IncrUse == Incr->use_end()) return;
+ Instruction *U2 = cast<Instruction>(IncrUse++);
+ if (IncrUse != Incr->use_end()) return;
+
+ // Find exit condition.
+ FCmpInst *EC = dyn_cast<FCmpInst>(U1);
+ if (!EC)
+ EC = dyn_cast<FCmpInst>(U2);
+ if (!EC) return;
+
+ if (BranchInst *BI = dyn_cast<BranchInst>(EC->getParent()->getTerminator())) {
+ if (!BI->isConditional()) return;
+ if (BI->getCondition() != EC) return;
}
-#if 0
- // Now replace all derived expressions in the loop body with simpler
- // expressions.
- for (unsigned i = 0, e = L->getBlocks().size(); i != e; ++i)
- if (LI->getLoopFor(L->getBlocks()[i]) == L) { // Not in a subloop...
- BasicBlock *BB = L->getBlocks()[i];
- for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
- if (I->getType()->isInteger() && // Is an integer instruction
- !I->use_empty() &&
- !Rewriter.isInsertedInstruction(I)) {
- SCEVHandle SH = SE->getSCEV(I);
- Value *V = Rewriter.expandCodeFor(SH, I, I->getType());
- if (V != I) {
- if (isa<Instruction>(V))
- V->takeName(I);
- I->replaceAllUsesWith(V);
- DeadInsts.insert(I);
- ++NumRemoved;
- Changed = true;
- }
- }
+ // Find exit value. If exit value can not be represented as an interger then
+ // do not handle this floating point PH.
+ ConstantFP *EV = NULL;
+ unsigned EVIndex = 1;
+ if (EC->getOperand(1) == Incr)
+ EVIndex = 0;
+ EV = dyn_cast<ConstantFP>(EC->getOperand(EVIndex));
+ if (!EV) return;
+ uint64_t intEV = Type::Int32Ty->getPrimitiveSizeInBits();
+ if (!convertToInt(EV->getValueAPF(), &intEV))
+ return;
+
+ // Find new predicate for integer comparison.
+ CmpInst::Predicate NewPred = CmpInst::BAD_ICMP_PREDICATE;
+ switch (EC->getPredicate()) {
+ case CmpInst::FCMP_OEQ:
+ case CmpInst::FCMP_UEQ:
+ NewPred = CmpInst::ICMP_EQ;
+ break;
+ case CmpInst::FCMP_OGT:
+ case CmpInst::FCMP_UGT:
+ NewPred = CmpInst::ICMP_UGT;
+ break;
+ case CmpInst::FCMP_OGE:
+ case CmpInst::FCMP_UGE:
+ NewPred = CmpInst::ICMP_UGE;
+ break;
+ case CmpInst::FCMP_OLT:
+ case CmpInst::FCMP_ULT:
+ NewPred = CmpInst::ICMP_ULT;
+ break;
+ case CmpInst::FCMP_OLE:
+ case CmpInst::FCMP_ULE:
+ NewPred = CmpInst::ICMP_ULE;
+ break;
+ default:
+ break;
+ }
+ if (NewPred == CmpInst::BAD_ICMP_PREDICATE) return;
+
+ // Insert new integer induction variable.
+ PHINode *NewPHI = PHINode::Create(Type::Int32Ty,
+ PH->getName()+".int", PH);
+ NewPHI->addIncoming(ConstantInt::get(Type::Int32Ty, newInitValue),
+ PH->getIncomingBlock(IncomingEdge));
+
+ Value *NewAdd = BinaryOperator::CreateAdd(NewPHI,
+ ConstantInt::get(Type::Int32Ty,
+ newIncrValue),
+ Incr->getName()+".int", Incr);
+ NewPHI->addIncoming(NewAdd, PH->getIncomingBlock(BackEdge));
+
+ // The back edge is edge 1 of newPHI, whatever it may have been in the
+ // original PHI.
+ ConstantInt *NewEV = ConstantInt::get(Type::Int32Ty, intEV);
+ Value *LHS = (EVIndex == 1 ? NewPHI->getIncomingValue(1) : NewEV);
+ Value *RHS = (EVIndex == 1 ? NewEV : NewPHI->getIncomingValue(1));
+ ICmpInst *NewEC = new ICmpInst(NewPred, LHS, RHS, EC->getNameStart(),
+ EC->getParent()->getTerminator());
+
+ // In the following deltions, PH may become dead and may be deleted.
+ // Use a WeakVH to observe whether this happens.
+ WeakVH WeakPH = PH;
+
+ // Delete old, floating point, exit comparision instruction.
+ NewEC->takeName(EC);
+ EC->replaceAllUsesWith(NewEC);
+ RecursivelyDeleteTriviallyDeadInstructions(EC);
+
+ // Delete old, floating point, increment instruction.
+ Incr->replaceAllUsesWith(UndefValue::get(Incr->getType()));
+ RecursivelyDeleteTriviallyDeadInstructions(Incr);
+
+ // Replace floating induction variable, if it isn't already deleted.
+ // Give SIToFPInst preference over UIToFPInst because it is faster on
+ // platforms that are widely used.
+ if (WeakPH && !PH->use_empty()) {
+ if (useSIToFPInst(*InitValue, *EV, newInitValue, intEV)) {
+ SIToFPInst *Conv = new SIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+ PH->getParent()->getFirstNonPHI());
+ PH->replaceAllUsesWith(Conv);
+ } else {
+ UIToFPInst *Conv = new UIToFPInst(NewPHI, PH->getType(), "indvar.conv",
+ PH->getParent()->getFirstNonPHI());
+ PH->replaceAllUsesWith(Conv);
}
-#endif
+ RecursivelyDeleteTriviallyDeadInstructions(PH);
+ }
- DeleteTriviallyDeadInstructions(DeadInsts);
-
- assert(L->isLCSSAForm());
- return Changed;
+ // Add a new IVUsers entry for the newly-created integer PHI.
+ IU->AddUsersIfInteresting(NewPHI);
}
projects / oota-llvm.git / blobdiff