Главная » 2020 » Май » 23 » Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. - Компиляторы: принципы, технологии и инструментарий, 2-е издание (2018)
14:45
Скачать Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. - Компиляторы: принципы, технологии и инструментарий, 2-е издание (2018)
Каждый, кто интересовался разработкой компиляторов, не мог не слышать о знаменитой "Книге Дракона", классическом труде Ахо и Ульмана "Принципы разработки компиляторов". Развитие технологий компиляции привело к рождению очередного "дракона" — книги "Компиляторы. Принципы, технологии, инструментарий", — у которой теперь уже четыре автора, и каждый из них является высококлассным специалистом в данной области. Книга, как и предыдущее издание, начинается с изложения основных принципов разработки компиляторов, включая детальное рассмотрение лексического и синтаксического анализа и генерации кода. Особенностью данного издания является широкое освещение вопросов оптимизации кода, в том числе для работы в многопроцессорных системах. Строгость изложения материала смягчается большим количеством практических примеров. Написание компиляторов охватывает такие области знаний, как языки программирования, архитектура вычислительных систем, алгоритмы и технология создания программного обеспечения. Помочь в освоении этих технологий и соответствующего инструментария и призвана данная книга. Несмотря на ее учебную ориентацию — в первую очередь, она предназначена для студентов и преподавателей соответствующих специальностей — книга будет полезна всем, кто просто работает над созданием компиляторов.
Предисловие 24 Глава 1. Введение в компиляцию 29 1.1 Компиляторы 29 1.1.1 Упражнения к разделу 1.1 32 1.2 Структура компилятора 32 1.2.1 Лексический анализ 33 1.2.2 Синтаксический анализ 35 1.2.3 Семантический анализ 37 1.2.4 Генерация промежуточного кода 38 1.2.5 Оптимизация кода 39 1.2.6 Генерация кода 39 1.2.7 Управление таблицей символов 40 1.2.8 Объединение фаз в проходы 41 1.2.9 Инструментарий для создания компиляторов 41 1.3 Эволюция языков программирования 42 1.3.1 Переход к языкам высокого уровня 42 1.3.2 Влияние на компиляторы 44 1.3.3 Упражнения к разделу 1.3 45 1.4 “Компилятороведение” 45 1.4.1 Моделирование при проектировании и реализации компилятора 45 1.4.2 Изучение оптимизации кода 46 1.5 Применения технологий компиляторов 48 1.5.1 Реализация высокоуровневых языков программирования 48 1.5.2 Оптимизация для архитектуры компьютера 50 1.5.3 Разработка новых архитектур компьютеров 52 1.5.4 Трансляции программ 54 1.5.5 Инструментарий для повышения производительности программного обеспечения 55Содержание 7 1.6 Азы языков программирования 57 1.6.1 Понятия статического и динамического 58 1.6.2 Среды и состояния 58 1.6.3 Статическая область видимости и блочная структура 61 1.6.4 Явное управление доступом 65 1.6.5 Динамическая область видимости 65 1.6.6 Механизмы передачи параметров 68 1.6.7 Псевдонимы 70 1.6.8 Упражнения к разделу 1.6 70 1.7 Резюме к главе 1 72 1.8 Список литературы к главе 1 73 Глава 2. Простой синтаксически управляемый транслятор 75 2.1 Введение 76 2.2 Определение синтаксиса 78 2.2.1 Определения грамматик 79 2.2.2 Выведение 81 2.2.3 Деревья разбора 82 2.2.4 Неоднозначности 84 2.2.5 Ассоциативность операторов 85 2.2.6 Приоритет операторов 86 2.2.7 Упражнения к разделу 2.2 89 2.3 Синтаксически управляемая трансляция 90 2.3.1 Постфиксная запись 91 2.3.2 Синтезированные атрибуты 92 2.3.3 Простые синтаксически управляемые определения 94 2.3.4 Обходы дерева 95 2.3.5 Схемы трансляции 97 2.3.6 Упражнения к разделу 2.3 99 2.4 Разбор 100 2.4.1 Нисходящий анализ 101 2.4.2 Предиктивный анализ 104 2.4.3 Использование пустых продукций 106 2.4.4 Разработка предиктивного анализатора 106 2.4.5 Левая рекурсия 107 2.4.6 Упражнения к разделу 2.4 109 2.5 Транслятор простых выражений 109 2.5.1 Абстрактный и конкретный синтаксис 110 2.5.2 Адаптация схемы трансляции 111 2.5.3 Процедуры для нетерминалов 113 2.5.4 Упрощение транслятора 1148 Содержание 2.5.5 Завершенная программа 115 2.6 Лексический анализ 118 2.6.1 Удаление пробельных символов и комментариев 119 2.6.2 Опережающее чтение 120 2.6.3 Константы 121 2.6.4 Распознавание ключевых слов и идентификаторов 121 2.6.5 Лексический анализатор 123 2.6.6 Упражнения к разделу 2.6 128 2.7 Таблицы символов 128 2.7.1 Таблица символов для области видимости 129 2.7.2 Использование таблиц символов 133 2.8 Генерация промежуточного кода 136 2.8.1 Два вида промежуточных представлений 136 2.8.2 Построение синтаксических деревьев 137 2.8.3 Статические проверки 142 2.8.4 Трехадресный код 144 2.8.5 Упражнения к разделу 2.8 151 2.9 Резюме к главе 2 152 Глава 3. Лексический анализ 155 3.1 Роль лексического анализатора 155 3.1.1 Лексический и синтаксический анализ 157 3.1.2 Токены, шаблоны и лексемы 157 3.1.3 Атрибуты токенов 159 3.1.4 Лексические ошибки 160 3.1.5 Упражнения к разделу 3.1 161 3.2 Буферизация ввода 162 3.2.1 Пары буферов 162 3.2.2 Ограничители 163 3.3 Спецификация токенов 165 3.3.1 Строки и языки 165 3.3.2 Операции над языками 166 3.3.3 Регулярные выражения 168 3.3.4 Регулярные определения 170 3.3.5 Расширения регулярных выражений 172 3.3.6 Упражнения к разделу 3.3 173 3.4 Распознавание токенов 177 3.4.1 Диаграммы переходов 179 3.4.2 Распознавание зарезервированных слов и идентификаторов 181 3.4.3 Завершение примера 183Содержание 9 3.4.4 Архитектура лексического анализатора на основе диаграммы переходов 184 3.4.5 Упражнения к разделу 3.4 187 3.5 Генератор лексических анализаторов Lex 191 3.5.1 Использование Lex 191 3.5.2 Структура программ Lex 192 3.5.3 Разрешение конфликтов в Lex 196 3.5.4 Прогностический оператор 197 3.5.5 Упражнения к разделу 3.5 198 3.6 Конечные автоматы 199 3.6.1 Недетерминированные конечные автоматы 200 3.6.2 Таблицы переходов 201 3.6.3 Принятие входной строки автоматом 201 3.6.4 Детерминированный конечный автомат 203 3.6.5 Упражнения к разделу 3.6 204 3.7 От регулярных выражений к автоматам 205 3.7.1 Преобразование НКА в ДКА 206 3.7.2 Моделирование НКА 210 3.7.3 Эффективность моделирования НКА 210 3.7.4 Построение НКА из регулярного выражения 213 3.7.5 Эффективность алгоритма обработки строк 218 3.7.6 Упражнения к разделу 3.7 221 3.8 Разработка генератора лексических анализаторов 221 3.8.1 Структура генерируемого анализатора 221 3.8.2 Распознавание шаблонов на основе НКА 223 3.8.3 ДКА для лексических анализаторов 225 3.8.4 Реализация прогностического оператора 226 3.8.5 Упражнения к разделу 3.8 228 3.9 Оптимизация распознавателей на основе ДКА 229 3.9.1 Важные состояния НКА 229 3.9.2 Функции, вычисляемые на синтаксическом дереве 231 3.9.3 Вычисление nullable, firstpos и lastpos 232 3.9.4 Вычисление followpos 234 3.9.5 Преобразование регулярного выражения непосредственно в ДКА 235 3.9.6 Минимизация количества состояний ДКА 237 3.9.7 Минимизация состояний в лексических анализаторах 242 3.9.8 Компромисс между скоростью и используемой памятью при моделировании ДКА 242 3.9.9 Упражнения к разделу 3.9 24410 Содержание 3.10 Резюме к главе 3 245 3.11 Список литературы к главе 3 247 Глава 4. Синтаксический анализ 251 4.1 Введение 252 4.1.1 Роль синтаксического анализатора 252 4.1.2 Образцы грамматик 253 4.1.3 Обработка синтаксических ошибок 254 4.1.4 Стратегии восстановления после ошибок 256 4.2 Контекстно-свободные грамматики 258 4.2.1 Формальное определение контекстно-свободной грамматики 258 4.2.2 Соглашения об обозначениях 260 4.2.3 Порождения 261 4.2.4 Деревья разбора и порождения 263 4.2.5 Неоднозначность 265 4.2.6 Проверка языка, сгенерированного грамматикой 266 4.2.7 Контекстно-свободные грамматики и регулярные выражения 267 4.2.8 Упражнения к разделу 4.2 269 4.3 Разработка грамматики 272 4.3.1 Лексический и синтаксический анализ 273 4.3.2 Устранение неоднозначности 273 4.3.3 Устранение левой рекурсии 275 4.3.4 Левая факторизация 278 4.3.5 Не контекстно-свободные языковые конструкции 279 4.3.6 Упражнения к разделу 4.3 280 4.4 Нисходящий синтаксический анализ 281 4.4.1 Синтаксический анализ методом рекурсивного спуска 283 4.4.2 FIRST и FOLLOW 285 4.4.3 LL(1)-грамматики 288 4.4.4 Нерекурсивный предиктивный синтаксический анализ 292 4.4.5 Восстановление после ошибок в предиктивном синтаксическом анализе 295 4.4.6 Упражнения к разделу 4.4 298 4.5 Восходящий синтаксический анализ 301 4.5.1 Свертки 302 4.5.2 Обрезка основ 302 4.5.3 Синтаксический анализ “перенос/свертка” 304 4.5.4 Конфликты в процессе ПС-анализа 306 4.5.5 Упражнения к разделу 4.5 309Содержание 11 4.6 Введение в LR-анализ: простой LR 309 4.6.1 Обоснование использования LR-анализаторов 310 4.6.2 Пункты и LR(0)-автомат 311 4.6.3 Алгоритм LR-анализа 317 4.6.4 Построение таблиц SLR-анализа 322 4.6.5 Активные префиксы 326 4.6.6 Упражнения к разделу 4.6 328 4.7 Более мощные LR-анализаторы 330 4.7.1 Канонические LR(1)-пункты 331 4.7.2 Построение множеств LR(1)-пунктов 332 4.7.3 Канонические таблицы LR(1)-анализа 336 4.7.4 Построение LALR-таблиц синтаксического анализа 338 4.7.5 Эффективное построение таблиц LALR-анализа 344 4.7.6 Уплотнение таблиц LR-анализа 349 4.7.7 Упражнения к разделу 4.7 352 4.8 Использование неоднозначных грамматик 353 4.8.1 Использование приоритетов и ассоциативности для разрешения конфликтов 353 4.8.2 Неоднозначность “висящего else” 357 4.8.3 Восстановление после ошибок в LR-анализе 358 4.8.4 Упражнения к разделу 4.8 361 4.9 Генераторы синтаксических анализаторов 363 4.9.1 Генератор синтаксических анализаторов Yacc 364 4.9.2 Использование Yacc с неоднозначной грамматикой 368 4.9.3 Создание лексического анализатора в Yacc с помощью Lex 371 4.9.4 Восстановление после ошибок в Yacc 372 4.9.5 Упражнения к разделу 4.9 375 4.10 Резюме к главе 4 375 4.11 Список литературы к главе 4 378 Глава 5. Синтаксически управляемая трансляция 383 5.1 Синтаксически управляемые определения 384 5.1.1 Наследуемые и синтезируемые атрибуты 384 5.1.2 Вычисление СУО в узлах дерева разбора 387 5.1.3 Упражнения к разделу 5.1 390 5.2 Порядок вычисления в СУО 391 5.2.1 Графы зависимостей 391 5.2.2 Упорядочение вычисления атрибутов 393 5.2.3 S-атрибутные определения 394 5.2.4 L-атрибутные определения 39412 Содержание 5.2.5 Семантические правила с контролируемыми побочными действиями 396 5.2.6 Упражнения к разделу 5.2 398 5.3 Применения синтаксически управляемой трансляции 399 5.3.1 Построение синтаксических деревьев 400 5.3.2 Структура типа 404 5.3.3 Упражнения к разделу 5.3 406 5.4 Синтаксически управляемые схемы трансляции 406 5.4.1 Постфиксные схемы трансляции 407 5.4.2 Реализация постфиксной СУТ с использованием стека синтаксического анализатора 407 5.4.3 СУТ с действиями внутри продукций 410 5.4.4 Устранение левой рекурсии из СУТ 411 5.4.5 СУТ для L-атрибутных определений 414 5.4.6 Упражнения к разделу 5.4 421 5.5 Реализация L-атрибутных СУО 422 5.5.1 Трансляция в процессе синтаксического анализа методом рекурсивного спуска 423 5.5.2 Генерация кода “на лету” 425 5.5.3 L-атрибутные СУО и LL-синтаксический анализ 428 5.5.4 Восходящий синтаксический анализ L-атрибутных СУО 434 5.5.5 Упражнения к разделу 5.5 439 5.6 Резюме к главе 5 439 5.7 Список литературы к главе 5 441 Глава 6. Генерация промежуточного кода 443 6.1 Варианты синтаксических деревьев 445 6.1.1 Ориентированные ациклические графы для выражений 445 6.1.2 Метод номера значения для построения ориентированных ациклических графов 447 6.1.3 Упражнения к разделу 6.1 450 6.2 Трехадресный код 450 6.2.1 Адреса и команды 450 6.2.2 Четверки 454 6.2.3 Тройки 455 6.2.4 Представление в виде статических единственных присваиваний 457 6.2.5 Упражнения к разделу 6.2 458 6.3 Типы и объявления 459 6.3.1 Выражения типов 459 6.3.2 Эквивалентность типов 461Содержание 13 6.3.3 Объявления 462 6.3.4 Размещение локальных имен в памяти 462 6.3.5 Последовательности объявлений 464 6.3.6 Поля в записях и классах 466 6.3.7 Упражнения к разделу 6.3 467 6.4 Трансляция выражений 468 6.4.1 Операции в выражениях 468 6.4.2 Инкрементная трансляция 470 6.4.3 Адресация элементов массива 471 6.4.4 Трансляция обращений к массиву 473 6.4.5 Упражнения к разделу 6.4 475 6.5 Проверка типов 477 6.5.1 Правила проверки типов 477 6.5.2 Преобразования типов 478 6.5.3 Перегрузка функций и операторов 481 6.5.4 Выведение типа и полиморфные функции 482 6.5.5 Алгоритм унификации 487 6.5.6 Упражнения к разделу 6.5 490 6.6 Поток управления 491 6.6.1 Булевы выражения 492 6.6.2 Код сокращенного вычисления 492 6.6.3 Инструкции потока управления 493 6.6.4 Трансляция логических выражений с помощью потока управления 496 6.6.5 Устранение излишних команд перехода 499 6.6.6 Булевы значения и код с переходами 501 6.6.7 Упражнения к разделу 6.6 502 6.7 Обратные поправки 504 6.7.1 Однопроходная генерация кода с использованием обратных поправок 504 6.7.2 Обратные поправки для булевых выражений 505 6.7.3 Инструкции потока управления 508 6.7.4 Инструкции break, continue и goto 511 6.7.5 Упражнения к разделу 6.7 512 6.8 Инструкции выбора 514 6.8.1 Трансляция инструкций выбора 514 6.8.2 Синтаксически управляемая трансляция инструкций выбора 515 6.8.3 Упражнения к разделу 6.8 517 6.9 Промежуточный код процедур 51714 Содержание 6.10 Резюме к главе 6 520 6.11 Список литературы к главе 6 521 Глава 7. Среды времени выполнения 525 7.1 Организация памяти 525 7.1.1 Статическое и динамическое распределение памяти 527 7.2 Выделение памяти в стеке 528 7.2.1 Деревья активации 529 7.2.2 Записи активации 532 7.2.3 Последовательности вызовов 535 7.2.4 Данные переменной длины в стеке 539 7.2.5 Упражнения к разделу 7.2 540 7.3 Доступ к нелокальным данным в стеке 542 7.3.1 Доступ к данным при отсутствии вложенных процедур 542 7.3.2 Вложенные процедуры 543 7.3.3 Язык с вложенными объявлениями процедур 544 7.3.4 Глубина вложенности 545 7.3.5 Связи доступа 547 7.3.6 Работа со связями доступа 548 7.3.7 Связи доступа для процедур, являющихся параметрами 550 7.3.8 Дисплеи 551 7.3.9 Упражнения к разделу 7.3 554 7.4 Управление кучей 555 7.4.1 Диспетчер памяти 555 7.4.2 Иерархия памяти компьютера 557 7.4.3 Локальность в программах 559 7.4.4 Снижение фрагментации 561 7.4.5 Освобождение памяти вручную 565 7.4.6 Упражнения к разделу 7.4 568 7.5 Введение в сборку мусора 568 7.5.1 Цели проектирования сборщиков мусора 569 7.5.2 Достижимость 572 7.5.3 Сборщики мусора с подсчетом ссылок 574 7.5.4 Упражнения к разделу 7.5 576 7.6 Введение в сборку на основе отслеживания 576 7.6.1 Базовый сборщик мусора 577 7.6.2 Базовая абстракция 580 7.6.3 Оптимизация алгоритма “пометить и подмести” 582 7.6.4 Сборщики мусора “пометить и сжать” 583 7.6.5 Копирующие сборщики 587 7.6.6 Сравнение стоимости 589Содержание 15 7.6.7 Упражнения к разделу 7.6 590 7.7 Распределенная сборка мусора 591 7.7.1 Инкрементная сборка мусора 591 7.7.2 Инкрементный анализ достижимости 593 7.7.3 Основы частичной сборки 596 7.7.4 Сборка мусора по поколениям 597 7.7.5 Алгоритм поезда 599 7.7.6 Упражнения к разделу 7.7 603 7.8 Дополнительные вопросы сборки мусора 604 7.8.1 Параллельная сборка мусора 605 7.8.2 Частичное перемещение объектов 608 7.8.3 Консервативная сборка мусора для небезопасных языков программирования 608 7.8.4 Слабые ссылки 609 7.8.5 Упражнения к разделу 7.8 610 7.9 Резюме к главе 7 611 7.10 Список литературы к главе 7 614 Глава 8. Генерация кода 617 8.1 Вопросы проектирования генератора кода 619 8.1.1 Вход генератора кода 619 8.1.2 Целевая программа 620 8.1.3 Выбор команд 621 8.1.4 Распределение регистров 623 8.1.5 Порядок вычислений 625 8.2 Целевой язык 625 8.2.1 Простая модель целевой машины 625 8.2.2 Стоимость программ и команд 629 8.2.3 Упражнения к разделу 8.2 630 8.3 Адреса в целевом коде 632 8.3.1 Статическое выделение памяти 632 8.3.2 Выделение памяти в стеке 635 8.3.3 Адреса имен времени выполнения 638 8.3.4 Упражнения к разделу 8.3 639 8.4 Базовые блоки и графы потоков 640 8.4.1 Базовые блоки 641 8.4.2 Информация о дальнейшем использовании 643 8.4.3 Графы потоков 644 8.4.4 Представление графов потоков 646 8.4.5 Циклы 646 8.4.6 Упражнения к разделу 8.4 64716 Содержание 8.5 Оптимизация базовых блоков 648 8.5.1 Представление базовых блоков с использованием ориентированных ациклических графов 648 8.5.2 Поиск локальных общих подвыражений 649 8.5.3 Устранение неиспользуемого кода 651 8.5.4 Применение алгебраических тождеств 652 8.5.5 Представление обращений к массивам 653 8.5.6 Присваивание указателей и вызовы процедур 655 8.5.7 Сборка базового блока из ориентированного ациклического графа 656 8.5.8 Упражнения к разделу 8.5 658 8.6 Простой генератор кода 660 8.6.1 Дескрипторы регистров и адресов 661 8.6.2 Алгоритм генерации кода 661 8.6.3 Разработка функции getReg 665 8.6.4 Упражнения к разделу 8.6 667 8.7 Локальная оптимизация 668 8.7.1 Устранение излишних загрузок и сохранений 668 8.7.2 Устранение недостижимого кода 669 8.7.3 Оптимизация потока управления 670 8.7.4 Алгебраические упрощения и снижение стоимости 671 8.7.5 Использование машинных идиом 671 8.7.6 Упражнения к разделу 8.7 671 8.8 Распределение и назначение регистров 672 8.8.1 Глобальное распределение регистров 672 8.8.2 Счетчики использований 673 8.8.3 Назначение регистров для внешних циклов 676 8.8.4 Распределение регистров путем раскраски графа 676 8.8.5 Упражнения к разделу 8.8 677 8.9 Выбор команд путем переписывания дерева 677 8.9.1 Схемы трансляции деревьев 678 8.9.2 Генерация кода путем замощения входного дерева 681 8.9.3 Поиск соответствий с использованием синтаксического анализа 684 8.9.4 Программы семантической проверки 685 8.9.5 Обобщенный поиск соответствий 686 8.9.6 Упражнения к разделу 8.9 688 8.10 Генерация оптимального кода для выражений 688 8.10.1 Числа Ершова 689 8.10.2 Генерация кода на основе помеченных деревьев выражений 690Содержание 17 8.10.3 Вычисление выражений при недостаточном количестве регистров 692 8.10.4 Упражнения к разделу 8.10 694 8.11 Генерация кода с использованием динамического программирования 695 8.11.1 Последовательные вычисления 696 8.11.2 Алгоритм динамического программирования 697 8.11.3 Упражнения к разделу 8.11 700 8.12 Резюме к главе 8 700 8.13 Список литературы к главе 8 702 Глава 9. Машинно-независимые оптимизации 705 9.1 Основные источники оптимизации 706 9.1.1 Причины избыточности 706 9.1.2 Конкретный пример: быстрая сортировка 707 9.1.3 Трансформации, сохраняющие семантику 710 9.1.4 Глобальные общие подвыражения 710 9.1.5 Распространение копий 712 9.1.6 Удаление бесполезного кода 713 9.1.7 Перемещение кода 714 9.1.8 Переменные индукции и снижение стоимости 715 9.1.9 Упражнения к разделу 9.1 718 9.2 Введение в анализ потоков данных 719 9.2.1 Абстракция потока данных 720 9.2.2 Схема анализа потока данных 722 9.2.3 Схемы потоков данных в базовых блоках 723 9.2.4 Достигающие определения 725 9.2.5 Анализ активных переменных 733 9.2.6 Доступные выражения 735 9.2.7 Резюме 740 9.2.8 Упражнения к разделу 9.2 740 9.3 Основы анализа потока данных 743 9.3.1 Полурешетки 744 9.3.2 Передаточные функции 750 9.3.3 Итеративный алгоритм в обобщенной структуре 753 9.3.4 Смысл решения потока данных 755 9.3.5 Упражнения к разделу 9.3 759 9.4 Распространение констант 760 9.4.1 Значения потока данных для структуры распространения констант 761 9.4.2 Сбор в структуре распространения констант 76218 Содержание 9.4.3 Передаточные функции для структуры распространения констант 762 9.4.4 Монотонность структуры распространения констант 763 9.4.5 Недистрибутивность структуры распространения констант 764 9.4.6 Интерпретация результатов 765 9.4.7 Упражнения к разделу 9.4 767 9.5 Устранение частичной избыточности 768 9.5.1 Источники избыточности 769 9.5.2 Все ли избыточные вычисления могут быть устранены? 771 9.5.3 Отложенное перемещение кода 773 9.5.4 Ожидаемость выражений 774 9.5.5 Алгоритм отложенного перемещения кода 775 9.5.6 Упражнения к разделу 9.5 785 9.6 Циклы в графах потоков 787 9.6.1 Доминаторы 787 9.6.2 Упорядочение в глубину 790 9.6.3 Ребра в глубинном остовном дереве 792 9.6.4 Обратные ребра и приводимость 794 9.6.5 Глубина графа потока 795 9.6.6 Естественные циклы 796 9.6.7 Скорость сходимости итеративных алгоритмов потоков данных 798 9.6.8 Упражнения к разделу 9.6 801 9.7 Анализ на основе областей 803 9.7.1 Области 804 9.7.2 Иерархии областей для приводимых графов потоков 805 9.7.3 Обзор анализа на основании областей 808 9.7.4 Необходимые предположения о передаточных функциях 810 9.7.5 Алгоритм анализа на основе областей 811 9.7.6 Обработка неприводимых графов потоков 816 9.7.7 Упражнения к разделу 9.7 818 9.8 Символический анализ 819 9.8.1 Аффинные выражения ссылочных переменных 819 9.8.2 Формулировка задачи потока данных 822 9.8.3 Символический анализ на основе областей 827 9.8.4 Упражнения к разделу 9.8 832 9.9 Резюме к главе 9 833 9.10 Список литературы к главе 9 838Содержание 19 Глава 10. Параллелизм на уровне команд 841 10.1 Архитектуры процессоров 842 10.1.1 Конвейерная обработка команд и задержки ветвления 842 10.1.2 Конвейерное выполнение 843 10.1.3 Многоадресные команды 844 10.2 Ограничения планирования кода 845 10.2.1 Зависимость через данные 846 10.2.2 Поиск зависимостей среди обращений к памяти 846 10.2.3 Компромиссы между использованием регистров и параллелизмом 848 10.2.4 Упорядочение фаз распределения регистров и планирования кода 851 10.2.5 Зависимость от управления 852 10.2.6 Поддержка опережающего выполнения 853 10.2.7 Базовая модель машины 855 10.2.8 Упражнения к разделу 10.2 856 10.3 Планирование базовых блоков 857 10.3.1 Графы зависимости данных 858 10.3.2 Планирование списков базовых блоков 859 10.3.3 Приоритетные топологические порядки 861 10.3.4 Упражнения к разделу 10.3 863 10.4 Глобальное планирование кода 864 10.4.1 Примитивное перемещение кода 865 10.4.2 Восходящее перемещение кода 867 10.4.3 Нисходящее перемещение кода 868 10.4.4 Обновление зависимостей данных 870 10.4.5 Алгоритм глобального планирования 870 10.4.6 Усовершенствованные методы перемещения кода 874 10.4.7 Взаимодействие с динамическими планировщиками 875 10.4.8 Упражнения к разделу 10.4 876 10.5 Программная конвейеризация 876 10.5.1 Введение 877 10.5.2 Программная конвейеризация циклов 879 10.5.3 Распределение регистров и генерация кода 882 10.5.4 Циклы с зависимыми итерациями 883 10.5.5 Цели и ограничения программной конвейеризации 884 10.5.6 Алгоритм программной конвейеризации 888 10.5.7 Планирование ациклических графов зависимости данных 889 10.5.8 Планирование графов с циклическими зависимостями 891 10.5.9 Усовершенствования алгоритма конвейеризации 89920 Содержание 10.5.10 Модульное расширение переменных 900 10.5.11 Условные инструкции 903 10.5.12 Аппаратная поддержка программной конвейеризации 904 10.5.13 Упражнения к разделу 10.5 904 10.6 Резюме к главе 10 907 10.7 Список литературы к главе 10 909 Глава 11. Оптимизация параллелизма и локальности 911 11.1 Фундаментальные концепции 914 11.1.1 Многопроцессорность 914 11.1.2 Параллелизм в приложениях 917 11.1.3 Параллелизм на уровне циклов 918 11.1.4 Локальность данных 920 11.1.5 Введение в теорию аффинных преобразований 922 11.2 Пример посерьезнее: умножение матриц 927 11.2.1 Алгоритм умножения матриц 927 11.2.2 Оптимизации 930 11.2.3 Интерференция кэша 933 11.2.4 Упражнения к разделу 11.2 933 11.3 Пространства итераций 934 11.3.1 Построение пространств итераций вложений циклов 934 11.3.2 Порядок выполнения вложенности циклов 936 11.3.3 Матричная запись неравенств 938 11.3.4 Добавление символьных констант 938 11.3.5 Управление порядком выполнения 939 11.3.6 Изменение осей 944 11.3.7 Упражнения к разделу 11.3 945 11.4 Аффинные индексы массивов 948 11.4.1 Аффинные обращения к данным 948 11.4.2 Аффинное и неаффинное обращения на практике 949 11.4.3 Упражнения к разделу 11.4 950 11.5 Повторное использование данных 951 11.5.1 Типы повторных использований 952 11.5.2 Собственные повторные использования 953 11.5.3 Собственное пространственное повторное использование 958 11.5.4 Групповое повторное использование 959 11.5.5 Упражнения к разделу 11.5 962 11.6 Анализ зависимости данных в массивах 964 11.6.1 Определение зависимостей данных доступов к массивам 965 11.6.2 Целочисленное линейное программирование 966Содержание 21 11.6.3 НОД 967 11.6.4 Эвристики для решения задачи целочисленного линейного программирования 969 11.6.5 Решение обобщенной задачи целочисленного линейного программирования 973 11.6.6 Резюме 975 11.6.7 Упражнения к разделу 11.6 976 11.7 Поиск параллельности, не требующей синхронизации 978 11.7.1 Вводный пример 978 11.7.2 Разбиения аффинного пространства 981 11.7.3 Ограничения разбиений пространства 982 11.7.4 Решение ограничений разбиений пространств 986 11.7.5 Простой алгоритм генерации кода 990 11.7.6 Устранение пустых итераций 993 11.7.7 Устранение проверок из внутреннего цикла 996 11.7.8 Преобразования исходного кода 998 11.7.9 Упражнения к разделу 11.7 1003 11.8 Синхронизация между параллельными циклами 1005 11.8.1 Постоянное количество синхронизаций 1006 11.8.2 Графы зависимостей программ 1007 11.8.3 Иерархическое время 1009 11.8.4 Алгоритм распараллеливания 1012 11.8.5 Упражнения к разделу 11.8 1013 11.9 Конвейеризация 1013 11.9.1 Что такое конвейеризация 1014 11.9.2 Последовательная сверхрелаксация: пример 1016 11.9.3 Полностью переставляемые циклы 1017 11.9.4 Конвейеризация полностью переставляемых циклов 1018 11.9.5 Общая теория 1021 11.9.6 Ограничения временного разбиения 1022 11.9.7 Решение временных ограничений с использованием ´ леммы Фаркаша 1026 11.9.8 Преобразования кода 1029 11.9.9 Параллелизм с минимальной синхронизацией 1035 11.9.10 Упражнения к разделу 11.9 1037 11.10 Оптимизации локальности 1039 11.10.1 Временная локальность вычисляемых данных 1040 ´ 11.10.2 Сжатие массива 1041 11.10.3 Чередование частей 1044 11.10.4 Алгоритмы оптимизации локальности 1047 11.10.5 Упражнения к разделу 11.10 105022 Содержание 11.11 Прочие применения аффинных преобразований 1050 11.11.1 Машины с распределенной памятью 1050 11.11.2 Процессоры с одновременным выполнением нескольких команд 1051 11.11.3 Векторные и SIMD-команды 1052 11.11.4 Предвыборка 1053 11.12 Резюме к главе 11 1054 11.13 Список литературы к главе 11 1057 Глава 12. Межпроцедурный анализ 1061 12.1 Базовые концепции 1062 12.1.1 Графы вызовов 1062 12.1.2 Чувствительность к контексту 1064 12.1.3 Строки вызовов 1067 12.1.4 Контекстно-чувствительный анализ на основе клонирования 1069 12.1.5 Контекстно-чувствительный анализ на основе резюме 1070 12.1.6 Упражнения к разделу 12.1 1073 12.2 Необходимость межпроцедурного анализа 1075 12.2.1 Вызовы виртуальных методов 1076 12.2.2 Анализ псевдонимов указателей 1076 12.2.3 Параллельность 1077 12.2.4 Поиск программных ошибок и уязвимых мест 1077 12.2.5 SQL-ввод 1078 12.2.6 Переполнение буфера 1080 12.3 Логическое представление потока данных 1081 12.3.1 Введение в Datalog 1082 12.3.2 Правила Datalog 1083 12.3.3 Интенсиональные и экстенсиональные предикаты 1085 12.3.4 Выполнение программы Datalog 1088 12.3.5 Инкрементное вычисление программ Datalog 1090 12.3.6 Проблематичные правила Datalog 1091 12.3.7 Упражнения к разделу 12.3 1093 12.4 Простой алгоритм анализа указателей 1095 12.4.1 Сложность анализа указателей 1096 12.4.2 Модель указателей и ссылок 1097 12.4.3 Нечувствительность к потоку 1098 12.4.4 Формулировка с применением Datalog 1099 12.4.5 Использование информации о типе 1101 12.4.6 Упражнения к разделу 12.4 1102 12.5 Контекстно-нечувствительный межпроцедурный анализ 1105Содержание 23 12.5.1 Влияние вызовов методов 1105 12.5.2 Построение графа вызовов в Datalog 1107 12.5.3 Динамическая загрузка и отражение 1108 12.5.4 Упражнения к разделу 12.5 1109 12.6 Контекстно-чувствительный анализ указателей 1109 12.6.1 Контексты и строки вызовов 1110 12.6.2 Добавление контекста в правила Datalog 1113 12.6.3 Дополнительные наблюдения о чувствительности 1114 12.6.4 Упражнения к разделу 12.6 1115 12.7 Реализация Datalog с применением BDD 1115 12.7.1 Диаграммы бинарного выбора 1116 12.7.2 Преобразования диаграмм бинарного выбора 1118 12.7.3 Представление отношений при помощи BDD 1119 12.7.4 Операции отношений и BDD-операции 1120 12.7.5 Использование диаграмм бинарного выбора для анализа целей указателей 1123 12.7.6 Упражнения к разделу 12.7 1124 12.8 Резюме к главе 12 1124 12.9 Список литературы к главе 12 1128 Приложение А. Завершенный пример начальной стадии компилятора 1133 А.1 Исходный язык 1133 А.2 Main 1135 А.3 Лексический анализатор 1135 А.4 Таблицы символов и типы 1139 А.5 Промежуточный код выражений 1140 А.6 Переходы для булевых выражений 1144 А.7 Промежуточный код для инструкций 1149 А.8 Синтаксический анализатор 1153 А.9 Построение начальной стадии 1160 Приложение Б. Поиск линейно независимых решений 1163 Предметный указатель 1167
Название: Компиляторы: принципы, технологии и инструментарий, 2-е издание Автор: Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. Год: 2018 Жанр: программирование, компьютерная, обучение Издательство: Вильямс Язык: Русский
Формат: pdf Качество: eBook Страниц: 1186 Размер: 8 MB
Скачать Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. - Компиляторы: принципы, технологии и инструментарий, 2-е издание (2018)
