X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLCSSA.cpp;h=1cba367a3e420d6e367c41cff9632eda55f28629;hb=7ed0364cee76de015ada95cfe08073e3b8cba825;hp=e46e35b3cad2a84cd56ef99080bc87ae6464249e;hpb=794fd75c67a2cdc128d67342c6d88a504d186896;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LCSSA.cpp b/lib/Transforms/Utils/LCSSA.cpp index e46e35b3cad..1cba367a3e4 100644 --- a/lib/Transforms/Utils/LCSSA.cpp +++ b/lib/Transforms/Utils/LCSSA.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Owen Anderson and is distributed under the -// University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,13 +12,13 @@ // the left into the right code: // // for (...) for (...) -// if (c) if(c) +// if (c) if (c) // X1 = ... X1 = ... // else else // X2 = ... X2 = ... // X3 = phi(X1, X2) X3 = phi(X1, X2) -// ... = X3 + 4 X4 = phi(X3) -// ... = X4 + 4 +// ... = X3 + 4 X4 = phi(X3) +// ... = X4 + 4 // // This is still valid LLVM; the extra phi nodes are purely redundant, and will // be trivially eliminated by InstCombine. The major benefit of this @@ -27,249 +27,320 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "lcssa" #include "llvm/Transforms/Scalar.h" -#include "llvm/Constants.h" -#include "llvm/Pass.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" -#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Statistic.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" -#include -#include +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/ScalarEvolution.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/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/SSAUpdater.h" using namespace llvm; +#define DEBUG_TYPE "lcssa" + STATISTIC(NumLCSSA, "Number of live out of a loop variables"); -namespace { - struct VISIBILITY_HIDDEN LCSSA : public FunctionPass { - static const int ID; // Pass identifcation, replacement for typeid - LCSSA() : FunctionPass((intptr_t)&ID) {} - - // Cached analysis information for the current function. - LoopInfo *LI; - DominatorTree *DT; - std::vector LoopBlocks; - - virtual bool runOnFunction(Function &F); - bool visitSubloop(Loop* L); - void ProcessInstruction(Instruction* Instr, - const std::vector& 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. - /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequiredID(LoopSimplifyID); - AU.addPreservedID(LoopSimplifyID); - AU.addRequired(); - AU.addRequired(); - } - private: - void getLoopValuesUsedOutsideLoop(Loop *L, - SetVector &AffectedValues); +/// 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; +} - Value *GetValueForBlock(DominatorTree::Node *BB, Instruction *OrigInst, - std::map &Phis); +/// 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; - /// inLoop - returns true if the given block is within the current loop - const bool inLoop(BasicBlock* B) { - return std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), B); - } - }; - - const int LCSSA::ID = 0; - RegisterPass X("lcssa", "Loop-Closed SSA Form Pass"); -} + BasicBlock *InstBB = Inst.getParent(); -FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } -const PassInfo *llvm::LCSSAID = X.getPassInfo(); + for (Use &U : Inst.uses()) { + Instruction *User = cast(U.getUser()); + BasicBlock *UserBB = User->getParent(); + if (PHINode *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(U); -/// runOnFunction - Process all loops in the function, inner-most out. -bool LCSSA::runOnFunction(Function &F) { - bool changed = false; - - LI = &getAnalysis(); - DT = &getAnalysis(); - - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) - changed |= visitSubloop(*I); - - return changed; -} + if (InstBB != UserBB && !L.contains(UserBB)) + UsesToRewrite.push_back(&U); + } -/// visitSubloop - Recursively process all subloops, and then process the given -/// loop if it has live-out values. -bool LCSSA::visitSubloop(Loop* L) { - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) - visitSubloop(*I); - - // Speed up queries by creating a sorted list of blocks - LoopBlocks.clear(); - LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); - std::sort(LoopBlocks.begin(), LoopBlocks.end()); - - SetVector 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()) + // If there are no uses outside the loop, exit with no change. + if (UsesToRewrite.empty()) return false; - - std::vector 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(), - E = AffectedValues.end(); I != E; ++I) - ProcessInstruction(*I, exitBlocks); - - assert(L->isLCSSAForm()); - - return true; -} -/// processInstruction - Given a live-out instruction, insert LCSSA Phi nodes, -/// eliminate all out-of-loop uses. -void LCSSA::ProcessInstruction(Instruction *Instr, - const std::vector& exitBlocks) { ++NumLCSSA; // We are applying the transformation - // Keep track of the blocks that have the value available already. - std::map Phis; + // 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 + // 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)) + DomBB = Inv->getNormalDest(); - DominatorTree::Node *InstrNode = DT->getNode(Instr->getParent()); + DomTreeNode *DomNode = DT.getNode(DomBB); - // Insert the LCSSA phi's into the exit blocks (dominated by the value), and - // add them to the Phi's map. - for (std::vector::const_iterator BBI = exitBlocks.begin(), - BBE = exitBlocks.end(); BBI != BBE; ++BBI) { - BasicBlock *BB = *BBI; - DominatorTree::Node *ExitBBNode = DT->getNode(BB); - Value *&Phi = Phis[ExitBBNode]; - if (!Phi && InstrNode->dominates(ExitBBNode)) { - PHINode *PN = new PHINode(Instr->getType(), Instr->getName()+".lcssa", - BB->begin()); - PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB))); - - // Remember that this phi makes the value alive in this block. - Phi = PN; - - // Add inputs from inside the loop for this PHI. - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - PN->addIncoming(Instr, *PI); + SmallVector AddedPHIs; + SmallVector PostProcessPHIs; + + SSAUpdater SSAUpdate; + 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) { + BasicBlock *ExitBB = *BBI; + 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()); + + // Add inputs from inside the loop for this PHI. + for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++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 (!L.contains(*PI)) + UsesToRewrite.push_back( + &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); } - - - // Record all uses of Instr outside the loop. We need to rewrite these. The - // LCSSA phis won't be included because they use the value in the loop. - for (Value::use_iterator UI = Instr->use_begin(), E = Instr->use_end(); - UI != E;) { - BasicBlock *UserBB = cast(*UI)->getParent(); - if (PHINode *P = dyn_cast(*UI)) { - unsigned OperandNo = UI.getOperandNo(); - UserBB = P->getIncomingBlock(OperandNo/2); - } - - // If the user is in the loop, don't rewrite it! - if (UserBB == Instr->getParent() || inLoop(UserBB)) { - ++UI; + + // Rewrite all uses outside the loop in terms of the new PHIs we just + // inserted. + for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) { + // If this use is in an exit block, rewrite to use the newly inserted PHI. + // This is required for correctness because SSAUpdate doesn't handle uses in + // the same block. It assumes the PHI we inserted is at the end of the + // block. + Instruction *User = cast(UsesToRewrite[i]->getUser()); + BasicBlock *UserBB = User->getParent(); + if (PHINode *PN = dyn_cast(User)) + UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); + + 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, patch up uses of the value with the appropriate LCSSA Phi, - // inserting PHI nodes into join points where needed. - Value *Val = GetValueForBlock(DT->getNode(UserBB), Instr, Phis); - - // Preincrement the iterator to avoid invalidating it when we change the - // value. - Use &U = UI.getUse(); - ++UI; - U.set(Val); + + // 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; } -/// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that -/// are used by instructions outside of it. -void LCSSA::getLoopValuesUsedOutsideLoop(Loop *L, - SetVector &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 - // block could be used outside the loop. - for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); - BB != E; ++BB) { - for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; - ++UI) { - BasicBlock *UserBB = cast(*UI)->getParent(); - if (PHINode* p = dyn_cast(*UI)) { - unsigned OperandNo = UI.getOperandNo(); - UserBB = p->getIncomingBlock(OperandNo/2); - } - - if (*BB != UserBB && !inLoop(UserBB)) { - AffectedValues.insert(I); - break; - } - } +/// 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; } -/// GetValueForBlock - Get the value to use within the specified basic block. -/// available values are in Phis. -Value *LCSSA::GetValueForBlock(DominatorTree::Node *BB, Instruction *OrigInst, - std::map &Phis) { - // If there is no dominator info for this BB, it is unreachable. - if (BB == 0) - return UndefValue::get(OrigInst->getType()); - - // If we have already computed this value, return the previously computed val. - Value *&V = Phis[BB]; - if (V) return V; - - DominatorTree::Node *IDom = BB->getIDom(); - - // Otherwise, there are two cases: we either have to insert a PHI node or we - // don't. We need to insert a PHI node if this block is not dominated by one - // of the exit nodes from the loop (the loop could have multiple exits, and - // though the value defined *inside* the loop dominated all its uses, each - // exit by itself may not dominate all the uses). - // - // The simplest way to check for this condition is by checking to see if the - // idom is in the loop. If so, we *know* that none of the exit blocks - // dominate this block. Note that we *know* that the block defining the - // original instruction is in the idom chain, because if it weren't, then the - // original value didn't dominate this use. - if (!inLoop(IDom->getBlock())) { - // Idom is not in the loop, we must still be "below" the exit block and must - // be fully dominated by the value live in the idom. - return V = GetValueForBlock(IDom, OrigInst, Phis); +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(); } - - BasicBlock *BBN = BB->getBlock(); - - // Otherwise, the idom is the loop, so we need to insert a PHI node. Do so - // now, then get values to fill in the incoming values for the PHI. - PHINode *PN = new PHINode(OrigInst->getType(), OrigInst->getName()+".lcssa", - BBN->begin()); - PN->reserveOperandSpace(std::distance(pred_begin(BBN), pred_end(BBN))); - V = PN; - - // Fill in the incoming values for the block. - for (pred_iterator PI = pred_begin(BBN), E = pred_end(BBN); PI != E; ++PI) - PN->addIncoming(GetValueForBlock(DT->getNode(*PI), OrigInst, Phis), *PI); - return PN; + +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); +}