Saturday 29 June 2013

Simplifying LLVM IR for PNaCl

Lately I've been working on Portable Native Client ("PNaCl" for short).

Native Client (NaCl) is a sandboxing system that allows safe execution of native code in a web browser -- typically C/C++ code compiled to x86-32, x86-64 or ARM native code (with some support for MIPS too). The problem with NaCl has always been that you have to compile your program multiple times, once for each target architecture. PNaCl aims to solve that, so that your program can be compiled once to an architecture-neutral executable which is then translated to x86 or ARM inside the web browser.

PNaCl is based on LLVM, and PNaCl's executable format is based on LLVM's IR ("Intermediate Representation") language and its binary encoding, LLVM bitcode. LLVM's IR language is quite complex, so we're pruning out and expanding out a lot of features in order to ensure that PNaCl will be maintainable in the long term and to reduce executable sizes.

As an example, consider this fragment of C code:

    struct foo {
      int x;
      int y;
    };

    void func(struct foo *ptr) {
      ptr->y = 123;
    }

Normally in LLVM this compiles to the following LLVM assembly code:

    %struct.foo = type { i32, i32 }

    define void @func(%struct.foo* nocapture %ptr) #0 {
    entry:
      %y = getelementptr inbounds %struct.foo* %ptr, i32 0, i32 1
      store i32 123, i32* %y, align 4, !tbaa !0
      ret void
    }

    attributes #0 = { nounwind }
    !0 = metadata !{metadata !"int", metadata !1}

With PNaCl, we strip out the types, names and metadata so that this becomes:

    define internal void @67(i32) {
      %2 = add i32 %0, 4
      %3 = inttoptr i32 %2 to i32*
      store i32 123, i32* %3, align 1
      ret void
    }

The definition of the struct type goes away. The "getelementptr" instruction is how LLVM handles pointer arithmetic for indexing into structs and arrays -- this gets expanded out and is replaced with pointer arithmetic on integers. The "%struct.foo*" pointer type is replaced with the i32 type. The "inttoptr" instruction remains as a vestige of LLVM's type system: every "load" or "store" instruction in a PNaCl executable is preceded by an "inttoptr" so that the program remains well-typed by LLVM's rules.

This is actually rather similar to what Emscripten and asm.js do. Like PNaCl, Emscripten is a system for running C/C++ programs in the web browser, but it compiles programs down to Javascript rather than using LLVM bitcode as an interchange format. Both PNaCl and Emscripten use Clang as a C/C++ front end, and run LLVM optimisation passes on the resulting LLVM IR code. In compiling to Javascript, Emscripten performs similar simplification steps for lowering IR, and asm.js codifies the resulting Javascript subset.