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