🍭

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

に公開
2023/01/19
1件
Zig
LLVM
tech

昔の会話

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

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

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

今のコンパイラの最適化

ちょっとやってみました。
円周率を求めるプログラムはこちらのものをお借りしました。
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13234300703

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にインライン展開されました。

関連

今回のことは下記の記事を書いた2013年の段階で実現できていたと思います。
https://embedded.hatenadiary.org/entry/20130622/p1

https://zenn.dev/tetsu_koba/articles/17959ee2770aa3

Discussion

藤田望藤田望

コンパイル時最適化は夢があって良いですね。
円周率を計算するプログラムは円周率.jpの158Byte で 2400 桁をお借りしています。

pi.cpp
#include <cstdio>

constexpr int N = 767;// 小数点以下桁数(とりあえずファインマンポイントまで)

struct s {
    char c[1 + 1 + N + 1];
}; 

constexpr s compute() {
  int a = 10000;
  int c = (N + 3 + 1) / 4 * 14;
  int b = 0;
  int d = 0;
  int e = 0;
  int g = 0;
  int f[(N + 3 + 1) / 4 * 14 + 1] = {};
  s buff = {};
 
  for (b = 0; b < c; b++) {
    f[b] = a / 5;
  }
 
  e = 0;
  for (int i = 0, c = (N + 3 + 1) / 4 * 14; i < 1 + 1 + N; i += 4, c -= 14) {
    d = 0;
    for (b = c - 1; b > 0; b--) {
      g = 2 * b - 1;
      d = d * b + f[b] * a;
      f[b] = d % g;
      d /= g;
    }
    int h = 1000;
    for (int j = 0; j < 4; j++) {
        buff.c[i + j] = '0' + (e + d / a) / h % 10;
        h /= 10;
        if (i + j == 0) {
            i++;
            buff.c[i + j] = '.';
        }
        if (i + j >= 1 + 1 + N - 1) {
            break;
        }
    }
    e = d % a;
  }
  return buff;
}

int main(void) {
    s s = compute();
    puts(s.c);
}

C++のconstexprを使用し、clang++ 22.1.0に-O1 -fconstexpr-steps=0を指定してコンパイルしています。

main:
        stp     x29, x30, [sp, #-16]!
        mov     x29, sp
        adrp    x0, .L__const.main.s
        add     x0, x0, :lo12:.L__const.main.s
        bl      puts
        mov     w0, wzr
        ldp     x29, x30, [sp], #16
        ret

.L__const.main.s:
        .asciz  "3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526356082778577134275778960917363717872146844090122495343014654958537105079227968925892354201995611212902196086403441815981362977477130996051870721134999999"

https://godbolt.org/z/rEs4b7d9d

1