qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

il.txt (33415B)


      1                 ===========================
      2                  QBE Intermediate Language
      3                 ===========================
      4 
      5 
      6 
      7 - Table of Contents
      8 -------------------
      9 
     10   1. <@ Basic Concepts >
     11       * <@ Input Files >
     12       * <@ BNF Notation >
     13       * <@ Sigils >
     14       * <@ Spacing >
     15   2. <@ Types >
     16       * <@ Simple Types >
     17       * <@ Subtyping >
     18   3. <@ Constants >
     19   4. <@ Linkage >
     20   5. <@ Definitions >
     21       * <@ Aggregate Types >
     22       * <@ Data >
     23       * <@ Functions >
     24   6. <@ Control >
     25       * <@ Blocks >
     26       * <@ Jumps >
     27   7. <@ Instructions >
     28       * <@ Arithmetic and Bits >
     29       * <@ Memory >
     30       * <@ Comparisons >
     31       * <@ Conversions >
     32       * <@ Cast and Copy >
     33       * <@ Call >
     34       * <@ Variadic >
     35       * <@ Phi >
     36   8. <@ Instructions Index >
     37 
     38 - 1. Basic Concepts
     39 -------------------
     40 
     41 The intermediate language (IL) is a higher-level language
     42 than the machine's assembly language.  It smoothes most
     43 of the irregularities of the underlying hardware and
     44 allows an infinite number of temporaries to be used.
     45 This higher abstraction level allows frontend programmers
     46 to focus on language design issues.
     47 
     48 ~ Input Files
     49 ~~~~~~~~~~~~~
     50 
     51 The intermediate language is provided to QBE as text.
     52 Usually, one file is generated per each compilation unit from
     53 the frontend input language.  An IL file is a sequence of
     54 <@ Definitions > for data, functions, and types.  Once
     55 processed by QBE, the resulting file can be assembled and
     56 linked using a standard toolchain (e.g., GNU binutils).
     57 
     58 Here is a complete "Hello World" IL file which defines a
     59 function that prints to the screen.  Since the string is
     60 not a first class object (only the pointer is) it is
     61 defined outside the function's body.  Comments start with
     62 a # character and finish with the end of the line.
     63 
     64     # Define the string constant.
     65     data $str = { b "hello world", b 0 }
     66 
     67     export function w $main() {
     68     @start
     69             # Call the puts function with $str as argument.
     70             %r =w call $puts(l $str)
     71             ret 0
     72     }
     73 
     74 If you have read the LLVM language reference, you might
     75 recognize the example above.  In comparison, QBE makes a
     76 much lighter use of types and the syntax is terser.
     77 
     78 ~ BNF Notation
     79 ~~~~~~~~~~~~~~
     80 
     81 The language syntax is vaporously described in the sections
     82 below using BNF syntax.  The different BNF constructs used
     83 are listed below.
     84 
     85   * Keywords are enclosed between quotes;
     86   * `... | ...` expresses alternatives;
     87   * `( ... )` groups syntax;
     88   * `[ ... ]` marks the nested syntax as optional;
     89   * `( ... ),` designates a comma-separated list of the
     90     enclosed syntax;
     91   * `...*` and `...+` are used for arbitrary and
     92     at-least-once repetition respectively.
     93 
     94 ~ Sigils
     95 ~~~~~~~~
     96 
     97 The intermediate language makes heavy use of sigils, all
     98 user-defined names are prefixed with a sigil.  This is
     99 to avoid keyword conflicts, and also to quickly spot the
    100 scope and nature of identifiers.
    101 
    102  * `:` is for user-defined <@ Aggregate Types>
    103  * `$` is for globals (represented by a pointer)
    104  * `%` is for function-scope temporaries
    105  * `@` is for block labels
    106 
    107 In this BNF syntax, we use `?IDENT` to designate an identifier
    108 starting with the sigil `?`.
    109 
    110 ~ Spacing
    111 ~~~~~~~~~
    112 
    113     `bnf
    114     NL := '\n'+
    115 
    116 Individual tokens in IL files must be separated by one or
    117 more spacing characters.  Both spaces and tabs are recognized
    118 as spacing characters.  In data and type definitions, newlines
    119 may also be used as spaces to prevent overly long lines.  When
    120 exactly one of two consecutive tokens is a symbol (for example
    121 `,` or `=` or `{`), spacing may be omitted.
    122 
    123 - 2. Types
    124 ----------
    125 
    126 ~ Simple Types
    127 ~~~~~~~~~~~~~~
    128 
    129     `bnf
    130     BASETY := 'w' | 'l' | 's' | 'd'  # Base types
    131     EXTTY  := BASETY    | 'b' | 'h'  # Extended types
    132 
    133 The IL makes minimal use of types.  By design, the types
    134 used are restricted to what is necessary for unambiguous
    135 compilation to machine code and C interfacing.  Unlike LLVM,
    136 QBE is not using types as a means to safety; they are only
    137 here for semantic purposes.
    138 
    139 The four base types are `w` (word), `l` (long), `s` (single),
    140 and `d` (double), they stand respectively for 32-bit and
    141 64-bit integers, and 32-bit and 64-bit floating-point numbers.
    142 There are no pointer types available; pointers are typed
    143 by an integer type sufficiently wide to represent all memory
    144 addresses (e.g., `l` on 64-bit architectures).  Temporaries
    145 in the IL can only have a basic type.
    146 
    147 Extended types contain base types plus `b` (byte) and `h`
    148 (half word), respectively for 8-bit and 16-bit integers.
    149 They are used in <@ Aggregate Types> and <@ Data> definitions.
    150 
    151 For C interfacing, the IL also provides user-defined aggregate
    152 types.  The syntax used to designate them is `:foo`.  Details
    153 about their definition are given in the <@ Aggregate Types >
    154 section.
    155 
    156 ~ Subtyping
    157 ~~~~~~~~~~~
    158 
    159 The IL has a minimal subtyping feature, for integer types only.
    160 Any value of type `l` can be used in a `w` context.  In that
    161 case, only the 32 least significant bits of the word value
    162 are used.
    163 
    164 Make note that it is the opposite of the usual subtyping on
    165 integers (in C, we can safely use an `int` where a `long`
    166 is expected).  A long value cannot be used in word context.
    167 The rationale is that a word can be signed or unsigned, so
    168 extending it to a long could be done in two ways, either
    169 by zero-extension, or by sign-extension.
    170 
    171 - 3. Constants
    172 --------------
    173 
    174     `bnf
    175     CONST :=
    176         ['-'] NUMBER  # Decimal integer
    177       | 's_' FP       # Single-precision float
    178       | 'd_' FP       # Double-precision float
    179       | $IDENT        # Global symbol
    180 
    181 Throughout the IL, constants are specified with a unified
    182 syntax and semantics.  Constants are immediates, meaning
    183 that they can be used directly in instructions; there is
    184 no need for a "load constant" instruction.
    185 
    186 The representation of integers is two's complement.
    187 Floating-point numbers are represented using the
    188 single-precision and double-precision formats of the
    189 IEEE 754 standard.
    190 
    191 Constants specify a sequence of bits and are untyped.
    192 They are always parsed as 64-bit blobs.  Depending on
    193 the context surrounding a constant, only some of its
    194 bits are used.  For example, in the program below, the
    195 two variables defined have the same value since the first
    196 operand of the subtraction is a word (32-bit) context.
    197 
    198     %x =w sub -1, 0
    199     %y =w sub 4294967295, 0
    200 
    201 Because specifying floating-point constants by their bits
    202 makes the code less readable, syntactic sugar is provided
    203 to express them.  Standard scientific notation is prefixed
    204 with `s_` and `d_` for single and double precision numbers
    205 respectively. Once again, the following example defines twice
    206 the same double-precision constant.
    207 
    208     %x =d add d_0, d_-1
    209     %y =d add d_0, -4616189618054758400
    210 
    211 Global symbols can also be used directly as constants;
    212 they will be resolved and turned into actual numeric
    213 constants by the linker.
    214 
    215 - 4. Linkage
    216 ------------
    217 
    218     `bnf
    219     LINKAGE :=
    220         'export' [NL]
    221       | 'section' SECNAME [NL]
    222       | 'section' SECNAME SECFLAGS [NL]
    223 
    224     SECNAME  := '"' .... '"'
    225     SECFLAGS := '"' .... '"'
    226 
    227 Function and data definitions (see below) can specify
    228 linkage information to be passed to the assembler and
    229 eventually to the linker.
    230 
    231 The `export` linkage flag marks the defined item as
    232 visible outside the current file's scope.  If absent,
    233 the symbol can only be referred to locally.  Functions
    234 compiled by QBE and called from C need to be exported.
    235 
    236 A `section` flag can be specified to tell the linker to
    237 put the defined item in a certain section.  The use of
    238 the section flag is platform dependent and we refer the
    239 user to the documentation of their assembler and linker
    240 for relevant information.
    241 
    242     section ".init_array"
    243     data $.init.f = { l $f }
    244 
    245 The section flag can be used to add function pointers to
    246 a global initialization list, as depicted above.  Note
    247 that some platforms provide a BSS section that can be
    248 used to minimize the footprint of uniformly zeroed data.
    249 When this section is available, QBE will automatically
    250 make use of it and no section flag is required.
    251 
    252 The section and export linkage flags should each appear
    253 at most once in a definition.  If multiple occurrences
    254 are present, QBE is free to use any.
    255 
    256 - 5. Definitions
    257 ----------------
    258 
    259 Definitions are the essential components of an IL file.
    260 They can define three types of objects: aggregate types,
    261 data, and functions.  Aggregate types are never exported
    262 and do not compile to any code.  Data and function
    263 definitions have file scope and are mutually recursive
    264 (even across IL files).  Their visibility can be controlled
    265 using linkage flags.
    266 
    267 ~ Aggregate Types
    268 ~~~~~~~~~~~~~~~~~
    269 
    270     `bnf
    271     TYPEDEF :=
    272         # Regular type
    273         'type' :IDENT '=' ['align' NUMBER]
    274         '{'
    275             ( SUBTY [NUMBER] ),
    276         '}'
    277       | # Opaque type
    278         'type' :IDENT '=' 'align' NUMBER '{' NUMBER '}'
    279 
    280     SUBTY := EXTTY | :IDENT
    281 
    282 Aggregate type definitions start with the `type` keyword.
    283 They have file scope, but types must be defined before being
    284 referenced.  The inner structure of a type is expressed by a
    285 comma-separated list of types enclosed in curly braces.
    286 
    287     type :fourfloats = { s, s, d, d }
    288 
    289 For ease of IL generation, a trailing comma is tolerated by
    290 the parser.  In case many items of the same type are
    291 sequenced (like in a C array), the shorter array syntax
    292 can be used.
    293 
    294     type :abyteandmanywords = { b, w 100 }
    295 
    296 By default, the alignment of an aggregate type is the
    297 maximum alignment of its members.  The alignment can be
    298 explicitly specified by the programmer.
    299 
    300     type :cryptovector = align 16 { w 4 }
    301 
    302 Opaque types are used when the inner structure of an
    303 aggregate cannot be specified; the alignment for opaque
    304 types is mandatory.  They are defined simply by enclosing
    305 their size between curly braces.
    306 
    307     type :opaque = align 16 { 32 }
    308 
    309 ~ Data
    310 ~~~~~~
    311 
    312     `bnf
    313     DATADEF :=
    314         LINKAGE*
    315 	'data' $IDENT '=' ['align' NUMBER]
    316         '{'
    317             ( EXTTY DATAITEM+
    318             | 'z'   NUMBER ),
    319         '}'
    320 
    321     DATAITEM :=
    322         $IDENT ['+' NUMBER]  # Symbol and offset
    323       |  '"' ... '"'         # String
    324       |  CONST               # Constant
    325 
    326 Data definitions express objects that will be emitted in the
    327 compiled file.  Their visibility and location in the compiled
    328 artifact are controlled with linkage flags described in the
    329 <@ Linkage > section.
    330 
    331 They define a global identifier (starting with the sigil
    332 `$`), that will contain a pointer to the object specified
    333 by the definition.
    334 
    335 Objects are described by a sequence of fields that start with
    336 a type letter.  This letter can either be an extended type,
    337 or the `z` letter.  If the letter used is an extended type,
    338 the data item following specifies the bits to be stored in
    339 the field.  When several data items follow a letter, they
    340 initialize multiple fields of the same size.
    341 
    342 The members of a struct will be packed.  This means that
    343 padding has to be emitted by the frontend when necessary.
    344 Alignment of the whole data objects can be manually specified,
    345 and when no alignment is provided, the maximum alignment from
    346 the platform is used.
    347 
    348 When the `z` letter is used the number following indicates
    349 the size of the field; the contents of the field are zero
    350 initialized.  It can be used to add padding between fields
    351 or zero-initialize big arrays.
    352 
    353 Here are various examples of data definitions.
    354 
    355     # Three 32-bit values 1, 2, and 3
    356     # followed by a 0 byte.
    357     data $a = { w 1 2 3, b 0 }
    358 
    359     # A thousand bytes 0 initialized.
    360     data $b = { z 1000 }
    361 
    362     # An object containing two 64-bit
    363     # fields, one with all bits sets and the
    364     # other containing a pointer to the
    365     # object itself.
    366     data $c = { l -1, l $c }
    367 
    368 ~ Functions
    369 ~~~~~~~~~~~
    370 
    371     `bnf
    372     FUNCDEF :=
    373         LINKAGE*
    374 	'function' [ABITY] $IDENT '(' (PARAM), ')' [NL]
    375         '{' NL
    376             BLOCK+
    377         '}'
    378 
    379     PARAM :=
    380         ABITY %IDENT  # Regular parameter
    381       | 'env' %IDENT  # Environment parameter (first)
    382       | '...'         # Variadic marker (last)
    383 
    384     ABITY := BASETY | :IDENT
    385 
    386 Function definitions contain the actual code to emit in
    387 the compiled file.  They define a global symbol that
    388 contains a pointer to the function code.  This pointer
    389 can be used in `call` instructions or stored in memory.
    390 
    391 The type given right before the function name is the
    392 return type of the function.  All return values of this
    393 function must have this return type.  If the return
    394 type is missing, the function cannot return any value.
    395 
    396 The parameter list is a comma separated list of
    397 temporary names prefixed by types.  The types are used
    398 to correctly implement C compatibility.  When an argument
    399 has an aggregate type, a pointer to the aggregate is passed
    400 by the caller.  In the example below, we have to use a load
    401 instruction to get the value of the first (and only)
    402 member of the struct.
    403 
    404     type :one = { w }
    405 
    406     function w $getone(:one %p) {
    407     @start
    408             %val =w loadw %p
    409             ret %val
    410     }
    411 
    412 If the parameter list ends with `...`, the function is
    413 a variadic function: it can accept a variable number of
    414 arguments.  To access the extra arguments provided by
    415 the caller, use the `vastart` and `vaarg` instructions
    416 described in the <@ Variadic > section.
    417 
    418 Optionally, the parameter list can start with an
    419 environment parameter `env %e`.  This special parameter is
    420 a 64-bit integer temporary (i.e., of type `l`).  If the
    421 function does not use its environment parameter, callers
    422 can safely omit it.  This parameter is invisible to a C
    423 caller: for example, the function
    424 
    425     export function w $add(env %e, w %a, w %b) {
    426     @start
    427             %c =w add %a, %b
    428             ret %c
    429     }
    430 
    431 must be given the C prototype `int add(int, int)`.
    432 The intended use of this feature is to pass the
    433 environment pointer of closures while retaining a
    434 very good compatibility with C.  The <@ Call > section
    435 explains how to pass an environment parameter.
    436 
    437 Since global symbols are defined mutually recursive,
    438 there is no need for function declarations: a function
    439 can be referenced before its definition.
    440 Similarly, functions from other modules can be used
    441 without previous declaration.  All the type information
    442 is provided in the call instructions.
    443 
    444 The syntax and semantics for the body of functions
    445 are described in the <@ Control > section.
    446 
    447 - 6. Control
    448 ------------
    449 
    450 The IL represents programs as textual transcriptions of
    451 control flow graphs.  The control flow is serialized as
    452 a sequence of blocks of straight-line code which are
    453 connected using jump instructions.
    454 
    455 ~ Blocks
    456 ~~~~~~~~
    457 
    458     `bnf
    459     BLOCK :=
    460         @IDENT NL     # Block label
    461         ( PHI NL )*   # Phi instructions
    462         ( INST NL )*  # Regular instructions
    463         JUMP NL       # Jump or return
    464 
    465 All blocks have a name that is specified by a label at
    466 their beginning.  Then follows a sequence of instructions
    467 that have "fall-through" flow.  Finally one jump terminates
    468 the block.  The jump can either transfer control to another
    469 block of the same function or return; jumps are described
    470 further below.
    471 
    472 The first block in a function must not be the target of
    473 any jump in the program.  If a jump to the function start
    474 is needed, the frontend must insert an empty prelude block
    475 at the beginning of the function.
    476 
    477 When one block jumps to the next block in the IL file,
    478 it is not necessary to write the jump instruction, it
    479 will be automatically added by the parser.  For example
    480 the start block in the example below jumps directly
    481 to the loop block.
    482 
    483     function $loop() {
    484     @start
    485     @loop
    486             %x =w phi @start 100, @loop %x1
    487             %x1 =w sub %x, 1
    488             jnz %x1, @loop, @end
    489     @end
    490             ret
    491     }
    492 
    493 ~ Jumps
    494 ~~~~~~~
    495 
    496     `bnf
    497     JUMP :=
    498         'jmp' @IDENT               # Unconditional
    499       | 'jnz' VAL, @IDENT, @IDENT  # Conditional
    500       | 'ret' [VAL]                # Return
    501 
    502 A jump instruction ends every block and transfers the
    503 control to another program location.  The target of
    504 a jump must never be the first block in a function.
    505 The three kinds of jumps available are described in
    506 the following list.
    507 
    508  1. Unconditional jump.
    509 
    510     Simply jumps to another block of the same function.
    511 
    512  2. Conditional jump.
    513 
    514     When its word argument is non-zero, it jumps to its
    515     first label argument; otherwise it jumps to the other
    516     label.  The argument must be of word type; because of
    517     subtyping a long argument can be passed, but only its
    518     least significant 32 bits will be compared to 0.
    519 
    520  3. Function return.
    521 
    522     Terminates the execution of the current function,
    523     optionally returning a value to the caller.  The value
    524     returned must be of the type given in the function
    525     prototype.  If the function prototype does not specify
    526     a return type, no return value can be used.
    527 
    528 - 7. Instructions
    529 -----------------
    530 
    531 Instructions are the smallest piece of code in the IL, they
    532 form the body of <@ Blocks >.  The IL uses a three-address
    533 code, which means that one instruction computes an operation
    534 between two operands and assigns the result to a third one.
    535 
    536 An instruction has both a name and a return type, this
    537 return type is a base type that defines the size of the
    538 instruction's result.  The type of the arguments can be
    539 unambiguously inferred using the instruction name and the
    540 return type.  For example, for all arithmetic instructions,
    541 the type of the arguments is the same as the return type.
    542 The two additions below are valid if `%y` is a word or a long
    543 (because of <@ Subtyping >).
    544 
    545     %x =w add 0, %y
    546     %z =w add %x, %x
    547 
    548 Some instructions, like comparisons and memory loads
    549 have operand types that differ from their return types.
    550 For instance, two floating points can be compared to give a
    551 word result (0 if the comparison succeeds, 1 if it fails).
    552 
    553     %c =w cgts %a, %b
    554 
    555 In the example above, both operands have to have single type.
    556 This is made explicit by the instruction suffix.
    557 
    558 The types of instructions are described below using a short
    559 type string.  A type string specifies all the valid return
    560 types an instruction can have, its arity, and the type of
    561 its arguments depending on its return type.
    562 
    563 Type strings begin with acceptable return types, then
    564 follows, in parentheses, the possible types for the arguments.
    565 If the N-th return type of the type string is used for an
    566 instruction, the arguments must use the N-th type listed for
    567 them in the type string.  When an instruction does not have a
    568 return type, the type string only contains the types of the
    569 arguments.
    570 
    571 The following abbreviations are used.
    572 
    573   * `T` stands for `wlsd`
    574   * `I` stands for `wl`
    575   * `F` stands for `sd`
    576   * `m` stands for the type of pointers on the target; on
    577     64-bit architectures it is the same as `l`
    578 
    579 For example, consider the type string `wl(F)`, it mentions
    580 that the instruction has only one argument and that if the
    581 return type used is long, the argument must be of type double.
    582 
    583 ~ Arithmetic and Bits
    584 ~~~~~~~~~~~~~~~~~~~~~
    585 
    586   * `add`, `sub`, `div`, `mul` -- `T(T,T)`
    587   * `neg` -- `T(T)`
    588   * `udiv`, `rem`, `urem` -- `I(I,I)`
    589   * `or`, `xor`, `and` -- `I(I,I)`
    590   * `sar`, `shr`, `shl` -- `I(I,ww)`
    591 
    592 The base arithmetic instructions in the first bullet are
    593 available for all types, integers and floating points.
    594 
    595 When `div` is used with word or long return type, the
    596 arguments are treated as signed.  The unsigned integral
    597 division is available as `udiv` instruction.  When the
    598 result of a division is not an integer, it is truncated
    599 towards zero.
    600 
    601 The signed and unsigned remainder operations are available
    602 as `rem` and `urem`.  The sign of the remainder is the same
    603 as the one of the dividend.  Its magnitude is smaller than
    604 the divisor one.  These two instructions and `udiv` are only
    605 available with integer arguments and result.
    606 
    607 Bitwise OR, AND, and XOR operations are available for both
    608 integer types.  Logical operations of typical programming
    609 languages can be implemented using <@ Comparisons > and
    610 <@ Jumps >.
    611 
    612 Shift instructions `sar`, `shr`, and `shl`, shift right or
    613 left their first operand by the amount from the second
    614 operand.  The shifting amount is taken modulo the size of
    615 the result type.  Shifting right can either preserve the
    616 sign of the value (using `sar`), or fill the newly freed
    617 bits with zeroes (using `shr`).  Shifting left always
    618 fills the freed bits with zeroes.
    619 
    620 Remark that an arithmetic shift right (`sar`) is only
    621 equivalent to a division by a power of two for non-negative
    622 numbers.  This is because the shift right "truncates"
    623 towards minus infinity, while the division truncates
    624 towards zero.
    625 
    626 ~ Memory
    627 ~~~~~~~~
    628 
    629   * Store instructions.
    630 
    631       * `stored` -- `(d,m)`
    632       * `stores` -- `(s,m)`
    633       * `storel` -- `(l,m)`
    634       * `storew` -- `(w,m)`
    635       * `storeh` -- `(w,m)`
    636       * `storeb` -- `(w,m)`
    637 
    638     Store instructions exist to store a value of any base type
    639     and any extended type.  Since halfwords and bytes are not
    640     first class in the IL, `storeh` and `storeb` take a word
    641     as argument.  Only the first 16 or 8 bits of this word will
    642     be stored in memory at the address specified in the second
    643     argument.
    644 
    645   * Load instructions.
    646 
    647       * `loadd` -- `d(m)`
    648       * `loads` -- `s(m)`
    649       * `loadl` -- `l(m)`
    650       * `loadsw`, `loaduw` -- `I(mm)`
    651       * `loadsh`, `loaduh` -- `I(mm)`
    652       * `loadsb`, `loadub` -- `I(mm)`
    653 
    654     For types smaller than long, two variants of the load
    655     instruction are available: one will sign extend the loaded
    656     value, while the other will zero extend it.  Note that
    657     all loads smaller than long can load to either a long or
    658     a word.
    659 
    660     The two instructions `loadsw` and `loaduw` have the same
    661     effect when they are used to define a word temporary.
    662     A `loadw` instruction is provided as syntactic sugar for
    663     `loadsw` to make explicit that the extension mechanism
    664     used is irrelevant.
    665 
    666   * Stack allocation.
    667 
    668       * `alloc4` -- `m(l)`
    669       * `alloc8` -- `m(l)`
    670       * `alloc16` -- `m(l)`
    671 
    672     These instructions allocate a chunk of memory on the
    673     stack.  The number ending the instruction name is the
    674     alignment required for the allocated slot.  QBE will
    675     make sure that the returned address is a multiple of
    676     that alignment value.
    677 
    678     Stack allocation instructions are used, for example,
    679     when compiling the C local variables, because their
    680     address can be taken.  When compiling Fortran,
    681     temporaries can be used directly instead, because
    682     it is illegal to take the address of a variable.
    683 
    684 The following example makes use some of the memory
    685 instructions.  Pointers are stored in long temporaries.
    686 
    687     %A0 =l alloc4 8      # stack allocate an array A of 2 words
    688     %A1 =l add %A0, 4
    689     storew 43,  %A0      # A[0] <- 43
    690     storew 255, %A1      # A[1] <- 255
    691     %v1 =w loadw  %A0    # %v1 <- A[0] as word
    692     %v2 =w loadsb %A1    # %v2 <- A[1] as signed byte
    693     %v3 =w add %v1, %v2  # %v3 is 42 here
    694 
    695 ~ Comparisons
    696 ~~~~~~~~~~~~~
    697 
    698 Comparison instructions return an integer value (either a word
    699 or a long), and compare values of arbitrary types.  The returned
    700 value is 1 if the two operands satisfy the comparison
    701 relation, or 0 otherwise.  The names of comparisons respect
    702 a standard naming scheme in three parts.
    703 
    704  1. All comparisons start with the letter `c`.
    705 
    706  2. Then comes a comparison type.  The following
    707     types are available for integer comparisons:
    708 
    709       * `eq` for equality
    710       * `ne` for inequality
    711       * `sle` for signed lower or equal
    712       * `slt` for signed lower
    713       * `sge` for signed greater or equal
    714       * `sgt` for signed greater
    715       * `ule` for unsigned lower or equal
    716       * `ult` for unsigned lower
    717       * `uge` for unsigned greater or equal
    718       * `ugt` for unsigned greater
    719 
    720     Floating point comparisons use one of these types:
    721 
    722       * `eq` for equality
    723       * `ne` for inequality
    724       * `le` for lower or equal
    725       * `lt` for lower
    726       * `ge` for greater or equal
    727       * `gt` for greater
    728       * `o` for ordered (no operand is a NaN)
    729       * `uo` for unordered (at least one operand is a NaN)
    730 
    731     Because floating point types always have a sign bit,
    732     all the comparisons available are signed.
    733 
    734  3. Finally, the instruction name is terminated with a
    735     basic type suffix precising the type of the operands
    736     to be compared.
    737 
    738 For example, `cod` (`I(dd,dd)`) compares two double-precision
    739 floating point numbers and returns 1 if the two floating points
    740 are not NaNs, or 0 otherwise.  The `csltw` (`I(ww,ww)`)
    741 instruction compares two words representing signed numbers and
    742 returns 1 when the first argument is smaller than the second one.
    743 
    744 ~ Conversions
    745 ~~~~~~~~~~~~~
    746 
    747 Conversion operations allow to change the representation of
    748 a value, possibly modifying it if the target type cannot hold
    749 the value of the source type.  Conversions can extend the
    750 precision of a temporary (e.g., from signed 8-bit to 32-bit),
    751 or convert a floating point into an integer and vice versa.
    752 
    753   * `extsw`, `extuw` -- `l(w)`
    754   * `extsh`, `extuh` -- `I(ww)`
    755   * `extsb`, `extub` -- `I(ww)`
    756   * `exts` -- `d(s)`
    757   * `truncd` -- `s(d)`
    758   * `stosi` -- `I(ss)`
    759   * `stoui` -- `I(ss)`
    760   * `dtosi` -- `I(dd)`
    761   * `dtoui` -- `I(dd)`
    762   * `swtof` -- `F(ww)`
    763   * `uwtof` -- `F(ww)`
    764   * `sltof` -- `F(ll)`
    765   * `ultof` -- `F(ll)`
    766 
    767 Extending the precision of a temporary is done using the
    768 `ext` family of instructions.  Because QBE types do not
    769 precise the signedness (like in LLVM), extension instructions
    770 exist to sign-extend and zero-extend a value.  For example,
    771 `extsb` takes a word argument and sign-extends the 8
    772 least-significant bits to a full word or long, depending on
    773 the return type.
    774 
    775 The instructions `exts` and `truncd` are provided to change
    776 the precision of a floating point value.  When the double
    777 argument of `truncd` cannot be represented as a
    778 single-precision floating point, it is truncated towards
    779 zero.
    780 
    781 Converting between signed integers and floating points is done
    782 using `stosi` (single to signed integer), `stoui` (single to
    783 unsigned integer, `dtosi` (double to signed integer), `dtoui`
    784 (double to unsigned integer), `swtof` (signed word to float),
    785 `uwtof` (unsigned word to float), `sltof` (signed long to
    786 float) and `ultof` (unsigned long to float).
    787 
    788 Because of <@ Subtyping >, there is no need to have an
    789 instruction to lower the precision of an integer temporary.
    790 
    791 ~ Cast and Copy
    792 ~~~~~~~~~~~~~~~
    793 
    794 The `cast` and `copy` instructions return the bits of their
    795 argument verbatim.  However a `cast` will change an integer
    796 into a floating point of the same width and vice versa.
    797 
    798   * `cast` -- `wlsd(sdwl)`
    799   * `copy` -- `T(T)`
    800 
    801 Casts can be used to make bitwise operations on the
    802 representation of floating point numbers.  For example
    803 the following program will compute the opposite of the
    804 single-precision floating point number `%f` into `%rs`.
    805 
    806     %b0 =w cast %f
    807     %b1 =w xor 2147483648, %b0  # flip the msb
    808     %rs =s cast %b1
    809 
    810 ~ Call
    811 ~~~~~~
    812 
    813     `bnf
    814     CALL := [%IDENT '=' ABITY] 'call' VAL '(' (ARG), ')'
    815 
    816     ARG :=
    817         ABITY VAL  # Regular argument
    818       | 'env' VAL  # Environment argument (first)
    819       | '...'      # Variadic marker
    820 
    821     ABITY := BASETY | :IDENT
    822 
    823 The call instruction is special in several ways.  It is not
    824 a three-address instruction and requires the type of all
    825 its arguments to be given.  Also, the return type can be
    826 either a base type or an aggregate type.  These specifics
    827 are required to compile calls with C compatibility (i.e.,
    828 to respect the ABI).
    829 
    830 When an aggregate type is used as argument type or return
    831 type, the value respectively passed or returned needs to be
    832 a pointer to a memory location holding the value.  This is
    833 because aggregate types are not first-class citizens of
    834 the IL.
    835 
    836 Unless the called function does not return a value, a
    837 return temporary must be specified, even if it is never
    838 used afterwards.
    839 
    840 An environment parameter can be passed as first argument
    841 using the `env` keyword.  The passed value must be a 64-bit
    842 integer.  If the called function does not expect an environment
    843 parameter, it will be safely discarded.  See the <@ Functions >
    844 section for more information about environment parameters.
    845 
    846 When the called function is variadic, there must be a `...`
    847 marker separating the named and variadic arguments.
    848 
    849 ~ Variadic
    850 ~~~~~~~~~~
    851 
    852 The `vastart` and `vaarg` instructions provide a portable
    853 way to access the extra parameters of a variadic function.
    854 
    855   * `vastart` -- `(m)`
    856   * `vaarg` -- `T(mmmm)`
    857 
    858 The `vastart` instruction initializes a *variable argument
    859 list* used to access the extra parameters of the enclosing
    860 variadic function.  It is safe to call it multiple times.
    861 
    862 The `vaarg` instruction fetches the next argument from
    863 a variable argument list.  It is currently limited to
    864 fetching arguments that have a base type.  This instruction
    865 is essentially effectful: calling it twice in a row will
    866 return two consecutive arguments from the argument list.
    867 
    868 Both instructions take a pointer to a variable argument
    869 list as sole argument.  The size and alignment of variable
    870 argument lists depend on the target used.  However, it
    871 is possible to conservatively use the maximum size and
    872 alignment required by all the targets.
    873 
    874     type :valist = align 8 { 24 }  # For amd64_sysv
    875     type :valist = align 8 { 32 }  # For arm64
    876     type :valist = align 8 { 8 }   # For rv64
    877 
    878 The following example defines a variadic function adding
    879 its first three arguments.
    880 
    881     function s $add3(s %a, ...) {
    882     @start
    883             %ap =l alloc8 32
    884             vastart %ap
    885             %r =s call $vadd(s %a, l %ap)
    886             ret %r
    887     }
    888 
    889     function s $vadd(s %a, l %ap) {
    890     @start
    891             %b =s vaarg %ap
    892             %c =s vaarg %ap
    893             %d =s add %a, %b
    894             %e =s add %d, %c
    895             ret %e
    896     }
    897 
    898 ~ Phi
    899 ~~~~~
    900 
    901     `bnf
    902     PHI := %IDENT '=' BASETY 'phi' ( @IDENT VAL ),
    903 
    904 First and foremost, phi instructions are NOT necessary when
    905 writing a frontend to QBE.  One solution to avoid having to
    906 deal with SSA form is to use stack allocated variables for
    907 all source program variables and perform assignments and
    908 lookups using <@ Memory > operations.  This is what LLVM
    909 users typically do.
    910 
    911 Another solution is to simply emit code that is not in SSA
    912 form!  Contrary to LLVM, QBE is able to fixup programs not
    913 in SSA form without requiring the boilerplate of loading
    914 and storing in memory.  For example, the following program
    915 will be correctly compiled by QBE.
    916 
    917     @start
    918             %x =w copy 100
    919             %s =w copy 0
    920     @loop
    921             %s =w add %s, %x
    922             %x =w sub %x, 1
    923             jnz %x, @loop, @end
    924     @end
    925             ret %s
    926 
    927 Now, if you want to know what phi instructions are and how
    928 to use them in QBE, you can read the following.
    929 
    930 Phi instructions are specific to SSA form.  In SSA form
    931 values can only be assigned once, without phi instructions,
    932 this requirement is too strong to represent many programs.
    933 For example consider the following C program.
    934 
    935     int f(int x) {
    936             int y;
    937             if (x)
    938                     y = 1;
    939             else
    940                     y = 2;
    941             return y;
    942     }
    943 
    944 The variable `y` is assigned twice, the solution to
    945 translate it in SSA form is to insert a phi instruction.
    946 
    947     @ifstmt
    948             jnz %x, @ift, @iff
    949     @ift
    950             jmp @retstmt
    951     @iff
    952             jmp @retstmt
    953     @retstmt
    954             %y =w phi @ift 1, @iff 2
    955             ret %y
    956 
    957 Phi instructions return one of their arguments depending
    958 on where the control came from.  In the example, `%y` is
    959 set to 1 if the `@ift` branch is taken, or it is set to
    960 2 otherwise.
    961 
    962 An important remark about phi instructions is that QBE
    963 assumes that if a variable is defined by a phi it respects
    964 all the SSA invariants.  So it is critical to not use phi
    965 instructions unless you know exactly what you are doing.
    966 
    967 - 8. Instructions Index
    968 -----------------------
    969 
    970   * <@ Arithmetic and Bits >:
    971 
    972       * `add`
    973       * `and`
    974       * `div`
    975       * `mul`
    976       * `neg`
    977       * `or`
    978       * `rem`
    979       * `sar`
    980       * `shl`
    981       * `shr`
    982       * `sub`
    983       * `udiv`
    984       * `urem`
    985       * `xor`
    986 
    987   * <@ Memory >:
    988 
    989       * `alloc16`
    990       * `alloc4`
    991       * `alloc8`
    992       * `loadd`
    993       * `loadl`
    994       * `loads`
    995       * `loadsb`
    996       * `loadsh`
    997       * `loadsw`
    998       * `loadub`
    999       * `loaduh`
   1000       * `loaduw`
   1001       * `loadw`
   1002       * `storeb`
   1003       * `stored`
   1004       * `storeh`
   1005       * `storel`
   1006       * `stores`
   1007       * `storew`
   1008 
   1009   * <@ Comparisons >:
   1010 
   1011       * `ceqd`
   1012       * `ceql`
   1013       * `ceqs`
   1014       * `ceqw`
   1015       * `cged`
   1016       * `cges`
   1017       * `cgtd`
   1018       * `cgts`
   1019       * `cled`
   1020       * `cles`
   1021       * `cltd`
   1022       * `clts`
   1023       * `cned`
   1024       * `cnel`
   1025       * `cnes`
   1026       * `cnew`
   1027       * `cod`
   1028       * `cos`
   1029       * `csgel`
   1030       * `csgew`
   1031       * `csgtl`
   1032       * `csgtw`
   1033       * `cslel`
   1034       * `cslew`
   1035       * `csltl`
   1036       * `csltw`
   1037       * `cugel`
   1038       * `cugew`
   1039       * `cugtl`
   1040       * `cugtw`
   1041       * `culel`
   1042       * `culew`
   1043       * `cultl`
   1044       * `cultw`
   1045       * `cuod`
   1046       * `cuos`
   1047 
   1048   * <@ Conversions >:
   1049 
   1050       * `dtosi`
   1051       * `dtoui`
   1052       * `exts`
   1053       * `extsb`
   1054       * `extsh`
   1055       * `extsw`
   1056       * `extub`
   1057       * `extuh`
   1058       * `extuw`
   1059       * `sltof`
   1060       * `ultof`
   1061       * `stosi`
   1062       * `stoui`
   1063       * `swtof`
   1064       * `uwtof`
   1065       * `truncd`
   1066 
   1067   * <@ Cast and Copy > :
   1068 
   1069       * `cast`
   1070       * `copy`
   1071 
   1072   * <@ Call >:
   1073 
   1074       * `call`
   1075 
   1076   * <@ Variadic >:
   1077 
   1078       * `vastart`
   1079       * `vaarg`
   1080 
   1081   * <@ Phi >:
   1082 
   1083       * `phi`
   1084 
   1085   * <@ Jumps >:
   1086 
   1087       * `jmp`
   1088       * `jnz`
   1089       * `ret`