29 lines
563 B
Markdown
29 lines
563 B
Markdown
# Control Flow Analysis
|
|
|
|
Dominator
|
|
|
|
for a given CFG **a node `x` dominates a node `y`** if every path from the Entry block to `y` contains `x`.
|
|
|
|
* Each BB dominates itself
|
|
* If `x dom y` and `y dom z` then `x dom z`
|
|
* If `x dom z` and `y dom z` then either `x dom y` or `y dom x`
|
|
|
|
Dominator Tree
|
|
* initial node is a root
|
|
* `x dom y` means that "`y` is a child of `x`"
|
|
|
|
|
|
Natural Loops
|
|
|
|
How to Find Natural Loop?: Introduction Backedge
|
|
|
|
Important concepts in a loop
|
|
* Header and Loop BB
|
|
* Back Edges
|
|
* Exit Edges
|
|
* Preheader (Preloop)
|
|
|
|
Loop-Invariant Computation
|
|
|
|
|