optimizationcompiler-constructioncompiler-optimizationregister-allocationdataflow-diagram

Live variable analysis , is my explanation correct?

As stackexchange have not more tags about compiler tags , so I'm posting here , this question .

A variable x is said to be live at a statement Si in a program if the following three conditions hold simultaneously :

1. There exists a statement Sj that uses x
2. There is a path from Si to Sj in the flow
   graph corresponding to the program
3. The path has no intervening assignment to x 
   including at Si and Sj

enter image description here

The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are

  1. p, s, u
  2. r, s, u
  3. r, u
  4. q, v

I try to explain :

As the wikipedia says "Stated simply: a variable is live if it holds a value that may be needed in the future."

As per the definition given in question, a variable is live if it is used in future before any new assignment. Block 2 has ‘r’ and ‘v’ both as live variables. as they are used in block 4 before any new value assinged to them. Note that variable ‘u’ is not live in block 2 as ‘u’ is assigned a new value in block 1 before it is used in block 3. Variables ‘p’, ‘s’ and ‘q’ are also not live in block 2 due to same reason. Block 3 has only ‘r’ as live variable as every other variable is assigned a new value before use.

Another explanation given as :

Only r.

p, s and u are assigned to in 1 and there is no intermediate use of them before that. Hence p, s and u are not live in both 2 and 3. q is assigned to in 4 and hence is not live in both 2 and 3.

v is live at 3 but not at 2. Only r is live at both 2 and 3.

But official GATE key said both r and u.

Solution

  • I see two things that are probably at least part of your confusion.

    First, in the list of conditions for live variables, there is no restriction stating that Si != Sj, so this makes the definitions a little imprecise in my mind.

    The second is your assertion "Note that variable ‘u’ is not live in block 2 as ‘u’ is assigned a new value in block 1 before it is used in block 3."

    The way I would look at this would be this:

    1. Upon entry into block 2, before the statement v = r + u is executed (imagine a no-op empty statement inserted as the entry to each block, and another as the exit from the block), then both r and u must be live, because there exists an upcoming statement that uses both, and there is a path in the code from the entry to that statement that contains no intermediate assignments to either. Rather than imagining these extra empty statements, using the original semantics of the definitions, then we're just talking about the case where Si == Sj, because both refer to the v = r + u statement - there is trivially a path from a statement to itself containing no additional assignments in that sense. I find it easier to think about it with the extra empty entry and exit statements, though.

    2. After the execution of v = r + u, however, at the imaginary block exit empty statement, it is now safe to consider u as not live (alternatively, dead), because nothing in block 4 uses it, and it's reassigned in block 1 before it's ever used again in either block 2 or 3.

    So, part of the confusion seems to be thinking of whether a variable is live in a particular block, which doesn't really fit with the definitions - you need to think about whether a variable is live at the point of a particular statement. You could make the case that the variable u is both alive and dead in block 2, depending on whether you look at it before execution of the lone statement, or after...