diff options
author | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
---|---|---|
committer | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
commit | cd749a9c07f1de2fb8affde90537efa4bc3e7c54 (patch) | |
tree | b21f6de4e08b89bb7931806bab798fc2a5e3a686 /lib/Transforms/Scalar/LoopDeletion.cpp | |
parent | 72621d11de5b873f1695f391eb95f0b336c3d2d4 (diff) | |
download | FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.zip FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.tar.gz |
Update llvm to r84119.
Diffstat (limited to 'lib/Transforms/Scalar/LoopDeletion.cpp')
-rw-r--r-- | lib/Transforms/Scalar/LoopDeletion.cpp | 70 |
1 files changed, 20 insertions, 50 deletions
diff --git a/lib/Transforms/Scalar/LoopDeletion.cpp b/lib/Transforms/Scalar/LoopDeletion.cpp index 302cdec..5f93756 100644 --- a/lib/Transforms/Scalar/LoopDeletion.cpp +++ b/lib/Transforms/Scalar/LoopDeletion.cpp @@ -15,19 +15,17 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "loop-delete" - #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" - using namespace llvm; STATISTIC(NumDeleted, "Number of loops deleted"); namespace { - class VISIBILITY_HIDDEN LoopDeletion : public LoopPass { + class LoopDeletion : public LoopPass { public: static char ID; // Pass ID, replacement for typeid LoopDeletion() : LoopPass(&ID) {} @@ -38,9 +36,9 @@ namespace { bool SingleDominatingExit(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks); bool IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, - SmallVector<BasicBlock*, 4>& exitBlocks); - bool IsLoopInvariantInst(Instruction *I, Loop* L); - + SmallVector<BasicBlock*, 4>& exitBlocks, + bool &Changed, BasicBlock *Preheader); + virtual void getAnalysisUsage(AnalysisUsage& AU) const { AU.addRequired<ScalarEvolution>(); AU.addRequired<DominatorTree>(); @@ -84,32 +82,13 @@ bool LoopDeletion::SingleDominatingExit(Loop* L, return DT.dominates(exitingBlocks[0], latch); } -/// IsLoopInvariantInst - Checks if an instruction is invariant with respect to -/// a loop, which is defined as being true if all of its operands are defined -/// outside of the loop. These instructions can be hoisted out of the loop -/// if their results are needed. This could be made more aggressive by -/// recursively checking the operands for invariance, but it's not clear that -/// it's worth it. -bool LoopDeletion::IsLoopInvariantInst(Instruction *I, Loop* L) { - // PHI nodes are not loop invariant if defined in the loop. - if (isa<PHINode>(I) && L->contains(I->getParent())) - return false; - - // The instruction is loop invariant if all of its operands are loop-invariant - 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; -} - /// IsLoopDead - Determined if a loop is dead. This assumes that we've already /// checked for unique exit and exiting blocks, and that the code is in LCSSA /// form. bool LoopDeletion::IsLoopDead(Loop* L, SmallVector<BasicBlock*, 4>& exitingBlocks, - SmallVector<BasicBlock*, 4>& exitBlocks) { + SmallVector<BasicBlock*, 4>& exitBlocks, + bool &Changed, BasicBlock *Preheader) { BasicBlock* exitingBlock = exitingBlocks[0]; BasicBlock* exitBlock = exitBlocks[0]; @@ -122,7 +101,7 @@ bool LoopDeletion::IsLoopDead(Loop* L, while (PHINode* P = dyn_cast<PHINode>(BI)) { Value* incoming = P->getIncomingValueForBlock(exitingBlock); if (Instruction* I = dyn_cast<Instruction>(incoming)) - if (!IsLoopInvariantInst(I, L)) + if (!L->makeLoopInvariant(I, Changed, Preheader->getTerminator())) return false; BI++; @@ -181,15 +160,16 @@ bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { return false; // Finally, we have to check that the loop really is dead. - if (!IsLoopDead(L, exitingBlocks, exitBlocks)) - return false; + bool Changed = false; + if (!IsLoopDead(L, exitingBlocks, exitBlocks, Changed, preheader)) + return Changed; // 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>(); - const SCEV* S = SE.getBackedgeTakenCount(L); + const SCEV *S = SE.getBackedgeTakenCount(L); if (isa<SCEVCouldNotCompute>(S)) - return false; + return Changed; // Now that we know the removal is safe, remove the loop by changing the // branch from the preheader to go to the single exit block. @@ -199,18 +179,12 @@ bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { // 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 // mess with this unless you have good reason and know what you're doing. - - // Move simple loop-invariant expressions out of the loop, since they - // might be needed by the exit phis. - for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); - LI != LE; ++LI) - for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); - BI != BE; ) { - Instruction* I = BI++; - if (!I->use_empty() && IsLoopInvariantInst(I, L)) - I->moveBefore(preheader->getTerminator()); - } - + + // Tell ScalarEvolution that the loop is deleted. Do this before + // deleting the loop so that ScalarEvolution can look at the loop + // to determine what it needs to clean up. + SE.forgetLoopBackedgeTakenCount(L); + // Connect the preheader directly to the exit block. TerminatorInst* TI = preheader->getTerminator(); TI->replaceUsesOfWith(L->getHeader(), exitBlock); @@ -248,11 +222,6 @@ bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { (*LI)->dropAllReferences(); } - // Tell ScalarEvolution that the loop is deleted. Do this before - // deleting the loop so that ScalarEvolution can look at the loop - // to determine what it needs to clean up. - SE.forgetLoopBackedgeTakenCount(L); - // Erase the instructions and the blocks without having to worry // about ordering because we already dropped the references. // NOTE: This iteration is safe because erasing the block does not remove its @@ -273,8 +242,9 @@ bool LoopDeletion::runOnLoop(Loop* L, LPPassManager& LPM) { // The last step is to inform the loop pass manager that we've // eliminated this loop. LPM.deleteLoopFromQueue(L); + Changed = true; NumDeleted++; - return true; + return Changed; } |