Marek Honzírek

Dominance in Control Flow Graph: a Way to Identify the Structure of Computer Program Marek Honzírek

Finding dominators in a control flow graph is one of the most desirable goals in control flow analysis. The dominators can be used for finding the parts of a computer code which must unconditionally run. The dominators can be further utilized for code optimizations and detecting independent units in a code. This can be especially suitable for the code written in assembly language, which represents complex structure, mainly caused by the still widely used statement GOTO. This work describes some suitable algorithms for finding dominators and then shows their application in practice. The behavior of the algorithms is investigated on random, as well as on assembly control flow graphs. This work also discusses the contribution of the dominators for the orientation in a control flow graph and proposes some suitable solutions.