gcc对-mavx优化的失败？

Question

编辑部分解决方案如下(编辑2)，但我仍然有一个问题(见结尾)

我试图用gcc-4.9.2编译以下C程序，在Windows7上运行32位，运行在奔腾G3220上(根据)。如果我正确理解，这个处理器没有AVX扩展，所以很自然地会发生一些事情，我只是不确定到底发生了什么。起初，我是在和gcc玩优化，然后我就“意外地”尝试了-mavx。

下面的程序计算数字0的排列。n-1 (以n作为参数)按字典顺序排列，以及每一排列的秩(其在这个顺序顺序中的位置)和"unrank“(从秩中恢复置换)，并检查所有这些都是正确的。它应该只打印“确定”或“错误”在最后。

• 使用gcc -O3，程序使用我检查过的所有整数输入(1 <= n <= 11)正确运行。
• 使用gcc -O3 -mavx，它对1 <= n <= 7正确运行，对于n >= 8，它不打印任何东西，实际上它什么也不做(退出之前几乎没有延迟)。我没有收到来自程序或Windows的消息(我本以为可能会有一个未知指令的崩溃，但它没有发生)。

(在另一台具有Windows764位、内核为i5和gcc-4.9.2的计算机上，该程序似乎在没有-mavx的情况下运行得很好，无论是用32版本还是用http://sourceforge.net/projects/mingw-w64/files/Toolchains%20targetting%20Win64/Personal%20Builds/mingw-builds/4.9.2/threads-win32/seh/编译)

我不明白的是，为什么它对某些输入值正确运行，而对于其他输入值则失败。有人对这件事有什么暗示吗？

下面是完整的程序，后面是一个较短的程序，也有同样的问题。

#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的评论，下面是一个具有相同问题的更短的程序。我删除了对输入值的所有检查，删除了所有级别/未排序的内容，并将malloc/free替换为大小为20的数组(现在只有一个，因为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指令和对齐以及实际上所有其他指令：

_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。

可以通过在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之间，它们用于构建初始'a‘的for循环，即数组{0，1，…，n-1}。实际上，AVX指令一次用于构建多个'a‘元素(我猜是4个)，如果'a’的长度不是4的倍数，那么在调用L9的puts("Z")之前，在调用L9的puts(“Z”)之前，还有一个额外的步骤(在L9和L3之间)，然后调用next_perm(n，a)；在L3。因此，问题非常简单:如果n足够小，那么AVX循环实际上是不运行的，并且没有错误。这里最大的有效n是4，但是gcc的不同运行方式不同，它看起来有点随机(我昨天得到了8)。

LC0和LC4标签指向由AVX指令使用的四个元素的两个数组: 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