From 89c45a162fe0cfd1fc4f9e246e89b11578552bf9 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Fri, 11 Mar 2016 08:50:55 +0000 Subject: [PATCH] [PM] Port GVN to the new pass manager, wire it up, and teach a couple of tests to run GVN in both modes. This is mostly the boring refactoring just like SROA and other complex transformation passes. There is some trickiness in that GVN's ValueNumber class requires hand holding to get to compile cleanly. I'm open to suggestions about a better pattern there, but I tried several before settling on this. I was trying to balance my desire to sink as much implementation detail into the source file as possible without introducing overly many layers of abstraction. Much like with SROA, the design of this system is made somewhat more cumbersome by the need to support both pass managers without duplicating the significant state and logic of the pass. The same compromise is struck here. I've also left a FIXME in a doxygen comment as the GVN pass seems to have pretty woeful documentation within it. I'd like to submit this with the FIXME and let those more deeply familiar backfill the information here now that we have a nice place in an interface to put that kind of documentaiton. Differential Revision: http://reviews.llvm.org/D18019 llvm-svn: 263208 --- llvm/include/llvm/InitializePasses.h | 2 +- llvm/include/llvm/LinkAllPasses.h | 1 + llvm/include/llvm/Transforms/Scalar.h | 7 - llvm/include/llvm/Transforms/Scalar/GVN.h | 232 +++++++++++ llvm/lib/LTO/LTOCodeGenerator.cpp | 2 +- llvm/lib/Passes/PassBuilder.cpp | 1 + llvm/lib/Passes/PassRegistry.def | 1 + llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp | 1 + llvm/lib/Transforms/IPO/PassManagerBuilder.cpp | 1 + llvm/lib/Transforms/Scalar/GVN.cpp | 554 +++++++++---------------- llvm/lib/Transforms/Scalar/Scalar.cpp | 3 +- llvm/test/Transforms/GVN/basic.ll | 1 + llvm/test/Transforms/GVN/pre-gep-load.ll | 2 + 13 files changed, 449 insertions(+), 359 deletions(-) create mode 100644 llvm/include/llvm/Transforms/Scalar/GVN.h diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index abfbf41..16f978a 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -138,7 +138,7 @@ void initializeExpandISelPseudosPass(PassRegistry&); void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&); void initializeGCMachineCodeAnalysisPass(PassRegistry&); void initializeGCModuleInfoPass(PassRegistry&); -void initializeGVNPass(PassRegistry&); +void initializeGVNLegacyPassPass(PassRegistry&); void initializeGlobalDCEPass(PassRegistry&); void initializeGlobalOptPass(PassRegistry&); void initializeGlobalsAAWrapperPassPass(PassRegistry&); diff --git a/llvm/include/llvm/LinkAllPasses.h b/llvm/include/llvm/LinkAllPasses.h index 84f1869..158b2d0 100644 --- a/llvm/include/llvm/LinkAllPasses.h +++ b/llvm/include/llvm/LinkAllPasses.h @@ -42,6 +42,7 @@ #include "llvm/Transforms/Instrumentation.h" #include "llvm/Transforms/ObjCARC.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Utils/SymbolRewriter.h" #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h" #include "llvm/Transforms/Vectorize.h" diff --git a/llvm/include/llvm/Transforms/Scalar.h b/llvm/include/llvm/Transforms/Scalar.h index 41884f6..6117c05 100644 --- a/llvm/include/llvm/Transforms/Scalar.h +++ b/llvm/include/llvm/Transforms/Scalar.h @@ -335,13 +335,6 @@ FunctionPass *createMergedLoadStoreMotionPass(); //===----------------------------------------------------------------------===// // -// GVN - This pass performs global value numbering and redundant load -// elimination cotemporaneously. -// -FunctionPass *createGVNPass(bool NoLoads = false); - -//===----------------------------------------------------------------------===// -// // MemCpyOpt - This pass performs optimizations related to eliminating memcpy // calls and/or combining multiple stores into memset's. // diff --git a/llvm/include/llvm/Transforms/Scalar/GVN.h b/llvm/include/llvm/Transforms/Scalar/GVN.h new file mode 100644 index 0000000..c6b86bf --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/GVN.h @@ -0,0 +1,232 @@ +//===- GVN.h - Eliminate redundant values and loads -------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides the interface for LLVM's Global Value Numbering pass +/// which eliminates fully redundant instructions. It also does somewhat Ad-Hoc +/// PRE and dead load elimination. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_GVN_H +#define LLVM_TRANSFORMS_SCALAR_GVN_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by GVN. These +/// are implementation details and should not be used by clients. +namespace gvn LLVM_LIBRARY_VISIBILITY { +struct AvailableValue; +struct AvailableValueInBlock; +struct Expression; +class GVNLegacyPass; +} + +/// The core GVN pass object. +/// +/// FIXME: We should have a good summary of the GVN algorithm implemented by +/// this particular pass here. +class GVN : public PassBase { +public: + + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager *AM); + + /// This removes the specified instruction from + /// our various maps and marks it for deletion. + void markInstructionForDeletion(Instruction *I) { + VN.erase(I); + InstrsToErase.push_back(I); + } + + DominatorTree &getDominatorTree() const { return *DT; } + AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } + MemoryDependenceResults &getMemDep() const { return *MD; } + +private: + friend class gvn::GVNLegacyPass; + + /// This class holds the mapping between values and value numbers. It is used + /// as an efficient mechanism to determine the expression-wise equivalence of + /// two values. + class ValueTable { + DenseMap valueNumbering; + DenseMap expressionNumbering; + AliasAnalysis *AA; + MemoryDependenceResults *MD; + DominatorTree *DT; + + uint32_t nextValueNumber; + + gvn::Expression create_expression(Instruction *I); + gvn::Expression create_cmp_expression(unsigned Opcode, + CmpInst::Predicate Predicate, + Value *LHS, Value *RHS); + gvn::Expression create_extractvalue_expression(ExtractValueInst *EI); + uint32_t lookup_or_add_call(CallInst *C); + + public: + ValueTable(); + ValueTable(const ValueTable &Arg); + ValueTable(ValueTable &&Arg); + ~ValueTable(); + + uint32_t lookup_or_add(Value *V); + uint32_t lookup(Value *V) const; + uint32_t lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Pred, + Value *LHS, Value *RHS); + bool exists(Value *V) const; + void add(Value *V, uint32_t num); + void clear(); + void erase(Value *v); + void setAliasAnalysis(AliasAnalysis *A) { AA = A; } + AliasAnalysis *getAliasAnalysis() const { return AA; } + void setMemDep(MemoryDependenceResults *M) { MD = M; } + void setDomTree(DominatorTree *D) { DT = D; } + uint32_t getNextUnusedValueNumber() { return nextValueNumber; } + void verifyRemoved(const Value *) const; + }; + + MemoryDependenceResults *MD; + DominatorTree *DT; + const TargetLibraryInfo *TLI; + AssumptionCache *AC; + SetVector DeadBlocks; + + ValueTable VN; + + /// A mapping from value numbers to lists of Value*'s that + /// have that value number. Use findLeader to query it. + struct LeaderTableEntry { + Value *Val; + const BasicBlock *BB; + LeaderTableEntry *Next; + }; + DenseMap LeaderTable; + BumpPtrAllocator TableAllocator; + + // Block-local map of equivalent values to their leader, does not + // propagate to any successors. Entries added mid-block are applied + // to the remaining instructions in the block. + SmallMapVector ReplaceWithConstMap; + SmallVector InstrsToErase; + + typedef SmallVector LoadDepVect; + typedef SmallVector AvailValInBlkVect; + typedef SmallVector UnavailBlkVect; + + bool runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD); + + /// Push a new Value to the LeaderTable onto the list for its value number. + void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { + LeaderTableEntry &Curr = LeaderTable[N]; + if (!Curr.Val) { + Curr.Val = V; + Curr.BB = BB; + return; + } + + LeaderTableEntry *Node = TableAllocator.Allocate(); + Node->Val = V; + Node->BB = BB; + Node->Next = Curr.Next; + Curr.Next = Node; + } + + /// Scan the list of values corresponding to a given + /// value number, and remove the given instruction if encountered. + void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { + LeaderTableEntry *Prev = nullptr; + LeaderTableEntry *Curr = &LeaderTable[N]; + + while (Curr && (Curr->Val != I || Curr->BB != BB)) { + Prev = Curr; + Curr = Curr->Next; + } + + if (!Curr) + return; + + if (Prev) { + Prev->Next = Curr->Next; + } else { + if (!Curr->Next) { + Curr->Val = nullptr; + Curr->BB = nullptr; + } else { + LeaderTableEntry *Next = Curr->Next; + Curr->Val = Next->Val; + Curr->BB = Next->BB; + Curr->Next = Next->Next; + } + } + } + + // List of critical edges to be split between iterations. + SmallVector, 4> toSplit; + + // Helper functions of redundant load elimination + bool processLoad(LoadInst *L); + bool processNonLocalLoad(LoadInst *L); + bool processAssumeIntrinsic(IntrinsicInst *II); + /// Given a local dependency (Def or Clobber) determine if a value is + /// available for the load. Returns true if an value is known to be + /// available and populates Res. Returns false otherwise. + bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, + Value *Address, gvn::AvailableValue &Res); + /// Given a list of non-local dependencies, determine if a value is + /// available for the load in each specified block. If it is, add it to + /// ValuesPerBlock. If not, add it to UnavailableBlocks. + void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, + AvailValInBlkVect &ValuesPerBlock, + UnavailBlkVect &UnavailableBlocks); + bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, + UnavailBlkVect &UnavailableBlocks); + + // Other helper routines + bool processInstruction(Instruction *I); + bool processBlock(BasicBlock *BB); + void dump(DenseMap &d); + bool iterateOnFunction(Function &F); + bool performPRE(Function &F); + bool performScalarPRE(Instruction *I); + bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, + unsigned int ValNo); + Value *findLeader(const BasicBlock *BB, uint32_t num); + void cleanupGlobalSets(); + void verifyRemoved(const Instruction *I) const; + bool splitCriticalEdges(); + BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); + bool replaceOperandsWithConsts(Instruction *I) const; + bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, + bool DominatesByEdge); + bool processFoldableCondBr(BranchInst *BI); + void addDeadBlock(BasicBlock *BB); + void assignValNumForDeadCode(); +}; + +/// Create a legacy GVN pass. This also allows parameterizing whether or not +/// loads are eliminated by the pass. +FunctionPass *createGVNPass(bool NoLoads = false); + +} + +#endif diff --git a/llvm/lib/LTO/LTOCodeGenerator.cpp b/llvm/lib/LTO/LTOCodeGenerator.cpp index a07edef..2aadfa5 100644 --- a/llvm/lib/LTO/LTOCodeGenerator.cpp +++ b/llvm/lib/LTO/LTOCodeGenerator.cpp @@ -111,7 +111,7 @@ void LTOCodeGenerator::initializeLTOPasses() { initializeGlobalsAAWrapperPassPass(R); initializeLICMPass(R); initializeMergedLoadStoreMotionPass(R); - initializeGVNPass(R); + initializeGVNLegacyPassPass(R); initializeMemCpyOptPass(R); initializeDCEPass(R); initializeCFGSimplifyPassPass(R); diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index 7f55353..aeb6b64 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -51,6 +51,7 @@ #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/Transforms/Scalar/EarlyCSE.h" #include "llvm/Transforms/Scalar/LowerExpectIntrinsic.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Scalar/SROA.h" #include "llvm/Transforms/Scalar/SimplifyCFG.h" #include diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index 112ce90..325d919 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -92,6 +92,7 @@ FUNCTION_PASS("instcombine", InstCombinePass()) FUNCTION_PASS("invalidate", InvalidateAllAnalysesPass()) FUNCTION_PASS("no-op-function", NoOpFunctionPass()) FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass()) +FUNCTION_PASS("gvn", GVN()) FUNCTION_PASS("print", PrintFunctionPass(dbgs())) FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) diff --git a/llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp b/llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp index 04b8f49..cf0e5b7 100644 --- a/llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp +++ b/llvm/lib/Target/NVPTX/NVPTXTargetMachine.cpp @@ -44,6 +44,7 @@ #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetSubtargetInfo.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" using namespace llvm; diff --git a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp index ae4d802..3bc9cd5 100644 --- a/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp +++ b/llvm/lib/Transforms/IPO/PassManagerBuilder.cpp @@ -34,6 +34,7 @@ #include "llvm/Transforms/IPO/FunctionAttrs.h" #include "llvm/Transforms/IPO/InferFunctionAttrs.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Vectorize.h" #include "llvm/Transforms/Instrumentation.h" diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 0348401..4a3d7f4 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -15,7 +15,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/Hashing.h" @@ -53,6 +53,7 @@ #include "llvm/Transforms/Utils/SSAUpdater.h" #include using namespace llvm; +using namespace llvm::gvn; using namespace PatternMatch; #define DEBUG_TYPE "gvn" @@ -74,13 +75,7 @@ static cl::opt MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore, cl::desc("Max recurse depth (default = 1000)")); -//===----------------------------------------------------------------------===// -// ValueTable Class -//===----------------------------------------------------------------------===// - -namespace { - -struct Expression { +struct llvm::gvn::Expression { uint32_t opcode; Type *type; SmallVector varargs; @@ -106,45 +101,6 @@ struct Expression { } }; -/// This class holds the mapping between values and value numbers. It is used -/// as an efficient mechanism to determine the expression-wise equivalence of -/// two values. -class ValueTable { - DenseMap valueNumbering; - DenseMap expressionNumbering; - AliasAnalysis *AA; - MemoryDependenceResults *MD; - DominatorTree *DT; - - uint32_t nextValueNumber; - - Expression create_expression(Instruction *I); - Expression create_cmp_expression(unsigned Opcode, - CmpInst::Predicate Predicate, Value *LHS, - Value *RHS); - Expression create_extractvalue_expression(ExtractValueInst *EI); - uint32_t lookup_or_add_call(CallInst *C); - -public: - ValueTable() : nextValueNumber(1) {} - uint32_t lookup_or_add(Value *V); - uint32_t lookup(Value *V) const; - uint32_t lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Pred, - Value *LHS, Value *RHS); - bool exists(Value *V) const; - void add(Value *V, uint32_t num); - void clear(); - void erase(Value *v); - void setAliasAnalysis(AliasAnalysis *A) { AA = A; } - AliasAnalysis *getAliasAnalysis() const { return AA; } - void setMemDep(MemoryDependenceResults *M) { MD = M; } - void setDomTree(DominatorTree *D) { DT = D; } - uint32_t getNextUnusedValueNumber() { return nextValueNumber; } - void verifyRemoved(const Value *) const; -}; - -} // End anonymous namespace. - namespace llvm { template <> struct DenseMapInfo { static inline Expression getEmptyKey() { return ~0U; } @@ -161,11 +117,119 @@ template <> struct DenseMapInfo { }; } // End llvm namespace. +/// Represents a particular available value that we know how to materialize. +/// Materialization of an AvailableValue never fails. An AvailableValue is +/// implicitly associated with a rematerialization point which is the +/// location of the instruction from which it was formed. +struct llvm::gvn::AvailableValue { + enum ValType { + SimpleVal, // A simple offsetted value that is accessed. + LoadVal, // A value produced by a load. + MemIntrin, // A memory intrinsic which is loaded from. + UndefVal // A UndefValue representing a value from dead block (which + // is not yet physically removed from the CFG). + }; + + /// V - The value that is live out of the block. + PointerIntPair Val; + + /// Offset - The byte offset in Val that is interesting for the load query. + unsigned Offset; + + static AvailableValue get(Value *V, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(V); + Res.Val.setInt(SimpleVal); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(MI); + Res.Val.setInt(MemIntrin); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getLoad(LoadInst *LI, unsigned Offset = 0) { + AvailableValue Res; + Res.Val.setPointer(LI); + Res.Val.setInt(LoadVal); + Res.Offset = Offset; + return Res; + } + + static AvailableValue getUndef() { + AvailableValue Res; + Res.Val.setPointer(nullptr); + Res.Val.setInt(UndefVal); + Res.Offset = 0; + return Res; + } + + bool isSimpleValue() const { return Val.getInt() == SimpleVal; } + bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; } + bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; } + bool isUndefValue() const { return Val.getInt() == UndefVal; } + + Value *getSimpleValue() const { + assert(isSimpleValue() && "Wrong accessor"); + return Val.getPointer(); + } + + LoadInst *getCoercedLoadValue() const { + assert(isCoercedLoadValue() && "Wrong accessor"); + return cast(Val.getPointer()); + } + + MemIntrinsic *getMemIntrinValue() const { + assert(isMemIntrinValue() && "Wrong accessor"); + return cast(Val.getPointer()); + } + + /// Emit code at the specified insertion point to adjust the value defined + /// here to the specified type. This handles various coercion cases. + Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt, + GVN &gvn) const; +}; + +/// Represents an AvailableValue which can be rematerialized at the end of +/// the associated BasicBlock. +struct llvm::gvn::AvailableValueInBlock { + /// BB - The basic block in question. + BasicBlock *BB; + + /// AV - The actual available value + AvailableValue AV; + + static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) { + AvailableValueInBlock Res; + Res.BB = BB; + Res.AV = std::move(AV); + return Res; + } + + static AvailableValueInBlock get(BasicBlock *BB, Value *V, + unsigned Offset = 0) { + return get(BB, AvailableValue::get(V, Offset)); + } + static AvailableValueInBlock getUndef(BasicBlock *BB) { + return get(BB, AvailableValue::getUndef()); + } + + /// Emit code at the end of this block to adjust the value defined here to + /// the specified type. This handles various coercion cases. + Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const { + return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn); + } +}; + //===----------------------------------------------------------------------===// // ValueTable Internal Functions //===----------------------------------------------------------------------===// -Expression ValueTable::create_expression(Instruction *I) { +Expression GVN::ValueTable::create_expression(Instruction *I) { Expression e; e.type = I->getType(); e.opcode = I->getOpcode(); @@ -199,7 +263,7 @@ Expression ValueTable::create_expression(Instruction *I) { return e; } -Expression ValueTable::create_cmp_expression(unsigned Opcode, +Expression GVN::ValueTable::create_cmp_expression(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && @@ -218,7 +282,7 @@ Expression ValueTable::create_cmp_expression(unsigned Opcode, return e; } -Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { +Expression GVN::ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { assert(EI && "Not an ExtractValueInst?"); Expression e; e.type = EI->getType(); @@ -274,12 +338,24 @@ Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) { // ValueTable External Functions //===----------------------------------------------------------------------===// +GVN::ValueTable::ValueTable() : nextValueNumber(1) {} +GVN::ValueTable::ValueTable(const ValueTable &Arg) + : valueNumbering(Arg.valueNumbering), + expressionNumbering(Arg.expressionNumbering), AA(Arg.AA), MD(Arg.MD), + DT(Arg.DT), nextValueNumber(Arg.nextValueNumber) {} +GVN::ValueTable::ValueTable(ValueTable &&Arg) + : valueNumbering(std::move(Arg.valueNumbering)), + expressionNumbering(std::move(Arg.expressionNumbering)), + AA(std::move(Arg.AA)), MD(std::move(Arg.MD)), DT(std::move(Arg.DT)), + nextValueNumber(std::move(Arg.nextValueNumber)) {} +GVN::ValueTable::~ValueTable() {} + /// add - Insert a value into the table with a specified value number. -void ValueTable::add(Value *V, uint32_t num) { +void GVN::ValueTable::add(Value *V, uint32_t num) { valueNumbering.insert(std::make_pair(V, num)); } -uint32_t ValueTable::lookup_or_add_call(CallInst *C) { +uint32_t GVN::ValueTable::lookup_or_add_call(CallInst *C) { if (AA->doesNotAccessMemory(C)) { Expression exp = create_expression(C); uint32_t &e = expressionNumbering[exp]; @@ -389,11 +465,11 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { } /// Returns true if a value number exists for the specified value. -bool ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; } +bool GVN::ValueTable::exists(Value *V) const { return valueNumbering.count(V) != 0; } /// lookup_or_add - Returns the value number for the specified value, assigning /// it a new number if it did not have one before. -uint32_t ValueTable::lookup_or_add(Value *V) { +uint32_t GVN::ValueTable::lookup_or_add(Value *V) { DenseMap::iterator VI = valueNumbering.find(V); if (VI != valueNumbering.end()) return VI->second; @@ -464,7 +540,7 @@ uint32_t ValueTable::lookup_or_add(Value *V) { /// Returns the value number of the specified value. Fails if /// the value has not yet been numbered. -uint32_t ValueTable::lookup(Value *V) const { +uint32_t GVN::ValueTable::lookup(Value *V) const { DenseMap::const_iterator VI = valueNumbering.find(V); assert(VI != valueNumbering.end() && "Value not numbered?"); return VI->second; @@ -474,7 +550,7 @@ uint32_t ValueTable::lookup(Value *V) const { /// assigning it a new number if it did not have one before. Useful when /// we deduced the result of a comparison, but don't immediately have an /// instruction realizing that comparison to hand. -uint32_t ValueTable::lookup_or_add_cmp(unsigned Opcode, +uint32_t GVN::ValueTable::lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Predicate, Value *LHS, Value *RHS) { Expression exp = create_cmp_expression(Opcode, Predicate, LHS, RHS); @@ -484,20 +560,20 @@ uint32_t ValueTable::lookup_or_add_cmp(unsigned Opcode, } /// Remove all entries from the ValueTable. -void ValueTable::clear() { +void GVN::ValueTable::clear() { valueNumbering.clear(); expressionNumbering.clear(); nextValueNumber = 1; } /// Remove a value from the value numbering. -void ValueTable::erase(Value *V) { +void GVN::ValueTable::erase(Value *V) { valueNumbering.erase(V); } /// verifyRemoved - Verify that the value is removed from all internal data /// structures. -void ValueTable::verifyRemoved(const Value *V) const { +void GVN::ValueTable::verifyRemoved(const Value *V) const { for (DenseMap::const_iterator I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) { assert(I->first != V && "Inst still occurs in value numbering map!"); @@ -508,287 +584,15 @@ void ValueTable::verifyRemoved(const Value *V) const { // GVN Pass //===----------------------------------------------------------------------===// -namespace { -class GVN; - -/// Represents a particular available value that we know how to materialize. -/// Materialization of an AvailableValue never fails. An AvailableValue is -/// implicitly associated with a rematerialization point which is the -/// location of the instruction from which it was formed. -struct AvailableValue { - enum ValType { - SimpleVal, // A simple offsetted value that is accessed. - LoadVal, // A value produced by a load. - MemIntrin, // A memory intrinsic which is loaded from. - UndefVal // A UndefValue representing a value from dead block (which - // is not yet physically removed from the CFG). - }; - - /// V - The value that is live out of the block. - PointerIntPair Val; - - /// Offset - The byte offset in Val that is interesting for the load query. - unsigned Offset; - - static AvailableValue get(Value *V, unsigned Offset = 0) { - AvailableValue Res; - Res.Val.setPointer(V); - Res.Val.setInt(SimpleVal); - Res.Offset = Offset; - return Res; - } - - static AvailableValue getMI(MemIntrinsic *MI, unsigned Offset = 0) { - AvailableValue Res; - Res.Val.setPointer(MI); - Res.Val.setInt(MemIntrin); - Res.Offset = Offset; - return Res; - } - - static AvailableValue getLoad(LoadInst *LI, unsigned Offset = 0) { - AvailableValue Res; - Res.Val.setPointer(LI); - Res.Val.setInt(LoadVal); - Res.Offset = Offset; - return Res; - } - - static AvailableValue getUndef() { - AvailableValue Res; - Res.Val.setPointer(nullptr); - Res.Val.setInt(UndefVal); - Res.Offset = 0; - return Res; - } - - bool isSimpleValue() const { return Val.getInt() == SimpleVal; } - bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; } - bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; } - bool isUndefValue() const { return Val.getInt() == UndefVal; } - - Value *getSimpleValue() const { - assert(isSimpleValue() && "Wrong accessor"); - return Val.getPointer(); - } - - LoadInst *getCoercedLoadValue() const { - assert(isCoercedLoadValue() && "Wrong accessor"); - return cast(Val.getPointer()); - } - - MemIntrinsic *getMemIntrinValue() const { - assert(isMemIntrinValue() && "Wrong accessor"); - return cast(Val.getPointer()); - } - - /// Emit code at the specified insertion point to adjust the value defined - /// here to the specified type. This handles various coercion cases. - Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt, - GVN &gvn) const; -}; - -/// Represents an AvailableValue which can be rematerialized at the end of -/// the associated BasicBlock. -struct AvailableValueInBlock { - /// BB - The basic block in question. - BasicBlock *BB; - - /// AV - The actual available value - AvailableValue AV; - - static AvailableValueInBlock get(BasicBlock *BB, AvailableValue &&AV) { - AvailableValueInBlock Res; - Res.BB = BB; - Res.AV = std::move(AV); - return Res; - } - - static AvailableValueInBlock get(BasicBlock *BB, Value *V, - unsigned Offset = 0) { - return get(BB, AvailableValue::get(V, Offset)); - } - static AvailableValueInBlock getUndef(BasicBlock *BB) { - return get(BB, AvailableValue::getUndef()); - } - - /// Emit code at the end of this block to adjust the value defined here to - /// the specified type. This handles various coercion cases. - Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const { - return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn); - } -}; - -class GVN : public FunctionPass { - bool NoLoads; - MemoryDependenceResults *MD; - DominatorTree *DT; - const TargetLibraryInfo *TLI; - AssumptionCache *AC; - SetVector DeadBlocks; - - ValueTable VN; - - /// A mapping from value numbers to lists of Value*'s that - /// have that value number. Use findLeader to query it. - struct LeaderTableEntry { - Value *Val; - const BasicBlock *BB; - LeaderTableEntry *Next; - }; - DenseMap LeaderTable; - BumpPtrAllocator TableAllocator; - - // Block-local map of equivalent values to their leader, does not - // propagate to any successors. Entries added mid-block are applied - // to the remaining instructions in the block. - SmallMapVector ReplaceWithConstMap; - SmallVector InstrsToErase; - - typedef SmallVector LoadDepVect; - typedef SmallVector AvailValInBlkVect; - typedef SmallVector UnavailBlkVect; - -public: - static char ID; // Pass identification, replacement for typeid - explicit GVN(bool noloads = false) - : FunctionPass(ID), NoLoads(noloads), MD(nullptr) { - initializeGVNPass(*PassRegistry::getPassRegistry()); - } - - bool runOnFunction(Function &F) override; - - /// This removes the specified instruction from - /// our various maps and marks it for deletion. - void markInstructionForDeletion(Instruction *I) { - VN.erase(I); - InstrsToErase.push_back(I); - } - - DominatorTree &getDominatorTree() const { return *DT; } - AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } - MemoryDependenceResults &getMemDep() const { return *MD; } - -private: - /// Push a new Value to the LeaderTable onto the list for its value number. - void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { - LeaderTableEntry &Curr = LeaderTable[N]; - if (!Curr.Val) { - Curr.Val = V; - Curr.BB = BB; - return; - } - - LeaderTableEntry *Node = TableAllocator.Allocate(); - Node->Val = V; - Node->BB = BB; - Node->Next = Curr.Next; - Curr.Next = Node; - } - - /// Scan the list of values corresponding to a given - /// value number, and remove the given instruction if encountered. - void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) { - LeaderTableEntry *Prev = nullptr; - LeaderTableEntry *Curr = &LeaderTable[N]; - - while (Curr && (Curr->Val != I || Curr->BB != BB)) { - Prev = Curr; - Curr = Curr->Next; - } - - if (!Curr) - return; - - if (Prev) { - Prev->Next = Curr->Next; - } else { - if (!Curr->Next) { - Curr->Val = nullptr; - Curr->BB = nullptr; - } else { - LeaderTableEntry *Next = Curr->Next; - Curr->Val = Next->Val; - Curr->BB = Next->BB; - Curr->Next = Next->Next; - } - } - } - - // List of critical edges to be split between iterations. - SmallVector, 4> toSplit; - - // This transformation requires dominator postdominator info - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - if (!NoLoads) - AU.addRequired(); - AU.addRequired(); - - AU.addPreserved(); - AU.addPreserved(); - } - - // Helper functions of redundant load elimination - bool processLoad(LoadInst *L); - bool processNonLocalLoad(LoadInst *L); - bool processAssumeIntrinsic(IntrinsicInst *II); - /// Given a local dependency (Def or Clobber) determine if a value is - /// available for the load. Returns true if an value is known to be - /// available and populates Res. Returns false otherwise. - bool AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo, - Value *Address, AvailableValue &Res); - /// Given a list of non-local dependencies, determine if a value is - /// available for the load in each specified block. If it is, add it to - /// ValuesPerBlock. If not, add it to UnavailableBlocks. - void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps, - AvailValInBlkVect &ValuesPerBlock, - UnavailBlkVect &UnavailableBlocks); - bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock, - UnavailBlkVect &UnavailableBlocks); - - // Other helper routines - bool processInstruction(Instruction *I); - bool processBlock(BasicBlock *BB); - void dump(DenseMap &d); - bool iterateOnFunction(Function &F); - bool performPRE(Function &F); - bool performScalarPRE(Instruction *I); - bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred, - unsigned int ValNo); - Value *findLeader(const BasicBlock *BB, uint32_t num); - void cleanupGlobalSets(); - void verifyRemoved(const Instruction *I) const; - bool splitCriticalEdges(); - BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ); - bool replaceOperandsWithConsts(Instruction *I) const; - bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root, - bool DominatesByEdge); - bool processFoldableCondBr(BranchInst *BI); - void addDeadBlock(BasicBlock *BB); - void assignValNumForDeadCode(); -}; - -char GVN::ID = 0; - -} // End anonymous namespace. - -// The public interface to this file... -FunctionPass *llvm::createGVNPass(bool NoLoads) { - return new GVN(NoLoads); +PreservedAnalyses GVN::run(Function &F, AnalysisManager *AM) { + bool Changed = runImpl(F, AM->getResult(F), + AM->getResult(F), + AM->getResult(F), + AM->getResult(F), + &AM->getResult(F)); + return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); } -INITIALIZE_PASS_BEGIN(GVN, "gvn", "Global Value Numbering", false, false) -INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) -INITIALIZE_PASS_END(GVN, "gvn", "Global Value Numbering", false, false) - #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) void GVN::dump(DenseMap& d) { errs() << "{\n"; @@ -2350,18 +2154,16 @@ bool GVN::processInstruction(Instruction *I) { } /// runOnFunction - This is the main transformation entry point for a function. -bool GVN::runOnFunction(Function& F) { - if (skipOptnoneFunction(F)) - return false; - - if (!NoLoads) - MD = &getAnalysis().getMemDep(); - DT = &getAnalysis().getDomTree(); - AC = &getAnalysis().getAssumptionCache(F); - TLI = &getAnalysis().getTLI(); - VN.setAliasAnalysis(&getAnalysis().getAAResults()); - VN.setMemDep(MD); +bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, + const TargetLibraryInfo &RunTLI, AAResults &RunAA, + MemoryDependenceResults *RunMD) { + AC = &RunAC; + DT = &RunDT; VN.setDomTree(DT); + TLI = &RunTLI; + VN.setAliasAnalysis(&RunAA); + MD = RunMD; + VN.setMemDep(MD); bool Changed = false; bool ShouldContinue = true; @@ -2857,3 +2659,57 @@ void GVN::assignValNumForDeadCode() { } } } + +class llvm::gvn::GVNLegacyPass : public FunctionPass { +public: + static char ID; // Pass identification, replacement for typeid + explicit GVNLegacyPass(bool NoLoads = false) + : FunctionPass(ID), NoLoads(NoLoads) { + initializeGVNLegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipOptnoneFunction(F)) + return false; + + return Impl.runImpl( + F, getAnalysis().getAssumptionCache(F), + getAnalysis().getDomTree(), + getAnalysis().getTLI(), + getAnalysis().getAAResults(), + NoLoads ? nullptr + : &getAnalysis().getMemDep()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + if (!NoLoads) + AU.addRequired(); + AU.addRequired(); + + AU.addPreserved(); + AU.addPreserved(); + } + +private: + bool NoLoads; + GVN Impl; +}; + +char GVNLegacyPass::ID = 0; + +// The public interface to this file... +FunctionPass *llvm::createGVNPass(bool NoLoads) { + return new GVNLegacyPass(NoLoads); +} + +INITIALIZE_PASS_BEGIN(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_END(GVNLegacyPass, "gvn", "Global Value Numbering", false, false) diff --git a/llvm/lib/Transforms/Scalar/Scalar.cpp b/llvm/lib/Transforms/Scalar/Scalar.cpp index c9f3ef2..10b1462 100644 --- a/llvm/lib/Transforms/Scalar/Scalar.cpp +++ b/llvm/lib/Transforms/Scalar/Scalar.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ScopedNoAliasAA.h" #include "llvm/Analysis/TypeBasedAliasAnalysis.h" +#include "llvm/Transforms/Scalar/GVN.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Verifier.h" #include "llvm/InitializePasses.h" @@ -40,7 +41,7 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) { initializeDeadInstEliminationPass(Registry); initializeScalarizerPass(Registry); initializeDSEPass(Registry); - initializeGVNPass(Registry); + initializeGVNLegacyPassPass(Registry); initializeEarlyCSELegacyPassPass(Registry); initializeFlattenCFGPassPass(Registry); initializeInductiveRangeCheckEliminationPass(Registry); diff --git a/llvm/test/Transforms/GVN/basic.ll b/llvm/test/Transforms/GVN/basic.ll index 6f4aace..3e74f50 100644 --- a/llvm/test/Transforms/GVN/basic.ll +++ b/llvm/test/Transforms/GVN/basic.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -gvn -S | not grep "%z2 =" +; RUN: opt < %s -passes=gvn -S | not grep "%z2 =" define i32 @main() { block1: diff --git a/llvm/test/Transforms/GVN/pre-gep-load.ll b/llvm/test/Transforms/GVN/pre-gep-load.ll index 94cd045..9eec8bb 100644 --- a/llvm/test/Transforms/GVN/pre-gep-load.ll +++ b/llvm/test/Transforms/GVN/pre-gep-load.ll @@ -1,4 +1,6 @@ ; RUN: opt < %s -basicaa -gvn -enable-load-pre -S | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes=gvn -enable-load-pre -S | FileCheck %s + target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128" target triple = "aarch64--linux-gnu" -- 2.7.4