GHC中如何实现整数比较

Question

起初，我想研究Integer是如何从类Ord派生的

我在GHC.分类中得到了这个定义

instance Ord Integer where
(<=) = leInteger
(>)  = gtInteger
(<)  = ltInteger
(>=) = geInteger
compare = compareInteger

compareInteger指向另一个源文件GHC.Integer.Type。它是这样定义的:

compareInteger :: Integer -> Integer -> Ordering
compareInteger (Jn# x)  (Jn# y) = compareBigNat y x
compareInteger (S#  x)  (S#  y) = compareInt#   x y
compareInteger (Jp# x)  (Jp# y) = compareBigNat x y
compareInteger (Jn# _)  _       = LT
compareInteger (S#  _)  (Jp# _) = LT
compareInteger (S#  _)  (Jn# _) = GT
compareInteger (Jp# _)  _       = GT

S#表示固定大小的整数，Jn#和Jp#表示任意大小的整数。

在GHC.Classes(来自ghcprim包(中，我能够找到compareInt#的定义。像Int#这样的不寻常类型的出现表明我离它越来越近了。

compareInt# :: Int# -> Int# -> Ordering
compareInt# x# y#
| isTrue# (x# <#  y#) = LT
| isTrue# (x# ==# y#) = EQ
| True                = GT

更深入地说，我得到了操作员(GHC.Prim模块(的定义

infix 4 <#
(<#) :: Int# -> Int# -> Int#
(<#) = (<#)

但这是我所能达到的深度。CCD_ 10是指它自己。我们不知道它在做什么。

(isTrue#只是一个"如果其参数为1#则返回True，如果为0#则返回False"的函数(

我在哪里可以找到来源，完成工作的实际地点?在最下面有一些组件吗?我在哪里能找到这个神圣的地方?

Answer 1

首先，从技术上讲，当你进入GHC.Integer.Type模块时，你就离开了Haskell的领域，进入了GHC使用的当前实现的领域，所以这个问题特别是关于GHC Haskell。

所有像(<#)这样的基元操作都是作为递归循环实现的，您可以在GHC.Prim模块中找到它。从那里，文档告诉我们下一个要查看的地方是primops.txt.pp文件，该文件以名称IntLtOp列出。

然后前面提到的文件说，有两组原始操作：在线和离线。在从STG到Cmm(这是GHC使用的两种内部表示(的转换过程中，可以解析行内原始运算，并且可以在GHC.StgToCmm.Prim模块中找到。事实上，IntLtOp的情况已经列在那里，它主要使用依赖于平台的mo_wordSLt函数进行在线转换。

此mo_wordSLt函数在GHC.Cmm.MachOp模块中定义，该模块包含引用：

机器级原始操作；我们可以合理地委托给要处理的本地代码生成器。

mo_wordSLt函数生成MachOp数据类型的MO_S_Lt构造函数。因此，我们可以进一步研究本机代码生成器，看看它是如何转换为低级指令的。平台上有很多选择：SPARC、AArch64、LLVM、C、PPC和X86(我在GitLab上用搜索功能找到了所有这些(。

X86是最受欢迎的平台，所以我将继续在那里。该实现使用condIntReg辅助函数，其定义如下：

condIntReg :: Cond -> CmmExpr -> CmmExpr -> NatM Register
condIntReg cond x y = do
CondCode _ cond cond_code <- condIntCode cond x y
tmp <- getNewRegNat II8
let
code dst = cond_code `appOL` toOL [
SETCC cond (OpReg tmp),
MOVZxL II8 (OpReg tmp) (OpReg dst)
]
return (Any II32 code)

同样有趣的是condIntCode的定义，它取决于条件的操作数。这是一个大函数，所以我不会在这里重现完整的代码，但一般情况下会产生CMP指令：

-- anything vs anything
condIntCode' _ cond x y = do
platform <- getPlatform
(y_reg, y_code) <- getNonClobberedReg y
(x_op, x_code) <- getRegOrMem x
let
code = y_code `appOL`
x_code `snocOL`
CMP (cmmTypeFormat (cmmExprType platform x)) (OpReg y_reg) x_op
return (CondCode False cond code)