JP2001067234A - Compiler and processor - Google Patents

Abstract

(57) [Problem] To provide a compiler which generates an alias check instruction for checking an alias state and arranges a load instruction before a store instruction, and a processor having the alias instruction. A compiler includes an instruction analysis unit that generates intermediate code from a source program, an instruction optimization unit that deletes extra instructions in the generated intermediate code, and an instruction conversion unit that converts an instruction into an executable target program. The instruction optimizing unit includes: a store / load instruction extracting unit that extracts a set of a store instruction and a load instruction from the intermediate code generated by the instruction analysis unit; Alias check instruction generating means for generating an alias check instruction for detecting the overlap at execution, and rearranging the instruction sequence in the order of an alias check instruction, a load instruction, and a store instruction, and replacing the conditional instruction with the original position of the load instruction And an instruction arranging means for arranging instructions.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a compiler for rearranging an instruction sequence and performing an optimization process in order to speed up the execution of a computer, and a processor for executing an instruction sequence compiled by the compiler.

[0002]

2. Description of the Related Art Although the performance of processors has been remarkably improved in recent years, the access speed of a memory is not as fast as the operation speed.

Therefore, a delay in memory access due to a cache mishit at the time of a load instruction and a delay due to a data transfer wait on the cache memory at the time of a load instruction tend to be further increased.

[0004] Therefore, in order to enable parallel processing with other instruction processing, it is necessary to group load instructions having a slow memory access time as much as possible and access the memory first.

Therefore, a compiler that precedes the load instruction is required.

FIG. 7 shows a configuration diagram of a conventional compiler 1.

[0007] The compiler 1 includes an instruction analysis unit 11 for generating intermediate code from the source program 2 and an optimization process for the generated intermediate code (the optimization process is a process for deleting extra instructions, collecting duplicate instructions, and so on). It is composed of an instruction optimizing unit A12 that performs processing for speeding up an instruction sequence such as conversion to a high-speed instruction, and an instruction converting unit 13 that generates a code of the target program 3 based on the optimization result. You.

Each instruction of the target program 3 is fetched and executed by the processor 4.

When the load instruction is rearranged before the store instruction on the compiler in order to speed up the memory access and the preceding execution is performed, the operand address of the load instruction and the store instruction on the memory is unknown on the compiler. And it was difficult to analyze the overlap (hereinafter referred to as alias) of the operand addresses of the load instruction and the store instruction.

For example, since pointers are frequently used in a program described in C language, the compiler cannot detect an alias relationship between a load instruction and a store instruction.

However, in actual program execution,
Since the operand addresses of the load instruction and the store instruction hardly overlap, the possibility that the load instruction is arranged before the store instruction to reduce the influence of the delay due to the memory access of the load instruction has not been utilized.

An object of the compiler of the present invention is to generate an alias check instruction for checking an alias state,
By arranging a load instruction before a store instruction, access to the load instruction at the time of execution is speeded up.

[0013]

An instruction analysis unit for generating an intermediate code from a source program, an instruction optimizing unit for deleting extra instructions in the generated intermediate code, and an instruction conversion unit for converting the generated intermediate code into an executable target program. Wherein the instruction optimizing unit comprises: a store / load instruction extracting unit for extracting a set of a store instruction and a load instruction from the intermediate code generated by the instruction analysis unit; An alias check instruction generating means for generating an alias check instruction for detecting an overlap between instruction operand addresses at the time of execution, and an instruction sequence rearranged in the order of an alias check instruction, a load instruction, and a store instruction, and executing the alias check instruction. When the overlap between the operand addresses is detected, the load instruction execution is corrected and the overlap is performed. There when not detected, nothing is configured to have an instruction arrangement means for arranging instruction with no execution condition to the original position of the load instruction.

According to this configuration, the alias check instruction checks the alias state when the target program is executed by the processor, so that it is possible to confirm whether the load instruction is moved before the store instruction. As a result,
If the movement is valid, the load instruction can be executed in advance, so that the speed of instruction execution can be increased. If the movement is invalid, the previously executed load instruction is invalid, so that an instruction (load instruction or move instruction) for correcting the content of the load instruction is executed. With this correction instruction, the contents of the preceding execution of the load instruction can be corrected.

The alias check instruction has a first input value for setting an operand address of a store instruction, a second input value for setting an operand address of a load instruction,
A third input for comparing the total value of the address sizes of at least one or more load instructions with the total value of the address sizes of at least one or more store instructions and setting a total value of the equal or larger address size Has the value
The absolute value of the difference between the first input value and the second input value is calculated. If the calculated result is smaller than the third input value, it indicates that the operand address of the load instruction and the operand address of the store instruction overlap. The check information is turned on.

With this configuration, one or more load instructions can be moved together before one or more store instructions, so that an alias check instruction can be generated which increases the effect of preceding execution of the load instruction.

When the data size of one load instruction is equal to the data size of one store instruction, 1 is set as the third input value of the alias check instruction. In this configuration, the value of the data size is set as the third input value.

With this configuration, an alias check instruction for determining whether the preceding execution of the load instruction before the store instruction is valid or invalid can be generated only by comparing the data size between the one load instruction and the one store instruction.

Also, the processor for executing the target program generated by the compiler has an execution means for executing the alias check instruction generated by the compiler.

With this configuration, it is possible to execute a target program in which a load instruction is arranged before a store instruction for preceding execution by using a processor capable of executing the generated alias check instruction.

[0021]

FIG. 1 shows a configuration diagram of a compiler 1 according to an embodiment.

The compiler 1 analyzes the source program 2 to generate an intermediate code, an instruction analyzing section 12 for optimizing instructions, and an instruction optimizing section 12 based on the results of the instruction optimizing section 12. The instruction conversion unit 13 generates a code.

The instruction optimizing unit 12 includes an instruction optimizing unit A and an instruction optimizing unit B.

The instruction optimizing unit A performs processing for speeding up the instruction sequence, such as the removal of extra instructions, the grouping of duplicate instructions, and the conversion to higher-speed instructions, as in the prior art.

The instruction optimizing unit B performs the processing of generating an alias check instruction for checking the alias state of a load instruction and a store instruction and the processing of arranging instruction strings such as an alias check instruction, a load instruction, and a store instruction. Performs processing to speed up columns.

The processor 4 inputs the target program generated by the compiler 1 and executes each instruction including an alias check instruction.

When the source program is input to the instruction analysis unit 11, the compiler 1 checks the grammar and generates an intermediate code if there is no error.

The generated intermediate code is transferred to the instruction optimization unit 12
To perform optimization processing.

The instruction optimizing unit B which is a feature of the present invention will be described.

FIG. 2 shows a flow chart of the instruction optimization unit B. (1) Detect a group of load instruction and store instruction from the intermediate code. (2) Perform alias check instruction generation processing based on the detected instruction. (S2 step) (3) Place the load instruction before the store instruction following the alias check instruction. (S3 step) (4) Check whether the third input value of the alias check instruction is 1 or not. (S4 step) (5) If the third input value is not 1, a conditional load instruction is arranged at the position of the original load instruction. (S5 step) (6) When the third input value is 1, a conditional move instruction is arranged at the position of the original load instruction. (S6 Step) FIG. 3 shows a flowchart of the alias check instruction generation processing.

An alias check instruction is an instruction for checking the alias state of operand addresses (hereinafter, abbreviated as addresses) of a load instruction and a store instruction.

The alias check instruction is vailias a1,
a2, x.

First input value a1: Store instruction address Second input value a2: Load instruction address Third input value x: Predetermined value When the processor 4 executes the instruction of the target program 3, the processor 4 The address is compared with the address of the load instruction. If the address is equal to or more than a predetermined value, check information indicating that the addresses do not overlap (hereinafter, referred to as the z flag of the condition code cc) is turned off. And S3
The execution of the load instruction moved in step is made valid.

At this time, the conditional load instruction generated in S5 step or the conditional move instruction generated in S6 step at the position of the original load instruction does not execute anything.

If the difference between the address of the store instruction and the address of the load instruction is smaller than a predetermined value, the z flag of cc indicating that the addresses are overlapped is turned on, and the execution of the moved load instruction is regarded as invalid. At the position of the load instruction, the same load instruction is executed again by the conditional load instruction, or the load instruction is moved to a predetermined register by the conditional move instruction to execute the correction processing of the load instruction.

The generation of an alias check instruction in the compiler 1 will be described.

An example in which a plurality of load instructions are moved over a plurality of store instructions will be described. (1) Search for N groups of store instructions and set a register indicating the reference address to the first input value. (S21
(2) Search M groups of load instructions and set the register indicating the reference address to the second input value. (S22
Step 3) (3) Check whether N = M = 1. (S23 step) (4) Obtain and compare the total value of the address sizes of the N groups of store instructions and the M groups of load instructions. (S24 step) (5) If N = M = 1, it is checked whether the data size of the load instruction is equal to the data size of the store instruction. (S25 step) (6) When N = M = 1 and the data size of the load instruction is equal to the data size of the store instruction, the third input value is set to 1. (S26 step) (7) If N = M = 1 and the data sizes of the load instruction and the store instruction are not equal, the larger value of the data size is set as the third input value. (S27 step) (8) If the load or store instruction is multiple instructions,
A value having the same or larger address size is set as the third input value. (9) An alias check instruction is generated based on the first to third input values. (S29 step) A specific example is shown below.

FIG. 4 shows an instruction sequence when an alias check instruction is generated according to the first embodiment.

FIG. 4A shows an instruction sequence before generation, and FIG.
Indicates an instruction sequence after generation.

First, an alias check instruction is generated based on the instruction string before generation.

Assuming that the instruction sequence is arranged in the order of a plurality of load instructions and a plurality of store instructions, the processing of generating an alias check instruction is performed as follows.

As a result of searching the group of store instructions, if the data size of the store instruction is an instruction of 1 byte, the address size of the group is changed from address [r1] to [r1 +
1]. Therefore, the first input value of the alias check instruction is (r1)
It is.

On the other hand, if the load instruction is an instruction having a data size of 4 bytes, the address size is 12 bytes from address [r2] to [r2 + 11]. Therefore, the second input value of the alias check instruction is (r2)
It is.

Next, comparing the address size of the store instruction with 2 bytes and the address size of the load instruction with 12 bytes, the address size of the load instruction is large. Therefore, the value 12 is set as the third input value.

FIG. 5 is an explanatory diagram of the address size according to the first embodiment.

The range where the load instruction and the store instruction overlap is actually between [r2] and [r2 + 11]. However, the alias check instruction determines that addresses overlap between [r2-11] and [r2 + 11]. This is [r2-11]
From [r2 + 11], if [r1] exists in [r2 + 11], it may become an alias, so it is determined that [r1] does not exist in that range. As a result, an instruction can be processed by one instruction instead of a plurality of instructions, so that the processing can be speeded up.

Next, the instruction placement processing will be described.

FIG. 4B shows an instruction sequence after the alias check instruction is generated.

After the alias check instruction (FIG. 4b), a plurality of store instructions are skipped and a plurality of grouped load instructions are arranged. (FIG. 4B) Next, a store instruction and the like are arranged following the load instruction while maintaining the arrangement relation between the store instruction and the position of the original load instruction. (FIG. 4B) Next, a conditional load instruction is arranged at the position of the original load instruction. Thus, the instruction arrangement processing is completed (of FIG. 4B).

The instruction sequence arranged as described above is transferred to the instruction conversion unit 1.
In step 3, after conversion into the target program 3, when the program is executed by the processor 4, the following operation is performed.

By executing the alias check instruction, |
If the value of r1-r2 | is smaller than the third input value, the z flag of the cc flag is turned on. Turn off if larger.

Address [r2], [r2 + 4], [r2 + 8]
4 bytes of data from register r30 and register r3
1. Load to register r32. (FIG. 4B) The data indicated by the register r10 is stored at the address indicated by the address [r1]. (FIG. 4B) When a conditional load instruction is issued, only when the z flag is ON, 4-byte data from the address [r2 + 4] is reloaded into the register r31. If the z flag (of FIG. 4b) is off, do nothing and go to the next instruction.
The data indicated by the register r11 is stored at the address indicated by the address [r1 + 1]. (FIG. 4B) When a conditional load instruction is issued, 4-byte data from the address [r2 + 8] is loaded into the register r32 only when the z flag is ON. (FIG. 4b) If the z flag is off, proceed to the next instruction without doing anything.

As described above, the compiler 1 generates the alias check instruction in a pair with the conditional load instruction, so that the processor can execute the instruction at high speed.

FIG. 6 shows an instruction sequence when an alias check instruction is generated in the second embodiment.

FIG. 6A shows an instruction sequence before generation, and FIG. 6B shows an instruction sequence after generation.

The instruction sequence before the generation of the alias check instruction is arranged in the order of one store instruction and one load instruction.

The process of generating an alias check instruction is performed as follows.

As a result of searching the group of store instructions, if the store instruction is an instruction having an address [r1] and a data width of 4 bytes, the first input value of the alias check instruction is [r
1]. (FIG. 6a) On the other hand, since the load instruction is an instruction having a data width of 4 bytes at address [r2], the second input value of the alias check instruction is:
[R2]. (FIG. 6a) Next, comparing the data size of the store instruction and the data size of the load instruction, since they are equal, the third input value is set to 1.

Next, the instruction arrangement processing will be described.

FIG. 6B shows an instruction sequence when an alias check instruction is generated in the second embodiment.

After the alias check instruction (FIG. 6B), a load instruction is arranged, skipping a store instruction.
(FIG. 6B) Next, the store instruction is arranged after the load instruction while maintaining the arrangement relation between the store instruction and the position of the original load instruction. (FIG. 6B) Next, a check move instruction is arranged at the position of the original load instruction. (FIG. 6B) Thus, the instruction placement processing is completed.

When the above instruction is executed by the processor 4, | r1 is executed by executing the alias check instruction.
If the value of -r2 | is smaller than 1, the z flag of the cc flag is turned on. Turn off if larger. (Fig. 6b) 4 bytes from address [r2] are loaded into register r3,
The register r0 is stored in 4 bytes from the address [r1]. (FIG. 6B) When a check move instruction is issued, the contents of the register r0 are transferred to the register r3 only when the z flag is ON. (FIG. 6b) If the z flag is off, proceed to the next instruction without doing anything.

As described above, since the compiler 1 generates an alias check instruction in a pair with a conditional move instruction, the processor can execute the instruction faster.

[0064]

According to the present invention, the effect of memory access delay due to a cache miss of a load instruction can be reduced.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of a compiler according to an embodiment;

FIG. 2 is a flowchart of an instruction optimization unit B of the embodiment.

FIG. 3 is a flowchart of an alias check instruction generation process according to the embodiment;

FIG. 4 is an instruction sequence when an alias check instruction is generated according to the first embodiment.

FIG. 5 is an explanatory diagram of an address size according to the first embodiment;

FIG. 6 shows an instruction sequence when an alias check instruction is generated according to the second embodiment.

FIG. 7 is a configuration diagram of a conventional compiler.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Compiler 2 Source program 3 Objective program 4 Processor 11 Instruction analysis part 12 Instruction optimization part 13 Instruction conversion part

Claims (4)

[Claims] An instruction analyzing unit for generating an intermediate code from a source program, an instruction optimizing unit for deleting extra instructions of the generated intermediate code, and an instruction converting unit for converting the generated intermediate code into an executable target program. A compiler, wherein the instruction optimizing unit is a store / load instruction extracting unit for extracting a set of a store instruction and a load instruction from the intermediate code generated by the instruction analysis unit; and an operand address of the extracted load instruction and the store instruction. An alias check instruction generating means for generating an alias check instruction for detecting overlap between executions, and an instruction sequence rearranged in the order of an alias check instruction, a load instruction, and a store instruction. When an overlap is detected, the load instruction execution is corrected, and no overlap is detected. Compiler characterized in that it comprises an instruction arrangement means for arranging the original position of the load instruction instruction conditional do not do anything when the Tsu. The alias check instruction is a sum of a first input value for setting an operand address of a store instruction, a second input value for setting an operand address of a load instruction, and an address size of at least one load instruction. And a third input value for comparing the sum of the address sizes of at least one or more store instructions to set a sum value of the equal or larger address size, the first input value and the third input value. The absolute value of the difference between the two input values is calculated, and if the calculated result is smaller than the third input value, check information indicating that the operand address of the load instruction and the operand address of the store instruction overlap is turned on. 2. The compiler according to claim 1, wherein: 3. When the data size of one load instruction is equal to the data size of one store instruction, 1 is set as the third input value of the alias check instruction. The value of the data size is set as a third input value.
The listed compiler. 4. A processor for executing a target program generated by a compiler, the processor having an alias check instruction generated by the compiler according to claim 1.