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 "thread" Q.LThread)
 457    <|> do
 458      _ <- ws1 $ string "section"
 459      (try secWithFlags) <|> sec
 460  where
 461    sec :: Parser Q.Linkage
 462    sec = wsNL strLit <&> (`Q.LSection` Nothing)
 463
 464    secWithFlags :: Parser Q.Linkage
 465    secWithFlags = do
 466      n <- ws1 strLit
 467      wsNL strLit <&> Q.LSection n . Just
 468\end{code}
 469
 470Function and data definitions (see below) can specify linkage
 471information to be passed to the assembler and eventually to the linker.
 472
 473The \texttt{export} linkage flag marks the defined item as visible outside the
 474current file\textquotesingle s scope. If absent, the symbol can only be
 475referred to locally. Functions compiled by QBE and called from C need to
 476be exported.
 477
 478The \texttt{thread} linkage flag can only qualify data definitions. It mandates
 479that the object defined is stored in thread-local storage. Each time a
 480runtime thread starts, the supporting platform runtime is in charge of
 481making a new copy of the object for the fresh thread. Objects in
 482thread-local storage must be accessed using the \texttt{thread \$IDENT} syntax,
 483as specified in the \nameref{sec:constants-and-vals} section.
 484
 485A \texttt{section} flag can be specified to tell the linker to put the defined
 486item in a certain section. The use of the section flag is platform
 487dependent and we refer the user to the documentation of their assembler
 488and linker for relevant information.
 489
 490\begin{verbatim}
 491section ".init_array" data $.init.f = { l $f }
 492\end{verbatim}
 493
 494The section flag can be used to add function pointers to a global
 495initialization list, as depicted above. Note that some platforms provide
 496a BSS section that can be used to minimize the footprint of uniformly
 497zeroed data. When this section is available, QBE will automatically make
 498use of it and no section flag is required.
 499
 500The section and export linkage flags should each appear at most once in
 501a definition. If multiple occurrences are present, QBE is free to use
 502any.
 503
 504\subsection{Definitions}
 505\label{sec:definitions}
 506
 507Definitions are the essential components of an IL file. They can define
 508three types of objects: aggregate types, data, and functions. Aggregate
 509types are never exported and do not compile to any code. Data and
 510function definitions have file scope and are mutually recursive (even
 511across IL files). Their visibility can be controlled using linkage
 512flags.
 513
 514\subsubsection{Aggregate Types}
 515\label{sec:aggregate-types}
 516
 517\begin{code}
 518typeDef :: Parser Q.TypeDef
 519typeDef = do
 520  _ <- wsNL1 (string "type")
 521  i <- wsNL1 userDef
 522  _ <- wsNL1 (char '=')
 523  a <- optionMaybe alignAny
 524  bracesNL (opaqueType <|> unionType <|> regularType) <&> Q.TypeDef i a
 525\end{code}
 526
 527Aggregate type definitions start with the \texttt{type} keyword. They have file
 528scope, but types must be defined before being referenced. The inner
 529structure of a type is expressed by a comma-separated list of fields.
 530
 531\begin{code}
 532subType :: Parser Q.SubType
 533subType =
 534  (Q.SExtType <$> extType)
 535    <|> (Q.SUserDef <$> userDef)
 536
 537field :: Parser Q.Field
 538field = do
 539  -- TODO: newline is required if there is a number argument
 540  f <- wsNL subType
 541  s <- ws $ optionMaybe decNumber
 542  pure (f, s)
 543
 544fields :: Bool -> Parser [Q.Field]
 545fields allowEmpty =
 546  (if allowEmpty then sepByTrail else sepByTrail1) field (wsNL $ char ',')
 547\end{code}
 548
 549A field consists of a subtype, either an extended type or a user-defined type,
 550and an optional number expressing the value of this field. In case many items
 551of the same type are sequenced (like in a C array), the shorter array syntax
 552can be used.
 553
 554\begin{code}
 555regularType :: Parser Q.AggType
 556regularType = Q.ARegular <$> fields True
 557\end{code}
 558
 559Three different kinds of aggregate types are presentl ysupported: regular
 560types, union types and opaque types. The fields of regular types will be
 561packed. By default, the alignment of an aggregate type is the maximum alignment
 562of its members. The alignment can be explicitly specified by the programmer.
 563
 564\begin{code}
 565unionType :: Parser Q.AggType
 566unionType = Q.AUnion <$> many1 (wsNL unionType')
 567  where
 568    unionType' :: Parser [Q.Field]
 569    unionType' = bracesNL $ fields False
 570\end{code}
 571
 572Union 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.
 573
 574\begin{code}
 575opaqueType :: Parser Q.AggType
 576opaqueType = Q.AOpaque <$> wsNL decNumber
 577\end{code}
 578
 579Opaque 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.
 580
 581\subsubsection{Data}
 582\label{sec:data}
 583
 584\begin{code}
 585dataDef :: Parser Q.DataDef
 586dataDef = do
 587  link <- many linkage
 588  name <- wsNL1 (string "data") >> wsNL global
 589  _ <- wsNL (char '=')
 590  alignment <- optionMaybe alignAny
 591  bracesNL dataObjs <&> Q.DataDef link name alignment
 592 where
 593    -- TODO: sepByTrail is not documented in the QBE BNF.
 594    dataObjs = sepByTrail dataObj (wsNL $ char ',')
 595\end{code}
 596
 597Data definitions express objects that will be emitted in the compiled
 598file. Their visibility and location in the compiled artifact are
 599controlled with linkage flags described in the \nameref{sec:linkage}
 600section.
 601
 602They define a global identifier (starting with the sigil \texttt{\$}), that
 603will contain a pointer to the object specified by the definition.
 604
 605\begin{code}
 606dataObj :: Parser Q.DataObj
 607dataObj =
 608  (Q.OZeroFill <$> (wsNL1 (char 'z') >> wsNL decNumber))
 609    <|> do
 610      t <- wsNL1 extType
 611      i <- many1 (wsNL dataItem)
 612      return $ Q.OItem t i
 613\end{code}
 614
 615Objects are described by a sequence of fields that start with a type
 616letter. This letter can either be an extended type, or the \texttt{z} letter.
 617If the letter used is an extended type, the data item following
 618specifies the bits to be stored in the field.
 619
 620\begin{code}
 621dataItem :: Parser Q.DataItem
 622dataItem =
 623  (Q.DString <$> strLit)
 624    <|> try
 625      ( do
 626          i <- ws global
 627          off <- (ws $ char '+') >> ws decNumber
 628          return $ Q.DSymOff i off
 629      )
 630    <|> (Q.DConst <$> constant)
 631\end{code}
 632
 633Within each object, several items can be defined. When several data items
 634follow a letter, they initialize multiple fields of the same size.
 635
 636\begin{code}
 637allocSize :: Parser Q.AllocSize
 638allocSize =
 639  choice
 640    [ bind "4" Q.AllocWord,
 641      bind "8" Q.AllocLong,
 642      bind "16" Q.AllocLongLong
 643    ]
 644\end{code}
 645
 646The members of a struct will be packed. This means that padding has to
 647be emitted by the frontend when necessary. Alignment of the whole data
 648objects can be manually specified, and when no alignment is provided,
 649the maximum alignment from the platform is used.
 650
 651When the \texttt{z} letter is used the number following indicates the size of
 652the field; the contents of the field are zero initialized. It can be
 653used to add padding between fields or zero-initialize big arrays.
 654
 655\subsubsection{Functions}
 656\label{sec:functions}
 657
 658\begin{code}
 659funcDef :: Parser Q.FuncDef
 660funcDef = do
 661  link <- many linkage
 662  _ <- ws1 (string "function")
 663  retTy <- optionMaybe (ws1 abity)
 664  name <- ws global
 665  args <- wsNL params
 666  body <- between (wsNL1 $ char '{') (wsNL $ char '}') $ many1 block
 667
 668  case (insertJumps body) of
 669    Nothing -> fail $ "invalid fallthrough in " ++ show name
 670    Just [] -> error "unreachable" -- TODO: Use NonEmpty
 671    Just blocks@(startBlk:_) ->
 672      return $
 673        Q.FuncDef {
 674          Q.fLinkage = link,
 675          Q.fName = name,
 676          Q.fStart = Q.label startBlk,
 677          Q.fAbity = retTy,
 678          Q.fParams = args,
 679          Q.fBlock = blkMap blocks
 680        }
 681\end{code}
 682
 683Function definitions contain the actual code to emit in the compiled
 684file. They define a global symbol that contains a pointer to the
 685function code. This pointer can be used in \texttt{call} instructions or stored
 686in memory.
 687
 688\begin{code}
 689subWordType :: Parser Q.SubWordType
 690subWordType = choice
 691  [ try $ bind "sb" Q.SignedByte
 692  , try $ bind "ub" Q.UnsignedByte
 693  , bind "sh" Q.SignedHalf
 694  , bind "uh" Q.UnsignedHalf ]
 695
 696abity :: Parser Q.Abity
 697abity = try (Q.ASubWordType <$> subWordType)
 698    <|> (Q.ABase <$> baseType)
 699    <|> (Q.AUserDef <$> userDef)
 700\end{code}
 701
 702The type given right before the function name is the return type of the
 703function. All return values of this function must have this return type.
 704If the return type is missing, the function must not return any value.
 705
 706\begin{code}
 707param :: Parser Q.FuncParam
 708param = (Q.Env <$> (ws1 (string "env") >> local))
 709    <|> (string "..." >> pure Q.Variadic)
 710    <|> do
 711          ty <- ws1 abity
 712          Q.Regular ty <$> local
 713
 714params :: Parser [Q.FuncParam]
 715params = parenLst param
 716\end{code}
 717
 718The parameter list is a comma separated list of temporary names prefixed
 719by types. The types are used to correctly implement C compatibility.
 720When an argument has an aggregate type, a pointer to the aggregate is
 721passed by thea caller. In the example below, we have to use a load
 722instruction to get the value of the first (and only) member of the
 723struct.
 724
 725\begin{verbatim}
 726type :one = { w }
 727
 728function w $getone(:one %p) {
 729@start
 730        %val =w loadw %p
 731        ret %val
 732}
 733\end{verbatim}
 734
 735If a function accepts or returns values that are smaller than a word,
 736such as \texttt{signed char} or \texttt{unsigned short} in C, one of the sub-word type
 737must be used. The sub-word types \texttt{sb}, \texttt{ub}, \texttt{sh}, and \texttt{uh} stand,
 738respectively, for signed and unsigned 8-bit values, and signed and
 739unsigned 16-bit values. Parameters associated with a sub-word type of
 740bit width N only have their N least significant bits set and have base
 741type \texttt{w}. For example, the function
 742
 743\begin{verbatim}
 744function w $addbyte(w %a, sb %b) {
 745@start
 746        %bw =w extsb %b
 747        %val =w add %a, %bw
 748        ret %val
 749}
 750\end{verbatim}
 751
 752needs to sign-extend its second argument before the addition. Dually,
 753return values with sub-word types do not need to be sign or zero
 754extended.
 755
 756If the parameter list ends with \texttt{...}, the function is a variadic
 757function: it can accept a variable number of arguments. To access the
 758extra arguments provided by the caller, use the \texttt{vastart} and \texttt{vaarg}
 759instructions described in the \nameref{sec:variadic} section.
 760
 761Optionally, the parameter list can start with an environment parameter
 762\texttt{env \%e}. This special parameter is a 64-bit integer temporary (i.e.,
 763of type \texttt{l}). If the function does not use its environment parameter,
 764callers can safely omit it. This parameter is invisible to a C caller:
 765for example, the function
 766
 767\begin{verbatim}
 768export function w $add(env %e, w %a, w %b) {
 769@start
 770        %c =w add %a, %b
 771        ret %c
 772}
 773\end{verbatim}
 774
 775must be given the C prototype \texttt{int add(int, int)}. The intended use of
 776this feature is to pass the environment pointer of closures while
 777retaining a very good compatibility with C. The \nameref{sec:call}
 778section explains how to pass an environment parameter.
 779
 780Since global symbols are defined mutually recursive, there is no need
 781for function declarations: a function can be referenced before its
 782definition. Similarly, functions from other modules can be used without
 783previous declaration. All the type information necessary to compile a
 784call is in the instruction itself.
 785
 786The syntax and semantics for the body of functions are described in the
 787\nameref{sec:control} section.
 788
 789\section{Control}
 790\label{sec:control}
 791
 792The IL represents programs as textual transcriptions of control flow
 793graphs. The control flow is serialized as a sequence of blocks of
 794straight-line code which are connected using jump instructions.
 795
 796\subsection{Blocks}
 797\label{sec:blocks}
 798
 799\ignore{
 800\begin{code}
 801-- Basic block abstraction with optional exit points. The 'insertJumps'
 802-- function takes care of inserting fallthrough for omitted jumps.
 803data Block'
 804  = Block'
 805  { label' :: Q.BlockIdent,
 806    phi' :: [Q.Phi],
 807    stmt' :: [Q.Statement],
 808    term' :: Maybe Q.JumpInstr
 809  }
 810  deriving (Show, Eq)
 811
 812blkMap :: [Q.Block] -> Map Q.BlockIdent Q.Block
 813blkMap = Map.fromList . map (\b -> (Q.label b, b))
 814
 815insertJumps :: [Block'] -> Maybe [Q.Block]
 816insertJumps xs = foldM go [] $ zipWithNext xs
 817  where
 818    zipWithNext :: [a] -> [(a, Maybe a)]
 819    zipWithNext [] = []
 820    zipWithNext lst@(_ : t) = zip lst $ map Just t ++ [Nothing]
 821
 822    fromBlock' :: Block' -> Q.JumpInstr -> Q.Block
 823    fromBlock' (Block' l p s _) = Q.Block l p s
 824
 825    go :: [Q.Block] -> (Block', Maybe Block') -> Maybe [Q.Block]
 826    go acc (x@Block' {term' = Just ji}, _) =
 827      Just (acc ++ [fromBlock' x ji])
 828    go acc (x@Block' {term' = Nothing}, Just nxt) =
 829      Just (acc ++ [fromBlock' x (Q.Jump $ label' nxt)])
 830    go _ (Block' {term' = Nothing}, Nothing) =
 831      Nothing
 832\end{code}
 833}
 834
 835\begin{code}
 836block :: Parser Block'
 837block = do
 838  l <- wsNL1 label
 839  p <- many (wsNL1 $ try phiInstr)
 840  s <- many (wsNL1 statement)
 841  Block' l p s <$> (optionMaybe $ wsNL1 jumpInstr)
 842\end{code}
 843
 844All blocks have a name that is specified by a label at their beginning.
 845Then follows a sequence of instructions that have "fall-through" flow.
 846Finally one jump terminates the block. The jump can either transfer
 847control to another block of the same function or return; jumps are
 848described further below.
 849
 850The first block in a function must not be the target of any jump in the
 851program. If a jump to the function start is needed, the frontend must
 852insert an empty prelude block at the beginning of the function.
 853
 854When one block jumps to the next block in the IL file, it is not
 855necessary to write the jump instruction, it will be automatically added
 856by the parser. For example the start block in the example below jumps
 857directly to the loop block.
 858
 859\subsection{Jumps}
 860\label{sec:jumps}
 861
 862\begin{code}
 863jumpInstr :: Parser Q.JumpInstr
 864jumpInstr = (string "hlt" >> pure Q.Halt)
 865        -- TODO: Return requires a space if there is an optionMaybe
 866        <|> Q.Return <$> ((ws $ string "ret") >> optionMaybe val)
 867        <|> try (Q.Jump <$> ((ws1 $ string "jmp") >> label))
 868        <|> do
 869          _ <- ws1 $ string "jnz"
 870          v <- ws val <* ws (char ',')
 871          l1 <- ws label <* ws (char ',')
 872          l2 <- ws label
 873          return $ Q.Jnz v l1 l2
 874\end{code}
 875
 876A jump instruction ends every block and transfers the control to another
 877program location. The target of a jump must never be the first block in
 878a function. The three kinds of jumps available are described in the
 879following list.
 880
 881\begin{enumerate}
 882  \item \textbf{Unconditional jump.} Jumps to another block of the same function.
 883  \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.
 884  \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.
 885  \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()}.
 886\end{enumerate}
 887
 888\section{Instructions}
 889\label{sec:instructions}
 890
 891\begin{code}
 892instr :: Parser Q.Instr
 893instr =
 894  choice
 895    [ try $ binaryInstr Q.Add "add",
 896      try $ binaryInstr Q.Sub "sub",
 897      try $ binaryInstr Q.Mul "mul",
 898      try $ binaryInstr Q.Div "div",
 899      try $ binaryInstr Q.URem "urem",
 900      try $ binaryInstr Q.Rem "rem",
 901      try $ binaryInstr Q.UDiv "udiv",
 902      try $ binaryInstr Q.Or "or",
 903      try $ binaryInstr Q.Xor "xor",
 904      try $ binaryInstr Q.And "and",
 905      try $ binaryInstr Q.Sar "sar",
 906      try $ binaryInstr Q.Shr "shr",
 907      try $ binaryInstr Q.Shl "shl",
 908      try $ unaryInstr Q.Neg "neg",
 909      try $ unaryInstr Q.Cast "cast",
 910      try $ unaryInstr Q.Copy "copy",
 911      try $ unaryInstr Q.VAArg "vaarg",
 912      try $ loadInstr,
 913      try $ allocInstr,
 914      try $ compareInstr,
 915      try $ extInstr,
 916      try $ truncInstr,
 917      try $ fromFloatInstr,
 918      try $ toFloatInstr
 919    ]
 920\end{code}
 921
 922Instructions are the smallest piece of code in the IL, they form the body of
 923\nameref{sec:blocks}. This specification distinguishes instructions and
 924volatile instructions, the latter do not return a value. For the former, the IL
 925uses a three-address code, which means that one instruction computes an
 926operation between two operands and assigns the result to a third one.
 927
 928\begin{code}
 929assign :: Parser Q.Statement
 930assign = do
 931  n <- ws local
 932  t <- ws (char '=') >> ws1 baseType
 933  Q.Assign n t <$> instr
 934
 935volatileInstr :: Parser Q.Statement
 936volatileInstr =
 937  Q.Volatile <$>
 938    (storeInstr <|> blitInstr <|> vastartInstr <|> dbglocInstr)
 939
 940-- TODO: Not documented in the QBE BNF.
 941statement :: Parser Q.Statement
 942statement = (try callInstr) <|> assign <|> volatileInstr
 943\end{code}
 944
 945An instruction has both a name and a return type, this return type is a base
 946type that defines the size of the instruction's result. The type of the
 947arguments can be unambiguously inferred using the instruction name and the
 948return type. For example, for all arithmetic instructions, the type of the
 949arguments is the same as the return type. The two additions below are valid if
 950\texttt{\%y} is a word or a long (because of \nameref{sec:subtyping}).
 951
 952\begin{verbatim}
 953%x =w add 0, %y
 954%z =w add %x, %x
 955\end{verbatim}
 956
 957Some instructions, like comparisons and memory loads have operand types
 958that differ from their return types. For instance, two floating points
 959can be compared to give a word result (0 if the comparison succeeds, 1
 960if it fails).
 961
 962\begin{verbatim}
 963%c =w cgts %a, %b
 964\end{verbatim}
 965
 966In the example above, both operands have to have single type. This is
 967made explicit by the instruction suffix.
 968
 969\subsection{Arithmetic and Bits}
 970
 971\begin{quote}
 972\begin{itemize}
 973\item \texttt{add}, \texttt{sub}, \texttt{div}, \texttt{mul}
 974\item \texttt{neg}
 975\item \texttt{udiv}, \texttt{rem}, \texttt{urem}
 976\item \texttt{or}, \texttt{xor}, \texttt{and}
 977\item \texttt{sar}, \texttt{shr}, \texttt{shl}
 978\end{itemize}
 979\end{quote}
 980
 981The base arithmetic instructions in the first bullet are available for
 982all types, integers and floating points.
 983
 984When \texttt{div} is used with word or long return type, the arguments are
 985treated as signed. The unsigned integral division is available as \texttt{udiv}
 986instruction. When the result of a division is not an integer, it is truncated
 987towards zero.
 988
 989The signed and unsigned remainder operations are available as \texttt{rem} and
 990\texttt{urem}. The sign of the remainder is the same as the one of the
 991dividend. Its magnitude is smaller than the divisor one. These two instructions
 992and \texttt{udiv} are only available with integer arguments and result.
 993
 994Bitwise OR, AND, and XOR operations are available for both integer
 995types. Logical operations of typical programming languages can be
 996implemented using \nameref{sec:comparisions} and \nameref{sec:jumps}.
 997
 998Shift instructions \texttt{sar}, \texttt{shr}, and \texttt{shl}, shift right or
 999left their first operand by the amount from the second operand. The shifting
1000amount is taken modulo the size of the result type. Shifting right can either
1001preserve the sign of the value (using \texttt{sar}), or fill the newly freed
1002bits with zeroes (using \texttt{shr}). Shifting left always fills the freed
1003bits with zeroes.
1004
1005Remark that an arithmetic shift right (\texttt{sar}) is only equivalent to a
1006division by a power of two for non-negative numbers. This is because the shift
1007right "truncates" towards minus infinity, while the division truncates towards
1008zero.
1009
1010\subsection{Memory}
1011\label{sec:memory}
1012
1013The following sections discuss instructions for interacting with values stored in memory.
1014
1015\subsubsection{Store instructions}
1016
1017\begin{code}
1018storeInstr :: Parser Q.VolatileInstr
1019storeInstr = do
1020  t <- string "store" >> ws1 extType
1021  v <- ws val
1022  _ <- ws $ char ','
1023  ws val <&> Q.Store t v
1024\end{code}
1025
1026Store instructions exist to store a value of any base type and any extended
1027type. Since halfwords and bytes are not first class in the IL, \texttt{storeh}
1028and \texttt{storeb} take a word as argument. Only the first 16 or 8 bits of
1029this word will be stored in memory at the address specified in the second
1030argument.
1031
1032\subsubsection{Load instructions}
1033
1034\begin{code}
1035loadInstr :: Parser Q.Instr
1036loadInstr = do
1037  _ <- string "load"
1038  t <- ws1 $ choice
1039    [ try $ bind "sw" (Q.LBase Q.Word),
1040      try $ bind "uw" (Q.LBase Q.Word),
1041      try $ Q.LSubWord <$> subWordType,
1042      Q.LBase <$> baseType
1043    ]
1044  ws val <&> Q.Load t
1045\end{code}
1046
1047For types smaller than long, two variants of the load instruction are
1048available: one will sign extend the loaded value, while the other will zero
1049extend it. Note that all loads smaller than long can load to either a long or a
1050word.
1051
1052The two instructions \texttt{loadsw} and \texttt{loaduw} have the same effect
1053when they are used to define a word temporary. A \texttt{loadw} instruction is
1054provided as syntactic sugar for \texttt{loadsw} to make explicit that the
1055extension mechanism used is irrelevant.
1056
1057\subsubsection{Blits}
1058
1059\begin{code}
1060blitInstr :: Parser Q.VolatileInstr
1061blitInstr = do
1062  v1 <- (ws1 $ string "blit") >> ws val <* (ws $ char ',')
1063  v2 <- ws val <* (ws $ char ',')
1064  nb <- decNumber
1065  return $ Q.Blit v1 v2 nb
1066\end{code}
1067
1068The blit instruction copies in-memory data from its first address argument to
1069its second address argument. The third argument is the number of bytes to copy.
1070The source and destination spans are required to be either non-overlapping, or
1071fully overlapping (source address identical to the destination address). The
1072byte count argument must be a nonnegative numeric constant; it cannot be a
1073temporary.
1074
1075One blit instruction may generate a number of instructions proportional to its
1076byte count argument, consequently, it is recommended to keep this argument
1077relatively small. If large copies are necessary, it is preferable that
1078frontends generate calls to a supporting \texttt{memcpy} function.
1079
1080\subsubsection{Stack Allocation}
1081
1082\begin{code}
1083allocInstr :: Parser Q.Instr
1084allocInstr = do
1085  siz <- (ws $ string "alloc") >> (ws1 allocSize)
1086  val <&> Q.Alloc siz
1087\end{code}
1088
1089These instructions allocate a chunk of memory on the stack. The number ending
1090the instruction name is the alignment required for the allocated slot. QBE will
1091make sure that the returned address is a multiple of that alignment value.
1092
1093Stack allocation instructions are used, for example, when compiling the C local
1094variables, because their address can be taken. When compiling Fortran,
1095temporaries can be used directly instead, because it is illegal to take the
1096address of a variable.
1097
1098\subsection{Comparisons}
1099\label{sec:comparisions}
1100
1101\begin{code}
1102compareInstr :: Parser Q.Instr
1103compareInstr = do
1104  _ <- char 'c'
1105  (try intCompare) <|> floatCompare
1106
1107compareArgs :: Parser (Q.Value, Q.Value)
1108compareArgs = do
1109  lhs <- ws val <* ws (char ',')
1110  rhs <- ws val
1111  pure (lhs, rhs)
1112
1113intCompare :: Parser Q.Instr
1114intCompare = do
1115  op <- compareIntOp
1116  ty <- ws1 intArg
1117
1118  (lhs, rhs) <- compareArgs
1119  pure $ Q.CompareInt ty op lhs rhs
1120
1121floatCompare :: Parser Q.Instr
1122floatCompare = do
1123  op <- compareFloatOp
1124  ty <- ws1 floatArg
1125
1126  (lhs, rhs) <- compareArgs
1127  pure $ Q.CompareFloat ty op lhs rhs
1128\end{code}
1129
1130Comparison instructions return an integer value (either a word or a long), and
1131compare values of arbitrary types. The returned value is 1 if the two operands
1132satisfy the comparison relation, or 0 otherwise. The names of comparisons
1133respect a standard naming scheme in three parts:
1134
1135\begin{enumerate}
1136  \item All comparisons start with the letter \texttt{c}.
1137  \item Then comes a comparison type.
1138  \item Finally, the instruction name is terminated with a basic type suffix precising the type of the operands to be compared.
1139\end{enumerate}
1140
1141The following instruction are available for integer comparisons:
1142
1143\begin{code}
1144compareIntOp :: Parser Q.IntCmpOp
1145compareIntOp = choice
1146  [ bind "eq" Q.IEq
1147  , bind "ne" Q.INe
1148  , try $ bind "sle" Q.ISle
1149  , try $ bind "slt" Q.ISlt
1150  , try $ bind "sge" Q.ISge
1151  , try $ bind "sgt" Q.ISgt
1152  , try $ bind "ule" Q.IUle
1153  , try $ bind "ult" Q.IUlt
1154  , try $ bind "uge" Q.IUge
1155  , try $ bind "ugt" Q.IUgt ]
1156\end{code}
1157
1158For floating point comparisons use one of these instructions:
1159
1160\begin{code}
1161compareFloatOp :: Parser Q.FloatCmpOp
1162compareFloatOp = choice
1163  [ bind "eq" Q.FEq
1164  , bind "ne" Q.FNe
1165  , try $ bind "le" Q.FLe
1166  , bind "lt" Q.FLt
1167  , try $ bind "ge" Q.FGe
1168  , bind "gt" Q.FGt
1169  , bind "o" Q.FOrd
1170  , bind "uo" Q.FUnord ]
1171\end{code}
1172
1173For example, \texttt{cod} compares two double-precision floating point numbers
1174and returns 1 if the two floating points are not NaNs, or 0 otherwise. The
1175\texttt{csltw} instruction compares two words representing signed numbers and
1176returns 1 when the first argument is smaller than the second one.
1177
1178\subsection{Conversions}
1179
1180Conversion operations change the representation of a value, possibly modifying
1181it if the target type cannot hold the value of the source type. Conversions can
1182extend the precision of a temporary (e.g., from signed 8-bit to 32-bit), or
1183convert a floating point into an integer and vice versa.
1184
1185\begin{code}
1186extInstr :: Parser Q.Instr
1187extInstr = do
1188  _ <- string "ext"
1189  ty <- ws1 extArg
1190  ws val <&> Q.Ext ty
1191 where
1192  extArg :: Parser Q.ExtArg
1193  extArg = try (Q.ExtSubWord <$> subWordType)
1194    <|> try (bind "sw" Q.ExtSignedWord)
1195    <|> bind "s" Q.ExtSingle
1196    <|> bind "uw" Q.ExtUnsignedWord
1197\end{code}
1198
1199Extending the precision of a temporary is done using the \texttt{ext} family of
1200instructions. Because QBE types do not specify the signedness (like in LLVM),
1201extension instructions exist to sign-extend and zero-extend a value. For
1202example, \texttt{extsb} takes a word argument and sign-extends the 8
1203least-significant bits to a full word or long, depending on the return type.
1204
1205\begin{code}
1206truncInstr :: Parser Q.Instr
1207truncInstr = do
1208  _ <- ws1 $ string "truncd"
1209  ws val <&> Q.TruncDouble
1210\end{code}
1211
1212The instructions \texttt{exts} (extend single) and \texttt{truncd} (truncate
1213double) are provided to change the precision of a floating point value. When
1214the double argument of truncd cannot be represented as a single-precision
1215floating point, it is truncated towards zero.
1216
1217\begin{code}
1218floatArg :: Parser Q.FloatArg
1219floatArg = bind "d" Q.FDouble <|> bind "s" Q.FSingle
1220
1221fromFloatInstr :: Parser Q.Instr
1222fromFloatInstr = do
1223  arg <- floatArg <* string "to"
1224  isSigned <- signageChar
1225  _ <- ws1 $ char 'i'
1226  ws val <&> Q.FloatToInt arg isSigned
1227
1228intArg :: Parser Q.IntArg
1229intArg = bind "w" Q.IWord <|> bind "l" Q.ILong
1230
1231toFloatInstr :: Parser Q.Instr
1232toFloatInstr = do
1233  isSigned <- signageChar
1234  arg <- intArg
1235  _ <- ws1 $ string "tof"
1236  ws val <&> Q.IntToFloat arg isSigned
1237\end{code}
1238
1239Converting between signed integers and floating points is done using
1240\texttt{stosi} (single to signed integer), \texttt{stoui} (single to unsigned
1241integer), \texttt{dtosi} (double to signed integer), \texttt{dtoui} (double to
1242unsigned integer), \texttt{swtof} (signed word to float), \texttt{uwtof}
1243(unsigned word to float), \texttt{sltof} (signed long to float) and
1244\texttt{ultof} (unsigned long to float).
1245
1246\subsection{Cast and Copy}
1247
1248The \texttt{cast} and \texttt{copy} instructions return the bits of their
1249argument verbatim. However a cast will change an integer into a floating point
1250of the same width and vice versa.
1251
1252Casts can be used to make bitwise operations on the representation of floating
1253point numbers. For example the following program will compute the opposite of
1254the single-precision floating point number \texttt{\%f} into \texttt{\%rs}.
1255
1256\begin{verbatim}
1257%b0 =w cast %f
1258%b1 =w xor 2147483648, %b0  # flip the msb
1259%rs =s cast %b1
1260\end{verbatim}
1261
1262\subsection{Call}
1263\label{sec:call}
1264
1265\begin{code}
1266-- TODO: Code duplication with 'param'.
1267callArg :: Parser Q.FuncArg
1268callArg = (Q.ArgEnv <$> (ws1 (string "env") >> val))
1269    <|> (string "..." >> pure Q.ArgVar)
1270    <|> do
1271          ty <- ws1 abity
1272          Q.ArgReg ty <$> val
1273
1274callArgs :: Parser [Q.FuncArg]
1275callArgs = parenLst callArg
1276
1277callInstr :: Parser Q.Statement
1278callInstr = do
1279  retValue <- optionMaybe $ do
1280    i <- ws local <* ws (char '=')
1281    a <- ws1 abity
1282    return (i, a)
1283  toCall <- ws1 (string "call") >> ws val
1284  fnArgs <- callArgs
1285  return $ Q.Call retValue toCall fnArgs
1286\end{code}
1287
1288The call instruction is special in several ways. It is not a three-address
1289instruction and requires the type of all its arguments to be given. Also, the
1290return type can be either a base type or an aggregate type. These specifics are
1291required to compile calls with C compatibility (i.e., to respect the ABI).
1292
1293When an aggregate type is used as argument type or return type, the value
1294respectively passed or returned needs to be a pointer to a memory location
1295holding the value. This is because aggregate types are not first-class
1296citizens of the IL.
1297
1298Sub-word types are used for arguments and return values of width less than a
1299word. Details on these types are presented in the \nameref{sec:functions} section.
1300Arguments with sub-word types need not be sign or zero extended according to
1301their type. Calls with a sub-word return type define a temporary of base type
1302\texttt{w} with its most significant bits unspecified.
1303
1304Unless the called function does not return a value, a return temporary must be
1305specified, even if it is never used afterwards.
1306
1307An environment parameter can be passed as first argument using the \texttt{env}
1308keyword. The passed value must be a 64-bit integer. If the called function does
1309not expect an environment parameter, it will be safely discarded. See the
1310\nameref{sec:functions} section for more information about environment
1311parameters.
1312
1313When the called function is variadic, there must be a \texttt{...} marker
1314separating the named and variadic arguments.
1315
1316\subsection{Variadic}
1317\label{sec:variadic}
1318
1319\begin{code}
1320vastartInstr :: Parser Q.VolatileInstr
1321vastartInstr = do
1322  _ <- ws1 (string "vastart")
1323  Q.VAStart <$> ws val
1324\end{code}
1325
1326The \texttt{vastart} and \texttt{vaarg} instructions provide a portable way to
1327access the extra parameters of a variadic function.
1328
1329\begin{enumerate}
1330  \item \texttt{vastart} -- \texttt{(m)}
1331  \item \texttt{vaarg} -- \texttt{T(mmmm)}
1332\end{enumerate}
1333
1334The \texttt{vastart} instruction initializes a variable argument list used to
1335access the extra parameters of the enclosing variadic function. It is safe to
1336call it multiple times.
1337
1338The \texttt{vaarg} instruction fetches the next argument from a variable
1339argument list. It is currently limited to fetching arguments that have a base
1340type. This instruction is essentially effectful: calling it twice in a row will
1341return two consecutive arguments from the argument list.
1342
1343Both instructions take a pointer to a variable argument list as the sole argument.
1344The size and alignment of the variable argument lists depends on the target used.
1345
1346\subsection{Phi}
1347
1348\begin{code}
1349phiBranch :: Parser (Q.BlockIdent, Q.Value)
1350phiBranch = do
1351  n <- ws1 label
1352  v <- val
1353  pure (n, v)
1354
1355phiInstr :: Parser Q.Phi
1356phiInstr = do
1357  -- TODO: code duplication with 'assign'
1358  n <- ws local
1359  t <- ws (char '=') >> ws1 baseType
1360
1361  _ <- ws1 (string "phi")
1362  -- TODO: combinator for sepBy
1363  p <- Map.fromList <$> sepBy1 (ws phiBranch) (ws $ char ',')
1364  return $ Q.Phi n t p
1365\end{code}
1366
1367First and foremost, phi instructions are NOT necessary when writing a frontend
1368to QBE. One solution to avoid having to deal with SSA form is to use stack
1369allocated variables for all source program variables and perform assignments
1370and lookups using \nameref{sec:memory} operations. This is what LLVM users
1371typically do.
1372
1373Another solution is to simply emit code that is not in SSA form! Contrary to
1374LLVM, QBE is able to fixup programs not in SSA form without requiring the
1375boilerplate of loading and storing in memory. For example, the following
1376program will be correctly compiled by QBE.
1377
1378\begin{verbatim}
1379@start
1380    %x =w copy 100
1381    %s =w copy 0
1382@loop
1383    %s =w add %s, %x
1384    %x =w sub %x, 1
1385    jnz %x, @loop, @end
1386@end
1387    ret %s
1388\end{verbatim}
1389
1390Now, if you want to know what phi instructions are and how to use them in QBE,
1391you can read the following.
1392
1393Phi instructions are specific to SSA form. In SSA form values can only be
1394assigned once, without phi instructions, this requirement is too strong to
1395represent many programs. For example consider the following C program.
1396
1397\begin{verbatim}
1398int f(int x) {
1399    int y;
1400    if (x)
1401        y = 1;
1402    else
1403        y = 2;
1404    return y;
1405}
1406\end{verbatim}
1407
1408The variable \texttt{y} is assigned twice, the solution to translate it in SSA
1409form is to insert a phi instruction.
1410
1411\begin{verbatim}
1412@ifstmt
1413    jnz %x, @ift, @iff
1414@ift
1415    jmp @retstmt
1416@iff
1417    jmp @retstmt
1418@retstmt
1419    %y =w phi @ift 1, @iff 2
1420    ret %y
1421\end{verbatim}
1422
1423Phi instructions return one of their arguments depending on where the control
1424came from. In the example, \texttt{\%y} is set to 1 if the
1425\texttt{\textbackslash{}ift} branch is taken, or it is set to 2 otherwise.
1426
1427An important remark about phi instructions is that QBE assumes that if a
1428variable is defined by a phi it respects all the SSA invariants. So it is
1429critical to not use phi instructions unless you know exactly what you are
1430doing.
1431
1432\subsection{Debug Information}
1433
1434QBE supports the inclusion of debug information. Specifically, it allows
1435defining from which source file type, data, and function definitions originated.
1436For this purpose, it provides the \texttt{dbgfile} definition, which receives a
1437file name (string literal) as its sole argument. Every type, data and function
1438definition thereafter are assumed to originate in this file.
1439
1440\begin{code}
1441-- TODO: not documnted in the QBE BNF.
1442fileDef :: Parser String
1443fileDef = do
1444  _ <- ws1 $ string "dbgfile"
1445  wsNL1 strLit
1446\end{code}
1447
1448Further, instructions within a function can be associated with a specific line
1449and column number of a previously defined \texttt{dbgfile}. The
1450\texttt{dbgfile} is referenced by index using the first argument to
1451\texttt{dbgloc}. The second argument represents the line number, the third
1452(optional) argument the column number.
1453
1454\begin{code}
1455-- TODO: not documnted in the QBE BNF.
1456dbglocInstr :: Parser Q.VolatileInstr
1457dbglocInstr = do
1458  _ <- ws1 $ string "dbgloc"
1459  file <- ws decNumber <* ws (char ',')
1460  line <- ws decNumber
1461  col  <- optionMaybe (ws (char ',') >> ws decNumber)
1462  return $ Q.DBGLoc file line col
1463\end{code}
1464
1465\end{document}