Dominator Tree
In Java GC
From Reference : Dominator tree of object graph in Java heap analyzer.
An object x dominates an object y if every path in the object graph from the start (or the root) node to y must go through x.
The immediate dominator x of some object y is the dominator closest to the object y.
A dominator tree is built out of the object graph. In the dominator tree, each object is the immediate dominator of its children, so dependencies between the objects are easily identified.
- If x is the immediate dominator of y, then the immediate dominator of x also dominates y, and so on.
- The edges in the dominator tree do not directly correspond to object references from object graph.
- The objects belonging to the sub-tree of x (i.e. the objects dominated by x) represent the retained set of x ;
In LLVM
In LLVM: DominatorTreeWrapperPass is a function pass that will compute and give you the dominator tree for a function.
Dominator tree in the [LLVM DominatorTree Class]:
- A block is said to be forward statically reachable if there is a path from the entry of the function to the block. A statically reachable block may become statically unreachable during optimization.
- A forward unreachable block may appear in the dominator tree, or it may not. If it does, dominance queries will return results as if all reachable blocks dominate it. When asking for a Node corresponding to a potentially unreachable block, calling code must handle the case where the block was unreachable and the result of getNode() is nullptr.
- Generally, a block known to be unreachable when the dominator tree is constructed will not be in the tree. One which becomes unreachable after the dominator tree is initially constructed may still exist in the tree, even if the tree is properly updated. Calling code should not rely on the preceding statements; this is stated only to assist human understanding.