06-backend.tex

%% We use `subfiles' package
\documentclass[preamble.tex]{subfiles}
\begin{document}

\clearpage

\chapter{Imperative code generation}
\label{ch:Code-Generation}

The previous chapter introduced the process of translating a graph of delayed array combinators to an assembly-like EDSL for expressing array computations.

We first identified a generic loop structure consisting of \[init], \[guard], \[body], \[yield], \[bottom] and \[done] section represented by \*basic blocks* in the \Loop language. A \[nest] basic block was introduces later to support nested loops, needed by segmented combinators. These loop sections ultimately constituted a skeleton which every combinator would populate with relevant \*statements* that would eventually be merged into a single loop.

We then looked at the translation of a number of flat and segmented array combinators into the \Loop language and showed how the partial loops would be merged together into ``runnable'' loops.

While the basic blocks of the loops did contain imperative style statements with some assembly-style labels attached to them, it was never said just what makes a loop ``runnable''.

In this chapter we explore a method by which \Loop language programs can be turned into runnable code. In practice the \Loop language can be interpreted by multiple backends. I present \Loop's translation to one possible backend which is currently available. This backend is targeting (perhaps unimaginatively) \Haskell source language, which means that the code generated is \Haskell.



\clearpage

\section{Approaches to looping}

In the surface \LiveFusion language loops are not explicit. However, most of the array combinators eventually form part of loops expressed in the internal \Loop language. We have discussed this language at length in the previous chapter.

When it comes to expressing loops there is a fundamental difference between the vast majority of general purpose languages (even functional ones) and the purely functional languages like \Haskell. In procedural languages the loop statements are usually built into the language. Further down, at the machine level, these loops become a collection of instructions with labels/addresses and @jump@ instructions to transfer control between parts of the loop.

The situation is very different in \Haskell however. The language does not offer an explicit construct for loops. All looping is expressed in the form of recursion.

If we are to generate \Haskell code that loops over arrays we need a way to express the loops we outlined in the previous chapter as recursive functions in the generated code.



\clearpage
\section{Fast mutable arrays in \Haskell}

The principle data structure that \LiveFusion is ultimately working with is an array. To achieve high performance, the generated code must be able to efficiently loop over arrays in memory which includes both reading an writing.

We have established that looping in \Haskell is done using recursive functions and this section discusses how this can be applied to array computations.

The internal \Loop language has @writeArray@ statement which hints the need for \*mutable* arrays. The use of mutable values is not typical in \Haskell and is discouraged. However, for performance reasons there are mechanisms through which this can be done.

In \Haskell all variable are immutable by default. To achieve mutability one must leave the pure context and use one that supports mutable state. This usually amounts to using @IO@ or @ST@ monads \cite{StateInHaskell}.

The @IO@ monad lets the programmer alter the global state of the program and perform any desired side-effecting computations. On the other hand, @ST@ monad only allows one to work with thread-local mutable memory. This memory is completely local to the monadic computation in that it is allocated, used and destroyed before the monad returns to the pure context.

The return value from the @ST@ monad is a pure \Haskell value. Thus, stateful computations performed inside the monad are not visible outside of the monadic context. The compiler ensures that no mutable state escapes the @ST@ computation. This means that for all intents and purposes an @ST@ computation can be considered pure, despite the fact that it may use side-effects internally (usually for efficiency reasons).

In \Haskell mutable arrays can be used from both @IO@ and @ST@ monads. There are several implementations available providing similar interfaces to efficient mutable arrays. Specifically \LiveFusion internally uses the \name{vector}\footnote{\url{http://hackage.haskell.org/package/vector}} package.\footnote{The choice of \name{vector} library is mostly due to historical reasons. It has been first implemented by Roman Leshchinskiy in the research group I am part of. It provides array functionality to \name{Data Parallel Haskell} and \name{Repa} \cite{KCL+10} both of which originate from this group.} Its use in the examples in this chapter should be quite self-explanatory. Since the \Loop language does not require any side-effecting computations beyond allocating and writing into memory, arrays in @ST@ monad will suffice.

\todo{Perhaps give a simple example of looping using vector if the translation code from Loop to Haskell is hard to understand.}



\clearpage
\section{Compiling \Loop language to \Haskell loops}

In this section I present the translation of the \Loop EDSL to \Haskell. The grammar of \Loop language is given once again in Figure~\ref{fig:Loop-grammar-again}. 

\begin{figure}
\subfile{loop-grammar}
\caption{\Loop language grammar.}
\label{fig:Loop-grammar-again}
\end{figure}
\todo{Put the footnotetext on the same page where the grammar ends up}\footnotetext{For improved readability the unique integers are replaced with meaningful names in the code listings. (Footnote for Figure~\ref{fig:Loop-grammar-again})}

A simple example to be used for illustration purposes is based on the @toPercetages@ function thoroughly studied in the previous chapter (Section~\ref{sec:loop-generation}). The following expression multiplies every element of an array by 100:

\begin{hscode}
map (* 100) xs
\end{hscode}

While the expression only consists of one combinator, @map@, the @xs@ argument may be a fusible pipeline of combinators. Likewise the @map@ itself may be fused into its consumer. However, for our purposes we assume that @xs@ is a \*manifest* array and that the result of @map@ is immediately forced.

The generated \Loop code for the example is shown in the right of Figure~\ref{fig:times100-hs-loop}. Its translation by the \Haskell backend is presented in the left of the same figure. For improved readability the code has been altered in the following ways:
\begin{enumerate}
\halfspacing
\item Function applications $\beta$-reduced
\item Fully qualified names simplified
\item Operators moved to infix position
\item Unique integer suffixes replaced with more descriptive names
\item Explicit literal conversions omitted
\item Strictness annotations (@!@) omitted
\end{enumerate}

\begin{hscode}[%
  columns=fullflexible, % to get well spaced subscripts
  keepspaces,           % and keep spaces
  literate=
    {_xs}{{\sub{xs}}}2
    {_map}{{\sub{map}}}3,    
]
let !elt_1 = (\a -> \b -> (GHC.Num.*) a b) elt_2 (GHC.Num.fromInteger 100)
           %$\Downarrow$%
let elt_map = elt_xs * 100
\end{hscode}


\subfile{lst-times100-hs-loop}



\subsection{Blocks and \texttt{goto}s}

A \Loop is essentially a group of labelled basic blocks with a predefined entry block. Every basic block becomes its own function in the generated code. We see in the example that each block like \[body]\sub{map/xs} became @body@\sub{map} function choosing only one label to represent the block. Each basic block has a unique identifier associated with it (in our case $map$), which distinguishes it from similarly named blocks of any nested loops which may be present.

A \*block* becomes a \*function* in the generated code. Consequently, the @goto@ statements become \*function calls*.

Blocks of the internal \Loop language do not explicitly specify what loop state they reference or declare. A loop's state is implicit and global. In the generated code the state of the loop is passed as function arguments. This is the reason for a large number of arguments to functions generated from blocks. The process for generating the arguments from loop variables will be outlined in Section~\ref{sec:Liveness-analysis} on liveness analysis.


\subsection{Conditionals}

The \Loop language offers two conditional statements: @if@ and @unless@. Given a boolean expression the @if@ statement transfers control to one of the two specified blocks. The @unless@ is a simplified @if@ statement which only transfers control to the specified block if the predicate is \*false*. The @unless@ is used to preempt execution of a block if a condition is not met.

Both @if@ and @unless@ are translated to \Haskell's @if@ expression in the generated code as seen in the \[guard] of the provided example.

% One important thing to note is that the @if@ and the @unless@ must come after all variable bindings and updates. Maybe give an example of (map . filter). But then it is unclear what to do with (map (1/) . filter (/= 0)) The eager evaluation will not short circuit the filter and the division will be performed.


\subsection{Variable bindings and assignments}

In the \Loop language every local variable must be bound before use. The code generator checks to ensure that the control goes through the binding before the first use of the variable.

% Since the language is currently untyped and relies on subsequent type inference and type checking in the generated code compiler, there are no explicit declarations.

The bound variables can be mutable as well as immutable. In fact the \Loop language does not currently make a distinction between the two in the way they are bound and used.

A variable \*binding* appears as a \*strict* @let@ binding in the generated \Haskell code. The exclamation marks, called \*strictness annotations*, (as in @let !x = ...@; omitted from code examples) ensure that every bound variable is evaluated to normal form so no thunks are created during evaluation. In most cases this is not necessary since the \GHC's strictness analysis will find most variables to be strict anyway. %However there are cases, especially in the presence of @filter@ combinators, where forcing strict evaluation is required for maintaining high performance of the generated code. \todo{See if not seq'ing post-filter variables results in thunks}

Whenever a new variable binding is encountered in a block of the loop it is assumed to be a fresh variable and it shadows any previous bindings of that variable in the environment. In practice this is useful for the cases where the block is entered multiple times throughout loop execution. In the studied example the \[body] block binds variables @elt@\sub{xs} and @elt@\sub{map} in every iteration. They are subsequently read in \[body] and \[yield] but are not required afterwards. A simple liveness analysis described in section Section~\ref{sec:Liveness-analysis} allows us to only pass those variables from \[body] to \[yield] and disregard them everywhere else. As such those variables are bound anew in every iteration.

The situation with mutable variables is slightly more complex. For example, the loop index @ix@\sub{xs} is bound like a regular variable in the \[init] block. However, once it has been \*assigned to* in \[bottom], it is given a fresh name @ix@\sub{xs}@'@ in the generated code. This is because variables in \Haskell are immutable. While there are ways to have mutable variables in @ST@ or @IO@ monads it results in less efficient code.\todo{as discussed further in Section ref.}

During liveness analysis mutable variable are treated the same way as their immutable counterparts. Technically it is possible to have a mutable variable that lives during one loop iteration but is not carried over to the next iteration. However, the author is yet to come across a combinator that would require that.


\subsection{Array manipulation}

Array is the fundamental data structure the \Loop language works with. Consequently the array primitives are built right into the language: @readArray@, @writeArray@, @arrayLength@, @newArray@ and @sliceArray@. The implementation of the primitives is presented in Figure~\ref{lst:array-primitives}.

\begin{figure}
\begin{hscode}
import Data.Vector.Unboxed as V
import Data.Vector.Unboxed.Mutable as MV
import Control.Monad.ST

arrayLength :: V.Unbox a => V.Vector a -> Int
arrayLength = V.length

readArray :: V.Unbox a => V.Vector a -> Int -> a
readArray = V.unsafeIndex

writeArray :: V.Unbox a => MV.MVector s a -> Int -> a -> ST s ()
writeArray = MV.unsafeWrite

newArray :: V.Unbox a => Int -> ST s (MV.MVector s a)
newArray = MV.new

sliceArray :: V.Unbox a => MV.MVector s a -> Int -> ST s (V.Vector a)
sliceArray vec len = V.unsafeFreeze $ MV.unsafeTake len vec
\end{hscode}

\caption{Array primitives implementation in \Haskell backend.},
\label{lst:array-primitives}
\end{figure}


The implementation is straightforward and all of these array primitives can be seen used in the example generated code. One will notice, however, that there are two types of vectors in use: \*immutable* @Vector@s and \*mutable* @MVector@s.


\subsubsection*{Immutable vectors}

The \*immutable* vectors are the ones passed around as @Manifest@ arrays in the surface \LiveFusion language. They are pure Haskell values and can be read inside a pure function. They are the array values that are passed into the generated code from the host program and are returned as the result. The @arrayLength@ and @readArray@ statements of the \Loop language result in function calls of the same name in the generated code and operate on immutable @Vector@s.


\subsubsection*{Mutable vectors}

The \*mutable* vectors on the other hand are only used internally by the generated code to create and fill a new array which would represent the result of the loop. The mutability of the vector is indicated in its type and the type of functions that operate on it.

% For example, the type of @unsafeWrite@\footnote{The @unsafe@ prefix of functions used indicates that no bound checks are performed on the indices passed. to avoid runtime overhead.} function which is used to write an element into a mutable array is actually quite a bit more general than that of our own @writeArray@ wrapper around it:

% -- IO/ST generic unsafeWrite
% unsafeWrite :: (Unbox a, PrimMonad m)
%             => MVector (PrimState m) a
%             -> Int
%             -> a
%             -> m ()

% This is done to make it possible to use @MVector@ from both @ST@ and @IO@ monads as we discussed previously. When using @ST@ as the @PrimMonad@ the extra @PrimState@ type argument @s@ ensures that stateful computations on the same @MVector@ value are performed inside the same state thread (i.e. they do not escape from the @ST@ monad).

\begin{hscode}
writeArray :: Unbox a
           => MVector s a
           -> Int
           -> a
           -> ST s ()
\end{hscode}

In the above type of @writeArray@, both the type of @MVector@ and the resulting @ST@ computation are indexed by @s@. This ensures that stateful computations on the same MVector value are performed inside the same state thread and do not escape from the @ST@ monad.

In order to return an array from the plugin, and thus outside the @ST@ monad, it must first be converted to an immutable @Vector@. @sliceArray@ is used for that as indicated by its type. The extra @Int@ argument allows to take only a portion of the array and return that. This is useful in @filter@-like operations which may produce a shorter array than initially allocated. 



\subsection{Returning results}

In all examples seen so far the the result of a loop computation was a single array variable (@result@\sub{map} in the above example). However it doesn't need to be. Both the \Loop language and the code generator can return multiple array and scalar values in nested tuples, e.g.:

\begin{hscode}[%
  columns=fullflexible, % to get well spaced subscripts
  keepspaces,           % and keep spaces
  literate=
    {_fold}{{\sub{fold}}}2
    {_scan}{{\sub{scan}}}2
    {_zip}{{\sub{zip}}}2
    {_r}{{\sub{r}}}2,
]
let acc_fold = ...
result_scan <- sliceArray ix_r arr_scan
result_zip  <- sliceArray ix_r arr_zip
return ((result_scan, result_zip), acc_fold)
\end{hscode}

% There is only a handful of combinators which return a scalar value, notably, @fold@, @index@ and @length@. The latter two are not actually a result of the compiled \Loop computation. They operate on @Manifest@ arrays in the host program. This leaves us currently with just the @fold@ operation which has to be handled differently.

% Whether it is an array or a scalar result, returning it is a matter of calling @return@ of the @ST@ monad with the appropriate variable as argument which can be seen of line \todo{line} in the example code.

% The only additional step required before returning an array is converting the mutable array to an immutable one. This allows the array to be returned to the outside of @ST@ monad and thus be usable in the pure host code. The @sliceArray@ function discussed in the previous section serves this purpose and is automatically generated for the \Loop language's @return@ statement.


\todo{The translation is presented formally in Figure}


\clearpage
\section{Liveness analysis and state passing}
\label{sec:Liveness-analysis}

We have discussed that the individual basic blocks of the \Loop language become @ST@ functions in the generated code. Subsequently the statements that transfer control from one block to the other (@goto@, @unless@, @if@) become function calls. 

\Loop language is largely a procedural language with assignment statement (@:=@) that can mutate variables arbitrarily. However, since the target language \Haskell has no mutable state by default\todo{\footnote{Later I will describe several ways to introduce mutable state in a \Haskell program and show all but the one chosen are currently negatively affecting performance.}} all mutable variables of the \Loop language must be translated to \Haskell as immutable values.

How does one pass state as pure \Haskell values? Each loop potentially has a lot of state that is written and read in different blocks of the loop. Since these blocks are functions it would be natural to assume that the state is passed in function arguments.

The problem, however, is that there is no fixed state alive in the loop at any given time. Referencing the original example in Figure~\ref{fig:times100-hs-loop}:
\begin{itemize}
\halfspacing
\item some intermediate variables like @elt@\sub{xs} are only used inside the block they are defined in (\[body])
\item some variables like @elt@\sub{map} are bound in \[body] and are later referenced in \[yield] but are unused after that
\item some variables are bound in \[init] and are persistent for the whole duration of the loop (counters and accumulators).
\end{itemize}

In order to appropriately generate the argument lists to the functions representing loop blocks I have implemented a \name{liveness analysis} pass in the \LiveFusion EDSL compiler.

\begin{bluebox}
\textbf{\large{Liveness analysis is not a backend feature}}

Liveness analysis operates on \Loop EDSL specification of the program. It computes environment for a control flow graph (CFG) of \*basic blocks* and operates on the notions of variable \*bindings* (@let@) and \*assignments* (@:=@). The outcome of liveness analysis is the information about the use of state in a CFG.\\

As such this pass is not specific to any specific backend and is a way to analyse a program given in \Loop EDSL. Nonetheless, I believe that the necessity for liveness analysis has not been justified until now. With enough foreword, it is described below.
\end{bluebox}

I will now offer an intuitive description for how the algorithm works.
\todo{Give formal semantics too?}

Each loop has a single entry block. Starting with that block, and following the loop's control flow graph (CFG) we recursively determine an environment which holds three properties: 
\begin{enumerate}
\halfspacing
  \item new variables \*bound* in the block (using @let@)
  \item variables that are \*destructively updated* in the current block (using assignment @:=@)
  \item variables otherwise \*assumed* to be in \*environment*:
    \begin{itemize}
      \item either because they are referenced in the \*current* block, or
      \item they are \*assumed* to be in the environment of any of the \*successor* blocks, to which control may be transferred (i.e. variables referenced but not bound in those blocks)
    \end{itemize}
\end{enumerate}

\todo{Give concrete examples}

Once the environment has been computed, it is used to generate function argument lists and the appropriate function calls for each @goto@, @unless@ and @if@ statement. Each of the block's \*assumed* variables becomes the argument of the \Haskell function corresponding to that block. \todo{In the example on Figure, the variable assumed are because...blah}

%The exact same list of variables is used to transfer control to that block, i.e. to make function calls to it. The only important point to make here is that the list of \*updated* variables in the calling block and use the appropriate variable on the caller side (e.g. @i'_xs@ instead of @i_xs@ \todo{on line ...})


\subsection{Discussion of liveness analysis}

Several points to note about computing the environment:
\begin{enumerate}
  \item Some blocks have multiple \*successor* blocks to which control can be transferred (e.g. \[guard] can go to \[body] or \[done]). The union of all \*assumed* variables is taken to determine what need to be in the environment of the current block.

  \item \Loop CFGs are inherently cyclic (e.g. \[bottom] block usually transfers control to \[guard] to begin the new iteration). Cycle detection is required when exploring CFG.

  \item \Loop variables may not be required by the immediate \*successor* basic blocks in the CFG. However, they will be in the set of \*assumed* variables if they are required later on. The relationship is transitive.

  \item The liveness analysis pass will catch any use of variables that have not been previously bound (resulting in a runtime error indicating a problem in the library, not in the client code).
\end{enumerate}

There are also two caveats of the \Haskell code generator in its current state:
\begin{itemize}
\halfspacing
\item A variable can only be assigned once in any given block
\item The new value won't be available until the control is transferred to a successor block
\end{itemize}

Both of the above are not fundamental limitations of either \Loop EDSL or the \Haskell backend. They arise from the fact that the liveness analysis works on \*per-block* basis and not \*per-statement*. This means that liveness analysis attempts to determine which variables are expected to be in scope in a particular block, which are updated and which are passed to successor blocks. However, it does not attempt to do the same for each statement.

So far neither of these limitations posed a problem since the loop structure itself is so modular. There is no apparent need in a more fine-grained per-statement liveness analysis. The generated \Haskell code is run through \GHC which itself has excellent liveness analysis and other compilation tactics resulting in efficient code. The planned \LLVM backend is also likely to be able to optimise the code in its current form.



\clearpage
\section{Interfacing host and plugin code}

In the previous sections we have seen the process of generating \Haskell code from \Loop EDSL. The functions generated from basic blocks of the loop form the main part of the plugin that would later be compiled and loaded into the running host program.

This section describes an extra layer of functionality that enables the dynamic compilation and loading of the generated code.


\subsection{Plugin side entry}

Looking at the plugin code presented at the beginning of this chapter in Figure~\ref{fig:times100-hs-loop}, the entry functions have the following type:

\begin{hscode}[%
  columns=fullflexible, % to get well spaced subscripts
  keepspaces,           % and keep spaces
  literate=
    {_1}{{\sub{map}}}3
    {_2}{{\sub{xs}}}2,
]
fromDyn :: Typeable a => Dynamic -> a
fromDyn d = case fromDynamic d of
              Just v  -> v
              Nothing -> error "Argument type mismatch"

entry :: [Dynamic] -> Dynamic
entry [arr_2] = toDyn (run (fromDyn arr_2))

run :: Vector Double -> Vector Double
run arr_2 = runST (init_1 arr_2)
\end{hscode}

The @entry@ function is the \*dynamically* typed entry into the plugin. Its type is the same for all plugins generated by \LiveFusion. The arguments such as manifest arrays are passed in as a list of @Dynamic@ values\footnote{See \url{http://hackage.haskell.org/package/base/docs/Data-Dynamic.html}} internally holding their type representation. This allows the plugin to coerce the argument to the appropriate type using @fromDyn@ ensuring that the type is correct at runtime.

On the other hand, the @run@ function is the typed entry into the plugin and is specific to every plugin generated.

In a more elaborate program with multiple arguments and return values the plugin may have entry functions such as the following:


\begin{hscode}
entry :: [Dynamic] -> Dynamic
entry [arr_1, arr_2, arr_3, len_4]
  = toDyn (run (fromDyn arr_1)
               (fromDyn arr_2)
               (fromDyn arr_3)
               (fromDyn len_4))

run :: Vector Double -> Vector Double -> Vector Int -> Int
    -> ((Vector Double, Vector Double), Vector Int)
run arr_1 arr_2 arr_3 len_4 = runST (init_5 arr_1 arr_2 arr_3 len_4)
\end{hscode}


Note that the return values are structured in a nested tuple. It resulted from the use of explicit tupling constructor @:*:@ discussed in Section~\ref{sec:AST}. For example:


\begin{hscode}
three :: AST ((Vector Double, Vector Double), Vector Int)
three = let xs :: Array Double = ...
            ys :: Array Double = ...
            zs :: Array Int    = ...
        in  xs :*: ys :*: zs
\end{hscode}



\subsection{Host side dynamic compilation and loading}

The code for the host side dynamic compilation and loading is relatively straightforward and is presented in Listing~\ref{lst:host}. It uses \name{GHC API} for compilation, which means that the \GHC is linked in as a library into every \LiveFusion binary (provided the linking is static).

At the moment the compiled code is not cached for later reuse. This means that if the same combinator graph is executed multiple times, it is recompiled every time. The ability to amortise compilation costs over multiple recursive calls is important for \name{Data Parallel Haskell} programs as we will see in the next chapter and it is left as future work.


\begin{hscode2}[%
  caption={Host side dynamic compilation and loading code},%
  label={lst:host},%
  aboveskip=-20pt,%
]
-- | Evaluates the AST to a final value.
evalAST :: Typeable t => AST t -> t
evalAST ast = result
  where
    loop = getLoop ast
    dynResult = unsafePerformIO $ evalLoopIO loop (typeOf result)
    result = fromJust $ fromDynamic dynResult
{-# NOINLINE evalAST #-}

type Arg = Dynamic

evalLoopIO :: Loop -> TypeRep -> IO Arg
evalLoopIO loop resultTy = do
  (pluginPath, h, moduleName) <- openTempModuleFile
  let entryFnName  = defaultEntryFunctionName ++ moduleName
  let codeString   = pluginCode moduleName entryFnName loop resultTy
  dump codeString h
  pluginEntry <- compileAndLoad pluginPath moduleName entryFnName
  let args    = Map.elems $ loopArgs loop
  let result  = pluginEntry args
  return result

openTempModuleFile :: IO (FilePath, Handle, String)
openTempModuleFile = do
  (fp, h) <- openTempFile "/tmp/" "Plugin.hs"
  let moduleName = takeBaseName fp
  return (fp, h, moduleName)

dump :: String -> Handle -> IO ()
dump code h = hPutStrLn h code >> hClose h

compileAndLoad :: FilePath -> String -> String -> IO ([Arg] -> Arg)
compileAndLoad hsFilePath moduleName entryFnName =
    defaultErrorHandler defaultFatalMessager defaultFlushOut $ do
      runGhc (Just libdir) $ do
        dflags_def <- getSessionDynFlags
        let dflags_dyn = gopt_set dflags_def Opt_BuildDynamicToo
        let dflags_opt = dflags_dyn { optLevel = 2 }
        setSessionDynFlags dflags_opt
        target <- guessTarget hsFilePath Nothing
        setTargets [target]
        r <- load LoadAllTargets
        case r of
          Failed    -> error "Compilation failed"
          Succeeded -> do
            setContext [IIDecl $ simpleImportDecl (mkModuleName moduleName)]
            pluginEntry <- compileExpr (moduleName ++ "." ++ entryFnName)
            let pluginEntry' = unsafeCoerce pluginEntry :: [Arg] -> Arg
            return pluginEntry'
\end{hscode2}



\clearpage

\section{Related work}

\subsection{Alternative backends}

This chapter has introduced the \Haskell backend for \LiveFusion. Dynamically compiling \Haskell modules has become a popular way of extending \Haskell applications with plugins \cite{DonsThesis, PlugginHaskellIn, DynApps}. These applications tend to have their plugins written by hand. This is contrary to the present work, where the plugin code is generated on the fly from the \Loop language code.

However, \LiveFusion is not limited to only one backend. In order to extend the framework to support other backends, a new interpreter for the \Loop language can be built together with an appropriate implementation of the scalar language functions (Section~\ref{sec:Scalar-language}).

One particularly attractive alternative is \LLVM framework \cite{LLVM:CGO04}. \GHC already uses \LLVM to produce highly efficient code. However, using a framework such as \LLVM for compiling \LiveFusion generated code may avoid the costs associated with running the generated code through the complete \GHC compilation pipeline. As it will be seen in the next chapter, a compilation overhead of 600 ms is not uncommon when compiling the generated code with \GHC. Reducing those costs may make \LiveFusion more widely applicable to use cases where many pieces of code must be compiled independently and amortisation cannot be as easily exploited.

While \LiveFusion is already producing optimised procedural style code, it still relies on \GHC to perform some optimisations. In particular user defined scalar functions that parametrise higher-order combinators are inlined without further analysis in hopes that \GHC will subsequently perform all the necessary optimisations on them. This may not be sufficient if \LLVM code is generated directly and \LiveFusion might need extra optimisation passes before the emitted code can target \LLVM.

Direct \LLVM code generation is becoming popular with EDSL for high performance computations. Both \FlowFusion \cite{FlowFusion} and \Accelerate \cite{acc-llvm} are targeting it. The former first converts the AST to \name{DDC Core} \cite{DDC}, an intermediate compiler language similar to \name{GHC Core}. \LLVM has also been successfully used for compiling a digital signal processing EDSL \cite{Thielemann-LLVM, Thielemann-Audio-LLVM}. 

Generating \Haskell and \LLVM are not the only options. \cite{RMKB06} offers a comparative study of \name{TaskGraph}, \name{Fabius} and \name{Tick C} system that are suitable for runtime generation of numeric code (referenced implicitly) before settling with \name{TaskGraph} for \name{DESOLA} (\name{Delayed Evaluation Self Optimising Linear Algebra}), a C++ library mentioned in Section~\ref{sec:DESOLA}. However, \Haskell and \LLVM may be the most suitable targets due to their maturity and availability as part of \Haskell development toolchain.



\subsection{Liveness Analysis and Mutability}

\LiveFusion takes a very high level specification of the program and converts in into an intermediate assembly-style \Loop language. The \Loop language has unconstrained control flow and destructive update which poses a problem when generating code targeting \*single assignment* backends such as \Haskell where all variables are immutable by default. \LLVM, similarly, requires that all registers are in \name{SSA} (\name{Static Single Assignment}) form.

In order to determine appropriate scoping of bound variables in the generated code and ensure that all destructive updates are represented as fresh variables, a liveness analysis pass was implemented (Section~\ref{sec:Liveness-analysis}). The analysis has been developed independently, however, in retrospect it is similar to the ubiquitous data flow analysis of control flow graphs employed by optimising compilers \cite{SSA-Braun13,WatersSeries} including \GHC's own \name{Cmm} language.

While \LiveFusion sports its own implementation of data flow analysis is may be possible to reuse a more easily extensible library for this purpose. For example, \name{Hoopl} \cite{Hoopl} which provides a way to encode data flow analysis and transformations.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Everything below is commented out
\begin{comment}

\subsection{Unboxing}

\subsection{Generating Haskell code}

\subsection{Loop state}
\section{Internal optimisations}




\subsection{Generating}


\subsection{Looping}
\begin{itemize}
\item There are many ways a loop can be represented in code
\item FPrs see it as a recursive function
\item Procedural programmers see it as a while or for C loop
\item Down at the machine level it is a chunk of code with a label and jump statement to the beginning of the loop (or alternatively out of the loop)
\item GPGPU
\item Vectorised instructions
\item When generating HsCode only rec fun, however want fast machine code in the end
\item Tail rec
\item Give example of what machine code it becomes
\item Thus need to make sure we always have tail rec
\end{itemize}

\section{Hell}

\begin{itemize}
\item haskell via TH (slow codegen, all native, TH is helpful, easy to gen code and parametrising functions, use the excellent GHC optimiser)
\item external (c) (slow codegen, fast exec, how to identify function correspondence, must act as compiler)
\item llvm (fast inmem gen, low level, must act as compiler in many ways)

\end {itemize}


\section{Haskell code generation}

\subsection{What do we need to generate}
\begin{itemize}
\item Loop code
\item A plugin template
\item Interface glue
\item Arg passing to and from - variadic functions, can't do without tricks
\item Lists of args + Unsafe coerce
\end{itemize}

\subsection{Efficient numeric computations in Haskell}
\begin{itemize}
\item Talk about haskell data structures (lists, arrays)
\item about boxed values
\item Prohibitive performance costs
\item Unboxed values
\end{itemize}

\subsection{Mutable vectors}
\begin{itemize}
\item Very low level access
\item Haskell vector or GHC.Prim
\item Largely the same underneath
\item Vector may be more intuitive
\item Offers many types of vectors and levels of access to them
\item Uses ST monad, to make sure...
\end{itemize}


\section{GHC provided optimisations}
\subsection{Tail recursion}
\begin{itemize}
\item Perhaps put the points from above here
\end{itemize}

\subsection{Strictness}
\begin{itemize}
\item What is it and why
\item Strictness analysis example
\item Where in our case it would fail
\item What to do: two things, the easiest is !
\end{itemize}

\subsection{Inlining}
\begin{itemize}
\item Funcall costs
\item Perhaps give an example with benchmark
\item LLVM helps?
\end{itemize}

\subsection{Unboxing}
\begin{itemize}
\item Give example
\item Rewrite \texttt{case i\# of I\# ->} which rewrites
\item (Might wanna merge with the section above)
\end{itemize}




\subsection{Compilation and loading}
\begin{itemize}
\item GHC API
\end{itemize} 


\section{Background}

\subsection{Passing loop state}

\begin{itemize}
\item We were passing explicit args
\item fast, GHC knows how to optimise away unused/dup variables (of which we have a lot)
\item STRef/IORefs - convenient but they are boxed and are not inlined even though are programs are strict
\item State monad. Build State monad on top of ST, use tuples for multiple state variables. It inlines and unboxes everything alright, but for some reason there remain lazy lets and continuation.
\item Arguably the cleanest approach to unboxed mutable state. Removes the limitation outlined in () whereby the updated value of the assigned variable won't be available in the same block it's assigned. It would also make the internal compilation process cleaner. Right now it needs to generate a fresh variable name for the updated variable and keep track of the variables updated in the current block.
\end{itemize}

\end{comment}

\IfNotCompilingAll{\printbibliography}

\end{document}