Deriving a coaxing loop from GHC code

Question

I struggled with low-level manual cycle optimization in the GHC. My program contains some loops that do numerical calculations. Real data is wrapped in other data structures, and the program is divided into "cyclic control flow functions" and "computational functions" so that some fields of the data structure are read inside the internal loops. I want the GHC to move these reads from internal loops. Here's a simplified version of the code to show what's happening.

data D = D !Double !C data C = C Double -- This function is called in every loop iteration. -- Parameter 'c' is loop-invariant. exampleLoopBody iac = case c of C b -> a + b * fromIntegral i -- The body of this function is a counted loop that should be optimized foo x = case x of D acc0 c -> let loop i acc = if i > 100 then acc else loop (i+1) (exampleLoopBody i acc c) in loop 0 acc0 

Each iteration of the loop evaluates case c of C b , but this is a redundant calculation because c is cycloinvariant. I can get the GHC to remove it by putting the redundant expression out of the loop:

 foo x = case x of D acc0 c -> case c -- This case statement inserted for optimization purposes of C b -> b `seq` -- It will read 'b' outside of the loop let loop i acc = if i > 100 then acc else loop (i+1) (exampleLoopBody i acc c) in loop 0 acc0 

The compiler in the lines exampleLoopBody . After that, the internal case statement is redundant and resolves:

 foo x = case x of D acc0 c -> case c of C b -> b `seq` let loop i acc = if i > 100 then acc else loop (i+1) (acc + b * fromIntegral i) -- The inlined case expression disappears in loop 0 acc0 

The purpose of seq is to make sure that the case expression is not dead code. seq checks to see if b _|_ . The GHC notes that since b been computed, it is useful to reuse this value in the body of the loop.

Now here is the problem: I really want all the relevant data fields to be strict. If I insert strictness annotations in the data definition, for example,

 data C = C !Double 

then seq and case c of C b have no effect on GHC. GHC removes them and I get the following:

 foo x = case x of D acc0 c -> let loop i acc = if i > 100 then acc else loop (i+1) (case c of C b -> acc + b * fromIntegral i) -- Evaluate the case in every iteration in loop 0 acc0 

This code evaluates case c of C b at each iteration, which I tried to avoid.

If I can’t rely on seq , I don’t know how else to force b out of the loop body. Is there a trick I can use in this case?

Answer 1

You can try to rearrange the arguments and move the parts of the loop option to lambda:

 -- note the order of the arguments changed exampleLoopBody (C b) = \ia -> a + b * fromIntegral i foo (D acc0 c) = let loopBody = exampleLoopBody c loop i acc = if i > 100 then acc else loop (i+1) (loopBody i acc) in loop 0 acc0 

In addition, this code accumulates a great invaluable expression at the moment, so you can force the battery setting every cycle.

Answer 2

This seems like the main reason newtype was placed in the language. Just change data C = C !Double to newtype C = C Double and write a naive version of the code. All case expressions for values ​​of type C will be deleted. As a side note, the code template that you have in your examples:

 case foo of D acc0 c -> case c of C b -> ... 

may be more succinctly written:

 case foo of D acc0 (C b) -> ...