编译原理第9篇

编译原理
chapter9
运行时存储空间组织
Chapter9 运行时存储空间组织
编译原理
chapter9
运行时存储空间组织
9.1 目标程序运行时的活动 9.2 运行时存储器的划分 9.3 简单的栈式存储分配 9.4 嵌套过程语言的栈式实现 9.5 堆式动态存储分配
编译原理
chapter9
运行时存储空间组织
编译原理
chapter9
运行时存储空间组织
1. 带有静态链的活动记录 带有静态链 静态链的活动记录 静态链：它指向直接外层过程的活动记录的起始位置， 静态链：它指向直接外层过程的活动记录的起始位置， 直接外层过程的活动记录的起始位置 用于访问各外层的变量（非局部变量）。 用于访问各外层的变量（非局部变量）。
动态链：指向调用本过程的最新活动 ④. 动态链：指向调用本过程的最新活动 返回地址 记录的起始地址； 记录的起始地址； 动态链 每个活动记录的大小在编译时可以确定 SP ( 除动态数据 )，因此以 为变址器可方便的访问各个数据 ，因此以SP为变址器可方便的访问各个数据
编译原理
chapter9
运行时存储空间组织
top
u=15 v=10 形式单元 参数个数 gcd(15,10)
sp top sp
2 返回地址 老sp
x=15 y=10
main() 全局 /静态区 静态区
编译原理
chapter9
运行时存储空间组织
program p; 9.4 嵌套过程语言的栈式实现 var a,x:integer; 语言为例， 以Pascal语言为例Q(b:integer); 语言为例 由于允许嵌套定义过程， procedure ，由于允许嵌套定义过程，则会 var i:integer; 出现“非局部名字的访问”问题。 出现“非局部名字的访问”问题。因此简单的栈式存储分 procedure R(u:integer;var v:integer); 配不适用。 配不适用。 var c,d:integer; begin if u=1 then R(u+1,v) 活动记录中可配有静态链和嵌套层次表两种方式来实现。 静态链和嵌套层次表43;c)*(b-d); 两种方式来实现。 end {R} begin …. R(1,x); ……. end {Q} procedure S; var c,i:integer; begin a=1;Q(c); …….end {S} begin a=0;S;…… end

2019/3/26
10
9.1.3 过程及其活动
• 出现在过程定义中的某些标识符具有特殊的 意义，称为该过程的形式参数，简称为形参。 调用过程时，表达式作为实在参数(或实参)传 递给被调用的过程，以替换出现在过程体中 的对应形式参数。9.1.4节将讨论实参和形参 的结合方法。 • 过程体的每次执行叫做该过程的一个活动。 过程p的一个活动的生存期是从过程体执行的 第一步到最后一步，包括执行被p调用的过程 的时间，以及再由这样的过程调用其它过程 所花的时间，等等。
• 计算实参并将其右值传递给被调用过程 • 传值方式可以如下实现：
– 被调用过程为每个形参开辟一个称为形式单元的 存储单元，用于存放相应实参的值。 – 调用过程计算实参，并把右值放入相应的形式单 元中。
实际参数A
A 单向传值
形式参数X
A的值 被调用者 直接使用
14
调用者
2019/3/26
2. 传地址
24
每个过程的活动记录内容
TOP 临时变量 数组内情向量 局部变量 形式单元

2 1
SP 0
静态链 动态链 返回地址
形式单元：存放相 应的实在参数的地 址或值。 局部数据区：局部 变量、内情向量、 临时工作单元 ( 如存 放对表达式求值的 结果)。
25
2019/3/26
9.2.3 局部数据的组织
2019/3/26
9
9.1.3 过程及其活动
• 将“过程、函数和方法”统称为“过程” • 过程定义是一个声明，它的最简单形式是把 一个标识符和一个语句联系起来。该标识符 是过程名，而这个语句是过程体。 • 当过程名出现在可执行语句中时，称相应的 过程在该点被调用。过程调用就是执行被调 用过程的过程体。注意，过程调用也可以出 现在表达式中。

上下文语义的合法性检查的依据
在语义分析中，符号表所登记的内容将用于语义检查（如检查 一个名字的使用和原先的说明是否一致）和产生中间代码。通 过符号表中属性记录可进行相应上下文的语义检查。 例如，在一个C语言程序中出现 … int i [3][5]; //定义整型数组i … float i[4][2]; //定义实型数组i,重定义冲突 … int i [3][5]; //定义整型数组i,重定义冲突 … 编译过程首先在符号表中记录了标识符i的属性是3×5个整型元 素的数组，而后在分析第二、第三这两个定义说明时编译系统 可通过符号表检查出标识符i的二次重定义冲突错误。本例还可 以看到不论在后二句中i的其它属性与前一句是否完全相同，只 要标识符名重定义，就将产生重定义冲突的语义错误。
9.1符号表的作用和地位 符号表的作用和地位 9.2符号的主要属性及作用 符号的主要属性及作用 9.3符号表的组织 符号表的组织
9.1 符号表的作用和地位
收集符号属性 上下文语义的合法性检查的依据 作为目标代码生成阶段地址分配的依据
收集符号属性
编译程序扫描说明部分，收集有关标识符的属性，并在符号表 中建立符号的相应属性信息。 例如，编译程序分析到下述两个说明语句 int A; float B[5]; 则在符号表中收集到关于符号A的属性是一个整型变量，关于 符号B的属性是具有5个浮点型元素的一维数组。
9.2 符号的主要属性及作用
符号属性
1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符型的成员信息 （３） 函数及过程的形参
① 符号名 符号表中设置一个符号名域，存放该标识符，该域通 常就是符号表的关键字域。
作为目标代码生成阶段地址分配的依据

性质形式：x = c，以及x = NAC
20
数据流分析模式
数据流分析中，程序点和数据流值关联起来
数据流值表示了程序点具有的性质 和某个程序点关联的数据流值：程序运行中经过这个
点时必然满足的条件 (安全)
域
某个数据流所有可能值的集合称为该数据流值的域 不同的应用选用不同的域，比如到达定值
32
到达定值的控制流方程
只要一个定值能够沿某条路径 到达一个程序点，这个定值就 是到达定值
IN[B] = ∪P是B的前驱基本块OUT[P]
如果从基本块P到B有一条控制流 边，那么OUT[P]在IN[B]中
一个定值必然先在某个前驱的 OUT值中，才能出现在B的IN中
∪称为到达定值的交汇运算符
设基本块包含语句s1, s2, …, sn
fB = fsn ◦ … ◦ fs2 ◦ fs1
24
基本块之间的控制流约束
前向数据流问题
B1
B2
B3
B的传递函数根据IN[B]计算
得到OUT[B]
IN[B]和B的各前驱基本块的
B
OUT值之间具有约束关系
逆向数据流问题
前向数据流的例子
B的传递函数根据OUT[B]计 假如
死代码多半是因为前面的优化而形成的
比如，B5中的x = t3就是死代码
消除后得到
x = t3
a[t2] = t5 a[t4] = t3
==>
goto B2
a[t2] = t5 a[t4] = t3 goto B2
13
代码移动
循环中的代码会被执行很多次
循环不变表达式：循环的同一次运行的不同迭代中， 表达式的值不变
如果
s是x = y + z，那么OUT[s]是？ s是x = x + y，那么OUT[s]是？