Keywords

1 Introduction

In compiling, register allocation is an important optimization technology. The main conventional methods of register allocation can be classified into two main classes: linear scan register allocation [1] and graph-coloring [2]. There are also some other register allocation methods such as studying optimal spilling in the light of SSA [3], heuristic allocation method [4], allocation of repair strategies [5], layered allocation [6], etc. The graph-coloring method, which is a highly effective global register allocation method [7, 8], was proposed by Chaitin in 1981. The coloring process must ensure that the adjacent nodes have different colors. The number of colors that an interference graph needs in coloring is called as its register pressure, and the treatment modifying code in order to make the graph colorable is called “reducing register pressure”.

Spilling symbolic registers [9,10,11,12] is a method for reducing register pressure. Its basic idea is to split the lifetime of a register allocation candidate into two or more lifetimes, i.e., dividing the live range of a symbolic register into two or more parts. Physical registers will get the gap time between live ranges of divided candidates. This process is helpful to reduce register pressure [13, 14]. The basic method of register-spilling is to spill candidates to memory. In conventional register-spilling algorithm [15, 16], each pending spilling candidate needs a storage unit, indicating that the storage space needed is directly proportional to the number of candidates to be spilled. This paper is devoted to the study of reducing the storage space for spilling in register allocation through storage units multiplexing. An algorithm that is based on the graph coloring register allocation method will be presented to realize this optimization. Not only will this algorithm not impact the register spilling result, but also it can greatly reduce the storage units needed in register spilling and thus improve the utilization of memory.

2 Optimization Algorithm

In order to optimize the storing of register allocation candidates (called webs in what follows) to be spilled, we define the following quantities to analyze the code:

  1. (1)

    NDimMtx is an N-dimensional matrix template class, where N can be 1 or 2 for the problem considered in this paper.

  2. (2)

    AdjacentListRecord is a data structure containing the needed information of an adjacent list record.

  3. (3)

    ApInstn is code instruction object.

  4. (4)

    def and use are definition object and use object, respectively.

  5. (5)

    DU and UD are definition-use-chain and use-definition-chain, respectively.

  6. (6)

    spillWebs is a set of webs to spilled (a web is made up of DUs), and spillWebList is the corresponding list form of spillWebs.

  7. (7)

    spillWebAdjList is the adjacency list for the webs to be spilled.

The top-level process of our optimization method has the following main steps:

  1. (1)

    First Judge_NeedRegistersSpilling() determines whether the register allocation needs spilling. If yes, the following steps should be executed.

  2. (2)

    Next, Find_SpillWebs() function finds out all the webs to be spilled, and generates spillWebs and spillWebList.

  3. (3)

    Next, Get_SpillWebsConflictShip() function analyzes the active ranges of the webs in spillWebs, judges whether they are overlapping.

  4. (4)

    Then, Assign_StorageSpaceToSpillWebs() assigns storage units for each elements of spillWebs: it assigns the same storage spaces to the webs that don’t conflict with each other, and assigns different storage spaces to those conflict with each other.

  5. (5)

    At last, Gen_SpillCode() generates spilling and restore codes.

At the beginning of the optimization, the algorithm set the initial offset of the available storage space for spilling to baseOffset, a global static variable. Then, for each following register spilling process, the value of baseOffset will be equal to the address of the maximum offset determined by its previous register spilling process. The algorithm of the top-level structure of our method is as follows:

figure a

We assume that optimistic heuristic method is used to prune the interference graph. To describe whether a node in an interference graph result should be spilled, we set a Boolean value for each node as a flag to mark this status. We traverse the webs whose spilling flags are true and put them into spillWebs and spillWebList. As for the conflict relation among the webs to be spilled, it can be obtained directly from the existing adjacent matrix and adjacent list and is stored in the spillWebAdjList object corresponding to spillWebs.

In the process of register spilling, the address of the storage units assigned to the webs in spillWebList increases from the base address for spilling. For each web w, the algorithm traverses the storage units starting from the base address until it finds a unit whose corresponding web is not conflict with w. When the algorithm finds out such a storage unit, it assigns this storage unit to the web w and ends the traversing process. It should be noted that some architectures have both scalar and vector operands, and hence there will be scalar and vector webs in spillWebList. In our algorithm, we assume that the increment of traversing storage units for a scalar web is a, while that for a vector web is m*a, both m and a being integer.

The corresponding algorithm is as follows:

figure b

After all the webs in spillWebs being assigned storage units, the algorithm inserts corresponding spills and restores for them. This treatment is the same as that used in conventional graph coloring method, so we don’t repeat it in this paper.

3 Verification

To show the effectiveness of our method, we demonstrate the using of the method in an example (see the left side of Fig. 1) by comparing with the conventional storage assigning method. We assume that the aim architecture has 4 general purpose registers, i.e., R0, R1, R2, and R3, and has a register AR3 as the base address register for register spilling. In Fig. 1, the arrows are live ranges corresponding to the variables, and a stands for the size of a storage unit. The result intermediate codes after the first register spilling pass are shown in the right part of Fig. 1.

Fig. 1.
figure 1

Schematic diagram of the first pass of register spilling for source codes.

Full size image

The following physical register assigning process will find out that the assignment is not successful. Then a second register allocation pass with register spilling is needed, where f and m will be further spilled. The final allocation result is shown in the right part of Fig. 2. As a comparison, the allocation result based on the conventional storage unit assignment method for webs to be spilled is shown in the left part of Fig. 2.

Fig. 2.
figure 2

Comparison diagram for the result code that the spilled data storing optimization is used and that the spilled data storing optimization is not used.

Full size image

According to this example, it is easy to see from Fig. 2 that 4 storage units is needed by our method but 6 storage units is needed by the conventional method. Of Course, it should be noted that the optimization effect of our method will be different for different codes because it depends on the conflict relations among register allocation candidates.

4 Conclusion

In this paper, an optimization method of storage space optimization in register spilling is presented. This method is based on graph coloring register allocation method and consists of several main steps, such as identifying the register allocation candidates to be spilled, analyzing the conflict relation among these candidates, assigning storage units to these candidates, etc. It is demonstrated by an example that the method can reduce the storage units needed in register spilling, and that the correctness of graph coloring register allocation will not be affected. Consequently, more load/store instructions that directly access memory can be used in register spilling, and thus reducing the pressure on offset registers.