// This file implements Loop Index Splitting Pass. This pass handles three
// kinds of loops.
//
-// [1] Loop is eliminated when loop body is executed only once. For example,
+// [1] A loop may be eliminated if the body is executed exactly once.
+// For example,
+//
// for (i = 0; i < N; ++i) {
-// if ( i == X) {
-// ...
+// if (i == X) {
+// body;
// }
// }
//
-// [2] Loop's iteration space is shrunk if loop body is executed for certain
-// range only. For example,
-//
+// is transformed to
+//
+// i = X;
+// body;
+//
+// [2] A loop's iteration space may be shrunk if the loop body is executed
+// for a proper sub-range of the loop's iteration space. For example,
+//
// for (i = 0; i < N; ++i) {
-// if ( i > A && i < B) {
+// if (i > A && i < B) {
// ...
// }
// }
-// is trnasformed to iterators from A to B, if A > 0 and B < N.
//
-// [3] Loop is split if the loop body is dominated by an branch. For example,
+// is transformed to iterators from A to B, if A > 0 and B < N.
+//
+// [3] A loop may be split if the loop body is dominated by a branch.
+// For example,
//
// for (i = LB; i < UB; ++i) { if (i < SV) A; else B; }
//
// is transformed into
+//
// AEV = BSV = SV
// for (i = LB; i < min(UB, AEV); ++i)
// A;
// for (i = max(LB, BSV); i < UB; ++i);
// B;
+//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "loop-index-split"
-
#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"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
-#include "llvm/Support/Compiler.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
namespace {
- class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass {
-
+ class LoopIndexSplit : public LoopPass {
public:
static char ID; // Pass ID, replacement for typeid
LoopIndexSplit() : LoopPass(&ID) {}
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 = ConstantInt::get(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 = ConstantInt::get(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);
- if (!OPI) return false;
+ if (!OPI)
+ return false;
if (OPI->getParent() != Header || isUsedOutsideLoop(OPI, L))
return false;
-
+ Value *StartValue = IVStartValue;
+ Value *ExitValue = IVExitValue;;
+
+ if (OPV != IndVar) {
+ // If BR operand is IV based then use this operand to calculate
+ // effective conditions for loop body.
+ BinaryOperator *BOPV = dyn_cast<BinaryOperator>(OPV);
+ if (!BOPV)
+ return false;
+ if (BOPV->getOpcode() != Instruction::Add)
+ return false;
+ StartValue = BinaryOperator::CreateAdd(OPV, StartValue, "" , BR);
+ ExitValue = BinaryOperator::CreateAdd(OPV, ExitValue, "" , BR);
+ }
+
if (!cleanBlock(Header))
return false;
// 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, IVStartValue, "lisplit", BR);
+ SplitValue, StartValue, "lisplit");
CmpInst::Predicate C2P = ExitCondition->getPredicate();
BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
- if (LatchBR->getOperand(0) != Header)
+ if (LatchBR->getOperand(1) != Header)
C2P = CmpInst::getInversePredicate(C2P);
- Instruction *C2 = new ICmpInst(C2P, SplitValue, IVExitValue, "lisplit", BR);
+ Instruction *C2 = new ICmpInst(BR, C2P, SplitValue, ExitValue, "lisplit");
Instruction *NSplitCond = BinaryOperator::CreateAnd(C1, C2, "lisplit", BR);
SplitCondition->replaceAllUsesWith(NSplitCond);
if (Header != *SI)
LatchSucc = *SI;
}
- LatchBR->setUnconditionalDest(LatchSucc);
- // Remove IVIncrement
- IVIncrement->replaceAllUsesWith(UndefValue::get(IVIncrement->getType()));
- IVIncrement->eraseFromParent();
+ // Clean up latch block.
+ Value *LatchBRCond = LatchBR->getCondition();
+ LatchBR->setUnconditionalDest(LatchSucc);
+ RecursivelyDeleteTriviallyDeadInstructions(LatchBRCond);
LPM->deleteLoopFromQueue(L);
EBR->setSuccessor(1, T);
}
+ LLVMContext &Context = Op.getContext();
+
// New upper and lower bounds.
Value *NLB = NULL;
Value *NUB = NULL;
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.
BasicBlock *ExitingBlock = ExitCondition->getParent();
if (!cleanBlock(ExitingBlock)) return false;
+ // If the merge point for BR is not loop latch then skip this loop.
+ if (BR->getSuccessor(0) != Latch) {
+ DominanceFrontier::iterator DF0 = DF->find(BR->getSuccessor(0));
+ assert (DF0 != DF->end() && "Unable to find dominance frontier");
+ if (!DF0->second.count(Latch))
+ return false;
+ }
+
+ if (BR->getSuccessor(1) != Latch) {
+ DominanceFrontier::iterator DF1 = DF->find(BR->getSuccessor(1));
+ assert (DF1 != DF->end() && "Unable to find dominance frontier");
+ if (!DF1->second.count(Latch))
+ return false;
+ }
+
// Verify that loop exiting block has only two predecessor, where one pred
// is split condition block. The other predecessor will become exiting block's
// dominator after CFG is updated. TODO : Handle CFG's where exiting block has
E = df_end(DN); DI != E; ++DI) {
BasicBlock *BB = DI->getBlock();
WorkList.push_back(BB);
- BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy));
+ BB->replaceAllUsesWith(UndefValue::get(
+ Type::getLabelTy(DeadBB->getContext())));
}
while (!WorkList.empty()) {
BasicBlock *BB = WorkList.back(); WorkList.pop_back();
+ LPM->deleteSimpleAnalysisValue(BB, LP);
for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end();
BBI != BBE; ) {
Instruction *I = BBI;
++BBI;
I->replaceAllUsesWith(UndefValue::get(I->getType()));
+ LPM->deleteSimpleAnalysisValue(I, LP);
I->eraseFromParent();
}
- LPM->deleteSimpleAnalysisValue(BB, LP);
DT->eraseNode(BB);
DF->removeBlock(BB);
LI->removeBlock(BB);
// 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);
- }
}
}
}
BasicBlock *ExitingBlock = ExitCondition->getParent();
if (!cleanBlock(ExitingBlock)) return false;
+ LLVMContext &Context = Header->getContext();
+
for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I) {
BranchInst *BR = dyn_cast<BranchInst>((*I)->getTerminator());
/* 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!");
}
DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock);
DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT);
- //[*] Split ALoop's exit edge. This creates a new block which
+ //[*] Split ALoop's exit edge. This creates a new block which
// serves two purposes. First one is to hold PHINode defnitions
// to ensure that ALoop's LCSSA form. Second use it to act
// as a preheader for BLoop.
|| isa<DbgInfoIntrinsic>(I))
continue;
- if (I->mayWriteToMemory())
+ if (I->mayHaveSideEffects())
return false;
// I is used only inside this block then it is OK.
projects / oota-llvm.git / blobdiff