（计算机软件与理论专业论文）程序结构化和数组私有化.pdf

程序结构化和数组私有化 第l 页共3 5 页 摘要 并行化编译是并行处理中的重要一环矿本文详细介绍了并行化编译中的两个 相关方面。其一是程序结构化，其二是数组私有化。 ( 早期的大量应用程序普遍存在g o t o 语句，这样的非结构化程序给并行编译 系统的分析和变换带来了极大的障碍。而且也影响了程序本身的可读性和可维护 性。，j 本文提供了一种程序结构化方法，在控制流图的基础上将不同的g o t o 转换 为语义等价的标准的w h i l e 或i f 语句，使f o r t r a n 程序在不改变程序语义的前 提下，变换成只有循环，分支及顺序三种结构的结构化程序。 旧前人们通常单纯用增加临时变量和相关判断的方法，或者使用共享代码拷 贝的方法来消除g o t o 语句。但前一种方法会造成判定增加，语义分析困难；而 后一种虽然使转变后的程序结构清晰，但却造成b e n c h m a r k 中的某些程序急剧膨 胀。针对上述问题一本文提出了能控制膨胀的代码拷贝的算法。另一方面，本文 中对不可规约的程序进行了规约化，解决了前人一直不曾注意的问题。 f 数组私有化的问题可以划分两个子问题：其一是识别临时数组，其二是迸行 终值复制。在私有化变换时，一个可私有化数组是否需要终值复制可以由数组的 数据流分析判定。如果一个数组的值在循环之后不再被使用( 不再活跃) ，那就 不需要终值复制，否则就必须对数组在循环出口的值进行复制。当一个处理器执 行某个特定的迭代时，它必须知道本迭代中对哪些数组元素写将是整个循环中对 这些元素的最后一次写。4 本文分析了现有的终值复制方法的不足，同时提出一个改进的终值复制方 法一一相关覆盖方法。咕在数据流的计算中使用了相关性，从而化简了计算，具 有很强的处理能力。在此基础上，我们同时对已有的活跃变量分析算法进行改进， 提出相关性分析和暴露集计算相结合的方法，提高了分析的效率。、上 关键字：程序结构化；膨胀，代码拷贝；数组私有化；终值复制；活跃变量 复旦大学硬士学位论文 堡宣堕塑些塑墼墨璺宣些 苎! 里苎三三! ! 一 a b s t r a c t i nd e s i g n i n gt h eo p t i m i z i n ga n dp a r a l l e l i z i n gc o m p i l e r , i ti so f t e ns i m p l e r a n dm o r ee f f i c i e n tt od e a lw i t hp r o g r a m st h a th a v es t r u c t u r a l i z e dc o n t r o lf l o w t h e r ea r em a n yi m p o r t a n tp r o g r a m st h a ti n c l u d eg o t os t a t e m e n t so ri r r e d u c i b l e l o o p s ，t h u sm a k i n g t h ee n t i r ep r o g r a m ss t r u c t u r e l e s s i nt h i sp a p e rip r e s e n t ad f o ( d e p t hf i r s to r d e r ) a l g o r i t h mt os t r u c t u r a l i z ef o r t r a np r o g r a m sb y e t i m i n a t i n g a l l g o t os t a t e m e n t s a n dt r a n s f o r m i n ga ni r r e d u c i b l e l o o p t o r e d u c i b l eo n e t h ea c t u a la l g o r i t h mp r o c e e d sb ye l i m i n a t i n gaf o r w a r dg o t ow i t hm o d i f i e d c o d ec o p ym e t h o da n dab a c k w a r dg o t ow i t hal o o p t h em e t h o do fm o d i f i e d c o p y c o d e i st oc o m b i n ec o d e - c o p ym e t h o dw i t hi fs t a t e m e n tm e t h o di n p r o g r a ms t r u c t u r a l i z a t i o nt oc o n t r o lp r o g r a mc o d ee x p a n s i o n m o r e o v e r , e v e r y i r r e d u c i b l el o o pw i l lb et r a n s f o r m e dt oc o r r e s p o n d i n gr e d u c i b l eo n ew eh a v e j m p l e m e n t e dt h em e t h o d i nt h ea f t ( a u t o m a t i cf o r t r a nt r a n s f o r m e r ) p a r a u e l i z i n gc o m p i l e ra n dt h ee x p e r i m e n t a l r e s u l t sd e m o n s t r a t et h a tt h e m e t h o di sb o t he f f i c i e n ta n de f f e c t i v e t h ep r o b l e mo fp r i v a t i z a t i o nm a yb ed i v i d e di n t ot w oi s s u e s t h ef i r s ti st h e p r i v a t i z a b i t i t yo fa na r r a yi nal o o p t h es e c o n di st h en e e dt oc o p yo u tt h el a s t d e f i n e dv a l u e s i fs o m ed e f i n i t i o n si nal o o pr e a c ht h ea r r a yu s e so u t s i d et h e l o o p ，t h e nt h el a s tv a l u e sw r i t t e nb yt h ed e f t n i t i o n si nl o o pm u s tb ec o p i e do u t w h e nap r o c e s s o re x e c u t e sap a r t i c u l a ri t e r a t i o n ，i tn e e d st od e t e r m i n ew h i c h a r r a ye l e m e n t ss h o u l db ec o p i e do u t t h ep u r p o s eo ft h el va n a l y s i si st od e t e r m i n ew h e t h e rt h ep r i v a t i z a b l e a r r a yi nal o o pi sl i v eo u t s i d et h el o o p t h i st h e s i sg i v e sam e t h o dw h i c h c o m b i n e sd e p e n d e n c em e t h o da n du p w a r d e x p o s e de l e m e n t sa n a l y s i s i nt h et h e s i sia n a l y z e dt h em e t h o d sw h i c ha r ea l w a y su s e dt od e t e r m i n e l a s td e f i n e di t e r a t i o no fa r r a ye l e m e n t s m o r e o v e ran e wm e t h o di sp r e s e n t e d t or e s o l v et h ec o p yo u ti s s u em o r ee f f i c i e n t l ya n de f f e c t i v e l y i ti sac o m b i n a t i o n o fd e p e n d e n c em e t h o da n dd a t a - f l o wm e t h o d k e y w o r d ：s t r u c t u r a l i z a t i o n ，e x p a n s i o n c o d e c o p y , a r r a yp r i v a t i z a t i o n ，c o p y o u t ，l i v ev a r i a b l e 复旦大学硕士学位论文 堡壁堕塑些塑墼望整宣些 蔓生里兰羔| _ ! l 前言 1 并行编译的相关背景 并行处理计算机是计算机设计的未来。当代面l 临的重大科学技术问题要依赖 于计算技术协助解决，一方面要作大型计算以得到更精确的解，另一方面要作计 算机模拟，以便进一步了解所探讨问题的结构与运动规律。这两个方面都离不开 并行处理技术。 虽然许多人都认识到并行处理技术的重要性，但并行处理技术的发展道路并 不平坦。从7 0 年代到9 0 年代中期，中间几起几落，究其原因，就是并行计算技 术仍然遇到若干困难，使其无法推广应用，其中最主要的一个问题就是并行程序 设计方法尚未达到科学化、实用化、和大众化阶段。 如何使大部分的程序员仍能保持自己的编程习惯，这里自动并行编译为并行 化现有的串行程序及编写新的并行程序提供了重要的支持，因此一直受到重视。 近十几年来，自动并行编译技术的研究进展，包括在相关分析、程序变换、数据 分布和重分布及调度等方面的进展，将自动并行编译进一步推向了实用化。如果 说基于共享内存的自动编译技术已具有一定程度的实用性，基于分布内存的技术 则由于数据分布的困难而离实用化还有一段距离。 九十年代初，1 1 li n o i s 大学的c s r d ( 其前身就是k u c k 教授的研究小组) 再次 开展了实验性研究工作，他们在分析了p e r f e c tb e n c h m a r k 和一些实际应用程序 后指出：数组私有化、归约识别、非线性递归标量识别、符号数据相关性分析和 过程间分析是非常重要的并行化技术。这些新的方法对一些实用程序非常有效， 并且具有相当大的代表性，是新的并行化编译系统设计时必须考虑的问题。 自9 0 年代以来，自动并行编译技术的研究有了很大的进展，产生了一批有 代表性的自动化系统，国外的有s u i f ( s t a n f o r du n i v e r s i t yi n t e r m i d i a t e f o r m a t ) ，p o l a r i s ：国内的有a f t 等。通过对这些系统的开发，人们提出了很多 实用技术，涵盖了数据相关性分析、数组私有化、规约识别、过程间分析等方面 的内容。 研究和实践都表明，在目前设计出基于共享内存的可实用的自动化并行系统 是可能的，但基于分布内存的可实用化系统还需假以时曰。为了设计更加实用和 强大的自动化系统，还需要人们从相关性分析、程序转换、数据分布优化到调度 的各个环节中进行研究，推出更好的新技术。 从总体上看，并行技术在几十中已经取得了很多重要进展，但很多方面还处 于完善和探索阶段，并行处理技术作为计算机科学的一个重要方向，其应用前景 将是非常广阔的，它的发展还需要所有从事并行处理研究人员的共同努力，来促 复旦大学硕士学位论文 程序结构化和数组私有化 第4 页共3 5 页 进并行技术的进一步普及化，实用化。 2 本文的主要内容和结构 本文针对并行编译中的两个主要方面：其一是程序结构化，针对传统f o r t r a n 程序中大量使用非结构化语句给编译系统带来的麻烦，设计了一个层次性的结构 化方法。该方法既最大限度地保留了系统原有的循环结构，又设法将其中非结构 化的部分变换为结构化，同时防止在结构化过程中程序的过度膨胀。另外还将不 可规约程序转变为等价的可规约程序。这个方面的工作主要是将原有的控制流分 析工作在并行化编译系统中加以推广。其二是提出了一个可在数组私有化中使用 的新的终值复制算法，该算法充分利用了终值复制的本质特性，并使用了相关性、 写自覆盖、尾覆盖等概念克服了终值复制时信息不足的困难。另外在涉及到的活 跃变量分析问题上，将相关性分析、暴露集计算和首覆盖等结合起来，提高了解 决的效率。 3 有关的符号约定 符号名称 解释 尸 上 b l 芒 上v 厶 程序段 一段f o r t r a n 程序 循环 f o r t r a n 的d o 循环 循环次数l 中的循环迭代次数 第d 层循环 嵌套循环l 中的由外向内的第d 层循环体 任意循环迭代循环l 在i $ v 王b l 之问的任意一次迭代 循环迭代 循环l 的第i 次迭代 r ，r lw ，w i读，写引用对数组的读，写引用 x ，x 引用引用集对数组的引用( x 是引用变量其取值为r tr ，w ，w ) r pf 睇 读7 写集 程序段p 中对数组的所有读7 写引用 s e t p ( x ) w b s ， n a w l u e ， 引用元素集 x 在p 中引用的所有数组元素的集合( x 不在p 中时为空集) s e 7 p ( z 产品s e t p ( x ) 写回集 循环l 的迭代i 的写回集 无反相关写 程序段p 中关于r 的无反相关写集，见定义6 暴露集 程序段p 中的暴露集 彳d 陟y 反输出相关写循环l 中关于w 的反输出相关写集，e g g 5 集 复旦大学硕士学位论文 程序结构化和数组私有化 第5 页共3 5 页 第一章程序结构化介绍 1 引言 一般程序设计语言为用户提供了大量的特殊语法成分。如早期的f o r t r a n 语 言，由于缺乏足够的结构化描述语句，致使大量已存在的相当有价值的应用程序 普遍采用g o t o 语句。这些非结构化成分的使用在早期的应用中获得相对较小 的代码规模。但在今天看来却是弊大于利，大量g o t o 的使用极大地降低了程 序的可读性及可维护性。尤其对于一个并行编译系统来说，非结构化成分的出现 使得程序结构紊乱，控制相关关系复杂，这些都将严重影响系统的分析和变换功 能。 程序结构化的目的就是要在不改变程序语义的前提下，通过改变程序结构来 消除大量的g o t o 语句，将程序变换成只有循环、分支及顺序三种结构的结构 化程序。 程序结构化有以下的优点。首先，结构化简化了程序中各语句间的控制相关 关系。通过结构化，我们将控制相关信息附在语法树上，从而避免了使用一个新 的复杂i r 一控制相关图。 其次，结构化加速了系统中的数据流分析。基于结构化的数据流分析一般不 需要迭代，因此大大降低了数据流分析的时间。 再次，由于并行转换系统在编译时需要知道的信息越来越多，于是人们开始 注意对源程序进行语义分析，而程序结构化规范简化了程序的结构，使得语义分 析成为可能。 2 相关工作 简而言之，程序结构化的工作就是将反向的g o t o 语句转变为循环，而将前 向g o t o 语句转变为条件判断。这个在理论上已经被完全解决的问题，在实际运 用中却出现了问题，致使一些b e n c h m a r k 程序无法结构化。这个问题在我们以 前研制的自动并行化工具a f t ( a u t o m a t i cf o r t r a nt r a n s f o r m a t i o n ) 中，以及 目前大多数的自动并行化工具中都广泛地存在着。通过对问题的分析，我们发现 原来被认为在理论上完全可行的算法，在实际中却因为空间或时间的限制，变为 不可行。 首先，在将前向g o t o 转变为i f 的过程中，如果完全依靠增加判定( 具体算 法见参考文献【1 】，【2 】) ，会增加临时变量和相关判定的数目，会给语义分析带 来极大的障碍。另一种极端方法是完全依靠公用代码拷贝消除g o t o ( 参考文献 【3 】) ，但在实践中发现有一部分程序会因为程序结构化时的代码过度膨胀而影 复旦大学硕士学位论文 堡壁堕塑垡塑墼丝整查些l 鱼至兰三l ：要一 响整个系统的性能，甚至可能导致系统崩溃。而本文算法在避免了大部分的无谓 的新增条件判定的基础上，同时考虑到程序代码过度膨胀带来的缺点，采用了主 要依靠拷贝但同时又结合了必要的条件判定的方法。在本文的第二章中第三节给 出了不同算法的比较结果。 其次，对于众多的g o t o 语句，应该采用怎样的处理顺序，才能取得较好的处 理效率和结果。以往的论文中通常只是采用随机的处理顺序，而在本文中提到了 按照控制流图的深度优先搜索序( d f o ) 的逆序进行，这样做不仅是合理的，而 且实际证明是高效的。 最后，对于不可规约程序的处理，在以前从未有人注意过，而只是将其和可 规约的情况统一处理。这样一来，当碰到不可规约的程序时，以前的结构化方法 的处理结果极不理想。而本文将不可规约的程序转化为可规约的程序，结构化的 结果是令人满意的。 3 本文程序结构化方法 目前的并行化编译系统，并行化的对象是d o 循环。因此，一般程序结构化 也以d o 循环为基本单位进行。d o 循环可以具有嵌套结构，对于嵌套d o 循环 结构化处理的顺序是自底向上，先处理嵌套最内层的d o 循环，再处理次外层的 循环，依次类推，每当结构化处理一个d o 循环时，包含在这个d o 循环中的其 他d o 循环都已经被结构化了。结构化每个d o 循环需要三个步骤： s t e p l 将跳出d o 循环的g o t o 变换为b r e a k 。 s t e p 2 除去d o 循环中的反向g o t o 使之成为w h i l e d o w h i l e 循环。 2 1 将跳出新形成的w h i l e d ow h i l e 循环的g o t o 变换为b r e a k 。 2 2 消除新形成的w h i l e d o w h i l e 循环中的前向g o t o 使之成为i f 语句。 s t e p 3 消除d o 循环中的前向g o t o 使之成为i f 语句。 具体的方法是：当完成第一步后，即一个d 0 循环中的外跳g o t o 被变换为 b r e a k 后，可以构造这个d 0 循环体内的控制流图，在构造控制流图时，外跳g o t o 被忽略。这种控制流图可以很好地反映一个循环体内g o t o 语句跳转的真实情况， 第二步就是根据控制流图的深度优先序，自底向上的找到d 0 循环体内反向g o t o 构成的循环。每当第二步得到一个g o t o 循环，若流图是不可规约的，则此g o t o 循环可能有不止一个入口，必须先将入口归一化。再消除g o t o 循环体内的外跳 和前向g o t o ，将g o t o 循环凝聚为流图上的一点。再重复第二步，直至再找不到 反向g o t o 构成的循环，最后只要消除d 0 循环内的前向g o t o ，整个流图就变换 完毕了。 顺序执行第一，第二和第三步，当前这个d o 循环就变换完毕了，再处理次 复旦大学硕士学位论文 程序结构化和数组私有化 第7 页共3 5 页 外层的d o 循环，依后序遍历处理整个程序的语法树。具体算法可见参考文献 【3 】。本文的算法对上述算法中的第三步作了改进。 3 1 外跳g o t o 的变换 f o r t r a n 不允许有跳入d o 循环的g o t o ，但允许有跳出循环的g o t o ，另外在 3 2 中将会讲到由g o t o 语句构成的循环，f o r t r a n 程序中也会存在从此种循环中跳 出的g o t o 。 去除外跳r o t o 的方法是引进c 语言中的b r e a k ，由于在a f t 系统中的i r 也 有b r e a k 的表示，这样一来，就保证了在结构化后的程序具有良好而简洁的结构。 先解释下述概念： 普通g o t o 语句：语句本身和跳转的目标都在同一层循环内。 外跳g o t o 语句：跳出当前循环层的g o t o 语句。 初次外跳g o t o 语句：对于跳出多层循环的外跳g o t o 语句，首次用b r e a k 使其 跳出最内层循环，并在该层循环的出口处，生成一个中 间外跳语句。 中间外跳g o t o 语句：对于跳出多层循环的外跳g o t o 语句，已用b r e a k 进行 跳转，但尚未转变为普通g o t o 语句。 在变换外跳g o t o 语句时，需要定义一对新的整型变量。如o u t _ g o t o _ t e m p 和 o u t _ g o t o _ c o u n t ，初值均为0 。对每个初次外跳g o t o 语句，通过o u t _ g o t o _ c o u n t 计数器，分配一个唯一的正整数值作为其i d ，然后计数器加“l ”，以保证同其他 的外跳g o t o 语句相区别。处理每个循环的外跳语句的步骤如下： 1 当为外跳g o t o 时，利用b r e a k 跳到循环的出口。 i f 为初次外跳g o t o ，分配给其一个正整数i d ，同时在该g o t o 之前插入一条赋值语句， 将该外跳g o t o 语句的i d 值赋给o u tg o t o _ t e m p ； e l s e 为中间外跳g o t o 语句，此时该外跳g o t o 已有i d ，且已赋给o u t _ g o l o _ t e m p 。 2 在循环出口处生成i f 条件语句，根据不同o u t _ g o t o _ t e m p 的值，生成新的g o t o 语句， 使已经通过b r e a k 语句跳到循环出r l 的外跳g o t o 语句再跳向各自的跳转目标。 对于生成的新g o t o 语句而言，如果下一步跳转的目标在本层循环体内，外跳g o t o 已经转换为普通g o t o ，对于它的处理将在3 4 节中讨论。否则是中间外跳g o t o 语句，要在外层循环继续按上法对其处理，直到其变为普通g o t o 语句为止。 这种将外跳g o t o 变为b r e a k 的分级跳跃的方法，可以使内层d o 循环的处理 与外层d o 循环的处理彻底分离，同时也将任意改变控制流的g o t o 变换为限制 较强的b r e a k 。 3 2 循环的识别 识别由g o t o 语句实现的循环，首先要构造控制流图。控制流图的构造可参见 复旦大学硕士学位论文 程序结构化和数组私有化 第8 页共3 5 页 编译书中的论述。 由于2 0 t o 构成的循环也可能嵌套，因此循环的识别也需要一定的顺序。在 a f t 系统中，识别循环的顺序是由内到外，因此需要判定循环的嵌套。判定两 个循环是否嵌套，可以使用深度优先序d f o 。控制流图中每个结点的深度优先 序是指一个流图在深度优先搜索时，被栈项弹出的顺序的逆序。据此可将控制流 图的边分为两类： 1 反向边( b a c ke d g e ) ，即若a 一 b 是边，那么d f o ( a ) d f o ( b ) ： 2 前向边( f o r w a r de d g e ) ，即若a 一 b 是边，那么d f o ( a ) b 都是回边( b 支配a ) 时，控制流图 称为可规约的( r e d u c i b l e ) 。可规约流图中，所有的反向边都构成循环。不可规 约流图中，一条不是回边的反向边实际上是构成了一个假循环，该循环不是单入 1 3 而是有多个入口，即循环外有跳入循环的g o t o 。对于这样的g o t a 和d 一 c 构成两个循环，如果d 一 c 是b 一 a 中 的一个嵌套循环，那么只有以下两种情况： 1 a 与c 不同，且a 支配c 。这种情况下d f o ( a ) d f o ( c ) 。 2 a 与c 相同，且d 到b 有一条路。这种情况下d f o ( d ) d f o ( b ) 。 注意如果a 与c 相同，但d ，b 之间无路，此时这两条回边构成同一循环。 我们可以按以下两个原则，给回边排序：回边首先按目标结点的d f o 由大 到小排列，对目标结点相同的则按源结点的d f o 由d , n 大排列。由此我们可以 保证处理反向边的顺序是按循环由内向外顺序进行的。 a f t 系统按由内向外的顺序识别循环时，每当识别出一个循环，a f t 系统 都会先将跳入循环的g o t d ，它构成的循环是由结点d ，结点n 以及有通路到达n 而该通路不经过d 的 堕盛丝盛：旦姿些堕盛盟望里q 盔王璺：王亘塞塑鳖笪兰亚塑基垩塑丝： 我们先介绍几个概念，在不可规约流图中。循环即为流图中的环路，流图的强连通分支， 即去掉环路中的反向边后，该环路不再强连通。这样一来，程序中任何可能反复执行的代码 都会被我们的算法纳入某一循环之中。而此时的晟内层循环，就是有且仅有一条反向边构成 的环路，该反向边按3 2 中介绍的方法得到。 显然按我们的算法，不会遗漏本应在循环体中的结点，但是否会误加入不是从循环正常入i ：1 ( d ) 跳入循环的结点。假设边s 一 t 即为非正常的跳入边，s 不属于循环体，而t 在循环体 中。假设d f o ( s ) d f o ( d ) ，则在深度优先搜索时，当s 进栈时，d 要么已在栈里，要 么尚未进栈。如果是前者，d 到s 有通路，s 应该在循环中，与假设矛盾。如果是后者，那 么s - n 有通路，n - d 又有边，那么d 将在s 后进栈，d f o ( s ) d f o ( a 1 ) ，所以只要我们对当前 流图中构成i f 的结点对( a i ，b i ) 按d f o ( a ) 由大到小的顺序排列，并按此 顺序依次构成i f 语句，那么我们就保证了内层i f 先形成。每当形成一个内层的 i f 语句后，我们将其凝聚为一个结点，然后再处理外层的i f 。 在将子流图( a ，b ) 中的嵌套i f 凝聚为一点后，子流图( a ，b ) 中除a 、 b 外的所有结点都只有一条出边，但还可能有多条入边。不妨设c 为( a ，b ) 中的一个结点，该结点有n 条入边，d 。- - c ，i = l ，n 。如果某些d i 不在( a ， b ) 中，我们将这样的g o t o 称为外跳入c 的g o t o ，反之，称其为内跳入c 的g o t o 。 对于9 1 尉g 入c 内的g o t o ，我们可以将c 到b 的路径( c ，e l ，e k ，b ) ，分 复旦大学硕士学位论文 锄 肌 呷 刮 一一 一一 上一班 “蛐，一一一 程序结构化和数组私有化 第1 1 页共3 5 页 裂为两条( c l ，e 1 1 ，e k ，b ) 和( c 2 ，e 1 2 ，e k 2 ，b ) 。实际上，就是将 c 到b 的路径上的所有结点进行复制。如果d i - - c 中的d i 不在( a ，b ) 中， 那么将d i 一 c 改为d i - - c l ：如果d 。- - c 中的d i 在( a ，b ) 中，那么将d - - c 改为d 。- - c 2 。经过这种结点分裂，a 支配( a ，b ) 中的所有结点，也即 子流图( a ，b ) 只有单入口a 和单出口b 。 经过上述变换后，子流图( a ，b ) 中还有结点其入边不为1 ，这些结点的源 结点都在( a ，b ) 中，对于这样的结点，如果也对每条入边使用结点分裂的方 法，通常会造成程序代码的急剧膨胀：如下例图l 中的( b ) 将会造成结点c 的n 次分裂。此时我们将采用称为条件分层的方法，这种方法不会增加l 临时变量和相 关判断，( 参见图1 中的( c ) ) ，该算法的工作流程如下： f o r 按d f o 顺序，遍历当前循环流图中的每一结点xf i f x ( a ，b ) & & x 有不止一条的( a ，b ) 内的入边 生成新结点a ： 找到从a 到x 的所有n 条路径( a ，e l ，e 2 1 ，e k ，x ) ( o n ) ； 在流图中删去n 条边( a ，e l t ) ，添加n 条边( a l ，e 1 1 ) ： 添加a 到a 1 的新边； 将( a i ，x ) 凝成最内层的i f 语句： ) 经过上述处理的子流图( a ，b ) ，从a 到b 的所有路径都是独立的。 a ( a ) 子流图( a ，b ) a ( b ) 结点分裂后( c ) 条件分层后 图1结点分裂法和条件分层法比较 从上面的叙述中可以看出，在构造i f 语句时，我们虽避免了子流图内的结 点分裂，但对于跳入子流图的入边却不可避免要用到结点分裂，这种方法的优点 在于它可以使转变后的程序结构简洁、清晰，减少不必要的条件判定。但它有时 也会导致流图因某些结点的过度分裂而急剧膨胀。这种膨胀有两个坏处：首先， 复旦大学硕士学位论文 程序结构化和数组私有化第1 2 页共3 5 页 它会耗尽系统空间，使系统由于申请不到足够的空间而崩溃；其次，如果一个 d o 循环的循环体膨胀过大，将会影响该d o 循环的执行，例如循环体内过长的 指令序列将会使c a c h e 由于频繁的调度而产生激烈抖动，从而大大降低c a c h e 的命中率。 在由子流图( a ，b ) 构成i f 的过程中，为防止过度膨胀，需要为其中每个 有从i f 外跳入的边的结点c 估计一个膨胀系数，从而估算出分裂结点c 的代价。 估计膨胀系数的具体方法如下： 1 从子流图的出口b 开始，按d f o 从大到小遍历子流图中的每一个有跳入 边的结点c 。 2 估算结点c 到b 的这条路径的权重。这条路径由一组结点构成，每个结点 实际上是一个基本块，或是由一些基本块构成的超结点( 如新形成的循环和i f 结构) 。通过对这个结点中的所有语句进行估算，可以得出该结点包含多少个操 作，一条路径上所有结点( 不包括b ) 所含操作的总和，为该条路径的权重。 3 确定结点的分裂次数。源点在子流图( a ，b ) 外的所有入边只需一次分裂。 4 结点c 的膨胀系数为权重分裂次数( 1 ) 。 如果一个结点c 的膨胀系数大于一个给定的阈值( 例如，可根据系统中内存 容量和c a c h e 大小来确定一个阂值) ，那么可以用与3 3 节中去掉从循环外跳入 循环的边相似的方法，去掉跳入i f 的边，将子流图( a ，b ) 转换为单入口a 的 i f 语句。这样一来避免了结点分裂，但将会增加临时变量和相关判定，这些判 定会给语义分析带来很大的障碍。 具体的做法是先进行代码拷贝，只在膨胀系数太大时才利用分级跳跃的方法 去掉跳入i f 的g o t o 。所有这样的g o t o 都先跳到i f 的入1 3 ，在l f 的入口将跳到 该i f 中不同的目标语句的g o t o 语句汇集在一起，这时需要有一个整数变量，如 命名为i f _ _ g o t o _ t e m p ，其初值为0 。每当遇到一个未处理的跳入g o t o 时，都要在 该g o t o 之前插入一条赋值语句，对i f _ g o t o _ t e m p 赋不同的值，在i f 的入1 3 处， 再根据i f _ g o t o _ t e m p 的值确定下一步跳转的目标。 复旦大学硕士学位论文 程序结构化和数组私有化第1 3 页共3 5 页 第二章结构化的实现和分析 1 a f t 系统中的程序结构化算法 在算法中三对全局量i n _ g o t o _ t e m p 和i n _ g o t o _ c o u n t ：o u t _ g o t ot e 删。和o u t g o t o _ c o u n t ； i f _ g o t o _ t e m p 和i f _ g o t o _ c o u n t ，分别用来给跳入循环的g o t o 语句，跳出循环的g o t o 语 句以及跳入i f 结构的g o t o 语句赋不同的值，使得在入口处或出口处能根据不同的值跳转到 不同的目标。它们的初值均为1 。 a f t 系统中完整的程序结构化算法的工作流程如下： f o r 每一个过程pf 对语法树进行后序遍历，按遍历顺序由内而外处理每个d o 循环 f o r 每一个d o 循环d o 将d o 循环中的所有外跳g o t o 语句变换为b r e a k 语句( 利用o u t g o t o t e m p ) ： 构造流图； 计算流图中各结点的支配结点( d o m i n a t o r ) ： f o r 按结点的d f o 的值由大到小遍历流图，对每一个结点df i f ( 有反向边指向结点d ) f 构造g o t o 语句构成的循环 c r e a t e g o t o l o o p ： ) 木去掉d 0 循环中的所有前向g o t o 语句 c r e a t e i f 。i n 。l o o p ； 将d o 循环凝成一个结点； ) 子函数c r e a t e g o t o lo o p $ 去掉反向g o t o 语句衫 查找由g o t o 语句构成的循环的循环体( 分可规约和不可规约两种情况) ； i f ( 该循环为不可规约) f o r 每个从循环外跳入该循环体的g o t o 语句 在该g o t o 前插入按i n _ g o t o _ c o u n t 值对i n _ g o t o t e m p 赋值的语句 先跳到循环入口，再跳转到目标： i n _ g o t o _ c o u n t + + ； ) 复旦大学硕士学位论文 堡壁壁塑些塑墼塑整查些 兰! ! 生苎j ! ! ! 一 ) 将跳出该循环的所有g o t o 语句分别转变为b r e a k 语句( 利用o u t g o t o t e m p ) ； c r e a r e - i f i n l o o p ； $ 处理该循环中的所有前向g o t o * 将g o t o 形成的循环凝成流图上一个结点： 返回主程序： ) 子函数c r e a t e i f - i n - g o t o 去掉一个指定的d o 循环中的所有前向的g o t oi 吾u - j , f o r 按结点的d f o 的值由大到小遍历循环体，寻找有多条出边的结点a 查找并确定由g o t o 语句构成的i f 语句的子流图( a b z f o r 按结点的d f o 的值由大到小遍历子流图( a ，b ) 中有多条入边的结点c i f ( 有从子流图( a ，b ) 外跳入c 的边) 计算结点c 的膨胀系数； i f ( 膨胀系数阈值) 对c 到b 的路径进行复制； e l s e 将外跳入边转变为先跳到a ，再转到c ( 利用i f _ g o t ot e m p ) ； ) f o r 按结点的d f o 的值由小到大遍历子流图( a ，b ) 中有多条入边的结点c 用条件分层方法处理子流图( a ，b ) 中跳入c 的边。构造内层i f 语句( a 。，c ) 十具体算法可参考3 4 * 将子流图( a i ，c ) 凝成一个i f 结点； 将子流图( 。b ) 凝成一个i f 结点： ) 返回； 2 优化措施 在上一章的3 2 节中，识别出由g o t o 构成的循环后，需要对新循环进行分 类( w h i l e d ow h i l e ) 。对于循环头即为其唯一出口的循环是普通的w h i l e 循环： 而普通的d ow h i l e 循环则是循环尾为其唯一出口的循环。但由g o t o 构成的循环 可能有多个出口，由于我们的a f t 系统支持b r e a k 语句，我们将会统一将其转换 为循环内有b r e a k 出口的w h i l e 循环。此时又分两种情况：若循环的头是这些出 口中的一个，构成的新循环是有终止条件的；反之，循环的头没有外跳边，新循 复旦大学硕士学位论文 程序结构化和数组私有化 第1 5 页共3 5 页 环的终止条件将恒为真。对于第二种情况，特别的是当循环只有一个中间出口的 情况。这时如果我们也将其简单的处理为条件恒真的有一个b r e a k 的w h i l e 循环， 似乎不大合适。这时更为合理的方法是在原出口处添加一条g o t o 语句，先转移 到循环尾，再将循环转换为不含b r e a k 语句的单出口普通d ow h i l e 循环。 更为难办的种情况是当循环头和循环尾同时是出口，我们方法是将其转换 为d o w h i l e 循环。去掉循环头的出口，添加g o t o 语句转移到循环尾，且d ow h i l e 的终止条件为头尾出口的条件的或。 如果我们希望结构化后的程序具有更良好而简洁的结构，我们将会发现在构 造i f 结构时，必须更仔细的处理各i f 分支的条件。例如在下面的例子中，我们 会发现对于有b r e a k 语句的i f 结构( 处理外跳g o t o 经常会遇到) 的两种处理， 使最后的结果不尽相同。 i f ( c o n d = = lc o n d = = 2 ) f i f ( c o n d = = 1 ) s 1 ： e l s e s 2 ： ) e l s eb r e a k ： if ( c o n d = = 1 ) s 1 ： e l s e i f ( c o n d = = 2 ) s 2 e l s eb r e a k ： 显然第二种转换更为合理，且使程序简洁，特别如果条件复杂，对其求并将会十 分麻烦。 当然上面的例子只是特殊的情况，我们希望在构造每一个i f 结构时，都能 将条件较为复杂的一个分支作为i f 的e l s e 分支。当然何为复杂，个人会有不同 的理解，在a f t 系统中，将以或连接的予条件的数目为复杂程度的度量。如果一 分支的条件是许多不同子条件的或，将意味着如其作为外层i f ，其内所包含的 嵌套i f 的层次将较深。 3 前人的研究 a m m a r g u e l l a t 和m c g i l lu n i v e r s i t y 在程序结构化方面做了颇多的研究， a m m a r g u e l l a t 在1 9 9 2 年发表的论文中提出了一套去除程序中g o t o 语句的方法， 她称之为控制流结构化方法( c o n t r o l f l o wn o r m a l i z a t i o n ) 。但由于其针对的 是一种不同于一般的高级程序语言的l i s p l i k e 语言，而且其将程序结构化等价 于对一串等式的变换，所以全文十分晦涩难懂。 简单说来她的方法是通过将语法结构映射成代数结构来实现的，它将程序映 射成一个包含一系列等式的系统。等式中的未知量代表了和程序中标号相关的 e o n t i n u a t i o n s 。c o n t i n u a t i o n 是这样一个函数，当它被调用时，能得到从这条 指令开始执行的该程序的结果。程序中的每条l a b e l 语句都与个c o n t i n u a t i o n 复旦大学硕士学位论文 程序结构化和数组私有化 第1 6 页共3 5 页 相对应。程序结构化的过程就是对这些等式进行一系列的转化：p r e c a l c u l a t i o n ， i fd i s t r i b u t i o n ，f a c t o r i z a t i o n ，d e r e c u r s i v a t i o n ，以及s u b s t i t u t i o n 和 e l i m i n a t i o n 。其优点在于：首先，经过其结构化后，程序中原有的g o t o 构成的 控制流循环都变成了单入口、单出口的w h i l e 循环。其次，其基于程序的拓扑排 序对程序进行结构化，在这种顺序下，可以减少公用代码的复制。但其同时存在 以下几个问题： 第一，由于其一个c o n t i n u a t i o n 与一个语句l a b e l 对应，但实际上，可能 一段连续的语句串前虽没有l a b e l ，但却需要一个c o n t i n u a t i o n 代表它。比如 有g o t o 的i f 语句的两个分支。另一方面，有些语句l a b e l 却毫无必要为其产生 一个相应的c o n t i n u a t i o n