CN-122019142-A - Register allocation method, computing device, storage medium and computer program product

CN122019142ACN 122019142 ACN122019142 ACN 122019142ACN-122019142-A

Abstract

The embodiment of the specification provides a register allocation method, because when the weight is set for the edge in the target network, the weight is positively correlated with the distance from the edge to the key point, and the weight between nodes and the distance between the target position and the key point are simultaneously activated through the explicit constraint of the energy function in iterative optimization, the target network can automatically arrange an overflow or reload instruction at a code position closer to the key operation when the iteration converges, after the lifetime is segmented, the byreg interval is as short as possible, so that a physical register can be used by more variables, and the pressure and the overflow instruction of the physical register are reduced. In general, the register allocation method ensures that the finally determined target position can not only relieve the conflict of physical registers, but also effectively reduce the occupation time of invalid registers caused by the fact that the instruction insertion point is far away from the key point, thereby reducing the memory access overhead on the whole and improving the utilization rate and the execution performance of the registers.

Inventors

LU SHIWEI
ZHANG ZHANJUN
WU YUAN
LI GEN
TANG YUXING

Assignees

飞腾信息技术有限公司

Dates

Publication Date: 20260512
Application Date: 20251230

Claims (13)

1. A register allocation method, comprising: When a physical register is allocated for the lifetime to be allocated, if no physical register which can be allocated exists, determining a target lifetime in the lifetime of the allocated physical register, wherein the lifetime corresponds to a virtual register and is used for representing the active interval of the virtual register; The target network comprises a plurality of nodes and a plurality of edges connected with the nodes, wherein the nodes represent edge bundles, the edges represent basic blocks, the weight of the edges are positively correlated with the distance from the edges to key points, and the key points are the positions of definition instructions or use instructions of virtual registers corresponding to the target lifetime; The method comprises the steps of iterating the target network to determine a target position enabling an energy function to be minimum in the target network, wherein the target position is a position for inserting a target instruction, the target instruction is an overflow instruction or a reload instruction, the value of the energy function is positively correlated with a first target parameter, the first target parameter comprises at least one of a weight between two nodes activated simultaneously and a distance between the target position and the key point, and the state representation of the activated node occupies the physical register.
2. The method of claim 1, wherein the state of the node characterizes an occupancy state of a physical register in an area corresponding to an edge beam characterized by the node, the target location includes an overflow location and a reload location, and the target location is a boundary edge of nodes with different node states; After the iteration is performed on the target network, the method further comprises: A state update procedure is performed to correct the overflow position in the direction of the defined instruction and/or to correct the reload position in the direction of the use instruction.
3. The method of claim 2, wherein the status update procedure comprises: Traversing the node from the overflow position along a first direction, traversing the node from the reload position along a second direction, and updating the state of the node from a first state to a second state when the node meets a preset condition, wherein the first state ensures that the physical register is occupied, and the second state characterizes the physical register to be idle; The preset conditions comprise a first condition and a second condition, wherein the first condition comprises that an edge beam represented by the node which is currently traversed is connected with a first basic block, the state of a downstream node is the second state, the first basic block is a basic block related to the definition instruction or the use instruction, and the downstream node is a node which is adjacent to the node which is currently traversed and is positioned in the second direction; The second condition comprises that a basic block of the edge beam connection represented by the node currently traversed is a second basic block, and the second basic block is a basic block with a single inlet or a single outlet; And correcting each target position according to the updated node state.
4. The method as recited in claim 2, further comprising: Calculating an overhead score corresponding to each target position according to each corrected target position, wherein the overhead score is positively correlated with the computing resource overhead caused by inserting the target instruction into each target position; And determining the optimal target position according to the overhead scores corresponding to the target positions.
5. The method according to claim 4, wherein the overhead score is positively correlated with a second target parameter, the second target parameter comprising a first parameter and/or a second parameter, the first parameter comprising an expected execution frequency of a basic block in which the target location is located, the second parameter comprising a distance between a basic block location in which the target location is located and a defined instruction, and a distance between the target location and a last of the usage instructions.
6. The method according to any one of claims 1 to 5, wherein the weight of the edge is further positively correlated with the expected execution frequency of the basic block represented by the edge, and/or the weight of the edge is further negatively correlated with a maximum of a first frequency and a second frequency, the first frequency being the expected execution frequency of the basic block where the defined instruction of the virtual register corresponding to the target lifetime is located, and the second frequency being the expected execution frequency of the basic block where all the used instructions of the virtual register corresponding to the target lifetime are located.
7. The method according to any one of claims 1-5, wherein iterating the target network comprises: Assigning an initial state value for a node in the target network, wherein the initial state value of the node is determined based on the topological position of the edge beam represented by the node in a control flow graph, and the initial state value is randomly generated in a preset probability distribution range; And carrying out iterative updating on the state value of each node based on an activation function, and calculating the energy function in each iterative process until the energy function converges, wherein the activation function is used for determining a new state value of the node based on the input sum of the nodes, and the input sum is an intermediate value for determining the state updating direction of the nodes.
8. The method of claim 7, wherein the activation function specifically includes a penalty term, a distance term, and a bias term, wherein, in the penalty term, for any two adjacent nodes in an active state at the same time, the higher the weight of the connection edge, the greater the contribution value to the energy function; in the distance item, for the node in the activated state, the larger the distance from the corresponding side beam to the key point is, the larger the contribution value of the node to the energy function is; the bias term is positively correlated with the extent of the lifetime.
9. The method of claim 7, wherein iteratively updating the state values of the nodes based on the activation function, the energy function being calculated during each iteration until the energy function converges comprises: Calculating the input sum of a current node, wherein the input sum is the difference value between the accumulated value of the input values of all neighbor nodes and the bias term of the current node, the current node is the node of the current iteration, and the bias term of the current node is positively related to the length of the lifetime; Determining a new state value of the current node based on the activation function according to the input sum of the current node; Calculating a difference value between a new state value of the current node and a state value in the previous iteration process, and updating the state value of the current node into the new state value when the difference value is larger than a first threshold value; when the difference value is smaller than or equal to the first threshold value and the first accumulated time is smaller than the second threshold value, the state value of the current node is not updated, and the first accumulated time is the time that the difference value is smaller than or equal to the first threshold value in the iterative process of the current node; Updating the state value of the current node to a new state value when the difference value is less than or equal to the first threshold value and the first accumulated number of times is greater than or equal to the second threshold value; After one round of iteration process is completed, calculating the current energy function of the target network, if the second accumulated times are larger than or equal to a third threshold value, determining that the energy function converges, and terminating the iteration process, wherein the second accumulated times are continuous times of which the energy fluctuation is smaller than a fluctuation threshold value, and the energy fluctuation is the difference value between the energy function calculated after the current round of iteration process and the energy function calculated after the previous round of iteration process.
10. The method according to any one of claims 1 to 5, wherein when allocating the physical registers for the lifetime to be allocated, if there are no physical registers that can be allocated, determining the target lifetime in the lifetime of the allocated physical registers includes: When physical registers are allocated for the to-be-allocated lifetime, if all physical registers are allocated for other lifetimes which conflict with the to-be-allocated lifetime, no allocatable physical registers are determined to exist; and determining the life cycle with the lowest overflow weight as the target life cycle in the life cycles of the allocated physical registers, wherein the overflow weight is positively correlated with the use frequency of the virtual register corresponding to the life cycle.
11. A computing device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, the processor implementing the register allocation method of any one of claims 1 to 10 when executing the computer program.
12. A computer readable storage medium, wherein a computer program is stored on the computer readable storage medium, and the computer program when executed by a processor implements the register allocation method according to any one of claims 1 to 10.
13. A computer program product, characterized in that the computer program product comprises a computer program which, when being executed by a processor, implements the register allocation method according to any one of claims 1 to 10.

Description

Register allocation method, computing device, storage medium and computer program product Technical Field The present disclosure relates to the field of computer applications, and more particularly, to a method for allocating registers, a computing device, a storage medium, and a computer program product. Background The register allocation is a key optimization link of the back end of the compiler, and the core task of the register allocation is to map virtual registers (the virtual registers can be used for storing variables, so that the virtual registers correspond to the variables in the process) in the program to limited physical registers, so that memory overflow overhead caused by insufficient physical registers is minimized, and the execution efficiency is improved. When the available physical registers are insufficient, the compiler needs to temporarily store part of the variables in the memory, which is called overflow (spilling), and when the variables overflow into the memory, the program wants to use the variables to read only from the memory, thus greatly reducing the execution efficiency of the program. Therefore, in the register allocation process, planning a reasonable overflow/reload position to improve the use efficiency of the physical register is a key to improve the program operation efficiency. Disclosure of Invention Embodiments of the present disclosure provide a register allocation method, a computing device, a storage medium, and a computer program product, so as to achieve the purpose of improving the use efficiency of a physical register, thereby improving the program operation efficiency. In order to achieve the technical purpose, the embodiment of the specification provides the following technical scheme: In a first aspect, an embodiment of the present specification provides a register allocation method, including: When a physical register is allocated for the lifetime to be allocated, if no physical register which can be allocated exists, determining a target lifetime in the lifetime of the allocated physical register, wherein the lifetime corresponds to a virtual register and is used for representing the active interval of the virtual register; The target network comprises a plurality of nodes and a plurality of edges connected with the nodes, wherein the nodes represent edge bundles, the edges represent basic blocks, the weight of the edges are positively correlated with the distance from the edges to key points, and the key points are the positions of definition instructions or use instructions of virtual registers corresponding to the target lifetime; The method comprises the steps of iterating the target network to determine a target position enabling an energy function to be minimum in the target network, wherein the target position is a position for inserting a target instruction, the target instruction is an overflow instruction or a reload instruction, the value of the energy function is positively correlated with a first target parameter, the first target parameter comprises at least one of a weight between two nodes activated simultaneously and a distance between the target position and the key point, and the state representation of the activated node occupies the physical register. In a second aspect, one embodiment of the present specification also provides a computing device including a memory, a processor, and a computer program stored on the memory and executable on the processor, the processor implementing a register allocation method as described above when executing the computer program. In a third aspect, an embodiment of the present specification further provides a computer readable storage medium having stored thereon a computer program which, when executed by a processor, implements a register allocation method as described above. In a fourth aspect, embodiments of the present description provide a computer program product or a computer program, the computer program product comprising a computer program stored in a computer readable storage medium, a processor of the computer device reading the computer program from the computer readable storage medium, the processor implementing the steps of the above-mentioned register allocation method when executing the computer program. Alternatively, the computer program may be stored on a readable storage medium or a cloud of a computer device, from which the processor of the computer device reads the computer program. As can be seen from the above technical solutions, in the implementation process, when a physical register is allocated for a lifetime to be allocated, if no physical register exists, determining a target lifetime in the lifetime of the allocated physical register, constructing a target network based on an edge beam graph corresponding to the target lifetime, and iterating the target network to determine a target position in the target network where an energy function is minimized, where the target