研究生院第十章.ppt

《研究生院第十章.ppt》由会员分享，可在线阅读，更多相关《研究生院第十章.ppt（80页珍藏版）》请在三一办公上搜索。

1、June 5,2000,第十章代码生成,代码生成器设计中的问题目标机器下次引用信息一个简单的代码生成器指令调度寄存器优化,June 5,2000,代码生成器的位置,各种代码的形式中间代码:后缀式，三地址代码，语法树符号表中的项：名字，类型，嵌套深度，偏移量目标代码：绝对机器代码，可再定位代码，汇编代码生成器的输出必须是正确和高质量的产生最优化代码的问题是不可判定的,June 5,2000,代码生成器设计中的问题,代码生成器依赖于目标机器和操作系统要充分发挥目标机器的能力：充分利用目标机器的资源代码生成器固有的问题存储管理指令选择寄存器分配计算次序选择可移植的代码生成器机器描述,June 5,2

2、000,代码生成器的输入,符号表信息决定中间表示中名字所代表的数据对象的运行地址偏移量作用域可能在动态时刻作为调试信息存在中间表示代码生成的很多技术是可以用于不同的中间表示的代码生成前，中间表示记录了足够详细的程序信息名字的值可以表示为目标机器能够直接操作的数类型检查已经完成明显的语义错误已经发现,June 5,2000,目标程序,代码生成器的输出：目标程序绝对机器语言可以放在内存中固定地方，并立即执行小程序、需要迅速编译和执行可重定位的机器语言程序可以分为多个目标模块，分别编译需要连接装配器将一组可重定位模块一起装入执行需要额外的开销，但灵活：可分别编译子程序和从目标模块中调用其它先前编译好

3、的程序模块如果目标机器不能自动处理重定位，则编译器必须提供显式的重定位信息给装配程序汇编语言代码生成的过程容易：可以产生符号指令和利用汇编器的宏避免了重复汇编器的工作,June 5,2000,存储管理,把程序中的名字映射到运行时的目标对象的地址是由前端和代码生成器共同完成的语言中过程的语义决定了运行时刻名字如何与存储空间相联系对名字的引用通过符号表记录了名字在过程数据区的相对地址所需要的存储空间运行时活动记录的管理运行时活动记录的分配和释放作为过程调用和返回序列的一部分call（调用）return（返回）halt（暂停）action（动作），为其它语句占有位置,June 5,2000,一个代码

4、生成器的输入,其中，arr，i，j是过程s中定义的数据；buf和n是过程p定义的数据,June 5,2000,静态分配管理,call调用语句用两条目标机器指令实现MOV#here+20,callee.static-areaGOTO callee.Code-areamov指令存放返回地址（#here+20是一个字面常数，指向goto后的那条指令的地址）goto指令将控制转移到被调用过程的目标代码过程的返回过程的返回指令表明一个过程的结束第一个过程没有调用者，以halt指令结束GOTO*callee.static-area按照活动记录中记录的返回地址返回,June 5,2000,静态存储管理：目标

5、代码的例子,/*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的局部数据*/,June 5,2000,栈式分配管理,活动记录的存储单元采用相对地址SP：指向栈顶活动记录开始的指针过程调用的处理第一个过程的代码通过将

6、SP置为存储器中栈区的开始位置来初始化栈：MOV#stackstart,SP/*初始化栈*/第一个过程的代码HALT/*终止过程运行*/过程调用序列给SP一个增量，并存储返回地址及将控制转移到被调用过程ADD#caller,recordsize,SP/*增加SP*/MOV#here+16,*SP/*存返回地址*/GOTOcallee.code-area/*将控制转移到被调用过程*/,June 5,2000,栈式分配管理（续）,过程返回的处理在被调用过程中GOTO*0(SP)/*返回到调用过程*/在调用过程中，恢复SPSUB#caller.recordsize,SP,June 5,2000,栈式

7、分配管理的例子,三地址代码/*s的代码*/action1call qaction2Halt/*p的代码*/action3return/*q的代码*/action4call paction5call qaction6call qreturn,June 5,2000,栈式分配管理的例子（续）,/*s的代码*/100:MOV#600,SP/*初始化栈*/108:ACTION1128:ADD#ssize,SP/*调用序列开始*/136:MOV152,*SP/*压入返回地址*/144:GOTO300/*调用q*/152:SUB#ssize,SP160:ACTION2180:HALT/*p的代码*/200

8、:ACTION3220:GOTO*0(SP)/*返回*/*q的代码*/300:ACTION3320:ADD#qsize,SP328:MOV344,*SP/*压入返回地址*/336:GOTO200/*调用p*/344:SUB#qsize,SP 600:/*栈的开始*/,June 5,2000,栈式分配管理（续）,名字的运行地址静态存储策略staticoffset动态存储策略局部名字非局部名字使用display表这个指针在编译时刻不能确定，因此要在动态时刻实现地址的最终确定MOV#0,12(R3)R3是存放display表指针的寄存器,June 5,2000,指令地址的决定,通过一个计数器决定每个

9、指令的地址标号的处理：j:goto i/*j是当前语句的号码*/如果i小于ji出现在j之前，目标地址是i对应的三地址代码的第一条指令地址如果i大于ji出现在j之后，目标地址此时不可知，可以利用回填的技术解决,June 5,2000,指令选择,目标机器指令系统的性质决定了指令选择的难易程度指令系统的一致性和完整性是重要因素如果目标机器不能以一致的方式支持各种数据类型，则每种例外都要专门的处理指令的速度和机器的特点是另一些重要的因素如果不考虑目标程序的效率，则指令选择是直截了当的代码的质量取决于它的执行速度和长度可以从多种指令中选择合适的：a=a+1MOVa,R0ADD#1,R0INCaMOVR0

10、,a时间信息对代码序列是重要的，但不是任何时候都精确的,June 5,2000,指令选择的例子,逐条语句地产生代码的方法常常产生低质量的代码a:=b+cd:=a+eMOVb,R0ADDc,R0MOVR0,aMOVa,R0ADDe,R0MOVR0,d,June 5,2000,寄存器分配,快速的寄存器通常，利用寄存器放置运算对象的指令比运算对象在内存中的指令短些执行也快些充分利用寄存器对高质量的代码生成是重要的,寄存器片内CACHE片外CACHE主存外存,寄存器优化局部性优化,June 5,2000,寄存器分配（续）,寄存器使用的两个子问题寄存器分配：为程序的某一点选择驻留在寄存器中的一组变量寄存

11、器指派：挑出变量将要驻留的具体寄存器寄存器分配的最优化是NP完全的特定要求的满足,June 5,2000,计算次序选择,计算执行的次序会影响目标代码的效率选择最佳次序是一个NP完全问题ld r1,&ald r1,&aadd r1,r0mul r2,r3mul r2,r3add r1,r0add r1,r2add r1,r2,June 5,2000,代码生成的途径,代码生成器的目的正确的代码：最重要的目标易于实现、调试和维护代码生成需要多方面的信息流信息依赖信息 代码生成的可移植性也是要考虑的一个问题将机器相关部分和不相关部分区分开,June 5,2000,目标机器（1）,熟悉目标机器和它的指令

12、系统这是设计一个好的代码生成器的先决条件但不存在通用的有效的机器描述目标机器字节可寻址机器，4字节为一个字有n个通用寄存器R0,R1,R(n-1)指令形式op源，目的MOV（源传到目的）ADD（源加到目的）SUB（目的减去源）contents(a)表示由a代表的寄存器和内存地址的内容,June 5,2000,目标机器（2）,地址模式 模式形式地址 附加代价绝对地址MM 1寄存器RR 0变址c(R)c+contents(R)1间接寄存器*Rcontents(R)0间接变址*c(R)contents(c+contents(R)1直接量#cc 1指令举例MOV R0,MR0=MMOV 4(R0),M

13、contensts(4+contents(R0)=MMOV*4(R0),Mcontents(contensts(4+contents(R0)=M,June 5,2000,目标机器（3）,指令代价如果把指令代价取成1，加上上述的地址模式的附加代价，就是对应指令的长度（以字计算）寄存器地址模式的代价为0含内存单元和常量的地址模式的代价是1，因为这种运算对象必须和指令存在一起如果空间是至关重要的，则应使指令的长度极小化此种优化有如下的两个额外好处：节省取指的开销，从而减少指令的执行时间提高指令cache的使用效率指令代价的例子MOV R0,R1指令代价是1，只占一个内存字MOV R5,M代价是2，M

14、要独占一个内存字ADD#1,R3代价是2，常数1占一个内存字SUB 4(R0),*12(R1)代价是3，4和12各占一个内存字,June 5,2000,目标机器（4）,对语句a:=b+c生成的代码 MOV b,R0ADD c,R0MOV R0,a代价=6 MOV b,aADD c,a代价=6这两种代码的代价虽然都是6，但它们的执行开销可能是不一样的如果用R0,R1,R2分别含a,b,c的地址，则有：MOV*R1,*R0ADD*R2,*R0代价=2如果R1,R2分别b,c的值，且b的值在这个赋之后不再需要，则有：ADD R2,R1MOV R1,a代价=3产生好的代码，必须有效利用它的寻址能力，尽

15、量把名字的左值或右值保存在寄存器中，以便在不久的将来使用,June 5,2000,Knobsfiles,SupplementalInfo,FSA Table,MachineDescription Builder,Machine-Level API,Micro-Scheduler,前编译时刻,MachineDescriptionFiles,编译时刻,后端,机器模型,OPT,LCS,GCS,SWP,RA,Schedule-Level API,June 5,2000,由预处理器从原始机器描述文件中提取机器参数，生成各种描述表，并对这些表作预处理，构造FSA的状态转换表：功能部件表操作延迟表旁路表模板

16、表模板状态表端口状态表状态转换表机器级 API 向微调度器和编译其它部分提供查询机器参数和状态的接口，并维护相关表格。,机器描述表,June 5,2000,代码生成器的产生方法,解释型代码生成定义一个虚拟的目标机，编译器的前端直接把源语言映射到虚拟的目标机语言重用性差，代码生成器紧密地与汇编语言绑定在一起，对每一种机器要重新写后端代码生成模式匹配代码生成用机器描述语言描述了中间语言到汇编语言的映射，预处理器将它转换成相应的模式集代码生成器将中间语言与模式集作匹配，生成汇编代码匹配算法与机器无关,June 5,2000,代码生成器的产生方法（续）,表驱动代码生成把输入的表达式树看成是一个输入串通

17、过构造状态转换表，用一系列语义动作完成代码生成 表驱动和模式匹配的差别模式匹配是自顶向下的推导，而表驱动可以是自顶向下的推导，也可以是自底向上的归约模式匹配一次匹配一个模版，模版集易于检查正确性，容易估计空间复杂性表驱动试图找出所有匹配的语法规则，代价高，语义动作表不容易检查正确性，大小也不容易估计,June 5,2000,下次引用信息（1）,下次不再引用意味着优化的机会寄存器优化临时名字存储单元的指派计算下次引用信息三地址语句中名字的引用定义：假定三地址语句i把a的值赋给x，如果语句j用x作为运算对象，并且控制从i流到j，这条路径中没有x的其它赋值，则称j引用x在i定的值在基本块内：下次引用

18、信息对每个基本块反向扫描为每个名字x在符号表中登记它是否在本块中有下次引用如果在本块中没有下次引用，则登记它是否在本块的出口活跃。缺省认为所有的非临时变量在出口都是活跃的,June 5,2000,下次引用信息（2）,对每一个三地址语句 i：x:=y op z，依次执行下述步骤：把当前符号表中变量x的下次引用信息和活跃信息附加到语句i上；（如果x不活跃，则这个语句可以删掉）把符号表中x的下次引用信息和活跃信息分别置为“无下次引用”和“非活跃”；把当前符号表中变量y和z的下次引用信息和活跃信息附加到语句i上；把符号表中y和z的下次引用信息均置为i，活跃信息均置为“活跃”。注意：上述次序不能颠倒，因

19、为x可能是y或z例：t:=a b u:=a c v:=t+u d:=v+u,June 5,2000,下次引用信息（3）,（1）t:=a+b（2）u:=a-c（3）v:=t+u（4）d:=v+u,名字 下次引用 活跃 t 无 非 a 无 活 b 无 活 c 无 活 d 无 活 u 无 活 v 无 活,d,u,v:无，活,无,非,4,4,活,活,u,v:4,活;t:无，非,无,非,3,活,活,3,u:3,活；a,c:无，活,无,非,2,2,活,活,a:2,活；b:无，活,无,非,1,1,活,活,t:3,活；,June 5,2000,下次引用信息（4）,临时名字的存储分配在需要临时变量时申请一个新的

20、名字是简单有效的，但浪费空间如果两个临时变量不是同时活跃的，则可以压缩在同一单元中临时变量存储单元的分配：依次检查临时变量区域的单元，找到第一个不含活跃临时变量的单元，指派给待分配的临时变量如果没有合适的单元，则在活动记录的临时变量区域中增加一个单元,June 5,2000,下次引用信息（5）,例子：t1:=a*at1:=a*at2:=a*bt2:=a*bt3:=2*t2t2:=2*t2t4:=t1+t3t1:=t1+t2t5:=b*bt2:=b*bt6:=t4+t5t1:=t1+t2,June 5,2000,一个简单的代码生成器（1）,这个代码生成器的假设条件：三地址语句的每种算符都有对应的

21、目标机器算符计算结果留在寄存器中尽可能长的时间。只有在以下两种情况才把它存入主存此寄存器要用于其它计算正好在过程调用、转移或标号语句之前在基本块的结尾，所有的寄存器都将保存，使得代码生成算法简单,June 5,2000,一个简单的代码生成器（2）,后续的代码尽可能引用变量在寄存器中的值，而不访问主存，如对a:=b+c如果b在Ri中，c在Rj中，b在此语句后不活跃，则可以为它生成代价为1的代码ADD Rj,Ri，结果a存在Ri中如果b在Ri中，c在内存单元中，b仍然不再活跃，则有：ADD c,Ri或：MOV c,RjADD Rj,Ri如果c的值以后还要用，则第二种方式更好一些，因为可以直接从寄存

22、器Rj中取得它的值由于语义的复杂性，上述代码生成可能要更为复杂,June 5,2000,一个简单的代码生成器（3）,寄存器描述和地址描述代码生成算法使用寄存器和名字的描述来跟踪寄存器的内容和名字的地址寄存器描述记住每个寄存器当前存的是什么在每个块的开始，寄存器描述显示所有寄存器为空（如果寄存器指派可以穿越块的边界，则此假设不成立）块的代码生成过程中，每个寄存器保存零个或若干个名字的值地址描述记住运行时每个名字的当前值可以在那个场所找到这个场所可以是寄存器、栈单元、内存地址或它们的集合等这些信息可以存于符号表中，在决定名字的访问方式时使用,June 5,2000,一个简单的代码生成器（4）,代码

23、生成算法输入：一个基本块的三地址语句序列输出：指令序列方法：对每个三地址语句x:=y op z完成下列动作1调用函数getreg决定存放y op z计算结果的场所L，L通常是寄存器，也可以是内存单元2查看y的地址描述，确定y值当前的一个场所y。如果y值当前既在内存单元又在寄存器中，选择寄存器作为y。如果y的值还不在L中，则产生指令MOV y,L3产生指令op z,L，其中z是z的当前场所之一（同2一样优先选择寄存器），修改x的地址描述，以表示x在场所L。如果L是寄存器，修改它的描述，以表示它含x的值4如果y和（或）z的当前值不再引用，在块的出口也不活跃，并且在寄存器中，则修改寄存器描述，以表示

24、在执行了x:=y op z后，这些寄存器分别不再含y和（或）z的值,June 5,2000,一个简单的代码生成器（5）,基本块结束的处理在基本块的出口，用MOV指令把在寄存器中的活跃变量的值保存值在寄存器中这个值在出口活跃复写语句的处理：x:=yy在寄存器中改变寄存器和地址的描述，记住x的值出现在该寄存器中如果y不再引用，且在块的出口不活跃，该寄存器不再保存y的值y的值仅在内存中若记住x的值在y的内存单元中，但如果更新y的值复杂；可以用getreg找到一个存放y的寄存器，并记住该寄存器是存放x的场所或产生指令MOV y,x，如果x在块中不再引用，此法较好,June 5,2000,一个简单的代码

25、生成器（6）,函数getreg返回保存语句x:=y op z的x值的场所L简单的实现方法：基于下次引用信息1如果名字y在寄存器中，此寄存器不含其它名字的值，并且y不活跃，且在执行x:=y op z后没有下次引用，则返回y的这个寄存器作为L21失败时，如果有的话，返回一个空闲寄存器32不成功时，如果x在块中有下次引用，或op是必须使用寄存器的算符（如变址），则找一个已被占用的寄存器R将R中的值根据存有的变量（可能不止一个）保存到内存单元中，并修改相关的地址描述R的选择要考虑spill的代价4如果x在本块中不再引用，或者找不到适当的被占用寄存器，则选择x的内存单元作为L,June 5,2000,一

26、个简单的代码生成器（7）,例子：赋值语句d:=(a b)+(a c)+(a c)可以翻译成下面的三地址代码序列t:=a b;u:=a c;v:=t+u;d:=v+ud在出口活跃，产生的代码序列：语 句生成的代码寄存器描述地址描述 寄存器空t:=a bMOV a,R0 R0含tSUB 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和内存中,June 5,2000,一个简单的代码生成器（8）,例子

27、的讨论上述代码的代价为12可以在第一个指令后增加MOV R0,R1，从而将代价减少为11（删去了MOV a,R1）,June 5,2000,一个简单的代码生成器（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),

28、R MOV b(R),Rai:=b MOV b,a(Ri)3 MOV Mi,R 5 MOV Si(A),R 5 MOV b,a(R)MOV b,a(R),June 5,2000,一个简单的代码生成器（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*

29、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),June 5,2000,一个简单的代码生成器（11）,条件语句：两种实现方式，以if x y，则CMP x,y置条件码为正等条件转移机器指令根据指定的条件（,=）是否满足来决定是否转移，如果用指令CJ=z表示如果条件码是负或零则转到z，所以有CMP x,yCJ z,June 5,2000,一个简单的代码生成器（12）,条件码的描述的记录这个描述告诉我们上次设置条件码的名字和比较的名字对x:=y+zMOV y,R0if x 0 goto zADD z,R

30、0MOV R0,xCJ z根据条件码描述可以知道，在ADD z,R0之后，条件码是由x设置的,June 5,2000,程序的依赖关系,依赖关系是什么？依赖关系表明了两个语句（或操作、计算）之间在执行顺序上存在的限制如果两个语句（或操作、计算）间存在着依赖关系，则这两个语句（或操作、计算）的执行必须满足依赖关系的要求如果两个语句（或操作、计算）间没有依赖关系，则这两个语句（或操作、计算）可以被并行执行或调整执行的顺序。依赖分析是分析语句（或操作、计算）间的依赖关系，从而确定它们是否可以并行执行依赖关系的分类数据依赖关系控制依赖关系控制流分析的结果计算的执行与否取决于控制条件是否满足,June 5

31、,2000,数据依赖关系的定义,定义：如果语句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.0S2:B=A+3.14159S3:A=1/3*(C-D)(无对A,B,C,D赋值）S4:A=(B*3.8)/1.78,June 5,2000,依赖图,以语句为节点，依赖关系为边，上例的依赖图为：,Ju

32、ne 5,2000,面向指令调度的依赖图,无环区域的依赖图是一个有向无环图G(V,E)，其中节点表示操作，边表示两个操作的执行时刻必须满足的约束。依赖边的分类流依赖、反依赖、输出依赖由访问寄存器导致的依赖 vs 由访问内存导致的依赖投机依赖边边上通常记有所需的延迟，这个延迟与操作及依赖边的类型有关伪依赖所需的延迟通常不大于1。内存取数操作的延迟通常难于在编译时刻确定。延迟的具体值由机器模型提供。,June 5,2000,依赖图的构造,构造依赖图通常可通过对基本块内的所有操作的一次或多次遍历完成，以构造流依赖边为例，算法如下：,void Build_DAG_For_BB(BB*bb)For ea

33、ch 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 o

34、ps in the list that shadowed by op.,June 5,2000,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,依赖图的例子,June 5,2000

35、,指令调度,在满足依赖关系、资源约束及硬件施加的其它约束条件的前提下，重新排定指令执行的顺序，提高资源利用率，使多个操作能够并行执行，同时减少因相关引起的处理器停顿，以缩短程序的执行时间。NP完全问题指令调度的复杂性来自于程序控制流和数据流的复杂性，以及硬件平台的复杂性。处理上述复杂性的方法：限制指令调度的范围，将流图划分为若干具有良好性质的、规模可控的区域。将机器相关部分从指令调度中分离出来。,June 5,2000,指令调度的一般步骤,构造区域(Region)构造区域上的依赖图根据依赖图进行调度代码的修正若有未调度的代码，重复上述步骤。,June 5,2000,指令调度,依据区域流图的性质

36、，可如下分类：,指令调度,Trace 调度,选择调度,Superblock/Hyperblock,SEME区域调度,无环调度,核心识别,模调度,软件流水,全局调度,局部调度,June 5,2000,局部指令调度算法表调度,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 tri

37、ed)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

38、current cycle.else commit the code motion.Update DAG,Candidate list,and Micro-Scheduler internal states,etc.,June 5,2000,就绪队列,一般而言，在某一时刻的就绪操作应满足下列条件：op在依赖图上的所有依赖前驱均已调度过。若op引用了某个操作op的结果，op于第i拍发出，且两者之间的延迟为l，则op的发出时刻不得早于i+l。若硬件有记分牌，则条件 2 可以去掉，这样在调度过程中就绪队列不会为空，但队列中的操作地位不同。给每个就绪操作加一个等待时间，每次调度总是选取等待时间最小的操

39、作。比较当前时刻与每个操作的最早开始时间。就绪队列在调度开始前计算一次，以后每调度一个操作，只需检查其在依赖图上的后继。,June 5,2000,操作的调度优先序,决定调度操作的先后顺序时使用的启发式信息：执行频率关键路径投机性所需补偿代码数量依赖图上的后继个数寄存器的使用情况是否在调度过程中动态更新上述信息需在代码质量与编译时间之间作出折中。,June 5,2000,A,B,C,D,E,F,G,E,NR,F,B,G,A,C,D a nested region as NR,全局的情形：构造区域,调度区域一般是无环的。依据流图的结构，基本块的执行频率，以及区域的预期大小等启发式信息构造。,Jun

40、e 5,2000,Trace 调度,Trace:执行过程中可能经过的一个基本块的线性序列Trace 的选择：根据分支概率及是否需要插入补偿代码等启发式规则选择执行路径，代码移动局限于该路径局部调度方法的延伸：以执行频率较低的路径上代码执行时间的增加为代价，换取频繁执行的路径上代码执行时间的缩减,June 5,2000,Trace 调度：算法,步骤：估算每个操作的执行频率挑选Trace使用某种局部指令调度方法如表调度对形成的Trace进行调度用调度完的代码替换流图中原来的Trace，必要时在Trace之外插入相应的补偿代码遍历调度后的流图并释放代码Trace 调度的问题：插入补偿代码的过程在实现

41、上复杂，且可能产生冗余在Trace 内作的一些优化，如复写传播，死代码删除等，由于split和join节点的存在而受到限制若分支概率相近，Trace 难于选择。,June 5,2000,Superblock 调度,A,B,C,F,E,D,A,B,C,F,E,D,F,Z,Z,Y,Y,尾复制,June 5,2000,Hyperblock 调度,条件执行体系结构提供64个1位的谓词寄存器(predicate registers)带有谓词的指令仅当谓词为真时改变机器状态，否则相当于一条NOP指令编译器为分支两侧的指令分配不同的谓词寄存器，由比较(cmp)指令在执行时刻为谓词赋值。条件执行可消除分支将控

42、制依赖转化为数据依赖减少由于分支预测错误带来的开销有可能增加关键路径长度,June 5,2000,寄存器分配,决定程序中哪些变量的值应该存放在寄存器中。减少访存和复写操作。最重要的编译优化之一：访问寄存器和存储器的代价相差在一个数量级以上。寄存器的数目虽已大为增加，但仍是十分稀缺的资源。许多优化的效果依赖寄存器分配的结果。寄存器分配与寄存器指派寄存器分配：决定哪些变量该占用寄存器。寄存器指派：决定变量该使用哪个寄存器。Caller-Save与Callee-Save寄存器传递参数与返回值的寄存器叶过程与非叶过程,June 5,2000,活跃区间与干涉,一个变量的活跃区间：一个变量的（极小化）活跃

43、区间是变量的定值与引用的一个子集，对于此集合中的任意定值dm和引用un，或者un在dm的du链上，或者存在一个由此集合中的定值与引用组成的交错序列dm=d0、u0、d1、u1、dk、uk=un，其中的任何一个ui、同时在di和di+1的du链上。直观上，变量的活跃区间对应于流图上联结变量的定值点和引用点的一个连通区域。干涉：两个变量的活跃区间干涉（简称两个变量干涉），若在其中某个变量的定值处，另一个变量是定值到达和活跃的。,June 5,2000,图的着色与寄存器分配,当前占统治地位的寄存器分配方法是图着色方法。图的k着色问题寄存器分配归结为图着色问题：首先构造干涉图，图中每个结点代表一个变量

44、的活跃区间，如果两个变量干涉，则在相应的结点vi和vj之间用边eij连接。假设目标机有k个寄存器可用，则寄存器分配的问题就变成对这个图找一个k着色的方案。,x=.y=.=.xz=.=y=z,y,z,x,Requires Two Colors,y,z,x,June 5,2000,干涉图的例子,x,z,y,有控制流的情形,x,y,z,需要两种颜色,June 5,2000,图着色寄存器分配Chaitins,判断一个图是否k可着色是一个NP完全问题。注意到图中度不大于k的节点总可以被着色，Chaitin提出了一种启发式方法：持续地从图中删掉度小于k的节点，若此过程一直进行到所有的节点均被删除，则图是k

45、可着色的。若此过程阻塞，即图中所有节点的度均不小于k，则依据溢出代价大小，从图中选择某个节点，删除该节点及其相连的边。然后重复上述过程。,June 5,2000,极小化活跃区间,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链包含公共的引用点，则将相应的两个活跃区间合

46、并成一个活跃区间。叠代直到活跃区间的集合稳定。,June 5,2000,极小化活跃区间,活跃区间的极小化有利于减轻变量间的干涉，减小干涉图的颜色数。,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,June 5,2000,建干涉图,Build_Interference_Graph_For_BB(block)live_var=var|var is live at the end of block;for each statements S,f

47、rom 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;,June 5,2000,计算溢出代价,最小化被溢出变量的代价值的和溢出代价：分配的优先序：代价较大的变量的优先级也较大干涉图

48、上度较大的变量的优先级较低,Cost(lr)=LOAD_COST x LoadTimes+STORE_COST x StoreTimes+MOVECOST x MoveTimes,Priority(lr)=Cost(lr)/Deg(lr),June 5,2000,图着色寄存器分配Priority-Based,Chow和Hennessy提出按活跃区间的优先级从高到低的顺序对图进行着色假定变量原本在内存中全局与局部两遍寄存器分配，GRA为LRA预留寄存器粗粒度：以基本块为分配单位优先级根据为变量分配寄存器能够减少的访存操作决定一遍着色，没有Chaitin式的先化简后回溯提出活跃区间分割（Live

49、Range Splitting），即当着色过程阻塞时，把活跃区间分成若干较小的活跃区间。这样可以产生较少的溢出,June 5,2000,寄存器分配：有谓词的情形,x,z,y,x,z,需要三个寄存器,y,(p2),(p1),(p2),(p1),June 5,2000,谓词分析,p0,p2,p1,x,y,z,P1与p2不可能同时为真,(p2),(p1),(p1),(p2),June 5,2000,考虑谓词的寄存器分配,x,z,y,根据谓词分析的结果构造干涉图,x,y,z,只需要两个寄存器,(p2),(p1),(p1),(p2),June 5,2000,指令调度和寄存器优化的时序问题,先做寄存器分配

50、，再作指令调度先做寄存器分配的优点在指令级并行度低、寄存器又少的处理机上得以体现从指令调度的观点看该顺序的最主要问题是：寄存器分配会带来反依赖和输出依赖，这将在一定程度上影响指令调度的效果先做指令调度，再作寄存器分配虽然更好的指令调度是人们所期望的，但如果代码需要的寄存器比能获得的寄存器还要多的话，则这个事实是不能令人接受的指令调度会增大寄存器分配的压力，再好的指令调度所获得的性能的提高也无法弥补由于较差的寄存器分配所带来的损失,June 5,2000,指令调度和寄存器优化的时序问题的例子,1)Val3=val1*3假设乘法指令需要4拍2)addr1=val33)Val4=val1*24)ad