[ValueTracking] Make poison propagation more aggressive

[sanjoy]

Summary

Motivation: fix PR31181 without regression (the actual fix is still in
progress). However, the actual content of PR31181 is not relevant
here.

This change makes poison propagation more aggressive in the following
cases:

1. poision * Val == poison, for any Val. In particular, this changes existing intentional and documented behavior in these two cases: a. Val is 0 b. Val is 2^k * N
2. poison << Val == poison, for any Val
3. getelementptr is poison if any input is poison

I think all of these are justified (and are axiomatically true in the
new poison / undef model):

1a: we need poison * 0 to be poison to allow transforms like these:

A * (B + C) ==> A * B + A * C

If poison * 0 were 0 then the above transform could not be allowed
since e.g. we could have A = poison, B = 1, C = -1, making the LHS

poison * (1 + -1) = poison * 0 = 0

and the RHS

poison * 1 + poison * -1 = poison + poison = poison

1b: we need e.g. poison * 4 to be poison since we want to allow

A * 4 ==> A + A + A + A

If poison * 4 were a value with all of their bits poison except the
last four; then we'd not be able to do this transform since then if A
were poison the LHS would only be "partially" poison while the RHS
would be "full" poison.

2: Same reasoning as (1b), we'd like have the following kinds
transforms be legal:

A << 1 ==> A + A

[majnemer]

LGTM!

lib/Analysis/ValueTracking.cpp

 bool llvm::propagatesFullPoison(const Instruction *I) {
   switch (I->getOpcode()) {
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Xor:
   case Instruction::Trunc:
   case Instruction::BitCast:
   case Instruction::AddrSpaceCast:
+  case Instruction::Mul:
+  case Instruction::Shl:
+  case Instruction::GetElementPtr:
     // These operations all propagate poison unconditionally. Note that poison
     // is not any particular value, so xor or subtraction of poison with
     // itself still yields poison, not zero.
     return true;
 
   case Instruction::AShr:
   case Instruction::SExt:
     // For these operations, one bit of the input is replicated across
     // multiple output bits. A replicated poison bit is still poison.
     return true;
 
-  case Instruction::Shl: {
-    // Left shift *by* a poison value is poison. The number of
-    // positions to shift is unsigned, so no negative values are
-    // possible there. Left shift by zero places preserves poison. So
-    // it only remains to consider left shift of poison by a positive
-    // number of places.
-    //
-    // A left shift by a positive number of places leaves the lowest order bit
-    // non-poisoned. However, if such a shift has a no-wrap flag, then we can
-    // make the poison operand violate that flag, yielding a fresh full-poison
-    // value.
-    auto *OBO = cast<OverflowingBinaryOperator>(I);
-    return OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap();
-  }
-
-  case Instruction::Mul: {
-    // A multiplication by zero yields a non-poison zero result, so we need to
-    // rule out zero as an operand. Conservatively, multiplication by a
-    // non-zero constant is not multiplication by zero.
-    //
-    // Multiplication by a non-zero constant can leave some bits
-    // non-poisoned. For example, a multiplication by 2 leaves the lowest
-    // order bit unpoisoned. So we need to consider that.
-    //
-    // Multiplication by 1 preserves poison. If the multiplication has a
-    // no-wrap flag, then we can make the poison operand violate that flag
-    // when multiplied by any integer other than 0 and 1.
-    auto *OBO = cast<OverflowingBinaryOperator>(I);
-    if (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap()) {
-      for (Value *V : OBO->operands()) {
-        if (auto *CI = dyn_cast<ConstantInt>(V)) {
-          // A ConstantInt cannot yield poison, so we can assume that it is
-          // the other operand that is poison.
-          return !CI->isZero();
-        }
-      }
-    }
-    return false;
-  }
-
   case Instruction::ICmp:
     // Comparing poison with any value yields poison.  This is why, for
     // instance, x s< (x +nsw 1) can be folded to true.
     return true;
 
-  case Instruction::GetElementPtr:
-    // A GEP implicitly represents a sequence of additions, subtractions,
-    // truncations, sign extensions and multiplications. The multiplications
-    // are by the non-zero sizes of some set of types, so we do not have to be
-    // concerned with multiplication by zero. If the GEP is in-bounds, then
-    // these operations are implicitly no-signed-wrap so poison is propagated
-    // by the arguments above for Add, Sub, Trunc, SExt and Mul.
-    return cast<GEPOperator>(I)->isInBounds();
-
   default:
     return false;
   }
 }
 
 const Value *llvm::getGuaranteedNonFullPoisonOp(const Instruction *I) {
   switch (I->getOpcode()) {
     case Instruction::Store:

test/Analysis/Delinearization/a.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 ;
 ; void foo(long n, long m, long o, int A[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[2*i+3][3*j-4][5*k+7] = 1;
 ; }
 
 ; AddRec: {{{(28 + (4 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(12 * %o)}<%for.j>,+,20}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 4 bytes.
-; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<%for.j>][{7,+,5}<nw><%for.k>]
+; CHECK: ArrayRef[{3,+,2}<%for.i>][{-4,+,3}<nw><%for.j>][{7,+,5}<nw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* nocapture %A) #0 {
 entry:
   %cmp32 = icmp sgt i64 %n, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end17
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry
   %cmp230 = icmp sgt i64 %m, 0

test/Analysis/Delinearization/iv_times_constant_in_subscript.ll

 ; RUN: opt < %s -analyze -delinearize | FileCheck %s
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, long b, double A[n][m]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       A[2i+b][2j] = 1.0;
 ; }
 
 ; AddRec: {{((%m * %b * 8) + %A),+,(2 * %m * 8)}<%for.i>,+,(2 * 8)}<%for.j>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m] with elements of 8 bytes.
-; CHECK: ArrayRef[{%b,+,2}<%for.i>][{0,+,2}<%for.j>]
+; CHECK: ArrayRef[{%b,+,2}<nsw><%for.i>][{0,+,2}<%for.j>]
 
 
 define void @foo(i64 %n, i64 %m, i64 %b, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]

test/Analysis/ScalarEvolution/flags-from-poison.ll

; CHECK: --> {%offset,+,1}<nw>
   call void @foo()
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
   ret void
 }
 
-; Without inbounds, GEP does not propagate poison in the very
-; conservative approach used here.
-define void @test-add-no-inbounds(float* %input, i32 %offset, i32 %numIterations) {
+; Any poison input makes getelementptr produce poison
+define void @test-gep-propagates-poison(float* %input, i32 %offset, i32 %numIterations) {
 ; CHECK-LABEL: @test-add-no-inbounds
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 
 ; CHECK: %index32 =
-; CHECK: --> {%offset,+,1}<nw>
+; CHECK: --> {%offset,+,1}<nsw>
   %index32 = add nsw i32 %i, %offset
 
   %ptr = getelementptr float, float* %input, i32 %index32
   %nexti = add nsw i32 %i, 1
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
; CHECK: --> {%offset,+,1}<nsw>
   %nexti = add nsw i32 %i, 1
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
   ret void
 }
 
-; Multiplication by a non-constant should not propagate poison in the
-; very conservative approach used here.
-define void @test-add-mul-no-propagation(float* %input, i32 %offset, i32 %numIterations) {
-; CHECK-LABEL: @test-add-mul-no-propagation
+; Any poison input to multiplication propages poison.
+define void @test-mul-propagates-poison(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-mul-propagates-poison
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 
 ; CHECK: %index32 =
-; CHECK: --> {%offset,+,1}<nw>
+; CHECK: --> {%offset,+,1}<nsw>
   %index32 = add nsw i32 %i, %offset
 
   %indexmul = mul nsw i32 %index32, %offset
   %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
   %nexti = add nsw i32 %i, 1
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop
 exit:
   ret void
 }
 
-; Multiplication by a non-zero constant does not propagate poison
-; without a no-wrap flag.
-define void @test-add-mul-no-propagation2(float* %input, i32 %offset, i32 %numIterations) {
-; CHECK-LABEL: @test-add-mul-no-propagation2
+define void @test-mul-propagates-poison-2(float* %input, i32 %offset, i32 %numIterations) {
+; CHECK-LABEL: @test-mul-propagates-poison-2
 entry:
   br label %loop
 loop:
   %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 
 ; CHECK: %index32 =
-; CHECK: --> {%offset,+,1}<nw>
+; CHECK: --> {%offset,+,1}<nsw>
   %index32 = add nsw i32 %i, %offset
 
   %indexmul = mul i32 %index32, 2
   %ptr = getelementptr inbounds float, float* %input, i32 %indexmul
   %nexti = add nsw i32 %i, 1
   %f = load float, float* %ptr, align 4
   %exitcond = icmp eq i32 %nexti, %numIterations
   br i1 %exitcond, label %exit, label %loop