
\chapter{Specifying Semantics of Machine Instructions}
\label{ch-ssl}

{\small
\begin{flushright}
Design: Shane and Cristina [97]; Documentation: Cristina and Shane [97], 
	Nathan [Jul 01]; Implementation: Shane [97], Doug [98], Nathan [Jun 01]
\end{flushright} 
}

A Semantic Specification Language, SSL, has been developed in
collaboration with Shane Sendall~\cite{Send97} in order to describe the
semantics of machine instructions.  
Shane's approach was based on an informal refinement of Object-Z~\cite{Duke97} 
specifications he wrote for the SPARC and 80286 architectures.
The original Object-Z specifications are available in his Honours 
thesis~\cite{Send97}; the SSL language has been modified since then and 
is described in this chapter.

The informal refinement from Object-Z specifications faced some
problems mainly to do with the bridging of the high-level specification
to a concrete form.  Further, the addressing modes were not
specified as such but the effective address was used (this address
being returned by NJMC's matching statement).  

The instructions that are the harder ones to describe are higher-order
instructions, which normally refer to the \emph{next} instruction 
in the sequence.  Examples of such instructions are SPARC's delayed
branches and 80286's string repeat instructions.  These will be 
described in more detail in Section~\ref{sec-hoInsts}.


\section{Design Decisions}
The SSL language was developed with integration into the SLED 
language~\cite{Rams97,Rams95} in mind.  However, due to 
time constraints, the language has been interfaced to the NJMC
toolkit's matching statement construct via a library.  This interface is 
called the \emph{RTL interface} and is described in Chapter~\ref{ch-ir},
Section~\ref{sec-rtl}. 

The following requirements were sought out of SSL:
\begin{itemize}
\item provide a simple and compact notation, 
\item model the semantics of machine instructions separately or per
	groups of instructions, 
\item model basic transfers of information via registers and memory
	locations, 
\item model complex and basic instructions without introduction of
	recursion or function calls, 
\item strictly model sizes of operands, registers and memory accesses, 
\item provide a universal model for flags and their interactions 
	via named registers and macro ``functions'', and
\item model broad environment structure and semantics to handle many 
	architectures and their idiosyncrasies; in other words expressibility,
\end{itemize}
Out of these requirements, the architecture environment is not 
yet fully supported, but will be discussed in Section~\ref{sec-archEnv}.


\section{Register Transfer Lists} 
Register transfer lists (RTL) is an intermediate language
that describes transfers of information between register-based 
instructions.  RTL assumes an infinite number of registers, hence
it is not constrained to a particular machine representation.
RTL has been used in the vpo optimiser~\cite{Beni88} for storing 
the target assembly instructions, and was a suitable representation 
for optimisation purposes.

More recently, RTL has been used as an intermediate representation in 
different system tools such as the link-time optimiser OM~\cite{Sriv93,Dec94},
GNU's compilers~\cite{Stal93}, and the editing library EEL~\cite{Laru95}. 
In all these tools, RTL stands for register transfer \emph{language}, 
and the representations vary widely.
The literature does not give much information on OM's RTL, but does
document the other two. 

GNU's RTL is a high-level language description of instructions,
in a lisp-like form.  A simple arithmetic operation between \texttt{x} and
\texttt{y} (with size field \texttt{m}) is described as follows:
\begin{verbatim}
    (plus:m x y)
\end{verbatim}
However, high-level instructions are also modelled in the language,
such as a multiexit conditional (\texttt{switch} in C or \texttt{case}
in Pascal):
\begin{verbatim}
     (cond [test1 value1 test2 value2 ...] default)
\end{verbatim}
These high-level instructions are hard to recover from binary
code and are also at a too high-level for analysis purposes.

EEL uses an RTL format internally to capture the semantics
of machine instructions.
EEL's spawn language extends EEL's RTL by adding a method to 
express instruction semantics by the way of a simple attribute
description.  Spawn's RTL defines the syntax of machine instructions
in the SLED style, and the semantics as attributes to each 
instruction by binding instructions to their semnatic attributes.
The following example describes the syntax in \texttt{pat} 
constructs, and the semantics in \texttt{sem} constructs.  
The syntax for load, store and other instructions are listed.
The semantics for load instructions is given as well.
{\small
\begin{verbatim}    
   pat [   ld      ldub    lduh    ldd     st      stb     sth     std    
           _       ldsb    ldsh    _       _       ldstub  _       swap    
           lda     lduba   lduha   ldda    sta     stba    stha    stda    
           _       ldsba   ldsha   _       _       ldstuba _       swapa  ]    
       is op3inst && op3=[0b000000..0b011111]    
  
   sem [   ldsb    ldsh    ldub    lduh    ld      ldf     lddf    
           ldsba   ldsha   lduba   lduha   lda                     ]    
       is (\r.\m.\sgn. r[rd]:=sgn m[addr])    
     @ [   R4w'    R4w'    R4w'    R4w'    R4w'    F4w'    F8w'    
           R4w'    R4w'    R4w'    R4w'    R4w'                    ]    
     $ [   M1r     M2r     M1r     M2r     M4r     M4r     M8r    
           M1r     M2r     M1r     M2r     M4r                     ]    
     $ [   #       #       Id32    Id32    Id32    Id32    Id64    
           #       #       Id32    Id32    Id32                    ]    
\end{verbatim}    
}
It can be seen from this example that this language models the
semantics of instructions in a simplistic way which only covers
general semantic content.  The language does not cover flag
effects or machine-dependent semantic attributes such as register
windows on SPARC.  

Given the suitability of RTL as an intermediate representation
for storing the semantics of instructions, we have developed
our own RTL that captures enough information of machine instructions
for the purposes of binary translation.  We are not interested
in a general RTL that would be suitable for emulation purposes,
so certain low-level details have been excluded from our
representation.  

SSL is the language we use to specify the semantics of machine
instructions in terms of RTLs.  We do not give a syntax description 
of our RTL here, but explain what the SSL language is able to 
specify and provide examples.  Chapter~\ref{ch-ir}, Section~\ref{sec-rtl}
gives a full description of our RTL language. 



\section{Semantic Specification Language Description} 
This section describes the syntax and semantics of the Semantic
Specification Language, SSL. The syntax of SSL is defined in
Extended-Backus-Naur-Form (EBNF), and semantics of SSL is described in
natural language integrated with examples from the 80286 and SPARC
architectures.  This was written in late 1997.  
 
Currently, SSL is limited in its ability to define the environment 
structure, and therefore such things like register windows cannot 
be modelled well. 
 
SSL allows for the description of the semantics of a \emph{list of
instructions} by means of \emph{statements} or register transfers
(or effects in Norman's documentation).  Most statements are
\emph{assignment} statements, but there is also support for
\emph{conditional} and \emph{flag} statements.  The register transfers 
for a group of instructions can be grouped via a \emph{table}. 
Individual assignment register transfers allow for a variety of
\emph{expression} (arithmetic, bitwise, logical and ternary). 
The base elements of an expression are \emph{values}, and the 
base elements of an instruction are \emph{variables}.  
We explain each of these in detail in the next sections.


\subsection{Registers}
A \emph{register} is a named memory space, which has a size and is 
mapped to a particular location or sets of locations. 
Some registers actually overlap with other registers, for example,
on x86, the 16-bit \texttt{ax} register overlaps with the lower part
of the 32-bit \texttt{eax} register.  On SPARC, 64-bit floating 
point registers are used by functions by overlapping two 32-bit 
registers.  We introduce the concepts of "shares" and "covers" to 
specify these two types of registers. 

Registers are defined within the pre-defined keyword \texttt{@REGISTERS}. 
Each register has the form \texttt{name[number]} which is the name 
of the register and its size in bits.  Registers can map to indexed 
locations in the register address space in different ways: 
\begin{itemize}
\item Numeric index: a numeric index basically gives the index into 
	the register space.  For example, \texttt{\%l0[32]->16} states that
	register name \texttt{\%l0} maps to position 16. 

\item Covers index: a \texttt{COVERS} index gives a numeric index into 
	the register address space and also states that the register
	being defined covers the address space of two or more registers (i.e.
	from the index of the first register to the index of the last 
	register mentioned). These registers need to be contiguous.  For example, 
	\texttt{\%f0to1[64]-> 64 COVERS \%f0..\%f1} gives register 
	\texttt{\%f0to1} the indexed location 64 and states that this 
	register overlaps the addressing space of registers \texttt{\%f0} 
	and \texttt{\%f1}.

\item Shares index: a \texttt{SHARES} index gives a numeric index into
	the register address space and also states that the register 
	being defined shares part of larger register (i.e. some bits 
	are shared).  For example,
	\texttt{\%ax[16] -> 0 SHARES \%eax@[0..15]} gives register 
	\texttt{\%ax} the index value of 0 and states that \texttt{\%ax} 
	is a 16-bit register composed of the bits 0 to 15 of register
	\texttt{\%eax}. 

\item -1 index: special registers such as \texttt{PC} are not given
	positive indexed into the register address space, instead, they 
	are listed as -1.
\end{itemize}

{\small
\begin{verbatim}
registers:  numberRegister
       |    coversRegister
       |    sharesRegister
       |    minusOneRegister
\end{verbatim}
}



\subsection{Variables and Values}
A \emph{variable} can be a register, memory, or parameter to an 
instruction operand.  
A \emph{value} is the contents of a variable (denoted with the
prefix prime symbol (')) or a numerical constant (integer or float).
A value can be signed extended by means of the \texttt{!} symbol.

For example, \texttt{r[5]} is register 5, and \texttt{'m[100000]!}
is a sign-extended value of the memory location 100000.

{\small
\begin{verbatim}
var_op:       REG_ID
       |      REG_MEM_IDX_ID  exp  ']'
       |      PARM

value_op:     '\'' var_op
       |      '\'' '(' var_op oper value_op ')'
       |      NAME
       |      FLOAT
       |      NUM
       |      PARM

REG_ID:       "%"[A-Za-z][A-Za-z0-9]*

REG_MEM_IDX_ID:  "r[" 
       |         "m["

ADDR:            "a["

PARM:         [a-z][a-z0-9_]*

NAME:         [A-Z][A-Z0-9_]*[A-Z0-9]

FLOAT:         (-)[0-9]+.[0-9]+             // Floats must have decimal pt

NUM:          (-)[0-9]+
       |       Ox[A-F0-9]+  
       |      (-)"2**"[0-9]+ 
\end{verbatim}
}


\subsection{Constants}
Constants are names assigned to numerical values that do not change.
Constants are commonly used to describe fixed values of a 
machine, for example, \texttt{WORD := 32}.

{\small
\begin{verbatim}
constants:    NAME ":=" NUM
\end{verbatim}
}

or

{\small
\begin{verbatim}
*80* %st := log2(2.7182818);
\end{verbatim}
}


\subsection{Functions}
\label{sec-funcs}
Several functions are provided to allow complex instructions to be described.
The main groups are conversion functions, floating point stack pseudo-functions,
and transcendental functions.

The conversion functions all take an expression and two integer sizes, and
are used to change the size of floating point numbers, or to change from
an integer of one size to a floating point value of another size, etc:

{\small
\begin{verbatim}
    fsize(exp, size1, size2)       // Convert from float size1 to float size2
    itof (exp, size1, size2)       // Convert from integer size1 to float size2
    ftoi (exp, size1, size2)       // Convert from float size1 to integer size2
    fround(exp,size1, size2)       // Convert from float size1 to float size2,
                                   // but integer value with rounding,
                                   // e.g. 3.75 -> 4.00
\end{verbatim}
}

To represent the effect of pushing or popping from a stack of registers, there
are two pseudo-functions:
{\small
\begin{verbatim}
    FPUSH                          // Signify a push to a stack of registers
    FPOP                           // Signify a pop from a stack of registers
\end{verbatim}
}

These are used for example when describing Intel floating point instructions
such as FLD. When the Register Transfer Lists are converted to independent
form, these pseudo-functions must be removed with a special pass. (This pass
also adjusts various register numbers, so that an equivalent representation
using a "flat" set of registers is obtained). Except just after decoding
instructions, FPUSH and FPOP will not be seen.

Various transcendental functions are included to describe complex floating
point instructions:

{\small
\begin{verbatim}
    sin(exp)                        // Sinusoid
    cos(exp)                        // Cosine
    tan(exp)                        // Tangent
    arctan(exp)                     // Inverse tangent
    log2(exp)                       // Logarithm to base 2
    loge(exp)                       // Natural logarithm
    log10(exp)                      // Logarithm to base 10
    sqrt(exp)                       // Square root
\end{verbatim}
}

All these functions take and return a floating point value.


\subsection{Expressions}
\label{sec-exps}
Three groups of expressions are supported: unary, binary and
ternary, each with an expressions as a member.   Expressions
are thought of as trees, with the leaves being the values of
the expression and the inner nodes being the operators of the
expressions.

Unary expressions include the negation (\texttt{NOT}) of an
expression, and the sign extension (\texttt{!}) of an expression.

Binary expressions include arithmetic, floating point arithmetic, bitwise and logical 
expressions, as well as bitwise expressions (\texttt{@}). 
The first three types of expressions are commonly found in 
most languages.  
The latter expression, bitwise-extraction, is needed to extract bits of 
a field, and hence the top and bottom bits need to be specified 
(separated by a \texttt{:} and stored as a binary expression).
This expression is derived from the SLED language.  
Examples of each of these types of expressions follow:
\begin{verbatim}
     'r[1] + 'r[5]     // arithmetic
     'r[31] +f 'r[32]  // floating point arithmetic
     'r[1] | 'm[1000]  // bitwise
     'r[5] or 'r[1]    // conditional
     'r[5] @ [0:19]    // bitwise-extraction
\end{verbatim}

The ternary expression \texttt{?:} consist of a logical expression, 
a true-branch expression, and a false-branch expression.  The 
semantics is as per the C language: if the logical expression 
evaluates to true, the true-branch expression is evaluated, otherwise
the false-branch expression.
For example, \texttt{'r[1] = 0 ? 0 : 1}.

Expressions can be cast to another size (in number of bits
required).  Casting can upgrade the size of the value of an
expression or downgrade it.  No sign extension happens either way;
when casting to a larger size, the new bits are padded with zeroes,
and when casting to a smaller size, the value is chopped at the 
number of bits specified.   
Casting is denoted by postfixing the size in \texttt{\{\}} brackets.
For example, \texttt{'r[rs1]\{64\}} casts the value of register
\texttt{rs1} to 64 bits.

Changing the size of floating point values is different, because it's not
just a matter of discarding or padding bits. These conversion operators
are described above in the Functions section (Section~\ref{sec-funcs}).

Expressions can be sign-extended by appending a ``!'', and the address of
an expression can be taken by using \texttt{a[{\it exp}]}. When taking the
address of an expression, it should be an expression that represents memory,
i.e. it should begin with \texttt{m[}. Later, when parameters have been instantiated,
the \texttt{a[m[exp]]} sequences can be relaced with just \texttt{exp}.

Finally, there are expressions in the context of tables, which
will be explained once the concept of table is introduced in
Section~\ref{sec-tab-and-exps}.

The complete EBNF for expressions follows.  The list of
expression operators and their meaning is defined in 
Figure~\ref{fig-expOps}.
{\small
\begin{verbatim}
exp:          exp ARITH_OP exp                  // arithmetic 
       |      exp FARITH_OP exp                 // floating point arithmetic 
       |      exp BIT_OP exp                    // bitwise   
       |      exp COND_OP exp                   // logical
       |      CONV_FUNC '(' exp ',' NUM ',' NUM ')' // conversion function
       |      TRANSCEND '(' exp ')'             // transcendental function
       |      FPUSH | FPOP                      // stack pseudo-function
       |      NOT exp                           // negation
       |      CONV exp                          // conversion         
       |      exp S_E                           // sign-extension
       |      ADDR '(' exp ')'                  // address-of
       |      COND_TNAME '[' IDX ']'            // table expression
       |      exp OP_TNAME '[' IDX ']' exp      // table operand   
       |      ternary                           // ternary      
       |      value_op                          // value         
       |      value_op cast                     // casted value
       |      value_op AT '[' NUM COLON NUM ']' // bitwise-extraction
       |      '(' exp ')'                       // parenthesis   
       |      '(' exp ')' cast                  // expression cast  

ternary:      '[' exp COND_OP exp '?' exp ':' exp ']'
       |      '[' exp COND_OP exp '?' exp ':' exp ']' cast
 
cast:         '{' NUM '}'
\end{verbatim}
}


\centerfigbegin
\begin{tabular}{|l|l|l|} \hline
Group		& Symbol			& Meaning \\ \hline
ARITH\_OP	& \texttt{+}		& addition \\
			& \texttt{-}		& subtraction \\
			& \texttt{*}		& multiplication \\
			& \texttt{/}		& division \\
			& \verb!%!			& modulus \\ \hline
FARITH\_OP	& \texttt{+f}		& addition of 32 bit floats \\
			& \texttt{+fd}		& addition of 64 bit floats  \\
			& \texttt{+fq}		& addition of 128 bit floats \\
			& \texttt{-f}		& subtraction of 32 bit floats\\
			& \texttt{-fd}		& subtraction of 64 bit floats\\
			& \texttt{-fq}		& subtraction of 128 bit floats\\
			& \texttt{*f}		& multiplication of 32 bit floats\\
			& \texttt{*fd}		& multiplication of 64 bit floats\\
			& \texttt{*fq}		& multiplication of 128 bit floats\\
			& \texttt{/f}		& division of 32 bit floats\\
			& \texttt{/fd}		& division of 64 bit floats\\
			& \texttt{/fq}		& division of 128 bit floats\\ \hline
BIT\_OP		& \verb!&!  		& (bitwise) and \\
			& \verb!&~!  		& (bitwise) and-not \\
			& \verb!|!			& (bitwise) or \\
			& \verb!|~!			& (bitwise) or-not \\
			& \verb!^! 			& xor \\
			& \verb!^~! 		& xor-not \\
			& \verb!>>!   		& right-shift \\
			& \verb!<<!   		& left-shift \\ 
			& \verb!>>A!		& right-shift-arithmetic \\
			& \texttt{rl}		& rotate-left \\
			& \texttt{rr}		& rotate-right \\
			& \texttt{rlc}		& rotate-left-through-carry \\
			& \texttt{rrc}		& rotate-right-through-carry \\ \hline
COND\_OP	& \texttt{=}		& equal \\
			& \verb!~=! & not equal \\
			& \texttt{<}	    & less than \\
			& \texttt{>}	    & greater than \\
			& \texttt{<=}	   	& less or equal to \\
			& \texttt{>=}		& greater or equal to \\
			& \texttt{and}		& and (of two expressions) \\
			& \texttt{or}		& or \\ \hline
\end{tabular}
\centerfigend{fig-expOps}{Expression Operators in the SSL Language}


\subsection{Statements}
\label{sec-stmts}
Statements describe transfers of information to/from registers.
All transfers have to be specified; there are no side-effects 
on transfers other than those described by a statement.
Most transfers will be assignments, however, there is also need
for conditional (if-then) statements and support for condition
codes as we do not want to fully specify these transfers, but
merely know if a change in a condition code could happen or not.

An \emph{assignment statement} consists of the size of the assignment
(in bits), the variable of the target of the assignment, and 
an expression describing the value of the assignment.
For example, \texttt{*32* r[rd] := 'imm22 << 10}, assigns 32 bits of 
the contents of parameter \texttt{imm22} left-shifted 10 bits to 
register \texttt{rd}.

A \emph{conditional statement} consists of a membership logical expression,
followed by a list of statements.  If the logical expression is
true, the list of statements is valid.  
Membership is denoted by the operator \texttt{|=}.  
A membership logical expression tests if an value is a member of
a set of numbers (or ranges of numbers).  
For example, \texttt{'r[rd] |= {2,3}} tests if the value of register
\texttt{rd} is either 2 or 3.

The \emph{empty statement} is denoted by \texttt{\_}.  This statement
is useful when describing the semantics of the \texttt{NOP} 
instruction.


\subsubsection*{Support for Condition Codes}
Condition codes are treated as named registers of size 1 bit. 
These can be defined in the environment section of the specification,
which is described in Section~\ref{sec-archEnv}.
Although only 0 or 1 can be assigned to a condition code, assignment 
statements to condition codes can be quite complex if fully described.
For example, the SPARC V8 manual describes the overflow of an 
add instruction which sets the condition codes as:
\begin{verbatim}
V <- (r[rs1]<31> and operand2<31> and (not result<31>)) or
      ((not r[rs1]<31>) and not operand2<31> and result<31>);
\end{verbatim}
Although this expression could be specified in SSL, we do not 
want to know how the condition code was set other than it may
be set---this removes overhead during translation time as an 
overflow condition code will have a similar meaning in all 
architectures.  (Note though that we need to define the meaning
somewhere and if different in another architecture, the effect
will need to be specified; at present we don't worry too much
about this).  

Since we are interested in knowing if the value of a condition code 
\emph{may} have been changed, we provide the following two macros:
\begin{itemize}
\item updateflags: specifies the named condition codes that may
	be changed by the instruction.  \\
	For example, the 80286 multiply instruction modifies all 6
	condition codes; this is specified as:
	\verb!defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)!.

	{\it
	This macro should be changed to a more general one:
	for a set list of condition codes, the arguments
	to this macro specify the new value for the condition codes:
	0, 1, or - (if hard to compute). \\
	For example, the SPARC add instruction will be specified as: 
	\texttt{updateflags(-,'r[rd],-,-)} for the negative, zero, 
	overflow and carry flags.  
	In contrast, the logical and instruction will be specified as:
	\texttt{updateflags(-,'r[rd],0,0)}. 
	}

\item undefineflags: this macro specifies that the value of all current 
	named condition codes is undefined or unknown.  Few 
	machine instructions produce this effect, for example the
	80286 divide instruction:
	\texttt{undefineflags()}. 
\end{itemize}
 
The EBNF for statements follows.  Notice that the membership
expression of the if\_then (conditional) statement is restricted
at present to use the name \texttt{idx} instead of any other
name.  This restriction can be lifted in the future.
{\small
\begin{verbatim}
stmt:         assign_stmt
       |      if_then
       |      FLAGMACRO '(' flag_list ')'
       |      no_statement

assign_stmt:  ASSIGNSIZE var_op ASSIGN exp
 
if_then:      '(' IDX MEM_OF '{' list_for_if '}' ')' THEN '(' ifstmt_list ')'
 
list_for_if:  list_for_if ',' range
       |      range
 
range:        NUM TO NUM
       |      NUM
 
ifstmt_list:  ifstmt_list stmt
       |      stmt

FLAGMACRO:    "updateflags"
       |      "undefflags"

flag_list:    flag_list ',' REG_ID
       |      REG_ID

no_statement: '_'
\end{verbatim}
}

\subsection{Operands}
\label{sec-operands}
Explicit operand definitions are a late, and still evolving, addition
to the SSL language. Essentially what the operand section does is allow
the specification of complex, variant operands in such a way that the
SLED and SSL files can be linked directly without the need of the intermediate
code that was previously needed to handle these cases.

The EBNF follows:
{\small
\begin{verbatim}
operands: 'OPERANDS' operand { ',' operand }

operand: param ':=' '{' list_parameter '}'
       | param list_parameter ASSIGNSIZE exp
       | param list_parameter '[' list_parameter ']' ASSIGNSIZE exp

list_parameter: [ param { ',' param } ]
\end{verbatim}
}

As seen above, there are three basic forms, although the second two are really
variants of the same form. The first specifies a list of operand variants, such
as commonly occurs with effective addresses in most common processor 
architectures. In other words, it states that the given param will be one of the
alternatives given. (For automatic use with the SLED file, the names on the
right hand side must appear in the SLED file as constructors) As an example from
SPARC, we have

{\small
\begin{verbatim}
OPERAND eaddr := { absoluteA, dispA, indirectA, indexA };
\end{verbatim} }

The second form specifies semantics for a single, specific operand, and normally
gives details for a variant previously mentioned in the above mentioned variant
list. The expression given is substituted into an instruction in place of the
simple value that would otherwise be used. Again from SPARC:

{\small
\begin{verbatim}
OPERAND
    dispA      rs1, simm13      *32* r[rs1] + sgnex(13,32,simm13),
    absoluteA  simm13           *32* sgnex(13,32,simm13),
    indexA     rs1, rs2         *32* r[rs1] + r[rs2],
    indirectA  rs1              *32* r[rs1],
\end{verbatim} }

Finally, the third form is also known as the functional, or lambda form, 
although in actuallity it is not quite a true first-class lambda. It
acts identically to the previous form, except that it takes a second set of
function arguments, enclosed in the square brackets. This allows an operand
to effectively pass in a small snippet of code, with the variables to be decided
later by the instruction (hence the lambda-ness) By way of illustration:

{\small
\begin{verbatim}
OPERAND
    example := { ex1, ex2 },
    ex1 a [r]   *32* r[r] + a,
    ex2 a [r]   *32* r[r] * a

EXINST example rs1 rd
    r[rd] := example(rs1);
\end{verbatim} }

For the sake of sanity, if a functional operand occurs in a variant operand,
all variants must have the same number of functional arguments (although they
may differ in other respects). 

\subsection{Tables}
\label{sec-tables}
Tables are used for grouping names of instructions alone or pairs of
instructions and operators or expressions.  These are useful when
describing the semantics of a group of instructions that behave
in a similar way; the group can be declared in a table and given
a name (the name of the table), which is then used in the 
specification, as described in the next section (Section~\ref{sec-insts}).

Tables of instructions are handy when grouping instructions that
come from the same family, such as the store instructions.
On SPARC, there are store double-word, word, half-word, and byte 
instructions, both in alternate or non-alternate storage, for a total of 
8 instructions.  The semantics of the store family of instructions is
the same, the only difference is in the size of the operand.  Hence
these instructions can be grouped in the \texttt{STORE} table:
\begin{verbatim}
STORE := { STD, STDA, ST, STA, STH, STHA, STB, STBA }
\end{verbatim}

Instructions that perform an arithmetic or bitwise operation can be
grouped in a table which pairs the instruction name with its operator.
In the following example, we have grouped the add, subtract, add and 
set condition codes, and subtract and set condition codes, in the
\texttt{ARITH, OP3} table.  The name \texttt{ARITH} is used to 
identify the instruction names, and the \texttt{OP3} name is used to
identify the operator name.  The table is viewed as a 2-dimensional
array for usage purposes:
\begin{verbatim}
[ARITH, OP3] := { (ADD_, "+"), (SUB_, "-"), (ADDCC_, "+"), (SUBCC_, "-") }
\end{verbatim}

Finally, the third type of table pairs instructions and expressions.
This is useful when grouping conditional instructions for example,
as the condition of the instruction is dependent on a condition code
or a set of condition codes; i.e. they are based on an expression of
condition codes.  
In the following example, the table \texttt{JUMPS,COND} is created. 
The \texttt{JUMPS} name indexes instruction names, and the \texttt{COND} 
name indexes expressions associated to the instructions:
\begin{verbatim}
[JUMPS,COND] := { (BA_, 1), (BN_,0), (BNE_, ~'%Z), (BE_, '%Z),
                  (BG_, ~('%Z |('%N ^ '%V))), (BLE_, '%Z |('%N ^ '%V)),
                  (BGE_, ~('%N ^ '%V)), (BL_, '%N ^ '%V),
                  (BGU_, ~('%C | '%Z)), (BLEU_, '%C | '%Z), (BCC_, ~'%C),
                  (BCS_, '%C), (BPOS_, ~'%N), (BNEG_, '%N), (BVC_, ~'%V),
                  (BVS_, '%V) }
\end{verbatim}

The EBNF for tables follows:
{\small
\begin{verbatim}
tables:       NAME ASSIGN '{' name_list '}'
                          // table declaration with single names
       |      '[' NAME ',' OP_TNAME ']' ASSIGN '{' name_op_list '}'
                          // table declaration with names and their operations
       |      '[' NAME ',' COND_TNAME ']' ASSIGN '{' name_exp_list '}'
                          // table declaration with names and their expressions

name_list:    name_list ',' INSTR_NAME
       |      INSTR_NAME

name_op_list: name_op_list ',' '(' INSTR_NAME ',' '"' oper '"' ')'
       |      '(' INSTR_NAME ',' '"' oper '"' ')'

name_exp_list: name_exp_list ',' '(' INSTR_NAME ',' exp ')'
       |       '(' INSTR_NAME ',' exp ')'

oper:         BIT_OP
       |      ARITH_OP
\end{verbatim}
}


\subsubsection{Tables and Expressions}
\label{sec-tab-and-exps}
In Section~\ref{sec-exps} we mentioned that there were two types
of expressions that dealt with tables: the table expression and 
the table operand.  The former allows users to index the second element
of tables that pair instructions and expressions, by indexing on the 
expression (i.e. the condition in the previous example).  The latter 
allows users to index the second element of tables that pair instructions
and operators, by indexing on their operator (i.e. the \texttt{OP3} 
field in the second to last example above). 
We replicate the relevant part of the expression EBNF for convenience: 
{\small
\begin{verbatim}
exp:   ...
       |      COND_TNAME '[' IDX ']'             // table expression
       |      exp OP_TNAME '[' IDX ']' exp       // table operand
       ...
\end{verbatim}
}

The expressions that relate to tables can be used as part of 
assignment statements which facilitate the description of the
semantics of an instruction.  For example, our earlier addition 
expression \texttt{'r[1] + 'r[5]} would be more general if taken
in context of the arguments parsed for an addition instruction:
a register \texttt{rs1}, a register or an immediate \texttt{reg\_or\_imm},
and the destination register \texttt{rd}, and specified as an 
assignment statement: 
\begin{verbatim}
*32* r[rd] := 'r[rs1] + 'reg_or_imm
\end{verbatim}
When being part of the \texttt{ARITH,OP3} table, the whole set of 
instructions can be specified as follows:
\begin{verbatim}
*32* r[rd] := 'r[rs1] OP3[idx] 'reg_or_imm
\end{verbatim}
where \texttt{idx} is an indexed variable into the table (based
on the instruction parsed), it would be 1 if the \texttt{ADD} 
instruction were parsed.

In a similar way, we can index in the \texttt{JUMPS,COND} table 
to determine the condition of a branch instruction.  In this case,
if the condition is true, the named register \texttt{\%nPC} is set
to a displacement from the current PC, otherwise it is set to the
next physical instruction.  Note that this is a simplification of
the complete semantics for illustration purposes only.
\begin{verbatim}
*32* %nPC := ((COND[idx] = 1) ? '%PC + (4 * disp22) : '%PC + 4)
\end{verbatim}


\subsection{Instructions}
\label{sec-insts}
An SSL instruction is the way we describe the semantics for one
particular machine/assembly instruction.  An instruction takes
the name of the assembly instruction or a table name as its left-hand-side 
(LHS) and a list of statements (as per Section~\ref{sec-stmts}) on
its right-hand-side (RHS).
The RHS and LHS are separated by indentation for readability 
purposes.

The assembly \texttt{ORcc} instruction takes three arguments on SPARC; 
a register and another register or an immediate value, and the 
destination register.  The input arguments are bitwise-or'd and 
the result is placed on the destination register.  The 4 condition 
codes are updated also, by setting the negation flag to the most
significant bit of the result, the zero bit based on whether the
result was 0 or not, and the overflow and carry bits to 0. 
This instruction can be specified as follows:
\begin{verbatim}
ORCC rs1, reg_or_imm, rd            *32* r[rd] := 'r[rs1] or 'reg_or_imm
                                    defineflags (%N, %Z, %V, %C)
\end{verbatim}

The following example illustrates how to specify the semantics for
a group of arithmetic and bitwise instructions that have been 
grouped in the \texttt{INSTR\_TABLE} table.  The LHS specifies the
name of the instruction (i.e. one of the ones in the table) and 
the number and names of the parameters.  The RHS specifies the 
semantic operation to be performed based on the index of the 
instruction in the table. 
{\small
\begin{verbatim}  
[INSTR_TABLE, OP1] := { (ADD_,"+"), (AND_,"&"), (OR_,"|"), (SUB_,"-"), (XOR_,"^") } 
INSTR_TABLE[idx] parameter1          *8* r[1] := 'r[1] OP1[idx] 'parameter1  
\end{verbatim}  
}

The EBNF for instructions follows.  The decorated
name argument refers to mainly x86 names that have been decorated in
SLED for ease of distinction of similar instruction; for example, 
attaching \texttt{mrb} at the end of a \texttt{ADD} instruction or a 
table of arithmetic and logical assembly instruction names 
\verb!ARITLOG[idx]^"mrb"!.
{\small
\begin{verbatim}
instr:        lhs_def stmt_list
 
lhs_def:      INSTR_NAME list_parm                 // single instruction LHS
       |      NAME '[' IDX ']' list_parm           // table instruction LHS
       |      NAME '[' IDX ']' DECOR list_parm     // table inst. with decorated name
       |      INSTR_NAME DECOR list_parm           // single instruction with decorated name
 
list_parm:    list_parm ',' PARM
       |      PARM
\end{verbatim}
}


\subsection{Parts of a Specification}
A complete SSL specification consists of up to four different
parts: definitions of constants, definitions of registers, definitions
of flag functions, definitions of operands, definitions of tables, and a 
list of SSL instructions.
The EBNF for the parts of a specification follows:
{\small
\begin{verbatim}
specification: specification parts
        |      parts

parts:         constants
        |      registers
        |      flag_fnc
        |      operands
        |      tables
        |      instr
\end{verbatim}
}



\section{Modelling Computer Architecture Features -- The Architecture 
	Environment}
\label{sec-archEnv}
The architecture environment is the first part of an SSL 
specification file and defines names and constants that are
needed in order to describe hardware-related issues that 
deal with machine instructions.  For example, the register 
window pointer (\texttt{CWP}) on SPARC.
This environment is not fully supported at present and 
hence it's mainly commented out in the specifications 
provided below.

The following architectural issues are defined for SPARC; constant
names that start with a \texttt{\#} are not supported at present.
{\small
\begin{verbatim}
NWINDOWS    := 3            # Number of windows (register windows)- implementation dependent
MAX_BYTE    := 2**8         # a byte of all 1's
MAX32BIT    := 2**32        # a word of all i's
MAXSIGN32   := 2**31        # all bits except sign bit are set
SIGN_32_NEG := -2**31
WORD        := 32           # size of word in bits
 
#ENDIANNESS := BIG
 
#REGISTER %N, %Z, %V, %C, %psr, %wim, %tbr, %Y, %asr[1..31], w[0..((NWINDOWS-1)*16)]
 
#CWP := {0..(NWINDOWS-1)}    # current window ptr
 
#INVARIANT ::= r[{0..31}] := w[({0..31} + 16*CWP) mod NWINDOWS*16]
 
#[ %g0, %g1, %g2, %g3, %g4, %g5, %g6, %g7,
#  %o0, %o1, %o2, %o3, %o4, %o5, %o6, %o7,
#  %l0, %l1, %l2, %l3, %l4, %l5, %l6, %l7,
#  %i0, %i1, %i2, %i3, %i4, %i5, %i6, %i7 ] is r[0..31]   # register window wrapping
#[ %sp, %fp ] is [ %o6 %i6 ]
\end{verbatim}
}

The first 7 lines declare constant names; only the numeric ones are
supported at present. 
The \texttt{REGISTER} directdive declares named registers.
Both \texttt{CWP} and \texttt{INVARIANT} declare aspects of 
register windows; the index into the window and the current window
invariant.
The last two tables bind names to registers.

For the 80286, the following architectural issues are defined:
{\small
\begin{verbatim}
# Constants defined in hexadecimal (modelling the manual)
MAX8BITS  =  0xFF
MAX16BITS =  0xFFFF
MAX8NEG   =  0xFFFFFFFF80   # (-128)
MAX16NEG  =  0xFFFFFF8000   # (-32,768)
SIGN16    =  0x8000

# General registers, flags, and Global variable defined as registers
#REGISTER %AX, %BX, %CX, %DX, %SP, %BP, %FP, %SI, %DI, %AL, %CL, %DL, %BL, %AH, %CH, %DH, %BH,
#         %ES, %CS, %SS, %DS, %PC, %OF, %DF, %IF, %TF, %SF, %ZF, %AF, %PF, %CF, %Rpt, %Skip

#%AL := %AX@(0:7)
#%AH := %AX@(8:15)
#%BL := %BX@(0:7)
#%BH := %BX@(8:15)
#%CL := %CX@(0:7)
#%CH := %CX@(8:15)
#%DL := %DX@(0:7)
#%DH := %DX@(8:15)

#ENDIANNESS = LITTLE
\end{verbatim}
}

As per SPARC, these define constants for maximum signed and 
unsigned constants, and binds names to registers.

At present, in each spec, there is also reference to what
effective address means, but this will be removed as 
the decoder of machine instructions should decode the effective
address and pass the relevant argument to the semantic spec,
hence we do not need to expand all cases in the spec and we
just use the name \texttt{eaddr} instead. 

The binding of names to registers is already part of SLED as
it is needed in order to specify the syntax of machine instructions.
These bindings are not really required if the spec is to be
used in that context.
The constant definitions are useful and are macro-expanded 
when an instruction is instanciated, hence they do not 
create an overhead.
The constants dealing with register windows need to be better
specified and possibly removed from the specification. 
We are considering different options at present---watch this
space. 

It is also desirable to provide the user with a means of
specifying their own macros or overriding the ones provided
by the SSL description.  Again, this has not been implemented
at present.


\subsection{Fetch-Execute Cycle}
Underlying any semantic specification is the fetch-execute
cycle that the processor follows when executing machine
instructions.  The standard cycle is the following:
\begin{enumerate}
\item Fetch the instruction from memory at the location
	pointed to by the PC (program counter) register,
\item Increment PC by the size of the instruction fetched,
\item Decode the fetched instruction, and
\item Execute the instruction.
\end{enumerate}
The cycle is repeated until the running process terminates.

Architectures such as SPARC have slightly modified the 
fetch-execute cycle by introducing another register to keep
track of targets of delayed instructions.  In their case,
the PC points to the next instruction to be executed, and
the nPC points to the next PC value; i.e. the instruction
after the next one.  Once an instruction is fetched, the 
PC takes the value of the nPC, and the nPC is incremented
by the size of the instruction fetched.   

The fetch-execute cycle of the processor is given explicitly
as a special instruction FETCHEXEC, which gives a list of RTs
to be executed on each cycle. The special function execute(n)
is defined only within the context of FETCHEXEC, to mean the
execution of an instruction at address n, which returns the
address of the following instruction. If no FETCHEXEC block
is given, the following default applies:

{\small
\begin{verbatim}
FETCHEXEC   *1*  %CTI := 0
            *32* r[tmp] := execute( %pc )
            *32* %pc := [%CTI = 0 ? r[tmp] : %pc ];
\end{verbatim} }

\%CTI is a pseudo-register which should be set to 1 by any
instruction that causes a control transfer (if and only if the
transfer actually takes place). This serves the dual purpose of
marking such control transfer instructions for later analysis, as
well as permitting its uses here.

It should be noted that the current implementation does not use
the contents of FETCHEXEC for static translation - while it may
theoretically be possible to use the information contained within
to eg eliminate branch delay slots, the analysis required for doing
so is currently beyond the scope of this project. At present only
the emulator uses this section.

\section{Modelling the Semantics of 80286 and SPARC Instruction Sets}
SSL has been used to model the semantics of machine instructions
for a CISC (80286) and a RISC (SPARC) machine.  In this section
we show extracts of the complete specifications for these machines;
the complete specs are available in the \uqbt\ source distribution.

The arithmetic and logical instruction table is shown in 
Figure~\ref{fig-286rtl} as an example of an 80286 group of
instructions specified in SSL.
\texttt{(ARITHLOG,OP1)} is a table containing pairs of arithmetic and 
logical instruction, and their operators.  
Due to the large number of addressing modes in x86, each 
instruction in this group takes 9 different forms depending on
the arguments to the instruction, and these forms are differenciated
by decorating the name of the table in each case.
Each instruction consists of an assignment, which is either of
8 or 16 bits in size, and assigns the result of the expression onto
the destination register (which in several instances is an implicit
register as described in the architecture manual).  The second
statement for each instruction is a \texttt{defineflags} macro
statement which describes transfers of information to condition
codes.

\centerfigbegin
\begin{footnotesize} 
\begin{verbatim}  
[ARITLOG,OP1] := { (ADD_, "+"), (AND_, "&"), (OR_, "|"), (SUB_, "-"), (XOR_, "^") }

ARITLOG[idx]^"iAL"  i8          *8* %AL := '%AL OP1[idx] i8
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"iAX"  i16         *16* %AX := '%AX OP1[idx] i16
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"mrb" eaddr, reg8  *8* eaddr := 'eaddr OP1[idx] 'reg8
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"mrw" eaddr, reg   *16* eaddr := 'eaddr OP1[idx] 'reg
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"rmb" reg8, eaddr  *8* reg8 := 'reg8 OP1[idx] 'eaddr
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"rmw" reg, eaddr   *16* reg := 'reg OP1[idx] 'eaddr
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"wb" eaddr, i8     *8* eaddr := 'eaddr OP1[idx] i8
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"b"  eaddr, i8     *8* eaddr := 'eaddr OP1[idx] i8
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
ARITLOG[idx]^"w"  eaddr, i16    *16* eaddr := 'eaddr OP1[idx] i16
                                defineflags(%SF,%ZF,%AF,%PF,%CF,%OF)
\end{verbatim}  
\end{footnotesize} 
\centerfigend{fig-286rtl}{SSL definition of the arithmetic and logical 
instruction from the 80286 architecture}  

The use of tables for instructions, operators, and expressions greatly
decrease the size of the specification, at a small expense on 
readability of the specification.
The use of flag macros enhances the specification by increasing its 
readability, and abstracting from the nitty-gritty details of flag 
transfers.


The SPARC load double word instructions are shown in Figure~\ref{fig-srtl}. 
The load double word instruction takes two parameters:  an effective
address (i.e. a register or an immediate) and a destination register.
The instruction assigns a 64-bit value into a pair of registers; the
first 32-bits go into an even register and the last 32-bits go into
an odd register.  The 64-bit value comes from memory, indexed
by a register or an immediate (i.e. eaddr).
 
\begin{figure}[h] 
\begin{footnotesize} 
\begin{verbatim}  
ODDMASK := 1 
EVENMASK := 30 
 
# Load double instruction-  the 1st reg. of double load must be even 
# the 2nd reg. of double load must be the next reg. after 1st, hence odd.  
LDD_  eaddr, rd                            *32* r['rd & EVENMASK] := 'm['eaddr] 
                                           *32* r['rd | ODDMASK] := 'm['eaddr + 4] 
\end{verbatim} 
\end{footnotesize} 
\caption{\label{fig-srtl} SSL definition of the load double word instructions from the SPARC architecture}  
\end{figure}  


An example of tables and membership expressions is shown in
Figure \ref{fig:ld}.
The table \texttt{(LOG,OP1)} contains logical assembly instructions
and their operators.  The first 6 instruction assign a value to 
a register.  The last 6 instruction do that and also affect the 
condition codes. 
When specifying the semantics of the instructions in this table,
the extra functionality attached to the last 6 instructions can
be specified by means of a membership expression (\texttt{|=}): if 
the assembly instruction index in the table is between 6 and 11 (recall 
that tables are indexed from 0), the instruction affects the condition 
codes as per specified.
The \texttt{|=} operator acts as a condition and the $=>$ acts as an
if-then statement. 

\centerfigbegin
\begin{footnotesize} 
\begin{verbatim} 
# logical table 
[LOG,OP1] := { (AND,"&"), (ANDN,"&~"), (OR,"|"), (ORN,"|~"), (XOR,"^"), (XNOR,"^~"), 
               (ANDCC,"&"), (ANDNCC,"&~"), (ORCC,"|"), (ORNCC,"|~"), (XORCC,"^"), (XNORCC,"^~"), 
 
LOG[idx]  rs1, reg_or_imm, rd             *32* r[rd] := 'r[rs1] OP1[idx] 'reg_or_imm 
                                          (idx |= {6..11}) => 
                                              defineflags(%N, %Z, %V, %C)
\end{verbatim} 
\end{footnotesize} 
\centerfigend{fig:ld}{SSL Specification for Rotates in the 80286} 


\subsection{Modelling Higher Order Instructions}
\label{sec-hoInsts}
The semantic description of most assembly instructions is straight 
forward as most instructions are self-contained; that is, they
refer to only arguments that come within the instruction itself.
However, there are a few instructions which related to other
instructions, typically the \emph{next} instruction in the
instruction stream.  These instructions are refere to as 
higher order instructions and deserve further explanation as 
to their semantic specification.

The higher order instructions available in the SPARC architecture
are all the delayed transfers of control (branches, calls and 
returns).  The ones available in the 80286 architecture are the
repeat string instructions. 
We are also aware the the Pentium has prefix instructions 
that may also be considered higher order, however, we are not
sure if this should be included as part of the decoder of
machine instructions or not---the prefixes commonly override 
a 16-bit register in the next instruction for a 32-bit register
name. 


\subsubsection*{Delayed Instructions}
On SPARC, delayed instructions take the form of a pair of 
instructions; the first one is a control transfer instruction 
and the second one (commonly referred to as the delay slot instruction)
can be any type of instruction (although normally it is not another
control transfer instruction).
These instructions are used whenever transfering control to another 
memory location in the program, as the next instruction in the stream 
can actually be executed prior to the transfer of control by the first 
instruction.  This is possible due to the architecture's pipeline.

The architecture manual~\cite{Spar92} models this instruction with
the help of a special hardware register available in SPARC; the
nPC register (for next program counter); and a variation on
the standard fetch-execute cycle: register PC points to the next
instruction to be executed, nPC points to the next instruction 
after PC has been executed, and the value of PC is always updated
with the value of nPC at the end of each iteration, and nPC is
updated by 4 bytes (i.e. one word).
For non-delayed instructions, nPC points 4 bytes ahead of PC 
(i.e. PC+4).  

Branch instructions have a further constraint---the delay 
slot instruction can be annulled or not depending on the
value of the 'a' field in the instruction.  
A machine-dependent specification of the branches on SPARC
would be as follows (as per current sparc.ssl spec):
{\small
\begin{verbatim}
# Jump table
[JUMPS,COND] := { (BA_, 1), (BN_,0), (BNE_, ~'%Z), (BE_, '%Z),
                  (BG_, ~('%Z |('%N ^ '%V))), (BLE_, '%Z |('%N ^ '%V)),
                  (BGE_, ~('%N ^ '%V)), (BL_, '%N ^ '%V),
                  (BGU_, ~('%C | '%Z)), (BLEU_, '%C | '%Z), (BCC_, ~'%C),
                  (BCS_, '%C), (BPOS_, ~'%N), (BNEG_, '%N), (BVC_, ~'%V),
                  (BVS_, '%V) }

JUMPS[idx]  disp22, a          *32* %nPC := ((COND[idx] = 1) ? '%PC + (4 * disp22) : 
                                             ((a = 1) ? '%PC + 4 : '%nPC))
                               *32* %PC := ((COND[idx] = 0 and ('a = 1)) ? '%PC + 4 : '%PC)
\end{verbatim}
}

{\it
However, although the previous specification is correct, it is not
useful for binary translation purposes as the target machine may
not have a special nPC register or the modified fetch-execute cycle
which sets the PC register to nPC.  Even if nPC is modelled with
any particular register, one would need to force the PC to be equal
to nPC at the end of each cycle; on x86 this can be done by 
pushing the value of nPC and returning (i.e. pops the value on
the top of the stack onto PC and transfers control there)---this
is nasty code we shouldn't need to use.

We ended up developing a transformational analysis to remove the 
nPC from source RTL instructions, this is explained in 
Chapter~\ref{ch-delay}. 
}


\subsubsection*{Repeat String Instructions}
On x86, the repeat instructions allow the next instruction in
the stream to be repeated the number of times specified in
the \texttt{cx} register based on an implicit condition in
the repeat instruction itself.  The next instruction in the stream
must be a string instruction (i.e. one of \texttt{cmps}, 
\texttt{lods}, \texttt{movs}, \texttt{scas}, or \texttt{stos}, 
in either byte or word mode).

The \texttt{REP, REPNE} and \texttt{REPNZ} instructions 
execute the next instruction in the stream while the value of
the \texttt{cx} register is not zero; each iteration decreases
the value of the register by one.
This instruction could have been modelled with a loop construct
in the language, however, we felt that SSL should not include
loops as this will most likely be misused by writers of 
semantic specifications.  Hence it was modelled with the
equivalent of two global flags: \texttt{Skip} and \texttt{Rpt} 
(for skip and repeat). 
The \texttt{Rpt} flag is set to 1 while the value of \texttt{cx} 
is greater than 0, and it is reset to 0 when the register 
becomes 0.  This flag is used by the string instructions to
update the value of the \texttt{PC} register prior to termination
of the instruction, namely, by ``going back'' one instruction
(to the repeat instruction) if the value of the flag was on.
The \texttt{Skip} flag is then needed to ``skip over'' the 
string instruction in the last iteration (as the loop is not
to be performed any more).
The relevant extract from SSL follows:  
{\small
\begin{verbatim}
# REPT table for repeat instructions with condition 'cx > 0'
REPT := { REP_, REPNE_, REPNZ_ }

# REP uses Skip and Rpt registers to enable iteration
REPT[idx]                       *1* %Skip := [('%CX = 0) ? 1 : '%Skip]
                                *1* %Rpt := [('%CX = 0) ? 0 : 1]
                                *16* %CX := [('%CX > 0) ? '%CX - 1 : '%CX]

# STRS table for string instructions 
STRS = { CMPS_, LODS_, MOVS_, SCAS_, STOS_ }
STRS[idx].b                     ...  // other stuff here 
                                *16* %PC := '%PC + ['%Rpt ? -1 : 0]
\end{verbatim}  
} 

{\it
As with the SPARC example, this does specify the semantics of
the repeat string instructions but at a great overhead -- we 
wouldn't want to model them on a different architecture as 
we would have to force the PC to change (and on SPARC that is
harder to do than on x86), but we would also have to dedicate
two registers for the special flags.  
The design of this instruction was based on the Object-Z 
specification as it was thought nicer than enumerating all 
possible pairs of repeat-string instruction and specifying 
each one (too ``brute force'' one would say). 
}



\section{SSL Simplifications}
Some changes were made to the language in late November/early
December to allow for the full implementation of a tool that
parses this language and stores the information in a suitable
form. 
We document here such issues, maybe they will be supported in
the future, maybe not:
\begin{itemize}
\item The size field of an assignment statement: the size field,
	denoted by * surrounding the number of bits of the 
	assignment, used to be specified by allowing also variables
	to hold this value (rather than fixed constants).  This
	simplified the specification of the store instructions for
	example.  The previous spec used to read:
{\small \begin{verbatim}
# STORE table
STORE = { ST, STA, STH, STHA, STB, STBA }

STORE[idx] Eaddr, rd                         *32* size := (idx > 1 ? (idx > 3 ?
8 : 16) : 32)
                                             *size* m['Eaddr] := 'r[rd]
\end{verbatim}
}
	Whereas the new one uses fixed sizes and therefore requires three
	tables instead of one:
{\small \begin{verbatim} 
STORE := { ST_, STA_}
STORE[idx] Eaddr, rd                         *32* m['Eaddr] := 'r[rd]

STORE := { STH_, STHA_ }
STORE[idx] Eaddr, rd                         *16* m['Eaddr] := 'r[rd]

STORE := { STB_, STBA_ }
STORE[idx] Eaddr, rd                         *8* m['Eaddr] := 'r[rd]
\end{verbatim}
}

\item Only numerical constants are allowed at present; extending it to 
alpahnumerical constants would help when trying to define characteristics
of architectures, such as little and big endianness; e.g.
{\small \begin{verbatim}
ENDIANNESS := BIG
\end{verbatim}
}

\end{itemize}



\section{Implementation -- Semantic Representation Decoder}
\label{sec-srd}
SRD, a Semantic Representation Decoder, is a tool that parses
SSL files and stores them in a file in a template form, 
ready for instanciation by an RTL interface (see Section~\ref{sec-rtl},
Chapter~\ref{ch-ir} for our RTL interface).

SRD makes use of lex and yacc to parse an SSL file and store
it in memory; this memory representation is then stored in
a template file.  

SRD at this stage takes a SSL specification of an architectures and parses
it (assuming that it is a valid specification) into an expression tree
structure. This structure is then ``expanded'' (not really, because it is
done in-situ) to cover all table en tries and the if statements are
resolved it is then put into an ascii file that is in a simplified form
(but still readable?). At the moment this ascii file (the second, ie. not
the specification) is parsed to get it into memory using yacc. 

\begin{itemize}
\item Constants cannot be expressions ie. they must be number values.

\item No constants are allowed in casts eg. r[rs1]{16} not r[rs1]{SIZE16}

\item if statements can only be used to select table offsets and cannot
contain an expression that depends on ``real'' variables. 

\item Instruction names must be uppercase and suffixed with an underscore
(eg. ADD\_); tables names must be uppercase and cannot be suffixed with an
under score (ADDTABLE). The lexer does not differenciate between a table
and a constant and therefore the c onstants are of the same form as a
table. 

\item The bit-extraction operator is a binary operation that has a LHS of
a value expression and a RHS that is itself a binary expression that has a
LHS value (lower bound) an operator colon (eg. :) and a RHS value (upper
bound). 

\item sign extension is classed as a unary operator.

\item all the rotates from 80286 (rrc rlc rr rl) have been included as
native operators. 

\item 80286 ENTER instruction is not complete due to the problem of
macro-expanding a while loop. 

\item In fact, no macro expansion is implemented

\item Flag procedures referred to as flag macro (do not macro expand)
define the flags that are effected or in the case of ``undefineflags''
show the flags that are set to 0. 

\item Particular naming conventions are required to differientiate between
instruction that have different addressing modes but have the same
parameter inputs. An example of this can be seen in 80286 CALL instruction
with the far and near segment options; they have the same parameters (and
the same instruction name of course) but they are different. They can be
differientiated in the specification because of the decoration suffixed.
However, the decoration is not included into the later structure where th
e matching takes place.  
\end{itemize}


\underline{First Expression tree structure}
The first expression tree is used to store the raw parsed ssl
specification (raw because it does no expansion and substituting). This
file also contains directives to for the next phase which manipulates this
structure. The next phase uses the original st ructures; where it
instantiates table requirements, substitutes constants and collapses if
statements. This phase stores the structure to a ascii representation. 


\underline{Second Expression tree structure}
The ascii file produced from above is then parsed and stored in memory by
the second expression tree structure. This structure is then used as the
template file that can be used as a guide to instantiate real
instructions.  Currently the parser has a minor problem, but the structure
and outline are there.

Note: More specific implementation details can be found in the
implementation files. 

