Maintaining memory order dependencies through LLVM optimisation passes.

Modern processors have complex memory models that can exhibit unwanted
behaviours if not correctly used. Many modern compilers do not provide
strong guarantees on the execution of programs in certain racy blocks of
code; this creates a set of weak memory behaviours in low level applications,
which can be unexpected, or are poorly modelled. [Batty et al.(2015)].
Some compilers make conservative judgements about the way these memory
models work, and emit machine code which is not as well optimised as it
could be. In the case of LLVM, optimisation passes have been analysed and
tested, but haven't been verified with respect to weak memory behaviours,
and they don't strictly reflect the x86 TSO memory model.

In a system being carefully designed around x86-TSO, such as the "readcopy-update"
primitive in the Linux kernel. The code which implements
this is core to the functionality of Linux and is called very frequently. A
performance boost could be obtained by omitting some of the fences present
in the conservative output of the LLVM C compiler (Clang).

The Linux RCU (read-copy-update) primitive is a mechanism for cheap
locking in the Linux Kernel. It has been implemented by Paul McKenney,
it relies on ordering preserved through dependencies in C code. This is
relies heavily in on the the dependencies preserved by GCC. LLVM does
not preserve these dependencies, and instead Linux kernels compiled under
LLVM have to include a collection of "fences" which are more than likely
slower than preserving dependencies.

By exploring changes to LLVM and it's optimisations I will ensure and
verify the dependency preservation of the compiler, and to be able to implement
a fence-free LLVM compiled Linux RCU primitive.

An ultimate goal of this research would be to be able to implement Linux
RCU without fences and measure the performance increase. I have a few
lines of exploration planned around this research.
There has been some recent work to verify optimisations in LLVM by
[Chakraborty and Vafeiadis(2016)], but they still rely on the insertion of
"fences" into code, rather than relying on the preservation of dependencies
as [McKenney(2016)] suggests. As previously discussed, the removal of
these fences should provide a measurable performance increase to the Linux
Kernel