core2core

まあ、よい機会なので少しCore Simplifierがどんな感じなのか概観してみることに。以下の話は、GHC-6.6のソースに基づいている。GHC compilerの中核は、main/HscMain.lhsに記述されている。hscSimplifyとか見ると、実質的にcore2coreを読んでいるだけなので、core2coreを見る。こいつは、SimplCore/SimplCore.lhsにある

core2core :: HscEnv
	  -> ModGuts
	  -> IO ModGuts

core2core hsc_env guts
  = do
        let dflags = hsc_dflags hsc_env
	    core_todos = getCoreToDo dflags

	us <- mkSplitUniqSupply 's'
	let (cp_us, ru_us) = splitUniqSupply us

		-- COMPUTE THE RULE BASE TO USE
	(imp_rule_base, guts') <- prepareRules hsc_env guts ru_us

		-- DO THE BUSINESS
	(stats, guts'') <- doCorePasses hsc_env imp_rule_base cp_us
			 		(zeroSimplCount dflags) 
					guts' core_todos

	dumpIfSet_dyn dflags Opt_D_dump_simpl_stats
		  "Grand total simplifier statistics"
		  (pprSimplCount stats)

	return guts''

まあ、よく分からんが、主要な処理は、getCoreToDoで、やるべき処理を決めて、使うRULESプラグマを用意するとかの前処理をして、doCorePassesでメイン処理。getCoreToDoは、main/DynFlags.lhsにあって、dflagsはコンパイラオプションに相当するデータ。

getCoreToDoが返すのは、[CoreToDo]型で、CoreToDoは、同じくDynFlags.lhsに

data CoreToDo		-- These are diff core-to-core passes,
			-- which may be invoked in any order,
  			-- as many times as you like.

  = CoreDoSimplify SimplifierMode [SimplifierSwitch]
  | CoreDoFloatInwards
  | CoreDoFloatOutwards FloatOutSwitches
  | CoreLiberateCase
  | CoreDoPrintCore
  | CoreDoStaticArgs
  | CoreDoStrictness
  | CoreDoWorkerWrapper
  | CoreDoSpecialising
  | CoreDoSpecConstr
  | CoreDoOldStrictness
  | CoreDoGlomBinds
  | CoreCSE
  | CoreDoRuleCheck Int{-CompilerPhase-} String	-- Check for non-application of rules 
						-- matching this string
  | CoreDoNothing 	 -- useful when building up lists of these things

とか、それっぽいのが並んでる。

doCorePassesは、CoreToDoリストの先頭から順に処理を行うだけ

doCorePasses :: HscEnv
             -> RuleBase        -- the imported main rule base
             -> UniqSupply      -- uniques
	     -> SimplCount      -- simplifier stats
             -> ModGuts	        -- local binds in (with rules attached)
             -> [CoreToDo]      -- which passes to do
             -> IO (SimplCount, ModGuts)

doCorePasses hsc_env rb us stats guts []
  = return (stats, guts)

doCorePasses hsc_env rb us stats guts (to_do : to_dos) 
  = do
	let (us1, us2) = splitUniqSupply us
	(stats1, guts1) <- doCorePass to_do hsc_env us1 rb guts
	doCorePasses hsc_env rb us2 (stats `plusSimplCount` stats1) guts1 to_dos

doCorePass (CoreDoSimplify mode sws)   = _scc_ "Simplify"      simplifyPgm mode sws
doCorePass CoreCSE		       = _scc_ "CommonSubExpr" trBinds  cseProgram
doCorePass CoreLiberateCase	       = _scc_ "LiberateCase"  trBinds  liberateCase
doCorePass CoreDoFloatInwards          = _scc_ "FloatInwards"  trBinds  floatInwards
doCorePass (CoreDoFloatOutwards f)     = _scc_ "FloatOutwards" trBindsU (floatOutwards f)
doCorePass CoreDoStaticArgs	       = _scc_ "StaticArgs"    trBinds  doStaticArgs
doCorePass CoreDoStrictness	       = _scc_ "Stranal"       trBinds  dmdAnalPgm
doCorePass CoreDoWorkerWrapper         = _scc_ "WorkWrap"      trBindsU wwTopBinds
doCorePass CoreDoSpecialising          = _scc_ "Specialise"    trBindsU specProgram
doCorePass CoreDoSpecConstr	       = _scc_ "SpecConstr"    trBindsU specConstrProgram
doCorePass CoreDoGlomBinds	       = trBinds glomBinds
doCorePass CoreDoPrintCore	       = observe printCore
doCorePass (CoreDoRuleCheck phase pat) = observe (ruleCheck phase pat)
doCorePass CoreDoNothing	       = observe (\ _ _ -> return ())

trBindsやtrBindsUは第一引数の関数に処理を丸投げしてるだけなのだけど、RuleBaseとかは全く使ってない。というわけで、simplifyPgmを見ようと思ったけど、微妙に長いのでやめた(ダメ

まあ、知りたかったのは、Core Simplifierがどういう順番で、最適化を行うかということで、それはgetCoreToDoが決める。普通に最適化オプション(-O)付けると、返ってくるCoreToDoリストは

[CoreDoSimplify SimplGently [NoCaseOfCase, MaxSimplifierIterations max_iter],

 CoreDoSpecialising,

 if full_laziness then CoreDoFloatOutwards (FloatOutSw False False) else CoreDoNothing,

 CoreDoFloatInwards,

 CoreDoSimplify (SimplPhase 2) [MaxSimplifierIterations max_iter],

 case rule_check of { Just pat -> CoreDoRuleCheck 2 pat; Nothing -> CoreDoNothing },

 CoreDoSimplify (SimplPhase 1) [MaxSimplifierIterations max_iter],

 case rule_check of { Just pat -> CoreDoRuleCheck 1 pat; Nothing -> CoreDoNothing },

 CoreDoSimplify (SimplPhase 0) [MaxSimplifierIterations 3],

 case rule_check of { Just pat -> CoreDoRuleCheck 0 pat; Nothing -> CoreDoNothing },

#ifdef OLD_STRICTNESS
 CoreDoOldStrictness
#endif

 if strictness then CoreDoStrictness else CoreDoNothing,

 CoreDoWorkerWrapper,

 CoreDoGlomBinds,

 CoreDoSimplify (SimplPhase 0) [MaxSimplifierIterations max_iter],

 if full_laziness then CoreDoFloatOutwards (FloatOutSw False True) else CoreDoNothing,

 if cse then CoreCSE else CoreDoNothing,

 CoreDoFloatInwards,

 case rule_check of { Just pat -> CoreDoRuleCheck 0 pat; Nothing -> CoreDoNothing },

 CoreDoSimplify (SimplPhase 0) [MaxSimplifierIterations max_iter]
]

という感じになっている。結局、"hylo In lengthNT out (hylo In (mapNT suc) out ls)"が最適化されないのは、何故なんだぜ？と、より一層疑問が深まっただけなのだった。普通にphase control付けないRULESプラグマはどこで処理されるんだろう。探すのめんどくせ

そして、よく読んだら、こういう話はOnoueのD論に全部書いてあった(だから、リンク張ったやつくらいちゃんと読もうよ＞私)

#どうでもいいけど、外人とか平気で、敬称なしで書いてるけど、日本人だとエライ違和感ある。「Onoueさん」と書きたくなってしまう。まあ、日本人でも、歴史上の人物とかは、地名みたいなもんで、特に敬意もわかないんだけど(織田信長とか、さん付けする人はあまりいない)。あと、教科書に名前が載ったり、定理名になったりするくらいの人は、私の中で歴史上の人物扱いになる(Knuthとかビル・ゲイツとかね)。ということから、エライ人に限って、さん付けされないという幾分奇妙な現象が起きる。けどまあ、エライ人に会うことはまずないのでいいのだ。エラくない人だと、新宿でばったり会って、お前何呼び捨てしてんねんとか因縁つけられる可能性が！(ありません)。まあ、うちから新宿行くには、一回乗換えが必要で面倒なので余り行かないのでセーフ。

ところで、

getCoreToDo dflags
  | Just todo <- coreToDo dflags = todo -- set explicitly by user
  | otherwise = core_todo
  where ...

となってるので、頑張ればコンパイラオプションで、最適化の順序を完全にユーザがコントロールできるんだろうか(そのうち調べるかもしれない)

GHCのExtCoreについて
http://citeseer.ist.psu.edu/tolmach01external.html
(あとで読む)