Patent US2640595A successfully refreshed from Google Patents.
Patent US5579520A successfully refreshed from Google Patents.
US5579520A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and methods for optimizing compiled code according to code object participation in program activities
Assignee: CODEGEAR LLC
•
Filing: 1994-05-13
•
Granted: 1996-11-26
•
Expires: 2014-05-13
Abstract
Abstract A development system having a compiler, a linker, an interface, and a code packing optimization module is described. The compiler generates or "compiles" source listings into object modules, which may be linked or combined with other object modules (e.g., stored in "library" files) to create an executable program. The optimization module embodies activity-based methods for generating a profile bitmap for a program of interest, to identify related code objects (i.e., procedures, functions, routines, and the like) based on clustering of activity bit signatures, so that related ones may be packed together in the executable program. A run of a program to be optimized is divided into a plurality of activities, typically those which are core to the operation of the program. A profile bitmap of the program is generated by running the target program through the various activities: for each code object "hit" during an activity a corresponding bit is set. In this manner, a bit signature is generated for each code object indicating which activities the code object has participated in. These patterns are then ordered, for identifying code objects of the program which should be clustered together. Given this order, related procedures may be located in contiguous or near-contiguous pages of the program by ordering them based on their bitmap signatures. In this manner, the efficiency of information retrieval operations (e.g., disk access, caching, and the like) is maximized.
Inventors
- 👤 John G. Bennett
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 03:19
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/40; G06F8/41; G06F8/44; G06F8/443; G06F8/54
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
142 words
In a system for operating computer programs, said programs comprising machine code having a plurality of procedures, a method for optimizing placement of procedures within a target program, the method comprising: (a) dividing execution of said target program into a plurality of activities which are based on operation of said target program by an end user, each of said activities requiring invocation of at least one procedure of said target program for completion of said each activity; (b) for each of said activities, executing said target program and at completion of said each activity, storing profile information for indicating which procedures of said target program were invoked for completion of said each activity; and (c) placing procedures which are invoked for a particular set of activities in contiguous locations of said target program, based on said profile information stored for each activity.
Claim 2
Dependent Claim
142 words
In a system for operating computer programs, said programs comprising machine code having a plurality of procedures, a method for optimizing placement of procedures within a target program, the method comprising: (a) dividing execution of said target program into a plurality of activities which are based on operation of said target program by an end user, each of said activities requiring invocation of at least one procedure of said target program for completion of said each activity; (b) for each of said activities, executing said target program and at completion of said each activity, storing profile information for indicating which procedures of said target program were invoked for completion of said each activity; and (c) placing procedures which are invoked for a particular set of activities in contiguous locations of said target program, based on said profile information stored for each activity.
Claim 3
Dependent Claim
19 words
The method of claim 1, wherein said activities are selected to represent core activities for operating said target program.
Claim 4
Dependent Claim
15 words
The method of claim 1, wherein said activities include user-invoked tasks of said target program.
Claim 5
Dependent Claim
28 words
The method of claim 1, wherein said plurality of activities comprises N number of activities, wherein N number of bits comprises a machine-word storage unit or multiple thereof.
Claim 6
Dependent Claim
31 words
The method of claim 4, wherein said machine-word storage unit is a selected one of an 8-bit unit, a 16-bit unit, a 32-bit unit, a 64-bit unit, and a 128-bit unit.
Claim 7
Dependent Claim
28 words
The method of claim 1, wherein said invocation of at least one procedure includes transferring program control to the procedure and executing machine code which comprises the procedure.
Claim 8
Dependent Claim
34 words
The method of claim 1, wherein said profile information comprises a profile bitmap, said profile bitmap providing a mapping between an activity and corresponding ones of said procedures required to complete said each activity.
Claim 9
Dependent Claim
29 words
The method of claim 1, wherein said profile information stores a reference count for each procedure for indicating how many times a particular procedure was invoked for each activity.
Claim 10
Dependent Claim
35 words
The method of claim 7, wherein said profile bitmap comprises a plurality of activity bit slices, each of said activity bit slices for identifying which of said procedures were invoked to complete a corresponding activity.
Claim 11
Dependent Claim
49 words
The method of claim 9, wherein step (c) includes: inverting said activity bit slices so that a bit signature is obtained for each procedure, for indicating which activities each procedure has been invoked for; and ordering the bit signatures so that procedures having identical bit signatures are clustered together.
Claim 12
Dependent Claim
26 words
The method of claim 10, wherein said ordering of bit signatures is based on a declining count of how many bits are set in each signature.
Claim 13
Dependent Claim
21 words
The method of claim 10, wherein said ordering of bit signatures is based on maximization of connectivity of neighboring bit signatures.
Claim 14
Dependent Claim
21 words
The method of claim 10, wherein said ordering of bit signatures is based on global maximization of connectivity between bit signatures.
Claim 15
Dependent Claim
41 words
The method of claim 1, wherein said target program is arranged in units of fixed-length pages, and wherein step (c) includes clustering procedures which are invoked for a particular set of activities into contiguous or near-contiguous pages of said target program.
Claim 16
Dependent Claim
26 words
The method of claim 14, wherein step (c) further includes padding pages as needed so that each group of clustered procedures begins on a page boundary.
Claim 17
Dependent Claim
161 words
In a development system for creating a computer program, said computer program comprising routines executable by a microprocessor, a method for optimizing ordering of said routines in the computer program, the method comprising: (a) dividing the program into a plurality of discrete activities, each activity representing a particular task of the program which occurs during actual use of the program by a user; (b) for each activity, generating a corresponding bit set, each bit in the bit set representing whether a call has been made to a particular routine during execution of said each activity; (c) determining a bit signature for each activity, each bit in said bit signature identifying which particular routines of the program have been called during execution of said each activity; (d) generating an ordered list of all bit signatures, for identifying which particular routines of the program are related based on activity; and (e) ordering said routines in the computer program according to said ordered list.
Claim 18
Dependent Claim
161 words
In a development system for creating a computer program, said computer program comprising routines executable by a microprocessor, a method for optimizing ordering of said routines in the computer program, the method comprising: (a) dividing the program into a plurality of discrete activities, each activity representing a particular task of the program which occurs during actual use of the program by a user; (b) for each activity, generating a corresponding bit set, each bit in the bit set representing whether a call has been made to a particular routine during execution of said each activity; (c) determining a bit signature for each activity, each bit in said bit signature identifying which particular routines of the program have been called during execution of said each activity; (d) generating an ordered list of all bit signatures, for identifying which particular routines of the program are related based on activity; and (e) ordering said routines in the computer program according to said ordered list.
Claim 19
Dependent Claim
28 words
The method of claim 16, wherein step (b) includes: for each activity, writing the corresponding bit set to a mass storage device upon completion of said each activity.
Claim 20
Dependent Claim
19 words
The method of claim 16, wherein said activities include tasks which are core to everyday operation of the program.
Claim 21
Dependent Claim
71 words
The method of claim 16, wherein step (b) includes: storing a handler routine for detecting when execution has begun for each routine of the program; and upon detecting that execution has begun for a particular routine for a currently executing activity, setting a corresponding bit in the bit set of said currently executing activity for representing that a call has been made to the particular routine during execution of said activity.
Claim 22
Dependent Claim
22 words
The method of claim 19, wherein said handler routine is invoked during execution of prologue code for each routine of the program.
Claim 23
Dependent Claim
28 words
The method of claim 19, wherein said handler routine is invoked in conjunction with a check routine which tests each routine of the program for memory stack overflow.
Claim 24
Dependent Claim
31 words
The method of claim 16, wherein step (d) includes: generating an ordered list of all bit signatures based on a declining count of how many bits are set in each signature.
Claim 25
Dependent Claim
26 words
The method of claim 16, wherein step (d) includes: generating an ordered list of all bit signatures based on maximization of connectivity of neighboring bit signatures.
Claim 26
Dependent Claim
26 words
The method of claim 16, wherein step (d) includes: generating an ordered list of all bit signatures based on global maximization of connectivity between bit signatures.
Claim 27
Dependent Claim
55 words
The method of claim 16, wherein each routine of the program is stored at one or more sequential page units, and wherein step (e) includes: ordering said routines in the computer program according to said ordered list, so that routines sharing an identical bit signature are stored contiguously in said page units of the program.
Claim 28
Dependent Claim
57 words
The method of claim 16, wherein routines of the program are stored in one or more code segments of the program, and wherein step (e) includes: ordering said routines in the computer program according to said ordered list, so that routines sharing an identical bit signature are stored contiguously in a particular code segment of the program.
Claim 29
Dependent Claim
31 words
The method of claim 16, wherein step (a) includes: dividing the program into N number of discrete activities, wherein N number of bits comprises a machine-word storage unit or multiple thereof.
Claim 30
Dependent Claim
53 words
The method of claim 16, further comprising: assigning a weighting to each activity for indicating importance of said each activity to execution of the program, so that in step (e), said ordering of said routines in the computer program is based on said ordered list and on said weighting assigned to each activity.
Claim 31
Dependent Claim
48 words
The method of claim 28, wherein the program includes a working set comprising routines of the program present in system memory, and wherein said working set for the program initially comprises routines for activities which are more important to execution of the program, as specified by said weighting.
Claim 32
Dependent Claim
15 words
The method of claim 16, wherein said activities include user-observable tasks of said target program.
References Cited (Backward Citations)
US5418954A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-26 | 2000-05-27 | 2000-11-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-26 | 2004-05-27 | 2004-11-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-26 | 2008-05-27 | 2008-11-26 | $7700.00 | Window Closed / Lapsed |