llvm / llvm/circt

[Analysis] Generalize dependence analysis to multi-block regions

Open
#1,945 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.2k
Forks
524
Avg merge
3d 2h
Merged PRs (30d)
46

Description

After https://github.com/llvm/circt/commit/71aa4a48067994c9cf3082bb14fc5f7ab4116caf, dependences within a loop iteration are considered. However, the analysis only supports `affine.for` and `affine.if` ops with single-block regions. This could be generalized to support multiple blocks, like `scf.execute_region` ops:

```mlir
func @test(%arg0: memref) {
affine.for %arg1 = 0 to 10 {
%0 = scf.execute_region -> i32 {
^bb0:
%1 = affine.load %arg0[%arg1] : memref
br ^bb1

^bb1:
affine.store %1, %arg0[%arg1] : memref
scf.yield %1 : i32
}
}
return
}
```

We should be able to use MLIR's [Dominance](https://github.com/llvm/llvm-project/blob/3fe7fe44249b0c640031a09800f3485a06a61d2d/mlir/include/mlir/IR/Dominance.h#L127) checks here. That could probably simplify the implementation for the currently supported cases, and support multiple blocks like above.

We'd also need to generalize the method to look up potential parents, which currently defers to [getEnclosingAffineForAndIfOps](https://github.com/llvm/llvm-project/blob/3fe7fe44249b0c640031a09800f3485a06a61d2d/mlir/include/mlir/Analysis/Utils.h#L44).

Contributor guide

No contributing guide indexed for this repository

Research direction

Start by tracing the dependence analysis logic for affine.for and affine.if regions, then review MLIR's Dominance checks in Dominance.h and the current getEnclosingAffineForAndIfOps helper in Utils.h. Generalize the parent lookup and region handling to support multi-block regions such as scf.execute_region while preserving the currently supported single-block cases.

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.