//
//===----------------------------------------------------------------------===//
//
-// This file implements the Dead Loop Elimination Pass. This pass is
-// responsible for eliminating loops with non-infinite computable trip counts
-// that have no side effects or volatile instructions, and do not contribute
-// to the computation of the function's return value.
+// This file implements the Dead Loop Deletion Pass. This pass is responsible
+// for eliminating loops with non-infinite computable trip counts that have no
+// side effects or volatile instructions, and do not contribute to the
+// computation of the function's return value.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/SmallVector.h"
class VISIBILITY_HIDDEN LoopDeletion : public LoopPass {
public:
static char ID; // Pass ID, replacement for typeid
- LoopDeletion() : LoopPass((intptr_t)&ID) { }
+ LoopDeletion() : LoopPass(&ID) {}
// Possibly eliminate loop L if it is dead.
bool runOnLoop(Loop* L, LPPassManager& LPM);
bool IsLoopInvariantInst(Instruction *I, Loop* L);
virtual void getAnalysisUsage(AnalysisUsage& AU) const {
+ AU.addRequired<ScalarEvolution>();
AU.addRequired<DominatorTree>();
AU.addRequired<LoopInfo>();
AU.addRequiredID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
+ AU.addPreserved<ScalarEvolution>();
AU.addPreserved<DominatorTree>();
AU.addPreserved<LoopInfo>();
AU.addPreservedID(LoopSimplifyID);
AU.addPreservedID(LCSSAID);
}
};
-
- char LoopDeletion::ID = 0;
- RegisterPass<LoopDeletion> X ("loop-deletion", "Delete dead loops");
}
+
+char LoopDeletion::ID = 0;
+static RegisterPass<LoopDeletion> X("loop-deletion", "Delete dead loops");
-LoopPass* llvm::createLoopDeletionPass() {
+Pass* llvm::createLoopDeletionPass() {
return new LoopDeletion();
}
/// SingleDominatingExit - Checks that there is only a single blocks that
-/// branches out of the loop, and that it also dominates the latch block. Loops
+/// branches out of the loop, and that it also g the latch block. Loops
/// with multiple or non-latch-dominating exiting blocks could be dead, but we'd
/// have to do more extensive analysis to make sure, for instance, that the
-/// control flow logic involves was or could be made loop-invariant.
+/// control flow logic involved was or could be made loop-invariant.
bool LoopDeletion::SingleDominatingExit(Loop* L,
SmallVector<BasicBlock*, 4>& exitingBlocks) {
return false;
DominatorTree& DT = getAnalysis<DominatorTree>();
- if (DT.dominates(exitingBlocks[0], latch))
- return true;
- else
- return false;
+ return DT.dominates(exitingBlocks[0], latch);
}
/// IsLoopInvariantInst - Checks if an instruction is invariant with respect to
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
if (!L->isLoopInvariant(I->getOperand(i)))
return false;
-
+
// If we got this far, the instruction is loop invariant!
return true;
}
/// NOTE: This entire process relies pretty heavily on LoopSimplify and LCSSA
/// in order to make various safety checks work.
bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) {
- SmallVector<BasicBlock*, 4> exitingBlocks;
- L->getExitingBlocks(exitingBlocks);
-
- SmallVector<BasicBlock*, 4> exitBlocks;
- L->getUniqueExitBlocks(exitBlocks);
-
- // We require that the loop only have a single exit block. Otherwise, we'd
- // be in the situation of needing to be able to solve statically which exit
- // block will be branced to, or trying to preserve the branching logic in
- // a loop invariant manner.
- if (exitBlocks.size() != 1)
- return false;
-
// We can only remove the loop if there is a preheader that we can
// branch from after removing it.
BasicBlock* preheader = L->getLoopPreheader();
if (L->begin() != L->end())
return false;
- // Don't remove loops for which we can't solve the trip count.
- // They could be infinite, in which case we'd be changing program behavior.
- if (!L->getTripCount())
+ SmallVector<BasicBlock*, 4> exitingBlocks;
+ L->getExitingBlocks(exitingBlocks);
+
+ SmallVector<BasicBlock*, 4> exitBlocks;
+ L->getUniqueExitBlocks(exitBlocks);
+
+ // We require that the loop only have a single exit block. Otherwise, we'd
+ // be in the situation of needing to be able to solve statically which exit
+ // block will be branched to, or trying to preserve the branching logic in
+ // a loop invariant manner.
+ if (exitBlocks.size() != 1)
return false;
// Loops with multiple exits or exits that don't dominate the latch
if (!IsLoopDead(L, exitingBlocks, exitBlocks))
return false;
+ // Don't remove loops for which we can't solve the trip count.
+ // They could be infinite, in which case we'd be changing program behavior.
+ ScalarEvolution& SE = getAnalysis<ScalarEvolution>();
+ SCEVHandle S = SE.getIterationCount(L);
+ if (isa<SCEVCouldNotCompute>(S))
+ return false;
+
// Now that we know the removal is safe, remove the loop by changing the
- // branch from the preheader to go to the single exiting block.
+ // branch from the preheader to go to the single exit block.
BasicBlock* exitBlock = exitBlocks[0];
+ BasicBlock* exitingBlock = exitingBlocks[0];
// Because we're deleting a large chunk of code at once, the sequence in which
// we remove things is very important to avoid invalidation issues. Don't
for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
BI != BE; ) {
Instruction* I = BI++;
- if (I->getNumUses() > 0 && IsLoopInvariantInst(I, L))
+ if (!I->use_empty() && IsLoopInvariantInst(I, L))
I->moveBefore(preheader->getTerminator());
}
// the preheader instead of the exiting block.
BasicBlock::iterator BI = exitBlock->begin();
while (PHINode* P = dyn_cast<PHINode>(BI)) {
- P->replaceUsesOfWith(exitBlock, preheader);
+ P->replaceUsesOfWith(exitingBlock, preheader);
BI++;
}
ChildNodes.clear();
DT.eraseNode(*LI);
- // Drop all references between the instructions and the block so
- // that we don't have reference counting problems later.
+ // Remove instructions that we're deleting from ScalarEvolution.
for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end();
- BI != BE; ++BI) {
- BI->dropAllReferences();
- }
+ BI != BE; ++BI)
+ SE.deleteValueFromRecords(BI);
+
+ SE.deleteValueFromRecords(*LI);
+ // Remove the block from the reference counting scheme, so that we can
+ // delete it freely later.
(*LI)->dropAllReferences();
}
projects / oota-llvm.git / blobdiff