Оптимальні програми обчислення виразів, Детальна інформація

а = (3 + 1) * ( 3 - 5) + с / 3;

Розмноження констант може навіть зменшити кількість необхідних присвоювань. Також воно тісно пов’язане з методом "згортки констант" (константною арифметикою), що зводить вирази з константами до якомога простішої форми. Сталі величини використовуються в програмі або безпосередньо (як у випадку чисел та цифр), або опосередковано (як у випадку декларування констант).

Згортка констант зводить наступний фрагмент програми на мові C

#define TWO 2

a = 1 + TWO;

до його еквівалентної форми

а = 3;

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

"Алгебраїчні спрощення" - це різновид згортки констант, який видаляє арифметичні тотожності. Код, що генерується для таких операторів як

х = у + 0;

х = у * 0;

х = у / 1.0;

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

"Логічні спрощення" - аналог попереднього методу оптимізації, що стосується логічних виразів. Оператори

x = y AND False;

x = y AND True;

x = y OR True;

x = y OR False;

та їх неявні модифікації можуть бути спрощені для уникнення зайвих обчислень. Можливі випадки навіть повного припинення обчислення логічного виразу, якщо в процесі роботи було виявлено незалежність результату від значень підвиразів.

"Видалення спільних підвиразів" - це процес зменшення кількості зайвих обчислень. Замість того, щоб генерувати код для обчислення значення кожен раз, коли воно використовується, оптимізуючий компілятор може спробувати виділити вираз таким чином, щоб його значення обчислювалося тільки один раз. Там, де це можливо, наступні появи цього ж виразу використовують раніше обчислене значення. Наприклад у*3 є спільним підвиразом у наступному тексті:

if( a[y*3] < 0 || b[y*3] > 10)

a[y*3] = 0;

Виділення його приводить до логічно еквівалентного тексту, що містить менше обчислень:

Т1 = у*3;

if( a[Т1] < 0 || b[Т1] > 10)

a[Т1] = 0;

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

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

"Видалення зайвих присвоювань" включає знаходження проміжку існування змінної і знищення присвоювань значень цієї змінної, якщо ці присвоювання не можуть змінити логіку програми. Цей метод звільняє обмежені ресурси, такі як стековий простір або машинні регістри (чому важливо мати багато вільних регістрів буде описано далі). В наступній послідовності команд:

а = х + у*3 - с;