弦图和 SSA 形式程序

Chordal graphs and SSA form programs

我的问题是为什么每个SSA形式的程序默认对应一个弦图。 Wikipedia defines 弦图为

a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle

这是一个取自 some lecture notes 的简单示例，我为了了解 SSA 形式注册分配的好处而关注。作者写道：

[...] the following program and corresponding chordal graph:

第一：我不明白这个图怎么是弦的。我意识到该程序不是 SSA 形式。然后作者将其转化为SSA形式得到这张干涉图

但是我还是看不出这是一个弦图，也看不出第一个图与后面的图有什么关系。

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

以下是我调查过的一些来源：

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

I don't understand how is this graph is chordal. I realize that the program is not in SSA form.

您说得对，原始程序不是 SSA 格式。您也有理由对为什么它的 "chordal graph" 是和弦感到困惑：它不是 。作者犯了一个小错误。他们在第一个程序中写 "chordal graph" 的地方，他们 的意思是 写 "interference graph".

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

a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle

如果有零个循环，那么空洞地所有个循环都包含一个和弦。

弦图和 SSA 形式程序

Chordal graphs and SSA form programs

graph

compiler-optimization

register-allocation

ssa