c++ - 在两个 ASM GCC 内联 block 之间传播进位

Question

尊敬的程序集/C++ 开发人员，

The question is: Does propagate the carry (or any flag) between two ASM block is realistic or totally insane, even if it works ?

几年前，我为低于 512 位(编译时)的大型算术开发了一个整数库。我此时没有使用 GMP，因为对于这种规模，由于内存分配和二进制表示的模型选择，GMP 变慢了 bench .

我必须承认我使用 BOOST_PP 创建了我的 ASM(字符串 block )，它不是很出色(如果好奇请看一下 vli)。图书馆运作良好。

但是我注意到此时不可能在两个 ASM 内联 block 之间传播状态寄存器的进位标志。这是合乎逻辑的，因为对于编译器在两个 block 之间生成的任何助记符，寄存器都会被重置( mov 指令除外(根据我的汇编知识))。

昨天我有了一个想法，在两个 ASM block 之间传播进位有点棘手(使用递归算法)。它正在运行，但我认为我很幸运。

#include <iostream>
#include <array>
#include <cassert>
#include <algorithm>

//forward declaration
template<std::size_t NumBits>
struct integer;


//helper using object function, partial specialization  is forbiden on functions
template <std::size_t NumBits, std::size_t W, bool K = W == integer<NumBits>::numwords>
struct helper {
    static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
        helper<NumBits, integer<NumBits>::numwords>::add(a,b);
    }
};

// first addition (call first)
template<std::size_t NumBits, std::size_t W>
struct helper<NumBits, W, 1> {
    static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
        __asm__ (
                              "movq %1, %%rax \n"
                              "addq %%rax, %0 \n"
                              : "+m"(a[0]) // output
                              : "m" (b[0]) // input only
                              : "rax", "cc", "memory");
        helper<NumBits,W-1>::add(a,b);
    }
};

//second and more propagate the carry (call next)
template<std::size_t NumBits, std::size_t W>
struct helper<NumBits, W, 0> {
    static inline void add(integer<NumBits> &a, const integer<NumBits> &b){
        __asm__ (
                              "movq %1, %%rax \n"
                              "adcq %%rax, %0 \n"
                              : "+m"(a[integer<NumBits>::numwords-W])
                              : "m" (b[integer<NumBits>::numwords-W])
                              : "rax", "cc", "memory");
        helper<NumBits,W-1>::add(a,b);
    }
};

//nothing end reccursive process (call last)
template<std::size_t NumBits>
struct helper<NumBits, 0, 0> {
    static inline void add(integer<NumBits> &a, const integer<NumBits> &b){};
};

// tiny integer class
template<std::size_t NumBits>
struct integer{
    typedef uint64_t      value_type;
    static const std::size_t numbits = NumBits;
    static const std::size_t numwords = (NumBits+std::numeric_limits<value_type>::digits-1)/std::numeric_limits<value_type>::digits;
    using container = std::array<uint64_t, numwords>;

    typedef typename container::iterator             iterator;

    iterator begin() { return data_.begin();}
    iterator end() { return data_.end();}

    explicit integer(value_type num = value_type()){
        assert( -1l >> 1 == -1l );
        std::fill(begin(),end(),value_type());
        data_[0] = num;
    }

    inline value_type& operator[](std::size_t n){ return data_[n];}
    inline const value_type& operator[](std::size_t n) const { return data_[n];}

    integer& operator+=(const integer& a){
        helper<numbits,numwords>::add(*this,a);
        return *this;
    }

    integer& operator~(){
        std::transform(begin(),end(),begin(),std::bit_not<value_type>());
        return *this;
    }

    void print_raw(std::ostream& os) const{
        os << "(" ;
        for(std::size_t i = numwords-1; i > 0; --i)
            os << data_[i]<<" ";
        os << data_[0];
        os << ")";
    }

    void print(std::ostream& os) const{
        assert(false && " TO DO ! \n");
    }

private:
    container data_;
};

template <std::size_t NumBits>
std::ostream& operator<< (std::ostream& os, integer<NumBits> const& i){
    if(os.flags() & std::ios_base::hex)
        i.print_raw(os);
    else
        i.print(os);
    return os;
}

int main(int argc, const char * argv[]) {
    integer<256> a; // 0
    integer<256> b(1);

    ~a; //all the 0 become 1

    std::cout << " a: " << std::hex << a << std::endl;
    std::cout << " ref: (ffffffffffffffff ffffffffffffffff ffffffffffffffff ffffffffffffffff) " <<  std::endl;

    a += b; // should propagate the carry

    std::cout << " a+=b: " << a << std::endl;
    std::cout << " ref: (0 0 0 0) " <<  std::endl; // it works but ...

    return 0;
}

我得到了正确的结果(它必须在版本 -O2 或 -O3 中编译!)并且 ASM 是正确的(在我的 Mac 上使用 clang++:Apple LLVM 版本 9.0.0 (clang-900.0.39.2))

    movq    -96(%rbp), %rax
    addq    %rax, -64(%rbp)

    ## InlineAsm End
    ## InlineAsm Start
    movq    -88(%rbp), %rax
    adcq    %rax, -56(%rbp)

    ## InlineAsm End
    ## InlineAsm Start
    movq    -80(%rbp), %rax
    adcq    %rax, -48(%rbp)

    ## InlineAsm End
    ## InlineAsm Start
    movq    -72(%rbp), %rax
    adcq    %rax, -40(%rbp)

我确信它正在工作，因为在优化过程中，编译器删除了 ASM block 之间的所有无用指令(在 Debug模式下它失败了)。

你怎么看？绝对不安全？编译器专家知道它的稳定性吗？

总结:我这样做只是为了好玩 :) 是的，GMP 是大型算术的解决方案!

Answer 1

__volatile__ 的使用是一种滥用。

__volatile__ 的目的是强制编译器在编写的位置发出汇编代码，而不是依靠数据流分析来解决这个问题。如果你在用户空间中对数据进行普通操作，通常你不应该使用 __volatile__，如果你需要 __volatile__ 来让你的代码工作，它几乎总是意味着您的操作数指定不正确。

是的，操作数指定不正确。让我们看一下第一个 block 。

__asm__ __volatile__ (
                      "movq %1, %%rax \n"
                      "addq %%rax, %0 \n"
                      : "=m"(a[0]) // output
                      : "m" (b[0]) // input only
                      : "rax", "memory");

这里有两个错误。

• 输出 "=m"(a[0]) 的约束不正确。回想一下，addq 的目标既是输入又是输出，因此正确的约束是 +，所以使用 "+m"(a[0])。如果你告诉编译器 a[0] 只是输出，编译器可能会安排 a[0] 包含一个垃圾值(通过死存储消除)，这是不是你想要的。

• 程序集规范中缺少标志。在不告诉编译器标志已修改的情况下，编译器可能会假设标志在整个汇编 block 中都保留了下来，这将导致编译器在其他地方生成不正确的代码。

不幸的是，这些标志只能用作汇编 block 的输出或破坏操作数，不能用作输入。所以在正确指定操作数上大惊小怪，所以你不使用 __volatile__...事实证明，无论如何都没有指定操作数的好方法!

因此这里的建议是，您应该至少修复您可以修复的操作数，并将"cc" 指定为一个clobber。但是有一些更好的解决方案根本不需要 __volatile__...

解决方案 #1:使用 GMP。

用于加法的mpn_ 函数不分配内存。 mpz_ 函数是 mpn_ 函数的包装器，带有一些额外的逻辑和内存分配。

解决方案 #2:将所有内容写入一个汇编 block 。

如果您在一个汇编 block 中编写整个循环，则不必担心在 block 之间保留标志。您可以使用汇编宏来执行此操作。请原谅，我不是一个汇编程序员:

template <int N>
void add(unsigned long long *dest, unsigned long long *src) {
  __asm__(
      "movq (%1), %%rax"
      "\n\taddq %%rax, (%0)"
      "\n.local add_offset"
      "\n.set add_offset,0"
      "\n.rept %P2" // %P0 means %0 but without the $ in front
      "\n.set add_offset,add_offset+8"
      "\n\tmovq add_offset(%1), %%rax"
      "\n\tadcq %%rax, add_offset(%0)"
      "\n.endr"
      :
      : "r"(dest), "r"(src), "n"(N-1)
      : "cc", "memory", "rax");
}   

它所做的是使用 .rept 汇编指令评估循环。您最终将获得 1 个 addq 拷贝和 N-1 个 adcq 拷贝，尽管如果您使用 -S 查看 GCC 的汇编输出你只会看到一个。汇编程序本身将创建拷贝，展开循环。

参见要点:https://gist.github.com/depp/966fc1f4d535e31d9725cc71d97daf91