This is an archive of the discontinued LLVM Phabricator instance.

[Dominators] Teach LoopDeletion to use the new incremental API
ClosedPublic

Authored by kuhar on Jul 13 2017, 4:24 PM.

Details

Summary

This patch makes LoopDeletion use the incremental DominatorTree API.

We modify LoopDeletion to perform the deletion in 5 steps:

  1. Create a new dummy edge from the preheader to the exit, by adding a conditional branch.
  2. Inform the DomTree about the new edge.
  3. Remove the conditional branch and replace it with an unconditional edge to the exit. This removes the edge to the loop header, making it unreachable.
  4. Inform the DomTree about the deleted edge.
  5. Remove the unreachable block from the function.

Creating the dummy conditional branch is necessary to perform incremental DomTree update.
We should consider using the batch updater when it's ready.

Diff Detail

Event Timeline

kuhar created this revision.Jul 13 2017, 4:24 PM
kuhar updated this revision to Diff 106553.Jul 13 2017, 4:34 PM

Add a comment explaining the special logic here.

kuhar updated this revision to Diff 106555.Jul 13 2017, 4:42 PM

Make the edited for loop more concise.

grosser requested changes to this revision.Jul 14 2017, 12:26 AM

Nice work! This mostly looks good to me, but I have some minor question. I mark this as request changes to be notified by Phabricator in case you reply. It seems some of the email notifications don't really work at the moment.

lib/Transforms/Scalar/LoopDeletion.cpp
303

preheader

308

I think it would be great to document this behavior in deleteEdge() and reference this behavior there! Also, do we happen to have a test case that documents this bulk removal of nodes in DT. I think this is an interesting, but not totally expected use of the deleteEdge API and it would be great if this has good test coverage.

Thanks again for working on this,

This revision now requires changes to proceed.Jul 14 2017, 12:26 AM
kuhar updated this revision to Diff 108368.Jul 26 2017, 3:16 PM
kuhar edited edge metadata.
kuhar marked an inline comment as done.

I think that I came up better guidelines on chaining updates. I included explanations for that in the comments and I added two new unittests illustrating them.

I misunderstood how LoopDeletion changes CFG and the previous explanation was incorrect because of that. Please tell me if this one is clear enough.

kuhar updated this revision to Diff 108541.Jul 27 2017, 4:23 PM
kuhar edited the summary of this revision. (Show Details)

Zhendong and Qirun were able to generate a CFG that broke the previous update chained logic. It turns out, that it's not legal to chain a deletion and an insertion when there's irreducible control flow that appears in the temporarily deleted subtree. I added a regression test for that.

I think that this shows that the current incremental API is tricky to use when CFG and DomTree updates are not performed in lockstep, and we *really* need a proper batch update API.

kuhar added a comment.Aug 2 2017, 8:42 AM

@grosser, @dberlin, @davide

Ping.
(This patch doesn't depend on the postdominator changes in review or on the batch updater.)

dberlin accepted this revision.Aug 2 2017, 9:34 AM

This looks fine to me.
I think it may make sense to try to add a few simple cfg drawings to show what machinations are really happening here, but if others undersrtand them just from the text descriptions, awesome.

grosser accepted this revision.Aug 2 2017, 9:44 AM

Hi @kuhar,

thank you for updating the comment. I found a couple of minor typos. The code likely looks good, but I don't see any reference to the irreducible control flow issues you mentioned. I assume you are now connecting the loop header to its exit to avoid the PDT update issue before. It might make sense to briefly explain why first deleting and then adding a new edge will break.

In any case, these are at most minor issues. Feel free to commit.

Best,
Tobias

include/llvm/Support/GenericDomTree.h
492

That looks good to me.

lib/Transforms/Scalar/LoopDeletion.cpp
248

THE dominator tree update

260

Could you maybe move the " DT.insertEdge(Preheader, ExitBlock);" this makes clear that the DT update comes right after the CFG change. Now it is hidden after the PHI update.

297

dominator

unittests/IR/DominatorTreeTest.cpp
538

Remove "a"

539

Remove "the"
Remove "of them"

This revision is now accepted and ready to land.Aug 2 2017, 9:44 AM
kuhar updated this revision to Diff 109377.Aug 2 2017, 10:39 AM

Address Daniel's and Tobias' comments.

kuhar marked 5 inline comments as done.Aug 2 2017, 10:40 AM

Amazing. Now this reads really nice.

unittests/IR/DominatorTreeTest.cpp
538

Still an "a" too much.

This revision was automatically updated to reflect the committed changes.