Cardinality analysis and other small fixes

As you'll see I've just pushed a wave of commits, of which cardinality analysis is the big one. Some of the others are performance tweaks that I discovered when benchmarking. Before pushing the wave I did a full nofib run against today's HEAD; here are the results. Pretty modest reductions, but zero big outliers in the wrong direction. A couple of compiler perf tests are worse, which I should look into. Thanks to Ilya for doing a lot of the cardinality work. Simon -------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- anna -1.3% -0.5% 0.18 0.18 +0.0% ansi -2.5% -0.8% 0.00 0.00 +0.0% atom -2.3% -0.0% -1.3% -1.3% +0.0% awards -2.4% -0.1% 0.00 0.00 +0.0% banner -2.8% -0.2% 0.00 0.00 +0.0% bernouilli -2.5% -0.0% +0.0% +0.0% +0.0% binary-trees -2.6% -0.2% -1.1% -1.1% +7.4% boyer -2.4% -0.0% 0.07 0.07 +0.0% boyer2 -2.6% -0.4% 0.01 0.01 +0.0% bspt -2.1% -0.0% 0.02 0.02 +0.0% cacheprof -2.0% -0.4% -3.6% -2.7% -5.7% calendar -2.5% +0.2% 0.00 0.00 +0.0% cichelli -2.6% -0.0% 0.16 0.16 +0.0% circsim -2.3% -0.0% -2.0% -1.9% +11.5% clausify -2.5% -0.0% 0.06 0.06 +0.0% comp_lab_zift -2.4% -0.0% -3.0% -3.0% +14.3% compress -2.3% -0.0% +0.0% +0.0% -33.3% compress2 -2.7% -0.0% -8.1% -8.1% -14.3% constraints -2.7% -1.9% -3.5% -3.5% +0.0% cryptarithm1 -2.9% -0.0% -8.8% -8.8% -50.0% cryptarithm2 -2.5% -0.0% 0.01 0.01 +0.0% cse -2.5% -0.1% 0.00 0.00 +0.0% eliza -2.7% -0.1% 0.00 0.00 +0.0% event -2.5% -0.0% +0.0% +0.0% +0.0% exp3_8 -2.5% -0.0% +0.0% +0.0% +0.0% expert -2.7% -0.2% 0.00 0.00 +0.0% fannkuch-redux -2.5% -0.0% -0.9% -0.9% +0.0% fasta -3.3% -0.0% -0.2% -0.4% +0.0% fem -2.4% -0.0% 0.03 0.03 +0.0% fft -2.4% -0.0% 0.06 0.06 +0.0% fft2 -2.2% -0.0% 0.09 0.09 +0.0% fibheaps -2.5% -0.0% 0.05 0.05 +0.0% fish -2.8% -0.0% 0.02 0.02 -50.0% fluid -1.7% -0.0% 0.01 0.01 +0.0% fulsom -2.0% -0.0% +0.4% +0.4% +33.3% gamteb -2.3% +0.5% 0.06 0.06 +0.0% gcd -2.5% -0.0% 0.05 0.05 +0.0% gen_regexps -2.9% -0.1% 0.00 0.00 +0.0% genfft -2.5% -0.0% 0.05 0.05 +0.0% gg -2.3% -0.0% 0.02 0.02 +0.0% grep -2.6% -0.4% 0.00 0.00 +0.0% hidden -2.1% -0.0% -0.5% -0.3% +0.0% hpg -2.2% -1.0% +1.7% +1.7% +0.0% ida -2.4% -0.0% 0.13 0.12 +0.0% infer -2.2% +0.0% 0.10 0.10 +0.0% integer -2.4% +0.0% -2.7% -2.7% +0.0% integrate -2.4% -0.0% +1.2% +1.2% +0.0% k-nucleotide -6.3% -0.0% +1.1% +1.1% +0.0% kahan -2.5% -0.0% +0.0% +0.0% +0.0% knights -2.5% -1.6% 0.01 0.01 +0.0% lcss -2.5% +0.0% +0.0% +0.0% +0.0% life -2.7% -0.0% -2.8% -2.8% +0.0% lift -2.5% -0.0% 0.00 0.00 +0.0% listcompr -2.8% -0.0% 0.14 0.14 +0.0% listcopy -2.8% -0.0% 0.14 0.14 +0.0% maillist -2.9% -0.2% 0.07 0.09 +11.2% mandel -2.4% -0.0% 0.11 0.11 +0.0% mandel2 -2.8% -0.0% 0.00 0.00 +0.0% minimax -2.7% -0.0% 0.00 0.00 +0.0% mkhprog -2.8% +0.1% 0.00 0.00 +0.0% multiplier -2.5% -0.0% -4.5% -4.5% +0.0% n-body -3.7% -0.0% +1.2% +1.1% +0.0% nucleic2 -2.3% -10.9% 0.10 0.10 +0.0% para -2.6% -0.0% +0.0% +0.0% +0.0% paraffins -2.5% -0.0% 0.20 0.20 +0.0% parser -1.9% -0.2% 0.05 0.05 -20.0% parstof -2.2% -0.0% 0.00 0.00 +0.0% pic -2.4% -0.0% 0.00 0.00 +0.0% pidigits -2.5% -0.0% -0.3% -1.0% +0.0% power -2.2% -0.0% -1.4% -1.4% +0.0% pretty -2.7% -0.2% 0.00 0.00 +0.0% primes -2.6% -0.0% 0.11 0.11 +0.0% primetest -2.5% -0.0% 0.14 0.14 +0.0% prolog -2.4% -0.3% 0.00 0.00 +0.0% puzzle -2.8% -0.0% -8.0% -8.0% +0.0% queens -2.5% -0.0% 0.02 0.02 +0.0% reptile -2.2% -0.0% 0.02 0.02 +0.0% reverse-complem -3.3% -0.1% +4.5% +4.5% +0.0% rewrite -2.6% -0.1% 0.02 0.02 +0.0% rfib -2.4% -0.1% 0.03 0.03 +0.0% rsa -2.6% -0.0% 0.03 0.03 +0.0% scc -2.8% -0.4% 0.00 0.00 +0.0% sched -2.5% -0.0% 0.03 0.03 +0.0% scs -1.9% +0.0% +0.2% +0.2% +0.0% simple -1.9% -0.0% -2.1% -2.1% +0.0% solid -2.3% -0.0% +0.0% +0.0% +0.0% sorting -2.8% -0.0% 0.00 0.00 +0.0% spectral-norm -2.6% -0.1% +0.0% +0.0% +0.0% sphere -2.3% -1.5% 0.08 0.08 +0.0% symalg -1.7% -0.0% 0.01 0.01 +0.0% tak -2.5% -0.0% 0.02 0.02 +0.0% transform -2.2% -0.0% -1.8% -1.8% +0.0% treejoin -2.9% -0.0% +0.0% +0.0% +0.0% typecheck -2.4% -0.0% -4.4% -4.4% +0.0% veritas -1.1% -0.0% 0.00 0.00 +0.0% wang -2.4% -0.0% +0.0% +0.0% +0.0% wave4main -2.4% +0.5% +0.0% +0.0% +0.0% wheel-sieve1 -2.5% -0.0% +0.0% +0.0% +0.0% wheel-sieve2 -2.5% -0.0% +0.0% +0.0% +0.0% x2n1 -2.5% -0.0% 0.00 0.00 +0.0% -------------------------------------------------------------------------------- Min -6.3% -10.9% -8.8% -8.8% -50.0% Max -1.1% +0.5% +4.5% +4.5% +33.3% Geometric Mean -2.5% -0.2% -1.3% -1.3% -1.5% | -----Original Message----- | From: ghc-commits-bounces@haskell.org [mailto:ghc-commits- | bounces@haskell.org] On Behalf Of Simon Peyton Jones | Sent: 06 June 2013 14:30 | To: ghc-commits@haskell.org | Subject: [commit: ghc] master: Implement cardinality analysis (99d4e5b) | | Repository : http://darcs.haskell.org/ghc.git/ | | On branch : master | | https://github.com/ghc/ghc/commit/99d4e5b4a0bd32813ff8c74e91d2dcf6b355 | 5176 | | >--------------------------------------------------------------- | | commit 99d4e5b4a0bd32813ff8c74e91d2dcf6b3555176 | Author: Simon Peyton Jones | Date: Fri May 3 14:50:58 2013 +0100 | | Implement cardinality analysis | | 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. | | compiler/basicTypes/Demand.lhs | 1034 ++++++++++++++++++++++++++------ | ------ | compiler/basicTypes/MkId.lhs | 4 +- | compiler/basicTypes/OccName.lhs | 7 +- | compiler/cmm/CmmParse.y | 3 +- | compiler/codeGen/StgCmmBind.hs | 44 +- | compiler/codeGen/StgCmmTicky.hs | 25 +- | compiler/coreSyn/CorePrep.lhs | 57 ++- | compiler/main/DynFlags.hs | 6 +- | compiler/simplCore/OccurAnal.lhs | 208 ++++---- | compiler/stgSyn/CoreToStg.lhs | 30 +- | compiler/stranal/DmdAnal.lhs | 582 ++++++++++++--------- | docs/storage-mgt/ldv.tex | 6 +- | includes/stg/Ticky.h | 7 +- | rts/Linker.c | 8 +- | rts/Ticky.c | 15 +- | 15 files changed, 1302 insertions(+), 734 deletions(-) | | | Diff suppressed because of size. To see it, use: | | git show 99d4e5b4a0bd32813ff8c74e91d2dcf6b3555176 | | _______________________________________________ | ghc-commits mailing list | ghc-commits@haskell.org | http://www.haskell.org/mailman/listinfo/ghc-commits