（计算机系统结构专业论文）面向ixp网络处理器的位域优化和内联优化.pdf

摘要 网络处理器是针对网络处理而优化设计的专用指令集处理器。其底层硬件体系结构 经过特殊的设计能够以线速率处理和传输网络数掘包。但程序员为了编写有效的网络处 理程序必须熟悉网络处理器底层硬件结构这样编写出的f 2 序虽然效- 年，较高，f i 足巫川 性和移植性都较差：并且随着网络处理器体系结构的不断复杂。程序员的负担将更重。 为此需要提供一种高层的，包含语占、编译器、运行时系统的综合编程环境让程序员能 够更加有效的写程序而不需要关注硬件细节。为程序员提供了灵活的编程接口，町以通 过软件实现各种网络处理协议和服务，降低了丌发成本和丌发周期。 网络处理器的特殊体系结构为编译技术提供了新的机会，本文分为两个独立的部分 介绍了在网络处理器i x p 编程环境项目中实现的两个针对其体系结构的编译优化技术一 一位域优化和内联优化。 位域优化是一种针对i x p 中位操作指令集的窥孔优化技术。通过向传统的数据流分 析技术中引入位信息，建立基于位信息的定值使用和使用定值链，以及使用模式匹配 技术进行指令合并。实验数据显示通过位域优化，可以删除i 1 一3 7 的指令。 内联优化是一种传统的编译器优化技术，但是i x p 处理器体系结构的独特性为内联 优化提供了新的机会。通过关键路径提取技术以及迭代编译，内联优化可以更有效的进 行分析和扩展。实验数据显示通过内联优化最终的网络处理的速度可以提高8 。 关键词：网络处理器内联优化位域优化编译器优化 b i t - f i e l do p t i m i z a t i o na n df u n c t i o ni n l i n i n gf o ri x pn e t w o r kp r o c e s s o r t a n gw e i ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db yw uc h e n g y o n g n e t w o r kp r o c e s s o ri san e wg e n e r a t i o no fa s i pp r o c e s s o ro p u m i z e df o rn e t w o r k p r o c e s s i n g o p t i m i z e dd e s i g na l l o w sn e t w o r ks y s t e mt of o r w a r dp a c k e t sa tw i r es p e e d s o f t w a r ep r o g r a m m i n ge n v i r o n m e n tp r o v i d e sp r o g r a m m e raf l e x i b l ei n t e r f a c e ，w h i c hm a k e si t e a s y t oi m p l e m e n tav a r i e t yo fn e t w o r kp r o c e s s i n gp r o t o c o l sa n ds e r v i c e s s u c ha l l e n v i r o n m e n tr e d u c e st h ed e v e l o p m e n tc o s ta n dt i m et om a r k e lh o w e v e r , c u r r e n te r a , i r o n m e n t n e e d ss o r w a r ee n g i n e e r st ob ef a m i l i a rw i t hh a r d w a r ea r c h i t e c t u r e 。t h i sd e g r a d e sp o r t a b i l i t y a n dr e u s a b i l i t yo fa p p l i c a t i o n s w i t ht h ei n c r e a s i n gc o m p l e x i t yo fh a r d w a r e , i tw i l lp u tm o r e l o a d so np r o g r a m m e r s on e wp r o g r a me n v i r o n m e n t sf r e e i n gp r o g r a m m e rf r o ma r c h i t e c t u r e d e t a i l sc o m e si n t or e q u i r e m e n t p r o j e c tt a r g e t st os u c hg o a l u n c o n v e n t i o n a la r c h i t e c t u r eo f n e t w o r kp r o c e s s o re x p o s e sn e w o p p o r t u n i t i e st oc o m p d e r t h i st h e s i si n t r o d u c e st w oi n d e p e n d e n tc o m p i l e ro p t i m i z a t i o n s ：b i t - f i e l do p t i m i z a t i o na n d i n l i n ee x p a n s i o n b o t h ，i m p l e m e n t e di nt h ep r o j e c t , a r ct a r g e tt oi x p a r c h i t e c t u r e b i t - f i e l do p t i m i z a t i o ni n t r o d u c e sb i ti n f o r m a t i o ni n t o t r a d i t i o n a ld a t af l o wa n a l y s i s ， c o n s t r u c t sd e fu s ea n du s e - d e fl i n kp a i ra n dg e n e r a t e se f f i c i e n tm a c h i n ec o d eu s i n gp a t t e r n m a t c h i n g t h ee x p e r i m e n t a lr e s u l t s h o w s t h a t t h i s o p t i m i z a t i o nc a n r e d u c e i n s t r u c t i o n s b y l 1 一3 7 h a l i n ee x p a n s i o ni sac l a s s i cc o m p i l e ro p t i m i z a t i o n n e wf e a t u r e so fd n e t w o r k p r o c e s s o re x p o s en e wo p t i m i z a t i o no p p o r t u n i t y w i t hc r i t i c a lp a t he x t r a c t i o na n di t e r a t i v e c o m p i l a t i o ns u p p o r t , f u n c t i o ni n l i n i n g c a l lp e r f o r mi n l i n e a n a l y s i sa n de x p a n s i o nm o r e e f f i c i e m l y t e s tr e s u l ts h o w st h a tf o r w a r d i n gr a t eo f t h en e t w o r ks y s t e mi n c r e a s e s8 k e y w o r d s ：n e t w o r kp r o c e s s o r f u n c t i o ni n l i n i n g ，b i t - f i e l do p t i m i z a t i o n 1 1 1 图1 1 事件驱动模型 图目录 图1 2 i x p 2 4 0 0 结构图 图1 4i x p 编译器整体结构 图2 1 导出位域操作 图2 2 位域优化代码示例 1 2 图2 3 带位信息的数掘流图1 3 图2 4 位域优化中流程图和模块图1 6 图3 11 3 一s w i t c h 的数据流图 2 4 图3 2 提取出的关键路径2 5 图3 3 关键路径提取流程图 图3 4 关键路径提取性能对比图 图3 5 迭代编译流程 图3 6 内联优化整体流程 图3 7 内联优化的位置。 2 6 3 3 图3 8 后内联被调用函数中的调用点 图3 9 先内联被调用函数中的调用点。 图3 1 0 内联性能分析 v i i 3 4 3 6 3 7 表目录 表2 1i x p 2 4 0 0 支持的位操作 表2 2 实验数据 表3 1 迭代反馈指令数的误差分析 表3 2 内联判断条件 表3 3 内联优化的代码膨胀率3 8 表3 4 基本块数目统计 i x 声明 我声明本论文是我本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，本论文中不包含 其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作_ r 明确的说明并表示j ，跗意。 作者签名：劫伟 晚2 。叮6 1 论文版权使用授权书 本人授权中国科学院计算技术研究所町以保留并向国家有关部门或机 构送交本论文的复印件和电子文档，允许本论文被查阅和借阅，可以将本 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编本论文。 ( 保密论文在解密后适用本授权书。) 惴名：洵午聊躲釉多慨么以6 f 1 1 引言 第一章背景介绍 随着因特叫深入到经济生活的方方面面，各种新型业务以越来越快的速度不断涌现， 伴随它们而来的是对网络处理速度和能力的更高要求，如何提高网络设备的处理速度和 可编程能力成为当务之急。为了提高包处珲的速度，传统网络选择a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ，专用集成电路) 作为处理方案，但这已经无法跟上不断出现 的网络协议和网络服务的要求；为了满足不断出现的网络包处理任务，进一步提高处理 的灵活性，保证处理速度，一种专门用来执行包处理、转发的高速可编程处理器一一网 络处理器出现了。 网络处理器是针对网络应用领域的专用指令集处理器( a s i p ，a p p l i c a t i o ns p e c i f i c i n s t r u c t i o np l o c e l 3 s o r ) 。它具有专门针对网络包处理而设计的体系结构特性和特殊的指令 集。由于特殊的体系结构，网络处理器能够以线速率执行网络处珲程序，除此之外网络 处理器所具有的编程能力使得它在设计实现同样的网络处理功能时相对于硬件解决方案 来说所需要的时间更短，代价也更低。 1 2 网络应用程序的特点 网络处理器是针对网络处理程序的而特殊设计的专用处理器，因此需要分析一下一 般网络处理程序的特点，下面列举了三条特点 1 6 】： 图1 1 事件驱动模型 a ) 嘲络处理程序操作过程一般是接受到达的数据包( 或者称为信元) 。对接收到的 数据包进行处理，再将处理之后的包转发出去 c ) 9 络程序的执行都是由包到达触发的； 通常将嘲络应用程序描述为事件触发的数据流计算模璎。所谓事件触发是与命令触发相 l 中固科学院坝十学位论文血向i x p 叫络处理器的位域优化和内联优化 区别的一种程序设计模型，特别适合于实时系统和交互程度很高的系统。在葬件触发模 型中，事件分发循环不断检测事件的发生；一旦出现事件，就通过事件处理分发程序触 发相应的事件处理程序进行相应的事件处理服务。图1 1 给出了网络中的一个蓼件触发 模型，其中的分发循环是一个典型的事件循环，该分发循环不断从网络通道中读取网络 包，根据网络包请求的服务不同分发到相应的服务处理程序进行处理。 b ) 对实时性要求高。由于网络处理设备要在有限时间内处理大量的包，i 列此处理 每个包的时间很有限，如果在规定的时问片内无法完成数掘包的处理。随后到达的包就 会放到缓冲区内：如果缓冲区满了，导致网络拥塞，造成数掘包的丢失，降低整个网络 传输的性能。 c ) 对分属不同流的包可以进行并行处理。在大部分情况下分属不同流的网络数掘 包处理之间没有依赖关系，因此网络系统可以并行地处理这些数掘包。由于同属一个流 的网络包之间，在经过网络系统时需要保持一定的顺序性，并且同一个流的数据包之日j 还要共享状态信息，因此同属一个流的网络数据包需要串行处理。 1 3 网络处理器的介绍 i n t e r n e t 建立在包交换技术之上，包处理是大部分网络应用的特点，设计用于有效进 行包处理的网络系统通常需要满足两个相互冲突的要求 1 6 1 ：( 1 ) 支持大量高带宽的链 路从而获得高吞吐率；( 2 ) 提供灵活广泛的，可以升级的服务。为了同时满足这两个要 求，网络处理器诞生了。 网络处理器是专门针对网络包处理而优化设计的可编程硬件设备，它的特点是速度 快和可编程，在a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t , 专用集成电路) 硬连电路 的高性能和通用处理器编程的灵活性之间取得折衷： 1 ) 与通用处理器之间的差别 网络处理器是针对包处理而优化设计的它所支持的指令集是专门针对包处理 的指令集。每条指令的执行时间比较短，因此指令流水线可以设计得很浅，这样使得线 程切换的开销更小，可以更好得支持多线程，能够快速高效地处理网络数据包。 2 ) 与a s i c 硬连电路的差别 网络处理器具有可编程性。对于不断出现的网络协议和服务，网络处理器可以通过 编写程序来支持它们，而不需要象硬连电路那样，重新设计整个硬连电路。此外，由于 a s l c 硬连电路的复杂性限制了它只适用于简单处理，难以承担更高层次的协议处理要 求，而网络处理器具有编写高层处理程序的能力，使得它应用面更加宽泛。 1 4i x p 网络处理器结构介绍 i x p ( i n t e r a c t e x c h a n g e p r o c e s s o r ) 是由i n t e l 公司开发的专门用于数据包处理的网络 处理器。它为用户提供了一种专门针对网络应用服务的解决方案，使得用户既能拥有编 2 第一币背景介绍 写通用处理器程序时的灵活性。又能够得到近似a s i c 实现所达到的性能。其中i - ) ( p 2 4 0 0 是i n t e l 公司丌发的第二代网络处理器，结构如图所示： 图1 2i x p 2 4 0 0 结构图 如图所示i x p 2 4 0 0 一共包含了9 个可编程处理器和多个协处理部件：可编程处理器 包括1 个x s c a l e 和8 个微引擎( m i c m e n g i n e ) 。其中x s c a l e 是一个通用处理器，用于处 理很少出现的复杂操作，微引擎是专门优化束进行快速包处理的处理器，它执行大部分 的包处理任务此外微引擎提供了硬件多线程机制，每个微引擎最多支持8 个线程。每 个线程的切换及现场保存都由硬件进行，线程矧调度通过硬件线程仲裁器实现，当一个 线程挂起自己时，由仲裁器决定哪个线程可以执行。通过实现硬件多线程微引擎可以隐 藏访存延迟，微引擎和微引擎之间还可以通过相邻寄存器( n e x tn e i g h b o rr e 衄e 0 进行通 信，实现数据处理的多级流水，提高吞吐率。协处理部件是针对包处理中特殊操作专门 设计的处理部件，为这些常用操作提供硬件支持，如执行h a s h 操作等。此外i x p 2 4 0 0 处理器具有多级存储层次：l o c a lm e m o r y , s c r a t c h p a d ，s r a m 和d r a m ，其中l o c a lm e m o r y 只能由每个微引擎独自使用，存取速度也最快，而其他存储区被所有的微引擎和x s c a l e 共享，其中s c r a t c h 的速度最快但容量最小，d r a m 速度最慢，容量最大。 1 5 编程环境介绍 本文介绍了针对i x p 硬件系统提供的一个简单易用的编程环境。整个环境由三大部 分组成：描述包处理处理程序的编程语言，支持编程语言的编译器以及一个能够进行动 念资源调整与分配以防范攻击优化网络系统性能以及功耗的运行时系统 1 6 1 。图1 给 出了编程环境系统结构图最终的编程环境使得在可编程包处理系统上丌发可移植、高 性能的包处理处理程序变得更加方便 中固科学院硕j 学位论文血向i x p 网络处理器的位域优化和内联优化 图1 3 系统结构 b a k e r 语言：b a k e r 语言是编程环境中提供的专用模块化编程语言，它在语法上类似 于e 语言，但针对包处理领域的一些特殊结构进行了扩展。利用b a k e r 语言网络处理程 序被描述为包处理函数( p p f ，p a c k e tp r o c e s s i n gf u n c t i o n ) 的组合，为整个包处理应用 程序提供了统一的规范。b a k e r 语占书写的包处理程序经过b a k e r 酊端编译成中间表示， 该中间表示以o r c 的w h i r l 中f h 】表示为基础，并针对b a k e r 语言中的特殊结构进行了 相应的扩展。 编译系统包含三个部分：p r o f i l e r ，流水线编译器以及a g g r e g a t e 编泽器。图1 3 给出 了编译系统的整体结构。 p r o f i l e r 阶段的是在代码生成之日h 进行，主要功能是通过仿真我们所定义的抽象机器 模型柬收集代码和数掘结构的p r o f i l i n g 信息一一比如数据结构的存储性质包处理函数 的执行频率、包处理函数之问的通信量、循环次数、分支跳转的频率等等。并将收集到 的p r o f i l i n g 信息标示在中间表示上。利用p r o f i l e r 收集到的p r o f i l i n g 信息可以更好的指导 接下来的流水线编译器进行资源分配。 流水线编译器所要解决的问题是如何组织应用程序来有效地使用包处理系统的各种 资源。首先，它使用数据结构的p r o f i l i n g 信息显式的管理存储层次：其次，流水线编译 器将多个包处理函数合并划分到相应的流水级( a g g r e g a t e ：运行在同一处理部件的函数 集合) ，并为每级流水分配硬件资源，获得一个a g g r e g a t e 到多处理器系统之间的初始映 射关系。 a g g r e g a t e 编译器为每个a g g r e g a t e 生成它的可执行目标代码。a g g r e g a t e 编译器根掘 4 第一带背景介绍 流水线编译器映射的不同处理器类型生成相应的目标代码。很多与体系结构相关的优化 都是在a g g r e g a t e 编译阶段完成的，图1 4 给出了a g g r e g a t e 编译过干廿中包含的一些媳犁 的优化编译优化阶段 由于i x p 网络处理器特殊的多核多线程体系结构，针对网络处理器的编泽优化技术 和通用处理器的编译优化技术之问存在差异，为了能够有效的利用i x p 处理器提供的并 行能力，需要专门设计针对这种体系结构的优化技术。针对i x p 网络处理器体系结构和 指令集的编译优化技术有：a g g r e g a t e 寄存器分配，指令调度和延迟隐臧，访存合并，位 域优化。与体系结构无关的优化主要是函数内联优化循环展开等。 由于i x p 的内存读取指令最多一次可以读取6 4 个字节的数据，因此需要寄存器分配 程序为读出来的内容分配多个寄存器，相应的寄存器分配中使用的图着色算法需要进行 修改以适应i x p 指令集中提供的这种特殊操作指令。i x p 编译器中称这种寄存器分配为 a g g r e g a t e 寄存器分配。 i x p 处理器指令集中很多指令从执行到最终的结果可用必须要等待几个周期，如 l o c a lc s rv v t 指令从执行到结果可用需要间隔三个周期，称作指令延迟槽，为了减少处理 器由于等待指令操作结果导致的停顿，i x p 编译器中实现了全局指令调度和局部指令调 度，通过将一些可以提前执行的指令提到延迟槽中，实现延迟隐减。 由于s r a m 和d r a m 都是慢速存储器，对s r a m 和d r a m 的读写需要很长的时问， 而i x p 指令集中提供了对多个相邻存储单元的读写操作，因此编译器可以通过分析程序 中的s r a m 和d r a m 读写操作，将那些对相邻地址访问的存储指令合并。尽量减少 s r a m 和d r a m 的访存次数。 为了有效地处理网络数据包，网络处理器的指令集中提供了专门针对包处理的指令。 位域优化是针对这些特定指令的一种窥孔优化技术，通过分析指令操作数的的位信息， 在编译器生成的目标代码中寻找可以被指令集中相同功能指令替换的指令序列，进行指 令替换操作，从而达到减少指令数，提高执行效率的目的。 函数调用通常会限制编译优化的作用范围，为了增加编译器处理的能力，传统的编 译优化技术中加入了函数内联优化，它将函数调用点扩展成实际的被调用函数的实现， 通过这种方法减少函数调用开销，这对于那些函数体较小并且频繁被调用的函数非常重 要：内联优化的好处是通过将函数体直接嵌入到函数调用点扩大了函数体的大小，为其 他编译器优化提供了更大的作用空间。 循环展开是一种用于提高在循环分支逻辑之日j 所执行的指令数量的编译优化技术。 它可以降低执行循环分支逻辑的次数。由于循环分支逻辑是额外丌销，降低其次数可以 减少开销，使循环运行更快 除了语言和编译系统外。编程环境还包括运行时系统：运行时系统包含一套系统管 理工具，通过这些工具运行时系统可以完成加载和运行a g g r e g a t e ，监控流量变化、系统 性能、能量消耗，并进行相应资源调整等任务此外，运行时系统还包含一个资源抽象 层，它为各种硬件资源向外提供高层接口，从而隐藏了它们的实现细节 5 中田f l 学院坝i j 位论文向向l 、ph 络处理；! 的位域优化取i 内联仉化 1 6 论文的组织 图1 4i x p 编译器整体结构 本文介绍了在面向i x p 网络处理器编译器中实现的两个相对独立的编译优化技术 位域优化和内联优化；位域优化是一种针对特定指令集的窥孔优化技术，内联优化足一 种和体系结构无关的高层优化。第一章对网络处理器进行了简单的介绍，并以i n t e l 公 司的i x p 2 4 0 0 网络处理器的体系结构为例进行描述，对编译器中的位域优化和内联优化 进行概要介绍。第二章详细描述了位域优化及其实现并对实验数掘加以分析第三章详 细描述了内联优化在网络处理器编译器中的设计与实现，包括迭代编译对内联优化的支 第一帝背景介埔 持以及关键路径提取技术的描述。第四章对整个论文进行总结，并提出迸一步研究方向 7 2 1 位域优化介绍 第二章位域优化 在嵌入式领域，对子字级数掘进行操作的程序相当普遍，比如媒体处理程序以及网 络处理程序等。在网络处理程序处理包头时，由于包头中的每个独立字段可能被映射到 多个内存单元，也可能多个字段映射到一个内存单元，这就要求网络系统在接收到一个 数据包之后要通过相应的位操作将包头中待处理的字段导出，进行相应的处理后，将操 作的结果重新存回到包头中相应的字段，最终将处理后的包头连同包一起转发出去。返 需要进行大量的位操作运算来提取和存储包头中相应字段。 垒! ! 璺宝! g - 露爱夏丽夏f 一百磊辱磊面蔷 图2 1 导出位域操作 如图2 1 所示，如果需要对一个跨越三个字节的字段进行处理的话，程序必须首先 将该字段取出，放到寄存器的低位，高位补0 ，然后进行运算并将运算的结果存回到原 来的字段中。这种存取字段的操作占用大量的执行时间，通过提供支持位偏移操作指令 可以减少这种开销，因此现在很多的嵌入式处理器都提供了直接对位域进行操作的指令。 i x p 网络处理器指令集中也提供了相应的指令。例如i df i e l d 指令，它的作用足将个奇 存器中的某一个或几个字节导出并存到另一个寄存器中，同时保持另一个寄存器中的其 他字节值不变。为了充分利用这些指令，需要编译器在代码生成阶段提供支持为此必 须要分析寄存器中的哪个位段有效以及该位段是否符合指令集中相应指令要求。 位域优化的作用是通过分析位操作指令，得出操作数实际使用的位长；并利用这些 位长信息，选择d 网络处理器中提供的相应操作指令来替换原有的移位或者逻辑操作： 最终达到减少指令条数提高程序运行速度的目的。如果我们不分析位信息，会失去很多 优化机会，无法充分利用指令集提供的位操作指令 位域优化的另一个好处是如果处理器的指令集能够提供位偏移寻址的话，我们可以 将位域范围不重叠的多个寄存器变量压缩到同一个寄存器中，这样就能够用一个寄存器 代替原来的多个寄存器，节约了寄存器这种宝贵的资源，进而减少了s p i l l 指令的数量 提高程序执行速度 中田科学院颂f 学位论文血向i x p 州络处理器的位域优化和内驳优化 2 2 国内外相关研究 因际上对位信息分析技术的研究已经丌眨了很多年，对r 位f l 息分析的：苗求芷f 1 鼬 着嵌入式领域的发展产生的，例如多媒体程序的处理，网络应用 i t n ，r - 的处理部包含火： 的位操作。如果硬件不提供特定指令支持这些操作，使用通用指令左实现这些操作将会 占用大量的c p u 时州，影响程序的效率。囡此现在很多嵌入式处理器都提供了 l 对位域 进行操作的指令，由此也产生了对位域进行研究分析的需求。现在国际上对位域的研究 主要包括位域信息的表示、基于位域的数据流分析、基于位域的寄存器分配、位操作指 令集的扩展等。 1 ) 位域的表示： 对于上面所提到的基于位域的研究，我们自然需要一种结构去表示这种倪域信息， 从而使其他优化可以使用这种信息来做相应的操作。r a j i vg u p t a 等人研究了一种用于位 信息分析的表示【2 】他们通过对赋值语句中等号右边的表达式位域的使用情况进行分析 来指导等号左边变量位域的划分。在划分完变量位域之后，通过全局的数据流分析建立 位域级的定值使用关系，通过引入c o m b m e 结点，将多个无用的位域重新合并成一个大 的位段。当遇到多个定值点位域划分冲突的情况，就可以将位域重新合并，再通过s p l i t 操作重新分割，生成一个个连续而且彼此不相交新的位域串。 常规的数据流分析是建立寄存器变量之间的定值使用和使用定值关系，它将寄存 器看作被处理的原子对象。而基于位信息的数掘流分析不仅要考虑寄存器变量之间的定 值使用和使用定值关系，同时需要考察寄存器中位信息的变化情况。通过对程序中位操 作指令的分析判断确定每个位操作指令对寄存器变量中位的影响，并将这种信息通过数 掘流进行传播从而最大可能的精确判断寄存器变量所使用的实际有效位。 2 ) 基于位域的寄存器分配： 由于寄存器是稀缺资源，对于嵌入式处理器更是如此。因此对于那些提供直接进行 位偏移寻址的操作指令来说，可以将多个互相不重叠的位域压缩到一个寄存器中，从而 节省寄存器的使用数量，减少s p i l l 数量，以提高程序的执行效率。s r i r a m a nt a l l a m 和 r a j i vg u p t a 已经做了这方面的研究工作【5 】，他们通过对位信息的分析，选出彼此不重叠 的位域，压缩到一个寄存器中这样通过位偏移寻址指令的支持可以显著的减少程序所 需要的寄存器的数量。他们的实验数据显示通过利用位信息分析实现这种全局的寄存器 分配可以将所需的寄存器的数量降低1 0 到5 0 。 2 3i x p 网络处理器指令集介绍 x p 网络处理器是针对网络包处理而优化设计的，对于包处理的特殊优化这一点可 以从网络处理器d 的指令集的设计中得到一定体现。在网络处理器的指令集中提供了 位段操作指令( 1 d _ f i e l d 和1 d - e e l d 二w _ c ”以及根据位段值进行分支跳转的指令( b r = b ”e 和 第二帝位域优化 b r ! = b y t e ) ；如果用通用处理器指令集的指令去实现同样功能的话，需要多条指令去实现， 而网络包处理中对于包头字段的提取是主要的网络处理任务，因此通过在处理器的指令 集中加入这种特定的指令，可以更有效的生成网络应用程序。 i x p 2 4 0 0 支持的位操作指令指令的功能描述 对a 投竹敌( a o p 用b 扫! ”敌( b - 叩执 r a i u o p 指止晌a l u 船们“ a l u d 船- t , ao p a l u _ o p b _ o p l 将结里t 给h 杯授竹数( d c s t 科bo p 址i ，so p _ s h f 析止册移仲若【们侈 ，后的鲐裳翱 一o f , 船 a i u _ s 鹏l ao p a l u _ o p bo p b 印s h q 叫u 投n “将结嫩哦鲶i j 钿投仉葛 群唧操f 1 数巾b 归j m 珩止“苜的千n 取- i ：翩b y t c _ c o m l r a r tv a l t 砷= b 归l i e b 姊b j u 姊电旦耵q 托u 融矗h 嗍 仿比戟蜘粜牛h 等瞄剑l a b e l # 所有i l 勃处 将嘲删翻1 啦符甜- 商坼f j 觑i 湘啪聊舭铀舭 坤= b 归p b g 脚o u n 脚b 印呻日e _ 啦b 衄嘲 蚧粜不等蒯畦纠址出所寸目l ，赴 。咿舳单划捣删硅珊，蝴柳中呐埽b b l 托d v 吐且q 曲娜呐_ e m u e s s t e _ o p o p u 吖j 咖 i 滓竹导月翩j 担一噶中忡腑d 晦埽中h 倒曲艟再生 ，哪，匕l 敏甲蜓酬航l 曲移 越觚黼螂中l 萨栅指 吐鼻b m j 伊睛i j 日昼脚电，删匦翱：- 印却u 吖p 棚 矗盟置 带导出并翩衄噼中鼬懈妇咩中刖世蝴j 掌 表2 1i x p 2 4 0 0 支持的位操作指令 为了利用处理器提供的这种特有指令，需要i x p 编译器提供相应的支持。位域优化 就是一种专门针对网络处理器中位域操作指令的编译优化技术。通过这种优化技术在最 终生成的代码序列中查找可以使用专用指令替换的通用指令集序列；如果存在这种序列 就实现相应的指令替换工作，已达到减少指令数的目的为了方便后面的讨论，表2 1 中列出了位域优化中使用到的i x p 2 4 0 0 处理器指令集中支持的位操作指令。其中a l u 操 作和a l u操作是两类算术运算指令，它们是由大的分类操作符或者 和小_ s h f ( a l u a l us h o 的运算操作符( 由a l uo p 操作符指定) 组成。其中a l u 操作表明算术运算类操作，a l us h f 操作表明带移位的算术运算类操作。b r = b y t e 和b r ! = b y t e 是一类特殊的跳转指令，它将通 用指令集中的跳转指令和比较指令的功能合成了一条指令，该指令具有四个操作数，其 中的前三个操作数实现了跳转条件的判断，相应的含义已在表中列出，最后一个操作数 是这条分支指令的跳转目标，根据前三个操作数运算结果进行相应的分支跳转。l df i e l d 和l df i e l dwc l r 是两条字节相关的操作指令，其中l df i e l d 实现了字节的插入运算，将 源操作数中的某个字节插入到目标操作数中，l df i e l dwc l r 则实现了字节的提取操作， 它将源操作数中的某个字节放到目标操作数相应位置中，并将目标操作数的其余位清零。 中田科学院颂i 学位论史血向i x p 州络妊坶器的位域优化和内联优化 2 4 优化机会 ( 1 ) a l u b 4 。2 5 5 a n d 。a l 】1 ) a l u b 4 2 5 5 a n d a l l ( 1 ) a = a o x f f , ( 2 ) a l u - 。2 4 0 b 4 】 ( 2 ) b r l 2 b y t e i a l 。0 , 2 4 0 ，一l l l 一拍】 ( 3 ) b n e l l t - l 一2 蜘 一b b 2 一f b o # 2 ) i f ( a o x f o ) b b 2 f o o # ( 3 ) a l u s h q a 3 一b ，b 1 5 】 ( 3 )c = b “5 ； ( 4 ) a l u _ s h t = 【a 3 一b ，b l 。“5 】 ( 4 ) b , l u i l 卅 ( 5 ) b r l l t i - l 卅 一l t i 2 # ( 4 )i 一l l l - 2 #( 5 ) a l u a 3 b 4 ，+ 8 a 5 1 ( 6 ) a l u a o 2 5 5 a n d 。b l 】 一l t _ l i # ( 5 ) e l s e 7 ) a l u a 3 b 4 + a o 】 ( 6 ) a l u _ s h q b o b 4 。o r a 3 。“2 4 】 一l t - l - i # ( 6 )c 。a 4 - ( b o x f f ) ； ( 8 ) a l u _ s h t i a 3 一，b ，a 3 ，( 2 4 1 ( 9 ) a l u b 0 ，b 4 ，+ a 3 1 ( 7 ) l ( 8 ) d = a 十( c “2 4 ) ： ( a ) 源代码 ( b ) 尢位域优化的扎编码 ( c ) 位域优化后的札编码 图2 2 位域优化代码示例 本节将通过一个实际的例子阐述实际代码中存在的位域优化机会。在图2 2 中给出 了一段c 程序以及用i x p 编译器编译生成的汇编指令序列。图2 2 ( b ) 是编译器在不采用 位域优化时生成的汇编指令序列；当不进行位域优化时，源程序中的第l 条位与( a n d ) 操作被转成了图2 2 ( b ) 中相同功能的汇编指令a l u b 4 ，2 5 5 ，a n d ，a 1 ，i f 语句被转成了一 条减法指令( 用于设定条件码寄存器) 和一条条件跳转指令b n e 【l t1l # 】，即减法指令 的两个操作数不等就跳转：否则，执行下一条指令a l us h f a 3 ，一，b ，b l ，“5 】，图2 2 ( b ) 中的第6 、7 两条指令完成源程序e l s e 分支中的语句，第8 、9 两条指令完成源程序中的 最后一条语句，也就是将变量c 的值先左移2 4 位和变量a 的值相加，并将结果赋给变量 d 。图2 2 ( c ) 是经过位域优化后的汇编码，从该图可以看出图2 2 ( b ) 中的第2 、3 两条指令， 被替换成了图2 2 ( c ) 中的b r ! = b y t e a l ，0 ，2 4 0 ，l tl2 胡( 该指令的意义见表1 ) ，之所以可 以替换是因为通过基于位信息的数据流分析可以发现操作数b 4 只有第1 个字节有效，因 此。我们可以使用图2 2 ( c ) 中的第2 条指令b r ! = b y t e 来完成图2 2 ( b ) 中相戍指令的功能。 同样可以用图2 2 ( c ) 中的第5 条指令a l u a 3 ，b 4 ，+ 8 ，a 5 】( 将a 5 的第1 个字节取出和b 4 相 加并将结果赋给a 3 ) 代替图2 2 ( b ) 中的第6 、7 两条指令，因为l x p 指令集中提供这种 a l u 操作指令，并且只有在b 操作数( 也就是这罩的a 5 ) 中的有效位是第1 个 节时j 能使用。因此必须通过分析操作数的位信息爿能确定能否使用该指令图2 2 ( b ) 中的最 后两条指令被替换成了图2 2 ( c ) 中的一条带移位的位或指令a l u _ s h q b 0 , b 4 ，o i t , a 3 ， o q 4 】t 之所以可以将原来的移位和加法两条指令替换成这条指令，足因为位信息分析可 以发现移位后的a 3 有效位信息是第3 个字节，而b 4 有效位信息是其第0 个字节，断定 两个操作数的有效位信息范围未发生重叠，因此该加法指令可以被转换成等价的位或指 1 2 第一二帝位域优化 令而不影响程序的正确性由于i x p 2 4 0 0 指令集中提供带移位的位或指令，可以将位或 运算和前面移位运算合并成一条带移位的位或指令( 如图2 2 ( c ) 中所示) ，这样两条指令被 转成了一条指令通过对比最终生成的汇编码，可以看出位域优化能够有效地利用1 x p 指令集提供的一些特殊指令来优化代码。 2 5 优化实现 位域优化技术主要分为二个阶段，第一个阶段是建立操作数的使用定值链及定值 使用链，这一阶段和传统编译器中的数掘流分析过程相同；第二个阶段利用6 u 一阶段数 据流分析的结果，通过定值使用链和使用定值链计算每个操作数的位信息；第三个阶 段根据第二阶段产生的位信息以及预先建立的匹配模板完成实际的指令合并工作。位域 优化静态地分析操作数的位信息，将分析得到的信息通过操作数的定值使用链传播下 去，编译器利用这些信息在c g i r ( c o d eg e n e r a t i o ni n t e r m e d i a t er e p r e s e n t a t i o n ，代码生 成阶段的中问表示) 中替换那些匹配的指令序列，生成高效的代码。 2 5 1 基于位信息的数据流分析 数据流分析是各种优化的基础，通过数据流分析可以揭示程序中操纵的变量之间相 互依赖关系，利用这种依赖关系进行各种程序优化。传统的数据流分析在寄存器操作数 之间建立定值使用链和使用定值链，而不提供更小粒度的位域信息，这无法满足位域 优化的要求，为此必须对传统数掘流分析加以扩充。我们采用的方法是在处理位操作指 令时，记录该操作对目标操作数位信息的影响，并将该信息通过定值一使用链传播到操作 数的使用点，实现基于位信息的数据流分析。 括餐 ；f 黼 扭a0 0 x x l | l lm ( j l n 【8 1 。0 静一 ( 2 ) o t a b i t t ：e 1 8 1 u ( m i d 卜k i l l b ) 图2 3 带位信息的数据流图 3 中国科学院碗士学位论文一血向i x p 叫络处理器的位域优化和内联优化 图2 3 给出了位信息在数据流图中的传播过程以及到达一定值数据流方程，方框表示 基本块( b a s i cb l o c k ，只有单个入口和单个出口的一段线性代码) ，花括号中列出了荩 本块入口和出口处各变量的位信息图下方给出了计算定值一使用链的数据流方程，第1 个流方程表示到达基本块入口处定值点的集合是该基本块所有前驱出口处活跃的定值点 ( o u t b ) 的并集，第2 个方程表示基本块出口处的定值点集合足到达该基本块入口处的 定值点( i ne b ) ，除去基本块中注销的定值点( k i l l b ) ，再加上基本块中新生成的定值 点( g e n b ) 。此外，对于具有多个定值点的变量，需要位信息合流运算，我们使用位或 运算作为合流运算，即变量在使用点的位信息是该变量所有定值点位信息的位或值。 假设变量a 和b 是函数的参数，它们的值在运行时才知道，因此，我们将初始位信 息设为0 x t f f f f l t f f 我们用位向量来记录变量的位信息，0 表示该位的信息对最终的计算结 果没有影响，l 表示该位的信息对最终的计算结果可能产生影响) ，通过这个位信息东记 录操作数中相应位是否有效，因此，0 x t f f l f f f f 表明该变量的所有位都可能对计算结果有 影响，位信息的值通过计算和传播不断被更新，到达固定点，这个位信息最终被用于指 导位域优化的进行。图2 3 中可以看到b b i 中的变量a 的位信息在完成& ( 位与) 操作后的 位信息变成了o ) 【f f 臣并被传播到b b 2 和b b 3 ，最终到达b b 4 中变量a 的使用点。对于 多定值变量，位信息是该变量所有定值点的位信息的位或运算，如图中所示，变量c 有 两个定值点，分别位于b b 2 和b b 3 ，而这两个定值点的位信息不同，因此就存在一个位 信息合流运算的问题，为了保证b b 4 中变量c 的位信息能够表示b b 2 和b b 3 中两个定 值的位信息，我们将b b 2 和b b 3 中的位信