循 环 优 化 循环的查栈 1．必经结点集
在程序流图中，对任意结点m和n，如果从流图的首结点出发，到达n的任一通路都要经过m，则称m是n的必经结点，记为m DOM n；流图中结点n的所有必经结点的集合称为结点n的必经结点集，记为D(n)。
显然，循环的入口结点是循环中所有结点的必经结点；此外，对任何结点n来说都有n DOM n。
如果把DOM看作流图结点集上定义的一个关系，则由定义容易看出它具有下述性质：
(1) 自反性：对流图中任意结点a，都有a DOM a。
(2) 传递性：对流图中任意结点a、b、c，若存在a DOM b和b DOM c, 则必有a DOM c。
(3) 反对称性：若存在a DOM b和b DOM a，则必有a=b。 2．回边
回边的定义如下：假设a→b是流图中一条有向边，如果b DOM a，则称a→b是流图中的一条回边。
查找循环的方法是：首先应用必经结点集来求出流图中的回边，然后利用回边找出流图中的循环的。 例2-6 求出流图的所有回边。
[解答] (1) 已知D(6)={1,2,4,6}，因存
在6→6且6 DOM 6，故6→6 是回边；
(2) 已知D(7)={1,2,4,7}，因存在7→4且 4 DOM 7，故7→4是回边；
(3) 已知D(4)={1,2,4}，因存在4→2且2 DOM 4，故4→2是回边
3．可归约流图
一个流图被称为可归约的，当且仅当流图中除去回边之外，其余的边构成一个无环路流图
对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。
图1 例示图 67 12345 删除归纳变量等优化。 1．代码外提
循环中的代码要随着循环反复执行，但其中某些运算的结果并不因循环而改变，对于这种不随循环变化的运算，可以将其外提到循环外。这样，程序的运行结果仍保持不变，但程序的运行效率却提高了。我们称这种优化为代码外提。 例2-7 试对图2-10给定的程序流图进行代码外提优化。
[解] 确定不变运算的原则是依次查看循环中各基本块的每个四元式，如果它的每个运算对象为常数或者定值点在循环外，则将此四元式标记为“不变运算”。查看图的程序流图，可以找出的不变运算是B3中的I=2和B4中的J=M+N。 进行代码外提时，只能将J=M+N提到循环前置结点，而B3中的I=2虽然是不变运算，但B3不是循环所有出口结点的必经结点，且循环中所有I的引用点并非只有B3的I定值能够到达，故B3中的I=2不能外提。最后，得到代码外提后的程序流图如图所示。
Y=0A=1B1if A>B goto B4B2I=2B=I+YB3B4A=A+IJ=M+NY=Y-1if Y=0 goto B2X=AB5
图2 程序流程图
if A>B goto B4B2I=2B=I+YB3A=A+IY=Y-1if Y=0 goto B2X=AB5B4J=M+NB?2Y=0A=1B1
图 3程序流程图
2．强度削弱
如果循环中有I的递归赋值I=I±C(C为循环不变量)，并且循环中T的赋值运算可化归为T=K*I±C1(K和C1为循环不变量)，那么T的赋值运算可以进行强度削弱。
进行强度削弱后，循环中可能出现一些新的无用赋值，如果它们在循环出口之后不是活跃变量则可以从循环中删除。此外，对下标变量地址计算来说，强度削弱实际就是实现下标变量地址的递归计算。 3．删除归纳变量
如果循环中对变量I只有惟一的形如I=I±C的赋值，且其中C为循环不变量，则称I为循环中的基本归纳变量。如果I是循环中一基本归纳变量，J在循环中的定值总是可化归为I的同一线性函数，也即J=C1*I±C2，其中C1和C2都是循环不变量，则称J是归纳变量，并称它与I同族。一个基本归纳变量也是一归纳变量。
第6章 运行时存储空间的组织
主要内容：
1 静态存储分配 2 简单的栈式存储分配 3 嵌套过程语言的栈式实现 4 堆式动态存储分配
主要介绍了静态存储分配和动态存储分配。 静态存储分配
如果在编译时就能够确定一个程序在运行时所需的存储空间大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地
址，存储空间的这种分配方法叫做静态分配。
对FORTRAN语言来说，其特点是不允许过程有递归性，每个数据名所需的存储空间大小都是常量(即不允许含可变体积的数据，如可变数组)，并且所有数据名的性质是完全确定的(不允许出现在运行时再动态确定其性质的名字这种情况)。这些特点确保整个程序所需数据空间的总量在编译时是完全确定的，从而每个数据名的地址就可静态地进行分配。 FORTRAN程序的静态分配
图FORTRAN程序的静态分配
主程序的目标代码 子程序1的目标代码 …… 子程序n的目标代码 全局变量 主程序的活动记录 子程序1的活动记录 …… 子程序n的活动记录 堆式动态存储分配
如果一种程序语言允许数据对象能够自由地分配和释放，或者不仅有过程而且有进程(process)这样的程序结构，那么由于空间的使用不一定遵循“先申请后释放”的原则，则栈式存储分配就不适用了。在这种情况下，通常使用一种称之为堆的动态存储分配方案。假定程序运行时有一个大的存储空间，需要时就从这个空间中借用一块，不用时再退还给它。
由于借、还的时间先后不一，因而经过一段时间的运行后，这个大空间就必然被分割成许多小块，这些块有些正在使用，有些则是空闲的(未被使用)。
对于堆式存储分配来说，需要解决两个问题：一是堆空间的分配，即当运行程序需要一块空间时应分配哪一块给它；另一个问题是分配空间的回收，由于返回堆的不用空间是按任意次序进行的，所以需要研究专门的回收分配策略。 堆式存储管理的方法
使用可利用空间表进行动态存储分配的方法又可分为如下两种：
(1) 定长块的管理。最简单的堆式存储管理方法是采用定长块的管理方法，
即将堆存储空间在初始化时就划分成大小相同的若干块，将各个块通过链表链接起来形成一个单向线性链表。由于各块大小相同，故分配时无需查找，只需将头指针所指的第一块分配给用户即可，然后头指针指向下一块。同样，当回收时，系统将待回收的存储块插入到表头即完成了该块的回收。
(2) 变长块的管理。变长块管理方法是一种常用的堆式存储管理方法，它可以根据实际需要来分配长度不同的空闲块；
系统开始时，存储空间是一完整空间，可利用空间表中只有一个大小为整个存储空间的空闲块。当系统运行一段时间后，随着分配和回收的进行，可利用空间表 中空闲块的大小和个数也随之改变。由于可利用空间表中的空闲块大小不同，因而存在着如何进行空闲块分配的问题。若可利用空间表存在多个大于所要求空间的空闲块，可采取以下三种方法之一进行存储分配：
(1) 首次满足法。从表头开始查找可利用空间表，将找到的第一个满足需要的空闲块或空闲块的一部分分配出去(当空闲块略大于所要求的空间时，则整块分配出去)，而其余部分仍作为一个空闲块留在表中。
(2) 最优满足法。系统扫描整个可利用空间表，从中找出一块不小于要求的最小空闲块予以分配。为了避免每次分配都要扫描整个表，通常将空闲块按由小到大的顺序进行排列。这样，所找到的第一个大于或等于所需空间的空闲块即为所求，无须再扫描整个表。
(3) 最差满足法。系统将可利用空间表中最大的空闲块予以分配(当然也要求其不小于所需空间的大小)，这种方法应使空闲块按由大到小的顺序排列，此时表头的空闲块即为所求。
第7章 目标代码生成
主要内容：
1 一个简单代码生成器
2 汇编指令到机器代码的翻译概述
主要介绍了一个简单的代码生成器。
要实现一个代码生成器，重点应该考虑两个问题：
1. 如何使生成的目标代码尽可能的短
2. 如何充分利用计算机的寄存器，减少目标代码中访问内存的次数 为了取得每个变量在基本块内的待用信息和活跃信息，可从基本块的出口由