Подтвердить что ты не робот

Получение GHC для подготовки инструкций "Добавить с переносом (ADC)"

Вот код, который добавляет два тройки незанятых слов, представляющих 192-битное число, в новую тройку нерасположенных слов, а также возвращает любое переполнение:

{-# 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 #) #)

Проблема - это определение "plusWord3". В идеале это похоже на функцию adc, которая принимает два слова и бит переноса и возвращает результат и новый перенос, поэтому результирующая сборка выглядит следующим образом:

add x1 y1
adc x2 y2
adc x3 y3

К сожалению, GHC, будь то native или через LLVM, создает уродливый ассемблерный код, который включает сохранение бит переноса в регистр, а затем чтение его с помощью отдельного дополнительного добавления вместо использования adc. Я не хочу вызывать внешнюю функцию C для достижения этой цели, так как как только вы добавляете накладные расходы на вызов, это, вероятно, не стоит, я бы хотел остаться в Haskell, чтобы код мог быть встроен там, где это возможно. Но я также хочу уговорить компилятор подготовить инструкцию adc соответствующим образом. В любом случае я могу достичь этого?

4b9b3361

Ответ 1

Самый реальный и эффективный способ - вызвать primop непосредственно в вашей программе.

Использование вызова FFI - самый простой способ, но поскольку вы также отметили, что это не самый эффективный способ из-за накладных расходов FFI.

Даже если компилятор будет поддерживать требуемую команду и использовать ее в некоторых программах, она будет хрупкой. Некоторые, казалось бы, невинные изменения в вашей программе могут закончиться разной сгенерированной сборкой, которая не использует требуемую команду.

Итак, мое предложение:

  • Добавьте инструкцию, необходимую для бэкэда генератора кода X86, если он еще не существует.
  • Добавить примитив, который переводится непосредственно в инструкцию, которую вы хотите запустить. Сначала убедитесь, что такой примитив не существует. Затем выполните следующие действия: https://ghc.haskell.org/trac/ghc/wiki/AddingNewPrimitiveOperations
  • Примап должен быть видимым в GHC.Prim(http://hackage.haskell.org/package/ghc-prim/docs/GHC-Prim.html), используйте его в своих программах.
  • Добавьте тесты, отправьте свой патч:)

Ответ 2

Я не знаком с низкоуровневым программированием, но после раунда вопросов по каналу Freenode #ghc я получил указатель на addIntC# primop, который связанные с LLVM llvm.sadd.with.overflow.. Я не уверен, что llvm компилирует это.


Нативный код GHC, похоже, знает о инструкции adc: X86/CodeGen.hs. Но, как говорится в комментарии:

мы обрабатываем добавление, но довольно плохо


Изменить: вы работаете со словами. Кажется, что бэкенд LLVM компилирует MO_Add2 (это другое имя для plusWord2) на llvm.uadd.with.overflow в https://github.com/ghc/ghc/blob/2b7d9c2b96eb9da3cce7826df4a91c3426095528/compiler/llvmGen/LlvmCodeGen/CodeGen.hs#L737, связанный билет: https://ghc.haskell.org/trac/ghc/ticket/9430