qute

   1% SPDX-FileCopyrightText: 2015-2024 Quentin Carbonneaux <quentin@c9x.me>
   2% SPDX-FileCopyrightText: 2025-2026 Sören Tempel <soeren+git@soeren-tempel.net>
   3%
   4% SPDX-License-Identifier: MIT AND GPL-3.0-only
   5
   6\documentclass{article}
   7%include polycode.fmt
   8
   9%subst blankline = "\\[5mm]"
  10
  11% See https://github.com/kosmikus/lhs2tex/issues/58
  12%format <$> = "\mathbin{\langle\$\rangle}"
  13%format <&> = "\mathbin{\langle\&\rangle}"
  14%format <|> = "\mathbin{\langle\:\vline\:\rangle}"
  15%format <?> = "\mathbin{\langle?\rangle}"
  16%format <*> = "\mathbin{\langle*\rangle}"
  17%format <*  = "\mathbin{\langle*}"
  18%format *>  = "\mathbin{*\rangle}"
  19
  20\long\def\ignore#1{}
  21
  22\usepackage{hyperref}
  23\hypersetup{
  24	colorlinks = true,
  25}
  26
  27\begin{document}
  28
  29\title{QBE Intermediate Language\vspace{-2em}}
  30\date{}
  31\maketitle
  32\frenchspacing
  33
  34\ignore{
  35\begin{code}
  36module Language.QBE.Parser
  37  ( skipInitComments,
  38    dataDef,
  39    typeDef,
  40    funcDef,
  41    fileDef
  42  )
  43where
  44
  45import Control.Monad (foldM)
  46import Data.Char (chr)
  47import Data.Word (Word64)
  48import Data.Functor ((<&>))
  49import Data.List (singleton)
  50import Data.Map (Map)
  51import Data.Map qualified as Map
  52import qualified Language.QBE.Types as Q
  53import Language.QBE.Util (bind, decNumber, octNumber, float)
  54import Text.ParserCombinators.Parsec
  55  ( Parser,
  56    alphaNum,
  57    anyChar,
  58    between,
  59    char,
  60    choice,
  61    letter,
  62    many,
  63    many1,
  64    manyTill,
  65    newline,
  66    noneOf,
  67    oneOf,
  68    optional,
  69    optionMaybe,
  70    sepBy,
  71    sepBy1,
  72    skipMany,
  73    skipMany1,
  74    string,
  75    try,
  76    (<?>),
  77    (<|>),
  78  )
  79\end{code}
  80}
  81
  82This an executable description of the
  83\href{https://c9x.me/compile/doc/il-v1.2.html}{QBE intermediate language},
  84specified through \href{https://hackage.haskell.org/package/parsec}{Parsec}
  85parser combinators and generated from a literate Haskell file. The description
  86is derived from the original QBE IL documentation, licensed under MIT.
  87Presently, this implementation targets version 1.2 of the QBE intermediate
  88language and aims to be equivalent with the original specification.
  89
  90\section{Basic Concepts}
  91
  92The intermediate language (IL) is a higher-level language than the
  93machine's assembly language. It smoothes most of the
  94irregularities of the underlying hardware and allows an infinite number
  95of temporaries to be used. This higher abstraction level lets frontend
  96programmers focus on language design issues.
  97
  98\subsection{Input Files}
  99
 100The intermediate language is provided to QBE as text. Usually, one file
 101is generated per each compilation unit from the frontend input language.
 102An IL file is a sequence of \nameref{sec:definitions} for
 103data, functions, and types. Once processed by QBE, the resulting file
 104can be assembled and linked using a standard toolchain (e.g., GNU
 105binutils).
 106
 107\begin{code}
 108comment :: Parser ()
 109comment = skipMany blankNL >> comment' >> skipMany blankNL
 110  where
 111    comment' = char '#' >> manyTill anyChar newline
 112\end{code}
 113
 114\ignore{
 115\begin{code}
 116skipNoCode :: Parser () -> Parser ()
 117skipNoCode blankP = try (skipMany1 comment <?> "comments") <|> blankP
 118\end{code}
 119}
 120
 121Here is a complete "Hello World" IL file which defines a function that
 122prints to the screen. Since the string is not a first class object (only
 123the pointer is) it is defined outside the function\textquotesingle s
 124body. Comments start with a \# character and finish with the end of the
 125line.
 126
 127\begin{verbatim}
 128data $str = { b "hello world", b 0 }
 129
 130export function w $main() {
 131@start
 132        # Call the puts function with $str as argument.
 133        %r =w call $puts(l $str)
 134        ret 0
 135}
 136\end{verbatim}
 137
 138If you have read the LLVM language reference, you might recognize the
 139example above. In comparison, QBE makes a much lighter use of types and
 140the syntax is terser.
 141
 142\subsection{Parser Combinators}
 143
 144\ignore{
 145\begin{code}
 146bracesNL :: Parser a -> Parser a
 147bracesNL = between (wsNL $ char '{') (wsNL $ char '}')
 148
 149quoted :: Parser a -> Parser a
 150quoted = let q = char '"' in between q q
 151
 152sepByTrail1 :: Parser a -> Parser sep -> Parser [a]
 153sepByTrail1 p sep = do
 154  x <- p
 155  xs <- many (try $ sep >> p)
 156  _ <- optional sep
 157  return (x:xs)
 158
 159sepByTrail :: Parser a -> Parser sep -> Parser [a]
 160sepByTrail p sep = sepByTrail1 p sep <|> return []
 161
 162parenLst :: Parser a -> Parser [a]
 163parenLst p = between (ws $ char '(') (char ')') inner
 164  where
 165    inner = sepBy (ws p) (ws $ char ',')
 166
 167unaryInstr :: (Q.Value -> Q.Instr) -> String -> Parser Q.Instr
 168unaryInstr conc keyword = do
 169  _ <- ws (string keyword)
 170  conc <$> ws val
 171
 172binaryInstr :: (Q.Value -> Q.Value -> Q.Instr) -> String -> Parser Q.Instr
 173binaryInstr conc keyword = do
 174  _ <- ws (string keyword)
 175  vfst <- ws val <* ws (char ',')
 176  conc vfst <$> ws val
 177
 178-- Can only appear in data and type definitions and hence allows newlines.
 179alignAny :: Parser Word64
 180alignAny = (ws1 (string "align")) >> wsNL decNumber
 181
 182-- Returns true if it is signed.
 183signageChar :: Parser Bool
 184signageChar = (char 's' <|> char 'u') <&> (== 's')
 185\end{code}
 186}
 187
 188The original QBE specification defines the syntax using a BNF grammar. In
 189contrast, this document defines it using Parsec parser combinators. As such,
 190this specification is less formal but more accurate as the parsing code is
 191actually executable. Consequently, this specification also captures constructs
 192omitted in the original specification (e.g., \nameref{sec:identifiers}, or
 193\nameref{sec:strlit}). Nonetheless, the formal language recognized by these
 194combinators aims to be equivalent to the one of the BNF grammar.
 195
 196\subsection{Identifiers}
 197\label{sec:identifiers}
 198
 199% Ident is not documented in the original QBE specification.
 200% See https://c9x.me/git/qbe.git/tree/parse.c?h=v1.2#n304
 201
 202\begin{code}
 203ident :: Parser String
 204ident = do
 205  start <- letter <|> oneOf "._"
 206  rest <- many (alphaNum <|> oneOf "$._")
 207  return $ start : rest
 208\end{code}
 209
 210Identifiers for data, types, and functions can start with any ASCII letter or
 211the special characters \texttt{.} and \texttt{\_}. This initial character can
 212be followed by a sequence of zero or more alphanumeric characters and the
 213special characters \texttt{\$}, \texttt{.}, and \texttt{\_}.
 214
 215\subsection{Sigils}
 216
 217\begin{code}
 218userDef :: Parser Q.UserIdent
 219userDef = Q.UserIdent <$> (char ':' >> ident)
 220
 221global :: Parser Q.GlobalIdent
 222global = Q.GlobalIdent <$> (char '$' >> ident)
 223
 224local :: Parser Q.LocalIdent
 225local = Q.LocalIdent <$> (char '%' >> ident)
 226
 227label :: Parser Q.BlockIdent
 228label = Q.BlockIdent <$> (char '@' >> ident)
 229\end{code}
 230
 231The intermediate language makes heavy use of sigils, all user-defined
 232names are prefixed with a sigil. This is to avoid keyword conflicts, and
 233also to quickly spot the scope and nature of identifiers.
 234
 235\begin{itemize}
 236  \item \texttt{:} is for user-defined \nameref{sec:aggregate-types}
 237  \item \texttt{\$} is for globals (represented by a pointer)
 238  \item \texttt{\%} is for function-scope temporaries
 239  \item \texttt{@@} is for block labels
 240\end{itemize}
 241
 242\subsection{Spacing}
 243
 244\begin{code}
 245blank :: Parser Char
 246blank = oneOf "\t " <?> "blank"
 247
 248blankNL :: Parser Char
 249blankNL = oneOf "\n\t " <?> "blank or newline"
 250\end{code}
 251
 252Individual tokens in IL files must be separated by one or more spacing
 253characters. Both spaces and tabs are recognized as spacing characters.
 254In data and type definitions, newlines may also be used as spaces to
 255prevent overly long lines. When exactly one of two consecutive tokens is
 256a symbol (for example \texttt{,} or \texttt{=} or \texttt{\{}), spacing may be omitted.
 257
 258\ignore{
 259\begin{code}
 260ws :: Parser a -> Parser a
 261ws p = p <* skipMany blank
 262
 263ws1 :: Parser a -> Parser a
 264ws1 p = p <* skipMany1 blank
 265
 266wsNL :: Parser a -> Parser a
 267wsNL p = p <* skipNoCode (skipMany blankNL)
 268
 269wsNL1 :: Parser a -> Parser a
 270wsNL1 p = p <* skipNoCode (skipMany1 blankNL)
 271
 272-- Only intended to be used to skip comments at the start of a file.
 273skipInitComments :: Parser ()
 274skipInitComments = skipNoCode (skipMany blankNL)
 275\end{code}
 276}
 277
 278\subsection{String Literals}
 279\label{sec:strlit}
 280
 281% The string literal is not documented in the original QBE specification.
 282% See https://c9x.me/git/qbe.git/tree/parse.c?h=v1.2#n287
 283
 284\begin{code}
 285strLit :: Parser String
 286strLit = concat <$> quoted (many strChr)
 287  where
 288    strChr :: Parser [Char]
 289    strChr = (singleton <$> noneOf "\"\\") <|> escSeq
 290
 291    -- TODO: not documnted in the QBE BNF.
 292    octEsc :: Parser Char
 293    octEsc = do
 294      n <- octNumber
 295      pure $ chr (fromIntegral n)
 296
 297    escSeq :: Parser [Char]
 298    escSeq = try $ do
 299      esc <- char '\\'
 300      (singleton <$> octEsc) <|> (anyChar <&> (\c -> [esc, c]))
 301\end{code}
 302
 303Strings are enclosed by double quotes and are, for example, used to specify a
 304section name as part of the \nameref{sec:linkage} information. Within a string,
 305a double quote can be escaped using a \texttt{\textbackslash} character. All
 306escape sequences, including double quote escaping, are passed through as-is to
 307the generated assembly file.
 308
 309\section{Types}
 310
 311\subsection{Simple Types}
 312
 313The IL makes minimal use of types. By design, the types used are
 314restricted to what is necessary for unambiguous compilation to machine
 315code and C interfacing. Unlike LLVM, QBE is not using types as a means
 316to safety; they are only here for semantic purposes.
 317
 318\begin{code}
 319baseType :: Parser Q.BaseType
 320baseType = choice
 321  [ bind "w" Q.Word
 322  , bind "l" Q.Long
 323  , bind "s" Q.Single
 324  , bind "d" Q.Double ]
 325\end{code}
 326
 327The four base types are \texttt{w} (word), \texttt{l} (long), \texttt{s} (single), and \texttt{d}
 328(double), they stand respectively for 32-bit and 64-bit integers, and
 32932-bit and 64-bit floating-point numbers. There are no pointer types
 330available; pointers are typed by an integer type sufficiently wide to
 331represent all memory addresses (e.g., \texttt{l} on 64-bit architectures).
 332Temporaries in the IL can only have a base type.
 333
 334\begin{code}
 335extType :: Parser Q.ExtType
 336extType = (Q.Base <$> baseType)
 337       <|> bind "b" Q.Byte
 338       <|> bind "h" Q.HalfWord
 339\end{code}
 340
 341Extended types contain base types plus \texttt{b} (byte) and \texttt{h} (half word),
 342respectively for 8-bit and 16-bit integers. They are used in \nameref{sec:aggregate-types}
 343and \nameref{sec:data} definitions.
 344
 345For C interfacing, the IL also provides user-defined aggregate types as
 346well as signed and unsigned variants of the sub-word extended types.
 347Read more about these types in the \nameref{sec:aggregate-types}
 348and \nameref{sec:functions} sections.
 349
 350\subsection{Subtyping}
 351\label{sec:subtyping}
 352
 353The IL has a minimal subtyping feature, for integer types only. Any
 354value of type \texttt{l} can be used in a \texttt{w} context. In that case, only the
 35532 least significant bits of the word value are used.
 356
 357Make note that it is the opposite of the usual subtyping on integers (in
 358C, we can safely use an \texttt{int} where a \texttt{long} is expected). A long value
 359cannot be used in word context. The rationale is that a word can be
 360signed or unsigned, so extending it to a long could be done in two ways,
 361either by zero-extension, or by sign-extension.
 362
 363\subsection{Constants and Vals}
 364\label{sec:constants-and-vals}
 365
 366\begin{code}
 367dynConst :: Parser Q.DynConst
 368dynConst =
 369  (Q.Const <$> constant)
 370    <|> (Q.Thread <$> (key "thread" >> global))
 371    <|> (Q.Common <$> (key "common" >> global))
 372    <|> (Q.Extern <$> try (key "extern" >> global))
 373    <|> (Q.ExternThread <$> (key "extern" >> key "thread" >> global))
 374    <?> "dynconst"
 375  where
 376    key s = ws1 $ string s
 377\end{code}
 378
 379Constants come in two kinds: compile-time constants and dynamic
 380constants. Dynamic constants include compile-time constants and other
 381symbol variants that are only known at program-load time or execution
 382time. Consequently, dynamic constants can only occur in function bodies.
 383
 384When the \texttt{extern} keyword prefixes a symbol name, the symbol is
 385accessed indirectly through a table edited by the dynamic linker (e.g.,
 386GOT/PLT). This enables PIE/PIC code generation. When \texttt{extern} is
 387combined with \texttt{thread}, the symbol is accessed using the
 388initial-exec TLS model, suitable for thread-local variables defined in
 389shared objects available at startup time (i.e., not loaded through
 390dlopen).
 391
 392The representation of integers is two's complement.
 393Floating-point numbers are represented using the single-precision and
 394double-precision formats of the IEEE 754 standard.
 395
 396\begin{code}
 397constant :: Parser Q.Const
 398constant =
 399  (Q.Number <$> decNumber)
 400    <|> (Q.SFP <$> sfp)
 401    <|> (Q.DFP <$> dfp)
 402    <|> (Q.Global <$> global)
 403    <?> "const"
 404  where
 405    sfp = string "s_" >> float
 406    dfp = string "d_" >> float
 407\end{code}
 408
 409Constants specify a sequence of bits and are untyped. They are always
 410parsed as 64-bit blobs. Depending on the context surrounding a constant,
 411only some of its bits are used. For example, in the program below, the
 412two variables defined have the same value since the first operand of the
 413subtraction is a word (32-bit) context.
 414
 415\begin{verbatim}
 416%x =w sub -1, 0 %y =w sub 4294967295, 0
 417\end{verbatim}
 418
 419Because specifying floating-point constants by their bits makes the code
 420less readable, syntactic sugar is provided to express them. Standard
 421scientific notation is prefixed with \texttt{s\_} and \texttt{d\_} for single and
 422double precision numbers respectively. Once again, the following example
 423defines twice the same double-precision constant.
 424
 425\begin{verbatim}
 426%x =d add d_0, d_-1
 427%y =d add d_0, -4616189618054758400
 428\end{verbatim}
 429
 430Global symbols can also be used directly as constants; they will be
 431resolved and turned into actual numeric constants by the linker.
 432
 433When the \texttt{thread} keyword prefixes a symbol name, the
 434symbol\textquotesingle s numeric value is resolved at runtime in the
 435thread-local storage.
 436
 437\begin{code}
 438val :: Parser Q.Value
 439val =
 440  (Q.VConst <$> dynConst)
 441    <|> (Q.VLocal <$> local)
 442    <?> "val"
 443\end{code}
 444
 445Vals are used as arguments in regular, phi, and jump instructions within
 446function definitions. They are either constants or function-scope
 447temporaries.
 448
 449\subsection{Linkage}
 450\label{sec:linkage}
 451
 452\begin{code}
 453linkage :: Parser Q.Linkage
 454linkage =
 455  wsNL (bind "export" Q.LExport)
 456    <|> wsNL (bind "common" Q.LCommon)
 457    <|> wsNL (bind "thread" Q.LThread)
 458    <|> do
 459      _ <- ws1 $ string "section"
 460      (try secWithFlags) <|> sec
 461  where
 462    sec :: Parser Q.Linkage
 463    sec = wsNL strLit <&> (`Q.LSection` Nothing)
 464
 465    secWithFlags :: Parser Q.Linkage
 466    secWithFlags = do
 467      n <- ws1 strLit
 468      wsNL strLit <&> Q.LSection n . Just
 469\end{code}
 470
 471Function and data definitions (see below) can specify linkage
 472information to be passed to the assembler and eventually to the linker.
 473
 474The \texttt{export} linkage flag marks the defined item as visible outside the
 475current file\textquotesingle s scope. If absent, the symbol can only be
 476referred to locally. Functions compiled by QBE and called from C need to
 477be exported.
 478
 479The \texttt{thread} linkage flag can only qualify data definitions. It mandates
 480that the object defined is stored in thread-local storage. Each time a
 481runtime thread starts, the supporting platform runtime is in charge of
 482making a new copy of the object for the fresh thread. Objects in
 483thread-local storage must be accessed using the \texttt{thread \$IDENT} syntax,
 484as specified in the \nameref{sec:constants-and-vals} section.
 485
 486A \texttt{section} flag can be specified to tell the linker to put the defined
 487item in a certain section. The use of the section flag is platform
 488dependent and we refer the user to the documentation of their assembler
 489and linker for relevant information.
 490
 491\begin{verbatim}
 492section ".init_array" data $.init.f = { l $f }
 493\end{verbatim}
 494
 495The section flag can be used to add function pointers to a global
 496initialization list, as depicted above. Note that some platforms provide
 497a BSS section that can be used to minimize the footprint of uniformly
 498zeroed data. When this section is available, QBE will automatically make
 499use of it and no section flag is required.
 500
 501The section and export linkage flags should each appear at most once in
 502a definition. If multiple occurrences are present, QBE is free to use
 503any.
 504
 505\subsection{Definitions}
 506\label{sec:definitions}
 507
 508Definitions are the essential components of an IL file. They can define
 509three types of objects: aggregate types, data, and functions. Aggregate
 510types are never exported and do not compile to any code. Data and
 511function definitions have file scope and are mutually recursive (even
 512across IL files). Their visibility can be controlled using linkage
 513flags.
 514
 515\subsubsection{Aggregate Types}
 516\label{sec:aggregate-types}
 517
 518\begin{code}
 519typeDef :: Parser Q.TypeDef
 520typeDef = do
 521  _ <- wsNL1 (string "type")
 522  i <- wsNL1 userDef
 523  _ <- wsNL1 (char '=')
 524  a <- optionMaybe alignAny
 525  bracesNL (opaqueType <|> unionType <|> regularType) <&> Q.TypeDef i a
 526\end{code}
 527
 528Aggregate type definitions start with the \texttt{type} keyword. They have file
 529scope, but types must be defined before being referenced. The inner
 530structure of a type is expressed by a comma-separated list of fields.
 531
 532\begin{code}
 533subType :: Parser Q.SubType
 534subType =
 535  (Q.SExtType <$> extType)
 536    <|> (Q.SUserDef <$> userDef)
 537
 538field :: Parser Q.Field
 539field = do
 540  -- TODO: newline is required if there is a number argument
 541  f <- wsNL subType
 542  s <- ws $ optionMaybe decNumber
 543  pure (f, s)
 544
 545fields :: Bool -> Parser [Q.Field]
 546fields allowEmpty =
 547  (if allowEmpty then sepByTrail else sepByTrail1) field (wsNL $ char ',')
 548\end{code}
 549
 550A field consists of a subtype, either an extended type or a user-defined type,
 551and an optional number expressing the value of this field. In case many items
 552of the same type are sequenced (like in a C array), the shorter array syntax
 553can be used.
 554
 555\begin{code}
 556regularType :: Parser Q.AggType
 557regularType = Q.ARegular <$> fields True
 558\end{code}
 559
 560Three different kinds of aggregate types are presentl ysupported: regular
 561types, union types and opaque types. The fields of regular types will be
 562packed. By default, the alignment of an aggregate type is the maximum alignment
 563of its members. The alignment can be explicitly specified by the programmer.
 564
 565\begin{code}
 566unionType :: Parser Q.AggType
 567unionType = Q.AUnion <$> many1 (wsNL unionType')
 568  where
 569    unionType' :: Parser [Q.Field]
 570    unionType' = bracesNL $ fields False
 571\end{code}
 572
 573Union types allow the same chunk of memory to be used with different layouts. They are defined by enclosing multiple regular aggregate type bodies in a pair of curly braces. Size and alignment of union types are set to the maximum size and alignment of each variation or, in the case of alignment, can be explicitly specified.
 574
 575\begin{code}
 576opaqueType :: Parser Q.AggType
 577opaqueType = Q.AOpaque <$> wsNL decNumber
 578\end{code}
 579
 580Opaque types are used when the inner structure of an aggregate cannot be specified; the alignment for opaque types is mandatory. They are defined simply by enclosing their size between curly braces.
 581
 582\subsubsection{Data}
 583\label{sec:data}
 584
 585\begin{code}
 586dataDef :: Parser Q.DataDef
 587dataDef = do
 588  link <- many linkage
 589  name <- wsNL1 (string "data") >> wsNL global
 590  _ <- wsNL (char '=')
 591  alignment <- optionMaybe alignAny
 592  bracesNL dataObjs <&> Q.DataDef link name alignment
 593 where
 594    -- TODO: sepByTrail is not documented in the QBE BNF.
 595    dataObjs = sepByTrail dataObj (wsNL $ char ',')
 596\end{code}
 597
 598Data definitions express objects that will be emitted in the compiled
 599file. Their visibility and location in the compiled artifact are
 600controlled with linkage flags described in the \nameref{sec:linkage}
 601section.
 602
 603They define a global identifier (starting with the sigil \texttt{\$}), that
 604will contain a pointer to the object specified by the definition.
 605
 606\begin{code}
 607dataObj :: Parser Q.DataObj
 608dataObj =
 609  (Q.OZeroFill <$> (wsNL1 (char 'z') >> wsNL decNumber))
 610    <|> do
 611      t <- wsNL1 extType
 612      i <- many1 (wsNL dataItem)
 613      return $ Q.OItem t i
 614\end{code}
 615
 616Objects are described by a sequence of fields that start with a type
 617letter. This letter can either be an extended type, or the \texttt{z} letter.
 618If the letter used is an extended type, the data item following
 619specifies the bits to be stored in the field.
 620
 621\begin{code}
 622dataItem :: Parser Q.DataItem
 623dataItem =
 624  (Q.DString <$> strLit)
 625    <|> try
 626      ( do
 627          i <- ws global
 628          off <- (ws $ char '+') >> ws decNumber
 629          return $ Q.DSymOff i off
 630      )
 631    <|> (Q.DConst <$> constant)
 632\end{code}
 633
 634Within each object, several items can be defined. When several data items
 635follow a letter, they initialize multiple fields of the same size.
 636
 637\begin{code}
 638allocSize :: Parser Q.AllocSize
 639allocSize =
 640  choice
 641    [ bind "4" Q.AllocWord,
 642      bind "8" Q.AllocLong,
 643      bind "16" Q.AllocLongLong
 644    ]
 645\end{code}
 646
 647The members of a struct will be packed. This means that padding has to
 648be emitted by the frontend when necessary. Alignment of the whole data
 649objects can be manually specified, and when no alignment is provided,
 650the maximum alignment from the platform is used.
 651
 652When the \texttt{z} letter is used the number following indicates the size of
 653the field; the contents of the field are zero initialized. It can be
 654used to add padding between fields or zero-initialize big arrays.
 655
 656\subsubsection{Functions}
 657\label{sec:functions}
 658
 659\begin{code}
 660funcDef :: Parser Q.FuncDef
 661funcDef = do
 662  link <- many linkage
 663  _ <- ws1 (string "function")
 664  retTy <- optionMaybe (ws1 abity)
 665  name <- ws global
 666  args <- wsNL params
 667  body <- between (wsNL1 $ char '{') (wsNL $ char '}') $ many1 block
 668
 669  case (insertJumps body) of
 670    Nothing -> fail $ "invalid fallthrough in " ++ show name
 671    Just [] -> error "unreachable" -- TODO: Use NonEmpty
 672    Just blocks@(startBlk:_) ->
 673      return $
 674        Q.FuncDef {
 675          Q.fLinkage = link,
 676          Q.fName = name,
 677          Q.fStart = Q.label startBlk,
 678          Q.fAbity = retTy,
 679          Q.fParams = args,
 680          Q.fBlock = blkMap blocks
 681        }
 682\end{code}
 683
 684Function definitions contain the actual code to emit in the compiled
 685file. They define a global symbol that contains a pointer to the
 686function code. This pointer can be used in \texttt{call} instructions or stored
 687in memory.
 688
 689\begin{code}
 690subWordType :: Parser Q.SubWordType
 691subWordType = choice
 692  [ try $ bind "sb" Q.SignedByte
 693  , try $ bind "ub" Q.UnsignedByte
 694  , bind "sh" Q.SignedHalf
 695  , bind "uh" Q.UnsignedHalf ]
 696
 697abity :: Parser Q.Abity
 698abity = try (Q.ASubWordType <$> subWordType)
 699    <|> (Q.ABase <$> baseType)
 700    <|> (Q.AUserDef <$> userDef)
 701\end{code}
 702
 703The type given right before the function name is the return type of the
 704function. All return values of this function must have this return type.
 705If the return type is missing, the function must not return any value.
 706
 707\begin{code}
 708param :: Parser Q.FuncParam
 709param = (Q.Env <$> (ws1 (string "env") >> local))
 710    <|> (string "..." >> pure Q.Variadic)
 711    <|> do
 712          ty <- ws1 abity
 713          Q.Regular ty <$> local
 714
 715params :: Parser [Q.FuncParam]
 716params = parenLst param
 717\end{code}
 718
 719The parameter list is a comma separated list of temporary names prefixed
 720by types. The types are used to correctly implement C compatibility.
 721When an argument has an aggregate type, a pointer to the aggregate is
 722passed by thea caller. In the example below, we have to use a load
 723instruction to get the value of the first (and only) member of the
 724struct.
 725
 726\begin{verbatim}
 727type :one = { w }
 728
 729function w $getone(:one %p) {
 730@start
 731        %val =w loadw %p
 732        ret %val
 733}
 734\end{verbatim}
 735
 736If a function accepts or returns values that are smaller than a word,
 737such as \texttt{signed char} or \texttt{unsigned short} in C, one of the sub-word type
 738must be used. The sub-word types \texttt{sb}, \texttt{ub}, \texttt{sh}, and \texttt{uh} stand,
 739respectively, for signed and unsigned 8-bit values, and signed and
 740unsigned 16-bit values. Parameters associated with a sub-word type of
 741bit width N only have their N least significant bits set and have base
 742type \texttt{w}. For example, the function
 743
 744\begin{verbatim}
 745function w $addbyte(w %a, sb %b) {
 746@start
 747        %bw =w extsb %b
 748        %val =w add %a, %bw
 749        ret %val
 750}
 751\end{verbatim}
 752
 753needs to sign-extend its second argument before the addition. Dually,
 754return values with sub-word types do not need to be sign or zero
 755extended.
 756
 757If the parameter list ends with \texttt{...}, the function is a variadic
 758function: it can accept a variable number of arguments. To access the
 759extra arguments provided by the caller, use the \texttt{vastart} and \texttt{vaarg}
 760instructions described in the \nameref{sec:variadic} section.
 761
 762Optionally, the parameter list can start with an environment parameter
 763\texttt{env \%e}. This special parameter is a 64-bit integer temporary (i.e.,
 764of type \texttt{l}). If the function does not use its environment parameter,
 765callers can safely omit it. This parameter is invisible to a C caller:
 766for example, the function
 767
 768\begin{verbatim}
 769export function w $add(env %e, w %a, w %b) {
 770@start
 771        %c =w add %a, %b
 772        ret %c
 773}
 774\end{verbatim}
 775
 776must be given the C prototype \texttt{int add(int, int)}. The intended use of
 777this feature is to pass the environment pointer of closures while
 778retaining a very good compatibility with C. The \nameref{sec:call}
 779section explains how to pass an environment parameter.
 780
 781Since global symbols are defined mutually recursive, there is no need
 782for function declarations: a function can be referenced before its
 783definition. Similarly, functions from other modules can be used without
 784previous declaration. All the type information necessary to compile a
 785call is in the instruction itself.
 786
 787The syntax and semantics for the body of functions are described in the
 788\nameref{sec:control} section.
 789
 790\section{Control}
 791\label{sec:control}
 792
 793The IL represents programs as textual transcriptions of control flow
 794graphs. The control flow is serialized as a sequence of blocks of
 795straight-line code which are connected using jump instructions.
 796
 797\subsection{Blocks}
 798\label{sec:blocks}
 799
 800\ignore{
 801\begin{code}
 802-- Basic block abstraction with optional exit points. The 'insertJumps'
 803-- function takes care of inserting fallthrough for omitted jumps.
 804data Block'
 805  = Block'
 806  { label' :: Q.BlockIdent,
 807    phi' :: [Q.Phi],
 808    stmt' :: [Q.Statement],
 809    term' :: Maybe Q.JumpInstr
 810  }
 811  deriving (Show, Eq)
 812
 813blkMap :: [Q.Block] -> Map Q.BlockIdent Q.Block
 814blkMap = Map.fromList . map (\b -> (Q.label b, b))
 815
 816insertJumps :: [Block'] -> Maybe [Q.Block]
 817insertJumps xs = foldM go [] $ zipWithNext xs
 818  where
 819    zipWithNext :: [a] -> [(a, Maybe a)]
 820    zipWithNext [] = []
 821    zipWithNext lst@(_ : t) = zip lst $ map Just t ++ [Nothing]
 822
 823    fromBlock' :: Block' -> Q.JumpInstr -> Q.Block
 824    fromBlock' (Block' l p s _) = Q.Block l p s
 825
 826    go :: [Q.Block] -> (Block', Maybe Block') -> Maybe [Q.Block]
 827    go acc (x@Block' {term' = Just ji}, _) =
 828      Just (acc ++ [fromBlock' x ji])
 829    go acc (x@Block' {term' = Nothing}, Just nxt) =
 830      Just (acc ++ [fromBlock' x (Q.Jump $ label' nxt)])
 831    go _ (Block' {term' = Nothing}, Nothing) =
 832      Nothing
 833\end{code}
 834}
 835
 836\begin{code}
 837block :: Parser Block'
 838block = do
 839  l <- wsNL1 label
 840  p <- many (wsNL1 $ try phiInstr)
 841  s <- many (wsNL1 statement)
 842  Block' l p s <$> (optionMaybe $ wsNL1 jumpInstr)
 843\end{code}
 844
 845All blocks have a name that is specified by a label at their beginning.
 846Then follows a sequence of instructions that have "fall-through" flow.
 847Finally one jump terminates the block. The jump can either transfer
 848control to another block of the same function or return; jumps are
 849described further below.
 850
 851The first block in a function must not be the target of any jump in the
 852program. If a jump to the function start is needed, the frontend must
 853insert an empty prelude block at the beginning of the function.
 854
 855When one block jumps to the next block in the IL file, it is not
 856necessary to write the jump instruction, it will be automatically added
 857by the parser. For example the start block in the example below jumps
 858directly to the loop block.
 859
 860\subsection{Jumps}
 861\label{sec:jumps}
 862
 863\begin{code}
 864jumpInstr :: Parser Q.JumpInstr
 865jumpInstr = (string "hlt" >> pure Q.Halt)
 866        -- TODO: Return requires a space if there is an optionMaybe
 867        <|> Q.Return <$> ((ws $ string "ret") >> optionMaybe val)
 868        <|> try (Q.Jump <$> ((ws1 $ string "jmp") >> label))
 869        <|> do
 870          _ <- ws1 $ string "jnz"
 871          v <- ws val <* ws (char ',')
 872          l1 <- ws label <* ws (char ',')
 873          l2 <- ws label
 874          return $ Q.Jnz v l1 l2
 875\end{code}
 876
 877A jump instruction ends every block and transfers the control to another
 878program location. The target of a jump must never be the first block in
 879a function. The three kinds of jumps available are described in the
 880following list.
 881
 882\begin{enumerate}
 883  \item \textbf{Unconditional jump.} Jumps to another block of the same function.
 884  \item \textbf{Conditional jump.} When its word argument is non-zero, it jumps to its first label argument; otherwise it jumps to the other label. The argument must be of word type; because of subtyping a long argument can be passed, but only its least significant 32 bits will be compared to 0.
 885  \item \textbf{Function return.} Terminates the execution of the current function, optionally returning a value to the caller. The value returned must be of the type given in the function prototype. If the function prototype does not specify a return type, no return value can be used.
 886  \item \textbf{Program termination.} Terminates the execution of the program with a target-dependent error. This instruction can be used when it is expected that the execution never reaches the end of the block it closes; for example, after having called a function such as \texttt{exit()}.
 887\end{enumerate}
 888
 889\section{Instructions}
 890\label{sec:instructions}
 891
 892\begin{code}
 893instr :: Parser Q.Instr
 894instr =
 895  choice
 896    [ try $ binaryInstr Q.Add "add",
 897      try $ binaryInstr Q.Sub "sub",
 898      try $ binaryInstr Q.Mul "mul",
 899      try $ binaryInstr Q.Div "div",
 900      try $ binaryInstr Q.URem "urem",
 901      try $ binaryInstr Q.Rem "rem",
 902      try $ binaryInstr Q.UDiv "udiv",
 903      try $ binaryInstr Q.Or "or",
 904      try $ binaryInstr Q.Xor "xor",
 905      try $ binaryInstr Q.And "and",
 906      try $ binaryInstr Q.Sar "sar",
 907      try $ binaryInstr Q.Shr "shr",
 908      try $ binaryInstr Q.Shl "shl",
 909      try $ unaryInstr Q.Neg "neg",
 910      try $ unaryInstr Q.Cast "cast",
 911      try $ unaryInstr Q.Copy "copy",
 912      try $ unaryInstr Q.VAArg "vaarg",
 913      try $ loadInstr,
 914      try $ allocInstr,
 915      try $ compareInstr,
 916      try $ extInstr,
 917      try $ truncInstr,
 918      try $ fromFloatInstr,
 919      try $ toFloatInstr
 920    ]
 921\end{code}
 922
 923Instructions are the smallest piece of code in the IL, they form the body of
 924\nameref{sec:blocks}. This specification distinguishes instructions and
 925volatile instructions, the latter do not return a value. For the former, the IL
 926uses a three-address code, which means that one instruction computes an
 927operation between two operands and assigns the result to a third one.
 928
 929\begin{code}
 930assign :: Parser Q.Statement
 931assign = do
 932  n <- ws local
 933  t <- ws (char '=') >> ws1 baseType
 934  Q.Assign n t <$> instr
 935
 936volatileInstr :: Parser Q.Statement
 937volatileInstr =
 938  Q.Volatile <$>
 939    (storeInstr <|> blitInstr <|> vastartInstr <|> dbglocInstr)
 940
 941-- TODO: Not documented in the QBE BNF.
 942statement :: Parser Q.Statement
 943statement = (try callInstr) <|> assign <|> volatileInstr
 944\end{code}
 945
 946An instruction has both a name and a return type, this return type is a base
 947type that defines the size of the instruction's result. The type of the
 948arguments can be unambiguously inferred using the instruction name and the
 949return type. For example, for all arithmetic instructions, the type of the
 950arguments is the same as the return type. The two additions below are valid if
 951\texttt{\%y} is a word or a long (because of \nameref{sec:subtyping}).
 952
 953\begin{verbatim}
 954%x =w add 0, %y
 955%z =w add %x, %x
 956\end{verbatim}
 957
 958Some instructions, like comparisons and memory loads have operand types
 959that differ from their return types. For instance, two floating points
 960can be compared to give a word result (0 if the comparison succeeds, 1
 961if it fails).
 962
 963\begin{verbatim}
 964%c =w cgts %a, %b
 965\end{verbatim}
 966
 967In the example above, both operands have to have single type. This is
 968made explicit by the instruction suffix.
 969
 970\subsection{Arithmetic and Bits}
 971
 972\begin{quote}
 973\begin{itemize}
 974\item \texttt{add}, \texttt{sub}, \texttt{div}, \texttt{mul}
 975\item \texttt{neg}
 976\item \texttt{udiv}, \texttt{rem}, \texttt{urem}
 977\item \texttt{or}, \texttt{xor}, \texttt{and}
 978\item \texttt{sar}, \texttt{shr}, \texttt{shl}
 979\end{itemize}
 980\end{quote}
 981
 982The base arithmetic instructions in the first bullet are available for
 983all types, integers and floating points.
 984
 985When \texttt{div} is used with word or long return type, the arguments are
 986treated as signed. The unsigned integral division is available as \texttt{udiv}
 987instruction. When the result of a division is not an integer, it is truncated
 988towards zero.
 989
 990The signed and unsigned remainder operations are available as \texttt{rem} and
 991\texttt{urem}. The sign of the remainder is the same as the one of the
 992dividend. Its magnitude is smaller than the divisor one. These two instructions
 993and \texttt{udiv} are only available with integer arguments and result.
 994
 995Bitwise OR, AND, and XOR operations are available for both integer
 996types. Logical operations of typical programming languages can be
 997implemented using \nameref{sec:comparisions} and \nameref{sec:jumps}.
 998
 999Shift instructions \texttt{sar}, \texttt{shr}, and \texttt{shl}, shift right or
1000left their first operand by the amount from the second operand. The shifting
1001amount is taken modulo the size of the result type. Shifting right can either
1002preserve the sign of the value (using \texttt{sar}), or fill the newly freed
1003bits with zeroes (using \texttt{shr}). Shifting left always fills the freed
1004bits with zeroes.
1005
1006Remark that an arithmetic shift right (\texttt{sar}) is only equivalent to a
1007division by a power of two for non-negative numbers. This is because the shift
1008right "truncates" towards minus infinity, while the division truncates towards
1009zero.
1010
1011\subsection{Memory}
1012\label{sec:memory}
1013
1014The following sections discuss instructions for interacting with values stored in memory.
1015
1016\subsubsection{Store instructions}
1017
1018\begin{code}
1019storeInstr :: Parser Q.VolatileInstr
1020storeInstr = do
1021  t <- string "store" >> ws1 extType
1022  v <- ws val
1023  _ <- ws $ char ','
1024  ws val <&> Q.Store t v
1025\end{code}
1026
1027Store instructions exist to store a value of any base type and any extended
1028type. Since halfwords and bytes are not first class in the IL, \texttt{storeh}
1029and \texttt{storeb} take a word as argument. Only the first 16 or 8 bits of
1030this word will be stored in memory at the address specified in the second
1031argument.
1032
1033\subsubsection{Load instructions}
1034
1035\begin{code}
1036loadInstr :: Parser Q.Instr
1037loadInstr = do
1038  _ <- string "load"
1039  t <- ws1 $ choice
1040    [ try $ bind "sw" (Q.LBase Q.Word),
1041      try $ bind "uw" (Q.LBase Q.Word),
1042      try $ Q.LSubWord <$> subWordType,
1043      Q.LBase <$> baseType
1044    ]
1045  ws val <&> Q.Load t
1046\end{code}
1047
1048For types smaller than long, two variants of the load instruction are
1049available: one will sign extend the loaded value, while the other will zero
1050extend it. Note that all loads smaller than long can load to either a long or a
1051word.
1052
1053The two instructions \texttt{loadsw} and \texttt{loaduw} have the same effect
1054when they are used to define a word temporary. A \texttt{loadw} instruction is
1055provided as syntactic sugar for \texttt{loadsw} to make explicit that the
1056extension mechanism used is irrelevant.
1057
1058\subsubsection{Blits}
1059
1060\begin{code}
1061blitInstr :: Parser Q.VolatileInstr
1062blitInstr = do
1063  v1 <- (ws1 $ string "blit") >> ws val <* (ws $ char ',')
1064  v2 <- ws val <* (ws $ char ',')
1065  nb <- decNumber
1066  return $ Q.Blit v1 v2 nb
1067\end{code}
1068
1069The blit instruction copies in-memory data from its first address argument to
1070its second address argument. The third argument is the number of bytes to copy.
1071The source and destination spans are required to be either non-overlapping, or
1072fully overlapping (source address identical to the destination address). The
1073byte count argument must be a nonnegative numeric constant; it cannot be a
1074temporary.
1075
1076One blit instruction may generate a number of instructions proportional to its
1077byte count argument, consequently, it is recommended to keep this argument
1078relatively small. If large copies are necessary, it is preferable that
1079frontends generate calls to a supporting \texttt{memcpy} function.
1080
1081\subsubsection{Stack Allocation}
1082
1083\begin{code}
1084allocInstr :: Parser Q.Instr
1085allocInstr = do
1086  siz <- (ws $ string "alloc") >> (ws1 allocSize)
1087  val <&> Q.Alloc siz
1088\end{code}
1089
1090These instructions allocate a chunk of memory on the stack. The number ending
1091the instruction name is the alignment required for the allocated slot. QBE will
1092make sure that the returned address is a multiple of that alignment value.
1093
1094Stack allocation instructions are used, for example, when compiling the C local
1095variables, because their address can be taken. When compiling Fortran,
1096temporaries can be used directly instead, because it is illegal to take the
1097address of a variable.
1098
1099\subsection{Comparisons}
1100\label{sec:comparisions}
1101
1102\begin{code}
1103compareInstr :: Parser Q.Instr
1104compareInstr = do
1105  _ <- char 'c'
1106  (try intCompare) <|> floatCompare
1107
1108compareArgs :: Parser (Q.Value, Q.Value)
1109compareArgs = do
1110  lhs <- ws val <* ws (char ',')
1111  rhs <- ws val
1112  pure (lhs, rhs)
1113
1114intCompare :: Parser Q.Instr
1115intCompare = do
1116  op <- compareIntOp
1117  ty <- ws1 intArg
1118
1119  (lhs, rhs) <- compareArgs
1120  pure $ Q.CompareInt ty op lhs rhs
1121
1122floatCompare :: Parser Q.Instr
1123floatCompare = do
1124  op <- compareFloatOp
1125  ty <- ws1 floatArg
1126
1127  (lhs, rhs) <- compareArgs
1128  pure $ Q.CompareFloat ty op lhs rhs
1129\end{code}
1130
1131Comparison instructions return an integer value (either a word or a long), and
1132compare values of arbitrary types. The returned value is 1 if the two operands
1133satisfy the comparison relation, or 0 otherwise. The names of comparisons
1134respect a standard naming scheme in three parts:
1135
1136\begin{enumerate}
1137  \item All comparisons start with the letter \texttt{c}.
1138  \item Then comes a comparison type.
1139  \item Finally, the instruction name is terminated with a basic type suffix precising the type of the operands to be compared.
1140\end{enumerate}
1141
1142The following instruction are available for integer comparisons:
1143
1144\begin{code}
1145compareIntOp :: Parser Q.IntCmpOp
1146compareIntOp = choice
1147  [ bind "eq" Q.IEq
1148  , bind "ne" Q.INe
1149  , try $ bind "sle" Q.ISle
1150  , try $ bind "slt" Q.ISlt
1151  , try $ bind "sge" Q.ISge
1152  , try $ bind "sgt" Q.ISgt
1153  , try $ bind "ule" Q.IUle
1154  , try $ bind "ult" Q.IUlt
1155  , try $ bind "uge" Q.IUge
1156  , try $ bind "ugt" Q.IUgt ]
1157\end{code}
1158
1159For floating point comparisons use one of these instructions:
1160
1161\begin{code}
1162compareFloatOp :: Parser Q.FloatCmpOp
1163compareFloatOp = choice
1164  [ bind "eq" Q.FEq
1165  , bind "ne" Q.FNe
1166  , try $ bind "le" Q.FLe
1167  , bind "lt" Q.FLt
1168  , try $ bind "ge" Q.FGe
1169  , bind "gt" Q.FGt
1170  , bind "o" Q.FOrd
1171  , bind "uo" Q.FUnord ]
1172\end{code}
1173
1174For example, \texttt{cod} compares two double-precision floating point numbers
1175and returns 1 if the two floating points are not NaNs, or 0 otherwise. The
1176\texttt{csltw} instruction compares two words representing signed numbers and
1177returns 1 when the first argument is smaller than the second one.
1178
1179\subsection{Conversions}
1180
1181Conversion operations change the representation of a value, possibly modifying
1182it if the target type cannot hold the value of the source type. Conversions can
1183extend the precision of a temporary (e.g., from signed 8-bit to 32-bit), or
1184convert a floating point into an integer and vice versa.
1185
1186\begin{code}
1187extInstr :: Parser Q.Instr
1188extInstr = do
1189  _ <- string "ext"
1190  ty <- ws1 extArg
1191  ws val <&> Q.Ext ty
1192 where
1193  extArg :: Parser Q.ExtArg
1194  extArg = try (Q.ExtSubWord <$> subWordType)
1195    <|> try (bind "sw" Q.ExtSignedWord)
1196    <|> bind "s" Q.ExtSingle
1197    <|> bind "uw" Q.ExtUnsignedWord
1198\end{code}
1199
1200Extending the precision of a temporary is done using the \texttt{ext} family of
1201instructions. Because QBE types do not specify the signedness (like in LLVM),
1202extension instructions exist to sign-extend and zero-extend a value. For
1203example, \texttt{extsb} takes a word argument and sign-extends the 8
1204least-significant bits to a full word or long, depending on the return type.
1205
1206\begin{code}
1207truncInstr :: Parser Q.Instr
1208truncInstr = do
1209  _ <- ws1 $ string "truncd"
1210  ws val <&> Q.TruncDouble
1211\end{code}
1212
1213The instructions \texttt{exts} (extend single) and \texttt{truncd} (truncate
1214double) are provided to change the precision of a floating point value. When
1215the double argument of truncd cannot be represented as a single-precision
1216floating point, it is truncated towards zero.
1217
1218\begin{code}
1219floatArg :: Parser Q.FloatArg
1220floatArg = bind "d" Q.FDouble <|> bind "s" Q.FSingle
1221
1222fromFloatInstr :: Parser Q.Instr
1223fromFloatInstr = do
1224  arg <- floatArg <* string "to"
1225  isSigned <- signageChar
1226  _ <- ws1 $ char 'i'
1227  ws val <&> Q.FloatToInt arg isSigned
1228
1229intArg :: Parser Q.IntArg
1230intArg = bind "w" Q.IWord <|> bind "l" Q.ILong
1231
1232toFloatInstr :: Parser Q.Instr
1233toFloatInstr = do
1234  isSigned <- signageChar
1235  arg <- intArg
1236  _ <- ws1 $ string "tof"
1237  ws val <&> Q.IntToFloat arg isSigned
1238\end{code}
1239
1240Converting between signed integers and floating points is done using
1241\texttt{stosi} (single to signed integer), \texttt{stoui} (single to unsigned
1242integer), \texttt{dtosi} (double to signed integer), \texttt{dtoui} (double to
1243unsigned integer), \texttt{swtof} (signed word to float), \texttt{uwtof}
1244(unsigned word to float), \texttt{sltof} (signed long to float) and
1245\texttt{ultof} (unsigned long to float).
1246
1247\subsection{Cast and Copy}
1248
1249The \texttt{cast} and \texttt{copy} instructions return the bits of their
1250argument verbatim. However a cast will change an integer into a floating point
1251of the same width and vice versa.
1252
1253Casts can be used to make bitwise operations on the representation of floating
1254point numbers. For example the following program will compute the opposite of
1255the single-precision floating point number \texttt{\%f} into \texttt{\%rs}.
1256
1257\begin{verbatim}
1258%b0 =w cast %f
1259%b1 =w xor 2147483648, %b0  # flip the msb
1260%rs =s cast %b1
1261\end{verbatim}
1262
1263\subsection{Call}
1264\label{sec:call}
1265
1266\begin{code}
1267-- TODO: Code duplication with 'param'.
1268callArg :: Parser Q.FuncArg
1269callArg = (Q.ArgEnv <$> (ws1 (string "env") >> val))
1270    <|> (string "..." >> pure Q.ArgVar)
1271    <|> do
1272          ty <- ws1 abity
1273          Q.ArgReg ty <$> val
1274
1275callArgs :: Parser [Q.FuncArg]
1276callArgs = parenLst callArg
1277
1278callInstr :: Parser Q.Statement
1279callInstr = do
1280  retValue <- optionMaybe $ do
1281    i <- ws local <* ws (char '=')
1282    a <- ws1 abity
1283    return (i, a)
1284  toCall <- ws1 (string "call") >> ws val
1285  fnArgs <- callArgs
1286  return $ Q.Call retValue toCall fnArgs
1287\end{code}
1288
1289The call instruction is special in several ways. It is not a three-address
1290instruction and requires the type of all its arguments to be given. Also, the
1291return type can be either a base type or an aggregate type. These specifics are
1292required to compile calls with C compatibility (i.e., to respect the ABI).
1293
1294When an aggregate type is used as argument type or return type, the value
1295respectively passed or returned needs to be a pointer to a memory location
1296holding the value. This is because aggregate types are not first-class
1297citizens of the IL.
1298
1299Sub-word types are used for arguments and return values of width less than a
1300word. Details on these types are presented in the \nameref{sec:functions} section.
1301Arguments with sub-word types need not be sign or zero extended according to
1302their type. Calls with a sub-word return type define a temporary of base type
1303\texttt{w} with its most significant bits unspecified.
1304
1305Unless the called function does not return a value, a return temporary must be
1306specified, even if it is never used afterwards.
1307
1308An environment parameter can be passed as first argument using the \texttt{env}
1309keyword. The passed value must be a 64-bit integer. If the called function does
1310not expect an environment parameter, it will be safely discarded. See the
1311\nameref{sec:functions} section for more information about environment
1312parameters.
1313
1314When the called function is variadic, there must be a \texttt{...} marker
1315separating the named and variadic arguments.
1316
1317\subsection{Variadic}
1318\label{sec:variadic}
1319
1320\begin{code}
1321vastartInstr :: Parser Q.VolatileInstr
1322vastartInstr = do
1323  _ <- ws1 (string "vastart")
1324  Q.VAStart <$> ws val
1325\end{code}
1326
1327The \texttt{vastart} and \texttt{vaarg} instructions provide a portable way to
1328access the extra parameters of a variadic function.
1329
1330\begin{enumerate}
1331  \item \texttt{vastart} -- \texttt{(m)}
1332  \item \texttt{vaarg} -- \texttt{T(mmmm)}
1333\end{enumerate}
1334
1335The \texttt{vastart} instruction initializes a variable argument list used to
1336access the extra parameters of the enclosing variadic function. It is safe to
1337call it multiple times.
1338
1339The \texttt{vaarg} instruction fetches the next argument from a variable
1340argument list. It is currently limited to fetching arguments that have a base
1341type. This instruction is essentially effectful: calling it twice in a row will
1342return two consecutive arguments from the argument list.
1343
1344Both instructions take a pointer to a variable argument list as the sole argument.
1345The size and alignment of the variable argument lists depends on the target used.
1346
1347\subsection{Phi}
1348
1349\begin{code}
1350phiBranch :: Parser (Q.BlockIdent, Q.Value)
1351phiBranch = do
1352  n <- ws1 label
1353  v <- val
1354  pure (n, v)
1355
1356phiInstr :: Parser Q.Phi
1357phiInstr = do
1358  -- TODO: code duplication with 'assign'
1359  n <- ws local
1360  t <- ws (char '=') >> ws1 baseType
1361
1362  _ <- ws1 (string "phi")
1363  -- TODO: combinator for sepBy
1364  p <- Map.fromList <$> sepBy1 (ws phiBranch) (ws $ char ',')
1365  return $ Q.Phi n t p
1366\end{code}
1367
1368First and foremost, phi instructions are NOT necessary when writing a frontend
1369to QBE. One solution to avoid having to deal with SSA form is to use stack
1370allocated variables for all source program variables and perform assignments
1371and lookups using \nameref{sec:memory} operations. This is what LLVM users
1372typically do.
1373
1374Another solution is to simply emit code that is not in SSA form! Contrary to
1375LLVM, QBE is able to fixup programs not in SSA form without requiring the
1376boilerplate of loading and storing in memory. For example, the following
1377program will be correctly compiled by QBE.
1378
1379\begin{verbatim}
1380@start
1381    %x =w copy 100
1382    %s =w copy 0
1383@loop
1384    %s =w add %s, %x
1385    %x =w sub %x, 1
1386    jnz %x, @loop, @end
1387@end
1388    ret %s
1389\end{verbatim}
1390
1391Now, if you want to know what phi instructions are and how to use them in QBE,
1392you can read the following.
1393
1394Phi instructions are specific to SSA form. In SSA form values can only be
1395assigned once, without phi instructions, this requirement is too strong to
1396represent many programs. For example consider the following C program.
1397
1398\begin{verbatim}
1399int f(int x) {
1400    int y;
1401    if (x)
1402        y = 1;
1403    else
1404        y = 2;
1405    return y;
1406}
1407\end{verbatim}
1408
1409The variable \texttt{y} is assigned twice, the solution to translate it in SSA
1410form is to insert a phi instruction.
1411
1412\begin{verbatim}
1413@ifstmt
1414    jnz %x, @ift, @iff
1415@ift
1416    jmp @retstmt
1417@iff
1418    jmp @retstmt
1419@retstmt
1420    %y =w phi @ift 1, @iff 2
1421    ret %y
1422\end{verbatim}
1423
1424Phi instructions return one of their arguments depending on where the control
1425came from. In the example, \texttt{\%y} is set to 1 if the
1426\texttt{\textbackslash{}ift} branch is taken, or it is set to 2 otherwise.
1427
1428An important remark about phi instructions is that QBE assumes that if a
1429variable is defined by a phi it respects all the SSA invariants. So it is
1430critical to not use phi instructions unless you know exactly what you are
1431doing.
1432
1433\subsection{Debug Information}
1434
1435QBE supports the inclusion of debug information. Specifically, it allows
1436defining from which source file type, data, and function definitions originated.
1437For this purpose, it provides the \texttt{dbgfile} definition, which receives a
1438file name (string literal) as its sole argument. Every type, data and function
1439definition thereafter are assumed to originate in this file.
1440
1441\begin{code}
1442-- TODO: not documnted in the QBE BNF.
1443fileDef :: Parser String
1444fileDef = do
1445  _ <- ws1 $ string "dbgfile"
1446  wsNL1 strLit
1447\end{code}
1448
1449Further, instructions within a function can be associated with a specific line
1450and column number of a previously defined \texttt{dbgfile}. The
1451\texttt{dbgfile} is referenced by index using the first argument to
1452\texttt{dbgloc}. The second argument represents the line number, the third
1453(optional) argument the column number.
1454
1455\begin{code}
1456-- TODO: not documnted in the QBE BNF.
1457dbglocInstr :: Parser Q.VolatileInstr
1458dbglocInstr = do
1459  _ <- ws1 $ string "dbgloc"
1460  file <- ws decNumber <* ws (char ',')
1461  line <- ws decNumber
1462  col  <- optionMaybe (ws (char ',') >> ws decNumber)
1463  return $ Q.DBGLoc file line col
1464\end{code}
1465
1466\end{document}