L5

Question 1

dataflow analysis

Answer 1

reasoning about flow of data in program

Question 2

different kinds of dataflow analysis

Answer 2

constants, variables, expressions

Question 3

what do dataflow analysis used in

Answer 3

bug-finding tools and compilers

Question 4

what is a control-flow graph?

Answer 4

a graph that summarizes the flow of control in all possible runs of the program

Question 5

what does each node represent?

Answer 5

a unique primitive statement

Question 6

what does each edge represent?

Answer 6

denotes immediate possible successor

Question 7

can we achieve soundness, completeness, and termination?

Answer 7

no

Question 8

what does dataflow analysis sacrifice?

Answer 8

completeness

Question 9

How does dataflow analysis sacrifice completeness?

Answer 9

abstract away control-flow condition with non-deterministic choice

Question 10

what non-deterministic choice does dataflow analysis use?

Answer 10

assume a condition can be evaluated to true or false. It considers path that is not possible in the actual run, thus incomplete

Question 11

applications of dataflow analysis

Answer 11

reaching definition analysis, very busy expression analysis, available expression analysis, and live variable analysis.

Question 12

reaching definition analysis

Answer 12

find usages of uninitialized variables

Question 13

very busy expression analysis

Answer 13

reduce code size (use in pacemakers)

Question 14

available expression analysis

Answer 14

use by the compiler to avoid recomputing expressions. Start with all available expression, and cross each out whenever it changes.

Question 15

live variable analysis

Answer 15

use by the compiler to efficiently allocate registers to program variables

Question 16

reaching definition analysis’ goal

Answer 16

• determines with assignment might reach each program point.
• determines for each program point, which assignments have been made and not overwritten, when execution reaches that point along some path.

Question 17

result of dataflow analysis (informally)

Answer 17

• set of facts at each program point in the form ex: ,

Question 18

result of dataflow analysis (formally)

Answer 18

• compute the set of fact in and out each node: IN(n) and OUT(n), repeat until they stop changing (saturated or fixed point)

Question 19

(reaching definition analysis operation 1) how to compute IN[n]

Answer 19

IN[n] = U(OUT[predecessors(n)])

Question 20

(reaching definition analysis operation 2) how to compute OUT[n]

Answer 20

OUT(n) = (IN[n] - KILL[n]) U GEN[n]

Question 21

(reaching definition analysis) KILL[n]) & GEN[n] of a condtion

Answer 21

empty sets

Question 22

(reaching definition analysis) KILL[n] & GEN[n] of an assignment

Answer 22

GEN[n] = {}; KILL[n]={: m!=n}

Question 23

(reaching definition analysis) Chaotic Iteration

Answer 23

for (each node n):
IN[n] = OUT[n] = null
OUT[entry] = {: v is a program variable}
Repeat:
for each node n: operation1; operation2; until IN[n] & OUT[n] stop changing

Question 24

why does it always terminate

Answer 24

• the 2 operations are monotonic: the IN[n] & OUT[n] sets never shrink, only grow
• largest is the set of all definitions in the program, which is finite

Question 25

very busy expression analysis' goal

Answer 25

determine very busy expressions at the exit from the point

Question 26

what is a very busy expression

Answer 26

an expression (not a statement, only the right side of the "=" sign) that is used before any of the variables occurring in it are redefined.

Question 27

(very busy expression operation 1) how to compute OUT[n]

Answer 27

OUT[n] = Intersection(In[successors(n)])

Question 28

(very busy expression operation 2) how to compute IN[n]

Answer 28

IN[n] = (OUT[n] - KILL[n]) U GEN[n]

Question 29

(very busy expression) KILL[n]) & GEN[n] of a condtion

Answer 29

empty sets

Question 30

(very busy expression) KILL[n]) & GEN[n] of an assignment

Answer 30

GEN[n] = {a}; KILL[n]={expr e: e contains x}

Question 31

(very busy expression) Chaotic Iteration

Answer 31

for (each node n): IN[n] = OUT[n] = set of all exprs in the program IN[exit] = {} Repeat: for each node n: operation1; operation2; until IN[n] & OUT[n] stop changing

Question 32

available expression analysis' goal

Answer 32

determine, for each program point, which expression must already have been computed, and not later modified, on all paths to the program point

Question 33

live variable analysis' goal

Answer 33

determine for each program point which variables could be live at the point's exit

Question 34

what is a live variable? (at point P)

Answer 34

if there is a path to a use of the variable that doesn't redefine the variable (at or after point P)

Question 35

may vs must facts

Answer 35

may: facts along some paths must: facts along all paths