diff options
Diffstat (limited to 'docs/comm/the-beast/simplifier.html')
| -rw-r--r-- | docs/comm/the-beast/simplifier.html | 86 |
1 files changed, 86 insertions, 0 deletions
diff --git a/docs/comm/the-beast/simplifier.html b/docs/comm/the-beast/simplifier.html new file mode 100644 index 0000000000..40cf7cf892 --- /dev/null +++ b/docs/comm/the-beast/simplifier.html @@ -0,0 +1,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> |