[EarlyCSE] Optionally use MemorySSA. NFC.

[gberry]

Summary

Use MemorySSA, if requested, to do less conservative memory dependency checking.

This change doesn't enable the MemorySSA enhanced EarlyCSE in the default pipelines, so should be NFC.

[mcrosier]

A few nits in passing.

lib/Transforms/Scalar/EarlyCSE.cpp

306–307

Can this be committed as a separate change?

563

Please capitalize handle and add a period.

574

Please add a descriptive && "Error message!".

760–762

Separate commit.

776

Separate commit. Maybe typdef?

[reames]

At a meta level, I'm not convinced that updating EarlyCSE to work with MemorySSA is the right approach. EarlyCSE is focused on being really really fast at cleaning up stupidly redundant IR so that the rest of the pass pipeline doesn't need to worry about it. MemorySSA is relatively expensive to construct. Given that, I'm really not sure putting it at the very beginning of the pipeline is a good design choice.

Now, having said that, it might make sense to have a dominance order CSE pass based on MemorySSA for use later in the pass pipeline. Currently we use EarlyCSE for two distinct purposes, its possible that it might be time to split them.

Can you justify why this is the right approach?

lib/Transforms/Scalar/EarlyCSE.cpp

504

Huh? This should be handled entirely inside MemorySSA?

555

Having two sets of variables, one integers, one pointers with similar names is *highly* confusing. I'd suggest pulling out a MemorySSA specific impl function and calling it from here to wrap the desired asserts.

563

This comment doesn't make sense where placed?

674

Code like this strongly hints that MemorySSA should be using ValueHandles.

test/Transforms/EarlyCSE/memoryssa.ll

8

If we do go this way, you'll need far far more tests.

[• dberlin]

So, if it's not actually slower in practice, would that address your
objection

[• dberlin]

In particular, i'm trying to understand if your concerns are *mostly* "we
want to keep this fast", or broader than that.
If they are broader than that, i'd like to understand the objection.
Because the speed one is simply "either we can make it fast enough or we
can't" (and i agree if we can't we shouldn't do it :P)

[gberry]

Update based on reames review feedback

[gberry]

@reames I've attempted to resolved most of your individual concerns (or at least made them explicit in the change). The bigger question of whether this is worth the compile time remains to be determined. Do you think more tests need to be added in addition to the already existing EarlyCSE tests? Adding additional run lines to those tests to enable -early-cse-use-memoryssa seems like overkill to me, but I don't feel to strongly about it. Or are you more concerned about adding new tests for cases that are only caught by MemorySSA (both positive and negative)?

@dberlin, @george.burgess.iv There are a couple of FIXME comments in this change that identify cases where MemorySSA is maybe being too conservative (e.g. when dealing with fence release instructions and load atomic instructions). Do you think it is reasonable to refine these cases in MemorySSA or is the conservatism restricted to EarlyCSE's usage, in which case we should deal with it in EarlyCSE? Similarly, what do you think of Phillip's suggestion to look at using ValueHandles in MemorySSA to make removal invalidating more automated?

[gberry]

@reames @dberlin Regarding the compile time impact, do you think it would be worth pursuing a change to make EarlyCSE's use of MemorySSA optional? That way we could avoid using it for early passes EarlyCSE and only use it for later ones, perhaps even influenced by optimization level? A related aspect of the plan for MemorySSA that I'd like to understand is how well we think we'll be able to amortize the cost of building it by preserving/maintaining it across passes. Daniel, can you share your thoughts on that?

[• dberlin]

So, i would like to see real numbers that say this is going to slow down
anything (or speed it up).
As I said, if the objection is speed, yes, we should look into that, and if
something needs to be done, we should do it.

We can amortize the cost quite well. It should essentially cost nearly
nothing past initial setup cost (it's not harder than the SSA updates we do
today, which are not expensive).

The entire plan is actually to amortize the cost.
Right now, the default pass schedules put things that use memdep mostly in
a row.

At the outset, with a little work, we should have to compute memoryssa
twice (once before MLSM/GVN/MemCpyOpt, once before DSE).
Getting all the way to DSE is harder in the sense that it's a longer way to
go to preserve passes.

But it's also interesting to note that none of these passes preserve memdep
today, and the cost of doing memdep queries on every store (as DSE would)
with no cache, should be more than the cost of memoryssa building + usage.

It definitely can be made to be so.
So that part doesn't worry me.

Shoving this in EarlyCSE, if it's fast enough, seems reasonable at a
glance. In a perfect world, it would be good to preserve it everywhere.
I'm not sure, at the beginning, it makes sense to try to preserve it across
tons and tons of passes that won't ever use it, but do touch memory
heavily. So i would expect EarlyCSE to end up as another computation point
for quite a while.

That needs to be traded off past how much better/easier/etc it makes
EarlyCSE.

[gberry]

Update to use MemorySSA in EarlyCSE if it is available, and make it
available for -O3 or greater in first EarlyCSE pass added by
addFunctionSimplificationPasses().

[gberry]

Compile time test for the llvm test suite on aarch64 (at -O3) were mostly a wash, some faster, some slower, no big outliers. The net change was slightly better compile times.

Notable performance improvements (no significant regressions):
MultiSource/Benchmarks/Trimaran/enc-md5/enc-md5 -6%
MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1 -5%
MultiSource/Benchmarks/sim/sim -3%
SingleSource/Benchmarks/McGill/chomp -4%
MultiSource/Benchmarks/Ptrdist/anagram/anagram -2%
spec2000/bzip2 -10%

@reames I've added some additional lit test coverage, is there more lit test coverage you'd like to see?

[bruno]

Hi Geoff, what are the numbers of the top slower ones?

[• dberlin]

I'm also interested.
We already know of some performance issues related to caching and use
optimization with weird testcases (many many nested blocks) that we are
fixing.
If we have significant perf regressions, it would be useful if for no other
reason than to inform the stuff george is taking a look at.

[gberry]

Here are the worst llvm test-suite compile time regressions. I've filtered out the very small test cases. The data shown are the percent diffs of compile times from 5 different runs with and without the above change.

llvm-test-suite/SingleSource/Benchmarks/Misc/ffbench:normal PASS +1.079%, +2.837%, +17.951%, +21.615%, +33.206%
llvm-test-suite/SingleSource/Benchmarks/Shootout-C++/shootout-cxx-moments:normal PASS +1.148%, +9.801%, +14.607%, +15.686%, +19.707%
llvm-test-suite/MultiSource/Applications/spiff/spiff:normal PASS -0.773%, +2.938%, +13.511%, +16.846%, +21.552%
llvm-test-suite/SingleSource/Benchmarks/Shootout-C++/shootout-cxx-nestedloop:normal PASS -1.623%, +1.635%, +12.996%, +13.561%, +14.354%
llvm-test-suite/MultiSource/Benchmarks/Prolangs-C++/garage/garage:normal PASS +1.092%, +8.865%, +12.830%, +14.206%, +15.722%
llvm-test-suite/MultiSource/Benchmarks/TSVC/IndirectAddressing-dbl/IndirectAddressing-dbl:normal PASS +4.676%, +5.196%, +10.725%, +12.248%, +12.967%
llvm-test-suite/MultiSource/Benchmarks/MallocBench/espresso/espresso:normal PASS -2.227%, +4.387%, +9.187%, +11.195%, +13.738%
llvm-test-suite/MultiSource/Benchmarks/BitBench/uuencode/uuencode:normal PASS -0.223%, +3.068%, +7.235%, +9.723%, +18.255%
llvm-test-suite/SingleSource/Benchmarks/Misc-C++/stepanov_container:normal PASS +1.185%, +2.054%, +4.369%, +8.627%, +11.474%
llvm-test-suite/MultiSource/Benchmarks/Prolangs-C++/family/family:normal PASS +1.386%, +1.767%, +4.300%, +10.017%, +19.309%
llvm-test-suite/MultiSource/Benchmarks/mediabench/adpcm/rawcaudio/rawcaudio:normal PASS +1.995%, +2.907%, +3.697%, +12.124%, +12.976%
llvm-test-suite/SingleSource/Benchmarks/Dhrystone/fldry:normal PASS +1.920%, +2.027%, +2.843%, +14.746%, +14.803%
llvm-test-suite/MultiSource/Benchmarks/tramp3d-v4/tramp3d-v4:normal PASS +1.305%, +1.674%, +2.269%, +2.961%, +9.660%

[• dberlin]

This looks super noisy even at 5 runs :)

[gberry]

@dberlin Yeah, I'm in the process of double checking some of these to make sure my testing methodology was sound.

[gberry]

Updated llvm-test-suite compile time regressions using LNT methodology:
llvm-test-suite/SingleSource/Benchmarks/Misc/flops-6 +4.019%
llvm-test-suite/SingleSource/Benchmarks/Adobe-C++/simple_types_constant_folding +4.967%
llvm-test-suite/SingleSource/Benchmarks/Polybench/medley/reg_detect/reg_detect +5.268%
llvm-test-suite/SingleSource/UnitTests/Vectorizer/gcc-loops +5.538%

[bruno]

Looks like the affected benchmarks changed in the new measurements, does that hold for performance improvements as well?

[• dberlin]

George, can you stare at these quickly and see if any of your caching
changes/etc will help?

(It's fine if not, just trying to avoid duplicating work)

[gberry]

In D19821#462310, @bruno wrote:

Looks like the affected benchmarks changed in the new measurements, does that hold for performance improvements as well?

I don't have that data yet, I'll update when I do.

[george.burgess.iv]

George, can you stare at these quickly and see if any of your caching changes/etc will help?

That depends on what exactly is slowing the benchmarks down so much. If our usage pattern is query -> remove -> query -> remove, then our cache may become useless, since (worst case) we drop the entire thing on each removal. If we primarily query defs, then this pattern gives us the same effectively-n^2 behavior of MemDep. One of the big goals of the new cache/walker is to allow us to drop as little as possible.

In terms of pure walker/cache speed, the current walker is happy to do a lot of potentially useless work walking phis we can't optimize; the one I'm working on will do as little work as possible in that case. Also, the current walker potentially does a lot of domtree queries when caching results, whereas the one I'm working on does none (except in asserts). Glancing at some of the benchmarks, I'm not sure if any of that is what's slowing us down here, though.

If you'd like, I'm happy to profile/poke around and give you a more definitive answer.

lib/Transforms/Scalar/EarlyCSE.cpp

500

Nit: Please use ///

571

Nit: return EarlierHeapGen == LaterHeapGen?

[gberry]

In D19821#462327, @gberry wrote:

In D19821#462310, @bruno wrote:

Looks like the affected benchmarks changed in the new measurements, does that hold for performance improvements as well?

I don't have that data yet, I'll update when I do.

The performance changes are mostly the same. Updated perf data (this is on an A57-like OoO aarch64 core, time deltas (negative is better)):
llvm-test-suite/SingleSource/Benchmarks/CoyoteBench/fftbench -21.811%, -21.633%, -21.488%, -21.074%, -20.747%, -20.168%, -20.084%, -18.987%, -18.615%, -18.487%
llvm-test-suite/MultiSource/Benchmarks/Trimaran/enc-md5/enc-md5 -6.557%, -6.557%, -6.557%, -6.077%, -6.077%, -5.525%, -5.525%, -5.525%, -5.525%, -5.000%
llvm-test-suite/MultiSource/Benchmarks/Trimaran/enc-pc1/enc-pc1 -3.306%, -3.306%, -3.306%, -2.479%, -2.479%, -2.479%, -2.479%, -2.479%, -1.681%, -1.667%
llvm-test-suite/MultiSource/Benchmarks/Prolangs-C/gnugo/gnugo -25.000%, -12.500%, -12.500%, -12.500%, -12.500%, -12.500%, +0.000%, +0.000%, +0.000%, +0.000%
llvm-test-suite/MultiSource/Benchmarks/sim/sim -12.815%, -2.667%, -2.667%, -2.400%, -1.872%, -1.114%, -1.111%, -1.070%, -1.067%, -1.067%
llvm-test-suite/MultiSource/Benchmarks/MallocBench/cfrac/cfrac -2.426%, -2.162%, -1.729%, -1.445%, -1.124%, -1.124%, -1.124%, -1.124%, -1.124%, -0.845%

llvm-test-suite/MultiSource/Benchmarks/mafft/pairlocalalign +0.399%, +0.430%, +0.458%, +0.507%, +0.593%, +0.626%, +0.778%, +1.097%, +1.195%, +1.309%

[gberry]

Update to address George's comments

[gberry]

I re-ran the llvm test-suite compile-time numbers with more samples and found no significant changes (improvements or regressions) in compile time.

[gberry]

I've put this on hold until I can re-run compile-time numbers after George's changes to the MemorySSA caching code go in (http://reviews.llvm.org/D21777)

[reames]

Sorry for not responding to this for so long.

My objection is primarily from a compile time concern. Right now, EarlyCSE is a *very* cheap pass to run. If you can keep it fast (even when we have to reconstruct MemorySSA) I don't object to having EarlyCSE MemorySSA based. I think that is a very hard bar to pass in practice. In particular, the bar is not total O3 time. It's EarlyCSE time. I fully expect that the more precise analysis may speed up other passes, but we can't assume that happens for all inputs. (As I write this, I'm recognizing that this might be too high a bar to set. If you think I'm being unreasonable, argue why and what a better line should be.)

Given I'm not going to have time to be active involved in this thread, I'm going to defer to other reviewers. If they think this is a good idea, I will not actively block the thread.

[reames]

p.s. The newer structure of using the original fast path check with memory ssa as a backup which is optional if available is much cleaner than the original code. I'm okay with something like this landing (once other reviewers have signed off) even if the compile time question isn't fully resolved provided that the force memory SSA pass is under an off by default option. As structured, this doesn't complicate the existing code much at all.

[gberry]

New version that adds a pass parameter to control whether MemorySSA is used.

Also changed the memory generation check to do a simpler MemorySSA
dominance check.

[gberry]

I've collected some compile time stats when enabling MemorySSA EarlyCSE just for the EarlyCSE pass added at the beginning of addFunctionSimplificationPasses at O2 and higher.
There were 8 benchmarks in the llvm test-suite whose compile time increased by more than 1%. The biggest increase was in consumer-typeset. Drilling down a bit, the MemorySSA construction time for compiling the z44.c input to this benchmark is reported as 2% of runtime.

[• dberlin]

lib/Transforms/Scalar/EarlyCSE.cpp

532

1. For loads, you don't have to ask for the clobbering access. It's already optimized such that getDefiningAccess == the clobbering access

2. For stores, not sure if you realize this, but

given
store q (lets's call this a)
x = load p
store q (let's call this b)

if you call getClobberingMemoryAccess on b, it will return a.

[gberry]

lib/Transforms/Scalar/EarlyCSE.cpp

532

For 1., I was not clear on whether this holds true after store removal.

For 2., yeah I get this, I'm not sure what you're getting at though. The removal of this second store by EarlyCSE doesn't use MemorySSA to check for intervening loads in this change. It uses the 'LastStore' tracking to know when a store made redundant by a second store can be removed.

[• dberlin]

lib/Transforms/Scalar/EarlyCSE.cpp

532

1. Updates have to make it hold after store removal :)

The problem is that if we don't keep this invariant up to date, it means everyone uses getClobberingAccess, which does a bunch of work to discover the load already points to the same thing.

Everyone doing that is much higher than the cost of one person updating the dominating def.

(there is one case were getClobberingAccess will give you a better answer, and that is on cases where we gave up during use optimization. I only have one testcase this occurs on. We only give up on optimizing a load if it's going to be super expensive, and you probably do *not* want to try to get better answers in that case).

As for updating when you remove stores, you should simply be able to replace any loads the store uses with getClobberingAccess(store) using RAUW.

Under the covers, removeMemoryAccess calls RAUW with the DefiningAccess.
We could change it to use getClobberingMemoryAccess for loads, and DefiningAccess for stores.

2. ah, okay.

[gberry]

lib/Transforms/Scalar/EarlyCSE.cpp

532

Okay, I get why just checking the defining access for loads is better (we get to skip the AA check).
For stores, we may be able to do something faster than calling getClobberingAccess(store). We could instead walk up the store defining access chain and stop if we get to a point that dominates the earlier load or a clobbering write. I'll have to time this to see if it makes a difference. I guess it will depend on what percentage of the time the clobber cache has been thrown away.

As for updating when removing stores: it seems like doing RAUW getClobberingAccess(store) is not optimal in some cases. For example:

store @G1 ; 1 = MD(entry)
store @G2 ; 2 = MD(1)
store %p ; 3 = MD(2)
load @G1 ; MU(3)
load @G2  ; MU(3)

If we remove 3 and RUAW getClobberingAccess(3) (=2) we get:

store @G1 ; 1 = MD(entry)
store @G2 ; 2 = MD(1)
load @G1 ; MU(2)
load @G2  ; MU(2)

but the load @G1 would be more precise if it was MU(1) (and the invariant that defining access == clobbering access would be broken). Is this just a compile-time/precision trade-off? Maybe for that reason it makes more sense to let the client decide if they want to do the simple RAUW getClobberingAccess(Store) or optimize each use separately?

[gberry]

Approved by @dberlin over email

include/llvm/LinkAllPasses.h

 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
 #include "llvm/Transforms/Utils/SymbolRewriter.h"
 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
 #include "llvm/Transforms/Vectorize.h"
 #include "llvm/Support/Valgrind.h"
 #include <cstdlib>
 
 namespace {
   struct ForcePassLinking {
ForcePassLinking() {
       (void) llvm::createLoopUnrollPass();
       (void) llvm::createLoopUnswitchPass();
       (void) llvm::createLoopVersioningLICMPass();
       (void) llvm::createLoopIdiomPass();
       (void) llvm::createLoopRotatePass();
       (void) llvm::createLowerExpectIntrinsicPass();
       (void) llvm::createLowerInvokePass();
       (void) llvm::createLowerSwitchPass();
+      (void) llvm::createMemorySSAPass();
       (void) llvm::createNaryReassociatePass();
       (void) llvm::createObjCARCAAWrapperPass();
       (void) llvm::createObjCARCAPElimPass();
       (void) llvm::createObjCARCExpandPass();
       (void) llvm::createObjCARCContractPass();
       (void) llvm::createObjCARCOptPass();
       (void) llvm::createPAEvalPass();
       (void) llvm::createPromoteMemoryToRegisterPass();

include/llvm/Transforms/Utils/MemorySSA.h

public:
 
   void verifyAnalysis() const override;
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 
 private:
   std::unique_ptr<MemorySSA> MSSA;
 };
 
+//===--------------------------------------------------------------------===//
+//
+// createMemorySSAPass - This pass builds memory SSA to allow walking memory
+// instructions using a use/def graph.
+//
+FunctionPass *createMemorySSAPass();
+
 /// \brief This is the generic walker interface for walkers of MemorySSA.
 /// Walkers are used to be able to further disambiguate the def-use chains
 /// MemorySSA gives you, or otherwise produce better info than MemorySSA gives
 /// you.
 /// In particular, while the def-use chains provide basic information, and are
 /// guaranteed to give, for example, the nearest may-aliasing MemoryDef for a
 /// MemoryUse as AliasAnalysis considers it, a user mant want better or other
 /// information. In particular, they may want to use SCEV info to further

lib/Transforms/IPO/PassManagerBuilder.cpp

 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/GVN.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
 #include "llvm/Transforms/Vectorize.h"
 
 using namespace llvm;
 
 static cl::opt<bool>
 RunLoopVectorization("vectorize-loops", cl::Hidden,
                      cl::desc("Run the Loop vectorization passes"));
 

 void PassManagerBuilder::addFunctionSimplificationPasses(
     legacy::PassManagerBase &MPM) {
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
     MPM.add(createSROAPass());
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
+  if (OptLevel > 2)
+    // Add MemorySSA to enhance memory dependency analysis in EarlyCSE.
+    MPM.add(createMemorySSAPass());
   MPM.add(createEarlyCSEPass());              // Catch trivial redundancies
   // Speculative execution if the target has divergent branches; otherwise nop.
   MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass());
   MPM.add(createJumpThreadingPass());         // Thread jumps.
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   // Combine silly seq's
   addInstructionCombiningPass(MPM);

lib/Transforms/Scalar/EarlyCSE.cpp

 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/RecyclingAllocator.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
 #include <deque>
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "early-cse"
 
 STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
 STATISTIC(NumCSE,      "Number of instructions CSE'd");

 /// cases so that instcombine and other passes are more effective. It is
 /// expected that a later pass of GVN will catch the interesting/hard cases.
 class EarlyCSE {
 public:
   const TargetLibraryInfo &TLI;
   const TargetTransformInfo &TTI;
   DominatorTree &DT;
   AssumptionCache &AC;
+  MemorySSA *MSSA;
   typedef RecyclingAllocator<
       BumpPtrAllocator, ScopedHashTableVal<SimpleValue, Value *>> AllocatorTy;
   typedef ScopedHashTable<SimpleValue, Value *, DenseMapInfo<SimpleValue>,
                           AllocatorTy> ScopedHTType;
 
   /// \brief A scoped hash table of the current values of all of our simple
   /// scalar expressions.
   ///
public:
   typedef ScopedHashTable<Value *, LoadValue, DenseMapInfo<Value *>,
                           LoadMapAllocator> LoadHTType;
   LoadHTType AvailableLoads;
 
   /// \brief A scoped hash table of the current values of read-only call
   /// values.
   ///
   /// It uses the same generation count as loads.
   typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
       CallHTType;
   CallHTType AvailableCalls;
 
   /// \brief This is the current generation of the memory value.
   unsigned CurrentGeneration;
 
   /// \brief Set up the EarlyCSE runner for a particular function.
   EarlyCSE(const TargetLibraryInfo &TLI, const TargetTransformInfo &TTI,
-           DominatorTree &DT, AssumptionCache &AC)
-      : TLI(TLI), TTI(TTI), DT(DT), AC(AC), CurrentGeneration(0) {}
+           DominatorTree &DT, AssumptionCache &AC, MemorySSA *MSSA)
+      : TLI(TLI), TTI(TTI), DT(DT), AC(AC), MSSA(MSSA), CurrentGeneration(0) {}
 
   bool run();
 
 private:
   // Almost a POD, but needs to call the constructors for the scoped hash
   // tables so that a new scope gets pushed on. These are RAII so that the
   // scope gets popped when the NodeScope is destroyed.
   class NodeScope {
Value *getOrCreateResult(Value *Inst, Type *ExpectedType) const {
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
       return LI;
     else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
       return SI->getValueOperand();
     assert(isa<IntrinsicInst>(Inst) && "Instruction not supported");
     return TTI.getOrCreateResultFromMemIntrinsic(cast<IntrinsicInst>(Inst),
                                                  ExpectedType);
   }
+
+  bool isSameMemGeneration(unsigned EarlierGeneration, unsigned LaterGeneration,
+                           Instruction *EarlierInst, Instruction *LaterInst);
+  bool isSameMemGenerationMemSSA(Instruction *EarlierInst,
+                                 Instruction *LaterInst);
+
+  void removeMSSA(Instruction *Inst) {
+    if (!MSSA)
+      return;
+    if (MemoryAccess *MA = MSSA->getMemoryAccess(Inst))
+      MSSA->removeMemoryAccess(MA);
+  }
 };
 }
 
+// Determine if the memory referenced by LaterInst is from the same heap version
+// as EarlierInst.
+// This is currently called in two scenarios:
+//
+//   load p
+//   ...
+//   load p
+//
+// and
+//
+//   x = load p
+//   ...
+//   store x, p
+//
+// in both cases we want to verify that there are no possible writes to the
+// memory referenced by p between the earlier and later instruction.
+bool EarlyCSE::isSameMemGeneration(unsigned EarlierGeneration,
+                                   unsigned LaterGeneration,
+                                   Instruction *EarlierInst,
+                                   Instruction *LaterInst) {
+  // Check the simple memory generation tracking first.
+  // FIXME: There are cases that the current implementation of MemorySSA/BasicAA
+  // won't catch but the simple memory generation tracking will.  One issue is
+  // that due to the decomposed GEP limit in BasicAA, some non-aliasing memory
+  // operations will show up as clobbers in MemorySSA due to BasicAA giving
+  // conservative results.
+  // FIXME: Another issue is the conservative way MemorySSA treats fence release
+  // instructions.  These will appear as MemoryClobbers for unordered stores,
+  // even though there is no ordering relationship between these two operations.
+
+  DEBUG(if (MSSA &&
+            !isSameMemGenerationMemSSA(EarlierInst, LaterInst) &&
+            EarlierGeneration == LaterGeneration)
+          dbgs() << "EarlyCSE: MemorySSA heap generation too conservative: "
+                 << EarlierInst->getFunction()->getName() << "\n"
+                 << "  " << *EarlierInst << "\n"
+                 << "  " << *LaterInst << "\n";);
+
+  if (EarlierGeneration == LaterGeneration)
+    return true;
+
+  return isSameMemGenerationMemSSA(EarlierInst, LaterInst);
+}
+
+bool EarlyCSE::isSameMemGenerationMemSSA(Instruction *EarlierInst,
+                                         Instruction *LaterInst) {
+  if (!MSSA)
+    return false;
+
+  MemorySSAWalker *MSSAWalker = MSSA->getWalker();
+
+  MemoryAccess *LaterHeapGen = MSSAWalker->getClobberingMemoryAccess(LaterInst);
+
+  if (MSSA->isLiveOnEntryDef(LaterHeapGen))
+    return true;
+
+  MemoryAccess *EarlierMA = MSSA->getMemoryAccess(EarlierInst);
+
+  // Handle cases like this:
+  //   x = load atomic, p
+  //   ... (no aliasing memory ops)
+  //   store unordered x, p
+  // In this case LaterHeapGen (i.e. the clobbering memory access for the store)
+  // is the atomic load (i.e. the EarlierInst MemoryAccess itself).
+  // FIXME: This may be better handled by having MemorySSA be less conservative
+  // when deciding if atomic loads should be clobbers or not.
+  if (LaterHeapGen == EarlierMA)
+    return true;
+
+  MemoryAccess *EarlierHeapGen =
+      MSSAWalker->getClobberingMemoryAccess(EarlierInst);
+  if (EarlierHeapGen == LaterHeapGen)
+    return true;
+
+  return false;
+}
+
 bool EarlyCSE::processNode(DomTreeNode *Node) {
   bool Changed = false;
   BasicBlock *BB = Node->getBlock();
 
   // If this block has a single predecessor, then the predecessor is the parent
   // of the domtree node and all of the live out memory values are still current
   // in this block.  If this block has multiple predecessors, then they could
   // have invalidated the live-out memory values of our parent value.  For now,
bool EarlyCSE::processNode(DomTreeNode *Node) {
   // See if any instructions in the block can be eliminated.  If so, do it.  If
   // not, add them to AvailableValues.
   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) {
     Instruction *Inst = &*I++;
 
     // Dead instructions should just be removed.
     if (isInstructionTriviallyDead(Inst, &TLI)) {
       DEBUG(dbgs() << "EarlyCSE DCE: " << *Inst << '\n');
+      removeMSSA(Inst);
       Inst->eraseFromParent();
       Changed = true;
       ++NumSimplify;
       continue;
     }
 
     // Skip assume intrinsics, they don't really have side effects (although
     // they're marked as such to ensure preservation of control dependencies),
if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
       continue;
     }
 
     // If the instruction can be simplified (e.g. X+0 = X) then replace it with
     // its simpler value.
     if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
       DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << "  to: " << *V << '\n');
       Inst->replaceAllUsesWith(V);
+      // This relies on SimplifyInstruction not removing any instructions that
+      // have MemoryAccesses.  It may make them dead, in which case they will
+      // get removed in the code above and MemorySSA updated correctly.
+      // FIXME: Perhaps MemorySSA should use ValueHandles?
+      removeMSSA(Inst);
       Inst->eraseFromParent();
       Changed = true;
       ++NumSimplify;
       continue;
     }
 
     // If this is a simple instruction that we can value number, process it.
     if (SimpleValue::canHandle(Inst)) {
       // See if the instruction has an available value.  If so, use it.
       if (Value *V = AvailableValues.lookup(Inst)) {
         DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << "  to: " << *V << '\n');
         if (auto *I = dyn_cast<Instruction>(V))
           I->andIRFlags(Inst);
         Inst->replaceAllUsesWith(V);
+        removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
         ++NumCSE;
         continue;
       }
 
       // Otherwise, just remember that this value is available.
       AvailableValues.insert(Inst, Inst);
       continue;
     }
 
     ParseMemoryInst MemInst(Inst, TTI);
     // If this is a non-volatile load, process it.
     if (MemInst.isValid() && MemInst.isLoad()) {
       // (conservatively) we can't peak past the ordering implied by this
       // operation, but we can add this load to our set of available values
       if (MemInst.isVolatile() || !MemInst.isUnordered()) {
         LastStore = nullptr;
         ++CurrentGeneration;
       }
 
       // If we have an available version of this load, and if it is the right
       // generation, replace this instruction.
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
-      if (InVal.DefInst != nullptr && InVal.Generation == CurrentGeneration &&
+      if (InVal.DefInst != nullptr &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing loads with ordering of any kind.
           !MemInst.isVolatile() && MemInst.isUnordered() &&
           // We can't replace an atomic load with one which isn't also atomic.
-          InVal.IsAtomic >= MemInst.isAtomic()) {
+          InVal.IsAtomic >= MemInst.isAtomic() &&
+          isSameMemGeneration(InVal.Generation, CurrentGeneration,
+                              InVal.DefInst, Inst)) {
         Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
         if (Op != nullptr) {
           DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
                        << "  to: " << *InVal.DefInst << '\n');
           if (!Inst->use_empty())
             Inst->replaceAllUsesWith(Op);
+          removeMSSA(Inst);
           Inst->eraseFromParent();
           Changed = true;
           ++NumCSELoad;
           continue;
         }
       }
 
       // Otherwise, remember that we have this instruction.
if (Inst->mayReadFromMemory() &&
         !(MemInst.isValid() && !MemInst.mayReadFromMemory()))
       LastStore = nullptr;
 
     // If this is a read-only call, process it.
     if (CallValue::canHandle(Inst)) {
       // If we have an available version of this call, and if it is the right
       // generation, replace this instruction.
       std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
-      if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
+      if (InVal.first != nullptr &&
+          isSameMemGeneration(InVal.second, CurrentGeneration, InVal.first,
+                              Inst)) {
         DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
                      << "  to: " << *InVal.first << '\n');
         if (!Inst->use_empty())
           Inst->replaceAllUsesWith(InVal.first);
+        removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
         ++NumCSECall;
         continue;
       }
 
       // Otherwise, remember that we have this instruction.
       AvailableCalls.insert(
           Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
       continue;
     }
 
     // A release fence requires that all stores complete before it, but does
     // not prevent the reordering of following loads 'before' the fence.  As a
     // result, we don't need to consider it as writing to memory and don't need
     // to advance the generation.  We do need to prevent DSE across the fence,
     // but that's handled above.
     if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
       if (FI->getOrdering() == AtomicOrdering::Release) {
         assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
         continue;
       }
 
     // write back DSE - If we write back the same value we just loaded from
     // the same location and haven't passed any intervening writes or ordering
     // operations, we can remove the write.  The primary benefit is in allowing
     // the available load table to remain valid and value forward past where
     // the store originally was.
     if (MemInst.isValid() && MemInst.isStore()) {
       LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
       if (InVal.DefInst &&
           InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
-          InVal.Generation == CurrentGeneration &&
           InVal.MatchingId == MemInst.getMatchingId() &&
           // We don't yet handle removing stores with ordering of any kind.
-          !MemInst.isVolatile() && MemInst.isUnordered()) {
+          !MemInst.isVolatile() && MemInst.isUnordered() &&
+          isSameMemGeneration(InVal.Generation, CurrentGeneration,
+                              InVal.DefInst, Inst)) {
         assert((!LastStore ||
                 ParseMemoryInst(LastStore, TTI).getPointerOperand() ==
-                MemInst.getPointerOperand()) &&
-               "can't have an intervening store!");
+                MemInst.getPointerOperand() ||
+                MSSA) &&
+               "can't have an intervening store if not using MemorySSA!");
         DEBUG(dbgs() << "EarlyCSE DSE (writeback): " << *Inst << '\n');
+        removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
         ++NumDSE;
         // We can avoid incrementing the generation count since we were able
         // to eliminate this store.
         continue;
       }
     }
if (Inst->mayWriteToMemory()) {
         if (LastStore) {
           ParseMemoryInst LastStoreMemInst(LastStore, TTI);
           assert(LastStoreMemInst.isUnordered() &&
                  !LastStoreMemInst.isVolatile() &&
                  "Violated invariant");
           if (LastStoreMemInst.isMatchingMemLoc(MemInst)) {
             DEBUG(dbgs() << "EarlyCSE DEAD STORE: " << *LastStore
                          << "  due to: " << *Inst << '\n');
+            removeMSSA(LastStore);
             LastStore->eraseFromParent();
             Changed = true;
             ++NumDSE;
             LastStore = nullptr;
           }
           // fallthrough - we can exploit information about this store
         }
 

 }
 
 PreservedAnalyses EarlyCSEPass::run(Function &F,
                                     AnalysisManager<Function> &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
+  auto *MSSA = AM.getCachedResult<MemorySSAAnalysis>(F);
 
-  EarlyCSE CSE(TLI, TTI, DT, AC);
+  EarlyCSE CSE(TLI, TTI, DT, AC, MSSA);
 
   if (!CSE.run())
     return PreservedAnalyses::all();
 
   // CSE preserves the dominator tree because it doesn't mutate the CFG.
   // FIXME: Bundle this with other CFG-preservation.
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<GlobalsAA>();
+  PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
 namespace {
 /// \brief A simple and fast domtree-based CSE pass.
 ///
 /// This pass does a simple depth-first walk over the dominator tree,
 /// eliminating trivially redundant instructions and using instsimplify to
public:
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+    auto *MSSAPass = getAnalysisIfAvailable<MemorySSAWrapperPass>();
+    auto *MSSA = MSSAPass ? &MSSAPass->getMSSA() : nullptr;
 
-    EarlyCSE CSE(TLI, TTI, DT, AC);
+    EarlyCSE CSE(TLI, TTI, DT, AC, MSSA);
 
     return CSE.run();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addUsedIfAvailable<MemorySSAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<MemorySSAWrapperPass>();
     AU.setPreservesCFG();
   }
 };
 }
 
 char EarlyCSELegacyPass::ID = 0;
 
 FunctionPass *llvm::createEarlyCSEPass() { return new EarlyCSELegacyPass(); }
 
 INITIALIZE_PASS_BEGIN(EarlyCSELegacyPass, "early-cse", "Early CSE", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(EarlyCSELegacyPass, "early-cse", "Early CSE", false, false)

lib/Transforms/Utils/MemorySSA.cpp

 }
 
 void MemorySSAWrapperPass::verifyAnalysis() const { MSSA->verifyMemorySSA(); }
 
 void MemorySSAWrapperPass::print(raw_ostream &OS, const Module *M) const {
   MSSA->print(OS);
 }
 
+FunctionPass *createMemorySSAPass() { return new MemorySSAWrapperPass(); }
+
 MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
 
 CachingMemorySSAWalker::CachingMemorySSAWalker(MemorySSA *M, AliasAnalysis *A,
                                                DominatorTree *D)
     : MemorySSAWalker(M), AA(A), DT(D) {}
 
 CachingMemorySSAWalker::~CachingMemorySSAWalker() {}
 

test/Transforms/EarlyCSE/AArch64/intrinsics.ll

 ; RUN: opt < %s -S -mtriple=aarch64-none-linux-gnu -mattr=+neon -early-cse | FileCheck %s
+; RUN: opt < %s -S -mtriple=aarch64-none-linux-gnu -mattr=+neon -basicaa -memoryssa -early-cse | FileCheck %s
 ; RUN: opt < %s -S -mtriple=aarch64-none-linux-gnu -mattr=+neon -passes=early-cse | FileCheck %s
 
 define <4 x i32> @test_cse(i32* %a, [2 x <4 x i32>] %s.coerce, i32 %n) {
 entry:
 ; Check that @llvm.aarch64.neon.ld2 is optimized away by Early CSE.
 ; CHECK-LABEL: @test_cse
 ; CHECK-NOT: call { <4 x i32>, <4 x i32> } @llvm.aarch64.neon.ld2.v4i32.p0i8
   %s.coerce.fca.0.extract = extractvalue [2 x <4 x i32>] %s.coerce, 0

test/Transforms/EarlyCSE/AArch64/ldstN.ll

 ; RUN: opt -S -early-cse < %s | FileCheck %s
+; RUN: opt -S -basicaa -memoryssa -early-cse < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 declare { <4 x i16>, <4 x i16>, <4 x i16>, <4 x i16> } @llvm.aarch64.neon.ld4.v4i16.p0v4i16(<4 x i16>*)
 
 ; Although the store and the ld4 are using the same pointer, the
 ; data can not be reused because ld4 accesses multiple elements.
 define { <4 x i16>, <4 x i16>, <4 x i16>, <4 x i16> } @foo() {

test/Transforms/EarlyCSE/atomics.ll

 ; RUN: opt < %s -S -early-cse | FileCheck %s
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
 
 ; CHECK-LABEL: @test12(
 define i32 @test12(i1 %B, i32* %P1, i32* %P2) {
   %load0 = load i32, i32* %P1
   %1 = load atomic i32, i32* %P2 seq_cst, align 4
   %load1 = load i32, i32* %P1
   %sel = select i1 %B, i32 %load0, i32 %load1
   ret i32 %sel

test/Transforms/EarlyCSE/basic.ll

 ; RUN: opt < %s -S -early-cse | FileCheck %s
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
 ; RUN: opt < %s -S -passes=early-cse | FileCheck %s
 
 declare void @llvm.assume(i1) nounwind
 
 ; CHECK-LABEL: @test1(
 define void @test1(i8 %V, i32 *%P) {
   %A = bitcast i64 42 to double  ;; dead
   %B = add i32 4, 19             ;; constant folds

test/Transforms/EarlyCSE/commute.ll

 ; RUN: opt < %s -S -early-cse | FileCheck %s
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
 
 ; CHECK-LABEL: @test1(
 define void @test1(float %A, float %B, float* %PA, float* %PB) {
   ; CHECK-NEXT: fadd
   ; CHECK-NEXT: store
   ; CHECK-NEXT: store
   ; CHECK-NEXT: ret
   %C = fadd float %A, %B

test/Transforms/EarlyCSE/fence.ll

 ; RUN: opt -S -early-cse < %s | FileCheck %s
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
 ; NOTE: This file is testing the current implementation.  Some of
 ; the transforms used as negative tests below would be legal, but 
 ; only if reached through a chain of logic which EarlyCSE is incapable
 ; of performing.  To say it differently, this file tests a conservative
 ; version of the memory model.  If we want to extend EarlyCSE to be more
 ; aggressive in the future, we may need to relax some of the negative tests.
 
 ; We can value forward across the fence since we can (semantically) 

test/Transforms/EarlyCSE/guards.ll

 ; RUN: opt -S -early-cse < %s | FileCheck %s
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
 
 declare void @llvm.experimental.guard(i1,...)
 
 define i32 @test0(i32* %ptr, i1 %cond) {
 ; We can do store to load forwarding over a guard, since it does not
 ; clobber memory
 
 ; CHECK-LABEL: @test0(

test/Transforms/EarlyCSE/memoryssa.ll

+; RUN: opt < %s -S -early-cse | FileCheck %s --check-prefix=CHECK-NOMEMSSA
+; RUN: opt < %s -S -basicaa -memoryssa -early-cse | FileCheck %s
+; RUN: opt < %s -S -aa-pipeline=basic-aa -passes='require<memoryssa>,early-cse' | FileCheck %s
+
+@G1 = global i32 zeroinitializer
+@G2 = global i32 zeroinitializer
+
+;; Simple load value numbering across non-clobbering store.
+; CHECK-LABEL: @test1(
+; CHECK-NOMEMSSA-LABEL: @test1(
+define i32 @test1() {
+  %V1 = load i32, i32* @G1
+  store i32 0, i32* @G2
+  %V2 = load i32, i32* @G1
+  ; CHECK-NOMEMSSA: sub i32 %V1, %V2
+  %Diff = sub i32 %V1, %V2
+  ret i32 %Diff
+  ; CHECK: ret i32 0
+}
+
+;; Simple dead store elimination across non-clobbering store.
+; CHECK-LABEL: @test2(
+; CHECK-NOMEMSSA-LABEL: @test2(
+define void @test2() {
+entry:
+  %V1 = load i32, i32* @G1
+  ; CHECK: store i32 0, i32* @G2
+  store i32 0, i32* @G2
+  ; CHECK-NOT: store
+  ; CHECK-NOMEMSSA: store i32 %V1, i32* @G1
+  store i32 %V1, i32* @G1
+  ret void
+}