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

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

Считывая исходный код в 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 не может trace функция и это 2 аргумента, и мы получаем hit напечатано дважды. Это работает как с GHC 6.12.4, так и с 7.0.3 в -O2,

Answer 2

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

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

hit 2
really hit 2
hit 1

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

hit 1
hit 2
really hit 2

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