\item The thread is preempted.
\end{itemize}
-A world-switch (i.e. when compiled code encounters interpreted code,
-and vice-versa) can happen in six ways:
-
-\begin{itemize}
-\item A GHC thread enters a Hugs-built thunk.
-\item A GHC thread calls a Hugs-compiled function.
-\item A GHC thread returns to a Hugs-compiled return address.
-\item A Hugs thread enters a GHC-built thunk.
-\item A Hugs thread calls a GHC-compiled function.
-\item A Hugs thread returns to a Hugs-compiled return address.
-\end{itemize}
-
A running system has a global state, consisting of
\begin{itemize}
heap.
\item The Thread Preemption Flag, which is set whenever the currently
running thread should be preempted at the next opportunity.
+\item A list of runnable threads.
+\item A list of blocked threads.
\end{itemize}
-Each thread has a thread-local state, which consists of
-
-\begin{itemize}
-\item @TSO@, the Thread State Object for this thread. This is a heap
-object that is used to store the current thread state when the thread
-is blocked or sleeping.
-\item @Sp@, the current stack pointer.
-\item @Su@, the current stack update frame pointer. This register
-points to the most recent update frame on the stack, and is used to
-calculate the number of arguments available when entering a function.
-\item @SpLim@, the stack limit pointer. This points to the end of the
-current stack chunk.
-\item Several general purpose registers, used for passing arguments to
-functions.
-\end{itemize}
-
-\noindent and various other bits of information used in specialised
-circumstances, such as profiling and parallel execution. These are
-described in the appropriate sections.
+Each thread is represented by a Thread State Object (TSO), which is
+described in detail in Section \ref{sect:TSO}.
The following is pseudo-code for the inner loop of the scheduler
itself.
How do we invoke GC, ccalls, etc.
General ccall (@ccall-GC@) and optimised ccall.
-\section{Evaluation}
+\section{Compiled Execution}
+
+This section describes the framework in which compiled code evaluates
+expressions. Only at certain points will compiled code need to be
+able to talk to the interpreted world; these are discussed in Section
+\ref{sec:hugs-ghc-interaction}.
\subsection{Calling conventions}
@
case x of (a,b) -> E
@
-In a stack-based evaluator such as the STG machine,
-a @case@ expression is evaluated by pushing a {\em return address} on the stack
-before evaluating the scrutinee (@x@ in this case). Once evaluation of the
-scrutinee is complete, execution resumes at the return address, which
-points to the code for the expression @E@.
+
+The code for a @case@ expression looks like this:
+
+\begin{itemize}
+\item Push the free variables of the branches on the stack (fv(@E@) in
+this case).
+\item Push a \emph{return address} on the stack.
+\item Evaluate the scrutinee (@x@ in this case).
+\end{itemize}
+
+Once evaluation of the scrutinee is complete, execution resumes at the
+return address, which points to the code for the expression @E@.
When execution resumes at the return point, there must be some {\em
return convention} that defines where the components of the pair, @a@
heap.
When passing an unboxed tuple to a function, the components are
-flattened out and passed on the stack/in registers as usual.
+flattened out and passed in \Arg{1} \ldots \Arg{n} as usual.
\end{itemize}
@
data Maybe a = Nothing | Just a
@
-How does the return convention encode which of the two constructors is being returned?
-A @case@ expression scrutinising a value of @Maybe@ type would look like this:
+How does the return convention encode which of the two constructors is
+being returned? A @case@ expression scrutinising a value of @Maybe@
+type would look like this:
@
case E of
Nothing -> ...
The code at the return address will test the tag and jump to the
appropriate code for the case branch.
-\ToDo{Decide whether it's better to load the tag into \Arg{2} or not.
-May be affected by whether \Arg{2} is a real register.}
-
The choice of whether to use a vectored return or a direct return is
made on a type-by-type basis --- up to a certain maximum number of
constructors imposed by the update mechanism
(section~\ref{sect:data-updates}).
+Single-constructor data types also use direct returns, although in
+that case there is no need to return a tag in \Arg{2}.
+
\ToDo{Say whether we pop the return address before returning}
+\ToDo{Stack stubbing?}
+
\subsection{Updates}
\label{sect:data-updates}
\item The update frame is still on the stack.
\end{itemize}
+We can safely share a single statically-compiled update function
+between all types. However, the code must be able to handle both
+vectored and direct-return datatypes. This is done by arranging that
+the update code looks like this:
+
+@
+ | ^ |
+ | return vector |
+ |---------------|
+ | fixed-size |
+ | info table |
+ |---------------| <- update code pointer
+ | update code |
+ | v |
+@
+
+Each entry in the return vector (which is large enough to cover the
+largest vectored-return type) points to the update code.
+
The update code:
\begin{itemize}
\item overwrites the {\em updatee} with an indirection to \Arg{1};
\item enters \Arg{1}.
\end{itemize}
-This update code is the same for all data types, and can therefore be
-compiled statically in the runtime system.
-
-Since Haskell is polymorphic, we sometimes have to compile code for
-updatable thunks without knowing the type that will be returned. In
-this case, the update frame must work for both direct and vectored
-returns. This requires that we generate an infotable containing both
-a valid direct return address (which will perform the update and then
-perform a direct return) and a valid return vector (each entry of
-which will perform the update and then perform a vectored return).
-
+We enter \Arg{1} again, having probably just come from there, because
+it knows whether to perform a direct or vectored return. This could
+be optimised by compiling special update code for each slot in the
+return vector, which performs the correct return.
\subsection{Semi-tagging}
\label{sect:semi-tagging}
May have to revert black holes - ouch!
@
+\section{Interpreted Execution}
+
+\subsection{Hugs Heap Objects}
+\label{sect:hugs-heap-objects}
+
+Compiled byte code lives on the global heap, in objects called
+Byte-Code Objects (or BCOs). The layout of BCOs is described in
+detail in Section \ref{sect:BCO}, in this section we will describe
+their semantics.
+
+Since byte-code lives on the heap, it can be garbage collected just
+like any other heap-resident data. Hugs maintains a table of
+currently live BCOs, which is treated as a table of live pointers by
+the garbage collector. When a module is unloaded, the pointers to its
+BCOs are removed from the table, and the code will be garbage
+collected some time later.
+
+A BCO represents a basic block of code - all entry points are at the
+beginning of a BCO, and it is impossible to jump into the middle of
+one. A BCO represents not only the code for a function, but also its
+closure; a BCO can be entered just like any other closure. The
+calling convention for any BCO is:
+
+\begin{itemize}
+\item Push any arguments on the stack.
+\item If the code has free variables, push their values on the stack
+(in a pre-defined order, pointers first).
+\item Begin interpreting the byte code.
+\end{itemize}
+
+If the code has free variables, it cannot be entered directly. The
+values for the free variables come from a thunk, which is represented
+by an AP object (Section \ref{sect:AP}). The AP object contains a
+pointer to a BCO and a number of values. When entered, it pushes the
+values on the stack and enters the BCO.
+
+The AP object can be used for both thunks and partial applications,
+since the calling convention is the same in each case. The AP object
+has a counterpart which is used for Hugs return addresses, as we shall
+see in Section \ref{ghc-to-hugs-return}.
+
+\section{Switching Worlds}
+
+\label{sect:switching-worlds}
+
+Because this is a combined compiled/interpreted system, the
+interpreter will sometimes encounter compiled code, and vice-versa.
+
+All world-switches go via the scheduler, ensuring that the world is in
+a known state ready to enter either compiled code or the interpreter.
+When a thread is run from the scheduler, the @whatNext@ field in the
+TSO (Section \ref{sect:TSO}) is checked to find out how to execute the
+thread.
+
+\begin{itemize}
+\item If @whatNext@ is set to @ReturnGHC@, we load up the required
+registers from the TSO and jump to the address at the top of the user
+stack.
+\item If @whatNext@ is set to @EnterGHC@, we load up the required
+registers from the TSO and enter the closure pointed to by the top
+word of the stack.
+\item If @whatNext@ is set to @EnterHugs@, we enter the top thing on
+the stack, using the interpreter.
+\end{itemize}
+
+There are four cases we need to consider:
+
+\begin{enumerate}
+\item A GHC thread enters a Hugs-built closure.
+\item A GHC thread returns to a Hugs-compiled return address.
+\item A Hugs thread enters a GHC-built closure.
+\item A Hugs thread returns to a Hugs-compiled return address.
+\end{enumerate}
+
+GHC-compiled modules cannot call functions in a Hugs-compiled module
+directly, because the compiler has no information about arities in the
+external module. Therefore it must assume any top-level objects are
+CAFs, and enter their closures.
+
+\ToDo{dynamic linking stuff}
+\ToDo{Hugs-built constructors?}
+
+We now examine the various cases one by one and describe how the
+switch happens in each situation.
+
+\subsection{A GHC thread enters a Hugs-built closure}
+\label{sect:ghc-to-hugs-closure}
+
+There are two possibilities: GHC has entered the BCO directly (for a
+top-level function closure), or it has entered an AP.
+
+The code for both objects is the same:
+
+\begin{itemize}
+\item Push the address of the BCO on the stack.
+\item Save the current state of the thread in its TSO.
+\item Return to the scheduler, setting @whatNext@ to @EnterHugs@.
+\end{itemize}
+
+\subsection{A GHC thread returns to a Hugs-compiled return address}
+\label{ghc-to-hugs-return}
+
+When Hugs pushes return addresses on the stack, they look like this:
+
+@
+ | |
+ |_______________|
+ | | -----> bytecode object
+ |_______________|
+ | | _____
+ |_______________| |
+ | _____
+ | | | Info Table
+ | | |
+ |_____\ |____| hugs_return
+ / . .
+ . . Code
+ . .
+@
+
+If GHC is returning, it will return to the address at the top of the
+stack. This address is a pointer to a statically compiled code
+fragment called @hugs_return@, which:
+
+\begin{itemize}
+\item pushes \Arg{1} (the return value) on the stack.
+\item saves the thread state in the TSO
+\item returns to the scheduler with @whatNext@ set to @EnterHugs@.
+\end{itemize}
+
+\noindent When Hugs runs, it will enter the return value, which will
+return using the correct Hugs convention to the return address
+underneath it on the stack.
+
+\subsection{A Hugs thread enters a GHC-compiled closure}
+\label{sect:hugs-to-ghc-closure}
+
+Hugs can recognise a GHC-built closure as not being one of the
+following types of object:
+
+\begin{itemize}
+\item A BCO.
+\item An AP.
+\item A constructor.
+\end{itemize}
+
+When Hugs is called on to enter a GHC closure, it executes the
+following sequence of instructions:
+
+\begin{itemize}
+\item Push the address of the closure on the stack.
+\item Save the current state of the thread in the TSO.
+\item Return to the scheduler, with the @whatNext@ field set to
+@EnterGHC@.
+\end{itemize}
+
+\subsection{A Hugs thread returns to a GHC-compiled return address}
+\label{sect:hugs-to-ghc-return}
+
+When Hugs is about to return, the stack looks like this:
+
+@
+ | |
+ |_______________|
+ | | -----> return address
+ |_______________|
+ | | -----> object being returned
+ |_______________|
+
+@
+
+The return address is recognisable as a GHC-return address by virtue
+of not being @hugs_return@. Hugs recognises that it needs to do a
+world-switch and performs the following sequence:
+
+\begin{itemize}
+\item save the state of the thread in the TSO.
+\item return to the scheduler, setting @whatNext@ to @EnterGHC@.
+\end{itemize}
+
+The first thing that GHC will do is enter the object on the top of the
+stack, which is a pointer to the value being returned. This value
+will then return itself to the return address using the GHC return
+convention.
\section{Heap objects}
\label{sect:fixed-header}
+\subsection{Hugs Objects}
+
+\subsubsection{Byte-Code Objects}
+\label{sect:BCO}
+
+A Byte-Code Object (BCO) is a container for a a chunk of byte-code,
+which can be executed by Hugs. For a top-level function, the BCO also
+serves as the closure for the function.
+
+The semantics of BCOs are described in Section
+\ref{hugs-heap-objects}. A BCO has the following structure:
+
+\begin{center}
+\begin{tabular}{|l|l|l|l|l|l|}
+\hline
+\emph{BCO} & \emph{Layout} & \emph{Offset} & \emph{Size} &
+\emph{Literals} & \emph{Byte code} \\
+\hline
+\end{tabular}
+\end{center}
+
+\noindent where:
+\begin{itemize}
+\item \emph{BCO} is a pointer to a static code fragment/info table that
+returns to the scheduler to invoke Hugs (Section
+\ref{ghc-to-hugs-closure}).
+\item \emph{Layout} contains the number of pointer literals in the
+\emph{Literals} field.
+\item \emph{Offset} is the offset to the byte code from the start of
+the object.
+\item \emph{Size} is the number of words of byte code in the object.
+\item \emph{Literals} contains any pointer and non-pointer literals used in
+the byte-codes (including jump addresses), pointers first.
+\item \emph{Byte code} contains \emph{Size} words of non-pointer byte
+code.
+\end{itemize}
+
+\subsubsection{AP objects}
+\label{sect:AP}
+
+Hugs uses a standard object for thunks, partial applications and
+return addresses. Thunks and partial applications live on the heap,
+whereas return addresses live on the stack.
+
+The layout of an AP is
+
+\begin{center}
+\begin{tabular}{|l|l|l|l|}
+\hline
+\emph{AP} & \emph{BCO} & \emph{Layout} & \emph{Free Variables} \\
+\hline
+\end{tabular}
+\end{center}
+
+\noindent where:
+
+\begin{itemize}
+\item \emph{AP} is a pointer to a statically-compiled code
+fragment/info table that returns to the scheduler to invoke Hugs
+(Sections \ref{ghc-to-hugs-closure}, \ref{ghc-to-hugs-return}).
+\item \emph{BCO} is a pointer to the BCO for the thunk.
+\item \emph{Layout} contains the number of pointers and the size of
+the \emph{Free Variables} field.
+\item \emph{Free Variables} contains the free variables of the
+thunk/partial application/return address, pointers first.
+\end{itemize}
+
\subsection{Pointed Objects}
All pointed objects can be entered.
projects / ghc-hetmet.git / blobdiff