Leveraging SIV in the DA Pass to Detect Loop Carried Dependencies

IR & Optimizations Loop Optimizations
1

Dear LLVM Community,

I’m working on improving the Dependency Analysis (DA) pass in LLVM to better detect “Loop Carried Dependencies” in loop fusion. The current DA tests (SIV, MIV, RDIV) lack sufficient detail for this task, and I’d like to discuss extending the pass to address this.

Problem Context

The issue arises when fusing two exact similar loops and detecting the dependency between them along with its direction and distance. For example:

for (int i = 0; i < 10; i++)
  A[i+1] = ...;

for (int j = 0; j < 10; j++)
  ... = A[j];

Here, there’s a backward loop-carried. The DA pass should ideally provide the dependency’s direction (<) and distance (-1), which is essential for detecting loop carried dependencies in loop fusion. Currently, loop fusion attempts to gather the required information using SCEV, but in some cases, the SCEV is too complicated to handle, while DA could have been able to manage them.

Current DA Pass Behavior

Currently, the DA pass classifies this as RDIV, which identifies a dependency by detecting an intersection between the expressions but does not specify the direction or distance. This is because direction and distance do not make sense when we have different loops, but in our case, the loops are structurally the same, so we could leverage additional information to identify the dependency’s direction and distance.

SIV’s Potential for Our Use Case

SIV (Single Index Variable) works well for dependencies within the same loop, providing both direction and distance. However, it’s currently restricted to dependencies within the same loop. Given that the loops in our case are structurally similar, I propose relaxing the condition for SIV to allow it to work specifically for the following cases:

for (int i = 0; i < 10; i++)
  A[i] = ...;

for (int j = 0; j < 10; j++)
  ... = A[j];

for (int i = 0; i < 10; i++)
  A[i+1] = ...;

for (int j = 0; j < 10; j++)
  ... = A[j];

This would help the DA pass to provide direction and distance across different but similar loops.

Request for Feedback

We would like to post this extension to the opensource LLVM. I’d appreciate feedback on this proposal, especially regarding:

  1. Whether relaxing the SIV conditions is a reasonable approach for handling loop carried dependencies.
  2. Any potential implications this might have on the performance or correctness of the DA pass.

Thank you for your time. I look forward to your thoughts

2

CC @sebpop

I have spent some time on the DA pass, specifically as our team is looking at enabling the LoopInterchange pass. Enabling loop-interchange

This would help the DA pass to provide direction and distance across different but similar loops.

Some questions:

  1. Have you considered what it means to be “similar loops”? I think one needs to have a concrete definition for this.
  2. When it comes to analysis, are you thinking of limiting the number of Src and Dst pairs you want to analyze at some point?
3

Thanks a lot for your response and the helpful questions!

  1. Regarding the definition of “similar loops”: We are limiting our consideration to single-level loops with a single induction variable. By “similar,” I mean loops that have induction variables with the same starting point, trip count, and endpoint.
  2. About limiting the number of source and destination pairs: That’s a great point, and I think it’s something we can do if the community agrees. It could definitely help manage performance.

I’d love to hear your thoughts on this!

4

We should try to keep the DA pass as short and simple as possible.
We should not modify the SIV test in DA: the legality for loop fusion should be developed in the loop fusion pass.

for (int i = 0; i < 10; i++)
  A[i] = ...;
 for (int j = 0; j < 10; j++)
  ... = A[j];
  1. Whether relaxing the SIV conditions is a reasonable approach for handling loop carried dependencies.

No, the dependence is not carried by any loop in the examples you provided.
Your intention is to analyze the dependences in the transformed loop:

for (int i = 0; i < 10; i++)
   A[i] = ...;
   ... = A[i];

and in this case DA’s SIV test will work fine.

5

Thank you for your thoughtful feedback, Sebastian.

I understand the importance of keeping the DA pass concise and focused. However, it would be beneficial if DA could provide additional information relevant to loop fusion without requiring the fusion to be performed ahead of time. With that in mind, I have made modifications to the DA pass to offer this capability.

The changes I’ve implemented do not interfere with the current functionality of DA; rather, they enhance the analysis by providing additional information, such as direction and distance, for cases where dependent instructions span across loops with the same trip count and depth. This allows for a more detailed evaluation of loop-carried dependencies before proceeding with fusion.

You can review the patch in this commit. The aim of these modifications is to extend the range of cases considered in the SIV test, with the added benefit of providing direction and distance information where applicable.

Thank you again for your insights.

6

You can review the patch in this commit

I read through the changes.
I believe the change is minimal and it improves DA for loop fusion.

Do you have a PR together with the changes to the loop-fusion pass?

7

No change is required in the transformation passes to use this additional information. Now the DA provides the separate but “similar” levels as dependent and provides direction and distance. Before they were only considered as dependent without any additional information. I have posted a patch [link] with test-cases to review. Please take a look and let me know if you had any questions.

8

Before adding new functionality to LoopFuse, I think it would be good to fix the existing issues.

1 Like