[InstSimplify] Fold out-of-bounds shift to poison

[nikic]

Summary

Make InstSimplify return poison rather than undef for out-of-bounds shifts, as specified by LandRef:

If op2 is (statically or dynamically) equal to or larger than the number of bits in op1, this instruction returns a poison value.

[nikic]

llvm/test/Transforms/InstCombine/shift.ll

1723

A peculiar regression. Not sure how this folded before, but we're clearly missing a fold here: https://llvm.godbolt.org/z/89bah8 Poison can fold to poison: https://alive2.llvm.org/ce/z/7Nwdri Undef can fold to base pointer: https://alive2.llvm.org/ce/z/y6NLvJ Undef can't fold to undef: https://alive2.llvm.org/ce/z/emLp_H

[aqjune]

llvm/test/Transforms/InstCombine/shift.ll

1723

The source program looks really interesting - it has gep with i1 index..!
I guess %G18 should have been folded like this:
gep %A2, i1 %C8 -> gep %A2, i1 undef -> gep %A2, i64 0 (by constfold sext undef) -> gep %A2
With poison, constfold sext poison is poison, hence it resulted in here.
I'll make a patch that makes gep poison -> poison.

[aqjune]

llvm/test/Transforms/InstCombine/shift.ll

1723

It should work now: https://github.com/llvm/llvm-project/commit/f665a8c5b8b42d88f89e1a3594b7d410ef206c32

[nikic]

Rebase over new gep poison fold.

[aqjune]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
                                unsigned MaxRecurse) {
   return simplifyRem(Instruction::URem, Op0, Op1, Q, MaxRecurse);
 }
 
 Value *llvm::SimplifyURemInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::SimplifyURemInst(Op0, Op1, Q, RecursionLimit);
 }
 
-/// Returns true if a shift by \c Amount always yields undef.
-static bool isUndefShift(Value *Amount, const SimplifyQuery &Q) {
+/// Returns true if a shift by \c Amount always yields poison.
+static bool isPoisonShift(Value *Amount, const SimplifyQuery &Q) {
   Constant *C = dyn_cast<Constant>(Amount);
   if (!C)
     return false;
 
-  // X shift by undef -> undef because it may shift by the bitwidth.
+  // X shift by undef -> poison because it may shift by the bitwidth.
   if (Q.isUndefValue(C))
     return true;
 
   // Shifting by the bitwidth or more is undefined.
   if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
     if (CI->getValue().getLimitedValue() >=
         CI->getType()->getScalarSizeInBits())
       return true;
 
   // If all lanes of a vector shift are undefined the whole shift is.
   if (isa<ConstantVector>(C) || isa<ConstantDataVector>(C)) {
     for (unsigned I = 0,
                   E = cast<FixedVectorType>(C->getType())->getNumElements();
          I != E; ++I)
-      if (!isUndefShift(C->getAggregateElement(I), Q))
+      if (!isPoisonShift(C->getAggregateElement(I), Q))
         return false;
     return true;
   }
 
   return false;
 }
 
 /// Given operands for an Shl, LShr or AShr, see if we can fold the result.
static Value *SimplifyShift(Instruction::BinaryOps Opcode, Value *Op0,
   // Shift-by-sign-extended bool must be shift-by-0 because shift-by-all-ones
   // would be poison.
   Value *X;
   if (match(Op1, m_Zero()) ||
       (match(Op1, m_SExt(m_Value(X))) && X->getType()->isIntOrIntVectorTy(1)))
     return Op0;
 
   // Fold undefined shifts.
-  if (isUndefShift(Op1, Q))
-    return UndefValue::get(Op0->getType());
+  if (isPoisonShift(Op1, Q))
+    return PoisonValue::get(Op0->getType());
 
   // If the operation is with the result of a select instruction, check whether
   // operating on either branch of the select always yields the same value.
   if (isa<SelectInst>(Op0) || isa<SelectInst>(Op1))
     if (Value *V = ThreadBinOpOverSelect(Opcode, Op0, Op1, Q, MaxRecurse))
       return V;
 
   // If the operation is with the result of a phi instruction, check whether
   // operating on all incoming values of the phi always yields the same value.
   if (isa<PHINode>(Op0) || isa<PHINode>(Op1))
     if (Value *V = ThreadBinOpOverPHI(Opcode, Op0, Op1, Q, MaxRecurse))
       return V;
 
   // If any bits in the shift amount make that value greater than or equal to
   // the number of bits in the type, the shift is undefined.
   KnownBits Known = computeKnownBits(Op1, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
   if (Known.One.getLimitedValue() >= Known.getBitWidth())
-    return UndefValue::get(Op0->getType());
+    return PoisonValue::get(Op0->getType());
 
   // If all valid bits in the shift amount are known zero, the first operand is
   // unchanged.
   unsigned NumValidShiftBits = Log2_32_Ceil(Known.getBitWidth());
   if (Known.countMinTrailingZeros() >= NumValidShiftBits)
     return Op0;
 
   return nullptr;

llvm/test/Transforms/InstCombine/add-shl-sdiv-to-srem.ll

;
   %sd = sdiv <3 x i8> %x, <i8 -5, i8 -5, i8 -5>
   %sl = shl <3 x i8> %sd, <i8 2, i8 2, i8 2>
   %rz = add <3 x i8> %sl, %x
   ret <3 x i8> %rz
 }
 
 define <2 x i64> @add-shl-sdiv-negative4(<2 x i64> %x) {
 ; CHECK-LABEL: @add-shl-sdiv-negative4(
-; CHECK-NEXT:    ret <2 x i64> undef
+; CHECK-NEXT:    ret <2 x i64> poison
 ;
   %sd = sdiv <2 x i64> %x, <i64 32, i64 32>
   %sl = shl <2 x i64> %sd, <i64 -5, i64 -5>
   %rz = add <2 x i64> %sl, %x
   ret <2 x i64> %rz
 }
 
 ; Vectors with undef values

llvm/test/Transforms/InstCombine/out-of-bounds-indexes.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 ; Check that we don't crash on unreasonable constant indexes
 
 define i32 @test_out_of_bounds(i32 %a, i1 %x, i1 %y) {
 ; CHECK-LABEL: @test_out_of_bounds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], 3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 undef)
+; CHECK-NEXT:    tail call void @llvm.assume(i1 poison)
 ; CHECK-NEXT:    ret i32 [[AND1]]
 ;
 entry:
   %and1 = and i32 %a, 3
   %B = lshr i32 %and1, -2147483648
   %cmp = icmp eq i32 %B, 1
   tail call void @llvm.assume(i1 %cmp)
   ret i32 %and1
 }
 
 define i128 @test_non64bit(i128 %a) {
 ; CHECK-LABEL: @test_non64bit(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i128 [[A:%.*]], 3
-; CHECK-NEXT:    tail call void @llvm.assume(i1 undef)
+; CHECK-NEXT:    tail call void @llvm.assume(i1 poison)
 ; CHECK-NEXT:    ret i128 [[AND1]]
 ;
   %and1 = and i128 %a, 3
   %B = lshr i128 %and1, -1
   %cmp = icmp eq i128 %B, 1
   tail call void @llvm.assume(i1 %cmp)
   ret i128 %and1
 }

llvm/test/Transforms/InstCombine/phi-shifts.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 ; OSS Fuzz: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=15217
 define i64 @fuzz15217(i1 %cond, i8* %Ptr, i64 %Val) {
 ; CHECK-LABEL: @fuzz15217(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[END:%.*]], label [[TWO:%.*]]
 ; CHECK:       two:
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
 entry:
   br i1 %cond, label %end, label %two
 
 two:
   br label %end
 
 end:
   %tmp869.0 = phi i128 [ 0, %entry ], [ 18446744073709551616, %two ]
   %tmp29 = lshr i128 %tmp869.0, 64
   %B1 = lshr i128 %tmp29, 170141183460469231731687303715884105727
   %tmp30 = trunc i128 %B1 to i64
   ret i64 %tmp30
 }

llvm/test/Transforms/InstCombine/shift.ll

bb11:                                             ; preds = %bb8
   br i1 undef, label %bb1, label %bb12
 
 bb12:                                             ; preds = %bb11, %bb8, %bb
   ret void
 }
 
 define i32 @test62(i32 %a) {
 ; CHECK-LABEL: @test62(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %b = ashr i32 %a, 32  ; shift all bits out
   ret i32 %b
 }
 
 define <4 x i32> @test62_splat_vector(<4 x i32> %a) {
 ; CHECK-LABEL: @test62_splat_vector(
-; CHECK-NEXT:    ret <4 x i32> undef
+; CHECK-NEXT:    ret <4 x i32> poison
 ;
   %b = ashr <4 x i32> %a, <i32 32, i32 32, i32 32, i32 32>  ; shift all bits out
   ret <4 x i32> %b
 }
 
 define <4 x i32> @test62_non_splat_vector(<4 x i32> %a) {
 ; CHECK-LABEL: @test62_non_splat_vector(
 ; CHECK-NEXT:    [[B:%.*]] = ashr <4 x i32> [[A:%.*]], <i32 32, i32 0, i32 1, i32 2>
;
   %B1 = udiv i177 %B10, %B6
   ret i177 %B1
 }
 
 ; OSS Fuzz #26716
 ; https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=26716
 define i177 @lshr_out_of_range2(i177 %Y, i177** %A2) {
 ; CHECK-LABEL: @lshr_out_of_range2(
-; CHECK-NEXT:    store i177** [[A2:%.*]], i177*** undef, align 8
 ; CHECK-NEXT:    ret i177 0
 ;
   %B5 = udiv i177 %Y, -1
   %B = sdiv i177 %B5, -1
   %B4 = add i177 %B5, %B
   %B2 = add i177 %B4, -1
   %B6 = mul i177 %B5, %B2
   %B12 = lshr i177 %Y, %B6
   %C8 = icmp ugt i177 %B12, %B4

llvm/test/Transforms/InstSimplify/shift-knownbits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 ; If any bits of the shift amount are known to make it exceed or equal
 ; the number of bits in the type, the shift causes undefined behavior.
 
 define i32 @shl_amount_is_known_bogus(i32 %a, i32 %b) {
 ; CHECK-LABEL: @shl_amount_is_known_bogus(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %or = or i32 %b, 32
   %shl = shl i32 %a, %or
   ret i32 %shl
 }
 
 ; Check some weird types and the other shift ops.
 
 define i31 @lshr_amount_is_known_bogus(i31 %a, i31 %b) {
 ; CHECK-LABEL: @lshr_amount_is_known_bogus(
-; CHECK-NEXT:    ret i31 undef
+; CHECK-NEXT:    ret i31 poison
 ;
   %or = or i31 %b, 31
   %shr = lshr i31 %a, %or
   ret i31 %shr
 }
 
 define i33 @ashr_amount_is_known_bogus(i33 %a, i33 %b) {
 ; CHECK-LABEL: @ashr_amount_is_known_bogus(
-; CHECK-NEXT:    ret i33 undef
+; CHECK-NEXT:    ret i33 poison
 ;
   %or = or i33 %b, 33
   %shr = ashr i33 %a, %or
   ret i33 %shr
 }
 
 
 ; If all valid bits of the shift amount are known 0, there's no shift.
;
   ret i9 %shl
 }
 
 
 ; For vectors, we need all scalar elements to meet the requirements to optimize.
 
 define <2 x i32> @ashr_vector_bogus(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @ashr_vector_bogus(
-; CHECK-NEXT:    ret <2 x i32> undef
+; CHECK-NEXT:    ret <2 x i32> poison
 ;
   %or = or <2 x i32> %b, <i32 32, i32 32>
   %shr = ashr <2 x i32> %a, %or
   ret <2 x i32> %shr
 }
 
 ; FIXME: This is undef, but computeKnownBits doesn't handle the union.
 define <2 x i32> @shl_vector_bogus(<2 x i32> %a, <2 x i32> %b) {

llvm/test/Transforms/InstSimplify/shift.ll

 ; CHECK-NEXT:    ret <2 x i141> zeroinitializer
 ;
   %B = shl <2 x i141> <i141 undef, i141 0>, %X
   ret <2 x i141> %B
 }
 
 define i55 @lshr_by_bitwidth(i55 %A) {
 ; CHECK-LABEL: @lshr_by_bitwidth(
-; CHECK-NEXT:    ret i55 undef
+; CHECK-NEXT:    ret i55 poison
 ;
   %B = lshr i55 %A, 55
   ret i55 %B
 }
 
 define i32 @shl_by_bitwidth(i32 %A) {
 ; CHECK-LABEL: @shl_by_bitwidth(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %B = shl i32 %A, 32
   ret i32 %B
 }
 
 define <4 x i32> @lshr_by_bitwidth_splat(<4 x i32> %A) {
 ; CHECK-LABEL: @lshr_by_bitwidth_splat(
-; CHECK-NEXT:    ret <4 x i32> undef
+; CHECK-NEXT:    ret <4 x i32> poison
 ;
   %B = lshr <4 x i32> %A, <i32 32, i32 32, i32 32, i32 32>     ;; shift all bits out
   ret <4 x i32> %B
 }
 
 define <4 x i32> @lshr_by_0_splat(<4 x i32> %A) {
 ; CHECK-LABEL: @lshr_by_0_splat(
 ; CHECK-NEXT:    ret <4 x i32> [[A:%.*]]
 ;
   %B = lshr <4 x i32> %A, zeroinitializer
   ret <4 x i32> %B
 }
 
 define <4 x i32> @shl_by_bitwidth_splat(<4 x i32> %A) {
 ; CHECK-LABEL: @shl_by_bitwidth_splat(
-; CHECK-NEXT:    ret <4 x i32> undef
+; CHECK-NEXT:    ret <4 x i32> poison
 ;
   %B = shl <4 x i32> %A, <i32 32, i32 32, i32 32, i32 32>     ;; shift all bits out
   ret <4 x i32> %B
 }
 
 define i32 @ashr_undef() {
 ; CHECK-LABEL: @ashr_undef(
 ; CHECK-NEXT:    ret i32 0
;
   %tmp1 = zext <2 x i32> %a to <2 x i64>
   %tmp2 = zext <2 x i32> %b to <2 x i64>
   %tmp3 = shl nuw <2 x i64> %tmp1, <i64 31, i64 31>
   %tmp4 = or <2 x i64> %tmp2, %tmp3
   %tmp5 = lshr <2 x i64> %tmp4, <i64 31, i64 31>
   ret <2 x i64> %tmp5
 }
 
-; TOOD: these should be poison
-
 define i32 @poison(i32 %x) {
 ; CHECK-LABEL: @poison(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %v = lshr i32 %x, poison
   ret i32 %v
 }
 
 define i32 @poison2(i32 %x) {
 ; CHECK-LABEL: @poison2(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %v = ashr i32 %x, poison
   ret i32 %v
 }
 
 define i32 @poison3(i32 %x) {
 ; CHECK-LABEL: @poison3(
-; CHECK-NEXT:    ret i32 undef
+; CHECK-NEXT:    ret i32 poison
 ;
   %v = shl i32 %x, poison
   ret i32 %v
 }
 
+; TODO: these should be poison
+
 define i32 @poison4(i32 %x) {
 ; CHECK-LABEL: @poison4(
 ; CHECK-NEXT:    ret i32 0
 ;
   %v = lshr i32 poison, %x
   ret i32 %v
 }
 

llvm/test/Transforms/InstSimplify/undef.ll

 ; CHECK-NEXT:    ret i64 poison
 ;
   %r = shl i64 undef, undef
   ret i64 %r
 }
 
 define i64 @test11b(i64 %a) {
 ; CHECK-LABEL: @test11b(
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
   %r = shl i64 %a, undef
   ret i64 %r
 }
 
 define i64 @test12() {
 ; CHECK-LABEL: @test12(
 ; CHECK-NEXT:    ret i64 poison
 ;
   %r = ashr i64 undef, undef
   ret i64 %r
 }
 
 define i64 @test12b(i64 %a) {
 ; CHECK-LABEL: @test12b(
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
   %r = ashr i64 %a, undef
   ret i64 %r
 }
 
 define i64 @test13() {
 ; CHECK-LABEL: @test13(
 ; CHECK-NEXT:    ret i64 poison
 ;
   %r = lshr i64 undef, undef
   ret i64 %r
 }
 
 define i64 @test13b(i64 %a) {
 ; CHECK-LABEL: @test13b(
-; CHECK-NEXT:    ret i64 undef
+; CHECK-NEXT:    ret i64 poison
 ;
   %r = lshr i64 %a, undef
   ret i64 %r
 }
 
 define i1 @test14() {
 ; CHECK-LABEL: @test14(
 ; CHECK-NEXT:    ret i1 undef

 ; CHECK-NEXT:    ret i64 undef
 ;
   %r = call i64 (i64) undef(i64 %a)
   ret i64 %r
 }
 
 define <4 x i8> @test19(<4 x i8> %a) {
 ; CHECK-LABEL: @test19(
-; CHECK-NEXT:    ret <4 x i8> undef
+; CHECK-NEXT:    ret <4 x i8> poison
 ;
   %b = shl <4 x i8> %a, <i8 8, i8 9, i8 undef, i8 -1>
   ret <4 x i8> %b
 }
 
 define i32 @test20(i32 %a) {
 ; CHECK-LABEL: @test20(
 ; CHECK-NEXT:    ret i32 poison