#include "llvm/Transforms/Scalar.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.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/Transforms/Utils/Local.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
bool runOnLoop(Loop *L, LPPassManager &LPM);
void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<ScalarEvolution>();
AU.addPreserved<ScalarEvolution>();
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
Loop *L;
LPPassManager *LPM;
LoopInfo *LI;
- ScalarEvolution *SE;
DominatorTree *DT;
DominanceFrontier *DF;
if (!L->getSubLoops().empty())
return false;
- SE = &getAnalysis<ScalarEvolution>();
DT = &getAnalysis<DominatorTree>();
LI = &getAnalysis<LoopInfo>();
DF = &getAnalysis<DominanceFrontier>();
}
// Reject loop if loop exit condition is not suitable.
- SmallVector<BasicBlock *, 2> EBs;
- L->getExitingBlocks(EBs);
- if (EBs.size() != 1)
+ BasicBlock *ExitingBlock = L->getExitingBlock();
+ if (!ExitingBlock)
return false;
- BranchInst *EBR = dyn_cast<BranchInst>(EBs[0]->getTerminator());
+ BranchInst *EBR = dyn_cast<BranchInst>(ExitingBlock->getTerminator());
if (!EBR) return false;
ExitCondition = dyn_cast<ICmpInst>(EBR->getCondition());
if (!ExitCondition) return false;
- if (EBs[0] != L->getLoopLatch()) return false;
+ if (ExitingBlock != L->getLoopLatch()) return false;
IVExitValue = ExitCondition->getOperand(1);
if (!L->isLoopInvariant(IVExitValue))
IVExitValue = ExitCondition->getOperand(0);
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;
// and i32 c1, c2
Instruction *C1 = new ICmpInst(ExitCondition->isSignedPredicate() ?
ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE,
- SplitValue, IVStartValue, "lisplit", BR);
+ SplitValue, StartValue, "lisplit", BR);
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, IVExitValue, "lisplit", BR);
+ Instruction *C2 = new ICmpInst(C2P, SplitValue, ExitValue, "lisplit", BR);
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);
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
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);