Dominance analysis of irreducible CFGs by reduction
This paper presents a simple and fast algorithm with proof of correctness for analyzing dominance relations of control flow graphs (CFGs). A dominator tree and dominance frontiers are obtained by reducing a DAG, which is obtained by adding dummy vertexes to the original CFG to transmit dominance relation of irreducible loops to the resultant DAG. A specific order of stacking vertexes eliminates the necessity to search for reduction candidates. The computational complexity of the algorithm for a real-world CFG with M edges is O(M), which is also confirmed by analyzing about 1700 CFGs extracted from real programs.
irreducible reduction control flow graph dominator tree dominance frontier immediate dominator