1

制御フロー グラフのアイデアが得られました。これには、ジャンプを表すエッジで接続された基本ブロック (常に発生する操作のシーケンス) であるノードが含まれます。

しかし、サブルーチン呼び出しをどのように表現するのでしょうか?

次のような 2 つの関数がある場合:

int tweedledee(void)
{
    int x = 16;
    return x + do_something();
}

int tweedledum(int n)
{
    if (n < 0)
       return n;
    else
       return n + do_something();
}

両方の関数が を呼び出している場合、ブロックから へのジャンプと への別のジャンプ、およびブロックから へのジャンプとdo_something()へのジャンプを許可する方法が必要ですが、 からへのジャンプとへのジャンプは決してありません。(または→ → ) したがって、単純な有向グラフではこれらの関係を定義するのに十分ではないように思えます...何かが足りないのかもしれません。tweedledeedo_somethingtweedledeetweedledumdo_somethingtweedledumtweedledeedo_somethingtweedledumtweedledumdo_somethingtweedledee

4

1 に答える 1

2

手順は、CFG と静的解析一般を非常に複雑にします。制御フロー グラフでルーチン呼び出しを表すには、さまざまな方法があります。

最初の一般的な解決策の 1 つは、ルーチンごとに CFG を作成し、「呼び出しノード」(たとえば、tweedledee の「CALL do_something()」に対応する基本ブロック) を 2 つのノード (実際の呼び出しブロック C と a) に分割することです。戻り値を書き込むためのブロック R。

C と呼び出されるルーチンの最初のブロックの間にエッジ (通常は特殊なタイプ) が挿入され、呼び出されるルーチンの最後のブロックと R の間に別のエッジが挿入されます。簡単な例:

void foo() { int x = bar(); }
int bar() { return 1; }

次のように変換できます。

[init::foo] ==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo]
                     ||            /\
                     \/            ||
                [init::bar] ==> [ret = 1 (end::bar)]

ルーチンからなど、bar() への別の呼び出しがある場合

void foo2() { int y = bar(); }

次のグラフが結果になる可能性があります。

 [init::foo] ==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo]
                     ||            /\
                     \/            ||
                [init::bar] ==> [ret = 1 (end::bar)]
                     /\            ||
                     ||            \/
 [init::foo2]==> [CALL bar()]  [x = RETVAL(bar())] ==> [end::foo2]

ここでの問題: このグラフにはパスがあります (例: init::foo ==> CALL bar() ==> init::bar ==> ret = 1 ==> x = RETVAL(bar()) == > end::foo2) は、プログラムでは意味がありません。これは、「プレーンな有向グラフ」で十分かどうか疑問に思うことの意味です。この問題にはさまざまなアプローチがあります。たとえば、ルーチン (ここではバー) のコピーを呼び出しごとに作成します。これは、実際の再帰がない場合にのみ役立ち、一般的にコストがかかります。静的分析では、そのようなコピーの固定数のみを使用してパスの数を「過大評価」することが役立つことがよくあります。

スライドInterprocedural Analysis Lecture Notes (Stephen Chong)は良い入門書のようです。このようなグラフの作成に関する非常に優れた本もあります。

于 2016-01-21T21:00:56.840 に答える