如何为控制流图建立优势边界？
How to build dominance frontier for control flow graph?
我想了解为节点构建 Ф 函数的通用原则是什么。
我在允许构建 Ф 函数的图中读到“支配边界 (DF)”关系。下面是一个简单代码片段的控制流图示例：
control-flow-graph
让我们考虑 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对吗？可以给我更详细的解释吗？
在构建 SSA 形式的上下文中理解优势边界的作用的最佳方法是识别图中的连接点。这是人们在纸上构建 SSA 表格时使用的直觉。
如果您的控制流图中的一个节点有少于 2 个前任节点，那么它不会在任何节点的支配边界中 - 因为它不能成为竞争定义的合并点。 “支配边界”的概念恰恰是某个节点的“支配”结束的节点（即它的定义可能不再是主导的定义；那些明确到达这些点的节点，没有来自其他替代路径的竞争定义可能会出现，因此会达到相同的点）。
因此，仅通过查看您的控制流图，我们可以看到唯一具有至少 2 个前驱的节点是 B2 和 B7。因此，这些节点将构成某些节点的边界。
你必须求助于支配的定义才能知道这些节点组成了谁的边界。根据定义，每个节点都支配自己。因此，如果我们查看块 B2 和 B7 的前任，我们可以消除那些不严格控制这些节点的块。
对于B7，我们有B5和B6支配B7的前身（即他们自己）。然而，它们并不严格地支配B7（事实上，它们根本不支配B7）。事实上，他们都在争夺 B7 定义的支配地位，这正是 B5 和 B6 的支配边界都是 {B7} 的原因。直观地，引用你的原图，你可以看到这两位前辈都定义了j和k，那么当控制流到达B7时，你使用谁的定义？您无法分辨，因为您可以通过其中任何一个到达 B7。因此，您将放置 phi 节点：j <- ϕ((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 等人的“一种简单、快速的支配算法”。 (https://www.cs.rice.edu/~keith/EMBED/dom.pdf)，他们给出了一个计算支配树的简单算法，以及一个直观的算法（图 5），用于通过沿着支配树向上移动来计算边界。
您最好凭直觉思考支配边界；哪些竞争定义可以到达连接点？在你给出的建议 DF(B1) 中，你有那个 B3 ∈ DF(B1)。这不可能是对的。原因是唯一可以达到 B3 的定义是那些离开 B2（它的前身）的定义。但是，输入 B2 的定义具有竞争力，因为您可以从 B7 或 B1 到达 B2（因此，如上所述，B2 必须有一个领先的 phi 节点 - phi 节点创建的定义最终将在没有竞争的情况下达到 B3。
我想了解为节点构建 Ф 函数的通用原则是什么。 我在允许构建 Ф 函数的图中读到“支配边界 (DF)”关系。下面是一个简单代码片段的控制流图示例： control-flow-graph
让我们考虑 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对吗？可以给我更详细的解释吗？
在构建 SSA 形式的上下文中理解优势边界的作用的最佳方法是识别图中的连接点。这是人们在纸上构建 SSA 表格时使用的直觉。
如果您的控制流图中的一个节点有少于 2 个前任节点，那么它不会在任何节点的支配边界中 - 因为它不能成为竞争定义的合并点。 “支配边界”的概念恰恰是某个节点的“支配”结束的节点（即它的定义可能不再是主导的定义；那些明确到达这些点的节点，没有来自其他替代路径的竞争定义可能会出现，因此会达到相同的点）。
因此，仅通过查看您的控制流图，我们可以看到唯一具有至少 2 个前驱的节点是 B2 和 B7。因此，这些节点将构成某些节点的边界。
你必须求助于支配的定义才能知道这些节点组成了谁的边界。根据定义，每个节点都支配自己。因此，如果我们查看块 B2 和 B7 的前任，我们可以消除那些不严格控制这些节点的块。
对于B7，我们有B5和B6支配B7的前身（即他们自己）。然而，它们并不严格地支配B7（事实上，它们根本不支配B7）。事实上，他们都在争夺 B7 定义的支配地位，这正是 B5 和 B6 的支配边界都是 {B7} 的原因。直观地，引用你的原图，你可以看到这两位前辈都定义了j和k，那么当控制流到达B7时，你使用谁的定义？您无法分辨，因为您可以通过其中任何一个到达 B7。因此，您将放置 phi 节点：j <- ϕ((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 等人的“一种简单、快速的支配算法”。 (https://www.cs.rice.edu/~keith/EMBED/dom.pdf)，他们给出了一个计算支配树的简单算法，以及一个直观的算法（图 5），用于通过沿着支配树向上移动来计算边界。
您最好凭直觉思考支配边界；哪些竞争定义可以到达连接点？在你给出的建议 DF(B1) 中，你有那个 B3 ∈ DF(B1)。这不可能是对的。原因是唯一可以达到 B3 的定义是那些离开 B2（它的前身）的定义。但是，输入 B2 的定义具有竞争力，因为您可以从 B7 或 B1 到达 B2（因此，如上所述，B2 必须有一个领先的 phi 节点 - phi 节点创建的定义最终将在没有竞争的情况下达到 B3。