llvm / llvm/llvm-project

[SDAG] scalarizeExtractedBinOp incorrectly applying rotl to extended bitwidth type

Open
#221,100 1 comment 0 reactions 0 assignees View on GitHub
generated by fuzzer llvm:SelectionDAG miscompilation
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

The following IR:
```llvm
target triple = "riscv64-unknown-linux-gnu"

define i64 @do_stuff() {
entry:
%vec.zero = insertelement <2 x i16> zeroinitializer, i16 0, i32 0
%vec.const = xor <2 x i16> %vec.zero,
%vec.shifted = call <2 x i16> @llvm.fshl.v2i16(<2 x i16> %vec.const, <2 x i16> %vec.const, <2 x i16> )

%a = extractelement <2 x i16> %vec.shifted, i32 0
%az = zext i16 %a to i64
%ax = xor i64 %az, 1

%b = extractelement <2 x i16> %vec.shifted, i32 1
%bz = zext i16 %b to i64

%r = or i64 %ax, %bz
ret i64 %r
}

declare <2 x i16> @llvm.fshl.v2i16(<2 x i16>, <2 x i16>, <2 x i16>)
```

(apologies that the repro is a bit hefty. I couldn't seem to reduce it further w/ llvm-reduce or manually. It's likely just padding to trigger at the right spot in the backend)

When compiled w/ `llc -O0 -mattr=+m,+v`:
```asm
do_stuff:
lui a0, 15
addi a0, a0, -1
ret
```

compare that to `llc -O0 -mattr=+m`:
```asm
do_stuff:
lui a0, 15
addi a0, a0, -106
ret
```

which matches what `opt -O2` folds it into:
```llvm
define noundef i64 @do_stuff() local_unnamed_addr #0 {
entry:
ret i64 61334
}
```

Godbolt link: https://godbolt.org/z/aWW1cKM6E

The problem seems to stem from `scalarizeExtractedBinOp`, which sees this graph:
```
SelectionDAG has 17 nodes:
t0: ch,glue = EntryToken
t8: v2i16 = BUILD_VECTOR Constant:i64<-7273>, Constant:i64<-10240>
t11: v2i16 = BUILD_VECTOR Constant:i64<0>, Constant:i64<12>
t12: v2i16 = rotl t8, t11
t31: i64 = extract_vector_elt t12, Constant:i64<1>
t33: i64 = and t31, Constant:i64<65535>
t26: i64 = or t33, Constant:i64<58262>
t22: ch,glue = CopyToReg t0, Register:i64 $x10, t26
t23: ch = RISCVISD::RET_GLUE t22, Register:i64 $x10, t22:1
```

And then does this:
```
Combining: t31: i64 = extract_vector_elt t12, Constant:i64<1>
... into: t34: i64 = Constant<-41938945>
```

This is pulling the desired lane out from the vector, and applying `rotl` to it individually. However, it seems to be doing so with the `i64` type, whereas the vector does so in `i16` (or `v2i16`). This causes a subtle difference in semantics; in this case we are meant to do:
```
rotl(0xD800, 12) => 0x0D80
= 3456
```
but instead we do
```
rotl(0xFFFF'FFFF'FFFF'D800, 12) => 0xFFFF'FFFF'FD80'0FFF
= -41938945
```

Which ends up causing the difference in later constant folds. I don't know what a fix looks like (the transform seems like it'd be safe if the extract and operation were done keeping the vector element type and then extended after, but I don't know if that's possible at this stage in the pipeline)

Relevant code:
https://github.com/llvm/llvm-project/blob/f111407c0502851409a887c8e5dea4a3ec190d4e/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp#L25576

I've only reproduced this on RISC-V, but I assume it can occur on other backends as well. I've verified this still occurs on the latest trunk, adf79c9ab28991d66f7d765437fb112fbbe00ec9

A bisect of this led to 4a6435397ba587022ecafa772cd504b8659da2fb but I don't think that's the cause, just a commit that uncovered an existing issue

For disclosure: this bug was found by a fuzzer meant to test code gen, which was written with LLM assistance. But, I manually reproduced the issue, and the analysis here is my own

Contributor guide

Open the contributing guide

Research direction

Start in llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp at scalarizeExtractedBinOp and reproduce the issue with the provided IR using llc -O0 -mattr=+m,+v and +m. Compare the vector-enabled result with the scalar result and opt -O2's folded value; done means the vector-enabled compilation preserves the expected i16 rotate semantics and returns the same result.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.