Continuing the previous discussion...
The "CSE modulo equality on integers" optimisation is actually called "Value
Based Partial Redundancy Elimination". There's a long line of prior work, and a
recentish paper by Thomas VanDrunen and Antony Hoskin at CC 2004. The algorithm
was implemented as a pass in LLVM, but has since rotted. It was removed due to
being unmaintained for the LLVM 2.7 release (April 2010), which was
coincidently the first version to support GHC (sighs). However, LLVM also
implements a related optimisation which it calls "Global Value Numbering" after
the hashing method used to identify expressions with the same value.
Unfortunately, it looks like the optimisation is failing to fire because it's
worried about the potential for low level pointer aliasing. To cut a longer
story short, I've just spent the last 4 hrs banging my head against the
following problem:
Suppose I have:
action :: Unbox a => a -> IO ()
thing :: Unbox a => (Int -> a) -> Int -> Int -> IO ()
thing !f !x1 !x2
= do let y1 = f x1
let y2 = f x2
action y1
action y2
I want to prevent the bindings for y1 and y2 from being floated into their
use-sites. In the resulting Core/Cmm code, both applications of "f" must be
fully evaluated before the two actions are performed. We don't need to deepseq
the result because "thing" will only ever be instantiated with Int, Float or
Double, so the intermediate values will all be unboxed.
There are some extra constraints:
1) The types of f, y1 and y2 must remain polymorphic.
2) You can't add new type class constraints to the types of "action", or
"thing", though we could add methods to "Unbox".
3) You can't do anything that results in new objects or thunks being allocated
in the core code.
I've tried various combinations of `seq`, `pseq` and case, to no avail. GHC
keeps being clever, eliminates whatever I write and refloats the bindings.
I thought about something like:
thing :: Unbox a => (Int -> a) -> Int -> Int -> IO ()
thing !f !x1 !x2
= do let y1 = f x1
let y2 = f x2
doActions y1 y2
where {-# NOINLINE doActions #-}
doActions y1' y2'
= do action y1'
action y2'
Sadly, this breaks rule 3. After inlining etc, the type of "a" turns out to be
"Float", and intermediate values are unboxed. The core code becomes equivalent
to:
= do let y1 = F# (... compute value of f x1 ...)
let y2 = F# (... compute value of f x2 ...)
doActions y1 y2
Allocating the first float object requires a write to the store, and breaks the
LLVM optimisation I want.
I tried specialising for doActions :: Float -> Float -> IO (), thinking it
would produce a version that takes the unboxed floats directly, but then it
complains about:
Warning: RULE left-hand side too complicated to desugar (doActions @ IO @
Float $dUnbox $dPrimMonad) `cast` ...
Another idea would be to add some primops like the following:
noopInt# :: Int# -> State# s -> State# s
noopFloat# :: Float# -> State# s -> State# s
...
These would serve as "sinks" for the values created by my two bindings. They
can't be polymorphic because I don't want I# or F# in the calls. Are there
functions like this already? I couldn't find them....
Cheers,
Ben.
_______________________________________________
Cvs-ghc mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/cvs-ghc
