🍭

円周率を求めるプログラムを最適化すると

2023/01/14に公開

Zig

LLVM

tech

昔の会話

ふと思い出しました。
大昔、25年くらい前に会社の同僚と食事しながらの会話。

「究極のコンパイラの最適化ってさ、円周率を求めるプログラムを最適化するとprintfで定数で出力されるだけになるよね」

私は大学でコンパイラを学んでいたので、こう答えました。
「今はまだできないけど、原理的にそれは可能だよ。」

今のコンパイラの最適化

ちょっとやってみました。
円周率を求めるプログラムはこちらのものをお借りしました。

pi.c

#include <stdio.h>

double AandW(int n)
{
	double pi = 0.0;
	if (n < 32) {
		for (; n >= 0; --n) {
			double n4 = n * 4.0;
			double tmp =
				(2 / (n4 + 1) + 2 / (n4 + 2) +
				 1 / (n4 + 3)) / (1LL << 2 * n);
			pi += n & 1 ? -tmp : tmp;
		}
	}
	return pi;
}

int main()
{
	printf("PI=%.15f\n", AandW(31));
}

最後に1回だけprintfで出力するように修正しました。

$ zig cc -O2 pi.c
$ ./a.out
PI=3.141592653589794

逆アセンブルして出力コードを見て見ます。(aarch64です)

$ objdump -d a.out
　　　...

000000000000092c <main>:
 92c:	a9bf7bfd 	stp	x29, x30, [sp, #-16]!
 930:	910003fd 	mov	x29, sp
 934:	90000008 	adrp	x8, 0 <__abi_tag-0x278>
 938:	90000000 	adrp	x0, 0 <__abi_tag-0x278>
 93c:	9126e000 	add	x0, x0, #0x9b8
 940:	fd44d900 	ldr	d0, [x8, #2480]
 944:	97ffff3b 	bl	630 <printf@plt>
 948:	2a1f03e0 	mov	w0, wzr
 94c:	a8c17bfd 	ldp	x29, x30, [sp], #16
 950:	d65f03c0 	ret
 
 ...

AandW(31)の関数呼び出しは引数に定数を渡しているのでコンパイル時に計算されて、生成されたmainのコードはprintfを呼ぶだけになっていました。
25年前に思ったことはとっくに実現していました。

zig cc は実際には clang + llvm を呼び出します。
最適化のオプションをつけない場合はソースコードの通りにAandWを呼び出します。
-OだけだとAandWの内容がmainにインライン展開されました。

円周率を求めるプログラムを最適化すると

昔の会話

今のコンパイラの最適化

関連

Discussion