幾個月前,我在Haskell的第一個項目是編寫一個c編譯器,結果是一個相當幼稚的代碼生成方法,我將在這裏介紹。請做而不是將此作爲代碼生成器的良好設計示例,而是將其視爲一種快速而骯髒(並且最終是天真)的方式,以便能夠以相當快的速度運行,並且具有良好的性能。
我開始通過定義一箇中間表示LIR(下中間表示),它緊密對應於我的指令集(在我的情況x86_64的):
data LIRInst = LIRRegAssignInst LIRReg LIRExpr
| LIRRegOffAssignInst LIRReg LIRReg LIRSize LIROperand
| LIRStoreInst LIRMemAddr LIROperand
| LIRLoadInst LIRReg LIRMemAddr
| LIREnterInst LIRInt
| LIRJumpLabelInst LIRLabel
| LIRIfInst LIRRelExpr LIRLabel LIRLabel -- false, then true
| LIRCallInst LIRLabel LIRLabel -- method label, return label
| LIRCalloutInst String
| LIRRetInst [LIRLabel] String -- list of successors, and the name of the method returning from
| LIRLabelInst LIRLabel
deriving (Show, Eq, Typeable)
接下來來到一個單子,將處理整個交織狀態翻譯(我是一無所知我們的朋友,在State Monad
-at的時間):
newtype LIRTranslator a = LIRTranslator
{ runLIR :: Namespace -> (a, Namespace) }
instance Monad LIRTranslator where
return a = LIRTranslator (\s -> (a, s))
m >>= f = LIRTranslator (\s ->
let (a, s') = runLIR m s
in runLIR (f a) s')
通過各種轉換階段,將被「擰」國家一起:
data Namespace = Namespace
{ temp :: Int -- id's for new temporaries
, labels :: Int -- id's for new labels
, scope :: [(LIRLabel, LIRLabel)] -- current program scope
, encMethod :: String -- current enclosing method
, blockindex :: [Int] -- index into the SymbolTree
, successorMap :: Map.Map String [LIRLabel]
, ivarStack :: [(LIRReg, [CFGInst])] -- stack of ivars (see motioned code)
}
爲了方便起見,我還指定了一系列的翻譯一元功能,例如:
-- |Increment our translator's label counter
incLabel :: LIRTranslator Int
incLabel = LIRTranslator (\[email protected](Namespace{ labels = l }) -> (l, ns{ labels = (l+1) }))
我然後繼續遞歸模式匹配我的AST,片段逐片段,得到形式的許多功能:
translateBlock :: SymbolTree -> ASTBlock -> LIRTranslator [LIRInst]
translateBlock st (DecafBlock _ [] _) = withBlock (return [])
translateBlock st block =
withBlock (do b <- getBlock
let st' = select b st
declarations <- mapM (translateVarDeclaration st') (blockVars block)
statements <- mapM (translateStm st') (blockStms block)
return (concat declarations ++ concat statements))
(用於翻譯目標語言的代碼塊)或
-- | Given a SymbolTree, Translate a single DecafMethodStm into [LIRInst]
translateStm st (DecafMethodStm mc _) =
do (instructions, operand) <- translateMethodCall st mc
final <- motionCode instructions
return final
(用於翻譯的方法調用)或
translateMethodPrologue :: SymbolTree -> DecafMethod -> LIRTranslator [LIRInst]
translateMethodPrologue st (DecafMethod _ ident args _ _) =
do let numRegVars = min (length args) 6
regvars = map genRegVar (zip [LRDI, LRSI, LRDX, LRCX, LR8, LR9] args)
stackvars <- mapM genStackVar (zip [1..] (drop numRegVars args))
return (regvars ++ stackvars)
where
genRegVar (reg, arg) =
LIRRegAssignInst (symVar arg st) (LIROperExpr $ LIRRegOperand reg)
genStackVar (index, arg) =
do let mem = LIRMemAddr LRBP Nothing ((index + 1) * 8) qword --^[rbp] = old rbp; [rbp + 8] = ret address; [rbp + 16] = first stack param
return $ LIRLoadInst (symVar arg st) mem
爲實際生成一些LIR代碼的例子。希望這三個例子能給你一個很好的起點;最終,你會想慢慢地,一次關注AST中的一個片段(或中間類型)。
這不值得一個完整的答案,顯然涉及到一種非常不同的語言風格,但是[你可能熟悉用Haskell編寫的編譯器](http://hackage.haskell.org/trac/ ghc/wiki /評論/編譯器/後端)的源代碼,你可以看看靈感。 – 2011-06-09 21:29:06
你的中間表示映射到jvm操作碼一對一嗎?如果沒有,那麼這是一個開始的地方:創建一個或多個數據類型來表示(目標的)JVM操作碼的一部分。然後走更高級的IR並創建低級別的JVM中心IR。 – Lambdageek 2011-06-09 21:38:48