[InstCombine] Add frozen for the condition value of SelectInst

[Allen]

Summary

If the condition value of SelectInst may be a poison or undef value,
infer constant range at SelectInst use is incorrect, similar to D143883.

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

[nikic]

It would be better to freeze the operand instead.

[Allen]

address comment

[nikic]

LGTM

[efriedma]

(For future reference, the freeze isn't necessary if the operand is poison; it's only necessary if the operand is undef.)

[Allen]

In D149339#4303335, @efriedma wrote:

(For future reference, the freeze isn't necessary if the operand is poison; it's only necessary if the operand is undef.)

hi, @efriedma, Thanks for your information.

do you mean we'd better check the attribute **noundef ** before adding the **freeze** ? such as  https://alive2.llvm.org/ce/z/2pIqvX, this case isn't necessary to add freeze  ?

[efriedma]

I don't think there's anything to do here at the moment. "noundef" refers to both undef and poison. (Later optimizations will remove the "freeze" if it isn't necessary.)

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

   }
 
   // If the divisor is a sext of a boolean, then the divisor must be max
   // unsigned value (-1). Therefore, the remainder is Op0 unless Op0 is also
   // max unsigned value. In that case, the remainder is 0:
   // urem Op0, (sext i1 X) --> (Op0 == -1) ? 0 : Op0
   Value *X;
   if (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)) {
-    Value *Cmp = Builder.CreateICmpEQ(Op0, ConstantInt::getAllOnesValue(Ty));
-    return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), Op0);
+    Value *FrozenOp0 = Builder.CreateFreeze(Op0, Op0->getName() + ".frozen");
+    Value *Cmp =
+        Builder.CreateICmpEQ(FrozenOp0, ConstantInt::getAllOnesValue(Ty));
+    return SelectInst::Create(Cmp, ConstantInt::getNullValue(Ty), FrozenOp0);
   }
 
   // For "(X + 1) % Op1" and if (X u< Op1) => (X + 1) == Op1 ? 0 : X + 1 .
   if (match(Op0, m_Add(m_Value(X), m_One()))) {
     Value *Val =
         simplifyICmpInst(ICmpInst::ICMP_ULT, X, Op1, SQ.getWithInstruction(&I));
     if (Val && match(Val, m_One())) {
       Value *FrozenOp0 = Builder.CreateFreeze(Op0, Op0->getName() + ".frozen");

llvm/test/Transforms/InstCombine/rem.ll

 ; CHECK-NEXT:    ret i5 [[REM]]
 ;
   %rem = urem i5 %x, -1
   ret i5 %rem
 }
 
 define i8 @urem_with_sext_bool_divisor(i1 %x, i8 %y) {
 ; CHECK-LABEL: @urem_with_sext_bool_divisor(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[REM:%.*]] = select i1 [[TMP1]], i8 0, i8 [[Y]]
+; CHECK-NEXT:    [[Y_FROZEN:%.*]] = freeze i8 [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[Y_FROZEN]], -1
+; CHECK-NEXT:    [[REM:%.*]] = select i1 [[TMP1]], i8 0, i8 [[Y_FROZEN]]
 ; CHECK-NEXT:    ret i8 [[REM]]
 ;
   %s = sext i1 %x to i8
   %rem = urem i8 %y, %s
   ret i8 %rem
 }
 
 define <2 x i8> @urem_with_sext_bool_divisor_vec(<2 x i1> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @urem_with_sext_bool_divisor_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[Y:%.*]], <i8 -1, i8 -1>
-; CHECK-NEXT:    [[REM:%.*]] = select <2 x i1> [[TMP1]], <2 x i8> zeroinitializer, <2 x i8> [[Y]]
+; CHECK-NEXT:    [[Y_FROZEN:%.*]] = freeze <2 x i8> [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[Y_FROZEN]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[REM:%.*]] = select <2 x i1> [[TMP1]], <2 x i8> zeroinitializer, <2 x i8> [[Y_FROZEN]]
 ; CHECK-NEXT:    ret <2 x i8> [[REM]]
 ;
   %s = sext <2 x i1> %x to <2 x i8>
   %rem = urem <2 x i8> %y, %s
   ret <2 x i8> %rem
 }
 
 define <2 x i4> @big_divisor_vec(<2 x i4> %x) {

 ; CHECK-NEXT:    [[S:%.*]] = select i1 [[B:%.*]], i32 12, i32 -3
 ; CHECK-NEXT:    [[R:%.*]] = urem i32 [[X:%.*]], [[S]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %s = select i1 %b, i32 12, i32 -3
   %r = urem i32 %x, %s
   ret i32 %r
 }
+
+; https://alive2.llvm.org/ce/z/bh2KHm
+define <2 x i32> @PR62401(<2 x i1> %x, <2 x i32> %y) {
+; CHECK-LABEL: @PR62401(
+; CHECK-NEXT:    [[Y_FROZEN:%.*]] = freeze <2 x i32> [[Y:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i32> [[Y_FROZEN]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[R:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> zeroinitializer, <2 x i32> [[Y_FROZEN]]
+; CHECK-NEXT:    ret <2 x i32> [[R]]
+;
+  %sext.i1 = sext <2 x i1> %x to <2 x i32>
+  %r = urem <2 x i32> %y, %sext.i1
+  ret <2 x i32> %r
+}

llvm/test/Transforms/InstCombine/shift.ll

 ; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=5032
 define void @ashr_out_of_range(ptr %A) {
 ; CHECK-LABEL: @ashr_out_of_range(
 ; CHECK-NEXT:    [[L:%.*]] = load i177, ptr [[A:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i177 [[L]], -1
 ; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 -1, i64 -2
 ; CHECK-NEXT:    [[G11:%.*]] = getelementptr i177, ptr [[A]], i64 [[TMP2]]
 ; CHECK-NEXT:    [[L7:%.*]] = load i177, ptr [[G11]], align 4
-; CHECK-NEXT:    [[C171:%.*]] = icmp slt i177 [[L7]], 0
-; CHECK-NEXT:    [[C17:%.*]] = select i1 [[TMP1]], i1 [[C171]], i1 false
+; CHECK-NEXT:    [[L7_FROZEN:%.*]] = freeze i177 [[L7]]
+; CHECK-NEXT:    [[C171:%.*]] = icmp slt i177 [[L7_FROZEN]], 0
+; CHECK-NEXT:    [[C17:%.*]] = and i1 [[TMP1]], [[C171]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = sext i1 [[C17]] to i64
 ; CHECK-NEXT:    [[G62:%.*]] = getelementptr i177, ptr [[G11]], i64 [[TMP3]]
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i177 [[L7]], -1
-; CHECK-NEXT:    [[B28:%.*]] = select i1 [[TMP4]], i177 0, i177 [[L7]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i177 [[L7_FROZEN]], -1
+; CHECK-NEXT:    [[B28:%.*]] = select i1 [[TMP4]], i177 0, i177 [[L7_FROZEN]]
 ; CHECK-NEXT:    store i177 [[B28]], ptr [[G62]], align 4
 ; CHECK-NEXT:    ret void
 ;
   %L = load i177, ptr %A
   %B5 = udiv i177 %L, -1
   %B4 = add i177 %B5, -1
   %B2 = add i177 %B4, -1
   %G11 = getelementptr i177, ptr %A, i177 %B2