C-후부 반복 최적화

구상적 독자

Haskell의 처리 시스템인 GHC가 설치되었습니다.

처리 시스템이 하드 드라이브에 남아 있음

C 언어는 읽을 수 있다

언어 처리 시스템 자체에 관심이 있음

어셈블리 언어에 대해서도 대체적으로 알고 있다

개시하다

Haskell의 대표적인 처리 시스템인 GHC에서 원본 코드는 C-로 컴파일됩니다.C-가 아닌 C-를 사용하는 이유 중 하나로 처리 시스템의 절차를 더욱 자유롭게 제어할 수 있다.하나의 예로 C-에서 결과가 돌아가는 (명확한) 최적화는 쉽게 표현할 수 있다.
하나의 예만 제시하고 문법은 설명하지 않는다.또한 이것은 저자의 환경(x86-64, Linux)의 예로 다른 환경에서 조정이 필요할 수 있다.
잘못이 있다면 부드럽게 지적해 주세요.여기에 소개된 코드는 다음과 같이 시작할 수 있다.
https://github.com/YoshikuniJujo/cmm/tree/master/qiita/tail_call_opt

C--무엇이

C-어떤 느낌인지 다음 논문에서 정리한다.
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/ppdp.pdf
간단히 설명하면 다음과 같다.
고급 언어의 컴파일러를 제작할 때 각자의 하드웨어에 대해 각자의 기계어를 생성하는 것이 아니라 어느 하드웨어에 공통된 중간적인 표현을 생성하여 각자의 기계어로 전환하는 코드 효율이 더욱 좋다.C 언어는 공통된 중간 표현으로 사용된 적이 있습니다.C 언어의 컴파일러가 널리 보급되어 좋은 선택이다.그러나 C언어는 이런'중간적 표현'으로 설계된 것이 아니어서 다양한 문제가 발생한다.그런 문제를 해결할 수 있도록 표현을 요구하다.그래서 C 언어와 어셈블리의 중간 표현인 C-를 설계했다.
C-의 컴파일러는 독립된 프로젝트로 몇 개 개발되었지만, 지금은 유지보수되지 않았다.따라서 GHC는 유지 관리되는 C-처리 시스템으로서 사용하기로 결정되었습니다.

C 함수main에서 호출

C 함수main에서 호출하여 C-로부터의 반환 값을 보여 줍니다.다음 코드를 준비하십시오.
fun.cmm

foo()
{
	return(123);
}

준비foo이런 수속(모듈).이것은 반환값으로 되돌아온다123.다음에 foo의 C 언어 코드를 호출할 준비를 하세요.
call_cmm.c

#include <stdio.h>

int
main(int argc, char *argv[])
{
	long ret;

	__asm__(
		"addq $-16, %%rsp\n\t"
		"moveq %%rbp, 8(%%rsp)\n\t"
		"moveq %%rsp, %%rbp\n\t"
		"moveq $print_ret, (%%rbp)\n\t"
		"jmp foo\n"
	"print_ret:\n\t"
		"moveq 8(%%rsp), %%rbp\n\t"
		"addq $16, %%rsp\n"
	: "=b"(ret)
	:
	: );

	printf("ret: %ld\n", ret);
	return 0;
}

함수main에서 C-의foo를 호출합니다.C-에서 %rbp는 스택 포인터로 사용되기 때문에 라벨%rbp의 값이 print_ret가 가리키는 주소를 대입한다.%rsp,%rbp는 이 전후에 값을 바꾸고 싶지 않기 때문에 다음과 같이 처리한다.

%rsp에서 16

을 빼다

%rsp의 값에 8을 더한 주소%rbp의 값을 대입

%rsp의 값을 %rbp

에 복제

%rbp의 값을 print_ret의 값에 대입한 주소

(으)로 건너뛰기foo

foo에서 %rbp로 되돌아오는 값에 표시된 주소 처리print_ret

%rsp의 값과 8의 주소로 되돌아오는 값%rbp

%rsp에 16

추가
아마도, 이렇게 하면 C-의 처리를 안전하게 호출할 수 있을 것이다.번역해 보세요.

% ghc fun.cmm -no-hs-main call_cmm.c -o fun
% ./fun
ret: 123

GHC는 기본적으로 C의 함수main입니다.이번에는 자기main를 사용하고 싶어서 선택해야 한다-no-hs-main.

마지막 컴백의 최적화란

다음과 같은 처리 요구가 있습니다.

처리의 명칭은 factorial

매개 변수는 n와 s 두 개

n비0보다 크면n - 1과s * n를 매개 변수factorial로 호출

n가 0인 경우 s의 값

을 반환합니다.
이 처리는 n 하나하나 1 줄어들고, 매번 s 는 n배이다.되돌아오는 값n의 곱셈이다.C 언어의'함수 호출'로 이 방법을 실행하면 매번 호출factorial할 때마다 창고에'귀환 주소'를 누적하고 n가0되더라도 처리는 창고에 누적된 주소를 순서대로 귀환한다.
하지만 그런 일을 할 필요는 없다.n가 0가 되는 단계에서 단숨에 최초의 호출원으로 돌아가면 된다.그럼 창고 구역도 낭비하지 않을 거예요.
이렇게 하면'스택으로 되돌아와 스택된 주소'의 처리와'스택된 주소를 순서대로 추적하는 처리'를 생략하는 것이 마지막 스택의 최적화(가능)입니다.

계산 단계 처리 (최적화되지 않은 버전)

끝부분 귀속 최적화 버전의 '계산 곱셈 처리' 는 다음과 같다.
fac_no_opt.cmm

factorial(bits64 n, bits64 s)
{
	if (n > 0) {
		(bits64 ret) = call factorial(n - 1, s * n);
		return(ret);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call factorial(10, 1);
	return(ret);
}

대충 알 것 같아서요.소스 C 언어의 소스 코드 사용call_cmm.c을 호출합니다.

% ghc fac_no_opt.cmm -no-hs-main call_cmm.c -o fac_no_opt
% ./fac_no_opt
ret: 3628800

계산 곱셈 처리 (최적화 버전)

그럼 끝부분의 귀속 버전을 최적화해 봅시다.C-에서 호출 처리 방법은 call뿐만 아니라 jump도 요점이다.아래와 같다.
fac_opt.cmm

factorial(bits64 n, bits64 s)
{
	if (n > 0) {
		jump factorial(n - 1, s * n);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call factorial(10, 1);
	return(ret);
}

n가 0보다 클 때의 처리는 call가 아니라 jump이다.주프로 비행할 때 처리해. 돌아오지 않을 거야.창고 주소가 쌓인 것을 되돌려주는 일도 없었다.그리고 처리는 제n회factorial회n + 1회return명령 제1차factorial호foo로 되돌아갔다.여분의 창고 소비와 여분의 도약을 생략했다.번역해 보세요.

% ghc fac_opt.cmm -no-hs-main call_cmm.c -o fac_opt
% ./fac_opt
ret: 3628800

1에서 n의 합을 계산하는 처리에서 비교하다

만약에'계승'이라면 결과가 너무 크다1부터 n까지의 총화라는 제재는 전후 처리를 비교적 최적화시켰다.

최적화 없음

최적화가 없으면 코드 개발을 진행할 수 있다.
sum_no_opt.cmm

summation(bits64 n, bits64 s)
{
	if (n > 0) {
		(bits64 ret) = call summation(n - 1, s + n);
		return(ret)
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call summation(2000000, 0);
	return(ret);
}

곱셈을 화산으로 바꾸다.아무튼 n부터 2000000(200만 원)로 바꾸자.해봐.

% ghc sum_no_opt.cmm -no-hs-main call_cmm.c -o sum_no_opt
% ./sum_no_opt
zsh: segmentation fault ./sum_no_opt

창고 구역을 다 썼나 봐요.부문별로 분류되다.

최적화 후

마지막으로 귀속이 최적화 코드로 바뀌었다.
sum_opt.cmm

summation(bits64 n, bits64 s)
{
	if (n > 0) {
		jump summation(n - 1, s + n);
	} else {
		return(s);
	}
}

foo()
{
	(bits64 ret) = call summation(2000000, 0);
	return(ret)
}

최적화되지 않은 버전에서 분리형2000000(200만)으로 변경해 봤다.

% ghc sum_opt.cmm -no-hs-main call_cmm.c -o sum_opt
% ./sum_opt
ret: 2000001000000

전혀 문제 없어요.그럼 2000000(200만)이 아니라 1000000000(10억)해보자.
sum_opt.cmm

...
	(bits64 ret) = call summation(1000000000, 0);
...

% ghc sum_opt.cmm -no-hs-main call_camm.c -o sum_opt
% ./sum_opt
ret: 500000000500000000

10억 번, 불러도 놀라지 않는다.

총결산

고급 언어의 컴파일러를 만들 때 모든 하드웨어의 기계 언어는 생성하기 어렵다.이 경우 C 언어를 중간 언어로 사용하는 것은'아이쿠아'다.그러나 C 언어는 원래 그런 용도로 쓰이지 않아 문제가 많았다.그 문제에서 끝부분 회귀를 최적화하기 어려운 문제가 하나 있다.C - 고급 언어를 컴파일할 때 중간 표현으로 설계된 언어입니다.중간 표현으로 C-대 C의 장점은'컴백 마무리를 위한 최적화는 간단하다'다.처리 블록을 호출할 때call 이런 방법이 아니라 jump 이런 방법을 준비했기 때문이다.간단한 예에서 C-의 꼬리 귀속 최적화 상황을 보여 준다.