purescript-native编译器原理(二):MagicDo优化深潜——Effect/Eff/ST单子如何被内联成高效原生C++代码

purescript-native编译器原理(二):MagicDo优化深潜——Effect/Eff/ST单子如何被内联成高效原生C++代码

【免费下载链接】purescript-nativeA native compiler backend for PureScript (via C++ or Golang)项目地址: https://gitcode.com/gh_mirrors/pu/purescript-native

purescript-native 是一个 PureScript 原生编译器后端，能把 PureScript 代码直接编译成 C++（或 Golang）。本文深入讲解它的核心MagicDo 优化——如何把Effect、Eff、ST单子的样板代码内联成高效原生 C++ 代码，把单子bind/return的全部开销在编译期彻底消除。

🧩 为什么单子需要专门的"内联"优化？

在 JavaScript 后端，do块被脱糖成嵌套的>>=调用，多一次调用只是多一层函数帧，JS 引擎尚可优化。但在原生 C++ 后端，这些"间接调用"是真实的函数调用 + 字典查找，开销被放大。

关键的观察是：单子化（monomorphized）之后，Effect/Eff/ST的>>=和return结构完全同构——它们本质上只是"取出前一个动作的值，传给后续代码"。既然结构固定，编译器就可以在编译期把整个单子结构摊平，直接生成直线代码。这就是 MagicDo 的立身之本。

🎯 三个通道：magicDoEffect、magicDoEff、magicDoST

核心实现位于src/CodeGen/IL/Optimizer/MagicDo.hs。同一个magicDo核心函数，分别针对三个单子实例化：

值得强调的是：优化识别的不是字面函数名，而是单子化后的类型类字典参数。例如判断一次>>=调用是否属于Effect单子，靠的是检查其字典参数是否为Effect.bindDict、函数本体是否为多态的Control.Bind.bind（见src/CodeGen/IL/Optimizer/Common.hs中的isDict辅助函数）。这保证了只对"真正的单子绑定"动手，绝不误伤普通函数调用。

🔨 四条核心变换规则

1.pure/return→ 直接取值

return x不再构造任何单子包装，直接变成值x本身。

2.bind→ 局部变量 + 顺序语句（核心规则）

m >>= \x -> body被改写为"声明局部变量x = m()，然后顺序执行 body"。源码注释中的示例最直观：

优化前（单子调用形态）：

Prelude">>="(m1)(function(x) { return ...; })

优化后（直线语句形态）：

function __do { var x = m1(); ... }

嵌套的单子调用链被彻底展平为顺序语句，函数调用帧、字典参数全部消失。

3.discard→ 丢弃绑定的结果

let _ = m这类"执行但丢弃结果"的写法会被识别为discard，直接替换成"执行 m、忽略返回值"的语句块。

4.untilE/whileE→ 原生 while 循环

Effect 库的untilE与whileE组合子被直接脱糖为原生While循环 IL，完全绕开函数调用，循环判断与循环体由 C++ 编译器直接处理。

还有一个不起眼的配角applyReturns：内联过程中，do块内部的每一个return e都会被替换为调用 e()。因为被内联进来的单子动作从"被引用的值"变成了"必须被执行的调用"——这一步保证了副作用顺序与原始语义严格一致。

🚀 ST 单子的专属深潜：引用变成局部变量

除通用通道外，ST单子还有一个专属的inlineST通道，思路更激进：

1. 定位runST块，作为分析的边界；
2. 清点资源：枚举该块内所有由newSTRef创建的引用，以及所有readSTRef/writeSTRef/modifySTRef的使用点；
3. 安全性判断：只有当每个引用都只在本runST作用域内使用、且没有任何引用"逃逸"到外部（比如作为函数参数传走或作为结果返回）时，才进入激进模式；
4. 激进内联：{ value: v }对象包装被完全拆掉，STRef退化为普通局部变量——
   • newSTRef v→ 声明局部变量并初始化
   • readSTRef r→ 直接读取变量
   • writeSTRef r v→ 直接赋值

若任一检查不通过，则保守地保留对象包装形式，仅做安全的等价替换。这意味着：一段"纯就地更新"的ST代码，最终编译产物里没有堆分配、没有引用计数，就是最朴素的局部变量读写。

📐 管线全景：MagicDo 在哪个环节工作？

src/CodeGen/IL/Optimizer.hs中的optimize函数定义了完整的优化管线，MagicDo 的位置很讲究：

1. 内联阶段：函数组合内联、unsafeCoerce/unsafePartial内联，untilFixedPoint循环至不动点；
2. MagicDo 阶段：按magicDoEffect→magicDoEff→magicDoST的顺序，每个通道都跑untilFixedPoint——因为剥开一层绑定后，往往会暴露出下一层可继续内联的绑定；
3. 收尾阶段：tco尾调用优化、inlineST引用内联、删除无用结果、公共子表达式内联，再次不动点迭代；
4. 最终整理：合并相邻的变量声明。

顺序即语义：MagicDo 必须先行。只有单子结构先被摊平成直线语句，后续的尾调用优化才能认出循环结构，C++ 端才能真正受益。

💡 对开发者的实际意义

• 放心写do记法：Effect/Eff/ST的单子风格写得越多，收益越大——内联后的 C++ 代码与手写直代码几乎无差别；
• ST 是零成本抽象：只要STRef不逃出runST作用域，它就只是局部变量，连shared_ptr都省了；
• 完全透明：这些优化在pscpp编译流程中自动执行（入口见app/Main.hs的transpile函数，逐模块输出.h/.cpp），开发者零感知、零配置。

📚 关键源码速查

• MagicDo 优化实现（含三个通道与inlineST）：src/CodeGen/IL/Optimizer/MagicDo.hs
• 完整优化管线与不动点循环：src/CodeGen/IL/Optimizer.hs
• 字典识别工具（isDict）：src/CodeGen/IL/Optimizer/Common.hs
• 编译器入口与输出：app/Main.hs
• C++ 运行时支撑文件：runtime/purescript.cpp、runtime/dictionary.h

至此，Effect/Eff/ST 的单子"语法糖"已在编译期化为乌有，剩下的就是直线、无分配的原生代码。下一篇我们继续拆解 TCO 尾调用优化与 Inliner 内联通道，看它们如何与 MagicDo 接力，共同榨干每一个 CPU 周期。

【免费下载链接】purescript-nativeA native compiler backend for PureScript (via C++ or Golang)项目地址: https://gitcode.com/gh_mirrors/pu/purescript-native