如何使用GHC防止常见的子表达式消除(CSE)

Question

鉴于该计划:

import Debug.Trace
main = print $ trace "hit" 1 + trace "hit" 1

如果我用ghc -O(7.0.1或更高版本)编译,我得到输出:

hit
2

即GHC使用常见的子表达式消除(CSE)来重写我的程序:

main = print $ let x = trace "hit" 1 in x + x

如果我编译-fno-cse然后我看到hit出现两次.

是否可以通过修改程序来避免CSE？是否有任何子表达式e,我可以保证e + e不会CSE'd？我知道lazy,但找不到任何旨在抑制CSE的东西.

这个问题的背景是cmdargs库,其中CSE打破了库(由于库中的杂质).一种解决方案是要求库的用户指定-fno-cse,但我更喜欢修改库.

Answer 1

如何通过使用引入该效果的测序monad来消除麻烦的来源 - 隐含效应？例如严格的身份monad跟踪:

data Eval a = Done a
            | Trace String a

instance Monad Eval where
  return x = Done x

  Done x    >>= k = k x
  Trace s a >>= k = trace s (k a)

runEval :: Eval a -> a
runEval (Done x) = x

track = Trace

现在我们可以用保证的trace调用顺序编写东西:

main = print $ runEval $ do
            t1 <- track "hit" 1
            t2 <- track "hit" 1
            return (t1 + t2)

虽然仍然是纯粹的代码,GHC不会试图变得聪明,即使-O2:

    $ ./A
    hit
    hit
    2

因此,我们只引入足以向GHC传授我们想要的语义的计算效果(跟踪).

这对编译优化非常有用.因此,GHC 2在编译时优化了数学,但仍然保留了trace语句的顺序.

作为这种方法有多强大的证据,这里是核心-O2和积极的内联:

main2 =
  case Debug.Trace.trace string trace2 of
    Done x -> case x of 
        I# i# -> $wshowSignedInt 0 i# []
    Trace _ _ -> err

trace2 = Debug.Trace.trace string d

d :: Eval Int
d = Done n

n :: Int
n = I# 2

string :: [Char]
string = unpackCString# "hit"

因此,GHC已尽其所能优化代码 - 包括静态计算数学 - 同时仍保留正确的跟踪.

参考文献:Simon MarlowEval介绍了有用的测序monad .

Answer 2

将源代码读入GHC,唯一不符合CSE条件的表达式是那些未通过exprIsBig测试的表达式.目前,这意味着Expr值Note,Let和Case,以及包含这些的表达式.

因此,对上述问题的回答是:

unit = reverse "" `seq` ()

main = print $ trace "hit" (case unit of () -> 1) +
               trace "hit" (case unit of () -> 1)

在这里,我们创建一个unit解析为的值(),但GHC无法确定其值(通过使用递归函数GHC无法优化 - reverse只是一个简单的一个).这意味着GHC不能CSE trace函数,它是2个参数,我们hit打印两次.这适用于GHC 6.12.4和7.0.3 at -O2.

Answer 3

我想你可以-fno-cse在源文件中指定选项,即通过放置一个pragma

{-# OPTIONS_GHC -fno-cse #-}

在上面.

另一种避免常见子表达式消除或一般浮动的方法是引入伪参数.例如,你可以试试

let x () = trace "hi" 1 in x () + x ()

这个特殊的例子不一定有效; 理想情况下,您应该通过伪参数指定数据依赖关系.例如,以下内容可能有效:

let
    x dummy = trace "hi" $ dummy `seq` 1
    x1      = x ()
    x2      = x x1 
in x1 + x2

x现在的结果"取决于"参数,dummy并且不再存在共同的子表达式.