[LoopFusion] Simplifying the legality checks

[1997alireza]

The current loop-fusion pass contains redundant and unnecessary checks that are causing multiple issues and crashes (e.g., #166560, #166535, #165031, #80301). In addition, a required domination check is missing (#168263). Considering that the current loop fusion only supports adjacent loops, we are able to simplify the checks in this pass. Following plans outline how these loop fusion checks should be restructured. There are two approaches we have considered and tested:

Approach 1: Simplify isControlFlowEquivalent

This function is currently unreliable and unnecessary. Its existing uses can be replaced or eliminated:

1. During candidate collection (collectFusionCandidates): A simplified version of isControlFlowEquivalent that only verifies if first loop dominates the second and the second post-dominates the first would be sufficient here.
2. During fusion (fuseCandidates) in isSafeToMoveBefore: At this stage, loop legality has already been verified the control-flow of the loops, and re-checking control-flow equivalence is redundant.¹

Approach 2: Remove isControlFlowEquivalent

In this approach, we check the adjacency of the loops during collection rather than fusion:

1. During candidate collection (collectFusionCandidates): isControlFlowEquivalent is replaced with isAdjacent.
2. During fusion (fuseCandidates): Condition isAdjacent is removed. isControlFlowEquivalent is also removed from isSafeToMoveBefore because of the same reason as in the first approach.

• In this approach, dominancy and post-dominancy of the loops are not explicitly checked anymore. No need to check whether PDT->dominates(FC1, FC0), as this condition is already verified implicitly in isAdjacent. But for the guarded loops, isAdjacent is not a sufficient check to make sure that DT->dominates(FC0, FC1). So one additional change that comes with this approach is to check this dominancy along with isAdjacent.

Additional Effects

• Simplify FusionCandidateCompare
  In either approaches, ordering can be determined only by checking which loop dominates the other, reducing the number of required checks here.

Comparing the computational complexity²

• Original loop fusion

  • During collection (collectFusionCandidates), it checks each new candidate with the beginning of each candidate set, O(n.k).
  • During fusion (fuseCandidates), it checks each loop with all others in the set, O(n^2/k).

• Approach 1

  • During collection (collectFusionCandidates), it checks each new candidate with the beginning of each candidate set, O(n.k).
  • During fusion (fuseCandidates), it checks each loop only with its following loop in the set, since it is the only possible adjacent loop, O(n).

• Approach 2

  • During collection (collectFusionCandidates), since the condition to keep in the same set is adjacency, each new candidates need to be checked with all members of all sets, O(n^2).
  • During fusion (fuseCandidates), it checks each loop only with its following loop in the set, since it is the only adjacent loop, O(n).

Footnotes

1. Before reaching the check isSafeToMoveBefore, the control-flow of the loops, and the equivalency of the guard conditions are already checked. ↩

2. n is the number of loops, k is the number of candidate sets. ↩

[Meinersbur]

Generally, the number of fuse candidates is low, so I would not be too worried about big O-complexity.

Following the mental model of
#166560 (comment)
I think the only candidate pool that is need is a list of sequential/adjacent loops (or its loop guards). One can iterate over the list and greedily merge neighbors, only one iteration is necessary. I think this corresponds to approach 1.

If I understand approach 2 correctly, isAdjacent is currently already enforced adjacency of the loops (respectively its loop guards) in fuseCandidates(), but which is only after the candidate list has already been created. So approach 2 adds a isAdjacent to the candidate selection. If the loops are adjacent, they can be sequentually ordered, and an all-to-all comparison becomes unnecessary.

So I don't think the two approaches are that different: approach 1 effectively has to check adjacency just as approach 2 does. But I think the FusionCandidates should be collected in a list according to its sequential execution order in the first place; it should not be necessary to sort them according to a heuristic.

[1997alireza]

Generally, the number of fuse candidates is low, so I would not be too worried about big O-complexity.

Following the mental model of #166560 (comment) I think the only candidate pool that is need is a list of sequential/adjacent loops (or its loop guards). One can iterate over the list and greedily merge neighbors, only one iteration is necessary. I think this corresponds to approach 1.

If I understand approach 2 correctly, isAdjacent is currently already enforced adjacency of the loops (respectively its loop guards) in fuseCandidates(), but which is only after the candidate list has already been created. So approach 2 adds a isAdjacent to the candidate selection. If the loops are adjacent, they can be sequentually ordered, and an all-to-all comparison becomes unnecessary.

So I don't think the two approaches are that different: approach 1 effectively has to check adjacency just as approach 2 does. But I think the FusionCandidates should be collected in a list according to its sequential execution order in the first place; it should not be necessary to sort them according to a heuristic.

Thanks Michael. I posted the implementation in PR #171889. As you suggested, now each candidate list contains sequential loops, so no sorting and no isAdjacent check are needed anymore after the candidate collection step.

[Meinersbur]

Thanks for the fix. Have you checked what is going with the still open issues #s (e.g. #166356, #165087, #115279)?

[1997alireza]

Thanks for the fix. Have you checked what is going with the still open issues #s (e.g. #165087, #165087, #115279)?

Yes we are working on the other loop fusion issue as well. Will try to post PRs soon to fix them.