[SCCP] Use ranges for predicate info conditions.

[fhahn]

Summary

This patch updates the code that deals with conditions from predicate
info to make use of constant ranges.

For ssa_copy instructions inserted by PredicateInfo, we have 2 ranges:

1. The range of the original value.
2. The range imposed by the linked condition.

1. is known, 2. can be determined using makeAllowedICmpRegion. The

intersection of those ranges is the range for the copy.

With this patch, we get a nice increase in the number of instructions
eliminated by both SCCP and IPSCCP for some benchmarks:

For MultiSource, SPEC2000 & SPEC2006:

Tests: 237
Same hash: 170 (filtered out)
Remaining: 67
Metric: sccp.NumInstRemoved
Program base patch diff
test-suite...Source/Benchmarks/sim/sim.test 10.00 71.00 610.0%
test-suite...CFP2000/177.mesa/177.mesa.test 361.00 1626.00 350.4%
test-suite...encode/alacconvert-encode.test 141.00 602.00 327.0%
test-suite...decode/alacconvert-decode.test 141.00 602.00 327.0%
test-suite...CI_Purple/SMG2000/smg2000.test 1639.00 4093.00 149.7%
test-suite...peg2/mpeg2dec/mpeg2decode.test 75.00 163.00 117.3%
test-suite...T2006/401.bzip2/401.bzip2.test 358.00 513.00 43.3%
test-suite...rks/FreeBench/pifft/pifft.test 11.00 15.00 36.4%
test-suite...langs-C/unix-tbl/unix-tbl.test 4.00 5.00 25.0%
test-suite...lications/sqlite3/sqlite3.test 541.00 667.00 23.3%
test-suite.../CINT2000/254.gap/254.gap.test 243.00 299.00 23.0%
test-suite...ks/Prolangs-C/agrep/agrep.test 25.00 29.00 16.0%
test-suite...marks/7zip/7zip-benchmark.test 1135.00 1304.00 14.9%
test-suite...lications/ClamAV/clamscan.test 1105.00 1268.00 14.8%
test-suite...urce/Applications/lua/lua.test 398.00 436.00 9.5%

Metric: sccp.IPNumInstRemoved
Program base patch diff
test-suite...C/CFP2000/179.art/179.art.test 1.00 3.00 200.0%
test-suite...006/447.dealII/447.dealII.test 429.00 1056.00 146.2%
test-suite...nch/fourinarow/fourinarow.test 3.00 7.00 133.3%
test-suite...CI_Purple/SMG2000/smg2000.test 818.00 1748.00 113.7%
test-suite...ks/McCat/04-bisect/bisect.test 3.00 5.00 66.7%
test-suite...CFP2000/177.mesa/177.mesa.test 165.00 255.00 54.5%
test-suite...ediabench/gsm/toast/toast.test 18.00 27.00 50.0%
test-suite...telecomm-gsm/telecomm-gsm.test 18.00 27.00 50.0%
test-suite...ks/Prolangs-C/agrep/agrep.test 24.00 35.00 45.8%
test-suite...TimberWolfMC/timberwolfmc.test 43.00 62.00 44.2%
test-suite...encode/alacconvert-encode.test 46.00 66.00 43.5%
test-suite...decode/alacconvert-decode.test 46.00 66.00 43.5%
test-suite...langs-C/unix-tbl/unix-tbl.test 12.00 17.00 41.7%
test-suite...peg2/mpeg2dec/mpeg2decode.test 31.00 41.00 32.3%
test-suite.../CINT2000/254.gap/254.gap.test 117.00 154.00 31.6%

[efriedma]

(Lint has a couple formatting suggestions.)

llvm/lib/Transforms/Scalar/SCCP.cpp

1251–1252

"If the original value is a constant we cannot do better" is technically not true; in theory, if we prove a contradiction, the ssa.copy is unreachable. But unlikely to matter in practice, I guess.

1268

Do we want to try to handle the case where we have a constant expression of integer type?

[fhahn]

Use range information only of either operand is a constant range, instead of for all integer types and drop special case preserving original constant.

[fhahn]

clang-format

[fhahn]

llvm/lib/Transforms/Scalar/SCCP.cpp

1251–1252

Agreed, the special case here was not really necessary. I've removed it. Intersecting the constant ranges below should give the same result in practice. I've added a test case with a contradiction (f11_contradiction). I think in those cases, the contradicting compare will get folded to false, and we never branch to the block with the contradiction.

1268

Ah yes, I've change it to use ranges only if either operand is a constant range.

I've added a test with a compare of 2 constant ranges. Currently this just swaps the known values and is not too helpful in that case (f14_constexpr2).

Also, would it be legal to fold something like i1 icmp eq (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @B to i32) to true? If it is, it looks like ConstantExpr currently misses that fold.

[efriedma]

llvm/lib/Transforms/Scalar/SCCP.cpp

1268

I think the order of the conditions might be backwards? Consider if OriginalVal is a ConstantRange, and CondVal is a Constant.

---

I briefly tried the following, and it seems to fold (just passing it to "opt -S"):

@B = global i32 0
@C = global i1 icmp eq (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @B to i32))

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

1268

Err, actually, hmm... in general, there's sort a conflict here between Constant and ConstantRange here; in more complicated cases, you could end up accidentally landing on overdefined by merging a Constant and a ConstantRange.

I guess it's unlikely to matter very much in practice; constant expressions are relatively rare.

[fhahn]

Thank you very much Eli!

llvm/lib/Transforms/Scalar/SCCP.cpp

1268

Yes I think potentially are cases involving constant ranges where we might go to overdefined using ranges unnecessarily. Maybe it would be best to try both and chose the better result, although it sometimes is not clear if a larger constant range or a constant Expr is better for further analysis. I think it would be interesting to follow up on that in future patches.

[efriedma]

Hang on, is this actually safe?

If we compute a predicate based on a possibly-undef value, and branch based on that, does the predicate actually mean anything?

[fhahn]

In D76611#1940012, @efriedma wrote:

Hang on, is this actually safe?

If we compute a predicate based on a possibly-undef value, and branch based on that, does the predicate actually mean anything?

There are 2 cases IIUC that may be undef: the value we derive a bound for and the bound. I think in terms of the bound value, we should be safe, as we will go to overdefined for ranges that are merged with undef and effectively remove the information from the bound.

I think for now it should be safe as well if the value we derive the bound for may be undef, because the only place we actually use range information for simplification is at compares and there we always replace an icmp with a constant.

And I am not sure if it would be safe in general to replace a value with a different value based on range info in any case. E.g. consider

define void @foo(i32 %a) {
entry:
  %bc.1 = icmp ult i32 %a, 15
  br i1 %bc.1, label %true, label %false

true:
  %f.1 = icmp eq i32 %a, 128
  call void @use(i1 %f.1)

  %p.127 = and i32 %a, 15
  call void @use.i32(i32 %p.127)
  ret void

false:
  ret void
}

We can use the range info in the above to remove %f.1, but we cannot use it to remove the %p.127 = and...., as %a could be undef. CVP currently gets this wrong, besides other things. If we want to remove the and, we would need to insert an extra freeze I think.

Does that make sense?

[fhahn]

I also added a set of additional test cases with various combinations of undef in https://reviews.llvm.org/rG081efa7dd084

They are also part of the current diff: llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll

[efriedma]

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable. But it would be more clear if we represented it explicitly in the lattice.

[fhahn]

In D76611#1942381, @efriedma wrote:

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable.

Yep that should be the case.

But it would be more clear if we represented it explicitly in the lattice.

Agreed. I think we should be able to convert singlecrfromundef to something like constantrangeincludingundef. The regular constantrange would mean it is guaranteed to not include undef (would only be able to come from things like phis with all incoming values constants != undef). We can use information from such ranges to replace values with other values (like the and removal). All other ranges should be constantrangeincludingundef, e.g. the and example with a constant and an arbitrary value or the information inferred from bounds. Let me prepare a patch.

[fhahn]

In D76611#1942381, @efriedma wrote:

If I'm understanding correctly, you're saying that SCCP doesn't care about the difference between constantrange and a hypothetical constantrangefromundef, therefore it's fine if the value is actually undef? I guess that's reasonable. But it would be more clear if we represented it explicitly in the lattice.

I've put up D76931. It is based on the assumption that we have to assume arbitrary values like function arguments may be undef. I did not find that spelled out anywhere explicitly, so I might be wrong there.

[fhahn]

Rebased after adding constantrange_including_undef to ValueLattice.

I think we can create ranges that do not include undef from branch conditions given the recent clarification to the langref. I update the code to make that explicit and added a comment on the reasoning behind it.

[efriedma]

Code looks fine.

I'm a little concerned that the recent clarification in LangRef doesn't actually match the code at the moment, so this could end up exposing an issue with some other transform. (grep for Attribute::SanitizeMemory.)

[fhahn]

In D76611#1955626, @efriedma wrote:

Code looks fine.

I'm a little concerned that the recent clarification in LangRef doesn't actually match the code at the moment, so this could end up exposing an issue with some other transform. (grep for Attribute::SanitizeMemory.)

I assume you are referring to code in other passes, right? I think we probably have code assuming both the new behaviour and the old one and we somehow have to consolidate the code base. Probably best to discuss that at the langref change/llvm-Dev?

[efriedma]

Yes, code in other passes, particularly SimplifyCFG.

[fhahn]

In D76611#1955707, @efriedma wrote:

Yes, code in other passes, particularly SimplifyCFG.

Thanks, I think I know what you mean now!

Making branch on undef UB kind of trades of making it easier to assume ranges (without undef) from branch conditions, but it makes it harder to introduce branches that where not there before, as it may introduce undef. This seems tricky. As you pointed out, the sanitizer attribute has some early exits for cases that might introduce branches on poison (but in most contexts that could also be undef). I'll raise it in D76973. It's probably best to discuss it there and maybe extend to llvm-dev.

Regardless of the outcome, I think the patch should be fine either way: only whether the range based on the condition can include undef or not is impacted by the outcome of that discussion. As ranges are only used to simplify conditions (which should be fine either way), switching to include undef for the new ranges by default should not have any functional impact on the current transformations.

I've updated the code to mark new ranges as potentially including undef. That should be the conservative choice and correct even if branch on undef is not UB. I've also added a TODO to flip the default once more other parts of the optimizer respect 'branch on undef is UB'.

Do you think this is conservative enough to get this in, even with the open questions remaining around 'branch on undef is UB'?

[efriedma]

That seems fine, yes. LGTM

llvm/lib/Transforms/Scalar/SCCP.cpp

 //===- SCCP.cpp - Sparse Conditional Constant Propagation -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //

 }
 
 void SCCPSolver::handleCallResult(CallSite CS) {
   Function *F = CS.getCalledFunction();
   Instruction *I = CS.getInstruction();
 
   if (auto *II = dyn_cast<IntrinsicInst>(I)) {
     if (II->getIntrinsicID() == Intrinsic::ssa_copy) {
-      if (isOverdefined(ValueState[I]))
-        return (void)markOverdefined(I);
-
-      auto *PI = getPredicateInfoFor(I);
-      if (!PI)
+      if (ValueState[I].isOverdefined())
         return;
 
       Value *CopyOf = I->getOperand(0);
-      auto *PBranch = dyn_cast<PredicateBranch>(PI);
-      if (!PBranch) {
+      auto *PI = getPredicateInfoFor(I);
+      auto *PBranch = dyn_cast_or_null<PredicateBranch>(PI);
+      if (!PI || !PBranch) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
-      Value *Cond = PBranch->Condition;
-
       // Everything below relies on the condition being a comparison.
-      auto *Cmp = dyn_cast<CmpInst>(Cond);
+      auto *Cmp = dyn_cast<CmpInst>(PBranch->Condition);
       if (!Cmp) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
       Value *CmpOp0 = Cmp->getOperand(0);
       Value *CmpOp1 = Cmp->getOperand(1);
       if (CopyOf != CmpOp0 && CopyOf != CmpOp1) {
         mergeInValue(ValueState[I], I, getValueState(CopyOf));
         return;
       }
 
-      if (CmpOp0 != CopyOf)
+      auto Pred = Cmp->getPredicate();
+      if (CmpOp0 != CopyOf) {
         std::swap(CmpOp0, CmpOp1);
+        Pred = Cmp->getSwappedPredicate();
+      }
 
-      ValueLatticeElement OriginalVal = getValueState(CopyOf);
-      ValueLatticeElement EqVal = getValueState(CmpOp1);
-      ValueLatticeElement &IV = ValueState[I];
-      if (PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_EQ) {
+      // Wait until CmpOp1 is resolved.
+      if (getValueState(CmpOp1).isUnknown()) {
         addAdditionalUser(CmpOp1, I);
-        if (isConstant(OriginalVal))
-          mergeInValue(IV, I, OriginalVal);
-        else
-          mergeInValue(IV, I, EqVal);
         return;
       }
-      if (!PBranch->TrueEdge && Cmp->getPredicate() == CmpInst::ICMP_NE) {
+
+      if (!PBranch->TrueEdge)
+        Pred = CmpInst::getInversePredicate(Pred);
+
+      ValueLatticeElement CondVal = getValueState(CmpOp1);
+      ValueLatticeElement &IV = ValueState[I];
+      ValueLatticeElement OriginalVal = getValueState(CopyOf);
+      if (CondVal.isConstantRange() || OriginalVal.isConstantRange()) {
+        auto NewCR =
+            ConstantRange::getFull(DL.getTypeSizeInBits(CopyOf->getType()));
+
+        // Get the range imposed by the condition.
+        if (CondVal.isConstantRange())
+          NewCR = ConstantRange::makeAllowedICmpRegion(
+              Pred, CondVal.getConstantRange());
+
+        // Combine range info for the original value with the new range from the
+        // condition.
+        auto OriginalCR = OriginalVal.isConstantRange()
+                              ? OriginalVal.getConstantRange()
+                              : ConstantRange::getFull(
+                                    DL.getTypeSizeInBits(CopyOf->getType()));
+        NewCR = NewCR.intersectWith(OriginalCR);
+
         addAdditionalUser(CmpOp1, I);
-        if (isConstant(OriginalVal))
-          mergeInValue(IV, I, OriginalVal);
-        else
-          mergeInValue(IV, I, EqVal);
+        // The new range is based on a branch condition. That guarantees that
+        // neither of the compare operands can be undef in the branch targets,
+        // unless we have conditions that are always true/false (e.g. icmp ule
+        // i32, %a, i32_max). For the latter overdefined/empty range will be
+        // inferred, but the branch will get folded accordingly anyways.
+        mergeInValue(
+            IV, I,
+            ValueLatticeElement::getRange(NewCR, /*MayIncludeUndef=*/false));
+        return;
+      } else if (Pred == CmpInst::ICMP_EQ && CondVal.isConstant()) {
+        // For non-integer values or integer constant expressions, only
+        // propagate equal constants.
+        addAdditionalUser(CmpOp1, I);
+        mergeInValue(IV, I, CondVal);
         return;
       }
 
       return (void)mergeInValue(IV, I, getValueState(CopyOf));
     }
   }
 
   // The common case is that we aren't tracking the callee, either because we

llvm/test/Transforms/SCCP/conditions-ranges-with-undef.ll

 ; %a.127 = and ... in the true block, as %a could be undef.
 define void @val_undef_range() {
 ; CHECK-LABEL: @val_undef_range(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = add i32 undef, 0
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ult i32 [[A]], 127
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[A]], 128
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[A_127:%.*]] = and i32 [[A]], 127
 ; CHECK-NEXT:    call void @use.i32(i32 [[A_127]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = add i32 undef, 0

 ; CHECK:       inc1:
 ; CHECK-NEXT:    br label [[IF:%.*]]
 ; CHECK:       inc2:
 ; CHECK-NEXT:    br label [[IF]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[TRUE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    call void @use(i1 false)
-; CHECK-NEXT:    call void @use.i32(i32 10)
+; CHECK-NEXT:    [[P_127:%.*]] = and i32 10, 127
+; CHECK-NEXT:    call void @use.i32(i32 [[P_127]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
 
   br i1 %cond, label %inc1, label %inc2
 
 inc1:
   br label %if

 ; CHECK-NEXT:    br label [[IF:%.*]]
 ; CHECK:       inc2:
 ; CHECK-NEXT:    br label [[IF]]
 ; CHECK:       if:
 ; CHECK-NEXT:    [[P:%.*]] = phi i32 [ [[A_127]], [[INC1]] ], [ undef, [[INC2]] ]
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ult i32 [[P]], 100
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[P]], 128
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[P_127:%.*]] = and i32 [[P]], 127
 ; CHECK-NEXT:    call void @use.i32(i32 [[P_127]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.127 = and i32 %a, 127

 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[PRED:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[PRED]]
 ; CHECK:       pred:
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ugt i32 [[A:%.*]], 10
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[A]], 5
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ne i32 [[A]], 5
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[A_127:%.*]] = and i32 [[A]], 127
 ; CHECK-NEXT:    call void @use.i32(i32 [[A_127]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br i1 %cond, label %bb1, label %bb2

llvm/test/Transforms/SCCP/conditions-ranges.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -ipsccp -S | FileCheck %s
 
 declare void @use(i1)
 
 define void @f1(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A_255:%.*]] = and i32 [[A:%.*]], 255
 ; CHECK-NEXT:    [[A_2:%.*]] = add i32 [[A_255]], 20
 ; CHECK-NEXT:    [[BC:%.*]] = icmp ugt i32 [[B:%.*]], [[A_2]]
 ; CHECK-NEXT:    br i1 [[BC]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[F_3:%.*]] = icmp ult i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i32 [[B]], 5
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[B]], 255
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
-; CHECK-NEXT:    [[F_4:%.*]] = icmp eq i32 [[B]], 276
-; CHECK-NEXT:    call void @use(i1 [[F_4]])
-; CHECK-NEXT:    [[F_5:%.*]] = icmp ugt i32 [[B]], 275
-; CHECK-NEXT:    call void @use(i1 [[F_5]])
-; CHECK-NEXT:    [[T_3:%.*]] = icmp ne i32 [[B]], 276
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
-; CHECK-NEXT:    [[T_4:%.*]] = icmp ule i32 [[B]], 275
-; CHECK-NEXT:    call void @use(i1 [[T_4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp eq i32 [[B]], 275
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a.255 = and i32 %a, 255

 ; CHECK-NEXT:    [[A_255:%.*]] = and i32 [[A:%.*]], 255
 ; CHECK-NEXT:    [[A_2:%.*]] = add i32 [[A_255]], 20
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ugt i32 [[B:%.*]], [[A_2]]
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
 ; CHECK-NEXT:    [[BC_2:%.*]] = icmp ult i32 [[B]], 255
 ; CHECK-NEXT:    br i1 [[BC_2]], label [[TRUE_2:%.*]], label [[FALSE_2:%.*]]
 ; CHECK:       true.2:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[F_3:%.*]] = icmp ult i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
-; CHECK-NEXT:    [[F_4:%.*]] = icmp eq i32 [[B]], 255
-; CHECK-NEXT:    call void @use(i1 [[F_4]])
-; CHECK-NEXT:    [[F_5:%.*]] = icmp ugt i32 [[B]], 255
-; CHECK-NEXT:    call void @use(i1 [[F_5]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i32 [[B]], 5
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
-; CHECK-NEXT:    [[T_3:%.*]] = icmp ult i32 [[B]], 255
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
-; CHECK-NEXT:    [[T_4:%.*]] = icmp ne i32 [[B]], 300
-; CHECK-NEXT:    call void @use(i1 [[T_4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[B]], 34
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false.2:
-; CHECK-NEXT:    [[F_6:%.*]] = icmp eq i32 [[B]], 254
-; CHECK-NEXT:    call void @use(i1 [[F_6]])
-; CHECK-NEXT:    [[F_7:%.*]] = icmp ult i32 [[B]], 255
-; CHECK-NEXT:    call void @use(i1 [[F_7]])
-; CHECK-NEXT:    [[T_5:%.*]] = icmp ne i32 [[B]], 254
-; CHECK-NEXT:    call void @use(i1 [[T_5]])
-; CHECK-NEXT:    [[T_6:%.*]] = icmp uge i32 [[B]], 255
-; CHECK-NEXT:    call void @use(i1 [[T_6]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp eq i32 [[B]], 255
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ne i32 [[B]], 275
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;

 
 ; Test with with nested conditions where the second conditions is more limiting than the first one.
 define void @f9_nested_conds(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f9_nested_conds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp ugt i32 [[B:%.*]], 10
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[B]], 0
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[B]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i32 [[B]], 5
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ne i32 [[B]], 10
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[B]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[B]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[BC_2:%.*]] = icmp ugt i32 [[B]], 20
 ; CHECK-NEXT:    br i1 [[BC_2]], label [[TRUE_2:%.*]], label [[FALSE_2:%.*]]
 ; CHECK:       true.2:
-; CHECK-NEXT:    [[F_3:%.*]] = icmp eq i32 [[B]], 11
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
-; CHECK-NEXT:    [[F_4:%.*]] = icmp eq i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[F_4]])
-; CHECK-NEXT:    [[T_3:%.*]] = icmp ugt i32 [[B]], 11
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
-; CHECK-NEXT:    [[T_4:%.*]] = icmp ne i32 [[B]], 20
-; CHECK-NEXT:    call void @use(i1 [[T_4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp eq i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ugt i32 [[B]], 21
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ugt i32 [[B]], 34
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false.2:
-; CHECK-NEXT:    [[F_5:%.*]] = icmp eq i32 [[B]], 21
-; CHECK-NEXT:    call void @use(i1 [[F_5]])
-; CHECK-NEXT:    [[F_6:%.*]] = icmp ugt i32 [[B]], 21
-; CHECK-NEXT:    call void @use(i1 [[F_6]])
-; CHECK-NEXT:    [[F_7:%.*]] = icmp ne i32 [[B]], 5
-; CHECK-NEXT:    call void @use(i1 [[F_7]])
-; CHECK-NEXT:    [[T_5:%.*]] = icmp ne i32 [[B]], 21
-; CHECK-NEXT:    call void @use(i1 [[T_5]])
-; CHECK-NEXT:    [[T_6:%.*]] = icmp ult i32 [[B]], 21
-; CHECK-NEXT:    call void @use(i1 [[T_6]])
-; CHECK-NEXT:    [[T_7:%.*]] = icmp ne i32 [[B]], 5
-; CHECK-NEXT:    call void @use(i1 [[T_7]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp eq i32 [[B]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    [[C_7:%.*]] = icmp ne i32 [[B]], 15
 ; CHECK-NEXT:    call void @use(i1 [[C_7]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;

 
 ; Test with with nested conditions where the second conditions is more limiting than the first one.
 define void @f10_cond_does_not_restrict_range(i32 %a, i32 %b) {
 ; CHECK-LABEL: @f10_cond_does_not_restrict_range(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B_255:%.*]] = and i32 [[B:%.*]], 255
 ; CHECK-NEXT:    br label [[TRUE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 [[B_255]], 256
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 [[B_255]], 300
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
-; CHECK-NEXT:    [[T_1:%.*]] = icmp ult i32 [[B_255]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
-; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i32 [[B_255]], 300
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
-; CHECK-NEXT:    [[T_3:%.*]] = icmp ne i32 [[B_255]], 256
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
-; CHECK-NEXT:    [[T_4:%.*]] = icmp ne i32 [[B_255]], 300
-; CHECK-NEXT:    call void @use(i1 [[T_4]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp eq i32 [[B_255]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[B_255]], 30
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %b.255 = and i32 %b, 255

 @B = global i32 17
 
 define void @f13_constexpr1() {
 ; CHECK-LABEL: @f13_constexpr1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[BC_1:%.*]] = icmp eq i32 add (i32 ptrtoint (i32* @A to i32), i32 10), 55
 ; CHECK-NEXT:    br i1 [[BC_1]], label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    [[F_1:%.*]] = icmp eq i32 add (i32 ptrtoint (i32* @A to i32), i32 10), 10
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
-; CHECK-NEXT:    [[F_2:%.*]] = icmp eq i32 add (i32 ptrtoint (i32* @A to i32), i32 10), 55
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = add i32 ptrtoint (i32* @A to i32), 10
   %bc.1 = icmp eq i32 %a, 55
   br i1 %bc.1, label %true, label %false

 }
 
 ; TODO: can we fold the compares in the true block?
 define void @f14_constexpr2() {
 ; CHECK-LABEL: @f14_constexpr2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 icmp eq (i32 ptrtoint (i32* @A to i32), i32 ptrtoint (i32* @B to i32)), label [[TRUE:%.*]], label [[FALSE:%.*]]
 ; CHECK:       true:
-; CHECK-NEXT:    call void @use(i1 icmp ne (i32 ptrtoint (i32* @A to i32), i32 ptrtoint (i32* @B to i32)))
-; CHECK-NEXT:    call void @use(i1 icmp eq (i32 ptrtoint (i32* @A to i32), i32 ptrtoint (i32* @B to i32)))
+; CHECK-NEXT:    call void @use(i1 icmp ne (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @A to i32)))
+; CHECK-NEXT:    call void @use(i1 icmp eq (i32 ptrtoint (i32* @B to i32), i32 ptrtoint (i32* @A to i32)))
 ; CHECK-NEXT:    ret void
 ; CHECK:       false:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %a = add i32 ptrtoint (i32* @A to i32), 0
   %b = add i32 ptrtoint (i32* @B to i32), 0
   %bc.1 = icmp eq i32 %a, %b

 
 ; Same as @udiv_1, but with the condition switched.
 define i32 @udiv_2(i64 %sz) {
 ; CHECK-LABEL: @udiv_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[SZ:%.*]], 4088
 ; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
 ; CHECK:       cond.true:
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i64 4088, [[SZ]]
 ; CHECK-NEXT:    br label [[COND_END]]
 ; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i64 [ [[DIV]], [[COND_TRUE]] ], [ 1, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[COND:%.*]] = phi i64 [ 0, [[COND_TRUE]] ], [ 1, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[CONV:%.*]] = trunc i64 [[COND]] to i32
 ; CHECK-NEXT:    ret i32 [[CONV]]
 ;
 entry:
   %cmp = icmp ugt i64 %sz, 4088
   br i1 %cmp, label %cond.true, label %cond.end
 
 cond.true:                                        ; preds = %entry
   %div = udiv i64 4088, %sz
   br label %cond.end
 
 cond.end:                                         ; preds = %entry, %cond.true
   %cond = phi i64 [ %div, %cond.true ], [ 1, %entry ]
   %conv = trunc i64 %cond to i32
   ret i32 %conv
 }

llvm/test/Transforms/SCCP/ip-constant-ranges.ll

 
 end:
   %res = phi i32 [ 0, %entry], [ 1, %if.true ]
   %call1 = tail call i32 @f3(i32 %res)
   ret i32 2
 }
 
 ; CHECK-LABEL: f4
-; CHECK: %cmp = icmp sgt i32 %x, 300
-; CHECK: %res = select i1 %cmp, i32 1, i32 2
-; CHECK: ret i32 %res
+; CHECK:  ret i32 undef
 define internal i32 @f4(i32 %x) {
 entry:
   %cmp = icmp sgt i32 %x, 300
   %res = select i1 %cmp, i32 1, i32 2
   ret i32 %res
 }
 
-; ICmp could introduce bounds on ConstantRanges.
+; ICmp introduces bounds on ConstantRanges.
 define i32 @caller3(i32 %x) {
+; CHECK-LABEL: define i32 @caller3(i32 %x)
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %res = phi i32 [ 0, %entry ], [ 1, %if.true ]
+; CHECK-NEXT:    ret i32 %res
+;
 entry:
   %cmp = icmp sgt i32 %x, 300
   br i1 %cmp, label %if.true, label %end
 
 if.true:
   %x.1 = tail call i32 @f4(i32 %x)
   br label %end