intro.tex

\chapter{Introduction}\label{sec:intro}

%In diesem Kapitel wird das Problem vorgestellt, das diese Arbeit löst.
%Es sollte verständlich sein (anschauliches Beispiel?).
%Das Problem sollte wichtig sein,
%denn das motiviert weiterzulesen.

%Bestenfalls ist dieses Kapitel auch für Laien verständlich.

When developers craft code, there is a need to convert it from a human-readable high-level language into a machine-understandable language, called assembly.
In order to do this programmers run a \textit{compiler} that checks the code for multiple sources of errors, and, if the code is correct, converts it into an executable file.
While converting the program into machine code the compiler optimizes the code.
This is only beneficial to the developer, as it ensures that his/her application, in the end, runs faster and/or requires fewer system resources.
A simple example of an optimization is constant folding~\cite{aho_2014}, where the compiler analyzes code and precalculates all constant values, instead of letting the operations on them waste valuable runtime to calculate each time the application runs.
An example can be seen below:
Humans immediately see that in~\Cref{fig:intro:cf1} $b$ is always equal to $9$ and using constant folding the compiler will be able to also perform this precomputation.
The result of this can be seen in~\Cref{fig:intro:cf2}.
Therefore, the optimization reduces the runtime of the (admittedly small) program, by virtue of there being one less calculation required.
Simplifying just one expression seems (and for a matter of fact is) quite useless, but in real-world code, an optimization like this can be applied on numerous similar expressions and hence noticeably improve the final product.

\input{fig/constant-folding.tex}

Of course there is a plethora of possibilities to optimize code.
Considering that loops make up approximately 10\% of code of many real-world applications\footnote{Measured using gcc (spec2006): 8.6\% of FIRM nodes are in loops}, they are a natural point to focus optimization efforts upon.
Loops can be unrolled fairly straightforward, if you know how often they are iterated, as is discussed in~\Cref{sec:basics}.

For example,~\Cref{fig:intro:unroll-simple-before} can be easily converted to~\Cref{fig:intro:unroll-simple-after}, while keeping all semantics intact.
In~\Cref{fig:intro:unroll-nostatic-bound} things get trickier, since the (exact) value of $N$ is unknown, simply unrolling a loop by copying its body a fixed number of times does not preserve the original semantics.

In~\Cref{sec:basics} fundamentals for working with these loops are discussed, which are enhanced, juxtaposed and integrated in~\Cref{sec:impl}.
Finally, in~\Cref{sec:eval} we evaluate the approach experimentally to see whether it yields a tangible benefit.

\input{fig/basic-unrolling.tex}

\input{fig/basic-unrolling-non-const.tex}