% Copyright (C) 1989, Digital Equipment Corporation
% All rights reserved.
% See the file COPYRIGHT for a full description.
%
% Last modified on Thu Jul 19 02:40:12 1990 by muller
%      modified on Fri Nov  3 16:28:36 1989 by kalsow

\chapter{Internals}

This section contains a brief introduction to the internal structure
of the compiler and runtime system.  This introduction is neither
comprehensive nor tutorial; it is merely intended as a stepping stone
for the courageous.

\section{A tour of the compiler}
%===============================

The compiler has undergone much evolution.  It started as a project to
build a simple and easy to maintain compiler.  Somewhere along the way
we decided to compile \modula. Much later we decided to generate C.
In hindsight, \modula was a good choice, C was at best mediocre.

The initial observation was that most compilers' data structures were
visible and complex.  This situation makes it necessary to understand
a compiler in its entirety before attempting non-trivial enhancements
or bug fixes.  By keeping most of the compiler's primary data
structures hidden behind opaque interfaces, we hoped to avoid this
pitfall.  So far, bugs have been easy to find.  During early
development, it was relatively easy to track the weekly language
changes.

The compiler is decomposed by language feature rather than the more
traditional compiler passes.  We attempted to confine each language
feature to a single module.  For example, the parsing, name binding,
type checking and code production for each statement is in its own
module.  This separation means that only the \verb|CaseStmt| module
needs to know what data structures exist to implement
\verb|CASE| statements.
Other parts of the compiler need only know that the \verb|CASE|
statement is a statement.  This fact is captured by the object subtype
hierarchy.  A \verb|CaseStmt.T| is a subtype of a \verb|Stmt.T|.

The main object types within the compiler are: values, statements,
expressions, and types.  ``Values'' is a misnomer; ``bindings'' would
be better.  This object class include anything that can be named:
modules, procedures, variables, exceptions, constants, types,
enumeration elements, record fields, methods, and procedure formals.
Statements include all of the \modula statements.  Expressions include
all the \modula expression forms that have a special syntax.  And
finally, types include the \modula types.

The compiler retains the traditional separation
of input streams, scanner, symbol table, and output stream.

The compilation process retains the usual phases.  Symbols are scanned
as needed by the parser.  A recursive descent parser reads the entire
source and builds the internal syntax tree.  All remaining passes
simply add decorations to this tree.  The next phase binds all
identifiers to values in scopes.
\modula allows arbitrary forward references so it is necessary
to accumulate all names within a scope before binding any identifiers
to values.  The next phase divides the types into structurally
equivalent classes.  This phase actually occurs in two steps.  First,
the types are divided into classes such that each class will have a
unique C representation.  Then, those classes are refined into what
\modula defines as structurally equivalent types.  After the types
have been partitioned, the entire tree is checked for type errors.
Finally, the C code is emitted.
C's requirement that declarations precede uses means
that the code is generated in several passes.
First, the types are generated during type checking.
Then, the procedure headers are produced.
And finally, the procedure bodies are generated.

The compiler implementation is in the \verb|compiler| directory.
Within that directory the following directories exist:
\begin{quote}
\begin{tabular}{ll}
      builtinOps   & \verb|ABS|, \verb|ADR|, \verb|BITSIZE|, ...  \\
      builtinTypes & \verb|INTEGER|, \verb|CHAR|, \verb|REFANY|, ...  \\
      builtinWord  & \verb|Word.And|, \verb|Word.Or|, ... \\
      exprs        & \verb|+|, \verb|-|, \verb|[]|, \verb|^|,
                        \verb|AND|, \verb|OR|, ...  \\
      misc         & main program, scanner, symbol tables, ...  \\
      stmts        & \verb|:=|, \verb|IF|, \verb|TRY|, \verb|WHILE|, ... \\
      types        & \verb|ARRAY|, \verb|BITS FOR|, \verb|RECORD|, ...  \\
      values       & \verb|MODULE|, \verb|PROCEDURE|, \verb|VAR|, ...  \\
\end{tabular}
\end{quote}

\section{A tour of the runtime}
%==============================

The runtime itself implements the garbage collector,
\modula startup code and a few miscellaneous functions.  The runtime
exists in the \verb|runtime| directory.

The interface between the compiler and runtime system is embodied (and
very sparsely documented) in \verb|M3Runtime.h|, \verb|M3Machine.h| and
\verb|M3RuntimeDecls.h|.  Every C file generated by the compiler
includes these files.

The allocator and garbage collector are based on Joel Bartlett's
``mostly copying collector''.
The best description of his collector is
\begin{quote}
  Joel F. Bartlett,
  ``Compacting garbage collection with ambiguous roots,''
  Digital -- Western Research Laboratory,
  WRL Research Report 88/2,
  February 1988.
\end{quote}
Since that paper, we've made a few modifications to support a
growing heap and to use extra information that the \modula
compiler generates.

Exceptions are implemented with \verb|setjmp| and \verb|longjmp|.  The
jump buffers and scope descriptors are chained together to form a
stack.  The head of the chain is kept in \verb|ThreadSupport.handlers|.
There is a distinct chain for each thread.  When an exception is
raised, the chain is searched.  If a handler for the exception is
found, the exception is allowed to unwind the stack, otherwise a
runtime error is signaled.  To unwind the stack, a \verb|longjmp| is
done to the first handler on the stack.  It does whatever cleanup is
necessary and passes control on up the stack to the next handler until
the exception is actually handled.

Reference types are represented at runtime by a ``typecell''.  Due to
separate compilation, opaque types and revelations, it is not possible
to fully initialize typecells at compile time.  Typecell
initialization is finished at runtime prior to the execution of any
user code.  A typecell contains a type's typecode, a pointer to its
parent typecell, the size of the types referent and method list if
any, the type's brand, the number of open array dimensions, the type's
fingerprint, and procedures to initialize the typecell, initialize new
instances of the type, and print instances of the type.

Initialization of a \modula address space occurs in several steps.
First, all types are registered.  That is, a global array that points
to all typecells is built.  Next, the runtime verifies that all opaque
types have been given concrete representations.  Then, the
initialization of typecells is finished.  Then, all types with the
same brand and fingerprint are identified with the same typecode.
Then, a check is made to ensure that distinct types have distinct
brands.  Then, all global variables are initialized.  And finally the
main bodies of the modules are invoked.  The skeletal code that
ensures that every module is initialized is generated by
\verb|m3ld|(1).

Other parts of the runtime, such as threads, are actually implemented
in the core library.

Thread switching is implemented with \verb|setjmp| and \verb|longjmp|.
A timer interrupt (signal) is used to cause preemptive thread
switching.  The global variable \verb|ThreadSupport.self| points to the
currently running thread.  The integer \verb|ThreadSupport.inCritical| is
used by the runtime to prevent thread switching during garbage
collection and other ``atomic'' runtime operations.

\section{Porting to another machine}
%===================================

Anyone who is interested in porting this compiler is encouraged!  We
would like to know how it goes.  The primary concerns when doing a
port will be the size and alignment constraints of the target machine
and the runtime.  We tried to avoid suspicious C constructs, but we
doubt that we were completely successful.

The directions in this section are somewhat sparse. We tried to make
the installation of \srcmodula smooth, but it is another story to make
the development of ports smooth. Please bear with us and tell us what
we can do to improve this section.

\paragraph{General.} 

If you want to a port to an unsupported system you should:
\begin{itemize}

\item install \srcmodula for multiple architectures (see
section~\ref{multiple-config}). One of them 
should be for a supported architecture so that you can build a
bootstrap compiler. In the following, let {\tt installed/m3} be the
pathname of the installed driver (not the compiler per se).

\item make a clone of the source tree for the cross-compiler, say in
{\tt cross} and another one for the target compiler, say {\tt port}.
You can go in your {\tt dist-1.5} directory and make the targets
{\tt cross} and {\tt port} to create these clones, that will reside next
to {\tt dist-1.5}.

\item establish a link to the installed version:
\begin{verbatim}
    $ (cd cross/system/driver; ln -s installed/m3 m3.bootstrap)
\end{verbatim}

\item chose a name for the new system, say $target$. Add it to the
{\tt TARGETS} and {\tt CLONES} definitions in {\tt dist-1.5/makefile}.

\item whenever you create a new source file, for example {\tt
dist-1.5/util/config.dist-$target$}, you need to create some links in
{\tt cross} and {\tt port}:
\begin{verse} \tt
    \$ (cd cross/util; ln -s .SRC/config.dist-$target$)\\
    \$ (cd port/util; ln -s .SRC/config.dist-$target$)\\
\end{verse}

\item create the file {\tt dist-1.5/util/config.dist-$target$}, using
similar files as a model. Don't forget the links in {\tt cross} and
{\tt port}. Make some additional links:
\begin{verse} \tt
    \$ (cd cross/util; ln -s config.dist-$target$ config)\\
    \$ (cd port/util; ln -s config.dist-$target$ config)\\
\end{verse}

\item modify the compiler, the runtime and the core library as described below
If you need to introduce a system-dependant part in a source C file,
you can use a conditional of the form:
\begin{verse}\tt
    \#if defined ($system$)\\
    ...\\
    \#endif\\
\end{verse}
In {\tt Imakefile}s, use:
\begin{verse}\tt
    \#if defined ($system$\_ARCHITECTURE)\\
    ...\\
    \#endif\\
\end{verse}

\item configure both hierarchies:
\begin{verse}\tt
    \$ (cd cross; make $target$)\\
    \$ (cd port; make $target$)
\end{verse}

\item add \verb|.ROOT/util| to your path (in each subdirectory of the
system, there is a link named \verb|.ROOT| to the top of the hierarchy)

\item build the cross-compiler, i.e. the compiler that generates code
for the $target$ system and runs on the $host$ system:
\begin{verbatim}
    $ (cd cross/system/compiler; m3all)
\end{verbatim}

\item produce a driver that uses the cross-compiler:
\begin{verbatim}
    $ (cd cross/system/driver; m3all m3.cross)
    $ (cd port/system/driver; \
       ln -s .ROOT/../cross/system/driver/m3.cross m3.bootstrap)
    $ (cd port; ln -s ../cross/system .cross)
\end{verbatim}

\item produce the C files in the port:
\begin{verbatim}
    $ (cd port/system; m3toC)
\end{verbatim}

\item on the $target$ system, finish the construction of the compiler
(it produces code for the $target$ system and runs on the $target$
system):
\begin{verbatim}
    $ (cd port/util; cc -o imake imake.c)
    $ (cd port/system; m3fromC)
\end{verbatim}
This compiler is stored in {\tt system/compiler/m3compiler} and the
associated runtime and core library in {\tt system/runtime/m3run.o}
and {\tt system/corelib/libm3core.a} respectively.

\item you can run the test programs to see if everything works:
\begin{verbatim}
    $ (cd port/tests; m3all test)
\end{verbatim}

\item if all went well, you have a working system for $target$.
Otherwise, you have to determine what's wrong and go back to
constructing the cross-compiler

\item send us ({\tt m3-request@src.dec.com}) your modifications for
the $target$ architecture, so that we can incorporate them in the next
release.

\end{itemize}

\paragraph{Compiler}
Hopefully, all the things that the compiler itself needs to know are
summarized in the {\tt Target} module. In {\tt system/compiler/misc},
create {Target.i3.$target$} and {\tt Target.m3.$target$}, using the
contents of the other versions of these files as a templates.

\paragraph{Runtime routines}
The file {\tt system/runtime/M3machine.h.$target$} (which you need to
create) is included in all the C files that are produced by the
compiler.  You can compare the existing versions to get a flavor of
what goes there. 

\paragraph{Threads}
On {\tt DS3100} systems, thread switching is implemented by standard C
code. This code should work on other architectures as well, provided
that {\tt \_longjmp} does not insist that the new stack pointer should
be lower in the stack than the current stack pointer. 

VAX/Ultrix~3.1 does not allow this liberal use of {\tt
\_longjmp}, so there is a piece of assembly code from which you can
start if your $target$ architecture is also restrictive. 

\paragraph{RandomReal}
The {\tt RandomReal} module (in {\tt system/corelib/random} depends on
the architecture. Create a {\tt
libs/misc/random/RandomReal.m3.$target$}, taking the existing files as
an example.

\paragraph{Loader} 
The loader ({\tt system/loader/m3ld.c}) also depends on the system,
because it has to rebuild C names from their translation by the
C compiler as they appears in object files. For example, the VAX
C compiler adds an underscore in front of C names, while the
DS3100 compiler doesn't. The proper behavior is achieved in {\tt
system/loader/m3ld.c} by conditional compilation.

\paragraph{Ultrix Library}
You are running a version of Unix for which there is no supported
library, you can make one if you want. This is tedious, because is
means putting most of {\tt /usr/include} in \modula syntax. However,
this not needed by the compiler and basic runtime itself. The core
library has an interface {\tt CoreOs} (in {\tt system/corelib/coreos})
that defines just the things that are needed by the system itself.

Good Luck!