     [file gcc-common.texi not included]

This file documents the use and the internals of the GNU Treelang (treelang) compiler.  At the moment this manual is not incorporated into the main GCC manual as it is incomplete.  It corresponds to the GCC-version-GCC version of treelang.

Published by the Free Software Foundation 59 Temple Place - Suite 330 Boston, MA 02111-1307 USA

Copyright © 1995,1996,1997,1998,1999,2000,2001,2002,2003,2004,2005 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with the Invariant Sections being ``GNU General Public License'', the Front-Cover texts being (a) (see below), and with the Back-Cover Texts being (b) (see below).  A copy of the license is included in the section entitled ``GNU Free Documentation License''.

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU software.  Copies published by the Free Software Foundation raise funds for GNU development.

Introduction
************

This manual documents how to run, install and maintain treelang. It also documents the features and incompatibilities in the GCC-version-GCC version of treelang.

     [file gpl.texi not included]

     [file fdl.texi not included]

Contributors to GNU Treelang
****************************

Treelang was based on 'toy' by Richard Kenner, and also uses code from the GCC core code tree.  Tim Josling first created the language and documentation, based on the GCC Fortran compiler's documentation framework.  Treelang was updated to use the TreeSSA infrastructure by James A. Morrison.

  * The packaging and compiler portions of GNU Treelang are based largely on the GCC compiler. See Contributors to GCC (Using and Maintaining GCC), for more information.

  * There is no specific run-time library for treelang, other than the standard C runtime.

  * It would have been difficult to build treelang without access to Joachim Nadler's guide to writing a front end to GCC (written in German).  A translation of this document into English is available via the CobolForGCC project or via the documentation links from the GCC home page http://gcc.gnu.org.

     [file funding.texi not included]

Getting Started
***************

Treelang is a sample language, useful only to help people understand how to implement a new language front end to GCC.  It is not a useful language in itself other than as an example or basis for building a new language.  Therefore only language developers are likely to have an interest in it.

This manual assumes familiarity with GCC, which you can obtain by using it and by reading the manuals Using the GNU Compiler Collection (GCC) and GNU Compiler Collection (GCC) Internals.

To install treelang, follow the GCC installation instructions, taking care to ensure you specify treelang in the configure step by adding treelang to the list of languages specified by --enable-langauges, e.g. --enable-languages=all,treelang.

If you're generally curious about the future of treelang, see Projects. If you're curious about its past, see Contributors.

To see a few of the questions maintainers of treelang have, and that you might be able to answer, see Open Questions.

What is GNU Treelang?
*********************

GNU Treelang, or treelang, is designed initially as a free replacement for, or alternative to, the 'toy' language, but which is amenable to inclusion within the GCC source tree.

treelang is largely a cut down version of C, designed to showcase the features of the GCC code generation back end.  Only those features that are directly supported by the GCC code generation back end are implemented.  Features are implemented in a manner which is easiest and clearest to implement.  Not all or even most code generation back end features are implemented.  The intention is to add features incrementally until most features of the GCC back end are implemented in treelang.

The main features missing are structures, arrays and pointers.

A sample program follows:

     // function prototypes
     // function 'add' taking two ints and returning an int
     external_definition int add(int arg1, int arg2);
     external_definition int subtract(int arg3, int arg4);
     external_definition int first_nonzero(int arg5, int arg6);
     external_definition int double_plus_one(int arg7);

     // function definition
     add
     {
       // return the sum of arg1 and arg2
       return arg1 + arg2;
     }

     subtract
     {
       return arg3 - arg4;
     }

     double_plus_one
     {
       // aaa is a variable, of type integer and allocated at the start of
       // the function
       automatic int aaa;
       // set aaa to the value returned from add, when passed arg7 and arg7 as
       // the two parameters
       aaa=add(arg7, arg7);
       aaa=add(aaa, aaa);
       aaa=subtract(subtract(aaa, arg7), arg7) + 1;
       return aaa;
     }

     first_nonzero
     {
       // C-like if statement
       if (arg5)
         {
           return arg5;
         }
       else
         {
         }
       return arg6;
     }

Lexical Syntax
**************

Treelang programs consist of whitespace, comments, keywords and names.

  * Whitespace consists of the space character, a tab, and the end of line character.  Line terminations are as defined by the standard C library.  Whitespace is ignored except within comments, and where it separates parts of the program.  In the example below, A and B are two separate names separated by whitespace.

          A B

  * Comments consist of // followed by any characters up to the end of the line.  C style comments (/* */) are not supported.  For example, the assignment below is followed by a not very helpful comment.

          x = 1; // Set X to 1

  * Keywords consist of any of the following reserved words or symbols:

       * { used to start the statements in a function

       * } used to end the statements in a function

       * ( start list of function arguments, or to change the precedence of operators in an expression

       * ) end list or prioritized operators in expression

       * , used to separate parameters in a function prototype or in a function call

       * ; used to end a statement

       * + addition, or unary plus for signed literals

       * - subtraction, or unary minus for signed literals

       * = assignment

       * == equality test

       * if begin IF statement

       * else begin 'else' portion of IF statement

       * static indicate variable is permanent, or function has file scope only

       * automatic indicate that variable is allocated for the life of the current scope

       * external_reference indicate that variable or function is defined in another file

       * external_definition indicate that variable or function is to be accessible from other files

       * int variable is an integer (same as C int)

       * char variable is a character (same as C char)

       * unsigned variable is unsigned. If this is not present, the variable is signed

       * return start function return statement

       * void used as function type to indicate function returns nothing

  * Names consist of any letter or "_" followed by any number of letters, numbers, or "_".  "$" is not allowed in a name.  All names must be globally unique, i.e. may not be used twice in any context, and must not be a keyword.  Names and keywords are case sensitive.  For example:

          a A _a a_ IF_X

     are all different names.

Parsing Syntax
**************

Declarations are built up from the lexical elements described above.  A file may contain one of more declarations.

  * declaration: variable declaration OR function prototype OR function declaration

  * Function Prototype: storage type NAME ( optional_parameter_list )

          static int add (int a, int b)

  * variable_declaration: storage type NAME initial;

     Example:

          int temp1 = 1;

     A variable declaration can be outside a function, or at the start of a function.

  * storage: automatic OR static OR external_reference OR external_definition

     This defines the scope, duration and visibility of a function or variable

      1. automatic: This means a variable is allocated at start of the current scope and released when the current scope is exited.  This can only be used for variables within functions.  It cannot be used for functions.

      2. static: This means a variable is allocated at start of program and remains allocated until the program as a whole ends.  For a function, it means that the function is only visible within the current file.

      3. external_definition: For a variable, which must be defined outside a function, it means that the variable is visible from other files.  For a function, it means that the function is visible from another file.

      4. external_reference: For a variable, which must be defined outside a function, it means that the variable is defined in another file.  For a function, it means that the function is defined in another file.

  * type: int OR unsigned int OR char OR unsigned char OR void

     This defines the data type of a variable or the return type of a function.

      a. int: The variable is a signed integer.  The function returns a signed integer.

      b. unsigned int: The variable is an unsigned integer.  The function returns an unsigned integer.

      c. char: The variable is a signed character.  The function returns a signed character.

      d. unsigned char: The variable is an unsigned character.  The function returns an unsigned character.

  * parameter_list OR parameter [, parameter]...

  * parameter: variable_declaration ,

     The variable declarations must not have initializations.

  * initial: = value

  * value: integer_constant

     Values without a unary plus or minus are considered to be unsigned.

          e.g. 1 +2 -3

  * function_declaration: name { variable_declarations statements }

     A function consists of the function name then the declarations (if any) and statements (if any) within one pair of braces.

     The details of the function arguments come from the function prototype.  The function prototype must precede the function declaration in the file.

  * statement: if_statement OR expression_statement OR return_statement

  * if_statement: if ( expression ) { variable_declarations statements } else { variable_declarations statements }

     The first lot of statements is executed if the expression is nonzero.  Otherwise the second lot of statements is executed.  Either list of statements may be empty, but both sets of braces and the else must be present.

          if (a==b)
          {
          // nothing
          }
          else
          {
          a=b;
          }

  * expression_statement: expression;

     The expression is executed, including any side effects.

  * return_statement: return expression_opt;

     Returns from the function. If the function is void, the expression must be absent, and if the function is not void the expression must be present.

  * expression: variable OR integer_constant OR expression + expression OR expression - expression OR expression == expression OR ( expression ) OR variable = expression OR function_call

     An expression can be a constant or a variable reference or a function_call.  Expressions can be combined as a sum of two expressions or the difference of two expressions, or an equality test of two expresions.  An assignment is also an expression.  Expresions and operator precedence work as in C.

  * function_call: function_name ( optional_comma_separated_expressions )

     This invokes the function, passing to it the values of the expressions as actual parameters.

Compiler Overview
*****************

treelang is run as part of the GCC compiler.

  * It reads a user's program, stored in a file and containing instructions written in the appropriate language (Treelang, C, and so on).  This file contains source code.

  * It translates the user's program into instructions a computer can carry out more quickly than it takes to translate the instructions in the first place.  These instructions are called machine code---code designed to be efficiently translated and processed by a machine such as a computer.  Humans usually aren't as good writing machine code as they are at writing Treelang or C, because it is easy to make tiny mistakes writing machine code.  When writing Treelang or C, it is easy to make big mistakes. But you can only make one mistake, because the compiler stops after it finds any problem.

  * It provides information in the generated machine code that can make it easier to find bugs in the program (using a debugging tool, called a debugger, such as gdb).

  * It locates and gathers machine code already generated to perform actions requested by statements in the user's program.  This machine code is organized into libraries and is located and gathered during the link phase of the compilation process.  (Linking often is thought of as a separate step, because it can be directly invoked via the ld command.  However, the gcc command, as with most compiler commands, automatically performs the linking step by calling on ld directly, unless asked to not do so by the user.)

  * It attempts to diagnose cases where the user's program contains incorrect usages of the language.  The diagnostics produced by the compiler indicate the problem and the location in the user's source file where the problem was first noticed.  The user can use this information to locate and fix the problem.

     The compiler stops after the first error.  There are no plans to fix this, ever, as it would vastly complicate the implementation of treelang to little or no benefit.

     (Sometimes an incorrect usage of the language leads to a situation where the compiler can not make any sense of what it reads---while a human might be able to---and thus ends up complaining about an incorrect ``problem'' it encounters that, in fact, reflects a misunderstanding of the programmer's intention.)

  * There are a few warnings in treelang.  For example an unused static function generate a warnings when -Wunused-function is specified, similarly an unused static variable generates a warning when -Wunused-variable are specified. The only treelang specific warning is a warning when an expression is in a return statement for functions that return void.

treelang consists of several components:

  * A modified version of the gcc command, which also might be installed as the system's cc command. (In many cases, cc refers to the system's ``native'' C compiler, which might be a non-GNU compiler, or an older version of GCC considered more stable or that is used to build the operating system kernel.)

  * The treelang command itself.

  * The libc run-time library.  This library contains the machine code needed to support capabilities of the Treelang language that are not directly provided by the machine code generated by the treelang compilation phase.  This is the same library that the main C compiler uses (libc).

  * The compiler itself, is internally named tree1.

     Note that tree1 does not generate machine code directly---it generates assembly code that is a more readable form of machine code, leaving the conversion to actual machine code to an assembler, usually named as.

GCC is often thought of as ``the C compiler'' only, but it does more than that. Based on command-line options and the names given for files on the command line, gcc determines which actions to perform, including preprocessing, compiling (in a variety of possible languages), assembling, and linking.

For example, the command gcc foo.c drives the file foo.c through the preprocessor cpp, then the C compiler (internally named cc1), then the assembler (usually as), then the linker (ld), producing an executable program named a.out (on UNIX systems).

As another example, the command gcc foo.tree would do much the same as gcc foo.c, but instead of using the C compiler named cc1, gcc would use the treelang compiler (named tree1). However there is no preprocessor for treelang.

In a GNU Treelang installation, gcc recognizes Treelang source files by name just like it does C and C++ source files.  It knows to use the Treelang compiler named tree1, instead of cc1 or cc1plus, to compile Treelang files.  If a file's name ends in .tree then GCC knows that the program is written in treelang.  You can also manually override the language.

Non-Treelang-related operation of gcc is generally unaffected by installing the GNU Treelang version of gcc. However, without the installed version of gcc being the GNU Treelang version, gcc will not be able to compile and link Treelang programs.

The command gcc -v x.tree where x.tree is a file which must exist but whose contents are ignored, is a quick way to display version information for the various programs used to compile a typical Treelang source file.

The tree1 program represents most of what is unique to GNU Treelang; tree1 is a combination of two rather large chunks of code.

One chunk is the so-called GNU Back End, or GBE, which knows how to generate fast code for a wide variety of processors. The same GBE is used by the C, C++, and Treelang compiler programs cc1, cc1plus, and tree1, plus others. Often the GBE is referred to as the ``GCC back end'' or even just ``GCC''---in this manual, the term GBE is used whenever the distinction is important.

The other chunk of tree1 is the majority of what is unique about GNU Treelang---the code that knows how to interpret Treelang programs to determine what they are intending to do, and then communicate that knowledge to the GBE for actual compilation of those programs.  This chunk is called the Treelang Front End (TFE).  The cc1 and cc1plus programs have their own front ends, for the C and C++ languages, respectively.  These fronts ends are responsible for diagnosing incorrect usage of their respective languages by the programs the process, and are responsible for most of the warnings about questionable constructs as well.  (The GBE in principle handles producing some warnings, like those concerning possible references to undefined variables, but these warnings should not occur in treelang programs as the front end is meant to pick them up first).

Because so much is shared among the compilers for various languages, much of the behavior and many of the user-selectable options for these compilers are similar. For example, diagnostics (error messages and warnings) are similar in appearance; command-line options like -Wall have generally similar effects; and the quality of generated code (in terms of speed and size) is roughly similar (since that work is done by the shared GBE).

Compile Treelang, C, or Other Programs
**************************************

A GNU Treelang installation includes a modified version of the gcc command.

In a non-Treelang installation, gcc recognizes C, C++, and Objective-C source files.

In a GNU Treelang installation, gcc also recognizes Treelang source files and accepts Treelang-specific command-line options, plus some command-line options that are designed to cater to Treelang users but apply to other languages as well.

See Programming Languages Supported by GCC (Using the GNU Compiler Collection (GCC)), for information on the way different languages are handled by the GCC compiler (gcc).

You can use this, combined with the output of the gcc -v x.tree command to get the options applicable to treelang.  Treelang programs must end with the suffix .tree.

Treelang programs are not by default run through the C preprocessor by gcc. There is no reason why they cannot be run through the preprocessor manually, but you would need to prevent the preprocessor from generating #line directives, using the -P option, otherwise tree1 will not accept the input.

The GNU Treelang Compiler
*************************

The GNU Treelang compiler, treelang, supports programs written in the GNU Treelang language.

Other Languages
***************

Tools and advice for interoperating with C and C++
==================================================

The output of treelang programs looks like C program code to the linker and everybody else, so you should be able to freely mix treelang and C (and C++) code, with one proviso.

C promotes small integer types to 'int' when used as function parameters and return values in non-prototyped functions.  Since treelang has no non-prototyped functions, the treelang compiler does not do this.

treelang internals
******************

treelang files
==============

To create a compiler that integrates into GCC, you need create many files.  Some of the files are integrated into the main GCC makefile, to build the various parts of the compiler and to run the test suite.  Others are incorporated into various GCC programs such as gcc.c.  Finally you must provide the actual programs comprising your compiler.

The files are:

 1. COPYING.  This is the copyright file, assuming you are going to use the GNU General Public Licence.  You probably need to use the GPL because if you use the GCC back end your program and the back end are one program, and the back end is GPLed.

     This need not be present if the language is incorporated into the main GCC tree, as the main GCC directory has this file.

 2. COPYING.LIB.  This is the copyright file for those parts of your program that are not to be covered by the GPL, but are instead to be covered by the LGPL (Library or Lesser GPL).  This licence may be appropriate for the library routines associated with your compiler. These are the routines that are linked with the output of the compiler.  Using the LGPL for these programs allows programs written using your compiler to be closed source. For example LIBC is under the LGPL.

     This need not be present if the language is incorporated into the main GCC tree, as the main GCC directory has this file.

 3. ChangeLog.  Record all the changes to your compiler.  Use the same format as used in treelang as it is supported by an emacs editing mode and is part of the FSF coding standard.  Normally each directory has its own changelog.  The FSF standard allows but does not require a meaningful comment on why the changes were made, above and beyond why they were made.  In the author's opinion it is useful to provide this information.

 4. treelang.texi.  The manual, written in texinfo. Your manual would have a different file name.  You need not write it in texinfo if you don't want do, but a lot of GNU software does use texinfo.

 5. Make-lang.in.  This file is part of the make file which in incorporated with the GCC make file skeleton (Makefile.in in the GCC directory) to make Makefile, as part of the configuration process.

     Makefile in turn is the main instruction to actually build everything.  The build instructions are held in the main GCC manual and web site so they are not repeated here.

     There are some comments at the top which will help you understand what you need to do.

     There are make commands to build things, remove generated files with various degrees of thoroughness, count the lines of code (so you know how much progress you are making), build info and html files from the texinfo source, run the tests etc.

 6. README.  Just a brief informative text file saying what is in this directory.

 7. config-lang.in.  This file is read by the configuration progress and must be present. You specify the name of your language, the name(s) of the compiler(s) incouding preprocessors you are going to build, whether any, usually generated, files should be excluded from diffs (ie when making diff files to send in patches).  Whether the equate 'stagestuff' is used is unknown (???).

 8. lang.opt.  This file is included into gcc.c, the main GCC driver, and tells it what options your language supports.  This is also used to display help.

 9. lang-specs.h.  This file is also included in gcc.c. It tells gcc.c when to call your programs and what options to send them.  The mini-language 'specs' is documented in the source of gcc.c.  Do not attempt to write a specs file from scratch - use an existing one as the base and enhance it.

 10. Your texi files.  Texinfo can be used to build documentation in HTML, info, dvi and postscript formats. It is a tagged language, is documented in its own manual, and has its own emacs mode.

 11. Your programs.  The relationships between all the programs are explained in the next section.  You need to write or use the following programs:

       * lexer.  This breaks the input into words and passes these to the parser.  This is lex.l in treelang, which is passed through flex, a lex variant, to produce C code lex.c.  Note there is a school of thought that says real men hand code their own lexers.  However, you may prefer to write far less code and use flex, as was done with treelang.

       * parser.  This breaks the program into recognizable constructs such as expressions, statements etc.  This is parse.y in treelang, which is passed through bison, which is a yacc variant, to produce C code parse.c.

       * back end interface.  This interfaces to the code generation back end.  In treelang, this is tree1.c which mainly interfaces to toplev.c and treetree.c which mainly interfaces to everything else. Many languages mix up the back end interface with the parser, as in the C compiler for example.  It is a matter of taste which way to do it, but with treelang it is separated out to make the back end interface cleaner and easier to understand.

       * header files.  For function prototypes and common data items.  One point to note here is that bison can generate a header files with all the numbers is has assigned to the keywords and symbols, and you can include the same header in your lexer.  This technique is demonstrated in treelang.

       * compiler main file.  GCC comes with a file toplev.c which is a perfectly serviceable main program for your compiler.  GNU Treelang uses toplev.c but other languages have been known to replace it with their own main program.  Again this is a matter of taste and how much code you want to write.

treelang compiler interfaces
============================

treelang driver
---------------

The GCC compiler consists of a driver, which then executes the various compiler phases based on the instructions in the specs files.

Typically a program's language will be identified from its suffix (e.g., .tree) for treelang programs.

The driver (gcc.c) will then drive (exec) in turn a preprocessor, the main compiler, the assembler and the link editor. Options to GCC allow you to override all of this. In the case of treelang programs there is no preprocessor, and mostly these days the C preprocessor is run within the main C compiler rather than as a separate process, apparently for reasons of speed.

You will be using the standard assembler and linkage editor so these are ignored from now on.

You have to write your own preprocessor if you want one.  This is usually totally language specific.  The main point to be aware of is to ensure that you find some way to pass file name and line number information through to the main compiler so that it can tell the back end this information and so the debugger can find the right source line for each piece of code.  That is all there is to say about the preprocessor except that the preprocessor will probably not be the slowest part of the compiler and will probably not use the most memory so don't waste too much time tuning it until you know you need to do so.

treelang main compiler
----------------------

The main compiler for treelang consists of toplev.c from the main GCC compiler, the parser, lexer and back end interface routines, and the back end routines themselves, of which there are many.

toplev.c does a lot of work for you and you should almost certainly use it.

Writing this code is the hard part of creating a compiler using GCC.  The back end interface documentation is incomplete and the interface is complex.

There are three main aspects to interfacing to the other GCC code.

Interfacing to toplev.c
.......................

In treelang this is handled mainly in tree1.c and partly in treetree.c. Peruse toplev.c for details of what you need to do.

Interfacing to the garbage collection
.....................................

Interfacing to the garbage collection. In treelang this is mainly in tree1.c.

Memory allocation in the compiler should be done using the ggc_alloc and kindred routines in ggc*.*. At the end of every 'function' in your language, toplev.c calls the garbage collection several times. The garbage collection calls mark routines which go through the memory which is still used, telling the garbage collection not to free it. Then all the memory not used is freed.

What this means is that you need a way to hook into this marking process. This is done by calling ggc_add_root. This provides the address of a callback routine which will be called duing garbage collection and which can call ggc_mark to save the storage. If storage is only used within the parsing of a function, you do not need to provide a way to mark it.

Note that you can also call ggc_mark_tree to mark any of the back end internal 'tree' nodes. This routine will follow the branches of the trees and mark all the subordinate structures. This is useful for example when you have created a variable declaaration that will be used across multiple functions, or for a function declaration (from a prototype) that may be used later on. See the next item for more on the tree nodes.

Interfacing to the code generation code.
........................................

In treelang this is done in treetree.c. A typedef called 'tree' which is defined in tree.h and tree.def in the GCC directory and largely implemented in tree.c and stmt.c forms the basic interface to the compiler back end.

In general you call various tree routines to generate code, either directly or through toplev.c. You build up data structures and expressions in similar ways.

You can read some documentation on this which can be found via the GCC main web page. In particular, the documentation produced by Joachim Nadler and translated by Tim Josling can be quite useful. the C compiler also has documentation in the main GCC manual (particularly the current CVS version) which is useful on a lot of the details.

In time it is hoped to enhance this document to provide a more comprehensive overview of this topic. The main gap is in explaining how it all works together.

Hints and tips
==============

  * TAGS: Use the make ETAGS commands to create TAGS files which can be used in emacs to jump to any symbol quickly.

  * GREP: grep is also a useful way to find all uses of a symbol.

  * TREE: The main routines to look at are tree.h and tree.def. You will probably want a hardcopy of these.

  * SAMPLE: look at the sample interfacing code in treetree.c. You can use gdb to trace through the code and learn about how it all works.

  * GDB: the GCC back end works well with gdb. It traps abort() and allows you to trace back what went wrong.

  * Error Checking: The compiler back end does some error and consistency checking. Often the result of an error is just no code being generated. You will then need to trace through and find out what is going wrong. The rtl dump files can help here also.

  * rtl dump files: The main compiler documents these files which are dumps of the rtl (intermediate code) which is manipulated doing the code generation process. This can provide useful clues about what is going wrong. The rtl 'language' is documented in the main GCC manual.

Open Questions
**************

If you know GCC well, please consider looking at the file treetree.c and resolving any questions marked "???".

Reporting Bugs
**************

You can report bugs to gcc-bugs@gcc.gnu.org or bug-gcc@gnu.org. Please make sure bugs are real before reporting them. Follow the guidelines in the main GCC manual for submitting bug reports.

Sending Patches for GNU Treelang
================================

If you would like to write bug fixes or improvements for the GNU Treelang compiler, that is very helpful.  Send suggested fixes to gcc-patches@gcc.gnu.org.

How To Get Help with GNU Treelang
*********************************

If you need help installing, using or changing GNU Treelang, there are two ways to find it:

  * Look in the service directory for someone who might help you for a fee. The service directory is found in the file named SERVICE in the GCC distribution.

  * Send a message to gcc@gcc.gnu.org.

Projects
********

If you want to contribute to treelang by doing research, design, specification, documentation, coding, or testing, the following information should give you some ideas.

Send a message to gcc@gcc.gnu.org if you plan to add a feature.

The main requirement for treelang is to add features and to add documentation. Features are things that the GCC back end can do but which are not reflected in treelang. Examples include structures, unions, pointers, arrays.