Front End
*********

This chapter describes some aspects of the design and implementation of the g77 front end.

Philosophy of Code Generation
=============================

Don't poke the bear.

The g77 front end generates code via the gcc back end.

The gcc back end (GBE) is a large, complex labyrinth of intricate code written in a combination of the C language and specialized languages internal to gcc.

While the code that implements the GBE is written in a combination of languages, the GBE itself is, to the front end for a language like Fortran, best viewed as a compiler that compiles its own, unique, language.

The GBE's ``source'', then, is written in this language, which consists primarily of a combination of calls to GBE functions and tree nodes (which are, themselves, created by calling GBE functions).

So, the g77 generates code by, in effect, translating the Fortran code it reads into a form ``written'' in the ``language'' of the gcc back end.

This language will heretofore be referred to as GBEL, for GNU Back End Language.

GBEL is an evolving language, not fully specified in any published form as of this writing. It offers many facilities, but its ``core'' facilities are those that corresponding most directly to those needed to support gcc (compiling code written in GNU C).

The g77 Fortran Front End (FFE) is designed and implemented to navigate the currents and eddies of ongoing GBEL and gcc development while also delivering on the potential of an integrated FFE (as compared to using a converter like f2c and feeding the output into gcc).

Goals of the FFE's code-generation strategy include:

  * High likelihood of generation of correct code, or, failing that, producing a fatal diagnostic or crashing.

  * Generation of highly optimized code, as directed by the user via GBE-specific (versus g77-specific) constructs, such as command-line options.

  * Fast overall (FFE plus GBE) compilation.

  * Preservation of source-level debugging information.

The strategies historically, and currently, used by the FFE to achieve these goals include:

  * Use of GBEL constructs that most faithfully encapsulate the semantics of Fortran.

  * Avoidance of GBEL constructs that are so rarely used, or limited to use in specialized situations not related to Fortran, that their reliability and performance has not yet been established as sufficient for use by the FFE.

  * Flexible design, to readily accommodate changes to specific code-generation strategies, perhaps governed by command-line options.

``Don't poke the bear'' somewhat summarizes the above strategies. The GBE is the bear. The FFE is designed and implemented to avoid poking it in ways that are likely to just annoy it. The FFE usually either tackles it head-on, or avoids treating it in ways dissimilar to how the gcc front end treats it.

For example, the FFE uses the native array facility in the back end instead of the lower-level pointer-arithmetic facility used by gcc when compiling f2c output). Theoretically, this presents more opportunities for optimization, faster compile times, and the production of more faithful debugging information. These benefits were not, however, immediately realized, mainly because gcc itself makes little or no use of the native array facility.

Complex arithmetic is a case study of the evolution of this strategy. When originally implemented, the GBEL had just evolved its own native complex-arithmetic facility, so the FFE took advantage of that.

When porting g77 to 64-bit systems, it was discovered that the GBE didn't really implement its native complex-arithmetic facility properly.

The short-term solution was to rewrite the FFE to instead use the lower-level facilities that'd be used by gcc-compiled code (assuming that code, itself, didn't use the native complex type provided, as an extension, by gcc), since these were known to work, and, in any case, if shown to not work, would likely be rapidly fixed (since they'd likely not work for vanilla C code in similar circumstances).

However, the rewrite accommodated the original, native approach as well by offering a command-line option to select it over the emulated approach. This allowed users, and especially GBE maintainers, to try out fixes to complex-arithmetic support in the GBE while g77 continued to default to compiling more code correctly, albeit producing (typically) slower executables.

As of April 1999, it appeared that the last few bugs in the GBE's support of its native complex-arithmetic facility were worked out. The FFE was changed back to default to using that native facility, leaving emulation as an option.

Other Fortran constructs---arrays, character strings, complex division, COMMON and EQUIVALENCE aggregates, and so on---involve issues similar to those pertaining to complex arithmetic.

So, it is possible that the history of how the FFE handled complex arithmetic will be repeated, probably in modified form (and hopefully over shorter timeframes), for some of these other facilities.

Two-pass Design
===============

The FFE does not tell the GBE anything about a program unit until after the last statement in that unit has been parsed. (A program unit is a Fortran concept that corresponds, in the C world, mostly closely to functions definitions in ISO C. That is, a program unit in Fortran is like a top-level function in C. Nested functions, found among the extensions offered by GNU C, correspond roughly to Fortran's statement functions.)

So, while parsing the code in a program unit, the FFE saves up all the information on statements, expressions, names, and so on, until it has seen the last statement.

At that point, the FFE revisits the saved information (in what amounts to a second pass over the program unit) to perform the actual translation of the program unit into GBEL, ultimating in the generation of assembly code for it.

Some lookahead is performed during this second pass, so the FFE could be viewed as a ``two-plus-pass'' design.

Two-pass Code
-------------

Most of the code that turns the first pass (parsing) into a second pass for code generation is in path-g77/std.c.

It has external functions, called mainly by siblings in path-g77/stc.c, that record the information on statements and expressions in the order they are seen in the source code. These functions save that information.

It also has an external function that revisits that information, calling the siblings in path-g77/ste.c, which handles the actual code generation (by generating GBEL code, that is, by calling GBE routines to represent and specify expressions, statements, and so on).

Why Two Passes
--------------

The need for two passes was not immediately evident during the design and implementation of the code in the FFE that was to produce GBEL. Only after a few kludges, to handle things like incorrectly-guessed ASSIGN label nature, had been implemented, did enough evidence pile up to make it clear that std.c had to be introduced to intercept, save, then revisit as part of a second pass, the digested contents of a program unit.

Other such missteps have occurred during the evolution of the FFE, because of the different goals of the FFE and the GBE.

Because the GBE's original, and still primary, goal was to directly support the GNU C language, the GBEL, and the GBE itself, requires more complexity on the part of most front ends than it requires of gcc's.

For example, the GBEL offers an interface that permits the gcc front end to implement most, or all, of the language features it supports, without the front end having to make use of non-user-defined variables. (It's almost certainly the case that all of K&R C, and probably ANSI C as well, is handled by the gcc front end without declaring such variables.)

The FFE, on the other hand, must resort to a variety of ``tricks'' to achieve its goals.

Consider the following C code:

     int
     foo (int a, int b)
     {
       int c = 0;

       if ((c = bar (c)) == 0)
         goto done;

       quux (c << 1);

     done:
       return c;
     }

Note what kinds of objects are declared, or defined, before their use, and before any actual code generation involving them would normally take place:

  * Return type of function

  * Entry point(s) of function

  * Dummy arguments

  * Variables

  * Initial values for variables

Whereas, the following items can, and do, suddenly appear ``out of the blue'' in C:

  * Label references

  * Function references

Not surprisingly, the GBE faithfully permits the latter set of items to be ``discovered'' partway through GBEL ``programs'', just as they are permitted to in C.

Yet, the GBE has tended, at least in the past, to be reticent to fully support similar ``late'' discovery of items in the former set.

This makes Fortran a poor fit for the ``safe'' subset of GBEL. Consider:

           FUNCTION X (A, ARRAY, ID1)
           CHARACTER*(*) A
           DOUBLE PRECISION X, Y, Z, TMP, EE, PI
           REAL ARRAY(ID1*ID2)
           COMMON ID2
           EXTERNAL FRED

           ASSIGN 100 TO J
           CALL FOO (I)
           IF (I .EQ. 0) PRINT *, A(0)
           GOTO 200

           ENTRY Y (Z)
           ASSIGN 101 TO J
     200   PRINT *, A(1)
           READ *, TMP
           GOTO J
     100   X = TMP * EE
           RETURN
     101   Y = TMP * PI
           CALL FRED
           DATA EE, PI /2.71D0, 3.14D0/
           END

Here are some observations about the above code, which, while somewhat contrived, conforms to the FORTRAN 77 and Fortran 90 standards:

  * The return type of function X is not known until the DOUBLE PRECISION line has been parsed.

  * Whether A is a function or a variable is not known until the PRINT *, A(0) statement has been parsed.

  * The bounds of the array of argument ARRAY depend on a computation involving the subsequent argument ID1 and the blank-common member ID2.

  * Whether Y and Z are local variables, additional function entry points, or dummy arguments to additional entry points is not known until the ENTRY statement is parsed.

  * Similarly, whether TMP is a local variable is not known until the READ *, TMP statement is parsed.

  * The initial values for EE and PI are not known until after the DATA statement is parsed.

  * Whether FRED is a function returning type REAL or a subroutine (which can be thought of as returning type void or, to support alternate returns in a simple way, type int) is not known until the CALL FRED statement is parsed.

  * Whether 100 is a FORMAT label or the label of an executable statement is not known until the X = statement is parsed. (These two types of labels get very different treatment, especially when ASSIGN'ed.)

  * That J is a local variable is not known until the first ASSIGN statement is parsed. (This happens after executable code has been seen.)

Very few of these ``discoveries'' can be accommodated by the GBE as it has evolved over the years. The GBEL doesn't support several of them, and those it might appear to support don't always work properly, especially in combination with other GBEL and GBE features, as implemented in the GBE.

(Had the GBE and its GBEL originally evolved to support g77, the shoe would be on the other foot, so to speak---most, if not all, of the above would be directly supported by the GBEL, and a few C constructs would probably not, as they are in reality, be supported. Both this mythical, and today's real, GBE caters to its GBEL by, sometimes, scrambling around, cleaning up after itself---after discovering that assumptions it made earlier during code generation are incorrect.)

So, the FFE handles these discrepancies---between the order in which it discovers facts about the code it is compiling, and the order in which the GBEL and GBE support such discoveries---by performing what amounts to two passes over each program unit.

(A few ambiguities can remain at that point, such as whether, given EXTERNAL BAZ and no other reference to BAZ in the program unit, it is a subroutine, a function, or a block-data---which, in C-speak, governs its declared return type. Fortunately, these distinctions are easily finessed for the procedure, library, and object-file interfaces supported by g77.)

Challenges Posed
================

Consider the following Fortran code, which uses various extensions (including some to Fortran 90):

     SUBROUTINE X(A)
     CHARACTER*(*) A
     COMPLEX CFUNC
     INTEGER*2 CLOCKS(200)
     INTEGER IFUNC

     CALL SYSTEM_CLOCK (CLOCKS (IFUNC (CFUNC ('('//A//')'))))

The above poses the following challenges to any Fortran compiler that uses run-time interfaces, and a run-time library, roughly similar to those used by g77:

  * Assuming the library routine that supports SYSTEM_CLOCK expects to set an INTEGER*4 variable via its COUNT argument, the compiler must make available to it a temporary variable of that type.

  * Further, after the SYSTEM_CLOCK library routine returns, the compiler must ensure that the temporary variable it wrote is copied into the appropriate element of the CLOCKS array. (This assumes the compiler doesn't just reject the code, which it should if it is compiling under some kind of a "strict" option.)

  * To determine the correct index into the CLOCKS array, (putting aside the fact that the index, in this particular case, need not be computed until after the SYSTEM_CLOCK library routine returns), the compiler must ensure that the IFUNC function is called.

     That requires evaluating its argument, which requires, for g77 (assuming -ff2c is in force), reserving a temporary variable of type COMPLEX for use as a repository for the return value being computed by CFUNC.

  * Before invoking CFUNC, is argument must be evaluated, which requires allocating, at run time, a temporary large enough to hold the result of the concatenation, as well as actually performing the concatenation.

  * The large temporary needed during invocation of CFUNC should, ideally, be deallocated (or, at least, left to the GBE to dispose of, as it sees fit) as soon as CFUNC returns, which means before IFUNC is called (as it might need a lot of dynamically allocated memory).

g77 currently doesn't support all of the above, but, so that it might someday, it has evolved to handle at least some of the above requirements.

Meeting the above requirements is made more challenging by conforming to the requirements of the GBEL/GBE combination.

Transforming Statements
=======================

Most Fortran statements are given their own block, and, for temporary variables they might need, their own scope. (A block is what distinguishes { foo (); } from just foo (); in C. A scope is included with every such block, providing a distinct name space for local variables.)

Label definitions for the statement precede this block, so 10 PRINT *, I is handled more like fl10: { ... } than { fl10: ... } (where fl10 is just a notation meaning ``Fortran Label 10'' for the purposes of this document).

Statements Needing Temporaries
------------------------------

Any temporaries needed during, but not beyond, execution of a Fortran statement, are made local to the scope of that statement's block.

This allows the GBE to share storage for these temporaries among the various statements without the FFE having to manage that itself.

(The GBE could, of course, decide to optimize management of these temporaries. For example, it could, theoretically, schedule some of the computations involving these temporaries to occur in parallel. More practically, it might leave the storage for some temporaries ``live'' beyond their scopes, to reduce the number of manipulations of the stack pointer at run time.)

Temporaries needed across distinct statement boundaries usually are associated with Fortran blocks (such as DO/END DO). (Also, there might be temporaries not associated with blocks at all---these would be in the scope of the entire program unit.)

Each Fortran block should get its own block/scope in the GBE. This is best, because it allows temporaries to be more naturally handled. However, it might pose problems when handling labels (in particular, when they're the targets of GOTOs outside the Fortran block), and generally just hassling with replicating parts of the gcc front end (because the FFE needs to support an arbitrary number of nested back-end blocks if each Fortran block gets one).

So, there might still be a need for top-level temporaries, whose ``owning'' scope is that of the containing procedure.

Also, there seems to be problems declaring new variables after generating code (within a block) in the back end, leading to, e.g., label not defined before binding contour or similar messages, when compiling with -fstack-check or when compiling for certain targets.

Because of that, and because sometimes these temporaries are not discovered until in the middle of of generating code for an expression statement (as in the case of the optimization for X**I), it seems best to always pre-scan all the expressions that'll be expanded for a block before generating any of the code for that block.

This pre-scan then handles discovering and declaring, to the back end, the temporaries needed for that block.

It's also important to treat distinct items in an I/O list as distinct statements deserving their own blocks. That's because there's a requirement that each I/O item be fully processed before the next one, which matters in cases like READ (*,*), I, A(I)---the element of A read in the second item must be determined from the value of I read in the first item.

Transforming DO WHILE
---------------------

DO WHILE(expr) must be implemented so that temporaries needed to evaluate expr are generated just for the test, each time.

Consider how DO WHILE (A//B .NE. 'END'); ...; END DO is transformed:

     for (;;)
       {
         int temp0;

         {
           char temp1[large];

           libg77_catenate (temp1, a, b);
           temp0 = libg77_ne (temp1, 'END');
         }

         if (! temp0)
           break;

         ...
       }

In this case, it seems like a time/space tradeoff between allocating and deallocating temp1 for each iteration and allocating it just once for the entire loop.

However, if temp1 is allocated just once for the entire loop, it could be the wrong size for subsequent iterations of that loop in cases like DO WHILE (A(I:J)//B .NE. 'END'), because the body of the loop might modify I or J.

So, the above implementation is used, though a more optimal one can be used in specific circumstances.

Transforming Iterative DO
-------------------------

An iterative DO loop (one that specifies an iteration variable) is required by the Fortran standards to be implemented as though an iteration count is computed before entering the loop body, and that iteration count used to determine the number of times the loop body is to be performed (assuming the loop isn't cut short via GOTO or EXIT).

The FFE handles this by allocating a temporary variable to contain the computed number of iterations. Since this variable must be in a scope that includes the entire loop, a GBEL block is created for that loop, and the variable declared as belonging to the scope of that block.

Transforming Block IF
---------------------

Consider:

     SUBROUTINE X(A,B,C)
     CHARACTER*(*) A, B, C
     LOGICAL LFUNC

     IF (LFUNC (A//B)) THEN
       CALL SUBR1
     ELSE IF (LFUNC (A//C)) THEN
       CALL SUBR2
     ELSE
       CALL SUBR3
     END

The arguments to the two calls to LFUNC require dynamic allocation (at run time), but are not required during execution of the CALL statements.

So, the scopes of those temporaries must be within blocks inside the block corresponding to the Fortran IF block.

This cannot be represented ``naturally'' in vanilla C, nor in GBEL. The if, elseif, else, and endif constructs provided by both languages must, for a given if block, share the same C/GBE block.

Therefore, any temporaries needed during evaluation of expr while executing ELSE IF(expr) must either have been predeclared at the top of the corresponding IF block, or declared within a new block for that ELSE IF---a block that, since it cannot contain the else or else if itself (due to the above requirement), actually implements the rest of the IF block's ELSE IF and ELSE statements within an inner block.

The FFE takes the latter approach.

Transforming SELECT CASE
------------------------

SELECT CASE poses a few interesting problems for code generation, if efficiency and frugal stack management are important.

Consider SELECT CASE (I('PREFIX'//A)), where A is CHARACTER*(*). In a case like this---basically, in any case where largish temporaries are needed to evaluate the expression---those temporaries should not be ``live'' during execution of any of the CASE blocks.

So, evaluation of the expression is best done within its own block, which in turn is within the SELECT CASE block itself (which contains the code for the CASE blocks as well, though each within their own block).

Otherwise, we'd have the rough equivalent of this pseudo-code:

     {
       char temp[large];

       libg77_catenate (temp, 'prefix', a);

       switch (i (temp))
         {
         case 0:
           ...
         }
     }

And that would leave temp[large] in scope during the CASE blocks (although a clever back end *could* see that it isn't referenced in them, and thus free that temp before executing the blocks).

So this approach is used instead:

     {
       int temp0;

       {
         char temp1[large];

         libg77_catenate (temp1, 'prefix', a);
         temp0 = i (temp1);
       }

       switch (temp0)
         {
         case 0:
           ...
         }
     }

Note how temp1 goes out of scope before starting the switch, thus making it easy for a back end to free it.

The problem that solution has, however, is with SELECT CASE('prefix'//A) (which is currently not supported).

Unless the GBEL is extended to support arbitrarily long character strings in its case facility, the FFE has to implement SELECT CASE on CHARACTER (probably excepting CHARACTER*1) using a cascade of if, elseif, else, and endif constructs in GBEL.

To prevent the (potentially large) temporary, needed to hold the selected expression itself ('prefix'//A), from being in scope during execution of the CASE blocks, two approaches are available:

  * Pre-evaluate all the CASE tests, producing an integer ordinal that is used, a la temp0 in the earlier example, as if SELECT CASE(temp0) had been written.

     Each corresponding CASE is replaced with CASE(I), where I is the ordinal for that case, determined while, or before, generating the cascade of if-related constructs to cope with CHARACTER selection.

  * Make temp0 above just large enough to hold the longest CASE string that'll actually be compared against the expression (in this case, 'prefix'//A).

     Since that length must be constant (because CASE expressions are all constant), it won't be so large, and, further, temp1 need not be dynamically allocated, since normal CHARACTER assignment can be used into the fixed-length temp0.

Both of these solutions require SELECT CASE implementation to be changed so all the corresponding CASE statements are seen during the actual code generation for SELECT CASE.

Transforming Expressions
========================

The interactions between statements, expressions, and subexpressions at program run time can be viewed as:

     ACTION(EXPR)

Here, ACTION is the series of steps performed to effect the statement, and EXPR is the expression whose value is used by ACTION.

Expanding the above shows a typical order of events at run time:

     Evaluate EXPR
     Perform ACTION, using result of evaluation of EXPR
     Clean up after evaluating EXPR

So, if evaluating EXPR requires allocating memory, that memory can be freed before performing ACTION only if it is not needed to hold the result of evaluating EXPR. Otherwise, it must be freed no sooner than after ACTION has been performed.

The above are recursive definitions, in the sense that they apply to subexpressions of EXPR.

That is, evaluating EXPR involves evaluating all of its subexpressions, performing the ACTION that computes the result value of EXPR, then cleaning up after evaluating those subexpressions.

The recursive nature of this evaluation is implemented via recursive-descent transformation of the top-level statements, their expressions, their subexpressions, and so on.

However, that recursive-descent transformation is, due to the nature of the GBEL, focused primarily on generating a single stream of code to be executed at run time.

Yet, from the above, it's clear that multiple streams of code must effectively be simultaneously generated during the recursive-descent analysis of statements.

The primary stream implements the primary ACTION items, while at least two other streams implement the evaluation and clean-up items.

Requirements imposed by expressions include:

  * Whether the caller needs to have a temporary ready to hold the value of the expression.

  * Other stuff???