haskell - online - Formato de llamada cmm para primop extranjero(ejemplo entero-gmp)

haskell core download

Question

He estado comprobando el código fuente integer-gmp para entender cómo se pueden implementar los primop extranjeros en términos de cmm como se documenta en la página GHC Primops . Estoy al tanto de las técnicas para implementarlas utilizando llvm hack o fvia-C / gcc; esta es más una experiencia de aprendizaje para mí para comprender este tercer enfoque que utiliza la biblioteca interger-gmp.

Entonces, busqué el tutorial de CMM en la página de MSFT (enlace pdf) , pasé por la página GHC CMM , y todavía hay algunas preguntas sin respuesta (difícil mantener todos esos conceptos en la cabeza sin cavar en CMM, que es lo que estoy haciendo ahora). Hay este fragmento de código del archivo entero cmm 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);
}

Como se define en el encabezado 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?

No entiendo las líneas 5-9 (la línea 1 es el comienzo en caso de que tenga una confusión de 1/0). Más específicamente:

• ¿Por qué el formato de llamada de función de ALLOC_PRIM_N (bytes, diversión, arg) de esa manera?
• ¿Por qué se manipula p de esa manera?

La función tal como yo lo entiendo (al observar la firma de la función en Prim.hs ) toma un int, y devuelve un (int, array de bytes) (almacenado en s , p respectivamente en el código).

Para cualquiera que se esté preguntando acerca de la llamada en línea en el if block , se trata de la implementación cmm de la función gmp mpz_init_si . Supongo que si llamas a una función definida en un archivo de objeto mediante llamada, no puede ser inlineada (lo cual tiene sentido ya que es código objeto, no código intermedio; el enfoque LLVM parece más adecuado para alinear a través de LLVM IR). Entonces, la optimización era definir una representación cmm de la función que se inline. Por favor corrígeme si esta suposición es incorrecta.

La explicación de las líneas 5-9 será muy apreciada. Tengo más preguntas sobre otras macros definidas en el archivo entero-gmp, pero puede ser demasiado pedir en una publicación. Si puede responder la pregunta con una página wiki de Haskell o un blog (puede publicar el enlace como respuesta), eso sería muy apreciado (y si lo hace, también apreciaría el paso a paso de un número entero). -gmp cmm macro como GMP_TAKE2_RET1 ).

Answer 1

Esas líneas asignan un nuevo ByteArray # en el montón de Haskell, por lo que para entenderlas primero debes saber un poco sobre cómo se gestiona el montón de GHC.

• Cada capacidad (= subproceso del sistema operativo que ejecuta el código Haskell) tiene su propio vivero dedicado, un área del montón en la que realiza asignaciones normales, pequeñas como esta. Los objetos simplemente se asignan secuencialmente en esta área desde direcciones bajas a direcciones altas hasta que la capacidad intenta realizar una asignación que excede el espacio restante en el vivero, lo que desencadena el recolector de basura.

• Todos los objetos de montón están alineados con un múltiplo del tamaño de palabra, es decir, 4 bytes en sistemas de 32 bits y 8 bytes en sistemas de 64 bits.

• El registro Hp del nivel Cmm señala (el comienzo de) la última palabra asignada en el vivero. HpLim apunta a la última palabra que se puede asignar en el vivero. (HpLim también se puede establecer en 0 por otro hilo para detener el mundo para GC, o para enviar una excepción asincrónica).

• https://ghc.haskell.org/trac/ghc/wiki/Commentary/Rts/Storage/HeapObjects tiene información sobre el diseño de objetos de montón individuales. En particular, cada objeto de montón comienza con un puntero de información , que (entre otras cosas) identifica qué tipo de objeto de montón es.

El tipo ByteArray # de Haskell se implementa con el tipo de objeto de montón ARR_WORDS. Un objeto ARR_WORDS solo consiste en (un puntero de información seguido de) un tamaño (en bytes) seguido de datos arbitrarios (la carga útil). La carga útil no es interpretada por el GC, por lo que no puede almacenar punteros en los objetos Heap de Haskell, pero puede almacenar cualquier otra cosa. SIZEOF_StgArrWords es el tamaño del encabezado común a todos los objetos del montón ARR_WORDS, y en este caso la carga útil es solo una palabra, por lo que SIZEOF_StgArrWords + WDS (1) es la cantidad de espacio que necesitamos asignar.

ALLOC_PRIM_N (SIZEOF_StgArrWords + WDS (1), integer_cmm_int2Integerzh, val) se expande a algo así como

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

La primera línea aumenta Hp por la cantidad que se asignará. La segunda línea verifica el desbordamiento del montón. La tercera línea registra la cantidad que tratamos de asignar, por lo que el GC puede deshacerla. La cuarta línea llama al GC.

La cuarta línea es la más interesante. Los argumentos le dicen al GC cómo reiniciar el hilo una vez que se hace la recolección de basura: debe reinvocar integer_cmm_int2Integerzh con el argumento val. El "_n" en stg_gc_prim_n (y el "_N" en ALLOC_PRIM_N) significa que val es un argumento no puntero (en este caso un Int #). Si val fuera un puntero a un objeto Heap de Haskell, el GC necesita saber que está en vivo (para que no se recopile) y reinvocar nuestra función con la nueva dirección del objeto. En ese caso, usaríamos la variante _p. También hay variantes como _pp para múltiples argumentos de puntero, _d para argumentos Double #, etc.

Después de la línea 5, hemos asignado correctamente un bloque de SIZEOF_StgArrWords + WDS (1) bytes y, recuerde, HP apunta a su última palabra. Entonces, p = Hp - SIZEOF_StgArrWords establece p al comienzo de este bloque. Las líneas 8 completan el puntero de información de p, identificando el objeto de montón recién creado como ARR_WORDS. CCCS es la pila del centro de costo actual, que se usa solo para crear perfiles. Cuando se habilita la creación de perfiles, cada objeto de pila contiene un campo adicional que básicamente identifica quién es responsable de su asignación. En compilaciones sin perfil, no hay CCCS y SET_HDR solo establece el puntero de información. Finalmente, la línea 9 completa el campo de tamaño del ByteArray #. El resto de la función rellena la carga útil y devuelve el valor del signo y el puntero del objeto ByteArray #.

Por lo tanto, esto terminó siendo más sobre el montón GHC que sobre el lenguaje Cmm, pero espero que ayude.

Answer 2

Conocimiento requerido

Para hacer operaciones aritméticas y lógicas, las computadoras tienen un circuito digital llamado ALU (Unidad lógica aritmética) en su CPU (Unidad de procesamiento central). Una ALU carga datos de los registros de entrada . El registro del procesador es el almacenamiento de memoria en la memoria caché L1 (solicitudes de datos dentro de 3 marcas de reloj de la CPU) implementadas en la SRAM (memoria de acceso aleatorio estática) ubicada en el chip de la CPU . Un procesador a menudo contiene varios tipos de registros, generalmente diferenciados por la cantidad de bits que pueden contener .

Los números se expresan en bits discretos y pueden contener un número finito de valores. Normalmente, los números tienen los siguientes tipos primitivos expuestos por el lenguaje de programación ( en 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

La aritmética de precisión fija para esos tipos se ha implementado en hardware . El tamaño de palabra se refiere a la cantidad de bits que la CPU de una computadora puede procesar de una sola vez. Para la arquitectura x86 esto es 32 bits y x64 esto es 64 bits .

IEEE 754 define números de coma flotante estándar para {16, 32, 64, 128} números de bit. Por ejemplo, el número de 32 bits (con 4 294 967 296 valores únicos) puede contener valores aproximados [-3.402823e38 a 3.402823e38] con una precisión de al menos 7 dígitos de coma flotante.

en adición

El acrónimo GMP significa Biblioteca de Aritmética de Precisión Múltiple de GNU y agrega soporte para aritmética de precisión arbitraria emulada por software. La aplicación Glasgow Haskell Compiler Integer usa esto.

GMP pretende ser más rápido que cualquier otra biblioteca bignum para todos los tamaños de operandos. Algunos factores importantes para hacer esto son:

• Usar palabras completas como el tipo aritmético básico.
• Usar diferentes algoritmos para diferentes tamaños de operandos; los algoritmos que son más rápidos para números muy grandes suelen ser más lentos para números pequeños.
• Código de lenguaje ensamblador altamente optimizado para los circuitos internos más importantes, especializados para diferentes procesadores.

Responder

Para algunos, Haskell podría tener una sintaxis un poco difícil de comprender, así que aquí está la versión de JavaScript

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

Donde goog está Google Closure, la clase de biblioteca utilizada se encuentra en Math.Integer . Funciones llamadas:

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);
};

Eso no es totalmente correcto ya que el tipo de devolución debe ser return (s,p); dónde

• s es valor
• p es signo

Para arreglar este envoltorio GMP debe ser creado. Esto se ha hecho en el proyecto del compilador de Haskell a JavaScript ( enlace de origen ).

Líneas 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;

Son como sigue

• asigna espacio como palabra nueva
• crea puntero a eso
• establecer el valor del puntero
• establecer el tamaño del tipo de puntero