System and method for reducing the occurrence of window use overflow

• US 6,131,188 A
• Filed: 11/17/1999
• Issued: 10/10/2000
• Est. Priority Date: 12/22/1995
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Goebel, Kurt J.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US09/442,110
• Time in Patent Office: 328 Days
• Field of Search: 717/5, 717/6, 717/7, 717/8, 717/9, 712/202, 712/216, 712/217, 712/218, 712/244, 712/228
• US Class Current: 717/141
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

Program routines normally requiring windowed register allocation using conventional assembly code generation in a compiler are examined for eligibility for a wrapper routine optimization procedure in which wrapper routine assembly code instructions are generated in response to the application of high level programming language instructions specifying routines. If not eligible, the compiler generates assembly code instructions in a conventional way, allocating windowed registers to each routine. If the routine is eligible for wrapper routine optimization, the routine is further examined to determine whether the routine includes tail routine calls only or calls within the body of the routine. If the former, the routine is examined to determine whether local stack usage is required. For a routine having tail routine calls only and a requirement of local stack usage, wrapper routine assembly code instructions of a first type are generated. If the routine includes tail calls only and no requirement for local storage, wrapper routine assembly code instructions of a second type are generated. If the routine incorporates one or more calls within the body thereof, the routine is further examined to determine whether a live register is required over any of the calls. If so, wrapper routine assembly code instructions of a third type are generated. If the routine incorporates calls within the body thereof and a live register is not required over any call, wrapper routine assembly code instructions of a fourth type are generated.

Claims

1. A method of generating wrapper routine assembly code instructions for executing routines specified by a high level programming language, said method comprising the steps of:

(a) identifying a routine that is eligible for having wrapper routine assembly code instructions generated therefor;

(b) classifying the eligible routine identified in step (a) into one of a plurality of types of wrapper routines; and

(c) generating wrapper routine assembly code instructions for the eligible routine identified in step (a) and in accordance with the type of wrapper routine classified in step (b), wherein, if an overlap of each of a plurality of registered windows onto a next allocated register window occurs, a frame pointer of a previous register window is renamed to a stack pointer of a new register window so that execution of the wrapper routine assembly code instructions does not require use of a register window.

2. The method of claim 1 wherein if a routine is determined in step (a) not to be eligible for classification in step (b), generating assembly code instructions for the routine using conventional code generation.

3. The method of claim 1 wherein said step (b) of classifying includes the step (i) of determining whether the eligible routine incorporates tail routine calls only, where tail routine calls are routine calls which occur just prior to the routine exit.

4. The method of claim 3 wherein said step (i) of determining is followed by the step (ii) of determining whether the eligible routine requires local stack usage whenever said step (i) of determining results in a determination of only tail routine calls within the eligible routine.

5. The method of claim 4 wherein said step (ii) of determining is followed by the alternative steps of:

(A) generating wrapper routine assembly code instructions of a first type whenever local stack usage is deemed required by the eligible routine;

or

(B) generating wrapper routine assembly code instructions of a second type whenever local stack usage is deemed not required by the eligible routine.

6. The method of claim 3 wherein said step (i) of determining is followed by the step (iii) of determining whether the eligible routine requires a live register over a routine call whenever said step (i) of determining results in a determination of calls within the body of the eligible routine.

7. The method of claim 6 wherein said step (iii) of determining is followed by the alternative steps of:

(C) generating wrapper routine assembly code instructions of a third type whenever a live register is deemed required over a routine call;

or

(D) generating wrapper routine assembly code instructions of a fourth type whenever a live register is deemed not required over a routine call.

8. A computer system having a compiler for generating wrapper routine assembly code instructions for executing routines in said computer system, said routines specified by a high level programming language, said compiler comprising:

a first procedure for identifying a routine that is eligible for having wrapper routine assembly code instructions generated therefor;

a second procedure for classifying the eligible routine identified in the first procedure into one of a plurality of types of wrapper routines; and

a third procedure for generating wrapper routine assembly code instructions for the eligible routine identified in the first procedure and in accordance with the type of wrapper routine classified by the second procedure, wherein, if an overlap of each of a plurality of registered windows onto a next allocated register window occurs, a frame pointer of a previous register window is renamed to a stack pointer of a new register window so that execution of the wrapper routine assembly code instructions does not require use of a register window.

9. The computer system of claim 8 wherein said compiler further includes a fourth procedure for generating assembly code instructions for the routine using a conventional code generation technique whenever the routine is deemed ineligible for classification in the second procedure and for generating wrapper routine assembly code in the third procedure.

10. The computer system of claim 8 wherein said second procedure includes a procedure for determining whether the eligible routine incorporates tail routine calls only, where tail routine calls are routine calls which occur just prior to the routine exit.

11. The computer system of claim 10 wherein said second procedure further includes a procedure for determining whether the eligible routine requires local stack usage whenever a determination of tail routine calls only has been made.

12. The computer system of claim 11 wherein said third procedure further includes a procedure for generating wrapper routine assembly code instructions of a first type whenever local stack usage is deemed required by the eligible routine and for generating wrapper routine assembly code instructions of a second type whenever local stack usage is deemed not required by the eligible routine.

13. The computer system of claim 9 wherein said second procedure includes a procedure for determining whether the eligible routine requires a live register over a routine call whenever calls within the body of the eligible routine have been determined.

14. The computer system of claim 13 wherein said third procedure includes a procedure for generating wrapper routine assembly code instructions of a third type whenever a live register is deemed required over a routine call and generating wrapper routine assembly code instructions of a fourth type whenever a live register is deemed not required over a routine call.

15. A computer program product including:

a computer usable medium having computer readable code embodied therein for generating wrapper routine assembly code instructions for executing routines in a computer system, said routines specified by a high level programming language, the computer program product comprising;

a first set of computer readable program code devices configured to cause a computer to effect identification of a routine that is eligible for having wrapper routine assembly code instructions generated therefor;

a second set of computer readable program code devices configured to cause a computer to effect classification of the eligible routine identified by the first set of computer readable program code devices into one of a plurality of types of wrapper routines; and

a third set of computer readable program code devices configured to cause a computer to effect the generation of wrapper routine assembly code instructions for the eligible routine identified by the first set of computer readable program code devices and in accordance with the type of wrapper routine classified by said second set of computer readable program code devices, wherein, if an overlap of each of a plurality of registered windows onto a next allocated register window occurs, a frame pointer of a previous register window is renamed to a stack pointer of a new register window so that so that execution of the wrapper routine assembly code instructions does not require use of a register window.

16. The computer program product of claim 15 wherein said computer program product further includes a fourth set of computer readable program code devices configured to cause a computer to effect generation of assembly code instructions for the given routine using a conventional code generation technique whenever a given routine is deemed ineligible for classification by said second set of computer readable program code devices and generation of wrapper routine assembly code by said third set of computer readable program code devices.

17. The computer program product of claim 15 wherein said second set of computer readable program code devices is configured to cause a computer to effect a determination whether the eligible routine incorporates tail routine calls only, where tail routine calls are routine calls which occur just prior to the routine exit.

18. The computer program product of claim 17 wherein said second set of computer readable program code devices is configured to cause a computer to effect a determination whether the eligible routine requires local stack usage whenever a determination of tail routine calls only has been made.

19. The computer program product of claim 18 wherein said third set of computer readable program code devices is configured to cause a computer to effect generation of wrapper routine assembly code instructions of a first type whenever local stack usage is deemed required by the eligible routine and generation of wrapper routine assembly code instructions of a second type whenever local stack usage is deemed not required by the eligible routine.

20. The computer program product of claim 16 wherein said second set of computer readable program code devices is configured to cause a computer to effect a determination whether the given routine requires a live register over a routine call whenever calls within the body of the eligible routine have been determined.

21. The computer program product of claim 20 wherein said third set of computer readable program code devices is configured to cause a computer to effect the generation of wrapper routine assembly code instructions of a third type whenever a live register is deemed required over a routine call and generation of wrapper routine assembly code instructions of a fourth type whenever a live register is deemed not required over a routine call.