// computations derived from them) into simpler forms suitable for subsequent
// analysis and transformation.
//
-// This transformation make the following changes to each loop with an
+// This transformation makes the following changes to each loop with an
// identifiable induction variable:
// 1. All loops are transformed to have a SINGLE canonical induction variable
// which starts at zero and steps by one.
AU.addRequired<ScalarEvolution>();
AU.addRequired<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
+ AU.addPreservedID(LCSSAID);
AU.setPreservesCFG();
}
private:
void runOnLoop(Loop *L);
void EliminatePointerRecurrence(PHINode *PN, BasicBlock *Preheader,
std::set<Instruction*> &DeadInsts);
- void LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
- SCEVExpander &RW);
+ Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
+ SCEVExpander &RW);
void RewriteLoopExitValues(Loop *L);
void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
};
- RegisterOpt<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
+ RegisterPass<IndVarSimplify> X("indvars", "Canonicalize Induction Variables");
}
FunctionPass *llvm::createIndVarSimplifyPass() {
unsigned PreheaderIdx = PN->getBasicBlockIndex(Preheader);
unsigned BackedgeIdx = PreheaderIdx^1;
if (GetElementPtrInst *GEPI =
- dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
+ dyn_cast<GetElementPtrInst>(PN->getIncomingValue(BackedgeIdx)))
if (GEPI->getOperand(0) == PN) {
- assert(GEPI->getNumOperands() == 2 && "GEP types must mismatch!");
+ assert(GEPI->getNumOperands() == 2 && "GEP types must match!");
// Okay, we found a pointer recurrence. Transform this pointer
// recurrence into an integer recurrence. Compute the value that gets
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(GEPI);
- for (unsigned i = 1, e = GEPI->getNumOperands()-1;
+ 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)) {
/// 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.
-void IndVarSimplify::LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
- SCEVExpander &RW) {
+///
+/// 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;
+ if (ExitBlocks.size() != 1) return 0;
BasicBlock *ExitBlock = ExitBlocks[0];
// Make sure there is only one predecessor block in the loop.
if (ExitingBlock == 0)
ExitingBlock = *PI;
else
- return; // Multiple exits from loop to this block.
+ return 0; // Multiple exits from loop to this block.
}
assert(ExitingBlock && "Loop info is broken");
if (!isa<BranchInst>(ExitingBlock->getTerminator()))
- return; // Can't rewrite non-branch yet
+ 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!");
- std::set<Instruction*> InstructionsToDelete;
- if (Instruction *Cond = dyn_cast<Instruction>(BI->getCondition()))
- InstructionsToDelete.insert(Cond);
-
+ Instruction *PotentiallyDeadInst = dyn_cast<Instruction>(BI->getCondition());
+
// 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.
BI->setCondition(Cond);
++NumLFTR;
Changed = true;
-
- DeleteTriviallyDeadInstructions(InstructionsToDelete);
+ return PotentiallyDeadInst;
}
HasConstantItCount) {
// Find out if this predictably varying value is actually used
// outside of the loop. "extra" as opposed to "intra".
- std::vector<User*> ExtraLoopUsers;
+ std::vector<Instruction*> ExtraLoopUsers;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
- UI != E; ++UI)
- if (!L->contains(cast<Instruction>(*UI)->getParent()))
- ExtraLoopUsers.push_back(*UI);
+ UI != E; ++UI) {
+ Instruction *User = cast<Instruction>(*UI);
+ if (!L->contains(User->getParent())) {
+ // If this is a PHI node in the exit block and we're inserting,
+ // into the exit block, it must have a single entry. In this
+ // case, we can't insert the code after the PHI and have the PHI
+ // still use it. Instead, don't insert the the PHI.
+ if (PHINode *PN = dyn_cast<PHINode>(User)) {
+ // FIXME: This is a case where LCSSA pessimizes code, this
+ // should be fixed better.
+ if (PN->getNumOperands() == 2 &&
+ PN->getParent() == BlockToInsertInto)
+ continue;
+ }
+ ExtraLoopUsers.push_back(User);
+ }
+ }
+
if (!ExtraLoopUsers.empty()) {
// Okay, this instruction has a user outside of the current loop
// and varies predictably in this loop. Evaluate the value it
// Rewrite any users of the computed value outside of the loop
// with the newly computed value.
- for (unsigned i = 0, e = ExtraLoopUsers.size(); i != e; ++i)
- ExtraLoopUsers[i]->replaceUsesOfWith(I, NewVal);
+ for (unsigned i = 0, e = ExtraLoopUsers.size(); i != e; ++i) {
+ PHINode* PN = dyn_cast<PHINode>(ExtraLoopUsers[i]);
+ if (PN && PN->getNumOperands() == 2 &&
+ !L->contains(PN->getParent())) {
+ // We're dealing with an LCSSA Phi. Handle it specially.
+ Instruction* LCSSAInsertPt = BlockToInsertInto->begin();
+
+ Instruction* NewInstr = dyn_cast<Instruction>(NewVal);
+ if (NewInstr && !isa<PHINode>(NewInstr) &&
+ !L->contains(NewInstr->getParent()))
+ for (unsigned j = 0; j < NewInstr->getNumOperands(); ++j){
+ Instruction* PredI =
+ dyn_cast<Instruction>(NewInstr->getOperand(j));
+ if (PredI && L->contains(PredI->getParent())) {
+ PHINode* NewLCSSA = new PHINode(PredI->getType(),
+ PredI->getName() + ".lcssa",
+ LCSSAInsertPt);
+ NewLCSSA->addIncoming(PredI,
+ BlockToInsertInto->getSinglePredecessor());
+
+ NewInstr->replaceUsesOfWith(PredI, NewLCSSA);
+ }
+ }
+
+ PN->replaceAllUsesWith(NewVal);
+ PN->eraseFromParent();
+ } else {
+ ExtraLoopUsers[i]->replaceUsesOfWith(I, NewVal);
+ }
+ }
// If this instruction is dead now, schedule it to be removed.
if (I->use_empty())
if (PN->getType()->isInteger()) { // FIXME: when we have fast-math, enable!
SCEVHandle SCEV = SE->getSCEV(PN);
if (SCEV->hasComputableLoopEvolution(L))
- // FIXME: Without a strength reduction pass, it is an extremely bad idea
- // to indvar substitute anything more complex than a linear induction
- // variable. Doing so will put expensive multiply instructions inside
- // of the loop. For now just disable indvar subst on anything more
- // complex than a linear addrec.
+ // 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->getNumOperands() == 2 && isa<SCEVConstant>(AR->getOperand(1)))
+ if (AR->isAffine())
IndVars.push_back(std::make_pair(PN, SCEV));
}
}
SCEVExpander Rewriter(*SE, *LI);
Rewriter.getOrInsertCanonicalInductionVariable(L,
IterationCount->getType());
- LinearFunctionTestReplace(L, IterationCount, Rewriter);
+ if (Instruction *I = LinearFunctionTestReplace(L, IterationCount,
+ Rewriter)) {
+ std::set<Instruction*> InstructionsToDelete;
+ InstructionsToDelete.insert(I);
+ DeleteTriviallyDeadInstructions(InstructionsToDelete);
+ }
}
return;
}
Changed = true;
if (!isa<SCEVCouldNotCompute>(IterationCount))
- LinearFunctionTestReplace(L, IterationCount, Rewriter);
+ 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
#endif
DeleteTriviallyDeadInstructions(DeadInsts);
+
+ if (mustPreserveAnalysisID(LCSSAID)) assert(L->isLCSSAForm());
}