<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/153808>153808</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            Type legalizing emits invalid `extract_subvector` node
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            backend:AMDGPU,
            llvm:SelectionDAG
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          lialan
      </td>
    </tr>
</table>

<pre>
    # Problem
Hitting assertion:
```bash
llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:25712: llvm::SDValue narrowExtractedVectorBinOp(llvm::EVT, llvm::SDValue, unsigned int, const llvm::SDLoc &, llvm::SelectionDAG &, bool): Assertion `(Index % VT.getVectorNumElements()) == 0 && "Extract index is not a multiple of the vector length."' failed.
```

When compiling the attached program. 

[bug.txt](https://github.com/user-attachments/files/21797144/bug.txt)

# To reproduce:

```
llc --march=amdgcn ./bug.txt
```

confirmed that at commit `5d115e49ba70` the problem still exists.

# Initial triage

Initial triage posted here: https://github.com/iree-org/iree/issues/21646#issuecomment-3190415870

> Problem is that when doing dagcombine we hit this assertion: https://github.com/llvm/llvm-project/pull/138279/files#diff-d0eb75096db76ab253fc7f8ae6343c4b4516fc619d851898cbdac1a5bf481941R25186-L25197

> The culprit is this node:
```
t544: v32f32 = fdiv # D:1 t541, t464
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>
```

> where index `16` cannot be divided by vector length `3` -- which is a hard requirement for `extract_subvector`: the index must be a multiple of the minimum number of elements in the result type. Should look for the reason why `v3f32` is a legalized type at this stage.


# Simple problem analysis

The input program is trying to do reduction of a vector using `@llvm.vector.reduce.fadd.v3f32` in a loop. The loop is unrolled. And then type legalizer turns the residual extraction:
```
t370: v51f32 = fdiv # D:1 t369, t12 // both operands are of type v51f32
...
t431: v3f32 = extract_subvector # D:1 t370, Constant:i32<48>
```

into:
```
t544: v32f32 = fdiv # D:1 t541, t464 // both operands are of type v32f32
...
t557: v3f32 = extract_subvector # D:1 t544, Constant:i32<16>
```

without checking if it is possible to form a valid `extract_subvector`.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy8Vl1v3LoR_TXcF2IFiRT18bAPitfrXuC2DWrXfSwocSSxoUiVovzRX18MtRt74yRoUOACBiRzh8NzZs4ZUS6LHizAgYhPRBx3cg2j8wejpZF21zr1eiCM08_etQYmkjZ_0iFoO1C5LOCDdpbwhqQNKdLtr5XLSNLGmKdpP3v3L-gCYSf8Fx-6Jex04xTcgSXsdA8GOkxybO4IOx2buxs3tdqCT7p5JrxhoswY4Q2NCXhDeHN_fJRmBWql9-759iV42QVQj9AF5z9p-9eZsOot_PbxgbCbj_txcbWRvKLaBvy_c3YJV6G_u44SVnyT4R3qy6-tc4awGqE2l8pQrAirfrMKXihhgj4-JAOEDelf1unWwAQ2LIRVuJXVlPAj4UeablkLShg7E6Q6ZtELtS5QSafVBD0boK6nYQT6FJNSA3YIY0IYI6ykvdQGVPK-PfieNv8YwdLOTbM22EtMIEOQ3QiKzt4NXk4J3UKJ-NSuQxJeAhFHwqoxhHnBOrATYadBh3Ftk85hd9cF_H7Lc-Z16rUBfLKsrMsszwk7XbKx-nwA4_TBUQ-zd2rt4Kyna8zGdHS_n6TvRsKPclJDZ2nyLtsHip2zvfYTKBpGGagMyHfSAZsiVJYJyOtWlrgh8p83hdMlaGMovOglLMkbwt-sDloaGryWA2zr12t0dksARUfwyIH-pFDaA-ydH86v-FiW9VyoIi8I43EBEYMNe57VaZ6JqjxzI_z24khURCT4jC1VDtup5NBtNqLPQEcdaBj1cuXYn6G7ePXawfNqDGGnjFesrN86y5Xu-71KoS1FWheqLQvZMsH7ruwrCQXPeZe3uciKviuyWlUiq-qqa5XsMinaPq-yOs_-xkRWFfvfmcjq8o3jwwi0W83sddh4Rvkr-GbkkLQJIs-R1hNnPWfoI9or_USxdUfCm4wGkWdo1JAXOUmbJEniNlFu2y67YLPbP5e1PVvqKkWOKW5wTEgbCG80Z4TfZAXhtx8liBSeUQ5n85IizQrUWycturgFqvSTVqBo-3rtYIzlGLrf0-dRdyPyl3SUXlEP_161j6OD9giwSD-gRgy8icLezp7WJR74cXJM2uppnahdpxY8rsJ5LlFtY4SHZTWBhtcZEno_utUoapz7Ek_fAuTiLH0eXxFMLCZij5ANDNLo_6APX2ccM1sblyAHuPhrs9i9nhDWxYjSSvO66GULeIhM5jVc5lMUhH-N48tRhQNErXEqIwV5Kee6YASWI09R0cm2nsRoSHqpVPIG2CJg5-YkSg_f8JjVemdwkNLG4jgBu3G5UPM0rN4ul1pptUpzEdLHDyTKjpexPU8i-5FaeVFHtWaMbhalrQsjdTN4adVCpd8aiDi2NG-iznn2C6JGLN8TdV59V9TaBvf_-u9_oBTz_EE-fdZhdGug3QjdF5SL7uk2cWa3LLo1gBLrnZ9QV9Jo9SPPJTt14KrmtdzBISuFYEVRZfVuPHCZV20vRAstVEUteqEyBqXo27ZuS8l3-sBSJtIqE1meFqJO6lTUoi15KrI6rbOK5ClMUpskytj5YRe_EYdM8Cqtdka2YJZ4jWOsXYd4BbjBd9l9AasIb5o_H-8-__3rD-cLzfUdjOEl0B_i8G_XYUHbxE_h11ODDgYOD-8MgCWDSceB8dPyxOG9W705_PLn5-sH8kz36cD-GwAA__9qDU_L">