API to update MemorySSA for cloned blocks.

[asbirlea]

Summary

End goal is to update MemorySSA in all loop passes. LoopUnswitch clones all blocks in a loop. SimpleLoopUnswitch clones some blocks. LoopRotate clones some instructions.
Some loop passes also make CFG changes.
This is an API based on what I found needed in LoopUnswitch, SimpleLoopUnswitch, LoopRotate, LoopInstSimplify, LoopSimplifyCFG.
Adding dependent patches using this API for context.

[asbirlea]

Uploaded D45300 and D45301 to give usage context.

[george.burgess.iv]

This is a DRAFT API based on what I found needed in the old LoopUnswitch pass.

To be clear, does this mean "I only would like feedback on the APIs for the moment; please don't nitpick the actual code before that's set in stone," or "I'd like a full code review, but I'm more than happy to refactor the APIs to something better if we can think of it"?

I'm assuming the former, but am also happy to nitpick. :)

[asbirlea]

First concern is duplicating functionality already present in MemorySSA. I honestly don't understand everything well enough, so it's possible there are chunks that can be factored out from existing methods and the ones in this patch.

Second concern is the best way to expose an update API. Until now, each update call pretty much assumed valid MemorySSA before and after the call. I'm adding APIs where it's known that MemorySSA is broken before the call.

Happy to get nitpicking after the high-level view, just to avoid the distraction.
But if you see something that bugs you now, please feel free to nitpick so we get *that* distraction out of the way :).

Also note that, while the stack of 3 patches doesn't crash any tests, it's not necessarily error-free. It should however give a good view of the end goal.

[• dberlin]

include/llvm/Analysis/MemorySSA.h

780 ↗

(On Diff #141085)

I don't understand the desire here, since it already should correctly identify whether it is a def or use on it's own.
What are you trying to do?

[asbirlea]

include/llvm/Analysis/MemorySSA.h

780 ↗

(On Diff #141085)

I'm trying to avoid the additional getModRefInfo call.

For cloned blocks we have a 1:1 mapping of all instructions. E.g., we know we've just cloned I, with MUD access that's a Use with some defining access. I'm trying to create a MUD for the clone instruction with all that info. The use case is in "CloneUsesAndDefs" below.

Perhaps it's not worth the effort, just trying to avoid AA calls where possible.

[george.burgess.iv]

(Thanks for the patch, by the way!)

So, I've looked at the API at a high level, and I think it's going in a good direction with some tweaks/naming changes. Naturally, whatever we end up standardizing on will need a fair amount of comments explaining what, exactly, it's trying to do/preconditions/etc. :)

FWIW, the naming suggestions are in part to help me be sure I'm not missing anything big WRT respected use-cases, ... So they're a bit shaky at times.

include/llvm/Analysis/MemorySSA.h

780 ↗

(On Diff #141085)

Would it be clearer to pass MemoryUseOrDef *Template and have this function interrogate it, instead of bool Use and bool Def (or split off a cloneMemoryAccess function to go with the whole cloning theme we're doing)? It's a bit more explicit about what you're trying to do (IMO), and it looks like it would simplify calling code a bit.

(Same with createDefinedAccess)

lib/Analysis/MemorySSAUpdater.cpp

378 ↗

(On Diff #141085)

updateForClonedLoop?

Given that we talk about entry blocks, exit blocks, etc. insertAccessesFromMap sounds pretty generic.

508 ↗

(On Diff #141085)

Insert phis if needed because... what happened? :)

I tried to read the loop code, but got a few layers deep in unfamiliar jargon and gave up.

542 ↗

(On Diff #141085)

General note: I think that Seen + Worklist combos can be replaced with a SmallSetVector. Not something we need to worry about at this very second, but...

615 ↗

(On Diff #141085)

So... "I just moved everything from Start to the end of To from From to To (I'm so glad we have backticks to disambiguate code from words). Please update MSSA to note that." ?

I'm assuming there are serious constraints on when this can be used. Moreover, I'm assuming that any use is invalid unless either:

• From was merged into To and is about to be deleted entirely, and From/To logically formed one basic block before the merge (e.g. From's only predecessor was To, and To's only successor was From)
• ...Or To is the result of chopping From in half starting at Start, so they still both logically form one basic block (with the pred/succ constraints mentioned above)

So, from a wording standpoint, I sort of think we should spell out both of those use-cases as separate methods (mergeSplicedBlocks and spliceBlocks?). If they both end up as one-line wrappers around this private moveInBulk, I'm happy with that. I'd just rather not advertise "hey, this is a general bulk move operation. Come to it with all your bulk memory moving needs." Plus, if we're specific in what we allow, we can throw in more asserts to catch mistakes. :)

617 ↗

(On Diff #141085)

I don't see a case in the given usage examples where this needs to be anything but End, and I suspect this gets a bit more complicated if Where != End. Until we need that functionality, can we please just assume it's always End for now? (D45300 uses Beginning, but AFAICT, it's a clean BB anyway. So, End should be equivalent?)

651 ↗

(On Diff #141085)

Why can't this just be "for each user of the last def in To that happens to be a Phi and has From as the old block, update its basic block"?

(We'd also need to special-case when Where != End here, probably, since the last Def in From might not be the last Def in To)

686 ↗

(On Diff #141085)

movePhiToNewImmediatePredecessor maybe?

It's a bit of a mouthful, yeah...

703 ↗

(On Diff #141085)

Yeah. This seems like the better approach to me, since this phi we're creating is identical (from the user's perspective, at least) to the previous one. Faster + (I assume) easier to think about + less code = yay.

[asbirlea]

Address comments.

[asbirlea]

include/llvm/Analysis/MemorySSA.h

780 ↗

(On Diff #141085)

Updated to MemoryUseOrDef *Template = nullptr.

lib/Analysis/MemorySSAUpdater.cpp

508 ↗

(On Diff #141085)

Update to updatePhisWhenAddingBBPredecessors.
Kinda long, but at least more insightful? :-/

542 ↗

(On Diff #141085)

Can you elaborate on this one? The Seen and Worklist structures keep different data, but perhaps I'm missing something here.
Btw, I used the same pattern I saw in fixupDefs, for some consistency.

615 ↗

(On Diff #141085)

You're right. Created moveAllAfterSpliceBlocks and moveAllAfterMergeBlocks.
Both call private member moveAllAccesses.

651 ↗

(On Diff #141085)

This can be called after optimizeUses and some defs may be optimized too. Doesn't this mean that any moved def in To can have users in a Phi, not just the last one?

It should work to go over all Defs in To, and all their users and if those are Phis with From incoming update to To. I think that may be more expensive, if there are a lot of Defs and few successors (transitive too), but it can go both ways.

703 ↗

(On Diff #141085)

Done, but I needed to modify MemorySSA's API to include MemoryPhis: generalized to moveTo(MemoryAccess *).

AFAICT this should be fine, since that call can only used by the updater, and this is the only case where a MemoryPhi is moved.
The alternative is to add another MemorySSA API: moveTo(MemoryPhi *, BasicBlock *) and keep the old one with MemoryUseOrDef. The advantage being the removal of the insertion point. I don't have a strong opinion here.

PTAL.

[asbirlea]

Update patch with the following:

• Fix a few bugs that were triggered by tests in SimpleLoopUnswitch
• Slightly modify current APIs and add a couple APIs motivated by SimpleLoopUnswitch
• Add APIs to delete blocks (SimpleLoopUnswitch modifies the CFG heavily) and MemoryPhi entries.

This is becoming a pretty complex patch, so if you think at least the removeBlocks/delete from MPhis should be in a separate patch, I can split them.

I will upload the patch that updates MSSA in SimpleLoopUnswitch as a dependecy as well.

As far as testing, all tests pass with the sequence of patches, but I am looking into additional testing.

[asbirlea]

Some cleanup and clang-format.

[george.burgess.iv]

(FWIW, Alina and I chatted about this offline. She has a few changes queued up; I'm adding my nits on unchanged bits now, and will do a thorough code review once the new patch is posted)

include/llvm/Analysis/MemorySSAUpdater.h

93 ↗

(On Diff #147539)

nit: all defs, uses, and phis

131 ↗

(On Diff #147539)

Nit: is Start the instruction that was previously the last instruction in To?

105 ↗

(On Diff #145098)

I like the ascii art :)

131 ↗

(On Diff #145098)

Nit: "was added additional predecessors" should probably be worded something like "BB had additional predecessors added"

lib/Analysis/MemorySSAUpdater.cpp

520 ↗

(On Diff #147539)

Please also note that uncloned exit blocks don't have predecessors/successors added

508 ↗

(On Diff #141085)

Much better. :)

I'm inclined to think updatePhisForNewBBPredecessors might be a bit more clear, but I'm also fine with this if you disagree.

542 ↗

(On Diff #141085)

...Do they? AFAICT, conceptually, this code does a BFS across nodes in our graph of BBs, and WorklistBB is the queue we use to visit everything (with Seen keeping us from revisiting). If I'm correct, SmallSetVector sounds like a sane thing here to me.

[asbirlea]

This update is more a whole rewrite of the APIs.

• I separated the cloning into an API that just clones (1:1 mapping) uses and defs in blocks
  • Cloning of blocks must be done in RPO order, assume MSSA api receives the block in the correct order.
  • Note that the cloning API will need to change (again) soon to take a vector of maps, once a pending SimpleLoopUnswitch patch (to make a set of clones of the same block at once) lands.
• Exit blocks are handled separately using the api for blocks getting precedessors
• All edges being added are handled in a single call (update phis when adding BB preds), and may end up looking a lot like the DT update (vector of some "update" type).
  • This call is adding Phis (if needed) in the BBs gaining predecessors and in the IDF of the blocks now defining accesses.
  • Next, it's fixing domination by replacing uses of all defs that may no longer dominate their uses with the nearest dominating def.
  • The algorithm to get this right is fairly complex and it does rely on the Def-Def optimizations being Uses, which is not currently the case.
• APIs to move accesses updated based on future usage in unswitch
• removeBlocks APis simplified in updater and in mssa.

I would appreciate high-level comments on the approach/algorithm first.

[asbirlea]

Rebase after checking in delete APIs.
Updated algorithm for updatePhisWhenAddingBBPred to consider any number of predecessors added for each block.
Updated cloneUseDef signature to use an LoopBlocksRPO.
Updated cloneUseDef to include an API with multiple VMaps, per the SimpleLoopUnswitch change.
Other cleanups.

[asbirlea]

Rebase on recent changes.
Added APIs now greatly simplified. Most updates are now done through applyUpdates.

[asbirlea]

Nit: add a comment.

[george.burgess.iv]

I'm not entirely through this patch (I hope to make more progress in the coming few days), but this is what I have for now. Logic's looking solid so far; I'm just nitpicky. :)

include/llvm/Analysis/MemorySSAUpdater.h

115 ↗

(On Diff #160698)

Do we mutate LoopBlocks/VM anywhere? If not, please constify them (here and in later new functions)

127 ↗

(On Diff #160698)

Same 'please constify if possible' nit, though please make this an ArrayRef instead of const SmallVectorImpl &

[george.burgess.iv]

include/llvm/Analysis/MemorySSAUpdater.h

131 ↗

(On Diff #160698)

nit: why do we take a &DT in this one and a *DT in the other?

267 ↗

(On Diff #160698)

It's unclear to me what the relation between phis/definitions in "a map of MemoryPhi : Definition" is here. Please elaborate

lib/Analysis/MemorySSA.cpp

1548 ↗

(On Diff #160698)

Why || defined(LLVM_ENABLE_DUMP)?

1553 ↗

(On Diff #160698)

nit: s/== true//

lib/Analysis/MemorySSAUpdater.cpp

404 ↗

(On Diff #160698)

naming nit: removeAllDuplicatePhiEdgesBetween?

425 ↗

(On Diff #160698)

please use dyn_cast if MA shouldn't be null

426 ↗

(On Diff #160698)

nit: this should only be null if MA is liveOnEntry. Please check against that instead, for clarity

430 ↗

(On Diff #160698)

same "please don't use or_null if null isn't OK" nit. (though it looks like we could do else { cast<MemoryPhi> here, since we're checking for MUD above?)

441 ↗

(On Diff #160698)

s/or_null//

484 ↗

(On Diff #160698)

s/or_null//

485 ↗

(On Diff #160698)

Please check against liveOnEntry instead

494 ↗

(On Diff #160698)

s/or_null// (and we can probably change this into else { cast<MemoryPhi> anyway)

550 ↗

(On Diff #160698)

can this be a range-for across ExitBlocks?

590 ↗

(On Diff #160698)

nit: please either remove the braces after the if or add them after the else. I'm impartial

697 ↗

(On Diff #160698)

probably redundant with the line below (unless it's possible for us to see the same BB repeatedly?)

702 ↗

(On Diff #160698)

Looks like you can replace everything between { ... } with EdgeCountMap[{Pi, BB}]++;.

operator[] on map-like containers generally acts like "return a reference if it exists. otherwise, construct or zero-init a member in the map and return a ref to that"

708 ↗

(On Diff #160698)

same "looks like you can replace everything between ..."

720 ↗

(On Diff #160698)

nit: There should probably be spaces before the end of each of these quotes

866 ↗

(On Diff #160698)

nit: I think this is long enough that it's best to just have braces after the for and if on lines 837/838. :)

[asbirlea]

Address comments.
Thank you for the detailed nits :).

lib/Analysis/MemorySSA.cpp

1548 ↗

(On Diff #160698)

copy-paste :)..removed.

lib/Analysis/MemorySSAUpdater.cpp

702 ↗

(On Diff #160698)

Ah, I wasn't sure it was zero-inited.

[asbirlea]

Few nits.

[asbirlea]

Rename DTUpdate to CFGUpdate, since now we're using the Update in Support.

[kuhar]

lib/Analysis/MemorySSAUpdater.cpp

662 ↗

(On Diff #160942)

I don't think this will be a bottleneck, but this can be optimized by starting the search at the node with the lowest level (highest in the tree).

[george.burgess.iv]

Lots of nits, and a few functional concerns. For the functional concerns that revolve around dubious edge additions, I'm happy with fixes or "it's impossible for that to actually happen; added a comment explaining that."

(If we do take the "that's impossible; have a comment" route, I assume that we're gating the new loop+MSSA transforms behind some loop-enable-mssa-like flag for a while to gain confidence about the correctness of this all?)

I also think we should have unittests (simple ones are perfectly OK) for the new updater functionality, please.

Like said, this review gave me a few things to do. I'll ping this with revisions when all of that's landed...

lib/Analysis/MemorySSAUpdater.cpp

429 ↗

(On Diff #160942)

It's not immediately clear to me that this can't be tripped in general. e.g.

void foo(int j, int *i) {
  if (j == 1 || j == 2) {
    *i = 0;
  } else {
    *i = 1;
  }
}

I realize this isn't a loopy case, but if we decided, in our infinite wisdom, that it was profitable to have a j == 1 block, a j == 2 block, and an else block, we'd end up with both the j == 1 and j == 2 block having DefMUDI == MSSA->getDefiningAccess(), no?

545 ↗

(On Diff #160942)

nit: no braces, please

559 ↗

(On Diff #160942)

nit: does this line need to be wrapped?

(also, please remove the const in *const; it's inconsistent with the remainder of this file)

577 ↗

(On Diff #160942)

nit: can this be an ArrayRef?

601 ↗

(On Diff #160942)

nit: if (!Rev...empty())

604 ↗

(On Diff #160942)

nit: Is it possible/easy to update DT in-place and undo the updates? The tool I'm using to grok this says that this line always lands in CalculateWithUpdates, which appears to always call CalculateFromScratch. It sometimes gets things wrong with templated code, though, so I could be assuming the wrong thing here.

625 ↗

(On Diff #160942)

(Can this be const, or are we updating it somewhere here?)

627 ↗

(On Diff #160942)

nit: it looks like all the recursion here is tail recursion. Is it possible/easy to rewrite this as a loop with 100% fewer std::function::operator() invocations? :)

635 ↗

(On Diff #160942)

nit: s/count/Count/

662 ↗

(On Diff #160942)

(if there's no reason to add it now, please add a quick TODO with kuhar's comment in case it becomes more desirable in the future)

663 ↗

(On Diff #160942)

nit: const SmallPtrSetImpl<...> &?

665 ↗

(On Diff #160942)

nit: auto * (here and elsewhere in the patch. In general, I think the accepted style for for loops is to prefer const auto & if it's a not-pointer, and const auto * if it's a pointer. Dropping const (and & in the first case) as necessary)

689 ↗

(On Diff #160942)

It looks like we expect PrevPredMap and AddedPredMap to have the same set of keys, and they're sorta related. Would it make sense to have something like

struct PredInfo {
  SmallPtrSet<...> Added;
  SmallPtrSet<...> Prev;
};
SmallDenseMap<BasicBlock *, PredInfo> PredMap;

instead, so the relationship is a bit more clear?

(Or maybe one of these will need to be a SmallSetVector or similar, given the ordering concerns below?)

703 ↗

(On Diff #160942)

To be sure I'm understanding (I'm not overly familiar with the DT APIs), this is saying "for all predecessors of BB, but also including additions in GD, { /* loop body */ }", yeah?

710 ↗

(On Diff #160942)

nit: if (PrevBlockSet.empty())

733 ↗

(On Diff #160942)

FWIW, it looks like this'll make MSSA subtly (and in a way that doesn't matter until we print it) depend on set ordering, which may be bad for writing tests and such.

Since we can iterate over elems in PrevPredMap in any order, we'll be creating these Phis in any order. Since we assign Phis IDs in the order in which they're created ...

In this case, looks like we can just iterate directly over Updates and the problem goes away (assuming Updates is populated in a deterministic order)?

739 ↗

(On Diff #160942)

nit: if you don't plan on mutating the &, make it a const &, please (and below)

741 ↗

(On Diff #160942)

nit: !empty()

755 ↗

(On Diff #160942)

Same (potential) nondeterministic ordering concerns.

760 ↗

(On Diff #160942)

Consider:

   entry
     |
     a
    / \
   |   c
    \ /
     d

a:
  ; 1 = MemoryDef(liveOnEntry)
c:
  ; 2 = MemoryDef(1)
d:
  ; 3 = MemoryPhi({c, 2}, {a, 1})
  ; 4 = MemoryDef(3); optimized to 1

And we add an edge from entry -> d. I don't claim to know when/if this can reasonably happen, but ...

782 ↗

(On Diff #160942)

Would it be more direct to just RAUW this Phi with DefP1, then remove it?

789 ↗

(On Diff #160942)

Same ordering concerns. Maybe this time we could just iterate over BB's preds and fold these two loops into one? As for additions, we may need to have AddedPredMap preserve the order we observe from Updates?

(That would also let us get rid of EdgeCountMap, it seems. Assuming we don't need it when we refactor the loop above)

807 ↗

(On Diff #160942)

Is it possible for BlocksWithDefsToReplace to get duplicates? If so, might it be a good idea to replace that with a SmallPtrSet?

816 ↗

(On Diff #160942)

(I'm assuming that there's some sort of guarantee that IDF calculations only pass these BBs into the DT. If it tries to access preds/succs of a BB, we might get badness, since the DT here may be pretending that we have CFG edges that we don't? Or did I miss us temporarily re-adding edges that were deleted between BBs?)

832 ↗

(On Diff #160942)

Are we sure that we only need to consider BlocksWithDefsToReplace here?

I could be totally misunderstanding, but imagine the following scenario (I'm not even going to try to invent an excuse for when this could happen. :) Just wanted to know if it was considered):

   entry
   /  |
  a   |
 / \  |
 b c  f
 \ /  |
  d   |
   \ /
    e

f:
  ; 1 = MemoryDef(liveOnEntry)
e:
  ; 2 = MemoryPhi({d, liveOnEntry}, {f, 1})

Now imagine that we add an edge f -> c. AFAICT, that would cause us to add a Phi to c (way above) and a Phi to d (idf loop), but I'm failing to see where we'd update the Phi in e to point to the new Phi in d. (Since the only no-longer-dominating BB is a)

Similarly, if d had a MemoryDef in it before we added this edge, would its DefiningAccess get pointed appropriately at this new Phi in d?

835 ↗

(On Diff #160942)

nit: can we scope this more tightly please? e.g. BasicBlock *DominatedBlock = UsrPhi->... and similar in the else

839 ↗

(On Diff #160942)

nit: Can we just do a range-for loop? Looks like we're only calling set on the use, which shouldn't cause any invalidation badness.

842 ↗

(On Diff #160942)

s/dyn_cast/cast/.

If a non-MemoryAccess is using a MemoryAccess, we have problems. :)

852 ↗

(On Diff #160942)

The O(Blocks.size() * AverageBlockMemoryAccessesCount * AverageMemoryAccessUserCount * (Blocks.size() + IDF.size())) (assuming dominates is constant time) behavior here is somewhat concerning to me, though idk if that's an unfounded concern.

If the user is a Def, it's probably best to just deoptimize it; we'll just start from the Def's defining access in the walker anyway. (...Or, well, we would if we noticed that the optimization is now invalid. For reasons unclear to me looking into history + comments, MemoryDef::isOptimized checks the Def's *defining* access, rather than its optimized access. Which is almost definitely incorrect, at least with the aliasing bits we now cache. Working on that now.)

If it's not the Def's optimized access that we're dealing with, then the only new Access that can work is MSSA->getMemoryAccess(U->getBlock()); (since the only way that can happen is if that Def is the first access in a BB, and we've just inserted that block into said BB).

If it's a Use, we'll try to reoptimize starting from its DefiningAccess, which will be whatever this Use points to. It's unclear what the right trade-off is there, since the more aggressive we are here, the less walking we *may* have to do in the future. Depending on the amount of luck involved in this loop's iteration order (e.g. if we remove the break;, is it possible for U to point to something different when the loop terminates? Is that value going to be better, worse, or are we uncertain? The feeling I get is "yes; uncertain," but I haven't fully reasoned through it,) it may be best to just say "point it at the phi of the Use's BB. If that doesn't exist, walk IDoms until we find the last Def."

(Edit: ...Did I never make MemoryDefs stop using WeakVHes to track what they're optimized to? OK. I'll work on that in parallel, too, since I imagine that's pretty necessary for this to work.)

[asbirlea]

Thanks a lot of the comments, working to address them.

A couple of quick clarifications.
Yes, enabling memoryssa is guarded by a flag, see dependent patches (unswitch, simple loop unswitch; the tests for those passes enable the flag so we do check correctness) and a couple of additional patches already landed to update memoryssa, again guarded and currently disabled, but the tests for those passes also enable the flag (the landed patches don't use any of the apis in this patch, hence no dependency).

comments-related:
Currently it does do CalculateFromScratch; it's creating a new DT based on a snapshot CFG where the "Delete" edges are undone. It updates MSSA only for "Inserts" added, then doing the "Deletes".
I have additional work I need to do to cleanup DT to use a GraphDiff internally as part of its update process (replace BatchUpdateInfo), and then I should be able to have this be an incremental update of doing the deletes in reverse (i.e. re-insert edges).
As for the IDF accessing succ/pred, it does! I taught it to use a snapshot graph too (GraphDiff passed as arg) in D50675.
Using a GraphDiff and the GraphTraits defined in CFGDiff.h should be the common interface for all.
Long-story short, there's a lot more work to be done before this is enabled :)

[asbirlea]

I'm planning to add a few more unittests, but sending the updates now for additional comments.

lib/Analysis/MemorySSAUpdater.cpp

604 ↗

(On Diff #160942)

At the moment we are creating a new DT. I should be able to optimize this after cleaning up DT to use GraphDiff internally. For now, added a comment.

703 ↗

(On Diff #160942)

Yes. The additions in GD in this case are edges that were removed and that we're reinserting for the scope of this update.

760 ↗

(On Diff #160942)

Fixed. Even if a Phi exists, continue to the section below that updates defs in BlocksWithDefsToReplace. Added test case as well.

807 ↗

(On Diff #160942)

We cannot get duplicates. We're walking up the DT, no cycles.

816 ↗

(On Diff #160942)

The GD passes as argument to IDF takes care of that.

832 ↗

(On Diff #160942)

This should be handled in the IDF loop above, fixed there.
Added testcase for this scenario.

839 ↗

(On Diff #160942)

I may be missing something, but if I do:
for (Use &U : DefToReplaceUses.uses()), I get a crash.
I guess the set() does invalidate the iterator? See below, the ++UI needs to be before U.set().

852 ↗

(On Diff #160942)

This should be fixed. Added testcase as well.

[asbirlea]

Address comments.

[asbirlea]

Fix bug introduced by refactoring.

[george.burgess.iv]

LGTM. Thanks for this!

lib/Analysis/MemorySSAUpdater.cpp

839 ↗

(On Diff #160942)

That's surprising, but WFM. :)

699 ↗

(On Diff #163598)

s/teh/the

704 ↗

(On Diff #163598)

s/ / / (two spaces -> one)

[asbirlea]

Small update triggered by a test in rotate (patch to be uploaded soon).

[asbirlea]

Thank you for the patience on this review! :)

I'm doing some additional offline testing before landing (+ the nits you noticed).

[asbirlea]

Final update before commit: changing a cast_or_null to dyn_cast_or_null for cloned instructions. LoopRotate can place Value in the map, as the clone of an instruction.

llvm/trunk/include/llvm/Analysis/MemorySSA.h

protected:
   }
 
   void removeFromLookups(MemoryAccess *);
   void removeFromLists(MemoryAccess *, bool ShouldDelete = true);
   void insertIntoListsForBlock(MemoryAccess *, const BasicBlock *,
                                InsertionPlace);
   void insertIntoListsBefore(MemoryAccess *, const BasicBlock *,
                              AccessList::iterator);
-  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *);
+  MemoryUseOrDef *createDefinedAccess(Instruction *, MemoryAccess *,
+                                      const MemoryUseOrDef *Template = nullptr);
 
 private:
   class CachingWalker;
   class OptimizeUses;
 
   CachingWalker *getWalkerImpl();
   void buildMemorySSA();
   void optimizeUses();
 
   void prepareForMoveTo(MemoryAccess *, BasicBlock *);
   void verifyUseInDefs(MemoryAccess *, MemoryAccess *) const;
 
   using AccessMap = DenseMap<const BasicBlock *, std::unique_ptr<AccessList>>;
   using DefsMap = DenseMap<const BasicBlock *, std::unique_ptr<DefsList>>;
 
   void
   determineInsertionPoint(const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks);
   void markUnreachableAsLiveOnEntry(BasicBlock *BB);
   bool dominatesUse(const MemoryAccess *, const MemoryAccess *) const;
   MemoryPhi *createMemoryPhi(BasicBlock *BB);
-  MemoryUseOrDef *createNewAccess(Instruction *);
+  MemoryUseOrDef *createNewAccess(Instruction *,
+                                  const MemoryUseOrDef *Template = nullptr);
   MemoryAccess *findDominatingDef(BasicBlock *, enum InsertionPlace);
   void placePHINodes(const SmallPtrSetImpl<BasicBlock *> &);
   MemoryAccess *renameBlock(BasicBlock *, MemoryAccess *, bool);
   void renameSuccessorPhis(BasicBlock *, MemoryAccess *, bool);
   void renamePass(DomTreeNode *, MemoryAccess *IncomingVal,
                   SmallPtrSetImpl<BasicBlock *> &Visited,
                   bool SkipVisited = false, bool RenameAllUses = false);
   AccessList *getOrCreateAccessList(const BasicBlock *);

llvm/trunk/include/llvm/Analysis/MemorySSAUpdater.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 #define LLVM_ANALYSIS_MEMORYSSAUPDATER_H
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
+#include "llvm/IR/ValueMap.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 
 namespace llvm {
 
 class Function;
 class Instruction;
 class MemoryAccess;
 class LLVMContext;
 class raw_ostream;
 
+using ValueToValueMapTy = ValueMap<const Value *, WeakTrackingVH>;
+using PhiToDefMap = SmallDenseMap<MemoryPhi *, MemoryAccess *>;
+using CFGUpdate = cfg::Update<BasicBlock *>;
+using GraphDiffInvBBPair =
+    std::pair<const GraphDiff<BasicBlock *> *, Inverse<BasicBlock *>>;
+
 class MemorySSAUpdater {
 private:
   MemorySSA *MSSA;
 
   /// We use WeakVH rather than a costly deletion to deal with dangling pointers.
   /// MemoryPhis are created eagerly and sometimes get zapped shortly afterwards.
   SmallVector<WeakVH, 16> InsertedPHIs;
 
   SmallPtrSet<BasicBlock *, 8> VisitedBlocks;
   SmallSet<AssertingVH<MemoryPhi>, 8> NonOptPhis;
 
 public:
   MemorySSAUpdater(MemorySSA *MSSA) : MSSA(MSSA) {}
+
   /// Insert a definition into the MemorySSA IR.  RenameUses will rename any use
   /// below the new def block (and any inserted phis).  RenameUses should be set
   /// to true if the definition may cause new aliases for loads below it.  This
   /// is not the case for hoisting or sinking or other forms of code *movement*.
   /// It *is* the case for straight code insertion.
   /// For example:
   /// store a
   /// if (foo) { }
   /// load a
   ///
   /// Moving the store into the if block, and calling insertDef, does not
   /// require RenameUses.
   /// However, changing it to:
   /// store a
   /// if (foo) { store b }
   /// load a
   /// Where a mayalias b, *does* require RenameUses be set to true.
   void insertDef(MemoryDef *Def, bool RenameUses = false);
   void insertUse(MemoryUse *Use);
+  /// Update the MemoryPhi in `To` following an edge deletion between `From` and
+  /// `To`. If `To` becomes unreachable, a call to removeBlocks should be made.
+  void removeEdge(BasicBlock *From, BasicBlock *To);
+  /// Update the MemoryPhi in `To` to have a single incoming edge from `From`,
+  /// following a CFG change that replaced multiple edges (switch) with a direct
+  /// branch.
+  void removeDuplicatePhiEdgesBetween(BasicBlock *From, BasicBlock *To);
+  /// Update MemorySSA after a loop was cloned, given the blocks in RPO order,
+  /// the exit blocks and a 1:1 mapping of all blocks and instructions
+  /// cloned. This involves duplicating all defs and uses in the cloned blocks
+  /// Updating phi nodes in exit block successors is done separately.
+  void updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
+                           ArrayRef<BasicBlock *> ExitBlocks,
+                           const ValueToValueMapTy &VM,
+                           bool IgnoreIncomingWithNoClones = false);
+  // Block BB was fully or partially cloned into its predecessor P1. Map
+  // contains the 1:1 mapping of instructions cloned and VM[BB]=P1.
+  void updateForClonedBlockIntoPred(BasicBlock *BB, BasicBlock *P1,
+                                    const ValueToValueMapTy &VM);
+  /// Update phi nodes in exit block successors following cloning. Exit blocks
+  /// that were not cloned don't have additional predecessors added.
+  void updateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+                                     const ValueToValueMapTy &VMap,
+                                     DominatorTree &DT);
+  void updateExitBlocksForClonedLoop(
+      ArrayRef<BasicBlock *> ExitBlocks,
+      ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT);
+
+  /// Apply CFG updates, analogous with the DT edge updates.
+  void applyUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+  /// Apply CFG insert updates, analogous with the DT edge updates.
+  void applyInsertUpdates(ArrayRef<CFGUpdate> Updates, DominatorTree &DT);
+
   void moveBefore(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveAfter(MemoryUseOrDef *What, MemoryUseOrDef *Where);
   void moveToPlace(MemoryUseOrDef *What, BasicBlock *BB,
                    MemorySSA::InsertionPlace Where);
   /// `From` block was spliced into `From` and `To`. There is a CFG edge from
   /// `From` to `To`. Move all accesses from `From` to `To` starting at
   /// instruction `Start`. `To` is newly created BB, so empty of
   /// MemorySSA::MemoryAccesses. Edges are already updated, so successors of
getPreviousDefFromEnd(BasicBlock *,
                         DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *
   getPreviousDefRecursive(BasicBlock *,
                           DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &);
   MemoryAccess *recursePhi(MemoryAccess *Phi);
   template <class RangeType>
   MemoryAccess *tryRemoveTrivialPhi(MemoryPhi *Phi, RangeType &Operands);
   void fixupDefs(const SmallVectorImpl<WeakVH> &);
+  // Clone all uses and defs from BB to NewBB given a 1:1 map of all
+  // instructions and blocks cloned, and a map of MemoryPhi : Definition
+  // (MemoryAccess Phi or Def). VMap maps old instructions to cloned
+  // instructions and old blocks to cloned blocks. MPhiMap, is created in the
+  // caller of this private method, and maps existing MemoryPhis to new
+  // definitions that new MemoryAccesses must point to. These definitions may
+  // not necessarily be MemoryPhis themselves, they may be MemoryDefs. As such,
+  // the map is between MemoryPhis and MemoryAccesses, where the MemoryAccesses
+  // may be MemoryPhis or MemoryDefs and not MemoryUses.
+  void cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+                        const ValueToValueMapTy &VMap, PhiToDefMap &MPhiMap);
+  template <typename Iter>
+  void privateUpdateExitBlocksForClonedLoop(ArrayRef<BasicBlock *> ExitBlocks,
+                                            Iter ValuesBegin, Iter ValuesEnd,
+                                            DominatorTree &DT);
+  void applyInsertUpdates(ArrayRef<CFGUpdate>, DominatorTree &DT,
+                          const GraphDiff<BasicBlock *> *GD);
 };
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_MEMORYSSAUPDATER_H

llvm/trunk/lib/Analysis/MemorySSA.cpp

MemoryPhi *MemorySSA::createMemoryPhi(BasicBlock *BB) {
   MemoryPhi *Phi = new MemoryPhi(BB->getContext(), BB, NextID++);
   // Phi's always are placed at the front of the block.
   insertIntoListsForBlock(Phi, BB, Beginning);
   ValueToMemoryAccess[BB] = Phi;
   return Phi;
 }
 
 MemoryUseOrDef *MemorySSA::createDefinedAccess(Instruction *I,
-                                               MemoryAccess *Definition) {
+                                               MemoryAccess *Definition,
+                                               const MemoryUseOrDef *Template) {
   assert(!isa<PHINode>(I) && "Cannot create a defined access for a PHI");
-  MemoryUseOrDef *NewAccess = createNewAccess(I);
+  MemoryUseOrDef *NewAccess = createNewAccess(I, Template);
   assert(
       NewAccess != nullptr &&
       "Tried to create a memory access for a non-memory touching instruction");
   NewAccess->setDefiningAccess(Definition);
   return NewAccess;
 }
 
 // Return true if the instruction has ordering constraints.
 // Note specifically that this only considers stores and loads
 // because others are still considered ModRef by getModRefInfo.
 static inline bool isOrdered(const Instruction *I) {
   if (auto *SI = dyn_cast<StoreInst>(I)) {
     if (!SI->isUnordered())
       return true;
   } else if (auto *LI = dyn_cast<LoadInst>(I)) {
     if (!LI->isUnordered())
       return true;
   }
   return false;
 }
 
 /// Helper function to create new memory accesses
-MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I) {
+MemoryUseOrDef *MemorySSA::createNewAccess(Instruction *I,
+                                           const MemoryUseOrDef *Template) {
   // The assume intrinsic has a control dependency which we model by claiming
   // that it writes arbitrarily. Ignore that fake memory dependency here.
   // FIXME: Replace this special casing with a more accurate modelling of
   // assume's control dependency.
   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
     if (II->getIntrinsicID() == Intrinsic::assume)
       return nullptr;
 
+  bool Def, Use;
+  if (Template) {
+    Def = dyn_cast_or_null<MemoryDef>(Template) != nullptr;
+    Use = dyn_cast_or_null<MemoryUse>(Template) != nullptr;
+#if !defined(NDEBUG)
+    ModRefInfo ModRef = AA->getModRefInfo(I, None);
+    bool DefCheck, UseCheck;
+    DefCheck = isModSet(ModRef) || isOrdered(I);
+    UseCheck = isRefSet(ModRef);
+    assert(Def == DefCheck && (Def || Use == UseCheck) && "Invalid template");
+#endif
+  } else {
     // Find out what affect this instruction has on memory.
     ModRefInfo ModRef = AA->getModRefInfo(I, None);
     // The isOrdered check is used to ensure that volatiles end up as defs
     // (atomics end up as ModRef right now anyway).  Until we separate the
     // ordering chain from the memory chain, this enables people to see at least
     // some relative ordering to volatiles.  Note that getClobberingMemoryAccess
     // will still give an answer that bypasses other volatile loads.  TODO:
-  // Separate memory aliasing and ordering into two different chains so that we
-  // can precisely represent both "what memory will this read/write/is clobbered
-  // by" and "what instructions can I move this past".
-  bool Def = isModSet(ModRef) || isOrdered(I);
-  bool Use = isRefSet(ModRef);
+    // Separate memory aliasing and ordering into two different chains so that
+    // we can precisely represent both "what memory will this read/write/is
+    // clobbered by" and "what instructions can I move this past".
+    Def = isModSet(ModRef) || isOrdered(I);
+    Use = isRefSet(ModRef);
+  }
 
   // It's possible for an instruction to not modify memory at all. During
   // construction, we ignore them.
   if (!Def && !Use)
     return nullptr;
 
   MemoryUseOrDef *MUD;
   if (Def)

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

 //===-- MemorySSAUpdater.cpp - Memory SSA Updater--------------------===//
 //
 //                     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 MemorySSAUpdater class.
 //
 //===----------------------------------------------------------------===//
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
while (!Worklist.empty()) {
             continue;
           Worklist.push_back(S);
         }
       }
     }
   }
 }
 
+void MemorySSAUpdater::removeEdge(BasicBlock *From, BasicBlock *To) {
+  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
+    MPhi->unorderedDeleteIncomingBlock(From);
+    if (MPhi->getNumIncomingValues() == 1)
+      removeMemoryAccess(MPhi);
+  }
+}
+
+void MemorySSAUpdater::removeDuplicatePhiEdgesBetween(BasicBlock *From,
+                                                      BasicBlock *To) {
+  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(To)) {
+    bool Found = false;
+    MPhi->unorderedDeleteIncomingIf([&](const MemoryAccess *, BasicBlock *B) {
+      if (From != B)
+        return false;
+      if (Found)
+        return true;
+      Found = true;
+      return false;
+    });
+    if (MPhi->getNumIncomingValues() == 1)
+      removeMemoryAccess(MPhi);
+  }
+}
+
+void MemorySSAUpdater::cloneUsesAndDefs(BasicBlock *BB, BasicBlock *NewBB,
+                                        const ValueToValueMapTy &VMap,
+                                        PhiToDefMap &MPhiMap) {
+  auto GetNewDefiningAccess = [&](MemoryAccess *MA) -> MemoryAccess * {
+    MemoryAccess *InsnDefining = MA;
+    if (MemoryUseOrDef *DefMUD = dyn_cast<MemoryUseOrDef>(InsnDefining)) {
+      if (!MSSA->isLiveOnEntryDef(DefMUD)) {
+        Instruction *DefMUDI = DefMUD->getMemoryInst();
+        assert(DefMUDI && "Found MemoryUseOrDef with no Instruction.");
+        if (Instruction *NewDefMUDI =
+                cast_or_null<Instruction>(VMap.lookup(DefMUDI)))
+          InsnDefining = MSSA->getMemoryAccess(NewDefMUDI);
+      }
+    } else {
+      MemoryPhi *DefPhi = cast<MemoryPhi>(InsnDefining);
+      if (MemoryAccess *NewDefPhi = MPhiMap.lookup(DefPhi))
+        InsnDefining = NewDefPhi;
+    }
+    assert(InsnDefining && "Defining instruction cannot be nullptr.");
+    return InsnDefining;
+  };
+
+  const MemorySSA::AccessList *Acc = MSSA->getBlockAccesses(BB);
+  if (!Acc)
+    return;
+  for (const MemoryAccess &MA : *Acc) {
+    if (const MemoryUseOrDef *MUD = dyn_cast<MemoryUseOrDef>(&MA)) {
+      Instruction *Insn = MUD->getMemoryInst();
+      // Entry does not exist if the clone of the block did not clone all
+      // instructions. This occurs in LoopRotate when cloning instructions
+      // from the old header to the old preheader. The cloned instruction may
+      // also be a simplified Value, not an Instruction (see LoopRotate).
+      if (Instruction *NewInsn =
+              dyn_cast_or_null<Instruction>(VMap.lookup(Insn))) {
+        MemoryAccess *NewUseOrDef = MSSA->createDefinedAccess(
+            NewInsn, GetNewDefiningAccess(MUD->getDefiningAccess()), MUD);
+        MSSA->insertIntoListsForBlock(NewUseOrDef, NewBB, MemorySSA::End);
+      }
+    }
+  }
+}
+
+void MemorySSAUpdater::updateForClonedLoop(const LoopBlocksRPO &LoopBlocks,
+                                           ArrayRef<BasicBlock *> ExitBlocks,
+                                           const ValueToValueMapTy &VMap,
+                                           bool IgnoreIncomingWithNoClones) {
+  PhiToDefMap MPhiMap;
+
+  auto FixPhiIncomingValues = [&](MemoryPhi *Phi, MemoryPhi *NewPhi) {
+    assert(Phi && NewPhi && "Invalid Phi nodes.");
+    BasicBlock *NewPhiBB = NewPhi->getBlock();
+    SmallPtrSet<BasicBlock *, 4> NewPhiBBPreds(pred_begin(NewPhiBB),
+                                               pred_end(NewPhiBB));
+    for (unsigned It = 0, E = Phi->getNumIncomingValues(); It < E; ++It) {
+      MemoryAccess *IncomingAccess = Phi->getIncomingValue(It);
+      BasicBlock *IncBB = Phi->getIncomingBlock(It);
+
+      if (BasicBlock *NewIncBB = cast_or_null<BasicBlock>(VMap.lookup(IncBB)))
+        IncBB = NewIncBB;
+      else if (IgnoreIncomingWithNoClones)
+        continue;
+
+      // Now we have IncBB, and will need to add incoming from it to NewPhi.
+
+      // If IncBB is not a predecessor of NewPhiBB, then do not add it.
+      // NewPhiBB was cloned without that edge.
+      if (!NewPhiBBPreds.count(IncBB))
+        continue;
+
+      // Determine incoming value and add it as incoming from IncBB.
+      if (MemoryUseOrDef *IncMUD = dyn_cast<MemoryUseOrDef>(IncomingAccess)) {
+        if (!MSSA->isLiveOnEntryDef(IncMUD)) {
+          Instruction *IncI = IncMUD->getMemoryInst();
+          assert(IncI && "Found MemoryUseOrDef with no Instruction.");
+          if (Instruction *NewIncI =
+                  cast_or_null<Instruction>(VMap.lookup(IncI))) {
+            IncMUD = MSSA->getMemoryAccess(NewIncI);
+            assert(IncMUD &&
+                   "MemoryUseOrDef cannot be null, all preds processed.");
+          }
+        }
+        NewPhi->addIncoming(IncMUD, IncBB);
+      } else {
+        MemoryPhi *IncPhi = cast<MemoryPhi>(IncomingAccess);
+        if (MemoryAccess *NewDefPhi = MPhiMap.lookup(IncPhi))
+          NewPhi->addIncoming(NewDefPhi, IncBB);
+        else
+          NewPhi->addIncoming(IncPhi, IncBB);
+      }
+    }
+  };
+
+  auto ProcessBlock = [&](BasicBlock *BB) {
+    BasicBlock *NewBlock = cast_or_null<BasicBlock>(VMap.lookup(BB));
+    if (!NewBlock)
+      return;
+
+    assert(!MSSA->getWritableBlockAccesses(NewBlock) &&
+           "Cloned block should have no accesses");
+
+    // Add MemoryPhi.
+    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB)) {
+      MemoryPhi *NewPhi = MSSA->createMemoryPhi(NewBlock);
+      MPhiMap[MPhi] = NewPhi;
+    }
+    // Update Uses and Defs.
+    cloneUsesAndDefs(BB, NewBlock, VMap, MPhiMap);
+  };
+
+  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
+    ProcessBlock(BB);
+
+  for (auto BB : llvm::concat<BasicBlock *const>(LoopBlocks, ExitBlocks))
+    if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
+      if (MemoryAccess *NewPhi = MPhiMap.lookup(MPhi))
+        FixPhiIncomingValues(MPhi, cast<MemoryPhi>(NewPhi));
+}
+
+void MemorySSAUpdater::updateForClonedBlockIntoPred(
+    BasicBlock *BB, BasicBlock *P1, const ValueToValueMapTy &VM) {
+  // All defs/phis from outside BB that are used in BB, are valid uses in P1.
+  // Since those defs/phis must have dominated BB, and also dominate P1.
+  // Defs from BB being used in BB will be replaced with the cloned defs from
+  // VM. The uses of BB's Phi (if it exists) in BB will be replaced by the
+  // incoming def into the Phi from P1.
+  PhiToDefMap MPhiMap;
+  if (MemoryPhi *MPhi = MSSA->getMemoryAccess(BB))
+    MPhiMap[MPhi] = MPhi->getIncomingValueForBlock(P1);
+  cloneUsesAndDefs(BB, P1, VM, MPhiMap);
+}
+
+template <typename Iter>
+void MemorySSAUpdater::privateUpdateExitBlocksForClonedLoop(
+    ArrayRef<BasicBlock *> ExitBlocks, Iter ValuesBegin, Iter ValuesEnd,
+    DominatorTree &DT) {
+  SmallVector<CFGUpdate, 4> Updates;
+  // Update/insert phis in all successors of exit blocks.
+  for (auto *Exit : ExitBlocks)
+    for (const ValueToValueMapTy *VMap : make_range(ValuesBegin, ValuesEnd))
+      if (BasicBlock *NewExit = cast_or_null<BasicBlock>(VMap->lookup(Exit))) {
+        BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0);
+        Updates.push_back({DT.Insert, NewExit, ExitSucc});
+      }
+  applyInsertUpdates(Updates, DT);
+}
+
+void MemorySSAUpdater::updateExitBlocksForClonedLoop(
+    ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap,
+    DominatorTree &DT) {
+  const ValueToValueMapTy *const Arr[] = {&VMap};
+  privateUpdateExitBlocksForClonedLoop(ExitBlocks, std::begin(Arr),
+                                       std::end(Arr), DT);
+}
+
+void MemorySSAUpdater::updateExitBlocksForClonedLoop(
+    ArrayRef<BasicBlock *> ExitBlocks,
+    ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT) {
+  auto GetPtr = [&](const std::unique_ptr<ValueToValueMapTy> &I) {
+    return I.get();
+  };
+  using MappedIteratorType =
+      mapped_iterator<const std::unique_ptr<ValueToValueMapTy> *,
+                      decltype(GetPtr)>;
+  auto MapBegin = MappedIteratorType(VMaps.begin(), GetPtr);
+  auto MapEnd = MappedIteratorType(VMaps.end(), GetPtr);
+  privateUpdateExitBlocksForClonedLoop(ExitBlocks, MapBegin, MapEnd, DT);
+}
+
+void MemorySSAUpdater::applyUpdates(ArrayRef<CFGUpdate> Updates,
+                                    DominatorTree &DT) {
+  SmallVector<CFGUpdate, 4> RevDeleteUpdates;
+  SmallVector<CFGUpdate, 4> InsertUpdates;
+  for (auto &Update : Updates) {
+    if (Update.getKind() == DT.Insert)
+      InsertUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
+    else
+      RevDeleteUpdates.push_back({DT.Insert, Update.getFrom(), Update.getTo()});
+  }
+
+  if (!RevDeleteUpdates.empty()) {
+    // Update for inserted edges: use newDT and snapshot CFG as if deletes had
+    // not occured.
+    // FIXME: This creates a new DT, so it's more expensive to do mix
+    // delete/inserts vs just inserts. We can do an incremental update on the DT
+    // to revert deletes, than re-delete the edges. Teaching DT to do this, is
+    // part of a pending cleanup.
+    DominatorTree NewDT(DT, RevDeleteUpdates);
+    GraphDiff<BasicBlock *> GD(RevDeleteUpdates);
+    applyInsertUpdates(InsertUpdates, NewDT, &GD);
+  } else {
+    GraphDiff<BasicBlock *> GD;
+    applyInsertUpdates(InsertUpdates, DT, &GD);
+  }
+
+  // Update for deleted edges
+  for (auto &Update : RevDeleteUpdates)
+    removeEdge(Update.getFrom(), Update.getTo());
+}
+
+void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
+                                          DominatorTree &DT) {
+  GraphDiff<BasicBlock *> GD;
+  applyInsertUpdates(Updates, DT, &GD);
+}
+
+void MemorySSAUpdater::applyInsertUpdates(ArrayRef<CFGUpdate> Updates,
+                                          DominatorTree &DT,
+                                          const GraphDiff<BasicBlock *> *GD) {
+  // Get recursive last Def, assuming well formed MSSA and updated DT.
+  auto GetLastDef = [&](BasicBlock *BB) -> MemoryAccess * {
+    while (true) {
+      MemorySSA::DefsList *Defs = MSSA->getWritableBlockDefs(BB);
+      // Return last Def or Phi in BB, if it exists.
+      if (Defs)
+        return &*(--Defs->end());
+
+      // Check number of predecessors, we only care if there's more than one.
+      unsigned Count = 0;
+      BasicBlock *Pred = nullptr;
+      for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
+        Pred = Pair.second;
+        Count++;
+        if (Count == 2)
+          break;
+      }
+
+      // If BB has multiple predecessors, get last definition from IDom.
+      if (Count != 1) {
+        // [SimpleLoopUnswitch] If BB is a dead block, about to be deleted, its
+        // DT is invalidated. Return LoE as its last def. This will be added to
+        // MemoryPhi node, and later deleted when the block is deleted.
+        if (!DT.getNode(BB))
+          return MSSA->getLiveOnEntryDef();
+        if (auto *IDom = DT.getNode(BB)->getIDom())
+          if (IDom->getBlock() != BB) {
+            BB = IDom->getBlock();
+            continue;
+          }
+        return MSSA->getLiveOnEntryDef();
+      } else {
+        // Single predecessor, BB cannot be dead. GetLastDef of Pred.
+        assert(Count == 1 && Pred && "Single predecessor expected.");
+        BB = Pred;
+      }
+    };
+    llvm_unreachable("Unable to get last definition.");
+  };
+
+  // Get nearest IDom given a set of blocks.
+  // TODO: this can be optimized by starting the search at the node with the
+  // lowest level (highest in the tree).
+  auto FindNearestCommonDominator =
+      [&](const SmallSetVector<BasicBlock *, 2> &BBSet) -> BasicBlock * {
+    BasicBlock *PrevIDom = *BBSet.begin();
+    for (auto *BB : BBSet)
+      PrevIDom = DT.findNearestCommonDominator(PrevIDom, BB);
+    return PrevIDom;
+  };
+
+  // Get all blocks that dominate PrevIDom, stop when reaching CurrIDom. Do not
+  // include CurrIDom.
+  auto GetNoLongerDomBlocks =
+      [&](BasicBlock *PrevIDom, BasicBlock *CurrIDom,
+          SmallVectorImpl<BasicBlock *> &BlocksPrevDom) {
+        if (PrevIDom == CurrIDom)
+          return;
+        BlocksPrevDom.push_back(PrevIDom);
+        BasicBlock *NextIDom = PrevIDom;
+        while (BasicBlock *UpIDom =
+                   DT.getNode(NextIDom)->getIDom()->getBlock()) {
+          if (UpIDom == CurrIDom)
+            break;
+          BlocksPrevDom.push_back(UpIDom);
+          NextIDom = UpIDom;
+        }
+      };
+
+  // Map a BB to its predecessors: added + previously existing. To get a
+  // deterministic order, store predecessors as SetVectors. The order in each
+  // will be defined by teh order in Updates (fixed) and the order given by
+  // children<> (also fixed). Since we further iterate over these ordered sets,
+  // we lose the information of multiple edges possibly existing between two
+  // blocks, so we'll keep and EdgeCount map for that.
+  // An alternate implementation could keep unordered set for the predecessors,
+  // traverse either Updates or children<> each time to get  the deterministic
+  // order, and drop the usage of EdgeCount. This alternate approach would still
+  // require querying the maps for each predecessor, and children<> call has
+  // additional computation inside for creating the snapshot-graph predecessors.
+  // As such, we favor using a little additional storage and less compute time.
+  // This decision can be revisited if we find the alternative more favorable.
+
+  struct PredInfo {
+    SmallSetVector<BasicBlock *, 2> Added;
+    SmallSetVector<BasicBlock *, 2> Prev;
+  };
+  SmallDenseMap<BasicBlock *, PredInfo> PredMap;
+
+  for (auto &Edge : Updates) {
+    BasicBlock *BB = Edge.getTo();
+    auto &AddedBlockSet = PredMap[BB].Added;
+    AddedBlockSet.insert(Edge.getFrom());
+  }
+
+  // Store all existing predecessor for each BB, at least one must exist.
+  SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, int> EdgeCountMap;
+  SmallPtrSet<BasicBlock *, 2> NewBlocks;
+  for (auto &BBPredPair : PredMap) {
+    auto *BB = BBPredPair.first;
+    const auto &AddedBlockSet = BBPredPair.second.Added;
+    auto &PrevBlockSet = BBPredPair.second.Prev;
+    for (auto &Pair : children<GraphDiffInvBBPair>({GD, BB})) {
+      BasicBlock *Pi = Pair.second;
+      if (!AddedBlockSet.count(Pi))
+        PrevBlockSet.insert(Pi);
+      EdgeCountMap[{Pi, BB}]++;
+    }
+
+    if (PrevBlockSet.empty()) {
+      assert(pred_size(BB) == AddedBlockSet.size() && "Duplicate edges added.");
+      LLVM_DEBUG(
+          dbgs()
+          << "Adding a predecessor to a block with no predecessors. "
+             "This must be an edge added to a new, likely cloned, block. "
+             "Its memory accesses must be already correct, assuming completed "
+             "via the updateExitBlocksForClonedLoop API. "
+             "Assert a single such edge is added so no phi addition or "
+             "additional processing is required.\n");
+      assert(AddedBlockSet.size() == 1 &&
+             "Can only handle adding one predecessor to a new block.");
+      // Need to remove new blocks from PredMap. Remove below to not invalidate
+      // iterator here.
+      NewBlocks.insert(BB);
+    }
+  }
+  // Nothing to process for new/cloned blocks.
+  for (auto *BB : NewBlocks)
+    PredMap.erase(BB);
+
+  SmallVector<BasicBlock *, 8> BlocksToProcess;
+  SmallVector<BasicBlock *, 16> BlocksWithDefsToReplace;
+
+  // First create MemoryPhis in all blocks that don't have one. Create in the
+  // order found in Updates, not in PredMap, to get deterministic numbering.
+  for (auto &Edge : Updates) {
+    BasicBlock *BB = Edge.getTo();
+    if (PredMap.count(BB) && !MSSA->getMemoryAccess(BB))
+      MSSA->createMemoryPhi(BB);
+  }
+
+  // Now we'll fill in the MemoryPhis with the right incoming values.
+  for (auto &BBPredPair : PredMap) {
+    auto *BB = BBPredPair.first;
+    const auto &PrevBlockSet = BBPredPair.second.Prev;
+    const auto &AddedBlockSet = BBPredPair.second.Added;
+    assert(!PrevBlockSet.empty() &&
+           "At least one previous predecessor must exist.");
+
+    // TODO: if this becomes a bottleneck, we can save on GetLastDef calls by
+    // keeping this map before the loop. We can reuse already populated entries
+    // if an edge is added from the same predecessor to two different blocks,
+    // and this does happen in rotate. Note that the map needs to be updated
+    // when deleting non-necessary phis below, if the phi is in the map by
+    // replacing the value with DefP1.
+    SmallDenseMap<BasicBlock *, MemoryAccess *> LastDefAddedPred;
+    for (auto *AddedPred : AddedBlockSet) {
+      auto *DefPn = GetLastDef(AddedPred);
+      assert(DefPn != nullptr && "Unable to find last definition.");
+      LastDefAddedPred[AddedPred] = DefPn;
+    }
+
+    MemoryPhi *NewPhi = MSSA->getMemoryAccess(BB);
+    // If Phi is not empty, add an incoming edge from each added pred. Must
+    // still compute blocks with defs to replace for this block below.
+    if (NewPhi->getNumOperands()) {
+      for (auto *Pred : AddedBlockSet) {
+        auto *LastDefForPred = LastDefAddedPred[Pred];
+        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
+          NewPhi->addIncoming(LastDefForPred, Pred);
+      }
+    } else {
+      // Pick any existing predecessor and get its definition. All other
+      // existing predecessors should have the same one, since no phi existed.
+      auto *P1 = *PrevBlockSet.begin();
+      MemoryAccess *DefP1 = GetLastDef(P1);
+
+      // Check DefP1 against all Defs in LastDefPredPair. If all the same,
+      // nothing to add.
+      bool InsertPhi = false;
+      for (auto LastDefPredPair : LastDefAddedPred)
+        if (DefP1 != LastDefPredPair.second) {
+          InsertPhi = true;
+          break;
+        }
+      if (!InsertPhi) {
+        // Since NewPhi may be used in other newly added Phis, replace all uses
+        // of NewPhi with the definition coming from all predecessors (DefP1),
+        // before deleting it.
+        NewPhi->replaceAllUsesWith(DefP1);
+        removeMemoryAccess(NewPhi);
+        continue;
+      }
+
+      // Update Phi with new values for new predecessors and old value for all
+      // other predecessors. Since AddedBlockSet and PrevBlockSet are ordered
+      // sets, the order of entries in NewPhi is deterministic.
+      for (auto *Pred : AddedBlockSet) {
+        auto *LastDefForPred = LastDefAddedPred[Pred];
+        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
+          NewPhi->addIncoming(LastDefForPred, Pred);
+      }
+      for (auto *Pred : PrevBlockSet)
+        for (int I = 0, E = EdgeCountMap[{Pred, BB}]; I < E; ++I)
+          NewPhi->addIncoming(DefP1, Pred);
+
+      // Insert BB in the set of blocks that now have definition. We'll use this
+      // to compute IDF and add Phis there next.
+      BlocksToProcess.push_back(BB);
+    }
+
+    // Get all blocks that used to dominate BB and no longer do after adding
+    // AddedBlockSet, where PrevBlockSet are the previously known predecessors.
+    assert(DT.getNode(BB)->getIDom() && "BB does not have valid idom");
+    BasicBlock *PrevIDom = FindNearestCommonDominator(PrevBlockSet);
+    assert(PrevIDom && "Previous IDom should exists");
+    BasicBlock *NewIDom = DT.getNode(BB)->getIDom()->getBlock();
+    assert(NewIDom && "BB should have a new valid idom");
+    assert(DT.dominates(NewIDom, PrevIDom) &&
+           "New idom should dominate old idom");
+    GetNoLongerDomBlocks(PrevIDom, NewIDom, BlocksWithDefsToReplace);
+  }
+
+  // Compute IDF and add Phis in all IDF blocks that do not have one.
+  SmallVector<BasicBlock *, 32> IDFBlocks;
+  if (!BlocksToProcess.empty()) {
+    ForwardIDFCalculator IDFs(DT);
+    SmallPtrSet<BasicBlock *, 16> DefiningBlocks(BlocksToProcess.begin(),
+                                                 BlocksToProcess.end());
+    IDFs.setDefiningBlocks(DefiningBlocks);
+    IDFs.calculate(IDFBlocks);
+    for (auto *BBIDF : IDFBlocks) {
+      if (auto *IDFPhi = MSSA->getMemoryAccess(BBIDF)) {
+        // Update existing Phi.
+        // FIXME: some updates may be redundant, try to optimize and skip some.
+        for (unsigned I = 0, E = IDFPhi->getNumIncomingValues(); I < E; ++I)
+          IDFPhi->setIncomingValue(I, GetLastDef(IDFPhi->getIncomingBlock(I)));
+      } else {
+        IDFPhi = MSSA->createMemoryPhi(BBIDF);
+        for (auto &Pair : children<GraphDiffInvBBPair>({GD, BBIDF})) {
+          BasicBlock *Pi = Pair.second;
+          IDFPhi->addIncoming(GetLastDef(Pi), Pi);
+        }
+      }
+    }
+  }
+
+  // Now for all defs in BlocksWithDefsToReplace, if there are uses they no
+  // longer dominate, replace those with the closest dominating def.
+  // This will also update optimized accesses, as they're also uses.
+  for (auto *BlockWithDefsToReplace : BlocksWithDefsToReplace) {
+    if (auto DefsList = MSSA->getWritableBlockDefs(BlockWithDefsToReplace)) {
+      for (auto &DefToReplaceUses : *DefsList) {
+        BasicBlock *DominatingBlock = DefToReplaceUses.getBlock();
+        Value::use_iterator UI = DefToReplaceUses.use_begin(),
+                            E = DefToReplaceUses.use_end();
+        for (; UI != E;) {
+          Use &U = *UI;
+          ++UI;
+          MemoryAccess *Usr = dyn_cast<MemoryAccess>(U.getUser());
+          if (MemoryPhi *UsrPhi = dyn_cast<MemoryPhi>(Usr)) {
+            BasicBlock *DominatedBlock = UsrPhi->getIncomingBlock(U);
+            if (!DT.dominates(DominatingBlock, DominatedBlock))
+              U.set(GetLastDef(DominatedBlock));
+          } else {
+            BasicBlock *DominatedBlock = Usr->getBlock();
+            if (!DT.dominates(DominatingBlock, DominatedBlock)) {
+              if (auto *DomBlPhi = MSSA->getMemoryAccess(DominatedBlock))
+                U.set(DomBlPhi);
+              else {
+                auto *IDom = DT.getNode(DominatedBlock)->getIDom();
+                assert(IDom && "Block must have a valid IDom.");
+                U.set(GetLastDef(IDom->getBlock()));
+              }
+              cast<MemoryUseOrDef>(Usr)->resetOptimized();
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
 // Move What before Where in the MemorySSA IR.
 template <class WhereType>
 void MemorySSAUpdater::moveTo(MemoryUseOrDef *What, BasicBlock *BB,
                               WhereType Where) {
   // Mark MemoryPhi users of What not to be optimized.
   for (auto *U : What->users())
     if (MemoryPhi *PhiUser = dyn_cast<MemoryPhi>(U))
       NonOptPhis.insert(PhiUser);

llvm/trunk/unittests/Analysis/MemorySSATest.cpp

TEST_F(MemorySSATest, TestOptimizedDefsAreProperUses) {
 
   // StoreAAccess should be present twice, since it uses liveOnEntry for both
   // its defining and optimized accesses. This is a bit awkward, and is not
   // relied upon anywhere at the moment. If this is painful, we can fix it.
   EXPECT_EQ(SortedUserList(cast<MemoryDef>(MSSA.getLiveOnEntryDef())),
             (std::vector<const MemoryDef *>{StoreAAccess, StoreAAccess,
                                             StoreBAccess}));
 }
+
+//   entry
+//     |
+//   header
+//    / \
+// body  |
+//    \ /
+//    exit
+// header:
+//  ; 1 = MemoryDef(liveOnEntry)
+// body:
+//  ; 2 = MemoryDef(1)
+// exit:
+//  ; 3 = MemoryPhi({body, 2}, {header, 1})
+//  ; 4 = MemoryDef(3); optimized to 3, cannot optimize thorugh phi.
+//  Insert edge: entry -> exit, check mssa Update is correct.
+TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiNotOpt) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  Argument *PointerArg = &*F->arg_begin();
+  BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
+  BasicBlock *Header(BasicBlock::Create(C, "header", F));
+  BasicBlock *Body(BasicBlock::Create(C, "body", F));
+  BasicBlock *Exit(BasicBlock::Create(C, "exit", F));
+  B.SetInsertPoint(Entry);
+  BranchInst::Create(Header, Entry);
+  B.SetInsertPoint(Header);
+  B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Exit, Body);
+  B.SetInsertPoint(Body);
+  B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(Exit, Body);
+  B.SetInsertPoint(Exit);
+  StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+  std::unique_ptr<MemorySSAUpdater> MSSAU =
+      make_unique<MemorySSAUpdater>(&MSSA);
+
+  MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);
+  EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));
+
+  // Alter CFG, add edge: entry -> exit
+  Entry->getTerminator()->eraseFromParent();
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Header, Exit);
+  SmallVector<CFGUpdate, 1> Updates;
+  Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});
+  Analyses->DT.applyUpdates(Updates);
+  MSSAU->applyInsertUpdates(Updates, Analyses->DT);
+  EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S1));
+}
+
+//   entry
+//     |
+//   header
+//    / \
+// body  |
+//    \ /
+//    exit
+// header:
+//  ; 1 = MemoryDef(liveOnEntry)
+// body:
+//  ; 2 = MemoryDef(1)
+// exit:
+//  ; 3 = MemoryPhi({body, 2}, {header, 1})
+//  ; 4 = MemoryDef(3); optimize this to 1 now, added edge should invalidate
+//  the optimized access.
+//  Insert edge: entry -> exit, check mssa Update is correct.
+TEST_F(MemorySSATest, TestAddedEdgeToBlockWithPhiOpt) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  Argument *PointerArg = &*F->arg_begin();
+  Type *Int8 = Type::getInt8Ty(C);
+  BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
+  BasicBlock *Header(BasicBlock::Create(C, "header", F));
+  BasicBlock *Body(BasicBlock::Create(C, "body", F));
+  BasicBlock *Exit(BasicBlock::Create(C, "exit", F));
+
+  B.SetInsertPoint(Entry);
+  Value *Alloca = B.CreateAlloca(Int8, ConstantInt::get(Int8, 1), "A");
+  BranchInst::Create(Header, Entry);
+
+  B.SetInsertPoint(Header);
+  StoreInst *S1 = B.CreateStore(B.getInt8(16), PointerArg);
+  B.CreateCondBr(B.getTrue(), Exit, Body);
+
+  B.SetInsertPoint(Body);
+  B.CreateStore(ConstantInt::get(Int8, 0), Alloca);
+  BranchInst::Create(Exit, Body);
+
+  B.SetInsertPoint(Exit);
+  StoreInst *S2 = B.CreateStore(B.getInt8(16), PointerArg);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  MemorySSAWalker *Walker = Analyses->Walker;
+  std::unique_ptr<MemorySSAUpdater> MSSAU =
+      make_unique<MemorySSAUpdater>(&MSSA);
+
+  MemoryDef *DefS1 = cast<MemoryDef>(MSSA.getMemoryAccess(S1));
+  EXPECT_EQ(DefS1, Walker->getClobberingMemoryAccess(S2));
+
+  // Alter CFG, add edge: entry -> exit
+  Entry->getTerminator()->eraseFromParent();
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), Header, Exit);
+  SmallVector<CFGUpdate, 1> Updates;
+  Updates.push_back({cfg::UpdateKind::Insert, Entry, Exit});
+  Analyses->DT.applyUpdates(Updates);
+  MSSAU->applyInsertUpdates(Updates, Analyses->DT);
+
+  MemoryPhi *Phi = MSSA.getMemoryAccess(Exit);
+  EXPECT_EQ(Phi, Walker->getClobberingMemoryAccess(S2));
+}
+
+//   entry
+//    /  |
+//   a   |
+//  / \  |
+//  b c  f
+//  \ /  |
+//   d   |
+//    \ /
+//     e
+// f:
+//  ; 1 = MemoryDef(liveOnEntry)
+// e:
+//  ; 2 = MemoryPhi({d, liveOnEntry}, {f, 1})
+//
+// Insert edge: f -> c, check update is correct.
+// After update:
+// f:
+//  ; 1 = MemoryDef(liveOnEntry)
+// c:
+//  ; 3 = MemoryPhi({a, liveOnEntry}, {f, 1})
+// d:
+//  ; 4 = MemoryPhi({b, liveOnEntry}, {c, 3})
+// e:
+//  ; 2 = MemoryPhi({d, 4}, {f, 1})
+TEST_F(MemorySSATest, TestAddedEdgeToBlockWithNoPhiAddNewPhis) {
+  F = Function::Create(
+      FunctionType::get(B.getVoidTy(), {B.getInt8PtrTy()}, false),
+      GlobalValue::ExternalLinkage, "F", &M);
+  Argument *PointerArg = &*F->arg_begin();
+  BasicBlock *Entry(BasicBlock::Create(C, "entry", F));
+  BasicBlock *ABlock(BasicBlock::Create(C, "a", F));
+  BasicBlock *BBlock(BasicBlock::Create(C, "b", F));
+  BasicBlock *CBlock(BasicBlock::Create(C, "c", F));
+  BasicBlock *DBlock(BasicBlock::Create(C, "d", F));
+  BasicBlock *EBlock(BasicBlock::Create(C, "e", F));
+  BasicBlock *FBlock(BasicBlock::Create(C, "f", F));
+
+  B.SetInsertPoint(Entry);
+  B.CreateCondBr(B.getTrue(), ABlock, FBlock);
+  B.SetInsertPoint(ABlock);
+  B.CreateCondBr(B.getTrue(), BBlock, CBlock);
+  B.SetInsertPoint(BBlock);
+  BranchInst::Create(DBlock, BBlock);
+  B.SetInsertPoint(CBlock);
+  BranchInst::Create(DBlock, CBlock);
+  B.SetInsertPoint(DBlock);
+  BranchInst::Create(EBlock, DBlock);
+  B.SetInsertPoint(FBlock);
+  B.CreateStore(B.getInt8(16), PointerArg);
+  BranchInst::Create(EBlock, FBlock);
+
+  setupAnalyses();
+  MemorySSA &MSSA = *Analyses->MSSA;
+  std::unique_ptr<MemorySSAUpdater> MSSAU =
+      make_unique<MemorySSAUpdater>(&MSSA);
+
+  // Alter CFG, add edge: f -> c
+  FBlock->getTerminator()->eraseFromParent();
+  B.SetInsertPoint(FBlock);
+  B.CreateCondBr(B.getTrue(), CBlock, EBlock);
+  SmallVector<CFGUpdate, 1> Updates;
+  Updates.push_back({cfg::UpdateKind::Insert, FBlock, CBlock});
+  Analyses->DT.applyUpdates(Updates);
+  MSSAU->applyInsertUpdates(Updates, Analyses->DT);
+
+  MemoryPhi *MPC = MSSA.getMemoryAccess(CBlock);
+  EXPECT_NE(MPC, nullptr);
+  MemoryPhi *MPD = MSSA.getMemoryAccess(DBlock);
+  EXPECT_NE(MPD, nullptr);
+  MemoryPhi *MPE = MSSA.getMemoryAccess(EBlock);
+  EXPECT_EQ(MPD, MPE->getIncomingValueForBlock(DBlock));
+}