Unreviewed, fix an obvious typo: a missing comma.
[WebKit-https.git] / Websites / webkit.org / docs / b3 / assembly-intermediate-representation.html
index 8fc69e43a1a065f32988cc61fa2a407a4f6c271f..ed4fb85f408332df7fdec813b1b32e81eb96ea9a 100644 (file)
 <html>
-  <head>
-    <title>Assembly Intermediate Representation</title>
-    <link rel="stylesheet" type="text/css" href="style.css">
-  </head>
-  <body>
+<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 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="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, 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 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. 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="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>.</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="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 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="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&amp;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>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="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>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 â€‹AirOpcode.opcodes file.</p>
-
-    <p><a href="https://bugs.webkit.org/show_bug.cgi?id=153668">FIXME: Add more text here.</a></p>
-  </body>
+      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>