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