重叠寄存器错误

Question

内联汇编代码替换其中一个for循环中的C++语句.

有时它神奇地工作并产生正确的结果 - 使用基数排序排序的数组.另一次Xcode生成一个Thread 1: EXC_BAD_ACCESS (code=1, address=0x1eccccccccd)错误,我incq (%[count], %%rdx, 4)使用反汇编视图追溯到行.

我的理解

反汇编视图incq (%[count], %%rdx, 4)为incq (%rax,%rdx,4).这可能意味着相同的寄存器用于不同的操作数(%%rax已在线使用movq (%[array], %%rcx, 4), %%rax),问题在于此处:: [array] "r" (array), [count] "r" (count), "b" (digit), "c" (i).

我不明白的是

如何管理寄存器,以便我可以使用足够的寄存器(分配给输入操作数以及后面的正文代码)并且它们不会同时重叠.我尝试了几种组合,但没有一种有效.

void countingSort(int array[], int length, int digit) {
    int i, count[10] = { };
    int sorted[length];

    // Store number of occurrences in count[].
    // for (i = 0; i < length; i++)
    //     count[ (array[i] / digit) % 10 ]++;

    for (i = 0; i < length; i++)
        asm volatile (
                      "movq (%[array], %%rcx, 4), %%rax \n\t"

                      "xorq %%rdx, %%rdx \n\t"
                      "divq %%rbx \n\t"
                      "movq $10, %%rbx \n\t"
                      "xorq %%rdx, %%rdx \n\t"
                      "divq %%rbx \n\t"

                      "incq (%[count], %%rdx, 4) \n\t"

                      :: [array] "r" (array), [count] "r" (count), "b" (digit), "c" (i)
                      : "memory"
        );

    // ...
}

完整代码:

#include<iostream>
using namespace std;

void print(int array[], int length) {
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
}

int findMax(int array[], int length) {
    int max = array[0];
    for (int i = 1; i < length; i++)
        if (array[i] > max)
            max = array[i];
    return max;
}

void countingSort(int array[], int length, int digit) {
    int i = 0, count[10] = { };
    int sorted[length];

    // Store number of occurrences in count[].
    // for (i = 0; i < length; i++)
    //     count[ (array[i] / digit) % 10 ]++;

    for (i = 0; i < length; i++)
        asm volatile (
                      "movq (%[array], %%rcx, 4), %%rax \n\t"

                      "xorq %%rdx, %%rdx \n\t"
                      "divq %%rbx \n\t"
                      "movq $10, %%rbx \n\t"
                      "xorq %%rdx, %%rdx \n\t"
                      "divq %%rbx \n\t"

                      "incq (%[count], %%rdx, 4) \n\t"

                      :: [array] "r" (array), [count] "r" (count), "b" (digit), "c" (i)
                      : "memory"
        );

    // Change count[i] so that count[i] now contains actual
    // position of the digit in sorted[].
    // for (i = 1; i < 10; i++)
    //     count[i] += count[i - 1];

    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the sorted array.
    for (i = length - 1; i >= 0; i--) {
        sorted[count[ (array[i] / digit) % 10 ] - 1] = array[i];
        count[ (array[i] / digit) % 10 ]--;
    }

    // Copy the sorted array to array[].
    for (i = 0; i < length; i++)
        array[i] = sorted[i];
}

void radixSort(int array[], int length) {
    // Maximum number helps later when counting number of digits.
    int max = findMax(array, length);

    // Do Counting sort for every digit.
    for (int digit = 1; max / digit > 0; digit *= 10)
        countingSort(array, length, digit);
}

int main() {
    int array[] = { 2, 4928, 48, 72, 280, 4, 66, 3, 1, 0, 4829 };
    int length = sizeof(array) / sizeof(array[0]);

    radixSort(array, length);
    print(array, length);
    return 0;
}

Answer 1

看起来这是一个课堂作业.在现实世界中,这不会通过内联汇编来完成.

问题:

• digit将10移动到RBX时,通过覆盖关联的寄存器来破坏.在C++编译器不知道这一点,因为你再没提RBX的限制被修改.编译器可能假设在内联汇编之前和之后RBX是相同的.
• 由于您使用的是32位整数,因此可以使用long而不是quadword除法.
• DIV是未签约的师, IDIV是签约师.您的 C++代码使用带符号的数字.这真的无关紧要,因为这个代码会在数组中以负数碰撞.如果您使用签名分区,您可以使用 CDQ将 EAX扩展到 EDX.
• 使用汇编模板通过编译器选择的寄存器传递除数(10).
• 您可以i转换为long约束中的类型.在64位代码中long是64位,并且在组装模板内引用时,默认情况下将使编译器使用64位寄存器.
• 整数是4个字节宽,而不是8.当访问与整数数组关联的内存时,您希望使用读取4个字节的指令.您使用的MOVQ和INCQ指令移动8个字节.您将需要考虑MOVL和INCL或其他移动4个字节的等效项.如果要将带符号的4字节值从内存移动到64位寄存器,可以使用MOVSXD.在AT&T语法中,最好使用MOVSLQ/MOVSL或MOVSXL,因为CLANG和GCC/G ++都能理解它们.
• 允许编译器为输入和输出操作数选择寄存器,而不是在汇编模板中对它们进行硬编码.在您的代码中,唯一一个由其中一条指令隐式修改的寄存器,我们无法做太多关于RDX.将其添加到clobbers列表中,以便编译器知道其内容可能会更改.

修改后的代码可能如下所示:

    asm (
             "movslq (%[array], %[index], 4), %%rax \n\t"
             "cdq \n\t"               /* Sign extend eax into edx */
             "idivl %[digit] \n\t"    /* array[i]/digit */
             "cdq \n\t"               /* Sign extend eax into edx */
             "idivl %[divisor] \n\t"  /* (array[i] / digit) mod 10 */
             "incl (%[count], %%rdx, 4)"
              : "=m" (*(int (*)[]) count) /* instead of memory clobber */
              : [divisor] "r" (10), [array] "r" (array), [count] "r" (count),
                [digit] "r" (digit), [index] "r" ((long)i),
                "m" (*(const int (*)[]) array) /* instead of memory clobber */
              : "rax", "rdx", "cc"
    );

我还删除了内存clobber并告诉它该数组是一个将被修改的输出内存操作数.这在GCC内联汇编文档中进行了讨论.由于除了约束和clobbers中指定的组件模板之外没有其他副作用,我们不需要使用volatile.

您可以删除第一个MOV指令并使用中间变量.这将允许您array[i]通过EAX通过约束传递当前值.由于EAX现在处于自己的输入/输出约束(使用+)中,我们可以将其从clobbers中删除.代码可能如下所示:

    int curval;
    asm (
             "cdq \n\t"               /* Sign extend eax into edx */
             "idivl %[digit] \n\t"    /* array[i]/digit */
             "cdq \n\t"               /* Sign extend eax into edx */
             "idivl %[divisor] \n\t"  /* (array[i] / digit) mod 10 */
             "incl (%[count], %%rdx, 4)"
             : "=m" (*(int (*)[]) count), /* instead of memory clobber */
               "+&a" (curval = array[i])  /* Early clobber, we modify it
                                             before all inputs processed */
             : [divisor] "r" (10), [array] "r" (array), [count] "r" (count),
               [digit] "r" (digit), [index] "r" ((long)i)
             : "rdx", "cc"
    );

如果上面的答案过于复杂,并且您想要修复代码中的直接问题,那么最小的一组更改可能如下所示:

    asm volatile (
                  "movl (%[array], %%rcx, 4), %%eax \n\t"
                  "xorq %%rdx, %%rdx \n\t"
                  "divq %%rbx \n\t"
                  "movq $10, %%rsi \n\t"
                  "xorq %%rdx, %%rdx \n\t"
                  "divq %%rsi \n\t"
                  "incl (%[count], %%rdx, 4) \n\t"
                  :: [array] "r" (array), [count] "r" (count), "b" (digit), "c" ((long)i)
                  : "memory", "rax", "rdx", "rsi"
    );

• 我们digit通过使用另一个寄存器来修改包含的寄存器以存储10来进行除法.如果优化编译器假定寄存器的值没有改变,则修改列为仅作为输入约束的寄存器可能会导致未定义的行为.编译器必须知道已更改的内容.
• 由于我们的汇编模板现在修改了RAX,RDX和RSI,我们必须将它们添加到clobber列表中.如果它们没有与之关联的输出约束,则它们需要位于clobber列表中.
• 我们使用MOVL指令将数组中的4字节整数移动到EAX.当指令的目标寄存器是32位寄存器时,CPU自动将其扩展到64位寄存器的高32位.
• INCQ更改为INCL以更新4字节存储器地址.

备注:

• 该"cc"撞被有效地忽略Ç/C++靶向x86和x96-64平台时."cc"如果模板确实破坏了标志,那么将其指定为clobber 并不是一个坏主意,就像在此代码中的情况一样.如果您曾经在处理器上工作,那么这是一个好习惯,其中必须在clobber列表中明确指定要修改的标志.
• 如果程序集模板没有输出(或输入/输出)约束,则它是隐式易失性的,并且volatile不需要修饰符.