Test Trac #9036
[ghc.git] / docs / comm / the-beast / simplifier.html
1 <!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
2 <html>
3 <head>
4 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
5 <title>The GHC Commentary - The Mighty Simplifier</title>
6 </head>
7
8 <body BGCOLOR="FFFFFF">
9 <h1>The GHC Commentary - The Mighty Simplifier</h1>
10 <p>
11 Most of the optimising program transformations applied by GHC are
12 performed on an intermediate language called <em>Core,</em> which
13 essentially is a compiler-friendly formulation of rank-2 polymorphic
14 lambda terms defined in the module <a
15 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/coreSyn/CoreSyn.lhs/"><code>CoreSyn.lhs</code>.</a>
16 The transformation engine optimising Core programs is called the
17 <em>Simplifier</em> and composed from a couple of modules located in the
18 directory <a
19 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/"><code>fptools/ghc/compiler/simplCore/</code>.</a>
20 The main engine of the simplifier is contained in <a
21 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/Simplify.lhs"><code>Simplify.lhs</code>.</a>
22 and its driver is the routine <code>core2core</code> in <a
23 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/SimplCore.lhs"><code>SimplCore.lhs</code>.</a>
24 <p>
25 The program that the simplifier has produced after applying its various
26 optimisations can be obtained by passing the option
27 <code>-ddump-simpl</code> to GHC. Moreover, the various intermediate
28 stages of the optimisation process is printed when passing
29 <code>-dverbose-core2core</code>.
30
31 <h4><a name="loopBreaker">Recursive Definitions</a></h4>
32 <p>
33 The simplification process has to take special care when handling
34 recursive binding groups; otherwise, the compiler might loop.
35 Therefore, the routine <code>reOrderRec</code> in <a
36 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/OccurAnal.lhs"><code>OccurAnal.lhs</code></a>
37 computes a set of <em>loop breakers</em> - a set of definitions that
38 together cut any possible loop in the binding group. It marks the
39 identifiers bound by these definitions as loop breakers by enriching
40 their <a href="basicTypes.html#occInfo">occurrence information.</a> Loop
41 breakers will <em>never</em> be inlined by the simplifier; thus,
42 guaranteeing termination of the simplification procedure. (This is not
43 entirely accurate -- see <a href="#rules">rewrite rules</a> below.)
44
45 The processes finding loop breakers works as follows: First, the
46 strongly connected components (SCC) of the graph representing all
47 function dependencies is computed. Then, each SCC is inspected in turn.
48 If it contains only a single binding (self-recursive function), this is
49 the loop breaker. In case of multiple recursive bindings, the function
50 attempts to select bindings where the decision not to inline them does
51 cause the least harm - in the sense of inhibiting optimisations in the
52 code. This is achieved by considering each binding in turn and awarding
53 a <em>score</em> between 0 and 4, where a lower score means that the
54 function is less useful for inlining - and thus, a better loop breaker.
55 The evaluation of bingings is performed by the function
56 <code>score</code> locally defined in <code>OccurAnal</code>.
57
58 Note that, because core programs represent function definitions as
59 <em>one</em> binding choosing between the possibly many equations in the
60 source program with a <code>case</code> construct, a loop breaker cannot
61 inline any of its possibly many alternatives (not even the non-recursive
62 alternatives).
63
64 <h4><a name="rules">Rewrite Rules</a></h4>
65 <p>
66 The application of rewrite rules is controlled in the module <a
67 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/simplCore/Simplify.lhs"><code>Simplify.lhs</code></a>
68 by the function <code>completeCall</code>. This function first checks
69 whether it should inline the function applied at the currently inspected
70 call site, then simplifies the arguments, and finally, checks whether
71 any rewrite rule can be applied (and also whether there is a matching
72 specialised version of the applied function). The actual check for rule
73 application is performed by the function <code><a
74 href="http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/ghc/compiler/specialise/Rules.lhs">Rules</a>.lookupRule</code>.
75 <p>
76 It should be note that the application of rewrite rules is not subject
77 to the loop breaker check - i.e., rules of loop breakers will be applied
78 regardless of whether this may cause the simplifier to diverge.
79
80 <p><small>
81 <!-- hhmts start -->
82 Last modified: Wed Aug 8 19:25:33 EST 2001
83 <!-- hhmts end -->
84 </small>
85 </body>
86 </html>