cvs commit: fptools/ghc/compiler/main CmdLineOpts.lhs DriverState.hs fptools/ghc/compiler/simplCore SimplCore.lhs fptools/ghc/compiler/specialise SpecConstr.lhs Rules.lhs Specialise.lhs

[Simon Peyton Jones]

simonpj     2001/02/28 03:48:35 PST

  Modified files:
    ghc/compiler/main    CmdLineOpts.lhs DriverState.hs 
    ghc/compiler/simplCore SimplCore.lhs 
    ghc/compiler/specialise Rules.lhs Specialise.lhs 
  Added files:
    ghc/compiler/specialise SpecConstr.lhs 
  Log:
  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
  
  
  Revision  Changes    Path
  1.134     +1 -0      fptools/ghc/compiler/main/CmdLineOpts.lhs
  1.30      +5 -1      fptools/ghc/compiler/main/DriverState.hs
  1.91      +3 -0      fptools/ghc/compiler/simplCore/SimplCore.lhs
  1.22      +5 -6      fptools/ghc/compiler/specialise/Rules.lhs
  1.72      +11 -10    fptools/ghc/compiler/specialise/Specialise.lhs