This chapter is based on the results of an investigation(1)which aimed at finding out how parts of the GNU Compiler Collection 'GCC' can be used in other compiler projects(2).
It will hopefully help you to write a GNU compiler for a so far unsupported language.
We describe the structure and basic concepts of 'GCC' from the perspective of someone writing a compiler front end. We deal with two different problems.
Examples are available, demonstrating how to work with these backend functions. See section 14.9 Tree Examples.
The chapter was originally based on GCC 2.7.2 and has not been fully updated to reflect subsequent changes. For a summary of some of the changes, and other sources of information, see section 14.8 Tree Changes and section `GCC Internals' in Using and Porting Gnu CC.
The Free Software Foundation has developed a suite of freely usable programs which are constituents of Unix-like operating system. Included in this suite is a compiler for the language `C'.
An important goal for the compiler was a high level of reusability of the larger part of the source code of this compiler. Because Unix runs on a large number of different architectures and platforms, it was a goal to build the compiler in such a way that it was as machine independent as possible.
A second goal was very high code quality, which is possible only through intensive optimisation. Both goals could only be reached at the same time if the optimisation were as much as possible independent of the concrete machine architecture. The problem was solved by developing a more or less processor independent machine language. This language is called "RTL - Register Transfer Language". See section `RTL' in Using and Porting Gnu CC.
The architecture for the RTL machine is an abstraction of actual processor achitectures. It therefore reflects the technical reality of familiar concepts like storage, processor registers, address types, an abstract jump command etc.
A code generator for a concrete processor is built through a language which allows you to describe the conversion of patterns of RTL into a concrete assembler language.
See section `Machine Desc' in Using and Porting Gnu CC, section `Target Macros' in Using and Porting Gnu CC, section `Config' in Using and Porting Gnu CC and section `Fragments' in Using and Porting Gnu CC for a comprehensive description of how with the help of this description language, you can create new code generators or improve existing ones. There and in section `RTL' in Using and Porting Gnu CC the language RTL is abundantly described.
These instructions for implementing an optimised platform independent representation with the aim of providing a conversion process into real machine specific assembler code also has the objective of making it possible to create a cross compiler without additional effort.
Reusability should also be achievable in another sense: It should with minimum possible effort be feasible to write a compiler for another language other than C, based on the pre-existing code.
Therefore again it is necessary for as many as possible of the existing high level language constructs to be easily converted into RTL.
Therefore an intermediate language was created, which allows existing constructs from high level languages to be respresented in a unified form, including:
The syntax tree stored in tree nodes which are created via
function calls described later, is then converted into RTL code by the
use of functions as described in section 14.5 Generating RTL from the syntax tree. For control structures,
variable scope and functions there are additionally functions in the
back end which allow direct creation of RTL from each such fragment.
Unfortunately, comprehensive documentation, explaining how one creates
such tree expressions and how one can use the very capable GCC
code generator for a new compiler, has not previously existed.
This chapter attempts to at least partly fill this gap.
It is true that the source code of GCC(4) is commented, but after painful experience the authors can report that the this information does not suffice to explain as you might hope how to write a new front end in the same manner as the existing front ends. Because the documentation is all local, you need to understand all of it before you can understand any of it.
The next section section 14.3 Overview of the GCC Compiler back end describes in detail the construction of the GNU C Compiler and the basic concepts insofar as they apply to our problem.
The following section 14.4 Creating Your Own GNU Compiler explains exactly what you need to do, to create a new member of the GNU Compiler Collection, in accordance with the concepts of the compiler's authors: how to call the parser and semantic analayis out of the existing code, how to obtain existing command line options or to add new ones; also how to enhance and adapt `make'-data. Additionally there is another possibility presented, the one used by the author of this chapter, to include the GNU backend into your own project.
The section section 14.5 Generating RTL from the syntax tree decribes in detail, how the code generator is controlled by the language specific part of the compiler. The most important of the numerous functions, data structures and access operations are presented and their interoperation is explained.
All that remains is the studying of the commented source code of GCC. A
sample program is provided in section 14.9 Tree Examples which hopefully may
greatly ease the use of the GNU C Codegenerator. The examples contain
important and comprehensive researched information in packaged form and
may limit the need to study the tree structures and associated code.
This example can also be used as an illustrated example for the section 14.4 Creating Your Own GNU Compiler.
The section section 14.6 Tree Summary and Overview brings all the work together and gives an overview.
This chapter describes the construction of the family of GNU Compilers, known above all through its best known member, the C Compiler GCC. This establishes the foundation for understanding information presented in the subsequent section 14.4 Creating Your Own GNU Compiler and particularly the section 14.5 Generating RTL from the syntax tree.
The concept of the GNU family compilers is, as already stated, to support as many high level languages and machine architectures with as little source code as possible, through intensive reuse and at the same time to achieve the highest quality generated assembler code.
The base package(5)contains the translation core, and front ends for the languages C, C++, Chill, Fortran and Objective C. Front ends also exist for Ada 95(6), and for Pascal(7).
To the knowledge of the author compilers for Modula-3 and COBOL are in progress and will in time be available.
The code generator can create code for about 30 various processor families, including prominent ones like DEC Alpha, Intel 80386 up to Pentium, Sun Sparc, HPPA, IBM RS/6000, but also such veterans as Motorola 68k, DEC VAX, IBM S/370.
One recognises here representatives of the RISC as well as the CICS architectures which in combination with the sheer number of processors clearly shows that the concept of processor independence - or better: simple portability to new processor families - has been achieved.
The base package includes over 500,000 lines of commented source code. The code generator comprises by far the greater part of this, over 450,000 lines which comprises two roughly equal parts: the processor descriptions for the previously-described 30 architectures(8)and the essential translator core each with around 225,000 lines. The remaining 100,000 lines is the code of the front ends for C, C++ and Objective C, of which more than two thirds stem from C++.
This work describes how the 225,000 lines of source code of the translator core can be used for your own project.
The implementation language C provides little modularisation support so there is no other option than to simulate the desired modularisation through division of the function into C Source files. In this manner the language specific parts were separated from the language independent parts. Files which contain special code for C, have for example the prefix `c-'. Files for Objective C begin with `objc-'. Files for C++ are contained in the subdirectory `cp'.
It is unfortunately not the case however that the front end and back end are completely separated. The back end routines need access to callback routines in the front end. Therefore there are several global variables which the front end must intialize and which remain unchanged during the translation and whose values represent the declaration of the current translation routine. These routines and variables have partly only cosmetic tasks and may remain unimplemented, partly they can use standard implementations but must in some cases be changed for specific languages.
Which routines and variables these are and how they are used, is described in detail in section 14.3.5 Callback.
In a large project which GCC is - as shown above - success unavoidably requires a certain discipline in programming. The programming language `C' is here also not very helpful. It does not fully support abstract concepts like data types and encourages the data interchange between modules using global variables. Object oriented programming, which offers much for the implementation of the transalator, is only possible with great difficulty.
The programmers of GCC have however partially implemented the concept of
abstract data types, in which important important divisions between
logical modules take procedural form. The creation of the tree
nodes happens exclusively through function calls, as does the creation
of the RTL code. Even the transition between various states(9)happens through
function calls. For the modification of fields in the tree nodes
certainly macros are used, though it is also possible, though not
recommended, to manipulate these fields directly.
Unfortunately there is intensive data exchange through global variables, an approach which makes the reading and understanding of the source code more difficult and which is not very consistent with the philosophy of abstract data types.
Fully aware that it can be impossible through the procedural pattern to make available counterparts to all the significant constructs of all programming languages for which someone may at some time want to write a compiler, the possibility of extensions by the user in the future was forseen.
It is thus in principle possible, to define your own classes of
tree nodes, certainly though one must then also implement the
translation of the nodes into RTL-format. We not further discuss this possibility.
The user does not directly call the core compiler himself. Rather, the user calls a control program (driver) named "gcc" which should be installed in the path. This program "gcc" with source code in `gcc.c'
and places therefore at the disposal of the programmer a unified entry point to all compilers of the GNU family. However it should be noted that some of the compilers have their own version of the driver `gcc.c'.
The core compiler is usually placed in a sub-directory `gcc-lib'\Architecture\Version, where the directory `gcc-lib' lies in `Unix' under `/usr/local/lib', and the compiler which is usually called `cc1' lies for example in `/usr/local/lib/gcc-lib/sun-sparc-subos4.1.3/2.7.2/cc1'
In principle one is not prevented from controlling other programs is this way using `gcc', but in the end it "specs" is a weakly expressive language with limited syntax at its disposal with only the ability to write loop free simple script type programs. It is similar in its goals to the `make' program, but without its power.
As described above, the user does not call the compiler directly, but the driver `gcc' which in its turn calls the actual compiler, being `cc1' for `C'. Our task is to develop a 'brother' to `cc1' which can compile the desired language.
Compilers of the GNU family, particularly the C compiler `cc1' compile only one source file each time they are run.
After various soon to be described initializations the source file is opened and the parser is called by the standard main routine in `toplev.c'.
There are in fact two significant possibilities, for writing your own compiler within the GNU realm.
tree format, processes the semantic
analysis on this tree and passes the created partial trees from time to
time through calls described to routines described in section 14.5 Generating RTL from the syntax tree for
conversion to RTL.
This approach has the advantage that you need not define your own format
for the syntax tree, and this also minimises the need for definition of
data structures, because you can use the pre-existing tree
format. This also enables fast "one pass" compilation.
The disadvantage is however the sometimes onerous operations on the
somewhat unfamiliar tree format, which is only documented in the
source code and in this document. Language dependent data structures
could ease the implementation of semantic analysis. Additionally it can
be very difficult to place the GNU back end into a consistent state
again after the discovery of a syntactic or semantic error.
tree format, and such tree part branches are from time to
time as above translated into RTL format through corresponding routine
calls.
The advantage is that you can relatively easily integrate front ends
for programming languages with the back end, because the program
can translate the language into the tree format when it chooses.
In cases where components like 'pretty printer' or abstract interpreters
are to be integrated into a translator, which requires a complete syntax
tree to work on, this is the only sensible possibility, because the GNU
tree representation never creates a full representation of the
syntax tree of the translated program, neither in the tree or in
the intentionally incomplete RTL format. In this case the GNU back end
is never placed in a failure mode and it is never necessary to recover
it from an inconsistent state, because it never gets into such a state.
The disadvantage is that you must define many additional data
structures; in addition the conversion of the syntax tree into the
tree format makes the program neither smaller nor faster.
In this chapter, we concentrate on the second alternative - using your own syntax tree.
The following sections describe how the known high level language
constructs - in each case after a conversion into tree format -
can be translated into RTL.
* in C, `^' in Pascal)
as they are built into most programming languages, and are recorded
recursively in the tree format. There is available for the
constructs named above a special routine or a special parameter for a
common routine, to create a tree object of the desired
type.
In the enumeration above, control structures were comprehended as
expressions. This viewpoint however does not correspond to the tradition
of imperative languages from the Algol family, such as `C' where one makes a clear
distinction between expressions and control structures. In this case control structures like
if, while, do, goto, or switch
(examples from C) are translated into tree format.
In many cases for each of the constructs above there are lots of
routines to call, in order to convert each fragment of the desired
construct into the necessary tree codes and then RTL codes. Thereby the
intermediate tree codes or parts of them required in each
case(11) are created and
converted into RTL code.
By way of example for clarification of the basic ideas, here is the calling scheme for the conditional branch. The details, including those for other constructs, follow later in section 14.5 Generating RTL from the syntax tree.
IF cond1 THEN stmt1 ELSEIF cond2 THEN stmt2 ELSE stmt3 END
Code for creation of the branch condition cond1:
expand_start_condition(cond1);
Code for the instructions resulting stmt1
Code for the second condition cond2:
expand_start_elseif(cond2);
Code for the instructions resulting stmt2
expand_start_else();
Code for the instructions resulting stmt3
expand_end_cond();
For marking the beginning and end of routines, variable scope, routine bodies, there are special routines for each case.
At the end of each of the routines to be translated, the function
end_of_compilation from the module `toplev.c' must be
called, in order for these routines to produce fully processed RTL code,
processed through the numerous optimisation phases, and in order to
finally generate assembler source from the now optimized RTL code.
For global variables and local static (in the C sense, meaning variables
that do not reside on the stack) variables, structures or arrays you
must instead call rest_of_decl_compilation from the same
`toplev.c' before you call rest_of_compilation.
For composite and enumeration types you must call
rest_of_type_compilation in order to provide information for the
debugger.
This section provides an overview of what you will find each source file and the role each plays for our problem. Most source files with the suffic `.c' are described.
The top module (where you will find `main') of the main compiler is in the file `toplev.c'. Here
The files `sdbout.c, xcoffout.c, dbxout.c' and `dwarfout.c' contain in each case a module which, if requested through the `-g' option, enhances the assembler output with information in the corresponding debugging format. This additional information allows one to investigate problems and bugs at source level using a program like `gdb'. This module will not concern us further, because its routines are automatically called from `toplev.c'.
The files `tree.c, tree.h' and `tree.def' contain the module which is of decisive importance for our task. Here you will find
We will make extensive use of all these components. You will probably want to print out these modules.
This section describes the old style storage managament, which is now not used in the main compilers.
The code generator manages basically three storage areas, out of which
storage is allocated from the system for objects to be created. These
are called `permanent', `temporary' and `momentary'. In
these storage areas are placed objects such as tree nodes and RTL
objects.
tree nodes for expressions, assignments
and calls, which are at once translated into RTL codes. RTL codes must
remain until the end of the routine, at which point it is optimized
through rest_of_compilation. At the end of the statement the
`momentary' storage should be freed.
Given that statements and routines can be nested, it is necessary to form the `temporary' and `momentary' storage areas as stacks.
This section describes the new style storage managament, which is now used in the main compilers.
In this world, the concepts of permament temporary and momentary storage no longer exist. Instead storage is recovered by one os several garbage collection mechanisms.
The files `ggc*.[ch]' contain the storage management routines. There is unfortunately no external documentation and the docuemntation in some of the modules is somewhat scanty. You should start with `ggc.h' and `ggc-common.c' which largely define the interface. If you need to look at the actual garbage collection modules then `ggc-page.c' while more complex than `ggc-simple.c' is better commented and easier to follow.
The basic concept is as follows:
tree nodes and
turn them into `rtl'. Do not use the calls to switch between
permanent, temporary and momentary allocation modes.
tree and rtl node have prebuilt callback
routines which you can use, however you still need to define these nodes
within root structures and call the appropriate routines tell GC about
the root structures. For example you would probably define tree
for the current function as a root, via `ggc_add_tree_root'.
The callback routine is called when the GC and `toplev.c' decide it
is time to free some storage. This could occur any time storage is
allocated or during `rest_of_compilation' and perhaps at other
times also. So you need to ensure that all used storage is covered by a
root and callback routine at all times. One thing to be careful of when
writing the callback routines is to ensure that they do not recurse too
deeply. The use of `varray' - virtual array - data structures may
be of assistance in this regard as they can be used to conveniently
store up all the 'pending' nodes.
Further documentation and a sample is needed of GC which I intend to provide shortly.
In the file `tree.h', various structures which collectively make up
the tree format are defined. In accordance with the philosophy of
abstract data types we will not concern ourselves with the formats of
these structures, following the convention that you read and write the
fields of these structures only via the access macros (to be described
shortly).
In the following, it is sufficient only to consider the quasi-abstract
data type tree defined using typedef.
In `tree.c', a series of functions whose names begin with
`build' are defined, which each return a new tree node. They
reserve, corresponding to the mode the system is in, storage from the
`permanent', `temporary' or `momentary' areas or using
new style memory allocation and initialize the fields of the nodes
according to the arguments of the call, or set them to 0.
In `tree.h' a whole series of macros is defined, by means of which,
according to convention, access to the fields of the tree nodes
is achieved. It is unfortunately the case that one field or even one
access macro can have multiple meanings for different constructs and in
different phases of the compiler, and in nodes of some types fields may
be unused. That makes understanding not at all easier.
While there are routines for the creation of tree nodes which
represent types, and for practically each different type a different
routine exists, for the declaration of arithmetical, logical and other
expressions it is different:
There is a creation routine for a whole familty of tree nodes,
the type of which which may be determined through the `TREE_CODE'
field. Thus `TREE_CODE' can have the value `MULT_EXPR', which
means that this node represents the multiplication of two child nodes.
The possible values are defined in `tree.def'. It explains what meaning and what purpose the various constructs have.
The source text and the explanation of the functions, which as indicated above, create RTL code for control structures, are found in `stmt.c'.
In order to include correct line number information in the RTL code, it is necessary in many cases, to output RTL code for an empty statement: a function for this purpose is also found here (maybe its `emit_line_note' in `emit_rtl.c' actually).
In order to convert statements that are expressions, such as assignments and calls, into RTL, a special function is needed.
Also here you will find functions to mark the beginning and end of the scope of a variable. These are not defined in the module `function.c' described below because `C' and several other languages have a block structure which makes it possible to declare local variables in the middle of the body of a routine not just at the start.
The source text and the explanation of the functions which create RTL code for (possibly nested) functions, is in `function.c'. Here are the functions to convert function declarations to RTL and also at the appropriate times to mark the beginning and end of the function.
In order to convert type declarations into RTL, there is a function in the module `stor-layout.c' and one in `toplev.c'.
In order to realise the conversion between elementary data types, there is a function in `convert.c'.
In module `fold-const.c' are modules at your disposal, which enable the values of simple constant expressions to be calculated. Integers of up to 64 bits can be manipulated.
In order to put external declarations, in `C' extern into the RTL code and thereby into
the assembler source code, you can use a function from the module `varasm.c'.
In order to ease the laborious process of debugging, there is a module
`print-tree.c': The functions here have no use for the translation
process, but they enable the recursive output of structures in the
tree format. They are particularly useful when using the debugger
`gdb', to concisely and quickly print tree and rtl structures.
The modules `expr.c', `calls.c', `explow.c',
`expmed.c', `optabs.c', `emit-rtl.c' and
`insn-emit.c' indirectly take part in the conversion from
tree to RTL format. They are called by the above desribed modules
but not from the front end directly.
These modules are not called from the front end directly, rather they
are called from rest_of_compilation. There is some documentation
of them in the main GCC manual.
(a +
b)*(a + b), which can be transformed into (a + b)^2, can have
processing time saved
More on the calling of the opitimisation routines is found in the function `rest_of_compilation' in module `toplev.c' and in section `Passes' in Using and Porting Gnu CC.
You may have wondered how GCC version decides which machine architecture to generate code for: the source code of both modules `insn_emit.c' and `insn_output.c' is initially synthesised during the building of GCC out of the machine descriptions, so that here the properties of the concrete machine architectures can flow into the compiler.
One sees that fundamentally the functions which are necessary for the compilation of the program in a high level anguage like C or Pascal are present within only in a few modules.
In order to write a front end then, it is not necessary to be in intimate contact with RTL, in theory at least. In practice for reasons of debugging you will most likely become well acquainted with RTL.
If the described interface does not support the desired functionality then enhancement or modification of the back end is necessary. Of course, the current functionality is sufficient to produce a program as powerful as a Turing machine. Doing some things that way could be laborious or create inefficient code.
The alert reader will have observed that until now no mention has been
made of an essential component of all compilers, the symbol table. In
addition, it is striking that in the sections above on the tree
format no mention has been made of nodes for variable references, for
named types(13) and similar usual
constructs which many languages would need.
That is no deficiency. Nodes which represent references to declared names, do not exist, because the declarations are represented by the inclusion the declaration node itself in, for example, an expression.
Which declaration is represented through a name in a concrete situation depends of course on the scope visibility rules of the translated high level language. The front end will obviously resolve this with the help of a symbol table, but that is not a problem for the back end to solve. The symbol table is almost(14) solely the concern of the front end.
This method makes possible a very high degree of flexibiliy with regard to the still very diverse rules of visibility of names in the various high level languages. The back end itself can hardly take into account all conceivable cases. Given that the front end, in building up the expression inserts the referenced declaration itself into the tree; at the same time the back end needs no knowledge of the scope rules of the translated language, which makes for a considerable easing its task.
Together with the previously described storage management, one must
therefore naturally be constantly aware of the need to ensure that
tree nodes which represent declarations are not freed as long as
they remain visible according to the rules and may therefore be
referenced. This creates the well known and tiresome problem of
'dangling references'.
As previously mentioned, there are several global variables and functions, which can be called by the back end, but are not defined there. In other words, whoever implements a new front end, is therefore required to define and set these variables, and to define and implement the functions.
It is not forbidden to call these functions also from the front end itself, provided they work correctly with the back end; they must just fulfil their implicit specifications.
Note: These nodes are now mostly in an array called global_trees and are
accessed via macros, although the names are not in caps as is usual with
macros.
tree error_tree_mark_node used as a tree node, represents
a partial tree in which during semantic analysis errors were found, as
for example, an incorrectly typed partial tree. This is done, in order
to avoid the code generator working on empty or untranslatable
references to incompplete trees. If you prefer to work in the manner in
which semantic analysis does not take place on the tree format
(see section 14.3.2.2 Two Principal Possibilities), then this variable plays no role,
but it must nonetheless be set. Usually it is set in the function
`init_decl_processing'.
tree integer_type_node used as a tree node that
shows that the declaration for a fundamental type represents an integer,
eg in the language C on the declaration of the type `int'. This is
also usually set in the function `init_decl_processing' and then
not changed.
tree char_type_node: similar, but for letters, in C this is `char'
tree void_type_node The name says it already: represents
the empty type, especially important for procedures.
tree integer_zero_node, tree integer_one_node denote
respectively constants of type `integer_type_node', with the values
0 or 1, are used in numerous places, among others as true and false
in C.
tree current_function_decl - is `NULL' as long as no
function is being translated, and points otherwise to a tree node
with type `FUNCTION_DECL' which represents the function being
translated at the moment, representing the current translated function.
char *language_string: A character string, eg
`"Pascal"', which contains the name of the currently translated
language; has only cosmetic use, output at the start of the module
`toplev.c'.
int flag_traditional: Is needed by module `dwarfout.c'
and used only by the language C. Thereby various dialects of this
language are distinguished - See section `C Dialect Options' in Using and Porting Gnu CC.
The functions in this group serve to create fundamental types with the desired properties. This is particularly necessary in the language C. Many other high level lenguages create only one type for whole numbers, so these functions are no longer so important. Yet you must place an implementation at the disposal of the back end.
In general it is not recommended to implement these functions from nothing, rather to take as a model an implementation in a previous compiler and make only the necessary changes to it.
tree type_for_mode(enum machine_mode mode, int unsignedp):
Creates a tree node, which is of the desired `mode' , where
`mode' represents machine data types like whole or floating point numbers,
processor conditions, or higher data types and so forth. For details see
the files `machmode.h' and `machmode.def'.
tree type_for_size(unsigned precision, int unsignedp): a
tree node of type whole number of exactly `precision' bits,
which is unsigned precisely when `unsignedp' is non-zero.
tree unsigned_type(tree type): takes a basic type and
returns the unsigned variant.
tree signed_type(tree type): similarly, takes a basic type and
returns the signed variant.
tree signed_or_unsigned_type(int unsignedp, tree type): creates a
variant of `type', which is signless precisely when
`unsignedp' is non-zero.
tree convert(tree type, tree expr): creates an expression,
which has the same value as `expr', but has type `type'. The
simplest approach here is to use the implementation in
`c-convert.c'.
For some special operations it is necessary for the back end to have the option to access the symbol table of the front end, in order to insert things into it.
Particularly for the following functions it is sensible to use standard implementations, for these functions are very complex in their interactions.
Double book-keeping is recommended, which means the management of all
symbols in two tables: one expressely for the front end, with the help
of which the semantic analysis is performed, and which is also used to
find the tree nodes which correspond to a given declaration, and
a second, which works with the following functions, and whose main
purpose is the construction of a `BLOCK' node for each scope level.
void init_decl_processing called from `toplev.c'
in order to initialize the symbol table: sets global variables, as
documented for example in section 14.3.5 Callback, inserts predefined variables
into the symbol table and so forth.
int global_bindings_p() is non-zero just when the current
scope is global; necessary in `toplev.c' for the correction of an
error, but which can be called, if, as in GCC, the semantic analysis is
carried out on the tree nodes.
tree getdecls() gives back a linked list of all declarations in
the current level of the symbol table. The order is inverted, opposite
to the original insertion sequence. These are needed in `toplev.c'
in order to output the symbol table, and on the other hand, in order to
define global variables which are declared but never defined.
int kept_level_p() is non-zero when a `BLOCK'
must be created for the current level of the symbol table. This function
is presently not used by the back end, only by the front
end(15).
void pushlevel(int ignore) creates a new level of the symbol
table, so that the introduction of a symbol with an already known name
causes a covering of the previous symbol. The parameter is always
`0' when called from the back end. It is recalled that new levels
are created not only by entry into a new function. Thus in C the
declaration of variables in the middle of the source text is enabled,
via a block statement(16) which corresponds to a level in the symbol table.
tree poplevel(int keep, int reverse, int functionbody) again
removes a level created by `pushlevel', returns the symbol table
back into the condition in which it was before the last
`pushlevel'. Returns a node of type `BLOCK'. tree nodes
of this type are used in order to generate information in the various
debugging formats. They have no real use for the actual translation. If
keep != 0, then a tree node of type `BLOCK' must be
created, otherwise this is not necessary. If reverse != 0, then
the list of declarations be must inverted, before they are are inserted
into the `BLOCK'. This has a partly historical basis(17). If functionbody != 0,
then the uncovered scope belongs to a function(18).
void insert_block(tree block) inserts the `BLOCK'
nodes into the list of the blocks within the current scope; this is
required in `expr.c' for the translation of the lambda-abstraction.
void set_block(tree block) sets the `BLOCK' for the current
scope; this is needed in several places in `integrate.c', also in
`stmt.c' of the creation of RTL for `goto' constructs, which
jump over the bounds of the scope regions.
tree pushdecl(tree decl) inserts the declaration `decl' into
the symbol table, and returns a tree node back. The returned node
need not necesarily be identical to the argument. In the case of an
equivalent declaration already in the symbol table, this is
returned. Thus redundant declarations can be easily caught. The
declarations are thereby placed at the front of the declaration list, so
that the list is inverted with respect to the insertion order. These
functions are used in `integrate.c' for 'inlining' in order to
insert into the containing function the declaration of the inserted
function.
All these functions are called from `toplev.c'. They neither take input parameters nor return a result. In the case when information transfer is necessary, then for good or evil global variables must result.
void lang_init(): Front end specific initialization like
setting certain global variables.
void lang_finish(): Front end specific cleanup.
init_lex(): No longer called.
init_parse. Initialization for the parsing and lexical analysis. Can be used to open files etc.
finish_parse. Wrap up the parsing and lexical analysis.
void lang_init_options(): Front end specific initialization for option processing.
This group of functions encompass functions which really depend on the semantics of the language. But here also again, it is easiest to adapt the source code of previous implementations.
tree maybe_build_cleanup(tree decl) creates a tree
node, which represents an automatic cleanup action. This is needed in
languages like C++ for the automatic calling of of destructors on
departure from a scope region or for exception handling. Otherwise
`NULL_TREE' can be returned.
tree incomplete_type_error(tree value, tree type) outputs
an error report, in the case where the type `type' was only
declared by way of a forward declaraion, but till now has not been defined.
`value' is the expression in which the error was detected, or
`NULL_TREE', in case the error is common.
tree truthvalue_conversion(tree expr) returns an
expression which has the same value as `expr' but in a type which
represents truth values.
void mark_addressable(tree expr) marks `expr' as a
construct which needs an address in storage. If `expr' is a
variable declaration, it may not be placed in a register, whereas if it
is a function declaration, then it may not only exist in 'inline'
form. This relates to the address operator `&' in `C'.
copy_lang_decl(tree node) is needed in `integrate.c',
in order to copy declarations, in which `DECL_LANG_SPECIFIC != 0';
if there are no such nodes, the routine body may remain empty.
void print_lang_statistics() is called from `toplev.c' at
the end of the compilation process. This can therefore be used to output
statistical information about the compilation process, such as the
number of created tree nodes, elapsed time for the various
language specific optimization processes, and so forth. Bear in mind
that generally the compiler should produce no messages for a correct
input file, so it is probably best to output nothing unless an option
requests statistics (eg absence of the `quiet' option).
void yyerror(char *) is needed by parsers created by
`bison' or `yacc', in order to output error messages about
sytax errors.
void print_lang_decl(FILE *file, tree node, int indent)
outputs the declaration for `node' with indentation depth
`indent' to the file `file'.
void print_lang_type(FILE *file, tree node, int indent)
outputs the type for `node' with indentation depth
`indent' to the file `file'.
void print_lang_identifier(FILE *file, tree node, int indent)
outputs the identifier `node' with indentation depth `indent' to the
file `file'.
void set_yydebug(int value)
sets the debugging control for the sytax analysis on (value != 0)
or off (value == 0).
int lang_decode_option(char *opt) is called from
`toplev.c' for all options in the command line, which are declared
in the field `lang_options' and returns `0' if the option is
not recognized. Significantly it is recorded in global variables, that
this variable was recognized. These variables can then be read from a
common place.
int yyparse() is called from the function `compile_file' in
the module `toplev.c'. This function starts the syntax analysis and
thereby the translation process. As is known of `bison' or
`yacc', the return value is precisly zero if no errors occurred. It
is of course not necessary to realise the `yyparse' syntax analysis
with a `bison' generated program; other preparation methods are
quite acceptable. For the case where `bison' is used however, the
convention exists, to hold the results of the reduction of processed
statements in the parser for only a brief time, in order to make the
grammar readable. The greater part of the work - the semantic analysis
and the control of the code generator - are implemented in functions,
which are called from the grammar actions.
In this chapter, two solutions of a practical problem should be discussed: what to do in order to annex the GNU back end to your own compiler, or how do you write a compiler, which integrates seamlessly into the GNU compiler family?
Fundamentally these are two different questions, on which here also
separate answers should be given. One question is expressed in precise
form: what to do exactly, in order to write a compiler which complies
with the non-binding principles laid down by the authors of GCC? This
"official" method of proceeding is especially recommended, if the
semantic analysis uses the tree format as described above in
section 14.3.2.2 Two Principal Possibilities.
The author of this report has not himself held to this method of proceeding in his experimental implementation and instead proceeded in a different way to connect the GNU back end to a compiler.
Small modifications must be made to the driver `gcc' in order to inform it that the family of GNU compilers has grown. The module `toplev.c' must also take on small changes for each new member of the GNU compiler family, in order to recognize language specific options. This will be described shortly.
For the following it is useful, if you have installed GCC yourself, or at least have read and understood the file `INSTALL'. A certain experience with `make' files, the programming language `C', macros and the like must be assumed.
We start with the assumption that GCC is already unpacked and has been built and that the object files have not been deleted.
The official GNU philosophy is that each new language should correspond to its own subdirectory(19) in the main directory(20). First therefore you must create a new directory from the main directory using the `mkdir' command, and in which all of the following takes place.
In this directory the two files `Make-lang.in' and `Makefile.in' must be present. Both are part of the `make' file, which are incorporated into the larger `make' file through being called from the `make' file in the main directory.
`Make-lang.in' is actually included in the main makefile in the `gcc' directory. Its main role is to call the makefile in the language directory. For this makefile, the current directory `.' relates to the gcc object directory and the current source directory `srcdir' relates to the `gcc' source directory.
`Makefile.in' is used to create the makefile in the language directory. Thus the current directory and current source directory refer to the language source and object directory.
In addition, `config-lang.in', which is read by the shell script `configure', is needed. Concerning the contents of these files, the simplest approach is to copy the files from another language, such as for C++ from the directory `cp' and make appropriate changes. Simple sample files for this are also found in Kenner95b. Be sure to set the 'outputs' value as this tells configure where to place the generated Makefile.
Obviously also the source files and include files belong in the new subdirectory. Be careful to ensure that all the callback functions presented in section 14.3.5 Callback are implemented in the source code.
The original author has not himself adhered to the GNU scheme, though the translator did. It is indeed very flexible, general and capable, but - particularly for the inexperienced - difficult to see through. In addition, you can increase productivity if you manually bind together parts of the larger compiler.
You can speed up linking by using the following procedure. However with a reasonably fast CPU, this prociedure is not needed and the standard GNU procedure is sufficient. The procedure below has not been tested for several years and may no longer work.
The file `build-directory/gcc/stamp-objlist' has a list of the object files in GCC which are language independent:
../diagnostic.o ../toplev.o ../version.o ../tree.o ../print-tree.o ../stor-layout.o ../fold-const.o ../function.o ../stmt.o ../except.o ../expr.o ../calls.o ../expmed.o ../explow.o ../optabs.o ../real.o ../builtins.o ../intl.o ../varasm.o ../rtl.o ../print-rtl.o ../rtlanal.o ../emit-rtl.o ../genrtl.o ../dbxout.o ../sdbout.o ../dwarfout.o ../dwarf2out.o ../xcoffout.o ../bitmap.o ../alias.o ../gcse.o ../integrate.o ../jump.o ../cse.o ../loop.o ../unroll.o ../flow.o ../combine.o ../varray.o ../regclass.o ../regmove.o ../local-alloc.o ../global.o ../reload.o ../reload1.o ../caller-save.o ../insn-peep.o ../reorg.o ../haifa-sched.o ../final.o ../recog.o ../reg-stack.o ../regrename.o ../insn-opinit.o ../insn-recog.o ../insn-extract.o ../insn-output.o ../insn-emit.o ../lcm.o ../profile.o ../insn-attrtab.o ../sparc.o ../convert.o ../mbchar.o ../dyn-string.o ../splay-tree.o ../graph.o ../sbitmap.o ../resource.o ../hash.o ../predict.o ../lists.o ../ggc-common.o ../ggc-page.o ../simplify-rtx.o ../ssa.o ../bb-reorder.o ../sibcall.o ../conflict.o
On different architectures from sparc, the file `sparc.o' will be replaced by the appropriate file.
With `ld -r stamp-objlist -o ind.o' one can gather these object files into one large object file, which can serve again as input to the linker(21).
The make file should then be enhanced as follows:
VPATH = . $(OTHER_DIRS)
foo: ind.o toplev.o $(OTHER_OBJS)
$(CC) -o foo ind.o toplev.o $(OTHER_OBJS)
and in order to create the driver:
prefix = /home/nadler # Installations directory
exec_prefix = $(prefix)
libdir = $(exec_prefix)/lib # gcc-lib comes from here
version = 2.7.2 # change correspondingly for other versions
target = sparc-sun-sunos4.1.3_U1
# change correspondingly for others
gcc_input_dirs = -Igcc272 -Igcc272/config # or where also
# the source code of GCC lies
MAKEGCCFLAGS = -DSTANDARD_STARTFILE_PREFIX=\"$(libdir)/\" \
-DSTANDARD_EXEC_PREFIX=\"$(libdir)/gcc-lib/\" \
-DDEFAULT_TARGET_VERSION=\"$(version)\" \
-DDEFAULT_TARGET_MACHINE=\"$(target)\" \
-DTOOLDIR_BASE_PREFIX=\"$(exec_prefix)/\"
gcc: gcc.c specs.h lang-specs.h version.o obstack.o
/home/nadler/bin/gcc $(gcc_input_dirs) $(MAKEGCCFLAGS)\
-o gcc gcc.c version.o obstack.o
Where `$(OTHER_OBJS)' is a `make' variable, in whose contents belong all other object files belonging to the compiler and `$(OTHER_DIRS)' contains other project directories(22).
The callback functions and the other variables mentioned are obviously defined in these object files. It is important to define the above mentioned make variables correctly, whereby the driver knows where it can find the compiler. As already stated above, it looks for the compiler in the directory `$(libdir)/gcc-lib/$(version)/$(target)/'.
For practical work it turns out for be advantageous, if you have various GCC programs: one which is never changed, which is called by `make', and which is used for practical work, and another, which one can play around with, try out new `specs' and for forth.
If part of the front end is already stable in the sense that one expects almost no more changes, then it is recommended to gather these parts into a larger object file using `ld -r'. The fewer open references the linker must close, the faster it runs. It pays therefore, to close cross references within the front end in this manner. However on modern CPUs this is not a big issue, as it only makes a difference of a second or two.
In order for the driver program `gcc' to know about the new compiler, it must be slightly modified. Note - you need not modify the source of the driver - the modification occurs automatically as part of the build process.
One should copy a file `lang-specs.h' into the new language's directory, for example out of the C++ directory `cp', and make modifications to it there.
In the already mentioned language `specs'(23) two facts must be specified:
{".cc", "@c++"},
{".cxx", "@c++"},
{".cpp", "@c++"},
{".c++", "@c++"},
{".C", "@c++"},
This is read as follows: if the file ends with one of the endings
`.cc, .cxx, .cpp, .c++' or `.C', then it is to be compiled
with the yet to be defined 'virtual' compiler named `C++'.
{"@c++",
"cpp -lang-c++ %{nostdinc*} %{C} %{v} %{A*} %{I*} %{P}\
%{C:%{!E:%eGNU C++ does not support -C without using -E}}\
-D__cplusplus %{W*}\n",
"%{!M:%{!MM:%{!E:cc1plus %{!pipe:%g.ii} %1 %2\
%{!Q:-quiet} -dumpbase %b.cc %{d*} %{m*} %{a}\
%{g*} %{O*} %{W*} %{w} %{pedantic*}\
%{v:-version} %{pg:-p} %{p}\
%{f*} \
%{S:%W{o*}%{!o*:-o %b.s}}}|\n\
%{!S:as %a %Y\
%{c:%W{o*}%{!o*:-o %w%b%O}}%{!c:-o %d%w%u%O}\
%{!pipe:%g.s} %A\n }}}}"},
The translator was called 'virtual' because it is not a program at the
operating system level, but is simply a name that refers to the calling
of a real program.
The example above is for illustrative purposes much shortened from `cp/lang-specs.h'. It means approximately;
A `specs' program is therefore simply a result of the expression of either or both of the forms described.
Therefore, what is required is to write a program to describe your own compiler. It can only be emphasised again, that the copying of pre-existing code is expressly encouraged, both by the author - from painful experience - and by the authors of GCC.
The author has not completely held to the GNU scheme in his experimental implementation. In order to be able to maintain a strict separation between the syntactic analysis, semantic analysis and code creation phases, which is not envisaged in the GNU scheme, instead of calling `yyparse', my own routine called `yyparse'is called, which in turn calls a the real though renamed `yyparse', obtains from this a syntax tree, and then from this starts the semantic analysis and the code creation. This decision is naturally purely a quetion of taste.
Also other changes may not be necessary but can be useful. Thus one can define additional options, in which the field `f_' is extended. These should certainly not be merely language specific options. It may thus be useful to define an option, whether a formatted output(24) is desired.
For really language specific options the callback function previously
mentioned lang_decode_option may be used. To have this called,
you must place the options to be handled into the field
`lang_options'. It should obviously be noted that the language
specific options and the `specs' programs must be coordinated with
one another. In the choice of options you should take care not to come
into conflict with already-used options.
It is useful, if your compiler uses the functions placed in `toplev.c' for error reporting, because that can contribute to a desirable unity. It is however not absolutely necessary.
A more detailed explanation of how the GCC makefiles work and how to integrate them is needed, but unfortunately does not exist. TODO.
See section 14.4.1 The Official GNU Way for some information on this..
A detailed explanation of how to use the GCC configuration information is needed but unfortunately does not exist. TODO when I have worked it out myself!
In this chapter the most important functions, constants and macros of the GNU back end are presented. The following is ordered according to themes, that is linguistic constructs.
Functions are given with their prototypes.
This chapter contains two examples section 14.9 Tree Examples which illustrate this material in context.
Note this discussion refers to the obsolete old style memory management. See above in section 14.3.3.5 Storage Management for the details of the new style memory management.
Defined in `tree.c', prototype declared in `tree.h'.
It depends on the current storage mode, from which area storage is obtained by the `build*' and `expand*' routines described in this section.
void temporary_allocation(): from now reserve storage from
the current `temporary' storage area.
void end_temporary_allocation(): switch temporarily, until
the next resume_temporary_allocation back into the
`permanent', but leave the `temporary' storage area unchanged.
void resume_temporary_allocation(): reverse
end_temporary_allocation and allocate from now on in the
`temporary' mode.
void permanent_allocation(int function_end): switch
permanently back to the `permanent' mode and release all the
objects allocate in the `temporary' storage area;
function_end != 0, if we have completed translating a global
function.
void push_obstacks_nochange(): creates a recovery marker in
the current storage area.
void pop_obstack(): returns to the previous recovery
marker, but does not free any storage.
The momentary area is intended for allocation of objects which only
exist transiently. This includes above all tree nodes which will
soon be translated into RTL code through an expand_(something)
call, thus for example expressions in statements, calls, conditions in
loops, conditional statements, case statements, but also assignments and
calls themsleves.
void push_momentary(): switch into the `momentary'
mode, if this mode is already active, creates a recovery marker.
void pop_momentary(): returns to the previous recovery
marker or returns to the previous mode respectively.
void clear_momentary(): frees all the objects allocated
since the last recovery marker.
int suspend_momentary(): switch temporarily again back to the
`temporary' mode. This is useful, if declarations are to be
translated, which in C as in many languages come in the middle of the
source code.
void resume_momentary(int flag): switches back to the
`momentary' mode, the parameter is the value returned from the
suspend_momentary call.
In a language like Pascal, it will seldom be necessary to use the
`momentary' storage property. An important use case arises from the
compilation of multiple branch statements. In this,
expand_end_case normally requires the branching expression as a
parameter, so after expand_start_case is called
push_momentary() is called, thereby through the following
clear_momentary() calls the branching expression is not freed.
The unified format in which the (partial) syntax tree is represented, is
called tree format and is defined in the file `tree.h'.
It exists as a series of struct types. Certainly it is not quite
as one may have expected, that is for each program language construct
its own struct type is defined. Rather a basic type struct
treee_common is defined which contains various fields, which all
nodes in the tree format have in common. Thereon to build up for
each 'class' of tree nodes, as for example declarations,
expressions or types, a struct type is defined, which contains
all fields which are only needed by nodes in this class. In all other
node types of this class the field remains unused.
The macros following access the fields common to all node types:
enum tree_code TREE_CODE(tree node): this particularly
important field contains a value which indicates exactly which node type
this node is.
An example of the value is `INTEGER_TYPE' for nodes which represent
a kind of whole number, or `VAR_DECL' for nodes which represent a
variable declaration, `MULT_EXPR' for a multiplication expression.
The node types are explained and defined in
`tree.def'. Unfortunately these values often have names which are
similar to the names of the access macros defined in `tree.h'. Care
is needed to avoid becoming confused.
tree node_type(tree node): often contains an pointer to the type
of the node. For derived types like arrays this points to the base type
for example. The code generator carries out almost no type consistency
checks; this is the responsibility of the front end. Generally if you
get it wrong you will find that no code is generated, or the compiler
may crash.
For array nodes it is your respnsibility to set the type field.
For pointer type nodes, this field points to the type to which the
pointer type points, similarly for field and reference types.
tree node_chain(tree node): each node can be included in a linked
list through this pointer. Note that some linked lists use this
field. In other case the nodes are linked togther via another set of
nodes which point to the subject nodes.
You are again reminded, that the convention is never to access the fields of a node directly, but always only by means of the macros defined in `tree.h'.
For the fields of tree nodes and their respective access macros,
in general the fields must be set before they have been passed to
an `expand' routine, for values subsequently set have no further
influence.
The code generator supports nested routines(25). One should create a new level in the `temporary' storage area for each level of nested routines if you are using old style memory management.
`decl' is always in this section a tree node, which
represents a declaration of node type `FUNCTION_DECL'.
void announce_function(tree decl), in `toplev.c': is
called at the beginning of the definition. Th effect is merely that an
announcement is output, which is generally suppressed through the
option `-quiet'.
void make_function_rtl(tree decl), in `varasm.c': call
for a declaration or definition of the function `decl', only once
naturally for each function. Issues the RTL code for the declaration of
the function (as opposed to the function body itself).
void init_function_start(tree decl, char *filename, int line), in
`function.c': called at the beginning of the code creation of the
body of the routine(26) for function declared with `decl'. Several variables are
set in file `function.c' to prepare it for the translation of a new
routine. `filename' is the name of the input file; this information
is required for the output of debugging information, the same for the
line number `line'. For other expressions you have to insert the
file/lineno information by other means (by inserting empty statements).
void expand_function_start(tree decl, int parms_have_cleanups),
in `function.c': likewise called at the beginning of the code
creation of the routine body for the function declared with `decl';
parms_have_cleanups != 0 just when upon reurn from the routine
`decl' certain cleanup actions on the input parameters are
required, which could be useful for certain parameter passing
mechanisms. It is important that the file name and line number be filled
in as line number == 0 is a magic flag in various parts of the code and
its use can cause crashes.
void expand_function_end(tree decl, int line, int end_bindings),
in `function.c': At the end of the code creation for the routine's
body, this is called for the function declared with `decl';
`line' is again the line number; end_bindings != 0 just when
`expand_function_end' should call the function
`expand_end_bindings'. It is important that the file name and line
number be filled in as line number == 0 is a magic flag in various parts
of the code and its use can cause crashes.
rest_of_compilation(tree decl), in `toplev.c':
carries out optimisation on prepared RTL code of the routine `decl'
and creates assembler code.
DECL_RESULT(decl): return variable of the function
`decl', is a declaration with `tree_code' `RESULT_DECL'
or `NULL_TREE' for procedures wihich which have no return
value. This variable contains the result of the function, which is given
back to the calling function.
DECL_ARGUMENTS(decl): points to the first element of
a list linked via `TREE_CHAIN' containing the declarations of the
formal parameters (`PARM_DECL') of `decl'.
TREE_TYPE(decl): function type of the routine
`decl', a tree node created by `build_function_type'.
DECL_INITIAL(decl): contains `BLOCK' nodes with
all declarations with `decl' for output in debugger format,
tree nodes created by `build_block', here most simply the
return value from `poplevel' (???).
TREE_PUBLIC(decl) != 0 when `decl' should also be
visible outside the current compilation unit, not used for routines
which are merely local. This is the opposite of static in
C.
TREE_STATIC(decl) != 0 just when `decl' has not
only been declared but also defined (not to be confused with
`static' in C).
TREE_EXTERNAL(decl) != 0 just when `decl' is
only a declaration for a definition outside the current compilation unit.
TREE_ADDRESSABLE(decl) != 0 just when `decl' is a
function which must have a non-inline version. This does not prevent it
from being inlined however, it just needs a non-inline copy..
void expand_start_bindings(int exit_flag):, in `stmt.c',
creates RTL for the beginning of a new scope region; exit_flag !=
0 just when this scope region can be exited by means of an `expand_exit_something'.
void expand_decl(tree decl), in `stmt.c', inserts the local
variable `decl' into the current scope region. In this case
TREE_CODE(decl) == VAR_DECL. This may ne incorrect - I think
pushdecl actually inserts it into the scope.
void expand_end_bindings(tree vars, int mark_ends, int
dont_jump_in), in `stmt.c', creates RTL for the end of a scope
region. In this case `vars' is the list of declaration nodes for
the variables declared in this scope region; this list is generally
supplied by a call to the callback function `getdecls()'.
mark_ends != 0 just when semantically meaningless RTL markers
would be placed at the beginning and end of the scope region;
dont_jump_in != 0 just when it is not allowed to jump into the
middle of the scope region, for example using `goto'.
void expand_decl_init(tree decl), in `stmt.c',
creates RTL for the initialization of the variable `decl', if
`DECL_INITIAL' is set, then to this value, otherwise 0 for basic types.
int expand_decl_cleanup(tree decl, tree cleanup), in
`stmt.c', creates RTL for a cleanup action(27) `cleanup' for the variable `decl', which
wll be automatically called up on departure from the scope
region. `cleanup' could be a call to a cleanup routine, but it may
in principle perform any complex tree expression.
tree build_block(vars, tags, subblocks, supercontext, chain), in
`tree.c'. This function is really only used in `poplevel'. It
creates a tree node of type `BLOCK' and initializes it:
This are numerous types supported. The `tree_code' constants for
types all have the form `*_TYPE'. For the creation of tree
nodes of many useful varieties of types, each one has its own
`build_*' function.
`make_node(enum tree_code code)': returns a node of the kind specified by `code'. Allocated from the storage area which is appropriate to the current mode. Nodes for the basic types are created using `make_node'.
The following values for `code' define the important basic types:
`tree make_node(enum tree_code INTEGER_TYPE)': creates a basic type for an integer type). This is primarily needed, in order to set the variable `integer_type_node' and for the implementation of the callback functions in section 14.3.5 Callback.
tree build_index_type(tree maxval): create an index type for
a field with possible index values between 0 and `maxval'.
tree build_index_2_type(tree lowval, tree highval): create an
index type for an array with possible indexes between `lowval' and
`highval'
tree build_array_type(tree elt_type, tree index_type): create
a type "array of `elt_type'"; `index_type' is an index type
created with `build_index_type' or `build_index_2_type'.
The creation of function is quite involved.
You have to create what is effectively a function prototype which contains a list of the types of the paramaters and also their names and the return value.
The type list is a list of tree_list nodes whose value field contains a
pointer to the type. This list is created with tree_cons.
A special 'magic' type node type_void_node pointed to by the
tree_list node at the end of the list is used to indicate that the
parameter list is fixed in length. In its absence the parameter list can have
extra elements (as in `printf(FILE f,char * s,,...)' in C).
You need to create the return value type and store it in the
DECL_RESULT field. If the return value is void, them you can
(28) use NULL_TREE or void_type_node
in the DECL_RESULT field to indicate this.
When creating the body of a function you also have to create the format
parameters. These are a list of variable declarations and are lisked
together by the tree_chain field. You can use chainon to
link them together.
You need to create two levels of blocks at least within the function, and assign the return value and then call a macro to say that it is the return value.
When calling a function you have to create a tree node for a
pointer to the function as well as all the actual parameters and link
them together, then create the function call and embed it in an
expression. The actual parameters are linked via tree_list nodes
using tree_cons.
It is important to set the flags indicating that the function has side-effects for example if it returns a void, otherwise it will not have code generated. Finally it is inportant to ensure that all the actual parameters are cast to the right values, even if this is a no-op (ie a NOP_EXPR).
Take close note of the sample calls in the sample applications and in the `cobcbei.c' routine in the COBOL compiler.
tree build_function_type(tree (value_type, tree arg_types):
creates a node for the type of function with return type
`value_type' and then parameter types
`arg_types'. `arg_types' is a `TREE_LIST' of `*_TYPE'
nodes. Each `FUNCTION_DECL' requires in its `CODE_TYPE' field
a pointer to a node of type `FUNCTION_TYPE'.
Unfortunately there is no complete single function for the creation of
tree nodes for record types.
tree make_node(RECORD_TYPE): creates an initially empty
record type like `struct' in C or `record' in Pascal, the
fields are progressively inserted. When the record type is ready,
`layout_type' and `rest_of_type_compilation' must be called.
RECORD_TYPE, but here
all fields lie at the same address, corresponding to `union' in C
tree build_decl(FIELD_DECL, tree name, tree type): creates
a field declaration with a name `name' and the type `type',
does not insert it into any record however. This must be done "by
hand", in which it is connected into the list, connected by
`TREE_CHAIN', and linked off the `TYPE_FIELDS' field of the
record node.
void layout_type(tree type), in the module
`stor-layout.c', must be called in order to calculate the size of an
object of type `type'.
rest_of_type_compilation(tree type), in module
`toplev.c', must be called in order to convert the format of a
record into a format readable by the debugger.
tree build_pointer_type(tree type): creates a type of the
form "pointer to `type'", where `type' is a type itself of course.
For the sake of completeness, several types are mentioned here, but not further explained. Further reference is available in `tree.h' and above all in `tree.def'.
tree get_identifier(char *str): returns a tree
node for the name `str'.
tree build_decl(enum tree_code code, tree name, tree type):
creates a declaration node with the (following later) permissible value
of `code'. Name is a node created with `get_identifier'.
`tree_code' for `build_decl': `VAR_DECL'
DECL_CONTEXT(decl) must point to the `FUNCTION_DECL':
in which the variable is declared, or `NULL_TYPE' for global variables.
TREE_TYPE(decl) is the declared type.
DECL_INITIAL(decl) can contain a value (tree), to which
the variable should be initialized.
TREE_PUBLIC(decl) != 0 just when `decl' should be
visible also outside the current translation unit, only useful for
global variables.
TREE_STATIC(decl) != 0 just when `decl' is not only
declared but also defined (not to be confused with `static' in C).
TREE_EXTERNAL(decl) != 0 just when `decl' a
declaration is outside the current translation unit, only useful for
global variables.
TREE_ADDRESSABLE(decl) != 0 just when `decl' is a
function, for which a non-inline version is required.
A special case is the `RESULT_DECL': it declares the result variable of a function. It is only useful as `DECL_RESULT' field in a `FUNCTION_DECL'.
tree) to which the
formal parameter should be pre-initialized. I am not sure where this
feature is used if anywhere.
tree) to which
the argument should be converted. In C for example `char' is
converted into `int'.
TREE_READONLY != 0, when parameter may not be set. Many
languages, for example Eiffel, permit no writing to formal parameters.
were already explained in section 14.5.5.5 Record Types.
See above in section 14.5.3 Routines.
build_decl(CONST_DECL, tree name, tree type): creates a
symbolic constant with the name `name' and the type `type'.
tree representations of expressions as constructs which
represent objects, which have values at run time, are primarily created
with the help of the following three functions:
tree build(enum tree_code code, tree type, ...): this
is the basic function with the help of which the majority of the
expressions in this section are created. `code' is a constant of
enumeration type `enum tree_code', which gives the type of the
desired expression. There are constants for addition, comparisons,
function calls, dereferencing and so on. In the following sections the
creation of expressions with the various values is presented. Each
expression has a type `type'. This is a tree of the form
presented in section 14.5.5 Types.
tree build1(enum tree_code code, tree type, tree expression): is
a special case, which runs faster, of build for the case that the
expression has only one child node.
tree build_nt(enum tree_code code, ...): just like
`build', but without a type parameter.
`TRUTH_ANDIF_EXPR' and `TRUTH_ORIF_EXPR' denote semi-strict expressions, which means that the calculation operation is terminated, if the result is clear from the result of the left hand side operand.
`type' is most usefully a type which only represents the values true and false. But that need not be the case. C for example uses whole number types for truth expressions.
build1(NOT_EXPR, tree type, tree expression): logical
negation (NOT) of `expression'.
tree build(TRUTH_ANDIF_EXPR, tree type, tree left, tree right):
semistrict conjunction (AND).
tree build(TRUTH_AND_EXPR, tree type, tree left, tree
right): strict conjunction (AND).
tree build(TRUTH_ORIF_EXPR, tree type, tree left, tree right):
semistrict disjunction (OR).
tree build(TRUTH_OR_EXPR, tree type, tree left, tree right):
strict disjunction (OR).
tree build(TRUTH_XOR_EXPR, tree type, tree left, tree
right): exclusive OR.
The usual arithmetic expressions for negation, addition, subtraction, multiplication, and exponentiation are supported. Besides there is a whole series of division and modulus expressions which all behave differently according to whether upward or downward rounding or truncation should be done, in case of a remainder.
Either both operands must be floating point or both operands must be fixed point. (It must not be a matter of the same types ??? Es mu"s sich nicht um denselben Typ handeln.) `type' must come from the same family of types as both operands. If a floating point number needs to be combined with a fixed point number, then a type conversion is necessary, see `CONVERT_EXPR'.
build1(NEGATE_EXPR, type, expression): create unary negation,
thus an expression of the form `-expression'.
build(PLUS_EXPR, type, left, right): addition of
`left' and `right'.
build(MINUS_EXPR, type, left, right): subtraction - `right' from `left'
build(MULT_EXPR, type, left, right): multiplication
There are various divisions operations supported for whole numbers:
There are also the corresponding remainder operations; here are the `TREE_CODE' values:
Equality and inequality tests are permitted for the supported (??? beliebige) types. `type' is most usefully of the same type which is used in logical expressions.
build(EQ_EXPR, tree type, tree left, tree right): equality test
build(NE_EXPR, tree type, tree left, tree right):
inequality test
Ordinal relations on the other hand are only supported for whole number, floating point and pointer types.
build(LT_EXPR, tree type, tree left, tree right): less than
build(LE_EXPR, tree type, tree left, tree right): less than
or equal
build(GT_EXPR, tree type, tree left, tree right): greater
than
build(GE_EXPR, tree type, tree left, tree right): greater
than or equal
The types `HOST_WIDE_INT' and `REAL_VALUE_TYPE' are defined in the `machmode.h' and `real.h' architecture dependent files.
tree build_int_2(HOST_WIDE_INT low, HOST_WIDE_INT hi):
creates a constants of whole number type `integer_type_node'. If
desired the type (`TREE_TYPE') of the constant can later be set to
another whole number type. In order to make it possible to have
constants which are larger than those directly supported by the machine
architecture, the value must be given in two halves. In case only the
usually wide value is used, `hi' must be set to the correct sign:
build_int_2(low, low >= 0 ? 0 : -1); is a correct call in this case.
tree build_real(tree type, REAL_VALUE_TYPE value): creates
a floating point constant of type `type' with value `value'.
tree build_real_from_int_cst(tree type, tree value): the same,
but value `value' is here a whole number constant tree
created with `build_int_2'.
tree build_string(int len, char *str): creates a character string
of length `len' and with contents `str'. You must set the
TREE_TYPE, probably to an array of bytes.
It is not necessary to distinguish between function and procedure calls. See procedure calls in section 14.5.9.1 Calls and Assignments.
build1(NOP_EXPR, void_type_node, NULL_TREE): empty expression,
useful only for conversion expressions for which no code creation is
needed, as perhaps between whole number and pointer types, or between different pointer types.
build1(CONVERT_EXPRESSION, tree type, tree expression):
creates a tree expression with the same value as
`expression', but with a new type. Used for conversions, for which
code must be created.
build1(INDIRECT_REF, type, expr): returns an expression
which represents the dereferencing of a pointer. `expr' is an
expression which must have pointer type.
build(COMPONENT_REF, type, record, field): returns an
expression, which accesses the field `field' from the record
`record'. The expression `record' must have record type,
`field' must be a field declaration from the type of `record'.
build(ARRAY_REF, type, array, index_list): returns an
expression which represents access to a field. `array' must be a
possibly multi-dimensional array; `index_list' must be a
`TREE_LIST' of expressions with whole number type.
As always, `type' is the type of the returned expression; as always pay attention to consistency. For dereferencing of a pointer to a whole number type, you should specify the whole number type and not the field type. "She'll be right mate" will not work - you need to get the types just right.
For the compilation of functional programs, several expressions are needed which represent control structures. For the compilation of imperative programs the functions explained above in section 14.3.2.5 Control Structures may be used to regulate the flow of control. It is naturally possible to do this also with the constructs presented here.
As far as I am aware these constructs are not used by any language - there are no functional languages in the GCC family. So use them with caution.
build(COMPOUND_EXPR, type, expression, value): creates an
expression, which first computes `expression', then `value' and
returns the results of `value'. Corresponds to the `,'
operator in C.
build1(LABEL_EXPR, void_type_node, label): creates an expression,
which is a jump label set to `label'. `label' is a
`LABEL_DECL'.
build1(GOTO_EXPR, void_type_node, label): creates an
expression, which executes an unconditional jump to the jump label
`label'. `label' is a `LABEL_DECL'.
build1(RETURN_EXPR, type, expression): creates an expression,
which the current function leaves (??? verl"a"st) after evaluation of
`expression'. The returned value is the momentary value of
`RESULT_DECL' of the current function.
build1(LOOP_EXPR, void_type_node, body):
creates an expression, which represents a loop with body `body'.
build1(EXIT_EXPR, void_type_node, cond):
creates an expression, which leaves the surrounding loop, if the
condition `cond' is evaluated to 'true'.
build(COND_EXPR, type, cond, then_part, else_part):
creates an expression, which first evaluates `cond', and returns
the value of `then_part' if `cond' is evaluated to 'true',
and otherwise returns the value of `else_part'. This corresponds to
the `? :' operator in C. `type' type is as always the type of
the created expression.
build(BIND_EXPR, type, vars, body, block) creates a
lambda-abstraction, over the variables listed in `vars', with
`body' as body of the expression in which the variables in
`vars' occur. `vars' is the first element of list linked by
`tree_chain'. `body' is an expression. `block' is a
`BLOCK' created by means of `build_block', which contains the
variables for the debugger. If one encloses the body of the abstraction
through `pushlevel'/`poplevel', one obtains `BLOCK' as
the return from the `poplevel'.
There are yet more expressions than have been presented up to now, for example for shift and rotation operations, for bitwise combination, for Pascal style set operations, for auto increment and decrement, for complex numbers and even more. They are defined and explained in `tree.def'.
The following functions are defined and explained together in
`stmt.c'. Some of these functions take a tree node
representing an expression, as a parameter. The expression is
translated into RTL upon request.
void expand_start_cond(tree cond, int exitflag): creates RTL code
for the beginning of a conditional statement. `cond' is the test
condition; exitflag != 0 just when the conditional statement can
be left through expand_exit_something.
void expand_start_elseif(tree cond): creates RTL code for
a further test condition.
void expand_start_else(): creates the beginning of the RTL
for the statement, which is executed if all the previous tests of this
conditional statement were false.
void expand_end_cond(): creates RTL for the end of this
conditional statement.
void expand_elseif(tree cond): converts the `else'
branch into a `elseif' under the condition `cond'. Purpose
unknown, not used in GCC itself.
Several of the following functions return a structure of type `struct nesting' or require such a value as a parameter. The contents of this structure are irrelevant for us, as it must merely be ensured that in each case the correct structure corresponding to the loop concerned is passed.
struct nesting *expand_start_loop(int exit_flag):
Creates the beginning of a loop; again exit_flag != 0 just when
the loop can be exited by `expand_exit_something'. A corresponding
`expand_continue_loop' will jump back to this place.
void expand_continue_loop(struct nesting *whichloop):
jumps, according to whether the beginning of the loop was created with
`expand_start_loop' or with
`expand_start_loop_continue_elsewhere', to the beginning or
respectively to the place established by
`expand_loop_continue_here'.
void expand_end_loop(): marks the end of a loop, is it
certainly not implicit that a jump back to the start of the loop
will take place; that is done by `expand_continue_loop'.
struct nesting (expand_start_loop_continue_elsewhere(int
exit_flag)), like `expand_start_loop', but the continuation point
of the loop must be explicitly set with `expand_loop_continue_here'.
void expand_loop_continue_here(): sets the continuation
point for the current loop.
void expand_exit_loop(struct nesting *whichloop):
Creates RTL code for an unconditional exit from the loop
`whichloop', corresponding to `break' in C.
int expand_exit_loop_if_false(struct nesting *whichloop, tree cond):
Creates RTL for a conditional departure from the loop
`whichloop'. If the runtime value of the expression `cond' is
false, then exit the loop, otherwise continue with the next statement.
void expand_start_case(int exit_flag, tree expr, tree type,
char *printname): creates RTL for beginning of a multibranch statement;
`expr' is the branch condition, `type' the
nominal(29) type; exit_flag != 0 is
again true, if this multibranch statement can be exited using
`expand_exit_something'. It is recommended, to set `exit_flag'
in order to allow exit from the statement in a manner similar to a C
`break'.
`printname' is an identifier which gives the name of the high
level construct, thus for example `switch' in C; this is needed for
certain error messages.
tree form, with the same value as
`v' but with type `t'.
tree pointer, which is set in the case of an
overlap, to the overlapping tree.
void pushcase_range(tree value1, tree value2, tree
(*converter)(tree, tree), tree label, tree *duplicate): just like
`pushcase', but for all cases between `value1' and
`value2' inclusive instead of only one value `value'.
`void int exit_something': creates RTL for exiting from the innermost enclosing structure, for which `exitflag = 1' was set. Returns `1' if no such statement exists.
tree expressions.
This chapter is the result of an extended engagement with the source code of GNAT, GPC and above all GCC(32).
An overview of the architecture and plan of the GNU compiler has been produced and presented, for how one's own front end can be connected to the GNU back end. The high level language constructs supported by the back end were described in detail, what to do in order to use these, including the data structures and functions which belong to each of these constructs, all presented in context.
Finally an example is presented (see section 14.9 Tree Examples) to demonstrate and hopefully simplify the use of the GNU back end.
An originally envisaged goal of this report, to make available for use an equally high level language independent and machine independent intermediate language, has not been fully realised. But that was not the main goal strived for. The main goal was to gather sufficient information, in order to be able to write this report, which gathers together the explicit and implicit information from the source code.
A really new programming language often distinguishes itself by its support of constructs which other languages do not posses. And to translate these into RTL may often be very difficult, because therefore detailed knowledge of RTL and the functions and data structures present in the GCC back end which are necessary for the direct creation of RTL code for the new constructs is needed, knowledge which is not needed for the simple use of the currently existing constructs.
One can also say, that the GNU back end suffices to translate 'conventional' languages. In order perhaps to realise a "Warren Abstract Machine" as is needed for the compilation of Prolog, the method of exclusive calls to the `build*' or `expand*' functions is probably not a good choice, even if on account of the undoubted `Turing' power available it must be possble to do so.
On the other hand the back end is sufficiently comprehensive for C, C++,
Objective C, Pascal and Ada 95. Even functional languages can be
relatively easily translated into the tree as shown in
section 14.5.7.8 Control Structures for Functional Programs. And additionally
especially for modern languages, their innovations are less in 'higher
constructs' but rather in encapsulation mechanisms like hiding and
modularity. The associated problems are rather a matter for the semantic
analysis than a matter for the code generator. One can therefore expect,
that the back end in its present form will suffice for many, though not
all conceivable languages.
The question certainly remains open, whether it would not be simpler, to output another less abstract high level language, like C, as the output from the compiler. True, that is also not trivial - for one thing simply on account of the possibility of semantic mismatch between the two languages - also open is the compilation strategy for certain source constructs(33), but this saves inbuilding the compiler into such a complex product as GCC and creates in spite of this comparatively high quality code. The immediate use of the code generator certainly has the advantage of offering better debugging possibilities due to the intimate knowledge of the data structures this makes possible..
One may wish that the code generator used fewer global variables: this would not only increase the comprehensibility of the code, it would also sooner allow the creation of a 'shared library'. Such a library would contribute to savings of processing resources: the program data for a GNU compiler in large part, for "C" over four fifths, arises from the code generator which is really the same for all languages; thus much disk space could be saved. However RMS is against the creation of a shared library in any case because this makes the use of parts of GCC in non-free programs more feasible.
The code generator also suffers from a limitation that it assumes the existence of a resgiter based machine. This has made it difficult to support so-called 'Java Chips' and certain functions such as the packed decimal support available in many mainframe computers.
Not all details could be comprehensively reported, simply on account of the extent of GCC. Whether the documentation gathered together in this report suffices to make the development of one's own compiler using GCC for code generation decisively easier, so that no intensive familiarisation is needed, the future will show. At least this report should suffice as the basis for one's own further investigation.
A few more tips:
The author and translator would be pleased to receive questions and comments at mailto:jnadler@gmx.net, and mailto:tej@melbpc.org.au.
We intend to offer this document to the FSF for inclusion in the GCC book, subject to having the appropriate documents signed by our school and employer respectively.
This section lists known sources of information about GCC internals and interfacing.
The list below lists miscellaneous references.
This section briefly records known changes made to GCC since this chapter was originally written.
The source code is available at http://cobolforgcc.sourceforge.net. They illustrate in practical terms the calling sequences and exchange of data required for interfacing to the code generation back end.
Two modules were created "by hand", and implement two well known simple algorithms. The first example recursively calculates the nth Fibonacci number and particularly illustrates function calls and branching. The second example iteratively calculates the factorial of the input parameter and thereby particularly illustrates looping.
Both show throughout the correct use of common constructs such as function declarations and variables.
There are known bugs; in particular they do not generate full and complete debug information even when the `-g' option is selected.
The structure of both examples is as follows:
tree-nodes for the implementation functions.
The source is commented (in English): the first example somewhat more comprehensively than the second, as many details are practically the same in both. These examples have been successfully tested.
A further example 'toy' is also included. Thus shows the integration with a real though simple parser.
If you want to use one as a base for a compiler, it is best to use toy, as copyright assignments are in place for the authors and maintainers of 'toy', which unfortunately is not the case for 'exa'. So if you use 'toy' as a base you can donate your compiler to the Free Software Foundation later on.
See http://cobolforgcc.sourceforge.net. This module is part of the cobol cvs tree, under `/gcc/exa'.
See http://cobolforgcc.sourceforge.net. This module is part of the cobol cvs tree, under `/gcc/toy'.
Go to the first, previous, next, last section, table of contents.