US5835776A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for instruction scheduling in an optimizing compiler for minimizing overhead instructions
Assignee: Oracle America Inc
•
Filing: 1995-11-17
•
Granted: 1998-11-10
•
Expires: 2015-11-17
Abstract
Abstract Apparatus and methods are disclosed for scheduling target program instructions during the code optimization pass of an optimizing compiler. Most modern microprocessors have the ability to issue multiple instructions in one clock cycle and/or possess multiple pipelined functional units. They also have the ability to add two values to form the address within memory load and store instructions. In such microprocessors this invention can, where applicable, accelerate the execution of modulo-scheduled loops. The invention consists of a technique to achieve this speed up by systematically reducing the number of certain overhead instructions in modulo scheduled loops. The technique involves identifying reducible overhead instructions, scheduling the balance of the instructions with normal modulo scheduling procedures and then judiciously inserting no more than three copies of the reducible instructions into the schedule.
Inventors
- 👤 Partha P. Tirumalai
- 👤 Krishna Subramanian
- 👤 Boris Baylin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 20:23
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F8/4452
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
241 words
A computer system having a central processing unit (CPU) and random access memory (RAM) coupled to said CPU, for use in 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 computer system comprising: a compiler system resident in said computer system having a front end compiler, a code optimizer and a back end code generator; and an instruction partition mechanism coupled to said code optimizer configured to partition instructions for the target program into reducible instructions and non-reducible instructions; a modulo scheduler mechanism coupled to said code optimizer configured to modulo schedule said non-reducible instructions; an instruction insertion mechanism configured to directly insert a copy of one of 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 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.
Claim 2
Dependent Claim
241 words
A computer system having a central processing unit (CPU) and random access memory (RAM) coupled to said CPU, for use in 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 computer system comprising: a compiler system resident in said computer system having a front end compiler, a code optimizer and a back end code generator; and an instruction partition mechanism coupled to said code optimizer configured to partition instructions for the target program into reducible instructions and non-reducible instructions; a modulo scheduler mechanism coupled to said code optimizer configured to modulo schedule said non-reducible instructions; an instruction insertion mechanism configured to directly insert a copy of one of 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 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.
Claim 3
Dependent Claim
42 words
The computer system of claim 1 wherein the modulo scheduler mechanism coupled to said code optimizer configured to modulo schedule said non-reducible instructions is further configured to produce a modulo schedule having a prologue section, a kernel section and an epilogue section.
Claim 4
Dependent Claim
55 words
The computer system of claim 1 wherein the instruction insertion mechanism configured to directly insert said copy of said reducible instructions into a modulo schedule of said non-reducible instructions which is produced by said modulo scheduler mechanism will insert no more than three copies of a designated reducible instruction into said modulo scheduled reducible instructions.
Claim 5
Dependent Claim
59 words
The computer system of claim 2 wherein the instruction insertion mechanism configured to directly insert said copy of said reducible instructions into a modulo schedule of said non-reducible instructions which is produced by said modulo scheduler mechanism will insert no more than one copy of a designated reducible instruction into each said modulo scheduled prologue, kernel and epilogue sections.
Claim 6
Independent Claim
251 words
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.
Claim 7
Independent Claim
251 words
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.
Claim 8
Dependent Claim
231 words
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.
Claim 9
Dependent Claim
231 words
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.
Claim 10
Dependent Claim
196 words
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.
Claim 11
Dependent Claim
196 words
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.
Claim 12
Dependent Claim
45 words
The method of claim 7 wherein the step of directly inserting a copy of each reducible instruction into a schedule of the non-reducible instructions inserts at most one copy of the reducible instruction in each of the prologue, kernel and epilogue sections of the schedule.
Claim 13
Dependent Claim
78 words
The method of claim 8 wherein the step of directly inserting a copy of each reducible instruction into a schedule of the non-reducible instructions is performed by finding a vacant slot in the schedule, inserting the copy of the reducible instruction in the vacant slot, and setting the displacement of the copy to a new value which corresponds to a function of the original increment in the reducible instruction and the location of the copy in the schedule.
Claim 14
Dependent Claim
37 words
The method of claim 9 wherein the displacement of the copy is set to a new value which is equal to the value MaxUseInPrologue times OriginalDisplacement if the copy is located in the prologue of the schedule.
Claim 15
Dependent Claim
37 words
The method of claim 9 wherein the displacement of the copy is set to a new value which is equal to the value "KUF times OriginalDisplacement" if the copy is located in the kernel of the schedule.
Claim 16
Dependent Claim
37 words
The method of claim 9 wherein the displacement of the copy is set to a new value which is equal to the value "(StageCount-1-MaxUseInPrologue) times OriginalDisplacement" if the copy is located in the epilogue of the schedule.
Claim 17
Dependent Claim
137 words
The method of claim 7 wherein the step of modifying the original offset value of the address identifier of an identified non-reducible instruction which uses a designated reducible instruction, further comprises the steps of; determining which section of the schedule the using non-reducible instruction is in, the sections designated as the prologue, kernel and epilogue sections of the schedule; determining whether the copy of the reducible instruction which is used by the identified non-reducible instruction is placed in the schedule before or after the using non-reducible instruction; and adjusting the original offset value in the using non-reducible instruction by a value which is a function of the section of the schedule the using non-reducible instruction is in, and whether the using non-reducible instruction is located before or after a copy of the reducible instruction in the schedule.
Claim 18
Dependent Claim
238 words
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.
Claim 19
Dependent Claim
238 words
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.
Claim 20
Dependent Claim
63 words
The computer system of claim 1 wherein a reducible instruction is defined as an instruction which is an integral self-increment or self-decrement of an induction variable, wherein the induction variable is incremented and decremented by a compile-time known integer constant and wherein all uses of said instruction can be modified to have an immediate displacement representing the computed result of the reducible instruction.
Claim 21
Dependent Claim
62 words
The apparatus of claim 5 wherein a reducible instruction is defined as an instruction which is an integral self-increment or self-decrement of an induction variable, wherein the induction variable is incremented and decremented by a compile-time known integer constant and wherein all uses of said instruction can be modified to have an immediate displacement representing the computed result of the reducible instruction.
Claim 22
Dependent Claim
63 words
The code optimizer of claim 6 wherein a reducible instruction is defined as an instruction which is an integral self-increment or self-decrement of an induction variable, wherein the induction variable is incremented and decremented by a compile-time known integer constant and wherein all uses of said instruction can be modified to have an immediate displacement representing the computed result of the reducible instruction.
Claim 23
Dependent Claim
62 words
The method of claim 7 wherein a reducible instruction is defined as an instruction which is an integral self-increment or self-decrement of an induction variable, wherein the induction variable is incremented and decremented by a compile-time known integer constant and wherein all uses of said instruction can be modified to have an immediate displacement representing the computed result of the reducible instruction.
Claim 24
Dependent Claim
64 words
The computer program product of claim 14 wherein a reducible instruction is defined as an instruction which is an integral self-increment or self-decrement of an induction variable, wherein the induction variable is incremented and decremented by a compile-time known integer constant and wherein all uses of said instruction can be modified to have an immediate displacement representing the computed result of the reducible instruction.
References Cited (Backward Citations)
US5265253A
Cited
US5339238A
Cited
US5448737A
Cited
US5386562A
Cited
US5418958A
Cited
US5367651A
Cited
US5418959A
Cited
US5606698A
Cited
US5485616A
Cited
US5491823A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-09 | 2002-05-11 | 2002-11-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-09 | 2006-05-11 | 2006-11-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-09 | 2010-05-11 | 2010-11-10 | $7700.00 | Window Closed / Lapsed |