I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code.
We were taught to first divide the code into blocks (according to GOTOs), and draw lines that represent a variables lifeline.
I am not sure on a = a op c (that is, same variable is both read and assigned in same command). I am following this examples, which sadly, has a typo that makes it hard to understand this very end-case. Here, a=a+b+c, so a is both used and assigned.
I have initially treated that with no special care (logic being "i know some interpreters can read RHS before LHS"), but now I am not quite sure.

My question really:
I think perhaps the example should have mark a's line starting from the read() command, end it in the a=a+b+c but also re-draw the line. This way an extra register will temporarily hold a's value before assigning it back to a. Is that correct? example: interference graph


You are right. The lifetime of a could be split into two spans. That said, how would you notate that in the interference graph? That is, how would you notate that one variable only interfered with one span of another variable's lifetime?

This is one of the motivations for Static Single Assignment (SSA) form. By having each assignment write to a "new" variable, you're never in the situation where a variable's lifetime is in potentially disjoint spans. You also have a name for each span of a (source-level) variable's lifetime, so the interference graph can be finer grained.

It is, however, safe to treat the lifetimes as starting at the first assignments and ending at the last uses. So while it may not be optimal to give each variable one single span of lifetime, it will never cause incorrect behavior.

  • $\begingroup$ So just to be sure I understood your answer: What I should do is in fact notate "a" of "a=read" as "a1", and the "a" of "a=a+b+c" to "a2=a1+b+c"? $\endgroup$ – yoad w Jan 13 '18 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.