Skip to content
  • Simon Peyton Jones's avatar
    [project @ 2002-04-04 13:15:18 by simonpj] · c44e1c41
    Simon Peyton Jones authored
    ---------------------------------------
    	A glorious improvement to CPR analysis
    	---------------------------------------
    
    Working on the CPR paper, I finally figured out how to
    do a decent job of taking account of strictness analyis when doing
    CPR analysis.
    
    There are two places we do that:
    
    1.  Usually, on a letrec for a *thunk* we discard any CPR info from
    the RHS.  We can't worker/wrapper a thunk.  BUT, if the let is
    	non-recursive
    	non-top-level
    	used strictly
    we don't need to discard the CPR info, because the thunk-splitting
    transform (WorkWrap.splitThunk) works.  This idea isn't new in this
    commit.
    
    
    2. Arguments to strict functions.  Consider
    
      fac n m = if n==0 then m
    		    else fac (n-1) (m*n)
    
    Does it have the CPR property?  Apparently not, because it returns the
    accumulating parameter, m.  But the strictness analyser will
    discover that fac is strict in m, so it will be passed unboxed to
    the worker for fac.  More concretely, here is the worker/wrapper
    split that will result from strictness analysis alone:
    
      fac n m = case n of MkInt n' ->
    	    case m of MkInt m' ->
    	    facw n' m'
    
      facw n' m' = if n' ==# 0#
    	       then I# m'
    	       else facw (n' -# 1#) (m' *# n')
    
    Now facw clearly does have the CPR property!  We can take advantage
    of this by giving a demanded lambda the CPR property.
    
    
    To make this work nicely, I've made NewDemandInfo into Maybe Demand
    rather than simply Demand, so that we can tell when we are on the
    first iteration.  Lots of comments about this in Note [CPR-AND-STRICTNESS].
    
    I don't know how much all this buys us, but it is simple and elegant.
    c44e1c41