Value Numbering ( eng. Value Numbering ) is one of the types of , used by the optimizing compiler to detect in the code ( ) of the program. Optimization can take advantage of the results of the analysis: , , removal of general subexpressions [1] , optimization of conditions ( if Optimization ) [2] , [3] . The analysis breaks the set of all considered operations generating a result (number or predicate ) into subsets of operations, in each of which all operations produce the same result regardless of input . Such subsets (as well as, sometimes, numbers of these subsets [4] ) are called congruence classes or equivalence classes [3] . The congruence classes are numbered, the congruence class number is called the value number . Thus, the task of numbering values can be formulated as follows: assign a unique number to each value generated within the considered section of the program [3] . To implement the numbering of values, you may need a constructed Def-Use-graph or SSA-form [4] . The numbering of values can be local (within one base unit ), global (within the CFG-graph of one procedure) and interprocedural [3] .
Content
Examples
Algorithms
Application
Using the results of numbering values in the algorithms of some optimizations related to the removal of redundant computations can significantly increase their efficiency and simplify the implementation [5] .
Removing common subexpressions
Streamline conditions
The simplest example of applying optimization conditions Optimization of conditions - removal of redundant conditional calculations. The control graph can contain, so-called, If-nodes — nodes that have two outgoing arcs, and, accordingly, on a set of operations necessary to select one of these arcs. We will call such a set of operations conditional calculation . If the control graph contains two If-nodes, one of which is dominated by the other (or at least one arc outgoing from it), then, provided that the numbers of the values of the results of their conditional calculations coincide (or under the condition that some value of the result of the lower conditional calculation follows from any value of the result of the upper conditional calculation), the calculation in the lower node can not be repeated. Condition optimization removes conditional calculations at the dominated node and removes the corresponding outgoing arc. In addition to removing redundant computations, the transformation can make some nodes and arcs of the control graph unreachable from the root node, that is, to detect an unreachable code . The simplest example of applying conditions optimization is shown in the diagram: if the variables a and b belong to the same congruence class, then the condition a ≥ 7 implies that b ≥ 7, then the condition b ≥ 6 is always fulfilled, and the condition b <6 cannot be fulfilled. The comparison operation and its corresponding transition operation at node 2 are redundant. Optimization of conditions will remove redundant conditional calculations in node 2 and remove the arc from node 2 to node 4. As a result, the program execution time for a ≥ 7 decreased due to the removal of the comparison operation, as well as the size of the code. |
Inline substitution
Inlining is an optimization that performs substitution of the function body instead of its call operation (CALL). The goal of the conversion is to reduce the number of control transfers, that is, to reduce the number of CALL and RETURN operations, as well as to make more efficient optimization work analyzing only one translation unit (and there are most of them). Inline cannot be applied to all functions in the program. For example, if you substitute a function that is too large instead of a call, the size of the code can increase significantly. In the process of performing the optimization, it is important to find a compromise between increasing the code and the speed of its execution. Interprocedural numbering of values makes it possible to refine this analysis, since, even if the size of the function being injected is too large, it may contain redundant calculations, which, after substitution and further removal of redundancies, will disappear. Thus, interprocedural numbering of values allows us to operate not with the size of the function being substituted, but with increasing the size of the code after substituting this function. A special case of this optimization is a partial inline, in which only a part of the called function is substituted, for example, containing the most frequently executed paths.
Notes
- А. A. Filippov. Methods for removing redundancies at the compilation of programs. Abstract , 2009 ( text Archived )
- ↑ Stepnov D. V. Optimization of the control graph of programs with redundant conditional calculations. 2012 ( PPT Archived )
- ↑ 1 2 3 4 A. Yu. Drozdov, A. V. Kan. Analysis "Interprocedural numbering of values." In Computers in the educational process , 2005, No. 5 ( text Archived )
- ↑ 1 2 Drozdov A. Yu., Novikov S. V., Bokhanko A. S., Galazin A. B. Global data flow graph and its role in conducting optimizing program transformations ( text archived )
- ↑ Filippov A. N. The method of numbering values and the use of its results in optimizing programs. In Information Technology , 2009, No. 4 ( text Archived )