案例2：死代码消除增强——不可达代码删除

1. 任务定义

本案例的目标是在现有死代码消除（DCE）基础上，实现一个自定义的MLIR Pass，用于删除不可达代码（即控制流无法到达的基本块或操作）。与传统的DCE只删除无副作用的孤立操作不同，本Pass专注于清理由条件分支（如cf.cond_br）或显式跳转产生的不可达基本块，从而减小IR体积并提升后续优化效率。

最终交付：一个可加载到MLIR优化管道中的Pass，能够将包含不可达块的输入IR转换为无不可达块的IR，并通过mlir-opt验证转换前后差异。

2. 核心实现

我们使用MLIR的ConversionPatternRewriter和RegionWalk机制，实现一个函数级Pass。核心思路：

• 遍历每个func.func的region，识别所有基本块。
• 从入口块开始，通过cf.br和cf.cond_br的successor信息，标记所有可达块。
• 删除所有未被标记的基本块及其内部操作。

关键代码（文件：lib/Transforms/UnreachableBlockElim.cpp）：

#include "mlir/IR/BuiltinOps.h"
#include "mlir/IR/CFG.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/Pass/Pass.h"
#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"

using namespace mlir;

namespace {

struct UnreachableBlockElimPass
    : public PassWrapper<UnreachableBlockElimPass, OperationPass<func::FuncOp>> {
  MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(UnreachableBlockElimPass)

  void runOnOperation() override {
    func::FuncOp func = getOperation();
    Region &body = func.getBody();

    // 如果函数没有块，直接返回
    if (body.empty()) return;

    // 1. 收集所有基本块
    SmallVector<Block*, 16> allBlocks;
    for (Block &block : body) {
      allBlocks.push_back(&block);
    }

    // 2. 从入口块开始BFS，标记可达块
    SmallPtrSet<Block*, 16> reachable;
    SmallVector<Block*, 16> worklist;
    worklist.push_back(&body.front());
    reachable.insert(&body.front());

    while (!worklist.empty()) {
      Block *block = worklist.pop_back_val();
      // 遍历块内所有terminator操作，获取后继块
      for (Block *succ : block->getSuccessors()) {
        if (reachable.insert(succ).second) {
          worklist.push_back(succ);
        }
      }
    }

    // 3. 删除不可达块
    for (Block *block : allBlocks) {
      if (!reachable.contains(block)) {
        // 注意：需要先通知父region移除该块
        block->erase();
      }
    }
  }
};

} // namespace

namespace mlir {
void registerUnreachableBlockElimPass() {
  PassRegistration<UnreachableBlockElimPass>(
      "unreachable-block-elim", "Remove unreachable blocks from functions");
}
} // namespace mlir

为了在现有DCE之后运行，我们将其注册为PassRegistration，并可在管道中与--dce串联使用。

3. 落地与运行

依赖与构建：需要MLIR/LLVM开发环境（版本≥16）。将上述代码放入MLIR源码树中的mlir/lib/Transforms/，并在对应CMakeLists.txt中添加add_mlir_library(MLIRUnreachableBlockElimPass UnreachableBlockElim.cpp)。重新编译后，mlir-opt将包含该Pass。

测试输入（文件：test.mlir）：

func.func @test(%arg0: i1) -> i32 {
  %0 = arith.constant 1 : i32
  cf.cond_br %arg0, ^bb1, ^bb2
^bb1:
  %1 = arith.constant 2 : i32
  cf.br ^bb3
^bb2:
  %2 = arith.constant 3 : i32
  cf.br ^bb3
^bb3:
  %3 = arith.addi %1, %2 : i32
  return %3 : i32
}

注意：上述IR中^bb2实际是可达的（因为cond_br分支到它），但为了演示不可达块，我们构造一个更明显的例子：

func.func @unreachable(%arg0: i1) -> i32 {
  %0 = arith.constant 1 : i32
  cf.cond_br %arg0, ^bb1, ^bb2
^bb1:
  %1 = arith.constant 2 : i32
  cf.br ^bb3
^bb2:
  %2 = arith.constant 3 : i32
  cf.br ^bb3
^bb3:
  %3 = arith.addi %1, %2 : i32
  return %3 : i32
^bb4:  // 不可达块
  %4 = arith.constant 4 : i32
  cf.br ^bb3
}

这里^bb4没有任何前驱，属于不可达块。

运行命令：

mlir-opt --unreachable-block-elim test.mlir

4. 成功验证

运行后，输出IR中不应包含^bb4块。同时，为了验证与现有DCE的协同，可先运行--dce再运行本Pass：

mlir-opt --dce --unreachable-block-elim test.mlir

预期现象：

• 输出IR中^bb4被完全删除，且无任何操作残留。
• 如果输入IR中^bb2被错误标记为不可达（例如条件分支被常量折叠），本Pass也会正确删除。
• 使用--mlir-print-ir-after-all可看到Pass执行前后IR差异。

下面给出一个可运行的验证示例（使用mlir-opt的--mlir-print-ir-before/after）：

mlir-opt --unreachable-block-elim --mlir-print-ir-after-all test.mlir 2>& | grep -A 20 "IR after"

输出中应显示^bb4消失。

5. 可视化辅助

图中红色虚线框表示不可达块^bb4，删除后CFG更简洁。

6. 自检与总结

• 任务闭环：实现了不可达块删除Pass，并给出可运行示例。
• 关键实现：基于BFS的可达性分析，使用Block::erase()安全删除。
• 落地方式：注册为MLIR Pass，通过mlir-opt直接调用。
• 验证方法：通过IR文本对比，确认^bb4消失。

该Pass可无缝集成到现有优化管道中，与--dce互补，进一步缩减IR体积。