В строительстве компилятора , А базовый блок представляет собой последовательность прямой линии код без каких - либо ветвей в , кроме как для входа и не разветвляется , кроме на выходе. [1] [2] Эта ограниченная форма делает базовый блок легко поддающимся анализу. [3] Компиляторы обычно разбивают программы на их базовые блоки в качестве первого шага в процессе анализа. Базовые блоки образуют вершины или узлы в графе потока управления .
Определение
В коде базового блока есть:
- Одна точка входа , то есть отсутствие кода внутри нее, является назначением инструкции перехода в любом месте программы.
- Одна точка выхода, означающая, что только последняя инструкция может заставить программу начать выполнение кода в другом базовом блоке.
В этих обстоятельствах всякий раз, когда выполняется первая инструкция в базовом блоке, остальные инструкции обязательно выполняются ровно один раз по порядку. [4] [5]
Код может быть исходным кодом , кодом сборки или какой-либо другой последовательностью инструкций.
Более формально последовательность инструкций образует базовый блок, если:
- Инструкция в каждой позиции преобладает над всеми инструкциями в последующих позициях или всегда выполняет их раньше.
- Никакая другая инструкция не выполняется между двумя инструкциями в последовательности.
Это определение в некотором смысле более общее, чем интуитивное. Например, он позволяет безусловные переходы к меткам, не предназначенным для других переходов. Это определение воплощает свойства, которые упрощают работу с базовыми блоками при построении алгоритма.
Блоки, которым может передаваться управление после достижения конца блока, называются преемниками этого блока , в то время как блоки, из которых могло поступить управление при входе в блок, называются предшественниками этого блока . На начало базового блока можно перейти из более чем одного места.
Алгоритм создания
Алгоритм для генерации базовых блоков из листинга коды прост: анализатор сканирует над кодом, маркировка границ блоков , которые являются инструкциями , которые могут либо начать или закончить блок , потому что они либо контроль передачи или принимать управление с другой точки. Затем листинг просто «разрезается» в каждой из этих точек, и основные блоки остаются.
Обратите внимание, что этот метод не всегда генерирует максимальные базовые блоки по формальному определению, но их обычно достаточно (максимальные базовые блоки - это базовые блоки, которые не могут быть расширены путем включения соседних блоков без нарушения определения базового блока [6] ).
Вход : последовательность инструкций (чаще всего трехадресный код ). [7]
Вывод : список базовых блоков, каждый трехадресный оператор содержится ровно в одном блоке.
- Определите лидеров в коде. Лидеры - это инструкции, которые подпадают под одну из следующих 3 категорий:
- Это первая инструкция. Первая инструкция - лидер.
- Целью условной или безусловной инструкции перехода / перехода является лидер.
- Инструкция, которая следует сразу за условной или безусловной инструкцией перехода / перехода, является лидером.
- Начиная с лидера, набор всех следующих инструкций до следующего лидера, не включая его, является базовым блоком, соответствующим стартовому лидеру. Таким образом, у каждого базового блока есть лидер.
Инструкции, завершающие базовый блок, включают следующее:
- безусловные и условные ветви , прямые и косвенные
- возвращается к вызывающей процедуре
- инструкции, которые могут вызвать исключение
- вызовы функций могут быть в конце базового блока , если они не могут вернуться, такие как функции , которые бросают исключение или специальные вызовы , такие как C «s
longjmp
иexit
- сама инструкция возврата.
Инструкции, с которых начинается новый базовый блок, включают следующее:
- точки входа в процедуры и функции
- мишени прыжков или веток
- "сквозные" инструкции после некоторых условных переходов
- инструкции, следующие за теми, которые вызывают исключения
- обработчики исключений.
Обратите внимание: поскольку управление никогда не может пройти через конец базового блока, некоторые границы блоков, возможно, придется изменить после нахождения базовых блоков. В частности, проходящие условные переходы должны быть заменены на двусторонние, а вызовы функций, генерирующие исключения, должны иметь безусловные переходы, добавленные после них. Для этого может потребоваться добавление меток в начало других блоков.
Смотрите также
Рекомендации
- ^ Хеннесси, Джон Л. и Дэвид А. Паттерсон. Компьютерная архитектура: количественный подход. Эльзевир, 2011.
- ↑ Daniel), Cooper, Keith D. (Keith (2012). Engineering a compiler . Torczon, Linda. (2nd ed.). Amsterdam : Elsevier / Morgan Kaufmann. P. 231. ISBN). 978-0120884780. OCLC 714113472 .
- ^ "Анализ потока управления" Фрэнсис Э. Аллен
- ^ Юсефи, Джавад (2015). Маскирование ошибок потока управления неправильного преемника с использованием избыточности данных . IEEE. С. 201–205. DOI : 10.1109 / ICCKE.2015.7365827 .
- ^ «Устранение глобального общего подвыражения» Джона Кока
- ^ Современный дизайн компилятора Дика Грюна, Анри Э. Бала, Сериэль Дж. Х. Джейкобс и Коэн Г. Лангендоен, стр. 320
- ^ Принципы, методы и инструменты компилятора, Ахо Сетхи Ульман
Внешние ссылки
- Базовые блоки - Сборник компиляторов GNU
- Расширенный базовый блок - Викисловарь