[SimplifyCFG][TranformUtils]Do not simplify away a trivial basic block if both this block and at least one of its predecessors are loop latches.

[mingmingl]

Summary

Before this patch, loop metadata (if exists) will override the metadata of each predecessor; if the predecessor block already has loop metadata, the orignal loop metadata won't be preserved abd cause missed loop transformations (see 'test2' in llvm/test/Transforms/SimplifyCFG/preserve-llvm-loop-metadata.ll).

To illustrate how inner-loop metadata might be dropped:

CFG Before

  
# BB is while.cond.exit, attached with loop metdata md2.
# BB->Pred is for.body, attached with loop metadata md1.
        entry
          |
          v
   ---> while.cond   ------------->  while.end
   |       |
   |       v
   |   while.body
   |       |
   |       v
   |    for.body <---- (md1)
   |       |  |______|
   |       v
   |    while.cond.exit (md2)
   |       |
   |_______|

CFG After

 
# while.cond1 is the merge of while.cond.exit and while.cond above.
# for.body is attached with md2, and md1 is dropped.
# If LoopSimplify runs later (as a part of loop pass), it could create
# dedicated exits for inner-loop (essentially adding `while.cond.exit` basck),
# but won't it won't see 'md1' nor restore it for the inner-loop.

        entry
          |
          v
  ---> while.cond1  ------------->  while.end
  |       |
  |       v
  |   while.body
  |       |
  |       v
  |    for.body <---- (md2)
  |_______|  |______|

[davidxl]

It would be clearer to describe the problem with example CFGs before and after (probably using ascii art) and explain how the meta data is lost during this transformation.

[mingmingl]

address comments.

[mingmingl]

In D134152#3798689, @davidxl wrote:

It would be clearer to describe the problem with example CFGs before and after (probably using ascii art) and explain how the meta data is lost during this transformation.

Done.

[mingmingl]

Add efriedma@ who has context on two related patch (https://reviews.llvm.org/D42691 and https://reviews.llvm.org/D35411)

p.s. 'test1' CHECK statements in 'preserve-llvm-loop-metadata.ll' is inadvertently removed. add them back.

[davidxl]

Thanks for the nice graph. It looks like after the simplification, for.cond is used as latch for both the inner and outer loop, but only one MD data is allowed. In this case, I think we should disable the block merge.

[nikic]

The current representation of loop metadata (using a loop latch terminator attachment) is known to be fundamentally broken. Loop latches are not uniquely associated with loops (both in that a latch can be part of multiple loops and a loop may have multiple latches). Loop headers are. The solution to this problem is also known: Add support for basic block metadata, and attach loop metadata to the loop header.

I don't think adding these kinds of hacks is going to scale much further -- someone needs to actually address the root problem.

[davidxl]

Re nikic's comment -- I agree with the statement in general, but I think the infrastructure fix is orthogonal to the bug fix (with the status quo). For what you suggested, we should probably file a bug to track it.

[davidxl]

llvm/include/llvm/Transforms/Utils/Local.h

160 ↗

(On Diff #462213)

This fixme seems out of context. Is it needed?

llvm/lib/Transforms/Utils/Local.cpp

1147

There is no need to document option 1 and option 2 here.

[mingmingl]

address comments.

[mingmingl]

llvm/include/llvm/Transforms/Utils/Local.h

160 ↗

(On Diff #462213)

It's verbose for a fix, but related with test coverage

1. When called by 'JumpThreading', loop latches are not attempted by TryToSimplifyUncondBranchFromEmptyBlock (code and comment)
2. When called by 'SimplifyCFG', loop latches with more than two predecessors are not attempted by TryToSimplifyUncondBranchFromEmptyBlock (code and patch)

As a result of 1) and 2), test cases are possible for SimplifyCFG but not straightforward (if makes sense at all) for JumpThreading -> what that means is shown in the relevant test case (test2), empty block BB has one predecessor, but it shouldn't be optimized away (for inner-loop metadata).

Removed this comment.

[davidxl]

Jumpthreading 'avoids' the problem with an earlier guard. Since the fix is in a common path, it is ok to just test simplifyCFG.

[davidxl]

Perhaps add a TODO in the comment part for the longer term solution suggested by nikic. Otherwise LGTM

[nikic]

It's fine to work around this in the meantime (it is a correctness problem when it comes to mustprogress at least) -- but shouldn't this be done by dropping the loop metadata? I believe that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

[mingmingl]

address comments.

[mingmingl]

In D134152#3819747, @davidxl wrote:

Perhaps add a TODO in the comment part for the longer term solution suggested by nikic. Otherwise LGTM

Thanks. Added a FIXME and quoted nikic's comment there.

In D134152#3809106, @nikic wrote:

The current representation of loop metadata (using a loop latch terminator attachment) is known to be fundamentally broken. Loop latches are not uniquely associated with loops (both in that a latch can be part of multiple loops and a loop may have multiple latches). Loop headers are. The solution to this problem is also known: Add support for basic block metadata, and attach loop metadata to the loop header.

I don't think adding these kinds of hacks is going to scale much further -- someone needs to actually address the root problem.

Thanks for the input! It makes sense to me that current representation won't scale well (from the history around this line, to first count for loop headers, then loop latches, then about the number of predecessors).

I didn't reply though, after davidxl@ beat me to it (that fixing loop metadata representation is a long shot to preserve the inner-loop metadata).

For efficiency considerations,

1. Regarding the scope, this patch only makes a difference when 'BB' has only one predecessor, in the sense that ToT won't simplify it away when 'BB' has more than two predecessors (as a loop latch)
2. branch-folder in the codegen pipeline is likely forward branches to unconditional branches to destination directly if this trivial block presents by then.
3. I did a loadtest on one representative internal benchmark and didn't see regressions.

[mingmingl]

In D134152#3820125, @nikic wrote:

It's fine to work around this in the meantime (it is a correctness problem when it comes to mustprogress at least) -- but shouldn't this be done by dropping the loop metadata? I believe that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

(Oh we sent out the comment around the same time and I quoted the previous comment :))

that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

Got it. This would make sense to me.

I once thought hard about how to 'concat' loop metadata correctly when drafting something, but that effort ended up nowhere.

TBH I haven't thought through what it would take (maybe clang and llvm IR first, while keeping IR compatibility for frontends of other languages) to implement header-based loop metadata. However, I concur that

1. in C++ code a loop could easily have many latches, compared with headers
2. Even when inner loop and outer loop have the same IR header [1], the inner-loop and outer-loop have headers (in c++ form) respectively.

[1]

This example from https://llvm.org/docs/LoopTerminology.html#important-notes

for (int i = 0; i < 128; ++i)
  for (int j = 0; j < 128; ++j)
    body(i,j);

[davidxl]

In D134152#3820125, @nikic wrote:

It's fine to work around this in the meantime (it is a correctness problem when it comes to mustprogress at least) -- but shouldn't this be done by dropping the loop metadata? I believe that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

Dropping the metadata in this case changes the program semantics (unlike dropping profile data), thus the transformation in this case is unsafe so it should be disabled as this patch does.

[fhahn]

In D134152#3821142, @davidxl wrote:

In D134152#3820125, @nikic wrote:

It's fine to work around this in the meantime (it is a correctness problem when it comes to mustprogress at least) -- but shouldn't this be done by dropping the loop metadata? I believe that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

Dropping the metadata in this case changes the program semantics (unlike dropping profile data), thus the transformation in this case is unsafe so it should be disabled as this patch does.

I think I am missing what the issue with dropping the loop metadata would be, could you elaborate? If we drop the metadata we should only lose information that may have enabled additional transformations, but shouldn't change the result of the program.

[davidxl]

In D134152#3821184, @fhahn wrote:

In D134152#3821142, @davidxl wrote:

In D134152#3820125, @nikic wrote:

It's fine to work around this in the meantime (it is a correctness problem when it comes to mustprogress at least) -- but shouldn't this be done by dropping the loop metadata? I believe that's the general rule for metadata: If a transform cannot safely preserve metadata, this is always resolved in favor of dropping the metadata, not preventing the transform.

Dropping the metadata in this case changes the program semantics (unlike dropping profile data), thus the transformation in this case is unsafe so it should be disabled as this patch does.

I think I am missing what the issue with dropping the loop metadata would be, could you elaborate? If we drop the metadata we should only lose information that may have enabled additional transformations, but shouldn't change the result of the program.

True - I should have been clearer. The behavior of the program does not change. What changes is the 'expected' shape of the affected loop. This is similar in spirit for 'always_inline' /'noinline' etc. We should have strong reason to 'not' preserve user directives.

[mingmingl]

fix a typo (basck->back) around line 1145. No other change (history tab could show diff).

llvm/lib/Transforms/Utils/Local.cpp

while (isa<PHINode>(*BBI)) {
         } else {
           return false;
         }
       }
       ++BBI;
     }
   }
 
+  // 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop
+  // metadata.
+  //
+  // FIXME: This is a stop-gap solution to preserve inner-loop metadata given
+  // current status (that loop metadata is implemented as metadata attached to
+  // the branch instruction in the loop latch block). To quote from review
+  // comments, "the current representation of loop metadata (using a loop latch
+  // terminator attachment) is known to be fundamentally broken. Loop latches
+  // are not uniquely associated with loops (both in that a latch can be part of
+  // multiple loops and a loop may have multiple latches). Loop headers are. The
+  // solution to this problem is also known: Add support for basic block
+  // metadata, and attach loop metadata to the loop header."
+  //
+  // Why bail out:
+  // In this case, we expect 'BB' is the latch for outer-loop and 'BB->Pred' is
+  // the latch for inner-loop (see reason below), so bail out to prerserve
+  // inner-loop metadata rather than eliminating 'BB' and attaching its metadata
+  // to this inner-loop.
+  // - The reason we believe 'BB' and 'BB->Pred' have different inner-most
+  // loops: assuming 'BB' and 'BB->Pred' are from the same inner-most loop L,
+  // then 'BB' is the header and latch of 'L' and thereby 'L' must consist of
+  // one self-looping basic block, which is contradictory with the assumption.
+  //
+  // To illustrate how inner-loop metadata is dropped:
+  //
+  // CFG Before
+  //
+  // BB is while.cond.exit, attached with loop metdata md2.
+  // BB->Pred is for.body, attached with loop metadata md1.
+  //
+  //      entry
+  //        |
+  //        v
+  // ---> while.cond   ------------->  while.end
+  // |       |
+  // |       v
+  // |   while.body
+  // |       |
+  // |       v
+  // |    for.body <---- (md1)
+  // |       |  |______|
+  // |       v
+  // |    while.cond.exit (md2)
+  // |       |
+  // |_______|
+  //
+  // CFG After
+  //
+  // while.cond1 is the merge of while.cond.exit and while.cond above.
+  // for.body is attached with md2, and md1 is dropped.
+  // If LoopSimplify runs later (as a part of loop pass), it could create
+  // dedicated exits for inner-loop (essentially adding `while.cond.exit`
+  // back), but won't it won't see 'md1' nor restore it for the inner-loop.
+  //
+  //       entry
+  //         |
+  //         v
+  // ---> while.cond1  ------------->  while.end
+  // |       |
+  // |       v
+  // |   while.body
+  // |       |
+  // |       v
+  // |    for.body <---- (md2)
+  // |_______|  |______|
+  if (Instruction *TI = BB->getTerminator())
+    if (MDNode *LoopMD = TI->getMetadata(LLVMContext::MD_loop)) {
+      for (BasicBlock *Pred : predecessors(BB)) {
+        if (Instruction *PredTI = Pred->getTerminator())
+          if (MDNode *PredLoopMD = PredTI->getMetadata(LLVMContext::MD_loop))
+            return false;
+      }
+    }
+
   LLVM_DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
 
   SmallVector<DominatorTree::UpdateType, 32> Updates;
   if (DTU) {
     // To avoid processing the same predecessor more than once.
     SmallPtrSet<BasicBlock *, 8> SeenPreds;
     // All predecessors of BB will be moved to Succ.
     SmallPtrSet<BasicBlock *, 8> PredsOfSucc(pred_begin(Succ), pred_end(Succ));

llvm/test/Transforms/SimplifyCFG/preserve-llvm-loop-metadata.ll

 
 if.end:                                           ; preds = %if.else, %if.then
   br label %while.cond, !llvm.loop !0
 
 while.end:                                        ; preds = %while.cond
   ret void
 }
 
-; The test case is constructed based on the following C++ code,
-; as a simplified test case to show why `llvm.loop.unroll.enable`
-; could be dropped.
+; Test that empty loop latch `while.cond.loopexit` will not be folded into its successor if its
+; predecessor blocks are also loop latches.
 ;
+; The test case is constructed based on the following C++ code.
 ; While the C++ code itself might have the inner-loop unrolled (e.g., with -O3),
 ; the loss of inner-loop unroll metadata is a bug.
 ; Under some optimization pipelines (e.g., FullLoopUnroll pass is skipped in ThinLTO prelink stage),
 ; and in real-world C++ code (e.g., with larger loop body), failing to
 ; preserve loop unroll metadata could cause missed loop unroll.
 ;
 ; constexpr int kUnroll = 5;
 ; int sum(int a, int b, int step, const int remainder, int* input) {

 !0 = distinct !{!0, !1}
 !1 = !{!"llvm.loop.distribute.enable", i1 true}
 !2 = distinct !{!2, !3}
 !3 = !{!"llvm.loop.mustprogress"}
 !4 = distinct !{!4, !3, !5}
 !5 = !{!"llvm.loop.unroll.enable"}
 ; CHECK: !0 = distinct !{!0, !1}
 ; CHECK: !1 = !{!"llvm.loop.distribute.enable", i1 true}
-; CHECK-NOT: !{!"llvm.loop.unroll.enable"}
+; CHECK: !2 = distinct !{!2, !3}
+; CHECK: !3 = !{!"llvm.loop.mustprogress"}
+; CHECK: !4 = distinct !{!4, !3, !5}
+; CHECK: !5 = !{!"llvm.loop.unroll.enable"}