System and methods for optimizing compiled code according to code object participation in program activities

• US 5,579,520 A
• Filed: 05/13/1994
• Issued: 11/26/1996
• Est. Priority Date: 05/13/1994
• Status: Expired due to Term

• Current Assignee: CodeGear (Idera, Inc.)
• Original Assignee: Borland International, Inc. (Open Text Corporation)
• Inventors: Bennett, John G.
• Primary Examiner(s): Heckler, Thomas M.
• Assistant Examiner(s): BUTLER, DENNIS
• Application Number:
  US08/242,561
• Time in Patent Office: 928 Days
• Field of Search: 395/700
• US Class Current: 717/151
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/54 Link editing before load time

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.

Claims

1. 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.

2. The method of claim 1, wherein said activities are selected to represent core activities for operating said target program.

3. The method of claim 1, wherein said activities include user-invoked tasks of said target program.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. The method of claim 10, wherein said ordering of bit signatures is based on maximization of connectivity of neighboring bit signatures.

13. The method of claim 10, wherein said ordering of bit signatures is based on global maximization of connectivity between bit signatures.

14. 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.

15. 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.

16. 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.

17. 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.

18. The method of claim 16, wherein said activities include tasks which are core to everyday operation of the program.

19. 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.

20. The method of claim 19, wherein said handler routine is invoked during execution of prologue code for each routine of the program.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. The method of claim 16, wherein said activities include user-observable tasks of said target program.