Patent US5339420A successfully refreshed from Google Patents.
US5339420A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Partitioning case statements for optimal execution performance
Assignee: International Business Machines Corp
•
Filing: 1991-02-01
•
Granted: 1994-08-16
•
Expires: 2011-02-01
Abstract
Abstract This invention permits an optimizing compiler to select optimal instruction sequences for handling the source level multi-way branch, commonly known as the case or switch statement. A costing heuristic is established, based on machine specific information, which weights the relative performance of instruction sequences used to perform statement selection from several available selection methods. The constants, which form the basis of the selection criteria, are then clustered into sets. This clustering is controlled by the costing heuristic. The resulting sets represent clusters of values for which a particular selection method is most appropriate. The invention is preferably implemented at the intermediate code level, and with appropriate preselection of parameters by the compiler builder, allows the invention to be used on any type of target machine. The use of the invention results in faster compilation and execution.
Inventors
- 👤 Steven M. Hoxey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 05:17
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
120 words
A method for optimizing the compiling of a program having multi-way branch statements, said method comprising the steps of: (a) selecting a multi-way branch statement from said multi-way branch statements; (b) examining said selected multi-way branch statement to determine the relative costs for each of a plurality of instruction sequences to implement said multi-way branch statement; (c) comparing the relative cost for executing each of said plurality of instruction sequences: (d) selecting one of said instruction sequences from said plurality of instruction sequences that carries the least cost; (e) implementing said selected least-cost instruction sequence in the compiled version of said program; and (f) repeating said steps (a) through (e) for each of said multi-way branch statements in said program.
Claim 2
Independent Claim
120 words
A method for optimizing the compiling of a program having multi-way branch statements, said method comprising the steps of: (a) selecting a multi-way branch statement from said multi-way branch statements; (b) examining said selected multi-way branch statement to determine the relative costs for each of a plurality of instruction sequences to implement said multi-way branch statement; (c) comparing the relative cost for executing each of said plurality of instruction sequences: (d) selecting one of said instruction sequences from said plurality of instruction sequences that carries the least cost; (e) implementing said selected least-cost instruction sequence in the compiled version of said program; and (f) repeating said steps (a) through (e) for each of said multi-way branch statements in said program.
Claim 3
Dependent Claim
25 words
A method as claimed in claim 1, in which said plurality of instruction sequences comprises range test, jump table, compare-and-branch, arithmetic progression and address translation.
Claim 4
Dependent Claim
20 words
A method as claimed in claim 1 wherein said costs include code of machine time required to execute said program.
Claim 5
Dependent Claim
29 words
A method as claimed in claim 1, further comprising setting a plurality of selection values according to parameters determined by a source text of said program to be compiled.
Claim 6
Dependent Claim
42 words
A method as claimed in claim 1, in which said step of comparing the relative cost is made by inserting values in a costing heuristic, and further comprising setting said values in said costing heuristic according to the architecture of said computer.
Claim 7
Dependent Claim
31 words
A method as claimed in claim 1 further comprising the steps of: establishing a costing heuristic; and clustering constants into sets from which said costing heuristic selects said lowest-cost instruction sequence.
Claim 8
Dependent Claim
107 words
An improved compiler for optimizing a program to be executed by a computer, said compiler comprising: (a) means for selecting a multi-way branch statement; (b) means for examining said multi-way branch statement to determine and compare the relative costs of executing each of a plurality of selection methods to determine which branch is to be taken by said program, where said plurality of selection methods comprise a jump table, range test, compare-and-branch, arithmetic progression and address translation; (c) means for selecting the least-cost selection method; and (d) means for implementing an instruction sequence corresponding to said selected least-cost selection method in the compiled version of said program.
Claim 9
Dependent Claim
107 words
An improved compiler for optimizing a program to be executed by a computer, said compiler comprising: (a) means for selecting a multi-way branch statement; (b) means for examining said multi-way branch statement to determine and compare the relative costs of executing each of a plurality of selection methods to determine which branch is to be taken by said program, where said plurality of selection methods comprise a jump table, range test, compare-and-branch, arithmetic progression and address translation; (c) means for selecting the least-cost selection method; and (d) means for implementing an instruction sequence corresponding to said selected least-cost selection method in the compiled version of said program.
Claim 10
Dependent Claim
22 words
An improved compiler as claimed in claim 7, in which said costs include cost of machine time required to execute said program.
References Cited (Backward Citations)
US5093916A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-15 | 1998-02-14 | 1998-08-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-15 | 2002-02-14 | 2002-08-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-15 | 2006-02-14 | 2006-08-16 | $7700.00 | Window Closed / Lapsed |