编译原理笔记

编译原理

概述

高级语言处理过程

  • 预处理:处理库,包,宏
  • 编译器:生成汇编语言(也可能一步到机器代码)
  • 汇编器:生成可重定位的机器代码
  • (链接器)加载器:(和库文件链接,)生成目标机器语言

前端:分析

  • 词法分析
  • 语法分析
  • 语义分析

后端:综合

  • 中间代码生成
  • 代码优化
  • 目标代码生成

和解释对比

  • 编译性能更好
  • 编译更容易优化
  • 编译目标程序独立于源程序
  • 解释可迁移性高

及时编译JIT(Just-In-Time Compiler)

  • 运行时执行程序编译操作
  • 弥补解释执行的不足:把翻译过的机器代码保存起来,以备下一次使用
  • e.g. Java中的JDK,JRE,字节码,虚拟机
  • 和AOT(Ahead-Of-Time Compiler)对比
    • 具备解释器的灵活性:只要有JIT编译器即可运行
    • 性能和AOT等同:运行时编译操作带来一些性能上的损失,但可以利用程序运行特征进行动态优化

词法分析

  • 根据模式(词法规则)得到类别和词的对应关系(记号token=类别+属性),或者说记号流
  • 二义性问题:
    • e.g. 模板中的”>>”和cin中的”>>”
    • 解决办法:查看上下文(Look Head),一般通过与语法分析交互解决,会增加负担;大多数情况词法分析和语法分析的界限明确

过程

  • (除去注释)
  • 分词
  • 生成token

概念

  • 字母表:符号的有限集
  • (字符)串:符号的有限序列,可以是空串$\epsilon$,$|s|$表示串的长度
  • 语言$L(G)$:由开始符号(见文法部分)推得的所有串的集合,可以是空集$\empty$,也可以是${\epsilon}$
    • 语言解决了无穷个串的有穷表示问题
  • 字母表的乘积:笛卡尔积
  • 字母表的幂:多次乘积,0次幂为空串${\epsilon}$
  • 字母表的正闭包:字母表的正数次幂(即非空符号串)的集合
  • 字母表的克林闭包:字母表的幂(即所有符号串)的集合
  • 串的连接:a+b
  • 串的幂:多次连接,0次连接为空串${\epsilon}$
  • 语言上定义有并,连接,幂,正闭包,克林闭包

核心方法:正则表达式

  • 正则表达式$r$定义了正则语言$L(r)$,和语言相比更紧凑,以递归形式定义:分为原子和组合两种
    • $\epsilon$是正则表达式,即$L(\epsilon)={\epsilon}$
    • $a\in \Sigma$,则$a$是正则表达式,即$L(a)={a}$
    • 正则表达式或、连接、闭包、括号(优先级递增)后仍然是正则表达式
  • 正则定义:给一些常用的正则表达式命名
  • 拓展
    • $r^+$:表示一个或多个
    • $r^*$:表示0个或多个
    • $r?$:表示0个或1个
    • $[a-z]$:字母的集合,数字类似
    • $[\hat{}a-z]$:除去字母的集合
    • \b:$[0-9]$
    • \D:$[\hat{ }0-9]$
    • \s:空白符的集合 [\t\n\r\f\v]
    • \S:非空白符的集合 [$\hat{ }$\t\n\r\f\v]
    • \w:字母数字字符 $[a-zA-Z0-9_]$
    • \W:非字母数字字符 $[\hat{ }a-zA-Z0-9_]$
    • $r.$:换行符外任意字符
    • ^:在中括号外使用表示从字符串开始位置开始匹配
    • $:匹配字符串结尾位置
  • 运算规定
    • 左结合
    • *类运算(闭包)优先级最高
    • 最大匹配原则:在达到终结状态时,还会尽可能地向后匹配以获得最大匹配

有限自动机

  • 和正则表达式对应的转换图,输入为字符串,返回值只有接受和拒绝两种

  • DFA:确定有限自动机,对于给定的状态和输入,仅有一条出边,每个时刻只有一种状态

  • NFA:不确定有限自动机,可能有多条出边,每个时刻可能有多种状态,NFA也可能经过$\epsilon$边转换(允许带$\epsilon$边的和不允许的两种NFA是等价的,可以相互转化)

  • 基本概念

    • 字母表
    • 状态集:圈
    • 初始状态:有箭头入边的圈
    • 终止状态:双圈
    • 边:映射
  • NFA和DFA是等价的,同一个RE,一般NFA更简洁,DFA较复杂,DFA内存占用更大,执行更快

  • NFA转化为DFA:子集构造&&最小化

    • 对初始状态闭包并标记作为DFA的初始状态,放入状态集
    • 对未标记的每个状态,标记它,然后对它的每种动作后的转化状态集求闭包,作为DFA的一个状态,并放入状态集,直到所有状态被标记
    • DFA的状态中若包含了NFA的终止状态,则是DFA的终止状态
    • 实现:构建NFA table
    • 最小化:把终止集作为一组,把非终止集作为一组,考虑每组内的状态的输入输出,观察其输出是否可区分,并合并,直至不能合并。
    • DFA的状态是NFA的状态的组合,状态指数增长,但在小规模问题中性能往往不那么糟糕
  • 模拟

    • DFA:字符全部用尽刚好是终止状态则接受,复杂度:$O(len)$,len为字符串长度
    • NFA:字符全部用尽只要有一个状态在终止状态则接受,复杂度:$O(len*N^2)$,N为DFA状态数
  • DFA变为table,在计算机中最后变为分支语句 e.g. table如下

    | | 0 | 1 |
    | —— | —— | —— |
    | S | T | U |
    | T | T | U |
    | U | T | X |

RE转化为NFA

  • 算法:同样是递归定义
    • 对原子RE:由初始态到终止态,边为该原子RE($\epsilon$或$r$)
    • $R1|R2$:形如方片,4边为空边,左节点为起点连接两个子起点,右节点为终点连接两个子终点
    • $R1R2$:形如棍,子终止节点和另一个子开始节点连接作为一个新节点即可
    • $R^*$:形如-0-
    • 手动计算过程:可以反复套用下面三图;也可以把正则表达式放到边上按上述递归情形一步一步地推(哈工大yyds

0

1

  • 词法分析转化流
graph LR
A["自然语言规则描述"] --> B["RE"]
B --> E["(NFA)"]
E --> C["DFA"]
G --> D["table"]
C --> G["Minimal"]
D --> F["if/switch"]
B -.-|lex| F

语法分析

RA/FA的局限性

  • $L={a^nb^n|n\geq 1}$不是正则语言:泵引理
  • 有穷自动机不能记忆,也就不能计数
  • 所有有嵌套结构的语言都不是正则语言

上下文无关文法CFG(Context Free Gramma)

  • 文法:无限制文法、上下文有关文法、上下文无关文法、正则文法

    • 上述文法是子集的关系
    • 分别又称为0,1,2,3型文法
  • 语法是文法的实例
  • 语法形式化定义:4元组$(T,N,S,\sigma)$
    • 终结符T,即token,约定使用小写字母,数字,标点符号,粗体字符串
    • 非终结符N,也称为语法变量,和终结符统称文法符号集,约定使用大写字母,小写或斜体字符串
    • 开始符号S,除非特殊说明,约定第一个产生式的左部即为开始符号
    • 产生式$\sigma: \alpha\to\beta_1|\beta_2|\beta_3$,读作$\alpha$定义$\beta_1$或$\beta_2$或$\beta_3$,其中$\beta_1, \beta_2, \beta_3$称为候选式
    • e.g. $T={0,1},n={A,B},s=a,\sigma={A\to 0A|1A|0B,B\to 0}$
    • 约定在不产生歧义的情况下可以只写产生式
  • 句型:由开始符号推得的串
  • 句子:不包含非终结符的句型
  • 推导(Derivation):通过产生式把非终结符替换,直至只有终结符,它是从生成的角度进行分析
    • $a_0$经过n步推导出$a_n$,则简记为$a_0\Rightarrow^n a_n$
    • 上下文有关文法:在推导时有串前后环境的限制条件 e.g. $BAB\to BBB$
    • 上下文无关文法:随时都能替换,不用管上下文 e.g. $A\to B$
    • 编程语言是上下文有关的,但使用上下文无关分析,一是因为编程语言的很多结构是上下文无关的,二是因为上下文有关文法效率很低,三是编程语言的一些上下文有关的部分可以放在其他阶段处理。
    • 最左(右)推导:每次推导替换最左(右)侧的非终结符
  • 归约:最右推导的逆过程,它是从识别的角度进行分析
  • 分析树
    • 根节点为开始符号,父节点和他的孩子组成一次对产生式的应用
    • 限定推导方式,分析树是唯一的
  • 二义性:对一个语法,存在一个句型,能构造出两颗不同的分析树,即有歧义的。
    • 考虑优先级和结合性:优先级越高,越靠近叶结点。
    • 可以通过引入额外非终结符,生成更多产生式的方法来消除二义性
  • 短语:给定一个句型,其分析树的每一颗子树的边缘
  • 直接短语:分析树高为2的短语。它一定是某个产生式的右部
  • 活前缀:又叫可行前缀,(LR分析时)栈中的内容
  • 规范句型:最右句型
  • 分析器Parser

    • 自顶向下:最左推导
    • 自底向上:最右推导的逆过程,又称最左归约

自顶向下

  • 自顶向下分析:递归下降(有回溯)分析、预测(无回溯)分析

    • 预测分析实现了剪枝,需要看目标句子是否匹配生成式的选择
    • 递归预测分析每一个非终结符都要写一个函数,相互调用,需要程序员编写,开发效率很低
    • 非递归预测分析即表驱动预测分析,本质上是手动递归的PDA=DFA+Stack,较RE可以记忆和计数,主流方式
  • 前缀/左公因子

    • 解决办法:推迟决策
    • 把公因子提出来,引入额外非终结符。
  • 左递归

    • 分为直接和间接两种,递归无法结束
    • 解决办法:重写文法改为等价的右递归,需要引入额外非终结符和$\epsilon$。如下:
  • LL(k)文法

    • LL(k)解析器:从左往右扫描,最左推导,用前k个字符进行预测
    • 要求:生成式不能有相同k位前缀/左公因子(保证推导唯一)&不能出现左递归的问题
    • 实现:可以通过递归,也可以通过更简单的分析表和栈(下推自动机PDA)来。(递归指程序根据过程驱动,非递归指表和栈驱动。)
    • 分析表:第一行为终结符,第一列为非终结符
    • 一般只使用LL(1),因为较大的预测字符,表格大小会指数增长
  • 构造分析表

    • FIRST集:句型中出现的第一个非终结符的集合,即可以从该句型构造出的所有串的首个终结符的所有可能的集合,还可以包含$\epsilon$。
    • FOLLOW集:句型后下一个终结符。约定,句型若在末尾,则$$$在其终结符中。初始符号的FOLLOW集包含$$$
    • 对于$S\to ABC$,若$$\notin C$,FOLLOW(B)=FIRST(C);若$$\in C$,则FOLLOW(B)=FIRST(C)+FOLLOW(S)
    • SELECT集:选用该产生式进行推导时的第一个非终结符的集合。若产生式右部是空串,则该集为产生式左部FOLLOW集。
    • 若$$\notin FIRST(\alpha)$,则$SELECT(A\to\alpha)=FIRST(\alpha)$
    • 若$$\in FIRST(\alpha)$,则$SELECT(A\to\alpha)=(FIRST(\alpha)-{$})\cup FOLLOW(A)$
    • 上述计算集合因为存在依赖关系,所以需要反复计算直至不再变化
    • 根据SELECT集进行填表,行为非终结符,列为终结符,表内为产生式
  • 错误处理

    • 非恐慌模式:非终结符不匹配或对应表项为空即出错
    • 恐慌模式:尽可能地进行匹配
      • 表项为空,忽略输入终结符,因为该输入字符可能是多余的
      • 表项为同步从词法单元(可以由FOLLOW集得到),忽略栈顶非终结符,因为它后面的句子可能匹配上该输入字符
      • 非终结符不匹配,忽略栈顶终结符,因为要尽可能匹配输入字符

自底向上

  • 自底向上比自顶向下更强大,使用更广泛,覆盖了左递归和共同前缀的问题
  • 移入归约解析:四种动作
    • 移入:将$#$从左往右移,即压栈
    • 归约:将字符串左侧逆向应用生成式,即先弹栈,再压栈
    • 接受:直至栈内包含开始符号且输入缓冲区为空
    • 拒绝/报错
  • 句柄:每次归约的符号串
    • 句柄只会出现在栈顶
    • 句柄是句型的最左直接短语
    • 规范句型:栈内符号串LHS+剩余输入。(不包含$$$)
  • LR(k):从左往右,最右推导的逆。向前看k个字符
    • LR看到的内容比LL更多
  • LR分析器
    • 栈:存放状态序列和符号
    • 输入
    • 分析表:动作表(s,a)和跳转表(s,x),其中a是终结符,x是非终结符
    • 驱动程序
    • si,rj:i表示状态号,j表示生成规则号
    • 移入将终结符移入符号栈,同时将状态移入状态栈
    • 归约将字符和状态(字符和状态的数量是一样的)一起出栈,再把生成式的左端入栈,此时需要对该左端非终结符进行GOTO,将对应的状态移入状态栈
    • 操作前后,栈中字符和状态数都是一样的
  • LR(0)
    • 对文法的要求很高,LR(0)分析表中需要没有语法分析动作冲突
    • 只能使用栈顶的信息,没有办法解决冲突的问题
    • 表中某个需要归约,则整行都需要归约
  • LR(0)项目Item
    • e.g. $A\to XYZ$得到4个项目$A\to·XYZ,A\to X·YZ,A\to XY·Z,A\to XYZ·$
    • 第一个项目是移入状态,表示等待移入
    • 中间两个是待约状态
    • 最后一个项目是归约状态,表示需要归约
    • 后继项目:同属一个产生式,圆点位置仅差1个符号的项目
    • 项目描述了句柄识别的状态
    • 从初始项目开始,圆点后如果是非终结符就把该非终结符的移入项目放入来求闭包
    • 状态间通过非终结符或终结符进行转移,再继续求闭包
    • 每个项目集闭包对应一个状态
    • 分析表构造:状态间通过终结符转换填移入;状态间通过非终结符转换填GOTO;归约状态(这里LR(0)保证仅该项目集闭包中仅有一个归约状态)没有GOTO,ACTION全填归约;初始符号的归约状态在符号表的$$$处填acc
  • 增广文法:在初始状态$S$前增加一个状态$S’$,这样能保证初始状态仅出现在一个生成式的左侧,可以用来保证表中只有一个acc
    • 这样可以产生两个项目:初始项目$\cdot S$,归约项目$S\cdot$
  • 冲突
    • 移入-归约冲突:一个项目集闭包(状态)下,同时有归约状态和移入状态
    • 归约-归约冲突:一个项目集闭包(状态)下,同时有不同的归约状态
  • SLR(1):简单的LR(1),又叫SLR
    • 当可以进行归约时使用Follow集向前看一个字符,根据生成式左端的FOLLOW集来决定是否进行归约,可以解决LR(0)中的一些冲突,不足以消除所有的冲突
    • 项目集闭包中可以既有不同的归约状态又有移入状态;归约行的动作可以不全是归约,也可以有不同的归约
    • SLR(1)分析表中需要每个项目集闭包中移入字符集和归约项目的FOLLOW集不能冲突
  • LR(1),又叫LR
    • SLR(1)只使用Follow集还是不够精确
    • 对状态进行细分,LR(1)项目=LR(0)项目+展望符
    • 展望符为一个字符的终结符或$$$,表示使用该归约后应该出现的第一个非终结符,实际上展望符只有在归约状态才有用
    • 初始状态的展望符为$$$;在求闭包时,展望符为生成式左端非终结符在上一次闭包过程后的非终结符,如果没有则要向上继承展望符
    • LR(1)分析表中归约只有在表项非终结符符合展望符才填入
    • 缺点:状态很多,表比较大,开销比较大
  • LALR(1):LookAhead LR(1)
    • 把LR(1)和SLR(1)进行平衡
    • 把LR(1)中相似的(同心的)状态(除展望符外一样的)进行合并。
    • 这种操作只会影响归约操作而不会影响移入操作。所以可能引入归约-归约冲突,但没有移入-归约冲突;识别错误可能被延迟,可能会做多余的归约,但不会做多余的移入。
    • 合并方式:暴力(先构建LR(1)状态再合并)/边构建边合并
    • 最常使用,yacc的底层实现
  • 错误处理:
    • 恐慌模式
    • 短语层次错误恢复
  • Parser的总体发展过程
    • 让归约变得更精确

语义分析

  • 检查上下文关联
  • 语法树遍历
  • 语义翻译:语义分析+中间代码生成
  • 语法制导翻译:语法分析+语义翻译
    • 可以逐层实现,但没必要,在一定的充分条件下最高效(时间&&空间)的方法是“一遍”实现

语法制导

  • 语法制导翻译定义SDD:CFG的推广
    • 语义属性+语义规则:每一个文法符号和语义属性相关联,每一个产生式和语义规则相关联
    • SDD不必显示地说明翻译发生的顺序
    • 综合属性:非终结符往上传,从后代和自己计算得到;终结符只有综合属性,由词法分析得到
    • 继承属性:从父亲,兄弟和自身得到
    • 非终结符可以有多个综合属性和继承属性
  • 标注分析树:语法分析树中的非终结符改写为对应的语义规则
  • 属性文法:没有副作用(语义规则中一些无关的代码)的SDD,即语义规则只有属性值的定义内容
  • 依赖图:SDD定义了分析树节点属性间的依赖关系
    • 依赖图在语法分析树上画,被依赖者指向依赖者,为了方便画边,综合属性节点放非终结符右侧,继承属性节点放非终结符左侧,一些计算中间结果可能被设置为虚属性节点
    • 可行的求值顺序是依赖图的拓扑排序
    • 依赖图没有循环依赖有两个常用充分条件:S-SDD,L-SDD,不仅如此,它们可以和语法分析过程一起实现
  • S属性定义S-SDD:仅具有综合属性
    • 可以根据任何自底向上的顺序计算
  • L属性定义L-SDD:依赖图的边只能从左到右
    • 要么是综合属性
    • 要么其继承属性只能依赖该非终结符(在生成式右端)左边的非终结符的属性,或生成式左端的继承属性,或自己的属性,而且其自己的属性不能在依赖图中成环
    • 每个S属性定义都是S属性定义
  • 语法制导翻译方案SDT:SDD的补充,具体的翻译实施方案
    • 语义属性+语义动作:产生式右部嵌入了一些语义动作(程序片段),嵌入的位置确定了该动作的执行时间
  • S-SDD转化为SDT
    • 可以在LR语法分析过程中实现
    • 把每个语义动作都放到产生式的最后
    • 具体实现:在LR基础上增加记录综合属性值的栈,归约时随字符集同样出栈并执行相应的动作,访问其它属性涉及到栈操作;若要实现多个属性,可以存放指针或把栈记录变大
  • L-SDD转化为SDT
    • 可以在LL或LR语法分析过程中实现,在规约时执行相应的语义动作
    • 继承属性放在该非终结符的前面,综合属性放生成式末尾
    • LL具体实现:拓展栈,在LL基础上允许栈中存放动作和属性。还需要保存数据项。
    • LR具体实现:引入标记非终结符替换语义动作,该非终结符只能推出$\epsilon$,结尾放对应的改写后的语义动作,这样所有的语义动作都放在生成式的末尾。细节上,这涉及到属性的栈寻址。

符号表

  • 程序变量:内存区域的别名
    • 声明:类型和名字
    • 定义:内存空间分配
  • 符号表:
    • 一种数据结构,存放每个符号名
    • 后续持续使用
    • 结构选择影响前端性能
    • 元素为字符串,类型,属性的元组
  • 静态作用域VS动态作用域

    • 效率高
    • 错误少
  • 作用域

    • 元素为符号表的栈,效率较低
  • 静态检查、动态检查
  • 静态类型、动态类型

LLVM VS GCC

  • LLVM没有开源污染性,更新更好,代码耦合性更好,可读性更好,大部分工具有API调用,每层输出基本都可以通过API查看
  • GCC支持性更好
  • 优化等级
    • -Os:二进制代码尽可能小
    • -O0:不优化,用于代码调试,减少编译时间并使调试可以产生预期的结果,默认优化等级
    • -O1:需要更多编译时间,大型函数需要更大的内存,编译器会尝试减小代码尺寸,减少执行时间,不执行任何需要大量编译时间的优化
    • -O2:几乎支持所有优化,不考虑空间时间的均衡
    • -O3:冒险地全局优化
    • 具体操作:向量化AVX(Intel),寄存器重命名,指令生成和调度,内联函数,平台特定编译器等等

中间代码生成

  • 后端的任务
    • 中间代码生成
    • 优化
    • 目标代码生成
  • IR:中间代码
    • 语法分析阶段的IR:AST
    • 编译优化阶段的IR:低阶IR,通常说的IR,连接前后端,和高级语言,机器解耦,便于平台移植和优化 e.g. LLVM中的IR Code,三地址码,静态单赋值
    • 寄存器分配阶段的IR:机器级IR
  • 三地址码:最多有三个操作数的操作
    • 操作数可以是变量,常量,临时中间变量
    • 实现方式:四元式,三元式,间接三元式
  • 静态单赋值SSA:赋值时创建变量的副本,方便进行优化
  • 类型表达式:array(len, type)…
  • 声明语句:属性width,type,offset
  • 赋值语句:属性addr,code(三地址码)
  • 增量翻译:只在已经生成的三地址码指令后面追加新的三地址指令,即不需要code这个属性,而是在genCode()函数内把新生成的代码添加到当前代码后面;否则需要不断进行连接和传递。
  • 数组引用语句:寻址
  • 控制流语句:属性true,false表示在True和False条件下的跳转标号,属性begin表示循环判断代码的跳转标号
  • 布尔表达式:属性true,false
  • 回填:不能确定跳转指令的目标标号时,把这类指令放入列表中。同一个列表中的跳转指令具有相同的目标标号,等到可以确定时再去填充。
  • 过程调用:…
  • 细节问题
    • 变量的内存存放:基地址+类型宽度
    • 内存对齐:方便cache存取
    • 字节序:大小端

运行时环境

  • 高级操作->底层有限的操作
  • 运行时环境
    • 硬件
    • OS
    • 运行时的库
  • 内存管理中的数据类型
    • 静态生命周期:全局变量,静态变量,代码
    • 作用域生命周期:局部变量,参数
    • 动态生命周期:内存申请释放,即栈和堆
  • 活动记录:管理一个过程调用的信息
  • 内存自动释放
    • 工具valgrind
    • 实现:
      • 计数:简单高效,不能处理循环计数问题
      • 追踪:可以处理循环计数问题,但相对低效

目标代码生成

  • 目标
    • 正确
    • 高质量
    • 快速
  • 任务
    • 指令选取
    • 寄存器分配
    • 指令排序
  • RISC&CISC
    • 见组成原理
  • fp:帧指针充当被调用函数和调用函数之间的锚,当调用一个函数时,该函数首先将 fp 的当前值保存在堆栈上。然后,它将 sp 寄存器的值保存在 fp 寄存器中。然后递减 sp 寄存器来为本地变量分配空间。fp 寄存器用于访问本地变量和参数,局部变量位于帧指针的负偏移量处,传递给函数的参数位于帧指针的正偏移量。当函数返回时, fp 寄存器被复制到 sp 寄存器中,这将释放用于局部变量的堆栈,函数调用者的 fp 寄存器的值由pop从堆栈中恢复。
  • MIPS:见文档
  • 面向对象
    • 静态和动态分发
    • 每个类一个虚(分发)表
    • 类面试题等

代码优化

  • 研究热点
    • 很多优化是NP难问题
  • 优化阶段
    • 源代码:算法层面
    • 中间代码:更高效的三地址码
    • 目标代码:机器相关的高效指令和寄存器分配
    • 汇编链接:机器码后的优化,通用性很强
    • e.g. inline,循环合并
  • 优化目标
    • 运行时间
    • 内存使用
    • 能耗
    • 可执行文件大小
    • 正确性是前提
  • 基本块:一串指令
    • 中间没有控制跳转分支语句
    • 标号可能在第一条
    • 分支跳转可能在最后一条
    • 整个序列第一条指令是首指令,跳转指令的目标指令是首指令,跳转指令后的一条指令是首指令;每条指令到下一条首指令之前或到整个序列结尾是一个基本块
  • 控制流图CFG
    • 有向图
    • 节点是基本快
    • 边是快的连接信息
  • 局部优化:基本块内的优化
    • 删除局部公共子表达式,把相同的表达式存起来避免重复计算,需要用到基本块的DAG
    • 使用代数恒等式推测公共子表达式
    • 赋值传播,尽量用新值参与运算,给删除死代码提供便利
    • 常量折叠,把常量在编译时直接展开,给删除死代码提供便利
    • 删除死代码,不计算没有被使用的结果(非活跃变量),不运行不可能被执行的分支
    • 强度削减,把较复杂的代码用更简单的代码实现,如$\div8\Leftrightarrow >>3$
    • 局部常量传播,只有常量计算得到的值也被展开
    • 代码移动:把循环中的循环不变计算(它对不同的循环层次而言是相对的)放到循环外面,即在循环前求值
  • 基本块的DAG表示
    • 寄存器的依赖关系图
    • 常量直接写
  • 全局优化:
    • 必须非常保守
    • 数据流分析
    • 全局常量传播GCP:…
  • 机器优化
    • 架构,如流水线,多核
    • 指令选取调度
    • 寄存器分配
    • 窥孔优化:孔比基本块还小,滑动窗口

现代编译技术

  • 计算机体系结构的发展趋势:领域专用架构

  • 编程语言发展趋势:领域专用语言,但这很痛苦;越来越抽象

  • 过去的成功经验:算力急速增长得益于软硬件间的协议,它的抽象充分利用了硬件的快速发展,e.g. 三段式编译器LLVM
  • 如今的环境:摩尔定律的失效,软硬件间的协议逐渐瓦解,出现了越来越多的专用领域架构,e.g.现在需要写GPU和CPU版本的程序
  • TVM:把深度学习的模型跑在任何机器后端的端到端解决方案
  • MLIR:多层面中间表示

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!