【AICon】探索RAG 技术在实际应用中遇到的挑战及应对策略!AICon精华内容已上线73%>>> 了解详情
写点什么

详解 Golang 中间代码生成

  • 2019-12-04
  • 本文字数:13219 字

    阅读完需:约 43 分钟

详解 Golang 中间代码生成

1.4 中间代码生成

前两节介绍的 词法与语法分析 以及 类型检查 两个部分都属于编译器前端,它们负责对源代码进行分析并检查其中存在的词法和语法错误,经过这两个阶段生成的抽象语法树已经不存在任何的结构上的错误了,从这一节开始就进入了编译器后端的工作 — 中间代码生成机器码生成 了,这里会介绍 Go 语言编译的中间代码生成阶段。


中间代码 是一种应用于抽象机器的编程语言,它设计的目的主要是帮助我们分析计算机程序,在编译的过程中,编译器会在将语言的源代码转换成目标机器上机器码的过程中,先把源代码转换成一种中间的表述形式,这里要介绍的就是 Go 语言如何将抽象语法树转换成 SSA 表示的中间代码。

__1. 中间代码生成

Go 语言编译器的中间代码具有静态单赋值(SSA)的特性,我们在介绍 Go 语言编译过程 中曾经介绍过静态单赋值,对这个特性不了解的读者可以回到上面的文章阅读相应的部分,当然也可以自行搜索学习相关的知识,不过在这里哪怕对 SSA 一无所知,也不会影响对这一节的理解。


我们再来回忆一下编译阶段入口的主函数中关于中间代码生成的部分,在这一段代码中会初始化 SSA 生成的配置,在配置初始化结束之后会调用 funccompile 对函数进行编译:


func Main(archInit func(*Arch)) {    // ...
initssaconfig()
for i := 0; i < len(xtop); i++ { n := xtop[i] if n.Op == ODCLFUNC { funccompile(n) } }
compileFunctions()}
复制代码


这一节将分别介绍配置的初始化以及函数编译两部分内容,我们会以 initssaconfigfunccompile 这两个函数作为入口来分析中间代码生成的具体过程和实现原理。

__1.1. 配置初始化

我们从 initssaconfig 函数开始介绍配置初始化的过程,这个函数的执行过程总共可以被分成三个部分,首先是初始化一个新的 Types 结构体:


func initssaconfig() {    types_ := ssa.NewTypes()
_ = types.NewPtr(types.Types[TINTER]) _ = types.NewPtr(types.NewPtr(types.Types[TSTRING])) _ = types.NewPtr(types.NewPtr(types.Idealstring)) _ = types.NewPtr(types.NewSlice(types.Types[TINTER])) _ = types.NewPtr(types.NewPtr(types.Bytetype)) _ = types.NewPtr(types.NewSlice(types.Bytetype)) // ... _ = types.NewPtr(types.Errortype)
复制代码


当前结构体中存储了指向所有 Go 语言中基本类型的指针,比如 BoolInt8、以及 String 等,除了生成这些类型之外还会使用 NewPtr 为其中的一些类型生成指向这些类型的指针:



NewPtr 函数的主要作用就是根据类型生成指向这些类型的指针,同时它会根据编译器的配置将生成的指针类型缓存在当前类型中,优化类型指针的获取效率:


func NewPtr(elem *Type) *Type {    if t := elem.Cache.ptr; t != nil {        if t.Elem() != elem {            Fatalf("NewPtr: elem mismatch")        }        return t    }
t := New(TPTR) t.Extra = Ptr{Elem: elem} t.Width = int64(Widthptr) t.Align = uint8(Widthptr) if NewPtrCacheEnabled { elem.Cache.ptr = t } return t}
复制代码


随后会根据当前的 CPU 架构初始化 SSA 配置 ssaConfig,我们会向 NewConfig 函数传入目标机器的 CPU 架构、上述代码初始化的 Types 结构体、上下文信息和 Debug 配置:


ssaConfig = ssa.NewConfig(thearch.LinkArch.Name, *types_, Ctxt, Debug['N'] == 0)
复制代码


该函数会根据传入的 CPU 架构设置用于生成中间代码和机器码的操作:


func NewConfig(arch string, types Types, ctxt *obj.Link, optimize bool) *Config {    c := &Config{arch: arch, Types: types}    c.useAvg = true    c.useHmul = true    switch arch {    case "amd64":        c.PtrSize = 8        c.RegSize = 8        c.lowerBlock = rewriteBlockAMD64        c.lowerValue = rewriteValueAMD64        c.registers = registersAMD64[:]        c.gpRegMask = gpRegMaskAMD64        c.fpRegMask = fpRegMaskAMD64        c.FPReg = framepointerRegAMD64        c.LinkReg = linkRegAMD64        c.hasGReg = false    case "amd64p32":    case "386":    case "arm":    case "arm64":    // ...    case "wasm":    default:        ctxt.Diag("arch %s not implemented", arch)    }    c.ctxt = ctxt    c.optimize = optimize
// ... return c}
复制代码


这里会设置当前编译器使用的指针和寄存器大小、可用寄存器列表、掩码等编译选项,所有的配置项一旦被创建,在整个编译期间都是只读的并且被全部编译阶段共享,也就是中间代码生成和机器码生成这两部分都会使用这一份配置完成自己的工作。


initssaconfig 方法调用的最后,会初始化一些编译器会用到的 Go 语言运行时的方法:


assertE2I = sysfunc("assertE2I")    assertE2I2 = sysfunc("assertE2I2")    assertI2I = sysfunc("assertI2I")    assertI2I2 = sysfunc("assertI2I2")    deferproc = sysfunc("deferproc")    Deferreturn = sysfunc("deferreturn")    Duffcopy = sysvar("duffcopy")    Duffzero = sysvar("duffzero")    // ...
复制代码


这些方法会在对应的 runtime 包结构体 Pkg 中创建一个新的符号 obj.LSym,表示上述的方法已经被注册到运行时 runtime 包中,我们在后面的中间代码生成中直接使用这些方法。

__1.2. 遍历和替换

在生成中间代码之前,我们还需要对抽象语法树中节点的一些元素进行替换,这个替换的过程就是通过 walk 和很多以 walk 开头的相关函数实现的,简单展示几个相关函数的签名:


func walk(fn *Node)func walkappend(n *Node, init *Nodes, dst *Node) *Nodefunc walkAppendArgs(n *Node, init *Nodes)func walkclosure(clo *Node, init *Nodes) *Nodefunc walkCall(n *Node, init *Nodes)func walkcompare(n *Node, init *Nodes) *Nodefunc walkcompareInterface(n *Node, init *Nodes) *Nodefunc walkcompareString(n *Node, init *Nodes) *Nodefunc walkexpr(n *Node, init *Nodes) *Nodefunc walkexprlist(s []*Node, init *Nodes)func walkexprlistcheap(s []*Node, init *Nodes)func walkexprlistsafe(s []*Node, init *Nodes)func walkprint(nn *Node, init *Nodes) *Nodefunc walkinrange(n *Node, init *Nodes) *Nodefunc walkpartialcall(n *Node, init *Nodes) *Nodefunc walkrange(n *Node) *Nodefunc walkselect(sel *Node)func walkselectcases(cases *Nodes) []*Nodefunc walkstmt(n *Node) *Nodefunc walkstmtlist(s []*Node)func walkswitch(sw *Node)
复制代码


这些函数会将一些关键字和内建函数转换成真正的函数调用,panicrecover 这两个内建函数就会被在上述方法中被转换成 gopanicgorecover 两个真正存在的函数。



上面是从关键字或内建函数到其他实际存在函数的映射,包括管道、哈希相关的操作、用于创建结构体对象的 makenew 关键字以及一些控制流中的关键字 select 等。


转换后的全部函数都属于运行时 runtime 包,我们能在 src/cmd/compile/internal/gc/builtin/runtime.go 文件中找到这里出现的函数,但是这里的函数都没有任何的实现,其中只包含了函数签名和定义。


func makemap64(mapType *byte, hint int64, mapbuf *any) (hmap map[any]any)func makemap(mapType *byte, hint int, mapbuf *any) (hmap map[any]any)func makemap_small() (hmap map[any]any)func mapaccess1(mapType *byte, hmap map[any]any, key *any) (val *any)// ...
func makechan64(chanType *byte, size int64) (hchan chan any)func makechan(chanType *byte, size int) (hchan chan any)// ...
复制代码


上面的代码只是让编译器能够找到对应符号的函数定义而已,真正的函数实现都在另一个 runtime 包中,Go 语言的主程序在执行时会调用 runtime 中的函数,也就是说关键字和内置函数的功能其实是由语言的编译器和运行时共同完成的。

__Channel

接下来,我们可以简单了解一下几个管道操作在遍历节点时是如何转换成运行时对应方法的,首先介绍向管道中发送消息或者从管道中接受消息,在编译器中会分别使用 OSENDORECV 表示这两个不同的操作:


func walkexpr(n *Node, init *Nodes) *Node {    // ...    case OSEND:        n1 := n.Right        n1 = assignconv(n1, n.Left.Type.Elem(), "chan send")        n1 = walkexpr(n1, init)        n1 = nod(OADDR, n1, nil)        n = mkcall1(chanfn("chansend1", 2, n.Left.Type), nil, init, n.Left, n1)    // ...}
复制代码


当遇到 OSEND 操作时,会使用 mkcall1 来创建一个操作为 OCALL 的节点,这个节点中包含当前调用的函数 chansend1 和几个参数,新的 OCALL 节点会替换当前的 OSEND 节点修改当前的抽象语法树。


在中间代码生成的阶段遇到 ORECV 操作时,编译器的处理与遇到 OSEND 时相差无几,我们也只是将 chansend1 换成了 chanrecv1,其他的参数没有太大的变化:


n = mkcall1(chanfn("chanrecv1", 2, n.Left.Type), nil, &init, n.Left, nodnil())
复制代码


使用 close 关键字的 OCLOSE 操作也会在 walkexpr 函数中被转换成调用 closechanOCALL 节点:


func walkexpr(n *Node, init *Nodes) *Node {    // ...    case OCLOSE:        fn := syslook("closechan")
fn = substArgTypes(fn, n.Left.Type) n = mkcall1(fn, nil, init, n.Left) // ...}
复制代码


对于 Channel 的这些内置操作都会在编译期间就转换成几个运行时执行的函数,很多人都想要了解 Channel 底层的实现,但是并不知道函数的入口,经过这里的分析我们就知道只需要在分析 chanrecv1chansend1closechan 几个函数就能理解管道的发送、接受和关闭的实现了。

__1.3. 编译

经过 walk 函数的处理之后,AST 的抽象语法树就不再会改变了,Go 语言的编译器会使用 compileSSA 函数将抽象语法树转换成中间代码,我们可以先看一下当前函数的实现:


func compileSSA(fn *Node, worker int) {    f := buildssa(fn, worker)    pp := newProgs(fn, worker)    genssa(f, pp)
pp.Flush()}
复制代码


buildssa 就是用来构建 SSA 形式中间代码的方法,我们其实可以使用命令行工具来观察当前中间代码的生成过程,假设我们有以下的 Go 语言源代码:


// hello.gopackage hello
func hello(a int) int { c := a + 2 return c}
复制代码


我们可以使用如下的命令来获取上述代码在生成最后中间代码期间经历的 N 个版本的 SSA 中间代码以及最后的汇编代码:


$ GOSSAFUNC=hello go build hello.gogenerating SSA for hellobuildssa-enter.   AS l(3).   .   NAME-hello.~r1 a(true) g(1) l(3) x(8) class(PPARAMOUT) intbuildssa-body.   DCL l(4).   .   NAME-hello.c a(true) g(3) l(4) x(0) class(PAUTO) tc(1) used int
. AS l(4) colas(true) tc(1). . NAME-hello.c a(true) g(3) l(4) x(0) class(PAUTO) tc(1) used int. . ADD l(4) tc(1) int. . . NAME-hello.a a(true) g(2) l(3) x(0) class(PPARAM) tc(1) used int. . . LITERAL-2 l(4) tc(1) int
. RETURN l(5) tc(1). RETURN-list. . AS l(5) tc(1). . . NAME-hello.~r1 a(true) g(1) l(3) x(8) class(PPARAMOUT) int. . . NAME-hello.c a(true) g(3) l(4) x(0) class(PAUTO) tc(1) used intbuildssa-exit// ...
复制代码


这个命令会首先打印出 hello 函数对应的抽象语法树,它会分别输出当前函数的 EnterNBodyExit 三个属性,打印这些属性的工作其实就由下面的函数完成的,因为函数太复杂所以在这里我们已经省略了:


func buildssa(fn *Node, worker int) *ssa.Func {    name := fn.funcname()    var astBuf *bytes.Buffer
var s state
fe := ssafn{ curfn: fn, log: printssa && ssaDumpStdout, } s.curfn = fn
s.f = ssa.NewFunc(&fe) s.config = ssaConfig s.f.Type = fn.Type s.f.Config = ssaConfig
// ...
s.stmtList(fn.Func.Enter) s.stmtList(fn.Nbody)
ssa.Compile(s.f) return s.f}
复制代码


ssaConfig 就是我们在这里的第一小节中初始化的,其中包含了与 CPU 架构相关的函数和配置,随后的中间代码生成其实也分成两个阶段,第一个阶段是使用 stmtList 以及相关函数将 AST 表示的中间代码转换成基于 SSA 的中间代码,第二个阶段会调用 ssa 包的 Compile 函数对 SSA 中间代码进行多轮的转换。

__AST 到 SSA

stmtList 方法的主要功能就是为传入数组中的每一个节点调用 stmt 方法,在这个方法中编译器会根据节点操作符的不同将当前 AST 转换成 SSA 中间代码:


func (s *state) stmt(n *Node) {    // ...
switch n.Op { case OCALLFUNC: if isIntrinsicCall(n) { s.intrinsicCall(n) return } fallthrough
case OCALLMETH, OCALLINTER: s.call(n, callNormal) if n.Op == OCALLFUNC && n.Left.Op == ONAME && n.Left.Class() == PFUNC { if fn := n.Left.Sym.Name; compiling_runtime && fn == "throw" || n.Left.Sym.Pkg == Runtimepkg && (fn == "throwinit" || fn == "gopanic" || fn == "panicwrap" || fn == "block" || fn == "panicmakeslicelen" || fn == "panicmakeslicecap") { m := s.mem() b := s.endBlock() b.Kind = ssa.BlockExit b.SetControl(m) } } case ODEFER: s.call(n.Left, callDefer) case OGO: s.call(n.Left, callGo) // ...
}
// ...}
复制代码


从上面节选的代码中我们会发现,在遇到函数调用、方法调用、使用 defer 或者 go 时都会执行 call 生成调用函数的 SSA 节点:


func (s *state) call(n *Node, k callKind) *ssa.Value {    var sym *types.Sym    fn := n.Left    switch n.Op {    case OCALLFUNC:        sym = fn.Sym    case OCALLMETH:        // ...    case OCALLINTER:        // ...    }    dowidth(fn.Type)    stksize := fn.Type.ArgWidth()
s.stmtList(n.List)
t := n.Left.Type args := n.Rlist.Slice() for i, n := range args { f := t.Params().Field(i) s.storeArg(n, f.Type, argStart+f.Offset) }
var call *ssa.Value switch { case k == callDefer: call = s.newValue1A(ssa.OpStaticCall, types.TypeMem, deferproc, s.mem()) case k == callGo: call = s.newValue1A(ssa.OpStaticCall, types.TypeMem, newproc, s.mem()) case sym != nil: call = s.newValue1A(ssa.OpStaticCall, types.TypeMem, sym.Linksym(), s.mem()) // ... } call.AuxInt = stksize s.vars[&memVar] = call
res := n.Left.Type.Results() fp := res.Field(0) return s.constOffPtrSP(types.NewPtr(fp.Type), fp.Offset+Ctxt.FixedFrameSize())}
复制代码


首先,从 AST 到 SSA 的转化过程中,编译器会生成将函数调用的参数放到栈上的中间代码,处理参数之后才会生成一条运行函数的命令 ssa.OpStaticCall;如果这里使用的是 defer 关键字,就会插入 deferproc 函数,使用 go 创建新的 Goroutine 时会插入 newproc 函数符号,在遇到其他情况时会插入表示普通函数对应的符号。


在上述方法中生成的 SSA 中间代码其实就是如下的形式:


compiling hellohello func(int) int  b1:    v1 = InitMem <mem>    v2 = SP <uintptr>    v3 = SB <uintptr> DEAD    v4 = LocalAddr <*int> {a} v2 v1 DEAD    v5 = LocalAddr <*int> {~r1} v2 v1    v6 = Arg <int> {a}    v7 = Const64 <int> [0] DEAD    v8 = Const64 <int> [2]    v9 = Add64 <int> v6 v8 (c[int])    v10 = VarDef <mem> {~r1} v1    v11 = Store <mem> {int} v5 v9 v10    Ret v11
复制代码


这里的 SSA 中间代码其实就是使用 GOSSAFUNC=hello go build hello.go 命令生成的,也是将 AST 转换成 SSA 的过程。

__多轮转换

虽然我们在 stmt 以及相关方法中生成了 SSA 中间代码,但是这些中间代码却仍然需要编译器进行优化以去掉无用代码并对操作数进行精简,也就是上述过程返回的中间代码需要经过 ssa.Compile 函数的多次处理:


func Compile(f *Func) {    if f.Log() {        f.Logf("compiling %s\n", f.Name)    }
phaseName := "init"
for _, p := range passes { f.pass = &p p.fn(f) }
phaseName = ""}
复制代码


这是删除了很多打印日志和性能分析功能的 Compile 函数,SSA 需要经历的多轮处理也都保存在 passes 变量中,其中包含了每一轮处理的名字、使用的函数以及可选的 required 标志:


var passes = [...]pass{    {name: "number lines", fn: numberLines, required: true},    {name: "early phielim", fn: phielim},    {name: "early copyelim", fn: copyelim},    // ...    {name: "loop rotate", fn: loopRotate},    {name: "stackframe", fn: stackframe, required: true},    {name: "trim", fn: trim},}
复制代码


目前的编译器总共引入了将近 50 个需要执行的过程,我们能在 GOSSAFUNC=hello go build hello.go 命令生成的文件中看到非常多熟悉的名称,例如最后一个 trim 阶段就生成了如下的 SSA 代码:


pass trim begin  pass trim end [738 ns]hello func(int) int  b1:    v1 = InitMem <mem>    v10 = VarDef <mem> {~r1} v1    v2 = SP <uintptr> : SP    v6 = Arg <int> {a} : a[int]    v8 = LoadReg <int> v6 : AX    v9 = ADDQconst <int> [2] v8 : AX (c[int])    v11 = MOVQstore <mem> {~r1} v2 v9 v10    Ret v11
复制代码


经过将近 50 轮处理的 SSA 中间代码相比处理之前已经有了非常大的改变,执行效率和过程也会有比较大的提升,多轮的处理已经包含了一些机器特定的修改,包括根据目标架构对代码进行改写,不过这里就不会展开介绍每一轮处理的具体内容了。

__2. 总结

中间代码的生成过程其实就是从 AST 抽象语法树到 SSA 中间代码的转换过程,在这期间会对语法树中的关键字在进行一次更新,更新后的语法树会经过多轮处理转变成最后的 SSA 中间代码,这里的代码大都是巨长的 switch 语句和复杂的函数以及调用栈,分析和阅读起来也非常困难。


很多 Go 语言中的关键字和内置函数都是在这个阶段被转换成运行时包中方法的,作者在后面的章节会从具体的语言关键字和内置函数的角度介绍一些数据结构和函数的实现。

__3. Reference


**本文转载自 Draveness 技术博客。


原文链接:https://draveness.me/golang/compile/golang-ir-ssa.html


2019-12-04 08:002056

评论

发布
暂无评论
发现更多内容

SQL 优化(三):使用覆盖索引

hungxy

升级企业数智化底座,助力企业实现数智连接

用友BIP

数智底座

制造企业实施MES系统受到的影响因素有哪些?

优秀

MES系统

NFTScan 推出「NFTScan Connect」计划,支持早期 Web3 初创团队

NFT Research

#Web3

打造数智物流底座,华为云DTSE助力物联云仓解锁物流新“速度”

华为云开发者联盟

云计算 华为云 华为云开发者联盟 企业号 6 月 PK 榜

🔥🔥🔥我可算把【年中复盘】玩明白了

禅道项目管理

总结 复盘

强化学习从基础到进阶-案例与实践[5.1]:Policy Gradient策略梯度-Cart pole游戏展示

汀丶人工智能

人工智能 深度学习 强化学习 策略梯度

Java 网络编程 —— 客户端协议处理框架

快乐非自愿限量之名

Java url

特别呈现|腾讯云 X K+ 峰会共同打造软件工程新生态

CODING DevOps

什么是MES?国内做MES系统的企业哪家好?

优秀

MES系统 mes

golang 实现四层负载均衡

蓝胖子的编程梦

nginx 负载均衡 LVS MySQL 高可用 #go

对标世界一流!构建更适合国有企业的全面预算体系!

用友BIP

全面预算

用友:时序数据库要更懂业务场景

用友BIP

AI自动生成代码,是时候冷静下来思考如何保障代码安全了

华为云PaaS服务小智

云计算 华为云 代码检查 华为开发者大会 AI编程

使用 diffusers 训练你自己的 ControlNet 🧨

互联网工科生

controlnet

企业号 7 月 PK 榜,火热开启!

InfoQ写作社区官方

热门活动 企业号 7 月 PK 榜

处理开发者账号到期导致APP下架的方处理开发者账号到期导致APP下架的方法

雪奈椰子

金域医学2023“域见杯”医检人工智能开发者大赛正式启动

华为云开发者联盟

人工智能 华为云 华为云开发者联盟 企业号 6 月 PK 榜

强化学习从基础到进阶-案例与实践[4.2]:深度Q网络DQN-Cart pole游戏展示

汀丶人工智能

人工智能 深度学习 强化学习 DQN

神级程序员,都在用哪些生产力工具?

互联网工科生

程序员 工具 生产力

敏捷在医疗器械开发中的应用 —— Q&A

ShineScrum捷行

解放开发者——5个好用的低代码开发平台

树上有只程序猿

IM即时通讯APP在聊天场景中的应用

WorkPlus

Rainbond助力“信创应用”迁移上云

北京好雨科技有限公司

云原生 rainbond 信创云 企业号 7 月 PK 榜

无法安装此app,因为无法验证其完整性 ,解决方案

雪奈椰子

强化学习从基础到进阶–案例与实践[11]:AlphaStar论文解读、监督学习、强化学习、模仿学习、多智能体学习、消融实验

汀丶人工智能

人工智能 深度学习 强化学习 7月日更

在找稳定的企业级数据云平台?奇点云DataSimba R4.9 LTS发布

奇点云

产品升级 奇点云 数据基础设施 DataSimba

2023-06-30:给你一个 rows * cols 大小的矩形披萨和一个整数 k, 矩形包含两种字符: ‘A‘ (表示苹果)和 ‘.‘ (表示空白格子), 你需要切披萨 k-1 次,得到 k 块披

福大大架构师每日一题

Go 算法 rust Go 语言 福大大架构师每日一题

【6.23-6.30】写作社区优秀技术博文一览

InfoQ写作社区官方

热门活动 优质创作周报

低代码平台源代码对程序有哪些作用?

这我可不懂

低代码 源代码 JNPF

低代码助力内部系统开发

高端章鱼哥

低代码 系统开发 JNPF

详解 Golang 中间代码生成_文化 & 方法_Draveness_InfoQ精选文章