Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes
Hi, i don't unserstand what  live() (may live) means in a basic block. I understand its meaning per line, but not per basic block. Is it the union  or the intersection af all Maylives per line ? (would not make sense to me ,but i dont know ).

(Eine Antwort auf deutsch wäre auch ok )
in * TF "Emb. Sys. and Rob." by (550 points)

1 Answer

0 votes

Short answer: Whether a variable is live or not always refers to a state (=line) of the program. For a basic block, you may therefore distinguish between the variables which are live at the beginning and at the end of the basic block (which are two particular lines of code in that basic block).

Longer answer: In general, a variable is live in a state of a computation path if the value of the variable will be read later on that path. Hence, we know that we should not overwrite that value at the moment, since the value is needed later on.

It is easy to explain liveness on a single computation path. However, compilers have to consider all potential computation paths at compile time. We therefore have to pessimistically assume that all paths are possible even though in reality some are not possible. 

For instance, consider the following program

    if(a) {
        if(a|b) {
            S1;
        } else {
            S2;
        }

S2 cannot be reached in this program, but the dataflow analysis does still consider it to be reachable (since such cases should not occur). We therefore can distinguish for a variable whether it may/must be live in that there may/must be a path where it is live at this point.

    if(a) {
        x = 2;
        if(a|b) {
            y = 3;
        } else {
            z = x+1;
        }

The program is first translated to the following internal representation where basic blocks are distinguished by lines:

    -----------------------------------
    0000 : _t0 := 0 == a
    0001 : if _t0 goto 10
    -----------------------------------
    0002 : x := 2
    0003 : _t1 := a | b
    0004 : _t2 := 0 == _t1
    0005 : if _t2 goto 8
    -----------------------------------
    0006 : y := 3
    0007 : goto 9
    -----------------------------------
    0008 : z := x + 1
    -----------------------------------
    0009 : goto 10
    -----------------------------------
    0010 : end
    -----------------------------------

See also the CFG of this example below:

We can now compute the following sets of live variables (MustLive ⊆ MayLive): 

    0000 : {a} ⊆ {a,b}
    0001 : {_t0} ⊆ {_t0,a,b}
    0002 : {a,b} ⊆ {a,b}
    0003 : {a,b} ⊆ {a,b,x}
    0004 : {_t1} ⊆ {_t1,x}
    0005 : {_t2} ⊆ {_t2,x}
    0006 : {} ⊆ {}
    0007 : {} ⊆ {}
    0008 : {x} ⊆ {x}
    0009 : {} ⊆ {}
    0010 : {} ⊆ {}

As you can see, variable x becomes may-live after its assignment in line 2, since there is a computation path 2->3->4->5->8->9->10 where it is read later on, namely in line 8. Variable x is however not must-live after its assignment, since there is another path 2->3->4->5->6->7->9->10 where it will not be read later on.

Considering the basic block consisting of lines 2,3,4,5, we can say that x is may-live at the end of the basic block (in line 5), but not at its beginning (in line 2).

Having written this, let me also add that people usually mean may-live if they just talk about liveness of variables. It is an superset of the variables that are really read in the following.

by (170k points)
So if x is may-live in line 5 but not in line 2, does that now mean x is may-live for the basic block 2-5 or not?
Reading the question twice, and having seen a related question, I now see what you are really asking for. Find your answer for the related question https://q2a.cs.uni-kl.de/1951/read-and-write-sets
Imprint | Privacy Policy
...