Structural Optimization of a Control Flow Graph Based on the Algorithm of Topological Sort

A. N. Kovartsev, D. A. Popova-Kovartseva , e-mail: kovr_ssau@mail.ru

Algorithms for topological ordering of a directed graph are widely used wherever necessary to produce a reasonable sequence of actions when one action is dependent on others. In this paper, topological sorting algorithm is used as the basic heuristic to construct an approximate algorithm for structural optimization of the control graph of the program in order to reduce the number of the test paths. The feature of the proposed algorithm is that it works not only with the directed acyclic graphs, but with the graphs containing the cycles.

Keywords: structural optimization, control flow graph, algorithm for topological ordering, global optimization

pp. 31–36