c - 使用 gcc 优化 -mavx 失败？

Question

编辑 下面的部分解决方案(编辑 2)，但我还有一个问题(见最后)

我正在尝试使用 gcc-4.9.2 编译以下 C 程序，在 Windows 7 上，32 位，在 Pentium G3220 上运行(根据 Windows 系统信息)。如果我理解正确的话，这个处理器没有 AVX 扩展，所以很自然会发生一些事情，我只是不确定到底是什么。最初，我正在使用 gcc 进行优化，我尝试了 -mavx 而不是“偶然”。

以下程序按字典顺序计算数字 0 ... n-1(以 n 作为参数给出)的排列，以及每个排列的排名(其在此顺序中的位置)和“unrank”(从排名中恢复排列) )，并检查所有这些是否正确。最后应该只打印“OK”或“Error”。

与 gcc -O3 ，程序在我检查过的所有整数输入下正确运行(1 <= n <= 11)。

与 gcc -O3 -mavx ，它在 1 <= n <= 7 时正确运行，对于 n >= 8，它什么也不打印，实际上它什么也不做(退出前几乎没有延迟)。我没有从程序或 Windows 收到任何消息(我原以为可能会因未知指令而崩溃，但它没有发生)。

(在另一台装有 Windows 7 64 位的计算机上，在 core-i5 和相同的 gcc-4.9.2 上，当在 32 或 64 bits 中编译时，该程序在没有 -mavx 的情况下似乎运行良好)

我不明白的是为什么它对某些输入值运行正确，而对其他输入值却失败。有人对此有任何提示吗？

这是完整的程序，然后是一个具有相同问题的较短程序。

#include <stdlib.h>
#include <stdio.h>

#define SWAP(a,b) {int c; c = a; a = b; b = c;}

int next_perm(int n, int a[n]) {
    int i, j, k;
    for(i = n - 1; i > 0 && a[i - 1] > a[i]; i--);
    for(j = i, k = n - 1; j < k; j++, k--) SWAP(a[j], a[k]);
    if(i == 0) return 0;
    for(j = i--; a[j] < a[i]; j++);
    SWAP(a[i], a[j]);
    return 1;
}

#undef SWAP

void copyvec(int n, int dst[n], int src[n]) {
    int i;
    for(i = 0; i < n; i++) {
        dst[i] = src[i];
    }
}

int eqvec(int n, int a[n], int b[n]) {
    int i;
    for(i = 0; i < n; i++) {
        if(a[i] != b[i]) return 0;
    }
    return 1;
}

int rank(int n, int a[n]) {
    int v[n], i, j, r;
    v[n - 1] = 1;
    for(j = n - 2; j >= 0; j--) v[j] = v[j + 1]*(n - 1 - j);
    for(r = i = 0; ; i++) {
        for(j = i; j < n; j++) {
            if(a[j] > j) goto cont;

        }
        return r;
cont:
        i = j;
        r += v[i]*(a[i] - i);
        for(j = i + 1; j < n; j++) {
            if(a[j] < a[i]) a[j]++;
        }
    }
}

void unrank(int n, int a[n], int p) {
    int v[n], i, j, r, s;
    v[n - 1] = 1;
    for(i = n - 2; i >= 0; i--) v[i] = v[i + 1]*(n - 1 - i);
    p %= n*v[0];
    for(i = 0; i < n; i++) a[i] = i;
    for(i = 0; p > 0; i++) {
        for(; v[i] > p; i++);
        r = p/v[i];
        p %= v[i];
        for(s = a[j = i + r]; j >= i; j--) a[j] = a[j - 1];
        a[i] = s;
    }
}

int main(int argc, char **argv) {
    int n, i, r, s = 0, q = 0;
    int *a = NULL, *b = NULL, *c = NULL;
    if(argc == 2 && (n = strtol(argv[1], NULL, 0)) > 0) {
        a = malloc(n*sizeof(int));
        b = malloc(n*sizeof(int));
        c = malloc(n*sizeof(int));
        if(!a || !b || !c) {
            puts("Unable to allocate memory");
            goto end;
        } else {
            for(i = 0; i < n; i++) a[i] = i;
            do {
                copyvec(n, b, a);
                r = rank(n, b);
                unrank(n, c, r);
                q |= s++ != r || !eqvec(n, a, c);
            } while(next_perm(n, a));
            puts(q?"Error":"OK");
        }
    } else {
        puts("perm n - Check all permutations of {0 ... n - 1}, with n > 0");
    }
end:
    if(a) free(a);
    if(b) free(b);
    if(c) free(c);
    return 0;
}

编辑

根据 Brian Cain 的评论，这里有一个较短的程序，但存在同样的问题。我删除了对输入值的所有检查，所有等级/非等级内容，并用大小为 20 的数组替换了 malloc/free(现在只有一个，因为不再使用 b 和 c)。现在程序只用 while(next_perm(n, a)); 计算排列循环，对它们不做任何事情。不过，它最后仍然应该打印“OK”，因为 q 的值在初始 q=0 后不会改变。

#include <stdlib.h>
#include <stdio.h>

#define SWAP(a,b) {int c; c = a; a = b; b = c;}

int next_perm(int n, int a[n]) {
    int i, j, k;
    for(i = n - 1; i > 0 && a[i - 1] > a[i]; i--);
    for(j = i, k = n - 1; j < k; j++, k--) SWAP(a[j], a[k]);
    if(i == 0) return 0;
    for(j = i--; a[j] < a[i]; j++);
    SWAP(a[i], a[j]);
    return 1;
}

#undef SWAP

int main(int argc, char **argv) {
    int n, i, r, s = 0, q = 0, a[20];
    n = strtol(argv[1], NULL, 0);
    for(i = 0; i < n; i++) a[i] = i;
    while(next_perm(n, a));
    puts(q?"Error":"OK");
    return 0;
}

编辑 2:汇编输出的解释

我还添加了 gcc 的反汇编输出(在 Intel 语法中)，发现于 gcc -O3 -mavx -S -masm=intel和 gcc-4.9.2(有关编译器的实际二进制文件，请参见上面的链接)。但是，它需要一些工作，因为按原样，gcc 会将调用内联到 next_perm，并且可读性较差。我也删除了 CFI directives和对齐以及实际上所有其他指令，以提高可读性:

_next_perm:
LFB0:
    push    ebp
    push    edi
    push    esi
    push    ebx
    mov ecx, DWORD PTR [esp+20]
    mov edx, DWORD PTR [esp+24]
    lea eax, [ecx-1]
    test    eax, eax
    jle L12
    mov edi, DWORD PTR [edx-4+ecx*4]
    cmp DWORD PTR [edx-8+ecx*4], edi
    mov ecx, eax
    jg  L5
    jmp L11
L28:
    mov esi, DWORD PTR [edx+ecx*4]
    cmp DWORD PTR [edx-4+ecx*4], esi
    jle L27
L5:
    sub ecx, 1
    jne L28
L4:
    mov ebx, ecx
L7:
    mov esi, DWORD PTR [edx+ebx*4]
    mov edi, DWORD PTR [edx+eax*4]
    mov DWORD PTR [edx+ebx*4], edi
    mov DWORD PTR [edx+eax*4], esi
    add ebx, 1
    sub eax, 1
    cmp ebx, eax
    jl  L7
L2:
    xor eax, eax
    test    ecx, ecx
    je  L23
L11:
    sal ecx, 2
    lea esi, [edx+ecx]
    lea ebp, [edx-4+ecx]
    mov ebx, DWORD PTR [esi]
    mov edi, DWORD PTR [ebp+0]
    cmp edi, ebx
    jle L9
    lea eax, [edx+4+ecx]
L10:
    mov esi, eax
    add eax, 4
    mov ebx, DWORD PTR [eax-4]
    cmp ebx, edi
    jl  L10
L9:
    mov DWORD PTR [ebp+0], ebx
    mov eax, 1
    mov DWORD PTR [esi], edi
L23:
    pop ebx
    pop esi
    pop edi
    pop ebp
    ret
L27:
    cmp eax, ecx
    jg  L4
    jmp L11
L12:
    mov ecx, eax
    jmp L2

汇编输出有无 -mavx 是一样的，除了标签号:没有 AVX 指令，这意味着问题实际上出在 main .

这可以通过添加一些 puts 来检查。在主要:

int main(int argc, char **argv) {
    int n, i, q = 0, a[20];
    puts("X");
    n = strtol(argv[1], NULL, 0);
    puts("Y");
    for(i = 0; i < n; i++) a[i] = i;
    puts("Z");
    while(next_perm(n, a));
    puts(q?"Error":"OK");
    return 0;
}

然后，程序在失败时仅打印 X 和 Y，因此问题来自用于在 Y 和 Z 之间的 for 循环中构建“a”的 AVX 指令。

这是 main 的汇编输出, 再次没有指令(LC2 指向“Y”，LC3 指向“Z”)。 main 的汇编输出中唯一的 AVX 指令在这两个 puts 之间，它们用于 for构建初始“a”的循环，即数组 {0, 1, ..., n-1}。实际发生的情况是，AVX 指令用于一次构建 'a' 的多个元素(我猜是 4 个)，如果 'a' 的长度不是 4 的倍数，那么还有一个额外的步骤(在L4 和 L9)，在 L9 调用 puts("Z") 之前，然后是 while(next_perm(n, a));在 L3。因此，问题很简单:如果 n足够小，那么AVX循环实际上并没有运行，并且没有错误。这里最大有效 n是 4，但它在不同的 gcc 运行之间有所不同，它似乎有点随机(我昨天得到了 8)。

LC0 和 LC4 标签指向 AVX 指令使用的两个包含 4 个元素的数组:LC0 是 {0,1,2,3}，LC4 是 {4,4,4,4}。难怪他们为什么在这里，即使没有对 AVX 的深入了解，它也闻起来像一个展开的循环 :-)

_main:
    push    ebp
    mov ebp, esp
    push    edi
    push    esi
    push    ebx
    and esp, -16
    sub esp, 96
    call    ___main
    mov DWORD PTR [esp], OFFSET FLAT:LC1
    call    _puts
    mov eax, DWORD PTR [ebp+12]
    mov DWORD PTR [esp+8], 0
    mov DWORD PTR [esp+4], 0
    mov eax, DWORD PTR [eax+4]
    mov DWORD PTR [esp], eax
    call    _strtol
    mov DWORD PTR [esp], OFFSET FLAT:LC2
    mov ebx, eax
    call    _puts
    test    ebx, ebx
    jle L17
    lea edx, [ebx-4]
    lea ecx, [ebx-1]
    shr edx, 2
    add edx, 1
    cmp ecx, 3
    lea eax, [0+edx*4]
    jbe L10
    vmovdqa xmm1, XMMWORD PTR LC4
    lea esi, [esp+16]
    xor ecx, ecx
    vmovdqa xmm0, XMMWORD PTR LC0
L5:
    mov edi, ecx
    add ecx, 1
    sal edi, 4
    cmp edx, ecx
    vmovaps XMMWORD PTR [esi+edi], xmm0
    vpaddd  xmm0, xmm0, xmm1
    ja  L5
    cmp ebx, eax
    je  L9
L4:
    lea edx, [eax+1]
    mov DWORD PTR [esp+16+eax*4], eax
    cmp ebx, edx
    jle L9
    mov DWORD PTR [esp+16+edx*4], edx
    lea edx, [eax+2]
    cmp ebx, edx
    jle L9
    add eax, 3
    mov DWORD PTR [esp+16+edx*4], edx
    cmp ebx, eax
    jle L9
    mov DWORD PTR [esp+16+eax*4], eax
L9:
    mov DWORD PTR [esp], OFFSET FLAT:LC3
    call    _puts
L3:
    mov DWORD PTR [esp+4], esi
    mov DWORD PTR [esp], ebx
    call    _next_perm
    test    eax, eax
    jne L3
    mov DWORD PTR [esp], OFFSET FLAT:LC5
    call    _puts
    lea esp, [ebp-12]
    xor eax, eax
    pop ebx
    pop esi
    pop edi
    pop ebp
    ret
L10:
    xor eax, eax
    lea esi, [esp+16]
    jmp L4
L17:
    lea esi, [esp+16]
    jmp L9

现在，我明白实际发生了什么，但还有一个问题:为什么当程序尝试运行 AVX 指令时没有任何错误消息？它只是退出，或者被杀死，但没有任何提示出现问题。

Answer 1

This code always results in:
where parameter = n
a[] = {0,0,2, 3, ...,n-2,n-1}
b[] = {n-1, n-1, ... , n-1}
c[] = {n-1, n-2, ... , 0}
when it reaches the above conditions,
then it exits with "OK"

the amount of time spent executing the code 
climbs at an exponential rate
as the value of the parameter is increased