diff options
| -rw-r--r-- | lib/Analysis/LoadValueNumbering.cpp | 233 |
1 files changed, 233 insertions, 0 deletions
diff --git a/lib/Analysis/LoadValueNumbering.cpp b/lib/Analysis/LoadValueNumbering.cpp new file mode 100644 index 0000000..154621e --- /dev/null +++ b/lib/Analysis/LoadValueNumbering.cpp @@ -0,0 +1,233 @@ +//===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===// +// +// 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 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. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoadValueNumbering.h" +#include "llvm/Analysis/ValueNumbering.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Pass.h" +#include "llvm/iMemory.h" +#include "llvm/BasicBlock.h" +#include "llvm/Support/CFG.h" +#include <algorithm> +#include <set> + +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 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. + /// + bool haveEqualValueNumber(LoadInst *LI, LoadInst *LI2, AliasAnalysis &AA, + DominatorSet &DomSetInfo) const; + }; + + // Register this pass... + RegisterOpt<LoadVN> X("load-vn", "Load Value Numbering"); + + // Declare that we implement the ValueNumbering interface + RegisterAnalysisGroup<ValueNumbering, LoadVN> Y; +} + + + +Pass *createLoadValueNumberingPass() { return new LoadVN(); } + + +/// getAnalysisUsage - Does not modify anything. It uses Value Numbering and +/// Alias Analysis. +/// +void LoadVN::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<AliasAnalysis>(); + AU.addRequired<ValueNumbering>(); + AU.addRequired<DominatorSet>(); +} + +// getEqualNumberNodes - Return nodes with the same value number as the +// specified Value. This fills in the argument vector with any equal values. +// +void LoadVN::getEqualNumberNodes(Value *V, + std::vector<Value*> &RetVals) const { + + if (LoadInst *LI = dyn_cast<LoadInst>(V)) { + // If we have a load instruction find all of the load 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 candiates that are + // identical. + // + std::vector<LoadInst*> CandidateLoads; + 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) // Not LI itself? + CandidateLoads.push_back(Cand); // Got one... + } + + // Remove duplicates from the CandidateLoads list because alias analysis + // processing may be somewhat expensive and we don't want to do more work + // than neccesary. + // + std::sort(CandidateLoads.begin(), CandidateLoads.end()); + CandidateLoads.erase(std::unique(CandidateLoads.begin(), + CandidateLoads.end()), + CandidateLoads.end()); + + // Get Alias Analysis... + AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); + DominatorSet &DomSetInfo = getAnalysis<DominatorSet>(); + + // Loop over all of the candindate 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]); + + } else { + // Make sure passmanager doesn't try to fulfill our request with ourself! + 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, 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)) + 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, AA, VisitedSet)) + return true; + + // None of our predecessor blocks contain an invalidating instruction, and we + // don't either! + return false; +} + + +/// 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 { + // Figure out which load dominates the other one. If neither dominates the + // other we cannot eliminate them. + // + // FIXME: This could be enhanced to some cases with a shared dominator! + // + 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(); + Value *LoadAddress = L1->getOperand(0); + + // L1 now dominates L2. Check to see if the intervening instructions between + // the two loads 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 L1 & L2... + // + if (AA.canInstructionRangeModify(*L1, *L2, LoadAddress)) + return false; // Cannot eliminate load + + // No instructions invalidate the loads, they produce the same value! + return true; + } else { + // Make sure that there are no store instructions between L1 and the end of + // it's basic block... + // + if (AA.canInstructionRangeModify(*L1, *BB1->getTerminator(), LoadAddress)) + 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(), *L2, LoadAddress)) + 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, 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; + } +} |