Базовый блок

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

Содержание

• 1 Определение
• 2 Алгоритм создания
• 3 См. Также
• 4 Ссылки
• 5 Внешние ссылки

Определение

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

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

В этих обстоятельствах, когда выполняется первая команда в базовом блоке, остальные инструкции обязательно выполняются ровно один раз по порядку.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

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

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

Ссылки

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

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