\section{Types of dependencies}

A dependency, in the most general sense, can be seen as an interaction between
two instructions stemming from shared data. This definition is willingly broad
as, depending on the circumstances, the CPU implementation, \ldots{}, some
categories of dependencies must be taken into account, while some may be
ignored.

\paragraph{Read-write categories.} The first distinction that can be made
between dependencies, and the one that is most often made, is whether the data
through which the dependency is created is read or written. They can be broken
down into four categories:

\begin{itemize}
    \item read-after-write (RaW);
    \item write-after-write (WaW);
    \item write-after-read (WaR);
    \item read-after-read (RaR).
\end{itemize}

For instance, in the kernel presented in the introduction of this chapter, the
first instruction (\lstxasm{add \%rax, \%rbx}) reads its first operand, the
register \reg{rax}, and both reads and writes its second operand \reg{rbx}. The
second \lstxasm{add} has the same behaviour. Thus, as \reg{rbx} is written at
line 1, and read at line 2, there is a read-after-write dependency between the
two.

Most of the time, \emph{dependency} is actually used to mean
\emph{read-after-write dependency}, sometimes called ``flow dependency''.
However, depending on the actual hardware implementation of the architecture,
other kinds of dependencies might induce a latency. While a read-after-read
dependency will not induce a latency in the vast majority of architectures, a
write-after-read could prevent instructions to be re-ordered in a way that the
writing instruction commits its result before the reading instruction uses the
previously stored value. In most modern CPUs, the processor actually has more
physical registers than what is exposed to the user through the ISA; a renaming
phrase will allocate those registers to avoid the effects of WaR and WaW
dependencies as much as possible.

\smallskip{}

For the present chapter, \textit{we only consider read-after-write
dependencies}; however, all the techniques we present are applicable to other
types of dependencies if the considered architecture requires to take them into
account.

\paragraph{Dependency medium.} In the example above, we only introduced
dependencies induced through registers, or \emph{register-carried}. There are,
however, other channels.

\smallskip{}

As we saw in the introduction to this chapter, as well as in the previous
chapter, dependencies can also be \emph{memory-carried}, in more or less
straightforward ways, such as in the examples from
\autoref{lst:mem_carried_exn}, where the last line always depends on the first.

\begin{lstfloat}[h!]
\begin{minipage}[t]{0.32\linewidth}
    \begin{lstlisting}[language={[x86masm]Assembler}]
add %rax, (%rbx)
add (%rbx), %rcx\end{lstlisting}
\end{minipage}\hfill
\begin{minipage}[t]{0.32\linewidth}
    \begin{lstlisting}[language={[x86masm]Assembler}]
add %rax, (%rbx)
add $8, %rbx
add -8(%rbx), %rcx\end{lstlisting}
\end{minipage}\hfill
\begin{minipage}[t]{0.32\linewidth}
    \begin{lstlisting}[language={[x86masm]Assembler}]
add %rax, (%rbx)
lea 16(%rbx), %r10
add -16(%r10), %rcx\end{lstlisting}
\end{minipage}\hfill
\caption{Examples of memory-carried dependencies.}\label{lst:mem_carried_exn}
\end{lstfloat}

\smallskip{}

Some dependencies are also \emph{flag-carried}. These are very akin to
register-carried dependency, but are not directly visible in the instruction.
For instance, a subtract operation may set flags indicating whether the result
is zero, and a subsequent jump may use this flag to chose whether the branch is
taken or not.

\smallskip{}

Depending on the architecture, other channels may still exist.

\medskip{}

In this chapter, we focus on register-carried and memory-carried dependencies,
with a large emphasis on memory-carried dependencies.

\paragraph{Presence of loops.} The previous examples were all pieces of
\emph{straight-line code} in which a dependency arose. However, many
dependencies are actually \emph{loop-carried}, such as those in
\autoref{lst:loop_carried_exn}. In \autoref{lst:loop_carried_exn:sumA}, line 2
depends on the previous iteration's line 2 as \reg{r10} is read, then written
back. In \autoref{lst:loop_carried_exn:quasiFibo}, line 3 depends on line 2 of
the same iteration; but line 2 alsp depends on line 3 two iterations ago by
reading \lstxasm{-16(\%rbx, \%r10)}.

\begin{lstfloat}
    \centering

    \begin{sublstfloat}[b]{0.48\linewidth}
        \begin{lstlisting}[language={[x86masm]Assembler}]
loop:
    add (%rax), %r10
    add $8, %rax
    jmp loop
\end{lstlisting}
\caption{Compute the sum of array \lstxasm{A}'s terms in \reg{r10}. \reg{rax} points to
        \lstxasm{A}.}\label{lst:loop_carried_exn:sumA}
    \end{sublstfloat}
    \hfill
    \begin{sublstfloat}[b]{0.48\linewidth}
        \begin{lstlisting}[language={[x86masm]Assembler}]
loop:
    mov -16(%rbx, %r10), (%rbx, %r10)
    add (%rax, %r10), (%rbx, %r10)
    add $8, %r10
    jmp loop
\end{lstlisting}
        \caption{Compute \lstxasm{B[i] = A[i] + B[i-2]}. \reg{rax} points to
        \lstxasm{A}, \reg{rbx} points to \lstxasm{B}.}\label{lst:loop_carried_exn:quasiFibo}
    \end{sublstfloat}
    \caption{Examples of loop-carried dependencies.}\label{lst:loop_carried_exn}
\end{lstfloat}
