Базовий блок

Базовий блок — це прямолінійна послідовність коду, без галужень, з лише однією точкою входу і однією точкою виходу.[1] Ця обмежена форма робить базовий блок дуже піддатливим для аналізу.[2] Зазвичай, компілятори на першому етапі процесу аналізу розкладають програму на її базові блоки. Базові блоки утворюють вершини або вузли в графі потоку керування.

Означення

Код базового блоку має:

• Одну точку входу, тобто жодна частина його коду не може бути пунктом призначенням команди переходу з іншої частини програми.
• Одну точку виходу, тобто лише остання інструкція маже спричинити перехід програми в інший базовий блок. За цих умов, якщо перша інструкція базового блоку виконана, інші інструкції буде обов'язково виконано рівно один раз, в їх порядку.[3]

Кодом може бути початковий код, асемблерний код або інша послідовність інструкцій.

Більш формально, послідовність інструкцій утворює базовий блок якщо:

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

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

Примітки

1. Basic Blocks [Архівовано 20 грудня 2019 у Wayback Machine.] Нутрощі GNU компіляторів
2. "Control Flow Analysis" by Frances E. Allen. Архів оригіналу за 26 травня 2020. Процитовано 4 жовтня 2016.
3. "Global Common Subexpression Elimination" by John Cocke