US5526499A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Speculative load instruction rescheduler for a compiler which moves load instructions across basic block boundaries while avoiding program exceptions
Assignee: International Business Machines Corp
•
Filing: 1994-12-27
•
Granted: 1996-06-11
•
Expires: 2014-12-27
Abstract
Abstract An instruction scheduler for a computer, capable of speculatively scheduling load instructions by moving certain categories of load instructions in an input instruction sequence from a source block of instructions to a target block of instructions to form an output instruction sequence, the instruction scheduler comprising: logic for selecting a data-independent load instruction as a candidate for rescheduling; logic for determining whether the base register that the load instruction makes use of and/or the contents thereof meets any one of a number of conditions; logic for moving the selected load instruction from the source block to the target block in response to determination that any one of the conditions is met.
Inventors
- 👤 David Bernstein
- 👤 Martin E. Hopkins
- 👤 Michael Rodeh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 15:04
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/3004; G06F9/30043; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F9/38; G06F9/3836; G06F9/3842
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
236 words
An instruction scheduler for rescheduling an input instruction sequence to form an output instruction sequence to run on a computer, the instruction scheduler speculatively scheduling load instructions by moving certain categories of load instructions from a source block of instructions in the input instruction sequence to a target block of instructions to form the output instruction sequence, a speculatively scheduled load instruction being a load instruction which has been moved from a position in the input instruction sequence that is later than a conditional branch instruction to a position in the output instruction sequence which is earlier than said conditional branch instruction, each of the load instructions making use of a base register having contents for determining a source address from which to load, the instruction scheduler comprising: logic for selecting a data-independent load instruction as a candidate load instruction for speculative rescheduling to a target block; logic for determining whether the base register that the candidate load instruction makes use of and/or the contents thereof meets any one of a number of conditions, each of which assure that speculative movement of the candidate load instruction to the target block will not cause a program exception if the candidate load instruction is executed in the target block; and logic for speculatively moving the candidate load instruction from the source block to the target block in response to determination that any one of the conditions is met.
Claim 2
Dependent Claim
236 words
An instruction scheduler for rescheduling an input instruction sequence to form an output instruction sequence to run on a computer, the instruction scheduler speculatively scheduling load instructions by moving certain categories of load instructions from a source block of instructions in the input instruction sequence to a target block of instructions to form the output instruction sequence, a speculatively scheduled load instruction being a load instruction which has been moved from a position in the input instruction sequence that is later than a conditional branch instruction to a position in the output instruction sequence which is earlier than said conditional branch instruction, each of the load instructions making use of a base register having contents for determining a source address from which to load, the instruction scheduler comprising: logic for selecting a data-independent load instruction as a candidate load instruction for speculative rescheduling to a target block; logic for determining whether the base register that the candidate load instruction makes use of and/or the contents thereof meets any one of a number of conditions, each of which assure that speculative movement of the candidate load instruction to the target block will not cause a program exception if the candidate load instruction is executed in the target block; and logic for speculatively moving the candidate load instruction from the source block to the target block in response to determination that any one of the conditions is met.
Claim 3
Dependent Claim
32 words
An instruction scheduler as claimed in claim 1 wherein one of the conditions is that the base register contains a pointer to a memory area where addresses of global variables are stored.
Claim 4
Dependent Claim
99 words
An instruction scheduler as claimed in claim 1 wherein one of the conditions is that both (a) the base register of the candidate load instruction be the same register as is being used as the base register of another load instruction within the target block and (b) there does not exist any instruction that changes the contents of this register in the path between the target block and the source block, the instruction scheduler further including means for allocating an extra dummy page, defined in read only mode, in front of and after each data segment of a program.
Claim 5
Dependent Claim
92 words
An instruction scheduler as claimed in claim 1 for forming an output instruction sequence to run on a computer having an operating system wherein page zero is defined in read only mode, and a finite number of bytes of page zero are filled with zeros, one of the conditions being that both (a) the contents of the base register of the candidate load instruction equals zero and (b) the contents of the base register not be changed in the path between the target block of instructions and the source block of instructions.
Claim 6
Dependent Claim
25 words
An instruction scheduler as claimed in claim 4 wherein the finite number of bytes of page zero are the first 64 bytes of page zero.
Claim 7
Dependent Claim
21 words
A compiler for compiling code to run on a computer, the compiler including all instruction scheduler as claimed in claim 1.
Claim 8
Dependent Claim
11 words
A computer including an instruction scheduler as claimed in claim 1.
Claim 9
Dependent Claim
13 words
A computer as claimed in claim 7 having a superscalar and/or superpipelined architecture.
Claim 10
Independent Claim
210 words
A method of rescheduling an input program instruction sequence, wherein said rescheduling allows load instructions to be speculatively scheduled, a speculatively scheduled load instruction being a load instruction which has been moved from a position in the input program instruction sequence that is later than a conditional branch instruction to a position in an output instruction sequence which is earlier than said conditional branch instruction, the input instruction sequence being partitioned into blocks of instructions and containing load instructions, each of the load instructions making use of a base register having contents for determining a source address from which to load, the method comprising: a. selecting a data-independent load instruction from a source block of instructions as a candidate load instruction for speculative movement to a target block of instructions; b. determining whether the base register the candidate load instruction makes use of or the contents thereof satisfies any one of a number of conditions, each of which assures that speculative movement of the candidate load instruction to the target block cannot cause a program exception if the candidate load instruction is executed in the target block; and if so, c. speculatively rescheduling the input program instruction sequence by moving the candidate load instruction to the target block of instructions.
Claim 11
Independent Claim
210 words
A method of rescheduling an input program instruction sequence, wherein said rescheduling allows load instructions to be speculatively scheduled, a speculatively scheduled load instruction being a load instruction which has been moved from a position in the input program instruction sequence that is later than a conditional branch instruction to a position in an output instruction sequence which is earlier than said conditional branch instruction, the input instruction sequence being partitioned into blocks of instructions and containing load instructions, each of the load instructions making use of a base register having contents for determining a source address from which to load, the method comprising: a. selecting a data-independent load instruction from a source block of instructions as a candidate load instruction for speculative movement to a target block of instructions; b. determining whether the base register the candidate load instruction makes use of or the contents thereof satisfies any one of a number of conditions, each of which assures that speculative movement of the candidate load instruction to the target block cannot cause a program exception if the candidate load instruction is executed in the target block; and if so, c. speculatively rescheduling the input program instruction sequence by moving the candidate load instruction to the target block of instructions.
Claim 12
Dependent Claim
108 words
A method, as claimed in claim 9, wherein the determining step (b) comprises the substeps of: (b1) identifying the base register of the candidate load instruction; (b2) determining whether or not the base register is redefined in the path from the source block to the target block, and if so the condition being deemed not to be satisfied; (b3) identifying the conditional register which is used in the branch of the target block; (b4) identifying the compare instruction that sets the condition register; (b5) determining whether or not the compare instruction compares the base register to zero, and if it does, the condition being deemed to be satisfied.
References Cited (Backward Citations)
US4435753A
Cited
US4656582A
Cited
US5133077A
Cited
US5093916A
Cited
US5202995A
Cited
US5119495A
Cited
US5202975A
Cited
US5303357A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-11 | 1999-12-11 | 2000-06-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-11 | 2003-12-11 | 2004-06-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-11 | 2007-12-11 | 2008-06-11 | $7700.00 | Window Closed / Lapsed |