JPH04252336A - Program optimization processing device - Google Patents

Abstract

PURPOSE:To obtain a program optimization processor which changes the executing order of instruction trains so as to attain the optimization of a program to the execution of a processor which performs the pipeline processing in regard of the program optimization processing of a computer. CONSTITUTION:An inter-instruction weight data base 2 holds the information which shows the estimated pipeline break length as the prescribed weight value when two instructions are continuously carried out for each arrangement of two necessary instructions of different types. A reliance analyzing part 3 shows the master-slave relation with the instruction right before the output of each input defined as a master instruction for each input of the corresponding instruction in regard of each instruction of an instruction train 1. Then the part 3 generates the information that set the weight decided by the base 2 as the master-slave relation information 5 for each master-slave relation. An instruction order setting part 4 repeats the prescribed instruction order setting processing until. the corresponding candidate assembly 6, becomes empty after the instruction lacking a master instruction is transferred to the candidate assembly from the relation 5 from the assembly 6. Thus a new instruction train is obtained.

Description

[Detailed description of the invention]

0001

[Industrial Application Field] The present invention is an optimization method for optimizing the instruction execution order of a program in a computer, and in particular, for optimizing to reduce pipeline breaks when executed by a computer having a parallel processing function using a pipeline. The present invention relates to a program optimization processing device.

0002

[Background Art] The process of modifying a program's instruction sequence so that it can be executed efficiently in a computer is known as optimization process.In an optimization routine such as a compiler, an invariant expression in a program loop is Optimizations such as reducing the number of steps in the repetitive part and deleting common expressions are often performed.

0003

[Problem to be Solved by the Invention] Although it is possible to reduce the number of steps using the conventional optimization described above, when a program is executed on a processor that performs pipeline processing, the same meaning (processing result) can be achieved. ), the pipeline flow differs depending on the instruction execution order, resulting in a large difference in performance.

That is, when, for example, subsequent instructions that use the output of a preceding instruction as input are passed into a pipeline in close proximity to each other, control allows the subsequent instruction to wait for the completion of the preceding instruction in the middle of the pipeline. A so-called pipeline break occurs, and the progress of subsequent instructions is suppressed for several cycles of the pipeline.

Therefore, in such a case, if there is an appropriate instruction unrelated to the execution of the preceding instruction, the execution order may be changed so that the instruction is inserted between the preceding instruction and the subsequent instruction. This eliminates stagnation in the pipeline flow and reduces execution time. However, optimization that takes such pipeline characteristics into consideration has not been performed in the past.

The object of the present invention is to provide a program optimization processing device that changes the execution order of instruction sequences so as to optimize execution by a processor that performs pipeline processing.

[0007]

Means for Solving the Problems FIG. 1 is a block diagram showing the configuration of the present invention. The figure shows the configuration of a program optimization processing device, which includes an inter-instruction weight database 2, a dependency relationship analysis section 3, and an instruction ordering section 4 in the process of optimizing the instruction order of an instruction sequence 1 constituting a program. establish.

[0008] The inter-instruction weight database 2 holds information representing, as a predetermined weight value, the length of a pipeline break that is expected when the two instructions are successively executed, for each sequence of various required two instructions. do.

The dependency analysis unit 3 indicates the parent-child relationship for each instruction in the instruction sequence 1 for each input of the instruction, with the instruction immediately before outputting each input as the parent instruction, and for each parent-child relationship, Information in which weights determined from the inter-instruction weight database 2 are set is generated as parent-child relationship information 5.

After moving the instruction without a parent instruction from the parent-child relationship information 5 to the candidate set 6, the instruction ordering unit 4 repeats the instruction ordering process until the candidate set 6 is empty, and creates a new instruction sequence 7. generate.

In the first invention, the instruction ordering process removes one of the instructions with the smallest weight from the candidate set 6 and outputs it to a new instruction sequence 7, which remains in the candidate set 6. If the weight of each instruction is not 0, it is decreased by 1, and then the instructions whose parent instruction no longer exists on the parent-child relationship information are moved from the parent-child relationship information to the candidate set, and the instructions are transferred in the output order. The new sequence of instructions thus arranged is used as an optimization result program.

[0012] In the second invention, a + attribute and a - attribute are provided for each required instruction type, and the above-mentioned first
In the invention instruction ordering process, when selecting the instruction to be output to the new instruction sequence from the candidate set, the order of the instruction with the + attribute is given the highest priority, and the order of the instruction with the - attribute is given the lowest priority. A process of selecting one of the instructions having the minimum weight among the instructions prioritized according to the order is added.

Furthermore, in the third invention, a next instruction relationship is provided between an instruction of a required instruction type and an instruction located next to the instruction in the instruction array of the program, and the first or second In the instruction ordering process of the invention, in the case of selecting the instruction to be output from the candidate set to the new instruction sequence, after outputting the instruction of the instruction type, the relationship between the instruction and the next instruction is successively determined. Add processing to select instructions that have

[0014]

For the required combination of instruction types, machine language instructions executed by a processor generally have arguments designated as several registers or storage areas, each argument being either an input or an output. Here, the term "argument" includes not only those explicitly specified in a machine language instruction but also those implicitly determined, such as a so-called "condition code."

[0015] Here, input refers to an argument whose value has been determined by the execution of another instruction and must be referenced when executing this instruction, and output refers to an argument whose value has been determined as a result of the processing of this instruction. It says the argument.

Therefore, in the instruction sequence of the program,
There are dependencies between instructions depending on the input/output relationship of each instruction,
Any other instruction that has an input argument as its output must always be executed first, and as long as this dependency is maintained, the meaning of the instruction sequence (processing result) will not change even if the execution order of the instructions is changed. ) generally remains unchanged.

Therefore, the program optimization processing device of the present invention creates parent-child relationship information indicating the dependence relationship between instructions for a given program, and adjusts the execution order while maintaining the parent-child relationship. Optimize pipeline breaks to minimize pipeline breaks by changing .

For this purpose, the first
An inter-instruction weight database is provided that indicates, as a weight, the length of a pipeline break caused by the second type of instruction when the second type of instruction is executed following the second type of instruction. A weight is assigned to each of the above-mentioned parent-child relationships.

In the optimization ordering process, taking into consideration that the weight can be reduced by inserting other instructions with no parent-child relationship between the instructions, the instructions are rearranged so that the sum of the weights is minimized. , optimize the execution time of pipeline processing.

[0020]

[Example] For example, the read command is changed to “read r1,
``data1'' is an instruction to input the storage area at address data1 and read data into the output register r1.
Consider the case of executing an instruction.

[0021] The write command is
r1, data2'', the data in the input register r1 is written to the output storage area data2. If the line break occurs for example one cycle time, then
w in combination from read instruction to write instruction
For example, assume that the weight of the rite command is "1".

The inter-instruction weight database 2 in FIG. 1 contains necessary combinations of instruction types, such as read and write.
, if there is an instruction such as move, the weight in the case of read→write is 1read→mo
Information representing the weight of subsequent instructions is prepared for all necessary sequences of two types of instructions, such as weight 0 in the case of ve, weight 1 in the case of write→read, and so on. Therefore, if the pipeline configuration, control method, etc. of the processor differ, the weight values will generally differ.

The dependency analysis unit 3 in FIG. 1 shows the parent-child relationship for each input of the instruction in the instruction sequence 1 by setting the instruction immediately before outputting the input as the parent instruction, and calculates this parent-child relationship. For each command, information in which a weight determined from the inter-instruction weight database 2 is set is generated as parent-child relationship information 5.

FIG. 2 shows an example of the processing flow of the dependency relationship analysis unit 3, in which it is assumed that all instructions in the instruction sequence 1 are identified in processing step 10 and sequentially processed from the beginning, and one instruction is processed in processing step 11. Take it out.

In processing step 12, all inputs of arguments determined by the instruction type are sequentially processed, and in processing step 13, one input is picked up. Identification is made in processing step 14, and a recent instruction whose output argument is the same as the input being taken is searched for while sequentially going back to the instructions preceding the instruction. That is, in processing step 15, the previous instruction is extracted, and in processing step 16, it is determined whether the same input as the current processing target is specified as the output, and if there is no matching output, the process returns to processing step 14 and another instruction is executed. Perform the above processing for the previous instruction.

If there is an instruction whose output matches the input,
Proceeding to processing step 17, an arc is set with the instruction that has the output as the parent and the instruction currently being processed as the child, and in processing step 18, the instruction type of the parent instruction and the instruction type of the child instruction are used as keys to create an arc between instructions. After setting a weight to the arc by searching the weight database 2 and generating the parent-child relationship information 5, the process returns to step 12.

In the case of the second and third inventions, the dependency relationship analysis unit 3 determines the attributes of the next instruction relationship for a specific instruction type;
+ attribute and - attribute information are held, and if the instruction type of the processed instruction corresponds to one of the specific instruction types, those attributes are set to the corresponding instruction in the parent-child relationship information 5 in processing step 18. .

Here, the next instruction relationship means that when there is a specific type of instruction, the instruction following that instruction in instruction sequence 1 is
This is an attribute that indicates that the instruction must be ordered so that it will be executed next even after optimization, and when an instruction of an instruction type for which the next instruction relationship is specified is processed, the instruction sequence 1
An arc to the next instruction is provided above, and a predetermined display is provided to indicate that the arc is related to the next instruction.

Specific types of next-instruction relationships include, for example, a skip instruction (an instruction that executes the next instruction or the next instruction based on conditional judgment), and a delay instruction.
There is an ed branch instruction (an instruction with a normal branch function, but the next instruction is executed even when branching).

Furthermore, when a type of command for which +attribute or -attribute is specified is processed, a predetermined display indicating each attribute is displayed for the command in the parent-child relationship information 5. The + attribute is a type of instruction that is more efficient if executed as early as possible, such as an unlock instruction to release a lock for exclusive control, or a cache invalidation instruction to invalidate unnecessary data in the processor's buffer. instructions (sometimes provided to improve the efficiency of cache control in multiprocessor systems), etc. The - attribute, contrary to the + attribute, is a type of instruction that is more efficient if executed as late as possible.
There are lock instructions and the like that execute locks for exclusive control.

The parent-child relationship information 5 generated as described above has a storage area allocated to each instruction in the instruction sequence 1, for example, and each area is provided with a display area for the content of the instruction and a + attribute or - attribute. , a pointer indicating a storage area of a child instruction representing an arc whose parent is the instruction, a weight value in the case of a child instruction, and a display of the next instruction relationship are provided for the number of arcs,
The configuration should include other necessary control information.

The instruction ordering unit 4 processes the parent-child relationship information 5 generated as described above as input, first moves instructions without a parent instruction in the parent-child relationship information 5 to the candidate set 6, and then performs instruction ordering processing on the candidate set. A new instruction sequence 7 is generated by repeating this process until 6 becomes empty.

FIG. 3 is a diagram showing an example of the processing flow of the instruction ordering unit 4. In processing step 20, parent-child relationship information 5 is
is scanned and all instructions without parents are extracted and set as candidate set 6.

Candidate set 6 is identified in processing step 21.
The following process is repeated until the candidate set 6 is empty, and if there is an instruction in candidate set 6, it is determined in processing step 22 whether there is an instruction with an arc related to the next instruction, and if there is, processing step 2 is performed.
3, the instruction is output to the new instruction string 7, and processing step 24
Then, the instructions sequentially connected to that instruction in the next instruction relationship are extracted from the parent-child relationship information 5 and output.

If there is no instruction with an arc related to the next instruction, an instruction with + attribute is selected in processing step 25, and if there is an instruction with + attribute, one instruction with the minimum weight among them is selected in processing step 27. The selected instruction is output to the new instruction string 7 in processing step 28.

[0036] If there is no +attribute command, processing step 2
6 selects an instruction that is not a - attribute, so even if it is a + attribute, -
If there is an instruction that is not an attribute, one instruction is selected and outputted in processing steps 27 and 28 as described above. Also, if only attributes are present, process steps 27 and 28 for those instructions.
select one instruction and output it as described above.

In the above process of outputting an instruction to the new instruction string 7, the immediate child instruction (
(generally there are a plurality of instructions) are identified by arcs, and the number of parent instructions in the control information is simultaneously reduced by one for those child instructions.

After the above, in processing step 29, candidate set 6 is
After subtracting by 1 all the weights of the remaining instructions that are not 0, the parent-child relationship information 5 is calculated in processing step 30.
is scanned, and if any instructions remain, all instructions that have newly lost their parents are moved to candidate set 6, and the process returns to step 21.

By repeating the above processing until there are no more instructions in the candidate set 6 in processing step 21, a new instruction sequence 7 consisting of instructions arranged in output order is obtained as an optimized program.

[0040]

As is clear from the above description, according to the present invention, in program optimization processing in a computer, execution by a processor that performs pipeline processing is
There is a significant industrial effect in that the execution order of a sequence of instructions can be changed and optimized to minimize pipeline breaks.

[Brief explanation of the drawing]

[Figure 1] Block diagram showing the configuration of the present invention

[Figure 2]
Processing flowchart of dependency analysis section

[Figure 3] Flowchart of processing of instruction ordering unit

[Explanation of symbols]

1 Instruction sequence 2 Inter-instruction weight database 3 Dependency analysis section 4 Instruction ordering section 5 Parent-child relationship information 6 Candidate set 7 New instruction sequence

Claims (3)

[Claims] [Claim 1] Instruction sequence (1) constituting the program
In the process of optimizing the order of instructions, an inter-instruction weight database (2), a dependency analysis section (3), and an instruction ordering section (4) are provided, and the inter-instruction weight database (
2) holds information representing, as a predetermined weight value, the length of a pipeline break that is expected when the two instructions are successively executed for each sequence of various two instructions;
The dependency analysis unit (3) indicates the parent-child relationship for each instruction in the instruction sequence (1) by setting the instruction immediately before outputting each input as a parent instruction for each input of the instruction, and calculates the parent-child relationship. For each command, information in which a weight determined from the inter-instruction weight database (2) is set is generated as parent-child relationship information (5), and the instruction ordering unit (4) assigns instructions without the parent instruction to the parent-child relationship information. After moving from (5) to candidate set (6), the instruction ordering process is repeated until the candidate set becomes empty to generate a new instruction sequence (7). 6), remove one of the instructions with the minimum weight from the candidate set and create the new instruction sequence (7).
and the weight is 0 for each instruction remaining in the candidate set.
If not, after decrementing by 1, the instructions whose parent instruction no longer exists on the parent-child relationship information are moved from the parent-child relationship information to the candidate set, and the new instruction sequence in which the instructions are arranged in the output order is created. A program optimization processing device, characterized in that it is configured to produce an optimization result as a program. [Claim 2] For each required instruction type, +
attributes and - attributes are provided, and the instruction ordering process (4) gives the highest priority to the order of the instructions with the + attributes when selecting the instructions to be output to the new instruction sequence from the candidate set (6). , the program optimization processing device according to claim 1, wherein the order of the instruction in the - attribute is set to the lowest position, and one of the instructions having the minimum weight is selected from among the instructions prioritized according to the order. . 3. A next-instruction relationship is established between an instruction of a desired instruction type and an instruction located next to the instruction in the instruction array of the program, and the instruction ordering process (4) is performed in accordance with the candidate set ( 6) In the case of selecting the instruction to be output to the new instruction sequence, after outputting the instruction of the instruction type,
3. The program optimization processing device according to claim 1, further comprising selecting an instruction having a relationship between the instruction and the next instruction.