第六章中间代码生成 陈林
本章内容 中间代码表示 抽象语法树 三地址代码 中间代码生成 表达式 类型检查 控制流
编译器前端的逻辑结构 静态类型检查和中间代码生成的过程都可以用语法制导的翻译来描述和实现 对于抽象语法树这种中间表示的生成, 第五章已经介绍过
表达式的有向无环图 语法树中, 公共子表达式每出现一次, 就有一个对应的子树 表达式的有向无环图 (Directed Acyclic Graph,DAG) 能够指出表达式中的公共子表达式, 更简洁地表示表达式
DAG 构造 可以用和构造抽象语法树一样的 SDD 来构造
DAG 构造 不同的处理 在函数 Leaf 和 Node 每次被调用时, 构造新节点前先检查是否已存在同样的节点, 如果已经存在, 则返回这个已有的节点 构造过程示例
三地址代码 (1) 每条指令右侧最多有一个运算符 一般情况可以写成 x = y op z 允许的运算分量 名字 : 源程序中的名字作为三地址代码的地址 常量 : 源程序中出现或生成的常量 编译器生成的临时变量
三地址代码 (2) 指令集合 (1) 运算 / 赋值指令 :x=y op z 复制指令 :x=y 无条件转移指令 :goto L x = op y 条件转移指令 :if x goto L if False x goto L 条件转移指令 :if x relop y goto L
三地址代码 (3) 指令集合 (2) 过程调用 / 返回 param x1 param x2 param xn call p, n // 设置参数 // 调用子过程 p,n 为参数个数 带下标的复制指令 :x=y[i] x[i]=y 注意 :i 表示离开数组位置第 i 个字节, 而不是数组的第 i 个元素 地址 / 指针赋值指令 : x=&y x=*y *x=y
三地址代码实例 语句 do i = i + 1; while (a[i]<v);
三地址指令的四元式表示方法 在实现时, 可以使用四元式 / 三元式 / 间接三元式来表示三地址指令 四元式 : 可以实现为纪录 ( 或结构 ) 格式 ( 字段 ): op arg1 arg2 result op: 运算符的内部编码 arg1,arg2,result 是地址 x=y+z + y z x 单目运算符不使用 arg2 param 运算不使用 arg2 和 result 条件转移 / 非条件转移将目标标号放在 result 字段
四元式的例子 赋值语句 :a=b* -c + b* -c
三元式表示 三元式 (triple) op arg1 arg2 使用三元式的位置来引用三元式的运算结果 x[i]=y 需要拆分为两个三元式 求 x[i] 的地址, 然后再赋值 x=y op z 需要拆分为 ( 这里? 是编号 ) (?) op y z = x? 问题 : 在优化时经常需要移动 / 删除 / 添加三元式, 导致三元式的移动
三元式的例子 a=b*-c + b * -c
间接三元式 包含了一个指向三元式的指针的列表 我们可以对这个列表进行操作, 完成优化功能 ; 操作时不需要修改三元式中的参数
静态单赋值 (SSA) SSA 中的所有赋值都是针对不同名的变量 对于同一个变量在不同路径中定值的情况, 可以使用 φ 函数来合并不同的定值 if (flag) x=-1; else x = 1; y = x*a if (flag) x 1 =-1; else x 2 = 1; x 3 =φ(x 1,x 2 ); y = x 3 *a
类型和声明 类型检查 (Type Checking) 利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配 类型信息的用途 查错 确定名字需要的内存空间 计算数组元素的地址 类型转换 选择正确的运算符 主要内容 确定名字的类型 变量的存储空间布局 ( 相对地址 )
类型表达式 类型表达式 (type expression): 表示类型的结构 基本类型 类名 类型构造算子作用于类型 array[ 数字, 类型表达式 ] record[ 字段 / 类型对的列表 ]( 可以用符号表表示 ) 函数类型构造算子 : 参数类型 结果类型 笛卡尔积 :s X t 可以包含取值为类型表达式的变量
类型表达式的例子 类型例子 元素个数为 3X4 的二维数组 数组的元素的记录类型 该记录类型中包含两个字段 : x 和 y, 其类型分别是 float 和 integer 类型表达式 array[3, array[4, record[(x,float),(y,integer)] ] ]
类型等价 不同的语言有不同的类型等价的定义 结构等价 或者它们是相同的基本类型 或者是相同的构造算子作用于结构等价的类型而得到的 或者一个类型是另一个类型表达式的名字 名等价 类型名仅仅代表其自身
声明 文法 含义 D 生成一个声明列表 T 生成不同的类型 B 生成基本类型 int/float C 表示分量, 生成 [num] 序列 注意 record 中包含了各个字段的声明, 字段声明和变量声明的文法一致
局部变量名的存储布局 变量的类型可以确定变量需要的内存 即类型的宽度 可变大小的数据结构只需要考虑指针 函数的局部变量总是分配在连续的区间 因此给每个变量分配一个相对于这个区间开始处的相对地址 变量的类型信息保存在符号表中
计算类型和宽度的 SDT
很重要 计算类型和宽度的 SDT 综合属性 :type, width 全局变量 t 和 w 用于将类型和宽度信息从 B 传递到 C ε 相当于 C 的继承属性, 因为总是通过拷贝来传递, 所以在 SDT 中只赋值一次, 也可以把 t 和 w 替换为 C.t 和 C.w
T B {C.t=B.type; C.w=B.width;} C {T.type=C.type;T.width=C.width} B int {B.type=integer;B.width=4} B float {B.type=float;B.width=8} C ε {C.type=C.t; C.width=C.w} C [ num]c1 { C1.t=C.t;C1.w=C.w; C.type=array(num.value,C1.type); C.width=num.value*C1.width } T B {C.t=B.type; C.w=B.width;} C {T.type=C.type;T.width=C.width} B int {B.type=integer;B.width=4} B float {B.type=float;B.width=8} C ε {C.type=C.t; C.width=C.w} C [ num]c1 { C1.t=array(num.value,C.t); C1.w=num.value*C.w; C.type=C1.type;C.width=C1.width} int[2][3]
SDT 运行的例子 输入 :int[2][3]
声明序列的 SDT 除了确定类型和类型宽度, 还有什么语义需要处理? 符号表中的位置
声明序列的 SDT(1) 在处理一个过程 / 函数时, 局部变量应该放到单独的符号表中去 这些变量的内存布局独立 相对地址从 0 开始 假设变量的放置和声明的顺序相同 SDT 的处理方法 变量 offset 记录当前可用的相对地址 每 分配 一个变量,offset 的值增加相应的值 top.put(id.lexeme, T.type, offset) 在当前符号表 ( 位于栈顶 ) 中创建符号表条目, 记录标识符的类型, 偏移量
声明序列的 SDT(2) 我们可以把 offset 看作 D 的继承属性 D.offset 表示 D 中第一个变量的相对地址 P {D.offset =0} D D T id; {D 1.offset = D.offset + T.width;} D 1
记录字段的处理 T record { D } 为每个记录创建单独的符号表 首先创建一个新的符号表, 压到栈顶 然后处理对应于字段声明的 D, 字段都被加入到新符号表中 最后根据栈顶的符号表构造出 record 类型表达式 ; 符号表出栈
表达式代码的 SDD 将表达式翻译成三地址指令序列 表达式的 SDD 属性 code 表示代码 addr 表示存放表达式结果的地址 ( 临时变量 ) new Temp() 可以生成一个临时变量 gen( ) 生成一个指令
表达式代码的 SDD
增量式翻译方案 主属性 code 满足增量式翻译的条件 注意 top.get( ) 从栈顶符号表开始, 逐个向下寻找 id 的信息 这里的 gen 发出相应的代码
重要 数组元素的寻址 数组元素存储在一块连续的存储空间中, 以方便快速的访问它们 n 个数组元素是 0,1,,n-1 进行顺序编号的 假设每个数组元素宽度是 w, 那么数组 A 的第 i 个元素的开始地址为 base+i*w, base 是 A[0] 的相对地址 推广到二维或多维数组 A[i 1 ][i 2 ] 表示第 i 1 行第 i 2 个元素 假设一行的宽度是 w 1, 同一行中每个元素的宽度是 w 2, A[i 1 ][i 2 ] 的相对地址是 base+i 1 *w 1 +i 2 *w 2 对于 k 维数组 A[i 1 ][i 2 ] [i k ], 推广 base+i 1 *w 1 +i 2 *w2+ +i k *w k
数组元素的寻址 ( 续 ) 根据第 j 维上的数组元素的个数 n j 和该数组每个元素的宽度 w 进行计算的, 如二维数组 A[i 1 ][i 2 ] 的地址 base+(i 1 *n 2 +i 2 )*w 于 k 维数组 A[i 1 ][i 2 ] [i k ] 的地址 base+(( (i 1 *n 2 +i 2 ) *n 3 +i 3 ) )*n k +i k )*w 有时下标不一定从 0 开始, 比如一维数组编号 low,low+1,,high, 此时 base 是 A[low] 的相对地址 计算 A[i] 的地址变成 base+(i-low)*w 预先计算技术 改写成 i*w+c 的形式, 其中 c=base-low*w 可以在编译时刻预先计算出来, 计算 A[i] 的相对地址只要计算 i*w 再加上 c 就可以了
数组元素的寻址 ( 续 ) 上述地址的计算是按行存放的 按行存放策略和按列存放策略可以推广到多维数组中
数组引用的翻译 为数组引用生成代码要解决的主要问题 数组引用的文法和地址计算相关联 假定数组编号从 0 开始, 基于宽度来计算相对地址 数组引用相关文法 非终结符号 L 生成一个数组名字加上一个下标表达式序列
数组引用生成代码的翻译方案 非终结符号 L 的三个综合属性 L.addr 指示一个临时变量, 计算数组引用的偏移量 L.array 是一个指向数组名字对应的符号表条目的指针,L.array.base 为该数组的基地址 L.type 是 L 生成的子数组的类型, 对于任何数组类型 t, 其宽度由 t.width 给出,t.elem 给出其数组元素的类型
数组引用生成代码的翻译方案 核心是确定数组引用的地址
数组引用翻译示例 基于数组引用的翻译方案, 表达式 c+a[i][j] 的注释语法树及三地址代码序列 假设 a 是一个 2*3 的整数数组,c i j 都是整数 那么 a 的类型是 array(2, array(3,integer)), a 的宽度是 24 a[i] 的类型是 array(3,integer), 宽度是 12 a[i][j] 的类型是整型
类型检查和转换 类型系统 给每一个组成部分赋予一个类型表达式 通过一组逻辑规则来表示这些类型表达式必须满足的条件 可发现错误 提高代码效率 确定临时变量的大小
类型系统的分类 类型综合 根据子表达式的类型构造出表达式的类型 if f 的类型为 s t 且 x 的类型为 s then f(x) 的类型为 t 类型推导 根据语言结构的使用方式来确定该结构的类型 : if f(x) 是一个表达式 then 对于某些类型 α,β;f 的类型为 α β 且 x 的类型为 α
类型转换 假设在表达式 x*i 中,x 为浮点数 i 为整数, 则结果应该是浮点数 x 和 i 使用不同的二进制表示方式 浮点 * 和整数 * 使用不同的指令 t1 = (float) i t2 = x fmul t1 类型转换比较简单时的 SDD E E1 + E2 { if(e1.type = integer and E2.type = integer) E.type = integer; else if (E1.type = float and E2.type= integer) E.type = float; } 这个规则没有考虑生成类型转换代码
类型的 widening 和 narrowing 编译器自动完成的转换为隐式转换, 程序员用代码指定的转换为显式转换
处理类型转换的 SDT 函数 Max 求的是两个参数在拓宽层次结构中的最小公共祖先 Widen 函数已经生成了必要的类型转换代码
函数 / 运算符的重载 通过查看参数来解决函数重载问题 E f(e 1 ) { if f.typeset = {s i t i 1<= i<= k} and E 1.type=s k then E.type = t k }
控制流的翻译 布尔表达式可以用于改变控制流 / 计算逻辑值 文法 B B B B && B!B (B) E rel E true false 语义 B 1 B 2 中 B 1 为真时, 不计算 B 2, 整个表达式为真, 因此, 当 B 1 为真时可以跳过 B 2 的代码 B 1 &&B 2 中 B 1 为假时, 可以不计算 B 2, 整个表达式为假 短路代码 通过跳转指令实现控制流的处理 逻辑运算符本身不在代码中出现
短路代码的例子 语句 if (x<100 x>200 && x!= y) x = 0; 代码 if x < 100 goto L2 iffalse x > 200 goto L1 iffalse x!= y goto L1 L2: x=0 L1: 接下来的代码 注 : 当 x<100 为真时, 直接执行 x=0; 所以执行 x>200 时,x<100 必然为假同理 : 计算 x!=y 时,x<100 为假, 而 x>200 为真
控制流语句的翻译 文法 :B 表示布尔表达式, S 代表语句 S if (B) S 1 S if (B) S 1 else S 2 S while (B) S 1 代码的布局见右图 继承属性 B.true:B 为真的跳转目标 B.false:B 为假的跳转目标 S.next:S 执行完毕时的跳转目标
语法制导的定义 (1)
语法制导的定义 (2)
布尔表达式的控制流翻译 生成的代码执行时跳转到两个标号之一 表达式的值为真时, 跳转到 B.true 表达式的值为假时, 跳转到 B.false B.true 和 B.false 是两个继承属性, 根据 B 所在的上下文指向不同的位置 如果 B 是 if 语句的条件表达式, 分别指向 then 分支和 else 分支 ; 如果没有 else 分支, 则指向 if 语句的下一条指令 如果 B 是 while 语句的条件表达式, 分别指向循环体的开头和循环出口处
布尔表达式代码的 SDD(1) 很重要
布尔表达式代码的 SDD(2)
布尔表达式代码的例子 if (x<100 x > 200 && x!= y ) x = 0
布尔值和跳转代码 程序中出现布尔表达式的目的可能就是求出它的值, 比如 x=a<b 处理方法 首先建立表达式的语法树, 然后根据表达式的不同角色来处理 文法 S id = E; if (E) S while (E) S S S E E E E && E E rel E 根据 E 的语法树结点所在的位置 S while ( E ) S 1 中的 E, 生成跳转代码 对于 S id = E, 生成计算右值的代码
do { if (x>0) x++; } while (x<5);
很重要 回填 (1) 为布尔表达式和控制流语句生成目标代码的关键问题 : 某些跳转指令应该跳转到哪里 例如 :if (B) S 按照短路代码的翻译方法,B 的代码中有一些跳转指令在 B 为假时执行, 这些跳转指令的目标应该跳过 S 对应的代码, 生成这些指令时,S 的代码尚未生成, 因此目标不确定 通过语句的继承属性 next 来传递 需要第二趟处理 如何一趟处理完毕呢?
回填 (2) 基本思想 记录 B 的代码中跳转指令 goto S.next,if goto S.next 的位置, 但是不生成跳转目标 这些位置被记录到 B 的综合属性 B.falseList 中 当 S.next 的值已知时 ( 即 S 的代码生成完毕时 ), 把 B.nextList 中的所有指令的目标都填上这个值 回填技术 生成跳转指令时暂时不指定跳转目标标号, 而是使用列表记录这些不完整的指令 等知道正确的目标时再填写目标标号 每个列表中的指令都指向同一个目标
布尔表达式的回填翻译 (1) 布尔表达式用于语句的控制流时, 它总是在取值 true 时和取值 false 时分别跳转到某个位置 引入两个综合属性 truelist: 包含跳转指令 ( 位置 ) 的列表, 这些指令在取值 true 时执行 falselist: 包含跳转指令 ( 位置 ) 的列表, 这些指令在取值 false 时执行 辅助函数 Makelist(i): 创建一个只包含 i 的列表 Merge(p1,p2): 将 p1 和 p2 指向的列表合并 Backpatch(p,i): 将 i 作为目标标号插入到 p 所指列表中的各指令中
布尔表达式的回填翻译 (2)
回填和非回填方法的比较 (1) true/false 属性的赋值, 在回填方案中对应为相应的 list 的赋值或者 merge 原来生成 label 的地方, 在回填方案中使用 M 来记录相应的代码位置,M.inst 需要对应 label 的标号 原方案生成的指令 goto B 1.false, 现在生成了 goto M.inst
回填和非回填方法的比较 (2) 回填时生成指令坯, 然后加入相应的 list 原来跳转到 B.true 的指令, 现在被加入到 B.truelist 中
布尔表达式的回填例子 x<100 x>200 && x!=y
控制转移语句的回填 S if ( B ) S if (B) S else S while (B) S { L } A L L S S 语句的综合属性 :nextlist nextlist 中的跳转指令的目标应该是 S 执行完毕之后紧接着执行的下一条指令的位置 考虑 S 是 while 语句 if 语句的子语句时, 分别应该跳转到哪里
控制转移语句的回填 M 的作用就是用 M.instr 记录下一个指令的位置 规则 1 中记录了 then 分支的代码起始位置 ; 规则 2 中, 分别记录了 then 分支和 else 分支的起始位置 ; N 的作用是生成 goto 指令坯,N.nextlist 只包含这个指令的位置
控制转移语句的回填
产生式 S -> repeat S 1 while B SDD begin = newlabel() S 1.next = newlabel() B.true = begin B.false = S.next S.code = label(begin) S 1.code label(s 1.next) B.code
Break Continue 的处理 虽然 break continue 在语法上是一个独立的句子, 但是它的代码和外围语句相关 方法 :(break 语句 ) 跟踪外围语句 S, 生成一个跳转指令坯 将这个指令坯的位置加入到 S 的 nextlist 中 跟踪的方法 在符号表中设置 break 条目, 令其指向外围语句 在符号表中设置指向 S 的 nextlist 的指针, 然后把这个指令坯的位置直接加入到 nextlist 中