Skip to content
  • Simon Peyton Jones's avatar
    [project @ 2001-02-28 11:48:34 by simonpj] · 12e6a9a5
    Simon Peyton Jones authored
    Add most of the code for constructor specialisation.  The comment
    below is reproduced from specialise/SpecConstr.lhs.
    
    It doesn't quite work properly yet, because we need to have 
    rules in scope in a recursive function's own RHS, and that
    entails a bit of fiddling I havn't yet completed.  But SpecConstr
    itself is a nice neat 250 lines of code.
    
    -----------------------------------------------------
    			Game plan
    -----------------------------------------------------
    
    Consider
    	drop n []     = []
    	drop 0 xs     = []
    	drop n (x:xs) = drop (n-1) xs
    
    After the first time round, we could pass n unboxed.  This happens in
    numerical code too.  Here's what it looks like in Core:
    
    	drop n xs = case xs of
    		      []     -> []
    		      (y:ys) -> case n of 
    				  I# n# -> case n# of
    					     0 -> []
    					     _ -> drop (I# (n# -# 1#)) xs
    
    Notice that the recursive call has an explicit constructor as argument.
    Noticing this, we can make a specialised version of drop
    	
    	RULE: drop (I# n#) xs ==> drop' n# xs
    
    	drop' n# xs = let n = I# n# in ...orig RHS...
    
    Now the simplifier will apply the specialisation in the rhs of drop', giving
    
    	drop' n# xs = case xs of
    		      []     -> []
    		      (y:ys) -> case n# of
    				  0 -> []
    				  _ -> drop (n# -# 1#) xs
    
    Much better!  
    
    We'd also like to catch cases where a parameter is carried along unchanged,
    but evaluated each time round the loop:
    
    	f i n = if i>0 || i>n then i else f (i*2) n
    
    Here f isn't strict in n, but we'd like to avoid evaluating it each iteration.
    In Core, by the time we've w/wd (f is strict in i) we get
    
    	f i# n = case i# ># 0 of
    		   False -> I# i#
    		   True  -> case n of n' { I# n# ->
    			    case i# ># n# of
    				False -> I# i#
    				True  -> f (i# *# 2#) n'
    
    At the call to f, we see that the argument, n is know to be (I# n#),
    and n is evaluated elsewhere in the body of f, so we can play the same
    trick as above.  However we don't want to do that if the boxed version
    of n is needed (else we'd avoid the eval but pay more for re-boxing n).
    So in this case we want that the *only* uses of n are in case statements.
    
    
    So we look for
    
    * A self-recursive function.  Ignore mutual recursion for now, 
      because it's less common, and the code is simpler for self-recursion.
    
    * EITHER
    
       a) At a recursive call, one or more parameters is an explicit 
          constructor application
    	AND
          That same parameter is scrutinised by a case somewhere in 
          the RHS of the function
    
      OR
    
        b) At a recursive call, one or more parameters has an unfolding
           that is an explicit constructor application
    	AND
          That same parameter is scrutinised by a case somewhere in 
          the RHS of the function
    	AND
          Those are the only uses of the parameter
    12e6a9a5