Websites/webkit.org/docs/b3/intermediate-representation.html

   1 <html>
   2 <head>
   3   <title>B3 Intermediate Representation</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 Engine</span>
  12       </div>
  13     </a>
  14   </div>
  15   <div id="contents">
  16     <h1><a href="index.html">Bare Bones Backend</a> / B3 Intermediate Representation</h1>
  17     <p>B3 IR is a C-like SSA representation of a procedure.  A procedure has a root block at
  18       which it starts execution when it is invoked.  A procedure does not have to terminate, but
  19       if it does, then it can be either due to a Return, which gracefully returns some value, or
  20       by a side-exit at designated instructions.  B3 gives the client a lot of flexibility to
  21       implement many different kinds of side-exits.</p>
  22
  23     <p>B3 is designed to represent procedures for the purpose of transforming them.  Knowing
  24       what transformations are legal requires knowing what a procedure does.  A transformation
  25       is valid if it does not change the observable behavior of a procedure.  This document
  26       tells you what B3 procedures do by telling you what each construct in B3 IR does.</p>
  27
  28     <h2>Procedure</h2>
  29
  30     <p>The parent object of all things in B3 is the Procedure.  Every time you want to compile
  31       something, you start by creating a Procedure.  The lifecycle of a Procedure is
  32       usually:</p>
  33
  34     <ol>
  35       <li>Create the Procedure.</li>
  36       <li>Populate the Procedure with code.</li>
  37       <li>Use either the <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Compilation.h">high-level
  38           Compilation API</a> or the
  39         <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Generate.h">low-level
  40           generation API</a>.</li>
  41     </ol>
  42
  43     <p>The act of compiling the Procedure changes it in-place, making it unsuitable for
  44       compiling again.  Always create a new Procedure every time you want to compile
  45       something.</p>
  46
  47     <h2>Types</h2>
  48
  49     <p>B3 has a trivial type system with only five types:</p>
  50
  51     <dl>
  52       <dt>Void</dt>
  53       <dd>Used to say that an instruction does not return a value.</dd>
  54
  55       <dt>Int32</dt>
  56       <dd>32-bit integer.  Integers don't have sign, but operations on them do.</dd>
  57
  58       <dt>Int64</dt>
  59       <dd>64-bit integer.</dd>
  60
  61       <dt>Float</dt>
  62       <dd>32-bit binary floating point number.</dd>
  63
  64       <dt>Double</dt>
  65       <dd>64-bit binary floating point number.</dd>
  66     </dl>
  67
  68     <p>B3 does not have a pointer type. Instead, the <code>B3::pointerType()</code> function will
  69       return either Int32 or Int64 depending on which kind of integer can be used to represent a
  70       pointer on the current platform. It's not a goal of B3 to support hardware targets that require
  71       pointers and integers to be segregated. It's not a goal of B3 to support GC (garbage
  72       collection) roots as a separate type, since JSC uses
  73       <a href="http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-88-2.pdf">Bartlett-style conservative
  74         root scanning</a>. This doesn't preclude any mainstream garbage collection algorithms,
  75       including copying, generational, or concurrent collectors, and frees up the compiler to perform
  76       more optimizations.</p>
  77
  78     <h2>Values</h2>
  79
  80     <p>Variables, and the instructions that define them, are represented using the Value object.
  81       The Value object has a return type, a kind, and zero or more children.  Children are
  82       references to other Values.  Those values are used as input to the instruction that
  83       computes this value.</p>
  84
  85     <p>The value kind is a combination of an opcode and optional flags. The flags allow a single
  86       opcode to have many variants. For example, Div and Mod may have the Chill flag set to indicate
  87       that they should not trap on corner cases.</p>
  88
  89     <p>Values also have a unique 32-bit index that is used as the name.</p>
  90
  91     <p>Example:</p>
  92
  93     <pre><code>Int32 @3 = Add(@1, @2)</code></pre>
  94
  95     <p>This represents a single Value instance.  Its index is 3.  It is an Int32.  The opcode is
  96       Add, and its children are @1 and @2.</p>
  97
  98     <p>Values may also have additional meta-data.  We use special subclasses of the B3::Value
  99       class for values that need meta-data.  For example, the Load value needs a 32-bit offset
 100       for the load.  We use the MemoryValue class for memory-accessing values, which all have
 101       such an offset.</p>
 102
 103     <h2>Stack Slots</h2>
 104
 105     <p>B3 exposes the concept of stack-allocated data and gives the client a lot of control.
 106       By default, stack slots get allocated wherever B3 chooses. It will try to pack them as
 107       much as possible. After compilation is done, you can retrieve each stack slot's location
 108       in the form of an offset from the frame pointer.</p>
 109
 110     <p>You can force stack slots to end up at a particular offset from the frame pointer, though
 111       this is very dangerous.  For example, B3 assumes that it can use the slots closest to the
 112       frame pointer for callee-saves, and currently when you force something to a particular
 113       frame pointer offset, there is no mechanism to notice that this space is also being used
 114       for callee-saves.  Therefore, we recommend not using the frame pointer offset forcing
 115       feature unless you know a lot about the ABI and you have no other choice.</p>
 116
 117     <h2>Variables</h2>
 118
 119     <p>Sometimes, SSA is inconvenient. For example, it's hard to do path specialization over SSA.
 120       B3 has the concept of Variables as a fall-back. The backend knows how to handle them and
 121       will coalesce and copy-propagate them. Inside the B3 optimizer, there is a classic SSA
 122       builder that eliminates variables and builds SSA in their place.</p>
 123
 124     <p>You can create Variables by using Procedure::addVariable(), and then you can access them
 125       using the Get and Set opcodes.</p>
 126
 127     <p>The fixSSA() phase will convert variables to SSA. If you use a lot of variables in your
 128       input to B3, it's a good idea to run fixSSA() manually before running the compiler. The
 129       default optimizer only runs fixSSA() towards the middle of optimizations. Passing non-SSA code
 130       as input to the optimizer may render the early phases ineffective. Fortunately, B3 phases
 131       are super easy to run. The following runs SSA fix-up on a Procedure named "proc":</p>
 132
 133     <pre><code>fixSSA(proc);</code></pre>
 134
 135     <h2>Control flow</h2>
 136
 137     <p>B3 represents control flow using basic blocks.  Each basic block may have zero or more
 138       predecessors.  Each basic block may have zero or more successors.  The meaning of the
 139       successors is determined by the basic block's last Value, which must be a terminal. A
 140       value is terminal if:</p>
 141
 142     <pre><code>value-&gt;effects().terminal</code></pre>
 143
 144     <p>Some opcodes are definitely terminal, like Jump, Branch, Oops, Return, and Switch. But a
 145       value with the Patchpoint opcode may or may not be terminal. In general it's necessary to
 146       check the <code>terminal</code> bit as shown above.</p>
 147
 148     <p>Each basic block contains a Vector&lt;Value*&gt; as the contents of the block. Control
 149       flow inside the block is implicit based on the order of Values in the vector.</p>
 150
 151     <h2>Opcodes</h2>
 152
 153     <p>This section describes opcodes in the following format:</p>
 154
 155     <dl>
 156       <dt>Int32 Foo(Int64, Double)</dt>
 157       <dd>This describes an opcode named Foo that uses Int32 as its return type and takes two
 158         children - one of type Int64 and another of type Double.</dd>
 159     </dl>
 160
 161     <p>We sometimes use the wildcard type T to represent polymorphic operations, like "T Add(T,
 162       T)".  This means that the value must take two children of the same type and returns a
 163       value of that type.  We use the type IntPtr to mean either Int32, or Int64, depending on
 164       the platform.</p>
 165
 166     <h3>Opcode descriptions</h3>
 167
 168     <dl>
 169       <dt>Void Nop()</dt>
 170       <dd>The empty value.  Instead of removing Values from basic blocks, most optimizations
 171         convert them to Nops.  Various phases run fix-up where all Nops are removed in one pass.
 172         It's common to see Nops in intermediate versions of B3 IR during optimizations.  Nops
 173         never lead to any code being generated and they do not impede optimizations, so they are
 174         usually harmless.  You can convert a Value to a Nop by doing convertToNop().</dd>
 175
 176       <dt>T Identity(T)</dt>
 177       <dd>Returns the passed value.  May be used for any type except Void.  Instead of replacing
 178         all uses of a Value with a different Value, most optimizations convert them to Identity.
 179         Various phases run fix-up where all uses of Identity are replaced with the Identity's
 180         child (transitively, so Identity(Identity(Identity(@x))) is changed to just @x).  Even
 181         the instruction selector "sees through" Identity.  You can remove all references to
 182         Identity in any value by calling Value::performSubstitution().  You can convert a Value
 183         to an Identity by doing convertToIdentity(otherValue).  If the value is Void,
 184         convertToIdentity() converts it to a Nop instead.</dd>
 185
 186       <dt>Int32 Const32(constant)</dt>
 187       <dd>32-bit integer constant.  Must use the Const32Value class, which has space for the
 188         int32_t constant.</dd>
 189
 190       <dt>Int64 Const64(constant)</dt>
 191       <dd>64-bit integer constant.  Must use the Const64Value class, which has space for the
 192         int64_t constant.</dd>
 193
 194       <dt>Float ConstFloat(constant)</dt>
 195       <dd>Float constant.  Must use the ConstFloatValue class, which has space for the float constant.</dd>
 196
 197       <dt>Double ConstDouble(constant)</dt>
 198       <dd>Double constant.  Must use the ConstDoubleValue class, which has space for the double constant.</dd>
 199
 200       <dt>Void Set(value, variable)</dt>
 201       <dd>Assigns the given value to the given Variable. Must use the VariableValue class.</dd>
 202
 203       <dt>T Get(variable)</dt>
 204       <dd>Returns the current value of the given Variable. Its return type depends on the
 205         variable. Must use the VariableValue class.</dd>
 206
 207       <dt>IntPtr SlotBase(stackSlot)</dt>
 208       <dd>Returns a pointer to the base of the given stack slot.  Must use the SlotBaseValue
 209         class.</dd>
 210
 211       <dt>IntPtr|Double ArgumentReg(%register)</dt>
 212       <dd>Returns the value that the given register had at the prologue of the procedure.  It
 213         returns IntPtr for general-purpose registers and Double for FPRs.  Must use the
 214         ArgumentRegValue class.</dd>
 215
 216       <dt>IntPtr FramePointer()</dt>
 217       <dd>Returns the value of the frame pointer register.  B3 procedures alway use a frame
 218         pointer ABI, and the frame pointer is always guaranteed to have this value anywhere
 219         inside the procedure.</dd>
 220
 221       <dt>T Add(T, T)</dt>
 222       <dd>Works with any type except Void.  For integer types, this represents addition with
 223         wrap-around semantics.  For floating point types, this represents addition according to
 224         the IEEE 854 spec.  B3 does not have any notion of "fast math".  A transformation over
 225         floating point code is valid if the new code produces exactly the same value, bit for
 226         bit.</dd>
 227
 228       <dt>T Sub(T, T)</dt>
 229       <dd>Works with any type except Void.  For integer types, this represents subtraction with
 230         wrap-around semantics.  For floating point types, this represents subtraction according
 231         to the IEEE 854 spec.</dd>
 232
 233       <dt>T Mul(T, T)</dt>
 234       <dd>Works with any type except Void.  For integer types, this represents multiplication
 235         with wrap-around semantics.  For floating point types, this represents multiplication
 236         according to the IEEE 854 spec.</dd>
 237
 238       <dt>T Div(T, T)</dt>
 239       <dd>
 240         <p>Works with any type except Void.  For integer types, this represents signed
 241           division with round-to-zero.  By default, its behavior is undefined for x/0 or
 242           -2<sup>31</sup>/-1.  For floating point types, this represents division according
 243           to the IEEE 854 spec.</p>
 244         <p>Integer Div may have the Chill flag set. You can create a Chill Div by saying
 245           <code>chill(Div)</code> instead of <code>Div</code>; the former creates a Kind
 246           that has Div as the opcode and has the Chill bit set. An operation is said to be
 247           chill if it returns a sensible value whenever its non-chill form would have had
 248           undefined behavior. Chill Div turns x/0 into 0 and -2<sup>31</sup>/-1 into
 249           -2<sup>31</sup>. We recognize this in IR because it's exactly the semantics of
 250           division on ARM64, and it's also exactly the semantics that JavaScript wants for
 251           "(x/y)|0".</p>
 252       </dd>
 253
 254       <dt>T Mod(T, T)</dt>
 255       <dd>
 256         <p>Works with any type except Void.  For integer types, this represents signed
 257           modulo. By default, its behavior is undefined for x%0 or -2<sup>31</sup>%-1.  For
 258           floating point types, this represents modulo according to "fmod()".</p>
 259         <p>Integer Mod may have the Chill flag set. You can create a Chill Mod by saying
 260           <code>chill(Mod)</code>. Chill Mod turns x%0 into 0 and -2<sup>31</sup>%-1 into
 261           0.</p>
 262       </dd>
 263
 264       <dt>T Neg(T)</dt>
 265       <dd>Works with any type except Void.  For integer types, this represents twos-complement
 266         negation.  For floating point types, this represents negation according to the IEEE
 267         spec.</dd>
 268
 269       <dt>T BitAnd(T, T)</dt>
 270       <dd>Bitwise and.  Valid for Int32 and Int64.</dd>
 271
 272       <dt>T BitOr(T, T)</dt>
 273       <dd>Bitwise or.  Valid for Int32 and Int64.</dd>
 274
 275       <dt>T BitXor(T, T)</dt>
 276       <dd>Bitwise xor.  Valid for Int32 and Int64.</dd>
 277
 278       <dt>T Shl(T, Int32)</dt>
 279       <dd>Shift left.  Valid for Int32 and Int64.  The shift amount is always Int32.  Only the
 280         low 31 bits of the shift amount are used for Int32.  Only the low 63 bits of the shift
 281         amount are used for Int64.</dd>
 282
 283       <dt>T SShr(T, Int32)</dt>
 284       <dd>Shift right with sign extension.  Valid for Int32 and Int64.  The shift amount is
 285         always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
 286         low 63 bits of the shift amount are used for Int64.</dd>
 287
 288       <dt>T ZShr(T, Int32)</dt>
 289       <dd>Shift right with zero extension.  Valid for Int32 and Int64.  The shift amount is
 290         always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
 291         low 63 bits of the shift amount are used for Int64.</dd>
 292
 293       <dt>T Clz(T)</dt>
 294       <dd>Count leading zeroes.  Valid for Int32 and Int64.</dd>
 295
 296       <dt>T Abs(T)</dt>
 297       <dd>Absolute value.  Valid for Float and Double.</dd>
 298
 299       <dt>T Ceil(T)</dt>
 300       <dd>Ceiling.  Valid for Float and Double.</dd>
 301
 302       <dt>T Floor(T)</dt>
 303       <dd>Flooring.  Valid for Float and Double.</dd>
 304
 305       <dt>T Sqrt(T)</dt>
 306       <dd>Square root.  Valid for Float and Double.</dd>
 307
 308       <dt>U BitwiseCast(T)</dt>
 309       <dd>If T is Int32 or Int64, it returns the bitwise-corresponding Float or Double,
 310         respectively.  If T is Float or Double, it returns the bitwise-corresponding Int32 or
 311         Int64, respectively.</dd>
 312
 313       <dt>Int32 SExt8(Int32)</dt>
 314       <dd>Fills the top 24 bits of the integer with the low byte's sign extension.</dd>
 315
 316       <dt>Int32 SExt16(Int32)</dt>
 317       <dd>Fills the top 16 bits of the integer with the low short's sign extension.</dd>
 318
 319       <dt>Int64 SExt32(Int32)</dt>
 320       <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
 321         high 32 bits are its sign extension.</dd>
 322
 323       <dt>Int64 ZExt32(Int32)</dt>
 324       <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
 325         high 32 bits are zero.</dd>
 326
 327       <dt>Int32 Trunc(Int64)</dt>
 328       <dd>Returns the low 32 bits of the 64-bit value.</dd>
 329
 330       <dt>Double IToD(T)</dt>
 331       <dd>Converts the given integer into a double.  Value for Int32 or Int64 inputs.</dd>
 332
 333       <dt>Double FloatToDouble(Float)</dt>
 334       <dd>Converts the given float into a double.</dd>
 335
 336       <dt>Float DoubleToFloat(Double)</dt>
 337       <dd>Converts the given double into a float.</dd>
 338
 339       <dt>Int32 Equal(T, T)</dt>
 340       <dd>Compares the two values.  If they are equal, return 1; else return 0.  Valid for all
 341         types except Void.  Integer comparisons simply compare all bits.  Floating point
 342         comparisons mostly compare bits, but have some corner cases: positive zero and negative
 343         zero are considered equal, and they return false when either value is NaN.</dd>
 344
 345       <dt>Int32 NotEqual(T, T)</dt>
 346       <dd>The opposite of Equal().  NotEqual(@x, @y) yields the same result as BitXor(Equal(@x,
 347         @y), 1).</dd>
 348
 349       <dt>Int32 LessThan(T, T)</dt>
 350       <dd>Returns 1 if the left value is less than the right one, 0 otherwise.  Does a signed
 351         comparison for integers.  For floating point comparisons, this has the usual caveats
 352         with respect to negative zero and NaN.</dd>
 353
 354       <dt>Int32 GreaterThan(T, T)</dt>
 355       <dd>Returns 1 if the left value is greater than the right one, 0 otherwise.  Does a signed
 356         comparison for integers.  For floating point comparisons, this has the usual caveats
 357         with respect to negative zero and NaN.</dd>
 358
 359       <dt>Int32 LessEqual(T, T)</dt>
 360       <dd>Returns 1 if the left value is less than or equal to the right one, 0 otherwise.  Does
 361         a signed comparison for integers.  For floating point comparisons, this has the usual
 362         caveats with respect to negative zero and NaN.</dd>
 363
 364       <dt>Int32 GreaterEqual(T, T)</dt>
 365       <dd>Returns 1 if the left value is greater than or equal to the right one, 0 otherwise.
 366         Does a signed comparison for integers.  For floating point comparisons, this has the
 367         usual caveats with respect to negative zero and NaN.</dd>
 368
 369       <dt>Int32 Above(T, T)</dt>
 370       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 371         value is unsigned-greater-than the right one, 0 otherwise.</dd>
 372
 373       <dt>Int32 Below(T, T)</dt>
 374       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 375         value is unsigned-less-than the right one, 0 otherwise.</dd>
 376
 377       <dt>Int32 AboveEqual(T, T)</dt>
 378       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 379         value is unsigned-greater-than-or-equal the right one, 0 otherwise.</dd>
 380
 381       <dt>Int32 BelowEqual(T, T)</dt>
 382       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 383         value is unsigned-less-than-or-equal the right one, 0 otherwise.</dd>
 384
 385       <dt>Int32 EqualOrUnordered(T, T)</dt>
 386       <dd>Floating point comparison, valid for Float and Double only.  Returns 1 if the left
 387         value is equal to the right one or if either value is NaN.  Returns 0 otherwise.</dd>
 388
 389       <dt>T Select(U, T, T)</dt>
 390       <dd>Returns either the second child or the third child.  T can be any type except Void.  U
 391         can be either Int32 or Int64.  If the first child is non-zero, returns the second child.
 392         Otherwise returns the third child.</dd>
 393
 394       <dt>Int32 Load8Z(IntPtr, offset)</dt>
 395       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
 396         signed integer offset to the child value.  Zero extends the loaded byte, so the high 24
 397         bits are all zero.  Must use the MemoryValue class.</dd>
 398
 399       <dt>Int32 Load8S(IntPtr, offset)</dt>
 400       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
 401         signed integer offset to the child value.  Sign extends the loaded byte.  Must use the
 402         MemoryValue class.</dd>
 403
 404       <dt>Int32 Load16Z(IntPtr, offset)</dt>
 405       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
 406         32-bit signed integer offset to the child value.  Zero extends the loaded 16-bit
 407         integer, so the high 16 bits are all zero.  Misaligned loads are not penalized.  Must
 408         use the MemoryValue class.</dd>
 409
 410       <dt>Int32 Load16S(IntPtr, offset)</dt>
 411       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
 412         32-bit signed integer offset to the child value.  Sign extends the loaded 16-bit
 413         integer.  Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
 414
 415       <dt>T Load(IntPtr, offset)</dt>
 416       <dd>Valid for any type except Void.  Loads a value of that type from the address, which is
 417         computed by adding the compile-time 32-bit signed integer offset to the child value.
 418         Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
 419
 420       <dt>Void Store8(Int32, IntPtr, offset)</dt>
 421       <dd>Stores a the low byte of the first child into the address computed by adding the
 422         compile-time 32-bit signed integer offset to the second child.  Must use the MemoryValue
 423         class.</dd>
 424
 425       <dt>Void Store16(Int32, IntPtr, offset)</dt>
 426       <dd>Stores a the low 16 bits of the first child into the address computed by adding the
 427         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
 428         not penalized.  Must use the MemoryValue class.</dd>
 429
 430       <dt>Void Store(T, IntPtr, offset)</dt>
 431       <dd>Stores the value in the first child into the address computed by adding the
 432         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
 433         not penalized.  Must use the MemoryValue class.</dd>
 434
 435       <dt>Void Fence()</dt>
 436       <dd>Abstracts standalone data fences on x86 and ARM. Must use the FenceValue class, which has
 437         two additional members that configure the precise meaning of the fence:
 438         <code>HeapRange FenceValue::read</code> and <code>HeapRange FenceValue::write</code>. If the
 439         <code>write</code> range is empty, this is taken to be a store-store fence, which leads to
 440         no code generation on x86 and the weaker <code>dmb ishst</code> fence on ARM. If the write
 441         range is non-empty, this produces <code>mfence</code> on x86 and <code>dmb ish</code> on
 442         ARM. Within B3 IR, the Fence also reports the read/write in its effects. This allows you to
 443         scope the fence for the purpose of B3's load elimination. For example, you may use a Fence
 444         to protect a store from being sunk below a specific load. In that case, you can claim to
 445         read just that store's range and write that load's range.</dd>
 446
 447       <dt>T1 CCall(IntPtr, [T2, [T3, ...]])</dt>
 448       <dd>Performs a C function call to the function pointed to by the first child.  The types
 449         that the function takes and the type that it returns are determined by the types of the
 450         children and the type of the CCallValue.  Only the first child is mandatory.  Must use
 451         the CCallValue class.</dd>
 452
 453       <dt>T1 Patchpoint([T2, [T3, ...]])</dt>
 454       <dd>
 455         <p>A Patchpoint is a customizable value.  Patchpoints take zero or more values of any
 456           type and return any type.  A Patchpoint's behavior is determined by the generator
 457           object.  The generator is a C++ lambda that gets called during code generation.  It gets
 458           passed an assembler instance (specifically, CCallHelpers&) and an object describing
 459           where to find all of the input values and where to put the result.  Here's an example:</p>
 460
 461         <pre><code>PatchpointValue* patchpoint = block->appendNew&lt;PatchpointValue&gt;(proc, Int32, Origin());
 462 patchpoint->append(ConstrainedValue(arg1, ValueRep::SomeRegister));
 463 patchpoint->append(ConstrainedValue(arg2, ValueRep::SomeRegister));
 464 patchpoint->setGenerator(
 465     [&] (CCallHelpers& jit, const StackmapGenerationParams& params) {
 466         jit.add32(params[1].gpr(), params[2].gpr(), params[0].gpr());
 467     });</code></pre>
 468
 469         <p>This creates a patchpoint that just adds two numbers. The patchpoint is set to return
 470           Int32.  The two child values, arg1 and arg2, are passed to the patchpoint with the
 471           SomeRegister constraint, which just requests that they get put in appropriate
 472           registers (GPR for integer values, FPR for floating point values).  The generator uses
 473           the params object to figure out which registers the inputs are in (params[1] and
 474           params[2]) and which register to put the result in (params[0]).  Many sophisticated
 475           constraints are possible.  You can request that a child gets placed in a specific
 476           register.  You can list additional registers that are
 477           clobbered - either at the top of the patchpoint (i.e. early) so that the clobbered
 478           registers interfere with the inputs, or at the bottom of the patchpoint (i.e. late) so
 479           that the clobbered registers interfere with the output.  Patchpoint constraints also
 480           allow you to force values onto the call argument area of the stack.  Patchpoints are
 481           powerful enough to implement custom calling conventions, inline caches, and
 482           side-exits.</p>
 483
 484         <p>A patchpoint is allowed to "side exit", i.e. abruptly exit from the procedure.  If it
 485           wants to do so by returning, it can use Procedure's API for getting the callee-save
 486           register layout, unwinding the callee-saves, and then returning.  More likely, the
 487           patchpoint will take some exit state as part of its arguments, and it will manipulate
 488           the call frame in place to make it look like another execution engine's call frame.
 489           This is called OSR, and JavaScriptCore does it a lot.</p>
 490
 491         <p>A patchpoint can be used as a terminal. Simply set the <code>terminal</code> bit:</p>
 492
 493         <pre><code>patchpoint-&gt;effects.terminal = true;</code></pre>
 494
 495         <p>The generator can determine where to branch by using the StackmapGenerationParams to
 496           get the set of labels for all successors. You're guaranteed that the number of
 497           successors of the patchpoint's basic block will be the same as when you created it.
 498           However, like any value, a patchpoint may be cloned. This means, for example, that if
 499           you use this to implement a table jump then the jump table must be created inside the
 500           generator, so that you get one jump table per clone.</p>
 501
 502         <p>Must use the PatchpointValue class with the Patchpoint opcode.</p>
 503       </dd>
 504
 505       <dt>T CheckAdd(T, T, [T2, [T3, ...]])</dt>
 506       <dd>Checked integer addition.  Works for T = Int32 or T = Int64.  First first two children
 507         are mandatory.  Additional children are optional.  All of the Check instructions take a
 508         generator and value constraints like a Patchpoint.  In the case of a CheckAdd, the
 509         generator runs on the path where the integer addition overflowed.  B3 assumes that
 510         CheckAdd will side-exit upon overflow, so the generator must do some kind of
 511         termination.  Usually, this is used to implement OSR exits on integer overflow and the
 512         optional arguments to CheckAdd will be the OSR exit state.  Must use the CheckValue
 513         class.</dd>
 514
 515       <dt>T CheckSub(T, T, [T2, [T3, ...]])</dt>
 516       <dd>Checked integer subtraction.  Works for T = Int32 or T = Int64.  First first two
 517         children are mandatory.  Additional children are optional.  All of the Check
 518         instructions take a generator and value constraints like a Patchpoint.  In the case of a
 519         CheckSub, the generator runs on the path where the integer subtraction overflowed.  B3
 520         assumes that CheckSub will side-exit upon overflow, so the generator must do some kind
 521         of termination.  Usually, this is used to implement OSR exits on integer overflow and
 522         the optional arguments to CheckSub will be the OSR exit state.  You can use CheckSub for
 523         checked negation by using zero for the first child.  B3 will select the native negate
 524         instruction when you do this.  Must use the CheckValue class.</dd>
 525
 526       <dt>T CheckMul(T, T, [T2, [T3, ...]])</dt>
 527       <dd>Checked integer multiplication.  Works for T = Int32 or T = Int64.  First first two
 528         children are mandatory.  Additional children are optional.  All of the Check
 529         instructions take a generator and value constraints like a Patchpoint.  In the case of a
 530         CheckMul, the generator runs on the path where the integer multiplication overflowed.
 531         B3 assumes that CheckMul will side-exit upon overflow, so the generator must do some
 532         kind of termination.  Usually, this is used to implement OSR exits on integer overflow
 533         and the optional arguments to CheckMul will be the OSR exit state.  Must use the
 534         CheckValue class.</dd>
 535
 536       <dt>Void Check(T, [T2, [T3, ...]])</dt>
 537       <dd>Exit check.  Works for T = Int32 or T = Int64.  This branches on the first child.  If
 538         the first child is zero, this just falls through.  If it's non-zero, it goes to the exit
 539         path generated by the passed generator.  Only the first child is mandatory.  B3 assumes
 540         that Check will side-exit when the first child is non-zero, so the generator must do
 541         some kind of termination.  Usually, this is used to implement OSR exit checks and the
 542         optional arguments to Check will be the OSR exit state.  Check supports efficient
 543         compare/branch fusion, so you can Check for fairly sophisticated predicates.  For
 544         example, Check(Equal(LessThan(@a, @b), 0)) where @a and @b are doubles will be generated
 545         to an instruction that branches to the exit if @a &gt;= @b or if either @a or @b are
 546         NaN.  Must use the CheckValue class.</dd>
 547
 548       <dt>Void Upsilon(T, ^phi)</dt>
 549       <dd>B3 uses SSA.  SSA requires that each variable gets assigned to only once anywhere in
 550         the procedure.  But that doesn't work if you have a variable that is supposed to be the
 551         result of merging two values along control flow.  B3 uses Phi values to represent value
 552         merges, just like SSA compilers usually do.  But while other SSA compilers represent the
 553         inputs to the Phi by listing the control flow edges from which the Phi gets its values,
 554         B3 uses the Upsilon value.  Each Phi behaves as if it has a memory location associated
 555         with it.  Executing the Phi behaves like a load from that memory location.
 556         Upsilon(@value, ^phi) behaves like a store of @value into the memory location associated
 557         with @phi.  We say "^phi" when we mean that we are writing to the memory location
 558         associated with the Phi.  Must use the UpsilonValue class.</dd>
 559
 560       <dt>T Phi()</dt>
 561       <dd>Works for any type except Void.  Represents a local memory location large enough to
 562         hold T.  Loads from that memory location.  The only way to store to that location is
 563         with Upsilon.</dd>
 564
 565       <dt>Void Jump(takenBlock)</dt>
 566       <dd>Jumps to takenBlock.  This must appear at the end of the basic block. The basic block
 567         must have exactly one successor.</dd>
 568
 569       <dt>Void Branch(T, takenBlock, notTakenBlock)</dt>
 570       <dd>Works for T = Int32 or T = Int64.  Branches on the child.  If the child is non-zero,
 571         it branches to the takenBlock.  Otherwise it branches to the notTakenBlock.  Must appear
 572         at the end of the basic block. The block must have exactly two successors.</dd>
 573
 574       <dt>Void Switch(T, cases...)</dt>
 575       <dd>Works for T = Int32 or T = Int64.  Switches on the child.  Contains a list of switch
 576         cases.  Each switch case has an integer constant and a target block.  The switch value
 577         also contains a fall-through target in case the child has a value that wasn't mentioned
 578         in the cases list.  Must use the SwitchValue class.  Must appear at the end of the basic
 579         block. The block must have one successor for each case, plus a successor for the
 580         fall-through (default) case. You can manage the successors of a block containing a Switch
 581         using API in SwitchValue, like SwitchValue::appendCase() and
 582         SwitchValue::setFallThrough().</dd>
 583
 584       <dt>Void EntrySwitch()</dt>
 585       <dd>
 586         <p>B3 supports multiple procedure entrypoints. The way you create multiple entrypoints is
 587           by placing an EntrySwitch at the end of the root block. The root block must then have a
 588           successor for each entrypoint. Additionally, you must tell the Procedure how many
 589           entrypoints you want. For example:</p>
 590         <pre><code>Procedure proc;
 591 proc.setNumEntrypoints(3);
 592 BasicBlock* root = proc.addBlock();
 593 BasicBlock* firstEntrypoint = proc.addBlock();
 594 BasicBlock* secondEntrypoint = proc.addBlock();
 595 BasicBlock* thirdEntrypoint = proc.addBlock();
 596 root->appendNew&lt;Value&gt;(proc, EntrySwitch, Origin());
 597 root->appendSuccessor(firstEntrypoint);
 598 root->appendSuccessor(secondEntrypoint);
 599 root->appendSuccessor(thirdEntrypoint);</code></pre>
 600         <p>This is the canonical way to use EntrySwitch, however the semantics are flexible enough
 601           to allow its use anywhere in the control flow graph. You can have an arbitrary number of
 602           EntrySwitches. This flexibility ensures that EntrySwitch works even when B3 does
 603           transformations that move code above the EntrySwitch, duplicate the EntrySwitch itself,
 604           or do any number of other unexpected things.</p>
 605         <p>EntrySwitch behaves as if each Procedure has a variable called Entry. Each physical
 606           entrypoint sets Entry to the index of that entrypoint (so 0, 1, or 2, above) and jumps to
 607           the root block. EntrySwitch is just a switch on the Entry variable. Transformations over
 608           code that uses EntrySwitch are valid so long as they don't change the procedure's
 609           behavior under these semantics.</p>
 610         <p>EntrySwitch is implemented without any actual variables or switching. Instead, all code
 611           that lies on some path from the root block to some EntrySwitch is cloned for each
 612           entrypoint. This lowering is done as a very late phase in Air, so most of the compiler
 613           does not have to know anything about entrypoints. Most of the compiler treats EntrySwitch
 614           as an opaque control flow construct. EntrySwitch lowering is allowed to clone an
 615           arbitrary amount of code. However, normal uses of EntrySwitch will place it at the end of
 616           an empty root block and B3 will only hoist a handful of things above EntrySwitch. This
 617           leads to only a small amount of cloned code in practice.</p>
 618       </dd>
 619
 620       <dt>Void Return(T <i>(optional)</i>)</dt>
 621       <dd>
 622           <p>
 623             Returns the control flow to the caller and terminates the procedure.
 624             Must appear at the end of the basic block. The block must have zero successors.
 625           </p>
 626           <p>
 627             If the node has a child, its value is returned. The type of the child can be any type except Void.
 628           </p>
 629       </dd>
 630
 631       <dt>Void Oops()</dt>
 632       <dd>Indicates unreachable code.  This may be implemented as either a trap or as a bare
 633         fall-through, since B3 is allowed to assume that this will never be reached.  Must appear
 634         at the end of the basic block.  The block must have zero successors. Note that we also use
 635         the Oops opcode to mean "no such opcode" in some B3 transformations.</dd>
 636     </dl>
 637
 638   </div>
 639 </body>
 640 </html>
 641