Оптимизация вызовов хвоста LLVM

Question

Вот мое понимание вещей:

Функция «f» является хвостовой рекурсивной, когда называть себя является ее последним действием. Хвост-рекурсия может быть значительно оптимизирована путем формирования цикла вместо вызова функции снова; параметры функции обновляются на месте, и тело снова запускается. Это называется рекурсивной оптимизацией хвостовых вызовов.

LLVM реализует рекурсивную оптимизацию вызовов при использовании fastcc, GHC или соглашения об использовании HiPE. http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

У меня есть несколько вопросов: Давайте рассмотрим простой пример:

int h(int x){ 
    if (x <= 0) 
    return x; 
    else 
    h(x-1); 
} 

1) В своем примере, ключевое слово «хвост» предшествует вызов. В другом месте я читал, что это ключевое слово необязательно. Пусть функция выше переводится на LLVM надлежащим образом, сделать последние несколько строк должны быть

%x' = load *i32 %x 
%m = tail call fastcc i32 @h(i32 %x') 
ret %m 

2) Каково значение опции inreg в их примере?

3) Я бы не хотел выполнять оптимизацию хвостовых вызовов повсюду, только для рекурсивных функций. Есть ли способ заставить LLVM выполнять только оптимизацию (когда она доступна) для рекурсивных функций?

Answer 1

Видимо, да. Вы должны изменить определение h, чтобы увидеть это (потому что оптимизатор слишком хорош! Он выясняет, что h является либо идентификатором, либо возвращает 0).

Рассмотрим

int factorial (int x, int y){ 
    if (x==0) 
    return y; 
    else 
    return factorial(x-1,y*x); 
} 

Собран с лязгом -S -emit-LLVM, так что не выполняется оптимизация. Видно, что прямые вызовы не указаны напрямую, а это означает, что соглашение о вызове по умолчанию достаточно для поддержки оптимизации хвостовой рекурсии (независимо от того, поддерживает ли он хвостовой вызов вообще - это другая история - было бы интересно узнать, но я думаю это действительно другой вопрос).

Файл, испускаемый clang -S -emit-llvm, является main.s (при условии, что определение факториала находится в main.c). Если вы запустите

opt -O3 main.s -S -o mainOpt.s 

затем вы можете видеть, что рекурсия хвоста устранена. Существует оптимизация, называемая tailcallelim, которая может быть включена как -O3. Трудно сказать, потому что файл справки opt -help говорит только, что -O3 похож на gcc -O3.

Дело в том, что мы можем видеть, что для этого не требуется указывать соглашение. Может быть, fastcc не нужен, или, может быть, он по умолчанию? Итак, (1) частично ответили; однако я до сих пор не знаю (2) или (3).

Answer 2

Есть две разные вещи здесь:

1. Вы можете оптимизировать самостоятельно рекурсивной хвост вызывает в петлю. LLVM предоставляет пропуск оптимизации, который делает это. Это не требует специального соглашения о вызове.
2. Вы можете использовать другое соглашение о вызове, чтобы гарантировать оптимальную оптимизацию вызовов всех вызовов в позиции хвоста (т. Е. Включая вызовы других функций).С LLVM вам нужно указать соглашение о вызове функции, в команде вызова и пометить вызов как хвостовой вызов.

Звучит так, как будто вы хотите первого.