[MachinePipeliner] Phi-Phi dependencies are handled incorrectly

[kasuga-fj]

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 |   I:  v2 = ...   <--------------------+
     |
     +-> SU: 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.

[kasuga-fj]

@bcahoon Could you please check? (Sorry for the many mentions)

[kasuga-fj]

Sorry, I misunderstood something of Phi scheduling. I believe the following fixes will resolve this issue..

• In multipleIterations, also consider order-dependencies (barrier-dependencies) between phis
• Return S.getSUnit() instead of P.getSUnit() in multipleIterations
• Update MaxEarlyStart instead of MinLateStart after calling multipleIterations