Research On Instruction Selection Based On Graph Neural Network

At present,most chips at home and abroad still use traditional algorithms based on macro expansion or graph coverage in the process of compiling back-end processing instructions for consideration of factors such as stability,reliability,and availability.Due to factors such as the continuous improvement of chip computing performance and the expansion of the instruction set,these instruction selection strategies cannot be iteratively updated automatically,and cannot make full use of the advantages of the high-efficiency instructions of the platform instruction set,and cannot adapt to such changes well.In essence,instruction selection can be divided into two processes,namely,pattern matching and pattern selection.For the pattern matching problem,this article uses the graph neural network model that has been popular in recent years to solve it.With the help of the graph neural network model to run on non-European data such as graphs,the matching function between graphs is realized,and a candidate instruction set is given.As a matching set.Then for the mode selection problem,this article uses meta-heuristic algorithm to deal with.Since there is more than one feasible instruction combination,the meta-heuristic algorithm can be used as input for the same matching set,and the output obtained may have different characteristics and output different instruction combinations.Based on the program of the BWDSP platform and its instruction set,this paper verifies the actual application performance of these two methods in the back-end compiler field through experiments,and proves this instruction selection through a comparative experiment with the traditional instruction selection strategy.The efficiency of the strategy can not only reduce the cost of program execution,make full use of the efficiency of the special and complex instructions in the BWDSP instruction set,but also apply this strategy to the instruction selection of other machine platforms,or compile other backends.The sub-process is the target,which improves the scalability and portability of this instruction selection strategy.The main work of this paper is as follows:.(1)Carry on instruction modeling to the instruction set of BWDSP chip.Each BWDSP instruction can be expressed as a graph structure after adding semantic rules.This structure must have the same attributes as the graph structure of the BWDSP program.Therefore,a set of semantic rules and standards must be used for BWDSP program and instruction set graph structure modeling.Based on the semantic rule standard proposed in this paper,a tool for automatically generating graph structure is designed.(2)CDFG modeling of BWDSP program.The control flow and data flow in the BWDSP source program are linked into a whole according to the dependency relationship,that is,the data control flow,and the CDFG(Control Data Flow Graph)can be obtained.The source program is classified and expanded,and the CDFG instruction graph set corresponding to different instruction types is obtained,which is used as the data set of the graph neural network.(3)Design and improve the graph neural network model structure to obtain a set of candidate instructions.This paper improves the classic inductive learning graph neural network GraphSAGE and the graph isomorphic network model GIN,and proposes a new graph neural network model-GINSA,which is applied to the pattern matching of the instruction selection process.This model is modeled for BWDSP.The model proposed by the latter program CDFG and instruction atlas sets the instructions given by the model as candidate instructions,and compares them with the instructions used in the actual program,and verifies the efficiency of the instructions selected by the model through the execution efficiency.(4)Using meta-heuristic algorithm,select the best instruction combination from the candidate instruction set as the final instruction combination.The meta-heuristic algorithm can solve the mode selection problem,which is essentially a combinatorial optimization problem.The candidate instruction set selected by the graph neural network is used as the matching set,and the meta-heuristic algorithm is used as the selector.The final result is a feasible selection from the matching set.The command combination is the final command combination.Through the above work,this article uses the BWDSP 1042 simulator based on LINUX system,The LLVM8.0 Release version is used as the environment architecture constructed by the data set and the Nvidia GeForce RTX 2060 graphics card is used for the training of the graph neural network model and the search acceleration of the meta-heuristic algorithm.The experiment is between the final instruction combination and the instructions used by the source program The performance comparison is used as the criterion to verify the advantages of the instruction selection strategy in this paper.