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.
Details
Details
Diff Detail
Diff Detail
- Repository
- rL LLVM
Event Timeline
There are a very large number of changes, so older changes are hidden. Show Older Changes
| 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. :) |
| 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). |
Comment Actions
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 1And 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.) |
Comment Actions
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 :)
Comment Actions
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. |
| 839 ↗ | (On Diff #160942) | I may be missing something, but if I do: |
| 852 ↗ | (On Diff #160942) | This should be fixed. Added testcase as well. |
Comment Actions
Thank you for the patience on this review! :)
I'm doing some additional offline testing before landing (+ the nits you noticed).
Comment Actions
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.