Changes between Version 1 and Version 2 of CallArity

Mar 7, 2014 2:01:46 PM (2 years ago)



  • CallArity

    v1 v2  
    33This wiki page is about the Call Arity analysis and transformation, which eta-expands definitions if we know that it is always being called with a certain number of arguments. This looks a the ''uses'' of a function, which is different from the the code in  CoreArity, which looks at the ''definition'' of a function.
    5 This pages does '''not''' document Call Arity as implemented; that documentation should be found and maintained with the code, at source:compiler/simplCore/CallArity.hs. But it discusses possible changes to the analysis.
     5This pages does '''not''' document Call Arity as implemented; that documentation should be found and maintained with the code, at source:compiler/simplCore/CallArity.hs.
    7 == Making use of multiple calls ==
    9 Currently, Call Arity only works if there is exactly one incoming call from the body of a let (and possibly one from the body of a recursive function); if there are multiple calls then we do not make use of this information. That is the right thing to do for thunks (we do not want to waste work!), but for functions this would not be an issue... if functions would not possibly call thunks again!
    11 Tricky example 1:
    13 {{{
    14 let d = case .. of ... -> \x . ...
    15                    ... -> \y . ...
    16     go = \x . d
    17 in ... go 1 2 ... go 3 4 ...
    18 }}}
    19 If the second call to `go` were not there, we would eta-expand both `go` and `d`. But there are two calls. We could return this information (“`go` is called multiple times, and each time with at least 2 argument”) and eta-expand `go`. But it would mean that the information coming from `g` (“`d` is called once with one argument) would have to be relaxed to “called many times”, and `d` not eta-exanded.
    21 So far so good; better expand only `go` than nothing at all.
    23 What makes this tricky is that we need information about what calls are exclusive with what other calls, to be able to handle recursion correctly. As a reminder, here the example for why we need that:
    25 {{{
    26 let d = case .. of ... -> \x . ...
    27                    ... -> \y . ...
    28     go = \x . case ... of ... -> go (x+1)
    29                           ... -> d
    30 in case .. of ... -> go 1 2
    31               ... -> d 1
    32 }}}
    34 We want to be able to eta-expand `d`, so we must find out that `d` is called at most once (with one argument). And we do, despite `d` being called from both the body of the let and a local recursive function! We can because the analysis tells us the body calls ''either '' `d` ''or'' `go`. And `go` itself calls ''either'' `d` ''or'' `go`.
    36 This exclusiveness is tricky if we expand the domain to carry more information.
    38 My next attempt: Return a map to `data CallCount = OnceAndOnly Arity | Many Arity` with the semantics that:
    39  * Among all variables that map to `OnceAndOnly`, at most one is called with that arity,
    40  * additional calls to functions mapping to `Many` can be made, which satisfy that arity.
    41 This is a strictly better domain in the sense that the current use of `Just` maps to the `OnceAndOnly`, and what is now `Nothing` simply gets more information.
     7This page used to discuss possible changes to the analysis, but these are implemented now ([cb8a63c]), so I removed the obsolete notes from here.