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

This GHC Trac page 也很好地解释了通行证。 This page 解释了优化顺序，但与 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: 到最后一个发生的所有优化阶段，我们看到了很多。

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

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

专业化 专业化的基本思想是通过识别调用函数的位置并创建非多态函数的版本来消除多态性和重载——它们特定于调用它们的类型。您还可以使用 SPECIALIZE 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) ，下面提到的规则可以触发，你最终会得到一些在未装箱的 Ints 上工作的东西，这比原来的要快得多。另一种看待专业化的方法是对类型类字典和类型变量的部分应用。这里的源代码中有很多注释。

浮动编辑：我之前显然误解了这一点。我的解释已经完全改变了。其基本思想是将不应重复的计算移出函数。例如，假设我们有这样的： \x -> let y = 昂贵的 x+y 在上面的 lambda 中，每次调用函数时，都会重新计算 y。浮动产生的更好的函数是 let y = 昂贵的 \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 同样，重复计算被保存。在这种情况下，源代码非常易读。目前，两个相邻 lambda 之间的绑定没有浮动。例如，这不会发生： \xy -> let t = x+x in ... 去 \x -> let t = x+x in \y -> ...

Float inwards 引用源码，floatInwards的主要目的是浮动到一个case的分支中，这样我们就不用分配东西了，保存在栈上，然后发现在选择的分支中不需要它们。举个例子，假设我们有这个表达式： 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 这篇论文虽然涵盖了其他主题，但给出了相当清晰的介绍。请注意，尽管它们的名称不同，但 float in 和 float out 不会进入无限循环，原因有两个：Float in floats 允许进入 case 语句，而 float out 处理函数。传球的顺序是固定的，所以它们不应该无限交替。

浮点数中的浮点数允许进入案例语句，而浮点数处理函数。

传球的顺序是固定的，所以它们不应该无限交替。

需求分析 需求分析或严格性分析与其说是一种转换，不如说更像是一种信息收集过程。编译器找到总是评估其参数（或至少其中一些）的函数，并使用按值调用而不是按需要调用来传递这些参数。由于您可以避免 thunk 的开销，因此这通常要快得多。 Haskell 中的许多性能问题要么是由于此传递失败，要么是代码不够严格。一个简单的例子是使用 foldr、foldl 和 foldl' 对整数列表求和之间的区别——第一个导致堆栈溢出，第二个导致堆溢出，最后一个由于严格性而运行良好。这可能是所有这些中最容易理解和最好记录的。我相信多态性和 CPS 代码经常会打败这一点。

Worker Wrapper 绑定 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 转换在它可以做的事情上是非常通用的。

Common sub-expression 这是另一个非常简单但非常有效的优化，例如严格性分析。基本思想是，如果您有两个相同的表达式，它们将具有相同的值。例如，如果 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 = fxz = g (fx) y 但是，如果您通过 llvm 编译，由于其全局值编号传递，您可能会得到其中的一些组合。

Liberate case 这似乎是一个非常有记录的转换，除了它可能导致代码爆炸的事实。这是我找到的小文档的重新格式化（并稍微重写）版本：这个模块遍历核心，并在自由变量上寻找案例。标准是：如果在到递归调用的路由上的自由变量上存在 case，则递归调用被展开替换。例如，在 f = \ t -> case v of V ab -> a : ft 中，内部 f 被替换。使 f = \ t -> case v of V ab -> a : (letrec f = \ t -> case v of V ab -> a : ft in f) t 注意阴影的需要。简化，我们得到 f = \ t -> case v of V ab -> a : (letrec f = \ t -> a : ft in ft) 这是更好的代码，因为 a 在内部 letrec 中是自由的，而不是需要v 的投影。注意这处理自由变量，不像 SpecConstr 处理已知形式的参数。有关 SpecConstr 的更多信息，请参见下文。

SpecConstr - 这将 f (Left x) y = somthingComplicated1 f (Right x) y = somethingComplicated2 转换为 f_Left xy = somethingComplicated1 f_Right xy = somethingComplicated2 {-# INLINE f #-} f (Left x) = f_Left xf (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 由许多启发式方法控制。论文中提到的那些是这样的：lambdas 是显式的，arity 是 a。右侧是“足够小”，由旗帜控制。该函数是递归的，并且在右侧使用了可特化的调用。该函数的所有参数都存在。至少其中一个参数是构造函数应用程序。该论点在函数的某处进行了案例分析。然而，启发式方法几乎肯定发生了变化。事实上，该论文提到了另一种第六启发式方法：仅当 x 仅通过案例仔细检查且未传递给普通函数或作为结果的一部分返回时，才专门处理参数 x。

lambdas 是显式的，arity 是 a。

右侧是“足够小”，由旗帜控制。

该函数是递归的，并且在右侧使用了可特化的调用。

该函数的所有参数都存在。

至少其中一个参数是构造函数应用程序。

该论点在函数的某处进行了案例分析。

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

---

懒惰

这不是“编译器优化”，而是语言规范保证的东西，所以你总是可以指望它发生。从本质上讲，这意味着在您对结果“做某事”之前不会执行工作。 （除非你做了几件事中的一件来故意关闭懒惰。）

显然，这本身就是一个完整的主题，SO 已经有很多关于它的问题和答案。

以我有限的经验，让你的代码太懒或太严格会比我要谈论的任何其他事情产生更大的性能损失（在时间和空间上）......

严格性分析

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

很明显，问题在于编译器不能总是检测到什么时候可以变得严格。有时您需要给编译器一些提示。 （除了涉足核心输出之外，我不知道有任何简单的方法可以确定严格性分析是否完成了您认为的工作。）

内联

如果您调用一个函数，并且编译器可以判断您正在调用哪个函数，它可能会尝试“内联”该函数 - 即用函数本身的副本替换函数调用。函数调用的开销通常非常小，但内联通常可以实现其他不会发生的优化，因此内联可能是一个巨大的胜利。

仅当函数“足够小”（或者如果您添加专门要求内联的编译指示）时，函数才会被内联。此外，只有在编译器可以判断您正在调用的函数时，才能内联函数。编译器可能无法分辨出两种主要方式：

如果您调用的函数是从其他地方传入的。例如，编译过滤器函数时，您不能内联过滤器谓词，因为它是用户提供的参数。

如果您正在调用的函数是类方法并且编译器不知道所涉及的类型。例如，编译 sum 函数时，编译器不能内联 + 函数，因为 sum 可以处理几种不同的数字类型，每种类型都有不同的 + 函数。

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

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

公共子表达式消除

如果某个代码块两次计算相同的值，编译器可能会用相同计算的单个实例替换它。例如，如果你这样做

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

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

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

您可能希望编译器总是这样做。然而，显然在某些情况下，这可能会导致性能更差，而不是更好，因此 GHC 并不总是这样做。坦率地说，我不太了解这背后的细节。但最重要的是，如果这种转换对您很重要，那么手动进行并不难。 （如果它不重要，你为什么要担心它？）

案例表达式

考虑以下：

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

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

问题是，这些函数中的大多数都是递归的。如果没有递归，内联将所有函数压缩到一个大代码块中，在其上运行简化器并生成没有中间列表的真正优化代码，这将是一项基本的练习。但是由于递归，这行不通。

您可以使用 {-# 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 次额外评估。但是，在这种情况下，您也不太可能希望手动内联它。所以基本上你可以使用规则：

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

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

这来自 community.haskell.org/~simonmar/papers/inline.pdf，其中包含更多关于内联的信息。

---