From 39b0c3d6133b702367048cd9ef518ad6747f3351 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sun, 11 Oct 2009 01:07:15 +0000 Subject: clean up and simplify some code. Don't use setvector when things will be inserted only once, just use vector. Don't compute ExitBlocks unless we need it, change std::sort to array_pod_sort. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@83747 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/LCSSA.cpp | 51 +++++++++++++++++++----------------------- 1 file changed, 23 insertions(+), 28 deletions(-) (limited to 'lib/Transforms/Utils/LCSSA.cpp') diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index af54add385..b3d1c977cf 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -34,15 +34,14 @@ #include "llvm/Function.h" #include "llvm/Instructions.h" #include "llvm/LLVMContext.h" -#include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/PredIteratorCache.h" -#include #include using namespace llvm; @@ -62,9 +61,6 @@ namespace { virtual bool runOnLoop(Loop *L, LPPassManager &LPM); - void ProcessInstruction(Instruction* Instr, - const SmallVector& exitBlocks); - /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG. It maintains both of these, /// as well as the CFG. It also requires dominator information. @@ -87,7 +83,9 @@ namespace { AU.addPreserved(); } private: - + void ProcessInstruction(Instruction* Instr, + const SmallVector& exitBlocks); + /// verifyAnalysis() - Verify loop nest. virtual void verifyAnalysis() const { // Check the special guarantees that LCSSA makes. @@ -95,14 +93,13 @@ namespace { } void getLoopValuesUsedOutsideLoop(Loop *L, - SetVector &AffectedValues, - const SmallVector& exitBlocks); + SmallVectorImpl &AffectedValues); Value *GetValueForBlock(DomTreeNode *BB, Instruction *OrigInst, DenseMap &Phis); /// inLoop - returns true if the given block is within the current loop - bool inLoop(BasicBlock* B) { + bool inLoop(BasicBlock *B) const { return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); } }; @@ -122,28 +119,27 @@ bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) { LI = &LPM.getAnalysis(); DT = &getAnalysis(); - // Speed up queries by creating a sorted list of blocks + // Speed up queries by creating a sorted vector of blocks. LoopBlocks.clear(); LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); - std::sort(LoopBlocks.begin(), LoopBlocks.end()); - - SmallVector exitBlocks; - L->getExitBlocks(exitBlocks); + array_pod_sort(LoopBlocks.begin(), LoopBlocks.end()); - SetVector AffectedValues; - getLoopValuesUsedOutsideLoop(L, AffectedValues, exitBlocks); + SmallVector AffectedValues; + getLoopValuesUsedOutsideLoop(L, AffectedValues); // If no values are affected, we can save a lot of work, since we know that // nothing will be changed. if (AffectedValues.empty()) return false; + + SmallVector ExitBlocks; + L->getExitBlocks(ExitBlocks); // Iterate over all affected values for this loop and insert Phi nodes - // for them in the appropriate exit blocks - - for (SetVector::iterator I = AffectedValues.begin(), + // for them in the appropriate exit blocks. + for (SmallVectorImpl::iterator I = AffectedValues.begin(), E = AffectedValues.end(); I != E; ++I) - ProcessInstruction(*I, exitBlocks); + ProcessInstruction(*I, ExitBlocks); assert(L->isLCSSAForm()); @@ -153,7 +149,7 @@ bool LCSSA::runOnLoop(Loop *l, LPPassManager &LPM) { /// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, /// eliminate all out-of-loop uses. void LCSSA::ProcessInstruction(Instruction *Instr, - const SmallVector& exitBlocks) { + const SmallVector &ExitBlocks) { ++NumLCSSA; // We are applying the transformation // Keep track of the blocks that have the value available already. @@ -172,8 +168,8 @@ void LCSSA::ProcessInstruction(Instruction *Instr, // Insert the LCSSA phi's into the exit blocks (dominated by the value), and // add them to the Phi's map. - for (SmallVector::const_iterator BBI = exitBlocks.begin(), - BBE = exitBlocks.end(); BBI != BBE; ++BBI) { + for (SmallVector::const_iterator BBI = ExitBlocks.begin(), + BBE = ExitBlocks.end(); BBI != BBE; ++BBI) { BasicBlock *BB = *BBI; DomTreeNode *ExitBBNode = DT->getNode(BB); Value *&Phi = Phis[ExitBBNode]; @@ -221,8 +217,7 @@ void LCSSA::ProcessInstruction(Instruction *Instr, /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that /// are used by instructions outside of it. void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, - SetVector &AffectedValues, - const SmallVector& exitBlocks) { + SmallVectorImpl &AffectedValues) { // FIXME: For large loops, we may be able to avoid a lot of use-scanning // by using dominance information. In particular, if a block does not // dominate any of the loop exits, then none of the values defined in the @@ -233,11 +228,11 @@ void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); UI != UE; ++UI) { BasicBlock *UserBB = cast(*UI)->getParent(); - if (PHINode *p = dyn_cast(*UI)) - UserBB = p->getIncomingBlock(UI); + if (PHINode *PN = dyn_cast(*UI)) + UserBB = PN->getIncomingBlock(UI); if (*BB != UserBB && !inLoop(UserBB)) { - AffectedValues.insert(I); + AffectedValues.push_back(I); break; } } -- cgit v1.2.3