[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

40

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

40

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

40

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

[w2yehia]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

40

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

40

@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

40

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

       return Val;
     }
 
-    if (ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
+    ConstantInt *RHS = dyn_cast<ConstantInt>(I->getOperand(1));
+    if (RHS && !RHS->isNegative()) {
       if (I->getOpcode() == Instruction::Shl) {
         // This is a value scaled by '1 << the shift amt'.
         Scale = UINT64_C(1) << RHS->getZExtValue();

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

+; RUN: opt -S -passes=instcombine < %s | FileCheck %s
+@test = external global [1 x i32], align 16
+
+define void @foo() {
+  br label %b0
+
+b0:
+  %1 = phi i64 [ 1, %0 ], [ %9, %b0 ]
+; Currently we cannot handle expressions of the form Offset - X * Scale.
+; CHECK: mul nsw i64 %1, -4
+; CHECK: alloca i8
+  %2 = mul nsw i64 %1, -4
+  %3 = add nsw i64 %2, 24
+  %4 = alloca i8, i64 %3, align 4
+  %5 = bitcast i8* %4 to i32*
+  store i32 undef, i32* %5, align 4
+
+  %6 = load i8, i8* %4, align 4
+  %7 = getelementptr inbounds [1 x i32], [1 x i32]* @test, i64 0, i8 %6
+  %8 = load i32, i32* %7, align 4
+  store i32 %8, i32* undef, align 4
+
+  %9 = add nuw nsw i64 %1, 1
+  br i1 undef, label %bend, label %b0
+
+bend:
+  ret void
+}
+