1

Push、Pop、Jump、If の操作を伴うスタックベースのおもちゃの言語があるとします。

プログラムがあり、その入力はおもちゃの言語です。たとえば、シーケンスを取得します

Push 1
Push 1
Pop
Pop

その場合、最大スタックは 2 になります。より複雑な例では、ブランチが使用されます。

Push 1
Push true
If   .success
Pop
Jump .continue
.success:
Push 1
Push 1
Pop
Pop
Pop
.continue:

この場合、最大スタックは 3 になります。ただし、実際にはスタック アンダーフロー エラーが発生するため、この場合のように上から下に移動して最大スタックを取得することはできません。

CFG を使用すると、グラフを作成して、基本ブロックの可能なすべてのパスをたどることができます。ただし、パスの数は n 個の頂点で急速に増加する可能性があるため、(n-1) になります。可能なパス。

私の現在のアプローチは、グラフをできるだけ単純化し、可能なパスを少なくすることです。これは機能しますが、私はそれが醜いと思います。この問題を攻撃するためのより良い (読む: より速い) 方法はありますか? アルゴリズムが生成するスタック深度が最適でなくても問題ありません。正しいスタック サイズが m の場合、私の唯一の制約は、結果 n が n >= m であることです。ここで良い結果を生み出す貪欲なアルゴリズムが利用可能でしょうか?

更新:サイクルと、すべての制御フロー マージのスタック深度が同じであるという不変条件を認識しています。問題を説明するために、簡単なおもちゃのような言葉を書き留めようと思いました。基本的に、私は決定論的なスタックベースの言語 (JVM バイトコード) を使用しているため、各操作には既知のスタックデルタがあります。

私はこの問題に対して、良い結果 (単純化された cfg) を生成する実用的な解決策を持っていることに注意してください。

4

2 に答える 2

2

あなたの言語にユーザー入力がないように見える場合、すべてのプログラムは常に同じ方法で計算するだけです。したがって、プログラムを実行し、実行中に最大スタックサイズを追跡できます。おそらくあなたが望むものではないでしょう。

パスの引数については、ジャンプはサイクルを許可することに注意してください。したがって、さらに分析しないと、サイクルは非終了とスタック オーバーフローを意味する可能性があります (つまり、各サイクルの実行後にスタック サイズが増加します)。[n 個のノードは、サイクルが存在する場合でも無限に多くのパスを意味します]

コードを実際に実行する代わりに、何らかの形式の抽象的な解釈を行うことができる場合があります。

IVlad からのコメントについて: 可能なサイクルが存在するため、単にプッシュをカウントするのは間違っています。

ただし、if ステートメントのセマンティクスが不明なので、これも役立つ可能性があります。if ステートメントのラベルは前方ラベルのみであると仮定します (つまり、コード内でジャンプバックすることはできません)。その場合、パスカウントの引数が復活します。実際には、結果の CFG はツリー (コードをコピーしない場合は DAG) になります。その場合、プッシュ数をボトムアップで計算し、if ステートメントの場合は両方のブランチの最大プッシュ数を取得することで、概算のカウントを行うことができます。これはまだ最適な正しい結果ではありませんが、push ステートメントの単純なカウントよりも優れた概算が得られます。

于 2010-05-03T10:15:01.530 に答える
1

通常、ジャンプとループに対してスタックの深さを不変にする必要があります。

これは、すべてのノードについて、すべての受信エッジが同じスタック深度を持つ必要があることを意味します。これにより、バックエッジは計算済みの命令のスタック深度を変更できなくなるため、CFG のウォークが大幅に簡素化されます。

これは、制限されたスタックの深さの要件でもあります。強制しないと、コード内のループが増加します。

考慮すべきもう 1 つのことは、すべてのオペコードのスタック効果を決定論的にすることです。非決定的なオペコードの例は次のとおりです: POP IF TopOfStack == 0.

編集：

オペコードの決定論的なセットとスタック深度の不変条件がある場合は、プログラムのすべての可能なパスにアクセスする必要はありません。最大スタック深度を決定するには、CFG を介して DFS/BFS を実行するだけで十分です。これは (命令の量に応じて) 線形時間で実行できますが、高速ではありません。

現在の基本ブロックの出力エッジが指している基本ブロックがまだ評価される必要があるかどうかを評価することは、パフォーマンスに関連するべきではありません。最悪の場合でも、すべての命令は でありIF、評価するエッジは 2*N しかありません。

于 2010-05-03T10:19:02.603 に答える