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">occurence 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>