[PM] Port GVN to the new pass manager, wire it up, and teach a couple of tests to run GVN in both modes.

[chandlerc]

Summary

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.

[• dberlin]

Thanks so much for doing this.
This looks completely reasonable to me. While, as you say, this could be cleaned up further, and needs to be better documented, i don't think that's your job.
so LGTM

[chandlerc]

In D18019#372148, @dberlin wrote:

Thanks so much for doing this.
This looks completely reasonable to me. While, as you say, this could be cleaned up further, and needs to be better documented, i don't think that's your job.
so LGTM

Thanks for the review! Happy to help with any subsequent cleanups if I can, but yea, I'll probably focus on pass manager-y things for now.

[davidxl]

llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp

47

I noticed this line -- why is this inclusion needed?

[chandlerc]

llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp

47

Because NVPTX adds GVN into its target-specific code generation pass pipeline, and so it needs the 'createGVNPass' function. (You should be able to delete this and see the compile fail. At least, that's how I knew to add it.)

[davidxl]

llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp

47

The question is why Scalar .h does not include GVN.h?

[chandlerc]

llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp

47

Historically, LLVM used monolithic headers and functions that returned opaque types for passes.

A large chunk of the new pass manager design moves us towards "normal" patterns. There is a header, with a type, and maybe some helper functions. It allows much more fine grained headers so folks only pull in what they need. And with new-style passes it allows passes to be used outside the context of a pass manager if desirable (for unit testing for example).

If Scalar.h included GVN.h, then it would pull in a pretty large pile of code that doesn't make sense for everyone to pull in.

If Scalar.h continued to own the createGVNPass function, it would break proper modularity, as the constructs being defined in GVN.cpp would be declared in different and fairly distant places.

[davidxl]

ok, Scalar.h will eventually be deprecated then.

David

llvm/trunk/include/llvm/InitializePasses.h

 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeEarlyCSELegacyPassPass(PassRegistry &);
 void initializeEliminateAvailableExternallyPass(PassRegistry&);
 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&);
 void initializeIPCPPass(PassRegistry&);
 void initializeIPSCCPPass(PassRegistry&);
 void initializeIVUsersPass(PassRegistry&);
 void initializeIfConverterPass(PassRegistry&);
 void initializeInductiveRangeCheckEliminationPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #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"
 #include "llvm/Support/Valgrind.h"
 #include <cstdlib>
 
 namespace {
   struct ForcePassLinking {

llvm/trunk/include/llvm/Transforms/Scalar.h

 //
 // MergedLoadStoreMotion - This pass merges loads and stores in diamonds. Loads
 // are hoisted into the header, while stores sink into the footer.
 //
 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.
 //
 FunctionPass *createMemCpyOptPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopDeletion - This pass performs DCE of non-infinite loops that it

llvm/trunk/include/llvm/Transforms/Scalar/GVN.h

+//===- 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<GVN> {
+public:
+
+  /// \brief Run the pass over the function.
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> *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<Value *, uint32_t> valueNumbering;
+    DenseMap<gvn::Expression, uint32_t> 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<BasicBlock *> 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<uint32_t, LeaderTableEntry> 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<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
+  SmallVector<Instruction *, 8> InstrsToErase;
+
+  typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
+  typedef SmallVector<gvn::AvailableValueInBlock, 64> AvailValInBlkVect;
+  typedef SmallVector<BasicBlock *, 64> 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<LeaderTableEntry>();
+    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<std::pair<TerminatorInst *, unsigned>, 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<uint32_t, Value *> &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

llvm/trunk/lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeSROALegacyPassPass(R);
   initializeSROA_DTPass(R);
   initializeSROA_SSAUpPass(R);
   initializePostOrderFunctionAttrsLegacyPassPass(R);
   initializeReversePostOrderFunctionAttrsPass(R);
   initializeGlobalsAAWrapperPassPass(R);
   initializeLICMPass(R);
   initializeMergedLoadStoreMotionPass(R);
-  initializeGVNPass(R);
+  initializeGVNLegacyPassPass(R);
   initializeMemCpyOptPass(R);
   initializeDCEPass(R);
   initializeCFGSimplifyPassPass(R);
 }
 
 bool LTOCodeGenerator::addModule(LTOModule *Mod) {
   assert(&Mod->getModule().getContext() == &Context &&
          "Expected module in same context");

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #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 <type_traits>
 
 using namespace llvm;
 
 static Regex DefaultAliasRegex("^(default|lto-pre-link|lto)<(O[0123sz])>$");
 

llvm/trunk/lib/Passes/PassRegistry.def

 #endif
 FUNCTION_PASS("aa-eval", AAEvaluator())
 FUNCTION_PASS("adce", ADCEPass())
 FUNCTION_PASS("early-cse", EarlyCSEPass())
 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
+FUNCTION_PASS("gvn", GVN())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))
 FUNCTION_PASS("print<regions>", RegionInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs()))

llvm/trunk/lib/Target/NVPTX/NVPTXTargetMachine.cpp

 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetLoweringObjectFile.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/GVN.h"
 
 using namespace llvm;
 
 namespace llvm {
 void initializeNVVMReflectPass(PassRegistry&);
 void initializeGenericToNVVMPass(PassRegistry&);
 void initializeNVPTXAllocaHoistingPass(PassRegistry &);
 void initializeNVPTXAssignValidGlobalNamesPass(PassRegistry&);

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/ManagedStatic.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #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"
 
 using namespace llvm;
 
 static cl::opt<bool>
 RunLoopVectorization("vectorize-loops", cl::Hidden,
                      cl::desc("Run the Loop vectorization passes"));

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

 // This pass performs global value numbering to eliminate fully redundant
 // instructions.  It also performs simple dead load elimination.
 //
 // Note that this pass does the value numbering itself; it does not use the
 // ValueNumbering analysis passes.
 //
 //===----------------------------------------------------------------------===//
 
-#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"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <vector>
 using namespace llvm;
+using namespace llvm::gvn;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "gvn"
 
 STATISTIC(NumGVNInstr,  "Number of instructions deleted");
 STATISTIC(NumGVNLoad,   "Number of loads deleted");
 STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
 STATISTIC(NumGVNBlocks, "Number of blocks merged");
 STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
 STATISTIC(NumPRELoad,   "Number of loads PRE'd");
 
 static cl::opt<bool> EnablePRE("enable-pre",
                                cl::init(true), cl::Hidden);
 static cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true));
 
 // Maximum allowed recursion depth.
 static cl::opt<uint32_t>
 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<uint32_t, 4> varargs;
 
   Expression(uint32_t o = ~2U) : opcode(o) {}
 
   bool operator==(const Expression &other) const {
     if (opcode != other.opcode)
struct llvm::gvn::Expression {
 
   friend hash_code hash_value(const Expression &Value) {
     return hash_combine(
         Value.opcode, Value.type,
         hash_combine_range(Value.varargs.begin(), Value.varargs.end()));
   }
 };
 
-/// 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<Value *, uint32_t> valueNumbering;
-  DenseMap<Expression, uint32_t> 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<Expression> {
   static inline Expression getEmptyKey() { return ~0U; }
 
   static inline Expression getTombstoneKey() { return ~1U; }
 
   static unsigned getHashValue(const Expression e) {
     using llvm::hash_value;
     return static_cast<unsigned>(hash_value(e));
   }
   static bool isEqual(const Expression &LHS, const Expression &RHS) {
     return LHS == RHS;
   }
 };
 } // 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<Value *, 2, ValType> 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<LoadInst>(Val.getPointer());
+  }
+
+  MemIntrinsic *getMemIntrinValue() const {
+    assert(isMemIntrinValue() && "Wrong accessor");
+    return cast<MemIntrinsic>(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();
   for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
        OI != OE; ++OI)
     e.varargs.push_back(lookup_or_add(*OI));
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
if (CmpInst *C = dyn_cast<CmpInst>(I)) {
     for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
          II != IE; ++II)
       e.varargs.push_back(*II);
   }
 
   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) &&
          "Not a comparison!");
   Expression e;
   e.type = CmpInst::makeCmpResultType(LHS->getType());
   e.varargs.push_back(lookup_or_add(LHS));
   e.varargs.push_back(lookup_or_add(RHS));
 
   // Sort the operand value numbers so x<y and y>x get the same value number.
   if (e.varargs[0] > e.varargs[1]) {
     std::swap(e.varargs[0], e.varargs[1]);
     Predicate = CmpInst::getSwappedPredicate(Predicate);
   }
   e.opcode = (Opcode << 8) | Predicate;
   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();
   e.opcode = 0;
 
   IntrinsicInst *I = dyn_cast<IntrinsicInst>(EI->getAggregateOperand());
   if (I != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0 ) {
     // EI might be an extract from one of our recognised intrinsics. If it
Expression GVN::ValueTable::create_extractvalue_expression(ExtractValueInst *EI) {
 
   return e;
 }
 
 //===----------------------------------------------------------------------===//
 //                     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];
     if (!e) e = nextValueNumber++;
     valueNumbering[C] = e;
     return e;
   } else if (AA->onlyReadsMemory(C)) {
     Expression exp = create_expression(C);
uint32_t GVN::ValueTable::lookup_or_add_call(CallInst *C) {
 
   } else {
     valueNumbering[C] = nextValueNumber;
     return nextValueNumber++;
   }
 }
 
 /// 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<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
   if (VI != valueNumbering.end())
     return VI->second;
 
   if (!isa<Instruction>(V)) {
     valueNumbering[V] = nextValueNumber;
     return nextValueNumber++;
   }
uint32_t GVN::ValueTable::lookup_or_add(Value *V) {
   uint32_t& e = expressionNumbering[exp];
   if (!e) e = nextValueNumber++;
   valueNumbering[V] = e;
   return e;
 }
 
 /// 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<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
   assert(VI != valueNumbering.end() && "Value not numbered?");
   return VI->second;
 }
 
 /// Returns the value number of the given comparison,
 /// 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);
   uint32_t& e = expressionNumbering[exp];
   if (!e) e = nextValueNumber++;
   return e;
 }
 
 /// 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<Value*, uint32_t>::const_iterator
          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
     assert(I->first != V && "Inst still occurs in value numbering map!");
   }
 }
 
 //===----------------------------------------------------------------------===//
 //                                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<Value *, 2, ValType> 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;
-  }
+PreservedAnalyses GVN::run(Function &F, AnalysisManager<Function> *AM) {
+  bool Changed = runImpl(F, AM->getResult<AssumptionAnalysis>(F),
+                         AM->getResult<DominatorTreeAnalysis>(F),
+                         AM->getResult<TargetLibraryAnalysis>(F),
+                         AM->getResult<AAManager>(F),
+                         &AM->getResult<MemoryDependenceAnalysis>(F));
+  return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
 
-  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<LoadInst>(Val.getPointer());
-  }
-
-  MemIntrinsic *getMemIntrinValue() const {
-    assert(isMemIntrinValue() && "Wrong accessor");
-    return cast<MemIntrinsic>(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<BasicBlock *> 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<uint32_t, LeaderTableEntry> 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<llvm::Value *, llvm::Constant *, 4> ReplaceWithConstMap;
-  SmallVector<Instruction *, 8> InstrsToErase;
-
-  typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
-  typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect;
-  typedef SmallVector<BasicBlock *, 64> 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<LeaderTableEntry>();
-    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<std::pair<TerminatorInst *, unsigned>, 4> toSplit;
-
-  // This transformation requires dominator postdominator info
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequired<AssumptionCacheTracker>();
-    AU.addRequired<DominatorTreeWrapperPass>();
-    AU.addRequired<TargetLibraryInfoWrapperPass>();
-    if (!NoLoads)
-      AU.addRequired<MemoryDependenceWrapperPass>();
-    AU.addRequired<AAResultsWrapperPass>();
-
-    AU.addPreserved<DominatorTreeWrapperPass>();
-    AU.addPreserved<GlobalsAAWrapperPass>();
-  }
-
-  // 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<uint32_t, Value *> &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);
-}
-
-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<uint32_t, Value*>& d) {
   errs() << "{\n";
   for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
        E = d.end(); I != E; ++I) {
       errs() << I->first << "\n";
       I->second->dump();
   }
bool GVN::processInstruction(Instruction *I) {
   patchAndReplaceAllUsesWith(I, Repl);
   if (MD && Repl->getType()->getScalarType()->isPointerTy())
     MD->invalidateCachedPointerInfo(Repl);
   markInstructionForDeletion(I);
   return true;
 }
 
 /// 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<MemoryDependenceWrapperPass>().getMemDep();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
-  TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
-  VN.setAliasAnalysis(&getAnalysis<AAResultsWrapperPass>().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;
 
   // Merge unconditional branches, allowing PRE to catch more
   // optimization opportunities.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
     BasicBlock *BB = &*FI++;

 void GVN::assignValNumForDeadCode() {
   for (BasicBlock *BB : DeadBlocks) {
     for (Instruction &Inst : *BB) {
       unsigned ValNum = VN.lookup_or_add(&Inst);
       addToLeaderTable(ValNum, &Inst, BB);
     }
   }
 }
+
+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<AssumptionCacheTracker>().getAssumptionCache(F),
+        getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+        getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+        getAnalysis<AAResultsWrapperPass>().getAAResults(),
+        NoLoads ? nullptr
+                : &getAnalysis<MemoryDependenceWrapperPass>().getMemDep());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    if (!NoLoads)
+      AU.addRequired<MemoryDependenceWrapperPass>();
+    AU.addRequired<AAResultsWrapperPass>();
+
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+
+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)

llvm/trunk/lib/Transforms/Scalar/Scalar.cpp

 
 #include "llvm/Transforms/Scalar.h"
 #include "llvm-c/Initialization.h"
 #include "llvm-c/Transforms/Scalar.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #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"
 #include "llvm/IR/LegacyPassManager.h"
 
 using namespace llvm;
 
 /// initializeScalarOptsPasses - Initialize all passes linked into the
 /// ScalarOpts library.
 void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCELegacyPassPass(Registry);
   initializeBDCEPass(Registry);
   initializeAlignmentFromAssumptionsPass(Registry);
   initializeConstantHoistingPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCEPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeScalarizerPass(Registry);
   initializeDSEPass(Registry);
-  initializeGVNPass(Registry);
+  initializeGVNLegacyPassPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeFlattenCFGPassPass(Registry);
   initializeInductiveRangeCheckEliminationPass(Registry);
   initializeIndVarSimplifyPass(Registry);
   initializeJumpThreadingPass(Registry);
   initializeLICMPass(Registry);
   initializeLoopDataPrefetchPass(Registry);
   initializeLoopDeletionPass(Registry);

llvm/trunk/test/Transforms/GVN/basic.ll

 ; RUN: opt < %s -gvn -S | not grep "%z2 ="
+; RUN: opt < %s -passes=gvn -S | not grep "%z2 ="
 
 define i32 @main() {
 block1:
   %z1 = bitcast i32 0 to i32
   br label %block2
 block2:
   %z2 = bitcast i32 0 to i32
   ret i32 %z2
 }

llvm/trunk/test/Transforms/GVN/pre-gep-load.ll

 ; 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"
 
 define double @foo(i32 %stat, i32 %i, double** %p) {
 ; CHECK-LABEL: @foo(
 entry:
   switch i32 %stat, label %sw.default [
     i32 0, label %sw.bb