X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLoadValueNumbering.cpp;h=3fbf23806ce60fcb17796f87e06d5de1534ec089;hb=8b0e3602e2b54162e892bddac90b4ab2e13ee0de;hp=d69f83e8a73ab421501ee81eb8a0c7318e05e08e;hpb=2652da6af93360e5e5598bc3ca105439a7a8e1a9;p=oota-llvm.git diff --git a/lib/Analysis/LoadValueNumbering.cpp b/lib/Analysis/LoadValueNumbering.cpp index d69f83e8a73..3fbf23806ce 100644 --- a/lib/Analysis/LoadValueNumbering.cpp +++ b/lib/Analysis/LoadValueNumbering.cpp @@ -1,10 +1,10 @@ //===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===// -// +// // 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 implements a value numbering pass that value numbers load and call @@ -39,16 +39,16 @@ using namespace llvm; namespace { // FIXME: This should not be a FunctionPass. struct LoadVN : public FunctionPass, public ValueNumbering { - + /// Pass Implementation stuff. This doesn't do any analysis. /// bool runOnFunction(Function &) { return false; } - + /// getAnalysisUsage - Does not modify anything. It uses Value Numbering /// and Alias Analysis. /// virtual void getAnalysisUsage(AnalysisUsage &AU) const; - + /// getEqualNumberNodes - Return nodes with the same value number as the /// specified Value. This fills in the argument vector with any equal /// values. @@ -63,7 +63,7 @@ namespace { virtual void deleteValue(Value *V) { getAnalysis().deleteValue(V); } - + /// copyValue - This method should be used whenever a preexisting value in /// the program is copied or cloned, introducing a new value. Note that /// analysis implementations should tolerate clients that use this method to @@ -81,10 +81,10 @@ namespace { }; // Register this pass... - RegisterOpt X("load-vn", "Load Value Numbering"); + RegisterPass X("load-vn", "Load Value Numbering"); // Declare that we implement the ValueNumbering interface - RegisterAnalysisGroup Y; + RegisterAnalysisGroup Y(X); } FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); } @@ -95,10 +95,10 @@ FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); } /// void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); - AU.addRequired(); + AU.addRequiredTransitive(); AU.addRequired(); - AU.addRequired(); - AU.addRequired(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); } static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom, @@ -109,7 +109,7 @@ static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom, // stop searching, returning success. if (CurBlock == Dom || !Visited.insert(CurBlock).second) return true; - + // Check whether this block is known transparent or not. std::map::iterator TBI = TransparentBlocks.lower_bound(CurBlock); @@ -125,7 +125,7 @@ static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom, } else if (!TBI->second) // This block is known non-transparent, so that path can't be either. return false; - + // The current block is known to be transparent. The entire path is // transparent if all of the predecessors paths to the parent is also // transparent to the memory location. @@ -180,7 +180,7 @@ void LoadVN::getCallEqualNumberNodes(CallInst *CI, if (AllOperandsEqual) IdenticalCalls.push_back(C); } - + if (IdenticalCalls.empty()) return; // Eliminate duplicates, which could occur if we chose a value that is passed @@ -212,7 +212,7 @@ void LoadVN::getCallEqualNumberNodes(CallInst *CI, Instruction *First = CI, *Second = C; if (!DomSetInfo.dominates(CI, C)) std::swap(First, Second); - + // Scan the instructions between the calls, checking for stores or // calls to dangerous functions. BasicBlock::iterator I = First; @@ -283,64 +283,14 @@ void LoadVN::getEqualNumberNodes(Value *V, LoadInst *LI = cast(V); if (LI->isVolatile()) return getAnalysis().getEqualNumberNodes(V, RetVals); - - // If we have a load instruction, find all of the load and store instructions - // that use the same source operand. We implement this recursively, because - // there could be a load of a load of a load that are all identical. We are - // guaranteed that this cannot be an infinite recursion because load - // instructions would have to pass through a PHI node in order for there to be - // a cycle. The PHI node would be handled by the else case here, breaking the - // infinite recursion. - // - std::vector PointerSources; - getEqualNumberNodes(LI->getOperand(0), PointerSources); - PointerSources.push_back(LI->getOperand(0)); - + + Value *LoadPtr = LI->getOperand(0); BasicBlock *LoadBB = LI->getParent(); Function *F = LoadBB->getParent(); - - // Now that we know the set of equivalent source pointers for the load - // instruction, look to see if there are any load or store candidates that are - // identical. - // - std::map > CandidateLoads; - std::map > CandidateStores; - std::set Allocations; - - while (!PointerSources.empty()) { - Value *Source = PointerSources.back(); - PointerSources.pop_back(); // Get a source pointer... - - if (AllocationInst *AI = dyn_cast(Source)) - Allocations.insert(AI); - - for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end(); - UI != UE; ++UI) - if (LoadInst *Cand = dyn_cast(*UI)) {// Is a load of source? - if (Cand->getParent()->getParent() == F && // In the same function? - Cand != LI && !Cand->isVolatile()) // Not LI itself? - CandidateLoads[Cand->getParent()].push_back(Cand); // Got one... - } else if (StoreInst *Cand = dyn_cast(*UI)) { - if (Cand->getParent()->getParent() == F && !Cand->isVolatile() && - Cand->getOperand(1) == Source) // It's a store THROUGH the ptr... - CandidateStores[Cand->getParent()].push_back(Cand); - } - } - - // Get alias analysis & dominators. - AliasAnalysis &AA = getAnalysis(); - DominatorSet &DomSetInfo = getAnalysis(); - Value *LoadPtr = LI->getOperand(0); + // Find out how many bytes of memory are loaded by the load instruction... unsigned LoadSize = getAnalysis().getTypeSize(LI->getType()); - - // Find all of the candidate loads and stores that are in the same block as - // the defining instruction. - std::set Instrs; - Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end()); - CandidateLoads.erase(LoadBB); - Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end()); - CandidateStores.erase(LoadBB); + AliasAnalysis &AA = getAnalysis(); // Figure out if the load is invalidated from the entry of the block it is in // until the actual instruction. This scans the block backwards from LI. If @@ -349,30 +299,31 @@ void LoadVN::getEqualNumberNodes(Value *V, bool LoadInvalidatedInBBBefore = false; for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) { --I; - // If this instruction is a candidate load before LI, we know there are no - // invalidating instructions between it and LI, so they have the same value - // number. - if (isa(I) && Instrs.count(I)) { - RetVals.push_back(I); - Instrs.erase(I); - } else if (AllocationInst *AI = dyn_cast(I)) { + if (I == LoadPtr) { // If we run into an allocation of the value being loaded, then the // contents are not initialized. - if (Allocations.count(AI)) { - LoadInvalidatedInBBBefore = true; + if (isa(I)) RetVals.push_back(UndefValue::get(LI->getType())); - break; - } + + // Otherwise, since this is the definition of what we are loading, this + // loaded value cannot occur before this block. + LoadInvalidatedInBBBefore = true; + break; + } else if (LoadInst *LI = dyn_cast(I)) { + // If this instruction is a candidate load before LI, we know there are no + // invalidating instructions between it and LI, so they have the same + // value number. + if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) + RetVals.push_back(I); } if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) { // If the invalidating instruction is a store, and its in our candidate // set, then we can do store-load forwarding: the load has the same value // # as the stored value. - if (isa(I) && Instrs.count(I)) { - Instrs.erase(I); - RetVals.push_back(I->getOperand(0)); - } + if (StoreInst *SI = dyn_cast(I)) + if (SI->getOperand(1) == LoadPtr) + RetVals.push_back(I->getOperand(0)); LoadInvalidatedInBBBefore = true; break; @@ -387,10 +338,8 @@ void LoadVN::getEqualNumberNodes(Value *V, for (BasicBlock::iterator I = LI->getNext(); I != LoadBB->end(); ++I) { // If this instruction is a load, then this instruction returns the same // value as LI. - if (isa(I) && Instrs.count(I)) { + if (isa(I) && cast(I)->getOperand(0) == LoadPtr) RetVals.push_back(I); - Instrs.erase(I); - } if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) { LoadInvalidatedInBBAfter = true; @@ -398,9 +347,33 @@ void LoadVN::getEqualNumberNodes(Value *V, } } - // If there is anything left in the Instrs set, it could not possibly equal - // LI. - Instrs.clear(); + // If the pointer is clobbered on entry and on exit to the function, there is + // no need to do any global analysis at all. + if (LoadInvalidatedInBBBefore && LoadInvalidatedInBBAfter) + return; + + // Now that we know the value is not neccesarily killed on entry or exit to + // the BB, find out how many load and store instructions (to this location) + // live in each BB in the function. + // + std::map CandidateLoads; + std::set CandidateStores; + + for (Value::use_iterator UI = LoadPtr->use_begin(), UE = LoadPtr->use_end(); + UI != UE; ++UI) + if (LoadInst *Cand = dyn_cast(*UI)) {// Is a load of source? + if (Cand->getParent()->getParent() == F && // In the same function? + // Not in LI's block? + Cand->getParent() != LoadBB && !Cand->isVolatile()) + ++CandidateLoads[Cand->getParent()]; // Got one. + } else if (StoreInst *Cand = dyn_cast(*UI)) { + if (Cand->getParent()->getParent() == F && !Cand->isVolatile() && + Cand->getOperand(1) == LoadPtr) // It's a store THROUGH the ptr. + CandidateStores.insert(Cand->getParent()); + } + + // Get dominators. + DominatorSet &DomSetInfo = getAnalysis(); // TransparentBlocks - For each basic block the load/store is alive across, // figure out if the pointer is invalidated or not. If it is invalidated, the @@ -412,7 +385,7 @@ void LoadVN::getEqualNumberNodes(Value *V, // is live across the CFG from the source to destination blocks, and if the // value is not invalidated in either the source or destination blocks, add it // to the equivalence sets. - for (std::map >::iterator + for (std::map::iterator I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) { bool CantEqual = false; @@ -454,18 +427,19 @@ void LoadVN::getEqualNumberNodes(Value *V, // For any loads that are not invalidated, add them to the equivalence // set! if (!CantEqual) { - Instrs.insert(I->second.begin(), I->second.end()); + unsigned NumLoads = I->second; if (BB1 == LoadBB) { // If LI dominates the block in question, check to see if any of the // loads in this block are invalidated before they are reached. for (BasicBlock::iterator BBI = I->first->begin(); ; ++BBI) { - if (isa(BBI) && Instrs.count(BBI)) { - // The load is in the set! - RetVals.push_back(BBI); - Instrs.erase(BBI); - if (Instrs.empty()) break; + if (LoadInst *LI = dyn_cast(BBI)) { + if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) { + // The load is in the set! + RetVals.push_back(BBI); + if (--NumLoads == 0) break; // Found last load to check. + } } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) - & AliasAnalysis::Mod) { + & AliasAnalysis::Mod) { // If there is a modifying instruction, nothing below it will value // # the same. break; @@ -477,11 +451,12 @@ void LoadVN::getEqualNumberNodes(Value *V, BasicBlock::iterator BBI = I->first->end(); while (1) { --BBI; - if (isa(BBI) && Instrs.count(BBI)) { - // The load is in the set! - RetVals.push_back(BBI); - Instrs.erase(BBI); - if (Instrs.empty()) break; + if (LoadInst *LI = dyn_cast(BBI)) { + if (LI->getOperand(0) == LoadPtr && !LI->isVolatile()) { + // The load is the same as this load! + RetVals.push_back(BBI); + if (--NumLoads == 0) break; // Found all of the laods. + } } else if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) { // If there is a modifying instruction, nothing above it will value @@ -490,8 +465,6 @@ void LoadVN::getEqualNumberNodes(Value *V, } } } - - Instrs.clear(); } } @@ -501,16 +474,21 @@ void LoadVN::getEqualNumberNodes(Value *V, if (LoadInvalidatedInBBBefore) return; - for (std::map >::iterator - I = CandidateStores.begin(), E = CandidateStores.end(); I != E; ++I) - if (DomSetInfo.dominates(I->first, LoadBB)) { + // Stores in the load-bb are handled above. + CandidateStores.erase(LoadBB); + + for (std::set::iterator I = CandidateStores.begin(), + E = CandidateStores.end(); I != E; ++I) + if (DomSetInfo.dominates(*I, LoadBB)) { + BasicBlock *StoreBB = *I; + // Check to see if the path from the store to the load is transparent // w.r.t. the memory location. bool CantEqual = false; std::set Visited; for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB); PI != E; ++PI) - if (!isPathTransparentTo(*PI, I->first, LoadPtr, LoadSize, AA, + if (!isPathTransparentTo(*PI, StoreBB, LoadPtr, LoadSize, AA, Visited, TransparentBlocks)) { // None of these stores can VN the same. CantEqual = true; @@ -523,9 +501,9 @@ void LoadVN::getEqualNumberNodes(Value *V, // of the load block to the load itself. Now we just scan the store // block. - BasicBlock::iterator BBI = I->first->end(); + BasicBlock::iterator BBI = StoreBB->end(); while (1) { - assert(BBI != I->first->begin() && + assert(BBI != StoreBB->begin() && "There is a store in this block of the pointer, but the store" " doesn't mod the address being stored to?? Must be a bug in" " the alias analysis implementation!"); @@ -534,8 +512,7 @@ void LoadVN::getEqualNumberNodes(Value *V, // If the invalidating instruction is one of the candidates, // then it provides the value the load loads. if (StoreInst *SI = dyn_cast(BBI)) - if (std::find(I->second.begin(), I->second.end(), SI) != - I->second.end()) + if (SI->getOperand(1) == LoadPtr) RetVals.push_back(SI->getOperand(0)); break; }