[SimplifyCFG] Fix miscompile in tryWidenCondBranchToCondBranch. PR52290

[mkazantsev]

Summary

tryWidenCondBranchToCondBranch is supposed to perform guard widening,
redirecting a deopting exit of successor block into a deopting exit of the
widenable predecessor block. But the check that the latter is actually deoptimizing
was never done. As result, the transform was turning

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb7, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb2, %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

into

define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
bb:
  %tmp = call i1 @llvm.experimental.widenable.condition()
  br i1 %tmp, label %bb2, label %bb1

bb1:                                              ; preds = %bb2, %bb
  br i1 undef, label %bb7, label %bb5

bb2:                                              ; preds = %bb
  %tmp3 = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
  br i1 undef, label %bb1, label %bb4

bb4:                                              ; preds = %bb2
  call void @snork() [ "deopt"() ]
  unreachable

bb5:                                              ; preds = %bb1
  ret i32 0

bb7:                                              ; preds = %bb1
  %tmp8 = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
  ret i32 %tmp8
}

Note that this is just wrong: previously taking branch bb2->bb7 was always a deopt,
but then it was replaced with bb2->bb1 and then it could go to bb5 which was not
even reachable from bb2 before the transform. (In this test conditions are undef, but
in fact they are never analyzed so it doesn't matter; condition in bb2 could as well be
a regular value).

So in fact, this transform may replace a deopting edge with some random edge which
never deopts. It's a miscompile by itself, and in case of SimplifyCFG, it has weird interactions
with other transforms of SimplifyCondBranchToCondBranch, which create a .pr Phi, then
thread through it, and then the described buggy transform repeats and brings the code into
its initial state. So we end up stuck in an infinite loop.

This patch fixes this situation by ensuring that widenable condition branch actually goes to
deopt if the condition is false.

[lebedev.ri]

I'm not familiar with @llvm.experimental.deoptimize.
This should not be in parseWidenableBranch(), right?

[reames]

Max, the wideable condition intrinsic is carefully specified to not require any particular item down the widened path. Your explanation is misleading at best.

I suspect you do have a bug here - the test case sure seems to imply that - but it's not the lack of a deoptimizing call down the untaken path of the widenable condition. I'd almost suspect a bug in your frontend lowering to this if it weren't for the infinite loop in the test case.

[mkazantsev]

Philip, the bug was indeed revealed on attempt to change the frontend, but there was no bug in initial IR. You are right that widenable condition does not require anything specific be down the false path. But guard widening does. All deopts are mutually replacable, but you can't replace a deopt with a random branch just because there is a widenable condition elsewhere. This makes SimplifyCFG somewhat mad.

[mkazantsev]

Some more detailed description: imagine each block had a unique call signaling that we entered it. In the initial test, path bb->bb1->bb5 did exist and was legal. But if after bb we've decided to go to bb2, then there is no possible way we can ever get to bb5. But with this transform, we sure can (bb->bb2->bb1->bb5), for no explainable reason. Guard widening doesn't explain it. It's a bug.

[mkazantsev]

Ping

[apilipenko]

I agree with Philip, widening transformation doesn't rely on deoptimizations.

Some more detailed description: imagine each block had a unique call signaling that we entered it.

The transform in question will not happen if there are side effects in the block.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static bool tryWidenCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI,
   //    BI's condition.
   Value *CondWB, *WC;
   BasicBlock *IfTrueBB, *IfFalseBB;
   if (!parseWidenableBranch(PBI, CondWB, WC, IfTrueBB, IfFalseBB) ||
       IfTrueBB != BI->getParent() || !BI->getParent()->getSinglePredecessor())
     return false;
   if (!IfFalseBB->phis().empty())
     return false; // TODO
+  // We are going to replace one of deopting successors of BB with IfFalseBB,
+  // but for that we need to make sure it's actually deoptimizing.
+  if (!IfFalseBB->getTerminatingDeoptimizeCall())
+    return false;
   // Use lambda to lazily compute expensive condition after cheap ones.
   auto NoSideEffects = [](BasicBlock &BB) {
     return !llvm::any_of(BB, [](const Instruction &I) {
         return I.mayWriteToMemory() || I.mayHaveSideEffects();
       });
   };
   if (BI->getSuccessor(1) != IfFalseBB && // no inf looping
       BI->getSuccessor(1)->getTerminatingDeoptimizeCall() && // profitability

llvm/test/Transforms/SimplifyCFG/pr52290.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 ; RUN: opt < %s -passes=simplifycfg -S | FileCheck %s
 
-; XFAIL: *
-; REQUIRES: asserts
-; FIXME: Fails due to infinite loop in iterativelySimplifyCFG.
-
 ; ModuleID = 'test/Transforms/SimplifyCFG/pr-new.ll'
 source_filename = "test/Transforms/SimplifyCFG/pr-new.ll"
 
 define i32 @test(float %arg) gc "statepoint-example" personality i32* ()* @blam {
-; CHECK-LABEL: @test
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP:%.*]] = call i1 @llvm.experimental.widenable.condition()
+; CHECK-NEXT:    br i1 [[TMP]], label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br i1 undef, label [[BB7:%.*]], label [[BB5:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, i8 addrspace(1)* undef, i64 16
+; CHECK-NEXT:    br i1 undef, label [[BB7]], label [[BB4:%.*]]
+; CHECK:       bb4:
+; CHECK-NEXT:    call void @snork() [ "deopt"() ]
+; CHECK-NEXT:    unreachable
+; CHECK:       bb5:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP8:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32(i32 10) [ "deopt"() ]
+; CHECK-NEXT:    ret i32 [[TMP8]]
+;
 bb:
   %tmp = call i1 @llvm.experimental.widenable.condition()
   br i1 %tmp, label %bb2, label %bb1
 
 bb1:                                              ; preds = %bb
   br i1 undef, label %bb7, label %bb5
 
 bb2:                                              ; preds = %bb