Czy ręcznie napiszemy kod optymalniej niż kompilator?

Istnieje taki mit, że jeżeli chcemy napisać mega optymalny kod, gdzie liczy się każda instrukcja – powinniśmy napisać go ręcznie w asemblerze. Kompilator nie poradzi sobie z tym zadaniem tak dobrze jak człowiek. Zawsze doda jakieś bezsensowne instrukcje trwoniąc w ten sposób cenny czas.

Ja się z tym całkowicie nie zgadzam i w swoich materiałach często pokazuję jak kompilator robi różne optymalizacje, a nam się nie udaje go pobić. Albo kiedy ręcznie robimy w kodzie błędy, a kompilator generuje kod poprawnie. Nie inaczej będzie tym razem, ale nie uprzedzajmy faktów.

Sam wielokrotnie łapałem się na tym, że posądzałem kompilator o bezsensowne działanie. A potem okazywało się, że nie miałem racji. Dlatego teraz staram się nie rzucać przedwcześnie oskarżeń. Z drugiej strony widzę, że nie byłem sam. Pod moimi materiałami nieraz pojawiają się dyskusje o bezsensownych optymalizacjach kompilatora. I zwykle staję wtedy w obronie maszyny.

W dzisiejszym artykule pokażę Case Study przypadku, gdzie kompilator GCC na ARM Cortex-M robi dziwne i “nieoptymalne” operacje.

Czy kompilator pisze optymalny kod w asemblerze?

Weźmy prosty przykład:

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

uint32_t a = 1234567;

void fun1(void)
{
    a += 7654321;
}

Po wklepaniu w Godbolta otrzymamy coś takiego:

Jeżeli chcesz się samodzielnie pobawić – tutaj link do przykładu w Godbolcie.

Kompilator jest jakiś upośledzony. Najpierw robi jakieś niepotrzebne operacje na rejestrze R7 (linie 4-5). Potem ma dodać liczbę do zawartości zmiennej a. I zamiast to zrobić jak człowiek – najpierw wczytuje do R3 adres zmiennej a (linia 6), do R2 wartość zmiennej a za pomocą adresu (linia 7) a potem do R3 wpisuje liczbę, którą chce dodać (linia 8). Ale nie jak człowiek za pomocą instrukcji move (MOV) tylko wczytuje ją z pamięci (LDR).

Przecież pierwsze czego uczymy się na laborkach z asemblera to korzystanie z instrukcji MOV. Zapisalibyśmy to:

mov R3, 7654321

Albo zamiast zapisywać zmienną do rejestru użylibyśmy stałej liczbowej od razu podczas dodawania:

ADD R3, R2, 7654321

A kompilator nie dość, że utrudnia sobie życie wykorzystując nieintuicyjne instrukcje, to jeszcze musi zapisać stałą w pamięci FLASH.

A na koniec jeszcze znowu robi te głupie operacje na R7 (linie 12-14). Teraz jeszcze dodał NOPa (no operation). Chyba po to, żeby pokazać jak nie szanuje pojedynczych instrukcji. 

W każdym razie widzimy wyraźnie, że kompilator wcale nie tworzy optymalnego kodu. Ręcznie napisalibyśmy to lepiej, tylko nie chce nam się przepisywać wszystkiego do asemblera. Ale przy super ważnych funkcjach, które muszą być optymalne już na pewno nam się opłaci przepisać je w asemblerze.

Wersja z włączoną optymalizacją

Nie da się ukryć – kompilator dodał tutaj kilka niepotrzebnych instrukcji. Na przykład operacje na R7 to obsługa Stack Frame zgodnie z ARM Procedure Call Standard czyli zasadami tłumaczenia funkcji C na asemblera. W tej funkcji Stack Frame nie jest nam do niczego potrzebny, więc te operacje są nadmiarowe.

Tak – kompilator zachowuje się tutaj nieoptymalnie. Ale jak nie włączyliśmy optymalizacji, to chyba nie możemy mieć o to pretensji, prawda?

Zobaczmy więc co się dzieje z włączoną optymalizacją.

Już lepiej. Przynajmniej pozbyliśmy się R7. Używanie rejestrów w funkcji też jest bardziej efektywne. Ale problem z obsługą stałej dalej został. Najprostsza implementacja z użyciem MOV pozwoliłaby nam uniknąć odczytu z pamięci, a użycie w stałej w instrukcji ADD dodatkowo oszczędziłoby jedną instrukcję.

Co to za optymalizacja, którą bez żadnego wysiłku możemy pokonać po pierwszym spojrzeniu na kod?

Zobaczmy jeszcze przykład z innymi stałymi:

Super – tutaj kompilator domyślił się, że można użyć stałą od razu w instrukcji ADD. Ale miał niezłą fantazję, bo rozbił to na dwie operacje. Jak on śmie nazywać to OPTYMALIZACJĄ?

Ok wystarczy tych optymalizacji. Wniosek jest prosty – kompilator potyka się o własne nogi. Nawet jak coś zoptymalizuje, to i tak zrobi coś głupiego. Nic nie zastąpi człowieka. Ale szkoda nam czasu na ręczną optymalizację i tylko dlatego bierzemy to co jest.

Ręcznie napiszę to lepiej

Aby zadać maszynie ostateczny cios musimy jeszcze tylko sami napisać to lepiej. Nic prostszego. Kopiujemy poprzedni kod, podmieniamy dwie instrukcje ADD na jedną:

add R3, #2000000

Kompilujemy i…

Error: invalid constant (1e8480) after fixup

A tutaj link do Godbolta.

No dobra, nie udało się z addem, próbujemy z movem.

I znowu to samo.

Powtarzamy dla wszystkich stałych używanych w tym przykładzie: 1000000, 2000000, 1234567, 7654321, 0x00FFAA55, 0x55AAFF00. Ciągle to samo – nie możemy wpisać stałej do rejestru jak ludzie.

Dlaczego tak się dzieje?

Stałe w Cortex-M

Okazuje się, że stałe liczbowe na poziomie asemblera w architekturze ARM Cortex-M mają spore ograniczenia. Nie możemy tak po prostu użyć sobie dowolnej liczby 32-bitowej. W STM32 Core Programming Manualu znajdziemy taki akapit:

Constant

You specify an operand2 constant in the form #constant, where constant can be:

• Any constant that can be produced by shifting an 8-bit value left by any number of bits within a 32-bit word.

• Any constant of the form 0x00XY00XY

• Any constant of the form 0xXY00XY00

• Any constant of the form 0xXYXYXYXY

In the constants shown above, X and Y are hexadecimal digits.

Czyli kiedy chcemy użyć typowych patternów jak 0xAAAAAAAA lub 0xFFFFFFFF wtedy spełnimy te ograniczenia. Ale kiedy chcemy wpisać na przykład 1000000 dziesiętnie to już nam się nie uda.

Tak samo jest z adresami. O ile wpiszemy 0x08000000 (początek FLASHa) lub 0x20000000 (początek RAMu), to już na dowolnym adresie np. 0x200018FF polegniemy.

Dlaczego tak się dzieje?

Każdą instrukcję asemblerową możemy zmapować jeden do jednego na instrukcję w kodzie maszynowym. Cortex-M używa zestawu instrukcji Thumb-2, gdzie większość instrukcji ma 16 bitów, a niektóre mogą mieć 32 bity.

Czyli na 16 lub maksymalnie 32 bitach musimy upchnąć kod operacji, id rejestrów z operandami i naszą stałą zawierającą 32-bitową wartość. Widzimy więc, że to się nie może udać.

Tak wyglądają możliwe warianty instrukcji MOV w kodzie maszynowym:

A tak ADD:

A dokument, z którego to wziąłem to ARMv7-M Achitecture Reference Manual.

Co robić, jak żyć?

To ograniczenie jest szczególnie bolesne jeżeli chcemy działać na adresach zmiennych. Czyli praktycznie w każdym programie. Dlatego niektóre procesory składają adresy z dwóch rejestrów – bazy i offsetu. Korzystając z faktu, że najstarsze bity adresu są takie same. Tak się dzieje na przykład w x86, gdzie mamy segment i offset.

W Cortex-M mamy inne rozwiązanie. Możemy zapisać adres w pamięci FLASH i wczytać go do rejestru z pamięci. Czyli zamiast move(MOV) wykorzystujemy load (LDR). Dopiero potem możemy odczytać wartość spod wpisanego adresu. Dlatego potem następuje drugi load. Dokładnie coś takiego robił kompilator we wcześniejszym przykładzie.

Ale zaraz. Co my właściwie w ten sposób osiągnęliśmy?

Przecież znowu musimy wczytać adres. Tylko tym razem z pamięci FLASH.

Na szczęście instrukcja LDR ma różne warianty. A jednym z nich jest PC-relative. Jest to coś podobnego do bazy i offsetu. Naszą bazą jest PC (Program Counter wskazujący adres aktualnej instrukcji), a argumentem liczbowym jest offset.

Czyli kompilator zdawał sobie sprawę z ograniczeń naszej architektury i zrealizował kod najefektywniej, jak się dało.

Pseudoinstrukcje

Za to jak byśmy chcieli coś takiego napisać ręcznie – musielibyśmy się nieźle nagimnastykować z adresami i offsetami. To by było bardzo niepraktyczne. Dlatego firma ARM wprowadziła do swojego asemblera pseudoinstrukcje.

Jest to dodatkowa składnia, która wygląda jak instrukcja asemblerowa, ale może być rozbita na kilka instrukcji w kodzie maszynowym. W naszym przykładzie możemy użyć pseudoinstrukcji:

LDR R0, =ADDR

Dzięki użyciu znaku = przed stałą asembler rozbije to na dwie instrukcje LDR, umieści ADDR w pamięci FLASH i przekaże jako argument odpowiedni offset.

Podsumowanie

Morał z tej historii jest taki, że kompilator nie jest taki głupi i jeżeli robi jakieś dziwne operacje to widocznie inaczej się nie da. A nam się może wydawać, że jest inaczej, bo nie znamy ograniczeń wynikających na przykład z kodu maszynowego danych instrukcji. Oczywiście mówię tutaj o przypadku, kiedy włączyliśmy optymalizacje.

Dlatego po pierwsze warto podchodzić do ręcznych optymalizacji z dużą pokorą. Prawdopodobnie nie jesteśmy mądrzejsi od kompilatora i łatwiej coś zepsuć niż poprawić. A już na pewno możemy stracić bez sensu czas.

A po drugie – warto znać nasz procesor, żeby wiedzieć z czego wynikają poszczególne ograniczenia i się potem nie dziwić.

A jeżeli chcesz się tego wszystkiego nauczyć – koniecznie przyjdź w czwartek 10 października na webinar Asembler w Embedded: Od czego zacząć?