基于图神经网络的BWDSP指令选择方法优化研究

侯 璇，凤维杰，郑启龙，2

1(中国科学技术大学 计算机科学与技术学院，合肥 230026) 2(中国科学技术大学 高性能计算安徽省重点实验室，合肥 230026) E-mail：hx970922@mail.ustc.edu.cn

1 引 言

BWDSP是由中国电子科技集团第三十八研究所研制的一款数字信号处理器[1]，该处理器采用VLIW结构以及SIMD数据格式，能够在单周期内并行执行16条32位的指令.BWDSP采用了可读性强的汇编指令系统，同时BWDSP提供了一套丰富的指令集，总共有7类约600余条指令，且通过指令缓冲池技术能使指令在存储器中按照16字紧凑排列，节省存储空间，减少分支程序的开销.指令选择在编译过程中的作用是从目标处理器的指令集中选择指令用以实现与中间表示相同的功能.中间表示，Intermediate Representation，简称为IR，是一种与源代码和目标平台机器架构均无关的通用表示.常见的编译系统可将支持的高级语言编写的源代码生成与后端机器架构无关的中间表示，再通过特定平台下的机器代码转换方法将中间表示转换为相应的机器码.通常，从源代码到机器码的转换过程可划分为多个转换阶段，而主要作用对象就是IR，每个阶段对IR不断地优化，得到不同阶段优化后的IR，最终经过汇编和链接生成目标机器的可执行的机器码.指令选择也是转换过程中可拆分、可优化的一个阶段，在编译后端的代码生成中是非常重要的环节，选择出的指令的质量高低决定程序的执行代价的优劣，对后端生成的机器码有着非常重大的影响.因此，良好的指令选择策略对现阶段编译系统至关重要.目前，一些常见的编译器如GCC[2]、BURG[3]、GNU LIGHTING[4]、PCC[5]、HBURG[6]、JBURG[7]、CODESYN[8]、LLVM[9]、CBURG[10]、CHESS[11]、JHSC[12]等所采用的指令选择策略依然是采用传统的方法.如宏扩展[13]、树覆盖[14]、DAG覆盖[15]、图覆盖[16].表1为BWDSP指令集分类.

表1 BWDSP指令集分类Table 1 BWDSP instruction set classification

这些方法在现有的编译器中有着非常良好的应用，也是相对简单成熟的.但就每一种方法而言都有其不足.对于宏扩展，宏扩展策略的优点是简单直观：1)由于宏扩展策略受限于每次只能扩展单个IR语句，导致宏扩展策略所选择的指令的质量较低；2)宏扩展的可移植性较差，对新的高级语言则需重写宏；3)宏一般使用专用语言编写，因此宏难以维护和扩展.对于图覆盖策略，该策略是对宏扩展的改进与拓展，在该策略中，IR被表示为图，目标机的机器指令也同样被表示为图结构.Pozzi[17]等人提出的基于图匹配的方法在构建IR时某些公共子表达式要么必须被切分成更小的子表达式，要么被重复计算.这将导致难以选择更高效的指令.其中，大部分工作都是基于控制流图(Control Flow Graph，简称为CFG)，或者包含数据流图信息的有向无环图(Directed Acyclic Graph，简称为DAG)，局部不完整的IR上进行的，这也导致了所选择出的指令在质量和结构上并不理想.

BWDSP的指令格式如式(1)所示，表示无符号定点16位加减法同时运算指令，{Macro}指所使用的宏，H表示选择高16位，Rm_n表示双源寄存器，U表示无符号运算，该指令将Rm和Rn同时加减后，送到双源寄存器Rm_n中.

{Macro}HRm_n=HRm+/-HRn(U)

(1)

BWDSP内部有4个基本执行宏，每个宏包含15个部件，包含8个ALU、4个MUL、2个SHF、1个SPU.而指令主要由运算部件的数据运算、存储器间同运算部件之间的数据调用或传输、存储器间的数据调用或传输等组成.由式(1)也可看到，对于在同一执行行内一次执行的指令组，所选用指令的处理效率越高，其性能提升也越明显.因此指令选择的优化在后端代码优化中的影响也是非常大的.

目前，图神经网络，Graph Neural Networks[18]，简称为GNN，在处理非结构化数据上显示出越来越强大的优势.一方面，它能够理解节点与节点之间的依赖关系，另一方面，与传统的神经网络模型不同的是，GNN能够通过邻域节点的信息聚合来更新节点的隐藏状态.常应用于结构化数据的场景和非结构化场景中，其他应用场景包括基于图的NP-hard问题[19-21]等.

因此，现阶段采用最广泛的图覆盖策略为基础，同时现代编译器基于图表示的指令选择可以看作是一种图形变换[22].因此，本文提出一种基于GNN的方法，收集完整的IR信息即将CFG与DAG结合起来构成数据控制流图，Control Data Flow Graph，简称为CDFG，以建立IR图集.再通过对GNN模型的搭建与训练，用以完成基于图集的相似性搜索，找到代价相对较小的复杂机器指令图集合，最终通过模式匹配找到执行代价最小的指令，结合BWDSP的VLIW指令架构达到降低指令执行代价的目的.本文基于LLVM及BWDSP模拟器平台，具体的设计实现如下：1)建模源程序IR的CDFG；2)建模BWDSP指令集为指令图集；3)基于图集训练GNN指令选择器模型.本文的整体设计思路如图1所示.

图1 GNN实现指令选择整体设计图Fig.1 Overall design of GNN instruction selection

2 GNN的设计与实现

本文确定了基于LLVM平台和图覆盖策略来实现BWDSP的指令选择.1)通过分析LLVM处理指令选择的过程，验证图神经网络处理指令选择的可行性.2)通过制定语义映射规则将CFG和DAG静态连接成CDFG，并给出构造CDFG的动态链接库工具，建立程序和指令图集；3)对比分析BWDSP指令集和LLVM虚拟指令集的特性、BWDSP所提供的IR格式和LLVM所提供的IR格式，确定了常见的数据处理对应的IR及其对应的指令规模.最后验证了GNN在处理IR所表示的图结构中的可行性和有效性.

本文首先分析LLVM处理指令选择的过程.源代码经过LLVM前端clang编译器后生成平台无关的中间表示IR，再通过Lowering pass，将IR构造为平台有关的SelectionDAG.Lowering Pass是一种LLVM趟，趟的作用是对IR进行一次遍历和操作，完成系统架构或用户所指定的转换、分析或优化等功能，如Dce Pass是将IR中一些无用的死代码消除的趟.SelectionDAG，即是表示源程序所有信息的图结构，由两类SDNode组成.SDNode，即为SelectionDAG的节点.每个SDNode包含一条指令的操作码和数据.根据不同的类型，每个SDNode又可包含3或4个子块.拥有3个子块的SDNode代表数据节点，3个子块从上至下分别表示节点类型枚举，节点编号和节点的数据类型；拥有4个子块的SDNode表示为操作节点，从上至下分别表示操作符接受的输入操作数的序号，节点类型枚举，节点编号和节点的数据类型.

此时构造出来的SelectionDAG是针对特定平台下的源代码的图表示.但lowering Pass所创建的SelectionDAG并不一定全部被目标架构支持.所以，还需要对SelectionDAG多次进行合法化优化和合并优化.合法化是对数据类型和操作两个方面进行优化，如对于不支持sdiv指令的X86架构，合法化优化Pass则会将sdiv节点的操作码转换为X86架构支持的sdivrem指令；如目标平台指令集下只支持64位数据类型，而SelectionDAG中数据类型只包括32位，合法化优化Pass则会将SelectionDAG中的不合法的数据类型转换为目标平台支持的节点数据类型.合并优化则是为了合并或消除SelectionDAG中冗余的节点，目的是为指令选择能够生成更优的指令提供更好的DAG.此时经过这3种Pass的多次优化之后得到最终的SelectionDAG，对于包含add和sub指令的优化后的SelectionDAG如图2所示.

图2 包含add 和 sub指令的SelectionDAGFig.2 SelectionDAG with add and sub instructions

指令选择是基于最终的SelectionDAG生成针对目标平台指令的机器指令节点的过程.在LLVM中，指令语义是以树模式的方式描述，并通过tableGen工具将目标平台的指令集描述存储在对应的.td文件中.选择的过程是通过调用SelectionCodeCommon()函数，首先接收SDNode判断节点的属性，判断节点的类型来决定是否选择机器指令，再加载匹配表对应的.td文件进行匹配，此时生成即是针对特定平台的MachineDAG.

综上，LLVM的指令选择是基于优化后的SelectionDAG与目标指令集下的语义模式匹配完成.所以，可以将SelectionDAG作为切入点，首先通过IR构造包含程序全局信息的CDFG，再编写基于LLVM的优化趟来生成对应的SelectionDAG，并作为模型中源程序对应的CDFG数据集，最后搭建和训练GNN模型，并将选择出来的目标平台的机器指令作为真实的结果与预测的结果对比，反向传播以更新GNN模型.因此，本文主要分为以下3步来实现.

1)构造源程序的CDFG数据集.通过制定相关语义映射规则将CFG和DAG组合成CDFG，与保存源程序局部信息的DAG相比，构造出来的CDFG保存了源程序的全局结构信息.

2)由于BWDSP所使用的编译器同样是基于LLVM的Clang编译器，所以生成的中间代码格式也统一于LLVM.同时分析BWDSP指令集和LLVM虚拟指令集的特性，每条LLVM虚拟指令都对应至少一条BWDSP机器指令，保证后期匹配集合的可选性.通过前期的调研确定常见的数据处理方式对应的IR中常用的LLVM虚拟指令集中的指令，即确定源程序数据集的规模.

3)本文用一种新的方式，即将GNN模型应用到编译后端的指令选择过程，来模拟遍历SelectionDAG，从机器指令集的语义描述中匹配指令，并通过后期实验验证了本文的可行性和有效性.

2.1 建模源程序IR的CDFG

LLVM的中间代码格式是基于SSA的，BWDSP使用LLVM的前端编译器，因此其中间代码格式也是基于SSA的.SSA[23]，Static Single Assignment，静态单变量赋值，它具有类型安全性、底层操作性、灵活性，能够清楚表达绝大多数的高级语言，是运用在编译技术等领域的高效数据流分析技术.基于SSA中间表示能够保证每个被使用的变量都有唯一的定义，因此SSA能带来精确的“使用—定义”关系，故而利用“使用—定义”关系的能够完成更有效的优化.现代诸多编译系统如GCC、Open64、LLVM都提供了对SSA的支持.DAG中包含程序的数据流信息和局部数据依赖间的关系；CFG是表示一个函数块内的执行流图，图中的每一个节点是语句，边表示执行流信息.

本文基于LLVM的SSA图，设计了一种更全面同时也更简洁的IR的图表示数据控制流图的建模方法.LLVM首先会把基于SSA的IR表示为DAG，本文基于Eclipse环境下的Gecos[24]工具来生成对应程序的DAG表示.数据控制流图的基本设计思路是：1)首先将中间代码改造成SSA形式的IR，并以此为基础分别构建基于SSA的DAG和控制流图CFG.基于SSA的DAG和CFG用于捕获程序的数据流和控制流.2)扩展DAG和CFG，并将这两种图结构组合在一起得到数据控制流图CDFG，使得数据控制流图在捕获程序的数据流以及控制流的同时能够更好地保证程序的语法及语义信息的完整性和正确性.因此，本文针对BWDSP平台提出适应性方案，最终导出以下6个数据控制流图的设计规则：

Rule1.数据控制流图能够捕获程序的数据流和控制流：捕获两种信息流能够更完整的保存程序的信息.

Rule2.函数中的基本块应被表示成节点：便于捕获控制流，同时便于进行模式匹配.

Rule3.数据和控制操作应被表示成节点：用于捕获数据流和控制流.

Rule4.函数中所使用的实值应被表示成节点：实值也是数据.

Rule5.表示实值的节点只有一个入边：保证每个实值只有一个定义.

Rule6.数据控制流图应基于SSA：SSA能够保证精确地“使用-定义”关系.

函数的基本块是IR中按顺序执行的指令容器，在基本块中指令按照出现的先后顺序来执行.基于以上6个规则，本文分3步来构建数据控制流图：1)基于SSA构建源程序的DAG；2)基于LLVM自带的CFG生成工具构建CFG；3)组合DAG和CFG得到CDFG.最后本文按照以上6个规则，将两种图结构组合为CDFG.图3为LLVM生成包含add和sub指令示例程序对应的CFG.

图3 LLVM生成包含add和sub指令程序对应的CFGFig.3 CFG generated by LLVM containing add and sub instruction

2.1.1 捕获数据流

为了捕获数据流，本文基于SSA形式的IR构建SSA图.通常编译器中可以提取出SSA图，因为SSA图基于SSA形式的IR，所以该图符合R6以及R1中的部分规则.此外，本文对SSA图定义了扩展节点：

1)计算节点：该节点表示程序中的数据操作以及φ函数.该类节点的定义满足了R3的设计规则.

2)变量节点：该节点程序中的变量.该类节点的定义满足了R3的设计规则.

3)实值节点：该节点用于表示被数据操作所使用或由数据操作所产生的实值.该类节点的定义满足了R4的设计规则.

在计算节点中，φ函数用于解决SSA图只赋值一次，因而无法确定同一变量在执行先后顺序上的取值问题.在变量节点中，程序中的变量表示的是在SSA图中所使用的变量，包括函数外部的全局变量和函数内部的局部变量.SSA图和CFG共用一个返回节点，删除SSA图中的返回节点.基于上述设计的SSA图不仅能够捕获数据流，同时能够满足R3、R4、R6以及R1的部分规则.

2.1.2 捕获控制流

为了捕获IR的控制流，本文基于SSA形式的IR构建CFG，并在CFG中定义两种节点：

1)块节点：表示程序中的基本块.该类节点的定义满足了R2的设计规则；

2)控制节点：该节点表示控制流从一个块跳转到另一个块的跳转.该类节点的定义满足了R1的部分设计规则.

2.1.3 组合数据控制流图

本文简单地在SSA图和CFG之间添加有向边将这两类图组合成数据控制流图：

1)值定义边：每个实值节点与CFG的入口块节点连接一条有向边，表示实值节点的定义.

2)值引用边：变量节点和使用该变量的控制节点之间连接一条有向边，表示控制流对数据流的影响.

CFG中的边表示程序中的控制流动，同时有一些边需要为其加上标签，作为存储CDFG图信息的边矩阵的元素值.例如从判断语句的控制节点流出的边需要为其标识True和False，分别对应的值为1和0.CFG中前后相邻基本块之间对于控制流的标签的依次累加.以此，为子图集中的每个图中的边添加标签.

由于DAG中每个基本块内中指令按照先后顺序执行，所以在生成CDFG时基本块中的控制流是定向流动的，因此块内可快速指定，方便简化CDFG的生成过程.

2.2 构建BWDSP指令集为指令图集

在BWDSP处理器中总共有600多条指令，本文使用和建模源程序IR的CDFG相同的方法将指令表示成模式.与生成数据控制流图不同的是，当指令的输出不依赖于控制流时，控制流图为空，此时模式没有入口块.通常一条复杂指令能完成多条简单指令组合才能完成的复杂操作，但是一条单独的指令很难建模成图.为了便于建模，本文为每条指令添加一条或多条语义规则.因为基于BWDSP处理器的所有程序都可以用这600多条指令表示，因此本文将这600多条指令全部建模并制作成子图模式集以方便使用.

经过以上步骤，已完成将目标平台的机器指令的语义描述由原先的.td文件转换为与输入数据集所包含的源程序结构相同的图结构文件的内容.输入数据集与输出结果采用相同的结构作为统一的标准，为后期GNN模型的预测同步以实现节点从平台无关到特定平台的映射准备.

表2是本文按照提出的规则对最大值指令的扩展，增加了相应的语义规则，是可表示图结构的模式.图4对应于表2的模式，其中虚线代表数据流，黑色表示控制流.此图按照CDFG规则设计，符合指令对应CDFG的前提条件.

表2 通过添加语义规则求最大值指令的模式Table 2 Pattern of maximum instruction by adding semantic rules

图4 表2对应的模式Fig.4 Corresponding pattern of Table2

2.3 基于图集训练GNN指令选择器模型

CDFG与SelectionDAG同为基于LLVM的IR图表示，这使得模式匹配问题可以转换成子图匹配问题.而现阶段，子图匹配问题可以使用图卷积神经网络的方法来解决.常见的GNN采用邻域聚合方法，通过递归聚合和变换相邻节点的嵌入表示来计算自身节点的嵌入表示，是一种非常有效的图表示学习框架.目前许多基于GNN的变体也已经被提出，因其令人信服的性能和较高的可解释性而被应用到节点分类[25]、图分类[25]、链接预测[26]任务的领域中，且都取得了非常不错的效果.图5展示了图节点嵌入的过程.

图5 GNN中Embedding的示例Fig.5 An example of Embedding in GNN

本文所采用的GNN模型也是基于嵌入的GraphSage[27]和GIN[28]模型，针对本文特定的BWDSP的场景做了一些相应的改进.GraphSAGE，即Graph SAmple and aggreGatE，是一种能够利用顶点的属性信息高效地产生未知顶点嵌入向量的一种归纳式学习的框架，核心思想是通过学习一个对邻居顶点进行聚合表示的函数来产生目标顶点的嵌入向量表示，解决了GCN中归纳式学习的问题，能够学习节点的表示方法，因此在现有的图基础上对所添加的新的节点能够获取其表示.GIN，即Graph Isomorphism Network，图同构网络，该网络模型对Weisfeiler-Lehman测试进行了推广，从而在GNNs中鉴别能力最强.MLP可以近似拟合任意函数，因此GIN通过引入MLP，能够学习到单射函数，从而弥补GraphSAGE模型中只使用单层感知机的不足.

甲维盐全称甲氨基阿维菌素苯甲酸盐，可以增强神经质如谷氨酸和Y-氨基丁酸(GABA) 的作用，从而使大量氯离子进入神经细胞，使细胞功能丧失，扰乱神经传导，幼虫在接触后马上停止进食，发生不可逆转的麻痹，在3～4天内达到最高致死率．甲维盐是一种新型高效半合成抗生素杀虫剂，其具有超高效、低毒(制剂近无毒)、无残留和无公害等生物农药的特点，对鳞翅目昆虫的幼虫和其它许多害虫及螨类的活性极高，既有胃毒作用又兼触杀作用，在非常低的剂量(0.084～2 g/hm2)下具有很好的效果，而且在防治害虫的过程中对益虫没有伤害，有利于对害虫的综合防治[1-2]．

对于构造出来的CDFG，由于GNN能够理解图中节点与节点之间的依赖关系，对于其中的CFG中的Basic Block，则可能在到达基本块的结尾的时候预测出下一条指令为终止符指令，因此能够增大GNN预测的准确率.

本文首先将源程序和数据集的格式按照制定的标准统一，对原始数据集对应的基于IR的CDFG进行训练，以及构建模式选择器的过程，分为3个步骤描述.

1)源程序的控制流图可以由顺序结构，选择结构以及循环结构3种基本结构表示，这里根据程序的执行规则，所有结构中的单独指令都会在定长的指令周期内完成，所以可假设单独指令的执行代价相同.BWDSP中对应指令模式的数据流图中也由同样的规则，将所有指令对应的模式代价视为与其控制流图的执行代价相同.其中所有的边标签代表指令与指令之间的执行代价，本文所涉及到的图内边信息则基于控制流和数据流而表示为指令间依赖关系的强弱.

通过上述步骤之后本文所使用的CDFG存储在其对应的.dot文件，这样指令对应的.dot文件和源程序所对应的.dot文件就构成了GNN的输入数据集.因此，依据此信息将.dot文件作为输入，首先对图中每个节点进行按顺序标注，这样就能得到IR的图的拓扑表示.每一个节点都对应一种指令，如二进制位指令add、向量指令insertelement、内存访问alloca等，对这些指令添加和标注标签.本文采用one-hot编码格式为这些标签编码，以连续化程序指令的特征，因而每一个指令对应一个特有的标签向量.

因此，基于上述原理，本文可以按照统一的标准来制定源程序和BWDSP指令模式CDFG的节点标签和边标签，图6中黑色边表示控制流，虚线边表示数据流.

图6 加入语义规则之后的Max指令其拓扑结构对应的模式Fig.6 Topology of Max instruction after adding semantic rules

2)获取CDFG的Laplacian矩阵.对应一个图G={V，E}，本文采用正则化的Laplacian矩阵，如式(2)所示：

Lsys=D-1/2LD-1/2

(2)

其中D为图中顶点的度矩阵，L为组合的Laplacian矩阵.不同的CDFG的规模是不同的，且CDFG是有向图，所以本文重定义了图的邻接关系，对转换之后的Laplacian矩阵重新计算大小，将边的信息添加至Laplacian矩阵当中.设拓扑图中节点的数量为M，则矩阵的规模为M×M.设图的边数为T，图中节点最大的度为Dmax，则边权值矩阵大小为T×Dmax.

本文所采用的模型的学习过程主要有以下4个步骤：

a)对节点的局部k跳邻域进行固定大小的随机采样.

b)通过聚合中心节点的邻居特征信息来获得中心节点的临界状态.

c)将临界状态线性转换为最终状态.

d)最后使用中心节点的最终状态，进行预测并反向传播错误.

其中，对于第1步中节点的k跳邻域，k的取值一般在{1，2}之间，本文中根据IR指令控制流动和数据流动的特征分析，聚合节点的一阶和二阶的邻居信息即可满足对于邻居节点信息的要求.在第2步中的中心节点表示在当前聚合过程中图中的任一节点，从该节点出发聚合与其相邻的一阶和二阶邻居节点作为该节点的最终聚合信息.当前中心节点完成聚合邻居节点信息的操作后得到的嵌入向量表示即为当前节点的临界状态.将邻居节点聚合的特征和经过线性变换的当前中心节点的特征进行求和或级联，通过非线性激活函数的转换，得到更新后的特征即当前节点聚合后的最终状态.

按照上述步骤完成模型的训练过程.对任何一个输入指令的IR的CDFG可以输出其对应的匹配模式标签.根据之前对边的标签和节点标签的处理特性，并结合GIN结构的特点，本文使用sum聚合算子来学习全部的标签以及数量，以获得精确的结构信息.本文所使用的图神经网络伪代码如表3所示.

表3 图神经网络伪代码Table 3 Pseudocode of graph neural network

通过引入聚合函数的概念来定义图的卷积.聚合函数实质上是聚合节点的邻域信息.它必须对节点顺序的排列具有不变性，因此也保证了指令的执行顺序的不变性.其中sum聚合算子的定义如式(3)所示：

aggsum=σ(SUM{W·hj+b，∀vj∈N(vi)})

(3)

其中W和b，是聚合操作中学习的参数.Sum算子用于将邻居聚合的特征与当前节点特征合并，以更新当前节点特征.图7为节点和图的更新过程.

图7 节点和图的更新过程Fig.7 Graph node and graph update process

训练的过程即实现指令选择的过程，本文训练出来模型作为指令选择器.本文所使用的指令选择模型是基于GIN和GraphSAGE两个神经网络模型，因此简称为GINSA.GINSA能够预测出源程序对应的CDFG中相应节点的标签，将模型预测的指令标签整合成可使用BWDSP确定的指令超集，该超集是指令选择中第2步模式匹配所选用指令的完备集，是对覆盖指令集合的约束.通过元启发式算法进行模式匹配可选择出有效的机器指令.

3 实验及评估

3.1 时空复杂度分析

假设源程序的数目为m，LLVM虚拟指令数为n，BWDSP指令数目为l，每个源程序可产生若干条虚拟指令语句，设其数目为s，在加载源程序为其中间代码编码的过程的时间复杂度为O(m·s).另外，由于GINSA是基于GCN模型，前向传播的重点在于聚合邻居节点的信息，所以模型整体的主要时间复杂度和空间复杂度分别为式(4)和式(5)：

(4)

(5)

D为模型的层数，l为层数索引，M为需要聚合的邻接节点的特征，对于单层卷积层来说M的维度如式(6)所示：

Ml=Nsrc×Nneighbor×Din

(6)

其中，Nsrc为源节点的数量，Nneighbor为邻居节点的数量，Din为输入的特征维度，K为卷积核的边长，对于输入为矩阵的神经网络模型，输入输出的通道数只有一层，故而简化.

3.2 实 验

3.2.1 实验过程

本文所使用的实验平台是基于Ubuntu18.04上的BWDSP 1042模拟器，LLVM8.0 Release版本作为数据集构建的环境架构以及Nvidia GeForce RTX 2060显卡用于模型的训练加速，实验以准确率为评判标准.

3.2.2 GINSA基本测试实验

本文首先在LLVM虚拟指令集上实验，完成对每条平台无关指令的编码.基于MUTAG、PTC、CDFG这3个数据集，使用GCN、GIN、GraphSAGE作为基准网络模型，最后将GINSA模型同样应用于3个数据集，准确率实验结果如表4所示.

表4 对比实验结果Table 4 Comparison of experimental results

MUTAG是关于化合物的数据集，原子代表结点，化学键代表边，因此每个化合物可看为一张图，其中包含两类共188张图，每个图都对应一个标签，代表类别.PTC也是关于化合物的数据集，包含4个类别共344张图，同样，每个图都有一个标签表示类别.CDFG为本文收集的C源程序对应的优化后的IR数据集，语句代表节点，数据控制流表示边，其中常用的LLVM虚拟指令集共包含108条指令，因而有108个类别共3000张图.从表4中可知，在MUTAG和PTC两个数据上使用GINSA模型得到的准确率与基准图神经网络模型相差无几，且在CDFG数据集能够实现识别出指令的功能，最高能达到79.8%的准确率.一方面验证了基于改进的图神经网络GINSA在一般性的图数据集上的可行性和可靠性，另一方面也验证了图神经网络在处理指令选择过程理论上的有效性.将模型对于源程序CDFG中节点的标签标注收集起来作为指令选择模式匹配任务中的超集.其对比结果如表5所示.

表5 指令选择器指令超集和实际指令集对比Table 5 Instruction selector instruction superset versus actual instruction set

表5的结果是保证常见的指令至少出现一次的前提下，在同一个C源程序上得到由GINSA得出的指令和LLVM实际选用指令的类别内数目的对比.可以看出，GINSA指令选择器所选择出来的指令超集和它实际所使用的指令之间的差距在所选用的指令类别上保持一致，其中仅仅在数据传输指令类别上有些许的不同，且实际选用的指令集是GINSA所选择指令集的子集，说明指令选择器具有完备性.另外，本文通过和LLVM后端中保存指令相关信息的.td文件对比得到的初步结论是：在编译后端代码生成的指令选择过程中运用图神经网络模型，在一定的情况下能够识别和预测出正确的指令类别集合，并且能够选择出包含BWDSP指令集中特有复杂指令候选集合来完成多个单指令实现的目标.虽然模型的运算量较大，但后期进行优化之后可作为单独可附加的模块进行移植.

3.2.3 GINSA在指令子数据集上的实验

本文基于平台无关的LLVM虚拟指令集，按照指令出现的频率选择最常见的虚拟指令作为指令子数据集，并以此整理数据集来评测GINSA的性能.

在大多数的简单C程序中，从得到的中间代码中可以观察到，LLVM中的大多数复杂指令并没有被用到.所以，在编码的过程中为了降低程序所占内存的大小和提高程序执行速度，我们设计了这样的实验，对比在LLVM整体和局部指令集下GINSA的识别具体指令的准确率.数据传输指令是数据存取的必要指令，几乎每个程序都会涉及到其中几种，如“store”“load”；在ALU指令中，常见的有“add”“sub”“and”“or”“xor”等；MUL指令中，有“mul”等.在该实验中，本文摘取了其中的一部分作为数据集.图8中虚线和实线分别表示训练的准确率和测试的准确率在使用数据集中的全部样本对模型进行的一次完整训练的变化过程，横坐标是完整训练次数增长的方向.可以看出，随着训练次数的增加，每条曲线所代表的准确率都在不断上升，每条曲线所代表的准确率都在不断上升，最终能够稳定在96%上下，表明在该子指令集下GINSA能够识别出有效的指令超集.本文检取其中出现频率最高的几种指令，相比在LLVM整体虚拟指令集上的实验，明显提高了GINSA模型最终得到的准确率，表明了GINSA模型的可靠性.

图8 GINSA在LLVM子数据集上的性能Fig.8 Performance on LLVM subset by GINSA

4 总 结

本文基于改进的GNN模型，设计实验和验证了改进的指令选择模型在编译后端代码生成的指令选择步骤中的可行性、可靠性和有效性.本文首先验证GNN在处理指令选择场景上应用的可行性，再提出构造CDFG的规则，基于LLVM平台和BWDSP1042模拟器，将指令集中的指令和程序建模成CDFG.然后在GraphSAGE和GIN两种GNN模型上改进，以训练出指令选择器，最后基于GNN训练的结果为源代码选择出可靠的BWDSP复杂指令，完成了指令选择的初始目的.

本文通过实验验证了GNN通用框架在处理图类型的非结构化数据上的高适用性.在BWDSP指令集和X86架构上实验，验证了指令选择模型所选择出指令集合的可用性，并分析了GNN模型的优势和特性.在未来的工作中，可通过优化GNN模型的结构来提升指令选择的正确性，也可通过将GNN模型简化并封装成BWDSP内部可调用模块的方式来实现其可集成性.