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 回答