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</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     <h2>Values</h2>
  69
  70     <p>Variables, and the instructions that define them, are represented using the Value object.
  71       The Value object has a return type, an opcode, and zero or more children.  Children are
  72       references to other Values.  Those values are used as input to the instruction that
  73       computes this value.</p>
  74     <p>Values also have a unique 32-bit index that is used as the name.</p>
  75
  76     <p>Example:</p>
  77
  78     <pre><code>Int32 @3 = Add(@1, @2)</code></pre>
  79
  80     <p>This represents a single Value instance.  Its index is 3.  It is an Int32.  The opcode is
  81       Add, and its children are @1 and @2.</p>
  82
  83     <p>Values may also have additional meta-data.  We use special subclasses of the B3::Value
  84       class for values that need meta-data.  For example, the Load value needs a 32-bit offset
  85       for the load.  We use the MemoryValue class for memory-accessing values, which all have
  86       such an offset.</p>
  87
  88     <h2>Stack Slot</h2>
  89
  90     <p>B3 exposes the concept of stack-allocated data and gives the client a lot of control.
  91       By default, stack slots get allocated wherever B3 chooses. It will try to pack them as
  92       much as possible. After compilation is done, you can retrieve each stack slot's location
  93       in the form of an offset from the frame pointer.</p>
  94
  95     <p>You can force stack slots to end up at a particular offset from the frame pointer, though
  96       this is very dangerous.  For example, B3 assumes that it can use the slots closest to the
  97       frame pointer for callee-saves, and currently when you force something to a particular
  98       frame pointer offset, there is no mechanism to notice that this space is also being used
  99       for callee-saves.  Therefore, we recommend not using the frame pointer offset forcing
 100       feature unless you know a lot about the ABI and you have no other choice.</p>
 101
 102     <p>Stack slots are also used for creating non-SSA variables with the intention of having B3
 103       convert them into SSA.  There are two kinds of stack slots.</p>
 104
 105     <dl>
 106       <dt>Anonymous</dt>
 107       <dd>Anonymous stack slots are used to represent local variables that aren't in SSA form.
 108         B3 is allowed to assume that nobody will store to an anonymous stack slot except through
 109         Store instructions in the B3 procedure.  B3 is allowed to assume that a Store that does
 110         not write to the entire anonymous stack slot leaves the unwritten part in an undefined
 111         state.  Usually, anonymous stack slots are allocated to have the same size as the type
 112         of variable they are being used to represent.</dd>
 113
 114       <dt>Locked</dt>
 115       <dd>These stack slots are assumed to operate "as if" they were in the heap, in the sense
 116         that the may get read or written using operations not visible in B3 IR.</dd>
 117     </dl>
 118
 119     <p>The fixSSA() phase will convert anonymous stack slots to SSA.</p>
 120
 121     <h2>Control flow</h2>
 122
 123     <p>B3 represents control flow using basic blocks.  Each basic block may have zero or more
 124       predecessors.  Each basic block may have zero or more successors.  The successors are
 125       controlled by the basic block's last Value, which must be a ControlValue instance.</p>
 126
 127     <p>Each basic block contains a Vector&lt;Value*&gt; as the contents of the block. Control
 128       flow inside the block is implicit based on the order of Values in the vector.</p>
 129
 130     <h2>Opcodes</h2>
 131
 132     <p>This section describes opcodes in the following format:</p>
 133
 134     <dl>
 135       <dt>Int32 Foo(Int64, Double)</dt>
 136       <dd>This describes an opcode named Foo that uses Int32 as its return type and takes two
 137         children - one of type Int64 and another of type Double.</dd>
 138     </dl>
 139
 140     <p>We sometimes use the wildcard type T to represent polymorphic operations, like "T Add(T,
 141       T)".  This means that the value must take two children of the same type and returns a
 142       value of that type.  We use the type IntPtr to mean either Int32, or Int64, depending on
 143       the platform.</p>
 144
 145     <h3>Opcode descriptions</h3>
 146
 147     <dl>
 148       <dt>Void Nop()</dt>
 149       <dd>The empty value.  Instead of removing Values from basic blocks, most optimizations
 150         convert them to Nops.  Various phases run fix-up where all Nops are removed in one pass.
 151         It's common to see Nops in intermediate versions of B3 IR during optimizations.  Nops
 152         never lead to any code being generated and they do not impede optimizations, so they are
 153         usually harmless.  You can convert a Value to a Nop by doing convertToNop().</dd>
 154
 155       <dt>T Identity(T)</dt>
 156       <dd>Returns the passed value.  May be used for any type except Void.  Instead of replacing
 157         all uses of a Value with a different Value, most optimizations convert them to Identity.
 158         Various phases run fix-up where all uses of Identity are replaced with the Identity's
 159         child (transitively, so Identity(Identity(Identity(@x))) is changed to just @x).  Even
 160         the instruction selector "sees through" Identity.  You can remove all references to
 161         Identity in any value by calling Value::performSubstitution().  You can convert a Value
 162         to an Identity by doing convertToIdentity(otherValue).  If the value is Void,
 163         convertToIdentity() converts it to a Nop instead.</dd>
 164
 165       <dt>Int32 Const32(constant)</dt>
 166       <dd>32-bit integer constant.  Must use the Const32Value class, which has space for the
 167         int32_t constant.</dd>
 168
 169       <dt>Int64 Const64(constant)</dt>
 170       <dd>64-bit integer constant.  Must use the Const64Value class, which has space for the
 171         int64_t constant.</dd>
 172
 173       <dt>Float ConstFloat(constant)</dt>
 174       <dd>Float constant.  Must use the ConstFloatValue class, which has space for the float constant.</dd>
 175
 176       <dt>Double ConstDouble(constant)</dt>
 177       <dd>Double constant.  Must use the ConstDoubleValue class, which has space for the double constant.</dd>
 178
 179       <dt>IntPtr SlotBase(stackSlot)</dt>
 180       <dd>Returns a pointer to the base of the given stack slot.  Must use the SlotBaseValue
 181         class.</dd>
 182
 183       <dt>IntPtr|Double ArgumentReg(%register)</dt>
 184       <dd>Returns the value that the given register had at the prologue of the procedure.  It
 185         returns IntPtr for general-purpose registers and Double for FPRs.  Must use the
 186         ArgumentRegValue class.</dd>
 187
 188       <dt>IntPtr FramePointer()</dt>
 189       <dd>Returns the value of the frame pointer register.  B3 procedures alway use a frame
 190         pointer ABI, and the frame pointer is always guaranteed to have this value anywhere
 191         inside the procedure.</dd>
 192
 193       <dt>T Add(T, T)</dt>
 194       <dd>Works with any type except Void.  For integer types, this represents addition with
 195         wrap-around semantics.  For floating point types, this represents addition according to
 196         the IEEE 854 spec.  B3 does not have any notion of "fast math".  A transformation over
 197         floating point code is valid if the new code produces exactly the same value, bit for
 198         bit.</dd>
 199
 200       <dt>T Sub(T, T)</dt>
 201       <dd>Works with any type except Void.  For integer types, this represents subtraction with
 202         wrap-around semantics.  For floating point types, this represents subtraction according
 203         to the IEEE 854 spec.</dd>
 204
 205       <dt>T Mul(T, T)</dt>
 206       <dd>Works with any type except Void.  For integer types, this represents multiplication
 207         with wrap-around semantics.  For floating point types, this represents multiplication
 208         according to the IEEE 854 spec.</dd>
 209
 210       <dt>T Div(T, T)</dt>
 211       <dd>Works with any type except Void.  For integer types, this represents signed division
 212         with round-to-zero.  Its behavior is undefined for x/0 or -2<sup>31</sup>/-1.  For floating
 213         point types, this represents division according to the IEEE 854 spec.</dd>
 214
 215       <dt>T Mod(T, T)</dt>
 216       <dd>Works with any type except Void.  For integer types, this represents signed modulo.
 217         Its behavior is undefined for x%0 or -2<sup>31</sup>%-1.  For floating point types, this
 218         represents modulo according to "fmod()".</dd>
 219
 220       <dt>T Neg(T)</dt>
 221       <dd>Works with any type except Void.  For integer types, this represents twos-complement
 222         negation.  For floating point types, this represents negation according to the IEEE
 223         spec.</dd>
 224
 225       <dt>T ChillDiv(T, T)</dt>
 226       <dd>Chill division.  Valid for Int32 and Int64.  An operation is said to be chill if it
 227         returns a sensible value whenever its non-chill form would have had undefined behavior.
 228         ChillDiv turns x/0 into 0 and -2<sup>31</sup>/-1 into -2<sup>31</sup>.  This is a separate opcode
 229         because it's exactly the semantics of division on ARM64, and it's also exactly the
 230         semantics that JavaScript wants for "(x/y)|0".</dd>
 231
 232       <dt>T ChillMod(T, T)</dt>
 233       <dd>Chill modulo.  Valid for Int32 and Int64.  ChllMod turns x%0 into 0 and
 234         -2<sup>31</sup>%-1 into 0.</dd>
 235
 236       <dt>T BitAnd(T, T)</dt>
 237       <dd>Bitwise and.  Valid for Int32 and Int64.</dd>
 238
 239       <dt>T BitOr(T, T)</dt>
 240       <dd>Bitwise or.  Valid for Int32 and Int64.</dd>
 241
 242       <dt>T BitXor(T, T)</dt>
 243       <dd>Bitwise xor.  Valid for Int32 and Int64.</dd>
 244
 245       <dt>T Shl(T, Int32)</dt>
 246       <dd>Shift left.  Valid for Int32 and Int64.  The shift amount is always Int32.  Only the
 247         low 31 bits of the shift amount are used for Int32.  Only the low 63 bits of the shift
 248         amount are used for Int64.</dd>
 249
 250       <dt>T SShr(T, Int32)</dt>
 251       <dd>Shift right with sign extension.  Valid for Int32 and Int64.  The shift amount is
 252         always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
 253         low 63 bits of the shift amount are used for Int64.</dd>
 254
 255       <dt>T ZShr(T, Int32)</dt>
 256       <dd>Shift right with zero extension.  Valid for Int32 and Int64.  The shift amount is
 257         always Int32.  Only the low 31 bits of the shift amount are used for Int32.  Only the
 258         low 63 bits of the shift amount are used for Int64.</dd>
 259
 260       <dt>T Clz(T)</dt>
 261       <dd>Count leading zeroes.  Valid for Int32 and Int64.</dd>
 262
 263       <dt>T Abs(T)</dt>
 264       <dd>Absolute value.  Valid for Float and Double.</dd>
 265
 266       <dt>T Ceil(T)</dt>
 267       <dd>Ceiling.  Valid for Float and Double.</dd>
 268
 269       <dt>T Sqrt(T)</dt>
 270       <dd>Square root.  Valid for Float and Double.</dd>
 271
 272       <dt>U BitwiseCast(T)</dt>
 273       <dd>If T is Int32 or Int64, it returns the bitwise-corresponding Float or Double,
 274         respectively.  If T is Float or Double, it returns the bitwise-corresponding Int32 or
 275         Int64, respectively.</dd>
 276
 277       <dt>Int32 SExt8(Int32)</dt>
 278       <dd>Fills the top 24 bits of the integer with the low byte's sign extension.</dd>
 279
 280       <dt>Int32 SExt16(Int32)</dt>
 281       <dd>Fills the top 16 bits of the integer with the low short's sign extension.</dd>
 282
 283       <dt>Int64 SExt32(Int32)</dt>
 284       <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
 285         high 32 bits are its sign extension.</dd>
 286
 287       <dt>Int64 ZExt32(Int32)</dt>
 288       <dd>Returns a 64-bit integer such that the low 32 bits are the given Int32 value and the
 289         high 32 bits are zero.</dd>
 290
 291       <dt>Int32 Trunc(Int64)</dt>
 292       <dd>Returns the low 32 bits of the 64-bit value.</dd>
 293
 294       <dt>Double IToD(T)</dt>
 295       <dd>Converts the given integer into a double.  Value for Int32 or Int64 inputs.</dd>
 296
 297       <dt>Double FloatToDouble(Float)</dt>
 298       <dd>Converts the given float into a double.</dd>
 299
 300       <dt>Float DoubleToFloat(Double)</dt>
 301       <dd>Converts the given double into a float.</dd>
 302
 303       <dt>Int32 Equal(T, T)</dt>
 304       <dd>Compares the two values.  If they are equal, return 1; else return 0.  Valid for all
 305         types except Void.  Integer comparisons simply compare all bits.  Floating point
 306         comparisons mostly compare bits, but have some corner cases: positive zero and negative
 307         zero are considered equal, and they return false when either value is NaN.</dd>
 308
 309       <dt>Int32 NotEqual(T, T)</dt>
 310       <dd>The opposite of Equal().  NotEqual(@x, @y) yields the same result as BitXor(Equal(@x,
 311         @y), 1).</dd>
 312
 313       <dt>Int32 LessThan(T, T)</dt>
 314       <dd>Returns 1 if the left value is less than the right one, 0 otherwise.  Does a signed
 315         comparison for integers.  For floating point comparisons, this has the usual caveats
 316         with respect to negative zero and NaN.</dd>
 317
 318       <dt>Int32 GreaterThan(T, T)</dt>
 319       <dd>Returns 1 if the left value is greater than the right one, 0 otherwise.  Does a signed
 320         comparison for integers.  For floating point comparisons, this has the usual caveats
 321         with respect to negative zero and NaN.</dd>
 322
 323       <dt>Int32 LessEqual(T, T)</dt>
 324       <dd>Returns 1 if the left value is less than or equal to the right one, 0 otherwise.  Does
 325         a signed comparison for integers.  For floating point comparisons, this has the usual
 326         caveats with respect to negative zero and NaN.</dd>
 327
 328       <dt>Int32 GreaterEqual(T, T)</dt>
 329       <dd>Returns 1 if the left value is greater than or equal to the right one, 0 otherwise.
 330         Does a signed comparison for integers.  For floating point comparisons, this has the
 331         usual caveats with respect to negative zero and NaN.</dd>
 332
 333       <dt>Int32 Above(T, T)</dt>
 334       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 335         value is unsigned-greater-than the right one, 0 otherwise.</dd>
 336
 337       <dt>Int32 Below(T, T)</dt>
 338       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 339         value is unsigned-less-than the right one, 0 otherwise.</dd>
 340
 341       <dt>Int32 AboveEqual(T, T)</dt>
 342       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 343         value is unsigned-greater-than-or-equal the right one, 0 otherwise.</dd>
 344
 345       <dt>Int32 BelowEqual(T, T)</dt>
 346       <dd>Unsigned integer comparison, valid for Int32 and Int64 only.  Returns 1 if the left
 347         value is unsigned-less-than-or-equal the right one, 0 otherwise.</dd>
 348
 349       <dt>Int32 EqualOrUnordered(T, T)</dt>
 350       <dd>Floating point comparison, valid for Float and Double only.  Returns 1 if the left
 351         value is equal to the right one or if either value is NaN.  Returns 0 otherwise.</dd>
 352
 353       <dt>T Select(U, T, T)</dt>
 354       <dd>Returns either the second child or the third child.  T can be any type except Void.  U
 355         can be either Int32 or Int64.  If the first child is non-zero, returns the second child.
 356         Otherwise returns the third child.</dd>
 357
 358       <dt>Int32 Load8Z(IntPtr, offset)</dt>
 359       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
 360         signed integer offset to the child value.  Zero extends the loaded byte, so the high 24
 361         bits are all zero.  Must use the MemoryValue class.</dd>
 362
 363       <dt>Int32 Load8S(IntPtr, offset)</dt>
 364       <dd>Loads a byte from the address, which is computed by adding the compile-time 32-bit
 365         signed integer offset to the child value.  Sign extends the loaded byte.  Must use the
 366         MemoryValue class.</dd>
 367
 368       <dt>Int32 Load16Z(IntPtr, offset)</dt>
 369       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
 370         32-bit signed integer offset to the child value.  Zero extends the loaded 16-bit
 371         integer, so the high 16 bits are all zero.  Misaligned loads are not penalized.  Must
 372         use the MemoryValue class.</dd>
 373
 374       <dt>Int32 Load16S(IntPtr, offset)</dt>
 375       <dd>Loads a 16-bit integer from the address, which is computed by adding the compile-time
 376         32-bit signed integer offset to the child value.  Sign extends the loaded 16-bit
 377         integer.  Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
 378
 379       <dt>T Load(IntPtr, offset)</dt>
 380       <dd>Valid for any type except Void.  Loads a value of that type from the address, which is
 381         computed by adding the compile-time 32-bit signed integer offset to the child value.
 382         Misaligned loads are not penalized.  Must use the MemoryValue class.</dd>
 383
 384       <dt>Void Store8(Int32, IntPtr, offset)</dt>
 385       <dd>Stores a the low byte of the first child into the address computed by adding the
 386         compile-time 32-bit signed integer offset to the second child.  Must use the MemoryValue
 387         class.</dd>
 388
 389       <dt>Void Store16(Int32, IntPtr, offset)</dt>
 390       <dd>Stores a the low 16 bits of the first child into the address computed by adding the
 391         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
 392         not penalized.  Must use the MemoryValue class.</dd>
 393
 394       <dt>Void Store(T, IntPtr, offset)</dt>
 395       <dd>Stores the value in the first child into the address computed by adding the
 396         compile-time 32-bit signed integer offset to the second child.  Misaligned stores are
 397         not penalized.  Must use the MemoryValue class.</dd>
 398
 399       <dt>T1 CCall(IntPtr, [T2, [T3, ...]])</dt>
 400       <dd>Performs a C function call to the function pointed to by the first child.  The types
 401         that the function takes and the type that it returns are determined by the types of the
 402         children and the type of the CCallValue.  Only the first child is mandatory.  Must use
 403         the CCallValue class.</dd>
 404
 405       <dt>T1 Patchpoint([T2, [T3, ...]])</dt>
 406       <dd>A Patchpoint is a customizable value.  Patchpoints take zero or more values of any
 407         type and return any type.  A Patchpoint's behavior is determined by the generator
 408         object.  The generator is a C++ lambda that gets called during code generation.  It gets
 409         passed an assembler instance (specifically, CCallHelpers&) and an object describing
 410         where to find all of the input values and where to put the result.  Here's an example:
 411
 412         <pre><code>PatchpointValue* patchpoint = block->appendNew&lt;PatchpointValue&gt;(proc, Int32, Origin());
 413 patchpoint->append(ConstrainedValue(arg1, ValueRep::SomeRegister));
 414 patchpoint->append(ConstrainedValue(arg2, ValueRep::SomeRegister));
 415 patchpoint->setGenerator(
 416     [&] (CCallHelpers& jit, const StackmapGenerationParams& params) {
 417         jit.add32(params[1].gpr(), params[2].gpr(), params[0].gpr());
 418     });</code></pre>
 419
 420         <p>This creates a patchpoint that just adds two numbers. The patchpoint is set to return
 421           Int32.  The two child values, arg1 and arg2, are passed to the patchpoint with the
 422           SomeRegister constraint, which just requests that they get put in appropriate
 423           registers (GPR for integer values, FPR for floating point values).  The generator uses
 424           the params object to figure out which registers the inputs are in (params[1] and
 425           params[2]) and which register to put the result in (params[0]).  Many sophisticated
 426           constraints are possible.  You can request that a child gets placed in a specific
 427           register.  You can list additional registers that are
 428           clobbered - either at the top of the patchpoint (i.e. early) so that the clobbered
 429           registers interfere with the inputs, or at the bottom of the patchpoint (i.e. late) so
 430           that the clobbered registers interfere with the output.  Patchpoint constraints also
 431           allow you to force values onto the call argument area of the stack.  Patchpoints are
 432           powerful enough to implement custom calling conventions, inline caches, and
 433           side-exits.</p>
 434
 435         <p>A patchpoint is allowed to "side exit", i.e. abruptly exit from the procedure.  If it
 436           wants to do so by returning, it can use Procedure's API for getting the callee-save
 437           register layout, unwinding the callee-saves, and then returning.  More likely, the
 438           patchpoint will take some exit state as part of its arguments, and it will manipulate
 439           the call frame in place to make it look like another execution engine's call frame.
 440           This is called OSR, and JavaScriptCore does it a lot.</p>
 441
 442         <p>Must use the PatchpointValue class with the Patchpoint opcode.</p>
 443       </dd>
 444
 445       <dt>T CheckAdd(T, T, [T2, [T3, ...]])</dt>
 446       <dd>Checked integer addition.  Works for T = Int32 or T = Int64.  First first two children
 447         are mandatory.  Additional children are optional.  All of the Check instructions take a
 448         generator and value constraints like a Patchpoint.  In the case of a CheckAdd, the
 449         generator runs on the path where the integer addition overflowed.  B3 assumes that
 450         CheckAdd will side-exit upon overflow, so the generator must do some kind of
 451         termination.  Usually, this is used to implement OSR exits on integer overflow and the
 452         optional arguments to CheckAdd will be the OSR exit state.  Must use the CheckValue
 453         class.</dd>
 454
 455       <dt>T CheckSub(T, T, [T2, [T3, ...]])</dt>
 456       <dd>Checked integer subtraction.  Works for T = Int32 or T = Int64.  First first two
 457         children are mandatory.  Additional children are optional.  All of the Check
 458         instructions take a generator and value constraints like a Patchpoint.  In the case of a
 459         CheckSub, the generator runs on the path where the integer subtraction overflowed.  B3
 460         assumes that CheckSub will side-exit upon overflow, so the generator must do some kind
 461         of termination.  Usually, this is used to implement OSR exits on integer overflow and
 462         the optional arguments to CheckSub will be the OSR exit state.  You can use CheckSub for
 463         checked negation by using zero for the first child.  B3 will select the native negate
 464         instruction when you do this.  Must use the CheckValue class.</dd>
 465
 466       <dt>T CheckMul(T, T, [T2, [T3, ...]])</dt>
 467       <dd>Checked integer multiplication.  Works for T = Int32 or T = Int64.  First first two
 468         children are mandatory.  Additional children are optional.  All of the Check
 469         instructions take a generator and value constraints like a Patchpoint.  In the case of a
 470         CheckMul, the generator runs on the path where the integer multiplication overflowed.
 471         B3 assumes that CheckMul will side-exit upon overflow, so the generator must do some
 472         kind of termination.  Usually, this is used to implement OSR exits on integer overflow
 473         and the optional arguments to CheckMul will be the OSR exit state.  Must use the
 474         CheckValue class.</dd>
 475
 476       <dt>Void Check(T, [T2, [T3, ...]])</dt>
 477       <dd>Exit check.  Works for T = Int32 or T = Int64.  This branches on the first child.  If
 478         the first child is zero, this just falls through.  If it's non-zero, it goes to the exit
 479         path generated by the passed generator.  Only the first child is mandatory.  B3 assumes
 480         that Check will side-exit when the first child is non-zero, so the generator must do
 481         some kind of termination.  Usually, this is used to implement OSR exit checks and the
 482         optional arguments to Check will be the OSR exit state.  Check supports efficient
 483         compare/branch fusion, so you can Check for fairly sophisticated predicates.  For
 484         example, Check(Equal(LessThan(@a, @b), 0)) where @a and @b are doubles will be generated
 485         to an instruction that branches to the exit if @a &gt;= @b or if either @a or @b are
 486         NaN.  Must use the CheckValue class.</dd>
 487
 488       <dt>Void Upsilon(T, ^phi)</dt>
 489       <dd>B3 uses SSA.  SSA requires that each variable gets assigned to only once anywhere in
 490         the procedure.  But that doesn't work if you have a variable that is supposed to be the
 491         result of merging two values along control flow.  B3 uses Phi values to represent value
 492         merges, just like SSA compilers usually do.  But while other SSA compilers represent the
 493         inputs to the Phi by listing the control flow edges from which the Phi gets its values,
 494         B3 uses the Upsilon value.  Each Phi behaves as if it has a memory location associated
 495         with it.  Executing the Phi behaves like a load from that memory location.
 496         Upsilon(@value, ^phi) behaves like a store of @value into the memory location associated
 497         with @phi.  We say "^phi" when we mean that we are writing to the memory location
 498         associated with the Phi.  Must use the UpsilonValue class.</dd>
 499
 500       <dt>T Phi()</dt>
 501       <dd>Works for any type except Void.  Represents a local memory location large enough to
 502         hold T.  Loads from that memory location.  The only way to store to that location is
 503         with Upsilon.</dd>
 504
 505       <dt>Void Jump(takenBlock)</dt>
 506       <dd>Jumps to takenBlock.  This is a ControlValue, so it must appear at the end of the
 507         basic block.</dd>
 508
 509       <dt>Void Branch(T, takenBlock, notTakenBlock)</dt>
 510       <dd>Works for T = Int32 or T = Int64.  Branches on the child.  If the child is non-zero,
 511         it branches to the takenBlock.  Otherwise it branches to the notTakenBlock.  Must use
 512         the ControlValue class.  Must appear at the end of the basic block.</dd>
 513
 514       <dt>Void Switch(T, cases...)</dt>
 515       <dd>Works for T = Int32 or T = Int64.  Switches on the child.  Contains a list of switch
 516         cases.  Each switch case has an integer constant and a target block.  The switch value
 517         also contains a fall-through target in case the child has a value that wasn't mentioned
 518         in the cases list.  Must use the SwitchValue class.  Must appear at the end of the basic
 519         block.</dd>
 520
 521       <dt>Void Return(T)</dt>
 522       <dd>Works for any type except Void.  Returns the given value and terminates the procedure.
 523         This is a ControlValue, but it must have an empty successors list.  Must appear at the
 524         end of the basic block.</dd>
 525
 526       <dt>Void Oops()</dt>
 527       <dd>Indicates unreachable code.  This may be implemented as either a trap or as a bare
 528         fall-through, since B3 is allowed to assume that this will never be reached.  This is a
 529         ControlValue, but it must have an empty successors list.  Must appear at the end of the
 530         basic block.  Note that we also use the Oops opcode to mean "no such opcode" in some B3
 531         transformations.</dd>
 532     </dl>
 533
 534   </div>
 535 </body>
 536 </html>
 537