US5901308A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Software mechanism for reducing exceptions generated by speculatively scheduled instructions
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1996-03-18
•
Granted: 1999-05-04
•
Expires: 2016-03-18
Abstract
Abstract A method of compiling an application to reduce the occurrence of speculative exceptions is described. The method includes the steps of compiling the application to provide a speculation table and an executable file, and obtaining profile information about said compiled application using representative data sets. The compiler includes a scheduler unit for rearranging the order of the instructions in the application to provide optimal performance. The speculation table comprises a number of entries corresponding to the instructions of the application, each entry including a tag identifying the instruction and a semaphore indicating whether or not the instruction is likely to cause an exception. The executable file is run using a number of representative data sets to profile information identifying those instructions that result in exceptions, and the tag of the instruction is stored in a log file. After the profiling has completed, the tags of the instructions causing exceptions are used to set the semaphores in the speculation table corresponding to the tag. The application is then re-compiled. During the recompilation, those instructions with their semaphores set; i.e. those instructions causing exceptions, will not be speculatively scheduled by the compiler.
Inventors
- 👤 Robert Cohn
- 👤 Michael C. Adler
- 👤 Paul Geoffrey Lowney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 16:28
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F11/00; G06F11/30; G06F11/34; G06F11/3466; G06F9/00; G06F9/06; G06F9/30; G06F9/38; G06F9/3836; G06F9/3842; G06F9/3861
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
67 words
A method comprising the steps of: compiling source code into an executable application comprising a plurality of instructions in an order of maximum speculation; executing said executable application based on a plurality of data sets and storing exception characteristics of each instruction; and recompiling said source code using said stored exception characteristics to determine a portion of said plurality of instructions which should not be speculatively scheduled.
Claim 2
Independent Claim
67 words
A method comprising the steps of: compiling source code into an executable application comprising a plurality of instructions in an order of maximum speculation; executing said executable application based on a plurality of data sets and storing exception characteristics of each instruction; and recompiling said source code using said stored exception characteristics to determine a portion of said plurality of instructions which should not be speculatively scheduled.
Claim 3
Dependent Claim
74 words
The method according to claim 1, wherein the source code includes the plurality of instructions having a first order, and wherein said step of compiling comprises the step of providing the executable application having the plurality of instructions in a second order that is different than the first order, the second order having each non-branch instruction of the plurality of instructions moved before as many branch instructions as possible relative to the first order.
Claim 4
Dependent Claim
38 words
The method according to claim 1, wherein said step of recompiling further comprises the step of selecting instructions of said source code for reordering, said instructions selected for re-ordering responsive to said associated exception characteristics of said instruction.
Claim 5
Dependent Claim
33 words
The method according to claim 3, further comprising the step of providing a speculation table having an entry for each of said instructions, said entry for storing said exception characteristics of said instruction.
Claim 6
Dependent Claim
30 words
The method according to claim 4, wherein each entry of said speculation table further comprises a semaphore for indicating whether said instruction may be scheduled speculatively by said recompile step.
Claim 7
Dependent Claim
23 words
The method according to claim 5, wherein said semaphore is set during said profiling step responsive to said exception characteristics exceeding a threshold.
Claim 8
Dependent Claim
40 words
The method according to claim 4, wherein said source code further comprises a stream of instructions, and wherein the step of recompiling further comprises the step of optimizing said stream of instructions to provide improved performance of said executable application.
Claim 9
Dependent Claim
40 words
The method according to claim 7, wherein said optimizing step further comprises the steps of: replicating one of said instructions; and when replicating said one of said instructions, additionally replicating said exception characteristics corresponding to said one of said instructions.
Claim 10
Dependent Claim
64 words
The method according to claim 1, wherein the plurality of instructions includes a first set of initialization instructions that initializes variables used during execution of the executable application, and wherein the method further comprises the step of: adding a second set of initialization instructions to said executable application, said second set of initialization instructions initializing said variables used during execution of said executable application.
Claim 11
Independent Claim
28 words
The method according to step 9, wherein said second set of initialization instructions initialize the variables in an attempt to cause exceptions during execution of said executable application.
Claim 12
Independent Claim
28 words
The method according to step 9, wherein said second set of initialization instructions initialize the variables in an attempt to cause exceptions during execution of said executable application.
Claim 13
Dependent Claim
69 words
The method of claim 1, wherein the step of executing and storing includes the step of generating an exception log for each of the plurality of data sets, and wherein the method further comprises the step of: merging the exception log for each of the plurality of data sets to form a merged log having aggregate exception counts for each of the plurality of instructions of the executable application.
Claim 14
Dependent Claim
33 words
The method of claim 11, further comprising the step of: comparing the aggregate exception counts of the merged log to a predetermined threshold to identify instructions of the source code for non-speculative scheduling.
Claim 15
Dependent Claim
37 words
The method of claim 12, wherein the step of recompiling includes the step of: speculatively scheduling an instruction that causes an exception when an aggregate exception count associated with that instruction is less than the predetermined threshold.
Claim 16
Dependent Claim
59 words
The method of claim 1, wherein a first instruction precedes a second instruction in program order within the source code, wherein the first instruction initializes a particular variable and the second instruction uses the particular variable, and wherein the step of compiling includes the step of: ordering the second instruction ahead of the first instruction within the executable application.
Claim 17
Independent Claim
164 words
An apparatus comprising: a memory that stores source code; a processor coupled to said memory; a compiler program, stored in said memory, for compiling the source code into an executable application when the compiler program is executed by the processor, said compiler program including: a translation unit for translating the source code stored in said memory into a translated program comprising a stream of instructions; an optimization unit for optimizing said translated program to provide enhanced performance of said processor; a scheduler unit for rearranging said stream of instructions in an order of maximum speculation upon an initial compile of the source code; and means for providing a speculation table, said speculation table comprising a plurality of entries corresponding to said stream of instructions, each entry for storing exception characteristics of said associated instruction, said exception characteristics used by said compiler program to determine a portion of said stream of instructions which should not be speculatively scheduled upon retranslation of said stream of instructions.
Claim 18
Independent Claim
164 words
An apparatus comprising: a memory that stores source code; a processor coupled to said memory; a compiler program, stored in said memory, for compiling the source code into an executable application when the compiler program is executed by the processor, said compiler program including: a translation unit for translating the source code stored in said memory into a translated program comprising a stream of instructions; an optimization unit for optimizing said translated program to provide enhanced performance of said processor; a scheduler unit for rearranging said stream of instructions in an order of maximum speculation upon an initial compile of the source code; and means for providing a speculation table, said speculation table comprising a plurality of entries corresponding to said stream of instructions, each entry for storing exception characteristics of said associated instruction, said exception characteristics used by said compiler program to determine a portion of said stream of instructions which should not be speculatively scheduled upon retranslation of said stream of instructions.
Claim 19
Dependent Claim
27 words
The apparatus of claim 15 wherein said compiler program further comprises: means, responsive to said speculation table, for providing a recompiled application for execution on said processor.
Claim 20
Dependent Claim
76 words
The apparatus of claim 16, further comprising: means for generating a log file, stored in memory, for storing profile information incurred by executing said executable application using a variety of data sets, wherein said log file includes a plurality of program counters of instructions in said executable application and a count associated with each of said program counters, said count indicating the number of exceptions incurred during execution of said executable application using said data sets.
Claim 21
Dependent Claim
50 words
The apparatus of claim 17, further comprising: means for cross-referencing said program counters in said log file against a tag of each of said instructions; and means for updating said exception characteristics of each instruction of said speculation table responsive to said cross-referencing means and responsive to said log file.
Claim 22
Dependent Claim
63 words
The apparatus of claim 15, wherein the stream of instructions includes a first set of initialization instructions that initializes variables used during execution of the executable application, and wherein said compiler further comprises: initialization means for adding a second set of initialization instructions to said executable application said second set of initialization instructions initializing said variables used during execution of said executable application.
Claim 23
Dependent Claim
27 words
The apparatus of claim 19, wherein said second set of initialization instructions initialize the variables in an attempt to cause exceptions during execution of said executable application.
Claim 24
Dependent Claim
70 words
The apparatus of claim 15, further comprising: exception log generation code that, when executed by the processor, generates an exception log for each of the plurality of data sets; and merge code that, when executed by the processor, merges the exception log for each of the plurality of data sets to form a merged log having aggregate exception counts for each of the plurality of instructions of the executable application.
Claim 25
Dependent Claim
38 words
The apparatus of claim 21, further comprising: compare code that, when executed by the processor, compares the aggregate exception counts of the merged log to a predetermined threshold to identify instructions of the source code for non-speculative scheduling.
Claim 26
Dependent Claim
41 words
The apparatus of claim 22, wherein, during a recompile of the source code, the compiler is adapted to speculatively schedule an instruction that causes an exception when an aggregate exception count associated with that instruction is less than the predetermined threshold.
Claim 27
Dependent Claim
64 words
The apparatus of claim 15, wherein a first instruction precedes a second instruction in program order within the source code, wherein the first instruction initializes a particular variable and the second instruction uses the particular variable, and wherein the compiler is adapted to order the second instruction ahead of the first instruction within the executable application during an initial compile of the source code.
Claim 28
Dependent Claim
27 words
The apparatus of claim 15 wherein said scheduler unit further comprises: means for rearranging said instructions such that all of said instructions are moved before preceding branches.
Claim 29
Dependent Claim
21 words
The apparatus of claim 15 wherein said scheduler unit further comprises: means for precluding rearrangement of instructions having undesirable exception characteristics.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-03 | 2002-11-02 | 2003-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-03 | 2006-11-02 | 2007-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-03 | 2010-11-02 | 2011-05-04 | $7700.00 | Window Closed / Lapsed |