+ 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 HscMain.hscCodeGen.
+ The machine code generator proceeds itself in a number of phases: First,
+ the Core intermediate language is translated
+ into STG-language; second, STG-language is transformed into a
+ GHC-internal variant of C--;
+ and thirdly, this is either emitted as concrete C--, converted to GNU C,
+ or translated to native code (by the native code
+ generator which targets IA32, Sparc, and PowerPC [as of March '5]).
+
+ 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 Spineless Tagless + G-machine, are in Implementing + lazy functional languages on stock hardware: the Spineless Tagless + G-machine, 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.) +
+ +
+ The AST of the STG-language and the generation of STG code from Core is
+ both located in the stgSyn/
+ directory; in the modules StgSyn
+ and CoreToStg,
+ respectively.
+
+ 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 + administrative normal form (ANF). (C.f., The essence of compiling + with continuations. Cormac Flanagan, Amr Sabry, Bruce F. Duba, and + Matthias Felleisen. ACM SIGPLAN Conference on Programming Language + Design and Implementation, 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 static reference tables (SRTs), + which determine the top-level bindings referenced by each let binding + and case expression. +
++ 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). +
+
+ The representation of STG language defined in StgSyn
+ abstracts over both binders and occurences of variables. The type names
+ involved in this generic definition all carry the prefix
+ Gen (such as in GenStgBinding). Instances of
+ these generic definitions, where both binders and occurences are of type
+ Id.Id
+ are defined as type synonyms and use type names that drop the
+ Gen prefix (i.e., becoming plain StgBinding).
+ Complete programs in STG form are represented by values of type
+ [StgBinding].
+
+ Although, the actual translation from Core AST into STG AST is performed
+ by the function CoreToStg.coreToStg
+ (or CoreToStg.coreExprToStg
+ for individual expressions), the translation crucial depends on CorePrep.corePrepPgm
+ (resp. CorePrep.corePrepExpr),
+ which prepares Core code for code generation (for both byte code and
+ machine code generation). CorePrep 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.
+
+ 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 CoreToStg.coreToStg,
+ 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.
+
+ 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 CoreToStg.stg2stg
+ is to compute SRTs from the live CAF information determined during STG
+ generation. Other than that, SCCfinal.stgMassageForProfiling
+ is executed when compiling for profiling and information may be dumped
+ for debugging purposes.
+
+ GHC's internal form of C-- is defined in the module Cmm.
+ 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 Gen (such as
+ GenCmm). The same module also instantiates the generic
+ form to a concrete form where data is represented by
+ CmmStatic and instructions are represented by
+ CmmStmt (giving us, e.g., Cmm from
+ GenCmm). The concrete form more or less follows the
+ external C-- language.
+
+ Programs in STG form are translated to Cmm by CodeGen.codeGen
+