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