Базовый блок

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

Определение [ править ]

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

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

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

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

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

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

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

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

Алгоритм создания [ править ]

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

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

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

[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] Принципы, методы и инструменты компилятора, Ахо Сетхи Уллман.

[1]

[2]

[3]

[4]

[5]

[6]

[7]