#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
+#include "llvm/LLVMContext.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/Dominators.h"
IVExitValue = ExitCondition->getOperand(0);
if (!L->isLoopInvariant(IVExitValue))
return false;
+ if (!IVBasedValues.count(
+ ExitCondition->getOperand(IVExitValue == ExitCondition->getOperand(0))))
+ return false;
// If start value is more then exit value where induction variable
// increments by 1 then we are potentially dealing with an infinite loop.
}
// Return V+1
-static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt) {
- ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
+static Value *getPlusOne(Value *V, bool Sign, Instruction *InsertPt,
+ LLVMContext *Context) {
+ Constant *One = Context->getConstantInt(V->getType(), 1, Sign);
return BinaryOperator::CreateAdd(V, One, "lsp", InsertPt);
}
// Return V-1
-static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt) {
- ConstantInt *One = ConstantInt::get(V->getType(), 1, Sign);
+static Value *getMinusOne(Value *V, bool Sign, Instruction *InsertPt,
+ LLVMContext *Context) {
+ Constant *One = Context->getConstantInt(V->getType(), 1, Sign);
return BinaryOperator::CreateSub(V, One, "lsp", InsertPt);
}
// Return min(V1, V1)
static Value *getMin(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
- Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
- V1, V2, "lsp", InsertPt);
+ Value *C = new ICmpInst(InsertPt,
+ Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ V1, V2, "lsp");
return SelectInst::Create(C, V1, V2, "lsp", InsertPt);
}
// Return max(V1, V2)
static Value *getMax(Value *V1, Value *V2, bool Sign, Instruction *InsertPt) {
- Value *C = new ICmpInst(Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
- V1, V2, "lsp", InsertPt);
+ Value *C = new ICmpInst(InsertPt,
+ Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT,
+ V1, V2, "lsp");
return SelectInst::Create(C, V2, V1, "lsp", InsertPt);
}
// If BR operands are not IV or not loop invariants then skip this loop.
Value *OPV = SplitCondition->getOperand(0);
Value *SplitValue = SplitCondition->getOperand(1);
- if (!L->isLoopInvariant(SplitValue)) {
- Value *T = SplitValue;
- SplitValue = OPV;
- OPV = T;
- }
+ if (!L->isLoopInvariant(SplitValue))
+ std::swap(OPV, SplitValue);
if (!L->isLoopInvariant(SplitValue))
return false;
Instruction *OPI = dyn_cast<Instruction>(OPV);
// c1 = icmp uge i32 SplitValue, StartValue
// c2 = icmp ult i32 SplitValue, ExitValue
// and i32 c1, c2
- Instruction *C1 = new ICmpInst(ExitCondition->isSignedPredicate() ?
+ Instruction *C1 = new ICmpInst(BR, ExitCondition->isSignedPredicate() ?
ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
- SplitValue, StartValue, "lisplit", BR);
+ SplitValue, StartValue, "lisplit");
CmpInst::Predicate C2P = ExitCondition->getPredicate();
BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
if (LatchBR->getOperand(0) != Header)
C2P = CmpInst::getInversePredicate(C2P);
- Instruction *C2 = new ICmpInst(C2P, SplitValue, ExitValue, "lisplit", BR);
+ Instruction *C2 = new ICmpInst(BR, C2P, SplitValue, ExitValue, "lisplit");
Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
SplitCondition->replaceAllUsesWith(NSplitCond);
if (Value *V = IVisLT(Op)) {
// Restrict upper bound.
if (IVisLE(*ExitCondition))
- V = getMinusOne(V, Sign, PHTerm);
+ V = getMinusOne(V, Sign, PHTerm, Context);
NUB = getMin(V, IVExitValue, Sign, PHTerm);
} else if (Value *V = IVisLE(Op)) {
// Restrict upper bound.
if (IVisLT(*ExitCondition))
- V = getPlusOne(V, Sign, PHTerm);
+ V = getPlusOne(V, Sign, PHTerm, Context);
NUB = getMin(V, IVExitValue, Sign, PHTerm);
} else if (Value *V = IVisGT(Op)) {
// Restrict lower bound.
- V = getPlusOne(V, Sign, PHTerm);
+ V = getPlusOne(V, Sign, PHTerm, Context);
NLB = getMax(V, IVStartValue, Sign, PHTerm);
} else if (Value *V = IVisGE(Op))
// Restrict lower bound.
// ExitBB is now dominated by CondBB
DT->changeImmediateDominator(ExitBB, CondBB);
DF->changeImmediateDominator(ExitBB, CondBB, DT);
-
- // Basicblocks dominated by ActiveBB may have ExitingBB or
- // a basic block outside the loop in their DF list. If so,
- // replace it with CondBB.
- DomTreeNode *Node = DT->getNode(ActiveBB);
- for (df_iterator<DomTreeNode *> DI = df_begin(Node), DE = df_end(Node);
- DI != DE; ++DI) {
- BasicBlock *BB = DI->getBlock();
- DominanceFrontier::iterator BBDF = DF->find(BB);
+
+ // Blocks outside the loop may have been in the dominance frontier of blocks
+ // inside the condition; this is now impossible because the blocks inside the
+ // condition no loger dominate the exit. Remove the relevant blocks from
+ // the dominance frontiers.
+ for (Loop::block_iterator I = LP->block_begin(), E = LP->block_end();
+ I != E; ++I) {
+ if (*I == CondBB || !DT->dominates(CondBB, *I)) continue;
+ DominanceFrontier::iterator BBDF = DF->find(*I);
DominanceFrontier::DomSetType::iterator DomSetI = BBDF->second.begin();
DominanceFrontier::DomSetType::iterator DomSetE = BBDF->second.end();
while (DomSetI != DomSetE) {
DominanceFrontier::DomSetType::iterator CurrentItr = DomSetI;
++DomSetI;
BasicBlock *DFBB = *CurrentItr;
- if (DFBB == ExitingBB || !L->contains(DFBB)) {
+ if (!LP->contains(DFBB))
BBDF->second.erase(DFBB);
- BBDF->second.insert(CondBB);
- }
}
}
}
/* Do nothing */
}
else if (IVisLE(*SplitCondition)) {
- AEV = getPlusOne(SplitValue, Sign, PHTerm);
- BSV = getPlusOne(SplitValue, Sign, PHTerm);
+ AEV = getPlusOne(SplitValue, Sign, PHTerm, Context);
+ BSV = getPlusOne(SplitValue, Sign, PHTerm, Context);
} else {
assert (0 && "Unexpected split condition!");
}
}
else if (IVisLE(*ExitCondition)) {
if (IVisLT(*SplitCondition)) {
- AEV = getMinusOne(SplitValue, Sign, PHTerm);
+ AEV = getMinusOne(SplitValue, Sign, PHTerm, Context);
}
else if (IVisLE(*SplitCondition)) {
- BSV = getPlusOne(SplitValue, Sign, PHTerm);
+ BSV = getPlusOne(SplitValue, Sign, PHTerm, Context);
} else {
assert (0 && "Unexpected split condition!");
}