63

我一直在检查integer-gmp源代码，以了解如何根据GHC Primops page中记录的 cmm 实现外国 primops 。我知道使用llvm hack或 fvia-C/gcc 来实现它们的技术——这对我来说更像是一种学习经验，可以理解 interger-gmp 库使用的第三种方法。

因此，我在 MSFT 页面（pdf 链接）上查找了 CMM 教程，浏览了GHC CMM 页面，但仍然有一些未解决的问题（如果不深入研究 CMM，很难将所有这些概念牢记在心，这就是我现在正在做的事情）。integer-bmp cmm 文件中有以下代码片段：

integer_cmm_int2Integerzh (W_ val)
{
   W_ s, p; /* to avoid aliasing */

   ALLOC_PRIM_N (SIZEOF_StgArrWords + WDS(1), integer_cmm_int2Integerzh, val);

   p = Hp - SIZEOF_StgArrWords;
   SET_HDR(p, stg_ARR_WORDS_info, CCCS);
   StgArrWords_bytes(p) = SIZEOF_W;

   /* mpz_set_si is inlined here, makes things simpler */
   if (%lt(val,0)) {
        s  = -1;
        Hp(0) = -val;
   } else {
     if (%gt(val,0)) {
        s = 1;
        Hp(0) = val;
     } else {
        s = 0;
     }
  }

   /* returns (# size  :: Int#,
                 data  :: ByteArray#
               #)
   */
   return (s,p);
}

如ghc cmm 标头中所定义：

W_ is alias for word.
ALLOC_PRIM_N is a function for allocating memory on the heap for primitive object.
Sp(n) and Hp(n) are defined as below (comments are mine):
#define WDS(n) ((n)*SIZEOF_W) //WDS(n) calculates n*sizeof(Word)
#define Sp(n)  W_[Sp + WDS(n)]//Sp(n) points to Stackpointer + n word offset?
#define Hp(n)  W_[Hp + WDS(n)]//Hp(n) points to Heap pointer + n word offset?

我不明白第 5-9 行（如果您有 1/0 的困惑，第 1 行是开始）。进一步来说：

  • 为什么ALLOC_PRIM_N(bytes,fun,arg)的函数调用格式是那样的？
  • 为什么 p 被这样操纵？

我理解的函数（通过查看Prim.hs中的函数签名）接受一个 int，并返回一个 (int, byte array) （分别存储在s代码p中）。

对于任何想知道内联调用的人if block，它是 gmp mpz_init_si 函数的 cmm 实现。我的猜测是，如果您通过 ccall 调用在目标文件中定义的函数，则它不能被内联（这是有道理的，因为它是目标代码，而不是中间代码 - LLVM 方法似乎更适合通过 LLVM IR 内联）。因此，优化是定义要内联的函数的 cmm 表示。如果这个猜测是错误的，请纠正我。

非常感谢对第 5-9 行的解释。我对 integer-gmp 文件中定义的其他宏有更多疑问，但在一篇文章中可能会问得太多。如果您可以通过 Haskell wiki 页面或博客回答问题（您可以发布链接作为答案），那将不胜感激（如果您这样做了，我也将不胜感激整数的逐步演练-gmp cmm 宏，例如GMP_TAKE2_RET1)。

4

2 回答 2

5

这些行在 Haskell 堆上分配了一个新的 ByteArray#，因此要理解它们，您首先需要了解 GHC 的堆是如何管理的。

  • 每个功能（= 执行 Haskell 代码的 OS 线程）都有自己专用的Nursery，这是堆的一个区域，它可以在其中进行正常的小型分配，例如这个。对象被简单地从低地址到高地址按顺序分配到该区域中，直到该功能尝试进行超过托儿所中剩余空间的分配，这将触发垃圾收集器。

  • 所有堆对象都与字大小的倍数对齐，即在 32 位系统上为 4 个字节，在 64 位系统上为 8 个字节。

  • Cmm 级寄存器 Hp 指向已在 Nursery 中分配的最后一个字（开头）。HpLim 指向可以在 Nursery 中分配的最后一个单词。（HpLim 也可以被另一个线程设置为 0 以停止 GC，或发送异步异常。）

  • https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects包含有关单个堆对象布局的信息。值得注意的是，每个堆对象都以一个信息指针开头，它（除其他外）标识它是什么类型的堆对象。

Haskell 类型 ByteArray# 是用堆对象类型 ARR_WORDS 实现的。ARR_WORDS 对象仅由（一个信息指针后跟）一个大小（以字节为单位）和任意数据（有效负载）组成。有效负载不被 GC 解释，因此它不能存储指向 Haskell 堆对象的指针，但它可以存储任何其他内容。SIZEOF_StgArrWords 是所有 ARR_WORDS 堆对象共有的标头大小，在这种情况下，有效负载只是一个单词，因此 SIZEOF_StgArrWords + WDS(1) 是我们需要分配的空间量。

ALLOC_PRIM_N (SIZEOF_StgArrWords + WDS(1), integer_cmm_int2Integerzh, val) 扩展为类似

Hp = Hp + (SIZEOF_StgArrWords + WDS(1));
if (Hp > HpLim) {
    HpAlloc = SIZEOF_StgArrWords + WDS(1);
    goto stg_gc_prim_n(integer_cmm_int2Integerzh, val);
}

第一行将 Hp 增加了要分配的数量。第二行检查堆溢出。第三行记录了我们尝试分配的数量，因此 GC 可以撤消它。第四行调用 GC。

第四行是最有趣的。参数告诉 GC 在垃圾收集完成后如何重新启动线程：它应该使用参数 val 重新调用 integer_cmm_int2Integerzh。stg_gc_prim_n 中的“_n”（以及 ALLOC_PRIM_N 中的“_N”）意味着 val 是一个非指针参数（在这种情况下是一个 Int#）。如果 val 是指向 Haskell 堆对象的指针，GC 需要知道它是活动的（因此它不会被收集）并使用对象的新地址重新调用我们的函数。在这种情况下，我们将使用 _p 变体。还有一些变体，例如 _pp 用于多个指针参数，_d 用于 Double# 参数等。

在第 5 行之后，我们成功分配了一个 SIZEOF_StgArrWords + WDS(1) 字节块，记住，Hp 指向它的最后一个字。因此，p = Hp - SIZEOF_StgArrWords 将 p 设置为该块的开头。第 8 行填充 p 的 info 指针，将新创建的堆对象标识为 ARR_WORDS。CCCS 是当前的成本中心堆栈，仅用于分析。启用分析后，每个堆对象都包含一个额外的字段，该字段基本上标识谁负责其分配。在非分析构建中，没有 CCCS 和 SET_HDR 只是设置信息指针。最后，第 9 行填写了 ByteArray# 的大小字段。函数的其余部分填充有效负载并返回符号值和 ByteArray# 对象指针。

所以，这最终更多地是关于 GHC 堆而不是关于 Cmm 语言，但我希望它有所帮助。

于 2014-09-22T14:54:39.793 回答
3

在此处输入图像描述

所需知识

为了进行算术和逻辑运算，计算机在其CPU（中央处理单元）中具有称为ALU（算术逻辑单元）的数字电路。ALU 从输入寄存器加载数据。处理器寄存器是在位于CPU 芯片的SRAM （静态随机存取存储器）中实现的L1 高速缓存（3 个 CPU 时钟周期内的数据请求）中的内存存储。一个处理器通常包含几种寄存器，通常根据它们可以容纳的位数来区分。

数字以离散位表示，可以容纳有限数量的值。通常数字具有编程语言（在 Haskell 中）公开的以下原始类型：

 8 bit numbers = 256 unique representable values
16 bit numbers = 65 536 unique representable values
32 bit numbers = 4 294 967 296 unique representable values
64 bit numbers = 18 446 744 073 709 551 616 unique representable values

这些类型的固定精度算术已在硬件中实现。字长是指计算机的 CPU 一次可以处理的位数。对于x86架构，这是32 位，而x64是64 位。

IEEE 754定义了{16, 32, 64, 128} 位数字的浮点数标准。例如，32 位点数（具有 4 294 967 296 个唯一值）可以保持近似值[ -3.402823e38 到 3.402823e38]，精度至少为7个浮点数。

在此处输入图像描述

此外

首字母缩略词GMP表示GNU 多精度算术库，并增加了对软件模拟任意精度算术的支持。Glasgow Haskell Compiler Integer 实现使用它。

GMP 的目标是在所有操作数大小上都比任何其他 bignum 库都快。这样做的一些重要因素是：

  • 使用全字作为基本算术类型。
  • 对不同的操作数大小使用不同的算法；对于非常大的数字更快的算法通常对于小数字来说更慢。
  • 为最重要的内部循环高度优化的汇编语言代码，专门用于不同的处理器。

回答

对于某些 Haskell 可能有点难以理解语法所以这里是 javascript 版本 

var integer_cmm_int2Integerzh = function(word) {
  return WORDSIZE == 32 
    ? goog.math.Integer.fromInt(word))
    : goog.math.Integer.fromBits([word.getLowBits(), word.getHighBits()]);
};

goog使用的Google Closure 库类位于Math.Integer中。调用函数：

goog.math.Integer.fromInt = function(value) {
  if (-128 <= value && value < 128) {
    var cachedObj = goog.math.Integer.IntCache_[value];
    if (cachedObj) {
      return cachedObj;
    }
  }

  var obj = new goog.math.Integer([value | 0], value < 0 ? -1 : 0);
  if (-128 <= value && value < 128) {
    goog.math.Integer.IntCache_[value] = obj;
  }
  return obj;
};
goog.math.Integer.fromBits = function(bits) {
  var high = bits[bits.length - 1];
  return new goog.math.Integer(bits, high & (1 << 31) ? -1 : 0);
};

这并不完全正确，因为返回类型应该在return (s,p);哪里

  • s 是值
  • p 是符号

为了修复这个 GMP 包装应该被创建。这已在Haskell to JavaScript 编译器项目（源链接）中完成。

5-9 行

ALLOC_PRIM_N (SIZEOF_StgArrWords + WDS(1), integer_cmm_int2Integerzh, val);
p = Hp - SIZEOF_StgArrWords;
SET_HDR(p, stg_ARR_WORDS_info, CCCS);
StgArrWords_bytes(p) = SIZEOF_W;

如下面所述

  • 分配空间作为新词
  • 创建指向它的指针
  • 设置指针值
  • 设置指针类型大小
于 2014-09-24T06:32:12.193 回答