[commit: hoopl] simonmar-alternative-block-rep: An alternative Block representation that gives O(1) access to the (7094b03)

[Simon Marlow]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/hoopl

On branch  : simonmar-alternative-block-rep

http://hackage.haskell.org/trac/ghc/changeset/7094b034d34101a8991d36397b88cc161f3b349c

>---------------------------------------------------------------

commit 7094b034d34101a8991d36397b88cc161f3b349c
Author: Simon Marlow <marlowsd at gmail.com>
Date:   Fri Jun 15 11:58:30 2012 +0100

    An alternative Block representation that gives O(1) access to the
    first and last node, which makes it easier to perform operations on
    these nodes.
    
    With the new representation we can have
    
      blockSplit :: Block n C C -> (n C O, Block n O O, n O C)
      blockSplit (BlockCC f b t) = (f, b, t)
    
      blockJoin :: n C O -> Block n O O -> n O C -> Block n C C
      blockJoin f b t = BlockCC f b t
    
    whereas in the old representation these would be O(n), and would need
    an extra Maybe (because Blocks can't be empty).  This came up because
    GHC needs these kinds of operations - search for uses of
    blockToNodeList in compiler/cmm for some examples.  Many of these are
    just picking apart blocks to get at the first or last nodes.
    
    The simonmar-alternative-block-rep branch makes the representation
    change to the extent required to compile GHC master and do performance
    measurements.  Some functions that GHC does not require are commented
    out.

 src/Compiler/Hoopl.hs           |    2 +-
 src/Compiler/Hoopl/Dataflow.hs  |   20 +++--
 src/Compiler/Hoopl/Graph.hs     |   36 +++++-----
 src/Compiler/Hoopl/GraphUtil.hs |  141 ++++++++++++++++++++++----------------
 src/Compiler/Hoopl/MkGraph.hs   |    4 +-
 src/Compiler/Hoopl/Show.hs      |   11 ++--
 src/Compiler/Hoopl/Util.hs      |   71 ++++++++++----------
 src/Compiler/Hoopl/XUtil.hs     |  118 ++++++++++++++++++--------------
 8 files changed, 222 insertions(+), 181 deletions(-)


Diff suppressed because of size. To see it, use:

    git show 7094b034d34101a8991d36397b88cc161f3b349c