预计GHC可以可靠地执行哪些优化？

小开

最佳答案

此GHC TRAC页面也很好地解释了过程。这一页解释了优化顺序，尽管与大多数Trac Wiki一样，它已经过时了。

对于细节，最好的办法可能是查看特定程序是如何编译的。查看正在执行哪些优化的最佳方法是使用-v标志对程序进行详细编译。以我能在电脑上找到的第一个Haskell片段为例：

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
[NONREC
ModSummary {
ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
ms_mod = main:Main,
ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
import Control.Concurrent, import System.Environment]
ms_srcimps = []
}]
*** Deleting temp files:
Deleting:
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
Consts = True,
PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
Consts = True,
PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
[DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

从第一个*** Simplifier:到最后一个，所有的优化阶段都发生在这里，我们看到了很多。

首先，简化器在几乎所有阶段之间运行。这使得编写多个过程变得更加容易。例如，在实现许多优化时，它们只需创建重写规则来传播更改，而不必手动执行。Simplifier包含许多简单的优化，包括内联和融合。据我所知，这样做的主要限制是GHC拒绝内联递归函数，并且必须正确命名才能使Fusion工作。

接下来，我们将看到已执行的所有优化的完整列表：

专业化

专门化的基本思想是通过标识调用函数的位置并创建非多态的函数版本（它们特定于调用它们的类型）来消除多态和重载。您还可以告诉编译器使用SPECIALISE pragma来执行此操作。以阶乘函数为例：
```
 fac :: (Num a, Eq a) => a -> a
fac 0 = 1
fac n = n * fac (n - 1)
```
由于编译器不知道要使用的乘法的任何属性，因此根本无法对其进行优化。但是，如果它看到它在Int上使用，它现在可以创建一个新版本，只是类型不同：
```
 fac_Int :: Int -> Int
fac_Int 0 = 1
fac_Int n = n * fac_Int (n - 1)
```
接下来，可以触发下面提到的规则，并且您最终可以在未装箱的Int上工作，这比原始的要快得多。另一种看待专门化的方法是部分应用于类型类字典和类型变量。

这里的源中有大量的纸币。
浮
出水面

编辑：我以前显然误解了这个。我的解释完全改变了。

其基本思想是将不应重复的计算移出函数。例如，假设我们有：
```
 \x -> let y = expensive in x+y
```
在上面的lambda中，每次调用函数时，都会重新计算_0的_ABC.浮出产生的一个更好的函数是
```
 let y = expensive in \x -> x+y
```
为了促进该过程，可以应用其他变换。例如，会发生以下情况：
```
  \x -> x + f 2
\x -> x + let f_2 = f 2 in f_2
\x -> let f_2 = f 2 in x + f_2
let f_2 = f 2 in \x -> x + f_2
```
再次，节省了重复计算。

在这种情况下，源的可读性很强。

此时，两个相邻lambdas之间的绑定不会浮动。例如，这种情况不会发生：
```
 \x y -> let t = x+x in ...
```
去
```
  \x -> let t = x+x in \y -> ...
```
向内
漂浮

引用源代码，

floatInwards的主要用途是浮动到案例的分支中，这样我们就不会分配内容，将它们保存在堆栈中，然后发现所选分支中不需要它们。

例如，假设我们有以下表达式：
```
 let x = big in
case v of
True -> x + 1
False -> 0
```
如果v求值为False，则通过分配x（这大概是一些大的thunk），我们浪费了时间和空间。向内浮动解决了这个问题，产生了：
```
 case v of
True -> let x = big in x + 1
False -> let x = big in 0
```
，随后由简化符替换为
```
 case v of
True -> big + 1
False -> 0
```
这张纸虽然涵盖了其他主题，但给出了相当清晰的介绍。请注意，尽管名称不同，但浮动输入和浮动输出不会进入无限循环，原因有两个：
1. FLOAT IN FLOATS允许INTOcase语句，而FLOAT OUT处理函数。
2. 传球的顺序是固定的，所以它们不应该无限交替。
需求分析

需求分析或严格性分析与其说是一种转换，不如说是一种信息收集过程。编译器查找始终计算其参数（或至少部分参数）的函数，并使用按值调用而不是按需调用来传递这些参数。因为您可以避开thunk的开销，所以这通常要快得多。Haskell中的许多性能问题要么是由于这一遍失败，要么是由于代码不够严格。一个简单的例子是使用foldr、foldl和foldl'来对整数列表求和之间的差异-第一个导致堆栈溢出，第二个导致堆溢出，而最后一个由于严格性而运行良好。这可能是所有这些中最容易理解和最好记录的。我相信多态性和CPS代码通常会击败这一点。
工人包装器绑定

Worker/Wrapper转换的基本思想是在一个简单的结构上执行一个紧密的循环，在末尾转换到该结构或从该结构转换。以这个函数为例，它计算一个数的阶乘。
```
 factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
```
使用GHC中Int的定义，我们有
```
 factorial :: Int -> Int
factorial (I# 0#) = I# 1#
factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
I# down# -> down#)
```
请注意代码是如何包含在I#s中的？我们可以通过以下方式删除它们：
```
 factorial :: Int -> Int
factorial (I# n#) = I# (factorial# n#)


factorial# :: Int# -> Int#
factorial# 0# = 1#
factorial# n# = n# *# factorial# (n# -# 1#)
```
尽管这个特定的示例也可以由SpecConstr完成，但是Worker/Wrapper转换在它所能做的事情上是非常通用的。
公共子表达式

这是另一个非常有效的简单优化，就像严格性分析一样。其基本思想是，如果有两个相同的表达式，它们将具有相同的值。例如，如果fib是斐波纳契数计算器，则CSE将转换
```
 fib x + fib x
```
进入
```
 let fib_x = fib x in fib_x + fib_x
```
这将计算量减半。不幸的是，这有时会妨碍其他优化。另一个问题是，这两个表达式必须在相同的位置，并且它们必须句法上相同，而不是在值上相同。例如，如果没有一组内联，CSE将不会在下面的代码中触发：
```
 x = (1 + (2 + 3)) + ((1 + 2) + 3)
y = f x
z = g (f x) y
```
然而，如果你通过LLVM编译，由于它的全局值编号传递，你可能会得到其中的一些组合。
解放凯斯

这似乎是一个可怕的文档化转换，除了它可能导致代码爆炸的事实之外。下面是我找到的小文档的重新格式化（并稍微重写）的版本：

此模块遍历Core，并在自由变量上查找case。标准是：如果在到递归调用的路径上的自由变量上存在case，则递归调用被替换为展开。例如，在
```
 f = \ t -> case v of V a b -> a : f t
```
更换内部f。使
```
 f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t
```
请注意阴影的必要性。简化，我们得到
```
 f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)
```
这是更好的代码，因为a在内部letrec中是空闲的，而不需要从v进行投影。注意，与处理已知形式的论据的SpecConstr不同，这处理自由变量。

有关specconstr的更多信息，请参见下文。
SpecConstr-这将转换程序，如
```
 f (Left x) y = somthingComplicated1
f (Right x) y = somethingComplicated2
```
进入
```
 f_Left x y = somethingComplicated1
f_Right x y = somethingComplicated2


{-# INLINE f #-}
f (Left x) = f_Left x
f (Right x) = f_Right x
```
作为一个扩展的例子，采用last的定义：
```
 last [] = error "last: empty list"
last (x:[]) = x
last (x:x2:xs) = last (x2:xs)
```
我们首先将其转换为
```
 last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last (x2:xs)


{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
接下来，运行简化器，我们有
```
 last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last_cons x2 xs


{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
请注意，程序现在更快了，因为我们不会重复地对列表的前面进行装箱和取消装箱。另请注意，内联是至关重要的，因为它允许实际使用新的、更有效的定义，并使递归定义更好。

SpecConstr由许多启发式算法控制。文件中提到的是：
1. lambda是显式的，并且aritya。
2. 右手边足够小，由旗帜控制的东西。
3. 该函数是递归的，并且在右侧使用了Specializable调用。
4. 函数的所有参数都存在。
5. 至少有一个参数是构造函数应用程序。
6. 这个论点在函数中的某个地方进行了案例分析。
然而，启发法几乎肯定已经改变了。事实上，这篇论文提到了另一种第六种启发式方法：

仅当x是由case仔细检查的唯一的，并且不传递给普通函数或作为结果的一部分返回时，才专注于参数x。

这是一个非常小的文件（12行），所以可能没有触发那么多的优化（尽管我认为它做了所有的优化）。这也没有告诉你为什么它选择了这些传球，以及为什么它把它们按这个顺序排列。

小开

懒惰

这不是“编译器优化”，但它是由语言规范保证的，所以你总是可以指望它发生。从本质上讲，这意味着工作不会执行，直到你“做了一些事情”的结果。（除非你做了几件事中的一件，故意关掉懒惰。）

很明显，这本身就是一个完整的话题，所以已经有很多关于它的问题和答案。

在我有限的经验中，让你的代码太懒惰或太严格的很大性能损失（时间和空间）比我将要讨论的任何其他东西都要大……

严格性分析

除非必要，否则懒惰就是逃避工作。如果编译器可以确定“总是”需要给定的结果，那么它就不会费心存储计算并在以后执行它。它会直接执行，因为这样效率更高。这就是所谓的“严格分析”。

显然，问题是编译器不能总是来检测何时可以使某些内容变得严格。有时你需要给编译器一些提示。（我不知道有任何简单的方法来确定严格性分析是否已经完成了您认为它已经完成的工作，除了通过核心输出。）

内联

如果你调用一个函数，并且编译器可以知道你调用的是哪个函数，它可能会尝试“内联”该函数-也就是说，用函数本身的副本替换函数调用。函数调用的开销通常很小，但内联通常会使其他优化发生，而这在其他情况下是不会发生的，因此内联可能是一个巨大的胜利。

函数只有在“足够小”的情况下才会内联（或者如果您添加了专门要求内联的杂注）。此外，只有在编译器知道您正在调用什么函数的情况下，才能内联函数。有两种主要方式是编译器无法判断的：

如果你调用的函数是从其他地方传入的。例如，当编译filter函数时，您不能内联过滤器谓词，因为它是用户提供的参数。
如果你调用的函数是一个类方法和，编译器不知道涉及到什么类型。例如，当编译sum函数时，编译器不能内联+函数，因为sum使用几种不同的数字类型，每种类型具有不同的+函数。

在后一种情况下，您可以使用{-# SPECIALIZE #-}编译指示来生成硬编码为特定类型的函数版本。例如，{-# SPECIALIZE sum :: [Int] -> Int #-}将编译为Int类型硬编码的sum的版本，这意味着+可以内联在该版本中。

但请注意，只有当编译器知道我们正在使用Int时，才会调用新的特殊sum函数。否则，将调用原始的多态sum。同样，实际的函数调用开销相当小。这是内联可以实现的额外优化，这是有益的。

公共子表达式消除

如果某个代码块计算了两次相同的值，编译器可能会将其替换为相同计算的单个实例。例如，如果您

(sum xs + 1) / (sum xs + 2)

那么编译器可能会将其优化为

let s = sum xs in (s+1)/(s+2)

您可能以为编译器会总是来执行此操作。然而，显然在某些情况下，这可能会导致更差的性能，而不是更好的性能，因此GHC不会总是来执行此操作。坦率地说，我并不真正了解这背后的细节。但底线是，如果这种转换对您很重要，那么手动完成它并不难。（如果它不重要，你为什么要担心它？）

CASE表达式

请考虑以下几点：

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

前三个等式都检查列表是否非空（以及其他内容）。但是检查同样的东西三次是浪费的。幸运的是，编译器很容易将其优化为几个嵌套的case表达式。在这种情况下，类似于

foo xs =
case xs of
y:ys ->
case y of
0 -> "zero"
1 -> "one"
_ -> foo ys
[]   -> "end"

这不太直观，但效率更高。因为编译器可以很容易地进行这种转换，所以您不必担心。只需以最直观的方式编写模式匹配即可。编译器非常擅长重新排序和重新排列，以使其尽可能快。

融合

列表处理的标准Haskell习惯用法是将获取一个列表并生成一个新列表的函数链接在一起。典型的例子是

map g . map f

不幸的是，虽然懒惰保证了跳过不必要的工作，但中间列表的所有分配和释放都会影响性能。“融合”或“毁林”是编译器试图消除这些中间步骤的地方。

麻烦的是，这些函数中的大多数都是递归的。在没有递归的情况下，将所有函数压缩到一个大代码块中，在其上运行Simplifier并生成没有中间列表的真正最优代码，这将是内联中的一个基本练习。但由于递归，这是行不通的。

您可以使用{-# RULE #-}杂注来修复其中的一些问题。例如，

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

现在，每次GHC看到map应用于map时，它都会将其压缩为对列表的单次传递，从而消除中间列表。

麻烦的是，这只适用于map，然后是map。还有许多其他的可能性-map后面跟着filter，filter后面跟着map，等等。发明了所谓的“流融合”，而不是为它们中的每一个手工编码解决方案。这是一个更复杂的技巧，我不会在这里描述。

总之，这些都是由那个程序员编写的特殊优化技巧。GHC本身对核聚变一无所知；这一切都在列表库和其他容器库中。因此，发生什么优化取决于您的容器库是如何编写的（或者，更现实地说，您选择使用哪些库）。

例如，如果您使用Haskell 98数组，则不要期望任何类型的融合。但我知道vector库具有广泛的融合功能。都是关于图书馆的。编译器只提供RULES编译指示。（顺便说一句，这是非常强大的。作为库的作者，您可以使用它来重写客户端代码！）

元：

我同意人们所说的“代码第一，配置文件第二，优化第三”。
我也同意人们所说的“对于给定的设计决策有多少成本，有一个心理模型是有用的”。

所有事物的平衡，以及所有..

小开

如果只在一个地方使用了let绑定V=RHS，那么即使RHS很大，您也可以依靠编译器来内联它。

唯一的例外（在当前问题的上下文中几乎不存在）是Lambdas，它有重复工作的风险。考虑：

let v = rhs
l = \x-> v + x
in map l [1..100]

在那里，内联V将是危险的，因为一个（句法）使用将转化为RHS的99个额外的评估。但是，在这种情况下，您也不太可能想要手动内联它。所以本质上你可以使用规则：

如果您考虑内联一个只出现一次的名称，编译器无论如何都会这样做。

作为一个令人愉快的推论，简单地使用字母绑定来分解长语句（希望获得清晰度）基本上是免费的。

这来自于 community.Haskell.org/~simonmar/papers/inline.PDF 它包含了更多关于内联的信息。