diff options
| -rw-r--r-- | include/llvm/Analysis/LoadValueNumbering.h | 35 | ||||
| -rw-r--r-- | include/llvm/Analysis/Passes.h | 7 | ||||
| -rw-r--r-- | include/llvm/Analysis/ValueNumbering.h | 75 | ||||
| -rw-r--r-- | include/llvm/LinkAllPasses.h | 4 | ||||
| -rw-r--r-- | include/llvm/Transforms/Scalar.h | 9 | ||||
| -rw-r--r-- | lib/Analysis/LoadValueNumbering.cpp | 530 | ||||
| -rw-r--r-- | lib/Analysis/ValueNumbering.cpp | 286 | ||||
| -rw-r--r-- | lib/Transforms/Scalar/GCSE.cpp | 205 | ||||
| -rw-r--r-- | tools/llvm-ld/Optimize.cpp | 1 | ||||
| -rw-r--r-- | tools/lto/LTOCodeGenerator.cpp | 1 |
10 files changed, 0 insertions, 1153 deletions
diff --git a/include/llvm/Analysis/LoadValueNumbering.h b/include/llvm/Analysis/LoadValueNumbering.h deleted file mode 100644 index 340a193e0a..0000000000 --- a/include/llvm/Analysis/LoadValueNumbering.h +++ /dev/null @@ -1,35 +0,0 @@ -//===- llvm/Analysis/LoadValueNumbering.h - Value # Load Insts --*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines 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. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LOAD_VALUE_NUMBERING_H -#define LLVM_ANALYSIS_LOAD_VALUE_NUMBERING_H - -namespace llvm { - -class FunctionPass; - -/// createLoadValueNumberingPass - Create and return a new pass that implements -/// the ValueNumbering interface. -/// -FunctionPass *createLoadValueNumberingPass(); - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 7843aea2ae..7995fc8cdc 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -79,13 +79,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createBasicVNPass - This pass walks SSA def-use chains to trivially - // identify lexically identical expressions. - // - ImmutablePass *createBasicVNPass(); - - //===--------------------------------------------------------------------===// - // // createProfileLoaderPass - This pass loads information from a profile dump // file. // diff --git a/include/llvm/Analysis/ValueNumbering.h b/include/llvm/Analysis/ValueNumbering.h deleted file mode 100644 index 72452acda1..0000000000 --- a/include/llvm/Analysis/ValueNumbering.h +++ /dev/null @@ -1,75 +0,0 @@ -//===- llvm/Analysis/ValueNumbering.h - Value #'ing Interface ---*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the abstract ValueNumbering interface, which is used as the -// common interface used by all clients of value numbering information, and -// implemented by all value numbering implementations. -// -// Implementations of this interface must implement the various virtual methods, -// which automatically provides functionality for the entire suite of client -// APIs. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_VALUE_NUMBERING_H -#define LLVM_ANALYSIS_VALUE_NUMBERING_H - -#include <vector> -#include "llvm/Pass.h" -#include "llvm/System/IncludeFile.h" - -namespace llvm { - -class Value; -class Instruction; - -struct ValueNumbering { - static char ID; // Class identification, replacement for typeinfo - virtual ~ValueNumbering(); // We want to be subclassed - - /// 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 = 0; - - ///===-------------------------------------------------------------------===// - /// Interfaces to update value numbering analysis information as the client - /// changes the program. - /// - - /// 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) {} - - /// 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. - /// - virtual void copyValue(Value *From, Value *To) {} - - /// replaceWithNewValue - This method is the obvious combination of the two - /// above, and it provided as a helper to simplify client code. - /// - void replaceWithNewValue(Value *Old, Value *New) { - copyValue(Old, New); - deleteValue(Old); - } -}; - -} // End llvm namespace - -// Force any file including this header to get the implementation as well -FORCE_DEFINING_FILE_TO_BE_LINKED(BasicValueNumbering) - -#endif diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h index 76a4a2f58d..d53e7bea50 100644 --- a/include/llvm/LinkAllPasses.h +++ b/include/llvm/LinkAllPasses.h @@ -18,7 +18,6 @@ #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/FindUsedTypes.h" #include "llvm/Analysis/IntervalPartition.h" -#include "llvm/Analysis/LoadValueNumbering.h" #include "llvm/Analysis/LoopVR.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/PostDominators.h" @@ -50,7 +49,6 @@ namespace { (void) llvm::createStructRetPromotionPass(); (void) llvm::createBasicAliasAnalysisPass(); (void) llvm::createLibCallAliasAnalysisPass(0); - (void) llvm::createBasicVNPass(); (void) llvm::createBlockPlacementPass(); (void) llvm::createBlockProfilerPass(); (void) llvm::createBreakCriticalEdgesPass(); @@ -65,7 +63,6 @@ namespace { (void) llvm::createEdgeProfilerPass(); (void) llvm::createFunctionInliningPass(); (void) llvm::createFunctionProfilerPass(); - (void) llvm::createGCSEPass(); (void) llvm::createGlobalDCEPass(); (void) llvm::createGlobalOptimizerPass(); (void) llvm::createGlobalsModRefPass(); @@ -77,7 +74,6 @@ namespace { (void) llvm::createInternalizePass(false); (void) llvm::createLCSSAPass(); (void) llvm::createLICMPass(); - (void) llvm::createLoadValueNumberingPass(); (void) llvm::createLoopExtractorPass(); (void) llvm::createLoopSimplifyPass(); (void) llvm::createLoopStrengthReducePass(); diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h index d62cdc7a86..b4c3e7caf5 100644 --- a/include/llvm/Transforms/Scalar.h +++ b/include/llvm/Transforms/Scalar.h @@ -78,15 +78,6 @@ FunctionPass *createScalarReplAggregatesPass(signed Threshold = -1); //===----------------------------------------------------------------------===// // -// GCSE - This pass is designed to be a very quick global transformation that -// eliminates global common subexpressions from a function. It does this by -// examining the SSA value graph of the function, instead of doing slow -// bit-vector computations. -// -FunctionPass *createGCSEPass(); - -//===----------------------------------------------------------------------===// -// // InductionVariableSimplify - Transform induction variables in a program to all // use a single canonical induction variable per loop. // diff --git a/lib/Analysis/LoadValueNumbering.cpp b/lib/Analysis/LoadValueNumbering.cpp deleted file mode 100644 index f99ebb4a83..0000000000 --- a/lib/Analysis/LoadValueNumbering.cpp +++ /dev/null @@ -1,530 +0,0 @@ -//===- LoadValueNumbering.cpp - Load Value #'ing Implementation -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// 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 -// 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 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/Support/CFG.h" -#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 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; - - /// 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. - /// - 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... -static RegisterPass<LoadVN> -X("load-vn", "Load Value Numbering", false, true); - -// Declare that we implement the ValueNumbering interface -static RegisterAnalysisGroup<ValueNumbering> Y(X); - -FunctionPass *llvm::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.addRequiredTransitive<AliasAnalysis>(); - AU.addRequired<ValueNumbering>(); - 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.find(CurBlock); - - if (TBI == TransparentBlocks.end()) { - // 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(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 (User::op_iterator i = CI->op_begin() + 1, e = CI->op_end(); i != e; ++i) - if (isa<Argument>(*i) || - isa<Instruction>(*i)) { - Op = *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 (User::op_iterator i = CI->op_begin() + 1, j = C->op_begin() + 1, - e = CI->op_end(); i != e; ++i, ++j) - if (*j != *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 (!AA.onlyReadsMemory(CI)) { - 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 -// specified Value. This fills in the argument vector with any equal values. -// -void LoadVN::getEqualNumberNodes(Value *V, - std::vector<Value*> &RetVals) const { - // If the alias analysis has any must alias information to share with us, we - // can definitely use it. - if (isa<PointerType>(V->getType())) - getAnalysis<AliasAnalysis>().getMustAliases(V, RetVals); - - if (!isa<LoadInst>(V)) { - if (CallInst *CI = dyn_cast<CallInst>(V)) - getCallEqualNumberNodes(CI, RetVals); - - // Not a load instruction? Just chain to the base value numbering - // implementation to satisfy the request... - assert(&getAnalysis<ValueNumbering>() != (ValueNumbering*)this && - "getAnalysis() returned this!"); - - return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals); - } - - // 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); - - 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>().getTypeStoreSize(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 (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)); - - LoadInvalidatedInBBBefore = true; - break; - } - } - - // 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; - } - } - } - - // 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. - 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; - } - - 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; - } - } - - // 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; - } - } - } - } -} diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp deleted file mode 100644 index 55323eaa9e..0000000000 --- a/lib/Analysis/ValueNumbering.cpp +++ /dev/null @@ -1,286 +0,0 @@ -//===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements the non-abstract Value Numbering methods as well as a -// default implementation for the analysis group. -// -// The ValueNumbering analysis pass is mostly deprecated. It is only used by the -// Global Common Subexpression Elimination pass, which is deprecated by the -// Global Value Numbering pass (which does its value numbering on its own). -// -//===----------------------------------------------------------------------===// - -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/ValueNumbering.h" -#include "llvm/Support/InstVisitor.h" -#include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Type.h" -#include "llvm/Support/Compiler.h" -using namespace llvm; - -char ValueNumbering::ID = 0; -// Register the ValueNumbering interface, providing a nice name to refer to. -static RegisterAnalysisGroup<ValueNumbering> V("Value Numbering"); - -/// ValueNumbering destructor: DO NOT move this to the header file for -/// ValueNumbering or else clients of the ValueNumbering class may not depend on -/// the ValueNumbering.o file in the current .a file, causing alias analysis -/// support to not be included in the tool correctly! -/// -ValueNumbering::~ValueNumbering() {} - -//===----------------------------------------------------------------------===// -// Basic ValueNumbering Pass Implementation -//===----------------------------------------------------------------------===// -// -// Because of the way .a files work, the implementation of the BasicVN class -// MUST be in the ValueNumbering file itself, or else we run the risk of -// ValueNumbering being used, but the default implementation not being linked -// into the tool that uses it. As such, we register and implement the class -// here. -// - -namespace { - /// BasicVN - This class is the default implementation of the ValueNumbering - /// interface. It walks the SSA def-use chains to trivially identify - /// lexically identical expressions. This does not require any ahead of time - /// analysis, so it is a very fast default implementation. - /// - struct VISIBILITY_HIDDEN BasicVN - : public ImmutablePass, public ValueNumbering { - static char ID; // Class identification, replacement for typeinfo - BasicVN() : ImmutablePass((intptr_t)&ID) {} - - /// getEqualNumberNodes - Return nodes with the same value number as the - /// specified Value. This fills in the argument vector with any equal - /// values. - /// - /// This is where our implementation is. - /// - virtual void getEqualNumberNodes(Value *V1, - std::vector<Value*> &RetVals) const; - }; -} - -char BasicVN::ID = 0; -// Register this pass... -static RegisterPass<BasicVN> -X("basicvn", "Basic Value Numbering (default GVN impl)", false, true); - -// Declare that we implement the ValueNumbering interface -static RegisterAnalysisGroup<ValueNumbering, true> Y(X); - -namespace { - /// BVNImpl - Implement BasicVN in terms of a visitor class that - /// handles the different types of instructions as appropriate. - /// - struct VISIBILITY_HIDDEN BVNImpl : public InstVisitor<BVNImpl> { - std::vector<Value*> &RetVals; - explicit BVNImpl(std::vector<Value*> &RV) : RetVals(RV) {} - - void visitCastInst(CastInst &I); - void visitGetElementPtrInst(GetElementPtrInst &I); - void visitCmpInst(CmpInst &I); - - void handleBinaryInst(Instruction &I); - void visitBinaryOperator(Instruction &I) { handleBinaryInst(I); } - void visitShiftInst(Instruction &I) { handleBinaryInst(I); } - void visitExtractElementInst(Instruction &I) { handleBinaryInst(I); } - - void handleTernaryInst(Instruction &I); - void visitSelectInst(Instruction &I) { handleTernaryInst(I); } - void visitInsertElementInst(Instruction &I) { handleTernaryInst(I); } - void visitShuffleVectorInst(Instruction &I) { handleTernaryInst(I); } - void visitInstruction(Instruction &) { - // Cannot value number calls or terminator instructions. - } - }; -} - -ImmutablePass *llvm::createBasicVNPass() { return new BasicVN(); } - -// getEqualNumberNodes - Return nodes with the same value number as the -// specified Value. This fills in the argument vector with any equal values. -// -void BasicVN::getEqualNumberNodes(Value *V, std::vector<Value*> &RetVals) const{ - assert(V->getType() != Type::VoidTy && - "Can only value number non-void values!"); - // We can only handle the case where I is an instruction! - if (Instruction *I = dyn_cast<Instruction>(V)) - BVNImpl(RetVals).visit(I); -} - -void BVNImpl::visitCastInst(CastInst &CI) { - Instruction &I = (Instruction&)CI; - Value *Op = I.getOperand(0); - Function *F = I.getParent()->getParent(); - - for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); - UI != UE; ++UI) - if (CastInst *Other = dyn_cast<CastInst>(*UI)) - // Check that the opcode is the same - if (Other->getOpcode() == Instruction::CastOps(I.getOpcode()) && - // Check that the destination types are the same - Other->getType() == I.getType() && - // Is it embedded in the same function? (This could be false if LHS - // is a constant or global!) - Other->getParent()->getParent() == F && - // Check to see if this new cast is not I. - Other != &I) { - // These instructions are identical. Add to list... - RetVals.push_back(Other); - } -} - -void BVNImpl::visitCmpInst(CmpInst &CI1) { - Value *LHS = CI1.getOperand(0); - for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); - UI != UE; ++UI) - if (CmpInst *CI2 = dyn_cast<CmpInst>(*UI)) - // Check to see if this compare instruction is not CI, but same opcode, - // same predicate, and in the same function. - if (CI2 != &CI1 && CI2->getOpcode() == CI1.getOpcode() && - CI2->getPredicate() == CI1.getPredicate() && - CI2->getParent()->getParent() == CI1.getParent()->getParent()) - // If the operands are the same - if ((CI2->getOperand(0) == CI1.getOperand(0) && - CI2->getOperand(1) == CI1.getOperand(1)) || - // Or the compare is commutative and the operands are reversed - (CI1.isCommutative() && - CI2->getOperand(0) == CI1.getOperand(1) && - CI2->getOperand(1) == CI1.getOperand(0))) - // Then the instructiosn are identical, add to list. - RetVals.push_back(CI2); -} - - - -// isIdenticalBinaryInst - Return true if the two binary instructions are -// identical. -// -static inline bool isIdenticalBinaryInst(const Instruction &I1, - const Instruction *I2) { - // Is it embedded in the same function? (This could be false if LHS - // is a constant or global!) - if (I1.getOpcode() != I2->getOpcode() || - I1.getParent()->getParent() != I2->getParent()->getParent()) - return false; - - // If they are CmpInst instructions, check their predicates - if (CmpInst *CI1 = dyn_cast<CmpInst>(&const_cast<Instruction&>(I1))) - if (CI1->getPredicate() != cast<CmpInst>(I2)->getPredicate()) - return false; - - // They are identical if both operands are the same! - if (I1.getOperand(0) == I2->getOperand(0) && - I1.getOperand(1) == I2->getOperand(1)) - return true; - - // If the instruction is commutative, the instruction can match if the - // operands are swapped! - // - if ((I1.getOperand(0) == I2->getOperand(1) && - I1.getOperand(1) == I2->getOperand(0)) && - I1.isCommutative()) - return true; - - return false; -} - -// isIdenticalTernaryInst - Return true if the two ternary instructions are -// identical. -// -static inline bool isIdenticalTernaryInst(const Instruction &I1, - const Instruction *I2) { - // Is it embedded in the same function? (This could be false if LHS - // is a constant or global!) - if (I1.getParent()->getParent() != I2->getParent()->getParent()) - return false; - - // They are identical if all operands are the same! - return I1.getOperand(0) == I2->getOperand(0) && - I1.getOperand(1) == I2->getOperand(1) && - I1.getOperand(2) == I2->getOperand(2); -} - - - -void BVNImpl::handleBinaryInst(Instruction &I) { - Value *LHS = I.getOperand(0); - - for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end(); - UI != UE; ++UI) - if (Instruction *Other = dyn_cast<Instruction>(*UI)) - // Check to see if this new binary operator is not I, but same operand... - if (Other != &I && isIdenticalBinaryInst(I, Other)) { - // These instructions are identical. Handle the situation. - RetVals.push_back(Other); - } -} - -// IdenticalComplexInst - Return true if the two instructions are the same, by -// using a brute force comparison. This is useful for instructions with an -// arbitrary number of arguments. -// -static inline bool IdenticalComplexInst(const Instruction *I1, - const Instruction *I2) { - assert(I1->getOpcode() == I2->getOpcode()); - // Equal if they are in the same function... - return I1->getParent()->getParent() == I2->getParent()->getParent() && - // And return the same type... - I1->getType() == I2->getType() && - // And have the same number of operands... - I1->getNumOperands() == I2->getNumOperands() && - // And all of the operands are equal. - std::equal(I1->op_begin(), I1->op_end(), I2->op_begin()); -} - -void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) { - Value *Op = I.getOperand(0); - - // Try to pick a local operand if possible instead of a constant or a global - // that might have a lot of uses. - for (User::op_iterator i = I.op_begin() + 1, e = I.op_end(); i != e; ++i) - if (isa<Instruction>(*i) || isa<Argument>(*i)) { - Op = *i; - break; - } - - for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end(); - UI != UE; ++UI) - if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI)) - // Check to see if this new getelementptr is not I, but same operand... - if (Other != &I && IdenticalComplexInst(&I, Other)) { - // These instructions are identical. Handle the situation. - RetVals.push_back(Other); - } -} - -void BVNImpl::handleTernaryInst(Instruction &I) { - Value *Op0 = I.getOperand(0); - Instruction *OtherInst; - - for (Value::use_iterator UI = Op0->use_begin(), UE = Op0->use_end(); - UI != UE; ++UI) - if ((OtherInst = dyn_cast<Instruction>(*UI)) && - OtherInst->getOpcode() == I.getOpcode()) { - // Check to see if this new select is not I, but has the same operands. - if (OtherInst != &I && isIdenticalTernaryInst(I, OtherInst)) { - // These instructions are identical. Handle the situation. - RetVals.push_back(OtherInst); - } - - } -} - - -// Ensure that users of ValueNumbering.h will link with this file -DEFINING_FILE_FOR(BasicValueNumbering) diff --git a/lib/Transforms/Scalar/GCSE.cpp b/lib/Transforms/Scalar/GCSE.cpp deleted file mode 100644 index 9d3f1a8750..0000000000 --- a/lib/Transforms/Scalar/GCSE.cpp +++ /dev/null @@ -1,205 +0,0 @@ -//===-- GCSE.cpp - SSA-based Global Common Subexpression Elimination ------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass is designed to be a very quick global transformation that -// eliminates global common subexpressions from a function. It does this by -// using an existing value numbering analysis pass to identify the common -// subexpressions, eliminating them when possible. -// -// This pass is deprecated by the Global Value Numbering pass (which does a -// better job with its own value numbering). -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "gcse" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Type.h" -#include "llvm/Analysis/ConstantFolding.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/ValueNumbering.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/Support/Compiler.h" -#include <algorithm> -using namespace llvm; - -STATISTIC(NumInstRemoved, "Number of instructions removed"); -STATISTIC(NumLoadRemoved, "Number of loads removed"); -STATISTIC(NumCallRemoved, "Number of calls removed"); -STATISTIC(NumNonInsts , "Number of instructions removed due " - "to non-instruction values"); -STATISTIC(NumArgsRepl , "Number of function arguments replaced " - "with constant values"); -namespace { - struct VISIBILITY_HIDDEN GCSE : public FunctionPass { - static char ID; // Pass identification, replacement for typeid - GCSE() : FunctionPass((intptr_t)&ID) {} - - virtual bool runOnFunction(Function &F); - - private: - void ReplaceInstructionWith(Instruction *I, Value *V); - - // This transformation requires dominator and immediate dominator info - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesCFG(); - AU.addRequired<DominatorTree>(); - AU.addRequired<ValueNumbering>(); - } - }; -} - -char GCSE::ID = 0; -static RegisterPass<GCSE> -X("gcse", "Global Common Subexpression Elimination"); - -// createGCSEPass - The public interface to this file... -FunctionPass *llvm::createGCSEPass() { return new GCSE(); } - -// GCSE::runOnFunction - This is the main transformation entry point for a -// function. -// -bool GCSE::runOnFunction(Function &F) { - bool Changed = false; - - // Get pointers to the analysis results that we will be using... - DominatorTree &DT = getAnalysis<DominatorTree>(); - ValueNumbering &VN = getAnalysis<ValueNumbering>(); - - std::vector<Value*> EqualValues; - - // Check for value numbers of arguments. If the value numbering - // implementation can prove that an incoming argument is a constant or global - // value address, substitute it, making the argument dead. - for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); AI != E;++AI) - if (!AI->use_empty()) { - VN.getEqualNumberNodes(AI, EqualValues); - if (!EqualValues.empty()) { - for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) - if (isa<Constant>(EqualValues[i])) { - AI->replaceAllUsesWith(EqualValues[i]); - ++NumArgsRepl; - Changed = true; - break; - } - EqualValues.clear(); - } - } - - // Traverse the CFG of the function in dominator order, so that we see each - // instruction after we see its operands. - for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()), - E = df_end(DT.getRootNode()); DI != E; ++DI) { - BasicBlock *BB = DI->getBlock(); - - // Remember which instructions we've seen in this basic block as we scan. - std::set<Instruction*> BlockInsts; - - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { - Instruction *Inst = I++; - - if (Constant *C = ConstantFoldInstruction(Inst)) { - ReplaceInstructionWith(Inst, C); - } else if (Inst->getType() != Type::VoidTy) { - // If this instruction computes a value, try to fold together common - // instructions that compute it. - // - VN.getEqualNumberNodes(Inst, EqualValues); - - // If this instruction computes a value that is already computed - // elsewhere, try to recycle the old value. - if (!EqualValues.empty()) { - if (Inst == &*BB->begin()) - I = BB->end(); - else { - I = Inst; --I; - } - - // First check to see if we were able to value number this instruction - // to a non-instruction value. If so, prefer that value over other - // instructions which may compute the same thing. - for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) - if (!isa<Instruction>(EqualValues[i])) { - ++NumNonInsts; // Keep track of # of insts repl with values - - // Change all users of Inst to use the replacement and remove it - // from the program. - ReplaceInstructionWith(Inst, EqualValues[i]); - Inst = 0; - EqualValues.clear(); // don't enter the next loop - break; - } - - // If there were no non-instruction values that this instruction - // produces, find a dominating instruction that produces the same - // value. If we find one, use it's value instead of ours. - for (unsigned i = 0, e = EqualValues.size(); i != e; ++i) { - Instruction *OtherI = cast<Instruction>(EqualValues[i]); - bool Dominates = false; - if (OtherI->getParent() == BB) - Dominates = BlockInsts.count(OtherI); - else - Dominates = DT.dominates(OtherI->getParent(), BB); - - if (Dominates) { - // Okay, we found an instruction with the same value as this one - // and that dominates this one. Replace this instruction with the - // specified one. - ReplaceInstructionWith(Inst, OtherI); - Inst = 0; - break; - } - } - - EqualValues.clear(); - - if (Inst) { - I = Inst; ++I; // Deleted no instructions - } else if (I == BB->end()) { // Deleted first instruction - I = BB->begin(); - } else { // Deleted inst in middle of block. - ++I; - } - } - - if (Inst) - BlockInsts.insert(Inst); - } - } - } - - // When the worklist is empty, return whether or not we changed anything... - return Changed; -} - - -void GCSE::ReplaceInstructionWith(Instruction *I, Value *V) { - if (isa<LoadInst>(I)) - ++NumLoadRemoved; // Keep track of loads eliminated - if (isa<CallInst>(I)) - ++NumCallRemoved; // Keep track of calls eliminated - ++NumInstRemoved; // Keep track of number of insts eliminated - - // Update value numbering - getAnalysis<ValueNumbering>().deleteValue(I); - - I->replaceAllUsesWith(V); - - if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { - // Removing an invoke instruction requires adding a branch to the normal - // destination and removing PHI node entries in the exception destination. - BranchInst::Create(II->getNormalDest(), II); - II->getUnwindDest()->removePredecessor(II->getParent()); - } - - // Erase the instruction from the program. - I->eraseFromParent(); -} diff --git a/tools/llvm-ld/Optimize.cpp b/tools/llvm-ld/Optimize.cpp index 0cbd29ccb3..af95939776 100644 --- a/tools/llvm-ld/Optimize.cpp +++ b/tools/llvm-ld/Optimize.cpp @@ -13,7 +13,6 @@ #include "llvm/Module.h" #include "llvm/PassManager.h" -#include "llvm/Analysis/LoadValueNumbering.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/Verifier.h" diff --git a/tools/lto/LTOCodeGenerator.cpp b/tools/lto/LTOCodeGenerator.cpp index e60dc171bb..ad3964d3f7 100644 --- a/tools/lto/LTOCodeGenerator.cpp +++ b/tools/lto/LTOCodeGenerator.cpp @@ -31,7 +31,6 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/Verifier.h" -#include "llvm/Analysis/LoadValueNumbering.h" #include "llvm/CodeGen/FileWriters.h" #include "llvm/Target/SubtargetFeature.h" #include "llvm/Target/TargetOptions.h" |