This patch introduces MemorySSA, a virtual SSA form for memory. Details on what it looks like are in MemorySSA.h

[george.burgess.iv]

Summary

There is no grand scheme to use this across LLVM (at least, that i have).
The main purposees for it are to clean and speed up things like MemoryDependenceAnalysis
(which spends a lot of time walking to find use/defs of memory, etc), and to
be able to provide load value numbering to GVN (and PRE).
Secondarily, it may be possible to speed up some of the other load/store
motion passes using it.

Note that creation of MemorySSA is linear time and space relative to the IR
size. It uses the same linear time phi placement algorithm PromoteMemoryToRegisters does
(though sadly, not the same code because abstracting PromoteMemoryToRegisters
is not easy since we don't derive the memory access classes from things
like Value, etc)

It's lived both as a utility that passes could create and delete, and as a pass.
In the current patch, it's a functionpass that things can require
as an analysis.
Happy to put it back to being a utility, not sure which makes more sense.
I only have GVN using it right now.

As a small note: The immediate-use lists are ugly right now. Suggestions for how to do
that better welcome.

Anyway, happy to answer any questions, and not looking to commit this tomorrow,
more it got to the point where i think it would be good to get some other eyes
on it.

[reames]

include/llvm/Transforms/Utils/MemorySSA.h

13

This comment will need to be expanded at some point. That can wait until the code is closer to ready though.

Correction, the comment I wanted was below. Might make sense to move some of it into the file comment or provide a forward reference.

31

I would phrase this as: links together memory access instructions such as loads, stores, ...

92

I might avoid the term "Type" here since that has a well defined meaning in LLVM. Using AccessType consistently would be clearer.

108

A bounds assertion here would be good.

130

The term "UseOperand" isn't clear to me here. Is this the link back to a def or phi?

156

I'm not sure we need an explicit def version here. Doesn't the address of the underlying instruction serve that purpose as well? (And when that instruction disappears, we need to renumber anyways.)

[• dberlin]

Thanks so much for taking a look at what i've got so far!

[jmolloy]

Hi Daniel,

One inline comment about the design. Sorry for the naiveity.

Cheers,

James

include/llvm/Transforms/Utils/MemorySSA.h

151

I don't understand this: Firstly, why must all defs have a use? We can store without loading the resulting value back.

Secondly, you've used inheritance which is an "is-a" relationship. Is there something fundamental I'm missing here?

[• dberlin]

Also, as a natural followup, i'll pointed out that GCC experimented with
must/may defs (IE we have MemoryMustDef to represent strong updates, and
MemoryMayDef to everything else), as well as a separate MemoryKill (for
inline assembly we didn't understand or instructions that were "clobbers of
all memory").

It also allowed for multiple "heap versions" to be live at once (To try to
reduce the length of the chains).
This required multiple memorydefs/uses on a single instruction, as well as
multiple phis

In practice, nothing used any of these distinctions to any good effect.
In the end, they all just wanted to walk the chains, and having multiple
heap versions means walking more chains (even if some are shorter), so in
the end it did not end up making the compiler faster, but it did make it
more complicated :)

After roughly 10-12 years (i forget how long it's been) of playing with
different options, GCC is also now back to just MemoryDef and MemoryUse,
and a single heap version.

[• dberlin]

Update for commments received so far.

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

include/llvm/Transforms/Utils/MemorySSA.h

13

fixed

31

fixed

92

Fixed

156

fixed in version i'm about to upload

This does make debugging a bit harder (IMHO), but such is life :)

[• dberlin]

Reserve space for args

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Initialize Use lists
Fix bug in getClobberingMemoryAccess

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[hfinkel]

lib/Transforms/Utils/MemorySSA.cpp

87

What exactly does "updated to handle call instructions properly" mean? Also, this looks like it should be a member function of AA. Can you please add it there (then we can update MDA to use it too?).

101

Part of my confusion is this: What does the call's return value have to do with the memory location(s) accessed by the call?

We do have these in AA:

static Location getLocationForSource(const MemTransferInst *MTI);
static Location getLocationForDest(const MemIntrinsic *MI);

and I imagine those would be good to use here.

But for generic calls, we don't have any facility to get a location, or list of locations, touched by the call. We can do call-site vs. call-site queries, and call-site vs. Location queries, however.

137

Can you please define here what a "false" version is? (non-aliasing?)

242

I'm likely missing something here, but why don't you just call AA->getModRefInfo for all types of instructions? The overload for Instruction* handles all of the various types:

/// getModRefInfo - Return information about whether or not an instruction may
/// read or write the specified memory location.  An instruction
/// that doesn't read or write memory may be trivially LICM'd for example.
ModRefResult getModRefInfo(const Instruction *I,
                           const Location &Loc) {
  switch (I->getOpcode()) {
  case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, Loc);
  case Instruction::Load:   return getModRefInfo((const LoadInst*)I,  Loc);
  case Instruction::Store:  return getModRefInfo((const StoreInst*)I, Loc);
  case Instruction::Fence:  return getModRefInfo((const FenceInst*)I, Loc);
  case Instruction::AtomicCmpXchg:
    return getModRefInfo((const AtomicCmpXchgInst*)I, Loc);
  case Instruction::AtomicRMW:
    return getModRefInfo((const AtomicRMWInst*)I, Loc);
  case Instruction::Call:   return getModRefInfo((const CallInst*)I,  Loc);
  case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc);
  default:                  return NoModRef;
  }
}

270

Why are you printing the instruction addresses here? Would it be more useful to print *I?

358

Range-based for?

412

Range-based for using succ_range?

436

Range-based for here?

491

Range-based for?

540

Range-based for?

556

Maybe add here?

assert(!DT->isReachableFromEntry(BB) &&
            "Reachable block found while handling unreachable blocks");

614

Range-based for?

636

Range-based for?

638

Range-based for?

652

You're testing against an empty location? I don't think this is what you want, how about using this:

/// getModRefBehavior - Return the behavior when calling the given call site.
virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);

688

in to -> into

689

But you don't really insert anything into the IR proper. I'd rephrase this.

718

No need for { } here.

730

Range-based for?

738

Range-based for? And you don't need the { } here.

771

Range-based for?

781

Range-based for?

[• dberlin]

Comment at: lib/Transforms/Utils/MemorySSA.cpp:357
@@ +356,3 @@
+ unsigned ID = 0;
+ for (auto I = F.begin(), E = F.end(); I != E; ++I)

+ BBNumbers[I] = ID++;

Range-based for?

BTW, at least the obvious construction of that for( auto I : F) gives:
../lib/Transforms/Utils/MemorySSA.cpp:350:13: error: call to deleted
constructor of 'llvm::BasicBlock'

for (auto I : F)
          ^ ~

../include/llvm/IR/BasicBlock.h:85:3: note: 'BasicBlock' has been
explicitly marked deleted here

BasicBlock(const BasicBlock &) = delete;
^

Is there some way to iterate over basic block instructions using range
based for that we've added?

[• dberlin]

Update for review comments (though not quite ready for re-review, need to document a few changes better)

Also handle call caching and clobbering better

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[majnemer]

include/llvm/Analysis/AliasAnalysis.h

155–156 ↗

(On Diff #20966)

No need for else here.

include/llvm/Transforms/Utils/MemorySSA.h

2–3

This looks strange, can you make it look like the other files?

lib/Transforms/Utils/MemorySSA.cpp

2

No need for this whitespace.

[• dberlin]

Move state into a structure, clean up a bit, and use structure to stop abusing Loc.Ptr as storage

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[hfinkel]

lib/Transforms/Utils/MemorySSA.cpp

238

I had also been thinking that the logic of this else block could be moved into a utility function of AliasAnalysis. It seems to be that this is exactly what you'd want

AA->getModRefInfo(Inst1, Inst2)

to mean. Do you agree?

[• dberlin]

Add a dominance verifier, make a new alias analysis API and use it, fix a small bug in incomplete phi handling

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Bug fix i had forgotten to commit locally

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Add dump and verify options so we can use them for tests
Write basic tests
Remove compute live in, it's useless for memory ssa (everything is live-in since defs are uses)

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Make MemorySSA able to be lazy, and add a non-lazy pass for tests to use
Separate out walking interface, move caching walker to use it

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[reames]

This is looking reasonable complete. Any chance we could land it in it's current form and evolve it in tree? Tracking changes is becoming quite hard.

Using this to implement a simple cross block DSE might be an interesting proof of concept. I'm not set on that idea, but it would be nice to have something in tree to show this actually working. Once we have that, we can migrate other passes to it one by one.

[• dberlin]

Update API, fix all documentation, fix use list bugs
Should be ready enough now.

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Trigger an update so phabricator resends this review email.
This code should now be ready to go in.

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Update MemorySSA API to allow specifying where insertion occurs

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Update linear time phi placement algorithm for bug fixes
Add an API for adding memory uses

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Just a friendly ping. I think i've addressed all previous comments on
MemorySSA, and have patches ready to make it used in-tree (see the
MergedLoadStoreMotion rewrite. I also have a MemCpyOptimizer rewrite
in progress).

[reames]

Ok, this review excludes MemorySSA.cpp. I'll come back to that in a separate pass shortly.

I see a bunch of small issues, but nothing so far that absolutely needs to be addressed before submission. Given that a) this is an off by default change, and b) the author is a long established trusted committer, I have no problem with review comments being addresses as this evolves further in tree.

When you do submit, please separate the AA changes into their own submission. It should go in a few days before the memorySSA so that we can identify breakage in isolation.

I would also strongly prefer to see more test cases included. If nothing else, having a set of small examples for the semi obvious cases would make the usage of memory ssa much easier to understand.

include/llvm/Analysis/AliasAnalysis.h

374 ↗

(On Diff #23347)

I might make this a switch so that all the cases are obviously covered and checked by the compiler.

508 ↗

(On Diff #23347)

This seems like a subset of the getModRefInfo interface. Is there a strong reason it needs to be phrased differently?

include/llvm/IR/Function.h

552

Again, submit separately please.

include/llvm/Transforms/Utils/MemorySSA.h

16

Given clobbers aren't instructions, please phrase this as:
such as loads, stores, and calls, and atomics.

Also, you *really* need to update this comment to include the bits about only mayalias accesses being on the immediate use list. This is badly needed to prevent confusion.

62

This comment is now explicitly wrong.

101

Should this be part of the public interface?

118

Aren't all of these actually users not uses? Not sure there's a real distinction for memory SSA, but this might be slightly confusing by analogy to normal def-use. If there is no difference, maybe add a comment that clarifies that?

One possible interesting case, what happens if you have a partially overlapping memcpy? Is that a single user or two uses?

133

Why do these need to be friends? Shouldn't protected access be enough? I *really* dislike having friend declarations here unless they're absolutely necessary.

149

"find" seems like the wrong name here. Possible hasUse?

154

Should this possibly be a pure virtual function? 0 doesn't seem overly meaningful here.

196

Again, does this need to be public?

228

Define clobber. Preferrably using mayalias terminology. References to AA docs are fine.

261

Is this still true with the mayalias changes? If so, how does that work? Respond as a comment in code please.

270

Should this be called on a phi? Maybe llvm_unreachable?

293

Move definition to cpp please.

327

Args seems like a confusing name here. What does the PHINode class call these? Use that for consistency please.

408

When should this (and the next few routines) be used?

430

Hopefully, this is checked in an assertion somewhere?

540

Can you expand this comment? From the naming, it's not clear when I'd use one of these and why.

551

I'd suggest clarifying this as "by skipping any def which AA can prove does not alias the location(s) accessed by the instruction given"

554

This comment is unclear?

563

Dead code, please remove!

572

I'm confused, am I allowed to call getClobberingMemoryAccess on a DoNothingMemorySSAWalker? What are the semantics here?

577

"real"? As opposed to?

lib/Analysis/AliasAnalysis.cpp

351 ↗

(On Diff #23347)

These *need* to submitted separately with test cases if possible.

[reames]

include/llvm/Analysis/AliasAnalysis.h

148 ↗

(On Diff #23347)

This can and should go in separately.

371 ↗

(On Diff #23347)

Same as above.

[reames]

Ok, here's the MemorySSA.cpp parts of the review. Lots of small style comments, a couple of larger concerns. At least some of the code duplication would be nice to address before submission, though I wouldn't say it's mandatory as long as it was done quickly thereafter.

I'm uncomfortable with some of the bits inside the CachingMemorySSAWalker routines. Would you mind submitting the first version of the memory SSA code without them and then reviewing those separately? There's some very complex logic there that duplicates parts of MDA. Given how tricky MDA has been, I'm really not comfortable with the code in the walkers as it stands today without a much more careful review

lib/Transforms/Utils/MemorySSA.cpp

50

Isn't this line redundant with the above?

80

I'm skipping all the code copied from PMtR. I'm going to assume it's correct.

p.s. Any chance this could be expressed in a common template used by both places?

282

Can we use smart pointers by chance? The manual memory management seems unnecessary.

304

We no longer throw this out do we?

322

This should be pulled out in a helper lambda or otherwise commoned.

328

else if - once you do that, can't this just become:
if (def) {
} else if (use) {
} else {

llvm_unreachable()

}

416

Don't you need to add these to the per-BB list? Also, can this code be commoned with the memory SSA construction path?

428

It looks like you're not really using the instruction at all, maybe just pass the basicblock to begin with?

463

Again, can we common this somewhere? You've got this lazy creation scatter all over the place.

Accesses = ensureBBList(BB)?

505

This seems odd. Shouldn't we be putting Replacer in the spot Replacee was?

548

Did you possible mean a != here?

561

This condition really doesn't feel like a "replacement". Is it time to reconsider the interface and turn this into an assert?

572

It might be cleaner to unconditionally insert the new value, then fold single use memory phis. Having a fold single use phi utility might also be useful on the public interface.

Actually, are you expecting an invariant where such phis are always folded? If so, please update comments to say so.

612

If there are no uses, why is it required? Did you mean:
use_empty || onlySingleValue?

621

You've got this code repeated a bit. Utility function on memoryPhi?

822

Can't you just use cl opt for this?

853

smart pointer?

943

Er, huh? How can this happen? And should it?

1006

Er, what? This just seems flat out wrong. Two loads on the same thread to the same location are always ordered regardless of flags. Ordering doesn't bypass a mustalias...

Unless this is absolutely required, I would request you separate this and review it separately.

1026

I might be missing something here, but how is this not an infinite recursion on itself?

1043

This seems suspicious to me as said above.

More generally, the smarts of this routine deserve to be reviewed independently.

1084

Mild preference, change this to:
else if (CallSite CS = ...) {
} else {
}

1111

Does this optimization actually help? Just curious.

[jmolloy]

Hi Daniel,

I'm looking at making LLVM recognize an idiom that I think MemorySSA+PRE would handle. What's the status of MemorySSA?

I know you haven't had much time to work on it recently; is it in such a state that someone (me) could help progress it?

Cheers,

James

[• dberlin]

Yes, it was looked at and approved, it just needs more tests written
and the initial update infrastructure ripped out and then slowly
rebuilt.
I can send you the latest patch, which fixes a bunch of bugs/etc.

[hfinkel]

In D7864#216848, @dberlin wrote:

Yes, it was looked at and approved, it just needs more tests written
and the initial update infrastructure ripped out and then slowly
rebuilt.
I can send you the latest patch, which fixes a bunch of bugs/etc.

Can you please post it here too, so we can continue the review?

[• dberlin]

Refactor and rewrite a lot of stuff. This is somewhat of an intermediate state, so it's a bit messier than i'd like.
This version builds but i haven't played with it in a few months, so i expect it is bitrotted and may be a bit broken.
I am updating it mainly to give someone else a chance to takeover since i'm going to be swamped for a while.

Main algorithmic changes:
We now use BFS to find nearest dominating access in the caching walker.
I've performed extensive performance testing of hybrid DFS and BFS schemes, and BFS wins every time.
A bunch of things have started being iteratorized.
The caching walker has been modified a bit. The current caching scheme is fast, but can't easily be invalidated on a per-access basis.
The overhead of simple schemes that supported that level of invalidation was *quite* large.
(the ideal caching storage scheme here is actually quadtrees).

The caching walker now uses the same phi translation mechanism that memorydepedenceanalysis does.
I'm not sure this is a good thing, as that phi translation mechanism is ... strange and weird and has weird optimizations embedded in it.
It may be better to get worse optimization to start and clean that stuff up.

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Also note: BFS or a hybrid DFS scheme is required to actually fulfill the
API guarantee we make - that we will give you the nearest dominating access.
DFS may find an access that is dominating but not the nearest dominating
one, depending on what paths it follows.

[hfinkel]

Thanks for the update!

Quick comment (just so I don't forget), there are a few places that have:

assert(N < 10000 && ..)

that need to become actual conservative bailouts instead of asserts.

lib/Transforms/Utils/MemorySSA.cpp

1285

You might also want to check AA->pointsToConstantMemory here.

[• dberlin]

Yeah, these were just debugging asserts. They are there so i got asserts
on infinite loops and could bugpoint the testcases.
There shouldn't be any bugs left (most of the infinite loops were due to
inconsistency between the iterator and phitransaddr in what the result of
phi translation was. Now that they use the same thing, there is no
inconsistency) :)

They should definitely be removed, and i've run memoryssa across google's
codebase without them triggering.

I'm pretty sure i won't get to this patch in the next 6 months, though i'm
trying to find someone on my side to take it over. If someone else wants
to, that'd be awesome as well.

[• dberlin]

Fix comments, remove DFS, update tests to work again (aliasing got too smart)

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[hfinkel]

lib/Transforms/Utils/MemorySSA.cpp

1125

This algorithm in getClobberingMemoryAccess does not seem correct. If we have this:

   [ entry ]
       |
      ...
       |
   (clobbering access - a)
      ...
  /          \
...         (clobbering access - b)
 |              |
...           ....
 \              /
        ...
 (starting access)

UpwardsBFSWalkAccess seems to walk upward until it finds its first clobbering access, and returns that when found. In the case above, if we find clobbering access (b) first, then we're okay, because we'll pick some dominating def farther down the path which is on all paths to both dominating accesses.

But, if we hit clobbering access (a) first, then we'll accept that (incorrectly) as the new final access, because it dominates the original. However, not all paths to all aliasing defs terminate (or pass through) that access.

I think that you can continue the walk so that you search the entire subgraph to make sure that all paths terminate at the same aliasing def, and only in that case, use it (and, in that case, you know it must dominate).

My attempts to think up a good solution to the more-general problem have thus-far been stymied by this situation:

[entry]
  |
.....
(clobbering access - b)
 |
....   ________________________________
  \   /                                                               |
   (x)                                                               |
 ......                                                               |
    |                                                                 |
    |    ______________________                 |
     \   /                                        |                   |
(starting access)                        |                   |
     ...                                           |                   |
 (clobbering access - a)              |                   |
    ...                                            |                   |
    | |                                            |                   |
    | |______________________|                   |
    |                                                                  |
    |_________________________________|

The idea is that the block with the starting access also later has a clobbering access (a). This block is one of its own predecessors, but that's not the only path from clobbering access (a) back to the starting access. And furthermore, the other path flows through other blocks that do properly dominate the starting access. Thus, even if you were to pick a def (or phi) on the path from the starting access through its dominating predecessor, say at (x), and even though there are paths to all aliasing defs along that route, you'd still be wrong because there exists a path to clobbering access (a) that does not contain (x) (the path following the inner-loop backedge).

Thoughts? (am I off base here?)

[• dberlin]

In-progress update

This brings back the DFS code and starts to update the BFS code to do the right thing with phi nodes.
Given the structure of the SSA graph and our requirements, i'm pretty positive both DFS and BFS will give correct results (and testing them against each other bears this out, though is not exhaustive).

Given that, and how ugly the BFS code is now starting to become to support the phi node rules, i'm tempted to get rid of it and just stick with DFS.

Thoughts welcome :)

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[• dberlin]

Remove BFS code, fix a bug in DFS code.

(Updating so gbiv can take over)

Updating D7864: This patch introduces MemorySSA, a virtual SSA form for memory.

Details on what it looks like are in MemorySSA.h

[george.burgess.iv]

It turns out that *can* steal revisions -- yay.

Taking ownership, killing D16743

[george.burgess.iv]

Added Danny's patch that makes everything a User, as well as all of the updates published originally in the now-abandoned D16743.

Addressed all feedback in D16743, as well.

[• dberlin]

You need

static inline bool classof(const Value *V) {
<right stuff>
}

For each of the classes. I only pasted it into memorydef, but without it, walking over operands and casting uses will not work.

[• dberlin]

But other than that, LGTM, i don't really have anything to add.
Thanks for taking this on!

[george.burgess.iv]

• Marked dead feedback as done, responded to others, will respond to remaining non-done + unanswered by tomorrow
• Fixed Danny's comment about having classof(Value*)
• Moved initialize[...]Pass methods to fix a bug with how we were trying to link things
• Ripped out some optimizations (e.g. checks for invariant loads, etc.) because those seem mildly controversial, and can be added in a later patch

[george.burgess.iv]

Thanks for the LGTM, Danny.

First wave of responses...

include/llvm/Transforms/Utils/MemorySSA.h

134

Because it breaks code like (ripped from MemoryDef::print(raw_ostream &)):

MemoryAccess *UO = getDefiningAccess();
if (UO && UO->getID()) // Breaks
  // ...

...Because protected doesn't let you call protected methods on other MemoryAccesses. You can call them on yourself, or you can call them on other MemoryDefs. That's all.

Do you think it would be better to make getID() public, or to keep the friend declarations? I'm happy with either.

152

It wasn't entirely an isa relationship. It's now refactored to be more clear.

294

Definition of MemoryPhi::setIncomingValue is now substantially smaller. Leaving in header, unless you'd still like to see it moved.

409

Update API has been removed for now.

lib/Transforms/Utils/MemorySSA.cpp

81

Comment is on code that seems to have been removed.

88

Comment is on code that seems to have been removed.

153

Comment is on code that seems to have been removed.

622

Now only exists in one place AFAICT.

964

Nuked possiblyAffectedBy from orbit; it's an optimization that can be readded later.

964

Do you still hold this opinion? (Potentially dubious is now in CachingMemorySSAWalker::instructionClobbersQuery)

964

Marked with a TODO so we can look into that when we have users of MemorySSA/a more complete API/...

964

Seems old; we now use DFS. Marking as done, but added a test case of your second example.

964

I think it's better to get MemorySSA in and work on little optimizations like this after that. Removed the invariant check (but kept the test as an XFAIL), to be readded in the near future as a set of enhancements.

[george.burgess.iv]

After further investigation, the rest of the comments seem to be dead/already addressed, too; marked them as done.

Also, wow. Responding to comments at the bottom *really* didn't go well. I thought it would reflow them, but apparently not. Sorry about that. :/

Either way, I'll leave this open for a bit, in case anyone has any other remarks. Assuming Danny's LGTM is sufficient to let me commit, I'll do so lateish Wednesday if there are no objections by then. :)

Trying to make the comment/response chain at the bottom look less confusing...

reames

Er, what? This just seems flat out wrong. Two loads on the same thread to the same location are always ordered regardless of flags. Ordering doesn't bypass a mustalias...
Unless this is absolutely required, I would request you separate this and review it separately.

Nuked possiblyAffectedBy from orbit; it's an optimization that can be readded later.

Does this optimization actually help? Just curious.

Marked with a TODO so we can look into that when we have users of MemorySSA/a more complete API/...

This seems suspicious to me as said above.
More generally, the smarts of this routine deserve to be reviewed independently.

possiblyAffectedBy was removed, so I think this comment doesn't apply anymore (nor does my initial response to it). :)

hfinkel

You might also want to check AA->pointsToConstantMemory here.

I think it's better to get MemorySSA in and work on little optimizations like this after that. Removed the invariant check (but kept the test as an XFAIL), to be readded in the near future as a set of enhancements. (Good point, though!)

This algorithm in getClobberingMemoryAccess does not seem correct [...]

Seems old; we now use DFS. Marking as done, but added a test case of your second example.

[reames]

Explicitly LGTM as well. I'm really looking forward to having this in tree so that we can start experimenting and iterating on top of it.

I don't think we're going to be ready to switch the default for a while yet, but being able to iterate and work through the bugs in tree is going to be very empowering and will likely speedup progress.

p.s. What's your planned next step? I'd suggest implementing a very simple pass which just runs obvious peepholes over the MemorySSA representation. (e.g. a MemCombine pass). My suspicion is that will be a good way to stress the implementation and might even be profitable enough to just turn on by default. In particular, a pass that got the easy forms of cross block DSE would be very useful..

[• dberlin]

FWIW: My plan was going to start to replace some of the existing
memorydependence users which are O(N^2) and ugly with simpler O(N)
algorithms using MemorySSA

[george.burgess.iv]

Explicitly LGTM as well. I'm really looking forward to having this in tree so that we can start experimenting and iterating on top of it.

Thanks! (Also, naturally, thanks to everyone who reviewed/commented/... :) )

I don't think we're going to be ready to switch the default for a while yet, but being able to iterate and work through the bugs in tree is going to be very empowering and will likely speedup progress.

It seems that there are a number of people who are concerned about subtle bugs (both in MemorySSA, and in user code -- especially if this lets us optimize code in new and exciting ways). So, I agree that making this opt-in for a time is a good idea.

What's your planned next step? I'd suggest implementing a very simple pass which just runs obvious peepholes over the MemorySSA representation. (e.g. a MemCombine pass). My suspicion is that will be a good way to stress the implementation and might even be profitable enough to just turn on by default. In particular, a pass that got the easy forms of cross block DSE would be very useful.

I don't have any plans. If we want to port existing passes soon, we'll either need an update API, or we'll need to restrict ourselves to passes that don't use the update API. Also, we'll need a wrapper that either queries MemDep or MemorySSA if we want to have a global "use MemorySSA?" flag. If we think making a simple MemorySSA-based DSE pass would be a better first step, I'm fine doing that, as well. Same thing goes for readding the optimizations that were stripped out today.

So long as progress is made, I'm happy. :)

[davidxl]

Excellent progress.

As Danny mentioned, the O(N^2) behavior of some MemoryDependence users
are biting us badly in some cases. For instance, some of the C++
source takes forever to compile with profile instrumentation turned on
and the root cause is due to that. Replacing those with memSSA based
algorithms will have very large (good) impact.

thanks,

David

[• dberlin]

I don't have any plans. If we want to port existing passes soon, we'll
either need an update API, or we'll need to restrict ourselves to passes
that don't use the update API.

FWIW: For the passes i played with converting, timing compute memssa + use
it vs memdep, for basically all testcases i could find, the time difference
was in the noise.
For larger cases, memssa is a straight win.
This is because most of the memdep passes are walking a ton of blocks/insts
repeatedly anyway.

Also, we'll need a wrapper that either queries MemDep or MemorySSA if we
want to have a global "use MemorySSA?" flag.

I'm not sure such a flag makes sense, given the above. I'm not sure you
*want* to try to alternate between them, because a lot of your order of
magnitude speedups will come from doing things fundamentally different
than random querying (IE move to more "SSA-like" algorithms).

(Though i expect using memssa as a straight replacement will still likely
be faster).

If we think making a simple MemorySSA-based DSE pass would be a better

first step, I'm fine doing that, as well. Same thing goes for readding the
optimizations that were stripped out today.

If you do the optimizations, i'm happy to start to convert passes. I was
going to just do them in close to the order necessary to preserve memssa
from beginning to end of opts that use it, but happy to do whatever.

(mergedloadstoremotion and memcpyoptimizer are the easiest things to
convert and will give speedups).

Converting most passes requires building an update API, and converting a
few of them and seeing what they want out of updating is the best way i can
think of to design that API.

(You can see where i played with it in the mergedloadstoremotion mpass).

So long as progress is made, I'm happy. :)

http://reviews.llvm.org/D7864

[jlebar]

I'm seeing an asan failure in one of the tests added here. I'm building from tip, clean tree, linux x86-64.

-- Testing: 1 of 15992 tests, 1 threads --
FAIL: LLVM-Unit :: Transforms/Utils/UtilsTests/MemorySSA.RemoveMemoryAccess (1 of 1)
******************** TEST 'LLVM-Unit :: Transforms/Utils/UtilsTests/MemorySSA.RemoveMemoryAccess' FAILED ********************
Note: Google Test filter = MemorySSA.RemoveMemoryAccess
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from MemorySSA
[ RUN      ] MemorySSA.RemoveMemoryAccess
=================================================================
==5162==ERROR: AddressSanitizer: heap-use-after-free on address 0x60800000bb68 at pc 0x000000c96299 bp 0x7ffea8a84a90 sp 0x7ffea8a84a88
READ of size 8 at 0x60800000bb68 thread T0
  #0 0xc96298 in llvm::MemoryAccess::getBlock() const /usr/local/google/home/jlebar/llvm/src/include/llvm/Transforms/Utils/MemorySSA.h:116:34
  #1 0xc96298 in llvm::MemorySSA::removeFromLookups(llvm::MemoryAccess*) /usr/local/google/home/jlebar/llvm/src/lib/Transforms/Utils/MemorySSA.cpp:469
  #2 0x58ffee in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:65:3
  #3 0xd66ec3 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #4 0xd66ec3 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
  #5 0xd6b854 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
  #6 0xd6cb16 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
  #7 0xd85c7a in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
  #8 0xd84eaf in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #9 0xd84eaf in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
  #10 0xd3cc67 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
  #11 0x7fc886a0dec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287
  #12 0x54bd09 in _start (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x54bd09)

0x60800000bb68 is located 72 bytes inside of 96-byte region [0x60800000bb20,0x60800000bb80)
freed by thread T0 here:
  #0 0x4c734b in operator delete(void*) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c734b)
  #1 0xc9602e in llvm::ilist_node_traits<llvm::MemoryAccess>::deleteNode(llvm::MemoryAccess*) /usr/local/google/home/jlebar/llvm/src/include/llvm/ADT/ilist.h:160:39
  #2 0xc9602e in llvm::iplist<llvm::MemoryAccess, llvm::ilist_traits<llvm::MemoryAccess> >::erase(llvm::ilist_iterator<llvm::MemoryAccess>) /usr/local/google/home/jlebar/llvm/src/include/llvm/ADT/ilist.h:466
  #3 0xc9602e in llvm::iplist<llvm::MemoryAccess, llvm::ilist_traits<llvm::MemoryAccess> >::erase(llvm::MemoryAccess*) /usr/local/google/home/jlebar/llvm/src/include/llvm/ADT/ilist.h:470
  #4 0xc9602e in llvm::MemorySSA::removeFromLookups(llvm::MemoryAccess*) /usr/local/google/home/jlebar/llvm/src/lib/Transforms/Utils/MemorySSA.cpp:467
  #5 0x58ffee in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:65:3
  #6 0xd66ec3 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #7 0xd66ec3 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
  #8 0xd6b854 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
  #9 0xd6cb16 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
  #10 0xd85c7a in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
  #11 0xd84eaf in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #12 0xd84eaf in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
  #13 0xd3cc67 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
  #14 0x7fc886a0dec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

previously allocated by thread T0 here:
  #0 0x4c6e0b in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c6e0b)
  #1 0xa7ec05 in llvm::User::allocateFixedOperandUser(unsigned long, unsigned int, unsigned int) /usr/local/google/home/jlebar/llvm/src/lib/IR/User.cpp:129:7
  #2 0xa7ec05 in llvm::User::operator new(unsigned long, unsigned int) /usr/local/google/home/jlebar/llvm/src/lib/IR/User.cpp:147
  #3 0xc92784 in llvm::MemoryDef::operator new(unsigned long) /usr/local/google/home/jlebar/llvm/src/include/llvm/Transforms/Utils/MemorySSA.h:271:41
  #4 0xc92784 in llvm::MemorySSA::createNewAccess(llvm::Instruction*, bool) /usr/local/google/home/jlebar/llvm/src/lib/Transforms/Utils/MemorySSA.cpp:378
  #5 0xc9098f in llvm::MemorySSA::buildMemorySSA(llvm::AAResults*, llvm::DominatorTree*) /usr/local/google/home/jlebar/llvm/src/lib/Transforms/Utils/MemorySSA.cpp:260:26
  #6 0x58f91b in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:55:29
  #7 0xd66ec3 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #8 0xd66ec3 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
  #9 0xd6b854 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
  #10 0xd6cb16 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
  #11 0xd85c7a in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
  #12 0xd84eaf in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
  #13 0xd84eaf in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
  #14 0xd3cc67 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
  #15 0x7fc886a0dec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

SUMMARY: AddressSanitizer: heap-use-after-free /usr/local/google/home/jlebar/llvm/src/include/llvm/Transforms/Utils/MemorySSA.h:116 llvm::MemoryAccess::getBlock() const
Shadow bytes around the buggy address:
0x0c107fff9710: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff9720: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff9730: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff9740: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c107fff9750: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
=>0x0c107fff9760: fa fa fa fa fd fd fd fd fd fd fd fd fd[fd]fd fd
0x0c107fff9770: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 00
0x0c107fff9780: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
0x0c107fff9790: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
0x0c107fff97a0: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 00 fa
0x0c107fff97b0: fa fa fa fa 00 00 00 00 00 00 00 00 00 00 03 fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable:           00
Partially addressable: 01 02 03 04 05 06 07 
Heap left redzone:       fa
Heap right redzone:      fb
Freed heap region:       fd
Stack left redzone:      f1
Stack mid redzone:       f2
Stack right redzone:     f3
Stack partial redzone:   f4
Stack after return:      f5
Stack use after scope:   f8
Global redzone:          f9
Global init order:       f6
Poisoned by user:        f7
Container overflow:      fc
ASan internal:           fe
==5162==ABORTING

********************
Testing Time: 0.56s
********************
Failing Tests (1):
  LLVM-Unit :: Transforms/Utils/UtilsTests/MemorySSA.RemoveMemoryAccess

Unexpected Failures: 1

[george.burgess.iv]

Thanks for the report -- looking into it now :)

[george.burgess.iv]

It seems that the test in question wasn't introduced by this patch, but the fix seems somewhat trivial, so my attempt was checked in as r262452. Please let me know if that didn't end up fixing it (I lack an ASAN-instrumented build of LLVM :) ).

[jlebar]

Please let me know if that didn't end up fixing it (I lack an ASAN-instrumented build of LLVM :) ).

Works now, although now that it's fixed asan is showing me memory leaks. :) One seems to be in the test itself, but another appears to be in the actual code.

Clearly not as urgent, but here's the report:

********************
FAIL: LLVM-Unit :: Transforms/Utils/UtilsTests/MemorySSA.RemoveMemoryAccess (15985 of 15994)
******************** TEST 'LLVM-Unit :: Transforms/Utils/UtilsTests/MemorySSA.RemoveMemoryAccess' FAILED ********************
Note: Google Test filter = MemorySSA.RemoveMemoryAccess
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from MemorySSA
[ RUN      ] MemorySSA.RemoveMemoryAccess
[       OK ] MemorySSA.RemoveMemoryAccess (25 ms)
[----------] 1 test from MemorySSA (25 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test case ran. (26 ms total)
[  PASSED  ] 1 test.

=================================================================
==147403==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 304 byte(s) in 1 object(s) allocated from:
    #0 0x4c66ab in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c66ab)
    #1 0xc89da5 in llvm::MemorySSA::buildMemorySSA(llvm::AAResults*, llvm::DominatorTree*) /usr/local/google/home/jlebar/llvm/src/lib/Transforms/Utils/MemorySSA.cpp:234:3
    #2 0x58f1eb in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:55:29
    #3 0xd60843 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #4 0xd60843 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
    #5 0xd651d4 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
    #6 0xd66496 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
    #7 0xd7f5fa in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
    #8 0xd7e82f in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #9 0xd7e82f in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
    #10 0xd365e7 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
    #11 0x7fb091525ec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

Indirect leak of 1024 byte(s) in 1 object(s) allocated from:
    #0 0x4c66ab in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c66ab)
    #1 0x58e7b8 in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:53:3
    #2 0xd60843 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #3 0xd60843 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
    #4 0xd651d4 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
    #5 0xd66496 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
    #6 0xd7f5fa in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
    #7 0xd7e82f in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #8 0xd7e82f in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
    #9 0xd365e7 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
    #10 0x7fb091525ec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

ndirect leak of 32 byte(s) in 1 object(s) allocated from:
    #0 0x4c66ab in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c66ab)
    #1 0x58e777 in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:52:3
    #2 0xd60843 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #3 0xd60843 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
    #4 0xd651d4 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
    #5 0xd66496 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
    #6 0xd7f5fa in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
    #7 0xd7e82f in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #8 0xd7e82f in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
    #9 0xd365e7 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
    #10 0x7fb091525ec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

Indirect leak of 16 byte(s) in 1 object(s) allocated from:
    #0 0x4c66ab in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c66ab)
    #1 0x58ee7f in void llvm::AAResults::addAAResult<llvm::BasicAAResult>(llvm::BasicAAResult&) /usr/local/google/home/jlebar/llvm/src/include/llvm/Analysis/AliasAnalysis.h:173:5
    #2 0x58ee7f in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:54
    #3 0xd60843 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #4 0xd60843 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
    #5 0xd651d4 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
    #6 0xd66496 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
    #7 0xd7f5fa in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
    #8 0xd7e82f in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #9 0xd7e82f in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
    #10 0xd365e7 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
    #11 0x7fb091525ec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

Indirect leak of 8 byte(s) in 1 object(s) allocated from:
    #0 0x4c66ab in operator new(unsigned long) (/usr/local/google/home/jlebar/code/llvm/asan/unittests/Transforms/Utils/UtilsTests+0x4c66ab)
    #1 0x592596 in __gnu_cxx::new_allocator<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<llvm::AAResults::Concept> > >::allocate(unsigned long, void const*) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/ext/new_allocator.h:104:27
    #2 0x592596 in std::_Vector_base<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<llvm::AAResults::Concept> >, std::allocator<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<llvm::AAResults::Concept> > > >::_M_allocate(unsigned long) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/stl_vector.h:168
    #3 0x592596 in void std::vector<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<llvm::AAResults::Concept> >, std::allocator<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<
llvm::AAResults::Concept> > > >::_M_emplace_back_aux<llvm::AAResults::Model<llvm::BasicAAResult>*>(llvm::AAResults::Model<llvm::BasicAAResult>*&&) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/vector.tcc:404
    #4 0x58f1cd in void std::vector<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<llvm::AAResults::Concept> >, std::allocator<std::unique_ptr<llvm::AAResults::Concept, std::default_delete<
llvm::AAResults::Concept> > > >::emplace_back<llvm::AAResults::Model<llvm::BasicAAResult>*>(llvm::AAResults::Model<llvm::BasicAAResult>*&&) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/vector.tcc:101:4
    #5 0x58f1cd in void llvm::AAResults::addAAResult<llvm::BasicAAResult>(llvm::BasicAAResult&) /usr/local/google/home/jlebar/llvm/src/include/llvm/Analysis/AliasAnalysis.h:173
    #6 0x58f1cd in MemorySSA_RemoveMemoryAccess_Test::TestBody() /usr/local/google/home/jlebar/llvm/src/unittests/Transforms/Utils/MemorySSA.cpp:54
    #7 0xd60843 in void testing::internal::HandleExceptionsInMethodIfSupported<testing::Test, void>(testing::Test*, void (testing::Test::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #8 0xd60843 in testing::Test::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2161
    #9 0xd651d4 in testing::TestInfo::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2309:5
    #10 0xd66496 in testing::TestCase::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2416:5
    #11 0xd7f5fa in testing::internal::UnitTestImpl::RunAllTests() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:4207:11
    #12 0xd7e82f in bool testing::internal::HandleExceptionsInMethodIfSupported<testing::internal::UnitTestImpl, bool>(testing::internal::UnitTestImpl*, bool (testing::internal::UnitTestImpl::*)(), char const*) /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:2145:12
    #13 0xd7e82f in testing::UnitTest::Run() /usr/local/google/home/jlebar/llvm/src/utils/unittest/googletest/src/gtest.cc:3841
    #14 0xd365e7 in main /usr/local/google/home/jlebar/llvm/src/utils/unittest/UnitTestMain/TestMain.cpp:47:10
    #15 0x7fb091525ec4 in __libc_start_main /build/eglibc-3GlaMS/eglibc-2.19/csu/libc-start.c:287

SUMMARY: AddressSanitizer: 1384 byte(s) leaked in 5 allocation(s).

[• dberlin]

Actually, sigh, we didn't do that already because we hand them back to the
user as well.
Anyway, i'm working up a patch to fix these.

[• dberlin]

This should hopefully fix all the leaks and asan errors (there is one real
bug here).
It is asan clean on OSX now, i am building on linux to do the leak check.

• fixasanissues.diff3 KBDownload

include/llvm/IR/Function.h

/// @}
   bool hasPrologueData() const {
     return getSubclassDataFromValue() & (1<<2);
   }
 
   /// \brief Get the prologue data associated with this function.
   Constant *getPrologueData() const;
   void setPrologueData(Constant *PrologueData);
 
+  /// Print the function to an output stream with an optional
+  /// AssemblyAnnotationWriter.
+  void print(raw_ostream &OS, AssemblyAnnotationWriter *AAW = nullptr,
+             bool ShouldPreserveUseListOrder = false,
+             bool IsForDebug = false) const;
+
   /// viewCFG - This function is meant for use from the debugger.  You can just
   /// say 'call F->viewCFG()' and a ghostview window should pop up from the
   /// program, displaying the CFG of the current function with the code for each
   /// basic block inside.  This depends on there being a 'dot' and 'gv' program
   /// in your path.
   ///
   void viewCFG() const;
 

include/llvm/InitializePasses.h

 void initializeMachineSchedulerPass(PassRegistry&);
 void initializeMachineSinkingPass(PassRegistry&);
 void initializeMachineTraceMetricsPass(PassRegistry&);
 void initializeMachineVerifierPassPass(PassRegistry&);
 void initializeMemCpyOptPass(PassRegistry&);
 void initializeMemDepPrinterPass(PassRegistry&);
 void initializeMemDerefPrinterPass(PassRegistry&);
 void initializeMemoryDependenceAnalysisPass(PassRegistry&);
+void initializeMemorySSALazyPass(PassRegistry&);
+void initializeMemorySSAPrinterPassPass(PassRegistry&);
 void initializeMergedLoadStoreMotionPass(PassRegistry &);
 void initializeMetaRenamerPass(PassRegistry&);
 void initializeMergeFunctionsPass(PassRegistry&);
 void initializeModuleDebugInfoPrinterPass(PassRegistry&);
 void initializeNaryReassociatePass(PassRegistry&);
 void initializeNoAAPass(PassRegistry&);
 void initializeObjCARCAAWrapperPassPass(PassRegistry&);
 void initializeObjCARCAPElimPass(PassRegistry&);

include/llvm/Transforms/Utils/MemorySSA.h

+//===- MemorySSA.h - Build Memory SSA ---------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// \file
+// \brief This file exposes an interface to building/using memory SSA to
+// walk memory instructions using a use/def graph
+
+// Memory SSA class builds an SSA form that links together memory access
+// instructions such loads, stores, atomics and calls.  Additionally, it does a
+// trivial form of "heap versioning" Every time the memory state changes in the
+// program, we generate a new heap version It generates MemoryDef/Uses/Phis that
+// are overlayed on top of the existing instructions
+
+// As a trivial example,
+// define i32 @main() #0 {
+// entry:
+//   %call = call noalias i8* @_Znwm(i64 4) #2
+//   %0 = bitcast i8* %call to i32*
+//   %call1 = call noalias i8* @_Znwm(i64 4) #2
+//   %1 = bitcast i8* %call1 to i32*
+//   store i32 5, i32* %0, align 4
+//   store i32 7, i32* %1, align 4
+//   %2 = load i32* %0, align 4
+//   %3 = load i32* %1, align 4
+//   %add = add nsw i32 %2, %3
+//   ret i32 %add
+// }
+// Will become
+//  define i32 @main() #0 {
+// entry:
+//   ; 1 = MemoryDef(0)
+//   %call = call noalias i8* @_Znwm(i64 4) #3
+//   %2 = bitcast i8* %call to i32*
+//   ; 2 = MemoryDef(1)
+//   %call1 = call noalias i8* @_Znwm(i64 4) #3
+//   %4 = bitcast i8* %call1 to i32*
+//   ; 3 = MemoryDef(2)
+//   store i32 5, i32* %2, align 4
+//   ; 4 = MemoryDef(3)
+//   store i32 7, i32* %4, align 4
+//   ; MemoryUse(4)
+//   %7 = load i32* %2, align 4
+//   ; MemoryUse(3)
+//   %8 = load i32* %4, align 4
+//   %add = add nsw i32 %7, %8
+//   ret i32 %add
+// }
+// Given this form, all the stores that could ever effect the load
+// at %8 can be gotten by using the memory use associated with it,
+// and walking from use to def until you hit the top of the function.
+
+// Each def also has a list of users associated with it, so you can walk from
+// both def to users, and users to defs.
+// Note that we disambiguate MemoryUse's, but not the RHS of memorydefs.
+// You can see this above at %8, which would otherwise be a MemoryUse(4)
+// Being disambiguated means that for a given store, all the MemoryUses on its
+// use lists are may-aliases of that store (but the MemoryDefs on its use list
+// may not be)
+//
+// MemoryDefs are not disambiguated because it would require multiple reaching
+// definitions, which would require multiple phis, and multiple memoryaccesses
+// per instruction.
+
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
+#define LLVM_TRANSFORMS_UTILS_MEMORYSSA_H
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/ADT/ilist_node.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include <list>
+
+namespace llvm {
+
+class BasicBlock;
+class DominatorTree;
+class Function;
+class MemoryAccess;
+template <class T> class memoryaccess_def_iterator_base;
+typedef memoryaccess_def_iterator_base<MemoryAccess> memoryaccess_def_iterator;
+typedef memoryaccess_def_iterator_base<const MemoryAccess>
+    const_memoryaccess_def_iterator;
+
+// \brief The base for all memory accesses. All memory accesses in a
+// block are linked together using an intrusive list.
+class MemoryAccess : public ilist_node<MemoryAccess> {
+public:
+  enum AccessType { AccessUse, AccessDef, AccessPhi };
+
+  // Methods for support type inquiry through isa, cast, and
+  // dyn_cast
+  static inline bool classof(const MemoryAccess *) { return true; }
+
+  virtual ~MemoryAccess();
+  BasicBlock *getBlock() const { return Block; }
+
+  /// \brief Get the instruction that this MemoryAccess represents.
+  /// This may be null in the case of phi nodes.
+  virtual Instruction *getMemoryInst() const = 0;
+
+  /// \brief Get the access that produces the memory state used by this access.
+  virtual MemoryAccess *getDefiningAccess() const = 0;
+
+  /// \brief Replace our defining access with a new one.
+  ///
+  /// This function updates use lists.
+  virtual void setDefiningAccess(MemoryAccess *) = 0;
+
+  virtual void print(raw_ostream &OS) const {};
+  virtual void dump() const;
+
+  typedef SmallPtrSet<MemoryAccess *, 8> UserListType;
+  typedef UserListType::iterator iterator;
+  typedef UserListType::const_iterator const_iterator;
+
+  unsigned user_size() const { return Users.size(); }
+  bool user_empty() const { return Users.empty(); }
+  iterator user_begin() { return Users.begin(); }
+  iterator user_end() { return Users.end(); }
+  iterator_range<iterator> users() {
+    return iterator_range<iterator>(user_begin(), user_end());
+  }
+
+  const_iterator user_begin() const { return Users.begin(); }
+  const_iterator user_end() const { return Users.end(); }
+  iterator_range<const_iterator> uses() const {
+    return iterator_range<const_iterator>(user_begin(), user_end());
+  }
+
+  /// \brief This iterator walks over all of the defs in a given
+  /// MemoryAccess. For MemoryPhi nodes, this walks arguments.  For
+  /// MemoryUse/MemoryDef, this walks the defining access.
+  memoryaccess_def_iterator defs_begin();
+  const_memoryaccess_def_iterator defs_begin() const;
+  memoryaccess_def_iterator defs_end();
+  const_memoryaccess_def_iterator defs_end() const;
+
+protected:
+  friend class MemorySSA;
+  friend class MemoryUse;
+  friend class MemoryDef;
+  friend class MemoryPhi;
+  AccessType getAccessType() const { return AccessType; }
+
+  /// \brief Set the instruction that this MemoryUse represents.
+  virtual void setMemoryInst(Instruction *MI) = 0;
+
+  /// \brief Add a use of this memory access to our list of uses.
+  ///
+  /// Note: We depend on being able to add the same use multiple times and not
+  /// have it end up in our use list multiple times.
+  void addUse(MemoryAccess *Use) { Users.insert(Use); }
+
+  /// \brief Remove a use of this memory access from our list of uses.
+  void removeUse(MemoryAccess *Use) { Users.erase(Use); }
+
+  /// \brief Return true if \p Use is one of the uses of this memory access.
+  bool hasUse(MemoryAccess *Use) { return Users.count(Use); }
+
+  MemoryAccess(AccessType AT, BasicBlock *BB) : AccessType(AT), Block(BB) {}
+
+  /// \brief Used internally to give IDs to MemoryAccesses for printing
+  virtual unsigned int getID() const = 0;
+
+private:
+  MemoryAccess(const MemoryAccess &);
+  void operator=(const MemoryAccess &);
+  AccessType AccessType;
+  BasicBlock *Block;
+  UserListType Users;
+};
+
+template <>
+struct ilist_traits<MemoryAccess> : public ilist_default_traits<MemoryAccess> {
+  // See details of the instruction class for why this trick works
+  MemoryAccess *createSentinel() const {
+    return static_cast<MemoryAccess *>(&Sentinel);
+  }
+
+  static void destroySentinel(MemoryAccess *) {}
+
+  MemoryAccess *provideInitialHead() const { return createSentinel(); }
+  MemoryAccess *ensureHead(MemoryAccess *) const { return createSentinel(); }
+  static void noteHead(MemoryAccess *, MemoryAccess *) {}
+
+private:
+  mutable ilist_half_node<MemoryAccess> Sentinel;
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const MemoryAccess &MA) {
+  MA.print(OS);
+  return OS;
+}
+
+/// \brief Represents read-only accesses to memory
+///
+/// In particular, the set of Instructions that will be represented by
+/// MemoryUse's is exactly the set of Instructions for which
+/// AliasAnalysis::getModRefInfo returns "Ref".
+class MemoryUse : public MemoryAccess {
+public:
+  MemoryUse(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB)
+      : MemoryUse(DMA, AccessUse, MI, BB) {}
+
+  virtual MemoryAccess *getDefiningAccess() const final {
+    return DefiningAccess;
+  }
+
+  virtual Instruction *getMemoryInst() const final { return MemoryInst; }
+
+  static inline bool classof(const MemoryUse *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessUse;
+  }
+  virtual void print(raw_ostream &OS) const;
+
+protected:
+  friend class MemorySSA;
+
+  MemoryUse(MemoryAccess *DMA, enum AccessType AT, Instruction *MI,
+            BasicBlock *BB)
+      : MemoryAccess(AT, BB), DefiningAccess(nullptr), MemoryInst(MI) {
+    setDefiningAccess(DMA);
+  }
+  virtual void setMemoryInst(Instruction *MI) final { MemoryInst = MI; }
+  virtual void setDefiningAccess(MemoryAccess *DMA) final {
+    if (DefiningAccess != DMA) {
+      if (DefiningAccess)
+        DefiningAccess->removeUse(this);
+      if (DMA)
+        DMA->addUse(this);
+    }
+    DefiningAccess = DMA;
+  }
+  virtual unsigned int getID() const {
+    llvm_unreachable("MemoryUse's do not have ID's");
+  }
+
+private:
+  MemoryAccess *DefiningAccess;
+  Instruction *MemoryInst;
+};
+
+/// \brief Represents a read-write access to memory, whether it is a must-alias,
+/// or a may-alias.
+///
+/// In particular, the set of Instructions that will be represented by
+/// MemoryDef's is exactly the set of Instructions for which
+/// AliasAnalysis::getModRefInfo returns "Mod" or "ModRef".
+/// Note that, in order to provide def-def chains, all defs also have a use
+/// associated with them.  This use points to the nearest reaching
+/// MemoryDef/MemoryPhi.
+class MemoryDef final : public MemoryUse {
+public:
+  MemoryDef(MemoryAccess *DMA, Instruction *MI, BasicBlock *BB, unsigned Ver)
+      : MemoryUse(DMA, AccessDef, MI, BB), ID(Ver) {}
+
+  static inline bool classof(const MemoryDef *) { return true; }
+  static inline bool classof(const MemoryUse *MA) {
+    return MA->getAccessType() == AccessDef;
+  }
+
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessDef;
+  }
+  virtual void print(raw_ostream &OS) const;
+
+protected:
+  friend class MemorySSA;
+  // For debugging only. This gets used to give memory accesses pretty numbers
+  // when printing them out
+
+  virtual unsigned int getID() const final { return ID; }
+
+private:
+  const unsigned int ID;
+};
+
+/// \brief Represents phi nodes for memory accesses.
+///
+/// These have the same semantic as regular phi nodes, with the exception that
+/// only one phi will ever exist in a given basic block.
+/// Guaranteeing one phi per block means guaranteeing there is only ever one
+/// valid reaching MemoryDef/MemoryPHI along each path to the phi node.
+/// This is ensured by not allowing disambiguation of the RHS of a MemoryDef or
+/// a MemoryPhi's operands.
+/// That is, given
+/// if (a) {
+///   store %a
+///   store %b
+/// }
+/// it *must* be transformed into
+/// if (a) {
+///    1 = MemoryDef(liveOnEntry)
+///    store %a
+///    2 = MemoryDef(1)
+///    store %b
+/// }
+/// and *not*
+/// if (a) {
+///    1 = MemoryDef(liveOnEntry)
+///    store %a
+///    2 = MemoryDef(liveOnEntry)
+///    store %b
+/// }
+/// even if the two stores do not conflict.  Otherwise, both 1 and 2 reach the
+/// end of the branch, and if there are not two phi nodes, one will be
+/// disconnected completely from the SSA graph below that point.
+/// Because MemoryUse's do not generate new definitions, they do not have this
+/// issue.
+class MemoryPhi final : public MemoryAccess {
+public:
+  MemoryPhi(BasicBlock *BB, unsigned int NP, unsigned int Ver)
+      : MemoryAccess(AccessPhi, BB), ID(Ver), NumPreds(NP) {
+    Operands.reserve(NumPreds);
+  }
+
+  virtual Instruction *getMemoryInst() const final {
+    llvm_unreachable(
+        "MemoryPhi's do not have a memory instruction associated with them");
+  }
+
+  virtual MemoryAccess *getDefiningAccess() const final {
+    llvm_unreachable("MemoryPhi's do not have a single defining access");
+  }
+
+  /// \brief This is the number of actual predecessors this phi node has.
+  unsigned int getNumPreds() const { return NumPreds; }
+
+  /// \brief This is the number of incoming values currently in use
+  ///
+  /// During SSA construction, we differentiate between this and NumPreds to
+  /// know when the PHI node is fully constructed.
+  unsigned int getNumIncomingValues() const { return Operands.size(); }
+
+  /// \brief Set the memory access of argument \p v of this phi node to be \p MA
+  ///
+  /// This function updates use lists.
+  void setIncomingValue(unsigned int v, MemoryAccess *MA) {
+    std::pair<BasicBlock *, MemoryAccess *> &Val = Operands[v];
+    // We need to update use lists.  Because our uses are not to specific
+    // operands, but instead to this MemoryAccess, and because a given memory
+    // access may appear multiple times in the phi argument list, we need to be
+    // careful not to remove the use of this phi, from MA, until we check to
+    // make sure MA does not appear elsewhere in the phi argument list.
+    if (Val.second != MA) {
+      if (Val.second) {
+        bool existsElsewhere = false;
+        for (unsigned i = 0, e = Operands.size(); i != e; ++i) {
+          if (i == v)
+            continue;
+          if (Operands[i].second == Val.second)
+            existsElsewhere = true;
+        }
+        if (!existsElsewhere)
+          Val.second->removeUse(this);
+      }
+      MA->addUse(this);
+      Val.second = MA;
+    }
+  }
+
+  MemoryAccess *getIncomingValue(unsigned int v) const {
+    return Operands[v].second;
+  }
+  void setIncomingBlock(unsigned int v, BasicBlock *BB) {
+    std::pair<BasicBlock *, MemoryAccess *> &Val = Operands[v];
+    Val.first = BB;
+  }
+  BasicBlock *getIncomingBlock(unsigned int v) const {
+    return Operands[v].first;
+  }
+
+  typedef SmallVector<std::pair<BasicBlock *, MemoryAccess *>, 8> OperandsType;
+  typedef OperandsType::const_iterator const_op_iterator;
+  inline const_op_iterator ops_begin() const { return Operands.begin(); }
+  inline const_op_iterator ops_end() const { return Operands.end(); }
+  inline iterator_range<const_op_iterator> operands() const {
+    return iterator_range<const_op_iterator>(ops_begin(), ops_end());
+  }
+
+  static inline bool classof(const MemoryPhi *) { return true; }
+  static inline bool classof(const MemoryAccess *MA) {
+    return MA->getAccessType() == AccessPhi;
+  }
+
+  virtual void print(raw_ostream &OS) const;
+
+protected:
+  friend class MemorySSA;
+
+  virtual void setDefiningAccess(MemoryAccess *) final {
+    llvm_unreachable("MemoryPhi's do not have a single defining access");
+  }
+  virtual void setMemoryInst(Instruction *MI) final {}
+
+  // MemorySSA currently cannot handle edge additions or deletions (but can
+  // handle direct replacement).  This is protected to ensure people don't try.
+  void addIncoming(MemoryAccess *MA, BasicBlock *BB) {
+    Operands.push_back(std::make_pair(BB, MA));
+    MA->addUse(this);
+  }
+
+  // For debugging only. This gets used to give memory accesses pretty numbers
+  // when printing them out
+  virtual unsigned int getID() const final { return ID; }
+
+private:
+  // For debugging only
+  const unsigned ID;
+  unsigned NumPreds;
+  OperandsType Operands;
+};
+
+class MemorySSAWalker;
+
+/// \brief Encapsulates MemorySSA, including all data associated with memory
+/// accesses.
+class MemorySSA {
+public:
+  MemorySSA(Function &);
+  ~MemorySSA();
+
+  /// \brief Build Memory SSA, and return the walker we used during building,
+  /// for later reuse.  If MemorySSA is already built, just return the walker.
+  MemorySSAWalker *buildMemorySSA(AliasAnalysis *, DominatorTree *);
+  bool isFinishedBuilding() const { return builtAlready; }
+
+  /// \brief Given a memory Mod/Ref'ing instruction, get the MemorySSA
+  /// access associaed with it.  If passed a basic block gets the memory phi
+  /// node that exists for that block, if there is one.
+  MemoryAccess *getMemoryAccess(const Value *) const;
+  void dump() const;
+  void print(raw_ostream &) const;
+
+  /// \brief Return true if \p MA represents the live on entry value
+  ///
+  /// Loads and stores from pointer arguments and other global values may be
+  /// defined by memory operations that do not occur in the current function, so
+  /// they may be live on entry to the function.  MemorySSA represents such
+  /// memory state by the live on entry definition, which is guaranteed to
+  /// occurr before any other memory access in the function.
+  inline bool isLiveOnEntryDef(const MemoryAccess *MA) const {
+    return MA == LiveOnEntryDef;
+  }
+
+  inline MemoryAccess *getLiveOnEntryDef() const {
+    assert(LiveOnEntryDef && "Live on entry def not initialized yet");
+    return LiveOnEntryDef;
+  }
+
+  typedef iplist<MemoryAccess> AccessListType;
+
+  /// \brief Return the list of MemoryAccess's for a given basic block.
+  ///
+  /// This list is not modifiable by the user.
+  const AccessListType *getBlockAccesses(const BasicBlock *BB) const {
+    auto It = PerBlockAccesses.find(BB);
+    if (It == PerBlockAccesses.end())
+      return nullptr;
+    return It->second.get();
+  }
+
+  /// \brief Remove a MemoryAccess from MemorySSA, including updating all
+  /// definitions and uses.
+  /// This should be called when a memory instruction that has a MemoryAccess
+  /// associated with it is erased from the program.  For example, if a store or
+  /// load is simply erased (not replaced), removeMemoryAccess should be called
+  /// on the MemoryAccess for that store/load.
+  void removeMemoryAccess(MemoryAccess *);
+
+  /// \brief Replace one MemoryAccess with another, including updating all
+  /// definitions and uses.
+  /// This should be called when one memory instruction is being replaced with
+  /// another.  For example, during GVN, a load may be replaced with another
+  /// existing load. This function should be called to let MemorySSA know that
+  /// this has happened
+  void replaceMemoryAccess(MemoryAccess *Replacee, MemoryAccess *Replacer);
+
+  enum InsertionPlace { Beginning, End };
+
+  /// \brief Replace a MemoryAccess with a new access, created based on
+  /// instruction \p Replacer - this does not perform generic SSA updates, so it
+  /// only works if the new access dominates the old accesses uses.
+  ///
+  /// This API should be used if a new memory instruction has been added that is
+  /// being used to replace an existing one.  For example, during store sinking,
+  /// we may replace  a store sunk further down the CFG.  In that
+  /// case, this function should be called with the MemoryAccess for the
+  /// original store, and the new instruction replacing it.
+  /// We may also merge two stores in two branches into a store after the
+  /// branch.
+  /// For example, we may have
+  /// if (a) {
+  ///   1 = MemoryDef(liveOnEntry)
+  ///   store %a
+  /// } else {
+  ///   2 = MemoryDef(liveOnEntry)
+  ///   store %a
+  /// }
+  /// 3 = MemoryPhi(1, 2)
+  /// MemoryUse(3)
+  /// load %a
+  /// If the store is sunk below the branch, the correct update would be to call
+  /// tihs function with the MemoryPhi and the new store, and removeAccess on
+  /// the two old stores.
+  /// This version places the access at either the end or the beginning of \p
+  /// Replacer's block, depending on the value of \p Where.
+  ///
+  /// \returns the new access that was created.
+  MemoryAccess *replaceMemoryAccessWithNewAccess(MemoryAccess *Replacee,
+                                                 Instruction *Replacer,
+                                                 enum InsertionPlace Where);
+  /// \brief Replace a MemoryAccess with a new access, created based on
+  /// instruction \p Replacer - this does not perform generic SSA updates, so it
+  /// only works if the new access dominates the old accesses uses.
+  ///
+  /// This version places the access before the place that \p Where points to.
+  MemoryAccess *
+  replaceMemoryAccessWithNewAccess(MemoryAccess *Replacee,
+                                   Instruction *Replacer,
+                                   const AccessListType::iterator &Where);
+
+  /// \brief Add a new MemoryUse for \p Use at the beginning or end of a block.
+  ///
+  /// This API is used to add MemoryUse's for new loads (or other memory Ref'ing
+  /// instructions) to MemorySSA.  For example, if a load is hoisted and the old
+  /// load eliminated, the proper update is to call addNewMemoryUse on the new
+  /// load, and then replaceMemoryAccess with (old load, new load).
+  MemoryAccess *addNewMemoryUse(Instruction *Use, enum InsertionPlace Where);
+
+  /// \brief Given two memory accesses in the same basic block, determine
+  /// whether MemoryAccess \p A dominates MemoryAccess \p B.
+  bool locallyDominates(const MemoryAccess *A, const MemoryAccess *B) const;
+
+protected:
+  // Used by Memory SSA annotater, dumpers, and wrapper pass
+  friend class MemorySSAAnnotatedWriter;
+  friend class MemorySSAPrinterPass;
+  void verifyDefUses(Function &F);
+  void verifyDomination(Function &F);
+
+private:
+  void verifyUseInDefs(MemoryAccess *, MemoryAccess *);
+  typedef DenseMap<const BasicBlock *, std::unique_ptr<AccessListType>>
+      AccessMap;
+
+  void
+  determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
+  void computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels);
+  void markUnreachableAsLiveOnEntry(BasicBlock *BB);
+  bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
+  void removeFromLookups(MemoryAccess *);
+  MemoryAccess *createNewAccess(Instruction *, bool ignoreNonMemory = false);
+  MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
+
+  MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *);
+  void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
+                  SmallPtrSet<BasicBlock *, 16> &Visited);
+  std::unique_ptr<AccessListType> &getOrCreateAccessList(BasicBlock *);
+  bool replaceAllOccurrences(MemoryPhi *, MemoryAccess *, MemoryAccess *);
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+  Function &F;
+
+  // Memory SSA mappings
+  DenseMap<const Value *, MemoryAccess *> InstructionToMemoryAccess;
+  AccessMap PerBlockAccesses;
+  MemoryAccess *LiveOnEntryDef;
+
+  // Memory SSA building info
+  unsigned int nextID;
+  bool builtAlready;
+  MemorySSAWalker *Walker;
+};
+
+// This pass does eager building and then printing of MemorySSA. It is used by
+// the tests to be able to build, dump, and verify Memory SSA.
+
+class MemorySSAPrinterPass : public FunctionPass {
+public:
+  MemorySSAPrinterPass();
+
+  static char ID;
+  bool doInitialization(Module &M) override;
+  bool runOnFunction(Function &) override;
+  void releaseMemory() override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void print(raw_ostream &OS, const Module *M) const override;
+  static void registerOptions();
+  MemorySSA &getMSSA() { return *MSSA; }
+
+private:
+  bool VerifyMemorySSA;
+
+  MemorySSA *MSSA;
+  MemorySSAWalker *Walker;
+  Function *F;
+};
+
+class MemorySSALazy : public FunctionPass {
+public:
+  MemorySSALazy();
+
+  static char ID;
+  bool runOnFunction(Function &) override;
+  void releaseMemory() override;
+  MemorySSA &getMSSA() { return *MSSA; }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+private:
+  MemorySSA *MSSA;
+};
+
+/// \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
+/// disambiguate memory accesses, or they may want the nearest dominating
+/// may-aliasing MemoryDef for a call or a store.  This API enables a
+/// standardized interface to getting and using that info.
+
+class MemorySSAWalker {
+public:
+  MemorySSAWalker(MemorySSA *);
+  virtual ~MemorySSAWalker() {}
+
+  typedef SmallVector<MemoryAccess *, 8> MemoryAccessSet;
+  /// \brief Given a memory Mod/Ref/ModRef'ing instruction, calling this
+  /// will give you the nearest dominating MemoryAccess that Mod's the location
+  /// the instruction accesses (by skipping any def which AA can prove does not
+  /// alias the location(s) accessed by the instruction given).
+  ///
+  /// Note that this will return a single access, and it must dominate the
+  /// Instruction, so if an operand of a MemoryPhi node Mod's the instruction,
+  /// this will return the MemoryPhi, not the operand.  This means that
+  /// given:
+  /// if (a) {
+  ///   1 = MemoryDef(liveOnEntry)
+  ///   store %a
+  /// } else {
+  ///   2 = MemoryDef(liveOnEntry)
+  ///    store %b
+  /// }
+  /// 3 = MemoryPhi(2, 1)
+  /// MemoryUse(3)
+  /// load %a
+  ///
+  /// calling this API on load(%a) will return the MemoryPhi, not the MemoryDef
+  /// in the if (a) branch.
+  virtual MemoryAccess *getClobberingMemoryAccess(const Instruction *) = 0;
+
+  /// \brief Given a potentially clobbering memory access and a new location,
+  /// calling this will give you the nearest dominating clobbering MemoryAccess
+  /// (by skipping non-aliasing def links).
+  ///
+  /// This version of the function is mainly used to disambiguate phi translated
+  /// pointers, where the value of a pointer may have changed from the initial
+  /// memory access.  Note that this expects to be handed either a memory use,
+  /// or an already potentially clobbering access.  Unlike the above API, if
+  /// given a MemoryDef that clobbers the pointer as the starting access, it
+  /// will return that MemoryDef, whereas the above would return the clobber
+  /// starting from the use side of  the memory def.
+  virtual MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                                  MemoryLocation &) = 0;
+
+  /// \brief Given a memory access, invalidate anything this walker knows about
+  /// that access.
+  /// This API is used by walkers that store information to perform basic cache
+  /// invalidation.  This will be called by MemorySSA at appropriate times for
+  /// the walker it uses or returns through getWalker.
+  virtual void invalidateInfo(MemoryAccess *){};
+
+protected:
+  MemorySSA *MSSA;
+};
+
+/// \brief A MemorySSAWalker that does no alias queries, or anything else. It
+/// simply returns the links as they were constructed by the builder.
+class DoNothingMemorySSAWalker final : public MemorySSAWalker {
+public:
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          MemoryLocation &) override;
+};
+typedef std::pair<MemoryAccess *, MemoryLocation> MemoryAccessPair;
+typedef std::pair<const MemoryAccess *, MemoryLocation> ConstMemoryAccessPair;
+
+/// \brief A MemorySSAWalker that does AA walks and caching of lookups to
+/// disambiguate accesses.
+class CachingMemorySSAWalker final : public MemorySSAWalker {
+public:
+  CachingMemorySSAWalker(MemorySSA *, AliasAnalysis *, DominatorTree *);
+  virtual ~CachingMemorySSAWalker();
+  MemoryAccess *getClobberingMemoryAccess(const Instruction *) override;
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          MemoryLocation &) override;
+  void invalidateInfo(MemoryAccess *) override;
+
+protected:
+  struct UpwardsMemoryQuery;
+  MemoryAccess *doCacheLookup(const MemoryAccess *, const UpwardsMemoryQuery &,
+                              const MemoryLocation &);
+
+  void doCacheInsert(const MemoryAccess *, MemoryAccess *,
+                     const UpwardsMemoryQuery &, const MemoryLocation &);
+
+  void doCacheRemove(const MemoryAccess *, const UpwardsMemoryQuery &,
+                     const MemoryLocation &);
+
+private:
+  MemoryAccessPair UpwardsDFSWalk(MemoryAccess *, const MemoryLocation &,
+                                  UpwardsMemoryQuery &, bool);
+
+  typedef SmallDenseMap<MemoryAccessPair, MemoryAccessPair> PathMap;
+  std::pair<MemoryAccess *, MemoryLocation>
+  UpwardsBFSWalkAccess(MemoryAccess *, const MemoryLocation &, PathMap &,
+                       struct UpwardsMemoryQuery &);
+  MemoryAccess *getClobberingMemoryAccess(MemoryAccess *,
+                                          struct UpwardsMemoryQuery &);
+  MemoryAccessPair
+  findDominatingAccess(const MemoryAccess *, const MemoryAccessPair &,
+                       const PathMap &,
+                       const struct UpwardsMemoryQuery &) const;
+  bool instructionClobbersQuery(const MemoryDef *, struct UpwardsMemoryQuery &,
+                                const MemoryLocation &Loc) const;
+  SmallDenseMap<ConstMemoryAccessPair, MemoryAccess *>
+      CachedUpwardsClobberingAccess;
+  DenseMap<const MemoryAccess *, MemoryAccess *> CachedUpwardsClobberingCall;
+  AliasAnalysis *AA;
+  DominatorTree *DT;
+};
+
+/// \brief Iterator base class used to implement const and non-const iterators
+/// over the defining accesses of a MemoryAccess.
+template <class T>
+class memoryaccess_def_iterator_base
+    : public iterator_facade_base<memoryaccess_def_iterator_base<T>,
+                                  std::forward_iterator_tag, T, ptrdiff_t, T *,
+                                  T *> {
+  typedef typename memoryaccess_def_iterator_base::iterator_facade_base BaseT;
+
+public:
+  memoryaccess_def_iterator_base(T *Start) : Access(Start), ArgNo(0) {}
+  memoryaccess_def_iterator_base() : Access(nullptr), ArgNo(0) {}
+  bool operator==(const memoryaccess_def_iterator_base &Other) const {
+    if (Access == nullptr)
+      return Other.Access == nullptr;
+    return Access == Other.Access && ArgNo == Other.ArgNo;
+  }
+
+  // This is a bit ugly, but for MemoryPHI's, unlike PHINodes, you can't get the
+  // block from the operand in constant time (In a PHINode, the uselist has
+  // both, so it's just subtraction).  We provide it as part of the
+  // iterator to avoid callers having to linear walk to get the block.
+  // If the operation becomes constant time on MemoryPHI's, this bit of
+  // abstraction breaking should be removed.
+  BasicBlock *getPhiArgBlock() const {
+    MemoryPhi *MP = dyn_cast<MemoryPhi>(Access);
+    assert(MP && "Tried to get phi arg block when not iterating over a PHI");
+    return MP->getIncomingBlock(ArgNo);
+  }
+  typename BaseT::iterator::pointer operator*() const {
+    assert(Access && "Tried to access past the end of our iterator");
+    // Go to the first argument for phis, and the defining access for everything
+    // else.
+    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access))
+      return MP->getIncomingValue(ArgNo);
+    return Access->getDefiningAccess();
+  }
+  using BaseT::operator++;
+  memoryaccess_def_iterator &operator++() {
+    assert(Access && "Hit end of iterator");
+    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(Access)) {
+      if (++ArgNo >= MP->getNumIncomingValues()) {
+        ArgNo = 0;
+        Access = nullptr;
+      }
+    } else {
+      Access = nullptr;
+    }
+    return *this;
+  }
+
+private:
+  T *Access;
+  unsigned ArgNo;
+};
+
+inline memoryaccess_def_iterator MemoryAccess::defs_begin() {
+  return memoryaccess_def_iterator(this);
+}
+inline const_memoryaccess_def_iterator MemoryAccess::defs_begin() const {
+  return const_memoryaccess_def_iterator(this);
+}
+
+inline memoryaccess_def_iterator MemoryAccess::defs_end() {
+  return memoryaccess_def_iterator();
+}
+
+inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
+  return const_memoryaccess_def_iterator();
+}
+
+/// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case,
+/// and uses in the inverse case.
+template <> struct GraphTraits<MemoryAccess *> {
+  typedef MemoryAccess NodeType;
+  typedef memoryaccess_def_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(NodeType *N) { return N; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->defs_begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->defs_end();
+  }
+};
+
+template <> struct GraphTraits<Inverse<MemoryAccess *>> {
+  typedef MemoryAccess NodeType;
+  typedef MemoryAccess::iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(NodeType *N) { return N; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->user_begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->user_end();
+  }
+};
+
+/// \brief Provide an iterator that walks defs, giving both the memory access,
+/// and the current pointer location, updating the pointer location as it
+/// changes due to phi node translation.
+///
+/// This iterator, while somewhat specialized, is what most clients actually
+/// want when walking upwards through MemorySSA def chains.  It takes a pair of
+/// <MemoryAccess,MemoryLocation>, and walks defs, properly translating the
+/// memory location through phi nodes for the user.
+class upward_defs_iterator
+    : public iterator_facade_base<upward_defs_iterator,
+                                  std::forward_iterator_tag,
+                                  const MemoryAccessPair> {
+  typedef typename upward_defs_iterator::iterator_facade_base BaseT;
+
+public:
+  upward_defs_iterator(const MemoryAccessPair &Info)
+      : DefIterator(Info.first), Location(Info.second),
+        OriginalAccess(Info.first) {
+    CurrentPair.first = nullptr;
+
+    if (Info.first)
+      WalkingPhi = isa<MemoryPhi>(Info.first);
+    fillInCurrentPair();
+  }
+  upward_defs_iterator() : DefIterator(), Location(), OriginalAccess() {
+    CurrentPair.first = nullptr;
+  }
+  bool operator==(const upward_defs_iterator &Other) const {
+    return DefIterator == Other.DefIterator;
+  }
+
+  typename BaseT::iterator::reference operator*() const {
+    assert(DefIterator != OriginalAccess->defs_end() &&
+           "Tried to access past the end of our iterator");
+    return CurrentPair;
+  }
+  using BaseT::operator++;
+
+  upward_defs_iterator &operator++() {
+    assert(DefIterator != OriginalAccess->defs_end() &&
+           "Tried to access past the end of the iterator");
+    ++DefIterator;
+    if (DefIterator != OriginalAccess->defs_end())
+      fillInCurrentPair();
+    return *this;
+  }
+
+  BasicBlock *getPhiArgBlock() const { return DefIterator.getPhiArgBlock(); }
+
+private:
+  void fillInCurrentPair() {
+    CurrentPair.first = *DefIterator;
+    if (WalkingPhi && Location.Ptr) {
+      PHITransAddr Translator(
+          const_cast<Value *>(Location.Ptr),
+          OriginalAccess->getBlock()->getModule()->getDataLayout(), nullptr);
+      if (!Translator.PHITranslateValue(OriginalAccess->getBlock(),
+                                        DefIterator.getPhiArgBlock(), nullptr,
+                                        false))
+        if (Translator.getAddr() != Location.Ptr) {
+          CurrentPair.second = Location.getWithNewPtr(Translator.getAddr());
+          return;
+        }
+    }
+    CurrentPair.second = Location;
+  }
+
+  MemoryAccessPair CurrentPair;
+  memoryaccess_def_iterator DefIterator;
+  MemoryLocation Location;
+  bool WalkingPhi;
+  MemoryAccess *OriginalAccess;
+};
+
+inline upward_defs_iterator upward_defs_begin(const MemoryAccessPair &Pair) {
+  return upward_defs_iterator(Pair);
+}
+inline upward_defs_iterator upward_defs_end() { return upward_defs_iterator(); }
+}
+
+#endif

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
   initializeLazyValueInfoPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
+  initializeMemorySSALazyPass(Registry);
+  initializeMemorySSAPrinterPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
   initializePostDominatorTreePass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);

lib/IR/AsmWriter.cpp

while (hasMore()) {
     UseListOrders.pop_back();
   }
 }
 
 //===----------------------------------------------------------------------===//
 //                       External Interface declarations
 //===----------------------------------------------------------------------===//
 
+void Function::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW,
+                     bool ShouldPreserveUseListOrder,
+                     bool IsForDebug) const {
+  SlotTracker SlotTable(this->getParent());
+  formatted_raw_ostream OS(ROS);
+  AssemblyWriter W(OS, SlotTable, this->getParent(), AAW,
+                   IsForDebug,
+                   ShouldPreserveUseListOrder);
+  W.printFunction(this);
+}
+
 void Module::print(raw_ostream &ROS, AssemblyAnnotationWriter *AAW,
                    bool ShouldPreserveUseListOrder, bool IsForDebug) const {
   SlotTracker SlotTable(this);
   formatted_raw_ostream OS(ROS);
   AssemblyWriter W(OS, SlotTable, this, AAW, IsForDebug,
                    ShouldPreserveUseListOrder);
   W.printModule(this);
 }

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LoopSimplify.cpp
   LoopUnroll.cpp
   LoopUnrollRuntime.cpp
   LoopUtils.cpp
   LoopVersioning.cpp
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
+  MemorySSA.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   PromoteMemoryToRegister.cpp
   SSAUpdater.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp
   SimplifyLibCalls.cpp

lib/Transforms/Utils/MemorySSA.cpp

+//===-- MemorySSA.cpp - Memory SSA Builder---------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------===//
+//
+// This file implements the MemorySSA class.
+//
+//===----------------------------------------------------------------===//
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
+#include "llvm/Analysis/MemoryLocation.h"
+#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/IR/AssemblyAnnotationWriter.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/Module.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/FormattedStream.h"
+#include "llvm/Transforms/Utils/MemorySSA.h"
+#include <algorithm>
+#include <queue>
+
+#define DEBUG_TYPE "memoryssa"
+using namespace llvm;
+STATISTIC(NumClobberCacheLookups, "Number of Memory SSA version cache lookups");
+STATISTIC(NumClobberCacheHits, "Number of Memory SSA version cache hits");
+STATISTIC(NumClobberCacheInserts, "Number of MemorySSA version cache inserts");
+INITIALIZE_PASS_WITH_OPTIONS_BEGIN(MemorySSAPrinterPass, "print-memoryssa",
+                                   "Memory SSA", true, true)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
+INITIALIZE_PASS_END(MemorySSAPrinterPass, "print-memoryssa", "Memory SSA", true,
+                    true)
+INITIALIZE_PASS(MemorySSALazy, "memoryssalazy", "Memory SSA", true, true)
+
+namespace llvm {
+
+/// \brief An assembly annotator class to print Memory SSA information in
+/// comments.
+class MemorySSAAnnotatedWriter : public AssemblyAnnotationWriter {
+  friend class MemorySSA;
+  const MemorySSA *MSSA;
+
+public:
+  MemorySSAAnnotatedWriter(const MemorySSA *M) : MSSA(M) {}
+
+  virtual void emitBasicBlockStartAnnot(const BasicBlock *BB,
+                                        formatted_raw_ostream &OS) {
+    MemoryAccess *MA = MSSA->getMemoryAccess(BB);
+    if (MA)
+      OS << "; " << *MA << "\n";
+  }
+
+  virtual void emitInstructionAnnot(const Instruction *I,
+                                    formatted_raw_ostream &OS) {
+    MemoryAccess *MA = MSSA->getMemoryAccess(I);
+    if (MA)
+      OS << "; " << *MA << "\n";
+  }
+};
+}
+
+namespace {
+struct RenamePassData {
+  DomTreeNode *DTN;
+  DomTreeNode::const_iterator ChildIt;
+  MemoryAccess *IncomingVal;
+
+  RenamePassData(DomTreeNode *D, DomTreeNode::const_iterator It,
+                 MemoryAccess *M)
+      : DTN(D), ChildIt(It), IncomingVal(M) {}
+  void swap(RenamePassData &RHS) {
+    std::swap(DTN, RHS.DTN);
+    std::swap(ChildIt, RHS.ChildIt);
+    std::swap(IncomingVal, RHS.IncomingVal);
+  }
+};
+}
+
+namespace llvm {
+
+/// \brief Rename a single basic block into MemorySSA form.
+/// Uses the standard SSA renaming algorithm.
+/// \returns The new incoming value.
+MemoryAccess *MemorySSA::renameBlock(BasicBlock *BB,
+                                     MemoryAccess *IncomingVal) {
+  auto It = PerBlockAccesses.find(BB);
+  // Skip most processing if the list is empty.
+  if (It != PerBlockAccesses.end()) {
+    auto &Accesses = It->second;
+    for (auto &L : *Accesses) {
+      if (isa<MemoryPhi>(L)) {
+        IncomingVal = &L;
+      } else if (MemoryUse *MU = dyn_cast<MemoryUse>(&L)) {
+        MU->setDefiningAccess(IncomingVal);
+      } else if (MemoryDef *MD = dyn_cast<MemoryDef>(&L)) {
+        // We can't legally optimize defs, because we only allow single
+        // memory phis/uses on operations, and if we optimize these, we can
+        // end up with multiple reaching defs.  Uses do not have this
+        // problem, since they do not produce a value
+        MD->setDefiningAccess(IncomingVal);
+        IncomingVal = MD;
+      }
+    }
+  }
+
+  // Pass through values to our successors
+  for (auto S : successors(BB)) {
+    auto It = PerBlockAccesses.find(S);
+    // Rename the phi nodes in our successor block
+    if (It != PerBlockAccesses.end() && isa<MemoryPhi>(It->second->front())) {
+      auto &Accesses = It->second;
+      MemoryPhi *Phi = cast<MemoryPhi>(&Accesses->front());
+      unsigned NumEdges = std::count(succ_begin(BB), succ_end(BB), S);
+      assert(NumEdges && "Must be at least one edge from Succ to BB!");
+      for (unsigned i = 0; i != NumEdges; ++i)
+        Phi->addIncoming(IncomingVal, BB);
+    }
+  }
+  return IncomingVal;
+}
+
+/// \brief This is the standard SSA renaming algorithm.
+///
+/// We walk the dominator tree in preorder, renaming accesses, and then filling
+/// in phi nodes in our successors.
+void MemorySSA::renamePass(DomTreeNode *Root, MemoryAccess *IncomingVal,
+                           SmallPtrSet<BasicBlock *, 16> &Visited) {
+  SmallVector<RenamePassData, 32> WorkStack;
+  IncomingVal = renameBlock(Root->getBlock(), IncomingVal);
+  WorkStack.push_back({Root, Root->begin(), IncomingVal});
+  Visited.insert(Root->getBlock());
+
+  while (!WorkStack.empty()) {
+    DomTreeNode *Node = WorkStack.back().DTN;
+    DomTreeNode::const_iterator ChildIt = WorkStack.back().ChildIt;
+    IncomingVal = WorkStack.back().IncomingVal;
+
+    if (ChildIt == Node->end()) {
+      WorkStack.pop_back();
+    } else {
+      DomTreeNode *Child = *ChildIt;
+      ++WorkStack.back().ChildIt;
+      BasicBlock *BB = Child->getBlock();
+      Visited.insert(BB);
+      IncomingVal = renameBlock(BB, IncomingVal);
+      WorkStack.push_back({Child, Child->begin(), IncomingVal});
+    }
+  }
+}
+
+/// \brief Compute dominator levels, used by the phi insertion algorithm above.
+void MemorySSA::computeDomLevels(DenseMap<DomTreeNode *, unsigned> &DomLevels) {
+  for (auto DFI = df_begin(DT->getRootNode()), DFE = df_end(DT->getRootNode());
+       DFI != DFE; ++DFI)
+    DomLevels[*DFI] = DFI.getPathLength() - 1;
+}
+
+/// \brief This handles unreachable block acccesses by deleting phi nodes in
+/// unreachable blocks, and marking all other unreachable MemoryAccess's as
+/// being uses of the live on entry definition.
+void MemorySSA::markUnreachableAsLiveOnEntry(BasicBlock *BB) {
+  assert(!DT->isReachableFromEntry(BB) &&
+         "Reachable block found while handling unreachable blocks");
+
+  auto It = PerBlockAccesses.find(BB);
+  if (It == PerBlockAccesses.end())
+    return;
+
+  auto &Accesses = It->second;
+  for (auto AI = Accesses->begin(), AE = Accesses->end(); AI != AE;) {
+    auto Next = std::next(AI);
+    // If we have a phi, just remove it. We are going to replace all
+    // users with live on entry.
+    if (isa<MemoryPhi>(&*AI)) {
+      Accesses->erase(AI);
+    } else {
+      AI->setDefiningAccess(LiveOnEntryDef);
+    }
+    AI = Next;
+  }
+}
+
+MemorySSA::MemorySSA(Function &Func)
+    : F(Func), LiveOnEntryDef(nullptr), nextID(0), builtAlready(false),
+      Walker(nullptr) {}
+
+MemorySSA::~MemorySSA() {
+  InstructionToMemoryAccess.clear();
+  PerBlockAccesses.clear();
+  delete LiveOnEntryDef;
+}
+std::unique_ptr<MemorySSA::AccessListType> &
+MemorySSA::getOrCreateAccessList(BasicBlock *BB) {
+  auto Res = PerBlockAccesses.insert(std::make_pair(BB, nullptr));
+  if (Res.second) {
+    Res.first->second = make_unique<AccessListType>(); // AccessListType();
+  }
+  return Res.first->second;
+}
+
+MemorySSAWalker *MemorySSA::buildMemorySSA(AliasAnalysis *AA,
+                                           DominatorTree *DT) {
+  if (builtAlready)
+    return Walker;
+  else
+    Walker = new CachingMemorySSAWalker(this, AA, DT);
+
+  this->AA = AA;
+  this->DT = DT;
+
+  // We create an access to represent "live on entry", for things like
+  // arguments or users of globals, where the memory they use is defined before
+  // the beginning of the function. We do not actually insert it in to the IR.
+  // We do not define a live on exit for the immediate uses, and thus our
+  // semantics do *not* imply that something with no immediate uses can simply
+  // be
+  // removed.
+  BasicBlock &StartingPoint = F.getEntryBlock();
+  LiveOnEntryDef = new MemoryDef(nullptr, nullptr, &StartingPoint, nextID++);
+
+  // We maintain lists of memory accesses per-block, trading memory for time. We
+  // could just look up the memory access for every possible instruction in the
+  // stream.
+  SmallPtrSet<BasicBlock *, 32> DefiningBlocks;
+
+  // Go through each block, figure out where defs occur, and chain together all
+  // the accesses.
+  for (auto &B : F) {
+    AccessListType *Accesses = nullptr;
+    for (auto &I : B) {
+      MemoryAccess *MA = createNewAccess(&I, true);
+      if (!MA)
+        continue;
+      if (isa<MemoryDef>(MA))
+        DefiningBlocks.insert(&B);
+      if (!Accesses)
+        Accesses = getOrCreateAccessList(&B).get();
+      Accesses->push_back(MA);
+    }
+  }
+
+  // Determine where our MemoryPhi's should go
+  IDFCalculator IDFs(*DT);
+  IDFs.setDefiningBlocks(DefiningBlocks);
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  IDFs.calculate(IDFBlocks);
+
+  // Now place MemoryPhi nodes.
+  for (auto &BB : IDFBlocks) {
+    // Insert phi node
+    auto &Accesses = getOrCreateAccessList(BB);
+    MemoryPhi *Phi = new MemoryPhi(
+        BB, std::distance(pred_begin(BB), pred_end(BB)), nextID++);
+    InstructionToMemoryAccess.insert(std::make_pair(BB, Phi));
+    // Phi's always are placed at the front of the block.
+    Accesses->push_front(Phi);
+  }
+
+  // Now do regular SSA renaming on the MemoryDef/MemoryUse. Visited will get
+  // filled in with all blocks.
+  SmallPtrSet<BasicBlock *, 16> Visited;
+  renamePass(DT->getRootNode(), LiveOnEntryDef, Visited);
+  // Now optimize the MemoryUse's defining access to point to the nearest
+  // dominating clobbering def.
+  // This ensures that MemoryUse's that are killed by the same store are
+  // immediate users of that store, one of the invariants we guarantee.
+  for (auto DomNode : depth_first(DT)) {
+    BasicBlock *BB = DomNode->getBlock();
+    auto AI = PerBlockAccesses.find(BB);
+    if (AI == PerBlockAccesses.end())
+      continue;
+    auto &Accesses = AI->second;
+    for (auto &MA : *Accesses) {
+      if (MemoryUse *MU = dyn_cast<MemoryUse>(&MA)) {
+        auto RealVal = Walker->getClobberingMemoryAccess(MU->getMemoryInst());
+        MU->setDefiningAccess(RealVal);
+      }
+    }
+  }
+
+  // Mark the uses in unreachable blocks as live on entry, so that they go
+  // somewhere.
+  for (auto &BB : F)
+    if (!Visited.count(&BB))
+      markUnreachableAsLiveOnEntry(&BB);
+
+  builtAlready = true;
+  return Walker;
+}
+
+static MemoryAccess *getDefiningAccess(MemoryAccess *MA) {
+  if (isa<MemoryUse>(MA) || isa<MemoryDef>(MA))
+    return MA->getDefiningAccess();
+  else
+    return nullptr;
+}
+static void setDefiningAccess(MemoryAccess *Of, MemoryAccess *To) {
+  if (isa<MemoryUse>(Of) || isa<MemoryDef>(Of))
+    Of->setDefiningAccess(To);
+}
+
+/// \brief Properly remove \p MA from all of MemorySSA's lookup tables.
+///
+/// Because of the way the intrusive list and use lists work, it is important to
+/// do removal in the right order.
+void MemorySSA::removeFromLookups(MemoryAccess *MA) {
+  assert(MA->user_empty() &&
+         "Trying to remove memory access that still has uses");
+  setDefiningAccess(MA, nullptr);
+  // Invalidate our walker's cache if necessary
+  if (!isa<MemoryUse>(MA))
+    Walker->invalidateInfo(MA);
+  // The call below to erase will destroy MA, so we can't change the order we
+  // are doing things here
+  Instruction *MemoryInst = MA->getMemoryInst();
+  if (MemoryInst)
+    InstructionToMemoryAccess.erase(MemoryInst);
+  auto &Accesses = PerBlockAccesses.find(MA->getBlock())->second;
+  Accesses->erase(MA);
+  if (Accesses->empty()) {
+    PerBlockAccesses.erase(MA->getBlock());
+  }
+}
+
+/// \brief Helper function to create new memory accesses
+MemoryAccess *MemorySSA::createNewAccess(Instruction *I, bool ignoreNonMemory) {
+  // Find out what affect this instruction has on memory.
+  ModRefInfo ModRef = AA->getModRefInfo(I);
+  bool def = false, use = false;
+  if (ModRef & MRI_Mod)
+    def = true;
+  if (ModRef & MRI_Ref)
+    use = true;
+
+  // It's possible for an instruction to not modify memory at all. During
+  // construction, we ignore them.
+  if (ignoreNonMemory && !def && !use)
+    return nullptr;
+
+  assert((def || use) &&
+         "Trying to create a memory access with a non-memory instruction");
+
+  if (def) {
+    MemoryDef *MD = new MemoryDef(nullptr, I, I->getParent(), nextID++);
+    InstructionToMemoryAccess.insert(std::make_pair(I, MD));
+    return MD;
+  } else if (use) {
+    MemoryUse *MU = new MemoryUse(nullptr, I, I->getParent());
+    InstructionToMemoryAccess.insert(std::make_pair(I, MU));
+    return MU;
+  }
+
+  llvm_unreachable("Not a memory instruction!");
+}
+
+MemoryAccess *MemorySSA::findDominatingDef(BasicBlock *UseBlock,
+                                           enum InsertionPlace Where) {
+  // Handle the initial case
+  if (Where == Beginning)
+    // The only thing that could define us at the beginning is a phi node
+    if (MemoryAccess *Phi = getMemoryAccess(UseBlock))
+      return Phi;
+
+  DomTreeNode *CurrNode = DT->getNode(UseBlock);
+  // Need to be defined by our dominator
+  if (Where == Beginning)
+    CurrNode = CurrNode->getIDom();
+  Where = End;
+  while (CurrNode) {
+    auto It = PerBlockAccesses.find(CurrNode->getBlock());
+    if (It != PerBlockAccesses.end()) {
+      auto &Accesses = It->second;
+      for (auto RAI = Accesses->rbegin(), RAE = Accesses->rend(); RAI != RAE;
+           ++RAI) {
+        if (isa<MemoryDef>(*RAI) || isa<MemoryPhi>(*RAI))
+          return &*RAI;
+      }
+    }
+    CurrNode = CurrNode->getIDom();
+  }
+  return LiveOnEntryDef;
+}
+
+MemoryAccess *MemorySSA::addNewMemoryUse(Instruction *Use,
+                                         enum InsertionPlace Where) {
+  BasicBlock *UseBlock = Use->getParent();
+  MemoryAccess *DefiningDef = findDominatingDef(UseBlock, Where);
+  auto &Accesses = getOrCreateAccessList(UseBlock);
+  MemoryAccess *MA = createNewAccess(Use);
+
+  // Set starting point, then optimize to get correct answer.
+  MA->setDefiningAccess(DefiningDef);
+  auto RealVal = Walker->getClobberingMemoryAccess(MA->getMemoryInst());
+  MA->setDefiningAccess(RealVal);
+
+  // Easy case
+  if (Where == Beginning) {
+    auto AI = Accesses->begin();
+    while (isa<MemoryPhi>(AI))
+      ++AI;
+    Accesses->insert(AI, MA);
+  } else {
+    Accesses->push_back(MA);
+  }
+  return MA;
+}
+
+MemoryAccess *MemorySSA::replaceMemoryAccessWithNewAccess(
+    MemoryAccess *Replacee, Instruction *Replacer, enum InsertionPlace Where) {
+  BasicBlock *ReplacerBlock = Replacer->getParent();
+
+  auto &Accesses = getOrCreateAccessList(ReplacerBlock);
+  if (Where == Beginning) {
+    // Access must go after the first phi
+    auto AI = Accesses->begin();
+    while (AI != Accesses->end()) {
+      if (!isa<MemoryPhi>(AI))
+        break;
+      ++AI;
+    }
+    return replaceMemoryAccessWithNewAccess(Replacee, Replacer, AI);
+  } else {
+    return replaceMemoryAccessWithNewAccess(Replacee, Replacer,
+                                            Accesses->end());
+  }
+}
+
+MemoryAccess *MemorySSA::replaceMemoryAccessWithNewAccess(
+    MemoryAccess *Replacee, Instruction *Replacer,
+    const AccessListType::iterator &Where) {
+
+  BasicBlock *ReplacerBlock = Replacer->getParent();
+  MemoryAccess *MA = nullptr;
+  MemoryAccess *DefiningAccess = getDefiningAccess(Replacee);
+
+  // Handle the case we are replacing a phi node, in which case, we don't kill
+  // the phi node
+  if (DefiningAccess == nullptr) {
+    assert(isa<MemoryPhi>(Replacee) &&
+           "Should have been a phi node if we can't get a defining access");
+    assert(DT->dominates(Replacee->getBlock(), ReplacerBlock) &&
+           "Need to reuse PHI for defining access, but it will not dominate "
+           "replacing instruction");
+    DefiningAccess = Replacee;
+  }
+
+  MA = createNewAccess(Replacer);
+  MA->setDefiningAccess(DefiningAccess);
+  auto It = PerBlockAccesses.find(ReplacerBlock);
+  assert(It != PerBlockAccesses.end() &&
+         "Can't use iterator insertion for brand new block");
+  auto &Accesses = It->second;
+  Accesses->insert(Where, MA);
+  replaceMemoryAccess(Replacee, MA);
+  return MA;
+}
+
+/// \brief Returns true if \p Replacer dominates \p Replacee .
+bool MemorySSA::dominatesUse(const MemoryAccess *Replacer,
+                             const MemoryAccess *Replacee) const {
+  if (isa<MemoryUse>(Replacee) || isa<MemoryDef>(Replacee))
+    return DT->dominates(Replacer->getBlock(), Replacee->getBlock());
+  const MemoryPhi *MP = cast<MemoryPhi>(Replacee);
+  // For a phi node, the use occurs in the predecessor block of the phi node.
+  // Since we may occur multiple times in the phi node, we have to check each
+  // operand to ensure Replacer dominates each operand where Replacee occurs.
+  for (const auto &Arg : MP->operands())
+    if (Arg.second == Replacee)
+      if (!DT->dominates(Replacer->getBlock(), Arg.first))
+        return false;
+  return true;
+}
+
+/// \brief Replace all occurrences of \p Replacee with \p Replacer in a PHI
+/// node.
+/// \return true if we replaced all operands of the phi node.
+bool MemorySSA::replaceAllOccurrences(MemoryPhi *P, MemoryAccess *Replacee,
+                                      MemoryAccess *Replacer) {
+  bool ReplacedAllValues = true;
+  for (unsigned i = 0, e = P->getNumIncomingValues(); i != e; ++i) {
+    if (P->getIncomingValue(i) == Replacee)
+      P->setIncomingValue(i, Replacer);
+    else
+      ReplacedAllValues = false;
+  }
+  return ReplacedAllValues;
+}
+
+void MemorySSA::replaceMemoryAccess(MemoryAccess *Replacee,
+                                    MemoryAccess *Replacer) {
+
+  // If we don't replace all phi node entries, we can't remove it.
+  bool replacedAllPhiEntries = true;
+  // If we are replacing a phi node, we may still actually use it, since we
+  // may now be defined in terms of it.
+  bool usedByReplacee = getDefiningAccess(Replacer) == Replacee;
+
+  // Just to note: We can replace the live on entry def, unlike removing it, so
+  // we don't assert here, but it's almost always a bug, unless you are
+  // inserting a load/store in a block that dominates the rest of the program.
+  for (auto U : Replacee->users()) {
+    if (U == Replacer)
+      continue;
+    assert(dominatesUse(Replacer, Replacee) &&
+           "Definitions will not dominate uses in replacement!");
+    if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U)) {
+      if (replaceAllOccurrences(MP, Replacee, Replacer))
+        replacedAllPhiEntries = true;
+    } else {
+      U->setDefiningAccess(Replacer);
+    }
+  }
+  // Kill our dead replacee if it's really dead
+  if (replacedAllPhiEntries && !usedByReplacee) {
+    removeFromLookups(Replacee);
+  }
+}
+
+#ifndef NDEBUG
+/// \brief Returns true if a phi is defined by the same value on all edges
+static bool onlySingleValue(MemoryPhi *MP) {
+  MemoryAccess *MA = nullptr;
+
+  for (const auto &Arg : MP->operands()) {
+    if (!MA)
+      MA = Arg.second;
+    else if (MA != Arg.second)
+      return false;
+  }
+  return true;
+}
+#endif
+
+void MemorySSA::removeMemoryAccess(MemoryAccess *MA) {
+  assert(MA != LiveOnEntryDef && "Trying to remove the live on entry def");
+  // We can only delete phi nodes if they are use empty
+  if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
+    // This code only used in assert builds
+    (void)MP;
+    assert(MP->user_empty() && "We can't delete memory phis that still have "
+                               "uses, we don't know where the uses should "
+                               "repoint to!");
+    assert((MP->user_empty() || onlySingleValue(MP)) &&
+           "This phi still points to multiple values, "
+           "which means it is still needed");
+  } else {
+    MemoryAccess *DefiningAccess = getDefiningAccess(MA);
+    // Re-point the uses at our defining access
+    for (auto U : MA->users()) {
+      assert(dominatesUse(DefiningAccess, U) &&
+             "Definitions will not dominate uses in removal!");
+      if (MemoryPhi *MP = dyn_cast<MemoryPhi>(U)) {
+        replaceAllOccurrences(MP, MA, DefiningAccess);
+      } else {
+        U->setDefiningAccess(DefiningAccess);
+      }
+    }
+  }
+
+  // The call below to erase will destroy MA, so we can't change the order we
+  // are doing things here
+  removeFromLookups(MA);
+}
+
+void MemorySSA::print(raw_ostream &OS) const {
+  MemorySSAAnnotatedWriter Writer(this);
+  F.print(OS, &Writer);
+}
+
+void MemorySSA::dump() const {
+  MemorySSAAnnotatedWriter Writer(this);
+  F.print(dbgs(), &Writer);
+}
+
+/// \brief Verify the domination properties of MemorySSA by checking that each
+/// definition dominates all of its uses.
+void MemorySSA::verifyDomination(Function &F) {
+  for (auto &B : F) {
+    // Phi nodes are attached to basic blocks
+    MemoryAccess *MA = getMemoryAccess(&B);
+    if (MA) {
+      MemoryPhi *MP = cast<MemoryPhi>(MA);
+      for (const auto &U : MP->users()) {
+        BasicBlock *UseBlock;
+        // Phi operands are used on edges, we simulate the right domination by
+        // acting as if the use occurred at the end of the predecessor block.
+        if (MemoryPhi *P = dyn_cast<MemoryPhi>(U)) {
+          for (const auto &Arg : P->operands()) {
+            if (Arg.second == MP) {
+              UseBlock = Arg.first;
+              break;
+            }
+          }
+        } else {
+          UseBlock = U->getBlock();
+        }
+        assert(DT->dominates(MP->getBlock(), UseBlock) &&
+               "Memory PHI does not dominate it's uses");
+      }
+    }
+    for (auto &I : B) {
+      MA = getMemoryAccess(&I);
+      if (MA) {
+        if (MemoryDef *MD = dyn_cast<MemoryDef>(MA))
+          for (const auto &U : MD->users()) {
+            BasicBlock *UseBlock;
+            // Things are allowed to flow to phi nodes over their predecessor
+            // edge.
+            if (MemoryPhi *P = dyn_cast<MemoryPhi>(U)) {
+              for (const auto &Arg : P->operands()) {
+                if (Arg.second == MD) {
+                  UseBlock = Arg.first;
+                  break;
+                }
+              }
+            } else {
+              UseBlock = U->getBlock();
+            }
+            assert(DT->dominates(MD->getBlock(), UseBlock) &&
+                   "Memory Def does not dominate it's uses");
+          }
+      }
+    }
+  }
+}
+
+/// \brief Verify the def-use lists in MemorySSA, by verifying that \p Use
+/// appears in the use list of \p Def.
+void MemorySSA::verifyUseInDefs(MemoryAccess *Def, MemoryAccess *Use) {
+  // The live on entry use may cause us to get a NULL def here
+  if (Def == nullptr) {
+    assert(isLiveOnEntryDef(Use) &&
+           "Null def but use not point to live on entry def");
+    return;
+  }
+  assert(Def->hasUse(Use) && "Did not find use in def's use list");
+}
+
+/// \brief Verify the immediate use information, by walking all the memory
+/// accesses and verifying that, for each use, it appears in the
+/// appropriate def's use list
+void MemorySSA::verifyDefUses(Function &F) {
+  for (auto &B : F) {
+    // Phi nodes are attached to basic blocks
+    MemoryAccess *MA = getMemoryAccess(&B);
+    if (MA) {
+      assert(isa<MemoryPhi>(MA) &&
+             "Something other than phi node on basic block");
+      MemoryPhi *MP = cast<MemoryPhi>(MA);
+      for (unsigned i = 0, e = MP->getNumIncomingValues(); i != e; ++i)
+        verifyUseInDefs(MP->getIncomingValue(i), MP);
+    }
+    for (auto &I : B) {
+      MA = getMemoryAccess(&I);
+      if (MA) {
+        if (MemoryPhi *MP = dyn_cast<MemoryPhi>(MA)) {
+          for (unsigned i = 0, e = MP->getNumIncomingValues(); i != e; ++i)
+            verifyUseInDefs(MP->getIncomingValue(i), MP);
+        } else {
+          verifyUseInDefs(MA->getDefiningAccess(), MA);
+        }
+      }
+    }
+  }
+}
+
+MemoryAccess *MemorySSA::getMemoryAccess(const Value *I) const {
+  return InstructionToMemoryAccess.lookup(I);
+}
+
+/// \brief Determine, for two memory accesses in the same block,
+/// whether \p Dominator dominates \p Dominatee.
+/// \returns True if \p Dominator dominates \p Dominatee.
+bool MemorySSA::locallyDominates(const MemoryAccess *Dominator,
+                                 const MemoryAccess *Dominatee) const {
+
+  assert((Dominator->getBlock() == Dominatee->getBlock()) &&
+         "Asking for local domination when accesses are in different blocks!");
+  // Get the access list for the block
+  const auto *AccessList = getBlockAccesses(Dominator->getBlock());
+  AccessListType::const_reverse_iterator It(Dominator->getIterator());
+
+  // If we hit the beginning of the access list before we hit dominatee, we must
+  // dominate it
+  while (It != AccessList->rend()) {
+    if (&*It == Dominatee)
+      return false;
+    ++It;
+  }
+  return true;
+}
+
+void MemoryDef::print(raw_ostream &OS) const {
+  MemoryAccess *UO = getDefiningAccess();
+
+  OS << getID() << " = "
+     << "MemoryDef(";
+  if (UO && UO->getID() != 0)
+    OS << UO->getID();
+  else
+    OS << "liveOnEntry";
+  OS << ")";
+}
+
+void MemoryPhi::print(raw_ostream &OS) const {
+  OS << getID() << " = "
+     << "MemoryPhi(";
+  for (unsigned int i = 0, e = getNumIncomingValues(); i != e; ++i) {
+    BasicBlock *BB = getIncomingBlock(i);
+    MemoryAccess *MA = getIncomingValue(i);
+    OS << "{";
+    if (BB->hasName())
+      OS << BB->getName();
+    else
+      BB->printAsOperand(OS, false);
+    OS << ",";
+    assert((isa<MemoryDef>(MA) || isa<MemoryPhi>(MA)) &&
+           "Phi node should have referred to def or another phi");
+    if (MA->getID() != 0)
+      OS << MA->getID();
+    else
+      OS << "liveOnEntry";
+    OS << "}";
+    if (i + 1 < e)
+      OS << ",";
+  }
+  OS << ")";
+}
+
+MemoryAccess::~MemoryAccess() {}
+
+void MemoryUse::print(raw_ostream &OS) const {
+  MemoryAccess *UO = getDefiningAccess();
+  OS << "MemoryUse(";
+  if (UO && UO->getID() != 0)
+    OS << UO->getID();
+  else
+    OS << "liveOnEntry";
+  OS << ")";
+}
+
+void MemoryAccess::dump() const {
+  print(dbgs());
+  dbgs() << "\n";
+}
+
+char MemorySSAPrinterPass::ID = 0;
+
+MemorySSAPrinterPass::MemorySSAPrinterPass() : FunctionPass(ID) {
+  initializeMemorySSAPrinterPassPass(*PassRegistry::getPassRegistry());
+}
+
+void MemorySSAPrinterPass::releaseMemory() {
+  delete MSSA;
+  delete Walker;
+}
+
+void MemorySSAPrinterPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<AAResultsWrapperPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.addPreserved<DominatorTreeWrapperPass>();
+  AU.addPreserved<GlobalsAAWrapperPass>();
+}
+
+bool MemorySSAPrinterPass::doInitialization(Module &M) {
+
+  VerifyMemorySSA =
+      M.getContext()
+          .template getOption<bool, MemorySSAPrinterPass,
+                              &MemorySSAPrinterPass::VerifyMemorySSA>();
+  return false;
+}
+
+void MemorySSAPrinterPass::registerOptions() {
+  OptionRegistry::registerOption<bool, MemorySSAPrinterPass,
+                                 &MemorySSAPrinterPass::VerifyMemorySSA>(
+      "verify-memoryssa", "Run the Memory SSA verifier", false);
+}
+
+void MemorySSAPrinterPass::print(raw_ostream &OS, const Module *M) const {
+  MSSA->print(OS);
+}
+
+bool MemorySSAPrinterPass::runOnFunction(Function &F) {
+  this->F = &F;
+  MSSA = new MemorySSA(F);
+  AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
+  DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  Walker = MSSA->buildMemorySSA(AA, DT);
+
+  if (VerifyMemorySSA) {
+    MSSA->verifyDefUses(F);
+    MSSA->verifyDomination(F);
+  }
+
+  return false;
+}
+
+char MemorySSALazy::ID = 0;
+
+MemorySSALazy::MemorySSALazy() : FunctionPass(ID) {
+  initializeMemorySSALazyPass(*PassRegistry::getPassRegistry());
+}
+
+void MemorySSALazy::releaseMemory() { delete MSSA; }
+
+bool MemorySSALazy::runOnFunction(Function &F) {
+  MSSA = new MemorySSA(F);
+  return false;
+}
+
+MemorySSAWalker::MemorySSAWalker(MemorySSA *M) : MSSA(M) {}
+
+CachingMemorySSAWalker::CachingMemorySSAWalker(MemorySSA *M, AliasAnalysis *A,
+                                               DominatorTree *D)
+    : MemorySSAWalker(M), AA(A), DT(D) {}
+
+CachingMemorySSAWalker::~CachingMemorySSAWalker() {
+  CachedUpwardsClobberingAccess.clear();
+  CachedUpwardsClobberingCall.clear();
+}
+
+struct CachingMemorySSAWalker::UpwardsMemoryQuery {
+  // True if we saw a phi whose predecessor was a backedge
+  bool SawBackedgePhi;
+  // True if our original query started off as a call
+  bool isCall;
+  // The pointer location we started the query with. This will be
+  // empty if isCall is true.
+  MemoryLocation StartingLoc;
+  // This is the instruction we were querying about.
+  const Instruction *Inst;
+  // Set of visited Instructions for this query.
+  DenseSet<MemoryAccessPair> Visited;
+  // Set of visited call accesses for this query This is separated out because
+  // you can always cache and lookup the result of call queries (IE when
+  // isCall == true) for every call in the chain. The calls have no AA
+  // location associated with them with them, and thus, no context dependence.
+  SmallPtrSet<const MemoryAccess *, 32> VisitedCalls;
+  // The MemoryAccess we actually got called with, used to test local domination
+  const MemoryAccess *OriginalAccess;
+  // The Datalayout for the module we started in
+  const DataLayout *DL;
+};
+
+void CachingMemorySSAWalker::doCacheRemove(const MemoryAccess *M,
+                                           const UpwardsMemoryQuery &Q,
+                                           const MemoryLocation &Loc) {
+  if (Q.isCall)
+    CachedUpwardsClobberingCall.erase(M);
+  else
+    CachedUpwardsClobberingAccess.erase({M, Loc});
+}
+
+void CachingMemorySSAWalker::doCacheInsert(const MemoryAccess *M,
+                                           MemoryAccess *Result,
+                                           const UpwardsMemoryQuery &Q,
+                                           const MemoryLocation &Loc) {
+  ++NumClobberCacheInserts;
+  if (Q.isCall)
+    CachedUpwardsClobberingCall[M] = Result;
+  else
+    CachedUpwardsClobberingAccess[{M, Loc}] = Result;
+}
+
+MemoryAccess *CachingMemorySSAWalker::doCacheLookup(const MemoryAccess *M,
+                                                    const UpwardsMemoryQuery &Q,
+                                                    const MemoryLocation &Loc) {
+  ++NumClobberCacheLookups;
+  MemoryAccess *Result = nullptr;
+
+  if (Q.isCall)
+    Result = CachedUpwardsClobberingCall.lookup(M);
+  else
+    Result = CachedUpwardsClobberingAccess.lookup({M, Loc});
+
+  if (Result) {
+    ++NumClobberCacheHits;
+    return Result;
+  }
+  return nullptr;
+}
+
+/// \brief Return true if \p QueryInst could possibly have a Mod result with \p
+/// DefInst.
+static bool possiblyAffectedBy(const Instruction *QueryInst,
+                               const Instruction *DefInst) {
+  if (isa<LoadInst>(DefInst) && isa<LoadInst>(QueryInst)) {
+    const LoadInst *DefLI = cast<LoadInst>(DefInst);
+    const LoadInst *QueryLI = cast<LoadInst>(QueryInst);
+    // A non-volatile load can't be clobbered by a volatile one unless the
+    // volatile one is ordered.
+    if (!QueryLI->isVolatile() && DefLI->isVolatile())
+      return DefLI->getOrdering() > Unordered;
+  }
+  return true;
+}
+
+bool CachingMemorySSAWalker::instructionClobbersQuery(
+    const MemoryDef *MD, struct UpwardsMemoryQuery &Q,
+    const MemoryLocation &Loc) const {
+  Instruction *DefMemoryInst = MD->getMemoryInst();
+  assert(DefMemoryInst && "Defining instruction not actually an instruction");
+
+  if (!Q.isCall) {
+    // Okay, well, see if it's a volatile load vs non-volatile load
+    // situation.
+    if (possiblyAffectedBy(Q.Inst, DefMemoryInst))
+      // Check whether our memory location is modified by this instruction
+      if (AA->getModRefInfo(DefMemoryInst, Loc) & MRI_Mod)
+        return true;
+  } else {
+    // If this is a call, try then mark it for caching
+    if (ImmutableCallSite(DefMemoryInst)) {
+      Q.VisitedCalls.insert(MD);
+    }
+    if (AA->getModRefInfo(DefMemoryInst, ImmutableCallSite(Q.Inst)) !=
+        MRI_NoModRef)
+      return true;
+  }
+  return false;
+}
+
+MemoryAccessPair CachingMemorySSAWalker::UpwardsDFSWalk(
+    MemoryAccess *StartingAccess, const MemoryLocation &Loc,
+    UpwardsMemoryQuery &Q, bool FollowingBackedge) {
+  MemoryAccess *ModifyingAccess = nullptr;
+
+  auto DFI = df_begin(StartingAccess);
+  for (auto DFE = df_end(StartingAccess); DFI != DFE;) {
+    MemoryAccess *CurrAccess = *DFI;
+    if (MSSA->isLiveOnEntryDef(CurrAccess))
+      return {CurrAccess, Loc};
+    if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc)) {
+      return {CacheResult, Loc};
+    }
+    // If this is a MemoryDef, check whether it clobbers our current query.
+    if (MemoryDef *MD = dyn_cast<MemoryDef>(CurrAccess)) {
+      // If we hit the top, stop following this path
+      // While we can do lookups, we can't sanely do inserts here unless we
+      // were to track every thing we saw along the way, since we don't
+      // know where we will stop.
+      if (instructionClobbersQuery(MD, Q, Loc)) {
+        ModifyingAccess = CurrAccess;
+        break;
+      }
+    }
+    // We need to know whether it is a phi so we can track backedges.
+    // Otherwise, walk all upward defs.
+    bool IsPhi = isa<MemoryPhi>(CurrAccess);
+    // Recurse on PHI nodes, since we need to change locations.
+    // TODO: Allow graphtraits on pairs, which would turn this whole function
+    // into a normal single depth first walk.
+    if (IsPhi) {
+      MemoryAccess *FirstDef = nullptr;
+      DFI = DFI.skipChildren();
+      const MemoryAccessPair PHIPair(CurrAccess, Loc);
+      if (Q.Visited.count(PHIPair))
+        return PHIPair;
+      for (auto MPI = upward_defs_begin(PHIPair), MPE = upward_defs_end();
+           MPI != MPE; ++MPI) {
+        bool Backedge = false;
+        // Don't follow this path again if we've followed it once
+        if (!Q.Visited.insert(*MPI).second)
+          continue;
+        if (IsPhi && !FollowingBackedge &&
+            DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock()))
+          Backedge = true;
+        MemoryAccessPair CurrentPair =
+            UpwardsDFSWalk(MPI->first, MPI->second, Q, Backedge);
+        // All the phi arguments should reach the same point if we can bypass
+        // this phi.  The alternative is that they hit this phi node, which
+        // means we can skip this argument.
+        if (FirstDef && (CurrentPair.first != PHIPair.first &&
+                         FirstDef != CurrentPair.first)) {
+          ModifyingAccess = CurrAccess;
+          break;
+        } else if (!FirstDef) {
+          FirstDef = CurrentPair.first;
+        }
+      }
+    } else {
+      // You can't call skipchildren and also increment the iterator
+      ++DFI;
+    }
+  }
+  if (!ModifyingAccess)
+    return {MSSA->getLiveOnEntryDef(), Q.StartingLoc};
+  const BasicBlock *OriginalBlock = Q.OriginalAccess->getBlock();
+  unsigned N = DFI.getPathLength();
+  MemoryAccess *FinalAccess = ModifyingAccess;
+
+  for (; N != 0; --N) {
+    ModifyingAccess = DFI.getPath(N - 1);
+    BasicBlock *CurrBlock = ModifyingAccess->getBlock();
+    if (!FollowingBackedge)
+      doCacheInsert(ModifyingAccess, FinalAccess, Q, Loc);
+    if (DT->dominates(CurrBlock, OriginalBlock) &&
+        (CurrBlock != OriginalBlock || !FollowingBackedge ||
+         MSSA->locallyDominates(ModifyingAccess, Q.OriginalAccess)))
+      break;
+  }
+  // Cache everything else on the way back
+  for (; N != 0; --N) {
+    MemoryAccess *CacheAccess = DFI.getPath(N - 1);
+    doCacheInsert(CacheAccess, ModifyingAccess, Q, Loc);
+  }
+  assert(Q.Visited.size() < 1000 && "Visited too much");
+
+  return {ModifyingAccess, Loc};
+}
+
+/// \brief Perform a BFS walking, starting at \p StartingAccess, and going
+/// upwards (IE through defining accesses) until we reach something that
+/// Mod's StartingAccess's memory location.
+///
+/// \p Prev is filled in with the immediate predecessor of each node when
+/// walking, so that the path we took from EndingAccess to StartingAccess can be
+/// traced by walking through Prev.
+///
+/// TODO: It would be really nice to have a bfs iterator that we can use to do
+/// upwards and downwards walks.  This would require making iterators for the
+/// memory access types, graphtraits, making bfs_ext iterators.
+std::pair<MemoryAccess *, MemoryLocation>
+CachingMemorySSAWalker::UpwardsBFSWalkAccess(MemoryAccess *StartingAccess,
+                                             const MemoryLocation &StartingLoc,
+                                             PathMap &Prev,
+                                             UpwardsMemoryQuery &Q) {
+  std::queue<MemoryAccessPair> Worklist;
+  Q.Visited.insert({StartingAccess, StartingLoc});
+  Worklist.emplace(StartingAccess, StartingLoc);
+  MemoryAccess *ModifyingAccess = nullptr;
+  Q.SawBackedgePhi = false;
+
+  MemoryLocation Loc;
+  while (!Worklist.empty()) {
+    const MemoryAccessPair Pair = Worklist.front();
+    MemoryAccess *CurrAccess = Pair.first;
+    Loc = Pair.second;
+    Worklist.pop();
+
+    // If we hit the live on entry def, this path stops
+    if (MSSA->isLiveOnEntryDef(CurrAccess))
+      continue;
+
+    // See if we've already followed this path with this set of memory
+    // information.
+    if (auto CacheResult = doCacheLookup(CurrAccess, Q, Loc)) {
+      // If we have followed this path in the past, we still need to make sure
+      // we mark it visited for our *current walk* and fill out the prev table
+      // if we haven't already, because the cached information may be from a
+      // previous walk.
+      if (Q.Visited.insert({CacheResult, Loc}).second)
+        Prev[{CacheResult, Loc}] = {CurrAccess, Loc};
+      return {CacheResult, Loc};
+    }
+
+    // If this is a MemoryDef, check whether it clobbers our current query.
+    if (MemoryDef *MD = dyn_cast<MemoryDef>(CurrAccess)) {
+      // If we hit the top, stop following this path
+      // While we can do lookups, we can't sanely do inserts here unless we
+      // were to track every thing we saw along the way, since we don't
+      // know where we will stop.
+      if (instructionClobbersQuery(MD, Q, Loc)) {
+        ModifyingAccess = CurrAccess;
+        break;
+      }
+    }
+    // We need to know whether it is a phi so we can track backedges and check
+    // whether we can bypass it.
+    // Otherwise, walk all upward defs.
+    bool IsPhi = isa<MemoryPhi>(CurrAccess);
+    if (IsPhi) {
+      MemoryAccess *FirstDef = nullptr;
+      const MemoryAccessPair PHIPair(CurrAccess, Loc);
+      for (auto MPI = upward_defs_begin(Pair), MPE = upward_defs_end();
+           MPI != MPE; ++MPI) {
+        // If we hit a phi that goes across a backedge, mark it
+        if (!Q.SawBackedgePhi &&
+            DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock()))
+          Q.SawBackedgePhi = true;
+        // We may have already visited this argument along another path
+        if (!Q.Visited.insert(*MPI).second)
+          continue;
+
+        assert(Prev.count(*MPI) == 0 &&
+               "This part of the map should not already be filled in!");
+        MemoryAccessPair CurrentPair =
+            UpwardsBFSWalkAccess(MPI->first, MPI->second, Prev, Q);
+        // All the phi arguments should reach the same point if we can bypass
+        // this phi.  The alternative is that they hit this phi node, which
+        // means we can skip this argument.
+        if (FirstDef && (CurrentPair.first != PHIPair.first &&
+                         FirstDef != CurrentPair.first)) {
+          ModifyingAccess = CurrAccess;
+          break;
+        } else if (!FirstDef) {
+          FirstDef = CurrentPair.first;
+        }
+        // Finally, enqueue the argument and new pointer, and set the map to
+        // say we got here from the phi and the old pointer.
+        Prev[*MPI] = Pair;
+
+        Worklist.emplace(*MPI);
+      }
+    } else {
+      for (auto MPI = upward_defs_begin(Pair), MPE = upward_defs_end();
+           MPI != MPE; ++MPI) {
+
+        // If we hit a phi that goes across a backedge, mark it
+        if (IsPhi && !Q.SawBackedgePhi &&
+            DT->dominates(CurrAccess->getBlock(), MPI.getPhiArgBlock()))
+          Q.SawBackedgePhi = true;
+        // We may have already visited this argument along another path
+        if (!Q.Visited.insert(*MPI).second)
+          continue;
+
+        assert(Prev.count(*MPI) == 0 &&
+               "This part of the map should not  already be filled in!");
+
+        // Finally, enqueue the argument and new pointer, and set the map to
+        // say we got here from the phi and the old pointer.
+        Prev[*MPI] = Pair;
+
+        Worklist.emplace(*MPI);
+      }
+    }
+  }
+
+  // If we emptied the worklist, it means every path to the beginning of the
+  // function had nothing that MOD'd our query.  This means we should return the
+  // live on entry def.  Note that CurrAccess will not always be the
+  // liveOnEntryDef at his point. If, for example, the last path we followed led
+  // into a cycle, it will be something else.
+  if (!ModifyingAccess && Worklist.empty())
+    return {MSSA->getLiveOnEntryDef(), StartingLoc};
+
+  return {ModifyingAccess, Loc};
+}
+
+/// \brief Walk the use-def chains starting at \p MA and find
+/// the MemoryAccess that actually clobbers Loc.
+///
+/// \returns a pair of clobbering memory access and whether we hit a cyclic phi
+/// node.
+MemoryAccess *CachingMemorySSAWalker::getClobberingMemoryAccess(
+    MemoryAccess *StartingAccess, struct UpwardsMemoryQuery &Q) {
+  PathMap Prev;
+#if 0
+  auto CurrAccessPair =
+      UpwardsBFSWalkAccess(StartingAccess, Q.StartingLoc, Prev, Q);
+#else
+  auto CurrAccessPair = UpwardsDFSWalk(StartingAccess, Q.StartingLoc, Q, false);
+#endif
+  // Either we will have found something that conflicts with us, or we will have
+  // hit the liveOnEntry. Check for liveOnEntry.
+  if (MSSA->isLiveOnEntryDef(CurrAccessPair.first))
+    return CurrAccessPair.first;
+  // Now find the thing that dominates us from the path we found to the
+  // clobbering access.
+  MemoryAccessPair FinalAccessPair =
+      findDominatingAccess(StartingAccess, CurrAccessPair, Prev, Q);
+  MemoryAccess *FinalAccess = FinalAccessPair.first;
+  assert(FinalAccessPair.first &&
+         "Should have found something that dominated our original access");
+  // Everything along the rest of the path now terminates at CurrAccess
+  // TODO
+  // 1. We could cache the rest of the prev map as partial cache info and
+  // restart the BFS walk from it if and when we need to
+  // 2. We also know that anything in the Prev map with the same Loc that is
+  // dominated by FinalAccess, also terminates in FinalAccess (by the definition
+  // of the domination). We could cache these as well.
+
+  // This just avoids doing a cache insert of the same thing twice, in the case
+  // that our walk terminated in something that dominated our original access.
+  // In that case, we would insert both here and in the loop below.
+  if (FinalAccess != CurrAccessPair.first)
+    doCacheInsert(CurrAccessPair.first, CurrAccessPair.first, Q,
+                  CurrAccessPair.second);
+
+  unsigned N = 0;
+  MemoryAccess *CacheAccess = FinalAccess;
+  MemoryLocation CacheLoc = FinalAccessPair.second;
+  while (CacheAccess) {
+    doCacheInsert(CacheAccess, FinalAccess, Q, CacheLoc);
+    const auto &PrevResult = Prev.lookup({CacheAccess, CacheLoc});
+    CacheAccess = PrevResult.first;
+    CacheLoc = PrevResult.second;
+    ++N;
+    assert(N < 10000 && "In the second loop too many times");
+  }
+
+  return FinalAccess;
+}
+
+MemoryAccessPair CachingMemorySSAWalker::findDominatingAccess(
+    const MemoryAccess *StartingAccess, const MemoryAccessPair &FinalAccessPair,
+    const PathMap &Path, const struct UpwardsMemoryQuery &Q) const {
+  // This means walking the prev pointers backwards to figure
+  // out how we go to this clobber, stopping when we find something that
+  // dominates the original access.
+  // If we saw a phi node with a backedge, the thing that we found in our block
+  // may in fact be after us in the current block, in which case, we need to
+  // check local domination to make sure we give a correct answer.
+
+  // Since this code may be a little confusing, here is what is happening:
+  // First we extract the block of the original access that the user queried
+  // about, I.E. the access for the instruction they passed to
+  // getClobberingAccess.
+  // This may or may *not* be the same as StartingAccess (for a MemoryUse, the
+  // StartingAccess might be the RHS def, depending on which query function was
+  // used).
+  // However, we know that StartingAccess dominates our OriginalAccess, so
+  // either we should find something "better", or we should get back to
+  // StartingAccess.  The null check below is just to make sure the loop
+  // terminates. We assert that it does not happen.
+
+  const BasicBlock *OriginalBlock = Q.OriginalAccess->getBlock();
+  MemoryAccess *FinalAccess = FinalAccessPair.first;
+  MemoryLocation FinalLoc = FinalAccessPair.second;
+
+  // Walk backwards until we hit the starting access
+  while (FinalAccess && FinalAccess != StartingAccess) {
+    BasicBlock *CurrBlock = FinalAccess->getBlock();
+    // Stop if we hit the dominating access
+    if (DT->dominates(CurrBlock, OriginalBlock) &&
+        (CurrBlock != OriginalBlock || !Q.SawBackedgePhi ||
+         MSSA->locallyDominates(FinalAccess, Q.OriginalAccess)))
+      break;
+
+    // Otherwise lookup the next entry in the path we took through BFS and go
+    // there.
+    const auto &PrevResult = Path.lookup({FinalAccess, FinalLoc});
+    FinalAccess = PrevResult.first;
+    FinalLoc = PrevResult.second;
+  }
+  // We should have always found *something*, or hit the StartingAccess.
+  // If we found nothing, then the walk was done wrong (since the walk started
+  // at StartingAccess, walking the path backwards should always terminate
+  // there).
+  assert((FinalAccess || FinalAccess == StartingAccess) &&
+         "Path walk was not done properly");
+
+  return {FinalAccess, FinalLoc};
+}
+
+MemoryAccess *
+CachingMemorySSAWalker::getClobberingMemoryAccess(MemoryAccess *StartingAccess,
+                                                  MemoryLocation &Loc) {
+  if (isa<MemoryPhi>(StartingAccess))
+    return StartingAccess;
+  if (MSSA->isLiveOnEntryDef(StartingAccess))
+    return StartingAccess;
+
+  Instruction *I = StartingAccess->getMemoryInst();
+
+  struct UpwardsMemoryQuery Q;
+  // Conservatively, fences are always clobbers, so don't perform the walk if we
+  // hit a fence.
+  if (isa<FenceInst>(I))
+    return StartingAccess;
+
+  Q.OriginalAccess = StartingAccess;
+  Q.StartingLoc = Loc;
+  Q.Inst = StartingAccess->getMemoryInst();
+  Q.isCall = false;
+  Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout();
+
+  auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc);
+  if (CacheResult)
+    return CacheResult;
+
+  // Unlike the other function, do not walk to the def of a def, because we are
+  // handed
+  // something we already believe is the clobbering access.
+  if (isa<MemoryUse>(StartingAccess))
+    StartingAccess = StartingAccess->getDefiningAccess();
+
+  MemoryAccess *FinalAccess = getClobberingMemoryAccess(StartingAccess, Q);
+  doCacheInsert(Q.OriginalAccess, FinalAccess, Q, Q.StartingLoc);
+  DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *StartingAccess << "\n");
+  DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *FinalAccess << "\n");
+
+  return FinalAccess;
+}
+
+MemoryAccess *
+CachingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
+
+  MemoryAccess *StartingAccess = MSSA->getMemoryAccess(I);
+
+  // There should be no way to lookup an instruction and get a phi as the
+  // access, since we only map BB's to PHI's.
+  assert(!isa<MemoryPhi>(StartingAccess));
+
+  struct UpwardsMemoryQuery Q;
+  Q.OriginalAccess = StartingAccess;
+
+  // First extract our location, then start walking until it is
+  // clobbered
+  // For calls, we store the call instruction we started with in
+  // Loc.Ptr
+  MemoryLocation Loc(I);
+  // We can't sanely do anything with a FenceInst, they conservatively
+  // clobber all memory, and have no locations to get pointers from to
+  // try to disambiguate
+  if (isa<FenceInst>(I)) {
+    return StartingAccess;
+  } else if (ImmutableCallSite(I)) {
+    Q.isCall = true;
+    Q.Inst = I;
+  } else {
+    Q.isCall = false;
+    Q.StartingLoc = MemoryLocation::get(I);
+    Q.Inst = I;
+  }
+  Q.DL = &Q.Inst->getParent()->getModule()->getDataLayout();
+  auto CacheResult = doCacheLookup(StartingAccess, Q, Q.StartingLoc);
+  if (CacheResult)
+    return CacheResult;
+
+  // Short circuit invariant loads
+  if (const LoadInst *LI = dyn_cast<LoadInst>(I))
+    if (LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr) {
+      doCacheInsert(StartingAccess, MSSA->getLiveOnEntryDef(), Q,
+                    Q.StartingLoc);
+      return MSSA->getLiveOnEntryDef();
+    }
+
+  // Start with the thing we already think clobbers this location
+  StartingAccess = StartingAccess->getDefiningAccess();
+
+  // At this point, StartingAccess may be the live on entry def.
+  // If it is, we will not get a better result.
+  if (MSSA->isLiveOnEntryDef(StartingAccess))
+    return StartingAccess;
+  MemoryAccess *FinalAccess = getClobberingMemoryAccess(StartingAccess, Q);
+
+  doCacheInsert(Q.OriginalAccess, FinalAccess, Q, Q.StartingLoc);
+  if (Q.isCall) {
+    for (const auto &C : Q.VisitedCalls)
+      doCacheInsert(C, FinalAccess, Q, Q.StartingLoc);
+  }
+
+  DEBUG(dbgs() << "Starting Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *StartingAccess << "\n");
+  DEBUG(dbgs() << "Final Memory SSA clobber for " << *I << " is ");
+  DEBUG(dbgs() << *FinalAccess << "\n");
+
+  return FinalAccess;
+}
+
+void CachingMemorySSAWalker::invalidateInfo(MemoryAccess *MA) {
+  UpwardsMemoryQuery Q;
+  if (!isa<MemoryPhi>(MA)) {
+    Instruction *I = MA->getMemoryInst();
+    if (ImmutableCallSite(I)) {
+      Q.isCall = true;
+      Q.Inst = I;
+    } else {
+      Q.isCall = false;
+      Q.StartingLoc = MemoryLocation::get(I);
+      Q.Inst = I;
+    }
+  }
+
+  doCacheRemove(MA, Q, Q.StartingLoc);
+}
+
+MemoryAccess *
+DoNothingMemorySSAWalker::getClobberingMemoryAccess(const Instruction *I) {
+  MemoryAccess *MA = MSSA->getMemoryAccess(I);
+  if (isa<MemoryPhi>(MA))
+    return MA;
+  return MA->getDefiningAccess();
+}
+
+MemoryAccess *DoNothingMemorySSAWalker::getClobberingMemoryAccess(
+    MemoryAccess *StartingAccess, MemoryLocation &) {
+  if (isa<MemoryPhi>(StartingAccess))
+    return StartingAccess;
+  return StartingAccess->getDefiningAccess();
+}
+}

test/Transforms/Util/memoryssa-cyclicphi.ll

+; RUN: opt -basicaa -print-memoryssa -verify-memoryssa -analyze < %s 2>&1| FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.hoge = type { i32, %struct.widget }
+%struct.widget = type { i64 }
+define hidden void @quux(%struct.hoge *%f) align 2 {
+  %tmp = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1, i32 0
+  %tmp24 = getelementptr inbounds %struct.hoge, %struct.hoge* %f, i64 0, i32 1
+  %tmp25 = bitcast %struct.widget* %tmp24 to i64**
+  br label %bb26
+
+bb26:                                             ; preds = %bb77, %0
+; CHECK:  3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; 3 = MemoryPhi({%0,liveOnEntry},{bb77,2})
+; CHECK-NEXT:   br i1 undef, label %bb68, label %bb77
+  br i1 undef, label %bb68, label %bb77
+
+bb68:                                             ; preds = %bb26
+; CHECK:  MemoryUse(liveOnEntry)
+; MemoryUse(liveOnEntry)
+; CHECK-NEXT:   %tmp69 = load i64, i64* null, align 8
+  %tmp69 = load i64, i64* null, align 8
+; CHECK:  1 = MemoryDef(3)
+; 1 = MemoryDef(3)
+; CHECK-NEXT:   store i64 %tmp69, i64* %tmp, align 8
+  store i64 %tmp69, i64* %tmp, align 8
+  br label %bb77
+
+bb77:                                             ; preds = %bb68, %bb26
+; CHECK:  2 = MemoryPhi({bb26,3},{bb68,1})
+; 2 = MemoryPhi({bb26,3},{bb68,1})
+; CHECK:  MemoryUse(2)
+; MemoryUse(2)
+; CHECK-NEXT:   %tmp78 = load i64*, i64** %tmp25, align 8
+  %tmp78 = load i64*, i64** %tmp25, align 8
+  %tmp79 = getelementptr inbounds i64, i64* %tmp78, i64 undef
+  br label %bb26
+}

test/Transforms/Util/memoryssa-no-disconnected.ll

+; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1| FileCheck %s
+; This test ensures we don't end up with multiple reaching defs for a single use/phi edge
+; If we were to optimize defs, we would end up with 2= MemoryDef(liveOnEntry) and 4 = MemoryDef(liveOnEntry)
+; Both would mean both 1,2, and 3,4 would reach the phi node.  Because the phi node can only have one entry
+; on each edge, it would choose 2, 4 and disconnect 1 and 3 completely from the SSA graph, even though they
+; are not dead
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128" 
+define void @sink_store(i32 %index, i32* noalias nocapture %foo, i32* noalias nocapture %bar) {
+entry:
+  %cmp = trunc i32 %index to i1
+  br i1 %cmp, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+; CHECK:  1 = MemoryDef(liveOnEntry)
+; 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store i32 %index, i32* %foo, align 4, !alias.scope !0
+  store i32 %index, i32* %foo, align 4, !alias.scope !0
+; CHECK:  2 = MemoryDef(1)
+; 2 = MemoryDef(1)
+; CHECK-NEXT:   store i32 %index, i32* %bar, align 4, !noalias !0
+  store i32 %index, i32* %bar, align 4, !noalias !0
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+; CHECK:  3 = MemoryDef(liveOnEntry)
+; 3 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   store i32 %index, i32* %foo, align 4, !alias.scope !0
+  store i32 %index, i32* %foo, align 4, !alias.scope !0
+; CHECK:  4 = MemoryDef(3)
+; 4 = MemoryDef(3)
+; CHECK-NEXT:   store i32 %index, i32* %bar, align 4, !noalias !0
+  store i32 %index, i32* %bar, align 4, !noalias !0
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+; CHECK:  5 = MemoryPhi({if.then,2},{if.else,4})
+; 5 = MemoryPhi({if.then,2},{if.else,4})
+; CHECK:  MemoryUse(5)
+; MemoryUse(5)
+; CHECK-NEXT:   %c = load i32, i32* %foo, !alias.scope !0
+  %c = load i32, i32* %foo, !alias.scope !0
+; CHECK:  MemoryUse(5)
+; MemoryUse(5)
+; CHECK-NEXT:   %d = load i32, i32* %bar, !noalias !0
+  %d = load i32, i32* %bar, !noalias !0
+  ret void
+}
+!0 = !{!0}

test/Transforms/Util/memoryssa-optimize-use.ll

+; RUN: opt -basicaa -print-memoryssa -analyze -verify-memoryssa < %s 2>&1| FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+; Function Attrs: ssp uwtable
+define i32 @main() #0 {
+entry:
+; CHECK:  1 = MemoryDef(liveOnEntry)
+; 1 = MemoryDef(liveOnEntry)
+; CHECK-NEXT:   %call = call noalias i8* @_Znwm(i64 4) #2
+  %call = call noalias i8* @_Znwm(i64 4) #2
+  %0 = bitcast i8* %call to i32*
+; CHECK:  2 = MemoryDef(1)
+; 2 = MemoryDef(1)
+; CHECK-NEXT:   %call1 = call noalias i8* @_Znwm(i64 4) #2
+  %call1 = call noalias i8* @_Znwm(i64 4) #2
+  %1 = bitcast i8* %call1 to i32*
+; CHECK:  3 = MemoryDef(2)
+; 3 = MemoryDef(2)
+; CHECK-NEXT:   store i32 5, i32* %0, align 4
+  store i32 5, i32* %0, align 4
+; CHECK:  4 = MemoryDef(3)
+; 4 = MemoryDef(3)
+; CHECK-NEXT:   store i32 7, i32* %1, align 4
+  store i32 7, i32* %1, align 4
+; CHECK:  MemoryUse(3)
+; MemoryUse(3)
+; CHECK-NEXT:   %2 = load i32, i32* %0, align 4
+  %2 = load i32, i32* %0, align 4
+; CHECK:  MemoryUse(4)
+; MemoryUse(4)
+; CHECK-NEXT:   %3 = load i32, i32* %1, align 4
+  %3 = load i32, i32* %1, align 4
+; CHECK:  MemoryUse(3)
+; MemoryUse(3)
+; CHECK-NEXT:   %4 = load i32, i32* %0, align 4
+  %4 = load i32, i32* %0, align 4
+; CHECK:  MemoryUse(4)
+; MemoryUse(4)
+; CHECK-NEXT:   %5 = load i32, i32* %1, align 4
+  %5 = load i32, i32* %1, align 4
+  %add = add nsw i32 %3, %5
+  ret i32 %add
+}
+declare noalias i8* @_Znwm(i64) #1
+
+attributes #0 = { ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nobuiltin "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { builtin }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"PIC Level", i32 2}
+!1 = !{!"clang version 3.7.0 (http://llvm.org/git/clang.git c9903b44534b8b5debcdbe375ee5c1fec6cc7243) (llvm/trunk 228022)"}