+++ /dev/null
-\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.]
projects / ghc-hetmet.git / blobdiff