Как современная оптимизация компилятора может преобразовать рекурсию в возврат константы?

Когда я компилирую следующий простой рекурсивный код с помощью g++, ассемблерный код просто возвращает i, как если бы g++ мог выполнять некоторые трюки алгебры, как люди.

int Identity(int i) {
  if (i == 1)
    return 1;
  else
    return Identity(i-1)+1;
}

Я не думаю, что эта оптимизация касается хвостовой рекурсии, и, по-видимому, g++ должен по крайней мере сделать две эти вещи:

  1. Если мы передадим отрицательное значение, этот код попадет в бесконечный цикл, поэтому допустимо ли для g++ устранить эту ошибку?
  2. Хотя можно перечислить все значения от 1 до INT_MAX, а затем g++ может сказать, что эта функция должна возвращать i, очевидно, g++ использует более умный метод обнаружения, поскольку процесс компиляции довольно быстрый. Поэтому моя проблема в том, как оптимизация компилятора делает это?

Как воспроизвести

% g++ -v
gcc version 8.2.1 20181127 (GCC)

% g++ a.cpp -c -O2 && objdump -d a.o
Disassembly of section .text:
0000000000000000 <_Z8Identityi>:
   0:   89 f8                   mov    %edi,%eax
   2:   c3

Обновлено: спасибо многим за ответ на проблему. Я собрал некоторые обсуждения и обновления здесь.

  1. Компилятор использует некоторый метод, чтобы узнать, что передача отрицательных значений приводит к UB. Может быть, компилятор использует тот же метод для выполнения трюков алгебры.
  2. О хвостовой рекурсии: Согласно Википедии, мой прежний код НЕ является формой хвостовой рекурсии. Я попробовал версию хвостовой рекурсии, и gcc генерирует правильный цикл while. Тем не менее, он не может просто вернуть меня, как мой прежний код.
  3. Кто-то указывает, что компилятор может попытаться "доказать" f (x) = x, но я до сих пор не знаю названия используемой техники оптимизации. Я заинтересован в точном названии такой оптимизации, такой как устранение общего подвыражения (CSE) или какой-то их комбинации или чего-то еще.

Обновлено + ответил: Благодаря ответу ниже (я пометил его как полезный, а также проверил ответ от manlio), я думаю, я понимаю, как компилятор может сделать это простым способом. Пожалуйста, смотрите пример ниже. Во-первых, современный gcc может сделать что-то более мощное, чем хвостовая рекурсия, поэтому код преобразуется во что-то вроде этого:

// Equivalent to return i
int Identity_v2(int i) {
  int ans = 0;
  for (int i = x; i != 0; i--, ans++) {}
  return ans;
}
// Equivalent to return i >= 0 ? i : 0
int Identity_v3(int x) {
  int ans = 0;
  for (int i = x; i >= 0; i--, ans++) {}
  return ans;
}

(Я предполагаю, что) компилятор может знать, что ans и я разделяем одну и ту же дельту, и он также знает я = 0 при выходе из цикла. Следовательно, компилятор знает, что он должен вернуть i. В v3 я использую оператор >= поэтому компилятор также проверяет знак ввода для меня. Это может быть намного проще, чем я предполагал.

Ответы

Ответ 1

Оптимизация 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

Это первый дамп, в котором рекурсия была превращена в цикл:

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 (второй случай на самом деле является частным случаем третьего, и мы представляем его отдельно только для ясности):

  1. Просто верните x, где x не находится ни в одной из оставшихся специальных фигур. Мы переписываем это в простой эквивалент возврата m_acc * x + a_acc.
  2. return f (...), где f - текущая функция, переписывается классическим способом исключения хвостовой рекурсии в присвоение аргументов и переходит к началу функции. Значения аккумуляторов неизменны.
  3. вернуть 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.

Ответ 2

gcc может оптимизировать рекурсию даже в случае нерекурсивных вызовов. Я предполагаю, что многие общие рекурсивные шаблоны ищутся и затем переводятся в их итеративную или закрытую форму.

Вы можете прочитать эту старую добрую короткую страницу об (не) -well известных фактах оптимизации о gcc.

Ответ 3

Если мы передадим отрицательное значение, этот исходный код попадет в бесконечный цикл, так ли это верно для g++ для устранения этой ошибки?

Увеличение/уменьшение целых чисел со знаком может вызвать переполнение/отмену потока, что является неопределенным поведением (в отличие от целых чисел без знака). Компилятор просто предполагает, что UB здесь не происходит (т.е. Компилятор всегда предполагает, что целые числа со знаком не переполняются/не переполняются, если вы не используете -fwrapv). Если это так, то это ошибка программирования.