Примеры применения оптимизаций
В качестве обобщения приведем несколько примеров работы совокупности описанных оптимизаций. Пусть модуль для оптимизации имеет следующий упорядоченный список оптимизаций:
удаление неиспользуемых операций;
удаление неиспользуемых функций;
перемещение операций в условные блоки;
объединение одинаковых условных конструкций;
cвёртка констант и приведение типов;
минимизация булевых выражений;
распространение констант.
Мы будем придерживаться следующей стратегии для оптимизации дерева:
Совершается проход по всем операциям в дереве и, если тип операции соответствует типу, для которого определена оптимизация из списка, то запускается соответствующая трансформация.
После прохода по всем операциям возможны три случая.
Была вызвана хотя бы одна оптимизация. Тогда перезапускаем процесс с первого шага вновь.
Не было вызвано оптимизаций. Процесс завершается.
Достигнут выставленный лимит проходов. Завершаем процесс.
Рассмотрим примеры.
Оптимизации: 1, 3, 5, 7
До оптимизации:
def main(x: int) -> int:
z: int = 1 + 2 + 3 # 0
c: int = 2 # 1
y: float = 0 # 2
if (x > 1): # 3
b: int = z * c # 4
return b # 5
else:
a: int = z + z # 6
return a # 7
После оптимизации:
def main(x: int) -> int:
z: int = 1 + 5 # 0
if (x > 1): # 3
c: int = 2 # 1
b: int = z * 2 # 4
return b # 5
else:
a: int = z + z # 6
return a # 7
Оптимизации: 1, 5, 7
До оптимизации:
def main(x: int) -> int:
z: int = 1 + 5 # 0
if (x > 1): # 3
c: int = 2 # 1
b: int = z * 2 # 4
return b # 5
else:
a: int = z + z # 6
return a # 7
После оптимизации:
def main(x: int) -> int:
z: int = 6 # 0
if (x > 1): # 3
b: int = 6 * 2 # 4
return b # 5
else:
a: int = 6 + 6 # 6
return a # 7
Оптимизации: 1, 5, 7
До оптимизации:
def main(x: int) -> int:
z: int = 6 # 0
if (x > 1): # 3
b: int = 6 * 2 # 4
return b # 5
else:
a: int = 6 + 6 # 6
return a # 7
После оптимизации:
def main(x: int) -> int:
if (x > 1): # 3
return 12 # 5
else:
return 12 # 7
Оптимизации: 4
До оптимизации:
def main(x: int) -> int:
if (x > 1): # 3
return 12 # 5
else:
return 12 # 7
После оптимизации:
def main(x: int) -> int:
return 12 # 5
Как итог мы получили функцию, возвращающую число 12. К подобному результату можно прийти, выполняя оптимизации в другом порядке.
В текущей реализации оптимизирующего анализатора не присутствуют следующие трансформации общего назначения:
выделение общих подвыражений;
канонизация выражений (преобразования арифметических операций и установления порядка для коммутативных операций);
подстановка функций;
глобальное распространение констант;
перечисление значений (Value Numbering).
Также для текущего дерева операции не представлена операция, агрегирующая результаты веток условных и цикловых операций (Φ-node или Φ-операция). В силу такой особенности, например, для распространения констант достаточно тяжело рассматривать области после условных и цикловых конструкций. При их наличии можно бы было производить более качественный анализ.
Отметим, что некоторые оптимизации при каждом запуске инициализируют структуры данных, например, перемещение операций в условные блоки каждый раз инициализирует структуру для регионов кода. Данную структуру, возможно, вынести в отдельную глобальную структуру и обновлять ее при изменении по аналогии с деревом операций (например, в MLIR доступ к схожей структуре возможен для каждой операции для любой оптимизации). Она могла быть использована при выделении общих подвыражений или канонизации выражений. При реализации трансформаций мы придерживались, того, что мы не передаем внутреннее состояние структур между запусками оптимизаций, то есть единственным входным значением оставалось дерево операций.