Modified: trunk/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html (201524 => 201525)
--- trunk/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html 2016-05-31 21:24:19 UTC (rev 201524)
+++ trunk/Websites/webkit.org/docs/b3/assembly-intermediate-representation.html 2016-05-31 21:40:18 UTC (rev 201525)
@@ -14,10 +14,341 @@
</div>
<div id="contents">
<h1><a href="" Bones Backend</a> / Assembly Intermediate Representation</h1>
- <p>The B3 compiler converts SSA procedures into efficient machine code by first converting
- them to a form that reveals machine details, like registers. This form is called Assembly
- Intermediate Representation, or just Air for short.</p>
-
+ <p>The B3 compiler comprises two intermediate representations: a higher-level
+ <a href=""
+ representation called <a href="" 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=""
+ object. <code>Code</code> comprises an array of
+ <a href=""
+ blocks</a>. Each basic block comprises an array of
+ <a href=""
+ 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, an array of
+ arguments
+ (<a href=""
+ and an origin. The origin is simply a B3 IR
+ <a href=""
+ 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. Most clients only have to worry about the pointer type varying between Int32 and
+ Int64. It's a goal of B3 IR to ensure that B3 values behave the same way except when the
+ alternative would be prohibitive (like with pointer size or the corner-case behaviors of
+ division). 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=""
+ and abstract
+ <a href=""
+ slots</a>.</p>
+
+ <h3>Air as an Instruction Superset</h3>
+ <p>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 with 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.</p>
+
+ <p>Air opcodes support overloading. For example, the Add32 opcode has both two-operand and
+ three-operand overloads, and those overloads have multiple forms: the first operand may or
+ may not be an immediate and depending on the CPU, some of the other operands may or may not
+ be memory addresses. 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. This allows clients
+ to generate Air by experimenting with various different instruction 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, 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="" 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 constraints 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>Note that 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 interfere 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="" 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="" 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>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 for example 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>Inst::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="" code generator</a>
+ that uses a
+ <a href="" 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=""
+ 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>See the header of
+ <a href=""
+ for a complete list of shorthand used by Air's opcode definition language.</p>
+
+ <h2>Summary</h2>
<p>Air is designed around _javascript_Core'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
@@ -25,8 +356,6 @@
into actual calls to MacroAssembler. Consequently, we can "add" new instructions to Air
usually by just editing the <a href=""
file.</p>
-
- <p><a href="" Add more text here.</a></p>
</div>
</body>
</html>
