[c++] C ++ 컴파일러가 꼬리 재귀 최적화를 수행합니까?



Answers

gcc 4.3.2는 main() 에이 함수 (crappy / trivial atoi() 구현)를 완전히 인라인합니다. 최적화 수준은 -O1 입니다. 나는 그것으로 extern 는 것을 알아 차릴 수있다. (심지어는 static 에서 extern 바꾼다. 꼬리 재귀는 꽤 빨리 사라지므로 프로그램의 정확성에 의존하지 않을 것이다.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}
Question

C와 C ++ 모두에서 tail-recursion 최적화를 수행하는 것이 완벽하게 잘 작동하는 것으로 보입니다. 그러나 디버깅하는 동안이 최적화를 나타내는 프레임 스택을 보지 못했습니다. 스택은 재귀가 얼마나 깊은 지 알려주기 때문에 일종의 좋은 방법입니다. 그러나 최적화도 훌륭합니다.

C ++ 컴파일러가이 최적화를 수행합니까? 왜? 왜 안돼?

컴파일러에게 어떻게 할 것인가?

  • MSVC의 경우 : / O2 또는 / Ox
  • GCC의 경우 : -O2 또는 -O3

컴파일러가 어떤 경우에 이것을 수행했는지 확인하는 것은 어떻습니까?

  • MSVC의 경우 PDB 출력을 활성화하여 코드를 추적 한 다음 코드를 검사합니다.
  • GCC ..의 경우?

나는 여전히 특정 함수가 컴파일러에 의해 이와 같이 최적화되었는지를 결정하는 방법에 대한 제안을하고 싶다. (비록 Konrad가 나에게 그것을 가정한다는 것을 안심할지라도)

컴파일러가 무한 재귀를 만들고 무한 루프 나 스택 오버플로를 일으키는 지 확인하면 컴파일러에서이 작업을 수행하는지 항상 확인할 수 있습니다 (GCC에서이 작업을 수행 한 결과 -O2가 충분하다는 사실을 알았지 만). 내가 알고있는 특정 기능을 확인하려면 어쨌든 종료됩니다. 나는 이것을 확인하기위한 쉬운 방법을 원한다. :)

몇 가지 테스트를 거친 후에, 나는 소멸자가이 최적화를 할 수있는 가능성을 망쳐 놓는다는 것을 발견했다. 특정 변수 및 임시 변수의 범위를 변경하여 return 문이 시작되기 전에 범위를 벗어나는 지 확인할 수있는 경우가 있습니다.

tail-call 후에 어떤 소멸자가 실행되어야한다면, tail-call optimization은 수행 될 수 없다.




명백한 (컴파일러는 요구하지 않는 한 이런 종류의 최적화를 수행하지 않는다.) C ++의 테일 콜 최적화에 대한 복잡성은 소멸자이다.

주어진 것과 같이 :

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

컴파일러는 재귀 호출이 반환 된 후에 cls 의 소멸자를 호출해야하므로 (일반적으로) 꼬리 호출을 최적화 할 수 없습니다.

때때로 컴파일러는 소멸자가 외부에서 볼 수있는 부작용이 없다는 것을 볼 수 있지만 (그렇게 빨리 처리 할 수는 있지만) 종종 그렇게 할 수 없습니다.

이 중 특히 일반적인 형태는 Funky 가 실제로 std::vector 또는 이와 유사한 부분입니다.




Links