Генерация кода компилятора - распределение регистров внутри условных блоков - PullRequest
Новая
       1

Генерация кода компилятора - распределение регистров внутри условных блоков

6 голосов
/ 22 сентября 2010

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

Например, предположим, что регистр для x (скажем,% eax на i386) был определен до следующего оператора: 

while ( x ) { x = x - 1 ; /* more statements */ }

В коде дополнительных оператороввозможно, что x будет перенаправлен обратно в стек.Когда код возвращается к началу цикла while для повторной оценки x, он попытается использовать% eax - но это может даже не содержать значение x сейчас.Таким образом, у нас может быть что-то вроде 

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
_LOOP1: cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       #eax now holds something else
        ....
        jmp _LOOP1

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

Мое решение выглядит примерно так: 

        movl -8(%ebp), %eax        # eax <- x
        ....                       # do stuff but let x stay in %eax
        movl %eax, -8(%ebp)        # spilling and clearing all registers
_LOOP1: movl -8(%ebp), %eax        # get a register for x again
        cmpl $0, %eax
        ....
        movl -12(%ebp), %eax       # eax now holds something else
        ....
        movl %eax, -8(%ebp)        # spill to prevent overwrite
        jmp _LOOP1

Кажется, мое решение немного постороннее или ненужное.Есть ли какой-то общий прием оптимизации, который я здесь забыл?

РЕДАКТИРОВАТЬ: Я также хотел бы отметить, что нечто подобное происходит для условий, таких как, если и если еще.Это происходит для них, потому что регистр может быть выделен для переменной внутри блока для условного выражения, но генератор кода предполагает, что он был перемещен туда для всего остального после.У меня почти такой же подход к этому делу.

1 Ответ

4 голосов
/ 27 сентября 2010

Общая техника, которую вы здесь ищете, обычно называется «расщеплением живого диапазона». Поиск Google для этого термина даст вам ссылки на кучу разных статей.По сути, идея заключается в том, что вы хотите разделить одну переменную (в вашем примере x) на несколько переменных с непересекающимися диапазонами реального времени, каждый из которых копируется в следующую в точке разделения.Таким образом, у вас будет x.0 перед циклом, который будет скопирован в x.1 непосредственно перед while и использован в качестве цикла.Затем сразу после цикла вы копируете x.1 в x.2 и используете его после цикла.Каждая из разделенных переменных потенциально может быть выделена для другого регистра (или стекового слота).

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

...