short inta[1000]，b[1000]，c[1000];

　　for(i=2;i<1000;i++)

　　a[i]=b[i]+c[i];

　　通过循环正规化技术处理后，该循环可以变形为：

　　short inta[1000]，b[1000]，c[1000];

　　for(i=1;i<999;i++)

　　a[i+1]=b[i+1]+c[i+1];

　　本文使用“格”作为数据流分析中对内部数据结构的形式化表示方法。传统的数据流分析[6]可以看作是沿着变量位宽的传播进行操作，或者为每个变量维持1个位向量。前者无法得到算术操作的精确的结果，因为对1个8位数的位传播往往导致1个9位的结果，尽管8位数就足够了，或者1个变量中只有最重要的几个位能够进行位消去。而后者不支持精确的算术分析，因为它往往会保守的假设每个加法结果都产生进位。所以，在进行数据流分析的时候，我们使用“格”结构来形式化表达内部数据结构。1个数据范围可以看作是从某个下界到某个上界变化的整数的子范围的简单连接，因此，用数据范围就能够清楚的表达某个变量的下界和上界。因为我们只需要用1个简单的范围就可以表示变量的所有可能的值，因此，尽管该表示方法不允许消去低位的位，却可以对算术表达式实现精确的计算。

　　我们选择格来表示数据范围传播基于以下3个方面的因素：首先，这种表示方法能够将位宽分析应用到更普遍的值范围传播问题，这对于解决值预测、分支预测、常数传播、过程复制和程序验证都非常有效。第2，该表示方法保证了精确性，这对于大多数算术应用非常重要;第3也是最重要的，在我们的编译算法中，用生存期(life range)作为处理子字的标准，在该结构中，我们将每个子字的生存期映射到值的范围，从而获得每个生存期的精确结果，所以，这种“格”的结构也可视为对生存期传播的表示。

　　在格的表示中，值的生存期被分配到某个变量，格自下向上提升，如图2所示值的定义和计算如下：

　　(1)⊥DR⊥：未初始化时的子字生存期的值

　　(2)TDR⊥：不能静态决定的值，即子字集合的生存期的上界

　　(3)∪：生存期的并集〈al，ah〉∩〈bl，bh〉=〈min(al，bl)，max(ah，bh)〉

　　(4)∩：生存期的交集〈al，ah〉∩〈bl，bh〉=〈max(al，bl)，max(ah，bh)〉

　　以如下所示的代码段为例，这是取自MPEG—4算法中的1段简化的循环代码，

　　for(i=0;i

　　C[i]=A[i]—B[i] /*1S*/

　　D[i+1]=D[i]+C[i] /*2S*/

　　}

　　我们通过分析，得到代码段中的真相关和输出相关，图3分别表示循环的数据相关以及循环分配后得到的强连通部件。相关图的强连通部件

　　表示带有向边的节点的最大集合，带有多个节点的强连通部件表示相关循环中语句的

　　最大集合。语句S1不带自圈，所以它自己组成了1个单1的强连通部件，S1能够按照子字并行方式处理。语句S2在循环中是自相关的，我们用循环展开来消除这种相关，如下代码所示。

　　for(i=0;i

　　C[i]=A[i]—B[i];

　　C[i+1]=A[i+1]—B[i+1]}

　　首先根据操作数的类型进行适当的展开，如寄存器为32位，那么对于C语言中定义的short类型的int操作数，就要将循环展开2次，然后进行非循环指令调度，组合相同循环指令的所有实例，这样，S2也可以按照子字并行方式执行了。

5 结论与展望

　　本文根据多媒体应用程序的特点，对其关键核心———内层循环进行分析研究，在现有向量编译的基础上，提出了挖掘内层循环的按位数据流分析算法，方法简单，容易执行，很好的挖掘了图像处理程序内在固有的子字并行。我们将在此工作基础上，进1步融合多媒体编译优化技术，在更复杂的循环结构上进行分析研究。

参考文献：

　　[1] R B Lee。Subword parallelism with max—2[J]。IEEE Micro，1996，16(4)：51—59。

　　[2] A Krall，S Lelait。Compilation techniques for multimedia pro—cessors [J]。 International Journal of Parallel Programming，2000，28(4)：347—361。2577第 12A 期吴 丹：1种确定多媒体应用程序内层循环的子字并行编译方法

　　[3]Intel Corporation。IA—32Intel Architecture Software Devel—oper’s Manual[Z]。Volume2A：Instruction Set Reference，A—M。2004。

　　[4] Intel Corporation。IA—32Intel Architecture Software Devel—oper’s Manual[Z]。Volume2B：Instruction Set Reference，N—Z。2004。