path: root/docs/paper.tex

\documentclass[11pt]{proc}
%\documentclass[preprint,10pt]{sigplanconf}

\usepackage{amsmath}
\usepackage{url}

\begin{document}

%\conferenceinfo{Splash '11}{??-2011, Portland.} 
%\copyrightyear{2011} 
%\copyrightdata{[to be supplied]} 

%\titlebanner{}        % These are ignored unless
%\preprintfooter{(C) 2011 Alon Zakai, Creative Commons BY-SA Licensed}   % 'preprint' option specified.

\title{Emscripten: An LLVM-to-JavaScript Compiler}
%\subtitle{}

%\authorinfo{Alon Zakai}
%           {Mozilla}
%           {azakai@mozilla.com}

\author{Alon Zakai \\ Mozilla \\ \url{azakai@mozilla.com}}

\maketitle

\begin{abstract}
JavaScript is the standard language of the web, supported on essentially
all web browsers. Despite efforts to allow other languages to be run as well,
none have come close to being universally available on all
browsers, which severely limits their usefulness on the web. However, there are reasonable reasons why
allowing other languages would be beneficial, including reusing existing code and allowing
developers to use their languages of choice.

We present Emscripten, an LLVM-to-JavaScript compiler. Emscripten compiles
LLVM assembly code into standard JavaScript, which opens up two avenues for running code written
in other languages on the web: (1) Compile a language directly into LLVM, and
then compile that into JavaScript using Emscripten, or (2) Compiling
a language's entire runtime (typically written in C or C++) into JavaScript using Emscripten, and
using the compiled runtime to run code written in that language. Examples of languages
that can use the first approach are C and C++, as compilers exist for them into LLVM. An example
of a language that can use the second approach is Python, and Emscripten has
been used to compile CPython (the standard C implementation of Python) into JavaScript,
allowing standard Python code to be run on the web, which was not previously
possible.

Emscripten itself is written in JavaScript (to enable various
dynamic compilation techniques), and is available under the MIT
license (a permissive open source license), at \url{http://www.emscripten.org}.
As an LLVM-to-JavaScript compiler, the challenges in designing
Emscripten are somewhat the reverse of the norm -- one must go from a low-level
assembly into a high-level language, and recreate parts of the original
high-level structure of the code that were lost in the compilation to
low-level LLVM. We detail the algorithms used in
Emscripten to deal with those challenges.

\end{abstract}

%\category{CR-number}{subcategory}{third-level}

%\terms
%term1, term2

%\keywords
%keyword1, keyword2

\bigskip

\copyright 2011 Alon Zakai. License: Creative Commons Attribution-ShareAlike (CC BY-SA), \url{http://creativecommons.org/licenses/by-sa/3.0/}

\section{Introduction}

Since the mid 1990's, JavaScript has been present in most web browsers (sometimes
with minor variations and under slightly different names, e.g., JScript in Internet
Explorer), and today it is
well-supported on essentially all web browsers, from desktop browsers like
Internet Explorer, Firefox, Chrome and Safari, to mobile browsers on smartphones
and tablets. Together with HTML and CSS, JavaScript is the standards-based
foundation of the web.

Running other programming languages on the web has been suggested many times,
and browser plugins have allowed doing so, e.g., via the Java
and Flash plugins. However, plugins must be manually installed and do not integrate in
a perfect way with the outside HTML. Perhaps more problematic is that they cannot run
at all on some platforms, for example, Java and Flash cannot run on iOS devices such as the iPhone
and iPad. For those reasons, JavaScript remains
the primary programming language of the web.

There are, however, justifiable motivations for running code from
other programming languages on the web, for example, if one has a large
amount of existing code already written in another language, or if one
simply has a strong preference for another language (and perhaps is
more productive in it).

As a consequence, there have been some efforts to compile languages
\textbf{into} JavaScript. Since JavaScript is present in essentially all web
browsers, by compiling one's language of choice into JavaScript, one
can still generate content that will run practically everywhere.
Examples of this approach include the Google Web Toolkit, which compiles
Java into JavaScript; Pyjamas, which compiles Python into JavaScript;
Script\# and jsc, % http://jsc.sourceforge.net/
which compile .NET assemblies into JavaScript; and there are rumors
about an Oracle project to translate JVM bytecode into JavaScript.

In this paper we present another project along those lines: \textbf{Emscripten},
which compiles LLVM assembly into JavaScript. LLVM (Low Level Virtual
Machine) is a compiler project primarily focused on C, C++ and
Objective-C. It compiles those languages through a \emph{frontend} (the
main ones of which are Clang and LLVM-GCC) into the
LLVM intermediary representation (which can be machine-readable
bitcode, or human-readable assembly), and then passes it
through a \emph{backend} which generates actual machine code for a particular
architecure. Emscripten plays the role of a backend which targets JavaScript.

By using Emscripten, potentially many languages can be
run on the web, using one of the following methods:
\begin{itemize}
\item Compile \textbf{code} in a language recognized by one of the existing LLVM frontends
      into LLVM, and then compile that
      into JavaScript using Emscripten. Frontends for various languages
      exist, including many of the most popular programming languages such as C and
      C++, and also various new and emerging languages (e.g., Rust).
\item Compile the \textbf{runtime} used to parse and execute code in
      a particular language into LLVM, then compile that into JavaScript using
      Emscripten. It is then possible to run code in that runtime on the web.
      This is a useful approach if
      a language's runtime is written in a language for which an LLVM
      frontend exists, but the language iself has no such frontend. For
      example, no currently-supported frontend exists for Python, however
      it is possible to compile CPython -- the standard implementation of
      Python, written in C -- into JavaScript, and run Python code on that
      (see Subsection X.Y).
\end{itemize}

From a technical standpoint, the main challenges in designing and implementing
Emscripten are that it compiles a low-level language -- LLVM assembly -- into
a high-level one -- JavaScript. This is somethat the reverse of the usual
situation one is in when building a compiler, and leads to some unique
difficulties. For example, to get good performance in JavaScript one must
use natural JavaScript code flow structures, like loops and ifs, but
those structures do not exist in LLVM assembly (instead, what is present
there is essentially `flat' code with \emph{goto} commands).
Emscripten must therefore reconstruct a high-level
representation from the low-level data it receives.

In theory that issue could have been avoided by compiling a higher-level
language into JavaScript. For example, if compiling Java into JavaScript
(as the Google Web Toolkit does), then one can benefit from the fact
that Java's loops, ifs and so forth generally have a very direct parallel
in JavaScript (of course the downside is that this approach yields a
compiler only for Java). Compiling LLVM into JavaScript is less straightforward,
but wee will see later that it is possible to reconstruct
a substantial part of the high-level structure of the original code.

We conclude this introduction with a list of this paper's main contributions:
\begin{itemize}
\item We describe Emscripten itself, during
      which we detail its approach in compiling LLVM into JavaScript.
\item We give details of Emscripten's `Relooper' algorithm, which generates
      high-level loop structures from low-level branching data. We are
      unaware of related results in the literature.
\end{itemize}
In addition, the following are the main contributions of Emscripten
itself, that to our knowledge were not previously possible:
\begin{itemize}
\item It allows compiling a very large subset of C and C++ code into
      JavaScript, which can then be run on the web.
\item By compiling their runtimes, it allows running languages such as Python
      on the web.
\end{itemize}

The remainder of this paper is structured as follows. In Section 2 we
describe, from a high level, the approach taken to compiling LLVM assembly into JavaScript.
In Section 3 we describe the workings of Emscripten on a lower, more
concrete level. In Section 4 we give an overview of some uses of
Emscripten. In Section 5 we summarize and give directions for future
work on Emscripten and uses of it.

\section{Compilation Approach}

Let us begin by considering what the challenge is, when we want to compile something
into JavaScript. Assume we are given the
following simple example of a C program, which we want to compile into JavaScript:
\begin{verbatim}
  #include <stdio.h>
  int main()
  {
    int sum = 0;
    for (int i = 1; i < 100; i++)
      sum += i;
    printf("1+...+100=%d\n", sum);
    return 0;
  }
\end{verbatim}
This program calculates the sum of the integers from 1 to 100. When
compiled by Clang, the generated LLVM
assembly code includes the following:
\begin{verbatim}
@.str = private constant [14 x i8]
        c"1+...+100=%d\0A\00"

define i32 @main() {
  %1 = alloca i32, align 4
  %sum = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 0, i32* %sum, align 4
  store i32 1, i32* %i, align 4
  br label %2

; <label>:2
  %3 = load i32* %i, align 4
  %4 = icmp slt i32 %3, 100
  br i1 %4, label %5, label %12

; <label>:5
  %6 = load i32* %i, align 4
  %7 = load i32* %sum, align 4
  %8 = add nsw i32 %7, %6
  store i32 %8, i32* %sum, align 4
  br label %9

; <label>:9
  %10 = load i32* %i, align 4
  %11 = add nsw i32 %10, 1
  store i32 %11, i32* %i, align 4
  br label %2

; <label>:12
  %13 = load i32* %sum, align 4
  %14 = call i32 (i8*, ...)*
        @printf(i8* getelementptr inbounds
          ([14 x i8]* @.str, i32 0, i32 0),
          i32 %13)
  ret i32 0
}
\end{verbatim}
At first glance, this may look more difficult to translate into
JavaScript than the original C++. However, compiling C++ in
general would require writing code to handle preprocessing,
classes, templates, and all the idiosyncrasies and complexities
of C++. LLVM assembly, while more verbose in this example, is
lower-level and simpler to work on. It also has the benefit we
mentioned earlier, which
is one of the main goals of Emscripten, that many languages can
be compiled into LLVM.

A detailed overview of LLVM assembly is beyond our scope here. Briefly,
though, the example assembly above can easily be seen to define a
function main(), then allocate some values on the stack (alloca),
then load and store various values (load and store). We do not have
the high-level code structure as we had in C++, with a loop, instead
we have code `fragments', each with a label, and code flow moves
from one to another by branch (br) instructions. (Label 2 is the
condition check in the loop; label 5 is the body, label 9 is the
increment, and label 12 is the final part of the function, outside
of the loop).
Conditional branches
can depend on calculations, for example the results of comparing
two values (icmp). Other numerical operations include addition (add).
Finally, printf is called (call). The challenge, then, is to convert
this and things like it into JavaScript.

In general, Emscripten's approach is to translate each line of LLVM
assembly into JavaScript, 1 for 1, into `normal' JavaScript
as much as possible. So, for example, an \emph{add} operation becomes
a normal JavaScript addition, a function call becomes a JavaScript
function call, etc. This 1 to 1 translation generates JavaScript
that resembles assembly code, for example, the LLVM assembly shown
before for main() would be compiled into the following:
\begin{verbatim}
function _main() {
  var __stackBase__  = STACKTOP;
  STACKTOP += 12;
  var __label__ = -1;
  while(1) switch(__label__) {
    case -1:
      var $1 = __stackBase__;
      var $sum = __stackBase__+4;
      var $i = __stackBase__+8;
      HEAP[$1] = 0;
      HEAP[$sum] = 0;
      HEAP[$i] = 0;
      __label__ = 0; break;
    case 0:
      var $3 = HEAP[$i];
      var $4 = $3 < 100;
      if ($4) { __label__ = 1; break; }
      else    { __label__ = 2; break; }
    case 1:
      var $6 = HEAP[$i];
      var $7 = HEAP[$sum];
      var $8 = $7 + $6;
      HEAP[$sum] = $8;
      __label__ = 3; break;
    case 3:
      var $10 = HEAP[$i];
      var $11 = $10 + 1;
      HEAP[$i] = $11;
      __label__ = 0; break;
    case 2:
      var $13 = HEAP[$sum];
      var $14 = _printf(__str, $13);
      STACKTOP = __stackBase__;
      return 0;
  }
}
\end{verbatim}
Some things
to take notice of:
\begin{itemize}
\item A switch-in-a-loop construction is used in order to let the flow
      of execution move between fragments of code in an arbitrary manner: We set
      \emph{\_\_label\_\_} to the (numerical representation of the) label of
      the fragment we want to reach, and do a break, which leads to the proper
      fragment being reached. Inside each fragment, every line of code corresponds to a line of
      LLVM assembly, generally in a very straightforward manner. 
\item Memory is implemented by \emph{HEAP}, a JavaScript array. Reading from
      memory is a read from that array, and writing to memory is a write.
      \emph{STACKTOP} is the current position of the stack. (Note that we
      allocate 4 memory locations for 32-bit integers on the stack, but only 
      write to 1 of them. See the Load-Store Consistency subsection below for why.)
\item LLVM assembly functions become JavaScript functions, and function calls
      are normal JavaScript function calls. In general, we attempt to generate
      as `normal' JavaScript as possible.
\end{itemize}

\subsection{Load-Store Consistency (LSC)}

We saw before that Emscripten's memory usage allocates the usual number
of bytes on the stack for variables (4 bytes for a 32-bit integer, etc.).
However, we only wrote values into the first location, which appeared odd.
We will now see the reason for that.

To get there, we must first step back, and note that
Emscripten does not aim to achieve perfect compatibility with all possible
LLVM assembly (and correspondingly, with all possible C or C++ code, etc.);
instead, Emscripten targets a subset of LLVM assembly code, which is portable
and does not make crucial assumptions about the underlying CPU architecture
on which the code is meant to run. That subset is meant to encompass the
vast majority of real-world code that would be compiled into LLVM,
while also being compilable into very
performant JavaScript.

More specifically, Emscripten assumes that the LLVM assembly code it is
compiling has \textbf{Load-Store Consistency} (LSC), which is the requirement that
loads from and stores to a specific memory address will use the same type. Normal C and C++
code generally does so: If $x$ is a variable containing a 32-bit floating
point number, then both loads and stores of $x$ will be of 32-bit floating
point values, and not 16-bit unsigned integers or anything else. (Note that
even if we write something like \begin{verbatim}float x = 5\end{verbatim} then the
compiler will assign a 32-bit float with the value of 5 to $x$, and not
an integer.)

To see why this is important for performance, consider the following
C code fragment, which does \emph{not} have LSC:
\begin{verbatim}
  int x = 12345;
  [...]
  printf("first byte: %d\n", *((char*)&x));
\end{verbatim}
Assuming an architecture with more than 8 bits, this code will read
the first byte of \emph{x}. (It might, for example, be used to detect the
endianness of the CPU.) To compile this into JavaScript in
a way that will run properly, we must do more than a single operation
for either the read or the write, for example we could do this:
\begin{verbatim}
  var x_value = 12345;
  var x_addr = stackAlloc(4);
  HEAP[x_addr]   = (x_value >> 0) & 255;
  HEAP[x_addr+1] = (x_value >> 8) & 255;
  HEAP[x_addr+2] = (x_value >> 16) & 255;
  HEAP[x