Camil Demetrescu edited osr-llvm.tex  over 8 years ago

Commit id: 56079d1d23e25890fb53de944f4f256139dadb9e

deletions | additions      

       

%\subsection{Example}  In this section we discuss how to implement the OSR approach of \mysection\ref{se:overview} in LLVM. Our discussion is based on a simple example that illustrates a profile-driven optimization scenario. We start from a simple base function ({\tt isord}) that checks whether an array of numbers is ordered according to some criterion specified by a comparator, as shown in \myfigure\ref{fi:isord-example}. Our goal is to instrument {\tt isort} so that, whenever the number of iterations of {\tt isord} exceeds a certain threshold, control is dynamically diverted to a faster version generated on the fly by inlining the comparator.   The IR code shown in this section has been generated with \osrkit, an LLVM-based library we designed that supports to support  VM builders with a set of abstractions for perform  OSR instrumentation of IR code\ifauthorea{}{\footnote{\osrkit\ is included code\footnote{Virtual register names and labels in the LLVM-produced IR code shown  in this paper have been refactored to make  the accompanying artifact.}}. code more readable.}.  %To explain how the OSR approach of \mysection\ref{se:overview} can be implemented in LLVM, we consider the simple example of \myfigure\ref{fi:isord-example}. Function {\tt isord} checks whether an array of numbers is ordered according to some criterion specified by a comparator. 

\fi  \paragraph{OSR Instrumentation in IR.}  To defer the compilation of the continuation function until the comparator is known at run time, we instrument {\tt isord} with an open OSR point at the beginning of the loop body, as shown in \myfigure\ref{fig:isordfrom}. Portions added to the original code by OSR istrumentation are highlighted in grey\footnote{Virtual register names and labels in the LLVM-produced IR code have been refactored to make the code more readable.}. grey.  %The figure illustrates how the original {\tt isord} code is instrumented by \tinyvm, highlighting in grey the added portions.   A new basic block is placed at the beginning of the loop body, which increments a hotness counter {\tt p.osr} and jumps to an OSR-firing block if the counter reaches the threshold (1000 iterations in this example). The OSR block contains a tail call to the target generation stub, which receives as parameters the four live variables at the OSR point ({\tt v}, {\tt n}, {\tt i}, {\tt c}). Notice that maintaining the SSA form requires adjusting $\phi$-nodes. The stub (see \myfigure[...]) calls a code generator that: 1) builds an optimized version of {\tt isord} by inlining the comparator (which is known when the OSR is fired), and 2) uses it to create the continuation function {\tt isordto} shown in \myfigure\ref{fig:isordascto}. The stub terminates with a tail call to {\tt isordto}. To generate the continuation function from the optimized version created by the inliner, we need to replace the function entry point, remove dead code, replace live variables with the function parameters, and fix $\phi$-nodes accordingly. Additions resulting from the IR instrumentation are in grey, while removals are struck-through.