Unreviewed build fix; use ASSERT_UNUSED rather than ASSERT to fix release builds.
[WebKit-https.git] / Websites / webkit.org / docs / b3 / assembly-intermediate-representation.html
1 <html>
2 <head>
3   <title>Assembly 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> / Assembly Intermediate Representation</h1>
17     <p>The B3 compiler comprises two intermediate representations: a higher-level
18       <a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">SSA</a>-based
19       representation called <a href="intermediate-representation.html">B3 IR</a> and a lower-level
20       representation that focuses of machine details, like registers. This lower-level form is called
21       Air (Assembly Intermediate Representation).</p>
22     
23     <p>Air programs are represented using a
24       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirCode.h"><code>Air::Code</code></a>
25       object. <code>Code</code> comprises an array of
26       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h">basic
27         blocks</a>. Each basic block comprises an array of
28       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirInst.h"><code>Inst</code></a>s.
29       Air has an explicit control flow graph: each basic block has predecessor and successor blocks.
30       Execution always begins at the first basic block (<code>code[0]</code>). The <code>Inst</code>s
31       in each block are executed in order. Each <code>Inst</code> has an opcode, an array of
32       arguments
33       (<a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirArg.h"><code>Arg</code></a>s),
34       and an origin. The origin is simply a B3 IR
35       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Value.h"><code>Value</code></a>.
36       Some opcodes use the origin for additional meta-data. This works because Air code always
37       coexists with the B3 procedure from which it was generated.</p>
38     
39     <p>This document begins by describing the philosophy of Air. The behavior of <code>Arg</code>s is
40       central to Air's execution model, which is described in the section that follows. The last
41       section describes the way Air opcodes are defined.</p>
42     
43     <h2>Philosophy of Air</h2>
44     
45     <p>B3 is designed to be portable to many kinds of CPUs. Currently, it supports x86-64 and ARM64,
46       which are quite different from each other. In B3 IR, we expose very few instruction set
47       details. Most clients only have to worry about the pointer type varying between Int32 and
48       Int64. It's a goal of B3 IR to ensure that B3 values behave the same way except when the
49       alternative would be prohibitive (like with pointer size or the corner-case behaviors of
50       division). But to effectively compile code to different CPUs, the compiler has to eventually
51       make instruction set details explicit. This is where Air comes in. B3 locks in most
52       CPU-specific details at the moment of conversion to Air, and the Air code is irreversibly tied
53       to some specific CPU.</p>
54     
55     <p>Air is an instruction <i>superset</i>: it recognizes all of the instructions from all CPUs
56       that Air may target. In its lowest-level form, Air is simply a way of describing an assembly
57       instruction sequence, and this includes CPU concepts like registers and direct accesses to the
58       stack. Air also has a higher-level form in which the assembly has not yet undergone register
59       or stack allocation. Therefore, Air also supports abstract registers (called
60       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirTmp.h"><code>Tmp</code></a>s)
61       and abstract
62       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirStackSlot.h">stack
63         slots</a>.</p>
64     
65     <h3>Air as an Instruction Superset</h3>
66     <p>It is possible to speak of an x86-64 instruction while compiling for ARM64,
67       for example. Clients of Air, such as the B3 to Air lowering phase, are allowed to pick with any
68       Air opcode and ask if that opcode would be valid on the current CPU. They are also allowed to
69       check if specific forms of any given opcode are valid. This allows clients to optimize for
70       multiple instruction sets by cascading through the possible opcodes that they know of, starting
71       with the one they think is most efficient. Some of those opcodes may only be available on one
72       CPU while others are available everywhere.</p>
73     
74     <p>Air opcodes support overloading. For example, the Add32 opcode has both two-operand and
75       three-operand overloads, and those overloads have multiple forms: the first operand may or
76       may not be an immediate and depending on the CPU, some of the other operands may or may not
77       be memory addresses. A fundamental Air operation is <code>Inst::isValidForm()</code>, which
78       tells the client if the instruction's current form is valid on the current CPU. This may
79       return false either because the Inst is not well-formed for any CPU or because it is not
80       valid for the current CPU even though it may be valid on some other CPU. This allows clients
81       to generate Air by experimenting with various different instruction forms before settling on
82       the one that the current CPU supports.</p>
83     
84     <h3>Air as a High-Level Assembly</h3>
85     <p>Air doesn't require the client to perform register or stack allocation. Anywhere that Air
86       accepts a register it will also accept a <code>Tmp</code>. Anywhere that Air accepts an address
87       it will also accept a stack slot reference. Air code generation comprises a register allocator
88       and a stack allocator, which turn <code>Tmp</code>s into <code>Reg</code>s and stack slots into
89       addresses with the frame pointer (or stack pointer) as the base and some integer offset. Air
90       allows clients to speak of registers directly even while also using <code>Tmp</code>s, and the
91       register allocator will ensure that it avoids clobbering registers that the client code already
92       relies upon. This is possible because Air has precise modeling of how instructions use
93       registers, so it's always possible to determine which registers are live at any point in the
94       Air code.</p>
95     
96     <p>Air's philosophy allows B3 to use it for converting high-level, CPU-agnostic SSA procedures
97       into code for the current CPU. Air is an instruction superset that allows clients to consider
98       all available instructions on all possible CPUs and query which forms of those instructions are
99       available on the current CPU. Air also supports for high-level concepts like <code>Tmp</code>s
100       and stack slots, which allows B3 to Air lowering to focus on which instructions to use without
101       worrying about register allocation or stack layout.</p>
102     
103     <h2>Args and the Air Execution Model</h2>
104     <p>Air can be thought of as an
105       <a href="https://en.wikipedia.org/wiki/Orthogonal_instruction_set">orthogonal instruction
106         set</a>. It's possible to construct an <code>Inst</code> with any combination of opcode and
107       arguments. The opcode determines what Air will do to the arguments - it may read from them or
108       write to them, for example. Orthognality implies that any argument that is read may be either
109       a register (or <code>Tmp</code>), an address, or an immediate; while any argument that is
110       written may be either a register or an address. Air constraints orthognality where the target
111       CPU would. For example, none of Air's target CPUs would support an <code>Add32</code>
112       instruction that loads its sources from memory <i>and</i> stores its result into memory. Even
113       x86 doesn't go that far. Either before or after creating an <code>Inst</code>, the client can
114       query if a particular combination of arguments (for example, three memory addresses) would be
115       valid for a given opcode (for example, <code>Add32</code>).</p>
116     
117     <p>Air arguments are represented using the <code>Arg</code> object. <code>Arg</code> can
118       represent any of the following assembly operands:</p>
119     
120     <dl>
121       <dt>Tmp</dt>
122       <dd>A <code>Tmp</code> represents either a register or a temporary.</dd>
123       
124       <dt>Imm, BigImm, BitImm, and BitImm64</dt>
125       <dd>These are various kinds of immediates. We distinguish between big and small immediates
126         because some instructions only allow immediates within a certain range. We distinguish
127         between immediates for bit operations and immediates for all other operations because ARM
128         has different constraints on the values of immediates depending on whether they are used for
129         bit math.</dd>
130       
131       <dt>Addr, Stack, CallArg, and Index</dt>
132       <dd>These are all memory addresses. Addr is a base-offset address, which uses a <code>Tmp</code>
133         for the base and an immediate for the offset. Stack and CallArg are abstract stack offsets.
134         Index is a base-index address, which has a pair of <code>Tmp</code>s (base and index) as well
135         as an offset immediate and a scaling immediate for the index.</dd>
136       
137       <dt>RelCond, ResCond, and DoubleCond</dt>
138       <dd>These are condition codes for various kinds of branches.</dd>
139       
140       <dt>Special</dt>
141       <dd>Air allows certain <code>Inst</code>s to point to additional meta-data. The Special
142         argument type is used for such meta-data. It holds a <code>Arg::Special*</code>.</dd>
143       
144       <dt>WidthArg</dt>
145       <dd>Some special Air opcodes take operands that describe the width of the operation. Possible
146         values are <code>Width8</code>, <code>Width16</code>, <code>Width32</code>, and
147         <code>Width64</code>.</dd>
148     </dl>
149     
150     <p>The opcode of an <code>Inst</code> combined with the overload - i.e. the number of arguments
151       - determines what the <code>Inst</code> will do to each argument. The behavior of arguments
152       comes down to three dimensions that are determined by the opcode and overload:</p>
153     
154     <dl>
155       <dt>Role</dt>
156       <dd>The role of an argument is an enum that describes the timing of when the argument is
157         accessed, how it's accessed (use, a.k.a. read; or def, a.k.a write), how important that
158         access is for performance (either <i>warm</i> or <i>cold</i>), and how writes affect the top
159         bits (either ignores them or zero-fills them). The timing of an argument role is discussed
160         further below. The performance requirements of an argument are used for register allocation
161         prioritization. A warm argument is counted towards the register allocation priority
162         heuristic, while a cold one isn't.</dd>
163       
164       <dt>Type</dt>
165       <dd>Air recognizes two types, <code>GP</code> (general purpose) and <code>FP</code> (floating
166         point). Arguments also have type. It's important to remember that there is both a type for
167         the argument as determined by the opcode and overload, and a type of the argument itself.
168         Some arguments are untyped, which means that they may be used regardless of the type desired
169         by the opcode/overload. For example, addresses are untyped. Other arguments have specific
170         type, like registers and <code>Tmp</code>s. Except for <code>BigImm</code>, immediates are
171         <code>GP</code>.</dd>
172       
173       <dt>Width</dt>
174       <dd>The amount of bits, starting at lowest-order, that the instruction affects. Possible values
175         are <code>Width8</code>, <code>Width16</code>, <code>Width32</code>, and
176         <code>Width64</code>.</dd>
177     </dl>
178     
179     <p>The timing of an argument role is important, and brings us to the order of execution of an
180       <code>Inst</code>. Each <code>Inst</code> can be thought of as executing three
181       steps:</p>
182     
183     <ol>
184       <li>Perform <i>early</i> actions.</li>
185       <li>Perform <i>primary</i> actions.</li>
186       <li>Perform <i>late</i> actions.</li>
187     </ol>
188     
189     <p>Note that the early actions of one instruction happen immediately after the late actions of
190       the instruction before it. However, many Air analyses view them as happening at the same time.
191       For example, any register usage in the early action of one instruction interfere with the
192       register usage in the late action of the instruction that came before it. All of Air's
193       liveness and interference analyses reason about the
194       <a href="https://en.wikipedia.org/wiki/Off-by-one_error#Fencepost_error"><i>fence posts</i></a>
195       between instructions, where the late actions of the previous instruction and the early actions
196       of the next form an interference clique.</p>
197     
198     <p>Let's consider a simple example, like <code>Add32</code> with two arguments. Let's say that
199       the first argument is a memory location and the second argument is a register. Air uses the
200       <a href="https://en.wikipedia.org/wiki/X86_assembly_language#Syntax">AT&amp;T style</a> of
201       placing the destination argument last for most instructions. This Add32 loads from memory and
202       adds the value to the register. Air writes this as:</p>
203     
204     <pre><code>Add32 42(%rax), %rcx</code></pre>
205     
206     <p>This instruction will proceed in three steps:</p>
207     
208     <ol>
209       <li>Load the value at offset 42 from the memory address in <code>%rax</code>. The result is
210         stored in an internal, hidden CPU location for the remainder of execution. Even if the
211         instruction later stores to memory and overwrites this value, <code>Add32</code> will still
212         use the original value it had loaded. We say that this is an <i>early use</i>. At the same
213         time, the CPU will load the value of <code>%rcx</code> and store it in a hidden CPU
214         location. This is also an early use.</li>
215       <li>Add the two values together. Store the result in hidden CPU location.</li>
216       <li>Zero-extend the resulting value and store it into <code>%rcx</code>. This is a <i>late
217           def with zero extension</i>.</li>
218     </ol>
219     
220     <p>Therefore, the two-argument overload of <code>Add32</code> ascribes the following to its
221       arguments:</p>
222     
223     <ul>
224       <li>The roles are <i>early warm use</i> for the first argument (<code>42(%rax)</code>) and
225         <i>early warm use with late warm def with zero extension</i> for the second argument
226         (<code>%rcx</code>). Early warm use is written as <code>Use</code> for short. Early warm
227         use with late warm def with zero extension is written as <code>UseZDef</code> for
228         short.</li>
229       <li>The types of both arguments are <code>GP</code>. This matches <code>42(%rax)</code> because
230         addresses match any type. This matches <code>%rcx</code> because it's a general-purpose
231         register.</li>
232       <li>The widths of both arguments are <code>Width32</code>. Combined with <code>UseZDef</code>,
233         this means that the instruction will read the low 32 bits of <code>%rcx</code> in the early
234         actions and it will store to <i>all</i> bits of <code>%rcx</code> in the late actions, but it
235         will ensure that all but the low 32 bits are zero.</li>
236     </ul>
237     
238     <p>Air can tell you what role, type, and width is ascribed to each argument by using the
239       <code>Inst::forEachArg(func)</code> operation. It takes a callback of type
240       <code>void(Arg&, Arg::Role, Arg::Type, Arg::Width)</code>. For our <code>Add32</code> example,
241       this callback would get called twice:</p>
242     
243     <ol>
244       <li><code>func(42(%rax), Use, GP, Width32)</code></li>
245       <li><code>func(%rcx, UseZDef, GP, Width32)</code></li>
246     </ol>
247     
248     <p>Air supports exotic roles, such as late uses and early defs. There is even the
249       <code>Scratch</code> role, which means early def and late use. Speaking of a <code>Tmp</code>
250       in the <code>Scratch</code> role means that the <code>Tmp</code> will be assigned a register
251       that is guaranteed to not interfere with any of the other registers that the instruction
252       speaks of. Late uses and early defs are crucial for patchpoints, which may for example require
253       that one of the incoming values be given a register that does not interfere with whatever
254       register is used for the result. This can be expressed either as giving the inputs a late use
255       role or by giving the outputs an early def role. The full list of possible roles is:</p>
256     
257     <dl>
258       <dt>Use</dt>
259       <dd>Early warm use.</dd>
260       
261       <dt>ColdUse</dt>
262       <dd>Early cold use.</dd>
263       
264       <dt>LateUse</dt>
265       <dd>Late warm use.</dd>
266       
267       <dt>LateColdUse</dt>
268       <dd>Late cold use.</dd>
269       
270       <dt>Def</dt>
271       <dd>Late def. <i>Note that all defs are warm.</i></dd>
272       
273       <dt>ZDef</dt>
274       <dd>Late def with zero-extension.</dd>
275       
276       <dt>UseDef</dt>
277       <dd>Early warm use and late def.</dd>
278       
279       <dt>UseZDef</dt>
280       <dd>Early warm use and late def with zero extension.</dd>
281       
282       <dt>EarlyDef</dt>
283       <dd>Early def.</dd>
284       
285       <dt>Scratch</dt>
286       <dd>Early def and late warm use.</dd>
287       
288       <dt>UseAddr</dt>
289       <dd>Early warm use of the address's components.</dd>
290     </dl>
291     
292     <p><code>UseAddr</code> is interesting for the <code>Lea</code> (load effective address)
293       instruction, which evaluates the address and places the result into a temporary or register.
294       The argument must be an address, but <code>UseAddr</code> means that we don't actually read
295       from the address. Note that using an address in any of the other roles always implies that the
296       components of the address are used early and warm (i.e. <code>Use</code>).</p>
297     
298     <p>Air arguments are central to Air's execution model. The early and late actions of an
299       instruction have to do with arguments, and what happens to each argument during the early and
300       late actions is determined by the opcode and the number of arguments (i.e. the overload).
301       Clients of Air may create an <code>Inst</code> with any combination of opcode and arguments
302       and then query, using <code>Inst::isValidForm()</code> if the opcode, overload, and specific
303       arguments are valid for the current CPU.</p>
304     
305     <h2>Defining Air</h2>
306     <p>Air has many opcodes and the opcodes have many different overloads and forms. Air makes it
307       easy to reason about all of them with helpers like <code>isValidForm()</code> and
308       <code>forEachArg()</code>. It also provides a <code>Inst::generate()</code> function that will
309       generate code for the instruction, provided that it does not use any non-register
310       <code>Tmp</code>s or any abstract stack slots. If we wrote the
311       code for validating, iterating, and generating each form by hand, we would have a bad time.
312       For this reason, Air comes with an
313       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb">opcode code generator</a>
314       that uses a
315       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">opcode definition file</a>
316       as input. The opcode definition file use a simple and concise syntax that lets us define many
317       opcodes at once and constrain them to the CPU kinds that support them. Additionally, Air
318       supports <i>custom</i> opcodes, where the code generator emits calls to
319       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirCustom.h">hand-written
320         C++ code</a>. This section describes the opcode definition language.</p>
321     
322     <p>It's easiest to understand the opcode definitions with an example. Let's use the two-argument
323       overload of <code>Add32</code>.</p>
324     
325     <pre><code>Add32 U:G:32 UZD:G:32
326     Tmp, Tmp
327     x86: Imm, Addr
328     x86: Imm, Index
329     Imm, Tmp
330     x86: Addr, Tmp
331     x86: Tmp, Addr
332     x86: Tmp, Index</code></pre>
333     
334     <p>The first line defines the overload. It has two arguments. The first argument serves the
335       <code>Use</code> role, shorted as <code>U</code>. It is general-purpose, shortened as
336       <code>G</code>. It has a 32-bit width. Hence the string <code>U:G:32</code>. Similarly,
337       <code>UZD:G:32</code> means <code>UseZDef</code>, <code>GP</code>, <code>Width32</code>.</p>
338     
339     <p>The next lines list the available forms of the overload. A form is a list of possible kinds of
340       arguments. These use the same terminology for <code>Arg</code> kinds from the previous section,
341       with the caveat that <code>Addr</code> implies that <code>Addr</code>, <code>Stack</code>, or
342       <code>CallArg</code> would be accepted.</p>
343     
344     <p>Prefixing any line with <code>x86:</code> means that this form is only available on x86
345       CPUs, such as x86 or x86-64.</p>
346     
347     <p>See the header of
348       <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">AirOpcode.opcodes</a>
349       for a complete list of shorthand used by Air's opcode definition language.</p>
350     
351     <h2>Summary</h2>
352     <p>Air is designed around JavaScriptCore's existing MacroAssembler. Air has Inst objects,
353       which each describe some method call to the MacroAssembler: an Inst's opcode indicates
354       which method name to use and its args indicate the arguments to pass to that method. We
355       use code generation to create a massive switch statement that turns the reflective Insts
356       into actual calls to MacroAssembler. Consequently, we can "add" new instructions to Air
357       usually by just editing the <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">AirOpcode.opcodes</a>
358       file.</p>
359   </div>
360 </body>
361 </html>
362