А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 3
Текст из файла (страница 3)
Машинно-независимые оптимизации Основные источники оптимизации 9.1.1 Причины избыточности 9.1.2 Конкретный пример: быстрая сортировка 9.1.3 Трансформации, сохраняющие семантику 9.!.4 Глобальные общие подвыражения 9.! .5 Распространение копий 9.1.6 Удаление бесполезного кода 9.1.7 Перемещение кода 9.1.8 Переменные индукции и снижение стоимости 9.1.9 Упражнения к разделу 9.1 Введение в анализ потоков данных 9.2.! Абстракция потока данных 9.2.2 Схема анализа потока данных 9.2.3 Схемы потоков данных в базовых блоках 9.2.4 Достигающие определения 9.2.5 Анализ активных переменных 9.2.6 Доступные выражения 9.2.7 Резюме 9.2.8 Упражнения к разделу 9.2 Основы анализа потока данных 9.3.1 Полурешетки 9.3.2 Передаточные функции 9.3.3 Итеративный алгоритм в обобщенной структуре 9.3.4 Смысл решения патока данных 9.3.5 Упражнения к разделу 9.3 Распространение констант 9.4.1 Значения потока данных для структуры распространения констант Сбор в структуре распространения констант 705 706 706 707 7!О 710 712 713 7!4 715 718 719 720 722 723 725 733 735 740 740 743 744 750 753 755 759 760 18 Содержание 9.4.3 762 763 764 765 767 768 769 771 773 774 775 785 787 787 790 792 794 795 796 9.5 9.6 798 801 803 804 805 808 810 81! 816 818 819 819 822 827 832 833 838 9.7 9.8 9,9 9.10 Передаточные функции для структуры распространения констант 9.4.4 Монотонность структуры распространения констант 9.4.5 Недистрибутивность структуры распространения констант 9.4.6 Интерпретация результатов 9.4.7 Упражнения к разделу 9.4 Устранение частичной избыточности 9.5.1 Источники избыточности 9.5.2 Все ли избыточные вычисления могут быть устранены? 9.5.3 Отложенное перемещение кода 9.5.4 Ожидаемость выражений 9.5.5 Алгоритм отложенного перемещения кода 9.5.6 Упражнения к разделу 9.5 Циклы в графах потоков 9.6.1 Доминаторы 9.6.2 Упорядочение в глубину 9.6.3 Ребра в глубинном остовном дереве 9.6.4 Обратные ребра и приводимость 9.6.5 Глубина графа потока 9.6.6 Естественные циклы 9.6.7 Скорость сходимости итеративных алгоритмов потоков данных 9.6.8 Упражнения к разделу 9.6 Анализ на основе областей 9.7.1 Области 9,7.2 Иерархии областей для приводимых графов потоков 9.7.3 Обзор анализа на основании областей 9,7.4 Необходимые предположения о передаточных функциях 9.7.5 Алгоритм анализа на основе областей 9.7.6 Обработка неприводимых графов потоков 9.7.7 Упражнения к разделу 9.7 Символический анализ 9.8.1 Аффинные выражения ссылочных переменных 9.8.2 Формулировка задачи потока данных 9.8.3 Символический анализ на основе областей 9.8.4 Упражнения к разделу 9.8 Резюме к главе 9 Список литературы к главе 9 Содержание 19 О.
Параллелизм на уровне команд Глава 1 10. 1 10.2 10.3 10.4 10.5 Архитектуры процессоров 1О !.1 Конвейерная обработка команд и задержки ветвления 10.1.2 Конвейерное выполнение !О.!.3 Многоадресные команды Ограничения планирования кода 10.2.1 Зависимость через данные 10.2.2 Поиск зависимостей среди обращений к памяти 10.2.3 Компромиссы между использованием регистров и параллелизмом 10.2.4 Упорядочение фаз распределения регистров и планирования кода 10.2.5 Зависимость от управления 10.2.6 Поддержка опережающего выполнения 10.2.7 Базовая модель машины 10.2.8 Упражнения к разделу 10.2 Планирование базовых блоюв 10.3.! Графы зависимости данных 10.3.2 Планирование списков базовых блоков 10.3.3 Приоритетные топологические порядки 10.3.4 Упражнения к разделу 10.3 Глобальное планирование кода 10.4.! Примитивное перемещение кода 10.4.2 Восходяшее перемещение кода 10.4.3 Нисходящее перемещение кода 10.4.4 Обновление зависимостей данных 10.4.5 Алгоритм глобального планирования 10.4.6 Усовершенствованные методы перемещения кода 10.4.7 Взаимодействие с динамическими планировщиками 10.4.8 Упражнения к разделу 10.4 Программная юнвейеризация ! 0.5,1 Введение ! 0.5.2 Программная юнвейеризация циклов 10.5.3 Распределение регистров и генерация кода 10.5.4 Циклы с зависимыми итерациями 10.5.5 Цели и ограничения программной конвейеризации 10.5.6 Алгоритм программной юнвейеризации 10.5.7 Планирование ациклических графов зависимости данных 10.5.8 Планирование графов с циклическими зависимостями 10.5.9 Усовершенствования алгоритма конвейеризации 841 842 842 843 844 845 846 846 848 851 852 853 855 856 857 858 859 861 863 864 865 867 868 870 870 874 875 876 876 877 879 882 883 884 888 889 89! 899 Содержание 900 903 904 904 907 909 10.6 10.7 Глава 1 11.1 11.2 ! !.3 ! 1.4 1 1.5 958 959 962 964 965 966 ! 1.6 10.5.10 Модульное расширение переменных ! 0.5.1! Условные инструкции 10.5.12 Аппаратная поддержка программной конвейеризации ! 0.5.13 Упражнения к разделу 10.5 Резюме к главе !0 Список литературы к главе 10 1.
Оптимизация параллелизма и локальности Фундаментальные концепции 11.1.! Многопроцессорность 11.1.2 Параллелизм в приложениях ! 1.1.3 Параллелизм на уровне циклов 1!.1.4 Локальность данных !!.1.5 Введение в теорию аффинных преобразований Пример посерьезнее: умножение матриц 11.2.1 Алгоритм умножения матриц 11.2.2 Оптимизации 11.2.3 Интерференция кэша 11.2.4 Упражнения к разделу 11.2 Пространства итераций 11.3.! Построение пространств итераций вложений циклов 1!.3.2 Порядок выполнения вложенности циклов 1!.3.3 Матричная запись неравенств 11.3.4 Добавление символьных констант 113.5 Управление порядком выполнения 11.3.6 Изменение осей 11.3.7 Упражнения к разделу 11.3 Аффннные индексы массивов 11.4.1 Аффинные обращения к данным 11.4.2 Аффинное и неаффинное обращения на практике 1!.4.3 Упражнения к разделу 11.4 Повторное использование данных !! .5.
! Типы повторных использований ! !.5.2 Собственные повторные использования 1 !.5.3 Собственное пространственное повторное использование 11.5.4 Групповое повторное использование 11.5.5 Упражнения к разделу 11.5 Анализ зависимости данных в массивах 11.6.1 Определение зависимостей данных доступов к массивам 11.6.2 Целочисленное линейное программирование 911 914 914 917 918 920 922 927 927 930 933 933 934 934 936 938 938 939 944 945 948 948 949 950 95! 952 953 Содержание 11,7 11.8 ! 1.9 ! 1.10 Оптимизации локальности 1!.10.1 Временная локальность вычисляемых данных 11.10.2 Сжатие массива 11.10.3 Чередование частей 11.! 0.4 Алгоритмы оптимизации локальности 11.10.5 Упражнения к разделу 11.!О 11.6.3 ИОД 11.6.4 Эвристики для решения задачи целочисленного линейного программирования 11.6.5 Решение обобщенной задачи целочисленного линейного программирования ! 1.6.6 Резюме 11.6.7 Упражнения к разделу 11.6 Поиск параллельности, не требующей синхронизации 11.7.! Вводный пример 11.7.2 Разбиения аффинного пространства !1.7.3 Ограничения разбиений пространства 1!.7.4 Решение ограничений разбиений пространств 1!.7.5 Простой алгоритм генерации кода 11.7.6 Устранение пустых итераций 11.7.7 Устранение проверок из внутреннего цикла !1.7.8 Преобразования исходного кода 11.7.9 Упражнения к разделу 1!.7 Синхронизация между параллельными циклами 11.8.1 Постоянное количество синхронизаций 11.8.2 Графы зависимостей программ !1.8.3 Иерархическое время !1.8.4 Алгоритм распараллеливания 11.8.5 Упражнения к разделу 11.8 Конвейеризация 11.9.! Что такое конвейеризация 11.9.2 Последовательная сверхрелаксация: пример 11.9.3 Полностью переставляемые циклы 11.9.4 Конвейеризация полностью переставляемых циклов 11.9.5 Общая теория 11.9.6 Ограничения временного разбиения 11.9.7 Решение временных ограничений с использованием леммы Фаркаша 11.9.8 Преобразования кода 11.9.9 Параллелизм с минимальной синхронизацией 11.9.10 Упражнения к разделу 11.9 967 969 973 975 976 978 978 981 982 986 990 993 996 998 1003 1005 1006 1007 1009 10!2 1013 1013 1014 1016 1017 1018 1021 1022 1026 1029 !035 1037 !039 1040 1041 1044 1047 1050 22 Содержание 1050 1050 1051 1052 1053 1054 1057 Глава 1 12.1 1061 1062 1062 !064 !067 12.2 12.3 12.4 12.5 11.11 Прочие применения аффинных преобразований 11.11.1 Машины с распределенной памятью 11.!!.2 Процессоры с одновременным выполнением нескольких команд 11.11.3 Векторные и 81МП-команды 1! .11.4 Предвыборка 11.12 Резюме к главе !! 1!.13 Список литературы к главе 11 2.
Межпроцедурный анализ Базовые концепции 12.1.1 Графы вызовов 12.1.2 Чувствительность к контексту 12.1.3 Строки вызовов ! 2.1.4 Контекстно-чувствительный анализ на основе клонирования 12.1.5 Контекстно-чувствительный анализ на основе резюме 12.1.6 Упражнения к разделу 12.1 Необходимость межпроцедурного анализа 12.2.1 Вызовы виртуальных методов 12.2.2 Анализ псевдонимов указателей 12.2,3 Параллельность 12.2.4 Поиск программных ошибок и уязвимых мест 12.2.5 81 1Ь-ввод 12.2.6 Переполнение буфера Логическое представление потока данных !2.3.1 Введение в !За!а!ой 12.3.2 Правила 13а1а!ой 12.3.3 Интенсиональные и зкстенсиональные предикаты 12.3.4 Выполнение программы Па!а!ой 12.3.5 Инкрементное вычисление программ Па1а1о8 12.3.6 Проблематичные правила Па!а!о8 12.3.7 Упражнения к разделу 12.3 Простой алгоритм анализа указателей 12.4.1 Сложность анализа указателей 12.4.2 Модель указателей и ссылок !2.4.3 Нечувствительность к потоку 12.4.4 Формулировка с применением Па!а!ой 12.4.5 Использование информации о типе 12.4.6 Упражнения к разделу 12.4 Контекстно-нечувствительный межпроцедурный анализ 1069 1070 1073 !075 !076 1076 1077 1077 !078 !080 108! 1082 1083 1085 1088 1090 1091 1093 1095 1096 !097 1098 1099 1!01 1!02 1105 23 Содержание 1123 1124 1124 1128 Приложение А.
Завершенный пример начальной стадии компилятора А.1 А.2 А.З А.4 А.5 А.б А.7 А.8 А.9 Приложение Б. Поиск линейно независимых решений 1163 Предметный указатель 1167 12.6 12. 7 12.8 ! 2.9 12.5.1 Влияние вызовов методов 12.5.2 Построение графа вызовов в !3а!а!ой 12.5.3 Динамическая загрузка и отражение 12.5.4 Упражнения к разделу 12.5 Контекстно-чувствительный анализ указателей !2.6.1 Контексты и строки вызовов 12.6.2 Добавление контекста в правила Па!а!ой 12.6,3 Дополнительные наблюдения о чувствительности 12.6.4 Упражнения к разделу 12.6 Реализация Па!а!ой с применением В!3!3 12.7.1 Диаграммы бинарного выбора 12.7.2 Преобразования диаграмм бинарного выбора 12.7.3 Представление отношений при помощи В!3!3 12.7.4 Операции отношений и В1Ю-операции 12.7.5 Использование диаграмм бинарного выбора для анализа целей указателей 12.7.6 Упражнения к разделу 12.7 Резюме к главе 12 Список литературы к главе !2 Исходный язык Ма1п Лексический анализатор Таблицы символов и типы Промежуточный код выражений Переходы для булевых выражений Промежуточный код для инструкций Синтаксический анализатор Построение начальной стадии 1105 1107 1108 1109 !109 1110 1113 1!14 1115 1115 1116 1118 1119 1120 1133 1133 1135 1135 1139 1140 1144 1149 1153 1160 Предисловие Со времени написания первого издания книги в 1986 году в мире разработки компиляторов произошли значительные изменения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
