compiler/cmm/README

   1 Sketch of the new arrivals:
   2
   3   MkZipCfg       Constructor functions for control-flow graphs.
   4                  Not understandable in its entirety without reference
   5                  to ZipCfg, but nevertheless a worthy starting point,
   6                  as it is a good deal simpler than full ZipCfg.
   7                  MkZipCfg is polymorphic in the types of middle and last
   8                  nodes.
   9
  10   ZipCfg         Describes a zipper-like representation for true basic-block
  11                  control-flow graphs.  A block has a single entry point,
  12                  which is a always a label, followed by zero or mode 'middle
  13                  nodes', each of which represents an uninterruptible
  14                  single-entry, single-exit computation, then finally a 'last
  15                  node', which may have zero or more successors.  A special
  16                  'exit node' is used for splicing together graphs.
  17
  18                  In addition to three representations of flow graphs, the
  19                  module provides a surfeit of functions for observing and
  20                  modifying graphs and related data:
  21                    - Block IDs, sets and environments thereof
  22                    - supply of fresh block IDS (as String -> UniqSM BlockId)
  23                    - myriad functions for splicing graphs
  24                    - postorder_dfs layout of blocks
  25                    - folding, mapping, and translation functions
  26
  27                  ZipCFG is polymorphic in the type of middle and last nodes.
  28
  29   CmmExpr        Code for C-- expressions, which is shared among old and new
  30                  representations of flow graphs.  Of primary interest is the
  31                  type class UserOfLocalRegs and its method foldRegsUsed,
  32                  which is sufficiently overloaded to be used against
  33                  expressions, statements, formals, hinted formals, and so
  34                  on.  This overloading greatly clarifies the computation of
  35                  liveness as well as some other analyses.
  36
  37   ZipCfgCmm      Types to instantiate ZipCfg for C--: middle and last nodes,
  38                  and a bunch of abbreviations of types in ZipCfg and Cmm.
  39                  Also provides suitable constructor functions for building
  40                  graphs from Cmm statements.
  41
  42   CmmLiveZ       A good example of a very simple dataflow analysis.  It
  43                  computes the set of live local registers at each point.
  44
  45   DFMonad        Support for dataflow analysis and dataflow-based
  46                  transformation.   This module needs work.  Includes
  47                    DataflowLattice - for tracking dataflow facts (good)
  48                    DFA - monad for iterative dataflow analysis (OK)
  49                    DFM - monad for iterative dataflow analysis and rewriting (OK)
  50                    DFTx - monad to track Whalley/Davidson transactions (ugly)
  51                    type class DataflowAnalysis - operations common to DFA, DFM
  52                  Some dodgy bits are
  53                    subAnalysis, which may not be right
  54
  55   ZipDataflow    Iteratively solve forward and backward dataflow problems over
  56                  flow graphs.  Polymorphic in the type of graph and in the
  57                  lattice of dataflow facts.   Supports the incremental
  58                  rewriting technique described by Lerner, Grove, and Chambers
  59                  in POPL 2002.  The code is a mess and is still being
  60                  sorted out.
  61
  62
  63   CmmTx          A simple monad for tracking when a transformation has
  64                  occurred (something has changed).
  65
  66   CmmCvt         Converts between Cmm and ZipCfgCmm representations.
  67
  68   CmmProcPointZ  One module that performs three analyses and
  69                  transformations:
  70
  71                     1. Using Michael Adams's iterative algorithm, computes a
  72                        minimal set of proc points that enable code to be
  73                        generated without copying any basic blocks.
  74
  75                     2. Assigns a protocol to each proc point.  The assigner
  76                        is rigged to enable the 'Adams optimization' whereby
  77                        we attempt to eliminate return continuations by
  78                        making procedures return directly to join points.
  79                        Arguably this could be done by a separate rewriting
  80                        pass to perform earlier.
  81
  82                     3. Insert CopyIn and CopyOut nodes where needed
  83                        according to the protocols.
  84
  85   CmmSpillReload Inserts spills and reloads to establish the invariant that
  86                  at a safe call, there are no live variables in registers.
  87
  88   CmmCPSZ        The CPS transformation so far.
  89
  90   CmmContFlowOpt Branch-chain elimination and elimination of unreachable code.
  91
  92   CmmCvt         Conversion to and from the new format.
  93
  94   CmmOpt         Changed optimization to use 'foldRegsUsed'; eliminated
  95                  significant duplication of code.
  96
  97   PprCmmZ        Prettyprinting functions related to ZipCfg and ZipCfgCmm