[IR] Fix the definition of 'shl nsw'

[majnemer]

Summary

Provide a definition for 'shl nsw' which makes it compatible with 'mul nsw'.

[sanjoy]

Just to be clear, you're explicitly making shl nsw X Y be poison less often than mul nsw X (1<<Y)? The example I have in mind is (for i8) X = -1, Y = 7. If so, that might be worth stating in the LangRef, maybe even with an example or two.

[majnemer]

In D8890#153095, @sanjoy wrote:

Just to be clear, you're explicitly making shl nsw X Y be poison less often than mul nsw X (1<<Y)? The example I have in mind is (for i8) X = -1, Y = 7. If so, that might be worth stating in the LangRef, maybe even with an example or two.

Er, the idea is that they will be poison at exactly the same rate. mul nsw i8 -1, 128 is poison because 128 can't be represented in i8. shl nsw i8 -1, 7 should be poison as well. I see the typo you are getting at, "it shifts out any non-sign bits" is wrong. I'll try to rephrase it so it is correct.

[sanjoy]

Also, I'd vote for just directly stating that "X << Y" sign overflows if and only if "X * (1 << Y)" sign overflows. What it actually implies for shifting out sign bits etc. should be stated as a corollary.

[majnemer]

• Address Sanjoy's review comments.

[majnemer]

• Let the wording do the right thing for -1.

[sanjoy]

docs/LangRef.rst

5061–5062

I'd prefer just removing this, and defining nuw directly, like nsw.

5063

Should be `nsw` here.

5064

I'd use "if and only if" here.

5080

Should we add an example of a poison-value creating shl?

lib/Analysis/InstructionSimplify.cpp

2303

Is this correct for i1?

test/Transforms/InstCombine/cast.ll

783

Why do we need to change this test?

[chandlerc]

FWIW, I really liked having a definition explicit in terms of what kinds of bits can be shifted out. I think its good to *both* define this from first principles of where bits move in the shift operation, *and* how it should relate to an NSW multiply by a power of two.

Unsure when after when we chatted this wording went away, but I'd really like to keep it.

[majnemer]

docs/LangRef.rst

5061–5062

Done.

5063

Done.

5064

Done.

lib/Analysis/InstructionSimplify.cpp

2303

i1 is handled earlier. I will add an assert to make that clear.

test/Transforms/InstCombine/cast.ll

783

I am changing these tests to as they were back in r219566.

[majnemer]

• Address Sanjoy's review comments.
• Let the wording do the right thing for -1.
• Address Sanjoy's latest review comments.

[majnemer]

In D8890#153126, @chandlerc wrote:

FWIW, I really liked having a definition explicit in terms of what kinds of bits can be shifted out. I think its good to *both* define this from first principles of where bits move in the shift operation, *and* how it should relate to an NSW multiply by a power of two.

Unsure when after when we chatted this wording went away, but I'd really like to keep it.

The explicit definition gets hairy very quickly. It didn't correctly handle shl nsw i32 1073741824, 1 or shl nsw i32 -1, 31.

[sanjoy]

I'm fine keeping the sign-bit based definition as a corollary,
especially if we can prove and list the edge cases.

I don't think that _is_ the first-principles definition though, given
that we're adding exceptions to it just so that multiplication based
definition works.

[chandlerc]

In D8890#153137, @majnemer wrote:

In D8890#153126, @chandlerc wrote:

FWIW, I really liked having a definition explicit in terms of what kinds of bits can be shifted out. I think its good to *both* define this from first principles of where bits move in the shift operation, *and* how it should relate to an NSW multiply by a power of two.

Unsure when after when we chatted this wording went away, but I'd really like to keep it.

The explicit definition gets hairy very quickly. It didn't correctly handle shl nsw i32 1073741824, 1 or shl nsw i32 -1, 31.

The version we looked at we specifically had handle -1. I don't think it is hard to make it handle (1 << 30).

[chandlerc]

In D8890#153142, @sanjoy wrote:

I'm fine keeping the sign-bit based definition as a corollary,
especially if we can prove and list the edge cases.

I don't think that _is_ the first-principles definition though, given
that we're adding exceptions to it just so that multiplication based
definition works.

Not the first-principles *motivation*. I'm not suggesting that the bit-math is what is the primary motivation or the most important consequences. I'm suggesting that it doesn't rely on reasoning about anything other than the basic bit shifting operation, and I find it very nice to define in those terms as the basis, and merely state the equivalence that is intended (and motivating that particular definition). We can (and probably should!) even call out that this *is* a strange definition but that it is specifically chosen to establish this equivalence.

[sanjoy]

One way to phrase the overflow behavior in terms of bits shifted out
is:

T << S as N-bit integers sign-overflows if and only if

a. S != N and the bits shifted out are not all equal to the sign bit
   of (T << S).

b. S == N and the bits shifted out are not all zero.

[(a) is the definition of sign-overflow as in the LangRef today. (b)
is LangRef's definition for unsigned-wrap.]

(b) is equivalent to "S == N and T != 1".

We can now prove that "T << S" sign-overflows iff "T * (1 << S)"
sign-overflows:

If S != N:

Sext(T * (1 << S)) == Sext(T) * Sext(1 << S)

<=> Sext(T * (1 << S)) == Sext(T) * Zext(1 << S)
<=> Sext(T * (1 << S)) == Sext(T) << S -- (A)
<=> Sext(T << S) == Sext(T) << S
<=> (a)

if S == N:

Sext(T * (1 << S)) == Sext(T) * Sext(1 << S)

<=> Sext(T * (1 << N)) == Sext(T) * Sext(1 << N)
<=> T == 1
<=> (b)

For (A) we use the identity "Sext(T) << S == Sext(T) * Zext(1 << S)".
This really is the interesting difference between shifting and
multiplication -- roughly speaking, shifting always treats its second
argument as unsigned. More precisely, if we define a "half-nsw
multiplication", one where "sext(A *hnsw B) == sext(A) * zext(B)" then
the current definition of an "shl nsw A B" in the LangRef is
equivalent to "A *hnsw B".

• Sanjoy

[sanjoy]

the current definition of an "shl nsw A B" in the LangRef is
equivalent to "A *hnsw B".

Um, should be 'equivalent to "A *hnsw (1 << B)"'.

• Sanjoy

[sanjoy]

Is this abandoned?

[sanjoy]

Resigning so that this does not show up in my pending reviews list. Feel free to add me back if this change is being revived.

docs/LangRef.rst

 
 The value produced is ``op1`` \* 2\ :sup:`op2` mod 2\ :sup:`n`,
 where ``n`` is the width of the result. If ``op2`` is (statically or
 dynamically) negative or equal to or larger than the number of bits in
 ``op1``, the result is undefined. If the arguments are vectors, each
 vector element of ``op1`` is shifted by the corresponding shift amount
 in ``op2``.
 
 If the ``nuw`` keyword is present, then the shift produces a :ref:`poison
-value <poisonvalues>` if it shifts out any non-zero bits. If the
-``nsw`` keyword is present, then the shift produces a :ref:`poison
-value <poisonvalues>` if it shifts out any bits that disagree with the
-resultant sign bit. As such, NUW/NSW have the same semantics as they
-would if the shift were expressed as a mul instruction with the same
-nsw/nuw bits in (mul %op1, (shl 1, %op2)).
+value <poisonvalues>` if and only if ``op1`` \* ``1 << op2`` results in unsigned
+overflow.
+
+If the ``nsw`` keyword is present, then the shift produces a :ref:`poison
+value <poisonvalues>` if and only if ``op1`` \* ``1 << op2`` results in signed
+overflow.
 
 Example:
 """"""""
 
 .. code-block:: llvm
 
       <result> = shl i32 4, %var   ; yields i32: 4 << %var
       <result> = shl i32 4, 2      ; yields i32: 16
       <result> = shl i32 1, 10     ; yields i32: 1024
       <result> = shl i32 1, 32     ; undefined
+      <result> = shl nsw i32 1, 31 ; yields i32: -2147483648
+      <result> = shl nsw i32 2, 30 ; poison
       <result> = shl <2 x i32> < i32 1, i32 1>, < i32 1, i32 2>   ; yields: result=<2 x i32> < i32 2, i32 4>
 
 '``lshr``' Instruction
 ^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::

lib/Analysis/InstructionSimplify.cpp

if (match(LHS, m_URem(m_Value(), m_ConstantInt(CI2)))) {
         Upper = Upper + 1;
         assert(Upper != Lower && "Upper part of range has wrapped!");
       }
     } else if (match(LHS, m_NUWShl(m_ConstantInt(CI2), m_Value()))) {
       // 'shl nuw CI2, x' produces [CI2, CI2 << CLZ(CI2)]
       Lower = CI2->getValue();
       Upper = Lower.shl(Lower.countLeadingZeros()) + 1;
     } else if (match(LHS, m_NSWShl(m_ConstantInt(CI2), m_Value()))) {
+      assert(Width > 1 && "i1 should've been handled earlier!");
       if (CI2->isNegative()) {
+        unsigned ShiftAmount;
+        if (CI2->isMinusOne()) {
+          // 'shl nsw -1, x' produces [-1 << (Width-2), -1]
+          ShiftAmount = Width - 2;
+        } else {
           // 'shl nsw CI2, x' produces [CI2 << CLO(CI2)-1, CI2]
-        unsigned ShiftAmount = CI2->getValue().countLeadingOnes() - 1;
+          ShiftAmount = CI2->getValue().countLeadingOnes() - 1;
+        }
         Lower = CI2->getValue().shl(ShiftAmount);
         Upper = CI2->getValue() + 1;
       } else {
+        unsigned ShiftAmount;
+        if (CI2->isOne()) {
+          // 'shl nsw 1, x' produces [1, 1 << (Width-1)]
+          ShiftAmount = Width - 1;
+        } else {
           // 'shl nsw CI2, x' produces [CI2, CI2 << CLZ(CI2)-1]
-        unsigned ShiftAmount = CI2->getValue().countLeadingZeros() - 1;
+          ShiftAmount = CI2->getValue().countLeadingZeros() - 1;
+        }
         Lower = CI2->getValue();
         Upper = CI2->getValue().shl(ShiftAmount) + 1;
       }
     } else if (match(LHS, m_LShr(m_Value(), m_ConstantInt(CI2)))) {
       // 'lshr x, CI2' produces [0, UINT_MAX >> CI2].
       APInt NegOne = APInt::getAllOnesValue(Width);
       if (CI2->getValue().ult(Width))
         Upper = NegOne.lshr(CI2->getValue()) + 1;

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (match(&I, m_Mul(m_Shl(m_Value(NewOp), m_Constant(C2)),
                         m_Constant(C1))) &&
         match(C1, m_APInt(IVal))) {
       // ((X << C2)*C1) == (X * (C1 << C2))
       Constant *Shl = ConstantExpr::getShl(C1, C2);
       BinaryOperator *Mul = cast<BinaryOperator>(I.getOperand(0));
       BinaryOperator *BO = BinaryOperator::CreateMul(NewOp, Shl);
       if (I.hasNoUnsignedWrap() && Mul->hasNoUnsignedWrap())
         BO->setHasNoUnsignedWrap();
-      if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap() &&
-          Shl->isNotMinSignedValue())
+      if (I.hasNoSignedWrap() && Mul->hasNoSignedWrap())
         BO->setHasNoSignedWrap();
       return BO;
     }
 
     if (match(&I, m_Mul(m_Value(NewOp), m_Constant(C1)))) {
       Constant *NewCst = nullptr;
       if (match(C1, m_APInt(IVal)) && IVal->isPowerOf2())
         // Replace X*(2^C) with X << C, where C is either a scalar or a splat.
         NewCst = ConstantInt::get(NewOp->getType(), IVal->logBase2());
       else if (ConstantDataVector *CV = dyn_cast<ConstantDataVector>(C1))
         // Replace X*(2^C) with X << C, where C is a vector of known
         // constant powers of 2.
         NewCst = getLogBase2Vector(CV);
 
       if (NewCst) {
         BinaryOperator *Shl = BinaryOperator::CreateShl(NewOp, NewCst);
 
         if (I.hasNoUnsignedWrap())
           Shl->setHasNoUnsignedWrap();
-        if (I.hasNoSignedWrap() && NewCst->isNotMinSignedValue())
+        if (I.hasNoSignedWrap())
           Shl->setHasNoSignedWrap();
 
         return Shl;
       }
     }
   }
 
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {

test/Transforms/InstCombine/2011-06-13-nsw-alloca.ll

; CHECK: alloca double*
   store i32 %parm, i32* %1, align 4
   store double* null, double** %ptr, align 4
   %2 = load i32, i32* %1, align 4
   %3 = icmp ne i32 %2, 0
   br i1 %3, label %4, label %10
 
 ; <label>:4                                       ; preds = %0
   %5 = load i32, i32* %1, align 4
-  %6 = shl nsw i32 %5, 3
+  %6 = mul nsw i32 %5, 8
 ; With "nsw", the alloca and its bitcast can be fused:
   %7 = add nsw i32 %6, 2048
 ;  CHECK: alloca double
   %8 = alloca i8, i32 %7
   %9 = bitcast i8* %8 to double*
 ; CHECK-NEXT: store double*
   store double* %9, double** %ptr, align 4
   br label %10

test/Transforms/InstCombine/cast.ll

; CHECK-NEXT: getelementptr %s, %s addrspace(1)*
   %l = load %s, %s addrspace(1)* %r
 ; CHECK-NEXT: load %s, %s addrspace(1)*
   ret %s %l
 ; CHECK-NEXT: ret %s
 }
 
 define double @test69(double *%p, i64 %i) {
 ; CHECK-LABEL: @test69(
-  %o = shl nsw i64 %i, 3
+  %o = mul nsw i64 %i, 8
   %q = bitcast double* %p to i8*
   %pp = getelementptr inbounds i8, i8* %q, i64 %o
 ; CHECK-NEXT: getelementptr inbounds double, double*
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
 ; CHECK-NEXT: load double, double*
   ret double %l
 ; CHECK-NEXT: ret double
; CHECK-NEXT: getelementptr double, double*
   %l = load double, double* %r
 ; CHECK-NEXT: load double, double*
   ret double %l
 ; CHECK-NEXT: ret double
 }
 
 define double @test72(double *%p, i32 %i) {
 ; CHECK-LABEL: @test72(
-  %so = shl nsw i32 %i, 3
+  %so = mul nsw i32 %i, 8
   %o = sext i32 %so to i64
 ; CHECK-NEXT: sext i32 %i to i64
   %q = bitcast double* %p to i8*
   %pp = getelementptr inbounds i8, i8* %q, i64 %o
 ; CHECK-NEXT: getelementptr inbounds double, double*
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
 ; CHECK-NEXT: load double, double*
   ret double %l
 ; CHECK-NEXT: ret double
 }
 
 define double @test73(double *%p, i128 %i) {
 ; CHECK-LABEL: @test73(
-  %lo = shl nsw i128 %i, 3
+  %lo = mul nsw i128 %i, 8
   %o = trunc i128 %lo to i64
 ; CHECK-NEXT: trunc i128 %i to i64
   %q = bitcast double* %p to i8*
   %pp = getelementptr inbounds i8, i8* %q, i64 %o
 ; CHECK-NEXT: getelementptr double, double*
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
 ; CHECK-NEXT: load double, double*
; CHECK: bitcast
   %pp = getelementptr inbounds i8, i8* %q, i32 %c
   %r = bitcast i8* %pp to %s*
   %l = load %s, %s* %r
   ret %s %l
 }
 
 define double @test80([100 x double]* %p, i32 %i) {
 ; CHECK-LABEL: @test80(
-  %tmp = shl nsw i32 %i, 3
+  %tmp = mul nsw i32 %i, 8
 ; CHECK-NEXT: sext i32 %i to i64
   %q = bitcast [100 x double]* %p to i8*
   %pp = getelementptr i8, i8* %q, i32 %tmp
 ; CHECK-NEXT: getelementptr [100 x double], [100 x double]*
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
 ; CHECK-NEXT: load double, double*
   ret double %l
 ; CHECK-NEXT: ret double
 }
 
 define double @test80_addrspacecast([100 x double] addrspace(1)* %p, i32 %i) {
 ; CHECK-LABEL: @test80_addrspacecast(
 ; CHECK-NEXT: getelementptr [100 x double], [100 x double] addrspace(1)* %p
 ; CHECK-NEXT: load double, double addrspace(1)*
 ; CHECK-NEXT: ret double
-  %tmp = shl nsw i32 %i, 3
+  %tmp = mul nsw i32 %i, 8
   %q = addrspacecast [100 x double] addrspace(1)* %p to i8 addrspace(2)*
   %pp = getelementptr i8, i8 addrspace(2)* %q, i32 %tmp
   %r = addrspacecast i8 addrspace(2)* %pp to double addrspace(1)*
   %l = load double, double addrspace(1)* %r
   ret double %l
 }
 
 define double @test80_addrspacecast_2([100 x double] addrspace(1)* %p, i32 %i) {
 ; CHECK-LABEL: @test80_addrspacecast_2(
 ; CHECK-NEXT: getelementptr [100 x double], [100 x double] addrspace(1)*
 ; CHECK-NEXT: addrspacecast double addrspace(1)*
 ; CHECK-NEXT: load double, double addrspace(3)*
 ; CHECK-NEXT: ret double
-  %tmp = shl nsw i32 %i, 3
+  %tmp = mul nsw i32 %i, 8
   %q = addrspacecast [100 x double] addrspace(1)* %p to i8 addrspace(2)*
   %pp = getelementptr i8, i8 addrspace(2)* %q, i32 %tmp
   %r = addrspacecast i8 addrspace(2)* %pp to double addrspace(3)*
   %l = load double, double addrspace(3)* %r
   ret double %l
 }
 
 define double @test80_as1([100 x double] addrspace(1)* %p, i16 %i) {
 ; CHECK-LABEL: @test80_as1(
-  %tmp = shl nsw i16 %i, 3
+  %tmp = mul nsw i16 %i, 8
 ; CHECK-NEXT: sext i16 %i to i32
   %q = bitcast [100 x double] addrspace(1)* %p to i8 addrspace(1)*
   %pp = getelementptr i8, i8 addrspace(1)* %q, i16 %tmp
 ; CHECK-NEXT: getelementptr [100 x double], [100 x double] addrspace(1)*
   %r = bitcast i8 addrspace(1)* %pp to double addrspace(1)*
   %l = load double, double addrspace(1)* %r
 ; CHECK-NEXT: load double, double addrspace(1)*
   ret double %l

test/Transforms/InstSimplify/compare.ll

  %shl = shl nsw i64 -1, %a
  %cmp = icmp sge i64 %shl, 3
  ret i1 %cmp
 
 ; CHECK-LABEL: @icmp_shl_nsw_neg1
 ; CHECK-NEXT: ret i1 false
 }
 
-define i1 @icmp_shl_nsw_1(i64 %a) {
- %shl = shl nsw i64 1, %a
- %cmp = icmp sge i64 %shl, 0
+define i1 @icmp_shl_nsw_2(i64 %a) {
+ %shl = shl nsw i64 2, %a
+ %cmp = icmp sgt i64 %shl, 0
  ret i1 %cmp
 
-; CHECK-LABEL: @icmp_shl_nsw_1
+; CHECK-LABEL: @icmp_shl_nsw_2
 ; CHECK-NEXT: ret i1 true
 }
 
 define i1 @icmp_shl_1_V_ugt_2147483648(i32 %V) {
   %shl = shl i32 1, %V
   %cmp = icmp ugt i32 %shl, 2147483648
   ret i1 %cmp