METHOD OF FORMING A PROGRAM EXECUTION GRAPH TO SEARCH FOR NESTED CYCLES BASED ON STATIC AND DYNAMIC ANALYSIS OF EXECUTABLE CODE

A method is proposed for constructing a program execution graph based on static and dynamic analysis of executable program code for subsequent search for nested loops and their classification. A simplified structure of the execution graph is presented to reduce the number of repeated calculations during processing. Such structure consists of individual procedure subgraphs that being linked to each other. Code instructions grouped into code instruction blocks separated by jmp-type instructions. It is shown how nesting depth of loop can be calculated utilizing intraprocedure and interprocedure nesting depth of each subgraph. The process of obtaining execution graphs based on static and dynamic analysis of executable program is briefly described. A method for combining program execution graphs obtained from static and dynamic analysis is presented. The graph from static analysis used as a basis, due to its higher code coverage. First stage is an algorithm for initial matching of corresponding procedure subgraphs of both graphs, using the memory address of first vertex. Second stage is an algorithm for combination of both subgraphs into one, using the memory address to determine the equality of all vertices in both subgraphs. Third stage is an algorithm for adjusting the execution order records from the dynamic analysis to the obtained graph. The resulting information about cycles can be applied for automatic parallelization on the user's system side, taking into account its configuration.