Kompilatory

Alfred V. Aho, Jeffrey Ullman, Monica S. Lam, Ravi Sethi

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-20381-8

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2019

Liczba stron:

1066

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Aho, Alfred V.; Ullman, Jeffrey; Lam, Monica S.; Sethi, Ravi. Kompilatory. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2019, 1066 s. ISBN 978-83-01-20381-8

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Aho, A.V.

A1 Ullman, J.

A1 Lam, M.S.

A1 Sethi, R.

T1 Kompilatory

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2019

SN 978-83-01-20381-8

Bibliografia BibTex:

@Book{ 208893, author = "Aho, Alfred V. and Ullman, Jeffrey and Lam, Monica S. and Sethi, Ravi", editor = "", title = "Kompilatory", publisher = "Wydawnictwo Naukowe PWN", year = "2019", address = "Warszawa", isbn = "978-83-01-20381-8" }

Bibliografia endNote:

TY - BOOK

AU - Aho, Alfred V.

AU - Ullman, Jeffrey

AU - Lam, Monica S.

AU - Sethi, Ravi

ED -

TI - Kompilatory

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2019

SN - 978-83-01-20381-8

ER -

Netografia (standard APA):

Aho, Alfred V.; Ullman, Jeffrey; Lam, Monica S.; Sethi, Ravi. Kompilatory [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2019 [dostęp: 03 06 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/kompilatory-alfred-v-aho-jeffrey-ullman-208893.

programowanie, języki programowania, kompilacja, język maszynowy, program, interpreter, kompilatory, Dragon Book, parsing, lekser, generator kodu, optymalizacja kodu, środowiska wykonawcze, architektura komputerów, wyrażenia regularne

Języki programowania są sposobami zapisu przedstawiającymi obliczenia w sposób zrozumiały dla ludzi i dla maszyn. Świat, jaki dziś znamy, uzależniony jest od języków programowania, gdyż całe oprogramowanie działające na wszystkich komputerach zost...

Więcej

ISBN/ISSN:

978-83-01-20381-8

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2019

Liczba stron:

1066

XML:ISBN/ISSN:

ONIX MARC21

Przedmowa 22
1. Wprowadzenie 26
1.1. Translatory26
1.2. Struktura kompilatora29
1.1.1. Ćwiczenia do podrozdziału 1.129
1.2.1. Analiza leksykalna31
1.2.2. Analiza składniowa32
1.2.3. Analiza semantyczna34
1.2.4. Generowanie kodu posredniego34
1.2.5. Optymalizacja kodu35
1.2.6. Generowanie kodu36
1.2.7. Zarządzanie tablica symboli36
1.2.8. Grupowanie faz w przebiegi37
1.2.9. Narzędzia do budowania kompilatorów37
1.3. Ewolucja języków programowania38
1.3.1. Przejście na języki wyższego poziomu38
1.3.2. Wpływ na kompilatory39
1.3.3. Ćwiczenia do podrozdziału 1.340
1.4. Teoria konstruowania kompilatorów41
1.4.1. Modelowanie w projektowaniu i implementacji kompilatora41
1.4.2. Nauka o optymalizacji kodu41
1.5. Zastosowania technologii kompilatorów43
1.5.1. Implementacja języków programowania wysokiego poziomu44
1.5.2. Optymalizacje architektur komputerów46
1.5.3. Projekty nowych architektur komputerów47
1.5.4. Tłumaczenie programów49
1.5.5. Narzędzia niezawodności oprogramowania50
1.6. Podstawy języków programowania52
1.6.1. Rozróżnienie statyczny/dynamiczny53
1.6.2. Środowiska i stany53
1.6.3. Statyczny zasięg i struktura blokowa55
1.6.4. Jawna kontrola dostępu59
1.6.5. Zasięg dynamiczny59
1.6.6. Mechanizmy przekazywania parametrów61
1.6.7. Aliasowanie63
1.6.8. Ćwiczenia do podrozdziału 1.664
1.7. Podsumowanie65
1.8. Bibliografia66
2. Prosty translator sterowany składnia 68
2.1. Wprowadzenie69
2.2. Definiowanie składni71
2.2.1. Definicja gramatyki71
2.2.2. Wyprowadzenia73
2.2.3. Drzewa rozbioru74
2.2.4. Niejednoznaczność76
2.2.5. Łączność operatorów77
2.2.6. Priorytety operatorów78
2.2.7. Ćwiczenia do podrozdziału 2.281
2.3. Translacja sterowana składnia82
2.3.1. Notacja postfiksowa83
2.3.2. Syntetyzowane atrybuty83
2.3.3. Proste definicje sterowane składnia85
2.3.4. Przechodzenie drzewa86
2.3.5. Schematy translacji88
2.3.6. Ćwiczenia do podrozdziału 2.390
2.4. Analiza składniowa91
2.4.1. Analiza zstępująca91
2.4.2. Analiza predykcyjna94
2.4.3. Kiedy używać e-produkcji96
2.4.4. Projektowanie parsera predykcyjnego97
2.4.5. Lewostronna rekurencja98
2.5. Translator dla prostych wyrażeń99
2.4.6. Ćwiczenia do podrozdziału 2.499
2.5.1. Składnia abstrakcyjna i konkretna100
2.5.2. Dostosowywanie schematu translacji101
2.5.3. Procedury dla nieterminali102
2.5.4. Upraszczanie translatora103
2.5.5. Kompletny program104
2.6. Analiza leksykalna107
2.6.1. Usuwanie białych znaków i komentarzy108
2.6.2. Czytanie z wyprzedzeniem109
2.6.3. Stałe109
2.6.4. Rozpoznawanie słów kluczowych i identyfikatorów110
2.6.5. Analizator leksykalny112
2.7. Tablice symboli116
2.6.6. Ćwiczenia do podrozdziału 2.6116
2.7.1. Tablica symboli dla zasięgu118
2.7.2. Używanie tablic symboli121
2.8. Generowanie kodu pośredniego123
2.8.1. Dwa rodzaje reprezentacji pośrednich123
2.8.2. Konstruowanie drzew składniowych124
2.8.3. Kontrole statyczne129
2.8.4. Kod trójadresowy131
2.9. Podsumowanie137
2.8.5. Ćwiczenia do podrozdziału 2.8137
3. Analiza leksykalna 140
3.1. Rola analizatora leksykalnego140
3.1.1. Analiza leksykalna kontra analiza składniowa (parsing)142
3.1.2. Tokeny, wzorce i leksemy142
3.1.3. Atrybuty tokenów143
3.1.4. Błędy leksykalne145
3.2. Buforowanie wejścia146
3.1.5. Ćwiczenia do podrozdziału 3.1146
3.2.1. Pary buforów147
3.2.2. Wartownicy148
3.3. Specyfikacje tokenów149
3.3.1. Ciągi i języki150
3.3.2. Działania na językach151
3.3.3. Wyrażenia regularne152
3.3.4. Definicje regularne154
3.3.5. Rozszerzenia wyrażeń regularnych155
3.3.6. Ćwiczenia do podrozdziału 3.3156
3.4. Rozpoznawanie tokenów160
3.4.1. Diagramy przejść161
3.4.2. Rozpoznawanie zastrzeżonych słów i identyfikatorów164
3.4.3. Dokończenie przykładu165
3.4.4. Architektura analizatora leksykalnego opartego na diagramie przejść166
3.4.5. Ćwiczenia do podrozdziału 3.4168
3.5. Lex – generator analizatorów leksykalnych172
3.5.1. Korzystanie z Lex172
3.5.2. Struktura programów w języku Lex173
3.5.3. Rozwiązywanie konfliktów w Lex177
3.5.4. Operator prawego kontekstu177
3.5.5. Ćwiczenia do podrozdziału 3.5178
3.6. Automaty skończone179
3.6.1. Niedeterministyczne automaty skończone180
3.6.2. Tablice przejść181
3.6.3. Akceptowanie ciągów wejściowych przez automat181
3.6.4. Deterministyczne automaty skończone182
3.6.5. Ćwiczenia do podrozdziału 3.6183
3.7. Od wyrażeń regularnych do automatów184
3.7.1. Konwertowanie NAS na DAS185
3.7.2. Symulacja NAS188
3.7.3. Wydajność symulacji NAS189
3.7.4. Konstruowanie NAS z wyrażenia regularnego191
3.7.5. Wydajność algorytmów przetwarzania ciągów195
3.8. Projektowanie generatora analizatorów leksykalnych199
3.7.6. Ćwiczenia do podrozdziału 3.7199
3.8.1. Struktura generowanego analizatora199
3.8.2. Dopasowywanie wzorców na podstawie NAS202
3.8.3. DAS dla analizatorów leksykalnych203
3.8.4. Implementacja operatora prawego kontekstu204
3.9. Optymalizacja mechanizmów rozpoznających wzorce oparte na DAS205
3.8.5. Ćwiczenia do podrozdziału 3.8205
3.9.1. Istotne stany w NAS206
3.9.2. Funkcje wyliczane z drzewa składniowego208
3.9.3. Obliczanie nullable, firstpos i lastpos209
3.9.4. Obliczanie followpos210
3.9.5. Bezpośrednie konwertowanie wyrażenia regularnego na DAS212
3.9.6. Minimalizacja liczby stanów w DAS214
3.9.7. Minimalizacja liczby stanów w analizatorach leksykalnych218
3.9.8. Wybieranie miedzy czasem a pamięcią w symulatorze DAS218
3.10. Podsumowanie220
3.9.9. Ćwiczenia do podrozdziału 3.9220
3.11. Bibliografia222
4. Analiza składniowa 226
4.1. Wprowadzenie227
4.1.1. Rola parsera227
4.1.2. Reprezentatywne gramatyki228
4.1.3. Obsługa błędów składniowych229
4.1.4. Strategie przywracania kontroli po błędzie230
4.2. Gramatyki bezkontekstowe232
4.2.1. Formalna definicja gramatyki bezkontekstowej232
4.2.2. Konwencje notacyjne234
4.2.3. Wyprowadzenie235
4.2.4. Drzewa rozbioru237
4.2.5. Niejednoznaczność239
4.2.6. Weryfikowanie języka wygenerowanego przez gramatykę239
4.2.7. Gramatyki bezkontekstowe a wyrażenia regularne241
4.2.8. Ćwiczenia do podrozdziału 4.2242
4.3. Tworzenie gramatyki245
4.3.1. Analiza leksykalna a analiza składniowa245
4.3.2. Eliminowanie niejednoznaczności246
4.3.3. Eliminowanie rekurencji lewostronnej247
4.3.4. Lewostronna faktoryzacja250
4.3.5. Konstrukcje językowe niebędące bezkontekstowymi251
4.3.6. Ćwiczenia do podrozdziału 4.3252
4.4. Analiza zstepująca253
4.4.1. Analiza oparta na zejściach rekurencyjnych254
4.4.2. FIRST oraz FOLLOW256
4.4.3. Gramatyki LL(1)258
4.4.4. Nierekurencyjna analiza predykcyjna262
4.4.5. Przywracanie po błędzie w analizie predykcyjnej264
4.4.6. Ćwiczenia do podrozdziału 4.4267
4.5. Analiza wstępująca270
4.5.1. Redukcje270
4.5.2. Przycinanie uchwytów271
4.5.3. Analiza metoda przesuniecie-redukcja272
4.5.4. Konflikty w analizie metoda przesuniecie-redukcja274
4.5.5. Ćwiczenia do podrozdziału 4.5276
4.6. Wprowadzenie do analizy LR: proste LR (SLR)277
4.6.1. Dlaczego parsery LR?277
4.6.2. Sytuacje i automat LR(0)278
4.6.3. Algorytm parsingu LR284
4.6.4. Konstruowanie tablic analizy SLR289
4.6.5. Żywotne prefiksy292
4.6.6. Ćwiczenia do podrozdziału 4.6293
4.7. Bardziej skuteczne parsery LR295
4.7.1. Kanoniczne sytuacje LR(1)295
4.7.2. Konstruowanie zbiorów sytuacji LR(1)297
4.7.3. Tablice analizy kanonicznego LR(1)300
4.7.4. Konstruowanie tablic analizy LALR301
4.7.5. Wydajne konstruowanie tablic analizy LALR306
4.7.6. Kompresowanie tablic analizy LR311
4.7.7. Ćwiczenia do podrozdziału 4.7313
4.8. Gramatyki niejednoznaczne314
4.8.1. Wykorzystanie priorytetów i łączności do rozwiązywania konfliktów314
4.8.2. Niejednoznaczność „wiszącego else”317
4.8.3. Przywracanie kontroli po błędzie w analizie LR319
4.8.4. Ćwiczenia do podrozdziału 4.8322
4.9. Generatory parserów323
4.9.1. Generator parserów Yacc323
4.9.2. Używanie Yacc z gramatykami niejednoznacznymi327
4.9.3. Tworzenie analizatorów leksykalnych zgodnych z Yacc przy użyciu Lex330
4.9.4. Przywracanie kontroli po błędach w Yacc331
4.10. Podsumowanie333
4.9.5. Ćwiczenia do podrozdziału 4.9333
4.11. Bibliografia336
5. Translacja sterowana składnia 340
5.1. Definicje sterowane składnia341
5.1.1. Atrybuty dziedziczone i syntetyzowane341
5.1.2. Przetwarzanie SDD w węzłach drzewa rozbioru343
5.2. Kolejność przetwarzania w SDD347
5.1.3. Ćwiczenia do podrozdziału 5.1347
5.2.1. Grafy zależności347
5.2.2. Porządkowanie obliczania atrybutów349
5.2.3. Definicje S-atrybutowane350
5.2.4. Definicje L-atrybutowane350
5.2.5. Reguły semantyczne z kontrolowanymi efektami ubocznymi352
5.2.6. Ćwiczenia do podrozdziału 5.2354
5.3. Zastosowania translacji sterowanej składnia355
5.3.1. Konstruowanie drzew składniowych355
5.3.2. Struktura opisu typu359
5.4. Sterowane składnia schematy translacji361
5.3.3. Ćwiczenia do podrozdziału 5.3361
5.4.1. Postfiksowe schematy translacji362
5.4.2. Implementacja postfiksowego SDT przez stos parsera363
5.4.3. SDT z akcjami wewnątrz produkcji364
5.4.4. Eliminowanie rekurencji lewostronnej z SDT366
5.4.5. SDT dla definicji L-atrybutowanych369
5.4.6. Ćwiczenia do podrozdziału 5.4374
5.5. Implementacja L-atrybutowanych SDD375
5.5.1. Tłumaczenie podczas parsingu na podstawie zejść rekurencyjnych376
5.5.2. Generowanie kodu w locie379
5.5.3. L-atrybutowane SDD i parsing LL381
5.5.4. Analiza wstępujaca L-atrybutowanych SDD386
5.6. Podsumowanie391
5.5.5. Ćwiczenia do podrozdziału 5.5391
5.7. Bibliografia393
6. Generowanie kodu pośredniego 396
6.1. Odmiany drzew składniowych397
6.1.1. Skierowane grafy acykliczne dla wyrażeń398
6.1.2. Metoda numerowania wartości do konstruowania DAG399
6.2. Kod trójadresowy402
6.1.3. Ćwiczenia do podrozdziału 6.1402
6.2.1. Adresy i instrukcje403
6.2.2. Czwórki405
6.2.3. Trójki406
6.2.4. Forma Static Single Assignment408
6.3. Typy i deklaracje409
6.2.5. Ćwiczenia do podrozdziału 6.2409
6.3.1. Wyrażenia określające typy410
6.3.2. Równoważność typów411
6.3.3. Deklaracje412
6.3.4. Rozmieszczenie w pamięci dla nazw lokalnych413
6.3.5. Sekwencje deklaracji415
6.3.6. Pola rekordów i klas416
6.3.7. Ćwiczenia do podrozdziału 6.3417
6.4. Translacja wyrażeń418
6.4.1. Operacje wewnątrz wyrażeń418
6.4.2. Tłumaczenie przyrostowe395420
6.4.3. Adresowanie elementów tablic420
6.4.4. Tłumaczenie odwołań do tablic422
6.4.5. Ćwiczenia do podrozdziału 6.4424
6.5. Kontrola typów426
6.5.1. Reguły kontroli typów426
6.5.2. Konwersje typów427
6.5.3. Przeciążanie funkcji i operatorów430
6.5.4. Inferencja typów i funkcje polimorficzne430
6.5.5. Algorytm unifikacji435
6.6. Przepływ sterowania438
6.5.6. Ćwiczenia do podrozdziału 6.5438
6.6.1. Wyrażenia logiczne439
6.6.2. Kod krótki440
6.6.3. Instrukcje sterujące440
6.6.4. Translacja wyrażeń logicznych443
6.6.5. Unikanie nadmiarowych skoków goto445
6.6.6. Wartości logiczne i skaczący kod447
6.6.7. Ćwiczenia do podrozdziału 6.6448
6.7. Backpatching449
6.7.1. Jednoprzebiegowe generowanie kodu przy użyciu poprawiania wstecznego450
6.7.2. Backpatching wyrażeń logicznych451
6.7.3. Instrukcje sterujące454
6.7.4. Instrukcje break, continue i goto456
6.7.5. Ćwiczenia do podrozdziału 6.7457
6.8. Instrukcje wyboru458
6.8.1. Translacja instrukcji switch458
6.8.2. Sterowana składnia translacja instrukcji switch460
6.8.3. Ćwiczenia do podrozdziału 6.8461
6.9. Kod pośredni dla procedur462
6.10. Podsumowanie464
6.11. Bibliografia465
7. Środowiska wykonania 468
7.1. Organizacja pamięci468
7.1.1. Alokacje statyczne kontra dynamiczne470
7.2. Stosowa rezerwacja pamięci471
7.2.1. Drzewa aktywacji471
7.2.2. Rekordy aktywacji475
7.2.3. Sekwencje wywołujące477
7.2.4. Dane zmiennej długości na stosie480
7.2.5. Ćwiczenia do podrozdziału 7.2482
7.3. Dostęp do nielokalnych danych na stosie483
7.3.1. Dostęp do danych bez zagnieżdżonych procedur484
7.3.2. Problemy dotyczące zagnieżdżonych procedur484
7.3.3. Język z zagnieżdżonymi deklaracjami procedur485
7.3.4. Głębokość zagnieżdżenia485
7.3.5. Wiązania dostępu487
7.3.6. Manipulowanie wiązaniami dostępu489
7.3.7. Wiązania dostępu a parametry procedur490
7.3.8. Tablice display492
7.3.9. Ćwiczenia do podrozdziału 7.3494
7.4. Zarządzanie sterta495
7.4.1. Zarządca pamięci495
7.4.2. Hierarchia pamięci komputera496
7.4.3. Lokalność w programach498
7.4.4. Redukowanie fragmentacji501
7.4.5. Ręczne zadania dealokacji504
7.5. Wprowadzenie do odśmiecania pamięci507
7.4.6. Ćwiczenia do podrozdziału 7.4507
7.5.1. Cele projektowe odśmiecaczy pamięci508
7.5.2. Osiągalność511
7.5.3. Kolektory śmieci ze zliczaniem referencji513
7.5.4. Ćwiczenia do podrozdziału 7.5515
7.6. Wprowadzenie do odśmiecania bazujacego na śledzeniu516
7.6.1. Podstawowy odśmiecacz Mark and Sweep516
7.6.2. Podstawowa abstrakcja518
7.6.3. Optymalizowanie znakowania i zamiatania520
7.6.4. Odsmiecacze Mark and Compact522
7.6.5. Odśmiecacze kopiujące525
7.6.6. Porównanie kosztów527
7.6.7. Ćwiczenia do podrozdziału 7.6528
7.7. Odśmiecanie z krótkimi pauzami529
7.7.1. Przyrostowe zbieranie danych śmieciowych529
7.7.2. Przyrostowa analiza osiągalności531
7.7.3. Założenia odśmiecaczy częściowych533
7.7.4. Generacyjne zbieranie danych śmieciowych535
7.7.5. Algorytm pociągowy536
7.7.6. Ćwiczenia do podrozdziału 7.7540
7.8. Zaawansowane zagadnienia związane ze sprzątaniem pamięci541
7.8.1. Równoległe i współbieżne odśmiecanie pamięci542
7.8.2. Częściowa relokacja obiektów544
7.8.3. Konserwatywne odśmiecanie dla języków niebezpiecznych typologicznie545
7.8.4. Słabe referencje546
7.9. Podsumowanie547
7.8.5. Ćwiczenia do podrozdziału 7.8547
7.10. Bibliografia550
8. Generowanie kodu 552
8.1. Zagadnienia projektowania generatora kodu553
8.1.1. Dane wejściowe generatora kodu554
8.1.2. Program docelowy554
8.1.3. Wybieranie rozkazów556
8.1.4. Przydzielanie rejestrów557
8.2. Język docelowy559
8.1.5. Kolejność wykonywania559
8.2.1. Prosty model maszyny docelowej559
8.2.2. Koszty programu i rozkazów562
8.2.3. Ćwiczenia do podrozdziału 8.2563
8.3. Adresy w kodzie wynikowym565
8.3.1. Alokacje statyczne566
8.3.2. Alokacja na stosie568
8.3.3. Adresy czasu wykonania dla nazw571
8.3.4. Ćwiczenia do podrozdziału 8.3571
8.4. Bloki podstawowe i grafy przepływu572
8.4.1. Bloki podstawowe573
8.4.2. Informacja o następnym użyciu575
8.4.3. Grafy przepływu576
8.4.4. Reprezentacje grafów przepływu578
8.4.5. Pętle578
8.4.6. Ćwiczenia do podrozdziału 8.4579
8.5. Optymalizowanie bloków podstawowych580
8.5.1. Reprezentacja bloków podstawowych jako skierowanych grafów acyklicznych (DAG)580
8.5.2. Wyszukiwanie lokalnych podwyrażeń wspólnych581
8.5.3. Eliminowanie martwego kodu583
8.5.4. Korzystanie z tożsamości algebraicznych583
8.5.5. Reprezentacja odwołań do tablic585
8.5.6. Przypisania przy użyciu wskaźników i wywołania procedur587
8.5.7. Odtwarzanie bloków podstawowych z DAG562589
8.5.8. Ćwiczenia do podrozdziału 8.5589
8.6. Prosty generator kodu590
8.6.1. Deskryptory rejestrów i adresów591
8.6.2. Algorytm generowania kodu592
8.6.3. Projekt funkcji getReg595
8.7. Optymalizacja przez szparkę597
8.6.4. Ćwiczenia do podrozdziału 8.6597
8.7.1. Eliminowanie nadmiarowych ładowań i zapisów598
8.7.2. Eliminowanie nieosiągalnego kodu598
8.7.3. Optymalizacje przepływu sterowania599
8.7.4. Uproszczenia algebraiczne i redukcje mocy operatorów600
8.8. Przydzielanie i przypisywanie rejestrów601
8.7.5. Użycie idiomów języka maszynowego601
8.7.6. Ćwiczenia do podrozdziału 8.7601
8.8.1. Globalny przydział rejestrów602
8.8.2. Liczniki użyć602
8.8.3. Przypisywanie rejestrów dla pętli zewnętrznych605
8.8.4. Przydział rejestrów przez kolorowanie grafu605
8.9. Dobór rozkazów przez przekształcanie drzewa606
8.8.5. Ćwiczenia do podrozdziału 8.8606
8.9.1. Schematy translacji drzew607
8.9.2. Generowanie kodu przez kafelkowanie drzewa wejściowego609
8.9.3. Dopasowywanie wzorców przez parsing612
8.9.4. Procedury kontroli semantycznej614
8.9.5. Ogólne dopasowywanie drzew614
8.10. Generowanie optymalnego kodu dla wyrażeń616
8.10.1. Liczby Ershova616
8.9.6. Ćwiczenia do podrozdziału 8.9616
8.10.2. Generowanie kodu na podstawie etykietowanego drzewa wyrażenia617
8.10.3. Obliczanie wyrażeń przy niedostatecznej liczbie rejestrów620
8.11. Generowanie kodu przy użyciu programowania dynamicznego622
8.10.4. Ćwiczenia do podrozdziału 8.10622
8.11.1. Przetwarzanie po kolei623
8.11.2. Algorytm programowania dynamicznego624
8.12. Podsumowanie627
8.11.3. Ćwiczenia do podrozdziału 8.11627
8.13. Bibliografia628
9. Optymalizacje niezależne od typu procesora 632
9.1. Główne źródła optymalizacji633
9.1.1. Przyczyny nadmiarowości633
9.1.2. Bieżący przykład: Quicksort634
9.1.3. Transformacje zachowujące semantykę636
9.1.4. Globalne wspólne podwyrażenia637
9.1.5. Propagacja kopii639
9.1.6. Usuwanie martwego kodu640
9.1.7. Przemieszczenie kodu641
9.1.8. Zmienne indukcyjne i redukcja mocy641
9.1.9. Ćwiczenia do podrozdziału 9.1644
9.2. Wprowadzenie do analizy przepływu danych646
9.2.1. Abstrakcja przepływu danych646
9.2.2. Schemat analizy przepływu danych648
9.2.3. Schematy przepływu danych dla bloków podstawowych650
9.2.4. Definicje osiągające651
9.2.5. Analiza żywotności zmiennych658
9.2.6. Wyrażenia dostępne660
9.2.7. Podsumowanie podrozdziału 9.2664
9.2.8. Ćwiczenia do podrozdziału 9.2665
9.3. Podstawy analizy przepływu danych667
9.3.1. Półkraty668
9.3.2. Funkcje transferu673
9.3.3. Algorytm iteracyjny dla ogólnego szkieletu675
9.3.4. Sens rozwiązania przepływu danych678
9.3.5. Ćwiczenia do podrozdziału 9.3681
9.4. Propagacja stałych682
9.4.1. Wartości przepływu danych dla szkieletu propagacji stałych683
9.4.2. Funkcja spotkania dla szkieletu propagacji stałych684
9.4.3. Funkcje transferu dla szkieletu propagacji stałych684
9.4.4. Monotoniczność szkieletu propagacji stałych685
9.4.5. Niedystrybutywność szkieletu propagacji stałych685
9.4.6. Interpretacja wyników687
9.4.7. Ćwiczenia do podrozdziału 9.4688
9.5. Eliminowanie częściowej nadmiarowości689
9.5.1. Źródła nadmiarowości690
9.5.2. Czy możliwe jest wyeliminowanie całej nadmiarowości?692
9.5.3. Problem opóźniającego przemieszczenia kodu694
9.5.4. Częściowa nadmiarowość695
9.5.5. Antycypowanie wyrażeń695
9.5.6. Algorytm opóźniającego przemieszczenia kodu696
9.5.7. Ćwiczenia do podrozdziału 9.5706
9.6. Pętle w grafach przepływu707
9.6.1. Dominatory707
9.6.2. Porządkowanie w głąb711
9.6.3. Krawędzie w drzewie rozpinającym w głąb713
9.6.4. Krawędzie zwrotne i redukowalność715
9.6.5. Głębokość grafu przepływu716
9.6.6. Pętle naturalne716
9.6.7. Tempo zbieżności iteracyjnych algorytmów przepływu danych718
9.6.8. Ćwiczenia do podrozdziału 9.6721
9.7. Analiza oparta na regionach723
9.7.1. Regiony724
9.7.2. Hierarchie regionów dla redukowalnych grafów przepływu725
9.7.3. Wprowadzenie do analizy opartej na regionach728
9.7.4. Konieczne założenia dotyczące funkcji transferu729
9.7.5. Algorytm dla analizy opartej na regionach731
9.7.6. Obsługa nieredukowalnych grafów przepływu735
9.7.7. Ćwiczenia do podrozdziału 9.7737
9.8. Analiza symboliczna738
9.8.1. Afiniczne wyrażenia zmiennych referencyjnych738
9.8.2. Formułowanie problemu przepływu danych742
9.8.3. Analiza symboliczna oparta na regionach745
9.8.4. Ćwiczenia do podrozdziału 9.8750
9.9. Podsumowanie751
9.10. Bibliografia754
10. Równoległość na poziomie instrukcji 758
10.1. Architektury procesorów759
10.1.1. Potoki instrukcji i opóźnienia rozgałęzień759
10.1.2. Wykonywanie potokowe760
10.1.3. Zlecanie wielu instrukcji761
10.2. Ograniczenia szeregowania wykonania kodu762
10.2.1. Zależność danych762
10.2.2. Wyszukiwanie zależności miedzy dostępami do pamięci763
10.2.3. Kompromis miedzy wykorzystaniem rejestrów i równoległością765
10.2.4. Kolejność faz alokacji rejestrów i szeregowania kodu767
10.2.5. Zależność sterowania768
10.2.6. Wsparcie dla wykonania spekulatywnego769
10.2.7. Podstawowy model maszyny771
10.2.8. Ćwiczenia do podrozdziału 10.2772
10.3. Szeregowanie wykonania dla bloków podstawowych774
10.3.1. Grafy zależności danych774
10.3.2. Szeregowanie listowe bloków podstawowych776
10.3.3. Priorytetowy porządek topologiczny777
10.3.4. Ćwiczenia do podrozdziału 10.3778
10.4. Globalne szeregowanie kodu779
10.4.1. Elementarne przemieszczanie kodu780
10.4.2. Przemieszczanie kodu w górę782
10.4.3. Przemieszczanie kodu w dół783
10.4.4. Uaktualnianie zależności danych785
10.4.5. Globalne algorytmy szeregowania785
10.4.6. Zaawansowane techniki przemieszczania kodu789
10.4.7. Interakcja ze schedulerami dynamicznymi790
10.4.8. Ćwiczenia do podrozdziału 10.4790
10.5. Potokowanie programowe791
10.5.1. Wprowadzenie791
10.5.2. Potokowanie programowe dla pętli794
10.5.3. Alokacja rejestrów i generowanie kodu796
10.5.4. Petle Do-Across797
10.5.5. Cele i ograniczenia potokowania programowego798
10.5.6. Algorytm potokowania programowego802
10.5.7. Szeregowanie acyklicznych grafów zależności danych803
10.5.8. Szeregowanie cyklicznych grafów zależności804
10.5.9. Usprawnienia algorytmów potokowania811
10.5.10.Modularne rozszerzanie zmiennych812
10.5.11. Instrukcje warunkowe815
10.5.12.Wsparcie sprzętowe dla potokowania programowego816
10.5.13. Ćwiczenia do podrozdziału 10.5816
10.6. Podsumowanie818
10.7. Bibliografia820
11. Optymalizacja pod katem równoległości i lokalności 822
11.1. Pojęcia podstawowe825
11.1.1. Wieloprocesorowość825
11.1.2. Równoległość w aplikacjach827
11.1.3. Równoległość na poziomie pętli829
11.1.4. Lokalność danych830
11.1.5. Wprowadzenie do teorii transformacji afinicznych832
11.2. Mnożenie macierzy: pogłębiony przykład836
11.2.1. Algorytm mnożenia macierzy837
11.2.2. Optymalizacje839
11.2.3. Interferencja cache842
11.3. Przestrzenie iteracji843
11.2.4. Ćwiczenia do podrozdziału 11.2843
11.3.1. Konstruowanie przestrzeni iteracji z gniazda pętli843
11.3.2. Kolejność wykonywania gniazd pętli846
11.3.3. Postać macierzowa nierówności846
11.3.4. Uwzględnianie stałych symbolicznych847
11.3.5. Kontrolowanie kolejności wykonania848
11.3.6. Zmiana osi852
11.3.7. Ćwiczenia do podrozdziału 11.3854
11.4. Afiniczne indeksy tablic856
11.4.1. Dostępy afiniczne856
11.4.2. Dostęp afiniczny i nieafiniczny w praktyce857
11.4.3. Ćwiczenia do podrozdziału 11.4858
11.5. Ponowne użycie danych859
11.5.1. Rodzaje ponownego użycia860
11.5.2. Samodzielne ponowne użycie861
11.5.3. Samodzielne przestrzenne użycie ponowne864
11.5.4. Grupowe użycie ponowne866
11.5.5. Ćwiczenia do podrozdziału 11.5869
11.6. Analiza zależności danych dla tablicy870
11.6.1. Definicja zależności danych miedzy dostępami do tablic871
11.6.2. Programowanie całkowitoliczbowe (liniowe)872
11.6.3. Test NWD873
11.6.4. Heurystyki dla całkowitoliczbowego programowania liniowego875
11.6.5. Rozwiązywanie ogólnych problemów programowania całkowitoliczbowego879
11.6.6. Podsumowanie podrozdziału 11.6881
11.6.7. Ćwiczenia do podrozdziału 11.6881
11.7. Wyszukiwanie równoległości niewymagającej synchronizacji883
11.7.1. Przykład wstępny883
11.7.2. Afiniczne podziały w przestrzeni886
11.7.3. Ograniczenia podziału w przestrzeni887
11.7.4. Rozwiązywanie ograniczeń podziału w przestrzeni890
11.7.5. Prosty algorytm generowania kodu894
11.7.6. Eliminowanie pustych iteracji897
11.7.7. Eliminowanie warunków z najbardziej wewnętrznych pętli899
11.7.8. Transformacje kodu źródłowego902
11.7.9. Ćwiczenia do podrozdziału 11.7906
11.8. Synchronizacja miedzy pętlami równoległymi908
11.8.1. Stała liczba operacji synchronizujących908
11.8.2. Grafy zależności programu909
11.8.3. Czas hierarchiczny912
11.8.4. Algorytm zrównoleglania914
11.8.5. Ćwiczenia do podrozdziału 11.8915
11.9. Potokowanie916
11.9.1. Czym jest potokowanie?916
11.9.2. Sukcesywna nadrelaksacja (Successive Over-Relaxation – SOR): przykład praktyczny918
11.9.3. W pełni przestawialne petle919
11.9.4. Potokowanie w pełni przestawialnych pętli921
11.9.5. Teoria ogólna922
11.9.6. Ograniczenia podziału w czasie923
11.9.7. Rozwiązywanie ograniczeń podziału w czasie przy użyciu lematu Farkasa927
11.9.8. Transformacje kodu930
11.9.9. Równoległość z minimalna synchronizacja934
11.9.10. Ćwiczenia do podrozdziału 11.9937
11.10.Optymalizowanie lokalności939
11.10.1. Lokalność czasowa danych obliczanych939
11.10.2.Kontrakcja tablic940
11.10.3. Przeplatanie partycji943
11.10.4. Zbieranie wszystkiego razem947
11.10.5. Ćwiczenia do podrozdziału 11.10948
11.11.Inne zastosowania transformacji afinicznych949
11.11.1. Maszyny z pamięcią rozproszona949
11.11.2. Procesory z jednoczesnym zlecaniem rozkazów950
11.11.3. Maszyny wektorowe i SIMD950
11.11.4.Wczesny odczyt danych951
11.12.Podsumowanie953
11.13.Bibliografia955
12. Analiza międzyproceduralna 960
12.1. Podstawowe pojęcia961
12.1.1. Grafy wywołań961
12.1.2. Wrażliwość na kontekst963
12.1.3. Łańcuchy wywołań965
12.1.4. Analiza kontekstowa oparta na klonowaniu967
12.1.5. Analiza kontekstowa oparta na podsumowaniu969
12.1.6. Ćwiczenia do podrozdziału 12.1971
12.2. Dlaczego potrzebna jest analiza międzyproceduralna?973
12.2.1. Wywołania metod wirtualnych973
12.2.2. Analiza aliasowania wskaźników974
12.2.3. Zrównoleglanie974
12.2.4. Wykrywanie błędów i podatności na ataki974
12.2.5. SQL injection975
12.2.6. Przepełnienie bufora977
12.3. Logiczna reprezentacja przepływu danych978
12.3.1. Wprowadzenie do Datalogu979
12.3.2. Reguły Datalogu980
12.3.3. Predykaty intensjonalne i ekstensjonalne981
12.3.4. Wykonywanie programów Datalogu984
12.3.5. Inkrementalne przetwarzanie programów Datalogu985
12.3.6. Problematyczne reguły Datalogu988
12.3.7. Ćwiczenia do podrozdziału 12.3989
12.4. Prosty algorytm analizy wskaźników991
12.4.1. Dlaczego analiza wskaźników jest trudna991
12.4.2. Model dla wskaźników i referencji992
12.4.3. Niewrażliwość na przepływ sterowania993
12.4.4. Sformułowanie problemu w Datalogu994
12.4.5. Wykorzystanie informacji o typach996
12.4.6. Ćwiczenia do podrozdziału 12.4998
12.5. Analiza międzyproceduralna niewrażliwa na kontekst999
12.5.1. Efekty wywołania metody999
12.5.2. Odkrywanie grafu wywołań w Datalogu1001
12.5.3. Dynamiczne ładowanie i refleksja1002
12.6. Analiza wskaźników z uwzględnieniem kontekstu1003
12.5.4. Ćwiczenie do podrozdziału 12.51003
12.6.1. Konteksty i łańcuchy wywołań1004
12.6.2. Dodawanie kontekstu do reguł Datalogu1007
12.7. Implementacja Datalogu przez BDD1008
12.6.3. Dodatkowe spostrzeżenia dotyczące wrażliwości1008
12.6.4. Ćwiczenia do podrozdziału 12.61008
12.7.1. Binarne diagramy decyzyjne1009
12.7.2. Przekształcenia BDD1011
12.7.3. Reprezentowanie relacji przy uzyciu BDD1012
12.7.4. Operacje na relacjach jako operacje na BDD1013
12.7.5. Wykorzystanie BDD w analizie miejsc wskazywanych1016
12.7.6. Ćwiczenia do podrozdziału 12.71016
12.8. Podsumowanie1017
12.9. Bibliografia1020
A. Pełny front-end kompilatora 1024
A.1. Język źródłowy1024
A.2. Main1026
A.3. Analizator leksykalny1026
A.4. Tabele symboli oraz typy1029
A.5. Kod pośredni dla wyrażeń1030
A.6. Kod skaczący dla wyrażeń logicznych1033
A.7. Kod pośredni dla instrukcji1037
A.8. Parser1041
A.9. Budowanie front-endu kompilatora1046
B. Znajdowanie rozwiązań liniowo niezależnych 1048
Indeks1052

1.4.TEORIAKONSTRUOWANIAKOMPILATORÓW

nazwą,jakożeniemamożliwościzagwarantowania,żekodutworzonyprzez

kompilatorbędzierzeczywiścierównieszybkilubszybszyniżdowolnyinnykod

realizującytosamozadanie.

Współcześnieoptymalizacjakoduwykonywanaprzezkompilatorstałasię

jednocześniebardziejważna,aleibardziejzłożona.Większazłożonośćwynika

stąd,żearchitekturyprocesorówrównieżstałysiębardziejrozbudowane,za-

pewniającwięcejmożliwościusprawnieniasposobuwykonywaniakodu.Jest

bardziejważna,gdyżmasywnierównoległekomputerywymagająznaczących

optymalizacji;wprzeciwnymrazieichwydajnośćmożespaśćorządwielkości

lubjeszczebardziej.Wrazzdominacjąmaszynwielordzeniowych(komputerów

wyposażonychwukładyzawierającewielkąliczbęprocesorów)wszystkiekompi-

latorymusząporadzićsobiezproblememrzeczywistegowykorzystaniamaszyn

wieloprocesorowych.

Byłobytrudne,jeślinieniemożliwe,zbudowanieniezawodnegokompila-

torazgotowychnsztuczek”.Ztegowzględuwokółproblemuoptymalizacji

kodupowstałarozległaiużytecznateoria.Wykorzystanieścisłychpodstaw

matematycznychpozwaladowieść,czyoptymalizacjajestpoprawnaiczydaje

pożądanyefektdlawszelkichmożliwychdanychwejściowych.Począwszyod

rozdziału9,pokażemy,żetakiemodele,jakgrafy,macierzeiprogramowanie

liniowesąniezbędne,jeślikompilatormatworzyćdobrzezoptymalizowany

kod.

Jednocześniesamaczystateorianiejestwystarczająca.Podobniejakwprzy-

padkuwieluinnychpraktycznychproblemów,nieistniejąostateczneidoskonałe

odpowiedzi.Wistociewiększośćpytań,którestawiamywzwiązkuzoptymaliza-

cjąkompilatorów,jestnierozstrzygalna.Jednąznajważniejszychumiejętności

potrzebnychwprojektowaniukompilatorówjestzdolnośćdowłaściwegosformu-

łowaniaproblemu,którychcemyrozwiązać.Napoczątekpotrzebujemydobre-

gorozumieniazachowaniaprogramóworazpogłębionegoeksperymentowania

itestowaniawceluweryﬁkacjinaszychintuicji.

Optymalizacjakompilatoramusispełniaćnastępująceceleprojektowe:

•

Optymalizacjamusibyćpoprawna,czylizachowywaćznaczenieskompilo-

wanegoprogramu.

•Optymalizacjamusipoprawiaćwydajnośćwieluprogramów.

•Czaskompilacjimusinadalbyćrozsądny.

•Wymaganywysiłekprojektowymusibyćakceptowalny.

Niemożliwebyłobyprzecenienieważnościpoprawnościoptymalizacji.Trywialne

byłobynapisaniekompilatoragenerującegoszybkikod,gdybytenwygenerowany

kodniemusiałbyćpoprawny!Optymalizowaniekompilatorówjesttaktrudne,

żemożemyzprzekonaniempowiedzieć,żenieistniejeoptymalizującykompilator

całkowiciewolnyodbłędów!

Tymsamymnajważniejszymcelem,którytrzebamiećnawzględzieprzy

pisaniukompilatora,jestpoprawność.

Drugicelgłosi,żekompilatormusibyćskutecznywpoprawianiuwydaj-

nościwieluwejściowychprogramów.Naogółprzezwydajnośćrozumiemy

Brak wyników

Kompilatory

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra