Series /

«编译原理»笔记

Contents

第 7 章 运行时环境
ch-7-runtime-environment
2021
December 6
运行时内存的划分 目标代码存放在固定大小的 代码区 大小可确定的变量、全局变量存放在固定大小的 静态区(可读可写) 栈存放活动记录(或称为栈帧),主要是一些短生命周期的数据。每个线程有自己的栈。 堆存放编译时大小无法确定的数据(而指向这些数据的指针,比如数组的首地址,则存放在栈中),通常是长生命周期的数据。线程之间可以共享堆。 过程起源于为了节省内存而可独立编译的程序片段。 一个过程的每一次执行称为一个活动。 每次活动时记录的状态称为活动记录。每个活动记录中有一系列的域。 用一棵树存放程序运行过程中所有的活动状态,称为活动树。 活动树和程序行为间存在对应关系: 1)过程调用的序列和活动树的前序遍历相对应; 2)过程返回的序列和活动树的后序遍历相对应; 3)亲节点是未结束活动,且路径顺序即调用顺序 假定控制流(当前状态)位于某个过程的特定活动中,且该活动对应于活动树上的某个结点 N。那么当前尚未结束的(即活跃的)活动就是结点 N 及其祖先结点对应的活动。这些活动被调用的顺序就是他们从根节点到 N 的路径上的出现顺序。这些活动将按照这个顺序的反序返回。 根据这样的性质,使得我们可以通过 栈 实现程序控制。 活动记录(栈帧)中各种域的作用 如下: # 名称 作用 1 临时数据 存放表达式中间结果 2 局部数据 存放局部数据。详见下文。 3 机器状态 调用前的状态,如之前的寄存器等,以便恢复现场 4 访问链 指向外层的作用域栈帧。由于只和代码有关,又叫静态链 5 控制链 指向调用方的(上一个)栈帧(比如 RSP,存放上个帧栈顶)由于在运行过程中不断压栈时形成,又叫动态链 6 实参 用于存放主调函数为被调用函数所提供的实参信息 7 返回值 被调用函数用来为主调函数存放返回值的域 斜体 表示非必须的 在实际实现时,返回值和部分实参通过寄存器传递。多数数据放在栈中。
第 9 章 目标代码生成
ch-9-target-code-generation
2021
December 22
目标代码生成概述 目标代码生成程序的任务 将前端产生的源程序的中间代码表示转换为等价的目标代码。 对目标代码生成程序的要求: 正确 高质量 代码生成程序的位置 输入: 中间代码 符号表 记录了与名字有关的信息 决定中间表示中的名字所代表的数据对象的运行地址 输出: 与源程序等价的目标代码 逻辑地址空间 划分成为四个代码及数据区域: 一个静态确定的代码区 Code。这个区存放可执行的目标代码。目标代码的大小可以在编译时刻确定。 一个静态确定的静态数据区 Static。这个区存放全局常量和编译器生成的其他数据。全局常量和编译器数据的大小也可以在编译时刻确定。 一个动态管理的堆区 Heap。这个区存放程序运行时刻分配和释放的数据对象。Heap 的大小不能在编译时刻静态确定。 一个动态管理的栈区 Stack。这个区存放过程的活动记录。活动记录会随着过程的调用和返回被创建和消除。和堆区 - 样,栈区的大小也不能在编译时刻确定。 目标代码的形式 绝对地址的机器语言程序 可把目标代码放在内存中固定的地方、立即执行 可重定位的机器语言程序 .obj(DOS)、.o(UNIX) 开发灵活,允许各子模块单独编译 由连接装配程序将它们连接在一起,生成可执行文件 汇编语言程序 代码生成程序设计的相关问题。 基本块与流图 断句 如何划分基本块(考点): 龙书说: 把中间代码划分成为基本块 (basic block)。每个基本块是满足下列条件的最大的连续三地址指令序列。 ①控制流只能从基本块中的第 - 一个指令进人该块。也就是说,没有跳转到基本块中间的转移指令。 ②除了基本块的最后一个指令,控制流在离开基本块之前不会停机或者跳转。 GOTO 后断。 GOTO 到的语句之前断。 GOTO 前不断后断。
第 10 章 代码优化
ch-10-code-optimization
2021
December 22
掌握基本块优化技术,主要包括: 公共表达式的删除、复制传播、常数合并及常数传播、削弱计算强度等; 掌握循环优化技术,主要包括: 循环展开、代码外提、削弱计算强度、删除归纳变量; 概述 代码优化程序的任务 对中间代码或目标代码进行等价变换,使变换后的代码质量更高。 对代码优化程序的要求 等价变换 提高目标代码的执行速度 减少目标代码占用的空间 代码优化程序的位置 目标代码生成之前的中间代码优化 目标代码生成之后的目标代码优化 基本块优化 注意:不能轻易跨越基本块进行优化 如: i = 0 -------------- LOOP: i = i + 1 // 不能优化为 i = 1 ... if i < n goto LOOP 常数合并 计算常数表达式。$ x= 3*2+1 \Rightarrow x = 7$ 常数传播 常量作为值代入表达式 删除公共表达式 反复使用某个求值,而求值所依赖的变量状态皆未改变,则没必要反复求值,用第一次的即可。 复制传播 a = b, c = a,则后文实际上都可以用 b 来表示 a, c 删除死代码 求值后却没有使用的值 无法到达的块(如恒假条件里的块) 死块的后面很可能也是死块 削弱计算强度 例如 x = y**2 变成 x = y * y 例如 x = x + 0, x = 1 * x 可能是无意义的。 改变计算次序(没看懂有何意义) 循环优化 为循环语句生成的中间代码包括如下 4 部分: