All Flashcards
Dominating
A dominates B if you have to go trough B to get to A.
Dominator set
A set of all dominating nodes.
Immediate dominator set
From the dominator set the one that is closed.
Post-dominator table
A is post-dominator table of B if to get from B to the exit you have to go trough A.
Spanning tree
Representation of a CFG where two rules are followed: 1. If there’s an edge to an unvisited node, we mark the edge and follow it
2. If there’s no edge to an unvisited node, we go back to the parent.
Advancing edge
An edge going from A to B where B is a decendant of A in a the spanning tree.
Retreating edge
An edge going from A to B where A is the decendant of B in the spanning tree
Cross-edge
An edge where A is not an ancestor of B or B of A in a spanning tree
Back edge
An edge from A to B where B dominates A.
Function inlining
Instead of function call, we replace the function call with the body of the function
Function cloning
Create different versions of functions for different calls to reduce static arguments
Constant folding
Evaluating expressions at runtime (x = 1 + 2 -> x = 3)
Constant propogation
Replace uses of variables with constants if the variables are constant
Copy propagation
Copies of variables are replaced by the values it has been copied from. So x = y; y = x + 1 -> x = y; y = y + 1
Algebraic simplification
things like a * 1 -> a
Common Subexpressions elimination
If a expression is calculated multiple times, it is reused instead
Dead Code Elimination
If a variable isn’t read from.
Strength reduction
Some operations take more computation (mul, div) replace them with simpler ones (add, sub)
Loop-invariant code motion
If a statement/expression doesn’t change in a loop, take it out of the loop.
