1. 06 Nov, 2015 1 commit
    • Joachim Breitner's avatar
      Call Arity: In "e x", the result of "x" is not shared · a58eeb7f
      Joachim Breitner authored
      in contrast to "e (f x)", where CorePrep will turn it into "let y = f x
      in e x". So in
        let f = ...
        in e (f x)
      we know that f is called at most once, but in
        let f = ...
        in e f
      we do not know that.
      
      Previously Call Arity would assume that in "e x", "x" is evaluated at
      most once. This rarely would make a difference (the argument "x" is
      analized with an incoming arity of 0, so no eta-expansion would be done
      anyways), but of course this should still be fixed.
      
      This fixes #11064.
      
      Note the corresponding code dmdTransformThunkDmd in DmdAnal.
      a58eeb7f
  2. 16 Apr, 2015 1 commit
    • Joachim Breitner's avatar
      Call Arity: Trade precision for performance in large mutually recursive groups · 9654a7cf
      Joachim Breitner authored
      Sometimes (especial with derived Data instances, it seems), one can have
      very large mutually recursive bindings. Calculating the Call Arity
      analysis result with full precision is an expensive operation in these
      case. So above a certain threshold (25, for no good reason besides
      intuition), skip this calculation and assume the recursion is not
      linear, which is a conservative result.
      
      With this, the Call Arity analysis accounts for 3.7% of the compile time
      of haskell-src-exts. Fixes #10293
      
      Differential Revision: https://phabricator.haskell.org/D843
      9654a7cf
  3. 15 Apr, 2015 1 commit
    • Joachim Breitner's avatar
      Improve Call Arity performance · a9ca67f6
      Joachim Breitner authored
      This improves how the Call Arity deals with "boring" variables. Boring
      variables are those where it does not bother to include in the analysis
      result, so whenever something is looked up in the analysis result, we
      have to make a conservative assumption about them.
      
      Previously, we extended the result with such conservative information
      about them, to keep the code uniform, but that could blow up the amount
      of data passed around, even if only temporarily, and slowed things down.
      
      We now pass around an explicit list (well, set) of variable that are
      boring and take that into account whenever we use the result. Not as
      pretty, but noticably faster.
      a9ca67f6
  4. 23 Mar, 2015 1 commit
  5. 22 Mar, 2015 1 commit
  6. 23 Feb, 2015 1 commit
  7. 21 Feb, 2015 1 commit
  8. 31 Oct, 2014 1 commit
  9. 01 Oct, 2014 1 commit
  10. 14 Mar, 2014 2 commits
  11. 12 Mar, 2014 1 commit
  12. 05 Mar, 2014 1 commit
    • Joachim Breitner's avatar
      Major Call Arity rework · cb8a63cb
      Joachim Breitner authored
      This patch improves the call arity analysis in various ways.
      
      Most importantly, it enriches the analysis result information so that
      when looking at a call, we do not have to make a random choice about
      what side we want to take the information from. Instead we can combine
      the results in a way that does not lose valuable information.
      
      To do so, besides the incoming arities, we store remember "what can be
      called with what", i.e. an undirected graph between the (interesting)
      free variables of an expression. Of course it makes combining the
      results a bit more tricky (especially mutual recursion), but still
      doable.
      
      The actually implemation of the graph structure is abstractly put away
      in a module of its own (UnVarGraph.hs)
      
      The implementation is geared towards efficiently representing the graphs
      that we need (which can contain large complete and large complete
      bipartite graphs, which would be huge in other representations). If
      someone feels like designing data structures: There is surely some
      speed-up to be obtained by improving that data structure.
      
      Additionally, the analysis now takes into account that if a RHS stays a
      thunk, then its calls happen only once, even if the variables the RHS is
      bound to is evaluated multiple times, or is part of a recursive group.
      cb8a63cb
  13. 18 Feb, 2014 8 commits
  14. 10 Feb, 2014 2 commits
    • Joachim Breitner's avatar
      Add a unit test for CallArity · 9bc82656
      Joachim Breitner authored
      This also sets precedence for testing internals of GHC directly, i.e.
      without trying to come up with Haskell code and observable effects.
      Let's see how that goes.
      
      I put all the tests (including those where the analysis could do better)
      in one file because starting the GHC API is quite slow.
      9bc82656
    • Joachim Breitner's avatar
      Implement CallArity analysis · cdceadf3
      Joachim Breitner authored
      This analysis finds out if a let-bound expression with lower manifest
      arity than type arity is always called with more arguments, as in that
      case eta-expansion is allowed and often viable. The analysis is very
      much tailored towards the code generated when foldl is implemented via
      foldr; without this analysis doing so would be a very bad idea!
      
      There are other ways to improve foldr/builder-fusion to cope with foldl,
      if any of these are implemented then this step can probably be moved to
      -O2 to save some compilation times. The current impact of adding this
      phase is just below +2% (measured running GHC's "make").
      cdceadf3