Оптимизация компилятора: вынос инвариантного кода из циклов для повышения производительности. Анализ зависимостей данных позволяет оптимизировать даже вложенные циклы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип оптимизации компилятора
Type of compiler optimization
В компьютерном программировании код, инвариантный относительно цикла, состоит из операторов или выражений (в императивном языке программирования), которые можно переместить за пределы тела цикла, не изменяя при этом семантику программы. Перемещение инвариантного кода (также называемое вынесением или продвижением скаляров) — это оптимизация компилятора, которая выполняет это перемещение автоматически.
In computer programming, loop invariant code consists of statements or expressions (in an imperative programming language) that can be moved outside the body of a loop without affecting the semantics of the program. Loop invariant code motion (also called hoisting or scalar promotion) is a compiler optimization that performs this movement automatically.
Обнаружение неизменного кода
Обычно анализ достигающих определений используется для определения, является ли утверждение или выражение инвариантным относительно цикла. Например, если все достигающие определения операндов некоторого простого выражения находятся вне цикла, то это выражение можно вынести за пределы цикла. Недавние исследования с использованием анализа зависимостей потока данных позволяют обнаруживать не только инвариантные команды, но и более крупные фрагменты кода, такие как внутренний цикл. Анализ также выявляет квазиинварианты произвольной степени, то есть команды или фрагменты кода, которые становятся инвариантными после определенного числа итераций тела цикла.
Usually, a reaching definitions analysis is used to detect whether a statement or expression is loop invariant. For example, if all reaching definitions for the operands of some simple expression are outside of the loop, the expression can be moved out of the loop. Recent work using data flow dependence analysis allows to detect not only invariant commands but larger code fragments such as an inner loop. The analysis also detects quasi invariants of arbitrary degrees, that is commands or code fragments that become invariant after a fixed number of iterations of the loop body.
Преимущества
Код, инвариантный относительно цикла, который был вынесен за пределы цикла, выполняется реже, что приводит к увеличению скорости работы. Другим следствием этого преобразования является возможность хранения констант в регистрах и отсутствие необходимости вычислять адрес и обращаться к памяти (или кэш-линии) на каждой итерации. Однако, если создается слишком много переменных, возникает высокая нагрузка на регистры, особенно на процессорах с небольшим количеством регистров, таких как 32-битный x86. Если компилятору не хватает регистров, некоторые переменные будут вытеснены в память. Для противодействия этому может быть выполнена обратная оптимизация – рематериализация.
Loop invariant code which has been hoisted out of a loop is executed less often, providing a speedup. Another effect of this transformation is allowing constants to be stored in registers and not having to calculate the address and access the memory (or cache line) at each iteration. However, if too many variables are created, there will be high register pressure, especially on processors with few registers, like the 32 bit x86. If the compiler runs out of registers, some variables will be spilled. To counteract this, the inverse optimization can be performed, rematerialization.