Add a simple arity analyser
authorsimonpj@microsoft.com <unknown>
Tue, 21 Dec 2010 16:58:00 +0000 (16:58 +0000)
committersimonpj@microsoft.com <unknown>
Tue, 21 Dec 2010 16:58:00 +0000 (16:58 +0000)
commit1d7a3cf332532b1f9d798b44e76c4be6f0c74dcf
tree1ec1c4bbde46fc0217bb1cf2214fa58597d9be6c
parent62af0377c41ffcc76ae308e07e328106846f050c
Add a simple arity analyser

I've wanted to do this for ages, but never gotten around to
it.  The main notes are in Note [Arity analysis] in SimplUtils.

The motivating example for arity analysis is this:

  f = \x. let g = f (x+1)
          in \y. ...g...

What arity does f have?  Really it should have arity 2, but a naive
look at the RHS won't see that.  You need a fixpoint analysis which
says it has arity "infinity" the first time round.

This makes things more robust to the way in which you write code.  For
example, see Trac #4474 which is fixed by this change.

Not a huge difference, but worth while:

        Program           Size    Allocs   Runtime   Elapsed
--------------------------------------------------------------------------------
            Min          -0.4%     -2.2%    -10.0%    -10.0%
            Max          +2.7%     +0.3%     +7.1%     +6.9%
 Geometric Mean          -0.3%     -0.2%     -2.1%     -2.2%

I don't really believe the runtime numbers, because the machine was
busy, but the bottom line is that not much changes, and what does
change reliably (allocation and size) is in the right direction.
compiler/coreSyn/CoreArity.lhs
compiler/coreSyn/CoreUtils.lhs
compiler/simplCore/SimplUtils.lhs