# Affine: Loop Parallel

affine dialectの`AffineParallelize` passについてのメモ。

## AffineParallelize

1. AffineForOpに対してwalk
2. ターゲットとなるloopがParallelize可能かチェック(`isLoopParallel`)
- option: `parallel-reductions` をtrueにすると、reduction loopに対してParallelize可能かもチェックする
3. 2をパスしたloopに対して、Parallel化を適用

void AffineParallelize::runOnOperation() {
  func::FuncOp f = getOperation();

  // The walker proceeds in pre-order to process the outer loops first
  // and control the number of outer parallel loops.
  std::vector<ParallelizationCandidate> parallelizableLoops;
  f.walk<WalkOrder::PreOrder>([&](AffineForOp loop) {
    SmallVector<LoopReduction> reductions;
    if (isLoopParallel(loop, parallelReductions ? &reductions : nullptr))
      parallelizableLoops.emplace_back(loop, std::move(reductions));
  });

  for (const ParallelizationCandidate &candidate : parallelizableLoops) {
    unsigned numParentParallelOps = 0;
    AffineForOp loop = candidate.loop;
    for (Operation *op = loop->getParentOp();
         op != nullptr && !op->hasTrait<OpTrait::AffineScope>();
         op = op->getParentOp()) {
      if (isa<AffineParallelOp>(op))
        ++numParentParallelOps;
    }

    if (numParentParallelOps < maxNested) {
      if (failed(affineParallelize(loop, candidate.reductions))) {
        LLVM_DEBUG(llvm::dbgs() << "[" DEBUG_TYPE "] failed to parallelize\n"
                                << loop);
      }
    } else {
      LLVM_DEBUG(llvm::dbgs() << "[" DEBUG_TYPE "] too many nested loops\n"
                              << loop);
    }
  }
}

## Parallelizableのチェック
ループのParalleize可能かのチェック（isLoopParallel）を実施。

- `Dialect/Affine/Analysis/AffineAnalysis.cpp`

### isLoopParallel
1. loop-carriedなSSA依存がある場合かつ、`ParallelReductions` が指定されない場合はNG
1. `ParallelReductions`のチェック
- option: `parallel-reductions` がTrueの場合
3. [Memory dependencesのチェック](#Check-Memory-dependences)

### Check: ParallelReductions
TBD

### Check: Memory dependences
- [ mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp#L598](https://github.com/llvm/llvm-project/blob/main/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp#L598)

DependenceResult mlir::affine::checkMemrefAccessDependence(
    const MemRefAccess &srcAccess,
    const MemRefAccess &dstAccess,
    unsigned loopDepth,
    FlatAffineValueConstraints *dependenceConstraints,
    SmallVector<DependenceComponent, 2> *dependenceComponents,
    bool allowRAR) {..}

2つのメモリアクセス srcAccess と dstAccess の間に依存関係が存在するかどうかを調べる。依存関係がある場合、その方向や性質を調べるための情報を提供される。

1. srcAccess と dstAccess のメモリ参照が同じかどうかを確認する。異なる場合は NoDependence を返す。
- これは異なるメモリをアクセスしている場合には依存関係がないとみなす。
1. allowRAR（Read-After-Read）フラグが無効で、srcAccessとdstAccessのそれぞれがAffineWriteOpInterfaceを満たさない場合は、NoDependence を返す。
- これは、読み込みアクセスでは依存関係を確立できないということを指す。
1. srcAccess と dstAccess のOperationが同じAffineScope内に存在し、共通のAffineScope内でブロックを共有していることを確認する。
1. srcAccess と dstAccess のアクセス関係を取得し、アクセス関係のMergeと逆行列を計算して依存関係を解析する。
- これにより、srcAccessとdstAccess のそれぞれのIteration Domainが同じメモリ場所にアクセスするかどうかが評価される。
1. Iteration Domain制約を追加して、srcAccess が dstAccess よりも先にアクセスされるように制約を設定する。
- これにより、依存関係が確立される方向が制御される。
1. Solution spaceが空であれば、依存関係は存在しないとみなし、NoDependence を返す。
1. 依存関係の方向ベクトルを計算し、依存関係の成分情報が提供されている場合に返す。

この関数の目的は、与えられた2つのメモリアクセス間に依存関係が存在するかどうかを検出し、存在する場合にその性質や方向を調べることである。これにより、プログラムの最適化や並列化の可能性を評価するための情報が提供される。

::: warning
TODO: Commentに記載されているExampleの例がピンとこなかったので、改めて読みたい..
- [mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp#L538](https://github.com/llvm/llvm-project/blob/main/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp#L538)
:::

## Parallel化の適応
TBD