From f6e0e88f125e4b4258978d64dafaaf95cd7ad1e7 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Tue, 29 Apr 2008 19:58:07 +0000 Subject: Rename DeadLoopElimination to LoopDeletion, part one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@50436 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/DeadLoopElimination.cpp | 260 -------------------------- lib/Transforms/Scalar/LoopDeletion.cpp | 260 ++++++++++++++++++++++++++ 2 files changed, 260 insertions(+), 260 deletions(-) delete mode 100644 lib/Transforms/Scalar/DeadLoopElimination.cpp create mode 100644 lib/Transforms/Scalar/LoopDeletion.cpp (limited to 'lib/Transforms') diff --git a/lib/Transforms/Scalar/DeadLoopElimination.cpp b/lib/Transforms/Scalar/DeadLoopElimination.cpp deleted file mode 100644 index fc11cab..0000000 --- a/lib/Transforms/Scalar/DeadLoopElimination.cpp +++ /dev/null @@ -1,260 +0,0 @@ -//===- DeadLoopElimination.cpp - Dead Loop Elimination Pass ---------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the Dead Loop Elimination Pass. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "dead-loop" - -#include "llvm/Transforms/Scalar.h" -#include "llvm/Instruction.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/SmallVector.h" - -using namespace llvm; - -STATISTIC(NumDeleted, "Number of loops deleted"); - -namespace { - class VISIBILITY_HIDDEN DeadLoopElimination : public LoopPass { - public: - static char ID; // Pass ID, replacement for typeid - DeadLoopElimination() : LoopPass((intptr_t)&ID) { } - - // Possibly eliminate loop L if it is dead. - bool runOnLoop(Loop* L, LPPassManager& LPM); - - bool SingleDominatingExit(Loop* L); - bool IsLoopDead(Loop* L); - bool IsLoopInvariantInst(Instruction *I, Loop* L); - - virtual void getAnalysisUsage(AnalysisUsage& AU) const { - AU.addRequired(); - AU.addRequired(); - AU.addRequiredID(LoopSimplifyID); - AU.addRequiredID(LCSSAID); - - AU.addPreserved(); - AU.addPreserved(); - AU.addPreservedID(LoopSimplifyID); - AU.addPreservedID(LCSSAID); - } - }; - - char DeadLoopElimination::ID = 0; - RegisterPass X ("dead-loop", "Eliminate dead loops"); -} - -LoopPass* llvm::createDeadLoopEliminationPass() { - return new DeadLoopElimination(); -} - -bool DeadLoopElimination::SingleDominatingExit(Loop* L) { - SmallVector exitingBlocks; - L->getExitingBlocks(exitingBlocks); - - if (exitingBlocks.size() != 1) - return 0; - - BasicBlock* latch = L->getLoopLatch(); - if (!latch) - return 0; - - DominatorTree& DT = getAnalysis(); - if (DT.dominates(exitingBlocks[0], latch)) - return exitingBlocks[0]; - else - return 0; -} - -bool DeadLoopElimination::IsLoopInvariantInst(Instruction *I, Loop* L) { - // PHI nodes are not loop invariant if defined in the loop. - if (isa(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; -} - -bool DeadLoopElimination::IsLoopDead(Loop* L) { - SmallVector exitingBlocks; - L->getExitingBlocks(exitingBlocks); - BasicBlock* exitingBlock = exitingBlocks[0]; - - // Get the set of out-of-loop blocks that the exiting block branches to. - SmallVector exitBlocks; - L->getUniqueExitBlocks(exitBlocks); - if (exitBlocks.size() > 1) - return false; - BasicBlock* exitBlock = exitBlocks[0]; - - // Make sure that all PHI entries coming from the loop are loop invariant. - BasicBlock::iterator BI = exitBlock->begin(); - while (PHINode* P = dyn_cast(BI)) { - Value* incoming = P->getIncomingValueForBlock(exitingBlock); - if (Instruction* I = dyn_cast(incoming)) - if (!IsLoopInvariantInst(I, L)) - return false; - - BI++; - } - - // Make sure that no instructions in the block have potential side-effects. - 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; ++BI) { - if (BI->mayWriteToMemory()) - return false; - } - } - - return true; -} - -/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the -/// observable behavior of the program other than finite running time. Note -/// we do ensure that this never remove a loop that might be infinite, as doing -/// so could change the halting/non-halting nature of a program. -bool DeadLoopElimination::runOnLoop(Loop* L, LPPassManager& LPM) { - // 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()) - 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 (!preheader) - return false; - - // We can't remove loops that contain subloops. If the subloops were dead, - // they would already have been removed in earlier executions of this pass. - if (L->begin() != L->end()) - return false; - - // Loops with multiple exits or exits that don't dominate the latch - // are too complicated to handle correctly. - if (!SingleDominatingExit(L)) - return false; - - // Finally, we have to check that the loop really is dead. - if (!IsLoopDead(L)) - return false; - - // Now that we know the removal is safe, change the branch from the preheader - // to go to the single exiting block. - SmallVector exitingBlocks; - L->getExitingBlocks(exitingBlocks); - BasicBlock* exitingBlock = exitingBlocks[0]; - - SmallVector exitBlocks; - L->getUniqueExitBlocks(exitBlocks); - BasicBlock* exitBlock = exitBlocks[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 - // 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->getNumUses() > 0 && IsLoopInvariantInst(I, L)) - I->moveBefore(preheader->getTerminator()); - } - - // Connect the preheader directly to the exit block. - TerminatorInst* TI = preheader->getTerminator(); - if (BranchInst* BI = dyn_cast(TI)) { - if (BI->isUnconditional()) - BI->setSuccessor(0, exitBlock); - else if (L->contains(BI->getSuccessor(0))) - BI->setSuccessor(0, exitBlock); - else - BI->setSuccessor(1, exitBlock); - } else { - // FIXME: Support switches - return false; - } - - // Rewrite phis in the exit block to get their inputs from - // the preheader instead of the exiting block. - BasicBlock::iterator BI = exitBlock->begin(); - while (PHINode* P = dyn_cast(BI)) { - unsigned i = P->getBasicBlockIndex(exitingBlock); - P->setIncomingBlock(i, preheader); - BI++; - } - - // Update lots of internal structures... - DominatorTree& DT = getAnalysis(); - for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); - LI != LE; ++LI) { - // Move all of the block's children to be children of the preheader, which - // allows us to remove the domtree entry for the block. - SmallPtrSet childNodes; - childNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); - for (SmallPtrSet::iterator DI = childNodes.begin(), - DE = childNodes.end(); DI != DE; ++DI) - DT.changeImmediateDominator(*DI, DT[preheader]); - - DT.eraseNode(*LI); - - // Drop all references between the instructions and the block so - // that we don't have reference counting problems later. - for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); - BI != BE; ++BI) { - BI->dropAllReferences(); - } - - (*LI)->dropAllReferences(); - } - - // Erase the instructions and the blocks without having to worry - // about ordering because we already dropped the references. - 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++; - I->eraseFromParent(); - } - - (*LI)->eraseFromParent(); - } - - // Finally, the blocks from loopinfo. This has to happen late because - // otherwise our loop iterators won't work. - LoopInfo& loopInfo = getAnalysis(); - SmallPtrSet blocks; - blocks.insert(L->block_begin(), L->block_end()); - for (SmallPtrSet::iterator I = blocks.begin(), - E = blocks.end(); I != E; ++I) - loopInfo.removeBlock(*I); - - // The last step is to inform the loop pass manager that we've - // eliminated this loop. - LPM.deleteLoopFromQueue(L); - - NumDeleted++; - - return true; -} diff --git a/lib/Transforms/Scalar/LoopDeletion.cpp b/lib/Transforms/Scalar/LoopDeletion.cpp new file mode 100644 index 0000000..fc11cab --- /dev/null +++ b/lib/Transforms/Scalar/LoopDeletion.cpp @@ -0,0 +1,260 @@ +//===- DeadLoopElimination.cpp - Dead Loop Elimination Pass ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the Dead Loop Elimination Pass. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "dead-loop" + +#include "llvm/Transforms/Scalar.h" +#include "llvm/Instruction.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/SmallVector.h" + +using namespace llvm; + +STATISTIC(NumDeleted, "Number of loops deleted"); + +namespace { + class VISIBILITY_HIDDEN DeadLoopElimination : public LoopPass { + public: + static char ID; // Pass ID, replacement for typeid + DeadLoopElimination() : LoopPass((intptr_t)&ID) { } + + // Possibly eliminate loop L if it is dead. + bool runOnLoop(Loop* L, LPPassManager& LPM); + + bool SingleDominatingExit(Loop* L); + bool IsLoopDead(Loop* L); + bool IsLoopInvariantInst(Instruction *I, Loop* L); + + virtual void getAnalysisUsage(AnalysisUsage& AU) const { + AU.addRequired(); + AU.addRequired(); + AU.addRequiredID(LoopSimplifyID); + AU.addRequiredID(LCSSAID); + + AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); + AU.addPreservedID(LCSSAID); + } + }; + + char DeadLoopElimination::ID = 0; + RegisterPass X ("dead-loop", "Eliminate dead loops"); +} + +LoopPass* llvm::createDeadLoopEliminationPass() { + return new DeadLoopElimination(); +} + +bool DeadLoopElimination::SingleDominatingExit(Loop* L) { + SmallVector exitingBlocks; + L->getExitingBlocks(exitingBlocks); + + if (exitingBlocks.size() != 1) + return 0; + + BasicBlock* latch = L->getLoopLatch(); + if (!latch) + return 0; + + DominatorTree& DT = getAnalysis(); + if (DT.dominates(exitingBlocks[0], latch)) + return exitingBlocks[0]; + else + return 0; +} + +bool DeadLoopElimination::IsLoopInvariantInst(Instruction *I, Loop* L) { + // PHI nodes are not loop invariant if defined in the loop. + if (isa(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; +} + +bool DeadLoopElimination::IsLoopDead(Loop* L) { + SmallVector exitingBlocks; + L->getExitingBlocks(exitingBlocks); + BasicBlock* exitingBlock = exitingBlocks[0]; + + // Get the set of out-of-loop blocks that the exiting block branches to. + SmallVector exitBlocks; + L->getUniqueExitBlocks(exitBlocks); + if (exitBlocks.size() > 1) + return false; + BasicBlock* exitBlock = exitBlocks[0]; + + // Make sure that all PHI entries coming from the loop are loop invariant. + BasicBlock::iterator BI = exitBlock->begin(); + while (PHINode* P = dyn_cast(BI)) { + Value* incoming = P->getIncomingValueForBlock(exitingBlock); + if (Instruction* I = dyn_cast(incoming)) + if (!IsLoopInvariantInst(I, L)) + return false; + + BI++; + } + + // Make sure that no instructions in the block have potential side-effects. + 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; ++BI) { + if (BI->mayWriteToMemory()) + return false; + } + } + + return true; +} + +/// runOnLoop - Remove dead loops, by which we mean loops that do not impact the +/// observable behavior of the program other than finite running time. Note +/// we do ensure that this never remove a loop that might be infinite, as doing +/// so could change the halting/non-halting nature of a program. +bool DeadLoopElimination::runOnLoop(Loop* L, LPPassManager& LPM) { + // 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()) + 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 (!preheader) + return false; + + // We can't remove loops that contain subloops. If the subloops were dead, + // they would already have been removed in earlier executions of this pass. + if (L->begin() != L->end()) + return false; + + // Loops with multiple exits or exits that don't dominate the latch + // are too complicated to handle correctly. + if (!SingleDominatingExit(L)) + return false; + + // Finally, we have to check that the loop really is dead. + if (!IsLoopDead(L)) + return false; + + // Now that we know the removal is safe, change the branch from the preheader + // to go to the single exiting block. + SmallVector exitingBlocks; + L->getExitingBlocks(exitingBlocks); + BasicBlock* exitingBlock = exitingBlocks[0]; + + SmallVector exitBlocks; + L->getUniqueExitBlocks(exitBlocks); + BasicBlock* exitBlock = exitBlocks[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 + // 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->getNumUses() > 0 && IsLoopInvariantInst(I, L)) + I->moveBefore(preheader->getTerminator()); + } + + // Connect the preheader directly to the exit block. + TerminatorInst* TI = preheader->getTerminator(); + if (BranchInst* BI = dyn_cast(TI)) { + if (BI->isUnconditional()) + BI->setSuccessor(0, exitBlock); + else if (L->contains(BI->getSuccessor(0))) + BI->setSuccessor(0, exitBlock); + else + BI->setSuccessor(1, exitBlock); + } else { + // FIXME: Support switches + return false; + } + + // Rewrite phis in the exit block to get their inputs from + // the preheader instead of the exiting block. + BasicBlock::iterator BI = exitBlock->begin(); + while (PHINode* P = dyn_cast(BI)) { + unsigned i = P->getBasicBlockIndex(exitingBlock); + P->setIncomingBlock(i, preheader); + BI++; + } + + // Update lots of internal structures... + DominatorTree& DT = getAnalysis(); + for (Loop::block_iterator LI = L->block_begin(), LE = L->block_end(); + LI != LE; ++LI) { + // Move all of the block's children to be children of the preheader, which + // allows us to remove the domtree entry for the block. + SmallPtrSet childNodes; + childNodes.insert(DT[*LI]->begin(), DT[*LI]->end()); + for (SmallPtrSet::iterator DI = childNodes.begin(), + DE = childNodes.end(); DI != DE; ++DI) + DT.changeImmediateDominator(*DI, DT[preheader]); + + DT.eraseNode(*LI); + + // Drop all references between the instructions and the block so + // that we don't have reference counting problems later. + for (BasicBlock::iterator BI = (*LI)->begin(), BE = (*LI)->end(); + BI != BE; ++BI) { + BI->dropAllReferences(); + } + + (*LI)->dropAllReferences(); + } + + // Erase the instructions and the blocks without having to worry + // about ordering because we already dropped the references. + 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++; + I->eraseFromParent(); + } + + (*LI)->eraseFromParent(); + } + + // Finally, the blocks from loopinfo. This has to happen late because + // otherwise our loop iterators won't work. + LoopInfo& loopInfo = getAnalysis(); + SmallPtrSet blocks; + blocks.insert(L->block_begin(), L->block_end()); + for (SmallPtrSet::iterator I = blocks.begin(), + E = blocks.end(); I != E; ++I) + loopInfo.removeBlock(*I); + + // The last step is to inform the loop pass manager that we've + // eliminated this loop. + LPM.deleteLoopFromQueue(L); + + NumDeleted++; + + return true; +} -- cgit v1.1