+++ /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 / blobdiff