（计算机科学与技术专业论文）嵌入式处理器编译器关键技术研究.pdf

围防科学技术大学研究牛院学位论文 摘要 嵌入式系统通常对性能、实时性、功耗等有着严格的要求，需要非常高效的机器 代码。因此，嵌入式软件开发常采用汇编语言。但汇编语言编程费时、调试困难，而 且代码难以移植。嵌入式系统的广泛应用和嵌入式软件规模的不断扩大，决定了用高 级语言代替汇编语言进行嵌入式软件开发是必然趋势。但使用高级语言编译器生成 代码的质量和手工编写的汇编代码相比还有很大差距，不能满足嵌入式系统的要求。 因此，嵌入式处理器编译技术研究有着非常重要的现实意义。 传统编译技术通常不能直接适用于嵌入式领域，需要进行扩展或者设计全新的算 法。传统的编译技术一般基于规则的机器模型，并采用简单启发式方法以达到较快的 编译速度。嵌入式处理器一般具有不规则的体系结构特征，且在嵌入式环境中，编译 器生成高质量代码的重要性高于编译时间。 本文主要研究了嵌入式处理器编译技术的三个问题：嵌入式处理器寄存器分配、 多媒体扩展指令集的代码生成、双指令集处理器多目标代码选择。 在传统图着色寄存器分配方法中，假设机器模型具有简单的寄存器文件。这些算 法采用“d e g r e e 后”测试冲突图结点是否局部可着色，并通过特殊的技巧对此扩展， 以适用于不规则的寄存器文件特征。经过多年研究，此问题取得了很大进展。但是， 传统图着色寄存器分配算法在进行冲突图结点局部可着色测试时，无法知道邻居结 点所分配的颜色，只能采取保守的估算，因而降低了编译生成的代码质量。这是它们 难以克服的困难。 传统树模式匹配和动态规划技术不能有效利用多媒体处理器的指令集并行， 基于传统并行编译技术的扩展一般局限于循环级并行，且没有全局优化标量指令 和s i m d 指令的使用。 传统编译技术一般仅优化单一的目标，例如性能、功耗。嵌入式系统常需同时优 化多个目标。单一目标的优化对其它目标有何影响，如何在多个目标间权衡，需要进 一步研究。 嵌入式系统的复杂性决定了需要采用新的方法学来研究嵌入式编译技术。从元 启发式算法以及编译器前后端有机结合这两个角度来研究嵌入式编译技术是本文工 作的重要思想。 近二十年来，元启发式( m e t a - h e u r i s t i c s ) 算法得到广泛研究。这些算法来自于人们 从自然界得到的启发，通过模拟物理过程、生物进化等自然现象，能够克服经典优化 算法的局限性，系统地搜索问题的解空间，较好地解决多种优化问题。编译技术中同 样存在各种优化问题，尤其在嵌入式环境中，这些问题更加复杂，常使得传统编译技 同防科学技术大学研究牛院学位论文 术不能简单地适用。元启发式算法为求解复杂的编译优化问题提供了广阔空间。 程序分析是编译优化的基础。可以把编译器前端程序分析的优势和编译器后端 的机器相关信息结合起来，以适应复杂的嵌入式环境下编译技术研究的需要。 本文主要研究成果和创新包括以下几个方面： 1 针对嵌入式处理器不规则寄存器文件体系结构特征，本文提出了一种新的图着 色寄存器分配混合演化算法h m a g r a ，突破了传统图着色寄存器分配算法在寄 存器冲突图结点局部可着色测试问题上难以克服的障碍，为实现嵌入式处理器 寄存器分配器提供了新途径。 本文的h m a g r a 算法主要由遗传算法和禁忌搜索算法构成，利用c h a i t i n 算法作 为前端对冲突图进行预处理，对剩余冲突图中各结点按照其类型随机分配颜色， 计算结点间的冲突数量，通过演化过程逐渐减少图的总体冲突，最终实现图成功 着色。此算法不仅可以精确计算冲突图结点是否局部可着色，而且能够用规范的 寄存器分配模型代替传统算法中的特殊技巧，以适应嵌入式处理器寄存器文件 不规则特征带来的复杂性。 2 面向多媒体指令集，本文提出了一种新的s i m d 代码生成算法i c g m e 。 i c g m e 算法扩展了传统的树模式匹配和动态规划技术，通过修改代码生成器的 产生器i b u r g i 具为数据流树结点的每个目标非终结符保留多个匹配规则，以识 别构造s i m d $ 旨令的并行操作；在编译器前端对存储操作相对于向量寄存器的对 齐状况进行数据流分析，并把分析结果传递给编译器后端，以辅助构造s i m d 矛u 数据重组指令；最终生成多媒体向量指令和非多媒体标量指令混合的汇编代码。 通过结合编译器前端程序分析的优势和编译器后端的机器信息，i c g m e 算法不 仅简化了s i m d 代码的生成，而且能够同时利用s i m d 指令和非s i m d 指令，以生成 高质量的机器代码。 3 以a r m t h u m b 双指令集处理器为例，本文提出了用元启发式算法求解编译技术 中多目标优化问题的方法学。 本文把双指令集处理器代码选择问题表示为权衡程序代码大小和运行时间的多 目标优化问题，利用程序p r o f i l i n g 技术为其建立数学模型，通过一种多目标蚁群 算法结合子集选择的方法求解此问题。 4 基于s u i f m a c h i n e s u i f 编译器研究框架，我们进一步完善了代码选择、寄存器分 配和程序分析的实验环境。 我们实现了多种传统的图着色寄存器分配算法和元启发式图着色寄存器分配算 法h m a g r a ，实现了多媒体代码生成算法i c g m e 和部分程序分析模块，实现了 针对多目标代码生成的蚁群优化算法m o a r m a n t s s 。 国防科学技术大学研究生院学位论文 嵌入式处理器编译技术需要扩展传统的编译技术或者设计全新的算法。本文分 析了传统编译技术在嵌入式环境中遇到的关键问题，并以元启发式算法和编译器前 后端有机结合的方为基础，研究了嵌入式编译技术的三个问题：嵌入式处理器寄存 器分配、多媒体扩展指令集的代码生成、双指令集处理器多目标代码选择。实验结果 表明了这些方法的有效性。本文把元启发式算法用于嵌入式编译技术的研究与实现 尚处于初步阶段。元启发式算法从新的角度为研究嵌入式编译技术提供了广阔空间。 关键词：编译技术，嵌入式处理器，元启发式算法，寄存器分配，代 码生成，多媒体指令，多目标优化 围防科学技术大学研究牛院学位论文 a b s t r a c t t om e e tv a r i o u sr e q u i r e m e n t sl i k ep e r f o r m a n c e ，p o w e r ，a n dr e a l - t i m er e s p o n s et oe x t e r n a l e v e n t s ，e m b e d d e ds y s t e m sn e e dh i g h l ye f f i c i e n tm a c h i n ec o d e t h e r e b ya s s e m b l yl a n g u a g e i sa l w a y sw i d e l yu s e di ne m b e d d e dp r o g r a m m i n g h o w e v e r ，t i m e - c o n s u m i n gp r o g r a m m i n g ， v e x i n gd e b u g g i n g ，a n dp o o rc o d ep o r t a b i l i t yo fa s s e m b l yp r o g r a m m i n ga r en o tn e g l e c t a b l e w i t ht h ee x t e n s i o no fa p p l i c a t i o na r e ao fe m b e d d e ds y s t e m sa n dt h ee v e r - g r o w i n go ft h es i z e o fe m b e d d e ds o f t w a r e ，a s s e m b l yl a n g u a g ew i l lb ei n e v i t a b l yr e p l a c e db yh i g hl e v e ll a n g u a g e i ne m b e d d e ds o f t w a r ed e v e l o p m e n t b u tc o m p a r e dt om a n u a l l yw r i t t e na s s e m b l yc o d e ，t h e c o d eg e n e r a t e db yh i g hl e v e ll a n g u a g ec o m p i l e r si so f t e nm u c hw o r s ea n dc a n n o tm e e tt h e r e q u i r e m e n t s s oi ti sv e r yi m p o r t a n tt os t u d y t h ec o m p i l e rt e c h n i q u e sf o re m b e d d e ds y s t e m s t r a d i t i o n a lc o m p i l e rt e c h n i q u e sa r eu s u a l l yn o ta p p l i c a b l et ot h ee m b e d d e dd o m a i nd i - r e c t l y , w h i c hn e e dt ob ee x t e n d e d m o r e o v e r ，s o m ec o m p l e t e l yd i s t i n c ta l g o r i t h m sa r ee x - p e c t e ds o m e t i m e s t h er e a s o ni st h a tt r a d i t i o n a lc o m p i l e rt e c h n i q u e sa r eu s u a l l yb a s e do n r e g u l a rm a c h i n em o d e l s ，a n da p p l ys i m p l eh e u r i s t i c st og e t r e s u l t sr a p i d l y ；h o w e v e r ，e m b e d d e d p r o c e s s o r so f t e nh a v ei r r e g u l a ra r c h i t e c t u r a lc h a r a c t e r i s t i c s a d d i t i o n a l l y , i nt h ee m b e d d e d d o m a i n ，t h ei m p o r t a n c eo fh i g hq u a l i t yc o d eo u t w e i g h st h a to fs h o r tc o m p i l a t i o nt i m e t h i st h e s i sm a i n l yf o c u s e so nt h r e ep r o b l e m so fc o m p i l e rt e c h n i q u e sf o re m b e d d e ds y s - t e m s ：r e g i s t e ra l l o c a t i o nf o re m b e d d e dp r o c e s s o r s ，c o d eg e n e r a t i o nf o rm u l t i m e d i ai n s t r u c t i o n s e te x t e n s i o n ，a n dc o d es e l e c t i o nf o rd u a li n s t r u c t i o ns e tp r o c e s s o r s t r a d i t i o n a lg r a p h c o l o r i n gr e g i s t e ra l l o c a t i o na l g o r i t h m sa r eb a s e do no v e r - s i m p l i f i e dr e g - i s t e rf i l e so fm a c h i n em o d e l s w h i c ha p p l yt h er u l eo f “d e g r e e k t ot e s tt h el o c a lc o l o r a b i l i t y o fi n t e r f e r e n c eg r a p h sa n de x t e n dt h i sr u l eb ya dh o cs k i l l st oi r r e g u l a rr e g i s t e rf i l ec h a r a c t e r i s t i c s s i g n i f i c a n tp r o g r e s sh a sb e e nm a d eo nt h i sp r o b l e mt h r o u g hy e a r so fe f f o r t so f c o m p i l e rr e s e a r c h e r s b u tw h e nt e s t i n gt h el o c a lc o l o r a b i l i t yo fi n t e r f e r e n c eg r a p h s ，t r a - d i t i o n a lg r a p h - c o l o r i n gr e g i s t e ra l l o c a t i o na l g o r i t h m sc a n n o tg e tt h ec o l o r so fi t sn e i g h b o r n o d e s ，c o n s e q u e n t l y , t h e ym a k ec o n s e r v a t i v ee s t i m a t i o n so ft h e m s i n c et r a d i t i o n a lt r e ep a t t e r nm a t c h i n ga n dd y n a m i cp r o g r a m m i n gc a n n o te x p l o i te f - f i c i e n t l yi n s t r u c t i o n l e v e lp a r a l l e l i s m ，t h ee x t e n s i o nb a s e do nt r a d i t i o n a lp a r a l l e lc o m p i l e r t e c h n i q u e sm a i n l yi sl i m i t e di nl o o p - l e v e lp a r a l l e l i s m ，w h i c hc a n n o te x p l o i ts c a l a ri n s t r u c t i o n s a n ds i m dv e c t o ri n s t r u c t i o n so p t i m a l l y t r a d i t i o n a lc o m p i l e rt e c h n i q u e su s u a l l yi m p r o v ec o d eq u a l i t yf o ras i n g l eo b j e c t i v e ，s u c h a sp e r f o r m a n c eo rp o w e r h o w e v e r ，e m b e d d e ds y s t e m su s u a l l yn e e dt ob eo p t i m i z e df o r x i i i m u l t i p l eo b j e c t i v e s i ti sn e c e s s a r y t or e s e a r c hh o wac o m p i l e rt r a n s f o r m a t i o nf o ro n eo b j e c t i v e i n f l u e n c e st h eo t h e ro b j e c t i v e sa n dh o wt om a k et r a d e - o f f sa m o n gd i f f e r e n to b j e c t i v e s t h ec o m p l e x i t yo fe m b e d d e ds y s t e m sm a k e si tn e c e s s a r yt oa p p l yn e wm e t h o d st or e - 8 e a r c hc o m p i l e rt e c h n i q u e sf o rt h e m t h ec o r ei d e ao ft h i s t h e s i s i si m p r o v i n gc o m p i l e r t e c h n i q u e sw i t ht h eh e l po fm e t a - h e u r i s t i c sa n dt h ei n t e g r a t i o no fc o m p i l e rf r o n t e n da n d b a c k - e n d i nt h el a s tt w e n t yy e a r s ，t h e r eh a sb e e ne x t e n s i v er e s e a r c ho nm e t a - h e u r i s t i ca l g o r i t h m s m e t a - h e u r i s t i c s ，i n s p i r e db yn a t u r e ，c a no v e r c o m e t h el i m i t a t i o n so fc l a s s i co p t i m i z a t i o na l g o - r i t h m s8 n dc a ns e a r c ：ht h es o l u t i o ns p a c es y s t e m a t i c a l l yt os o l v em a n yo p t i m i z a t i o np r o b l e m s b ys i m u l a t i n gn a t u r a lp h e n o m e n as u c ha sp h y s i c a lp r o c e s s e sa n de v o l u t i o n s t h e r ea r ea v a r i e t vo fo p t i m i z a t i o np r o b l e m si nt h ec o m p i l e rd o m a i n ，w h i c ha r em o r ec o m p l e xi nt h e e m b e d d e dd o m a i n t h e yb r i n gd i f f i c u l t i e st ot h ea p p l i c a t i o no fs t a n d a r dc o m p i l e rt e c h n i q u e s m e t a - h e u r i s t i c so p e nu pab r o a dw a yt os o l v ec o m p l e xc o m p i l e ro p t i m i z a t i o np r o b l e m s p r o g r a ma n a l y s i si st h ef o u n d a t i o no fc o m p i l e ro p t i m i z a t i o n s t om e e tt h e r e q u i r e m e n t s o fc o m p i l e rt e c h n i q u e sf o re m b e d d e ds y s t e m s ，t h ea d v a n t a g e so fc o m p i l e rf r o n t e n dp r o g r a m a n a l y s i sa n dt h em a c h i n e - s p e c i f i ci n f o r m a t i o no fc o m p i l e rb a c k - e n dc a n b ec o m b i n e d t h em a i nc o n t r i b u t i o n so ft h et h e s i sa r ea sf o l l o w s 1 f o ri r r e g u l a ra r c h i t e c t u r a lc h a r a c t e r i s t i c so fe m b e d d e dp r o c e s s o r s ，an e wg r a p h - c o l o r i n g r e g i s t e ra l l o c a t i o na l g o r i t h mh m a g r ai sp r o p o s e d ，w h i c hi s b a s e do nah y b r i de v o - l u t i o n a r ym e t h o d t h ea l g o r i t h mp r o v i d e san e w d i r e c t i o nf o ri m p l e m e n t i n gr e g i s t e r a l l o c a t o r sw h i l eb r e a k i n gt h r o u g ht h ed i f f i c u l t i e si nc o m p u t i n gl o c a lc o l o r a b i l i t yo fi n t e r - f e r e n c eg r a p h s ，w h i c hc a n n o tb es o l v e d a l g o r i t h m sb a s e do ns i m p l eh e u r i s t i c s b yt r a d i t i o n a lg r a p hc o l o r i n gr e g i s t e ra l l o c a t i o n h m a g r aa l g o r i t h mc o m b i n e sag e n e t i ca l g o r i t h mw i t ha t a b us e a r c hs u b r o u t i n e i t u s e 8c h a i t i na l g o r i t h mt op r e - p r o c e s st h ei n t e r f e r e n c eg r a p h ，a s s i g n sc o l o r st on o d e s o ft h er e m a i n i n gi n t e r f e r e n c eg r a p hr a n d o m l ya c c o r d i n gt ot h e i rc l a s s e s ，c o m p u t e st h e n u m b e ro fc o n f l i c t s ，a n dd e c r e a s e st h i sn u m b e rg r a d u a l l yu n t i lt h eg r a p hc a nb ec o l o r e d s u c c e s s f u l l v t h i sm e t h o dc a nn o to n l yc o m p u t et h el o c a lc o l o r a b i l i t yo fi n t e r f e r e n c e g r a p h sa c c u r a t e l y , b u ta l s or e p l a c et h ea dh o cs k i l l so ft r a d i t i o n a lm e t h o d sb yar e g u l a r r e g i s t e ra l l o c a t i o nm o d e l i tc a nt h u sd e a lw i t hc o m p l e xi r r e g u l a rc h a r a c t e r i s t i c so f e m b e d d e dp r o c e s s o rr e g i s t e rf i l e s 2 f o rm u l t i m e d i ai n s t r u c t i o ns e t ，an e wa l g o r i t h mi c g m ef o rt h eg e n e r a t i o no fs i m d c o d ei sp r o p o s e d x i v 国防科学技术大学研究生院学位论文 i c g m ea l g o r i t h me x t e n d ss t a n d a r dt r e ep a t t e r nm a t c h i n ga n dd y n a m i cp r o g r a m m i n g t e c h n i q u e s ，m o d i f i e st h ei b u r gc o d eg e n e r a t o rg e n e r a t o ri ns u c haw a y t h a ti t sg e n e r a t e d c o d eg e n e r a t o r sa l l o wt or e t a i nm u l t i p l em a t c h i n gr u l e sf o re a c ht a r g e tn o n t e r m i n a lo f an o d eo fd a t af l o wt r e e si no r d e rt oi d e n t i f yp a r a l l e lo p e r a t i o n so fs i m di n s t r u c t i o n s t h ed a t af l o wa n a l y s i st h a ti st oi d e n t i f yw h e t h e rm e m o r yr e f e r e n c e sa r ea l i g n e dr e l a t i v e t ov e c t o rr e g i s t e r si sp e r f o r m e di nt h ec o m p i l e rf r o n t e n d t h e nt h ea n a l y s i sr e s u l t sa r e t r a n s f e r e dt ot h ec o m p i l e rb a c k - e n dt oa s s i s ti nc o n s t r u c t i n gs i m da n dp e r m u t a t i o ni n s t r u c t i o n s f i n a l l y , a s s e m b l yc o d eo fm u l t i m e d i av e c t o ri n s t r u c t i o n sa n dn o n - m u l t i m e d i a s c a l a ri n s t r u c t i o n si sg e n e r a t e d t h r o u g ht h ei n t e g r a t i o no fc o m p i l e rf r o n t - e n da n a l y - s i sa n dt h em a c h i n e s p e c i f i ci n f o r m a t i o no fc o m p i l e rb a c k - e n d ，i c g m ea l g o r i t h mc a n n o to n l ys i m p l i f yt h eg e n e r a t i o no fs i m dc o d e ，b u ta l s ou s eb o t hs i m da n dn o n s i m d i n s t r u c t i o n st oi m p r o v ec o d eq u a l i t y 3 i no r d e rt om e e tm u l t i - o b j e c t i v er e q u i r e m e n t so fe m b e d d e ds y s t e m s an e wm e t h o d o l o g y i sp r o p o s e dt od e a lw i t hm u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e m si nt h ec o m p i l e rd o m a i n u s i n gm e t a - h e u r i s t i c s a n dt h ep r o b l e mo fc o d es e l e c t i o nf o ra r m t h u m bp r o c e s s o r s w i t hd u a li n s t r u c t i o ns e t si su s e dt oe x e m p l i f yt h i si d e a t h i st h e s i sf o r m u l a t e st h ep r o b l e mo fc o d es e l e c t i o nf o rp r o c e s s o r sw i t hd u a li n s t r u c t i o n s e t sa sam u l t i o b j e c t i v eo p t i m i z a t i o np r o b l e mt h a tn e e d st r a d e - o f fb e t w e e nt h ec o d es i z e a n dt h ec o d ee x e c u t i o nt i m e ，c r e a t e sam a t h e m a t i c a lm o d e lf o ri tu s i n gp r o g r a mp r o f i l i n g t e c h n i q u e ，a n ds o l v e si tw i t hab a s i cm u l t i - o b j e c t i v ea n tc o l o n yo p t i m i z a t i o na l g o r i t h m m o a r m a n t s st o g e t h e rw i t hs u b s e ts e l e c t i o nm e t h o d 4 b a s e do nt h es u i f m a c h i n e s u i fc o m p i l e rr e s e a r c hf r a m e w o r k ，w eh a v ee x t e n d e dt h e e x p e r i m e n t a le n v i r o n m e n tf o rc o d es e l e c t i o n ，r e g i s t e ra l l o c a t i o n ，a n dp r o g r a ma n a l y s i s s e v e r a lt r a d i t i o n a lg r a p h - c o l o r i n gr e g i s t e ra l l o c a t i o na l g o r i t h m sa n dam e t a - h e u r i s t i c g r a p h - c o l o r i n gr e g i s t e ra l l o c a t i o na l g o r i t h mh m a - g r ah a v eb e e ni m p l e m e n t e d ac o d e g e n e r a t i o na l g o r i t h mi c g m ef o rm u l t i m e d i ap r o c e s s o r sa n ds e v e r a lc o m p i l e rp a s s e s f o rp r o g r a ma n a l y s i sh a v eb e e ni m p l e m e n t e da sw e l l f u r t h e r m o r e ，a na c oa l g o r i t h m m o a r m a n t - s sf o rm u l t i o b j e c t i v ec o d eg e n e r a t i o ni si m p l e m e n t e d i t i sn e c e s s a r yt oe x t e n dt r a d i t i o n a lc o m p i l e rt e c h n i q u e so rt od e s i g nn e wo n e si nt h e e m b e d d e dd o m a i n t h i st h e s i sa n a l y z e ss o m ek e yp r o b l e m so ft r a d i t i o n a lc o m p i l e rt e c h n i q u e s i nt h ee m b e d d e dd o m a i n b a s e do nm e t a - h e u r i s t i c sa n dt h ei n t e g r a t i o no ft h ec o m p i l e r f r o n t e n da n db a c k - e n d ，i tm a i n l yf o c u s e so nt h r e ep r o b l e m so fe m b e d d e ds y s t e m s ：r e g i s t e r a l l o c a t i o nf o re m b e d d e dp r o c e s s o r s ，c o d eg e n e r a t i o nf o rm u l t i m e d i ai n s t r u c t i o ns e te x t e n s i o n ， 国防科学技术大学研究牛院学位论文 a n dc o d es e l e c t i o nf o rd u a li n s t r u c t i o ns e tp r o c e s s o r s e x p e r i m e n t a lr e s u l t sp r o v et h ee f f i c i e n c y o fo u rm e t h o d s t h er e s e a r c ha n di m p l e m e n t a t i o ni nt h i st h e s i so na p p l y i n gm e t a - h e u r i s t i c st o c o m p i l e rt e c h n i q u e sf o re m b e d d e ds y s t e m sa r es t i l le l e m e n t a r y f r o man e wd i r e c t i o n ，m e t a - h e u r i s t i c so p e nu pab r o a dw a yt or e s e a r c hc o m p i l e rt e c h n i q u e si nt h ee m b e d d e dd o m a i n k e yw o r d s ：c o m p i l e rt e c h n i q u e s ，e m b e d d e dp r o c e s s o r s ，m e t a - h e u r i s t i ca l g o - r i t h m s ，r e g i s t e ra l l o c a t i o n ，c o d eg e n e r a t i o n ，m u l t i m e d i ai n s t r u c - t i o n s ，m u l t i o b j e c t i v eo p t i m i z a t i o n x v i 国防科学技术大学研究生院学位论文 表目录 3 1 寄存器分配s p i l l 代码开销5 2 3 2 寄存器分配算法的时间开销5 6 4 1 核心函数三种目标代码的比较7 1 6 1a l i g n m e n t 分析传播函数【1 1 1 0 2 6 2 i b u r 9 2 的e b n f 文法1 0 3 v 同防科学技术大学研究生院学位论文 图目录 编译器总体结构。3 寄存器分配冲突图，左图中寄存器同构，右图中寄存器异构7 一条s i m d j j i j 法指令并行执行多个加法操作8 c h a i t i n 寄存器分配算法的主要流程1 6 b r i g g s 寄存器分配算法的主要流程1 7 g e o r g e - a p p e l 寄存器分配算法的主要流程1 8 冲突图的两种扩展方法1 9 o l i v e 语言的e b n f 描述2 1 具有2 一c o l o r i n g 的钻石图4 1 b r i g g s 乐观图着色方法4 2 b r i g g s 算法处理寄存器对的加边方法4 2 b r i g g s 处理寄存器对的加边方法4 3 s m i t h - r a m s e y 饱和测试存在保守估算4 5 i n t e lx 8 6 处理器的物理寄存器类4 7 h m a g r a 算法的主模块4 9 传统图着色寄存器分配算法之间的比较5 3 传统图着色与h m a g r a 寄存器分配算法之间的比较5 4 传统图着色与局部搜索以及h m a g r a 寄存器分配算法之间的比较5 5 i n t e lm m x p a c k e d 数据类型【2 】6 1 i n t e lm m x 向量加指令6 2 i n t e lm m x 数据重组指令【2 】6 2 s i m d 代码生成的编译器流程6 6 扩展的t r e e p a r s i n g 基于特定的非终结符识别并行操作6 8 s i m d 数据重组6 9 a c o 元启发式算法的基本结构7 6 g l e - a s s h a s 、e a s 、a s r a n k 的性能比较8 0