Candidate Best Optimizations Sequences for Code Size Reduction

Recent compilers contain various optimizations, which can frequently be manually switched on or off via compiler flags or switches. With so many optimizations available to compilers, it's practically hard to choose which is best for a single program. Traditionally, compiler developers have operated under one of two assumptions: either a predefined optimization sequence is "good enough" for all programs, or supplying users with an extensive collection of optimization flags is sufficient, so putting the burden to the user [1-3].

An optimization sequence is a collection of optimization passes that can be applied on the program's Intermediate Representation (IR). Choosing the right optimization pass and the right order for given application is called phase-ordering problem. The set of all optimization sequences is known as the optimization sequence space, and it is incessantly large. To explain the phase-ordering problem, let us establish a boolean vector o, with components oi representing the various compiler optimizations. Each optimization oi can be activated (oi=1) or disabled (oi=0). The vector o depicts a phase-ordering compiler optimization sequence in the n-dimensional factorial space |Ophases| = n!, where n is the number of optimizations. However, the provided limit is for a made easier phase-ordering problem with a constant vector length and lack of repetitions. Allowing repetition and dynamic duration broadens the design possibilities to:

$\mid Ophases-repetition \mid=\sum_{i=0}^m n^{\mathrm{i}} \ldots$       (1)

where, n is the number of optimizations being investigated, and m is the maximum length for the optimization sequence. For instance, with n optimizations and m=10, |Ophases repetition| will result in more than 11 billion various combinations for each application [4]. Many default optimization levels are provided by compilers, e.g., O1, O2, O3, Oz Some of these optimization levels O2, O3 focus on enhancing the program execution time, while the Os, Oz are dedicate to dealing with reducing code size [5-7]. Through the execution of the program, all the optimization flags will be turned off by default, and the expert can turn some or all of them on according to the program's needs. For example, the GCC has more than 200 passes while the LLVM Clang and opt have more than 100 passes [8-10]. The sequence of these passes called the optimization sequence. Choosing the right sequence can help the programmers achieve better performance [11, 12].

Clearly, some optimizations can increase the code size, like loop unrolling or procedure inlining, while others can decrease it, for example, dead code removal or strength reduction [13, 14].There are two reasons that arise to answer the question of "why is there a need to turn off some optimization passes instead of applying all of them ". The first is, the characteristics of some passes might not match with the characteristics of the program. The second reason is that some of these passes have a negative impact on the quality of the resulting program [15-18]. Thus, instead of speeding up the program or decreasing the program size, the reverse may occur. An illustrative example involves the employment of inlining, a technique that substitutes a function invocation with its corresponding body. This particular transformation has the potential to cause a phenomenon known as code expansion, subsequently increasing the potential for cache misutilization [19, 20]. The execution time of the generated code is beyond the scope of this paper. This paper is primarily focus on the code size, and the resulting code may have a reduced size. The rest of the paper is organized as follows: Section 2 introduces some of the related works. Section 3 details the suggested method and explains it is implementation. In Section 4, the experimental results obtained from the proposed methods are presented. Finally, Section 5 summarizes the findings of suggested method.

1.png

Figure 1. The block diagram of the proposed method

3.1.2 Compute program size

A wide range of different programs, 50 programs, are extracted from three benchmark suites: PolyBench, Shootout, and Stanford. The programs' size is computed in which each program (p) is executed with all optimization sequences that are generated prviously. Moreover, these programs are compiled using Os and Oz flags and their size are computed.

Table 1. Os and Oz optimization passes [24, 25]

3.2 Extracting the selective sequences

According to the previous stage, the average of programs size obtained by compiling these programs with seq (SI) compared to the average programs size obtained by compiling the identical programs with the Os and Oz flags. The sequence with average program sizes less than the one with Os or Oz flag adds to the singed table. This procedure carried out for every sequence.

3.3 Construction sings table

Each program is compiled with the Os and Oz flags, and their execution times are stored in the Sign table. Subsequently each one of the two thousand sequences is used to compile all the programs. The sequences that result in an average size for all programs smaller than those created by Os or Oz are recognized and included into the Sign table as shown in Figure 2.

The first raw of this table represents the extracted sequences and the first column represents the programs' names. The entry to this table is a sign to give us an indicator if the i-th sequence reduces the program size or no. Finally, the files name of dynamic features for these programs are also added to the Sign Table.

3.4 Compute the similarity

For unseen programs (new programs) and the programs in the Signs Table, their dynamic features are extracted. Perf/Linux tool is used to extract these features (36 events). Performance counter events are used to reflect the program behavior. Table 2 illustrates these events. The process of quantifying similarity between the unobserved program and the programs contained within the signs table is undertaken. The sequences corresponding to the most similar programs are selected as potential candidates to optimize the unseen program.

Multiple metrics are available for the quantification of similarity. One commonly employed approach is the utilization of the cosine metric, as illustrated through the equation presented herein.

$\operatorname{Sim}(\mathrm{p}, \mathrm{pi})=\frac{\sum_{w=1}^m p w * p i w}{\sqrt{\sum_{w=1}^m p w^2 *} \sqrt{\sum_{w=1}^m p i w^2}}$         (2)

where, the symbol 'p' denotes the unseen program, which refer to a program yet to be observed, while 'pi' signifies a set of supplementary programs, herein referred to as training programs [26, 27]. The new program that is yet to be observed, its level of similarity is determined by extracting its dynamic features and evaluating them against those of all other programs, in the signs table.

Table 2. Perf events [1, 28]

3.5 Candidates sequences for unseen program

After computing the similarity between the unseen program and the programs in the signs table, the most similar programs are selected. Then, the unseen program is compiled using the list of sequences that belong to the selected programs. Finally, sequences that produces lower the code size are chosen.

In this paper, a method to reduce the code size based on the signs table is proposed. Two thousand sequences are randomly generated. Each sequence compiled with 50 programs. Then the average program size for 50 programs is computed, where the sequence that gives the average program's size better than -Oz flag is extracted and put in the signs table. A set of eight unobserved programs are employed for validating the method. After computing the similarity of the unseen program, the sequences that belong to the most similar program are candidates to optimize it. The results show that for most eight unseen programs, the produced programs are 9% smaller than -Oz. In our future work, we need to address other types of features and study their effect on program size. Furthermore, we plan to investigate the power of machine learning techniques for code size reduction.