第六章 中间代码生成 赵建华 南京大学计算机系.

Presentation on theme: "第六章 中间代码生成 赵建华 南京大学计算机系."— Presentation transcript:

1 第六章 中间代码生成 赵建华 南京大学计算机系

2 本章内容 中间代码表示 静态类型检查 中间代码生成 抽象语法树 三地址代码：x=y op z 类型检查（type checking）
语法分析之后的抽象语法(syntax)检查，比如break的位置，goto的目标…. 中间代码生成

3 编译器前端的逻辑结构

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

5 三地址代码（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

6 三地址代码（3） 指令集合（2） 过程调用/返回： 带下标的复制指令：x=y[i] x[i]=y 地址/指针赋值指令：
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

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

8 三地址指令的四元式表示方法 在实现时，可以使用四元式/三元式/间接三元式来表示三地址指令 四元式：可以实现为纪录（或结构）
格式（字段）： op arg1 arg2 result op: 运算符的内部编码 arg1,arg2,result是地址 x=y+z y z x 单目运算符不使用arg2 param运算不使用arg2和result 条件转移/非条件转移将目标标号放在result字段

9 四元式的例子 赋值语句：a=b* -c + b* -c

10 三元式表示 三元式（triple） op arg1 arg2 使用三元式的位置来引用三元式的运算结果 x[i]=y需要拆分为两个三元式
x=y op z需要拆分为（这里？是编号） (?) op y z = x ? 问题：在优化时经常需要移动/删除/添加三元式，导致三元式的移动。

11 三元式的例子 a=b*-c + b * -c

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

13 静态单赋值（SSA） SSA中的所有赋值都是针对不同名的变量 对于同一个变量在不同路径中定值的情况，可以使用φ函数来合并不同的定值
if (flag) x=-1; else x = 1; y = x*a if (flag) x1=-1; else x2 = 1; x3=φ(x1,x2)； y = x3*a

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

15 类型表达式 类型表达式（type expression）：表示类型的结构 基本类型 类名 类型构造算子作用于类型
array[数字，类型表达式] record[字段/类型对的列表]（可以用符号表表示） 函数类型构造算子：参数类型结果类型 笛卡尔积：s X t 可以包含取值为类型表达式的变量

16 类型表达式的例子 类型例子 类型表达式 元素个数为3X4的二维数组 数组的元素的记录类型
该记录类型中包含两个字段: x和y,其类型分别是float和integer 类型表达式 array[3, array[4,record[(x,float),(y,float)]]

17 类型等价 不同的语言有不同的类型等价的定义 结构等价 名等价 或者它们是相同的基本类型 或者是相同的构造算子作用于结构等价的类型而得到的。
或者一个类型是另一个类型表达式的名字 名等价 类型名仅仅代表其自身

18 声明 文法 含义： D  T id ; D | ε T  B C | record ‘{’ D ‘}’ C  int | float
C  ε | [num] C 含义： D生成一系列声明； T生成不同的类型； B生成基本类型int/float； C表示分量，生成[num]序列； 注意record中包含了各个字段的声明。字段声明和变量声明的文法一致。

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

20 计算T的类型和宽度的SDT 综合属性：type, width 全局变量t和w用于将类型和宽度信息从B传递到C ε
相当于C的继承属性，因为总是通过拷贝来传递，所以在SDT中只赋值一次。也可以把t和w替换为C.t和C.w

21 SDT运行的例子 输入：int[2][3]

22 作用域和符号表 在具有语句块概念的编程语言中，标识符x在最内层的x声明的作用域中。 每个作用域对应于一个符号表；多个符号表形成树状结构。
在语义分析时，通过栈来存放当前符号表及其祖先。

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

24 声明序列的SDT（2） 我们可以把offset看作D的继承属性 D.offset表示D中第一个变量的相对地址
P{D.offset =0} D D T id; {D1.offset = D.offset + T.width;} D1

25 记录字段的处理 Trecord ‘{‘ D ‘}’ 为每个记录创建单独的符号表 首先创建一个新的符号表，压到栈顶；

26 表达式代码的SDD 将表达式翻译成三地址指令序列 表达式的SDD 属性code表示代码 addr表示存放表达式结果的地址（临时变量）
new Temp()可以生成一个临时变量 gen(…)生成一个指令

27 增量式翻译方案 主属性code满足增量式翻译的条件。 注意： top.get(…)从栈顶符号表开始，逐个向下寻找id的信息。
这里的gen发出相应的代码

28 数组元素的寻址 假设数组元素被存放在连续的存储空间中。 元素从0到n-1编号，第i个元素的地址为 base+i*w
K维数组的寻址：假设数组按行存放，即首先存放A[0][i2]…[ik]，然后存放A[1][i2]…[ik]，… A[i1][i2]…[ik]的地址 base+i1*w1+i2*w2+…+ik*wk 或者 base+((…((i1*n2+i2)*n3+i3)…)*nk+ik)*w 其中：base、w、i、n的值可以从符号表中找到。

29 新的文法产生式 数组元素L：LL[E] | id[E] 以数组元素为左部的赋值：SL=E; 数组元素作为表达式中的因子：EL
L的代码计算偏移量，将结果存放于L.addr所指的临时变量中 综合属性array记录了相应数组的信息：元素类型，基地址，…

30 数组元素作为因子 L的代码只计算了偏移量； 数组元素的存放地址应该根据偏移量进一步计算，即L的数组基址加上偏移量 使用三地址指令x=a[i]

31 数组元素作为赋值左部 使用三地址指令a[i]=x

32 例子 表达式：c+a[i][j]

33 类型检查和转换 类型系统： 可发现错误、提高代码效率、确定临时变量的大小、… 给每一个组成部分赋予一个类型表达式
通过一组逻辑规则来表示这些类型表达式必须满足的条件 可发现错误、提高代码效率、确定临时变量的大小、…

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

35 类型转换 假设在表达式x*i中，x为浮点数、i为整数，则结果应该是浮点数 类型转换比较简单时的SDD： 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;} } 这个规则没有考虑生成类型转换代码

36 类型的widening和narrowing
Java的类型转换规则 编译器自动完成的转换为隐式转换，程序员用代码指定的转换为显式转换。

37 处理类型转换的SDT 函数Max求的是两个参数在拓宽层次结构中的最小公共祖先 Widen函数已经生成了必要的类型转换代码

38 函数/运算符的重载 通过查看参数来解决函数重载问题 Ef(E1)
{ if f.typeset = {siti|1<= i<= k} and E1.type=sk then E.type = tk }

39 控制流的翻译 布尔表达式可以用于改变控制流/计算逻辑值。 文法 语义 短路代码
B  B‖B | B && B | !B | (B) | E rel E | true | false 语义 B1‖B2中B1为真时，不计算B2，整个表达式为真。因此，当B1为真时应该跳过B2的代码。 B1&&B2中B1为假时，不计算B2，整个表达式为假 短路代码 通过跳转指令实现控制流的处理 逻辑运算符本身不在代码中出现；

40 短路代码的例子 语句： 代码 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为真

41 控制流语句的翻译 文法：B表示布尔表达式，S代表语句 代码的布局见右图 继承属性 S if (B) S1
S if (B) S1 else S2 Swhile (B) S1 代码的布局见右图 继承属性 B.true：B为真的跳转目标 B.false：B为假的跳转目标 S.next：S执行完毕时的跳转目标

42 语法制导的定义（1）

43 语法制导的定义（2） 增量式生成代码： S while (
{begin = newlabel(); B.true = newlabel; B.false = S.next; gen(begin ‘:’)} B ) {gen(B.true ‘:’);S1.next=begin;}S1{gen(‘goto’ begin);}

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

45 布尔表达式的代码的SDD（1）

46 布尔表达式的代码的SDD（2）

47 布尔表达式代码的例子 if (x<100 || x > 200 && x!= y ) x = 0; 的代码

48 布尔值和跳转代码 程序中出现布尔表达式的目的可能就是求出它的值。比如x=a<b； 处理方法： 文法： 根据E的语法树结点所在的位置：
首先建立表达式的语法树，然后根据表达式的不同角色来处理。 文法： S  id = E; | if (E) S | while (E) S | S S E E‖E | E && E | E rel E | … 根据E的语法树结点所在的位置： Swhile ( E ) S1中的E，生成跳转代码 对于Sid = E，生成计算右值的代码

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

50 回填（2） 基本思想： 记录B的代码中跳转指令goto S.next，if … goto S.next的位置，但是不生成跳转目标。 这些位置被记录到B的综合属性B.falseList中； 当S.next的值已知时（即S的代码生成完毕时），把B.nextList中的所有指令的目标都填上这个值。 回填技术： 生成跳转指令时暂时不指定跳转目标标号，而是使用列表记录这些不完整的指令； 等知道正确的目标时再填写目标标号； 每个列表中的指令都指向同一个目标

51 布尔表达式的回填翻译（1） 布尔表达式用于语句的控制流时，它总是在取值true时和取值false时分别跳转到某个位置 引入两个综合属性
truelist: 包含跳转指令（位置）的列表，这些指令在取值true时执行 falselist：包含跳转指令（位置）的列表，这些指令在取值false时执行 辅助函数 Makelist(i) Merge(p1,p2) Backpatch(p,i)

52 布尔表达式的回填翻译（2）

53 回填和非回填方法的比较（1） true/false属性的赋值，在回填方案中对应为相应的list的赋值或者merge；
B  {B1.true=B.true, B1.false = newlabel();} B1 || {label(B1.false); B2.true = B.true; B2.false=B.false;} B2 true/false属性的赋值，在回填方案中对应为相应的list的赋值或者merge； 原来生成label的地方，在回填方案中使用M来记录相应的代码位置。M.inst的需要对英语相应label的标号； 原方案生成的指令goto B1.false，现在生成了goto M.inst

54 回填和非回填方法的比较（2） 回填时生成指令坯，然后加入相应的list 原来跳转到B.true的指令，现在被加入到B.truelist中。

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

56 控制转移语句的回填 S if ( B ) S | if (B) S else S | while (B) S | { L } | A
L  L S | S 语句的综合属性：nextlist nextlist中的跳转指令的目标应该是S执行完毕之后紧接着执行的下一条指令的位置。 考虑S是while语句、if语句的子语句时，分别应该跳转到哪里？

57 控制转移语句的回填（2） M的作用就是用M.instr记录下一个指令的位置
规则1中记录了then分支的代码起始位置； 规则2中，分别记录了then分支和else分支的起始位置； N的作用是生成goto指令坯，N.nextlist只包含这个指令的位置

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

59 Break、Continue的处理 虽然break、continue在语法上是一个独立的句子，但是它的代码和外围语句相关。
跟踪外围语句S， 生成一个跳转指令坯 将这个指令坯的位置加入到S的nextlist中。 跟踪的方法 在符号表中设置break条目，令其指向外围语句 在符号表中设置指向S的nextlist的指针，然后把这个指令坯的位置直接加入到nextlist中。