[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;
     }
   }
 
+  // If the unconditional branch we replaced contains llvm.loop metadata
+  // and any of its predecessor is also a loop latch, bail out directly.
+  //
+  // Two alternative options that won't work well:
+  // 1. Partially forwards 'BB->pred' to 'BB->succ', only for predecessors of BB
+  // that are not loop latches.
+  //    In this case, 'BB' might be partially duplicated (e.g., the PHI
+  //    instructions) into 'BB->succ' for non-loop-latch pred, and meanwhile
+  //    still preserved for loop-latch pred. 'BB->succ' has more predecesors.
+  // 2. Proceed with deleting 'BB' when loop metadata of BB and Pred could be
+  // concatenated correctly (e.g. loop properties doesn't conflict, and the
+  // concatenation won't changing loop transformation result due to pass
+  // ordering, etc).
+  //    1) Firstly, multiple transformations in the same metadata are ambigious
+  //    -> the transformation result depend on execution order of different loop
+  //    passes. Say 'BB' and 'BB->pred' are outer and inner loop respectively,
+  //    concatenating them correctly for different scenarios is tricky. 2) In a
+  //    subset of cases when concat is correct,
+  //       a) if the inner-most loop of 'BB' and inner-most loop of Pred are the
+  //       same loop, LoopSimplify (scheduled before each LoopPass by pass
+  //       managers) will ensure there is only exactly one loop latch. So it's
+  //       better to let LoopSimplify simplify the CFG. b) If 'BB' is from an
+  //       outer loop and 'Pred' is from an inner loop, then 'BB' is an exit
+  //       block of the inner-loop with predecessors that are out of the
+  //       inner-loop. As a result, LoopSimplify will create dedicated exits for
+  //       the inner loop, which has the same effect of adding 'BB' back. By
+  //       then it's ambiguious how to undo the concatenation of loop metadata.
+  //
+  // In practice, the SimplifyCFG pass could run many times in an optimizer
+  // pipeline. When SimplifyCFG run after all loops passes complete, loops might
+  // have been simplified away (e.g. completely unrolled). In these cases, this
+  // function could still kick in and simplify trival 'BB' away.
+  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));
     Updates.reserve(Updates.size() + 2 * pred_size(BB) + 1);
     for (auto *PredOfBB : predecessors(BB))
       // This predecessor of BB may already have Succ as a successor.
       if (!PredsOfSucc.contains(PredOfBB))
         if (SeenPreds.insert(PredOfBB).second)
           Updates.push_back({DominatorTree::Insert, PredOfBB, Succ});
     SeenPreds.clear();
     for (auto *PredOfBB : predecessors(BB))
       if (SeenPreds.insert(PredOfBB).second)
         Updates.push_back({DominatorTree::Delete, PredOfBB, BB});
     Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
 
   if (isa<PHINode>(Succ->begin())) {

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

-; RUN: opt -opaque-pointers -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -keep-loops=false -S < %s | FileCheck %s
-; RUN: opt -opaque-pointers -passes='simplifycfg<no-keep-loops>' -S < %s | FileCheck %s
+; 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, i32* %n.addr, align 4
   %0 = bitcast i32* %count to i8*
   store i32 0, i32* %count, align 4

 ;        i += step;
 ;        #pragma unroll
 ;        for (int k = 0; k < kUnroll; k++) {
 ;           asm volatile ("add %w0, %w1\n" : "=r"(sum) : "r"(input[k + i]):"cc");
 ;        }
 ;    }
 ;    return sum;
 ; }
-define i32 @test2(i32 %a, i32 %b, i32 %step, i32 %remainder, ptr %input) {
+define i32 @test2(i32 %a, i32 %b, i32 %step, i32 %remainder, i32* %input) {
 entry:
   br label %while.cond
 
 while.cond.loopexit:                              ; preds = %for.body
   br label %while.cond, !llvm.loop !2
 
 while.cond:                                       ; preds = %while.cond.loopexit, %entry
   %i.0 = phi i32 [ %a, %entry ], [ %add, %while.cond.loopexit ]
   %sum.0 = phi i32 [ 0, %entry ], [ %1, %while.cond.loopexit ]
   %sub = sub nsw i32 %b, %i.0
   %cmp = icmp sgt i32 %sub, %remainder
   br i1 %cmp, label %while.body, label %while.end
 
 while.body:                                       ; preds = %while.cond
   %add = add nsw i32 %i.0, %step
   br label %for.body
 
 for.body:                                         ; preds = %while.body, %for.body
   %k.07 = phi i32 [ 0, %while.body ], [ %inc, %for.body ]
   %add2 = add nsw i32 %k.07, %add
   %idxprom = sext i32 %add2 to i64
-  %arrayidx = getelementptr inbounds i32, ptr %input, i64 %idxprom
-  %0 = load i32, ptr %arrayidx, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %input, i64 %idxprom
+  %0 = load i32, i32* %arrayidx, align 4
   %1 = tail call i32 asm sideeffect "add ${0:w}, ${1:w}\0A", "=r,r,~{cc}"(i32 %0)
   %inc = add nuw nsw i32 %k.07, 1
   %cmp1 = icmp ult i32 %inc, 5
   br i1 %cmp1, label %for.body, label %while.cond.loopexit, !llvm.loop !4
 
 while.end:                                        ; preds = %while.cond
   %sum.0.lcssa = phi i32 [ %sum.0, %while.cond ]
   ret i32 %sum.0.lcssa
 }
 
 !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: !4 = distinct !{!4, !3, !5}
+; CHECK: !5 = !{!"llvm.loop.unroll.enable"}