Средства разработки приложений


Обзор методов оптимизации кода - часть 17


2. Связи типа "запись после записи". Команда cj зависит от ci, если

  • обе команды записывают значения в некоторый регистр r
  • j > i
  • имеется хотя бы одна команда сk, которая читает значение r, записанное командой ci.

Будем обозначать это отношение как ci

cj. Выполнение команды cj должно быть запланировано позже чем ci, если имеет место ci
cj.

3. Связи типа "запись после чтения". Команда cj зависит от ci, если существует команда ck, такая что имеет место ck

ci и ck
cj. Будем обозначать это отношение ci
cj. Смысл этой зависимости в том, что ci читает некоторый регистр r, записанный ранее командой ck, а cj (i) записывает в r другое значение. Если имеет место ci
cj, то cj может быть выполнена не раньше ci (т.е. одновременно или позднее ci).

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

На рис. 11 представлены примеры зависимостей всех типов и показано, как образуются антизависимости.

Зависимости по данным препятствуют параллельному исполнению команд и их переупорядочению при планировании. В случае, показанном на рис. 11а), возможно параллельное выполнение команд (1,2,4) или (3,4). После распределения регистров (рис. 11б), антизависимости жестко определят порядок выполнения команд – 1), 2), 3), 4). Поэтому важно по возможности избавляться от них. Большинство из перечисленных далее преобразований направлено на снятие антизависимостей по данным внутри областей планирования.

Миграция команд. Если результат команды не используется в данной области, то ее можно переместить в области, которые выполняются реже. Для суперблоков этот метод применяется следующим образом [35]. Если результат операции не используется в суперблоке S, то она может быть удалена из S, при этом ее копии создаются во всех суперблоках, на которые управление может быть передано из S.


- Начало -  - Назад -  - Вперед -