PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

恬祖
5 years ago
Views:

1 第六章中间代码生成许畅南京大学计算机系 2018 年春季

2 本章内容中间代码表示表达式的有向无环图 DAG 三地址代码 :x = y op z 类型检查类型类型检查表达式的翻译中间代码生成控制流回填 2

3 编译器前端的逻辑结构前端是对源语言进行分析并产生中间表示处理与源语言相关的细节, 与目标机器无关前端后端分开的好处 : 不同的源语言不同的机器可以得到不同的编译器组合 3

4 中间代码表示及其好处形式多种中间表示, 不同层次抽象语法树三地址代码重定位为新的机器建编译器, 只需要做从中间代码到新的目标代码的翻译器 ( 前端独立 ) 高层次的优化优化与源语言和目标机器都无关 4

5 中间代码的实现静态类型检查和中间代码生成的过程都可以用语法制导的翻译来描述和实现对于抽象语法树这种中间表示的生成, 第五章已经介绍过 5

6 生成抽象语法树的语法制导定义 a + a * (b c) + (b c) * d 的抽象语法树 6

7 表达式的有向无环图语法树中, 公共子表达式每出现一次, 就有一颗对应的子树表达式的有向无环图 (Directed Acyclic Graph, DAG) 能够指出表达式中的公共子表达式, 更简洁地表示表达式 7

8 DAG 构造可以用和构造抽象语法树一样的 SDD 来构造不同的处理在函数 Leaf 和 Node 每次被调用时, 构造新节点前先检查是否已存在同样的节点, 如果已经存在, 则返回这个已有的节点构造过程示例 8

9 三地址代码 (1) 每条指令右侧最多有一个运算符一般情况可以写成 x = y op z 允许的运算分量名字 : 源程序中的名字作为三地址代码的地址常量 : 源程序中出现或生成的常量编译器生成的临时变量 9

10 三地址代码 (2) 指令集合 (1) 运算 / 赋值指令 : x = y op z x = op y 复制指令 : x = y 无条件转移指令 : goto L 条件转移指令 : if x goto L if False x goto L 条件转移指令 : if x relop y goto L 10

11 三地址代码 (3) 指令集合 (2) 过程调用 / 返回 param x 1 // 设置参数 param x 2 param x n call p, n // 调用子过程 p,n 为参数个数带下标的复制指令 :x = y[i] x[i] = y 注意 :i 表示离开数组位置第 i 个字节, 而不是数组的第 i 个元素地址 / 指针赋值指令 x = &y x = *y *x = y 11

12 例子语句 do i = i + 1; while (a[i] < v); 12

13 三地址指令的四元式表示方法在实现时, 可使用四元式 / 三元式 / 间接三元式 / 静态单赋值来表示三地址指令四元式 : 可以实现为记录 ( 或结构 ) 格式 ( 字段 ) : op arg 1 arg 2 result op: 运算符的内部编码 arg 1, arg 2, result 是地址 x = y + z + y z x 单目运算符不使用 arg 2 param 运算不使用 arg 2 和 result 条件转移 / 非条件转移将目标标号放在 result 字段 13

14 四元式的例子赋值语句 :a = b * c + b * c 14

15 三元式表示三元式 (Triple) : op arg 1 arg 2 使用三元式的位置来引用三元式的运算结果 x = y op z 需要拆分为 (? 是编号 )? op y z = x (?) x[i] = y 需要拆分为两个三元式求 x[i] 的地址, 然后再赋值优化时经常需要移动 / 删除 / 添加三元式, 导致三元式的移动 15

16 三元式的例子 16

17 间接三元式包含了一个指向三元式的指针的列表可以对这个列表进行操作, 完成优化功能, 操作时不需要修改三元式中的参数 17

18 静态单赋值 (SSA) Static Single Assignment (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; 18

19 类型和声明类型检查 (Type checking) 利用一组规则来检查运算分量的类型和运算符的预期类型是否匹配类型信息的用途查错确定名字需要的内存空间计算数组元素的地址类型转换选择正确的运算符本节的内容确定名字的类型变量的存储空间布局 ( 相对地址 ) 19

20 类型表达式类型表达式 (Type expression): 表示类型的结构可能是基本类型也可能通过类型构造算子作用于类型表达式而得到如 int [2][3], 表示由两层数组组成的数组 array(2, array(3, integer)) array 是类型构造算子, 有两个参数 : 数字和类型 20

21 类型表达式的定义基本类型 ( 或类型名 ) 是类型表达式如 :boolean, char, integer, float, void, 类型构造算子 array 作用于数字和类型表达式得到类型表达式,record 作用于字段名和相应的类型得到类型表达式类型构造算子可得到函数类型的类型表达式如果 s, t 是类型表达式, 其笛卡尔积 s t 也是类型表达式如 :struct { int a[10]; float f; } st; 对应于 :record((a array(0..9, int)) (f real)) 21

22 类型等价不同的语言有不同的类型等价的定义结构等价它们是相同的基本类型, 或由相同的构造算子作用于结构等价的类型而得到, 或一个类型是另一个类型表达式的名字名等价类型名仅代表自身 ( 仅有前两个条件 ) 22

23 类型的声明处理基本类型数组类型或记录类型的文法 D T id; D ε T B C record '{' D '}' B int float C ε [num] C 应用该文法及其对应的语法制导定义, 除了得到类型表达式之外, 还得进行各种类型的存储布局 23

24 局部变量的存储布局变量的类型可以确定变量需要的内存即类型的宽度 ( 该类型一个对象所需的存储单元的数量 ) 可变大小的数据结构只需要考虑指针函数的局部变量总是分配在连续的区间因此给每个变量分配一个相对于这个区间开始处的相对地址变量的类型信息保存在符号表中 24

25 计算 T 的类型和宽度的 SDT 综合属性 :type, width 全局变量 t 和 w 用于将类型和宽度信息从 B 传递到 C ε 相当于 C 的继承属性 ( 也可以把 t 和 w 替换为 C.t 和 C.w) { { ; } 25

26 SDT 运行的例子输入 :int [2][3] 26

27 声明序列的 SDT (1) 在处理一个过程 / 函数时, 局部变量应该放到单独的符号表中去这些变量的内存布局独立相对地址从 0 开始, 变量的放置和声明的顺序相同 SDT 的处理方法变量 offset 记录当前可用的相对地址每分配一个变量,offset 增加相应的值 ( 加宽度 ) top.put(id.lexeme, T.type, offset) 在符号表中创建条目, 记录标识符的类型和偏移量 27

28 声明序列的 SDT (2) 可以把 offset 看作 D 的继承属性 D.offset 表示 D 中第一个变量的相对地址 P { D.offset = 0; } D D T id; { D 1.offset = D.offset + T.width; } D 1 28

29 记录和类中的字段 (1) 记录变量声明的翻译方案约定一个记录中各个字段的名字必须互不相同字段名的偏移量 ( 相对地址 ), 是相对于该记录的数据区字段而言的记录类型使用一个专用的符号表, 对其各个字段的类型和相对地址进行单独编码记录类型 record(t):record 是类型构造算子,t 是符号表对象, 保存该记录类型各个字段的信息 29

30 记录和类中的字段 (2) 注 : 记录类型存储方式可以推广到类 30

31 表达式代码的 SDD 将表达式翻译成三地址代码的 SDD code 表示代码 addr 表示存放表达式结果的地址 new Temp() 生成临时变量 gen() 生成指令 a = b + c 31

32 增量式翻译方案类似于上一章中所述的边扫描边生成 gen 不仅构造新的三地址指令, 还要将它添加到至今为止已生成的指令序列之后不需要 code 指令保存已有的代码, 而是对 gen 的连续调用生成一个指令序列 32

33 数组元素的寻址假设数组元素被存放在连续的存储空间中, 元素从 0 到 n 1 编号, 第 i 个元素的地址为 base + i * w k 维数组的寻址 : 假设数组按行存放, 首先存放 A[0][i 2 ] [i k ], 然后存放 A[1][i 2 ] [i k ],, 那么 A[i 1 ][i 2 ] [i k ] 的地址为 base + i 1 * w 1 + i 2 * w i k * w k, 或者 base + (( ((i 1 * n 2 + i 2 ) * n 3 + i 3 ) ) * n k + i k ) * w 其中 base, w, n 的值可以从符号表中找到 33

34 数组引用的翻译为数组引用生成代码要解决的主要问题数组引用的文法和地址计算相关联假定数组编号从 0 开始, 基于宽度来计算相对地址数组引用相关文法非终结符号 L 生成数组名, 加上一个下标表达式序列 34

35 数组引用生成代码的翻译方案 (1) 非终结符号 L 的三个综合属性 L.array 是一个指向数组名字对应的符号表条目的指针 (L.array.base 为该数组的基地址 ) L.addr 指示一个临时变量, 计算数组引用的偏移量 L.type 是 L 生成的子数组的类型对于任何 ( 子 ) 数组类型 L.type, 其宽度由 L.type.width 给出, L.type.elem 给出其数组元素的类型 35

36 数组引用生成代码的翻译方案 (2) 核心是确定数组引用的地址 36

37 数组引用生成代码的翻译方案 (3) L 的代码只计算了偏移量数组元素的存放地址应该根据偏移量进一步计算, 即 L 的数组基址加上偏移量使用三地址指令 x = a[i] 37

38 数组引用生成代码的翻译方案 (4) 使用三地址指令 a[i] = x 38

39 例子表达式 :c + a[i][j] 39

40 类型检查和转换类型系统给每一个组成部分赋予一个类型表达式通过一组逻辑规则来表达类型表达式必须满足的条件可发现错误提高代码效率确定临时变量的大小类型检查可以分为动态和静态两种强类型的 : 如果编译器中的类型系统能够保证它接受的程序在运行时刻不会发生类型错误, 则该语言的这种实现称为强类型的 40

41 类型系统的分类类型综合根据子表达式的类型构造出表达式的类型 if f 的类型为 s t 且 x 的类型为 s then f(x) 的类型为 t 类型推导根据语言结构的使用方式来确定该结构的类型 if f(x) 是一个表达式 then 对于某些类型 α 和 β,f 的类型为 α β 且 x 的类型为 α 41

42 函数 / 运算符的重载通过查看参数来解决函数重载问题 E f(e 1 ) { if f.typeset = { s i t i 1 <= i <= n } and E 1.type = s k } then E.type = t k 42

43 类型转换假设在表达式 x * i 中,x 为浮点数,i 为整数, 则结果应该是浮点数 x 和 i 使用不同的二进制表示方式浮点 * 和整数 * 使用不同的指令 t 1 = (float) i t 2 = x fmul t 1 类型转换比较简单时的 SDT E E 1 + E 2 { if (E 1.type = integer and E 2.type = integer) E.type = integer; } else if (E 1.type = float and E 2.type = integer) E.type = float; 43

44 类型拓宽 widening 和窄化 narrowing Java 的类型转换规则编译器自动完成的转换为隐式转换, 程序员用代码指定的转换为显式转换 44

45 处理类型转换的 SDT 函数 max 求两个参数在拓宽层次结构中的最小公共祖先函数 widen 生成必要的类型转换代码 45

46 控制流的翻译布尔表达式可以用于改变控制流 / 计算逻辑值文法 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, 整个表达式为假短路代码通过跳转指令实现控制流, 逻辑运算符本身不出现 46

47 短路代码的例子语句 if (x < 100 x > 200 && x!= y) x = 0; 代码 if x < 100 goto L 2 if False x > 200 goto L 1 if False x!= y goto L 1 L 2 : x = 0 L 1 : 接下来的代码 47

48 控制流语句的翻译控制流语句 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 执行完毕时的跳转目标 48

49 语法制导的定义 (1) 49

50 语法制导的定义 (2) 增量式生成代码 S while ( { begin = newlabel(); B.true = newlabel(); B.false = S.next; gen(begin ':'); } B ) { S 1.next = begin; gen(b.true ':'); } S 1 { gen('goto' begin); } 50

51 布尔表达式的控制流翻译生成的代码执行时跳转到两个标号之一表达式的值为真时, 跳转到 B.true 表达式的值为假时, 跳转到 B.false B.true 和 B.false 是两个继承属性, 根据 B 所在的上下文指向不同的位置如果 B 是 if 语句的条件表达式, 分别指向 then 分支和 else 分支, 如果没有 else 分支, 则 B.false 指向 if 语句的下一条指令如果 B 是 while 语句的条件表达式, 分别指向循环体的开头和循环出口处 51

52 布尔表达式的代码的 SDD (1) // 短路 // 短路 52

53 布尔表达式的代码的 SDD (2) 53

54 布尔表达式代码的例子 if (x < 100 x > 200 && x!= y ) x = 0; 的代码生成的中间代码优化过的中间代码 54

55 布尔值和跳转代码程序中出现布尔表达式也可能是求值 :x = a < b 处理方法建立表达式的语法树, 根据表达式的不同角色来处理文法 S id = E; if (E) S while (E) S S S E E E E && E! E E rel E 根据 E 的语法树结点所在的位置 S while ( E ) S 1 中的 E, 生成跳转代码对于 S id = E, 生成计算右值的代码 55

56 回填 (1) 为布尔表达式和控制流语句生成目标代码关键问题 : 某些跳转指令应该跳转到哪里? 例如 :if (B) S 按照短路代码的翻译方法,B 的代码中有一些跳转指令在 B 为假时执行这些跳转指令的目标应该跳过 S 对应的代码, 但生成这些指令时,S 的代码尚未生成, 因此目标不确定通过语句的继承属性 next 来传递, 需要第二趟处理如何一趟处理完毕呢? 56

57 回填 (2) 基本思想记录 B 中跳转指令如 goto S.next 的标号, 但不生成跳转目标, 这些标号被记录到 B 的综合属性 B.falselist 中当 S.next 的值成为已知时 ( 即 S 的代码生成完毕时 ), 把 B.falselist 中的所有指令的目标都填上这个值回填技术生成跳转指令时不指定跳转目标, 而是使用列表记录这些不完整指令的标号当知道正确的跳转目标时再填写目标列表中的每个指令都指向同一个目标 57

58 布尔表达式的回填翻译 (1) 布尔表达式在取值 true/false 时分别跳转到某目标综合属性 truelist: 包含跳转指令标号的列表, 这些指令在取值 true 时执行 falselist: 包含跳转指令标号的列表, 这些指令在取值 false 时执行辅助函数 makelist(i): 创建一个包含跳转指令标号 i 的列表 merge(p 1, p 2 ): 将 p 1 和 p 2 指向的标号列表合并然后返回 backpatch(p, i): 将 i 作为跳转目标插入 p 的所有指令中 58

59 布尔表达式的回填翻译 (2) 文法中引入非终结符号 M 在适当的时候获取将要生成指令的标号 59

60 回填和非回填方法的比较 (1) 比较生成指令坯, 然后加入相应的 list 原来跳转到 B.true 的指令, 现在加入到 B.truelist 中原来跳转到 B.false 的指令, 现在加入到 B.falselist 中 60

61 回填和非回填方法的比较 (2) true/false 属性的赋值, 在回填方案中对应为相应的 truelist/falselist 的赋值或者 merge 61

62 布尔表达式的回填例子 x < 100 x > 200 && x!= y _ 62

63 控制转移语句的回填 (1) 语句 S if ( B ) S if ( B ) S else S while ( B ) S { L } A L L S S 综合属性 nextlist nextlist 中跳转指令的目标是 S 执行完毕后紧接着执行的下一条指令的标号考虑 S 是 if 语句 while 语句的子语句时, 分别应该跳转到哪里? 63

64 控制转移语句的回填 (2) M: 用 M.instr 记录下一条指令的标号 N: 生成 goto 指令坯,N.nextlist 包含该指令标号 64

65 控制转移语句的回填 (3) 65

66 Break Continue 的处理虽然 break continue 在语法上是一个独立的句子, 但是它的代码和外围语句相关方法 :(break 语句 ) 跟踪外围循环语句 S 生成一个跳转指令坯将这个指令坯的位置加入到 S 的 nextlist 中 66

Microsoft PowerPoint - 6 Intermediate-Code Generation.pptx

Microsoft PowerPoint - 6 Intermediate-Code Generation.pptx 第六章中间代码生成陈林本章内容中间代码表示抽象语法树三地址代码中间代码生成表达式类型检查控制流编译器前端的逻辑结构静态类型检查和中间代码生成的过程都可以用语法制导的翻译来描述和实现对于抽象语法树这种中间表示的生成, 第五章已经介绍过表达式的有向无环图语法树中, 公共子表达式每出现一次, 就有一个对应的子树表达式的有向无环图 (Directed Acyclic Graph,DAG)