llvm / llvm/llvm-project

[InstCombine] Incorrectly transformed of Freezing early

Open
#193,698 2 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine miscompilation
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

InstCombine seems to perform an incorrect transform for the following code:

```llvm
declare <1 x double> @dummy(<1 x double>)

define <2 x double> @pr25999_phis2_reduced(i1 %c, <1 x double> %a, <2 x double> %b) {
bb1:
br i1 %c, label %bb2, label %bb3

bb2: ; preds = %bb1
%r = call <1 x double> @dummy(<1 x double> poison)
br label %bb3

bb3: ; preds = %bb2, %bb1
%t1 = phi <1 x double> [ %a, %bb1 ], [ %r, %bb2 ]
%t2 = phi <2 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
%d = fadd <1 x double> %t1, %t1
%t3 = extractelement <1 x double> %d, i32 0
%freeze.ins = freeze double %t3
%t4 = insertelement <2 x double> %t2, double %freeze.ins, i32 1
ret <2 x double> %t4
}
```

The `opt -O3` will transform it to:

```llvm
declare <2 x double> @dummy(<2 x double>)

define <4 x double> @pr25999_phis2(i1 %c, <2 x double> %a, <4 x double> %b) {
br i1 %c, label %bb2, label %bb3

bb2: ; preds = %bb1
%r = call <2 x double> @dummy(<2 x double> poison)
br label %bb3

bb3: ; preds = %bb2, %bb1
%t1 = phi <2 x double> [ %a, %bb1 ], [ %r, %bb2 ]
%t2 = phi <4 x double> [ %b, %bb1 ], [ zeroinitializer, %bb2 ]
%t1.fr = freeze <2 x double> %t1
%d = fadd <2 x double> %t1.fr, %t1.fr
%0 = shufflevector <2 x double> %d, <2 x double> poison, <4 x i32>
%t4 = shufflevector <4 x double> %t2, <4 x double> %0, <4 x i32>
ret <4 x double> %t4
}
```

The incorrect point might be the order of the `fadd` and `freeze`, we assuming `%t1 = < poison, #x7ff1000000000000 (SNaN) >`, for original code:

```llvm
%d = fadd <2 x double> %t1, %t1
%t3 = extractelement <2 x double> %d, i32 0
%freeze.ins = freeze double %t3
```

It performs `poison + poison` in `%d`.

while, the optimized code trying add to freeze value of `posion` in following code:

```llvm
%t1.fr = freeze <2 x double> %t1
%d = fadd <2 x double> %t1.fr, %t1.fr
%0 = shufflevector <2 x double> %d, <2 x double> poison, <4 x i32>
```

I am trying verify it using online alive2, but it exit with time out: https://alive2.llvm.org/ce/z/97tvEz

The verify report of running alive at local machine:
```
----------------------------------------
declare <1 x double> @dummy(<1 x double>)

define <2 x double> @pr25999_phis2_reduced(i1 %c, <1 x double> %a, <2 x double> %b) {
bb1:
br i1 %c, label %bb2, label %bb3

bb2:
%r = call <1 x double> @dummy(<1 x double> poison)
br label %bb3

bb3:
%t1 = phi <1 x double> [ %a, %bb1 ], [ %r, %bb2 ]
%t2 = phi <2 x double> [ %b, %bb1 ], [ { 0.000000, 0.000000 }, %bb2 ]
%d = fadd <1 x double> %t1, %t1
%t3 = extractelement <1 x double> %d, i32 0
%freeze.ins = freeze double %t3
%t4 = insertelement <2 x double> %t2, double %freeze.ins, i32 1
ret <2 x double> %t4
}
=>
declare <1 x double> @dummy(<1 x double>)

define <2 x double> @pr25999_phis2_reduced(i1 %c, <1 x double> %a, <2 x double> %b) {
bb1:
br i1 %c, label %bb2, label %bb3

bb2:
%r = call <1 x double> @dummy(<1 x double> poison)
br label %bb3

bb3:
%t1 = phi <1 x double> [ %a, %bb1 ], [ %r, %bb2 ]
%t2 = phi <2 x double> [ %b, %bb1 ], [ { 0.000000, 0.000000 }, %bb2 ]
%t1.fr = freeze <1 x double> %t1
%d = fadd <1 x double> %t1.fr, %t1.fr
%#0 = shufflevector <1 x double> %d, <1 x double> poison, 0, 4294967295
%t4 = shufflevector <2 x double> %t2, <2 x double> %#0, 0, 2
ret <2 x double> %t4
}
Transformation doesn't verify!

ERROR: Target's return value is more undefined

Example:
i1 %c = #x0 (0)
<1 x double> %a = < poison >
<2 x double> %b = < #x0000000000000003 (0.000000000000?), poison >

Source:
>> Jump to %bb3
<1 x double> %t1 = < poison >
<2 x double> %t2 = < #x0000000000000003 (0.000000000000?), poison >
<1 x double> %d = < poison >
double %t3 = poison
double %freeze.ins = #x0000000000000003 (0.000000000000?)
<2 x double> %t4 = < #x0000000000000003 (0.000000000000?), #x0000000000000003 (0.000000000000?) >

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 > size: 0 align: 1 alloc type: 0 alive: false address: #x0
Block 1 > size: 0 align: 1 alloc type: 0 alive: true address: #x8

Target:
>> Jump to %bb3
<1 x double> %t1 = < poison >
<2 x double> %t2 = < #x0000000000000003 (0.000000000000?), poison >
<1 x double> %t1.fr = < #x7ff0608280000001 (SNaN) >
<1 x double> %d = < #x7ff0608280000001 (SNaN) >
<2 x double> %#0 = < #x7ff0608280000001 (SNaN), poison >
<2 x double> %t4 = < #x0000000000000003 (0.000000000000?), #x7ff0608280000001 (SNaN) >

TARGET MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 > size: 0 align: 1 alloc type: 0 alive: false address: #x0
Block 1 > size: 0 align: 1 alloc type: 0 alive: true address: #x8
Source value: < #x0000000000000003 (0.000000000000?), #x0000000000000003 (0.000000000000?) >
Target value: < #x0000000000000003 (0.000000000000?), #x7ff0608280000001 (SNaN) >

Summary:
0 correct transformations
1 incorrect transformations
0 failed-to-prove transformations
0 Alive2 errors
```

Contributor guide

Open the contributing guide

Research direction

Start by reproducing the reported LLVM IR with opt -O3 and inspect the InstCombine transformation that moves freeze before fadd. Use the supplied Alive2 comparison to confirm the poison and SNaN behavior. Done means the transformation no longer produces a more-undefined result and the verification succeeds.

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
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.