Dlaczego ICC rozwija tę pętlę w ten sposób i używa lea do arytmetyki?

Question

Patrząc na wygenerowany przez ICC 17 kod do iterowania na std :: unordered_map <> (używając https://godbolt.org), byłem bardzo zdezorientowany.

I destylowanej dół przykład tak:

long count(void** x) 
{ 
    long i = 0; 
    while (*x) 
    { 
    ++i; 
    x = (void**)*x; 
    } 
    return i; 
} 

przygotowanie tego z ICC 17, z flagą -O3 prowadzi do następującego demontażu:

count(void**): 
     xor  eax, eax          #6.10 
     mov  rcx, QWORD PTR [rdi]       #7.11 
     test  rcx, rcx          #7.11 
     je  ..B1.6  # Prob 1%      #7.11 
     mov  rdx, rax          #7.3 
..B1.3:       # Preds ..B1.4 ..B1.2 
     inc  rdx           #7.3 
     mov  rcx, QWORD PTR [rcx]       #7.11 
     lea  rsi, QWORD PTR [rdx+rdx]      #9.7 
     lea  rax, QWORD PTR [-1+rdx*2]      #9.7 
     test  rcx, rcx          #7.11 
     je  ..B1.6  # Prob 18%      #7.11 
     mov  rcx, QWORD PTR [rcx]       #7.11 
     mov  rax, rsi          #9.7 
     test  rcx, rcx          #7.11 
     jne  ..B1.3  # Prob 82%      #7.11 
..B1.6:       # Preds ..B1.3 ..B1.4 ..B1.1 
     ret              #12.10 

porównaniu z oczywistą realizacji (które używają gcc i clang, nawet dla -O3), wydaje się robić kilka rzeczy inaczej:

1. Rozwija pętlę, z dwoma dekresami przed powrotem do pętli - jednak w środku tego jest skok warunkowy.
2. wykorzystuje lea dla niektórych operacji arytmetycznych
3. To zachowuje licznik (Inc RDX) dla każdego dwa iteracji pętli while natychmiast oblicza odpowiednich liczników każdej iteracji (w Rax i RSI)

Jakie są potencjalne korzyści z robienia tego wszystkiego? Zakładam, że może to mieć coś wspólnego z planowaniem?

Dla porównania, jest to kod generowany przez gcc 6.2:

count(void**): 
     mov  rdx, QWORD PTR [rdi] 
     xor  eax, eax 
     test rdx, rdx 
     je  .L4 
.L3: 
     mov  rdx, QWORD PTR [rdx] 
     add  rax, 1 
     test rdx, rdx 
     jne  .L3 
     rep ret 
.L4: 
     rep ret 

Answer 1

Nie jest to świetny przykład, ponieważ pętla jest trywialnie wąskie gardła na opóźnienie pointer-chasing, a nie uop przepustowość lub innego rodzaju pętli narzut. Ale mogą istnieć przypadki, w których posiadanie mniejszej liczby ubytków może pomóc procesorowi out-of-order, być może dalej. Lub możemy po prostu mówić o optymalizacji struktury pętli i udawać, że mają znaczenie, np. dla pętli, która zrobiła coś innego.

---

rozwinięciem jest potencjalnie użyteczny w ogóle, nawet gdy pętla trip-count nie jest obliczalna wyprzedzeniem. (np. w pętli wyszukiwania takiej jak ta, która zatrzymuje się, gdy znajdzie wartownika).Nieodebrane odgałęzienie warunkowe różni się od pobranej gałęzi, ponieważ nie ma żadnego negatywnego wpływu na front-end (jeśli jest przewidywany poprawnie).

Zasadniczo ICC właśnie rozwinęło tę pętlę. Sposób, w jaki używa LEA i MOV do obsługi i, jest dość braindead, ponieważ używał więcej instrukcji niż dwa instrukcje inc rax. (Chociaż powoduje to, że ścieżka krytyczna jest krótsza, na serwerze IvB i późniejszym, które mają zerową latencję, mov r64, r64, więc wykonanie poza kolejnością może przyspieszyć uruchamianie tych układów).

Oczywiście, ponieważ ta szczególna wąska pętla opóźnia śledzenie pointeru, uzyskujesz w najlepszym przypadku długoterminową przepustowość jednego na 4 zegary (opóźnienie obciążenia L1 dla Skylake, dla rejestrów całkowitych), lub jeden na 5 zegarów na większości innych mikroarchitektur Intel. (Nie sprawdzałem podwójnie tych latencji, nie ufaj tym konkretnym liczbom, ale są one w porządku).

IDK, jeśli ICC analizuje łańcuch zależności zależnych od pętli, aby zdecydować, jak zoptymalizować. Jeśli tak, to prawdopodobnie nie rozwinęłoby się wcale, gdyby wiedziało, że robi słabą pracę, gdy próbowało się rozwinąć.

Przez krótki łańcuch, wykonywanie poza kolejnością może być w stanie zacząć coś działa po pętli, jeśli oddział pętli wyjście przewiduje poprawnie. W takim przypadku dobrze jest zoptymalizować pętlę.

Rozwinięcie powoduje również zgłoszenie większej liczby predyktorów gałęzi na problem. Zamiast jednej gałęzi wyjścia z pętlą o długim wzorze (np. Niepobrane po 15 pobranych), masz dwie gałęzie. Dla tego samego przykładu, który nigdy nie był brany pod uwagę, a taki, który bierze 7 razy, a następnie nie jest brany po raz ósmy.

---

Oto co odręcznie rozwinął po dwóch realizacja wygląda:

Fix up i w ścieżce pętli wyjścia dla jednego z punktów wyjścia, dzięki czemu można obsługiwać go tanio wewnątrz pętli.

count(void**): 
    xor  eax, eax    # counter 
    mov  rcx, QWORD PTR [rdi] # *x 
    test  rcx, rcx 
    je  ..B1.6 
.p2align 4 # mostly to make it more likely that the previous test/je doesn't decode in the same block at the following test/je, so it doesn't interfere with macro-fusion on pre-HSW 
.loop: 
    mov  rcx, QWORD PTR [rcx] 
    test  rcx, rcx 
    jz  .plus1 

    mov  rcx, QWORD PTR [rcx] 
    add  rax, 2 
    test  rcx, rcx 
    jnz  .loop 
..B1.6: 
    ret 

.plus1:   # exit path for odd counts 
    inc  rax 
    ret 

Powoduje to, że pętla body 5 fused-domain unosi się, jeśli obie pary TEST/JCC wykonają makro-bezpiecznik. Haswell może tworzyć dwie fuzje w jednej grupie dekodowania, ale wcześniejsze procesory nie.

Implementacja gcc ma tylko 3 odcienie, czyli mniej niż szerokość procesora. Zobacz this Q&A o małych pętlach wydobywających się z bufora pętli. Żaden procesor nie może faktycznie wykonać/wycofać więcej niż jednego pobranego oddziału na zegar, więc nie jest łatwo sprawdzić, jak procesory wysyłają pętle z mniej niż 4 uops, ale najwyraźniej Haswell może wydać pętlę 5-uop na jedną na 1,25 cykli. Wcześniejsze procesory mogą wydać je tylko raz na 2 cykle.

Answer 2

1. Nie ma jednoznacznej odpowiedzi, dlaczego to robi, ponieważ jest zastrzeżona kompilator. Tylko intel wie, dlaczego. Powiedział, że kompilator Intel jest często bardziej agresywny w optymalizacji pętli. To nie znaczy, że jest lepiej. Widziałem sytuacje, w których agresywny inline inteligenta prowadzi do gorszej wydajności niż clang/gcc. W takim przypadku musiałem wyraźnie zakazać wprowadzania w niektórych witrynach z telefonami. Podobnie, czasami trzeba zabronić rozwijania się poprzez pragmy w Intel C++, aby uzyskać lepszą wydajność.

2. lea to szczególnie przydatna instrukcja. Umożliwia jedną zmianę, dwa dodatki i jeden ruch w jednej instrukcji. Jest to znacznie szybsze niż wykonanie tych czterech operacji oddzielnie. Jednak nie zawsze robi to różnicę. A jeśli lea jest używany tylko do dodawania lub przenoszenia, może być lepszy lub nie. Więc widać w 7.11 wykorzystuje ruch, podczas gdy w ciągu najbliższych dwóch liniach lea służy do zrobienia dodatek plusa przenieść, a dodawanie, zmianę, plus ruch

3. nie widzę tam tu opcjonalne korzyści