[LoopPredication] Do not sink conditions to branches. PR61673

[mkazantsev]

Summary

This patch fixes the bug that happens when we sink a widenable condition from
outside the loop into the loop, and therefore creating more possible execution
paths than existed before.

This sinking is:

• sometimes illegal, as shown in https://github.com/llvm/llvm-project/issues/61673
• always useless, at least I could not find any reason to do it.

Maybe there was some intent here, but there is no test that would show why it is done
and I could not find such reason myself. So I'm just removing this code.

[mkazantsev]

@reames you seem to be the author of this code. Do you remember why it was done? I couldn't figure out the motivation from this comment or tests.

[anna]

Adding more context here: This transform gets enabled by LICM hoisting widenable conditions (today it is hidden because we stopped LICM from hoisting widenable conditions: https://reviews.llvm.org/D146274). Also, while discussing with @apilipenko about the comment in Loop Predication, he pointed that the latter part of the comment referred to older implementation in loop predication before we had GuardUtils::widenBranch API.
Specifically the latter part of this comment (" inserting code before it and then modifying the operand is legal.") :

// Subtlety: We need to avoid inserting additional uses of the WC.  We know
 // that it can only have one transitive use at the moment, and thus moving
 // that use to just before the branch and inserting code before it and then
 // modifying the operand is legal.

But we could not identify why "we need to avoid inserting additional uses of the WC".

It seems there is a wider problem here. At least, according to me, there is nothing in the semantics of widenable condition that prevents us from sinking widenable condition into the loop. This means we can have subtle (and hard to debug) miscompiles such as the one caused here and in GuardWidening (explained here: https://github.com/llvm/llvm-project/issues/60234). Anything that prevents LLVM transforms from sinking widenable condition into loops?

One more point: the original cause of the downstream miscompile is still present after this fix (that makes sense because even when we sink the widenable condition into the loop, later LICM comes along and hoists it out, so the bug attempted to be fixed by this patch is masked). In short - the miscompile is seen when we have loop predication's hoisting of widenable condition, followed by loop predication's predicate loop exits transform here. Will continue investigation on that front.

This patch probably solves a bug as explained by Max here: https://github.com/llvm/llvm-project/issues/61673

[mkazantsev]

It seems there is a wider problem here. At least, according to me, there is nothing in the semantics of widenable condition that prevents us from sinking widenable condition into the loop.

@anna here is how WC is declared:

// Supports widenable conditions for guards represented as explicit branches.
def int_experimental_widenable_condition : Intrinsic<[llvm_i1_ty], [],
                                           [IntrInaccessibleMemOnly, IntrWillReturn]>;

it has semantics of accessing innacessible memory. In particular, it can read or write it. So you cannot sink it into the loops for the same reasons as you cannot do so to volatile loads. Hoisting - possibly legal (assuming that no one else is accessing this memory), but sinking is sure not.

So by default, we should not move it at all, unless we intentionally did exceptions (and I'm currently finding and undoing them; they were not meant to exist).

[anna]

Thanks for clarification Max.

This is superseded by the complete fix here: https://reviews.llvm.org/D147662

[anna]

llvm/lib/Transforms/Scalar/LoopPredication.cpp

1188

We should not widen at the branch, but rather at the widenable call. This is handled in the patch referenced above.

[mkazantsev]

Closing per Anna's comment.

llvm/lib/Transforms/Scalar/LoopPredication.cpp

bool LoopPredication::predicateLoopExits(Loop *L, SCEVExpander &Rewriter) {
   // can't guarantee this as a current unanalyzeable exit may later become
   // analyzeable, but we can at least avoid the obvious cases.
   const SCEV *MinEC = getMinAnalyzeableBackedgeTakenCount(*SE, *DT, L);
   if (isa<SCEVCouldNotCompute>(MinEC) || MinEC->getType()->isPointerTy() ||
       !SE->isLoopInvariant(MinEC, L) ||
       !Rewriter.isSafeToExpandAt(MinEC, WidenableBR))
     return ChangedLoop;
 
-  // Subtlety: We need to avoid inserting additional uses of the WC.  We know
-  // that it can only have one transitive use at the moment, and thus moving
-  // that use to just before the branch and inserting code before it and then
-  // modifying the operand is legal.
-  auto *IP = cast<Instruction>(WidenableBR->getCondition());
-  // Here we unconditionally modify the IR, so after this point we should return
-  // only `true`!
-  IP->moveBefore(WidenableBR);
-  if (MSSAU)
-    if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(IP))
-       MSSAU->moveToPlace(MUD, WidenableBR->getParent(),
-                          MemorySSA::BeforeTerminator);
-  Rewriter.setInsertPoint(IP);
-  IRBuilder<> B(IP);
+  Rewriter.setInsertPoint(WidenableBR);
+  IRBuilder<> B(WidenableBR);
 
   bool InvalidateLoop = false;
   Value *MinECV = nullptr; // lazily generated if needed
   for (BasicBlock *ExitingBB : ExitingBlocks) {
     // If our exiting block exits multiple loops, we can only rewrite the
     // innermost one.  Otherwise, we're changing how many times the innermost
     // loop runs before it exits.
     if (LI->getLoopFor(ExitingBB) != L)

llvm/test/Transforms/LoopPredication/pr61673.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt -S -passes=loop-predication < %s 2>&1 | FileCheck %s
+
+; DO NOT sink widenable condition into the loop. It will create extra uses, which leads to miscompile.
+; See detailed explanation at https://github.com/llvm/llvm-project/issues/61673.
+define i32 @test() {
+; CHECK-LABEL: define i32 @test() {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WC:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    br label [[OUTER_LOOP:%.*]]
+; CHECK:       outer_backedge.loopexit:
+; CHECK-NEXT:    br label [[OUTER_BACKEDGE:%.*]]
+; CHECK:       outer_backedge:
+; CHECK-NEXT:    call void @print()
+; CHECK-NEXT:    [[CNT_NEXT:%.*]] = add i32 [[CNT:%.*]], 1
+; CHECK-NEXT:    br label [[OUTER_LOOP]]
+; CHECK:       outer_loop:
+; CHECK-NEXT:    [[CNT]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[CNT_NEXT]], [[OUTER_BACKEDGE]] ]
+; CHECK-NEXT:    br i1 [[WC]], label [[INNER_LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       inner_loop.preheader:
+; CHECK-NEXT:    br label [[INNER_LOOP:%.*]]
+; CHECK:       inner_loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[NEVER:%.*]] ], [ 2, [[INNER_LOOP_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
+; CHECK-NEXT:    br i1 false, label [[NEVER]], label [[ALWAYS:%.*]]
+; CHECK:       never:
+; CHECK-NEXT:    [[ICMP:%.*]] = icmp ugt i32 [[IV_NEXT]], 37
+; CHECK-NEXT:    br i1 [[ICMP]], label [[OUTER_BACKEDGE_LOOPEXIT:%.*]], label [[INNER_LOOP]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[CNT_LCSSA:%.*]] = phi i32 [ [[CNT]], [[OUTER_LOOP]] ]
+; CHECK-NEXT:    ret i32 [[CNT_LCSSA]]
+; CHECK:       always:
+; CHECK-NEXT:    br label [[OUTER_BACKEDGE]]
+;
+entry:
+  %wc = call i1 @llvm.experimental.widenable.condition()
+  br label %outer_loop
+
+outer_backedge:                                   ; preds = %always, %never
+  call void @print()
+  %cnt.next = add i32 %cnt, 1
+  br label %outer_loop
+
+outer_loop:                                       ; preds = %outer_backedge, %entry
+  %cnt = phi i32 [0, %entry], [%cnt.next, %outer_backedge]
+  br i1 %wc, label %inner_loop.preheader, label %exit
+
+inner_loop.preheader:                             ; preds = %outer_loop
+  br label %inner_loop
+
+inner_loop:                                       ; preds = %never, %inner_loop.preheader
+  %iv = phi i32 [ %iv.next, %never ], [ 2, %inner_loop.preheader ]
+  %iv.next = add nuw nsw i32 %iv, 1
+  br i1 false, label %never, label %always
+
+never:                                            ; preds = %inner_loop
+  %icmp = icmp ugt i32 %iv.next, 37
+  br i1 %icmp, label %outer_backedge, label %inner_loop
+
+exit:                                             ; preds = %outer_loop
+  %cnt.lcssa = phi i32 [%cnt, %outer_loop]
+  ret i32 %cnt.lcssa
+
+always:                                           ; preds = %inner_loop
+  br label %outer_backedge
+}
+
+declare void @print()
+
+; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite)
+declare noundef i1 @llvm.experimental.widenable.condition() #0
+
+attributes #0 = { nocallback nofree nosync nounwind speculatable willreturn memory(inaccessiblemem: readwrite) }

llvm/test/Transforms/LoopPredication/predicate-exits.ll

 exit:
   %result = phi i32 [ %loop.acc.next, %guarded ]
   ret i32 %result
 }
 
 define i32 @trivial_wb(ptr %array, i32 %length, i32 %n) {
 ; CHECK-LABEL: @trivial_wb(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[N:%.*]], i32 1)
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[UMAX]], -1
 ; CHECK-NEXT:    [[UMIN:%.*]] = call i32 @llvm.umin.i32(i32 [[LENGTH:%.*]], i32 [[TMP0]])
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[LENGTH]], [[UMIN]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = freeze i1 [[TMP1]]
-; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i1 [[TMP2]], [[WIDENABLE_COND]]
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_PREHEADER:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    [[DEOPTRET:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
 ; CHECK-NEXT:    ret i32 [[DEOPTRET]]
 ; CHECK:       loop.preheader:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:

 exit:
   %result = phi i32 [ %loop.acc.next, %guarded2 ]
   ret i32 %result
 }
 
 define void @test_memssa() {
 ; CHECK-LABEL: @test_memssa(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[TMP:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    [[TMP1:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    br i1 [[TMP]], label [[BB3:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       bb3:
 ; CHECK-NEXT:    br label [[BB4:%.*]]
 ; CHECK:       bb4:
 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i32 [ [[TMP7:%.*]], [[BB6:%.*]] ], [ 0, [[BB3]] ]
 ; CHECK-NEXT:    br i1 true, label [[BB10:%.*]], label [[BB6]]