X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLICM.cpp;h=40af0a811d103650c5417abfd6874636472d4f62;hb=9289ae85b41eef62ae1fadb93e99d33f723fb682;hp=2662a6016de77fad98e8da289ac1ae8892fd1239;hpb=326821ef12c911af1d785e305e81dc3c07e456a5;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index 2662a6016de..40af0a811d1 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group 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. // //===----------------------------------------------------------------------===// // @@ -35,6 +35,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" +#include "llvm/IntrinsicInst.h" #include "llvm/Instructions.h" #include "llvm/Target/TargetData.h" #include "llvm/Analysis/LoopInfo.h" @@ -42,10 +43,11 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Transforms/Utils/PromoteMemToReg.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Support/Debug.h" #include "llvm/ADT/Statistic.h" #include @@ -57,14 +59,23 @@ STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk"); STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk"); STATISTIC(NumPromoted , "Number of memory locations promoted to registers"); -namespace { - cl::opt - DisablePromotion("disable-licm-promotion", cl::Hidden, - cl::desc("Disable memory promotion in LICM pass")); +static cl::opt +DisablePromotion("disable-licm-promotion", cl::Hidden, + cl::desc("Disable memory promotion in LICM pass")); + +// This feature is currently disabled by default because CodeGen is not yet +// capable of rematerializing these constants in PIC mode, so it can lead to +// degraded performance. Compile test/CodeGen/X86/remat-constant.ll with +// -relocation-model=pic to see an example of this. +static cl::opt +EnableLICMConstantMotion("enable-licm-constant-variables", cl::Hidden, + cl::desc("Enable hoisting/sinking of constant " + "global variables")); - struct VISIBILITY_HIDDEN LICM : public LoopPass { +namespace { + struct LICM : public LoopPass { static char ID; // Pass identification, replacement for typeid - LICM() : LoopPass((intptr_t)&ID) {} + LICM() : LoopPass(&ID) {} virtual bool runOnLoop(Loop *L, LPPassManager &LPM); @@ -76,12 +87,19 @@ namespace { AU.addRequiredID(LoopSimplifyID); AU.addRequired(); AU.addRequired(); - AU.addRequired(); AU.addRequired(); // For scalar promotion (mem2reg) AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreservedID(LoopSimplifyID); } bool doFinalization() { + // Free the values stored in the map + for (std::map::iterator + I = LoopToAliasMap.begin(), E = LoopToAliasMap.end(); I != E; ++I) + delete I->second; + LoopToAliasMap.clear(); return false; } @@ -90,7 +108,6 @@ namespace { // Various analyses that we use... AliasAnalysis *AA; // Current AliasAnalysis information LoopInfo *LI; // Current LoopInfo - ETForest *ET; // ETForest for the current loop.. DominatorTree *DT; // Dominator Tree for the current Loop... DominanceFrontier *DF; // Current Dominance Frontier @@ -101,6 +118,13 @@ namespace { AliasSetTracker *CurAST; // AliasSet information for the current loop... std::map LoopToAliasMap; + /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. + void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L); + + /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias + /// set. + void deleteAnalysisValue(Value *V, Loop *L); + /// SinkRegion - Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in /// reverse depth first order w.r.t the DominatorTree. This allows us to @@ -117,6 +141,10 @@ namespace { /// void HoistRegion(DomTreeNode *N); + // Cleanup debug information (remove stoppoints with no coressponding + // instructions). + void CleanupDbgInfoRegion(DomTreeNode *N); + /// inSubLoop - Little predicate that returns true if the specified basic /// block is in a subloop of the current one, not the current one itself. /// @@ -203,14 +231,16 @@ namespace { std::vector > &PromotedValues, std::map &Val2AlMap); }; - - char LICM::ID = 0; - RegisterPass X("licm", "Loop Invariant Code Motion"); } -LoopPass *llvm::createLICMPass() { return new LICM(); } +char LICM::ID = 0; +static RegisterPass X("licm", "Loop Invariant Code Motion"); -/// Hoist expressions out of the specified loop... +Pass *llvm::createLICMPass() { return new LICM(); } + +/// Hoist expressions out of the specified loop. Note, alias info for inner +/// loop is not preserved so it is not a good idea to run LICM multiple +/// times on one loop. /// bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { Changed = false; @@ -220,7 +250,6 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { AA = &getAnalysis(); DF = &getAnalysis(); DT = &getAnalysis(); - ET = &getAnalysis(); CurAST = new AliasSetTracker(*AA); // Collect Alias info from subloops @@ -244,10 +273,12 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { // Because subloops have already been incorporated into AST, we skip blocks in // subloops. // - for (std::vector::const_iterator I = L->getBlocks().begin(), - E = L->getBlocks().end(); I != E; ++I) - if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... - CurAST->add(**I); // Incorporate the specified basic block + for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); + I != E; ++I) { + BasicBlock *BB = *I; + if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops... + CurAST->add(*BB); // Incorporate the specified basic block + } // We want to visit all of the instructions in this loop... that are not parts // of our subloops (they have already had their invariants hoisted out of @@ -256,11 +287,12 @@ bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { // // Traverse the body of the loop in depth first order on the dominator tree so // that we are guaranteed to see definitions before we see uses. This allows - // us to sink instructions in one pass, without iteration. AFter sinking + // us to sink instructions in one pass, without iteration. After sinking // instructions, we perform another pass to hoist them out of the loop. // SinkRegion(DT->getNode(L->getHeader())); HoistRegion(DT->getNode(L->getHeader())); + CleanupDbgInfoRegion(DT->getNode(L->getHeader())); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can... @@ -312,6 +344,35 @@ void LICM::SinkRegion(DomTreeNode *N) { } } +void LICM::CleanupDbgInfoRegion(DomTreeNode *N) { + BasicBlock *BB = N->getBlock(); + + // If this subregion is not in the top level loop at all, exit. + if (!CurLoop->contains(BB)) return; + + // We are processing blocks in reverse dfo, so process children first... + const std::vector &Children = N->getChildren(); + for (unsigned i = 0, e = Children.size(); i != e; ++i) + CleanupDbgInfoRegion(Children[i]); + + // Only need to process the contents of this block if it is not part of a + // subloop (which would already have been processed). + if (inSubLoop(BB)) return; + + // We modify the basicblock, so don't cache end() + for (BasicBlock::iterator I=BB->begin(); I != BB->end();) { + Instruction *Last = 0; + // Remove consecutive dbgstoppoints, leave only last + do { + if (Last) { + Last->eraseFromParent(); + Changed = true; + } + Last = I; + ++I; + } while (isa(Last) && isa(I)); + } +} /// HoistRegion - Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -354,31 +415,39 @@ bool LICM::canSinkOrHoistInst(Instruction &I) { if (LI->isVolatile()) return false; // Don't hoist volatile loads! + // Loads from constant memory are always safe to move, even if they end up + // in the same alias set as something that ends up being modified. + if (EnableLICMConstantMotion && + AA->pointsToConstantMemory(LI->getOperand(0))) + return true; + // Don't hoist loads which have may-aliased stores in loop. unsigned Size = 0; if (LI->getType()->isSized()) - Size = AA->getTargetData().getTypeSize(LI->getType()); + Size = AA->getTypeStoreSize(LI->getType()); return !pointerInvalidatedByLoop(LI->getOperand(0), Size); } else if (CallInst *CI = dyn_cast(&I)) { + if (isa(CI)) { + // Don't hoist/sink dbgstoppoints, we handle them separately + return false; + } // Handle obvious cases efficiently. - if (Function *Callee = CI->getCalledFunction()) { - AliasAnalysis::ModRefBehavior Behavior =AA->getModRefBehavior(Callee, CI); - if (Behavior == AliasAnalysis::DoesNotAccessMemory) - return true; - else if (Behavior == AliasAnalysis::OnlyReadsMemory) { - // If this call only reads from memory and there are no writes to memory - // in the loop, we can hoist or sink the call as appropriate. - bool FoundMod = false; - for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); - I != E; ++I) { - AliasSet &AS = *I; - if (!AS.isForwardingAliasSet() && AS.isMod()) { - FoundMod = true; - break; - } + AliasAnalysis::ModRefBehavior Behavior = AA->getModRefBehavior(CI); + if (Behavior == AliasAnalysis::DoesNotAccessMemory) + return true; + else if (Behavior == AliasAnalysis::OnlyReadsMemory) { + // If this call only reads from memory and there are no writes to memory + // in the loop, we can hoist or sink the call as appropriate. + bool FoundMod = false; + for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); + I != E; ++I) { + AliasSet &AS = *I; + if (!AS.isForwardingAliasSet() && AS.isMod()) { + FoundMod = true; + break; } - if (!FoundMod) return true; } + if (!FoundMod) return true; } // FIXME: This should use mod/ref information to see if we can hoist or sink @@ -435,9 +504,9 @@ bool LICM::isLoopInvariantInst(Instruction &I) { /// position, and may either delete it or move it to outside of the loop. /// void LICM::sink(Instruction &I) { - DOUT << "LICM sinking instruction: " << I; + DEBUG(errs() << "LICM sinking instruction: " << I); - std::vector ExitBlocks; + SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); if (isa(I)) ++NumMovedLoads; @@ -459,12 +528,10 @@ void LICM::sink(Instruction &I) { // Move the instruction to the start of the exit block, after any PHI // nodes in it. I.removeFromParent(); - - BasicBlock::iterator InsertPt = ExitBlocks[0]->begin(); - while (isa(InsertPt)) ++InsertPt; + BasicBlock::iterator InsertPt = ExitBlocks[0]->getFirstNonPHI(); ExitBlocks[0]->getInstList().insert(InsertPt, &I); } - } else if (ExitBlocks.size() == 0) { + } else if (ExitBlocks.empty()) { // The instruction is actually dead if there ARE NO exit blocks. CurAST->deleteValue(&I); if (!I.use_empty()) // If I has users in unreachable blocks, eliminate. @@ -478,7 +545,7 @@ void LICM::sink(Instruction &I) { // Firstly, we create a stack object to hold the value... AllocaInst *AI = 0; - if (I.getType() != Type::VoidTy) { + if (I.getType() != Type::getVoidTy(I.getContext())) { AI = new AllocaInst(I.getType(), 0, I.getName(), I.getParent()->getParent()->getEntryBlock().begin()); CurAST->add(AI); @@ -530,8 +597,7 @@ void LICM::sink(Instruction &I) { // If we haven't already processed this exit block, do so now. if (InsertedBlocks.insert(ExitBlock).second) { // Insert the code after the last PHI node... - BasicBlock::iterator InsertPt = ExitBlock->begin(); - while (isa(InsertPt)) ++InsertPt; + BasicBlock::iterator InsertPt = ExitBlock->getFirstNonPHI(); // If this is the first exit block processed, just move the original // instruction, otherwise clone the original instruction and insert @@ -565,7 +631,7 @@ void LICM::sink(Instruction &I) { if (AI) { std::vector Allocas; Allocas.push_back(AI); - PromoteMemToReg(Allocas, *DT, *DF, CurAST); + PromoteMemToReg(Allocas, *DT, *DF, AI->getContext(), CurAST); } } } @@ -574,7 +640,7 @@ void LICM::sink(Instruction &I) { /// that is safe to hoist, this instruction is called to do the dirty work. /// void LICM::hoist(Instruction &I) { - DOUT << "LICM hoisting to " << Preheader->getName() << ": " << I; + DEBUG(errs() << "LICM hoisting to " << Preheader->getName() << ": " << I); // Remove the instruction from its current basic block... but don't delete the // instruction. @@ -595,7 +661,8 @@ void LICM::hoist(Instruction &I) { /// bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { // If it is not a trapping instruction, it is always safe to hoist. - if (!Inst.isTrapping()) return true; + if (Inst.isSafeToSpeculativelyExecute()) + return true; // Otherwise we have to check to make sure that the instruction dominates all // of the exit blocks. If it doesn't, then there is a path out of the loop @@ -607,14 +674,8 @@ bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) { if (Inst.getParent() == CurLoop->getHeader()) return true; - // It's always safe to load from a global or alloca. - if (isa(Inst)) - if (isa(Inst.getOperand(0)) || - isa(Inst.getOperand(0))) - return true; - // Get the exit blocks for the current loop. - std::vector ExitBlocks; + SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); // For each exit block, get the DT node and walk up the DT until the @@ -688,12 +749,11 @@ void LICM::PromoteValuesInLoop() { // Scan the basic blocks in the loop, replacing uses of our pointers with // uses of the allocas in question. // - const std::vector &LoopBBs = CurLoop->getBlocks(); - for (std::vector::const_iterator I = LoopBBs.begin(), - E = LoopBBs.end(); I != E; ++I) { + for (Loop::block_iterator I = CurLoop->block_begin(), + E = CurLoop->block_end(); I != E; ++I) { + BasicBlock *BB = *I; // Rewrite all loads and stores in the block of the pointer... - for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); - II != E; ++II) { + for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { if (LoadInst *L = dyn_cast(II)) { std::map::iterator I = ValueToAllocaMap.find(L->getOperand(0)); @@ -714,30 +774,30 @@ void LICM::PromoteValuesInLoop() { // want to insert one copy of the code in each exit block, though the loop may // exit to the same block more than once. // - std::set ProcessedBlocks; + SmallPtrSet ProcessedBlocks; - std::vector ExitBlocks; + SmallVector ExitBlocks; CurLoop->getExitBlocks(ExitBlocks); - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) - if (ProcessedBlocks.insert(ExitBlocks[i]).second) { - // Copy all of the allocas into their memory locations. - BasicBlock::iterator BI = ExitBlocks[i]->begin(); - while (isa(*BI)) - ++BI; // Skip over all of the phi nodes in the block. - Instruction *InsertPos = BI; - unsigned PVN = 0; - for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { - // Load from the alloca. - LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); - - // If this is a pointer type, update alias info appropriately. - if (isa(LI->getType())) - CurAST->copyValue(PointerValueNumbers[PVN++], LI); - - // Store into the memory we promoted. - new StoreInst(LI, PromotedValues[i].second, InsertPos); - } + for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { + if (!ProcessedBlocks.insert(ExitBlocks[i])) + continue; + + // Copy all of the allocas into their memory locations. + BasicBlock::iterator BI = ExitBlocks[i]->getFirstNonPHI(); + Instruction *InsertPos = BI; + unsigned PVN = 0; + for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) { + // Load from the alloca. + LoadInst *LI = new LoadInst(PromotedValues[i].first, "", InsertPos); + + // If this is a pointer type, update alias info appropriately. + if (isa(LI->getType())) + CurAST->copyValue(PointerValueNumbers[PVN++], LI); + + // Store into the memory we promoted. + new StoreInst(LI, PromotedValues[i].second, InsertPos); } + } // Now that we have done the deed, use the mem2reg functionality to promote // all of the new allocas we just created into real SSA registers. @@ -746,14 +806,14 @@ void LICM::PromoteValuesInLoop() { PromotedAllocas.reserve(PromotedValues.size()); for (unsigned i = 0, e = PromotedValues.size(); i != e; ++i) PromotedAllocas.push_back(PromotedValues[i].first); - PromoteMemToReg(PromotedAllocas, *DT, *DF, CurAST); + PromoteMemToReg(PromotedAllocas, *DT, *DF, Preheader->getContext(), CurAST); } /// FindPromotableValuesInLoop - Check the current loop for stores to definite -/// pointers, which are not loaded and stored through may aliases. If these are -/// found, create an alloca for the value, add it to the PromotedValues list, -/// and keep track of the mapping from value to alloca. -/// +/// pointers, which are not loaded and stored through may aliases and are safe +/// for promotion. If these are found, create an alloca for the value, add it +/// to the PromotedValues list, and keep track of the mapping from value to +/// alloca. void LICM::FindPromotableValuesInLoop( std::vector > &PromotedValues, std::map &ValueToAllocaMap) { @@ -766,35 +826,94 @@ void LICM::FindPromotableValuesInLoop( // We can promote this alias set if it has a store, if it is a "Must" alias // set, if the pointer is loop invariant, and if we are not eliminating any // volatile loads or stores. - if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && - !AS.isVolatile() && CurLoop->isLoopInvariant(AS.begin()->first)) { - assert(AS.begin() != AS.end() && - "Must alias set should have at least one pointer element in it!"); - Value *V = AS.begin()->first; - - // Check that all of the pointers in the alias set have the same type. We - // cannot (yet) promote a memory location that is loaded and stored in - // different sizes. + if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() || + AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue())) + continue; + + assert(!AS.empty() && + "Must alias set should have at least one pointer element in it!"); + Value *V = AS.begin()->getValue(); + + // Check that all of the pointers in the alias set have the same type. We + // cannot (yet) promote a memory location that is loaded and stored in + // different sizes. + { bool PointerOk = true; for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) - if (V->getType() != I->first->getType()) { + if (V->getType() != I->getValue()->getType()) { PointerOk = false; break; } + if (!PointerOk) + continue; + } - if (PointerOk) { - const Type *Ty = cast(V->getType())->getElementType(); - AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); - PromotedValues.push_back(std::make_pair(AI, V)); + // It isn't safe to promote a load/store from the loop if the load/store is + // conditional. For example, turning: + // + // for () { if (c) *P += 1; } + // + // into: + // + // tmp = *P; for () { if (c) tmp +=1; } *P = tmp; + // + // is not safe, because *P may only be valid to access if 'c' is true. + // + // It is safe to promote P if all uses are direct load/stores and if at + // least one is guaranteed to be executed. + bool GuaranteedToExecute = false; + bool InvalidInst = false; + for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); + UI != UE; ++UI) { + // Ignore instructions not in this loop. + Instruction *Use = dyn_cast(*UI); + if (!Use || !CurLoop->contains(Use->getParent())) + continue; + + if (!isa(Use) && !isa(Use)) { + InvalidInst = true; + break; + } + + if (!GuaranteedToExecute) + GuaranteedToExecute = isSafeToExecuteUnconditionally(*Use); + } - // Update the AST and alias analysis. - CurAST->copyValue(V, AI); + // If there is an non-load/store instruction in the loop, we can't promote + // it. If there isn't a guaranteed-to-execute instruction, we can't + // promote. + if (InvalidInst || !GuaranteedToExecute) + continue; + + const Type *Ty = cast(V->getType())->getElementType(); + AllocaInst *AI = new AllocaInst(Ty, 0, V->getName()+".tmp", FnStart); + PromotedValues.push_back(std::make_pair(AI, V)); - for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) - ValueToAllocaMap.insert(std::make_pair(I->first, AI)); + // Update the AST and alias analysis. + CurAST->copyValue(V, AI); - DOUT << "LICM: Promoting value: " << *V << "\n"; - } - } + for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) + ValueToAllocaMap.insert(std::make_pair(I->getValue(), AI)); + + DEBUG(errs() << "LICM: Promoting value: " << *V << "\n"); } } + +/// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info. +void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) { + AliasSetTracker *AST = LoopToAliasMap[L]; + if (!AST) + return; + + AST->copyValue(From, To); +} + +/// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias +/// set. +void LICM::deleteAnalysisValue(Value *V, Loop *L) { + AliasSetTracker *AST = LoopToAliasMap[L]; + if (!AST) + return; + + AST->deleteValue(V); +}