Optimizing compiler using templates corresponding to portions of an intermediate language graph to determine an order of evaluation and to allocate lifetimes to temporary names for variables

• US 5,613,117 A
• Filed: 04/20/1994
• Issued: 03/18/1997
• Est. Priority Date: 02/27/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Grove, Richard B., Davidson, Caroline S., Hobbs, Steven O.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): WEINSTEIN, MARC
• Application Number:
  US08/231,441
• Time in Patent Office: 1,063 Days
• Field of Search: 395/700, 395/500, 364/200, 364/900
• US Class Current: 717/144
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/447 Target code generation

Abstract

A compiler framework uses a generic "shell" and a generic back end (where the code generator is target-specific). The generic back end provides the functions of optimization, register and memory allocation, and code generation. The code generation function of the back end may be targeted for any of a number of computer architectures. A front end is tailored for each different source language, such as Cobol, Fortran, Pascal, C, C++, etc. The front end scans and parses the source code modules, and generates from them an intermediate language representation of the source code programs expressed in the source code. The intermediate language represents any of the source code languages in a universal manner, so the interface between the front end and back end is of a standard format, and need not be rewritten for each language-specific front end. A feature is a method for doing code generation using code templates in a multipass manner. The selection and application of code templates occurs at four different times during the compilation process: (1) A pattern select phase does a pattern match in a context pass to select the best code templates; (2) Tasks of the context pass use context actions of the selected templates to analyze the evaluation order to expressions and to allocate temporary names; (3) A bind pass uses the binding actions of the selected templates to allocate template names; (4) Finally, a code pass uses code generation actions of the selected templates to guide the generation of object code.

Claims

1. A method of performing code generation executed in a computer system comprising the steps of:

matching a portion of an intermediate language graph with a code template, said portion of said intermediate language graph comprising a plurality of tuples and being a representation of a first source program in an intermediate language, each tuple representing a single operation to be performed in said first source program, said code template including a predetermined intermediate language pattern which corresponds to said portion of said intermediate language graph to guide in generating a part of a first object module that corresponds to said first source program;

analyzing said portion of said intermediate language graph to determine an order of evaluation of an expression in said portion of said intermediate language graph using actions which are included in said code template and which indicate said order of evaluation;

allocating, using said actions in accordance with said order of evaluation, a temporary name for a variable and assigning an allocation lifetime to said temporary name, said allocation lifetime indicating the extent to which the temporary name and the storage of the temporary name are associated with said variable in said intermediate language graph;

updating at least one of said plurality of tuples in said portion of said intermediate language graph as needed to perform said analyzing and said allocating steps as indicated by said actions; and

generating machine language instructions that are included in said part of said object module by using said actions and said intermediate language graph having at least one updated tuple.

2. The method of claim 1, wherein said temporary name is one of a local temporary or non-local temporary name, said local temporary name being a variable allocation with a lifetime limited to said portion of said intermediate language graph, said non-local temporary name being a variable allocation with a lifetime that extends beyond said portion of said intermediate language graph.

3. The method of claim 2, wherein said matching step is performed during a first pass over said portion of said intermediate language graph, said analyzing step and said allocating step for allocating non-local temporary names are performed during a second pass over said portion of said intermediate language graph, said portion being updated and producing a modified portion of said intermediate language graph, said allocating step for allocating local temporary names is performed during a third pass using said modified portion of said intermediate language graph, said modified portion being updated and producing another modified portion of said intermediate language, and said generating step is performed during a fourth pass over said other modified portion of said intermediate language graph.

4. The method of claim 3, wherein each of said second, said third, and said fourth passes is performed by an action interpreter that uniquely processes a part of said actions for said each pass.

5. The method of claim 3, wherein said actions include one or more undelayed actions and one or more delayed actions, said undelayed actions being performed prior to said delayed actions for each of said second, said third, and said fourth passes and producing a processing result which is used in one of said delayed actions.

6. The method of claim 1, wherein one of said actions indicates that said variable associated with said temporary name is stored in a memory.

7. The method of claim 1, wherein one of said actions indicates that said variable associated with said temporary name is stored in a register.

8. The method of claim 1, wherein said predetermined language pattern includes a result value mode, a pattern tree, a sequence of boolean tests, and a cost of the code generated by said code template, said result value mode indicating the result value computed by said portion of said first object module, said pattern tree describing operators and operands of said predetermined intermediate language pattern, said sequence of boolean tests representing statements about said portion of said intermediate language graph that must be true for said predetermined intermediate language pattern to be matched to said portion, said cost being represented as an integer and indicating a performance cost associated with said portion of generated code.

9. The method of claim 8, wherein said matching step includes comparing a cost associated with said code template and another cost associated with another code template, and choosing one of said code template and said other code template with the minimum associated cost.

10. The method of claim 1, wherein said first object module is for a first target computer system and wherein the method of claim 1 is used to produce a second object module for another target computer system, said second object module corresponding to a second source program different from said first source program.

11. A compiler for use in a computer to perform code generation during the compiling of a source program to produce a corresponding object module, the compiler comprising:

a code comparator which matches a portion of an intermediate language graph with a code template, said intermediate language graph comprising tuples and being a representation of a first source program in an intermediate language, each tuple representing a single operation to be performed in said first source program, said code template including a predetermined intermediate language pattern which corresponds to said portion of said intermediate language graph to guide in generating a part of a first object module that corresponds to said first source program;

a code analyzer for analyzing said portion of said intermediate language graph to determine an order of evaluation of an expression in said portion of said intermediate language graph using actions which are included in said code template and which indicate said order of evaluation;

an allocator that uses said actions in accordance with said order of evaluation to allocate a temporary name for a variable and assigning an allocation lifetime to said temporary name, said allocation lifetime indicating the extent to which the temporary name and the storage of the temporary name are associated with said variable in said intermediate language graph;

means for updating a tuple in said portion of said intermediate language graph as needed by the analyzer and the allocator to perform, respectfully, the analyzing and the allocating as indicated by said actions; and

means for generating machine language instructions that are included in said part of said object module by using said actions and said intermediate language graph having updated tuples.

12. The apparatus of claim 11, wherein said allocator further includes a local temporary name allocator and a non-local temporary name allocator, said local temporary name allocator allocating variables with a lifetime limited to said portion of said intermediate language graph, said non-local temporary name allocator allocating variables with a lifetime that extends beyond said portion of said intermediate language graph.

13. The apparatus of claim 11, wherein said predetermined language pattern includes a result value mode, a pattern tree, a sequence of boolean tests, and a cost of the code generated by said code template, said result value mode indicating the result value computed by said portion of said first object module, said pattern tree describing operators and operands of said predetermined intermediate language pattern, said sequence of boolean tests representing statements about said portion of said intermediate language graph that must be true for said predetermined intermediate language pattern to be matched to said portion, said cost being represented as an integer and indicating a performance cost associated with said portion of generated code.

14. The apparatus of claim 11, wherein said first object module is for a first target computer system and wherein the apparatus of claim 11 is used to produce a second object module for another target computer system, said second object module corresponding to a second source program different from said first source program.