[llvm][fix-irreducible] ensure that loop subtree under child is correctly reconnected to new loop

[sunziping2016]

Summary

The modified function was incorrectly (not unnecessarily) ignoring grandchild loops, and this change fixes the bug. In particular, this fixes the handling of the loop { inner, body }. The TODO in the same function is talking about the b1 self loop, which may be "unnecessarily" lost, but that is a different issue.

[sameerds]

I think the change description is missing the point and needs to be rephrased. The modified function was incorrectly (not unnecessarily) ignoring grandchild loops, and this change fixes the bug. In particular, this fixes the handling of the loop { inner, body }. The TODO in the same function is talking about the b1 self loop, which may be "unnecessarily" lost, but that is a different issue.

A possible wording would be: "ensure that loop subtree under child is correctly reconnected to new loop"

[sunziping2016]

In D125522#3521143, @sameerds wrote:

I think the change description is missing the point and needs to be rephrased. The modified function was incorrectly (not unnecessarily) ignoring grandchild loops, and this change fixes the bug. In particular, this fixes the handling of the loop { inner, body }. The TODO in the same function is talking about the b1 self loop, which may be "unnecessarily" lost, but that is a different issue.

A possible wording would be: "ensure that loop subtree under child is correctly reconnected to new loop"

Sorry, I'm new here, so I know little about the workflows. I've just updated the title and the summary of this revision. I don't know whether you mean this. And I've noticed there is a build failure on x64 debian. Should I fix this?

[sameerds]

In D125522#3521160, @sunziping2016 wrote:

Sorry, I'm new here, so I know little about the workflows. I've just updated the title and the summary of this revision. I don't know whether you mean this. And I've noticed there is a build failure on x64 debian. Should I fix this?

It is not enough to edit this revision in Phabricator (i.e., this web interface). You will need to amend the git commit in your worktree, because that's the one you will actually submit.

About the failure, I am not confident enough to say that you can ignore it. It is better if you ask on discourse.

[sunziping2016]

update commit message

[sameerds]

Sorry I missed this earlier. The name of the new test "issue55099.ll" doesn't really convey much information. It should be renamed to something more informative, like "preserve-child-loops.ll"

You don't have to upload a new patch here if you rename that file. Just make sure you rename it in your git commit before you do a "git push" to main branch.

[sunziping2016]

Thanks for your patient and professional review. I think the x64 debian failure is related to my changes. I need to spend some time to fix the issue.

[sunziping2016]

rename test file to a meaningful name

[sunziping2016]

Merged by commit https://github.com/llvm/llvm-project/commit/242961f23b4abaca999611fd364e93a8d2186371

llvm/lib/Transforms/Utils/FixIrreducible.cpp

static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
   for (Loop *Child : ChildLoops) {
     LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
                       << "\n");
     // TODO: A child loop whose header is also a header in the current
     // SCC gets destroyed since its backedges are removed. That may
     // not be necessary if we can retain such backedges.
     if (Headers.count(Child->getHeader())) {
       for (auto BB : Child->blocks()) {
+        if (LI.getLoopFor(BB) != Child)
+          continue;
         LI.changeLoopFor(BB, NewLoop);
         LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
                           << "\n");
       }
+      std::vector<Loop *> GrandChildLoops;
+      std::swap(GrandChildLoops, Child->getSubLoopsVector());
+      for (auto GrandChildLoop : GrandChildLoops) {
+        GrandChildLoop->setParentLoop(nullptr);
+        NewLoop->addChildLoop(GrandChildLoop);
+      }
       LI.destroy(Child);
       LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
       continue;
     }
 
     Child->setParentLoop(nullptr);
     NewLoop->addChildLoop(Child);
     LLVM_DEBUG(dbgs() << "added child loop to new loop\n");

llvm/test/Transforms/FixIrreducible/preserve-child-loops.ll

+; RUN: opt %s -fix-irreducible -S -o - | FileCheck %s
+
+define dso_local void @foo(i1 %a) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label %irr.guard
+; CHECK:       block1:
+; CHECK-NEXT:    br label %irr.guard
+; CHECK:       block2:
+; CHECK-NEXT:    br label %body
+; CHECK:       body:
+; CHECK-NEXT:    br i1 %a, label %latch, label %inner_body
+; CHECK:       inner_body:
+; CHECK-NEXT:    br label %body
+; CHECK:       latch:
+; CHECK-NEXT:    br label %irr.guard
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD:%.*]] = phi i1 [ %a, %latch ], [ %a, %block1 ], [ %a, %entry ]
+; CHECK-NEXT:    br i1 [[GUARD]], label %block1, label %block2
+;
+entry:
+  br i1 %a, label %block1, label %block2
+
+block1:
+  br i1 %a, label %block1, label %block2
+
+block2:
+  br label %body
+
+body:
+  br i1 %a, label %latch, label %inner_body
+
+inner_body:
+  br label %body
+
+latch:
+  br i1 %a, label %block1, label %block2
+
+}