3

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:

confusing example

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

post-ssa example 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:

  1. https://pdfs.semanticscholar.org/db6b/c047856bee4eb4e7d04f1b934864dca4b065.pdf?_ga=2.67844629.501567003.1543477413-723933249.1539714051

  2. https://homepages.dcc.ufmg.br/~fernando/publications/papers/APLAS05.pdf

  3. http://compilers.cs.uni-saarland.de/papers/ifg_ssa.pdf

  4. https://homepages.dcc.ufmg.br/~fernando/classes/dcc888/ementa/slides/SSABasedRA.pdf

Alex Reinking
  • 16,724
  • 5
  • 52
  • 86
yazan daba
  • 219
  • 5
  • 11

1 Answers1

1

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.

Alex Reinking
  • 16,724
  • 5
  • 52
  • 86
  • thank you for the answer but I didn't get this line (If there are zero cycles, then vacuously all of those cycles contain a chord.)correctly can you please clarify it more @AlexReinking – yazan daba Dec 04 '18 at 21:00
  • I mean what I've understand is that for a graph to be chordal there must be **at least** four vertices that creates cycle and there's an edge between two vertices from the cycle but not part of it (like the first image) , so if you can please clarify what I've got wrong about the definition of chordal graph @AlexReinking – yazan daba Dec 04 '18 at 21:17
  • No, that's not right. If a graph has no cycles containing four or more vertices then it is chordal by default. All graphs of fewer than 4 vertices are chordal for that reason. – Alex Reinking Dec 04 '18 at 21:23
  • Now I get it what the definition is trying to say is that if there' a graph with four vertices and those four vertices form a cycle then there must be a chord to call this graph chordal, right ? – yazan daba Dec 04 '18 at 21:36
  • More like if a graph has no cycles of length 4 or more OR if every cycle of length 4 or more has a chord, then the graph is chordal. – Alex Reinking Dec 04 '18 at 21:38
  • Sir you made my day, thank you so much for your efforts and time that is the answer that I was looking for – yazan daba Dec 04 '18 at 21:40
  • Happy to help :) – Alex Reinking Dec 04 '18 at 21:41