haskell - Cómo hacer que GHC produzca instrucciones de "Agregar con transporte(ADC)"

optimization

Question

Aquí hay un código que agrega dos triples de palabras sin caja que representan un número de 192 bits a un nuevo triple de palabras sin caja, y también devuelve cualquier desbordamiento:

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

import GHC.Prim(plusWord2#, Word#, or#)

longAdd :: 
  (# Word#, Word#, Word# #) -> 
  (# Word#, Word#, Word# #) -> 
  (# Word#, (# Word#, Word#, Word# #) #)

longAdd (# xl, xm, xh #) (# yl, ym, yh #) =     
  let
    plusWord3 x y c = 
      let 
        (# c1, r1 #) = plusWord2# x y
        (# c2, r2 #) = plusWord2# r1 c
      in
        (# plusWord# c1 c2, r2 #)
    (# cl, rl #) = plusWord2# xl yl
    (# cm, rm #) = plusWord3 xm ym cl
    (# ch, rh #) = plusWord3 xh yh cm     
  in
    (# ch, (# rl, rm, rh #) #)

El problema es la definición "plusWord3". Idealmente, esto es como una función "adc", que toma dos palabras y el bit de acarreo y devuelve el resultado y un nuevo acarreo, por lo que el ensamblaje resultante es como el siguiente:

add x1 y1
adc x2 y2
adc x3 y3

Desafortunadamente, GHC, ya sea nativo o mediante LLVM, produce un código de ensamblaje feo que implica guardar el bit de acarreo en un registro y luego leerlo a través de un complemento adicional separado, en lugar de solo usar adc . No quiero llamar a una función externa de C para lograr esto, ya que una vez que agregue la sobrecarga de la llamada probablemente no valga la pena, me gustaría quedarme en Haskell para que el código pueda estar en línea cuando sea posible. Pero también quiero poder convencer al compilador para que produzca la instrucción adc adecuada. ¿Hay de todos modos puedo lograr eso?

Answer 1

La forma más confiable y real sería llamar a un primop directamente en su programa.

Usar una llamada FFI es la forma más fácil, pero como también notó, no será la manera más eficiente, debido a los gastos generales de FFI.

Incluso si el compilador apoye la instrucción que desea y la use en algunos programas, sería frágil. Algunos cambios aparentemente inocentes en su programa pueden terminar con un ensamblaje generado diferente que no usa la instrucción que desea.

Así que mi propuesta es:

1. Agregue la instrucción que necesita al generador de código X86 backend, si aún no está allí.
2. Agregue un primop que se traduzca directamente a la instrucción que desea ejecutar. Primero asegúrese de que no existe tal primop. Luego siga estos pasos: https://ghc.haskell.org/trac/ghc/wiki/AddingNewPrimitiveOperations
3. Su primop debería estar visible en GHC.Prim ( http://hackage.haskell.org/package/ghc-prim/docs/GHC-Prim.html ), utilícelo en sus programas.
4. Añade pruebas, envía tu parche :)

Answer 2

No estoy familiarizado con la programación de bajo nivel, pero después de la ronda de preguntas en el canal #ghc de Freenode, obtuve un puntero para addIntC# primint, que está relacionado con llvm.sadd.with.overflow. de LLVM llvm.sadd.with.overflow. . No estoy seguro de lo que llvm compila en.

El código nativo gen de GHC parece conocer la instrucción adc : X86/CodeGen.hs . Pero como dice el comentario:

Manejamos la suma, pero más bien mal.

Edición: se trabaja con palabras. Parece que el backend de LLVM compila MO_Add2 (que es otro nombre para plusWord2 ) para llvm.uadd.with.overflow en https://github.com/ghc/ghc/blob/2b7d9c2b96eb9da3cce7826df4a91c3426095528/compiler/llvmGen/LlvmCodeGen/CodeGen.hs#L737 llvm.uadd.with.overflow de las llvm.uadd.with.overflow de las llvm.uadd.with.overflow de las llvm.uadd.with.overflow https://github.com/ghc/ghc/blob/2b7d9c2b96eb9da3cce7826df4a91c3426095528/compiler/llvmGen/LlvmCodeGen/CodeGen.hs#L737 , boleto relacionado: https://ghc.haskell.org/trac/ghc/ticket/9430