0
$\begingroup$

I'm currently preparing for an exam in compiler construction. The course is mainly about optimization in the backend of the compiler. For the optimization we have to do data flow analysis by hand. In one example I do not understand how gen and kill sets are determined. My solutions differ a lot although I stuck to the transfer functions for reaching definitions. The analysis is structured by base blocks.

Code:

1: i=2;
L1:
2: if( i <= 220 ) goto L4;
L2:
3: t4 = i*8;
4: t5 = base() + t4;
5: t6 = t4 + j;
6: j = j+1;
7: if( t6 >= 120 ) goto L3;
8: t5 = t6 + t4;
L3:
9: i = t5 + 1;
10: goto L1;
L4:
11: return i;

Base Blocks:

  • BB1 = {1}
    • me: gen={1} kill={2,3}
    • solution: gen={1} kill={2,3}
  • BB2 = {2}
    • me: gen={} kill={}
    • solution: gen={2} kill={}
  • BB3 = {3, 4, 5, 6, 7}
    • me: gen={3,4,5,6} kill={4,5,6,8,9}
    • solution: gen={3,4,7} kill={5,6,8,9} ???
  • BB4 = {8}
    • me: gen={8} kill={4,9}
    • solution: gen={8} kill={9}
  • BB5 = {9, 10}
    • me: gen={9} kill={3}
    • solution: gen={9} kill={2,3}
  • BB6 = {11}
    • me: gen={} kill={}
    • solution: gen={} kill={}

The gen and kill set are used to compute the in and out set. In and out set are then used to compute reaching definitions.

Can somebody explain to me why the sets differ by so much?

$\endgroup$
  • $\begingroup$ Perhaps you could explain what gen and kill are in your context? $\endgroup$ – Yuval Filmus Mar 30 '18 at 11:56
  • $\begingroup$ The generate set is the set of definitions generated by a base block. The kill set is the set of definitions destroyed by the base block. $\endgroup$ – mdxg Mar 30 '18 at 12:08
  • $\begingroup$ What are these sets supposed to represent? Are you trying to compute reaching definitions? Live variables? Something else? Try adding as much context as possible. $\endgroup$ – Yuval Filmus Mar 30 '18 at 12:22
  • $\begingroup$ Oh sorry. Yes the gen and kill set are used to compute in and out set. In and out set are then used to compute reaching definitions $\endgroup$ – mdxg Mar 30 '18 at 12:23
  • $\begingroup$ Please edit the question to incorporate that information into the question, so people don't need to read the comments to understand what you are asking. Thanks! $\endgroup$ – D.W. Mar 30 '18 at 16:28

Your Answer

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

Browse other questions tagged or ask your own question.