[Haskell-cafe] GHC optimisations

[Stefan O'Rear]

On Wed, Aug 22, 2007 at 09:04:11AM +0100, Simon Peyton-Jones wrote:
> | First of all, optimizing mod and div can not be done with PrelRules,
> | because they are not primitives, quot and rem are.
> 
> Yes, you can do them with PrelRules!  Check out PrelRules.builtinRules.
> 
> | Multiplication and division can become shifts:
> |
> |  > {-# RULES
> |  >
> |  > -- x * 2^n  -->  x `shiftL` n
> |  > "x# *# 2#"  forall x#.  x# *# 2# = x# `iShiftL#` 1#
> |  > "2# *# x#"  forall x#.  2# *# x# = x# `iShiftL#` 1#
> |  >   -- etc.
> 
> 
> | A problem with these rules is that you need a whole lot of them. 32 per
> | operation (on a 32 bit platform), * 4 operations, * 2 separate versions
> | for words and ints = 256.
> 
> I think you should be able to a lot better.  For example, to do
> constant folding for +# you might think you needed a lot of rules
> 
>         1# +# 2# = 3#
>         1# +# 3# = 4#
>         etc
> 
> But not so!  See PrelRules for how to write one rule that does all of
> these at once.  I think you can do multiply-to-shift in the same way.
> 
> The downside of PrelRules is that it's part of the compiler, not in
> Haskell pragmas; that's what makes it more expressive than rules
> written in source code.

Something I've pondered is adding a more-expressive form of RULES which
works using general pattern matching:

{-# XRULES
 "*#-to-shift" (*#)
  (CoreLit (CoreInt num)) obj
      | num .&. (num - 1) == 0  ->
          CoreApp (CoreVar "GHC.Prim.iShiftL#")
                  [obj, CoreLit (CoreInt (lg2 num))]
  obj (CoreLit (CoreInt num))
      | num .&. (num - 1) == 0  ->
          CoreApp (CoreVar "GHC.Prim.iShiftL#")
                  [obj, CoreLit (CoreInt (lg2 num))]
#-}

This would require reusing the TH infrastructure, and (depending on how
much we can abstract) might leak too many details of Core to be
useful; on the other hand it would allow some very interesting domain
optimizations to be done.

Views might be nice here.

Opinions on whether something like this is a good idea?

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070822/c13a6c0e/attachment.bin