5. Dataflow Analysis Flashcards
What is dataflow analysis?
Static analysis reasoning about the flow of data (constants, variables, expressions) in a program
What is a control-flow graph?
A graph that summarizes the flow of control in all possible runs of the program.
Each node in the graph corresponds to a unique primitive statement in the program.
Each edge outgoing from a node denotes a possible immediate successor of that statement in some run of the program.
True or False? It is impossible for analysis to achieve all of the following: soundness, completeness, termination.
True
Dataflow analysis sacrifices completness.
Sound: will report all facts that could occur in actual runs.
Incomplete: May report additional facts that can’t occur in actual runs.
What is the primary source of dataflow analysis incompleteness?
Dataflow analysis abstracts away control-flow conditions with non-deterministic choice.
Non-deterministic choice means the analysis will assume that the condition can evaluate to true or false (even if in actual runs the condition always evaluates to true).
This is how dataflow analysis ensures it will consider all possible paths in actual runs of the program (sound) and maybe paths that are never possible (incomplete)
What are the following applications of dataflow analysis used for?
- Reaching Definitions Analysis
- Very Busy Expressions Analysis
- Available Expressions Analysis
- Live Variables Analysis
Reaching Definitions Analysis
- Find usages of uninitialized variables
Very Busy Expressions Analysis
- Reduce code size
Available Expressions Analysis
- Avoid recomputing expressions
Live Variables Analysis
- Allocate registers efficiently
How do we know the Chaotic Iteration algorithm will always terminate?
The two operations of reaching definitions analysis are monotonic > IN and OUT sets never shrink, only grow
Largest they can be set of all definitions in program > IN and OUT cannot grow forever
IN and OUT will stop changing after some iteration.
What is Live Variables Analysis?
Determine for each program point which variables could be live at the point’s exit
A variable is live if there’s a path to a use of the variable that doesn’t redefine the variable.
