GCC가 꼬리 수익성 최적화를 수행하는지 어떻게 확인합니까?
https://stackoverflow.com/questions/490324
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
GCC (보다 구체적으로 G ++)가 꼬리 재귀를 최적화하고 있는지 어떻게 알 수 있습니까? 특정 기능에서? (몇 번 등장했기 때문에 : GCC가 일반적으로 꼬리 재귀를 최적화 할 수 있는지 테스트하고 싶지 않습니다. 최적화 여부를 알고 싶습니다. 나의 꼬리 재귀 기능.)
귀하의 대답이 "생성 된 어셈블러를보십시오"라면, 내가 찾고있는 것을 정확히 알고 싶습니다. 그리고 최적화가 있는지 확인하기 위해 어셈블러를 검사하는 간단한 프로그램을 작성할 수 있는지 여부를 알고 싶습니다.
추신. 나는 이것이 질문의 일부로 보인다는 것을 알고 있습니다 C ++ 컴파일러가 테일 추방 최적화를하는 경우 어느 것이 있습니까? 5 개월 전부터. 그러나 나는 생각하지 않습니다 이 부분 그 질문 중 만족스럽게 답변되었습니다. (답은 "컴파일러가 최적화를했는지 확인하는 가장 쉬운 방법 (내가 알고있는)은 스택 오버플로를 초래하거나 어셈블리 출력을보고있는 호출을 수행하는 것입니다."
해결책
사용합시다 다른 질문의 예제 코드. 컴파일하지만 GCC에게 조립하지 말라고 지시하십시오.
gcc -std=c99 -S -O2 test.c
이제 보자 _atoi 결과에서 기능 테스트 파일 (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;
}
함수를 비상장으로 호출 할 때 0을 0으로 전달하십시오. 그렇지 않으면 오라클을 통과하십시오. 제거 해야하는 꼬리 재귀 호출이 없다면 런타임에 알려질 것입니다.
이것을 테스트 할 때, 내 버전의 GCC가 첫 번째 꼬리 통화를 최적화하지는 않지만 나머지 테일 호출은 최적화 된 것처럼 보입니다. 흥미로운.
생성 된 어셈블리 코드를보고 그것이 사용하는지 확인하십시오. call 또는 jmp X86의 재귀 호출에 대한 지침 (다른 아키텍처의 경우 해당 지침을 찾으십시오). 당신이 사용할 수있는 nm 그리고 objdump 기능에 해당하는 어셈블리 만 얻습니다. 다음 기능을 고려하십시오.
int fact(int n)
{
return n <= 1 ? 1 : n * fact(n-1);
}
AS로 컴파일하십시오
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
위의 기능을 실행하면이 스크립트는 "사실은 재귀 적"인쇄를 인쇄합니다. 대신 컴파일 할 때 -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 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 16 je 23 <foo+0x23> d: 85 c0 test %eax,%eax f: 74 12 je 23 <foo+0x23> 11: 51 push %ecx 12: 48 dec %eax 13: 51 push %ecx 14: 50 push %eax 15: 8d 42 ff lea -0x1(%edx),%eax 18: 50 push %eax 19: e8 fc ff ff ff call 1a <foo+0x1a> 1e: 83 c4 10 add $0x10,%esp 21: eb 02 jmp 25 <foo+0x25> 23: 01 d0 add %edx,%eax 25: c9 leave 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
첫 번째 경우, <foo+0x11>-<foo+0x1d> 두 번째 경우에는 함수 호출에 대한 인수를 추진합니다. <foo+0x11>-<foo+0x14> 변수를 수정합니다 jmp서문 이후 어딘가에 같은 함수에 s. 그것이 당신이 찾고 싶은 것입니다.
나는 당신이 이것을 프로그래밍적으로 할 수 있다고 생각하지 않습니다. 가능한 변형이 너무 많습니다. 함수의 "고기"는 처음에 더 가까이 있거나 더 멀리 떨어져있을 수 있으며, 당신은 그것을 구별 할 수 없습니다. jmp 루프 나 조건부에서 보지 않고 조건부. a 대신 조건부 점프 일 수 있습니다 jmp. gcc a call 어떤 경우에는 다른 경우에 형제 통화 최적화를 적용하십시오.
FYI, GCC의 "형제 콜"은 테일 리커 징던 호출보다 약간 더 일반적입니다. 효과적으로 동일한 스택 프레임을 재사용하는 기능 호출은 잠재적으로 형제 자매 호출입니다.
편집하다
자립을 찾을 때의 예로 call 당신을 오도 할 것입니다.
int bar(int n) {
if (n == 0)
return bar(bar(1));
if (n % 2)
return n;
return bar(n / 2);
}
GCC는 형제 콜 최적화를 3 개 중 2 개에 적용합니다. bar 전화. 나는 그것을 찾을 수 없지만 단일 최적화되지 않은 전화는 단일 레벨보다 더 이상 더 이상 진행되지 않기 때문에 여전히 그것을 최적화라고 부릅니다. call <bar+..> 생성 된 어셈블리에서.
나는 분해를보기에는 너무 게으르다. 이 시도:
void so(long l)
{
++l;
so(l);
}
int main(int argc, char ** argv)
{
so(0);
return 0;
}
이 프로그램을 컴파일하고 실행하십시오. 그것이 영원히 실행되면, 꼬리 추방은 최적화되었습니다. 스택을 불고 있다면 그렇지 않았습니다.
편집 : 죄송합니다. 너무 빨리 읽으십시오. OP는 그의 특별한 기능 꼬리 재고가 최적화되어 있습니다. 확인...
... 원리는 여전히 동일합니다. 꼬리 수술이 최적화되면 스택 프레임은 동일하게 유지됩니다. 당신은 그것을 사용할 수 있어야합니다 백트레이스 기능 기능 내에서 스택 프레임을 캡처하고 성장 중인지 여부를 결정하십시오. 꼬리 재귀가 최적화되면 버퍼에서 하나의 리턴 포인터 만.
내가 확인한 또 다른 방법은 다음과 같습니다.
- 'gcc -o2'로 코드를 컴파일하십시오.
- 'GDB'시작
- 테일 추방/제거 될 것으로 예상되는 함수에 중단 점을 배치하십시오.
- 코드를 실행하십시오
- 꼬리 통화가 제거 된 경우, 중단 점은 한 번만 또는 전혀 맞지 않습니다. 이것에 대한 자세한 내용은 참조하십시오 이것
간단한 방법 : 간단한 꼬리 재귀 프로그램을 구축하고 컴파일 한 후 최적화되었는지 확인하십시오.
당신이 이미 당신의 질문에 그것을 가지고 있다는 것을 깨달았습니다. 어셈블리를 읽는 방법을 알고 있다면 말하기가 매우 쉽습니다. 재귀 함수는 기능 본문 내에서 스스로 ( "호출 레이블"포함)를 호출하고 루프는 "JMP 레이블"입니다.
최적화가 없으면 해당 기능 호출의 재귀가 너무 깊기 때문에 스택 오버플로로 이어지는 입력 데이터를 제작하고 발생하는지 확인할 수 있습니다. 물론 이것은 사소하지 않으며 때로는 충분히 큰 입력으로 인해 기능이 참을 수 없을 정도로 오랜 시간 동안 실행됩니다.
