Dominators and Retained Size

Let's continue to use this example call graph:

Imagine the pow function itself might is not very large. But it calls functions soft and fluffy, both of which are huge. And they are both only called by pow, so if pow were removed, then soft and fluffy would both become dead code and get removed as well. Therefore, pow's "real" size is huge, even though it doesn't look like it at a glance.

The dominator relationship gives us a way to reason about the retained size of a function.

In a graph that is rooted at vertex R, vertex A is said to dominate vertex B if every path in the graph from R to B includes A. It follows that if A were removed from the graph, then B would become unreachable.

In our call graphs, the roots are the main function (for executables) or publicly exported functions (for libraries).

V is the immediate dominator of a vertex U if V != U, and there does not exist another distinct vertex W that is dominated by V but also dominates U. If we take all the vertices from a graph, remove the edges, and then add edges for each immediate dominator relationship, then we get a tree. Here is the dominator tree for our call graph from earlier, where shred is the root:

Using the dominator relationship, we can find the retained size of some function by taking its shallow size and adding the retained sizes of each function that it immediately dominates.