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