[AffineToStaticLogic] Support iteratively lowering nested loops.
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 2.2k
- Forks
- 524
- Avg merge
- 3d 2h
- Merged PRs (30d)
- 46
Description
After #2657 we can explore a new way to add support for nested loops. This is different from the idea in #2320, which would solve the nested loop problem within the scheduling analysis, and could be a good intermediate step before enhancing the scheduling analysis. Once the analysis can support nested loops, we could have the pass try the analysis, and fall back to this approach in general.
The idea is to keep the same analysis and transformation steps, which lower one Affine for loop, but apply them iteratively from the innermost loop out. This could be accomplished by updating the existing pass to use a RewritePattern that matches innermost loops, and applying the pattern greedily.
If we do this, innermost loops will be turned into pipelines, and the outer loops would need to know how to schedule pipelines. With the new bound attribute, we have enough information in the IR to compute the latency of PipelineWhileOp and communicate that back to the scheduling analysis.
One thing we need to be careful about is maintaining the sequential execution of inner loops, as mentioned in #2320. When an Affine for loop contains nested pipelines, we will need to special case this pass to generate the induction variable increment in a new, final stage, rather than putting it directly in the first stage.
There are probably some other details to work out, but this could be a relatively non-intrusive change to handle loop nests, including imperfect loop nests.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the existing Affine-to-static pass and its analysis and transformation steps. Trace how an Affine for loop becomes a pipeline, then investigate applying the existing logic iteratively from innermost loops outward with a greedy RewritePattern. Done means nested and imperfect loop nests lower correctly, outer scheduling accounts for PipelineWhileOp latency, and inner-loop execution remains sequential.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100