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
|
<!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 - The Mighty Simplifier</title>
</head>
<body BGCOLOR="FFFFFF">
<h1>The GHC Commentary - The Mighty Simplifier</h1>
<p>
Most of the optimising program transformations applied by GHC are
performed on an intermediate language called <em>Core,</em> which
essentially is a compiler-friendly formulation of rank-2 polymorphic
lambda terms defined in the module <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/coreSyn/CoreSyn.lhs/"><code>CoreSyn.lhs</code>.</a>
The transformation engine optimising Core programs is called the
<em>Simplifier</em> and composed from a couple of modules located in the
directory <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/"><code>fptools/ghc/compiler/simplCore/</code>.</a>
The main engine of the simplifier is contained in <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/Simplify.lhs"><code>Simplify.lhs</code>.</a>
and its driver is the routine <code>core2core</code> in <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/SimplCore.lhs"><code>SimplCore.lhs</code>.</a>
<p>
The program that the simplifier has produced after applying its various
optimisations can be obtained by passing the option
<code>-ddump-simpl</code> to GHC. Moreover, the various intermediate
stages of the optimisation process is printed when passing
<code>-dverbose-core2core</code>.
<h4><a name="loopBreaker">Recursive Definitions</a></h4>
<p>
The simplification process has to take special care when handling
recursive binding groups; otherwise, the compiler might loop.
Therefore, the routine <code>reOrderRec</code> in <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/OccurAnal.lhs"><code>OccurAnal.lhs</code></a>
computes a set of <em>loop breakers</em> - a set of definitions that
together cut any possible loop in the binding group. It marks the
identifiers bound by these definitions as loop breakers by enriching
their <a href="basicTypes.html#occInfo">occurence information.</a> Loop
breakers will <em>never</em> be inlined by the simplifier; thus,
guaranteeing termination of the simplification procedure. (This is not
entirely accurate -- see <a href="#rules">rewrite rules</a> below.)
The processes finding loop breakers works as follows: First, the
strongly connected components (SCC) of the graph representing all
function dependencies is computed. Then, each SCC is inspected in turn.
If it contains only a single binding (self-recursive function), this is
the loop breaker. In case of multiple recursive bindings, the function
attempts to select bindings where the decision not to inline them does
cause the least harm - in the sense of inhibiting optimisations in the
code. This is achieved by considering each binding in turn and awarding
a <em>score</em> between 0 and 4, where a lower score means that the
function is less useful for inlining - and thus, a better loop breaker.
The evaluation of bingings is performed by the function
<code>score</code> locally defined in <code>OccurAnal</code>.
Note that, because core programs represent function definitions as
<em>one</em> binding choosing between the possibly many equations in the
source program with a <code>case</code> construct, a loop breaker cannot
inline any of its possibly many alternatives (not even the non-recursive
alternatives).
<h4><a name="rules">Rewrite Rules</a></h4>
<p>
The application of rewrite rules is controlled in the module <a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/Simplify.lhs"><code>Simplify.lhs</code></a>
by the function <code>completeCall</code>. This function first checks
whether it should inline the function applied at the currently inspected
call site, then simplifies the arguments, and finally, checks whether
any rewrite rule can be applied (and also whether there is a matching
specialised version of the applied function). The actual check for rule
application is performed by the function <code><a
href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/specialise/Rules.lhs">Rules</a>.lookupRule</code>.
<p>
It should be note that the application of rewrite rules is not subject
to the loop breaker check - i.e., rules of loop breakers will be applied
regardless of whether this may cause the simplifier to diverge.
<p><small>
<!-- hhmts start -->
Last modified: Wed Aug 8 19:25:33 EST 2001
<!-- hhmts end -->
</small>
</body>
</html>
|
