public:
static char ID; // Pass identification, replacement for typeid
- IndVarSimplify() : LoopPass((intptr_t)&ID) {}
+ IndVarSimplify() : LoopPass(&ID) {}
bool runOnLoop(Loop *L, LPPassManager &LPM);
bool doInitialization(Loop *L, LPPassManager &LPM);
std::set<Instruction*> &DeadInsts);
Instruction *LinearFunctionTestReplace(Loop *L, SCEV *IterationCount,
SCEVExpander &RW);
- void RewriteLoopExitValues(Loop *L);
+ void RewriteLoopExitValues(Loop *L, SCEV *IterationCount);
void DeleteTriviallyDeadInstructions(std::set<Instruction*> &Insts);
+
+ void OptimizeCanonicalIVType(Loop *L);
};
}
NewPhi->addIncoming(Constant::getNullValue(NewPhi->getType()), Preheader);
// Create the new add instruction.
- Value *NewAdd = BinaryOperator::createAdd(NewPhi, AddedVal,
+ Value *NewAdd = BinaryOperator::CreateAdd(NewPhi, AddedVal,
GEPI->getName()+".rec", GEPI);
NewPhi->addIncoming(NewAdd, PN->getIncomingBlock(BackedgeIdx));
/// 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) {
+void IndVarSimplify::RewriteLoopExitValues(Loop *L, SCEV *IterationCount) {
BasicBlock *Preheader = L->getLoopPreheader();
// Scan all of the instructions in the loop, looking at those that have
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));
+ bool HasConstantItCount = isa<SCEVConstant>(IterationCount);
std::set<Instruction*> InstructionsToDelete;
std::map<Instruction*, Value*> ExitValues;
//
SCEVHandle IterationCount = SE->getIterationCount(L);
if (!isa<SCEVCouldNotCompute>(IterationCount))
- RewriteLoopExitValues(L);
+ RewriteLoopExitValues(L, IterationCount);
// Next, analyze all of the induction variables in the loop, canonicalizing
// auxillary induction variables.
DOUT << "INDVARS: New CanIV: " << *IndVar;
if (!isa<SCEVCouldNotCompute>(IterationCount)) {
- if (IterationCount->getType()->getPrimitiveSizeInBits() <
- LargestType->getPrimitiveSizeInBits())
- IterationCount = SE->getZeroExtendExpr(IterationCount, LargestType);
- else if (IterationCount->getType() != LargestType)
- IterationCount = SE->getTruncateExpr(IterationCount, LargestType);
+ IterationCount = SE->getTruncateOrZeroExtend(IterationCount, LargestType);
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;
+ BasicBlock::iterator InsertPt = Header->getFirstNonPHI();
// If there were induction variables of other sizes, cast the primary
// induction variable to the right size for them, avoiding the need for the
// 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);
#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 (LoopInfo::block_iterator I = L->block_begin(), E = L->block_end();
+ I != E; ++I) {
+ BasicBlock *BB = *I;
+ if (LI->getLoopFor(BB) == L) { // Not in a subloop...
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
if (I->getType()->isInteger() && // Is an integer instruction
!I->use_empty() &&
}
}
}
+ }
#endif
DeleteTriviallyDeadInstructions(DeadInsts);
-
+ OptimizeCanonicalIVType(L);
assert(L->isLCSSAForm());
return Changed;
}
+
+/// OptimizeCanonicalIVType - If loop induction variable is always
+/// sign or zero extended then extend the type of the induction
+/// variable.
+void IndVarSimplify::OptimizeCanonicalIVType(Loop *L) {
+ PHINode *PH = L->getCanonicalInductionVariable();
+ if (!PH) return;
+
+ // Check loop iteration count.
+ SCEVHandle IC = SE->getIterationCount(L);
+ if (isa<SCEVCouldNotCompute>(IC)) return;
+ SCEVConstant *IterationCount = dyn_cast<SCEVConstant>(IC);
+ if (!IterationCount) return;
+
+ unsigned IncomingEdge = L->contains(PH->getIncomingBlock(0));
+ unsigned BackEdge = IncomingEdge^1;
+
+ // Check IV uses. If all IV uses are either SEXT or ZEXT (except
+ // IV increment instruction) then this IV is suitable for this
+ // transformation.
+ bool isSEXT = false;
+ BinaryOperator *Incr = NULL;
+ const Type *NewType = NULL;
+ for(Value::use_iterator UI = PH->use_begin(), UE = PH->use_end();
+ UI != UE; ++UI) {
+ const Type *CandidateType = NULL;
+ if (ZExtInst *ZI = dyn_cast<ZExtInst>(UI))
+ CandidateType = ZI->getDestTy();
+ else if (SExtInst *SI = dyn_cast<SExtInst>(UI)) {
+ CandidateType = SI->getDestTy();
+ isSEXT = true;
+ }
+ else if ((Incr = dyn_cast<BinaryOperator>(UI))) {
+ // Validate IV increment instruction.
+ if (PH->getIncomingValue(BackEdge) == Incr)
+ continue;
+ }
+ if (!CandidateType) {
+ NewType = NULL;
+ break;
+ }
+ if (!NewType)
+ NewType = CandidateType;
+ else if (NewType != CandidateType) {
+ NewType = NULL;
+ break;
+ }
+ }
+
+ // IV uses are not suitable then avoid this transformation.
+ if (!NewType || !Incr)
+ return;
+
+ // IV increment instruction has two uses, one is loop exit condition
+ // and second is the IV (phi node) itself.
+ ICmpInst *Exit = NULL;
+ for(Value::use_iterator II = Incr->use_begin(), IE = Incr->use_end();
+ II != IE; ++II) {
+ if (PH == *II) continue;
+ Exit = dyn_cast<ICmpInst>(*II);
+ break;
+ }
+ if (!Exit) return;
+ ConstantInt *EV = dyn_cast<ConstantInt>(Exit->getOperand(0));
+ if (!EV)
+ EV = dyn_cast<ConstantInt>(Exit->getOperand(1));
+ if (!EV) return;
+
+ // Check iteration count max value to avoid loops that wrap around IV.
+ APInt ICount = IterationCount->getValue()->getValue();
+ if (ICount.isNegative()) return;
+ uint32_t BW = PH->getType()->getPrimitiveSizeInBits();
+ APInt Max = (isSEXT ? APInt::getSignedMaxValue(BW) : APInt::getMaxValue(BW));
+ if (ICount.getZExtValue() > Max.getZExtValue()) return;
+
+ // Extend IV type.
+
+ SCEVExpander Rewriter(*SE, *LI);
+ Value *NewIV = Rewriter.getOrInsertCanonicalInductionVariable(L,NewType);
+ PHINode *NewPH = cast<PHINode>(NewIV);
+ Instruction *NewIncr = cast<Instruction>(NewPH->getIncomingValue(BackEdge));
+
+ // Replace all SEXT or ZEXT uses.
+ SmallVector<Instruction *, 4> PHUses;
+ for(Value::use_iterator UI = PH->use_begin(), UE = PH->use_end();
+ UI != UE; ++UI) {
+ Instruction *I = cast<Instruction>(UI);
+ PHUses.push_back(I);
+ }
+ while (!PHUses.empty()){
+ Instruction *Use = PHUses.back(); PHUses.pop_back();
+ if (Incr == Use) continue;
+
+ SE->deleteValueFromRecords(Use);
+ Use->replaceAllUsesWith(NewIV);
+ Use->eraseFromParent();
+ }
+
+ // Replace exit condition.
+ ConstantInt *NEV = ConstantInt::get(NewType, EV->getZExtValue());
+ Instruction *NE = new ICmpInst(Exit->getPredicate(),
+ NewIncr, NEV, "new.exit",
+ Exit->getParent()->getTerminator());
+ SE->deleteValueFromRecords(Exit);
+ Exit->replaceAllUsesWith(NE);
+ Exit->eraseFromParent();
+
+ // Remove old IV and increment instructions.
+ SE->deleteValueFromRecords(PH);
+ PH->removeIncomingValue((unsigned)0);
+ PH->removeIncomingValue((unsigned)0);
+ SE->deleteValueFromRecords(Incr);
+ Incr->eraseFromParent();
+}
+
projects / oota-llvm.git / blobdiff