[InstCombine] decomposeSimpleLinearExpr should bail out on negative operands.

[w2yehia]

Summary

InstCombine tries to rewrite

%prod = mul nsw i64 %X,   Scale
%acc = add nsw i64 %prod,   Offset
%0 = alloca i8, i64 %acc, align 4
%1 = bitcast i8* %0 to i32*
Use ( %1 )

into

%prod = mul nsw i64 %X,   Scale/4
%acc = add nsw i64 %prod,   Offset/4
%0 = alloca i32, i64 %acc, align 4
Use (%0)

But it assumes Scale is unsigned.

For now, bail out on negative operands to avoid an incorrect transformation.

[w2yehia]

This comment was removed by w2yehia.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

Isn't the actual bug here? The && !OBI->hasNoSignedWrap() shouldn't be there. The number of elements is an unsigned value, so we should be checking for no unsigned wrap, not "either no unsigned or no signed wrap".

[w2yehia]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

i'm not that familiar with the implications of (not) having nsw, so you are likely correct.
Does the presence of nsw indicate the operands of the multiplication are signed?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

nsw indicates that there is no signed overflow, while we need no unsigned overflow here.

[w2yehia]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

Thanks for reviewing. I had to read up more about nsw/nuw and signedness in llvm in general.
I couldn't conclude that the presence of nuw indicates that the operands of the mul can be safely interpreted as unsigned.
I might be asking the wrong question, so can you please tell me why checking for nuw is necessary and sufficient in order to make the code (in decomposeSimpleLinearExpr and PromoteCastOfAllocation) to be sound?

[w2yehia]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

@nikic I will implement your suggestion. I had to convince myself (and get educated on these flags)

After brainstorming with @sfertile about the implications of the nuw/nsw flags, we concluded that doing only the && !OBI->hasNoSignedWrap() is not a sufficient condition to safely interpret Scale (2nd) operand of the mul as unsigned in isolation.
Consider this pseudo-llvm where the -4 is intended to be signed:

if ( %X == 1 || %X == 0) {
  %0 = mul nuw i32 %X, -4   // 1 * 4294967292 = 4294967292 (no unsigned wrap)
  ..

However, because this exit condition applies to all visited instructions (add, mul, shl), having the nuw means you cannot having something like 24 - 4 because it unsigned overflows. So if we expand the above example:

if ( %X == 1 || %X == 0) {
  %0 = mul nuw i32 %X, -4   // 1 * 4294967292 = 4294967292 (no unsigned wrap)
  %1 = add nuw i32 %0, C    // 4294967292 + C
   alloca i8, %1

The addition 4294967292 + C must overflow in order to produce a positive signed number. If it does not overflow then the user-intended result is simply a large unsigned number and storing it in an unsigned is fine.

[w2yehia]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

42

basically, if you have a complex expression involving add/mul/shl and one of the operands is negative, then in order to bring back the result to a positive value an unsigned overflow has to occur:

1. add i32 -1, C // (unsigned) -1 + C must overflow
2. mul i32 -1, C // (unsigned) -1 * C must overflow
3. shl i32 -1, C // (unsigned) -1 << C must overflow

[w2yehia]

As per review, remove !OBI->hasNoSignedWrap() from the early exit condition. Also the original fix is no longer needed so remove it as well.

[nikic]

llvm/test/Transforms/InstCombine/neg-alloca.ll

2

Please use the llvm/utils/update_test_checks.py script to generate CHECK lines.

Also, I think that this test case may be reduced, I don't think you really need much more than then mul+add+alloca+bitcast sequence?

[w2yehia]

llvm/test/Transforms/InstCombine/neg-alloca.ll

2

I reduced the testcase, and made the RUN command canonical (based on suggestions in update_test_checks.py).
I think the current CHECKs capture the required functionality best.

[w2yehia]

llvm/test/Transforms/InstCombine/neg-alloca.ll

2

I think the current CHECKs capture the required functionality best.

Sorry wrote in a rush. I mean that we want the test not to be fragile (that's obvious) and so having too much CHECKs is not good. I think it's enough to CHECK that the negative operand remains and the alloca type is the same.

[w2yehia]

@nikic any chance you can review this today? thanks!

[nikic]

llvm/test/Transforms/InstCombine/neg-alloca.ll

2

We generally prefer to always use auto-generated check lines, even if they contain "unnecessary" instructions, because it makes it easier to update tests in the future.

[w2yehia]

use update_test_checks.py to generate the CHECKs

[w2yehia]

llvm/test/Transforms/InstCombine/neg-alloca.ll

2

fair enough. Thanks.

[nikic]

LGTM, though patch description needs an update.

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

static Value *decomposeSimpleLinearExpr(Value *Val, unsigned &Scale,
   if (ConstantInt *CI = dyn_cast<ConstantInt>(Val)) {
     Offset = CI->getZExtValue();
     Scale  = 0;
     return ConstantInt::get(Val->getType(), 0);
   }
 
   if (BinaryOperator *I = dyn_cast<BinaryOperator>(Val)) {
     // Cannot look past anything that might overflow.
+    // We specifically require nuw because we store the Scale in an unsigned
+    // and perform an unsigned divide on it.
     OverflowingBinaryOperator *OBI = dyn_cast<OverflowingBinaryOperator>(Val);
-    if (OBI && !OBI->hasNoUnsignedWrap() && !OBI->hasNoSignedWrap()) {
+    if (OBI && !OBI->hasNoUnsignedWrap()) {
       Scale = 1;
       Offset = 0;
       return Val;
     }
 
     if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
       if (I->getOpcode() == Instruction::Shl) {
         // This is a value scaled by '1 << the shift amt'.

llvm/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
-; With "nsw", the alloca and its bitcast can be fused:
-  %7 = add nsw i32 %6, 2048
+  %6 = shl nuw i32 %5, 3
+; With "nuw", the alloca and its bitcast can be fused:
+  %7 = add nuw 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
 ; <label>:10                                      ; preds = %4, %0
   %11 = load double*, double** %ptr, align 4
define void @fu2(i32 %parm) nounwind ssp {
   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 = mul nsw i32 %5, 8
-; Without "nsw", the alloca and its bitcast cannot be fused:
+  %6 = mul nuw i32 %5, 8
+; Without "nuw", the alloca and its bitcast cannot be fused:
   %7 = add  i32 %6, 2048
 ; CHECK: alloca i8
   %8 = alloca i8, i32 %7
 ; CHECK-NEXT: bitcast double**
 ; CHECK-NEXT: store i8*
   %9 = bitcast i8* %8 to double*
   store double* %9, double** %ptr, align 4
   br label %10
 
 ; <label>:10                                      ; preds = %4, %0
   %11 = load double*, double** %ptr, align 4
   call void @bar(double* %11)
   ret void
 }
 

llvm/test/Transforms/InstCombine/neg-alloca.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+declare void @use(i32 *)
+
+define void @foo(i64 %X) {
+; Currently we cannot handle expressions of the form Offset - X * Scale.
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nsw i64 [[X:%.*]], -4
+; CHECK-NEXT:    [[TMP2:%.*]] = add nsw i64 [[TMP1]], 24
+; CHECK-NEXT:    [[TMP3:%.*]] = alloca i8, i64 [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i8* [[TMP3]] to i32*
+; CHECK-NEXT:    call void @use(i32* nonnull [[TMP4]])
+; CHECK-NEXT:    ret void
+;
+  %1 = mul nsw i64 %X, -4
+  %2 = add nsw i64 %1, 24
+  %3 = alloca i8, i64 %2, align 4
+  %4 = bitcast i8* %3 to i32*
+  call void @use(i32 *%4)
+  ret void
+}