（计算机科学与技术专业论文）指令cache优化中代码重排技术的研究与实现.pdf

里堕型兰垫查查兰里! 壅生堕堂垡笙苎 a b s t r a c t w i t ht l ed e v e l o p m e n to fa r c h i t e c t u r e ，e s p e c i a l l y0 fm u l t i i s s u ea 托h i t e c t u r e ，t h ed e m a n d sf o r e f ：f i d e n t l yi n s t m c t i o nf c t c h i n go nm o d e mm i c r o p r o c e s s o r si si n c r e a s i n g s o ，h o wt oi m p r o v e i - c ac ：h eh j tr a t ea n de n h a n c ep m c e s s o r sp e d b 肌a n c eb e c a m eas i g n i f i c a n ti s s u e c 0 d er c o r d e r i n gi sa i li m p o n a n tt e c h n o l o g y0 fi c a c h e 叩t i m i z a t i o n ，w h i c hc a np o s i t i o n d o s d yt o g c t h e rt l i o s cc o d e st h a ts w i t c ht h e i rc o n t r o l t oe a c ho t l l e r 丘e q u e n t l y ，s u c ht h a tt h es i z e 0 ft l l ew o r k i n gs e tc 锄b er e d u c e da n di - c a c h eh i t 豫t ec a nb e 抽c r e a s e d i nt b i sp a p e rw es t u d i c d t h ec o d er e o r d e r i n gl e c h n o l o g y 曲ms e v e r a la s p e c t s ，a n dg e tf o l l o w i n ga c h i e v e m e n t ： f i r s t ，w ed i s c u 鹳e dt w om e t h o d so fg a t h e r i n gt l l ei n f b n n a t i o nf o r d er e o r d 州n gs u c ha s p r o f i l e - b a s e dp r e d i c t i o n ，p r o g r a m - b 鹤e db r 柚c hp r e d i d i o n ，a i l da n a l y z e dt h ea l g o r i m m s0 ft h e m s e c o n d ，w es t u d i e d 锄dc o m p a r e dt h r e em a i nm e t h o d so fc o d er e o f d e r i n g ，i n d u d i n g p r o c e d u r er e o r d e r i n g ，b a s i cb l o c kr e o r d e r i n ga n dp r o c e d u r es p l i n i n g 1 1 l i r d ，w e 孤a l y z e di d e t a j lt b ei l p l e m e n tm e t h o do fc o d er e o r d e r i n gi ng c c a i l dp o i n t e d 0 u tj t sd e 6 d e n c j e s l a s t ，w e 百v ea i la p p f o a c ho fc o d er e o r d e r i n ga ta b s 圩a c t 仃e el e v e lb a s e do nt h ef f a m eo f g c c 4 1 o l l rm e t h o do b t a i n sp r o c e d u r e sc a l l i n gf r e q u e n c yi n f o 皿a t i o nb a s e d0 n t a t i cb m c h p r c d i d i o n ，锄dr e o r d e r st h ep r o c e d u r e sb yh pa l g o r i t h m t h ee x p e r i m e n tr e s u ns h o w st t l a tt h i s 印p r o a c h 伽曲t a i l lc o n s i d e r a b l eo p t i m i z a t i o ne f f e c t k e y w o r d s ：i n s t n l c l i o nc a c h e ，d er e o r d e r i n g ，p r o c c d u r er e o r d e r i n 舀b r a c hp r e d i c t i 图目录 图1 11 9 8 0 年以来处理器和存储器的性能随时问提高的变化曲线图 图1 2 一个通用于嵌入式系统、台式机和服务器的典型多级存储层次结构 圈2 1 过程调用图 图2 2 包含一个循环头的循环，+ 图2 3 由分支概率求分支频率示意图，+ + 。 图2 4e d g ep r o f i l i n g 示意图 图2 5 过程放置示意图， 图2 6 控制流程图， 图2 7 逻辑c a c h e 示意图， 图2 8 过程分裂示意图， 图2 9 过程分裂的修正， 图3 1g c c 结构图， 图3 2 根据d a 文件获取基本块执行次数的处理框架图 图3 3 基本块移动示意图， 图3 4 基本块重排相关函数处理时序图 图3 5 基本块重排总体框架图， 图4 1g c c 编译处理的太体框架， 图4 2 过程重排框架图 图4 3 过程调用频率传播示意圈 图4 4 过程重排示意图+ 圈4 5s p e c f p 2 0 0 0 在各种优化方案的结果比较图，。 图4 6s p c i n t 2 0 0 0 在各种优化方案的结果比较图， o_墙他坞塘盯埔均加组控衢札弘如帖儿肌 ， - ， 一一一 旦堕型兰垫查查堂鲨塞竺堕堂生笙苎 一 表目录 表2 1 b a l ll a r u s 预测的分支发生概率 表4 1s p e c f p 2 0 0 0 测试结果( 单位秒) 表4 2s p e c i n t 2 0 0 0 测试结果( 单位秒) 1 1 5 0 5 0 国防科学技术大学研究生院学位沦文 第一章绪论 1 1 课题研究背景 1 1 1 处理器与存储器的性能差异 随着制造工艺的进步以及计算机体系结构的发展，处理器的速度大约每1 8 个月就增 长一倍，而存储器的速度大约每十年才增长一倍，处理器和存储器性能的提高并不同步， 存储器的发展速度已经远远落后于处理器的发展速度。自上世纪八十年代以来，主存储器 的访问速度每年增长7 左右，而处理器的速度的增长达5 0 至1 0 0 “”。图1 1 1 给出了1 9 8 0 年以来处理器和存储器的性能随时间提高的变化曲线图。 p r o c e s s o 卜d r a mg a p ( i a t e n c v ) 1 0 0 0 8 磊 至 是 芷 1 0 0 1 0 1 图1 11 9 8 0 年以来处理器和存储器的性能随时间提高的变化曲线图 1 1 2 层次存储系统 为了解决存储器与处理器在处理速度上的巨大差异，人们引入了层次存储系统。层次 存储系统是指将存储系统组织成一个层次的结构，在这个层次系统中存储容量大、访问速 度慢的存储器位于较底层，存储容量小但访问速度侠的存储器则位于系统的较高层次。 寄存器c 扯h o 容量：5 0 0 b 批 “k b 速度： 0 2 5 n sl n s 存储器 5 1 2 m b i o o n s 磁盘存储 1 0 0 0 b 5 m s 图1 2 一个通用于嵌入式系统、台式机和服务器的典型多级存储层次结构 如图1 2 是一个典型的层次存储系统，在该系统中距离c p u 越远的层次，存储容量越大 第l 页 国防科学技术大学研究生院学位论文 访问速度越慢。此外由于快速存储器较为昂贵，这种组织结构同时也提供了一个存储器系 统，使其价格几乎相当于最便宜的一层存储器的价格，但是访问速度却与最快一层的接近。 在层次存储系统中，处理器直接在c a c h e 中取得指令和数据，因此c a c h e 的性能的好 坏直接影响到c p u 性能的发挥。特别是现代高性能处理器大多是多流出的体系结构，它对 c a c h e 的影响更大。因此如何提高c a c h e 性能，最大限度发挥处理器能力已经成为硬件设 计人员和软件设计人员共同关心的主题。 1 1 3 指令c a c h e 优化 与数据c a c h e 一样，对于指令c a c h e 来说，平均访问时间是衡量其性能的一个重要标 准。设法降低c a c h e 的平均访问时问是c a c h e 优化所关心的主要问题，我们有如下的计算 公式： 平均存储访问时间= 命中时间+ 失效率8 失效代价 从上面的公式可知，可以通过减少命中时间，提高命中率，减少失效代价等方面来优 化c a c h e 的性能。其中减少命中时间和减少失效代价只能从体系结构和硬件方面考虑，而 减少失效率则可以从体系结构和软件两方面来考虑。我们在此所关心的是如何减少c a c h e 的失效率。 一般来说，c a c h e 失效可以分为三类：一类是强制失效( c o m p u l s o r ym i s s ) ，即第一 次访问某个数据时产生的失效；另一类是容量失效( c a p a c i t ym i s s ) ，即由于c p u 工作集 超过了c a c h e 的大小，使得访问过的数据不在c a c h e 中；最后是冲突失效( c 0 n n i c t m i s s ) ， 它是指c a c h e 中被访问的数据由于c p u 交叉引用另一数据而被替换出c a c b e 。强制失效发 生的频率并不高，对程序性能的影响不明显，可通过预取的机制来降低这种失效开销。当 c a c h e 容量较小时，则通常会发生容量失效，增大c a c h e 容量可以降低容量失效的频率。 冲突失效是由于多个当前活跃地址都映射到同一c a c h e 行中引起的提高c a c h e 的关联度 是降低冲突失频率的一种有效方法。前面的方法都是基于体系结构层次的优化策略，此外， 通过软件方法实现的开发程序的局部性，也是降低失效的一种非常有效的方法。程序中 1 0 o o 代码运行9 0 的时间f 2 1 】，程序的运行满足一定的局部性规律，局部性包括空间局 部性和时间局部性两个方面。空间局部性是指最近被访问数据的相邻数据在不久的将来会 被访问，而时间局部性是指最近被访问的数据在不久的将来会被再次访问。c a c h e 的引入 也正是利用了程序的局部性原理。在编译或链接时，我们根据一定的策略将分支频繁或调 用频繁的代码放置在一起，这样可以提高程序的局部性从而提高指令c a c h e 的命中率。目 前，在许多商用1 1 0 蝽开源编译器【9 1 1 l 中都实现了通过代码重排来达到对指令c a c h e 进行优 化的目的。 第2 页 国防科学技术大学研究生院学位论文 l ，2 代码重排技术 1 2 1 代码重排的概念 代码重排是指以提高指令c a c h e 命中率为主要目的，由编译器、链接器或其它工具实 现的根据一定规则改变代码排列次序的技术。它的目的是通过改变代码的原始的排列次 序，将频繁调用或转移的代码块放置在一起，以提高程序的局部性，改善指令c a c h e 的性 能。目前，代码重排的粒度主要有两种。一种是以过程为基本重排单位，它根据过程之间 的调用频率来决定过程放置的先后次序。另一种是以基本块为单位的代码重排，它是过程 内部的代码重排，它的重排依据是各基本块的执行和分支转移的频率。此外，为了进一步 提高代码重排的优化效果，我们通常对过程进行适当的分裂，它将过程内部执行频率非常 低的代码从过程中分离出来，放置在目标文件中的单独区域，通过这种处理通常可以减少 程序的工作集，提高程序的空间局部性。 代码重排可以在程序的编译阶段实现【1 5 1 ，也可以在程序的链接时实现【2 3 10 1 ，此外还 可以在程序的运行时通过其它工具( 如l o a d e r 程序) 实现1 4 。前面两种是静态的重排方 法，它们使用的重排信息可以通过两种方式获得，种是在编译时根据定的启发式信息 预测程序的执行频率，另一种方法通过两遍编译，第一遍在程序中插桩并运行一个小的数 据集来收集程序运行时的p m f i l e 信息，第二遍贝根据反馈的p m f i l e 信息指导优化。而动态 的重排方法所使用的是程序运行时的信息来指导代码重排。由于运行时代码重排的开销比 较大，它一般只适合大粒度的过程重排。 1 2 2 代码重排对程序的影响 代码重排的目的就是改善程序的局部性，提高指令c a c h e 的命中率，除此之外，代码 重排还可以减少程序的工作集的大小，提高1 1 m 的命中率，同时还能拉直指令执行序列， 减少发生分支的数目等等。由于它从多方面影响了代码运行性能，目前在许多商用编译器 ( 如：c 0 m p a qc 编译器1 10 】) 和开放源码编译器( 如：0 p e nr e s e a r c hc 0 m p i l e r ( o r c ) 编译器1 1 1 】 和g n ug c c 编译器【9 】) 都采用来了代码重排的优化，并取得了非常显著的优化效果。例如， 在c 釉p a qc 编译器中，采用了基于p r o f i l e 信息的激进的经典优化，s p e c i i 】t 9 5 测试程序 平均获得1 7 的加速比【。代码重排到底是怎样影响程序性能的? 下面我们针对不同的重 排粒度分别进行讨论。 对于基本块重排来说通过将分支频繁的代码放置在一起，使得执行频繁的代码成为下 降分支，加长了分支前代码的执行序列的长度，同时每个c a c h e 行中被执行的指令数目也 增加了，降低了指令c a c h e 的失效率。在通常的代码中大量执行频率很低的代码分布在 程序的各个部分，它们严重影响了指令c a c h e 的性能。考虑如下一段错误检测代码： 第3 页 国防科学技术入学研究生院学位论文 i f ( f 酷f ，d re r r d r ) t h e n h a n d l eu n u s u a lc a s e m o r ec o d e 通常情况下错误不会发生，因此，如果不进行优化处理的话，分支指令所在的c a c h e 行中 的指令并非都被执行，从而降低了指令c a c h e 的利用率。如果将执行频率低的代码分离出 来，则可以提高c a c l l e 的命中率。除此之外，通过将分支频繁的边变为下降边，减少了发 生分支的数目，同时硬件预测与程序的正常执行相匹配，降低了分支的开销，更好地利用 了分支延时槽。在某些情况下，将不频繁执行的代码移走，还可以消除一个无条件分支。 对于过程重排来说，通过将频繁调用的过程放置在一起，增加了两个过程位于同一页 面的概率，从而减少了程序的工作集的大小，降低了1 r i 上f r h s l a t i 【舶k a s i d eb u f f e r ) 的 失效率。过程重摊的另一个好处就是可以减少长分支指令的数目，可以提高程序的执行效 率。同时也减少了两个过程间代码在c a c h e 行中的交叉次数，这会导致更少的c a c h e 的冲 突，从雨提高指令c a c h e 的命中率。 对于过程分裂来说，它将过程内部的一些执行频率很低的代码分离到一个单独的区域 中，从而可以减少过程的体积，提高程序的局部性。通过过程分裂，更多的过程可以位于 同一个页面中，这样更进一步减少了程序的工作集以及t l b 的失效率。 1 2 3 代码重排技术的研究现状 对于通过对程序进行重新构造来优化存储系统的性能的技术，很早就有人从事这方面 的研究，他们早期的工作主要集中在如何减少虚存系统中页的失效i 笛2 4 芦郐御。随着计算机 的发展，特别是c a c h e 的出现，人们逐渐将目光转向c a c h e 层次的优化。如何在过程和基 本块的较低层次上通过改变程序的排列次序来提高指令c a c h e 的性能逐渐成了编译优化所 关注的焦点。 一目前，根据重排实现时机的不同，我们可以将代码重排分为两类；一类是静态的方法， 即在程序编译和链按时实现的代码重排。它最主要是通过一定的启发式信息或程序的 p r o m e 信息来指导编译器对代码进行重新重排达到优化的目的。另一类是动态实现的方法， 它是在程序运行时由装载程序实现的代码重排，它主要应用在当前的w m d o w s 平台的动 态调用库( d u ，) 程序以及u n 平台中的共享对象中。 动态方法是根据程序运行时的动态信息确定代码的排列顺序。例如，由d 孤i e l j s c a l e s 提出并在舢p h a 服务器的d i g i t a lu n i x 中实现的d y n a m i cp r o c e d u r ep l a c e m e n t ( d p p ) 算法 1 ，就是一种动态的重排方法，它是对c h e n 和l e u p e n 的j u s t i n t i m ec o d el a y o u t ( j i t c l ) 一1 算法的一种改进。它的基本思想是根据程序调用的先后次序对代码进行重排，所有的操 作对用户来既都是透明的，代码放置的过程由功a d e r 程序实现。放置前在代码段开辟一个 新的代码区域用来放置被调用的过程，然后对过程按照调用的先后次序放置在新代码段 中。通过这种方法放置过程可以有效地提高c a c h e 的性能，但由于运行时开销太大，会对 优化的效果产生负面的影响，因此也很难做到过程内的基本块重排。 静态重排方法的频率信息可以有两个来源，一个是根据启发式信息预测代码的执行和 第4 页 国防科学技术大学研究生院学位论文 第二章基本概念与关键技术研究 本章主要介绍了重排相关的基本概念，研究了获取代码重排信息的两种主要方式，介 绍并分析了相关的算法，并从过程和基本块两种粒度以及过程分裂等方面介绍了当前代码 重排的主要技术，分析和比较了各种算法的特点。 2 1 1 过程调用图 2 1 过程调用图和程序控制流程图 在编译优化中，过程问的优化需要用到过程的控制流与数据流。作为过程间优化的过 程重排同样需要用到过程之间的调用信息，它需要知道程序中所有的过程以及它们之间的 调用关系，为此必须有相关的工具来刻画和描述这种关系。一个常用的手段就是构造过程 调用图。调用图是一个有向图，图中的节点表示过程，有向边表示过程之间的调用关系。 我们给出其形式化的定义如下： 给定一个由过程p l ，p 2 p n 组成的程序p ，p 的( 静态) 调用图是由节点集合 n = p 1 ，p n ) ，调用点标号集合s 、带标号的边的集合e 口4 x n x s 以及一个区别对待的入口节 点r 甜( 代表主程序) 组成的图g p = ( 通常写作g ) ，其中对于每个e = ， s k 表示p i 中对p j 的一个调用点。如果过程p i 对p j 只有一次调用，我们可以省略调用点 s k ，并将此边写成p i p j 。 对于过程重排来说，所关心的只是某个过程对哪些过程进行了调用，以及它们之间的 调用频率是怎样的。因此，我们可以将以上的调用图加以修改，成为一个加权的有向图， 图中边的权值表示一个过程调用另一过程的频率，节点的权值表示该过程所执行的频率。 如下图2 1 所示，就是一个有向的过程调用图，图中的节点表示每一个过程，边表示它们 的调用关系( 从调用者指向被调用者) ，边的权值表示过程之间的调用频率。 图2 1 过程调用图 2 。1 。2 程序控制流图 在编译优化阶段，我们必须使编译器对程序如何使用系统中的可用资源具有全局性的 第8 页 国防科学技术大学研究生院学位论文 “理解”能力。它很重要的基础就是构建程序的控制流程图，通过控制流图来描述程序的 控制的流向。控制流图是由基本块和有向边组成，图中的每个节点表示一个基本块，连接 基本块的有向边表示控制的流动方向。 在控制流图中，基本块( b a s i cb 1 0 c k ) 是一个非常重要的概念，它是指程序中一个顺序执 行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其 中的最后一个语句。对于一个基本块来说，执行时只能从其入口进入，从其出口退出。基 本块的第一条指令称为首领0 l e a d e r ) ，它可以是程序的入口点，分支的目标，或直接紧跟在 分支指令或返回指令之后的指令。为了确定一个程序的基本块，我们首先标识出所有的首 领指令，然后对于每一个指令，依次将从该首领到下一个首领或程序结尾之间的所有指令 都包含在它的基本块中。 在标识了基本块之后，我们用含有节点集合和( 控制流) 边集合的有根的有向图来刻画 过程的控靠流。图中的每个节点代表一个基本块，外加两个不月的结点，称为e 姗和e x i t 节点，以及一个边的集合。边集合中的边连接一个基本块到其它基本块。此外，对于过程 中的每个初始基本块，我们引入从e n t r y 到它的一条边；对予每个结束基本块( 没有后继的 基本块) ，引入从它到c x i t 的一条边。e n t r y 和e x j t 基本块不是实质性的，引入它们是出于 技术上的原因它们使得许多算法描述起来更简单。由此得到的图我们称之为过程的控 制流图。在基本块重排中还需要用到基本块执行频率，分支发生的概率，以及分支的频率。 因此，在重排时我们通常构造的是一个加权的控制流图。 2 2 代码重排信息的获取 通常可以使用预测的方法来分析程序的分支的行为，要使代码重排能取得理想的效 果，其中一个关键的因素就是如何对程序的运行行为做出合理的预测。目前- ，预测程序行 为的方式主要有两种：一种是根据一定的启发式原则分析程序代码的静态预测；另一种是 根据程序运行的p r o f i l e 信息对程序的行为做出动态预测。两种方式都能有效预测程序行为， 指导编译优化，但后者的预测更为精确。当前大多数代码重排算法都使用代码的执行频率 作为重排的依据( 也有一些方法使用程序的时序信息来指导重排，如t p c m “1 算法的过程重排 算法就是如此) 。因此，如何取得程序的频率信息成了代码重排首先 溶旧i 题卞面我们将分别对当前使用的二瓤 晰黧刚护唼j雾甬争辄刚鳓黍嚣廷登“马一|；：fj舌褊丽编警霭耧苷鍪；蓉签等翥渊攀生的可能性做出推断，预 测分支是发生还是不发生。有研究表明i 别，许多程序的动态分 支的行为与程序的输入无关，因而，静态分支预测通常是预测程序的分支的行为的一种有效方 式，它是编译优化常用的一种手段。分支预测首先根据个启发式策略预测程序中分支的 发生概率，然后再根据分支的发生概率推导出每一个基本块与边的分支频率。在过程内的 x 国防科学技术大学研冤生院学位论文 图的调用频率进行预测。程序分支预测最著名的算法是w u l a m s 算法f 1 4 】，下面我们分别 从过程内部和过程之间两个方面分别进行介绍。 过程内部的预测是以程序的控制流图为基础的。它首先根据启发式信息对控制流图中 的每一条边估算它的发生概率。算法的启发式策略选择借鉴了b a l l 1 a m s 的思想，它将 控制流程图中的分支分为两类，一类是循环分支，一类是非循环分支。在这里循环分支是 指某个分支的出边要么跳出循环，要么是循环的回边，它的一个特性就是该类分支控镱4 循 环迭代。同理，非循环分支是指那些不是循环分支的分支，它对循环迭代不会有影响。一 般来说一个循环会迭代多次，因此，对于循环的回边，则认为其是会发生的，而对于跳出 循环的边来说，则认为它是会不发生的。如果某条边不是循环边则可以根据分支指令的操 作码和操作数进行预测，也可以根据分支指令的后继基本块的特征进行预测。具体预测方 法如下： l o o pb r 柚c hh e u r i s t i c ( l b 哪：预测指向循环头的回边是发生的，跳出循环的边 是不发生的。 p o i n t e r h e u r i s t i “p m ：当一个指针与n u l l 或两个指针值相比较时 c a l l h e u r i s t i “c i ) ：分支的后继基本块包含一个调用时。则预测分支不会到达该后继基本块。 s t o r e b e u r i s t i c 幅h ) ：如果分支的后继基本块中包含一个存储操作，则预测分支不会到达该后继基本块。r e t u m h c u r i s t i “r 脚：若分支的后继基本块包含返回操作，则预测分支不会到达该基本块。对 每一个分支使用这些启发式信息进行预测，当有多个启发式信息可以使用时，则对它 们定义一个优先顺序，每次选择首次匹配的启发式原则进行预测。算法提供的顺序如下：p 支 是发生还是不发生，它还不能确定如果一个分支发生的话它的发生概率是多少，为此b all&larus通过反复的试验得出如表21所示的一组数据用来预测分支发生的概率。第 x 里堕型兰垫查。- 大堂型壅兰堕堂垡笙窒 表2 1 b a l l i j a n l s 预测的分支发生概率 h e u r i s t i 璐 p m b a b i j i t yo fb 描n g b r a n c l i l o o pb r a n c h ( u j h ) 鹤 p o i n t c r ( p h ) 6 0 c a 儿( c h ) 7 8 0 p c o d ef o h )蝴 l 0 0 pe x i t ( u j h ) 8 0 r e t u m ( 1 l h ) 7 2 s t o r e ( s h ) 5 5 l o o ph e a d e r ( i 删)7 5 g u a r d ( g h )6 2 在分支概率预测完成以后，就需要进行频率的预测，即根据分支的概率预测基本块的 执行频率以及分支的频率。首先有如下的一些推导方法，若知道某个基本块的执行频率， 则它的出边的频率等于基本块的频率与该分支的概率的乘积，同时基本块执行频率等于它 的所有的入边的频率的和。由于预测是在过程的内部进行的，不需要考虑过程之间的调用 情况，即不需要知道某个过程的具体执行频率，可以假设每个过程只执行一次。因此，对 于每个过程来说它的入口基本块的执行频率是1 。根据这个信息和前面的推导方法，沿着 控制流的方向对频率进行传播，很容易计算出所有基本块和分支的频率。用形式化的公式 表示如下： b 缸q 惭) = l( 如果b i 是入口基本块) b f r c 心i ) = y 加鼋一6 f ) ( 否则) 却e 声茜( 埘) 丘e q ( b i 专b j ) = b f r e q ( b i ) + p r o b ( b i 专b j ) 其中b 疔e q 表示基本块的频率，打e q 表示边的频率，p r e d 表示b 的所有前驱节点，p r o b 表示边的发生概率。这种方法对于没有循环的控制流程图时是非常有效的，在有循环的情 况下，由于循环头的节点的频率的计算依赖于循环返回边的频率，而循环返回边的频率又 依赖于头节点的频率的传播，这是一个相互递归的问题，因此，简单地向下传播算法无法 解决这种问题。对于可归约图中的无嵌套循环来说，关键是求循环头节点的频率，现在我 们推导关于头节点频率的计算公式。 如图2 2 ，假设b 0 是循环头节点，它是循环的唯一的进入节点，”一，叼p u j 是进入该 节点的非循环边的频率的总和，b 1 ，b k 是包含到达b 0 的返回边的基本块。“是控制从b o 到达b j 的概率，p 是控制从b 0 经过b i 再返回b o 的概率，且有p f ：r f + p r d 6 ( 6 f 4 6 0 ) 。则 第1 l 页 国防科学技术大学研究生院学位论文 循环头节点的频率有以下的公式： 咖g p 0 ) ；拥一加口( 6 0 ) + 善加口( 6 - 6 0 ) 设 = 加一他口( 6 0 ) + 罗( 垆叼何扫r 口6 何一加吣 箭 i = 加一阳p o ) + 善惭( b o ) + ，+ p r d 6 何- 6 0 ) ) = 加一f 钾p o ) + 皂伊叼p o ) 善( 一+ p 砌枷- b o ) ) = 一+ p ，0 6 何一6 0 ) i 叩p 0 ) 2 善( ，f p 渤( b _ 6 0 ) ) 。著p 如果o s 印p o ) 1 则 ；塑：立丝鱼虫 1 一节p o ) 图2 2 包含一个循环头的循环 在这个导出公式中，我们将印( b o ) 叫做b 0 的循环概率( c y c l i cp r o b a b i l i t y ) 。由公式我们可以 知道，在求循环头节点的频率对，只要隶出循环概率就可以。对于结束的循环( 控制流图 中有循环跳出边) 来说印( b o ) s u c c 一 d e s t 以及 b b 一 s u c c 一 s u c c n e x t 一 一 d e s t 可得到该基本块的所有后继节点；通过b b 一 p r e d 一 d e s t 以及b b 一 p r e d 一 p r e a _ n e x t 一 一 s r c 可得到该基本块的所有前驱节点。此外，c o u n t 保 存该边的执行频率信息，p r o b a b i l i t y 是该边的分支概率信息。 3 3 基于程序插桩的p r o f i l e 重排信息 g c c 中的重排信息主要有两个来源，一个是通过程序插桩取得程序运行时的p r o f i l e 信息，另一个是通过静态分支预测分支概率以及频率信息。两种方式在g c c 中被有机地 结合起来，即在不能取得运行时脚l e 信息时，则使用静态预测的方法预测。 基于程序插桩的p r o f i l e 信息，与之相关的功能的代码主要有三个部分。一部分是程序 插桩的代码，另一部分是信息读取的代码。最后是分支概率计算部分。 对于程序的插桩主要由呻6 l e c 文件完成。我们在第二章提到过，代码重排需要基本 块与边的频率信息，因此通过对边的插桩可以完成这一目的。同时为了减少插入代码的数 量，通常先对控制流程图构造一个生成树，然后对不在生成树上的边进行插桩，这样既能 取得必须的信息又能减少开销。这部分功能是由函数b r a n c 吣r o b 完成，在打开呻f i l e a r c s 开关时( 表示用户需要对程序进行插桩处理) ，则该函数首先调用f i n d _ s p a i l n i n g i 扛e e ，构造 调用图的生成树，并且将那些异常边与关键边也添加进来。完成这部分工作之后，则调用 i i l s t m m e n te d g e s 对不在生成树上的边进行插桩处理。具体完成插入对插桩库函数调用指令 的功能是由mp 斌l e c 中的f t l 蓼n e d g ep r o f i l e r 实现的，它在r t l 中闻表示层插入 x 国防科学技术大学研究生院学位论文 i n tr o u n d ；在第几遍中被构建的 i n tl e n g t h ；，轨迹的长度( 基本块的数目) t r a c e 数据结构是保存与轨迹相关的信息，每一条轨迹有一个t r a c e 与之相对应。对于每 一条轨迹通过f i r s t 和l a s t 两个域保存该轨迹的首位两个基本块，它在后面轨迹的合并时将 被用到，该轨迹是在第几遍进行构造的，在后面判断是否存在循环时将会利用到它们。 l e n g 吐l 表示轨迹的长度，即基本块的个数。n 佻e 数据结构虽然只有轨迹的首尾两个基本块， 但是前面我们介绍过，基本块中有一个r b i 域，可以通过r b i n e x t 将轨迹链中的基本块连 接起来，因此，通过首尾两个基本块就可以对轨迹中的所有基本块进行访问。此外，g c c 中和基本块有关的数据结构定义如下： t y p c d c fs t m c tb b r o _ b a s i 咄i o c k d a t 硅_ d e f f i n ts t a n o ft r a c e ；哪个路径的开始块( 1 表示不是路径的开始块) i n t e n do 乏t r a c e ；删匿个路径的结尾块( 1 表示不是路径的末尾块) 肋h e a pth e a p ；b b 在哪个堆中 f i b n o d etn o d e ：佃b 在哪个堆节点中 ) b b 阳- b a s i 屯b l o c k _ d a t a - d e f 也是基本块重排中的一个十分重要的数据结构，它是记录 重排时每一个基本块的相关信息，因此每一个基本块都对应有一个结构，他们组成一个数 组，数组元素的个数就是基本块的数日。我们可以通过基本快的索引数据域i n d c x 来访问 该数组，通过这个数据结构我们可以报容易地判断一个基本块是否为一条轨迹的开始块或 结束块，如果是则保存的是该基本块所属的轨迹索引号，如果不是则该值为1 ，这在我们 后顽的轨迹链按时非常有效。h e a p 域记录了该基本块所对应的堆的信息，h e a p 在轨迹构 建中有非常重要的作用，它存放了本遍所用的种子节点，在一条轨迹构造完成之后再在 h e a p 中选择一个关键值最小的基本块构建新的轨迹。在本遍轨迹审投存被选中的基本块则 保存到一个新的h e a p 中，供下一遍轨迹构建时作为新的种子节点，初始时的种子是程序入 口点的所有的后继基本块。在将基本块压入h e a 口中时，首先生成一个关键值，它是基本块 频率最高的进入边的值， 除了以上两个关键数据结构之外，还必须确定阂值的有关信息，以及构造轨迹的遍的 信息，他们定义如下： 矧e 丘n en j t o u n d s5 ：处理遍数，通常是4 遍，但是在将过程分裂成冷和热区域时需要 额外的处理遍。 s t a t i ci n tb r a n c k t h r c s h o l d n _ r o i j n d s 】= 4 0 0 ，2 0 0 ，1 0 0 ，o ，o ) ：分支阈值。 s t a t i ci n te x e t t h r e s h o l d n r o u n d s 】= 5 0 0 ，2 0 0 ，5 0 ，o ，o ) ：执行阈值。 籼e 硒ed u p u g 盯i o n j w r e s h o l d1 0 0 ：复制阈值 其中，n r o u n d 定义了需要处理的遍的数目，一般来说通过4 遍就可以构建轨迹。 对于冷块来说( 前面的过程分裂将每一个基本块都分成冷和热两种类型) ，由于在前面的 轨迹构造遍中不能包含进来，因此，我们通常需要额外的一遍来构建所有冷基本块的轨迹。 第2 8 页 国防科学技术大学研究生院学位论文 数组b r a i l c ht l l r e s h o l d 与数组e x e ct h r c s h o l d 定义了分支和执行的阈值信息，他们的元素的 个数是5 ， 元素的值从一个较大的值递减到o ，在每一遍构建轨迹时取其中的一个元素值 作为阈值条件。最后两个值都为零是为了与处理冷基本块相对应。 基本块重排的主控函数是b b - r c o r d e r c 中的r c o r d e r _ b a s i c _ b l o c k s 。该函数首先调用 f i n d 地蝣e s 函数形成一系列的轨迹，然后调用c o 腿e c tt r a c e s 函数对所有构造的轨迹进行链 接，基本块排列的最后的顺序。下面我们分别介绍这两个主要函数。 f i i l dt r a c e s 是构造轨迹的总控函数，它的功能就是根据过程的入口基本块开始，依次 构建基本块的轨迹。工作的过程是对控制流图进行蹬次( 在进行了过程分裂的情况下，通 常需要五次) 循环构造轨迹，每次使用不同的闽值条件，如上面所定义的，每次使用数组 中的一个值。该函数只要控制总循环以及对阙值条件进行设置。具体轨迹的构造是由 6 n dt r a c 1r o u n d 函数完成的。 6 加j m c c s 1m u n d 函数首先从堆栈h e a p 中选择一个权值最小的基本块，判断该基本 块的执行频率是否满足条件，若不满足则将该基本块添加进h e a p 中，如果满足则将该基本 块加入到本次构造的轨迹的末尾，然后再进行后续基本块的选择。选择后续基本块时，首 先选择一条合适的后继边，边的选择必须满足分支阙值与执行阈值等条件，该边的目标基 本块就可能是我们要选择的后续基本块。然后再对该基本块进行判断，看该基本块是否被 访问过，如果被访问则可能有两种情况，一种是该基本块在本次所构建的轨迹中，另一种 是该基本块不在本次所构建的轨迹当中。第一种情况表明有一个循环出现，此时我们对迭 代次数大于4 次的循环进行旋转处理，使得跳出该循环频率最高的边位于该轨迹的末尾。 对于循环小于4 次的情况，且该基本块的后继只有一个，则将该基本块复制到该轨迹的末 尾同时停止路径的增长。对于第二种情况的则将该基本块继续添加进来。通过以上的步骤 就可以构建一系列的轨迹。 在轨迹构造完成之后就需要对各条轨迹进行链接处理。链接的目的就是使得各条首尾 有边相连的轨迹结合成为一条轨迹，同时对于可以进行复制的基本块进行复制处理。完成 该功能的主要函数是c d n n 咄t r a c e s ，该函数根据不同的情况进行处理。对于所有被构造的 轨迹序列，可能会出现以下的三种情况： 一条轨迹的末尾节点与另一条轨迹的首节点存在有一条边相连 一条轨迹的末尾节点与另一条轨迹的中间节点存在一条边与之相连 两条轨迹不相连，或者相连的节点不是首节点或尾节点，即不是首尾相连或尾与 中间节点相连 对于第一种情况，该函数通过两个步骤来完成，首先是向前扩展，即遍历所有的路径， 如果存在有一条轨迹的末尾节点与另一条轨迹的头节点相连，则扩展该路径，将两条路径 的首位相连。然后再向后扩展，即根据当前路径的末尾节点检查受否有一条与之相连的另 一条轨迹的首节点，如果存在则将其首尾相连。如果仍然有一些未连接的轨迹时，则检查 是否存在一个基本块b b ，其中b b 是一条轨迹的末尾块b b 的后继，同时b b 也是另一路 第2 9 页 国防科学技术大学研究生院学位论文 径的开始基本块b b 的前驱块，此时则复制基本块b b 到该轨迹的末尾，同时合并这两条路 径。对于其它剩余的轨迹则将它们简单地进行链接。轨迹的连接时，首先遍历t r a c e 数组中 的每一条轨迹，每访问一条轨迹就对它进行向前和向后的扩展组成一条新的轨迹t 之后再 将它与上一条轨迹进行简单的连接( 首尾相连) 。通过这种方法就可以从程序入口点开始， 将所有的轨迹序列链接成一条新的轨迹。 通过轨迹的构造和轨迹的连接之后，所有对基本块顺序的排列的工作已经完成，并且 基本块重排后的顺序到保存基本块的l b i 域中。从过程的e n m y - - b i _ d c k 开始，通过每一 个基本块中的栅专e x t 就可以访河到新的顺序中的下一个基本块。但是由于改变了基本块 的存放次序，有可能会引起程序的语义的错误。例如，对于一个c 中的典型的i f t h e n 结 构，其控制流图如下图3 。3 ： 图3 3 基本块移动示意图 a c 是分支发生边，a b 是下降边，如果在基本块重排时我们将b 移走，则c 成了a 的下降边到达的基本块，为了保证程序执行的正确性，我们必须在a 的下降边上插入一条 跳转指令，使得它跳转到b 的新位置，在有的情况下还需要转换分支条件。g c g 中这部 分工作是由f u p j c o r d e r - c h a i n 完成的，它主要完成代码重排后的一些修正任务。 f i 础pr e o r d e rc h a i n 函数首先通过r b i 专n e x t 按照新的顺序从入口基本块开始遍历所有 基本块，考察每个基本块的最后一条指令。根据指令的不同将指令分为条件跳转指令，非 条件跳转指令，以及