NewGVN

[majnemer]

include/llvm/Transforms/Scalar/GVNExpression.h

15–16

I'd insert a newline here.

17–18

I'd insert a newline here.

77

Comments should end with a period.

86

other should follow the naming convention.

119–120

unsigned int -> unsigned, there are other places where this not followed, please correct them.

129–162

Inline keyword is superfluous, we are in the class definition. Please correct this elsewhere as well.

557

Please use const auto * when assigning w/ a dyn_cast, the type should be clear.

[mehdi_amini]

Great to see this finally come upstream! Thanks for driving this :)

(Just two quick comments inline while I'm here)

include/llvm/Transforms/Scalar/GVNExpression.h

222

final does not seem applied equally everywhere, for instance why isn't LoadExpression marked final as well?

242

= default; (check the others)

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

1002

There's a bug (well, incompleteness) here that i just noticed
For memory, we also need to mark the uses of the MemoryDef/MemoryUse for the instruction as touched.
(and handle MemoryPhi's).
While most of the time, they are already touched, otherwise, will not iterate when we have discovered something about memory for, say, store over store.

MemoryPhi's will need value numbering when I fix the store over store problem, but for now, i'd just skip them.

So i'd add something like

if (MemoryAccess *MA = MSSA->getMemoryAccess(V)) 
  markMemoryUsersTouched(MA);

where markMemoryUsersTouched just walks the users of MA and mark MA->getInst() touched iff it's a MemoryUseOrDef.

This will ensure memory instructions change when we discover new things about them.

Sorry, in GCC, they are part of the IR, so there aren't two use lists :)

[Prazek]

include/llvm/Transforms/Scalar/GVNExpression.h

38

I am not really sure what does it mean, where other enums seems to be self descriptive.
Does it mean "inside basic block, but not BB start nor end?"

66

You could call another ctor here like:
Expression(unsigned int o = ..) : Expression(ExpressionTypeBase), o) {}

[davide]

Addressed the first round of comments + random cleanups I found by inspection.

[davide]

include/llvm/Transforms/Scalar/GVNExpression.h

222

Just an oversight. Fixed (also in other places).

242

I converted all of them, please let me know if I missed something

[jwhowarth]

Can you also post on Phabricator a mockup of a patch to enable the newgvn pass by default in the trunk clang compiler in order to simplify end-user testing? I noticed that the current clang compiler doesn't seem to enable the current gvn pass by default.

[davide]

In D26224#600689, @jwhowarth wrote:

Can you also post on Phabricator a mockup of a patch to enable the newgvn pass by default in the trunk clang compiler in order to simplify end-user testing? I noticed that the current clang compiler doesn't seem to enable the current gvn pass by default.

Sure, I'll make one. I'm not sure what you mean when you say that the current clang compiler doesn't call the current GVN. In EmitAssemblyHelper::CreatePasses, we call inside LLVM, PMBuilder.populateModulePassManager() which creates a pass pipeline containing GVN (see Transforms/IPO/PassManagerBuilder.cpp).

[jmolloy]

Hi Davide,

A high level comment for an issue I've just run into when rebasing GVNSink on top of NewGVN - you've defined LoadExpression::equals and StoreExpression::equals in the header, which gives multiple definition errors (for ::equals and the vtables) if any other file tries to #include <GVNExpression.h>.

Cheers,

James

[davide]

Move LoadExpression::equals/StoreExpression::equals to NewGVN.cpp

[davide]

ping

[Bigcheese]

include/llvm/Transforms/Scalar/GVNExpression.h

50

These don't need to be private.

55

This can be private.

56

Since you've got getOptcode() and setOpcode() this doesn't need to be protected. Either make this public and get rid of the accessors, or make it private.

65

I think this can be removed.

70

This needs to be an anchor as per http://llvm.org/docs/CodingStandards.html#provide-a-virtual-method-anchor-for-classes-in-headers

72–84

The behavior of this operator is quite nonintuitive. It's actually isTrivallyCongruent(), not is equal. However if this is the natural equality definition for this type, then it would be fine with a comment explaining that.

88–90

This can return a different hash_code for Expressions which compare equal.

112–114

Don't need to be private.

166

Not needed.

190

Anchor.

include/llvm/Transforms/Scalar/NewGVN.h

11–13

This looks like the comment from the old GVN pass.

lib/Transforms/Scalar/NewGVN.cpp

2

NewGVN.cpp

11–15

Old comment. Missing \file

128

Prefer ~0u

133

Prefer ~1u

146

This seems like the wrong equality operator for the above hash. It will return true for things that don't hash to the same value.

211

This doesn't need to be explicit.

1227

Do we have a proper type anywhere to use for a range instead of pair? first and last.

[davide]

Addressed Michael's comments.

[davide]

Sorry for the delay. I'm on the road this week with limited access to internet.
I encourage other people to comment so that we can get the first revision in tree and iterate from there.

include/llvm/Transforms/Scalar/GVNExpression.h

88–90

See Danny's reply (in the next mail).

lib/Transforms/Scalar/NewGVN.cpp

1227

No, I personally don't mind std::pair, but I can change it if you feel strong.

[davide]

Monday morning ping.
I would like to get the first cut in-tree soon (let's say, this week or the next) so we can iterate in-tree.

[RKSimon]

Mainly a code style review and a few random things I managed to spot. I don't know enough about GVN to go in depth.

What I did notice was that this really needs commenting more thoroughly, describing each Expression class type etc. and there needs to be more consistency with the ordering of class variables / method types.

include/llvm/Transforms/Scalar/GVNExpression.h

35

Use a short prefix not the whole enum type name: ET_Base, ..... ET_Store, ET_BasicEnd

48

Should this be called ExpressionBase or something?

63

Keep the constructors / destructors at the top of the public block? At least not mixed in with the other methods.

68

Magic numbers - replace with enum?

84

Split the print/debug methods into their own section headed with (similar to MachineInstr.h):

//
// Debugging support
//

84

Debug print out code can be quite bulky - worth moving these to a cpp file instead of inline?

117

Consistently put these next to the ops_begin() methods?

156

Put these consistently in the same place in each class.

206

Add override? Probably in a few other places too.

445

Put class variables consistently at the top or the bottom.

lib/Transforms/Scalar/NewGVN.cpp

137

static_cast<uintptr_t>(-1) ?

174

Is it a good idea to leave an initializer here?

246

Don't leave this amongst the creators

376

newline

437

Did you mean to compare pointer values?

443

Tidyup?

E->ops_push_back(lookupOperandLeader(Arg1, nullptr, B));
E->ops_push_back(lookupOperandLeader(Arg2, nullptr, B));

460

return nullptr;

553

wasted newline

591

Remove braces:

if (Value *V = ConstantFoldInstOperands(I, C, *DL, TLI))

677

E->ops_push_back(lookupOperandLeader(PointerOp, LI, B))

810

if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {

979

if (E == nullptr) {

1271

Same named variables is asking for trouble

1434

newline

1573

Why is this increment not done in the for block?

1681

Use for-range loop?

for (CongruenceClass *CC : CongruenceClasses])

1828

Why isn't this increment done in the for block?

[silvas]

Simon has done a pretty good job with the style review. Once his comments are cleaned up it will be easier to provide further comments.

A couple other stylistic comments and a doc request. I still need to do a walk-through of the code and stuff to provide more in-depth comments.

include/llvm/Transforms/Scalar/GVNExpression.h

242

PrintEType here and elsewhere.

lib/Transforms/Scalar/NewGVN.cpp

11

This file comment needs to be signficantly expanded. Remember, lots of people looking at this class might be e.g. people taking a compiler class that want to look at a "real" GVN implementation. Let's make sure come away impressed so that they will want to join LLVM!

At the very least, some citations for the relevant paper and stuff, along with summary of which exact variant of the algorithm are implemented would be good. Also, I think the high-level idea of GVN is simple enough that a high-level from-scratch description would be appropriate. I can help with writing this if you want.

In theory, we can expand this later, but when have you seen a commit improving a file-level comment? The only one I remember was in response to post-commit review asking for an improved file-level comment. So getting it right the first time is actually pretty important.

475

Are the ifdef's necessary when all that is inside is a DEBUG?

[silvas]

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

[davide]

In D26224#618046, @silvas wrote:

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

Yes, this is my intention. In the non-upstream branch all the tests have another run line which looks like
RUN: opt -newgvn %s | FileCheck %s. They're not included here just to make the diff smaller.

[kariddi]

lib/Transforms/Scalar/NewGVN.cpp

1220

This gets cleared, but the CongruenceClasses seem to be created through "new" and stored in the vector.

Where do they get destroyed?

[kariddi]

lib/Transforms/Scalar/NewGVN.cpp

1331

You are hiding the already defined variable of the same name above. This is slightly confusing while reading the code.

Consider changing this to CurrInstRange or the one above in TotalInstRange or something like that.

[RKSimon]

In D26224#618457, @davide wrote:

In D26224#618046, @silvas wrote:

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

Yes, this is my intention. In the non-upstream branch all the tests have another run line which looks like
RUN: opt -newgvn %s | FileCheck %s. They're not included here just to make the diff smaller.

Might it be possible to create a new phab patch now - dependent on this one that includes the NewGVN activation and test changes? Doesn't affect this initial patch but helps everyone see the upcoming effects on tests.

[davide]

Thank you all for the comments! New revision attached.

[davide]

In D26224#620326, @davide wrote:

Thank you all for the comments! New revision attached.

@hfinkel : Hal, do you plan to review this?

include/llvm/Transforms/Scalar/GVNExpression.h

35

Done.

48

To be honest, I prefer Expression. I can change it if you feel strong about it.

63

Fixed.

84

Not sure, this doesn't seem to have a terrible compile-time impact. We can move later, if needed.

84

yeah.

156

Done.

206

Done, I think.

445

Consistently put variables at the top of the class.

lib/Transforms/Scalar/NewGVN.cpp

11

I agree. Tried to expand it a bit.

137

Michael preferred ~0U, but from what I see -1 is used everywhere else, so I'm switching back.

460

Changed, here and everywhere else in the file.

475

Probably not, removing.

1271

well, very spread in the new PM port, but I agree with you. I put an underscore at the beginning so that we can distinguish.

1573

Many other passes do the same, seems like common style.

1681

Nice catch!

1828

See comment above.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

11

I'm happy to describe the sparse predicated algorithm a bit if you want to add it. I'll touch on the predication/etc bits when we add them.

Traditional GVN algorithms fall into two categories: Congruence partitioning and Hash based.

Hash based GVN's hash the operation performed by an instruction in some fashion, and look it up in a hash table. Anything that hashes the same and is otherwise "congruent" is considered equal. A hash based value numbering is optimistic if it is assumes that everything not in the table is congruent to everything else, and pessimistic if it is assumes everything not in the table is not congruent to everything else.

Congruence partitioning based GVN's start with every value in a single partition, and split the partition as they discover values that are not equal.

Optimistic hash based GVN and congruence partitioning GVN will discover the same set of congruences.

Most compilers nowadays use optimistic hash based approaches. The downside to optimistic hash based value numbering is that it requires reprocessing the entire routine again and again until the hashtables stops changing. This is because value dependences are not tracked well enough to know what must be reprocessed, and values can be involved in cycles (meaning there is no perfect order in which you can process the function to get a correct result). This makes these algorithms non-sparse. There are refinements to these algorithms, such as SCC based value numbering, which only requires iterating SCC's of the SSA graph, but most compilers use the hash table approach.

By contrast, the algorithm is more like the sparse conditional constant propagation algorithm, and uses a worklist of instructions to process. Dependencies between values and instructions are tracked finely enough (through the CongruenceClass structure) that when the value an operation has changes, we add the possibly dependent instructions to the worklist and keep going.

Memory locations s also value numbered by this algorithm. For memory, the goal of the algorithm is to discover the values stored at various memory locations (instead of just what loads are equivalent). Because of this loads and stores are value numbered together (while they are different expression classes, the hash ensures this occurs). MemorySSA is used to value number memory state.

To give a concrete example, given:
1 = MemoryDef(0)
store %a, %ptr

and

MemoryUse (1)
load %ptr

These will be value numbered into the same congruence class, as the memory is the same location with the same value.

This also enables the algorithm to discover equivalences that alias analysis cannot easily do.

A trivial example:

1= MemoryDef(0)
store %a, %ptr
MemoryUse(1)
load %ptr
2 = MemoryDef(1)
store %a, %ptr
MemoryUse(2)
load %ptr

These loads are equivalent, but a simple value numbering will not discover this.

The algorithm we use will discover that the stores store the same value, and thus will say that 1 and 2 are equivalent memory states.

It will then value number
MemoryUse(2)
load %ptr

as if it was
MemoryUse(1)
load %ptr

This enables the algorithm to discover fairly advanced (and even cyclic) equivalences between memory locations, much as it will do for scalars.

The algorithm used also performs unreachable code elimination/etc, similar to how sparse conditional constant propagation works. It optimistically assumes edges are unreachable until proven otherwise, and ignores unreachable values when value numbering phi nodes to create a maximal answer to value equivalence.

In addition to the above this algorithm supports forward propagation, global reassociation, and predication.

[silvas]

A couple more small comments as take another pass looking at the patch.

lib/Transforms/Scalar/NewGVN.cpp

843

"Don’t duplicate function or class name at the beginning of the comment."

http://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

1456

This is just implementing a lexicographical comparison, right?

If so, I would do:

return std::tie(DFSIn, DFSOut, ...) < std::tie(other.DFSIn, other.DFSOut, ...);

1465

This seems super sketchy, comparing < on pointers. What's up with that? Won't that make the result nondeterministic?

[hfinkel]

include/llvm/Transforms/Scalar/GVNExpression.h

66

Please explain in this comment why you're not comparing the expression types for loads and stores. This is also somewhat confusing because we've already compared the opcodes.

184

This looks a bit odd. Shouldn't you check the opcode equality first and then cast to BasicExpression?

lib/Transforms/Scalar/NewGVN.cpp

216

Do we want to guard this with #ifdef NDEBUG?

461

Add period after expression.

648

We also need to add operand bundles too for calls.

[davide]

Another round of comments.

[davide]

lib/Transforms/Scalar/NewGVN.cpp

648

Addressed all your other comments, Hal. I put a FIXME here and I'll review it later (sorry I'm not super familiar with operator bundles and I want to add a test as well).

843

Done, did a pass over NewGVN.cpp

1456

Done, it's now much easier to understand, thanks!

[hfinkel]

A few more comments on the comments, otherwise, I'm fine with committing this and working on it in-tree. Thanks for your work on this!

include/llvm/Transforms/Scalar/GVNExpression.h

67

What does load coercion mean in this context? Also, for loads and stores we set the opcode to 0 and that should be noted somewhere here.

lib/Transforms/Scalar/NewGVN.cpp

649

bundle operators -> operand bundles

[vsk]

include/llvm/Transforms/Scalar/GVNExpression.h

64

Could you add a brief comment explaining the significance of the ~0U, ~1U, and ~2U opcodes before using them? In particular, it would be nice to explain why we don't look at 'Other' when Opcode is in {~0,~1}.

[Prazek]

include/llvm/Transforms/Scalar/GVNExpression.h

112–115

It would be better to provide defautl values here

126–127

and remove it from here.
Also, it seems suspicious that NumOperands argument is not NumOperands, it is actually MaxOperands.

188

const auto &OE

242

const auto &OE

include/llvm-c/Transforms/Scalar.h

 void LLVMAddScalarizerPass(LLVMPassManagerRef PM);
 
 /** See llvm::createMergedLoadStoreMotionPass function. */
 void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM);
 
 /** See llvm::createGVNPass function. */
 void LLVMAddGVNPass(LLVMPassManagerRef PM);
 
+/** See llvm::createGVNPass function. */
+void LLVMAddNewGVNPass(LLVMPassManagerRef PM);
+
 /** See llvm::createIndVarSimplifyPass function. */
 void LLVMAddIndVarSimplifyPass(LLVMPassManagerRef PM);
 
 /** See llvm::createInstructionCombiningPass function. */
 void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM);
 
 /** See llvm::createJumpThreadingPass function. */
 void LLVMAddJumpThreadingPass(LLVMPassManagerRef PM);

include/llvm/InitializePasses.h

 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeMergedLoadStoreMotionLegacyPassPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeModuleSummaryIndexWrapperPassPass(PassRegistry &);
 void initializeNameAnonGlobalLegacyPassPass(PassRegistry &);
 void initializeNaryReassociateLegacyPassPass(PassRegistry &);
+void initializeNewGVNPass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);
 void initializeObjCARCContractPass(PassRegistry&);
 void initializeObjCARCExpandPass(PassRegistry&);
 void initializeObjCARCOptPass(PassRegistry&);
 void initializeOptimizationRemarkEmitterWrapperPassPass(PassRegistry&);
 void initializeOptimizePHIsPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createCountingFunctionInserterPass();
       (void) llvm::createEarlyCSEPass();
       (void) llvm::createGVNHoistPass();
       (void) llvm::createMergedLoadStoreMotionPass();
       (void) llvm::createGVNPass();
+      (void) llvm::createNewGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();
       (void) llvm::createInstructionNamerPass();
       (void) llvm::createMetaRenamerPass();
       (void) llvm::createPostOrderFunctionAttrsLegacyPass();
       (void) llvm::createReversePostOrderFunctionAttrsPass();
       (void) llvm::createMergeFunctionsPass();

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 *createNewGVNPass();
+
+//===----------------------------------------------------------------------===//
+//
 // 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

include/llvm/Transforms/Scalar/GVNExpression.h

+//======- GVNExpression.h - GVN Expression classes -------*- C++ -*-==-------=//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// The header file for the GVN pass that contains expression handling
+/// classes
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H
+#define LLVM_TRANSFORMS_SCALAR_GVNEXPRESSION_H
+
+#include "llvm/ADT/Hashing.h"
+#include "llvm/IR/Constant.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/ArrayRecycler.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+
+namespace llvm {
+class MemoryAccess;
+
+namespace GVNExpression {
+
+enum ExpressionType {
+  ExpressionTypeBase,
+  ExpressionTypeConstant,
+  ExpressionTypeVariable,
+  ExpressionTypeBasicStart,
+  ExpressionTypeBasic,
+  ExpressionTypeCall,
+  ExpressionTypeAggregateValue,
+  ExpressionTypePhi,
+  ExpressionTypeLoad,
+  ExpressionTypeStore,
+  ExpressionTypeBasicEnd
+};
+class Expression {
+
+private:
+  void operator=(const Expression &) = delete;
+  Expression(const Expression &) = delete;
+
+protected:
+  ExpressionType EType;
+  unsigned Opcode;
+
+public:
+  unsigned getOpcode() const { return Opcode; }
+
+  void setOpcode(unsigned opcode) { Opcode = opcode; }
+
+  ExpressionType getExpressionType() const { return EType; }
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const Expression *) { return true; }
+
+  Expression(ExpressionType ET = ExpressionTypeBase, unsigned O = ~2U)
+      : EType(ET), Opcode(O) {}
+
+  virtual ~Expression() = default;
+
+  bool operator==(const Expression &Other) const {
+    if (Opcode != Other.Opcode)
+      return false;
+    if (Opcode == ~0U || Opcode == ~1U)
+      return true;
+    // Compare etype for anything but load and store.
+    if (getExpressionType() != ExpressionTypeLoad &&
+        getExpressionType() != ExpressionTypeStore &&
+        getExpressionType() != Other.getExpressionType())
+      return false;
+
+    return equals(Other);
+  }
+
+  virtual bool equals(const Expression &Other) const { return true; }
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(EType, Opcode);
+  }
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "etype = " << EType << ",";
+    OS << "opcode = " << Opcode << ", ";
+  }
+
+  void print(raw_ostream &OS) const {
+    OS << "{ ";
+    printInternal(OS, true);
+    OS << "}";
+  }
+  void dump() const { print(dbgs()); }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const Expression &E) {
+  E.print(OS);
+  return OS;
+}
+
+class BasicExpression : public Expression {
+private:
+  void operator=(const BasicExpression &) = delete;
+  BasicExpression(const BasicExpression &) = delete;
+  BasicExpression() = delete;
+  typedef ArrayRecycler<Value *> RecyclerType;
+  typedef RecyclerType::Capacity RecyclerCapacity;
+
+protected:
+  Value **Operands;
+  unsigned MaxOperands;
+  unsigned NumOperands;
+  Type *ValueType;
+
+public:
+  typedef Value **op_iterator;
+  typedef Value *const *const_ops_iterator;
+
+  /// \brief Swap two operands. Used during GVN to put commutative operands in
+  /// order.
+  void swapOperands(unsigned First, unsigned Second) {
+    std::swap(Operands[First], Operands[Second]);
+  }
+  Value *getOperand(unsigned N) const {
+    assert(Operands && "Operands not allocated");
+    assert(N < NumOperands && "Operand out of range");
+    return Operands[N];
+  }
+
+  void setOperand(unsigned N, Value *V) {
+    assert(Operands && "Operands not allocated before setting");
+    assert(N < NumOperands && "Operand out of range");
+    Operands[N] = V;
+  }
+  unsigned getNumOperands() const { return NumOperands; }
+
+  op_iterator ops_begin() { return Operands; }
+  op_iterator ops_end() { return Operands + NumOperands; }
+  const_ops_iterator ops_begin() const { return Operands; }
+  const_ops_iterator ops_end() const { return Operands + NumOperands; }
+  iterator_range<op_iterator> operands() {
+    return iterator_range<op_iterator>(ops_begin(), ops_end());
+  }
+
+  iterator_range<const_ops_iterator> operands() const {
+    return iterator_range<const_ops_iterator>(ops_begin(), ops_end());
+  }
+
+  void ops_push_back(Value *Arg) {
+    assert(NumOperands < MaxOperands && "Tried to add too many operands");
+    assert(Operands && "Operandss not allocated before pushing");
+    Operands[NumOperands++] = Arg;
+  }
+  bool ops_empty() const { return getNumOperands() == 0; }
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const BasicExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    ExpressionType et = EB->getExpressionType();
+    return et > ExpressionTypeBasicStart && et < ExpressionTypeBasicEnd;
+  }
+
+  void allocateOperands(RecyclerType &Recycler, BumpPtrAllocator &Allocator) {
+    assert(!Operands && "Operands already allocated");
+    Operands = Recycler.allocate(RecyclerCapacity::get(MaxOperands), Allocator);
+  }
+  void deallocateOperands(RecyclerType &Recycler) {
+    Recycler.deallocate(RecyclerCapacity::get(MaxOperands), Operands);
+  }
+
+  void setType(Type *T) { ValueType = T; }
+
+  Type *getType() const { return ValueType; }
+
+  BasicExpression(unsigned NumOperands)
+      : BasicExpression(NumOperands, ExpressionTypeBasic) {}
+  BasicExpression(unsigned NumOperands, ExpressionType ET)
+      : Expression(ET), Operands(nullptr), MaxOperands(NumOperands),
+        NumOperands(0), ValueType(nullptr) {}
+
+  virtual ~BasicExpression() = default;
+
+  virtual bool equals(const Expression &Other) const {
+    const BasicExpression &OE = cast<BasicExpression>(Other);
+    if (Opcode != OE.Opcode)
+      return false;
+    if (ValueType != OE.ValueType)
+      return false;
+    if (NumOperands != OE.NumOperands)
+      return false;
+    if (!std::equal(ops_begin(), ops_end(), OE.ops_begin()))
+      return false;
+    return true;
+  }
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeBasic, ";
+
+    this->Expression::printInternal(OS, false);
+    OS << "operands = {";
+    for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+      OS << "[" << i << "] = ";
+      Operands[i]->printAsOperand(OS);
+      OS << "  ";
+    }
+    OS << "} ";
+  }
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(EType, Opcode, ValueType,
+                        hash_combine_range(ops_begin(), ops_end()));
+  }
+};
+class CallExpression final : public BasicExpression {
+private:
+  void operator=(const CallExpression &) = delete;
+  CallExpression(const CallExpression &) = delete;
+  CallExpression() = delete;
+
+protected:
+  CallInst *Call;
+  MemoryAccess *DefiningAccess;
+
+public:
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const CallExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeCall;
+  }
+  CallExpression(unsigned NumOperands, CallInst *C, MemoryAccess *DA)
+      : BasicExpression(NumOperands, ExpressionTypeCall), Call(C),
+        DefiningAccess(DA) {}
+
+  virtual ~CallExpression() = default;
+
+  virtual bool equals(const Expression &Other) const {
+    if (!this->BasicExpression::equals(Other))
+      return false;
+    const CallExpression &OE = cast<CallExpression>(Other);
+    if (DefiningAccess != OE.DefiningAccess)
+      return false;
+    return true;
+  }
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(this->BasicExpression::getHashValue(), DefiningAccess);
+  }
+
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeCall, ";
+    this->BasicExpression::printInternal(OS, false);
+    OS << " represents call at " << Call;
+  }
+};
+class LoadExpression final : public BasicExpression {
+private:
+  void operator=(const LoadExpression &) = delete;
+  LoadExpression(const LoadExpression &) = delete;
+  LoadExpression() = delete;
+
+protected:
+  LoadInst *Load;
+  MemoryAccess *DefiningAccess;
+  unsigned Alignment;
+
+  LoadExpression(enum ExpressionType EType, unsigned NumOperands,
+                 LoadInst *L, MemoryAccess *DA)
+      : BasicExpression(NumOperands, EType), Load(L), DefiningAccess(DA) {
+    Alignment = L ? L->getAlignment() : 0;
+  }
+
+public:
+  LoadInst *getLoadInst() const { return Load; }
+  void setLoadInst(LoadInst *L) { Load = L; }
+
+  MemoryAccess *getDefiningAccess() const { return DefiningAccess; }
+  void setDefiningAccess(MemoryAccess *MA) { DefiningAccess = MA; }
+  unsigned getAlignment() const { return Alignment; }
+  void setAlignment(unsigned Align) { Alignment = Align; }
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const LoadExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeLoad;
+  }
+
+  LoadExpression(unsigned NumOperands, LoadInst *L, MemoryAccess *DA)
+      : LoadExpression(ExpressionTypeLoad, NumOperands, L, DA) {}
+
+  virtual ~LoadExpression() = default;
+
+  virtual bool equals(const Expression &Other) const;
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(Opcode, ValueType, DefiningAccess,
+                        hash_combine_range(ops_begin(), ops_end()));
+  }
+
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeLoad, ";
+    this->BasicExpression::printInternal(OS, false);
+    OS << " represents Load at " << Load;
+    OS << " with DefiningAccess " << DefiningAccess;
+  }
+};
+
+class StoreExpression final : public BasicExpression {
+private:
+  void operator=(const StoreExpression &) = delete;
+  StoreExpression(const StoreExpression &) = delete;
+  StoreExpression() = delete;
+
+protected:
+  StoreInst *Store;
+  MemoryAccess *DefiningAccess;
+
+public:
+  StoreInst *getStoreInst() const { return Store; }
+  MemoryAccess *getDefiningAccess() const { return DefiningAccess; }
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const StoreExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeStore;
+  }
+  StoreExpression(unsigned NumOperands, StoreInst *S, MemoryAccess *DA)
+      : BasicExpression(NumOperands, ExpressionTypeStore), Store(S),
+        DefiningAccess(DA) {}
+
+  virtual ~StoreExpression() = default;
+
+  virtual bool equals(const Expression &Other) const;
+
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeStore, ";
+    this->BasicExpression::printInternal(OS, false);
+    OS << " represents Store at " << Store;
+  }
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(Opcode, ValueType, DefiningAccess,
+                        hash_combine_range(ops_begin(), ops_end()));
+  }
+};
+
+class AggregateValueExpression final : public BasicExpression {
+private:
+  void operator=(const AggregateValueExpression &) = delete;
+  AggregateValueExpression(const AggregateValueExpression &) = delete;
+  AggregateValueExpression() = delete;
+
+  unsigned MaxIntOperands;
+  unsigned NumIntOperands;
+  unsigned *IntOperands;
+
+public:
+  typedef unsigned *int_arg_iterator;
+  typedef const unsigned *const_int_arg_iterator;
+
+  int_arg_iterator int_ops_begin() { return IntOperands; }
+  int_arg_iterator int_ops_end() { return IntOperands + NumIntOperands; }
+  const_int_arg_iterator int_ops_begin() const { return IntOperands; }
+  const_int_arg_iterator int_ops_end() const {
+    return IntOperands + NumIntOperands;
+  }
+  unsigned int_ops_size() const { return NumIntOperands; }
+  bool int_ops_empty() const { return NumIntOperands == 0; }
+  void int_ops_push_back(unsigned IntOperand) {
+    assert(NumIntOperands < MaxIntOperands &&
+           "Tried to add too many int operands");
+    assert(IntOperands && "Operands not allocated before pushing");
+    IntOperands[NumIntOperands++] = IntOperand;
+  }
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const AggregateValueExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeAggregateValue;
+  }
+
+  AggregateValueExpression(unsigned NumOperands,
+                           unsigned NumIntOperands)
+      : BasicExpression(NumOperands, ExpressionTypeAggregateValue),
+        MaxIntOperands(NumIntOperands), NumIntOperands(0),
+        IntOperands(nullptr) {}
+
+  virtual ~AggregateValueExpression() = default;
+
+  virtual void allocateIntOperands(BumpPtrAllocator &Allocator) {
+    assert(!IntOperands && "Operands already allocated");
+    IntOperands = Allocator.Allocate<unsigned>(MaxIntOperands);
+  }
+
+  virtual bool equals(const Expression &Other) const {
+    if (!this->BasicExpression::equals(Other))
+      return false;
+    const AggregateValueExpression &OE = cast<AggregateValueExpression>(Other);
+    if (NumIntOperands != OE.NumIntOperands)
+      return false;
+    if (!std::equal(int_ops_begin(), int_ops_end(), OE.int_ops_begin()))
+      return false;
+
+    return true;
+  }
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(this->BasicExpression::getHashValue(),
+                        hash_combine_range(int_ops_begin(), int_ops_end()));
+  }
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeAggregateValue, ";
+    this->BasicExpression::printInternal(OS, false);
+    OS << ", intoperands = {";
+    for (unsigned i = 0, e = int_ops_size(); i != e; ++i) {
+      OS << "[" << i << "] = " << IntOperands[i] << "  ";
+    }
+    OS << "}";
+  }
+};
+
+class PHIExpression final : public BasicExpression {
+public:
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const PHIExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypePhi;
+  }
+  BasicBlock *getBB() const { return BB; }
+
+  void setBB(BasicBlock *bb) { BB = bb; }
+
+  virtual bool equals(const Expression &Other) const {
+    if (!this->BasicExpression::equals(Other))
+      return false;
+    const PHIExpression &OE = cast<PHIExpression>(Other);
+    if (BB != OE.BB)
+      return false;
+    return true;
+  }
+
+  PHIExpression(unsigned NumOperands, BasicBlock *B)
+      : BasicExpression(NumOperands, ExpressionTypePhi), BB(B) {}
+
+  virtual ~PHIExpression() = default;
+
+  virtual hash_code getHashValue() const {
+    return hash_combine(this->BasicExpression::getHashValue(), BB);
+  }
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypePhi, ";
+    this->BasicExpression::printInternal(OS, false);
+    OS << "bb = " << BB;
+  }
+
+private:
+  void operator=(const PHIExpression &) = delete;
+  PHIExpression(const PHIExpression &) = delete;
+  PHIExpression() = delete;
+  BasicBlock *BB;
+};
+class VariableExpression final : public Expression {
+public:
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const VariableExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeVariable;
+  }
+
+  Value *getVariableValue() const { return VariableValue; }
+  void setVariableValue(Value *V) { VariableValue = V; }
+  virtual bool equals(const Expression &Other) const {
+    const VariableExpression &OC = cast<VariableExpression>(Other);
+    if (VariableValue != OC.VariableValue)
+      return false;
+    return true;
+  }
+
+  VariableExpression(Value *V)
+      : Expression(ExpressionTypeVariable), VariableValue(V) {}
+  virtual hash_code getHashValue() const {
+    return hash_combine(EType, VariableValue->getType(), VariableValue);
+  }
+
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeVariable, ";
+    this->Expression::printInternal(OS, false);
+    OS << " variable = " << *VariableValue;
+  }
+
+private:
+  void operator=(const VariableExpression &) = delete;
+  VariableExpression(const VariableExpression &) = delete;
+  VariableExpression() = delete;
+
+  Value *VariableValue;
+};
+class ConstantExpression final : public Expression {
+public:
+  // Methods for support type inquiry through isa, cast, and dyn_cast.
+  static bool classof(const ConstantExpression *) { return true; }
+  static bool classof(const Expression *EB) {
+    return EB->getExpressionType() == ExpressionTypeConstant;
+  }
+  Constant *getConstantValue() const { return ConstantValue; }
+
+  void setConstantValue(Constant *V) { ConstantValue = V; }
+  virtual bool equals(const Expression &Other) const {
+    const ConstantExpression &OC = cast<ConstantExpression>(Other);
+    if (ConstantValue != OC.ConstantValue)
+      return false;
+    return true;
+  }
+
+  ConstantExpression()
+      : Expression(ExpressionTypeConstant), ConstantValue(NULL) {}
+
+  ConstantExpression(Constant *constantValue)
+      : Expression(ExpressionTypeConstant), ConstantValue(constantValue) {}
+  virtual hash_code getHashValue() const {
+    return hash_combine(EType, ConstantValue->getType(), ConstantValue);
+  }
+  virtual void printInternal(raw_ostream &OS, bool printEType) const {
+    if (printEType)
+      OS << "ExpressionTypeConstant, ";
+    this->Expression::printInternal(OS, false);
+    OS << " constant = " << *ConstantValue;
+  }
+
+private:
+  void operator=(const ConstantExpression &) = delete;
+  ConstantExpression(const ConstantExpression &) = delete;
+
+  Constant *ConstantValue;
+};
+
+bool LoadExpression::equals(const Expression &Other) const {
+  if (!isa<LoadExpression>(Other) && !isa<StoreExpression>(Other))
+    return false;
+  if (!this->BasicExpression::equals(Other))
+    return false;
+  if (const auto *OtherL = dyn_cast<LoadExpression>(&Other)) {
+    if (DefiningAccess != OtherL->getDefiningAccess())
+      return false;
+  } else if (const auto *OtherS = dyn_cast<StoreExpression>(&Other)) {
+    if (DefiningAccess != OtherS->getDefiningAccess())
+      return false;
+  }
+
+  return true;
+}
+bool StoreExpression::equals(const Expression &Other) const {
+  if (!isa<LoadExpression>(Other) && !isa<StoreExpression>(Other))
+    return false;
+  if (!this->BasicExpression::equals(Other))
+    return false;
+  if (const auto *OtherL = dyn_cast<LoadExpression>(&Other)) {
+    if (DefiningAccess != OtherL->getDefiningAccess())
+      return false;
+  } else if (const auto *OtherS = dyn_cast<StoreExpression>(&Other)) {
+    if (DefiningAccess != OtherS->getDefiningAccess())
+      return false;
+  }
+
+  return true;
+}
+}
+}
+
+#endif

include/llvm/Transforms/Scalar/NewGVN.h

+//===- NewGVN.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_NEWGVN_H
+#define LLVM_TRANSFORMS_SCALAR_NEWGVN_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+class NewGVNPass : public PassInfoMixin<NewGVNPass> {
+public:
+  /// \brief Run the pass over the function.
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
+};
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_NEWGVN_H
+

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   LoopUnswitch.cpp
   LoopVersioningLICM.cpp
   LowerAtomic.cpp
   LowerExpectIntrinsic.cpp
   LowerGuardIntrinsic.cpp
   MemCpyOptimizer.cpp
   MergedLoadStoreMotion.cpp
   NaryReassociate.cpp
+  NewGVN.cpp
   PartiallyInlineLibCalls.cpp
   PlaceSafepoints.cpp
   Reassociate.cpp
   Reg2Mem.cpp
   RewriteStatepointsForGC.cpp
   SCCP.cpp
   SROA.cpp
   Scalar.cpp

lib/Transforms/Scalar/NewGVN.cpp

+//===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// 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/NewGVN.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/SparseBitVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/TinyPtrVector.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/CFGPrinter.h"
+#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/Loads.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/MemoryDependenceAnalysis.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GlobalVariable.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/PredIteratorCache.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/GVNExpression.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
+#include "llvm/Transforms/Utils/SSAUpdater.h"
+#include <unordered_map>
+#include <utility>
+#include <vector>
+using namespace llvm;
+using namespace PatternMatch;
+using namespace llvm::GVNExpression;
+
+#define DEBUG_TYPE "newgvn"
+
+STATISTIC(NumGVNInstrDeleted, "Number of instructions deleted");
+STATISTIC(NumGVNBlocksDeleted, "Number of blocks deleted");
+STATISTIC(NumGVNOpsSimplified, "Number of Expressions simplified");
+STATISTIC(NumGVNPhisAllSame, "Number of PHIs whos arguments are all the same");
+
+//===----------------------------------------------------------------------===//
+//                                GVN Pass
+//===----------------------------------------------------------------------===//
+
+// Congruence classes represent the set of expressions/instructions
+// that are all the same *during some scope in the function*.
+// That is, because of the way we perform equality propagation, and
+// because of memory value numbering, it is not correct to assume
+// you can willy-nilly replace any member with any other at any
+// point in the function.
+//
+// For any Value in the Member set, it is valid to replace any dominated member
+// with that Value.
+//
+// Every congruence class has a leader, and the leader is used to
+// symbolize instructions in a canonical way (IE every operand of an
+// instruction that is a member of the same congruence class will
+// always be replaced with leader during symbolization).
+// To simplify symbolization, we keep the leader as a constant if class can be
+// proved to be a constant value.
+// Otherwise, the leader is a randomly chosen member of the value set, it does
+// not matter which one is chosen.
+// Each congruence class also has a defining expression,
+// though the expression may be null.  If it exists, it can be used for forward
+// propagation and reassociation of values.
+//
+struct CongruenceClass {
+  typedef SmallPtrSet<Value *, 4> MemberSet;
+  unsigned ID;
+  // Representative leader.
+  Value *RepLeader;
+  // Defining Expression.
+  const Expression *DefiningExpr;
+  // Actual members of this class.
+  MemberSet Members;
+
+  // True if this class has no members left.  This is mainly used for assertion
+  // purposes, and for skipping empty classes.
+  bool Dead;
+
+  explicit CongruenceClass(unsigned ID)
+      : ID(ID), RepLeader(0), DefiningExpr(0), Dead(false) {}
+  CongruenceClass(unsigned ID, Value *Leader, const Expression *E)
+      : ID(ID), RepLeader(Leader), DefiningExpr(E), Dead(false) {}
+};
+
+namespace llvm {
+  template <> struct DenseMapInfo<const Expression *> {
+    static const Expression *getEmptyKey() {
+      uintptr_t Val = static_cast<uintptr_t>(-1);
+      Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
+      return reinterpret_cast<const Expression *>(Val);
+    }
+    static const Expression *getTombstoneKey() {
+      uintptr_t Val = static_cast<uintptr_t>(-2);
+      Val <<= PointerLikeTypeTraits<const Expression *>::NumLowBitsAvailable;
+      return reinterpret_cast<const Expression *>(Val);
+    }
+    static unsigned getHashValue(const Expression *V) {
+      return static_cast<unsigned>(V->getHashValue());
+    }
+    static bool isEqual(const Expression *LHS, const Expression *RHS) {
+      if (LHS == RHS)
+        return true;
+      if (LHS == getTombstoneKey() || RHS == getTombstoneKey() ||
+          LHS == getEmptyKey() || RHS == getEmptyKey())
+        return false;
+      return *LHS == *RHS;
+    }
+  };
+} // end namespace llvm
+
+class NewGVN : public FunctionPass {
+  DominatorTree *DT;
+  const DataLayout *DL;
+  const TargetLibraryInfo *TLI;
+  AssumptionCache *AC;
+  AliasAnalysis *AA;
+  MemorySSA *MSSA;
+  MemorySSAWalker *MSSAWalker;
+  BumpPtrAllocator ExpressionAllocator;
+  ArrayRecycler<Value *> ArgRecycler;
+
+  // Congruence class info.
+  CongruenceClass *InitialClass;
+  std::vector<CongruenceClass *> CongruenceClasses;
+  unsigned NextCongruenceNum = 0;
+
+  // Value Mappings.
+  DenseMap<Value *, CongruenceClass *> ValueToClass;
+  DenseMap<Value *, const Expression *> ValueToExpression;
+
+  // Expression to class mapping.
+  typedef DenseMap<const Expression *, CongruenceClass *> ExpressionClassMap;
+  ExpressionClassMap ExpressionToClass;
+
+  // Which values have changed as a result of leader changes.
+  SmallPtrSet<Value *, 8> ChangedValues;
+
+  // Reachability info.
+  typedef BasicBlockEdge BlockEdge;
+  DenseSet<BlockEdge> ReachableEdges;
+  SmallPtrSet<const BasicBlock *, 8> ReachableBlocks;
+
+  // This is a bitvector because, on larger functions, we may have
+  // thousands of touched instructions at once (entire blocks,
+  // instructions with hundreds of uses, etc).  Even with optimization
+  // for when we mark whole blocks as touched, when this was a
+  // SmallPtrSet or DenseSet, for some functions, we spent >20% of all
+  // the time in GVN just managing this list.  The bitvector, on the
+  // other hand, efficiently supports test/set/clear of both
+  // individual and ranges, as well as "find next element" This
+  // enables us to use it as a worklist with essentially 0 cost.
+  BitVector TouchedInstructions;
+
+  DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
+  DenseMap<const DomTreeNode *, std::pair<unsigned, unsigned>>
+      DominatedInstRange;
+
+  // Debugging for how many times each block and instruction got processed.
+  DenseMap<const Value *, unsigned> ProcessedCount;
+
+  // DFS info.
+  DenseMap<const BasicBlock *, std::pair<int, int>> DFSDomMap;
+  DenseMap<const Value *, unsigned> InstrDFS;
+  std::vector<Instruction *> DFSToInstr;
+
+  // Deletion info.
+  SmallPtrSet<Instruction *, 8> InstructionsToErase;
+
+public:
+  static char ID; // Pass identification, replacement for typeid.
+  explicit NewGVN() : FunctionPass(ID) {
+    initializeNewGVNPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override;
+  bool runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
+              TargetLibraryInfo *TLI, AliasAnalysis *AA,
+              MemorySSA *MSSA);
+
+private:
+  // This transformation requires dominator postdominator info.
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<AssumptionCacheTracker>();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<TargetLibraryInfoWrapperPass>();
+    AU.addRequired<MemorySSAWrapperPass>();
+    AU.addRequired<AAResultsWrapperPass>();
+
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+  }
+
+  // Expression handling.
+  const Expression *createExpression(Instruction *, const BasicBlock *);
+  const Expression *createBinaryExpression(unsigned, Type *, Value *, Value *,
+                                           const BasicBlock *);
+  bool setBasicExpressionInfo(Instruction *, BasicExpression *,
+                              const BasicBlock *);
+  PHIExpression *createPHIExpression(Instruction *);
+  const VariableExpression *createVariableExpression(Value *);
+  const ConstantExpression *createConstantExpression(Constant *);
+  const Expression *createVariableOrConstant(Value *V, const BasicBlock *B);
+  const StoreExpression *createStoreExpression(StoreInst *, MemoryAccess *,
+                                               const BasicBlock *);
+  LoadExpression *createLoadExpression(Type *, Value *, LoadInst *,
+                                       MemoryAccess *, const BasicBlock *);
+
+  const CallExpression *createCallExpression(CallInst *, MemoryAccess *,
+                                             const BasicBlock *);
+  const AggregateValueExpression *
+  createAggregateValueExpression(Instruction *, const BasicBlock *);
+
+  // Congruence class handling.
+  CongruenceClass *createCongruenceClass(Value *Leader, const Expression *E) {
+    CongruenceClass *result =
+        new CongruenceClass(NextCongruenceNum++, Leader, E);
+    CongruenceClasses.emplace_back(result);
+    return result;
+  }
+
+  CongruenceClass *createSingletonCongruenceClass(Value *Member) {
+    CongruenceClass *CClass = createCongruenceClass(Member, NULL);
+    CClass->Members.insert(Member);
+    ValueToClass[Member] = CClass;
+    return CClass;
+  }
+  void initializeCongruenceClasses(Function &F);
+
+  // Symbolic evaluation.
+  const Expression *checkSimplificationResults(Expression *, Instruction *,
+                                               Value *);
+  const Expression *performSymbolicEvaluation(Value *, const BasicBlock *);
+  const Expression *performSymbolicLoadEvaluation(Instruction *,
+                                                  const BasicBlock *);
+  const Expression *performSymbolicStoreEvaluation(Instruction *,
+                                                   const BasicBlock *);
+  const Expression *performSymbolicCallEvaluation(Instruction *,
+                                                  const BasicBlock *);
+  const Expression *performSymbolicPHIEvaluation(Instruction *,
+                                                 const BasicBlock *);
+  const Expression *performSymbolicAggrValueEvaluation(Instruction *,
+                                                       const BasicBlock *);
+
+  // Congruence finding.
+  // Templated to allow them to work both on BB's and BB-edges.
+  template <class T>
+  Value *lookupOperandLeader(Value *, const User *, const T &) const;
+  void performCongruenceFinding(Value *, const Expression *);
+
+  // Reachability handling.
+  void updateReachableEdge(BasicBlock *, BasicBlock *);
+  void processOutgoingEdges(TerminatorInst *, BasicBlock *);
+  bool isOnlyReachableViaThisEdge(const BasicBlockEdge &);
+  Value *findConditionEquivalence(Value *, BasicBlock *) const;
+
+  // Elimination.
+  struct ValueDFS;
+  void convertDenseToDFSOrdered(CongruenceClass::MemberSet &,
+                                std::vector<ValueDFS> &);
+
+  bool eliminateInstructions(Function &);
+  void replaceInstruction(Instruction *, Value *);
+  void markInstructionForDeletion(Instruction *);
+  void deleteInstructionsInBlock(BasicBlock *);
+
+  // New instruction creation.
+  void handleNewInstruction(Instruction *){};
+  void markUsersTouched(Value *);
+  void markMemoryUsersTouched(MemoryAccess *);
+
+  // Utilities.
+  void cleanupTables();
+  std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
+  void updateProcessedCount(Value *V);
+};
+
+char NewGVN::ID = 0;
+
+// createGVNPass - The public interface to this file.
+FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); }
+
+#ifndef NDEBUG
+static std::string getBlockName(const BasicBlock *B) {
+  return DOTGraphTraits<const Function *>::getSimpleNodeLabel(B, NULL);
+}
+#endif
+
+INITIALIZE_PASS_BEGIN(NewGVN, "newgvn", "Global Value Numbering", false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_END(NewGVN, "newgvn", "Global Value Numbering", false, false)
+PHIExpression *NewGVN::createPHIExpression(Instruction *I) {
+  BasicBlock *PhiBlock = I->getParent();
+  PHINode *PN = cast<PHINode>(I);
+  PHIExpression *E = new (ExpressionAllocator)
+      PHIExpression(PN->getNumOperands(), I->getParent());
+
+  E->allocateOperands(ArgRecycler, ExpressionAllocator);
+  E->setType(I->getType());
+  E->setOpcode(I->getOpcode());
+  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
+    BasicBlock *B = PN->getIncomingBlock(i);
+    if (!ReachableBlocks.count(B)) {
+      DEBUG(dbgs() << "Skipping unreachable block " << getBlockName(B)
+                   << " in PHI node " << *PN << "\n");
+      continue;
+    }
+    if (I->getOperand(i) != I) {
+      const BasicBlockEdge BBE(B, PhiBlock);
+      auto Operand = lookupOperandLeader(I->getOperand(i), I, BBE);
+      E->ops_push_back(Operand);
+    } else {
+      E->ops_push_back(I->getOperand(i));
+    }
+  }
+  return E;
+}
+
+// Set basic expression info (Arguments, type, opcode) for Expression
+// E from Instruction I in block B.
+bool NewGVN::setBasicExpressionInfo(Instruction *I, BasicExpression *E,
+                                    const BasicBlock *B) {
+  bool AllConstant = true;
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
+    E->setType(GEP->getSourceElementType());
+  else
+    E->setType(I->getType());
+  E->setOpcode(I->getOpcode());
+  E->allocateOperands(ArgRecycler, ExpressionAllocator);
+
+  for (auto &O : I->operands()) {
+    auto Operand = lookupOperandLeader(O, I, B);
+    if (!isa<Constant>(Operand))
+      AllConstant = false;
+    E->ops_push_back(Operand);
+  }
+  return AllConstant;
+}
+
+const Expression *NewGVN::createBinaryExpression(unsigned Opcode, Type *T,
+                                                 Value *Arg1, Value *Arg2,
+                                                 const BasicBlock *B) {
+  BasicExpression *E = new (ExpressionAllocator) BasicExpression(2);
+
+  E->setType(T);
+  E->setOpcode(Opcode);
+  E->allocateOperands(ArgRecycler, ExpressionAllocator);
+  if (Instruction::isCommutative(Opcode)) {
+    // Ensure that commutative instructions that only differ by a permutation
+    // of their operands get the same value number by sorting the operand value
+    // numbers.  Since all commutative instructions have two operands it is more
+    // efficient to sort by hand rather than using, say, std::sort.
+    if (Arg1 > Arg2)
+      std::swap(Arg1, Arg2);
+  }
+  auto BinaryLeader = lookupOperandLeader(Arg1, nullptr, B);
+  E->ops_push_back(BinaryLeader);
+  BinaryLeader = lookupOperandLeader(Arg2, nullptr, B);
+  E->ops_push_back(BinaryLeader);
+
+  Value *V = SimplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), *DL, TLI,
+                           DT, AC);
+  if (const Expression *SimplifiedE = checkSimplificationResults(E, nullptr, V))
+    return SimplifiedE;
+  return E;
+}
+
+// Take a Value returned by simplification of Expression E/Instruction
+// I, and see if it resulted in a simpler expression. If so, return
+// that expression
+// TODO: Once finished, this should not take an Instruction, we only
+// use it for printing
+const Expression *NewGVN::checkSimplificationResults(Expression *E,
+                                                     Instruction *I, Value *V) {
+  if (!V)
+    return NULL;
+  if (auto *C = dyn_cast<Constant>(V)) {
+#ifndef NDEBUG
+    if (I)
+      DEBUG(dbgs() << "Simplified " << *I << " to "
+                   << " constant " << *C << "\n");
+#endif
+    NumGVNOpsSimplified++;
+    assert(isa<BasicExpression>(E) &&
+           "We should always have had a basic expression here");
+
+    cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
+    ExpressionAllocator.Deallocate(E);
+    return createConstantExpression(C);
+  } else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
+#ifndef NDEBUG
+    if (I)
+      DEBUG(dbgs() << "Simplified " << *I << " to "
+                   << " variable " << *V << "\n");
+#endif
+    cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
+    ExpressionAllocator.Deallocate(E);
+    return createVariableExpression(V);
+  }
+
+  CongruenceClass *CC = ValueToClass.lookup(V);
+  if (CC && CC->DefiningExpr) {
+#ifndef NDEBUG
+    if (I)
+      DEBUG(dbgs() << "Simplified " << *I << " to "
+                   << " expression " << *V << "\n");
+
+#endif
+    NumGVNOpsSimplified++;
+    assert(isa<BasicExpression>(E) &&
+           "We should always have had a basic expression here");
+    cast<BasicExpression>(E)->deallocateOperands(ArgRecycler);
+    ExpressionAllocator.Deallocate(E);
+    return CC->DefiningExpr;
+  }
+  return NULL;
+}
+
+const Expression *NewGVN::createExpression(Instruction *I,
+                                           const BasicBlock *B) {
+
+  BasicExpression *E =
+      new (ExpressionAllocator) BasicExpression(I->getNumOperands());
+
+  bool AllConstant = setBasicExpressionInfo(I, E, B);
+
+  if (I->isCommutative()) {
+    // Ensure that commutative instructions that only differ by a permutation
+    // of their operands get the same value number by sorting the operand value
+    // numbers.  Since all commutative instructions have two operands it is more
+    // efficient to sort by hand rather than using, say, std::sort.
+    assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
+    if (E->getOperand(0) > E->getOperand(1))
+      E->swapOperands(0, 1);
+  }
+
+  // Perform simplificaiton
+  // TODO: Right now we only check to see if we get a constant result.
+  // We may get a less than constant, but still better, result for
+  // some operations.
+  // IE
+  //  add 0, x -> x
+  //  and x, x -> x
+  // We should handle this by simply rewriting the expression.
+  if (auto *CI = dyn_cast<CmpInst>(I)) {
+    // Sort the operand value numbers so x<y and y>x get the same value
+    // number.
+    CmpInst::Predicate Predicate = CI->getPredicate();
+    if (E->getOperand(0) > E->getOperand(1)) {
+      E->swapOperands(0, 1);
+      Predicate = CmpInst::getSwappedPredicate(Predicate);
+    }
+    E->setOpcode((CI->getOpcode() << 8) | Predicate);
+    // TODO: 25% of our time is spent in SimplifyCmpInst with pointer operands
+    // TODO: Since we noop bitcasts, we may need to check types before
+    // simplifying, so that we don't end up simplifying based on a wrong
+    // type assumption. We should clean this up so we can use constants of the
+    // wrong type
+
+    assert(I->getOperand(0)->getType() == I->getOperand(1)->getType() &&
+           "Wrong types on cmp instruction");
+    if ((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
+         E->getOperand(1)->getType() == I->getOperand(1)->getType())) {
+      Value *V = SimplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1),
+                                 *DL, TLI, DT, AC);
+      if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+        return SimplifiedE;
+    }
+
+  } else if (isa<SelectInst>(I)) {
+    if (isa<Constant>(E->getOperand(0)) ||
+        (E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
+         E->getOperand(2)->getType() == I->getOperand(2)->getType())) {
+      Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1),
+                                    E->getOperand(2), *DL, TLI, DT, AC);
+      if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+        return SimplifiedE;
+    }
+  } else if (I->isBinaryOp()) {
+    Value *V = SimplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1),
+                             *DL, TLI, DT, AC);
+    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+      return SimplifiedE;
+  } else if (auto *BI = dyn_cast<BitCastInst>(I)) {
+    Value *V = SimplifyInstruction(BI, *DL, TLI, DT, AC);
+    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+      return SimplifiedE;
+  } else if (isa<GetElementPtrInst>(I)) {
+    Value *V = SimplifyGEPInst(E->getType(),
+                               ArrayRef<Value *>(E->ops_begin(), E->ops_end()),
+                               *DL, TLI, DT, AC);
+    if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+      return SimplifiedE;
+  } else if (AllConstant) {
+    // We don't bother trying to simplify unless all of the operands
+    // were constant.
+    // TODO: There are a lot of Simplify*'s we could call here, if we
+    // wanted to.  The original motivating case for this code was a
+    // zext i1 false to i8, which we don't have an interface to
+    // simplify (IE there is no SimplifyZExt).
+
+    SmallVector<Constant *, 8> C;
+    for (Value *Arg : E->operands())
+      C.emplace_back(cast<Constant>(Arg));
+
+    Value *V = ConstantFoldInstOperands(I, C, *DL, TLI);
+    if (V) {
+      if (const Expression *SimplifiedE = checkSimplificationResults(E, I, V))
+        return SimplifiedE;
+    }
+  }
+  return E;
+}
+
+const AggregateValueExpression *
+NewGVN::createAggregateValueExpression(Instruction *I, const BasicBlock *B) {
+  if (auto *II = dyn_cast<InsertValueInst>(I)) {
+    AggregateValueExpression *E = new (ExpressionAllocator)
+        AggregateValueExpression(I->getNumOperands(), II->getNumIndices());
+    setBasicExpressionInfo(I, E, B);
+    E->allocateIntOperands(ExpressionAllocator);
+
+    for (auto &Index : II->indices())
+      E->int_ops_push_back(Index);
+    return E;
+
+  } else if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
+    AggregateValueExpression *E = new (ExpressionAllocator)
+        AggregateValueExpression(I->getNumOperands(), EI->getNumIndices());
+    setBasicExpressionInfo(EI, E, B);
+    E->allocateIntOperands(ExpressionAllocator);
+
+    for (auto &Index : EI->indices())
+      E->int_ops_push_back(Index);
+    return E;
+  }
+  llvm_unreachable("Unhandled type of aggregate value operation");
+}
+
+const VariableExpression *
+NewGVN::createVariableExpression(Value *V) {
+  VariableExpression *E = new (ExpressionAllocator) VariableExpression(V);
+  E->setOpcode(V->getValueID());
+  return E;
+}
+
+const Expression *NewGVN::createVariableOrConstant(Value *V,
+                                                   const BasicBlock *B) {
+  auto Leader = lookupOperandLeader(V, nullptr, B);
+  if (auto *C = dyn_cast<Constant>(Leader))
+    return createConstantExpression(C);
+  return createVariableExpression(Leader);
+}
+
+const ConstantExpression *
+NewGVN::createConstantExpression(Constant *C) {
+  ConstantExpression *E = new (ExpressionAllocator) ConstantExpression(C);
+  E->setOpcode(C->getValueID());
+  return E;
+}
+
+const CallExpression *NewGVN::createCallExpression(CallInst *CI,
+                                                   MemoryAccess *HV,
+                                                   const BasicBlock *B) {
+  CallExpression *E =
+      new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, HV);
+  setBasicExpressionInfo(CI, E, B);
+  return E;
+}
+
+// lookupOperandLeader -- See if we have a congruence class and leader
+// for this operand, and if so, return it. Otherwise, return the
+// original operand.
+template <class T>
+Value *NewGVN::lookupOperandLeader(Value *V, const User *U,
+                                   const T &B) const {
+  CongruenceClass *CC = ValueToClass.lookup(V);
+  if (CC && (CC != InitialClass))
+    return CC->RepLeader;
+  return V;
+}
+
+LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
+                                             LoadInst *LI, MemoryAccess *DA,
+                                             const BasicBlock *B) {
+  LoadExpression *E = new (ExpressionAllocator) LoadExpression(1, LI, DA);
+  E->allocateOperands(ArgRecycler, ExpressionAllocator);
+  E->setType(LoadType);
+
+  // Give store and loads same opcode so they value number together.
+  E->setOpcode(0);
+  auto Operand = lookupOperandLeader(PointerOp, LI, B);
+  E->ops_push_back(Operand);
+  if (LI)
+    E->setAlignment(LI->getAlignment());
+
+  // TODO: Value number heap versions. We may be able to discover
+  // things alias analysis can't on it's own (IE that a store and a
+  // load have the same value, and thus, it isn't clobbering the load).
+  return E;
+}
+
+const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
+                                                     MemoryAccess *DA,
+                                                     const BasicBlock *B) {
+  StoreExpression *E =
+      new (ExpressionAllocator) StoreExpression(SI->getNumOperands(), SI, DA);
+  E->allocateOperands(ArgRecycler, ExpressionAllocator);
+  E->setType(SI->getValueOperand()->getType());
+
+  // Give store and loads same opcode so they value number together.
+  E->setOpcode(0);
+  auto Operand = lookupOperandLeader(SI->getPointerOperand(), SI, B);
+  E->ops_push_back(Operand);
+
+  // TODO: Value number heap versions. We may be able to discover
+  // things alias analysis can't on it's own (IE that a store and a
+  // load have the same value, and thus, it isn't clobbering the load).
+  return E;
+}
+
+const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I,
+                                                         const BasicBlock *B) {
+  StoreInst *SI = cast<StoreInst>(I);
+  const Expression *E = createStoreExpression(SI, MSSA->getMemoryAccess(SI), B);
+  return E;
+}
+
+const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I,
+                                                        const BasicBlock *B) {
+  LoadInst *LI = cast<LoadInst>(I);
+
+  // We can eliminate in favor of non-simple loads, but we won't be able to
+  // eliminate them.
+  if (!LI->isSimple())
+    return nullptr;
+
+  Value *LoadAddressLeader =
+      lookupOperandLeader(LI->getPointerOperand(), I, B);
+  // Load of undef is undef.
+  if (isa<UndefValue>(LoadAddressLeader))
+    return createConstantExpression(UndefValue::get(LI->getType()));
+
+  MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(I);
+
+  if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
+    if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
+      Instruction *DefiningInst = MD->getMemoryInst();
+      // If the defining instruction is not reachable, replace with undef.
+      if (!ReachableBlocks.count(DefiningInst->getParent()))
+        return createConstantExpression(UndefValue::get(LI->getType()));
+    }
+  }
+
+  const Expression *E = createLoadExpression(
+      LI->getType(), LI->getPointerOperand(), LI, DefiningAccess, B);
+  return E;
+}
+
+/// performSymbolicCallEvaluation - Evaluate read only and pure calls, and
+/// create an expression result.
+const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I,
+                                                        const BasicBlock *B) {
+  CallInst *CI = cast<CallInst>(I);
+  if (AA->doesNotAccessMemory(CI))
+    return createCallExpression(CI, nullptr, B);
+  else if (AA->onlyReadsMemory(CI))
+    return createCallExpression(CI, MSSAWalker->getClobberingMemoryAccess(CI),
+                                B);
+  else
+    return nullptr;
+}
+
+// performSymbolicPHIEvaluation - Evaluate PHI nodes symbolically, and
+// create an expression result.
+const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I,
+                                                       const BasicBlock *B) {
+  PHIExpression *E = cast<PHIExpression>(createPHIExpression(I));
+  if (E->ops_empty()) {
+    DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
+                 << "\n");
+    E->deallocateOperands(ArgRecycler);
+    ExpressionAllocator.Deallocate(E);
+    return createConstantExpression(UndefValue::get(I->getType()));
+  }
+
+  Value *AllSameValue = E->getOperand(0);
+
+  // See if all arguments are the same, ignoring undef arguments, because we can
+  // choose a value that is the same for them.
+  for (const Value *Arg : E->operands())
+    if (Arg != AllSameValue && !isa<UndefValue>(Arg)) {
+      AllSameValue = NULL;
+      break;
+    }
+
+  if (AllSameValue) {
+    // It's possible to have phi nodes with cycles (IE dependent on
+    // other phis that are .... dependent on the original phi node),
+    // especially in weird CFG's where some arguments are unreachable, or
+    // uninitialized along certain paths.
+    // This can cause infinite loops  during evaluation (even if you disable
+    // the recursion below, you will simply ping-pong between congruence
+    // classes). If a phi node symbolically evaluates to another phi node,
+    // just leave it alone. If they are really the same, we will still
+    // eliminate them in favor of each other.
+    if (isa<PHINode>(AllSameValue))
+      return E;
+    NumGVNPhisAllSame++;
+    DEBUG(dbgs() << "Simplified PHI node " << *I << " to " << *AllSameValue
+                 << "\n");
+    E->deallocateOperands(ArgRecycler);
+    ExpressionAllocator.Deallocate(E);
+    if (auto *C = dyn_cast<Constant>(AllSameValue))
+      return createConstantExpression(C);
+    return createVariableExpression(AllSameValue);
+  }
+  return E;
+}
+
+const Expression *
+NewGVN::performSymbolicAggrValueEvaluation(Instruction *I,
+                                           const BasicBlock *B) {
+  if (auto *EI = dyn_cast<ExtractValueInst>(I)) {
+    auto *II = dyn_cast<IntrinsicInst>(EI->getAggregateOperand());
+    if (II != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
+      unsigned Opcode = 0;
+      // EI might be an extract from one of our recognised intrinsics. If it
+      // is we'll synthesize a semantically equivalent expression instead on
+      // an extract value expression.
+      switch (II->getIntrinsicID()) {
+      case Intrinsic::sadd_with_overflow:
+      case Intrinsic::uadd_with_overflow:
+        Opcode = Instruction::Add;
+        break;
+      case Intrinsic::ssub_with_overflow:
+      case Intrinsic::usub_with_overflow:
+        Opcode = Instruction::Sub;
+        break;
+      case Intrinsic::smul_with_overflow:
+      case Intrinsic::umul_with_overflow:
+        Opcode = Instruction::Mul;
+        break;
+      default:
+        break;
+      }
+
+      if (Opcode != 0) {
+        // Intrinsic recognized. Grab its args to finish building the
+        // expression.
+        assert(II->getNumArgOperands() == 2 &&
+               "Expect two args for recognised intrinsics.");
+        return createBinaryExpression(Opcode, EI->getType(),
+                                      II->getArgOperand(0),
+                                      II->getArgOperand(1), B);
+      }
+    }
+  }
+
+  return createAggregateValueExpression(I, B);
+}
+
+/// performSymbolicEvaluation - Substitute and symbolize the value
+/// before value numbering.
+const Expression *NewGVN::performSymbolicEvaluation(Value *V,
+                                                    const BasicBlock *B) {
+  const Expression *E = NULL;
+  if (auto *C = dyn_cast<Constant>(V))
+    E = createConstantExpression(C);
+  else if (isa<Argument>(V) || isa<GlobalVariable>(V)) {
+    E = createVariableExpression(V);
+  } else {
+    // TODO: memory intrinsics.
+    // TODO: Some day, we should do the forward propagation and reassociation
+    // parts of the algorithm.
+    Instruction *I = cast<Instruction>(V);
+    switch (I->getOpcode()) {
+    case Instruction::ExtractValue:
+    case Instruction::InsertValue:
+      E = performSymbolicAggrValueEvaluation(I, B);
+      break;
+    case Instruction::PHI:
+      E = performSymbolicPHIEvaluation(I, B);
+      break;
+    case Instruction::Call:
+      E = performSymbolicCallEvaluation(I, B);
+      break;
+    case Instruction::Store:
+      E = performSymbolicStoreEvaluation(I, B);
+      break;
+    case Instruction::Load:
+      E = performSymbolicLoadEvaluation(I, B);
+      break;
+    case Instruction::BitCast: {
+      E = createExpression(I, B);
+    } break;
+
+    case Instruction::Add:
+    case Instruction::FAdd:
+    case Instruction::Sub:
+    case Instruction::FSub:
+    case Instruction::Mul:
+    case Instruction::FMul:
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::FDiv:
+    case Instruction::URem:
+    case Instruction::SRem:
+    case Instruction::FRem:
+    case Instruction::Shl:
+    case Instruction::LShr:
+    case Instruction::AShr:
+    case Instruction::And:
+    case Instruction::Or:
+    case Instruction::Xor:
+    case Instruction::ICmp:
+    case Instruction::FCmp:
+    case Instruction::Trunc:
+    case Instruction::ZExt:
+    case Instruction::SExt:
+    case Instruction::FPToUI:
+    case Instruction::FPToSI:
+    case Instruction::UIToFP:
+    case Instruction::SIToFP:
+    case Instruction::FPTrunc:
+    case Instruction::FPExt:
+    case Instruction::PtrToInt:
+    case Instruction::IntToPtr:
+    case Instruction::Select:
+    case Instruction::ExtractElement:
+    case Instruction::InsertElement:
+    case Instruction::ShuffleVector:
+    case Instruction::GetElementPtr:
+      E = createExpression(I, B);
+      break;
+    default:
+      return NULL;
+    }
+  }
+  if (!E)
+    return NULL;
+  return E;
+}
+
+/// There is an edge from 'Src' to 'Dst'.  Return true if every path from
+/// the entry block to 'Dst' passes via this edge.  In particular 'Dst'
+/// must not be reachable via another edge from 'Src'.
+bool NewGVN::isOnlyReachableViaThisEdge(const BasicBlockEdge &E) {
+
+  // While in theory it is interesting to consider the case in which Dst has
+  // more than one predecessor, because Dst might be part of a loop which is
+  // only reachable from Src, in practice it is pointless since at the time
+  // GVN runs all such loops have preheaders, which means that Dst will have
+  // been changed to have only one predecessor, namely Src.
+  const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
+  const BasicBlock *Src = E.getStart();
+  assert((!Pred || Pred == Src) && "No edge between these basic blocks!");
+  (void)Src;
+  return Pred != nullptr;
+}
+
+void NewGVN::markUsersTouched(Value *V) {
+  // Now mark the users as touched.
+  for (auto &U : V->uses()) {
+    auto *User = dyn_cast<Instruction>(U.getUser());
+    assert(User && "Use of value not within an instruction?");
+    TouchedInstructions.set(InstrDFS[User]);
+  }
+}
+
+void NewGVN::markMemoryUsersTouched(MemoryAccess *MA) {
+  for (auto U : MA->users()) {
+    if (auto *MUD = dyn_cast<MemoryUseOrDef>(U))
+      TouchedInstructions.set(InstrDFS[MUD->getMemoryInst()]);
+    else
+      TouchedInstructions.set(InstrDFS[MA]);
+  }
+}
+
+/// perf rmCongruenceFinding - Perform congruence finding on a given
+/// value numbering expression.
+void NewGVN::performCongruenceFinding(Value *V, const Expression *E) {
+
+  ValueToExpression[V] = E;
+  // This is guaranteed to return something, since it will at least find
+  // INITIAL.
+  CongruenceClass *VClass = ValueToClass[V];
+  assert(VClass && "Should have found a vclass");
+  // Dead classes should have been eliminated from the mapping.
+  assert(!VClass->Dead && "Found a dead class");
+
+  CongruenceClass *EClass;
+  // Expressions we can't symbolize are always in their own unique
+  // congruence class.
+  if (E == NULL) {
+    // We may have already made a unique class.
+    if (VClass->Members.size() != 1 || VClass->RepLeader != V) {
+      CongruenceClass *NewClass = createCongruenceClass(V, NULL);
+      // We should always be adding the member in the below code.
+      EClass = NewClass;
+      DEBUG(dbgs() << "Created new congruence class for " << *V
+                   << " due to NULL expression\n");
+    } else {
+      EClass = VClass;
+    }
+  } else if (const auto *VE = dyn_cast<VariableExpression>(E)) {
+    EClass = ValueToClass[VE->getVariableValue()];
+  } else {
+    auto lookupResult = ExpressionToClass.insert({E, nullptr});
+
+    // If it's not in the value table, create a new congruence class.
+    if (lookupResult.second) {
+      CongruenceClass *NewClass = createCongruenceClass(NULL, E);
+      auto place = lookupResult.first;
+      place->second = NewClass;
+
+      // Constants and variables should always be made the leader.
+      if (const auto *CE = dyn_cast<ConstantExpression>(E))
+        NewClass->RepLeader = CE->getConstantValue();
+      else if (const auto *VE = dyn_cast<VariableExpression>(E))
+        NewClass->RepLeader = VE->getVariableValue();
+      else if (const auto *SE = dyn_cast<StoreExpression>(E))
+        NewClass->RepLeader = SE->getStoreInst()->getValueOperand();
+      else
+        NewClass->RepLeader = V;
+
+      EClass = NewClass;
+      DEBUG(dbgs() << "Created new congruence class for " << *V
+                   << " using expression " << *E << " at " << NewClass->ID
+                   << "\n");
+      DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n");
+    } else {
+      EClass = lookupResult.first->second;
+      assert(EClass && "Somehow don't have an eclass");
+
+      assert(!EClass->Dead && "We accidentally looked up a dead class");
+    }
+  }
+  bool WasInChanged = ChangedValues.erase(V);
+  if (VClass != EClass || WasInChanged) {
+    DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
+                 << "\n");
+
+    if (VClass != EClass) {
+      DEBUG(dbgs() << "New congruence class for " << V << " is " << EClass->ID
+                   << "\n");
+
+      VClass->Members.erase(V);
+      EClass->Members.insert(V);
+      ValueToClass[V] = EClass;
+      // See if we destroyed the class or need to swap leaders.
+      if (VClass->Members.empty() && VClass != InitialClass) {
+        if (VClass->DefiningExpr) {
+          VClass->Dead = true;
+          DEBUG(dbgs() << "Erasing expression " << *E << " from table\n");
+          ExpressionToClass.erase(VClass->DefiningExpr);
+        }
+      } else if (VClass->RepLeader == V) {
+        // FIXME: When the leader changes, the value numbering of
+        // everything may change, so we need to reprocess.
+        VClass->RepLeader = *(VClass->Members.begin());
+        for (auto M : VClass->Members) {
+          if (auto *I = dyn_cast<Instruction>(M))
+            TouchedInstructions.set(InstrDFS[I]);
+          ChangedValues.insert(M);
+        }
+      }
+    }
+    markUsersTouched(V);
+    if (Instruction *I = dyn_cast<Instruction>(V))
+      if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
+        markMemoryUsersTouched(MA);
+  }
+}
+
+// updateReachableEdge - Process the fact that Edge (from, to) is
+// reachable, including marking any newly reachable blocks and
+// instructions for processing.
+void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
+  // Check if the Edge was reachable before.
+  if (ReachableEdges.insert({From, To}).second) {
+    // If this block wasn't reachable before, all instructions are touched.
+    if (ReachableBlocks.insert(To).second) {
+      DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n");
+      const auto &InstRange = BlockInstRange.lookup(To);
+      TouchedInstructions.set(InstRange.first, InstRange.second);
+    } else {
+      DEBUG(dbgs() << "Block " << getBlockName(To)
+                   << " was reachable, but new edge {" << getBlockName(From)
+                   << "," << getBlockName(To) << "} to it found\n");
+
+      // We've made an edge reachable to an existing block, which may
+      // impact predicates. Otherwise, only mark the phi nodes as touched, as
+      // they are the only thing that depend on new edges. Anything using their
+      // values will get propagated to if necessary.
+      auto BI = To->begin();
+      while (isa<PHINode>(BI)) {
+        TouchedInstructions.set(InstrDFS[&*BI]);
+        ++BI;
+      }
+    }
+  }
+}
+
+// findConditionEquivalence - Given a predicate condition (from a
+// switch, cmp, or whatever) and a block, see if we know some constant
+// value for it already.
+Value *NewGVN::findConditionEquivalence(Value *Cond, BasicBlock *B) const {
+  auto Result = lookupOperandLeader(Cond, nullptr, B);
+  if (isa<Constant>(Result))
+    return Result;
+  return nullptr;
+}
+
+//  processOutgoingEdges - Process the outgoing edges of a block for
+//  reachability.
+void NewGVN::processOutgoingEdges(TerminatorInst *TI, BasicBlock *B) {
+  // Evaluate reachability of terminator instruction.
+  BranchInst *BR;
+  if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
+    Value *Cond = BR->getCondition();
+    Value *CondEvaluated = findConditionEquivalence(Cond, B);
+    if (!CondEvaluated) {
+      if (auto *I = dyn_cast<Instruction>(Cond)) {
+        const Expression *E = createExpression(I, B);
+        if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
+          CondEvaluated = CE->getConstantValue();
+        }
+      } else if (isa<ConstantInt>(Cond)) {
+        CondEvaluated = Cond;
+      }
+    }
+    ConstantInt *CI;
+    BasicBlock *TrueSucc = BR->getSuccessor(0);
+    BasicBlock *FalseSucc = BR->getSuccessor(1);
+    if (CondEvaluated && (CI = dyn_cast<ConstantInt>(CondEvaluated))) {
+      if (CI->isOne()) {
+        DEBUG(dbgs() << "Condition for Terminator " << *TI
+                     << " evaluated to true\n");
+        updateReachableEdge(B, TrueSucc);
+      } else if (CI->isZero()) {
+        DEBUG(dbgs() << "Condition for Terminator " << *TI
+                     << " evaluated to false\n");
+        updateReachableEdge(B, FalseSucc);
+      }
+    } else {
+      updateReachableEdge(B, TrueSucc);
+      updateReachableEdge(B, FalseSucc);
+    }
+  } else if (auto *SI = dyn_cast<SwitchInst>(TI)) {
+    // For switches, propagate the case values into the case
+    // destinations.
+
+    // Remember how many outgoing edges there are to every successor.
+    SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
+
+    bool MultipleEdgesOneReachable = false;
+    Value *SwitchCond = SI->getCondition();
+    Value *CondEvaluated = findConditionEquivalence(SwitchCond, B);
+    // See if we were able to turn this switch statement into a constant.
+    if (CondEvaluated && isa<ConstantInt>(CondEvaluated)) {
+      ConstantInt *CondVal = cast<ConstantInt>(CondEvaluated);
+      // We should be able to get case value for this.
+      auto CaseVal = SI->findCaseValue(CondVal);
+      if (CaseVal.getCaseSuccessor() == SI->getDefaultDest()) {
+        // We proved the value is outside of the range of the case.
+        // We can't do anything other than mark the default dest as reachable,
+        // and go home.
+        updateReachableEdge(B, SI->getDefaultDest());
+        return;
+      }
+      // Now get where it goes and mark it reachable.
+      BasicBlock *TargetBlock = CaseVal.getCaseSuccessor();
+      updateReachableEdge(B, TargetBlock);
+      unsigned WhichSucc = CaseVal.getSuccessorIndex();
+      // Calculate whether our single reachable edge is really a single edge to
+      // the target block.  If not, and the block has multiple predecessors, we
+      // can only replace phi node values.
+      for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
+        if (i == WhichSucc)
+          continue;
+        BasicBlock *Block = SI->getSuccessor(i);
+        if (Block == TargetBlock)
+          MultipleEdgesOneReachable = true;
+      }
+    } else {
+      for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
+        BasicBlock *TargetBlock = SI->getSuccessor(i);
+        ++SwitchEdges[TargetBlock];
+        updateReachableEdge(B, TargetBlock);
+      }
+    }
+  } else {
+    // Otherwise this is either unconditional, or a type we have no
+    // idea about. Just mark successors as reachable.
+    for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
+      BasicBlock *TargetBlock = TI->getSuccessor(i);
+      updateReachableEdge(B, TargetBlock);
+    }
+  }
+}
+
+// The algorithm initially places the values of the routine in the INITIAL congruence
+// class. The leader of INITIAL is the undetermined value `TOP`.
+// When the algorithm has finished, values still in INITIAL are unreachable.
+void NewGVN::initializeCongruenceClasses(Function &F) {
+  // FIXME now i can't remember why this is 2
+  NextCongruenceNum = 2;
+  // Initialize all other instructions to be in INITIAL class.
+  CongruenceClass::MemberSet InitialValues;
+  for (auto &B : F)
+    for (auto &I : B)
+      InitialValues.insert(&I);
+
+  InitialClass = createCongruenceClass(NULL, NULL);
+  for (auto L : InitialValues)
+    ValueToClass[L] = InitialClass;
+  InitialClass->Members.swap(InitialValues);
+
+  // Initialize arguments to be in their own unique congruence classes
+  for (auto &FA : F.args())
+    createSingletonCongruenceClass(&FA);
+}
+
+void NewGVN::cleanupTables() {
+#ifndef NDEBUG
+  for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
+    DEBUG(dbgs() << "Congruence class " << CongruenceClasses[i]->ID << " has "
+                 << CongruenceClasses[i]->Members.size() << " members\n");
+  }
+#endif
+
+  ValueToClass.clear();
+  ArgRecycler.clear(ExpressionAllocator);
+  ExpressionAllocator.Reset();
+  CongruenceClasses.clear();
+  ExpressionToClass.clear();
+  ValueToExpression.clear();
+  ReachableBlocks.clear();
+  ReachableEdges.clear();
+  ProcessedCount.clear();
+  DFSDomMap.clear();
+  InstrDFS.clear();
+  InstructionsToErase.clear();
+
+  DFSToInstr.clear();
+  BlockInstRange.clear();
+  TouchedInstructions.clear();
+  DominatedInstRange.clear();
+}
+
+std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
+                                                       unsigned Start) {
+  unsigned End = Start;
+  for (auto &I : *B) {
+    InstrDFS[&I] = End++;
+    DFSToInstr.emplace_back(&I);
+  }
+
+  // All of the range functions taken half-open ranges (open on the end side).
+  // So we do not subtract one from count, because at this point it is one
+  // greater than the last instruction.
+  return std::make_pair(Start, End);
+}
+
+void NewGVN::updateProcessedCount(Value *V) {
+#ifndef NDEBUG
+  if (ProcessedCount.count(V) == 0) {
+    ProcessedCount.insert({V, 1});
+  } else {
+    ProcessedCount[V] += 1;
+    assert(ProcessedCount[V] < 100 &&
+           "Seem to have processed the same Value a lot\n");
+  }
+#endif
+}
+
+// runOnFunction - This is the main transformation entry point for a function.
+bool NewGVN::runGVN(Function &F, DominatorTree *DT, AssumptionCache *AC,
+                   TargetLibraryInfo *TLI, AliasAnalysis *AA,
+                   MemorySSA *MSSA) {
+  bool Changed = false;
+  this->DT = DT;
+  this->AC = AC;
+  this->TLI = TLI;
+  this->AA = AA;
+  this->MSSA = MSSA;
+  DL = &F.getParent()->getDataLayout();
+  MSSAWalker = MSSA->getWalker();
+
+  // Count number of instructions for sizing of hash tables, and come
+  // up with a global dfs numbering for instructions.
+  unsigned ICount = 0;
+  SmallPtrSet<BasicBlock *, 16> VisitedBlocks;
+
+  // Note: We want RPO traversal of the blocks, which is not quite the same as
+  // dominator tree order, particularly with regard whether backedges get
+  // visited first or second, given a block with multiple successors.
+  // If we visit in the wrong order, we will end up performing N times as many
+  // iterations.
+  ReversePostOrderTraversal<Function *> RPOT(&F);
+  for (auto &B : RPOT) {
+    VisitedBlocks.insert(B);
+    const auto &BlockRange = assignDFSNumbers(B, ICount);
+    BlockInstRange.insert({B, BlockRange});
+    ICount += BlockRange.second - BlockRange.first;
+  }
+
+  // Handle forward unreachable blocks and figure out which blocks
+  // have single preds.
+  for (auto &B : F) {
+    // Assign numbers to unreachable blocks.
+    if (!VisitedBlocks.count(&B)) {
+      const auto &BlockRange = assignDFSNumbers(&B, ICount);
+      BlockInstRange.insert({&B, BlockRange});
+      ICount += BlockRange.second - BlockRange.first;
+    }
+  }
+
+  TouchedInstructions.resize(ICount + 1);
+  DominatedInstRange.reserve(F.size());
+  // Ensure we don't end up resizing the expressionToClass map, as
+  // that can be quite expensive. At most, we have one expression per
+  // instruction.
+  ExpressionToClass.reserve(ICount + 1);
+
+  // Initialize the touched instructions to include the entry block.
+  const auto &InstRange = BlockInstRange.lookup(&F.getEntryBlock());
+  TouchedInstructions.set(InstRange.first, InstRange.second);
+  ReachableBlocks.insert(&F.getEntryBlock());
+
+  initializeCongruenceClasses(F);
+
+  // We start out in the entry block.
+  BasicBlock *LastBlock = &F.getEntryBlock();
+  while (TouchedInstructions.any()) {
+    // Walk through all the instructions in all the blocks in RPO.
+    for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
+         InstrNum = TouchedInstructions.find_next(InstrNum)) {
+      Instruction *I = DFSToInstr[InstrNum];
+      BasicBlock *CurrBlock = I->getParent();
+
+      // If we hit a new block, do reachability processing.
+      if (CurrBlock != LastBlock) {
+        LastBlock = CurrBlock;
+        bool BlockReachable = ReachableBlocks.count(CurrBlock);
+        const auto &InstRange = BlockInstRange.lookup(CurrBlock);
+
+        // If it's not reachable, erase any touched instructions and move on.
+        if (!BlockReachable) {
+          TouchedInstructions.reset(InstRange.first, InstRange.second);
+          DEBUG(dbgs() << "Skipping instructions in block "
+                       << getBlockName(CurrBlock)
+                       << " because it is unreachable\n");
+          continue;
+        }
+        updateProcessedCount(CurrBlock);
+      }
+      DEBUG(dbgs() << "Processing instruction " << *I << "\n");
+      if (I->use_empty() && !I->getType()->isVoidTy()) {
+        DEBUG(dbgs() << "Skipping unused instruction\n");
+        if (isInstructionTriviallyDead(I, TLI))
+          markInstructionForDeletion(I);
+        TouchedInstructions.reset(InstrNum);
+        continue;
+      }
+      updateProcessedCount(I);
+
+      if (!I->isTerminator()) {
+        const Expression *Symbolized = performSymbolicEvaluation(I, CurrBlock);
+        performCongruenceFinding(I, Symbolized);
+      } else {
+        processOutgoingEdges(dyn_cast<TerminatorInst>(I), CurrBlock);
+      }
+      // Reset after processing (because we may mark ourselves as touched when
+      // we propagate equalities).
+      TouchedInstructions.reset(InstrNum);
+    }
+  }
+
+  Changed |= eliminateInstructions(F);
+
+  // Delete all instructions marked for deletion.
+  for (Instruction *ToErase : InstructionsToErase) {
+    if (!ToErase->use_empty())
+      ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
+
+    ToErase->eraseFromParent();
+  }
+
+  // Delete all unreachable blocks.
+  for (auto &B : F) {
+    BasicBlock *BB = &B;
+    if (!ReachableBlocks.count(BB)) {
+      DEBUG(dbgs() << "We believe block " << getBlockName(BB)
+                   << " is unreachable\n");
+      deleteInstructionsInBlock(BB);
+      Changed = true;
+    }
+  }
+
+  cleanupTables();
+  return Changed;
+}
+
+bool NewGVN::runOnFunction(Function &F) {
+  if (skipFunction(F))
+    return false;
+  return runGVN(F, &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+                &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F),
+                &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
+                &getAnalysis<AAResultsWrapperPass>().getAAResults(),
+                &getAnalysis<MemorySSAWrapperPass>().getMSSA());
+}
+
+PreservedAnalyses NewGVNPass::run(Function &F,
+                                  AnalysisManager<Function> &AM) {
+  NewGVN Impl;
+
+  // Apparently the order in which we get these results matter for
+  // the old GVN (see Chandler's comment in GVN.cpp). I'll keep
+  // the same order here, just in case.
+  auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+  auto &AA = AM.getResult<AAManager>(F);
+  auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
+  bool Changed = Impl.runGVN(F, &DT, &AC, &TLI, &AA, &MSSA);
+  if (!Changed)
+    return PreservedAnalyses::all();
+  PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<GlobalsAA>();
+  return PA;
+}
+
+// Return true if V is a value that will always be available (IE can
+// be placed anywhere) in the function.  We don't do globals here
+// because they are often worse to put in place.
+// TODO: Separate cost from availability
+static bool alwaysAvailable(Value *V) {
+  return isa<Constant>(V) || isa<Argument>(V);
+}
+
+//  Get the basic block from an instruction/value.
+static BasicBlock *getBlockForValue(Value *V) {
+  if (auto *I = dyn_cast<Instruction>(V))
+    return I->getParent();
+  return nullptr;
+}
+struct NewGVN::ValueDFS {
+  int DFSIn;
+  int DFSOut;
+  int LocalNum;
+  // Only one of these will be set.
+  Value *Val;
+  Use *U;
+  ValueDFS()
+      : DFSIn(0), DFSOut(0), LocalNum(0), Val(nullptr), U(nullptr) {}
+
+  bool operator<(const ValueDFS &other) const {
+    // It's not enough that any given field be less than - we have sets
+    // of fields that need to be evaluated together to give a proper ordering.
+    // For example, if you have;
+    // DFS (1, 3)
+    // Val 0
+    // DFS (1, 2)
+    // Val 50
+    // We want the second to be less than the first, but if we just go field
+    // by field, we will get to Val 0 < Val 50 and say the first is less than
+    // the second. We only want it to be less than if the DFS orders are equal.
+
+    if (DFSIn < other.DFSIn)
+      return true;
+    else if (DFSIn == other.DFSIn) {
+      if (DFSOut < other.DFSOut)
+        return true;
+      else if (DFSOut == other.DFSOut) {
+        if (LocalNum < other.LocalNum)
+          return true;
+        else if (LocalNum == other.LocalNum) {
+          if (Val < other.Val)
+            return true;
+          if (U < other.U)
+            return true;
+        }
+      }
+    }
+    return false;
+  }
+};
+
+void NewGVN::convertDenseToDFSOrdered(CongruenceClass::MemberSet &Dense,
+                                      std::vector<ValueDFS> &DFSOrderedSet) {
+  for (auto D : Dense) {
+    // First add the value.
+    BasicBlock *BB = getBlockForValue(D);
+    // Constants are handled prior to ever calling this function, so
+    // we should only be left with instructions as members.
+    assert(BB || "Should have figured out a basic block for value");
+    ValueDFS VD;
+
+    std::pair<int, int> DFSPair = DFSDomMap[BB];
+    assert(DFSPair.first != -1 && DFSPair.second != -1 && "Invalid DFS Pair");
+    VD.DFSIn = DFSPair.first;
+    VD.DFSOut = DFSPair.second;
+    VD.Val = D;
+    // If it's an instruction, use the real local dfs number.
+    if (auto *I = dyn_cast<Instruction>(D))
+      VD.LocalNum = InstrDFS[I];
+    else
+      llvm_unreachable("Should have been an instruction");
+
+    DFSOrderedSet.emplace_back(VD);
+
+    // Now add the users.
+    for (auto &U : D->uses()) {
+      if (auto *I = dyn_cast<Instruction>(U.getUser())) {
+        ValueDFS VD;
+        // Put the phi node uses in the incoming block.
+        BasicBlock *IBlock;
+        if (auto *P = dyn_cast<PHINode>(I)) {
+          IBlock = P->getIncomingBlock(U);
+          // Make phi node users appear last in the incoming block
+          // they are from.
+          VD.LocalNum = InstrDFS.size() + 1;
+        } else {
+          IBlock = I->getParent();
+          VD.LocalNum = InstrDFS[I];
+        }
+        std::pair<int, int> DFSPair = DFSDomMap[IBlock];
+        VD.DFSIn = DFSPair.first;
+        VD.DFSOut = DFSPair.second;
+        VD.U = &U;
+        DFSOrderedSet.emplace_back(VD);
+      }
+    }
+  }
+}
+
+static void patchReplacementInstruction(Instruction *I, Value *Repl) {
+  // Patch the replacement so that it is not more restrictive than the value
+  // being replaced.
+  auto *Op = dyn_cast<BinaryOperator>(I);
+  auto *ReplOp = dyn_cast<BinaryOperator>(Repl);
+
+  if (Op && ReplOp)
+    ReplOp->andIRFlags(Op);
+
+  if (auto *ReplInst = dyn_cast<Instruction>(Repl)) {
+    // FIXME: If both the original and replacement value are part of the
+    // same control-flow region (meaning that the execution of one
+    // guarentees the executation of the other), then we can combine the
+    // noalias scopes here and do better than the general conservative
+    // answer used in combineMetadata().
+
+    // In general, GVN unifies expressions over different control-flow
+    // regions, and so we need a conservative combination of the noalias
+    // scopes.
+    unsigned KnownIDs[] = {
+        LLVMContext::MD_tbaa,           LLVMContext::MD_alias_scope,
+        LLVMContext::MD_noalias,        LLVMContext::MD_range,
+        LLVMContext::MD_fpmath,         LLVMContext::MD_invariant_load,
+        LLVMContext::MD_invariant_group};
+    combineMetadata(ReplInst, I, KnownIDs);
+  }
+}
+
+static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
+  patchReplacementInstruction(I, Repl);
+  I->replaceAllUsesWith(Repl);
+}
+
+void NewGVN::deleteInstructionsInBlock(BasicBlock *BB) {
+  DEBUG(dbgs() << "  BasicBlock Dead:" << *BB);
+  ++NumGVNBlocksDeleted;
+
+  // Check to see if there are non-terminating instructions to delete.
+  if (isa<TerminatorInst>(BB->begin()))
+    return;
+
+  // Delete the instructions backwards, as it has a reduced likelihood of having
+  // to update as many def-use and use-def chains. Start after the terminator.
+  auto StartPoint = BB->rbegin();
+  ++StartPoint;
+  // Note that we explicitly recalculate BB->rend() on each iteration,
+  // as it may change when we remove the first instruction.
+  for (BasicBlock::reverse_iterator I(StartPoint); I != BB->rend();) {
+    Instruction &Inst = *I++;
+    if (!Inst.use_empty())
+      Inst.replaceAllUsesWith(UndefValue::get(Inst.getType()));
+    if (isa<LandingPadInst>(Inst))
+      continue;
+
+    Inst.eraseFromParent();
+    ++NumGVNInstrDeleted;
+  }
+}
+
+void NewGVN::markInstructionForDeletion(Instruction *I) {
+  DEBUG(dbgs() << "Marking " << *I << " for deletion\n");
+  InstructionsToErase.insert(I);
+}
+
+void NewGVN::replaceInstruction(Instruction *I, Value *V) {
+
+  DEBUG(dbgs() << "Replacing " << *I << " with " << *V << "\n");
+  patchAndReplaceAllUsesWith(I, V);
+  // We save the actual erasing to avoid invalidating memory
+  // dependencies until we are done with everything.
+  markInstructionForDeletion(I);
+}
+
+namespace {
+
+// This is a stack that contains both the value and dfs info of where
+// that value is valid.
+class ValueDFSStack {
+public:
+  Value *back() const { return ValueStack.back(); }
+  std::pair<int, int> dfs_back() const { return DFSStack.back(); }
+
+  void push_back(Value *V, int DFSIn, int DFSOut) {
+    ValueStack.emplace_back(V);
+    DFSStack.emplace_back(DFSIn, DFSOut);
+  }
+  bool empty() const { return DFSStack.empty(); }
+  bool isInScope(int DFSIn, int DFSOut) const {
+    if (empty())
+      return false;
+    return DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second;
+  }
+
+  void popUntilDFSScope(int DFSIn, int DFSOut) {
+
+    // These two should always be in sync at this point.
+    assert(ValueStack.size() == DFSStack.size() &&
+           "Mismatch between ValueStack and DFSStack");
+    while (
+        !DFSStack.empty() &&
+        !(DFSIn >= DFSStack.back().first && DFSOut <= DFSStack.back().second)) {
+      DFSStack.pop_back();
+      ValueStack.pop_back();
+    }
+  }
+
+private:
+  SmallVector<Value *, 8> ValueStack;
+  SmallVector<std::pair<int, int>, 8> DFSStack;
+};
+}
+
+bool NewGVN::eliminateInstructions(Function &F) {
+  // This is a non-standard eliminator. The normal way to eliminate is
+  // to walk the dominator tree in order, keeping track of available
+  // values, and eliminating them.  However, this is mildly
+  // pointless. It requires doing lookups on every instruction,
+  // regardless of whether we will ever eliminate it.  For
+  // instructions part of most singleton congruence class, we know we
+  // will never eliminate it.
+
+  // Instead, this eliminator looks at the congruence classes directly, sorts
+  // them into a DFS ordering of the dominator tree, and then we just
+  // perform eliminate straight on the sets by walking the congruence
+  // class member uses in order, and eliminate the ones dominated by the
+  // last member.   This is technically O(N log N) where N = number of
+  // instructions (since in theory all instructions may be in the same
+  // congruence class).
+  // When we find something not dominated, it becomes the new leader
+  // for elimination purposes
+
+  bool AnythingReplaced = false;
+
+  // Since we are going to walk the domtree anyway, and we can't guarantee the
+  // DFS numbers are updated, we compute some ourselves.
+  DT->updateDFSNumbers();
+
+  for (auto &B : F) {
+    if (!ReachableBlocks.count(&B)) {
+      for (const auto S : successors(&B)) {
+        for (auto II = S->begin(); isa<PHINode>(II); ++II) {
+          PHINode &Phi = cast<PHINode>(*II);
+          DEBUG(dbgs() << "Replacing incoming value of " << *II << " for block "
+                       << getBlockName(&B)
+                       << " with undef due to it being unreachable\n");
+          for (auto &Operand : Phi.incoming_values())
+            if (Phi.getIncomingBlock(Operand) == &B)
+              Operand.set(UndefValue::get(Phi.getType()));
+        }
+      }
+    }
+    DomTreeNode *Node = DT->getNode(&B);
+    if (Node)
+      DFSDomMap[&B] = {Node->getDFSNumIn(), Node->getDFSNumOut()};
+  }
+
+  for (unsigned i = 0, e = CongruenceClasses.size(); i != e; ++i) {
+    CongruenceClass *CC = CongruenceClasses[i];
+
+    // FIXME: We should eventually be able to replace everything still
+    // in the initial class with undef, as they should be unreachable.
+    // Right now, initial still contains some things we skip value
+    // numbering of (UNREACHABLE's, for example).
+    if (CC == InitialClass || CC->Dead)
+      continue;
+    assert(CC->RepLeader && "We should have had a leader");
+
+    // If this is a leader that is always available, and it's a
+    // constant or has no equivalences, just replace everything with
+    // it. We then update the congruence class with whatever members
+    // are left.
+    if (alwaysAvailable(CC->RepLeader)) {
+      SmallPtrSet<Value *, 4> MembersLeft;
+      for (auto M : CC->Members) {
+
+        Value *Member = M;
+
+        // Void things have no uses we can replace.
+        if (Member == CC->RepLeader || Member->getType()->isVoidTy()) {
+          MembersLeft.insert(Member);
+          continue;
+        }
+
+        DEBUG(dbgs() << "Found replacement " << *(CC->RepLeader) << " for "
+                     << *Member << "\n");
+        // Due to equality propagation, these may not always be
+        // instructions, they may be real values.  We don't really
+        // care about trying to replace the non-instructions.
+        if (auto *I = dyn_cast<Instruction>(Member)) {
+          assert(CC->RepLeader != I &&
+                 "About to accidentally remove our leader");
+          replaceInstruction(I, CC->RepLeader);
+          AnythingReplaced = true;
+
+          continue;
+        } else {
+          MembersLeft.insert(I);
+        }
+      }
+      CC->Members.swap(MembersLeft);
+
+    } else {
+      DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n");
+      // If this is a singleton, we can skip it.
+      if (CC->Members.size() != 1) {
+
+        // This is a stack because equality replacement/etc may place
+        // constants in the middle of the member list, and we want to use
+        // those constant values in preference to the current leader, over
+        // the scope of those constants.
+        ValueDFSStack EliminationStack;
+
+        // Convert the members to DFS ordered sets and then merge them.
+        std::vector<ValueDFS> DFSOrderedSet;
+        convertDenseToDFSOrdered(CC->Members, DFSOrderedSet);
+
+        // Sort the whole thing.
+        sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
+
+        for (auto &C : DFSOrderedSet) {
+          int MemberDFSIn = C.DFSIn;
+          int MemberDFSOut = C.DFSOut;
+          Value *Member = C.Val;
+          Use *MemberUse = C.U;
+
+          // We ignore void things because we can't get a value from them.
+          if (Member && Member->getType()->isVoidTy())
+            continue;
+
+          if (EliminationStack.empty()) {
+            DEBUG(dbgs() << "Elimination Stack is empty\n");
+          } else {
+            DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
+                         << EliminationStack.dfs_back().first << ","
+                         << EliminationStack.dfs_back().second << ")\n");
+          }
+          if (Member && isa<Constant>(Member))
+            assert(isa<Constant>(CC->RepLeader));
+
+          DEBUG(dbgs() << "Current DFS numbers are (" << MemberDFSIn << ","
+                       << MemberDFSOut << ")\n");
+          // First, we see if we are out of scope or empty.  If so,
+          // and there equivalences, we try to replace the top of
+          // stack with equivalences (if it's on the stack, it must
+          // not have been eliminated yet).
+          // Then we synchronize to our current scope, by
+          // popping until we are back within a DFS scope that
+          // dominates the current member.
+          // Then, what happens depends on a few factors
+          // If the stack is now empty, we need to push
+          // If we have a constant or a local equivalence we want to
+          // start using, we also push.
+          // Otherwise, we walk along, processing members who are
+          // dominated by this scope, and eliminate them.
+          bool ShouldPush =
+              Member && (EliminationStack.empty() || isa<Constant>(Member));
+          bool OutOfScope =
+              !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut);
+
+          if (OutOfScope || ShouldPush) {
+            // Sync to our current scope.
+            EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
+            ShouldPush |= Member && EliminationStack.empty();
+            if (ShouldPush) {
+              EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
+            }
+          }
+
+          // If we get to this point, and the stack is empty we must have a use
+          // with nothing we can use to eliminate it, just skip it.
+          if (EliminationStack.empty())
+            continue;
+
+          // Skip the Value's, we only want to eliminate on their uses.
+          if (Member)
+            continue;
+          Value *Result = EliminationStack.back();
+
+          // Don't replace our existing users with ourselves.
+          if (MemberUse->get() == Result)
+            continue;
+
+          DEBUG(dbgs() << "Found replacement " << *Result << " for "
+                       << *MemberUse->get() << " in " << *(MemberUse->getUser())
+                       << "\n");
+
+          // If we replaced something in an instruction, handle the patching of
+          // metadata.
+          if (auto *ReplacedInst =
+                  dyn_cast<Instruction>(MemberUse->get()))
+            patchReplacementInstruction(ReplacedInst, Result);
+
+          assert(isa<Instruction>(MemberUse->getUser()));
+          MemberUse->set(Result);
+          AnythingReplaced = true;
+        }
+      }
+    }
+
+    // Cleanup the congruence class.
+    SmallPtrSet<Value *, 4> MembersLeft;
+    for (auto MI = CC->Members.begin(), ME = CC->Members.end(); MI != ME;) {
+      auto CurrIter = MI;
+      ++MI;
+      Value *Member = *CurrIter;
+      if (Member->getType()->isVoidTy()) {
+        MembersLeft.insert(Member);
+        continue;
+      }
+
+      if (auto *MemberInst = dyn_cast<Instruction>(Member)) {
+        if (isInstructionTriviallyDead(MemberInst)) {
+          // TODO: Don't mark loads of undefs.
+          markInstructionForDeletion(MemberInst);
+          continue;
+        }
+      }
+      MembersLeft.insert(Member);
+    }
+    CC->Members.swap(MembersLeft);
+  }
+
+  return AnythingReplaced;
+}
+

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCELegacyPassPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeScalarizerPass(Registry);
   initializeDSELegacyPassPass(Registry);
   initializeGuardWideningLegacyPassPass(Registry);
   initializeGVNLegacyPassPass(Registry);
+  initializeNewGVNPass(Registry);
   initializeEarlyCSELegacyPassPass(Registry);
   initializeEarlyCSEMemSSALegacyPassPass(Registry);
   initializeGVNHoistLegacyPassPass(Registry);
   initializeFlattenCFGPassPass(Registry);
   initializeInductiveRangeCheckEliminationPass(Registry);
   initializeIndVarSimplifyLegacyPassPass(Registry);
   initializeJumpThreadingPass(Registry);
   initializeLegacyLICMPassPass(Registry);

 void LLVMAddScalarizerPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createScalarizerPass());
 }
 
 void LLVMAddGVNPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createGVNPass());
 }
 
+void LLVMAddNewGVNPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createNewGVNPass());
+}
+
 void LLVMAddMergedLoadStoreMotionPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createMergedLoadStoreMotionPass());
 }
 
 void LLVMAddIndVarSimplifyPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createIndVarSimplifyPass());
 }