[SCCP] convert signed div/rem to unsigned for non-negative operands

[spatel]

Summary

This extends the transform added with D81756 to handle div/rem opcodes. For example:
https://alive2.llvm.org/ce/z/cX6za6

This replicates part of what CVP already does, but the motivating example from issue #57472, demonstrates a phase ordering problem - we convert branches to select before CVP runs and miss the transform.

I didn't find an explanation for skipping a constant operand in the existing zext code (ie, sext i8 42 -> zext i8 42 is valid, but we skip it). So that clause is not included for this transform, but there is a test diff for that pattern in case it should be bypassed.

I'd split this into a refactoring NFC patch that adds the helper function, then add the code for sdiv/srem cases if approved. I can also add ashr->lshr as a follow-up.

[BaoshanPang]

llvm/test/Transforms/SCCP/divrem.ll

141

Should we add a 'TODO' here just like what we do for @sdiv_nonneg0_nonnegconst1 ?

[spatel]

llvm/test/Transforms/SCCP/divrem.ll

141

This one is not safe to transform - it needs 'nsw':
https://alive2.llvm.org/ce/z/VDuSrw

I can make that explicit in the comment.

[BaoshanPang]

llvm/test/Transforms/SCCP/divrem.ll

141

I see. Thanks for the example.
Then the patch looks good to me.

[fhahn]

I didn't find an explanation for skipping a constant operand in the existing zext code (ie, sext i8 42 -> zext i8 42 is valid, but we skip it). So that clause is not included for this transform, but there is a test diff for that pattern in case it should be bypassed.

Do those operations have users left? If they can be simplified to a constant, I'd expect tryToReplaceWithConstant to take care of replacing all users of them.

I'd split this into a refactoring NFC patch that adds the helper function, then add the code for sdiv/srem cases if approved. I

Splitting off the helper first would make sense, overall this looks like a nice improvement.

[spatel]

In D133198#3767857, @fhahn wrote:

I didn't find an explanation for skipping a constant operand in the existing zext code (ie, sext i8 42 -> zext i8 42 is valid, but we skip it). So that clause is not included for this transform, but there is a test diff for that pattern in case it should be bypassed.

Do those operations have users left? If they can be simplified to a constant, I'd expect tryToReplaceWithConstant to take care of replacing all users of them.

Yes, the instruction still has a user. For example, when I step through this:

define i16 @srem_cmp_constants() {
  %sel = select i1 false, i16 0, i16 12704
  %r = srem i16 %sel, 0
  ret i16 %r
}

I see:

% opt -ipsccp sdiv.ll -S -debug
Args: opt -ipsccp sdiv.ll -S -debug 
Marking Block Executable: 

Popped off BBWL: 
  %sel = select i1 false, i16 0, i16 12704
  %r = srem i16 %sel, 0
  ret i16 %r

Merged constantrange<12704, 12705> into   %sel = select i1 false, i16 0, i16 12704 : constantrange<12704, 12705>

Popped off I-WL:   %sel = select i1 false, i16 0, i16 12704
RESOLVING UNDEFS
markOverdefined:   %r = srem i16 %sel, 0

Popped off OI-WL:   %r = srem i16 %sel, 0
Merged overdefined into define i16 @srem_cmp_constants() {
  %sel = select i1 false, i16 0, i16 12704
  %r = srem i16 %sel, 0
  ret i16 %r
}
 : overdefined

Popped off OI-WL: define i16 @srem_cmp_constants() {
  %sel = select i1 false, i16 0, i16 12704
  %r = srem i16 %sel, 0
  ret i16 %r
}

RESOLVING UNDEFS
  Constant: i16 12704 =   %sel = select i1 false, i16 0, i16 12704
; ModuleID = 'sdiv.ll'
source_filename = "sdiv.ll"

define i16 @srem_cmp_constants() {
  %r = srem i16 12704, 0
  ret i16 %r
}

So we are doing the RAUW, but the solver is not re-run on those uses to get the subsequent constant-folding?

[spatel]

In D133198#3768623, @spatel wrote:

define i16 @srem_cmp_constants() {

%r = srem i16 12704, 0
ret i16 %r

}

So we are doing the RAUW, but the solver is not re-run on those uses to get the subsequent constant-folding?

Ah - just noticed that it all folds away except in this case with 0 divisor. That's treated as a special-case because it is immediate UB?

[spatel]

Patch updated:
Rebased after refactoring (22e1f66f26b8).
Added explanatory comment to negative multiply test.

[spatel]

Patch updated:
Missed adding a test comment in the previous revision.

[bcl5980]

Should we do this in Instcombine also? Like check Known.isNonNegative() for LHS and RHS in instcombine?
SCCP can work on the cases with dominated condition. And Instcombine with value tracking also help the case like abs or and a mask without sign bits?

[spatel]

In D133198#3769266, @bcl5980 wrote:

Should we do this in Instcombine also? Like check Known.isNonNegative() for LHS and RHS in instcombine?
SCCP can work on the cases with dominated condition. And Instcombine with value tracking also help the case like abs or and a mask without sign bits?

It's already done:
https://github.com/llvm/llvm-project/blob/8534f514747d57cd42602403eb98c8230f5c7ff9/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp#L1218
https://github.com/llvm/llvm-project/blob/8534f514747d57cd42602403eb98c8230f5c7ff9/llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp#L1607

We miss the transform in the motivating case because the dominating condition is converted to select. So we could also match select patterns in instcombine, but I like this as a more general solution.

[spatel]

Based on previous "LGTM" comment, setting this to "accepted", so it won't complain on commit.

[fhahn]

Ah - just noticed that it all folds away except in this case with 0 divisor. That's treated as a special-case because it is immediate UB?

Yeah, probably not worth worrying about

[fhahn]

It looks like this is causing a crash when building llvm-test-suite. Ive reverted the commit for now to unblock some bots.

To reproduce, run opt -passes=ipsccp on the IR below.

@g = internal global i32 256, align 4

define void @test() {
entry:
  %0 = load i32, ptr @g, align 4
  %div = sdiv i32 %0, undef
  ret void
}

[fhahn]

I should have been clearer, this patch seems to cause the assertion below for the reproducer:

Assertion failed: (I != ValueState.end() && "V not found in ValueState nor Paramstate map!"), function getLatticeValueFor, file SCCPSolver.cpp, line 418.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0. Program arguments: ..../bin/opt -ipsccp bugpoint-reduced-simplified.ll
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  opt                      0x0000000106285094 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
1  opt                      0x0000000106284094 llvm::sys::RunSignalHandlers() + 112
2  opt                      0x0000000106285720 SignalHandler(int) + 344
3  libsystem_platform.dylib 0x0000000197bc82a4 _sigtramp + 56
4  libsystem_pthread.dylib  0x0000000197b99cec pthread_kill + 288
5  libsystem_c.dylib        0x0000000197ad32c8 abort + 180
6  libsystem_c.dylib        0x0000000197ad2620 err + 0
7  opt                      0x00000001072a5cac llvm::SCCPInstVisitor::getLatticeValueFor(llvm::Value*) const (.cold.3) + 0
8  opt                      0x00000001063883ec llvm::SCCPSolver::getTrackedRetVals() + 0
9  opt                      0x000000010610dbb8 simplifyInstsInBlock(llvm::SCCPSolver&, llvm::BasicBlock&, llvm::SmallPtrSetImpl<llvm::Value*>&, llvm::TrackingStatistic&, llvm::TrackingStatistic&) + 964
10 opt                      0x000000010610c144 llvm::runIPSCCP(llvm::Module&, llvm::DataLayout const&, std::__1::function<llvm::TargetLibraryInfo const& (llvm::Function&)>, llvm::function_ref<llvm::AnalysisResultsForFn (llvm::Function&)>) + 1488
11 opt                      0x0000000105cac960 llvm::IPSCCPPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) + 200
12 opt                      0x0000000105a688e0 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) + 460
13 opt                      0x0000000104979b10 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) + 12628
14 opt                      0x0000000104989eb4 main + 13084
15 dyld                     0x0000000197873e50 start + 2544

[spatel]

In D133198#3772527, @fhahn wrote:

I should have been clearer, this patch seems to cause the assertion below for the reproducer:

Assertion failed: (I != ValueState.end() && "V not found in ValueState nor Paramstate map!"), function getLatticeValueFor, file SCCPSolver.cpp, line 418.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0. Program arguments: ..../bin/opt -ipsccp bugpoint-reduced-simplified.ll
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
0  opt                      0x0000000106285094 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) + 56
1  opt                      0x0000000106284094 llvm::sys::RunSignalHandlers() + 112
2  opt                      0x0000000106285720 SignalHandler(int) + 344
3  libsystem_platform.dylib 0x0000000197bc82a4 _sigtramp + 56
4  libsystem_pthread.dylib  0x0000000197b99cec pthread_kill + 288
5  libsystem_c.dylib        0x0000000197ad32c8 abort + 180
6  libsystem_c.dylib        0x0000000197ad2620 err + 0
7  opt                      0x00000001072a5cac llvm::SCCPInstVisitor::getLatticeValueFor(llvm::Value*) const (.cold.3) + 0
8  opt                      0x00000001063883ec llvm::SCCPSolver::getTrackedRetVals() + 0

Thanks for reverting. I didn't see any bot fail mails that correspond to this crash, but I can repro the minimal test crashing locally.
However, I'm still not sure what is going on in the internals of the solver. Strangely, there's no crash if I just insert the same test into the file with the other tests that were added for this patch. Something about the state of other tests prevents the crash.
Maybe this is why the existing code avoided transforming a constant-foldable instruction in the sext case? :)
If I add a clause like that here, it seems to avoid the trouble, but I'll try to step through some more and see if I can find the real cause of the problem.

llvm/lib/Transforms/Scalar/SCCP.cpp

static bool replaceSignedInst(SCCPSolver &Solver,
   case Instruction::SExt: {
     // If the source value is not negative, this is a zext.
     Value *Op0 = Inst.getOperand(0);
     if (isa<Constant>(Op0) || InsertedValues.count(Op0) || !isNonNegative(Op0))
       return false;
     NewInst = new ZExtInst(Op0, Inst.getType(), "", &Inst);
     break;
   }
+  case Instruction::SDiv:
+  case Instruction::SRem: {
+    // If both operands are not negative, this is the same as udiv/urem.
+    Value *Op0 = Inst.getOperand(0), *Op1 = Inst.getOperand(1);
+    if (InsertedValues.count(Op0) || InsertedValues.count(Op1) ||
+        !isNonNegative(Op0) || !isNonNegative(Op1))
+      return false;
+    auto NewOpcode = Inst.getOpcode() == Instruction::SDiv ? Instruction::UDiv
+                                                           : Instruction::URem;
+    NewInst = BinaryOperator::Create(NewOpcode, Op0, Op1, "", &Inst);
+    break;
+  }
   default:
     return false;
   }
 
   // Wire up the new instruction and update state.
   assert(NewInst && "Expected replacement instruction");
   NewInst->takeName(&Inst);
   InsertedValues.insert(NewInst);

llvm/test/Transforms/PhaseOrdering/srem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -O1 -S < %s | FileCheck %s
 ; RUN: opt -O2 -S < %s | FileCheck %s
 ; RUN: opt -O3 -S < %s | FileCheck %s
 
+; srem should be folded based on branch conditions
+; This can be done by IPSCCP or CVP.
+
 define i32 @PR57472(i32 noundef %x) {
 ; CHECK-LABEL: @PR57472(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X:%.*]], -1
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X]], 16
-; CHECK-NEXT:    [[COND:%.*]] = select i1 [[CMP]], i32 [[REM]], i32 42
-; CHECK-NEXT:    ret i32 [[COND]]
+; CHECK-NEXT:    [[REM:%.*]] = and i32 [[X]], 15
+; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[CMP]], i32 [[REM]], i32 42
+; CHECK-NEXT:    ret i32 [[SPEC_SELECT]]
 ;
 entry:
   %x.addr = alloca i32, align 4
   store i32 %x, ptr %x.addr, align 4
   %0 = load i32, ptr %x.addr, align 4
   %cmp = icmp sge i32 %0, 0
   br i1 %cmp, label %cond.true, label %cond.false
 

llvm/test/Transforms/SCCP/binaryops-range-special-cases.ll

 }
 
 define void @srem_cmp_constants() {
 ; CHECK-LABEL: @srem_cmp_constants(
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    call void @use(i1 false)
-; CHECK-NEXT:    [[SREM_3:%.*]] = srem i16 12704, 0
+; CHECK-NEXT:    [[SREM_3:%.*]] = urem i16 12704, 0
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i16 [[SREM_3]], 1
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
   %sel = select i1 false, i16 0, i16 12704
   %srem.1 = srem i16 %sel, 12704
   %c.1 = icmp eq i16 %srem.1, 0
   call void @use(i1 %c.1)

llvm/test/Transforms/SCCP/divrem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=ipsccp -S < %s | FileCheck %s
 
 define i8 @sdiv_nonneg0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_nonneg0_nonneg1(
 ; CHECK-NEXT:    [[PX:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[PX]], [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = udiv i8 [[PX]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = and i8 %x, 127
   %py = lshr i8 %y, 1
   %r = sdiv i8 %px, %py
   ret i8 %r
 }
 
 define i8 @sdiv_nonnegconst0_nonneg1(i7 %y) {
 ; CHECK-LABEL: @sdiv_nonnegconst0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = zext i7 [[Y:%.*]] to i8
-; CHECK-NEXT:    [[R:%.*]] = sdiv i8 42, [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = udiv i8 42, [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = zext i7 %y to i8
   %r = sdiv i8 42, %py
   ret i8 %r
 }
 
+; TODO: This can be converted to udiv.
+
 define i8 @sdiv_nonneg0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @sdiv_nonneg0_nonnegconst1(
 ; CHECK-NEXT:    [[PX:%.*]] = mul nsw i8 [[X:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[PX]], 42
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = mul nsw i8 %x, %x
   %r = sdiv i8 %px, 42
   ret i8 %r
 }
 
+; negative test
+
 define i8 @sdiv_unknown0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @sdiv_unknown0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[X:%.*]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = lshr i8 %y, 1
   %r = sdiv i8 %x, %py
   ret i8 %r
 }
 
+; negative test
+
 define i8 @sdiv_nonnegconst0_unknown1(i7 %y) {
 ; CHECK-LABEL: @sdiv_nonnegconst0_unknown1(
 ; CHECK-NEXT:    [[SY:%.*]] = sext i7 [[Y:%.*]] to i8
 ; CHECK-NEXT:    [[R:%.*]] = sdiv i8 42, [[SY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sy = sext i7 %y to i8
   %r = sdiv i8 42, %sy
   ret i8 %r
 }
 
+; negative test - mul must be 'nsw' to be known non-negative
+
 define i8 @sdiv_unknown0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @sdiv_unknown0_nonnegconst1(
 ; CHECK-NEXT:    [[SX:%.*]] = mul i8 [[X:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = sdiv i8 [[SX]], 42
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = mul i8 %x, %x
   %r = sdiv i8 %sx, 42
   ret i8 %r
 }
 
 define i8 @srem_nonneg0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @srem_nonneg0_nonneg1(
 ; CHECK-NEXT:    [[PX:%.*]] = and i8 [[X:%.*]], 127
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[PX]], [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[PX]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = and i8 %x, 127
   %py = lshr i8 %y, 1
   %r = srem i8 %px, %py
   ret i8 %r
 }
 
 define i8 @srem_nonnegconst0_nonneg1(i8 %y) {
 ; CHECK-LABEL: @srem_nonnegconst0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = and i8 [[Y:%.*]], 127
-; CHECK-NEXT:    [[R:%.*]] = srem i8 42, [[PY]]
+; CHECK-NEXT:    [[R:%.*]] = urem i8 42, [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = and i8 %y, 127
   %r = srem i8 42, %py
   ret i8 %r
 }
 
 define i8 @srem_nonneg0_nonnegconst1(i7 %x) {
 ; CHECK-LABEL: @srem_nonneg0_nonnegconst1(
 ; CHECK-NEXT:    [[PX:%.*]] = zext i7 [[X:%.*]] to i8
-; CHECK-NEXT:    [[R:%.*]] = srem i8 [[PX]], 42
+; CHECK-NEXT:    [[R:%.*]] = urem i8 [[PX]], 42
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %px = zext i7 %x to i8
   %r = srem i8 %px, 42
   ret i8 %r
 }
 
+; negative test
+
 define i8 @srem_unknown0_nonneg1(i8 %x, i8 %y) {
 ; CHECK-LABEL: @srem_unknown0_nonneg1(
 ; CHECK-NEXT:    [[PY:%.*]] = lshr i8 [[Y:%.*]], 1
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 [[X:%.*]], [[PY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %py = lshr i8 %y, 1
   %r = srem i8 %x, %py
   ret i8 %r
 }
 
+; negative test
+
 define i8 @srem_nonnegconst0_unknown1(i7 %y) {
 ; CHECK-LABEL: @srem_nonnegconst0_unknown1(
 ; CHECK-NEXT:    [[SY:%.*]] = sext i7 [[Y:%.*]] to i8
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 42, [[SY]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sy = sext i7 %y to i8
   %r = srem i8 42, %sy
   ret i8 %r
 }
 
+; negative test - mul must be 'nsw' to be known non-negative
+
 define i8 @srem_unknown0_nonnegconst1(i8 %x) {
 ; CHECK-LABEL: @srem_unknown0_nonnegconst1(
 ; CHECK-NEXT:    [[SX:%.*]] = mul i8 [[X:%.*]], [[X]]
 ; CHECK-NEXT:    [[R:%.*]] = srem i8 [[SX]], 42
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sx = mul i8 %x, %x
   %r = srem i8 %sx, 42
   ret i8 %r
 }
 
+; x is known non-negative in t block
+
 define i32 @PR57472(i32 %x) {
 ; CHECK-LABEL: @PR57472(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
-; CHECK-NEXT:    [[REM:%.*]] = srem i32 [[X]], 16
+; CHECK-NEXT:    [[REM:%.*]] = urem i32 [[X]], 16
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       f:
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[REM]], [[T]] ], [ 42, [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %cmp = icmp sge i32 %x, 0
   br i1 %cmp, label %t, label %f
 
 t:
   %rem = srem i32 %x, 16
   br label %exit
 
 f:
   br label %exit
 
 exit:
   %cond = phi i32 [ %rem, %t ], [ 42, %f ]
   ret i32 %cond
 }
 
+; x is known non-negative in f block
+
 define i32 @PR57472_alt(i32 %x) {
 ; CHECK-LABEL: @PR57472_alt(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[X:%.*]], 2000000000
 ; CHECK-NEXT:    br i1 [[CMP]], label [[T:%.*]], label [[F:%.*]]
 ; CHECK:       t:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       f:
-; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 16, [[X]]
+; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 16, [[X]]
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ -42, [[T]] ], [ [[DIV]], [[F]] ]
 ; CHECK-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %cmp = icmp ugt i32 %x, 2000000000
   br i1 %cmp, label %t, label %f