[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

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

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/include/llvm/Transforms/Utils/Local.h

 /// successor (BB!). Eliminate the edge between them, moving the instructions in
 /// the predecessor into BB. This deletes the predecessor block.
 void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, DomTreeUpdater *DTU = nullptr);
 
 /// BB is known to contain an unconditional branch, and contains no instructions
 /// other than PHI nodes, potential debug intrinsics and the branch. If
 /// possible, eliminate BB by rewriting all the predecessors to branch to the
 /// successor block and return true. If we can't transform, return false.
+//
+// FIXME: Currently the conditions diverge when this function is called by
+// 'JumpThreading' and 'SimplifyCFG'. The divergence should really be unified.
 bool TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
                                              DomTreeUpdater *DTU = nullptr);
 
 /// Check for and eliminate duplicate PHI nodes in this block. This doesn't try
 /// to be clever about PHI nodes which differ only in the order of the incoming
 /// values, but instcombine orders them so it usually won't matter.
 bool EliminateDuplicatePHINodes(BasicBlock *BB);
 

llvm/lib/Transforms/Utils/Local.cpp

while (isa<PHINode>(*BBI)) {
         } else {
           return false;
         }
       }
       ++BBI;
     }
   }
 
+  // 'BB' and 'BB->Pred' are loop latches, 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` 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)
+  // |_______|  |______|
+  //
+  // Alternative option 1, concatenate outer-loop metadata and inner-loop
+  // metadata and attach it to inner-loop metadata and proceed with deleting BB.
+  // This doesn't work since multiple transformations in the same loop metadata
+  // are not well defined, and the results could depend on loop pass ordering.
+  // Even if concatenation is correct, deleted 'BB' could be added back by
+  // LoopSimplify pass -> use CFG after as an example, after 'BB' is deleted,
+  // 'while.cond1' is an exit block with predecessors (entry) that are not
+  // dominated by inner-loop header (for.body), so LoopSimplify will add a
+  // dedicated exit for the inner-loop. By then it's ambigious how to undo the
+  // concatenation of loop metadata.
+  //
+  // Alternative option 2, partially fold 'BB' into 'BB->Succ' -> this may not
+  // simplify CFG.
+  //
+  // To illustrate:
+  //
+  // CFG Before
+  //
+  //     BB.0  BB.1  BB.2 (md1)    AnotherPred
+  //      |   /           |             |
+  //      v  v            |             |
+  //     BB.PHI           |             |
+  //     BB.BR (md2) <----              |
+  //      |                             |
+  //      v                             |
+  //     Succ <-------------------------
+  //
+  // CFG After
+  //
+  //     (md2)  (md2)
+  //    BB.0  BB.1  BB.2 (md1)  AnotherPred
+  //     |     /      |            |
+  //     |     /      v            |
+  //     |    /     BB.PHI         |
+  //     |    /     BB.BR(md2)     |
+  //     |   /   /                 |
+  //     v  v   v                  |
+  //    BB.PHI.Rewrite             |
+  //    Succ <----------------------
+  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

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -keep-loops=false -S < %s | FileCheck %s
 ; RUN: opt -passes='simplifycfg<no-keep-loops>' -S < %s | FileCheck %s
 
 define void @test1(i32 %n) #0 {
 entry:
   %n.addr = alloca i32, align 4
   %count = alloca i32, align 4
   store i32 %n, ptr %n.addr, align 4
while.body:                                       ; preds = %while.cond
   br i1 %cmp1, label %if.then, label %if.else
 
 if.then:                                          ; preds = %while.body
   %3 = load i32, ptr %count, align 4
   %add = add i32 %3, 1
   store i32 %add, ptr %count, align 4
   br label %if.end
 
-; CHECK: if.then:
-; CHECK:  br label %while.cond, !llvm.loop !0
 
 if.else:                                          ; preds = %while.body
   %4 = load i32, ptr %count, align 4
   %add2 = add i32 %4, 2
   store i32 %add2, ptr %count, align 4
   br label %if.end
 
-; CHECK: if.else:
-; CHECK:  br label %while.cond, !llvm.loop !0
 
 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"}