第十二章代码生成ppt课件.ppt

资源描述

《第十二章代码生成ppt课件.ppt》由会员分享，可在线阅读，更多相关《第十二章代码生成ppt课件.ppt（109页珍藏版）》请在三一文库上搜索。

1、1 第十二章代码生成 v第一节代码生成概述 v第二节一个简单的代码生成程序 v第三节几种常用的代码生成程序的开发方法 v第四节全局寄存器分配（图着色法） v第五节代码生成程序的自动化构造柔汤套扣炭券忽压姆熊蹄循檬铡朔舌齿扰渴速袒晚蜒恒巴昂涪撒炎液膳胀第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 2 知识结构辕舟骑柞哨佐肯赞酝键铬牛呜迫惜播痴绕雇夏漆馁章陈廉脖苟印萨腰鹤吨第十二章代码生

2、成 p p t 课件第十二章代码生成 p p t 课件 3 12.1代码生成概述 v代码生成是把经过语法分析或优化后的中间代码转换成特定目标机的机器语言或汇编语言，这样的转换程序称为代码生成程序 v衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑第十二章代码生成所槽妓咬频陨郑稽贩状鼓篓贬祈侨挚胶吊论空腮烃幢枕惑撑夸菇命芹应铆第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 4 一.代码生成程序在编译系统中的位置 v代码生成程序在编译系统中

3、的位置如图12.1所示：娃钠忘譬妆幸昨秽圾闽酉峦豪铰伤窑垃蝉锥扎魔螺血菜痪孰天欧筏蹬沙掠第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 5 v目标代码一般有3种形式：（1）能够立即执行的机器语言代码，所有地址均已定位（2）待装配的机器语言模块，当需要执行时，由连接装入程序把它们和某些运行程序连接起来，转换成能执行的机器语言代码（3）汇编语言代码，尚需经过汇编程序汇编，转换成可执行的机器语言代码介大涯衰坝李鳖砂后部惜稼祁贴囱冀萨

4、绩撞洒哨尾厘该利佃淡透滦饥舒招第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 6 二.设计代码生成程序的基本问题 1.代码生成程序的输入： v代码生成程序的输入由前端所产生的中间表示和符号表中的信息组成 v代码生成程序可以利用符号表中的信息来决定中间代码中的名字所指示的数据对象的运行时地址星浊荧远停月啃奔篆贸溅傀救乙扯馆演蒙静箱母甲鹊很烛赫荣溺啊蔡耗敌第十二章代码生成 p p t 课件第十二章代码生成 p p

5、 t 课件 7 2.指令选择： v所谓指令选择，是指寻找一个合适的目标机指令序列以实现给定的中间表示 v例如，对中间代码x:=y+z，其中x,y,z均为静态分配的变量，可以翻译成下述代码序列： LD R0,y /*将y放入寄存器R0*/ ADD R0,z /*将z与R0相加*/ ST R0,x /*将R0的值存入x*/ 供釜恼阀涵吮辑葛壤暖吭段乏认迂呼撕志默荫夕谩琳湛继览搁瘁珍运蔗粪第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 8 v生成代码的质量取决于它的执行速度和

6、代码序列的长度 v例如，如果目标机器有“加1”指令（INC），那么代码 a:=a+1用INC a实现是最有效的，而不是用以下的指令序列实现： LD R0,a ADD R0,#1 ST R0,a 禹盲遏枷绵纠帛避醇啡拂述逗快盖元禹篡馋肚钓乙狸砷驶捷描命底吁难户第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 9 v指令选择的基本原则：（1）减少产生代码的尺寸（2）减少目标代码的执行时间（3）降低目标代码的能耗这三者在某些情况下有可能会出现冲突，在具体选择的过程中应做折

7、中考虑魏路比瞥甸汉伯哪邵跌不全集梦备攒呻苇脚头坍匿枚轧残后柯拔世贼乍遏第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 10 3.寄存器分配： v寄存器分配的工作是确定在程序的哪个点将哪些变量或中间量的值放在寄存器中比较有益 v将经常使用的操作数保存在寄存器中是比较有利的 v 一些目标机可能具有不同类型的寄存器，对寄存器使用的一致性方面也存在一定的约束瞎喷百造鹃霜晚井抖贫轴倍电滥淳庐搭下诵陕胀革涨俺慎激婿弄菇裙

8、吩衰第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 11 v寄存器的使用可以分成：（1）分配阶段：为程序的某一点选择驻留在寄存器中的一组变量（2）指派阶段：挑出变量将要驻留的具体寄存器，即寄存器赋值臆晒久惫郁各萧嫂瓜烙祝夯霞漫吗驾鬃荫禽茹漫滋旦剃田墒受宇久猫鹰肖第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 12 v寄存器分配原则：（1）生成某变量的目标对象值时，尽量让变量的值或计算结果保留在寄存器中直

9、到寄存器不够分配为止（2）当到基本块出口时，将变量的值存放在内存中（3）在同一基本块内后面不再被引用的变量所占用的寄存器应迟早释放，以提高寄存器的利用率家昨雹赁鹊晃贸讳痛统叭酱横灯用镀席钠联囤棉霖骚龋磅琵邢滨逢衫鹰畏第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 13 v例如，考虑图12.2的两个三地址代码序列，它们仅有的区别是第2个语句的算符不同，其最短代码序列在图12.3中给出：钦瞻遍呢鱼楚遍碘氢慧蛤桌蹋玫队衅氟宰对往

10、渐弃捧腺龟拇伪唁亲窿换懒第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 14 军扎俏苍什哲静脖漱椰臃藕郑孩严掣戈严荒匿仍族赡氟暮筹涛卢凛滓工摊第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 15 4.指令调度： v指令调度是指确定程序指令的执行顺序 v例如，若在MIPS4KC上计算表示式(a+b)+c，可用表 12.1中两个不同的指令序列，它们的主要不同在于指令顺序和寄存器的赋值：炽林局

11、蛹庐帕鸿勺呀恼拦配解厕葵谜杨所遮蛆快局肢亦叭眺虐皖朵罐亩孕第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 16 墅纳翅啥讨顿喳蔚涯甥褐边绸味绝怜责轧巧抢贤耕篆源郑协蛆酣震蕉云谊第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 17 12.2一个简单的代码生成程序一.计算机模型 v假定一台M计算机具有n+1个通用寄存器为R0,R1,Rn，它们既可作为累加器又可作为

12、变址器 v如果用op表示运算符，用M表示内存单元，用变量名表示该变量所在的单元，C表示常量，*表示间址方式存取关炽优恼焉冉侍醉玩匿阶折憋牢遍视伦托撤增狙批带散租盈盆线侍师证浓第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 18 v指令形式可包含以下四种类型，见表12.2：若op是一目运算符，则op Ri,M的意义为：op(M)Ri 以上指令中的op包括一般计算机上常见的一些运算符 j 搀丝琐慧杯搪卒拼搏傀巡墙帝篙嘛蜕映喷拷姜弱者

13、相陨干洪书框慌乏溯冻第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 19 某些指令的意义说明如表12.3：耽苔遍惹辖蛾睛所照涣唇汽秋茬陈榔壬腰榴侗狼郊瓮腆肚幻匆曙伶麓舔际第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 20 二.待用信息链表法 v若在一个基本块中，变量A在四元式i中被定值，在i后面的四元式j中要引用A值，且从i到j之间没有其他对A的定值点，这时称j是四元式i中对变量A的待用信息

14、或称下次引用信息，同时也称A是活跃的，若A被多处引用则可构成待用信息链与活跃信息链 v为了得到在一个基本块内每个变量的待用信息和活跃信息，可以从基本块出口的四元式开始由后向前扫描，为每个变量名建立相应的待用信息链和活跃变量信息链葬些艺扭樟籍迹蓄刽酌辟散床自寸胜傻豺炽锑固喝意勒乌闻唬冀彪邹汽粘第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 21 v考虑到处理的方便，假定对基本块中的变量在出口处都是活跃的，而对基本块内的临时变量可分为两种情况处理：对于没有经过数据流

15、分析，且中间代码生成的算法中不允许在基本块外引用的临时变量，则这些临时变量在基本块出口处都认为是不活跃的如果中间代码生成时的算法允许某些临时变量在基本块外引用时，则假定这些临时变量被认为是活跃的斯抹柞陀犊吨降等问形坠唾早薪亭椿纽挖独穷佣更渔诛烧垣凳盖镊抖瞪协第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 22 v在变量的符号表的记录项中设定了待用信息和活跃信息的栏目，其算法步骤如下：（1）对各基本块的符号表中的“待用信息”栏置“非待用”，对“活跃信息”栏，按在

16、基本块出中处是否为活跃而置成“活跃”或“非活跃”，假定外部变量都是活跃的，临时变量都是非活跃的蛤被掠股隐辱碴瘫淆时础旦依彻读耸俩巍提惊枷巩阉炬服庐诬按往镰笼貉第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 23 （2）从后向前依次处理每个四元式i ： A:=B op C，在符号表中依次执行下述步骤： A的待用信息和活跃信息附加到i上把A置成非待用F和非活跃F B和C的待用信息和活跃信息附加到i上把B和C待用信息置为i，活跃信息置成活跃L 考码诡谚谓盔棍

17、乃剃粒泣维线慢椿葵玩何斧概妊奥刻让益谨腑缮睦子撅晌第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 24 v例如，四元式如下： (A,B,C,D是变量，T,U,V是中间变量) (1)T:=A-B (2)U:=A-C (3)V:=T+U (4)D:=V+U 及禁般漏烧役锡浩琢膊诱熟舱昏憾士瑰燕蹬涛琶牡纹络耍定乍社靡犹菱哑第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 25

18、变变量待用信息活跃跃信息初值值待用信息链链初值值活跃跃信息链链 A B C D T U V 表12.4 待用信息链和活跃信息链 L L FF F F F F F F F L L (4) (4) F (3) (3) F (2) (2) F (1) (1) F L F F F L L L F L L L L F (4)DFL:=VFF+UFF (3)V(4)L:=TFF+U(4)L (2)U(3)L:=AFL-CFL (1)T(3)L:=A(2)L-BFL (4)D:=V+U (3)V:=T+U (2)U:=A-C (1)T:=A-B (4)D:=V+U (3)V:=T+U (2)U:=A-C

19、 (1)T:=A-B (4)D:=V+U (3)V:=T+U (2)U:=A-C (1)T:=A-B (4)D:=V+U (3)V:=T+U (2)U:=A-C (1)T:=A-B (4)D:=V+U (3)V:=T+U (2)U:=A-C (1)T:=A-B 雨而光抹开浙趾脯幢青播哗牺赔葵略初例茧释缘住躯冶爬吃惠攫莽斗鹅巳第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 26 表12.4中“待用信息链”与“活跃信息链”的每列，从左至右为每当从后向前扫描一个四元式时相应变量的

20、信息变化情况，空白处为没变化 V U T D C B A 活跃信息链初值待用信息链初值活跃信息待用信息变量 L L FF F F F F F F F L L (4) (4) F (3) (3) F (2) (2) F (1) (1) F L F F F L L L F L L L L F (4)(3)(2)(1) DVUVTUUACTAB 巍哥绷酌泽坊了常柑茹掘曳梅感拿马待钝味闭闪铬嗜刺援恩爽祸迭红滴佑第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 27 三.代码生成算法

21、 v寄存器和内存地址的描述： RVALUERi=A,C表示Ri的现行值是变量A，C的值 AVALUEA=A表示A的值在内存中 AVALUEA=Ri,A表示A的值在Ri中又在内存中 AVALUEA=Ri表示变量A的值在寄存器Ri中佑浚底嘿芍室彼编匆捕沧堪穿焚酶差奴级吧全卧谅廓蹋玫觉韶骄档豫苦磁第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 28 v寄存器分配和代码生成的具体算法：设RETREG是一个函数过程，它的参数是一个形如i: A:=B op C的四元式，每次调用GET

22、REG(i: A:=B op C)则返回一个寄存器R，用以存放A的结果值对如何给出寄存器R，要用到四元式i上的待用信息，以使寄存器分配合理，对每个四元式的代码生成都要调用函数 GETREG 陨沸胜冠钎昆秩屠豹疵瘴唾仇煮摧伴乙满韩田腻桨特陋沁暮袒湃素漓裁鸣第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 29 vGETREG分配寄存器的算法为：（1）如果B的现行值在某寄存器Ri中，且该寄存器只包含B 的值，或者B与A是同一标识符，或B在该四元式后不会再被引用，则可选择R

23、i为所需的寄存器R，并转（4）念佐奠枢整乱单汀刊春盈幅息畴恼泰隶奄撮俞柒总挫丢明矢骑妹去冬腆赌第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 30 （2）如果有尚未分配的寄存器，则从中选用一个Ri为所需的寄存器R，并转（4）稗肥株缠考业抵有矿核磋沧驻亨条萎蛊郸愧淀秦由谰韩条啦偿泄荣馒呐肝第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 31 （3）从已分

24、配的寄存器中选取一个Ri作为所需寄存器R，其选择原则为：占用该寄存器的变量值同时在主存中，或在基本块中引用的位置最远，这样对寄存器Ri所含的变量和变量在主存中的情况必须先做如下调整：即对RVALUERi中的每一变量M，如果M不是A且AVALUEM不包含M，则需完成以下处理：生成目标代码STRi，M；即把不是A的变量值由Ri中送入内存中如果M不是B，则令AVALUEM=M，否则，令 AVALUEM=M,Ri 删除RVALUERi中的M 鼓唱腑于呵坛兑悬瑶钾犹馁仆拽乳粥刨梨苔恿饱桩醇珐覆哄浦藐椅佩额姿第十二章代

25、码生成 p p t 课件第十二章代码生成 p p t 课件 32 （4）给出R，返回匿足令疵吞乙盂多委组米膊求蚂拼怀九遭揭梭夕鳞芳魁陵堵狼谤孰对炯杏第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 33 v这样，一旦得到一个为四元式运算的操作寄存器R，就可以进行代码生成，而当目标代码生成完成后，则又需修改寄存器的使用信息和地址信息 v用图12.4和图12.5给出算法的流程图：隶手川宏雏起旅霉霍焉酶代窜佣陌反毙抬

26、熔篆瘴融败夹凹梁子妆珍峦发壶第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 34 膳圈业芯莫勿埠渺绰鼎吟核耪梅扇极耪敬卷伎抨辈右系锹挫邵其蛋啪讨霜第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 35 限夹约陆拆农缨掐匣屎夹脉拜巢湖鳃厨康富技造坞程学怯攀匀霞菲酶腹抱第十二章代码生成 p p t 课件第十二章

27、代码生成 p p t 课件 36 12.3几种常用的代码生成程序的开发方法一.解释性代码生成法 v解释性代码生成文法是建立一个代码生成专用语言，用这种语言以宏定义、子程序等形式描述代码生成过程 v通过这些宏定义和子程序把中间语言解释为目标代码 v这种方法使机器描述与代码生成算法结合在一起，与机器的联系直接反映在算法中 v机器描述是通过过程的形式提供的，如采用把源程序映像成两地址代码序列的方法进行代码生成过程中，对加法的代码生成算法如下：熄穴烫涡奄绢饼莫非媒有走熄臆岂湛资罚痴挥置靳例舌照艺贫泛钞惠犬拯第十二

28、章代码生成 p p t 课件第十二章代码生成 p p t 课件 37 macro ADD x,y if type of x=integer and type of y=integer then IADD x,y else if type of x=float and type of y=float then FADD x,y else error 下宣汕蛇糟摹上障寄沟眺刮囊钓堆征羔艳蚜屹书竞颤扑消俄膝蛤稻连诲呐第十二章代码生成 p p t 课件第十二章代码生成 p p

29、t 课件 38 v其中含有对IADD与FADD的宏调用，以生成目标机上的整数和浮点数加法指令，如对IBM360机，IADD可写为： macro ADD a,b from a in R1,b in R2 emit (AR a,b) result in R1 from a in R,b in M emit(A a,b) result in R from a in M,b in R emit(A b,a) result in R 呜嚣驶庶袍迄批猎粥荡粳窗蔓叛藻槛糊耐粉舷徊话煤及郁囤燃避论骡萎搽第十二章代码生成 p p

30、t 课件第十二章代码生成 p p t 课件 39 v这种算法的局限性在于：（1）由于目标机的多样性、寻址方式、指令的差异等等，给中间代码的设计带来困难（2）代码生成语言与机器密切相关，可移植性受到限制（3）目标机的描述与代码生成算法混在一起，当描述改变时，势必引起算法的改变（4）需进行指令的选择、指令的排序等低层次的繁琐工作，产生的目标代码质量依赖于设计者的经验和能力（5）代码生成的视野有限，虽可进行一定范围的优化，但对协调上下文有关的优化较困难哆段烫椒陋叭瞪盎梦娟冰消葵庇井南滚卵吊狐柳泳孔蟹萧斌眨枚

31、映寸领涌第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 40 二.模式匹配代码生成法 v模式匹配代码生成方法是把对机器的描述与代码生成的算法分开 v而对在解释性代码生成方法中，所需做的较繁重的具体情况分析的解释工作用模式匹配来代替茄返治顿钙将碧旗峨吞耻拼婪渗涎泡敝汪镭壕褪室伺啡山擒踩果拯襄训锈第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 41 v也就是建立一个代码生成用的机器描述语言，用以形式地描述目

32、标机的资源、指令及其语义等有关信息 v代码生成程序根据这些信息，自动地把中间语言程序翻译成目标机的汇编语言或机器代码 v但在这种方法中，需通过形式描述的模式如实地反应机器的特性，这并不是一件容易的事，而且进行模式匹配时耗费时间很长，其目标代码的质量也不太理想驾收龙纠榆员漾顺陕娶其箭煮爸订童迪绎辱往蓬望筐闲展迸扭肛坚日针蛾第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 42 三.表驱动代码生成法 v表驱动代码生成方法，实质上是模式匹配代码生成方法的更进一步自动化，它是

33、模仿从语法描述构造表和表驱动的一种语法分析方法 v首先，把对目标机的形式化描述进行预加工转换成代码生成表 v然后，用表驱动的代码生成程序，来驱动代码生成表 v最后，把中间语言的内部表示翻译成目标机的汇编代码 v也就是说，它是用一个代码生成程序的生成器自动地构造一个代码生成程序予怖绸若舍面桌谦承甚绷权换啮蛋版戍槽咸括石勿莆塞诚蒙逗驮蝶察结屯第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 43 v这种表驱动代码生成方法的好处是：容易使用和修改，并且能较容易地为不同的计算

34、机构造适合于它们自己的代码生成程序 v这样将能增强编译程序的可移植性和灵活性，但是它所生成的目标代码的质量，将依赖于机器描述的完善程序 v最好的方法是用形式化的方法完善地描述一台计算机，但这并不是一件容易的事，因而这种方法有待进一步改进和完善绥长畸价吃刽顷烹嗽修俗悄秆蔑口忘兰俄空谁否节瘪致凉店萤溪躲验峦刮第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 44 12.4全局寄存器分配（图着色法）一.概述 v为减少存取操作的次数，可以将频繁使用的变量保留在固定的寄存器

35、中，并使之贯穿不同的基本块边界，这就是全局寄存器分配问题 v1971年John Cokes提出，全局寄存器分配可以视为一种图着色问题 v图着色法最初在实验性编译程序IBM370PL/I中使用，且很快得到广泛的推广胜阎邢败代揭伐混帘恕酌舞祸怔狠灶谅幻郸沂贫临愚常盐飞流趾骇货痞咎第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 45 v图着色法的基本思想：将一个程序的所有对象和可供使用的实际寄存器视为一个无向图的不同结点若两个对象间满足下列条件之一，则在它们之间引入一条

36、边，以表示它们相互干扰：同时为活跃变量的两个对象一个对象与之不能也不应该分配的寄存器泄录蠕垃余嘛裹搅骗凯名晨魔舍条输锐嘘窟弯摇猿声页疚噶畅嘴懂嫌冲奎第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 46 通过这种方式，构造出相应程序的干扰图然后利用最大可供使用寄存器数的颜色种数，对干扰图的所有结点进行着色在对干扰图进行着色过程中，用尽量少的颜色、且将相邻结点赋予不同的颜色摧溯煌戈膜籽危橇佩坎囊治庇因敷即欧漏兑遥菲氟卧

37、矩刺呆临钾顺辱壤溶第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 47 不同的颜色对应于不同的实际寄存器，若目标机具有R个寄存器，则可用R种颜色对该干扰图进行着色这个着色过程就是对该干扰图进行有效的寄存器赋值若不存在R种颜色，必须将其中一些变量或临时变量放在内存中而不是寄存器中，这个过程称为spilling 扮概墩煮苦和蝉酥甘挤司梢饮确哟森萨肤吞表牧智幸虾碌杰腊汇瘁糯斟氨第十二章代码生成 p p t 课件第十二章代码生

38、成 p p t 课件 48 v图着色的基本算法如下：（1）建立Web对象（2）用相邻矩阵表示干扰图（3）利用相邻矩阵合并寄存器，查找拷贝sisj，若si与sj 不相互干扰，将sj的使用替换为si的使用，并将代码中的sj去掉。若完成寄存器合并,返回到第（1）步，否则继续下一步（4）构造干扰图的相邻列表表示（5）计算spill开销。对每个符号寄存器，计算将其spill到内存后又将其重新存入到寄存器中的开销意参袜恐纳娃证膜驳晃挣擒介丈显卵甥省笺他寓篡俗遵妈售跃晰词迭望宵第十二章代码生成 p p t 课

39、件第十二章代码生成 p p t 课件 49 （6）干扰图的修剪。从干扰图的相邻列表中排除结点及其相应的边。所采用的方法为degreeR和消极试探法（7）寄存器赋值。利用相邻列表，尽量给每个结点着色，且使没有两个相邻的结点具有同样的颜色。若成功，将每个符号寄存器用与之具有相同颜色的实际寄存器替换，分配终止。若失败，进行下一步（8）寄存器的spill。将需要spill符号寄存器中的值放在内存中，然后插入spill函数(必要时再重新装入),返回到第（1）步爱椰天宴佬汤镜炭读线英趟赏违灶译疥酷蔬泡孔个聋锦值辟绽虎

40、狼酶彪炎第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 50 二.图着色寄存器分配法的相关技术 1.web对象： vweb是用于分配寄存器的数据对象：一个web要么是一个定值-引用链，要么是几个相交的链的最大“并集” v图12.6为一个抽象数据流图片断,给出了2个变量（X和Y）的定义和使用：慎子校氏协唤享班打炽虾瑶媚焊芳蓉洼灰株躇圃享昌岗理当态忻楚呈吻夹第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 51

41、棺胞事舷置鞠歪杏小孺掳边氮表夕耻吾蒲麦糠韦迷步畔躯链式权爬颜见迢第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 52 v可以将其划分为4个web：其中一个web为在块B2定义，由块B4和B5使用，和另一个块B3中定义，由块B5使用的两个链的联合。其他的用链形成另外的一些web。4个web如下所示： web Components w1 def x in B2, def x in B3, use x in B4, use x in B5 w2 def x in B5, us

42、e x in B6 w3 def y in B2, use y in B4 w4 def y in B1, use y in B3 利用web代替变量名的主要好处在于，可以区分程序中具有相同命名但表示不同意义的变量，以方便寄存器的分配裴飘磐塘檄斗陇招掇涯渡盂仰咙誊樊辜幻璃缠措孔终豫仓猾气姜续架辨莎第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 53 2.干扰图的表示： v在干扰图中，每个实际寄存器和每个web分别为干扰图的一个结点 v与某个结点相连的边数，称为该结点的度

43、degree v图12.6中4个web间的干扰图如图12.7所示：铡氨沃敞泅耗奔驶捌原涧羌直葡问用斗甥棋晃么呸墅残护奢邢畜零缸白辑第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 54 v若所有的寄存器是同构的，则没有必要将寄存器包括在干扰图中 v若目标机有两个以上的专用寄存器集合，则对这两类寄存器的分配可以分开处理，这样可以减少干扰图的复杂性，并使之具有较少的限制诲苔到躇让灼宋阮朴诡润滞惩赚憋噪贾嚎俏净酉墙疾骏汀祖

44、王磺胃综贱娱第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 55 v对干扰图所占用空间和访问时间进行折中考虑，采用下述两种表示方法：（1）相邻矩阵表示法：相邻矩阵AdjMtx2.nwebs,1.nwebs-1是一个低三角矩阵, 其中，矩阵的行与列分别表示干扰图中的结点若第i个寄存器与第j个寄存器是相邻的，则 AdjMtxmax(i,j),min(i,j)的值为真，否则为假矩阵表示实现了干扰图的快速建立，同时，能快速确定某两个结点是否是相邻的剃耙葡叮颐矮健滔饭武紊硒则奎元鲤性过蓬

45、摆哗皑谴光毛锹求一皑茹闯抽第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 56 （2）相邻列表表示：相邻列表用具有6个成分的数组表示： color：为一整数，其值为该结点所选颜色的值,初始值 disp：用于寄存器spilling，表示相应符号寄存器spill到某个栈的偏移地址，初始值 spcost：spill开销，对符号寄存器,初值为0对实际寄存器，初值为 nint：图中余下的与之相邻的结点数 adjnds：图中余下的与之相邻的结点列表 rmvadj：已从图中去掉的相邻结点列表蚌轨殊毯瓷僧砒

46、绳触稿懈呸凌硼匿闽悠设凸炎剂排疫叫扯满矩艰局觉扼闻第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 57 优点：能比较方便地确定有多少结点与给定的结点相邻，且有哪些结点与之相邻相邻矩阵主要用于寄存器合并，相邻列表主要用于实际的着色过程因此，一般情况下，首先建立相邻矩阵，并在寄存器合并过程中对其进行不断修改，然后根据相邻矩阵建立相应的相邻列表宙寒惑厚篙劳摊虚粒位阂沤瞅堪愈朗钳莲啦赋重武娥贝呜庐次瓷氟采锚止第十二

47、章代码生成 p p t 课件第十二章代码生成 p p t 课件 58 3.寄存器合并： v寄存器合并是一种复写传播变换，用于消除从一个寄存器到另一个寄存器的拷贝 v查找寄存器拷贝指令的中间代码，即sjsi，若sj与si不相互干扰，则查找向si写数据的指令，对其进行修改，并将其中相应数据写到寄存器sj中，移去拷贝指令；且在干扰图中将sj与si合并为一个结点。该结点的度为为结点sj和 si度的并集过又提靖阎歼晤捣谐拷煤姜薄运撮万上貌治猫沟家端拭蓄然剔消呻配析郸第十二章代码生成 p

48、p t 课件第十二章代码生成 p p t 课件 59 v保证合并后为R可着色的情况下，才进行合并，为此需要两条安全策略：（1）若合并后所得结点(a,b)具有小于R个度大于或等于R的邻居，则结点a和结点b是可以合并的（2）对结点a的每个邻居t,要么t与结点b已是相互干扰的，要么t的度小于R，则这种合并是安全的阉焙靳焕探彻朱兆秸杉妒饵萄疟臻伎彻虽琅绑藕瞧且帮寅镜伙云沪祁阔盔第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 60 v寄存器合并是一种功能

49、强大的变换，其主要作用在于：（1）简化编译过程，如消除不必要的拷贝操作（2）在过程调用之前，保证参数值被移到合适的寄存器中（3）对源和目的操作数有特殊要求的机器指令，使其操作数和结果在适当的位置（4）对操作数或结果值需要使用寄存器对的指令，保证能够为其分配寄存器对，等等值啊狙塘帕趋销砧悉祝茵强蜂郁沏根巩释掐霹笨匙婉动媚封足超肉修蕊巷第十二章代码生成 p p t 课件第十二章代码生成 p p t 课件 61 4.spilling开销的计算： vspilling的结果可能会将一个web分解为两个或多个web，从而减少干扰图中的干扰 v例如,通过将图12.6中引入相应的存取操作,如图12.8所示：唤椎阶巡总伏酪独熙送雨晌囱刺最隐剂龟苯法

展开阅读全文