Branch instruction conversion to multi-threaded parallel instructions

A program conversion apparatus, comprising:

• a syntax analysis section for analyzing the syntax of a source program to produce an intermediate program;
• a parallelization section for performing optimization processing including parallelization for the intermediate program;
• and
• a code generation section for producing a target program including an instruction code for a target processor apparatus from the intermediate program optimized by said parallelization section;
• said parallelization section including an intermediate program inputting section for reading in the intermediate program and analyzing a control flow and a data flow, a register allocation section for trying to perform register allocation prior to parallelization to estimate a register allocation situation of variables and intermediate terms of the intermediate program and executing allocation of registers, a fork spot determination section for determining, based on a result of the trial of the register allocation, a spot of a conditional branch portion of the intermediate program to be converted into a parallel code for which a thread creation instruction is used, an instruction reordering section for performing reordering of instructions before and after the parallelization spot from information of the parallelization spot determined by said fork spot determination section, the data flow, and an intermediate program outputting section for outputting the instruction sequence for which the conversion including the parallelization has been completed in a format of the intermediate program again.

A program conversion apparatus for performing optimization processing including parallelization of an intermediate program obtained by a syntax analysis of a source program performed by a syntax analysis section so that the intermediate program may be suitable for a target processor apparatus, comprising:

• register allocation trial means for trying allocation of registers of the target processor apparatus on the intermediate program and obtaining register allocation information prior to actual allocation;
• means for calculating a distance of data dependence generated through a memory in the target processor apparatus for the intermediate program;
• means for determining a fork designation taking the distance of data dependence through a memory on the intermediate program into consideration and replacing a conditional branch with a thread creation instruction;
• and
• means for referring to a result of the register allocation trial to reorder the instructions before and after the thread creation instruction on the intermediate program.

A program conversion method for performing an optimization process including parallelization for an intermediate program outputted as a result of a syntax analysis on a program conversion apparatus which compiles a source program and outputs a target program for a target processing apparatus of the multi-thread type, comprising:

• a register allocating trial step of trying register allocation prior to parallelization to estimate a register allocation situation of variables and intermediate terms of the intermediate program;
• a fork spot determination step of determining based on a result of the register allocation trial whether or not a conditional branch portion of the intermediate program should be converted into a parallel code for which a thread creation instruction is used or performing determination of whether or not the conditional branch portion should be converted into a parallel code and, when such conversion should be performed, determination of a parallelization execution method;
• an instruction reordering step of converting the conditional branch portion in the intermediate program into a parallel code for which the thread creation instruction is used based on a result of the determination by the fork spot determination step and referring to the result of the register allocation trial to insert an instruction for assuring a data-dependence relationship between threads through a memory into positions before and after the thread creation instruction and reorder the instructions before and after the thread creation instruction so that thread creation may be performed in an early stage;
• and
• a register allocation step of performing definite register allocation so that the same allocation result as that upon the register allocation trial may be obtained for the parallelized and reordered instruction sequence.

A recording medium on which a program for causing a computer to perform an optimization process including parallelization for an intermediate program outputted as a result of a syntax analysis on a compiler which compiles a source program and produces and outputs a target program for a multi-thread processor apparatus is recorded, the optimization process including:

• a register allocation trial process of trying register allocation prior to parallelization to estimate a register allocation situation of variables and intermediate terms of the intermediate program;
• a fork spot determination process of determining based on a result of the register allocation trial whether or not a conditional branch portion of the intermediate program should be converted into a parallel code for which a thread creation instruction is used or performing determination of whether or not the conditional branch portion should be converted into a parallel code and, when such conversion should be performed, determination of a parallelization execution method;
• an instruction reordering process of converting the conditional branch portion in the intermediate program into a parallel code for which the thread creation instruction is used based on a result of the determination by the fork spot determination step and referring to the result of the register allocation trial to insert an instruction for assuring a data-dependent relationship between threads through a memory into positions before and after the thread creation instruction and reorder the instructions before and after the thread creation instruction so that thread creation may be performed in an early stage;
• and
• a register allocation process of performing definite register allocation so that the same allocation result as that upon the register allocation trial with regard to whether a physical register is allocated may be obtained for the parallelized and reordered instruction sequence.

A program conversion apparatus for converting a given source program into a program for a multi-thread processor including a plurality of program counters and a plurality of thread execution apparatus, said plurality of thread execution apparatus being operable to fetch, decode and execute a plurality of instructions of threads simultaneously in accordance with said plurality of program counters such that it is possible to execute, after a thread is created, the thread in a control speculative mode wherein a change having had an effect on a register set can be cancelled later and to execute the thread in a data-dependent speculative mode wherein, when, after a self thread loads a value from a memory location, a parent thread by which the self thread has been created stores a value into the same memory location, at least a processing result of the self thread after the load is abandoned and the processing is re-executed, said multi-thread processor having an instruction set with which it can be executed by a single machine instruction or a combination of several machine instructions for a thread being executed by any of said thread execution apparatus to give, when a thread created by the self thread performs load from a memory location of a designated address, an instruction in advance to temporarily block the operation, to clear the load temporary blocking instruction to the designated memory address, for the thread being executed by the thread execution apparatus to create a new thread of the data-dependent speculative mode and to clear the data-dependent speculative mode of the thread of the data-dependent speculative mode created by the self thread, said program conversion apparatus comprising:

• a fork spot determination section for determining whether or not a conditional branch portion of the intermediate program should be converted into a parallel code for which a thread creation instruction is used and determining a parallelization execution method with the parallel code;
• said fork spot determination section including calculation means for calculating at least two or more distances of data dependence and means for determining the branching direction of that one of the distances of data dependence which exhibits a higher minimum value as a fork destination and selecting the branch spot as a fork spot.