Redundancy elimination, and how to prevent bindings from being floated.

[Ben Lippmeier]

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.