Compiler apparatus

BACKGROUND OF THE INVENTION

0001(1) Field of the Invention

0002The present invention relates to a compiler apparatus which converts a source program described in a high-level language, such as the C language, into a machine language program. In particular, the present invention relates to speed enhancement achieved by the compiler apparatus for a loop process.

0003(2) Description of the Related Art

0004A compiler converts a source program described in a high-level language into a machine language program which is made up of machine language instructions. When doing so, the compiler sets the order of instructions so as to improve the execution efficiency of the machine language program. This operation is referred to as “instruction scheduling”.

0005In the technical field of language processors, how to improve the execution efficiency of a loop process has been one of the research themes over a long period of time. Generally, a loop is made up of control statements, such as “for” statements and “while” statements, and a body including 0 or more arithmetic expressions. This body is repeated until a repetition condition defined by a control statement is satisfied. An executable unit for such a loop process is called “iteration”, and the number of derived iterations is the same as the number of repetitions indicated in the control statement. For example, when the control statement describes that the body is to be repeated 100 times. 100 iterations would be derived from the body.

0006It should be understood that all or some of the iterations may be executed in parallel so that the execution efficiency of the loop process can be improved. For the parallel execution of the iterations, it is conventionally known that an optimization technique called “software pipelining” executed on the body of the loop process (also referred to as the “loop body” hereafter) is effective (see Japanese Application Publication No. 10-97423, for example).

0007Software pipelining is an optimization technique whereby the compiler converts the loop body into machine language instructions in a manner that parallels a pipeline so as to improve performance in the instruction execution. An explanation is given as to the execution of software pipelining, with reference to <figref idref="DRAWINGS">FIG. 1</figref>.

0008<figref idref="DRAWINGS">FIG. 1</figref> (a) is a diagram showing an example of the loop body, which is made up of instructions A, B, and C, and a branch instruction br. <figref idref="DRAWINGS">FIG. 1</figref> (b) is a diagram showing an example of a case where the instruction sequence shown in <figref idref="DRAWINGS">FIG. 1</figref> (a) is iterated 3 times without the parallel execution. Suppose, for example, that each of the instructions A, B, and C and a branch instruction br takes 1 cycle to complete. In this case, 4 cycles are required to complete each repetitive process (i.e., iteration), meaning that 12 cycles are required to complete 3 iterations.

0009Meanwhile, <figref idref="DRAWINGS">FIG. 1</figref> (c) is a diagram showing an example of a case where 3 iterations of the instruction sequence shown in <figref idref="DRAWINGS">FIG. 1</figref> (a) are optimized by software pipelining so that the instruction sequences are executed in parallel. In this case, optimization is performed in such a manner that the instruction C and the instruction A are executed in parallel and that the branch instruction br and the instruction B are executed in parallel, respectively across 2 iterations. Accordingly, the same 3 iterations can be executed in a total of 8 cycles, which is reduced from 12 cycles having been taken without the parallel execution.

0010It should be noted here that a combination of instructions to be executed in parallel is determined in accordance with a dependence relation between the instructions as well as hardware resources available in the processor that executes the machine language program.

0011A period of time taken from the start of an iteration to the start of the next iteration is termed an “initiation interval”. The shorter the initiation interval, the smaller the number of execution cycles required to complete the loop process and thus the faster the execution of the loop process.

0012However, in the case where considerable constraints are imposed on the hardware resources available to the processor, it is difficult to shorten the initiation interval or to appropriately perform instruction scheduling. This causes a problem that the effect of reducing the number of execution cycles would be small.

0013<figref idref="DRAWINGS">FIG. 2</figref> is a diagram illustrating this problem. This diagram shows a result of optimization by software pipelining executed on the instruction sequence shown in <figref idref="DRAWINGS">FIG. 1</figref> (a). Note here that each of the instructions A and B uses a hardware resource D. <figref idref="DRAWINGS">FIG. 2</figref> (a) shows a result of optimization in the case where there is only one hardware resource D. Meanwhile, <figref idref="DRAWINGS">FIG. 2</figref> (b) shows a result of optimization in the case where there are two hardware resources D. As shown in <figref idref="DRAWINGS">FIG. 2</figref> (a), the instructions A and B cannot be executed in parallel because there is only one hardware resource D. On account of this, the initiation interval cannot be reduced below 2. On the other hand, as shown in <figref idref="DRAWINGS">FIG. 2</figref> (b), the two hardware resources D allow the instructions A and B to be executed in parallel, thereby shortening the initiation interval to 1. In this way, the length of the initiation interval depends on the computer architecture. In other words, in the case where the initiation interval is long due to the hardware resource constraints, it is impossible to reduce the current initiation interval through optimization performed by the compiler.

0014Meanwhile, suppose that there is a loop-carried dependence, which refers to a data dependence between the instructions across the iterations. In this case, the minimum initiation interval is determined depending on the maximum number of cycles of the path including the loop-carried dependence in a data dependence graph that shows data dependence relations. This means that the initiation interval cannot be shortened to less than the value representing the present maximum number of cycles. For this reason, when this maximum value is large, there would be another problem that the software pipelining optimization has little effect of reducing the number of execution cycles.

0015<figref idref="DRAWINGS">FIGS. 3A and 3B</figref> are diagrams illustrating this problem. <figref idref="DRAWINGS">FIG. 3A</figref> is a diagram of a data dependence graph that shows data dependence relations among the instructions in the loop. <figref idref="DRAWINGS">FIG. 3B</figref> is a diagram showing a result of software pipelining executed on the basis of the data dependence graph shown in <figref idref="DRAWINGS">FIG. 3A</figref>.

0016Here, a brief explanation is given as to data dependences. Data dependences can be grouped under three classes, which are: “true dependence”, “antidependence”, and “output dependence”. A “true dependence” refers to a dependence relation in which an instruction uses the variable having been defined by the preceding instruction. An “antidependence” refers to a dependence relation in which an instruction defines the variable having been used by the preceding instruction. An “output dependence” refers to a dependence relation in which an instruction redefines the variable having been defined by the preceding instruction. In addition to these, a data dependence that exists between iterations is particularly referred to as a “loop-carried dependence”. This loop-carried dependence does not exist between the instructions of the body. To be more specific, a loop-carried dependence is a dependence relation that arises to allow a value obtained by an execution of an arithmetic expression within an iteration to be used in the iterations that follow. When this dependence relation exists, an arithmetic expression of the referencing side is prohibited from preceding an arithmetic expression of the defining side in execution. Moreover, in the present specification, a dependence relation that includes both a loop-carried dependence and one of the above-mentioned three dependences is referred to as follows. When a loop-carried dependence and a true dependence exist between two instructions, this relation is referred to as a “loop-carried true dependence”. When a loop-carried dependence and an antidependence exist between two instructions, this relation is referred to as a “loop-carried antidependence”. When a loop-carried dependence and an output dependence exist between two instructions, this relation is referred to as a “loop-carried output dependence”.

0017As shown in <figref idref="DRAWINGS">FIG. 3A</figref>, true dependences and an antidependence exist among the three instructions (i.e., the instructions ld, add, and st) within the loop. In this diagram, the true dependence is indicated by an arrow in a solid line whereas the antidependence is indicated by an arrow in a short dashed line.

0018Here, “ld r<b>0</b>, (r<b>1</b>+)” is an instruction to load data at an address stored in a register r<b>1</b> from a main memory, to store the data into a register r<b>0</b>, and to increment the value stored in the register r<b>1</b> by 1. Moreover. “add r<b>2</b>, r<b>0</b>, r<b>0</b>” is an instruction to add the value stored in the register r<b>0</b> to the value stored in the register r<b>0</b> and to store the addition result into a register r<b>2</b>. Furthermore, “st (r<b>1</b>), r<b>2</b>” is an instruction to store the value stored in the register r<b>2</b> into the main memory at an address that is stored in the register r<b>1</b>.

0019Thus, the true dependence exists between the instruction ld and the instruction add, with the register r<b>0</b> being a parameter. To be more specific, the register r<b>0</b> having been defined by the instruction ld is referenced by the instruction add. Note that a latency from the start of execution of the instruction ld until the time when the instruction add becomes executable is 3 cycles. This is accordingly described as “3 (r<b>0</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 3A</figref>.

0020Similarly, the true dependence exists between the instruction add and the instruction st, with the register r<b>2</b> being a parameter. Note that a latency between these 2 instructions is 1 cycle. This is accordingly described as “1 (r<b>2</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 3A</figref>.

0021Moreover, the loop-carried antidependence exists between the instruction st and the instruction ld, with the register r<b>1</b> being a parameter. To be more specific, the value stored in the register r<b>1</b> by the instruction ld after being referenced by the instruction st is incremented by 1, so that the register r<b>1</b> is defined. It should be noted that, in the specification of the present invention, a latency between two instructions having a loop-carried antidependence relation and a latency between two instructions having a loop-carried output dependence relation are both 0 cycle. This is accordingly described as “0 (r<b>1</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 3A</figref>.

0022Here, in the case of this cyclic path in the data dependence graph including the loop-carried dependence, the number of cycles of the present cyclic path is 4 (=3+1+0). Moreover, this cyclic path has only one loop-carried dependence, meaning that a dependence distance is 1. The “dependence distance” refers to the number of iterations present between two instructions which are loop-carried dependent on each other across two iterations. As shown in <figref idref="DRAWINGS">FIG. 3B</figref>, at least 4 cycles of the initiation interval is required from the start of execution of the instruction ld in an iteration to the start of execution of the instruction ld in the next iteration. Therefore, the initiation interval cannot be shortened to less than the number of cycles of the cyclic path in the dependence graph that includes the loop-carried dependence.

SUMMARY OF THE INVENTION

0023The present invention was conceived in view of the problems described above, and has an object of providing a compiler apparatus which can perform software pipelining optimization so that the number of execution cycles taken to complete a loop process can be significantly reduced.

0024In order to achieve the stated object, the compiler apparatus according to an aspect of the present invention converts a source program into a machine language program for a processor which is capable of parallel processing, and is composed of: a parsing unit operable to parse the source program and then to convert the source program into an intermediate program which is described in an intermediate language; an optimization unit operable to optimize the intermediate program; and a conversion unit operable to convert the optimized intermediate program into the machine language program, wherein the optimization unit is operable to execute software pipelining, by inserting a transfer instruction, which is used for transferring data between operands, into a loop process included in the intermediate program so that a data dependence relation is changed. To be more specific, the optimization unit has: a cyclic path detection unit operable to create a data dependence graph representing dependence relations among instructions existing in the intermediate program, and to detect a cyclic path which is a closed path that starts and ends with an instruction, the cyclic path tracing data dependences of the instruction in the data dependence graph; an insertion unit operable to insert the transfer instruction whose operands include a parameter of a loop-carried dependence included in the detected cyclic path; and a software pipelining unit operable to execute software pipelining on the intermediate program into which the transfer instruction has been inserted.

0025By the insertion of the transfer instruction into the loop, the closed path in the data dependence graph of the original loop can be divided into a plurality of closed paths. With this, there is a possibility of reducing the maximum number of cycles of the closed path in the data dependence graph of the original loop. This, in turn, leads to a possibility of shortening the initiation interval and of reducing the number of execution cycles taken to complete the loop process, after the software pipelining optimization is executed. Accordingly, the present invention can provide a compiler apparatus which can perform software pipelining optimization that has a considerable effect of reducing the number of execution cycles taken to complete a loop process.

0026For example, the insertion unit may include: an instruction selection unit operable to select an instruction on which a different instruction is true dependent and which is loop-carried antidependent, in the detected cyclic path; an instruction replacement unit operable to replace a first register that is used in the selected instruction with a second register; and a transfer instruction insertion unit operable to insert the transfer instruction for transferring a value stored in the first register to the second register. Moreover, the insertion unit may include: an instruction selection unit operable to select an instruction which is true dependent and on which a different instruction is loop-carried antidependent, in the detected cyclic path; an instruction replacement unit operable to replace a first register that is defined by the selected instruction with a second register; and a transfer instruction insertion unit operable to insert the transfer instruction for transferring a value stored in the second register to the first register.

0027With this structure, the dependence relation existing as the loop-carried antidependence in the closed path of the data dependence graph is divided, so that a new cyclic path in which the placement constraints have been eased can be generated. This leads to a possibility of reducing the number of execution cycles taken to complete the loop process. Accordingly, the present invention can provide a compiler apparatus which can perform software pipelining optimization that has a considerable effect of reducing the number of execution cycles taken to complete a loop process.

0028Preferably, the cyclic path detection unit is operable to detect at least one cyclic path which has a longest total latency of data dependences, and the instruction selection unit is operable to, when there exist a plurality of cyclic paths which each have the longest total latency, select an instruction, from among instructions which are loop-carried dependent in the cyclic paths or on each of which a different instruction is loop-carried dependent in the cyclic paths, that is loop-carried dependent in a largest number of cyclic paths or that a different instruction is loop-carried dependent on in a largest number of cyclic paths.

0029In this way, it is preferable to select the instruction which is loop-carried dependent or on which a different instruction is loop-carried dependent in the greatest number of the cyclic paths. With this selection, more path lengths can be reduced. Accordingly, the software pipelining optimization that has a considerable effect of reducing the number of execution cycles can be performed. In addition, the instruction placement constraints during instruction scheduling can be eased.

0030Moreover, the cyclic path detection unit may be operable to detect a cyclic path which has a longest path length, the path length representing a total latency of data dependences in the cyclic path.

0031The minimum initiation interval in the loop process is determined depending on the longest path length of the cyclic path. Thus, detection of such a cyclic path that has the longest path length and insertion of a transfer instruction into that cyclic path lead to a possibility of shortening the initiation interval. This, in turn, leads to a possibility of reducing the number of execution cycles taken to complete the loop process.

0032Preferably, the cyclic path detection unit is operable to detect a resource constrained cyclic path which has a longest resource constrained path length.

0033Detection of a cyclic path that has the longest path length with consideration given to constraints imposed on the hardware resources or the like can lead to a possibility of shortening the path length of the cyclic path that is a real bottleneck. Accordingly, the number of execution cycles taken to complete the loop process can be reduced, and the instruction placement constrains during instruction scheduling can be also eased.

0034Moreover, the cyclic path detection unit is operable to detect a cyclic path other than a cyclic path which is made up of two instructions and in which a same one register causes both a true dependence and a loop-carried antidependence.

0035When a transfer instruction is inserted into a cyclic path which is made up of two instructions and in which the same register causes both a true dependence and a loop-carried antidependence, the path length or the initiation interval cannot be shortened. For such a cyclic path, the cyclic path detection may not be performed, so that the optimization effect can be accordingly improved.

0036Furthermore, the cyclic path detection unit may be operable to detect a cyclic path in which a latency incurred by an instruction that is true dependent and that a different instruction is loop-carried antidependent on is longer than a latency incurred by the transfer instruction.

0037A cyclic path whose path length would become longer by the insertion of a transfer instruction can be eliminated in advance. Consequently, the cyclic path selection can be appropriately performed with enhanced speed and efficiency.

0038A program according to another aspect of the present invention is for a processor which is capable of parallel processing, the program causing the processor to execute: an instruction for executing iterations of a loop process in parallel; and a transfer instruction for transferring data between operands used in an instruction making up a closed path which starts and ends with a same instruction, the closed path tracing data dependences of the instruction included in a data dependence graph created with respect to the loop process.

0039As compared to a program in which a transfer instruction is not inserted, the initiation interval of this program is shorter because the transfer instruction has been inserted into the loop process. Accordingly, the present invention can provide a program which is capable of extremely high-speed execution.

0040It should be noted here that the present invention may be realized not only as a compiler apparatus that has these characteristic units, but also as: a compiling method that has steps corresponding to the characteristic units provided in such a compiler apparatus; and a compiler that causes a computer to execute the characteristic steps included in the compiling method. Also, it should be understood that such a compiler can be distributed via a record medium such as a CD-ROM (Compact Disc-Read Only Memory), or via a communication network such as the Internet.

0041The present invention can provide a compiler apparatus which can perform software pipelining optimization that has a considerable effect of reducing the number of execution cycles taken to complete a loop process.

0042Recent years have seen an increased introduction of processors which are capable of parallel processing. A loop process may frequently occur during the course of program execution. Thus, as a machine language program created by the compiler apparatus of the present invention is capable of high-speed execution, its practical value is significantly high.

FURTHER INFORMATION ABOUT TECHNICAL BACKGROUND TO THIS APPLICATION

0043The disclosure of Japanese Patent Application No. 2005-165999 filed on Jun. 6. 2005 including specification, drawings and claims is incorporated herein by reference in its entirety.

BRIEF DESCRIPTION OF THE DRAWINGS

0044These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings that illustrate a specific embodiment of the invention. In the Drawings:

0045<figref idref="DRAWINGS">FIG. 1</figref> is a diagram illustrating software pipelining;

0046<figref idref="DRAWINGS">FIG. 2</figref> to <figref idref="DRAWINGS">FIG. 3B</figref> are diagrams illustrating the conventional problems;

0047<figref idref="DRAWINGS">FIG. 4</figref> is a functional block diagram showing a structure of a compiler apparatus;

0048<figref idref="DRAWINGS">FIG. 5</figref> is a diagram showing changes in a data dependence graph before and after the insertion of a transfer instruction into a cyclic path;

0049<figref idref="DRAWINGS">FIG. 6</figref> is a diagram showing respective results of software pipelining executed before and after the insertion of a transfer instruction;

0050<figref idref="DRAWINGS">FIG. 7</figref> is a diagram showing a cyclic path obtained after an instruction mov has been inserted into a root node (an instruction ld) of the cyclic path shown in <figref idref="DRAWINGS">FIG. 5</figref> (a);

0051<figref idref="DRAWINGS">FIG. 8</figref> is a flowchart showing a process performed by a software pipelining unit;

0052<figref idref="DRAWINGS">FIGS. 9A to 9C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a cyclic path that has a loop-carried antidependence;

0053<figref idref="DRAWINGS">FIG. 10</figref> is a diagram showing a cyclic path obtained after an instruction mov has been inserted into a root node A in the case where the same register causes both the true dependence and the loop-carried antidependence of the root node A shown in <figref idref="DRAWINGS">FIG. 9A</figref>;

0054<figref idref="DRAWINGS">FIG. 11</figref> is a diagram showing changes before and after the insertion of a transfer instruction into a cyclic path that has a loop-carried output dependence;

0055<figref idref="DRAWINGS">FIG. 12</figref> is a diagram showing a cyclic path obtained after an instruction mov has been inserted into the cyclic path shown in <figref idref="DRAWINGS">FIG. 11</figref> (a);

0056<figref idref="DRAWINGS">FIG. 13</figref> is a diagram showing changes before and after the insertion of a transfer instruction into a cyclic path that has a loop-carried true dependence;

0057<figref idref="DRAWINGS">FIG. 14</figref> is a diagram showing changes before and after the insertion of a transfer instruction into a cyclic path that is made up of two instructions;

0058<figref idref="DRAWINGS">FIG. 15</figref> is a diagram showing changes before and after the insertion of a transfer instruction in the case where two cyclic paths, each being made up of two instructions, are included;

0059<figref idref="DRAWINGS">FIG. 16A</figref> is a diagram illustrating a longest path in the case where no resource constraints are imposed;

0060<figref idref="DRAWINGS">FIG. 16B</figref> is a diagram illustrating a longest path in the case where the resource constraints are imposed;

0061<figref idref="DRAWINGS">FIGS. 17A to 17C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a leaf node of a cyclic path that includes a plurality of longest paths;

0062<figref idref="DRAWINGS">FIGS. 18A and 18B</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a root node of a cyclic path that includes a plurality of longest paths;

0063<figref idref="DRAWINGS">FIGS. 19A to 19C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a cyclic path that includes a plurality of loop-carried dependences; and

0064<figref idref="DRAWINGS">FIG. 20</figref> is a diagram showing changes in a data dependence graph before and after the insertion of a transfer instruction into a cyclic path.

DESCRIPTION OF THE PREFERRED EMBODIMENT

0065The following is a description of a compiler apparatus according to an embodiment of the present invention, with reference to the drawings.

0066<figref idref="DRAWINGS">FIG. 4</figref> is a functional block diagram showing a structure of the compiler apparatus. More specifically, <figref idref="DRAWINGS">FIG. 4</figref> (a) is a functional block diagram showing an entire structure of the compiler apparatus whereas <figref idref="DRAWINGS">FIG. 4</figref> (b) is a functional block diagram showing a structure of a software pipelining unit which is a part of the compiler apparatus.

0067As shown in <figref idref="DRAWINGS">FIG. 4</figref> (a), a compiler apparatus <b>202</b> converts a source program <b>201</b> described in a high-level language, such as the C language, into a machine language program <b>203</b> which is executable by a processor. The compiler apparatus <b>202</b> is composed of a parsing unit <b>204</b>, an optimization unit <b>205</b>, and an output unit <b>206</b>. In the present embodiment, the target processor of the compiler apparatus <b>202</b> is a processor that is capable of executing a plurality of instructions in parallel.

0068The parsing unit <b>204</b> is a processing unit which performs a parsing process on the inputted source program <b>201</b> and then outputs a program described in an intermediate language. Hereafter, the program described in the intermediate language is referred to as an “intermediate program”. The optimization unit <b>205</b> is a processing unit which performs a predetermined optimization process on the intermediate program. The output unit <b>206</b> is a processing unit which converts the intermediate program, on which the optimization process has been performed, into a machine language program and then outputs the program.

0069The optimization unit <b>205</b> has a first optimization unit <b>207</b>, a software pipelining unit <b>208</b>, and a second optimization unit <b>209</b>. Each of the first optimization unit <b>207</b> and the second optimization unit <b>209</b> performs a general optimization process. The software pipelining unit <b>209</b> is a processing unit which optimizes a loop process included in the intermediate program by executing a software pipelining process.

0070As shown in <figref idref="DRAWINGS">FIG. 4</figref> (b), the software pipelining unit <b>208</b> has a cyclic path analysis unit <b>211</b>, an instruction selection unit <b>212</b>, a transfer instruction insertion unit <b>213</b>, and a conventional software pipelining unit <b>214</b>.

0071The cyclic path analysis unit <b>211</b> is a processing unit which creates a data dependence graph representing dependence relations among the instructions included in the intermediate program and which analyzes a cyclic path in the data dependence graph. A definition of the cyclic path is described later. The instruction selection unit <b>212</b> is a processing unit which selects, in accordance with the analysis result given by the cyclic path analysis unit <b>211</b>, an instruction from the data dependence graph, into which a transfer instruction is to be inserted. Here, the “transfer instruction” refers to an instruction at which data can be transferred between the operands, and generally is what is termed an instruction mov that moves data between the registers. The transfer instruction insertion unit <b>213</b> is a processing unit which inserts a transfer instruction into the instruction selected by the instruction selection unit <b>212</b>. The conventional software pipelining unit <b>214</b> is a processing unit which executes the conventional software pipelining process on the intermediate program after the transfer instruction has been inserted.

0072It should be noted here that each processing unit making up the compiler apparatus <b>202</b> is realized as a program that is executed on a computer.

0073The following are definitions of the terms used throughout the present specification.

0074(1) Cyclic path: A closed path of a data dependence graph, which is traced along the data dependences of an instruction and which begins and ends with the same instruction. Note that, in the cyclic path, the same instruction is not traced more than once.

0075(2) Path length: A total latency of the data dependences in the cyclic path.

0076(3) Resource constrained cyclic path: A cyclic path with consideration given to the resource constraints (i.e., the constraints imposed on the hardware resources and on the number of instructions executable in parallel).

0077(4) Resource constrained path length: A total latency of the data dependences in the resource constrained cyclic path.

0078(5) Longest path: A longest cyclic path.

0079(6) Resource constrained longest path: A longest cyclic path with consideration given to the resource constraints.

0080(7) Leaf node: An instruction which the other instruction is true dependent on and which is antidependent, in the cyclic path.

0081(8) Root node: An instruction which is true dependent and which the other instruction is antidependent on, in the cyclic path.

0082A principal object of the present invention is to improve software pipelining in performance by inserting a transfer instruction into a leaf node or a root node in a cyclic path or a resource constrained cyclic path. For this reason, a detailed explanation will be given only as to the process executed by the software pipelining unit <b>208</b> in the present embodiment. The other processing units of the compiler apparatus <b>202</b> respectively have the same functions as those of a conventional compiler apparatus, and thus detailed explanations of them are not repeated here.

0083First, an explanation is given as to workings and effects achieved by the insertion of a transfer instruction into the cyclic path. <figref idref="DRAWINGS">FIG. 5</figref> is a diagram showing changes in a data dependence graph before and after the insertion of the transfer instruction into the cyclic path.

0084<figref idref="DRAWINGS">FIG. 5</figref> (a) shows the same cyclic path as the one in the data dependence graph shown in <figref idref="DRAWINGS">FIG. 3A</figref>. This cyclic path includes three instructions within the loop, which are instructions ld, add, and st. The path length of this data dependence graph is 4 cycles. Meanwhile, <figref idref="DRAWINGS">FIG. 5</figref> (b) shows the cyclic path obtained after an instruction mov, which is a kind of transfer instruction, has been inserted into the leaf node (i.e., the instruction st) of the cyclic path shown in <figref idref="DRAWINGS">FIG. 5</figref> (a). To be more specific, instead of the instruction st, an instruction “st (r<b>4</b>). r<b>2</b>” is used. In this instruction, a register r<b>1</b> which is a parameter used by the instruction st for a loop-carried dependence is replaced with an unused register r<b>4</b>. Also, a transfer instruction “mov r<b>4</b>, r<b>1</b>” is inserted, so that a value stored in the register r<b>1</b> which is the original parameter is stored into the register r<b>4</b>. By this insertion of the instruction mov into the leaf node, the cyclic path whose path length was 4 cycles is divided into 2 cyclic paths. That is, one is made up of instructions ld and mov and its path length is 3 cycles, and the other is made up of instructions may and st and its path length is 1 cycle. As can be understood from this, by the insertion of the transfer instruction, the original loop-carried dependence is cut up. In the present specification, when a loop-carried dependence is cut up so that new cyclic paths are created in this way, this cutting process is referred to as “loop-carried dependence cut”.

0085As mentioned above, the minimum value of the initiation interval by software pipelining is determined depending on the longest path length. This means, in the case where the cyclic path shown in <figref idref="DRAWINGS">FIG. 5</figref> (a) is the longest path of the present loop process, the initiation interval can be reduced from 4 to 3.

0086<figref idref="DRAWINGS">FIG. 6</figref> is a diagram showing respective results of software pipelining performed before and after the insertion of the transfer instruction. <figref idref="DRAWINGS">FIG. 6</figref> (a) shows the result of software pipelining which is performed before the transfer instruction is inserted, and the resultant initiation interval is 4 cycles. Meanwhile, <figref idref="DRAWINGS">FIG. 6</figref> (b) shows the result of software pipelining which is performed after the transfer instruction has been inserted, and the resultant initiation interval is 3 cycles. By the insertion of the transfer instruction, although there is a possibility of increasing the number of execution cycles per iteration, the initiation interval is shortened. Therefore, for the loop as a whole, the number of execution cycles is reduced. The greater the number of iterations, the larger this effect is.

0087Moreover, as shown in <figref idref="DRAWINGS">FIG. 5</figref>, the dependence distance between the instructions st and ld is increased from 1 to 2. Accordingly, the instruction placement constraint during software pipelining is eased.

0088<figref idref="DRAWINGS">FIG. 7</figref> is a diagram showing a cyclic path obtained after an instruction mov has been inserted into the root node (the instruction ld) of the cyclic path shown in <figref idref="DRAWINGS">FIG. 5</figref> (a). To be more specific, instead of the instruction ld, an instruction “ld r<b>0</b>, (r<b>4</b>+)” is used. In this instruction, the register r<b>1</b> which is a parameter used by the instruction ld is replaced with the unused register r<b>4</b>. Also, a transfer instruction “mov r<b>4</b>, r<b>1</b>” is inserted, so that a value stored in the register r<b>4</b> is stored into the register r<b>1</b> that is the original parameter. By this insertion of the instruction mov into the root node, the cyclic path whose path length was 4 cycles is divided into 2 cyclic paths. That is, one is made up of instructions ld and mov and its path length is 3 cycles, and the other is made up of instructions may and st and its path length is 1 cycle. As explained above with reference to <figref idref="DRAWINGS">FIGS. 5 and 6</figref>, there is a possibility of shortening the initiation interval to 3 cycles in this case as well.

0089Next, an explanation is given as to a flow of a process executed by the software pipelining unit <b>208</b> shown in <figref idref="DRAWINGS">FIG. 4</figref> (b). <figref idref="DRAWINGS">FIG. 8</figref> is a flowchart showing the process performed by the software pipelining unit <b>208</b>.

0090The cyclic path analysis unit <b>211</b> creates a data dependence graph for a loop included in the intermediate program and acquires cyclic paths existing in the data dependence graph (S<b>400</b>). Then, the instruction selection unit <b>212</b> sets all the cyclic paths of the loop acquired in the cyclic path acquisition process (S<b>400</b>) as a cyclic path set (S<b>401</b>). Moreover, the instruction selection unit <b>212</b> obtains longest paths from the cyclic paths included in the cyclic path set (S<b>402</b>). Then, the instruction selection unit <b>212</b> excludes the longest paths whose path lengths will become longer by the insertion of the transfer instruction, from the cyclic path set (S<b>403</b>). Furthermore, the instruction selection unit <b>212</b> selects one from among the leaf nodes and the root nodes of the longest paths belonging to the cyclic path set (S<b>404</b>). The transfer instruction insertion unit <b>213</b> inserts the transfer instruction into the selected leaf node or root node (S<b>405</b>). Then, the conventional software pipelining unit <b>214</b> executes the software pipelining process on the loop process into which the transfer instruction has been inserted (S<b>406</b>).

0091The above examples of <figref idref="DRAWINGS">FIGS. 5 and 6</figref> show the cases where the transfer instruction is inserted into the leaf node of the longest path that has the loop-carried antidependence relation and then software pipelining is performed. Meanwhile, the example of <figref idref="DRAWINGS">FIG. 7</figref> shows the case where the transfer instruction is inserted into the root node of the longest path that has the loop-carried antidependence relation and then software pipelining is performed.

0092As described earlier, the data dependences can be grouped under three classes, which are true dependence, antidependence, and output dependence. Similarly, the loop-carried dependence can be grouped under true dependence, antidependence, and output dependence.

0093The following are considerations given to changes in the path length in the cases where: the transfer instruction is inserted into the longest path that has the loop-carried antidependence relation: the transfer instruction is inserted into the longest path that has the loop-carried output dependence relation; and the transfer instruction is inserted into the longest path that has the loop-carried true dependence relation.

0000[Loop-Carried Antidependence]

0094<figref idref="DRAWINGS">FIGS. 9A to 9C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into the cyclic path which has a loop-carried antidependence.

0095<figref idref="DRAWINGS">FIG. 9A</figref> shows an example of the cyclic path which has the loop-carried antidependence, the cyclic path being made up of instructions A, B, C, and D. Note that, in the present cyclic path, the instruction A is a root node whereas the instruction D is a leaf node. Also note that the loop-carried antidependence exists between the leaf node D and the root node A. In <figref idref="DRAWINGS">FIGS. 9A to 9C</figref>, the true dependence is indicated by an arrow in a solid line whereas the antidependence is indicated by an arrow in a short dashed line. For instance, a latency from the start of execution of the instruction A until the time when the instruction B becomes executable is 4 cycles. Thus, as can be seen in the diagram of <figref idref="DRAWINGS">FIG. 9A</figref>, the path length of the present cyclic path is 12 cycles.

0096<figref idref="DRAWINGS">FIG. 9B</figref> shows a cyclic path obtained after an instruction mov has been inserted into an instruction other than the leaf node D and the root node A shown in <figref idref="DRAWINGS">FIG. 9A</figref>. This diagram shows a cyclic path of a case where the instruction mov is inserted into the instruction B or C. As shown, the loop-carried dependence relation between the instructions A and D is not changed even after the instruction mov has been inserted into the instruction other than the root node A and the leaf node D. In addition, due to the insertion of the instruction mov, 1 cycle of latency is required between the start of execution of the instruction mov and the start of execution of the instruction C, resulting in increasing the path length from 12 to 13. Thus, the path length cannot be shortened, meaning that the initiation interval cannot be shortened either.

0097<figref idref="DRAWINGS">FIG. 9C</figref> shows a cyclic path obtained after the instruction mov has been inserted into the leaf node D shown in <figref idref="DRAWINGS">FIG. 9A</figref>. In this example, due to the insertion of the instruction mov into the leaf node D, the loop-carried dependence cut is performed between the instructions A and D. As a result of this, the cyclic path of 12 cycles with a dependence distance of 1 is changed into cyclic paths of 4 cycles and of 1 cycle. As can be understood from this, there is a possibility of shortening the initiation interval from 12 cycles to 4 cycles in the case where the cyclic path shown in <figref idref="DRAWINGS">FIG. 9A</figref> is the longest path. However, when another cyclic path whose path length is 5 cycles or more is present within the loop, that path length would be the minimum initiation interval. Additionally, by the loop-carried dependence cut, the instruction placement constraint can be eased.

0098<figref idref="DRAWINGS">FIG. 10</figref> is a diagram showing a cyclic path obtained after an instruction mov has been inserted into the root node A in the case where the same register causes both the true dependence and the loop-carried antidependence for the root node A shown in <figref idref="DRAWINGS">FIG. 9A</figref>. As is the case with the example shown in <figref idref="DRAWINGS">FIG. 9C</figref>, the cyclic path of 12 cycles is changed into cyclic paths of 4 cycles and of 9 cycles by the loop-carried dependence cut. Thus, there is a possibility of shortening the initiation interval from 12 cycles to 9 cycles in the case where the cyclic path shown in <figref idref="DRAWINGS">FIG. 9A</figref> is the longest path. Also, the instruction replacement constraint can be eased.

0000[Loop-Carried Output Dependence]

0099<figref idref="DRAWINGS">FIG. 11</figref> is a diagram showing changes before and after the insertion of a transfer instruction into the cyclic path that has a loop-carried output dependence. <figref idref="DRAWINGS">FIG. 11</figref> (a) shows an example of the cyclic path that has the loop-carried output dependence, the cyclic path being made up of one ld instruction and two add instructions. In this diagram, the true dependence is indicated by an arrow in a solid line whereas the output dependence is indicated by an arrow in a short dashed line.

0100Here, “ld, r<b>0</b>, (r<b>1</b>+)” is an instruction to load data at an address stored in a register r<b>1</b> from a main memory, to store the data into a register r<b>0</b>, and to increment the value stored in the register r<b>1</b> by 1. Moreover, “add r<b>2</b>, r<b>0</b>, r<b>0</b>” is an instruction to add the value stored in the register r<b>0</b> to the value stored in the register r<b>0</b> and to store the addition result into a register r<b>2</b>. Furthermore, “add r<b>0</b>, r<b>2</b>, r<b>2</b>” is an instruction to add the value stored in the register r<b>2</b> to the value stored in the register r<b>2</b> and to store the addition result into the register r<b>0</b>.

0101Thus, the true dependence exists between the instruction “ld r<b>0</b>, (r<b>1</b>+)” and the instruction “add r<b>2</b>, r<b>0</b>, r<b>0</b>”, with the register r<b>0</b> being a parameter. To be more specific, the register r<b>0</b> having been defined by the instruction ld is referenced by the instruction add. Note that a latency from the start of execution of the instruction ld until the time when the instruction add becomes executable is 3 cycles. This is accordingly described as “3 (r<b>0</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 11</figref> (a).

0102Similarly, a true dependence exists between the instruction “add r<b>2</b>, r<b>0</b>, r<b>0</b>” and the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>”, with the register r<b>2</b> being a parameter. Note that a latency between these 2 instructions is 1 cycle. This is accordingly described as “1 (r<b>2</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 11</figref> (a).

0103Moreover, a loop-carried output dependence exists between the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>” and the instruction “ld r<b>0</b>, (r<b>1</b>+)”, with the register r<b>0</b> being a parameter. To be more specific, after being defined by the instruction add, the value stored in the register r<b>0</b> is redefined by the instruction ld. Note again, as described earlier, that in the embodiment of the present invention, a latency between the two instructions having a loop-carried dependence is 0 cycle. This is accordingly described as “0 (r<b>0</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 11</figref> (a).

0104In the case of this cyclic path in the data dependence graph including such a loop-carried dependence, the path length is 4 (=3+1+0). Moreover, this cyclic path has only one loop-carried dependence, meaning that a dependence distance is 1.

0105Although this cyclic path has no root node or leaf node that fits the definition described above, consider a case where an instruction mov is inserted into an instruction corresponding to a leaf node, that is, an instruction which is loop-carried dependent. <figref idref="DRAWINGS">FIG. 11</figref> (b) shows a cyclic path obtained after the instruction mov has been inserted into the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>” that is loop-carried dependent in the cyclic path shown in <figref idref="DRAWINGS">FIG. 11</figref> (a). To be more specific, instead of the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>”, an instruction “add r<b>3</b>, r<b>2</b>, r<b>2</b>” is used. In this instruction, the register r<b>0</b> which is a parameter used by the present instruction add for the loop-carried dependence is replaced with an unused register r<b>3</b>. Also, a transfer instruction “mov r<b>3</b>, r<b>0</b>” is inserted, so that the value stored in the register r<b>0</b> which is the original parameter is stored into the register r<b>3</b>. By this insertion of the instruction mov into the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>” which is loop-carried dependent, the loop-carried dependence cut is performed between the instructions add and ld. As a result of this, the cyclic path with a dependence distance of l is eliminated.

0106<figref idref="DRAWINGS">FIG. 12</figref> is a diagram showing a cyclic path obtained after the instruction mov has been inserted into an instruction corresponding to a root node of the cyclic path shown in <figref idref="DRAWINGS">FIG. 11</figref> (a), i.e., the instruction “ld r<b>0</b>, (r<b>1</b>+)” on which the other instruction is loop-carried dependent. To be more specific, instead of the instruction “ld r<b>0</b>, (r<b>1</b>+)”, an instruction “ld r<b>3</b>, (r<b>1</b>+)” is used. In this instruction, the register r<b>0</b> which is a parameter used by the present instruction ld for the loop-carried dependence is replaced with the unused register r<b>3</b>. Also, a transfer instruction “mov r<b>0</b>, r<b>3</b>” is inserted, so that the value stored in the register r<b>3</b> is stored into the register r<b>0</b> that is the original parameter. By this insertion of the instruction mov into the root node, the loop-carried dependence cut is performed between the instructions add and ld. As a result of this, the cyclic path whose path length was 4 cycles is divided into 2 cyclic paths. That is, one is made up of instructions ld and mov and its path length is 3 cycles and the other is made up of one mov instruction and two add instructions and its path length is 2 cycles, with a dependence distance of 1. Accordingly, in the case where the cyclic path shown in <figref idref="DRAWINGS">FIG. 11</figref> (a) is the longest path, there is a possibility of shortening the initiation interval to 3 cycles.

0000[Loop-Carried True Dependence]

0107<figref idref="DRAWINGS">FIG. 13</figref> is a diagram showing changes before and after the insertion of a transfer instruction into a cyclic path that has a loop-carried true dependence. <figref idref="DRAWINGS">FIG. 13</figref> (a) shows an example of the cyclic path that has the loop-carried true dependence, the cyclic path being made up of one mul instruction and two add instructions. In this diagram, all the dependence relations are true dependences, each being indicated by an arrow in a solid line.

0108Here, “mul, r<b>1</b>, r<b>0</b>, r<b>0</b>” is an instruction to multiply the data stored in the register r<b>0</b> by the data stored in the register r<b>0</b> and to store the multiplication result into the register r<b>1</b>. Moreover, “add r<b>2</b>, r<b>1</b>, r<b>1</b>” is an instruction to add the value stored in the register r<b>1</b> to the value stored in the register r<b>1</b> and to store the addition result into the register r<b>2</b>. Furthermore, “add r<b>0</b>, r<b>2</b>, r<b>2</b>” is an instruction to add the value stored in the register r<b>2</b> to the value stored in the register r<b>2</b> and to store the addition result into the register r<b>0</b>.

0109Thus, the true dependence exists between the instruction “mul r<b>1</b>, r<b>0</b>, r<b>0</b>” and the instruction “add r<b>2</b>, r<b>1</b>, r<b>1</b>”, with the register r<b>1</b> being a parameter. To be more specific, the register r<b>1</b> having been defined by the instruction mul is referenced by the instruction add. Note that a latency from the start of execution of the instruction mul until the time when the instruction add becomes executable is 4 cycles. This is accordingly described as “4 (r<b>1</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 13</figref> (a).

0110Similarly, a true dependence exists between the instruction “add r<b>2</b>, r<b>1</b>, r<b>1</b>” and the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>”, with the register r<b>2</b> being a parameter. Note that a latency between these 2 instructions is 1 cycle. This is accordingly described as “1 (r<b>2</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 13</figref> (a).

0111Moreover, a loop-carried true dependence exists between the instruction “add r<b>0</b>, r<b>2</b>, r<b>2</b>” and the instruction “mul r<b>1</b>, r<b>0</b>, r<b>0</b>”, with the register r<b>0</b> being a parameter. A latency between the 2 instructions is 1 cycle. This is accordingly described as “1 (r<b>0</b>)” in the diagram of <figref idref="DRAWINGS">FIG. 13</figref> (a).

0112In the case of this cyclic path of the data dependence graph that includes such a loop-carried dependence, the path length is 6 (=4+1+1).

0113This cyclic path has no root node or leaf node that fits the definition described above, as all the data dependences within the graph are true dependences. Here, consider a case where the instruction mov is inserted into the instruction mul which is one of the instructions making up the cyclic path. <figref idref="DRAWINGS">FIG. 13</figref> (b) shows a cyclic path obtained after the instruction mov has been inserted into the cyclic path shown in <figref idref="DRAWINGS">FIG. 13</figref> (a). To be more specific, instead of the instruction “mul r<b>1</b>, r<b>0</b>, r<b>0</b>”, an instruction “mul r<b>3</b>, r<b>0</b>, r<b>0</b>” is used. In this instruction, the register r<b>1</b> which is a parameter used by the present instruction mul is replaced with the unused register r<b>3</b>. Also, a transfer instruction “mov r<b>1</b>, r<b>3</b>” is inserted, so that the value stored in the register r<b>3</b> is stored into the register r<b>1</b> which is the original parameter. Note that a latency from the start of execution of the instruction mov until the time when the instruction add becomes executable is 1 cycle. As a result, the path length after the insertion of the transfer instruction becomes 7 (=4+1+1+1). As can be understood from this, the path length cannot be shortened by the insertion of the transfer instruction. In fact, the path length becomes longer, only increasing the code size. It should be noted here that in the case of the cyclic path made up of only true dependences, the path length cannot be shortened no matter where the transfer instruction is to be inserted. This means the optimization has no effect in such a case.

0000[Cyclic Path Made Up of Two Instructions]

0114Next, an explanation is given as to a case where a transfer instruction is inserted into a cyclic path which is made up of two instructions.

0115<figref idref="DRAWINGS">FIG. 14</figref> is a diagram showing changes before and after the insertion of a transfer instruction into a cyclic path which is made up of two instructions and in which the same register causes both a true dependence and a loop-carried antidependence. <figref idref="DRAWINGS">FIG. 14</figref> (a) shows an example of the cyclic path having the loop-carried antidependence, the cyclic path being made up of two instructions A and B and the path length being 4 cycles. In this diagram, the true dependence is indicated by an arrow in a solid line whereas the loop-carried antidependence is indicated by an arrow in a short dashed line.

0116<figref idref="DRAWINGS">FIG. 14</figref> (b) shows a cyclic path obtained after the instruction mov has been inserted into the root node shown in <figref idref="DRAWINGS">FIG. 14</figref> (a). By this insertion of the instruction mov, the loop-carried dependence cut is performed. Nevertheless, the path length is still 4 cycles at the maximum. It can be verified that in the case where the transfer instruction is inserted into a root node of a cyclic path made up of two instructions, the initiation interval cannot be shortened, thereby rendering the optimization ineffectual. In fact, the insertion of the instruction mov increases the code size of the machine language program <b>203</b>, which leads to degradation in performance.

0117Meanwhile, <figref idref="DRAWINGS">FIG. 15</figref> is a diagram showing changes before and after the insertion of a transfer instruction in the case where 2 cyclic paths are included, each cyclic path being made up of two instructions and the same register causing both a true dependence and a loop-carried antidependence in the cyclic path.

0118<figref idref="DRAWINGS">FIG. 15</figref> (a) shows an example of the cyclic paths that each have a loop-carried antidependence. Here, one cyclic path is made up of instructions A and B whereas the other cyclic path is made up of instructions A and C. In this diagram, the true dependence is indicated by an arrow in a solid line and the loop-carried antidependence is indicated by an arrow in a short dashed line. As can be seen, these 2 cyclic paths have the instruction A as a common root node and each path length is 4 cycles.

0119<figref idref="DRAWINGS">FIG. 15</figref> (b) shows a cyclic path obtained after the instruction mov has been inserted into the root node shown in <figref idref="DRAWINGS">FIG. 15</figref> (a). By the insertion of the instruction mov, the loop-carried dependence cut is performed. As a result, the cyclic path shown in <figref idref="DRAWINGS">FIG. 15</figref> (a) is changed into 3 cyclic paths with a dependence distance of 1. More specifically, these 3 are: 1 cyclic path with a path length of 4 cycles; and 2 cyclic paths each with a path length of 1 cycle. In this case, the path length is still 4 cycles at the maximum, meaning that the initiation interval cannot be shortened. However, the number of cyclic paths with the path length of 4 cycles is reduced from 2 to 1. Accordingly, the instruction placement constraint imposed during software pipelining is eased, so that the probability of success in software pipelining increases.

0000[Resource-Constrained Cyclic Path]

0120Next, an explanation is given as to a case where a transfer instruction is inserted into a cyclic path that is formed in consideration of resource constraints.

0121First, a comparison is made between the longest paths in the cases where the resource constraints are imposed and not imposed, using the same dependence graph. <figref idref="DRAWINGS">FIGS. 16A and 16B</figref> are diagrams illustrating the difference between the longest paths. <figref idref="DRAWINGS">FIG. 16A</figref> shows a cyclic path in the case where no resource constraints are imposed whereas <figref idref="DRAWINGS">FIG. 16B</figref> shows a cyclic path that is formed with consideration given to the resource constraints. In these diagrams, the true dependence is indicated by an arrow in a solid line. Here, it should be noted that although not illustrated in these diagram, there is necessarily a loop-carried dependence opposite in direction to the true dependence indicated by the solid line.

0122As shown in <figref idref="DRAWINGS">FIG. 16A</figref>, when no resource constraints are imposed, the cyclic path made up of instructions e, f, and g is the longest path and its path length is 7 cycles. On the other hand, in the resource-constrained cyclic path as shown in <figref idref="DRAWINGS">FIG. 16B</figref>, instructions a, b, and c use one and the same resource d.

0123Hereafter, a cyclic path made up of instructions s, a, and e is referred to as the “cyclic path a”; a cyclic path made up of instructions s, b, and e is referred to as the “cyclic path b”; and a cyclic path made up of instructions s, c, and e is referred to as the “cyclic path c”. When no resource constraints are imposed, each of their path lengths is 6 cycles. As already mentioned above, however, the instructions a, b, and c share one and the same resource d in common. Suppose here that a latency from the execution start of one of the instructions a, b, and c until the time when the executed instruction releases the resource d is 2 cycles. Note that the instructions a, b, and c are executed in this order as a fixed order of priority.

0124For the execution of the instructions included in the cyclic path a, the instruction a does not have to wait for the resource d to be released since the other instructions do not use the resource d. On account of this, the resource constrained path length of the cyclic path a is 6 (=4+2+0) cycles. For the execution of the instructions included in the cyclic path b, the instruction b has to wait 2 cycles, even when executable, until the instruction a releases the resource d. Thus, the resource constrained path length of the cyclic path b is 8 (=4+2+2+0) cycles. For the execution of the instructions included in the cyclic path c, the instruction c has to wait 4 (=2+2) cycles, even when executable, until the instructions a and b release the resource d. On account of this, the resource constrained path length of the cyclic path c is 10 (=4+2+2+2+0) cycles. Consequently, the resource constrained longest path is the cyclic path c, and its resource constrained path length is 10 cycles.

0125In this way, even in the same dependence graph, the longest paths are different depending on whether or not the resource constraints are imposed, and thus the path lengths are also different. In consideration of this, for the case where the resource constraints are imposed, the resource constrained longest path needs to be obtained.

0000[Cyclic Path Including a Plurality of Longest Paths]

0126An explanation is next given as to a case where a transfer instruction is inserted into a cyclic path which includes a plurality of longest paths.

0127<figref idref="DRAWINGS">FIGS. 17A to 17C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a leaf node of the cyclic path that includes a plurality of longest paths. In these diagrams, the true dependence is indicated by an arrow in a solid line. Here, it should be noted that although not illustrated in these diagram, there is necessarily a loop-carried dependence opposite in direction to the true dependence indicated by the solid line.

0128<figref idref="DRAWINGS">FIG. 17A</figref> shows a cyclic path that includes 5 longest paths, with each path length being 6 cycles. In this diagram, these 5 longest paths are indicated specifically by arrows in thick solid lines. As shown, the loop-carried dependence between the instructions b and a also exists in 3 cyclic paths, which are: a path made up of instructions a, m, and b; a path made up of instructions a, n, and b; and a path made up of instructions a, o, and b. Moreover, the loop-carried dependence between the instructions c and b also exists in 2 cyclic paths, which are: a path made up of instructions b, p, and c; and a path made up of instructions b, r, and c.

0129<figref idref="DRAWINGS">FIG. 17B</figref> shows a cyclic path obtained after the instruction mov has been inserted into the leaf node b so that the loop-carried dependence cut is executed between the instructions b and a. In this diagram, the arrows in thick lines indicate the cyclic paths changed from the longest paths shown in <figref idref="DRAWINGS">FIG. 17A</figref>. More specifically, the 5 longest paths whose respective path lengths were 6 cycles are changed into, with a dependence distance of 1: 2 longest paths, each path length being 6 cycles; 1 cyclic path with a path length of 4 cycles: and 1 cyclic path with a path length of 1 cycle.

0130<figref idref="DRAWINGS">FIG. 17C</figref> shows a cyclic path obtained after the instruction mov has been inserted into the leaf node c so that the loop-carried dependence cut is executed between the instructions c and b. In this diagram, the arrows in thick lines indicate the cyclic paths changed from the longest paths shown in <figref idref="DRAWINGS">FIG. 17A</figref>. More specifically, the 5 longest paths whose respective path lengths were 6 cycles are changed into, with a dependence distance of 1: 3 longest paths, each path length being 6 cycles; 1 cyclic path with a path length of 4 cycles; and 1 cyclic path with a path length of 1 cycle.

0131As can be understood, the number of the longest paths is reduced more in the case of <figref idref="DRAWINGS">FIG. 17B</figref> than the case of <figref idref="DRAWINGS">FIG. 17C</figref>. That is, for the case where the transfer instruction is inserted into a leaf node, the number of cyclic paths with longer path lengths can be reduced by the loop-carried dependence cut performed by the insertion of the transfer instruction into the leaf node that has more, longer cyclic paths. Consequently, the instruction placement constraint imposed during software pipelining can be eased.

0132<figref idref="DRAWINGS">FIGS. 18A and 18B</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a root node of the cyclic path that includes a plurality of longest paths. Note here that the arrows in these diagrams represent the same meanings as those in <figref idref="DRAWINGS">FIGS. 17A to 17C</figref>.

0133<figref idref="DRAWINGS">FIG. 18A</figref> shows a cycle path obtained after the instruction mov has been inserted into the root node a so that the loop-carried dependence cut is performed between the instructions b and a shown in <figref idref="DRAWINGS">FIG. 17A</figref>. Note here, in this case, that the same register causes both the true dependence between the instruction a and the instructions m, n, and o and the loop-carried dependence between the instruction b and a. As shown, the 5 longest paths whose respective path lengths were 6 cycles are changed into, with a dependence distance of 1: 2 longest paths, each path length being 6 cycles; 1 cyclic path with a path length of 4 cycles; and 3 cyclic paths, each path length being 3 cycles.

0134Meanwhile, <figref idref="DRAWINGS">FIG. 18B</figref> shows a cycle path obtained after the instruction mov has been inserted into the root node b so that the loop-carried dependence cut is performed between the instructions c and b shown in <figref idref="DRAWINGS">FIG. 17A</figref>. Note here, in this case, that the same register causes both the true dependence between the instruction b and the instructions p and r and the loop-carried dependence between the instruction c and b. As shown, the 5 longest paths whose respective path lengths were 6 cycles are changed into, with a dependence distance of 1: 3 longest paths, each path length being 6 cycles; 1 cyclic path with a path length of 4 cycles; and 2 cyclic paths, each path length being 3 cycles.

0135As can be understood, the number of the longest paths is reduced more in the case of <figref idref="DRAWINGS">FIG. 18A</figref> than the case of <figref idref="DRAWINGS">FIG. 18B</figref>. That is, for the case where the transfer instruction is inserted into a root node, the number of cyclic paths with longer path lengths can be reduced by the loop-carried dependence cut performed by the insertion of the transfer instruction into the root node that has more, longer cyclic paths. Consequently, the instruction placement constraint imposed during software pipelining can be eased.

0000[Cyclic Path Including a Plurality of Loop-Carried Dependences]

0136<figref idref="DRAWINGS">FIGS. 19A to 19C</figref> are diagrams showing changes before and after the insertion of a transfer instruction into a cyclic path that has a plurality of loop-carried dependences. In these diagrams, the true dependence is indicated by an arrow in a solid line whereas the loop-carried antidependence is indicated by an arrow in a short dashed line.

0137<figref idref="DRAWINGS">FIG. 19A</figref> shows a cyclic path that includes 2 loop-carried dependences, which exist respectively between the instructions c and b and between the instructions b and a. The path length of this cyclic path is 16 cycles as shown.

0138<figref idref="DRAWINGS">FIG. 19B</figref> shows a cycle path obtained after the instruction mov has been inserted into the root node a of the cyclic path shown in <figref idref="DRAWINGS">FIG. 19A</figref>. To be more specific. the cyclic path of 16 cycles with a dependence distance of 2 is divided into cyclic paths whose respective path lengths are 13 cycles and 4 cycles, with a dependence distance of 2. Note here, in this case, that the same register causes both the true dependence between the instructions a and d and the loop-carried dependence between the instruction b and a. In this way, the path length is shortened, thereby casing the instruction placement constraint imposed during software pipelining.

0139Meanwhile, <figref idref="DRAWINGS">FIG. 19C</figref> shows a cycle path obtained after the instruction mov has been inserted into the leaf node c of the cyclic path shown in <figref idref="DRAWINGS">FIG. 19A</figref> As shown, the cyclic path whose path length is 16 cycles with a dependence distance of 2 is eliminated. Accordingly, the instruction placement constraint imposed during software pipelining can be eased.

0140As described so far, according to the present invention, when a cyclic path includes at least one loop-carried antidependence, the path length can be shortened and the instruction placement constraint imposed during software pipelining can be eased, by the insertion of a transfer instruction into a leaf node or root node of the cyclic path. This allows software pipelining to be performed with enhanced speed and efficiency in the cases where the path length of the longest path or the resource constrained path length of the resource-constrained longest path can be shortened and the initiation interval of the loop process can also be shortened.

0141Although the compiler apparatus of the present invention has been described in the present embodiment, the present invention is not limited to this. For example, the above-mentioned loop-carried dependence cut may be performed more than once on the same loop, so that software pipelining can be executed with even more enhanced speed and efficiency.

0142Moreover, in the exclusion process performed on the cyclic path set in step S<b>403</b> shown in <figref idref="DRAWINGS">FIG. 8</figref>, the instruction selection unit <b>212</b> may exclude a cyclic path in which the latency of the root node is equal to or shorter than the latency of the transfer instruction. By doing so, the cyclic path whose path length would be longer by the insertion of the transfer instruction can be excluded in advance. This allows an appropriate cyclic path to be selected with enhanced speed and efficiency.

0143Furthermore, in the examples shown in <figref idref="DRAWINGS">FIGS. 5 to 7</figref>, the explanation was given as to the cases where the registers respectively causing the true dependence and causing the loop-carried antidependence for the leaf node or root node are different. However, these registers may be the same one register. <figref idref="DRAWINGS">FIG. 20</figref> is a diagram showing changes in a data dependence graph before and after the insertion of a transfer instruction into a cyclic path.

0144<figref idref="DRAWINGS">FIG. 20</figref> (a) shows a cyclic path that includes three instructions ldm, add, and stm. As shown in this diagram, the register as a parameter of the true dependence and the register as a parameter of the loop-carried antidependence in this cyclic path are the same, i.e., the register r<b>1</b>. <figref idref="DRAWINGS">FIG. 20</figref> (b) shows a cyclic path obtained after the instruction mov has been inserted into the root node, that is, the instruction ldm, of the cyclic path shown in <figref idref="DRAWINGS">FIG. 20</figref> (a). To be more specific, instead of the instruction ldm, an instruction “ldm r<b>0</b>: r<b>6</b>, (r<b>2</b>+)” is used. In this instruction, the register r<b>1</b> which is the parameter used by the instruction ldm for the loop-carried dependence is replaced with an unused register r<b>6</b>. Also, a transfer instruction “mov r<b>1</b>, r<b>6</b>” is inserted, so that the value stored in the register r<b>6</b> is stored into the register r<b>1</b> which is the original parameter. By this insertion of the instruction mov into the root node, the cyclic path whose path length was 4 cycles is divided into 2 cyclic paths whose respective path lengths are 3 cycles and 2 cycles. In this case, there is a possibility of shortening the initiation interval to 3 cycles.

0145Although only one exemplary embodiment of this invention has been described in detail above, those skilled in the art will readily appreciate that many modifications are possible in the exemplary embodiment without materially departing from the novel teachings and advantages of this invention. Accordingly, all such modifications are intended to be included within the scope of this invention.

INDUSTRIAL APPLICABILITY

0146The present invention can be applied to a compiler or the like whose target processor is capable of parallel processing.