一种精确分析任务WCET的自动化方法

摘要

一种精确分析任务WCET的自动化方法，包括以下步骤：一、产生程序的无循环控制流图NLCFG；二、利用NLCFG确定依赖输入变量及其对应节点；三、确定依赖循环变量、依赖非输入分支变量及它们所对应的非依赖输入节点；四、删除非依赖输入节点产生ICFG；五、产生ICFG的所有路径；六、针对每条路径产生其输入条件以及该路径对应的WCET。利用每条路径的条件和其对应的WCET能够精确估算任务的WCET。

权利要求

1.一种精确分析任务WCET的自动化方法,其特征在于：包括以下步骤，

步骤一、产生程序的无循环控制流图NLCFG，无循环控制流图是一种特殊的控制流图，其与CFG的区别在于其循环语句产生的CFG节点只包括循环体节点而不包括分支谓词节点及相应的回边，建立起NLCFG节点与源程序语句的对应关系，同时循环体节点也得到标识；

步骤二、利用步骤一中的NLCFG，从入口节点开始，依照深度优先策略，确定每一个变量是否是依赖输入变量及其对应的依赖输入节点；

步骤三、确定步骤二中依赖输入变量中的依赖循环变量、依赖非输入分支变量，确定依赖循环变量、依赖非输入分支变量对应的非依赖输入节点；

步骤四、从步骤二中删除非依赖输入节点，产生输入变量相关的ICFG，其中，最终形成的NLCFG为输入变量相关的，标记为ICFG；

步骤五、依照深度优先策略产生ICFG的所有路径；

步骤六、针对步骤五的每条路径产生其输入条件；

步骤七、产生步骤六中每条路径对应的WCET，利用每条路径的WCET，即可精确计算整个程序的WCET；

其上所述的深度优先策略是指，在处理一个节点后，把该节点的所有后续节点进行依次排队处理；排队之后，对队列中的第一个节点仍然按照同样方法处理，这样只有在第一个节点及其后续节点处理完毕或者无法处理之后，才开始处理第二个节点，当一个节点有一个前任节点的执行后状态是不确定的，也就是说是没有定义的时，该节点是无法处理的，对无法处理的节点，将此节点重新排在队列末尾。

2.如权利要求1所述的一种精确分析任务WCET的自动化方法，其特征在于：所述的依赖输入变量的确定方法为，为每个节点设置节点执行前与执行后两个状态，节点的状态定义了在节点执行前与执行后每个变量是否是依赖输入变量，节点后的状态是由该节点执行后对节点前状态改变后的状态，节点前状态由所有流向该节点的节点后状态确定，在确定节点前状态时，对于所有流向该节点的节点，如果在这些节点的节点后状态中，一个变量是依赖输入变量，则该变量的状态是依赖输入变量的。

3.如权利要求2所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的依赖输入变量为，由输入变量定义的变量是依赖输入变量，由输入变量和依赖输入变量定义的变量也是依赖输入变量。

4.如权利要求1所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的依赖循环变量和依赖非输入分支变量统称为非依赖输入变量，非依赖输入变量对应的节点为非依赖输入节点。

5.如权利要求1所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的步骤四中删除非依赖输入节点的方法为，删除的方法仍然按照节点的基本结构进行删除，如果一个分支节点或者汇合节点不包括任何节点，使用空节点表示。

6.如权利要求5所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的空节点就是不执行任何操作的节点，空节点对应的语句为空语句。

7.如权利要求1所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的针对ICFG的每一条路径，在这个路径上只有两类节点，一类是对应于赋值语句的节点，另一类是对应于条件语句的分支节点，对于分支节点，如果其分支谓词表达式是输入变量的线性表示，则可以构造出该分支谓词针对输入变量的线性表达式。

8.如权利要求7所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的ICFG路径，该路径上每个分支节点分支取向已经确定，根据路径上的所有分支节点构造输入变量的约束，如果定义目标函数为所有输入变量累加的最小化，则构成典型的线性规划求解问题。

9.如权利要求8所述的一种精确分析任务WCET的自动化方法,其特征在于：所述的线性规划求解利用线性规划解析器，即可确定该ICFG路径的输入条件，此条件即为ICFG路径对应的输入条件，如果线性规划解析器求得该目标函数无解，则说明该路径为不可行路径，则应排除该路径。

说明书

一种精确分析任务WCET的自动化方法

技术领域

[0001] 本发明涉及一种精确估算实时系统任务最差情况执行时间（WCET ：Worst-Case Execution Time）的自动化方法，属于实时嵌入式系统领域。

背景技术

[0002] 与通用计算机系统不同，实时系统的结果只有在规定的时间范围内完成时才是有效的，如果没有在规定的时间范围内完成时，轻则降低系统的性能，重则引起灾难性的后果，比如飞机投弹、核泄漏。因此，对于实时系统，事先获取系统中每个任务的WCET和最好情况的执行时间（BCET ：Best-Case Execution Time）有着特别重要的意义。鉴于BECT分析与WCET分析技术相同，人们只涉及WCET分析。事实上，WCET分析是实时系统任务调度及可调度性检测的前提，也是系统性能瓶颈分析的基础。

[0003] WCET分析通常包括三个组成部分：①程序流事实分析；②执行时间模型的建立；③基于前两项信息的WCET计算。流事实信息就是程序的执行流信息，比如循环的最大迭代次数、不可行路径(infeasible path)等，其中不可行路径是指对任意输入数据都不可能执行的程序路径。

[0004] 要获取程序的WCET，还需要对程序的目标代码进行分析以获得实际的时间，即建立执行时间模型。举例来说，对于不带cache、没有流水线的传统CISC指令，其指令的执行时间是固定的，其执行时间模型就是：一个代码段的执行时间就是其所对应的每条指令执行时间的累加。

[0005] 计算是在给定程序流事实和执行时间模型的情况下，为程序计算WCET估值。比如对于常见的基于树的（tree-based）计算方法，使用为每种类型的复合程序语句定义的规则确定语句的WCET，然后通过自底向上遍历程序的语法分析树产生整个程序的WCET估值。具体来说，对于复合语句S1;S2，WCET(S1;S2) = WCET (S1) + WCET (S2)；对于条件语句if (E) then S1 else S2，WCET (if (E) then S1 else S2) = WCET(E)+max(WCET (S1), WCET (S2)) ；对于循环语句while (E) do S，WCET(while (E) do S) = (n+1)* WCET(E)+n* WCET (S)，这里n为循环迭代次数。

[0006] 有很多实时程序，其执行轨迹由程序的输入变量值或者范围确定的，在该条件下程序按照此轨迹执行。举例来说，如图6所示的C程序：

[0007] 假定exponent的范围为[-10,10]，则依据基于树的方法和相应的指令代码，其WCET为：

[0008] Wpow=111+max(301,283)+270+117+10*(117+317)+111+max(560,0)+244=6054[0009] 其中，假定第3 6行程序对应的if语句的条件部分代码指令执行时间为111，两个~分支的执行时间分别为301和283，第7行程序对应的赋值语句的代码指令执行时间为270，第8 9行程序对应的for语句的条件部分代码指令执行时间为117，第9行程序对应的赋值语~
句的代码指令执行时间为317，第10 11行程序对应的if语句的条件部分代码指令执行时间~
为111，第11行程序对应的赋值语句的代码指令执行时间为560，第12行程序对应的赋值语句的代码指令执行时间为244。

[0010] 假定有如图7所示代码：

[0011] 则其中Pow部分的WCET为：10*6054=60540。

发明内容

[0012] 本发明提出了一种精确分析任务WCET的自动化方法，利用该方法能够精确估算任务的WCET。

[0013] 为实现上述技术目的，所采用的技术方案是：一种精确分析任务WCET的自动化方法,包括以下步骤，

[0014] 步骤一、产生程序的无循环控制流图NLCFG，建立起NLCFG节点与源程序语句的对应关系，同时循环体节点也得到标识；

[0015] 步骤二、利用步骤一中的NLCFG，从入口节点开始，依照深度优先策略，确定每一个变量是否是依赖输入变量及其对应的依赖输入节点；

[0016] 步骤三、确定步骤二中依赖输入变量中的依赖循环变量、依赖非输入分支变量，确定依赖循环变量、依赖非输入分支变量对应的非依赖输入节点；

[0017] 步骤四、从步骤二中删除非依赖输入节点，产生输入变量相关的ICFG；

[0018] 步骤五、依照深度优先策略产生ICFG的所有路径；

[0019] 步骤六、针对步骤五的每条路径产生其输入条件；

[0020] 步骤七、产生步骤六中每条路径对应的WCET。利用每条路径的WCET，即可精确计算整个程序的WCET。

[0021] 本发明所述的深度优先策略是指，在处理一个节点后，把该节点的所有后续节点进行依次排队处理；排队之后，对队列中的第一个节点仍然按照同样方法处理，这样只有在第一个节点及其后续节点处理完毕或者无法处理之后，才开始处理第二个节点。当一个节点有一个前任节点的执行后状态是不确定的，也就是说是没有定义的时，该节点是无法处理的。对无法处理的节点，将此节点重新排在队列末尾。

[0022] 本发明所述的依赖输入变量的确定方法为，为每个节点设置节点执行前与执行后两个状态，节点的状态定义了在该位置每个变量是否是依赖输入变量，节点后的状态是由该节点执行后对节点前状态改变后的状态，节点前状态由所有流向该节点的节点后状态确定，在确定节点前状态时，对于所有流向该节点的节点，如果在这些节点的节点后状态中，一个变量是依赖输入变量，则该变量的状态是依赖输入变量的。

[0023] 本发明所述的依赖输入变量为，由输入变量定义的变量是依赖输入变量，由输入变量和依赖输入变量定义的变量也是依赖输入变量。

[0024] 本发明所述的依赖循环变量和依赖非输入分支变量统称为非依赖输入变量，非依赖输入变量对应的节点为非依赖输入节点。

[0025] 本发明所述的步骤四中删除非依赖输入节点的方法为，删除的方法仍然按照节点的基本结构进行删除，如果一个分支节点或者汇合节点不包括任何节点，可以使用空节点表示。

[0026] 本发明所述的空节点就是不执行任何操作的节点，空节点对应的语句为空语句。

[0027] 本发明所述的针对ICFG的每一条路径，在这个路径上只有两类节点，一类是对应于赋值语句的节点，另一类是对应于条件语句的分支节点。对于分支节点，如果其分支谓词表达式是输入变量的线性表示，则可以构造出该分支谓词针对输入变量的线性表达式。

[0028] 本发明所述的ICFG路径，该路径上每个分支节点分支取向已经确定，根据路径上的所有分支节点构造输入变量的约束，如果定义目标函数为所有输入变量累加的最小化，则构成典型的线性规划求解问题。

[0029] 本发明所述的线性规划求解利用线性规划解析器，即可确定该ICFG路径的输入条件，此条件即为该情况的输入条件，如果线性规划解析器求得该目标函数无解，则说明该路径为不可行路径，则应排除该路径。

[0030] 本发明有益效果是：该方法能够明显提高具有不同情况执行路径程序的WCET估算精度。

附图说明

[0031] 图1 是本发明的执行步骤流程图；

[0032] 图2 是本发明的程序基本语句与程序控制流程图基本结构的对应关系图；

[0033] 图3 是本发明的确定依赖输入的核心算法流程图；

[0034] 图4 是本发明的图6程序的NLCFG；

[0035] 图5 是本发明的实例程序GetMode及其NLCFG；

[0036] 图6为本发明的例程Pow程序；

[0037] 图7为本发明的例程Pow调用程序。

具体实施方式

[0038] 下面结合附图对本发明进行进一步的详细说明。通过足够详细的描述这些实施示例，使得本领域技术人员能够实践本发明。

[0039] 一种自动产生任务的分情况WCET表达式的方法，利用该表达式能够精确估算任务的WCET。

[0040] 如图1所示，本发明提出的自动化精确产生程序WCET的方法包括6个步骤，具体步骤如下：

[0041] 步骤1：产生程序的无循环控制流图NLCFG

[0042] 程序控制流图（CFG，Control Flow Graph），是对程序的图形化表示，它既表示了程序的控制结构信息，也表示了程序语句执行的流向。一个结构化程序由三种基本语句构成：复合语句、条件语句和循环语句。控制流程图由节点和有向边组成。与基本语句相对应，一个程序的控制流程图也由三种基本结构组成：顺序、分支、循环。控制流图节点分为赋值节点、分支点和汇聚点，赋值节点对应程序的赋值语句，分支节点对应条件语句或循环语句中的条件判断，此条件也称为分支谓词。控制流图的边表示程序的执行流向，分支节点的边称作分支，对应于程序中一段要顺序执行的语句序列。

[0043] 无循环控制流图（NLCFG，No Loop Control Flow Graph）是一种特殊的控制流图，其与CFG的区别在于其循环语句产生的CFG节点只包括循环体节点而不包括分支谓词节点及相应的回边。只所以产生NLCFG是因为本发明还没有为经过循环迭代的依赖输入情况提供解决方案，而循环的回边使后续的分析变得复杂。

[0044] 通过分析源程序，按照程序的三种基本语句进行分析，能够产生程序的NLCFG。程序NLCFG的节点可以使用数字进行标识，边可以用二元组(m,n)表示，其表示从节点m到节点n的有向边。

[0045] 建立NLCFG之后，也建立起NLCFG节点与源程序语句的对应关系，同时循环体节点也得到标识。

[0046] 步骤2：利用NLCFG确定依赖输入变量及其对应节点

[0047] 针对NLCFG，从入口节点开始，依照深度优先策略，确定每一个变量是否是依赖输入变量。由输入变量定义的变量是依赖输入变量，由输入变量和依赖输入变量定义的变量也是依赖输入变量。

[0048] 为了确定依赖输入变量及其对应的NLCFG节点，为每个节点设置节点执行前与执行后两个状态。节点的状态定义了在该位置每个变量是否是依赖输入变量。节点后的状态是由该节点执行后对节点前状态改变后的状态，而节点前状态则由所有流向该节点的节点后状态确定。在确定节点前状态时，对于所有流向该节点的节点，如果在这些节点的节点后状态中，一个变量是依赖输入变量，那么可以确定，该变量的状态是依赖输入变量。

[0049] 所谓深度优先策略是指，在处理一个节点后，把该节点的所有后续节点的排队依次处理。排队之后，对队列中的第一个节点仍然按照同样方法处理，这样只有在第一个节点及其后续节点处理完毕或者无法处理之后，才开始处理第二个节点。一个节点是无法处理的，如果该节点有一个前任节点的执行后状态是不确定的，也就是说是没有定义的。对于无法处理的节点，将该节点重新排在队列末尾。

[0050] 一个节点m的前任节点是指该节点有一条边指向节点m。同理，一个节点m的后续节点是指节点m有一条边指向该节点。

[0051] 对于结构化程序，由于NLCFG没有循环结构，所以NLCFG有向图是单向的。因此， NLCFG中的节点是有序的。也因此，本发明所述的处理策略能够保证快速确定每个节点的状态。

[0052] 所有引用依赖输入变量的节点为依赖输入节点。

[0053] 步骤3：确定依赖循环变量、依赖非输入分支变量及其节点

[0054] 在循环体中定义的变量为依赖循环变量，一个变量如果在定义中引用了依赖循环变量，则该变量同样为依赖循环变量。同样，在非依赖输入分支谓词的分支中定义的变量为依赖非输入分支变量，一个变量如果在定义中引用了依赖非输入分支变量，则该变量同样为依赖非输入分支变量。这两类变量统称为非依赖输入变量NOINPUT。

[0055] 针对一个循环体节点或者非依赖输入分支节点，通过确定一个变量在节点后状态为NOINPUT，从该节点开始，通过向后传递，可以确定所有的NOINPUT。

[0056] 步骤4：删除非依赖输入节点产生ICFG

[0057] 针对NLCFG，删除图中非依赖输入节点。删除的方法仍然按照节点的基本结构进行删除，所不同的是，如果一个分支节点或者汇合节点不包括任何节点，可以使用空节点表示。所谓空节点就是不执行任何操作的节点。空节点对应的语句为空语句。

[0058] 最终形成的NLCFG为输入变量相关的，标记为ICFG。

[0059] 步骤5：产生ICFG的所有路径

[0060] 对于ICFG，可产生其所有路径。由于ICFG是单向图，可按照深度优先策略产生所有路径。

[0061] 步骤6：针对每条路径产生其输入条件

[0062] 针对ICFG的每一条路径，在这个路径上只有两类节点，一类是对应于赋值语句的节点，另一类是对应于条件语句的分支节点。对于分支节点，如果其分支谓词表达式是输入变量的线性表示，则可以构造出该分支谓词针对输入变量的线性表达式。假定输入表示为X=，m是输入变量的个数，假定一个分支节点的谓词可以表示为X的线性函数F(X)= d1 x1+...+ dm xm+ c，由于任意给定一个输入，沿着该路径能够计算该谓词的值，因此能够计算出谓词线性表达式的各参数dj：

[0063]  ，j=1,2,…,m

[0064] 其中I0=(i1,.., ij,.., im)为任一输入，∆ij为任一不为0的增量。I0最常见的值为(0,0,…,0)。

[0065] 对于ICFG路径来说，该路径上每个分支节点分支取向已经确定，因而，可以根据路径上的所有分支节点构造输入变量的约束。如果定义目标函数为所有输入变量累加的最小化，则构成典型的线性规划求解问题。

[0066] 利用线性规划解析器，即可确定该ICFG路径的输入条件，此条件即为该情况的输入条件，如果线性规划解析器求得该目标函数无解，则说明该路径为不可行路径，则应排除该路径。

[0067] 步骤7：产生该路径对应的WCET

[0068] 对于上述路径的WCET，其对应程序的WCET计算则应当只计算属于该路径的WCET。具体而言，对于基于树的计算方法，差异体现在条件语句。如果一个条件语句的分支谓词节点属于该路径，假定该条件语句为if (E) then S1 else S2，如果在S1该路径上，则WCET (if (E) then S1 else S2) = WCET(E)+ WCET (S1)，如果在S2该路径上，则WCET (if (E) then S1 else S2) = WCET(E)+ WCET (S2)。

[0069] 实施例1

[0070] 下面结合附图对本发明进行进一步的详细说明。通过足够详细的描述这些实施示例，使得本领域技术人员能够实践本发明。

[0071] 本发明提出了一种精确产生程序WCET的自动化方法，该方法利用程序控制流图（CFG，Control Flow Graph）类似的图自动产生任务WCET情况表达式，从而达到精确估算任务WCET的目的。

[0072] 本发明提出的自动化精确产生程序WCET的方法包括6个步骤，具体步骤如下：

[0073] 步骤1：产生程序的无循环控制流图NLCFG

[0074] 与产生程序的CFG类似，同样通过对程序的三种基本语句构成：复合语句、条件语句和循环语句，生成相应的三种基本结构组成：顺序、分支和循环体，生成的对应关系如附图2所示。对于条件语句，附图2中只表示了if then else条件语句，对于if then语句和case语句可以类似处理。对循环语句也同样如此。

[0075] 通过对源程序进行分析，按照程序基本语句与NLCFG基本结构的对应关系，利用递归，能够产生程序的NLCFG。程序NLCFG的节点可以使用从小到大数字1、2、3、…进行标识，边可以用二元组表示，比如(m,n)表示从节点m到节点n的有向边。

[0076] 控制流图节点分为赋值节点、分支点和汇聚点。赋值节点对应于程序的赋值语句，分支节点对应于条件语句的分支谓词。建立NLCFG之后，也建立起每个CFG节点与源程序语句的对应关系。

[0077] 对图6程序，其NLCFG如附图4所示，其共有8个节点，其中1、6为分支节点，2、3、4、5、7、8为赋值节点，返回语句也认为是赋值节点。同时，节点5还为循环体节点。

[0078] 对另一个实例程序GetMode，其源程序及其NLCFG如附图5所示。

[0079] 步骤2：根据CFG中产生依赖输入变量节点

[0080] 对于一个节点m，定义其执行前状态为Pre(n)，节点后状态为Pro(n)。所谓状态是指每个变量都有一个取值，或者说每个变量对特定值有一个映射。为方便区分，定义三个特定值：INIT、INPUT和UNDEF，分别表示初始化、依赖输入和没有定义。一个变量是依赖输入变量如果该变量能够完全被输入变量或者依赖输入变量定义。

[0081] 对于被分析程序的入口节点I0，定义其执行前状态Pre(I0)为：所有输入变量映射为INPUT，其余变量映射为INIT。

[0082] 针对NLCFG，从入口节点开始，依照深度优先策略，确定每一个变量是否是依赖输入变量。分析包括两步：（1）对节点的执行效果的分析；（2）对汇合节点的分析。

[0083] 一个节点执行后的状态是由该节点执行前状态以及节点执行对状态的影响两部分决定的。对于节点n，假定其定义的变量集合使用def(n)表示，其引用的变量集合使用ref(n)表示。如果ref(n)中变量在Pre(n)中都是依赖输入变量，那么，在Pro(n)中，在保留Pre(n)中变量状态的基础上，定义def(n)中变量为依赖输入变量。

[0084] 一个节点n的执行前状态是由所有该节点的前任节点状态确定。节点m是节点n的前任节点，如果NLCFG中存在一条边(m,n)。同时，节点n称为节点m的后续节点。

[0085] 对于节点n的所有前任节点，如果所有这些节点执行后状态中，一个变量的所有状态是依赖输入变量，则节点n的执行前状态中该变量的状态为依赖输入变量INPUT，否则为INIT。

[0086] 所谓深度优先策略是指，在处理一个节点后，把该节点的所有后续节点的排队依次处理。排队之后，对队列中的第一个节点仍然按照同样方法处理，这样只有在第一个节点及其后续节点处理完毕或者无法处理之后，才开始处理第二个节点。一个节点是无法处理的，如果该节点有一个前任节点的执行后状态是不确定的，即对于该前任节点的执行后状态，其所有变量的定义为UNDEF。对于无法处理的节点，将该节点重新排在队列末尾。

[0087] 具体的实现算法可参考图3。

[0088] 在图3中，初始化所有节点是将所有节点的执行前及执行后状态都设置为UNDEF，而定义第一个节点的执行前状态是将其状态设置为INIT。如果一个节点的执行前或者执行后状态为非UNDEF，也就是说该状态中所有变量的值不等于UNDEF，则称该节点的执行前或者执行后状态已定义。

[0089] 如前所述，在图3中，依据依赖输入变量定义确定节点i执行后状态是指，任给变量y∈ref(i)，如果y在Pre(i)中为INPUT，则def(i)中变量在Pro(i)中为INPUT，否则，Pro(i)中变量值等于Pre(i)中的相应值。

[0090] 举例来说，假定节点i对应语句U = (X-Y)*2，则def(i)={U}，ref(i)={ X,Y }，如果X和Y为INPUT，则在Pro(i)中变量U的状态为INPUT，而X和Y的状态保持不变，仍然为INPUT。

[0091] 同样，也如前所述，根据前任节点的执行后状态设置节点j的执行前状态是指，如果一个变量y在节点j的所有前任节点的执行后状态中都为INPUT，则变量y在Pre(j)中为INPUT。

[0092] 对于图5示例，如果变量X在节点7、8、9中的执行后状态都为INPUT，则变量X在节点10中的执行前状态也为INPUT。

[0093] 依照核心算法，对图6程序及其附图4所示的NLCFG，计算可知1、2、3、6为依赖输入节点，其余节点为初始化节点。

[0094] 同样，对于附图5GetMode实例及其NLCFG，除节点13外，其余节点都为依赖输入节点。

[0095] 步骤3：确定依赖循环变量、依赖非输入分支变量及其节点

[0096] 一个变量为依赖循环变量，如果该变量在循环体中定义，或者在该变量的定义中引用了依赖循环变量。一个变量为依赖非输入分支变量，如果该变量在非依赖输入分支谓词的分支中定义，或者在该变量的定义中引用了非输入分支变量。这两类变量统称为非依赖输入变量NOINPUT。

[0097] 针对一个循环体节点或者非依赖输入分支节点，通过确定一个变量在节点后状态为NOINPUT，从该节点开始，通过向后传递，可以确定所有的NOINPUT。

[0098] 针对一个循环体节点或者非依赖输入分支节点，，通过确定一个变量在节点后状态为NOINPUT，从该节点开始，通过向后传递分析，可以确定所有的NOINPUT变量。

[0099] 向后传递分析方法和步骤2输入依赖分析类似，也包括两步：（1）对节点的执行效果的分析；（2）对汇合节点的分析。

[0100] 此时，对于节点n，其分析与步骤2的分析有所不同：如果ref(n)中有一个变量在Pre(n)中是NOINPUT，那么，在Pro(n)中，def(n)中变量为NOINPUT。

[0101] 同样，节点n的所有前任节点中，如果有一个节点执行后状态中，变量x的状态是NOINPUT变量，则节点n的执行前状态中该变量的状态为NOINPUT。

[0102] 同时，引用变量或定义变量中有NOINPUT变量的节点为NOINPUT节点。

[0103] 对图6程序及其附图4所示的NLCFG，节点5和节点7为依赖循环节点。

[0104] 对于附图5GetMode实例及其NLCFG，节点11、12、13为依赖循环节点。

[0105] 步骤4：删除非依赖输入节点产生ICFG

[0106] 针对NLCFG，删除图中非依赖输入节点。删除的方法仍然按照节点的基本结构进行删除，所不同的是，如果一个分支节点或者汇合节点不包括任何节点，可以使用空节点表示。所谓空节点就是不执行任何操作的节点。空节点对应的语句为空语句。

[0107] 对图6程序及其附图4所示的NLCFG，将删除非依赖输入节点4、5、7、8，其中节点7、8将设置为空节点。

[0108] 对于附图5GetMode实例及其NLCFG，将删除非依赖输入节点11、12、13，节点11、12、13也将设置为空节点。

[0109] 最终形成的NLCFG为输入变量相关的，标记为ICFG。

[0110] 步骤5：产生ICFG的所有路径

[0111] 对于ICFG，可产生其所有路径。由于ICFG是单向图，可按照深度优先策略产生所有路径。

[0112] 对图6程序的ICFG，其路径共有四条：(1,2,6,7,8)、(1,2,6, 8)、(1,3,6,7,8)、(1,3,6, 8)。

[0113] 对于图5实例程序的ICFG，其路径共有12条，包括(1,2,3,5,6,7,10,11,13)、(1,2,3,5,8, 10,12,13) 、(1,2,4,5,8,9,10,12,13)等。

[0114] 步骤6：针对每条路径产生其输入条件

[0115] 假定对于路径(1,2,3,5,6,7,10,11,13)，对于其中节点5，假定其谓词针对输入的线性表达式为F5(X,Y,Z)=aX+bY+cZ+d。令X=2,Y=1,Z=100，沿着该路径，可以计算出F5 (2,1,100)=2，F5 (3,1,100)=4，所以可以求得a为：

[0116] a=( F5 (3,1,100)- F5 (2,1,100))/(3-2)=2

[0117] 同样，可以求得b=( F5 (3,2,100)- F5 (3,1,100))=(2-4)/(2-1)=-2[0118] 以及c=1,d=-100

[0119] 所以，F5(X,Y,Z)=2X-2Y+Z-100

[0120] 同理，可以得到F10(X,Y,Z)= 3X-Y -2，以及F2(X,Y,Z)= X-Y。

[0121] 根据路径(1,2,3,5,6,7,10,11,13)的分支取值，可以得到线性规划问题求解：

[0122] min X + Y + Z 满足:X–Y>0 2X - 2Y + Z –100 >0 3X -Y–2≤0

[0123] 利用线性规划解析程序，可以求得：< X =-50，Y =-51，Z =100>

[0124] 此即为路径(1,2,3,5,6,7,10,11,13)的输入条件。

[0125] 对图6程序，其输入情况比较简单，即包括exponent < 0和exponent ≥ 0两种情况，分别对应路径 (1,2,6,7,8)和(1,3,6, 8)，而路径(1,2,6, 8)和(1,3,6,7,8)为不可行路径。

[0126] 步骤6：产生该路径对应的WCET

[0127] 对于基于树的计算方法，对于某条路径的WCET，只需要计算整个程序中对应于该路径的WCET。也就是说，对于条件语句，只计算属于该路径的分支。

[0128] 对图6程序，对于路径(1,2,6,7,8)，其对应于输入情况exponent < 0，其WCET为：

[0129] WCET(1,2,6,7,8) = WCET(语句3) + WCET(语句4) + WCET(语句7) +

[0130] WCET(语句8) + ( WCET(语句8) + WCET(语句9) )*(- exponent) + WCET(语句10) + WCET(语句11) + WCET(语句12)

[0131] 根据之前的假定，可计算出路径(1,2,6,7,8)的WCET为：

[0132] WCET(1,2,6,7,8) = 111 + 301 + 270 + 117 + (117+317)*(- exponent)+111+560+244

[0133] = 1714+(434) *(- exponent)

[0134] 同样，对于路径(1,3,6, 8)，其对应于输入情况exponent ≥ 0，其WCET为：

[0135] WCET(1,3,6, 8) = WCET(语句3) + WCET(语句6) + WCET(语句7) +

[0136] WCET(语句8) + ( WCET(语句8) + WCET(语句9) )*(exponent) + WCET(语句10) + WCET(语句12)

[0137] = 111+283+ 270 + 117 + (117+317)*(- exponent)+111+244

[0138] = 1136+(434) * exponent。