从GHC中哄骗循环不变代码运动

Question

我一直在努力进行GHC中的低级手动循环优化.我的程序包含一些执行数值计算的循环.真实数据包含在其他数据结构中,并且程序被分​​解为"循环控制流函数"和"计算函数",使得一些数据结构字段最终在内部循环内被读取.我希望GHC将这些读取移出内部循环.这是代码的简化版本,用于显示正在发生的事情.

data D = D !Double !C
data C = C Double

-- This function is called in every loop iteration.
-- Parameter 'c' is loop-invariant.
exampleLoopBody i a c =
  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

每个循环迭代都会计算case c of C b,但这是冗余计算,因为它c是循环不变的.我可以通过在循环外部放置一个冗余的case表达式来使GHC解除它:

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

编译器内联exampleLoopBody.之后,内部案例陈述是多余的并被消除:

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

目的seq是确保case表达式不是死代码.该seq检查是否b是_|_.GHC注意到,自从b计算出来之后,在循环体中重用该值是有用的.

现在,问题出在这里:我真的希望所有相关的数据字段都是严格的.如果我在数据定义中插入严格注释,像这样,

data C = C !Double

然后就GHC而言seq并case c of C b没有影响.GHC删除它们,我得到了这个:

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

此代码case c of C b在每次迭代中进行评估,这正是我试图避免的.

如果我不能依赖seq,我不知道如何b在循环体外强制计算.在这种情况下,我可以使用一些技巧吗？

Answer 1

您可以尝试重新排列参数并将循环变体部分移至 lambda 中：

-- note the order of the arguments changed
exampleLoopBody (C b) =
  \i a -> 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

此外，此代码目前构建了一个大型未计算表达式，因此您可能希望每次通过循环强制使用累加器参数。