小编典典

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

all

GHC 有很多可以执行的优化,但我不知道它们都是什么,也不知道它们执行的可能性有多大以及在什么情况下执行。

我的问题是:我可以期望它每次或几乎都应用哪些转换?如果我看到一段将被频繁执行(评估)的代码,我的第一个想法是“嗯,也许我应该优化它”,在这种情况下,我的第二个想法应该是,“别想了,
GHC 得到这个”?

我正在阅读论文Stream Fusion: From Lists to Streams to Nothing at
All
,他们使用的将列表处理重写为不同形式的技术,GHC
的正常优化随后将可靠地优化为简单的循环,这对我来说是新颖的。我如何判断我自己的程序何时有资格进行这种优化?

GHC
手册中有一些信息,但它只是回答问题的一部分。

编辑:我开始赏金了。我想要的是一个低级转换的列表,例如 lambda/let/case-
floating、类型/构造函数/函数参数专业化、严格性分析和拆箱、worker/wrapper,以及我遗漏的其他任何重要的 GHC
转换,以及输入和输出代码的解释和示例,以及理想情况下的总体效果大于其部分总和的情况说明。理想情况下,会提及何时 不会进行转换
发生。我不期望对每个转换都进行新颖的解释,几句话和内联的单行代码示例就足够了(或者一个链接,如果不是二十页的科学论文),只要大局是到最后就清楚了。我希望能够查看一段代码,并能够很好地猜测它是否会编译成一个紧密的循环,或者为什么不编译,或者我必须改变什么来实现它。(我对像流融合这样的大型优化框架不太感兴趣(我刚刚读过一篇关于它的论文);更多的是
编写 这些框架的人所拥有的知识。)


阅读 83

收藏
2022-07-13

共1个答案

小编典典

这个 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:到最后,所有优化阶段都发生在这里,我们看到了很多。

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

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

  • 专精

特化的基本思想是通过识别调用函数的位置并创建非多态函数的版本来消除多态性和重载——它们特定于调用它们的类型。您还可以使用编译指示告诉编译器执行此操作SPECIALISE。以阶乘函数为例:

     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)

接下来,下面提到的规则可以触发,你最终会得到一些在 unboxed Ints
上工作的东西,这比原来的要快得多。另一种看待专业化的方法是对类型类字典和类型变量的部分应用。

这里的源代码中有很多注释。

  • 浮出水面

编辑:我之前显然误解了这一点。我的解释已经完全改变了。

其基本思想是将不应重复的计算移出函数。例如,假设我们有这个:

     \x -> let y = expensive in x+y

在上面的 lambda 中,每次调用函数时,y都会重新计算。浮动产生的更好的功能是

     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

同样,节省了重复计算。

在这种情况下,源代码非常易读。

目前两个相邻 lambda 之间的绑定没有浮动。例如,这不会发生:

     \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,这可能是一些很大的麻烦,我们浪费了时间和空间。向内浮动解决了这个问题,产生了这个:

     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. 浮点数中的浮点数允许进入`case`语句,而浮点数处理函数。
2. 传球的顺序是固定的,所以它们不应该无限交替。
  • 需求分析

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

  • Worker Wrapper 绑定

worker/wrapper
转换的基本思想是在一个简单的结构上做一个紧密的循环,在末端转换到该结构并从该结构转换。例如,使用这个函数,它计算一个数字的阶乘。

     factorial :: Int -> Int
 factorial 0 = 1
 factorial n = n * factorial (n - 1)

使用IntGHC 中的定义,我们有

     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 完成,但是工人/包装器的转换在它可以做的事情上是非常普遍的。

  • 公共子表达式

这是另一个非常简单但非常有效的优化,例如严格性分析。基本思想是,如果您有两个相同的表达式,它们将具有相同的值。例如,如果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. lambdas 是显式的,arity 是`a`.
2. 右侧是“足够小”,由旗帜控制。
3. 该函数是递归的,并且在右侧使用了可特化的调用。
4. 该函数的所有参数都存在。
5. 至少其中一个参数是构造函数应用程序。
6. 该论点在函数的某处进行了案例分析。

然而,启发式方法几乎肯定发生了变化。事实上,该论文提到了另一种第六启发式:

x仅当x仅由 a 审查并且未传递给普通函数或作为结果的一部分返回 时才 专门处理参数。case

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

2022-07-13