--- /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 - 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>
projects / ghc-hetmet.git / blobdiff