% SPDX-FileCopyrightText: 2015-2024 Quentin Carbonneaux <quentin@c9x.me>
% SPDX-FileCopyrightText: 2025-2026 Sören Tempel <soeren+git@soeren-tempel.net>
%
% SPDX-License-Identifier: MIT AND GPL-3.0-only

\documentclass{article}
%include polycode.fmt

%subst blankline = "\\[5mm]"

% See https://github.com/kosmikus/lhs2tex/issues/58
%format <$> = "\mathbin{\langle\$\rangle}"
%format <&> = "\mathbin{\langle\&\rangle}"
%format <|> = "\mathbin{\langle\:\vline\:\rangle}"
%format <?> = "\mathbin{\langle?\rangle}"
%format <*> = "\mathbin{\langle*\rangle}"
%format <*  = "\mathbin{\langle*}"
%format *>  = "\mathbin{*\rangle}"

\long\def\ignore#1{}

\usepackage{hyperref}
\hypersetup{
	colorlinks = true,
}

\begin{document}

\title{QBE Intermediate Language\vspace{-2em}}
\date{}
\maketitle
\frenchspacing

\ignore{
\begin{code}
module Language.QBE.Parser
  ( skipInitComments,
    dataDef,
    typeDef,
    funcDef,
    fileDef
  )
where

import Control.Monad (foldM)
import Data.Char (chr)
import Data.Word (Word64)
import Data.Functor ((<&>))
import Data.List (singleton)
import Data.Map (Map)
import Data.Map qualified as Map
import qualified Language.QBE.Types as Q
import Language.QBE.Util (bind, decNumber, octNumber, float)
import Text.ParserCombinators.Parsec
  ( Parser,
    alphaNum,
    anyChar,
    between,
    char,
    choice,
    letter,
    many,
    many1,
    manyTill,
    newline,
    noneOf,
    oneOf,
    optional,
    optionMaybe,
    sepBy,
    sepBy1,
    skipMany,
    skipMany1,
    string,
    try,
    (<?>),
    (<|>),
  )
\end{code}
}

This an executable description of the
\href{https://c9x.me/compile/doc/il-v1.2.html}{QBE intermediate language},
specified through \href{https://hackage.haskell.org/package/parsec}{Parsec}
parser combinators and generated from a literate Haskell file. The description
is derived from the original QBE IL documentation, licensed under MIT.
Presently, this implementation targets version 1.2 of the QBE intermediate
language and aims to be equivalent with the original specification.

\section{Basic Concepts}

The intermediate language (IL) is a higher-level language than the
machine's assembly language. It smoothes most of the
irregularities of the underlying hardware and allows an infinite number
of temporaries to be used. This higher abstraction level lets frontend
programmers focus on language design issues.

\subsection{Input Files}

The intermediate language is provided to QBE as text. Usually, one file
is generated per each compilation unit from the frontend input language.
An IL file is a sequence of \nameref{sec:definitions} for
data, functions, and types. Once processed by QBE, the resulting file
can be assembled and linked using a standard toolchain (e.g., GNU
binutils).

\begin{code}
comment :: Parser ()
comment :: Parser ()
comment = ParsecT String () Identity Char -> Parser ()
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m ()
skipMany ParsecT String () Identity Char
blankNL Parser ()
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity String
forall {u}. ParsecT String u Identity String
comment' ParsecT String () Identity String -> Parser () -> Parser ()
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Char -> Parser ()
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m ()
skipMany ParsecT String () Identity Char
blankNL
  where
    comment' :: ParsecT String u Identity String
comment' = Char -> ParsecT String u Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'#' ParsecT String u Identity Char
-> ParsecT String u Identity String
-> ParsecT String u Identity String
forall a b.
ParsecT String u Identity a
-> ParsecT String u Identity b -> ParsecT String u Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String u Identity Char
-> ParsecT String u Identity Char
-> ParsecT String u Identity String
forall s (m :: * -> *) t u a end.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m end -> ParsecT s u m [a]
manyTill ParsecT String u Identity Char
forall s (m :: * -> *) u. Stream s m Char => ParsecT s u m Char
anyChar ParsecT String u Identity Char
forall s (m :: * -> *) u. Stream s m Char => ParsecT s u m Char
newline
\end{code}

\ignore{
\begin{code}
skipNoCode :: Parser () -> Parser ()
skipNoCode :: Parser () -> Parser ()
skipNoCode Parser ()
blankP = Parser () -> Parser ()
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser () -> Parser ()
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m ()
skipMany1 Parser ()
comment Parser () -> String -> Parser ()
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"comments") Parser () -> Parser () -> Parser ()
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser ()
blankP
\end{code}
}

Here is a complete "Hello World" IL file which defines a function that
prints to the screen. Since the string is not a first class object (only
the pointer is) it is defined outside the function\textquotesingle s
body. Comments start with a \# character and finish with the end of the
line.

\begin{verbatim}
data $str = { b "hello world", b 0 }

export function w $main() {
@start
        # Call the puts function with $str as argument.
        %r =w call $puts(l $str)
        ret 0
}
\end{verbatim}

If you have read the LLVM language reference, you might recognize the
example above. In comparison, QBE makes a much lighter use of types and
the syntax is terser.

\subsection{Parser Combinators}

\ignore{
\begin{code}
bracesNL :: Parser a -> Parser a
bracesNL :: forall a. Parser a -> Parser a
bracesNL = ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity a
-> ParsecT String () Identity a
forall s (m :: * -> *) t u open close a.
Stream s m t =>
ParsecT s u m open
-> ParsecT s u m close -> ParsecT s u m a -> ParsecT s u m a
between (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'{') (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'}')

quoted :: Parser a -> Parser a
quoted :: forall a. Parser a -> Parser a
quoted = let q :: ParsecT String u Identity Char
q = Char -> ParsecT String u Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'"' in ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity a
-> ParsecT String () Identity a
forall s (m :: * -> *) t u open close a.
Stream s m t =>
ParsecT s u m open
-> ParsecT s u m close -> ParsecT s u m a -> ParsecT s u m a
between ParsecT String () Identity Char
forall {u}. ParsecT String u Identity Char
q ParsecT String () Identity Char
forall {u}. ParsecT String u Identity Char
q

sepByTrail1 :: Parser a -> Parser sep -> Parser [a]
sepByTrail1 :: forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail1 Parser a
p Parser sep
sep = do
  a
x <- Parser a
p
  [a]
xs <- Parser a -> Parser [a]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many (Parser a -> Parser a
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser a -> Parser a) -> Parser a -> Parser a
forall a b. (a -> b) -> a -> b
$ Parser sep
sep Parser sep -> Parser a -> Parser a
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser a
p)
  ()
_ <- Parser sep -> Parser ()
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m ()
optional Parser sep
sep
  [a] -> Parser [a]
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs)

sepByTrail :: Parser a -> Parser sep -> Parser [a]
sepByTrail :: forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail Parser a
p Parser sep
sep = Parser a -> Parser sep -> Parser [a]
forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail1 Parser a
p Parser sep
sep Parser [a] -> Parser [a] -> Parser [a]
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> [a] -> Parser [a]
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return []

parenLst :: Parser a -> Parser [a]
parenLst :: forall a. Parser a -> Parser [a]
parenLst Parser a
p = ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity [a]
-> ParsecT String () Identity [a]
forall s (m :: * -> *) t u open close a.
Stream s m t =>
ParsecT s u m open
-> ParsecT s u m close -> ParsecT s u m a -> ParsecT s u m a
between (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'(') (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
')') ParsecT String () Identity [a]
inner
  where
    inner :: ParsecT String () Identity [a]
inner = Parser a
-> ParsecT String () Identity Char
-> ParsecT String () Identity [a]
forall s (m :: * -> *) t u a end.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m end -> ParsecT s u m [a]
sepBy (Parser a -> Parser a
forall a. Parser a -> Parser a
ws Parser a
p) (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')

unaryInstr :: (Q.Value -> Q.Instr) -> String -> Parser Q.Instr
unaryInstr :: (Value -> Instr) -> String -> Parser Instr
unaryInstr Value -> Instr
conc String
keyword = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
keyword)
  Value -> Instr
conc (Value -> Instr)
-> ParsecT String () Identity Value -> Parser Instr
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val

binaryInstr :: (Q.Value -> Q.Value -> Q.Instr) -> String -> Parser Q.Instr
binaryInstr :: (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
conc String
keyword = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
keyword)
  Value
vfst <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> ParsecT String () Identity Char
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Value -> Value -> Instr
conc Value
vfst (Value -> Instr)
-> ParsecT String () Identity Value -> Parser Instr
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val

-- Can only appear in data and type definitions and hence allows newlines.
alignAny :: Parser Word64
alignAny :: Parser Word64
alignAny = (ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"align")) ParsecT String () Identity String -> Parser Word64 -> Parser Word64
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
wsNL Parser Word64
decNumber

-- Returns true if it is signed.
signageChar :: Parser Bool
signageChar :: Parser Bool
signageChar = (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
's' ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'u') ParsecT String () Identity Char -> (Char -> Bool) -> Parser Bool
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> (Char -> Char -> Bool
forall a. Eq a => a -> a -> Bool
== Char
's')
\end{code}
}

The original QBE specification defines the syntax using a BNF grammar. In
contrast, this document defines it using Parsec parser combinators. As such,
this specification is less formal but more accurate as the parsing code is
actually executable. Consequently, this specification also captures constructs
omitted in the original specification (e.g., \nameref{sec:identifiers}, or
\nameref{sec:strlit}). Nonetheless, the formal language recognized by these
combinators aims to be equivalent to the one of the BNF grammar.

\subsection{Identifiers}
\label{sec:identifiers}

% Ident is not documented in the original QBE specification.
% See https://c9x.me/git/qbe.git/tree/parse.c?h=v1.2#n304

\begin{code}
ident :: Parser String
ident :: ParsecT String () Identity String
ident = do
  Char
start <- ParsecT String () Identity Char
forall s (m :: * -> *) u. Stream s m Char => ParsecT s u m Char
letter ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m Char
oneOf String
"._"
  String
rest <- ParsecT String () Identity Char
-> ParsecT String () Identity String
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many (ParsecT String () Identity Char
forall s (m :: * -> *) u. Stream s m Char => ParsecT s u m Char
alphaNum ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m Char
oneOf String
"$._")
  String -> ParsecT String () Identity String
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (String -> ParsecT String () Identity String)
-> String -> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ Char
start Char -> String -> String
forall a. a -> [a] -> [a]
: String
rest
\end{code}

Identifiers for data, types, and functions can start with any ASCII letter or
the special characters \texttt{.} and \texttt{\_}. This initial character can
be followed by a sequence of zero or more alphanumeric characters and the
special characters \texttt{\$}, \texttt{.}, and \texttt{\_}.

\subsection{Sigils}

\begin{code}
userDef :: Parser Q.UserIdent
userDef :: Parser UserIdent
userDef = String -> UserIdent
Q.UserIdent (String -> UserIdent)
-> ParsecT String () Identity String -> Parser UserIdent
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
':' ParsecT String () Identity Char
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity String
ident)

global :: Parser Q.GlobalIdent
global :: Parser GlobalIdent
global = String -> GlobalIdent
Q.GlobalIdent (String -> GlobalIdent)
-> ParsecT String () Identity String -> Parser GlobalIdent
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'$' ParsecT String () Identity Char
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity String
ident)

local :: Parser Q.LocalIdent
local :: Parser LocalIdent
local = String -> LocalIdent
Q.LocalIdent (String -> LocalIdent)
-> ParsecT String () Identity String -> Parser LocalIdent
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'%' ParsecT String () Identity Char
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity String
ident)

label :: Parser Q.BlockIdent
label :: Parser BlockIdent
label = String -> BlockIdent
Q.BlockIdent (String -> BlockIdent)
-> ParsecT String () Identity String -> Parser BlockIdent
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'@' ParsecT String () Identity Char
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity String
ident)
\end{code}

The intermediate language makes heavy use of sigils, all user-defined
names are prefixed with a sigil. This is to avoid keyword conflicts, and
also to quickly spot the scope and nature of identifiers.

\begin{itemize}
  \item \texttt{:} is for user-defined \nameref{sec:aggregate-types}
  \item \texttt{\$} is for globals (represented by a pointer)
  \item \texttt{\%} is for function-scope temporaries
  \item \texttt{@@} is for block labels
\end{itemize}

\subsection{Spacing}

\begin{code}
blank :: Parser Char
blank :: ParsecT String () Identity Char
blank = String -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m Char
oneOf String
"\t " ParsecT String () Identity Char
-> String -> ParsecT String () Identity Char
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"blank"

blankNL :: Parser Char
blankNL :: ParsecT String () Identity Char
blankNL = String -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m Char
oneOf String
"\n\t " ParsecT String () Identity Char
-> String -> ParsecT String () Identity Char
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"blank or newline"
\end{code}

Individual tokens in IL files must be separated by one or more spacing
characters. Both spaces and tabs are recognized as spacing characters.
In data and type definitions, newlines may also be used as spaces to
prevent overly long lines. When exactly one of two consecutive tokens is
a symbol (for example \texttt{,} or \texttt{=} or \texttt{\{}), spacing may be omitted.

\ignore{
\begin{code}
ws :: Parser a -> Parser a
ws :: forall a. Parser a -> Parser a
ws Parser a
p = Parser a
p Parser a -> Parser () -> Parser a
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> Parser ()
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m ()
skipMany ParsecT String () Identity Char
blank

ws1 :: Parser a -> Parser a
ws1 :: forall a. Parser a -> Parser a
ws1 Parser a
p = Parser a
p Parser a -> Parser () -> Parser a
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> Parser ()
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m ()
skipMany1 ParsecT String () Identity Char
blank

wsNL :: Parser a -> Parser a
wsNL :: forall a. Parser a -> Parser a
wsNL Parser a
p = Parser a
p Parser a -> Parser () -> Parser a
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* Parser () -> Parser ()
skipNoCode (ParsecT String () Identity Char -> Parser ()
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m ()
skipMany ParsecT String () Identity Char
blankNL)

wsNL1 :: Parser a -> Parser a
wsNL1 :: forall a. Parser a -> Parser a
wsNL1 Parser a
p = Parser a
p Parser a -> Parser () -> Parser a
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* Parser () -> Parser ()
skipNoCode (ParsecT String () Identity Char -> Parser ()
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m ()
skipMany1 ParsecT String () Identity Char
blankNL)

-- Only intended to be used to skip comments at the start of a file.
skipInitComments :: Parser ()
skipInitComments :: Parser ()
skipInitComments = Parser () -> Parser ()
skipNoCode (ParsecT String () Identity Char -> Parser ()
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m ()
skipMany ParsecT String () Identity Char
blankNL)
\end{code}
}

\subsection{String Literals}
\label{sec:strlit}

% The string literal is not documented in the original QBE specification.
% See https://c9x.me/git/qbe.git/tree/parse.c?h=v1.2#n287

\begin{code}
strLit :: Parser String
strLit :: ParsecT String () Identity String
strLit = [String] -> String
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([String] -> String)
-> ParsecT String () Identity [String]
-> ParsecT String () Identity String
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity [String]
-> ParsecT String () Identity [String]
forall a. Parser a -> Parser a
quoted (ParsecT String () Identity String
-> ParsecT String () Identity [String]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many ParsecT String () Identity String
strChr)
  where
    strChr :: Parser [Char]
    strChr :: ParsecT String () Identity String
strChr = (Char -> String
forall a. a -> [a]
singleton (Char -> String)
-> ParsecT String () Identity Char
-> ParsecT String () Identity String
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> String -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m Char
noneOf String
"\"\\") ParsecT String () Identity String
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity String
escSeq

    -- TODO: not documnted in the QBE BNF.
    octEsc :: Parser Char
    octEsc :: ParsecT String () Identity Char
octEsc = do
      Word64
n <- Parser Word64
octNumber
      Char -> ParsecT String () Identity Char
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Char -> ParsecT String () Identity Char)
-> Char -> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Int -> Char
chr (Word64 -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Word64
n)

    escSeq :: Parser [Char]
    escSeq :: ParsecT String () Identity String
escSeq = ParsecT String () Identity String
-> ParsecT String () Identity String
forall tok st a. GenParser tok st a -> GenParser tok st a
try (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ do
      Char
esc <- Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'\\'
      (Char -> String
forall a. a -> [a]
singleton (Char -> String)
-> ParsecT String () Identity Char
-> ParsecT String () Identity String
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Char
octEsc) ParsecT String () Identity String
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (ParsecT String () Identity Char
forall s (m :: * -> *) u. Stream s m Char => ParsecT s u m Char
anyChar ParsecT String () Identity Char
-> (Char -> String) -> ParsecT String () Identity String
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> (\Char
c -> [Char
esc, Char
c]))
\end{code}

Strings are enclosed by double quotes and are, for example, used to specify a
section name as part of the \nameref{sec:linkage} information. Within a string,
a double quote can be escaped using a \texttt{\textbackslash} character. All
escape sequences, including double quote escaping, are passed through as-is to
the generated assembly file.

\section{Types}

\subsection{Simple Types}

The IL makes minimal use of types. By design, the types used are
restricted to what is necessary for unambiguous compilation to machine
code and C interfacing. Unlike LLVM, QBE is not using types as a means
to safety; they are only here for semantic purposes.

\begin{code}
baseType :: Parser Q.BaseType
baseType :: Parser BaseType
baseType = [Parser BaseType] -> Parser BaseType
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
  [ String -> BaseType -> Parser BaseType
forall a. String -> a -> Parser a
bind String
"w" BaseType
Q.Word
  , String -> BaseType -> Parser BaseType
forall a. String -> a -> Parser a
bind String
"l" BaseType
Q.Long
  , String -> BaseType -> Parser BaseType
forall a. String -> a -> Parser a
bind String
"s" BaseType
Q.Single
  , String -> BaseType -> Parser BaseType
forall a. String -> a -> Parser a
bind String
"d" BaseType
Q.Double ]
\end{code}

The four base types are \texttt{w} (word), \texttt{l} (long), \texttt{s} (single), and \texttt{d}
(double), they stand respectively for 32-bit and 64-bit integers, and
32-bit and 64-bit floating-point numbers. There are no pointer types
available; pointers are typed by an integer type sufficiently wide to
represent all memory addresses (e.g., \texttt{l} on 64-bit architectures).
Temporaries in the IL can only have a base type.

\begin{code}
extType :: Parser Q.ExtType
extType :: Parser ExtType
extType = (BaseType -> ExtType
Q.Base (BaseType -> ExtType) -> Parser BaseType -> Parser ExtType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser BaseType
baseType)
       Parser ExtType -> Parser ExtType -> Parser ExtType
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ExtType -> Parser ExtType
forall a. String -> a -> Parser a
bind String
"b" ExtType
Q.Byte
       Parser ExtType -> Parser ExtType -> Parser ExtType
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ExtType -> Parser ExtType
forall a. String -> a -> Parser a
bind String
"h" ExtType
Q.HalfWord
\end{code}

Extended types contain base types plus \texttt{b} (byte) and \texttt{h} (half word),
respectively for 8-bit and 16-bit integers. They are used in \nameref{sec:aggregate-types}
and \nameref{sec:data} definitions.

For C interfacing, the IL also provides user-defined aggregate types as
well as signed and unsigned variants of the sub-word extended types.
Read more about these types in the \nameref{sec:aggregate-types}
and \nameref{sec:functions} sections.

\subsection{Subtyping}
\label{sec:subtyping}

The IL has a minimal subtyping feature, for integer types only. Any
value of type \texttt{l} can be used in a \texttt{w} context. In that case, only the
32 least significant bits of the word value are used.

Make note that it is the opposite of the usual subtyping on integers (in
C, we can safely use an \texttt{int} where a \texttt{long} is expected). A long value
cannot be used in word context. The rationale is that a word can be
signed or unsigned, so extending it to a long could be done in two ways,
either by zero-extension, or by sign-extension.

\subsection{Constants and Vals}
\label{sec:constants-and-vals}

\begin{code}
dynConst :: Parser Q.DynConst
dynConst :: Parser DynConst
dynConst =
  (Const -> DynConst
Q.Const (Const -> DynConst)
-> ParsecT String () Identity Const -> Parser DynConst
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Const
constant)
    Parser DynConst -> Parser DynConst -> Parser DynConst
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (GlobalIdent -> DynConst
Q.Thread (GlobalIdent -> DynConst) -> Parser GlobalIdent -> Parser DynConst
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (String -> ParsecT String () Identity String
key String
"thread" ParsecT String () Identity String
-> Parser GlobalIdent -> Parser GlobalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser GlobalIdent
global))
    Parser DynConst -> Parser DynConst -> Parser DynConst
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (GlobalIdent -> DynConst
Q.Extern (GlobalIdent -> DynConst) -> Parser GlobalIdent -> Parser DynConst
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser GlobalIdent -> Parser GlobalIdent
forall tok st a. GenParser tok st a -> GenParser tok st a
try (String -> ParsecT String () Identity String
key String
"extern" ParsecT String () Identity String
-> Parser GlobalIdent -> Parser GlobalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser GlobalIdent
global))
    Parser DynConst -> Parser DynConst -> Parser DynConst
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (GlobalIdent -> DynConst
Q.ExternThread (GlobalIdent -> DynConst) -> Parser GlobalIdent -> Parser DynConst
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (String -> ParsecT String () Identity String
key String
"extern" ParsecT String () Identity String
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> String -> ParsecT String () Identity String
key String
"thread" ParsecT String () Identity String
-> Parser GlobalIdent -> Parser GlobalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser GlobalIdent
global))
    Parser DynConst -> String -> Parser DynConst
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"dynconst"
  where
    key :: String -> ParsecT String () Identity String
key String
s = ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
s
\end{code}

Constants come in two kinds: compile-time constants and dynamic
constants. Dynamic constants include compile-time constants and other
symbol variants that are only known at program-load time or execution
time. Consequently, dynamic constants can only occur in function bodies.

When the \texttt{extern} keyword prefixes a symbol name, the symbol is
accessed indirectly through a table edited by the dynamic linker (e.g.,
GOT/PLT). This enables PIE/PIC code generation. When \texttt{extern} is
combined with \texttt{thread}, the symbol is accessed using the
initial-exec TLS model, suitable for thread-local variables defined in
shared objects available at startup time (i.e., not loaded through
dlopen).

The representation of integers is two's complement.
Floating-point numbers are represented using the single-precision and
double-precision formats of the IEEE 754 standard.

\begin{code}
constant :: Parser Q.Const
constant :: ParsecT String () Identity Const
constant =
  (Word64 -> Const
Q.Number (Word64 -> Const)
-> Parser Word64 -> ParsecT String () Identity Const
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser Word64
decNumber)
    ParsecT String () Identity Const
-> ParsecT String () Identity Const
-> ParsecT String () Identity Const
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (Float -> Const
Q.SFP (Float -> Const)
-> ParsecT String () Identity Float
-> ParsecT String () Identity Const
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Float
sfp)
    ParsecT String () Identity Const
-> ParsecT String () Identity Const
-> ParsecT String () Identity Const
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (Double -> Const
Q.DFP (Double -> Const)
-> ParsecT String () Identity Double
-> ParsecT String () Identity Const
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Double
dfp)
    ParsecT String () Identity Const
-> ParsecT String () Identity Const
-> ParsecT String () Identity Const
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (GlobalIdent -> Const
Q.Global (GlobalIdent -> Const)
-> Parser GlobalIdent -> ParsecT String () Identity Const
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser GlobalIdent
global)
    ParsecT String () Identity Const
-> String -> ParsecT String () Identity Const
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"const"
  where
    sfp :: ParsecT String () Identity Float
sfp = String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"s_" ParsecT String () Identity String
-> ParsecT String () Identity Float
-> ParsecT String () Identity Float
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Float
forall f. (Floating f, Read f) => Parser f
float
    dfp :: ParsecT String () Identity Double
dfp = String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"d_" ParsecT String () Identity String
-> ParsecT String () Identity Double
-> ParsecT String () Identity Double
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Double
forall f. (Floating f, Read f) => Parser f
float
\end{code}

Constants specify a sequence of bits and are untyped. They are always
parsed as 64-bit blobs. Depending on the context surrounding a constant,
only some of its bits are used. For example, in the program below, the
two variables defined have the same value since the first operand of the
subtraction is a word (32-bit) context.

\begin{verbatim}
%x =w sub -1, 0 %y =w sub 4294967295, 0
\end{verbatim}

Because specifying floating-point constants by their bits makes the code
less readable, syntactic sugar is provided to express them. Standard
scientific notation is prefixed with \texttt{s\_} and \texttt{d\_} for single and
double precision numbers respectively. Once again, the following example
defines twice the same double-precision constant.

\begin{verbatim}
%x =d add d_0, d_-1
%y =d add d_0, -4616189618054758400
\end{verbatim}

Global symbols can also be used directly as constants; they will be
resolved and turned into actual numeric constants by the linker.

When the \texttt{thread} keyword prefixes a symbol name, the
symbol\textquotesingle s numeric value is resolved at runtime in the
thread-local storage.

\begin{code}
val :: Parser Q.Value
val :: ParsecT String () Identity Value
val =
  (DynConst -> Value
Q.VConst (DynConst -> Value)
-> Parser DynConst -> ParsecT String () Identity Value
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser DynConst
dynConst)
    ParsecT String () Identity Value
-> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (LocalIdent -> Value
Q.VLocal (LocalIdent -> Value)
-> Parser LocalIdent -> ParsecT String () Identity Value
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser LocalIdent
local)
    ParsecT String () Identity Value
-> String -> ParsecT String () Identity Value
forall s u (m :: * -> *) a.
ParsecT s u m a -> String -> ParsecT s u m a
<?> String
"val"
\end{code}

Vals are used as arguments in regular, phi, and jump instructions within
function definitions. They are either constants or function-scope
temporaries.

\subsection{Linkage}
\label{sec:linkage}

\begin{code}
linkage :: Parser Q.Linkage
linkage :: Parser Linkage
linkage =
  Parser Linkage -> Parser Linkage
forall a. Parser a -> Parser a
wsNL (String -> Linkage -> Parser Linkage
forall a. String -> a -> Parser a
bind String
"export" Linkage
Q.LExport)
    Parser Linkage -> Parser Linkage -> Parser Linkage
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser Linkage -> Parser Linkage
forall a. Parser a -> Parser a
wsNL (String -> Linkage -> Parser Linkage
forall a. String -> a -> Parser a
bind String
"thread" Linkage
Q.LThread)
    Parser Linkage -> Parser Linkage -> Parser Linkage
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> do
      String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"section"
      (Parser Linkage -> Parser Linkage
forall tok st a. GenParser tok st a -> GenParser tok st a
try Parser Linkage
secWithFlags) Parser Linkage -> Parser Linkage -> Parser Linkage
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser Linkage
sec
  where
    sec :: Parser Q.Linkage
    sec :: Parser Linkage
sec = ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
wsNL ParsecT String () Identity String
strLit ParsecT String () Identity String
-> (String -> Linkage) -> Parser Linkage
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> (String -> Maybe String -> Linkage
`Q.LSection` Maybe String
forall a. Maybe a
Nothing)

    secWithFlags :: Parser Q.Linkage
    secWithFlags :: Parser Linkage
secWithFlags = do
      String
n <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 ParsecT String () Identity String
strLit
      ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
wsNL ParsecT String () Identity String
strLit ParsecT String () Identity String
-> (String -> Linkage) -> Parser Linkage
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> String -> Maybe String -> Linkage
Q.LSection String
n (Maybe String -> Linkage)
-> (String -> Maybe String) -> String -> Linkage
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> Maybe String
forall a. a -> Maybe a
Just
\end{code}

Function and data definitions (see below) can specify linkage
information to be passed to the assembler and eventually to the linker.

The \texttt{export} linkage flag marks the defined item as visible outside the
current file\textquotesingle s scope. If absent, the symbol can only be
referred to locally. Functions compiled by QBE and called from C need to
be exported.

The \texttt{thread} linkage flag can only qualify data definitions. It mandates
that the object defined is stored in thread-local storage. Each time a
runtime thread starts, the supporting platform runtime is in charge of
making a new copy of the object for the fresh thread. Objects in
thread-local storage must be accessed using the \texttt{thread \$IDENT} syntax,
as specified in the \nameref{sec:constants-and-vals} section.

A \texttt{section} flag can be specified to tell the linker to put the defined
item in a certain section. The use of the section flag is platform
dependent and we refer the user to the documentation of their assembler
and linker for relevant information.

\begin{verbatim}
section ".init_array" data $.init.f = { l $f }
\end{verbatim}

The section flag can be used to add function pointers to a global
initialization list, as depicted above. Note that some platforms provide
a BSS section that can be used to minimize the footprint of uniformly
zeroed data. When this section is available, QBE will automatically make
use of it and no section flag is required.

The section and export linkage flags should each appear at most once in
a definition. If multiple occurrences are present, QBE is free to use
any.

\subsection{Definitions}
\label{sec:definitions}

Definitions are the essential components of an IL file. They can define
three types of objects: aggregate types, data, and functions. Aggregate
types are never exported and do not compile to any code. Data and
function definitions have file scope and are mutually recursive (even
across IL files). Their visibility can be controlled using linkage
flags.

\subsubsection{Aggregate Types}
\label{sec:aggregate-types}

\begin{code}
typeDef :: Parser Q.TypeDef
typeDef :: Parser TypeDef
typeDef = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
wsNL1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"type")
  UserIdent
i <- Parser UserIdent -> Parser UserIdent
forall a. Parser a -> Parser a
wsNL1 Parser UserIdent
userDef
  Char
_ <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL1 (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'=')
  Maybe Word64
a <- Parser Word64 -> ParsecT String () Identity (Maybe Word64)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe Parser Word64
alignAny
  Parser AggType -> Parser AggType
forall a. Parser a -> Parser a
bracesNL (Parser AggType
opaqueType Parser AggType -> Parser AggType -> Parser AggType
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser AggType
unionType Parser AggType -> Parser AggType -> Parser AggType
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser AggType
regularType) Parser AggType -> (AggType -> TypeDef) -> Parser TypeDef
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> UserIdent -> Maybe Word64 -> AggType -> TypeDef
Q.TypeDef UserIdent
i Maybe Word64
a
\end{code}

Aggregate type definitions start with the \texttt{type} keyword. They have file
scope, but types must be defined before being referenced. The inner
structure of a type is expressed by a comma-separated list of fields.

\begin{code}
subType :: Parser Q.SubType
subType :: Parser SubType
subType =
  (ExtType -> SubType
Q.SExtType (ExtType -> SubType) -> Parser ExtType -> Parser SubType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser ExtType
extType)
    Parser SubType -> Parser SubType -> Parser SubType
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (UserIdent -> SubType
Q.SUserDef (UserIdent -> SubType) -> Parser UserIdent -> Parser SubType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser UserIdent
userDef)

field :: Parser Q.Field
field :: Parser Field
field = do
  -- TODO: newline is required if there is a number argument
  SubType
f <- Parser SubType -> Parser SubType
forall a. Parser a -> Parser a
wsNL Parser SubType
subType
  Maybe Word64
s <- ParsecT String () Identity (Maybe Word64)
-> ParsecT String () Identity (Maybe Word64)
forall a. Parser a -> Parser a
ws (ParsecT String () Identity (Maybe Word64)
 -> ParsecT String () Identity (Maybe Word64))
-> ParsecT String () Identity (Maybe Word64)
-> ParsecT String () Identity (Maybe Word64)
forall a b. (a -> b) -> a -> b
$ Parser Word64 -> ParsecT String () Identity (Maybe Word64)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe Parser Word64
decNumber
  Field -> Parser Field
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (SubType
f, Maybe Word64
s)

fields :: Bool -> Parser [Q.Field]
fields :: Bool -> Parser [Field]
fields Bool
allowEmpty =
  (if Bool
allowEmpty then Parser Field -> ParsecT String () Identity Char -> Parser [Field]
forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail else Parser Field -> ParsecT String () Identity Char -> Parser [Field]
forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail1) Parser Field
field (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
\end{code}

A field consists of a subtype, either an extended type or a user-defined type,
and an optional number expressing the value of this field. In case many items
of the same type are sequenced (like in a C array), the shorter array syntax
can be used.

\begin{code}
regularType :: Parser Q.AggType
regularType :: Parser AggType
regularType = [Field] -> AggType
Q.ARegular ([Field] -> AggType) -> Parser [Field] -> Parser AggType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Bool -> Parser [Field]
fields Bool
True
\end{code}

Three different kinds of aggregate types are presentl ysupported: regular
types, union types and opaque types. The fields of regular types will be
packed. By default, the alignment of an aggregate type is the maximum alignment
of its members. The alignment can be explicitly specified by the programmer.

\begin{code}
unionType :: Parser Q.AggType
unionType :: Parser AggType
unionType = [[Field]] -> AggType
Q.AUnion ([[Field]] -> AggType)
-> ParsecT String () Identity [[Field]] -> Parser AggType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser [Field] -> ParsecT String () Identity [[Field]]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many1 (Parser [Field] -> Parser [Field]
forall a. Parser a -> Parser a
wsNL Parser [Field]
unionType')
  where
    unionType' :: Parser [Q.Field]
    unionType' :: Parser [Field]
unionType' = Parser [Field] -> Parser [Field]
forall a. Parser a -> Parser a
bracesNL (Parser [Field] -> Parser [Field])
-> Parser [Field] -> Parser [Field]
forall a b. (a -> b) -> a -> b
$ Bool -> Parser [Field]
fields Bool
False
\end{code}

Union 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.

\begin{code}
opaqueType :: Parser Q.AggType
opaqueType :: Parser AggType
opaqueType = Word64 -> AggType
Q.AOpaque (Word64 -> AggType) -> Parser Word64 -> Parser AggType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
wsNL Parser Word64
decNumber
\end{code}

Opaque 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.

\subsubsection{Data}
\label{sec:data}

\begin{code}
dataDef :: Parser Q.DataDef
dataDef :: Parser DataDef
dataDef = do
  [Linkage]
link <- Parser Linkage -> ParsecT String () Identity [Linkage]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many Parser Linkage
linkage
  GlobalIdent
name <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
wsNL1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"data") ParsecT String () Identity String
-> Parser GlobalIdent -> Parser GlobalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser GlobalIdent -> Parser GlobalIdent
forall a. Parser a -> Parser a
wsNL Parser GlobalIdent
global
  Char
_ <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'=')
  Maybe Word64
alignment <- Parser Word64 -> ParsecT String () Identity (Maybe Word64)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe Parser Word64
alignAny
  Parser [DataObj] -> Parser [DataObj]
forall a. Parser a -> Parser a
bracesNL Parser [DataObj]
dataObjs Parser [DataObj] -> ([DataObj] -> DataDef) -> Parser DataDef
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> [Linkage] -> GlobalIdent -> Maybe Word64 -> [DataObj] -> DataDef
Q.DataDef [Linkage]
link GlobalIdent
name Maybe Word64
alignment
 where
    -- TODO: sepByTrail is not documented in the QBE BNF.
    dataObjs :: Parser [DataObj]
dataObjs = Parser DataObj
-> ParsecT String () Identity Char -> Parser [DataObj]
forall a sep. Parser a -> Parser sep -> Parser [a]
sepByTrail Parser DataObj
dataObj (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
\end{code}

Data definitions express objects that will be emitted in the compiled
file. Their visibility and location in the compiled artifact are
controlled with linkage flags described in the \nameref{sec:linkage}
section.

They define a global identifier (starting with the sigil \texttt{\$}), that
will contain a pointer to the object specified by the definition.

\begin{code}
dataObj :: Parser Q.DataObj
dataObj :: Parser DataObj
dataObj =
  (Word64 -> DataObj
Q.OZeroFill (Word64 -> DataObj) -> Parser Word64 -> Parser DataObj
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL1 (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'z') ParsecT String () Identity Char -> Parser Word64 -> Parser Word64
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
wsNL Parser Word64
decNumber))
    Parser DataObj -> Parser DataObj -> Parser DataObj
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> do
      ExtType
t <- Parser ExtType -> Parser ExtType
forall a. Parser a -> Parser a
wsNL1 Parser ExtType
extType
      [DataItem]
i <- ParsecT String () Identity DataItem
-> ParsecT String () Identity [DataItem]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many1 (ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
forall a. Parser a -> Parser a
wsNL ParsecT String () Identity DataItem
dataItem)
      DataObj -> Parser DataObj
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (DataObj -> Parser DataObj) -> DataObj -> Parser DataObj
forall a b. (a -> b) -> a -> b
$ ExtType -> [DataItem] -> DataObj
Q.OItem ExtType
t [DataItem]
i
\end{code}

Objects are described by a sequence of fields that start with a type
letter. This letter can either be an extended type, or the \texttt{z} letter.
If the letter used is an extended type, the data item following
specifies the bits to be stored in the field.

\begin{code}
dataItem :: Parser Q.DataItem
dataItem :: ParsecT String () Identity DataItem
dataItem =
  (String -> DataItem
Q.DString (String -> DataItem)
-> ParsecT String () Identity String
-> ParsecT String () Identity DataItem
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity String
strLit)
    ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
forall tok st a. GenParser tok st a -> GenParser tok st a
try
      ( do
          GlobalIdent
i <- Parser GlobalIdent -> Parser GlobalIdent
forall a. Parser a -> Parser a
ws Parser GlobalIdent
global
          Word64
off <- (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'+') ParsecT String () Identity Char -> Parser Word64 -> Parser Word64
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
ws Parser Word64
decNumber
          DataItem -> ParsecT String () Identity DataItem
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (DataItem -> ParsecT String () Identity DataItem)
-> DataItem -> ParsecT String () Identity DataItem
forall a b. (a -> b) -> a -> b
$ GlobalIdent -> Word64 -> DataItem
Q.DSymOff GlobalIdent
i Word64
off
      )
    ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
-> ParsecT String () Identity DataItem
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (Const -> DataItem
Q.DConst (Const -> DataItem)
-> ParsecT String () Identity Const
-> ParsecT String () Identity DataItem
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Const
constant)
\end{code}

Within each object, several items can be defined. When several data items
follow a letter, they initialize multiple fields of the same size.

\begin{code}
allocSize :: Parser Q.AllocSize
allocSize :: Parser AllocSize
allocSize =
  [Parser AllocSize] -> Parser AllocSize
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
    [ String -> AllocSize -> Parser AllocSize
forall a. String -> a -> Parser a
bind String
"4" AllocSize
Q.AllocWord,
      String -> AllocSize -> Parser AllocSize
forall a. String -> a -> Parser a
bind String
"8" AllocSize
Q.AllocLong,
      String -> AllocSize -> Parser AllocSize
forall a. String -> a -> Parser a
bind String
"16" AllocSize
Q.AllocLongLong
    ]
\end{code}

The members of a struct will be packed. This means that padding has to
be emitted by the frontend when necessary. Alignment of the whole data
objects can be manually specified, and when no alignment is provided,
the maximum alignment from the platform is used.

When the \texttt{z} letter is used the number following indicates the size of
the field; the contents of the field are zero initialized. It can be
used to add padding between fields or zero-initialize big arrays.

\subsubsection{Functions}
\label{sec:functions}

\begin{code}
funcDef :: Parser Q.FuncDef
funcDef :: Parser FuncDef
funcDef = do
  [Linkage]
link <- Parser Linkage -> ParsecT String () Identity [Linkage]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many Parser Linkage
linkage
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"function")
  Maybe Abity
retTy <- ParsecT String () Identity Abity
-> ParsecT String () Identity (Maybe Abity)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe (ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall a. Parser a -> Parser a
ws1 ParsecT String () Identity Abity
abity)
  GlobalIdent
name <- Parser GlobalIdent -> Parser GlobalIdent
forall a. Parser a -> Parser a
ws Parser GlobalIdent
global
  [FuncParam]
args <- Parser [FuncParam] -> Parser [FuncParam]
forall a. Parser a -> Parser a
wsNL Parser [FuncParam]
params
  [Block']
body <- ParsecT String () Identity Char
-> ParsecT String () Identity Char
-> ParsecT String () Identity [Block']
-> ParsecT String () Identity [Block']
forall s (m :: * -> *) t u open close a.
Stream s m t =>
ParsecT s u m open
-> ParsecT s u m close -> ParsecT s u m a -> ParsecT s u m a
between (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL1 (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'{') (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
wsNL (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'}') (ParsecT String () Identity [Block']
 -> ParsecT String () Identity [Block'])
-> ParsecT String () Identity [Block']
-> ParsecT String () Identity [Block']
forall a b. (a -> b) -> a -> b
$ ParsecT String () Identity Block'
-> ParsecT String () Identity [Block']
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many1 ParsecT String () Identity Block'
block

  case ([Block'] -> Maybe [Block]
insertJumps [Block']
body) of
    Maybe [Block]
Nothing -> String -> Parser FuncDef
forall a. String -> ParsecT String () Identity a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> Parser FuncDef) -> String -> Parser FuncDef
forall a b. (a -> b) -> a -> b
$ String
"invalid fallthrough in " String -> String -> String
forall a. [a] -> [a] -> [a]
++ GlobalIdent -> String
forall a. Show a => a -> String
show GlobalIdent
name
    Just [] -> String -> Parser FuncDef
forall a. HasCallStack => String -> a
error String
"unreachable" -- TODO: Use NonEmpty
    Just blocks :: [Block]
blocks@(Block
startBlk:[Block]
_) ->
      FuncDef -> Parser FuncDef
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (FuncDef -> Parser FuncDef) -> FuncDef -> Parser FuncDef
forall a b. (a -> b) -> a -> b
$
        Q.FuncDef {
          fLinkage :: [Linkage]
Q.fLinkage = [Linkage]
link,
          fName :: GlobalIdent
Q.fName = GlobalIdent
name,
          fStart :: BlockIdent
Q.fStart = Block -> BlockIdent
Q.label Block
startBlk,
          fAbity :: Maybe Abity
Q.fAbity = Maybe Abity
retTy,
          fParams :: [FuncParam]
Q.fParams = [FuncParam]
args,
          fBlock :: Map BlockIdent Block
Q.fBlock = [Block] -> Map BlockIdent Block
blkMap [Block]
blocks
        }
\end{code}

Function definitions contain the actual code to emit in the compiled
file. They define a global symbol that contains a pointer to the
function code. This pointer can be used in \texttt{call} instructions or stored
in memory.

\begin{code}
subWordType :: Parser Q.SubWordType
subWordType :: Parser SubWordType
subWordType = [Parser SubWordType] -> Parser SubWordType
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
  [ Parser SubWordType -> Parser SubWordType
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser SubWordType -> Parser SubWordType)
-> Parser SubWordType -> Parser SubWordType
forall a b. (a -> b) -> a -> b
$ String -> SubWordType -> Parser SubWordType
forall a. String -> a -> Parser a
bind String
"sb" SubWordType
Q.SignedByte
  , Parser SubWordType -> Parser SubWordType
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser SubWordType -> Parser SubWordType)
-> Parser SubWordType -> Parser SubWordType
forall a b. (a -> b) -> a -> b
$ String -> SubWordType -> Parser SubWordType
forall a. String -> a -> Parser a
bind String
"ub" SubWordType
Q.UnsignedByte
  , String -> SubWordType -> Parser SubWordType
forall a. String -> a -> Parser a
bind String
"sh" SubWordType
Q.SignedHalf
  , String -> SubWordType -> Parser SubWordType
forall a. String -> a -> Parser a
bind String
"uh" SubWordType
Q.UnsignedHalf ]

abity :: Parser Q.Abity
abity :: ParsecT String () Identity Abity
abity = ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall tok st a. GenParser tok st a -> GenParser tok st a
try (SubWordType -> Abity
Q.ASubWordType (SubWordType -> Abity)
-> Parser SubWordType -> ParsecT String () Identity Abity
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser SubWordType
subWordType)
    ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (BaseType -> Abity
Q.ABase (BaseType -> Abity)
-> Parser BaseType -> ParsecT String () Identity Abity
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser BaseType
baseType)
    ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (UserIdent -> Abity
Q.AUserDef (UserIdent -> Abity)
-> Parser UserIdent -> ParsecT String () Identity Abity
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser UserIdent
userDef)
\end{code}

The type given right before the function name is the return type of the
function. All return values of this function must have this return type.
If the return type is missing, the function must not return any value.

\begin{code}
param :: Parser Q.FuncParam
param :: Parser FuncParam
param = (LocalIdent -> FuncParam
Q.Env (LocalIdent -> FuncParam) -> Parser LocalIdent -> Parser FuncParam
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"env") ParsecT String () Identity String
-> Parser LocalIdent -> Parser LocalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser LocalIdent
local))
    Parser FuncParam -> Parser FuncParam -> Parser FuncParam
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"..." ParsecT String () Identity String
-> Parser FuncParam -> Parser FuncParam
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> FuncParam -> Parser FuncParam
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure FuncParam
Q.Variadic)
    Parser FuncParam -> Parser FuncParam -> Parser FuncParam
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> do
          Abity
ty <- ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall a. Parser a -> Parser a
ws1 ParsecT String () Identity Abity
abity
          Abity -> LocalIdent -> FuncParam
Q.Regular Abity
ty (LocalIdent -> FuncParam) -> Parser LocalIdent -> Parser FuncParam
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser LocalIdent
local

params :: Parser [Q.FuncParam]
params :: Parser [FuncParam]
params = Parser FuncParam -> Parser [FuncParam]
forall a. Parser a -> Parser [a]
parenLst Parser FuncParam
param
\end{code}

The parameter list is a comma separated list of temporary names prefixed
by types. The types are used to correctly implement C compatibility.
When an argument has an aggregate type, a pointer to the aggregate is
passed by thea caller. In the example below, we have to use a load
instruction to get the value of the first (and only) member of the
struct.

\begin{verbatim}
type :one = { w }

function w $getone(:one %p) {
@start
        %val =w loadw %p
        ret %val
}
\end{verbatim}

If a function accepts or returns values that are smaller than a word,
such as \texttt{signed char} or \texttt{unsigned short} in C, one of the sub-word type
must be used. The sub-word types \texttt{sb}, \texttt{ub}, \texttt{sh}, and \texttt{uh} stand,
respectively, for signed and unsigned 8-bit values, and signed and
unsigned 16-bit values. Parameters associated with a sub-word type of
bit width N only have their N least significant bits set and have base
type \texttt{w}. For example, the function

\begin{verbatim}
function w $addbyte(w %a, sb %b) {
@start
        %bw =w extsb %b
        %val =w add %a, %bw
        ret %val
}
\end{verbatim}

needs to sign-extend its second argument before the addition. Dually,
return values with sub-word types do not need to be sign or zero
extended.

If the parameter list ends with \texttt{...}, the function is a variadic
function: it can accept a variable number of arguments. To access the
extra arguments provided by the caller, use the \texttt{vastart} and \texttt{vaarg}
instructions described in the \nameref{sec:variadic} section.

Optionally, the parameter list can start with an environment parameter
\texttt{env \%e}. This special parameter is a 64-bit integer temporary (i.e.,
of type \texttt{l}). If the function does not use its environment parameter,
callers can safely omit it. This parameter is invisible to a C caller:
for example, the function

\begin{verbatim}
export function w $add(env %e, w %a, w %b) {
@start
        %c =w add %a, %b
        ret %c
}
\end{verbatim}

must be given the C prototype \texttt{int add(int, int)}. The intended use of
this feature is to pass the environment pointer of closures while
retaining a very good compatibility with C. The \nameref{sec:call}
section explains how to pass an environment parameter.

Since global symbols are defined mutually recursive, there is no need
for function declarations: a function can be referenced before its
definition. Similarly, functions from other modules can be used without
previous declaration. All the type information necessary to compile a
call is in the instruction itself.

The syntax and semantics for the body of functions are described in the
\nameref{sec:control} section.

\section{Control}
\label{sec:control}

The IL represents programs as textual transcriptions of control flow
graphs. The control flow is serialized as a sequence of blocks of
straight-line code which are connected using jump instructions.

\subsection{Blocks}
\label{sec:blocks}

\ignore{
\begin{code}
-- Basic block abstraction with optional exit points. The 'insertJumps'
-- function takes care of inserting fallthrough for omitted jumps.
data Block'
  = Block'
  { Block' -> BlockIdent
label' :: Q.BlockIdent,
    Block' -> [Phi]
phi' :: [Q.Phi],
    Block' -> [Statement]
stmt' :: [Q.Statement],
    Block' -> Maybe JumpInstr
term' :: Maybe Q.JumpInstr
  }
  deriving (Int -> Block' -> String -> String
[Block'] -> String -> String
Block' -> String
(Int -> Block' -> String -> String)
-> (Block' -> String)
-> ([Block'] -> String -> String)
-> Show Block'
forall a.
(Int -> a -> String -> String)
-> (a -> String) -> ([a] -> String -> String) -> Show a
$cshowsPrec :: Int -> Block' -> String -> String
showsPrec :: Int -> Block' -> String -> String
$cshow :: Block' -> String
show :: Block' -> String
$cshowList :: [Block'] -> String -> String
showList :: [Block'] -> String -> String
Show, Block' -> Block' -> Bool
(Block' -> Block' -> Bool)
-> (Block' -> Block' -> Bool) -> Eq Block'
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: Block' -> Block' -> Bool
== :: Block' -> Block' -> Bool
$c/= :: Block' -> Block' -> Bool
/= :: Block' -> Block' -> Bool
Eq)

blkMap :: [Q.Block] -> Map Q.BlockIdent Q.Block
blkMap :: [Block] -> Map BlockIdent Block
blkMap = [(BlockIdent, Block)] -> Map BlockIdent Block
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(BlockIdent, Block)] -> Map BlockIdent Block)
-> ([Block] -> [(BlockIdent, Block)])
-> [Block]
-> Map BlockIdent Block
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Block -> (BlockIdent, Block)) -> [Block] -> [(BlockIdent, Block)]
forall a b. (a -> b) -> [a] -> [b]
map (\Block
b -> (Block -> BlockIdent
Q.label Block
b, Block
b))

insertJumps :: [Block'] -> Maybe [Q.Block]
insertJumps :: [Block'] -> Maybe [Block]
insertJumps [Block']
xs = ([Block] -> (Block', Maybe Block') -> Maybe [Block])
-> [Block] -> [(Block', Maybe Block')] -> Maybe [Block]
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM [Block] -> (Block', Maybe Block') -> Maybe [Block]
go [] ([(Block', Maybe Block')] -> Maybe [Block])
-> [(Block', Maybe Block')] -> Maybe [Block]
forall a b. (a -> b) -> a -> b
$ [Block'] -> [(Block', Maybe Block')]
forall a. [a] -> [(a, Maybe a)]
zipWithNext [Block']
xs
  where
    zipWithNext :: [a] -> [(a, Maybe a)]
    zipWithNext :: forall a. [a] -> [(a, Maybe a)]
zipWithNext [] = []
    zipWithNext lst :: [a]
lst@(a
_ : [a]
t) = [a] -> [Maybe a] -> [(a, Maybe a)]
forall a b. [a] -> [b] -> [(a, b)]
zip [a]
lst ([Maybe a] -> [(a, Maybe a)]) -> [Maybe a] -> [(a, Maybe a)]
forall a b. (a -> b) -> a -> b
$ (a -> Maybe a) -> [a] -> [Maybe a]
forall a b. (a -> b) -> [a] -> [b]
map a -> Maybe a
forall a. a -> Maybe a
Just [a]
t [Maybe a] -> [Maybe a] -> [Maybe a]
forall a. [a] -> [a] -> [a]
++ [Maybe a
forall a. Maybe a
Nothing]

    fromBlock' :: Block' -> Q.JumpInstr -> Q.Block
    fromBlock' :: Block' -> JumpInstr -> Block
fromBlock' (Block' BlockIdent
l [Phi]
p [Statement]
s Maybe JumpInstr
_) = BlockIdent -> [Phi] -> [Statement] -> JumpInstr -> Block
Q.Block BlockIdent
l [Phi]
p [Statement]
s

    go :: [Q.Block] -> (Block', Maybe Block') -> Maybe [Q.Block]
    go :: [Block] -> (Block', Maybe Block') -> Maybe [Block]
go [Block]
acc (x :: Block'
x@Block' {term' :: Block' -> Maybe JumpInstr
term' = Just JumpInstr
ji}, Maybe Block'
_) =
      [Block] -> Maybe [Block]
forall a. a -> Maybe a
Just ([Block]
acc [Block] -> [Block] -> [Block]
forall a. [a] -> [a] -> [a]
++ [Block' -> JumpInstr -> Block
fromBlock' Block'
x JumpInstr
ji])
    go [Block]
acc (x :: Block'
x@Block' {term' :: Block' -> Maybe JumpInstr
term' = Maybe JumpInstr
Nothing}, Just Block'
nxt) =
      [Block] -> Maybe [Block]
forall a. a -> Maybe a
Just ([Block]
acc [Block] -> [Block] -> [Block]
forall a. [a] -> [a] -> [a]
++ [Block' -> JumpInstr -> Block
fromBlock' Block'
x (BlockIdent -> JumpInstr
Q.Jump (BlockIdent -> JumpInstr) -> BlockIdent -> JumpInstr
forall a b. (a -> b) -> a -> b
$ Block' -> BlockIdent
label' Block'
nxt)])
    go [Block]
_ (Block' {term' :: Block' -> Maybe JumpInstr
term' = Maybe JumpInstr
Nothing}, Maybe Block'
Nothing) =
      Maybe [Block]
forall a. Maybe a
Nothing
\end{code}
}

\begin{code}
block :: Parser Block'
block :: ParsecT String () Identity Block'
block = do
  BlockIdent
l <- Parser BlockIdent -> Parser BlockIdent
forall a. Parser a -> Parser a
wsNL1 Parser BlockIdent
label
  [Phi]
p <- ParsecT String () Identity Phi -> ParsecT String () Identity [Phi]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many (ParsecT String () Identity Phi -> ParsecT String () Identity Phi
forall a. Parser a -> Parser a
wsNL1 (ParsecT String () Identity Phi -> ParsecT String () Identity Phi)
-> ParsecT String () Identity Phi -> ParsecT String () Identity Phi
forall a b. (a -> b) -> a -> b
$ ParsecT String () Identity Phi -> ParsecT String () Identity Phi
forall tok st a. GenParser tok st a -> GenParser tok st a
try ParsecT String () Identity Phi
phiInstr)
  [Statement]
s <- ParsecT String () Identity Statement
-> ParsecT String () Identity [Statement]
forall s u (m :: * -> *) a. ParsecT s u m a -> ParsecT s u m [a]
many (ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
forall a. Parser a -> Parser a
wsNL1 ParsecT String () Identity Statement
statement)
  BlockIdent -> [Phi] -> [Statement] -> Maybe JumpInstr -> Block'
Block' BlockIdent
l [Phi]
p [Statement]
s (Maybe JumpInstr -> Block')
-> ParsecT String () Identity (Maybe JumpInstr)
-> ParsecT String () Identity Block'
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (ParsecT String () Identity JumpInstr
-> ParsecT String () Identity (Maybe JumpInstr)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe (ParsecT String () Identity JumpInstr
 -> ParsecT String () Identity (Maybe JumpInstr))
-> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity (Maybe JumpInstr)
forall a b. (a -> b) -> a -> b
$ ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall a. Parser a -> Parser a
wsNL1 ParsecT String () Identity JumpInstr
jumpInstr)
\end{code}

All blocks have a name that is specified by a label at their beginning.
Then follows a sequence of instructions that have "fall-through" flow.
Finally one jump terminates the block. The jump can either transfer
control to another block of the same function or return; jumps are
described further below.

The first block in a function must not be the target of any jump in the
program. If a jump to the function start is needed, the frontend must
insert an empty prelude block at the beginning of the function.

When one block jumps to the next block in the IL file, it is not
necessary to write the jump instruction, it will be automatically added
by the parser. For example the start block in the example below jumps
directly to the loop block.

\subsection{Jumps}
\label{sec:jumps}

\begin{code}
jumpInstr :: Parser Q.JumpInstr
jumpInstr :: ParsecT String () Identity JumpInstr
jumpInstr = (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"hlt" ParsecT String () Identity String
-> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> JumpInstr -> ParsecT String () Identity JumpInstr
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure JumpInstr
Q.Halt)
        -- TODO: Return requires a space if there is an optionMaybe
        ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Maybe Value -> JumpInstr
Q.Return (Maybe Value -> JumpInstr)
-> ParsecT String () Identity (Maybe Value)
-> ParsecT String () Identity JumpInstr
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"ret") ParsecT String () Identity String
-> ParsecT String () Identity (Maybe Value)
-> ParsecT String () Identity (Maybe Value)
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Value
-> ParsecT String () Identity (Maybe Value)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe ParsecT String () Identity Value
val)
        ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (BlockIdent -> JumpInstr
Q.Jump (BlockIdent -> JumpInstr)
-> Parser BlockIdent -> ParsecT String () Identity JumpInstr
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ((ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"jmp") ParsecT String () Identity String
-> Parser BlockIdent -> Parser BlockIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser BlockIdent
label))
        ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
-> ParsecT String () Identity JumpInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> do
          String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"jnz"
          Value
v <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> ParsecT String () Identity Char
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
          BlockIdent
l1 <- Parser BlockIdent -> Parser BlockIdent
forall a. Parser a -> Parser a
ws Parser BlockIdent
label Parser BlockIdent
-> ParsecT String () Identity Char -> Parser BlockIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
          BlockIdent
l2 <- Parser BlockIdent -> Parser BlockIdent
forall a. Parser a -> Parser a
ws Parser BlockIdent
label
          JumpInstr -> ParsecT String () Identity JumpInstr
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (JumpInstr -> ParsecT String () Identity JumpInstr)
-> JumpInstr -> ParsecT String () Identity JumpInstr
forall a b. (a -> b) -> a -> b
$ Value -> BlockIdent -> BlockIdent -> JumpInstr
Q.Jnz Value
v BlockIdent
l1 BlockIdent
l2
\end{code}

A jump instruction ends every block and transfers the control to another
program location. The target of a jump must never be the first block in
a function. The three kinds of jumps available are described in the
following list.

\begin{enumerate}
  \item \textbf{Unconditional jump.} Jumps to another block of the same function.
  \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.
  \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.
  \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()}.
\end{enumerate}

\section{Instructions}
\label{sec:instructions}

\begin{code}
instr :: Parser Q.Instr
instr :: Parser Instr
instr =
  [Parser Instr] -> Parser Instr
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
    [ Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Add String
"add",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Sub String
"sub",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Mul String
"mul",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Div String
"div",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.URem String
"urem",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Rem String
"rem",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.UDiv String
"udiv",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Or String
"or",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Xor String
"xor",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.And String
"and",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Sar String
"sar",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Shr String
"shr",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Value -> Instr) -> String -> Parser Instr
binaryInstr Value -> Value -> Instr
Q.Shl String
"shl",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Instr) -> String -> Parser Instr
unaryInstr Value -> Instr
Q.Neg String
"neg",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Instr) -> String -> Parser Instr
unaryInstr Value -> Instr
Q.Cast String
"cast",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Instr) -> String -> Parser Instr
unaryInstr Value -> Instr
Q.Copy String
"copy",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ (Value -> Instr) -> String -> Parser Instr
unaryInstr Value -> Instr
Q.VAArg String
"vaarg",
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
loadInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
allocInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
compareInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
extInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
truncInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
fromFloatInstr,
      Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser Instr -> Parser Instr) -> Parser Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ Parser Instr
toFloatInstr
    ]
\end{code}

Instructions are the smallest piece of code in the IL, they form the body of
\nameref{sec:blocks}. This specification distinguishes instructions and
volatile instructions, the latter do not return a value. For the former, the IL
uses a three-address code, which means that one instruction computes an
operation between two operands and assigns the result to a third one.

\begin{code}
assign :: Parser Q.Statement
assign :: ParsecT String () Identity Statement
assign = do
  LocalIdent
n <- Parser LocalIdent -> Parser LocalIdent
forall a. Parser a -> Parser a
ws Parser LocalIdent
local
  BaseType
t <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'=') ParsecT String () Identity Char
-> Parser BaseType -> Parser BaseType
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser BaseType -> Parser BaseType
forall a. Parser a -> Parser a
ws1 Parser BaseType
baseType
  LocalIdent -> BaseType -> Instr -> Statement
Q.Assign LocalIdent
n BaseType
t (Instr -> Statement)
-> Parser Instr -> ParsecT String () Identity Statement
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser Instr
instr

volatileInstr :: Parser Q.Statement
volatileInstr :: ParsecT String () Identity Statement
volatileInstr =
  VolatileInstr -> Statement
Q.Volatile (VolatileInstr -> Statement)
-> ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity Statement
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
    (ParsecT String () Identity VolatileInstr
storeInstr ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity VolatileInstr
blitInstr ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity VolatileInstr
vastartInstr ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
-> ParsecT String () Identity VolatileInstr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity VolatileInstr
dbglocInstr)

-- TODO: Not documented in the QBE BNF.
statement :: Parser Q.Statement
statement :: ParsecT String () Identity Statement
statement = (ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
forall tok st a. GenParser tok st a -> GenParser tok st a
try ParsecT String () Identity Statement
callInstr) ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity Statement
assign ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
-> ParsecT String () Identity Statement
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> ParsecT String () Identity Statement
volatileInstr
\end{code}

An instruction has both a name and a return type, this return type is a base
type that defines the size of the instruction's result. The type of the
arguments can be unambiguously inferred using the instruction name and the
return type. For example, for all arithmetic instructions, the type of the
arguments is the same as the return type. The two additions below are valid if
\texttt{\%y} is a word or a long (because of \nameref{sec:subtyping}).

\begin{verbatim}
%x =w add 0, %y
%z =w add %x, %x
\end{verbatim}

Some instructions, like comparisons and memory loads have operand types
that differ from their return types. For instance, two floating points
can be compared to give a word result (0 if the comparison succeeds, 1
if it fails).

\begin{verbatim}
%c =w cgts %a, %b
\end{verbatim}

In the example above, both operands have to have single type. This is
made explicit by the instruction suffix.

\subsection{Arithmetic and Bits}

\begin{quote}
\begin{itemize}
\item \texttt{add}, \texttt{sub}, \texttt{div}, \texttt{mul}
\item \texttt{neg}
\item \texttt{udiv}, \texttt{rem}, \texttt{urem}
\item \texttt{or}, \texttt{xor}, \texttt{and}
\item \texttt{sar}, \texttt{shr}, \texttt{shl}
\end{itemize}
\end{quote}

The base arithmetic instructions in the first bullet are available for
all types, integers and floating points.

When \texttt{div} is used with word or long return type, the arguments are
treated as signed. The unsigned integral division is available as \texttt{udiv}
instruction. When the result of a division is not an integer, it is truncated
towards zero.

The signed and unsigned remainder operations are available as \texttt{rem} and
\texttt{urem}. The sign of the remainder is the same as the one of the
dividend. Its magnitude is smaller than the divisor one. These two instructions
and \texttt{udiv} are only available with integer arguments and result.

Bitwise OR, AND, and XOR operations are available for both integer
types. Logical operations of typical programming languages can be
implemented using \nameref{sec:comparisions} and \nameref{sec:jumps}.

Shift instructions \texttt{sar}, \texttt{shr}, and \texttt{shl}, shift right or
left their first operand by the amount from the second operand. The shifting
amount is taken modulo the size of the result type. Shifting right can either
preserve the sign of the value (using \texttt{sar}), or fill the newly freed
bits with zeroes (using \texttt{shr}). Shifting left always fills the freed
bits with zeroes.

Remark that an arithmetic shift right (\texttt{sar}) is only equivalent to a
division by a power of two for non-negative numbers. This is because the shift
right "truncates" towards minus infinity, while the division truncates towards
zero.

\subsection{Memory}
\label{sec:memory}

The following sections discuss instructions for interacting with values stored in memory.

\subsubsection{Store instructions}

\begin{code}
storeInstr :: Parser Q.VolatileInstr
storeInstr :: ParsecT String () Identity VolatileInstr
storeInstr = do
  ExtType
t <- String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"store" ParsecT String () Identity String
-> Parser ExtType -> Parser ExtType
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser ExtType -> Parser ExtType
forall a. Parser a -> Parser a
ws1 Parser ExtType
extType
  Value
v <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val
  Char
_ <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
','
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> VolatileInstr)
-> ParsecT String () Identity VolatileInstr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> ExtType -> Value -> Value -> VolatileInstr
Q.Store ExtType
t Value
v
\end{code}

Store instructions exist to store a value of any base type and any extended
type. Since halfwords and bytes are not first class in the IL, \texttt{storeh}
and \texttt{storeb} take a word as argument. Only the first 16 or 8 bits of
this word will be stored in memory at the address specified in the second
argument.

\subsubsection{Load instructions}

\begin{code}
loadInstr :: Parser Q.Instr
loadInstr :: Parser Instr
loadInstr = do
  String
_ <- String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"load"
  LoadType
t <- Parser LoadType -> Parser LoadType
forall a. Parser a -> Parser a
ws1 (Parser LoadType -> Parser LoadType)
-> Parser LoadType -> Parser LoadType
forall a b. (a -> b) -> a -> b
$ [Parser LoadType] -> Parser LoadType
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
    [ Parser LoadType -> Parser LoadType
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser LoadType -> Parser LoadType)
-> Parser LoadType -> Parser LoadType
forall a b. (a -> b) -> a -> b
$ String -> LoadType -> Parser LoadType
forall a. String -> a -> Parser a
bind String
"sw" (BaseType -> LoadType
Q.LBase BaseType
Q.Word),
      Parser LoadType -> Parser LoadType
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser LoadType -> Parser LoadType)
-> Parser LoadType -> Parser LoadType
forall a b. (a -> b) -> a -> b
$ String -> LoadType -> Parser LoadType
forall a. String -> a -> Parser a
bind String
"uw" (BaseType -> LoadType
Q.LBase BaseType
Q.Word),
      Parser LoadType -> Parser LoadType
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser LoadType -> Parser LoadType)
-> Parser LoadType -> Parser LoadType
forall a b. (a -> b) -> a -> b
$ SubWordType -> LoadType
Q.LSubWord (SubWordType -> LoadType) -> Parser SubWordType -> Parser LoadType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser SubWordType
subWordType,
      BaseType -> LoadType
Q.LBase (BaseType -> LoadType) -> Parser BaseType -> Parser LoadType
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser BaseType
baseType
    ]
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> LoadType -> Value -> Instr
Q.Load LoadType
t
\end{code}

For types smaller than long, two variants of the load instruction are
available: one will sign extend the loaded value, while the other will zero
extend it. Note that all loads smaller than long can load to either a long or a
word.

The two instructions \texttt{loadsw} and \texttt{loaduw} have the same effect
when they are used to define a word temporary. A \texttt{loadw} instruction is
provided as syntactic sugar for \texttt{loadsw} to make explicit that the
extension mechanism used is irrelevant.

\subsubsection{Blits}

\begin{code}
blitInstr :: Parser Q.VolatileInstr
blitInstr :: ParsecT String () Identity VolatileInstr
blitInstr = do
  Value
v1 <- (ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"blit") ParsecT String () Identity String
-> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> ParsecT String () Identity Char
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Value
v2 <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> ParsecT String () Identity Char
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Word64
nb <- Parser Word64
decNumber
  VolatileInstr -> ParsecT String () Identity VolatileInstr
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (VolatileInstr -> ParsecT String () Identity VolatileInstr)
-> VolatileInstr -> ParsecT String () Identity VolatileInstr
forall a b. (a -> b) -> a -> b
$ Value -> Value -> Word64 -> VolatileInstr
Q.Blit Value
v1 Value
v2 Word64
nb
\end{code}

The blit instruction copies in-memory data from its first address argument to
its second address argument. The third argument is the number of bytes to copy.
The source and destination spans are required to be either non-overlapping, or
fully overlapping (source address identical to the destination address). The
byte count argument must be a nonnegative numeric constant; it cannot be a
temporary.

One blit instruction may generate a number of instructions proportional to its
byte count argument, consequently, it is recommended to keep this argument
relatively small. If large copies are necessary, it is preferable that
frontends generate calls to a supporting \texttt{memcpy} function.

\subsubsection{Stack Allocation}

\begin{code}
allocInstr :: Parser Q.Instr
allocInstr :: Parser Instr
allocInstr = do
  AllocSize
siz <- (ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"alloc") ParsecT String () Identity String
-> Parser AllocSize -> Parser AllocSize
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> (Parser AllocSize -> Parser AllocSize
forall a. Parser a -> Parser a
ws1 Parser AllocSize
allocSize)
  ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> AllocSize -> Value -> Instr
Q.Alloc AllocSize
siz
\end{code}

These instructions allocate a chunk of memory on the stack. The number ending
the instruction name is the alignment required for the allocated slot. QBE will
make sure that the returned address is a multiple of that alignment value.

Stack allocation instructions are used, for example, when compiling the C local
variables, because their address can be taken. When compiling Fortran,
temporaries can be used directly instead, because it is illegal to take the
address of a variable.

\subsection{Comparisons}
\label{sec:comparisions}

\begin{code}
compareInstr :: Parser Q.Instr
compareInstr :: Parser Instr
compareInstr = do
  Char
_ <- Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'c'
  (Parser Instr -> Parser Instr
forall tok st a. GenParser tok st a -> GenParser tok st a
try Parser Instr
intCompare) Parser Instr -> Parser Instr -> Parser Instr
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser Instr
floatCompare

compareArgs :: Parser (Q.Value, Q.Value)
compareArgs :: Parser (Value, Value)
compareArgs = do
  Value
lhs <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> ParsecT String () Identity Char
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Value
rhs <- ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val
  (Value, Value) -> Parser (Value, Value)
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Value
lhs, Value
rhs)

intCompare :: Parser Q.Instr
intCompare :: Parser Instr
intCompare = do
  IntCmpOp
op <- Parser IntCmpOp
compareIntOp
  IntArg
ty <- Parser IntArg -> Parser IntArg
forall a. Parser a -> Parser a
ws1 Parser IntArg
intArg

  (Value
lhs, Value
rhs) <- Parser (Value, Value)
compareArgs
  Instr -> Parser Instr
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Instr -> Parser Instr) -> Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ IntArg -> IntCmpOp -> Value -> Value -> Instr
Q.CompareInt IntArg
ty IntCmpOp
op Value
lhs Value
rhs

floatCompare :: Parser Q.Instr
floatCompare :: Parser Instr
floatCompare = do
  FloatCmpOp
op <- Parser FloatCmpOp
compareFloatOp
  FloatArg
ty <- Parser FloatArg -> Parser FloatArg
forall a. Parser a -> Parser a
ws1 Parser FloatArg
floatArg

  (Value
lhs, Value
rhs) <- Parser (Value, Value)
compareArgs
  Instr -> Parser Instr
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Instr -> Parser Instr) -> Instr -> Parser Instr
forall a b. (a -> b) -> a -> b
$ FloatArg -> FloatCmpOp -> Value -> Value -> Instr
Q.CompareFloat FloatArg
ty FloatCmpOp
op Value
lhs Value
rhs
\end{code}

Comparison instructions return an integer value (either a word or a long), and
compare values of arbitrary types. The returned value is 1 if the two operands
satisfy the comparison relation, or 0 otherwise. The names of comparisons
respect a standard naming scheme in three parts:

\begin{enumerate}
  \item All comparisons start with the letter \texttt{c}.
  \item Then comes a comparison type.
  \item Finally, the instruction name is terminated with a basic type suffix precising the type of the operands to be compared.
\end{enumerate}

The following instruction are available for integer comparisons:

\begin{code}
compareIntOp :: Parser Q.IntCmpOp
compareIntOp :: Parser IntCmpOp
compareIntOp = [Parser IntCmpOp] -> Parser IntCmpOp
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
  [ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"eq" IntCmpOp
Q.IEq
  , String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"ne" IntCmpOp
Q.INe
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"sle" IntCmpOp
Q.ISle
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"slt" IntCmpOp
Q.ISlt
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"sge" IntCmpOp
Q.ISge
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"sgt" IntCmpOp
Q.ISgt
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"ule" IntCmpOp
Q.IUle
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"ult" IntCmpOp
Q.IUlt
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"uge" IntCmpOp
Q.IUge
  , Parser IntCmpOp -> Parser IntCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser IntCmpOp -> Parser IntCmpOp)
-> Parser IntCmpOp -> Parser IntCmpOp
forall a b. (a -> b) -> a -> b
$ String -> IntCmpOp -> Parser IntCmpOp
forall a. String -> a -> Parser a
bind String
"ugt" IntCmpOp
Q.IUgt ]
\end{code}

For floating point comparisons use one of these instructions:

\begin{code}
compareFloatOp :: Parser Q.FloatCmpOp
compareFloatOp :: Parser FloatCmpOp
compareFloatOp = [Parser FloatCmpOp] -> Parser FloatCmpOp
forall s (m :: * -> *) t u a.
Stream s m t =>
[ParsecT s u m a] -> ParsecT s u m a
choice
  [ String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"eq" FloatCmpOp
Q.FEq
  , String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"ne" FloatCmpOp
Q.FNe
  , Parser FloatCmpOp -> Parser FloatCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser FloatCmpOp -> Parser FloatCmpOp)
-> Parser FloatCmpOp -> Parser FloatCmpOp
forall a b. (a -> b) -> a -> b
$ String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"le" FloatCmpOp
Q.FLe
  , String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"lt" FloatCmpOp
Q.FLt
  , Parser FloatCmpOp -> Parser FloatCmpOp
forall tok st a. GenParser tok st a -> GenParser tok st a
try (Parser FloatCmpOp -> Parser FloatCmpOp)
-> Parser FloatCmpOp -> Parser FloatCmpOp
forall a b. (a -> b) -> a -> b
$ String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"ge" FloatCmpOp
Q.FGe
  , String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"gt" FloatCmpOp
Q.FGt
  , String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"o" FloatCmpOp
Q.FOrd
  , String -> FloatCmpOp -> Parser FloatCmpOp
forall a. String -> a -> Parser a
bind String
"uo" FloatCmpOp
Q.FUnord ]
\end{code}

For example, \texttt{cod} compares two double-precision floating point numbers
and returns 1 if the two floating points are not NaNs, or 0 otherwise. The
\texttt{csltw} instruction compares two words representing signed numbers and
returns 1 when the first argument is smaller than the second one.

\subsection{Conversions}

Conversion operations change the representation of a value, possibly modifying
it if the target type cannot hold the value of the source type. Conversions can
extend the precision of a temporary (e.g., from signed 8-bit to 32-bit), or
convert a floating point into an integer and vice versa.

\begin{code}
extInstr :: Parser Q.Instr
extInstr :: Parser Instr
extInstr = do
  String
_ <- String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"ext"
  ExtArg
ty <- Parser ExtArg -> Parser ExtArg
forall a. Parser a -> Parser a
ws1 Parser ExtArg
extArg
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> ExtArg -> Value -> Instr
Q.Ext ExtArg
ty
 where
  extArg :: Parser Q.ExtArg
  extArg :: Parser ExtArg
extArg = Parser ExtArg -> Parser ExtArg
forall tok st a. GenParser tok st a -> GenParser tok st a
try (SubWordType -> ExtArg
Q.ExtSubWord (SubWordType -> ExtArg) -> Parser SubWordType -> Parser ExtArg
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser SubWordType
subWordType)
    Parser ExtArg -> Parser ExtArg -> Parser ExtArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> Parser ExtArg -> Parser ExtArg
forall tok st a. GenParser tok st a -> GenParser tok st a
try (String -> ExtArg -> Parser ExtArg
forall a. String -> a -> Parser a
bind String
"sw" ExtArg
Q.ExtSignedWord)
    Parser ExtArg -> Parser ExtArg -> Parser ExtArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ExtArg -> Parser ExtArg
forall a. String -> a -> Parser a
bind String
"s" ExtArg
Q.ExtSingle
    Parser ExtArg -> Parser ExtArg -> Parser ExtArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> ExtArg -> Parser ExtArg
forall a. String -> a -> Parser a
bind String
"uw" ExtArg
Q.ExtUnsignedWord
\end{code}

Extending the precision of a temporary is done using the \texttt{ext} family of
instructions. Because QBE types do not specify the signedness (like in LLVM),
extension instructions exist to sign-extend and zero-extend a value. For
example, \texttt{extsb} takes a word argument and sign-extends the 8
least-significant bits to a full word or long, depending on the return type.

\begin{code}
truncInstr :: Parser Q.Instr
truncInstr :: Parser Instr
truncInstr = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"truncd"
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> Value -> Instr
Q.TruncDouble
\end{code}

The instructions \texttt{exts} (extend single) and \texttt{truncd} (truncate
double) are provided to change the precision of a floating point value. When
the double argument of truncd cannot be represented as a single-precision
floating point, it is truncated towards zero.

\begin{code}
floatArg :: Parser Q.FloatArg
floatArg :: Parser FloatArg
floatArg = String -> FloatArg -> Parser FloatArg
forall a. String -> a -> Parser a
bind String
"d" FloatArg
Q.FDouble Parser FloatArg -> Parser FloatArg -> Parser FloatArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> FloatArg -> Parser FloatArg
forall a. String -> a -> Parser a
bind String
"s" FloatArg
Q.FSingle

fromFloatInstr :: Parser Q.Instr
fromFloatInstr :: Parser Instr
fromFloatInstr = do
  FloatArg
arg <- Parser FloatArg
floatArg Parser FloatArg
-> ParsecT String () Identity String -> Parser FloatArg
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"to"
  Bool
isSigned <- Parser Bool
signageChar
  Char
_ <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'i'
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> FloatArg -> Bool -> Value -> Instr
Q.FloatToInt FloatArg
arg Bool
isSigned

intArg :: Parser Q.IntArg
intArg :: Parser IntArg
intArg = String -> IntArg -> Parser IntArg
forall a. String -> a -> Parser a
bind String
"w" IntArg
Q.IWord Parser IntArg -> Parser IntArg -> Parser IntArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> String -> IntArg -> Parser IntArg
forall a. String -> a -> Parser a
bind String
"l" IntArg
Q.ILong

toFloatInstr :: Parser Q.Instr
toFloatInstr :: Parser Instr
toFloatInstr = do
  Bool
isSigned <- Parser Bool
signageChar
  IntArg
arg <- Parser IntArg
intArg
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"tof"
  ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val ParsecT String () Identity Value
-> (Value -> Instr) -> Parser Instr
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> IntArg -> Bool -> Value -> Instr
Q.IntToFloat IntArg
arg Bool
isSigned
\end{code}

Converting between signed integers and floating points is done using
\texttt{stosi} (single to signed integer), \texttt{stoui} (single to unsigned
integer), \texttt{dtosi} (double to signed integer), \texttt{dtoui} (double to
unsigned integer), \texttt{swtof} (signed word to float), \texttt{uwtof}
(unsigned word to float), \texttt{sltof} (signed long to float) and
\texttt{ultof} (unsigned long to float).

\subsection{Cast and Copy}

The \texttt{cast} and \texttt{copy} instructions return the bits of their
argument verbatim. However a cast will change an integer into a floating point
of the same width and vice versa.

Casts can be used to make bitwise operations on the representation of floating
point numbers. For example the following program will compute the opposite of
the single-precision floating point number \texttt{\%f} into \texttt{\%rs}.

\begin{verbatim}
%b0 =w cast %f
%b1 =w xor 2147483648, %b0  # flip the msb
%rs =s cast %b1
\end{verbatim}

\subsection{Call}
\label{sec:call}

\begin{code}
-- TODO: Code duplication with 'param'.
callArg :: Parser Q.FuncArg
callArg :: Parser FuncArg
callArg = (Value -> FuncArg
Q.ArgEnv (Value -> FuncArg)
-> ParsecT String () Identity Value -> Parser FuncArg
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"env") ParsecT String () Identity String
-> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Value
val))
    Parser FuncArg -> Parser FuncArg -> Parser FuncArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"..." ParsecT String () Identity String
-> Parser FuncArg -> Parser FuncArg
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> FuncArg -> Parser FuncArg
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure FuncArg
Q.ArgVar)
    Parser FuncArg -> Parser FuncArg -> Parser FuncArg
forall s u (m :: * -> *) a.
ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
<|> do
          Abity
ty <- ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall a. Parser a -> Parser a
ws1 ParsecT String () Identity Abity
abity
          Abity -> Value -> FuncArg
Q.ArgReg Abity
ty (Value -> FuncArg)
-> ParsecT String () Identity Value -> Parser FuncArg
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Value
val

callArgs :: Parser [Q.FuncArg]
callArgs :: Parser [FuncArg]
callArgs = Parser FuncArg -> Parser [FuncArg]
forall a. Parser a -> Parser [a]
parenLst Parser FuncArg
callArg

callInstr :: Parser Q.Statement
callInstr :: ParsecT String () Identity Statement
callInstr = do
  Maybe (LocalIdent, Abity)
retValue <- ParsecT String () Identity (LocalIdent, Abity)
-> ParsecT String () Identity (Maybe (LocalIdent, Abity))
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe (ParsecT String () Identity (LocalIdent, Abity)
 -> ParsecT String () Identity (Maybe (LocalIdent, Abity)))
-> ParsecT String () Identity (LocalIdent, Abity)
-> ParsecT String () Identity (Maybe (LocalIdent, Abity))
forall a b. (a -> b) -> a -> b
$ do
    LocalIdent
i <- Parser LocalIdent -> Parser LocalIdent
forall a. Parser a -> Parser a
ws Parser LocalIdent
local Parser LocalIdent
-> ParsecT String () Identity Char -> Parser LocalIdent
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'=')
    Abity
a <- ParsecT String () Identity Abity
-> ParsecT String () Identity Abity
forall a. Parser a -> Parser a
ws1 ParsecT String () Identity Abity
abity
    (LocalIdent, Abity)
-> ParsecT String () Identity (LocalIdent, Abity)
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (LocalIdent
i, Abity
a)
  Value
toCall <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"call") ParsecT String () Identity String
-> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val
  [FuncArg]
fnArgs <- Parser [FuncArg]
callArgs
  Statement -> ParsecT String () Identity Statement
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (Statement -> ParsecT String () Identity Statement)
-> Statement -> ParsecT String () Identity Statement
forall a b. (a -> b) -> a -> b
$ Maybe (LocalIdent, Abity) -> Value -> [FuncArg] -> Statement
Q.Call Maybe (LocalIdent, Abity)
retValue Value
toCall [FuncArg]
fnArgs
\end{code}

The call instruction is special in several ways. It is not a three-address
instruction and requires the type of all its arguments to be given. Also, the
return type can be either a base type or an aggregate type. These specifics are
required to compile calls with C compatibility (i.e., to respect the ABI).

When an aggregate type is used as argument type or return type, the value
respectively passed or returned needs to be a pointer to a memory location
holding the value. This is because aggregate types are not first-class
citizens of the IL.

Sub-word types are used for arguments and return values of width less than a
word. Details on these types are presented in the \nameref{sec:functions} section.
Arguments with sub-word types need not be sign or zero extended according to
their type. Calls with a sub-word return type define a temporary of base type
\texttt{w} with its most significant bits unspecified.

Unless the called function does not return a value, a return temporary must be
specified, even if it is never used afterwards.

An environment parameter can be passed as first argument using the \texttt{env}
keyword. The passed value must be a 64-bit integer. If the called function does
not expect an environment parameter, it will be safely discarded. See the
\nameref{sec:functions} section for more information about environment
parameters.

When the called function is variadic, there must be a \texttt{...} marker
separating the named and variadic arguments.

\subsection{Variadic}
\label{sec:variadic}

\begin{code}
vastartInstr :: Parser Q.VolatileInstr
vastartInstr :: ParsecT String () Identity VolatileInstr
vastartInstr = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"vastart")
  Value -> VolatileInstr
Q.VAStart (Value -> VolatileInstr)
-> ParsecT String () Identity Value
-> ParsecT String () Identity VolatileInstr
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> ParsecT String () Identity Value
-> ParsecT String () Identity Value
forall a. Parser a -> Parser a
ws ParsecT String () Identity Value
val
\end{code}

The \texttt{vastart} and \texttt{vaarg} instructions provide a portable way to
access the extra parameters of a variadic function.

\begin{enumerate}
  \item \texttt{vastart} -- \texttt{(m)}
  \item \texttt{vaarg} -- \texttt{T(mmmm)}
\end{enumerate}

The \texttt{vastart} instruction initializes a variable argument list used to
access the extra parameters of the enclosing variadic function. It is safe to
call it multiple times.

The \texttt{vaarg} instruction fetches the next argument from a variable
argument list. It is currently limited to fetching arguments that have a base
type. This instruction is essentially effectful: calling it twice in a row will
return two consecutive arguments from the argument list.

Both instructions take a pointer to a variable argument list as the sole argument.
The size and alignment of the variable argument lists depends on the target used.

\subsection{Phi}

\begin{code}
phiBranch :: Parser (Q.BlockIdent, Q.Value)
phiBranch :: Parser (BlockIdent, Value)
phiBranch = do
  BlockIdent
n <- Parser BlockIdent -> Parser BlockIdent
forall a. Parser a -> Parser a
ws1 Parser BlockIdent
label
  Value
v <- ParsecT String () Identity Value
val
  (BlockIdent, Value) -> Parser (BlockIdent, Value)
forall a. a -> ParsecT String () Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (BlockIdent
n, Value
v)

phiInstr :: Parser Q.Phi
phiInstr :: ParsecT String () Identity Phi
phiInstr = do
  -- TODO: code duplication with 'assign'
  LocalIdent
n <- Parser LocalIdent -> Parser LocalIdent
forall a. Parser a -> Parser a
ws Parser LocalIdent
local
  BaseType
t <- ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
'=') ParsecT String () Identity Char
-> Parser BaseType -> Parser BaseType
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser BaseType -> Parser BaseType
forall a. Parser a -> Parser a
ws1 Parser BaseType
baseType

  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"phi")
  -- TODO: combinator for sepBy
  Map BlockIdent Value
p <- [(BlockIdent, Value)] -> Map BlockIdent Value
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(BlockIdent, Value)] -> Map BlockIdent Value)
-> ParsecT String () Identity [(BlockIdent, Value)]
-> ParsecT String () Identity (Map BlockIdent Value)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Parser (BlockIdent, Value)
-> ParsecT String () Identity Char
-> ParsecT String () Identity [(BlockIdent, Value)]
forall s (m :: * -> *) t u a end.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m end -> ParsecT s u m [a]
sepBy1 (Parser (BlockIdent, Value) -> Parser (BlockIdent, Value)
forall a. Parser a -> Parser a
ws Parser (BlockIdent, Value)
phiBranch) (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (ParsecT String () Identity Char
 -> ParsecT String () Identity Char)
-> ParsecT String () Identity Char
-> ParsecT String () Identity Char
forall a b. (a -> b) -> a -> b
$ Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Phi -> ParsecT String () Identity Phi
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (Phi -> ParsecT String () Identity Phi)
-> Phi -> ParsecT String () Identity Phi
forall a b. (a -> b) -> a -> b
$ LocalIdent -> BaseType -> Map BlockIdent Value -> Phi
Q.Phi LocalIdent
n BaseType
t Map BlockIdent Value
p
\end{code}

First and foremost, phi instructions are NOT necessary when writing a frontend
to QBE. One solution to avoid having to deal with SSA form is to use stack
allocated variables for all source program variables and perform assignments
and lookups using \nameref{sec:memory} operations. This is what LLVM users
typically do.

Another solution is to simply emit code that is not in SSA form! Contrary to
LLVM, QBE is able to fixup programs not in SSA form without requiring the
boilerplate of loading and storing in memory. For example, the following
program will be correctly compiled by QBE.

\begin{verbatim}
@start
    %x =w copy 100
    %s =w copy 0
@loop
    %s =w add %s, %x
    %x =w sub %x, 1
    jnz %x, @loop, @end
@end
    ret %s
\end{verbatim}

Now, if you want to know what phi instructions are and how to use them in QBE,
you can read the following.

Phi instructions are specific to SSA form. In SSA form values can only be
assigned once, without phi instructions, this requirement is too strong to
represent many programs. For example consider the following C program.

\begin{verbatim}
int f(int x) {
    int y;
    if (x)
        y = 1;
    else
        y = 2;
    return y;
}
\end{verbatim}

The variable \texttt{y} is assigned twice, the solution to translate it in SSA
form is to insert a phi instruction.

\begin{verbatim}
@ifstmt
    jnz %x, @ift, @iff
@ift
    jmp @retstmt
@iff
    jmp @retstmt
@retstmt
    %y =w phi @ift 1, @iff 2
    ret %y
\end{verbatim}

Phi instructions return one of their arguments depending on where the control
came from. In the example, \texttt{\%y} is set to 1 if the
\texttt{\textbackslash{}ift} branch is taken, or it is set to 2 otherwise.

An important remark about phi instructions is that QBE assumes that if a
variable is defined by a phi it respects all the SSA invariants. So it is
critical to not use phi instructions unless you know exactly what you are
doing.

\subsection{Debug Information}

QBE supports the inclusion of debug information. Specifically, it allows
defining from which source file type, data, and function definitions originated.
For this purpose, it provides the \texttt{dbgfile} definition, which receives a
file name (string literal) as its sole argument. Every type, data and function
definition thereafter are assumed to originate in this file.

\begin{code}
-- TODO: not documnted in the QBE BNF.
fileDef :: Parser String
fileDef :: ParsecT String () Identity String
fileDef = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"dbgfile"
  ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
wsNL1 ParsecT String () Identity String
strLit
\end{code}

Further, instructions within a function can be associated with a specific line
and column number of a previously defined \texttt{dbgfile}. The
\texttt{dbgfile} is referenced by index using the first argument to
\texttt{dbgloc}. The second argument represents the line number, the third
(optional) argument the column number.

\begin{code}
-- TODO: not documnted in the QBE BNF.
dbglocInstr :: Parser Q.VolatileInstr
dbglocInstr :: ParsecT String () Identity VolatileInstr
dbglocInstr = do
  String
_ <- ParsecT String () Identity String
-> ParsecT String () Identity String
forall a. Parser a -> Parser a
ws1 (ParsecT String () Identity String
 -> ParsecT String () Identity String)
-> ParsecT String () Identity String
-> ParsecT String () Identity String
forall a b. (a -> b) -> a -> b
$ String -> ParsecT String () Identity String
forall s (m :: * -> *) u.
Stream s m Char =>
String -> ParsecT s u m String
string String
"dbgloc"
  Word64
file <- Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
ws Parser Word64
decNumber Parser Word64 -> ParsecT String () Identity Char -> Parser Word64
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity a
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f a
<* ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',')
  Word64
line <- Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
ws Parser Word64
decNumber
  Maybe Word64
col  <- Parser Word64 -> ParsecT String () Identity (Maybe Word64)
forall s (m :: * -> *) t u a.
Stream s m t =>
ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe (ParsecT String () Identity Char -> ParsecT String () Identity Char
forall a. Parser a -> Parser a
ws (Char -> ParsecT String () Identity Char
forall s (m :: * -> *) u.
Stream s m Char =>
Char -> ParsecT s u m Char
char Char
',') ParsecT String () Identity Char -> Parser Word64 -> Parser Word64
forall a b.
ParsecT String () Identity a
-> ParsecT String () Identity b -> ParsecT String () Identity b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> Parser Word64 -> Parser Word64
forall a. Parser a -> Parser a
ws Parser Word64
decNumber)
  VolatileInstr -> ParsecT String () Identity VolatileInstr
forall a. a -> ParsecT String () Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (VolatileInstr -> ParsecT String () Identity VolatileInstr)
-> VolatileInstr -> ParsecT String () Identity VolatileInstr
forall a b. (a -> b) -> a -> b
$ Word64 -> Word64 -> Maybe Word64 -> VolatileInstr
Q.DBGLoc Word64
file Word64
line Maybe Word64
col
\end{code}

\end{document}