[LVI][CVP] Don't compute CR at SelectInst Use if Cond value may not be well-defined

[StephenFan]

Summary

If the condition value of SelectInst may be a poison or undef value,
infer constant range at SelectInst use is in correct.

See https://alive2.llvm.org/ce/z/MWMTYn

Fixes: https://github.com/llvm/llvm-project/issues/62200

[nikic]

The tests should all be updated to use noundef, plus one representative test without it.

[StephenFan]

add noundef and add new test.

[nikic]

LGTM

llvm/lib/Analysis/LazyValueInfo.cpp

1670–1673

This issue is only about undef, it does not affect poison. This is why it's mostly a theoretical problem.

llvm/lib/Analysis/LazyValueInfo.cpp

ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U,
   // position where V can be constrained by a select or branch condition.
   const Use *CurrU = &U;
   // TODO: Increase limit?
   const unsigned MaxUsesToInspect = 3;
   for (unsigned I = 0; I < MaxUsesToInspect; ++I) {
     std::optional<ValueLatticeElement> CondVal;
     auto *CurrI = cast<Instruction>(CurrU->getUser());
     if (auto *SI = dyn_cast<SelectInst>(CurrI)) {
+      // If the value is undef, a different value may be chosen in
+      // the select condition and at use.
+      if (!isGuaranteedNotToBeUndefOrPoison(SI->getCondition(), AC))
+        break;
       if (CurrU->getOperandNo() == 1)
         CondVal = getValueFromCondition(V, SI->getCondition(), true);
       else if (CurrU->getOperandNo() == 2)
         CondVal = getValueFromCondition(V, SI->getCondition(), false);
     } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) {
       // TODO: Use non-local query?
       CondVal =
           getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), PHI->getParent());

llvm/test/Transforms/CorrelatedValuePropagation/cond-at-use.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -passes=correlated-propagation < %s | FileCheck %s
 
 declare void @use.i16(i16)
 declare i16 @llvm.usub.sat.i16(i16, i16)
 declare i16 @llvm.uadd.sat.i16(i16, i16)
 declare i16 @llvm.umin.i16(i16, i16)
 declare i16 @llvm.abs.i16(i16, i1)
 
-define i16 @sel_true_cond(i16 %x) {
+define i16 @sel_true_cond(i16 noundef %x) {
 ; CHECK-LABEL: @sel_true_cond(
 ; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i16 [[X]], 10
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[SUB1]], i16 42
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10)
   %cmp = icmp uge i16 %x, 10

 ;
   %sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10)
   call void @use.i16(i16 %sub)
   %cmp = icmp uge i16 %x, 10
   %sel = select i1 %cmp, i16 %sub, i16 42
   ret i16 %sel
 }
 
-define i16 @sel_true_cond_chain_speculatable(i16 %x) {
+define i16 @sel_true_cond_chain_speculatable(i16 noundef %x) {
 ; CHECK-LABEL: @sel_true_cond_chain_speculatable(
 ; CHECK-NEXT:    [[SUB1:%.*]] = add nuw i16 [[X:%.*]], 1
 ; CHECK-NEXT:    [[EXTRA:%.*]] = mul i16 [[SUB1]], 3
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i16 [[X]], -1
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[EXTRA]], i16 42
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %sub = call i16 @llvm.uadd.sat.i16(i16 %x, i16 1)
;
   %sub = call i16 @llvm.uadd.sat.i16(i16 %x, i16 1)
   %extra = mul i16 %sub, 3
   %extra2 = xor i16 %sub, 7
   %cmp = icmp ne i16 %x, -1
   %sel = select i1 %cmp, i16 %extra2, i16 42
   ret i16 %sel
 }
 
-define i16 @sel_false_cond(i16 %x) {
+define i16 @sel_false_cond(i16 noundef %x) {
 ; CHECK-LABEL: @sel_false_cond(
 ; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i16 [[X:%.*]], 10
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X]], 10
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 42, i16 [[SUB1]]
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %sub = call i16 @llvm.usub.sat.i16(i16 %x, i16 10)
   %cmp = icmp ult i16 %x, 10
loop:
   %iv.next = call i16 @llvm.usub.sat.i16(i16 %iv, i16 1)
   %count.next = add i16 %count, 1
   br i1 %cmp, label %exit, label %loop
 
 exit:
   ret i16 %count
 }
 
-define i16 @urem_elide(i16 %x) {
+define i16 @urem_elide(i16 noundef %x) {
 ; CHECK-LABEL: @urem_elide(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X:%.*]], 42
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[X]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %urem = urem i16 %x, 42
   %cmp = icmp ult i16 %x, 42
   %sel = select i1 %cmp, i16 %urem, i16 24
   ret i16 %sel
 }
 
-define i16 @urem_expand(i16 %x) {
+define i16 @urem_expand(i16 noundef %x) {
 ; CHECK-LABEL: @urem_expand(
 ; CHECK-NEXT:    [[X_FROZEN:%.*]] = freeze i16 [[X:%.*]]
 ; CHECK-NEXT:    [[UREM_UREM:%.*]] = sub nuw i16 [[X_FROZEN]], 42
 ; CHECK-NEXT:    [[UREM_CMP:%.*]] = icmp ult i16 [[X_FROZEN]], 42
 ; CHECK-NEXT:    [[UREM:%.*]] = select i1 [[UREM_CMP]], i16 [[X_FROZEN]], i16 [[UREM_UREM]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X]], 84
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %urem = urem i16 %x, 42
   %cmp = icmp ult i16 %x, 84
   %sel = select i1 %cmp, i16 %urem, i16 24
   ret i16 %sel
 }
 
-define i16 @urem_narrow(i16 %x) {
+define i16 @urem_narrow(i16 noundef %x) {
 ; CHECK-LABEL: @urem_narrow(
 ; CHECK-NEXT:    [[UREM_LHS_TRUNC:%.*]] = trunc i16 [[X:%.*]] to i8
 ; CHECK-NEXT:    [[UREM1:%.*]] = urem i8 [[UREM_LHS_TRUNC]], 42
 ; CHECK-NEXT:    [[UREM_ZEXT:%.*]] = zext i8 [[UREM1]] to i16
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X]], 85
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[UREM_ZEXT]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;

 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %urem = urem i16 %x, 42
   %cmp = icmp ult i16 %x, 257
   %sel = select i1 %cmp, i16 %urem, i16 24
   ret i16 %sel
 }
 
-define i16 @srem_elide(i16 %x) {
+define i16 @srem_elide(i16 noundef %x) {
 ; CHECK-LABEL: @srem_elide(
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i16 [[X:%.*]], 42
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i16 [[X]], -42
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[AND]], i16 [[X]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %srem = srem i16 %x, 42
   %cmp1 = icmp slt i16 %x, 42
   %cmp2 = icmp sgt i16 %x, -42
   %and = and i1 %cmp1, %cmp2
   %sel = select i1 %and, i16 %srem, i16 24
   ret i16 %sel
 }
 
-define i16 @srem_narrow(i16 %x) {
+define i16 @srem_narrow(i16 noundef %x) {
 ; CHECK-LABEL: @srem_narrow(
 ; CHECK-NEXT:    [[SREM_LHS_TRUNC:%.*]] = trunc i16 [[X:%.*]] to i8
 ; CHECK-NEXT:    [[SREM1:%.*]] = srem i8 [[SREM_LHS_TRUNC]], 42
 ; CHECK-NEXT:    [[SREM_SEXT:%.*]] = sext i8 [[SREM1]] to i16
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i16 [[X]], 43
 ; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i16 [[X]], -43
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[AND]], i16 [[SREM_SEXT]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %srem = srem i16 %x, 42
   %cmp1 = icmp slt i16 %x, 43
   %cmp2 = icmp sgt i16 %x, -43
   %and = and i1 %cmp1, %cmp2
   %sel = select i1 %and, i16 %srem, i16 24
   ret i16 %sel
 }
 
-define i16 @srem_convert(i16 %x) {
+define i16 @srem_convert(i16 noundef %x) {
 ; CHECK-LABEL: @srem_convert(
 ; CHECK-NEXT:    [[X_NONNEG:%.*]] = sub i16 0, [[X:%.*]]
 ; CHECK-NEXT:    [[SREM1:%.*]] = urem i16 [[X_NONNEG]], 42
 ; CHECK-NEXT:    [[SREM1_NEG:%.*]] = sub i16 0, [[SREM1]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i16 [[X]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM1_NEG]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %srem = srem i16 %x, 42
   %cmp = icmp slt i16 %x, 0
   %sel = select i1 %cmp, i16 %srem, i16 24
   ret i16 %sel
 }
 
-define i16 @sdiv_convert(i16 %x) {
+define i16 @sdiv_convert(i16 noundef %x) {
 ; CHECK-LABEL: @sdiv_convert(
 ; CHECK-NEXT:    [[X_NONNEG:%.*]] = sub i16 0, [[X:%.*]]
 ; CHECK-NEXT:    [[SREM1:%.*]] = udiv i16 [[X_NONNEG]], 42
 ; CHECK-NEXT:    [[SREM1_NEG:%.*]] = sub i16 0, [[SREM1]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i16 [[X]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[SREM1_NEG]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;

 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %min = call i16 @llvm.umin.i16(i16 %x, i16 10)
   %cmp = icmp ule i16 %x, 10
   %sel = select i1 %cmp, i16 %min, i16 42
   ret i16 %sel
 }
 
-define i16 @ashr_convert(i16 %x, i16 %y) {
+define i16 @ashr_convert(i16 noundef %x, i16 %y) {
 ; CHECK-LABEL: @ashr_convert(
 ; CHECK-NEXT:    [[ASHR:%.*]] = lshr i16 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i16 [[X]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[ASHR]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %ashr = ashr i16 %x, %y
   %cmp = icmp sge i16 %x, 0
   %sel = select i1 %cmp, i16 %ashr, i16 24
   ret i16 %sel
 }
 
-define i32 @sext_convert(i16 %x) {
+define i32 @sext_convert(i16 noundef %x) {
 ; CHECK-LABEL: @sext_convert(
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i16 [[X:%.*]] to i32
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i16 [[X]], 0
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i32 [[EXT]], i32 24
 ; CHECK-NEXT:    ret i32 [[SEL]]
 ;
   %ext = sext i16 %x to i32
   %cmp = icmp sge i16 %x, 0

 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %add = add i16 %x, 42
   %cmp = icmp ult i16 %x, 100
   %sel = select i1 %cmp, i16 %add, i16 24
   ret i16 %sel
 }
 
-define i16 @and_elide(i16 %x) {
+define i16 @and_elide(i16 noundef %x) {
 ; CHECK-LABEL: @and_elide(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X:%.*]], 8
 ; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[X]], i16 24
 ; CHECK-NEXT:    ret i16 [[SEL]]
 ;
   %and = and i16 %x, 7
   %cmp = icmp ult i16 %x, 8
   %sel = select i1 %cmp, i16 %and, i16 24
   ret i16 %sel
 }
+
+define i16 @cond_value_may_not_well_defined(i16 %x) {
+; CHECK-LABEL: @cond_value_may_not_well_defined(
+; CHECK-NEXT:    [[AND:%.*]] = and i16 [[X:%.*]], 7
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i16 [[X]], 8
+; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i16 [[AND]], i16 24
+; CHECK-NEXT:    ret i16 [[SEL]]
+;
+  %and = and i16 %x, 7
+  %cmp = icmp ult i16 %x, 8
+  %sel = select i1 %cmp, i16 %and, i16 24
+  ret i16 %sel
+}