研究生院第十章.ppt

第十章代码生成,代码生成器设计中的问题 目标机器 下次引用信息 一个简单的代码生成器 指令调度 寄存器优化,代码生成器的位置,各种代码的形式 中间代码: 后缀式，三地址代码，语法树 符号表中的项：名字，类型，嵌套深度，偏移量 目标代码：绝对机器代码，可再定位代码，汇编 代码生成器的输出必须是正确和高质量的 产生最优化代码的问题是不可判定的,代码生成器设计中的问题,代码生成器 依赖于目标机器和操作系统 要充分发挥目标机器的能力：充分利用目标机器的资源 代码生成器固有的问题 存储管理 指令选择 寄存器分配 计算次序选择 可移植的代码生成器 机器描述,代码生成器的输入,符号表信息 决定中间表示中名字所代表的数据对象的运行地址 偏移量 作用域 可能在动态时刻作为调试信息存在 中间表示 代码生成的很多技术是可以用于不同的中间表示的 代码生成前，中间表示记录了足够详细的程序信息 名字的值可以表示为目标机器能够直接操作的数 类型检查已经完成 明显的语义错误已经发现,目标程序,代码生成器的输出：目标程序 绝对机器语言 可以放在内存中固定地方，并立即执行 小程序、需要迅速编译和执行 可重定位的机器语言 程序可以分为多个目标模块，分别编译 需要连接装配器将一组可重定位模块一起装入执行 需要额外的开销，但灵活：可分别编译子程序和从目标模块中调用其它先前编译好的程序模块 如果目标机器不能自动处理重定位，则编译器必须提供显式的重定位信息给装配程序 汇编语言 代码生成的过程容易：可以产生符号指令和利用汇编器的宏 避免了重复汇编器的工作,存储管理,把程序中的名字映射到运行时的目标对象的地址是由前端和代码生成器共同完成的 语言中过程的语义决定了运行时刻名字如何与存储空间相联系 对名字的引用通过符号表 记录了名字在过程数据区的相对地址 所需要的存储空间 运行时活动记录的管理 运行时活动记录的分配和释放作为过程调用和返回序列的一部分 call（调用） return（返回） halt（暂停） action（动作），为其它语句占有位置,一个代码生成器的输入,其中，arr，i，j是过程s中定义的数据；buf和n是过程p定义的数据,静态分配管理,call调用语句用两条目标机器指令实现 MOV #here + 20 , callee. static-area GOTO callee. Code-area mov指令存放返回地址（#here + 20是一个字面常数，指向goto后的那条指令的地址） goto指令将控制转移到被调用过程的目标代码 过程的返回 过程的返回指令表明一个过程的结束 第一个过程没有调用者，以halt指令结束 GOTO * callee. static-area 按照活动记录中记录的返回地址返回,静态存储管理：目标代码的例子,/* s的代码 */ 100:ACTION1; 120:MOV140 , 364/* 保存返回地址140 */ 132:GOTO200/* 调用p */ 140:ACTION2; 160:HALT /* p的代码 */ 200:ACTION3; 220:GOTO * 364/* 返回到364单元里存放的地址 */ /* 300-363保留着s的活动记录 */ 300:/* 返回地址 */ 304:/* s的局部数据 */ /* 364-451保留着p的活动记录 */ 364:/* 返回地址 */ 368:/* p的局部数据 */,栈式分配管理,活动记录的存储单元采用相对地址 SP：指向栈顶活动记录开始的指针 过程调用的处理 第一个过程的代码通过将SP置为存储器中栈区的开始位置来初始化栈： MOV#stackstart, SP/* 初始化栈 */ 第一个过程的代码 HALT/* 终止过程运行 */ 过程调用序列给SP一个增量，并存储返回地址及将控制转移到被调用过程 ADD#caller, recordsize, SP/* 增加SP */ MOV#here + 16 , * SP/*存返回地址*/ GOTOcallee. code-area/*将控制转移到被调用过程*/,栈式分配管理（续）,过程返回的处理 在被调用过程中 GOTO * 0 ( SP )/* 返回到调用过程 */ 在调用过程中，恢复SP SUB #caller. recordsize , SP,栈式分配管理的例子,三地址代码 /* s的代码 */ action1 call q action2 Halt /* p的代码 */ action3 return /* q的代码 */ action4 call p action5 call q action6 call q return,栈式分配管理的例子（续）,/* s的代码 */ 100:MOV#600 , SP/* 初始化栈 */ 108:ACTION1 128:ADD#ssize , SP/* 调用序列开始 */ 136:MOV152 , * SP/* 压入返回地址 */ 144:GOTO300/* 调用q */ 152:SUB#ssize , SP 160:ACTION2 180:HALT /* p的代码 */ 200:ACTION3 220:GOTO* 0 (SP)/* 返回 */ /* q的代码 */ 300:ACTION3 320:ADD#qsize , SP 328:MOV344 , * SP/* 压入返回地址 */ 336:GOTO200/* 调用p */ 344:SUB#qsize , SP 600:/* 栈的开始*/,栈式分配管理（续）,名字的运行地址 静态存储策略 staticoffset 动态存储策略 局部名字 非局部名字 使用display表 这个指针在编译时刻不能确定，因此要在动态时刻实现地址的最终确定 MOV#0 , 12(R3) R3是存放display表指针的寄存器,指令地址的决定,通过一个计数器决定每个指令的地址 标号的处理：j: goto i/*j是当前语句的号码*/ 如果i小于j i出现在j之前，目标地址是i对应的三地址代码的第一条指令地址 如果i大于j i出现在j之后，目标地址此时不可知，可以利用回填的技术解决,指令选择,目标机器指令系统的性质决定了指令选择的难易程度 指令系统的一致性和完整性是重要因素 如果目标机器不能以一致的方式支持各种数据类型，则每种例外都要专门的处理 指令的速度和机器的特点是另一些重要的因素 如果不考虑目标程序的效率，则指令选择是直截了当的 代码的质量取决于它的执行速度和长度 可以从多种指令中选择合适的：a=a+1 MOVa , R0 ADD#1 , R0INCa MOVR0 , a 时间信息对代码序列是重要的，但不是任何时候都精确的,指令选择的例子,逐条语句地产生代码的方法常常产生低质量的代码 a := b + c d := a + e MOVb , R0 ADDc , R0 MOVR0 , a MOVa , R0 ADDe , R0 MOVR0 , d,寄存器分配,快速的寄存器 通常，利用寄存器放置运算对象的指令比运算对象在内存中的指令短些 执行也快些 充分利用寄存器对高质量的代码生成是重要的,寄存器 片内CACHE 片外CACHE 主存 外存,寄存器优化 局部性优化,寄存器分配（续）,寄存器使用的两个子问题 寄存器分配：为程序的某一点选择驻留在寄存器中的一组变量 寄存器指派：挑出变量将要驻留的具体寄存器 寄存器分配的最优化是NP完全的 特定要求的满足,计算次序选择,计算执行的次序会影响目标代码的效率 选择最佳次序是一个NP完全问题 ld r1 , t:无，非,无,非,3,活,活,3,u:3,活；a,c:无，活,无,非,2,2,活,活,a:2,活；b:无，活,无,非,1,1,活,活,t:3,活；,下次引用信息（4）,临时名字的存储分配 在需要临时变量时申请一个新的名字是简单有效的，但浪费空间 如果两个临时变量不是同时活跃的，则可以压缩在同一单元中 临时变量存储单元的分配： 依次检查临时变量区域的单元，找到第一个不含活跃临时变量的单元，指派给待分配的临时变量 如果没有合适的单元，则在活动记录的临时变量区域中增加一个单元,下次引用信息（5）,例子： t1 := a * at1 := a * a t2 := a * bt2 := a * b t3 := 2 * t2t2 := 2 * t2 t4 := t1 + t3t1 := t1 + t2 t5 := b * bt2 := b * b t6 := t4 + t5t1 := t1 + t2,一个简单的代码生成器（1）,这个代码生成器的假设条件： 三地址语句的每种算符都有对应的目标机器算符 计算结果留在寄存器中尽可能长的时间。只有在以下两种情况才把它存入主存 此寄存器要用于其它计算 正好在过程调用、转移或标号语句之前 在基本块的结尾，所有的寄存器都将保存，使得代码生成算法简单,一个简单的代码生成器（2）,后续的代码尽可能引用变量在寄存器中的值，而不访问主存，如对a := b + c 如果b在Ri中，c在Rj中，b在此语句后不活跃，则可以为它生成代价为1的代码ADD Rj , Ri，结果a存在Ri中 如果b在Ri中，c在内存单元中，b仍然不再活跃，则有： ADD c , Ri 或： MOV c , Rj ADD Rj , Ri 如果c的值以后还要用，则第二种方式更好一些，因为可以直接从寄存器Rj中取得它的值 由于语义的复杂性，上述代码生成可能要更为复杂,一个简单的代码生成器（3）,寄存器描述和地址描述 代码生成算法使用寄存器和名字的描述来跟踪寄存器的内容和名字的地址 寄存器描述记住每个寄存器当前存的是什么 在每个块的开始，寄存器描述显示所有寄存器为空（如果寄存器指派可以穿越块的边界，则此假设不成立） 块的代码生成过程中，每个寄存器保存零个或若干个名字的值 地址描述记住运行时每个名字的当前值可以在那个场所找到 这个场所可以是寄存器、栈单元、内存地址或它们的集合等 这些信息可以存于符号表中，在决定名字的访问方式时使用,一个简单的代码生成器（4）,代码生成算法 输入：一个基本块的三地址语句序列 输出：指令序列 方法：对每个三地址语句x := y op z完成下列动作 1调用函数getreg决定存放y op z计算结果的场所L，L通常是寄存器，也可以是内存单元 2查看y的地址描述，确定y值当前的一个场所y。如果y值当前既在内存单元又在寄存器中，选择寄存器作为y。如果y的值还不在L中，则产生指令MOV y , L 3产生指令op z , L，其中z是z的当前场所之一（同2一样优先选择寄存器），修改x的地址描述，以表示x在场所L。如果L是寄存器，修改它的描述，以表示它含x的值 4如果y和（或）z的当前值不再引用，在块的出口也不活跃，并且在寄存器中，则修改寄存器描述，以表示在执行了x := y op z后，这些寄存器分别不再含y和（或）z的值,一个简单的代码生成器（5）,基本块结束的处理 在基本块的出口，用MOV指令把在寄存器中的活跃变量的值保存 值在寄存器中 这个值在出口活跃 复写语句的处理：x := y y在寄存器中 改变寄存器和地址的描述，记住x的值出现在该寄存器中 如果y不再引用，且在块的出口不活跃，该寄存器不再保存y的值 y的值仅在内存中 若记住x的值在y的内存单元中，但如果更新y的值复杂；可以用getreg找到一个存放y的寄存器，并记住该寄存器是存放x的场所 或产生指令MOV y , x，如果x在块中不再引用，此法较好,一个简单的代码生成器（6）,函数getreg 返回保存语句x := y op z的x值的场所L 简单的实现方法：基于下次引用信息 1如果名字y在寄存器中，此寄存器不含其它名字的值，并且y不活跃，且在执行x := y op z后没有下次引用，则返回y的这个寄存器作为L 21失败时，如果有的话，返回一个空闲寄存器 32不成功时，如果x在块中有下次引用，或op是必须使用寄存器的算符（如变址），则找一个已被占用的寄存器R 将R中的值根据存有的变量（可能不止一个）保存到内存单元中，并修改相关的地址描述 R的选择要考虑spill的代价 4如果x在本块中不再引用，或者找不到适当的被占用寄存器，则选择x的内存单元作为L,一个简单的代码生成器（7）,例子： 赋值语句d := ( a b ) + ( a c ) + ( a c )可以翻译成下面的三地址代码序列 t := a b ; u := a c ; v := t + u ; d := v + u d在出口活跃，产生的代码序列： 语 句生成的代码寄存器描述地址描述 寄存器空 t := a bMOV a , R0 R0含t SUB b , R0t在R0中 u := a c MOV a , R1 R0含tt在R0中 SUB c , R1 R1含uu在R1中 v := t + u ADD R1 , R0 R0含vu在R1中 R1含uv在R0中 d := v + uADD R1 , R0 R0含dd在R0中 MOV R0 , dd在R0和内存中,一个简单的代码生成器（8）,例子的讨论 上述代码的代价为12 可以在第一个指令后增加MOV R0 , R1，从而将代价减少为11（删去了MOV a , R1）,一个简单的代码生成器（9）,为其它类型的语句产生代码 变址语句的处理，其中： 偏移为Si 活动记录的指针在寄存器A 寄存器R是调用函数getreg时返回的寄存器 对于第一个赋值，如果a在块中有下次引用，且寄存器R是可用的，则a留在寄存器R中 在第二个语句中，假定a静态分配 语 句 i在寄存器Ri中 i在内存Mi中 i在栈中 代 码 代价 代 码 代价 代 码 代价 a := bi MOV b(Ri) , R 2 MOV Mi , R 4 MOV Si(A) , R 4 MOV b(R) , R MOV b(R) , R ai := b MOV b , a(Ri) 3 MOV Mi , R 5 MOV Si(A) , R 5 MOV b , a(R) MOV b , a(R),一个简单的代码生成器（10）,指针语句的处理，其中： 偏移为Sp 活动记录的指针在寄存器A 寄存器R是调用函数getreg时返回的寄存器 对于第一个赋值，如果a在块中有下次引用，且寄存器R是可用的，则a留在寄存器R中 在第二个语句中，假定a静态分配 语 句 p在寄存器Rp中 p在内存Mp中 p在栈中 代 码 代价 代 码 代价 代 码 代价 a := * p MOV * Rp , a 2 MOV Mp , R 3 MOV Sp(A) , R 3 MOV * R , R MOV * R , R * p := a MOV a , * Rp 2 MOV Mp , R 4 MOV a , R 5 MOV a , * R MOV R , *Sp(A),一个简单的代码生成器（11）,条件语句：两种实现方式，以if x y，则CMP x , y置条件码为正等 条件转移机器指令根据指定的条件（ , , =）是否满足来决定是否转移，如果用指令CJ= z表示如果条件码是负或零则转到z，所以有 CMP x , y CJ z,一个简单的代码生成器（12）,条件码的描述的记录 这个描述告诉我们上次设置条件码的名字和比较的名字对 x := y + zMOV y , R0 if x 0 goto zADD z , R0 MOV R0 , x CJ z 根据条件码描述可以知道，在ADD z , R0之后，条件码是由x设置的,程序的依赖关系,依赖关系是什么？ 依赖关系表明了两个语句（或操作、计算）之间在执行顺序上存在的限制 如果两个语句（或操作、计算）间存在着依赖关系，则这两个语句（或操作、计算）的执行必须满足依赖关系的要求 如果两个语句（或操作、计算）间没有依赖关系，则这两个语句（或操作、计算）可以被并行执行或调整执行的顺序。 依赖分析是分析语句（或操作、计算）间的依赖关系，从而确定它们是否可以并行执行 依赖关系的分类 数据依赖关系 控制依赖关系 控制流分析的结果 计算的执行与否取决于控制条件是否满足,数据依赖关系的定义,定义：如果语句S在语句S之前执行，且两个语句访问相同变量V,其中至少有一个语句是对V赋值，则我们说这两个语句之间存在数据依赖关系，记为ss： 如果V在S中定义，在S中使用，称为真依赖，或流依赖，记为s ts 如果V在S中使用，在S中定义，称为反依赖，记为sas 如果V在S和S中定义，称为输出依赖，记为SoS 如果V在S和S中使用，称为输入依赖，记为SiS 例子 S1: A=1.0 S2: B=A+3.14159 S3: A=1/3*(C-D) (无对A,B,C,D赋值） S4: A=(B*3.8)/1.78,依赖图,以语句为节点，依赖关系为边，上例的依赖图为：,面向指令调度的依赖图,无环区域的依赖图是一个有向无环图G(V, E)， 其中节点表示操作，边表示两个操作的执行时刻必须满足的约束。 依赖边的分类 流依赖、反依赖、输出依赖 由访问寄存器导致的依赖 vs 由访问内存导致的依赖 投机依赖边 边上通常记有所需的延迟，这个延迟与操作及依赖边的类型有关 伪依赖所需的延迟通常不大于1。 内存取数操作的延迟通常难于在编译时刻确定。 延迟的具体值由机器模型提供。,依赖图的构造,构造依赖图通常可通过对基本块内的所有操作的一次或多次遍历完成，以构造流依赖边为例，算法如下：,void Build_DAG_For_BB(BB* bb) For each op in bb, from head to tail For each operand of op Let def_op_list be the defining ops list of operand ; while (def_op_list != NULL) Get an def_op from def_op_list; If (dependence exists between def_op and op) Build an edge between def_op and op; Add op to the defining ops list of ops results. Remove those ops in the list that shadowed by op. ,add t1 = 8,p,ld4 t2 = log,add t2 = 1,t2,mov out0 = 0,br.ret rp,ld4 out0 = t4,shladd t4 = n,2,t3,ld4 t3 = p,st4 log = t2,ld4 count = t1,cmp4.ge p1,p2=n,count,struct dyn-array int *x; int count; ; dyn-array *p; If( n count ) (*log)+; return p-xn; else return 0; ,Y,N,依赖图的例子,指令调度,在满足依赖关系、资源约束及硬件施加的其它约束条件的前提下，重新排定指令执行的顺序，提高资源利用率，使多个操作能够并行执行，同时减少因相关引起的处理器停顿，以缩短程序的执行时间。 NP完全问题 指令调度的复杂性来自于程序控制流和数据流的复杂性，以及硬件平台的复杂性。 处理上述复杂性的方法： 限制指令调度的范围，将流图划分为若干具有良好性质的、规模可控的区域。 将机器相关部分从指令调度中分离出来。,指令调度的一般步骤,构造区域 (Region) 构造区域上的依赖图 根据依赖图进行调度 代码的修正 若有未调度的代码，重复上述步骤。,指令调度,依据区域流图的性质，可如下分类：,指令调度,Trace 调度,选择调度,Superblock/Hyperblock,SEME区域调度,无环调度,核心识别,模调度,软件流水,全局调度,局部调度,局部指令调度算法表调度,void Schedule_BB(BB* bb) Build dependence graph for bb; Compute ready candidates for current cycle; while (candidate list not empty) If (theres no empty slot in current cycle or all candidates tried) Advance to next cycle. Reset all candidates untried. Update micro-schedulers internal states. Pick an op with highest priority from the candidate list to schedule; Query machine model whether the selected op can be commited. if (machine model answers NO) set the op tried so that it will not be tried in current cycle. else commit the code motion. Update DAG, Candidate list, and Micro-Scheduler internal states, etc. ,就绪队列,一般而言，在某一时刻的就绪操作应满足下列条件： op在依赖图上的所有依赖前驱均已调度过。 若op引用了某个操作op的结果，op于第i拍发出，且两者之间的延迟为l，则op的发出时刻不得早于i+l。 若硬件有记分牌，则条件 2 可以去掉，这样在调度过程中就绪队列不会为空，但队列中的操作地位不同。 给每个就绪操作加一个等待时间，每次调度总是选取等待时间最小的操作。 比较当前时刻与每个操作的最早开始时间。 就绪队列在调度开始前计算一次，以后每调度一个操作，只需检查其在依赖图上的后继。,操作的调度优先序,决定调度操作的先后顺序时使用的启发式信息： 执行频率 关键路径 投机性 所需补偿代码数量 依赖图上的后继个数 寄存器的使用情况 是否在调度过程中动态更新上述信息需在代码质量与编译时间之间作出折中。,A,B,C,D,E,F,G,E,NR,F,B,G,A,C,D a nested region as NR,全局的情形：构造区域,调度区域一般是无环的。依据流图的结构，基本块的执行频率，以及区域的预期大小等启发式信息构造。,Trace 调度,Trace: 执行过程中可能经过的一个基本块的线性序列 Trace 的选择： 根据分支概率及是否需要插入补偿代码等启发式规则选择执行路径，代码移动局限于该路径 局部调度方法的延伸：以执行频率较低的路径上代码执行时间的增加为代价，换取频繁执行的路径上代码执行时间的缩减,Trace 调度：算法,步骤： 估算每个操作的执行频率 挑选Trace 使用某种局部指令调度方法如表调度对形成的Trace进行调度 用调度完的代码替换流图中原来的Trace，必要时在Trace之外插入相应的补偿代码 遍历调度后的流图并释放代码 Trace 调度的问题： 插入补偿代码的过程在实现上复杂，且可能产生冗余 在Trace 内作的一些优化，如复写传播，死代码删除等，由于split和join节点的存在而受到限制 若分支概率相近，Trace 难于选择。,Superblock 调度,A,B,C,F,E,D,A,B,C,F,E,D,F,Z,Z,Y,Y,尾复制,Hyperblock 调度,条件执行 体系结构提供64个1位的谓词寄存器(predicate registers) 带有谓词的指令仅当谓词为真时改变机器状态，否则相当于一条NOP指令 编译器为分支两侧的指令分配不同的谓词寄存器，由比较 (cmp) 指令在执行时刻为谓词赋值。 条件执行可消除分支 将控制依赖转化为数据依赖 减少由于分支预测错误带来的开销 有可能增加关键路径长度,寄存器分配,决定程序中哪些变量的值应该存放在寄存器中。 减少访存和复写操作。 最重要的编译优化之一： 访问寄存器和存储器的代价相差在一个数量级以上。 寄存器的数目虽已大为增加，但仍是十分稀缺的资源。 许多优化的效果依赖寄存器分配的结果。 寄存器分配与寄存器指派 寄存器分配：决定哪些变量该占用寄存器。 寄存器指派：决定变量该使用哪个寄存器。 Caller-Save与Callee-Save寄存器 传递参数与返回值的寄存器 叶过程与非叶过程,活跃区间与干涉,一个变量的活跃区间： 一个变量的（极小化）活跃区间是变量的定值与引用的一个子集，对于此集合中的任意定值dm和引用un，或者un在dm的du链上，或者存在一个由此集合中的定值与引用组成的交错序列dm=d0、u0、d1、u1、dk、uk= un，其中的任何一个ui、同时在di和di+1的du链上。 直观上，变量的活跃区间对应于流图上联结变量的定值点和引用点的一个连通区域。 干涉： 两个变量的活跃区间干涉（简称两个变量干涉），若在其中某个变量的定值处，另一个变量是定值到达和活跃的。,图的着色与寄存器分配,当前占统治地位的寄存器分配方法是图着色方法。 图的k着色问题 寄存器分配归结为图着色问题： 首先构造干涉图，图中每个结点代表一个变量的活跃区间，如果两个变量干涉，则在相应的结点vi和vj之间用边eij连接。 假设目标机有k个寄存器可用，则寄存器分配的问题就变成对这个图找一个k着色的方案。,x = . y = . = . x z = . = y = z,y,z,x,Requires Two Colors,y,z,x,干涉图的例子,x,z,y,有控制流的情形,x,y,z,需要两种颜色,图着色寄存器分配Chaitins,判断一个图是否k可着色是一个NP完全问题。 注意到图中度不大于k的节点总可以被着色，Chaitin提出了一种启发式方法：持续地从图中删掉度小于k的节点，若此过程一直进行到所有的节点均被删除，则图是k可着色的。若此过程阻塞，即图中所有节点的度均不小于k，则依据溢出代价大小，从图中选择某个节点，删除该节点及其相连的边。然后重复上述过程。,极小化活跃区间,Rename(CFG) for each (var) lrsvar = ; for each (d in dd_chain(var) lr = new_a_lr(du_chain(d); lrsvar += lr; endfor do for each (lr1 in lrsvar) for each (lr2 in lrsvar ,首先每个变量的每个du链都被初始化为一个活跃区间。 其次，若同一个变量的两个du链包含公共的引用点，则将相应的两个活跃区间合并成一个活跃区间。 叠代直到活跃区间的集合稳定。,极小化活跃区间,活跃区间的极小化有利于减轻变量间的干涉，减小干涉图的颜色数。,for ( i=0; in; i+ ) a = b + d; b = a + d; a = c + d; c = a + d; ,for ( i=0; in; i+ ) a1 = b + d; b = a1 + d; a2 = c + d; c = a2 + d; ,a,b,c,d,a1,b,c,d,a2,建干涉图,Build_Interference_Graph_For_BB(block) live_var = var | var is live at the end of block ; for each statements S, from tail to the head of block live_var = live_var - variable used by definition in S ; if S is not of the form a = b; make every var in live_var interfere with the variables defined in S; live_var = live_var all the variables used by reference in S; ,计算溢出代价,最小化被溢出变量的代价值的和 溢出代价： 分配的优先序： 代价较大的变量的优先级也较大 干涉图上度较大的变量的优先级较低,Cost(lr) = LOAD_COST x LoadTimes + STORE_COST x StoreTimes + MOVECOST x MoveTimes,Priority(lr) = Cost(lr) / Deg(lr),图着色寄存器分配Priority-Based,Chow和Hennessy提出按活跃区间的优先级从高到低的顺序对图进行着色 假定变量原本在内存中 全局与局部两遍寄存器分配，GRA为LRA预留寄存器 粗粒度：以基本块为分配单位 优先级根据为变量分配寄存器能够减少的访存操作决定 一遍着色，没有Chaitin式的先化简后回溯 提出活跃区间分割（Live Range Splitting），即当着色过程阻塞时，把活跃区间分成若干较小的活跃区间。这样可以产生较少的溢出,寄存器分配：有谓词的情形,x,z,y,x,z,需要三个寄存器,y,(p2),(p1),(p2),(p1),谓词分析,p0,p2,p1,x,y,z,P1与p2不可能同时为真,(p2),(p1),(p1),(p2),考虑谓词的寄存器分配,x,z,y,根据谓词分析的结果构造干涉图,x,y,z,只需要两个寄存器,(p2),(p1),(p1),(p2),指令调度和寄存器优化的时序问题,先做寄存器分配，再作指令调度 先做寄存器分配的优点在指令级并行度低、寄存器又少的处理机上得以体现 从指令调度的观点看该顺序的最主要问题是：寄存器分配会带来反依赖和输出依赖，这将在一定程度上影响指令调度的效果 先做指令调度，再作寄存器分配 虽然更好的指令调度是人们所期望的，但如果代码需要的寄存器比能获得的寄存器还要多的话，则这个事实是不能令人接受的 指令调度会增大寄存器分配的压力，再好的指令调度所获得的性能的提高也无法弥补由于较差的寄存器分配所带来的损失,指令调度和寄存器优化的时序问题的例子,1) Val3 = val1 * 3假设乘法指令需要4拍 2) addr1 = val3 3) Val4 = val1 * 2 4) addr2 = val4 若先做寄存器分配，再作指令调度 由于val3和val4此后不再被继续引用，所以可以分在一个寄存器中 发射时间指令 0r3 = r1 * 3 4store addr1 , r3 5r3 = r1 * 2 9store addr2 , r3共需要10拍,指令调度和寄存器优化的时序问题的例子,若先做指令调度，再作寄存器分配 此时，由于val3和val4活跃区间重叠，所以不可以分在一个寄存器中 发射时间指令 0r3 = r1 * 3 1r4 = r1 * 2 4store addr1 , r3 5store addr2 , r4共需要6拍 而且如果处理机能同时发射两条定点乘法和两条store指令的话，这一组指令可以在5拍完成,指令调度和寄存器优化的时序问题（续）,协作式指令调度和寄存器分配 避免的分裂考虑上述两个问题引起的缺乏通讯的问题 但算法过于复杂，难于实现，具有理论意义 一种实际的时序 先做指令调度（由于寄存器较多，所以可以忍受） 再作寄存器分配，但为了获得较好的效果，可能会移动基本块中的指令位置或由于寄存器溢出和恢复增加了基本块中的指令 在基本块内，对已经更改过的基本块重新进行指令调度,