Page 75 - 《软件学报》2021年第6期

苏卓 等:基于分支标记的数据流模型的代码生成方法 1649

(2) 分支组件嵌套该如何进行有效的控制流分析.每个组件都会受到其前面的全部分支组件的分支的影
响,那么当该分支后面存在分支(甚至在该分支后面存在更多分支)时,如何针对多层的分支信息进行
分支化简及合并是一个复杂的问题;
(3) 分支组件存在分支交叉时,该如何生成控制流代码.在模型表达层面,两个分支组件各自的一个分支
都汇聚到了同一个组件上,这种表达意味着汇聚到同一个组件上的两个分支,只要至少一个分支可以
触发,该组件就可以执行.所以那该件的数据源可能会有 3 种情况(数据分别来自两个分支和数据共同
来自两个分支).多个分支组件之间的分支交叉,可能会带来非常多的分支执行路径的可能,这也是自
由使用分支组件所带来的代码生成的最大的难题.
本文针对数据流分支的代码生成问题进行了深入的研究,提出了一种针对数据流模型中任意复杂的分支
组件组合的代码生成算法.该算法的主体是按照数据流的拓扑排序从前向后依次进行的:首先,根据分支组件的
分支信息为其后继组件添加控制流标签,由于某些组件会处于不同的分支下,所以之后要将组件所有的分支情
况进行化简合并.所有组件的分支信息都计算完之后,构造一个组件代码生成位置表,通过各个组件的分支信
息,向这个列表中插入分支和组件数据源信息.由于存在分支,有的组件可能会被插入到多个位置.最终得到的
列表就是完整的基于控制流的组件执行顺序.按这个生成位置表对各个组件分别生成代码,即可得到完整的模
型的代码.
1 研究思路

针对复杂的数据流模型,首先要对模型进行调度分析,根据模型中的分支组件为所有组件计算分支标记,在
分支标记过程中,对组件的分支信息进行化简处理;其次,根据每个组件的简化分支信息构造组件代码生成位置
表;最后,根据组件代码生成位置表就可以生成完整的复合模型调度顺序的代码.针对数据流模型中分支组件的
代码生成方法的主体框架如图 1 所示.

1 A 1 A
C C {0,0}
2 B 2 if (B) {
A B A B {0} {0} C 3 Branch B0: 3 C
分支 D 分支 D A B {0,1} 4 C 4 } else {
分支 5 Branch B1: 5 D
D 6 D 6 }
层1 层2 层3 层1 层2 层3
(a) 数据流模型 (b) 模型调度顺序 (c) 简化的分支标记 (d) 组件代码生成位置表 (e) 完整代码
Fig.1 Framework of code generation method for branch actors in data flow model
图 1 针对数据流模型中分支组件的代码生成方法框架
• 第 1 步,对数据流模型进行调度分析.
数据流模型的调度顺序是按照拓扑排序确定的:首先找到模型中没有数据输入的组件,将它们设置为第 1
层;之后,把这些组件在模型中去除,再次寻找没有数据输入的组件,将这些新找到的组件设置为第 2 层.以此类
推.对于模型中的数据延时组件,我们将其视为首尾断开的两个组件,用这样的方式来打破模型的环路.
• 第 2 步,根据调度顺序,逐层确定分支标记.
从模型的第 1 层开始,对组件添加分支标记,这些分支标记是会根据组件的连接关系向后传递的.默认模型
最开始就有一个分支,我们将处于第 1 个分支上的组件标记为{0}.之后,如果遇到分支组件,就在分支组件后面
进行叠加标记;同样的,分支组件的第 1 个分支用{0}标记,第 2 个分支用{1}标记,如图 1(c)所示.由于分支信息是
从前向后叠加的,所以在对模型中任何一个组件进行分支标记前,首先对该组件所有的前驱组件的分支进行合
并化简处理,这样就可以尽早地完成分支的合并,以避免代码生成的“分支爆炸”的现象.这里的“分支爆炸”指的
是由于分支组件的组合使用(包括多个分支组件的不同分支的交汇以及分支组件的嵌套),会造成后续组件可能
的执行情况数会成指数增长.如果每个组件都继承前驱组件带来的所有分支情况,并且按组件所有的分支情况