仓颉 High-Level IR 设计与实现

涂玏

博士毕业于中山大学，2018年加入华为编程语言实验室，先后参与AI领域算子编程语言和仓颉编程语言项目。目前主要负责仓颉语言的编译前端实现，主要涉及的技术方向包括：多层级IR、程序分析、编译优化、元编程等

01 背景与动机

传统的编译架构通常基于抽象语法树（Abstract SyntaxTree，即 AST）和类三地址码形式的中间表达（Intermediate Representation，即 IR）两层数据结构建立：

• AST层面通常负责程序的语义分析、类型推断、语法糖变换等工作 
• IR 层面通常负责程序的编译优化和进一步的二进制生成

AST通常与语言强相关，不同的语言语法不同会有一套不同的 AST具体实现。而 IR 则通常设计为语言、平台无关来解耦编译前端和后端，从而提供一个稳定的编译优化平台。业界广泛应用的 LLVM 编译框架的核心即为 LLVMIR 及基于此提供的各项编译基础设施能力。通过语言、平台无关的架构设计，积累了大量可复用的分析优化资产。

而仓颉编程语言是一款面向全场景智能的新一代编程语言，主打原生智能化、天生全场景、高性能、强安全。融入鸿蒙生态，为开发者提供良好的编程体验。

为了让仓颉语言能够易学易用，降低开发者入门门槛和开发过程中的心智负担，仓颉支持函数式、命令式和面向对象等多种常见的开发范式和编程模式，并支持了轻量化线程模型、模式匹配、流运算符等各类现代语言特性和语法糖让开发者简洁高效地表达各种业务逻辑。同时，仓颉语言追求编码即安全，除类型系统和自动内存管理外，仓颉还提供各种运行时检查（包括数组下标越界检查、类型转换检查、数值计算溢出检查、以及字符串编码合法性检查等）用于保证代码安全。

上述语言设计极大的提升了仓颉语言的开发效率和安全能力，但也对语言的具体实现提出了相应的挑战和诉求：

• 仓颉语言的多范式支持和各类现代语言特性提供了高抽象层次的程序表达能力。如何在编译器中更好的识别和利用这些高抽象表达中的语义信息来进行编译优化提高运行性能 
• 运行时检查虽然能完备地识别和拦截程序运行中的错误，但也会带来额外的运行开销。如何通过程序分析技术在编译期提前识别部分 场景来消除这部分的运行开销是一个获得安全和性能之间更好平衡的关键方法

此时，传统基于 AST和 语言、平台无关 IR 的编译架构（仓颉也选择对接到 LLVMIR 上来复用社区已有的大量分析优化和代码生成相关资产）难以满足上述需求，具体体现在：

1. AST十分贴近源码，因此

• 虽然完整地保留了程序中的结构和语句对应的语义信息，但缺乏显式的控制流信息，难以完成复杂的数据流分析
• 随着仓颉语言的演进，特性的变化和语法的变更都会体现 AST的实现变化。因此在 AST上实现的各类分析优化都需要重新适配，在工程实现角度也存在较大的代价

2. LLVMIR 具备良好的数据流分析能力，但因其与语言无关的通用设计，也缺失了捕捉更多仓颉 specific 语义信息的机会。且 LLVMIR的抽象层次较低，与仓颉源码之间的映射差异较大，在程序分析时难以给出一个精确源码位置的报错信息

02 业界现有编程语言分析

著名计算机科学家 David Wheeler 有一句名言：All problems in computer sciencecan besolved by another level ofindirection。当传统 AST + IR 的两层架构无法满足需求时，大家的思路都不约而同地尝试在编译器中引入额外的程序表达层。

Rust

Rust 团队在 2016 年在其编译架构中正式引入了额外的一层 Mid-LevelIR（简称 MIR），其主要目的是：

• 基于 MIR 提供的数据流分析能力，实现更准确的程序分析能力，特别是 Rust ownership 机制相关的 borrowcheck 检查能力
• 基于 MIR 实现更多 Rust-Specific 的编译优化，与 LLVMIR 上提供的 low-level optimizations 互补，进一步提升程序的运行性能

Swift

Swift 团队也在其编译架构中引入了额外的一层 Swift Intermediate Language（简称 SIL），其主要目的是：

• 基于 SIL提供的数据流分析能力，实现更准确的编译期代码检查，包括变量初始化检查、死代码检查、分支完备性检查等
• 基于 SIL实现更多 high-level的编译优化，如 Witness/VTable 优化、闭包内联、堆栈内存分配优化、标量替换等

03 仓颉 High-Level IR

因此，我们在仓颉的编译架构中也引入了一层 Cangjie High-LevelIR（简称 CHIR），并基于 CHIR 提供的数据流分析能力，实现：

• 更准确的编译期代码检查（包括但不限于：变量初始化检查、死代码检查、数组越界检查、整数运算溢出检查、除零检查），从而在一定程度上减少因运行时检查带来的额外开销，并通过用户友好的编译器报错信息提升开发体验
• 更丰富的程序分析和编译优化能力。通过 CHIR 保留更多仓颉程序中的高抽象语义信息并用于程序分析和编译优化（包括但不限于：虚函数调用优化、冗余指令消除、函数副作用分析、Range Analysis、逃逸分析、SROA、循环不变量外提、循环展开），从而提升运行性能

引入 CHIR 后的仓颉总体编译流程如下图所示：

CHIR 在结构上总体可分为以下个部分:

• 导入全局变量/函数的声明部分：对应仓颉源码中对其他包的导入声明 
• 类型定义部分：对应仓颉源码中 struct/class/interface 等自定义类型的定义
• 全局变量定义部分：对应仓颉源码中的全局变量和静态成员变量的定义
• 函数定义部分：对应仓颉源码中全局函数和自定义类型成员函数的定

此外，CHIR 也提供了一套完整的类型系统和属性机制，用于提供类型和其他语义信息的补充。由于篇幅限制，我们无法在本文章中展开描述 CHIR 的所有细节，这里我们先简单通过一个与仓颉源码对照的例子来让读者有一个直观的感受。

以下面一个仓颉代码为例：

其对应的 CHIR 如下所示（注：这里由于篇幅限制，裁剪和略去了不相关的部分，仅展示了与 CHIR 结构相关的部分代码）：

上述示例中的 [] 即为属性机制，用于提供属性信息标注，如 [readOnly] 表示被标注的变量或函数参数为只读类型。而 : 及其后面的内容即为类型标注，用于提供类型信息，如 @_ZN7default11coefficientE: Float64& 即表示该全局变量的类型为 Float64& ，表示对 Float64 类型的引用，支持对该变量的修改，对应仓颉源码中的 var 修饰符对应的可变性语义。

CHIR 支持的指令语句总体也可以归纳为以下几类：

• 基础数学运算类：包括加减乘除、位运算、逻辑运算、移位运算、比较运算等操作 
• 字面量类：包括创建整数、浮点数、布尔、字符、字符串等类型的字面量操作
• 复合对象创建及解构：包括创建 Tuple 对象和对其的解构操作
• 访存操作类：包括内存分配、内存读写、受限的内存地址偏移操作
• 函数调用类：包括直接函数调用和虚函数调用操作
• 类型相关操作类：包括类型转换和类型判定操作
• 异常相关操作类：包括各类可能产生异常的操作（如：函数调用、数学运算、内存分配等）和异常的抛出、获取等操作
• 基础控制流操作类：包括控制流的直接跳转、条件跳转
• 高阶控制流操作类：包括原生支持的 If、While、ForIn、Lambda 等（注：在文章后面部分会有更具体的介绍）
• 可扩展的 Intrinsic 操作类：提供 CHIR 的指令语句扩展能力，在具体实现中主要是对运行时提供的 Intrinsic 接口的封装
• 其他：如轻量化线程创建操作、VArray对象创建等仓颉特有特性的对应操作

同样由于篇幅限制，我们无法在本文章中对所有 CHIR 支持的指令进行一一具体介绍。这里我们从挑选了部分常用的类别指令语句，并简单通过一些与仓颉源码对照的例子来让读者有一个直观的感受。

对于上述没有展开介绍的 CHIR 部分，后续读者可关注仓颉开源的相关信息，我们会将 CHIR 的详细设计文档一并开源公布。

下面我们着重介绍 CHIR 针对上述需求和挑战在设计上的一些要点。

CHIR 设计要点 1：支持嵌套的语法结构

业界常见的 IR 通常会使用 BasicBlock 的语法结构来提供更显式的控制流语义信息。在 BasicBlock 中，所有语句指令都严格按顺序执行，而控制流的转移仅能通过 BasicBlock 的末尾语句指令（通常称为 Terminator）来进行。因此，函数中的代码可以被组织为以 BasicBlock 为节点构成的一个 ControlFlowGraph（简称 CFG)。

上述 IR 结构可以很好地提供控制流信息，但由于程序中所有的控制流语句都被转换为 BasicBlock 之间的跳转，也导致了一些问题：

• 原程序中产生控制流转移的语句在被归一映射为 BasicBlock 间跳转后，部分语义信息被丢失而无法进行更准确的分析优化。例如，在做循环相关的分析优化时，我们已难以判断此时 BasicBlock 的跳转是来自于循环还是 If等语句，因此通常都需要对 IR 进行分析并尝试重构原循环结构来提取相关信息，而这会产生额外的编译开销和部分复杂场景下的不准确性
• 现代语言中通常都包含作用域的概念，而控制流相关语句大多会形成作用域间的嵌套。在转换为 BasicBlock 之间的跳转后，这些嵌套结构被“破坏和铺平”，对应作用域信息也被丢失，而作用域的信息对变量生命周期等分析优化非常重要

以下面C++中的一个简单循环代码为例：

其对应的 LLVMIR 如下所示：

因此，CHIR 在上述 IR 的理念基础上进行了扩展，支持可嵌套 CFG 的语法结构：

• Block 中所有语句指令依赖严格按顺序执行，且 Block 末尾的 Terminator 语句指令定义 Block 之间的跳转。Block 间的跳转构成当前层级的 CFG
• Block 中的语句支持按其定义的语义规则将控制流转移到其所包含的一个或多个子 CFG，而控制流在进入子 CFG 并完成后会返回至该语句中，然后基于语义规则继续进入其他子 CFG 或者结束当前语句执行并按顺序执行 Block 中的下一条语句

对比可以看出，在引入了嵌套 CFG 的支持后，CHIR 可以在提供显式控制流语义信息的同时，直接引入对 If、While 甚至 For 语句的支持，且嵌套的 CFG 天然就对应的原程序中的作用域结构，从而保留更多语义信息用于程序分析和编译优化

以下面的仓颉代码为例

其对应的 CHIR 如下：

一些上述示例中涉及的 CHIR 语法介绍：

1）[] 用于提供属性信息的标注，如 [readOnly] 表示被标注的变量或函数参数为只读类型；

2） Allocate(T) 语句表示申请一个 T 类型的内存，并获得该内存位置的引用，对应一个 T& 引用类型的结果，后续可基于 Load 和 Store 语句对该部分内存进行读写；

3) Exit 语句表示控制流结束并退出当前 CFG。Exit 语句不携带值，因此CHIR 中函数返回值是通过函数入口处的一个被标记为 [ret] 的特殊变量来存放。

在示例中可以看到，CHIR 可以支持原生的 If语句，而无需过早地将其转换为 Block 之间的跳转导致丢失作用域信息。但需要注意的是，为了遵从“控制流进入语句包含的子 CFG 后必须返回至语句中”的原则，示例源代码中 if表达式里的 return表达式对应的控制流转移动作需要通过等价地程序变换，在 CHIR 中”延迟“到 If语句完成后进行。

为了实现这个等价变换，我们会额外生成一些变量来标记需要“延迟”的控制流转移动作。需要指出的是，在通过原生的 If语句完成相关的分析优化后，我们可以对 If语句包含的子 CFG 进行一次类似函数内联的操作，将 If语句再次转换为 Block 之间的跳转。此时，这些额外的变量可以通过常量分析等优化消除，从而不在二进制上产生实际的运行开销。

CHIR 设计要点 2：保留仓颉类型的语义信息

仓颉语言设计了一套强大的类型系统来支持不同的编程范式，而类型本身也携带了丰富的语义信息（如：父子类型关系、内存布局、虚表等）。

CHIR 也希望完整地保留仓颉类型的语义信息，除了内建支持大部分仓颉中的基础类型（如：整数类型、浮点类型、Bool类型、String类型、Array类型等），还原生支持 Struct、Enum、Class、Interface 等自定义类型。

以下面的仓颉代码为例：

其对应的 CHIR 如下：

如上示例，通过记录的类型父子继承关系、成员变量、成员函数、vtable 等信息，可以很方便地在 CHIR 上完成诸如虚函数调用消除、SROA 等编译优化

04 小结

总的来说，CHIR 是针对仓颉语言设计实现的需求，在 AST和 LLVMIR 之间引入的的一层高抽象层次的 IR。基于 CHIR 提供的数据流分析和保留更多仓颉程序中语义信息的能力，可以更好地支持各项程序分析和编译优化。下一步我们还将继续发挥 CHIR 的特点，探索更多能力的支持：

• 在编译器中进一步实现其他分析优化，如：box/unbox优化、跨过程/跨包的分析优化
• 作为仓颉开放生态中的一环，向广大开发者提供可扩展的仓颉程序分析和编译优化平台。目前仓颉团队也已经基于 CHIR 与北京大学、南京大学、湖南大学等多个研究团队开展程序分析的相关工作

后续我们也将就 CHIR 上所实现的程序分析和编译优化发布更多的技术文章，敬请关注。

参考文献

https://llvm.org/pubs/2004-01-30-CGO-LLVM.html

https://rust-lang.github.io/rfcs/1211-mir.html

https://github.com/swiftlang/swift/blob/main/docs/SIL.rst

https://www.youtube.com/watch?v=Ntj8ab-5cvE

 仓颉编程语言通用版本SDK Beta试用报名链接