X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLICM.cpp;h=40af0a811d103650c5417abfd6874636472d4f62;hb=9289ae85b41eef62ae1fadb93e99d33f723fb682;hp=3a7adef56ebc71a113e6029f3c56b6186818b123;hpb=9133fe28954d498fc4de13064c7d65bd811de02c;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index 3a7adef56eb..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,16 +35,19 @@ #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" +#include "llvm/Analysis/LoopPass.h" #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 @@ -56,13 +59,25 @@ 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"); +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")); + namespace { - cl::opt - DisablePromotion("disable-licm-promotion", cl::Hidden, - cl::desc("Disable memory promotion in LICM pass")); + struct LICM : public LoopPass { + static char ID; // Pass identification, replacement for typeid + LICM() : LoopPass(&ID) {} - struct VISIBILITY_HIDDEN LICM : public FunctionPass { - virtual bool runOnFunction(Function &F); + virtual bool runOnLoop(Loop *L, LPPassManager &LPM); /// This transformation requires natural loop information & requires that /// loop preheaders be inserted into the CFG... @@ -74,6 +89,19 @@ namespace { 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; } private: @@ -88,10 +116,14 @@ namespace { BasicBlock *Preheader; // The preheader block of the current loop... Loop *CurLoop; // The current loop we are working on... AliasSetTracker *CurAST; // AliasSet information for the current loop... + std::map LoopToAliasMap; - /// visitLoop - Hoist expressions out of the specified loop... - /// - void visitLoop(Loop *L, AliasSetTracker &AST); + /// 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 @@ -99,7 +131,7 @@ namespace { /// visit uses before definitions, allowing us to sink a loop body in one /// pass without iteration. /// - void SinkRegion(DominatorTree::Node *N); + void SinkRegion(DomTreeNode *N); /// HoistRegion - Walk the specified region of the CFG (defined by all /// blocks dominated by the specified block, and that are in the current @@ -107,7 +139,11 @@ namespace { /// visit definitions before uses, allowing us to hoist a loop body in one /// pass without iteration. /// - void HoistRegion(DominatorTree::Node *N); + 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. @@ -132,8 +168,8 @@ namespace { if (BlockInLoop == LoopHeader) return true; - DominatorTree::Node *BlockInLoopNode = DT->getNode(BlockInLoop); - DominatorTree::Node *IDom = DT->getNode(ExitBlock); + DomTreeNode *BlockInLoopNode = DT->getNode(BlockInLoop); + DomTreeNode *IDom = DT->getNode(ExitBlock); // Because the exit block is not in the loop, we know we have to get _at // least_ its immediate dominator. @@ -195,16 +231,18 @@ namespace { std::vector > &PromotedValues, std::map &Val2AlMap); }; - - RegisterPass X("licm", "Loop Invariant Code Motion"); } -FunctionPass *llvm::createLICMPass() { return new LICM(); } +char LICM::ID = 0; +static RegisterPass X("licm", "Loop Invariant Code Motion"); + +Pass *llvm::createLICMPass() { return new LICM(); } -/// runOnFunction - For LICM, this simply traverses the loop structure of the -/// function, hoisting expressions out of loops if possible. +/// 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::runOnFunction(Function &) { +bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) { Changed = false; // Get our Loop and Alias Analysis information... @@ -213,28 +251,19 @@ bool LICM::runOnFunction(Function &) { DF = &getAnalysis(); DT = &getAnalysis(); - // Hoist expressions out of all of the top-level loops. - for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { - AliasSetTracker AST(*AA); - visitLoop(*I, AST); - } - return Changed; -} - + CurAST = new AliasSetTracker(*AA); + // Collect Alias info from subloops + for (Loop::iterator LoopItr = L->begin(), LoopItrE = L->end(); + LoopItr != LoopItrE; ++LoopItr) { + Loop *InnerL = *LoopItr; + AliasSetTracker *InnerAST = LoopToAliasMap[InnerL]; + assert (InnerAST && "Where is my AST?"); -/// visitLoop - Hoist expressions out of the specified loop... -/// -void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { - // Recurse through all subloops before we process this loop... - for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { - AliasSetTracker SubAST(*AA); - visitLoop(*I, SubAST); - - // Incorporate information about the subloops into this loop... - AST.add(SubAST); + // What if InnerLoop was modified by other passes ? + CurAST->add(*InnerAST); } + CurLoop = L; - CurAST = &AST; // Get the preheader block to move instructions into... Preheader = L->getLoopPreheader(); @@ -244,10 +273,12 @@ void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { // 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... - AST.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 @@ void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { // // 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... @@ -270,6 +302,9 @@ void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { // Clear out loops state information for the next iteration CurLoop = 0; Preheader = 0; + + LoopToAliasMap[L] = CurAST; + return Changed; } /// SinkRegion - Walk the specified region of the CFG (defined by all blocks @@ -278,7 +313,7 @@ void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { /// uses before definitions, allowing us to sink a loop body in one pass without /// iteration. /// -void LICM::SinkRegion(DominatorTree::Node *N) { +void LICM::SinkRegion(DomTreeNode *N) { assert(N != 0 && "Null dominator tree node?"); BasicBlock *BB = N->getBlock(); @@ -286,7 +321,7 @@ void LICM::SinkRegion(DominatorTree::Node *N) { if (!CurLoop->contains(BB)) return; // We are processing blocks in reverse dfo, so process children first... - const std::vector &Children = N->getChildren(); + const std::vector &Children = N->getChildren(); for (unsigned i = 0, e = Children.size(); i != e; ++i) SinkRegion(Children[i]); @@ -309,13 +344,42 @@ void LICM::SinkRegion(DominatorTree::Node *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 /// first order w.r.t the DominatorTree. This allows us to visit definitions /// before uses, allowing us to hoist a loop body in one pass without iteration. /// -void LICM::HoistRegion(DominatorTree::Node *N) { +void LICM::HoistRegion(DomTreeNode *N) { assert(N != 0 && "Null dominator tree node?"); BasicBlock *BB = N->getBlock(); @@ -337,7 +401,7 @@ void LICM::HoistRegion(DominatorTree::Node *N) { hoist(I); } - const std::vector &Children = N->getChildren(); + const std::vector &Children = N->getChildren(); for (unsigned i = 0, e = Children.size(); i != e; ++i) HoistRegion(Children[i]); } @@ -351,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 @@ -386,7 +458,9 @@ bool LICM::canSinkOrHoistInst(Instruction &I) { // Otherwise these instructions are hoistable/sinkable return isa(I) || isa(I) || - isa(I) || isa(I) || isa(I); + isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || + isa(I); } /// isNotUsedInLoop - Return true if the only users of this instruction are @@ -430,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; @@ -454,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. @@ -473,9 +545,11 @@ 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()->front().begin()); + I.getParent()->getParent()->getEntryBlock().begin()); + CurAST->add(AI); + } // Secondly, insert load instructions for each use of the instruction // outside of the loop. @@ -496,6 +570,7 @@ void LICM::sink(Instruction &I) { // Insert a new load instruction right before the terminator in // the predecessor block. PredVal = new LoadInst(AI, "", Pred->getTerminator()); + CurAST->add(cast(PredVal)); } UPN->setIncomingValue(i, PredVal); @@ -504,6 +579,7 @@ void LICM::sink(Instruction &I) { } else { LoadInst *L = new LoadInst(AI, "", U); U->replaceUsesOfWith(&I, L); + CurAST->add(L); } } @@ -521,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 @@ -556,7 +631,7 @@ void LICM::sink(Instruction &I) { if (AI) { std::vector Allocas; Allocas.push_back(AI); - PromoteMemToReg(Allocas, *DT, *DF, AA->getTargetData(), CurAST); + PromoteMemToReg(Allocas, *DT, *DF, AI->getContext(), CurAST); } } } @@ -565,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. @@ -586,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 @@ -598,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 @@ -679,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)); @@ -705,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. @@ -737,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, AA->getTargetData(), 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) { @@ -757,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); +}