PR

インライン化のタイミングを制御

 インライン化のタイミングは,書き換え規則を使ったプログラムの効率化に影響することがあります。例を見てみましょう。

 前回,中間データ構造を除去するための融合変換の一つである「fold/build」という手法を紹介しました。この手法では,リストを扱う演算を「build関数を使って定義した優良生産者」と「foldr関数を使って定義した優良消費者」として再定義します。そして,優良生産者と優良消費者の間に出てくる「foldr k z (build g)」という式を"fold/build"規則を使って「g k z」というbuildやfoldrを使わない形式に変換します。これにより,優良生産者と優良消費者の間で作成される中間データ構造を除去します。

{-# RULES
"fold/build"    forall k z (g::forall b. (a->b->b) -> b -> b) . 
                foldr k z (build g) = g k z
~ 略 ~
 #-}

 ところが,"fold/build"規則が適用される前にfoldrやbuildがインライン化されると,"fold/build"規則が適用されなくなってしまいます。この問題を回避するには,"fold/build"規則が適用される前にfoldrやbuildがインライン化されるのを防がなければなりません。

 NOINLINE指示文を使えば,foldrやbuildのインライン化を防ぐことはできます。しかし,これではいかなる場合でもfoldrやbuildがインライン化されなくなってしまいます。foldrやbuildをインライン化するほうがプログラムを効率化できる場合もあるため,NOINLINE指示文を使うのは不適切です。

 段階制御を使えば,この問題を解決できます。GHCでは「インライン化や書き換え規則の適用を有効・無効にするタイミング」を制御できるよう,単純化器の実行を複数の「フェーズ(phase,段階)」に分けています。段階制御を使えば,どのフェーズでインライン化や書き換え規則の適用を有効・無効にするかを設定できます。

 では,foldrとbuildのそれぞれの定義を見てみましょう。

foldr            :: (a -> b -> b) -> b -> [a] -> b
~ 略 ~
{-# INLINE [0] foldr #-}
-- Inline only in the final stage, after the foldr/cons rule has had a chance
-- Also note that we inline it when it has *two* parameters, which are the 
-- ones we are keen about specialising!
foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

build   :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
{-# INLINE [1] build #-}
~ 略 ~
build g = g (:) []

 INLINE指示文の中で「[]」に囲まれた部分が段階制御です。[1]や[0]のように数字を記述することで,インライン化を有効にするタイミングを設定します。例えば,[1]と指定すると,フェーズ1以降でインライン化が有効になります。フェーズ1でインライン化を行うという意味ではないので注意してください。

 逆にインライン化を無効にするタイミングを指定したい場合には,[~1]や[~0]のように数字の前に「~」を付けます。

 段階制御で指定する数字の具体的な意味を知るため,単純化器のフェーズを調べてみましょう。単純化器を使った最適化を行っているのは,GHCの「SimplCoreパス」と呼ばれる部分です。SimplCoreパスは「コア言語から,より最適化されたコア言語への変換を行うパス(Core-to-Core pass)」になっており,SimplCoreパスで行われる「コアからコアへの変換を行うパス」はcore2core関数にまとめられています。つまり,core2core関数の実装をたどっていけば,単純化器のフェーズを知ることができます(参考リンク1参考リンク2参考リンク3)。

core2core :: HscEnv
          -> ModGuts
          -> IO ModGuts
core2core hsc_env guts = do
    let dflags = hsc_dflags hsc_env
    us <- mkSplitUniqSupply 's'
    let (cp_us, ru_us) = splitUniqSupply us
    -- COMPUTE THE ANNOTATIONS TO USE
    ann_env <- prepareAnnotations hsc_env (Just guts)
    -- COMPUTE THE RULE BASE TO USE
    (imp_rule_base, guts1) <- prepareRules hsc_env guts ru_us
    ~ 略 ~
    let mod = mg_module guts
    (guts2, stats) <- runCoreM hsc_env ann_env imp_rule_base cp_us mod $ do
        -- FIND BUILT-IN PASSES
        let builtin_core_todos = getCoreToDo dflags
        -- DO THE BUSINESS
        doCorePasses builtin_core_todos guts1
    Err.dumpIfSet_dyn dflags Opt_D_dump_simpl_stats
        "Grand total simplifier statistics"
        (pprSimplCount stats)
    return guts2

type CorePass = CoreToDo
~ 略 ~
doCorePasses :: [CorePass] -> ModGuts -> CoreM ModGuts
doCorePasses passes guts = foldM (flip doCorePass) guts passes

 core2coreでは,getCoreToDo関数でCorePassのリストを作成し,doCorePassesでCorePassを実行します。doCorePassesは,リスト中のCorePassを先頭から順に実行するようにfoldMで定義されています。したがって,getCoreToDoで作成されるリストの順序が,そのままGHCでの単純化器を使った最適化の実行順序になります。

 ではgetCoreToDoの定義を見てみましょう。

getCoreToDo :: DynFlags -> [CoreToDo]
getCoreToDo dflags
  | Just todo <- coreToDo dflags = todo -- set explicitly by user
  | otherwise = core_todo
  where
    opt_level     = optLevel dflags
    phases        = simplPhases dflags
    max_iter      = maxSimplIterations dflags
    ~ 略 ~
    maybe_rule_check phase = runMaybe rule_check (CoreDoRuleCheck phase)
    simpl_phase phase names iter
      = CoreDoPasses
          [ CoreDoSimplify (SimplPhase phase names) [
              MaxSimplifierIterations iter
            ],
            maybe_rule_check phase
          ]
    ~ 略 ~
                -- By default, we have 2 phases before phase 0.
                -- Want to run with inline phase 2 after the specialiser to give
                -- maximum chance for fusion to work before we inline build/augment
                -- in phase 1.  This made a difference in 'ansi' where an
                -- overloaded function wasn't inlined till too late.
                -- Need phase 1 so that build/augment get
                -- inlined.  I found that spectral/hartel/genfft lost some useful
                -- strictness in the function sumcode' if augment is not inlined
                -- before strictness analysis runs
    simpl_phases = CoreDoPasses [ simpl_phase phase ["main"] max_iter
                                  | phase <- [phases, phases-1 .. 1] ]

        -- initial simplify: mk specialiser happy: minimum effort please
    simpl_gently = CoreDoSimplify SimplGently [
            ~ 略 ~
            NoCaseOfCase,       -- Don't do case-of-case transformations.
                                -- This makes full laziness work better
            MaxSimplifierIterations max_iter
        ]
    ~ 略 ~
    core_todo =
     if opt_level == 0 then
       [vectorisation,
        simpl_phase 0 ["final"] max_iter]
     else {- opt_level >= 1 -} [
        ~ 略 ~
        -- initial simplify: mk specialiser happy: minimum effort please
        simpl_gently,
        ~ 略 ~
        simpl_phases,
                -- Phase 0: allow all Ids to be inlined now
        ~ 略 ~
        simpl_phase 0 ["main"] (max max_iter 3),
    ~ 略 ~
        -- Final clean-up simplification:
        simpl_phase 0 ["final"] max_iter
     ]

defaultDynFlags :: DynFlags
defaultDynFlags =
     DynFlags {
        ~ 略 ~
        coreToDo                = Nothing,
        stgToDo                 = Nothing,
        ~ 略 ~
      }

 getCoreToDoの中の「| Just todo <- coreToDo dflags = todo」では,「パターン・ガード(Pattern Guards)」という拡張機能が使われています。GHCで-X*オプションやLANGUAGE指示文を使ってPatternGuardsを指定することで,この拡張機能を利用できます(参考リンク)。またこの拡張機能は,Haskellの新標準であるHaskell 2010で追加される予定です(参考リンク)。

 パターン・ガードは,ガード節の内部で「リストの内包表記のような記述と変数束縛」を可能にするものです。「| Just todo <- coreToDo dflags = todo」は,「DynFlags型の変数であるdflagsのcoreToDoフィールドがJustである場合に,Justで包まれた値をtodoに束縛し,それからtodoを返す」という定義になっています。dflagsのcoreToDoフィールドがJustでない場合には,getCoreToDo関数の他のガード節が使われます。getCoreToDoでは,他のガード節はotherwiseしかないので,dflagsのcoreToDoフィールドがJustでない場合にはcore_todoを返します。

 DynFlags型のデフォルトの値を定義しているdefaultDynFlags変数を見ると,coreToDoフィールドはNothingになっています。したがってgetCoreToDoのコメントにもあるように,プログラマが特別な操作をしない限り,getCoreToDoはcore_todoとして評価されます。今回は,このデフォルトの動作だけを見れば十分です。