This is an archive of the discontinued LLVM Phabricator instance.

[LoopSimplifyCFG] Use DTU.applyUpdates instead of insert/deleteEdge
ClosedPublic

Authored by mkazantsev on Jan 28 2019, 1:03 AM.

Details

Summary

insert/deleteEdge methods in DTU can make updates incorrectly in some cases
(see https://bugs.llvm.org/show_bug.cgi?id=40528), and it is recommended to
use applyUpdates methods instead when it is needed to make a mass update in CFG.

Diff Detail

Event Timeline

mkazantsev created this revision.Jan 28 2019, 1:03 AM

I think the underlying problem is a bug of DTU, but am not 100% sure. In the given test, eager strategy does the following:

  1. Removes dead edge bb4->bb18;
  2. Tries to remove edge bb18->bb6, but the actual deletion does not happen because bb18 does not have a DT node;
  3. As result, after these two operations the IDOM of bb6 is bb3, while it should be bb29 after we have removed edge bb18->bb6.

To me it seems that at some point we screwed up making the probper updates for bb6. I think we should've done it when removed bb4->bb18. However the comments in DTU about that are fuzzy. They say that:

/// Notify all available trees on an edge deletion. If both DT and PDT are
/// nullptrs, this function discards the update. Under either Strategy,
/// self-dominance update will be removed. The Eager Strategy applies
/// the update immediately while the Lazy Strategy queues the update.
/// It is recommended to only use this method when you have exactly one
/// deletion (and no insertions). It is recommended to use applyUpdates() in
/// all other cases. This function has to be called *after* making the update
/// on the actual CFG. An internal functions checks if the edge doesn't exist
/// in the CFG in DEBUG mode.
void deleteEdge(BasicBlock *From, BasicBlock *To);

I do not know what this recommendation is about. Does anybody know whether DTU should be able to work correctly with eager strategy?

Maybe @kuhar knows what should be the correct behavior of eager DTU updates here? I think it's a bug in DTU, but the comments are uncertain enough to give me doubts about that. :)

mkazantsev retitled this revision from [LoopSimplifyCFG] Fix DT update strategy to [LoopSimplifyCFG] Use lazy DT update strategy: bug with eager one?.Jan 28 2019, 3:25 AM
mkazantsev edited the summary of this revision. (Show Details)
asbirlea added inline comments.Jan 28 2019, 10:26 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
325

I have not looked at this in detail, but I've had a similar issue at one point in SimpleLoopUnswitch with DomTree. AFAICT, this applies for DTU as well.
Calling deleteEdge and insertEdge one after the other will not do the updates properly.
The correct way to do it is:

SmallVector<DominatorTree::UpdateType, 3> DTUpdates;
DTUpdates.push_back({DT.Insert, NewPreheader, L.getHeader()});
DTUpdates.push_back({DT.Insert, Preheader, NewPreheader});
DTUpdates.push_back({DT.Delete, Preheader, L.getHeader()});
DTU.applyUpdates(DTUpdates);

Perhaps the behavior is different with the Eager strategy, but I'm fairly confident using applyUpdates is correct for DT.

mkazantsev marked an inline comment as done.Jan 30 2019, 12:07 AM
mkazantsev added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
325

With lazy strategy, flush() is doing exactly this thing, calling applyUpdates inside.

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

mkazantsev retitled this revision from [LoopSimplifyCFG] Use lazy DT update strategy: bug with eager one? to [LoopSimplifyCFG] Work around bug in DTU by using lazy strategy.Jan 30 2019, 6:10 AM
mkazantsev edited the summary of this revision. (Show Details)
kuhar added a comment.Jan 30 2019, 7:56 AM

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

You should use DTU.applyUpdates after a transformation that affects multiple CFG edges to inform DomTree about all of the things that changed since the last time it was updated. Eager strategy means that at each update point the updates are performed immediately, while the lazy update strategy is free to schedule them at any 'update' (synchronization) point between the first one and flush (possibly multiple time).
Perhaps we should improve the the documentation. @mkazantsev: do you have some suggestions?

kuhar added a comment.Jan 30 2019, 7:58 AM

@NutshellySima What was the reason we introduced DTU.insertEdge and DTU.deleteEdge? While they are essential primitives in the incremental updater, couldn't we get rid of it entirely? My memory is blurry.

It is indeed a bug in DTU, I was able to construct a unit test to reproduce it. https://bugs.llvm.org/show_bug.cgi?id=40528

You should use DTU.applyUpdates after a transformation that affects multiple CFG edges to inform DomTree about all of the things that changed since the last time it was updated. Eager strategy means that at each update point the updates are performed immediately, while the lazy update strategy is free to schedule them at any 'update' (synchronization) point between the first one and flush (possibly multiple time).
Perhaps we should improve the the documentation. @mkazantsev: do you have some suggestions?

When I read the documentation, I interpreted

It is recommended to only use this method when you have exactly one deletion (and no insertions). It is recommended to use applyUpdates() in all other cases.

as a profitability reasoning, not correctness reasoning. If we intentionally do not guarantee equivalence of Eager strategy and Lazy strategy (which is the same as applyUpdates), we should clearly state that "It is only legal to use this method when you have exactly one deletion...".
So if you think that the observed behavior is not a bug, I propose making this change. Otherwise, the bug should be fixed.

I've run some extensive Fuzz testing on my side for three 72 hours, it seems this one along with other fixes on review cover all bugs we had.

@NutshellySima What was the reason we introduced DTU.insertEdge and DTU.deleteEdge? While they are essential primitives in the incremental updater, couldn't we get rid of it entirely? My memory is blurry.

Under Eager update strategy, they act as an alias of DTU.applyUpdates. And under Lazy update strategy, they'll assert when insertEdge() is inserting a nonexistent edge / deleteEdge() is deleting an edge that still exists to detect possible misuses.

Anyway, it is OK to get rid of insertEdge/deleteEdge entirely if we remove the check I mentioned. (I didn't implement a similar check in DTU.applyUpdates under Lazy strategy because it is still an open debate whether trying "inserting a nonexistent edge/deleting an edge that still exists" is a good approach.)

So, is it OK to go with this fix here?

kuhar requested changes to this revision.EditedFeb 5 2019, 6:57 AM

So, is it OK to go with this fix here?

You should replace insert/deleteEdge with applyUpdates -- I'd argue that even though it works with how the lazy strategy is implemented now, it is semantically incorrect because the DomTree updates you schedule don't match the CFG at the point of updates.
Then, it would be interesting to see whether:

  1. Eager strategy works (it should)
  2. How fast is eager vs lazy
This revision now requires changes to proceed.Feb 5 2019, 6:57 AM
mkazantsev retitled this revision from [LoopSimplifyCFG] Work around bug in DTU by using lazy strategy to [LoopSimplifyCFG] Use DT.update instead of DTU.
mkazantsev edited the summary of this revision. (Show Details)

I've given up using DTU, now the updates are applied directly.

kuhar added a comment.Feb 6 2019, 11:43 AM

I've given up using DTU, now the updates are applied directly.

Max, why don't you use DTU with .applyUpdates? Are you facing some difficulties, or found documentation confusing somewhere else?
I don't have much time recently, but I can definitely find enough to fix some issues people have with updating dominators. If you think something is not obvious or too difficult, there are probably multiple people who faced the same problems but never bother to share their experience.

kuhar added a comment.Feb 6 2019, 11:45 AM

I've given up using DTU, now the updates are applied directly.

Max, why don't you use DTU with .applyUpdates? Are you facing some difficulties, or found documentation confusing somewhere else?
I don't have much time recently, but I can definitely find enough to fix some issues people have with updating dominators. If you think something is not obvious or too difficult, there are probably multiple people who faced the same problems but never bother to share their experience.

The goal of DTU is take away as much low-level burden when updating dominators as possible. Ideally, nobody should have to use the raw updater in DomTree anymore, and the DTU api should enable us to cheaply update PostDominators without modifying the update logic.
That's why I'm opposed to using raw updates, unless absolutely necessary.

Actually I am just confused by the number of different ways to do the same thing, all having different bugs inside. If using DTU.applyUpdates is the right day now, I'm ok with that.

mkazantsev retitled this revision from [LoopSimplifyCFG] Use DT.update instead of DTU to [LoopSimplifyCFG] Use DTU.applyUpdates instead of insert/deleteEdge.
mkazantsev edited the summary of this revision. (Show Details)
kuhar accepted this revision.Feb 7 2019, 7:44 AM

LGTM

This revision is now accepted and ready to land.Feb 7 2019, 7:44 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptFeb 8 2019, 12:13 AM