2025-02-Compiler/notes/9.md

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