US5966539A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Link time optimization with translation to intermediate program and following optimization techniques including program analysis code motion live variable set generation order analysis, dead code elimination and load invariant analysis
Assignee: Hewlett Packard Development Co LP
•
Filing: 1997-11-03
•
Granted: 1999-10-12
•
Expires: 2017-11-03
Abstract
Abstract A computer system is directed to convert a program written as a plurality of high level source code modules into corresponding machine executable code. The source code modules are compiled into an object code module, and the object code modules are translated into a single linked code module in the form of a register translation language and logical symbol table compatible with a plurality of computer system hardware architectures. The source code program structures are recovered from the linked code module, and the linked code module is partitioned into a plurality of procedure, and instructions of each of the procedures grouped into basic blocks. A procedure flow graph is constructed for each of the procedures, and a program call graph is constructed for the linked code module. The linked code module is modified by eliminating dead code and moving loop-invariant code from loops. The modified linked code is converted into machine executable code compatible with a target one of said plurality of computer system hardware architectures.
Inventors
- 👤 Amitabh Srivastava
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 20:11
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/445; G06F8/43; G06F8/433; G06F8/443; G06F8/4434; G06F8/4435
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
71 words
A computer implemented method for optimizing machine executable code, comprising the steps of: generating machine executable code by linking compiled object code modules; translating said machine executable code into intermediate program code in the form of an intermediate language, said intermediate language having instructions independent of a particular computer system hardware architecture; and generating machine dependent executable code compatible with a target computer system hardware architecture from said intermediate program code.
Claim 2
Dependent Claim
71 words
A computer implemented method for optimizing machine executable code, comprising the steps of: generating machine executable code by linking compiled object code modules; translating said machine executable code into intermediate program code in the form of an intermediate language, said intermediate language having instructions independent of a particular computer system hardware architecture; and generating machine dependent executable code compatible with a target computer system hardware architecture from said intermediate program code.
Claim 3
Dependent Claim
22 words
The method as in claim 1 further including: modifying said intermediate program module to optimize the execution of said machine executable code.
Claim 4
Dependent Claim
54 words
The method as in claim 2 further comprising: identifying a first set of instructions of said intermediate program module which will not be executed; identifying a second set of instructions of said intermediate program module which compute values not used; and deleting said first and second set of instructions from said intermediate program module.
Claim 5
Dependent Claim
56 words
The method as in claim 2 further comprising: identifying a set of instructions of said intermediate program module which are to be executed repeatedly; locating instructions of said set of instructions which do not change a state of the computer while said set of instructions are executed; and moving such instructions from said set of instructions.
Claim 6
Dependent Claim
73 words
The method as in claim 1 further comprising: partitioning said instructions of said intermediate program module into a plurality of procedures, each procedure including instructions related for execution; constructing a program call graph for said plurality of procedures, said program call graph to indicate the flow of execution among said plurality of procedures; and applying said program call graph to said plurality of procedures to determine optimization opportunities in said plurality of procedures.
Claim 7
Dependent Claim
87 words
The method as in claim 5 further comprising: grouping instructions of each of said plurality of procedures into basic blocks, all instructions of a particular basic block to be executed if a first instruction of said particular basic block is executed; constructing a procedure flow graph for each procedure, a particular procedure flow graph to indicate the flow of execution among said basic blocks of a particular procedure; and applying said particular procedure flow graph to said particular procedure to determine optimization opportunities in said particular procedure.
Claim 8
Dependent Claim
87 words
The method as in claim 6 further comprising: for each basic block of said plurality of procedures, analyzing said plurality of procedures to generate a first set of variables which are live at the beginning of execution of each of said basic blocks and a second set of variables which are live at the end of execution of each of said basic block; and determining, in response to generating said first and second set of variables, an available register to use while optimizing said plurality of procedures.
Claim 9
Dependent Claim
58 words
The method as in claim 7 further comprising: in a first stage of said analyzing step, permitting liveliness information regarding said first and second set of variables to follow a forward flow of the execution path; and in a second stage of said analyzing step, permitting said liveliness information to follow a return flow of the execution path.
Claim 10
Dependent Claim
45 words
The method as in claim 8 further comprising: in said first stage, analyzing said procedures and said basic blocks in a reverse-depth-first order; and in said second stage, analyzing said procedures in a depth-first order, and analyzing said basic blocks in said reverse depth-first order.
Claim 11
Dependent Claim
101 words
The method as in claim 5 further comprising: identifying one of said plurality of procedures as a dominating procedure if said one of said plurality of procedures calls any other one of said plurality of procedure more than once; identifying a descendant procedure, said descendant procedure called by said dominating procedure, said descendant procedure and said dominating procedures being a loop region; identifying a step procedure of said loop region if said step procedure is called by any of said plurality of procedures other than said dominating procedure and said descendant procedure; and removing said step procedure from said loop region.
Claim 12
Dependent Claim
92 words
The method as in claim 10 further comprising: identifying specific instructions of said loop region as invariant instructions if said specific instructions do not change an execution and data state of the computer while executing said specific instructions of said loop region; determining the number of times each of said invariant instructions will be executed; sorting said invariant instructions by the number of times said invariant instructions will be executed; and moving said invariant instructions from said loop region in a sequence as determined by the sorted order of said invariant instructions.
Claim 13
Dependent Claim
80 words
In a computer system, a method for optimizing machine executable code, the machine executable code representing linked object code modules derived from a plurality of source code modules, each source code module being in the form of a high level language, comprising the steps of: translating said machine executable code into intermediate program code; optimizing said intermediate program code; and generating optimized machine dependent executable code compatible with a target computer system hardware architecture from said optimized intermediate program code.
Claim 14
Dependent Claim
80 words
In a computer system, a method for optimizing machine executable code, the machine executable code representing linked object code modules derived from a plurality of source code modules, each source code module being in the form of a high level language, comprising the steps of: translating said machine executable code into intermediate program code; optimizing said intermediate program code; and generating optimized machine dependent executable code compatible with a target computer system hardware architecture from said optimized intermediate program code.
Claim 15
Dependent Claim
28 words
The method as in claim 12 including: identifying instructions of said intermediate program module which will not be executed; and deleting such instructions from said intermediate program module.
Claim 16
Dependent Claim
183 words
The method as in claim 13 including: recovering source code structures from said intermediate program module; partitioning said instructions of said intermediate program module into a plurality of procedures, each procedure including instructions related for execution; constructing a program call graph, said program call graph to indicate the flow of execution among said plurality of procedures; identifying one of the plurality of procedures as a dominating procedure, said dominating procedure to call any other one of said plurality of procedures more than once; identifying a descendant procedure of said dominating procedure if said descendant procedure is called from said dominating procedure, said descendant procedures and said dominating procedures being a loop region; identifying said descendant procedure as a step procedure if said descendant procedure is called by any of said plurality of procedures other than said dominating procedure and said descendant procedure; removing said step procedure from said loop region; locating instructions in said loop region which do not change an execution state of the computer while the instructions of said loop region are executed; and removing such instructions from said loop region.
Claim 17
Dependent Claim
41 words
The method of claim 12 wherein the machine executable code is compatible with a first hardware architecture, and the machine dependent executable code is compatible with a second hardware architecture, said first and second hardware architectures being different from each other.
Claim 18
Independent Claim
61 words
A method for optimizing compiled machine executable code from a program, comprising the steps of: linking said compiled machine executable code; translating said linked compiled machine executable code into an intermediate code having instructions independent of a particular computer system hardware architecture; and generating optimized machine dependent executable code compatible with a target computer system hardware architecture using the intermediate code.
Claim 19
Independent Claim
61 words
A method for optimizing compiled machine executable code from a program, comprising the steps of: linking said compiled machine executable code; translating said linked compiled machine executable code into an intermediate code having instructions independent of a particular computer system hardware architecture; and generating optimized machine dependent executable code compatible with a target computer system hardware architecture using the intermediate code.
Claim 20
Dependent Claim
19 words
The method, as recited in claim 16, wherein said translating and generating steps are performed during said linking step.
Claim 21
Dependent Claim
23 words
The method, as recited in claim 16, further comprising the step of: modifying said intermediate module to optimize the execution of the program.
Claim 22
Dependent Claim
19 words
The method, as recited in claim 16, further comprising the step of: determining optimization opportunities in said intermediate module.
Claim 23
Dependent Claim
26 words
The method, as recited in claim 16, further comprising the step of: applying a constructed program call graph to determine optimization opportunities in said intermediate module.
Claim 24
Dependent Claim
29 words
The method, as recited in claim 16, further comprising the steps of: partitioning said intermediate module into a plurality of procedures; and performing optimization within and among said procedures.
References Cited (Backward Citations)
US4667290A
Cited
US4782444A
Cited
US5161216A
Cited
US5179702A
Cited
US5212794A
Cited
US5175856A
Cited
US5327561A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-11 | 2003-04-12 | 2003-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-11 | 2007-04-12 | 2007-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-11 | 2011-04-12 | 2011-10-12 | $7700.00 | Window Closed / Lapsed |