时间戳

首页 > 解决方案 > GHC 中如何实现整数比较？

haskell - GHC 中如何实现整数比较？

问题描述

起初，我想研究如何Integer从课程中派生Ord

我在 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#只是一个函数，“True如果它的参数是则返回，如果是1#False 0#”）

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

标签： haskellghc

解决方案

首先，从技术上讲，当您进入GHC.Integer.Type模块时，您会离开 Haskell 领域并进入 GHC 使用的当前实现领域，所以这个问题专门针对 GHC Haskell。

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

然后前面提到的文档说有两组primops：in-line和out-of-line。在从 STG 到 Cmm（这是 GHC 使用的两种内部表示）的转换过程中，内联 primops 被解析，并且可以在GHC.StgToCmm.Prim模块中找到。确实，该IntLtOp案例已在此处列出，并且主要使用mo_wordSLt取决于平台的功能对其进行了在线转换。

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

机器级primops；我们可以合理地委托给本机代码生成器来处理的那些。

该mo_wordSLt函数生成数据类型的MO_S_Lt构造函数。MachOp因此，我们可以进一步研究本机代码生成器，看看它是如何转换为低级指令的。平台有很多选择：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)

推荐阅读