read- and write-sets

Question

Hello,

I've got a question regarding read- and write-sets of cmd programs.

Consider the following program:

0000 : a := 2
0001 : b := 3
0002 : t0 := c < a
0003 : if t0 goto 7

If we see those four lines as one Basic Block, I would compute the read-set as read{a,c,t0} and the write-set as write{a,b,t0}. I've found out that my read-set is wrong and should instead be read{c}, but I do not understand why a and t0 are not part of the set since they - in my opinion - get read in lines 2 and 3 (also according to lecture slide 47)

I thought that maybe temp vars just like t0 is one are never in read-sets, but then I still do not understand why a is not part of the set.

Thank you for any help!

Answer 1

Interesting question! The short answer is that you just considered which variables are read and written in the basic block, but you did not consider whether the values read are those written in the same basic block or before that basic block.

For example, if you consider your program as the following MiniC program 

        nat a,b,c,d;
        bool t0;
      
        thread t {
         a = 2;
         b = 3;
         t0 = c < a;
         if(t0) {
             d = 1;
            } else {
                d = 2;
            }
        }

you will get almost the same CMD program

    -----------------------------------
    0000 : a := 2
    0001 : b := 3
    0002 : t0 := c < a
    0003 : _t0 := 0 == t0
    0004 : if _t0 goto 7
    -----------------------------------
    0005 : d := 1
    0006 : goto 8
    -----------------------------------
    0007 : d := 2
    -----------------------------------
    0008 : sync
    -----------------------------------

and the first basic block is only reading variable c as you can see in the control flow graph 

To get these results from the MiniC teaching tool, use the following options:

•     translate threads to Abacus assembler
•     translate to CMD program (requires translation to Abacus assembler)
•     print control flow graph (requires translation to Abacus assembler)

Why is that so? Variable a is read in line 2, but the value read there is the value 2 which has been assigned in line 0, and it is therefore not the value a had before the basic block. If a would not be needed in the following, you could replace the occurrences of a in lines 0 and 2 by another temporary variable like t1. 

Same way t0 is read, but it is the value assigned in the same basic block. 

Therefore it is just the variable c whose value before the basic block is needed in the basic block. 

This distinction has nothing to do with temporary variables like t0. They may also belong to read/write sets of a basic block.

Comments

Thank you very much for the detailed answer.

To be honest, I have some problems using the MiniC teaching tool. For example for the current exercise sheet in rosy, the programs are given in cmd but the tool requires MiniC code.

Nevertheless, I now understand how one computes read and write-sets, thank you!

---

I understand. However, you should be able to solve the exercise also without any tool, and second, it is not so difficult to generate an almost "corresponding" MiniC program. To show that I intensionally have used the MiniC compiler for the explanations above.