graph - 弦图和 SSA 形式程序

Question

我的问题是为什么每个 SSA 表单程序默认都对应一个弦图。维基百科将弦图定义为

弦图是其中四个或更多顶点的所有循环都具有弦的图，弦是不属于循环但连接循环的两个顶点的边

这是一个简单的示例，取自我遵循的一些讲义，以了解 SSA 表单对注册分配的好处。作者写道：

[...] 以下程序和相应的弦图：

第一：我不明白这个图表是如何和弦的。我意识到该程序不是 SSA 形式。然后作者将其转换为SSA形式得到这个干扰图

但是我再一次看不出这是一个弦图，或者第一个图如何与后面的任何图相关。

所有这些都使得理解 SSA 程序如何产生弦交点图变得非常困难。

以下是我研究过的一些来源：

score 1 · Accepted Answer

关于您在讲义第 6 节中列出的程序：

我不明白这个图表是如何和弦的。我意识到该程序不是 SSA 形式。

您是正确的，原始程序不是 SSA 形式。您也有理由对为什么它的“弦图”是弦图感到困惑：它不是. 作者犯了一个小错误。他们在参考第一个程序时写“弦图”的地方，他们的意思是写“干涉图”。

您所指的第二张图很简单，因为它不包含任何循环。记住您给出的弦图的定义：

弦图是其中四个或更多顶点的所有循环都有一个弦，这是一条不属于循环但连接循环的两个顶点的边

如果有零个周期，那么所有这些周期都包含一个和弦。

1 回答 1