Search

CN-121658010-B - Register allocation method, apparatus, computer program product, and readable storage medium

CN121658010BCN 121658010 BCN121658010 BCN 121658010BCN-121658010-B

Abstract

The invention discloses a register allocation method, equipment, a computer program product and a readable storage medium, which belong to the field of program compiling and are used for allocating registers for variables during program compiling, so that the problem that a large number of registers cannot be allocated in a program is solved, partial neighbor nodes of the nodes need to be overflowed to a memory if nodes with the degrees larger than the total number of the registers exist in a conflict graph, and a neighbor node area (the nodes and adjacent nodes thereof) of one node is provided with partitionability.

Inventors

  • ZHANG QING
  • ZHAN YONGZHENG
  • WANG QUN

Assignees

  • 济南迈威智能科技有限公司

Dates

Publication Date
20260508
Application Date
20260204

Claims (13)

  1. 1. A register allocation method, comprising: Constructing a conflict graph for each variable in the target program, wherein any node in the conflict graph represents one variable, and an edge between two nodes represents that the two variables need to be used simultaneously in the life cycle of the target program; Judging whether nodes with the degrees larger than the total number of registers exist in the conflict graph, wherein the degrees are the total number of adjacent nodes; If the node with the highest current degree in the conflict graph is used as a target node, and the target node and the adjacent nodes thereof are used as neighborhood node areas in the conflict graph; If not, executing the steps of carrying out register allocation on the variables in the target program according to the current conflict graph; Dividing the neighborhood node area into a plurality of node subareas and returning to the step of judging whether nodes with degrees larger than the total number of registers exist in the conflict graph, wherein the node subareas comprise the target nodes, and the degrees of the target nodes in the node subareas are smaller than the total number of registers; according to the current conflict graph, performing register allocation on variables in the target program; the dividing the neighborhood node region into a plurality of node subregions includes: determining the total number of nodes in the neighborhood node region; Determining the target number of the node subareas obtained after segmentation according to the total number of nodes and the total number of registers aiming at preset constraint conditions, wherein the preset constraint conditions comprise that all the node subareas comprise the target nodes, and the degrees of the target nodes in the node subareas are smaller than the total number of registers; Constructing equivalent nodes with the number of the target nodes reduced by one and the value of the corresponding variable of the target node being equal; Dividing all neighbor nodes of the target node into a target number of neighbor node groups, wherein the number of nodes in the neighbor node groups is less than the total number of registers minus one; And deleting the edges of each node in the neighbor node group and the target node in a conflict graph aiming at any other neighbor node group except for the neighbor node group which is uniquely designated, and establishing the edges between the equivalent nodes which are uniquely corresponding to the neighbor node group for each node in the neighbor node group.
  2. 2. The method for allocating registers according to claim 1, wherein determining the target number of the partitioned node sub-areas according to the total number of nodes and the total number of registers for the preset constraint condition comprises: Subtracting one from the total number of nodes to obtain the total number of neighbor nodes of the target node; Subtracting one from the total number of registers to obtain a first value; judging whether a remainder exists after dividing the total number of the neighbor nodes by the first numerical value; if the node sub-area is not found, dividing the total number of the neighbor nodes by the quotient of the first value to obtain the target number of the node sub-areas after the dividing; If the node sub-area is present, dividing the total number of the neighbor nodes by the quotient of the first value and one, and taking the quotient as the target number of the node sub-areas obtained after the division.
  3. 3. The register allocation method according to claim 1, wherein said allocating registers to variables in the target program according to the current conflict graph comprises: Judging whether nodes with degrees larger than the total number of registers exist in the current conflict graph or not; If the conflict graph does not exist, distributing registers to any unallocated node in the conflict graph in a one-to-one correspondence manner; if the node with the largest degree in the conflict graph exists, the node is used as a node to be processed; distributing the registers to nodes in a to-be-processed set in a one-to-one correspondence manner, wherein the to-be-processed set comprises to-be-processed nodes and adjacent nodes thereof; determining overflow cost of any unallocated node in a set to be processed, wherein the unallocated node is a node of an unallocated register; Overflowing the node with the minimum overflow cost in the set to be processed as a target overflow node to the memory; deleting the target overflow node and the connected edges thereof in the conflict graph, and returning to the step of judging whether nodes with degrees larger than the total number of registers exist in the current conflict graph.
  4. 4. A method of allocating registers as claimed in claim 3, wherein said determining, for any unallocated node in the set to be processed, an overflow cost for said unallocated node comprises: determining core parameter items of unallocated nodes aiming at any unallocated node in a to-be-processed set; The core parameter item comprises a use frequency, a life cycle length and a degree, wherein the use frequency is the read-write times of a variable corresponding to a node in the life cycle of a target program, and the life cycle length is the declaration cycle length of the variable corresponding to the node; and determining the overflow cost of the unassigned node through a preset cost relation based on the core parameters of the unassigned node.
  5. 5. The register allocation method according to claim 4, wherein the cost relation comprises: Cost=aP+bL+cD; The Cost is the overflow Cost of the unassigned node, a, b and c are preset coefficients, P is the use frequency of the unassigned node, L is the life cycle length of the unassigned node, and D is the degree of the unassigned node.
  6. 6. The method according to claim 4, wherein before determining the overflow cost of the unallocated node by a preset cost relation based on the core parameters of the unallocated node, the determining the overflow cost of the unallocated node for any unallocated node in the set to be processed further includes: Judging whether an overflow auxiliary switch in the system is started or not; if the node is started, determining auxiliary parameters of the unassigned node; The determining, based on the core parameters of the unassigned node, the overflow cost of the unassigned node according to the preset cost relation includes: And determining the overflow cost of the unassigned node according to a preset cost relation based on the core parameters and the auxiliary parameters of the unassigned node.
  7. 7. The register allocation method of claim 6, wherein the auxiliary parameters comprise at least one of neighbor node register allocation ratio, variable type, and semantic importance level; The distribution ratio of the neighbor node registers is the duty ratio of the nodes distributed with the registers in the neighborhood nodes.
  8. 8. The method according to any one of claims 1 to 7, wherein after constructing a conflict graph for each variable in the target program, before performing register allocation for the variable in the target program according to the current conflict graph, the method further comprises: Determining an equivalent variable pair in the target program, wherein two variables in the equivalent variable pair belong to an assignment relation; judging whether the degree of the new variable obtained by combining the equivalent variable pairs is smaller than the total number of registers or not according to the degrees of two variables in the equivalent variable pairs in the conflict graph; If the set of the equivalent variables is smaller than the set of the equivalent variables, combining the two variables in the equivalent variable pair into one variable in the conflict graph.
  9. 9. The method for allocating registers according to claim 8, wherein determining whether the degree of the new variable obtained by combining the equivalent variable pairs is smaller than the total number of registers according to the degrees of the two variables in the conflict graph comprises: Adding the degrees of two variables in the equivalent variable pair in the conflict graph to obtain the degrees of the new variable obtained by combining the equivalent variable pair; And judging whether the degree of the new variable obtained by combining the equivalent variable pairs is smaller than the total number of registers.
  10. 10. The register allocation method according to claim 8, wherein said merging two variables in said equivalent variable pair into one variable in a conflict graph comprises: deleting edges between two variables in the equivalent variable pair in the conflict graph; and combining two variables in the equivalent variable pair into one variable.
  11. 11. A register allocation apparatus, comprising: A memory for storing a computer program; processor for implementing the steps of the register allocation method according to any one of claims 1 to 10 when executing said computer program.
  12. 12. A computer program product comprising computer programs/instructions which when executed by a processor implement the steps of the register allocation method of any one of claims 1 to 10.
  13. 13. A computer readable storage medium, characterized in that the computer readable storage medium has stored thereon a computer program which, when executed by a processor, implements the steps of the register allocation method according to any of claims 1 to 10.

Description

Register allocation method, apparatus, computer program product, and readable storage medium Technical Field The present invention relates to the field of program compilation, and in particular, to a register allocation method, apparatus, computer program product, and readable storage medium. Background The register allocation is an important link of a compiler in the process of compiling a program, and refers to allocating variables in the program to registers as much as possible so as to reduce access to a memory, however, a mature register allocation method is lacked in the related art, a large number of variables cannot be allocated to the registers, and therefore the running efficiency of an executable program obtained by final compiling is poor. Therefore, how to provide a solution to the above technical problem is a problem that a person skilled in the art needs to solve at present. Disclosure of Invention The invention aims to provide a register allocation method, equipment, a computer program product and a readable storage medium, wherein the method can determine target nodes with the degree larger than the total number of registers in a conflict graph, then divide a neighborhood node area of the target nodes into a plurality of node subareas, and meet the conditions that all the node subareas comprise target nodes, and the degree of the target nodes in the node subareas is smaller than the total number of registers, so that partial neighbor nodes of the target nodes cannot be allocated to the registers and overflow to a memory, the number of variables needing to overflow to the memory in the target program is reduced, and the operation efficiency of an executable program obtained through final compiling is improved. In order to solve the above technical problems, the present invention provides a register allocation method, including: Constructing a conflict graph for each variable in the target program, wherein any node in the conflict graph represents one variable, and an edge between two nodes represents that the two variables need to be used simultaneously in the life cycle of the target program; determining target nodes with the degrees larger than the total number of registers in the conflict graph, and taking the target nodes and adjacent nodes thereof as neighborhood node areas in the conflict graph, wherein the degrees are the total number of the adjacent nodes; dividing a neighborhood node area into a plurality of node subareas, wherein the node subareas comprise the target nodes, and the degrees of the target nodes in the node subareas are smaller than the total number of registers; and according to the current conflict graph, performing register allocation on variables in the target program. On the other hand, determining the target node with the degree larger than the total number of registers in the conflict graph, and taking the target node and the adjacent nodes thereof as the neighborhood node region in the conflict graph comprises: judging whether nodes with the degrees larger than the total number of registers exist in the conflict graph or not; If the node with the highest current degree in the conflict graph is used as a target node, and the target node and the adjacent nodes thereof are used as neighborhood node areas in the conflict graph; If not, executing the steps of carrying out register allocation on the variables in the target program according to the current conflict graph; After the neighborhood node area is divided into a plurality of node subareas, the step of judging whether nodes with degrees larger than the total number of registers exist in the conflict graph is executed. In another aspect, the partitioning the neighborhood node region into a plurality of node sub-regions includes: determining the total number of nodes in the neighborhood node region; Determining the target number of the node subareas obtained after segmentation according to the total number of nodes and the total number of registers aiming at preset constraint conditions, wherein the preset constraint conditions comprise that all the node subareas comprise the target nodes, and the degrees of the target nodes in the node subareas are smaller than the total number of registers; Constructing equivalent nodes with the number of the target nodes reduced by one and the value of the corresponding variable of the target node being equal; Dividing all neighbor nodes of the target node into a target number of neighbor node groups, wherein the number of nodes in the neighbor node groups is less than the total number of registers minus one; And deleting the edges of each node in the neighbor node group and the target node in a conflict graph aiming at any other neighbor node group except for the neighbor node group which is uniquely designated, and establishing the edges between the equivalent nodes which are uniquely corresponding to the neighbor node group for each node in the neighbor node group. On th