//===- 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 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
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/CFG.h"
+#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetData.h"
#include <set>
#include <algorithm>
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 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
void getCallEqualNumberNodes(CallInst *CI,
std::vector<Value*> &RetVals) const;
};
+}
- // Register this pass...
- RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering");
+char LoadVN::ID = 0;
+// Register this pass...
+static RegisterPass<LoadVN>
+X("load-vn", "Load Value Numbering", false, true);
- // Declare that we implement the ValueNumbering interface
- RegisterAnalysisGroup<ValueNumbering, LoadVN> Y;
-}
+// Declare that we implement the ValueNumbering interface
+static RegisterAnalysisGroup<ValueNumbering> Y(X);
FunctionPass *llvm::createLoadValueNumberingPass() { return new LoadVN(); }
///
void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
- AU.addRequired<AliasAnalysis>();
+ AU.addRequiredTransitive<AliasAnalysis>();
AU.addRequired<ValueNumbering>();
- AU.addRequired<DominatorSet>();
- AU.addRequired<TargetData>();
+ AU.addRequiredTransitive<DominatorTree>();
+ 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.
Function *CF = CI->getCalledFunction();
if (CF == 0) return; // Indirect call.
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
- AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CF, CI);
+ AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CI);
if (MRB != AliasAnalysis::DoesNotAccessMemory &&
MRB != AliasAnalysis::OnlyReadsMemory)
return; // Nothing we can do for now.
if (AllOperandsEqual)
IdenticalCalls.push_back(C);
}
-
+
if (IdenticalCalls.empty()) return;
// Eliminate duplicates, which could occur if we chose a value that is passed
// ANY memory.
//
if (MRB == AliasAnalysis::OnlyReadsMemory) {
- DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
+ DominatorTree &DT = getAnalysis<DominatorTree>();
BasicBlock *CIBB = CI->getParent();
for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
CallInst *C = IdenticalCalls[i];
bool CantEqual = false;
- if (DomSetInfo.dominates(CIBB, C->getParent())) {
+ 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 (!DomSetInfo.dominates(CI, 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;
CantEqual = true;
break;
} else if (CallInst *CI = dyn_cast<CallInst>(I)) {
- if (CI->getCalledFunction() == 0 ||
- !AA.onlyReadsMemory(CI->getCalledFunction())) {
+ if (!AA.onlyReadsMemory(CI)) {
CantEqual = true;
break;
}
}
}
- } else if (DomSetInfo.dominates(C->getParent(), CIBB)) {
+ } else if (DT.dominates(C->getParent(), CIBB)) {
// FIXME: We could implement this, but we don't for now.
CantEqual = true;
} else {
LoadInst *LI = cast<LoadInst>(V);
if (LI->isVolatile())
return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
-
+
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(LI->getType());
+ unsigned LoadSize = getAnalysis<TargetData>().getTypeStoreSize(LI->getType());
AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
// Figure out if the load is invalidated from the entry of the block it is in
// we see any candidate loads, then we know they have the same value # as LI.
//
bool LoadInvalidatedInBBAfter = false;
- 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) && cast<LoadInst>(I)->getOperand(0) == LoadPtr)
- RetVals.push_back(I);
+ {
+ 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;
+ if (AA.getModRefInfo(I, LoadPtr, LoadSize) & AliasAnalysis::Mod) {
+ LoadInvalidatedInBBAfter = true;
+ break;
+ }
}
}
// 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?
}
// Get dominators.
- DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
+ 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
// Right now we only can handle cases where one load dominates the other.
// FIXME: generalize this!
BasicBlock *BB1 = I->first, *BB2 = LoadBB;
- if (DomSetInfo.dominates(BB1, BB2)) {
+ 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 (DomSetInfo.dominates(BB2, BB1)) {
+ } 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.
// 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)) {
+ if (DT.dominates(*I, LoadBB)) {
BasicBlock *StoreBB = *I;
// Check to see if the path from the store to the load is transparent