[InstCombine] foldExtExtBinop introduces undef dependency on unused vector lanes
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`foldExtExtBinop` in InstCombine may introduces `undef` dependency when the vector operands contain undef in lanes that the original scalar code did not use.
Giving following IR:
```llvm
define <3 x i8> @src(<3 x i8> %0, <3 x i8> %1) {
%3 = extractelement <3 x i8> %0, i64 0
%4 = zext i8 %3 to i16
%5 = extractelement <3 x i8> %1, i64 0
%6 = zext i8 %5 to i16
%7 = add nuw nsw i16 %6, %4
%8 = extractelement <3 x i8> %0, i64 1
%9 = zext i8 %8 to i16
%10 = extractelement <3 x i8> %1, i64 1
%11 = zext i8 %10 to i16
%12 = add nuw nsw i16 %11, %9
%13 = lshr i16 %7, 8
%14 = add nuw nsw i16 %12, %13
%15 = extractelement <3 x i8> %0, i64 2
%16 = extractelement <3 x i8> %1, i64 2
%17 = add i8 %16, %15
%18 = lshr i16 %14, 8
%19 = trunc i16 %18 to i8
%20 = add i8 %17, %19
%21 = trunc i16 %7 to i8
%22 = insertelement <3 x i8> undef, i8 %21, i32 0
%23 = trunc i16 %14 to i8
%24 = insertelement <3 x i8> %22, i8 %23, i32 1
%25 = insertelement <3 x i8> %24, i8 %20, i32 2
ret <3 x i8> %25
}
```
the `opt -O3` will optimized it to:
```llvm
define <3 x i8> @tgt(<3 x i8> %0, <3 x i8> %1) local_unnamed_addr #0 {
%foldExtExtBinop = add <3 x i8> %1, %0
%3 = icmp ult <3 x i8> %foldExtExtBinop, %1
%add.narrowed.overflow = extractelement <3 x i1> %3, i64 0
%4 = extractelement <3 x i8> %0, i64 1
%5 = zext i8 %4 to i16
%6 = extractelement <3 x i8> %1, i64 1
%7 = zext i8 %6 to i16
%8 = add nuw nsw i16 %7, %5
%9 = zext i1 %add.narrowed.overflow to i16
%10 = add nuw nsw i16 %8, %9
%foldExtExtBinop2 = add <3 x i8> %1, %0
%11 = extractelement <3 x i8> %foldExtExtBinop2, i64 2
%12 = lshr i16 %10, 8
%13 = trunc nuw nsw i16 %12 to i8
%14 = add i8 %11, %13
%15 = trunc i16 %10 to i8
%16 = insertelement <3 x i8> %foldExtExtBinop, i8 %15, i64 1
%17 = insertelement <3 x i8> %16, i8 %14, i64 2
ret <3 x i8> %17
}
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) }
```
For the target, lane 0 of `%1` is used in multiple independent vector operations (`%foldExtExtBino`, `%add.narrowed.overflow`) allowing different concretizations of undef at each use.
Alive2 reports that the transformation `produces more undefined behavior in the target`
I have try to reduce the case, but it still timeout at online alive-tv: https://alive2.llvm.org/ce/z/B4nbt4
running alive-tv on local machine:
```shell
----------------------------------------
define <3 x i8> @src(<3 x i8> %#0, <3 x i8> %#1) {
#2:
%#3 = extractelement <3 x i8> %#0, i64 0
%#4 = zext i8 %#3 to i16
%#5 = extractelement <3 x i8> %#1, i64 0
%#6 = zext i8 %#5 to i16
%#7 = add nsw nuw i16 %#6, %#4
%#8 = extractelement <3 x i8> %#0, i64 1
%#9 = zext i8 %#8 to i16
%#10 = extractelement <3 x i8> %#1, i64 1
%#11 = zext i8 %#10 to i16
%#12 = add nsw nuw i16 %#11, %#9
%#13 = lshr i16 %#7, 8
%#14 = add nsw nuw i16 %#12, %#13
%#15 = extractelement <3 x i8> %#0, i64 2
%#16 = extractelement <3 x i8> %#1, i64 2
%#17 = add i8 %#16, %#15
%#18 = lshr i16 %#14, 8
%#19 = trunc i16 %#18 to i8
%#20 = add i8 %#17, %#19
%#21 = trunc i16 %#7 to i8
%#22 = insertelement <3 x i8> undef, i8 %#21, i32 0
%#23 = trunc i16 %#14 to i8
%#24 = insertelement <3 x i8> %#22, i8 %#23, i32 1
%#25 = insertelement <3 x i8> %#24, i8 %#20, i32 2
ret <3 x i8> %#25
}
=>
define <3 x i8> @tgt(<3 x i8> %#0, <3 x i8> %#1) nofree willreturn memory(none) {
#2:
%foldExtExtBinop = add <3 x i8> %#1, %#0
%#3 = icmp ult <3 x i8> %foldExtExtBinop, %#1
%add.narrowed.overflow = extractelement <3 x i1> %#3, i64 0
%#4 = extractelement <3 x i8> %#0, i64 1
%#5 = zext i8 %#4 to i16
%#6 = extractelement <3 x i8> %#1, i64 1
%#7 = zext i8 %#6 to i16
%#8 = add nsw nuw i16 %#7, %#5
%#9 = zext i1 %add.narrowed.overflow to i16
%#10 = add nsw nuw i16 %#8, %#9
%foldExtExtBinop2 = add <3 x i8> %#1, %#0
%#11 = extractelement <3 x i8> %foldExtExtBinop2, i64 2
%#12 = lshr i16 %#10, 8
%#13 = trunc nsw nuw i16 %#12 to i8
%#14 = add i8 %#11, %#13
%#15 = trunc i16 %#10 to i8
%#16 = insertelement <3 x i8> %foldExtExtBinop, i8 %#15, i64 1
%#17 = insertelement <3 x i8> %#16, i8 %#14, i64 2
ret <3 x i8> %#17
}
Transformation doesn't verify!
ERROR: Target's return value is more undefined
Example:
<3 x i8> %#0 = < #x00 (0), #x00 (0), #x03 (3) >
<3 x i8> %#1 = < undef, #x00 (0), #x03 (3) >
Source:
i8 %#3 = #x00 (0)
i16 %#4 = #x0000 (0)
i8 %#5 = #x03 (3) [based on undef]
i16 %#6 = #x0003 (3) [based on undef]
i16 %#7 = #x0003 (3) [based on undef]
i8 %#8 = #x00 (0)
i16 %#9 = #x0000 (0)
i8 %#10 = #x00 (0)
i16 %#11 = #x0000 (0)
i16 %#12 = #x0000 (0)
i16 %#13 = #x0000 (0)
i16 %#14 = #x0000 (0)
i8 %#15 = #x03 (3)
i8 %#16 = #x03 (3)
i8 %#17 = #x06 (6)
i16 %#18 = #x0000 (0)
i8 %#19 = #x00 (0)
i8 %#20 = #x06 (6)
i8 %#21 = #x03 (3) [based on undef]
<3 x i8> %#22 = < #x03 (3) [based on undef], #x03 (3) [based on undef], #x03 (3) [based on undef] >
i8 %#23 = #x00 (0)
<3 x i8> %#24 = < #x03 (3) [based on undef], #x00 (0), #x03 (3) [based on undef] >
<3 x i8> %#25 = < #x03 (3) [based on undef], #x00 (0), #x06 (6) >
Target:
<3 x i8> %foldExtExtBinop = < #x00 (0), #x00 (0), #x06 (6) >
<3 x i1> %#3 = < #x0 (0), #x0 (0), #x0 (0) >
i1 %add.narrowed.overflow = #x0 (0)
i8 %#4 = #x00 (0)
i16 %#5 = #x0000 (0)
i8 %#6 = #x00 (0)
i16 %#7 = #x0000 (0)
i16 %#8 = #x0000 (0)
i16 %#9 = #x0000 (0)
i16 %#10 = #x0000 (0)
<3 x i8> %foldExtExtBinop2 = < #x03 (3) [based on undef], #x00 (0), #x06 (6) >
i8 %#11 = #x06 (6)
i16 %#12 = #x0000 (0)
i8 %#13 = #x00 (0)
i8 %#14 = #x06 (6)
i8 %#15 = #x01 (1)
<3 x i8> %#16 = < #x00 (0), #x01 (1), #x06 (6) >
<3 x i8> %#17 = < #x00 (0), #x01 (1), #x06 (6) >
Source value: < #x03 (3) [based on undef], #x00 (0), #x06 (6) >
Target value: < #x00 (0), #x01 (1), #x06 (6) >
/home/xinlong/workspace/alive2/build/alive-tv --smt-to=300000 5.21s user 0.01s system 99% cpu 5.231 total
```
Should we insert a `freeze` inst for `%1` ?
testcase reduced from: https://github.com/llvm/llvm-project/blame/8edbf230980a038f120e754439a79cec68ad9356/llvm/test/Transforms/InstCombine/shift-add.ll#L728-L777
Contributor guide
Research direction
Start with foldExtExtBinop and the reduced testcase in llvm/test/Transforms/InstCombine/shift-add.ll around lines 728-777. Reproduce the transformation with opt -O3 and check it with Alive2, then trace how undef vector lanes are reused. Done means the InstCombine result no longer introduces undefined behavior that the source does not permit, with a regression test covering this case.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100