编译原理（二）, MLIR（二）, StableHLO
2024-07-16编译原理
SSA
SSA：static single assignment form
// Non SSA form
a = 1;
a = 2;
b = a + 1;
// SSA form
a1 = 1;
a2 = 2;
b1 = a2 + 1;
SSA只要求每个变量的赋值程序点只能有一个，这个程序点可以出现在循环内部（这意味着执行过程中这个程序点会被多次执行）。
Phi function：
if (cond) {
x = 1;
} else {
x = 2;
}
y = x;
这个转成SSA是：
if (cond) {
x1 = 1;
} else {
x2 = 2;
}
y = x?;
最后一行x的下标是由条件决定是x1，还是x2。为了解决这种无法确定下标的情况，我们引入了Phi function：
if (cond) {
x1 = 1;
} else {
x2 = 2;
}
y = phi(x1, x2);
所以一个分支语句实际上包含了3个block，除了明处的then和else之外，还有Phi function所在的merge block。
PPCG
Polyhedral Parallel Code Generation
代码：
https://github.com/Meinersbur/ppcg
PLUTO
An automatic parallelizer and locality optimizer for affine loop nests
官网：
http://pluto-compiler.sourceforge.net/
参考：
https://www.zhihu.com/question/329294933
如何评价PLUTO编译器？
MPS
MPS是jetbrains推出的用于构建DSL的工具。
官网：
https://www.jetbrains.com/mps/
ANTLR
ANTLR—Another Tool for Language Recognition，其前身是PCCTS，它为包括Java，C++，C#,python在内的语言提供了一个通过语法描述来自动构造自定义语言的识别器（recognizer），编译器（parser）和解释器（translator）的框架。
官网：
http://www.antlr.org/
参考：
http://yuzhouwan.com/posts/55501/
Antlr
https://www.ibm.com/developerworks/cn/java/j-lo-antlr/index.html
使用Antlr开发领域语言
参考
x86一开始并没有使用太多的通用寄存器，原因之一（注意，只是之一）是当时的编译器无力进行寄存器分配，让编译器自动决定程序中众多变量，哪些应该装入寄存器，哪些应该换出，哪些变量应该映射到同一个寄存器上，并不是一件易事，JVM采用堆栈结构的原因之一，就是不信任编译器的寄存器分配能力，转而使用堆栈结构，躲开寄存器分配的难题。
到80年代早期，IBM的G. J. Chaitin公开了他们的图染色寄存器分配算法之后，编译器的分配能力获得长足进步，形成了现在这样的编译器主导的寄存器分配格局。
堆栈传递参数，会导致大量内存操作，造成性能损失。
https://www.zhihu.com/question/24551779
为什么ARM和MIPS那么多寄存器，x86那么少？
stdcall每次调用节省3字节，函数体本身只会存在于一处，而函数调用会存在很多处，所以总的来说生成的二进制产物体积会减小很多。缺点是不支持可变参数函数。
C/C++默认使用cdecl。早期的X86 CPU并没有RET指令，也就没有stdcall。
类似的还有regcall、regparm、fastcall、sseregparm。
这些call的优化点都是：参数尽可能通过寄存器传递，减少堆栈操作，堆栈仅用于实在放不下的参数。
sseregparm甚至把算盘打到了SSE寄存器上。
https://www.zhihu.com/question/662928381
为什么win32 API要采用stdcall？
https://mp.weixin.qq.com/s/MqfteZBSWbnBpHbFYw8Eqw
如何编写一个简单的Python编译器
https://zhuanlan.zhihu.com/p/28637279
使用LLVM+PLY实现一个C语言子集的玩具编译器
https://mp.weixin.qq.com/s/7wmBsJgPnOtPXcYaoQd1qA
基于LLVM的源码级依赖分析方案的设计与实现
https://mp.weixin.qq.com/s/vOJPxzH_1SUyXzNeE85zHQ
编译器入门：没有siri的那些年，我们如何实现人机对话？
https://mp.weixin.qq.com/s/4FJzxPyCmakjIU-9xlQmJQ
阁下可知文言编程之精妙？CMU本科生开源文言文编程语言，数天2K星
https://mp.weixin.qq.com/s/7PH8o1tbjLsM4-nOnjbwLw
Java即时编译器原理解析及实践
https://mp.weixin.qq.com/s/s2W_VVlS-UC8PaaVYJlNgw
浅谈编译过程
https://mp.weixin.qq.com/s/j8_8QwFnyOr66m9aekor1g
用JS解释JS！详解AST及其应用
https://zhuanlan.zhihu.com/p/471250907
从零开始，写个编译器！
https://www.zhihu.com/question/34619258
现代c++编译器对临时对象做了怎样的优化？
https://zhuanlan.zhihu.com/p/474324656
我对深度学习编译器和框架的认识
https://sunfishcode.github.io/blog/2018/10/22/Canonicalization.html
Canonicalization
MLIR
./mlir-opt --pass-pipeline="builtin.module(func.func(tosa-to-linalg-named, tosa-to-linalg, tosa-to-arith{include-apply-rescale=1}, tosa-to-tensor),one-shot-bufferize,...)" a.mlir -o b.mlir
mlir-opt是一个命令行工具，用于组建Pass pipeline，将一个mlir文件变成另一个mlir文件。
TPP (Tensor Processing Primitives)
《Tensor Processing Primitives: A Programming Abstraction for Efficiency and Portability in Deep Learning & HPC Workloads》
TCP (Tensor Compute Primitives)
https://discourse.llvm.org/t/rfc-tile-dialect-and-or-dialect-reshuffle/71252
Tile Dialect and-or Dialect Reshuffle
模式匹配：
Pattern Descriptor Language
https://mlir.llvm.org/docs/PDLL/
在PDL之前，还有一个Tablegen DRR：
https://mlir.llvm.org/docs/DeclarativeRewrites/
Table-driven Declarative Rewrite Rule
./mlir-pdll -x=mlir rewrite.pdll
参考：
https://mp.weixin.qq.com/s/fal6vz9gaZMbR41QMGE3AQ
MLIR发布：全新的中介码与编译器框架
https://zhuanlan.zhihu.com/p/361448250
MLIR Toy Tutorials
https://zhuanlan.zhihu.com/p/141256429
MLIR文章视频汇总
https://zhuanlan.zhihu.com/p/379063169
MLIR: 编译器基础架构重定义
https://zhuanlan.zhihu.com/p/508345356
AI编译器的概览、挑战和实践
https://blog.csdn.net/just_sort/article/details/123624966
基于MLIR的矩阵乘法高性能GPU代码生成：一些早期结果
https://zhuanlan.zhihu.com/p/442140282
MLIR: A Brief Survey
https://zhuanlan.zhihu.com/p/545672504
MLIR原理与应用技术杂谈
https://zhuanlan.zhihu.com/p/513872467
面向ASIC设备的编译器框架：TVM or MLIR？
https://www.zhihu.com/question/442964082
如何评价MLIR项目中Linalg Dialect的设计思想？
https://wzzju.github.io/mlir/jax/xla/2022/09/12/mlir-pass/
浅析MLIR在Pass优化中的应用
https://zhuanlan.zhihu.com/p/446836964
MLIR中Dialects分类及关联
https://www.lei.chat/zh/posts/mlir-codegen-dialects-for-machine-learning-compilers/
机器学习编译器代码生成相关MLIR Dialect
https://www.lei.chat/zh/posts/mlir-vector-dialect-and-patterns/
MLIR Vector Dialect以及Patterns
https://www.lei.chat/zh/posts/mlir-linalg-dialect-and-patterns/
MLIR Linalg Dialect以及Patterns
https://www.jeremykun.com/2023/08/10/mlir-running-and-testing-a-lowering/
MLIR — Running and Testing a Lowering
https://github.com/KEKE046/mlir-tutorial
Hands-On Practical MLIR Tutorial
https://www.cnblogs.com/BobHuang/p/18249482
从零开始教你写一个MLIR Pass
StableHLO
stablehlo是OpenXLA项目在MLIR基础上的扩展。
官网：
https://github.com/openxla/stablehlo
算子spec：
https://openxla.org/stablehlo/spec
和mlir-opt类似，stablehlo也提供了stablehlo-opt的命令行工具，用于执行pass，进行IR之间的转换。
几种到XLA的IR dialect：
DHLO：Dynamic HLO。
CHLO：client HLO dialect，上层前端的IR。
LHLO：”late”-HLO，经过buffer assignment后的HLO。HLO和LHLO的区别在于HLO注重的是tensor的表达，不考虑到内存的分配。
MHLO：”meta”-HLO dialect，是HLO风格的MLIR dialect， 并且在IR上扩展支持了dynamic shape。XLA HLO的shape是静态不可变的，不同shape需要重新编译；MHLO支持动态shape，IR本身有能力表达shape计算和动态shape信息的传递。
LMHLO：”late”-“meta”-HLO dialect。是LHLO风格的MLIR dialect。即内存分配之后的IR，也就是无动态shape的IR。
参考：
https://zhuanlan.zhihu.com/p/404706825
mlir-hlo cpu jit
https://zhuanlan.zhihu.com/p/470439442
elementwise fusion(hlo vs mhlo vs linalg)
https://zhuanlan.zhihu.com/p/622562160
XLA IR：HLO、LHLO、MHLO和LMHLO
https://zhuanlan.zhihu.com/p/609386195
hlo –> linalg
