Как предотвратить устранение общих подвыражений

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

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

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 для секвенирования была введена Саймоном Марлоу .

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 при -O2.

Answer 3

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

Answer 4

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

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)выполняется, что (ИМО), что мы действительно хотим.Например, если мы изменим (t1 + t2) на (t2 + t1), это решение даст следующий вывод:

hit 2
really hit 2
hit 1

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

hit 1
hit 2
really hit 2

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