Method of constructing a constant-folding mechanism in a multilanguage optimizing compiler

• US 5,836,014 A
• Filed: 05/16/1994
• Issued: 11/10/1998
• Est. Priority Date: 02/27/1991
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Faiman, Robert Neil Jr.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/243,560
• Time in Patent Office: 1,639 Days
• Field of Search: 395/700, 395/600, 395/200, 395/650, 395/705, 395/707, 395/708, 395/709
• US Class Current: 717/156
• 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 comprises a generic compiler back end which may be used by a plurality of front ends to generate object code for a target computer system. Each front end scans and parses a source module containing source code for a programming language, and generates an intermediate language representation that describes the source code. The intermediate language representation is input to the generic compiler back end which performs optimization and code generation for a plurality of target computer systems. "Constant folding" optimization is performed by the generic compiler back end, and comprises finding occurrences of expressions that can be reduced to a constant and calculated at compile time rather than at runtime. One mechanism for performing constant folding, also referred to as K-folding, uses a KFOLD routine that is built by the compiler framework. The KFOLD routine is constructed using a special front end that produces an intermediate language representation of the KFOLD routine which may be used by the generic back end to produce a corresponding object file for one of a plurality of target computer systems. The special front end produces the intermediate language representation for the KFOLD routine using as input the intermediate language comprising intermediate language operators.

Claims

1. A method executed in a computer system for producing an object module comprising a constant-folding routine, said method comprising the steps of:

generating a flow graph that represents a constant-folding routine in an intermediate language using a compiler front end and an intermediate language input, said intermediate language being a universal language used by a plurality of compiler front ends to represent source code and including operators and data types used to describe said source code, each compiler front end corresponding to a different programming language, said intermediate language input describing said intermediate language and comprising said operators and said data types of said intermediate language, said constant-folding routine included in a code optimizer to evaluate a constant expression and to replace said constant expression with an equivalent expression yielding a same result as said constant expression, said constant expression being comprised of at least one of said operators or said data types; and

producing an object module that contains machine instructions of said constant-folding routine using said flow graph as an input to a code generator, said code generator being a common code generator used by each of said plurality of front ends to generate an object module using a flow graph.

2. The method of claim 1, wherein said code generator generates code for a plurality of different target computer systems, wherein a target computer system is one in which said constant-folding routine is executed.

3. The method of claim 1, wherein said generating step further comprises operating the compiler front end in a mode that suppresses translation of source code and enables generation of said flow graph representing said constant-folding routine, and wherein said flow graph is composed of tuples.

4. The method of claim 1 further comprising providing said plurality of compiler front ends, each compiler front end accepting input source code for a different programming language and performing said generating step to generate a flow graph that represents said input source code in said intermediate language.

5. A method performed in a host computer system having a memory for compiling source code and producing a corresponding object module, the method comprising the steps of:

generating a first flow graph that is stored in said memory by performing an execution flow analysis of said source code, said first flow graph representing said source code in an intermediate language, said intermediate language being a universal language used by a plurality of compiler front ends to represent source code and including operators and data types used to described said source code, each of said plurality of compiler front ends corresponding to a different programming language;

generating a second flow graph that contains an optimized representation of said first flow graph by detecting a constant expression in said first flow graph and executing a constant-folding routine which evaluates said constant expression and replaces said constant expression with an equivalent expression yielding a same result as said constant expression, said constant expression including at least one of said operators or said data types, said second flow graph being stored in said memory; and

producing said corresponding object module by using said second flow graph as input to a code generator that produces said corresponding object module for a target computer system, said corresponding object module including machine instructions for execution in said target computer system, said code generator being a common code generator used by a plurality of front ends to generate an object module using a flow graph;

and wherein said constant-folding routine is produced by performing the steps of;

generating, using a compiler front end and an intermediate language input to said compiler front end, a third flow graph that represents said constant-folding routine in said intermediate language, said intermediate language input describing said intermediate language and comprising said operators and said data types of said intermediate language, said compiler front end being one of said plurality of compiler front ends; and

producing a constant-folding object module using said third flow graph as an input to said code generator.

6. A method according to claim 5 wherein said intermediate language comprises tuples, each tuple representing a corresponding single expression in said source code.

7. A method according to claim 6, wherein said second flow graph comprises one or more blocks, each block including a sequence of tuples with no entry or exit between the first and last tuple of said sequence.

8. A method according to claim 7, wherein each of said sequence of tuples begins with a tuple representing a routine entry point or representing a label and ends with a tuple representing a routine return or representing a transfer of runtime execution control to another label.

9. A method according to claim 6, wherein each of said tuples is a data structure comprising fields that represent an operator, an operator data type, and one or more operands.

10. A method according to claim 9 wherein said intermediate language input to said compiler front end includes data types supported by said target computer system.

11. The method according to claim 9, wherein said intermediate language input comprises a table of information describing operators and operator data types that may be represented in a tuple.

12. An apparatus for use in a host computer system having a memory for compiling source code and producing a corresponding object module, the apparatus comprising:

A) a first compiler front end performing an execution flow analysis of said source code and producing a first flow graph that is stored in said memory, said first flow graph representing said source code in an intermediate language including operators and data types used to describe said source code;

B) a compiler back end, coupled to said first compiler front end, said compiler back-end comprising;

i) optimizing means that uses said first flow graph as input for producing a second flow graph that contains an optimized representation of said first flow graph, said second flow graph representing said source code in said intermediate language and being stored in said memory; and

ii) code generator means, coupled to said optimizing means, for generating said corresponding object module using said second flow graph as input;

said optimizing means comprising constant-folding means executing a constant-folding routine for detecting and evaluating a constant expression in said second flow graph and replacing said constant expression with an equivalent expression yielding a same result as said constant expression, said constant expression being comprised of at least one of said operators or said data types, said corresponding object module comprising machine instructions for execution in said target computer system; and

C) means for generating said constant-folding routine comprising;

i) a second compiler front end for generating a third flow graph that represents said constant-folding routine in said intermediate language, said third flow graph being generated using said operators of said intermediate language as input; and

ii) said compiler back end, using said third flow graph as input and coupled to said second compiler front end, for generating an object file containing machine instructions for said constant-folding routine.

13. Apparatus of claim 12, wherein said intermediate language comprises tuples, each tuple representing a single expression in said source code.

14. Apparatus of claim 12, wherein each of said tuples are data structures in said memory, each tuple comprising fields that represent an operator, one or more operands, and a data type of said single expression.

15. Apparatus of claim 14, wherein said second compiler front end is said first compiler front end operating in a processing mode for generating said third flow graph, and wherein said input to said second compiler front end comprises a table of operators that are represented in a tuple of said intermediate language and data types that may be generated by said first compiler front end.

16. An apparatus used in a computer system for producing an object module comprising a constant-folding routine, said apparatus comprising:

generating means for generating a flow graph that represents said constant-folding routine in an intermediate language using a compiler front end and an intermediate language input, said intermediate language being a universal language used by a plurality of compiler front ends to represent source code and including operators and data types used to describe said source code, each compiler front end corresponding to a different programming language, said intermediate language input describing said intermediate language and comprising said operators and said data types of said intermediate language, said constant-folding routine included in a code optimizer to evaluate a constant expression and to replace said constant expression with an equivalent constant expression yielding a same result as said constant expression, said constant expression being comprised of at least one of said operators or said data types; and

producing means for producing said object module using said flow graph as an input to a code generator, said code generator being a common code generator used by said plurality of compiler front ends to generate an object module using a flow graph.

17. The apparatus of claim 16, wherein said code generator generates code for a plurality of different target computer systems in which said constant-folding routine is executed.

18. The apparatus of claim 16, wherein said compiler front end operates in a mode that suppresses translation of source code and enables generation of said flow graph representing said constant-folding routine, and said flow graph being composed of tuples.

19. An apparatus for compiling source code in a host computer system with a memory and producing a corresponding object module, the apparatus comprising:

generating means for generating a first flow graph that is stored in said memory by performing an execution flow analysis of said source code, said first flow graph representing said source code in an intermediate language, said intermediate language being a universal language used by a plurality of compiler front ends to represent source code and including operators and data types used to described said source code, each of said plurality of compiler front ends corresponding to a different programming language;

generating means for generating a second flow graph that contains an optimized representation of said first flow graph by detecting a constant expression in said first flow graph and executing a constant-folding routine which evaluates and replaces said constant expression with an equivalent expression yielding a same result as said constant expression, said constant expression being comprised of at least one of said operators or said data types, said third flow graph being stored in said memory; and

producing means for producing said corresponding object module by using said second flow graph as input to a code generator that produces said corresponding object module for a target computer system, said corresponding object module including machine instructions for execution in said target computer system, said code generator being a common code generator used by a plurality of front ends to generate an object module using a flow graph;

and wherein said constant-folding routine is produced using;

a compiler front end and an intermediate language input to said compiler front end for generating a third flow graph that represents said constant-folding routine in said intermediate language, said intermediate language input describing said intermediate language and comprising said operators and said data types of said intermediate language; and

said code generator, using said third flow graph as an input, for generating a constant-folding object module comprising machine instructions for said constant-folding routine.