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

    <tr>
        <th>Summary</th>
        <td>
            "Instruction does not dominate all uses" after Complex Deinterleaving Pass
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

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

<pre>
    For the following IR:
```llvm
target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "aarch64-none-linux-gnu"

define void @foo() #0 {
bb:
 br label %bb173

bb173:                                            ; preds = %bb173, %bb
  %phi177 = phi <2 x i32> [ %add190, %bb173 ], [ zeroinitializer, %bb ]
  %phi178 = phi <2 x i32> [ %add187, %bb173 ], [ zeroinitializer, %bb ]
  %add185 = add <2 x i32> %phi178, <i32 1, i32 1>
  %add186 = add <2 x i32> %phi177, <i32 1, i32 1>
  %shufflevector = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer
  %add187 = add <2 x i32> %add185, %shufflevector
 %shufflevector189 = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer
  %add190 = add <2 x i32> %add186, %shufflevector189
  br i1 poison, label %bb193, label %bb173

bb193:                                            ; preds = %bb173
  %add194 = or <2 x i32> %add190, %add187
  store volatile i32 0, ptr null, align 4
  unreachable
}

attributes #0 = { "target-cpu"="neoverse-v1" }
```
Complex deinterleaving produced broken code:
```
identifyNode on   %add187 = add <2 x i32> %add185, %shufflevector /   %add190 = add <2 x i32> %add186, %shufflevector189
identifyNode on   %add185 = add <2 x i32> %phi178, <i32 1, i32 1> /   %add186 = add <2 x i32> %phi177, <i32 1, i32 1>
identifyNode on   %phi178 = phi <2 x i32> [ %add187, %bb173 ], [ zeroinitializer, %bb ] / %phi177 = phi <2 x i32> [ %add190, %bb173 ], [ zeroinitializer, %bb ]
identifyNode on <2 x i32> <i32 1, i32 1> / <2 x i32> <i32 1, i32 1>
identifyNode on   %shufflevector = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer / %shufflevector189 = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer
Identified reduction starting from instructions:   %add187 = add <2 x i32> %add185, %shufflevector / %add190 = add <2 x i32> %add186, %shufflevector189
Verifying parent property of node %bb173
Verifying parent property of node %bb
*** IR Dump After Complex Deinterleaving Pass (complex-deinterleaving) ***
define void @foo() #0 {
bb:
  %0 = call <4 x i32> @llvm.experimental.vector.interleave2.v4i32(<2 x i32> zeroinitializer, <2 x i32> zeroinitializer)
  br label %bb173

bb173: ; preds = %bb173, %bb
  %1 = phi <4 x i32> [ %0, %bb ], [ %4, %bb173 ]
  %shufflevector = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer
  %2 = call <4 x i32> @llvm.experimental.vector.interleave2.v4i32(<2 x i32> <i32 1, i32 1>, <2 x i32> <i32 1, i32 1>)
  %3 = add <4 x i32> %1, %2
  %4 = add <4 x i32> %3, %5
  %shufflevector189 = shufflevector <2 x i32> zeroinitializer, <2 x i32> zeroinitializer, <2 x i32> zeroinitializer
  %5 = call <4 x i32> @llvm.experimental.vector.interleave2.v4i32(<2 x i32> %shufflevector, <2 x i32> %shufflevector189)
  br i1 true, label %bb193, label %bb173

bb193:                                            ; preds = %bb173
  %6 = call { <2 x i32>, <2 x i32> } @llvm.experimental.vector.deinterleave2.v4i32(<4 x i32> %4)
  %7 = extractvalue { <2 x i32>, <2 x i32> } %6, 0
  %8 = extractvalue { <2 x i32>, <2 x i32> } %6, 1
  %add194 = or <2 x i32> %8, %7
  store volatile i32 0, ptr null, align 4
  unreachable
}
... eventually
Instruction does not dominate all uses!
  %4 = call <4 x i32> @llvm.experimental.vector.interleave2.v4i32(<2 x i32> %shufflevector, <2 x i32> %shufflevector189)
  %3 = add <4 x i32> %2, %4
in function foo
LLVM ERROR: Broken function found, compilation aborted!
```

Godbolt link https://godbolt.org/z/7zbbePPd6

Bisect pointed to https://github.com/llvm/llvm-project/commit/c15557d64eb985bd88c0db3c85a66d8267ecdb29 by @igogo-x86 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMWE1v2zgT_jX0ZSBDIvV58MGJ6xcF-u4WWaB3Shzb3NKkQFHeJL9-QUlOZTlp3LrZJnBkfgyHMw85z4zMm0ZuNeKCJDckWc1463bGLgTXUvG9mpVGPCzWxoLbIWyMUuYfqbfw8Y6wJQlXJFySNOw_Sh32_ZDjdosOBHdc8QfTOiBsBYRSDPaELTGQOWFL_89oIKOUsGX38L00JmyZxoGMqBeIaB5oRvuxv7qe9MNBTbsFg55BVzdHCaUndjgra4VHGzi31S6NA200Bkrq9j7Y6vZpTf8UuJEa4WCkABKHG2MIzQktgFAWAsluerGyfIIBSguKl6iA0KQso4yN9fUDbAk_8EfYDdQWRTNYPmilt3172NZ36p2MsqwTq3cSCLulcA_So_MBSHLjZbgQURE-rY4yBiRZdf3kBh7RGqmlk1zJR7RPYp3MZKP89Y3y7MqNOiVJtxEXYrrR0ZBuNbuVjELk232DfZgqSl9RlF2gqNm1m43CA1bO2E7fdGSs-Tk3rxOYuJS97FKP3YDsiZGDkulwlBe_3aEifMWh9DmHorw46iktyAhqIxujveg4Fgs2HTmLzuIXRefEq7ibPUNzGo9DzAyLG2es5x7FnVTYXcZOsHYWdKuUb3Mltxri45JWW-TVjpcKB8ey1dhD7pyVZeuwGRjM25z5eKU9SQZV3XEgWxFKNZoD2gaDQ0QohW-6jlTfd2_NvlZ4DwKldmgV8oPPDbU1oq1QQGnNV9RQGYHn2aLvSoHayc3DH0YgGA1XXnAgdA2_6k69bNtPE9Opfdfy0rMGvi1Fdw78Rxln6t5kk5fgfV3sO-j9ZpY_wvte6Pljj5FEARZFWzlpNDSOW-cDfWPNHqRunO1nmp5Cr4_gXxO_X9DKzUPHSNyidp6YarTuAcwGtD_1U9a-UH7gMTp84OMdrNp9DcuNQwtHTlydcuJn3njmzat-OjilzL6wPOr82QLUm9cjVnGlPGTxCLK4q8_neF-jlXvUjqt5D9j8yRSk80PsF_jS-7rrNc7LF5TFl9e60Zh04jPSCU-JZCAbQpP4jIjeY21H3-b8nmXBM7OelypG5rFxQMYnARkN-NKRePyy-PFsk5eO4XcXpckbncS0JD8_hWf4jE7KXGdbfBdFbjpCyZeTY0-ecS1bfRe-ESueAnh6d-LTS9nnGbx3llfuwFWLF9tCky6FhCNt-dXaostfAvIhCt6m9J_P54AH1K7lSj0MGf1bugZhsAFtHAizl5o7BH-ObYMNodFZGL-7UPg-H9EB2gEnqWHT6t5vn0y7wU-fvvwfPtzd_Xnn4-Kmf10ZibVaeC0-aUt_IkYDL411KJ4AmrzP9M__GVEa5UBJ_RV2ztW-MiJ0Teh620_Njd0Sun4kdJ09liV-_izSsYYb2WDl_OusdijAmaka6XZtOa_MntB198Nb_xXU1vyNlSN0XZn9XnaNKEmSTKQxlkWelCLPq1CUrMoTnqYip2mGlShpAeWDP1G5NVsT3OcpzMSCiYIVfIaLKC0YZUmYxrPdIo6qjRBxlRZYJTEraFgio6IsShbmmzyfyQUNKQtzmkdJGNNoLngRF2kaFkyEJcaMxCHuuVTz7v4Yu53JpmlxkSZhHM86EmuOP0naRedZ2W4bf-Fk45pvy5x0CheE0ksvNgX-WqE2a61a_DDenQMNoevOh38DAAD__0ul_f8">