[project @ 1996-01-08 20:28:12 by partain]

[ghc-hetmet.git] / ghc / compiler / codeGen / cgintro.lit

\section[codegen-intro]{Intro/background info for the code generator}

\tr{NOTES.codeGen} LIVES!!!

\begin{verbatim}
=======================
NEW!  10 Nov 93                 Semi-tagging

Rough idea

        case x of               -- NB just a variable scrutinised
          []     -> ...
          (p:ps) -> ...p...     -- eg.  ps not used

generates

        Node = a ptr to x
        while TRUE do { switch TAG(Node) {

          INDIRECTION_TAG : Node = Node[1]; break;      -- Dereference indirection

          OTHER_TAG : adjust stack; push return address; ENTER(Node)

          0 :   adjust stack; 
                JUMP( Nil_case )

          1 :   adjust stack;
                R2 := Node[2]   -- Get ps
                JUMP( Cons_case )
        }

* The "return address" is a vector table, which contains pointers to
  Nil_case and Cons_case.

* The "adjust stack" in the case of OTHER_TAG is one word different to
  that in the case of a constructor tag (0,1,...), because it needs to
  take account of the return address.  That's why the stack adjust
  shows up in the branches, rather than before the switch.

* In the case of *unvectored* returns, the "return address" will be
  some code which switches on TagReg.  Currently, the branches of the
  case at the return address have the code for the alternatives
  actually there:

        switch TagReg {
          0 : code for nil case
          1 : code for cons case
        }
        
But with semi-tagging, we'll have to label each branch:

        switch TagReg {
          0 : JUMP( Nil_case )
          1 : JUMP( Cons_case )
        }

So there's an extra jump.  Boring.  Boring.  (But things are usually
eval'd...in which case we save a jump.)

* TAG is a macro which gets a "tag" from the info table. The tag
  encodes whether the thing is (a) an indirection, (b) evaluated
  constructor with tag N, or (c) something else. The "something else"
  usually indicates something unevaluated, but it might also include
  FETCH_MEs etc.  Anything which must be entered.

* Maybe we should get the info ptr out of Node, into a temporary
  InfoPtrReg, so that TAG and ENTER share the info-ptr fetch.

* We only load registers which are live in the alternatives.  So at
  the start of an alternative, either the unused fields *will* be in
  regs (if we came via enter/return) or they *won't* (if we came via
  the semi-tagging switch).  If they aren't, GC had better not follow
  them. So we can't arrange that all live ptrs are neatly lined up in
  the first N regs any more.  So GC has to take a liveness
  bit-pattern, not just a "number of live regs" number.

* We need to know which of the constructors fields are live in the
  alternatives.  Hence STG code has to be elaborated to keep live vars
  for each alternative, or to tag each bound-var in the alternatives
  with whether or not it is used.

* The code generator needs to be able to construct unique labels for
  the case alternatives.  (Previously this was done by the AbsC
  flattening pass.) Reason: we now have an explicit join point at the
  start of each alternative.

* There's some question about how tags are mapped.  Is 0 the first
  tag?  (Good when switching on TagReg when there are only two
  constructors.)  What is OTHER_TAG and INDIRECTION_TAG?

* This whole deal can be freely mixed with un-semi-tagged code.
  There should be a compiler flag to control it.

=======================
Many of the details herein are moldy and dubious, but the general
principles are still mostly sound.
\end{verbatim}

%************************************************************************
%*                                                                      *
\subsection{LIST OF OPTIMISATIONS TO DO}
%*                                                                      *
%************************************************************************

\begin{itemize}
\item
Register return conventions.

\item
Optimisations for Enter when 
        \begin{itemize}
        \item
        know code ptr, so don't indirect via Node
        \item
        know how many args
        \item
        top level closures don't load Node
        \end{itemize}
\item
Strings.

\item
Case of unboxed op with more than one alternative, should generate
a switch or an if statement.
\end{itemize}

{\em Medium}

\begin{itemize}
\item
Don't allocate constructors with no args.  
Instead have a single global one.

\item
Have global closures for all characters, and all small numbers.
\end{itemize}


{\em Small}

\begin{itemize}
\item
When a closure is one of its own free variables, don't waste a field
on it.  Instead just use Node.
\end{itemize}


%************************************************************************
%*                                                                      *
\subsection{ENTERING THE GARBAGE COLLECTOR}
%*                                                                      *
%************************************************************************

[WDP: OLD]

There are the following ways to get into the garbage collector:

\begin{verbatim}
_HEAP_OVERFLOW_ReturnViaNode
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Used for the GC trap at closure entry.

        - Node is only live ptr
        - After GC, enter Node

_HEAP_OVERFLOW_ReturnDirect0, _HEAP_OVERFLOW_ReturnDirect1, ... 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Used:   for fast entry of functions, and
        case alternative where values are returned in regs

        - PtrReg1..n are live ptrs
        - ReturnReg points to start of code (before hp oflo check)
        - After GC, jump to ReturnReg
        - TagReg is preserved, in case this is an unvectored return


_HEAP_OVERFLOW_CaseReturnViaNode
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        *** GRIP ONLY ***

Used for case alternatives which return node in heap

        - Node is only live ptr
        - RetVecReg points to return vector
        - After GC, push RetVecReg and enter Node
\end{verbatim}

Exactly equivalent to @GC_ReturnViaNode@, preceded by pushing @ReturnVectorReg@.

The only reason we re-enter Node is so that in a GRIP-ish world, the
closure pointed to be Node is re-loaded into local store if necessary.

%************************************************************************
%*                                                                      *
\subsection{UPDATES}
%*                                                                      *
%************************************************************************

[New stuff 27 Nov 91]

\subsubsection{Return conventions}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

When executing the update continuation code for a constructor, 
@RetVecReg@ points to the {\em beginning of} the return vector.  This is to
enable the update code to find the normal continuation code.
(@RetVecReg@ is set up by the code which jumps to the update continuation
code.)

\subsubsection{Stack arrangement}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Each stack has a ``stack update ptr'', SuA and SuB, which point to the
topmost word of the stack just after an update frame has been pushed.

A standard update frame (on the B stack) looks like this 
(stack grows downward in this picture):

\begin{verbatim}
        |                                       |
        |---------------------------------------|
        | Saved SuA                             |
        |---------------------------------------|
        | Saved SuB                             |
        |---------------------------------------|
        | Pointer to closure to be updated      |
        |---------------------------------------|
        | Pointer to Update return vector       |
        |---------------------------------------|
\end{verbatim}

The SuB therefore points to the Update return vector component of the
topmost update frame.

A {\em constructor} update frame, which is pushed only by closures
which know they will evaluate to a data object, looks just the 
same, but without the saved SuA pointer.

\subsubsection{Pushing update frames}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

An update is pushed right at the start of the code for an updatable
closure.  But {\em after} the stack overflow check.  (The B-stack oflo
check should thereby include allowance for the update frame itself.)

\subsubsection{Return vectors}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Every ``return address'' pushed on the stack by a boxed \tr{case} is a
pointer to a vector of one or more pairs of code pointers:

\begin{verbatim}
        ------> -----------------
                | Cont1         |
                |---------------|
                | Update1       |
                -----------------
                | Cont2         |
                |---------------|
                | Update2       |
                -----------------
                ...etc...
\end{verbatim}

Each pair consists of a {\em continuation} code pointer and an
{\em update} code pointer.

For data types with only one constructor, or too many constructors for
vectoring, the return vector consists of a single pair.

When the \tr{data} decl for each data type is compiled, as well as
making info tables for each constructor, an update code sequence for
each constructor (or a single one, if unvectored) is also created.
        
ToDo: ** record naming convention for these code sequences somewhere **

When the update code is entered, it uses the value stored in the
return registers used by that constructor to update the thing pointed
to by the update frame (all of which except for the return address is
still on the B stack).  If it can do an update in place (ie
constructor takes 3 words or fewer) it does so.

In the unvectored case, this code first has to do a switch on the tag,
UNLESS the return is in the heap, in which case simply overwrite with
an indirection to the thing Node points to.

Tricky point: if the update code can't update in place it has to
allocate a new object, by performing a heap-oflo check and jumping to
the appropriate heap-overflow entry point depending on which RetPtr
registers are live (just as when compiling a case alternative).

When the update code is entered, a register @ReturnReg@ is assumed to
contain the ``return address'' popped from the B stack. This is so
that the update code can enter the normal continuation code when it is
done.

For standard update frames, the A and B stack update ptrs are restored
from the saved versions before returning, too.

\subsubsection{Update return vector}
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Both standard and constructor update frames have as their topmost word
a pointer to a static, fixed, update return vector.

The ``continuation'' entry of each pair in this vector sets UpdReg to
point to the thing to be updated (gotten from the update frame), pops
the update frame, and returns to the ``update'' entry of the
corresponding pair in the next return vector (now exposed on top of B
stk).

The ``update'' entry of each pair in this vector overwrites the thing
to be updated with an indirection to the thing UpdReg points to, and
then returns in the same was as the "continuation" entry above.

There need to be enough pairs in the update return vector to cater for
any constructor at all.


*************************

Things which need to be altered if you change the number of constructors
which switches off vectored returns:
\begin{verbatim}
        Extra cases in update return vector (file xxx)
        The value xxxx in yyyy.lhs
        others?
\end{verbatim}
**************************

%************************************************************************
%*                                                                      *
\subsection{HEAP OBJECTS}
%*                                                                      *
%************************************************************************

The heap consists of {\em closures}.
A closure can be either:
\begin{itemize}
\item
a {\em suspension}, which is an unevaluated thunk.
\item
a {\em constructed object} (or just constructor); created by let(recs) and
by updating.
\item
a {\em partial application} (only updating creates these).
\end{itemize}

Closures are laid out with the {\em info pointer} at the lowest
address (but see notes on the Global Address field for parallel
system).  [We don't try to localise knowledge of this!  It is a royal
pain having to cope with closures laid out backwards.]

Ptr fields occur first (before non-ptr ones).

Non-normal-form closures are always at least 3 words in size (excl
global address), so they can be updated with a list cell (should they
evaluate to that).

Normal form (constructor) closures are always at least 2 words in size
(excl global address), so they have room enough for forwarding ptrs
during GC, and FETCHME boxes after flushing.

1-word closures for normal-form closures in static space.  Explain
more.

Ideally, the info pointer of a closure would point to...
\begin{verbatim}
              |-------------|
              | info table  |
              |-------------|
info ptr ---> code
\end{verbatim}

But when C is the target code we can't guarantee the relative
positions of code and data.  So the info ptr points to
\begin{verbatim}
              |-------------|
info ptr ---->|    ------------------------> code
              |-------------|
              | info table  |
              |-------------|
\end{verbatim}

That is, there's an extra indirection involved; and the info table
occurs AFTER the info pointer rather than before. The info table
entries are ``reversed'' too, so that bigger negative offsets in the
``usual'' case turn into bigger positive offsets.
              
SUSPENSIONS

The simplest form of suspension is
\begin{verbatim}
        info-ptr, ptr free vars, non-ptr free vars
\end{verbatim}

where the info table for info-ptr gives 
\begin{itemize}
\item
the total number of words of free vars
\item
the number of words of ptr free vars (== number of ptr free vars)
in its extra-info part.
\end{itemize}

Optimised versions omit the size info from the info table, and instead
use specialised GC routines.


%************************************************************************
%*                                                                      *
\subsection{NAMING CONVENTIONS for compiled code}
%*                                                                      *
%************************************************************************


Given a top-level closure called f defined in module M, 

\begin{verbatim}
        _M_f_closure            labels the closure itself
                                (only for top-level (ie static) closures)

        _M_f_entry              labels the slow entry point of the code
        _M_f_fast               labels the fast entry point of the code

        _M_f_info               labels the info pointer for the closure for f
                                (NB the info ptr of a closure isn't public 
                                in the sense that these labels
                                are.  It is private to a module, and 
                                its name can be a secret.)
\end{verbatim}

These names are the REAL names that the linker sees. The initial underscores
are attached by the C compiler.

A non-top-level closure has the same names, but as well as the \tr{f}
the labels have the unique number, so that different local closures
which share a name don't get confused.  The reason we need a naming
convention at all is that with a little optimisation a tail call may
jump direct to the fast entry of a locally-defined closure.

\tr{f} may be a constructor, in the case of closures which are the curried
versions of the constructor.

For constructor closures, we have the following naming conventions, where
the constructor is C defined in module M:

\begin{verbatim}
        _M_C_con_info           is the info ptr for the constructor
        _M_C_con_entry          is the corresponding code entry point
\end{verbatim}

%************************************************************************
%*                                                                      *
\subsection{ENTRY CONVENTIONS}
%*                                                                      *
%************************************************************************

\begin{description}
\item[Constructor objects:]
        On entry to the code for a constructor (\tr{_M_C_con_entry}), Node
        points to the constructor object.  [Even if the constructor has arity
        zero...]

\item[Non-top-level suspensions (both fast and slow entries):]
        Node points to the closure.

\item[Top-level suspensions, slow entry:]
        ReturnReg points to the slow entry point itself

\item[..ditto, fast entry:]
        No entry convention
\end{description}


%************************************************************************
%*                                                                      *
\subsection{CONSTRUCTOR RETURN CONVENTIONS}
%*                                                                      *
%************************************************************************

There is lots of excitement concerning the way in which constructors
are returned to case expressions.

{\em Simplest version}
%=====================

The return address on the stack points directly to some code.  It
expects:

\begin{verbatim}
Boxed objects:
        PtrReg1 points to the constructed value (in the heap) (unless arity=0)
        Tag     contains its tag (unless # of constructors = 1)

Unboxed Ints:   IntReg          contains the int
        Float:  FloatReg        contains the returned value
\end{verbatim}

{\em Small improvement: vectoring}
%=================================

If there are fewer than (say) 8 constructors in the type, the return
address points to a vector of return addresses.  The constructor does
a vectored return.  No CSwitch.

Complication: updates.  Update frames are built before the type of the
thing which will be returned is known.  Hence their return address
UPDATE has to be able to handle anything (vectored and nonvectored).

Hence the vector table goes BACKWARD from ONE WORD BEFORE the word
pointed to by the return address.

{\em Big improvement: contents in registers}
%===========================================

Constructor with few enough components (eg 8ish) return their
arguments in registers.  [If there is only one constructor in the
type, the tag register can be pressed into service for this purpose.]

Complication: updates.  Update frames are built before the type of the
thing which will be returned is known.  Hence their return address
UPDATE has to be able to handle anything.

So, a return address is a pointer to a PAIR of return addresses (or
maybe a pointer to some code immediately preceded by a pointer to some
code).

The ``main'' return address is just as before.

The ``update'' return address expects just the same regs to be in use
as the ``main'' address, BUT AS WELL the magic loc UpdPtr points to a
closure to be updated.  It carries out the update, and contines with
the main return address.

The ``main'' code for UPDATE just loads UpdPtr the thing to be
updated, and returns to the "update" entry of the next thing on the
stack.

The ``update'' entry for UPDATE just overwrites the thing to be
updated with an indirection to UpdPtr.

These two improvements can be combined orthogonally.


%************************************************************************
%*                                                                      *
\subsection{REGISTERS}
%*                                                                      *
%************************************************************************

Separate registers for
\begin{verbatim}
        C stack (incl interrupt handling, if this is not done on
                another stk) (if interrupts don't mangle the C stack,
                we could save it for most of the time and reuse the
                register)

        Arg stack
        Basic value and control stack
                These two grow towards each other, so they are each
                other's limits!

        Heap pointer
\end{verbatim}

And probably also
\begin{verbatim}
        Heap limit
\end{verbatim}


%************************************************************************
%*                                                                      *
\subsection{THE OFFSET SWAMP}
%*                                                                      *
%************************************************************************

There are THREE kinds of offset:
\begin{description}
\item[virtual offsets:]

    start at 1 at base of frame, and increase towards top of stack.

    don't change when you adjust sp/hp.

    independent of stack direction.

    only exist inside the code generator, pre Abstract C

    for multi-word objects, the offset identifies the word of the
    object with smallest offset

\item[reg-relative offsets:]

    start at 0 for elt to which sp points, and increase ``into the
    interesting stuff.''

    Specifically, towards 
    \begin{itemize}
    \item
    bottom of stack (for SpA, SpB)
    \item
    beginning of heap (for Hp)
    \item
    end of closure (for Node)
    \end{itemize}

    offset for a particular item changes when you adjust sp.

    independent of stack direction.

    exist in abstract C CVal and CAddr addressing modes

    for multi-word objects, the offset identifies the word of the
    object with smallest offset

\item[real offsets:]

    either the negation or identity of sp-relative offset.

    start at 0 for elt to which sp points, and either increase or
    decrease towards bottom of stk, depending on stk direction

    exist in real C, usually as a macro call passing an sp-rel offset

    for multi-word objects, the offset identifies the word of the
    object with lowest address
\end{description}

%************************************************************************
%*                                                                      *
\subsection{STACKS}
%*                                                                      *
%************************************************************************

There are two stacks, as in the STG paper.
\begin{description}
\item[A stack:]
contains only closure pointers.  Its stack ptr is SpA.

\item[B stack:]
contains basic values, return addresses, update frames.
Its stack ptr is SpB.
\end{description}

SpA and SpB point to the topmost allocated word of stack (though they
may not be up to date in the middle of a basic block).
                
\subsubsection{STACK ALLOCATION}

A stack and B stack grow towards each other, so they overflow when
they collide.

The A stack grows downward; the B stack grows upward.  [We'll try to
localise stuff which uses this info.]

We can check for stack {\em overflow} not just at the start of a basic
block, but at the start of an entire expression evaluation.  The
high-water marks of case-expression alternatives can be max'd.

Within the code for a closure, the ``stack frame'' is deemed to start
with the last argument taken by the closure (ie the one deepest in the
stack).  Stack slots are can then be identified by ``virtual offsets''
from the base of the frame; the bottom-most word of the frame has
offset 1.

For multi-word slots (B stack only) the offset identifies the word
with the smallest virtual offset. [If B grows upward, this is the word
with the lowest physical address too.]

Since there are two stacks, a ``stack frame'' really consists of two
stack frames, one on each stack.

For each stack, we keep track of the following:
        
\begin{verbatim}
* virtSp        virtual stack ptr       offset of topmost occupied stack slot
                                        (initialised to 0 if no args)

* realSp        real stack ptr          offset of real stack ptr reg    
                                        (initialised to 0 if no args)

* tailSp        tail-call ptr           offset of topmost slot to be retained
                                        at next tail call, excluding the 
                                        argument to the tail call itself

* hwSp          high-water mark         largest value taken by virtSp
                                        in this closure body
\end{verbatim}

The real stack pointer is (for now) only adjusted at the tail call itself,
at which point it is made to point to the topmost occupied word of the stack.

We can't always adjust it at the beginning, because we don't
necessarily know which tail call will be made (a conditional might
intervene).  So stuff is actually put on the stack ``above'' the stack
pointer.  This is ok because interrupts are serviced on a different
stack.

The code generator works entirely in terms of stack {\em virtual
offsets}.  The conversion to real addressing modes is done solely when
we look up a binding.  When we move a stack pointer, the offsets of
variables currently bound to stack offsets in the environment will
change.  We provide operations in the @cgBindings@ type to perform
this offset-change (to wit, @shiftStkOffsets@), leaving open whether
it is done pronto, or kept separate and applied to lookups.

Stack overflow checking takes place at the start of a closure body, using
the high-water mark information gotten from the closure body.


%************************************************************************
%*                                                                      *
\subsection{HEAP ALLOCATION}
%*                                                                      *
%************************************************************************

Heap ptr reg (Hp) points to the last word of allocated space (and not
to the first word of free space).

The heap limit register (HpLim) points to the last word of available
space.

A basic block allocates a chunk of heap called a ``heap frame''.
The word of the frame nearest to the previously-allocated stuff
has virtual offset 1, and offsets increase from 1 to the size of the 
frame in words.  

Closures are allocated with their code pointers having the lowest virtual
offset.  

NOTE: this means that closures are only laid out with code ptr at
lowest PHYSICAL address if the heap grows upwards.

Heap ptr reg is moved at the beginning of a basic block to account for
the allocation of the whole frame.  At this time a heap exhaustion
check is made (has the heap ptr gone past the heap limit?).  In the
basic block, indexed accesses off the heap ptr fill in this newly
allocated block.  [Bias to RISC here: no cheap auto-inc mode, and free
indexing.]

We maintain the following information during code generation:

\begin{verbatim}
* virtHp        virtual heap ptr        offset of last word
                                        of the frame allocated so far
                                        Starts at 0 and increases.
* realHp        virtual offset of
                the real Hp register
\end{verbatim}

Since virtHp only ever increases, it doubles as the heap high water mark.

\subsubsection{BINDINGS}

The code generator maintains info for each name about where it is.
Each variable maps to:

\begin{verbatim}
        - its kind

        - its volatile location:- a temporary variable
                                - a virtual heap offset n, meaning the 
                                        ADDRESS OF a word in the current
                                        heap frame
                                - absent

        - its stable location:  - a virtual stack offset n, meaning the
                                        CONTENTS OF an object in the
                                        current stack frame
                                - absent
\end{verbatim}

\subsubsection{ENTERING AN OBJECT}

When a closure is entered at the normal entry point, the magic locs
\begin{verbatim}
        Node            points to the closure (unless it is a top-level closure)
        ReturnReg       points to the code being jumped to
\end{verbatim}
At the fast entry point, Node is still set up, but ReturnReg may not be.
[Not sure about this.]