Dlaczego prosta pętla jest zoptymalizowana, gdy limit wynosi 959, ale nie 960?

Rozważ tę prostą pętlę:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 959; i++)
    p += 1;
  return p;
}

Jeśli kompilujesz za pomocą gcc 7 (migawka) lub clang (trunk) -march=core-avx2 -Ofast, otrzymasz coś bardzo podobnego do.

.LCPI0_0:
        .long   1148190720              # float 960
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Innymi słowy, po prostu ustawia odpowiedź na 960 bez zapętlania.

Jeśli jednak zmienisz kod na:

float f(float x[]) {
  float p = 1.0;
  for (int i = 0; i < 960; i++)
    p += 1;
  return p;
}

Utworzony zespół faktycznie wykonuje sumę pętli? Na przykład clang daje:

.LCPI0_0:
        .long   1065353216              # float 1
.LCPI0_1:
        .long   1086324736              # float 6
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        vxorps  ymm1, ymm1, ymm1
        mov     eax, 960
        vbroadcastss    ymm2, dword ptr [rip + .LCPI0_1]
        vxorps  ymm3, ymm3, ymm3
        vxorps  ymm4, ymm4, ymm4
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        vaddps  ymm0, ymm0, ymm2
        vaddps  ymm1, ymm1, ymm2
        vaddps  ymm3, ymm3, ymm2
        vaddps  ymm4, ymm4, ymm2
        add     eax, -192
        jne     .LBB0_1
        vaddps  ymm0, ymm1, ymm0
        vaddps  ymm0, ymm3, ymm0
        vaddps  ymm0, ymm4, ymm0
        vextractf128    xmm1, ymm0, 1
        vaddps  ymm0, ymm0, ymm1
        vpermilpd       xmm1, xmm0, 1   # xmm1 = xmm0[1,0]
        vaddps  ymm0, ymm0, ymm1
        vhaddps ymm0, ymm0, ymm0
        vzeroupper
        ret

Dlaczego tak jest i dlaczego jest dokładnie to samo dla clang i gcc?

Limit dla tej samej pętli, jeśli zastąpi floatsię doubleto 479. To jest taki sam dla gcc i brzękiem ponownie.

Zaktualizuj 1

Okazuje się, że gcc 7 (snapshot) i clang (trunk) zachowują się bardzo różnie. clang optymalizuje pętle dla wszystkich limitów mniejszych niż 960, o ile wiem. Z drugiej strony gcc jest wrażliwy na dokładną wartość i nie ma górnej granicy. Na przykład nie optymalizuje pętli, gdy limit wynosi 200 (jak również wiele innych wartości), ale robi, gdy limit wynosi 202 i 20002 (a także wiele innych wartości).

TL; DR

Domyślnie, bieżąca migawka GCC 7 zachowuje się niespójnie, podczas gdy poprzednie wersje mają domyślny limit z powodu PARAM_MAX_COMPLETELY_PEEL_TIMES, który wynosi 16. Można go przesłonić z wiersza poleceń.

Celem ograniczenia jest zapobieganie rozwijaniu się zbyt agresywnej pętli, która może być mieczem obosiecznym .

Wersja GCC <= 6.3.0

Odpowiednią opcją optymalizacji dla GCC jest -fpeel-loops, która jest włączana pośrednio wraz z flagą -Ofast(nacisk jest mój):

Peelingi pętle, dla których jest wystarczająco dużo informacji, że nie rzucają się zbytnio (z informacji zwrotnych na temat profilu lub analizy statycznej ). Włącza również całkowite obieranie pętli (tj. Całkowite usunięcie pętli z małą stałą liczbą iteracji ).

Włączone za pomocą -O3i / lub -fprofile-use.

Więcej szczegółów można uzyskać dodając -fdump-tree-cunroll:

$ head test.c.151t.cunroll 

;; Function f (f, funcdef_no=0, decl_uid=1919, cgraph_uid=0, symbol_order=0)

Not peeling: upper bound is known so can unroll completely

Wiadomość pochodzi od /gcc/tree-ssa-loop-ivcanon.c:

if (maxiter >= 0 && maxiter <= npeel)
    {
      if (dump_file)
        fprintf (dump_file, "Not peeling: upper bound is known so can "
         "unroll completely\n");
      return false;
    }

stąd try_peel_loopfunkcja zwraca false.

Bardziej szczegółowe dane wyjściowe można uzyskać za pomocą -fdump-tree-cunroll-details:

Loop 1 iterates 959 times.
Loop 1 iterates at most 959 times.
Not unrolling loop 1 (--param max-completely-peeled-times limit reached).
Not peeling: upper bound is known so can unroll completely

Możliwe jest modyfikowanie limitów przez granie z parametrami max-completely-peeled-insns=ni max-completely-peel-times=n:

max-completely-peeled-insns

Maksymalna liczba wstawek całkowicie oderwanej pętli.

max-completely-peel-times

Maksymalna liczba iteracji pętli, aby była odpowiednia do całkowitego obierania.

Aby dowiedzieć się więcej na temat insns, zapoznaj się z podręcznikiem GCC Internals .

Na przykład, jeśli kompilujesz z następującymi opcjami:

-march=core-avx2 -Ofast --param max-completely-peeled-insns=1000 --param max-completely-peel-times=1000

kod zamienia się w:

f:
        vmovss  xmm0, DWORD PTR .LC0[rip]
        ret
.LC0:
        .long   1148207104

Szczęk

Nie jestem pewien, co właściwie robi Clang i jak dostosować jego granice, ale jak zauważyłem, można zmusić go do oceny końcowej wartości, zaznaczając pętlę rozwijaniem pragmy , a to całkowicie ją usunie:

#pragma unroll
for (int i = 0; i < 960; i++)
    p++;

skutkuje:

.LCPI0_0:
        .long   1148207104              # float 961
f:                                      # @f
        vmovss  xmm0, dword ptr [rip + .LCPI0_0] # xmm0 = mem[0],zero,zero,zero
        ret

Po przeczytaniu komentarza Sulthana myślę, że:

1. Kompilator w pełni rozwija pętlę, jeśli licznik pętli jest stały (i niezbyt wysoki)

2. Po rozwinięciu kompilator widzi, że operacje sumy można zgrupować w jedną.

Jeśli z jakiegoś powodu pętla nie zostanie rozwinięta (tutaj: wygenerowałaby zbyt wiele instrukcji 1000), operacji nie można grupować.

Kompilator mógł zobaczyć, że rozwinięcie 1000 instrukcji jest równoznaczne z pojedynczym dodaniem, ale opisane powyżej kroki 1 i 2 to dwie oddzielne optymalizacje, więc nie może podjąć „ryzyka” rozwijania, nie wiedząc, czy operacje można grupować (przykład: wywołanie funkcji nie może być grupowane).

Uwaga: jest to przypadek narożny: kto używa pętli, aby ponownie dodać to samo? W takim przypadku nie polegaj na możliwości rozwijania / optymalizacji kompilatora; bezpośrednio napisz właściwą operację w jednej instrukcji.

Bardzo dobre pytanie!

Wydaje się, że osiągnąłeś limit liczby iteracji lub operacji, które kompilator próbuje wbudować podczas upraszczania kodu. Jak udokumentował Grzegorz Szpetkowski, istnieją specyficzne dla kompilatorów sposoby modyfikowania tych ograniczeń za pomocą pragm lub opcji wiersza poleceń.

Możesz także pobawić się Eksploratorem kompilatorów Godbolt, aby porównać, jak różne kompilatory i opcje wpływają na wygenerowany kod: gcc 6.2i icc 17nadal clang 3.9wstawiaj kod dla 960, podczas gdy nie (przy domyślnej konfiguracji Godbolt, w rzeczywistości przestaje on wstawiać na 73).