<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/114354>114354</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
[InstCombine] wrong folding of `(lshr (add (zext X), (zext Y)), K)` for undefined inputs
</td>
</tr>
<tr>
<th>Labels</th>
<td>
new issue
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
bongjunj
</td>
</tr>
</table>
<pre>
https://github.com/llvm/llvm-project/blob/6bf214b7c6d74ec581bc52a9142756a1d1df6df0/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp#L964-L978
Alive2 report: https://alive2.llvm.org/ce/z/18Sfgb
```llvm
----------------------------------------
define i4 @not_bool_add_lshr.2(i2 %a, i2 %b) {
#0:
%#1 = mul i2 %a, 3
%zext.a = zext i2 %#1 to i4
%zext.b = zext i2 %b to i4
%add = add nsw i4 %zext.a, %zext.b
%lshr = lshr i4 %add, 2
ret i4 %lshr
}
=>
define i4 @not_bool_add_lshr.2(i2 %a, i2 %b) {
#0:
%#1 = sub i2 0, %a
%add.narrowed = sub i2 %b, %a
%add.narrowed.overflow = icmp ult i2 %add.narrowed, %#1
%lshr = zext i1 %add.narrowed.overflow to i4
ret i4 %lshr
}
Transformation doesn't verify!
ERROR: Target's return value is more undefined
Example:
i2 %a = undef
i2 %b = #x0 (0)
Source:
i2 %#1 = #x0 (0) [based on undef value]
i4 %zext.a = #x0 (0)
i4 %zext.b = #x0 (0)
i4 %add = #x0 (0)
i4 %lshr = #x0 (0)
Target:
i2 %#1 = #x1 (1)
i2 %add.narrowed = #x0 (0)
i1 %add.narrowed.overflow = #x1 (1)
i4 %lshr = #x1 (1)
Source value: #x0 (0)
Target value: #x1 (1)
----------------------------------------
define i64 @lshr_16_to_64_add_zext_basic.2(i16 %a, i16 %b) {
#0:
%zext.a = zext i16 %a to i64
%#1 = mul i16 %a, %b
%zext.b = zext i16 %#1 to i64
%add = add i64 %zext.a, %zext.b
%lshr = lshr i64 %add, 16
ret i64 %lshr
}
=>
define i64 @lshr_16_to_64_add_zext_basic.2(i16 %a, i16 %b) {
#0:
%#1 = add i16 %b, 1
%add.narrowed = mul i16 %a, %#1
%add.narrowed.overflow = icmp ult i16 %add.narrowed, %a
%lshr = zext i1 %add.narrowed.overflow to i64
ret i64 %lshr
}
Transformation doesn't verify!
ERROR: Target's return value is more undefined
Example:
i16 %a = undef
i16 %b = #x0000 (0)
Source:
i64 %zext.a = #x0000000000000000 (0) [based on undef value]
i16 %#1 = #x0000 (0)
i64 %zext.b = #x0000000000000000 (0)
i64 %add = #x0000000000000000 (0)
i64 %lshr = #x0000000000000000 (0)
Target:
i16 %#1 = #x0001 (1)
i16 %add.narrowed = #x0000 (0)
i1 %add.narrowed.overflow = #x1 (1)
i64 %lshr = #x0000000000000001 (1)
Source value: #x0000000000000000 (0)
Target value: #x0000000000000001 (1)
----------------------------------------
define i32 @lshr_32_add_zext_trunc.2(i32 %a, i32 %b) {
#0:
%zext.a = zext i32 %a to i64
%zext.b = zext i32 %b to i64
%add = add nsw nuw i64 %zext.a, %zext.b
%#1 = add i64 %zext.b, %add
%trunc.add = trunc i64 %#1 to i32
%shr = lshr i64 %add, 32
%trunc.shr = trunc i64 %shr to i32
%ret = add nuw i32 %trunc.add, %trunc.shr
ret i32 %ret
}
=>
define i32 @lshr_32_add_zext_trunc.2(i32 %a, i32 %b) {
#0:
%add.narrowed = add i32 %a, %b
%add.narrowed.overflow = icmp ult i32 %add.narrowed, %a
%trunc.add = add i32 %b, %add.narrowed
%trunc.shr = zext i1 %add.narrowed.overflow to i32
%ret = add nuw i32 %trunc.add, %trunc.shr
ret i32 %ret
}
Transformation doesn't verify!
ERROR: Target is more poisonous than source
Example:
i32 %a = undef
i32 %b = #x00000000 (0)
Source:
i64 %zext.a = #x0000000000000000 (0) [based on undef value]
i64 %zext.b = #x0000000000000000 (0)
i64 %add = #x0000000000000000 (0)
i64 %#1 = #x0000000000000000 (0)
i32 %trunc.add = #x00000000 (0)
i64 %shr = #x0000000000000000 (0)
i32 %trunc.shr = #x00000000 (0)
i32 %ret = #x00000000 (0)
Target:
i32 %add.narrowed = #x00000000 (0)
i1 %add.narrowed.overflow = #x1 (1)
i32 %trunc.add = #xffffffff (4294967295, -1)
i32 %trunc.shr = #x00000001 (1)
i32 %ret = poison
Source value: #x00000000 (0)
Target value: poison
Summary:
0 correct transformations
3 incorrect transformations
0 failed-to-prove transformations
0 Alive2 errors
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzEWN-P2jgQ_mvMi7UoGSeBPPCwLUU6XaWT2j7cPSEndiBViJHtsG3_-pMdE5xAArvV3iEE-fHNN54Z-5vEVKlyV3O-QvEHFK9ntNF7IVeZqHffm_r7LBPs52qv9VEh8oxgg2CzK_W-yea5OCDYVNXp_Pd0lOI7zzWCTVaJDMEmyQoIo2yRJ2wR8TxehlkeA03DCBZxQkMWsiJhReDxlMbum6S1KoQ8KASbP2qlP4pDVta8f_Z1XxZazfPjEQH5nCbR0-d0sUTBGgXP7e9zVZ44YMmPQmpEnnE_EGpvz43ruZA7BJvcuPiFYBMuvxa7zOdyv0nQfu147aWnBz8tmvGirDkuI4yioBZ6mwlRbSlj20rt5RwQLEvACGKK4CNuDzMEKUaLD24IQAITgj3B5j4CEmJE1vjQVNizJg6DIP7Ff-g5tSBz6FDWUAtcRh6bhWZDaHaFo4xZkPmv1YsN6ezIeO-oPBsTozWyB60FZczA4QyTXLs7BuRiXqzdAVkj8ul9UulnUjWZsQhcILQf97ymUooXznxsy96DD9BzceKyqMSLNSvzwxE31TnBPtDRmNHcSl5blnCcvleqyXx2K43qUtSYCa5qBAuNT1yWxU8EoT_7P3358tcXs46-UbnjGsFCGfpG1vhEq4bjUuGDkBw3dVsc1rP-QQ_HincJd3HbkKyBf7mdgAjIjwAjWAYIUp_rq2hkPqTqqjcwS1H8IaOKMyzq1lM7XBS7LPhTd8yvhxkdWzehpwFdIUfDc_mdCM9UfxleiK_m0OgQJubNGPn1qAeIthwuq-T5lt82pD5kwOL_vk1VE6sFZqTbMNlqsU0iKwimbNuMqjJvZSFMLrrQHt_T2CsBdRR2rSXRqBp7nqyXCZ1toZ0mJ2Nia6N8pdImvtSGiQNaaUheo7Xvl-AubTbEzuYjDqe090aOB6r5iAA7gmsF9oT8deqb9OV3NMf_q_6ep_BQgF3yLwoSBA-JcHJTRgef18iytyLGx-K7zR5w69n0lPoRg75yT1rcFvLbEQ319no-TsX_BkG_H80jAj8Z_y29n_bx-_JPoFMnAhdd0rKpnS4R74GQPPRwfSX8juJao68EnXhPzqNqbh6d6-blMVXvi6Q_8c-CxZgHbwM_e7NnZ6uuzRDwDCaaRg_XEp_RPWJzsceLIDYa2MVrYm0z0w3PDb5j7Wlni5VcP9Ce3mMCXC1Dm3uPZ9DXH2k4ZOyRn45Wz_PqFftiP1ach9rVuxfrt_pc19aOolSiFo3Cek9rrNr-M9XiyMg7Bhm-ZExo-Lu3uf-wgV310gmLQd3v5Mpb_m_gv2V2E36enfeKNmy81yvunr83tNWxjBXuY-ARpFGaLCCNzUJ6GrG-kY_bzs75aJfG_WY93aR9FsfVHA5U_vQkMcC5kJLnGuveolZnAMFlfQcS4IKWFWdPWjwdpTjxcaDbw-NSCukud5twM7YiLCUpnfFVuCABidJ0CbP9Kg0iDhFjJGAsIkBzuoAoYGFAwijMOczKFQQQmfMgihKAeRwHiywni7gIkzhjGYoCfqBl1e0OzkqlGr4Kw4jE0ayiGa-U3TQFqPkLtncRAIrXM7my26FZs1OmG5VKqwuNLnVld1v9fc14jV-kqHe4EBUr6x0WBTYhwrJ9RoOlnU6wtGr-t6mfVeH2_B97bi_9af6TABdCXl4CcFkfG61mjaxev5VrA1MINi7y0wr-DQAA___ZLOon">