1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
<!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>
|
