1. 06 Jun, 2013 5 commits
    • Simon Peyton Jones's avatar
      Add TyCon.checkRecTc, and use in in typeArity · a1a67b58
      Simon Peyton Jones authored
      This just formalises an abstraction we've been using anyway,
      namely to expand "recursive" TyCons until we see them twice.
      We weren't doing this in typeArity, and that inconsistency
      was leading to a subsequent ASSERT failure, when compiling
      Stream.hs, which has a newtype like this
      
         newtype Stream m a b = Stream (m (Either b (a, Stream m a b)))
      a1a67b58
    • Simon Peyton Jones's avatar
      Wibbles (merg-os) to ticky-ticky · 62653122
      Simon Peyton Jones authored
      62653122
    • Simon Peyton Jones's avatar
      Comments about the Name Cache · 507c8970
      Simon Peyton Jones authored
      507c8970
    • Simon Peyton Jones's avatar
      Implement cardinality analysis · 99d4e5b4
      Simon Peyton Jones authored
      This major patch implements the cardinality analysis described
      in our paper "Higher order cardinality analysis". It is joint
      work with Ilya Sergey and Dimitrios Vytiniotis.
      
      The basic is augment the absence-analysis part of the demand
      analyser so that it can tell when something is used
      	 never
      	 at most once
       	 some other way
      
      The "at most once" information is used
          a) to enable transformations, and
             in particular to identify one-shot lambdas
          b) to allow updates on thunks to be omitted.
      
      There are two new flags, mainly there so you can do performance
      comparisons:
          -fkill-absence   stops GHC doing absence analysis at all
          -fkill-one-shot  stops GHC spotting one-shot lambdas
                           and single-entry thunks
      
      The big changes are:
      
      * The Demand type is substantially refactored.  In particular
        the UseDmd is factored as follows
            data UseDmd
              = UCall Count UseDmd
              | UProd [MaybeUsed]
              | UHead
              | Used
      
            data MaybeUsed = Abs | Use Count UseDmd
      
            data Count = One | Many
      
        Notice that UCall recurses straight to UseDmd, whereas
        UProd goes via MaybeUsed.
      
        The "Count" embodies the "at most once" or "many" idea.
      
      * The demand analyser itself was refactored a lot
      
      * The previously ad-hoc stuff in the occurrence analyser for foldr and
        build goes away entirely.  Before if we had build (\cn -> ...x... )
        then the "\cn" was hackily made one-shot (by spotting 'build' as
        special.  That's essential to allow x to be inlined.  Now the
        occurrence analyser propagates info gotten from 'build's stricness
        signature (so build isn't special); and that strictness sig is
        in turn derived entirely automatically.  Much nicer!
      
      * The ticky stuff is improved to count single-entry thunks separately.
      
      One shortcoming is that there is no DEBUG way to spot if an
      allegedly-single-entry thunk is acually entered more than once.  It
      would not be hard to generate a bit of code to check for this, and it
      would be reassuring.  But it's fiddly and I have not done it.
      
      Despite all this fuss, the performance numbers are rather under-whelming.
      See the paper for more discussion.
      
             nucleic2          -0.8%    -10.9%      0.10      0.10     +0.0%
               sphere          -0.7%     -1.5%      0.08      0.08     +0.0%
      --------------------------------------------------------------------------------
                  Min          -4.7%    -10.9%     -9.3%     -9.3%    -50.0%
                  Max          -0.4%     +0.5%     +2.2%     +2.3%     +7.4%
       Geometric Mean          -0.8%     -0.2%     -1.3%     -1.3%     -1.8%
      
      I don't quite know how much credence to place in the runtime changes,
      but movement seems generally in the right direction.
      99d4e5b4
    • Simon Peyton Jones's avatar
      Comments and white space only · da4ff650
      Simon Peyton Jones authored
      da4ff650
  2. 05 Jun, 2013 2 commits
  3. 04 Jun, 2013 6 commits
  4. 03 Jun, 2013 4 commits
  5. 02 Jun, 2013 1 commit
  6. 01 Jun, 2013 1 commit
  7. 31 May, 2013 2 commits
  8. 30 May, 2013 15 commits
  9. 28 May, 2013 4 commits