# POSET-RL: Phase ordering for Optimizing Size and Execution Time using
Reinforcement Learning

Shalini Jain1, Yashas Andaluri2, S. VenkataKeerthy3 and Ramakrishna Upadrasta4
Department of Computer Science and Engineering, IIT Hyderabad
Email: {1cs15resch11010, 2cs17b21m000001<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The ever increasing memory requirements of several applications has led to
increased demands which might not be met by embedded devices. Constraining the
usage of memory in such cases is of paramount importance. It is important that
such code size improvements should not have a negative impact on the runtime.
Improving the execution time while optimizing for code size is a non-trivial
but a significant task.

The ordering of standard optimization sequences in modern compilers is fixed,
and are heuristically created by the compiler domain experts based on their
expertise. However, this ordering is sub-optimal, and does not generalize well
across all the cases.

We present a reinforcement learning based solution to the phase ordering
problem, where the ordering improves both the execution time and code size. We
propose two different approaches to model the sequences: one by manual
ordering, and other based on a graph called Oz Dependence Graph (ODG). Our
approach uses minimal data as training set, and is integrated with LLVM.

We show results on x86 and AArch64 architectures on the benchmarks from SPEC-
CPU 2006, SPEC-CPU 2017 and MiBench. We observe that the proposed model based
on ODG outperforms the current Oz sequence both in terms of size and execution
time by 6.19% and 11.99% in SPEC 2017 benchmarks, on an average.

Keywords-Phase Ordering, Compiler Optimization, Reinforcement learning

##  I Introduction

One of the essential components of compiler construction are optimizations.
They involve transforming the input program and generating code that is
semantically equivalent to it, but performs better in various metrics like
execution time, code size, power utilization, etc.

Modern compilers have several number of optimizations like vectorization, dead
code elimination implemented as passes. A collection of these individual
passes are statically ordered a priori and are exposed as off-the-shelf
standard optimization flags like O0, O1, O2, O3, Os, and Oz. Among these
predefined optimization flags, O0 disables all optimizations, essentially
making the compiler a translator of the source-program to binary. It provides
fast compilation of source code, while also giving good correlation between
source and the generated code. Optimization flags O1, O2, and O3 are designed
to improve performance by reducing the execution time. While the O1 flag
enables some important optimizations, the O2 flag adds a few more
optimizations. The O2 flag also changes the heuristics for the optimizations
when compared to O1 flag. With respect to execution of the code, the O3
sequence gives the best performance among all these optimizations. Although
these optimizations improve the performance of program execution, they may
also increase code size.

The Os and Oz flags are designed to optimize for code size. The Os flag is
designed to perform nearly similar to O2 flag, while promising an appreciable
decrease in code size. The Oz flag is designed to provide more code size
reduction than Os. Such a reduction in code size by optimizations in Oz,
generally incurs penalty on the execution time, leading to a trade-off between
O3 and Oz in terms of code size and execution time.

We observe on a set of benchmarks from the standard SPEC CPU benchmarks that
the binaries generated by Oz flag incurs $10\%$ more execution time than that
of O3; while resulting in about $3.5\%$ improvement in terms of code size, on
an average. A chart showing the runtime and code size characteristics of these
benchmarks is shown in Fig. 1. In this work, we try to find if this gap
exhibited by Oz passes can be improved by further reducing the code size while
improving the run time.

Figure 1: O3 vs. Oz: Comparison of runtime and code size

Although these predefined optimization flags achieve good performance when
compared to the unoptimized case, they do not guarantee the best performance
for every given input program. Moreover, the ordering of passes in these
sequences is not based on a particular input program but is statically
predefined.

The problem of selecting and ordering the optimization passes, called the
phase ordering problem has been a fertile ground for compiler researchers for
many decades [1]. The classic paper by Cooper et al. [2] refers to this
particular problem where they propose using AI/ML techniques for reordering
optimizations.

In the literature, the phase ordering problem has been recognized to be an
important problem for several reasons, including the following:

  * •

On a particular program, two optimizations applied in different orders may
have an unpredictable impact on its performance. It is also possible that a
predetermined optimization sequence could result in an adverse effect on the
performance of the program.

  * •

After transformation of a program by an optimization sequence or flag, there
is no guarantee to ensure performance improvements. The user, who is
interested in the performance improvement of a particular program, may also
expect some guarantees about the potential improvements on the particular
program, or even a assurance that all (possible) optimizations have been tried
to improve the program.

  * •

The best optimization order designed for one program may not perform well on
another (new) program. The predetermined optimization sequence could even
degrade the performance for new programs.

Exploiting the undecidable nature of this problem [3], several machine
learning based approaches [4], [5], [6], [7], [8] have been used to predict
the optimization sequences given an input program. These techniques use the
expert-designed program features to represent programs for training the model
to arrive at the solution.

Several approaches have been proposed in the recent times to represent
programs as vectors, called program embeddings, analogous to word2vec like
approaches of natural language processing. Such embeddings created by
considering syntactic and semantic information of the program is used as the
input for ML purposes. The most notable embeddings are AST based embeddings of
code2vec [9], and the IR based embeddings of inst2vec [10], and IR2Vec [11].

To our understanding, the earlier works on phase ordering have considered code
size and execution time optimizations as independent objectives. However,
optimizing for codesize and execution time are orthogonal - optimization for
codesize can adversely affect the execution time and vice versa. On the other
hand, if the execution time is not considered while optimizing for codesize,
gains in codesize can lead to worse performance. Hence, we propose a
Reinforcement Learning (RL) based solution for determining better optimization
sequences for a given program to optimize for both code size together and the
execution time in LLVM compiler. Our work is based on modeling programs as
vectors using IR2Vec representations which is a LLVM-based program encoding.

We use a reinforcement learning approach as the search space of optimizations
is too big to enumerate. For a compiler with $m$ optimization passes, if the
sequence length is fixed as $n$, then there can be potentially $m^{n}$
combinations, allowing repetitions. And, Oz of LLVM has 90 transformation
passes, among which 54 are unique. If one has to replicate such a setup, there
can be potentially $54^{90}\approx 10^{156}$ combinations. As it can be seen,
creating this many combinations for each element of the dataset is highly
infeasible, making reinforcement learning a go to method for this problem.

Also, we use IR2Vec representations as it captures the syntax and semantics of
the code intricately when compared to the expert-designed feature set. IR2Vec
representations of the program are modelled as the state, and the sequence of
optimization passes as actions for the formulated RL problem. The agent
predicts the optimizations to apply on the input program. The environment -
LLVM optimizer applies the predicted sequences and recomputes the
representation corresponding to the predicted sequence to update the state for
the next step. This environment is thus responsible for handling the
interaction between the agent and the effect of the action it takes in the
form of rewards.

We propose two different sets of sub-sequences to model the action space in
our RL model. Similar to the earlier works like [4], [6] that model
optimization sequences for execution time by manual or analytical grouping of
passes, we too design a logical grouping of optimization passes to form the
action space. These groups form the sub-sequences, and are obtained from the
standard -Oz sequence of LLVM. Second, we create a graph: Oz Dependence Graph
(ODG) depicting the dependencies among the passes in the Oz sequence and
derive the sequences by traversing the graph.

Our method uses Q-learning [12], which involves determining the optimum
Q-function for a state-action pair. We approximate this by using a neural
network called Deep Q-Network [13],[14], which performs better with complex
environments than the simple Q-learning algorithm that maintains a table or a
matrix called Q-table. We trained our model with the single source llvm-test-
suite benchmark files [15]. Our trained model is able to reduce binary sizes
for most of the benchmarks from MiBench [16], SPEC CPU (int and fp) 2017 [17],
and SPEC CPU 2006 [18] benchmark-suites.

Contributions: The following are our key contributions:

  * •

We propose a novel Deep Q-Network (DQN) based RL model that predicts the
optimal sequence of optimization passes for a given input source program. Our
framework is unique as it builds from embeddings given by IR2Vec encoding and
derives its scalability characteristics.

  * •

We propose a Oz Dependence Graph (ODG) to cluster the individual optimization
passes into various sub-sequences that forms an action space of the RL model.
ODG shows all the dependencies among the optimization passes in terms of the
order they are present in the Oz flag.

  * •

We study the results on two different architectures: x86 and AArch64. We show
results on MiBench, SPEC CPU 2006 and 2017 benchmark suites.

  * •

We show that our solution outperforms the standard Oz sequence by achieving
better code size reduction while improving the runtime on standard compiler
benchmarks. In SPEC 2017, 2006 and MiBench, we achieve a maximum size
reduction of upto $22.94\%$, $9.93\%$, $8.68\%$, while achieving improvements
in runtimes of upto $46\%$, $6\%$ and $16\%$ respectively.

The rest of the paper is further organized as the following: Some relevant
background of Reinforcement Learning (RL) is explained in Section II. In our
solution, we model each program as states, and optimization passes as actions
in accordance with reinforcement learning techniques. We discuss this design
in Section III. In Section IV, we explain the rationale for the above design.
In Section V, we discuss experimentation details, and the detailed analysis of
results. We discuss the related works in Section VI. Finally, in Section VII,
we conclude our work.

##  II Background

In this section we give a brief summary of the reinforcement learning
techniques and the program representation method that we use.

Figure 2: Reinforcement Learning Process

###  II-A Reinforcement Learning and Markov Decision Process

The overview of a reinforcement learning method using Markov Decision Process
(MDP) is shown in Fig. 2. A reinforcement learning problem modelled on the
Markov Decision Process usually consists of the following:

  * •

Agent: An agent is the actor that makes a decision by choosing an action from
an action space for which it receives reward from the environment. A positive
valued reward represents a good decision and negative value represents a bad
decision. After performing any action, the agent moves from current state to
the new state.

  * •

States: An instance of the environment is defined as a state. For each action
the agent takes, the current state transitions to a new state.

  * •

Action: Decision taken by the agent by looking into the current state. Set of
all actions that an agent can take forms an action space.

  * •

Environment: The agent is placed in an environment that rewards or punishes
the agent for the current action. The agent interacts with the environment to
learn better so as to maximize the reward in future.

An agent usually interacts with the environment through states and actions to
get rewards. The formulation of RL problems can be exploited by a software
agent to explore an environment and make profitable decisions. This fits
nicely with our need for exploiting a sequence of actions viz optimization
passes and taking profitable actions that results in optimizing code size
along with the execution time.

As discussed earlier, reinforcement learning can be formulated using Markov
Decision Processes (MDPs). An MDP provides a mathematical framework that can
model decision making. An agent is said to follow the Markov Property, if the
current state of the agent depends only on its immediate previous state or its
next state depends only on its current state. This augurs well with respect to
our problem where the agent can choose an optimization pass given its current
state and not have to look in the past.

###  II-B Deep Q-Networks

Q-learning involves quantifying state-action pairs with q-values that define
how good a given action for a particular state is. The vanilla Q-learning in
practice involves maintaining a table or matrix of values. Although the
Q-learning algorithm may generalize well to real-world problems, it usually
becomes infeasible for complex environments as the number of states go higher.
The Deep Q-Network (DQN) was introduced to solve this problem which involves
combining the traditional Q-learning algorithm with Deep Neural Networks [13].
The deep neural network here acts as a function approximator for the
Q-function by replacing the need for storing values in a Q-table. The various
flavours of DQN have been proposed and are widely used [13], [14], [19], [20].
We use Double DQN for modelling our problem.

A vanilla DQN on training suffers from the overestimation of Q values [19].
The notion of double DQN was introduced to meet with this challenge. Instead
of using the target network for predicting the future q-value, double DQN uses
an online network to predict the best action $a^{\prime}$ for a given state
$s^{\prime}$. The q-value, $q(s^{\prime},a^{\prime})$ for the state-action
pair $(s^{\prime},a^{\prime})$ is given by the target network.

###  II-C IR2Vec

As described earlier, modern compilers have several nontrivial compiler
optimizations implemented in them that are the result of manual heuristics
designed by expert compiler writers. Various machine learning techniques have
been proposed to solve such tasks on source code by modelling them as Natural
Language Processing problems [21]. Of late, researchers identified the issues
arising from modelling programs as natural languages and proposed programming
language centric approaches to model programs. These approaches result in
representing programs as vectors [9], [10], [11], analogous to that of natural
language representations like word2vec and gloVe.

We use IR2Vec representations [11] to represent programs in our model. IR2Vec
uses the intermediate representation of LLVM to represent programs as high
dimensional vectors called program embeddings. As it is based on LLVM IR, the
representation is naturally independent of the source languages and target
architectures. It can generate encodings for all the languages that LLVM can
support.

The IR2Vec framework is primarily built from a vocabulary containing the
representation of each fundamental entities of the IR, viz. opcode, type and
operands. These are used to form the higher-level representations, at the
program level, function level, or instruction level. Also, IR2Vec uses the
use-def, reaching definitions, and live variable analyses information to
construct flow-analysis based representations. It is shown that IR2Vec
representations have high scalablity, have better memory characteristics, and
exhibit better Out Of Vocabulary characteristics than the other approaches.

We chose IR2Vec representations to represent programs, as it builds on program
analysis approaches to form program centric representations.

##  III Methodology

The overview of our proposed methodology is shown in Fig. 3. The input source
code is initially fed to the environment where the LLVM IR is generated by the
LLVM’s front-end, which in turn is converted to embeddings by using the IR2Vec
module as shown in Fig. 3. These representations of input programs form our
observation space or states as discussed in Section II. The RL agent starts
learning the information about the environment through a series of episodes by
consuming these embeddings as input. For each step in an episode, given the
input program representation, the agent interacts with the environment by
predicting the optimization sub-sequence to apply as an action from the action
space. We describe the action space in detail in Section IV. The LLVM
optimizer or opt is used to apply the optimizations predicted by the RL agent,
which then transitions the current state to the next state. The new state is
formed by updating the IR2Vec representations corresponding to updated code
after applying the predicted transformations. For each such transition, the RL
agent receives a reward and continues the same till it reaches the end of an
episode. We refer to this flow diagrammatically in Fig. 3. The rewards are
defined as the combination of reduction in the size of an object file as well
as improvement in throughput in comparison to an object file optimized with
the Oz sequence.

Figure 3: Overview of the proposed workflow

We broadly divide our framework into 3 main modules viz (i) Environment, (ii)
RL agent, and (iii) Reward computation which we explain in greater detail in
subsequent Sections, III-A, III-B and III-C respectively.

###  III-A Environment

As our work is based on LLVM-IR, we convert source files into LLVM-IR using
the existing frontend framework. Since we consider only C/C++ input files,
clang/clang++ converts it into IR files. These IR files are original non-
optimized versions. We consider this data as an input dataset to the RL agent.

As discussed in Section II, the environment in an RL problem allows the agent
to explore and make decisions on the basis of the actions it takes. Here our
environment serves the same for the RL agent which interacts with it to
perform actions and to get rewards associated with it. Our environment further
consists of three modules i.e. IR2Vec embeddings, Rewards and action space,
each of these discussed in detail below.

####  III-A1 IR2Vec Embeddings

To represent the source programs we use IR2Vec [11] embeddings which represent
each program as higher dimensional vectors that encode both program features
as well as flow information. This enables us to better represent the source
programs as the semantics of it is also encoded in the embeddings. Each source
program vector acts as a state for the environment which changes with the
application of optimization passes. This causes the DQN to have transitioned
to a different state.

####  III-A2 Rewards

During training, we compile the LLVM-IR module obtained at each step to its
object file, without linking, so as to prevent the inclusion of code from
linked libraries. This module computes the total size of the object file. We
use LLVM-MCA [22] to estimate the throughput of the generated binary. Higher
the throughput, lesser would be the runtime. Hence we use this throughput as a
static measure to model the runtime of the code. Both the code size and
throughput components form the reward. We describe reward calculation in
section III-C. Initially, for each source program in the input dataset, this
module computes the size of an object file and throughput generated by LLVM-
MCA without any optimization and with the -Oz optimization sequence. Then, for
each step of an episode, this module computes the size of an object file and
throughput generated by LLVM-MCA for the resultant object file on applying the
predicted action.

####  III-A3 Action Space

Action space consists of all the sub-sequences (set of optimizations passes
from LLVM) generated from the Oz optimization sequence. At each step the RL
agent selects any one sub-sequence from the action space and applies it to the
IR present in the current state. We experiment with two approaches for forming
the action space - sub-sequences generated by manual grouping and sub-sequence
selection by ODG, discussed in detail in Section IV.

###  III-B RL Agent

As discussed in Section II, we define our RL agent as a Double Deep Q-Network
(DDQN). Given the IR2Vec representation as a state, the DDQN predicts the
associated Q-value for every action in the action space containing different
optimization sequences. As discussed earlier, the optimization sequence with
the highest Q-value is chosen and is then applied to LLVM-IR of the source
program to obtain the next state. After gathering enough experiences by
interacting with the environment, the DDQN then starts to train to obtain the
optimal Q-value for every state.

###  III-C Reward Computation

We define our reward (R) as the combination of improvement in binary size and
the throughput corresponding to the optimized and the original, non optimized
versions of the compiled object file. It is computed as:

$R=\alpha*R_{BinSize}+\beta*R_{Throughput}$ (1)

Where, reward corresponding to BinSize ($R_{BinSize}$) is defined as the ratio
of change in size between each interim states of an episode to binary size of
the original object file, as shown in Eqn (2).

$R_{BinSize}=\frac{BinSize_{last}-BinSize_{curr}}{BinSize_{base}}$ (2)

Here, $BinSize_{last}$ refers to the size of the object file of the previous
state, $BinSize_{curr}$ refers to the total size of the object file after
performing the action chosen by the model, and $BinSize_{base}$ refers to the
size of the object file without any optimization.

We describe the throughput component of the reward, $R_{Throughput}$ as the
ratio of change in throughput between each interim states of an episode to the
throughput of the original object file, as shown in Eqn (3).

$R_{Throughput}=\frac{Throughtput_{curr}-Throughtput_{last}}{Throughtput_{base}}$
(3)

Here, $Throughput_{curr}$, $Throughput_{last}$ and $Throughput_{base}$ refer
to the throughput generated by LLVM-MCA for current state, last state and
without any optimization respectively.

##  IV Selection of Sub-Sequences

TABLE I: List of transformation passes in Oz optimization sequence (LLVM-10)
List of Transformation Passes in Oz
---
-ee-instrument -simplifycfg -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor -globalopt -mem2reg -deadargelim -instcombine -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation -simplifycfg -instcombine -tailcallelim -simplifycfg -reassociate -loop-simplify -lcssa -loop-rotate -licm -loop-unswitch -simplifycfg -instcombine -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -gvn -memcpyopt -sccp -bdce -instcombine -jump-threading -correlated-propagation -dse -loop-simplify -lcssa -licm -adce -simplifycfg -instcombine -barrier -elim-avail-extern -rpo-functionattrs -globalopt -globaldce -float2int -lower-constant-intrinsics -loop-simplify -lcssa -loop-rotate -loop-distribute -loop-vectorize -loop-simplify -loop-load-elim -instcombine -simplifycfg -instcombine -loop-simplify -lcssa -loop-unroll -instcombine -loop-simplify -lcssa -licm -alignmentfromassumptions -strip-dead-prototypes -globaldce -constmerge -loop-simplify -lcssa -loop-sink -instsimplify -div-rem-pairs -simplifycfg
TABLE II: List of manual sub-sequences designed from Oz sequence S.No. | Manual Sub-sequence
---|---
1 | -ee-instrument -simplifycfg -sroa -early-cse -lower-expect -forceattrs -inferattrs -mem2reg
2 | -ipsccp -called-value-propagation -attributor -globalopt
3 | -deadargelim -instcombine -simplifycfg
4 | -prune-eh -inline -functionattrs -barrier
5 | -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation
6 | -simplifycfg -instcombine -tailcallelim -simplifycfg -reassociate
7 | -loop-simplify -lcssa -loop-rotate -licm -loop-unswitch -simplifycfg -instcombine
8 | -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll
9 | -mldst-motion -gvn -memcpyopt -sccp -bdce -instcombine -jump-threading -correlated-propagation -dse
10 | -loop-simplify -lcssa -licm -adce -simplifycfg -instcombine
11 | -barrier -elim-avail-extern -rpo-functionattrs -globalopt -globaldce -float2int -lower-constant-intrinsics
12 | -loop-simplify -lcssa -loop-rotate -loop-distribute -loop-vectorize
13 | -loop-simplify -loop-load-elim -instcombine -simplifycfg -instcombine
14 | -loop-simplify -lcssa -loop-unroll -instcombine -loop-simplify -lcssa -licm -alignment-from-assumptions
15 | -strip-dead-prototypes -globaldce -constmerge -loop-simplify -lcssa -loop-sink -instsimplify -div-rem-pairs -simplifycfg
Figure 4: Oz Dependence Graph TABLE III: List of sub-sequences designed from ODG of Oz sequence S.No. | ODG Sub-sequence
---|---
1 | -instcombine -barrier -elim-avail-extern -rpo-functionattrs -globalopt -globaldce -constmerge
2 | -instcombine -barrier -elim-avail-extern -rpo-functionattrs -globalopt -globaldce -float2int -lower-constant-intrinsics
3 | -instcombine -barrier -elim-avail-extern -rpo-functionattrs -globalopt -mem2reg -deadargelim
4 | -instcombine -jump-threading -correlated-propagation -dse
5 | -instcombine -jump-threading -correlated-propagation
6 | -instcombine
7 | -instcombine -tailcallelim
8 | -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll
9 | -loop-simplify -lcssa -indvars -loop-idiom -loop-deletion -loop-unroll -mldst-motion -gvn -memcpyopt -sccp -bdce
10 | -loop-simplify -lcssa -licm -adce
11 | -loop-simplify -lcssa -licm -alignmentfromassumptions -strip-dead-prototypes -globaldce -constmerge
12 | -loop-simplify -lcssa -licm -alignmentfromassumptions -strip-dead-prototypes -globaldce -float2int -lower-constant-intrinsics
13 | -loop-simplify -lcssa -licm -loop-unswitch
14 | -loop-simplify -lcssa -loop-rotate -licm -adce
15 | -loop-simplify -lcssa -loop-rotate -licm -alignmentfromassumptions -strip-dead-prototypes -globaldce -constmerge
16 | -loop-simplify -lcssa -loop-rotate -licm -alignmentfromassumptions -strip-dead-prototypes -globaldce -float2int -lower-constant-intrinsics
17 | -loop-simplify -lcssa -loop-rotate -licm -loop-unswitch
18 | -loop-simplify -lcssa -loop-rotate -loop-distribute -loop-vectorize
19 | -loop-simplify -lcssa -loop-sink -instsimplify -div-rem-pairs -simplifycfg
20 | -loop-simplify -lcssa -loop-unroll
21 | -loop-simplify -lcssa -loop-unroll -mldst-motion -gvn -memcpyopt -sccp -bdce
22 | -loop-simplify -loop-load-elim
23 | -simplifycfg
24 | -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor
| -globalopt -globaldce -constmerge -barrier
25 | -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor
| -globalopt -globaldce -float2int -lower-constant-intrinsics -barrier
26 | -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor
| -globalopt -mem2reg -deadargelim -barrier
27 | -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation -dse -barrier
28 | -simplifycfg -prune-eh -inline -functionattrs -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation -barrier
29 | -simplifycfg -reassociate
30 | -simplifycfg -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor -globalopt -globaldce -constmerge
31 | -simplifycfg -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor -globalopt -globaldce -float2int
| -lower-constant-intrinsics
32 | -simplifycfg -sroa -early-cse -lower-expect -forceattrs -inferattrs -ipsccp -called-value-propagation -attributor -globalopt -mem2reg -deadargelim
33 | -simplifycfg -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation -dse
34 | -simplifycfg -sroa -early-cse-memssa -speculative-execution -jump-threading -correlated-propagation

LLVM provides several optimization sequences (O0, O1, O2, O3, Os, and Oz) that
contribute either or both to enhancing speedup and reduction of code size. Os
and Oz optimization sequences are well known for code size reduction. The Oz
optimization sequence aims to reduce code size of the given LLVM IR (even
further than Os, at the cost of possibly greater execution time than O2/O3).

The Oz sequence has the goal of reducing code size and is designed using the
same set of individual optimization passes as O2. However, the individual
optimizations occur with different frequencies, and in a different order when
compared to O2. And, some passes vary the parameters for optimizations
depending on the optimization level, as different levels have different goals.

Finding the optimal order of optimization passes with repetitive occurrences
of optimizations has always been a very hard problem. One simple way to define
action space is to make every individual pass as an action for our RL model.
Firstly, this has potential to induce a very large search space, as it grows
exponentially (due to various possible combinations of individual passes, and
sequence lengths). Further, this type of modeling faces the following
complications:

  * •

Certain transformation passes cannot be applied individually. They must appear
in a specific order to maintain their mutual dependencies.

  * •

Transformation passes can potentially disturb various properties of the IR:
either the control flow of the program, or its SSA property. These properties
must be restored by other passes before other transformation passes are
applied on the IR.

Due to these reasons, several works on phase ordering proposed using different
set of optimization passes, commonly known as sub-sequences with respect to
improving the execution time [4], [6], [7], code size reduction [8] and power
utilization [23]. Similarly, in this work we too prefer to use sub-sequences
instead of individual passes as actions. We generate these sub-sequences by
utilizing the Oz sequence, as Oz is better known for code size reduction. This
reduces the search space of the model and also leads in better code size
reduction.

In this work, we propose two approaches to form the action space: the first is
to group the optimization passes manually to form sub-sequences. The second
approach involves forming a graph out of the optimization passes from Oz
sequence, and traversing it to form sub-sequences, while preserving their
dependencies. These two approaches are discussed in Sec. IV-A and Sec. IV-B.

###  IV-A Sub-sequences generated by manual grouping

As the number of passes is finite, obtaining precise sub-sequences based on
their functionality can help the model make better decisions for selecting a
sub-sequence. The logic behind this is, as for different programs, different
sub-sequences may have different performance effects. So the model can learn
better based on the program characteristics with the help of IR2Vec embedding
and make better decisions.

Table I shows the Oz optimization sequence for llvm-10. The sub-sequences
created manually from LLVM’s Oz optimization sequence are listed in Table II.
This manual grouping of passes has been done by looking into specific
functionalities of passes and the Oz sequence. For example, sequence 2
performs some module level optimizations, while sequence 4 performs inlining.
Similarly, sequence 7 contains loop related passes like loop rotate, loop
invariant code motion, loop unswitch and also combines redundant instructions,
while sequence 12 performs loop distribution and vectorization.

###  IV-B Sub-sequences generated by Oz Directed Graph (ODG)

We utilize the ordering of the passes in Oz to create new sequences. We
propose a directed graph (ODG) that is derived from the ordering of Oz passes,
as shown in Fig. 4.

Each transformation pass in the Oz flag shown in the Table I forms the node,
and the edges depict the ordering of the passes within the sequence. I.e.,
there will be an edge between two nodes if they appear consecutively in the Oz
pass sequence. For example, as simplifycfg appears after instcombine in Oz, we
create a directed edge from simplifycfg to instcombine in the graph.

We pick nodes with a degree greater than an arbitrary value $k$ as critical
nodes. Such critical nodes are the prominent nodes in the graph, where more
than $k$ passes depend on them. Hence, we start and end the traversal on the
ODG with such nodes. ODG, when traversed from a critical node, would result in
a walk where the dependencies of each pass would appear before it. We end the
traversal when we reach another critical node. We model the sub-sequences for
action space using the sequence of nodes that are visited during this
traversal. This way of obtaining sequences from the walk on ODG allows us to
get the sub-sequences that are not part of the Oz sequence while keeping the
dependencies of the passes intact.

We choose a degree $k\geq 8$ for determining the critical nodes. Consequently,
we have simplifycfg, instcomibne and, loop-simplify as critical nodes. They
have a degree of 11, 10 and 8 respectively. This results in 34 different sub-
sequences in our action space is shown in Table III.

##  V Experimentation and Result analysis

In this section we talk about the experimental setup of our framework along
with our results.

###  V-A Experimental Setup

We used LLVM-10 for the experiments on the proposed framework. The modular
structure of LLVM provides us with easy integration of our proposed action
spaces viz Manual sub-sequences listed in Table II and sub-sequences generated
with ODG listed in Table III. The IR2Vec [11] encoding and infrastructure
which we choose to represent input source programs also fits nicely with our
choice for LLVM-10.

We use 130 source code files from the single source benchmarks of LLVM-test-
suite [15]. And, we consider entirely different set of programs/benchmarks
from MiBench, LLVM-test-suite, SPEC-CPU 2006 and SPEC-CPU-2017 benchmark suite
for validation. We use the program level embeddings of IR2Vec which represents
a complete source program as a vector of 300 dimensions.

##### Training

The proposed DQN model starts the training in batches on the input training
data. Each batch is a random sample of states of IR2Vec embeddings which is
generated by the IR2Vec module to form the state space for the base
environment.

The implementation of DQN follows $\epsilon$-greedy algorithm with $\epsilon$
set to a high value initially and then annealed in subsequent steps. When
$\epsilon$ is set to a high value the DQN is said to be in the exploration
state, which involves randomly selecting actions and remembering the
associated rewards and the next state in a buffer called replay memory. The
rewards for each action is calculated using the reward function R described in
section III-C. We set $\alpha$ to 10 and $\beta$ to 5 in the reward function
to give more weight to $R_{BinSize}$ than $R_{Throughput}$. With the annealing
of $\epsilon$, the DQN enters the exploitation phase greedily by choosing the
best possible action next. After each $\mu$ step, where $\mu$ is a
hyperparameter, a random batch is sampled out of the replay memory to train
the DQN.

Learning rate is set to $10^{-4}$. Initial epsilon for exploration starts at
1.0 and drops to a minimum of 0.01 over 20000 timesteps.

We trained our models on Intel Xeon E5-2690 and Intel Xeon Gold 5122 for both
manual and ODF sets of sub-sequences for x86 and AArch64 processor. The number
of time steps per iteration was set to 1005. It took around 16 hours to train
the model on the CPU mentioned. We study the improvements in code size and
runtimes on Intel Xeon E5-2697 processor. And, we study the improvements in
code size in case of AArch64. This is obtained by cross compiling LLVM to
target Cortex-A72 processor.

###  V-B Results

We evaluated the performance of our trained model by validating programs from
MiBench [16] and SPEC-CPU (2006 and 2017) benchmarks [18, 17]. By choosing
these set of benchmarks we cover both smaller and larger sized datasets. To
check the performance of our trained model, for the above mentioned
benchmarks, we apply the optimization sequence as suggested by the trained
model. Then, we generate the binaries and compute the binary size for all the
programs. We then compare it with the binary size generated with Oz
optimization for the respective program.

In Table IV, we show the min, avg and max % of size reduction for both x86 and
AArch64 processor when we use sequences predicted by the model that is trained
with manual and ODG sub-sequences. Negative value indicates that the binary
size obtained by applying the predicted sequence is more than the binary size
obtained using Oz. Min represents the % of the minimum size improvement. Or,
if it is negative, it represents the maximum size increased. Max represents
the maximum size reduction, while avg represents average/mean size reduction
for the respective benchmark.

TABLE IV: Percentage of min, mean and max size reduction wrt manual and ODG sequences for x86 and AArch64 Benchmark | Manual sub-sequences | ODG sub-sequences
---|---|---
|  Min |  Avg |  Max |  Min |  Avg |  Max
| x86
SPEC-2017 |  -2.14 |  0.12 |  3.74 |  -1.63 |  6.19 |  22.94
SPEC-2006 |  -3.69 |  -0.56 |  2.45 |  -0.02 |  4.38 |  9.93
MiBench |  -4.82 |  -1.26 |  0.91 |  -1.28 |  1.87 |  8.68
| AArch64
SPEC-2017 |  -8.45 |  0.88 |  4.88 |  -0.99 |  5.33 |  20.29
SPEC-2006 |  -5.16 |  2.47 |  6.64 |  -0.82 |  5.04 |  9.58
MiBench |  -9.43 |  -2.31 |  0.54 |  -7.54 |  0.01 |  7.20

Table IV shows the performance, in terms of minimum, average and maximum
reduction in code size, of the model when using manual sub-sequences and ODG
sub-sequences when compared to Oz. We observe that using manual sub-sequences
can achieve maximum size reduction of $3.74\%$ for SPEC-CPU 2017 and $2.45\%$
for SPEC-CPU 2006 for x86. Similarly, for AArch64 we obtain maximum size
reduction of $4.88\%$ for SPEC-CPU 2017, and $6.64\%$ for SPEC-CPU 2006.

We also observe that for binary size reduction, the model with ODG sub-
sequences performs better than the model with manual sub-sequences for all the
considered benchmarks on both x86 and AArch64 processors. With ODG sub-
sequences, the average size reduction is $6.19\%$ and $4.38\%$ with a maximum
of $22.94\%$ and $9.93\%$ size reduction for SPEC-CPU 2017 and SPEC-CPU 2006
respectively for x86. Likewise, the average size reduction for SPEC-CPU 2017
is $5.33\%$ with a maximum of $20.29\%$ size reduction for AArch64. It can be
seen that average size reduction with ODG sub-sequences is positive for all
the benchmarks and a maximum of $6.19\%$ for SPEC-CPU 2017 for x86 processor
is achieved. Although we achieve good maximum size reduction with manual sub-
sequences, on an average it is not able to reduce binary sizes when compared
to that of ODG sequences. In the sequences obtained from ODG, there are very
few benchmarks where the binary size has increased in comparison with Oz
optimization.

We also run the binaries and measure their execution time and compare with the
execution time of Oz. The detailed analysis of runtime and code size for the
binaries generated by predicted sequences from ODG for SPEC-CPU 2017 and SPEC-
CPU 2006 wrt x86 processor are shown in Fig. 5.

TABLE V: Percentage of improvement in execution time wrt manual and ODG sequences for x86 Benchmark | Manual sub-sequences | ODG sub-sequences
---|---|---
SPEC-2017 |  7.33 |  11.99
SPEC-2006 |  -4.68 |  -4.19
MiBench |  4.13 |  6.00

Table V shows the $\%$ decrease in execution time of binaries obtained by
applying the sequences predicted by the model trained with manual or ODG sub-
sequences. We can observe that using ODG sub-sequences reduces execution time
by $11.99\%$ for SPEC-CPU 2017 and $6.00\%$ for MiBench

(a) SPEC Runtimes

(b) SPEC Runtimes

(c) SPEC code size

(d) SPEC code size

Figure 5: Runtime and Binary size for benchmarks from SPEC-CPU suite (2006 and
2017) for Oz and ODG sub-sequences (lower is better)

Fig. 5 shows the execution time improvement in seconds and binary size
reduction in kilobytes for SPEC-CPU 2017 and SPEC-CPU 2006 benchmarks. With
the ODG sub-sequences, the model predicts a sequence that leads to a reduction
in execution time for 541.leela by $45.91\%$ and 520.omnetpp by $35.08\%$. We
achieve good performance improvement for most of the SPEC-CPU 2017 benchmarks,
while execution time is increasing for most of the SPEC-CPU 2006 benchmarks.

In Fig. 5(c) and 5(d), we show the percentage reduction in binary size for the
sub-sequences generated by applying ODG sequences when compared to the
binaries generated by applying Oz on SPEC-CPU 2017 and SPEC-CPU 2006
benchmarks. It can be seen that for almost all the benchmarks, our framework
is able to reduce the binary size. However, for 519.lbm and 464.h264 there is
a slight increase in binary size.

TABLE VI: Some predicted sub-sequences 1 |  9→31→15→6→20→14→25→5→11→27→0→10→30→24→4
---|---
2 |  15→7→23→21→30→5→14→0→25→31→6→2→27→10→11
3 |  24→30→3→31→6→28→5→17→0→18→8→2→25→22→27
4 |  14→11→7→32→30→10→23→9→12→18→2→16→13→4→0
5 |  14→11→19→10→16→32→30→9→12→23→26→13→7→17→15

In Table VI, we show 5 sub-sequences predicted by the model. The first
sequence corresponding to x86 508.namd starts with initial passes from the Oz
sequences such as -simplifycfg, -sroa, -early-cse and then has loop passes,
-mem2reg, intermediate Oz passes such as -globalopt, -globaldce and ends with
loop passes. The second sequence was predicted for 525.x264 on x86. It
alternates between initial/intermediate Oz passes and loop passes. Whereas,
the third sequence starts with loop passes, initial passes from Oz, -mem2reg
and then has intermediate Oz passes and ends with loop passes. This sequence
was predicted for susan benchmark from MiBench in x86. The fourth sequence has
intermediate Oz passes, initial Oz passes, -mem2reg, loop passes and
initial/intermediate Oz passes in that order. The last two sequences
correspond to 508.namd and 511.povray benchmarks on compiling for AArch64.

As it can be observed, the predicted ODG sequences contain a mix of passes
from initial, intermediate, ending pass sub-sequences and loop passes of Oz.
Such combination of sub-sequences are not present in the Oz sequence. This
shows that our framework can exploit the performance by applying the new sub-
sequences which otherwise would have not been applied. It can also be seen
that different sub-sequences are predicted for different sources, that in turn
improves the performance.

##  VI Related Works

In recent days, several approaches that use machine learning to get better
heuristics for many compiler optimization problems like vectorization [24]
[25], inlining [26], unrolling [27], etc. have been proposed and are widely
accepted.

Several approaches have been proposed to use machine learning techniques to
solve the phase ordering problem. These works range from using genetic
algorithms [2], [28], clustering techniques [4], and Bayesian networks [29].
Also, several such approaches have been proposed to optimize for either
execution time [4], [7] or code size [30], [8]. To our understanding, ours is
the first framework that attempts to predict optimization sequences that
jointly optimizes both execution time and binary size . There have been other
works including those that optimize compile time [28] and power consumption
[31].

Most of these works are based on expert defined features. However, the process
of defining the complete set of features is cumbersome and needs domain
compiler engineer expertise. Hence, of late, deep learning is gaining
popularity with its ability to process large scale of data, and as it can
relieve the expert to pick the right set of features. The deep learning based
approaches do not require feature engineering by the expert compiler engineer.

Several approaches have been proposed to represent source code as input to
deep learning methods. Feature based approaches represent programs as
collection of hand picked features like number of basic blocks, number of
branches, etc. Milepost [5] is one such work that uses program features to
learn the better optimization sequences and the parameters for the
optimization algorithms.

On the other hand, there exist approaches that represent source codes as
distributed vector, where the meaning of the code is distributed across
various components of the high-dimensional vector. Methods like code2vec [9],
inst2vec [10] and IR2Vec [11] fall under this category. These approaches use
different abstractions of the program for forming representations. code2vec
uses the paths of Abstract Syntax Trees, while inst2vec and IR2Vec use the
Intermediate Representation of the programs to form language independent
representations. These approaches come up with representations that are
independent of the underlying applications.

Several approaches that use DNNs on reinforcement learning setup have been
proposed to solve the phase ordering problem [6], [32]. Modelling phase
ordering for compiler optimizations as a reinforcement learning fits
naturally, as the number of possible combinations of the optimizations are too
high even on fixing the sequence length. For a sequence of length $n$ and for
the number of passes $p$, a total of $p^{n}$ combinations are feasible.
Enumerating them to create a dataset to train on is intractable. Hence our
framework also models the phase ordering problem as a reinforcement learning
problem.

Different approaches have been proposed to model the output space differently.
A seminal work by Cooper et al. [2] proposed an ordering on 10 transformation
passes to optimize for code size. Another important work is by Kulkarni et al.
[28] that shows that such a space of optimization sequences is too big to
enumerate, and devise an exhaustive search technique by which they analyze
this space to automatically calculate relationships between different phases.

The recent approaches model the output space as sub-sequences, where the sub-
sequences are often grouped manually by following certain heuristics. Ashori
et al. proposed a framework, MiCOMP [4] where the passes in O3 sequence are
clustered to form groups. These clusters are then treated as sub-sequences. A
predictive model learns the ordering of these sub-sequences to achieve better
execution time.

Jain et al. [33] analyze the effects of optimizations in Oz sequence. They
divide the Oz sequence into a set of logical groups and analyze them to study
their contributions for the code size reduction.

Silva et al [34] in a similar spirit designed an approach to arrive at the
reduced set of optimization passes that perform better than Os. They come up
with a covering set of optimization passes by exploring the space of
optimizations using genetic algorithms.

Closest to our work is that of Mammadli et al. [6] They propose a framework
that uses reinforcement learning to come up with optimization sequences that
have better execution time characteristics when compared to O3. They model
action spaces by dividing the optimizations in O3 into sub-sequences. These
sub-sequences are divided into different levels of abstraction, where an
action at a higher level has more number of passes and parameters, while the
lowest level has a single pass with parameters. For a given program, the
predicted sequence has a fixed length and usually has a repetitions of the
same action. We on the other hand, design a framework to achieve better code
size characteristics while preserving, if not improving the run time, when
compared to Oz by using a double DQN model. Also, we propose two different
output spaces as actions - a sub-sequence based output space derived from Oz
in the similar spirit of Mammadli et al; sub-sequences obtained by traversing
over the Oz dependence graph (ODG). Our methodology is also different, we use
the novel IR2Vec embeddings [11] that can use the LLVM-IR representation for
encoding programs.

##  VII Conclusions

We proposed a reinforcement learning based framework to solve the compiler
phase ordering problem, that results in improving both code size and execution
time. We model an action space using two approaches, one based on manual sub-
sequences, and other by creating a graph out of Oz optimization sequence and
traversing it. Using only minimal training, we were able to obtain
improvements in terms of code size and execution time over Oz optimization
flag of LLVM-10. Our model uses static rewards calculated at the compile time
relying on LLVM-MCA for the runtime, and the binary size to model code size
characteristics. We show the code size improvements on x86 and AArch64
architectures, and execution time on x86 using standard benchmarks.

Our approach can be extened to O3 or other optimizations by constructing the
corresponding pass dependence graphs for optimizing the performance or size.
In future, we plan to extend this framework to support predicting the
parameters of the optimizations (like unroll factors and vector factors) along
with the sequence. We have integrated our framework with LLVM 10. The source
code and other relevant artifacts are available at
https://compilers.cse.iith.ac.in/projects/posetrl/.

## Acknowledgments

We are grateful to Suresh Purini for insightful discussions and guidance at
the early stage of this work. We thank Anilava Kundu for the discussions and
help in the initial stages of implementation.

This research is funded by the Department of Electronics & Information
Technology and the Ministry of Communications & Information Technology,
Government of India. This work is partially supported by a Visvesvaraya PhD
Scheme under the MEITY, GoI (PhD-MLA/04(02)/2015-16), an NSM research grant
(MeitY/R$\&$D/HPC/2(1)/2014), a Visvesvaraya Young Faculty Research Fellowship
from MeitY, and a Google PhD Fellowship.

## References

  * [1] S. R. Vegdahl, “Phase coupling and constant generation in an optimizing microcode compiler,” SIGMICRO Newsl., vol. 13, p. 125–133, Oct. 1982\.
  * [2] K. D. Cooper, P. J. Schielke, and D. Subramanian, “Optimizing for reduced code space using genetic algorithms,” in Proceedings of the ACM SIGPLAN 1999 Workshop on Languages, Compilers, and Tools for Embedded Systems, LCTES ’99, (New York, NY, USA), p. 1–9, Association for Computing Machinery, 1999.
  * [3] S.-A.-A. Touati and D. Barthou, “On the decidability of phase ordering problem in optimizing compilation,” in Proceedings of the 3rd Conference on Computing Frontiers, CF ’06, (New York, NY, USA), p. 147–156, Association for Computing Machinery, 2006.
  * [4] A. H. Ashouri, A. Bignoli, G. Palermo, C. Silvano, S. Kulkarni, and J. Cavazos, “Micomp: Mitigating the compiler phase-ordering problem using optimization sub-sequences and machine learning,” vol. 14, no. 3, 2017.
  * [5] G. Fursin, C. Miranda, O. Temam, M. Namolaru, E. Yom-Tov, A. Zaks, B. Mendelson, E. V. Bonilla, J. Thomson, H. Leather, C. K. I. Williams, M. O’Boyle, P. Barnard, E. Ashton, E. Courtois, and F. Bodin, “Milepost gcc: machine learning based research compiler,” 2008.
  * [6] R. Mammadli, A. Jannesari, and F. Wolf, “Static neural compiler optimization via deep reinforcement learning,” pp. 1–11, 11 2020.
  * [7] S. Purini and L. Jain, “Finding good optimization sequences covering program space,” ACM Trans. Archit. Code Optim., vol. 9, Jan. 2013.
  * [8] A. F. Zanella, A. F. da Silva, and F. M. Quintão, “Yacos: A complete infrastructure to the design and exploration of code optimization sequences,” in Proceedings of the 24th Brazilian Symposium on Context-Oriented Programming and Advanced Modularity, SBLP ’20, (New York, NY, USA), p. 56–63, Association for Computing Machinery, 2020.
  * [9] U. Alon, M. Zilberstein, O. Levy, and E. Yahav, “Code2vec: Learning distributed representations of code,” Proc. ACM Program. Lang., vol. 3, pp. 40:1–40:29, Jan. 2019.
  * [10] T. Ben-Nun, A. S. Jakobovits, and T. Hoefler, “Neural code comprehension: A learnable representation of code semantics,” in Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS’18, (USA), pp. 3589–3601, Curran Associates Inc., 2018.
  * [11] S. VenkataKeerthy, R. Aggarwal, S. Jain, M. S. Desarkar, R. Upadrasta, and Y. N. Srikant, “Ir2vec: Llvm ir based scalable program embeddings,” ACM Trans. Archit. Code Optim., vol. 17, Dec. 2020.
  * [12] C. J. Watkins and P. Dayan, “Q-learning,” vol. 8, pp. 279–292, Springer, 1992\.
  * [13] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” 2013.
  * [14] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” vol. 518, pp. 529–533, Nature Publishing Group, 2015.
  * [15] L. Org., “LLVM Test Suite.” https://github.com/llvm/llvm-test-suite.  Accessed 2021-08-25.
  * [16] M. Guthaus, J. Ringenberg, D. Ernst, T. Austin, T. Mudge, and R. Brown, “Mibench: A free, commercially representative embedded benchmark suite,” in Proceedings of the Fourth Annual IEEE International Workshop on Workload Characterization. WWC-4 (Cat. No.01EX538), pp. 3–14, 2001.
  * [17] J. Bucek, K.-D. Lange, and J. v. Kistowski, “Spec cpu2017: Next-generation compute benchmark,” in Companion of the 2018 ACM/SPEC International Conference on Performance Engineering, ICPE ’18, (New York, NY, USA), pp. 41–42, ACM, 2018.
  * [18] J. L. Henning, “SPEC CPU2006 benchmark descriptions,” SIGARCH Comput. Archit. News, vol. 34, no. 4, pp. 1–17, 2006.
  * [19] H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in Proceedings of the AAAI conference on artificial intelligence, vol. 30, 2016.
  * [20] Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas, “Dueling network architectures for deep reinforcement learning,” in International conference on machine learning, pp. 1995–2003, PMLR, 2016.
  * [21] M. Allamanis, E. T. Barr, P. Devanbu, and C. Sutton, “A survey of machine learning for big code and naturalness,” ACM Computing Surveys (CSUR), vol. 51, no. 4, p. 81, 2018.
  * [22] L. Org., “LLVM-MCA.” https://llvm.org/docs/CommandGuide/llvm-mca.html.
  * [23] J. Pallister, S. J. Hollis, and J. Bennett, “Identifying compiler options to minimize energy consumption for embedded platforms,” The Computer Journal, vol. 58, no. 1, pp. 95–109, 2015.
  * [24] K. Stock, L.-N. Pouchet, and P. Sadayappan, “Using machine learning to improve automatic vectorization,” ACM Trans. Archit. Code Optim., vol. 8, Jan. 2012\.
  * [25] A. Haj-Ali, N. K. Ahmed, T. Willke, Y. S. Shao, K. Asanovic, and I. Stoica, “Neurovectorizer: End-to-end vectorization with deep reinforcement learning,” in Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization, CGO 2020, (New York, NY, USA), p. 242–255, Association for Computing Machinery, 2020.
  * [26] D. Simon, J. Cavazos, C. Wimmer, and S. Kulkarni, “Automatic construction of inlining heuristics using machine learning,” in Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO), CGO ’13, (USA), p. 1–12, IEEE Computer Society, 2013.
  * [27] M. Stephenson and S. Amarasinghe, “Predicting unroll factors using supervised classification,” in International Symposium on Code Generation and Optimization, pp. 123–134, March 2005.
  * [28] P. A. Kulkarni, D. B. Whalley, G. S. Tyson, and J. W. Davidson, “Exhaustive optimization phase order space exploration,” in Proceedings of the International Symposium on Code Generation and Optimization, CGO ’06, (USA), p. 306–318, IEEE Computer Society, 2006.
  * [29] A. H. Ashouri, G. Mariani, G. Palermo, E. Park, J. Cavazos, and C. Silvano, “Cobayn: Compiler autotuning framework using bayesian networks,” ACM Trans. Archit. Code Optim., vol. 13, June 2016.
  * [30] K. Cooper, D. Subramanian, and L. Torczon, “Adaptive optimizing compilers for the 21st century,” The Journal of Supercomputing, vol. 23, 09 2002.
  * [31] R. Nobre, L. Reis, and J. Cardoso, “Compiler phase ordering as an orthogonal approach for reducing energy consumption,” 07 2018.
  * [32] Q. Huang, A. Haj-Ali, W. S. Moses, J. Xiang, I. Stoica, K. Asanović, and J. Wawrzynek, “Autophase: Compiler phase-ordering for hls with deep reinforcement learning,” 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), pp. 308–308, 2019.
  * [33] S. Jain, U. Bora, P. Kumar, V. B. Sinha, S. Purini, and R. Upadrasta, “An analysis of executable size reduction by llvm passes,” CSI Transactions on ICT, pp. 1–6, 2019.
  * [34] A. F. d. Silva, B. N. B. de Lima, and F. M. Q. a. Pereira, “Exploring the space of optimization sequences for code-size reduction: Insights and tools,” CC 2021, (New York, NY, USA), p. 47–58, Association for Computing Machinery, 2021.


[aff1]School of Applied and Engineering Physics, Cornell University, Ithaca,
NY 14850, USA. [aff2]Department of Physics and Institute for Fusion Studies,
The University of Texas at Austin, Austin, TX 78712, USA.
<EMAIL_ADDRESS>
# Carrier-Envelope Phase Controlled Electron Injection into a Laser-Wakefield
Accelerator

Jihoon Kimcor1  Tianhong Wang  Vladimir Khudik  Gennady Shvets

###### Abstract

Single cycle laser pulse propagating inside a plasma causes controllable
asymmetric plasma electron expulsion from laser according to laser carrier
envelope phase (CEP) and forms an oscillating plasma bubble. Bubble’s
transverse wakefield is modified, exhibiting periodic modulation. Injection
scheme for a laser wakefield accelerator combining a single cycle low
frequency laser pulse and a many cycle high frequency laser pulse is proposed.
The co-propagating laser pulses form a transversely oscillating wakefield
which efficiently traps and accelerates electrons from background plasma. By
tuning the initial CEP of the single cycle laser pulse, injection dynamics can
be modified independently of the many cycle pulse, enabling control of
electron bunches’ spatial profile.

##  1 INTRODUCTION

Plasma-based accelerators offer a new pathway to compact accelerators,
supporting unparalleled acceleration gradients in order of hundreds of GV/m.
In a laser-wakefield accelerator (LWFA) Malka  _et al._ (2008); Esarey,
Schroeder, and Leemans (2009), a plasma cavity is generated via the time-
averaged (ponderomotive) pressure of an ultra-intense laser pulse pushing
plasma electrons out of its way. The LWFA concept has proven to be highly
successful in generating multi-GeV, low-emittance, ultra-short electron
bunches at multiple laser facilities around the world Nakamura  _et al._
(2007); Leemans  _et al._ (2014); Gonsalves  _et al._ (2019). High-energy
electrons generated by LWFAs are promising candidates for various
applications, including TeV-scale next-generation lepton colliders Schroeder
_et al._ (2010), and high brightness radiation and particle sources Stark,
Toncian, and Arefiev (2016).

Under most circumstances relevant to laser-plasma accelerators, ponderomotive
description is sufficient for describing the response of plasma electrons to
laser pulses. Under the ponderomotive approximation, laser pulse polarization
and carrier phase play negligible roles Mora and T.M. Antonsen (1997). This
approximation breaks down for single or few-cycle laser pulses via several
mechanisms, including the ionization injection Chen  _et al._ (2010) of inner-
shell electrons into a plasma bubble that occurs in gaseous plasma targets
containing high-$Z$ ions Lifschitz and Malka (2020). Another polarization- and
phase-dependent mechanism is the creation of an asymmetric plasma ”bubble”
with an overall displacement in the laser polarization direction. The
displacement of a plasma bubble produced by a few-cycle laser pulse
propagating through the plasma in the $x-$direction with the group (phase)
velocity $v_{\rm g}$ ($v_{\rm ph}$) is determined by the oscillating carrier
envelope phase $\Phi_{\rm CEP}(x)$ (CEP). Such CEP oscillations induce a
periodic bubble displacement with the same period $v_{\rm g}T_{\rm
CEP}\approx\lambda_{L}v_{\rm g}/\left(v_{\rm ph}-v_{\rm g}\right)$ Nerush and
Kostyukov (2009). When combined with robust self-injection of plasma electrons
into the bubble Lifschitz and Malka (2020); Nerush and Kostyukov (2009); Ma
_et al._ (2016); Huijts  _et al._ (2020), the jitter of the latter can induce
betatron oscillations of the former, resulting in X-ray generation Huijts  _et
al._ (2020).

While electron injection and acceleration by few-cycle laser pulses has been
theoretically and experimentally demonstrated Huijts  _et al._ (2020); Faure
_et al._ (2018); Chou  _et al._ (2013), this approach to LWFA has limited
potential for high-energy (GeV-scale) electron acceleration. The short pulse
length and small pulse energy results in a relatively short acceleration
distance Faure  _et al._ (2018) because of reduced self-focusing Sprangle  _et
al._ (1992) and rapid diffraction of the laser pulse. Using high-density
plasmas to increase self-focusing results in continuous injection, low energy
gain, and reduced quality of the accelerated beam Faure  _et al._ (2018); Chou
_et al._ (2013).

In this paper, we show that a single-cycle laser pulse can be used as a
controllable self-injection mechanism for high-energy acceleration when
combined with a multi-cycle higher-intensity laser pulse that serves as the
LWFA driver over long distances (see Fig. 1). We show that this CEP-based
Injection (CEPI) mechanism can be realized with moderate-power injector
pulses, and is controlled by the CEP of the injector pulse. Below we show the
CEPI concept via a single particle model, derive the injection criteria, and
validate the results using 3D Particle-In-Cell (PIC) simulations.

Figure 1: Schematic of the LWFA with CEP-based injection. A transversely
oscillating plasma bubble driven by a single-cycle injector pulse (orange) and
a multi-cycle driver pulse (light blue) periodically traps electrons from
ambient plasma. Time-dependent CEP controls bubble center displacement from
the laser pulse propagation axis (dashed line), determining which electrons
are injected (red line) and which ones pass through (blue).

##  2 Theory and Test-Particle Simulations

For qualitative understanding of electron injection into an oscillating plasma
bubble, we use a simplified model of a positively-charged (devoid of
electrons) spherical plasma bubble with radius $R$ propagating with uniform
velocity $v_{b}$ Kostyukov, Pukhov, and Kiselev (2004); Kalmykov  _et al._
(2009). A moving-frame Hamiltonian describing plasma electrons interaction
with the bubble is given by
$H(\rho,t)=\sqrt{1+(\mathbf{P}+\mathbf{A})^{2}}-v_{b}P_{x}-\phi$ Kalmykov  _et
al._ (2009); Kostyukov  _et al._ (2009); Yi  _et al._ (2010), where
$\mathbf{\rho}=(\xi,y,z-z_{\rm osc})$, $\xi=x-v_{b}t$, $z_{\rm osc}(t)$ is the
transverse coordinate of the oscillating bubble center, $\mathbf{P}$ is the
canonical momentum, and $\mathbf{A}$ ($\phi$) are the vector (scalar)
potentials. For simplicity, the time, length, potential, and electron momentum
variables are normalized to $\omega_{p}^{-1}$, $k_{p}^{-1}=c/\omega_{p}$,
$m_{e}c^{2}/|e|$, and $m_{e}c$, respectively. Under the $A_{x}=-\phi=\Phi/2$
gauge, we further assume that $\Phi=(\rho^{2}-R^{2})/4$ inside and $\Phi=0$
outside the bubble Kostyukov  _et al._ (2009). Transverse oscillations $z_{\rm
osc}(t)\equiv z_{0}\cos(\omega_{\rm CEP}t+\phi_{\rm CEP})$ of the plasma
bubble excited by the injector laser pulse introduces time dependence into the
Hamiltonian. Here $z_{0}$ is the maximum bubble oscillation amplitude, and
$\phi_{\rm CEP}$ has the meaning of the CEP phase at the time of the
electron’s entrance into the bubble.

The electron equations of motion in the $x-z$ plane can be derived from
$H(\rho,t)$:

$\displaystyle\frac{dp_{x}}{dt}=-\frac{(1+v_{b})\xi}{4}+\frac{v_{z}\tilde{z}(t)}{4}-\frac{\tilde{z}(t)\dot{z}_{osc}(t)}{4},$
(1) $\displaystyle\frac{dp_{z}}{dt}=-\frac{(v_{x}+1)\tilde{z}(t)}{4},$ (2)

where the relativistic electron momenta $p_{x,z}$ are related to the
corresponding electron displacements according to $d\xi/dt=p_{x}/\gamma-v_{b}$
and $dz/dt=p_{z}/\gamma$. Finally, $\tilde{z}(t)=z-z_{osc}$ defines electron
displacement from the oscillating bubble center.

Electrons have $H=1$ prior to their interaction with the bubble, and for
robust injection to occur, Hamiltonian must evolve such that $H<0$ Kalmykov
_et al._ (2009); Yi  _et al._ (2010). Without time-dependent terms $z_{\rm
osc}(t)$ and $\dot{z}_{\rm osc}\equiv dz_{\rm osc}/dt$, the Hamiltonian is
conserved ($dH/dt=0$), and electrons cannot get trapped/accelerated by the
plasma bubble except for large radius of bubbleKostyukov  _et al._ (2009).
Bubble oscillations cause the Hamiltonian to evolve, and enable the trapping
of plasma electrons:$\frac{\partial H}{\partial
t}=\frac{dH}{dt}=\dot{p_{z}}(t)\dot{z}_{osc}(t),$ where the condition for
trapping is given by integral over electron trajectory: $\Delta
H=\int\dot{p_{z}}(t)\dot{z}_{osc}(t)dt<-1$.

Assuming that the electron passage time through the bubble, $T_{\rm pass}\sim
R$, is much shorter than $T_{\rm CEP}$, the Hamiltonian increment can be
approximated as $\Delta H^{(1)}\approx-z_{0}\omega_{\rm CEP}\sin(\phi_{\rm
CEP})\Delta p^{(0)}$, where $\Delta p^{(0)}$ is the zeroth-order ($z_{\rm
osc}=0$) transverse momentum increment of an electron passing through the
bubble. For an electron entering the bubble at its edge at $z=\pm R$ and
pulled into the interior, the maximum transverse momentum gain is $|p_{z}^{\rm
max}|\approx 0.14R^{2}$ in the limit of $v_{b}=c$ Kostyukov  _et al._ (2009).
Therefore, trapping condition for an electron entering the bubble’s edge at
the right phase ($\phi_{\rm CEP}=\pi/2$) can be estimated by
$z_{0}>7/(\omega_{\rm CEP}R^{2})$. In physical units, the injection criterion
can be expressed as $z_{0}\sim k_{p}^{-1}\sqrt{n_{\rm
crit}/n_{p}}\left(k_{p}R\right)^{-2}$ .

The injection process is visualized in Fig. 2 (a), where the results of
solving equations of motion given by Eqs. (1) and (2) are shown for two
initially quiescent electrons. The first (red star) electron enters a
transversely oscillating bubble with $\phi_{\rm CEP}=\pi/2$, while the second
(blue star) one is delayed in time so as to enter the bubble with $\phi_{\rm
CEP}=\pi$. The electrons’ initial transverse position is chosen such that
electrons enter the bubble at its lower edge ($\tilde{z}(t_{0})=-R,\xi=0$),
which is typically the optimal position for electron injection into a plasma
bubble Kalmykov  _et al._ (2009); Kostyukov  _et al._ (2009). The chosen
normalized bubble parameters ($R=5$, $z_{0}/R=0.3$, $T_{\rm CEP}=35$,
$\gamma_{b}=5$) approximately correspond to a realistic particle-in-cell (PIC)
plasma simulation presented later. According to Fig. 2(a), only the first
electron is injected into the bubble, while the second one passes through.
This phase-dependent behavior can be understood via tracking the evolution of
particle’s Hamiltonian: the trapped electron’s Hamiltonian decreases below
zero near $t=15$, fulfilling the sufficient trapping condition. In contrast,
the passing electron’s Hamiltonian increases and remains positive. In order to
be injected into the bubble, an electron must enter it at the appropriate
oscillation phase $\phi_{\rm CEP}$ of its center. Since these transverse
oscillations are periodic, injection events also happen periodically (twice
per period). Specifically, if a bubble can trap electron at $(x_{1},z_{1})$
for $\phi_{\rm CEP1}$, then it will also trap a ”partner” electron for
$\phi_{\rm CEP2}=\phi_{\rm CEP1}+\pi$ at $(x_{2}=x_{1}+v_{b}T_{\rm
CEP}/2,z_{2}=-z_{1})$.

In practice, asymmetry of bubble is generated by a single-cycle kicker pulse:
to show that such pulse can generate an asymmetric plasma flow and understand
dependency on pulse parameters, we ran a test-particle parameter scan where a
swarm of particles pass through a combined field of a quiescent bubble and an
injector pulse. By measuring the mean transverse momenta of the particles
after they pass the combined fields, we quantify the degree of asymmetry.
Bubble size and injector pulse spot size is fixed, while the cycle number and
ratio between injector pulse wavelength and plasma wavelength were varied. The
two parameters are chosen order to take advantage of the nonponderomotive
scaling law: $\delta p_{z}\propto U_{p}^{3/2}\lambda_{\rm inj}^{2}/\sigma_{\rm
inj}^{2}\sin(\phi_{\rm CEP})$ Nerush and Kostyukov (2009). Our numerical
computation shows [see Fig. 2(b)] that there is greater asymmetry in
transverse momentum when (1) injector pulse laser wavelength is longer and (2)
injector pulse laser cycle number is smaller, in qualitative agreement with
the non-ponderomotive scaling. Combined with our previous injection criterion,
this shows that using a long-wavelength injector is advantageous.

To model electron trapping from background plasma, we simulate the interaction
of the same oscillating plasma bubble with a swarm of initially resting
electrons that are seeded into a three-dimensional (3D) volume of initial
positions $(x_{0},y_{0},z_{0})$ defined by the $R<x_{0}<100$,
$-6.5<y_{0},z_{0}<6.5$ range. The equations of motion are solved for the
electrons entering the bubble during the $0<t<300$ time interval. We observe
that electron injection is periodic in time $t=x_{0}/v_{b}$, with spacing
equal to the half-period of the bubble centroid oscillation $\Delta t=T_{\rm
CEP}/2$, as can be seen in Fig. 2(c). The injections occur in short bursts at
times corresponding to the optimal bubble center oscillation phase $\phi_{\rm
CEP}=\pm\pi/2$ at the electron entrance into the bubble. By color-coding the
electrons by their injection time and plotting them in the $(t,z_{0})$ space,
we show that electrons are injected from alternating initial locations
$z_{0}=\pm R$. This shows that the particles situated near the bubble’s edge
are the easiest to trap. This can be understood from the scaling of $|\Delta
H|\propto\bar{\rho}^{2}$, where $\bar{\rho}$ is the impact parameter of an
electron entering the bubble. Therefore, those electrons “grazing” the
bubble’s edge ($\bar{\rho}\approx R$) have the largest change in their
Hamiltonian, making them the best candidates for satisfying the injection
criterion.

Figure 2:  Test particles results. (a) Trajectories in the $\xi-z$ plane and
moving reference frame: $\phi_{\rm CEP}=\pi/2$ (red) and $\phi_{\rm CEP}=\pi$
(blue). Bubble boundaries: unperturbed (black solid line) and maximally-
displaced (black dashed line). (b) Parameter scan over laser wavelength and
cycles of average electron transverse momentum $|\langle p_{z}\rangle|$ after
passing through a single-cycle pulse and a quiescent bubble. (c-d) Injected
electrons from distinct initial locations are color-coded based on their
initial location $x_{0}$ and plotted at $t=300$ (c) in the initial conditions
plane $(x_{0},z_{0})$ and (d) inside the bubble (black circle). Red line in
(c): density of injected electrons vs initial position.

Time delay between separate injection affects the longitudinal structure of
the trapped/accelerated particle beam. As the electrons are accelerated at the
back of the bubble, they advance forward through the bubble. Therefore,
longitudinal spacing between micro-bunches injected at different times is
given by $\Delta\xi\approx(c-v_{b})\Delta t\approx T_{\rm
CEP}/(4\gamma_{b}^{2})$, where $\gamma_{b}$ is the relativistic factor of the
bubble, and $v_{b}/c\approx 1-1/2\gamma_{b}^{2}$ for $\gamma_{b}\gg 1$.
Several micro-bunches are observed in Fig. 2(d).

Figure 3: Evolution of the laser pulses and plasma wakes. (a-b) Bubble in x-z
plane and on axis laser pulse of the driver (blue line) and $\lambda_{\rm
inj}=2.4\,\mu m$ kicker (red line) for injector pulse $\phi_{\rm CEP}=0$ at
(a) x=0.08 mm (b) x=0.2 mm. Green star: $\zeta$-location where the wakefields
are plotted in (c-d). (c-d) On-axis transverse wakes at
$\zeta\equiv(x-ct)/\lambda=9$ (c) for the $\lambda_{\rm inj}=2.4\,\mu m$
injector pulse CEPs $\phi_{\rm CEP}=0$ (black solid line) and $\phi_{\rm
CEP}=\pi/2$ (black dashed line) (d) for the injector pulse CEPs $\phi_{\rm
CEP}=\pi$ , $\lambda_{\rm inj}=2.4\,\mu m$ (black solid line) and
$\lambda_{\rm inj}^{(2)}=1.2\,\mu m$ (black dashed line). Red (blue) dotted-
dashed lines correspond to propagation distances $x_{1}=0.08$ mm ($x_{2}=0.2$
mm). Plasma wakes and laser electric field strength scale:
$E_{0}=e/mc\omega_{\rm dr}$. Plasma density: $n_{p}=4.4\times 10^{18}$ cm-3,
laser parameters: see Table I.

##  3 PIC Simulation Results

To model complex physical effects accompanying nonlinear interactions between
the two laser pulses and the plasma, we use a 3D particle-in-cell (PIC) code
VLPL Pukhov (1999). As shown in Fig 1, two linearly polarized laser pulses are
launched into a tenuous plasma with a plateau density $n_{p}=4.4\times
10^{18}$ cm-3 prefaced by a linear density ramp with length $L=0.03\,{\rm
mm}$. A multi-cycle short-wavelength driver pulse with the wavelength
$\lambda_{\rm dr}$ trails a single-cycle long-wavelength injector pulse with
the wavelength $\lambda_{\rm inj}$, with the delay time $\Delta T=21\,{\rm
fs}$ optimized so as to place the injected electrons close to the rear of the
plasma bubble formed by the driver pulse. Pulses’ parameters are summarized in
Table 1. Note that the injector pulse energy $U_{\rm inj}\sim 20\,{\rm mJ}$ in
this example is a small fraction of the driver pulse energy $U_{\rm dr}\sim
580\,{\rm mJ}$ because of its low power and short duration.

Laser pulse | Driver | Injector | Injector 2
---|---|---|---
Polarization | y | z | z
Wavelength | $\lambda_{\rm dr}=0.8\,{\rm\mu m}$ | $\lambda_{\rm inj}=2.4\,{\rm\mu m}$ | $\lambda_{\rm inj}^{(2)}=1.2\,{\rm\mu m}$
Duration | $T_{\rm dr}=19\,{\rm fs}$ | $T_{\rm inj}=5\,{\rm fs}$ | $T_{\rm inj}^{(2)}=2.5\,{\rm fs}$
Spot Size | $\sigma_{\rm dr}=10\,{\rm\mu m}$ | $\sigma_{\rm inj}=8\,{\rm\mu m}$ | $\sigma_{\rm inj}^{(2)}=8\,{\rm\mu m}$
Peak power | $P_{\rm dr}=31\,{\rm TW}$ | $P_{\rm inj}=3.4\,{\rm TW}$ | $P_{\rm inj}^{(2)}=13.2\,{\rm TW}$
Table 1: Pulses’ Parameters

During the early stage of co-propagation of the driver and injector pulses
[see Fig. 3(a)], the former produces the bubble while the latter induces its
transverse centroid oscillations in the direction of the injector
polarization. Bubble oscillations are manifested as a transverse on-axis field
wake $W_{\perp}\equiv E_{z}+B_{y}$ shown in Fig. 3(c), where
$\left(E_{z},B_{y}\right)(\zeta,z=y=0)$ are the transverse electric/magnetic
wakefields of the bubble. During the co-propagation phase lasting over a
distance $x\approx 0.2\,{\rm mm}$, the transverse wake oscillates with a
spatial period $cT_{\rm CEP}\approx 70\lambda_{\rm dr}$ that can be estimated
from $cT_{\rm CEP}\approx 2\lambda_{\rm
inj}\left(\frac{1}{\gamma_{b}^{2}}+\frac{n_{p}}{n_{\rm crit}(\lambda_{\rm
inj})}\right)^{-1}$ where $n_{\rm crit}(\lambda)=\pi
m_{e}c^{2}/(e^{2}\lambda^{2})$ is the critical density corresponding to
wavelength $\lambda$. The wakefield phase is easily controlled by the injector
CEP as shown in Fig. 3(c), where the transverse wakes produced by the injector
pulses with two different initial values of $\phi_{\rm CEP}=0,\pi/2$ are
phase-shifted by $90^{\circ}$ with respect to each other. On the other hand,
the magnitude and phase of the longitudinal wake $W_{\rm parallel}\equiv
E_{x}$ are CEP-independent.

The difference of our two-pulse scenario from the previously proposed scheme
utilizing a single CEP-controlled injector pulse for injection/acceleration is
that the driver pulse outruns the injector pulse as shown in Fig. 3(b). Rapid
depletion of the injection pulse is owing to its much stronger interaction
with plasma due to its longer wavelength, as expressed by the $n_{p}/n_{\rm
crit}(\lambda_{\rm inj})\gg n_{p}/n_{\rm crit}(\lambda_{\rm dr})$
relationship. Indeed, the field strength of the injection pulse significantly
decays after $L_{\rm inj}^{\rm depl}=250\lambda_{\rm dr}$ while the driver
pulse stays the same as shown in Fig. 3(d). The injection pulse depletion is
mirrored in the decay of the transverse plasma wake $W_{\perp}$ over the same
depletion distance $L_{\rm inj}^{\rm depl}$ plotted in Fig. 3(c). Therefore,
we expect the injection to stop after $x\approx L_{\rm inj}^{\rm depl}$ and
stable acceleration of the trapped electrons to proceed for a much longer
distance, leading to stable high-energy acceleration.

Figure 4: Electron injection into an oscillating bubble. (a) Densities of
ambient plasma and injected electrons in the $x-z$ plane at $x=0.32\,{\rm
mm}$. (b) Electron injection rate (solid line) and transverse locations (blue
dots) of the injected electrons as a function of time. (c) Energy spectrum and
(d) Injected electron current at $x=L_{\rm acc}=1.5\,{\rm mm}$ for different
injector pulse wavelengths: $\lambda_{\rm inj}=2.4\,{\rm\mu m}$ (blue line)
and $\lambda_{\rm inj}=1.2\,{\rm\mu m}$ (red line). Star and square labels in
(b-d) label the corresponding injection times (b), energy spectra (c), and
positions inside the bubble (d).

As shown in test-particle simulations (see Fig. 2), periodic oscillations of
the plasma bubble’s centroid induce periodic injections of electrons into the
bubble. This is observed in the PIC simulations and plotted in Fig. 4(a):
multiple micro-bunches are trapped and accelerated inside the plasma bubble
after the extinction of the injection pulse, but significantly before the
depletion of the driver pulse. Electrons are periodically injected from the
plasma into the bubble as shown in Fig. 4(b) with a periodic spacing of
$T_{\rm CEP}/2\approx 35\lambda/c$ corresponding to a half-period of the
centroid oscillation. Injection terminates after $x\approx L_{\rm inj}^{\rm
depl}$ when the transverse oscillation amplitude decreases to zero as shown in
Fig. 3(c). The total injected charge is calculated to be $Q_{1}\approx
93\,{\rm pC}$, and distributed over several micro-bunches shown in Fig. 3(a).
We have also found that the injector pulse CEP directly controls the
transverse distribution of the electrons inside the plasma bubble: the
injected bunches corresponding to $\phi_{\rm CEP}^{\prime}=\phi_{\rm CEP}+\pi$
are mirror images of each other, i.e. $z^{\prime}=-z$ and
$\zeta^{\prime}=\zeta$ for the corresponding electrons. Therefore, the CEP
phase may be extracted by observing the resulting deflection angle from one of
the resulting bunches as they exit the plasma.

Multiple injection events occurring during the co-propagation stage of the two
pulses are reflected in the complex electron spectrum after the propagation
distance $L_{\rm acc}\approx 1.5\,{\rm mm}$ shown in Fig. 4(c).
Correspondingly, the beam current plotted in Fig. 4(d) exhibits multiple peaks
separated by $\Delta\xi\approx\Delta T_{\rm cep}/4\gamma_{bb}^{2}\approx
0.66\lambda_{\rm dr}$, as was explained in the context of the test-particle
simulation shown in Fig. 2 (d). The two prominent quasi-monoenergetic peaks at
$\gamma_{1}\approx 520$ (star) and $\gamma_{2}\approx 670$ (square) correspond
to the injection times $ct_{1}\approx 250\lambda_{\rm dr}$ and $ct_{2}\approx
135\lambda_{\rm dr}$, respectively [see Fig. 4(b)]. Electrons injected at
earlier time $t_{2}<t_{1}$ reach higher energy because they are positioned
ahead of the $t_{1}$ injection inside the bubble as shown in Fig. 4(d).
Therefore, they partially deplete the wakefield, resulting in a smaller
acceleration gradient for the later injections.

The advantage of the presented two-pulse scheme involving a long-wavelength
single-cycle injector pulse was verified by simulating the following two
scenarios: (i) no injector pulse, (ii) short-wavelength ($\lambda_{\rm
inj}^{(2)}=\lambda_{\rm inj}/2$) injector pulse with $P_{\rm
inj}^{(2)}=4P_{\rm inj}=13.2\,{\rm TW}$ and $\tau=2.5\,{\rm fs}$. While the
injector pulse alone can also inject/accelerate electrons, it cannot sustain a
stable accelerating bubble over a significant distance, resulting in the
energy gain of less than $10$ MeV. Scenario (i) only yields a small
accelerated charge $q\approx 1\,{\rm pC}$. The driver pulse cannot efficiently
inject electrons into the bubble due to its slowly-evolving nature. Scenario
(ii), designed so as to preserve the ponderomotive potential $U_{p}\propto
P_{\rm inj}\lambda_{\rm inj}^{2}/\sigma_{\rm inj}^{2}$ of the injector pulse
while reducing its wavelength, also results in an inefficient charge
injection. The corresponding current profile is indicated by a red line in
Fig. 4(d), and the total injected charge $Q_{2}\approx 21\,{\rm pC}\ll Q_{1}$
[see Fig. 4(c)]. Qualitatively, this occurs because the CEP-dependent
transverse momentum $\delta p_{z}$ imparted to a plasma electron by a single-
cycle injection pulse has a non-ponderomotive scaling that favors longer
wavelengths. The smaller asymmetry in transverse momentum is evidenced by a
smaller $W_{\perp}$ amplitude compared to $2.4\,\mu$m case, as seen in Fig. 3
(d).

In conclusion, we propose and theoretically demonstrate a two-pulse CEP-
dependent scheme for laser injection and acceleration of electrons from a
preformed plasma. By combining a single-cycle long-wavelength laser pulse for
rapid electron injection and a multi-cycle short-wavelength driver pulse
providing long-distance acceleration of the injected electrons, we demonstrate
that a sequence of equally spaced ultra-short (sub-femtosecond) high-current
(tens of kA) electron micro-bunches with ultra-relativistic energies (hundreds
of MeVs) can be generated. Direct control of the betatron oscillation phase of
each micro-bunch is provided by the initial CEP of the injector pulse. We
envision that such beams can be used as compact sources of X-ray radiation.

##  4 ACKNOWLEDGMENTS

This work was supported by the DOE Grant No. DESC0019431. The authors thank
the Texas Advanced Computing Center (TACC) at The University of Texas at
Austin for providing the HPC resources.

## References

  * Malka  _et al._ (2008) V. Malka, J. Faure, Y. A. Gauduel, E. Lefebvre, A. Rousse, and K. T. Phuoc, Nat. Phys. 4, 447–453 (2008).
  * Esarey, Schroeder, and Leemans (2009) E. Esarey, C. B. Schroeder, and W. P. Leemans, Rev.Mod.Phys 81, p. 1229 (2009).
  * Nakamura  _et al._ (2007) K. Nakamura, B. Nagler, C. T´oth, C. G. R. Geddes, C. B. Schroeder, E. Esarey, and S. M. Hooker, Phys. Plasmas 14, p. 056708 (2007).
  * Leemans  _et al._ (2014) W. P. Leemans, A. J. Gonsalves, H.-S. Mao, K. Nakamura, C. Benedetti, C. B. Schroeder, C. Tóth, J. Daniels, D. E. Mittelberger, S. S. Bulanov, J.-L. Vay, C. G. R. Geddes, and E. Esarey, Phys. Rev. Lett. 113, p. 245002 (2014).
  * Gonsalves  _et al._ (2019) A. J. Gonsalves, K. Nakamura, J. Daniels, C. Benedetti, C. Pieronek, T. C. H. de Raadt, S. Steinke, J. H. Bin, S. S. Bulanov, J. van Tilborg, C. G. R. Geddes, C. B. Schroeder, C. Tóth, E. Esarey, K. Swanson, L. Fan-Chiang, G. Bagdasarov, N. Bobrova, V. Gasilov, G. Korn, P. Sasorov, and W. P. Leemans, Phys. Rev. Lett. 122, p. 084801 (2019).
  * Schroeder  _et al._ (2010) C. B. Schroeder, E. Esarey, C. G. R. Geddes, C. Benedetti, and W. P. Leemans, Phys. Rev. ST Accel. Beams 13, p. 101301 (2010).
  * Stark, Toncian, and Arefiev (2016) D. J. Stark, T. Toncian, and A. V. Arefiev, Phys. Rev. Lett. 116, p. 185003May (2016).
  * Mora and T.M. Antonsen (1997) P. Mora and J. T.M. Antonsen, Phys. Plasmas 4, p. 217 (1997).
  * Chen  _et al._ (2010) M. Chen, Z. M. Sheng, Y. Y. Ma, and J. Zhang, J. Appl. Phys. 99, p. 025003 (2010).
  * Lifschitz and Malka (2020) A. F. Lifschitz and V. Malka, New J. Phys. 14, p. 053045 (2020).
  * Nerush and Kostyukov (2009) E. N. Nerush and I. Y. Kostyukov, Phys. Rev. Lett. 103, p. 035001Jul (2009).
  * Ma  _et al._ (2016) Y. Ma, L. Chen, D. Li, W. Yan, K. Huang, M. Chen, Z. Sheng, K. Nakajima, T. Tajima, and J. Zhang, Sc. Rep 6, p. 30491 (2016).
  * Huijts  _et al._ (2020) J. Huijts, I. Andriyash, L. Rovige, A. Vernier, , and J. Faure, arXiv 2006, p. 10566 (2020).
  * Faure  _et al._ (2018) J. Faure, D. Gustas, D. Guénot, A. Vernier, F. Böhle, M. Ouillé, S. Haessler, R. Lopez-Martens, and A. Lifschitz, Plasma Phys.Contro Fusion 61, p. 014012 (2018).
  * Chou  _et al._ (2013) S. Chou, J. Xu, D. Cardenas, D. Rivas, T. Wittmann, F. K. S. Karsch, and L. Veisz, 2013 Conference on Lasers and Electro-Optics - International Quantum Electronics Conference (2013).
  * Sprangle  _et al._ (1992) P. Sprangle, E. Esarey, J. Krall, and G. Joyce, Phys. Rev. Lett. 69, 2200–2203Oct (1992).
  * Kostyukov, Pukhov, and Kiselev (2004) I. Kostyukov, A. Pukhov, and S. Kiselev, Phys. Plasmas 11, p. 5256 (2004).
  * Kalmykov  _et al._ (2009) S. Kalmykov, S. A. Yi, V. Khudik, and G. Shvets, Phys. Rev. Lett. 103, p. 135004Sep (2009).
  * Kostyukov  _et al._ (2009) I. Kostyukov, E. Nerush, A. Pukhov, and V. Seredov, Phys. Rev. Lett. 103, p. 175003Oct (2009).
  * Yi  _et al._ (2010) S. A. Yi, V. Khudik, S. Y. Kalmykov, and G. Shvets, Plasma Phys.Contro Fusion 53, p. 014012 (2010).
  * Pukhov (1999) A. Pukhov, J. Plasma Phys. 61, p. 425 (1999).