X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLCSSA.cpp;h=1cba367a3e420d6e367c41cff9632eda55f28629;hb=7ed0364cee76de015ada95cfe08073e3b8cba825;hp=5dddb6e28a5f95671fbc375a2d4e498af6733b6a;hpb=d04a8d4b33ff316ca4cf961e06c9e312eff8e64f;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index 5dddb6e28a5..1cba367a3e4 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -27,233 +27,123 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "lcssa" #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Constants.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/PredIteratorCache.h" #include "llvm/Pass.h" -#include "llvm/Support/PredIteratorCache.h" +#include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/SSAUpdater.h" using namespace llvm; -STATISTIC(NumLCSSA, "Number of live out of a loop variables"); - -namespace { - struct LCSSA : public LoopPass { - static char ID; // Pass identification, replacement for typeid - LCSSA() : LoopPass(ID) { - initializeLCSSAPass(*PassRegistry::getPassRegistry()); - } - - // Cached analysis information for the current function. - DominatorTree *DT; - LoopInfo *LI; - ScalarEvolution *SE; - std::vector LoopBlocks; - PredIteratorCache PredCache; - Loop *L; - - virtual bool runOnLoop(Loop *L, LPPassManager &LPM); - - /// 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. - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - - AU.addRequired(); - AU.addRequired(); - AU.addPreservedID(LoopSimplifyID); - AU.addPreserved(); - } - private: - bool ProcessInstruction(Instruction *Inst, - const SmallVectorImpl &ExitBlocks); - - /// verifyAnalysis() - Verify loop nest. - virtual void verifyAnalysis() const { - // Check the special guarantees that LCSSA makes. - assert(L->isLCSSAForm(*DT) && "LCSSA form not preserved!"); - } - - /// inLoop - returns true if the given block is within the current loop - bool inLoop(BasicBlock *B) const { - return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); - } - }; -} - -char LCSSA::ID = 0; -INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) - -Pass *llvm::createLCSSAPass() { return new LCSSA(); } -char &llvm::LCSSAID = LCSSA::ID; +#define DEBUG_TYPE "lcssa" +STATISTIC(NumLCSSA, "Number of live out of a loop variables"); -/// BlockDominatesAnExit - Return true if the specified block dominates at least -/// one of the blocks in the specified list. -static bool BlockDominatesAnExit(BasicBlock *BB, - const SmallVectorImpl &ExitBlocks, - DominatorTree *DT) { - DomTreeNode *DomNode = DT->getNode(BB); +/// Return true if the specified block is in the list. +static bool isExitBlock(BasicBlock *BB, + const SmallVectorImpl &ExitBlocks) { for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (DT->dominates(DomNode, DT->getNode(ExitBlocks[i]))) + if (ExitBlocks[i] == BB) return true; - return false; } +/// Given an instruction in the loop, check to see if it has any uses that are +/// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the +/// uses. +static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, + const SmallVectorImpl &ExitBlocks, + PredIteratorCache &PredCache, LoopInfo *LI) { + SmallVector UsesToRewrite; -/// runOnFunction - Process all loops in the function, inner-most out. -bool LCSSA::runOnLoop(Loop *TheLoop, LPPassManager &LPM) { - L = TheLoop; - - DT = &getAnalysis(); - LI = &getAnalysis(); - SE = getAnalysisIfAvailable(); + BasicBlock *InstBB = Inst.getParent(); - // Get the set of exiting blocks. - SmallVector ExitBlocks; - L->getExitBlocks(ExitBlocks); - - if (ExitBlocks.empty()) - return false; - - // Speed up queries by creating a sorted vector of blocks. - LoopBlocks.clear(); - LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); - array_pod_sort(LoopBlocks.begin(), LoopBlocks.end()); - - // Look at all the instructions in the loop, checking to see if they have uses - // outside the loop. If so, rewrite those uses. - bool MadeChange = false; - - for (Loop::block_iterator BBI = L->block_begin(), E = L->block_end(); - BBI != E; ++BBI) { - BasicBlock *BB = *BBI; - - // For large loops, avoid 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 block could be used outside the loop. - if (!BlockDominatesAnExit(BB, ExitBlocks, DT)) - continue; - - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); - I != E; ++I) { - // Reject two common cases fast: instructions with no uses (like stores) - // and instructions with one use that is in the same block as this. - if (I->use_empty() || - (I->hasOneUse() && I->use_back()->getParent() == BB && - !isa(I->use_back()))) - continue; - - MadeChange |= ProcessInstruction(I, ExitBlocks); - } - } - - // If we modified the code, remove any caches about the loop from SCEV to - // avoid dangling entries. - // FIXME: This is a big hammer, can we clear the cache more selectively? - if (SE && MadeChange) - SE->forgetLoop(L); - - assert(L->isLCSSAForm(*DT)); - PredCache.clear(); - - return MadeChange; -} - -/// isExitBlock - Return true if the specified block is in the list. -static bool isExitBlock(BasicBlock *BB, - const SmallVectorImpl &ExitBlocks) { - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (ExitBlocks[i] == BB) - return true; - return false; -} + for (Use &U : Inst.uses()) { + Instruction *User = cast(U.getUser()); + BasicBlock *UserBB = User->getParent(); + if (PHINode *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(U); -/// ProcessInstruction - Given an instruction in the loop, check to see if it -/// has any uses that are outside the current loop. If so, insert LCSSA PHI -/// nodes and rewrite the uses. -bool LCSSA::ProcessInstruction(Instruction *Inst, - const SmallVectorImpl &ExitBlocks) { - SmallVector UsesToRewrite; - - BasicBlock *InstBB = Inst->getParent(); - - for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end(); - UI != E; ++UI) { - User *U = *UI; - BasicBlock *UserBB = cast(U)->getParent(); - if (PHINode *PN = dyn_cast(U)) - UserBB = PN->getIncomingBlock(UI); - - if (InstBB != UserBB && !inLoop(UserBB)) - UsesToRewrite.push_back(&UI.getUse()); + if (InstBB != UserBB && !L.contains(UserBB)) + UsesToRewrite.push_back(&U); } // If there are no uses outside the loop, exit with no change. - if (UsesToRewrite.empty()) return false; - + if (UsesToRewrite.empty()) + return false; + ++NumLCSSA; // We are applying the transformation // Invoke instructions are special in that their result value is not available - // along their unwind edge. The code below tests to see whether DomBB dominates + // along their unwind edge. The code below tests to see whether DomBB + // dominates // the value, so adjust DomBB to the normal destination block, which is // effectively where the value is first usable. - BasicBlock *DomBB = Inst->getParent(); - if (InvokeInst *Inv = dyn_cast(Inst)) + BasicBlock *DomBB = Inst.getParent(); + if (InvokeInst *Inv = dyn_cast(&Inst)) DomBB = Inv->getNormalDest(); - DomTreeNode *DomNode = DT->getNode(DomBB); + DomTreeNode *DomNode = DT.getNode(DomBB); - SmallVector AddedPHIs; + SmallVector AddedPHIs; + SmallVector PostProcessPHIs; SSAUpdater SSAUpdate; - SSAUpdate.Initialize(Inst->getType(), Inst->getName()); - + SSAUpdate.Initialize(Inst.getType(), Inst.getName()); + // Insert the LCSSA phi's into all of the exit blocks dominated by the // value, and add them to the Phi's map. - for (SmallVectorImpl::const_iterator BBI = ExitBlocks.begin(), - BBE = ExitBlocks.end(); BBI != BBE; ++BBI) { + for (SmallVectorImpl::const_iterator BBI = ExitBlocks.begin(), + BBE = ExitBlocks.end(); + BBI != BBE; ++BBI) { BasicBlock *ExitBB = *BBI; - if (!DT->dominates(DomNode, DT->getNode(ExitBB))) continue; - + if (!DT.dominates(DomNode, DT.getNode(ExitBB))) + continue; + // If we already inserted something for this BB, don't reprocess it. - if (SSAUpdate.HasValueForBlock(ExitBB)) continue; - - PHINode *PN = PHINode::Create(Inst->getType(), - PredCache.GetNumPreds(ExitBB), - Inst->getName()+".lcssa", - ExitBB->begin()); + if (SSAUpdate.HasValueForBlock(ExitBB)) + continue; + + PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB), + Inst.getName() + ".lcssa", ExitBB->begin()); // Add inputs from inside the loop for this PHI. for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { - PN->addIncoming(Inst, *PI); + PN->addIncoming(&Inst, *PI); // If the exit block has a predecessor not within the loop, arrange for // the incoming value use corresponding to that predecessor to be // rewritten in terms of a different LCSSA PHI. - if (!inLoop(*PI)) + if (!L.contains(*PI)) UsesToRewrite.push_back( - &PN->getOperandUse( - PN->getOperandNumForIncomingValue(PN->getNumIncomingValues()-1))); + &PN->getOperandUse(PN->getOperandNumForIncomingValue( + PN->getNumIncomingValues() - 1))); } AddedPHIs.push_back(PN); - + // Remember that this phi makes the value alive in this block. SSAUpdate.AddAvailableValue(ExitBB, PN); + + // LoopSimplify might fail to simplify some loops (e.g. when indirect + // branches are involved). In such situations, it might happen that an exit + // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create + // PHIs in such an exit block, we are also inserting PHIs into L2's header. + // This could break LCSSA form for L2 because these inserted PHIs can also + // have uses outside of L2. Remember all PHIs in such situation as to + // revisit than later on. FIXME: Remove this if indirectbr support into + // LoopSimplify gets improved. + if (auto *OtherLoop = LI->getLoopFor(ExitBB)) + if (!L.contains(OtherLoop)) + PostProcessPHIs.push_back(PN); } // Rewrite all uses outside the loop in terms of the new PHIs we just @@ -268,25 +158,189 @@ bool LCSSA::ProcessInstruction(Instruction *Inst, if (PHINode *PN = dyn_cast(User)) UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); - if (isa(UserBB->begin()) && - isExitBlock(UserBB, ExitBlocks)) { + if (isa(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { // Tell the VHs that the uses changed. This updates SCEV's caches. if (UsesToRewrite[i]->get()->hasValueHandle()) ValueHandleBase::ValueIsRAUWd(*UsesToRewrite[i], UserBB->begin()); UsesToRewrite[i]->set(UserBB->begin()); continue; } - + // Otherwise, do full PHI insertion. SSAUpdate.RewriteUse(*UsesToRewrite[i]); } + // Post process PHI instructions that were inserted into another disjoint loop + // and update their exits properly. + for (auto *I : PostProcessPHIs) { + if (I->use_empty()) + continue; + + BasicBlock *PHIBB = I->getParent(); + Loop *OtherLoop = LI->getLoopFor(PHIBB); + SmallVector EBs; + OtherLoop->getExitBlocks(EBs); + if (EBs.empty()) + continue; + + // Recurse and re-process each PHI instruction. FIXME: we should really + // convert this entire thing to a worklist approach where we process a + // vector of instructions... + processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI); + } + // Remove PHI nodes that did not have any uses rewritten. for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) { if (AddedPHIs[i]->use_empty()) AddedPHIs[i]->eraseFromParent(); } - + return true; } +/// Return true if the specified block dominates at least +/// one of the blocks in the specified list. +static bool +blockDominatesAnExit(BasicBlock *BB, + DominatorTree &DT, + const SmallVectorImpl &ExitBlocks) { + DomTreeNode *DomNode = DT.getNode(BB); + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) + if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i]))) + return true; + + return false; +} + +bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, + ScalarEvolution *SE) { + bool Changed = false; + + // Get the set of exiting blocks. + SmallVector ExitBlocks; + L.getExitBlocks(ExitBlocks); + + if (ExitBlocks.empty()) + return false; + + PredIteratorCache PredCache; + + // Look at all the instructions in the loop, checking to see if they have uses + // outside the loop. If so, rewrite those uses. + for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end(); + BBI != BBE; ++BBI) { + BasicBlock *BB = *BBI; + + // For large loops, avoid 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 block could be used outside the loop. + if (!blockDominatesAnExit(BB, DT, ExitBlocks)) + continue; + + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + // Reject two common cases fast: instructions with no uses (like stores) + // and instructions with one use that is in the same block as this. + if (I->use_empty() || + (I->hasOneUse() && I->user_back()->getParent() == BB && + !isa(I->user_back()))) + continue; + + Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache, LI); + } + } + + // If we modified the code, remove any caches about the loop from SCEV to + // avoid dangling entries. + // FIXME: This is a big hammer, can we clear the cache more selectively? + if (SE && Changed) + SE->forgetLoop(&L); + + assert(L.isLCSSAForm(DT)); + + return Changed; +} + +/// Process a loop nest depth first. +bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, + ScalarEvolution *SE) { + bool Changed = false; + + // Recurse depth-first through inner loops. + for (Loop::iterator I = L.begin(), E = L.end(); I != E; ++I) + Changed |= formLCSSARecursively(**I, DT, LI, SE); + + Changed |= formLCSSA(L, DT, LI, SE); + return Changed; +} + +namespace { +struct LCSSA : public FunctionPass { + static char ID; // Pass identification, replacement for typeid + LCSSA() : FunctionPass(ID) { + initializeLCSSAPass(*PassRegistry::getPassRegistry()); + } + + // Cached analysis information for the current function. + DominatorTree *DT; + LoopInfo *LI; + ScalarEvolution *SE; + + bool runOnFunction(Function &F) override; + + /// 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. + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + + AU.addRequired(); + AU.addRequired(); + AU.addPreservedID(LoopSimplifyID); + AU.addPreserved(); + AU.addPreserved(); + } + +private: + void verifyAnalysis() const override; +}; +} + +char LCSSA::ID = 0; +INITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) + +Pass *llvm::createLCSSAPass() { return new LCSSA(); } +char &llvm::LCSSAID = LCSSA::ID; + + +/// Process all loops in the function, inner-most out. +bool LCSSA::runOnFunction(Function &F) { + bool Changed = false; + LI = &getAnalysis().getLoopInfo(); + DT = &getAnalysis().getDomTree(); + SE = getAnalysisIfAvailable(); + + // Simplify each loop nest in the function. + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + Changed |= formLCSSARecursively(**I, *DT, LI, SE); + + return Changed; +} + +static void verifyLoop(Loop &L, DominatorTree &DT) { + // Recurse depth-first through inner loops. + for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) + verifyLoop(**LI, DT); + + // Check the special guarantees that LCSSA makes. + //assert(L.isLCSSAForm(DT) && "LCSSA form not preserved!"); +} + +void LCSSA::verifyAnalysis() const { + // Verify each loop nest in the function, assuming LI still points at that + // function's loop info. + for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) + verifyLoop(**I, *DT); +}