Blok podstawowy

W konstrukcji kompilatora blok podstawowy jest sekwencją kodu w linii prostej bez rozgałęzień z wyjątkiem wejścia i bez rozgałęzień z wyjątkiem wyjścia. Ta ograniczona forma sprawia, że podstawowy blok jest bardzo podatny na analizę. Kompilatory zwykle rozkładają programy na ich podstawowe bloki jako pierwszy krok w procesie analizy. Podstawowe bloki tworzą wierzchołki lub węzły w grafie przepływu sterowania .

Definicja

Kod w podstawowym bloku ma:

Jeden punkt wejścia , co oznacza, że żaden kod w nim nie jest celem instrukcji skoku w dowolnym miejscu programu.
Jeden punkt wyjścia, co oznacza, że tylko ostatnia instrukcja może spowodować, że program rozpocznie wykonywanie kodu w innym bloku podstawowym.

W tych okolicznościach, ilekroć wykonywana jest pierwsza instrukcja w bloku podstawowym, pozostałe instrukcje są koniecznie wykonywane dokładnie raz iw kolejności.

Kodem może być kod źródłowy , kod asemblera lub inna sekwencja instrukcji.

Bardziej formalnie, sekwencja instrukcji tworzy podstawowy blok, jeśli:

Instrukcja na każdej pozycji dominuje lub zawsze wykonuje przed wszystkimi pozycjami na późniejszych pozycjach.
Żadna inna instrukcja nie jest wykonywana między dwiema instrukcjami w sekwencji.

Ta definicja jest pod pewnymi względami bardziej ogólna niż definicja intuicyjna. Na przykład pozwala na bezwarunkowe skoki do etykiet, które nie są celem innych skoków. Ta definicja obejmuje właściwości, które ułatwiają pracę z podstawowymi blokami podczas konstruowania algorytmu.

Bloki, do których kontrola może zostać przeniesiona po osiągnięciu końca bloku, nazywane są następcami tego bloku, podczas gdy bloki, z których kontrola mogła pochodzić przy wejściu do bloku, nazywane są poprzednikami tego bloku . Początek bloku podstawowego można przeskoczyć z więcej niż jednego miejsca.

Algorytm tworzenia

Algorytm generowania podstawowych bloków z listy kodu jest prosty: analizator skanuje kod, zaznaczając granice bloków , które są instrukcjami, które mogą rozpoczynać lub kończyć blok, ponieważ albo przekazują sterowanie, albo akceptują sterowanie z innego punktu. Następnie lista jest po prostu „wycinana” w każdym z tych punktów, a podstawowe bloki pozostają.

Należy zauważyć, że ta metoda nie zawsze generuje maksymalne bloki podstawowe, zgodnie z formalną definicją, ale zwykle są one wystarczające (maksymalne bloki podstawowe to podstawowe bloki, których nie można rozszerzyć o sąsiednie bloki bez naruszenia definicji podstawowego bloku).

Wejście : Sekwencja instrukcji (głównie kod trójadresowy ). Wyjście : Lista podstawowych bloków z każdą instrukcją z trzema adresami w dokładnie jednym bloku.

Zidentyfikuj liderów w kodzie. Liderzy to instrukcje, które należą do jednej z następujących 3 kategorii:
1. To jest pierwsza instrukcja. Pierwsza instrukcja to lider.
2. Celem warunkowej lub bezwarunkowej instrukcji goto/jump jest lider.
3. Instrukcja, która następuje bezpośrednio po warunkowej lub bezwarunkowej instrukcji goto/jump jest liderem.
Począwszy od lidera, zestaw wszystkich kolejnych instrukcji do następnego lidera i bez niego jest podstawowym blokiem odpowiadającym rozpoczynającemu liderowi. Zatem każdy podstawowy blok ma lidera.

Instrukcje kończące blok podstawowy obejmują:

gałęzie bezwarunkowe i warunkowe , zarówno bezpośrednie, jak i pośrednie;
powraca do procedury wywołującej;
instrukcje, które mogą rzucić wyjątek ;
wywołania funkcji mogą znajdować się na końcu bloku podstawowego, jeśli nie mogą powrócić, na przykład funkcje, które rzucają wyjątki lub wywołania specjalne, takie jak longjmp i exit w C ;
samą instrukcję zwrotu.

Instrukcje rozpoczynające nowy blok podstawowy obejmują:

punkty wejścia procedur i funkcji;
cele skoków lub gałęzi;
instrukcje „przechodzące” następujące po niektórych gałęziach warunkowych;
instrukcje następujące po tych, które rzucają wyjątki;
obsługi wyjątków.

Należy zauważyć, że ponieważ sterowanie nigdy nie może przejść przez koniec podstawowego bloku, niektóre granice bloku mogą wymagać modyfikacji po znalezieniu podstawowych bloków. W szczególności gałęzie warunkowe z opadaniem muszą zostać zamienione na gałęzie dwukierunkowe, a wywołania funkcji zgłaszające wyjątki muszą mieć po nich dodane skoki bezwarunkowe. Wykonanie tych czynności może wymagać dodania etykiet na początku innych bloków.

Zobacz też

Linki zewnętrzne