末尾再帰最適化判定

C++でコンパイラが末尾最適化を行なっているのかを判定するコードを考えてみた。

私は最初、id:higepon:20070804:1186241590のコードを思いついたのだけど、このプログラムは誤りだった。関数のなかでアドレス演算子&でアドレスをとると、そのアドレスを外部から参照されて変更とかされたときに、N回目の再帰とM回目(N!=M)の再帰とで異なるアドレス指していないと元のプログラムと等価にならない。 だから途中でアドレスをとると末尾再帰の最適化は行なわれないのだろう。

修正案は、こうだ。

#include <stdio.h> 
#include <stdlib.h> 

int* tail_rec_opt_internal(int level) 
{ 
	if (level == 0) 
		return &level; 

	return tail_rec_opt_internal(--level); 

} 

bool is_tail_rec_opt() 
{ 
	int level = 100; // ある程度大きい数に

	int diff =  (int)(&level - tail_rec_opt_internal(level));

	return diff < level;
	// 末尾再帰が行なわれていないなら、再帰の停止時にstack frame上には
	// 少なくともlevel個のintの値が格納されていたはずである。
} 

int _tmain(int argc, _TCHAR* argv[])
{
	printf("tail recursion call optimized? : %s\n", is_tail_rec_opt() ? "true" : "false"); 
	return 0; 
}

Visual C++2005で、最適化ありとなしとで正しく結果が表示されることを確認した。