Skip to main content

Def-Use

Topic appears in the following WE1 Exams:

  • 2021 07 26 Q3 (3 points)
  • 2021 01 13 Q2.1 (3 points) Mixed def-use and symbolic execution

Therefore it appears in 33% of the WE1 exams and it is worth 3 points on average.

Summary

Identify every time a variable is defined (modified) and used with that version, for example:

1 int i, k = 0;
2 i = k;
3 while (i<10)
4 i++;

The def-use pairs for k are <1, 2> while the ones for i are <2, 3>, <2, 4>, <4, 3>, <4, 4>.

A more complex example:

0  int foo() {
1    x = input();
2    while (x > 0) {
3        y = 2 * x;
4      if (x > 10)
5        y = x - 1;
6      else
7        x = x + 2;
8      x = x - 1;
9    }
10   x = x - 1;
11   return x;
12 }

A control flow graph could be useful:

The identified def-use pairs for x are:

  • <1, 2> <1, 3> <1, 4> <1, 5> <1, 7> <1, 8> <1, 10>
  • <7,8>
  • <8, 2> <8, 3> <8, 4> <8, 5> <8, 7> <8, 8> <8, 10>
  • <10, 11>

While we see for y:

  • <3,?> <5, ?>

So y is defined but never used.

Past exam exercise

2021 07 26 Q3 (3 points)

Identify the def-use pairs for program my_func and say whether they highlight anything unusual.

0  int my_func (int x, int y) {
1      int z, k, res;
2      if (x <= 0 || y <= 0)
3          return -1;
4      z = x;
5      k = y;
6      while (x != y) {
7          if (x > y)
8              x = x - y;
9          else y = y - x; }
10     if (z % x == 0) {
11         res = 1;
12         z = 1; }
13     else z = 0;
14 	   return res; }
VariableDef-Use pairs
x<0,2>, <0,4>, <0,6>, <0,7>, <0,8>, <0,9>, <0,10>
<8,6>, <8,7>,<8,8>, <8,9>, <8,10>
y<0,2>, <0,5>, <0,6>, <0,7>, <0,8>, <0,9>
<9,6>, <9,7>,<9,8>, <9,9>
z<4, 10>, <12,?>, <13,?>
k<5, ?>
res<?,14>, <11,14>

Variable z is set at lines 12 and 13, but it is then never used, which is not necessarily a problem, though it is not ideal. Similarly, variable k is set at line 5, but it is never used. Variable res is potentially used at line 14 without being initialized. However, an inspection of the paths that lead to line 14 show that line 13 is actually never executed (i.e., the condition at line 10 is always true), so variable res will actually be always initialized when it is used.

2021 01 13 Q2.1 (3 points) Mixed def-use and symbolic execution

0  int func (int) {
1      int k, i, y;
2      int res = 0;
3      if (x < 1)
4          return res;
5      if (x % 2 != 0)
6          return res;
7      y = x;
8      i = 0;
9      while (i <= 10 && y % 4 != 0)
10         y = y*y;
11         i = i + 1;
12     }
13     if (i > 5
14 	       res = k;
15     else
16         res = res + 1;
17     return res;

Point A: identify pairs and highlight unusual

Identify the def-use pairs for program func and say whether they highlight anything unusual.

Back to top