Я попытался выполнить поиск, но не смог найти: какие реквизиты для функций, чтобы gcc оптимизировал хвостовую рекурсию? Есть ли ссылки или список, которые будут содержать наиболее важные случаи? Поскольку это зависит от версии, мои интересы - это версии 4.6.3 или более поздней версии (чем выше, тем лучше). Тем не менее, на самом деле, любая конкретная ссылка была бы весьма признательна.Рекурсия хвоста в gcc/g ++
Заранее благодарен!
При включенном режиме -O2 gcc будет выполнять оптимизацию хвостового вызова, если это возможно. Теперь вопрос: когда это возможно?
можно устранить один рекурсивный вызов всякий раз, когда рекурсивный вызов происходит либо непосредственно перед или внутри (одинарные) return заявление, поэтому нет никаких наблюдаемых побочных эффектов после этого, кроме, возможно, возвращается другое значение. Это включает в себя возвращающие выражения с участием тернарного оператора.
Обратите внимание, что даже если есть рекурсивных вызовах в обратном выражении (например, в примере с известным примером фибоначчи: return (n==1) ? 1 : fib(n-1)+fib(n-2);), рекурсия хвостового вызова по-прежнему применяется, но только до последнего рекурсивного вызова.
В качестве очевидного частного случая, если компилятор может доказать, что рекурсивная функция (и ее аргументы) квалифицируется как постоянное выражение, она может (вплоть до настраиваемой максимальной глубины рекурсии, по умолчанию 500) устранять не только хвостовой вызов , но полное выполнение функции. Это то, что GCC делает регулярно и довольно надежно в -O2, что даже включает в себя вызовы некоторых библиотечных функций, таких как strlen на литералах.
Я помню, что несколько версий назад у меня была проблема, когда gcc не оптимизировал хвосты для какой-либо виртуальной функции, но я не смог воспроизвести это поведение сейчас. Существуют ли там какие-то специальные ограничения? – dtldarek
Виртуальные вызовы функций преобразуются в «обычные» вызовы функций, если тип объекта известен во время компиляции, и поэтому они могут быть оптимизированы и встроены в хвостовой вызов. Однако, когда они действительно являются функциями _virtual_, они не могут быть оптимизированы, потому что во время компиляции невозможно узнать, что будет вызываться. Нет другого выбора, кроме как сделать «реальный» виртуальный вызов через vtable. Например, когда вы передаете 'B *' вашей функции и вызываете 'foo()' на этом указателе (с 'D1' и' D2', происходящими от 'B'), это может вызвать' D1 :: foo' или 'D2 :: foo' - рекурсивный или нет, компилятор не может знать. – Damon
Для оптимизации хвостового вызова вам не нужно знать, является ли функция рекурсивной, вы просто переключаете 'call' на' jmp', и это все (более или менее). Gcc может сделать это с помощью указателей на функции, есть ли у вас какие-либо идеи, почему vtable будет отличаться (прямо сейчас он также делает хвосты для виртуальных функций)? – dtldarek