gcc가 꼬리 재귀 최적화를 수행하는지 어떻게 확인합니까?

gcc가 꼬리 재귀 최적화를 수행하는지 어떻게 확인합니까?

---

gcc (구체적으로는 g ++)가 특정 함수에서 꼬리 재귀 를 최적화하고 있는지 어떻게 알 수 있습니까? (이것은 몇 번을 마련이기 때문에 :. GCC는 일반적으로 꼬리 재귀를 최적화 할 수 있는지 테스트 싶지 않아 나는 그것이 최적화 알고 싶어 내 꼬리 재귀 함수를.)

귀하의 대답이 "생성 된 어셈블러보기"인 경우, 정확히 무엇을 찾고 있는지, 그리고 최적화가 있는지 확인하기 위해 어셈블러를 검사하는 간단한 프로그램을 작성할 수 있는지 여부를 알고 싶습니다.

추신. 이것이 꼬리 재귀 최적화를 수행하는 C ++ 컴파일러가있는 경우 질문의 일부로 나타나는 것을 알고 있습니다 . 5 개월 전부터. 그러나 나는 그 질문 의이 부분이 만족스럽게 대답되었다고 생각하지 않습니다 . (답은 "컴파일러가 최적화를 수행했는지 확인하는 가장 쉬운 방법은 (내가 알고있는) 스택 오버플로를 초래할 수있는 호출을 수행하거나 어셈블리 출력을 보는 것입니다.")

---

다른 질문의 예제 코드를 사용하겠습니다 . 컴파일하되 gcc에게 어셈블하지 말라고 지시하십시오.

gcc -std = c99 -S -O2 test.c

이제 _atoi결과 test.s 파일 (Mac OS 10.5의 gcc 4.0.1)에서 함수를 살펴 보겠습니다 .

        .text
        .align 4,0x90
_atoi:
        pushl   %ebp
        testl   %eax, %eax
        movl    %esp, %ebp
        movl    %eax, %ecx
        je      L3
        .align 4,0x90
L5:
        movzbl  (%ecx), %eax
        testb   %al, %al
        je      L3
        leal    (%edx,%edx,4), %edx
        movsbl  %al,%eax
        incl    %ecx
        leal    -48(%eax,%edx,2), %edx
        jne     L5
        .align 4,0x90
L3:
        leave
        movl    %edx, %eax
        ret

컴파일러는이 함수에 대해 꼬리 호출 최적화를 수행했습니다. call원래 C 코드에는 함수 호출이있는 반면 해당 코드 에는 명령 이 없기 때문에 알 수 있습니다 . 또한 jne L5함수에서 뒤로 점프 하는 명령어 를 볼 수 있는데, 이는 C 코드에 분명히 루프가 없을 때 루프를 나타냅니다. 최적화를 끈 상태에서 재 컴파일하면라는 줄이 표시되고 call _atoi뒤로 점프도 표시되지 않습니다.

이를 자동화 할 수 있는지 여부는 또 다른 문제입니다. 어셈블러 코드의 세부 사항은 컴파일하는 코드에 따라 다릅니다.

프로그래밍 방식으로 발견 할 수 있다고 생각합니다. 함수가 스택 포인터의 현재 값을 인쇄하도록합니다 (x86에서 ESP 등록). 함수가 첫 번째 호출에 대해 재귀 호출과 동일한 값을 인쇄하면 컴파일러가 마무리 호출 최적화를 수행 한 것입니다. 이 아이디어는 관찰하고자하는 함수를 수정해야하며 컴파일러가 함수를 최적화하기 위해 선택하는 방법에 영향을 미칠 수 있습니다. 테스트가 성공하면 (동일한 ESP 값이 두 번 모두 인쇄 됨) 계측 없이도 최적화가 수행 될 것이라고 가정하는 것이 합리적이라고 생각하지만 테스트가 실패하면 실패가 원인인지 알 수 없습니다. 인스 트루먼 테이션 코드 추가.

---

편집 내 원래 게시물은 GCC가 실제로 테일 콜 제거를 수행하는 것을 방지했습니다. 나는 GCC가 어쨌든 테일 콜 제거를 수행하도록 속이는 몇 가지 추가 트릭을 추가했습니다.

Steven의 답변을 확장하면 프로그래밍 방식으로 동일한 스택 프레임이 있는지 확인할 수 있습니다.

#include <stdio.h>

// We need to get a reference to the stack without spooking GCC into turning
// off tail-call elimination
int oracle2(void) { 
    char oracle; int oracle2 = (int)&oracle; return oracle2; 
}

void myCoolFunction(params, ..., int tailRecursionCheck) {
    int oracle = oracle2();
    if( tailRecursionCheck && tailRecursionCheck != oracle ) {
        printf("GCC did not optimize this call.\n");
    }
    // ... more code ...
    // The return is significant... GCC won't eliminate the call otherwise
    return myCoolFunction( ..., oracle);
}

int main(int argc, char *argv[]) {
    myCoolFunction(..., 0);
    return 0;
}

비재 귀적으로 함수를 호출하는 경우 check 매개 변수를 0으로 전달하십시오. 그렇지 않으면 오라클을 전달하십시오. 제거되어야하는 꼬리 재귀 호출이 그렇지 않은 경우 런타임에 알림을 받게됩니다.

이것을 테스트 할 때 내 버전의 GCC가 첫 번째 마무리 호출을 최적화하지 않는 것처럼 보이지만 나머지 마무리 호출은 최적화되어 있습니다. 흥미 롭군.

---

생성 된 어셈블리 코드를보고 x86의 재귀 호출에 대해 call또는 jmp명령어를 사용하는지 확인합니다 (다른 아키텍처의 경우 해당 명령어를 검색). nm및 objdump을 사용 하여 함수에 해당하는 어셈블리 만 가져올 수 있습니다 . 다음 기능을 고려하십시오.

int fact(int n)
{
  return n <= 1 ? 1 : n * fact(n-1);
}

다음으로 컴파일

gcc fact.c -c -o fact.o -O2

그런 다음 꼬리 재귀를 사용하는지 테스트하려면 :

# get starting address and size of function fact from nm
ADDR=$(nm --print-size --radix=d fact.o | grep ' fact$' | cut -d ' ' -f 1,2)
# strip leading 0's to avoid being interpreted by objdump as octal addresses
STARTADDR=$(echo $ADDR | cut -d ' ' -f 1 | sed 's/^0*\(.\)/\1/')
SIZE=$(echo $ADDR | cut -d ' ' -f 2 | sed 's/^0*//')
STOPADDR=$(( $STARTADDR + $SIZE ))

# now disassemble the function and look for an instruction of the form
# call addr <fact+offset>
if objdump --disassemble fact.o --start-address=$STARTADDR --stop-address=$STOPADDR | \
    grep -qE 'call +[0-9a-f]+ <fact\+'
then
    echo "fact is NOT tail recursive"
else
    echo "fact is tail recursive"
fi

위의 함수에서 실행되면이 스크립트는 "fact is tail recursive"를 출력합니다. 대신 컴파일 할 때 -O3대신 -O2,이 호기심 인쇄 "사실은 꼬리 재귀 아닙니다."

ehemient가 그의 의견에서 지적했듯이 이것은 거짓 부정을 초래할 수 있습니다. 이 스크립트는 함수에 자체에 대한 재귀 호출이 전혀 포함되어 있지 않고 형제 재귀 (예 :를 A()호출 B()하는 호출 A())를 감지하지 않는 경우에만 정답을 산출합니다 . 지금은 생성 된 어셈블리를 사람이 보지 않는보다 강력한 방법을 생각할 수 없지만 적어도이 스크립트를 사용하여 개체 파일 내의 특정 기능에 해당하는 어셈블리를 쉽게 가져올 수 있습니다.

---

PolyThinker의 답변을 확장하면 구체적인 예가 있습니다.

int foo(int a, int b) {
    if (a && b)
        return foo(a - 1, b - 1);
    return a + b;
}

i686-pc-linux-gnu-gcc-4.3.2 -Os -fno-optimize-sibling-calls 산출:

00000000 <foo> :
   0:55 푸시 % ebp
   1:89 e5 이동 % esp, % ebp
   3 : 8b 55 08 mov 0x8 (% ebp), % edx
   6 : 8b 45 0c mov 0xc (% ebp), % eax
   9:85 d2 테스트 % edx, % edx
   b : 74 16 je 23 <foo + 0x23>
   d : 85 c0 테스트 % eax, % eax
   f : 74 12 je 23 <foo + 0x23>
  11:51 % ecx 푸시
  12:48 dec % eax
  13:51 푸시 % ecx
  14:50 % eax 푸시
  15 : 8d 42 ff lea -0x1 (% edx), % eax
  18:50 푸시 % eax
  19 : e8 fc ff ff ff 호출 1a <foo + 0x1a>
  1e : 83 c4 10 추가 $ 0x10, % esp
  21 : eb 02 jmp 25 <foo + 0x25>
  23:01 d0 % edx, % eax 추가
  25 : c9 휴가
  26 : c3 ret

i686-pc-linux-gnu-gcc-4.3.2 -Os 산출:

00000000 <foo>:
   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   8b 55 08                mov    0x8(%ebp),%edx
   6:   8b 45 0c                mov    0xc(%ebp),%eax
   9:   85 d2                   test   %edx,%edx
   b:   74 08                   je     15 <foo+0x15>
   d:   85 c0                   test   %eax,%eax
   f:   74 04                   je     15 <foo+0x15>
  11:   48                      dec    %eax
  12:   4a                      dec    %edx
  13:   eb f4                   jmp    9 <foo+0x9>
  15:   5d                      pop    %ebp
  16:   01 d0                   add    %edx,%eax
  18:   c3                      ret

In the first case, <foo+0x11>-<foo+0x1d> pushes arguments for a function call, while in the second case, <foo+0x11>-<foo+0x14> modifies the variables and jmps to the same function, somewhere after the preamble. That's what you want to look for.

I don't think you can do this programatically; there's too much possible variation. The "meat" of the function may be closer to or further away from the start, and you can't distinguish that jmp from a loop or conditional without looking at it. It might be a conditional jump instead of a jmp. gcc might leave a call in for some cases but apply sibling call optimization to other cases.

FYI, gcc's "sibling calls" is slightly more general than tail-recursive calls -- effectively, any function call where re-using the same stack frame is okay is potentially a sibling call.

[edit]

As an example of when just looking for a self-recursive call will mislead you,

int bar(int n) {
    if (n == 0)
        return bar(bar(1));
    if (n % 2)
        return n;
    return bar(n / 2);
}

GCC will apply sibling call optimization to two out of the three bar calls. I'd still call it tail-call-optimized, since that single unoptimized call never goes further than a single level, even though you'll find a call <bar+..> in the generated assembly.

---

i am way too lazy to look at a disassembly. Try this:

void so(long l)
{
    ++l;
    so(l);
}
int main(int argc, char ** argv)
{
    so(0);
    return 0;
}

compile and run this program. If it runs forever, the tail-recursion was optimized away. if it blows the stack, it wasn't.

EDIT: sorry, read too quickly, the OP wants to know if his particular function has its tail-recursion optimized away. OK...

...the principle is still the same - if the tail-recursion is being optimized away, then the stack frame will remain the same. You should be able to use the backtrace function to capture the stack frames from within your function, and determine if they are growing or not. If tail recursion is being optimized away, you will have only one return pointer in the buffer.

---

Another way I checked this is:

1. Compile your code with 'gcc -O2'
2. start 'gdb'
3. Place a breakpoint in the function you are expecting to be tail-recursion optimized/eliminated
4. run your code
5. If it has been tail call eliminated, then the breakpoint will be hit only once or never. For more on this see this

---

A simple method: Build a simple tail recursion program, compile it, and dissemble it to see if it is optimized.

Just realized that you already had that in your question. If you know how to read assembly, it's quite easy to tell. Recursive functions will call themselves (with "call label") from within the function body, and a loop will be just "jmp label".

---

You could craft input data that would lead to stack overflow because of too deep recursion of that function calls if there were no optimization and see if it happens. Of course, this is not trivial and sometimes big enough inputs will make the function run for intolerably long period of time.

참고URL : https://stackoverflow.com/questions/490324/how-do-i-check-if-gcc-is-performing-tail-recursion-optimization