gc编译器使用特殊的类似Lisp的面向对象语言（ DSL ）来描述静态单一分配 （SSA）优化规则。
我建议分析这种语言的主要元素，其特征和局限性。
作为练习，让我们向Go编译器添加一条以前没有生成的指令，以优化表达式a*b+c 。
这是有关Go SSA编译器后端内部内容的系列文章中的第一篇，因此，除了查看规则本身的DSL描述之外，我们还将考虑相关组件以为下一个会话创建必要的基础。
引言
前端go编译器在从带注释的AST生成SSA视图时结束。 负责转换的功能可以在cmd / compile / internal / gc / ssa.go中找到。 SSA后端的入口点是ssa.Compile函数，该函数在cmd / compile / internal / ssa / compile.go中定义 。
术语学| EN | RU | 价值 |
|---|
| 编译器前端 | 编译器前端 | 语法分析和词法分析，有时是类型解析，中间表示接近源代码，通常带有注释的AST。 |
| 编译器后端 | 编译器后端 | 下层优化和中间表示，代码生成。 |
| 形式 | 形式 | 几乎是“表达式”（expression）一词的同义词。 通常在Lisp中， form是命名程序元素（列表或原子）的一种相当普遍的方式。 |
| 优化阶段 | 优化阶段 | 在程序上执行某种算法。 “通过”一词在某种程度上是模棱两可的，因为一个阶段可以执行多次通过，并且/或者使用其他阶段通用的代码。 |
在阅读本文时，如果发现一个完全无法理解的术语，值得报告，可以将其添加到此表中。
SSA Go优化器包含几个阶段，每个阶段都通过编译函数。 有些阶段使用所谓的“重写规则”，即将一个SSA序列转换为另一个（可能更优化）的规则。
转换规则使用S-expressions描述。 这些表达式的元素是ssa.Value 。 在最简单的情况下，这些规则允许您将一个ssa.Value替换为另一个。
例如，下面的代码折叠了8位常量的乘法：
(Mul8 (Const8 [c]) (Const8 [d])) -> (Const8 [int64(int8(c*d))])
SSA值主要有两类：高级的，几乎独立于目标机器的值，以及特定于体系结构的值（通常映射到1合1机器指令）。
针对这两个类别描述了优化。 首先，是所有架构的通用高层，然后是面向平台的。
与规则关联的所有代码都位于cmd / compile / internal / ssa / gen中 。 我们将考虑两套：
- genericOps.go-与机器无关的操作。
- AMD64Ops.go-特定于
GOARCH=AMD64 （64位x86）的操作。
在抽象机上工作的前几个阶段之后，执行所谓的降低，这导致从genericOps过渡到一组特定体系结构。 在我们的示例中，这将是AMD64Ops 。 此后，所有后续阶段都将根据第二类进行演示。
优化器之后，代码生成器开始起作用。 对于AMD64，可以在软件包cmd / compile / internal / amd64中找到代码生成的实现。 代码生成器的任务是将ssa.Block和ssa.Value替换为传递给汇编器的 obj.Prog序列。 汇编器将收集机器代码，在链接之后即可准备执行。
优化规则
如果具有操作定义的文件命名为“ ${ARCH}Ops.go ”，则优化规则将放置在“ ${ARCH}.Rules ”中。
高级规则执行简单的转换， 常量表达式的大多数折叠以及一些简化后续处理的转换。
每个具有低级规则的文件都包含两个部分：
- 降低-用等效机器代替抽象操作。
- 优化本身。
减少对机器的操作的示例：
(Const32 [val]) -> (MOVLconst [val]) // L - long, 32- (Const64 [val]) -> (MOVQconst [val]) // Q - quad, 64- | | generic op | AMD64 op
在低级优化中，执行了许多重要的优化操作，例如降低操作成本 ，部分嵌入并利用处理器中可用的内存寻址模式的功能。
操作具有助记符名称，通常称为操作码。 与体系结构相关的操作的操作码通常反映实际指令的名称。
规则描述语言语法
基本语法在rulegen.go中进行了描述：
还值得一提的是， .Rules文件中允许使用“ // ”注释。
让我们看一个包含所有这些元素的简单示例：
Opcode=ADDLconst - 32- : AuxInt=c - , `x` : : (ADDLconst [c] x) && int32(c)==0 -> x | / | / | | / | / | | / | / | / ( `&&` ) ,
所有这些解释性签名都不是有效规则记录的一部分。
此规则将x+0转换为x 。 条件部分中的所有内容都是正常的Go代码，
除非限于表达式，其结果应为bool 。
您可以调用rewrite.go中定义的谓词 。
除了通常的操作码之外，还可以使用产生以下规则的组合：
(ADD(Q|L)const [off] x:(SP)) -> (LEA(Q|L) [off] x) // Q|L alternation: (ADDQconst [off] x:(SP)) -> (LEAQ [off] x) (ADDLconst [off] x:(SP)) -> (LEAL [off] x) // `x`: (ADDQconst [off] (SP)) -> (LEAQ [off] (SP)) (ADDLconst [off] (SP)) -> (LEAL [off] (SP))
(SP)是genericOps.go中的操作之一，表示加载指向硬件堆栈的指针。 对于没有硬件SP体系结构，将对其进行仿真。
模板中变量的功能（ ->左侧的S表达式）：
- 变量，例如
x ，不带:捕获任何内容 - 像常规变量一样，
_捕获任何值，但是结果可以忽略
// : ADDQconst, // : (ADDQconst _) -> v (ADDQconst x) -> (ADDQconst x)
如果未指定AuxInt （在方括号中表示），则该规则将在任何AuxInt值上AuxInt 。 与{}参数类似（下面有关它们）。
名称v表示最外层捕获的形式。
例如，对于表达式(ADDQconst (SUBQconst x))外部形式为ADDQconst 。
变量可以多次使用，这使您可以要求S表达式的多个部分相互匹配：
(ADDQconst [v] (ADDQconst [v] x)) // , , "x+2+2" (x+v+v).
规则类型
在某些情况下，需要明确指出生成和/或匹配形式的类型。
类型在“三角括号”中指示，作为C ++模板中的类型参数：
// typ.UInt32 - BTSLconst. // BSFL typ.UInt32, // . (Ctz16 x) -> (BSFL (BTSLconst <typ.UInt32> [16] x))
除了类型之外，还有“字符”（或更普遍的是Aux属性）。
(StaticCall [argsWidth] {target} mem) -> (CALLstatic [argsWidth] {target} mem)
[argsWidth] Value.AuxInt 。 对于StaticCall传递的参数的总大小{target} Value.Aux 。 对于StaticCall调用函数<typ.UInt32> Value.Type 。 值类型
Aux和AuxInt的语义因操作而异。 在这种情况下，文档的最佳来源是*Ops.go文件。 每个opData操作码opData都有一个aux字段，该字段描述了如何解释这些字段。
对于类型的描述，使用包cmd / compile / internal / types 。 一些类型特定于SSA后端，例如types.TypeFlags ，其余类型在cmd/compile/internal/gc和cmd/compile/internal/ssa之间通用。
特殊类型
有一种特殊类型的types.TypeMem ，它可以一次执行多个功能：
- 允许您按内存访问模式对
ssa.Value进行排序和分组。 特别是，这保证了基本块框架内正确的执行顺序（以下有关它们）。 - 确定程序中内存流的状态。 如果指令修改了内存，则此操作将生成类型为
types.TypeMem的新SSA值。
像OpPhi的特殊含义OpPhi ，内存在优化程序的许多阶段都得到了特殊的解释。
关于披披Phi的角色因阶段而异。
在编译器的SSA工作之初， Phi发挥了其经典作用，并根据导致我们获得该值的执行路径来表达对值的选择。
例如，如果一个块中有两个跳转，并且都修改了内存，那么目标块将接收到等于(Phi mem1 mem2)的内存。 周期也会拖拉Phi值。
另一个特殊类型是types.TypeFlags提到的types.TypeFlags 。 此类型描述指令生成CPU标志 。
在这种情况下，诸如ADDQ指令尽管会生成标志，但它们的类型不是types.Flags ，而是带有clobberFlags属性标记。
types.Flags用于突出显示诸如CMPQ之类的指令的结果，这些指令不会将结果写入其任何显式操作数，而只会更新处理器的内部状态，该状态可由下一条指令使用。
像SETL这样的指令允许您“读取”标志并将其作为ssa.Value返回，可以将其放置在寄存器中。
L-less than G-greater than | | (SETL (InvertFlags x)) -> (SETG x) | ,
SSA检验程序
假设我们有一个像这样的程序（ example.go ）：
package example func fusedMulAdd(a, b, c float64) float64 { return a*c + b }
我们可以看一下为fusedMulAdd函数生成的SSA代码：
$ GOSSAFUNC=fusedMulAdd go tool compile example.go > ssa.txt
现在检查工作（当前）目录：
ssa.txt包含tekt转储。ssa.html是自动生成的，它包含相同的信息，但格式更具交互性，并且易于阅读。 尝试在浏览器中打开。
fusedMulAdd的机器代码为了表达，字符~r3重命名为ret 。
v7 (4) MOVSD a(SP), X0 v11 (4) MOVSD c+16(SP), X1 v12 (4) MULSD X1, X0 v6 (4) MOVSD b+8(SP), X1 v13 (4) ADDSD X1, X0 v15 (4) MOVSD X0, ret+24(SP) b1 (4) RET
这是在lower阶段（ssa.html）之后的fusedMulAdd的SSA程序的样子：
文字格式SSA程式如果出于某种原因您想复制此内容：
lower [77667 ns] b1: v1 (?) = InitMem <mem> v2 (?) = SP <uintptr> v7 (?) = LEAQ <*float64> {~r3} v2 v8 (3) = Arg <float64> {a} v9 (3) = Arg <float64> {b} v10 (3) = Arg <float64> {c} v12 (+4) = MULSD <float64> v8 v10 v13 (4) = ADDSD <float64> v12 v9 v14 (4) = VarDef <mem> {~r3} v1 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4)
将其转换为S表达式：
(MOVQstore {~r3} (SP) (ADDSD (MULSD (Arg {a}) (Arg {c})) (Arg {b})))
regalloc阶段之后的SSA这是regalloc阶段的ssa.html的输出。
regalloc [87237 ns] b1: v1 (?) = InitMem <mem> v14 (4) = VarDef <mem> {~r3} v1 v2 (?) = SP <uintptr> : SP v8 (3) = Arg <float64> {a} : a[float64] v9 (3) = Arg <float64> {b} : b[float64] v10 (3) = Arg <float64> {c} : c[float64] v7 (4) = LoadReg <float64> v8 : X0 v11 (4) = LoadReg <float64> v10 : X1 v12 (+4) = MULSD <float64> v7 v11 : X0 v6 (4) = LoadReg <float64> v9 : X1 v13 (4) = ADDSD <float64> v12 v6 : X0 v15 (4) = MOVSDstore <mem> {~r3} v2 v13 v14 Ret v15 (line +4)
添加新的优化规则
在具有FMA的处理器上，我们可以用一条指令而不是两条指令来计算a*c + b 。
以CL117295作为Ilya Tokar著作权的依据。
为了您的方便，我准备了一个 diff补丁 。
1.添加新操作-FMASD
在文件compile/internal/ssa/gen/AMD64Ops.go找到AMD64ops slice AMD64ops并添加一个新元素（任何位置）：
{
由于之前没有任何操作(fp,fp,fp -> fp) ，因此您需要定义一个新的限定符：
fp01 = regInfo{inputs: nil, outputs: fponly} fp21 = regInfo{inputs: []regMask{fp, fp}, outputs: fponly} + fp31 = regInfo{inputs: []regMask{fp, fp, fp}, outputs: fponly}
2.添加优化规则
(ADDSD (MULSD xy) z) -> (FMASD zxy)
更加正确的实施并非不是无条件的，并且将检查FMA的可用性。 我们将假定目标计算机上肯定存在FMA。
编译器使用config进行此类检查：
// config.useFMA=false, . (ADDSD (MULSD xy) z) && config.useFMA-> (FMASD zxy)
如何检查FMA支持？如果lscpu在系统上可用，那么例如：
$ lscpu | grep fma
3.代码生成的实现
现在，在compile/internal/amd64/ssa.go定义的ssaGenValue函数中，您需要为FMASD添加代码生成：
func ssaGenValue(s *gc.SSAGenState, v *ssa.Value) { switch v.Op { case ssa.OpAMD64FMASD: p := s.Prog(v.Op.Asm())
现在，一切准备就绪，可以测试我们的新优化工作。 添加新指令非常罕见，通常新的优化是基于已经定义的SSA操作进行的。
检查结果
第一步是从更新的gen/AMD64Ops.go和gen/AMD64.Rules生成Go代码。
接下来，我们需要构建新的编译器：
go install cmd/compile
现在，在编译同一示例时，我们得到了不同的机器代码：
- v7 (4) MOVSD a(SP), X0 - v11 (4) MOVSD c+16(SP), X1 - v12 (4) MULSD X1, X0 - v6 (4) MOVSD b+8(SP), X1 - v13 (4) ADDSD X1, X0 - v15 (4) MOVSD X0, ret+24(SP) - b1 (4) RET + v12 (4) MOVSD b+8(SP), X0 + v7 (4) MOVSD a(SP), X1 + v11 (4) MOVSD c+16(SP), X2 + v13 (4) VFMADD231SD X2, X1, X0 + v15 (4) MOVSD X0, ret+24(SP) + b1 (4) RET
基本块
既然完成了最困难的工作，就让我们来谈谈基础块 。
我们上面优化的值以块为单位，而这些块在功能上。
像ssa.Value这样的块是抽象的并且与机器相关。 所有块都只有一个入口点，并且有0到2个目标块（取决于块的类型）。
最简单的块是If ， Exit和Plain ：
Exit块有0个分配块。 这些是叶子块，例如使用panic进行非本地跳转。Plain块有1个分配块。 在完成了该块的所有指令后，可以将其视为无条件跳转。If块有2个目标块。 根据条件（ Block.Control ）执行转换。
以下是将抽象块重写为AMD64块的简单示例：
"then" ( ) | "else" ( ) | | (If (SETL cmp) yes no) -> (LT cmp yes no) (If (SETLE cmp) yes no) -> (LE cmp yes no)
在编译器的SSA部分中的其他优化阶段中，将更详细地考虑块的主题。
优化规则的局限性
SSA后端具有其优势。 在O(1)一些优化是可行的。 但是，还有一些缺点，至少在其实现的某些方面发生变化之前，仅优化器的SSA还是不够的。
假设您要 append ：
xs = append(xs, 'a') xs = append(xs, 'b')
在生成SSA时，代码的高级结构会丢失，并且不是普通函数的append已内置到包含块的主体中。 您将必须编写一个繁琐的规则，以捕获为append生成的整个操作序列。
专门讲.Rules ，此DSL在块（ ssa.Block ）上的工作相当薄弱。 与块关联的任何非平凡的优化都是不可能用这种语言表达的。 无法进行部分块更新。 扔掉块也是不可能的（但是存在First块形式的黑客攻击，用于删除无效代码）。
即使某些缺陷可以解决，大多数编译器也同意没有一种更好的中间形式来表示代码。
走得更快
如果您提出了一些很酷的优化规则，请随时将其发送到go-review.googlesource.com 。 我很乐意评论（添加到CC中的iskander.sharipov@intel.com ）。
快乐的黑客编译器！
奖金材料
Go中添加或更改了SSA规则的良好补丁的示例：
不久前，出现了一个README文档来描述编译器的SSA部分。
推荐阅读。