CN1783009A - Hot route searching method in assembly code hot function - Google Patents

Abstract

The invention discloses a method for searching hot paths in hot functions of assembly codes, which is used to search for paths with high execution frequency in assembly codes, including: restoring the assembly codes to control flow graphs, the control flow graphs are composed of multiple basic blocks, and includes the information of the plurality of basic blocks; identify the cycle information and loop nesting information of the basic blocks in the control flow graph according to the information of the basic blocks; The layer cycle is used as the current cycle to search for all the paths in the cycle. When searching for the path of the current cycle, the basic blocks of the sub-cycles of the current cycle are not considered; the execution frequency of each path found is calculated, and according to the execution frequency of the path Pick out the thermal path. The method of the present invention has the advantages of being able to quickly and accurately find out a number of hot paths that most closely affect performance and have the highest execution frequency from assembly codes; it is beneficial for developers to concentrate on analyzing codes on hot paths and save workload.

Description

A Hot Path Searching Method in Hot Functions of Assembly Code

technical field

The invention relates to a method for searching hot paths, in particular to a method for searching hot paths in hot functions of assembly codes.

Background technique

During the development of the compiler, developers often encounter such problems: the performance of the compiler is not as good as expected, but they don't know where the problem is; The performance has been improved, but it has declined in some cases; I got two compilers with different performances, and I want to know the difference in their optimization methods, but I don't know how to start. Such problems are usually resolved by performance analysis.

Performance analysis refers to dynamically or statically analyzing the code generated by the program to find out the imperfections or performance potential. Performance analysis tools can be divided into dynamic and static.

Dynamic analysis refers to the use of software or hardware to collect runtime information when the program is running, and finally gives statistical information to assist developers in finding performance bottlenecks. For example, Intel Corporation's VTune (Intel Corp, VTunePerformance Analyzers) can sample the currently executed instructions by time or event, or perform instrumentation on the program, and give statistical information on the CPU execution time of each function and each line of code. Another example is HP's perfmon (HP Corp, Overview of the Perfmon), which uses the performance management unit (PMU) on the IA-64 Itanium processor to count the distribution of CPU time on various events, such as Cache miss, pipeline Flush and register stack overflow, etc.

Static analysis refers to analyzing the assembly code generated by the compiler to find problems.

ORC is a research-oriented open source optimizing compiler for the IA64/Linux platform. In the process of developing the ORC compiler, first use VTune and perfmon for dynamic performance analysis. But the macro statistics given by perfmon et al. don't help much with micro problems. For example, although it points out how much time the program spends on instruction stopping and waiting, it has no way of knowing which places can be overcome by instruction scheduling. Another example is that it points out how much time the program spends executing instructions, but it does not know which instructions can be optimized through technologies such as Copy Propagation and Dead-Code Elimination. This information is obtained from static analysis of assembly code.

But in reality, the workload of analyzing assembly code is very large, and developers often feel that they have no way to start. For example, the number of assembler code lines in the test examples in SPEC2000 is often hundreds of thousands of lines, which cannot be fully analyzed. In order to solve the above problems, an easy-to-think method is based on the 2/8 distribution principle of program execution: 80% of the program time is spent executing 20% of the code, so only those that have the most impact on performance and the highest execution frequency need to be analyzed A handful of functions, the hot functions. However, what is usually encountered is that the assembly code of these hot functions also has tens of thousands of lines, especially after inlining (Inlining), the analysis volume is still very large. Continuing to expand this idea, we can concentrate on analyzing the hot code in the hot function. To find the hot code, you need to search for the hot path. The so-called hot paths refer to the most common paths for program execution. Since most of the program's time is spent in loops, if the entire function is regarded as the outermost loop, then each hot path must be located in a certain loop. Therefore, for the selected hot function, it is necessary to find out the loops in the function first, then search for hot paths in each loop, and finally sort by execution frequency, and select the hottest paths as the basis for performance analysis.

Contents of the invention

The purpose of the present invention is to overcome the large number of assembly codes in the static performance analysis of existing compilers, and it is not easy to find out the defects of key codes for analysis, and provide a static performance analysis method for compilers, that is, the hot path in the assembly code hot function Search method, which can quickly and accurately find several paths that have the most impact on performance and the highest execution frequency in the assembly code generated by the compiler.

In order to achieve the above object, the present invention provides a method for searching hot paths in assembly code hot functions, which is used to search for paths with high execution frequency in assembly codes, including:

Step a): restoring the assembly code into a control flow graph, the control flow graph is composed of a plurality of basic blocks and includes information of the plurality of basic blocks;

Step b): identifying the loop information and loop nesting information of the basic block in the control flow diagram according to the information of the basic block;

Step c): using each loop in the control flow graph as the current loop to search for all the paths in the loop; wherein, when searching for the path of the current loop, the basic blocks of the sub-loops of the current loop are not considered;

Step d): Calculate the execution frequency of each searched path, and select the hot path according to the execution frequency of the path.

In the above technical solution, the information of the basic block includes: the execution frequency of the basic block, the predecessor block and the successor block of the basic block, and the probability that the basic block advances to the successor block.

In the above technical solution, in step c), the path starts from the entry block of the current loop, and advances along the execution path of the basic block, if a sub-loop of the current loop is encountered during the forward process, the sub-loop is skipped. The basic block of circulation moves on, and when in advancing process, when a current basic block satisfies a termination condition, this current basic block is used as the last basic block of this path; Said termination condition is:

1) The current basic block has no successor block;

2) At least one successor block of the current basic block is not in the current cycle.

In the above-mentioned technical solution, in step c), it also includes setting a threshold value. When searching for a path, when the probability that the basic block advances to a successor block is less than the threshold value, then the basic block is not considered to go to the successor block. The block's execution path.

In step d), the execution frequency of the path is the product of the execution frequencies of all the basic blocks making up the path and the execution probabilities between adjacent basic blocks making up the path.

The advantage of method of the present invention is:

1. From the large amount of assembly code generated by the compiler, quickly and accurately find out several hot paths that have the most impact on performance and the highest execution frequency.

2. It helps compiler developers to focus on analyzing the code on the hot path, saving workload.

Description of drawings

Fig. 1 is the flowchart of the inventive method

Fig. 2 is a schematic diagram of the pseudocode of the hot_path_enum function in the embodiment.

Fig. 3 and Fig. 4 are schematic diagrams of pseudo codes of the enum_paths function in the embodiment.

Figure 5 is an output of a hot path search for a function CollectGarb in CPU2000gap.

Fig. 6 is a code control flow diagram in an embodiment

Detailed ways

The present invention will be further described in detail below in conjunction with the accompanying drawings and specific embodiments.

As shown in Figure 1, a hot path search method in an assembly code hot function includes the following steps:

In step 10, the assembly code is reduced to a control flow graph. A control flow graph refers to an abstract data structure used in a compiler, which is an abstract representation of a program or process. In a control flow graph, each node represents a basic block, and directed edges represent transitions in the control flow. The control flow graph also has two special blocks: the entry block and the exit block. The control flow enters the control flow graph through the entry block, and the control flow ends through the exit block. The purpose of restoring the control flow graph is to prepare for identifying loops. The operation of restoring the control flow graph is realized by using the compiler profiling technology. Compiler profiling is a technology to obtain program execution information. It is an existing technology. Compiler profiling technology can be used to dynamically obtain such as the number of executions of basic blocks, the execution time of each function in the program, the probability of control flow transition, etc. information. After the operation of restoring the control flow graph is completed, each basic block is marked with at least the following information:

Block ID: the ID of the basic block;

Frequency: the execution frequency of the basic block;

Predecessors: IDs of all predecessors of the basic block on the control flow graph;

Successors: IDs of all successors of the basic block on the control flow graph;

Probabilities: in turn correspond to the probability that the control flow is transferred to each of its successors.

Figure 6 is a restored control flow graph, which contains information such as the number and identification of the basic block, the execution frequency of the successor block, and the probability of transferring the basic block to its successor block.

Since this step can be implemented using existing technologies, it will not be described in detail here.

In step 20, the cycle information of the basic block in the control flow diagram is identified from the information of the basic block. The compiler records the loop information on the basic block when doing loop optimization, and outputs it together with the basic block when the code is output. As a result of identifying loops, each loop has the following types of information:

Loop entry: referred to as entry, the only entry of the loop;

Loop tail: referred to as tail, the only ending basic block of the loop, which has a loop back edge pointing to the entry;

Loop side exits: s ₀ …s _m , 0 or more side exits of the loop;

Loop blocks: bb ₁ …bb _n , all basic blocks located in this loop.

The above-mentioned ending basic blocks or side exits of the loop are defined as loop exits. The entire function can be regarded as the outermost loop, the entry of the function is the entry of the outermost loop, and the exit of the function is the end of the outermost loop. The outermost loop has no side exits, and its basic blocks are all basic blocks in the function.

In Figure 6, the function to be identified is the outermost loop loop1, which contains all basic blocks. The loop loop2 consists of basic blocks b, e.

Since the identification of the cycle can be implemented in the compiler, the specific process of identifying the cycle will not be described in detail here.

In step 30, loop nesting information is identified. Loop nesting information, that is, to indicate which is the immediate parent loop of each loop. The identification of loop nesting information uses the following two principles: 1) If the entry and tail of loop1 are both in loop2, then loop2 must be the ancestor loop of loop1; 2) If loop2 is the smallest in the ancestor loop of loop1, then loop2 is the parent loop of loop1. Sort all the loops by size, scan whether the small loop is in the big loop from small to large, and identify the nesting information of the loop. Using the above two principles, it is possible to specifically identify which sub-loops and parent loops are of a loop.

In Figure 6, it can be seen that loop2 is a sub-loop of loop1.

In step 40, hot paths in the loop are searched. It has been mentioned in the summary of the invention that a preferred solution in the process of searching for the hot path is to use the threshold technology to quickly search for the hot path. In this embodiment, this step is described in detail by taking the preferred solution as an example.

Before describing this operation step in detail, first introduce how to realize the processing of the sub-cycle.

The judgment and identification of the hot path is based on the execution frequency of the path, but because the sub-loop can loop itself, it will get the wrong execution frequency of the current path, so it should be skipped during the hot path search for a loop sub loop. The specific operation steps are as follows: set the current path cur_path={entry,...,bb _i }, and a successor cur_block of bb _i is the entry of a certain sub-loop, and set the k post exits of the sub-loop to be pe ₁ ,..., pe _k . The so-called loop exit successor refers to the successor blocks of all loop exits of the current loop, and these blocks are not in the current loop. For sub-loop processing, we only need to jump to each exit successor pe _i (i=0, 1, 2...k) of the sub-loop, let the current path cur_path={entry,..., cur_block, pe _i }. Correspondingly, the frequency of the current path is multiplied by the probability of control flow jumping from the subloop to pe _i .

The processing of sub-loops is applied to the method of fast hot path search described below.

The implementation method of hot path fast search is:

The path starts from the entry block of the current loop and advances along the execution path of the basic block. If a sub-loop of the current loop is encountered during the forward process, the basic block of the sub-loop is skipped and continues to move forward. In, when a current basic block satisfies a termination condition, the current basic block is taken as the last basic block of the path; the termination condition is:

1) The current basic block has no successor block;

2) At least one successor block of the current basic block is not in the current cycle.

The execution frequency of a path is the product of the execution frequencies of all the basic blocks that make up the path and the execution probabilities between adjacent basic blocks that make up the path.

The threshold technology is used in the search process of the hot path. In the search process, a threshold value is set. If the probability of a basic block jumping to a subsequent basic block is less than the threshold value, the basic block to the subsequent block is not considered. Execution path, which speeds up the search for hot paths.

In this embodiment, the above-mentioned fast hot path search method is realized by using the function hot_path_enum(loop). The function of this function is to find out all the hot paths in the current loop loop and its sub-loops, and use it to call the outermost loop of the function to find out all the hot paths in the function. Referring to Figure 2, it includes the following steps:

Step 41: Define a variable cur_path, and leave it empty, indicating that there is no hot path yet.

Step 42: Use the variable eblock to mark the entry block of the loop.

Step 43: Use the variable cur_path_freq to mark the execution frequency of the eblock.

Step 44: Call the function enum_paths(eblock, cur_path, cur_path_freq, loop) to calculate the hot path of the current loop. The variable cur_path_freq is used to record the execution frequency of the path, and the variable loop indicates the current loop.

Step 45: Compute the thermal paths of all sub-loops of the loop.

In step 44, the function enum_paths (eblock, cur_path, cur_path_freq, loop) is called, which is used to calculate the hot path, and the threshold technology is used in this function. Its operation process is relatively complicated, and its specific operation will be described in detail below with reference to FIG. 3 and FIG. 4 .

Call the function enum_paths(cur_block, cur_path, cur_path_freq, loop), where cur_block represents the current block, cur_path represents the current path, cur_path_freq represents the execution frequency of the current path, and loop represents the loop it is in.

Step 100: Determine whether the current block cur_block is in a loop, if not, return and end the current function, if yes, continue to perform the following operations.

Step 200: Add the current block cur_block into the current path cur_path.

Step 300: Determine whether cur_block has a successor block, if there is a successor block, jump to step 500, if there is no successor block, proceed to the next step.

Step 400: Output the current hot path cur_path and its execution frequency cur_path_freq, and jump to step 700.

Step 500: Set the flag already_dump to 0, indicating that the hot path and its execution frequency have not been output.

Step 600: Record the successor block of curr_block as succ, and perform the following operations on the successor block.

Step 610: Determine whether the successor block succ is the entry of a sub-loop of the current loop, if no, jump to step 620, if yes, continue to perform the following operations.

Step 611: Set a variable tmp_cur_path_freq, which is the product of the current path execution frequency cur_path_freq and the probability of the edge from the current block cur_block to the successor block succ.

Step 612: Use inner_loop to identify the sub-loop where the successor block succ is located. If there is a successor block at the exit of the sub-loop, use post_exit to identify the new successor block, and perform the following operations on the new successor block.

Step 612a: Multiply tmp_cur_path_freq by the probability of jumping from inner_loop to post_exit, and put the result back into tmp_cur_path_freq.

Step 612b: call enum_paths(post_exit, cur_path, tmp_cur_path_freq, loop); calculate all hot paths starting from post_exit.

Step 613: Determine whether the hot paths in other subsequent blocks post_exit of the exit of the sub-loop inner_loop have been calculated. If not, jump to step 612a. If calculated, continue the following operations.

Step 620: If the successor block succ is not within the loop or the successor path of cur_block (namely cur_block->succ) is a return edge, then perform the following operations; if not, go to step 630.

Step 621: Determine whether already_dump is 0, if it is 0, output the current set of hot paths and execution frequency, and continue to perform the following operations. If not 0, do nothing and jump to step 630.

Step 622: Set already_dump to 1.

Step 630: Determine whether the execution probability of the side where the successor path of cur_block (ie cur_block->succ) is located is less than a threshold value, the threshold value is given by the user according to actual needs. If yes, jump to step 660, if no, continue the following operations.

Step 640: Multiply cur_path_freq by the execution probability of the edge cur_block->succ, and place the multiplied result in tmp_cur_path_freq.

Step 650: Call the function enum_paths(succ, cur_path, tmp_cur_path_freq, loop) to calculate the set of all hot paths starting from succ.

Step 660: Determine whether the internal heat paths of all successor blocks succ of the current block curr_block have been calculated, if not, select a successor block whose internal heat paths have not been calculated, and jump to step 600, if yes, continue Do the following.

Step 700: End the operation and exit the function.

Step 610 to step 613 in the above steps are the specific realization of the processing sub-loop.

The above is the method of the present invention.

Using the profiling in the compilation process, the hot paths can be sorted by execution frequency, and the hottest paths (that is, the paths with the highest execution frequency) can be selected as the basis for performance analysis.

A specific example is given below to illustrate the method of this embodiment.

As shown in Figure 6, it is a control flow graph of a piece of code. In this graph, there are seven basic blocks a, b, c, d, e, f, and g. The integer next to the basic block represents the execution frequency of this basic block , There are edges between blocks, and the numbers on the edges represent the probability of walking this edge. There are two loops in the figure, one is the outermost loop, denoted as loop1, which contains all the basic blocks. The other is the sub-loop loop2, which consists of basic blocks b, e. Start searching for the path in loop1 from a, a has two successor blocks, namely b and c, the execution frequency of a is 10, the probability of going from a to b is 0.2, and the probability of going from a to c is 0.8. To illustrate the processing of subloops, the thresholding technique is not used. First go from a to b, the current path cur_path={a}, the frequency is 10. Because b is the entrance of the sub-loop loop2, we can see from the above-mentioned sub-loop processing that the sub-loop loop2 should be skipped, so it directly jumps to the exit of loop2 to follow d and f, thus splitting into two paths: {a, d} The frequency of and {a, f}, {a, d} is 10*0.2*0.01=0.02; the frequency of {a, f} is 10*0.2*0.01=0.02. These two paths continue to traverse downwards, generating two paths: {a, d, g} and {a, f, g} with frequencies of 0.02 and 0.02, respectively. At this time, traverse down again, because the basic block g has no successor block, so the path is terminated, and finally two paths {a, d, g} and {a, f, g} are obtained, and the frequencies are 0.02 and 0.02 respectively. If a goes to c, the current path cur_path={a}, the frequency is 10, the successor block c of a does not meet the termination condition of the path, and the hot path search method described in the present invention is repeatedly used, with the basic block c as the current block, its The successor block is g, add c to the current path, the current path cur_path={a,c}, the frequency is 10×0.8=8, similarly traverse downwards, and get the path {a,c,g}, the frequency is 10× 0.8×1.0=8, since g has no successor block, the termination condition of the path is met, and the final obtained path is {a, c, g} with a frequency of 8. After the hot path search is implemented for the outermost loop loop1, the hot path search is performed on the sub-loop loop2 skipped in the first hot path search. There are two basic blocks b and e in loop2. In this loop, the entry block of the loop is b, and the exit blocks of the loop are b and e. If b is both an entry block and an exit block, it is easy to obtain a path {b} with a frequency of 100. If b is an entry block and e is an exit block, the method of the present invention can also easily obtain the path {b, e}, and its frequency is 100×0.99=99. Therefore, there are two paths {b} and {b, e} in loop2, and their frequencies are 100 and 99 respectively. From the control flow graph of this code, five paths can be obtained according to the method of the present invention, namely: {a, d, g}, {a, f, g}, {a, c, g}, { b} and {b, e}. If the hot paths are sorted and the top 3 hottest paths are taken, then they are {b}, {b, e}, {a, c, g} in order. The above is under the condition that the threshold technology is not used. If the threshold technique is used, assuming that the threshold value is set to 0.1, since the probability of jumping from a to d and f is less than 0.1, it will not traverse {a, d, g} and {a, f, g}. Path, the final path is {a, c, g}, {b} and {b, e}. Doing so can obviously save the time of traversing related basic blocks and speed up the search, so as to achieve the purpose of quickly searching for hot paths.

The method of the present invention can be used to search for the hot path more conveniently. As shown in FIG. 5 , an output of a function CollectGarb in the CPU2000gap using the method of the present invention is used to search for the hot path.

In the figure, Path# represents the sequence number of the path, Loop# represents the loop sequence number, Freq represents the frequency of execution, Hot Path &(Source Line#) represents the specific hot path, and the part in the back brackets represents the line number of the source program. In Figure 5, the five paths with the highest execution frequency in the CollectGarb function are listed. Taking path 2 as an example, the cycle number of this path is 1, its execution frequency is 5.21e+06, and its specific hot path is 29 30 116 117 47, where the number label indicates the sequence number of the basic block, that is to say, the hot path 2 passes through the basic blocks 29, 30, 116, 117 and 47. The line numbers of the starting source program of the above basic blocks are 774 789790 791 792 799 800 834 respectively.

Claims (5)

1. A method for searching hot paths in assembly code hot functions, which is used to search for paths with high execution frequency in assembly codes, including: Step a): restoring the assembly code into a control flow graph, the control flow graph is composed of a plurality of basic blocks and includes information of the plurality of basic blocks; Step b): identifying the loop information and loop nesting information of the basic block in the control flow graph according to the information of the basic block; Step c): using each loop in the control flow graph as the current loop to search for all the paths in the loop; wherein, when searching for the path of the current loop, the basic blocks of the sub-loops of the current loop are not considered; Step d): Calculate the execution frequency of each searched path, and select the hot path according to the execution frequency of the path. 2. The hot path search method in the assembly code hot function according to claim 1, wherein the information of the basic block includes: the execution frequency of the basic block, the predecessor block and the successor block of the basic block, the basic block Probability of advancing to a successor block. 3. The hot path searching method in the assembly code hot function according to claim 2, characterized in that, in step c), the path starts from the entry block of the current loop and advances along the execution path of the basic block , if a sub-cycle of the current cycle is encountered during the forward process, the basic block of the sub-cycle is skipped and continues to move forward. When a current basic block satisfies a termination condition during the forward process, the current basic block is used as the path The last basic block of ; the termination condition is: 1) The current basic block has no successor block; 2) At least one successor block of the current basic block is not in the current cycle. 4. The hot path search method in the assembly code hot function according to claim 3, characterized in that, in step c), it also includes setting a threshold value, when searching for the path, when the basic block advances to one of the When the probability of the successor block is less than the threshold, the execution path from the basic block to the successor block is not considered. 5. The hot path searching method in the assembly code hot function according to claim 2, characterized in that, in step d), the execution frequency of the path is the execution frequency of all basic blocks forming the path and the The product of execution probabilities between adjacent basic blocks of a path.

Images