Методы и алгоритмы оптимизации переходов в компиляторе базового уровня системы двоичной трансляции для архитектуры "Эльбрус"

• Автор: Рыбаков, Алексей Анатольевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 152 с. : ил.

Оглавление
Введение
Глава 1. Системы двоичной трансляции
1.1 Основные определения
1.2 Особенности архитектуры «Эльбрус»
1.3 Система динамической двоичной трансляции Lintel
1.4 Базовый оптимизирующий компилятор
1.5 Обзор систем двоичной трансляции
1.6 Оптимизации переходов
1.6.1 Использование задержек переходов
1.6.2 Оптимизация последовательностей переходов
1.6.3 Предсказание переходов
1.6.4 Удаление лишних переходов путем слияния или расположения узлов
1.6.5 Перемешивание подготовок переходов
1.7 Выводы из главы
Глава 2. Моделирование промежуточного представления оптимизирующего компилятора
2.1 Граф потока управления и статический профиль исполнения
2.2 Создание случайного графа потока управления со статическим
профилем исполнения
2.3 Моделирование графа потока управления с помощью языка
программирования Erlang
2.4 Выводы из главы
Глава 3. Алгоритмы оптимизации переходов
3.1 Оптимизация линеаризации исполнения программы

3.1.1 Постановка задачи
3.1.2 Определение структуры графа провалов
3.1.3 Приближенный алгоритм линеаризации исполнения программы
3.1.4 Оценка эффективности работы приближенного алгоритма
3.2 Локальное распределение подготовок переходов
3.2.1 Оптимальное решение для переходов по неповторяющимся адресам
3.2.2 Использование истории переходов для распределения регистров переходов
3.3 Перенос операций подготовок переходов между узлами
3.3.1 Общее описание оптимизации переноса операций между узлами
3.3.2 Алгоритм оптимизации переноса подготовок переходов между узлами
3.3.3 Определение сложности алгоритма
3.4 Выводы из главы
Глава 4. Применение оптимизаций переходов в базовом компиляторе
4.1 Методика проведения измерений
4.2 Тестовый пакет SPEC CPU2
4.3 Общие характеристики задач пакета SPEC CPU2
4.4 Алгоритм линеаризации исполнения программы
4.5 Использование истории переходов
4.6 Перенос подготовок переходов между узлами
4.7 Суммарный эффект оптимизаций переходов
4.8 Выводы из главы
Заключение

Список сокращений Предметный указатель Список литературы
Динамический транслятор переводит часто исполняемые базовые блоки (hot blocks) в последовательности инструкций IA-64 и сохраняет их в кэше кода для дальнейшего переиспользования. При сохранении оттранслированного кода применяется механизм связывания. Транслятор применяет некоторые оптимизации, такие как ленивое вычисление флагов, свертка констант, пропагация копий, удаление мертвого кода и частичное разрешение конфликтов по доступу в память. Планирование кода осуществляется на основании построенного графа зависимостей между операциями.
1.6 Оптимизации переходов
В данном разделе приведено описание основных оптимизаций переходов, использование которых позволяет повысить производительность результирующего кода. Среди общего описания оптимизаций переходов указаны разработанные в рамках данной работы оптимизации, применяемые в базовом компиляторе.
1.6.1 Использование задержек переходов
В некоторых архитектурах (РА-RISC, SPARC, MIPS) используются так называемые отложенные переходы, у которых между исполнением команды перехода и собственно осуществлением самого перехода выдерживается один или два такта. Данная задержка называется также delay slot. Для повышения эффективности планирования кода в данные такты могут быть помещены полезные инструкции (в противном случае эти такты все равно будут заняты, но уже пустыми инструкциями). Для того чтобы эффективно использовать delay slot перехода, нужно проанализировать граф зависимостей рассматриваемого линейного участка и определить в нем листовые операции, которые могут быть спланированы за отложенным переходом. Также в delay slot в некоторых случаях могут быть спланированы операции из линейного участ-