0

私は有向グラフを持っています。ノード N が常に上位ノード T のパス内にあるかどうかを知りたいです。それを確認する方法は、エントリ ノードから開始して深さ優先検索を実行することです。いずれかのパスで、ノード N がノード T の前に検出された場合、常にそのパスにあるとは限りません。

例として、添付の画像では、エントリ ノードはentry_0_CC_FC、上位ノードはif_end_0_CC_FC、ノード N はland.lhs.true26_0_CC_FCです。

しかし、アルゴリズムが無限ループに陥っています。時間がかかりすぎているか、行き詰まっているか、よくわかりません。ちなみに、このグラフには119個のブロックがあります。これがコードです。無限ループに陥る可能性のある問題を確認できますか。

void CheckIfNotAlwaysInPath(bool& violation, BasicBlock* BS, 
  BasicBlock* BT, BasicBlock* BN, set<BasicBlock*> visited)
{
    int i;

    // If already visited
    if ( visited.find( BS ) != visited.end() ) // If already had visited
        return;

    visited.insert(BS);

    if ( BS == BN )
    {
        if ( visited.find( BT ) == visited.end() )
            violation = true;
        return;
    }

    if ( isa<ReturnInst>(BS->getTerminator()) )
        return;
    if ( BS->getTerminator()->getNumSuccessors() == 0 )
        return;


    for( i = 0; i < BS->getTerminator()->getNumSuccessors(); i++ )
    {
        if ( visited.find( BS->getTerminator()->getSuccessor(i) ) == visited.end() )
            CheckIfNotAlwaysInPath(violation, BS->getTerminator()->getSuccessor(i), BT, BN, visited);
    }
}

ここに画像の説明を入力.

4

1 に答える 1

0

グラフでフィードバックを確認します。次に、コード内の参照機能ブロック/ステート マシンを確認します。上段のif.end531_0_CC_FCまでは大丈夫なはずです。その後、 for.body ブロックまたは for.cond675.loopexit_0_cc_FC でエラーが発生しやすくなる可能性があります...または他のループバックの一部。

私の最初の推測は for.cond675.loopexit_0_cc_FC から for.body.688.lr.ph_0_CC_FC へのループバックでしょう。

于 2012-08-30T09:47:35.560 に答える