Распространение констант
Распространение констант – оптимизация в компиляторах, уменьшающая избыточные вычисления, путем замены в выражениях переменных их известными значениями.
Для оптимизации выполняется обход графа в ширину для каждой определенной функции. Во время обхода поддерживается стек областей, которые содержат информацию о переменных и их значениях в каждой области кода. Операции, порождающие области: IfOp, ThenOp, ElseOp, ForOp, WhileOp, FunctionOp, ConditionOp. При обходе для каждой порождающей операции мы добавляем в стек новую область, а при выходе из порождающей операции удаляем область из стека. Единицей области является пара следующего вида:
метка для переменной;
результат константной операции.
Далее опишем процесс распространения для порождающих операций:
Распространение безусловных и цикловых конструкций (линейный участок кода)
При анализе кода при встрече StoreOp мы добавляем в текущую область соответствующую метку переменной и значение константной операции. В случае если для StoreOp встречается не константная операция, мы сохраняем метку переменной и инвалидирующий результат (результат показывает, что переменную дальше нельзя распространять). При каждой новой встрече StoreOp обновляем результат в паре.
При встрече LoadOp (запрос значения переменной из памяти) совершаем обход стека областей до первого вхождения переменной. Далее просматриваем хранящийся результат. Если результат константная операция, то заменяем все результаты использования LoadOp на результат константной операции. Если результат неопределённый, то пропускаем подстановку и продолжаем обход графа кода.
До оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
z + 1 # 2
z = y # 3
z + 2 # 4
z = 2 # 5
z + 3 # 6
После оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
1 + 1 # 2
z = y # 3
z + 2 # 4
z = 2 # 5
2 + 3 # 6
В данном примере создается одна область для тела функции. Рассмотрим выполнение оптимизации построчно.
Происходит выделение памяти и определение значения переменной z константой 1. В область заносится метка переменной z и значение константной операции.
Просматривается значение из области, выполняется подстановка 1.
Инвалидируется метка переменной, так как неизвестно значение переменной y.
Вновь просматриваем область, значение метки для переменной z неопределённо пропускаем распространение.
В области обновляется значение переменной z константой 2.
Просматривается значение из области, выполняется подстановка 2.
Описанный процесс является основой алгоритма и будет повторятся для любых линейных участков кода. Случаи условных и циклических конструкций имеют дополнительные правила обновления меток и их обнуления.
Распространение с условными конструкциями.
В языке условные конструкции представлены оператором if c then частью или then-else частью.
Опишем алгоритм сначала для if только с then частью.
При встрече IfOp мы создаем новую область и просматриваем тело then части. При встрече StoreOp мы добавляем метку и значение в текущую область и обнуляем все метки для переменной в вышележащих областях. Таким образом мы можем продолжать распространение констант в локальной области тела оператора, а при выходе из тела IfOp область удалиться и переопределённые переменные перестанут распространяться.
При встрече LoadOp просматриваем области пока не найдем значение переменной. Рассмотрим пример.
До оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
if (y > 1): # 2
z + 1 # 3
z = 2 # 4
z + 1 # 5
z + 3 # 6
После оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
if (y > 1): # 2
1 + 1 # 3
z = 2 # 4
2 + 1 # 5
z + 3 # 6
Аналогично анализу для линейной области создается область при входе в тело функции и добавляется метка для переменной z.
Добавляем новую область с стек.
Выполняется поиск по стеку. В текущей области метки переменной не присутствует, просматривая области дальше найдем метку в области функции и выполним подстановку.
Добавляем метку для переменной z в текущую область и обнуляем метку в области функции.
Выполняем подстановку константы из текущей области. Оканчивается тело IfOp удаляем область из стека.
При просмотре области функции, найдем, что метка для переменно z обнулена, нельзя выполнить распространение констант.
Опишем для if только с then-else частью, в отличие от if только с then частью. Перед началом распространения проанализируем обе ветки и создадим список меток переменных, которые будут обнулены. Далее выполним распространение констант для каждой ветки без обнуления меток в вышележащих областях. После обнулим метки переменных из вышележащих областей согласно созданному списку.
До оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
if (y > 1): # 2
z = 2 # 3
z + 1 # 4
else: # 5
z + 2 # 6
z + 3 # 7
После оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
if (y > 1): # 2
z = 2 # 3
2 + 1 # 4
else: # 5
1 + 2 # 6
z + 3 # 7
Задержка в обнулении переменных необходима, чтобы корректно учесть значения переменных, которые объявлены в вышележащих областях. При таком подходе мы анализируем части кода, как два независимых участка линейного кода.
Распространение с циклами
Для ForOp и WhileOp перед началом распространения проанализируем тело цикла. Обнулим значения переменных, которые изменяют свое значение в теле, в вышележащих областях. После обнуления можно работать с телом цикла, как с линейным участком кода.
До оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
x: int = 2 # 2
while (y > 1): # 3
y = y - 1 # 3
z = z + 1 # 4
x + 2 # 5
x + 3 # 6
После оптимизации:
def foo(y: int) -> None:
z: int = 1 # 1
x: int = 2 # 2
while (y > 1): # 3
y = y - 1 # 3
z = z + 1 # 4
2 + 2 # 5
2 + 3 # 6
Для переменной z перед началом анализа тела цикла, будет обнулена метка из 1 строчки, так как значение переменной буде изменено в строке 4.
Для переменной x изменения значения в цикле не происходит поэтому возможно распространение как внутри цикла, так и после него.