0

我想了解为节点构建 Ф 函数的通用原则。我在允许构建 Ф 函数的图中阅读了“优势边界 (DF) ”关系。这是一个简单代码片段的控制流图示例： 控制流图

让我们考虑 DF 的定义：

DF is a set of nodes w such that x dominates predecessor of w, but x does not strictly dominate w

好的，这是我对这个定义的理解。让我们考虑一下：DF(B1) = { B3, B5, B6, B7 } 因为：

dom(B1, B2) & !strictly_dom(B1, B3) & is_predecessor(B2, B3);
dom(B1, B3) & !strictly_dom(B1, B5) & is_predecessor(B3, B5);
dom(B1, B3) & !strictly_dom(B1, B6) & is_predecessor(B3, B6); 
dom(B1, B6) & !strictly_dom(B1, B7) & is_predecessor(B6, B7);

这是对DF的正确理解吗？请给我更详细的解释好吗？

4

1 回答 1

2

在构建 SSA 表单的上下文中，了解优势边界的作用的最佳方法是识别图中的连接点。这是人们在纸上构建 SSA 表格时使用的直觉。

如果您的控制流图中的一个节点的前任少于 2 个，那么它将不会位于任何节点的优势边界 - 因为它不能成为竞争定义的合并点。“优势边界”的概念正是某个节点的“优势”结束的节点（即，它的定义可能不再是主导的；肯定达到这些点的节点，没有来自其他替代路径的竞争，其他路径定义可能会出现，因此会达到相同的点）。

因此，只需查看您的控制流图，我们就可以看到唯一具有至少 2 个前驱节点的节点是B2和B7。因此，这些节点将构成某些节点的边界。

你必须诉诸支配地位的定义，才能知道谁的边界是由这些节点组成的。根据定义，每个节点都主宰自己。因此，如果我们查看块的前身B2和B7，我们可以消除那些不严格支配这些节点的人。

因为B7，我们有那个B5并且B6支配了一个前身B7（即他们自己）。但是，它们并不严格支配B7（实际上，它们根本不支配B7）。事实上，它们都在为达到的定义而竞争支配地位，这B7正是为什么两者都具有支配边界B5的原因。直观地，引用您的原始图，您可以看到这两个前辈都定义了和，那么当控制流到达 时，您使用谁的定义？你不能说，因为你可以通过任何一个到达。所以，你会放置 phi 节点：和B6{B7}jkB7B7j <- ϕ((j, B5), (j, B6))k <- ϕ((k, B5), (k, B6)). 跟踪您正在谈论的每个变量定义的来源对于确定执行重命名时使用的（重）名称非常重要（放置 phi 节点，然后重命名）。

因为B2,B7是一个前身并且根据定义支配自己。但是，它并没有严格控制B2，因为它与入口块中的初始定义竞争，B1. 因此，您还需要放置 phi 节点来合并这些定义：j <- ϕ((j, B1), (j, B7)), k <- ϕ((k, B1), (k, B7)). i请注意，因为i从未重新定义，因此没有相互竞争的定义。据我所知，您可以不断地将i的值 ,传播1到其使用站点并删除定义。

我推荐阅读 Cooper 等人的“A Simple, Fast Dominance Algorithm”。（https://www.cs.rice.edu/~keith/EMBED/dom.pdf），他们给出了一个简单的算法来计算支配树，以及一个直观的算法（图 5），通过向上走来计算边界支配树。

您最好直观地考虑优势边界；哪些相互竞争的定义可以达到一个连接点？在DF(B1)你给出的建议中，你有那个B3 ∈ DF(B1)。这不可能是对的。原因是唯一可以达到B3的定义是离开的定义B2（它的单一前身）。但是，输入的定义是B2有竞争力的，因为您可以B2通过来自B7or到达B1（因此，如上所述，B2必须有一个领先的 phi 节点 - 由 phi 节点创建的定义最终将在B3没有竞争的情况下到达）。

于 2021-11-01T13:58:59.353 回答