Patent EP0354074A1 successfully refreshed from Google Patents.
Patent US1764962A successfully refreshed from Google Patents.
Patent US6070009A successfully refreshed from Google Patents.
US6070009A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for estimating execution rates of program execution paths
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1997-11-26
•
Granted: 2000-05-30
•
Expires: 2017-11-26
Abstract
Abstract A method is provided for estimating execution rates of program executions paths. The method samples path-identifying state information of selected instructions while executing the program in a processor. A control flow graph of the program is supplied, the control flow graph includes a plurality of path segments. The control flow graph is analyzed using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information. The set of paths segments can be counted to determine their relative execution frequencies.
Inventors
- 👤 Jeffrey Dean
- 👤 Robert A. Eustace
- 👤 James E. Hicks
- 👤 Carl A. Waldspurger
- 👤 William E. Weihl
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 20:14
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/30; G06F11/34; G06F11/3466; G06F11/3409; G06F11/3419; G06F11/3447; G06F2201/00; G06F2201/865; G06F2201/88
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
81 words
A method for estimating execution rates of program execution paths, comprising the steps of: sampling path-identifying state information of selected instructions while executing the program; supplying a control flow graph of the program, the control flow graph including a plurality of path segments; analyzing the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and counting the set of path segments to determine their relative execution frequencies.
Claim 2
Independent Claim
81 words
A method for estimating execution rates of program execution paths, comprising the steps of: sampling path-identifying state information of selected instructions while executing the program; supplying a control flow graph of the program, the control flow graph including a plurality of path segments; analyzing the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and counting the set of path segments to determine their relative execution frequencies.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the path-identifying state information includes identifications of the selected instructions.
Claim 4
Independent Claim
98 words
A method for estimating execution rates of program execution paths, comprising the steps of: sampling path-identifying state information of selected instructions while executing the program, wherein the path-identifying state information includes identifications of the selected instructions and addresses of the selected instructions; supplying a control flow graph of the program, the control flow graph including a plurality of path segments; analyzing the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and counting the set of path segments to determine their relative execution frequencies.
Claim 5
Independent Claim
98 words
A method for estimating execution rates of program execution paths, comprising the steps of: sampling path-identifying state information of selected instructions while executing the program, wherein the path-identifying state information includes identifications of the selected instructions and addresses of the selected instructions; supplying a control flow graph of the program, the control flow graph including a plurality of path segments; analyzing the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and counting the set of path segments to determine their relative execution frequencies.
Claim 6
Dependent Claim
19 words
The method of claim 3 wherein the path-identifying state information includes identification of a process executing the selected instruction.
Claim 7
Dependent Claim
15 words
The method of claim 3 wherein the path-identifying state information includes an address space number.
Claim 8
Dependent Claim
17 words
The method of claim 3 wherein the path-identifying state information includes a hardware context or thread identifier.
Claim 9
Dependent Claim
16 words
The method of claim 3 wherein the path-identifying state information includes recent branch taken/not-taken history information.
Claim 10
Dependent Claim
29 words
The method of claim 3 wherein the path-identifying state information includes information produced by applying a function to address bits of recently processed instructions of particular classes of instructions.
Claim 11
Dependent Claim
23 words
The method of claim 8 wherein the particular classes of instructions include branch instructions, indirect branch instructions, call instructions, and indirect call instructions.
Claim 12
Dependent Claim
23 words
The method of claim 3 wherein the path-identifying state information includes information identifying a plurality of instructions executed within a specified time interval.
Claim 13
Dependent Claim
17 words
The method of claim 10 wherein the path-identifying state information includes addresses of the plurality of instructions.
Claim 14
Dependent Claim
140 words
A computer program product for estimating execution rates of program execution paths, the computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: a first set of instructions that sample path-identifying state information of selected instructions of the program while executing the program; a second set of instructions that supply a control flow graph of the program, the control flow graph including a plurality of path segments; a third set of instructions that analyze the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and a fourth set of instructions that count the set of path segments to determine their relative execution frequencies.
Claim 15
Dependent Claim
140 words
A computer program product for estimating execution rates of program execution paths, the computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: a first set of instructions that sample path-identifying state information of selected instructions of the program while executing the program; a second set of instructions that supply a control flow graph of the program, the control flow graph including a plurality of path segments; a third set of instructions that analyze the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and a fourth set of instructions that count the set of path segments to determine their relative execution frequencies.
Claim 16
Dependent Claim
21 words
The computer program product of claim 12 wherein the path-identifying state information includes identifications of the selected instructions of the program.
Claim 17
Dependent Claim
157 words
A computer program product for estimating execution rates of program execution paths, the computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: a first set of instructions that sample path-identifying state information of selected instructions of the program while executing the program, wherein the path-identifying state information includes identifications of the selected instructions and addresses of the selected instructions; a second set of instructions that supply a control flow graph of the program, the control flow graph including a plurality of path segments; a third set of instructions that analyze the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and a fourth set of instructions that count the set of path segments to determine their relative execution frequencies.
Claim 18
Dependent Claim
157 words
A computer program product for estimating execution rates of program execution paths, the computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising: a first set of instructions that sample path-identifying state information of selected instructions of the program while executing the program, wherein the path-identifying state information includes identifications of the selected instructions and addresses of the selected instructions; a second set of instructions that supply a control flow graph of the program, the control flow graph including a plurality of path segments; a third set of instructions that analyze the control flow graph using the path-identifying state information to identify a set of path segments that are consistent with the sampled state information; and a fourth set of instructions that count the set of path segments to determine their relative execution frequencies.
Claim 19
Dependent Claim
21 words
The computer program product of claim 14 wherein the path-identifying state information includes identification of a process executing the selected instruction.
Claim 20
Dependent Claim
17 words
The computer program product of claim 14 wherein the path-identifying state information includes an address space number.
Claim 21
Dependent Claim
19 words
The computer program product of claim 14 wherein the path-identifying state information includes a hardware context or thread identifier.
Claim 22
Dependent Claim
18 words
The computer program product of claim 14 wherein the path-identifying state information includes recent branch taken/not-taken history information.
Claim 23
Dependent Claim
34 words
The computer program product of claim 14 wherein the path-identifying state information includes information produced by applying a function to address bits of recently processed instructions of particular classes of instructions of the program.
Claim 24
Dependent Claim
25 words
The computer program product of claim 19 wherein the particular classes of instructions include branch instructions, indirect branch instructions, call instructions, and indirect call instructions.
Claim 25
Dependent Claim
28 words
The computer program product of claim 14 wherein the path-identifying state information includes information identifying a plurality of instructions of the program executed within a specified time interval.
Claim 26
Dependent Claim
22 words
The computer program product of claim 21 wherein the path-identifying state information includes addresses of the plurality of instructions of the program.
References Cited (Backward Citations)
US4590550A
Cited
US4845615A
Cited
US5103394A
Cited
US4821178A
Cited
US5151981A
Cited
US5572672A
Cited
US5450586A
Cited
US5479652A
Cited
US5479652B1
Cited
US5651112A
Cited
US5485574A
Cited
US5493673A
Cited
US5446876A
Cited
US5581482A
Cited
US5528753A
Cited
US5537541A
Cited
US5764970A
Cited
US5809450A
Cited
US5923872A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |