Reduced O3 subsequence labelling: a stepping stone towards optimisation sequence prediction

Abstract

Finding a good compiler autotuning methodology, particularly for selecting the right set of optimisations and finding the best ordering of these optimisations for a given code fragment has been a long-standing problem. As the rapid development of machine learning techniques, tackling the problem of compiler autotuning using machine learning or deep learning has become increasingly common in recent years. There have been many deep learning models proposed to solve problems, such as predicting the optimal heterogeneous mapping or thread-coarsening factor; however, very few have revisited the problem of optimisation phase tuning. In this paper, we intend to revisit and tackle the problem using deep learning techniques. Unfortunately, the problem is too complex to be addressed in its full scope. We present a new problem, called reduced O3 subsequence labelling – a reduced O3 subsequence is defined as a subsequence of O3 optimisation passes that contains no useless passes, which is a simplified problem and expected to be a stepping stone towards solving the optimisation phase tuning problem. We formulated the problem and attempted to solve the problem by using genetic algorithms. We believe that with mature deep learning techniques, a machine learning model that predicts the reduced O3 subsequences or even the best O3 subsequence for a given code fragment could be developed and used to prune the search space of the problem of the optimisation phase tuning, thereby shortening the tuning process and also providing more effective tuning results.

Keywords:

• Compiler autotuning
• compiler optimisation phase tuning
• evolutionary computation

1. Introduction

An optimising compiler performs a sequence of optimising transformation techniques, which are implemented as optimisation passes (or optimisation phases) and aim to transform a program to a semantically equivalent program that uses fewer computing resources or instructions. However, some passes are correlated and have positive or negative impacts to each other. For example, a program might not be vectorised if the licm pass (which performs loop invariant code motion) is not used (Kruse & Grosser, 2018). Therefore, how to determine the best sequence of passes for a program is a big research problem of compiler optimisations. In past research, evolution algorithms were used to solve this problem. However, since there are many optimisation passes in a compiler, the search space for the best sequence of passes is too large to be explored in reasonable time. There have been many kinds of research that use machine learning techniques to improve the speed of compiler optimisation tuning. The biggest challenge of such research is how to present program sources for machine learning models. With the rapid progress of deep learning technology, applying deep learning techniques to compilers has become a new research hotspot.

It seems that we can use the deep learning technique to find a way to present program structures more accurately and to predict the best sequences of passes for programs, but deep learning methods require an adequately large amount of training data. Unfortunately, preparing those training data could be time-consuming for the problem of optimisation phase tuning (OPT) because we have to tune the compiler optimisations for many programs, and this involves lots of compilation and running processes. A trivial solution is to use a brute-force search method to find the best sequence of passes for a program, but it takes a huge amount of time to explore all sequences even for a single program. Perhaps, as a result, recent researches have seldom focused directly on optimisation pass analysis and prediction but rather on simpler compilation tuning problems, such as tuning for heterogeneous mapping or the thread coarsening factor (Ben-Nun et al., 2018b; Cummins et al., 2017).

An alternative approach to brute-force search is to use evolutionary computation as a tool for generating good sequences of passes for a program so as to speed up the process of collecting training data. However, evolutionary computation is used to seek a good enough solution rather than the optimal one, so the sequences produced by an evolutionary computation-based tuning algorithm are likely the best sequence. Unfortunately, optimisation passes are not guaranteed to be effective in improving the program execution performance, so there might be useless passes in an optimisation sequence. These useless passes are considered noises for machine learning. It is as if we use sentences that are full of redundant words as training data for building a machine learning model for language translation. Simplifying sentences by word properties is an important trick in natural language processing, so for compiler tuning with machine learning, we also need a technique to simplify optimisation sequences to eliminate possible noises of machine learning.

In view of the aforementioned problems, we attempt to reduce both the noises and the variations in order to improve machine learning performance. We attempt to change the objective of machine learning from predicting the best optimisation options of a program to predicting the reduced O3 subsequences of the program. We believe that optimisation-level three (i.e. O3) is a combination of optimisation options that are selected and ordered by compiler experts. The O3 optimisation sequence might not be the best for a program, but for most programs the O3 option results in acceptable performance improvement. However, the O3 optimisation sequence may also contain useless optimisations. A reduced O3 subsequence is thus defined as an O3 optimisation subsequence that contains no useless optimisations. We expect to use machine learning techniques to predict reduced O3 subsequences of a program, and then use the reduced O3 subsequences as the basis (as a reduced search space) for compiler autotuning.

2. Optimisation phase tuning and its difficulties

2.1. Problem formulation

The OPT problem is to select the right set of compiler optimisation passes and find the best ordering of these passes for a given program so that the program achieves the best performance. The solution of the problem involves searching the best sequence from arbitrary lengths of sequences of repeatable optimisation passes, though not all optimisation passes are considered repeatable. The search space of the problem is extremely huge for a modern compiler, which is commonly equipped with many optimisation passes.

Suppose a compiler C has n distinct optimisation passes: $O=\{O_1,O_2,\dots ,O_n\}$, and $OptBag(O,M)$ is a multiset containing the n distinct optimisation passes: $\{m_1\cdot O_1,m_2\cdot O_2,\dots ,m_n\cdot O_n\}$, where M is a sequence of positive integers $(m_1,m_2,\dots ,m_n)$ and $m_i$ denotes the number of repetitions of $O_i$ in the multiset; that is, optimisation pass $O_i$ occurs $m_i$ time(s) in the multiset. A possible optimisation sequence, with $O_i$ being used at most $m_i$ time(s), in compiler C is a k-permutation of $OptBag(O,M)$, a sequence of length k of elements of $OptBag(O,M)$, where k can be any positive integer that is smaller than or equal to the size of the multiset ($|OptBag(O,M)|$, which equals to $m_1+m_2+\cdots +m_n$). In other words, all possible optimisation sequences form a set $\mathcal{S}(\mathcal{P}(OptBag(O,M)))$, where $\mathcal{S}(x)$ denotes the permutation group of x and $\mathcal{P}(x)$ denotes the power set of x. For simplicity we denote $\mathcal{S}(\mathcal{P}(OptBag(O,M)))$ as $\mathbb{S}\mathbb{E}\mathbb{Q}(O,M)$, as indicated in Equation (1(1) $\mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\equiv \mathcal{S}(\mathcal{P}(\{m_1\cdot O_1,m_2\cdot O_2,\dots ,m_n\cdot O_n\}))$(1) ). (1) $\mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\equiv \mathcal{S}(\mathcal{P}(\{m_1\cdot O_1,m_2\cdot O_2,\dots ,m_n\cdot O_n\}))$(1) The number of all possible optimisation sequences is expected to be huge when n is large. According to Jurić and Šiljak's formula of number of permutations of multisets (Željko & Šiljak, 2011), the number of k-permutations of $OptBag(O,M)$ can be written as (2) $P(k,M)=\sum (\genfrac{}{}{0ex}{}{c(i_1)}{{\lambda }_1})(\genfrac{}{}{0ex}{}{c(i_2)-{\lambda }_2}{{\lambda }_2})\cdots (\genfrac{}{}{0ex}{}{c(i_s)-{\lambda }_1-{\lambda }_2-\cdots -{\lambda }_{s-1}}{{\lambda }_s}),$(2) where $k={\lambda }_1{i}_1+{\lambda }_2{i}_2+\cdots +{\lambda }_s{i}_s,$ max$\{m_1,m_2,\dots ,m_n\}\ge i_1\ge i_2\ge \cdots \ge i_s\ge 1$, and $c(i)$ is the number of numbers $m_p$ that are not smaller than i, where ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_s,i_1,i_2,\dots ,i_s$ are integers, and $p=1,2,\dots ,n$. Consequently, the number of all possible optimisation sequences, with $O_i$ being used at most $m_i$ time(s), in compiler C can be written as (3) $P(M)=\sum _{k=1}^{|OptBag(O,M)|}P(k,M),$(3) which summarises the numbers of permutations of optimisation sequences whose length ranges from 1 to $|OptBag(O,M)|$. For example, considering a compiler with a set of optimisation passes $O_i=\{A,B,C,D,E\}$ and $M_i=(1,2,2,1,2)$ – and thereby $OptBag(O_i,M_i)=\{1\cdot A,2\cdot B,2\cdot C,1\cdot D,2\cdot E\}$ –, all possible optimisation sequences can be derived in Table 1. As listed in Table 1, with only five optimisation passes and three of them being used for at most twice, the number of all possible optimisation sequences [or $P(M_i)$, which equals $P(1,M_i)+P(2,M_i)+P(3,M_i)+P(4,M_i)+P(5,M_i)+P(6,M_i)$] is truly large. More specifically, there are 14, 457 possible optimisation sequences in the set of $\mathbb{S}\mathbb{E}\mathbb{Q}(O_i,M_i)$, which represents the search space of the OPT problem.

Table 1. All possible optimisation sequences of $OptBag(O_i,M_i)$, which form the set $\mathbb{S}\mathbb{E}\mathbb{Q}(O_i,M_i)$; $P(k,M_i)$, the number of k-permutations of $OptBag(O_i,M_i)$.

	$P(k,M_i)$	$\mathbb{S}\mathbb{E}\mathbb{Q}(O_i,M_i)$
k = 1	4	$\{A,B,C,D,E,$
k = 2	23	$AB,AC,AD,AE,BA,BB,BC,BD,BE,CA,CB,CC,CD,CE,DA,DB,DC,DE,EA,$
		$EB,EC,ED,EE,$
k = 3	96	$ABB,ABC,ABD,ABE,ACB,ACC,ACD,ACE,ADB,ADC,ADE,AEB,AEC,AED,$
		$AEE,BAB,BAC,BAD,BAE,BBA,BBC,BBD,BBE,BCA,BCB,BCC,BCD,$
		$BCE,BDA,BDB,BDC,BDE,BEA,BEB,BEC,BED,BEE,CAB,CAC,CAD,$
		$CAE,CBA,CBB,CBC,CBD,CBE,CCA,CCB,CCD,CCE,CDA,CDB,CDC,$
		$CDE,CEA,CEB,CEC,CED,CEE,DAB,DAC,DAE,DBA,DBB,DBC,DBE,$
		$DCA,DCB,DCC,DCE,DEA,DEB,DEC,DEE,EAB,EAC,EAD,EAE,EBA,$
		$EBB,EBC,EBD,EBE,ECA,ECB,ECC,ECD,ECE,EDA,EDB,EDC,EDE,$
		$EEA,EEB,EEC,EED,$
k = 4	354	$ABBC,ABBD,ABBE,ABCB,ABCC,ABCD,ABCE,ABDB,ABDC,ABDE,\dots ,$
		$EECA,EECB,EECC,EECD,EEDA,EEDB,EEDC,$
k = 5	1110	$ABBCC,ABBCD,ABBCE,ABBDC,ABBDE,ABBEC,ABBED,ABBEE,\dots ,$
		$EEDBA,EEDBB,EEDBC,EEDCA,EEDCB,EEDCC,$
k = 6	2790	$ABBCCD,ABBCCE,ABBCDC,ABBCDE,ABBCEC,ABBCED,ABBCEE,\dots ,$
		$EEDCBA,EEDCBB,EEDCBC,EEDCCA,EEDCCB\}$
k = 7	5040	$ABBCCDE,ABBCCED,ABBCCEE,ABBCDCE,ABBCDEC,ABBCDEE,\dots ,$
		$EEDCBCB,EEDCCAB,EEDCCBA,EEDCCBB\}$
k = 8	5040	$ABBCCDEE,ABBCCEDE,ABBCCEED,ABBCDCEE,ABBCDECE,\dots ,$
		$EEDCCABB,EEDCCBAB,EEDCCBBA\}$

Suppose Compiler is a function that generates the executable of a given program prog with an optimisation sequence $\overrightarrow{s}$ being applied by using compiler C, and Evaluator is another function that evaluates the performance of a given executable exec with specific input data in on a specific hardware platform, as indicated in Equation (4(4) $\begin{array}{rl}Compiler& :(prog,\overrightarrow{s})\mapsto exec\\ Evaluator& :(exec,in)\mapsto perf\end{array}$(4) ). The definition of performance can refer to a metric, such as the time elapsed (or the energy consumed) during the execution, the size of the executable, or even the combination of multiple metrics; in most scenarios, execution time is regarded as the performance metric, where the lower execution time, the higher performance. By taking the result of Compiler into Evaluator, we can derive a fitness function $\mathcal{F}$ that judges how good an optimisation sequence is for a given program prog with specific inputs in, as shown in Equation (5(5) $Fitness:((prog,\overrightarrow{s})\mapsto exec,in)\mapsto perf\Rightarrow {\mathcal{F}}_{prog,in}:\overrightarrow{s}\mapsto perf$(5) ). Finally, the OPT problem can be defined in Definition 2.1, and it is considered an optimisation problem which can be solved using evolutionary computation. (4) $\begin{array}{rl}Compiler& :(prog,\overrightarrow{s})\mapsto exec\\ Evaluator& :(exec,in)\mapsto perf\end{array}$(4) (5) $Fitness:((prog,\overrightarrow{s})\mapsto exec,in)\mapsto perf\Rightarrow {\mathcal{F}}_{prog,in}:\overrightarrow{s}\mapsto perf$(5)

Definition 2.1

The problem of optimisation phase tuning

Given a program prog with inputs in together with a multiset $OptBag(O,M)$, find an optimisation sequence $\overrightarrow{s}$, which belongs to $\mathbb{S}\mathbb{E}\mathbb{Q}(O,M)$, such that ${\mathcal{F}}_{prog,in}(\overrightarrow{s})$ is maximised, as shown in Equation (6(6) ${\mathcal{F}}_{prog,in}(\overrightarrow{s})=max\{{\mathcal{F}}_{prog,in}(\overrightarrow{a})\mid \mathrm{\forall }\overrightarrow{a}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\}$(6) ). (6) ${\mathcal{F}}_{prog,in}(\overrightarrow{s})=max\{{\mathcal{F}}_{prog,in}(\overrightarrow{a})\mid \mathrm{\forall }\overrightarrow{a}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\}$(6)

2.2. Optimisation phase tuning using machine learning

As indicated in Equation (3(3) $P(M)=\sum _{k=1}^{|OptBag(O,M)|}P(k,M),$(3) ), the search space of the OPT problem defined in Equation (6(6) ${\mathcal{F}}_{prog,in}(\overrightarrow{s})=max\{{\mathcal{F}}_{prog,in}(\overrightarrow{a})\mid \mathrm{\forall }\overrightarrow{a}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\}$(6) ) can be very large even when $|OptBag(O,M)|$ is moderate. Machine learning techniques, which allows machine to learn from past tuning experiences, have been used to directly or indirectly solve the OPT problem. Many prior studies reshaped the problem and used machine learning results to guide tuning actions and reduce the search space. Most of these studies focused on building two predictors: optimisation sequence predictors and speedup predictors (Ashouri et al., 2018, september). An optimisation sequence predictor is built upon a machine learning model that yields the best set of optimisation passes or sequences for a given program (Cavazos et al., 2007; Fursin et al., 2011; Kulkarni et al., 2004; Park et al., 2011), whereas a speedup predictor is based on a machine learning model that predicts the amount of speedup that can be obtained when an optimisation sequence is applied (Ashouri et al., 2016, 2017; Dubach et al., 2007).

No matter which problem a prediction model targets at, a difficult challenge is how to transform a sequence of program code into numerical features usable for machine learning. Many prior studies (e.g. Milepost GCC (Fursin et al., 2011)) extracted features from a program based on some statistics of static or dynamic instructions of the program and provided adequate results. However, the feature extractor in such studies does not consider the execution order of instructions as a program feature and thus likely fails to distinguish two programs with almost identical computation tasks but slightly different computation orders, which may determine whether a specific optimisation pass should be applied. For example, functions slp_vectorizable and less_slp_vectorizable listed in Figure 1 are semantically equivalent but have slight differences in the order of the operations in lines 2 and 9. The effect of the slp-vectorize optimisation pass (Lattner & Adve, 2004) on these two functions are significant different, where slp_vectorizable is fully vectorised. One may design a feature extractor that also considers the sequence or the structure of a program, but it is likely to be a challenging task. Moreover, there might be more features to be developed in order to capture the important characteristics of the program for better machine learning results.

Figure 1. An example in which two functions that are semantically equivalent but slightly different in the order of operations are interpreted differently by the slp-vectorize compiler optimiser (Lattner & Adve, 2004), thereby resulting in different optimisation results.

With the development of deep learning techniques, automatic feature extraction has been made feasible (Cummins et al., 2017; Park et al., 2012), and therefore end-to-end prediction models have become possible. Nevertheless, past researches that utilised deep learning techniques rarely focused on the OPT problem but the problem of parameter tuning for specific optimisation passes, such as finding the optimal heterogeneous compute device mapping or the optimal thread coarsening factor (Ben-Nun et al., 2018a; Cummins et al., 2017). This is attributed to fact that the parameter tuning problems usually have a smaller search space, whereas the OPT problem is too complex to be effectively solved using deep learning techniques.

2.3. Useless optimisation passes

Despite the absence of a practical optimiser sequence predictor, compiler designers have done extensive work to determine some fixed optimisation sequences and provide compilation options (e.g. -O1, -O2, and -O3) for compiler users to optimise their programs with these optimisation sequences. It is well-known that the fixed optimisation sequences, especially the O3 sequence, can yield good results in terms of performance for many programs, and sometimes it can be quite difficult to find another optimisation sequence that delivers better results. Nevertheless, some passes of the optimisation sequences may fail to transform the programs or even transform the programs negatively. These optimisation passes are considered useless for the programs since they provide no benefit to the programs. The fact that a pass might be useless for a program seems intuitive – otherwise selecting the right set of compiler optimisation passes is unnecessary, but such fact has a significant impact on solving the OPT problem. For example, if someone attempts to use a naïve genetic algorithm to find the best optimisation sequence, the genetic algorithm is probably not effective. The genetic algorithm is likely to be stuck at a local optimum sequence since a sequence might just evolve one with some useless passes to another with some other useless passes during the evolutionary process; it is like someone randomly walks into a basin and is trapped in the basin.

To address the possible issues that can arise from useless passes when solving the OPT problem, we introduce a concept of the effectiveness of passes to quantify the strength of a pass on a specific program and input. The effectiveness of a pass $O_i$ on a program prog with inputs in is defined as the maximum benefit in the performance of the program execution that results from the pass for all possible optimisation sequences that contain the pass, as indicated in Equation (7(7) $\begin{array}{rl}{\mathbb{S}\mathbb{E}\mathbb{Q}}_{O_i}(O,M)& \equiv \{\overrightarrow{a}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\mid O_i\in \overrightarrow{a}\}\\ {\text{Effectiveness}}_{prog,in}(O_i)& =max\{{\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})\mid \mathrm{\forall }\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{O_i}(O,M),\\ & \overrightarrow{t}=\overrightarrow{s}\setminus O_i\},\end{array}$(7) ). (7) $\begin{array}{rl}{\mathbb{S}\mathbb{E}\mathbb{Q}}_{O_i}(O,M)& \equiv \{\overrightarrow{a}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\mid O_i\in \overrightarrow{a}\}\\ {\text{Effectiveness}}_{prog,in}(O_i)& =max\{{\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})\mid \mathrm{\forall }\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{O_i}(O,M),\\ & \overrightarrow{t}=\overrightarrow{s}\setminus O_i\},\end{array}$(7) where ${\mathbb{S}\mathbb{E}\mathbb{Q}}_{O_i}(O,M)$ represents the set of all possible optimisation sequences that contain $O_i$ for the given $OptBag(O,M)$, and $\overrightarrow{t}$ is a sequence that is derived from $\overrightarrow{s}$ and contains no $O_i$. The concept of effectiveness of a pass is trivial: the more the performance benefit the pass can deliver, the more effective the pass is. Of course, determining the effectiveness of a pass on a program will take a long process by evaluating the program with all possible optimisation sequences that involve the pass being applied, as well as the corresponding optimisation sequences in which the pass is removed. Nevertheless, one may still get a rough figure of how effective a pass is by a sampling methodology. For example, Table 2 listed the estimated effectiveness of some LLVM passes on two programs (loop_unroll and stepanov_abstraction from the LLVM test suite), where the estimated effectiveness of each pass is obtained by running a program with 100 different subsequences (randomly sampled) of the LLVM O3 optimisation sequence being applied. According to Table 2, we found that passes like inline, instcombine, and instcombine had a significant impact on stepanov_abstraction, while passes like globalopt, deadargelim, argpromotion, and correlated-propagation seemed useless for stepanov_abstraction.

Table 2. Estimated effectiveness of some LLVM passes on programs loop_unroll and stepanov_abstraction.

Program	loop_unroll	stepanov_abstraction
Pass
forceattrs	0.002	0.007
globalopt	0.028	0.000
deadargelim	0.013	0.000
inline	0.001	0.702
argpromotion	0.029	0.001
early-cse-memssa	0.001	0.077
jump-threading	0.001	0.033
instcombine	0.001	0.693
pgo-memop-opt	0.025	0.007
simplifycfg	0.010	0.033
loop-rotate	0.010	0.132
instcombine	0.013	0.748
correlated-propagation	0.070	0.002
licm	0.002	0.088
globaldce	0.000	0.070

Apart from adversely affecting an evolutionary process, useless passes also disturbs the training process of machine learning-based prediction models that are discussed in Section 2.2. Useless passes are considered noisy training data for machine learning. Taking an optimisation sequence predictor as an example, to build a prediction model, a large sample in terms of optimisation sequences and their consequent effects is required as a training sample of the model. Suppose we are building the model with the samples listed in Table 3, which indicates the execution times of two programs (matmul4x4 and recursive from the LLVM test suite) when some optimisation sequences that are sampled from the LLVM O3 optimisation sequence were applied. An optimisation sequence in the table is represented as a bit vector in which each bit represents whether the corresponding optimisation pass is applied and the corresponding optimisation passes of a vector are memtoreg, simplifycfg, tailcallelim, memcpyopt, sroa, loop-rotate, and slp-vectorize. According to Table 3, we observe that optimisation sequence 1111111 delivered the best results for both of the two programs, but the ideal training data for this model in this case are optimisation sequences 0001101 and 1110010 (and their consequent results). This is because 1111111 contains some useless passes for both of the two programs; the model is likely unable to differentiate the two programs if 1111111 was treated as a golden label. Of course, with a large amount of training data, machine learning methods are more capable of handling noises than traditional statistical techniques. However, it takes too much long time to generate training data – each training datum is obtained by compiling a program with a certain optimisation sequence and also executing the program, and these two processes can be very time consuming, especially for the later process. More importantly, as mentioned in Section 2.1, the space of all possible optimisation sequences is too large to be fully or even moderately explored. Compared to other deep learning-powered predictors, such as image and speech recognitions, deep learning-based optimisation sequence predictors are still immature because it is tough to build an effective prediction model if there are no sufficiently large amount of training data.

A possible solution to the aforementioned problem is to use a genetic algorithm to generate appropriate, effective training data (or the golden labels) for machine learning, but nevertheless, a naïve genetic algorithm will probably fail to achieve this goal as mentioned earlier in this section. We believe this is perhaps why previous studies on the OPT problem using machine learning have often focused on only the performance gain but not the accuracy of the machine learning models. We boldly conclude that the OPT problem is difficult to solve because not only is the problem space huge but also useless passes act as a barricade against successfully solving the problem.

Table 3. The execution times (in seconds) of matmul4x4 and recursive when some sampled optimisation sequences were applied. A bit vector represents the optimisation sequence that was applied to a program, and each bit of a vector represents whether the corresponding optimisation pass was applied. The corresponding optimisation passes of a vector are memtoreg, simplifycfg, tailcallelim, memcpyopt, sroa, loop-rotate, and slp-vectorize.

Sequence	1111111	0001111	0001101	1010000	1110010
Benchmark
matmul4x4	0.27	0.27	0.27	1.12	1.12
recursive	0.43	0.85	0.85	0.45	0.43

3. Reduced O3 subsequence labelling

In order to cope with the two problems (i.e. a vast problem space and annoying useless optimisation passes) concluded in Section 2.3, we introduce a new problem, called reduced O3 subsequence labelling (RO3SL), which aims to discover reduced O3 subsequences that are considered as key hints for obtaining appropriate training data to model an effective, accurate optimisation sequence predictor. In this sense, RO3SL can be regarded as a subproblem of OPT from two main perspectives, which address the two aforementioned problems: (1) RO3SL has a smaller problem space than OPT, and (2) RO3SL is designed to assist in solving the OPT problem by eliminating annoying useless passes. As indicated by its name, the RO3SL problem has a problem space that is formed by O3 subsequences, which are subsequences of the O3 optimisation sequence, rather than all possible optimisation sequences. As we have discussed in Section 2.3, in practice the O3 optimisation sequence typically perform well for a wide range of different programs; therefore, it seems reasonable to use only the subsequences of the O3 optimisation sequence as the training data to get around the issue of the enormous problem space. Furthermore, RO3SL is designed to identify all the reduced O3 subsequences for a given program and inputs, where a reduced sequence is defined as an optimisation sequence that does not contain any useless passes, thereby eliminating possible training noises that are caused by useless passes.

3.1. Investigation on O3 subsequences

Despite the reduced problem space, the number of possible O3 subsequences can still be huge when the length of the O3 optimisation sequence is long. Taking LLVM compiler infrastructure, whose O3 optimisation sequence consists of 92 passes, as an example, the number of possible O3 subsequences (i.e. the size of set ${\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}$) exceeds ${10}^{143}$, as indicated in Equation (8(8) $\begin{array}{rl}{\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{O}3}^{\mathrm{LLVM}}& =⟨O_1,O_2,\dots ,O_{92}⟩\\ {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}& \equiv \{⟨O_{n_k}{⟩}_{n_k\in \{\mathrm{1..92}\}}\mid n_1<n_2<\cdots <n_{92}\}\\ |{\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}|& =\sum _{n=1}^{92}(\genfrac{}{}{0ex}{}{92}{n})n!>{10}^{143},\end{array}$(8) ). (8) $\begin{array}{rl}{\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{O}3}^{\mathrm{LLVM}}& =⟨O_1,O_2,\dots ,O_{92}⟩\\ {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}& \equiv \{⟨O_{n_k}{⟩}_{n_k\in \{\mathrm{1..92}\}}\mid n_1<n_2<\cdots <n_{92}\}\\ |{\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}|& =\sum _{n=1}^{92}(\genfrac{}{}{0ex}{}{92}{n})n!>{10}^{143},\end{array}$(8) where ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{O}3}^{\mathrm{LLVM}}$ and ${\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}$ represent the O3 optimisation sequence and the set of all possible O3 subsequences of the LLVM compiler infrastructure, respectively.

For a better understanding of how many useless passes may occur in an O3 subsequence, we conducted an experiment, in which we randomly sampled 2700 sequences from all possible O3 subsequences and applied each of these sequences to three programs (loop_unroll, matmul4x4, and recursive) and executed the programs, respectively. Figure 2 illustrates the execution times of program loop_unroll for 2700 distinct O3 subsequences, where the x-axis represents the length of an optimisation sequence, and the y-axis represents its corresponding execution time. This figure indicates that many O3 subsequences, with different lengths of optimisation sequences, resulted in the same execution performance. This is likely attributed to fact that these optimisation sequences are variants of a reduced sequence, which contain different numbers of useless passes. Such a phenomenon also occurred for matmul4x4 and recursive.

Figure 2. Execution times of program loop_unroll for 2700 distinct O3 subsequences. Each dot represents the result of an O3 subsequence.

To further perceive the dependencies and interactions among different optimisation passes, we investigated the relevance between optimisation sequences and their corresponding execution results for matmul4x4 and recursive. Tables 4 and 5 display the execution times of programs matmul4x4 and recursive for some particular optimisation sequences. Table 4 indicates that pass slp-vectorize was necessary for matmul4x4 and the execution performance of matmul4x4 could be better improved if passes memcpyopt and sora were applied before slp-vectorize, while other O3 optimisation passes provided almost no contribution to growth in performance. By contrast, Table 5 reveals that both early-cse-memssa and mem2reg produced good results for program recursive, but the combination of the two did not produce a synergistic effect. In addition, although the sequence of $⟨\mathit{t}\mathit{a}\mathit{i}\mathit{l}\mathit{c}\mathit{a}\mathit{l}\mathit{l}\mathit{e}\mathit{l}\mathit{i}\mathit{m}\mathit{,}\mathit{l}\mathit{o}\mathit{o}\mathit{p}\mathit{-}\mathit{r}\mathit{o}\mathit{t}\mathit{a}\mathit{t}\mathit{e}⟩$ itself did not perform well, pass tailcallelim transformed the recursive structure of the program into the form of loops, which were later optimised by pass loop-rotate. Instead, the sequence with a prepended pass mem2reg achieved the best performance.

Table 4. Execution times of program matmul4x4 for four particular O3 subsequences.

Optimisation sequence	Execution time (second)
$⟨\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$	0.32
$⟨\mathit{s}\mathit{o}\mathit{r}\mathit{a}\mathit{,}\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$	0.43
$⟨\mathit{m}\mathit{e}\mathit{m}\mathit{c}\mathit{p}\mathit{y}\mathit{o}\mathit{p}\mathit{t}\mathit{,}\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$	0.32
$⟨\mathit{m}\mathit{e}\mathit{m}\mathit{c}\mathit{p}\mathit{y}\mathit{o}\mathit{p}\mathit{t}\mathit{,}\mathit{s}\mathit{o}\mathit{r}\mathit{a}\mathit{,}\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$	0.27

Table 5. Execution times of program recursive for seven particular O3 subsequences.

Optimisation sequence	Execution time (second)
$⟨\mathit{i}\mathit{n}\mathit{s}\mathit{t}\mathit{c}\mathit{o}\mathit{m}\mathit{b}\mathit{i}\mathit{n}⟩$	0.87
$⟨\mathit{e}\mathit{a}\mathit{r}\mathit{l}\mathit{y}\mathit{-}\mathit{c}\mathit{s}\mathit{e}\mathit{-}\mathit{m}\mathit{e}\mathit{m}\mathit{s}\mathit{s}\mathit{a}⟩$	0.51
$⟨\mathit{e}\mathit{a}\mathit{r}\mathit{l}\mathit{y}\mathit{-}\mathit{c}\mathit{s}\mathit{e}\mathit{-}\mathit{m}\mathit{e}\mathit{m}\mathit{s}\mathit{s}\mathit{a}\mathit{,}\mathit{i}\mathit{n}\mathit{s}\mathit{t}\mathit{c}\mathit{o}\mathit{m}\mathit{b}\mathit{i}\mathit{n}⟩$	0.49
$⟨\mathit{t}\mathit{a}\mathit{i}\mathit{l}\mathit{c}\mathit{a}\mathit{l}\mathit{l}\mathit{e}\mathit{l}\mathit{i}\mathit{m}\mathit{,}\mathit{l}\mathit{o}\mathit{o}\mathit{p}\mathit{-}\mathit{r}\mathit{o}\mathit{t}\mathit{a}\mathit{t}\mathit{e}⟩$	1.05
$⟨\mathit{m}\mathit{e}\mathit{m}\mathit{2}\mathit{r}\mathit{e}\mathit{g}\mathit{,}\mathit{l}\mathit{o}\mathit{o}\mathit{p}\mathit{-}\mathit{r}\mathit{o}\mathit{t}\mathit{a}\mathit{t}\mathit{e}⟩$	0.49
$⟨\mathit{m}\mathit{e}\mathit{m}\mathit{2}\mathit{r}\mathit{e}\mathit{g}\mathit{,}\mathit{t}\mathit{a}\mathit{i}\mathit{l}\mathit{c}\mathit{a}\mathit{l}\mathit{l}\mathit{e}\mathit{l}\mathit{i}\mathit{m}⟩$	0.44
$⟨\mathit{m}\mathit{e}\mathit{m}\mathit{2}\mathit{r}\mathit{e}\mathit{g}\mathit{,}\mathit{t}\mathit{a}\mathit{i}\mathit{l}\mathit{c}\mathit{a}\mathit{l}\mathit{l}\mathit{e}\mathit{l}\mathit{i}\mathit{m}\mathit{,}\mathit{l}\mathit{o}\mathit{o}\mathit{p}\mathit{-}\mathit{r}\mathit{o}\mathit{t}\mathit{a}\mathit{t}\mathit{e}⟩$	0.418

If we attempt to build a optimisation sequence prediction model, we will naturally treat sequences $⟨\mathit{m}\mathit{e}\mathit{m}\mathit{c}\mathit{p}\mathit{y}\mathit{o}\mathit{p}\mathit{t}\mathit{,}\mathit{s}\mathit{o}\mathit{r}\mathit{a}\mathit{,}\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$ and $⟨\mathit{m}\mathit{e}\mathit{m}\mathit{2}\mathit{r}\mathit{e}\mathit{g}\mathit{,}\mathit{t}\mathit{a}\mathit{i}\mathit{l}\mathit{c}\mathit{a}\mathit{l}\mathit{l}\mathit{e}\mathit{l}\mathit{i}\mathit{m}\mathit{,}\mathit{l}\mathit{o}\mathit{o}\mathit{p}\mathit{-}\mathit{r}\mathit{o}\mathit{t}\mathit{a}\mathit{t}\mathit{e}⟩$ as labels for programs matmul4x4 and recursive, respectively. However, if we take a close look at the effect of the desired O3 subsequence on the code snippet of matmul4x4, which is shown in Figure 3, we can see that the $⟨\mathit{m}\mathit{e}\mathit{m}\mathit{c}\mathit{p}\mathit{y}\mathit{o}\mathit{p}\mathit{t}\mathit{,}\mathit{s}\mathit{o}\mathit{r}\mathit{a}\mathit{,}\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$ sequence effectively optimised the memory copy loop (lines 22–23), whereas the matrix computations (lines 5–20) could be optimised only by $⟨\mathit{s}\mathit{l}\mathit{p}\mathit{-}\mathit{v}\mathit{e}\mathit{c}\mathit{t}\mathit{o}\mathit{r}\mathit{i}\mathit{z}\mathit{e}⟩$. If the machine-learning methods we intend to use can extract features that describe the characteristics of these two parts of the code snippet and we demand the machine learning model to be more general, the two O3 subsequences should be preserved and treated as labels for training the model. Therefore, identifying as many O3 subsequences that do not contain any useless passes (or reduced O3 subsequences) as possible is a crucial step towards resolving the OPT problem.

Figure 3. Code snippet of program matmul4x4.

3.2. Problem formulation

As defined earlier in this section, a reduced sequence is an optimisation sequence that does not contain any useless passes, which have no benefit to a program with specific inputs; nevertheless, the passes may profit another program or even the same program with other inputs. Consequently, the set of reduced sequences varies from program to program and even input to input. The formal definitions of the set of all reduced sequences and the set of all reduced O3 subsequences with a specific program and inputs are given in Equations (9(9) $\begin{array}{rl}{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{prog,in}(O,M)& \equiv \{\overrightarrow{s}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\mid \mathrm{\forall }\overrightarrow{t}=\overrightarrow{s}\setminus O_i\wedge O_i\in \overrightarrow{s}\wedge O_i\in O,\\ & {\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})>\delta \}\end{array}$(9) ) and (13(13) $\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}\equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.\overrightarrow{a}⪰\overrightarrow{s}\},$(13) ), respectively. (9) $\begin{array}{rl}{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{prog,in}(O,M)& \equiv \{\overrightarrow{s}\in \mathbb{S}\mathbb{E}\mathbb{Q}(O,M)\mid \mathrm{\forall }\overrightarrow{t}=\overrightarrow{s}\setminus O_i\wedge O_i\in \overrightarrow{s}\wedge O_i\in O,\\ & {\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})>\delta \}\end{array}$(9) (10) $\begin{array}{rl}{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}& \equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \mathrm{\forall }\overrightarrow{t}=\overrightarrow{s}\setminus O_i\wedge O_i\in \overrightarrow{s}\wedge O_i\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3}^{\mathrm{LLVM}},\\ & {\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})>\delta \},\end{array}$(10) where δ represents a measurement error. The condition of ${\mathcal{F}}_{prog,in}(\overrightarrow{s})-{\mathcal{F}}_{prog,in}(\overrightarrow{t})>\delta$ is used to determine whether $O_i$ is a useless pass as $O_i$ belongs to $\overrightarrow{s}$, but not $\overrightarrow{t}$, which is derived from $\overrightarrow{s}$. The RO3SL problem is in fact an optimisation problem that aims to collect the set of reduced O3 subsequences and can be roughly formulated in Equation (11(11) $\begin{array}{rl}\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}& \equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \\ & \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \},\end{array}$(11) ). (11) $\begin{array}{rl}\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}& \equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \\ & \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \},\end{array}$(11) where $\Vert \overrightarrow{x}\Vert$ denotes the length of vector $\overrightarrow{x}$. In this optimisation problem, the objective is to find out as many reduced O3 subsequences as possible using the fact that a short sequence that delivers the same performance as a longer sequence contains fewer useless passes. As a result, the need to check whether a pass is useless in a certain sequence can be eliminated.

However, by the definition of the reduced sequences, two sequences that contain no useless passes and optimise different program fragments with less benefit will not be included in the set of reduced sequences. These two sequences will be indistinguishable if we use Equation (11(11) $\begin{array}{rl}\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}& \equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \\ & \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \},\end{array}$(11) ) to solve the RO3SL problem; hence, Equation (11(11) $\begin{array}{rl}\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}& \equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \\ & \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \},\end{array}$(11) ) should be revised to address such issue. In evolutionary computation, this type of problem is called a multimodal task (Tanabe & Ishibuchi, 2020), which distinguishes different elements in the solution space by the distance between them – in this case, two sequences are distinguished by the distance between the two sequences, where the distance should be clearly defined.

Since a sequence can be encoded as a bit vector (as we have done in Table 3), it makes intuitive sense to consider the Hamming distance (Hamming, 1950) to distinguish two sequences. However, the Hamming distance is not an appropriate measure for distinguishing two optimisation sequences. For example, Table 6 gives an example of two similar Hamming distances for two distinct pairs of sequences. The first pair of sequences are similar sequences, both of which turn on the six passes except the third one, and they are different by the decisions made on the last two passes, so the Hamming distance of three is calculated. By contrast, the second pair of sequences are quite different because they turn on two distinct passes, respectively, but the Hamming distance between the two sequences is only two. It would be difficult to determine the similarity between two sequences by using the Hamming distance. Fortunately, the Jaccard distance (Jaccard, 1912), which measures the similarity between two bit vectors, as indicated in Equation (12(12) ${\mathcal{D}}_J(\overrightarrow{a},\overrightarrow{b})=\frac{\Vert \overrightarrow{a}\oplus \overrightarrow{b}\Vert }{\Vert \overrightarrow{a}\vee \overrightarrow{b}\Vert },$(12) ), fits our needs.

Table 6. The Hamming and Jaccard distances between optimisation sequences. ${\mathcal{D}}_H({\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$, ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}})$, the Hamming distance between sequences ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$ and ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}}$; ${\mathcal{D}}_J({\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$, ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}})$, the Jaccard distance between sequences ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$ and ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}}$.

${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$	${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}}$	${\mathcal{D}}_H({\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$, ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}})$	${\mathcal{D}}_J({\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{a}}$, ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{b}})$
11011110	11011101	3	$\frac{2}{7}$
00000100	10000000	2	1

(12) ${\mathcal{D}}_J(\overrightarrow{a},\overrightarrow{b})=\frac{\Vert \overrightarrow{a}\oplus \overrightarrow{b}\Vert }{\Vert \overrightarrow{a}\vee \overrightarrow{b}\Vert },$(12) where ⊕ and ∨ are a bitwise exclusive-or operator and a bitwise or operator, respectively. As the shortest distance between two 2-bit vectors is $\frac{1}{2}$, it is reasonable to use this as a threshold to determine whether two sequences are similar; that is, if the Jaccard distance of two sequences are greater than $\frac{1}{2}$, they are considered distinguishable. In the examples in Table 6, we can distinguish the second pair of sequences by using the Jaccard distance as their Jaccard distance is 1, while the first pair of sequences are considered indistinguishable as their Jaccard distance is $\frac{2}{7}$.

With the consideration of the sequence distance, now, we have a well-defined optimisation problem, which is defined in Definition 3.1 and aims to collect reduced O3 subsequences.

Definition 3.1

The problem of reduced O3 subequence labelling

Given a program prog with inputs in together with the O3 optimisation sequence ${\mathbb{s}\mathbb{e}\mathbb{q}}_{\mathrm{O}3}^{\mathrm{LLVM}}$, find the set of reduced O3 subsequences $\overline{{\mathbb{R}\mathbb{S}\mathbb{E}{\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}}_{prog,in}}$, which is defined in Equation (13(13) $\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}\equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.\overrightarrow{a}⪰\overrightarrow{s}\},$(13) ). (13) $\overline{{\mathbb{R}\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{{\mathrm{LLVM}}_{prog,in}}}\equiv \{\overrightarrow{s}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mid \nexists \overrightarrow{a}\in {\mathbb{S}\mathbb{E}\mathbb{Q}}_{\mathrm{O}3\mathrm{sub}}^{\mathrm{LLVM}}\mathrm{s}.\mathrm{t}.\overrightarrow{a}⪰\overrightarrow{s}\},$(13) where $\overrightarrow{a}⪰\overrightarrow{b}$ is defined in Equation (14(14) $\overrightarrow{a}⪰\overrightarrow{s}⟺{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \wedge {\mathcal{D}}_J(\overrightarrow{a},\overrightarrow{s})<\frac{1}{2}$(14) ). (14) $\overrightarrow{a}⪰\overrightarrow{s}⟺{\mathcal{F}}_{prog,in}(\overrightarrow{a})-{\mathcal{F}}_{prog,in}(\overrightarrow{s})>\delta \wedge \Vert \overrightarrow{a}\Vert <\Vert \overrightarrow{s}\Vert \wedge {\mathcal{D}}_J(\overrightarrow{a},\overrightarrow{s})<\frac{1}{2}$(14)

3.3. Genetic algorithm for reduced O3 subsequence labelling

The optimisation problem defined in Definition 3.1 is not a simple problem; it is a typical multi-modal, multi-objective problem. This optimisation problem is obvious a multi-objective problem since multiple objectives, such as the length and the result (i.e. the execution time of a program after a sequence is applied when compiling the program) of a sequence, should be considered to find a reduced O3 subsequence. The problem is also a multi-modal because multiple reduced O3 subsequences are expected to discover in order to be applied to different parts of a program. It is worth noting that in the past a multi-modal optimisation was not necessary if the objective was to seek the best sequence of a whole program. With the rapid growth of deep learning techniques, especially more and more sophisticated feature extraction techniques, it is essential to decompose a program and optimise its decompositions individually. Therefore, a multi-modal optimisation must be considered to meet this need in Definition 3.1.

A multi-modal, mulit-objective optimisation problem is difficult to solve, so many new techniques and approaches have been tried in recent years (Tanabe & Ishibuchi, 2020). In this study, we adopted the technique of SPEA2+ (Kim et al., 2004), which is an improved version of SPEA2 (Zitzler et al., 2001), to solve the RO3SL problem. We propose a new crossover operator (Algorithm ??) and a new mutation operator (Algorithm ??) upon the operators defined in SPEA2+ so as to generate better sequences with respect to the objective of the RO3SL problem. More specifically, the crossover operator is basically based on the one-point crossover (Poli & Langdon, 1998). When performing the crossover operation, if the given two sequences are indistinguishable (i.e. their Jaccard distance is smaller than $\frac{1}{2}$), it is likely that the two sequences are variants of the same reduced sequence but contain different numbers of useless passes. In this case, the crossover operation can be performed in a more aggressive way by producing a new sequence that is the intersection or union of the two sequences. Moreover, a fully random mutation is likely not a favourable mutation method for the RO3SL problem since the mutation operation may just lead to an unproductive result, just like randomly walking the floor of a basin and get trapped as we have discussed in Section 2.3. The proposed mutation operator intends to guide the mutation process to move towards the same direction by setting or unsetting a number of bits within a given bit vector (or the optimisation sequence). By using the SPEA2+ algorithm along with the proposed crossover and mutation operators, we are now able to generate approximate reduced O3 subsequences, which can be treated as the key training data for resolving the OPT problem.

4. Experimental results and discussion

4.1. Evaluation environment

All of the evaluations in this study were conducted on a platform whose hardware and system details are indicated in Table 7. Processor affinity was used to ensure that each program or application stayed in the same processor during the whole execution in order to reduce cache interference. Meanwhile, there were no other processes running except the system processes in order to reduce any possible interference. The benchmarks we used to evaluate the modified SPEA2+ algorithm were collected from the test suite of the LLVM compiler infrastructure (Lattner & Adve, 2004), including loop_unroll from Adobe-C++ and two applications: libSVM and Hexxagon.

Table 7. Hardware and system information of the evaluation platform.

Component	Specification
CPU	Intel i7-8700 K 4.3 GHz
Memory	DDR4 2600 16G×2
OS	Ubunut 16.04
Kernel version	4.19.83

4.2. Evaluation results

In order to demonstrate the effectiveness of the modified SPEA2+ algorithm, we implemented four different genetic algorithms to solve the RO3SL problem: naïve genetic algorithm (GA), SPEA2, SPEA2, and modified SPEA2+ (with customised crossover and mutation operators listed in Algorithms ?? and ??, respectively). All of the four genetic algorithms were implemented based on DEAP, an evolutionary computation framework (Fortin et al., 2012), and Table 8 lists the details about the implementation of the genetic algorithms. As the goal of the genetic algorithms is to generate reduced O3 subsequences, the effectiveness of a genetic algorithm is assessed by how closely the generated sequences resemble the reduced O3 subsequences, which contain no useless passes. In other words, the assessments could be based upon the degree of similarity (i.e. the Jaccard distance) between the generated sequences and the reduced O3 subsequences. Figure 4 illustrates the average Jaccard distances between the generated sequences and the reduced O3 subsequences for the four genetic algorithms during the evolutionary process from ten runs of the genetic algorithms. It indicates that as the generation number became larger, the sequences generated by the modified SPEA2+ algorithm gradually resembled the reduced O3 subsequences, whereas the sequences generated by the other three algorithms contained about 50% or even more of useless passes for all generations. Table 9 lists the average Jaccard distances between the generated sequences (for final generation) and the reduced O3 subsequences for program loop_unroll and applications libSVM and Hexxagon from 10 runs of the genetic algorithms. Our proposed algorithm (modified SPEA2+) produced the best results against the other three algorithms.

Figure 4. Jaccard distances between the generated sequences and the reduced O3 subsequences by generations for program loop_unroll.

Table 8. Genetic algorithms used to solve the problem of reduced O3 subsequence labelling.

Operator	Mate selection	Crossover & mutation	Survival selection
Algorithm
Naïve GA	selTournament${}^a$	General	selTournament
SPEA2	selTournament	General	selSPEA2
SPEA2+	selTournament	General	selSPEA2+
Modified SPEA2+	selTournament	Customised	selSPEA2+

${}^a$selTournament: a section function provided by DEAP, an evolutionary computation framework (Fortin et al., 2012).

Table 9. Jaccard distances between the generated sequences (final generation) and the reduced O3 subsequences for program loop_unroll and applications libSVM and Hexxagon.

Algorithm	Naïve GA	SPEA2	SPEA2+	Modified SPEA2+
Benchmark
loop_unroll	0.56	0.51	0.47	0.21
libSVM	0.45	0.35	0.32	0.15
Hexxagon	0.51	0.22	0.23	0.19

5. Conclusion

Compiler tuning using machine learning techniques is moving to the next level, where more accurate code feature models are required with more detailed optimisation information. We have presented a new problem, called reduced O3 subsequence labelling, to simplify the compiler autotuning problem and expected to be a stepping stone towards solving the optimisation tuning problem. We have also implemented a modified SPEA2+ genetic algorithm to address the problem of reduced O3 subsequence labelling. The experimental results demonstrate that the proposed genetic algorithm generated optimisation sequences with less useless passes. We believe that mature deep learning techniques combined with evolutionary optimisation algorithms that generate reduced O3 subsequences can enable an effective prediction model that predicts reduced O3 subsequences or even the best O3 subsequence for an individual code fragment; this will be a major step towards solving the problem of optimisation phase tuning.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This study was partially supported by the Ministry of Science and Technology of Taiwan [grant number MOST 110-2221-E-A49-030-MY3].