Strange case related to InstCombinePass

IR & Optimizations
,
1

Hello!

I found a strange case related to InstCombinePass.

When I compiled this code snippet with /O2 using clang-cl.exe,

uint64_t func(uint64_t a, uint64_t b, uint64_t c) {
  uint64_t L_2 = a;
  uint64_t L_5 = b;
  uint64_t L_8 = c;
  uint64_t V_0 = 0;

  // il2cpp_codegen_add(a, b) is equivalent into 'a + b'
  V_0 = (
    (int64_t)il2cpp_codegen_add(
      ((int64_t)il2cpp_codegen_add(
        (int64_t)L_2, ((int64_t)((uint64_t)L_5>>((int32_t)32))))
      ), 
      ((int64_t)((uint64_t)L_8>>((int32_t)32)))
    )
  );

  uint64_t L_9 = V_0;

  if (((int64_t)((int64_t)L_9&((int64_t)(std::numeric_limits<int64_t>::min)()))))
  {
  	goto IL_0047;
  }

  uint64_t L_10 = V_0;
  V_0 = ((int64_t)((int64_t)L_10<<1));
  int32_t* L_11 = ___pexp2;
  int32_t* L_12 = ___pexp2;
  int32_t L_13 = *((int32_t*)L_12);
  // il2cpp_codegen_subtract is equivalent to 'L_13 - 1'
  *((int32_t*)L_11) = (int32_t)((int32_t)il2cpp_codegen_subtract(L_13, 1));

IL_0047:
  uint64_t L_14 = V_0;
  return L_14;
}

I got this IR code where the if-statement has been removed so that the executable did not work correctly. Since the predicate above can be both true and false, the if-statement shouldn’t be removed.

13:                                               ; preds = %7, %12
  %14 = lshr i64 %1, 32, !dbg !36985
  %15 = lshr i64 %0, 32, !dbg !36985
  %16 = mul nuw nsw i64 %14, %15, !dbg !36991
  %17 = and i64 %1, 4294967295, !dbg !36995
  %18 = mul nuw nsw i64 %17, %15, !dbg !36998
  %19 = and i64 %0, 4294967295, !dbg !37002
  %20 = mul nuw nsw i64 %14, %19, !dbg !37005
  %21 = lshr i64 %20, 32, !dbg !37006
  %22 = lshr i64 %18, 32, !dbg !37006
  %23 = add nuw nsw i64 %22, %16, !dbg !37009
  %24 = add nuw nsw i64 %23, %21, !dbg !37012
  %25 = shl nuw i64 %24, 1, !dbg !37014
  %26 = load i32, ptr %2, align 4, !dbg !37015
  %27 = add nsw i32 %26, -1, !dbg !37018
  store i32 %27, ptr %2, align 4, !dbg !37019
  ret i64 %25, !dbg !37020

When I disabled InstCombinePass by commenting out all ‘addPass(InstCombinePass());’ calls in PassBuilderPipelines.cpp, I got this code correctly woring.

13:                                               ; preds = %7, %12
  %14 = lshr i64 %1, 32, !dbg !37401
  %15 = trunc i64 %14 to i32, !dbg !37401
  %16 = lshr i64 %0, 32, !dbg !37401
  %17 = trunc i64 %16 to i32, !dbg !37401
  %18 = zext i32 %15 to i64, !dbg !37405
  %19 = zext i32 %17 to i64, !dbg !37405
  %20 = mul nuw nsw i64 %18, %19, !dbg !37408
  %21 = trunc i64 %1 to i32, !dbg !37409
  %22 = zext i32 %21 to i64, !dbg !37413
  %23 = mul nuw nsw i64 %22, %19, !dbg !37416
  %24 = trunc i64 %0 to i32, !dbg !37417
  %25 = zext i32 %24 to i64, !dbg !37421
  %26 = mul nuw nsw i64 %18, %25, !dbg !37424
  %27 = lshr i64 %26, 32, !dbg !37425
  %28 = lshr i64 %23, 32, !dbg !37425
  %29 = add nuw nsw i64 %28, %20, !dbg !37428
  %30 = add nuw nsw i64 %29, %27, !dbg !37431
  %31 = and i64 %30, -9223372036854775808, !dbg !37432
  %32 = icmp ne i64 %31, 0, !dbg !37432
  %33 = select i1 %32, i32 2, i32 0, !dbg !37395
  %34 = icmp eq i32 %33, 0
  br i1 %34, label %35, label %39

35:                                               ; preds = %13
  %36 = shl i64 %30, 1, !dbg !37434
  %37 = load i32, ptr %2, align 4, !dbg !37435
  %38 = sub nsw i32 %37, 1, !dbg !37438
  store i32 %38, ptr %2, align 4, !dbg !37439
  br label %39, !dbg !37440

39:                                               ; preds = %13, %35
  %40 = phi i64 [ %30, %13 ], [ %36, %35 ]
  ret i64 %40, !dbg !37441

Does anyone who understands InstCombinePass very well help me to figure why this happened and how to resolve this case?

Thank you for any help!

2

If I read it correctly:

  • mul nsw multiplies two zero-extended 32-bit numbers (two non-negative numbers). Since the operation is nsw, the compiler can assume that signed multiplication will not overflow (the result will be non-negative).
  • lshr produces a non-negative value.
  • add nsw of two non-negative values cannot produce negative value for the same reason.
  • %31 = and i64 %30, -9223372036854775808 is always 0 since %30 is never negative.
  • because of that %32 is always false, %33 is always 0, and the branch condition %34 = icmp eq i32 %33, 0 is always true.
1 Like
3

Following up @s-barannikov previous comment, I think you might want to check il2cpp_codegen_add and see why LLVM thinks it’s a good idea to attach nsw on multiplications in the first place, as I believe that function is more than just a + b.

1 Like
4

Side note - because I remember having to dig these semantics up and figured it’d be worth restating them.

nsw doesn’t quite mean the inputs are non-negative. It’s “if we interpret the inputs as signed numbers and then do the [operation] an infinite precision, that value will be the same as the result of the [operation], interpreted as a signed number”. That is, mul nsw i32 -4, 8 is -32, not poison

nuw or “no unsigned wrap” is the same thing but swap all the "signed"s for “unsigned”. So while, for example, add i32 -1, 1 is nsw but not nuw, since 0xff_ff_ff_ff + 1 is 0x1_00_00_00_00 in infinite precision but 0x0 when truncated to 32 bits.

But also, re the generated IR, I observe that you’ve got logical shift right, which doesn’t preserve the sign bit.

lshr i64 %v, (N > 0) is non-negative/has a clear sign bit by definition.

I think you want to prod C++ into making those arithmetic shifts instead

1 Like
5

oh I was also slightly confused by how Sergei described it but I believe what he meant was that because it’s multiplying two non-negative numbers, the result will be non-negative.

2 Likes