X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLICM.cpp;h=5275de4d59177a63e867dd59cd28adc3c5818da7;hb=98bf436e2e2ab463d79c54a42a46b12028905330;hp=534a073abe190bf04d33a54477006545327a8a51;hpb=8601a9bf54049389e0e0b6a907dc51069dcadc60;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp index 534a073abe1..5275de4d591 100644 --- a/lib/Transforms/Scalar/LICM.cpp +++ b/lib/Transforms/Scalar/LICM.cpp @@ -24,13 +24,16 @@ #include "llvm/Transforms/Utils/Local.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Instructions.h" #include "llvm/DerivedTypes.h" +#include "llvm/Target/TargetData.h" #include "llvm/Support/InstVisitor.h" #include "llvm/Support/CFG.h" -#include "Support/Statistic.h" #include "Support/CommandLine.h" +#include "Support/Debug.h" +#include "Support/Statistic.h" #include "llvm/Assembly/Writer.h" #include @@ -42,106 +45,6 @@ namespace { Statistic<> NumHoistedLoads("licm", "Number of load insts hoisted"); Statistic<> NumPromoted("licm", "Number of memory locations promoted to registers"); - /// LoopBodyInfo - We recursively traverse loops from most-deeply-nested to - /// least-deeply-nested. For all of the loops nested within the current one, - /// we keep track of information so that we don't have to repeat queries. - /// - struct LoopBodyInfo { - std::vector Calls; // Call instructions in loop - std::vector Invokes; // Invoke instructions in loop - - // StoredPointers - Targets of store instructions... - std::set StoredPointers; - - // LoadedPointers - Source pointers for load instructions... - std::set LoadedPointers; - - enum PointerClass { - PointerUnknown = 0, // Nothing is known about this pointer yet - PointerMustStore, // Memory is stored to ONLY through this pointer - PointerMayStore, // Memory is stored to through this or other pointers - PointerNoStore // Memory is not modified in this loop - }; - - // PointerIsModified - Keep track of information as we find out about it in - // the loop body... - // - std::map PointerIsModified; - - /// CantModifyAnyPointers - Return true if no memory modifying instructions - /// occur in this loop. This is just a conservative approximation, because - /// a call may not actually store anything. - bool CantModifyAnyPointers() const { - return Calls.empty() && Invokes.empty() && StoredPointers.empty(); - } - - /// incorporate - Incorporate information about a subloop into the current - /// loop. - void incorporate(const LoopBodyInfo &OtherLBI); - void incorporate(BasicBlock &BB); // do the same for a basic block - - PointerClass getPointerInfo(Value *V, AliasAnalysis &AA) { - PointerClass &VInfo = PointerIsModified[V]; - if (VInfo == PointerUnknown) - VInfo = calculatePointerInfo(V, AA); - return VInfo; - } - private: - /// calculatePointerInfo - Calculate information about the specified - /// pointer. - PointerClass calculatePointerInfo(Value *V, AliasAnalysis &AA) const; - }; -} - -/// incorporate - Incorporate information about a subloop into the current loop. -void LoopBodyInfo::incorporate(const LoopBodyInfo &OtherLBI) { - // Do not incorporate NonModifiedPointers (which is just a cache) because it - // is too much trouble to make sure it's still valid. - Calls.insert (Calls.end(), OtherLBI.Calls.begin(), OtherLBI.Calls.end()); - Invokes.insert(Invokes.end(),OtherLBI.Invokes.begin(),OtherLBI.Invokes.end()); - StoredPointers.insert(OtherLBI.StoredPointers.begin(), - OtherLBI.StoredPointers.end()); - LoadedPointers.insert(OtherLBI.LoadedPointers.begin(), - OtherLBI.LoadedPointers.end()); -} - -void LoopBodyInfo::incorporate(BasicBlock &BB) { - for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) - if (CallInst *CI = dyn_cast(&*I)) - Calls.push_back(CI); - else if (StoreInst *SI = dyn_cast(&*I)) - StoredPointers.insert(SI->getOperand(1)); - else if (LoadInst *LI = dyn_cast(&*I)) - LoadedPointers.insert(LI->getOperand(0)); - - if (InvokeInst *II = dyn_cast(BB.getTerminator())) - Invokes.push_back(II); -} - - -// calculatePointerInfo - Calculate information about the specified pointer. -LoopBodyInfo::PointerClass LoopBodyInfo::calculatePointerInfo(Value *V, - AliasAnalysis &AA) const { - for (unsigned i = 0, e = Calls.size(); i != e; ++i) - if (AA.getModRefInfo(Calls[i], V, ~0)) - return PointerMayStore; - - for (unsigned i = 0, e = Invokes.size(); i != e; ++i) - if (AA.getModRefInfo(Invokes[i], V, ~0)) - return PointerMayStore; - - PointerClass Result = PointerNoStore; - for (std::set::const_iterator I = StoredPointers.begin(), - E = StoredPointers.end(); I != E; ++I) - if (AA.alias(V, ~0, *I, ~0)) - if (V == *I) - Result = PointerMustStore; // If this is the only alias, return must - else - return PointerMayStore; // We have to return may - return Result; -} - -namespace { struct LICM : public FunctionPass, public InstVisitor { virtual bool runOnFunction(Function &F); @@ -150,29 +53,31 @@ namespace { /// virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); - AU.addRequiredID(LoopPreheadersID); + AU.addRequiredID(LoopSimplifyID); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); // For scalar promotion (mem2reg) AU.addRequired(); } private: LoopInfo *LI; // Current LoopInfo AliasAnalysis *AA; // Current AliasAnalysis information + DominanceFrontier *DF; // Current Dominance Frontier bool Changed; // Set to true when we change anything. BasicBlock *Preheader; // The preheader block of the current loop... Loop *CurLoop; // The current loop we are working on... - LoopBodyInfo *CurLBI; // Information about the current loop... + AliasSetTracker *CurAST; // AliasSet information for the current loop... + DominatorTree *DT; // Dominator Tree for the current Loop... /// visitLoop - Hoist expressions out of the specified loop... /// - void visitLoop(Loop *L, LoopBodyInfo &LBI); + void visitLoop(Loop *L, AliasSetTracker &AST); /// 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 defintions before uses, allowing us to hoist a loop body in one + /// visit definitions before uses, allowing us to hoist a loop body in one /// pass without iteration. /// void HoistRegion(DominatorTree::Node *N); @@ -193,12 +98,17 @@ namespace { /// void hoist(Instruction &I); + /// SafeToHoist - Only hoist an instruction if it is not a trapping instruction + /// or if it is a trapping instruction and is guaranteed to execute + /// + bool SafeToHoist(Instruction &I); + /// pointerInvalidatedByLoop - Return true if the body of this loop may /// store into the memory location pointed to by V. /// bool pointerInvalidatedByLoop(Value *V) { - // Check to see if any of the basic blocks in CurLoop invalidate V. - return CurLBI->getPointerInfo(V, *AA) != LoopBodyInfo::PointerNoStore; + // Check to see if any of the basic blocks in CurLoop invalidate *V. + return CurAST->getAliasSetForPointer(V, 0).isMod(); } /// isLoopInvariant - Return true if the specified value is loop invariant @@ -215,7 +125,7 @@ namespace { void PromoteValuesInLoop(); /// findPromotableValuesInLoop - Check the current loop for stores to - /// definate pointers, which are not loaded and stored through may aliases. + /// 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... @@ -230,12 +140,12 @@ namespace { /// friend class InstVisitor; void visitBinaryOperator(Instruction &I) { - if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1))) + if (isLoopInvariant(I.getOperand(0)) && isLoopInvariant(I.getOperand(1)) && SafeToHoist(I)) hoist(I); } void visitCastInst(CastInst &CI) { Instruction &I = (Instruction&)CI; - if (isLoopInvariant(I.getOperand(0))) hoist(I); + if (isLoopInvariant(I.getOperand(0)) && SafeToHoist(CI)) hoist(I); } void visitShiftInst(ShiftInst &I) { visitBinaryOperator((Instruction&)I); } @@ -245,7 +155,8 @@ namespace { Instruction &I = (Instruction&)GEPI; for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) if (!isLoopInvariant(I.getOperand(i))) return; - hoist(I); + if(SafeToHoist(GEPI)) + hoist(I); } }; @@ -263,13 +174,15 @@ bool LICM::runOnFunction(Function &) { // Get our Loop and Alias Analysis information... LI = &getAnalysis(); AA = &getAnalysis(); + DF = &getAnalysis(); + DT = &getAnalysis(); // Hoist expressions out of all of the top-level loops. const std::vector &TopLevelLoops = LI->getTopLevelLoops(); for (std::vector::const_iterator I = TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) { - LoopBodyInfo LBI; - LICM::visitLoop(*I, LBI); + AliasSetTracker AST(*AA); + LICM::visitLoop(*I, AST); } return Changed; } @@ -277,32 +190,32 @@ bool LICM::runOnFunction(Function &) { /// visitLoop - Hoist expressions out of the specified loop... /// -void LICM::visitLoop(Loop *L, LoopBodyInfo &LBI) { +void LICM::visitLoop(Loop *L, AliasSetTracker &AST) { // Recurse through all subloops before we process this loop... for (std::vector::const_iterator I = L->getSubLoops().begin(), E = L->getSubLoops().end(); I != E; ++I) { - LoopBodyInfo SubLBI; - LICM::visitLoop(*I, SubLBI); + AliasSetTracker SubAST(*AA); + LICM::visitLoop(*I, SubAST); // Incorporate information about the subloops into this loop... - LBI.incorporate(SubLBI); + AST.add(SubAST); } CurLoop = L; - CurLBI = &LBI; + CurAST = &AST; // Get the preheader block to move instructions into... Preheader = L->getLoopPreheader(); assert(Preheader&&"Preheader insertion pass guarantees we have a preheader!"); // Loop over the body of this loop, looking for calls, invokes, and stores. - // Because subloops have already been incorporated into LBI, we skip blocks in + // Because subloops have already been incorporated into AST, we skip blocks in // subloops. // const std::vector &LoopBBs = L->getBlocks(); for (std::vector::const_iterator I = LoopBBs.begin(), E = LoopBBs.end(); I != E; ++I) if (LI->getLoopFor(*I) == L) // Ignore blocks in subloops... - LBI.incorporate(**I); // Incorporate the specified basic block + AST.add(**I); // 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 @@ -313,7 +226,7 @@ void LICM::visitLoop(Loop *L, LoopBodyInfo &LBI) { // that we are guaranteed to see definitions before we see uses. This allows // us to perform the LICM transformation in one pass, without iteration. // - HoistRegion(getAnalysis()[L->getHeader()]); + HoistRegion(DT->getNode(L->getHeader())); // Now that all loop invariants have been removed from the loop, promote any // memory references to scalars that we can... @@ -327,19 +240,19 @@ void LICM::visitLoop(Loop *L, LoopBodyInfo &LBI) { /// 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 defintions +/// 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) { assert(N != 0 && "Null dominator tree node?"); // If this subregion is not in the top level loop at all, exit. - if (!CurLoop->contains(N->getNode())) return; + if (!CurLoop->contains(N->getBlock())) return; // Only need to hoist the contents of this block if it is not part of a // subloop (which would already have been hoisted) - if (!inSubLoop(N->getNode())) - visit(*N->getNode()); + if (!inSubLoop(N->getBlock())) + visit(*N->getBlock()); const std::vector &Children = N->getChildren(); for (unsigned i = 0, e = Children.size(); i != e; ++i) @@ -366,10 +279,47 @@ void LICM::hoist(Instruction &Inst) { Changed = true; } +/// SafeToHoist - Only hoist an instruction if it is not a trapping instruction +/// or if it is a trapping instruction and is guaranteed to execute +/// +bool LICM::SafeToHoist(Instruction &Inst) { + + //If it is a trapping instruction, then check if its guaranteed to execute. + if(Inst.isTrapping()) { + + //Get the instruction's basic block. + BasicBlock *InstBB = Inst.getParent(); + + //Get the Dominator Tree Node for the instruction's basic block/ + DominatorTree::Node *InstDTNode = DT->getNode(InstBB); + + //Get the exit blocks for the current loop. + const std::vector &ExitBlocks = CurLoop->getExitBlocks(); + + //For each exit block, get the DT node and walk up the DT until + //the instruction's basic block is found or we exit the loop. + for(unsigned i=0; i < ExitBlocks.size(); ++i) { + DominatorTree::Node *IDom = DT->getNode(ExitBlocks[i]); + + while(IDom != InstDTNode) { + + //Get next Immediate Dominator. + IDom = IDom->getIDom(); + + //See if we exited the loop. + if(!CurLoop->contains(IDom->getBlock())) + return false; + } + } + } + + return true; +} + void LICM::visitLoadInst(LoadInst &LI) { - if (isLoopInvariant(LI.getOperand(0)) && - !pointerInvalidatedByLoop(LI.getOperand(0))) { + if (isLoopInvariant(LI.getOperand(0)) && !LI.isVolatile() && + !pointerInvalidatedByLoop(LI.getOperand(0)) && SafeToHoist(LI)) { hoist(LI); ++NumHoistedLoads; } @@ -384,7 +334,7 @@ void LICM::visitLoadInst(LoadInst &LI) { /// void LICM::PromoteValuesInLoop() { // PromotedValues - List of values that are promoted out of the loop. Each - // value has an alloca instruction for it, and a cannonical version of the + // value has an alloca instruction for it, and a canonical version of the // pointer. std::vector > PromotedValues; std::map ValueToAllocaMap; // Map of ptr to alloca @@ -417,12 +367,12 @@ void LICM::PromoteValuesInLoop() { // Rewrite all loads and stores in the block of the pointer... for (BasicBlock::iterator II = (*I)->begin(), E = (*I)->end(); II != E; ++II) { - if (LoadInst *L = dyn_cast(&*II)) { + if (LoadInst *L = dyn_cast(II)) { std::map::iterator I = ValueToAllocaMap.find(L->getOperand(0)); if (I != ValueToAllocaMap.end()) L->setOperand(0, I->second); // Rewrite load instruction... - } else if (StoreInst *S = dyn_cast(&*II)) { + } else if (StoreInst *S = dyn_cast(II)) { std::map::iterator I = ValueToAllocaMap.find(S->getOperand(1)); if (I != ValueToAllocaMap.end()) @@ -457,10 +407,10 @@ 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, getAnalysis()); + PromoteMemToReg(PromotedAllocas, *DT, *DF, AA->getTargetData()); } -/// findPromotableValuesInLoop - Check the current loop for stores to definate +/// 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... @@ -470,51 +420,37 @@ void LICM::findPromotableValuesInLoop( std::map &ValueToAllocaMap) { Instruction *FnStart = CurLoop->getHeader()->getParent()->begin()->begin(); - for (std::set::iterator I = CurLBI->StoredPointers.begin(), - E = CurLBI->StoredPointers.end(); I != E; ++I) { - Value *V = *I; - if (isLoopInvariant(V) && - CurLBI->getPointerInfo(V, *AA) == LoopBodyInfo::PointerMustStore) { - - // Don't add a new entry for this stored pointer if it aliases something - // we have already processed. - std::map::iterator V2AMI = - ValueToAllocaMap.lower_bound(V); - if (V2AMI == ValueToAllocaMap.end() || V2AMI->first != V) { - // Check to make sure that any loads in the loop are either NO or MUST - // aliases. We cannot rewrite loads that _might_ come from this memory - // location. - - bool PointerOk = true; - for (std::set::const_iterator I =CurLBI->LoadedPointers.begin(), - E = CurLBI->LoadedPointers.end(); I != E; ++I) - if (AA->alias(V, ~0, *I, ~0) == AliasAnalysis::MayAlias) { - PointerOk = false; - break; - } - - 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)); - ValueToAllocaMap.insert(V2AMI, std::make_pair(V, AI)); - - DEBUG(std::cerr << "LICM: Promoting value: " << *V << "\n"); - - // Loop over all of the loads and stores that alias this pointer, - // adding them to the Value2AllocaMap as well... - for (std::set::const_iterator - I = CurLBI->LoadedPointers.begin(), - E = CurLBI->LoadedPointers.end(); I != E; ++I) - if (AA->alias(V, ~0, *I, ~0) == AliasAnalysis::MustAlias) - ValueToAllocaMap[*I] = AI; - - for (std::set::const_iterator - I = CurLBI->StoredPointers.begin(), - E = CurLBI->StoredPointers.end(); I != E; ++I) - if (AA->alias(V, ~0, *I, ~0) == AliasAnalysis::MustAlias) - ValueToAllocaMap[*I] = AI; + // Loop over all of the alias sets in the tracker object... + for (AliasSetTracker::iterator I = CurAST->begin(), E = CurAST->end(); + I != E; ++I) { + AliasSet &AS = *I; + // We can promote this alias set if it has a store, if it is a "Must" alias + // set, and if the pointer is loop invariant. + if (!AS.isForwardingAliasSet() && AS.isMod() && AS.isMustAlias() && + 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. + bool PointerOk = true; + for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) + if (V->getType() != I->first->getType()) { + PointerOk = false; + break; } + + 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)); + + for (AliasSet::iterator I = AS.begin(), E = AS.end(); I != E; ++I) + ValueToAllocaMap.insert(std::make_pair(I->first, AI)); + + DEBUG(std::cerr << "LICM: Promoting value: " << *V << "\n"); } } }