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

    <tr>
        <th>Summary</th>
        <td>
            [MachinePipeliner] Phi-Phi dependencies are handled incorrectly
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          kasuga-fj
      </td>
    </tr>
</table>

<pre>
    We have found that there are cases where phi-phi dependencies are not handled correctly. The following link shows an example.
https://godbolt.org/z/qfsT5WK5a

The following is part of the debug output.

```
SU(1):   %6:gpr32 = PHI %4:gpr32, %bb.0, %7:gpr32, %bb.2
  # preds left       : 0
  # succs left       : 2
 # rdefs left       : 0
  Latency            : 0
  Depth              : 0
  Height             : 4
  Successors:
    SU(10): Data Latency=0 Reg=%6
    SU(2): Ord  Latency=0 Barrier
SU(2):   %7:gpr32 = PHI %3:gpr32, %bb.0, %8:gpr32, %bb.2
  # preds left       : 1
  # succs left       : 2
  # rdefs left       : 0
  Latency            : 0
 Depth              : 0
  Height             : 4
  Predecessors:
 SU(1): Ord  Latency=0 Barrier
  Successors:
    SU(8): Data Latency=0 Reg=%7
    SU(3): Ord  Latency=0 Barrier
```

There is a dependence between `SU(1)` and `SU(2)`, and the distance of it is 1. However, `SwingSchedulerDAG::getDistance` returns 0 because the dependence is not an anti. I think this problem can be resolved by changing the dependence type to an anti in `SwingSchedulerDAG::updatePhiDependencies`.

https://github.com/llvm/llvm-project/blob/c947709df7859bb7285873593adab70349a5ab3e/llvm/lib/CodeGen/MachinePipeliner.cpp#L957-L958

However, I'm not quite sure if there's any intent to append barrier-dependence rather than anti.

Slightly off topic, but I have a feeling that `multipleIterations` has bugs. If I understand it correctly, this function addresses the following case: the instruction defining v2 should be scheduled before the instruction defining v3.

```
         v0 = phi(..., v2) ---+---------+
                               | Data    |
     +-- v1 = phi(..., v0) <---+         | Anti
     | |
Data |   v2 = ...   <--------------------+
     |
     +-> v3 = USE v1
```

If so, I see the following problems.
- The return value of `multipleIterations` should be `S.getSUnit()`, not `P.getSUnit()`.
- The value to be updated is `MaxEarlyStart`, not `MinLateStart`.
    - In https://github.com/llvm/llvm-project/blob/c947709df7859bb7285873593adab70349a5ab3e/llvm/lib/CodeGen/MachinePipeliner.cpp#L2942-L2945.
 - Also, we should use `cycle - 2 * II` instead of `cycle`?
- `multipleIterations` also doesn't handle phi-phi barrier-dependence correctly.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMV0-Tm7gT_TTypQsKCzD44INnHCeuX1K_qXVSOQvUGCUaiUjCE--n32qwx_b82-zmstSUByT161a_1msQ3qudQVyw_Iblq4noQ2vd4rvw_U5EzbdJZeVh8RWhFXuExvZGQmhFgNCiQxAOoRYePTwMz12roq5VILFDI9HUCv2wyNgArTBSo4TaOod10IcYPrcEqrV9UGYHWpnv4Fv74EEYwJ_ivtMYs2TFkmUbQudZumR8zfh6Z2VldYit2zG-_pPx9Y_Gf86__i8X4_Lx9xpeeeiEC2Abih4kVv0ObB-6PsSXVmyWHP-Gx-0Xxssp43OWLgGA8XzG0uWucykHlq7g7sOGBrPTIOO39FxVcXK8LZ5P8RGb4FLoHEoPGpsA40WekssVvq_rZytOGLTASWxeh_goApr6ABfX1fwKu9ACvDr_AdWuDc_ms9P8tq9r9N66gaHjIMCYueSYupUI4hQJS1cJ_IE7lq6GfF6b8KPF_52EK4sb4ZxCd8ELv-SleImX9HVeyn_Dy_SXefl9Yn6XlzuHEp8xc1XQb-f4bWrLv2W2eGKR_pLXJwfw8Sw7pDMszuqCUGF4QDTAZsl5W7MEhJGPY3wcI5LFIF8IUvkgyN42oAKhTmP4YB9wj24ohlmyJc3Y1i3KXqNbLd_T_tPlDsPqaEx-HIbeGQ8JVFiL3uNRWh4DVH7QPmFAmKBi2EBoSeZCS3LkbKXxHmphoEJw6K3eo4TqAHUrzI5U6wleOHQIwZ4AQZk3gu07KQLetWp1ocdsllzJ3RNlVaHtq7i294yvtd6f_kWds9-wDoyvK20rxtf1PCuKZC6bosznVVXwMi-LNJ-nQoqqSNJsLnJRpXiBo8ju1kp8j4bx9SdRt8rgnepQK4MurruO8fTjPC-ij_O8vIzygpwN48X9kNUfvQoIvqfCaMaWxHhB3eMAygQ0YUhVR5uHaiyx6CKZTpANNbQjPZcet5oOlz6AbRoItlM1Oa_6AJuxGwpokALfjR2RzZL7XgfVadwEdCIoayjZ0AoPVb_zMWwa2EBvJDqqIEml99gMCXwoiqY3NdmCkNKhp-YarvoYNVw6RDSqjA-uH9dLbJShBXtOXbTXkorKH6uCHhrr8A2z9K02-Kgw-2SQ165VjJdxHFPgezpjEEUR4zfR6WL85onpyxcrbkcJGe8vbAY02E9fcEhdBVh6O_q5wlqaoC5Bitsz7OCHRoCyRLBxHA-yeRu9cF1v4XlwLH0H-3TA-bJ9B_vpGwK2acDboX7BIz7h9KgE_shANLwZjeICe6H7QalerbAz26QF8Q7D9otRgfHyLH10XtgsuXs-e-VzdBYsgY3yIUnD2Cz5JH6-E04ftkG4cA36SRkS89NMfM5SBBsD_z2F4fOMR_Sbn2KNYKlHeh7wlE-SczZL6kOtESLgwPgSNhvKOB0gFPLIyrCCUpKuT7l8lSuhvQVp0RvGi9NL8eOL8wsidX5dnshFKufpXExwMS2mZZpznmeTdlFOixTrej6b5lU-y5qkTLNqxousEUk9L6cTteAJz5LZNEvKJJtmcT6fTSuZpUXZFGVSFSxL8F4oHVMi6bV6orzvcTHP82k60aJC7YdvBM4NPsAwyTinTwa3GNgjhWNZopUP_owSVNDDx8VTJli-grtWRXcvfS2cvhSUedz8pHd68Y8LaYjTM74e97Ff8L8CAAD__32ywhU">