GHC 中函数参数的内联

Question

我试图找到 GHC 中发生的某种内联的源代码，其中内联作为参数传递给另一个函数的函数。例如，我可能会写如下定义（使用我自己的 List 类型以避免重写规则）：

data MyList a = Nil | Cons a (MyList a)
  deriving (Show)

mapMyList :: (a -> b) -> MyList a -> MyList b
mapMyList f Nil = Nil
mapMyList f (Cons a rest) = Cons (f a) $ mapMyList f rest

接听电话

fromList :: [a] -> MyList a
fromList = ...

main = do
  print $ mapMyList (*2) $ fromList [1..5]

mapMyList 是递归的，所以不能直接内联。但是，在生成的核心中，我看到以下定义：

Rec {
-- RHS size: {terms: 16, types: 11, coercions: 0, joins: 0/0}
Main.main_$smapMyList [Occ=LoopBreaker] :: MyList Int -> MyList Int
[GblId, Arity=1, Str=<S,1*U>, Unf=OtherCon []]
Main.main_$smapMyList
  = \ (sc_s2Rb :: MyList Int) ->
      case sc_s2Rb of {
        Nil -> Main.Nil @Int;
        Cons a_aBe rest_aBf ->
          Main.Cons
            @Int
            (case a_aBe of { GHC.Types.I# x_a24u ->
             GHC.Types.I# (GHC.Prim.*# x_a24u 2#)
             })
            (Main.main_$smapMyList rest_aBf)
      }
end Rec }

特别是smapMyList不再接受函数作为参数，(* 2)在这里被内联了。我想知道哪个优化过程正在生成这段代码，它是如何工作的？

我发现 this related issue，它似乎在寻求一种使用 SPECIALIZE pragma 来保证这种行为的方法，这让我相信专业化过程正在这样做。但是，在阅读有关 GHC 专业化的文档时，它似乎是针对类型类字典的专业化，而不是函数参数（在我的示例中没有类型类）。

我也看了static argument transformation which seems related; for example the GHC source关于通行证的说法：

May be seen as removing invariants from loops: Arguments of recursive functions that do not change in recursive calls are removed from the recursion, which is done locally and only passes the arguments which effectively change.

但是，我尝试使用 -fno-static-argument-transformation -fno-specialise 禁用这两个通道，发现这种转换仍然会发生。

我提出这个问题的动机是我正在用另一种语言 (Koka) 实现这种转换，所以我想了解其他语言是如何做到的。

Complete test program

Generated core（禁用特化和静态参数转换后）

Answer 1

优化被称为“调用模式特化”（a.k.a.SpecConstr），它根据应用参数来特化函数。论文 "Call-pattern specialisation for Haskell programs" by Simon Peyton Jones 中描述了优化。 GHC 中的当前实现在两个高度相关的方面与该论文中描述的不同：

SpecConstr 可以应用于同一模块中的任何调用，而不仅仅是单个定义内的递归调用。
SpecConstr 可以作为参数应用于函数，而不仅仅是构造函数。但是，它对 lambda 不起作用，除非它们因完全懒惰而浮出水面。

这是在没有这种优化的情况下生成的核心的相关部分，使用 -fno-spec-constr，并带有 -dsuppress-all -dsuppress-uniques -dno-typeable-binds 标志：

Rec {
mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a1 rest -> Cons (f a1) (mapMyList f rest)
      }
end Rec }

Rec {
main_go
  = \ x ->
      Cons
        (I# x)
        (case x of wild {
           __DEFAULT -> main_go (+# wild 1#);
           5# -> Nil
         })
end Rec }

main3 = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main2
  = $fShowMyList_$cshowsPrec
      $fShowInt $fShowMyList1 (mapMyList main3 (main_go 1#))

main1 = main2 []

main = hPutStr' stdout main1 True

我认为这个优化有点令人失望，因为它只适用于同一模块内的使用。还有，很长一段时间（自"Stream Fusion. From Lists to Streams to Nothing at All" paper from 2007) people have hoped that this optimization could optimize stream fusion. However, as I understand it, nobody has been able to make it work properly and reliably for that purpose (see this GHC issue）。所以现在我们还是在base中使用劣质的foldr/build融合

我开始讨论改善 this GHC issue. I think the most promising line of future work would be to improve the static argument transform optimization. See this comment by Sebastian Graf 现状的可能性。

我做了更多的调试，特别是我使用了 -dverbose-core2core 选项并检查了结果。正如我所料，优化是由于 SpecConstr 优化而发生的。这是 SpecConstr 之前的核心（在 Simplifier pass 之后）：

Rec {
mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a rest -> Cons (f a) (mapMyList f rest)
      }
end Rec }

lvl = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main
  = case toList (mapMyList lvl (fromList (eftInt 1# 5#))) of {
      ...

这是 SpecConstr 之后的核心：

Rec {
$smapMyList
  = \ sc ->
      case sc of {
        Nil -> Nil;
        Cons a rest -> Cons (lvl a) (mapMyList lvl rest)
      }

mapMyList
  = \ @ a @ b f ds ->
      case ds of {
        Nil -> Nil;
        Cons a rest -> Cons (f a) (mapMyList f rest)
      }
end Rec }

lvl = \ ds -> case ds of { I# x -> I# (*# x 2#) }

main
  = case toList (mapMyList lvl (fromList (eftInt 1# 5#))) of {
      ...

因此，您可以看到 SpecConstr 创建了 $smapMyList 函数，它是 mapMyList 的一个版本，专门用于 lvl 参数，即 *2 函数。

请注意，此专用函数尚未使用，它是使用新创建的重写规则完成的，该规则随后会在简化器运行时触发。如果您使用标志 -ddump-rule-rewrites，您可以看到它们的实际效果：

Rule fired
    Rule: SC:mapMyList0
    Module: (Main)
    Before: mapMyList TyArg Int TyArg Int ValArg lvl ValArg rest
    After:  (\ sc -> $smapMyList sc) rest
    Cont:   Stop[BoringCtxt] MyList Int
Rule fired
    Rule: SC:mapMyList0
    Module: (Main)
    Before: mapMyList
              TyArg Int TyArg Int ValArg lvl ValArg fromList (eftInt 1# 5#)
    After:  (\ sc -> $smapMyList sc) (fromList (eftInt 1# 5#))
    Cont:   StrictArg toList
            Select nodup wild
            Stop[RhsCtxt] String

这是后续 Simplifier pass 之后的核心（它也内联 lvl）：

Rec {
$smapMyList
  = \ sc ->
      case sc of {
        Nil -> Nil;
        Cons a rest ->
          Cons (case a of { I# x -> I# (*# x 2#) }) ($smapMyList rest)
      }
end Rec }

main
  = case toList ($smapMyList (fromList (eftInt 1# 5#))) of {
      ...

这也说明了此优化也需要完全惰性的原因：lvl 函数需要浮动，因为 SpecConstr 不适用于 lambda。这个飘出去需要十足的懒惰。

GHC 中函数参数的内联

Inlining of function parameters in GHC

haskell

ghc