[Analysis] Generalize dependence analysis to multi-block regions
- 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