在两个 ASM GCC 内联块之间传播进位位
propagate carry bit between two ASM GCC inline block
亲爱的 Assembly/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（字符串块），它不是很漂亮（如果好奇请看一下 vli）。图书馆运作良好。
然而我注意到此时不可能在两个 ASM 内联块之间传播状态寄存器的进位标志。这是合乎逻辑的，因为对于编译器在两个块之间生成的任何助记符，寄存器都会被重置（ mov 指令除外（根据我的汇编知识））。
昨天我想到了在两个 ASM 块之间传播进位有点棘手（使用递归算法）。它正在工作，但我认为我很幸运。
#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 with 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 块之间的所有无用指令（在调试模式下它失败了）。
你怎么看？绝对不安全？编译器专家知道它的稳定性吗？
总而言之：我这样做只是为了好玩 :) 是的，GMP 是大型算术的解决方案！
使用 __volatile__ 是一种滥用。
__volatile__的目的是强制编译器在写入的位置发出汇编代码，而不是依靠数据流分析来解决这个问题。如果您在用户 space 中对数据进行普通操作，通常您不应该使用 __volatile__，如果您需要 __volatile__ 来让您的代码工作，这几乎总是意味着您的操作数指定不正确。
是的，操作数指定不正确。我们先看第一块。
__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] 包含一个垃圾值（通过死存储消除），这不是你想要的。
程序集规范中缺少标志。在不告诉编译器标志被修改的情况下，编译器可能会假设标志在整个汇编块中都被保留，这将导致编译器在其他地方生成不正确的代码。
不幸的是，这些标志只能用作汇编块的输出或破坏操作数，不能用作输入。所以在正确指定操作数之后大惊小怪，所以你不使用 __volatile__...事实证明，无论如何都没有指定操作数的好方法！
所以这里的建议是你应该至少修复你能修复的操作数，并指定"cc"作为一个破坏者。但是有一些更好的解决方案根本不需要 __volatile__...
解决方案 #1：使用 GMP。
加法的mpn_函数不分配内存。 mpz_ 函数是 mpn_ 函数的包装器，具有一些额外的逻辑和内存分配。
解决方案 #2：将所有内容写入一个汇编块。
如果在一个汇编块中编写整个循环，则不必担心在块之间保留标志。您可以使用汇编宏来执行此操作。请原谅，我不是一个汇编程序员：
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 汇编指令评估循环。您最终将获得 addq 的 1 个副本和 adcq 的 N-1 个副本，尽管如果您查看带有 -S 的 GCC 的汇编输出，您只会看到每个副本之一。汇编程序本身将创建副本，展开循环。
参见要点：https://gist.github.com/depp/966fc1f4d535e31d9725cc71d97daf91
亲爱的 Assembly/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（字符串块），它不是很漂亮（如果好奇请看一下 vli）。图书馆运作良好。
然而我注意到此时不可能在两个 ASM 内联块之间传播状态寄存器的进位标志。这是合乎逻辑的，因为对于编译器在两个块之间生成的任何助记符，寄存器都会被重置（ mov 指令除外（根据我的汇编知识））。
昨天我想到了在两个 ASM 块之间传播进位有点棘手（使用递归算法）。它正在工作，但我认为我很幸运。
#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 with 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 块之间的所有无用指令（在调试模式下它失败了）。
你怎么看？绝对不安全？编译器专家知道它的稳定性吗？
总而言之：我这样做只是为了好玩 :) 是的，GMP 是大型算术的解决方案！
使用 __volatile__ 是一种滥用。
__volatile__的目的是强制编译器在写入的位置发出汇编代码，而不是依靠数据流分析来解决这个问题。如果您在用户 space 中对数据进行普通操作，通常您不应该使用 __volatile__，如果您需要 __volatile__ 来让您的代码工作，这几乎总是意味着您的操作数指定不正确。
是的，操作数指定不正确。我们先看第一块。
__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]包含一个垃圾值（通过死存储消除），这不是你想要的。程序集规范中缺少标志。在不告诉编译器标志被修改的情况下，编译器可能会假设标志在整个汇编块中都被保留，这将导致编译器在其他地方生成不正确的代码。
不幸的是，这些标志只能用作汇编块的输出或破坏操作数，不能用作输入。所以在正确指定操作数之后大惊小怪，所以你不使用 __volatile__...事实证明，无论如何都没有指定操作数的好方法！
所以这里的建议是你应该至少修复你能修复的操作数，并指定"cc"作为一个破坏者。但是有一些更好的解决方案根本不需要 __volatile__...
解决方案 #1：使用 GMP。
加法的mpn_函数不分配内存。 mpz_ 函数是 mpn_ 函数的包装器，具有一些额外的逻辑和内存分配。
解决方案 #2：将所有内容写入一个汇编块。
如果在一个汇编块中编写整个循环，则不必担心在块之间保留标志。您可以使用汇编宏来执行此操作。请原谅，我不是一个汇编程序员：
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 汇编指令评估循环。您最终将获得 addq 的 1 个副本和 adcq 的 N-1 个副本，尽管如果您查看带有 -S 的 GCC 的汇编输出，您只会看到每个副本之一。汇编程序本身将创建副本，展开循环。
参见要点：https://gist.github.com/depp/966fc1f4d535e31d9725cc71d97daf91