Компиляторы: принципы, технологии и инструментарий

Содержание ......Page 7
Предисловие ......Page 25
1.1 Компиляторы ......Page 30
1.2 Структура компилятора ......Page 33
1.2.1 Лексический анализ ......Page 34
1.2.2 Синтаксический анализ ......Page 36
1.2.3 Семантический анализ ......Page 38
1.2.4 Генерация промежуточного кода ......Page 39
1.2.6 Генерация кода ......Page 40
1.2.7 Управление таблицей символов ......Page 41
1.2.9 Инструментарий для создания компиляторов ......Page 42
1.3.1 Переход к языкам высокого уровня ......Page 43
1.3.2 Влияние на компиляторы ......Page 45
1.4.1 Моделирование при проектировании и реализации компилятора ......Page 46
1.4.2 Изучение оптимизации кода ......Page 47
1.5.1 Реализация высокоуровневых языков программирования ......Page 49
1.5.2 Оптимизация для архитектуры компьютера ......Page 51
1.5.3 Разработка новых архитектур компьютеров ......Page 53
1.5.4 Трансляции программ ......Page 55
1.5.5 Инструментарий для повышения производительности программного обеспечения ......Page 56
1.6 Азы языков программирования ......Page 58
1.6.2 Среды и состояния ......Page 59
1.6.3 Статическая область видимости и блочная структура ......Page 62
1.6.5 Динамическая область видимости ......Page 66
1.6.6 Механизмы передачи параметров ......Page 69
1.6.8 Упражнения к разделу 1.6 ......Page 71
1.7 Резюме к главе 1 ......Page 73
1.8 Список литературы к главе 1 ......Page 74
Глава 2. Простой синтаксически управляемый транслятор ......Page 76
2.1 Введение ......Page 77
2.2 Определение синтаксиса ......Page 79
2.2.1 Определения грамматик ......Page 80
2.2.2 Выведение ......Page 82
2.2.3 Деревья разбора ......Page 83
2.2.4 Неоднозначности ......Page 85
2.2.5 Ассоциативность операторов ......Page 86
2.2.6 Приоритет операторов ......Page 87
2.2.7 Упражнения к разделу 2.2 ......Page 90
2.3 Синтаксически управляемая трансляция ......Page 91
2.3.1 Постфиксная запись ......Page 92
2.3.2 Синтезированные атрибуты ......Page 93
2.3.3 Простые синтаксически управляемые определения ......Page 95
2.3.4 Обходы дерева ......Page 96
2.3.5 Схемы трансляции ......Page 98
2.3.6 Упражнения к разделу 2.3 ......Page 100
2.4 Разбор ......Page 101
2.4.1 Нисходящий анализ ......Page 102
2.4.2 Предиктивный анализ ......Page 105
2.4.4 Разработка предиктивного анализатора ......Page 107
2.4.5 Левая рекурсия ......Page 108
2.5 Транслятор простых выражений ......Page 110
2.5.1 Абстрактный и конкретный синтаксис ......Page 111
2.5.2 Адаптация схемы трансляции ......Page 112
2.5.3 Процедуры для нетерминалов ......Page 114
2.5.4 Упрощение транслятора ......Page 115
2.5.5 Завершенная программа ......Page 116
2.6 Лексический анализ ......Page 119
2.6.1 Удаление пробельных символов и комментариев ......Page 120
2.6.2 Опережающее чтение ......Page 121
2.6.4 Распознавание ключевых слов и идентификаторов ......Page 122
2.6.5 Лексический анализатор ......Page 124
2.7 Таблицы символов ......Page 129
2.7.1 Таблица символов для области видимости ......Page 130
2.7.2 Использование таблиц символов ......Page 134
2.8.1 Два вида промежуточных представлений ......Page 137
2.8.2 Построение синтаксических деревьев ......Page 138
2.8.3 Статические проверки ......Page 143
2.8.4 Трехадресный код ......Page 145
2.8.5 Упражнения к разделу 2.8 ......Page 152
2.9 Резюме к главе 2 ......Page 153
3.1 Роль лексического анализатора ......Page 156
3.1.2 Токены, шаблоны и лексемы ......Page 158
3.1.3 Атрибуты токенов ......Page 160
3.1.4 Лексические ошибки ......Page 161
3.1.5 Упражнения к разделу 3.1 ......Page 162
3.2.1 Пары буферов ......Page 163
3.2.2 Ограничители ......Page 164
3.3.1 Строки и языки ......Page 166
3.3.2 Операции над языками ......Page 167
3.3.3 Регулярные выражения ......Page 169
3.3.4 Регулярные определения ......Page 171
3.3.5 Расширения регулярных выражений ......Page 173
3.3.6 Упражнения к разделу 3.3 ......Page 174
3.4 Распознавание токенов ......Page 178
3.4.1 Диаграммы переходов ......Page 180
3.4.2 Распознавание зарезервированных слов и идентификаторов ......Page 182
3.4.3 Завершение примера ......Page 184
3.4.4 Архитектура лексического анализатора на основе диаграммы переходов ......Page 185
3.4.5 Упражнения к разделу 3.4 ......Page 188
3.5.1 Использование Lex ......Page 192
3.5.2 Структура программ Lex ......Page 193
3.5.3 Разрешение конфликтов в Lex ......Page 197
3.5.4 Прогностический оператор ......Page 198
3.5.5 Упражнения к разделу 3.5 ......Page 199
3.6 Конечные автоматы ......Page 200
3.6.1 Недетерминированные конечные автоматы ......Page 201
3.6.3 Принятие входной строки автоматом ......Page 202
3.6.4 Детерминированный конечный автомат ......Page 204
3.6.5 Упражнения к разделу 3.6 ......Page 205
3.7 От регулярных выражений к автоматам ......Page 206
3.7.1 Преобразование НКА в ДКА ......Page 207
3.7.3 Эффективность моделирования НКА ......Page 211
3.7.4 Построение НКА из регулярного выражения ......Page 214
3.7.5 Эффективность алгоритма обработки строк ......Page 219
3.8.1 Структура генерируемого анализатора ......Page 222
3.8.2 Распознавание шаблонов на основе НКА ......Page 224
3.8.3 ДКА для лексических анализаторов ......Page 226
3.8.4 Реализация прогностического оператора ......Page 227
3.8.5 Упражнения к разделу 3.8 ......Page 229
3.9.1 Важные состояния НКА ......Page 230
3.9.2 Функции, вычисляемые на синтаксическом дереве ......Page 232
3.9.3 Вычисление nullable, firstpos и lastpos ......Page 233
3.9.4 Вычисление followpos ......Page 235
3.9.5 Преобразование регулярного выражения непосредственно в ДКА ......Page 236
3.9.6 Минимизация количества состояний ДКА ......Page 238
3.9.8 Компромисс между скоростью и используемой памятью при моделировании ДКА ......Page 243
3.9.9 Упражнения к разделу 3.9 ......Page 245
3.10 Резюме к главе 3 ......Page 246
3.11 Список литературы к главе 3 ......Page 248
Глава 4. Синтаксический анализ ......Page 252
4.1.1 Роль синтаксического анализатора ......Page 253
4.1.2 Образцы грамматик ......Page 254
4.1.3 Обработка синтаксических ошибок ......Page 255
4.1.4 Стратегии восстановления после ошибок ......Page 257
4.2.1 Формальное определение контекстно-свободной грамматики ......Page 259
4.2.2 Соглашения об обозначениях ......Page 261
4.2.3 Порождения ......Page 262
4.2.4 Деревья разбора и порождения ......Page 264
4.2.5 Неоднозначность ......Page 266
4.2.6 Проверка языка, сгенерированного грамматикой ......Page 267
4.2.7 Контекстно-свободные грамматики и регулярные выражения ......Page 268
4.2.8 Упражнения к разделу 4.2 ......Page 270
4.3 Разработка грамматики ......Page 273
4.3.2 Устранение неоднозначности ......Page 274
4.3.3 Устранение левой рекурсии ......Page 276
4.3.4 Левая факторизация ......Page 279
4.3.5 Не контекстно-свободные языковые конструкции ......Page 280
4.3.6 Упражнения к разделу 4.3 ......Page 281
4.4 Нисходящий синтаксический анализ ......Page 282
4.4.1 Синтаксический анализ методом рекурсивного спуска ......Page 284
4.4.2 FIRST и FOLLOW ......Page 286
4.4.3 LL(1)-грамматики ......Page 289
4.4.4 Нерекурсивный предиктивный синтаксический анализ ......Page 293
4.4.5 Восстановление после ошибок в предиктивном синтаксическом анализе ......Page 296
4.4.6 Упражнения к разделу 4.4 ......Page 299
4.5 Восходящий синтаксический анализ ......Page 302
4.5.2 Обрезка основ ......Page 303
4.5.3 Синтаксический анализ "перенос/свертка" ......Page 305
4.5.4 Конфликты в процессе ПС-анализа ......Page 307
4.6 Введение в LR-анализ: простой LR ......Page 310
4.6.1 Обоснование использования LR-анализаторов ......Page 311
4.6.2 Пункты и 1Ж(0)-автомат ......Page 312
4.6.3 Алгоритм LR-анализа ......Page 318
4.6.4 Построение таблиц SLR-анализа ......Page 323
4.6.5 Активные префиксы ......Page 327
4.6.6 Упражнения к разделу 4.6 ......Page 329
4.7 Более мощные LR-анализаторы ......Page 331
4.7.1 Канонические 1Л(1)-пункты ......Page 332
4.7.2 Построение множеств LR(l)-nyHKTOB ......Page 333
4.7.3 Канонические таблицы 1Л(1)-анализа ......Page 337
4.7.4 Построение LALR-таблиц синтаксического анализа ......Page 339
4.7.5 Эффективное построение таблиц LALR-анализа ......Page 345
4.7.6 Уплотнение таблиц LR-анализа ......Page 350
4.7.7 Упражнения к разделу 4.7 ......Page 353
4.8.1 Использование приоритетов и ассоциативности для разрешения конфликтов ......Page 354
4.8.2 Неоднозначность "висящего else" ......Page 358
4.8.3 Восстановление после ошибок в LR-анализе ......Page 359
4.8.4 Упражнения к разделу 4.8 ......Page 362
4.9 Генераторы синтаксических анализаторов ......Page 364
4.9.1 Генератор синтаксических анализаторов Yacc ......Page 365
4.9.2 Использование Yacc с неоднозначной грамматикой ......Page 369
4.9.3 Создание лексического анализатора в Yacc с помощью Lex ......Page 372
4.9.4 Восстановление после ошибок в Yacc ......Page 373
4.10 Резюме к главе 4 ......Page 376
4.11 Список литературы к главе 4 ......Page 379
Глава 5. Синтаксически управляемая трансляция ......Page 384
5.1.1 Наследуемые и синтезируемые атрибуты ......Page 385
5.1.2 Вычисление СУО в узлах дерева разбора ......Page 388
5.1.3 Упражнения к разделу 5.1 ......Page 391
5.2.1 Графы зависимостей ......Page 392
5.2.2 Упорядочение вычисления атрибутов ......Page 394
5.2.4 L-атрибутные определения ......Page 395
5.2.5 Семантические правила с контролируемыми побочными действиями ......Page 397
5.2.6 Упражнения к разделу 5.2 ......Page 399
5.3 Применения синтаксически управляемой трансляции ......Page 400
5.3.1 Построение синтаксических деревьев ......Page 401
5.3.2 Структура типа ......Page 405
5.4 Синтаксически управляемые схемы трансляции ......Page 407
5.4.2 Реализация постфиксной СУТ с использованием стека синтаксического анализатора ......Page 408
5.4.3 СУТ с действиями внутри продукций ......Page 411
5.4.4 Устранение левой рекурсии из СУТ ......Page 412
5.4.5 СУТ для L-атрибутных определений ......Page 415
5.4.6 Упражнения к разделу 5.4 ......Page 422
5.5 Реализация L-атрибутных СУО ......Page 423
5.5.1 Трансляция в процессе синтаксического анализа методом рекурсивного спуска ......Page 424
5.5.2 Генерация кода "на лету" ......Page 426
5.5.3 L-атрибутные СУО и LL-синтаксический анализ ......Page 429
5.5.4 Восходящий синтаксический анализ L-атрибутных СУО ......Page 435
5.6 Резюме к главе 5 ......Page 440
5.7 Список литературы к главе 5 ......Page 442
Глава 6. Генерация промежуточного кода ......Page 444
6.1.1 Ориентированные ациклические графы для выражений ......Page 446
6.1.2 Метод номера значения для построения ориентированных ациклических графов ......Page 448
6.2.1 Адреса и команды ......Page 451
6.2.2 Четверки ......Page 455
6.2.3 Тройки ......Page 456
6.2.4 Представление в виде статических единственных присваиваний ......Page 458
6.2.5 Упражнения к разделу 6.2 ......Page 459
6.3.1 Выражения типов ......Page 460
6.3.2 Эквивалентность типов ......Page 462
6.3.4 Размещение локальных имен в памяти ......Page 463
6.3.5 Последовательности объявлений ......Page 465
6.3.6 Поля в записях и классах ......Page 467
6.3.7 Упражнения к разделу 6.3 ......Page 468
6.4.1 Операции в выражениях ......Page 469
6.4.2 Инкрементная трансляция ......Page 471
6.4.3 Адресация элементов массива ......Page 472
6.4.4 Трансляция обращений к массиву ......Page 474
6.4.5 Упражнения к разделу 6.4 ......Page 476
6.5.1 Правила проверки типов ......Page 478
6.5.2 Преобразования типов ......Page 479
6.5.3 Перегрузка функций и операторов ......Page 482
6.5.4 Выведение типа и полиморфные функции ......Page 483
6.5.5 Алгоритм унификации ......Page 488
6.5.6 Упражнения к разделу 6.5 ......Page 491
6.6 Поток управления ......Page 492
6.6.2 Код сокращенного вычисления ......Page 493
6.6.3 Инструкции потока управления ......Page 494
6.6.4 Трансляция логических выражений с помощью потока управления ......Page 497
6.6.5 Устранение излишних команд перехода ......Page 500
6.6.6 Булевы значения и код с переходами ......Page 502
6.6.7 Упражнения к разделу 6.6 ......Page 503
6.7.1 Однопроходная генерация кода с использованием обратных поправок ......Page 505
6.7.2 Обратные поправки для булевых выражений ......Page 506
6.7.3 Инструкции потока управления ......Page 509
6.7.4 Инструкции break, continue и goto ......Page 512
6.7.5 Упражнения к разделу 6.7 ......Page 513
6.8.1 Трансляция инструкций выбора ......Page 515
6.8.2 Синтаксически управляемая трансляция инструкций выбора ......Page 516
6.9 Промежуточный код процедур ......Page 518
6.10 Резюме к главе 6 ......Page 521
6.11 Список литературы к главе 6 ......Page 522
7.1 Организация памяти ......Page 526
7.1.1 Статическое и динамическое распределение памяти ......Page 528
7.2 Выделение памяти в стеке ......Page 529
7.2.1 Деревья активации ......Page 530
7.2.2 Записи активации ......Page 533
7.2.3 Последовательности вызовов ......Page 536
7.2.4 Данные переменной длины в стеке ......Page 540
7.2.5 Упражнения к разделу 7.2 ......Page 541
7.3.1 Доступ к данным при отсутствии вложенных процедур ......Page 543
7.3.2 Вложенные процедуры ......Page 544
7.3.3 Язык с вложенными объявлениями процедур ......Page 545
7.3.4 Глубина вложенности ......Page 546
7.3.5 Связи доступа ......Page 548
7.3.6 Работа со связями доступа ......Page 549
7.3.7 Связи доступа для процедур, являющихся параметрами ......Page 551
7.3.8 Дисплеи ......Page 552
7.3.9 Упражнения к разделу 7.3 ......Page 555
7.4.1 Диспетчер памяти ......Page 556
7.4.2 Иерархия памяти компьютера ......Page 558
7.4.3 Локальность в программах ......Page 560
7.4.4 Снижение фрагментации ......Page 562
7.4.5 Освобождение памяти вручную ......Page 566
7.5 Введение в сборку мусора ......Page 569
7.5.1 Цели проектирования сборщиков мусора ......Page 570
7.5.2 Достижимость ......Page 573
7.5.3 Сборщики мусора с подсчетом ссылок ......Page 575
7.6 Введение в сборку на основе отслеживания ......Page 577
7.6.1 Базовый сборщик мусора ......Page 578
7.6.2 Базовая абстракция ......Page 581
7.6.3 Оптимизация алгоритма "пометить и подмести" ......Page 583
7.6.4 Сборщики мусора "пометить и сжать" ......Page 584
7.6.5 Копирующие сборщики ......Page 588
7.6.6 Сравнение стоимости ......Page 590
7.6.7 Упражнения к разделу 7.6 ......Page 591
7.7.1 Инкрементная сборка мусора ......Page 592
7.7.2 Инкрементный анализ достижимости ......Page 594
7.7.3 Основы частичной сборки ......Page 597
7.7.4 Сборка мусора по поколениям ......Page 598
7.7.5 Алгоритм поезда ......Page 600
7.7.6 Упражнения к разделу 7.7 ......Page 604
7.8 Дополнительные вопросы сборки мусора ......Page 605
7.8.1 Параллельная сборка мусора ......Page 606
7.8.3 Консервативная сборка мусора для небезопасных языков программирования ......Page 609
7.8.4 Слабые ссылки ......Page 610
7.8.5 Упражнения к разделу 7.8 ......Page 611
7.9 Резюме к главе 7 ......Page 612
7.10 Список литературы к главе 7 ......Page 615
Глава 8. Генерация кода ......Page 618
8.1.1 Вход генератора кода ......Page 620
8.1.2 Целевая программа ......Page 621
8.1.3 Выбор команд ......Page 622
8.1.4 Распределение регистров ......Page 624
8.1.5 Порядок вычислений 62 ......Page 6
8.2.1 Простая модель целевой машины ......Page 626
8.2.2 Стоимость программ и команд ......Page 630
8.2.3 Упражнения к разделу 8.2 ......Page 631
8.3.1 Статическое выделение памяти ......Page 633
8.3.2 Выделение памяти в стеке ......Page 636
8.3.3 Адреса имен времени выполнения ......Page 639
8.3.4 Упражнения к разделу 8.3 ......Page 640
8.4 Базовые блоки и графы потоков ......Page 641
8.4.1 Базовые блоки ......Page 642
8.4.2 Информация о дальнейшем использовании ......Page 644
8.4.3 Графы потоков ......Page 645
8.4.5 Циклы ......Page 647
8.4.6 Упражнения к разделу 8.4 ......Page 648
8.5.1 Представление базовых блоков с использованием ориентированных ациклических графов ......Page 649
8.5.2 Поиск локальных общих подвыражений ......Page 650
8.5.3 Устранение неиспользуемого кода ......Page 652
8.5.4 Применение алгебраических тождеств ......Page 653
8.5.5 Представление обращений к массивам ......Page 654
8.5.6 Присваивание указателей и вызовы процедур ......Page 656
8.5.7 Сборка базового блока из ориентированного ациклического графа ......Page 657
8.5.8 Упражнения к разделу 8.5 ......Page 659
8.6 Простой генератор кода ......Page 661
8.6.2 Алгоритм генерации кода ......Page 662
8.6.3 Разработка функции getReg ......Page 666
8.6.4 Упражнения к разделу 8.6 ......Page 668
8.7.1 Устранение излишних загрузок и сохранений ......Page 669
8.7.2 Устранение недостижимого кода ......Page 670
8.7.3 Оптимизация потока управления ......Page 671
8.7.6 Упражнения к разделу 8.7 ......Page 672
8.8.1 Глобальное распределение регистров ......Page 673
8.8.2 Счетчики использований ......Page 674
8.8.4 Распределение регистров путем раскраски графа ......Page 677
8.9 Выбор команд путем переписывания дерева ......Page 678
8.9.1 Схемы трансляции деревьев ......Page 679
8.9.2 Генерация кода путем замощения входного дерева ......Page 682
8.9.3 Поиск соответствий с использованием синтаксического анализа ......Page 685
8.9.4 Программы семантической проверки ......Page 686
8.9.5 Обобщенный поиск соответствий ......Page 687
8.10 Генерация оптимального кода для выражений ......Page 689
8.10.1 Числа Ершова ......Page 690
8.10.2 Генерация кода на основе помеченных деревьев выражений ......Page 691
8.10.3 Вычисление выражений при недостаточном количестве регистров ......Page 693
8.10.4 Упражнения к разделу 8.10 ......Page 695
8.11 Генерация кода с использованием динамического программирования ......Page 696
8.11.1 Последовательные вычисления ......Page 697
8.11.2 Алгоритм динамического программирования ......Page 698
8.12 Резюме к главе 8 ......Page 701
8.13 Список литературы к главе 8 ......Page 703
Глава 9. Машинно-независимые оптимизации ......Page 706
9.1.1 Причины избыточности ......Page 707
9.1.2 Конкретный пример: быстрая сортировка ......Page 708
9.1.4 Глобальные общие подвыражения ......Page 711
9.1.5 Распространение копий ......Page 713
9.1.6 Удаление бесполезного кода ......Page 714
9.1.7 Перемещение кода ......Page 715
9.1.8 Переменные индукции и снижение стоимости ......Page 716
9.1.9 Упражнения к разделу 9.1 ......Page 719
9.2 Введение в анализ потоков данных ......Page 720
9.2.1 Абстракция потока данных ......Page 721
9.2.2 Схема анализа потока данных ......Page 723
9.2.3 Схемы потоков данных в базовых блоках ......Page 724
9.2.4 Достигающие определения ......Page 726
9.2.5 Анализ активных переменных ......Page 734
9.2.6 Доступные выражения ......Page 736
9.2.8 Упражнения к разделу 9.2 ......Page 741
9.3 Основы анализа потока данных ......Page 744
9.3.1 Полурешетки ......Page 745
9.3.2 Передаточные функции ......Page 751
9.3.3 Итеративный алгоритм в обобщенной структуре ......Page 754
9.3.4 Смысл решения потока данных ......Page 756
9.3.5 Упражнения к разделу 9.3 ......Page 760
9.4 Распространение констант ......Page 761
9.4.1 Значения потока данных для структуры распространения констант ......Page 762
9.4.3 Передаточные функции для структуры распространения констант ......Page 763
9.4.4 Монотонность структуры распространения констант ......Page 764
9.4.5 Недистрибутивность структуры распространения констант ......Page 765
9.4.6 Интерпретация результатов ......Page 766
9.4.7 Упражнения к разделу 9.4 ......Page 768
9.5 Устранение частичной избыточности ......Page 769
9.5.1 Источники избыточности ......Page 770
9.5.2 Все ли избыточные вычисления могут быть устранены? ......Page 772
9.5.3 Отложенное перемещение кода ......Page 774
9.5.4 Ожидаемость выражений ......Page 775
9.5.5 Алгоритм отложенного перемещения кода ......Page 776
9.5.6 Упражнения к разделу 9.5 ......Page 786
9.6.1 Доминаторы ......Page 788
9.6.2 Упорядочение в глубину ......Page 791
9.6.3 Ребра в глубинном остовном дереве ......Page 793
9.6.4 Обратные ребра и приводимость ......Page 795
9.6.5 Глубина графа потока ......Page 796
9.6.6 Естественные циклы ......Page 797
9.6.7 Скорость сходимости итеративных алгоритмов потоков данных ......Page 799
9.6.8 Упражнения к разделу 9.6 ......Page 802
9.7 Анализ на основе областей ......Page 804
9.7.1 Области ......Page 805
9.7.2 Иерархии областей для приводимых графов потоков ......Page 806
9.7.3 Обзор анализа на основании областей ......Page 809
9.7.4 Необходимые предположения о передаточных функциях ......Page 811
9.7.5 Алгоритм анализа на основе областей ......Page 812
9.7.6 Обработка неприводимых графов потоков ......Page 817
9.7.7 Упражнения к разделу 9.7 ......Page 819
9.8.1 Аффинные выражения ссылочных переменных ......Page 820
9.8.2 Формулировка задачи потока данных ......Page 823
9.8.3 Символический анализ на основе областей ......Page 828
9.8.4 Упражнения к разделу 9.8 ......Page 833
9.9 Резюме к главе 9 ......Page 834
9.10 Список литературы к главе 9 ......Page 839
Глава 10. Параллелизм на уровне команд ......Page 842
10.1.1 Конвейерная обработка команд и задержки ветвления ......Page 843
10.1.2 Конвейерное выполнение ......Page 844
10.1.3 Многоадресные команды ......Page 845
10.2 Ограничения планирования кода ......Page 846
10.2.2 Поиск зависимостей среди обращений к памяти ......Page 847
10.2.3 Компромиссы между использованием регистров и параллелизмом ......Page 849
10.2.4 Упорядочение фаз распределения регистров и планирования кода ......Page 852
10.2.5 Зависимость от управления ......Page 853
10.2.6 Поддержка опережающего выполнения ......Page 854
10.2.7 Базовая модель машины ......Page 856
10.2.8 Упражнения к разделу 10.2 ......Page 857
10.3 Планирование базовых блоков ......Page 858
10.3.1 Графы зависимости данных ......Page 859
10.3.2 Планирование списков базовых блоков ......Page 860
10.3.3 Приоритетные топологические порядки ......Page 862
10.3.4 Упражнения к разделу 10.3 ......Page 864
10.4 Глобальное планирование кода ......Page 865
10.4.1 Примитивное перемещение кода ......Page 866
10.4.2 Восходящее перемещение кода ......Page 868
10.4.3 Нисходящее перемещение кода ......Page 869
10.4.5 Алгоритм глобального планирования ......Page 871
10.4.6 Усовершенствованные методы перемещения кода ......Page 875
10.4.7 Взаимодействие с динамическими планировщиками ......Page 876
10.5 Программная конвейеризация ......Page 877
10.5.1 Введение ......Page 878
10.5.2 Программная конвейеризация циклов ......Page 880
10.5.3 Распределение регистров и генерация кода ......Page 883
10.5.4 Циклы с зависимыми итерациями ......Page 884
10.5.5 Цели и ограничения программной конвейеризации ......Page 885
10.5.6 Алгоритм программной конвейеризации ......Page 889
10.5.7 Планирование ациклических графов зависимости данных ......Page 890
10.5.8 Планирование графов с циклическими зависимостями ......Page 892
10.5.9 Усовершенствования алгоритма конвейеризации ......Page 900
10.5.10 Модульное расширение переменных ......Page 901
10.5.11 Условные инструкции ......Page 904
10.5.13 Упражнения к разделу 10.5 ......Page 905
10.6 Резюме к главе 10 ......Page 908
10.7 Список литературы к главе 10 ......Page 910
Глава 11. Оптимизация параллелизма и локальности ......Page 912
11.1.1 Многопроцессорность ......Page 915
11.1.2 Параллелизм в приложениях ......Page 918
11.1.3 Параллелизм на уровне циклов ......Page 919
11.1.4 Локальность данных ......Page 921
11.1.5 Введение в теорию аффинных преобразований ......Page 923
11.2.1 Алгоритм умножения матриц ......Page 928
11.2.2 Оптимизации ......Page 931
11.2.4 Упражнения к разделу 11.2 ......Page 934
11.3.1 Построение пространств итераций вложений циклов ......Page 935
11.3.2 Порядок выполнения вложенности циклов ......Page 937
11.3.4 Добавление символьных констант ......Page 939
11.3.5 Управление порядком выполнения ......Page 940
11.3.6 Изменение осей ......Page 945
11.3.7 Упражнения к разделу 11.3 ......Page 946
11.4.1 Аффинные обращения к данным ......Page 949
11.4.2 Аффинное и неаффинное обращения на практике ......Page 950
11.4.3 Упражнения к разделу 11.4 ......Page 951
11.5 Повторное использование данных ......Page 952
11.5.1 Типы повторных использований ......Page 953
11.5.2 Собственные повторные использования ......Page 954
11.5.3 Собственное пространственное повторное использование ......Page 959
11.5.4 Групповое повторное использование ......Page 960
11.5.5 Упражнения к разделу 11.5 ......Page 963
11.6 Анализ зависимости данных в массивах ......Page 965
11.6.1 Определение зависимостей данных доступов к массивам ......Page 966
11.6.2 Целочисленное линейное программирование ......Page 967
11.6.3 НОД ......Page 968
11.6.4 Эвристики для решения задачи целочисленного линейного программирования ......Page 970
11.6.5 Решение обобщенной задачи целочисленного линейного программирования ......Page 974
11.6.6 Резюме ......Page 976
11.6.7 Упражнения к разделу 11.6 ......Page 977
11.7.1 Вводный пример ......Page 979
11.7.2 Разбиения аффинного пространства ......Page 982
11.7.3 Ограничения разбиений пространства ......Page 983
11.7.4 Решение ограничений разбиений пространств ......Page 987
11.7.5 Простой алгоритм генерации кода ......Page 991
11.7.6 Устранение пустых итераций ......Page 994
11.7.7 Устранение проверок из внутреннего цикла ......Page 997
11.7.8 Преобразования исходного кода ......Page 999
11.7.9 Упражнения к разделу 11.7 ......Page 1004
11.8 Синхронизация между параллельными циклами ......Page 1006
11.8.1 Постоянное количество синхронизации ......Page 1007
11.8.2 Графы зависимостей программ ......Page 1008
11.8.3 Иерархическое время ......Page 1010
11.8.4 Алгоритм распараллеливания ......Page 1013
11.9 Конвейеризация ......Page 1014
11.9.1 Что такое конвейеризация ......Page 1015
11.9.2 Последовательная сверхрелаксация: пример ......Page 1017
11.9.3 Полностью переставляемые циклы ......Page 1018
11.9.4 Конвейеризация полностью переставляемых циклов ......Page 1019
11.9.5 Общая теория ......Page 1022
11.9.6 Ограничения временного разбиения ......Page 1023
11.9.7 Решение временных ограничений с использованием леммы Фаркаша ......Page 1027
11.9.8 Преобразования кода ......Page 1030
11.9.9 Параллелизм с минимальной синхронизацией ......Page 1036
11.9.10 Упражнения к разделу 11.9 ......Page 1038
11.10 Оптимизации локальности ......Page 1040
11.10.1 Временная локальность вычисляемых данных ......Page 1041
11.10.2 Сжатие массива ......Page 1042
11.10.3 Чередование частей ......Page 1045
11.10.4 Алгоритмы оптимизации локальности ......Page 1048
11.11.1 Машины с распределенной памятью ......Page 1051
11.11.2 Процессоры с одновременным выполнением нескольких команд ......Page 1052
11.11.3 Векторные и SIMD-команды ......Page 1053
11.11.4 Предвыборка ......Page 1054
11.12 Резюме к главе 11 ......Page 1055
11.13 Список литературы к главе 11 ......Page 1058
Глава 12. Межпроцедурный анализ ......Page 1062
12.1.1 Графы вызовов ......Page 1063
12.1.2 Чувствительность к контексту ......Page 1065
12.1.3 Строки вызовов ......Page 1068
12.1.4 Контекстно-чувствительный анализ на основе клонирования ......Page 1070
12.1.5 Контекстно-чувствительный анализ на основе резюме ......Page 1071
12.1.6 Упражнения к разделу 12.1 ......Page 1074
12.2 Необходимость межпроцедурного анализа ......Page 1076
12.2.2 Анализ псевдонимов указателей ......Page 1077
12.2.4 Поиск программных ошибок и уязвимых мест ......Page 1078
12.2.5 SQL-ввод ......Page 1079
12.2.6 Переполнение буфера ......Page 1081
12.3 Логическое представление потока данных ......Page 1082
12.3.1 Введение в Datalog ......Page 1083
12.3.2 Правила Datalog ......Page 1084
12.3.3 Интенсиональные и экстенсиональные предикаты ......Page 1086
12.3.4 Выполнение программы Datalog ......Page 1089
12.3.5 Инкрементное вычисление программ Datalog ......Page 1091
12.3.6 Проблематичные правила Datalog ......Page 1092
12.3.7 Упражнения к разделу 12.3 ......Page 1094
12.4 Простой алгоритм анализа указателей ......Page 1096
12.4.1 Сложность анализа указателей ......Page 1097
12.4.2 Модель указателей и ссылок ......Page 1098
12.4.3 Нечувствительность к потоку ......Page 1099
12.4.4 Формулировка с применением Datalog ......Page 1100
12.4.5 Использование информации о типе ......Page 1102
12.4.6 Упражнения к разделу 12.4 ......Page 1103
12.5.1 Влияние вызовов методов ......Page 1106
12.5.2 Построение графа вызовов в Datalog ......Page 1108
12.5.3 Динамическая загрузка и отражение ......Page 1109
12.6 Контекстно-чувствительный анализ указателей ......Page 1110
12.6.1 Контексты и строки вызовов ......Page 1111
12.6.2 Добавление контекста в правила Datalog ......Page 1114
12.6.3 Дополнительные наблюдения о чувствительности ......Page 1115
12.7 Реализация Datalog с применением BDD ......Page 1116
12.7.1 Диаграммы бинарного выбора ......Page 1117
12.7.2 Преобразования диаграмм бинарного выбора ......Page 1119
12.7.3 Представление отношений при помощи BDD ......Page 1120
12.7.4 Операции отношений и BDD-операции ......Page 1121
12.7.5 Использование диаграмм бинарного выбора для анализа целей указателей ......Page 1124
12.8 Резюме к главе 12 ......Page 1125
12.9 Список литературы к главе 12 ......Page 1129
А.1 Исходный язык ......Page 1134
А.З Лексический анализатор ......Page 1136
А.4 Таблицы символов и типы ......Page 1140
А.5 Промежуточный код выражений ......Page 1141
А.6 Переходы для булевых выражений ......Page 1145
А.7 Промежуточный код для инструкций ......Page 1150
А.8 Синтаксический анализатор ......Page 1154
А.9 Построение начальной стадии ......Page 1161
Приложение Б. Поиск линейно независимых решений ......Page 1164
Предметный указатель ......Page 1168