最近、スタック消費量の見積もりをやっている。
前にも書いたのだが、どんぶり勘定というわけにはいかない部分があり、真面目に計算している。
コンパイラにスタック消費量の見積もり機能があって、
この関数を起点にしたスタック消費量を計算してといえば、普通はうまく出てくる。
ただ、アセンブラのコードやポインタ呼び出しの関数があるとそうもいかず、
それで前にOSの中身を調べていたという事情もある。
とはいえ、このあたりは調べればだいたい判明するものである。
ところがこれだけでは済まない部分があって、それが再帰呼び出しである。
関数の再帰呼び出しがあると 関数A→関数B→関数A→関数B……
となるとスタック消費量の見積もりは発散してしまう。
当然、無限に再帰呼び出しされるということはあり得ないし、
なんなら再帰呼び出し自体が発生しないことも多いのだが、解析上生じてしまうことがあると。
こういうケースについては再帰呼び出しの最大回数を指定して解析する機能がある。
再帰呼び出しはせいぜい1回だろうという検討が付いていれば、最大1回と指定すればうまくやってくれる。
実際は1回も再帰呼び出しにならないものが多いから過大な見積もりのような気はするけど。
ところが、これでもうまくいかないケースがあったのである。
(関数A, 関数B, 関数C)→関数X→関数Y→(関数A, 関数B, 関数C, 関数D) のような呼び出しパスがあると、
複数の再帰呼び出しのループが関数X→関数Yで被ってしまう場合である。
関数Aの再帰呼び出しが最大1回となるケースを考えても、
A→X→Y→B→X→Y→C→X→Y→A→X→Y→D のような遠回りをするケースも想定され、
解析ツールもこういうケースはまともに結果を出せないと警告が出てくる。
うーん、困ってしまった。
で、いろいろ調べたわけだが、こういうことは実際には存在しなくて、
例えば、関数Aを起点にした場合、関数Yには遷移しないとか、
関数Yから先への遷移がないとか、関数Yで呼び出す関数は関数Dに限られるとか、
いろいろな制約を付ける余地があることがわかった。
ところが、こういうのを解析ツールに設定する方法がないので、さてどうしたものかと。
考えた結果行き着いたのは、こういう問題を引き起こす関数のスタック消費量を別途計算して、
その結果を使って他の関数のスタック消費量を計算させるという方法だった。
関数Aを起点にした場合、関数Yには遷移しない場合は、
関数Yのスタック消費量は計算に入れないとしてスタック計算をさせる。
こうすると再帰呼び出しにならないので普通に計算できる。
関数Yからの遷移先が限られるというのは、いずれもポインタ呼び出しで、
ポインタ呼び出しの関数を列挙している部分を書き換えて、スタック計算させる。
この結果を関数Aのスタック消費量としてオーバーライドしておけば、回避できるというわけである。
しかし、なんでこんなわけのわからないことになってしまっているのか。
実はこれは社内でコーディングされたものではなく、
あるベンダーから購入したライブラリのコードなのである。
なかなか、どんぶり勘定とはいかないし、スタック消費量はコンパイラ次第、
どうしても我々の責任でもってスタック消費量を見積もらざるを得ない。
確かに意図的に再帰呼び出しを利用しているコードも一部には存在するのだが、多くはそうではない。
どうも関数ポインタを多用していることが背景にあるらしい。
解析上、関数ポインタ呼び出しを行う関数は、関数ポインタに入りうる関数をすべて列挙せざるを得ない。
ところが実際には呼び出し元によりだいたい限定されているのである。
わかりやすいパターンでは、関数ポインタを引数にとる関数があって、
func_z(func_1, ….); のように具体的な関数名を指定して呼び出される。
この場合、関数A→関数Z→関数B、関数C→関数Z→関数D のようにルートは決まり切っているが、
解析上は関数Zは関数B, 関数Dを呼び出しうるとして記述する。
この結果として解析上は再帰呼び出しが存在することになるが、実際にはあり得ないわけである。
ライブラリのコードの中身に立ち入る必要は本来なさそうなのだが、
デバッグやカスタマイズの都合で現実にはいろいろ立ち入っている。
あまりに複雑なコードに「一体何を考えてコーディングしてるんでしょうね」とぼやいているひとがいたが、
確かにこれは何を考えて作っているのか大変わかりにくい。
難しいですね。
当初は明らかにあり得ないパスの計算結果を出してすさまじい数字になっていたが、少しずつ収束してきている。
まだいくつか解消しないといけない再帰呼び出しはあり、難易度は高いが、なんとかなるかなぁと。