(19)中华人民共和国国家知识产权局
(12)发明专利申请
(10)申请公布号 (43)申请公布日 (21)申请号 202010938370.5
(22)申请日 2020.09.09
(71)申请人 湖南泛联新安信息科技有限公司
地址 410000 湖南省长沙市开福区伍家岭
街道栖凤路486号凯乐微谷商务中心1
栋B座17层
(72)发明人 黄子桓 魏书宁 李立 冯元辉
(74)专利代理机构 长沙市护航专利代理事务所
(特殊普通合伙) 43220
代理人 莫晓齐
(51)Int.Cl.
G06F 30/327(2020.01)
G06F 30/331(2020.01)
(54)发明名称
方法
(57)摘要
本发明公开了一种基于RTL网表的有限状态
机识别及提取方法，包括：S1将RTL网表中存在逻
寄存器的驱动网表并判断该驱动网表是否符合
FSM状态转换逻辑，将符合FSM状态转换逻辑的驱
动网表标视为状态寄存器并提取和收集该状态
寄存器及其驱动网表；S3对被标记的状态寄存器
及其驱动网表计算驱动网表在不同输入信号下
状态寄存器的输出信号，并形成FSM状态转换图；
S4输出FSM识别及提取结果。本发明对比基于HDL
的FSM识别及提取方法更具通用性；以RTL网表作
为分析对象在一定程度上能够有效的降低分析
的时间和空间复杂度。权利要求书1页 说明书5页 附图3页CN 112036104 A 2020.12.04
C N 112036104
A
1.一种基于RTL网表的有限状态机识别及提取方法，其特征在于，包括如下步骤：
S1、获得疑似状态寄存器：遍历RTL网表中的所有寄存器并检查寄存器是否存在逻辑反馈，存在逻辑反馈的寄存器为疑似状态寄存器；
S2、提取和收集状态寄存器及其驱动网表：针对所有疑似状态寄存器，从疑似状态寄存器输入端口反向搜索并提取驱动该疑似状态寄存器的驱动网表进行分析，判断该疑似状态寄存器的驱动网表是否符合FSM状态转换逻辑，符合FSM状态转换逻辑的驱动网表所驱动的疑似状态寄存器被视为状态寄存器，提取和收集被确定的状态寄存器及其驱动网表；
S3、获得FSM状态转换图：遍历步骤S2中提取和收集的状态寄存器及其驱动网表，计算驱动网表在不同输入信号下状态寄存器的输出信号，建立驱动网表输入信号和状态寄存器输出信号的映射关系，并形成FSM状态转换图；
S4、输出FSM识别及提取结果：将步骤S2中提取和收集的状态寄存器及其驱动网表和步骤S3形成的FSM状态转换图作为FSM识别及提取结果输出。
2.如权利要求1所述的一种基于RTL网表的有限状态机识别及提取方法，其特征在于，所述步骤S1具体分解为如下步骤：
S11、RTL网表输入；
S12、遍历RTL网表中的各器件识别出所有的寄存器；
S13、遍历所有的寄存器；
S14、检查寄存器是否存在逻辑反馈；若是，则进入步骤S15；反之，则返回步骤S13；S15、存在逻辑反馈的寄存器为疑似状态寄存器。
3.如权利要求2所述的一种基于RTL网表的有限状态机识别及提取方法，其特征在于，所述步骤S2具体分解为如下步骤：
S21、遍历所有疑似状态寄存器，从疑似状态寄存器输入端口反向搜索并提取驱动该疑似状态寄存器的驱动网表进行分析；
S22、判断该疑似状态寄存器的驱动网表是否符合FSM状态转换逻辑，若是，则进入步骤S23，反之，则返回步骤S21；
S23、该疑似状态寄存器为状态寄存器；
S24、提取和收集状态寄存器及其驱动网表。
4.如权利要求3所述的一种基于RTL网表的有限状态机识别及提取方法，其特征在于，所述S2步骤中，判断疑似状态寄存器的驱动网表是否符合FSM状态转换逻辑的具体过程是：首先，疑似状态寄存器的驱动网表中仅包含组合逻辑器件；其次，疑似状态寄存器的驱动网表的输入信号须包含该疑似状态寄存器的输出信号，再次，在疑似状态寄存器的驱动网表的输入信号包含常量输入信号及非常量输入信号时，疑似状态寄存器的输出信号和非常量输入信号只能作为组合逻辑器件的控制信号或组合逻辑器件的地址信号或疑似状态寄存器的复位信号或疑似状态寄存器的置位信号。
权 利 要 求 书1/1页CN 112036104 A
一种基于RTL网表的有限状态机识别及提取方法
技术领域
[0001]本发明属于集成电路的技术领域，具体涉及一种基于RTL网表的有限状态机识别及提取方法。
背景技术
[0002]在基于FPGA(Field Programable Gate Arrays，现场可编程逻辑阵列)的硬件设计领域中FSM(Finite State Machine，有限状态机)技术具有及其广泛的应用。一方面随着FPGA集成度的不断提升使得基于FPGA的硬件设计逻辑愈来愈复杂，采用人工审查的方式对设计中的FSM进行检查及优化已近十分困难；另一方面针对FSM的识别、提取、分析和优化也已经成为了自动化、智能化的FPGA(Field Programmable Gate Array，现场可编辑逻辑门阵列)开发工具的必不可少的主要功能之一。如何能够高效的对基于FPGA的硬件设计中识别和提取其中FSM逻辑具有较高的实用价值。
[0003]目前，现有的FSM识别和提取方法存在如下缺陷：
[0004]基于HDL(Hardware Description Language，硬件描述语言)的FSM识别和提取技术，这种技术是通过在HDL代码中采用文本匹配的方式搜索符合预设FSM代码模式的HDL代码片段以实现对FSM的识别和提取的，主要的缺点在于其只能够识别符合预设FSM编码风格的HDL代码片段，漏查率较高。此外针对不同的HDL语言都需要构建不同的预设FSM编码模式，通用性受限。
[0005]基于门级网表的FSM识别技术，这类技术通过将HDL转换成统一的RTL(Register Transfer Level，寄存器转换级电路)网表描述并在生成的RTL网表描述中依据一定的判别条件去查电路中的FSM电路结构，这类算法主要存在的问题在于与门级网表的节点数量一般都会多于等价的RTL网表的
节点数量，在门级描述中进行遍历和搜索的时间复杂度和空间复杂度都显著高于RTL网表上进行同等分析的复杂度。
发明内容
[0006]为解决上述技术问题中的至少之一，本发明提出一种基于RTL网表的有限状态机识别及提取方法。
[0007]本发明的目的通过以下技术方案实现：
[0008]本发明提供了一种基于RTL网表的有限状态机识别及提取方法，包括如下步骤：[0009]S1、获得疑似状态寄存器：遍历RTL网表中的所有寄存器并检查寄存器是否存在逻辑反馈，存在逻辑反馈的寄存器被视为疑似状态寄存器；
[0010]S2、提取和收集状态寄存器及其驱动网表：针对所有疑似状态寄存器，从疑似状态寄存器输入端口反向搜索并提取驱动该疑似状态寄存器的驱动网表进行分析，判断该疑似状态寄存器的驱动网表是否符合FSM状态转换逻辑，符合FSM状态转换逻辑的驱动网表所驱动的疑似状态寄存器被视为状态寄存器，提取和收集被确定的状态寄存器及其驱动网表；[0011]S3、获得FSM状态转换图：遍历步骤S2中提取和收集的状态寄存器及其驱动网表，
计算驱动网表在不同输入信号下状态寄存器的输出信号，建立驱动网表输入信号和状态寄存器输出信号的映射关系，并形成FSM状态转换图；
[0012]S4、输出FSM识别及提取结果：将步骤S2中提取和收集的状态寄存器及其驱动网表和步骤S3形成的FSM状态转换图作为FSM识别及提取结果输出。
[0013]作为进一步的改进，所述步骤S1具体分解为如下步骤：
[0014]S11、RTL网表输入；
[0015]S12、遍历RTL网表中的各器件识别出所有的寄存器；
[0016]S13、遍历所有的寄存器；
[0017]S14、检查寄存器是否存在逻辑反馈；若是，则进入步骤S15；反之，则返回步骤S13；[0018]S15、存在逻辑反馈的寄存器为疑似状态寄存器。
[0019]作为进一步的改进，所述步骤S2具体分解为如下步骤：
[0020]S21、针对所有疑似状态寄存器，从疑似状态寄存器输入端口反向搜索并提取驱动该疑似状态寄存器的驱动网表进行分析；
[0021]S22、判断该疑似状态寄存器的驱动网表是否符合FSM状态转换逻辑，若是，则进入步骤S23，反之，则返回步骤S21；
[0022]S23、该疑似状态寄存器为状态寄存器；
[0023]S24、提取和收集状态寄存器及其驱动网表。
[0024]作为进一步的改进，所述判断疑似状态寄存器驱动网表是否符合FSM状态转换逻辑的具体过程是，首先，疑似状态寄存器的驱动网表中仅包含组合逻辑器件，其次，疑似状态寄存器的驱动网表的输入信号须包含该疑似状态寄存器的输出信号，再次，在疑似状态寄存器的驱动网表的输入信号包含常量输入信号以及非常量输入信号时，疑似状态寄存器的输出信号和非常量输入信号只能作为组合逻辑器件的控制信号或组合逻辑器件的地址信号或疑似状态寄存器的复位信号或疑似状态寄存器的置位信号。
[0025]本发明提供的一种基于RTL网表的有限状态机识别及提取方法，包括步骤：S1、获得疑似状态寄存器：遍历RTL网表中的所有寄存器并检查寄存器是否存在逻辑反馈，存在逻辑反馈的寄存器被视为疑似状态寄存器；S2、提取和收集状态寄存器及其驱动网表：针对所有疑似状态寄存器，从疑似状态寄存器输入端口反向搜索并提取驱动该疑似状态寄存器的驱动网表进行分析，判断该疑似状态寄存器驱动网表是否符合FSM状态转换逻辑，符合FSM 状态转换逻辑的驱动网表所驱动的疑似状态寄存器
被视为状态寄存器，提取和收集被确定的状态寄存器及其驱动网表；S3、获得FSM状态转换图：遍历步骤S2中提取和收集的状态寄存器及其驱动网表，计算驱动网表在不同输入信号下状态寄存器的输出信号，建立驱动网表输入信号和状态寄存器输出信号的映射关系，并形成FSM状态转换图；S4、输出FSM识别及提取结果：将步骤S2中提取和收集的状态寄存器及其驱动网表和步骤S3形成的FSM状态转换图作为FSM识别及提取结果输出。本发明采用了上述方法，由于RTL网表作为HDL的一种中间表示形式具有语言无关的特性，即主流的HDL编写的代码都可以转换为同类的RTL网表，使本发明采用的方法对比于基于HDL的FSM识别及提取方法更具通用性；另一方由于网表作为一种有向图结构，使得网表遍历和搜索的时间和空间复杂度会与网表节点以及边的数量呈现指数关系，本发明以节点及边数通常少于等价门级网表的RTL网表作为分析对象在一定程度上能够有效的降低分析的时间和空间复杂度。
附图说明
[0026]利用附图对本发明作进一步说明，但附图中的实施例不构成对本发明的任何限制，对于本领域的普通技术人员，在不付出创造性劳动的前提下，还可以根据以下附图获得其它的附图。
[0027]图1为本发明的流程图。
[0028]图2为本发明获得疑似状态寄存器的流程图。
[0029]图3为本发明提取和收集状态寄存器及其驱动网表的流程图。
[0030]图4为本发明获得FSM状态转换图的流程图。
[0031]图5为本发明实施例中FSM的RTL网表示意图。
具体实施方式
[0032]为了使本领域的技术人员更好地理解本发明的技术方案，下面结合附图和具体实施例对本发明作进一步详细的描述，需要说明的是，在不冲突的情况下，本申请的实施例及实施例中的特征可以相互组合。
[0033]结合图1所示，本发明实施例提供一种基于RTL网表的有限状态机识别及提取方法，包括如下步骤：
[0034]S1、获得疑似状态寄存器。本发明以集成电路对应的RTL网表作为输入，如图2所示，遍历RTL网表中的各器件，识别出所有的寄存器，再对所有的寄存器进行遍历，检查寄存器是否存在逻辑反馈，将存在逻辑反馈的所有寄存器作为疑似状态寄存器，否则，再检查其它寄存器是否存在逻辑反馈，直到RTL网表中所有的寄存器检查完成。寄存器指的是构成数字逻辑电路的基本单元，寄存器受到时钟沿信号的控制且能够存储二进制数据。在RTL网表抽象中，寄存器可以由D触发器或SR触发器
来实现。寄存器是否存在逻辑反馈，是指寄存器的输出只能直接或间接通过组合逻辑器件(非时序器件)与该寄存器的输入端口相连接，而组合逻辑器件指的是一类输出端口仅仅与器件当前输入端口相关的数字逻辑器件。本实施例中，如图5所示，为FSM的RTL网表，其中，Data_in是FSM的输入信号引脚，Data_out是FSM的输出信号引脚，clk是FSM的时钟信号引脚、rst是FSM的复位信号引脚，RTL_Mux_1和RTL_ Mux_2是多路选择器,RTL_Rom_0至RTL_Rom_7是只读存储器，RTL_Reg是寄存器，Logic Block是逻辑块，1和3分别是线网的位宽。先对RTL网表中的各器件进行遍历，识别出RTL网表中的寄存器RTL_reg，检查寄存器是否存在逻辑反馈，本实施例以RTL_reg寄存器的输出端口Q作为遍历的起始，采用深度优先遍历(Depth First Search，DFS)的方法检查寻满足条件的路径，深度优先遍历是一个针对图和树的遍历算法，是从起点开始对RTL网表中一个分支路径的各节点搜索深入到不能再深入为止，然后回溯路径，又从起点开始对RTL网表中另一个分支路径的各节点搜索深入到不能再深入为止，直到所有节点被搜索且每个节点只访问一次。深度优先遍历搜索的条件为寄存器输出端口与该寄存器输入端口之间存在逻辑反馈，经过遍历可以得到反馈路径：
[0035]Q(RTL_Reg)->C(RTL_Mux_2)->D(RTL_Mux_2)->D(RTL_Reg)->Q(RTL_Reg) [0036]其中，Q(RTL_Reg)是寄存器RTL_Reg的输出端口，C(RTL_Mux_2)是多路选择器RTL_ Mux_2数据选通端口，D(RTL_Mux_2)是多路选择器RTL_Mux_2的输出端口，D(RTL_Reg)是寄存器RTL_Reg的输入端口。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议