JPH03260732A - Register allocation system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a register allocation method in a compiler that analyzes a source program and generates a target program with high execution efficiency.

(Prior art) Figure 3 shows the basic configuration of a conventional compiler. The compiler manually inputs a source program (1), checks the syntax using a syntax analyzer (2), and performs appropriate code analysis. The intermediate code is converted into intermediate code, and the storage allocation section (3), optimization section (4), and register allocation section (
After the process 5), the final target program (7) is generated by the code generator (6).

In order to generate a target program with high execution efficiency, register allocation optimization plays an important role among various optimization techniques. °'Compilers by Aho et al., the standard work on writing compilers
Pr1ciples, techniques, a
ndTools (8ddison-Wesl
ey Publishing Company.

(1986), a program is divided into a sequence of consecutive statements called basic blocks, local register allocation is performed for these basic blocks, and the remaining registers are used to create global registers that cover a wider range. The allocation method is described as a typical register allocation method.

Theoretically, register allocation can be reduced to the problem of determining the mapping between the data to be allocated and a finite number of registers, but it is known that finding the optimal solution is extremely difficult. .

Accordingly, various heuristic techniques have been developed in the past. Taking global register allocation as an example, a typical process is to allocate registers for each loop that exists in a program. This is based on the empirical rule that loop execution takes up a very high proportion of the entire program's execution time. One method is to allocate registers in order of the frequency of data appearing during the loop. In this method, the mapping between data and registers is one-to-one. In other words, a register once allocated to certain data permanently corresponds to that data throughout the loop.

Although the above-mentioned global register allocation method is a simple algorithm and easy to understand, it is insufficient in terms of register allocation efficiency.

Chaitin et al. developed a more efficient global register allocation method by analyzing register allocation as a graph coloring problem. This associates the data to which registers are allocated with nodes on the graph, and connects corresponding nodes with lines for data that is simultaneously active at any point in the program. The graph obtained in this way is called a register interference graph.

Coloring a graph means applying different colors to adjacent nodes (nodes connected by lines) on an interference graph, and the colors used for coloring correspond to registers. If it is not possible to color all the nodes on the interference graph using a certain finite number of colors, we can select the node with the smallest profit and continue the coloring process by removing the note 4 from the graph. A method has been proposed. The register allocation method using graph coloring is the “Register A” method by Chaitin et al.
l-1location Via Coloring
(Computer Languages Vol. 6
．． 1981 pp, 47-57) and “Register A11ocation an
d Spilling Via Graph Color
ing (Proceeding 5IGPLAN8
2. Symposium Compiler C
on5truction, 5IGPLAN Noti
ces.

1982, pp98-105).

In any case, in the register allocation method described above, the profit is calculated, which shows how much profit there is when a register is allocated to the data that is the target of register allocation, compared to when it is not allocated. Evaluating this profit plays an important role in register allocation processing.

(Problem to be Solved by the Invention) In the conventional register allocation method, the profit is calculated for the data to be allocated to registers, and the value of the profit is evaluated to determine the set of data to which registers should be allocated. Or, conversely, data to be excluded from allocation candidates was determined.

However, since the profits are calculated all at once before the process of determining the mapping between data and registers, as the process of determining the mapping described above progresses, ・Array elements and the index of the array element ・Pointer and the pointer In cases where the profit value of one data changes depending on the status of register allocation for the other data, such as the data shown by , the profit is not evaluated accurately and the efficiency of register allocation decreases. There was a problem.

The above situation will be explained with reference to the drawings. Figure 4 shows
Part (8) of a FORTRAN program is shown, and in the corresponding intermediate code, the number of references to data appearing in statements (IO) to (13) included in the DO loop starting from statement (9) is Suppose that the results are obtained as shown in FIG. For simplicity, consider the above profit as the number of data references. 3
When registers are allocated to the data appearing in this loop in pairs in descending order of profit, a result as shown in FIG. 6 is obtained.

In the data set (14) to which registers are allocated,
Array elements ^(ind
ex) are both included. However, A (index
), the result is that the statement (
There is no need to use 1ndex except for the first reference to A (index) that appears in 10).

Therefore, the actual number of references to 1ndex is reduced by 3 to 3. According to FIG. 5, the actual number of references to 1ndex is the 4th in the whole, so 1ndex
Instead of a data set with no registers allocated (
15) It is more efficient to allocate registers to other data T included in the target program.

This invention was made in order to solve the above-mentioned problems, and aims to provide a register allocation method that prevents the value of profit from changing during the register allocation process and provides an efficient target program. purpose.

[Means to solve the problem]

The register allocation method according to the present invention divides the register allocation process into two stages, and in the first stage, uses a number of symbol registers equal to or less than the number of physical registers that can be used for the register allocation process to assign array elements or pointers. A symbol register is allocated to data that is indirectly referenced at the level of the target program, such as data pointed to by Regarding the intermediate code replaced with , physical registers are allocated to symbol registers and scalar data.

[Function] In this invention, by the above-mentioned first stage treatment,
Symbol registers are allocated to some data in the program, and after that information is reflected in the intermediate code, in the second stage processing, these symbol registers and scalar data that are not subject to processing in the first stage are allocated. Final physical register allocation is performed for the data in the program, and register allocation for the data in the program is completed.

(Example) An embodiment of the present invention will be described below.

FIG. 1 shows the configuration of a register allocation section according to this embodiment. In Figure 1, (16) is an intermediate code received from the previous processing unit, (17) is register allocation information, (18) is an intermediate code that includes symbol registers, and (19) is an intermediate code that includes physical registers. The register allocation unit (5) in this embodiment is a symbol register allocation unit (5a) for indirect reference data.
, an intermediate code conversion unit (5b), and a physical register allocation unit (5C).

Symbol lettuce 4 allocation part for the above indirect reference data (
In 5a), intermediate code (16) is input, symbol registers are allocated only for indirect reference data, that is, data pointed to by array elements or pointers, and the result is output as register allocation information (17).

The scope of register allocation is not particularly limited, but generally global allocation is performed for each loop or for the entire program.

Note that the symbol register herein means a register that ultimately has a one-to-one correspondence with a physical register, but whose specific register number has not yet been determined. however,
As a special case, it may be a physical register itself.

FIG. 2 shows a flowchart for allocating symbol registers to indirect reference data for each loop. This process will be explained below with reference to FIG.

First, a loop to be allocated to registers is searched for (step Sl). In the case of multiple nested loops, the innermost loop executes the most times, so register allocation searches for unprocessed loops starting from the innermost loop.

If there is no unprocessed loop, the process ends (step S2).

Otherwise, a set of indirect reference data appearing in the loop is determined (step S3). For array elements,
Analyzing the subscript expressions, those whose subscripts have the same value are the set V
It is one of the elements inside. Similarly, in the case of data pointed to by pointers, data whose pointers have the same value are treated as one element in the set V.

If the set ■ is empty (step S4), that is, there is no data to be allocated, the process moves to the next loop (step S1). If not, a set R of symbol registers to be used for allocation is determined (step S5).

The number of symbol registers is less than or equal to the number of usable physical registers, and the number of symbol registers should be determined by examining how much of the total data the indirect reference data that appears during the loop accounts for, etc. .

Next, the profit is calculated for each element of the set (step S6). For simplicity, here we consider the number of references as profit.

Next, the data vI with the largest profit is found in the set (2), and an arbitrary symbol register R in the set R is assigned to it (step S7).

After that, the data v to be allocated from the set ■
Remove I (step S8), and if the set V is empty (step 59), move on to the next loop (step Sl)
. Otherwise, the symbol register R used for allocation is removed from the set R (step 510). set R
If is empty (step 511), the process moves to the next loop (step SL). Otherwise, the process moves to allocation to the next data (step S7).

Returning to FIG. 1, the explanation will continue. Next, the intermediate code conversion unit (5b) refers to the register allocation information (17), and converts the indirect reference data to which the symbol register has been allocated by the above process into the symbol register on the intermediate code (16). Performs the replacement process. As a result, an intermediate code (18) containing symbol registers is generated.

In the case of high-level intermediate code that is close to the representation of the source program, references to data pointed to by array elements or pointers may simply be replaced with symbolic registers, but in the case of low-level intermediate code that is close to the machine language representation, In the case of code, since references to indirect reference data are expressed by multiple texts, processing such as deleting an index load instruction for the array element is also required, for example.

Next, the physical register allocation unit (5C) generates an intermediate code (
Regarding 18), physical registers are allocated for symbol registers and scalar data, and an intermediate code (19) including the physical registers is output.

The indirect reference data has already been processed by the indirect reference data symbol register allocation unit (5a), and even if unallocated indirect reference data exists, it is not subject to physical register allocation.

Furthermore, physical registers must be allocated to symbol registers, but this is guaranteed in principle since the number of symbol registers is limited to the number of physical registers.

Symbol register allocation unit for indirect reference data (5a
), the range of register allocation is not particularly limited. Regarding the allocation for each loop, a method similar to that described in the process of the symbol register allocation unit (5a) for indirect reference data can be applied. Here, the value of profit for the symbol register is set to infinity so that it is allocated with priority over scalar data.

Although the above embodiment has been described on the assumption that global register allocation is performed for each loop in each stage of processing, a local allocation method such as a graph coloring method may be used. Furthermore, although the internal configuration of the register allocation section has been explained assuming that each processing section is continuous, the intermediate code conversion section (5
b) and the physical register allocation unit (5c) may be separated; for example, an optimization processing unit may be placed between them.

〔Effect of the invention〕

As described above, according to the present invention, the register allocation process is divided into two stages, and the allocation to indirect reference data and the allocation to normal scalar data are separated, so that the association between indirect reference data and indirect indexes is separated. Regarding the above, the profit for one data does not change depending on the status of register allocation for the other data, and it is now possible to calculate the accurate profit, which enables more accurate register allocation and improves efficiency. This has the effect of providing a good objective program.

Also, depending on the machine architecture, there may be restrictions on the registers that can be used for specific instructions or specific data reference methods, so by using symbolic registers in the first stage of processing, the second stage of processing Since specific register numbers have not been determined at the start, the second stage of processing also has the effect of allowing more detailed allocation depending on the target machine at once.

[Brief explanation of drawings]

FIG. 1 is a configuration diagram of a register allocation section in an embodiment of the present invention, and FIG. 2 is a flowchart showing an overview of processing of the symbol register allocation section for indirect reference data in the register allocation section in an embodiment of the invention. Third
The figure is a basic configuration diagram of a compiler, Figure 4 is an explanatory diagram showing a part of a FORTRAN program to explain the problem to be solved by this invention, and Figure 5 is a diagram showing a portion of the FORTRAN program in the DO loop of the program in Figure 4. FIG. 6 is an explanatory diagram showing the number of times data is referenced, and FIG. 6 is an explanatory diagram showing the mapping relationship between data and registers when register allocation is performed using the conventional method. In the drawings, (1) is a source program, (5) is a register allocation section, (5a) is a symbol register allocation section for indirect reference data, (5b) is an intermediate code conversion section, and (5C) is a symbol register and scalar data. The physical register allocation part for (7) is the target program, (1
6) is intermediate code, (17) is register allocation information,
(18) indicates an intermediate code including symbol registers, and (19) indicates an intermediate code including physical registers. In each figure, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] In a compiler that analyzes a source program and generates a target program for a processor connected to a finite number of registers and a memory that has a storage capacity sufficiently larger than the total capacity of the registers and has a slower access time than the registers, As a first step, the number of symbolic registers equal to or less than the number of available physical registers is used to target indirect reference data that is accessed by indirect indexing at the level of the target program, such as data pointed to by array elements or pointers. A register allocation method characterized in that, as a second step, physical register allocation is performed for symbol registers and scalar data with respect to intermediate code in which data to which symbol registers have been allocated by the above processing is replaced with symbol registers. .