Базовый блок - Basic block

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

Определение

В коде базового блока есть:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка