Оптимизация GCC передает работу над промежуточным представлением вашего кода в формате GIMPLE .
Используя опции -fdump-*, вы можете попросить GCC вывести промежуточные состояния дереваи узнайте много подробностей о выполненных оптимизациях.
В этом случае интересные файлы (номера могут различаться в зависимости от версии GCC):
.004t.gimple
Этоявляется начальной точкой:
int Identity(int) (int i)
{
int D.2330;
int D.2331;
int D.2332;
if (i == 1) goto <D.2328>; else goto <D.2329>;
<D.2328>:
D.2330 = 1;
return D.2330;
<D.2329>:
D.2331 = i + -1;
D.2332 = Identity (D.2331);
D.2330 = D.2332 + 1;
return D.2330;
}
.038t.eipa_sra
Последний оптимизированный источник, представляющий рекурсию:
int Identity(int) (int i)
{
int _1;
int _6;
int _8;
int _10;
<bb 2>:
if (i_3(D) == 1)
goto <bb 4>;
else
goto <bb 3>;
<bb 3>:
_6 = i_3(D) + -1;
_8 = Identity (_6);
_10 = _8 + 1;
<bb 4>:
# _1 = PHI <1(2), _10(3)>
return _1;
}
Как обычно с SSA , GCC вставляет ложные функции, известные как PHI, в начало базовых блоков, где это необходимо, для объединения нескольких возможных значений переменной.
Здесь:
# _1 = PHI <1(2), _10(3)>
где_1 либо получает значение 1, либо _10, в зависимости от того, достигаем ли мы здесь через блок 2 или блок 3.
.039t.tailr1
Это первая свалка, в которой есть рекурсияn превращается в цикл:
int Identity(int) (int i)
{
int _1;
int add_acc_4;
int _6;
int acc_tmp_8;
int add_acc_10;
<bb 2>:
# i_3 = PHI <i_9(D)(0), _6(3)>
# add_acc_4 = PHI <0(0), add_acc_10(3)>
if (i_3 == 1)
goto <bb 4>;
else
goto <bb 3>;
<bb 3>:
_6 = i_3 + -1;
add_acc_10 = add_acc_4 + 1;
goto <bb 2>;
<bb 4>:
# _1 = PHI <1(2)>
acc_tmp_8 = add_acc_4 + _1;
return acc_tmp_8;
}
Та же оптимизация, которая обрабатывает хвостовые вызовы, также обрабатывает тривиальные случаи рекурсивного хвостового вызова путем создания аккумуляторов.
Существует очень похожий пример вначальный комментарий файла https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-tailcall.c:
В файле реализовано исключение хвостовой рекурсии.Он также используется для анализа хвостовых вызовов в целом, передачи результатов на уровень rtl, где они используются для оптимизации sibcall.
Помимо стандартного исключения хвостовой рекурсии, мы обрабатываем самые тривиальные случаи созданияхвост рекурсивен путем создания аккумуляторов.
Например, следующая функция
int sum (int n)
{
if (n > 0)
return n + sum (n - 1);
else
return 0;
}
преобразуется в
int sum (int n)
{
int acc = 0;
while (n > 0)
acc += n--;
return acc;
}
Для этого мы поддерживаем два аккумулятора (a_acc и m_acc), которые указывают, что когда мы достигнем оператора return x, мы должны вместо этого вернуть a_acc + x * m_acc.Они изначально инициализируются в 0 и 1 соответственно, поэтому семантика функции, очевидно, сохраняется.Если мы гарантируем, что значение аккумулятора никогда не изменится, мы опустим аккумулятор.
В трех случаях функция может выйти.Первый обрабатывается в Adjust_return_value, два других в Adjust_accumulator_values (второй случай на самом деле является частным случаем третьего, и мы представляем его отдельно только для ясности):
- Просто вернуть
xгде x отсутствует ни в одной из оставшихся специальных фигур.Мы переписываем это в простой эквивалент return m_acc * x + a_acc. - return
f (...), где f - текущая функция, переписывается классическим способом исключения хвостовой рекурсии, в назначение аргументов и переходк началу функции.Значения аккумуляторов не изменяются. - return
a + m * f(...), где a и m не зависят от вызова на f.Чтобы сохранить семантику, описанную ранее, мы хотим, чтобы это было переписано таким образом, чтобы мы наконец вернули a_acc + (a + m * f(...)) * m_acc = (a_acc + a * m_acc) + (m * m_acc) * f(...).Т.е. мы увеличиваем a_acc на a * m_acc, умножаем m_acc на m и исключаем хвостовой вызов до f.Особые случаи, когда значение только добавляется или просто умножается, получается установкой a = 0 или m = 1.