Разлив символа не улучшает окрашивание - PullRequest
Новая
       81

Разлив символа не улучшает окрашивание

3 голосов
/ 04 марта 2020

Скажем, у меня есть это промежуточное представление некоторого кода: 

t1 = 1
t2 = 2
t3 = 3

t4 = t1 + t2
t5 = t3 + t4

use t5

Конечная цель состоит в том, чтобы назначить регистр, используя только два регистра ARM, r0 и r1, и, возможно, пролить некоторые символы.

Первым шагом является вычисление текущих диапазонов для каждой команды: 

t1 = 1       |
t2 = 2       | t1
t3 = 3       | t1, t2

t4 = t1 + t2 | t1, t2, t3 (this is going to become a problem)
t5 = t3 + t4 | t3, t4

use t5       | t5

Регистрация графа помех 

              t2
            /    \     
           /      \    
          /        \   
        t1----------t3
                    | 
                    | 
        t5          t4

Регистрация назначения с помощью раскраски графа

Теперь используйте алгоритм Чейтина, чтобы раскрасить его с помощью двух регистров:

  1. Найти узел с менее чем 2 ребрами
    1. Найдено => t5
    2. Удалите его из графика
    3. Pu sh поместите в стек: [t5]
  2. Найдите узел с менее чем 2 ребрами
    1. Найдено => t4
    2. Удалить его из графика, pu sh: [t5, t4]
  3. Нет узлов с менее чем 2 ребрами! (мы смотрим на t1 - t2 - t3 треугольник)
    1. Выберите один случайным образом (или с наивысшей степенью (2 для всех оставшихся узлов)) => t3 (это может быть проблемой)
    2. Удалить его из графика, pu sh: [t5, t4, t3]
  4. Найти узел с менее чем 2 ребрами
    1. Найдено t2
    2. Удалите его из графика, pu sh: [t5, t4, t3, t2]
  5. Pu sh последний узел: [t5, t4, t3, t2, t1]

Теперь назначьте регистры в обратном порядке:

  1. Символ Pop => t1
    1. Конфликтующие узлы: нет
    2. Назначить: t1 => r0
    3. Put t1 обратно в график
  2. Pop t2
    1. Конфликтующие узлы: {t1: r0}
    2. У нас есть еще один бесплатный регистр
    3. Назначить: t2 => r1
    4. Поместить t2 обратно в график
  3. Pop t3
    1. Конфликтующие узлы: {t1: r0, t2: r1}
    2. ОЙ! Больше никаких бесплатных регистров!
    3. Spill it => t3 => m0
    4. Поместите t3 обратно в график
  4. Больше никаких разливов не требуется!

Окончательное назначение: 

t1 -> r0
t2 -> r1
t3 -> m0 (spilled)
t4 -> r0 (or r1)
t5 -> r0 (or r1)

Вставка разливов

Теперь, согласно это (слайд 29) и это (слайд 4):

Перед каждой операцией, которая использует [символ разлива t3], вставлять t3 := load m0

После каждой операции, которая определяет [символ разлива t3], вставьте store t3, m0

Давайте сделаем это, а также вычислим живые диапазоны: 

t1 = 1       |
t2 = 2       | t1

t3 = 3       | t1, t2
// STORE
store t3, m0 | t1, t2, t3 (STILL 3 SYMBOLS!)

t4 = t1 + t2 | t1, t2

// LOAD
t3 = load m0 | t4
t5 = t3 + t4 | t3, t4

use t5       | t5

Задача

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

Итак, разлив не сработал!

Теперь я перебил всех возможных кандидатов на разлив. вручную и обнаружил, что буровая установка остается не 2-раскрашиваемой, если мы пролили какой-либо один символ, но она становится 2-раскрашиваемой, если мы вылим любую из этих пар символов: * 1 153 *

  • t1 и t3
  • t2 и t3

... а также t1, t2 и t3, но пролить только два символа выглядит проще.

Актуальный вопрос

Как мне решить, что разлить? Какую эвристику c использовать? Мне также хотелось бы, чтобы алгоритм выполнял глобальное назначение регистров, поэтому простые живые диапазоны и линейное сканирование (в отличие от построения RIG) кажутся довольно громоздким подходом.

Кроме того, если я повторно запустите тот же алгоритм для кода с разливами, результатом будет снова «spill t3», даже если это уже сделано, поэтому код будет l oop навсегда. Более того, если я продолжу проливать t3 и вставлять код load / store, я получу все больше и больше инструкций, где мешают t1, t2 и t3, поэтому ситуация будет ухудшаться .

И это при условии, что я могу просто t3 = load m0, в то время как на ARM (на который я нацеливаюсь) m0 сначала нужно сохранить в своем собственном регистре.

...