基于基本块的汇编代码得出程序的数据流图的实现方法

摘要

本发明涉及处理器结构设计领域，旨在提供一种基于基本块的汇编代码得出程序的数据流图的实现方法。该方法包括下述步骤：分类模块对指令进行分类；关系分析模块对指令间的依赖关系进行分析并分类；数据流图分析模块针对第一种情况下的指令间的依赖关系得出数据流图。本发明中，程序的数据流图可能出现不规则的情况，这就意味着数据流图能够背分割成数据流子图。本发明是根据汇编代码对指令进行划分，得出3种指令，然后分别考虑3种指令中的两种指令之间的依赖关系，得出程序的数据流图。采用本方法可以提高指令的执行效率，还可以提高处理器性能。

说明书

技术领域

本发明涉及处理器结构设计领域，特别是涉及一种基于基本块的汇编代码得出程序的数据流图的实现方法。

背景技术

乱序处理机可以通过增加指令发射的宽度来提高性能，但是，传统增加指令发射宽度的方法并不能提高计算机性能，也就是说增加了设计的复杂性和能耗需求。在执行核中，一个发射指令宽的处理器需要更大更宽的结构去支持更多的并行处理的指令，这些指令包括指令调度器、寄存器文件、旁路网络。如果设计采用更大更宽的结构，其流水线必须支持很大的时钟频率。但是在执行关键循环时，流水线结构可能会使性能下降。

发明内容

本发明的目的在于克服现有技术中的不足，提供一种基于基本块的汇编代码得出程序的数据流图的实现方法。

本发明解决其技术问题采用的技术方案如下：

提供一种基于基本块的汇编代码得出程序的数据流图的实现方法，包括以下步骤：

(1)分类模块对指令进行分类

分类模块根据汇编代码把指令分为三类：第一种指令中有两个输入一个输出；第二种指令中含有一个输入一个输出；第三种指令中含有一个输入零个输出；

(2)关系分析模块对指令间的依赖关系进行分析并分类

指令间的依赖关系存在三种情况：

第一种情况：考虑第一种指令和第二种指令之间的依赖关系，再单独考虑第三种指令之间的依赖关系；

第二种情况：考虑第二种指令和第三种指令之间的依赖关系，再单独考虑第一种指令之间的依赖关系；

第三种情况：考虑第一种指令和第三种指令之间的依赖关系，再单独考虑第二种指令之间的依赖关系；

(3)数据流图分析模块针对第一种情况下的指令间的依赖关系得出数据流图

第一步，链表创建器建立链表

文件扫描器对汇编代码文件中的汇编指令逐条进行扫描，扫描的同时链表创建器对每条汇编指令建立指令结点；

指令结点node包含七个域：op域、输入一input1域、输入二input2域、输出output域、寄存器的个数num域、标签tag域、next域；

op域用来存放指令中的操作码，输入一input1域和输入二input2域是寄存器值的输入，输出output域是寄存器值的产生者，next域用来存放下一个节点的地址；当在一条指令中有两个相同的寄存器时，看作两个不同的寄存器，因为寄存器的值不相同，在建立链表的同时对标签tag域进行初始化为0，并计算每条指令中寄存器的个数num；

第二步，链表扫描器扫描链表

顺序查找过程：链表扫描器首先判断结点的num域是否等于1，如果等于1，则该结点单独作为一个数据流图；如果不为1，则把第一个结点的标签域tag设置为n，并且顺序比较第一个结点的输出域与其余结点的输入域；如果链表扫描器找到一个结点的输入域与第一个结点的输出域相同，则把该结点的标签域tag设置为n，并且把该结点作为第一个结点；顺序比较该结点的输出域与其余结点的输入域，如果相同，则把该结点的标签域tag设置为n；链表扫描器继续顺序查找，一直查找到链表末尾；

链表扫描器返回到链表的头结点，从头结点开始查找，本次查找是查找结点的标签域tag是否被修改过，如果找到结点的标签域tag没有被修改过，则把该结点作为第一个结点，重复上面的顺序查找过程，但是不同的是该结点的标签要修改等于n+1；如果链表扫描器找到标签域tag被修改的结点，则保持原来的值不变，并且在本次查找中，之前标签域tag修改为n+1的结点要重新修改为n，停止本次查找；重复上面的顺序查找过程；

新链表的顺序查找过程和顺序查找第一个链表num域值不为1的查找过程相同；

第三步，数据流图输出模块输出数据流图

数据流图输出模块根据链表中的每个结点的标签域tag值的不同，得到指令结点的数据流图；数据流图输出模块把相同tag值的结点作为一个数据流图，没有相同的则单独作为一个数据流图。

与背景技术相比，本发明具有的有益的效果是：

程序的数据流图可能出现不规则的情况，这就意味着数据流图能够背分割成数据流子图。本发明是根据汇编代码对指令进行划分，得出3种指令，然后分别考虑3种指令中的两种指令之间的依赖关系，得出程序的数据流图。采用本方法可以提高指令的执行效率，还可以提高处理器性能。

附图说明

图1为本发明中考虑第一种指令和第二种指令之间的依赖关系得出数据流图的流程图。

具体实施方式

本方法的具体过程及实例如下：

(1)分类模块对指令进行分类

分类模块根据汇编代码把指令分为三类。第一种指令：该指令中有两个输入一个输出，如：addq a1，t4，t0，这条指令意思就是将a1寄存器中的值加上t4寄存器中的值相加，并将其和存放到t0寄存器中，addq表示指令操作码，寄存器a1、t4表示两个输入，t0表示输出；第二种指令：该指令中含有一个输入一个输出，如：了ldl t3，0(t0)，这条指令意思就是将寄存器t0中的值加上零后并将其和存储到寄存器t3中，ldl表示指令操作码，寄存器t0表示输入，寄存器t3表示输出；第三中指令：一个输入零个输出，如：bne t1，0x1200eb2b，这条指令意思就是如果寄存器t1中的值不相等零，就转到地址0x1200eb2b处继续执行，bne表示指令操作码，寄存器t1表示输入，0x1200eb2b是跳转地址。

(2)关系分析模块对指令间的依赖关系进行分析并分类

在本方法中主要考虑三中情况，第一种情况：考虑第一种指令和第二种指令之间的依赖关系，再单独考虑第三种指令之间的依赖关系；第二种情况：考虑第二种指令和第三种指令之间的依赖关系，再单独考虑第一种指令之间的依赖关系；第三种情况：考虑第一种指令和第三种指令之间的依赖关系，再单独考虑第二种指令之间的依赖关系。

(3)数据流图分析模块针对第一种情况下的指令间的依赖关系得出数据流图

本方法只实现第一种情况：考虑第一种指令和第二种指令之间的依赖关系，再单独考虑第三种指令之间的依赖关系，主要分为以下几步：

第一步，链表创建器建立链表

文件扫描器对汇编代码文件中的汇编指令逐条进行扫描，扫描的同时链表创建器对每条汇编指令建立指令结点。

指令结点node包含七个域：op域，输入一input1域，输入二input2域，输出output域，寄存器的个数num域，标签tag域，next域。op域用来存放指令中的操作码，输入一input1域和输入二input2域是寄存器值的输入，输出output域是寄存器值的产生者，next域用来存放下一个节点的地址，当在一条指令中有两个相同的寄存器时，看作两个不同的寄存器，因为寄存器的值不相同，在建立链表的同时对标签tag域进行初始化为0，并计算每条指令中寄存器的个数num。

第二步，链表扫描器扫描链表

顺序查找过程：链表扫描器首先判断结点的num域是否等于1，如果等于1，就意味着该条指令只有一个寄存器，也就是只有一个输入，没有输出，属于第三种指令，则建立新的链表，把该结点信息复制到该链表的第一个结点中，如果在扫描过程中第二次遇到结点num域为1的结点，则把结点信息复制到第二个结点中，依次类推；如果不为1，修改第一个结点的标签域tag等于n，并且顺序比较第一个结点的输出域与其余结点的输入域，如果链表扫描器找到一个结点的输入域与第一个结点的输出域相同，则修改该结点的标签域tag等于n，并且把该结点作为第一个结点，顺序比较该结点的输出域与其余结点的输入域，如果相同，则修改该结点的标签域tag等于n。链表扫描器继续顺序查找，一直查找到链表末尾。

链表扫描器返回到链表的头结点，从头结点开始查找，本次查找是查找结点的标签域tag是否被修改过，如果找到结点的标签域tag没有被修改过，则把该结点作为第一个结点，重复上面的顺序查找过程，但是不同的是该结点的标签要修改等于n+1；如果链表扫描器找到标签域tag被修改的结点，则保持原来的值不变，并且在本次查找中，之前标签域tag修改为n+1的结点要重新修改为n，停止本次查找；重复上面的顺序查找过程。

新链表的顺序查找过程和顺序查找第一个链表num域值不为1的查找过程相同。

第三步，数据流图输出模块输出数据流图

数据流图输出模块根据链表中每个结点的标签域tag值的不同，可以得到指令结点的数据流图。数据流图输出模块把具有相同tag值的结点作为一个数据流图，没有相同的则单独作为一个数据流图。

本发明中，分类模块、关系分析模块、数据流图分析模块、链表创建器、文件扫描器、链表扫描器和数据流图输出模块，均为常用的由软件实现的功能性模块。本领域技术人员通过对本申请文本的理解，结合之前已掌握的知识，可以轻易实现有关软件模块的编写，因此不再赘述。