//===- 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
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.
virtual void deleteValue(Value *V) {
getAnalysis<AliasAnalysis>().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
};
// Register this pass...
- RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
+ RegisterPass<LoadVN> X("load-vn", "Load Value Numbering");
// Declare that we implement the ValueNumbering interface
- RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
+ RegisterAnalysisGroup<ValueNumbering> Y(X);
}
FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
///
void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequired
Transitive<AliasAnalysis>();
AU.addRequired<ValueNumbering>();
- AU.addRequired<DominatorSet>();
- AU.addRequired<TargetData>();
+ AU.addRequiredTransitive<DominatorSet>();
+ AU.addRequiredTransitive<TargetData>();
}
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<BasicBlock*, bool>::iterator TBI =
TransparentBlocks.lower_bound(CurBlock);
} 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.
if (AllOperandsEqual)
IdenticalCalls.push_back(C);
}
-
+
if (IdenticalCalls.empty()) return;
// Eliminate duplicates, which could occur if we chose a value that is passed
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;
LoadInst *LI = cast<LoadInst>(V);
if (LI->isVolatile())
return getAnalysis<ValueNumbering>().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<Value*> 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<BasicBlock*, std::vector<LoadInst*> > CandidateLoads;
- std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
- std::set<AllocationInst*> Allocations;
-
- while (!PointerSources.empty()) {
- Value *Source = PointerSources.back();
- PointerSources.pop_back(); // Get a source pointer...
-
- if (AllocationInst *AI = dyn_cast<AllocationInst>(Source))
- Allocations.insert(AI);
-
- for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
- UI != UE; ++UI)
- if (LoadInst *Cand = dyn_cast<LoadInst>(*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<StoreInst>(*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<AliasAnalysis>();
- DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
- Value *LoadPtr = LI->getOperand(0);
+
// Find out how many bytes of memory are loaded by the load instruction...
unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
-
- // Find all of the candidate loads and stores that are in the same block as
- // the defining instruction.
- std::set<Instruction*> 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<AliasAnalysis>();
// 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
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<LoadInst>(I) && Instrs.count(I)) {
- RetVals.push_back(I);
- Instrs.erase(I);
- } else if (AllocationInst *AI = dyn_cast<AllocationInst>(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<AllocationInst>(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<LoadInst>(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<StoreInst>(I) && Instrs.count(I)) {
- Instrs.erase(I);
- RetVals.push_back(I->getOperand(0));
- }
+ if (StoreInst *SI = dyn_cast<StoreInst>(I))
+ if (SI->getOperand(1) == LoadPtr)
+ RetVals.push_back(I->getOperand(0));
LoadInvalidatedInBBBefore = true;
break;
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<LoadInst>(I) && Instrs.count(I)) {
+ if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
RetVals.push_back(I);
- Instrs.erase(I);
- }
if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
LoadInvalidatedInBBAfter = true;
}
}
- // 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<BasicBlock*, unsigned> CandidateLoads;
+ std::set<BasicBlock*> CandidateStores;
+
+ for (Value::use_iterator UI = LoadPtr->use_begin(), UE = LoadPtr->use_end();
+ UI != UE; ++UI)
+ if (LoadInst *Cand = dyn_cast<LoadInst>(*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<StoreInst>(*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<DominatorSet>();
// 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
// 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<BasicBlock*, std::vector<LoadInst*> >::iterator
+ for (std::map<BasicBlock*, unsigned>::iterator
I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
bool CantEqual = false;
// 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<LoadInst>(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<LoadInst>(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;
BasicBlock::iterator BBI = I->first->end();
while (1) {
--BBI;
- if (isa<LoadInst>(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<LoadInst>(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
}
}
}
-
- Instrs.clear();
}
}
if (LoadInvalidatedInBBBefore)
return;
- for (std::map<BasicBlock*, std::vector<StoreInst*> >::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<BasicBlock*>::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<BasicBlock*> 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;
// 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!");
// If the invalidating instruction is one of the candidates,
// then it provides the value the load loads.
if (StoreInst *SI = dyn_cast<StoreInst>(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;
}
projects / oota-llvm.git / blobdiff