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

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

What is claimed is:

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.

Description

RELATED CASES

This application discloses subject matter also disclosed in the following copending applications, filed herewith and assigned to Digital Equipment Corporation, the assignee of this application:

Ser. No. 662,461, filed Feb. 27, 1991, by Robert Neil Faiman, Jr., David Scott Blickstein and Steven Hobbs, for "INTERFACE FOR REPRESENTING EFFECTS IN A MULTILANGUAGE OPTIMIZING COMPILER"; (PD90-0364), now U.S. Pat. No. 5,493,675.

Ser. No. 662,477, filed Feb. 27, 1991, by Dennis Joseph Murphy and Robert Neil Faiman, Jr., for "INTERFACE FOR SYMBOL TABLE CONSTRUCTION IN A MULTILANGUAGE OPTIMIZING COMPILER"; (PD90-0366), abandoned and continuation filed on Ser. No. 08/243,615, May 16, 1994 and Ser. No. 08/364,437, Dec. 24, 1994.

Ser. No. 662,483, filed Feb. 27, 1991, by David Scott Blickstein, for "ANALYZING INDUCTIVE EXPRESSIONS IN A MULTILANGUAGE OPTIMIZING COMPILER"; (PD90-0368), now U.S. Pat. No. 5,577,253.

Ser. No. 662,464, filed Feb. 27, 1991, by Caroline Sweeney Davidson, Richard Barry Grove and Steven Hobbs, for "MULTILANGUAGE OPTIMIZING COMPILER USING TEMPLATES IN MULTIPLE PASS CODE GENERATION". (PD90-0369), abandoned and continuation filed as Ser. No. 08/231,441 on Apr. 20, 1994.

BACKGROUND OF THE INVENTION

This invention relates to compilers for digital computer programs, and more particularly to a compiler framework that is adapted to be used with a number of different computer languages, to generate code for a number of different target machines.

Compilers are usually constructed for translating a specific source language to object code for execution on a specific target machine which has a specific operating system. For example, a Fortran compiler may be available for generating code for a computer having the VAX architecture using the VMS operating system, or a C compiler for a 80386 computer executing MS/DOS. Intermediate parts of these language- and target-specific compilers share a great deal of common structure and function, however, and so construction of a new compiler can be aided by using some of the component parts of an existing compiler, and modifying others. Nevertheless, it has been the practice to construct new compilers for each combination of source language and target machine, and when new and higher-performance computer architectures are designed the task of rewriting compilers for each of the commonly-used source languages is a major task.

The field of computer-aided software engineering (CASE) is heavily dependent upon compiler technology. CASE tools and programming environments are built upon core compilers. In addition, performance specifications of computer hardware are often integrally involved with compiler technology. The speed of a processor is usually measured in high-level language benchmarks, so therefore optimizing compilers can influence the price-performance factor of new computer equipment.

In order to facilitate construction of compilers for a variety of different high-level languages, and different target computer architectures, it is desirable to enhance the commonality of core components of the compiler framework. The front end of a compiler directly accesses the source code module, and so necessarily is language-specific; a compiler front end constructed to interpret Pascal would not be able to interpret C. Likewise, the code generator in the back end of a compiler has to use the instruction set of the target computer architecture, and so is machine-specific. Thus, it is the intermediate components of a compiler that are susceptible to being made more generic. compiler front end usually functions to first translate the source code into an intermediate language, so that the program that was originally written in the high-level source language appears in a more elemental language for the internal operations of the compiler. The front end usually produces a representation of the program or routine, in intermediate language, in the form of a so-called graph, along with a symbol table. These two data structures, the intermediate language graph and the symbol table, are the representation of the program as used internally by the compiler. Thus, by making the intermediate language and construction of the symbol table of universal or generic character, the components following the front end can be made more generic.

After the compiler front end has generated the intermediate language graph and symbol table, various optimizing techniques are usually implemented. The flow graph is rearranged, meaning the program is rewritten, to optimize speed of execution on the target machine. Some optimizations are target-specific, but most are generic. Commonly-used optimizations are code motion, strength reduction, etc. Next in the internal organization of a compiler is the register and memory allocation. Up to this point, data references were to variables and constants by name or in the abstract, without regard to where stored; now, however, data references are assigned to more concrete locations, such as specific registers and memory displacements (not memory addresses yet). At this point, further optimizations are possible, in the form of register allocation to maintain data in registers are minimize memory references; thus the program may be again rearranged to optimize register usage. Register allocation is also somewhat target machine dependent, and so the generic nature of the compiler must accommodate specifying the number, size and special assignments for the register set of the target CPU. Following register and memory allocation, the compiler implements the code generation phase, in which object code images are produced, and these are of course in the target machine language or instruction set, i.e., machine-specific. Subsequently, the object code images are linked to produce executable packages, adding various run-time modules, etc., all of which is machine-specific.

In a typical compiler implementation, it is thus seen that the structure of the intermediate language graph, and the optimization and register and memory allocation phases, are those most susceptible to being made more generic. However, due to substantive differences in the high-level languages most commonly used today, and differences in target machine architecture, obstacles exist to discourage construction of a generic compiler core.

SUMMARY OF THE INVENTION

In accordance with one embodiment of the invention, a compiler framework is provided which uses a generic "shell" or control and sequencing mechanism, and a generic back end (where the code generator is of course target-specific). The generic back end provides the functions of optimization, register and memory allocation, and code generation. The shell may be executed on various host computers, and 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++, Ada, etc. The front end scans and parses the source code modules, and generates from them an intermediate language representation of the programs expressed in the source code. This intermediate language is constructed to represent 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.

The intermediate language representation generated by the front end is based upon a tuple as the elemental unit, where each tuple represents a single operation to be performed, such as a load, a store, an add, a label, a branch, etc. A data structure is created by the front end for each tuple, with fields for various necessary information. Along with the ordered series of tuples, the front end generates a symbol table for all references to variables, routines, labels, etc., as is the usual practice. The tuples are in ordered sequences within blocks, where a block is a part of the code that begins with a routine or label and ends in a branch, for example, where no entry or exit is permitted between the start and finish of a block. Each block is also a data structure, or node, and contains pointers to its successors and predecessors (these being to symbols in the symbol table). The interlinked blocks make up a flow graph, called the intermediate language graph, which is the representation of the program used by the back end to do the optimizations, register and memory allocations, etc.

One of the features of the invention is a mechanism for representing effects and dependencies in the interface between front end and back end. A tuple has an effect if it writes to memory, and has a dependency if it reads from a location which some other node may write to. Various higher level languages have differing ways of expressing operations, and the same sequence may in one language allow a result or dependency, while in another language it may not. Thus, a mechanism which is independent of source language is provided for describing the effects of program execution. This mechanism provides a means for the compiler front end to generate a detailed language-specific information to the multi-language optimizer in the compiler back end. This mechanism is used by the global optimizer to determine legal and effective optimizations, including common subexpression recognition and code motions. The intermediate language and structure of the tuples contain information so that the back end (optimizers) can ask questions of the front end (obtain information from the intermediate language graph), from which the back end can determine when the execution of the code produced for the target machine for one tuple will affect the value computed by code for another tuple. The interface between back end and front end is in this respect language independent. The back end does not need to know what language it is compiling. The advantage is that a different back end (and shell) need not be written for each source language, but instead an optimizing compiler can be produced for each source language by merely tailoring a front end for each different language.

Another feature of one embodiment of the invention is the use in the optimization part of the compiler of a method for analyzing induction variables. A variable is said to be an induction variable if it increments or decrements once every time through the loop, and is executed at most once each time through the loop. In addition to finding induction variables, this optimization finds inductive expressions, which are expressions that can be computed as linear functions of induction variables. The object of this optimization is generally to replace multiplications with additions, which are cheaper execute faster on most architectures); this is known as strength reduction. Detection of induction variables requires the use of "sets" of potential induction variables; doing this dynamically for each loop is an expensive and complicated operation, so the improvement here is to use the side effects sets used to construct IDEF sets.

An additional feature of one embodiment of the invention is a mechanism for "folding constants" (referred to as K-folding or a KFOLD routine), included as one of the optimizations. This mechanism is for finding occurrences where expressions can be reduced to a constant and calculated at compile time rather than a more time-consuming calculation during runtime. An important feature is that the KFOLD code is built by the compiler framework itself rather than having to be coded or calculated by the user. The KFOLD builder functions as a front end, like the other language-specific front ends, but there is no source code input; instead, the input is in intermediate language and merely consists of a listing of all of the operators and all of the data types. The advantage is that a much more thorough KFOLD package can be generated, at much lower cost.

A further feature of one embodiment is the type definition mechanism, referred to a the TD module. This module provides mechanisms used by the front end and the compiler of the back end in constructing program type information to be incorporated in an object module for use by a linker or debugger. The creation of "type information" takes place in the context of symbol table creation and allows a front end to specify to the back end an abstract representation of program type information. The TD module provides service routines that allow a front end to describe basic types and abstract types.

In addition, a feature of one embodiment 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) The pattern select or PATSELECT phase does a pattern match in the CONTEXT pass to select the best code templates; (2) The TNASSIGN and TNLIFE tasks of the CONTEXT pass use context actions of the selected templates to analyze the evaluation order to expressions and to allocate temporary names (TNs) with lifetimes nonlocal to the code templates; (3) The TNBIND pass uses the binding actions of the selected templates to allocate TNs with lifetimes local to the code templates; (4) Finally, the CODE pass uses code generation actions of the selected templates to guide the generation of object code.

BRIEF DESCRIPTION OF THE DRAWINGS

The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as other features and advantages thereof, will be best understood by reference to the detailed description of specific embodiments which follows, when read in conjunction with the accompanying drawings, wherein:

FIG. 1 is a schematic representation of a compiler using features of the invention;

FIG. 2 is an electrical diagram in block form of a host computer upon which the methods of various features of the invention may be executed;

FIG. 3 is a diagrammatic representation of code to be compiled by the compiler of FIG. 1, in source code form, intermediate language form, tree from, and assembly language form;

FIG. 4 is a diagrammatic representation of the data structure of a tuble used in the compiler of FIG. 1;

FIG. 5 is a logic flow chart of the operation of the shell of FIG. 1;

FIG. 6 is an example listing of code containing constants; and

FIG. 7 is a diagram of data fields and relationships (pointers) for illustrating type definition according to one feature of the invention.

FIG. 8 is a schematic representation showing a special front end.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

Referring to FIG. 1, the compiler framework 10 according to one embodiment of the invention is a language-independent framework for the creation of portable, retargetable compilers. The compiler framework 10 consists of a portable operating system interface referred to as the shell 11 and a retargetable optimizer and code generator 12 (the back end). The shell 11 is portable in that can be adapted to function with any of several operating systems such as VAX/VMS, Unix, etc., executing on the host computer. The shell operates under this host operating system 13 executing on a host computing system as seen in FIG. 2, typically including a CPU 14 coupled to a main memory 15 by a system bus 16, and coupled to disk storage 17 by an I/O controller 18. The shell 11 and compiler 12 may be combined with a front end 20 to create a portable, retargetable compiler for a particular source language. Thus, a compiler based on the framework 10 of the invention consists of three basic parts: a shell 11 which has been tailored for a particular host operating system 14--this determines the host environment of the compiler; a front end 20 for a particular source language (e.g., C, C++, Pascal, Fortran, Ada, Cobol, etc.)--this determines the source language of the compiler; and a back end 12 for a particular target machine (i.e., a particular architecture such as VAX, RISC, etc.)--this determines the target machine of the compiler.

Since the interfaces between the shell 11, the front end 20, and the back end 12 are fixed, the individual components of a compiler produced according to the invention may be replaced freely. That is, the front end 20 may consist of a number of interchangeable front ends, e.g., one for Fortran, one for Cobol, one for Pascal, one for C, etc. Likewise, a shell 11 tailored for running under VMS on a VAX computer may be replaced by a shell 11 running under the Unix operating system on a RISC workstation, while the front end 20 and back end 12 remain the same.

The shell 11 provides a fixed interface between the host operating system 13 and the rest of the compiler. The shell provides several advantages according to the invention. First, the shell 11 provides a portable interface to basic features of the operating system 13. For example, the front end 20 need not know details of the file system, command parsing, or heap storage allocation under the host operating system 13, since all these services are accessed through shell routines, and the shell is tailored to the operating system 13 being used. Second, the shell 11 eliminates duplication of effort by providing a single implementation of some common compiler components, such as command line parsing, include-file processing, and diagnostic file generation. Third, the use of these common components also guarantees consistency among compilers created using the framework 10; all compilers created using this framework 10 will write listing files in the same format, will treat command line qualifiers the same, will issue similar-looking error messages, etc. Fourth, having common shell utilities in the shell 11 improves the internal integration of the compiler, since the front and back ends 20 and 12 use the same shell functions. For example, use of the shell locator package means that source file locations can be referred to consistently in the source listing, front-end generated diagnostics, back-end generated diagnostics, the object listing, and the debugger information.

The front end 20 is the only component of a compiler created by the framework 10 which understands the source language being compiled. This source language is that used to generate the text of a source code file or files (module or modules) 21 which define the input of the compiler. The front end 20 performs a number of functions. First, it calls the shell 11 to obtain command line information and text lines from the source files 21. Second, the front end 20 calls the shell 11 to control the listing file, write diagnostic messages, and possibly to write other files for specific languages. Third, the front end 20 does lexical, syntactic, and semantic analysis to translate the source text in file 21 to a language-independent internal representation used for the interface 22 between the front end 20 and the back end 12. Fourth, the front end 20 invokes the back end 12 to generate target system object code 23 from the information in the internal representation. Fifth, the front end 20 provides routines which the back end 12 calls via call path 24 to obtain language-specific information during back end processing. Not included in the compiler framework of FIG. 1 is a linker which links the object code modules or images 23 to form an executable image to run on the target machine 25.

The target machine 25 for which the back end 12 of the compiler creates code is a computer of some specific architecture, i.e., it has a register set of some specific number and data width, the logic executes a specific instruction set, specific addressing modes are available, etc. Examples are (1) the VAX architecture, as described in (2) a RISC type of architecture based upon the 32-bit RISC chip available from MIPS, Inc., as part number R2000 or R3000 and described by Lane in "MIPS R2000 RISC Architecture", Printice-Hall, 1987, and (3) an advanced RISC architecture with 64-bit registers as described in copending application Ser. No. 547,589, filed Jun. 29, 1990. Various other architectures would be likewise accommodated.

In general, the front end 20 need not consider the architecture of the target machine 25 upon which the object code 23 will be executed, when the front end 20 is translating from source code 15 to the internal representation of interface 22, since the internal representation is independent of the target machine 25 architecture. Some aspects of the front end 20 may need to be tailored to the target system, however; for example, aspects of the data representation such as allocation and alignment, might be customized to fit the target machine 25 architecture better, and routine call argument mechanisms may depend on the target system calling standard, and further the runtime library interface will probably be different for each target system.

The back end 12 functions to translate the internal representation 22 constructed by the front end 20 into target system object code 23. The back end 12 performs the basic functions of optimization 26, code generation 27, storage and register allocation 28, and object file emission 29. The optimization function is performed on the code when it is in its internal representation. The back end 12 also includes utility routines which are called by the front end 20 to create a symbol table 30 and intermediate language data structures.

When the user (that is, a user of the computer system of FIG. 2, where the computer system is executing the operating system 13) invokes the compiler of FIG. 1 (though a callable interface, or some other mechanism), the shell 11 receives control. The shell 11 invokes the front end 20 to compile an input stream from source file 15 into an object file 23. The front end 20 invokes the back end 12 to produce each object module within the object file 23. The front end 20 may invoke the back end 12 to create code for each individual routine within an object module 23, or it may call a back end driver which will generate code for an entire module at once.

The front end 20 parses the source code 21 and generates an intermediate language version of the program expressed in the source code. The elemental structure of the intermediate language is a tuple. A tuple is an expression which in source language performs one operation. For example, referring to FIG. 3, the expression

I=J+1

as represented in source language is broken down into four tuples for representation in the intermediate language, these being numbered $1, $2, $3 and $4. This way of expressing the code in IL includes a first tuple $1 which is a fetch represented by an item 31, with the object of the fetch being a symbol J. The next tuple is a literal, item 32, also making reference to a symbol "1." The next tuple is an Add, item 33, which makes reference to the results of tuples $1 and $2. The last tuple is a store, item 34, referencing the result of tuple $3 and placing the result in symbol I in the symbol table. The expression may also be expressed as a logic tree as seen in FIG. 3, where the tuples are identified by the same reference numerals. This same line of source code could be expressed in assembly for a RISC type target machine, as three instructions LOAD, ADD integer, and STORE, using some register such as REG 4 in the register file, in the general form seen in FIG. 3. Or, for a CISC machine, the code emitted may be merely a single instruction, ADD #1,J,I as also seen in the Figure.

A tuple, then, is the elemental expression of a computer program, and in the form used in this invention is a data structure 35 which contains at least the elements set forth in FIG. 4, including (1) an operator and type field 36, e.g., Fetch, Store, Add, etc., (2) a locator 37 for defining where in the source module 21 the source equivalent to the tuple is located, (3) operand pointers 38 to other tuples, to literal nodes or symbol nodes, such as the pointers to I and #1 tuples $1 and $2 in FIG. 3. A tuple also has attribute fields 39, which may include, for example, Label, Conditional Branch, Argument (for Calls), or SymRef (a symbol in the symbol table). The tuple has a number field 40, representing the order of this tuple in the block.

The front end 20 parses the source code to identify tuples, then to identify basic blocks of code. A block of code is defined to be a sequence of tuples with no entry or exit between the first and last tuple. Usually a block starts with a label or routine entry and ends with a branch to another label. A task of the front end 20 is to parse the source code 21 and identify the tuples and blocks, which of course requires the front end to be language specific. The tuple thus contains fields 41 that say whether or not this tuple is the beginning of a block, and the end of a block.

As discussed in more detail below, one feature of the invention is a method of representing effects. A tuple has effects if it stores or writes to a memory location (represented at the IL level as a symbol), or is dependent upon what another tuple writes to a location. Thus, in the example given in FIG. 3, tuple $4 has an effect (store to I) and tuple $1 has a dependency (content of J). Thus the tuple data structure as represented in FIG. 4 has fields 42 and 43 to store the effects and dependencies of this tuple.

A single execution of a compiler of FIG. 1 is driven by the shell 11 as illustrated in the flow chart of FIG. 5. As indicated by the item 45 of FIG. 5, the shell 11 receives control when the compiler of FIG. 1 is invoked by the user via the operating system 13. The user in a command line specifies a "plus-list" or list of the modules 21 to be operated upon. The next step is calling by the shell 11 of a front-end routine GEM$XX.sub.-- INIT, which does any necessary initialization for the front end, indicated by the item 46. This front end routine GEM$XX.sub.-- INIT is described in the Appendix. Next, the shell 11 parses the global command qualifiers and calls the front end routine GEM$XX.sub.-- PROCESS.sub.-- GLOBALS, as indicated by the item 47. Then, for each "plus-list" (comma-separated entity) in the command line used at the operating system 13 level to involve the compiler, the shell executes a series of actions; this is implemented by a loop using a decision point 48 to check the plus-list. So long as there is an item left in the plus-list, the actions indicated by the items 49-52 are executed. These actions include accessing the source files 21 specified in the command line and creating an input stream for them, indicated by the item 49, then parsing the local qualifiers (specific to that plus-list), calling GEM$XX.sub.-- PROCESS.sub.-- LOCALS to do any front-end determined processing on them, and opening the output files specified by the qualifiers, indicated by the item 50. The actions in the loop further include calling the front-end routine GEM$XX.sub.-- COMPILE to compile the input stream, indicated by the item 51, then closing the output files, item 52. When the loop falls through, indicating all of the plus-list items have been processed, the next step is calling the front end routine GEM$XX.sub.-- FINI to do any front-end cleanup, indicated by item 53. Then, the execution is terminated, returning control to the invoker, item 54.

The shell 11 calls GEM$XX.sub.-- COMPILE to compile a single input stream. An input stream represents the concatenation of the source files or modules 21 specified in a single "plus list" in the compiler command line, as well as any included files or library text. By default, compiling a single input stream produces a single object file 23, although the compiler does allow the front end 20 to specify multiple object files 23 during the compilation of an input stream.

Before calling GEM$XX.sub.-- COMPILE, the shell 11 creates the input stream, parses the local qualifiers, and opens the output files. After calling GEM$XX.sub.-- COMPILE, it closes all the input and output files.

The front end 20 (GEM$XX.sub.-- COMPILE and the front-end routines that are called from it) reads source records 21 from the input stream, translates them into the intermediate representation of interface 22 (including tuples, blocks, etc. of the intermediate language graph, and the symbol table) and invokes the back end 12 to translate the intermediate representation into object code in the object file 23.

An object file 23 may contain any number of object modules. Pascal creates a single object module for an entire input stream (a MODULE or PROGRAM). FORTRAN (in one embodiment) creates a separate object module for each END statement in the input stream. BLISS creates an object module for each MODULE.

To create an object module 23, the front end 20 translates the input stream or some subsequence thereof (which we can call a source module 21) into its internal representation for interface 22, which consists of a symbol table 30 for the module and an intermediate language graph 55 for each routine. The front end 20 then calls back end routines to initialize the object module 23, to allocate storage for the symbols in the symbol table 30 via storage allocation 28, to initialize that storage, to generate code for the routines via emitter 29, and to complete the object module 23.

The compiler is organized as a collection of packages, each of which defines a collection of routines or data structures related to some aspect of the compilation process. Each package is identified by a two-letter code, which is generally an abbreviation of the package function. The interface to a package is defined by a specification file. If a package is named ZZ, then its specification file will be GEM$ZZ.SDL.

Any symbol which is declared in a package's specification file is said to be exported from that package. In general, symbols exported from package ZZ have names beginning with GEM$ZZ.sub.--. The specific prefixing conventions for global and exported names are set forth in Table 1.

The shell 11 is a collection of routines to support common compiler activities. The shell components are interrelated, so that a program that uses any shell component gets the entire shell. It is possible, however, for a program to use the shell 11 without using the back end 12. This can be a convenient way of writing small utility programs with production-quality features (input file concatenation and inclusion, command line parsing, diagnostic file generation, good listing files, etc.) Note that the shell 11 is actually the "main program" of any program that uses it, and that the body of the application must be called from the shell 11 using the conventions described below. To use a shell package ZZ from a BLISS program, a user does a LIBRARY `GEM$ZZ`. To use the shell from other languages, a user must first translate the shell specification files into the implementation language.

The shell packages are summarized in the following paragraphs; they are documented in their specification files (the GEM$ZZ.SDL files) in the Appendix. Most shell routine arguments (e.g., integer, string, etc.) fall into one of the categories set forth in Table 2.

The interface from the shell 11 to the front end 20 has certain requirements. Since the shell 11 receives control when a compiler of FIG. 1 is invoked, a front end 20 must declare entry points so the shell 11 can invoke it and declare global variables to pass front end specific information to the shell 11. The front end 20 provides the global routines set forth in Table 3, in one embodiment. These routines have no parameters and return no results.

The Virtual Memory Package (GEM$VM): The virtual memory package provides a standard interface for allocating virtual memory. It supports the zoned memory concept of the VMS LIB$VN facility; in fact, under VMS, GEM$VM is an almost transparent layer over LIB$VM. However, the GEM$VM interface is guaranteed to be supported unchanged on any host system.

The Locator Package (GEM$LO): A locator describes a range of source text 21 (starting and ending file, line, and column number). The text input package returns locators for the source lines that it reads. Locators are also used in the symbol table 30 and intermediate language nodes 43 to facilitate message and debugger table generation, and are used for specifying where in the listing file the listing package should perform actions. A locator is represented as a longword. The locator package maintains a locator database, and provides routines to create and interpret locators. There is also a provision for user-created locators, which allow a front end to create its own locators to describe program elements which come from a non-standard source (for example, BLISS macros or Ada generic instantiation).

The Text Input Package (GEM$TI): The text input package supports concatenated source files 21, nested (included) source files 21, and default and related files specs, while insulating the front end 20 from the I/O architecture of the underlying operating system 13. Text of a source file 21 is read a line at a time. The text input package GEM$TI colludes with the locator package GEM$LO to create a locator describing each source line it reads.

The Text Output Package (GEM$TX): The text output package supports output to any number of output files 44 simultaneously. Like the text input package, it insulates its caller from the operating system 13. It will write strings passed by reference or descriptor. It provides automatic line wrapping and indentation, page wrapping, and callbacks to a user-provided start-of-page routine.

The Listing Package (GEM$LS): The listing package will write a standard format listing file containing a copy of the source files 21 (as read by the text input package GEM$TI), with annotations provided by the front end 11 at locations specified with locators. The listing file is created as a GEM$TX output file 44, which the front end 20 may also write to directly, using the GEM$TX output routines.

The Internal Representation

The internal representation of a module 21 comprises a symbol table 30 for the module and a compact intermediate language graph 55 or CILG, for each routine in source module 21. These are both pointer-linked data structures made up of nodes.

Nodes, according to the framework of FIG. 1, will be defined. Almost all data structures used in the interface between the front and back ends 20 and 12 (and most of the data structures used privately by the back end 12) are nodes. A node as the term is used herein is a self-identifying block of storage, generally allocated from the heap with GEM$VM.sub.-- GET. All nodes have the aggregate type GEMSNODE, with fields GEM$NOD.sub.-- KIND and GEM$NOD.sub.-- SUBKIND. Kind is a value from the enumerated type GEM$NODE.sub.-- KINDS which identifies the general kind of the node. Subkind is a value from the enumerated type GEM$NODE.sub.-- SUBKINDS which identifies the particular kind of the node within the general class of nodes specified by kind. Any particular node also has an aggregate type determined by its kind field. For example, if kind is GEM$NODE K.sub.-- SYMBOL, then the node has type GEM$SYMBOL.sub.-- NODE. Note that the types associated with nodes do not obey the naming conventions described above. The interface node types and their associated enumerated type constants are defined in the files set forth in Table 4.

The compiler framework of FIG. 1 supports a simple tree-structured symbol table 30, in which symbol nodes are linked together in chains off of block nodes, which are arranged in a tree. All symbolic information to be used by the compiler must be included in this symbol table 30. There are also literal nodes, representing literal values of the compiled program; frame nodes, representing storage areas (PSECTs and stack frames) where variables may be allocated; and parameter nodes, representing elements in the parameter lists of routine entry points. The symbol table structure and the contents of symbol table nodes are described below.

The intermediate language is the language used for all internal representations of the source code 21. The front end 20 describes the code of a routine to be compiled as a compact intermediate language graph 55, or CILG. This is simply a linked list of CIL tuple nodes 35 of FIG. 4 (also referred to as tuple nodes, or simply as tuples), each of which represents an operation and has pointers 38 to the tuple nodes representing its operands. Tuple nodes may also contain pointers 38 to symbol table nodes. The intermediate language is described in more detail below.

The front end 20 must create the internal representation 22 of the module 21 one node at a time, and link the nodes together into the symbol table 30 and IL data structures 55. The routines and macros of Table 5, also documented in the Appendix, are used to create and manipulate the data structures of the internal representation 22.

The back end 12 makes no assumptions about how the front end 20 represents block and symbol names. Instead, the front end 20 is required to provide a standard call-back interface that the back end 12 can use to obtain these names.

Every symbol node has a flag, GEM$SYM.sub.-- HAS.sub.-- NAME, and every block node has a flag, GEM$BLK.sub.-- HAS.sub.-- NAME. When the front end 20 initializes a symbol or block node, it must set its has name flag to indicate whether a name string is available for it. (Some symbols and blocks, such as global and external symbols and top level module blocks, must have names.) There is a global variable, GEM$ST.sub.-- G.sub.-- GET.sub.-- NAME, in the ST package. Before invoking the back end, the front end must set this variable to the address of a callback routine which fits the description set forth in Table 5.

To compile a source module using the GEM$CO.sub.-- COMPILE.sub.-- MODULE interface, a front end (that is, the routing GEM$XX.sub.-- COMPILE) does (in order) each of the activities described in the following paragraphs.

1. Create the Internal Representation

The first task of the front end 20 is to create the internal representation 22 of the source module. To begin with, it must call GEM$ST.sub.-- INIT to initialize the symbol table 30 and associated virtual memory zones. It must then read the source module 21 from the input stream, using the GEM$Tr package; do lexical, syntactic, and semantic analysis of the source module 21; and generate the symbol table 30 and the intermediate language graphs 55 for the module as described above, using the GEM$ST and GEM$IL routines which are documented in the Appendix.

In addition, the module's source listing may be annotated with calls to the GEM$LS shell package, and error's in the module may be reported with calls to the GEM$MS package.

If the source module 21 contains errors severe enough to prevent code generation, then the front end 20 should now call GEM$LS.sub.-- WRYTE.sub.-- SOURCE to write the listing file and GEM$ST.sub.-- FINI to release all the space allocated for the internal representation 22. Otherwise, it must proceed with the following steps.

2. Specify the Callback Routines

Before calling the back end 12 to compile the module 21, the front end 20 must initialize the following global variables with the addresses of routines that will be called by the back end 12.

(1) GEM$ST.sub.-- G.sub.-- GET.sub.-- NAME must be initialized to the address of a routine that will yield the names of symbol and block nodes in the symbol table 30, as described above.

(2) The GEM$SE.sub.-- G global variables must be initialized to the addresses of routines that will do source-language defined side effect analysis, as described below. The compiler provides a predefined collection of side effect routines, suitable for use during the early development of a front end 20, which can be selected by calling GEM$SE.sub.-- DEFAULT.sub.-- IMPLEMENTATION.

(3) GEM$ER.sub.-- G.sub.-- REPORT.sub.-- ROUTINE contains the address of the front end's routine for reporting back end detected errors, as described below.

3. Do the Compilation

When the internal representation is complete, the front end 20 can call GEM$CO.sub.-- COMPILE.sub.-- MODULE (described below) to translate it into target machine object representation 23. The front end should then call GEM$LS.sub.-- WRITE.sub.-- SOURCE to list the input stream in the listing file. It may also call GEM$ML.sub.-- LIST.sub.-- MACHINE.sub.-- CODE to produce an assembly code listing of the compiled module 23.

Note that normally, GEM$LS.sub.-- WRITE.sub.-- SOURCE has to be called after GEM$CO.sub.-- COMPILE.sub.-- MODULE so that the source listing 21 can be annotated with any error messages generated during back end processing. However, it is a good idea for the front end 20 to provide a debugging switch which will cause GEM$LS.sub.-- WRITE.sub.-- SOURCE to be called first. This will make it possible to get a source listing even if a bug causes the compiler to abort during back end processing.

4. Clean Up

When compilation is complete, the front end 20 must call GEM$CO.sub.-- COMPLETE.sub.-- MODULE to release the space used for back end processing, and then GEM$ST.sub.-- FINI to release the space used for the internal representation.

The back end 12 is able to detect conditions during compilation which are likely to represent conditions in the source program 21 which ought to be reported to the user, such as uninitialized variables, unreachable code, or conflicts of static storage initialization. However, a particular front end 20 may need to customize which of these conditions will be reported, or the precise messages that will be issued.

To allow this, the back end 12 reports all anomalous conditions that it detects by calling the routine whose address is in the global variable GEM$34.sub.-- G.sub.-- REPORT.sub.-- ROUTINE, with the argument list described below. This routine is responsible for actually issuing the error message.

There is a default error reporting routine set forth in the Appendix named GEM$ER.sub.-- REPORT.sub.-- ROUTINE, whose address will be in GEMSER.sub.-- G REPORT.sub.-- ROUTINE unless the front end has stored the address of its own report routine there. This default routine has three uses:

(1) The default routine provides reasonable messages, so the front end developers are not obliged to provide their own routine unless and until they need to customize it.

(2) When the front end developers do choose to write a report routine, they can use the default routine as a model.

(3) The front end's routine can be written as a filter, which processes (or ignores) certain errors itself, and calls the default routine with all others.

INTERFACE FOR REPRESENTING EFFECTS

As an essential step in detecting common subexpressions (CSEs), invariant expressions, and opportunities for code motion, the optimizer 26 in the back end 12 must be able to determine when two expression tuples are guaranteed to compute the same value. The basic criterion is that an expression B computes the same value as an expression A if:

1. A and B are literal references to literals with the same value, CSE references to the same CSE, or symbol references to the same symbol; or

2.

a. A. is evaluated on every control flow path from the start of the routine to B, and

b. A and B have the same operator and data type, and

c. the operands of B compute the same values as the corresponding operands of A (obviously a recursive definition), and

d. no tuple which occurs on any path from an evaluation of A to an evaluation of B can affect the value computed by B.

The optimizer 26 of FIG. 1 can validate criteria 1, 2a, 2b, and 2c by itself; but criterion 2d depends on the semantics of the language being compiled, i.e., the language of source code module 21. But since the compiler 12 in the back end must be language-independent, a generic interface is provided to the front end 20 to convey the necessary information. When can the execution of one tuple affect the value computed by another tuple? The interface 22 must allow the optimizer 26 to ask this question, and the compiler front end 20 to answer it.

The model underlying this interface 22 is that some tuples have effects, and that other tuples have dependencies. A tuple has an effect if it might change the contents of one or more memory locations. A tuple has a dependency on a memory location if the value computed by the tuple depends on the contents of the memory location. Thus, the execution of one tuple can affect the value computed by another tuple if it has the effect of modifying a memory location which the other tuple depends on.

Given the ramifications of address arithmetic and indirect addressing, it is impossible in general to determine the particular memory location accessed by a tuple. Thus we must deal with heuristic approximations to the sets of memory locations which might possibly be accessed.

The actual interface 22 provides two mechanisms for the front end 20 to communicate dependency information to the optimizer 26. These are the straight-line dependency interface and the effects-class interface.

In the straight-line dependency interface, to determine dependencies in straight-line code, the optimizer 26 will ask the front end 20 to (1) push tuples on an effects stack and pop them off again, and (2) find the top-most tuple on the effects stack whose execution might possibly affect the value computed by a specified tuple.

The straight-line mechanism is not appropriate when the optimizer 26 needs to compute what effects might occur as a result of program flow through arbitrary sets of flow paths. For this situation, the front end 20 is allowed to define a specified number (initially 128) of effects classes, each representing some (possibly indeterminate) set of memory locations. A set of effects classes is represented by a bit vector. For example, an effects class might represent the memory location named by a particular variable, the set of all memory locations which can be modified by procedure calls, or the set of memory locations which can be accessed by indirect references (pointer dereferences).

For the effects-class interface, the optimizer will ask the front end to (1) compute the set of effects classes containing memory locations which might be changed by a particular tuple, and (2) compute the set of effects classes containing memory locations which a particular tuple might depend on.

Using this effects-class interface, the optimizer can compute, for each basic block, a bit-vector (referred to as the LDEF set) which represents the set of effects classes containing memory locations which can be modified by some tuple in that basic block.

The optimizer will also ask the front end to (3) compute the set of effects classes which might include the memory location associated with a particular variable symbol.

This information is used by the split lifetime optimization phase (see below) to compute the lifetime of a split candidate.

The optimizer 26 uses these interfaces as follows. Remember that the reason for these interfaces is to allow the optimizer 26 in back end 12 to determine when "no tuple which occurs on any path from an evaluation of A to an evaluation of B can affect the value computed by B." If A and B occur in the same basic block, this just means "no tuple between A and B can change the value computed by B." This can be easily determined using the straight-line dependency interface.

If the basic block containing A dominates the basic block containing B (i.e., every flow path from the routine entry node to the basic block containing B passes through the basic block containing A), then the optimizer finds the series of basic blocks X1, X2, . . . Xn, where X1 is the basic block containing A, Xn is the basic block containing B, and each Xi immediately dominates X(i+1). Then the test has two parts:

1. There must be no tuple between A and the end of basic block X1, or between the beginning of basic block Xn and B, or in any of the basic blocks X2, X3, . . . X(n-1), which can change the value computed by B. This can be easily determined using the straight-line dependency interface.

2. There must be no flow path between two of the basic blocks Xi and X(i+1) which contains a tuple which can change the value computed by B. The optimizer tests this with the effects-class mechanism, by computing the union of the LDEF sets of all the basic blacks which occur on any flow path from Xi to X(i+1), computing the intersection of this set with the set of effects classes containing memory locations that B might depend on, and testing whether this intersection is empty.

The structure of the interface will now be described. The interface routines are called by the back end 12. The front end 20 must make its implementation of the interface available before it invokes the back end 12. It does this by placing the addresses of its interface routine entry points in standard global variables. The optimizer 26 can then load the routine address from the appropriate global variable when it invokes one of these routines. The interface routines are documented below with names of the form GEM.sub.-- SE.sub.-- xxx. The front end must store the entry address of each corresponding implementation routine in the global variable named GEM.sub.-- SE.sub.-- G.sub.-- xxx.

Tuples that have effects and dependencies are of interest. to this interface. Only a few of the IL tuples can have effects and dependencies. (Roughly speaking, tuples that do a store can have effects; tuples that do a fetch can have a dependency; tuples that do a routine call can have both.)

More specifically, each tuple falls into one of the following categories:

1. The tuple does not have any effects, nor is it dependent on any effects. (Example: ADD). Tuples that fall into this class are NOT pushed on the effects stack. Nor are such tuples ever passed to GEM.sub.-- SE.sub.-- EFFECTS.

2. The tuple may have effects, but has no dependencies. (Example: STORE).

3. The tuple may have dependencies, but does not cause any affects. (Example: FETCH).

4. The tuple both may have effects (out-effects) and a separate set of dependencies (in-effects). (Example: procedure calls)

5. The tuple may have both effects and dependencies. The effects it depends on are identical to the effects it produces. (Example: PREINCR).

A particular tuple called the DEFINES tuple is provided to allow a front end 20 to specify effects which are not associated with any tuple. One possible use of the DEFINES tuple would be to implement the BLISS CODECOMMENT feature, which acts as a fence across which optimizations are disallowed. The translation of CODECOMMENT would be a DEFINES tuple that has all effects, and therefore invalidate all tuples.

Argument passing tuples (such as ARGVAL and ARGADR) have effects and dependencies. However, the effects and dependencies of a parameter tuple are actually considered to be associated with the routine call that the parameter tuple belongs to. For example, in the BLISS routine call F(X,.X+Y), the parameter X would have the effect of changing X. However, this would not invalidate a previously computed value of .X+.Y, since the effect does not actually occur until F is called.

The data structure of FIG. 4 representing a tuple is accessed by both front end 20 and back end 12, and some fields of this structure are limited to only front end or only back end access. Every tuple 35 which can have effects or dependencies will contain one or more longword fields 42 or 43, typically named GEM.sub.-- TPL.sub.-- xxx.sub.-- EFFECTS or GEM.sub.-- TPL.sub.-- xxx.sub.-- DEPENDENCIES. The field names used for particular tuples are described in the section on The Intermediate Language. No code in the back end will ever examine or modify these fields--they are reserved for use by the front end. They are intended as a convenient place to record information which can be used to simplify the coding of the interface routines.

There is a similar longword field named GEM.sub.-- SYM.sub.-- EFFECTS in each symbol node of symbol table 30, which is also reserved for use by the front end 20.

For the straight-line dependency interface, a description of the routines will now be given. The front end provides an implementation of the following routines:

GEM.sub.-- SE.sub.-- PUSH.sub.-- EFFECT(EIL.sub.-- TUPLE: in GEM.sub.-- TUPLE.sub.-- NODE)--Pushes the EIL tuple whose address is in the EIL.sub.-- TUPLE parameter onto the effects stack.

GEM.sub.-- SE.sub.-- PUSH.sub.-- EFFECT(EIL.sub.-- TUPLE: in GEM.sub.-- TUPLE.sub.-- NODE)--Pops the topmost EIL tuple from the effects stack. This is guaranteed to be the tuple whose address is in the EIL.sub.-- TUPLE parameter. Of course, this means that the parameter is redundant. However, it may simplify the coding of the POP procedure for a front end that doesn't use a single-stack implementation for the effects stack (see the implementation discussion below).

    ______________________________________
    GEM.sub.-- TUPLE.sub.-- NODE =
    GEM.sub.-- SE.sub.-- FIND.sub.-- EFFECT(
            EIL.sub.-- TUPLE  : in GEM.sub.-- TUPLE.sub.-- NODE,
            MIN.sub.-- EXPR.sub.-- COUNT : value)
    ______________________________________

    ______________________________________
    GEM.sub.-- TUPLE.sub.-- NODE =
    GEM.sub.-- SE.sub.-- FIND.sub.-- EFFECTS (
            VAR.sub.-- SYM  : in GEM.sub.-- SYMBOL.sub.-- NODE,
            MIN.sub.-- EXPR.sub.-- COUNT : value)
    ______________________________________

    ______________________________________
    X›N! = true;   | Add effects class N to set X.
    X›N! = false;  | Remove effects class N from set X.
    if .X›N! then . . .
                  | If effects class N is in set X . . .
    ______________________________________

    ______________________________________
    GEM.sub.-- SE.sub.-- EFFECTS(
    EIL.sub.-- TUPLE
                  : in    GEM.sub.-- TUPLE.sub.-- NODE,
    EFFECTS.sub.-- BV
                  : inout GEM.sub.-- SE.sub.-- EFFECTS.sub.-- SET)
    ______________________________________

    ______________________________________
    GEM.sub.-- SE.sub.-- DEPENDENCIES(
    EIL.sub.-- TUPLE
                  : in    GEM.sub.-- TUPLE.sub.-- NODE,
    EFFECTS.sub.-- BV
                  : inout GEM.sub.-- SE.sub.-- EFFECTS.sub.-- SET)
    ______________________________________

    ______________________________________
    GEM.sub.-- SE.sub.-- VARIABLE.sub.-- DEPENDENCIES(
    SYMBOL        : in    GEM.sub.-- SYMBOL.sub.-- NODE,
    EFFECTS.sub.-- BV
                  : out   GEM.sub.-- SE.sub.-- EFFECTS.sub.-- SET)
    ______________________________________

    ______________________________________
           Label L V = 1
                   IF V > 10
                   GOTO LABEL M
                 ELSE
                   PRINT X
                 V = V + 1
                 END IF
    ______________________________________

    ______________________________________
                DO I = 1, 100
                X = I * 8
                T = I - 4
                A›I! = T * 4
                END DO
    ______________________________________

    ______________________________________
                  I = 1;
            L:    X = X + (4 * I)
                  I = I + 1
                  if I < = 100 GOTO L
    ______________________________________

    ______________________________________
                  I = 1;
                  I2 = 4;
            L:    X = X + I2
                  I = I + 1
                  I2 = I2 + 4
                  if I < = 100 GOTO L
    ______________________________________

    ______________________________________
                  I2 = 4;
            L:    X = X + I2
                  I2 = I2 + 4
                  if I2 < = 400 GOTO L
    ______________________________________

    ______________________________________
           -f(I)
           f(I) + g(I)   f(I) - g(I)
           f(I) + E      E + f(I)
           f(I) - E      E - f(I)
           f(I) * E      E * f(I)
    ______________________________________

    ______________________________________
                D = 50
                DO I = 1, n
                  A›I! = D + . . .
                  D = I + 4
    ______________________________________

    ______________________________________
    select TUPLE›OPCODE}
    ›FETCH!
    If base symbol is still a basis IV candidate
    then
    mark this tuple as being inductive.
    ›STORE!
    Let V be the base symbol of the store.
    If the value being stored is not inductive or.sub.-- else
    the basic IV of the inductive value being stored is not V or.sub.-- else
    the coefficient of the stored value is not 1
    remove V from the basic IV set of the loop top
    then
    remove V from the basic IV set of the loop top
    then
    mark the store as being inductive
    ›ADD, SUB, MUL, etc.!
    If one operand is inductive and other operand is loop invariant
    then
    mark this tuple as being inductive
    ______________________________________

    ______________________________________
                int toy.sub.-- procl)
                {
                float b,c;
                :
                }
    ______________________________________

    ______________________________________
    I          INT          A       ADDR
    U          UINT         S       STR
    R          REAL         B       BITS
    C          CMPLX
    ______________________________________