CS 243 Assignment 1Assignment 1Dataflow AnalysisDue: January 25, 11:00 amThis is a written assignment, every student must hand in his or her homework.Bring your homework to class on January 25. SCPD students may submit theirhomework by e-mail via [email protected] or give your homeworkto the courier.1. Compute the available expressions ( Chapt e r 9.2.6 in ALSU) on entry and exitfor each basic block in the flow graph below.entryt = x+y; c = a+b;b = t+c;a = t+c;b = 4;c = t+c;a = x+y;exit2. Is the following a meet operator? Please answer yes or no. No explanation isnecessary.(a) Maximum value (on integers)(b) Product (on integers)(c) Addition (on integers)(d) Product mod 2 (on the set {0, 1})(e) Addition mod 2 (on the set {0, 1})(f) The GCD function (on integers)Winter 2011/2012 page 1 of 3CS 243 Assignment 13. We say that a program point p belongs to a live range of a definition d u=x+yiff the value assigned to u in definiti on d may be accessed by using variable u atpoint p, for some path in the flow graph starting at p. Consider for example thecode fragme nt below:a = x + y;b0z = a;b1a = 0;b2a = a + 1;b3b = a + z;b4exitThe live range of the definition ‘a = x + y’ at point entrypoi nt(b0) is{exitpoint(b0), entrypoint(b1), exitpoint(b1), entrypoint(b3)}. Similarly, the liverange of the definition ‘a = a + 1’ at point entrypoint(b3) is {exitpoint(b3),entrypoint(b4)}.This concept of live ranges can be used to increase flexibility in register assign-ment. For e x amp l e, the live ranges of the definition s of a in b0and b3do notintersect at any points, so it may be possible to use same r egi s te r s to hold thesetwo values.Describe an algorithm to find the live range of every definition in a program.Winter 2011/2012 page 2 of 3CS 243 Assignment 14. Define a compiler analysis that generates two kinds of warnings to he l p program-mers detect uninitialized variables in their programs.(a) Warning I is issued on each use of a variable that may potentially be unini-tialized.(b) Warning II is issued on each u se of a variable that is definitely uninitial i z e d.You can define one or more data flow problems to solve this problem. Stateclearly how you generate the warnings. For each data flow analysis defined, fillin the following table:Direction (forward or backward)Lattice valuesMeaning of lattice valuesMeet operatorTopBottomBoundary conditionsInitial interior valuesTransfer functions5. This question asks you to think about how changes to the ini ti al value s in a dataflow analy si s can affect the result. Recall that an answer to a data flow problemis considered “safe” if it is no bigger than the ideal solution.Suppose you have defined a forward dataflow algorithm that is distribut i ve andhas finite descending chains. You accidentally initialized O UT[ B ] to ⊥ for allnodes oth er t han ENTRY.(a) Will your algorithm give a safe answer for all flow graphs?(b) If not, will it give a safe answer for some flow graph s? If it wil l , give anexample.(c) Will your algorithm give the MOP solution for all flow graphs?(d) If not, will it give the MOP solution for some flow graphs? If it will, givean example.Winter 2011/2012 page 3 of