Method and apparatus for instruction scheduling in an optimizing compiler for minimizing overhead instructions

An apparatus for optimizing the execution time of executable instructions in a target program which is designated to run on a target computer architecture having a plurality of parallel computation units which facilitate instruction pipelining and which provides an ability to add two values to form an address used in a memory load or store instruction and which permits two or more instructions to be issued in a single clock cycle, said apparatus comprising:

• a computer having a processor, a memory, and an input/output section;
• a compiler system resident in said computer memory having a front end compiler, a code optimizer and a back end code generator;
• and
• an instruction partition mechanism coupled to said computer for use by said code optimizer to partition instructions for the target program into reducible instructions and non-reducible instructions;
• a modulo scheduler mechanism coupled to said computer for use by said code optimizer to modulo schedule said non-reducible instructions;
• an instruction insertion mechanism configured to directly insert said reducible instructions into a modulo schedule of said non-reducible instructions which is produced by said modulo scheduler mechanism;
• and
• an instruction modification mechanism coupled to said computer for use by said code optimizer configured to identify one or more of scheduled non-reducible instructions which would normally use a value produced by a designated reducible instruction and said instruction modification mechanism further configured to modify an original offset in an address portion of said identified one or more of scheduled non-reducible instructions which use a designated reducible instruction.

A code optimizer for use in an compiler system for compiling a target program to run on a target computer architecture having a plurality of parallel computation units which facilitate instruction pipelining and which provides an ability to add two values to form an address used in a memory load or store instruction and which permits two or more instructions to be issued in a single clock cycle, said code optimizer comprising:

• a first portion configured to accept as input an intermediate code representation of said target program;
• a second portion, coupled to said first portion, configured to partition instructions for the target program into reducible instructions and non-reducible instructions;
• a third portion, coupled to said second portion configured to modulo schedule said non-reducible instructions;
• a fourth portion, coupled to said third portion configured to directly insert copies of said reducible instructions into a modulo schedule of said non-reducible instructions which is produced by said third portion;
• and
• a fifth portion, coupled to said fourth portion configured to identify one or more of scheduled non-reducible instructions which would normally use a value produced by a designated reducible instruction and said fifth portion further configured to modify an original offset in an address portion of said identified one or more of scheduled non-reducible instructions which use a designated reducible instruction, thereby producing a schedule of the executable instructions for the target program.

A computer controlled method of scheduling the executable instructions of a target program directed at a target computer architecture having a plurality of parallel computation units which facilitate instruction pipelining and which provides an ability to add two values to form an address used in a memory load or store instruction and which permits two or more instructions to be issued in a single clock cycle, the schedule produced in a manner that reduces the number of executable instructions required in the schedule, said method comprising the steps of:

• partitioning target program instructions to be compiled into a set of reducible instructions and a set of non-reducible instructions;
• modulo scheduling the set of non-reducible instructions;
• directly inserting a copy of each reducible instruction into a schedule of the non-reducible instructions;
• for a copy of a designated reducible instruction inserted into the schedule, identifying all scheduled non-reducible instructions which use the designated reducible instruction;
• and
• modifying the original offset value of the address identifier of an identified non-reducible instruction which uses a designated reducible instruction, thereby producing a schedule of executable instructions for the target program which contains a minimum number of copies of each reducible instruction.

A computer program product comprising:

• a computer usable medium having computer readable program code mechanisms embodied therein to schedule the executable instructions of a target program directed at a target computer architecture having a plurality of parallel computation units which facilitate instruction pipelining and which provides an ability to add two values to form an address used in a memory load or store instruction and which permits two or more instructions to be issued in a single clock cycle, the schedule produced in a manner that reduces the number of executable instructions required in the schedule, the computer readable program code mechanisms in said computer program product comprising:
• computer readable code mechanisms to cause a computer to partition instructions for a loop in the target program into reducible instructions and non-reducible instructions;
• computer readable code mechanisms to cause the computer to modulo schedule said non-reducible instructions;
• and
• computer readable code mechanisms to cause the computer to directly insert said reducible instructions into a modulo schedule of said non-reducible instructions which is produced by said modulo scheduler mechanism;
• and
• computer readable code mechanisms to cause the computer to identify one or more of scheduled non-reducible instructions which would normally use a value produced by a designated reducible instruction and said instruction modification mechanism further to modify an original offset in an address portion of said identified one or more of scheduled non-reducible instructions which use a designated reducible instruction.