Survey on Combinatorial Register Allocation and Instruction Scheduling
Roberto Casta\~{n
Christian Schulte
Register allocation and instruction scheduling are two central compiler back-end problems that are critical for quality. % In the last two decades, combinatorial optimization has emerged as an alternative approach to traditional, heuristic algorithms for these problems. % Combinatorial approaches are generally slower but more flexible than their heuristic counterparts and have the potential to generate optimal code. % This paper surveys existing literature on combinatorial register allocation and instruction scheduling. % The survey covers approaches that solve each problem in isolation as well as approaches that integrate both problems. % The latter have the potential to generate code that is globally optimal by capturing the trade-off between conflicting register allocation and instruction scheduling decisions.
paper.tex
%[?% -*- mode: LaTeX; fill-column: 70; show-trailing-whitespace: t; -*-
\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{paralist}
\usepackage{tabu}
\usepackage{pbox}
\usepackage[hyphens]{url}
\usepackage[pdfusetitle, hidelinks]{hyperref}
\usepackage[disable]{todonotes}
\usepackage{rotating}
\usepackage{tablefootnote}
\usepackage{authblk}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{mathtools}

\newcommand{\roberto}[1]{\todo[color=lime]{#1}}
\newcommand{\invisible}[1]{}
\newcommand{\columnWidth}{3cm}
\newcommand{\newTableSection}{\hline\\[-0.3cm]}
\newcommand{\noMathIpvar}[2]{\operatorname{#1}(#2)}
\newcommand{\ipvar}[2]{$\noMathIpvar{#1}{#2}$}

\newcommand{\NN}{\ensuremath{\mathbb N}}
\newcommand{\ZZ}{\ensuremath{\mathbb Z}}
\newcommand{\RR}{\ensuremath{\mathbb R}}
\newcommand{\set}[1]{\left \{#1\right \}}
\newcommand{\summationSup}[3]{\displaystyle\sum_{\mathclap{#1}}^{#2}#3}
\newcommand{\finiteDomainNumbers}{D}
\newcommand{\yes}{$\checkmark$}
\newcommand{\no}{\textcolor{gray}{-}}
\newcommand{\localIS}{$\checkmark$}
\newcommand{\globalIS}{$\checkmark$}
\newcommand{\basicCoalescing}{basic}
\newcommand{\ultimateCoalescing}{ultimate}
\newcommand{\register}[1]{\texttt{#1}}
\newcommand{\etal}{\emph{et al.\@}}
\newcommand{\sequence}[1]{\left( #1 \right) }
\newcommand{\summation}[2]{\displaystyle\sum_{\mathclap{#1}}#2}
\newcommand{\exitWeightSymbol}{\operatorname{weight}}
\newcommand{\exitWeight}[1]{\exitWeightSymbol(#1)}
\newcommand{\exitInstructionSymbol}{\operatorname{exit}}
\newcommand{\exitInstruction}[1]{\exitInstructionSymbol(#1)}
\newcommand{\p}[1]{\left(#1\right)}
\newcommand{\entryInstructionSymbol}{\operatorname{entry}}
\newcommand{\entryInstruction}[1]{\entryInstructionSymbol(#1)}
\newcommand{\blockCostSymbol}{\operatorname{cost}}
\newcommand{\blockCost}[1]{\blockCostSymbol(#1)}

\hypersetup{
    pdfauthor={Roberto Castaneda Lozano, Christian Schulte},
    pdfsubject={},
    pdfcreator={},
    pdfproducer={},
    pdfkeywords={combinatorial optimization, register allocation, instruction scheduling},
}

\begin{document}

\title{Survey on Combinatorial Register Allocation and Instruction
  Scheduling}

\author{Roberto Casta\~{n}eda Lozano}
\author{Christian Schulte}

\affil{SCALE, KTH Royal Institute of Technology \& Swedish Institute of Computer Science, Sweden\\
  \texttt{\{rcas,cschulte\}@kth.se}}

\date{}

\maketitle

\begin{abstract}
Register allocation and instruction scheduling are two central
compiler back-end problems that are critical for
quality.
%
In the last two decades, combinatorial optimization has emerged as an
alternative approach to traditional, heuristic algorithms for these
problems.
%
Combinatorial approaches are generally slower but more flexible than
their heuristic counterparts and have the potential to generate
optimal code.
%
This paper surveys existing literature on combinatorial register
allocation and instruction scheduling.
%
The survey covers approaches that solve each problem in isolation as
well as approaches that integrate both problems.
%
The latter have the potential to generate code that is globally
optimal by capturing the trade-off between conflicting register
allocation and instruction scheduling decisions.
\end{abstract}

\section{Introduction}\label{sec:introduction}

% What are these problems and why do they matter

Compiler back-ends take an intermediate representation (IR) of a
program and generate assembly code for a particular processor.
%
The main problems in assembly code generation are instruction
selection, register allocation, and instruction scheduling.
%
Register allocation assigns temporaries (program variables in the IR)
to processor registers or to memory.
%
Instruction scheduling reorders instructions to improve their
throughput.
%
Because of the increasing access latency gap between memory and
processor registers, register allocation has a significant impact on
the performance of the generated code~\cite{Hennessy2011,Nandivada2007}.
%
Instruction scheduling has a significant impact for in-order
processors (which issue instructions in the order dictated by the
assembly) and is of paramount importance for very long instruction
word (VLIW) processors~\cite{Fisher1983} (which are able to issue
multiple, statically scheduled instructions in each execution cycle).
%
Out-of-order processors (which re-schedule instructions in hardware)
also benefit from compile-time instruction scheduling, since their
dynamic reordering algorithms have limited scope.

This paper surveys existing literature on combinatorial optimization
approaches to register allocation and instruction scheduling.
%
Traditional, heuristic approaches to these problems are complex, hard
to adapt to new processors, and generate suboptimal code.
%
Combinatorial optimization has emerged as an alternative approach that
is generally slower but more flexible than its heuristic counterparts
and has the potential to generate optimal code~\cite{Kremer1997}.
%
Furthermore, combinatorial optimization makes it possible to solve
both problems in integration to generate code that is better than the
combination of the optimal solutions to each individual problem.

The survey introduces a detailed taxonomy of the existing
combinatorial register allocation and instruction scheduling
approaches, which enables a critical comparison, illustrates the
developments and trends in the area, and exposes problems that remain
unsolved.
%
To the best of our knowledge, it contributes the first review devoted
to combinatorial approaches to register allocation and instruction
scheduling.
%
Available surveys of register
allocation~\cite{Johnsson1973,Rajlich1984,PereiraSurvey2008,Protzenko2009},
instruction scheduling~\cite{Rau1993,Allan1995,Rong2007}, and
integrated code generation~\cite{Kessler2010} ignore or present only a
very brief description of combinatorial approaches.

\paragraph{Heuristic approaches.}

Traditional back-ends apply heuristic algorithms to solve register
allocation and instruction scheduling, as these are hard combinatorial
problems for which optimal solving has been commonly considered
computationally infeasible.
%
Heuristic algorithms sacrifice optimal solutions in favor of low
complexity by taking a sequence of greedy decisions based on local
criteria.
%
Common heuristic algorithms for register allocation include
graph-coloring~\cite{Chaitin1981,Briggs1994,George1996},
puzzle-solving for irregular register
architectures~\cite{PereiraArticle2008}, and linear scan for
just-in-time compilation~\cite{Poletto1999}.
%
A classic heuristic approach to instruction scheduling is list
scheduling~\cite{Rau1993}.

\paragraph{Combinatorial approaches.}

Given the combinatorial nature of register allocation and instruction
scheduling and their significant impact on assembly code quality,
numerous ways of approaching them with combinatorial optimization
techniques have been proposed starting in the early 1990s.
%
Some factors underpinning this trend are:
%
\begin{inparaitem}[]
\item recent progress in optimization technology,
\item improved understanding of the structure of the code generation
  problems, and
\item increasing complexity and diversity of processors,
  particularly for embedded systems.
\end{inparaitem}
%
The most explored combinatorial optimization techniques for code
generation are Integer Programming, Constraint Programming, and
Partitioned Boolean Quadratic Programming.
%
These techniques generally target the same types of problems but 
often have complementary strengths.

\paragraph{Integrated code generation.}

Register allocation and instruction scheduling are interdependent
problems: the solution to one of them affects the
other~\cite{Goodman1988}.
%
Aggressive instruction scheduling often leads to programs that require
more registers to store their temporaries which makes
register allocation more difficult.
%
Conversely, doing register allocation in isolation imposes a partial
order among instructions which makes instruction
scheduling more difficult.
%
Given the interdependencies between problems, a fair amount of research has been devoted to study
combinatorial approaches that solve register allocation and
instruction scheduling in integration.
%
Integrated combinatorial approaches can deliver globally optimal
solutions by capturing the trade-offs between both problems.
%
Integrated combinatorial approaches are better suited for this problem
than their heuristic counterparts, since the underlying combinatorial
models of each code generation problem are composable as
Section~\ref{sec:integrated-approaches} shows.

\paragraph{Outline of the paper.}

Section~\ref{sec:combinatorial-optimization} describes the most
popular combinatorial optimization techniques for code generation.
%
Sections~\ref{sec:register-allocation}
and~\ref{sec:instruction-scheduling} present combinatorial approaches
to register allocation and instruction scheduling in isolation.
%
Section~\ref{sec:integrated-approaches} discusses integrated
combinatorial approaches to both problems, and the paper concludes
with Section~\ref{sec:conclusion}.

\section{Combinatorial Optimization Approaches}\label{sec:combinatorial-optimization}

Combinatorial optimization is a collection of \emph{formal} and
\emph{complete} techniques to model and solve hard combinatorial
problems.
%
Combinatorial optimization techniques are \emph{formal} since they
capture combinatorial problems with a generic, formal modeling
language.
%
They are \emph{complete} since they automatically explore the full
solution space and guarantee to eventually find the optimal solution
to a combinatorial problem (or prove that there is none).
%
This section presents the most popular combinatorial techniques for
code generation: Integer Programming (IP), Constraint Programming
(CP), and Partitioned Boolean Quadratic Programming (PBQP).
%
Search-based techniques which are not formal or complete lie outside
of the scope of this survey.
%
Examples of these are genetic algorithms~\cite{Colin2010} and dynamic
programming~\cite{Cormen2009}.

Section~\ref{sec:modeling} presents the modeling languages of each
combinatorial optimization technique; Section~\ref{sec:solving}
describes their main solving mechanisms.

\subsection{Modeling}\label{sec:modeling}

Combinatorial models consist, regardless of the particular
optimization technique used, of the following elements:

\begin{description}

\item[Variables] represent the decisions that are
  combined to form solutions.
  %
  Variables can take values from different domains (for example,
  integers~$\ZZ$ or
  Booleans~$\set{0,1}$).
  %
  The variables in a model are represented here as $x_1, x_2,
  \ldots, x_n$.

\item[Constraints] are relations over the variables that must hold for any
  solution.
  %
  The structure of the constraints depends on the applied technique.

\item[Objective function] is an expression on the model variables to be
  minimized by the solver.

\end{description}

\newcommand{\technique}[4]{#1 & #2 & #3 & #4\\}
\newcommand{\techniqueNotes}[1]{& \multicolumn{3}{c}{(#1)}\\}

\begin{table}[h]
  \setlength{\tabcolsep}{0.3cm}
  \setlength{\tabulinesep}{0.1cm}
  \begin{center}
    \scalebox{0.98}{%
    \begin{tabu}{%
        l%
        c%
        c%
        c%
      }\hline
      \rowfont{\bfseries}
      \technique{technique}{variables}{constraints}{objective function}
      \newTableSection{}%
      \technique
          {IP}
          {$x_i \in \set{0,1}$}
          {$\summationSup{i = 1}{n}{a_i x_i} \le b$}
          {$\summationSup{i = 1}{n}{c_i x_i}$}
      \techniqueNotes{$a_i, b, c_i\in\ZZ$ constant coefficients}
      \technique
          {CP}
          {$x_i \in \finiteDomainNumbers{}$}
          {any $r(x_1, x_2, \ldots, x_n)$}
          {any $f(x_1, x_2, \ldots, x_n)$}
      \techniqueNotes{$\finiteDomainNumbers{}\subset\ZZ$ finite integer domain}
      \technique
          {PBQP}
          {$x_i \in \finiteDomainNumbers{}\subset\ZZ$}
          {\no}
          {$\summationSup{i = 1}{n}{c(x_i)} + \summationSup{i,j = 1}{n}{C(x_i, x_j)}$}
      \techniqueNotes{$c(x_i)$ cost of $x_i$; $C(x_i, x_j)$ cost of $x_i \land x_j$}
    \end{tabu}
    }
  \end{center}
  \caption{Typical modeling elements for different techniques.}
  \label{tab:techniques}
\end{table}

\paragraph{Integer Programming (IP).}

IP~\cite{Nemhauser1999} is a special case of Linear Programming where
the variables range over integers.
%
This survey assumes that IP only considers \mbox{0-1} variables for
simplicity, since the vast majority of applications to code generation
is limited to such a domain.
%
The constraints and objective function of IP models are linear as
shown in Table~\ref{tab:techniques}.

\paragraph{Constraint Programming (CP).}

CP~\cite{Rossi2006} models can be seen as a generalization of IP
models where the variables take values from a finite integer domain
$D\subset\ZZ$ (which can emulate 0-1 variables if $D = \set{0,1}$), and the
constraints and the objective function are expressed by general
relations and expressions on the problem variables.
%
Often, such relations are formalized as \emph{global constraints} that
express commonly occurring substructures involving several variables.

\paragraph{Partitioned Boolean Quadratic Programming (PBQP).}

\todo{Mats: \emph{I was a little surprised to find PBQP, which seems
    rather esoteric.}}

PBQP~\cite{Scholz2002} is a special case of the Quadratic Assignment
Problem~\cite{Koopmans1957}.
%
As for CP, variables range over a finite integer domain $D\subset\ZZ$.
%
However, PBQP models do not explicitly formulate constraints.
%
Instead, each single variable assignment $x_i$ is given a cost
$c(x_i)$ and each pair of variable assignments $x_i \land x_j$ is
given a cost $C(x_i, x_j)$.
%
Pairs of assignments can be then forbidden by setting their cost to a
practically infinite value.
%
The objective function is formed by the cost of each individual
assignment and the cost of each pair of assignments as shown in
Table~\ref{tab:techniques}.

\subsection{Solving}\label{sec:solving}

\paragraph{Integer Programming.}

IP solvers proceed by exploiting \emph{linear relaxations} and
\emph{branch-and-bound search}, as well as other techniques. For an
overview of IP, see for example~\cite{Nemhauser1999}.
%
As a first step, an optimal solution to a relaxed Linear Programming
(LP) problem, where the variables can take any real value between 0
and 1, is computed.
%
LP relaxations are enabled by the linear nature of the IP models and
can be computed efficiently in practice.
%
If all the variables in the solution to the LP problem are integral,
this optimal solution also applies to the original IP problem.
%
Otherwise, search decomposes the problem into two subproblems in which
a non-integral variable is assigned the values 0 and 1 and the process
is repeated.
%
LP relaxations provide lower bounds on the value of the objective
function which are applied to prove optimality.
%
Valid solutions found during solving provide upper bounds which are
applied by branch-and-bound search to reduce the search space.

\paragraph{Constraint Programming.}

CP solvers proceed by interleaving \emph{constraint propagation} and
\emph{branch-and-bound search}. More information on CP can be found
in~\cite{Rossi2006}.
%
Constraint propagation discards values for variables that cannot be
part of any solution.
%
When no further propagation is possible, search tries several
alternatives on which constraint propagation and search is repeated.
%
As for IP solving, valid solutions found during solving are exploited
by branch-and-bound search to reduce the search space.
%
Constraint propagation is essential to reduce the search space.
%
Global constraints play a key role in propagation as they are
associated to particularly effective propagation algorithms.

\paragraph{Partitioned Boolean Quadratic Programming.}

State-of-the-art PBQP solvers proceed in two phases: \emph{reduction}
and \emph{back-propagation}~\cite{Hames2006}.
%
Reduction transforms the original problem iteratively until the
objective function becomes trivial to handle (that is, only the costs
of individual assignments $c(x_i)$ remain).
%
This is achieved by applying a set of reduction rules.
%
Special rules that reduce the problem in polynomial time while
guaranteeing optimality of the final solution are prioritized.
%
If none of these rules apply, reduction continues either by applying
branch-and-bound search to preserve optimality, or by taking a
problem-dependent, heuristic decision.
%
After reducing the problem to a trivial one, back-propagation
reconstructs the original problem by assigning values to variables to
minimize the cost of the final solution.

\section{Register Allocation}\label{sec:register-allocation}

%\subsection{The Register Allocation Problem}\label{sec:the-register-allocation-problem}

%\paragraph{Preliminary definitions.}

Register allocation takes as input a function where instructions of a
particular processor have already been selected.
%
Functions are typically represented by their control-flow graph (CFG).
%
A basic block in the CFG consists of a straight-line sequence of
\emph{instructions} of maximum length.
%
Instructions use and define \emph{temporaries}.
%
Temporaries are storage locations holding values corresponding to
program variables after instruction selection.

A \emph{program point} is located between two consecutive statements.
%
A temporary~$t$ is \emph{live} at a program point if $t$ holds a value
that might be used in the future.
%
The \emph{live range} of a temporary~$t$ is the set of program points
where $t$ is live.
%
Two temporaries \emph{interfere} if their live ranges overlap.

\paragraph{Register allocation and assignment.}

Register allocation assigns temporaries to either processor registers
or memory.
%
Register assignment maps non-interfering temporaries to the same
register to improve register utilization and avoid the use of memory
as much as possible.

\paragraph{Spilling.}

In general, optimal register utilization does not guarantee the
availability of enough processor registers and some temporaries must
be \emph{spilled} (that is, stored in memory).
%
Spilling a temporary requires the insertion of store and load
instructions to move its value to and from memory.
%
The selection and placement of these instructions has considerable
impact on the efficiency of the generated code.
%
%
\emph{Spill code optimization} reduces the cost of a spill by
optimizing the placement of its corresponding store and load
instructions.

\paragraph{Coalescing.}

The input program may contain temporaries related by \emph{copies}
(operations that replicate the value of a temporary into another).
%
Copy-related temporaries that do not interfere can be \emph{coalesced}
(assigned to the same register) in order to discard the corresponding
copies and thereby improve efficiency and reduce code size.

\paragraph{Live-range splitting.}

In some cases, it is desirable to allocate a temporary $t$ to
different locations during different parts of its live range.
%
This is achieved by \emph{splitting} $t$ into a temporary for each
part of the live range that is to be allocated to a different
location.

\paragraph{Packing.}

Each temporary $t$ has a certain bit width which is determined by
$t$'s source data type.
%
Many processors allow temporaries of small widths to be assigned
to different parts of a physical register of larger width.
%
This characteristic is commonly known as \emph{register aliasing}.
%
For example, Intel's x86~\cite{x86} combines pairs of 8-bits registers
(\register{AH}, \register{AL}) into 16-bit registers (\register{AX}).
%
Packing non-interfering temporaries into the same physical register is
key to improving register utilization.

\paragraph{Rematerialization.}

In processors with a very limited number of registers can be sometimes
beneficial to recompute (that is, \emph{rematerialize}) a reused value
rather than occupying a register until its later use, or spilling.

\paragraph{Multiple register banks.}

Some processors include multiple processor banks clustered around
different types of functional units, which often leads to alternative
temporary allocations.
%
To handle effectively these architectures, register allocation needs
to take into account the cost of allocating a temporary to different
register banks and moving its value across them.

\paragraph{Scope.}

\emph{Local} register allocation deals with one basic block at a time,
spilling all temporaries that are live at basic block boundaries.
%
\emph{Global} register allocation considers entire functions, yielding
better code as temporaries can be kept in the same register across
basic blocks.

\todo{\emph{Early Approaches} subsection where the work by
  Day~\cite{Day1970} and Luque and Ripoll~\cite{Luque1984} is
  reviewed.}

\subsection{Optimal Register Allocation (ORA)}

The most prominent combinatorial approach to global register
allocation is presented in 1996 by Goodwin and
Wilken~\cite{Goodwin1996}.
%
The approach, called \emph{Optimal Register Allocation} (ORA), is
based on an IP model that captures the full range of register
allocation subproblems (see Table~\ref{tab:register-allocation} for a
summary of the characteristics of each approach).
%
Goodwin and Wilken's ORA demonstrated, for the first time, that
combinatorial global register allocation is feasible -- although much
slower than heuristic approaches.

The ORA allocator derives an IP model in several steps.
%
First, a \emph{Live Range Graph} (LRG) is constructed for each
temporary $t$ and register $\register{r}$ in the program (Goodwin and
Wilken use the terms \emph{symbolic registers} and \emph{symbolic
  register graphs} to refer to temporaries and
LRGs~\cite{Goodwin1996}).
%
Then, different program points of the LRG are annotated with binary
decisions that correspond to 0-1 variables in the IP model and linear
constraints (called \emph{conditions} in~\cite{Goodwin1996}) involving
groups of decisions.

\paragraph{Model.}
%
The model includes four main groups of variables to capture different
subproblems:
%
\begin{inparaitem}[]
\item \emph{register assignment variables}
  \ipvar{def}{t,\register{r}}\footnote{Note that the original variable
    names and constraints in the publications cited by this survey are
    sometimes altered or simplified for the sake of clarity and
    comparability of different approaches.},
  \ipvar{use-cont}{t,\register{r}}, and
  \ipvar{use-end}{t,\register{r}} indicate whether temporary $t$ is
  assigned to $\register{r}$ at each definition and use
  ($\operatorname{use-cont}$ and $\operatorname{use-end}$ reflect
  whether the assignment continues after the use or it is ended);
\item \emph{spilling variables} \ipvar{store}{t,\register{r}},
  \ipvar{cont}{t,\register{r}}, and \ipvar{load}{t,\register{r}}
  indicate whether temporary $t$ which is assigned to register $r$ is
  stored in memory, whether the assignment to $\register{r}$ continues
  after a possible store, and whether $t$ is loaded from memory to
  $\register{r}$;
\item \emph{coalescing variables} \ipvar{elim}{t,t',\register{r}}
  indicate whether the copy from $t$ to $t'$ is eliminated by
  assigning $t$ and $t'$ to $\register{r}$; and
\item \emph{rematerialization variables} \ipvar{remat}{t,\register{r}}
  indicate whether $t$ is rematerialized into $\register{r}$.
\end{inparaitem}

\todo{picture similar to Figure 15B}

The model includes linear constraints on these variables to enforce that
%
\begin{inparaitem}[]
\item at each program point, each register holds at most one
  temporary;
\item each temporary is assigned to a register at each program point
  where it is defined and used;
\item each temporary is assigned the same register where its live
  ranges are merged at the join points of the CFG; and
\item an assignment of temporary $t$ to a register that holds right
  before a use must be conserved until the program point where $t$ is
  used.
\end{inparaitem}
%
Other constraints to capture spilling, coalescing, and
rematerialization are listed in~\cite{Goodwin1996}.

The objective function minimizes the total overhead of decisions
reflected on the spilling, coalescing, and rematerialization
variables.

\paragraph{Solving.}
%
Goodwin and Wilken use an off-the-shelf commercial IP solver to derive
register allocations and compare the results against those of GCC's
register allocator for a Hewlett-Packard PA-RISC processor~\cite{PA-RISC}.
%
The experiments reveal that in practice register allocation problems
have a relatively low average complexity, and functions of hundreds of
instructions can be optimally solved in a time scale of minutes.

\paragraph{Model extensions for irregular processors.}

The results of Goodwin and Wilken encouraged further research based on
the ORA approach.
%
In 1998, Kong and Wilken present a set of extensions~\cite{Kong1998}
to the original ORA model, including register packing and handling
multiple register banks, to deal with irregularities in register
architectures.
%
The extensions are complete enough to be able to deal with Intel's x86
architecture~\cite{x86}, which presents a fairly irregular register file.
%
The results improve drastically the code quality of GCC -- the
extended ORA approach reduces the execution time overhead due to
register allocation by $61\%$ on average.
%
An interesting finding is that IP solving, as opposed to heuristic
approaches, becomes easier in the face of less registers and more
irregularities -- the solving times of Goodwin and Wilken are reduced
by two orders of magnitude.

\paragraph{Faster ORA model.}

The (still large) solving time gap between the ORA and heuristic
approaches is reduced by Fu and Wilken in 2002~\cite{Fu2002}.
%
Fu and Wilken identify numerous conditions under which decisions are
\emph{dominated}.
%
A 0-1 decision (variable) is \emph{dominated} if there always exists
an equal or better solution where the decision is not
taken~\cite{Chu2012}.
%
Fu and Wilken remove dominated spilling variables from the model to
decrease its complexity.

Experiments where the reduced model is compared to the original one by
Goodwin and Wilken show how the IP solving process is sped-up by
four orders of magnitude: two due to increased computational power and
algorithmic improvements in the IP solver and two due to the removal
of dominated variables and their corresponding constraints.
%
The improvements allow solving $98.5\%$ of the functions in the SPEC92
integer benchmarks optimally with a time limit of 1024 seconds.

\subsection{Partitioned Boolean Quadratic Programming (PBQP)}

Scholz and Eckstein propose in 2002 an alternative combinatorial
approach to ORA that models register allocation as a PBQP
problem~\cite{Scholz2002}.
%
The simplicity with which register allocation can be reduced to a PBQP
problem and the availability since 2008 of a production-quality
implementation\footnote{
  \url{http://permalink.gmane.org/gmane.comp.compilers.llvm.devel/34822}}
within the LLVM~\cite{Lattner2004} compiler infrastructure have made
PBQP one of the most popular optimization techniques for code generation.
%
However, the simplicity of PBQP also comes with limitations -- the
range of subproblems that can be captured is narrower than that of the
more general ORA approach.
%
In particular, the PBQP approach does not support live-range splitting
(see Table~\ref{tab:register-allocation}).

\paragraph{Model.}
%
In contrast to the rather complex model of the ORA approach, the PBQP
model features a single class of variables \ipvar{a}{t} giving the
register to which temporary $t$ is assigned.
%
The decision to spill $t$ to memory is captured by including a special
spilling register $\emph{sp}$ to the domain of each variable
\ipvar{a}{t}.
%
That is, the assignment $\noMathIpvar{a}{t} = \emph{sp}$ indicates that
$t$ is spilled to memory.
%
The inclusion of spilling registers in the domains of the assignment
variables guarantees the existence of a trivial solution where all
temporaries are spilled.
%
Similarly, a special rematerialization register $\emph{rm}$ is added
to the domain of each variable \ipvar{a}{t} to introduce the
possibility of rematerializing $t$~\cite[Chapter 4]{Hames2011}.
%
For the sake of solving, Scholz and Eckstein decompose each variable
\ipvar{a}{t} into a collection of alternative Boolean variables
$\set{\noMathIpvar{x}{t,\emph{sp}}, \noMathIpvar{x}{t,\register{R0}},
  \noMathIpvar{x}{t,\register{R1}}, \ldots,
  \noMathIpvar{x}{t,\register{Rm}}}$, but the formulation with finite
integer variables is preferred here for simplicity.
%
As is characteristic of PBQP models (see Table~\ref{tab:techniques}),
constraints are expressed as practically infinite costs in individual
assignments $c(\noMathIpvar{a}{t})$ and pairs of assignments
$C(\noMathIpvar{a}{t}, \noMathIpvar{a}{t'})$.
%
Individual costs $c(\noMathIpvar{a}{t})$ are used to
%
\begin{inparaitem}[]
\item forbid assignments of temporaries to registers that do not
  belong to supported register classes,
\item take into account the overhead of spilling or rematerializing
  $t$, and
\item take into account the benefit of coalescing $t$ with
  pre-assigned registers.
\end{inparaitem}
%
Costs of pairs of assignments $C(\noMathIpvar{a}{t},
\noMathIpvar{a}{t'})$ are used to
%
\begin{inparaitem}[]
\item forbid assignments of interfering temporaries to the same
  register,
\item forbid register assignments of interfering temporaries to
  aliased registers; and
\item take into account the benefit of coalescing $t$ and $t'$.
\end{inparaitem}
%
The objective function minimizes the total cost of individual and
pairs of assignments, effectively enforcing the constraints that would
lead to a practically infinite cost.

\todo{Mats would like a figure illustrating the model}

\paragraph{Solving.}

Scholz and Eckstein devised a custom heuristic solver that follows the
procedure explained in Section~\ref{sec:solving} and an optimal solver
that applies exhaustive enumeration (as opposed to branch-and-bound)
search when no reduction rule applies.
%
Results for a digital signal processor (DSP) show that the PBQP
approach can deliver up to $13.6\%$ faster programs than traditional,
graph coloring-based heuristics.
%
At the same time, the results show a significant quality gap between
the solutions delivered by the heuristic and the optimal PBQP solver.
%
Further experimentation on the optimal PBQP solver by Hirnschrott
\etal{} supports the conclusions of Scholz and Eckstein for DSPs with
different number of registers and instruction
operands~\cite{Hirnschrott2003}.

\paragraph{Improved PBQP solver.}

In 2006, Hames and Scholz~\cite{Hames2006} contribute improved
reduction heuristics and a branch-and-bound search mechanism to the
PBQP solver.
%
The heuristics apply ideas from graph-coloring register allocation to
choose the temporary that is selected for reduction when no rule
applies.
%
As opposed to the scheme of Scholz and Eckstein, temporaries are only
committed to particular registers during the \emph{back-propagation}
phase.

Hames and Scholz's experiments for Intel's x86 architecture~\cite{x86}
show that
%
\begin{inparaitem}[]
\item Scholz and Eckstein's heuristic perform poorly for
  general-purpose code and processors such as x86 which are more
  regular than typical DSPs,
\item the branch-and-bound PBQP solver solves $97.4\%$ of the SPEC2000
  functions over 24 hours, and
\item the new heuristic PBQP solver is on average $2\%$ from the
  optimal solutions and almost in all cases generates better solutions
  than the graph coloring-based heuristics.
\end{inparaitem}

\subsection{Progressive Register Allocation (PRA)}

Koes and Goldstein introduce in 2005 a \emph{progressive} approach to
register allocation~\cite{Koes2005} which is extended and improved in
2006~\cite{Koes2006}.
%
An ideal (combinatorial) progressive solver should
%
\begin{inparaenum}[1)]
\item deliver reasonable solutions quickly,
\item improve them if more time is allowed, and
\item find the optimal one if enough time is available.
\end{inparaenum}
%
Although both the ORA and the PBQP approach can also potentially
behave progressively, in 2005 none of them were able to meet the first
condition.

Koes and Goldstein propose to model register allocation as a
multi-commodity network flow (MCNF) problem~\cite{Ahuja1993}, which
can be seen as a special case of an IP problem.
%
The MCNF problem consists of finding a flow of multiple commodities
through a network such that the cost of flowing through all arcs is
minimized and the flow capacity of each arc is not exceeded\todo{we
  need a picture here}.

The reduction of register allocation to MCNF is intuitive: each
commodity corresponds to a temporary which flows through the function
instructions.
%
This model can express detailed allocations and accurately take into
account their cost.
%
Furthermore, the approach can leverage well-understood solving
techniques available for network problems to yield progressive solving
behavior.
%
On the other hand, the flow abstraction can cope with neither
coalescing nor register packing, and since the network's flow must be
conserved, each temporary can only be allocated to a single location
at each program point.

\paragraph{Model.}

As mentioned above, each commodity in the network flow corresponds to
a temporary.
%
For each program point and storage location (registers and memory), a
node is added to the network.
%
The flow of a temporary $t$ through the network determines how $t$ it
is allocated. \todo{a visual example would surely be appreciated}
%
As for the PBQP model, a single class of variables is defined:
%
\ipvar{a}{t, \sequence{i,j}} indicates whether the temporary $t$ flows
through the arc $\sequence{i,j}$ where $i,j$ represent storage
locations at particular program points.
%
Compared to the PBQP model, the additional variable dimension
corresponding to program points permits expressing more detailed
register allocations capturing live-range splitting.
%
The model includes linear constraints to enforce that
%
\begin{inparaitem}[]
\item only one temporary flows through each register node (called
  \emph{bundle constraints} by Koes and Goldstein~\cite{Koes2006}),
  and
\item flow is conserved through the nodes (the same amount of flow
  that enters a node exits it).
\end{inparaitem}
%
The objective function minimizes the arc traversal cost for all
flows.
%
The cost of an arc \ipvar{c}{\sequence{i,j}} reflects the cost of
moving a temporary from the source location $i$ to the destination
location $j$:
%
\begin{inparaitem}[]
\item if $i$ and $j$ correspond to the same locations, no cost is
  incurred;
\item if $i$ and $j$ correspond to different registers,
  \ipvar{c}{\sequence{i,j}} is the cost of a register-to-register move
  instruction; and
\item if one of $i$ and $j$ corresponds to memory and the other to a
  register, \ipvar{c}{\sequence{i,j}} is the cost of a memory access
  instruction.
\end{inparaitem}

\paragraph{Solving.}

Although The PRA model is a valid IP formulation and can be thus
solved by a regular IP solver, Koes and Goldstein design a dedicated
solving scheme with the goal of delivering a more progressive
behavior.
%
The solving scheme is mainly based on a Lagrangian relaxation, a
general IP technique that, similarly to PBQP models, replaces hard
constraints by terms in the objective function that penalize their
violation.
%
Relaxing the bundle constraints allows to decompose the problem into
one subproblem for each temporary.
%
Each subproblem is then solved with an iterative optimization method
based on computations of shortest paths (which correspond to
least-cost individual register allocations).
%
The process is iterated until the bundle constraints are no longer
violated, at which point the solution is an optimal register
allocation.
%
At the end of each iteration, heuristics guided by information
obtained from the Lagrangian relaxation deliver progressively
improving solutions.

Koes and Goldstein compare their progressive solver with GCC's
register allocator and a commercial IP solver.
%
Experiment results with functions from different benchmarks show that
the PRA approach is indeed more progressive than other solving
techniques such as standard IP: it delivers first solutions in a time
that is competitive with traditional heuristic approaches and
generates optimal solutions for $83.5\%$ of the functions after 1000
iterations.
%
The optimal solutions yield in average a code size reduction of
$6.8\%$ compared to a heuristic graph-coloring approach.

\subsection{Other Approaches}

A recent approach that is radically different from those discussed
above is that of Krause~\cite{Krause2013}.
%
Krause exploits the property that most programming languages yield
structured programs~\cite{Thorup1998} to obtain optimal register
allocations in polynomial time, where the polynomial degree is given
by the (constant) number of registers of a processor.
%
Krause's approach applies a dynamic programming (DP) solving strategy,
where locally optimal decisions are extended to globally optimal ones.
%
The approach can deal with most of the register allocation subproblems
(see Table~\ref{tab:register-allocation}), and experiments show that
it is best suited for processors with few registers.

Other approaches have focused on decomposing the vast amount of
subproblems included in register allocation and solving each of the
resulting problems to optimality.
%
This pragmatic strategy aims at improving code generation time while
still achieving near-optimal (but not globally optimal) solutions.
%
In 2001, Appel and George propose to solve spilling (including spill
code optimization and live-range splitting) optimally with IP and to
resort to heuristic algorithms for register assignment and
coalescing~\cite{Appel2001}.
%
Their experiments demonstrate that the approach scales better than the
full-fledged ORA solver (as to be expected since less subproblems are
considered at the same time) and improves the speed of the code
generated by a heuristic register allocator by $9.5\%$.
%
In 2009, Ebner~\etal{} introduce a more structured IP approach to the
same problem as Appel and George in which spilling, spill code
optimization, and live-range splitting are modeled as a minimum cut
problem with capacity constraints~\cite{Ebner2009}.
%
A node in the minimum-cut network corresponds to a temporary at a
particular program point.
%
A solution corresponds to a cut in the network where one partition is
allocated to memory and the other to processor registers.
%
The problem is solved both with a dedicated solver based on a
Lagrangian relaxation (where the capacity constraints are relaxed) and
a commercial IP solver.
%
Interestingly, the experiments show that the IP solver performs better
than all but the simplest version of the dedicated solver, delivering
optimal solutions in less solving time.
%
Finally, Colombet~\etal{} introduce in 2011 an alternative IP
approach~\cite{Colombet2011} that additionally captures
rematerialization, overcomes some prior limitations (including the
inability of allocate a temporary to memory and a processor register
locations simultaneously), and handles programs in Static Single
Assignment (SSA) form~\cite{Cytron1991}.
%
This program form, where temporaries are only defined once, has proved
to have useful properties for register allocation~\cite{Hack2006}.
%
Colombet~\etal{}'s experiments with the EEMBC benchmarks for a VLIW
processor show that the estimated cost (that is, the optimal value to
the objective function) is improved on average by around 40 \%
compared to the model of Appel and George, where the addition of
rematerialization accounts for approximately half of the improvement.
%
An interesting finding is that these substantial estimated
improvements only correspond to modest runtime improvements, due to
interactions with the later instruction scheduling and bundling stage.

Together with their optimal spilling approach, Appel and George
launched in 2000 the \emph{Optimal Coalescing
  Challenge}\footnote{\url{http://www.cs.princeton.edu/~appel/coalesce}},
a benchmark for the second phase of their decomposed approach to
register allocation~\cite{Appel2001}.
%
In 2007, Grund and Hack present an optimal coalescing approach based
on IP~\cite{Grund2007} that solves $90.7\%$ of the coalescing problems
in the Optimal Coalescing Challenge to optimality.
%
The approach reduces the input problem by preassigning temporaries to
registers whenever it is safe and exploits the structure of the
interference graph to derive additional constraints that speed-up
solving.

\todo{alternative measure of complexity for
  Table~\ref{tab:register-allocation}: order of variables, order of
  constraints}

\begin{table}
  \newcommand{\registerAllocationApproach}[9]{#8 & #6 & #2 & #1 & #3 & #9 & #4 & #5 & #7\\}
  \renewcommand{\columnWidth}{0.6cm}
  \setlength{\tabcolsep}{2pt}
  \begin{center}
    \scalebox{0.95}{%
    \begin{tabu}{%
        l%
        c%
        c%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        c}\hline
      \rowfont{\bfseries}
      approach & TC & SC & \registerAllocationApproach{SO}{CO}{RP}{RM}{MB}{RA}{SZ}{SP}{LS}
      \newTableSection{}%
      % The 2000 number is taken from Figures 15 and 16 in [Fu2002]
      ORA~\cite{Goodwin1996,Kong1998,Fu2002} & IP & global & \registerAllocationApproach{\yes}{\yes}{\yes}{\yes}{\yes}{\yes}{$\sim{} 2000$}{\yes}{\yes}
      PBQP~\cite{Scholz2002,Hirnschrott2003,Hames2006} & PBQP & global & \registerAllocationApproach{\no}{\yes}{\yes}{\yes}{\no}{\yes}{?}{\yes}{\no}
      PRA~\cite{Koes2005,Koes2006} & IP & global & \registerAllocationApproach{\yes}{\no}{\no}{\yes}{\yes}{\yes}{?}{\yes}{\yes}
      Krause~\cite{Krause2013} & DP & global & \registerAllocationApproach{\yes}{\yes}{\yes}{\yes}{\no}{\yes}{?}{\yes}{\yes}
      % The 2000 number is taken from Figure 7 in [Appel2001]
      Appel and George~\cite{Appel2001} & IP & global & \registerAllocationApproach{\yes}{\no}{\no}{\no}{\no}{\no}{$\sim{} 2000$}{\yes}{\yes}
      Ebner~\etal{}~\cite{Ebner2009} & IP & global & \registerAllocationApproach{\yes}{\no}{\no}{\no}{\no}{\no}{?}{\yes}{\yes}
      Colombet~\etal{}~\cite{Colombet2011} & IP & global & \registerAllocationApproach{\yes}{\no}{\no}{\yes}{\no}{\no}{?}{\yes}{\yes}
      Grund and Hack~\cite{Grund2007} & IP & global & \registerAllocationApproach{\no}{\yes}{\no}{\no}{\no}{\yes}{?}{\no}{\yes}
    \end{tabu}
    }
  \end{center}
  \caption{Combinatorial register allocation approaches: technique
    (TC), scope (SC), spilling (SP), register assignment (RA),
    coalescing (CO), spill code optimization (SO), register packing
    (RP), live-range splitting (LS), rematerialization (RM), multiple
    register banks (MB), and size of largest optimal solution in
    number of instructions (SZ).}
  \label{tab:register-allocation}
\end{table}

\section{Instruction Scheduling}\label{sec:instruction-scheduling}

%\subsection{The Instruction Scheduling Problem}\label{sec:the-instruction-scheduling-problem}

%\paragraph{Instruction Scheduling.}

Instruction scheduling maps program instructions to basic blocks and
issue cycles within the blocks.
%
A valid instruction schedule must satisfy the dependencies among
instructions and cannot exceed the capacity of any processor resource
such as data buses and functional units.
%
Typically, instruction scheduling aims at minimizing the
\emph{makespan} of the computed schedule -- the number of cycles it
takes to execute the schedule.
%
All models presented in this section, unless stated otherwise, have
makespan minimization as their objective function.

\paragraph{Dependencies.}

Flow of data and control cause dependencies among instructions.
%
The dependencies in each basic block of a program form a
\emph{dependency graph} (DG) where vertices represent instructions and
an arc $\sequence{i,j}$ indicates that instruction $j$ depends on
instruction $i$.
%
Arcs in a DG are often labeled with the latency \ipvar{l}{i,j} between
the corresponding instructions.
%
The latency dictates the minimum amount of cycles that must elapse
between the issue of the two instructions.
%
For convenience, combinatorial instruction scheduling approaches
usually add artificial \emph{entry} and \emph{exit} instructions to
the DG that precede and succeed all other instructions.

\paragraph{Resources.}

Instructions share limited processor resources such as functional
units and data buses.
%
%
The organization of hardware resources varies widely among different
processors and profoundly affects the complexity of instruction
scheduling.
%
Resources are classified as \emph{single-} or \emph{multi-capacity}
depending on the number of instructions that can access them at the same
time.
%
Instructions can use either one resource each (\emph{single usage}) or
multiple resources (\emph{multiple usage}).
%
Resource usage can be \emph{uni-} or \emph{two-dimensional} depending on
whether its duration is one or longer than one.
%
Finally, resource usage is either \emph{synchronous} if usage by an
instruction $i$ starts at the issue cycle of $i$ or \emph{asynchronous}
otherwise.

\paragraph{Instruction bundling.}

Traditional RISC processors are \emph{single-issue}: they can
issue only one instruction at each clock cycle.
%
Modern processors are usually \emph{multiple-issue}: they can issue
several instructions every clock cycle.
%
To exploit this capability, in-order multiple-issue processors such as
VLIW processors require the compiler to perform \emph{instruction
  bundling}, combining instructions into bundles that are compatible
with the issue restrictions of the processor.
%
Such restrictions are often caused by underlying resource constraints
which can be handled analogously to the constraints imposed by other
processor resources.

\paragraph{Scope.}

Unlike register allocation which is almost always handled globally,
the instruction scheduling literature covers different problem scopes.
%
This can be classified into three levels, where each level can potentially
deliver better code at the expense of increasing the complexity of
scheduling: 
%
\begin{inparaenum}[]
\item \emph{local instruction scheduling} schedules instructions
  within basic blocks in isolation, under the assumption that each
  instruction is already placed in a certain basic block;
%
\item \emph{regional instruction scheduling} considers collections of
  basic blocks with a certain CFG structure; and
%
\item \emph{global instruction scheduling} considers entire functions.
\end{inparaenum}
%
Besides assigning each instruction $i$ to an issue cycle within its
block, regional and global instruction scheduling must decide the
basic block into which $i$ is placed.

\subsection{Local Instruction Scheduling}~\label{sec:local-instruction-scheduling}

\paragraph{Early approaches.}

An early combinatorial approach to local instruction scheduling is
introduced by Arya in 1985~\cite{Arya1985}.
%
This approach uses IP to compute optimal schedules for single-issue
vector processors such as the early Cray-1.
%
Arya's model includes non 0-1 integer variables \ipvar{T}{i} and
\ipvar{E}{i} representing the issue and execution cycle of each
instruction $i$, which are not necessarily equal in the targeted
processor.
%
Both dependency and resource constraints are modeled with inequalities
on pairs of cycle variables.
%
This simple model for resource constraints is possible as all
resources are of single-capacity.
%
Thus, two instructions $i$, $j$ using the same resource simultaneously
can be prevented by a constraint where either $i$ precedes $j$ or vice
versa.
%
Arya's approach includes an adaptation to single-basic block loops
based on partial unfolding.
%
Three experiments with a commercial IP solver on basic blocks of up to
36 instructions show that the approach is feasible and improves
hand-optimized code significantly.

In 1991, Ertl and Krall introduce the first local instruction
scheduling approach based on constraint programming~\cite{Ertl1991}.
%
Ertl and Krall use 
\emph{constraint logic programming}~\cite{Jaffar1987} which embeds
constraint propagation techniques into logic programming.
%
Their model targets single-issue, pipelined RISC processors where the
resource consumption of an instruction must be considered at each
stage of the pipeline.
%
The model includes, for each instruction $i$ and pipeline stage $k$, a
finite integer domain variable \ipvar{s}{i,k} representing the cycle
in which $i$ resides in $k$.
%
Dependencies among instructions are modeled as in Arya's approach.
%
Equality constraints link the different stage cycle variables of an
instruction.
%
To enforce that only one instruction at a time resides in each
pipeline stage~$k$, an \emph{alldifferent} constraint~\cite{Regin1994}
forcing all variables $\set{\noMathIpvar{c}{i_1,k},
  \noMathIpvar{c}{i_2,k}, \ldots, \noMathIpvar{c}{i_n,k}}$ to take
different values is used.
%
Experiments on a few programs for the Motorola 88100 processor show
that the approach improves $8.5\%$ and $19\%$ of the basic blocks
scheduled by the Harris C compiler and GCC 1.3 respectively.
%
However, the richness of Ertl and Krall's resource model comes at the
cost of low scalability: the experiments show that the approach cannot
handle larger problems than Arya's scheduler despite the  six year gap
between both publications.

The first combinatorial approach to instruction scheduling and
bundling for multiple-issue processors is introduced by Leupers and
Marwedel in 1997~\cite{Leupers1997}.
%
Their model is inspired by early work on IP-based scheduling for high
level synthesis~\cite{Hwang1991,Gebotys1991} and designed to target
irregular DSPs.
%
Among the additional challenges presented by such processors, the
model incorporates \emph{alternative instruction versions} and
\emph{side effect handling}.
%
Alternative instruction versions (called \emph{alternative encodings}
by Leupers and Marwedel) supports the selection of different instruction
implementations, each using different resources, for an instruction
in the input program.
%
Side effect handling
%
\begin{inparaenum}[]
\item supports inserting and scheduling \emph{no-operation instructions} that
  inhibit writes to certain registers; and
\item accounts for pairs of instructions that must be scheduled
  together if a particular version of one of them is chosen.
\end{inparaenum}
%
To schedule instructions in a basic block and take into account the
particularities of DSPs, Leupers and Marwedel introduce an IP model
with two types of 0-1 variables:
%
\begin{inparaenum}[]
\item \emph{scheduling variables} \ipvar{s}{v,i,k} indicate
  whether version $v$ of instruction $i$ is issued in cycle $k$; and
\item \emph{no-operation variables} \ipvar{n}{r,k} indicate whether
  register $r$ is inhibited by a no-operation in cycle $k$.
\end{inparaenum}
%
The model includes constraints to ensure that
%
\begin{inparaenum}[]
\item each instruction is implemented and scheduled once,
\item dependencies are satisfied,
\item instruction versions that use the same resource are not issued
  in the same cycle, and
\item no-operations are inserted to prevent destroying live data
  stored in registers.
\end{inparaenum}
%
Leupers and Marwedel present some experimental results on a few
signal-processing basic blocks for the TMS320C25 and Motorola DSP56k
processors, reporting optimal results for basic blocks of up to 45
instructions.

\paragraph{Modern approaches.}

In 2000, a publication by Wilken~\etal{}~\cite{Wilken2000} triggers a
new phase in the combinatorial instruction scheduling research.
%
This phase is characterized by a higher ambition on scalability where
the goal is to solve the largest basic blocks (containing thousands of
instructions) from established benchmarks such as SPEC95 and SPEC2000.
%
The focus shifts from being able to deal with highly irregular
architectures to
%
\begin{inparaenum}[]
\item understanding and exploiting the structure of the DG (the main
  structure of instruction scheduling), and
\item improving the underlying solving techniques by applying
  problem-specific knowledge.
\end{inparaenum}

Wilken~\etal{} use a restricted form of the IP model by Leupers and
Marwedel introduced above.
%
The model contains scheduling variables \ipvar{s}{i,k} indicating
whether instruction $i$ is issued in cycle $k$, and single-scheduling
and dependency constraints similar to those of Leupers and Marwedel.
%
The main contributions of Wilken~\etal{} are DG transformations and IP
solving techniques that make the original problem easier to solve.
%
These contributions assume single-issue processors although the model
itself can be generalized to deal with multiple-issue processors.
%
The contributed DG transformations include:
%
\begin{inparaenum}[]
\item \emph{partitioning} to decompose DGs while preserving
  optimality,
\item \emph{redundant dependency elimination} to discard dependencies
  that do not affect the solution but incur overhead in the IP
  formulation, and
\item \emph{region linearization} to enforce dominating schedules in
  specific components of the DG.
\end{inparaenum}
%
The devised solving techniques include:
%
\begin{inparaenum}[]
\item \emph{iterative range reduction} and \emph{instruction probing}
  to iteratively tighten the instruction cycle bounds and discard
  scheduling variables,
\item \emph{dependency and spreading cuts} to correct and tighten
  invalid linear relaxations, and
\item \emph{algebraic simplification} to reduce the number of
  variables involved in dependency constraints.
\end{inparaenum}
%
Experiments on an ideal processor with latencies of up to three cycles
show that the improvements by Wilken~\etal{} allow to schedule all
basic blocks from the SPEC95 floating-point benchmarks (containing up
to 1000 instructions) to optimality.

Shortly after the publication of Wilken~\etal{}, Van Beek and Wilken
introduce a CP approach targeting the same processor
model~\cite{VanBeek2001}.
%
The model contains finite integer scheduling variables \ipvar{s}{i}
representing the issue cycle of each instruction $i$.
%
Dependency constraints are directly expressed as inequalities on the
scheduling variables.
%
Similarly to Ertl and Krall~\cite{Ertl1991}, an \emph{alldifferent}
constraint~\cite{Regin1994} is used to force a single issue in each
cycle.
%
The model also contains two types of \emph{implied constraints}
(logically redundant constraints that increase the amount of
propagation and thus reduce the search space):
%
\begin{inparaenum}[]
\item \emph{distance constraints}, which impose a minimum issue
  distance among the boundary instructions of the regions as defined
  by Wilken~\etal{}; and
\item \emph{predecessor/successor constraints}, which enforce
  lower/upper bounds on the scheduling variable domains of
  instructions with multiple predecessors/successors (these
  constraints can be seen as an application of \emph{edge finding}, a
  general constraint propagation algorithm~\cite{Baptiste2001}).
\end{inparaenum}
%
Van Beek and Wilken demonstrate, using a custom-made solver, that the
CP approach is significantly faster (22 times) than the original IP
approach for the same basic blocks from the SPEC95 floating-point
benchmarks.

In 2006, Heffernan and Wilken~\cite{Heffernan2006} contribute two
further DG transformations which generalize to multiple-issue
processors: \emph{superior nodes} and \emph{superior subgraphs}.
%
The first transformation identifies pairs of independent instructions
in the DG such that relating them by an artificial dependency
preserves the optimality of the original scheduling problem.
%
The second transformation is a computationally heavier generalization
that identifies pairs of isomorphic subgraphs in the DG such that
their instructions can be also optimally related by artificial
dependencies.
%
The transformations are applied iteratively as their outcome might
expose further transformation opportunities.
%
Heffernan and Wilken show that the upper and lower makespan bounds of
the basic blocks in the SPEC2000 floating-point benchmarks are
significantly reduced after the transformations are applied,
particularly for single-issue processors.

Malik \etal{} (including Van Beek) introduce in 2008 a CP approach
that combines the above ideas to generalize to multiple-issue
processors while remaining scalable~\cite{Malik2008}.
%
The model is an extension of Van Beek and Wilken's model where
single-issue \emph{alldifferent} constraints are replaced by the more
general \emph{global cardinality} constraints~\cite{Regin1996}.
%
A \emph{global cardinality} constraint for each processor resource
limits the amount of instructions of the same type that can be issued
in the same cycle.
%
The use of this constraint enables a compact model where the
individual resource used by each instruction does not need to be
tracked with additional variables and constraints.
%
Furthermore, the model contains four types of implied constraints:
%
\begin{inparaenum}[]
\item \emph{distance} and \emph{predecessor/successor constraints}
  generalized to multiple-issue processors,
\item \emph{safe pruning constraints} which discard suboptimal
  schedules with idle cycles, and
\item \emph{superior subgraph constraints} (called \emph{dominance
  constraints} by Malik \etal{}) which apply the transformation
  introduced by Heffernan and Wilken as constraint propagation.
\end{inparaenum}
%
Unlike all previous modern approaches, Malik \etal{} experiment on a
multiple-issue processor with a bundle width varying from 1 to 6
instructions and a latency model similar to that of the PowerPC architecture.
%
The results using a custom solver for the full SPEC2000 benchmark show
that all but a few of the basic blocks (up to 2600 instructions) can
be solved to optimality.
%
Interestingly, the experiments show that the number of unsolved basic
blocks does not increase with bundle widths beyond 2 instructions.

\subsection{Regional Instruction Scheduling}

Local instruction scheduling is well understood and, despite its
theoretical complexity, has been shown in practice to be feasible for
combinatorial optimization techniques.
%
Unfortunately though, the scope of local instruction scheduling
(single basic blocks) severely limits the amount of instruction-level
parallelism that can be exploited, particularly for control-intensive
programs.
%
To overcome this limitation, regional instruction scheduling
approaches have been proposed that operate on multiple basic blocks
with a certain CFG structure.
%
The most studied structure in the context of combinatorial instruction
scheduling is the \emph{superblock}.
%
A superblock is a collection of consecutive basic blocks with a single
entry point and possibly multiple exit points~\cite{Hwu1993}.

\paragraph{Handling compensation code.}

Moving an instruction from one basic block to another often requires 
the insertion of \emph{compensation code} into yet another basic blocks to
preserve the program semantics.
%
In the case of superblocks, such a situation only arises when an
instruction is moved after an exit point where the result of the
instruction is required.
%
The published regional instruction scheduling approaches based on
combinatorial optimization avoid handling compensation code by either
disregarding the additional cost of placements of instructions
that require compensation code of just disallowing such placements.
%
The latter can be achieved by adding dependencies from such
instructions to their corresponding exit points, at the expense of
limiting the scope for optimization.

\paragraph{Superblock scheduling.}

The first optimal approach to superblock scheduling is presented by
Shobaki and Wilken in 2004~\cite{Shobaki2004}.
%
This approach is based on ad-hoc search (called \emph{enumeration} by
the authors) which is exhaustive and can thus deliver optimal
solutions in finite time.
%
The approach is not discussed in detail here as the employed technique
lacks the first step common to all combinatorial optimization
approaches (that is, the definition of the problem with a generic,
formal modeling language as discussed in Section~\ref{sec:modeling}).
%
The structure of the problem definition by Shobaki and Wilken is
similar to the model used by Heffernan and Wilken~\cite{Heffernan2006}
and Malik \etal{}~\cite{Malik2008} for local instruction scheduling.
%
The key difference with the local scheduling approaches lies in the
objective function: while local scheduling aims at minimizing the
makespan of a basic block, the objective function in superblock
scheduling minimizes the \emph{weighted makespan}.
%
The weighted makespan of a superblock is the sum of the cycles in
which each exit instruction is scheduled weighted by their exit
likelihood:
%
\begin{equation}\label{eq:superblock-objective-function}
  \summation{b \in B}{\exitWeight{b} \times \noMathIpvar{s}{\exitInstruction{b}}}
\end{equation}
%
where $B$ is the set of basic blocks in the superblock and
$\exitInstruction{b}$ gives the exit instruction of basic block $b$.
%
This objective function is common to all published combinatorial
optimization approaches for superblock scheduling.

In 2008, Malik \etal{}~\cite{Malik2008b} present a CP approach that
extends their local scheduler discussed above~\cite{Malik2008} to
superblocks and a richer resource model.
%
The basic model incorporates the following new elements to the local
scheduling one:
%
\begin{inparaitem}[]
\item the objective function for superblocks discussed
  above~(\ref{eq:superblock-objective-function}); and
\item additional variables and constraints to model two-dimensional
  resource usage and instructions that use all resources in their
  issue cycle.
\end{inparaitem}
%
To scale to larger problem sizes, the model also incorporates
superblock adaptations of
\begin{inparaenum}[]
\item \emph{distance} and
\item \emph{superior subgraph constraints}.
\end{inparaenum}
%
Malik \etal{} employ a more sophisticated solving procedure than in
previous approaches, involving
\begin{inparaenum}[]
\item \emph{portfolio search}~\cite{Gomes1997}, where the level and
  complexity of propagation is increased as solving proceeds;
\item \emph{impact-based search}~\cite{Refalo2004}, where the solver
  selects first the variable that causes most propagation to try
  different search alternatives on; and
\item \emph{decomposition}~\cite{Freuder1994}, where the independent
  basic blocks that belong to larger superblocks are solved
  separately.
\end{inparaenum}
%
A thorough experimental evaluation on the SPEC2000 benchmark for
different variations of the PowerPC processor shows that the approach
improves the results given by state-of-the-art heuristic algorithms
and conserves the scalability demonstrated for basic blocks, despite
the generalization to superblocks and the incorporation of a richer
resource model.

\paragraph{Trace scheduling.}

Superblocks can be generalized into \emph{traces} to increase further
the scope for scheduling, at the expense of higher complexity in
handling compensation code.
%
A trace is a collection of consecutive basic blocks with possibly
multiple entry and exit points~\cite{Fisher1981}.
%
Besides requiring compensation code due to exits (as for superblock
scheduling), trace scheduling must insert compensation code when
moving instructions before entry points.

The only published optimal approach for trace scheduling is due to
Shobaki \etal{}~\cite{Shobaki2009}.
%
This approach exploits the same technique as Shobaki and Wilken's
superblock scheduler and cannot thus be strictly seen as combinatorial
optimization.
%
Nevertheless, a brief discussion follows for completeness.
%
The main difference with the superblock approach by the same authors
lies in the objective function.
%
In trace scheduling, all possible execution paths through a trace must
be considered.
%
Also, it is desirable to account for the cost of inserting
compensation code outside the trace.
%
With these considerations in mind, Shobaki \etal{} propose the
following objective function to be minimized:
%
\begin{equation}\label{eq:trace-scheduling-objective-function}
 k C + \summation{p \in P}{\exitWeight{p} \times
   \p{\noMathIpvar{s}{\exitInstruction{b}} -
     \noMathIpvar{s}{\entryInstruction{b}}}}
\end{equation}
%
where $C$ is a variable indicating the number of compensation
instructions introduced in external blocks, $k$ is a constant factor
to control the trade-off between trace speed and size of the rest of
the function, and $P$ is the set of paths from some entry to some exit
in the trace.
%
The experimental results of Shobaki \etal{} for the SPEC2006 integer
benchmarks and a UltraSPARC IV processor (with an instruction bundle
width of four instructions) show that 91\% of the traces (of up to 424
instructions) can be solved optimally, yielding a slight improvement
of the weighted makespan (2.7\% on average) and a noticeable reduction
of the compensation code (15\% on average).

\paragraph{Software pipelining.}

A fundamentally different form of regional scheduling is
\emph{software pipelining}~\cite{Rau1981,Lam1988}.
%
Software pipelining schedules the instructions of multiple iterations
of a loop body simultaneously to increase the amount of available
instruction-level parallelism.
%
Typically, software pipelining is applied to inner-most loops
consisting of single basic blocks although extensions are proposed to
deal with larger structures~\cite[Section 20.4]{Rong2007}.
%
The output of software pipelining is a loop kernel with as short
makespan as possible (called \emph{initiation interval} in the context
of software pipelining), together with a prologue and epilogue to the
kernel where the instructions of the first and last iterations of the
loop are scheduled.
%
A comprehensive description of the problem is given by Allan
\etal{}~\cite{Allan1995}.

The most prominent combinatorial approach to software pipelining, based
on IP, is due to Govindarajan
\etal{}~\cite{Govindarajan1994,Altman1995}.
%
As is common in software pipelining, the approach proceeds by trying
to construct schedules of successively increasing initiation interval.
%
The first schedule found is thus guaranteed to be \emph{rate-optimal}
(that is, of minimum makespan).

The basic IP model, presented in 1994~\cite{Govindarajan1994},
includes two main groups of variables:
%
\begin{inparaitem}[]
\item \emph{kernel scheduling variables} \ipvar{a}{i,k} indicate
  whether instruction $i$ is scheduled in cycle $k$ within the loop
  kernel, and
\item \emph{offset scheduling variables} \ipvar{t}{i} give the cycle
  in which the first instance of instruction $i$ is issued.
\end{inparaitem}
%
These variables are subject to linear constraints to enforce that:
%
\begin{inparaitem}[]
\item only one instance of each instruction is scheduled within the
  loop kernel,
\item the capacity of the resources is not exceeded in any cycle,
\item the data dependencies among instructions are satisfied, and
\item the cycle of an instruction $i$ in the kernel given by
  \ipvar{a}{i,k} corresponds to its offset cycle \ipvar{t}{i}.
\end{inparaitem}
%
Furthermore, Govindarajan \etal{} propose extensions to deal with
two-dimensional resources and multiple resource usage.
%
Their experiments on 22 loops from the Livermore, SPEC92 and Whetstone
benchmark suites for a multiple-issue processor with a bundle width
varying from one to six show that the optimal solution can be found in
reasonable time (less than 30 seconds) for 91\% of the loops.
%
Although the maximum size of a loop is not indicated, the reported
initiation intervals suggest that the approach can handle loops in
the order of tens of instructions.

A year later, Altman \etal{} (including Govindarajan) present an
extension of the model~\cite{Altman1995} which copes with asynchronous
resource usage by keeping track of each individual use with 0-1
variables.
%
Altman \etal{}'s experiments on 1066 loops from the Livermore, SPEC92,
Linpack, NAS, and Whetstone benchmark suites for a variant of the
PowerPC-604 show that, despite a significant increase in the
complexity of the resource model, their extended approach can solve
75\% of the loops optimally within less than 18 minutes.

\subsection{Global Instruction Scheduling}

The ultimate scope of instruction scheduling is to consider whole
functions simultaneously, without making any assumption on the CFG
structure.
%
This is referred to as \emph{global instruction scheduling} in this
survey.

Global instruction scheduling allows an instruction to be moved from
its original basic block (called \emph{home basic block}) to any of
its predecessor or successor basic blocks (called \emph{candidate
  basic blocks}).
%
The decision to move an instruction to a predecessor (successor) basic
block is called \emph{upward (downward) code motion}.
%
An exception is made for \emph{non-speculative} instructions (for
example, those which can trigger exceptions), whose candidate basic
blocks are limited to avoid altering the semantics of the original
program.
%
Handling compensation code in global scheduling becomes a general
problem in which arbitrarily many copies of a moved instruction might
need to be replicated in different blocks to compensate for its
motion.

The only combinatorial approach to global instruction scheduling that
does not make any significant assumption on the CFG structure has been
proposed by Winkel~\cite{Winkel2004,Winkel2007}.
%
Winkel's IP-based approach is highly ambitious in that it captures 15
different types of code motion proposed in previous literature.
%
However, the basic model is relatively compact, although the complete
model comprises 11 types of variables and 35 types of constraints to
deal with the idiosyncrasies of the targeted processor and advanced
model extensions~\cite{Winkel2007}.
%
The basic model variable types are as follows:
%
\begin{inparaenum}[]
\item \emph{scheduling variables} \ipvar{s}{i,k,b} indicate whether
  instruction $i$ is scheduled in cycle $k$ in basic block $b$,
\item \emph{global motion variables} \ipvar{c}{i,b} indicate whether a
  copy of instruction $i$ is scheduled on all program paths preceding
  basic block $b$, and
\item \emph{block makespan variables} \ipvar{m}{b,k} indicate whether
  basic block $b$ has a makespan of $k$.
\end{inparaenum}
%
The basic model includes four types of constraints to enforce that
%
\begin{inparaitem}[]
\item every path leading to the home basic block of each instruction
  $i$ contains a scheduled copy of $i$,
\item the capacity of the resources is not exceeded in any cycle,
\item the data dependencies among instructions are satisfied, and
\item the makespan of each basic block $b$ is equal to the latest
  cycle of the instructions scheduled in $b$.
\end{inparaitem}
%
Additional variables and constraints are proposed, for example, to
discard bundles containing incompatible groups of
instructions~\cite{Winkel2004} and to handle two-dimensional resource usage
across basic block boundaries~\cite{Winkel2007}.
%
A detailed account of the model extensions is given in Winkel's
doctoral dissertation~\cite[Chapter 6]{Winkel2004b}.
%
The objective function is to minimize the weighted makespan of the
full function, that is the sum of the makespan of each basic block
weighed by its estimated execution frequency.

Winkel's approach solves the generated IP problems with a commercial
IP solver.
%
In contrast to most of the surveyed approaches, Winkel's model is
demonstrated analytically to yield combinatorial problems which can be
solved efficiently with IP techniques (that is, problems for which the
LP relaxations provide very tight bounds)~\cite[Chapter 5]{Winkel2004b}.
%
This analytic result is confirmed by a thorough experimental
evaluation on 104 functions from SPEC2006, containing up to 600
instructions and comprising 90\% of the execution time of the
benchmark suite.
%
The experiments for the Itanium 2 processor (with a bundle width of six
instructions) show that the approach is feasible for functions with some
hundreds of instructions, yielding a runtime speed-up of 10\% in
comparison with a heuristic global scheduler and 91\% in comparison to
optimal local instruction scheduling.

\begin{table}
  \newcommand{\instructionSchedulingApproach}[7]{#1 & #2 & #4 & #5 & #6 & #7\\}
  \renewcommand{\columnWidth}{0.6cm}
  \setlength{\tabcolsep}{2pt}
  \begin{center}
    \begin{tabu}{%
        l%
        c%
        c%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        c}\hline%
      \rowfont{\bfseries}
      approach & TC & \instructionSchedulingApproach{SC}{BD}{MC}{MU}{2D}{AS}{SZ}
      \newTableSection{}%
      Arya~\cite{Arya1985} & IP & \instructionSchedulingApproach{local}{\no}{\no}{\yes}{\yes}{\yes}{36}
      Ertl and Krall~\cite{Ertl1991} & CP & \instructionSchedulingApproach{local}{\no}{\no}{\yes}{\yes}{\yes}{24}
      Leupers and Marwedel~\cite{Leupers1997} & IP & \instructionSchedulingApproach{local}{\yes}{\no}{\yes}{\no}{\no}{45}
      Wilken~\etal{}~\cite{Wilken2000} & IP & \instructionSchedulingApproach{local}{\no}{\no}{\no}{\no}{\no}{1000}
      Van Beek and Wilken~\cite{VanBeek2001} & CP & \instructionSchedulingApproach{local}{\no}{\no}{\no}{\no}{\no}{1000}
      Malik~\etal{}~\cite{Malik2008} & CP & \instructionSchedulingApproach{local}{\yes}{\yes}{\yes}{\no}{\no}{2600}
      Malik~\etal{}~\cite{Malik2008b} & CP & \instructionSchedulingApproach{superblock}{\yes}{\yes}{\yes}{\yes}{\yes}{2600}
      Govindarajan \etal{}~\cite{Govindarajan1994} & IP & \instructionSchedulingApproach{sw.~pipelining}{\yes}{?}{\yes}{\yes}{\no}{?}
      Altman \etal{}~\cite{Altman1995} & IP & \instructionSchedulingApproach{sw.~pipelining}{\yes}{?}{\yes}{\yes}{\yes}{?}
      Winkel \etal{}~\cite{Winkel2007} & IP & \instructionSchedulingApproach{global}{\yes}{\no}{\yes}{\yes}{\no}{600}
    \end{tabu}
  \end{center}
  \caption{Combinatorial instruction scheduling approaches: technique
    (TC), scope (SC), bundling (BD), multiple usage (MU),
    two-dimensional usage (2D), asynchronous usage (AS), and size of
    largest optimal solution in number of instructions (SZ).}
  \label{tab:instruction-scheduling}
\end{table}

\section{Integrated Approaches}\label{sec:integrated-approaches}

As explained in the introduction, the strong interdependencies between
register allocation and instruction scheduling call for integrated
approaches where trade-offs can be accurately handled.
%
Combinatorial optimization is well suited for this task since, as
opposed to heuristic algorithms, combinatorial models are compositional.
%
Consequently, a significant body of literature has been built on
combinatorial integrated approaches.
%
Section~\ref{sec:register-allocation-and-instruction-scheduling}
discusses approaches focusing on register allocation and instruction
scheduling.
%
Section~\ref{sec:full-integration} reviews approaches that take one
step further, incorporating instruction selection into the
combinatorial model.

\subsection{Register Allocation and Instruction Scheduling}\label{sec:register-allocation-and-instruction-scheduling}

\paragraph{PROPAN.}

In 2000, K\"{a}stner proposes an IP-based approach that integrates
instruction scheduling with register assignment in the context of
\emph{PROPAN}, a post-pass optimization system~\cite{Kastner2000}.
%
PROPAN provides two alternative IP models: a \emph{time-based model}
and an \emph{order-based model}.

The \emph{time-based model} captures only instruction scheduling, and
it follows the structure of the majority of the instruction scheduling
models reviewed in Section~\ref{sec:instruction-scheduling}.
%
The model uses a 0-1 variable for each instruction $i$, cycle $k$, and
resource $l$ to indicate whether $i$ is issued in $k$ and allocated to
resource $l$; single-scheduling and dependency constraints similar to
those of Leupers and Marwedel (see
Section~\ref{sec:local-instruction-scheduling}); and resource
constraints to ensure that the capacity of the resources is not
exceeded in any cycle.

The \emph{order-based model} is largely based on a model devised by
Zhang~\cite{Zhang1996} and later adapted by K\"{a}stner and
Langenbach~\cite{Kastner1999}.
%
This model departs from the previously introduced IP models for
instruction scheduling in that it uses a non 0-1 integer variable to
represent the issue cycle of each instruction while retaining the
capacity to capture relatively complex resource constraints.
%
As Arya's model (see Section~\ref{sec:local-instruction-scheduling}),
dependency constraints are modeled with inequalities on pairs of cycle
variables.
%
Resource constraints are modeled as a resource allocation subproblem
based on flow networks, where a resource $l$ that \emph{flows} through
a sequence of instructions represents successive use of $l$ by
these instructions.
%
The 0-1 variables \ipvar{u}{l,i,j} indicate whether resource $l$ flows
from instruction $i$ to instruction $j$.
%
Whenever this is the case, \emph{resource serial constraints} ensure that $i$ is issued before
$j$.

K\"{a}stner describes an extension of the order-based model to
incorporate register assignment.
%
Register assignment is handled in a similar way to resource
allocation.
%
A flow network is constructed where registers flow through
instructions, where a register flowing through two instructions
represents successive writes to that register by these instructions.
%
0-1 variables \ipvar{r}{i,j} indicate whether a register flows from
instruction $i$ to instruction $j$.
%
\emph{Register serial constraints} ensure that this is only possible
if $j$ is scheduled in a cycle in which the temporaries defined by $i$
are not live anymore.

The model's scope is the superblock~\cite[Chapter 7]{Kastner2000b},
and the objective function minimizes its makespan.
%
More detail on both time- and order-based models is given in
K\"{a}stner's doctoral dissertation~\cite[Chapter 5]{Kastner2000b}.

The experimental results reported by K\"{a}stner are limited to nine
superblocks of up to 42 instructions, extracted out of digital signal
processing applications.
%
The experiments are conducted for two different processors.
%
For the ADSP-2106x processor, PROPAN (with the order-based model)
generates code that is almost 20\% faster than list scheduling in
conjunction with optimal register assignment.
%
For the TriMedia TM1000 processor, both models are compared after
solving the register assignment separately.
%
The results show that, for a processor with a wide bundle like
TriMedia TM1000 the time-based model performs better.

\paragraph{UNISON.}

In 2012, Casta\~{n}eda \etal{} present \emph{UNISON}, a CP approach
that integrates multiple subproblems of register allocation with
instruction scheduling~\cite{Castaneda2012}.
%
Unlike most integrated combinatorial approaches which extend
instruction scheduling with one or a few subproblems of register
allocation, UNISON focuses on capturing a wide array of them,
including register assignment and packing, coalescing, and spilling
for multiple register banks.
%
The scope of UNISON's register allocation is global while instructions
are scheduled locally.

Casta\~{n}eda \etal{} propose two transformations that are applied
to a function before formulating a CP problem:
%
\begin{inparaitem}[]
\item \emph{Linear Static Single Assignment construction}, where
  temporaries whose live ranges span several basic blocks are
  decomposed into one temporary per basic block and related by a
  congruence; and
\item \emph{copy extension}, where optional copy operations
  (\emph{copies} for short) are inserted at each definition and use of
  a temporary to replicate its value.
  %
  Copies can be implemented by alternative instructions with copy
  semantics such as register-to-register moves, loads, and stores; or
  made inactive by the solver.
\end{inparaitem}
%
Memory locations are modeled as individual registers, yielding a
compact model where the register to which a temporary is assigned
determines its allocation (processor registers or memory), and spill
code is reduced to simple copies between registers.

The CP model includes three main types of finite integer variables:
%
\begin{inparaenum}[]
\item \emph{register variables} \ipvar{r}{t} give the register to
  which temporary $t$ is assigned,
\item \emph{instruction variables} \ipvar{i}{o} give the instruction
  that implements operation $o$ (a special instruction is defined to
  indicate that $o$ is inactive), and
\item \emph{scheduling variables} \ipvar{s}{o} give the issue cycle
  of operation $o$.
\end{inparaenum}

Register assignment is modeled as a rectangle packing problem where
the live range of each temporary yields a rectangle to be packed into
a rectangular area with dimensions corresponding to issue cycles and
registers, similarly to the approach of Pereira and
Palsberg~\cite{Pereira2008}.
%
Coalescing constraints make copies inactive if their source and
destination temporaries are assigned to the same register.
%
Operand register constraints enforce that the operands of an operation
$o$ are assigned to registers allowed by the instruction that
implements $o$.
%
Congruence constraints connect congruent temporaries from different
basic blocks by assigning them to the same registers.
%
The instruction scheduling constraints are similar to those in the
basic model of Malik \etal{} (see
Section~\ref{sec:local-instruction-scheduling}), with the difference
that dedicated scheduling constraints such as \emph{cumulative}
constraints~\cite{Aggoun1993} are used instead of the more general
\emph{global cardinality} constraints.
%
Scheduling constraints enable an even more compact model as they can
capture two-dimensional usage without the need to resort to
additional variables and constraints.

In 2014, Casta\~{n}eda \etal{} propose an extension of UNISON's model
that captures the spill code optimization problem and improves the
scope of coalescing~\cite{Castaneda2014}.
%
The extension is based on the introduction of \emph{alternative
  temporaries} in the program representation and in the CP model,
allowing to choose the temporaries that are used and defined by each
operation among different alternative temporaries that hold the same
value.
%
In this extension, an operation $o$ is related to a temporary $t$ by
$o$'s operands, to which $t$ can be \emph{connected}.
%
The improved model includes a new type of variables: \emph{temporary
  connection} variables $y_p$ give the temporary that is connected to
operand $p$.
%
The improved model lifts the congruence constraints from temporaries
to operands and includes constraints to enforce that operations are
active if their defined temporaries are used by other active
operations.
%
The objective function is to minimize the \emph{weighted cost} of the
input function:
%
\begin{equation}\label{eq:unison-objective-function}
  \summation{b \in B}{\exitWeight{b} \times \blockCost{b}}
\end{equation}
%
where $B$ is the set of basic blocks in the function and
$\blockCost{b}$ is a generic cost function for basic block $b$.
%
By combining different definitions of $\exitWeight{b}$ and
$\blockCost{b}$, the objective function can be adapted to optimize for
different criteria such as speed or code size.

Casta\~{n}eda \etal{} introduce two methods to improve the robustness
and scalability of UNISON:
\begin{inparaenum}[]
\item \emph{presolving}, where the CP problem is reformulated before
  solving with the addition of implied constraints and bounds; and
\item \emph{decomposition}, where the CP problem is split into a
  global problem (where the decisions affecting multiple basic blocks
  are taken), and a local problem per basic block where the internal
  decisions of each basic block are taken independently.
\end{inparaenum}

A thorough experimental evaluation on 55 functions of the MediaBench
benchmark (of up to 1000 instructions) for the VLIW Hexagon processor
shows that UNISON generates code on average 7\% faster than that of a
traditional approach (LLVM) and can be easily adapted for code size
optimization (the resulting code size is on par with LLVM),
the presolving and decomposition methods are essential for UNISON's
robustness and scalability, and the improved model yields indeed
better solutions than the original model from 2012.

\paragraph{Other register allocation and instruction scheduling approaches.}

Other IP approaches have been proposed besides PROPAN and UNISON that
integrate multiple-issue instruction scheduling with subproblems of
register allocation for different program scopes.

Chang \etal{} propose in 1997 an early IP model for integrated local
instruction scheduling and spilling that includes spill code
optimization~\cite{Chang1997}.
%
The approach has similarities with the initial 2012 model of UNISON
(see above) in that input programs are extended with optional store
and load instructions after temporary definitions and before temporary
uses.
%
The model includes three types of variables:
%
\begin{inparaenum}[]
\item \emph{scheduling variables} \ipvar{s}{i,k} indicate whether
  instruction $i$ is scheduled in cycle $k$,
\item \emph{live range variables} \ipvar{l}{t,k} indicate whether
  temporary $t$ is live in cycle $k$, and
\item \emph{activeness variables} \ipvar{a}{i,k} indicate whether the
  store or load instruction $i$ is active in cycle $k$.
\end{inparaenum}
%
Single-scheduling, dependency and resource constraints are defined
similarly to other time-based models such as that of Leupers and
Marwedel (see Section~\ref{sec:local-instruction-scheduling}).
%
The number of simultaneous live temporaries in each cycle is
constrained to be less or equal than the number of available
registers.
%
The model only considers a store (load) instruction as active if it is
not scheduled in the same cycle as its predecessor (successor)
instruction in the DG.
%
The activeness variables make this distinction explicit.
%
Two alternative objective functions are proposed:
%
\begin{inparaenum}[]
\item to minimize the required number of registers given a fixed
  makespan, and
%
\item to minimize the makespan given a fixed number of available
  registers.
\end{inparaenum}
%
Two manual formulations of a basic block with 10 instructions for an
ideal processor are compared, with and without spilling.
%
The formulation with spilling takes one order of magnitude more time to be
solved to optimality.

Nagarakatte and Govindarajan propose in 2007 an IP model for register
allocation and spill code scheduling in the scope of software
pipelined loops~\cite{Nagarakatte2007}.
%
The approach assumes a software-pipelined loop kernel with a given
initiation interval and computes, if possible, a register allocation,
including assignment, spilling, and spill code optimization and
scheduling.
%
The IP model includes three types of variables:
%
\begin{inparaenum}[]
\item \emph{register assignment variables} \ipvar{a}{t,\register{r},k}
  indicate whether temporary $t$ is assigned to register
  $\register{r}$ in cycle $k$,
\item \emph{store variables} \ipvar{s}{t,\register{r},k} indicate
  whether temporary $t$ is stored from register $\register{r}$ to
  memory in cycle $k$, and
\item \emph{load variables} \ipvar{l}{t,\register{r},k} indicate
  whether temporary $t$ is loaded from memory to register
  $\register{r}$ in cycle $k$.
\end{inparaenum}

The model has several types of linear constraints to ensure that:
%
\begin{inparaenum}[]
\item temporaries are assigned to registers in the cycles in which
  they are defined and used,
\item temporaries loaded from memory are previously stored,
\item temporaries can only be stored if they are assigned to a
  register,
\item temporaries are assigned to registers in a certain cycle as a
  continuation of assignments in previous cycles or if they are just
  loaded from memory,
\item multiple temporaries are not assigned to the same register, and
\item the capacity of the memory functional units is not exceeded.
\end{inparaenum}
%
The model also includes some dominance constraints, for instance to
enforce that each temporary is stored at most once, and that
temporaries whose value is already contained in some register are not
loaded from memory.
%
The objective function is to minimize the spill code (number of stores
and loads involved in spilling).
%
The experiments for an idealized processor with a bundle width of 10
instructions on 268 loops from SPEC and Perfect Club benchmarks show
that Nagarakatte and Govindarajan's approach generates, on average,
$18\%$ and $13\%$ less spill code than the state-of-the-art heuristics
for 32 and 16 registers and avoids increasing the initiation interval
in $11\%$ and $12\%$ of the non-trivial loops for 32 and 16 registers.
%
In the worst case of a processor with 32 registers, the IP solver
takes on average 78 seconds to solve each loop to optimality.

\subsection{Full Integration}\label{sec:full-integration}

This section surveys the approaches that tackle the \emph{holy grail}
of combinatorial code generation: the addition of instruction
selection to combinatorial register allocation and instruction
scheduling.
%
Instruction selection transforms a program represented with
intermediate operations into an equivalent one that uses instructions
of a certain processor.
%
The task usually involves selecting among different \emph{instruction
  patterns} (\emph{patterns} for short) that can cover one or more
nodes and edges of a processor-independent DG.
%
This task closely interacts with register allocation and
instruction scheduling, since the selection of processor instructions
imposes constraints on the processor resources and register banks
that are used by the program.

\begin{table}
  \newcommand{\integratedApproachRA}[8]{#7 & #6 & #2 & #1 & #3 & #8 & #4 & #5}
  \newcommand{\integratedApproachIS}[5]{#1 & #3 & #4 & #5}
  \renewcommand{\columnWidth}{0.6cm}
  \setlength{\tabcolsep}{2pt}
  \begin{center}
    \rotatebox{90}{%
      \scalebox{0.98}{%
    \begin{tabular}{%
        l%
        c%
        c%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        >{\centering\arraybackslash}p{\columnWidth}%
        c}\hline
      \textbf{approach} & \textbf{TC} & \textbf{SC} & \integratedApproachRA{\textbf{SO}}{\textbf{CO}}{\textbf{RP}}{\textbf{RM}}{\textbf{MB}}{\textbf{RA}}{\textbf{SP}}{\textbf{LS}} & \integratedApproachIS{\textbf{BD}}{\textbf{MC}}{\textbf{MU}}{\textbf{2D}}{\textbf{AS}} & \textbf{IS} & \textbf{SZ}\\\newTableSection{}%
      PROPAN~\cite{Kastner2000} & IP & superblock & \integratedApproachRA{\no}{\no}{\no}{\no}{\yes}{\yes}{\no}{\no} & \integratedApproachIS{\yes}{\no}{\yes}{\yes}{\no} & \no & 42 \\
      UNISON~\cite{Castaneda2014} & CP & global   & \integratedApproachRA{\yes}{\yes}{\yes}{\no}{\yes}{\yes}{\yes}{\yes} & \integratedApproachIS{\yes}{\yes}{\yes}{\yes}{\no} & \no & 605 \\
      Chang~\etal{}~\cite{Chang1997} & IP & local & \integratedApproachRA{\yes}{\no}{\no}{\no}{\no}{\no}{\yes}{\no} & \integratedApproachIS{\yes}{\no}{\yes}{\no}{\no} & \no & $\sim{} 10$ \\
      Nagar.~\etal{}~\cite{Nagarakatte2007} & IP & sw.~pipelining & \integratedApproachRA{\yes}{\no}{\no}{\no}{\no}{\yes}{\yes}{\yes} & \integratedApproachIS{\yes}{\yes}{\no}{\no}{\no} & \no & ? \\
      Wilson~\etal{}~\cite{Wilson1994} & IP & global & \integratedApproachRA{\no}{\yes}{\no}{\no}{\no}{\yes}{\yes}{\yes} & \integratedApproachIS{\yes}{\no}{\yes}{\no}{\no} & \yes & 30 \\
      Gebotys~\cite{Gebotys1997} & IP & local & \integratedApproachRA{\yes}{\no}{\no}{\no}{\yes}{\yes}{\yes}{\yes} & \integratedApproachIS{\no}{\no}{\yes}{\no}{\no} & \yes & 108 \\
      ICG~\cite{Bashford1999} & CP & local & \integratedApproachRA{\yes}{\yes}{\no}{\no}{\yes}{\yes}{\yes}{\yes} & \integratedApproachIS{\yes}{\no}{\no}{\no}{\no} & \yes & 23 \\
      OPTIMIST~\cite{Eriksson2012} & IP & sw.~pipelining & \integratedApproachRA{\yes}{\no}{\no}{\no}{\yes}{\no}{\yes}{\yes} & \integratedApproachIS{\yes}{\no}{\yes}{\yes}{\yes} & \yes & 100 \\
    \end{tabular}
      }
    }
  \end{center}
  \vspace{-0.5cm}
  \caption{Integrated combinatorial approaches: technique (TC), scope
    (SC), spilling (SP), register assignment (RA), coalescing (CO),
    spill code optimization (SO), register packing (RP), live-range
    splitting (LS), rematerialization (RM), multiple register banks
    (MB), bundling (BD), multiple usage (MU), two-dimensional usage
    (2D), asynchronous usage (AS), instruction selection (IS), and
    size of largest optimal solution in number of instructions (SZ).}
  \label{tab:integrated}
  \vspace{-0.5cm}
\end{table}

\paragraph{Wilson~\etal{}}

The first combinatorial approach to fully integrated code generation
is proposed by Wilson~\etal{} in 1994~\cite{Wilson1994,Wilson2002}.
%
The model is designed with the goal of generating code for DSPs with
very limited and irregular register banks such as Motorola's DSP56001.
%
Remarkably, the IP model captures more register allocation subproblems
than many approaches without instruction selection.
%
Unfortunately, experimental results are not publicly available, which
has limited the impact of the approach.

Wilson~\etal{}'s IP model is rather compact in relation to the amount
of captured subproblems.
%
Since instruction selection is included, the input program is
represented at a higher level of abstraction, in terms of a DG with
processor-independent \emph{operations} and \emph{data edges}
(\emph{edges for short}).
%
Both operations as well as edges can be deactivated by the solver to
model internal operations of complex processor instructions, optional
spilling, and alternative implementations of certain operations such
as computations of memory addresses.
%
Unlike most studied approaches, the register allocation submodel is
based on edges rather than temporaries, which increases the model
granularity since multiple uses of the same temporary yield different
edges.
%
Similarly to UNISON (see
Section~\ref{sec:register-allocation-and-instruction-scheduling}),
Wilson~\etal{} extend the input program with optional stores, loads,
and register-to-register moves~\cite{Wilson2002}.

Similarly to Arya (see Section~\ref{sec:local-instruction-scheduling}),
the model uses non 0-1 integer variables $c_o$ representing the cycle
in which each operation $o$ is issued.
%
As discussed previously, this makes the formulation of dependency
constraints straightforward but limits the generality of the resource
model.
%
The model is completed with the following types of 0-1 variables:
%
\begin{inparaenum}[]
\item \emph{pattern selection variables} \ipvar{s}{p} indicate whether
  pattern $p$ is selected,
\item \emph{operation and edge activation variables} \ipvar{a}{o} and
  \ipvar{a}{e} indicate whether operation $o$ and edge $e$ are active,
  and
\item \emph{register assignment variables} \ipvar{a}{e,\register{r}}
  indicate whether edge $e$ is assigned to register $\register{r}$.
\end{inparaenum}
%
Instruction selection constraints enforce that:
%
\begin{inparaenum}[]
\item pattern coverings do not overlap,
\item edges and operations are active iff they are not internalized by
  a pattern covering,
\item active edges are assigned to a register,
\item edges related across basic blocks are assigned to the same
  register (similarly to the congruence constraints in UNISON),
\item the definers of active edges are scheduled before their users,
\item active operations that use the same resource are not scheduled
  in the same cycle, and
\item the definers and users of active edges that are assigned to the
  same register are scheduled such that the live ranges do not
  overlap.
\end{inparaenum}
%
Besides these constraints, an additional set of constraints allow to
model alternative implementations, in which the solver chooses one out
of a group of operations to appear in the generated code.
%
The objective function minimizes the weighted makespan of the input
function.

Unfortunately, Wilson~\etal{} do not report detailed experimental
results for their integrated code generation approach.
%
The paper discussions indicate that the approach is able to generate
optimal code for up to 30 operations, of the same quality as
hand-optimized versions.
%
Wilson~\etal{} propose some techniques to scale up the approach,
including taking preliminary decisions heuristically, and decomposing
functions into regions of basic blocks to be solved
incrementally~\cite{Wilson2002}.

\paragraph{Gebotys.}

An alternative, IP-based approach to fully integrated code generation
is due to Gebotys in 1997~\cite{Gebotys1997}.
%
Gebotys' approach solves instruction compaction as opposed to full
instruction scheduling.
%
Instruction compaction assumes a given fixed sequence of instructions
and decides, for each instruction $i$ in the sequence whether $i$ is
scheduled in parallel with its successor.
%
Solving compaction only dramatically reduces the search space at the
cost of limiting the capacity to exploit instruction-level
parallelism.

The model proposed by Gebotys is composed mostly of linear constraints
derived from \emph{Horn clauses}.
%
A Horn clause is a logical formula with at most one
conclusion~\cite{Horn1951}, and it is shown that the linear relaxation
of an IP problem consisting only of linear constraints derived from
Horn clauses gives the optimal solution to the IP problem.
%
Even IP models that are not fully composed of Horn constraints (as is
the case for Gebotys' model) become generally easier to solve,
although they must still resort to branch-and-bound in the general
case.

As Wilson's model, Gebotys' model is based on a DG representation with
processor-independent \emph{operations} and \emph{edges}.
%
The model contains two main types of 0-1 variables:
%
\begin{inparaenum}[]
\item \emph{pattern covering variables} \ipvar{c}{o,p} indicate
  whether pattern $p$ covers operation $o$, and
\item \emph{compaction variables} \ipvar{m}{o} indicate whether
  operation $o$ is to be compacted with its successor $o'$ in the
  input instruction sequence, due to the same pattern covering both
  $o$ and $o'$.
\end{inparaenum}
%
Instead of defining register assignment variables as in the case of
Wilson~\etal{}, Gebotys' model includes patterns for each different
flow that a data edge could follow through registers and memory.
%
Thus, selecting a pattern covering implicitly decides the register
assignment and possible spilling of the covered edges.
%
This representation is based on the assumption that the target
processor has a very small register file, as otherwise the number of
patterns would explode.
%
The model include non-Horn constraints to enforce that pattern
coverings do not overlap, and Horn constraints to enforce that
%
\begin{inparaenum}[]
\item coverings are selected that assign interfering edges to
  different registers, and
\item operations are compacted whenever their edge assignments are
  compatible.
\end{inparaenum}
%
The objective function is a weighted sum of three different costs:
makespan, code size, and energy consumption (approximated as the
number of memory accesses of the generated code).

Gebotys presents experimental results for six single-block signal
processing examples and TI's TMS320C2x -- a simple, single-issue DSP
with very few registers.
%
In the experiments, the objective function is limited to minimizing
the makespan, which in the case of TMS320C2x is directly proportional
to code size.
%
The results show a makespan improvement from $9\%$ of up to $118\%$
relative to the code generated by TI's C compiler.
%
Interestingly, the six basic blocks can be solved to optimality from the
first linear relaxation, without resorting to branch-and-bound search.
%
Gebotys also experiments with extending the model with complete
instruction scheduling by adding a time dimension to the pattern
selection variables, and observes a dramatic increase of the solving
time due to an explosion of variables in the model and the
insufficiency of the initial linear relaxations to deliver the optimal
solution.
%
Since TMS320C2x is a single-issue processor, the extended model does
not yield better solutions to any of the six single-block signal
processing examples.

\paragraph{ICG.}

Bashford and Leupers propose in 1999 \emph{ICG}, a code generator that
integrates instruction selection, register allocation and instruction
scheduling using an approach that is partially based on
CP~\cite{Bashford1999}.
%
As is common to all fully-integrated approaches, programs in ICG are
represented by a DG with abstract operations.
%
Unlike the other approaches, ICG decomposes the solving process into
several stages, sacrificing global optimality in favor of solving
speed.
%
In Bashford and Leupers's paper, ICG is described as a procedural code
generator with limited search capabilities.
%
However, the model is presented in this survey as a monolithic CP
model for clarity and consistency.

The ICG model comprises the following variable types:
%
\begin{inparaenum}[]
\item \emph{register variables} \ipvar{r}{o, op} give the register to
  which each use and definition operand $op$ of operation $o$ is
  assigned,
\item \emph{bundle type variables} \ipvar{t}{o} give the type of
  bundle to which operation $o$ belongs,
\item \emph{functional unit variables} \ipvar{f}{o} give the
  functional unit used by operation $o$, and
\item \emph{operation cost variables} \ipvar{c}{o} give the number of
  issue cycles required to execute operation $o$.
\end{inparaenum}
%
The register assignment variables include a special register to
represent each memory bank.
%
Pattern coverings are not represented explicitly with variables but
derived from the remaining decisions.
%
Possible coverings of more than one operation by a pattern $p$ are
represented by special registers assigned to the definition operands
covered by $p$.
%
The model lacks scheduling variables as instruction scheduling is
carried out in a procedural fashion~\cite[Section 7]{Bashford1999}.
%
The model contains constraints to ensure that:
\begin{inparaenum}[]
\item the registers assigned to operands of different operations are
  compatible;
\item operations can only be bundled together if they have the same
  bundle type and do not use the same functional unit; and
\item specific instruction constraints relating register assignments,
  bundle types, functional units and costs within an operation are
  satisfied.
\end{inparaenum}
%
The remaining constraints necessary for correct code generation such
as precedences among operations or non-interference among temporaries
are handled by procedural algorithms with a limited form of search.

The solving procedure is split into three steps:
\begin{inparaenum}[]
\item first, a constraint problem is formulated and initial
  propagation is performed to discard invalid registers for operands;
\item then, a procedural, iterative algorithm is run where operations
  are scheduled and spill code is generated. The latter is performed
  \emph{on-demand} by extending the problem with new variables and
  constraints corresponding to load, store, and register-to-register
  instructions. A certain level of search is permitted within each
  iteration, and reparation (where the problem is transformed into an
  easier one by means of, for example, spilling) is used as a last
  resort to handle search failures. The (implicit) goals are to
  minimize makespan and spill code.
\item Finally, search is applied to assign values to all variables
  that have not been decided yet.
\end{inparaenum}
%
A post-processing step is run to handle memory address computations.

Bashford and Leupers evaluate ICG on four basic blocks of the DSPstone
benchmark suite for the ADSP-210x processor.
%
The results show that the generated code is as good in terms of
makespan as hand-optimized code, and noticeably better than traditionally
generated code.
%
However, the scalability of ICG seems limited as generating code for a
relatively small basic block of 23 operations takes almost seven seconds,
where the immediately smaller basic blocks (17~operations) take less
than two seconds.

\paragraph{OPTIMIST.}

The most recent approach to fully integrated code generation is called
\emph{OPTIMIST}~\cite{Eriksson2012}.
%
This project has explored the application of several search techniques
for local code generation, including dynamic
programming~\cite{Kessler2001,Kessler2006} and genetic
algorithms~\cite{Eriksson2008}.
%
However, IP has established itself as the technique of choice within
OPTIMIST as a natural yet formal method to extend the code generation
model to more complex processors~\cite{Eriksson2008} and software
pipelining~\cite{Eriksson2009,Eriksson2012}.

%
Compared to previous integrated approaches, the OPTIMIST IP model has
a rich resource model in which, similarly to the early approach of
Ertl and Krall presented in
Section~\ref{sec:local-instruction-scheduling}, the resource usage of
an instruction is specified per pipeline stage.
%
Another distinctive feature is that copies between different register
banks and memory are only modeled implicitly by means of variables
indicating their movement, rather than inserted in the input program
in a preprocessing stage and defined as optional but otherwise regular
operations.
%
Similarly to UNISON (see
Section~\ref{sec:register-allocation-and-instruction-scheduling}),
memory is modeled as a register bank and thus spilling is unified with
handling multiple register banks.
%
The model captures thus register allocation but leaves out register
assignment, which precludes coalescing and register packing.

OPTIMIST's IP model is described first for local integrated code
generation and extended later for software pipelining.
%
The model (slightly simplified for clarity) includes the following
types of 0-1 variables:
%
\begin{inparaenum}[]
\item \emph{pattern selection variables} \ipvar{s}{p,k} indicate
  whether pattern $p$ is selected and issued in cycle $k$,
\item \emph{operation and edge covering variables} \ipvar{c}{p,o,k}
  and \ipvar{c}{p,e,k} indicate whether pattern $p$ covers operation
  $o$ and edge $e$ in cycle $k$,
\item \emph{copy variables} \ipvar{x}{t,s,d,k} indicate whether
  temporary $t$ is copied from source register bank $s$ to destination
  register bank $d$ in cycle $k$, and
\item \emph{register allocation variables} \ipvar{a}{t,b,k} indicate
  whether temporary $t$ is allocated to register bank $b$ in cycle
  $k$.
\end{inparaenum}
%
The model's instruction selection constraints ensure that
%
\begin{inparaenum}[]
\item all operations are covered by exactly one pattern.
\end{inparaenum}
%
The register allocation constraints ensure that the program
temporaries:
%
\begin{inparaenum}[]
\item are assigned to the register banks supported by their definer
  and user instructions in their definition and use cycles;
\item can only be allocated to a register bank $b$ in a cycle $k$ if
  they are defined in cycle $k$, are already allocated to $b$ in cycle
  $k - 1$, or are copied from another register bank in cycle $k$;
\item are not allocated to any register bank if they correspond to
  internalized edges; and
\item do not exceed the capacity of register banks in any cycle.
\end{inparaenum}
%
These register allocation constrains are closely related to earlier IP
models discussed in this survey.
%
The first and second constraints are similar to those of Nagarakatte
and Govindarajan (see
Section~\ref{sec:register-allocation-and-instruction-scheduling}); the
third constraint is similar to the second constraint in
Wilson~\etal{}'s model described above.
%
In both cases, the constraints are lifted from individual registers to
register banks.
%
Last, the model's instruction scheduling constraints ensure that:
%
\begin{inparaenum}[]
\item temporaries can only be used and copies after their definition
  cycle; and
\item resources such as functional units are not overused and the
  bundle width is not exceeded in any cycle.
\end{inparaenum}
%
The objective function, as is common to many local integrated
approaches, minimizes the basic block's makespan.

The model extension to single-block software pipelining preserves the
same variables and introduces only a few changes in the model
constraints.
%
The changes handle two fundamental characteristics of software
pipelining: the introduction of cyclic dependencies across loop
iterations, and the fact that resource usage by an instruction and
temporary live ranges might overlap over time across different
iterations.
%
As is common in combinatorial software pipelining, the initiation
interval is a fixed parameter and the IP problem is generated and
solved for different values until the optimal solution (that which
minimizes the initiation interval) is found.

Eriksson~\etal{} present experimental results for both the local and
the software pipelining IP approaches.
%
The original experimental results are presented in two
publications~\cite{Eriksson2008,Eriksson2012}.
%
This survey presents updated results from a rerun reported in
Eriksson's doctoral dissertation~\cite{Eriksson2011} where a newer IP
solver and host architecture are used.
%
The local IP approach is compared to a heuristic code generator based
on genetic algorithms (GAs).
%
The input basic blocks are extracted from the \emph{jpeg} and
\emph{mpeg2} benchmarks in MediaBench, and the targeted processor is a
slightly modified version of TI's C62x.
%
The code generated by the IP approach is better than that generated by
the heuristic in around $50\%$ of the cases, where the makespan is
improved by around 8 cycles in average and up to 100 cycles in the
largest basic block.
%
The largest basic block solved by the IP approach has 191 operations.
%
In the original experiment results published three years before, the
largest basic block solved by the IP approach within the same time
limit has 52 operations, and only $40\%$ of the basic blocks up to 191
operations can be solved~\cite[Section 4.2]{Eriksson2008}.
%
This difference illustrates the speed with which solvers and
architectures evolve to enable solving increasingly harder
combinatorial problems.

The fully-integrated software pipelining IP approach is evaluated by
comparing it to a separated approach (where instruction selection and
register bank allocation are solved first and the remaining tasks are
solved later).
%
The experiments are run for the same processor as the local approach
and loop kernels from the SPEC2000, SPEC2006, MediaBench, and Ffmpeg
benchmark suites.
%
The results show that the initiation interval of the kernels improved
by the integrated approach (which are $39\%$ of the total) is improved
by $20\%$ in average~\cite[Chapter 8]{Eriksson2011}.
%
The approach scales up to loop kernels of approximately 100
operations~\cite[Chapter 4]{Eriksson2011}, 40 operations larger
compared to the original experimental results obtained two years
before~\cite{Eriksson2012}.

\section{Conclusion}\label{sec:conclusion}

\todo{table with summary of benchmarks used in all approaches}

\todo{table with summary of combinatorial optimization systems used in
  all approaches}

This paper has surveyed the existing body of literature on
combinatorial register allocation and instruction scheduling, two
central compiler back-end problems.

Significant progress has been made for each of the problems in
isolation since the application of combinatorial optimization was
proposed in the 1980s.
%
Today, the vast majority of register allocation or instruction
scheduling problems found in practice can be solved to optimality in
the order of seconds.
%
Yet, combinatorial optimization is hardly applied in modern compilers.
%
This is most likely due to the fact that the performance improvements
yielded by combinatorial register allocation or instruction scheduling
in isolation are not dramatic enough to motivate a paradigm shift in
code generation.
%
Circumstantial factors such as licensing mismatches, software
integration obstacles, and even cultural differences are also likely
to play a part in this lack of adoption.

Integrated code generation has the potential to bring the kind of
improvements in code quality that would motivate a paradigm shift, but
further research is required in two directions:
\begin{inparaitem}[]
\item devising combinatorial models that capture all relevant code
  generation subproblems to deliver the highest code quality, and
\item developing solving methods that make it scale to the point where
  most practical problems can be solved in reasonable time.
\end{inparaitem}

\subsection*{Acknowledgments}

This research has been partially funded by LM Ericsson AB and the
Swedish Research Council (VR~621-2011-6229).
%
The authors are grateful for helpful comments from Sven Mallach,
Mattias Eriksson, Mats Carlsson, Bernhard Scholz, and Lang Hames.

\appendix

\bibliographystyle{plain}
\bibliography{paper}

\end{document}

paper.bbl
\begin{thebibliography}{10}

\bibitem{Aggoun1993}
Abderrahmane Aggoun and Nicolas Beldiceanu.
\newblock Extending {CHIP} in order to solve complex scheduling and placement
  problems.
\newblock {\em Mathematical and Computer Modelling}, 17(7):57--73, 1993.

\bibitem{Ahuja1993}
Ravindra~K. Ahuja, Thomas~L. Magnanti, and James~B. Orlin.
\newblock {\em Network Flows: Theory, Algorithms, and Applications}.
\newblock 1993.

\bibitem{Allan1995}
Vicki~H. Allan, Reese~B. Jones, Randall~M. Lee, and Stephen~J. Allan.
\newblock Software pipelining.
\newblock {\em ACM Comput. Surv.}, 27(3):367--432, September 1995.

\bibitem{Altman1995}
Erik~R. Altman, R.~Govindarajan, and Guang~R. Gao.
\newblock Scheduling and mapping: Software pipelining in the presence of
  structural hazards.
\newblock In {\em PLDI}, pages 139--150, 1995.

\bibitem{Appel2001}
Andrew~W. Appel and Lal George.
\newblock Optimal spilling for {CISC} machines with few registers.
\newblock {\em SIGPLAN Not.}, 36:243--253, May 2001.

\bibitem{Arya1985}
S.~Arya.
\newblock An optimal instruction-scheduling model for a class of vector
  processors.
\newblock {\em IEEE Transactions on Computers}, C-34(11):981--995, Nov 1985.

\bibitem{Baptiste2001}
Philippe Baptiste, Claude~Le Pape, and Wim Nuijten.
\newblock {\em Constraint-Based Scheduling}.
\newblock 2001.

\bibitem{Bashford1999}
Steven Bashford and Rainer Leupers.
\newblock Phase-coupled mapping of data flow graphs to irregular data paths.
\newblock {\em Design Automation for Embedded Systems}, pages 119--165, March
  1999.

\bibitem{Briggs1994}
Preston Briggs, Keith~D. Cooper, and Linda Torczon.
\newblock Improvements to graph coloring register allocation.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  16:428--455, 1994.

\bibitem{Castaneda2012}
Roberto Casta\~{n}eda Lozano, Mats Carlsson, Frej Drejhammar, and Christian
  Schulte.
\newblock Constraint-based register allocation and instruction scheduling.
\newblock In {\em CP}, volume 7514, pages 750--766, 2012.

\bibitem{Castaneda2014}
Roberto Casta\~{n}eda Lozano, Mats Carlsson, Gabriel Hjort~Blindell, and
  Christian Schulte.
\newblock Combinatorial spill code optimization and ultimate coalescing.
\newblock In {\em LCTES}, pages 23--32, 2014.

\bibitem{Chaitin1981}
Gregory~J. Chaitin, Marc~A. Auslander, Ashok~K. Chandra, John Cocke, Martin~E.
  Hopkins, and Peter~W. Markstein.
\newblock Register allocation via coloring.
\newblock {\em Computer Languages}, 6(1):47--57, 1981.

\bibitem{Chang1997}
Chia-Ming Chang, Chien-Ming Chen, and Chung-Ta King.
\newblock Using integer linear programming for instruction scheduling and
  register allocation in multi-issue processors.
\newblock {\em Computers Math. Applic.}, 34:1--14, November 1997.

\bibitem{Chu2012}
Geoffrey Chu and Peter~J. Stuckey.
\newblock A generic method for identifying and exploiting dominance relations.
\newblock In {\em CP}, volume 7514, pages 6--22, 2012.

\bibitem{Colombet2011}
Quentin Colombet, Florian Brandner, and Alain Darte.
\newblock Studying optimal spilling in the light of ssa.
\newblock In {\em CASES}, pages 25--34, 2011.

\bibitem{Cormen2009}
Thomas~H. Cormen, Charles~E. Leiserson, Ronald~L. Rivest, and Clifford Stein.
\newblock {\em Introduction to Algorithms, Third Edition}.
\newblock MIT, 2009.

\bibitem{Cytron1991}
Ron Cytron, Jeanne Ferrante, Barry~K. Rosen, Mark~N. Wegman, and F.~Kenneth
  Zadeck.
\newblock Efficiently computing static single assignment form and the control
  dependence graph.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  13(4):451--490, October 1991.

\bibitem{Ebner2009}
Dietmar Ebner, Bernhard Scholz, and Andreas Krall.
\newblock Progressive spill code placement.
\newblock In {\em CASES '09}, pages 77--86, 2009.

\bibitem{Eriksson2011}
Mattias Eriksson.
\newblock {\em Integrated Code Generation}.
\newblock PhD thesis, Link\"{o}ping University, Sweden, 2011.

\bibitem{Eriksson2009}
Mattias Eriksson and Christoph Kessler.
\newblock Integrated modulo scheduling for clustered {VLIW} architectures.
\newblock In {\em HiPEAC}, pages 65--79, 2009.

\bibitem{Eriksson2012}
Mattias Eriksson and Christoph Kessler.
\newblock Integrated code generation for loops.
\newblock {\em ACM Trans. Embed. Comput. Syst.}, 11S(1):19:1--19:24, June 2012.

\bibitem{Eriksson2008}
Mattias Eriksson, Oskar Skoog, and Christoph Kessler.
\newblock Optimal vs. heuristic integrated code generation for clustered {VLIW}
  architectures.
\newblock In {\em SCOPES}, pages 11--20, 2008.

\bibitem{Ertl1991}
M.~Ertl and Andreas Krall.
\newblock Optimal instruction scheduling using constraint logic programming.
\newblock In {\em Programming Language Implementation and Logic Programming},
  volume 528, pages 75--86, 1991.

\bibitem{Fisher1981}
J.~A. Fisher.
\newblock Trace scheduling: A technique for global microcode compaction.
\newblock {\em IEEE Trans. Comput.}, 30(7):478--490, July 1981.

\bibitem{Fisher1983}
J.~A. Fisher.
\newblock Very long instruction word architectures and the {ELI}-512.
\newblock In {\em ISCA}, pages 140--150, 1983.

\bibitem{Freuder1994}
Eugene~C. Freuder.
\newblock Exploiting structure in constraint satisfaction problems.
\newblock In {\em CP}, pages 51--74, 1994.

\bibitem{Fu2002}
Changqing Fu and Kent Wilken.
\newblock A faster optimal register allocator.
\newblock In {\em MICRO-35}, pages 245--256, 2002.

\bibitem{Gebotys1997}
Catherine~H. Gebotys.
\newblock An efficient model for {DSP} code generation: Performance, code size,
  estimated energy.
\newblock In {\em ISSS}, pages 41--47, 1997.

\bibitem{Gebotys1991}
Catherine~H. Gebotys and Mohamed~I. Elmasry.
\newblock Simultaneous scheduling and allocation for cost constrained optimal
  architectural synthesis.
\newblock In {\em DAC}, pages 2--7, 1991.

\bibitem{George1996}
Lal George and Andrew~W. Appel.
\newblock Iterated register coalescing.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  18:300--324, 1996.

\bibitem{Gomes1997}
Carla~P. Gomes and Bart Selman.
\newblock Algorithm portfolio design: Theory vs. practice.
\newblock In {\em UAI}, pages 190--197, 1997.

\bibitem{Goodman1988}
J.~R. Goodman and W.-C. Hsu.
\newblock Code scheduling and register allocation in large basic blocks.
\newblock In {\em ICS'88}, pages 442--452, 1988.

\bibitem{Goodwin1996}
David~W. Goodwin and Kent Wilken.
\newblock Optimal and near-optimal global register allocations using 0-1
  integer programming.
\newblock {\em Software -- Practice and Experience}, 26:929--965, August 1996.

\bibitem{Govindarajan1994}
R.~Govindarajan, Erik~R. Altman, and Guang~R. Gao.
\newblock A framework for resource-constrained rate-optimal software
  pipelining.
\newblock In {\em Parallel Processing: CONPAR 94 — VAPP VI}, volume 854,
  pages 640--651, 1994.

\bibitem{Grund2007}
Daniel Grund and Sebastian Hack.
\newblock A fast cutting-plane algorithm for optimal coalescing.
\newblock In {\em CC}, volume 4420, pages 111--125. Springer-Verlag, 2007.

\bibitem{Hack2006}
Sebastian Hack, Daniel Grund, and Gerhard Goos.
\newblock Register allocation for programs in {SSA}-form.
\newblock In {\em CC}, volume 3923, pages 247--262, 2006.

\bibitem{Hames2011}
Lang Hames.
\newblock {\em Specification driven register allocation}.
\newblock PhD thesis, University of Sydney, Australia, 2011.

\bibitem{Hames2006}
Lang Hames and Bernhard Scholz.
\newblock Nearly optimal register allocation with {PBQP}.
\newblock In {\em JMLC'06}, pages 346--361, 2006.

\bibitem{Heffernan2006}
Mark Heffernan and Kent Wilken.
\newblock Data-dependency graph transformations for instruction scheduling.
\newblock {\em Journal of Scheduling}, 8(5):427--451, 2006.

\bibitem{Hennessy2011}
John~L. Hennessy and David~A. Patterson.
\newblock {\em Computer Architecture: A Quantitative Approach}.
\newblock 5th edition, 2011.

\bibitem{Hirnschrott2003}
Ulrich Hirnschrott, Andreas Krall, and Bernhard Scholz.
\newblock Graph coloring vs. optimal register allocation for optimizing
  compilers.
\newblock In {\em JMLC'03}, pages 202--213, 2003.

\bibitem{Horn1951}
Alfred Horn.
\newblock On sentences which are true of direct unions of algebras.
\newblock {\em Journal of Symbolic Logic}, 16(1):14--21, 03 1951.

\bibitem{Hwang1991}
Cheng-Tsung Hwang, J.-H. Lee, and Yu-Chin Hsu.
\newblock A formal approach to the scheduling problem in high level synthesis.
\newblock {\em IEEE Transactions on Computer-Aided Design of Integrated
  Circuits and Systems}, 10(4):464--475, April 1991.

\bibitem{Hwu1993}
Wen-Mei~W. Hwu, Scott~A. Mahlke, William~Y. Chen, Pohua~P. Chang, Nancy~J.
  Warter, Roger~A. Bringmann, Roland~G. Ouellette, Richard~E. Hank, Tokuzo
  Kiyohara, Grant~E. Haab, John~G. Holm, and Daniel~M. Lavery.
\newblock The superblock: an effective technique for {VLIW} and superscalar
  compilation.
\newblock 7(1-2):229--248, May 1993.

\bibitem{x86}
Intel.
\newblock {\em Intel 64 and IA-32 Architectures Software Developer's Manual},
  September 2014.

\bibitem{Jaffar1987}
J.~Jaffar and J.-L. Lassez.
\newblock Constraint logic programming.
\newblock In {\em POPL}, pages 111--119, 1987.

\bibitem{Johnsson1973}
Richard~K. Johnsson.
\newblock A survey of register allocation.
\newblock Technical report, Carnegie Mellon University, United States of
  America, 1973.

\bibitem{PA-RISC}
Gerry Kane.
\newblock {\em PA-RISC 2.0 Architecture}.
\newblock Prentice Hall, 1195.

\bibitem{Kastner2000b}
Daniel K\"{a}stner.
\newblock {\em Retargetable Postpass Optimisation by Integer Linear
  Programming}.
\newblock PhD thesis, Saarland University, Germany, 2000.

\bibitem{Kastner2000}
Daniel K\"{a}stner.
\newblock {PROPAN}: A retargetable system for postpass optimisations and
  analyses.
\newblock In {\em LCTES}, volume 1985, pages 63--80, 2001.

\bibitem{Kastner1999}
Daniel K\"{a}stner and Marc Langenbach.
\newblock Code optimization by integer linear programming.
\newblock In {\em CC}, volume 1575, pages 122--136, 1999.

\bibitem{Kessler2010}
Christoph Kessler.
\newblock Compiling for {VLIW} {DSP}s.
\newblock In {\em Handbook of Signal Processing Systems}, pages 603--638. 2010.

\bibitem{Kessler2001}
Christoph Kessler and Andrzej Bednarski.
\newblock A dynamic programming approach to optimal integrated code generation.
\newblock In {\em LCTES}, pages 165--174, 2001.

\bibitem{Kessler2006}
Christoph Kessler and Andrzej Bednarski.
\newblock Optimal integrated code generation for {VLIW} architectures.
\newblock {\em Concurrency and Computation: Practice and Experience},
  18:1353--1390, 2006.

\bibitem{Koes2005}
David Koes and Seth~Copen Goldstein.
\newblock A progressive register allocator for irregular architectures.
\newblock In {\em CGO'05}, pages 269--280, 2005.

\bibitem{Koes2006}
David~Ryan Koes and Seth~Copen Goldstein.
\newblock A global progressive register allocator.
\newblock {\em SIGPLAN Not.}, 41:204--215, June 2006.

\bibitem{Kong1998}
Timothy Kong and Kent Wilken.
\newblock Precise register allocation for irregular architectures.
\newblock In {\em MICRO-31}, pages 297--307, 1998.

\bibitem{Koopmans1957}
Tjalling~C. Koopmans and Martin Beckmann.
\newblock Assignment problems and the location of economic activities.
\newblock {\em Econometrica}, 25(1):53--76, 1957.

\bibitem{Krause2013}
Philipp~Klaus Krause.
\newblock Optimal register allocation in polynomial time.
\newblock In {\em CC}, volume 7791, pages 1--20, 2013.

\bibitem{Kremer1997}
Ulrich Kremer.
\newblock Optimal and near-optimal solutions for hard compilation problems.
\newblock {\em Parallel Processing Letters}, 7(4):371--378, 1997.

\bibitem{Lam1988}
M.~Lam.
\newblock Software pipelining: An effective scheduling technique for {VLIW}
  machines.
\newblock In {\em PLDI}, pages 318--328, 1988.

\bibitem{Lattner2004}
Chris Lattner and Vikram Adve.
\newblock {LLVM}: A compilation framework for lifelong program analysis \&
  transformation.
\newblock In {\em CGO}, pages 75--88, 2004.

\bibitem{Leupers1997}
Rainer Leupers and Peter Marwedel.
\newblock Time-constrained code compaction for {DSP}'s.
\newblock {\em Transactions on Very Large Scale Integration Systems},
  5:112--122, March 1997.

\bibitem{Malik2008b}
Abid~M. Malik, Michael Chase, Tyrel Russell, and Peter Van~Beek.
\newblock An application of constraint programming to superblock instruction
  scheduling.
\newblock In {\em CP}, volume 5202, pages 97--111, 2008.

\bibitem{Malik2008}
Abid~M. Malik, Jim McInnes, and Peter~Van Beek.
\newblock Optimal basic block instruction scheduling for multiple-issue
  processors using constraint programming.
\newblock {\em International Journal on Artificial Intelligence Tools},
  17(1):37--54, 2008.

\bibitem{Nagarakatte2007}
Santosh~G. Nagarakatte and R.~Govindarajan.
\newblock Register allocation and optimal spill code scheduling in software
  pipelined loops using 0-1 integer linear programming formulation.
\newblock In {\em CC}, volume 4420, pages 126--140, 2007.

\bibitem{Nandivada2007}
V.~Nandivada, Fernando Pereira, and Jens Palsberg.
\newblock A framework for end-to-end verification and evaluation of register
  allocators.
\newblock In {\em Static Analysis}, volume 4634, pages 153--169, 2007.

\bibitem{Nemhauser1999}
G.~L. Nemhauser and L.~A. Wolsey.
\newblock {\em Integer and Combinatorial Optimization}.
\newblock 1999.

\bibitem{PereiraArticle2008}
Fernando Pereira and Jens Palsberg.
\newblock Register allocation by puzzle solving.
\newblock {\em SIGPLAN Not.}, 43:216--226, June 2008.

\bibitem{PereiraSurvey2008}
Fernando Magno~Quint{\~a}o Pereira.
\newblock A survey on register allocation.
\newblock Technical report, University of California, United States of America,
  2008.

\bibitem{Pereira2008}
Fernando Magno~Quint{\~a}o Pereira and Jens Palsberg.
\newblock Register allocation by puzzle solving.
\newblock pages 216--226, 2008.

\bibitem{Poletto1999}
Massimiliano Poletto and Vivek Sarkar.
\newblock Linear scan register allocation.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  21:895--913, 1999.

\bibitem{Protzenko2009}
Jonathan Protzenko.
\newblock A survey of register allocation techniques.
\newblock Technical report, \'{E}cole Polytechnique, France, 2009.

\bibitem{Rajlich1984}
Vaclav Rajlich and M.~Drew Moshier.
\newblock A survey of algorithms for register allocation in straight-line
  programs.
\newblock Technical report, University of Michigan, United States of America,
  1984.

\bibitem{Rau1981}
B.~R. Rau and C.~D. Glaeser.
\newblock Some scheduling techniques and an easily schedulable horizontal
  architecture for high performance scientific computing.
\newblock {\em SIGMICRO Newsl.}, 12(4):183--198, December 1981.

\bibitem{Rau1993}
B.~Ramakrishna Rau and J.~A. Fisher.
\newblock Instruction-level parallel processing: history, overview, and
  perspective.
\newblock 7:9--50, May 1993.

\bibitem{Colin2010}
Colin~R. Reeves.
\newblock Genetic algorithms.
\newblock In {\em Handbook of Metaheuristics}, pages 109--139. 2010.

\bibitem{Refalo2004}
Philippe Refalo.
\newblock Impact-based search strategies for constraint programming.
\newblock In {\em CP}, volume 3258, pages 557--571, 2004.

\bibitem{Regin1994}
Jean-Charles R{\'e}gin.
\newblock A filtering algorithm for constraints of difference in {CSP}s.
\newblock In {\em AAAI}, pages 362--367, 1994.

\bibitem{Regin1996}
Jean-Charles R{\'e}gin.
\newblock Generalized arc consistency for global cardinality constraint.
\newblock In {\em AAAI}, pages 209--215, 1996.

\bibitem{Rong2007}
Hongbo Rong and R.~Govindarajan.
\newblock Advances in software pipelining.
\newblock In {\em The Compiler Design Handbook}, pages 662--734. CRC, 2nd
  edition, 2007.

\bibitem{Rossi2006}
Francesca Rossi, Peter~Van Beek, and Toby Walsh.
\newblock {\em Handbook of Constraint Programming}.
\newblock 2006.

\bibitem{Scholz2002}
Bernhard Scholz and Erik Eckstein.
\newblock Register allocation for irregular architectures.
\newblock {\em SIGPLAN Not.}, 37:139--148, June 2002.

\bibitem{Shobaki2004}
Ghassan Shobaki and Kent Wilken.
\newblock Optimal superblock scheduling using enumeration.
\newblock In {\em MICRO-37}, pages 283--293, 2004.

\bibitem{Shobaki2009}
Ghassan Shobaki, Kent Wilken, and Mark Heffernan.
\newblock Optimal trace scheduling using enumeration.
\newblock 5:19:1--19:32, March 2009.

\bibitem{Thorup1998}
Mikkel Thorup.
\newblock All structured programs have small tree width and good register
  allocation.
\newblock {\em Inf. Comput.}, 142(2):159--181, May 1998.

\bibitem{VanBeek2001}
Peter Van~Beek and Kent Wilken.
\newblock Fast optimal instruction scheduling for single-issue processors with
  arbitrary latencies.
\newblock In {\em CP}, volume 2239, pages 625--639, 2001.

\bibitem{Wilken2000}
Kent Wilken, Jack Liu, and Mark Heffernan.
\newblock Optimal instruction scheduling using integer programming.
\newblock {\em SIGPLAN Not.}, 35:121--133, May 2000.

\bibitem{Wilson1994}
Tom Wilson, Gary Grewal, Ben Halley, and Dilip Banerji.
\newblock An integrated approach to retargetable code generation.
\newblock In {\em ISSS}, pages 70--75, 1994.

\bibitem{Wilson2002}
Tom Wilson, Gary Grewal, Shawn Henshall, and Dilip Banerji.
\newblock An {ILP}-based approach to code generation.
\newblock In {\em Code Generation for Embedded Processors}, pages 103--118.
  2002.

\bibitem{Winkel2004}
Sebastian Winkel.
\newblock Exploring the performance potential of {I}tanium processors with
  {ILP}-based scheduling.
\newblock In {\em CGO'04}, pages 189--200, 2004.

\bibitem{Winkel2004b}
Sebastian Winkel.
\newblock {\em Optimal global instruction scheduling for the {Itanium}
  processor architecture}.
\newblock PhD thesis, Saarland University, Germany, 2004.

\bibitem{Winkel2007}
Sebastian Winkel.
\newblock Optimal versus heuristic global code scheduling.
\newblock In {\em MICRO-40}, pages 43--55, 2007.

\bibitem{Zhang1996}
Li~Zhang.
\newblock {\em Scheduling and Allocation with Integer Linear Programming}.
\newblock PhD thesis, Saarland University, Germany, 1996.

\end{thebibliography}
