\HeadingLevelB{Out-of-Order and Speculative Execution}
\label{sec:out_of_order}

% Outcome: distinguish observed execution order from program order

CPU cores can execute instructions orders of magnitude faster than DRAM can
read data. Computer architects attempt to bridge this gap by using
hyper-threading (\S~\ref{sec:cpu_die}), out-of-order and speculative execution,
and caching, which is described in \S~\ref{sec:caching}. In CPUs that use
out-of-order execution, the order in which the CPU carries out a program's
instructions (\textit{execution order}) is not necessarily the same as the
order in which the instructions would be executed by a sequential evaluation
system (\textit{program order}).

An analysis of a system's information leakage must take out-of-order execution
into consideration. Any CPU actions observed by an attacker match the execution
order, so the attacker may learn some information by comparing the observed
execution order with a known program order. At the same time, attacks that try
to infer a victim's program order based on actions taken by the CPU must
account for out-of-order execution as a source of noise.

This section summarizes the out-of-order and speculative execution concepts
used when reasoning about a system's security properties.
\citep{patterson2013architecture} and \citep{hennessy2012architecture} cover the
concepts in great depth, while Intel's optimization manual
\citep{intel2014optimization} provides details specific to Intel CPUs.

% The Haswell Microarchitecture: Optimization S 2.1

Figure~\ref{fig:cpu_out_of_order} provides a more detailed view of the CPU core
components involved in out-of-order execution, and omits some less relevant
details from Figure~\ref{fig:cpu_core}.

\begin{figure}[htpb]
  \centering
  \includegraphics[width=87mm]{figures/cpu_out_of_order.pdf}
  \caption{
    The structures in a CPU core that are relevant to out-of-order and
    speculative execution. Instructions are decoded into micro-ops, which are
    scheduled on one of the execution unit's ports. The branch predictor
    enables speculative execution when a branch is encountered.
  }
  \label{fig:cpu_out_of_order}
\end{figure}

% Intel Microarchitecture Code Name Sandy Bridge Pipeline Overview:
%     Optimization S 2.2.1
% The Front End: Optimization S 2.2.2

The Intel architecture defines a \textit{complex instruction set} (CISC).
However, virtually all modern CPUs are architected following \textit{reduced
instruction set} (RISC) principles. This is accomplished by having the
instruction decode stages break down each instruction into \textit{micro-ops},
which resemble RISC instructions. The other stages of the execution pipeline
work exclusively with micro-ops.


\HeadingLevelC{Out-of-Order Execution}
\label{sec:execution_units}

% Out of Order Engine: Optimization S 2.2.23
% The Execution Core: S 2.2.4

Different types of instructions require different logic circuits, called
\textit{functional units}. For example, the arithmetic logic unit (ALU), which
performs arithmetic operations, is completely different from the load and store
unit, which performs memory operations. Different circuits can be used at the
same time, so each CPU core can execute multiple micro-ops in parallel.

The core's out-of-order engine receives decoded micro-ops, identifies the
micro-ops that can execute in parallel, assigns them to functional units, and
combines the outputs of the units so that the results are equivalent to having
the micro-ops executed sequentially in the order in which they come from the
decode stages.

For example, consider the sequence of pseudo micro-ops\footnote{The set of
micro-ops used by Intel CPUs is not publicly documented. The fictional examples
in this section suffice for illustration purposes.} in
Table~\ref{fig:out_of_order_micro_ops} below. The \texttt{OR} uses the result
of the \texttt{LOAD}, but the \texttt{ADD} does not. Therefore, a good
scheduler can have the load store unit execute the \texttt{LOAD} and the ALU
execute the \texttt{ADD}, all in the same clock cycle.

\begin{table}[hbt]
  \centering
  \caption{
    Pseudo micro-ops for the out-of-order execution example.
  }
  \label{fig:out_of_order_micro_ops}
  \begin{tabular}{| l | l | l |}
  \hline
  \textbf{\#} & \textbf{Micro-op} & \textbf{Meaning}\\
  \hline
  1 & \texttt{LOAD RAX, RSI} & RAX $\leftarrow$ DRAM[RSI]\\
  \hline
  2 & \texttt{OR RDI, RDI, RAX} & RDI $\leftarrow$ RDI $\lor$ RAX\\
  \hline
  3 & \texttt{ADD RSI, RSI, RCX} & RSI $\leftarrow$ RSI + RCX\\
  \hline
  4 & \texttt{SUB RBX, RSI, RDX} & RBX $\leftarrow$ RSI - RDX\\
  \hline
  \end{tabular}
\end{table}

% Renamer: Optimization S 2.2.3.1

The out-of-order engine in recent Intel CPUs works roughly as follows.
Micro-ops received from the decode queue are written into a \textit{reorder
buffer} (ROB) while they are \textit{in-flight} in the execution unit. The
\textit{register allocation table} (RAT) matches each register with the last
reorder buffer entry that updates it. The \textit{renamer} uses the RAT to
rewrite the source and destination fields of micro-ops when they are written in
the ROB, as illustrated in Tables \ref{fig:out_of_order_rob} and
\ref{fig:out_of_order_rat}. Note that the ROB representation makes it easy to
determine the dependencies between micro-ops.

\begin{table}[hbt]
  \centering
  \caption{
    Data written by the renamer into the reorder buffer (ROB), for the
    micro-ops in Table~\ref{fig:out_of_order_micro_ops}.
  }
  \label{fig:out_of_order_rob}
  \begin{tabular}{| l | l | l | l | l |}
  \hline
  \textbf{\#} & \textbf{Op} & \textbf{Source 1} & \textbf{Source 2} &
  \textbf{Destination}\\
  \hline
  1 & LOAD & RSI & $\emptyset$ & RAX \\
  \hline
  2 & OR & RDI & ROB \#1 & RSI \\
  \hline
  3 & ADD & RSI & RCX & RSI \\
  \hline
  4 & SUB & ROB \# 3 & RDX & RBX \\
  \hline
  \end{tabular}
\end{table}

\begin{table}[hbt]
  \centering
  \caption{
    Relevant entries of the register allocation table after the micro-ops in
    Table~\ref{fig:out_of_order_micro_ops} are inserted into the ROB.
  }
  \label{fig:out_of_order_rat}
  \begin{tabular}{| l | r | r | r | r | r | r |}
  \hline
  \textbf{Register} & RAX & RBX & RCX & RDX & RSI & RDI \\
  \hline
  \textbf{ROB \#} & \#1 & \#4 & $\emptyset$ & $\emptyset$ & \#3 & \#2 \\
  \hline
  \end{tabular}
\end{table}

% Scheduler: Optimization S 2.2.3.2

The scheduler decides which micro-ops in the ROB get executed, and places them
in the \textit{reservation station}. The reservation station has one port
for each functional unit that can execute micro-ops independently. Each
reservation station port port holds one micro-op from the ROB. The reservation
station port waits until the micro-op's dependencies are satisfied and forwards
the micro-op to the functional unit. When the functional unit completes
executing the micro-op, its result is \textit{written back} to the ROB, and
forwarded to any other reservation station port that depends on it.

The ROB stores the results of completed micro-ops until they are
\textit{retired}, meaning that the results are \textit{committed} to the
register file and the micro-ops are removed from the ROB. Although micro-ops
can be executed out-of-order, they must be retired in program order, in order
to handle exceptions correctly. When a micro-op causes a hardware exception
(\S~\ref{sec:faults}), all of the following micro-ops in the ROB are
\textit{squashed}, and their results are discarded.

In the example above, the \texttt{ADD} can complete before the \texttt{LOAD},
because it does not require a memory access. However, the \textit{ADD}'s result
cannot be committed before \texttt{LOAD} completes. Otherwise, if the
\textit{ADD} is committed and the \textit{LOAD} causes a page fault, software
will observe an incorrect value for the  RSI register.

% Load and Store Operation Overview: Optimization S 2.2.5

The ROB is tailored for discovering register dependencies between micro-ops.
However, micro-ops that execute out-of-order can also have memory dependencies.
For this reason, out-of-order engines have a \textit{load buffer} and a
\textit{store buffer} that keep track of in-flight memory operations and are
used to resolve memory dependencies.


\HeadingLevelC{Speculative Execution}

% Branch Prediction: Optimization S 2.2.2.3

Branch control flow instructions, also called \textit{branches}, change the instruction
pointer (RIP, \S~\ref{sec:registers}), if a condition is met (\textit{the
branch is taken}). They implement conditional statements (\texttt{if}) and
looping statements (such as \texttt{while} and \texttt{for}). The most
well-known branching instructions in the Intel architecture are in the
\texttt{j\textit{cc}} family, such as \texttt{je} (jump if equal).

Branches pose a challenge to the decode stage, because the instruction that
should be fetched after a branch is not known until the branching condition is
evaluated. In order to avoid stalling the decode stage, modern CPU designs
include \textit{branch predictors} that use historical information to guess
whether a branch will be taken or not.

When the decode stage encounters a branch instruction, it asks the branch
predictor for a guess as to whether the branch will be taken or not. The
decode stage bundles the branch condition and the predictor's guess into a
branch check micro-op, and then continues decoding on the path indicated by the
predictor. The micro-ops following the branch check are marked as
\textit{speculative}.

When the branch check micro-op is executed, the branch unit checks whether the
branch predictor's guess was correct. If that is the case, the branch check is
retired successfully. The scheduler handles \textit{mispredictions} by
squashing all micro-ops following the branch check, and by signaling the
instruction decoder to flush the micro-op decode queue and start fetching the
instructions that follow the correct branch.

% Data Prefetching: Optimization S 2.2.5.4

Modern CPUs also attempt to predict memory read patterns, so they can
\textit{prefetch} the memory locations that are about to be read into the
cache. Prefetching minimizes the latency of successfully predicted read
operations, as their data will already be cached. This is accomplished by
exposing circuits called prefetchers to memory accesses and cache misses. Each
prefetcher can recognize a particular access pattern, such as sequentially
reading an array's elements. When memory accesses match the pattern that a
prefetcher was built to recognize, the prefetcher loads the cache line
corresponding to the next memory access in its pattern.
