Базовый блок

Кодовая последовательность без ветвей, кроме входа и выхода

В конструкции компилятора базовый блок представляет собой прямую кодовую последовательность без каких-либо ветвей, кроме входа, и никаких ветвей, кроме выхода. ^{[1] [2]} Эта ограниченная форма делает базовый блок легко поддающимся анализу. ^[3] Компиляторы обычно разлагают программы на базовые блоки в качестве первого шага процесса анализа. Базовые блоки образуют вершины или узлы графа потока управления .

Определение

Код в базовом блоке имеет:

• Одна точка входа , что означает, что ни один код внутри нее не является пунктом назначения инструкции перехода в любом месте программы.
• Одна точка выхода. Это означает, что только последняя инструкция может заставить программу начать выполнение кода в другом базовом блоке.

В этих обстоятельствах всякий раз, когда выполняется первая инструкция в базовом блоке, остальные инструкции обязательно выполняются ровно один раз и по порядку. ^{[4] [5]}

Код может быть исходным кодом , ассемблерным кодом или какой-либо другой последовательностью инструкций.

Более формально, последовательность инструкций образует базовый блок, если:

• Инструкция в каждой позиции доминирует (всегда выполняется раньше) над всеми командами, находящимися в последующих позициях.
• Никакая другая инструкция не выполняется между двумя инструкциями в последовательности.

Это определение в некотором смысле является более общим, чем интуитивное. Например, он позволяет безусловные переходы к меткам, не предназначенным для других переходов. Это определение воплощает в себе свойства, которые упрощают работу с базовыми блоками при построении алгоритма.

Блоки, которым может передаваться управление после достижения конца блока, называются преемниками этого блока , а блоки, из которых управление могло поступить при входе в блок, называются предшественниками этого блока . К началу базового блока можно перейти из более чем одного места.

Алгоритм создания

Алгоритм генерации базовых блоков из листинга кода прост: анализатор сканирует код, отмечая границы блоков — инструкции, которые могут либо начинать, либо заканчивать блок, поскольку они либо передают управление, либо принимают управление из другой точки . Затем листинг просто «обрезается» в каждой из этих точек, а базовые блоки остаются.

Обратите внимание, что этот метод не всегда генерирует максимальные базовые блоки по формальному определению, но их обычно достаточно (максимальные базовые блоки — это базовые блоки, которые нельзя расширить за счет включения соседних блоков без нарушения определения базового блока ^[6] ).

Ввод : последовательность инструкций (в основном трехадресный код ). ^[7]
Выходные данные : список базовых блоков, в котором каждая трехадресная инструкция находится ровно в одном блоке.

1. Определите лидеров в коде. Лидеры — это инструкции, которые относятся к любой из следующих трех категорий:
   1. Это первая инструкция. Первая инструкция – лидер.
   2. Целью условной или безусловной инструкции перехода/перехода является лидер.
   3. Команда, которая следует сразу за условной или безусловной командой перехода/перехода, является ведущей.
2. Начиная с лидера, набор всех последующих инструкций до следующего лидера, не включая его, является базовым блоком, соответствующим стартовому лидеру. Таким образом, у каждого базового блока есть лидер.

Инструкции, завершающие базовый блок, включают следующее:

• безусловные и условные ветвления , как прямые, так и косвенные;
• возвращается к вызывающей процедуре;
• инструкции, которые могут вызвать исключение ;
• вызовы функций могут находиться в конце базового блока, если они не могут вернуться, например, функции, которые генерируют исключения, или специальные вызовы, такие как C и .longjmpexit

Инструкции, с которых начинается новый базовый блок, включают следующее:

• точки входа в процедуры и функции;
• мишени прыжков или ветвей;
• «проходные» инструкции, следующие за некоторыми условными ветвями;
• инструкции, следующие за теми, которые вызывают исключения;
• обработчики исключений.

Обратите внимание: поскольку управление никогда не может пройти через конец базового блока, некоторые инструкции, возможно, придется изменить, чтобы найти базовые блоки. В частности, сквозные условные ветки должны быть заменены двусторонними ветвями, а после вызовов функций, вызывающих исключения, должны быть добавлены безусловные переходы. Для этого может потребоваться добавление меток в начало других блоков.

Смотрите также

• Портал компьютерного программирования

• Блок (программирование)
• Граф потока управления
• Путь от решения к решению
• Расширенный базовый блок
• Линейная кодовая последовательность и переход

Рекомендации

1. Хеннесси, Джон Л.; Дэвид А. Паттерсон. Компьютерная архитектура: количественный подход . Эльзевир, 2011.
2. Купер, Кейт Дэниел; Торчон, Линда (2012). Разработка компилятора (2-е изд.). Амстердам : Эльзевир/Морган Кауфманн. п. 231. ИСБН 978-0120884780. OCLC  714113472.
3. «Анализ потока управления» Фрэнсис Э. Аллен.
4. Юсефи, Джавад (2015). «Маскирование ошибок потока управления неправильного преемника с использованием избыточности данных». 2015 5-я Международная конференция по компьютерным технологиям и инженерии знаний (ICCKE) . IEEE. стр. 201–205. дои : 10.1109/ICCKE.2015.7365827. ISBN 978-1-4673-9280-8.
5. «Глобальное устранение общих подвыражений» Джона Кока.
6. Современный дизайн компилятора Дика Грюна, Анри Э. Бала, Сериэль Дж. Джейкобс и Коэна Г. Лангендоена, стр. 320.
7. Принципы, методы и инструменты компилятора, Ахо Сетхи Уллман.

Внешние ссылки

• Базовые блоки — Коллекция компиляторов GNU
• Расширенный базовый блок — Викисловарь