Перемещение операций в условные блоки

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

Оптимизация разбивается на две части:

  1. Построение множества регионов.

  2. Поиск нужного региона для каждой операции и ее перемещение.

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

Процесс построения множества регионов.

Совершаем рекурсивный обход графа в глубину и для каждой операции, имеющей тело(потомков), создаем новый регион и заполняем его множество потомками и присваиваем текущему региону текущие значение метки. При встрече другой операции, содержащей потомков, увеличиваем значение метки и запускам обход уже для нее.

После полного обхода графа получим множество регионов. Например, для кода (зеленым цветом отмечены операторы для удобства ссылок на них):

def foo(x: int, y: float) -> None:
    z: int = 0          # 0
    с: int = 1          # 1
    a: int = x + y      # 2
    b: float = x - y    # 3
    
    if (
        x > 1           # 4
    ):                  # 5
        z = x + a + с   # 6
    else:               # 7
        z = y + b + с   # 8
    
    while (
        z > 0           # 9
    ):                  # 10
        z = z - 1       # 11

Будет построено следующее множество регионов.

Метка региона

Порождающая операция

Потомки

0

FunctionOp

0, 1, 2, 3, 5, 10

1

IfOp

CondOp, ThenOp, ElseOp

2

CondOp

4

3

ThenOp

6

4

ElseOp

8

5

WhileOp

CondOp, BodyOp

6

CondOp (для WhileOp)

9

7

BodyOp

11

Поиск нужного региона для операции и ее перемещение.

Далее снова выполняется обход графа, но с анализом уже всех операций:

  1. Для каждой операции анализируются операции, в которых она использована и строится множество операций, порождающих регионы, в которые потенциально может быть перемещена операция. Для этого:

    1. Анализируется массив пользователей результата операции. Если метка текущей операции меньше, чем метка региона в которой используется операция, то добавляем в множество операций соответствующий порождающий регион. В противном случае прекращаем анализ. Второй случай означает, что операция используется в регионе, которому принадлежит.

    2. Далее необходимо проверить множества потенциальных регионов на сестринские/братские связи. Если операция принадлежит двум братьям или сестрам, то завершаем анализ. В данном случае копирование операции не приведет не к чему, кроме, как увеличению количества операций и не упрощает анализ для других операций.

    3. Из оставшегося множества находим минимальный регион, в который может быть перемещена операция и проверяем, что этот регион порожден условной конструкцией. Если такой регион существует, то перемещаем операцию в его начало и обновляем множество регионов.

  2. При общем обходе графа операций мы учитываем потомков в обратном порядке, это позволяет перемещать целые связанные блоки кода друг за другом.

Рассмотрим работу второй части оптимизации на операциях 0, 1, 2, 3.

  1. Нулевая операция используется в операциях 9, 11, что соответствует регионам 6 и 7. Так как 6 и 7 регионы порождаются цикловой конструкцией перемещения не происходит (нарушается пункт с).

  2. Первая операция используется в операциях 6 и 8, что соответствует регионам 3 и 4. Перемещения не происходит, так как регионы 3 и 4 имеют братские связи (нарушается пункт b).

  3. Вторая операция используется в операции 6, что соответствует региону 3. Произойдет перемещение.

  4. Третья операция используется в операции 8, что соответствует региону 4. Произойдет перемещение.

После применения алгоритма код будет выглядеть следующим образом:

def foo(x: int, y: float) -> None:
    z: int = 0          # 0
    с: int = 1          # 1
    
    if (
        x > 1           # 4
    ):                  # 5
        a: int = x + y  # 2
        z = x + a + с   # 6
    else:               # 7
        b: float = x - y# 3
        z = y + b + с   # 8
    
    while (
        z > 0           # 9
    ):                  # 10
        z = z - 1       # 11

Приведем небольшой пример для пункта для поиска нужного региона.

def bar(x: int, y: float) -> None:
    z: int = 0          # 0
    a: int = x + y      # 1
    b: float = a * y    # 2
    
    if (
        x > 1           # 3
    ):                  # 4
        z = x + a + b   # 5

Из-за анализа потомков операции с конца сначала мы переместим операцию 2 в тело if и обновим множество регионов. После этого станет возможным переместить уже операцию 1 в тело if. Изначально мы этого сделать не могли так как операция 1 используется в операции 2 (нарушается пункт a). После оптимизации код имеет вид:

def bar(x: int, y: float) -> None:
    z: int = 0          # 0
    
    if (
        x > 1           # 3
    ):                  # 4
        a: int = x + y  # 1
        b: float = a * y# 2
        z = x + a + b   # 5

Назад