| <html> |
| <head> |
| <title>Assembly Intermediate Representation</title> |
| <link rel="stylesheet" type="text/css" href="style.css"> |
| </head> |
| <body> |
| <div id="banner"> |
| <a href="http://www.webkit.org/" class="banner-link"> |
| <div id="logo" class="site-logo"> |
| WebKit |
| <span class="tagline">Open Source Web Browser Engine</span> |
| </div> |
| </a> |
| </div> |
| <div id="contents"> |
| <h1><a href="index.html">Bare Bones Backend</a> / Assembly Intermediate Representation</h1> |
| <p>The B3 compiler comprises two intermediate representations: a higher-level |
| <a href="https://en.wikipedia.org/wiki/Static_single_assignment_form">SSA</a>-based |
| representation called <a href="intermediate-representation.html">B3 IR</a> and a lower-level |
| representation that focuses of machine details, like registers. This lower-level form is called |
| Air (Assembly Intermediate Representation).</p> |
| |
| <p>Air programs are represented using a |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirCode.h"><code>Air::Code</code></a> |
| object. <code>Code</code> comprises an array of |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirBasicBlock.h">basic |
| blocks</a>. Each basic block comprises an array of |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirInst.h"><code>Inst</code></a>s. |
| Air has an explicit control flow graph: each basic block has predecessor and successor blocks. |
| Execution always begins at the first basic block (<code>code[0]</code>). The <code>Inst</code>s |
| in each block are executed in order. Each <code>Inst</code> has an opcode, some flags, an |
| array of arguments |
| (<a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirArg.h"><code>Arg</code></a>s), |
| and an origin. The opcode and flags are wrapped in a <code>Kind</code>, to make it |
| convenient to carry them around together. The origin is simply a B3 IR |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/B3Value.h"><code>Value</code></a>. |
| Some opcodes use the origin for additional meta-data. This works because Air code always |
| coexists with the B3 procedure from which it was generated.</p> |
| |
| <p>This document begins by describing the philosophy of Air. The behavior of <code>Arg</code>s is |
| central to Air's execution model, which is described in the section that follows. The last |
| section describes the way Air opcodes are defined.</p> |
| |
| <h2>Philosophy of Air</h2> |
| |
| <p>B3 is designed to be portable to many kinds of CPUs. Currently, it supports x86-64 and ARM64, |
| which are quite different from each other. In B3 IR, we expose very few instruction set |
| details. It's a goal of B3 IR to ensure that B3 values behave the same way except when the |
| alternative would be counterproductive (like with pointer size, the corner-case behaviors of |
| division, or calling convention customization). But to effectively compile code to different |
| CPUs, the compiler has to eventually make instruction set details explicit. This is where Air |
| comes in. B3 locks in most CPU-specific details at the moment of conversion to Air, and the Air |
| code is irreversibly tied to some specific CPU.</p> |
| |
| <p>Air is an instruction <i>superset</i>: it recognizes all of the instructions from all CPUs |
| that Air may target. In its lowest-level form, Air is simply a way of describing an assembly |
| instruction sequence, and this includes CPU concepts like registers and direct accesses to the |
| stack. Air also has a higher-level form in which the assembly has not yet undergone register |
| or stack allocation. Therefore, Air also supports abstract registers (called |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirTmp.h"><code>Tmp</code></a>s) |
| and abstract |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirStackSlot.h">stack |
| slots</a>. A <code>Tmp</code> object can either hold an unallocated temporary or a |
| register.</p> |
| |
| <h3>Air as an Instruction Superset</h3> |
| <p>Air has syntax to speak of all of the CPU instructions we know about. It is possible to speak |
| of an x86-64 instruction while compiling for ARM64, for example. Clients of Air, such as the B3 |
| to Air lowering phase, are allowed to pick any Air opcode and ask if that opcode would be |
| valid on the current CPU. They are also allowed to check if specific forms of any given opcode |
| are valid. This allows clients to optimize for multiple instruction sets by cascading through |
| the possible opcodes that they know of, starting with the one they think is most efficient. |
| Some of those opcodes may only be available on one CPU while others are available |
| everywhere. Instruction selection does not need to know which instructions work on which CPUs; |
| Air will tell you if some instruction happens to not be valid right now for whatever reason.</p> |
| |
| <p>Air opcodes support overloading. For example, the Add32 opcode has both two-operand and |
| three-operand <i>overloads</i>, and those overloads have multiple <i>forms</i>: the first |
| operand may or may not be permitted to be an immediate and depending on the CPU and some of the |
| other operands may or may not be allowed to be memory addresses. We use <i>opcode overload</i> |
| to refer to all forms of an opcode that share the same number of arguments, and <i>opcode |
| form</i> to mean the number of arguments and their types. A fundamental Air operation is |
| <code>Inst::isValidForm()</code>, which tells the client if the instruction's current form is |
| valid on the current CPU. This may return false either because the Inst is not well-formed for |
| any CPU or because it is not valid for the current CPU even though it may be valid on some |
| other CPU. There is also <code>Air::isValidForm()</code>, which can answer if the form you are |
| intending to use will be valid even if you have not created an <code>Inst</code> yet. This |
| allows clients to generate Air by experimenting with different forms before settling on the one |
| that the current CPU supports.</p> |
| |
| <h3>Air as a High-Level Assembly</h3> |
| <p>Air doesn't require the client to perform register or stack allocation. Anywhere that Air |
| accepts a register it will also accept a <code>Tmp</code>. Anywhere that Air accepts an address |
| it will also accept a stack slot reference. Air code generation comprises a register allocator |
| and a stack allocator, which turn <code>Tmp</code>s into <code>Reg</code>s and stack slots into |
| addresses with the frame pointer (or stack pointer) as the base and some integer offset. Air |
| allows clients to speak of registers directly even while also using <code>Tmp</code>s, and the |
| register allocator will ensure that it avoids clobbering registers that the client code already |
| relies upon. This is possible because Air has precise modeling of how instructions use |
| registers, so it's always possible to determine which registers are live at any point in the |
| Air code.</p> |
| |
| <p>Air's philosophy allows B3 to use it for converting high-level, mostly-CPU-agnostic SSA |
| procedures into code for the current CPU. Air is an instruction superset that allows clients to |
| consider all available instructions on all possible CPUs and query which forms of those |
| instructions are available on the current CPU. Air also supports for high-level concepts like |
| <code>Tmp</code>s and stack slots, which allows B3 to Air lowering to focus on which |
| instructions to use without worrying about register allocation or stack layout.</p> |
| |
| <h2>Args and the Air Execution Model</h2> |
| <p>Air can be thought of as an |
| <a href="https://en.wikipedia.org/wiki/Orthogonal_instruction_set">orthogonal instruction |
| set</a>. It's possible to construct an <code>Inst</code> with any combination of opcode and |
| arguments. The opcode determines what Air will do to the arguments - it may read from them or |
| write to them, for example. Orthognality implies that any argument that is read may be either |
| a register (or <code>Tmp</code>), an address, or an immediate; while any argument that is |
| written may be either a register or an address. Air constrains orthognality where the target |
| CPU would. For example, none of Air's target CPUs would support an <code>Add32</code> |
| instruction that loads its sources from memory <i>and</i> stores its result into memory. Even |
| x86 doesn't go that far. Either before or after creating an <code>Inst</code>, the client can |
| query if a particular combination of arguments (for example, three memory addresses) would be |
| valid for a given opcode (for example, <code>Add32</code>).</p> |
| |
| <p>Air arguments are represented using the <code>Arg</code> object. <code>Arg</code> can |
| represent any of the following assembly operands:</p> |
| |
| <dl> |
| <dt>Tmp</dt> |
| <dd>A <code>Tmp</code> represents either a register or a temporary.</dd> |
| |
| <dt>Imm, BigImm, BitImm, and BitImm64</dt> |
| <dd>These are various kinds of immediates. We distinguish between big and small immediates |
| because some instructions only allow immediates within a certain range. We distinguish |
| between immediates for bit operations and immediates for all other operations because ARM |
| has different constraints on the values of immediates depending on whether they are used for |
| bit math.</dd> |
| |
| <dt>Addr, Stack, CallArg, and Index</dt> |
| <dd>These are all memory addresses. Addr is a base-offset address, which uses a <code>Tmp</code> |
| for the base and an immediate for the offset. Stack and CallArg are abstract stack offsets. |
| Index is a base-index address, which has a pair of <code>Tmp</code>s (base and index) as well |
| as an offset immediate and a scaling immediate for the index.</dd> |
| |
| <dt>RelCond, ResCond, and DoubleCond</dt> |
| <dd>These are condition codes for various kinds of branches.</dd> |
| |
| <dt>Special</dt> |
| <dd>Air allows certain <code>Inst</code>s to point to additional meta-data. The Special |
| argument type is used for such meta-data. It holds a <code>Arg::Special*</code>.</dd> |
| |
| <dt>WidthArg</dt> |
| <dd>Some special Air opcodes take operands that describe the width of the operation. Possible |
| values are <code>Width8</code>, <code>Width16</code>, <code>Width32</code>, and |
| <code>Width64</code>.</dd> |
| </dl> |
| |
| <p>The opcode of an <code>Inst</code> combined with the overload - i.e. the number of arguments |
| - determines what the <code>Inst</code> will do to each argument. The behavior of arguments |
| comes down to three dimensions that are determined by the opcode and overload:</p> |
| |
| <dl> |
| <dt>Role</dt> |
| <dd>The role of an argument is an enum that describes the timing of when the argument is |
| accessed, how it's accessed (use, a.k.a. read; or def, a.k.a write), how important that |
| access is for performance (either <i>warm</i> or <i>cold</i>), and how writes affect the top |
| bits (either ignores them or zero-fills them). The timing of an argument role is discussed |
| further below. The performance requirements of an argument are used for register allocation |
| prioritization. A warm argument is counted towards the register allocation priority |
| heuristic, while a cold one isn't.</dd> |
| |
| <dt>Type</dt> |
| <dd>Air recognizes two types, <code>GP</code> (general purpose) and <code>FP</code> (floating |
| point). Arguments also have type. It's important to remember that there is both a type for |
| the argument as determined by the opcode and overload, and a type of the argument itself. |
| Some arguments are untyped, which means that they may be used regardless of the type desired |
| by the opcode/overload. For example, addresses are untyped. Other arguments have specific |
| type, like registers and <code>Tmp</code>s. Except for <code>BigImm</code>, immediates are |
| <code>GP</code>.</dd> |
| |
| <dt>Width</dt> |
| <dd>The amount of bits, starting at lowest-order, that the instruction affects. Possible values |
| are <code>Width8</code>, <code>Width16</code>, <code>Width32</code>, and |
| <code>Width64</code>.</dd> |
| </dl> |
| |
| <p>The timing of an argument role is important, and brings us to the order of execution of an |
| <code>Inst</code>. Each <code>Inst</code> can be thought of as executing three |
| steps:</p> |
| |
| <ol> |
| <li>Perform <i>early</i> actions.</li> |
| <li>Perform <i>primary</i> actions.</li> |
| <li>Perform <i>late</i> actions.</li> |
| </ol> |
| |
| <p>The early actions of one instruction happen immediately after the late actions of |
| the instruction before it. However, many Air analyses view them as happening at the same time. |
| For example, any register usage in the early action of one instruction interferes with the |
| register usage in the late action of the instruction that came before it. All of Air's |
| liveness and interference analyses reason about the |
| <a href="https://en.wikipedia.org/wiki/Off-by-one_error#Fencepost_error"><i>fence posts</i></a> |
| between instructions, where the late actions of the previous instruction and the early actions |
| of the next form an interference clique.</p> |
| |
| <p>Let's consider a simple example, like <code>Add32</code> with two arguments. Let's say that |
| the first argument is a memory location and the second argument is a register. Air uses the |
| <a href="https://en.wikipedia.org/wiki/X86_assembly_language#Syntax">AT&T style</a> of |
| placing the destination argument last for most instructions. This Add32 loads from memory and |
| adds the value to the register. Air writes this as:</p> |
| |
| <pre><code>Add32 42(%rax), %rcx</code></pre> |
| |
| <p>This instruction will proceed in three steps:</p> |
| |
| <ol> |
| <li>Load the value at offset 42 from the memory address in <code>%rax</code>. The result is |
| stored in an internal, hidden CPU location for the remainder of execution. Even if the |
| instruction later stores to memory and overwrites this value, <code>Add32</code> will still |
| use the original value it had loaded. We say that this is an <i>early use</i>. At the same |
| time, the CPU will load the value of <code>%rcx</code> and store it in a hidden CPU |
| location. This is also an early use.</li> |
| <li>Add the two values together. Store the result in hidden CPU location.</li> |
| <li>Zero-extend the resulting value and store it into <code>%rcx</code>. This is a <i>late |
| def with zero extension</i>.</li> |
| </ol> |
| |
| <p>Therefore, the two-argument overload of <code>Add32</code> ascribes the following to its |
| arguments:</p> |
| |
| <ul> |
| <li>The roles are <i>early warm use</i> for the first argument (<code>42(%rax)</code>) and |
| <i>early warm use with late warm def with zero extension</i> for the second argument |
| (<code>%rcx</code>). Early warm use is written as <code>Use</code> for short. Early warm |
| use with late warm def with zero extension is written as <code>UseZDef</code> for |
| short.</li> |
| <li>The types of both arguments are <code>GP</code>. This matches <code>42(%rax)</code> because |
| addresses match any type. This matches <code>%rcx</code> because it's a general-purpose |
| register.</li> |
| <li>The widths of both arguments are <code>Width32</code>. Combined with <code>UseZDef</code>, |
| this means that the instruction will read the low 32 bits of <code>%rcx</code> in the early |
| actions and it will store to <i>all</i> bits of <code>%rcx</code> in the late actions, but it |
| will ensure that all but the low 32 bits are zero.</li> |
| </ul> |
| |
| <p>Air can tell you what role, type, and width is ascribed to each argument by using the |
| <code>Inst::forEachArg(func)</code> operation. It takes a callback of type |
| <code>void(Arg&, Arg::Role, Arg::Type, Arg::Width)</code>. For our <code>Add32</code> example, |
| this callback would get called twice:</p> |
| |
| <ol> |
| <li><code>func(42(%rax), Use, GP, Width32)</code></li> |
| <li><code>func(%rcx, UseZDef, GP, Width32)</code></li> |
| </ol> |
| |
| <p>It's important to remember that Air's summaries of what instructions do to arguments are |
| not meant to be exhaustive. For example, if an instruction claims to use an address, this |
| tells you that the instruction will perform a load but it tells you nothing about how that |
| load will be performed. This means that unless you know exactly what it means to use/def an |
| argument, you cannot perform this transformation:</p> |
| |
| <ul> |
| <li>Before: |
| <pre><code>Foo32 (%rax)</code></pre></li> |
| <li>After: |
| <pre><code>Move32 (%rax), %tmp |
| Foo32 %tmp</code></pre></li> |
| </ul> |
| |
| <p>Even if you know that Foo32 only uses its argument, you cannot do this because Move32 may |
| not load from the address using exactly the same kind of load that Foo32 would have done. |
| Memory accesses have many dimensions of options: alignment semantics (if you're lucky then |
| misaligned accesses run fast but sometimes they ignore low bits, trap if unaligned, or run |
| super slow when unaligned, and this behavior may depend on the opcode), temporality and |
| memory ordering, determinism of trapping, etc. Just seeing that an instruction uses an |
| address does not tell you what kind of load will happen, and currently Air does not have the |
| ability to answer such questions. Fortunately, Air does not have much need to move memory |
| accesses out of instructions. Uses and defs of temporaries, registers, immediates, and spill |
| slots don't have these caveats and so those arguments can be moved from one instruction to |
| another without worries.</p> |
| |
| <p>Air's introspection of <code>Inst</code>s tends to be quite fast thanks to the use of template |
| specialization and C++ lambdas. The <code>forEachArg()</code> template method uses an efficient |
| arrangement of switch statements to determine the opcode and overload. If <code>func</code> is |
| a C++ lambda, we expect <code>forEachArg()</code> to be specialized for that lambda. Therefore, |
| this idiom avoids virtual dispatch or memory allocation.</p> |
| |
| <p>Air supports exotic roles, such as late uses and early defs. There is even the |
| <code>Scratch</code> role, which means early def and late use. Speaking of a <code>Tmp</code> |
| in the <code>Scratch</code> role means that the <code>Tmp</code> will be assigned a register |
| that is guaranteed to not interfere with any of the other registers that the instruction |
| speaks of. Late uses and early defs are crucial for patchpoints, which may require |
| that one of the incoming values be given a register that does not interfere with whatever |
| register is used for the result. This can be expressed either as giving the inputs a late use |
| role or by giving the outputs an early def role. The full list of possible roles is:</p> |
| |
| <dl> |
| <dt>Use</dt> |
| <dd>Early warm use.</dd> |
| |
| <dt>ColdUse</dt> |
| <dd>Early cold use.</dd> |
| |
| <dt>LateUse</dt> |
| <dd>Late warm use.</dd> |
| |
| <dt>LateColdUse</dt> |
| <dd>Late cold use.</dd> |
| |
| <dt>Def</dt> |
| <dd>Late def. <i>Note that all defs are warm.</i></dd> |
| |
| <dt>ZDef</dt> |
| <dd>Late def with zero-extension.</dd> |
| |
| <dt>UseDef</dt> |
| <dd>Early warm use and late def.</dd> |
| |
| <dt>UseZDef</dt> |
| <dd>Early warm use and late def with zero extension.</dd> |
| |
| <dt>EarlyDef</dt> |
| <dd>Early def.</dd> |
| |
| <dt>Scratch</dt> |
| <dd>Early def and late warm use.</dd> |
| |
| <dt>UseAddr</dt> |
| <dd>Early warm use of the address's components.</dd> |
| </dl> |
| |
| <p><code>UseAddr</code> is interesting for the <code>Lea</code> (load effective address) |
| instruction, which evaluates the address and places the result into a temporary or register. |
| The argument must be an address, but <code>UseAddr</code> means that we don't actually read |
| from the address. Note that using an address in any of the other roles always implies that the |
| components of the address are used early and warm (i.e. <code>Use</code>).</p> |
| |
| <p>Air arguments are central to Air's execution model. The early and late actions of an |
| instruction have to do with arguments, and what happens to each argument during the early and |
| late actions is determined by the opcode and the number of arguments (i.e. the overload). |
| Clients of Air may create an <code>Inst</code> with any combination of opcode and arguments |
| and then query, using <code>isValidForm()</code> if the opcode, overload, and specific |
| arguments are valid for the current CPU.</p> |
| |
| <h2>Defining Air</h2> |
| <p>Air has many opcodes and the opcodes have many different overloads and forms. Air makes it |
| easy to reason about all of them with helpers like <code>isValidForm()</code> and |
| <code>forEachArg()</code>. It also provides a <code>Inst::generate()</code> function that will |
| generate code for the instruction, provided that it does not use any non-register |
| <code>Tmp</code>s or any abstract stack slots. If we wrote the |
| code for validating, iterating, and generating each form by hand, we would have a bad time. |
| For this reason, Air comes with an |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/opcode_generator.rb">opcode code generator</a> |
| that uses a |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">opcode definition file</a> |
| as input. The opcode definition file use a simple and concise syntax that lets us define many |
| opcodes at once and constrain them to the CPU kinds that support them. Additionally, Air |
| supports <i>custom</i> opcodes, where the code generator emits calls to |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirCustom.h">hand-written |
| C++ code</a>. This section describes the opcode definition language.</p> |
| |
| <p>It's easiest to understand the opcode definitions with an example. Let's use the two-argument |
| overload of <code>Add32</code>.</p> |
| |
| <pre><code>Add32 U:G:32, UZD:G:32 |
| Tmp, Tmp |
| x86: Imm, Addr |
| x86: Imm, Index |
| Imm, Tmp |
| x86: Addr, Tmp |
| x86: Tmp, Addr |
| x86: Tmp, Index</code></pre> |
| |
| <p>The first line defines the overload. It has two arguments. The first argument serves the |
| <code>Use</code> role, shorted as <code>U</code>. It is general-purpose, shortened as |
| <code>G</code>. It has a 32-bit width. Hence the string <code>U:G:32</code>. Similarly, |
| <code>UZD:G:32</code> means <code>UseZDef</code>, <code>GP</code>, <code>Width32</code>.</p> |
| |
| <p>The next lines list the available forms of the overload. A form is a list of possible kinds of |
| arguments. These use the same terminology for <code>Arg</code> kinds from the previous section, |
| with the caveat that <code>Addr</code> implies that <code>Addr</code>, <code>Stack</code>, or |
| <code>CallArg</code> would be accepted.</p> |
| |
| <p>Prefixing any line with <code>x86:</code> means that this form is only available on x86 |
| CPUs, such as x86 or x86-64.</p> |
| |
| <p>Air opcodes are designed to work with JavaScriptCore's existing MacroAssembler. By default, an |
| opcode is automatically given a code generator that calls |
| <code>MacroAssembler::<i>opcodeName</i></code>, where <i>opcodeName</i> is derived by |
| lower-casing the first letter of the Air opcode name. <code>Add32</code> becomes |
| <code>MacroAssembler::add32</code>, for example.</p> |
| |
| <p>See the header of |
| <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">AirOpcode.opcodes</a> |
| for a complete list of shorthand used by Air's opcode definition language.</p> |
| |
| <h2>Summary</h2> |
| <p>Air is designed around JavaScriptCore's existing MacroAssembler. Air has Inst objects, |
| which each describe some method call to the MacroAssembler: an Inst's opcode indicates |
| which method name to use and its args indicate the arguments to pass to that method. We |
| use code generation to create a massive switch statement that turns the reflective Insts |
| into actual calls to MacroAssembler. Consequently, we can "add" new instructions to Air |
| usually by just editing the <a href="http://trac.webkit.org/browser/trunk/Source/JavaScriptCore/b3/air/AirOpcode.opcodes">AirOpcode.opcodes</a> |
| file.</p> |
| </div> |
| </body> |
| </html> |
| |
