Background
A compiler (compiler) is a program that converts the original code written in a high-level programming language (C, C ++ code, etc.) into another representation (machine binary language).
The main purpose of the compiler is to translate a high-level computer language, which is convenient for a person to write, read, and maintain, into a machine language, i.e., an executable program, that the computer can interpret and run. The source code is typically a High-level language (High-level language), such as Pascal, C, C ++, c#, java, etc., and the target language is an assembly language or Object code (Object code) of the target Machine, sometimes referred to as Machine code (Machine code).
The main workflow of a modern compiler can be seen in fig. 1:
Optimizing pass introduction:
pass is a step in a compiler used to optimize or analyze a program, and a program typically passes through multiple passes, each of which may also be performed in multiple passes.
The optimized pass is described below by way of example in the clang/llvm architecture.
Converting LLVM IR to object assembly code requires several steps to go through. IR is transformed into back-end friendly representations of instructions, functions, global variables. This representation changes as the program goes through various back-end stages, approaching the actual target machine instructions. FIG. 2 shows the necessary steps, from LLVM IR to object code or assembly, that can be performed without necessarily optimizing Pass to further improve the quality of translation.
This translation pipeline consists of several stages at the back end, which are also referred to internally as super Pass, because they are implemented by several small Pass. These Pass are critical to the success of the backend compared to other steps, which are more important to improve the efficiency of the generated code.
FIG. 2 is a flow chart of the execution of the LLVM backend, showing the optimizations passes in FIG. 2, one passes possibly making multiple optimization pass in succession, and others being processes.
Can be used as an intermediate representation of the optimized inputs and outputs, collectively referred to as IR, such as IR, MI, MC, etc. in clang/llvm.
Other processes than optimization passes are necessary at compile time, and an optimization pass is generally optional, but if optimization is done, the resulting code will be better, not every optimization will have a positive optimization effect on the particular code.
During programming, programmers frequently modify code and recompile it. Although using CMake and other compiling systems, incremental compiling can be realized, the number of files to be compiled can be reduced as much as possible. But the incremental approach is file-level in that it determines whether recompilation is required based on whether the file is modified. In most cases, the programmer only modifies a few functions in the file, but will result in recompilation of the entire file and its dependencies. Even if only a single space is added to the file, this results in a large number of recompilations of the file.
In compiling a program, the compilation optimization takes most of the time, and a modern compiler typically has as many as 100 or more optimization Pass, however these Pass are not always valid, i.e. even if run, there is no change to the code. These inefficiencies optimize the operation of Pass, wasting a lot of compile time, affecting the compiler's use experience.
Disclosure of Invention
Aiming at the technical problems existing in the prior art, the invention provides a compiler performance optimization method, which comprises the following steps:
When compiling for the first time, recording hash values of functions IR before and after each function in the program code is completed, wherein IR refers to intermediate representation in the compiling process;
setting the optimization effectiveness of each optimization on the function according to whether the hash value of the function IR changes before and after each optimization is executed by each function;
recording the hash value of the triple < function IR before optimization, the hash value of the function IR after optimization and the optimization effectiveness > in a function optimization map table;
Calculating a hash value before the current function executes current optimization in the second compiling;
According to the current function and the current optimization, searching in the function optimization map table, and comparing the hash value of the function IR before the current function is subjected to the current optimization with the hash value of the current function before the current function is subjected to the current optimization calculated in the second compiling;
and determining whether the current optimization needs to be executed or not according to the comparison result and the value of the current optimization found in the function optimization map table for the optimization effectiveness of the current function.
On the basis of the technical scheme, the invention can be improved as follows.
Optionally, the setting the optimization validity of each optimization for the function according to whether the hash value of the function IR changes before and after each optimization is performed by each function includes:
If the hash value of the function IR changes before and after any one of the functions executes any one of the optimizations, the optimization of any one of the functions is valid, the optimization validity is set to be 1, and otherwise, the optimization is invalid, and the optimization validity is set to be 0.
Optionally, the function optimization map table is stored as a hidden file in a source code directory for use in next compiling.
Optionally, the method further comprises optimally storing the function optimization map table according to whether the two optimizations are adjacent. Wherein:
If the two optimizations are adjacent, regarding the same function, taking the hash value of the function IR after the LAST optimization as the hash value of the function IR before the current optimization, wherein the hash value of the function IR before the current optimization is expressed by LAST, which indicates that the hash value of the function IR after the LAST optimization is the same as the hash value of the function IR after the LAST optimization;
If the two optimizations are not adjacent, respectively calculating hash values of functions IR before and after the two optimizations;
when the hash value of the function IR before and after the SAME optimization is unchanged, the hash value of the function IR after the optimization is expressed by SAME, which indicates that the hash values of the function IR before and after the optimization are the SAME.
Optionally, the determining whether the current optimization needs to be executed according to the comparison result and the value of the current optimization found in the function optimization map table for the optimization effectiveness of the current function includes:
If the hash value of the function IR before the current function is executed and the hash value of the function IR before the current function is executed is different from the hash value of the function IR before the current function is executed, or if the hash value of the function IR before the current function is executed and the hash value of the function IR before the current function is executed is the same as the hash value of the function IR before the current function is executed and the hash value is 1, the current optimization is effective, the current optimization needs to be executed, otherwise, the current optimization is ineffective, and the current optimization does not need to be executed.
Optionally, the determining whether the current optimization needs to be executed according to the comparison result and the value of the current optimization found in the function optimization map table for the optimization effectiveness of the current function further includes:
When the current optimization needs to be executed, after the current optimization is executed, calculating the hash value of the current function IR after the execution of the current optimization is finished, and setting the effectiveness of the optimization according to whether the hash value of the function IR before and after the current optimization is changed;
The function optimization map table is updated based on the hash value of the function IR before and after the current optimization and the optimization validity.
The compiler performance optimization method comprises the steps of recording hash values of functions IR before and after each function in program codes executes each optimization, recording optimization effectiveness, recording the hash values of the functions IR before and after the optimization and the optimization effectiveness in a function optimization map table, calculating hash values of the current functions before executing the current optimization when the functions are compiled for the second time, searching in the function optimization map table, comparing the hash values of the functions IR before executing the current optimization of the current functions with the hash values of the current functions before executing the current optimization when the functions are compiled for the second time, and determining whether the current optimization needs to be executed according to comparison results and the values of the current optimization searched in the function optimization map table for the optimization effectiveness of the current functions. According to the method, the function optimization effectiveness table of the first compilation is established to guide the second compilation, so that redundant optimization is reduced as much as possible, and the time required by the second compilation is shortened.
Detailed Description
For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions of the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments of the present invention. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention. In addition, the technical features of each embodiment or the single embodiment provided by the invention can be combined with each other at will to form a feasible technical scheme, and the combination is not limited by the sequence of steps and/or the structural composition mode, but is necessarily based on the fact that a person of ordinary skill in the art can realize the combination, and when the technical scheme is contradictory or can not realize, the combination of the technical scheme is not considered to exist and is not within the protection scope of the invention claimed.
After the first compiling, if the compiling file of the program is deleted or the code is modified, a plurality of redundant optimizations can be still performed like the first compiling. These optimizations, if done, do not have an impact on the final generated code. These redundant optimizations can affect the speed of code compilation.
Based on the method, the invention provides a compiler performance optimization method, which guides the second compiling by establishing a function optimization effectiveness table of the previous compiling, skips meaningless redundant optimization as much as possible, shortens the compiling time of the second compiling, and mainly comprises two parts, wherein the first part is used for establishing a function optimization effectiveness map table during the first compiling, and the second part is used for guiding the compiling by using the established map table during the second compiling, reduces the redundant optimization and shortens the compiling time.
The IR referred to in the present invention is various intermediate representations, not only one, such as IR, MI, MC, etc. in the Clang/LLVM architecture, but also various types of intermediate results in the compilation process, which can be regarded as IR as an optimized input-output representation.
FIG. 3 provides a flow chart of a compiler performance optimization method of the present invention, as shown in FIGS. 3 and 4, the method comprising:
In step S1, when compiling for the first time, the hash value of each function IR before and after each function in the program code is recorded, where IR refers to an intermediate representation in the compiling process.
Step S2, setting the optimization effectiveness of each optimization on the function according to whether the hash value of the function IR changes before and after each optimization is completed by each function.
Wherein if the hash value of any function IR changes before and after any function executes any optimization, the any optimization is valid for the any function, the optimization validity is set to 1, otherwise, the optimization is invalid, and the optimization validity is set to 0.
And S3, recording the hash value of the triple < function IR before optimization, the hash value of the function IR after optimization and the optimization effectiveness > in a function optimization map table.
The step S3 specifically includes:
Step S301, map (funcName, passName) = < hash (pfuncName _ passName _ir), hash (funcName _ passName _ir), ISEFFECTIVE > table is created. Here, the hash (pfuncName _ passName _ir) represents the hash of a certain function IR before the optimization passName is performed, and p before the name represents previous. The hash (funcName _ passName _ir) represents the hash of some function IR after the optimization passName.
Step S302, setting the validity of optimization. Setting according to whether the hash value of the function IR before and after optimization changes, if the hash value of the function IR before and after optimization changes, setting the optimization effectiveness as 1, otherwise, setting the optimization effectiveness as 0.
And step S303, optimally storing the function optimization map table according to whether the two optimizations are adjacent. The specific optimized storage method is as follows:
Referring to fig. 5, it is assumed in this figure that the optimization process is:
namely P1 is adjacent to P2, P2 is not adjacent to P3, P3 is adjacent to P4, and P1, P2, P3 and P4 are all optimized pass.
For non-adjacent optimizations, hash values hash (pfuncName _ passName _ir) and hash (funcName _ passName _ir) before and after the optimization must be calculated. Such as (F1, P1), (F1, P3) in Table 1, and the like.
For two adjacent optimizations, that is, no other processing process exists in the middle, the hash value of the IR after the LAST optimization can be used as the hash value before the current optimization, that is, (F1, P2), (F1, P3) and the like in the table 1, so that one calculation can be omitted, the table space is saved, and the hash value before the current optimization is represented by only using a LAST mark and is the same as the hash value after the previous optimization. There is no need to store the hash before this optimization again, such as < LAST, hash (f1_p2_ir), 1>.
Table 1 function optimization map table
In the map table, a hash (pf1_p1_ir), a hash (f1_p1_ir), a hash (pf1_p1_ir), a hash of 1> indicates that the F1 function does not perform the hash value of the IR before the P1 optimization, and a hash (f1_p1_ir) indicates that the F1 function performs the hash value of the IR obtained after the P1 optimization. 1 indicates that the P1 optimization by the F1 function is effective. The LAST in table 1 indicates that the hash value after the LAST optimization was completed is used for two adjacent optimizations.
When the hash values before and after the optimization are the SAME, the hash values after the optimization can be replaced by SAME. When ISEFFECTIVE is 0, i.e., the optimization is invalid, i.e., the hash value is unchanged, the hash (f1_p1_ir) is marked as SAME, i.e., the SAME as the hash (pf1_p1_ir), such as (F1, P4).
For the function optimization table map(funcName, passName)= <hash(pfuncName_passName_IR),hash(funcName_passName_IR),isEffective>,, to simplify the expression, the triples stored in the table are
The 1 st element hash (pfuncName _ passName _ir) is written as map (funcName, passName) [1],
The 2 nd element hash (funcName _ passName _ir) is written as map (funcName, passName) [2],
The 3 rd element ISEFFECTIVE is written as map (funcName, passName) [3].
The function optimization map table can be used as a hidden file in a source code directory for next compiling.
And S4, calculating a hash value of the current function before the current optimization is executed in the second compiling.
And S5, searching in the function optimization map table according to the current function and the current optimization, and comparing the hash value of the function IR before the current optimization is executed by the searched current function with the hash value of the function IR before the current optimization is executed by the current function calculated by the second compiling.
And S6, determining whether the current optimization needs to be executed or not according to the comparison result and the value of the current optimization, which is found in the function optimization map table, on the optimization effectiveness of the current function.
Wherein, the hash value hash (pcurrentFunc _ currentPass _ir) before the current currentFunc function optimization is calculated. Map is looked up in the previously established function optimization map table (currentFunc, currentPass).
Whether the function is modified is determined based on the hash value of the pre-optimization function IR recorded in the lookup table and the calculated hash (pcurrentFuc _ currPass _ir). Specifically, the value < hash (pcurrentFunc _ currentPass _ir), hash (currentFunc _ currentPass _ir), ISEFFECTIVE > of the map (currentFunc, currentPass) is looked up in the function-optimized map table. If the calculated hash (pcurrentFunc _ currentPass _IR) and map (currentFunc, currentPass) 1 in the table are equal, the description function is not modified, and if not, the description function is modified.
If the function is modified or the optimization valid bit in the corresponding map entry is 1, then the currentPass optimization is performed. Otherwise, the optimization is deemed invalid and is skipped directly.
The following are two cases in which optimization needs to be performed:
① If the currentFunc function is not modified and the map (currentFunc, currentPass) 3 in the map table, ISEFFECTIVE, is 1, this indicates that the optimization is valid for the function and the optimization needs to be performed.
② If the currentFunc function is modified, the optimization passName is performed. Because the function has changed, it cannot be predicted whether currentPass is valid for the modified function based on the existing map table.
After step S6, step S7 is further included, when the optimization needs to be performed, after the currentPass is performed, the hash value of the IR of the function after the execution is calculated, and the function optimization map table is updated.
Specifically, S7 includes the following sub-steps:
step S701, after the optimization is performed, a hash value hash (currentFunc _ currentPass _ir) of the IR of the currentFunc function after the optimization is calculated.
Step S702, according to whether the hash value of the IR changes before and after the optimization, that is, whether the calculated hash (funcName _ passName _ir) is equal to the calculated hash (pfuncName _ passName _ir), setting ISEFFECTICE, wherein ISEFFECTIVE is 1 when the hash value and the hash value are unequal, and ISEFFECTIVE is 0 when the hash value and the hash value are equal.
In step S703, the map (currentFunc, currentPass) in the function-optimized map table is updated to < hash (pfuncName _ passName _ir), hash (funcName _ passName _ir), ISEFFECTIVE > for use in subsequent compilation.
The compiler performance optimization method provided by the invention has the following advantages:
(1) The information of the last compiling time is recorded in a simple and rapid mode to guide the compiling, reduce redundancy optimization and accelerate the compiling speed.
(2) Each optimized IR may be stored to determine whether the function changes to guide compilation to skip a certain function optimization, but this may require a lot of memory space, and determining whether the function changes requires a lot of computation, which may be slow to run.
(3) The built function optimization map table is quick, simple and efficient, can be directly searched in the next compiling process, and optimally stores the function optimization map table.
In the foregoing embodiments, the descriptions of the embodiments are focused on, and for those portions of one embodiment that are not described in detail, reference may be made to the related descriptions of other embodiments.
It will be appreciated by those skilled in the art that embodiments of the present invention may be provided as a method, system, or computer program product. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.
The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
While preferred embodiments of the present invention have been described, additional variations and modifications in those embodiments may occur to those skilled in the art once they learn of the basic inventive concepts. It is therefore intended that the following claims be interpreted as including the preferred embodiments and all such alterations and modifications as fall within the scope of the invention.
It will be apparent to those skilled in the art that various modifications and variations can be made to the present invention without departing from the spirit or scope of the invention. Thus, it is intended that the present invention also include such modifications and alterations insofar as they come within the scope of the appended claims or the equivalents thereof.