JPH1196018A - Compiling device, its method and computer-readable recording medium recording compiling execution program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To execute instruction scheduling considering of a by-pass and to optimize the use of the by-pass on a confluent point of a control flow graph. SOLUTION: In the compiling device, an intermediate code conversion part 14 converts a VLIW instruction string e.g. inputted from a source program input part 12 into an intermediate code instruction string. An instruction scheduling part 16 prepares a control flow graph for the instruction string converted into the intermediate code and generates an extended resource reservation table 18 extended by registering by-pass information for specifying a by-pass for reading out an operation number and a source operand in a writing part of a resource reservation table in each reference block of the control flow graph. An assembly code conversion part 20 converts an instruction including by-pass specification information into an assembly code based on the operation number and the by-pass information registered in the table 18.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a compiling apparatus and method for compiling a program used in a processor which processes instructions by a pipeline, and a computer-readable recording medium on which a compiling execution program is recorded.

[0002]

2. Description of the Related Art In recent years, VLIW instructions are executed in parallel by pipeline processing in a drawing processor or the like in order to execute a huge number of geometric transformation processes performed on a pixel basis at a high speed. FIG. 22 shows a VLIW instruction executed by the parallel pipeline processing. One VLIW instruction 1 is, for example, four instruction elements 2 operating in parallel.
A, 2B, 2C, and 2D. Each instruction element 2A to 2D has a length of, for example, 30 bits. VLIW
The positions of the instruction elements 2A to 2D of the instruction 1 are called slots, and are represented by slots A, B, C, and D.

[0003] Four instruction elements 2A to 2D included in one VLIW instruction 1 are supplied to a 4-parallel VLIW pipeline operation unit 3 and are simultaneously executed. FIG.
This is the flow of the pipeline by the 4-parallel VLIW pipeline operation unit 3, taking continuous VLIW instruction 1, VLIW instruction 2, and VLIW instruction 3 as an example. Here, the pipeline stage, for example, slot A and slot C
D, E1, E21, W, and slot B is D, E,
N, W, and slot D is D, E, R, W, which depends on the instruction element, but is initially D which decodes the instruction.
This stage is a stage, and the last stage is a W stage for writing to a register, with two operation stages between them.

A VLIW instruction sequence (source program) executed by such a four-parallel VLIW processor, when converted into assembly code by a compiler, increases the instruction level parallelism by rearranging the instructions in the program. In order to improve the execution speed, the instruction scheduling of the VLIW processor is performed as follows. The target program is converted into a VLIW operation sequence.

[0005] Instruction scheduling is performed for a sequence of VLIW operations. A VLIW instruction is created from the result of the instruction scheduling. When such instruction scheduling is performed, FIG.
The resource reservation table shown in FIG. The resource reservation table is
It has a first list 100A and a second list 100B. First
In the list 100A, for the value% r of the source operand, an operation number is registered in the register write end cycle in the execution cycles n + 0, n + 1, n + 2,.

The second list 100B stores the register write values of the slots A to D corresponding to the respective instruction elements of the VLIW instruction in the register write end cycle of the preceding instruction registered in the first list 100A. Register the operation number of the instruction to be used as the value of. VLIW instruction 1 in the resource reservation table of FIG.
3 are represented by, for example, the assembly code of FIG. VLIW instructions 1 to 4 using this assembly code
The meaning of 3 is as shown in FIG. In addition, VLIW instructions 1 to 3 in FIG. 24 are only instruction elements of slot B and do not use slots A, C, and D, and therefore store a non-operation instruction "nop".

[0007]

However, in such pipeline processing by the conventional VLIW processor, as is apparent from the flow of the pipeline in FIG. 23, a certain VLIW instruction results in a preceding VLIW instruction. Is used as the value of the source operand, the next VLIW instruction cannot be input to the pipeline unless the register write cycle that is the W stage of the preceding VLIW instruction is completed. Has occurred.

In order to solve this problem, the present inventors have proposed a processor having a software bypass control mechanism. A processor having a software bypass control mechanism has a feature that, in order to simplify hardware, a software specifies a value of a source operand of a VLIW instruction from a register or a plurality of bypass outputs. It is.

In the processor having this architecture, it is necessary to explicitly specify the method of bypassing or reading the value of the source operand of each instruction from the register in the assembly code in consideration of the timing of the pipeline. Also, when performing instruction scheduling of a VLIW operation for a processor having a software bypass control mechanism, information on which cycle output which register value to which instruction in which cycle is required.

In a compiler, a control flow graph is generally created and instruction scheduling is performed for each basic block. However, in a processor having a software bypass control mechanism, a plurality of control flow graphs are set at a junction of the control flow graph. The problem arises as to how to determine the register bypass designation of the instruction using the register value defined by the preceding basic block.

Further, since the control flow graph is generally a directed circulation graph, it may not be possible to refer to the resource reservation table of the preceding basic block when performing instruction scheduling of the basic block at the junction. The present invention has been made in view of such a problem, and enables an instruction scheduling considering a bypass for a processor having a software bypass control mechanism by using an extended resource reservation table. It is an object of the present invention to provide a compiling apparatus and method for optimizing use of a bypass at a junction of a control flow graph by determining a block scheduling order, and a computer-readable recording medium recording a compile execution program.

[0012]

FIG. 1 is a diagram illustrating the principle of the present invention. First, according to the present invention, as shown in FIG. 1A, for example, a plurality of instruction elements obtained by dividing a VLIW instruction are executed in parallel by pipeline processing, and in this pipeline processing, the operation result of the preceding instruction is written in a register. A processor with a bypass control mechanism that outputs to a bypass to be used as a source operand of a subsequent instruction, and explicitly specifies in assembly code whether to read a source operand of each instruction from a register or one of a plurality of bypass outputs. Provide a compiling device to be executed by.

As shown in FIG. 1B, the compiling apparatus according to the present invention comprises a source program input unit 1 for inputting a source program which is an instruction sequence described by, for example, a VLIW instruction.
2. An intermediate code conversion unit 14 that converts an instruction sequence input at the source program input unit 12 into an instruction sequence of an intermediate code, and creates a control flow graph of the instruction sequence converted into the intermediate code as shown in FIG. The extended resource reservation table 18 extended by registering bypass numbers for specifying bypasses for reading the operation number and the source operand in the write portion of the resource reservation table for each basic block of the control flow graph.
, An assembly code conversion unit 20 that converts an instruction including bypass designation information into assembly code based on the operation number and bypass information of the extended resource reservation table 18 created by the instruction scheduling unit 16, and an assembly Code conversion unit 20
And an assembly code output unit 22 for outputting the assembly code of the instruction sequence converted in the above as a target program 24.

As shown in FIG. 1C, the extended resource reservation table 18 generated by the instruction scheduling unit 16 stores the operation number and the operation result for each execution cycle for the value% r of the source operand. It has a first list 18A for registering a set and a second list 18B for registering bypass information obtained from the first list 18A together with an operation number for each execution cycle for the slot B corresponding to each instruction element of the VLIW instruction.

The instruction scheduling unit 16 is configured as shown in FIG.
As shown in (D), for example, a trace (CDF) is selected from a set of basic blocks for which scheduling has not been completed in the control flow graph, and is set as a scheduling target set T (CDF). . Trace (CD ・ D ・
If there are basic blocks A and B that have edges a2 and b that join F) and scheduling has not been completed, these basic blocks A and B are traced (CDD).
F) in addition to the scheduling target set T (CD
F · A · B) and the scheduling target set T (C · C
The basic block is scheduled for each of DFAB.

The instruction scheduling unit 16 is used to avoid a case where the resource reservation table of the preceding basic block cannot be referred to for a plurality of basic blocks included in the scheduling target set T. A basic block for which scheduling of a basic block has been completed but its own scheduling has not been completed. A basic block which has a basic block for which scheduling has been completed for the preceding basic block and has the least number of preceding basic blocks for which scheduling has not been completed. The block and are sequentially selected to repeat the basic block scheduling.

The instruction scheduling unit 16 includes a set T to be scheduled, for example, a set T (CDFAA.
For the plurality of basic blocks included in B), the instruction scheduling of the plurality of basic blocks B and C immediately before the basic block D at the merge point has been completed in order to optimize the merge point of the control flow graph. In this case, scheduling is performed with reference to the extended resource reservation table 16 of the basic block D at the junction.

In the scheduling of the basic block D at the junction, if an operation using the register value defined by a plurality of preceding basic blocks B and C exists in the basic block D at the junction, By generating a move instruction between registers in an empty slot of the block B or C, the timing of bypass at the entrance of the merging basic block D is adjusted. If the timing of bypass cannot be adjusted, the value of the operand is changed. Schedule to read from register.

The instruction scheduling unit 16 performs a basic operation on a plurality of basic blocks included in the scheduling target set T, for example, the basic blocks A, B, C, D, and F, in order to optimize the control flow graph junction. If the instruction scheduling of a plurality of basic blocks B and C preceding the block D is not completed, an operation using an operand defined by a basic block before the preceding basic blocks B and C whose instruction scheduling has not been completed. Is scheduled to be executed after the cycle in which writing to the register is completed.

Here, "a basic block before any basic block X" means a basic block X and a basic block whose control reaches the basic block X. Therefore, the basic blocks before the preceding basic blocks B and C mean the basic blocks A, B, C, D and F. Basic blocks D and F
Is included because the basic block F becomes the preceding basic block for the basic block D due to the formation of the loop, and the basic block D becomes the preceding basic block for the basic block F.

For writing to the other registers, a move instruction between registers is generated in an empty slot of the preceding basic block B or C, so that the bypass timing at the entrance of the basic block D at the junction is adjusted. If you ca n’t match the bypass timing,
Schedule the operand value to be read from a register.

The present invention also provides a compiling method executed by a processor having a software bypass control mechanism. This compiling method includes a source program input step of inputting an instruction sequence described by an instruction from a source file; an intermediate code conversion step of converting the instruction sequence input in the source file input step into an intermediate code instruction sequence; A control flow graph of the instruction sequence is created, and in a basic block unit of the control flow graph, an operation number and bypass information for specifying a bypass for reading a source operand are registered in a write portion of the resource reservation table, and an extended resource reservation table is registered. And an assembly code conversion step of converting an instruction including bypass designation information into an assembly code based on the operation number and the bypass information of the extended resource reservation table 18 created in the instruction scheduling step. The details of this method are the same as those of the apparatus.

An assembly code output step of outputting an assembly code of the instruction sequence converted in the assembly code conversion step is provided. Thus, according to the present invention, for a processor having a software bypass control mechanism,
By using the extended resource management table, instruction scheduling in consideration of bypass can be performed.

According to the present invention, the use of the bypass at the junction of the control flow graph, which is a problem unique to the processor having the software bypass control mechanism, is controlled for the processor having the software bypass control mechanism. By determining the order of scheduling the basic blocks of the flow graph, it is possible to perform the scheduling efficiently.

Further, according to the present invention, a plurality of instruction elements obtained by dividing an instruction are executed in parallel by pipeline processing,
In pipeline processing, the operation result of the preceding instruction is output to a bypass before being written to a register and can be used as a source operand of a subsequent instruction, and the source operand of each instruction is read from a register or one of a plurality of bypass outputs. Provided is a computer-readable recording medium that stores a compile execution program that compiles an instruction sequence to be executed by a processor having a bypass control mechanism that explicitly specifies the above in an assembly code.

A computer-readable recording medium on which the compile execution program is recorded has a saw program input unit for inputting a source program of an instruction sequence described by a VLIW instruction, and an instruction sequence input on the source program input unit. An intermediate code conversion unit for converting the instruction sequence into a code instruction sequence, and a control flow graph for the instruction sequence converted into the intermediate code, and an operation number and An instruction scheduling unit for registering bypass information specifying a bypass for reading a source operand to generate an extended resource reservation table, and including bypass information based on the operation number and bypass information of the extended resource reservation table created by the instruction scheduling unit Assembly to be converted to instruction assembly code Wherein the over de conversion unit, and the assembly code output unit for outputting the object program of the converted instruction sequence in assembly code conversion unit, further comprising: a.

[0027]

FIG. 2 is a functional block diagram of a compiling device according to the present invention. The compiling device of the present invention includes a source program input unit 12, an intermediate code conversion unit 1,
4, an instruction scheduling unit 16, an assembly code conversion unit 20, and an assembly code output unit 22.
The source program input unit 12 inputs the source program 10 written in a programming language such as C language.

That is, the source program 10 written in the programming language is divided into words called tokens, and the validity of the words is checked. The source program for which the validity of the programming language has been checked by the source programming input unit 12 is converted into an intermediate code by the next intermediate code conversion unit 14. The return to the intermediate code by the intermediate code conversion unit 14 is executed in the following procedure.

The source program is divided into tokens. Parse a sequence of tokens. That is, it checks whether or not it conforms to the grammar of the programming language. If the sequence of the tokens is correct, an intermediate code representing the meaning is generated based on the result of the syntax analysis.

The source program converted into the intermediate code is output to the instruction scheduling section 16. According to the present invention, in this instruction scheduling, a control flow graph is generated to determine the execution procedure of the source program. Further, in the compiling apparatus of the present invention, execution by a processor having a bypass control mechanism that explicitly specifies in assembly code whether to read the value of the source operand of an instruction from a register or one of a plurality of bypass outputs Compiles the VLIW instruction sequence
A process is performed to generate an extended resource reservation table 18 in which functions of the resource reservation table used for compiling the conventional VLIW instruction sequence are extended.

The extended resource reservation table 18 is obtained by creating a control flow graph of an instruction sequence converted into an intermediate code,
In the write portion of the resource reservation table for each basic block of the control flow graph, in addition to the conventional operation number, in the present invention, bypass information for specifying a bypass for newly reading the value of the source operand is registered and expanded. A resource reservation table is created.

When the extended resource reservation table 18 for each basic block unit in the control flow graph created for the instruction sequence of the source program converted into the intermediate code by the instruction scheduling unit 16 is completed, the next assembly code conversion unit 20 In the instruction scheduling unit 16
Is converted into an assembly code of a VLIW instruction including bypass designation information based on the operation number and bypass designation information of the extended resource reservation table 18 created in step (1).

Finally, the assembly code output unit 22 converts the intermediate code into a target program 24 which is converted into an assembly code executable by a processor having a software bypass control mechanism as a target. Output to media etc.
Next, a description will be given of a processor having a software bypass control mechanism to which the compiling device and method of the present invention are applied.

FIG. 3 is a diagram showing software and software to which the present invention is applied.
FIG. 4 is a block diagram of a processor having a bypass control mechanism, which includes an instruction execution unit 26, a bus unit interface 28 functioning as an input unit, a code RAM 30 storing a source program of a compiled VLIW instruction sequence, and a bus functioning as an output unit Unit interface 3
It consists of two.

The instruction execution unit 26 executes, for example, a geometric transformation process, and has a 4-parallel VLIW instruction execution format. The instruction execution unit 26 includes a 16-entry 32-bit integer register 40, a 32-entry 32-bit floating-point register 38, 42, a 32-bit floating-point arithmetic pipeline 44, 46, 52, 54, and a 32-bit integer arithmetic pipeline. 48, a 16-bit adder 50 for address calculation. Further, it has two separate data RAMs 34-1 and 34-2.
Load / store to M34-1 and M4-2 can be performed in parallel with a 64-bit width.

The VLIW instruction executed by the processor having the software bypass control mechanism shown in FIG. 3 is constituted by dividing one VLIW instruction 1 into four instruction elements 2A to 2D as shown in the conventional example of FIG. The position of each of the elements 2A to 2D is called a slot, which is called a slot A, a slot B, a slot C, and a slot D, respectively. The four instruction elements 2A to 2D included in one VLIW instruction 1 execute simultaneously. Is done.

In the four-parallel VLIW architecture of the processor shown in FIG. 3, a plurality of types of instruction elements are defined in advance, and each instruction element can be divided into several instruction categories according to the operation contents. The instruction categories include, for example, a floating-point operation instruction, a floating-point proportional instruction, a floating-point conversion instruction, an integer operation instruction, an integer comparison instruction, a load / store instruction, a branch instruction, an FR transfer instruction, an IR transfer instruction, a control instruction, and a nop. Divided into instructions.

The positions of slots A to D in which instruction elements belonging to each category can be arranged are fixed. For example, in slot B, only integer operation instructions, integer comparison instructions and load / store instructions can be placed. It cannot be placed in another slot. The processor provided with the software bypass control mechanism to which the compiling device of the present invention is applied is characterized in that the operation at the pipeline level of the instruction is included in the definition of the architecture. In other words, it is not possible to write a correct VLIW instruction program without understanding the pipeline operation. Almost all instructions process by inputting some data as the value of the source operand, and output the result.

In a processor with a software bypass control mechanism to which the present invention is applied, in the definition of the pipeline level of an instruction, not only the processing content but also the input and output of each pipeline stage in each instruction are performed. Has been determined. In addition, the input source and output destination of data are not limited to storage areas such as register files and memories.A bypass is provided to use the operation result of the preceding instruction as the source operand of the subsequent instruction before writing the register. Or output the operation result to the bypass. That is, in the processor targeted by the present invention, the bypass must be regarded as one resource.

FIG. 4 shows the flow of the pipeline by the pipeline operation of the processor with the software bypass control mechanism of FIG. Each of the four instruction elements constituting one VLIW instruction executes necessary processing in a plurality of steps. Each of the divided steps is a pipeline stage, and one pipeline stage is executed in one cycle.

Each pipeline stage in slots A to D has a name. For example, slot A and slot C
Are D, E1, E2, W, and slot B is D, E, E
N, W, and slot D is D, E, R, W. As described above, the pipeline stages are slightly different depending on the type of the instruction for the slot, but for any type of instruction, the first pipeline stage is the D stage for instruction decoding, and the last is the W stage for register writing. Two operation stages are provided.

As is apparent from the flow of the pipeline in FIG. 4, for example, four instruction elements included in the first VLIW instruction 1 are simultaneously input to the D stage in cycle n + 0. After proceeding with cycle n + 1 and cycle n + 2, the final stage of the W stage for register writing is finally provided in cycle n + 3. VLIW instruction 1
, The next VLIW instruction 2 is always continuous in a cycle, and is input to the D stage at cycle n + 1. The same applies to the following VLIW instruction 3, VLIW instruction 4, VLIW instruction 5, .... Therefore, there is a gap of four stages between the successively executed VLIW instructions 1, 2, 3, 4,... As in the flow of the pipeline of the conventional processor shown in FIG. Without
Accordingly, instructions can be executed at high speed.

FIG. 5 shows the operation block of slot B in the processor of FIG. 3, and includes an integer operation pipeline 48, a data RAM block 34 representing a data RAM to be loaded / stored, a floating point register 38, and an integer. It comprises a register 40. The result calculated by the integer operation pipeline 48 is output to an output path 48a, an E bypass 48b, an N bypass 48c, a W bypass 48d, and an address path 48e in accordance with prescribed timing.
Is output to The output path 48a becomes write data to the integer register 40, and the E bypass 48b and the N bypass 4
8c and W bypass 48d are candidates for source operands as bypasses. The value of the address path 48d is notified to the data RAM block 34 as address information.

The integer operation pipeline 48 takes two source operands, each of which has a source operand 60A,
Grouped like 60B. Source operand 6
As candidates for 0A, there are an input path 40a from the integer register 40, an E bypass 48b, an N bypass 48c, a W bypass 48d, and a load bypass 64, and one of these is selected as the source operand 60A.

As candidates for the source operand 60B, there are an input path 40b from the integer register 40, an E bypass 48b, an N bypass 48c, a W bypass 48d, a measurement path 62, and a load bypass 64, and one of these is one of them. Selected as source operand 60B. FIG.
Is an integer operation instruction, an integer proportional instruction, or a load / store instruction. FIG. 6 shows an integer operation instruction among them.
It is executed in four pipeline stages of E, N and W. That is, the source operand is read in the D stage,
The stage outputs the operation result to the E bypass 48b, the N stage outputs the operation result to the N bypass 48c, and finally the W stage outputs the operation result to the W bypass 48d.
In addition, the operation result is written into the integer register 40. This point is basically the same for the integer comparison instruction and the load / store instruction.

FIG. 7 is a flowchart of the overall processing operation of the assembly apparatus according to the present invention of FIG. 2 executed by a processor having the software bypass control mechanism shown in FIG. Steps S1 to S in this flowchart
5 corresponds to the processing functions of the source program input unit 12, the intermediate code conversion unit 14, the instruction scheduling unit 16, the assembly code conversion unit 20, and the assembly code output unit 22 in the functional blocks in FIG.

FIG. 8 shows details of the instruction scheduling of the intermediate code shown in step S3 of FIG. 7. A control flow graph is created from the intermediate code, and a process of generating a set of blocks to be scheduled for instruction scheduling is performed. . In FIG. 8, in the instruction scheduling of the present invention, a control flow graph of the intermediate code is created for the source program converted into the intermediate code in step S1. FIG. 9 is an example of the control flow graph created in step S1 of FIG. 8, and the control flow graph is an effective circulation graph created from the branch portion to the merge portion as one basic block.

In FIG. 9, one of the basic blocks A to J
It is composed of 0 blocks. The branch line of each block to the subsequent basic block is called an edge. For example, the basic block A has edges a1 and a2. The number of executions of the control flow graph is displayed on each of the edges. For example, the number of executions of the edge a1 of the basic block A is 1000 times, and the number of executions of the edge a2 is also 1000 times. Referring again to FIG. 8, if the control flow graph as shown in FIG. 9 is created in step S1, the process proceeds to step S2, where it is checked whether or not there is a basic block that has not yet been scheduled. If there is a basic block that has not been performed, the processing of steps S3 to S8 is repeated.

In steps S3 to S5, a scheduling target set T is generated as a set of basic blocks for performing scheduling. That is, in a normal program, there is a bias in the number of executions of the edge at the time of execution as shown in the control flow graph of FIG. In a processor having a software bypass control mechanism according to the present invention, it is desirable to efficiently generate a VLIW instruction using a bypass between a source block of an edge that is frequently executed and a basic block of a destination.

For this reason, as shown in FIG. 9, the number of executions is obtained for each edge by using the profile information, and the processing of steps S3 to S6 in FIG. repeat. First, step S
In No. 3, a trace T having an edge with a large number of executions is selected from a set of basic blocks not yet scheduled.

In the control flow graph of FIG. 9, for example, the edge block c of the basic block C is 51,000 times, and the edge d2 of the basic block D is 51000 times. A trace T connecting F is selected. Trace T (C, D, F)
It expresses. Next, in step S4, trace T (C, D, F)
Is selected, the basic block not yet scheduled is not included in the trace T (C, D, F), and the succeeding basic block is included in the preceding basic block included in the trace T (C, D, F). Find the set P. As such a set P, the trace T (C, D,
F) has a basic block A and a basic block B, and the set P is represented as a set P (A, B). In other words, the set P is a trace T (C, C,
D, F) can also be referred to as basic blocks A and B having edges a2 and b merging with each other and having not yet completed scheduling.

When the set P (A, B) is obtained in step S4, the process proceeds to step S5, where the set P (A, B) obtained in step S4 is added to the trace T (C, D, F) obtained in step S3. B) is added and the scheduling target set T
´ In this case, the scheduling target set T is T ′
(C, D, F, A, B). Then, step S6
Then, it is checked whether or not there is a basic block which has not been scheduled yet in the set T in step S5, and steps S6, S7, S are performed until the basic block no longer exists.
The processing from step 8 is repeated. Scheduling target set T
After all the basic block scheduling according to steps S6, S7, and S8 for 'is completed, the process proceeds to step S2, and a basic block for which scheduling is to be executed is found in step S6.

In the basic block search in step S7, as shown in FIG. 9, since the control flow graph is generally an effective circulation graph, the resource reservation table of the preceding basic block is used when the instruction scheduling of the basic block at the junction is performed. You may not be able to reference. As described above, in order to reduce the case where the resource reservation table of the preceding basic block cannot be referred to in the instruction scheduling of the basic block at the junction, step S
For a plurality of basic blocks included in the scheduling target set T obtained in 3 to S6, step S7 finds a basic block to be scheduled according to the following priority order.

Priority: a basic block having no preceding basic block. Priority: a basic block for which scheduling of all preceding basic blocks has been completed but its own scheduling has not been completed. Priority: scheduling has been performed for the preceding basic block. Basic blocks having completed basic blocks and having the least number of preceding basic blocks for which scheduling has not been completed. To be more specific, referring to FIG. 9, for example, as a scheduling target set T, T (A, B, C, D, E , F) are generated, the basic block having no preceding basic block corresponding to the priority order is the basic block A.
First, the basic block A is selected and scheduling is performed. As a basic block to be selected next, a basic block B is selected, which is a basic block in which scheduling of all preceding basic blocks indicated by the priorities has been completed but its own scheduling has not been completed. Note that the basic block C is not selected because it has a preceding basic block F for which scheduling has not been completed.

The priority order is a case where a plurality of basic blocks are directly present in a plurality of traces between a branch point and a junction in the control flow graph of FIG. 9, and among the traces existing in parallel, the scheduling is not performed. The scheduling is performed by finding the basic block of the trace with the least number of unfinished preceding basic blocks. By performing the instruction scheduling of the basic block in the order of the instruction scheduling in step S7 of FIG. 8, that is, the above-described priority order, it is possible to reduce the case where the resource reservation table of the preceding basic block cannot be referred to.

Further, in the processing of FIG. 7, the state of the basic block at the junction of the control flow graph is optimized in order to optimize the junction of the control flow graph of FIG. If there is a preceding basic block for which instruction scheduling has not been completed, the processing is divided into the following two cases.

First, in the case where all the instruction scheduling of the preceding basic block has been completed, the scheduling of the basic block at the junction is performed with reference to the resource reservation table of the preceding basic block. For example, in the basic block D at the junction shown in FIG. 9, when the instruction scheduling of the preceding basic blocks A, B, and C has all been completed, the scheduling of the basic block D at the junction is performed by using the resource reservation table of the preceding basic block. To do.

In this case, if there is an operation in the basic block D at the merging point using the values of the registers defined by the plurality of preceding basic blocks B and C, if possible, an empty slot of the preceding basic block B or C is used. , The bypass timing is adjusted at the entrance of the junction of the basic block D. FIG. 10 shows instruction slots of two preceding basic blocks B and C with respect to the basic block D at the junction in FIG. 9. In the slot 64 at the entrance of the basic block D at the junction,
The register value of the source operand of the slot 60 of the preceding basic block B and the register value of the source operand value% r1 of the slot 62 of the preceding basic block C are used.
As a result, the timing is shifted from the slot 62 of the basic block C.

In such a case, as shown in FIG. 11, by generating an inter-register move instruction in the empty slot 66 of the basic block B, the bypass timing at the entrance of the basic block D at the junction is adjusted. In this case, if the timing of the bypass cannot be adjusted by generating an inter-register move instruction for an empty slot, scheduling is performed so that the value of the source operand is read from the register.

Next, a description will be given of the processing in the case where there is a preceding basic block for which instruction scheduling has not been completed for the basic block at the junction of cases. For example, in the control flow graph of FIG. 9, if there is a preceding basic block C for which the instruction scheduling has not been completed for the basic block D at the junction, a register by an instruction before the preceding basic block C for which the instruction scheduling has not been completed is stored. It is necessary to guarantee that the value of the register is read after the writing of the register is completed.

Therefore, the operation using the source operand defined by the basic block before the preceding basic block C in which the instruction scheduling is not completed is performed after the cycle in which the writing to the register by the basic block before the basic block C is completed. The basic block D at the junction is scheduled to be executed. For writing to the other registers, the timing of bypass is adjusted in the same manner as in the case where the instruction scheduling of the preceding basic block in the case has already been completed.

Next, an extended resource reservation table is created for each of the basic blocks in step S8 of FIG.
Processing for generating a VLIW instruction from the operation number and bypass information of the extended resource reservation table will be described. First, generation of the extended resource reservation table will be described. Now, as an example, consider the instruction scheduling of the instruction sequence of the slot B indicated by the operation numbers OP1, OP2, and OP3 as shown in FIG. The content of the instruction sequence in slot B is the same as the instruction content shown in FIG. A pipeline cycle when the instruction sequence in slot B of FIG. 12 is executed by the processor with the software bypass control mechanism of FIG.
It looks like 3.

That is, for slot B of the VLIW instruction 1, in cycle 1, cycle 2, cycle 3, and cycle 4, the process proceeds to pipeline stages D, E, N, and W, and E,
The bypass output is performed in each of N and W. For slot B of VLIW instruction 2, cycle 2,
The pipeline stages D, E, N, and W are performed at 3, 4, and 5, respectively. Further, in the VLIW instruction 3 of the operation number OP3, the pipeline stages D, E, N, and W are set in cycles 3, 4, 5, and 6, respectively. The flow of this pipeline,
FIG. 14 shows a pipeline flow when executing an instruction including a case where a bypass output is selected as a source operand.

In FIG. 14, first, in the cycle n + 0, the VLIW instruction 1 is input to the D stage of the slot B and decoded, and in the next stage E of the cycle n + 1, the operand value% r2 is output to the bypass E as an operation result. Is output. In this cycle n + 1, at the same time, VLIW
The instruction 2 is input to the D stage, and the operation of the VLIW instruction 2 selects the operand value% r2 output to the bypass E.

In the next cycle n + 2, VLIW
Instruction 1 outputs an operation result to bypass N as an N-stage operation. At the same time, in cycle n + 2,
The operation result of VLIW instruction 2 is operand% in bypass E
Output as r3. Further, in the cycle n + 2, the VLIW instruction 3 is input to the D stage, and
Operand% r output from bypass N of LIW instruction 1
2 and the VLIW instruction 2 select and read the operand% r3 output to the bypass E.

V in slot B as shown in FIG.
The assembly code by the compiler of the present invention for explicitly specifying the reading of the value of the source operand from the bypasses E and N in the LIW instructions 1, 2, and 3 is shown in FIG.
(A). The contents of the assembly code explicitly specifying whether to bypass or read the value of the source operand from the register in FIG.
(B).

First, the slot B of the VLIW instruction is obtained by adding the source operands% r0 and% r1 of the register R to% r0.
It is an instruction to be 2. In this case, there is no reading of the source operand from the bypass. In the next VLIW instruction 2, the source operand% r0 output to the bypass E by the VLIW instruction 1 is read, and the measured value A is added.
3. In the next VLIW instruction 2,
The source operand% r2 of the bypass N output by the operation of the VLIW instruction 1 and the source operand% r2 of the bypass E output by the operation of the VLIW instruction 2 are read and added to obtain% r2.

In order to generate such an assembly code including the bypass selection information of FIG. 15A, the assembly code is processed in the order of FIGS. 16, 17 and 18, and finally the extended resource reservation table as shown in FIG. Is generated for each basic block. FIG.
Are the first list 18A and the second list 1
8B. In this extended resource reservation table, the instructions of the second list 18B are registered and the first list 18A is registered in the following procedure.
Update the output part of.

If the instruction i can use the slot S in the cycle X, and the operand used by the instruction exists in the cycle X of the first list 19A serving as the output list, the instruction i is stored in the second list 18B. Register in slot S in cycle X. The output of executing instruction i on slot S of cycle X is described in the first list.

The creation of the Zhang resource reservation table is specifically described as follows. FIG. 16 shows the first list 18A and the second list 18B of the extended resource reservation table before the start of the schedule. In this case, the operation number is undefined, there is no bypass information E, N, W, and the operands% r0,
Since% r1 is the register output R, the first list 1
Output to 8A (?,

R), (?,

R) is described. FIG. 17 shows a VLIW instruction 1 for the extended resource reservation table in cycle n + 0.
And updating of the output part, and the operation OP1
Since slot B is empty at cycle n + 0 and source operands% r0 and% r1 can be read from the register, V
LIW instruction 1 can be registered. In this case, since the source operands% r0 and% r1 are not read from the bypass, no bypass information is added.

Subsequently, the output obtained by executing VLIW instruction 1 of FIG.
This is described in List 18A. In this case, the operation number 1 and the bypass information E, N,
W and register output R by final register write
Set of (1,

E) (1,

N) (1,

W) (1,

Register as shown in R). FIG. 18 shows the registration of the extended resource reservation table of the VLIW instruction 2 to be performed subsequently. In this operation number OP2, slot B is vacant in cycle n + 1, and source operand% r2 can be read from bypass E as apparent from first list 18A.
Can be scheduled. This operation number 2
When the second list 18B is registered, the bypass information (% r2,

Stored together with E) and used when generating assembly code. Subsequently, an output obtained by executing the VLIW instruction 1 in FIG. 15 on the slot B in the cycle n + 1 is described in the first list 18A. In this case, the operation number 2 and the bypass information E, which outputs the operation result,
The set of N, W, and the register output R by the final register write is (2,

E) (2,

N) (2,

W) (2,

Register as shown in R). FIG. 19 shows the registration of the extended resource reservation table in the operation of the VLIW instruction 3 in FIG. 14. In the operation number OP3, the slot B is vacant in the cycle n + 2, and as is clear from the first list 18A, Since the source operands% r2 and% r3 can be read from the bypass N and the bypass E, respectively, the cycle n of the second list 18B
+2 slot B can be scheduled.

Subsequently, the output obtained by executing VLIW instruction 3 in FIG.
This is described in List 18A. In this case, the operation number 3 and the bypass information E, N,
W and register output R by final register write
Set of (3,

E) (3,

N) (3,

W) (3,

Registration is performed as shown in R). As described above, the operation number OP3 is stored in the second list 18 of the extended resource reservation table.
B, the operation number OP3 and the bypass information (% r2

N,% r3

E) is saved together and used when generating assembly code. From the extended resource reservation table created as shown in FIG. 19, the VLIW instruction sequence shown in FIG. 15A can be generated as a result. FIG. 20 shows the generation of the extended resource reservation table shown in FIGS. 16 to 19 and the generation processing of the VLIW instruction based on the table, and details the basic block scheduling in step S8 in FIG.

In FIG. 20, first, at step S1, an instruction dependence graph of instructions in the basic block to be scheduled is created. This instruction dependence graph is an effective graph that determines an execution procedure for each instruction. continue,
After clearing CLOCK indicating the number of cycles to 0 in step S2, it is checked in step S3 whether all the instructions in the basic block have been registered in the extended resource reservation table.

If unregistered, the flow advances to step S4 to check whether there is an unregistered instruction i which can be registered in the extended resource reservation table in the cycle indicated by the time CLOCK. If such an instruction i exists, the instruction i is registered by the operation number in the corresponding slot of the cycle specified by the time CLOCK in the extended resource reservation table in step S5. In this case, the source operand is selected from bypass. In this case, the bypass information is also registered at the same time.

If there is no longer any instruction i that can be registered in the extended resource reservation table of the CLOCK at the current time in step S4, the process proceeds to step S6, the time CLOCK is incremented by one, and the process returns to step S3 to return to the next step. The extended resource reservation table is registered in the cycle of the time CLOCK. Step S3
When the registration of all the instructions in the basic block in the extended resource reservation table is completed, the process proceeds to step S7, where the operation number of the registered extended resource reservation table and the bypass information registered at the same time are used as shown in FIG. V like
Generate an LIW instruction.

FIG. 22 shows an embodiment of a computer-readable recording medium on which the compile execution program of the present invention is recorded. The recording medium includes a removable portable storage medium such as a CD-ROM or a floppy disk,
There is a storage device of a program provider that provides a program via a line, and a memory device such as a RAM or a hard disk of a processing device in which the program is installed. The program provided by the recording medium is loaded into the processing device and executed on the main memory.

In the above embodiment, the instruction of the slot B in the processor having the software bypass control mechanism shown in FIG. 3 is taken as an example.
The same applies to C and D. Further, in the above-described embodiment, the compiling for the processor having the software bypass control mechanism of the parallel pipeline configuration for executing the parallel VLIW instruction has been described. Compiling for a processor having a software bypass control mechanism having one pipeline can be applied as it is.

Further, in the above-described embodiment, the compilation of the VLIW instruction is taken as an example, but the present invention is not limited by the form of the instruction.

[0096]

As described above, according to the present invention, by using an extended resource reservation table in which bypass information is added to an operation number for a processor having a software bypass control mechanism, the value of a source operand As a result, instruction scheduling in consideration of bypass can be performed.

According to the present invention, the use of the bypass at the junction of the control flow graph generated at the time of compilation, which is a problem specific to a processor having a software bypass control mechanism, is described in the basic block of the control flow graph. Can be efficiently performed by determining the scheduling order.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating the principle of the present invention.

FIG. 2 is a functional block diagram of a compiling device according to the present invention.

FIG. 3 is a block diagram of a processor having a software bypass control mechanism to which the present invention is directed;

FIG. 4 is a time chart of a flow of a pipeline by the processor of FIG. 3;

FIG. 5 is a block diagram showing an operation part of FIG. 3 for executing an instruction in a slot B;

FIG. 6 is a diagram illustrating the operation of the D, E, N, and W stages of an integer operation instruction executed in slot B of FIG. 5;

FIG. 7 is a flowchart of a compile processing procedure according to the present invention;

FIG. 8 is a flowchart for generating a set of basic blocks in the instruction scheduling process of FIG. 7;

FIG. 9 is an explanatory diagram of a control flow graph generated by compiling according to the present invention.

FIG. 10 is an explanatory diagram of a timing shift in a preceding basic block with respect to the junction in FIG. 9;

FIG. 11 is an explanatory diagram of timing adjustment at the junction entrance in FIG. 9;

FIG. 12 is an explanatory diagram of an assembly code of an instruction sequence before instruction scheduling without bypass control information.

FIG. 13 is a time chart showing bypass selection in a pipeline flow of a processor having a software bypass control mechanism.

FIG. 14 is a time chart showing a pipeline flow at the time of executing the instruction in FIG. 13;

FIG. 15 is an explanatory diagram of an assembly code after instruction scheduling having bypass control information.

16 is an explanatory diagram of an initial state of a resource reservation table used for creating the instruction sequence in FIG.

FIG. 17 is an explanatory diagram of creating a resource reservation table for the VLIW instruction 1 in FIG. 13;

FIG. 18 is an explanatory diagram of creating a resource reservation table for the VLIW instruction 2 in FIG.

FIG. 19 is an explanatory diagram for creating a resource reservation table for the VLIW instruction 3 in FIG. 13;

20 is a flowchart showing details of the scheduling of the basic blocks included in the set generated by the processing in FIG. 8;

FIG. 21 is an explanatory diagram of an embodiment of a computer-readable recording medium recording a compile execution program of the present invention.

FIG. 22 is a VLI executed in four parallel pipeline processing.
Structure explanation diagram of W instruction

FIG. 23 is a time chart of a pipeline flow by a conventional VLIW processor.

FIG. 24 is an explanatory diagram of a resource reservation table used in a compiler for a conventional VLIW processor.

FIG. 25 is a VLI used to create the resource reservation table of FIG. 24;
Explanatory drawing of the assembly code of W instructions 1 to 3 and the contents of the instruction

[Explanation of symbols]

 10: Source program 12: Source file input unit 14: Intermediate code conversion unit 16: Instruction scheduling unit 18: Extended resource reservation table 18A: First list 18B: Second list 20: Assembly code conversion unit 22: Assembly code output unit 24 : Object program 26: Instruction operation unit 28, 32: Bus unit interface 30: Code RAM 34-1, 34-2: Data RAM 38, 42: Floating point register 40: Integer register 44, 46, 52, 54: Floating point Operation pipeline 48: Integer operation pipeline 48a: Output path 48b: E bypass 48c: N bypass 48d: W bypass 48e: Address path 50: Adder 60A, 60B: Source operand 62: Immediate path 64: Load bypass

Claims (13)

[Claims] A plurality of instruction elements obtained by dividing an instruction are executed in parallel by pipeline processing. In the pipeline processing, an operation result of a preceding instruction is output to a bypass before being written to a register, and a source operand of a subsequent instruction is output. Compile to compile an instruction sequence to be executed by a processor with a bypass control mechanism that specifies whether to read a source operand of each instruction from a register or one of the plurality of bypass outputs in an assembly code. A saw program input unit for inputting a source program of an instruction sequence described by the VLIW instruction; an intermediate code conversion unit for converting the instruction sequence input at the source program input unit into an intermediate code instruction sequence; Creating a control flow graph of the instruction sequence converted to the intermediate code An instruction scheduling unit that registers an operation number and bypass information for specifying a bypass for reading a source operand in a write part of the resource reservation table for each basic block of the control flow graph to generate an extended resource reservation table; An assembly code conversion unit that converts an instruction including bypass information into an assembly code based on the operation number and the bypass information of the extended resource reservation table created by the unit; and a target program of the instruction sequence converted by the assembly code conversion unit. And a compiling device for outputting an assembly code. 2. The compiling device according to claim 1, wherein
The extended resource reservation table generated by the instruction scheduling unit includes, for the source operand value% r, a first list for registering a set of bypass information in which an operation number and an operation result are output for each execution cycle, and each instruction of a VLIW instruction. For the slot corresponding to the element, the second information in which the bypass information obtained from the first list is registered together with the operation number for each execution cycle.
And a list. 3. The compiling apparatus according to claim 1, wherein:
The instruction scheduling unit selects a trace from a set of basic blocks for which scheduling has not been completed in the control flow graph, sets the trace as a set to be scheduled, further has an edge joining the trace, and has not completed scheduling. A compiling apparatus, wherein, when a basic block exists, the basic block is added to the trace and included in the set to be scheduled, and a basic block is scheduled for each set to be scheduled. 4. The compiling device according to claim 3, wherein
The instruction scheduling unit, for a plurality of basic blocks included in the scheduling target set, in order to avoid a case where the resource reservation table of the preceding basic block cannot be referred to, a basic block having no preceding basic block, A basic block whose scheduling has been completed but its own scheduling has not been completed; a basic block which has a basic block whose scheduling has been completed as a preceding basic block and has the least number of preceding basic blocks whose scheduling has not been completed; A compiling device for sequentially selecting and repeating scheduling of basic blocks. 5. The compiling apparatus according to claim 1, wherein:
The instruction scheduling unit is configured to complete the instruction scheduling of a plurality of basic blocks preceding the basic block at the junction for the optimization of the control flow graph junction with respect to the basic blocks included in the scheduling target set. In this case, scheduling is performed with reference to the resource reservation table of the basic block at the junction, and in the scheduling of the basic block at the junction, an operation using the value of a register defined by a plurality of preceding basic blocks is performed. If it exists in the basic block at the junction, a move instruction between registers is generated in an empty slot of the preceding basic block to adjust the bypass timing at the entrance of the basic block at the junction, and adjust the bypass timing. If not, the value of the operand Compiling and wherein the scheduling to read from the register. 6. A compiling device according to claim 1, wherein:
The instruction scheduling unit completes instruction scheduling of a plurality of basic blocks preceding the basic block at the junction for optimization of a control flow graph junction with respect to a plurality of basic blocks included in the scheduling target set. If not,
Operations that use operands defined by basic blocks before the preceding basic block for which instruction scheduling has not been completed are scheduled to be executed after the cycle in which writing to the register is completed. Adjusts the bypass timing at the entrance of the basic block at the junction by generating a move instruction between registers in an empty slot of the preceding basic block, and if the bypass timing cannot be adjusted, the value of the operand And compiling a parallel VLIW instruction. 7. A plurality of instruction elements obtained by dividing an instruction are executed in parallel by pipeline processing, and in the pipeline processing, an operation result of a preceding instruction is output to a bypass before being written to a register, and a source operand of a subsequent instruction is written. Compile to compile an instruction sequence to be executed by a processor with a bypass control mechanism that specifies whether to read a source operand of each instruction from a register or one of the plurality of bypass outputs in an assembly code. In the method, a source program inputting step of inputting a source program as an instruction sequence described in the instruction, an intermediate code converting step of converting the instruction sequence input in the source file inputting step into an intermediate code instruction sequence, Create a control flow graph of the instruction sequence converted to the intermediate code. An instruction scheduling step of registering bypass information for specifying a bypass for reading an operation number and a source operand in a write portion of the resource write table for each basic block of the control flow graph to generate an extended resource reservation table; An assembly code conversion step of converting an instruction including bypass designation information into an assembly code based on the operation number and the bypass information of the extended resource reservation table created by the instruction scheduling unit; and an instruction sequence converted by the assembly code conversion unit An assembly code output process of outputting the assembly code of
A compilation method characterized by comprising: 8. The compiling method according to claim 7, wherein:
The extended resource reservation table generated in the instruction scheduling process includes, for the source operand value% r, a first list for registering a set of bypass information for outputting an operation number and an operation result for each execution cycle, and each instruction of a VLIW instruction. For the slot corresponding to the element, the second information in which the bypass information obtained from the first list is registered together with the operation number for each execution cycle.
And a list. 9. The compiling method according to claim 7, wherein:
In the instruction scheduling step, a trace is selected from a set of basic blocks for which scheduling has not been completed in the control flow graph to be a set to be scheduled, and further has an edge joining the trace, and scheduling has not been completed. A compile method comprising, when a basic block exists, adding the basic block to the trace and including the basic block in the set to be scheduled, and scheduling the basic block for each set to be scheduled. 10. The compiling method according to claim 9, wherein the instruction scheduling step is for avoiding a case where a resource reservation table of a preceding basic block cannot be referred to for a plurality of basic blocks included in the set to be scheduled. A basic block having no preceding basic block, a basic block for which scheduling of all preceding basic blocks has been completed but its own scheduling has not been completed, a basic block for which scheduling has been completed for the preceding basic block, and scheduling is not performed. A compilation method characterized by sequentially selecting basic blocks having the least number of unfinished preceding basic blocks and repeating basic block scheduling. 11. The compile method according to claim 7, wherein said instruction scheduling step comprises the steps of optimizing a converging point of a control flow graph for a plurality of basic blocks included in said set to be scheduled. If the instruction scheduling of a plurality of basic blocks preceding the block has all been completed, scheduling is performed by referring to the resource reservation table of the basic block at the junction. If an operation using the register value defined by a plurality of basic blocks is present in the basic block at the junction, a move instruction between registers is generated in an empty slot of the preceding basic block. Adjust the bypass timing at the block entrance to If it is not possible to adjust the grayed may compile wherein the scheduling to read the value of the operand from the register. 12. The compile method according to claim 7, wherein said instruction scheduling step includes the steps of: optimizing a control flow graph junction for a plurality of basic blocks included in said set to be scheduled; If the instruction scheduling of a plurality of basic blocks preceding the block has not been completed,
Operations that use operands defined by basic blocks before the preceding basic block for which instruction scheduling has not been completed are scheduled to be executed after the cycle in which writing to the register is completed. Adjusts the bypass timing at the entrance of the basic block at the junction by generating a move instruction between registers in an empty slot of the preceding basic block, and if the bypass timing cannot be adjusted, the value of the operand Compiling a schedule to read from a register. 13. A plurality of instruction elements obtained by dividing an instruction are executed in parallel by pipeline processing, and in the pipeline processing, an operation result of a preceding instruction is output to a bypass before being written to a register, and a source operand of a subsequent instruction is written. Compile to compile an instruction sequence to be executed by a processor with a bypass control mechanism that specifies whether to read a source operand of each instruction from a register or one of the plurality of bypass outputs in an assembly code. In a computer-readable recording medium on which an execution program is recorded, a saw program input unit for inputting a source program of an instruction sequence described in the VLIW instruction; An intermediate code conversion unit for converting into an instruction sequence; Create a control flow graph of the instruction sequence converted into the intermediate code, and register the operation number and bypass information for specifying the bypass for reading the source operand in the write part of the resource reservation table for each basic block of the control flow graph. An instruction scheduling unit that generates an extended resource reservation table by using the operation number and the bypass information of the extended resource reservation table created by the instruction scheduling unit. A computer-readable storage medium storing a compile execution program, comprising: an assembly code output unit that outputs a target program of an instruction sequence converted by the assembly code conversion unit.