别人的精品程序员swift

Swift的高级中间语言：SIL

2018-09-30  本文已影响416人  sea_biscute

简介

在LLVM的官方文档中对Swift的编译器设计描述如下： Swift编程语言是在LLVM上构建，并且使用LLVM IR和LLVM的后端去生成代码。但是Swift编译器还包含新的高级别的中间语言，称为SIL。SIL会对Swift进行较高级别的语义分析和优化。 我们下面分析一下SIL设计的动机和SIL的应用，包括高级别的语义分析，诊断转换，去虚拟化，特化，引用计数优化，TBAA(Type Based Alias Analysis)等。并且会在某些流程中加入对SIL和LLVM IR对比。

SIL介绍

SIL是为了实现swift编程语言而设计的,包含高级语义信息的SSA格式的中间语言.SIL包含以下功能:

和LLVM IR不同,SIL一般是target无关的独立格式的表示,可用于代码分发.但是也可以和LLVM一样表达具体target概念. 如果想查看更多SIL的实现和SIL通道的开发信息,可以查看SIL开发手册（原英文文档为SILProgrammersManual.md）。

我们下面对Clang的Swift编译器的传递流程进行对比：

编译流程对比

Clang编译器流程

image

Clang编译流程存在以下问题：

Swift编译器流程

Swift作为一个高级别和安全的语言具有以下特点：

高级别语言

安全语言

Swift编译流程图如下：

image

Swift编译器提供的SIL具有以下优势：

SIL的设计

SIL流程分析

Swift编译器作为高级编译器，具有以下严格的传递流程结构。 Swift编译器的流程如下

SIL操作流程分析

SILGen

SILGen遍历Swift进行了类型检查的AST，产生 raw SIL.SILGen产生的SIL格式具有如下属性:

这些特性会被接下来的确保优化和诊断检查使用，这两项在 raw SIL上一定会运行。

确保优化和诊断检查

在SILGen之后,会在raw SIL上运行确定顺序的优化。我们并不希望编译器产生的诊断改变编译器的进展，所以这些优化的设计是简单和可预测.

这个算法的核心作用体现为:流程图中的临界如果在流分析前被拆分的话,会使得运算更近高效. 原文: A key point in the algorithm is that it can be much more effective if the critical edges in the flowgraph have been split before the flow analysis is performed.

如果诊断通道完成后,会产生规范SIL.

说完了处理raw SIL的特定流程,我们对上面提到的优化通道: optimization passes进行下说明.

泛型优化

SIL获取语言特定的类型信息,使得无法在LLVM IR实现的高级优化在swift编译器中得以实现.

func min<T: Comparable>(x: T, y: T) -> T {
return y < x ? y : x
}

从普通的泛型展开

func min<T: Comparable>(x: T, y: T, FTable: FunctionTable) -> T {
let xCopy = FTable.copy(x)
let yCopy = FTable.copy(y)
let m = FTable.lessThan(yCopy, xCopy) ? y : x
FTable.release(x)
FTable.release(y)
return m
}

在确定入参类型时,比如Int,可以优化为

func min<Int>(x: Int, y: Int) -> Int {
return y < x ? y : x
}

从而减少泛型调用的开销

SIL语法

SIL依赖于swift的类型系统和声明,所以SIL语法是swift的延伸.一个.sil文件是一个增加了SIL定义的swift源文件.swift源文件只会针对声明进行语法分析.swift的func方法体(除了嵌套声明)和最高阶的代码会被SIL语法分析器忽略.在.sil文件中没有隐式import.如果使用swift或者Buildin标准组件的话必须明确的引入. 以下是一个.sil文件的示例

sil_stage canonical
​
import Swift
​
// 定义用于SIL函数的类型
​
struct Point {
 var x : Double
 var y : Double
}
​
class Button {
 func onClick()
 func onMouseDown()
 func onMouseUp()
}
​
// 定义一个swift函数,函数体会被SIL忽略
func taxicabNorm(_ a:Point) -> Double {
 return a.x + a.y
}
​
// 定义一个SIL函数
// @_T5norms11taxicabNormfT1aV5norms5Point_Sd 是swift函数名taxicabNorm重整之后的命名
sil @_T5norms11taxicabNormfT1aV5norms5Point_Sd : $(Point) -> Double {
bb0(%0 : $Point):
 // func Swift.+(Double, Double) -> Double
 %1 = function_ref @_Tsoi1pfTSdSd_Sd
 %2 = struct_extract %0 : $Point, #Point.x    //萃取Point结构体内的x
 %3 = struct_extract %0 : $Point, #Point.y    ////萃取Point结构体内的y
 %4 = apply %1(%2, %3) : $(Double, Double) -> Double  //冒号前为计算体实现通过引用的展开,冒号后为类型说明
 return %4 : Double  //返回值
}
​
// 定义一个SIL虚函数表,匹配的是动态分派中函数实现的id,这个动态分派是在已知的静态类的类型虚函数表中
sil_vtable Button {
 #Button.onClick!1: @_TC5norms6Button7onClickfS0_FT_T_
 #Button.onMouseDown!1: @_TC5norms6Button11onMouseDownfS0_FT_T_
 #Button.onMouseUp!1: @_TC5norms6Button9onMouseUpfS0_FT_T_
}

SIL阶段

decl ::= sil-stage-decl
sil-stage-decl ::= 'sil_stage' sil-stage
​
sil-stage ::= 'raw'
sil-stage ::= 'canonical'

基于操作的不同阶段,SIL拥有不同的声明.

SIL类型

sil-type ::= '/pre> '*'? generic-parameter-list? type

SIL的类型是通过$符号进行标记的。SIL的类型系统和swift的密切相关.所以$之后的类型会根据swift的类型语法进行语法分析。

类型降级: type lowering

swift的正式类型系统,倾向于对大量的类型信息进行抽象概括.但是SIL目标是展示更多的实现细节,这个区别也体现在SIL的类型系统中.所以把正式类型降级为较低类型的操作称为类型降级。

提取区别:Abstraction Difference

包含未约束类型的通用函数一定会被非直接调用.比如分配充足内存和创建地址指针指向这块地址。如下的泛型函数

func generateArray<T>(n : Int, generator : () -> T) -> [T]

函数generator会通过一个隐式指针,指向存储在一个非直接调用的地址中,(可以参考之前static vs dynamic dispatch中虚函数表的设计和实现).在处理任意类型值时操作都是一样的.

SIL对于类型的提取区别的设计是，在每个级别的代替中，提取数值都可以被使用。

为了可以实现如上设计,泛型实例的正式类型应该一直使用非替换正式类型的提取方式进行降级.例如

struct Generator<T> {
 var fn : () -> T
}
var intGen : Generator<Int>

其中intGen.fn拥有代替类型()->Int，可以被降级为@callee_owned () -> Int，可以直接返回结果.但是如果更恰当的使用非代替方式，()->T就会变成@callee_owned () -> @out Int

当使用非代替的提取方式进行类型降级时，可以看做将拥有相同构造的类型中的具体类型替换为现有类型,以此来实现类型降级. 对于g 的Generator<(Int, Int) -> Float>,g.fn是使用()->T进行降级的，简单理解就是,类型是否是具体类型,如果是,才能进行提取方式进行降级,不然只能产生

@callee_owned () -> @owned @callee_owned (@in (Int, Int)) -> @out Float.

所以提取区别来代替通用函数中类型的标准是:是否是具体类型.is materializable or not 这个系统具有通过重复代替的方式实现提取方式的属性.所以可以把降级的类型看做提取方式的编码. SILGen已经拥有了使用提取方式转换类型的工序. 目前只有函数和元祖类型会通过提取区别进行改变.

合法的SIL类型

SIL类型的值应该是这样的:

类型T满足一下条件才是一个合法的SIL类型

注意，在递归条件内的类型，还需要是正式类型。例如泛型内的参数，仍然是Swift类型，而不是SIL降级类型。

地址类型

地址类型$*T指针指向的是任意引用的值或者$T。
地址不是引用计数指针，不能被retained或released。

Box类型

本地变量和非直接的数值类型都是存储在堆上的，@box T是一个引用计数类型，指向的是包含了多种T的盒子。盒子使用的是Swift的原生引用计数。

Metatype类型

SIL内的metatype类型必须描述自身表示：

函数类型

SIL中的函数类型和Swift中的函数类型有以下区别：

VTables

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm decl ::= sil-vtable
sil-vtable ::= 'sil_vtable' identifier '{' sil-vtable-entry* '}'
​
sil-vtable-entry ::= sil-decl-ref ':' sil-linkage? sil-function-name

SIL使用class_method, super_method, objc_method,和 objc_super_method来表示类方法的动态分派dynamic dispatch class_method 和 super_method的实现是通过sil_vtable进行追踪的.sil_vtable的声明包含一个类的所有方法.

class A {
 func foo()
 func bar()
 func bas()
}
​
sil @A_foo : $@convention(thin) (@owned A) -> ()
sil @A_bar : $@convention(thin) (@owned A) -> ()
sil @A_bas : $@convention(thin) (@owned A) -> ()
​
sil_vtable A {
 #A.foo!1: @A_foo
 #A.bar!1: @A_bar
 #A.bas!1: @A_bas
}
​
class B : A {
 func bar()
}
​
sil @B_bar : $@convention(thin) (@owned B) -> ()
​
sil_vtable B {
 #A.foo!1: @A_foo
 #A.bar!1: @B_bar
 #A.bas!1: @A_bas
}
​
class C : B {
 func bas()
}
​
sil @C_bas : $@convention(thin) (@owned C) -> ()
​
sil_vtable C {
 #A.foo!1: @A_foo
 #A.bar!1: @B_bar
 #A.bas!1: @C_bas
}

swift的AST包含重载关系,可以用于在SIL的虚函数表中查找衍生类重载方法. 为了避免SIL方法是thunks,方法名是连接在原始方法实现之前.

Witness Tables

decl ::= sil-witness-table
sil-witness-table ::= 'sil_witness_table' sil-linkage?
 normal-protocol-conformance '{' sil-witness-entry* '}'

SIL将通用类型动态分派所需的信息编码为witness表.这些信息用于在生成二进制码时产生运行时分配表(runtime dispatch table).也可以用于对特定通用函数的SIL优化.每个明确的一致性声明都会产生witness表.通用类型的所有实例共享一个通用witness表.衍生类会继承基类的witness表.

protocol-conformance ::= normal-protocol-conformance
protocol-conformance ::= 'inherit' '(' protocol-conformance ')'
protocol-conformance ::= 'specialize' '<' substitution* '>'
 '(' protocol-conformance ')'
protocol-conformance ::= 'dependent'
normal-protocol-conformance ::= identifier ':' identifier 'module' identifier

witness的关键在于协议一致性.它是对于具体类型协议一致性的唯一标识.

sil-witness-entry ::= 'base_protocol' identifier ':' protocol-conformance
sil-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name
sil-witness-entry ::= 'associated_type' identifier
sil-witness-entry ::= 'associated_type_protocol'
 '(' identifier ':' identifier ')' ':' protocol-conformance

witness table由以下内容构成

witness table作用

swift中的协议是通过结构体实现的,可以支持交互.例如参数,属性都可以是结构体.当将结构体传递给协议参数时,结构体特定的部分可能会丢失(在编译期).协议的witness table就可以发挥作用(在运行时).

Default Witness Tables

decl ::= sil-default-witness-table
sil-default-witness-table ::= 'sil_default_witness_table'
 identifier minimum-witness-table-size
 '{' sil-default-witness-entry* '}'
minimum-witness-table-size ::= integer

SIL编码要求默认witness table有开放(resilient)的默认实现.包含以下条件

强制方法的开放的默认实现,存储在协议的元数据中. 默认witness表关键在在自身协议.只有公共可见协议才需要默认witness表.私有协议和内部协议是对外部组件不可见的,所以他们没有增加新的强制方法的开放性问题.

sil-default-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name

默认witness表目前只包含一项内容

全局变量

数据流错误

数据流错误可能存在于Raw SIL中,swift从语义上将那些条件定义为错误,所以他们必须使用诊断通道进行诊断,并且不能存在于规范SIL中. 定义初始化 swift要求所有的本地变量在使用前必须被初始化.在构造函数中,结构体,枚举或类类型的实例变量必须在对象被使用前初始化. 未全面覆盖(unreachable)的控制流 unreachable在raw SIL中生成,标记错误的控制流.例如对于非Void的函数没有返回值,或者switch没有完全覆盖所有的条件.这种dead code消解的保证,可以避免unreachable的基础block,也可以避免方法返回不合法的空类型.

运行时错误

一些操作,比如无条件的检查转换次数失败或者编译器Buildin.trap.都会引起运行时错误,这种错误会无条件的终止当前操作.如果可以检验运行时错误会发生或者已经发生.只要将它们排列到程序操作之后就可以将这些运行时错误重新安排.例如对于没有确定开始和结尾的for循环代码

// Given unknown start and end values, this loop may overflow
for var i = unknownStartValue; i != unknownEndValue; ++i {
 ...
}

会将内存溢出挂起,产生loop的关联运行时错误,之后检测循环的起始和结束点.只要循环体对于当前的操作没有可见影响即可.

未定义的行为

某些操作的错误使用成为未定义行为.例如对于Buildin.RawPointer的不可用未检测的类型转换.或者使用低于LLVM说明的编译器内建函数,调用当前LLVM不支持的行为.SIL程序中的未定义行为是无意义的,就像C中的未定义行为一样,没有语义对其进行预测.未定义行为不应该被合法的SIL文件触发,但是在SIL级别不一定会被检测和证实.

调用协议

以下内容讨论swift函数是如何生成SIL的.

swift调用协议 @convention(swift) swift本地方法默认使用siwft调用协议是. 入参为原组的函数被递归解构为单独的参数,即包含被调用的基础块的入口,也包含调用者的apply说明

func foo(_ x:Int, y:Int)
​
sil @foo : $(x:Int, y:Int) -> () {
entry(%x : $Int, %y : $Int):
 ...
}
​
func bar(_ x:Int, y:(Int, Int))
​
sil @bar : $(x:Int, y:(Int, Int)) -> () {
entry(%x : $Int, %y0 : $Int, %y1 : $Int):
 ...
}
​
func call_foo_and_bar() {
 foo(1, 2)
 bar(4, (5, 6))
}
​
sil @call_foo_and_bar : $() -> () {
entry:
 ...
 %foo = function_ref @foo : $(x:Int, y:Int) -> ()
 %foo_result = apply %foo(%1, %2) : $(x:Int, y:Int) -> ()
 ...
 %bar = function_ref @bar : $(x:Int, y:(Int, Int)) -> ()
 %bar_result = apply %bar(%4, %5, %6) : $(x:Int, y:(Int, Int)) -> ()
}

调用以繁琐数据类型作为入参和输出值的函数时

func foo(_ x:Int, y:Float) -> UnicodeScalar
​
foo(x, y)

在SIL内如下体现

%foo = constant_ref $(Int, Float) -> UnicodeScalar, @foo
%z = apply %foo(%x, %y) : $(Int, Float) -> UnicodeScalar

swift方法调用协议@convention(method) 方法调用协议用于独立方法的调用协议.柯里化method,使用self作为内部和外部参数.如果是非柯里化函数,self会在最后被传入

struct Foo {
 func method(_ x:Int) -> Int {}
}
​
sil @Foo_method_1 : $((x : Int), @inout Foo) -> Int { ... }

witness方法调用协议@convention(witness_method) witness方法调用协议是用于witness tables中的协议witness方法.它几乎等同于方法调用协议,只有对通用类型参数处理方面不同.对于非witness方法来说,机器协议可能会通过方法类型将方法签名进行静态转换.但是因为witness必须在Self类型下进行多态分配,所以Self相关的元数据必须通过最大化的提取规则传输.

C调用协议@convention(c) 在swift的C组件编译器中,C类型会被SIL对照到swift类型.C的函数入参和返回值,都会被SIL平台调用协议忽略. SIL和swift目前都不能调用包含可变参数的C的方法.

OC调用协议@convention(objc_method) SIL中的OC方法使用规范和ARC内一致.也可以从OC定义中引入属性. 使用@convention(block)并不会影响block的引用计数.

在SIL中OC方法的self参数是非柯里化的最后一个参数.就像原生swift方法

@objc class NSString {
 func stringByPaddingToLength(Int) withString(NSString) startingAtIndex(Int)
}
​
sil @NSString_stringByPaddingToLength_withString_startingAtIndex \
 : $((Int, NSString, Int), NSString)

IR级别的将self作为第一个参数的行为在SIL中提取了的.比如现存的_cmd方法参数.

基于类型的别名分析: type based alias analysis

SIL提供了两种类型别名分析(TBAA: Type Based Alias Analysis):类TBAA和类型访问TBAA

指令集

感兴趣可以自行查看SIL指令集

初始化和销毁

alloc_stack

sil-instruction ::= 'alloc_stack' sil-type (',' debug-var-attr)*
​
%1 = alloc_stack $T
// %1 has type $*T

在栈区开辟充分符合T类型的内存空间。指令的返回结果是初始化的内存地址。

如果类型的尺寸在运行时才能确定，编译器必须动态初始化内存。所以并不能确保内存一定是初始化在栈区，例如如果是特别大的数值，可能会在堆区初始化，栈区持有指针。

alloc_stack标记了值声明周期的开始。在结束时必须使用dealloc_stack销毁。

内存不能被retain，如果想初始化可retain的类型，使用alloc_box。

总结：alloc_stack在栈区为值类型开辟内存。不使用引用计数。

alloc_box

sil-instruction ::= 'alloc_box' sil-type (',' debug-var-attr)*
​
%1 = alloc_box $T
//   %1 has type $@box T

在堆上开辟足够大的内存来支持各种类型的T，以@box持有引用计数。这个指令的结果是@box的引用计数持有的box，project_box是要来过去box内部的值的地址的。

box初始化时引用计数为1，但是内存并不会被初始化。box持有内部的值，在引用计数为0时使用destory_addr对内部值进行释放，无法释放box的值没有被初始化的情况。这时候需要用到dealloc_box。

总结：alloc_box在堆上初始化指针类型的值，并且需要手动管理内存。

alloc_box和alloc_stack对比

alloc_box和alloc_stack最大的区别在于值的生命周期。举例，如果在闭包之外有一个变量声明，在闭包内使用了该变量。变量的值是可以被修改的，所以需要使用alloc_box来引用变量。

对于var声明的变量，因为可以多次修改它的值，甚至在作用域外也可以修改。所以使用alloc_box管理引用计数。

优化：Alloc box to stack

在SILGen阶段，会对闭包内使用变量的情况，通过alloc_box进行管理。

在SIL guaranteed transformations阶段，即生成正式SIL的阶段，会对于在闭包内没有进行值修改的变量内存分配进行优化，将alloc_box替换为alloc_stack。这个功能是在AllocBoxToStack组件内实现的。内部实现是将堆区不必要的初始化移动到栈区。

参考资料

上一篇下一篇

猜你喜欢

热点阅读