Compiler

The present invention relates to a compiler that converts source code into executable code.

Conventionally, the SuperH RISC Engine family of microcomputers 7750 series (hereinafter referred to as SH4) of Renesas Technology Corporation has a 16K byte operand cache that can be selected for copyback / write-through for data. As shown in Fig. 7, the operand cache consists of 512 cache lines, each cache line is a tag that stores bits 28 to 10 of the memory address of the data to be cached, and 32 bytes of data per cache line. It consists of a data part that stores data, a V bit that indicates whether valid data is stored in the cache, and a U bit that indicates whether the cache and memory match. The U bit reads new data into the cache when a cache error occurs. At that time, the U bit is used to refer to the U bit and write back the cached data to the memory if the cache and the memory do not match. That is, when a cache miss occurs, new data is read into the cache, but at that time, if the U bit is referenced and the cache and the memory do not match, the cached data is written back to the memory. When using the operand cache, the tags, U, and V bits are read from the cache line of the index (sequence number) indicated by bits 13 to 5 of the effective address of the memory (S1 in Fig. 7), and the effective address of the memory is used. Compare the tags with bits 28 to 10 (S2 in Figure 7). As a result of comparison, if they match and the V bit is valid, a cache hit occurs, and the data at the address indicated by bits 4 to 0 of the effective address of the memory is read or written from the data part of the cache line ( S3) in Fig. 7. As a conventional technique of this kind, there is a technique as shown in the following Patent Document 1.<patcit num="1"><text>Japanese Patent Application Laid-Open No. 5-257814</text></patcit>

<p> By the way, there are roughly three types of variables described in the source code. That is, as shown in Fig. 8, in the source code that defines the function func () {...}, (1) it is declared inside the function, memory is allocated from the stack when the function is executed, and only inside the function. Local variables that can be used, (2) Global that can be used from any function because the address in memory is determined at the time of linking from the object file declared outside the function and compiled and created for each source file into one executable file. Variables, (3) There are static variables that are declared with "static" added inside the function, the address in memory is determined at the time of linking, and can be used only in the declared function. Global variables and static variables can be assigned addresses at the time of linking, and variables can be placed at consecutive addresses. However, since local variables are assigned from the stack when the function is executed, global variables, static variables and local variables cannot be placed at consecutive addresses, but if they are local variables, they should be placed at consecutive addresses. Can be done.</p><p> However, conventional compilers do not consider whether or not a single arithmetic expression uses multiple variables of the same type. For this reason, the variable placement destinations are discontinuous, and when a plurality of variables of the same type are used in one arithmetic expression, a cache error occurs and the processing speed is reduced. For example, when using multiple local variables a, b, c, dummy1 and dummy2 in one function as shown in Fig. 8, when reading the variable a that is the assignment source, the variable a is a 4-byte int type. Therefore, bits 4 to bit 0 of the address of variable a are read as address data of 0x00 to 0x1F in the cache line corresponding to bits 13 to 5 of the address of variable a. In FIG. 8, when the address of the variable a is 0x0C000000, the data from 0x0C000000 to 0x0C00001F is read, so that 28 bytes of the variables a and dummy1 are read into the data part of the cache line. Then, as shown in FIG. 9, when writing to the variable b to be assigned, the variable b is not read in the cache and a cache miss occurs. Also, when variables a and b have the same value for bits 13 to 5, such as addresses 0x0C000000 and 0x0D000000, the same cache line will be used, and even if the data of variable a is read into the cache, it will be written to variable b. Is overwritten with the data of variable b, and the next time variable a is used, a cache miss will occur. As a result, there arises a problem that the cache cannot be used effectively and the processing speed is reduced.</p><p> An object of the present invention is to provide a compiler capable of placing variables on a cache so that the cache can be used effectively.</p>

<p> In order to achieve the above object, the present invention determines whether a plurality of variables of the same type are used in one arithmetic expression, and based on the determination result, variables of the same type are arranged in a continuous area of the cache. It is characterized by including a step of determining a placement address on the cache so as to be performed.</p>

<p> According to the present invention, by arranging variables of the same type of each arithmetic expression in continuous areas of the cache, variables of the same type of the arithmetic expression are both stored in the cache when the arithmetic expression is executed. It becomes easier and the processing speed can be improved.</p>

Hereinafter, embodiments of the present invention will be described with reference to the drawings. The compiler according to the present invention operates on the computer shown in FIG. The computer of FIG. 1 has a processor 101, a main memory 102, a bus 103, a disk device 104, and a CD-ROM reader 105, and the compiler contained in the CD-ROM (storage medium) 106 is a CD-ROM reader 105. Read using and stored in disk device 104 via bus 103. To execute the compiler, the compiler is transferred from the disk device 104 to the main memory 102 via the bus 103, and executed by the processor 101.

FIG. 2 shows an embodiment of the functional configuration of the compiler according to the present invention. The compiler 201 in FIG. 2 receives the source program 202 as an input, parses it with the intermediate code conversion unit 203, converts it into intermediate code, optimizes it with the optimization unit 204, and finally the local variable is set with the code generation unit 205. Convert to machine code 206 so that it is placed in a contiguous area of the cache. The detailed processing of the code generation unit 205 in FIG. 2 is shown in a flowchart in FIGS. 3 and 4.

In FIG. 3, the code generation unit 205 determines whether all the sentences in the source code 202 have been searched (step 301), and if all the sentences have been searched, the process proceeds to the global variable placement process (FIG. 4). However, if it is not finished, one source code statement is extracted (step 302) and it is determined whether the statement uses multiple local variables (step 303). In step 303, if a plurality of local variables are used in one arithmetic expression, the process proceeds to step 304, and if a plurality of local variables are not used, the process proceeds to step 306. In step 304, it is determined whether there are a plurality of local variables for which there is no initialization data. Since the compiler separates the area to be arranged for the variable with the initialization data and the variable without the initialization data, it is not possible to arrange the variable with the initialization data and the variable without the initialization data in the continuous area. Therefore, if there are a plurality of variables without initialization data, the process proceeds to step 305, and if there are no variables, the process proceeds to step 306. In step 305, the local variable information 510 as shown in FIG. 5 (b) is created. In the local variable information 510, the reference local variable name 5101, the variable name having an assignment relationship with the variable 5101, and the information 5102 consisting of the number of times of having an assignment relationship on the program source are registered as many as the number of assignment relationships. In this case, if the reference local variable 5101 has already been registered and the variable name 5102 in the assignment relationship has already been registered, only the number of uses is counted up.

In step 306, it is determined whether or not a plurality of global variables are used in one expression, and if they are used, the process proceeds to step 307, and if not, the process proceeds to step 308. In step 307, the global variable information 500 shown in FIG. 5 (a) is created. The global variable information 500 has a reference global variable name 5001, an allocation destination address 5002 if the allocation destination is determined, a variable name that has an assignment relationship with the reference variable 5001, and an assignment relationship on the program source. Register the usage count information 5003 as many as the number of substitution relationships. In this case as well, if the reference global variable 5001 has already been registered and the variable name 5003 in the assignment relationship has already been registered, only the number of uses is counted up. In step 308, it is determined whether the search for one function is completed. When finished, the process proceeds to step 309. If not completed, the process returns to step 301. In step 309, based on the local variable information 510 created in step 305, the local variables having a large number of assignment relationships are preferentially placed in the continuous area of the cache. Specifically, as shown in the example of FIG. 8, a plurality of variables are used in one arithmetic expression, and variables of the same type are arranged at consecutive addresses. At that time, make sure that the addresses other than bits 4 to 0 of the addresses arranged so that they can be read into the data part of the same cache line are the same.

By doing so, the local variables a and b used in the calculation formula of the example of FIG. 8 are arranged in the data part of the continuous area of the cache line at the time of execution as shown in FIG. As a result, the data of variables having an assignment relationship can be read into the cache by reading into the cache once, the cache can be used effectively, and the processing speed can be improved. At this time, if there are existing assignment relationships that have been used the same number of times, they are arranged in the order in which they appear. On the other hand, when all the statements are searched in step 301, the process proceeds to the global variable placement process (Fig. 4).

In FIG. 4, in step 401, it is determined whether or not all the global variable information 500 created in step 307 has been searched, and if not, the process proceeds to step 402, and if all have been searched, the process ends. In step 402, the one with the largest number of assignment relationships of 1 or more is searched. In the following step 403, it is determined whether the global variable searched in step 402 and the global variable having the largest assignment relationship with the global variable are both determined by the user. If the placement destination has been decided for both, the process proceeds to step 404, and if the placement destination has not been decided for either one, the process proceeds to step 405. In step 404, the global variable is placed in the area specified by the user. In step 405, it is determined whether one of the global variables in the assignment relationship has been placed or has been placed by the user. If the placement destination has been decided, the process proceeds to step 406, and if not, the process proceeds to step 407. In step 406, the variable whose placement destination is not determined is continuously placed in the variable whose placement destination is fixed.

In step 407, variables whose placement destinations are not determined are placed in a continuous area. At this time, the addresses other than bits 4 to 0 of the arranged addresses should be the same so that they can be read into the data part of the same cache line. That is, the indexes are the same. Then, an address to be placed at the placement destination address 5002 of the global variable information 500 is set. By doing so, when the next assignment relationship is searched, it will be placed in the area where it was placed this time. In step 408, set the number of assignment relationships of the placed global variables to "0" so that they will not be the target of the next search.

<figref num="1">It is a block diagram which shows the embodiment of the computer which executes the compiler which concerns on this invention.</figref><figref num="2">It is a functional block diagram which shows the embodiment of the compiler which concerns on this invention.</figref><figref num="3">It is a flowchart which shows the process of the code generation part of FIG.</figref><figref num="4">It is a flowchart which shows the detail of the global variable arrangement processing of FIG.</figref><figref num="5">It is a figure which shows the data structure example of a global variable, a local variable information.</figref><figref num="6">It is explanatory drawing which shows the arrangement example of the local variable when this invention is applied.</figref><figref num="7">It is explanatory drawing which shows the structure of an operand cache.</figref><figref num="8">It is a figure which shows the example of the source code which described the local variable which has an assignment relation.</figref><figref num="9">It is explanatory drawing which shows the arrangement example of the local variable which a cache miss occurs.</figref>

Code description

101 Processor 102 Main memory 104 Disk device 202 Source code 201 Compiler 203 Intermediate code conversion unit 204 Optimization unit 205 Code generator 206 Machine code 500 Global variable information 510 Local variable information