//===- 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 #'s load instructions.
-// To do this, it finds lexically identical load instructions, and uses alias
-// analysis to determine which loads are guaranteed to produce the same value.
+// This file implements a value numbering pass that value numbers load and call
+// instructions. To do this, it finds lexically identical load instructions,
+// and uses alias analysis to determine which loads are guaranteed to produce
+// the same value. To value number call instructions, it looks for calls to
+// functions that do not write to memory which do not have intervening
+// instructions that clobber the memory that is read from.
//
// This pass builds off of another value numbering pass to implement value
-// numbering for non-load instructions. It uses Alias Analysis so that it can
-// disambiguate the load instructions. The more powerful these base analyses
-// are, the more powerful the resultant analysis will be.
+// numbering for non-load and non-call instructions. It uses Alias Analysis so
+// that it can disambiguate the load instructions. The more powerful these base
+// analyses are, the more powerful the resultant value numbering will be.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/LoadValueNumbering.h"
+#include "llvm/Constants.h"
+#include "llvm/Function.h"
+#include "llvm/Instructions.h"
+#include "llvm/Pass.h"
+#include "llvm/Type.h"
#include "llvm/Analysis/ValueNumbering.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Pass.h"
-#include "llvm/Type.h"
-#include "llvm/iMemory.h"
-#include "llvm/BasicBlock.h"
#include "llvm/Support/CFG.h"
-#include <algorithm>
+#include "llvm/Support/Compiler.h"
+#include "llvm/Target/TargetData.h"
#include <set>
+#include <algorithm>
using namespace llvm;
namespace {
// FIXME: This should not be a FunctionPass.
- struct LoadVN : public FunctionPass, public ValueNumbering {
-
+ struct VISIBILITY_HIDDEN LoadVN : public FunctionPass, public ValueNumbering {
+ static char ID; // Class identification, replacement for typeinfo
+ LoadVN() : FunctionPass((intptr_t)&ID) {}
+
/// 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 getEqualNumberNodes(Value *V1,
std::vector<Value*> &RetVals) const;
- private:
- /// haveEqualValueNumber - Given two load instructions, determine if they
- /// both produce the same value on every execution of the program, assuming
- /// that their source operands always give the same value. This uses the
- /// AliasAnalysis implementation to invalidate loads when stores or function
- /// calls occur that could modify the value produced by the load.
+
+ /// deleteValue - This method should be called whenever an LLVM Value is
+ /// deleted from the program, for example when an instruction is found to be
+ /// redundant and is eliminated.
+ ///
+ 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
+ /// introduce the same value multiple times: if the analysis already knows
+ /// about a value, it should ignore the request.
///
- bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA,
- DominatorSet &DomSetInfo) const;
- bool haveEqualValueNumber(LoadInst *LI, StoreInst *SI, AliasAnalysis &AA,
- DominatorSet &DomSetInfo) const;
+ virtual void copyValue(Value *From, Value *To) {
+ getAnalysis<AliasAnalysis>().copyValue(From, To);
+ }
+
+ /// getCallEqualNumberNodes - Given a call instruction, find other calls
+ /// that have the same value number.
+ void getCallEqualNumberNodes(CallInst *CI,
+ std::vector<Value*> &RetVals) const;
};
+ char LoadVN::ID = 0;
// 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);
}
-Pass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
+FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
/// getAnalysisUsage - Does not modify anything. It uses Value Numbering and
///
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<DominatorTree>();
+ AU.addRequiredTransitive<TargetData>();
+}
+
+static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
+ Value *Ptr, unsigned Size, AliasAnalysis &AA,
+ std::set<BasicBlock*> &Visited,
+ std::map<BasicBlock*, bool> &TransparentBlocks){
+ // If we have already checked out this path, or if we reached our destination,
+ // 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);
+
+ if (TBI == TransparentBlocks.end() || TBI->first != CurBlock) {
+ // If this basic block can modify the memory location, then the path is not
+ // transparent!
+ if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
+ TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
+ return false;
+ }
+ TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
+ } 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.
+ for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
+ PI != E; ++PI)
+ if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
+ TransparentBlocks))
+ return false;
+ return true;
+}
+
+/// getCallEqualNumberNodes - Given a call instruction, find other calls that
+/// have the same value number.
+void LoadVN::getCallEqualNumberNodes(CallInst *CI,
+ std::vector<Value*> &RetVals) const {
+ Function *CF = CI->getCalledFunction();
+ if (CF == 0) return; // Indirect call.
+ AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+ AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CF, CI);
+ if (MRB != AliasAnalysis::DoesNotAccessMemory &&
+ MRB != AliasAnalysis::OnlyReadsMemory)
+ return; // Nothing we can do for now.
+
+ // Scan all of the arguments of the function, looking for one that is not
+ // global. In particular, we would prefer to have an argument or instruction
+ // operand to chase the def-use chains of.
+ Value *Op = CF;
+ for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
+ if (isa<Argument>(CI->getOperand(i)) ||
+ isa<Instruction>(CI->getOperand(i))) {
+ Op = CI->getOperand(i);
+ break;
+ }
+
+ // Identify all lexically identical calls in this function.
+ std::vector<CallInst*> IdenticalCalls;
+
+ Function *CIFunc = CI->getParent()->getParent();
+ for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
+ ++UI)
+ if (CallInst *C = dyn_cast<CallInst>(*UI))
+ if (C->getNumOperands() == CI->getNumOperands() &&
+ C->getOperand(0) == CI->getOperand(0) &&
+ C->getParent()->getParent() == CIFunc && C != CI) {
+ bool AllOperandsEqual = true;
+ for (unsigned i = 1, e = CI->getNumOperands(); i != e; ++i)
+ if (C->getOperand(i) != CI->getOperand(i)) {
+ AllOperandsEqual = false;
+ break;
+ }
+
+ if (AllOperandsEqual)
+ IdenticalCalls.push_back(C);
+ }
+
+ if (IdenticalCalls.empty()) return;
+
+ // Eliminate duplicates, which could occur if we chose a value that is passed
+ // into a call site multiple times.
+ std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
+ IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
+ IdenticalCalls.end());
+
+ // If the call reads memory, we must make sure that there are no stores
+ // between the calls in question.
+ //
+ // FIXME: This should use mod/ref information. What we really care about it
+ // whether an intervening instruction could modify memory that is read, not
+ // ANY memory.
+ //
+ if (MRB == AliasAnalysis::OnlyReadsMemory) {
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ BasicBlock *CIBB = CI->getParent();
+ for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
+ CallInst *C = IdenticalCalls[i];
+ bool CantEqual = false;
+
+ if (DT.dominates(CIBB, C->getParent())) {
+ // FIXME: we currently only handle the case where both calls are in the
+ // same basic block.
+ if (CIBB != C->getParent()) {
+ CantEqual = true;
+ } else {
+ Instruction *First = CI, *Second = C;
+ if (!DT.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;
+ for (++First; I != BasicBlock::iterator(Second); ++I) {
+ if (isa<StoreInst>(I)) {
+ // FIXME: We could use mod/ref information to make this much
+ // better!
+ CantEqual = true;
+ break;
+ } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
+ if (CI->getCalledFunction() == 0 ||
+ !AA.onlyReadsMemory(CI->getCalledFunction())) {
+ CantEqual = true;
+ break;
+ }
+ } else if (I->mayWriteToMemory()) {
+ CantEqual = true;
+ break;
+ }
+ }
+ }
+
+ } else if (DT.dominates(C->getParent(), CIBB)) {
+ // FIXME: We could implement this, but we don't for now.
+ CantEqual = true;
+ } else {
+ // FIXME: if one doesn't dominate the other, we can't tell yet.
+ CantEqual = true;
+ }
+
+
+ if (CantEqual) {
+ // This call does not produce the same value as the one in the query.
+ std::swap(IdenticalCalls[i--], IdenticalCalls.back());
+ IdenticalCalls.pop_back();
+ }
+ }
+ }
+
+ // Any calls that are identical and not destroyed will produce equal values!
+ for (unsigned i = 0, e = IdenticalCalls.size(); i != e; ++i)
+ RetVals.push_back(IdenticalCalls[i]);
}
// getEqualNumberNodes - Return nodes with the same value number as the
if (isa<PointerType>(V->getType()))
getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals);
- if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
- // Volatile loads cannot be replaced with the value of other loads.
- 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));
-
- Function *F = LI->getParent()->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::vector<LoadInst*> CandidateLoads;
- std::vector<StoreInst*> CandidateStores;
-
- while (!PointerSources.empty()) {
- Value *Source = PointerSources.back();
- PointerSources.pop_back(); // Get a source pointer...
-
- 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.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.push_back(Cand);
- }
- }
+ if (!isa<LoadInst>(V)) {
+ if (CallInst *CI = dyn_cast<CallInst>(V))
+ getCallEqualNumberNodes(CI, RetVals);
- // Remove duplicates from the CandidateLoads list because alias analysis
- // processing may be somewhat expensive and we don't want to do more work
- // than necessary.
- //
- unsigned OldSize = CandidateLoads.size();
- std::sort(CandidateLoads.begin(), CandidateLoads.end());
- CandidateLoads.erase(std::unique(CandidateLoads.begin(),
- CandidateLoads.end()),
- CandidateLoads.end());
- // FIXME: REMOVE THIS SORTING AND UNIQUING IF IT CAN'T HAPPEN
- assert(CandidateLoads.size() == OldSize && "Shrunk the candloads list?");
-
- // Get Alias Analysis...
- AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
- DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
-
- // Loop over all of the candidate loads. If they are not invalidated by
- // stores or calls between execution of them and LI, then add them to
- // RetVals.
- for (unsigned i = 0, e = CandidateLoads.size(); i != e; ++i)
- if (haveEqualValueNumber(LI, CandidateLoads[i], AA, DomSetInfo))
- RetVals.push_back(CandidateLoads[i]);
- for (unsigned i = 0, e = CandidateStores.size(); i != e; ++i)
- if (haveEqualValueNumber(LI, CandidateStores[i], AA, DomSetInfo))
- RetVals.push_back(CandidateStores[i]->getOperand(0));
-
- } else {
+ // Not a load instruction? Just chain to the base value numbering
+ // implementation to satisfy the request...
assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this &&
"getAnalysis() returned this!");
- // Not a load instruction? Just chain to the base value numbering
- // implementation to satisfy the request...
return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
}
-}
-
-// CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
-// (until DestBB) contain an instruction that might invalidate Ptr.
-//
-static bool CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
- Value *Ptr, unsigned Size,
- AliasAnalysis &AA,
- std::set<BasicBlock*> &VisitedSet) {
- // Found the termination point!
- if (BB == DestBB || VisitedSet.count(BB)) return false;
-
- // Avoid infinite recursion!
- VisitedSet.insert(BB);
-
- // Can this basic block modify Ptr?
- if (AA.canBasicBlockModify(*BB, Ptr, Size))
- return true;
-
- // Check all of our predecessor blocks...
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, DestBB, Ptr, Size, AA, VisitedSet))
- return true;
-
- // None of our predecessor blocks contain an invalidating instruction, and we
- // don't either!
- return false;
-}
+ // Volatile loads cannot be replaced with the value of other loads.
+ LoadInst *LI = cast<LoadInst>(V);
+ if (LI->isVolatile())
+ return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
-/// haveEqualValueNumber - Given two load instructions, determine if they both
-/// produce the same value on every execution of the program, assuming that
-/// their source operands always give the same value. This uses the
-/// AliasAnalysis implementation to invalidate loads when stores or function
-/// calls occur that could modify the value produced by the load.
-///
-bool LoadVN::haveEqualValueNumber(LoadInst *L1, LoadInst *L2,
- AliasAnalysis &AA,
- DominatorSet &DomSetInfo) const {
- assert(L1 != L2 && "haveEqualValueNumber assumes differing loads!");
- assert(L1->getType() == L2->getType() &&
- "How could the same source pointer return different types?");
- Value *LoadAddress = L1->getOperand(0);
+ Value *LoadPtr = LI->getOperand(0);
+ BasicBlock *LoadBB = LI->getParent();
+ Function *F = LoadBB->getParent();
// Find out how many bytes of memory are loaded by the load instruction...
- unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(L1->getType());
-
- // If the two loads are in the same basic block, just do a local analysis.
- if (L1->getParent() == L2->getParent()) {
- // It can be _very_ expensive to determine which instruction occurs first in
- // the basic block if the block is large (see PR209). For this reason,
- // instead of figuring out which block is first, then scanning all of the
- // instructions, we scan the instructions both ways from L1 until we find
- // L2. Along the way if we find a potentially modifying instruction, we
- // kill the search. This helps in cases where we have large blocks the have
- // potentially modifying instructions in them which stop the search.
-
- BasicBlock *BB = L1->getParent();
- BasicBlock::iterator UpIt = L1, DownIt = L1; ++DownIt;
- bool NoModifiesUp = true, NoModifiesDown = true;
-
- // Scan up and down looking for L2, a modifying instruction, or the end of a
- // basic block.
- while (UpIt != BB->begin() && DownIt != BB->end()) {
- // Scan up...
- --UpIt;
- if (&*UpIt == L2)
- return NoModifiesUp; // No instructions invalidate the loads!
- if (NoModifiesUp)
- NoModifiesUp &=
- !(AA.getModRefInfo(UpIt, LoadAddress, LoadSize) & AliasAnalysis::Mod);
-
- if (&*DownIt == L2)
- return NoModifiesDown;
- if (NoModifiesDown)
- NoModifiesDown &=
- !(AA.getModRefInfo(DownIt, LoadAddress, LoadSize)
- & AliasAnalysis::Mod);
- ++DownIt;
+ unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
+ 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
+ // we see any candidate load or store instructions, then we know that the
+ // candidates have the same value # as LI.
+ bool LoadInvalidatedInBBBefore = false;
+ for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
+ --I;
+ if (I == LoadPtr) {
+ // If we run into an allocation of the value being loaded, then the
+ // contents are not initialized.
+ if (isa<AllocationInst>(I))
+ RetVals.push_back(UndefValue::get(LI->getType()));
+
+ // 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 we got here, we ran into one end of the basic block or the other.
- if (UpIt != BB->begin()) {
- // If we know that the upward scan found a modifier, return false.
- if (!NoModifiesUp) return false;
+ 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 (StoreInst *SI = dyn_cast<StoreInst>(I))
+ if (SI->getOperand(1) == LoadPtr)
+ RetVals.push_back(I->getOperand(0));
- // Otherwise, continue the scan looking for a modifier or L2.
- for (--UpIt; &*UpIt != L2; --UpIt)
- if (AA.getModRefInfo(UpIt, LoadAddress, LoadSize) & AliasAnalysis::Mod)
- return false;
- return true;
- } else {
- // If we know that the downward scan found a modifier, return false.
- assert(DownIt != BB->end() && "Didn't find instructions??");
- if (!NoModifiesDown) return false;
-
- // Otherwise, continue the scan looking for a modifier or L2.
- for (; &*DownIt != L2; ++DownIt) {
- if (AA.getModRefInfo(DownIt, LoadAddress, LoadSize) &AliasAnalysis::Mod)
- return false;
- }
- return true;
+ LoadInvalidatedInBBBefore = true;
+ break;
}
- } else {
- // Figure out which load dominates the other one. If neither dominates the
- // other we cannot eliminate them.
- //
- // FIXME: This could be enhanced greatly!
- //
- if (DomSetInfo.dominates(L2, L1))
- std::swap(L1, L2); // Make L1 dominate L2
- else if (!DomSetInfo.dominates(L1, L2))
- return false; // Neither instruction dominates the other one...
-
- BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
-
- // L1 now dominates L2. Check to see if the intervening instructions
- // between the two loads might modify the loaded location.
-
- // Make sure that there are no modifying instructions between L1 and the end
- // of its basic block.
- //
- if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress,
- LoadSize))
- return false; // Cannot eliminate load
-
- // Make sure that there are no modifying instructions between the start of
- // BB2 and the second load instruction.
- //
- if (AA.canInstructionRangeModify(BB2->front(), *L2, LoadAddress, LoadSize))
- return false; // Cannot eliminate load
-
- // Do a depth first traversal of the inverse CFG starting at L2's block,
- // looking for L1's block. The inverse CFG is made up of the predecessor
- // nodes of a block... so all of the edges in the graph are "backward".
- //
- std::set<BasicBlock*> VisitedSet;
- for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
- VisitedSet))
- return false;
-
- // If we passed all of these checks then we are sure that the two loads
- // produce the same value.
- return true;
}
-}
-
-/// haveEqualValueNumber - Given a load instruction and a store instruction,
-/// determine if the stored value reaches the loaded value unambiguously on
-/// every execution of the program. This uses the AliasAnalysis implementation
-/// to invalidate the stored value when stores or function calls occur that
-/// could modify the value produced by the load.
-///
-bool LoadVN::haveEqualValueNumber(LoadInst *Load, StoreInst *Store,
- AliasAnalysis &AA,
- DominatorSet &DomSetInfo) const {
- // If the store does not dominate the load, we cannot do anything...
- if (!DomSetInfo.dominates(Store, Load))
- return false;
+ // Figure out if the load is invalidated between the load and the exit of the
+ // block it is defined in. While we are scanning the current basic block, if
+ // we see any candidate loads, then we know they have the same value # as LI.
+ //
+ bool LoadInvalidatedInBBAfter = false;
+ {
+ BasicBlock::iterator I = LI;
+ for (++I; I != LoadBB->end(); ++I) {
+ // If this instruction is a load, then this instruction returns the same
+ // value as LI.
+ if (isa<LoadInst>(I) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
+ RetVals.push_back(I);
+
+ if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
+ LoadInvalidatedInBBAfter = true;
+ break;
+ }
+ }
+ }
- BasicBlock *BB1 = Store->getParent(), *BB2 = Load->getParent();
- Value *LoadAddress = Load->getOperand(0);
+ // 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;
- assert(LoadAddress->getType() == Store->getOperand(1)->getType() &&
- "How could the same source pointer return different types?");
+ // 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());
+ }
- // Find out how many bytes of memory are loaded by the load instruction...
- unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(Load->getType());
+ // Get dominators.
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+
+ // 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
+ // boolean is set to false, if it's not it is set to true. If we don't know
+ // yet, the entry is not in the map.
+ std::map<BasicBlock*, bool> TransparentBlocks;
+
+ // Loop over all of the basic blocks that also load the value. If the value
+ // 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*, unsigned>::iterator
+ I = CandidateLoads.begin(), E = CandidateLoads.end(); I != E; ++I) {
+ bool CantEqual = false;
+
+ // Right now we only can handle cases where one load dominates the other.
+ // FIXME: generalize this!
+ BasicBlock *BB1 = I->first, *BB2 = LoadBB;
+ if (DT.dominates(BB1, BB2)) {
+ // The other load dominates LI. If the loaded value is killed entering
+ // the LoadBB block, we know the load is not live.
+ if (LoadInvalidatedInBBBefore)
+ CantEqual = true;
+ } else if (DT.dominates(BB2, BB1)) {
+ std::swap(BB1, BB2); // Canonicalize
+ // LI dominates the other load. If the loaded value is killed exiting
+ // the LoadBB block, we know the load is not live.
+ if (LoadInvalidatedInBBAfter)
+ CantEqual = true;
+ } else {
+ // None of these loads can VN the same.
+ CantEqual = true;
+ }
- // Compute a basic block iterator pointing to the instruction after the store.
- BasicBlock::iterator StoreIt = Store; ++StoreIt;
+ if (!CantEqual) {
+ // Ok, at this point, we know that BB1 dominates BB2, and that there is
+ // nothing in the LI block that kills the loaded value. Check to see if
+ // the value is live across the CFG.
+ std::set<BasicBlock*> Visited;
+ for (pred_iterator PI = pred_begin(BB2), E = pred_end(BB2); PI!=E; ++PI)
+ if (!isPathTransparentTo(*PI, BB1, LoadPtr, LoadSize, AA,
+ Visited, TransparentBlocks)) {
+ // None of these loads can VN the same.
+ CantEqual = true;
+ break;
+ }
+ }
- // Check to see if the intervening instructions between the two store and load
- // include a store or call...
- //
- if (BB1 == BB2) { // In same basic block?
- // In this degenerate case, no checking of global basic blocks has to occur
- // just check the instructions BETWEEN Store & Load...
- //
- if (AA.canInstructionRangeModify(*StoreIt, *Load, LoadAddress, LoadSize))
- return false; // Cannot eliminate load
-
- // No instructions invalidate the stored value, they produce the same value!
- return true;
- } else {
- // Make sure that there are no store instructions between the Store and the
- // end of its basic block...
- //
- if (AA.canInstructionRangeModify(*StoreIt, *BB1->getTerminator(),
- LoadAddress, LoadSize))
- return false; // Cannot eliminate load
-
- // Make sure that there are no store instructions between the start of BB2
- // and the second load instruction...
- //
- if (AA.canInstructionRangeModify(BB2->front(), *Load, LoadAddress,LoadSize))
- return false; // Cannot eliminate load
-
- // Do a depth first traversal of the inverse CFG starting at L2's block,
- // looking for L1's block. The inverse CFG is made up of the predecessor
- // nodes of a block... so all of the edges in the graph are "backward".
- //
- std::set<BasicBlock*> VisitedSet;
- for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, BB1, LoadAddress, LoadSize, AA,
- VisitedSet))
- return false;
-
- // If we passed all of these checks then we are sure that the two loads
- // produce the same value.
- return true;
+ // If the loads can equal so far, scan the basic block that contains the
+ // loads under consideration to see if they are invalidated in the block.
+ // For any loads that are not invalidated, add them to the equivalence
+ // set!
+ if (!CantEqual) {
+ 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 (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) {
+ // If there is a modifying instruction, nothing below it will value
+ // # the same.
+ break;
+ }
+ }
+ } else {
+ // If the block dominates LI, make sure that the loads in the block are
+ // not invalidated before the block ends.
+ BasicBlock::iterator BBI = I->first->end();
+ while (1) {
+ --BBI;
+ 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
+ // # the same.
+ break;
+ }
+ }
+ }
+ }
}
+
+ // Handle candidate stores. If the loaded location is clobbered on entrance
+ // to the LoadBB, no store outside of the LoadBB can value number equal, so
+ // quick exit.
+ if (LoadInvalidatedInBBBefore)
+ return;
+
+ // 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 (DT.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, StoreBB, LoadPtr, LoadSize, AA,
+ Visited, TransparentBlocks)) {
+ // None of these stores can VN the same.
+ CantEqual = true;
+ break;
+ }
+ Visited.clear();
+ if (!CantEqual) {
+ // Okay, the path from the store block to the load block is clear, and
+ // we know that there are no invalidating instructions from the start
+ // of the load block to the load itself. Now we just scan the store
+ // block.
+
+ BasicBlock::iterator BBI = StoreBB->end();
+ while (1) {
+ 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!");
+ --BBI;
+ if (AA.getModRefInfo(BBI, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
+ // 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 (SI->getOperand(1) == LoadPtr)
+ RetVals.push_back(SI->getOperand(0));
+ break;
+ }
+ }
+ }
+ }
}
projects / oota-llvm.git / blobdiff