Compiler Optimization Techniques: Dominators, Dead Code Elimination, Dataflow Analysis, SSA

These flashcards cover essential concepts in compiler optimization techniques related to dominators, dead code elimination, dataflow analysis, and the static single assignment (SSA) form.

Dominators

Nodes in a control flow graph where a dominator node must be executed before any dominated node on every path.

Immediate Dominators (IDOM)

The closest dominator of a node N that is not N itself.

Dominator Tree

A tree structure formed by linking immediate dominators.

Dominance Frontier

A set of block entries that are not dominated by P and are first reached from a given node D.

Post-Dominance

J post dominates I if all paths from I exit must pass through J.

Post Dominance Frontier (PDF)

The frontier determined by blocks that are not guaranteed to exit without passing through the post-dominator.

Control Dependence

Node J is control dependent on node I if I EPDF (J).

Dead Code Elimination

The process of removing code that is not reachable or unused in the program.

Mark-Sweep Algorithm

An algorithm for dead code elimination that marks useful operations and sweeps away the unused ones.

Critical Operations

Operations that are significant to the working of the program, like stores and branches.

Reach Def Analysis

Analysis that determines which definitions of variables will be accessed later without being overwritten.

Liveliness Analysis

Determines whether a value will be needed in the future.

Availability Analysis

Checks if an expression has already been computed.

Simple SSA (Static Single Assignment)

Each variable is assigned exactly once, with uses renamed according to reach definitions.

Dominance-based SSA

For a variable defined in block B, it is represented in blocks that are dominance frontiers of B.

Defkill

Lines of code that define a variable in a particular scope.

Phi Functions

Functions used in SSA forms to resolve variable values at join points.

MOP (Meet over Paths)

The theoretical perfect static reasoning of a compiler regarding variable values at various paths.

MFP (Maximum Fixed Point)

The iterative analysis method to find variable values that converge in the compiler's optimization process.