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