2

我有一种情况，必须在访问节点之前访问节点的前任。所以，这里是代码：

nodeQ.Enqueue(rootNode);

while(!nodeQ.Empty())
{
    node = nodeQ.Dequeue();
    ForEach(var predecessor in node.Predecessors)
    {
        if(predecessor is not visited)
        {
            //put the node back into the queue
            nodeQ.Enqueue(node);
            skip = true;
            break;
        }
    }
    if(skip)continue;

    Visit(node)

    foreach(var successor in node.Successors)
    {
        if(successor is not already visited)
        {
            nodeQ.Enqueue(successor);
        }
    }   
}

上述算法适用于没有循环的线性控制流图（阅读：循环）正常的 BFS 遍历并不能确保在节点本身之前访问节点的前任。

示例 CFG： 控制流图。 根：0

正常的 BFS 遍历将是： 0, 1 , 2 , 3 , 12, 4, 5, 9, 10, 11, 8 , 6, 7

但是，我希望顺序为 0、1、2、3、4、5、6、7、8、9、10、11、12，这可以通过我的代码中显示的小修改来实现开始。

但是，当涉及到循环时，此修改将导致无休止地跳过块。

可能失败的示例 CFG： 带循环的控制流图

在这种情况下，我的代码将无休止地推迟对节点 1、2、3 的访问

因此，我一直在寻找一种遍历方式，以确保在节点本身之前访问节点的前任节点（带或不带循环）的 CFG 节点的遍历。

我正在考虑识别后端，即检查节点 N 是否是其前任 P 的支配者，然后 P-> N 是后端并且不需要将 P 视为节点 N 的前身。但这似乎不是作为节点 N 工作并不总是必须支配节点 P。

4

2 回答 2

2

我解决了这个问题，首先找到 Dominators，创建一个 Dominator Tree，然后在 DFS pre-order 中遍历 Tree。

于 2015-07-16T08:19:03.903 回答
0

对于遇到此问题并寻求 CFG 和支配者计算指导的其他人，查看IBM WALA 工具可能会很有用。我在这里为我的特定任务找到了很多有用的信息。

于 2016-08-15T17:45:23.607 回答