Journal "Software Engineering"
a journal on theoretical and applied science and technology
ISSN 2220-3397

Issue N7 2014 year

On the Issue of Optimal Program Linearization
N. I. Vyukova , e-mail:, V. A. Galatenko , e-mail;, S. V. Samborskij

The paper discusses two methods for optimal program linearization from the viewpoint of minimizing the number of unconditional jumps. The first one relates to the simple case when only unconditional jumps are considered. This task can be formulated as the task of finding optimal path covering for a subgraph of CFG (Control Flow Graph). The subgraph in question (Fall Through Graph — FTG) includes only fallthrough edges and the vertices connected with them. The method implies finding the optimal "path and cycle" covering of FTG with subsequent breaking of cycles. The complexity of the algorithm is O(N) where N is the number of vertices in FTG.

The final section of the paper discusses the NP-complete task of path covering of an arbitrary digraph which arises during optimal program linearization with respect to all kinds of jumps including conditional ones. We propose a recursive enumeration based on building the optimal "path and cycle" covering of the digraph with subsequent breaking of cycles.

Keywords: jump optimization, program linearization, path covering
pp. 3–8