%
% Mite's assembly language
%
% Reuben Thomas
%
% made HeVeA-friendly 2/6/06
%


\documentclass{article}
\usepackage{a4,array,mite}
\usepackage[normalem]{ulem}
\renewcommand{\isdefinedas}{=}


\title{Mite's assembly language}
\author{Reuben Thomas}
\date{25th October 2000}

\begin{document}
\maketitle

\section{Introduction}

Mite's assembly language is based on the abstract syntax. Where the two correspond exactly the semantics are the same; the semantics of departures from and extensions to the abstract syntax are given below.


\section{Metagrammar}

The grammar is described in a BNF-like notation. \define{Terminal tokens} are shown \conc{thus}, and \define{non-terminal tokens} \nont{thus}. Space or lack of it between tokens, including line breaks, is significant. \define{Terms} are formed from tokens and the following operators, given in decreasing order of precedence:

\begin{description}
\item [Zero~or~more~repetitions]of a term are denoted by appending an asterisk, thus: $A$\closure.
\item [One~or~more~repetitions]of a term are denoted by appending a plus sign, thus: $A$\pclosure.
\item [Lists]are denoted by a single terminal character before a repetition symbol: for example, \nont{ship}\conc{,}\pclosure\ denotes a comma-separated list of one or more ships.
\item [Concatenation]is denoted by textual concatenation, thus: $AB$.
\item [Alternation]is denoted by a vertical bar, thus: $A$\Alt$B$.
\item [Optional~terms]are enclosed in brackets: \conc{A} \conc{cat's}\opt{\conc{-tail} \opt{\conc{causes}}} \conc{wounds!}
\end{description}
Parentheses may be used to override precedence: for example, \lbrac\nont{A}\alt\nont{B}\rbrac\nont{C} means ``\nont{A} or \nont{B}, followed by \nont{C}''.

A \define{production} consists of the non-terminal being defined, followed by an equals sign, followed by the defining term: \nont{insect} = \nont{head}\nont{thorax}\nont{abdomen}.


\section{Identifier\label{asm:identifier}}

\begin{bnfc}[alphanumeric]
\item[d-digit]0\Alt 1\Alt 2\Alt 3\Alt 4\Alt 5\Alt 6\Alt 7\Alt 8\Alt 9
\item[h-digit]\nont{d-digit}\Alt A\Alt B\Alt C\Alt D\Alt E\Alt F
\item[letter]a\Alt\hspace{0pt}\kern-1ex\ldots\kern-1ex\hspace{0pt}\Alt z\Alt A\Alt\hspace{0pt}\kern-1ex\ldots\kern-1ex\hspace{0pt}\Alt Z
\item[alphanumeric]\nont{letter}\Alt\nont{d-digit}\Alt\conc{\_}\Alt\conc{.}
\item[identifier]\lbrac\nont{letter}\alt\conc{\_}\rbrac\nont{alphanumeric}\closure
\end{bnfc}

\noindent An identifier is a string of letters, numbers, underscores and full stops, starting with a letter or underscore.


\section{Number}

\begin{bnfc}
\item[natural]\nont{h-digit}\pclosure\opt{:\lbrac b\alt o\alt d\alt h\rbrac}
\item[integer]\opt{-}\nont{natural}
\item[size]\nont{natural}\opt{@\nont{natural}\opt{@\nont{natural}}}
\item[offset]\nont{integer}\opt{@\nont{integer}\opt{@\nont{integer}}}
\item[width]1\Alt 2\Alt 4\Alt a
\end{bnfc}

\noindent A natural number is a string of hex digits (see section~\ref{asm:identifier}) optionally followed by a colon and a base (\conc{b} for binary, \conc{o} for octal, \conc{d} for decimal and \conc{h} for hexadecimal); numbers may only contain digits allowed by the base. If there is no base the number is decimal. An integer is a natural with optional initial minus sign. Three-component numbers have the components separated by \conc{@}.

Widths are given in bytes; \conc{a} represents $A/8$.


\section{Item}

\begin{bnfc}
\item[item]\nont{natural}
\item[reg]\nont{item}
\end{bnfc}

\noindent A \nont{reg} is a register; $T$ is not directly accessible.


\section{Label\label{asm:label}}

\begin{bnfc}[]
\item[l-label].\nont{identifier}
\item[x-label]x\nont{l-label}
\item[label]\nont{l-label}\Alt\nont{x-label}
\item[label-exp]\nont{label}\opt{+\nont{size}}
\end{bnfc}

\noindent A local label (\nont{l-label}) is the address of a location (see section~\ref{asm:location}). An external label (\nont{x-label}) refers to a label in another module.

When a label is used as an address the semantics of the instruction are preceded by $T\leftarrow l$, and the label is replaced by $T$ in the instruction's signature.


\section{Manifest}

\begin{bnfc}
\item[constant]ashift
\item[manifest]\#\nont{offset}\Alt\nont{constant}\Alt\nont{label-exp}
\end{bnfc}

\noindent The value of the constant \conc{ashift} is $\log _{2}A/8$.


\section{Instruction}

\begin{bnfc}[instruction]
\item[instruction]\nont{assignment}\Alt\nont{dataproc}\Alt\nont{memory}\Alt\nont{branch}\Alt\nont{callret}\Alt\nont{throwcat}\Alt\nont{stack}\Alt\nont{escape}\Alt\nont{datum}
\end{bnfc}


\subsection{Assignment\label{asm:assignment}}

\begin{bnfc}[assignment]
\item[assignment]MOV \nont{reg},\lbrac\nont{reg}\alt\nont{manifest}\rbrac\Alt\\
DEF \nont{reg},\nont{manifest}\Alt\\
UNDEF \nont{reg}\Alt\\
SWAP \nont{reg},\nont{reg}
\end{bnfc}

\noindent The instruction \inst{\conc{MOV} $r$\conc{,}$m$}, where $m$ is a manifest, has the semantics

\begin{center}
$S_{r}\leftarrow m$
\end{center}
\noindent The instruction \inst{\conc{DEF} $r$\conc{,}$m$} has the same semantics as \inst{\conc{MOV} $r$\conc{,}$m$}, but the register is made constant. The instruction \inst{\conc{UNDEF} $r$} makes $r$ non-constant, as does \conc{MOV} when applied to a constant register. Constant registers may only be modified by \conc{DEF}, \conc{UNDEF}, or \conc{MOV}.


\subsection{Data processing}

\begin{bnfc}[dataproc]
\item[dataproc]\nont{2-op} \nont{reg},\nont{reg}\Alt\\
\nont{3-op} \opt{\nont{reg}},\nont{reg},\nont{reg}\Alt\\
\nont{4-op} \opt{\nont{reg}},\opt{\nont{reg}},\nont{reg},\nont{reg}
\item[3-op]\nont{arithmetic}\Alt\nont{logical}\Alt\nont{shift}
\item[2-op]NEG\Alt NOT
\end{bnfc}

\noindent When a destination is omitted, it is $T$. The only 3-operand instructions whose destination may be omitted are \conc{SUB}, \conc{AND} and \conc{XOR}. At most one destination may be omitted in a 4-operand instruction.


\subsubsection{Arithmetic}

\begin{bnfc}[arithmetic]
\item[arithmetic]ADD\Alt SUB\Alt MUL
\item[4-op]DIV\opt{S\opt{Z}}
\end{bnfc}

\noindent The instruction \inst{\conc{DIV\opt{S\opt{Z}}}~\conc{$q$,$r$,$x$,$y$}} has the semantics

\begin{center}
\noindent \abs{DIV\opt{S\opt{Z}}}$(q,x,y)$\\
\abs{REM\opt{S\opt{Z}}}$(r,x,y)$
\end{center}
\noindent $q$ and $r$ must be distinct.


\subsubsection{Logical}

\begin{bnfc}
\item[logical]AND\Alt OR\Alt XOR
\item[shift]SL\Alt SRL\Alt SRA
\end{bnfc}


\subsection{Memory}

\begin{bnfc}[memory]
\item[memory]LD\_\nont{width} \nont{reg},[\nont{reg}\opt{,\nont{reg}}]\Alt\\
ST\_\nont{width} \nont{reg},[\nont{reg}\opt{,\nont{reg}}]\Alt\\
COPY\_\nont{size} \nont{item},\nont{item}
\end{bnfc}

\noindent \inst{\conc{LD} or \conc{ST\_}$w$ \conc{$r_{1}$,[$r_{2}$,$r_{3}$]}} has the semantics

\begin{center}
$T\leftarrow S_{r_{2}}+S_{r_{3}}$

\abs{LD} or \abs{ST}$(w,r_{1},T)$
\end{center}

\subsection{Branch}

\begin{bnfc}[condition]
\item[condition]AL\Alt EQ\Alt NE\Alt MI\Alt PL\Alt CS\Alt CC\Alt VS\Alt VC\Alt HI\Alt LS\Alt LT\Alt GE\Alt LE\Alt GT
\item[address]\nont{reg}\Alt\nont{label}
\item[branch]B\nont{condition} \nont{address}
\end{bnfc}

\noindent A branch to the value of a register must be to an indirectable label (see section~\ref{asm:code}). The types of stack items active at both branch and destination must match (including the constancy of registers and values of constants).


\subsection{Call and return\label{asm:callret}}

\begin{bnfc}
\item[type-list]{[}\lbrac\nont{natural},\nont{size}\rbrac,\closure\opt{\nont{natural}}]
\item[reg-list]{[}\nont{reg},\closure]
\item[callret]CALL\opt{F\opt{V}} \nont{address},\nont{natural},\nont{type-list} \opt{\nont{sync}}\Alt\\
CALLFC\opt{V} \nont{address},\nont{natural},\nont{item} \opt{\nont{sync}}\Alt\\
RET\opt{F} \nont{item},\nont{reg-list}
\end{bnfc}

\noindent In the instruction \inst{\conc{CALL}~$a$\conc{,}$p$\conc{,[}$t_1$\conc{,}$\dots $\conc{,}$t_n$\conc{]}}, $a$ must be the value of a subroutine label (see section~\ref{asm:subfunc}). If the address is a register, it must hold the address of an indirectable subroutine (see section~\ref{asm:code}). $p$ is the number of parameters. The type list gives the format of the return values, from bottom-most to top-most on the stack. The list items give alternately a number of registers followed by the size of a chunk. All chunk sizes must be non-zero. Any registers returned are ranked in descending order from the top of the stack downwards, and the return values are ranked above registers already on the stack. \nont{sync} is described in section~\ref{asm:catchthrow}.

\conc{CALLF} has the same effect as \conc{CALL} except that the system calling convention is used, and the number of return values must be zero or one. The first argument goes on top of the stack. \conc{CALLFV} and \conc{CALLFCV} are used to call a variadic function (see section~\ref{asm:subfunc}); in this case the second operand is the total number of parameters being passed. \conc{CALLFC} and \conc{CALLFCV} are used when the function returns a chunk, and the third operand gives either a register holding the address to which the return value should be copied, or the chunk in which it should be stored.

In the instruction \inst{\conc{RET} $c$\conc{,[}$r_1$\conc{,}$\dots $\conc{,}$r_n$\conc{]}}, $c$ must be the chunk placed on the stack on entry to the subroutine or function. The register list gives the return values, which must be in ascending stack order, and match the types in the corresponding \conc{CALL} instruction. A \conc{RET} is assumed to return from the textually most recently declared subroutine or function. \conc{RET} must be used to return from subroutines, and \conc{RETF} from functions.


\subsection{Catch and throw\label{asm:catchthrow}}

\begin{bnfc}[throwcat]
\item[throwcat]CATCH \nont{reg},\nont{l-label}\Alt\\
THROW \nont{reg},\nont{reg},\nont{reg} \opt{\nont{sync}}
\item[sync]SYNC \nont{l-label}
\end{bnfc}

\noindent In the instruction \inst{\conc{CATCH} $s$\conc{,}$l$}, $l$ must be a handler's label (see section~\ref{asm:handler}) in the current subroutine. $s$ is set to the corresponding stack pointer. In \inst{\conc{THROW} $l$\conc{,}$s$\conc{,}$c$}, $l$ must be the value of a handler's label, and $s$ the address returned by \conc{CATCH} for that label. The \conc{CATCH} must have been executed in the current subroutine or function, or one of its callers.

A \conc{SYNC} is performed before the semantics of the instruction to which it is attached. In \inst{\conc{SYNC} $l$}, $l$ must be a handler's label in the current subroutine. When a handler is reached via a \conc{THROW} instruction, registers other than the top-most stack item have the same value as just before the last \conc{SYNC} performed for that handler's label in the instantiation of the subroutine or function which is thrown to, provided they have not been altered since.


\subsection{Stack\label{asm:stack}}

\begin{bnfc}
\item[stack]NEW\opt{\_\nont{size}}\Alt\\
KILL\Alt\\
RANK \nont{reg},\nont{natural}\Alt\\
REBIND
\end{bnfc}

\noindent The instruction \inst{\conc{NEW}} creates a register with undefined value. The instruction \inst{\conc{NEW\_}$s$} creates an $s$-byte chunk. \inst{\conc{KILL}} kills the top-most item on the stack. Items further down may not be killed.

Registers are ranked, the ranking giving the order in which they would ideally be assigned to physical registers. The rankings are distinct and contiguous, the highest being 1. The instruction \inst{\conc{RANK} \conc{$r$,$n$}} changes the rank of register $r$ to $n$. $n$ must be between $1$ and the number of registers. When a register is killed or ranked, the rankings of the other registers are adjusted accordingly. Newly created registers have rank $1$. \inst{\conc{REBIND}} causes the bindings of virtual to physical registers to be updated to reflect the current ranking.

Stack instructions are interpreted statically: the \conc{NEW} and \conc{KILL} for a register must textually enclose all other uses. Apart from \conc{NEW} and \conc{KILL} the only instruction that affects the state of the stack seen by the textually next directive (see section~\ref{asm:directive}) is \conc{CALL}, which kills the parameters and creates the return values.


\subsection{Escape}

\begin{bnfc}
\item[escape]ESC \#\nont{natural}
\end{bnfc}

\noindent \inst{\conc{ESC}} performs arbitrary actions.


\subsection{Datum\label{asm:datum}}

\begin{bnfc}
\item[datum]LIT\_\nont{width} \nont{manifest},\pclosure\Alt\\
SPACE\opt{Z}\_\nont{width} \nont{size}
\end{bnfc}

\noindent The instruction \inst{\conc{LIT\_}$w$~$v_{1}$\conc{,}$\dots $\conc{,}$v_{n}$} places the values $v_{1}$ to $v_{n}$ in contiguous locations, starting at the next $w$-aligned address after the preceding datum, if any. Label values may only be used when $w$ is \conc{a}.

The instruction \inst{\conc{SPACE\opt{Z}\_}$w$~$n$} reserves $n$ $w$-words, starting at the next $w$-aligned address after the preceding datum, if any. If the \conc{Z} modifier is used the space is zero-initialised.


\section{Location\label{asm:location}}

\begin{bnfc}[location]
\item[location]\nont{code}\Alt\nont{handler}\Alt\nont{subroutine}\Alt\nont{function}\Alt\nont{data}
\end{bnfc}

\noindent A location assigns the address of the next piece of code or data to the given label.

A datum (see section~\ref{asm:datum}) may only appear after a \nont{data}, and other instructions may only appear after a non-\nont{data} location. The flow of control must never fall through to a location other than a code or handler labelling.


\subsection{Labelling\label{asm:labelling}}

\begin{bnfc}
\item[labelling]\opt{p}\nont{l-label}
\end{bnfc}

\noindent If \conc{p} is used the label is public, and may be visible outside the module.


\subsection{Code\label{asm:code}}

\begin{bnfc}
\item[code]\opt{i}\nont{labelling}
\end{bnfc}

\noindent If \conc{i} is used the label may be used as the target of an indirect (register) branch.


\subsection{Handler\label{asm:handler}}

\begin{bnfc}
\item[handler]h\nont{labelling}
\end{bnfc}

\noindent A handler is the same as a labelling, except that it may also be given as the label for a \conc{CATCH} instruction (see section~\ref{asm:catchthrow}). The top-most stack item at a handler must be a non-constant register.


\subsection{Subroutine and function\label{asm:subfunc}}

\begin{bnfc}[subroutine]
\item[subroutine]s\opt{l}\nont{labelling}
\item[function]f\opt{l}\opt{c}\opt{v}\nont{labelling}
\end{bnfc}

\noindent The code in a subroutine or function extends from its labelling to the next subroutine or function labelling. The state of the stack directly before the subroutine or function specifies the number and type of its parameters (with the exception of a function's variadic parameters). Subroutines must be reached by \conc{CALL}, and functions by \conc{CALLF}.

If \conc{l} is used in a subroutine or function labelling, the subroutine or function is a leaf routine, and may not perform any \conc{CALL} instructions.

If \conc{c} is used in a function labelling, the function returns a chunk. If \conc{v} is used, the function is variadic, and the \conc{V} modifier must be added to \conc{CALLF}. On entry to a variadic function the variadic arguments are stored in chunk 1, which should be declared with size 0. Their layout is system-dependent. The non-variadic arguments should be declared as normal.

The return chunk, which is placed on top of the stack on entry to a function or subroutine, must not be written to.


\subsection{Data\label{asm:data}}

\begin{bnfc}
\item[data]d\opt{r}\nont{labelling}
\end{bnfc}

\noindent If \conc{r} is used the data up to the next data location are read-only; otherwise they are writable. The data in a program define the initial contents of the memory. A data labelling has the same alignment as the first datum following it (see section~\ref{asm:datum}).


\section{Directive\label{asm:directive}}

\begin{bnfc}
\item[directive]\nont{instruction}\Alt\nont{location}
\end{bnfc}


\section{Module}

\begin{bnfc}
\item[module]\nont{directive}\pclosure
\end{bnfc}


\section{Comments}

A comment, starting with a semicolon, may be placed at the end of any line or on a line by itself.

\end{document}
