B3 should have documentation
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 29 Jan 2016 22:50:48 +0000 (22:50 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 29 Jan 2016 22:50:48 +0000 (22:50 +0000)

Reviewed by Saam Barati.

Change the documentation to use HTML instead of Markdown.  Markdown has trouble with
definition lists.  Things go downhill when you try to add paragraphs or code blocks to
a definition.  That's unfortunate since we use definitions for the IR document.

Since there is no way to use our preferred styling for the IR document without doing a
lot of bad hacks, it's best if we just stick to HTML. It looks plain but it's highly

* docs/b3/assembly-intermediate-representation.html: Added.
* docs/b3/bare-bones-backend.md: Removed.
* docs/b3/index.html: Added.
* docs/b3/intermediate-representation.html: Added.
* docs/b3/style.css: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195841 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Websites/webkit.org/docs/b3/assembly-intermediate-representation.html [new file with mode: 0644]
Websites/webkit.org/docs/b3/bare-bones-backend.md [deleted file]
Websites/webkit.org/docs/b3/index.html [new file with mode: 0644]
Websites/webkit.org/docs/b3/intermediate-representation.html [new file with mode: 0644]
Websites/webkit.org/docs/b3/style.css [new file with mode: 0644]

index 20c96fe..af59663 100644 (file)
@@ -1,3 +1,26 @@
+2016-01-29  Filip Pizlo  <fpizlo@apple.com>
+        B3 should have documentation
+        https://bugs.webkit.org/show_bug.cgi?id=153658
+        Reviewed by Saam Barati.
+        Change the documentation to use HTML instead of Markdown.  Markdown has trouble with
+        definition lists.  Things go downhill when you try to add paragraphs or code blocks to
+        a definition.  That's unfortunate since we use definitions for the IR document.
+        Since there is no way to use our preferred styling for the IR document without doing a
+        lot of bad hacks, it's best if we just stick to HTML. It looks plain but it's highly
+        practical.
+        * docs/b3/assembly-intermediate-representation.html: Added.
+        * docs/b3/bare-bones-backend.md: Removed.
+        * docs/b3/index.html: Added.
+        * docs/b3/intermediate-representation.html: Added.
+        * docs/b3/style.css: Added.
+        (dd):
+        (dd:last-child):
 2016-01-29  Timothy Hatcher  <timothy@apple.com>
         Add some defintion list styles.
diff --git a/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html b/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html
new file mode 100644 (file)
index 0000000..8fc69e4
--- /dev/null
@@ -0,0 +1,22 @@
+  <head>
+    <title>Assembly Intermediate Representation</title>
+    <link rel="stylesheet" type="text/css" href="style.css">
+  </head>
+  <body>
+    <h1><a href="index.html">Bare Bones Backend</a> / Assembly Intermediate Representation</h1>
+    <p>The B3 compiler converts SSA procedures into efficient machine code by first converting
+      them to a form that reveals machine details, like registers. This form is called Assembly
+      Intermediate Representation, or just Air for short.</p>
+    <p>Air is designed around JavaScriptCore's existing MacroAssembler. Air has Inst objects,
+      which each describe some method call to the MacroAssembler: an Inst's opcode indicates
+      which method name to use and its args indicate the arguments to pass to that method. We
+      use code generation to create a massive switch statement that turns the reflective Insts
+      into actual calls to MacroAssembler. Consequently, we can "add" new instructions to Air
+      usually by just editing the â€‹AirOpcode.opcodes file.</p>
+    <p><a href="https://bugs.webkit.org/show_bug.cgi?id=153668">FIXME: Add more text here.</a></p>
+  </body>
diff --git a/Websites/webkit.org/docs/b3/bare-bones-backend.md b/Websites/webkit.org/docs/b3/bare-bones-backend.md
deleted file mode 100644 (file)
index f22a74a..0000000
+++ /dev/null
@@ -1,132 +0,0 @@
-The Bare Bones Backend, or B3 for short, is WebKit's optimizing JIT for procedures containing C-like code.  It's currently used as the default backend for the [FTL JIT](https://trac.webkit.org/wiki/FTLJIT) inside [JavaScriptCore](https://trac.webkit.org/wiki/JavaScriptCore).
-B3 comprises a [C-like SSA IR](https://trac.webkit.org/wiki/B3IntermediateRepresentation)  known as "B3 IR", optimizations on B3 IR, an [assembly IR](https://trac.webkit.org/wiko/AssemblyIntermediateRepresentation) known as "Air", optimizations on Air, an instruction selector that turns B3 IR into Air, and a code generator that assembles Air into machine code.
-## Hello, World!
-Here's a simple example of C++ code that uses B3 to generate a function that adds two to its argument and returns it:
-    Procedure proc;
-    BasicBlock* root = proc.addBlock();
-    root->appendNew<ControlValue>(
-        proc, Return, Origin(),
-        root->appendNew<Value>(
-            proc, Add, Origin(),
-            root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
-            root->appendNew<Const64Value>(proc, Origin(), 2)));
-    std::unique_ptr<Compilation> compilation = std::make_unique<Compilation>(vm, proc);
-    int64_t (*function)(int64_t) = static_cast<int64_t (*)(int64_t)>(compilation->code().executableAddress());
-    printf("%d\n", function(42)); // prints 43
-When compiled, the resulting machine code looks like this:
-    0x3aa6eb801000: pushq %rbp
-    0x3aa6eb801001: movq %rsp, %rbp
-    0x3aa6eb801004: leaq 0x2(%rdi), %rax
-    0x3aa6eb801008: popq %rbp
-    0x3aa6eb801009: ret 
-B3 always emits a frame pointer prologue/epilogue to play nice with debugging tools.  Besides that, you can see that B3 optimized the procedure's body to a single instruction: in this case, a Load Effective Address to transfer %rdi + 2, where %rdi is the first argument register, into %rax, which is the result register.
-## B3 IR
-Clients of B3 usually interact with it using B3 IR.  It's C-like, in the sense that it models heap references as integers and does not attempt to verify memory accesses.  It enforces static single assignment, or SSA for short.  An SSA program will contain only one assignment to each variable, which makes it trivial to trace from a use of a variable to the operation that defined its value.  B3 IR is designed to be easy to generate and cheap to manipulate.
-B3 is designed to be used as a backend for JITs, rather than as a tool that programmers use directly.  Therefore, B3 embraces platform-specific concepts like argument registers, stack frame layout, the frame pointer, and the call argument areas.  It's possible to emit B3 IR that defines completely novel calling conventions, both for callers of the procedure being generated and for callees of the procedure's callsites.  B3 also makes it easy to just emit a C call.  There's an opcode for that.
-See [the IR documentation](/documentation/b3/intermediate-representation/) for more info.
-Here's an example of the IR from the example above:
-    BB#0: ; frequency = 1.000000
-        Int64 @0 = ArgumentReg(%rdi)
-        Int64 @1 = Const64(2)
-        Int64 @2 = Add(@0, $2(@1))
-        Void @3 = Return(@2, Terminal)
-## B3 Optimizations
-B3 is fairly new - we only started working on it in late Oct 2015.  But it already has some awesome optimizations:
-- CFG simplification.
-- Constant folding with some flow sensitivity.
-- Global CSE, including sophisticated load elimination.
-- Aggressive dead code elimination.
-- Tail duplication.
-- SSA fix-up.
-- Optimal placement of constant materializations.
-- Integer overflow check elimination.
-- Reassociation.
-- Lots of miscellaneous strength reduction rules.
-## Air
-Air, or Assembly IR, is the way that B3 represents the machine instruction sequence prior to code generation.  Air is like assembly, except that in addition to registers it has temporaries, and in addition to the native address forms it has abstract ones like "stack" (an abstract stack slot) and "callArg" (an abstract location in the outgoing call argument area of the stack).
-Here's the initial Air generated from the example above:
-    BB#0: ; frequency = 1.000000
-        Move %rdi, %tmp1, @0
-        Move $2, %tmp2, $2(@1)
-        Add64 $2, %tmp1, %tmp0, @2
-        Move %tmp0, %rax, @3
-        Ret64 %rax, @3
-## Air Optimizations
-Air has sophisticated optimizations that transform programs that use temporaries and abstract stack locations into ones that use registers directly.  Air is also responsible for ABI-related issues like stack layout and handling the C calling convention.  Air has the following optimizations:
-- Iterated Register Coalescing (https://www.cs.princeton.edu/research/techreps/TR-498-95).  This is our register allocator.
-- Graph coloring stack allocation.
-- Spill code fix-up.
-- Dead code elimination.
-- Partial register stall fix-up.
-- CFG simplification.
-- CFG layout optimization.
-Here's what these optimizations do to the example program:
-    BB#0: ; frequency = 1.000000
-        Add64 $2, %rdi, %rax, @2
-        Ret64 %rax, @3
-Note that the "@" references indicate the origin of the instruction in the B3 IR.
-## B3->Air lowering, also known as Instruction Selection
-The B3::LowerToAir phase converts B3 into Air by doing pattern-matching.  It processes programs backwards.  At each B3 value, it greedily tries to match both the value and as many of its children (i.e. Values it uses) and their children as possible to create a single instruction.  Different hardware targets support different instructions.  Air allows B3 to speak of the superset of all instructions on all targets, but exposes a fast query to check if a given instruction, or specific instruction form (like 3-operand add, for example) is available.  The instruction selector simply cascades through the patterns it knows about until it finds one that gives a legal instruction in Air.
-The instruction selector is powerful enough to do basic things like compare-branch and load-op-store fusion.  It's smart enough to do things like what we call the Mega Combo, where the following B3 IR:
-    Int64 @0 = ArgumentReg(%rdi)
-    Int64 @1 = ArgumentReg(%rsi)
-    Int32 @2 = Trunc(@1)
-    Int64 @3 = ZExt32(@2)
-    Int32 @4 = Const32(1)
-    Int64 @5 = Shl(@3, $1(@4))
-    Int64 @6 = Add(@0, @5)
-    Int32 @7 = Load8S(@6, ControlDependent|Reads:Top)
-    Int32 @8 = Const32(42)
-    Int32 @9 = LessThan(@7, $42(@8))
-    Void @10 = Check(@9:WarmAny, generator = 0x103fe1010, earlyClobbered = [], lateClobbered = [], usedRegisters = [], ExitsSideways|Reads:Top)
-Is turned into the following Air:
-    Move %rsi, %tmp7, @1
-    Move %rdi, %tmp1, @0
-    Move32 %tmp7, %tmp2, @3
-    Patch &Branch8(3,SameAsRep), LessThan, (%tmp1,%tmp2,2), $42, @10
-And the resulting code ends up being:
-    0x311001401004: movl %esi, %eax
-    0x311001401006: cmpb $0x2a, (%rdi,%rax,2)
-    0x31100140100a: jl 0x311001401015
-Other than the mandatory zero-extending operation to deal with the 32-bit argument being used as an index, B3 is smart enough to convert the address computation, load, and compare into a single instruction and then fuse that with the branch.
-## Code generation
-The final form of Air contains no registers or abstract stack slots.  Therefore, it maps directly to machine code.  The final code generation step is a very fast transformation from Air's object-oriented way of representing those instructions to the target's machine code.  We use JavaScriptCore's macro assembler for this purpose.
diff --git a/Websites/webkit.org/docs/b3/index.html b/Websites/webkit.org/docs/b3/index.html
new file mode 100644 (file)
index 0000000..2a3ad3b
--- /dev/null
@@ -0,0 +1,192 @@
+  <head>
+    <title>Bare Bones Backend</title>
+    <link rel="stylesheet" type="text/css" href="style.css">
+  </head>
+  <body>
+    <h1>Bare Bones Backend</h1>
+    <p>The Bare Bones Backend, or B3 for short, is WebKit's optimizing JIT for procedures
+      containing C-like code.  It's currently used as the default backend for the
+      <a href="https://trac.webkit.org/wiki/FTLJIT">FTL JIT</a> inside
+      <a href="https://trac.webkit.org/wiki/JavaScriptCore">JavaScriptCore</a>.</p>
+    <p>B3 comprises a <a href="intermediate-representation.html">C-like
+        SSA IR</a> known as "B3 IR", optimizations on B3 IR, an
+      <a href="assembly-intermediate-representation.html">assembly IR</a>
+      known as "Air", optimizations on Air, an instruction selector that turns B3 IR into Air,
+      and a code generator that assembles Air into machine code.</p>
+    <h2>Hello, World!</h2>
+    <p>Here's a simple example of C++ code that uses B3 to generate a function that adds two to
+      its argument and returns it:</p>
+    <pre><code>Procedure proc;
+BasicBlock* root = proc.addBlock();
+    proc, Return, Origin(),
+    root->appendNew&lt;Value&gt;(
+        proc, Add, Origin(),
+        root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0),
+        root->appendNew<Const64Value>(proc, Origin(), 2)));
+std::unique_ptr&lt;Compilation&gt; compilation = std::make_unique&lt;Compilation&gt;(vm, proc);
+int64_t (*function)(int64_t) = static_cast&lt;int64_t (*)(int64_t)&gt;(compilation->code().executableAddress());
+printf("%d\n", function(42)); // prints 44</code></pre>
+    <p>When compiled, the resulting machine code looks like this:</p>
+    <pre><code>0x3aa6eb801000: pushq %rbp
+0x3aa6eb801001: movq %rsp, %rbp
+0x3aa6eb801004: leaq 0x2(%rdi), %rax
+0x3aa6eb801008: popq %rbp
+0x3aa6eb801009: ret </code></pre>
+    <p>B3 always emits a frame pointer prologue/epilogue to play nice with debugging tools.
+      Besides that, you can see that B3 optimized the procedure's body to a single instruction:
+      in this case, a Load Effective Address to transfer %rdi + 2, where %rdi is the first
+      argument register, into %rax, which is the result register.</p>
+    <h2>B3 IR</h2>
+    <p>Clients of B3 usually interact with it using B3 IR.  It's C-like, in the sense that it
+      models heap references as integers and does not attempt to verify memory accesses.  It
+      enforces static single assignment, or SSA for short.  An SSA program will contain only one
+      assignment to each variable, which makes it trivial to trace from a use of a variable to
+      the operation that defined its value.  B3 IR is designed to be easy to generate and cheap
+      to manipulate.</p>
+    <p>B3 is designed to be used as a backend for JITs, rather than as a tool that programmers
+      use directly.  Therefore, B3 embraces platform-specific concepts like argument registers,
+      stack frame layout, the frame pointer, and the call argument areas.  It's possible to emit
+      B3 IR that defines completely novel calling conventions, both for callers of the procedure
+      being generated and for callees of the procedure's callsites.  B3 also makes it easy to
+      just emit a C call.  There's an opcode for that.</p>
+    <p>See <a href="/documentation/b3/intermediate-representation.html">the IR documentation</a>
+      for more info.</p>
+    <p>Here's an example of the IR from the example above:</p>
+    <pre><code>BB#0: ; frequency = 1.000000
+    Int64 @0 = ArgumentReg(%rdi)
+    Int64 @1 = Const64(2)
+    Int64 @2 = Add(@0, $2(@1))
+    Void @3 = Return(@2, Terminal)</code></pre>
+    <h2>B3 Optimizations</h2>
+    <p>B3 is fairly new - we only started working on it in late Oct 2015.  But it already has
+      some awesome optimizations:</p>
+    <ul>
+      <li>CFG simplification.</li>
+      <li>Constant folding with some flow sensitivity.</li>
+      <li>Global CSE, including sophisticated load elimination.</li>
+      <li>Aggressive dead code elimination.</li>
+      <li>Tail duplication.</li>
+      <li>SSA fix-up</li>
+      <li>Optimal placement of constant materializations.</li>
+      <li>Integer overflow check elimination.</li>
+      <li>Reassociation.</li>
+      <li>Lots of miscellaneous strength reduction rules.</li>
+    </ul>
+    <h2>Air</h2>
+    <p>Air, or Assembly IR, is the way that B3 represents the machine instruction sequence prior
+      to code generation.  Air is like assembly, except that in addition to registers it has
+      temporaries, and in addition to the native address forms it has abstract ones like "stack"
+      (an abstract stack slot) and "callArg" (an abstract location in the outgoing call argument
+      area of the stack).</p>
+    <p>Here's the initial Air generated from the example above:</p>
+    <pre><code>BB#0: ; frequency = 1.000000
+    Move %rdi, %tmp1, @0
+    Move $2, %tmp2, $2(@1)
+    Add64 $2, %tmp1, %tmp0, @2
+    Move %tmp0, %rax, @3
+    Ret64 %rax, @3</code></pre>
+    <p>Note that the "@" references indicate the origin of the instruction in the B3 IR.</p>
+    <h2>Air Optimizations</h2>
+    <p>Air has sophisticated optimizations that transform programs that use temporaries and
+      abstract stack locations into ones that use registers directly.  Air is also responsible
+      for ABI-related issues like stack layout and handling the C calling convention.  Air has
+      the following optimizations:</p>
+    <ul>
+      <li><a href="https://www.cs.princeton.edu/research/techreps/TR-498-95">Iterated Register Coalescing</a>.  This is our register allocator.</li>
+      <li>Graph coloring stack allocation.</li>
+      <li>Spill code fix-up.</li>
+      <li>Dead code elimination.</li>
+      <li>Partial register stall fix-up.</li>
+      <li>CFG simplification.</li>
+      <li>CFG layout optimization.</li>
+    </ul>
+    <p>Here's what these optimizations do to the example program:</p>
+    <pre><code>BB#0: ; frequency = 1.000000
+    Add64 $2, %rdi, %rax, @2
+    Ret64 %rax, @3</code></pre>
+    <h2>B3->Air lowering, also known as Instruction Selection</h2>
+    <p>The B3::LowerToAir phase converts B3 into Air by doing pattern-matching.  It processes
+      programs backwards.  At each B3 value, it greedily tries to match both the value and as
+      many of its children (i.e. Values it uses) and their children as possible to create a
+      single instruction.  Different hardware targets support different instructions.  Air
+      allows B3 to speak of the superset of all instructions on all targets, but exposes a fast
+      query to check if a given instruction, or specific instruction form (like 3-operand add,
+      for example) is available.  The instruction selector simply cascades through the patterns
+      it knows about until it finds one that gives a legal instruction in Air.</p>
+    <p>The instruction selector is powerful enough to do basic things like compare-branch and
+      load-op-store fusion.  It's smart enough to do things like what we call the Mega Combo,
+      where the following B3 IR:</p>
+    <pre><code>Int64 @0 = ArgumentReg(%rdi)
+Int64 @1 = ArgumentReg(%rsi)
+Int32 @2 = Trunc(@1)
+Int64 @3 = ZExt32(@2)
+Int32 @4 = Const32(1)
+Int64 @5 = Shl(@3, $1(@4))
+Int64 @6 = Add(@0, @5)
+Int32 @7 = Load8S(@6, ControlDependent|Reads:Top)
+Int32 @8 = Const32(42)
+Int32 @9 = LessThan(@7, $42(@8))
+Void @10 = Check(@9:WarmAny, generator = 0x103fe1010, earlyClobbered = [], lateClobbered = [], usedRegisters = [], ExitsSideways|Reads:Top)</code></pre>
+    <p>Is turned into the following Air:</p>
+    <pre><code>Move %rsi, %tmp7, @1
+Move %rdi, %tmp1, @0
+Move32 %tmp7, %tmp2, @3
+Patch &Branch8(3,SameAsRep), LessThan, (%tmp1,%tmp2,2), $42, @10</code></pre>
+    <p>And the resulting code ends up being:</p>
+    <pre><code>0x311001401004: movl %esi, %eax
+0x311001401006: cmpb $0x2a, (%rdi,%rax,2)
+0x31100140100a: jl 0x311001401015</code></pre>
+    <p>Other than the mandatory zero-extending operation to deal with the 32-bit argument being
+      used as an index, B3 is smart enough to convert the address computation, load, and compare
+      into a single instruction and then fuse that with the branch.</p>
+    <h2>Code generation</h2>
+    <p>The final form of Air contains no registers or abstract stack slots.  Therefore, it maps
+      directly to machine code.  The final code generation step is a very fast transformation
+      from Air's object-oriented way of representing those instructions to the target's machine
+      code.  We use JavaScriptCore's macro assembler for this purpose.</p>
+  </body>
diff --git a/Websites/webkit.org/docs/b3/intermediate-representation.html b/Websites/webkit.org/docs/b3/intermediate-representation.html
new file mode 100644 (file)
index 0000000..a74e97b
--- /dev/null
@@ -0,0 +1,518 @@
+  <head>
+    <title>B3 Intermediate Representation</title>
+    <link rel="stylesheet" type="text/css" href="style.css">
+  </head>
+  <body>
+    <h1><a href="index.html">Bare Bones Backend</a> / B3 Intermediate Representation</h1>
+    <p>B3 IR is a C-like SSA representation of a procedure.  A procedure has a root block at
+      which it starts execution when it is invoked.  A procedure does not have to terminate, but
+      if it does, then it can be either due to a Return, which gracefully returns some value, or
+      by a side-exit at designated instructions.  B3 gives the client a lot of flexibility to
+      implement many different kinds of side-exits.</p>
+    <p>B3 is designed to represent procedures for the purpose of transforming them.  Knowing
+      what transformations are legal requires knowing what a procedure does.  A transformation
+      is valid if it does not change the observable behavior of a procedure.  This document
+      tells you what B3 procedures do by telling you what each construct in B3 IR does.</p>
+    <h2>Procedure</h2>
+    <p>The parent object of all things in B3 is the Procedure.  Every time you want to compile
+      something, you start by creating a Procedure.  The lifecycle of a Procedure is
+      usually:</p>
+    <ol>
+      <li>Create the Procedure.</li>
+      <li>Populate the Procedure with code.</li>
+      <li>Use either the <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Compilation.h">high-level
+          Compilation API</a> or the
+        <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Generate.h">low-level
+          generation API</a>.</li>
+    </ol>
+    <p>The act of compiling the Procedure changes it in-place, making it unsuitable for
+      compiling again.  Always create a new Procedure every time you want to compile
+      something.</p>
+    <h2>Types</h2>
+    <p>B3 has a trivial type system with only five types:</p>
+    <dl>
+      <dt>Void</dt>
+      <dd>Used to say that an instruction does not return a value.</dd>
+      <dt>Int32</dt>
+      <dd>32-bit integer.  Integers don't have sign, but operations on them do.</dd>
+      <dt>Int64</dt>
+      <dd>64-bit integer.</dd>
+      <dt>Float</dt>
+      <dd>32-bit binary floating point number.</dd>
+      <dt>Double</dt>
+      <dd>64-bit binary floating point number.</dd>
+    </dl>
+    <h2>Values</h2>
+    <p>Variables, and the instructions that define them, are represented using the Value object.
+      The Value object has a return type, an opcode, and zero or more children.  Children are
+      references to other Values.  Values also have a unique 32-bit index that is used as the
+      name.  Those values are used as input to the instruction that computes this value.  For
+      example:</p>
+    <pre><code>Int32 @3 = Add(@1, @2)</code></pre>
+    <p>This represents a single Value instance.  Its index is 3.  It is an Int32.  The opcode is
+      Add, and its children are @1 and @2.</p>
+    <p>Values may also have additional meta-data.  We use special subclasses of the B3::Value
+      class for values that need meta-data.  For example, the Load value needs a 32-bit offset
+      for the load.  We use the MemoryValue class for memory-accessing values, which all have
+      such an offset.</p>
+    <h2>Stack Slot</h2>
+    <p>B3 exposes the concept of stack-allocated data and gives the client a lot of control.
+      You can force stack slots to end up at a particular offset from the frame pointer, though
+      this is very dangerous.  After compilation is done, you can get the selected frame pointer
+      offset from any stack slot.  Usually, you let B3 select where stack slots go, and then use
+      the StackSlot API to get its FP offset after compilation.</p>
+    <p>Stack slots are also used for creating non-SSA variables with the intention of having B3
+      convert them into SSA.  There are two kinds of stack lots.</p>
+    <dl>
+      <dt>Anonymous</dt>
+      <dd>Anonymous stack slots are used to represent local variables that aren't in SSA form.
+        B3 is allowed to assume that nobody will store to an anonymous stack slot except through
+        Store instructions in the B3 procedure.  B3 is allowed to assume that a Store that does
+        not write to the entire anonymous stack slot leaves the unwritten part in an undefined
+        state.  Usually, anonymous stack slots are allocated to have the same size as the type
+        of variable they are being used to represent.</dd>
+      <dt>Locked</dt>
+      <dd>These stack slots are assumed to operate "as if" they were in the heap, in the sense
+        that the may get read or written using operations not visible in B3 IR.</dd>
+    </dl>
+    <p>The fixSSA() phase will convert anonymous stack slots to SSA.</p>
+    <h2>Control flow</h2>
+    <p>B3 represents control flow using basic blocks.  Each basic block may have zero or more
+      predecessors.  Each basic block may have zero or more successors.  The successors are
+      controlled by the basic block's last Value, which must be a ControlValue instance.</p>
+    <p>Each basic block contains a Vector&lt;Value*&gt; as the contents of the block.</p>
+    <h2>Opcodes</h2>
+    <p>This section describes opcodes in the following format:</p>
+    <dl>
+      <dt>Int32 Foo(Int64, Double)</dt>
+      <dd>This describes an opcode named Foo that uses Int32 as its return type and takes two
+        children - one of type Int64 and another of type Double.</dd>
+    </dl>
+    <p>We sometimes use the wildcard type T to represent polymorphic operations, like "T Add(T,
+      T)".  This means that the value must take two children of the same type and returns a
+      value of that type.  We use the type IntPtr to mean either Int32, or Int64, depending on
+      the platform.</p>
+    <h3>Opcode descriptions</h3>
+    <dl>
+      <dt>Void Nop()</dt>
+      <dd>The empty value.  Instead of removing Values from basic blocks, most optimizations
+        convert them to Nops.  Various phases run fix-up where all Nops are removed in one pass.
+        It's common to see Nops in intermediate versions of B3 IR during optimizations.  Nops
+        never lead to any code being generated and they do not impede optimizations, so they are
+        usually harmless.  You can convert a Value to a Nop by doing convertToNop().</dd>
+      <dt>T Identity(T)</dt>
+      <dd>Returns the passed value.  May be used for any type except Void.  Instead of replacing
+        all uses of a Value with a different Value, most optimizations convert them to Identity.
+        Various phases run fix-up where all uses of Identity are replaced with the Identity's
+        child (transitively, so Identity(Identity(Identity(@x))) is changed to just @x).  Even
+        the instruction selector "sees through" Identity.  You can remove all references to
+        Identity in any value by calling Value::performSubstitution().  You can convert a Value
+        to an Identity by doing convertToIdentity(otherValue).  If the value is Void,
+        convertToIdentity() converts it to a Nop instead.</dd>
+      <dt>Int32 Const32(constant)</dt>
+      <dd>32-bit integer constant.  Must use the Const32Value class, which has space for the
+        int32_t constant.</dd>
+      <dt>Int64 Const64(constant)</dt>
+      <dd>64-bit integer constant.  Must use the Const64Value class, which has space for the
+        int64_t constant.</dd>
+      <dt>Float ConstFloat(constant)</dt>
+      <dd>Float constant.  Must use the ConstFloatValue class, which has space for the float constant.</dd>
+      <dt>Double ConstDouble(constant)</dt>
+      <dd>Double constant.  Must use the ConstDoubleValue class, which has space for the double constant.</dd>
+      <dt>IntPtr SlotBase(stackSlot)</dt>
+      <dd>Returns a pointer to the base of the given stack slot.  Must use the SlotBaseValue
+        class.</dd>
+      <dt>IntPtr|Double ArgumentReg(%register)</dt>
+      <dd>Returns the value that the given register had at the prologue of the procedure.  It
+        returns IntPtr for general-purpose registers and Double for FPRs.  Must use the
+        ArgumentRegValue class.</dd>
+      <dt>IntPtr FramePointer()</dt>
+      <dd>Returns the value of the frame pointer register.  B3 procedures alway use a frame
+        pointer ABI, and the frame pointer is always guaranteed to have this value anywhere
+        inside the procedure.</dd>
+      <dt>T Add(T, T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents addition with
+        wrap-around semantics.  For floating point types, this represents addition according to
+        the IEEE 854 spec.  B3 does not have any notion of "fast math".  A transformation over
+        floating point code is valid if the new code produces exactly the same value, bit for
+        bit.</dd>
+      <dt>T Sub(T, T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents subtraction with
+        wrap-around semantics.  For floating point types, this represents subtraction according
+        to the IEEE 854 spec.</dd>
+      <dt>T Mul(T, T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents multiplication
+        with wrap-around semantics.  For floating point types, this represents multiplication
+        according to the IEEE 854 spec.</dd>
+      <dt>T Div(T, T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents signed division
+        with round-to-zero.  Its behavior is undefined for x/0 or -2`^`31/-1.  For floating
+        point types, this represents division according to the IEEE 854 spec.</dd>
+      <dt>T Mod(T, T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents signed modulo.
+        Its behavior is undefined for x%0 or -2`^`31%-1.  For floating point types, this
+        represents modulo according to "fmod()".</dd>
+      <dt>T Neg(T)</dt>
+      <dd>Works with any type except Void.  For integer types, this represents twos-complement
+        negation.  For floating point types, this represents negation according to the IEEE
+        spec.</dd>
+      <dt>T ChillDiv(T, T)</dt>
+      <dd>Chill division.  Valid for Int32 and Int64.  An operation is said to be chill if it
+        returns a sensible value whenever its non-chill form would have had undefined behavior.
+        ChillDiv turns x/0 into 0 and -2`^`31/-1 into -2`^`31.  This is a separate opcode
+        because it's exactly the semantics of division on ARM64, and it's also exactly the
+        semantics that JavaScript wants for "(x/y)|0".</dd>
+      <dt>T ChillMod(T, T)</dt>
+      <dd>Chill modulo.  Valid for Int32 and Int64.  ChllMod turns x%0 into 0 and -2`^`31%-1
+        into 0.</dd>
+      <dt>T BitAnd(T, T)</dt>
+      <dd>Bitwise and.  Valid for Int32 and Int64.</dd>
+      <dt>T BitOr(T, T)</dt>
+      <dd>Bitwise or.  Valid for Int32 and Int64.</dd>
+      <dt>T BitXor(T, T)</dt>
+      <dd>Bitwise xor.  Valid for Int32 and Int64.</dd>
+      <dt>T Shl(T, Int32)</dt>
+      <dd>Shift left.  Valid for Int32 and Int64.  The shift amount is always Int32.  Only the
+        low 31 bits of the shift amount are used for Int32.  Only the low 63 bits of the shift
+        amount are used for Int64.</dd>
+      <dt>T SShr(T, Int32)</dt>
+      <dd>Shift right with sign extension.  Valid for Int32 and Int64.  The shift amount is
+        always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
+        low 63 bits of the shift amount are used for Int64.</dd>
+      <dt>T ZShr(T, Int32)</dt>
+      <dd>Shift right with zero extension.  Valid for Int32 and Int64.  The shift amount is
+        always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
+        low 63 bits of the shift amount are used for Int64.</dd>
+      <dt>T Clz(T)</dt>
+      <dd>Count leading zeroes.  Valid for Int32 and Int64.</dd>
+      <dt>T Abs(T)</dt>
+      <dd>Absolute value.  Valid for Float and Double.</dd>
+      <dt>T Ceil(T)</dt>
+      <dd>Ceiling.  Valid for Float and Double.</dd>
+      <dt>T Sqrt(T)</dt>
+      <dd>Square root.  Valid for Float and Double.</dd>
+      <dt>U BitwiseCast(T)</dt>
+      <dd>If T is Int32 or Int64, it returns the bitwise-corresponding Float or Double,
+        respectively.  If T is Float or Double, it returns the bitwise-corresponding Int32 or
+        Int64, respectively.</dd>
+      <dt>Int32 SExt8(Int32)</dt>
+      <dd>Fills the top 24 bits of the integer with the low byte's sign extension.</dd>
+      <dt>Int32 SExt16(Int32)</dt>
+      <dd>Fills the top 16 bits of the integer with the low short's sign extension.</dd>
+      <dt>Int64 SExt32(Int32)</dt>
+      <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
+        high 32 bits are its sign extension.</dd>
+      <dt>Int64 ZExt32(Int32)</dt>
+      <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
+        high 32 bits are zero.</dd>
+      <dt>Int32 Trunc(Int64)</dt>
+      <dd>Returns the low 32 bits of the 64-bit value.</dd>
+      <dt>Double IToD(T)</dt>
+      <dd>Converts the given integer into a double.  Value for Int32 or Int64 inputs.</dd>
+      <dt>Double FloatToDouble(Float)</dt>
+      <dd>Converts the given float into a double.</dd>
+      <dt>Float DoubleToFloat(Double)</dt>
+      <dd>Converts the given double into a float.</dd>
+      <dt>Int32 Equal(T, T)</dt>
+      <dd>Compares the two values.  If they are equal, return 1; else return 0.  Valid for all
+        types except Void.  Integer comparisons simply compare all bits.  Floating point
+        comparisons mostly compare bits, but have some corner cases: positive zero and negative
+        zero are considered equal, and they return false when either value is NaN.</dd>
+      <dt>Int32 NotEqual(T, T)</dt>
+      <dd>The opposite of Equal().  NotEqual(@x, @y) yields the same result as BitXor(Equal(@x,
+        @y), 1).</dd>
+      <dt>Int32 LessThan(T, T)</dt>
+      <dd>Returns 1 if the left value is less than the right one, 0 otherwise.  Does a signed
+        comparison for integers.  For floating point comparisons, this has the usual caveats
+        with respect to negative zero and NaN.</dd>
+      <dt>Int32 GreaterThan(T, T)</dt>
+      <dd>Returns 1 if the left value is greater than the right one, 0 otherwise.  Does a signed
+        comparison for integers.  For floating point comparisons, this has the usual caveats
+        with respect to negative zero and NaN.</dd>
+      <dt>Int32 LessEqual(T, T)</dt>
+      <dd>Returns 1 if the left value is less than or equal to the right one, 0 otherwise.  Does
+        a signed comparison for integers.  For floating point comparisons, this has the usual
+        caveats with respect to negative zero and NaN.</dd>
+      <dt>Int32 GreaterEqual(T, T)</dt>
+      <dd>Returns 1 if the left value is greater than or equal to the right one, 0 otherwise.
+        Does a signed comparison for integers.  For floating point comparisons, this has the
+        usual caveats with respect to negative zero and NaN.</dd>
+      <dt>Int32 Above(T, T)</dt>
+      <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
+        value is unsigned-greater-than the right one, 0 otherwise.</dd>
+      <dt>Int32 Below(T, T)</dt>
+      <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
+        value is unsigned-less-than the right one, 0 otherwise.</dd>
+      <dt>Int32 AboveEqual(T, T)</dt>
+      <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
+        value is unsigned-greater-than-or-equal the right one, 0 otherwise.</dd>
+      <dt>Int32 BelowEqual(T, T)</dt>
+      <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
+        value is unsigned-less-than-or-equal the right one, 0 otherwise.</dd>
+      <dt>Int32 EqualOrUnordered(T, T)</dt>
+      <dd>Floating point comparison, valid for Float and Double only.  Returns 1 if the left
+        value is equal to the right one or if either value is NaN.  Returns 0 otherwise.</dd>
+      <dt>T Select(U, T, T)</dt>
+      <dd>Returns either the second child or the third child.  T can be any type except Void.  U
+        can be either Int32 or Int64.  If the first child is non-zero, returns the second child.
+        Otherwise returns the third child.</dd>
+      <dt>Int32 Load8Z(IntPtr, offset)</dt>
+      <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
+        signed integer offset to the child value.  Zero extends the loaded byte, so the high 24
+        bits are all zero.  Must use the MemoryValue class.</dd>
+      <dt>Int32 Load8S(IntPtr, offset)</dt>
+      <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
+        signed integer offset to the child value.  Sign extends the loaded byte.  Must use the
+        MemoryValue class.</dd>
+      <dt>Int32 Load16Z(IntPtr, offset)</dt>
+      <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
+        32-bit signed integer offset to the child value.  Zero extends the loaded 16-bit
+        integer, so the high 16 bits are all zero.  Misaligned loads are not penalized.  Must
+        use the MemoryValue class.</dd>
+      <dt>Int32 Load16S(IntPtr, offset)</dt>
+      <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
+        32-bit signed integer offset to the child value.  Sign extends the loaded 16-bit
+        integer.  Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
+      <dt>T Load(IntPtr, offset)</dt>
+      <dd>Valid for any type except Void.  Loads a value of that type from the address, which is
+        computed by adding the compile-time 32-bit signed integer offset to the child value.
+        Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
+      <dt>Void Store8(Int32, IntPtr, offset)</dt>
+      <dd>Stores a the low byte of the first child into the address computed by adding the
+        compile-time 32-bit signed integer offset to the second child.  Must use the MemoryValue
+        class.</dd>
+      <dt>Void Store16(Int32, IntPtr, offset)</dt>
+      <dd>Stores a the low 16 bits of the first child into the address computed by adding the
+        compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
+        not penalized.  Must use the MemoryValue class.</dd>
+      <dt>Void Store(T, IntPtr, offset)</dt>
+      <dd>Stores the value in the first child into the address computed by adding the
+        compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
+        not penalized.  Must use the MemoryValue class.</dd>
+      <dt>T1 CCall(IntPtr, [T2, [T3, ...]])</dt>
+      <dd>Performs a C function call to the function pointed to by the first child.  The types
+        that the function takes and the type that it returns are determined by the types of the
+        children and the type of the CCallValue.  Only the first child is mandatory.  Must use
+        the CCallValue class.</dd>
+      <dt>T1 Patchpoint([T2, [T3, ...]])</dt>
+      <dd>A Patchpoint is a customizable value.  Patchpoints take zero or more values of any
+        type and return any type.  A Patchpoint's behavior is determined by the generator
+        object.  The generator is a C++ lambda that gets called during code generation.  It gets
+        passed an assembler instance (specifically, CCallHelpers&) and an object describing
+        where to find all of the input values and where to put the result.  Here's an example:
+        <pre><code>PatchpointValue* patchpoint = block->appendNew&lt;PatchpointValue&gt;(proc, Int32, Origin());
+patchpoint->append(ConstrainedValue(arg1, ValueRep::SomeRegister));
+patchpoint->append(ConstrainedValue(arg2, ValueRep::SomeRegister));
+    [&] (CCallHelpers& jit, const StackmapGenerationParams& params) {
+        jit.add32(params[1].gpr(), params[2].gpr(), params[0].gpr());
+    });</code></pre>
+        <p>This creates a patchpoint that just adds two numbers. The patchpoint is set to return
+          Int32.  The two child values, arg1 and arg2, are passed to the patchpoint with the
+          SomeRegister constraint, which just requests that they get put in appropriate
+          registers (GPR for integer values, FPR for floating point values).  The generator uses
+          the params object to figure out which registers the inputs are in (params[1] and
+          params[2]) and which register to put the result in (params[0]).  Many sophisticated
+          constraints are possible.  You can request that a child gets placed in a specific
+          register.  You can list additional registers that are
+          clobbered - either at the top of the patchpoint (i.e. early) so that the clobbered
+          registers interfere with the inputs, or at the bottom of the patchpoint (i.e. late) so
+          that the clobbered registers interfere with the output.  Patchpoint constraints also
+          allow you to force values onto the call argument area of the stack.  Patchpoints are
+          powerful enough to implement custom calling conventions, inline caches, and
+          side-exits.</p>
+        <p>A patchpoint is allowed to "side exit", i.e. abruptly exit from the procedure.  If it
+          wants to do so by returning, it can use Procedure's API for getting the callee-save
+          register layout, unwinding the callee-saves, and then returning.  More likely, the
+          patchpoint will take some exit state as part of its arguments, and it will manipulate
+          the call frame in place to make it look like another execution engine's call frame.
+          This is called OSR, and JavaScriptCore does it a lot.</p>
+        <p>Must use the PatchpointValue class with the Patchpoint opcode.</p>
+      </dd>
+      <dt>T CheckAdd(T, T, [T2, [T3, ...]])</dt>
+      <dd>Checked integer addition.  Works for T = Int32 or T = Int64.  First first two children
+        are mandatory.  Additional children are optional.  All of the Check instructions take a
+        generator and value constraints like a Patchpoint.  In the case of a CheckAdd, the
+        generator runs on the path where the integer addition overflowed.  B3 assumes that
+        CheckAdd will side-exit upon overflow, so the generator must do some kind of
+        termination.  Usually, this is used to implement OSR exits on integer overflow and the
+        optional arguments to CheckAdd will be the OSR exit state.  Must use the CheckValue
+        class.</dd>
+      <dt>T CheckSub(T, T, [T2, [T3, ...]])</dt>
+      <dd>Checked integer subtraction.  Works for T = Int32 or T = Int64.  First first two
+        children are mandatory.  Additional children are optional.  All of the Check
+        instructions take a generator and value constraints like a Patchpoint.  In the case of a
+        CheckSub, the generator runs on the path where the integer subtraction overflowed.  B3
+        assumes that CheckSub will side-exit upon overflow, so the generator must do some kind
+        of termination.  Usually, this is used to implement OSR exits on integer overflow and
+        the optional arguments to CheckSub will be the OSR exit state.  You can use CheckSub for
+        checked negation by using zero for the first child.  B3 will select the native negate
+        instruction when you do this.  Must use the CheckValue class.</dd>
+      <dt>T CheckMul(T, T, [T2, [T3, ...]])</dt>
+      <dd>Checked integer multiplication.  Works for T = Int32 or T = Int64.  First first two
+        children are mandatory.  Additional children are optional.  All of the Check
+        instructions take a generator and value constraints like a Patchpoint.  In the case of a
+        CheckMul, the generator runs on the path where the integer multiplication overflowed.
+        B3 assumes that CheckMul will side-exit upon overflow, so the generator must do some
+        kind of termination.  Usually, this is used to implement OSR exits on integer overflow
+        and the optional arguments to CheckMul will be the OSR exit state.  Must use the
+        CheckValue class.</dd>
+      <dt>Void Check(T, [T2, [T3, ...]])</dt>
+      <dd>Exit check.  Works for T = Int32 or T = Int64.  This branches on the first child.  If
+        the first child is zero, this just falls through.  If it's non-zero, it goes to the exit
+        path generated by the passed generator.  Only the first child is mandatory.  B3 assumes
+        that Check will side-exit when the first child is non-zero, so the generator must do
+        some kind of termination.  Usually, this is used to implement OSR exit checks and the
+        optional arguments to Check will be the OSR exit state.  Check supports efficient
+        compare/branch fusion, so you can Check for fairly sophisticated predicates.  For
+        example, Check(Equal(LessThan(@a, @b), 0)) where @a and @b are doubles will be generated
+        to an instruction that branches to the exit if @a &gt;= @b or if either @a or @b are
+        NaN.  Must use the CheckValue class.</dd>
+      <dt>Void Upsilon(T, ^phi)</dt>
+      <dd>B3 uses SSA.  SSA requires that each variable gets assigned to only once anywhere in
+        the procedure.  But that doesn't work if you have a variable that is supposed to be the
+        result of merging two values along control flow.  B3 uses Phi values to represent value
+        merges, just like SSA compilers usually do.  But while other SSA compilers represent the
+        inputs to the Phi by listing the control flow edges from which the Phi gets its values,
+        B3 uses the Upsilon value.  Each Phi behaves as if it has a memory location associated
+        with it.  Executing the Phi behaves like a load from that memory location.
+        Upsilon(@value, ^phi) behaves like a store of @value into the memory location associated
+        with @phi.  We say "^phi" when we mean that we are writing to the memory location
+        associated with the Phi.  Must use the UpsilonValue class.</dd>
+      <dt>T Phi()</dt>
+      <dd>Works for any type except Void.  Represents a local memory location large enough to
+        hold T.  Loads from that memory location.  The only way to store to that location is
+        with Upsilon.</dd>
+      <dt>Void Jump(takenBlock)</dt>
+      <dd>Jumps to takenBlock.  This is a ControlValue, so it must appear at the end of the
+        basic block.</dd>
+      <dt>Void Branch(T, takenBlock, notTakenBlock)</dt>
+      <dd>Works for T = Int32 or T = Int64.  Branches on the child.  If the child is non-zero,
+        it branches to the takenBlock.  Otherwise it branches to the notTakenBlock.  Must use
+        the ControlValue class.  Must appear at the end of the basic block.</dd>
+      <dt>Void Switch(T, cases...)</dt>
+      <dd>Works for T = Int32 or T = Int64.  Switches on the child.  Contains a list of switch
+        cases.  Each switch case has an integer constant and a target block.  The switch value
+        also contains a fall-through target in case the child has a value that wasn't mentioned
+        in the cases list.  Must use the SwitchValue class.  Must appear at the end of the basic
+        block.</dd>
+      <dt>Void Return(T)</dt>
+      <dd>Works for any type except Void.  Returns the given value and terminates the procedure.
+        This is a ControlValue, but it must have an empty successors list.  Must appear at the
+        end of the basic block.</dd>
+      <dt>Void Oops()</dt>
+      <dd>Indicates unreachable code.  This may be implemented as either a trap or as a bare
+        fall-through, since B3 is allowed to assume that this will never be reached.  This is a
+        ControlValue, but it must have an empty successors list.  Must appear at the end of the
+        basic block.  Note that we also use the Oops opcode to mean "no such opcode" in some B3
+        transformations.</dd>
+    </dl>
+  </body>
diff --git a/Websites/webkit.org/docs/b3/style.css b/Websites/webkit.org/docs/b3/style.css
new file mode 100644 (file)
index 0000000..daa9288
--- /dev/null
@@ -0,0 +1,6 @@
+dd {
+    padding: 0 0 0.5em 0;
+dd:last-child {
+    padding: 0 0 0 0;