llvm / llvm/llvm-project

[GlobalISel] Multiple miscompiles due to unsound flag retention in combiners

Open
#210,470 4 comments 0 reactions 1 assignee Claimed by @Michael-Chen-NJU View on GitHub
backend:AArch64 llvm:globalisel miscompilation
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

There is an entire family of miscompiles all stemming from the fact that `GIMatchTableExecutorImpl` always propagates flags from the root instruction of the match to the new instruction(s) in GlobalISel TableGen-based pattern apply combiners, which is not _generally_ sound.

All of these result in a miscompile with `llc -mtriple=aarch64 -global-isel -O1` through different combiner rules, the functions are named to match the combiner rules they hit:

```llvm
define i32 @APlusBMinusCMinusB(i32 %a, i32 %b, i32 %c) {
%am = and i32 %a, 15
%bc = sub i32 %b, %c
%add = add i32 %am, %bc
%root = sub nuw i32 %add, %b
%r = and i32 %root, 255
ret i32 %r
}

define i32 @AMinusBMinusCMinusC(i32 %a, i32 %b, i32 %c) {
%am = and i32 %a, 15
%bc = sub i32 %b, %c
%s2 = sub i32 %am, %bc
%root = sub nuw i32 %s2, %c
%r = and i32 %root, 255
%r2 = add i32 %r, %bc
ret i32 %r2
}

define i32 @AMinusBPlusCMinusA(i32 %a, i32 %b, i32 %c) {
%cm = and i32 %c, 15
%s1 = sub i32 %a, %b
%s2 = sub i32 %cm, %a
%root = add nuw i32 %s1, %s2
%r = and i32 %root, 255
ret i32 %r
}

define i32 @AMinusBPlusBMinusC(i32 %a, i32 %b, i32 %c) {
%am = and i32 %a, 15
%s1 = sub i32 %am, %b
%s2 = sub i32 %b, %c
%root = add nuw i32 %s1, %s2
%r = and i32 %root, 255
ret i32 %r
}

define i32 @APlusBMinusAplusC(i32 %a, i32 %b, i32 %c) {
%bm = and i32 %b, 15
%add1 = add i32 %a, %c
%s1 = sub i32 %bm, %add1
%root = add nuw i32 %a, %s1
%r = and i32 %root, 255
ret i32 %r
}

define i32 @APlusBMinusCPlusA(i32 %a, i32 %b, i32 %c) {
%bm = and i32 %b, 15
%add1 = add i32 %c, %a
%s1 = sub i32 %bm, %add1
%root = add nuw i32 %a, %s1
%r = and i32 %root, 255
ret i32 %r
}

define i32 @AMinusBMinusC(i32 %b, i32 %c) {
%cm = and i32 %c, 15
%bc = sub i32 %b, %cm
%root = sub nuw i32 256, %bc
%cmp = icmp uge i32 %root, 256
%r = zext i1 %cmp to i32
ret i32 %r
}

define i32 @add_shift(i32 %x, i32 %y) {
%xm = and i32 %x, 15
%neg = sub i32 0, %y
%shl = shl i32 %neg, 4
%root = add nuw i32 %xm, %shl
%r = and i32 %root, 255
ret i32 %r
}
```

This is not an exhaustive list; only what I've been able to prove to result in a miscompile.

Concrete incorrect result examples (these deliberately produce wrap on a non-nuw/nsw instruction but not on the nuw/nsw flagged one):
| | SDAG | GISel |
|-|-----|-----|
| APlusBMinusCMinusB(1,2,7) | 250 | -6 |
| AMinusBMinusCMinusC(1,10,2) | 255 | -1 |
| AMinusBPlusCMinusA(10,10,1) | 247 | -9 |
| AMinusBPlusBMinusC(1,200,100) | 157 | -99 |
| APlusBMinusAplusC(5,1,3) | 254 | -2 |
| APlusBMinusCPlusA(5,1,3) | 254 | -2 |
| AMinusBMinusC(6,1) | 0 | 1 |
| add_shift(1,1) | 241 | -15 |

Godbolt side by side GISel vs SDAG: https://godbolt.org/z/98Ynn8z6b

This is essentially the more general form of issue #203972 and was previously discussed in #70780

There's an additional bug as noted in https://github.com/llvm/llvm-project/issues/203972#issuecomment-4711820736 that the root instruction flags are always unconditionally copied and _using the documented syntax to drop a flag doesn't work_ - though the bug is even worse than that, because it copies the actual _entire flag word_ even if some of those flags are not even valid for the target instruction, I have not checked if that can be used to create further breakage if another combine rule triggers later.

Given the size of the footgun, I think the right thing to do would be to just drop all poison-generating flags by default unless the rule explicitly asks for flags to be retained - the alternative is fixing the explicit flag dropping (easy) and then auditing every rule if it needs to drop flags or not (error-prone, I think).

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.