Antkillerfarm Hacking V7.5

toolchain » 编译原理（二）, MLIR（二）, StableHLO

2024-07-16 :: 6161 Words

编译原理
- 文法
- SSA
- PPCG
- PLUTO
- MPS
- ANTLR
- 参考
MLIR
- model-explorer
- 参考
StableHLO

编译原理

文法

LL(k)：这里的”k”表示解析器可以向前看k个符号来做出决策。

https://blog.csdn.net/huihuisd/article/details/103777331

乔姆斯基4型文法

https://zhuanlan.zhihu.com/p/94424139

LL, LR文法浅析

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

model-explorer

model-explorer是google推出的可视化工具，支持对于MLIR的可视化。

官网：

https://github.com/google-ai-edge/model-explorer

安装&运行：

pip install ai-edge-model-explorer
model-explorer

参考

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基础上的扩展。

注意：XLA HLO IR是google自定义的IR，而StableHLO IR是MLIR的一个dialect。

官网：

https://github.com/openxla/stablehlo

算子spec：

https://openxla.org/stablehlo/spec

和mlir-opt类似，stablehlo也提供了stablehlo-opt的命令行工具，用于执行pass，进行IR之间的转换。

stablehlo-opt --vhlo-to-version="target=1.7.0" --vhlo-legalize-to-stablehlo ./a.mlirbc -o ./a.mlir

mlirbc是StableHLO的byte code，而mlir则是普通可供人阅读的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。

pytorch模型导出stablehlo IR。

model_exported = torch.export.export(torch_model, inputs)
stablehlo_gm = torch_xla.stablehlo.exported_program_to_stablehlo(
    model_exported,
    options
)

参考：

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

您的打赏，是对我的鼓励