Module Cfg_dominators
Dominator-related utility functions.
val build : Cfg.t -> Cfg_dominators.tComputes all dominator-related information, in particular immediate dominators, dominance frontiers, and dominator forest for the passed CFG.
val is_dominating : Cfg_dominators.t -> Label.t -> Label.t -> boolis_dominating doms x y is true iff x is dominating y according to doms. That is, all paths from the entry node to y go through x. All edges, regular and exceptional are treated the same way.
val is_strictly_dominating : Cfg_dominators.t -> Label.t -> Label.t -> boolis_strictly_dominating doms x y is true iff x is strictly dominating y according to doms. That is, is_dominating doms x y = true and x is not equal y. All edges, regular and exceptional are treated the same way.
val find_dominance_frontier : Cfg_dominators.t -> Label.t -> Label.Set.tfind_dominance_frontier doms label returns the dominance frontier for label according to doms. The definition we use is the following: "the dominance frontier of a node n is the set of all nodes m such that n dominates a predecessor of m, but does not strictly dominate m itself".
val dominator_forest : Cfg_dominators.t -> Cfg_dominators.dominator_tree listReturns all dominator trees. Typically one of these will correspond to the entry point of the program and the remainder to dead code.
val dominator_tree_for_entry_point :
Cfg_dominators.t ->
Cfg_dominators.dominator_treeReturns the unique dominator tree rooted at the entry point of the program (thus ignoring any isolated trees that correspond to dead code).
val iter_breadth_dominator_forest :
Cfg_dominators.t ->
f:(Label.t -> unit) ->
unititer_breadth_dominator_forest doms ~f iterates over the dominator forest from doms in a breadth-first manner (iterating over a whole tree of the forest before moving to the next tree), applying f to visited nodes.