GHC 깊이 들여다보기: Core를 대상으로
지난 블로그 글에서는 GHC 컴파일러에서 사용되는 중간 구조를 살펴보았습니다. 이번에는 Core 언어를 살펴봅시다.
**[Accompaying Source Code](https://github.com/sdiehl/dive-into-ghc/tree/master/03-core)**
Core
GHC에서 가장 핵심적인 데이터 타입입니다. Core는 System FC의 아주 작고 명시적으로 타입이 지정된 변형입니다. 이는 타입 위에서의 전칭 양화 메커니즘을 도입했다는 점에서 단순 타입 람다 대수와 다른 타입 있는 람다 대수이며, 이 전칭 양화는 대문자 람다 로 표기됩니다.
-- System-F Notation
Λ b c a. λ (f1 : b -> c) (g : a -> b) (x1 : a). f1 (g x1)
-- Haskell Core
\ (@ b) (@ c) (@ a) (f1 :: b -> c) (g :: a -> b) (x1 :: a) -> f1 (g x1)
Haskell 프런트엔드는 암묵적으로 타입이 지정되는 소스 언어이지만, Core는 명시적으로 타입이 지정되는 언어입니다. 모든 바인더는 명시적인 타입을 가지며, 항에는 명시적인 타입 추상화와 타입 적용이 포함됩니다.
GHCi에서 Core를 살펴보려면 다음 플래그와 다음 셸 별칭을 사용하여 호출할 수 있습니다. 표현을 읽기 쉽게 하려고 일부 메타데이터와 긴 형식의 이름이 출력되지 않도록 명시적으로 비활성화했습니다.
alias ghci-core="ghci -ddump-simpl -dsuppress-idinfo \
-dsuppress-coercions -dsuppress-type-applications \
-dsuppress-uniques -dsuppress-module-prefixes"
그러면 대화형 프롬프트에서 Core 표현을 대화식으로 탐색할 수 있습니다.
$ ghci-core
예를 들어 일반적인 식을 입력하고 그것이 Core로 어떻게 변환되는지 확인할 수 있습니다.
λ: let f x = x + 2 ; f :: Int -> Int
==================== Simplified expression ====================
returnIO
(: ((\ (x :: Int) -> + $fNumInt x (I# 2)) `cast` ...) ([]))
λ: let f x = (x, x)
==================== Simplified expression ====================
returnIO (: ((\ (@ t) (x :: t) -> (x, x)) `cast` ...) ([]))
Core 구문
Core는 CoreSyn 모듈에 정의되어 있습니다. 중심이 되는 데이터 타입은 Expr이며, 이 타입은 모든 Haskell 표현식을 압축하여 나타낼 수 있는 10가지 Core 데이터 타입을 담고 있습니다.
data Expr b
= Var Id
| Lit Literal
| App (Expr b) (Arg b)
| Lam b (Expr b)
| Let (Bind b) (Expr b)
| Case (Expr b) b Type [Alt b]
| Cast (Expr b) Coercion
| Tick (Tickish Id) (Expr b)
| Type Type
| Coercion Coercion
Core의 패턴 매치 로직은 생성자의 최대 한 갈래만을 판별하는 여러 데이터 타입으로 나뉩니다. 프런트엔드의 case 문을 Core의 case 문으로 변환하는 과정에서는 패턴 매치를 case들의 “분할 트리“로 펼치는 과정을 거칩니다. 와일드카드 패턴 매치에 해당하는 case는 (DEFAULT, [], rhs)입니다.
type Arg b = Expr b
type Alt b = (AltCon, [b], Expr b)
data AltCon
= DataAlt DataCon
| LitAlt Literal
| DEFAULT
특히 모든 타입에는 바인더의 타입을 나타내는 매개변수 b가 있습니다. 바인더 타입은 재귀 바인더와 비재귀 바인더를 포함하는 합 타입입니다. 상호 재귀적인 바인딩은 바인더의 리스트로 인코딩됩니다.
data Bind b
= NonRec b (Expr b)
| Rec [(b, (Expr b))]
예를 들어 팩토리얼 함수는 다음과 같습니다.
fac :: Int -> Int -> Int
fac a 0 = a
fac a n = fac (n*a) (n-1)
… 이 함수는 Core 바인더로 펼쳐지며 재귀 바인딩 안에 감싸집니다.
Rec {
fac :: Int -> Int -> Int
fac =
\ (a :: Int) (ds :: Int) ->
case ds of wild { I# ds1 ->
case ds1 of _ {
__DEFAULT ->
fac (* @ Int $fNumInt wild a) (- @ Int $fNumInt wild (I# 1));
0 -> a
}
}
end Rec }
CoreSyn 모듈은 바인더 매개변수를 펼쳐 편리하게 쓸 수 있도록 한 타입 동의어를 여러 개 제공합니다.
type TyVar = Var
type CoreExpr = Expr Var
type CoreBndr = Var
type CoreBind = Bind CoreBndr
type CoreProgram = [CoreBind]
덧붙이자면, Haskell 구문의 타이핑 판단을 다루는 논문에서 쓰이는 표기법은 일반적으로 다음 관례를 따르며, Expr에 있는 각 Haskell 데이터 타입과 일대일로 대응합니다.
Var
Var 타입은 대부분의 Core 정의에서 중심이 되는 타입이며, 컴파일러의 후반부에서 사용되는 주된 이름 타입입니다. 이 타입은 Id 타입의 동의어이지만 추가로 타입 변수를 포함할 수도 있습니다.
data Var
-- Type and kind variables
= TyVar
{ varName :: Name
, realUnique :: FastInt
, varType :: Kind
}
-- Internal type variables used by inference algorithm
| TcTyVar
{ varName :: Name
, realUnique :: FastInt
, varType :: Kind
, tc_tv_details :: TcTyVarDetails
}
-- Value level identifiers
| Id
{ varName :: !Name
, realUnique :: FastInt
, varType :: Type
, idScope :: IdScope
, id_details :: IdDetails
, id_info :: IdInfo
}
Var의 필드에는 식별자의 출처를 나타내는 중요한 타입도 들어 있습니다. LocalId는 람다, case, let 바인딩과 같은 식 안에서 바인딩됩니다. GlobalId는 최상위 식이거나 임포트된 데이터 생성자, 클래스 등입니다.
data IdScope
= GlobalId
| LocalId ExportFlag
스코프 외에도 식별자의 사용 방식과 유형에 대한 추가 정보를 제공하는 두 가지 메타데이터 레코드가 있습니다. 바로 IdInfo와 IdDetails입니다. IdDetails는 주로 변수가 왜 도입되었는지에 대한 정보를 담고 있으며, IdInfo는 core에서 core로의 패스 동안 적용될 수 있는 최적화에 관한 메타데이터를 담고 있습니다.
data IdDetails
= VanillaId
| RecSelId {sel_tycon :: TyCon, sel_naughty :: Bool}
| DataConWorkId DataCon.DataCon
| DataConWrapId DataCon.DataCon
| ClassOpId Class.Class
| PrimOpId PrimOp.PrimOp
| FCallId ForeignCall.ForeignCall
| TickBoxOpId TickBoxOp
| DFunId Int Bool
IdInfo의 구조는 플래그들의 집합입니다.
data IdInfo = IdInfo
{ arityInfo :: ArityInfo
, specInfo :: SpecInfo
, unfoldingInfo :: Unfolding
, cafInfo :: CafInfo
, oneShotInfo :: OneShotInfo
, inlinePragInfo :: InlinePragma
, occInfo :: OccInfo
, strictnessInfo :: StrictSig
, demandInfo :: Demand
, callArityInfo :: !ArityInfo
}
우리가 구성할 식별자들은 단순히 람다 식과 최상위 함수에서 나온 것이므로, 기본(vanilla) 형태의 id를 그대로 사용하겠습니다.
vanillaIdInfo :: IdInfo
vanillaIdInfo = IdInfo
{ cafInfo = vanillaCafInfo,
, arityInfo = unknownArity,
, specInfo = emptySpecInfo,
, unfoldingInfo = noUnfolding,
, oneShotInfo = NoOneShotInfo,
, inlinePragInfo = defaultInlinePragma,
, occInfo = NoOccInfo,
, demandInfo = topDmd,
, strictnessInfo = nopSig,
, callArityInfo = unknownArity
}
이름에 이 메타데이터와 타입을 결합하면 Id/Var가 고유하게 구성되며, 이들을 함께 결합해 주는 여러 헬퍼 함수가 있습니다.
mkTyVar :: Name -> Kind -> TyVar
mkLocalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
mkGlobalVar :: IdDetails -> Name -> Type -> IdInfo -> Id
예제
다음과 같은 아주 간단한 모듈을 생각해 봅시다.
module Example (f) where
f :: a -> a
f x = x
앞서 언급한 함수들을 사용하여 Core 구성 요소로 이 모듈을 다시 만들어 봅시다. 여기서는 mkUnique를 사용해 다소 억지스러운 방식으로 고유 값 공급(unique supply)을 흉내 내겠지만, 실제로는 이렇게 하지 말고 IO 안에서 공급을 초기화하면 됩니다.
mkName :: Int -> String -> Name
mkName i n = mkInternalName (mkUnique 'n' i) (mkOccName OccName.varName n) noSrcSpan
xn :: Name
xn = mkName 0 "x"
an :: Name
an = mkName 1 "a"
fn :: Name
fn = mkExternalName (mkUnique 'n' 2) modl (mkOccName OccName.varName "f") noSrcSpan
-- a :: *
a :: TyVar
a = mkTyVar an anyKind
-- x :: a
x :: Var
x = mkLocalVar VanillaId xn (TyVarTy a) vanillaIdInfo
-- f :: a -> a
fv :: Var
fv = mkGlobalVar VanillaId fn (FunTy (TyVarTy a) (TyVarTy a)) vanillaIdInfo
def :: [Syn.CoreBind]
def = [Syn.NonRec fv f]
f :: Syn.Expr Var
f = Syn.Lam x (Syn.Var x)
modl :: Module
modl = mkModule mainPackageKey (mkModuleName "Example")
이제 타입 검사 이후 컴파일러의 전반부에서 얻는 것과 똑같이 ModGuts와 ModSummary로 묶을 수 있는 합성 Core 모듈이 생겼습니다. 이 필드들 대부분은 기본 더미 값으로 초기화하기만 하면 됩니다.
guts :: ModGuts
guts = ModGuts
{
mg_module = modl,
mg_exports = [Avail fn],
mg_deps = noDependencies,
mg_dir_imps = emptyModuleEnv,
mg_used_names = mkNameSet [fn],
mg_used_th = False,
mg_rdr_env = emptyGlobalRdrEnv,
mg_fix_env = emptyFixityEnv,
mg_tcs = [],
mg_insts = [],
mg_fam_insts = [],
mg_patsyns = [],
mg_rules = [],
mg_binds = def, -- our binding
mg_foreign = NoStubs,
mg_warns = NoWarnings,
mg_hpc_info = NoHpcInfo False,
mg_modBreaks = emptyModBreaks,
mg_vect_decls = [],
mg_vect_info = noVectInfo,
mg_boot = False,
mg_anns = [],
mg_inst_env = emptyInstEnv,
mg_fam_inst_env = emptyFamInstEnv,
mg_safe_haskell = Sf_None,
mg_trust_pkg = False,
mg_dependent_files = []
}
summ :: DynFlags -> ModSummary
summ dflags = ModSummary
{
ms_mod = modl,
ms_hsc_src = HsSrcFile,
ms_location = ModLocation {
ml_hs_file = Nothing
, ml_hi_file = "Example.hi"
, ml_obj_file = "Example.o"
},
ms_hs_date = UTCTime (toEnum 0) 0,
ms_obj_date = Nothing,
ms_iface_date = Nothing,
ms_srcimps = [],
ms_textual_imps = [],
ms_hspp_file = "Example.hs",
ms_hspp_opts = dflags,
ms_hspp_buf = Nothing
}
코드 생성
이제 합성 core 모듈이 준비되었으므로, 여기에 일반 컴파일러 파이프라인을 실행하여 소스 코드를 컴파일할 때와 똑같이 컴파일할 수 있습니다. Core를 네이티브 코드로 변환하는 과정은 여러 단계를 거칩니다.
주요 패스는 Simplifier라고 불리며, Core를 Core로 매핑합니다. 이 패스의 역할은 더 효율적인 프로그램을 만들어 내는 것을 목표로, 정확성을 보존하는 수많은 변환을 수행하는 것입니다.
- 상수 폴딩
- 재작성 규칙 적용
- 인라이닝
- case-of-case 최적화
- 알려진 생성자에 대한 case 최적화
- 에타 확장과 에타 축소
최적화 외에도 GHC에는 Core Linter라는 패스가 있으며, 이 패스는 주어진 Core 프로그램에 대해 다양한 내부 일관성 검사를 수행합니다. Core는 명시적으로 타입이 지정되어 있으므로, 식별자의 타입이 바인딩과 일치하는지, 그리고 타입들이 내부적으로 일관적인지만 확인하면 되기 때문에 주어진 프로그램의 타입 검사는 간단합니다. Core linter는 Core를 변환하는 최적화 패스를 작성하거나 (기본 Haskell이 아닌) 다른 언어에서 Core를 대상으로 삼는 경우에 매우 유용합니다. linter 패스는 수많은 버그가 코드 생성 오류로 드러나기 전에 이를 미리 막아 줄 수 있습니다.
이제 나머지 컴파일러 파이프라인을 실행하여 모듈에서 어셈블리 코드를 생성하겠습니다. 타입 간 변환에 약간 번거로운 절차가 따르지만, 이 과정은 기본적으로 위의 패스들의 입력과 출력을 서로 연결하는 것에 불과합니다.
main :: IO ()
main = runGhc (Just libdir) $ do
dflags <- getSessionDynFlags
setSessionDynFlags $ dflags { hscTarget = HscAsm, ghcLink = LinkBinary }
dflags <- getSessionDynFlags
env <- getSession
setTargets [Target
{ targetId = TargetModule (mkModuleName "Example")
, targetAllowObjCode = True
, targetContents = Nothing }]
-- repares for code generation.
prep <- liftIO $ corePrepPgm env (ms_location (summ dflags)) (mg_binds guts) (mg_tcs guts)
-- Transform Core into STG
stg <- liftIO $ coreToStg dflags (mg_module guts) prep
-- STG Transformer
(stg_binds2, cost_centre_info) <- liftIO $ stg2stg dflags (mg_module guts) stg
-- Generated Cmm
let cmms = codeGen dflags (mg_module guts) (mg_tcs guts) cost_centre_info stg_binds2 (mg_hpc_info guts)
-- Initialize a name supply for the Cmm pipeline
us <- liftIO $ mkSplitUniqSupply 'S'
let initTopSRT = initUs_ us emptySRT
run_pipeline = cmmPipeline env
-- Collect the Cmm code stream after running the pipeline.
let cmmstream = do
a <- Stream.mapAccumL run_pipeline initTopSRT cmms
Stream.yield (srtToData a)
-- Prepare the Cmm for
genraw <- liftIO $ cmmToRawCmm dflags cmmstream
-- Initialize name supply for the native code generator and generate x86 to a
-- file from the prepared Cmm.
ncg_uniqs <- liftIO $ mkSplitUniqSupply 'n'
fname <- liftIO $ (openFile "Example.asm" WriteMode)
liftIO $ nativeCodeGen dflags (mg_module guts) modloc fname ncg_uniqs genraw
-- Dump the outputted Stg and Cmm out
gen <- liftIO $ Stream.collect cmmstream
liftIO $ putStrLn "=== STG ==="
liftIO $ putStrLn $ showGhc stg_binds2
liftIO $ putStrLn "=== CMM ==="
liftIO $ putStrLn $ showGhc gen
그러면 합성한 Core 모듈로부터 Example.asm 파일이 출력됩니다. 다음 단계의 프로젝트로는 더 복잡한 언어가 GHC Core를 타깃으로 삼도록 하여 GHC의 컴파일러 최적화와 네이티브 코드 생성을 활용하는 것을 생각해 볼 수 있습니다.