L5 Flashcards
dataflow analysis
reasoning about flow of data in program
different kinds of dataflow analysis
constants, variables, expressions
what do dataflow analysis used in
bug-finding tools and compilers
what is a control-flow graph?
a graph that summarizes the flow of control in all possible runs of the program
what does each node represent?
a unique primitive statement
what does each edge represent?
denotes immediate possible successor
can we achieve soundness, completeness, and termination?
no
what does dataflow analysis sacrifice?
completeness
How does dataflow analysis sacrifice completeness?
abstract away control-flow condition with non-deterministic choice
what non-deterministic choice does dataflow analysis use?
assume a condition can be evaluated to true or false. It considers path that is not possible in the actual run, thus incomplete
applications of dataflow analysis
reaching definition analysis, very busy expression analysis, available expression analysis, and live variable analysis.
reaching definition analysis
find usages of uninitialized variables
very busy expression analysis
reduce code size (use in pacemakers)
available expression analysis
use by the compiler to avoid recomputing expressions. Start with all available expression, and cross each out whenever it changes.
live variable analysis
use by the compiler to efficiently allocate registers to program variables
reaching definition analysis’ goal
- 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.
result of dataflow analysis (informally)
- set of facts at each program point in the form ex: ,
result of dataflow analysis (formally)
- compute the set of fact in and out each node: IN(n) and OUT(n), repeat until they stop changing (saturated or fixed point)
(reaching definition analysis operation 1) how to compute IN[n]
IN[n] = U(OUT[predecessors(n)])
(reaching definition analysis operation 2) how to compute OUT[n]
OUT(n) = (IN[n] - KILL[n]) U GEN[n]
(reaching definition analysis) KILL[n]) & GEN[n] of a condtion
empty sets
(reaching definition analysis) KILL[n] & GEN[n] of an assignment
GEN[n] = {}; KILL[n]={: m!=n}
(reaching definition analysis) Chaotic Iteration
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 changingwhy does it always terminate
- 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
very busy expression analysis’ goal
determine very busy expressions at the exit from the point
what is a very busy expression
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.
(very busy expression operation 1) how to compute OUT[n]
OUT[n] = Intersection(In[successors(n)])
(very busy expression operation 2) how to compute IN[n]
IN[n] = (OUT[n] - KILL[n]) U GEN[n]
(very busy expression) KILL[n]) & GEN[n] of a condtion
empty sets
(very busy expression) KILL[n]) & GEN[n] of an assignment
GEN[n] = {a}; KILL[n]={expr e: e contains x}
(very busy expression) Chaotic Iteration
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
available expression analysis’ goal
determine, for each program point, which expression must already have been computed, and not later modified, on all paths to the program point
live variable analysis’ goal
determine for each program point which variables could be live at the point’s exit
what is a live variable? (at point P)
if there is a path to a use of the variable that doesn’t redefine the variable (at or after point P)
may vs must facts
may: facts along some paths
must: facts along all paths
