Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-03-12
2002-04-02
Dam, Tuan Q. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S143000, C717S146000, C717S154000, C712S234000, C712S215000, C712S206000
Reexamination Certificate
active
06367076
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to an compiling method for compiling a source program into an object program for a CPUs that support predicated execution.
Programs executed on computers generally contain a large number of conditional branch instructions. A conditional branch instruction is one which changes the address of an instruction to be executed next, depending on whether a given condition is true or false. Usually, in the conditional branch instructions, the state where the condition is true is referred to as “the branch is taken”. In this case, an instruction to be executed after the conditional branch instruction is the instruction in an address which is specified by the operand in that conditional branch instruction, as opposed to the instruction in the address following that of the conditional branch instruction. On the other hand, the state where the condition is false is referred to as “the branch is not taken”. In this case, the instruction to be executed after the conditional branch instruction is the one in the address following that of the conditional branch instruction.
In CPUs that perform pipeline processing, an instruction is fetched from a memory or cache into the CPU several clock cycles before it is executed. Thus, the fetching of an instruction which has turned out to should be executed after the execution of a conditional branch instruction after a decision of whether its condition is true or not was made results in a failure to execute the next instruction in the cycle following the conditional branch instruction cycle. In that case, an idle cycle will be generated in which nothing can be performed. Such an event is referred to as a pipeline hazard, which is one of obstacles to high-speed program execution.
As one of methods to circumvent the pipeline hazard, predicated execution has been proposed (reference 1; “A Comparison of Full and Partial Predicated Execution Support for ILP Processors”, by Scott Mahlke, Proc. Of ISCA '95, pp. 138-149).
CPUs that support predicated execution differ from usual CPUs (i.e., CPUs that do not support predicated execution) in the following two points.
There is a predicate mode the CPU controls and a predicate mode set instruction is supported.
An opcode has a predicate field. The instruction is executed only when a coincidence occurs between the mode indicated by a value described in the predicate field and the predicate mode controlled by the CPU.
The utilization of the predicated execution allows conditional branch instructions in usual CPUs and instructions executed depending on whether their conditions are met to be modified as follows:
An conditional branch instruction is changed to an execution mode set instruction, which sets the CPU mode to “a” when the condition is true and to “b” when the condition is false.
With a sequence or group of instructions “A” to be executed when the branch is taken (i.e., when the condition is true), their respective predicate field value is specified to be a. With a sequence or group of instructions “B” to be executed when the branch is not taken (i.e., when the condition is false), their respective predicate field value is specified to be b. These instructions are allocated after the execution mode set instruction. An instruction in which the predicate field value is “a” and an instruction in which the predicate field value is “b” may be mixed. The “a” and “b” each take some numerical values.
The pipeline hazard can be circumvented by the utilization of the predicated execution because conditional branch instructions can be removed from a program.
Such predicated execution is expected to provide greater benefits especially in CPUs having VLIW (Very Long Instruction Word) architecture. Here, VLIW refers to an architecture in which a CPU contains multiple functional units which operate concurrently (reference 1: “A Compiler for VLIW Architectures” by Ellis, J. R., Bulldog, The MIT Press). The VLIW, which has the capability to execute two or more instructions at the same time, permits the speed of execution of a program to be increased, provided that instructions can be allocated simultaneously to many functional units. With the predicated execution, it is easy for many functional units to be filled with instructions because, as described previously, instructions can be allocated from both a sequence or group of instructions “A” which are executed when the branch is taken and a sequence or group of instructions “B” which are executed when the branch is not taken. For the VLIW in particular, therefore, the predicated execution is a promising means for speeding up the execution of a program.
However, the degree to which the program execution speed is increased depends on how to allocate the sequence of instructions “A” and the sequence of instructions “B” to the functional units. The establishment of a compiling method which allows for higher program execution speed is a problem.
As described above, the predicated execution does not suffer the pipeline hazard because no conditional branch is performed and the possibility therefore exists that a program may be executed at high speed. However, there exists heretofore no compiling method which allows for program execution at higher speed.
BRIEF SUMMARY OF THE INVENTION
It is therefor an object of the present invention to provide a compiling method which permits a CPU adapted for predicated execution to execute a program at high speed.
The invention is intended for a compiling method for compiling a source program into an object program for a CPU having multiple functional units that allow for concurrent operations and having a function of executing an instruction only when there is a predetermined relationship between an execution mode indicated by a value in a specific field in an instruction code and an execution mode managed within the CPU.
According to a first aspect of the present invention there is provided a compiling method comprising the steps of: analyzing the source program and generating intermediate codes; making an analysis of the intermediate codes; and allocating instructions from the intermediate codes based on the analysis, wherein an execution mode setting instruction to set an execution mode managed within the CPU, is allocated, instructions, such that whether the instructions are to be executed or not to be executed depends on the execution mode set by the execution mode setting instruction, are allocated, the instructions, in which values in their respective specific fields are identical, make an block together for every value in the specific field; an ending part of the block in which its last instruction is allocated is found for each block; and when the ending part of a certain block is to be earlier in the object program than the ending part of another block, an unconditional branch instruction identical in specific field value to the instructions in the certain block, is allocated either to be executed in the ending part of the certain block or to be executed as immediately as possible after the ending part of the block; whereby the object program is generated from the allocated instructions.
According to a second aspect of the present invention there is provided a compiling method comprising the steps of: analyzing the source program and generating intermediate codes; making an analysis of the intermediate codes; and allocating instructions from the intermediate codes based on the analysis, wherein an execution mode setting instruction to set an execution mode managed within the CPU, is allocated, instructions such that whether the instructions are to be executed or not to be executed depends on the execution mode set by the execution mode setting instruction are allocated, and wherein a decision of whether an instruction that is executed only when an execution mode set by the execution mode setting instruction is a certain specific mode can be allocated so that the instruction may be executed before the execution mode setting instruction or not is affirmative, the instruction
Fujii Hiroko
Imai Toru
Masubuchi Yoshio
Dam Tuan Q.
Kabushiki Kaisha Toshiba
Kendall Chuck
LandOfFree
Compiling method and memory storing the program code does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Compiling method and memory storing the program code, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compiling method and memory storing the program code will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2929471