Websites/webkit.org/docs/b3/index.html

   1 <html>
   2 <head>
   3   <title>Bare Bones Backend</title>
   4   <link rel="stylesheet" type="text/css" href="style.css">
   5 </head>
   6 <body>
   7   <div id="banner">
   8     <a href="http://www.webkit.org/" class="banner-link">
   9       <div id="logo" class="site-logo">
  10         WebKit
  11         <span class="tagline">Open Source Web Browser</span>
  12       </div>
  13     </a>
  14   </div>
  15   <div id="contents">
  16     <h1>Bare Bones Backend</h1>
  17     <p>The Bare Bones Backend, or B3 for short, is WebKit's optimizing JIT for procedures
  18       containing C-like code.  It's currently used as the default backend for the
  19       <a href="https://trac.webkit.org/wiki/FTLJIT">FTL JIT</a> inside
  20       <a href="https://trac.webkit.org/wiki/JavaScriptCore">JavaScriptCore</a>.</p>
  21
  22     <p>B3 comprises a <a href="intermediate-representation.html">C-like
  23         SSA IR</a> known as "B3 IR", optimizations on B3 IR, an
  24       <a href="assembly-intermediate-representation.html">assembly IR</a>
  25       known as "Air", optimizations on Air, an instruction selector that turns B3 IR into Air,
  26       and a code generator that assembles Air into machine code.</p>
  27
  28     <h2>Hello, World!</h2>
  29
  30     <p>Here's a simple example of C++ code that uses B3 to generate a function that adds two to
  31       its argument and returns it:</p>
  32
  33     <pre><code>Procedure proc;
  34 BasicBlock* root = proc.addBlock();
  35 root->appendNew&lt;ControlValue&gt;(
  36     proc, Return, Origin(),
  37     root->appendNew&lt;Value&gt;(
  38         proc, Add, Origin(),
  39         root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
  40         root->appendNew<Const64Value>(proc, Origin(), 2)));
  41
  42 std::unique_ptr&lt;Compilation&gt; compilation = std::make_unique&lt;Compilation&gt;(vm, proc);
  43 int64_t (*function)(int64_t) = bitwise_cast&lt;int64_t (*)(int64_t)&gt;(compilation->code().executableAddress());
  44
  45 printf("%lld\n", function(42)); // prints 44</code></pre>
  46
  47     <p>When compiled, the resulting machine code looks like this:</p>
  48
  49     <pre><code>0x3aa6eb801000: pushq %rbp
  50 0x3aa6eb801001: movq %rsp, %rbp
  51 0x3aa6eb801004: leaq 0x2(%rdi), %rax
  52 0x3aa6eb801008: popq %rbp
  53 0x3aa6eb801009: ret </code></pre>
  54
  55     <p>B3 always emits a frame pointer prologue/epilogue to play nice with debugging tools.
  56       Besides that, you can see that B3 optimized the procedure's body to a single instruction:
  57       in this case, a Load Effective Address to transfer %rdi + 2, where %rdi is the first
  58       argument register, into %rax, which is the result register.</p>
  59
  60     <h2>B3 IR</h2>
  61
  62     <p>Clients of B3 usually interact with it using
  63       <a href="intermediate-representation.html">B3 IR</a>.  It's C-like, in the sense that it
  64       models heap references as integers and does not attempt to verify memory accesses.  It
  65       enforces static single assignment, or SSA for short.  An SSA program will contain only one
  66       assignment to each variable, which makes it trivial to trace from a use of a variable to
  67       the operation that defined its value.  B3 IR is designed to be easy to generate and cheap
  68       to manipulate.</p>
  69
  70     <p>B3 is designed to be used as a backend for JITs, rather than as a tool that programmers
  71       use directly.  Therefore, B3 embraces platform-specific concepts like argument registers,
  72       stack frame layout, the frame pointer, and the call argument areas.  It's possible to emit
  73       B3 IR that defines completely novel calling conventions, both for callers of the procedure
  74       being generated and for callees of the procedure's callsites.  B3 also makes it easy to
  75       just emit a C call.  There's an opcode for that.</p>
  76
  77     <p>See <a href="intermediate-representation.html">the IR documentation</a> for more
  78       info.</p>
  79
  80     <p>Here's an example of the IR from the example above:</p>
  81
  82     <pre><code>BB#0: ; frequency = 1.000000
  83     Int64 @0 = ArgumentReg(%rdi)
  84     Int64 @1 = Const64(2)
  85     Int64 @2 = Add(@0, $2(@1))
  86     Void @3 = Return(@2, Terminal)</code></pre>
  87
  88     <h2>B3 Optimizations</h2>
  89
  90     <p>B3 is fairly new - we only started working on it in late Oct 2015.  But it already has
  91       some awesome optimizations:</p>
  92
  93     <ul>
  94       <li>CFG simplification.</li>
  95       <li>Constant folding with some flow sensitivity.</li>
  96       <li>Global CSE, including sophisticated load elimination.</li>
  97       <li>Aggressive dead code elimination.</li>
  98       <li>Tail duplication.</li>
  99       <li>SSA fix-up</li>
 100       <li>Optimal placement of constant materializations.</li>
 101       <li>Integer overflow check elimination.</li>
 102       <li>Reassociation.</li>
 103       <li>Lots of miscellaneous strength reduction rules.</li>
 104     </ul>
 105
 106     <h2>Air</h2>
 107
 108     <p><a href="assembly-intermediate-representation.html">Air</a>, or Assembly IR, is the way
 109       that B3 represents the machine instruction sequence prior
 110       to code generation.  Air is like assembly, except that in addition to registers it has
 111       temporaries, and in addition to the native address forms it has abstract ones like "stack"
 112       (an abstract stack slot) and "callArg" (an abstract location in the outgoing call argument
 113       area of the stack).</p>
 114
 115     <p>Here's the initial Air generated from the example above:</p>
 116
 117     <pre><code>BB#0: ; frequency = 1.000000
 118     Move %rdi, %tmp1, @0
 119     Move $2, %tmp2, $2(@1)
 120     Add64 $2, %tmp1, %tmp0, @2
 121     Move %tmp0, %rax, @3
 122     Ret64 %rax, @3</code></pre>
 123
 124     <p>Note that the "@" references indicate the origin of the instruction in the B3 IR.</p>
 125
 126     <h2>Air Optimizations</h2>
 127
 128     <p>Air has sophisticated optimizations that transform programs that use temporaries and
 129       abstract stack locations into ones that use registers directly.  Air is also responsible
 130       for ABI-related issues like stack layout and handling the C calling convention.  Air has
 131       the following optimizations:</p>
 132
 133     <ul>
 134       <li><a href="https://www.cs.princeton.edu/research/techreps/TR-498-95">Iterated Register Coalescing</a>.  This is our register allocator.</li>
 135       <li>Graph coloring stack allocation.</li>
 136       <li>Spill code fix-up.</li>
 137       <li>Dead code elimination.</li>
 138       <li>Partial register stall fix-up.</li>
 139       <li>CFG simplification.</li>
 140       <li>CFG layout optimization.</li>
 141     </ul>
 142
 143     <p>Here's what these optimizations do to the example program:</p>
 144
 145     <pre><code>BB#0: ; frequency = 1.000000
 146     Add64 $2, %rdi, %rax, @2
 147     Ret64 %rax, @3</code></pre>
 148
 149     <h2>B3->Air lowering, also known as Instruction Selection</h2>
 150
 151     <p>The B3::LowerToAir phase converts B3 into Air by doing pattern-matching.  It processes
 152       programs backwards.  At each B3 value, it greedily tries to match both the value and as
 153       many of its children (i.e. Values it uses) and their children as possible to create a
 154       single instruction.  Different hardware targets support different instructions.  Air
 155       allows B3 to speak of the superset of all instructions on all targets, but exposes a fast
 156       query to check if a given instruction, or specific instruction form (like 3-operand add,
 157       for example) is available.  The instruction selector simply cascades through the patterns
 158       it knows about until it finds one that gives a legal instruction in Air.</p>
 159
 160     <p>The instruction selector is powerful enough to do basic things like compare-branch and
 161       load-op-store fusion.  It's smart enough to do things like what we call the Mega Combo,
 162       where the following B3 IR:</p>
 163
 164     <pre><code>Int64 @0 = ArgumentReg(%rdi)
 165 Int64 @1 = ArgumentReg(%rsi)
 166 Int32 @2 = Trunc(@1)
 167 Int64 @3 = ZExt32(@2)
 168 Int32 @4 = Const32(1)
 169 Int64 @5 = Shl(@3, $1(@4))
 170 Int64 @6 = Add(@0, @5)
 171 Int32 @7 = Load8S(@6, ControlDependent|Reads:Top)
 172 Int32 @8 = Const32(42)
 173 Int32 @9 = LessThan(@7, $42(@8))
 174 Void @10 = Check(@9:WarmAny, generator = 0x103fe1010, earlyClobbered = [], lateClobbered = [],
 175                  usedRegisters = [], ExitsSideways|Reads:Top)</code></pre>
 176
 177     <p>Is turned into the following Air:</p>
 178
 179     <pre><code>Move %rsi, %tmp7, @1
 180 Move %rdi, %tmp1, @0
 181 Move32 %tmp7, %tmp2, @3
 182 Patch &Branch8(3,SameAsRep), LessThan, (%tmp1,%tmp2,2), $42, @10</code></pre>
 183
 184     <p>And the resulting code ends up being:</p>
 185
 186     <pre><code>0x311001401004: movl %esi, %eax
 187 0x311001401006: cmpb $0x2a, (%rdi,%rax,2)
 188 0x31100140100a: jl 0x311001401015</code></pre>
 189
 190     <p>Other than the mandatory zero-extending operation to deal with the 32-bit argument being
 191       used as an index, B3 is smart enough to convert the address computation, load, and compare
 192       into a single instruction and then fuse that with the branch.</p>
 193
 194     <h2>Code generation</h2>
 195
 196     <p>The final form of Air contains no registers or abstract stack slots.  Therefore, it maps
 197       directly to machine code.  The final code generation step is a very fast transformation
 198       from Air's object-oriented way of representing those instructions to the target's machine
 199       code.  We use JavaScriptCore's macro assembler for this purpose.</p>
 200
 201   </div>
 202 </body>
 203 </html>
 204
 205