HaskellでLisp to LLVM IRコンパイラ その４ （SSA中間言語）

LLVM IRに落とし込む前のステップとして簡略化した独自のSSA中間言語に変換しておく、という話を前回した。

その中間言語の各行を表現するデータ型がこれ：

data SSA = Alloc String
         | Store String String
         | Load String String

Lispと違ってこの言語は再帰的ではない。つまり、一つの命令のなかに他の命令が含まれることはない。なのでこの中間言語は「命令のリスト」つまり[SSA]型をとる。

出力して確認したりしたいのでShow型クラスのインスタンス化しておく：

instance Show SSA where show = showSSA

showSSA :: SSA -> String
showSSA (Alloc s) = "alloc " ++ s ++ "\n"
showSSA (Store s n) = "store " ++ s ++ " " ++ n ++ "\n"
showSSA (Load a s) = "load " ++ a ++ " " ++ s ++ "\n"

手書きで作ったテストファイルをLLVM IRに変換して結果を見たりしたいのでパーサも用意する：

readSSA :: String -> [SSA]
readSSA input = case parse parseSSAs "ssa" input of
  Left err  -> error $ "SSA parse failed: " ++ show err
  Right ssa -> ssa

REPLだとパースエラーもちゃんと処理してエラー表示してまたIOに戻るが、コンパイラなのでパースエラーがあったら例外投げて停止するだけで楽。この段階で型情報にEitherモナドとかいれなくてすむのはありがたい。

parseSSAs :: Parser [SSA]
parseSSAs = endBy parseSSA (char '\n')

parseSSA :: Parser SSA
parseSSA = parseAlloc 
       <|> parseStore 
       <|> parseLoad

parseAlloc :: Parser SSA
parseAlloc = do 
  try (string "alloc")
  skipMany1 space
  s <- parseVar
  return $ Alloc s

parseStore :: Parser SSA
parseStore = do
  try (string "store")
  skipMany1 space
  s <- parseVar
  skipMany1 space
  n <- parseNum
  return $ Store s n

parseLoad :: Parser SSA
parseLoad = do
  try (string "load")
  skipMany1 space
  a <- parseVar
  skipMany1 space
  s <- parseVar
  return $ Load a s

パーサのコードがけっこう無残なことになってる・・・　あと一項命令、二項命令などを関数化してparseBinary Load "load"のようにして定義した方がきれいかもしれない。パーサのすっきりした記述はまだ習得できてないな。

この中間言語からLLVM IRへの変換は単純：

ssasToLlvm :: [SSA] -> String
ssasToLlvm ssas = start ++ (concat $ map ssaToLlvm  ssas) ++ end

ssaToLlvm :: SSA -> String
ssaToLlvm (Alloc s) = "%" ++ s ++ " = alloca i32" ++ "\n"
ssaToLlvm (Store s n) = "store i32 " ++ n ++ ", i32* %" ++ s ++ "\n"
ssaToLlvm (Load a s) = "%" ++ a ++ " = load i32, i32* %" ++ s ++ "\n"

愚直に文字列を吐き出すだけ。しかし文字列作成のコードも無残なことになっている・・・　printf使うか。

次はこの中間言語を、ソースをパースして作ったLispValデータ構造からどう作成するか、の話。