[GlobalISel] Multiple miscompiles due to unsound flag retention in combiners
- 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
Assessment
This issue has not been assessed yet.