Как предотвратить удаление общих подвыражений (CSE) с помощью GHC

Как насчет устранения источника проблемы — неявного эффекта — с помощью монады последовательности, которая создает этот эффект? Например. монада строгого тождества с трассировкой:

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 сделал все возможное для оптимизации кода, включая статические расчеты, сохраняя при этом правильную трассировку.

Ссылки: полезная монада Eval для секвенирования была представлена ​​Саймон Марлоу.

При чтении исходного кода в 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 на -O2.

Я думаю, что вы можете указать опцию -fno-cse в исходном файле, т.е. поставив прагму

{-# 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 и общего подвыражения больше нет.

Я немного не уверен в монаде последовательности Дона (отправляю это как ответ, потому что сайт не позволяет мне добавлять комментарии). Немного изменив пример:

main :: IO ()
main = print $ runEval $ do
            t1 <- track "hit 1" (trace "really hit 1" 1)
            t2 <- track "hit 2" 2
            return (t1 + t2)

Это дает нам следующий результат:

hit 1
hit 2
really hit 1

То есть первая трассировка срабатывает, когда выполняется оператор t1 <- ..., а не тогда, когда t1 фактически оценивается в return (t1 + t2). Если мы определим монадический оператор связывания как

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

вместо этого выходные данные будут отражать фактический порядок оценки:

hit 1
really hit 1
hit 2

То есть трассировка будет срабатывать при выполнении инструкции (t1 + t2), что (IMO) является тем, чего мы действительно хотим. Например, если мы изменим (t1 + t2) на (t2 + t1), это решение выдаст следующий результат:

hit 2
really hit 2
hit 1

Вывод исходной версии остается неизменным, и мы не видим, когда наши термины действительно оцениваются:

hit 1
hit 2
really hit 2

Как и исходное решение, это также работает с -O3 (проверено на GHC 7.0.3).