--- /dev/null
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+ <head>
+ <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
+ <title>The GHC Commentary - You Got Control: The STG-language</title>
+ </head>
+
+ <body BGCOLOR="FFFFFF">
+ <h1>The GHC Commentary - You Got Control: The STG-language</h1>
+ <p>
+ GHC contains two completely independent backends: the byte code
+ generator and the machine code generator. The decision over which of
+ the two is invoked is made in <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/main/HscMain.lhs"><code>HscMain</code></a><code>.hscCodeGen</code>.
+ The machine code generator proceeds itself in a number of phases: First,
+ the <a href="desugar.html">Core</a> intermediate language is translated
+ into <em>STG-language</em>; second, STG-language is transformed into a
+ GHC-internal variant of <a href="http://www.cminusminus.org/">C--</a>;
+ and thirdly, this is either emitted as concrete C--, converted to GNU C,
+ or translated to native code (by the <a href="ncg.html">native code
+ generator</a> which targets IA32, Sparc, and PowerPC [as of March '5]).
+ </p>
+ <p>
+ In the following, we will have a look at the first step of machine code
+ generation, namely the translation steps involving the STG-language.
+ Details about the underlying abstract machine, the <em>Spineless Tagless
+ G-machine</em>, are in <a
+ href="http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34">Implementing
+ lazy functional languages on stock hardware: the Spineless Tagless
+ G-machine</a>, SL Peyton Jones, Journal of Functional Programming 2(2),
+ Apr 1992, pp127-202. (Some details have changed since the publication of
+ this article, but it still gives a good introduction to the main
+ concepts.)
+ </p>
+
+ <h2>The STG Language</h2>
+ <p>
+ The AST of the STG-language and the generation of STG code from Core is
+ both located in the <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/"><code>stgSyn/</code></a>
+ directory; in the modules <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/StgSyn.lhs"><code>StgSyn</code></a>
+ and <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/CoreToStg.lhs"><code>CoreToStg</code></a>,
+ respectively.
+ </p>
+ <p>
+ Conceptually, the STG-language is a lambda calculus (including data
+ constructors and case expressions) whose syntax is restricted to make
+ all control flow explicit. As such, it can be regarded as a variant of
+ <em>administrative normal form (ANF).</em> (C.f., <a
+ href="http://doi.acm.org/10.1145/173262.155113">The essence of compiling
+ with continuations.</a> Cormac Flanagan, Amr Sabry, Bruce F. Duba, and
+ Matthias Felleisen. <em>ACM SIGPLAN Conference on Programming Language
+ Design and Implementation,</em> ACM Press, 1993.) Each syntactic from
+ has a precise operational interpretation, in addition to the
+ denotational interpretation inherited from the lambda calculus. The
+ concrete representation of the STG language inside GHC also includes
+ auxiliary attributes, such as <em>static reference tables (SRTs),</em>
+ which determine the top-level bindings referenced by each let binding
+ and case expression.
+ </p>
+ <p>
+ As usual in ANF, arguments to functions etc. are restricted to atoms
+ (i.e., constants or variables), which implies that all sub-expressions
+ are explicitly named and evaluation order is explicit. Specific to the
+ STG language is that all let bindings correspond to closure allocation
+ (thunks, function closures, and data constructors) and that case
+ expressions encode both computation and case selection. There are two
+ flavours of case expressions scrutinising boxed and unboxed values,
+ respectively. The former perform function calls including demanding the
+ evaluation of thunks, whereas the latter execute primitive operations
+ (such as arithmetic on fixed size integers and floating-point numbers).
+ </p>
+ <p>
+ The representation of STG language defined in <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/StgSyn.lhs"><code>StgSyn</code></a>
+ abstracts over both binders and occurences of variables. The type names
+ involved in this generic definition all carry the prefix
+ <code>Gen</code> (such as in <code>GenStgBinding</code>). Instances of
+ these generic definitions, where both binders and occurences are of type
+ <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/basicTypes/Id.lhs"><code>Id</code></a><code>.Id</code>
+ are defined as type synonyms and use type names that drop the
+ <code>Gen</code> prefix (i.e., becoming plain <code>StgBinding</code>).
+ Complete programs in STG form are represented by values of type
+ <code>[StgBinding]</code>.
+ </p>
+
+ <h2>From Core to STG</h2>
+ <p>
+ Although, the actual translation from Core AST into STG AST is performed
+ by the function <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/CoreToStg.lhs"><code>CoreToStg</code></a><code>.coreToStg</code>
+ (or <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/CoreToStg.lhs"><code>CoreToStg</code></a><code>.coreExprToStg</code>
+ for individual expressions), the translation crucial depends on <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/coreSyn/CorePrep.lhs"><code>CorePrep</code></a><code>.corePrepPgm</code>
+ (resp. <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/coreSyn/CorePrep.lhs"><code>CorePrep</code></a><code>.corePrepExpr</code>),
+ which prepares Core code for code generation (for both byte code and
+ machine code generation). <code>CorePrep</code> saturates primitive and
+ constructor applications, turns the code into A-normal form, renames all
+ identifiers into globally unique names, generates bindings for
+ constructor workers, constructor wrappers, and record selectors plus
+ some further cleanup.
+ </p>
+ <p>
+ In other words, after Core code is prepared for code generation it is
+ structurally already in the form required by the STG language. The main
+ work performed by the actual transformation from Core to STG, as
+ performed by <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/CoreToStg.lhs"><code>CoreToStg</code></a><code>.coreToStg</code>,
+ is to compute the live and free variables as well as live CAFs (constant
+ applicative forms) at each let binding and case alternative. In
+ subsequent phases, the live CAF information is used to compute SRTs.
+ The live variable information is used to determine which stack slots
+ need to be zapped (to avoid space leaks) and the free variable
+ information is need to construct closures. Moreover, hints for
+ optimised code generation are computed, such as whether a closure needs
+ to be updated after is has been evaluated.
+ </p>
+
+ <h2>STG Passes</h2>
+ <p>
+ These days little actual work is performed on programs in STG form; in
+ particular, the code is not further optimised. All serious optimisation
+ (except low-level optimisations which are performed during native code
+ generation) has already been done on Core. The main task of <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/stgSyn/CoreToStg.lhs"><code>CoreToStg</code></a><code>.stg2stg</code>
+ is to compute SRTs from the live CAF information determined during STG
+ generation. Other than that, <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/profiling/SCCfinal.lhs"><code>SCCfinal</code></a><code>.stgMassageForProfiling</code>
+ is executed when compiling for profiling and information may be dumped
+ for debugging purposes.
+ </p>
+
+ <h2>Towards C--</h2>
+ <p>
+ GHC's internal form of C-- is defined in the module <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/cmm/Cmm.hs"><code>Cmm</code></a>.
+ The definition is generic in that it abstracts over the type of static
+ data and of the contents of basic blocks (i.e., over the concrete
+ representation of constant data and instructions). These generic
+ definitions have names carrying the prefix <code>Gen</code> (such as
+ <code>GenCmm</code>). The same module also instantiates the generic
+ form to a concrete form where data is represented by
+ <code>CmmStatic</code> and instructions are represented by
+ <code>CmmStmt</code> (giving us, e.g., <code>Cmm</code> from
+ <code>GenCmm</code>). The concrete form more or less follows the
+ external <a href="http://www.cminusminus.org/">C--</a> language.
+ </p>
+ <p>
+ Programs in STG form are translated to <code>Cmm</code> by <a
+ href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/codeGen/CodeGen.lhs"><code>CodeGen</code></a><code>.codeGen</code>
+ </p>
+
+ <p><hr><small>
+<!-- hhmts start -->
+Last modified: Sat Mar 5 22:55:25 EST 2005
+<!-- hhmts end -->
+ </small>
+ </body>
+</html>
projects / ghc-hetmet.git / commitdiff