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

131

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).

c  gcc  optimization  clang 
— eleanora
źródło
3
Sulthan prawdopodobnie ma na myśli to, że 1) kompilator rozwija pętlę i 2) po rozwinięciu widzi, że operacje sumujące można zgrupować w jedną. Jeśli pętla nie zostanie rozwinięta, operacji nie można grupować.
— Jean-François Fabre
3
Posiadanie nieparzystej liczby pętli sprawia, że ​​rozwijanie jest bardziej skomplikowane, kilka ostatnich iteracji należy wykonać specjalnie. To może wystarczyć, aby ustawić optymalizator w tryb, w którym nie może już rozpoznać skrótu. Jest całkiem prawdopodobne, że najpierw musi dodać kod dla specjalnego przypadku, a następnie musiałby go ponownie usunąć. Używanie optymalizatora między uszami jest zawsze najlepsze :)
— Hans Passant
3
@HansPassant Jest również zoptymalizowany dla dowolnej liczby mniejszej niż 959.
— eleanora
6
Czy nie byłoby to zwykle zrobione z eliminacją zmiennej indukcyjnej, zamiast rozwinąć szaloną kwotę? Rozwinięcie o współczynnik 959 jest szalone.
— harold
4
@eleanora Grałem z tym eksploratorem kompilacji i wydaje się, że zachodzi następująca sytuacja (mowa tylko o migawce gcc): Jeśli liczba pętli jest wielokrotnością 4 i co najmniej 72, pętla nie jest rozwijana (a raczej rozwijana przez współczynnik 4); w przeciwnym razie cała pętla jest zastępowana przez stałą - nawet jeśli liczba pętli wynosi 2000000001. Moje podejrzenie: przedwczesna optymalizacja (np. przedwczesna „hej, wielokrotność 4, to jest dobre do rozwijania”), która blokuje dalszą optymalizację vs. bardziej szczegółowe „O co w ogóle chodzi z tą pętlą?”)
— Hagen von Eitzen,

Odpowiedzi:

88

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
— Grzegorz Szpetkowski
źródło
Dziękuję za tę bardzo miłą odpowiedź. Jak zauważyli inni, gcc wydaje się być wrażliwy na dokładny rozmiar limitu. Na przykład nie udało się wyeliminować pętli 912 godbolt.org/g/EQJHvT . Co w takim przypadku mówi fdump-tree-cunroll-details?
— eleanora
W rzeczywistości nawet 200 ma ten problem. To wszystko znajduje się w migawce gcc 7, którą zapewnia Godbolt. godbolt.org/g/Vg3SVs To nie dotyczy w ogóle clang.
— eleanora
13
Wyjaśniasz mechanikę peelingu, ale nie wyjaśniasz, jakie znaczenie ma wartość 960 ani dlaczego w ogóle istnieje limit
— MM,
1
@MM: Zachowanie peeling jest zupełnie inne w GCC 6.3.0 i najnowszym snaphost. W przypadku tego pierwszego mocno podejrzewam, że zakodowany limit jest wymuszony przez PARAM_MAX_COMPLETELY_PEEL_TIMESparametr, który jest określony w /gcc/params.def:321wartości 16.
— Grzegorz Szpetkowski
14
Możesz wspomnieć, dlaczego GCC celowo ogranicza się w ten sposób. W szczególności, jeśli zbyt agresywnie rozwijasz pętle, binarny staje się większy i mniej prawdopodobne jest, że zmieścisz się w pamięci podręcznej L1. Chybienia w pamięci podręcznej są potencjalnie dość drogie w porównaniu do zaoszczędzenia kilku warunkowych skoków, zakładając dobre przewidywanie gałęzi (które będziesz mieć dla typowej pętli).
— Kevin
19

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.

— Jean-François Fabre
źródło
1
czy możesz skupić się na tej not too highczęści? Mam na myśli, dlaczego nie ma ryzyka w przypadku 100? Coś zgadłem ... w moim komentarzu powyżej ... może to być powód?
— user2736738
Myślę, że kompilator nie jest świadomy niedokładności zmiennoprzecinkowej, którą może wywołać. Myślę, że to tylko limit rozmiaru instrukcji. Masz max-unrolled-insnsobokmax-unrolled-times
— Jean-François Fabre
Ach, to była taka moja myśl lub domysł ... Chciałbym uzyskać bardziej jasne uzasadnienie.
— user2736738
5
Co ciekawe, jeśli zmienisz na floatan int, kompilator gcc jest w stanie wzmocnić pętlę niezależnie od liczby iteracji, dzięki optymalizacji zmiennych indukcyjnych ( -fivopts). Ale te wydają się nie działać dla floats.
— Tavian Barnes
1
@CortAmmon Racja, i przypominam sobie, że czytałem kilka osób, które były zaskoczone i zdenerwowane, że GCC używa MPFR do precyzyjnego obliczania bardzo dużych liczb, dając raczej inne wyniki niż równoważne operacje zmiennoprzecinkowe, które kumulowałyby błąd i utratę precyzji. Pokazuje, że wiele osób oblicza zmiennoprzecinkowe w niewłaściwy sposób.
— Zan Lynx,
12

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).

— chqrlie
źródło
Zredagowałem pytanie, aby wyjaśnić wersje gcc i clang, których używałem. Zobacz godbolt.org/g/FfwWjL . Na przykład używam -Ofast.
— eleanora
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.