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

1650 Journal of Software 软件学报 Vol.32, No.6, June 2021

生成的带有各种分支条件的代码将会非常冗长且低效.具体的分支标记和化简方法会在第 2 节中详细描述.
• 第 3 步,根据分支标记生成基于控制流的组件代码生成位置表.
建立一个空的组件代码生成位置表,将最开始的被标记{0}分支的组件,按调度顺序依次插入到生成位置表
中,遇到分支组件则在生成位置表中插入分支数量个 Branch 标记,后续组件若满足这个 Branch 标记的分支状
态,就插入到这个 Branch 标记后面,如图 1(d)所示.在遇到分支合并的组件时,这些 Branch 标记就会被删除,后面
再有新的分支则会创建新的 Branch 标记.更加详细的代码生成位置表的构造方法会在第 3 节中说明.
• 最后,直接根据基于控制流的组件代码生成位置表生成目标编程语言的代码.
这里的生成位置表相当于伪代码的作用,可以直接翻译为各种主流的编程语言.

2 模型调度顺序的计算

模型调度顺序的计算是生成代码的第 1 步.我们将模型视为一个有向无环图,通过对该图进行拓扑排序,确
定各个组件的执行顺序.这里需要注意的是:对于带有环的数据流模型,我们要将环路中寄存器类型的组件拆分
为存和取两部分,通过这种方式打破环路.用于代码生成的数据流模型,如果存在数据环路,那么其环路中必定
有延时、队列、数据池等寄存组件;否则,一旦执行到环路,模型将进入死循环.接下来要对模型进行拓扑排序,
找到模型中没有任何输入数据的组件,这些组件作为排序的第 1 层.然后消除第 1 层的组件和与它们连接的所
有数据流连线,继续寻找没有任何输入数据的组件,把新找到的这些组件作为排序的第 2 层.后面的各层以此类
推.由于已经事先将数据环打破,所以该排序可以在有限步骤内完成.我们仅对模型进行分层,而没有必要对层
内的组件执行顺序进行计算,因为同层的组件的执行不会相互影响.
为了更直观、更清晰地介绍模型调度顺序的计算和后续算法,下面采用一个带有分支嵌套的模型进行介
绍,模型如图 2 所示.图 2 中,用矩形表示一般组件,对于一般组件,我们可以将其简化地理解为根据给定的输入数
据计算得到输出数据,输出数据再根据组件间的连线向后传递;用三角形表示分支组件,为了描述起来更加简
单,这里仅采用二分支的组件进行演示,如图中的 B,F,G 这 3 个组件就是二分支组件,这些组件的左边有一个输
入端口,右边有两个输出端口,这些组件会根据特定条件将输入端口的数据选择性地输出到第 1 个输出端口或
第 2 个输出端口的其中一个,而另一个输出端口则不会向后输出数据,也不会触发后面的组件执行.整个模型的
调度顺序是从左向右进行的,按拓扑排序进行分层会将整个模型分为层 1~层 8 共 8 层.这个模型包含了除分支
交叉(不同的分支组件之间的分支发生合并)的多种复杂分支结构,例如在图 2 中,有 B 和 F 构成的分支嵌套的情
况、B 和 E 构成的分支提前结束的情况、H 和 I 和 M 构成的不同数据源的分支合并的情况、M 和 J 和 K 和 N
构成的跨多个分支的分支交叉和合并的情况.

H L
F
C I M
A B
D J N O
G
E K

层1 层2 层3 层4 层5 层6 层7 层8
Fig.2 Schematic diagram of a model with complex branches structure
图 2 具有复杂分支结构的模型示意图
3 分支标记的计算与简化

在介绍分支标记算法前,先明确几个数据表示的概念:分支(Branch),表示分支组件的单个分支,它由分支组
件和分支号(该分支组件的第几个分支)这两个数据唯一表示,记为 IdActor,Id 表示分支号,Actor 表示分支组件;