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

给定程序:

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不会被CSE拒绝的子表达式e + e？我知道 lazy ，但是找不到旨在抑制CSE的任何东西。

这个问题的背景是cmdargs库，其中CSE破坏了该库(由于库中的杂质)。一种解决方案是要求该库的用户指定-fno-cse，但我希望修改该库。

最佳答案

如何通过使用引入后果的排序单子(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)

虽然仍然是纯代码，但即使使用-O2，GHC也不会尝试变得聪明:

    $ ./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 Marlow介绍了用于排序的有用Eval monad。

关于optimization - 如何使用GHC防止常见的子表达消除(CSE)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5920200/