局部约束与全局约束对WCET分析的影响浅析

孟凡奇

摘 要：循环语句的执行次数对程序的执行时间是有影响的，通常循环次数越多，程序执行时间越长。因此，在最差情况执行时间分析中通常需要指明程序循环语句的执行次数上限。本文简要分析使用局部约束与全局约束标注循环上限对最差情况执行时间分析结果的影响。

关键词：最差情况执行时间；循环上界；局部约束；全局约束

众所周知，循环次数对执行时间是有影响的，通常循环次数越多，程序执行时间越长。因此，静态最差情况执行时间（Worst-case Execution Time，WCET）分析通常都需要知道（自动分析或人工标注）循环上界，以便使WCET估计值更精确[1]。本文将探寻使用“局部”或“全局”约束法标注循环上界会对程序的WCET分析有何影响，据此，我们可以决定何种情况下使用何种方法。

1 局部约束与全局约束

“局部”循环边界是指循环语句执行1次，其循环体可能的执行次数范围。“全局”循环边界是指从程序开始运行到结束，循环语句的循环体可能的全部执行次数范围。

以下面的代码为例，第1行for语句的“局部”和“全局”循环边界都是[0，5]。第2行for语句的局部循环边界是[0，5]，全局循环边界是[0，25]。

需要说明的是，由于WCET计算的是最差情况，因此，通常仅需要提供循环上界。我们可以使用“局部”约束法或“全局”约束法为计算WCET的整数线性规划提供所需的循环上界的表达式。局部约束法使用局部循环上界，分析工具会将局部循环上界转换成内外层语句执行次数的整数倍数关系。以上面的代码为例，如果第2个for循环的循环边界使用局部约束法进行标注，则会生成表达式“line2-5line1=0”，即第1行每执行1次，第2行执行5次。而全局约束使用全局循环边界，若第2个for使用全局约束，则会生成表达式“line2=25”。

多数情况下，由于局部循环边界易于获取，所以局部约束法是较为常见的标注方式。然而，情况并非如此简单。对于上下文敏感的循环，尤其是非正交多重嵌套循环，获取内循环的局部循环边界也并不容易。

2 全局约束与非正交循环

若嵌套循环中内层循环的执行次数完全或部分地依赖于外层循环能够直接修改的变量，则称此嵌套循环为“非正交”嵌套循环。

以下面的程序片段为例，第10行的while语句的局部循环执行次数既与外层循环的控制变量i有关，同时还与全局变量数组a有关。出于对安全的考虑，此类非正交多重嵌套循环在标注内循环的循环边界时，往往采用局部循环上界，即所有可能情况下的局部最大循环次数。例如，第10行while语句的局部循环上界是“9”。这样一来，内层while的全局执行次数会被记为小于等于9×9=81次。而其实际的最大全局执行次数为9+8+7+6+5+4+3+2+1=45次。于是，WCET估计值被严重高估了。

要获得更精确的WCET估计值，可以使用全局约束法标注非正交多重嵌套循环的循环边界。从表1中可以看出，使用全局约束可以获得比使用局部约束更精确的WCET估计值。程序fac.c来自于M?lardalen大学的WCET基准程序集。

可以采用“插桩→运行”的动态方法获取循环的全局执行次数。首先，生成待处理程序的抽象语法树；然后，在抽象语法树中寻找循环语句节点；接着，在每一个循环语句节点的第一个子节点之前插装探针，用于输出该循环语句在原源程序中的行号；然后，将插桩后的抽象语法树还原为源程序；最后，这个已经插桩了的源程序获得各循环语句的执行次数。此方法的優点是易于实现、效率较高。但缺点是必须提供最差输入，否则获得的循环执行次数未必是最差情况下的全局循环上界。

3 结束语

局部约束适用于循环上界识别较为容易的正交循环。全局约束适用于非正交循环的内循环语句，可以获得相较于局部约束更为精确的WCET估计值。因此，当程序中的嵌套循环是正交的，建议使用局部约束标注循环上界，否则建议使用全局约束。

[参考文献]

[1]吕鸣松，关楠，王义.面向WCET估计的Cache分析研究综述[J].软件学报，2014，25（2）：179-199.

[2]Li X，Liang Y，Mitra T，et al.Chronos：A timing analyzer for embedded software[J].Science of Computer Programming，2007， 69（1）：56-67.

[3]吕鸣松.实时系统最坏情况执行时间分析技术的研究[D].东北大学， 2010.