JP2002099425A - How to convert global variables to local variables - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To eliminate redundant memory references in use of global variables existing across function calls. In a compiler that performs local variable conversion of a global variable, if a function call exists in a conversion target area and a global variable is used in a callee function, the compiler calls the function of the callee. An argument corresponding to the global variable is added, and a function in which the use of the global variable in the function is replaced by the use of the added argument is newly created, and the caller calls the newly created function. .

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a compiling method for reducing the execution time of an object program in a computer utilization technique. In particular, the present invention relates to a program conversion method for reducing the number of executed memory reference instructions by replacing global variable references with local variable references.

[0002]

2. Description of the Related Art The performance of microprocessors has been dramatically improved by improving the parallelism at the instruction level and the operating frequency. On the other hand, DRAM which constitutes the main memory of the computer
(Dynamic RAM) performance improvement is at a lower level than processor performance improvement, and the number of cycles required for memory reference tends to continue to increase. To reduce the number of memory references, the compiler uses register allocation techniques to place variables that are referenced (defined or used) multiple times in a program in registers whenever possible. However, if there is a function call between multiple references, variables that may be referred to by the callee, such as global variables, need to be stored in memory before the call if their values are defined, If it is used after the call, it must be loaded again.

For example, if there is a program in which a reference to a global variable G exists before and after a function call performed conditionally as shown in FIG. 8A, a statement 806 stores the value of G in a memory as it is. Perform store, sentence 811
Generates an object code for loading the value of G. However, if the result of the condition determination in the statement 807 indicates that no call to the function f has occurred, these stores and loads are unnecessary. In such a case, for example, the document “A.
V. S. Sastry et al., A New Algorithm
m for Scalar Register Promo
Tion Based on SSA Form, Proc
eatings of the ACMSGPLAN ''
98 Conference on Programmi
ngLanguage Design and Impl
emmentation, pp. 15-25, 199
8), prepare a local variable of the same type as the global variable, replace the reference of the global variable with the reference of the local variable, and make the value consistent between the global variable and the local variable only where necessary. A method of removing a redundant memory reference by converting a program so as to perform a process that takes responsiveness is being studied.

When this method is applied, the program in FIG. 8A is converted as shown in FIG. 8B, and if the function call does not occur because the condition determination of the statement 820 is not satisfied, the value of G is reset. Since the loading is not performed, the program execution speeds up.

[0005]

According to the local variable conversion method of global variables shown in the above-mentioned paper, redundant memory references of global variables included in a caller function are deleted, but in a callee function, The case where there is a reference to the global variable is not considered, and the redundant memory reference could not be deleted. For example, in FIG. 6A, the function trim including the use of the global variable G is called a plurality of times in a loop extending from the statements 607 to 610. At the time of loop execution, a memory reference (load) to the use of G in the statement 616 occurs every time the trim is called. In the conventional method, a redundant memory reference existing over such a function call is used. I couldn't handle it.

[0006] It is an object of the present invention to provide a method for eliminating redundant memory references in the use of global variables that exist across function calls.

[0007]

In order to achieve the above object, according to the present invention, a function call exists in an area where a local variable conversion of a global variable is to be applied, and the global variable to be converted into a local variable is If used by the callee, local variable conversion is performed after the use of the global variable at the callee is removed by adding a new argument (this is referred to as argument conversion).

In the argument conversion, for a function and a global variable to be converted, an argument of the same type as the global variable is added to the function, and a function in which the use of the global variable in the function is replaced with the use of the argument is newly added. Perform the process of creating. At the same time, the call site of the caller adds a corresponding global variable to the argument and changes the call site to call the newly created function.

By performing this conversion, the use of the global variable existing in the callee function is moved to the caller as an argument. As a result, the use of a global variable existing over a function call becomes a target of local variable conversion of the global variable in the conventional function, and redundant memory reference can be deleted.

[0010]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention will be described below.

FIG. 1 is a configuration diagram of a computer system on which a compiler according to the present invention operates. As shown, the computer system includes a CPU 101, a main storage device 104, an external storage device 105, a display device 102, a keyboard 1
03. The external storage device 105 stores a source program 106 and an object program 107. The main storage device 104 includes a compiler 108
And the intermediate code 10 required in the compilation process
9. The variable reference table 110 and the argument conversion table 111 are held. The compiling process is performed by the CPU 101 executing the compiler program 108. The keyboard 103 is used to give commands from the user to the compiler 108. The display device 102 informs the user of the end of compilation or an error.

FIG. 2 is a flowchart showing the flow of the compiling process. In the processing of the compiler, first, in step 201, syntax analysis is performed. The syntax analysis reads the source program 106 and creates an intermediate code 109 that can be processed inside the compiler. For the syntax analysis processing, see, for example, "Eiho, Seshi, Ullman: Compiler I
(Science, 1990) pages 30-74 ". Next, in step 202, a variable reference analysis is performed. Regarding variable reference analysis, see “Aho, Seshi and Ullman: Compiler II (Science, 1990) 74
Pages 1 to 772 ". By the variable reference analysis, a set of variables referred to in each statement included in the program and a type of reference (definition, use) are obtained, and these are recorded in the variable reference table 110. Then step 20
At 3, check whether there is any unprocessed function. If not, proceed to step 206, generate an object code, and end. The object code generation is also described in “Eiho, Seshii and Ullman: Compiler II (Science Inc., 1990), pp. 624-707”.
If there is an unprocessed function, one function is extracted in step 204 (assumed to be n). Then, in step 205, a global variable local variable conversion process is performed on the global variables in n. This processing will be described in more detail with reference to FIGS. After this processing, the processing is repeated from step 203.

FIG. 3 is a diagram showing the flow of the processing of step 205 in detail. Here, among the functions called from the given function n, necessary variables are subjected to global variable argument conversion, and then local variable conversion processing is performed on the global variables in n.

First, in step 301, among the functions called by the function n, a function requiring argument conversion and a global variable to be converted are obtained. The result is recorded in the argument conversion table 111. This processing will be described later in detail with reference to FIG. In step 302, it is checked whether there is an unprocessed function among the functions registered in the argument conversion table 111.
Proceed to 6. If there is, at step 303, one of the functions is taken out (this is taken as f). In step 304, argument conversion is performed on f, and a new function is created (this is referred to as f2
And). This processing will be described later in detail with reference to FIG. In step 305, the call site of f registered in the argument conversion table 111 is modified so as to call f2, and the converted global variable is added as an argument. Finally, in step 306, local variables are converted from global variables. Step 306 is conventional.

FIG. 4 is a diagram showing the flow of the process of step 301 in detail. In step 401, for all functions called from the function n, a set of used global variables is checked from the variable reference table 110, and the union thereof is obtained (let it be u). u is a set of global variables that are candidates for argument conversion. Step 402
Then, it checks whether there is any unprocessed global variable in u, and terminates if not. If there is, at step 403, one of the global variables is taken out (it is set as g). In step 404, a reference area of g in the function n is obtained (let it be r). Here, the reference region of g is a set of sentences that define or use g. However, for the call site, the statement in which g is defined or used in the callee is also included in the reference area. In step 405, it is checked whether there is an unprocessed sentence among the sentences included in r.
Return to 02. If there is, at step 406, one sentence is extracted (let it be s). In step 407, it is checked whether or not any of the execution paths from s reaches the call site included in r.
Return to 5. If so, a redundant memory reference may occur between the reference to g in s and the reference to g in the function called from that call site. Then, the process proceeds to step 408. Among call sites in r that can be reached from s, those that use and do not define g at the call destination, call function (f), used global variable (g), call The set of sites is registered in the argument conversion table 111, and the process returns to step 405.

FIG. 5 is a diagram showing in detail the flow of the process of step 304. First, in step 501, the function f is cloned, and a new function f2 is created. Step 5
In 02, it is checked whether there is any unprocessed global variable in the function f registered in the argument conversion table 111, and if not, the process ends. If there is, at step 503, one of the global variables is extracted (let it be g). Step 50
In step 4, a variable having the same type as g is added as an argument of the function f2 (this is referred to as g2). In step 505, the reference of g in the function f2 is replaced with the reference of g2.

Next, an application example of the present embodiment will be described. Consider a program as shown in FIG. 6A as an input.

A variable reference table as shown in FIG. 6B is created by the variable reference analysis in step 202 in FIG. For global variables, G is the statement 616 in the function trim.
And 617.

Next, at step 204, m as an unprocessed function
ain is extracted, and in step 205, local variables are converted into global variables. In FIG. 3 showing step 205 in detail, first, in step 301, a function and a global variable to be subjected to argument conversion are selected from functions called from the main.

In FIG. 4 showing step 301 in detail, first, in step 401, a union of global variables used in the called function is obtained. The function called from main is only trim, and it can be seen from the variable reference table that the set of global variables used is {G}. In step 402, G is selected as an unprocessed global variable (step 403). Step 40
When the reference region of G is obtained in step 4, it becomes {608}, and in step 405, the sentence 608 is selected as an unprocessed sentence and is set as s (step 406). When it is checked in step 407 whether there is a call site in r that can be reached from s, it is found that the call site can reach itself (statement 608) by an execution path that follows a loop from statement 607 to statement 610. move on. In step 408, the function t to be converted
rim, global variable G to be converted, call site 6
08 is registered in the argument conversion table.

Returning to FIG. 3, next, at step 302, one unprocessed function is extracted by referring to the argument conversion table. Where tr
Since only im is registered, this is selected (step 303). In step 304, argument conversion is applied to trim. First, in step 501, a function trim2 obtained by cloning trim is created. Step 50
In step 2, the parameter conversion table is checked to see if any of the global variables registered for trim is unprocessed, and G is selected (step 503). Step 504
To add an argument g of the same type as G to trim2 (see statement 713 in FIG. 7). At step 505, sentence 6 in trim2
Replace the use of G in 16, 617 with g. FIG.
Trim2 in (a) is the result of the replacement.

Next, in step 305, the call site corresponding to the function whose argument has been converted based on the argument conversion table is replaced with the function call after the argument conversion (statements 716 and 71).
7). The call of trim in statement 608 is trim
2 and a new G is added as an argument (statement 708). Main in FIG. 7A is the result of the conversion.

Finally, at step 306, a conventional local variable conversion of a global variable is performed. The conversion result is shown in FIG.
become that way. After the use of the global variable G in trim has moved into main, it has been moved out of the loop by local variable conversion of the global variable. This eliminates redundant memory references in the use of G that occurred with each call of trim, and occurs only once at the loop entry.

[0024]

In accordance with the present invention, a method is provided for eliminating redundant memory references in the use of global variables across function calls. As a result, the amount of memory reference at the time of program execution is reduced, which is effective in speeding up program execution.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a computer system on which a compiler of the present invention operates.

FIG. 2 is a diagram showing a processing flow of a compiler.

FIG. 3 is a diagram showing a flow of a local variable conversion process of a global variable.

FIG. 4 is a view showing a flow of an argument conversion application target determination process.

FIG. 5 is a diagram showing a flow of an argument conversion process.

FIG. 6 is a diagram showing an example of local variable conversion of a global variable according to the present invention.

FIG. 7 is a view showing an example (result) of local variable conversion of a global variable according to the present invention.

FIG. 8 is a diagram showing an example of a local variable conversion of a global variable according to the related art.

Claims (3)

[Claims] In a compiler for performing local variable conversion of a global variable, when a function call exists in a conversion target area and a global variable is used in a callee function, the compiler calls the function of the callee. Add a function corresponding to the global variable, replace the use of the global variable in the function with the use of the added argument, and newly create a function, and call the newly created function. A program conversion method. 2. A compiler using the program conversion method according to claim 1. 3. A storage medium storing the compiler according to claim 2.