一种COStream语法分析过程中符号表和静态数据流图生成方法转让专利
申请号 : CN202010679621.2
文献号 : CN111949269B
文献日 : 2021-06-11
发明人 : 于俊清 , 黄业兴 , 李新星
申请人 : 华中科技大学
摘要 :
权利要求 :
1.一种COStream语法分析过程中符号表生成方法,其特征在于,该方法包括以下步骤:S1.在COStream中将作用域分为全局作用域、块作用域、Composite作用域以及Operator作用域,其中,所述全局作用域为整个程序代码,所述块作用域为一对大括号之间包含的程序代码,所述Composite作用域为Composite结构内部的程序代码,所述Operator作用域为Operator结构内部的程序代码;
S2.构建满足COStream中Stream、Operator和Composite文法结构特性的COStream符号表,构建的COStream符号表包括:变量表、Stream表和Composite表;
S3.初始化COStream符号表,使用Level字段表示当前作用域的层次深度,使用Number字段表示同一Level下当前作用域处于并列作用域的编号,Level初始化为0,Number在每一层Level下初始化为0;
S4.每当解析到全局作用域、Composite作用域、Operator作用域和块级作用域时都生成新的作用域,使用作用域栈和表示当前作用域的top指针实现作用域的层次控制,所有的作用域都以Level和Number为下标保存在二维数组中。
2.如权利要求1所述的方法,其特征在于,所述全局作用域用于存储全局声明的变量、数据流、函数以及Composite;所述块作用域用于存储声明的局部变量和局部数据流;所述Composite作用域用于存储Composite结构中声明的输入输出数据流参数、参数列表以及Composite内声明的变量;所述Operator作用域用于存储Operator结构中的初始化变量和输入输出数据流。
3.如权利要求2所述的方法,其特征在于,所述变量表中用于存储变量名、变量类型、变量是否是数组、变量值和抽象语法树中声明该变量的节点;所述Stream表用于存储Stream名、Composite调用时数据流参数真正的数据流名、数据流内数据类型和抽象语法树中声明该Stream的节点;所述Composite表用于存储Composite名称、Composite中的参数数据流、参数变量、Composite被调用的次数和抽象语法树中声明该Composite的节点。
4.如权利要求2或3所述的方法,其特征在于,步骤S4具体如下:全局作用域作为整个作用域层次结构的顶点被添加到作用域栈中,此时top指针指向此全局作用域;
在进入下一层作用域,具体执行的步骤包括:①生成新的作用域,使用变量表、Stream表和Composite表保存当前作用域下解析到的标识符信息;
②将新的作用域推入作用域栈中保存;
③将top指针指向新的作用域,并将作用域层次深度Level加1;
在遍历完当前作用域返回上一层时,进行作用域层次的回退操作,具体步骤包括:①将top指针指向作用域栈栈顶;
②作用域栈出栈得到上一层作用域;
③Level减1,上一层作用域的NUmber加1。
5.如权利要求1至4任一项所述的方法,其特征在于,每一个作用域都有一个前向指针指向上层作用域,形成一个由子节点指向父节点的反向树状结构。
6.一种基于符号表的COStream编译的静态数据流图生成方法,所述符号表采用如权利要求1至5任一项所述的方法生成,其特征在于,该方法包括:(1)通过执行上下文模拟Composite调用,每当遇到一个Composite调用,生成新的执行上下文,并保存当前Composite调用下的参数信息到执行上下文中的符号表;
(2)根据执行上下文中确定的Composite调用的参数信息,对Composite结构内的赋值语句、条件语句以及循环语句进行常量传播分析,确定变量的常量值,并根据程序的执行路径将常量值传递下去,并对Splitjoin、Pipeline和add语句进行分析,生成Composite调用数组,用于保存展开过程中的Composite调用;
(3)每一个Operator结构都会生成一个静态数据流图中的节点,如果程序中包含嵌套数据流结构,则根据得到的Composite调用数组,通过由外向内逐层展开嵌套数据流程序的方式来生成静态数据流图;通过由内向外逐层确定静态数据流图中嵌套结构中的计算节点传递的数据个数。
7.如权利要求6所述的方法,其特征在于,所述通过执行上下文模拟Composite调用,包括以下子步骤:
(1)将上层执行上下文推入执行上下文栈中,生成新的执行上下文,并用指针指向当前执行上下文;
(2)初始化执行上下文,保存当前Composite作用域;
(3)解析Composite调用传入的参数数值,得到参数所对应的值,保存在变量表中,解析Composite调用传入的输入输出数据流,保存到Stream表中数据流参数所对应的真实数据流名字段中,指明数据流参数所对应的真实数据流;
(4)解析完当前Composite调用后,进行执行上下文的回退操作。
8.如权利要求6或7所述的方法,其特征在于,所述常量传播包括:对于赋值语句,根据计算表达式所涉及的变量,从当前执行上下文中查找变量对应的常量值,计算出表达式的结果,并将计算得到的常量值保存到执行上下文中对应的变量中;
对于条件判断语句,根据条件语句的判断结果确定程序的执行路径;
对于for循环语句,分析循环语句的初始条件、结束条件以及循环变量,确定循环次数;
按照循环次数模拟循环内语句的执行,计算出变量的常量值;
对Splitjoin、Pipeline和add语句,生成Composite调用数组,用于保存展开过程中的Composite调用。
9.如权利要求6至8任一项所述的方法,其特征在于,嵌套数据流结构的展开从最外层Splitjoin或Pipeline结构开始,每一层嵌套结构的展开分为如下步骤:①根据得到的Composite调用数组,将数组中保存的Composite调用进行数据流连接;
对于Pipeline结构,则将Composite调用串行连接;对于Splitjoin结构,则将数组中的Composite调用上端与Split节点并行连接,下端与Join节点并行连接;
②对Composite调用数组中的Composite调用进行逐个解析,如果Composite调用是Operator的封装,则生成静态数据流图中的节点,如果Composite调用是Splitjoin或Pipeline结构的封装,则进一步展开;
③回到步骤①重复执行,由外向内对内层嵌套Splitjoin或Pipeline结构进行展开,直到解析到最内层嵌套结构。
10.如权利要求6至9任一项所述的方法,其特征在于,由内向外对每层Splitjoin结构中计算节点的输入输出数据的个数进行分析,并根据分析结果修改每层Splitjoin结构的Split和Join节点的方法,使静态数据流图能达到稳态调度,具体步骤如下:(i)计算内层Splitjoin结构每个分支达到稳态调度时,输入输出的数据个数;
(ii)计算每个分支输入输出的数据个数的比值;
(iii)根据比值修改内层Split和Join节点;
(iv)如果该层Splitjoin结构不是最外层嵌套结构,则回到步骤(i)重复执行;
所述根据比值修改内层Split和Join节点具体为:Split节点根据每个分支所需数据个数比值,修改Split节点为每个分支分配的数据个数,并根据比值之和修改Split节点接收的数据个数;Join节点根据每个分支产生的数据个数的比值,修改Join节点从每个分支接收的数据个数,并根据比值之和修改Join节点输出的数据个数。
说明书 :
一种COStream语法分析过程中符号表和静态数据流图生成
方法
技术领域
背景技术
Operator代表一个计算单元,其中包含数据的计算过程;Composite是对一个或多个
Operator的封装,通过对Composite的调用实现计算节点的复用。用户使用这三种结构描述
算法过程,由COStream编译器通过分析生成静态数据流图,并依次进行工作量估计、任务划
分、流水线构建和生成可并行计算的目标代码。COStream语言具有广泛的应用领域,当前主
要用于面向大数据处理的应用,如媒体处理、信号处理、搜索应用、数据文件处理等。目前由
于COStream无法使用变量来控制计算节点的调用,而导致无法编译部分复杂算法,应用场
景受限。
换不必要的指令,加快目标代码的运行速度。主要分为:简单常量传播、稀疏简单常量传播、
条件常量传播和稀疏条件常量传播。“一种基于代数系统的跨文件过程间优化方法”和“基
于路径包含处理方法的源代码静态分析方法及其装置”等专利,使用的常量传播方法只关
注简单表达式的计算,不支持分析函数调用过程中参数传递对变量的常量值的影响,同时
也不支持对循环语句中常量值的挖掘。在COStream中实现常量传播方法需要结合
Composite调用传递的参数,对赋值语句、条件语句和循环语句进行分析,来挖掘COStream
中的常量值。
作为数据流编程语言,与面向对象编程语言差异较大,其中引入了Stream、Composite与
Operator等全新的文法结构,并且在静态数据流图生成过程中需要频繁地读写变量值、数
据流类型和Composite参数等信息,所以需要结合上述需求设计COStream符号表的存储信
息和存储结构,并且因为一般编程语言的作用域仅划分为全局作用域和块级作用域,采用
树形结构存储作用域,无法满足COStream中内层Operator结构对外层Composite结构中标
识符的读写需求,所以需要对COStream的作用域进行合理的划分,设计合适的作用域层次
结构。
发明内容
COStream能够编译包含由变量控制计算节点调用的复杂程序,扩大了COStream的应用场
景,并且简化了编写嵌套数据流程序的方式,减少了代码量,提高了COStream的用户友好
性。
包含的程序代码,所述Composite作用域为Composite结构内部的程序代码,所述Operator
作用域为Operator结构内部的程序代码;
在每一层Level下初始化为0;
有的作用域都以Level和Number为下标保存在二维数组中。
Composite结构中声明的输入输出数据流参数、参数列表以及Composite内声明的变量;所
述Operator作用域用于存储Operator结构中的初始化变量和输入输出数据流。
参数真正的数据流名、数据流内数据类型和抽象语法树中声明该Stream的节点;所述
Composite表用于存储Composite名称、Composite中的参数数据流、参数变量、Composite被
调用的次数和抽象语法树中声明该Composite的节点。
一作用域出发,都能够顺着前向指针一步一步快速地得到所有上层作用域,形成作用域链。
行路径将常量值传递下去,并对Splitjoin、Pipeline和add语句进行分析,生成Composite
调用数组,用于保存展开过程中的Composite调用;
序的方式来生成静态数据流图;通过由内向外逐层确定静态数据流图中嵌套结构中的计算
节点传递的数据个数。
数据流名字段中,指明数据流参数所对应的真实数据流;
量中;
Composite调用上端与Split节点并行连接,下端与Join节点并行连接;
Pipeline结构的封装,则进一步展开;
图能达到稳态调度,具体步骤如下:
据个数的比值,修改Join节点从每个分支接收的数据个数,并根据比值之和修改Join节点
输出的数据个数。
设计了作用域层次结构和符号表存储信息,实现满足COStream新增文法结构Stream、
Operator和Composite特性的符号表和对作用域的快速存储和读取。
息;常量传播结合Composite调用的参数信息,确定包含Composite调用的程序执行路径,在
此基础上,实现了对条件语句和循环语句的常量传播方法,能够挖掘出程序中所包含的更
多的常量信息;根据这些常量信息,实现了COStream对包含由变量控制计算节点的程序的
编译,使其能够编译实现更多复杂的算法,扩大了COStream的应用场景;嵌套数据流结构的
实现使得在使用COStream编程时,能够嵌套使用Splitjoin和Pipeline编程结构,简化了编
写嵌套数据流程序的方式,缩短了代码量,提高了编译速度,提高了COStream的用户友好
性。
附图说明
据个数,(b)为修改内层Split节点和Join节点输入输出的数据个数,(c)为对内层
Splitjoin结构每条分支分析得到各分支所需以及产生的数据个数,(d)为修改外层Split
节点和Join节点输入输出的数据个数。
具体实施方式
不用于限定本发明。此外,下面所描述的本发明各个实施方式中所涉及到的技术特征只要
彼此之间未构成冲突就可以相互组合。
作用域层次结构和符号表存储信息。
某层次深度下当前作用域处于并列作用域的第几个。每一个作用域都有一个指针pre指向
上层作用域,通过这种方式在作用域之间形成作用域链,来链接有上下级关系的作用域。
中维护这三个表。
来指向变量表中对应的变量。
实际保存在Stream表中,所以通过指针指向Stream表中对应的数据流。变量参数保存的是
Composite参数中的变量信息,因为变量信息实际存储在变量表中,所以通过指针指向变量
表中对应的变量。
键值对的方式存储表自负信息,键就是标识符的名字,值就是标识符相关的信息。
用域C1中保存在A中声明的参数“Count”。“Main”中的for循环也划分为一个块级作用域B1,
用以保存for循环中声明的变量。在图1中也展示了作用域的层次关系,其中使用Level和
Number唯一标记作用域,其中,Level表示当前作用域的层次深度,Number表示某层次深度
下当前作用域处于并列作用域的第几个。全局作用域处于第0层,即Level为0。在进入全局
作用域下声明的Composite结构时,作用域层次深度加一,即Level为1。在该层下有两个并
列的作用域C1和C2,使用Number进行标记区分,即相同作用域层次深度下第一个作用域C1
的Number值为0,第二个作用域C2的Number值为1。在Composite作用域C2下包含以for循环
语句,因此进行下一层块级作用域B1,此时Level为2,由于在B1为该层下唯一的一个作用
域,因此Number为0。在B1下包含if语句和else语句,分别生成两个块级作用域B2和B3。其作
用域层次深度Level为3,在该层次下包含两个作用域,因此B2的Number值为0,B3的Number
值为1。
间形成作用域链,来链接有上下级关系的作用域。
于在取值时根据数据类型来读取对应的常量值;Array用于标明此变量是否为数组,其类型
为布尔类型;Value存储变量的常量值,其类型为Constant类,用于保存整型、浮点数、字符
串、数组等不同数据类型的值;Node为一个指针,指向当前变量在抽象语法树中的节点。
Type 变量数据类型
Array 变量是否是数组
Value 变量值
Node 抽象语法树中声明该变量的节点
则存储Composite调用时数据流参数真正的数据流名,否则为空。StreamType存储数据流中
数据的类型,为一个指针列表。因为数据流内部数据变量的声明实际存储在变量表中,所以
通过指针来指向变量表中对应的变量。StreamType用于检测数据流使用的正确性;Node为
指针,指向当前数据流在抽象语法树中的声明节点。
相关的数据流信息实际保存在Stream表中,所以通过指针指向Stream表中对应的数据流。
Streams字段用于关联数据流参数和Composite调用时的实际输入输出数据流;Parameters
保存Composite结构的参数列表,其类型为指针列表,因为相关的参数变量信息实际存储在
变量表中,所以通过指针指向变量表中对应的变量。Parameters字段能够关联参数和实际
调用Composite时传入的值,用于实现执行上下文的模拟;Count保存当前Composite被调用
的次数,其类型为整数,用于区分多次调用同一个Composite时其内部声明的同名数据流;
Node为指针,指向抽象语法树中对应的Composite声明结点。
Name Composite名称
Streams Composite中的参数数据流
Parameters Composite中的参数变量
Count 当前Composite被调用的次数
Node 抽象语法树中声明该Composite的节点
流图生成方法是通过对抽象语法树的解析来生成静态数据流图,生成的过程中,需要使用
到上述生成的符号表中的变量值、Composite调用时数据流参数真正的数据流名和
Composite中的参数变量等信息。以下介绍执行上下文模拟和常量传播的具体实现方法。
Composite作用域保存当前Composite的作用域信息。本质上,执行上下文就是Composite调
用时根据参数信息生成的作用域,其符号表的变量表保存Composite被调用时的参数信息,
数据流表保存输入输出数据流信息。
指明数据流参数所对应的真实数据流。
变量中。
Composite调用的执行上下文;②常量传播。在执行上下文的基础上对Composite内部语句
进行常量传播分析,确定计算节点的调用次数和传递的数据个数;③静态数据流图中节点
生成。对抽象语法树的不同节点进行解析,生成数据流图中的节点。通过上述三个步骤,由
抽象语法树生成静态数据流图。静态数据流图生成方法中常量传播为关键方法。
循环语句进行常量传播分析,确定变量的常量值,并根据程序的执行路径将常量值传递下
去。根据变量的常量值可以确定计算节点的调用次数和传递的数据个数等信息。在常量传
播过程中对Splitjoin、Pipeline和add语句的分析过程中,会生成实际被调用的Composite
数组,来保存展开过程中的Composite调用。以下是常量传播过程中对不同语句的处理:
确保变量类型与常量值的一致性。赋值语句在解析过程中根据计算表达式所涉及的变量,
从当前执行上下文中查找变量对应的常量值,并计算表达式的结果。根据被赋值的变量,将
计算得到的常量值保存到执行上下文中对应的变量中。
中。如果为假,则对假值情况下的语句块进行解析。在语句块的解析过程中如果存在
Composite调用,则将此Composite调用添加到Composite调用数组中,用于记录在程序执行
时会被调用的Composite,以此来确定计算节点的调用次数。
次数模拟循环内语句的执行,进行常量传播分析。在模拟过程中为每次循环执行生成新的
作用域,记录当前循环内变量的常量值。③如果循环语句内存在Composite调用语句,则将
Composite调用添加到Composite调用数组中,来确定Composite在循环中被调用的次数。如
果Composite调用传入的参数会随循环的执行而改变,则复制Composite调用语句,将参数
变量替换为每次循环中变量的常量值。
值,将该值封装到Composite调用语句中,完成Composite调用语句参数的常量化。
add语句经分析处理后的Composite调用添加到数组中,来确定Splitjoin和Pipeline语句
内部计算节点的调用次数以及参数值。在解析Splitjoin或Pipeline结构生成静态数据流
图中的节点时,会根据此数组展开Splitjoin或Pipeline结构。Splitjoin和Pipeline内部
语句按上述步骤递归进行分析。
Transform,FFT)的部分代码。图中最左侧是变量n的常量传播过程,其值来自CombineDFT调
用传入的参数8,并将值传递到for循环语句中。中间部分展示变量j的常量传播过程。j的值
随for循环的执行而变化。通过对for循环的解析,得出for循环会执行三次。对每一次循环
进行模拟,得到每次循环中j的值分别为2、4、8。for循环包含在Pipeline结构中,且在for循
环中包含CombineDFTX调用,并传入j作为参数。因此在每一次循环中,常量传播得到的j的
值作为参数保存在CombineDFTX调用中,每一次循环中CombineDFTX调用则存储在Pipeline
结构的Composite调用数组中。右侧展示的是变量TN的常量传播过程,其值来自Pipeline结
构中Composite调用数组的三个CombineDFTX调用。通过对三次CombineDFTX调用的解析,为
每一次调用生成新的执行上下文,执行上下文中保存每次CombineDFTX调用传入的参数值
2、4、8作为TN的值。
图生成过程中,分析嵌套使用的Splitjoin和Pipeline结构时,需要解决内外层结构计算节
点之间的数据流连接,以及正确指定每一个计算节点的输入输出的数据个数。
骤:
构,则将数组中的Composite调用上端与Split节点并行连接,下端与Join节点并行连接。
(a)中的R0和R1。如果Composite调用是Splitjoin或Pipeline结构的封装,则进一步展开,
如图6中的(a)中的SP1。
数进行分析,并根据分析结果修改每层Splitjoin结构的Split和Join节点的方法,使静态
数据流图能达到稳态调度,具体步骤如下:
数据个数;Join节点根据每个分支产生的数据个数的比值,修改Join节点从每个分支接收
的数据个数,并根据比值之和修改Join节点输出的数据个数。
所示。内层Splitjoin在稳态调度时,左右两个分支所需的数据个数为1、1,产生的数据个数
为1、1。由此计算每个分支输入输出的数据个数的比值分别为1:1和1:1,根据比值修改内层
Split1和Join1节点。Split1节点根据每个分支所需数据个数比值,修改Split1节点为每个
分支分配的数据个数,并根据比值之和修改Split1节点接收的数据个数;Join1节点根据每
个分支产生的数据个数的比值,修改Join1节点从每个分支接收的数据个数,并根据比值之
和修改Join1节点输出的数据个数。在图7中的(b)中,因为内层Split1和Join1节点默认设
置的数据个数和分析每条分支所得出的结果相同,所以不需要修改。
的个数之比为2:1:1。外层Splitjoin结构的Split0节点为每个分支默认分配的数据个数为
1、1、1,与分析结果相同,但是Join0节点从每个分支默认接收的数据个数为1、1、1,与分析
结果不符。对外层Join0节点进行修改,使其从每个分支接收的数据个数为2、1、1,如图7中
的(d)所示。通过上述步骤实现多层Splitjoin嵌套结构中计算节点传递的数据个数的确
定,以及Split节点分发和Join节点合并数据时传递的数据个数的修正,使修正后的数据流
图能达到稳态调度。
在本发明的保护范围之内。