SSA/Control flow analysis

Question 1

A dominates B

Answer 1

to reach block B, must have gone through block A

Question 2

dominance frontier

Answer 2

For a block X, the set of nodes Y s.t. X dominates an immediate predecessor of Y but does not strictly dominate Y

Question 3

SSA

Answer 3

static single assignment form

Question 4

Goal of SSA form

Answer 4

build an intermediate representation of the program in which each variable is assigned a value in at most 1 program point

Question 5

How to convert to SSA form?

Answer 5

make new variables to carry over the effect of the original program

Question 6

Phi Functions

Answer 6

If have conditions and two different branches that assign different values to the same variable, then must pick one

Question 7

How to compute Phi function replacement

Answer 7

want to figure out where there are multiple assignments that reach a node; can put a phi func for each assignment at every node in dominance frontier

Question 8

Pruned Phi Functions

Answer 8

Suppose useless phi function nodes (cases where the result is never used downstream)

Question 9

meet operation

Answer 9

union of sets (of

Question 10

Why are reaching definitions useful?

Answer 10

Answers the question, where could this variable have been defined

Question 11

Forward analysis

Answer 11

Start at the beginning of a function’s CFG, work along the control edges (reaching definitions)

Question 12

Backward anlysis

Answer 12

Start at the end of a function’s CFG, work against the control edges (live variables)