This is an archive of the discontinued LLVM Phabricator instance.

[UnrollRuntime] Fix domTree failure in multiexit unrolling
ClosedPublic

Authored by anna on Jan 3 2019, 11:53 AM.

Details

Summary

This fixes the IDom for an exit block when runtime unrolling under multiexit/exiting case.
We initially had a restrictive check that the IDom is only updated when
it is the header of the loop.
However, we also need to update the IDom to the correct one when the
IDom is any block within the original loop. See added test case (which
fails dom tree verification without the patch).

Diff Detail

Repository
rL LLVM

Event Timeline

anna created this revision.Jan 3 2019, 11:53 AM
anna added a comment.Jan 3 2019, 11:53 AM

Context and history for runtime unrolling: https://reviews.llvm.org/D35304

LGTM. @kuhar may wish to comment.

kuhar added a comment.Jan 3 2019, 3:00 PM

@anna Can this be rewritten to use the DomTreeUpdater utility? We have large number of examples in the codebase already, so the question is whether this affects the performance in this case. Historically, we had tons of bugs in manual DomTree updates and I'd rather we replaces as much as possible using the incremental updater.

anna added a comment.Jan 3 2019, 3:14 PM

@anna Can this be rewritten to use the DomTreeUpdater utility?

@kuhar, I have not looked at the DTU uttility yet, but I'd think it can be rewritten (unless there are some limitations for the DomTreeUpdater utility). However, that would be a large enough change and I think it's better to do it as a separate change at a later point rather than as part of fixing this bug. Also, there are enough DT updates through out this code that it will take a while to get through the whole process of porting over for runtime unrolling.

kuhar added a comment.Jan 3 2019, 3:19 PM

@anna Can this be rewritten to use the DomTreeUpdater utility?

@kuhar, I have not looked at the DTU uttility yet, but I'd think it can be rewritten (unless there are some limitations for the DomTreeUpdater utility). However, that would be a large enough change and I think it's better to do it as a separate change at a later point rather than as part of fixing this bug. Also, there are enough DT updates through out this code that it will take a while to get through the whole process of porting over for runtime unrolling.

I see, thank you for the explanation. I think think there's nothing stopping it from being ported, this will be the correct long-term fix. I skimmed through the code and it shouldn't take more than a day. But as you mentioned, it can happen in a separate patch.

anna updated this revision to Diff 180269.Jan 4 2019, 10:17 AM

The IDom can be any block within the loop (as mentioned in the comment).
So, we need to check for IDom *contained* in the loop.
Added test case shows where the IDom is within the inner loop of the original loop.
Both test cases pass now with the fix.

anna planned changes to this revision.Jan 7 2019, 12:13 PM

the same bug can happen with:

  1. latch exit
  2. non-immediate successors of latchexit/otherexit.

I have simplified test cases for each of these and we need a more general fix. Working on this.

kuhar added a comment.Jan 7 2019, 12:16 PM

the same bug can happen with:

  1. latch exit
  2. non-immediate successors of latchexit/otherexit.

I have simplified test cases for each of these and we need a more general fix. Working on this.

... these things are extremely bug-prone; I really do suggest using the automatic updater instead of trying to deal with all tricky corner-cases here :)

anna added a comment.Jan 7 2019, 1:17 PM

the same bug can happen with:

  1. latch exit
  2. non-immediate successors of latchexit/otherexit.

I have simplified test cases for each of these and we need a more general fix. Working on this.

... these things are extremely bug-prone; I really do suggest using the automatic updater instead of trying to deal with all tricky corner-cases here :)

I've got a naive question about the DTU: Does the automatic updater handle the ImmediateDominator "automatically" for the remaining nodes in the dom tree once identify that one of the nodes in the DT has a change in IDom?

This will drastically help with #2 because what I have as a local fix using the old DT is something like this:

+   if (DT) {
+    // Check the dom children of each block in loop and if it is outside the
+    // current loop, update it to the preheader.
+    for (auto *BB: L->blocks()) {
+      auto *DomNodeBB = DT->getNode(BB);
+      for (auto *DomChild: DomNodeBB->getChildren()) {
+        if (!L->contains(LI->getLoopFor(DomChild->getBlock()))) {
+          DT->changeImmediateDominator(DomChild, DT->getNode(PreHeader));
+        }    
+      }    
+    }
+   }

This is a more general fix using the old DT to handle the non-immediate successors of an exit block in the loop.

kuhar added a comment.Jan 7 2019, 1:25 PM

I've got a naive question about the DTU: Does the automatic updater handle the ImmediateDominator "automatically" for the remaining nodes in the dom tree once identify that one of the nodes in the DT has a change in IDom?

Exactly. Given a set of CFG updates, if figures out how to change the DomTree and PostDomTree such that they match the CFG.

This will drastically help with #2 because what I have as a local fix using the old DT is something like this:

+   if (DT) {
+    // Check the dom children of each block in loop and if it is outside the
+    // current loop, update it to the preheader.
+    for (auto *BB: L->blocks()) {
+      auto *DomNodeBB = DT->getNode(BB);
+      for (auto *DomChild: DomNodeBB->getChildren()) {
+        if (!L->contains(LI->getLoopFor(DomChild->getBlock()))) {
+          DT->changeImmediateDominator(DomChild, DT->getNode(PreHeader));
+        }    
+      }    
+    }
+   }

This is a more general fix using the old DT to handle the non-immediate successors of an exit block in the loop.

Doesn't this loop have to be run until you reach a fixpoint?

anna added a comment.Jan 7 2019, 2:03 PM

I've got a naive question about the DTU: Does the automatic updater handle the ImmediateDominator "automatically" for the remaining nodes in the dom tree once identify that one of the nodes in the DT has a change in IDom?

Exactly. Given a set of CFG updates, if figures out how to change the DomTree and PostDomTree such that they match the CFG.

This will drastically help with #2 because what I have as a local fix using the old DT is something like this:

+   if (DT) {
+    // Check the dom children of each block in loop and if it is outside the
+    // current loop, update it to the preheader.
+    for (auto *BB: L->blocks()) {
+      auto *DomNodeBB = DT->getNode(BB);
+      for (auto *DomChild: DomNodeBB->getChildren()) {
+        if (!L->contains(LI->getLoopFor(DomChild->getBlock()))) {
+          DT->changeImmediateDominator(DomChild, DT->getNode(PreHeader));
+        }    
+      }    
+    }
+   }

This is a more general fix using the old DT to handle the non-immediate successors of an exit block in the loop.

Doesn't this loop have to be run until you reach a fixpoint?

yes, that's right - I'd missed that. Now, It's a principled fix which handles all cases of nearest common dominator of the IDoms of multiple exiting blocks, and these other cases I've seen above.

If any more DT bugs shows up in our fuzzer run, I'm just going to scrap this and go with the DTU itself instead of the other way around - landing this and then changing to DTU :)

anna updated this revision to Diff 180682.Jan 8 2019, 8:44 AM

we need to update domInfo for exits and those reachable from the exits.

anna added a comment.Jan 8 2019, 8:45 AM

This has passed all internal fuzzer runs - the DT verification failure tests have been added as test cases here after reduction.

@anna thank you for your patience and perseverance with this fix and welcome to the hairy world of manual dominator updates. :)

I too would like to see this moved to DTU in a future update but for now I feel it's sufficient that it's passed your fuzzer tests and is much better than the current state of DT verification failure.

LGTM.

anna added a comment.Jan 8 2019, 9:02 AM

thanks for reviewing the change Brian! Will land it soon.

brzycki accepted this revision.Jan 8 2019, 9:17 AM

I am accepting this revision.

This revision is now accepted and ready to land.Jan 8 2019, 9:17 AM
This revision was automatically updated to reflect the committed changes.