\ifhtml\section*{Contents} \tableofcontents \fi \section{MIPS instruction-set specification} This section is a complete specification of the MIPS instruction set. The MIPS is a good machine to start with because it has a small, regular instruction set. Its specification requires only the toolkit's basic features, and the regularity of the instruction set lends itself to factoring, making the specification small. As in the MIPS manual~\cite{kane:mips}, the specification is divided into two parts: one describing the instructions of the main CPU, the other describing those of the floating-point coprocessor. \subsubsection*{Tokens and fields} The MIPS is a RISC machine; all instructions occupy exactly one 32-bit token. Although the instructions of the floating-point coprocessor are listed separately in the manual, they use some of the same fields as the instructions of the main CPU. This property makes it possible to define all the fields in a single token class. We use {\tt noweb} to distribute the field specifications, putting most in the CPU section and the rest in the coprocessor section. [[fields]] specifications give only the positions of fields. [[fieldinfo]] specifications give more information; for example, we use special names to refer to the values of fields that denote registers. [[fieldinfo]] specifications are never required. The core MIPS specification describes the fields first, then patterns and constructors. We tell {\tt noweb} to put it in a file called {\tt mips-core.spec}. <>= fields of instruction (32) <> <<[[fieldinfo]] specifications>> <> @ \subsection{The MIPS CPU} A field is specified by giving a range of bit positions. Some of the MIPS fields are listed on page~A-3 of the MIPS architecture manual; others, like [[breakcode]], apply to only a couple of instructions. The MIPS manual sometimes uses more than one name for the same field, for example, [[offset]] and [[base]] are used instead of [[immed]] and [[rs]] to describe load and store instructions. The numbers in the specification are the starting and ending bit positions, where 0 is the least and 31 the most significant bit. <>= word 0:31 op 26:31 rs 21:25 rt 16:20 immed 0:15 offset 0:15 base 21:25 target 0:25 rd 11:15 shamt 6:10 funct 0:5 cond 16:20 breakcode 6:25 @ Special names are associated with the integer registers. These names can be used in constructor applications, as shown in the definitions of synthetic instructions in Section~\ref{sec:synth}. These names can also be used to generate symbolic disassemblers, and ``encoding'' procedures that emit assembly language. On the MIPS, we use names of the form $\hbox{\tt r}n$, except for the stack pointer ([[sp]]). <>= names [ r0 r1 r2 r3 r4 r5 r6 r7 r8 r9 r10 r11 r12 r13 r14 r15 r16 r17 r18 r19 r20 r21 r22 r23 r24 r25 r26 r27 r28 sp r30 r31 ] @ These names are just one of the properties that could be associated with the integer registers, which are [[rs]], [[rd]], [[rt]], and [[base]]. <<[[fieldinfo]] specifications>>= fieldinfo [ rs rt rd base ] is [ <> ] @ \subsubsection{Opcodes} An opcode is a pattern that constrains the values of one or more fields. Defining opcodes individually would be tedious, and the result would be hard to compare with the architecture manual, which uses opcode tables. The [[patterns]] declaration binds a table of names when a {\em generating expression} appears on the right-hand side, letting us write declarations that resemble the tables in the MIPS manual. The numeric codes for the MIPS opcodes are described in three tables on page~A-87 of the MIPS architecture manual. These tables are reproduced in Figure~\ref{figure:mips-tables}. Normal opcodes are six bits, and they appear in the [[op]] field of the instruction. This statement names patterns for each of the opcodes in the table at the top of Figure~\ref{figure:mips-tables}. <>= patterns [ special bcond j jal beq bne blez bgtz addi addiu slti sltiu andi ori xori lui cop0 cop1 cop2 cop3 _ _ _ _ _ _ _ _ _ _ _ _ lb lh lwl lw lbu lhu lwr _ sb sh swl sw _ _ swr _ lwc0 lwc1 lwc2 lwc3 _ _ _ _ swc0 swc1 swc2 swc3 _ _ _ _ ] is op = {0 to 63} @ This statement creates names for patterns constraining the [[op]] field. The expression ``[[op = {0 to 63}]]'' generates a list of 64~patterns, ranging from ``[[op = 0]]'' to ``[[op = 63]]''. Each pattern is associated with the corresponding name in the list to the left-hand side of [[is]]. For example, an instruction matches the pattern [[beq]] if its [[op]] field is~4. Patterns associated with the name ``[[_]]'' are discarded. \begin{figure} {\tabskip=0pt\offinterlineskip\footnotesize \newbox\strutbox \def\strut{\vrule height 8pt depth 3pt width0pt} \def\line{&\multispan{17}\hrulefill} \noindent\halign{&\hbox to 5em{\hss{#}\hss}&\strut\vrule #\cr &\omit&28..26&\multispan{12}\hfil\normalsize\bf Opcode\hfil&\omit&\omit&\omit\cr \strut 31..29& \omit&\scriptsize0&\omit&\scriptsize1&\omit&\scriptsize2&\omit&\scriptsize3& \omit&\scriptsize4&\omit&\scriptsize5&\omit&\scriptsize6&\omit&\scriptsize7&\omit\cr \line\cr \scriptsize0&&SPECIAL&&BCOND&&J&&JAL&&BEQ&&BNE&&BLEZ&&BGTZ&\cr \line\cr \scriptsize1&&ADDI&&ADDIU&&SLTI&&SLTIU&&ANDI&&ORI&&XORI&&LUI&\cr \line\cr \scriptsize2&&COP0&&COP1&&COP2&&COP3&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize3&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize4&&LB&&LH&&LWL&&LW&&LBU&&LHU&&LWR&&\dag&\cr \line\cr \scriptsize5&&SB&&SH&&SWL&&SW&&\dag&&\dag&&SWR&&\dag&\cr \line\cr \scriptsize6&&LWC0&&LWC1&&LWC2&&LWC3&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize7&&SWC0&&SWC1&&SWC2&&SWC3&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \noalign{\bigskip} &\omit&2..0&\multispan{12}\hfil\normalsize\bf SPECIAL\hfil&\omit&\omit&\omit\cr \strut 5..3& \omit&\scriptsize0&\omit&\scriptsize1&\omit&\scriptsize2&\omit&\scriptsize3& \omit&\scriptsize4&\omit&\scriptsize5&\omit&\scriptsize6&\omit&\scriptsize7&\omit\cr \line\cr \scriptsize0&&SLL&&\dag&&SRL&&SRA&&SLLV&&\dag&&SRLV&&SRAV&\cr \line\cr \scriptsize1&&JR&&JALR&&\dag&&\dag&&SYSCALL&&BREAK&&\dag&&\dag&\cr \line\cr \scriptsize2&&MFHI&&MTHI&&MFLO&&MTLO&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize3&&MULT&&MULTU&&DIV&&DIVU&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize4&&ADD&&ADDU&&SUB&&SUBU&&AND&&OR&&XOR&&NOR&\cr \line\cr \scriptsize5&&\dag&&\dag&&SLT&&SLTU&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize6&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \scriptsize7&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&&\dag&\cr \line\cr \noalign{\bigskip} &\omit&18..16&\multispan{12}\hfil\normalsize\bf BCOND\hfil&\omit&\omit&\omit\cr \strut 20..19& \omit&\scriptsize0&\omit&\scriptsize1&\omit&\scriptsize2&\omit&\scriptsize3& \omit&\scriptsize4&\omit&\scriptsize5&\omit&\scriptsize6&\omit&\scriptsize7&\omit\cr \line\cr \scriptsize0&&BLTZ&&BGEZ&&\multispan{11}\hfil&&\cr \line\cr \scriptsize1&&&&&&\multispan{11}\hfil&&\cr \line\cr \scriptsize2&&BLTZAL&&BGEZAL&&\multispan{11}\hfil&&\cr \line\cr \scriptsize3&&\multispan{3}&&\multispan{11}\hfil&&\cr \line\cr \noalign{\bigskip{\leftskip=3em\advance\hsize by 0.8in \noindent\llap{\dag\ }% Operation codes marked with a dagger cause reserved instruction exceptions and are reserved\strut\hfil\break\strut for future versions of the architecture.\par}} }} \caption{Opcode tables from MIPS architecture manual.} \label{figure:mips-tables} \end{figure} @ %\fillup{1.8in} Two opcodes, [[special]] and [[bcond]], are used for several instructions. These instructions are decoded by checking the bit-pattern in the [[funct]] and [[cond]] fields of the instructions, respectively. The following statement names patterns for each of the [[special]] opcodes in the table in the center of Figure~\ref{figure:mips-tables}: <>= patterns [ sll _ srl sra sllv _ srlv srav jr jalr _ _ syscall break _ _ mfhi mthi mflo mtlo _ _ _ _ mult multu div divu _ _ _ _ add addu sub subu and or xor nor _ _ slt sltu _ _ _ _ ] is special & funct = {0 to 47} @ The [[bcond]] table at the bottom of Figure~\ref{figure:mips-tables} is sparse. Instead of writing a table with many empty entries, we use another form of generating expression on the right-hand side; the list of integers in square brackets generates each integer in turn. <>= patterns [ bltz bgez bltzal bgezal ] is bcond & cond = [ 0 1 16 17 ] @ These statements create new patterns by adding further constraints to the existing patterns [[special]] and [[bcond]]. A slightly different way to look at this style of specification is that ``[[special]]'' and ``[[bcond]]'' are the names of tables, not opcodes. As we'll see, that view is a better one for the SPARC. @ \subsubsection{Grouping instructions} The rest of the patterns organize instructions into groups, much as is done in Chapter~3 of the MIPS manual. Most instructions are grouped by assembly-language syntax. Immediate-mode instructions are grouped into signed and unsigned variants ([[immedS]] and [[immedU]]), depending on whether the immediate operand is sign-extended. The toolkit uses disjunction to define patterns that match any of a group of related instructions. <>= patterns load is lb | lbu | lh | lhu | lw | lwl | lwr | sb | sh | sw | swl | swr immedS is addi | addiu | slti | sltiu immedU is andi | ori | xori arith3 is add | addu | sub | subu | slt | sltu | and | or | xor | nor shift is sll | srl | sra vshift is sllv | srlv | srav arith2 is mult | multu | div | divu mfhilo is mfhi | mflo mthilo is mthi | mtlo jump is j | jal jumpr is jr | jalr branch1 is blez | bgtz | bltz | bgez | bltzal | bgezal branch2 is beq | bne copls is lwc0 | lwc1 | lwc2 | lwc3 | swc0 | swc1 | swc2 | swc3 @ \subsubsection{Constructors for simple instructions} The patterns that group instructions can now be used to define constructors. A constructor specification contains an opcode, operands, possibly a set of equations, and an output pattern. The operands correspond to the procedure's arguments, and when the procedure is called, it emits the sequence of tokens defined by the output pattern. The toolkit generates an encoding procedure for each constructor. When the constructor name on the left-hand side is the name of a pattern, each disjunct of the pattern is used to generate a constructor. For example, the first declaration below generates a constructor for each disjunct bound to the pattern [[load]], i.e., [[lb]], [[lbu]], [[lh]], etc. Most output patterns for the MIPS constructors are conjunctions of the opcode and all the operands. For example, the load instructions could be described by \begin{quote} [[load rt, offset!(base) is load & rt & offset & base]]. \end{quote} Because this idiom is so common, not only on the MIPS but on other machines as well, the toolkit provides a special abbreviation for it: if the output pattern is omitted, the conjunction is inferred. We can use this trick to specify almost all of the integer instructions; only the one- and two-operand branches ([[branch1]] and [[branch2]]) and the jumps need to be treated specially. Given the groupings we defined above, we specify 56~instructions in just 15~lines:% \footnote{This is the one place in specifications where newlines can be significant, preventing the opcode of a following pattern be taken as an operand of the current pattern. The reference manual explains the lexical details.} <>= constructors load rt, offset!(base) immedS rt, rs, offset! immedU rt, rs, offset lui rt, offset arith3 rd, rs, rt shift rd, rt, shamt vshift rd, rt, rs arith2 rs, rt mfhilo rd mthilo rs syscall break breakcode copls ft, offset!(base) jr rs jalr rd, rs @ Operands with a trailing [[!]] (e.g., [[offset!]]) are treated as signed parameters in encoding procedures; the toolkit implicitly narrows their values to produce unsigned fields. @ These constructor specifications include the assembly-language syntax associated with the instructions being specified. For example, most operands are separated by commas, but the syntax [[offset(base)]] is used to suggest the address computation in the load and store instructions. Using assembly syntax in the constructor specification makes the specification look more like the architecture manual. We use the assembly syntax to produce symbolic disassemblers and ``encoding'' procedures that emit assembly language. @ \subsubsection{Branches and relocatable addresses} Because it's a RISC machine, the MIPS can't use target addresses directly as field values in branch instructions; a 32-bit address wouldn't leave room for an opcode, or anything else. Instead, the branches are relative to the program counter; the field corresponding to the target address records the difference between that address and the PC. We use equations to specify the relationships between the operands and fields. <>= <> relocatable reloc constructors branch1 rs, reloc { reloc = L + 4 * offset! } is branch1 & rs & offset; L: epsilon branch2 rs, rt, reloc { reloc = L + 4 * offset! } is branch2 & rs & rt & offset; L: epsilon @ The branch equations capture the semantics of the MIPS branch instructions; the offset is sign-extended, shifted left 2 bits, and added to the address of the delay slot, i.e., [[L]]. @ Constructor operands designated [[relocatable]] are {\em relocatable addresses}, like the branch targets named [[reloc]] above. Pattern labels, like [[L]] above, are also relocatable addresses. When a constructor that uses relocatable addresses is applied, it checks to see if those addresses are known (i.e., they have been assigned absolute adresses). If so, it treats them as ordinary integers and emits the instruction. Otherwise, it emits {\em placeholder} tokens and creates a relocation closure. The placeholders will be overwritten later, when the address becomes known and the application applies the closure. @ We have to specify a placeholder pattern for tokens of each class. On the MIPS, we have only one class, so we need one placeholder. We've picked a [[break]] instruction with code~99, so that we'll get a trap if by some mischance the placeholder sneaks into a real program and we try to execute it. <>= placeholder for instruction is break(99) @ The syntax ``[[break(99)]]'' isn't a special thing we use for placeholders; it's just the pattern we get by applying the [[break]] constructor to the value 99. @ The PC-relative branches can't jump anywhere in the MIPS address space, only within $2^{16}$ words of the PC. The MIPS provides a [[jump]] instruction that lets a program jump to any word in the same quarter of the address space as the PC. It's best specified using a lot of bit operations; the toolkit provides a notation for taking {\em bit slices} of values. For example, [[reloc@[28:31]]] denotes the four most significant bits of the 32-bit, relocatable address [[reloc]]. The description of [[j]] on page~A-31 in the MIPS manual corresponds to the equations below. <>= constructors jump reloc { reloc@[28:31] = L@[28:31], reloc@[2:27] = target, reloc@[0:1] = 0 } is L: jump & target @ The high bits of the target address must match the current address, the middle bits give the [[target]] field, and the low bits must be zero. @ \subsubsection{Synthetic instructions and conditional assembly} \label{sec:synth} We have completed our description of the MIPS integer instructions, but MIPS applications often use ``synthetic'' instructions, i.e., instructions that are in the assembly language but not in the hardware instruction set. We specify constructors for synthetic instructions by defining them in terms of existing constructors. We put synthetic instructions in a separate specification, because not all applications need synthetics. <>= constructors nop is sll (r0, r0, 0) mov rd, rs is addu(rd, rs, r0) b reloc is beq (r0, r0, reloc) @ The earlier [[fieldinfo]] specification permits us to use names, not numbers, to refer to register values. @ There is a large collection of synthetic branch instructions; they combine comparisons and branches. The result of comparisons is left in register~1, which MIPS conventions reserve for the assembler. <>= constructors bge rs, rt, reloc is slt (r1, rs, rt); beq(r1, r0, reloc) bgeu rs, rt, reloc is sltu(r1, rs, rt); beq(r1, r0, reloc) blt rs, rt, reloc is slt (r1, rs, rt); bne(r1, r0, reloc) bltu rs, rt, reloc is sltu(r1, rs, rt); bne(r1, r0, reloc) bleu rs, rt, reloc is sltu(r1, rt, rs); beq(r1, r0, reloc) ble rs, rt, reloc is slt (r1, rt, rs); beq(r1, r0, reloc) bgt rs, rt, reloc is slt (r1, rt, rs); bne(r1, r0, reloc) bgtu rs, rt, reloc is sltu(r1, rt, rs); bne(r1, r0, reloc) @ A full multiplication requires fetching the result from a special register. <>= constructors mul rd, rs, rt is multu(rs, rt); mflo(rd) @ Sometimes the best expansion for a synthetic instruction depends on the values of operands. We can choose one of several expansions by putting alternatives on the right-hand side of a constructor specification, each with its own set of equations. Each application of the constructor uses the first alternative for which the equations can be solved. For example, the [[li]] (load immeditate) synthetic instruction has three ways to load a signed value [[imm]] into register [[rt]]. When [[imm]] fits in 16 bits, use an immediate mode [[addiu]] instruction where the second operand is register 0, which is always 0. When the low-order 16 bits of [[imm]] are zero, use [[lui]] to assign the high-order bits to [[rt]]; [[lui]] automatically zero's the low-order bits. In the general case, cut [[imm]] into slices and use two instructions: [[lui]] to assign the high-order bits and [[addiu]] to add in the low-order bits. <>= constructors li rt, imm when { imm@[16:31]! = imm@[15]! } is addiu(rt, r0, imm@[0:15]!) when { imm@[0:15] = 0 } is lui (rt, imm@[16:31]) otherwise is lui(rt, imm@[16:31] + imm@[15]); addiu(rt, rt, imm@[0:15]!) @ For the third branch, the toolkit generates an unnecessary test to see that [[imm@[16:31] + imm@[15]]] doesn't overflow 16~bits. The test isn't needed, because the only way it can happen is when everything in sight is ones, and in that case we take the first branch. I'd love to have a symbolic-algebra system smart enough to figure this out. @ \subsection{The floating-point coprocessor} Pages B-5 through B-7 of the MIPS manual introduce a few more field names for the convenience of specifying the floating-point instructions. The integer-register fields [[rd]], [[rs]], and [[rt]] could be re-used to refer to fields of floating-point instructions, but we introduce new fields [[fd]], [[fs]], and [[ft]] in order to have different names for the registers. <>= ft 16:20 fs 11:15 fd 6:10 format 21:24 bit25 25:25 <<[[fieldinfo]] specifications>>= fieldinfo [ fs ft fd ] is [ <>] <>= names [ f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 f17 f18 f19 f20 f21 f22 f23 f24 f25 f26 f27 f28 f29 f30 f31 ] @ The [[format]] field has only three legitimate values: 0, 1, and 4. The [[sparse]] field attribute associates the names [[s]], [[d]], and [[w]] (signifying single, double, and word, respectively) with these values. <<[[fieldinfo]] specifications>>= fieldinfo format is [ sparse [ s = 0, d = 1, w = 4 ] ] @ The instruction codes for Coprocessor 1 (floating point) are given on page B-28 of the MIPS manual. We use names like ``[[add.]]'' instead of ``[[add.fmt]]'' because they make it possible to form the full name of the instruction by concatenating the name of the opcode pattern and the name of the format, e.g., [[add.s]], [[add.d]], etc. They also distinguish the floating-point opcodes from analogous integer opcodes. <>= patterns [ add. sub. mul. div. _ abs. mov. neg. _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ cvt.s cvt.d _ _ cvt.w _ _ _ _ _ _ _ _ _ _ _ c.f c.un c.eq c.ueq c.olt c.ult c.ole c.ule c.sf c.ngle c.seq c.ngl c.lt c.nge c.le c.ngt ] is cop1 & funct = {0 to 63} & bit25 = 1 @ Specifying the branch and move instructions is more complicated, because the relevant codes span several entries in the table, and the pattern language is designed to bind one pattern to one entry. We introduce two new fields to simplify the specification. <>= cop1code 22:25 copbcode 16:16 <>= patterns [ mfc1 cfc1 mtc1 ctc1 ] is cop1 & cop1code = {0 to 3} & funct = 0 bc1x is cop1 & (cop1code = 4 | cop1code = 6) bc1f is bc1x & copbcode = 0 bc1t is bc1x & copbcode = 1 @ The pattern [[bc1x]] is under-constrained. The architecture manual indicates that the [[cop1code]] field for the [[bc1f]] and [[bc1t]] instructions can have the value 4 or 6. When generating encoding code for the [[bc1f]] and [[bc1t]] constructors, the toolkit warns that their output patterns are under-constrained and chooses the [[cop1code = 4]], as described in the first disjunct for [[bc1x]]. Toolkit-generated decoding code recognizes either variant. @ {\hfuzz=0.7pt Like the integer opcodes, the floating-point opcodes are grouped by assembly-language syntax. \par} <>= patterns arith3. is add. | div. | mul. | sub. arith2. is abs. | mov. | neg. movec1 is mfc1 | mtc1 | cfc1 | ctc1 c.cond is c.f | c.un | c.eq | c.ueq | c.olt | c.ult | c.ole | c.ule | c.sf | c.ngle | c.seq | c.ngl | c.lt | c.nge | c.le | c.ngt lsc1 is lwc1 | swc1 convert is cvt.s | cvt.d | cvt.w @ The following constructor specifications introduce the compound-opcode concatenation operator ([[^]]). Each floating-point opcode has three variants, according to whether the value of the [[format]] field is [[s]], [[d]], or [[w]]. We form the constructors by concatenating opcode names with [[format]]. One constructor is created for each member of the cross product of the patterns named, (e.g., [[add.s]], [[add.d]], [[add.w]], [[div.s]], [[div.d]], etc). Constructor names can also include string literals delimited by double quotes, e.g. [[convert^"."^format]]. As with the integer instructions, most output patterns are implicit. The floating-point arithmetic, conditional, and type-conversion instructions all require floating-point operands that are even-odd register pairs. The equations for [[arith3.^format]], etc., below specify that the register operands are all even values. These equations have been commented out because we believe people won't want to pay the overheads of checking when generating encoding procedures, but we want them when we validate the spec, so I have arranged for the command \mbox{[[sed 's/# {/{/']]} to uncomment them. <>= constructors arith3.^format fd, fs, ft # { fd = 2 * _, fs = 2 * _, ft = 2 * _ } arith2.^format fd, fs # { fd = 2 * _, fs = 2 * _ } movec1 rt, rd c.cond^"."^format fs, ft # { fs = 2 * _, ft = 2 * _ } convert^"."^format fd, fs # { fd = 2 * _, fs = 2 * _ } "bc1f" reloc { reloc = L + 4 * offset! } is bc1f & offset; L: epsilon "bc1t" reloc { reloc = L + 4 * offset! } is bc1t & offset; L: epsilon @ We have to quote [[bc1f]] and [[bc1t]] instead of using them directly as opcodes, because these patterns have multiple disjuncts. The constructor-specification process ``explodes'' opcodes, so it would pick just one disjunct, and we would be unable to recognize the other when decoding an application of the constructor. @ There are several synthetic instructions that operate on pairs of floating point registers. [[l.d]] and [[s.d]] load and store double words, respectively. [[mtc.d]] and [[mfc.d]] move pairs of words in registers to and from the floating point co-processor. <>= constructors l.d ft,offset!(base) # { ft = 2 * _ } is lwc1(ft, offset!, base); lwc1(ft+1, offset!+4, base) s.d ft,offset!(base) # { ft = 2 * _ } is swc1(ft, offset!, base); swc1(ft+1, offset!+4, base) mtc1.d rt, fs # { rt = 2 * _, fs = 2 * _ } is mtc1(rt, fs); mtc1(rt+1, fs+1) mfc1.d rt, fs # { rt = 2 * _, fs = 2 * _ } is mfc1(rt, fs); mfc1(rt+1, fs+1) @ Because [[offset]] is a field, it is unsigned, and so we must use [[offset!]] to get the signed offset that [[lwc1]] and similar constructors expect. \iffalse \subsubsection{Other synthetic instructions} We include one more synthetic instruction to illustrate the use of the sequence ([[;]]) pattern operator. [[trunc.w.d]] implements the [[trunc.w.d]] assembly instruction and requires a sequence of 13 tokens. When applied, the [[trunc.w.d]] constructor emits the complete sequence specified on the right-hand side. We've put this thing in its own specification file because it doesn't appear in the TR (plus this way we'll be able to elide using an elide filter if ever I write one). <>= constructors trunc.w.d fs, ft, rt is cfc1(rt, f31); cfc1(rt, f31); nop(); ori(r1, rt, 3); xori(r1, r1, 2); ctc1(r1, f31); srlv(r0, r0, r0); cvt.w.d(fs, ft); nop(); ctc1(rt, f31); nop(); mfc1(rt, fs); nop() @ \fi @ \subsection{Application-specific specifications for the {\tt mld} linker} An application writer has the option of extending a machine's specification to include application-specific information. These extensions can simplify implementation of the application or can be used by the toolkit to generate more efficient encoding code. {\tt mld} is a retargetable, optimizing linker that generates code for the MIPS or the SPARC. {\tt mld} uses the toolkit to emit executable binary directly, instead of going through the assembler. This means it needs substitutes for the synthetic [[div]], [[divu]], [[rem]], and [[remu]] instructions provided by the MIPS assembler. @ The MIPS hardware does no checking for divide by zero or divisions that overflow; these checks have to be done in software. A [[break 7]] instruction is used to indicate one of these errors; so {\tt mld} has to generate code that does these tests. The first test just checks to see if the divisor is zero, branching around the break instruction if it isn't. If, for some reason, we can tell at compile time that the divisor is zero, we just emit a break, because that's what the MIPS assembler does. <>= constructors break7ifzero rt when { rt = 0 } is break(7) otherwise is bne(rt, r0, L); nop(); break(7); L: epsilon @ The other test, for overflow, is more complicated. On a two's-complement machine, integer division can overflow if it is signed, if the divisor is $-1$, and if the dividend is the most negative integer---there aren't enough bits to represent the result. <>= constructors break7ifoverflow rs, rt is addiu(r1, r0, -1); bne(rt, r1, L); lui(r1, 0x8000); bne(rs, r1, L); nop(); break(7); L : epsilon @ Given these two tests, we can define safe versions of signed and unsigned division and remainder. <>= constructors tested_divu rd, rs, rt is divu(rs, rt); nop(); break7ifzero(rt); mflo(rd); nop() tested_div rd, rs, rt is div(rs, rt); nop(); break7ifzero(rt); break7ifoverflow(rs, rt); mflo(rd); nop() tested_remu rd, rs, rt is divu(rs, rt); nop(); break7ifzero(rt); mfhi(rd); nop() tested_rem rd, rs, rt is div(rs, rt); nop(); break7ifzero(rt); break7ifoverflow(rs, rt); mfhi(rd); nop() @ Applications can also play games to trade safety for efficiency. Toolkit-generated encoding procedures prevent the application from putting a value in a field that is too small for it, so for example they won't let an application put 255 in a 5-bit field. If an application writer wants to promise that the values of a field will always fit, it can call the field ``unchecked,'' and the toolkit will omit the check, but it will still mask out the high bits. If the application can guarantee the high bits are zero, it can call a field ``guaranteed,'' and the toolkit won't even do the masking. Many applications, including {\tt mld}, include register allocators that always assign proper values to the fields denoting registers: <>= fieldinfo [ rs rt rd base fs ft fd ] is [ guaranteed ] @ @ [[mld]] emits relocatable addresses into the data segments. There is an argument for putting an address-emitting procedure into the toolkit library, but then that procedure would have to deal with all the details of generating a closure and so on when the value of the address wasn't yet known. Since the toolkit's generator already takes care of those details, it is much easier simply to specify a constructor that emits an address. We create a new token so we can distinguish a 32-bit data token from a 32-bit instruction token, and we choose a placeholder that is known to be an illegal address. <>= fields of addrtoken (32) addr32 0:31 placeholder for addrtoken is addr32 = 7 constructors emit_raddr reloc is addr32 = reloc @ \subsection{Specifications to support validation} We have validated this specification against the DEC-Ultrix MIPS assembler. To do that, we had to alter a little bit of syntax, and we had to discard some constructors that this assembler didn't know about. <>= assembly opcode jr is j jalr is jal mov is move {sll,srl,sra}v is $1 tested_{*} is $1 assembly operand [ rs rt rd base ] is "$%d" [ fs ft fd ] is "$%s" @ The machine instructions not recognized by the MIPS assembler are discarded. <>= discard break lwc0 swc0 arith3.^"w" arith2.^"w" c.cond^"."^"w" cvt.s.s cvt.w.w cvt.d.d swc2 lwc2 swc3 lwc3 @ On the MIPS, the checker's assembly output must include the [[noreorder]] directive. <>= .set noreorder