（计算机软件与理论专业论文）非局部跳转控制流的自动消除.pdf

摘要 在c 程序的并行化编译研究中，我们通常希望能尽可能地借鉴已经比较成 熟的f o r t r a n 程序并行化技术。但由于c 程序有一些f o r t r a n 程序所不具 有的特性，如非局部跳转、指针和递归函数等等，使得一些比较好的分析及并 行化技术无法直接用于c 程序的并行化。因此对于这些特性的研究就成为c 程 序并行化编译研究的很重要的部分。，、 ， jc 程序中非局部跳转控制流的出现使得程序控制流图复杂化，并使原有的 过程间数据流分析和指针分析等技术无法有效使用，妨碍了最终的并行化工作。 目前这方面的研究还比较少，而且现有的技术是在分析阶段对这种情况进行额 外处理，这导致已经很复杂的分析阶段负担加重，因而这种处理通常是相当保 、0 守的。) 本文通过分析c 程序中非局部跳转控制流的特点，提出了一个通过等价 程序变换消除非局部跳转流的方法，并对该方法在不同情况下的正确性进行了 阐述和证明。我们的方法是采用g o t o 和r e t u m 等语句来模拟非局部跳转控制流， 在不改变程序原有功能的情况下消除了程序中的非局部跳转控制流。该方法可 以在一个程序结构化的一个独立的阶段实现，因此可以把非局部跳转控制流对 并行化编译的其它阶段，尤其是分析阶段的不利影响最小化。同时该方法也有 助于提高程序结构化程度，有利于对程序的分析和并行化。 ， 本文所介绍的所有算法都已在我们实验室开发的c 程序分析工具a g a s s i z 系统中实现，并用于分析实用c 程序，实验证明这种消除非局部跳转控制流的 ， 方法是正确有效的。1 ，一5 a b s t r a c t i nt h er e s e a r c ho np a r a l l e l i z i n gc o m p i l e r sf o rc ，w eu s u a l l yw a n tt o u s et h o s e t e c h n i q u e st h a th a v eb e e nu s e de x t e n s i v e l y i np a r a l l e l i z i n gc o m p i l e r sf o rf o r t r a n b u tc p r o g r a m sh a v es o m ep r o p e r t i e st h a ta r en o tf o u n d i nf o r t r a n p r o g r a m s ，f o r e x a m p l e ，n o n l o c a lc o n t r o lf l o w , p o i n t e r ，r e c u r s i v ef u n c t i o n ，e r e t h e s ep r o p e r t i e sh a v e p r e v e n t e d u sf r o mi m m i g r a t i n gs o m eg o o dt e c h n i q u e sd i r e c t l yf r o mf o r t r a n c o m p i l e r s t occ o m p i l e r s t h e r e f o r e ，s t u d y i n gs u c hp r o p e r t i e sb e c o m e sav e r y i m p o r t a n ta s p e c to f o u rr e s e a r c ho n p a r a l l e l i z i u gc o m p i l e r s f o rc n o n l o c a lc o n t r o lf l o wi nc p r o g r a m s n o to n l yc o m p l i c a t e dt h ec o n t r o lf l o wg r a p h ，b u t a l s oi m p e d et h ei n t e r p r o c e d u r a ld a t af l o wa n a l y s i sa n d p o i n t e ra n a l y s i s f i n a l l yi t w i l l d oh a r mt ot h ep a r a l l e l i z a t i o nw o r k o n l yaf e ww o r kh a sb e e nd o n eo i ln o n l o c a l c o n t r o lf l o w , a n dc u r r e n tm e t h o di st oc o p ew i t l ln o n l o c a lc o n t r o lf l o wi nt h ea n a l y s i s p h a s e t h i sh a sp u te x t r ab u r d e no nt h ea n a l y s i sp h a s e t h a ti sr a t h e rc o m p l i c a t e d ，s o s u c hm e t h o di sa l w a y sc o n s e r v a t i v e a f t e ra n a l y z i n gt h en o n l o c a lc o n t r o lf l o wa p p e a r e di ncp r o g r a m s ，w ei n t r o d u c e da n e wm e t h o dt h a tc a nr e m o v en o n l o c a lc o n t r o lf l o w b ye q u i v a l e n tp r o g r a m t r a n s f o r m a t i o n i t sc o r r e c t n e s si sa l s oe x p l a i n e da n dp r o v e di nt h i sp a p e r o u rm e t h o d u s e st h ec o m b i n a t i o no fg o t oa n dr e t u r ns t a t e m e n tt os i m u l a t et h es e m a n t i c so f n o n l o c a lc o n t r o lf l o w t h i sm e t h o dc a l lb ei m p l e m e n t e di nas e p a r a t e dp h a s eo f p r o g r a ms t r u c t u r i z a t i o n ，t h u st h ed i s a d v a n t a g ec a u s e db yn o n l o c a lc o n t r o l f l o wt o o t h e r p h a s e s ，e s p e c i a l l y t h e a n a l y s i sp h a s e ，i s m i n i m i z e d w h a ti s m o r e ，t h e t r a n s f o r m a t i o nm a k e st h ep r o g r a mm o r es t r u c t u r e d ，w h i c hi sb e n e f i c i a lf o ra n a l y s i s a n d p a r a l l e l i z a t i o n a l lt h ea l g o r i t h m sp r e s e n t e di nt h i st h e s i sh a v e b e e ni na g a s s i z ，a na n a l y z i n gt o o lf o r c p r o g r a md e v e l o p e db yo u rl a b e x p e r i m e n t r e s u l l sh a v ep r o v e dt h ec o r r e c t n e s sa n d e 任b c t j v e n e s so f o u rm e t h o d 非局部跳转控制流的自动消除 第1 页共3 7 页 1 1 并行化编译器 第一章引言 随着硬件技术的发展，采用最新微处理器构建的共享内存多处理器( s m p ) 已经得到了广泛的使用，但编写并行程序的困难成为了我们充分利用并行计算 机资源的主要障碍【5 【2 8 】 3 1 】。为了解决这个问题，人们开始研究并行优化编译 系统。并行优化编译系统是一个可以将串行程序自动地转换为等价的并行程序 的编译器或预处理器，其目标是在并行计算机上使程序代码得到最大限度优化 并使程序的并行性得到尽可能的开发，以获取理想的加速比。并行优化编译系 统是并行计算机系统上开发高效软件的基础，它不但把程序员从复杂的并行处 理概念中解放出来，同时并行化编译技术的研究还可以为并行语言的设计提供 依据并有效地界定语言、编译和用户的责任【3 1 】。 在过去二十年中，对f o r t r a n 程序的并行优化技术研究取得了很大的进 展，国内外先后研制出了几个典型的并行优化系统，其中具有代表性的系统有 斯坦福大学的s u i f 2 9 ，伊利诺依大学的p o l a r i s 6 】，与复旦大学的a f t 3 0 等。 各种渠道发表的论文及系统测试数据都表明对串行f o r t r a n 程序的并行优化 已经逐步趋于成熟。 与f o r t r a n 程序的并行优化所取得的进展相比，c 程序的并行优化至今 没有取得实质性的进展。作为一门目前使用得非常广泛的高级语言，c 语言包 含了许多f o r t r a n 语言所不具有的语法特点，如非局部跳转、多级指针的使 用、内存的动态分配、函数的递归调用等。c 语言与f o r t r a n 语言的这些区 别决定了对c 程序的并行优化必然与对f o r t r a n 程序的并行优化有显著的不 同，而正是由于这些区别的存在，在一定的程度上无疑加剧了c 程序并行优化 的难度【1 】 3 2 。 非局部跳转控制流的自动消除 第2 页共3 7 页 1 2 非局部跳转控制流 非局部跳转控制流是由对系统调用肠馅n 妒和s e q m p 引起的控制流。执 行l o n g j m p 可以使程序直接跳到另一函数的某个s e t j m p 处，这类似于执行g o t o 语句后可以使程序跳到某个标号处，如图1 所示。z - 者不同之处在于g o t o 语句 只能在一个函数体以内跳转，而l o n g i m p 可以直接跳到另一个函数体内的 s e t j m p 。可以看到在图1 中当函数g 调用l o n g m p 后，程序将直接跳回m a i n 函 数中s e t j m p 所在语句处继续执行。 非局部跳转控制流是一种不规则的控制流，对数据流分析以及程序的并行 优化产生了不利影响。首先，含有s e t j m p 或f o n ，印的函数调用无法看作为一 个单入口单出口的语句块，原有的过程间分析技术在这种情况下不能适用【3 3 】。 其次，非局部跳转控制流破坏了程序的结构性，这使得有些对程序结构性要求 比较高的分析技术无法使用，导致分析结果比较保守，对最后的并行优化产生 不利影响。最后，原有的数据流图和调用图都无法反映非局部跳转控制流，如 果对它们进行改进以使其可以反映这种控制流，则势必导致数据流图和调用图 的数据结构都变得相当复杂。 l o n g ，r a p 和s e t j m p 主要用来处理例外情况，系统程序中通常都包含这两个 调用，在s p e c 9 5c i n t 的八个程序中有三个程序( g c c 、t i s p 和p e d ) 用到了l o n g m p 和s e t j m p 。因此对这个问题的解决具有实用价值。 m a i n ( ) v o i d f o l ： g o t o l ； ) ( a ) g o t o 语句 咖 婶 删节ffff朐 一蛾 献 。 嘲 非局部跳转控制流的自动消除 第3 页共3 7 顶 d r o c i p r o c 2 ( ) i n t - t os e t s 图2 s u i f 在指针分析阶段对i o n g j m p 的处理 1 3 相关的工作 由斯坦福大学开发的并行优化系统s u i f 对非局部跳转控制流问题进行了 一定的处理。在s u i f 的指针分析阶段，当分析程序遇到l o n g j m p 时，它将找到 当前调用栈中所有函数的函数体中的s e t j m p ，并把当前指针指向信息( p o i n t - t o s e t s ) 复制到每个这样的s e t j m p 的调用点上【1 】，如图2 所示。 s u i f 的方法是安全的但不够准确。它并没有考虑一个l o n g r a p 可能到达哪 些s e t j m p ，也没有分析一个s e 玎m p 可能由哪些l o n g j m p 到达，因此其复制的指 针信息中有相当一部分是多余的，得到的分析结果必然比较保守。另外，由于 是在分析阶段处理非局部跳转控制流，这意味着在分析阶段的其它各种分析中 仍需要分别考虑这个问题，导致已经比较庞大复杂的分析阶段又增加了新的负 担。 然而除s u i f 外，目前的并行与优化编译系统中都没有对非局部跳转控制 流问题进行处理，这使得我们对那些有非局部跳转控制流的程序无法进行有效 地并行和优化。因此，这个问题成为了我们研究c 程序并行优化工作的一个重 要部分。 1 4 本文的贡献及结构安排 通过对l o n g m p 和s e t j m p 的语法以及程序中非局部跳转控制流的出现特点 9 非局部跳转控制流的自动消除 第4 页共3 7 页 进行分析，我们发现可以通过程序变换的方法消除非局部跳转控制流，其原理 如图3 所示。根据这个思想，本文将提出一个消除非局部跳转控制流的算法。 该算法采用逐层r e t u r n 和g o t o 语句来模拟非局部跳转的语义，在不改变程序原 有功能的情况下消除非局部跳转控制流。采用这个算法，我们可以在程序结构 化中个独立的阶段对非局部跳转问题进行处理，避免了修改已经比较复杂的 的程序分析阶段，尽量减少l o n g i m p 对数据流分析和并行优化阶段的影响。同 时该算法还有助于程序的结构化，最终有利于程序的并行优化。 本文第2 章对c 程序并行优化系统a g a s s i z 进行简单的介绍，第3 章详细 介绍l o n g r a p 与s e t j m p 的语义和使用特点，第4 章给出一个可在简单情况下使 用的算法，对被处理的程序有较多限制条件，第5 章进一步讨论第4 章提出的 算法，并提出改进措施，以尽可能减少限制条件，第6 章对s p e c 9 5 中的1 3 0 l i 进行实例分析，第7 章对本文进行总结，并展望以后发展的方向。 五) ( a ) 执行i o n g j m p 实现的非局部跳转( b ) 用逐层悖t u m 来模拟非局部跳转 图3 消除 o n g j t n p 的原理 甲 非局部跳转控制流的自动消除第5 页共3 7 页 第二章c 程序并行优化系统a g a s s i z 概述 2 1 并行优化编译的流程 一个并行优化编译系统可以大致分为五个部分，如图4 所示。 图4 并行优化编译的流程 第一部分是p a r s e r ，即语法分析器，它负责读入c 语言程序并将其转换为 编译器内部的程序中间表示( i r ) 。这一部分相对比较简单，有现成算法和工具 可以使用，因此不属于并行优化编译研究的重点。在a g a s s i z 中程序的中间表 示是语法树，因此在p a r s e r 阶段之后的各阶段看到的程序都是以语法树形式出 现的。 第二部分是c l e a n u p ，在这一部分系统将在语法树上对程序进行一定的处 理，消除程序中不规范的成分，从而使i r 的结构简单化，并使后继的各种分析 得以简化。这一步的规范化处理包括以下两部分：语句与表达式的规范化，控 制流的结构化。 第三部分是a n a l y s i s ，这是并行优化编译系统中最庞大复杂的部分，通常 直接影响到最终并行优化结果的好坏。这部分根据分析所涉及的函数个数可以 分为过程间分析( i n t e r p r o c e d u r a la n a l y s i s ) 和过程内( i n t m p r o c e d u r a la n a l y s i s ) 两部分，但这两部分并非完全割裂，而是相互关联的。一般来说我们以过程间 分析为框架，在分析到具体函数内部时又要使用过程内分析。根据分析对象的 不同又可分为指针分析、标量分析、数组分析和相关性分析等等。 萝 非局部跳转控制流的自动消除第6 页共3 7 页 第四部分是p a r a l l e l i z a t i o n & o p t i m i z a t i o n 。到这里我们才开始真正地对程序 进行并行优化。常规的优化包括死码删除、常数传播和代码外提等等，而在并 行化中则有数组私有化、循环合并和变量规约等各种手段。这部分和a n a l y s i s 阶段是紧密相连的，对程序的并行优化工作需要使用到在a n a l y s i s 阶段中获得 的数据。 最后一部分u n p a r s e r 所包含的工作也比较简单，它把语法树转换为带编译 指导的并行c 程序，这样的c 程序可以直接由并行编译器编译，生成最终可在 并行机上并行执行的目标代码。 2 2a g a s s i z 系统中i r 的层次结构 作为f 程序分析工具中的程序中间表示，a g a s s i z 的朋必须能够准确而完 备地表示任何符合a n s i 标准的f 程序。也就是说，f 源程序中的每一种语法单 位都应该在a g a s s i z 系统的厢内通过相应的对象来表征。事实上，任何一个f 程序都可以用如下的产生式规则抽象地描述： p r o g r a m ：? = f i l e + f i l e ：= d e c a t a t j o n + p r o c e c u l a p r o c e d u r e ：? = t y p e 。+ p r o c n a m e + p a r a m e t e r * + p r o c e d u r e b o d y p r o c e d u r e b o d y ：= c o m p o u n d e t m t c o m p o u n d s t m t ：= l a b e l o + d e c i a r a t j o n 心t m t + s t m t ：= l a b e l o + a s s i g n s t m t | i fs t r u t | f o r s t m tlc o m p o u n d s t m t a s s i g n s t m t ：= d e n t i f i e r + = + e x p t 各种语句的具体的语法结构) e x p ：= u n a r y e x p | b i n a r y e x ptt r i n a r y e x p l i s t e x p u n a r y e x p ：| 一| ! |+ o p e r a n d b i n a r y e x p ：= o p e r a n d + i ，| | + | 一| ( ) | ( ) l + o p e r a n d t r i n a r y e x p ：= 9 p e r a n d ? o p e r a n d ：o p e r a n d i o p e r a n d ：o p e r a n d ：o p e r a n d l i s t e x p ：= o p e r a n d , e r a n d , o p e r a n d o p e r a n d ：= - d e n t i l l e rlc o n s t a n t | e x p | t y p e ：= s i m p l e t y p ela r r a y t y p e | p o i n t e r t y p e s t r u c t t y p e | s i m p e t y p e ：= i n t e g e r f m h r c h a r 根据上面的产生式规则，在对i r 进行面向对象设计时尽量抽取出各对象的 共性，再根据对象的继承关系用隐式内存管理的原则设计取用户层和i r 系统 层，i r 内各主要对象间的关系请参见图5 。 非局部跳转控制流的自动消除 第7 页共3 7 页 图5 a g a s s i z 中i r 各对象间的关系 2 3 语法树的统一表示 由于大多数的程序分析都是在对语法对象进行遍历的过程中完成的，因此 对任意的语法树对象进行遍历是程序分析系统一个非常重要的操作。为了提高 整个系统的效率，避免递归的频繁使用，a g a s s i z 系统采用统多叉树的形式 非局部跳转控制流的自动消除 第8 页共3 7 页 来表示语法对象，这种统一的语法树表示方法为语法树对象的有效遍历提供了 基础。 在a g a s s i z 系统语法树的多又树表示方法中，子语法对象与某个位置上的 子树对应，而不用类中的某个数据成员来表示。语法树上的每个结点都是一个 语法对象，虽然所有的对象都通过统一的语法树形式相连，但不同的对象有不 同的接口函数，朋用户可以通过这些接口函数来实现对语法树对象的操作。 在a g a s s i z 系统内的多叉树表 示法中，每个树结点对象有四个 p o i n t e r s y n t a x b a s e ) 类型的指针 ( 如左图所示) ，它们分别指向父 图6 多叉树的结点示意图 对象、左邻兄弟对象、右邻兄弟对 象与第一个儿子对象。这样便导致 一个多叉树对象在访问子语法对象时，效率不太高，因为它必须从第一个儿子 开始访问。对于一般的语法对象，如果多叉树的出度是常数，多叉树访问子对 象的效率，较之数据成员表示法的效率为一个小常数。 下图是一小段程序及其在a g a s s i z 系统中的语法树表示。 图7 a g a s s i z 系统中语句的语法树表示实例 采用多叉树的表示方法，语句和表达式可以被统一表示，这样在程序分析 非局部跳转控制流的自动消除 第9 页共3 7 页 过程中只要用一种遍历方式便可以实现对整个语法树的遍历分析，这不但简化 了上品内部遍历方法的实现，还极大地方便了膪用户对豫的使用。 非局部跳转控制流的自动消除 第l o 页共3 7 页 3 1 语法 第三章l o n g j m p 与s e t j m p 在第一章提到过，i o n g j m p 和s e t j m p 的关系类似于g o t o 语句和标号之间 的关系，执行j o n g j m p 可以跳到某个s e t j m p 的调用点。这种非局部跳转和一种 类型为i m p _ b u r 的变量密切相关， o n g j m p 和s e t j m p 都要以这种变量作为参数。 其工作原理如下：当s e t j m p 被调用时，调用点的地址就被保存到了作为s e t j m p 参数的i m p _ b u r 变量中；此后，当以相同j m pb u f 变量作为参数的 o n g j m p 被 调用时，保存在里面的地址就被读出，程序就跳到先前那个s e t j m p 的调用点继 续执行。 需要注意的 o n g j m p 和s e t j m p 的语法有以下几点 1 当以同一j m p _ b u f 变量为参数的不同s e t j m p 先后被调用时，后来调用 的s e t j m p 将覆盖前面的s e t j m p 写在i m p _ b u r 变量上的内容。如果此 时以这个j m pb u f 变量为参数的 o n g j m p 被调用，它的跳转目标是最 近被调用的那个s e t j m p 调用点。 2 在不同的情况下，s e t j m p 有不同的返回值。如果s e t j m p 是被直接调用 的，那么它的返回值为0 。而如果它是由某个l o n g j m p 跳转过来的，它 的返回值为 o n g j m p 的第二个实参的值。唯一的例外是，当 o n g j m p 的第二个实参值为0 时，s e t j m p 的返回值为l ，这可以保证从s e t j m p 的返回值是否为0 可以判别s e t j m p 是否被直接调用。图8 所示程序中， 当m a i n 函数中语句“v a l u e = s e t j m p ( j u m p e r ) ：”第一次执行后，v a l u e 的值为0 ，因此f 和g 将相继被调用。之后当g 函数中的l o n g j m p 被调 用后，程序又回到m a i n 函数中s e t j m p 的调用点，此时v a l u e 将被赋 值为1 ，即l o n g j m p 第二个实参的值。 非局部跳转控制流的自动消除 第l i 页共3 7 页 # i n c l u d e j m pb u fj u m p e r ： i n tf l a g ： v o i d g o ( f l a g = l ： l o n g j m p ( j u m p e r ，1 ) 1 v o i df ( ) g ( ) ： v o i dm a i n 0 f i n tv a l u e ： f l a g = o ； v a l u e = s e t j m p ( j u m p e r ) i f ( v a l u e ! = 0 ) e x i t ( v a l u e ) ： f ( ) ： r e t u r n ： 图8 一个包含l o n g j m p 的简单程序 t x 图9 i o n g j m p 不能跳出当前调用栈之外 3 因为在i m p _ b u r 变量中保存的仅仅是s e t j m p 调用点的地址信息，因此 从 o n g j m p 跳到某个s e t j m p ，程序不会完全恢复到调用这个s e t j m p 时 的状态。如果一个全局变量的值在调用s e t j m p 和l o n g j m p 之间被修改， 那么调用l o n g j m p 后这个变量的值仍为修改之后的值。仍以图8 中程 序为例，全局变量f l a g 在第一次调用s e t j m p 时值为0 ，而在调用l o n g j m p 之前被修改为l ，当程序由l o n g j m p 直接跳转到s e t j m p 后，f l a g 的值 仍然为l ，而不会恢复为0 。 4 作为l o n g j m p 调用目的地的s e t j m p 调用点所在的函数必须在当前调用 栈上，如图9 所示。如果目的s e t j m p 所在函数不在调用栈上，程序执 行将出现非法错或其它无法预料的结果。这个性质对本文提出的算法 来说非常重要，因为这意味着从 o n g j m p 所在函数可逐层返回到目的 非局部跳转控制流的自动消除 第1 2 页共3 7 页 s e t j m p 所在函数。具体如何利用这个性质来变换程序将在第四章中详 细介绍。 3 2l o n g j m p 和s e t j m p 的使用特点 从语法角度来说，对 o n g j m p 和s e t f i m p 的使用限制不多，只要满足1 0 n g f i m p 的目的s e t j m p 所在函数仍在调用栈中，它们的使用是非常自由的。而j m pb u f 变量类似于静态指针或一般指针，它可以作为函数的参数，i m p _ b u r 变量之间 在某些情况下( 见后面5 3 节) 也可以相互赋值。另外也可以通过b c o p y 等系 统调用把一个i m p _ b u r 变量的内容拷贝到另一个i m p _ b u r 变量。此外在某些数 据结构中可能包含类型为i m p _ b u r 的域。 在实际程序中， o n g j m p 、s e t j m p 和i m p _ b u r 变量的使用有一定的规律。 j m p _ b u f 变量的内容一般只在调用s e t j m p 时被修改，在调用 o n g j m p 时被读出。 而s e t j m p 调用后，程序通常有两个分支。个分支是当s e c j m p 是由 o n g j m p 跳转过来的情况，这表明程序出现了某种不正常的情况，需要运行一些善后的 代码。另一个分支则是正常运行的代码。s e t j m p 的使用模式如下图： v a l u e = s e t j m p ( b u f f e r ) ： i f ( v a l u e ) 半值非0 ，说明从某个l o n g j m p 跳转过来。执行一些清理工作 e l s e a 正常执行的代码 图1 0 s e t j m p 的使用模式 l o n g j m p 遇到某些异常情况时被调用，在不同的地方被调用或者碰到了不 同的异常情况， o n g j m p 的第二个参数往往有不同的值，这样当跳回到s e t j m p 时，就可以根据不同的返回值执行不同的善后代码。 非局部跳转控制流的自动消除 第1 3 页共3 7 页 第四章简单情况下的变换方法 4 1 基本思想 在3 1 节中提到过，作为 o n g j m p 调用目的地的s e t j m p 调用点所在的函数 必须在当前调用栈上。根据这个性质我们可以知道，从l o n g j m p 的调用点沿调 用链逐层返回可以到达s e t j m p 调用点所在函数。本文所提出的算法就是利用这 个性质，采用逐层返回以及局部跳转来模拟非局部跳转的语义，从而达到消除 程序中非局部跳转控制流的目的，其原理如图1 1 所示。为便于讨论与理解，本 章将首先考虑符合一些约束条件的程序的变换。在下一章中将进一步讨论算法 的改进与约束条件的消除。 非局部 p 卜逐r 层e t u 返r n 回 一局嚣蔬转 图11 用逐层返回和局部跳转模拟非局部跳转 t e m p = i + + ： v 。a t e m p ； i f ( s e t j m p ( b u f f e r ) ) t e m p = s o t j m p ( b u f f e r ) ； i f ( t e m p ) ) 图1 2 程序规范化 非局部跳转控制流的自动消除 第1 4 页共3 7 页 4 2 约束条件 在本文提出的算法中，所处理的程序是规范化后的程序。在规范化后的程 序中，所有具有副作用的表达式与操作符都被转化为等价的无副作用的表示， 函数调用的实参被转化成简单变量，函数调用只单独出现在函数调用语句或者 单独出现在赋值语句的右部。一个程序即使不满足上述条件，我们也可以通过 一定的等价变换手段使其满足这些条件。有关程序规范化更详细的介绍以及其 实现，请参阅【3 2 】。图1 2 是对两个对程序段进行规范化的例子： 为方便讨论，本节提出的基本算法对所处理的程序有进一步的约束条件。 这些约束条件包括： 1 程序中不包含s i g n a l 调用； 2 没有递归函数和函数指针： 3 j m pb u f 变量只以标量形式作为l o n g m p 和s e t j m p 的参数被引用。 4 3 关键词 在本文后面部分需要用到一些关键词，这里先对这些词进行介绍。算法的 输入称为源程序，输出称为目标程序，二者都为c 程序，且目标程序中没有非 局部跳转控制流。目标程序中对应于源程序中l o n g ，r a p 和s e t j m p 的位置分别称 为l o n g r a p 点和s e t j m p 点。 图1 1 中给出了算法的基本思想，即采用逐层返回和局部跳转模拟非局部 跳转，从p r o c n 中的l o n g r a p 点开始逐层返回( r e t u r n ) ，到达p r o c l 后可以通过非 局部跳转( e , o t o 语句) 跳到p r o c l 中的s e t j m p 点。因此，目标程序的运行可以分为 两种状态，处于模拟非局部跳转的逐层返回状态称为跳转状态，其余正常运行 状态称为正常状态。图1 1 中虚线所代表的状态即为跳转状态。程序从l o n g r a p 点开始进入跳转状态，到达目的s e t j m p 点后恢复为正常状态。程序在进入跳转 状态之后，其目的s e t j m p 点便已确定，不可以改变。 非局部跳转控制流的自动消除 第l5 页共3 7 页 4 4 算法概略 当程序处于跳转状态时，需要知道目的s e t j m p 点的位置。为了解决这个问 题，我们采用编号的方法来区分不同的s e t j m p 点。假如程序中有n 个s e t j m p 点，将它们从0 到n 一1 进行编号，编号顺序任意。这样在没有递归调用的情况 下，从0 到n 一1 的n 个整数值一一对应于程序中的n 个s e t j m p 点，也一一对应 于源程序中的n 个s e t j m p 调用。对我们的算法来说，这种一一对应关系是静态 的，可以在算法执行之前建立。但是对于目标程序来说，它还需要一个c 语言 能识别的程序位置标识，这样才能保证最后的局部跳转可以达到正确的位置。 因此我们给每个s e t j m p 点所在位置增加一个标号，从而在s e t j m p 点编号和标 号之间建立了一一对应关系。在上面两种对应关系都建立之后，无论是在本文 的变换算法还是在目标程序中，我们都有办法确定目的s e t j m p 点的位置。 目标程序中在进入跳转状态之后，有两个值需要从l o n g j m p 点传回目的 s e t j m p 点。一个是目的s e t j m p 点的编号，另一个是源程序中 o n g j m p 的第二 个参数的值。因为在跳转状态下这两个值都是确定的，所以可以用两个全局变 量来传递这两个值，它们在 o n g j m p 点被赋值，在逐层返回的过程中和目的 s e t j m p 点都可以获得它们的值。 在图1 3 中给出了在实现基本算法时对调用链上有关位置的不同处理，其中 假定源程序中s e t j m p 所在语句为“r = s e t j m p ( b u r ) ：”，g k 和gk + l 为从g ，到f 这 条调用链上的任意两个相邻的函数。在 o n g j m p 点，程序开始进入跳转状态， 并以某种方法获得目的s e t j m p 点的编号，加上原 o n g j m p 第二个参数，分别赋 值给两个全局变量。赋值完之后，可以判断目的s e t j m p 点是否在当前函数，如 果是就可以直接跳转过去，否则就直接返回。由于一个函数有哪些s e t j m p 点是 可以通过分析程序得到的静态信息，因此，我们可以通过目的s e t j m p 的值来判 断它是否在某个函数中。 对调用链中的其它函数调用，当它返回之后，如果程序处于跳转状态，则 必须判断目的s e t j m p 点是否在当前函数，如果是就必须执行跳转，否则继续返 回。在s e t j m p 点，如果程序处于跳转状态，首先从全局变量中得到从 o n g j m p 传来的值。然后标记程序进入正常状态。 l 墅曼塑墼篓蔓堕些型塑旦塑型壁l 一 笙! ! 基基! ! 夏 f v n ) 硝 o n g j m p ( b u fv ) ( v 。n ) ( a ) 用逐层返回模拟非局部跳转 ( v - n ) 为在遥层返回过程中需要 一步步传回去的一时值v 为 l o “g j m p 的第二个事敷，n 为目的 s e j m p 点的住置 设置程序处于跳转状态： 获取目的s e q m p 点的位置： 设置跳转所传的值： 哦目的耗u m p 点在当前函数) g o t o 目的s e t j m p 点： e l s e m f u m ： ( d ) 对i o n g j m p l 拘处理 图1 3 对调用链上有关位置的不同处理 这里还有两个问题没有解决。第一是如何判断程序处于何种状态，第二是 如何在，。脚点获得目的鼬f 向点的编号。第个闯题比较简单，可以用 个全局布尔变量来判断程序所处的状态，它的值在f d 咖点置为1 ，在s p 卿 点置为o ，这样当这个变量值为1 是表明程序处于跳转状态，为0 表示处于正 常状态。 第二个问题稍许有些复杂。在源程序中，目的船咖节的地址保存在咖l p 一6 矿 变量中，d 咖通过咖妒j 变量来获取目的船珈妒的地址( 其具体实现可能 随不同的系统而有所不同) 。在目标程序中，由于s e t j m p 和l o n g r a p 都已经不存 在，聊矿原有的作用已经消失，可能需要其它变量来记录目的咖点的 编号由此，对应于源程序中每个j 哪旷变量在目标程序中定义一个箍型变 非局部跳转控制流的自动消除 第1 7 页共3 7 页 量，称为其跳转点变量。用以记录s e t j m p 点的编号。跳转点变量的值在与其对 应的s e t j m p 点被修改为这个s e t j m p 点的编号，在与其对应的l o n g i m p 点被读出。 这样在执行到任一l o n g m p 点时，通过读取与这个f d 憾即点相应的跳转点变量 的值就可以知道目的s e t j m p 点的编号。 可以为每个j m pb u f 变量新定义一个变量作为其跳转点变量，对本节讨论 的算法来说这样做完全是可行的。但是在某些情况下，例如源程序中存在含有 j m p _ b u f 域的结构，则重新定义变量的方法会引起很大的麻烦，限制了算法的 使用范围。考虑到j m p _ b u f 变量原有的作用在目标程序中已不再需要，可以利 用原有的i m p _ b u r 变量来定义跳转点变量。首先在目标程序中重新定义i m p _ b u r 的类型，计算n = s i z e o f ( i m p b u f ) s i z e o f ( i n t ) ，定义i m p _ b u r 为长度n 的整 型数组，这样可以保证新类型和原来的类型大小相同。然后对应于源程序中每 个j m p _ b u f 变量b u f ，目标程序中b u f o 用作其跳转点变量。这里之所以选择 b u f 0 并非是必须的，实际上可以选择任意的b u f n ( 0 n n ) 作为跳转点变 量而不影响算法的正确性。类似的，在下一章中我们采用b u f 1 作为深度变量 也是一样的道理。 当源程序中i m p _ b u r 的大小不是i n t 大小的整数倍时，会导致新定义的 i m p _ b u r 类型与原来大小不一致。如果出现了这种情况，可以定义新的j m p _ b u ， 类型为字符数组，这样总可以保证与原来i m p _ b u r 类型大小相同，只是在后面 的算法中需要考虑字符与整型之间类型转换问题，算法的正确性不会受到影响。 在实际系统中还没有发现上述情况，为了讨论的方便，后面的部分都假定原 i m p _ b u r 类型大小为i n t 大小的整数倍，即定义j m p _ b u f 为整型数组。同样这 里也不考虑原来j m p _ b u f 类型大小比i n t 两倍还小的情况。 4 5 具体算法 算法可以分为6 步。 s t e p l ：给程序中出现的所有s e t j m p 调用进行编号。 s t e p 2 ：改变j m pb u f 的类型，相当于把源程序中的“# i n c l u d e ” 替换为“t y p e d e f i n t j m p b u f n ：”，这里n 是一个常数， 非局部跳转控制流的自动消除第1 8 页共3 7 页 n = s i z e o f ( j m p _ b u f ) s i z e o f ( i n t ) 。 s t e p 3 ：增加全局变量j u m p s t a t u s 、s e t j m p p o i n t 与l o n g j m p v a l u e ，并置 j u m p s t a t u s 的初始值为0 。j u m p s t a t u s 的取值为0 或1 ( 1 表示处于 跳转状态，0 表示处于正常状态) ；s e t j m p p o i n t 表示当处于跳转状态 时，目的s e t j m p 点的编号，s e t j m p p o i n t 的值只有在j u m p s t a t u s 值 等于l 时才有效；l o n g j m p v a l u e 用于保存l o n g j m p 调用中第二个参数 的值。 s t e p 4 ：对每个s e t j m p 的调用点( 设此s e t j m p 调用的编号为k ，参见s t e p l ) ： v a l u e = s e t j m p ( j u m p e r ) ：宰j u m p e r 为j m p _ b u r 变量 把旧j 卯= s e t j m p ( j u m p e r ) 库 换成： s e t j m p k ：j u m p e r l