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.

2 comments:

Toby said...

Mark, Can you say whether there is any plan to verify PNaCl, ala Greg Morriset's RockSalt for original NaCl?

Mark Seaborn said...

PNaCl is basically a portability layer on top of the existing NaCl sandboxes (for x86-32, x86-64 and ARM). The machine code that the PNaCl translator generates runs inside the NaCl sandbox, so this code has to pass the NaCl validator. The PNaCl translator also runs inside a NaCl sandbox, in a separate process.

I'm not sure what you mean by verifying PNaCl. We don't have any proofs that the PNaCl translator always generates safe code, for example, but since NaCl runs the validator on the generated code, such a proof is not necessary for safety. If we had such a proof, it would be useful as an optimisation, because it would let us skip running the validator. Currently, though, the NaCl x86/ARM validators are a lot faster than the PNaCl translator, so skipping validation wouldn't reduce the overall startup time by much.

NaCl has actually switched to using new implementations of the x86 validators that use a DFA-based approach that is similar to RockSalt's design. I think the switchover is happening in Chrome 28.