Changeset 201525 in webkit
- Timestamp:
- May 31, 2016, 2:40:18 PM (10 years ago)
- Location:
- trunk/Websites/webkit.org
- Files:
-
- 2 edited
-
ChangeLog (modified) (1 diff)
-
docs/b3/assembly-intermediate-representation.html (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/Websites/webkit.org/ChangeLog
r201291 r201525 1 2016-05-31 Filip Pizlo <fpizlo@apple.com> 2 3 Air needs documentation 4 https://bugs.webkit.org/show_bug.cgi?id=153668 5 6 Reviewed by Mark Lam, Saam Barati, and Benjamin Poulain. 7 8 Write documentation for Air! 9 10 * docs/b3/assembly-intermediate-representation.html: 11 1 12 2016-05-23 Jon Davis <jond@apple.com> 2 13 -
trunk/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html
r196029 r201525 15 15 <div id="contents"> 16 16 <h1><a href="index.html">Bare Bones Backend</a> / Assembly Intermediate Representation</h1> 17 <p>The B3 compiler converts SSA procedures into efficient machine code by first converting 18 them to a form that reveals machine details, like registers. This form is called Assembly 19 Intermediate Representation, or just Air for short.</p> 20 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&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> 21 352 <p>Air is designed around JavaScriptCore's existing MacroAssembler. Air has Inst objects, 22 353 which each describe some method call to the MacroAssembler: an Inst's opcode indicates … … 26 357 usually by just editing the <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">AirOpcode.opcodes</a> 27 358 file.</p> 28 29 <p><a href="https://bugs.webkit.org/show_bug.cgi?id=153668">FIXME: Add more text here.</a></p>30 359 </div> 31 360 </body>
Note:
See TracChangeset
for help on using the changeset viewer.
