The main topic in this section is to investigate the different effects of the trans-formation according to the different goals defined in Section7.1. On these three goals, only two of them will be considered: speed and size of the generated pro-gram. Indeed, the measure of power consumption is inaccessible in this thesis.
Intensive experiments have already been conducted on this topic ([7, 3]), and the integration of such results in this phase-ordering mechanism is left for future work, as explained in Section9.
The first subsection deals with a theoretical analysis of the effects of differ-ent transformations, and aims at finding the potdiffer-ential improvemdiffer-ents that these transformations may perform either on the speed or on the size of the program.
Again, for the sake of readability, only the part concerning Constant Folding is shown in this section. The remaining transformations can be found in Ap-pendix C.2. The second subsection introduces an experimental study in order to evaluate the results found in the first subsection.
7.2.1 Theory
In this part, the effects of Constant Folding are considered in order to establish whether the transformation is improving the speed or the size of the input pro-gram. As the Precalculation Process is applied after some transformations in the metric-based phase-ordering algorithm, a concluding remark is taking the Precalculation into account to evaluate the overall effect of the sequence of the two transformations in that case.
Finally all the effects of the transformations considered are summarized in the last part of this subsection.
7.2.1.1 Effects of Constant Folding
The transformation to be analyzed is the Constant Folding transformation, de-scribed in Section3.4.1.
Functional effect:
The aim of this optimization is to look for all variables assignments with constant values on the right side, and to replace further in the program the variables with their constant value.
Consequences on the program:
When replacing a variable’s occurrences by its constant value, the variable itself is less and less used. In fact, most of the time, all the occurrences of the variable between the first definition and the next assignment to this variable are replaced by a constant value, which makes the variable becomes dead at this point of the program. However, the transformation does not remove the dead assignments created.
⇒Conclusion:
∗ Size : The effect of Constant Folding on the size of the program varies depending on the variables replaced. Indeed, replacing a vari-able with a long name can improve the size of the program, while replacing a one-letter variable withtrue or false can degrade the size for example.
∗ Speed⊕: A successful Constant Folding call will improve the speed
of the program, as runtime variable evaluations are replaced by simple access to constant values.
∗ Associated with Precalculation: Constant Folding will still im-prove speed, while the effect on thesizeare still impossible to pre-dict, but there is more chance that Precalculation improves the size, as Constant Folding may create constant expressions to be computed.
7.2.1.2 Summary
The effects of the transformations considered in this thesis are summarized in Figure 7.1. For each case, a ⊕means that the transformation is very likely to improve the size or speed, a means it is likely to degrade the size or speed, and ameans that the effects can vary depending on some parameters, such as the length of the variables used for Constant Folding, or the number of expressions replaced for Common Subexpressions Elimination.
Size Speed
CP ⊕ ⊕
ES ⊕
CSE ⊕
DCE ⊕ ⊕
CM ⊕
CF ⊕
Figure 7.1: Effects of transformations
This study points out that all the transformations considered should improve the speed of the program, characterized in this thesis by the number of instructions executed. On the other hand, all are not always improving the size of the program. Some, like Code Motion, are even very likely to degrade it. For others, like Common Subexpressions or Elimination of Signs, it depends on some properties of the input program.
7.2.2 Experimental results
An experimental study have been conducted using the benchmark suite in order to get some insights about the effects of the transformations on the size and the speed of the program.
Figure 7.2 (respectively 7.3) represents the percentage of transformation calls improving or degrading the size of the program (respectively the speed of the program, measured by the number of instructions executed).
Figure 7.2: Percentage of transformation calls improving/degrading the size
These measures have been made using the regular-expression based approach in order to run a lot of different orders of optimization phases on the benchmark programs. Then, after each transformation call in each regular expression, the relative improvement of the size or speed of the program has been measured using the following coefficient:
N =Sbef oreS −Saf ter
bef ore
whereSis either the size of the program or the number of instruction executed.
These figures show that:
• the speed of the program is never degraded except for a very few percent-age of Code Motion calls. The cause of this degradation is very likely to be,
Figure 7.3: Percentage of transformation calls improving/degrading the speed as mentioned in the theoretical analysis of the effects of Code Motion (in AppendixC.2), the existence of a loop containing invariants and which is only executed once. Otherwise, as expected, all the other transformations are improving the speed of the program (though sometimes Precalculation is not improving, probably only removing uselessskip statements).
• only two transformations (and Precalculation) are always improving the size of the program: Dead Code Elimination and Copy Propagation. Elim-ination with Signs improved the size of the program more often than not, but the other three transformations are very likely to degrade it, especially Code Motion which never improved it.
This corroborates the previous analysis, and gives some useful insights on the proportion in which Constant Folding, Elimination with Signs and Common Subexpressions Elimination can improve or degrade the size of the program.
Figure 7.4 and7.5 shows the average relative improvement of the transforma-tions on the size and the speed of the program.
These figures show the importance of using Dead Code Elimination in both case (speed or size improvement), and permit to establish some comparison between the different transformations.
Figure 7.4: Average improvement of transformations on the size of the program
Figure 7.5: Average improvement of transformations on the speed of the pro-gram
For example, it shows that Copy Propagation should be of better use for re-ducing the size than Constant Folding or Common Subexpressions Elimination, but Dead Code Elimination is likely to be more efficient than Copy Propagation.
Thanks to these insights, a new mechanism for the comparison of the metrics can be designed, using coefficients to weight the different metrics, in order to improve the phase-ordering mechanism.