[MachinePipeliner] Pipeliner Doesn't Consider Phis in computeStart

[mmarjieh]

When trying to schedule an instruction X and it has an input from instruction Y two iterations ago (fed by two phis), the pipeliner doesn't consider Y when calculating the EarlyStart and LateStart parameters.

For example:

%phi1 = phi ..., %y
%phi2 = phi ..., %1

%x = instruction_x(%phi2)
%y = instruction_y

When scheduling we have two cases:

1. instruction_x is scheduled before instruction_y, say at cycle x.
   Then the calculation should be as follows:
   LateStart= min(LateStart, x + NumPhis * II - Latency_Of_x)

2. instruction_y is scheduled before instruction_x, say at cycle y.
   Then the calculation should be as follows:
   EarlyStart= max(EarlyStart, y - NumPhis * II + Latency_Of_x)

Reproducer:
https://godbolt.org/z/r1c6bTd6v

II=7
Inst (16) %11:gprc = ADDI %30:gprc_and_gprc_nor0, 4
is scheduled at cycle 10.
Whereas,
Inst (8) %25:gprc = ADD4 %4:gprc, %23:gprc
is scheduled at cycle 4.
which is an invalid schedule.

Explanation:
Inst (8) needs the output of Inst(16) from 1 iteration ago.
This means that at cycle 4 + II = 11, Inst(16)'s output should be ready to use by the next ADD4.
Inst (16) only started at cycle 10 and has a latency of 2, this means that its output won't be ready at cycle 11.

[kasuga-fj]

Hi. Let me clarify your situation.

For example:

%phi1 = phi ..., %y
%phi2 = phi ..., %1

%x = instruction_x(%phi2)
%y = instruction_y

%1 is unclear in your example. I guess you'd like to say something like below, right?

%phi1 = phi ..., %y
%phi2 = phi ..., %phi1

%x = use %phi2
%y = ...

Also, the example in your godbolt link does not seem to show your problem. It is possible that the input IR for pipeliner has changed due to other passes. Using the IR generated with -stop-before=pipeliner may be better.

Regarding the problem you seem to have, I think I might have seen something similar. IIRC, the cause was that a barrier-dependence is added in such a case ¹, but mulitpleIterations only handles data-dependencies between Phis ². Also, as you said, the cycle calculation in computeStart seems to be incorrect to me.

So, I believe that addressing the following two issues would solve your problem.

• Handle barrier-dependencies multipleIterations.
• Fix the cycle calculation related to multipleIterations ³.

However, I don't fully understand what multipleIterations actually do, nor do I know if such a fix is ideal. For example, what will happen in the following cases?

• The order of %phi1 and %phi2 are swapped in the input IR.
• There exists an instruction like %phi3 = phi ..., %phi2.
  • Is it sufficient to follow only two Phis in multipleIterations?

gentle ping to @bcahoon if you have some opinion. Thanks.

Footnotes

1. https://github.com/llvm/llvm-project/blob/de34213a67c23e090095526a2a79797a617a3f39/llvm/lib/CodeGen/MachinePipeliner.cpp#L961-L967 ↩

2. https://github.com/llvm/llvm-project/blob/de34213a67c23e090095526a2a79797a617a3f39/llvm/lib/CodeGen/MachinePipeliner.cpp#L2983-L2990) ↩

3. https://github.com/llvm/llvm-project/blob/de34213a67c23e090095526a2a79797a617a3f39/llvm/lib/CodeGen/MachinePipeliner.cpp#L3029-L3036 ↩

[bcahoon]

I think the bug in the reproducer is because the latency of the instruction is 2, but the latency of the anti dependence edge to SU(1) is 1. If the latency on the edge is 2, then the schedule for II=7 should fail because es=4 and ls=3 for Inst (1).

SU(16): %11:gprc = ADDI %30:gprc_and_gprc_nor0, 4
# preds left : 2
# succs left : 1
# rdefs left : 0
Latency : 2
Depth : 10
Height : 2
Predecessors:
SU(15): Data Latency=2 Reg=%30
SU(1): Anti Latency=1
Successors:
SU(17): Data Latency=2 Reg=%11
SU(17): STWX %11:gprc, %16:g8rc_and_g8rc_nox0, %3:g8rc_and_g8rc_nox0 :: (store (s32) into %ir.scevgep)

[bcahoon]

It's been a long time so I may not remember correctly, but I believe multipleIterations was added to improve the pipeliner results for very specific cases rather than added for correctness. In the case I'm thinking of, if the instructions are ordered correctly one less value needs to be saved across iterations.

[kasuga-fj]

I believe multipleIterations was added to improve the pipeliner results for very specific cases rather than added for correctness.

Oh, I've been thinking that this is necessary for correctness... I was confused about the comment // For instruction that requires multiple iterations, make sure that .... Thank you for the information!

But I'm still not sure what the case multipleIterations addresses. Maybe the return value of multipleIteration should be S.getSUnit(), not P.getSUnit()?

[kasuga-fj]

Right now, I think this issue describes two different problems:

1. The cases where there is a phi referred by another phi, which is stated in the first half of the issue description.
2. The problem triggered by the reproducer.

For the first one, I think NumPhis in the description corresponds to the distance of the dependency. Overestimating the distance (using a smaller value than the actual one) may lose some scheduling opportunities, but doesn't affect correctness.

For the second one, I agree with @bcahoon. We should use instruction latency for anti dependence latency.

[bcahoon]

But I'm still not sure what the case multipleIterations addresses. Maybe the return value of multipleIteration should be S.getSUnit(), not P.getSUnit()?

Here's an example:

 x = phi(-, y)
 z = phi(-, x)
   = inst1 z
 y = inst2

if y = inst2 is inserted before = inst1 z, then the generated pipline may be better if = inst1 z appears at an earlier cycle than y = inst2. That is, if y = inst2 is inserted at cycle N, then multipleIterations causes = inst1 z to be added before N. Without that function, it may be added at cycle N+1, for example. There are no dependences between those instructions otherwise. The problem with adding it after, at cycle N+1, is that an extra register copy is needed to save the value of y for another iteration due to the overlap.

[kasuga-fj]

Thanks. Your example makes sense to me. However, I think the current implementation doesn't process it correctly. In this case, multipleIterations ensures that = inst3 x is scheduled before N (BE, I and SU are variable names in computeStart).

 x = phi(-, y)  // BE
 z = phi(-, x)
   = inst1 z
 y = inst2      // I
   = inst3 x    // SU

I think multipleIterations should return S.getSUnit().

[bcahoon]

I think multipleIterations should return S.getSUnit().

I believe the case with = inst3 x is disallowed by the check after the call to multipleIterations with the following

llvm-project/llvm/lib/CodeGen/MachinePipeliner.cpp

Line 3033 in 5475834

if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&

I did try to remove multipleIterations. None of the lit tests fail. But, in the debug output, some of the test change due to differences in the values returned by computeStart.

Changing multipleIterations to return S.getUnit() also does not change any tests. But, it did change the MinLateStart for exactly the case you mention, = inst3 x in the test swp-kernel-phi1.ll

[kasuga-fj]

I believe the case with = inst3 x is disallowed by the check after the call to multipleIterations with the following

I think this is not a problem. What we actually interested in is y = inst2, not = inst3 x, right? I guess what we really want to achieve is the following. = inst3 x should not be inherently relevant.

 x = phi(-, y)
 z = phi(-, x)  // BE
   = inst1 z    // SU
 y = inst2      // I
   = inst3 x    // Unrelated instruction 

I did try to remove multipleIterations. None of the lit tests fail. But, in the debug output, some of the test change due to differences in the values returned by computeStart.

Changing multipleIterations to return S.getUnit() also does not change any tests. But, it did change the MinLateStart for exactly the case you mention, = inst3 x in the test swp-kernel-phi1.ll

Thanks for the try. IMHO, I think multipleIterations should be removed if there are no huge performance impact. I don't have strong opinion in terms of performance, but I think it's not good to leave a process that is not sure what it is doing.

[bcahoon]

I think this is not a problem. What we actually interested in is y = inst2, not = inst3 x, right? I guess what we really want to achieve is the following. = inst3 x should not be inherently relevant.

Yes.

Thanks for the try. IMHO, I think multipleIterations should be removed if there are no huge performance impact. I don't have strong opinion in terms of performance, but I think it's not good to leave a process that is not sure what it is doing.

I'm not against removing multipleIterations, but it will have a performance impact. I agree that it doesn't really fit there. There is probably a better way to add this functionality though. Maybe a DAG mutation?

[kasuga-fj]

I'm not against removing multipleIterations, but it will have a performance impact. I agree that it doesn't really fit there. There is probably a better way to add this functionality though. Maybe a DAG mutation?

Creating a new DAG mutation looks good to me! However, I am a little concerned that it would not change the existing behavior. That is, adding new edges may change some schedule result. As far as my quick check, artificial dependencies seem to be ignored correctly in each process (e.g., findingCircuits), so I believe nothing strange should happen.