[SOLVED] Chordal graphs and SSA form programs

Chordal graphs and SSA form programs

My question is about why every SSA form program corresponds to a chordal graph by default. Wikipedia defines chordal graphs as

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

Here's a simple example taken from some lecture notes I was following for the sake of understanding the benefit of SSA form to register allocation. The authors write:

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

First: I don't understand how is this graph is chordal. I realize that the program is not in SSA form. Then the author converts it to SSA form to get this interference graph

But again I can't see how this is a chordal graph or how the first graph is related to any of the later graphs.

All of this has made it very difficult to understand how SSA programs give rise to chordal intersection graphs.

Here's some of the sources that I've looked into:

Solution

Regarding the program you listed from Section 6 of the lecture notes:

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

You're correct that the original program is not in SSA form. You're also justifiably confused as to why its "chordal graph" is chordal: it isn't. The authors have made a small mistake. Where they wrote "chordal graph" in reference to that first program, they meant to write "interference graph".

This second graph you're referring to is trivially chordal because it doesn't contain any cycles. Remember the definition of a chordal graph you gave:

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

If there are zero cycles, then vacuously all of those cycles contain a chord.