所以这个问题可能看起来太新手了,但我已经在读 Steven Muchnick 的《高级编译器设计和实现》一书,在优化的第一章中谈到了常量折叠。
第一次尝试如下所示,但考虑到它需要类型类
Integral
和Bits
,几乎不可能实现。
data Value
= BoolV Bool
| IntegerV Integer
| FloatV Double
| StringV String
deriving (Show, Eq)
data Expression
= Const Value
| Temp Label
| List [Expression]
| Call Label [Expression]
| BinOp Operator Expression Expression
deriving (Show, Eq)
rerunOverIR :: Expression -> Expression
rerunOverIR = \case
Const constant -> Const constant
Temp temporary -> Temp temporary
List list -> List list
Call label args -> Call label (map rerunOverIR args)
BinOp operator lhs rhs ->
case operator of
Addition -> folder (+)
Subtraction -> folder (-)
Multiplication -> folder (*)
Modulo -> folder mod
Division -> folder div
BitwiseAnd -> folder (.&.)
BitwiseOr -> folder (.|.)
BitwiseXor -> folder xor
ShiftRight -> folder shiftR
ShiftLeft -> folder shiftL
Equal -> folder (==)
NotEqual -> folder (/=)
Greater -> folder (>)
GreaterEqual -> folder (>=)
Less -> folder (<)
LessEqual -> folder (<=)
LogicalAnd -> folder (&&)
LogicalOr -> folder (||)
_ -> error $ "this operator doesn't exist " ++ show operator
where
folder op =
case lhs of
Const c1 -> case rhs of
Const c2 -> Const $ op c1 c2
expr -> rerunOverIR $ BinOp operator (Const c1) (rerunOverIR expr)
e1 -> case rhs of
rerunOverIR c2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (Const c2)
e2 -> rerunOverIR $ BinOp operator (rerunOverIR e1) (rerunOverIR e2)
所以这次我尝试将表达式更改为以下,但结果更糟。
data Expression
= Bool Bool
| Integer Integer
| Float Double
| String String
| Temp Label
| List [Expression]
| Call Label [Expression]
| BinOp Operator Expression Expression
deriving (Show, Eq)
所以我的问题是,用 Haskell 编写的编译器或解释器如何在后期正确处理常量折叠?我很确定我走错了路......
看起来你当然应该能够通过这样做来做到这一点,例如,
Addition -> case (lhs, rhs) of
(Const (IntegerV lhs), Const (IntegerV rhs)) -> Const (IntegerV (lhs + rhs))
并且对于每种情况都同样明确。
更简单地说,您可以专门化
folder
为每组有效类型提供单独的版本:例如,当两个参数都是 folderNum
或 Const (IntegerV ...)
时,它将匹配。您的方向是正确的,但您必须进行详细的案例工作,以匹配哪些二进制运算适用于哪些常量类型。