GHC 中是如何实现整数比较的？

Question

起初，我想研究 Integer 是如何从 classOrd

派生出来的

我在 GHC.Classes

中得到了那个定义

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 中（来自 ghc-prim 包）我能够找到 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#
(<#) = (<#)

但这是我能够得到的深度。 <# 指的是它自己。我们不知道它在做什么。

(isTrue# 只是一个函数，“Returns True 如果它的参数是 1# 和 False 如果 0#”)

在哪里可以找到来源，即完成工作的实际位置？最底部有组装吗？我在哪里可以找到这个神圣的地方？

Answer 1

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

所有像 (<#) 这样的原始操作都实现为您在 GHC.Prim 模块中找到的递归循环。从那里 the documentation tells us the next place to look is the primops.txt.pp file where it is listed under the name IntLtOp.

然后前面提到的文档说有两组primops：in-line和out-of-line。内联 primops 在从 STG 到 Cmm（这是 GHC 使用的两个内部表示）的翻译过程中被解析，并且可以在 GHC.StgToCmm.Prim module. And indeed the IntLtOp case is listed there 中找到，它主要使用 mo_wordSLt 函数进行内联转换这取决于平台。

这个mo_wordSLt函数在GHC.Cmm.MachOp模块中定义，其中包含引用：

Machine-level primops; ones which we can reasonably delegate to the native code generators to handle.

mo_wordSLt 函数生成 MachOp 数据类型的 MO_S_Lt 构造函数。所以我们可以进一步研究本机代码生成器，看看它是如何被翻译成低级指令的。在平台上有很多选择：SPARC, AArch64, LLVM, C, PPC, and 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)

GHC 中是如何实现整数比较的？

How is integer comparison implemented in GHC?

haskell

ghc