Miscompile from AArch64 Global ISel backend: UDiv on LLVM>17

[tanmaytirpankar]

Look at the function f below:

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-linux-gnu"

define i2 @f(i2 %0) {
  %2 = sext i1 true to i2
  %3 = udiv i2 1, %2
  ret i2 %3
}

For the invocation f(-1), the expectation is that f will return a 0.

Lets look at the assembly generated by llc.

tanmay@revenant:~/llvm-clone/llvm/build-release/bin$ llc --march=aarch64 foo.ll -o -
	.text
	.file	"foo.ll"
	.globl	f                               // -- Begin function f
	.p2align	2
	.type	f,@function
f:                                      // @f
	.cfi_startproc
// %bb.0:
	mov	w0, wzr
	ret
.Lfunc_end0:
	.size	f, .Lfunc_end0-f
	.cfi_endproc
                                        // -- End function
	.section	".note.GNU-stack","",@progbits

Look at %bb.0. It stores a 0 in w0. According to the procedure call standard for AArch64 the function returns the value stored in w0 which as expected is 0.

Let us look at the assembly after running --global-isel:

tanmay@revenant:~/llvm-clone/llvm/build-release/bin$ llc --global-isel --march=aarch64 foo.ll -o -
	.text
	.file	"foo.ll"
	.globl	f                               // -- Begin function f
	.p2align	2
	.type	f,@function
f:                                      // @f
	.cfi_startproc
// %bb.0:
	ret
.Lfunc_end0:
	.size	f, .Lfunc_end0-f
	.cfi_endproc
                                        // -- End function
	.section	".note.GNU-stack","",@progbits

As can be seen here in %bb.0, there are no instructions. the function returns the value stored in w0 which has the first argument stored in it so -1.

The behavior was correct up until llvm-17.

cc @regehr

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

Author: Tanmay Tirpankar (tanmaytirpankar)

Look at the function `f` below:

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-linux-gnu"

define i2 @<!-- -->f(i2 %0) {
  %2 = sext i1 true to i2
  %3 = udiv i2 1, %2
  ret i2 %3
}

For the invocation f(-1), the expectation is that f will return a 0.

Lets look at the assembly generated by llc.

tanmay@<!-- -->revenant:~/llvm-clone/llvm/build-release/bin$ llc --march=aarch64 foo.ll -o -
	.text
	.file	"foo.ll"
	.globl	f                               // -- Begin function f
	.p2align	2
	.type	f,@<!-- -->function
f:                                      // @<!-- -->f
	.cfi_startproc
// %bb.0:
	mov	w0, wzr
	ret
.Lfunc_end0:
	.size	f, .Lfunc_end0-f
	.cfi_endproc
                                        // -- End function
	.section	".note.GNU-stack","",@<!-- -->progbits

Look at %bb.0. It stores a 0 in w0. According to the procedure call standard for AArch64 the function returns the value stored in w0 which as expected is 0.

Let us look at the assembly after running --global-isel:

tanmay@<!-- -->revenant:~/llvm-clone/llvm/build-release/bin$ llc --global-isel --march=aarch64 foo.ll -o -
	.text
	.file	"foo.ll"
	.globl	f                               // -- Begin function f
	.p2align	2
	.type	f,@<!-- -->function
f:                                      // @<!-- -->f
	.cfi_startproc
// %bb.0:
	ret
.Lfunc_end0:
	.size	f, .Lfunc_end0-f
	.cfi_endproc
                                        // -- End function
	.section	".note.GNU-stack","",@<!-- -->progbits

As can be seen here in %bb.0, there are no instructions. the function returns the value stored in w0 which has the first argument stored in it so -1.

The behavior was correct up until llvm-17.

cc @regehr

[tschuett]

There are a few options for you to investigate. Could you please run llc with -global-isel --march=aarch64 with:

• -stop-after=irtranslator
• -stop-after=legalizer
• -stop-before=instruction-select
  You should find variants of G_UDIV; the GlobelIsel UDiv.

I would prefer for you to take that exercise, because we different versions of llc.

[arsenm]

Breaks after AArch64PreLegalizerCombiner:

# *** IR Dump After IRTranslator (irtranslator) ***:
# Machine code for function f: IsSSA, TracksLiveness
Function Live Ins: $w0

bb.1 (%ir-block.1):
  liveins: $w0
  %1:_(s32) = COPY $w0
  %0:_(s2) = G_TRUNC %1:_(s32)
  %2:_(s1) = G_CONSTANT i1 true
  %4:_(s2) = G_CONSTANT i2 1
  %3:_(s2) = G_SEXT %2:_(s1)
  %5:_(s2) = G_UDIV %4:_, %3:_
  %6:_(s32) = G_ANYEXT %5:_(s2)
  $w0 = COPY %6:_(s32)
  RET_ReallyLR implicit $w0

# End machine code for function f.

# *** IR Dump After AArch64PreLegalizerCombiner (aarch64-prelegalizer-combiner) ***:
# Machine code for function f: IsSSA, TracksLiveness
Function Live Ins: $w0

bb.1 (%ir-block.1):
  liveins: $w0
  %13:_(s2) = G_IMPLICIT_DEF
  %6:_(s32) = G_ANYEXT %13:_(s2)
  $w0 = COPY %6:_(s32)
  RET_ReallyLR implicit $w0

# End machine code for function f.

[tschuett]

At not -O0, the combiner contains all_combines:

llvm-project/llvm/lib/Target/AArch64/AArch64Combine.td

Line 37 in 485075c

"AArch64PreLegalizerCombinerImpl", [all_combines,

[tschuett]

bin/llc --march=aarch64 -O0 --global-isel -stop-after=aarch64-prelegalizer-combiner foo.ll -o -

 bb.0 (%ir-block.1):
    liveins: $w0

    renamable $w9 = MOVZWi 1, 0
    renamable $w8 = ANDWri renamable $w9, 1
    renamable $w9 = SBFMWri killed renamable $w9, 0, 0
    renamable $w9 = ANDWri killed renamable $w9, 1
    renamable $w0 = UDIVWr killed renamable $w8, killed renamable $w9
    RET undef $lr, implicit killed $w0

Note the UDIVWr and the -O0.

[tschuett]

bin/llc --march=aarch64 -O0 --global-isel -stop-before=instruction-select foo.ll -o -

 %14:gpr(s32) = G_CONSTANT i32 1
    %15:gpr(s32) = COPY %14(s32)
    %13:gpr(s32) = G_CONSTANT i32 3
    %7:gpr(s32) = G_AND %15, %13
    %12:gpr(s32) = G_SEXT_INREG %14, 1
    %8:gpr(s32) = G_AND %12, %13
    %9:gpr(s32) = G_UDIV %7, %8
    $w0 = COPY %9(s32)
    RET_ReallyLR implicit $w0

[tschuett]

The CSEMIRBuilder blindly folds G_UDIV:

llvm-project/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp

Line 213 in 30e4b09

if (std::optional<APInt> Cst = ConstantFoldBinOp(

But it was probably the combiner.

[tschuett]

Non-exhaustive:
ae98939
8bfc0e0

[tschuett]

I believe is buggy: ae98939
It would fold G_UDIV 0, 0 -> 0. The constant folder, see link below, does not.

See here:

llvm-project/llvm/lib/CodeGen/GlobalISel/Utils.cpp

Line 534 in c4e57b1

case TargetOpcode::G_UDIV:

[antoniofrighetto]

I'm taking a look, though it seems like the miscompilation issue seems to be introduced way after performing the combining over G_UDIV. More specifically, the culprit seems to locate when trying to combine the second G_LSHR, when we pass from:

bb.1 (%ir-block.1):
  liveins: $w0
  %2:_(s1) = G_CONSTANT i1 true
  %4:_(s2) = G_CONSTANT i2 1
  %3:_(s2) = G_CONSTANT i2 -1
  %7:_(s2) = G_CONSTANT i2 0
  %8:_(s2) = G_CONSTANT i2 -2
  %10:_(s2) = G_SUB %4:_, %7:_
  %11:_(s2) = G_LSHR %10:_, %4:_(s2)
  %13:_(s2) = G_LSHR %10:_, %8:_(s2)
  %14:_(s1) = G_CONSTANT i1 false
  %15:_(s2) = G_SELECT %14:_(s1), %4:_, %13:_
  %6:_(s32) = G_ANYEXT %15:_(s2)
  $w0 = COPY %6:_(s32)
  RET_ReallyLR implicit $w0

to:

bb.1 (%ir-block.1):
  liveins: $w0
  %2:_(s1) = G_CONSTANT i1 true
  %4:_(s2) = G_CONSTANT i2 1
  %3:_(s2) = G_CONSTANT i2 -1
  %7:_(s2) = G_CONSTANT i2 0
  %8:_(s2) = G_CONSTANT i2 -2
  %10:_(s2) = G_SUB %4:_, %7:_
  %11:_(s2) = G_LSHR %10:_, %4:_(s2)
  %13:_(s2) = G_IMPLICIT_DEF
  %14:_(s1) = G_CONSTANT i1 false
  %15:_(s2) = G_SELECT %14:_(s1), %4:_, %13:_
  %6:_(s32) = G_ANYEXT %15:_(s2)
  $w0 = COPY %6:_(s32)
  RET_ReallyLR implicit $w0

The first one correctly verifies (https://alive2.llvm.org/ce/z/-YUjad), the second one (where the implicit definition is introduced) does not.