




\documentstyle[11pt,psfig]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}

\begin{document}

\title{Chapter 3 \\
Introduction to Instruction Sets, Registers and Addressing Modes}

\author{Norman Matloff \\
University of California at Davis}                                

\date{November 18, 1996}

\maketitle            

In this chapter we will introduce the machine language for the Mac-1 
and DLX {\bf architectures}, i.e. their instruction sets, registers and
addressing modes.  Although there are considerable differences
between these two architectures, as well as among those of Intel, MIPS, 
SPARC, PowerPC and other CPU chips, the general principles are fairly 
similar across machines.  Thus someone who is proficient at 
programming in the machine language of one machine will be able to 
quickly learn to program on other machines. 
 
Once again, keep in mind that machine language is what the computer 
executes.  Computers do not execute C or any other high-level language.  
If we write a C program on a given computer, the compiler will 
translate our C code to machine code.  And, once that machine code is
loaded into the computer's memory, the computer can not tell whether 
it came originally from a C source or we wrote it directly in machine 
language ourselves.

\section {Some Introductory Mac-1 Code}

We wish to write Mac-1 machine code which computes the maximum of the 
two numbers in memory locations 540 (0x21c) and 552 (0x228), adds 1, 
and stores the result in memory location 600.\footnote{Some computers
have {\bf virtual memory}, in which the hardware will ``rename''
memory locations.  Reads and writes specified for, say, location 552,
may actually go to, say, location 2014.  This gives the system added
flexibility in ways which we will not describe here, and we will
assume here that the systems being discussed do not have virtual
memory.}  The code itself will begin at memory location 0x100.  (This 
choice was arbitrary.) Here is a listing of the code, showing memory 
locations and their machine-language contents:

\begin{verbatim}
0x100:  0x021c  
0x101:  0x1258
0x102:  0x3228  
0x103:  0x4106
0x104:  0x0228
0x105:  0x1258
0x106:  0x7001
0x107:  0x2258
0x108:  0x1258
\end{verbatim}

To make some sense of this, here is a pseudocode guide to these
instructions:

\begin{verbatim}
0x100:  load c(540) to the AC register  
0x101:  store c(AC) memory word 600
0x102:  subtract c(552) from AC, and place the result in AC  
0x103:  if the result is positive, go to location 0x106
0x104:  load c(552) to the AC register
0x105:  store c(AC) memory word 600
0x106:  load the value 1 to the AC
0x107:  add c(600) to the AC
0x108:  store c(AC) to location 600
\end{verbatim}

Now let us look at these instructions in detail,\footnote{By the way, 
a program, such as the one here, consists of {\it instructions}.  The 
reader should take care not to call them ``commands.''  The term {\bf 
command} is generally used to mean things like operating system 
utilities, such as the Unix {\bf ls} command, which prints out file 
names on the screen.  That command itself is a program, made up of 
instructions.  This may seem like a small point, but it {\it is} an 
important one.} and see how their execution proceeds.  Suppose the
initial contents of the Mac-1 registers is as in Figure 3.1:

\vspace{0.2in}
\par
\psfig{file=Fig3.1.eps}
\par

Suppose also that c(540) and c(552) are 5 and 2, respectively, and
suppose there is no instruction prefetching.

{\bf 0x021c}  This is Mac-1's {\bf lodd} (``load direct'') instruction.
As with all Mac-1 instructions, {\bf lodd} is 16 bits long.  Its first
(i.e. most significant) four bits are 0000, which serve as the 
{\bf op code} of this instruction.  What that means is that Mac-1 
hardware\footnote{In some CPUs, including Mac-1 and the Intel family,
part of the hardware is implemented in program-like code called
{\bf microcode}, but this is beyond the scope of the material here.}
is designed so that whenever it sees that the first four bits of an 
instruction are 0000, it knows that this is a {\bf lodd} instruction,
i.e. that the instruction performs the {\bf lodd} operation.
We say that in this process Mac-1 {\bf decodes} the instruction, meaning
that it decides the instruction type by looking at the op code.  Recall
that this is done during Step B.

The remaining 12 bits of the instruction then form the {\bf operand},
i.e. the item on which the instruction will take some action.  In
the case of {\bf lodd}, the operand is interpreted as a memory address,
and the action of the instruction is to copy the contents of that
memory location to the AC register.

After this instruction finishes execution, the CPU will look as in
Figure 3.2:

\vspace{0.2in}
\par
\psfig{file=Fig3.2.eps}
\par

Note the contents of MAR and MDR.  There were {\it two} memory
accesses during the execution of this instruction, first the
instruction fetch and then the read from memory location 0x21c,
a location which happened to contain the value 5.  Thus c(MAR)
and c(MDR) are 0x21c and 5, respectively.

You should make sure you understand the values in the IR, PC and AC.
(Review the material on Steps A, B and C in Chapter 2 if needed.)
It so happens that SP is not affected, but in any case we will not
discuss SP until Chapter 5.

What about c(PS)?  The notation 0b00 means a 2-bit string, both 0s.
These two bits are called the N (``negative'') and Z (``zero'') bits.
Each time an instruction which uses the ALU is executed,\footnote{In
most machines, this includes instructions that load from and store to
memory, in this case {\bf lodd}, because their operands do pass
through the ALU.} the N bit will be set to 1 or 0, depending on
whether the result of the instruction is negative or not.  Similarly,
the Z bit will be set to 1 or 0, depending on whether the result of
the instruction is zero or not.  Since the value fetched by the {\bf
lodd} instruction here was 5, the N bit will be 0 (``No, 5 is not
negative'') and the Z bit will be 0 too (``No, 5 is not zero'').  You
will see why PS is important below, when we discuss the instruction at
0x103.

The reason this type of instruction is called ``load-direct'' is that
it uses {\bf direct addressing mode}, meaning that the operand's
address (in this case 0x21c) is given directly within the instruction.

Actually, one might count the AC register, to which this instruction
loads data, as the second operand.  However, in this case the operand
is implicit; the {\bf lodd} instruction always loads to AC.

{\bf 0x1258}  This is Mac-1's {\bf stod} (``store direct'')
instruction.  Its op code is 0001, and again the operand address is
specified in the last 12 bits of the instruction (0x258 = 600).

Again the AC register is an implicit operand, in this case the
source of the data; {\bf stodd} copies c(AC) to the specified
memory location.

After execution of this instruction, the state of the CPU will be:

\vspace{0.2in}
\par
\psfig{file=Fig3.3.eps}
\par

{\bf 0x3228}  Recall that we wish to find the maximum of c(540) and
c(552).  We have a copy of the former in AC, which we will now compare
to the latter via subtraction.  Mac-1's {\bf subd} (``subtract direct'')
instruction subtracts the operand from AC and places the result in AC.
The op code is 0011, and the memory location of the subtrahend is 
specified in the last 12 bits of the instruction.

The new state of the CPU will be:

\vspace{0.2in} 
\par
\psfig{file=Fig3.4.eps}
\par

Note c(PS).  Since the result of the instruction's computation was 3,
which is neither negative nor zero, the N and Z bits are both 0.  This
will play a central role in the next instruction.

{\bf 0x4106}  This is our first example of a {\bf branch} (an alternate
term is {\bf jump}) instruction.  This is one is Mac-1's {\bf jpos}
(``jump if positive'') instruction.  Its op code is 0100, and the
remaining 12 bits specify the {\bf target} of the branch, in this
case memory location 0x106.

The actions of a branch are to check whether certain specified 
conditions hold, and if so then load the PC with the target address.
The latter action causes the program to begin executing instructions
at the target address, rather than where we had been executing.

As the name {\bf jpos} implies, the condition to be checked in this
instruction is that a certain quantity is greater than zero.  Which
quantity is that?  This is where the PS register comes into play.  The
quantity in question is the result of the {\it last} instruction
executed which used the ALU, information about which was recorded in
PS's N and Z bits.  The branch will occur (the term used is that the
branch is {\bf taken}) if the result of the last instruction was
positive, meaning that N = 0 and Z = 0.  

This means that the action of our current instruction, 0x4106 at 
location 0x103, will check whether N and Z are both 0, and if so then 
change the PC value to 0x106; otherwise take no action.  In our
instance here, the subtraction in the previous instruction happened
to be 5-2 = 3, so that N and Z are both 0, so the jump will be taken.
The circuitry in the CPU will copy the lower 12 bits of the IR to the
PC.  The new CPU state will be:

\vspace{0.2in}
\par 
\psfig{file=Fig3.5.eps}
\par

Note the contents of MAR and MDR, which reflect the instruction fetch.
No other memory access has occurred since then.  Similarly, the branch
instruction does not use the ALU or access AC, so the contents of PS
and AC have not changed.

If on the other hand c(552) had been say, 24, then N would have been
1 and the jump would not have been taken.  Then c(PC) would have been
0x104 (having been incremented from 0x103 during Step A of the
instruction).  We would then execute the {\bf lodd} in 0x104 and
the {\bf stod} in 0x105.  We would only then arrive at 0x106. 

Note that all the CPU ``remembers'' from the previous instruction is
whether that instruction produced a negative result or not, and
whether the result was zero or not.  No other information is recorded.
Thus for instance the CPU, in executing the {\bf jpos} instruction
0x4106, does not remember that the previous instruction was a {\bf
subd}.

{\bf 0x7001}  This is the {\bf loco} (``load constant'') instruction.
The op code is 0111, and the remaining 12 bits specify a constant to
be loaded into AC.  In other words, this instruction will load the
number 1 into AC.

This is known as {\bf immediate addressing mode}, meaning that a
constant operand is embedded in the instruction immediately following
the op code.

The new CPU state will be:

\vspace{0.2in}
\par
\psfig{file=Fig3.6.eps}
\par

{\bf 0x2258}  This is an {\bf addd} (``add direct'') instruction,
with op code 0010.  It works like {\bf lodd}, except that instead of
copying the contents of the specified memory location to the AC, 
it adds those contents to whatever number is already in the AC.
After execution, the CPU will look like this:

\vspace{0.2in}
\par
\psfig{file=Fig3.7.eps}
\par

{\bf 0x1258}  This is another load to location 600, identical to
the one we saw earlier, so no further comment will be made.

By the way, all the Mac-1 instructions in this example happened to
have four-bit op codes, but this is not the case for all Mac-1 
instructions.  In fact, out of Mac-1's 23 instruction types, two
have eight-bit op codes and two have 16-bit op codes.\footnote{In
the latter case, the whole instruction is op code, without any
operands.  An example is {\bf retn}, an instruction that does a
return from a function call.  We will discuss this instruction in
Chapter 5.}  The four-bit op codes are 0000 through 1110.  All the
remaining instructions begin with 1111, such as the {\bf insp}
(``increment SP'') instruction, whose op code is 11111100.  You
should make sure you understand why, once the op codes 0000 through
1110 are set, all other op codes are forced to begin with 1111.

\section {Some Introductory DLX Code}

Again, we will write machine code, this time for DLX, which computes 
the maximum of the two numbers in memory locations 540 (0x21c) and 
552 (0x228), adds 1, and stores the result in memory location 600.  
Let us suppose that we also want the code to copy c(540) to DLX's 
r10 register.

The DLX architecture features 32-bit words and addresses, and includes a
program counter, pc, 32 general-purpose registers r0-r31, and 32
floating-point registers f0-f31.  The general-purpose registers serve as
their name implies.  A given register may be used sometimes as a data
register, other times as an index register, and so on.  However, as is
the case with many RISC machines, register r0 is not so flexible.  In
fact, it is completely inflexible, because the value 0 is hardwired into
it.  DLX also has a program counter, pc.

Again the code will begin at memory location 0x100.  Here is a 
listing of the code, showing memory locations and their 
machine-language contents:

\begin{verbatim}
0x100: 0x8c01021c
0x104: 0x00015020
0x108: 0x20230001
0x10c: 0x8c020228
0x110: 0x0022202a
0x114: 0x10800008
0x118: 0x00000000
0x11c: 0x20430001
0x120: 0xac030258
\end{verbatim}

Here is a pseudocode guide to the code:

\begin{verbatim}
0x100: load c(540) into r1
0x104: copy c(r1) to r10
0x108: add 1 to c(r1) and store the sum in r3
0x10c: load c(552) into r2
0x110: store 1 in r4 if c(r1) < c(r2), otherwise store 0 in r4
0x114: branch to 0x120 if c(r4) is 0
0x118: do nothing!
0x11c: add 1 to c(r2) and store the sum in r3
0x120: store c(r3) to memory location 600
\end{verbatim}

The first thing to note from this pseudocode is that DLX's large
register set gives us much more flexibility, compared to Mac-1,
which has only one data register AC.  Here, for instance, it allows
us to hold copies of both c(540) and c(552) in registers, something
which would have been impossible in Mac-1.  Recalling the fact that
access to registers is much faster than to memory, this is very
significant.  

Note also that though the instructions are stored in consecutive
words of memory, just as in our Mac-1 example, those addresses of
those words ascend in increments of 4.  This difference stems from
the fact that in Mac-1 individual bytes within a word do not have 
addresses, whereas the four bytes within a DLX word have consecutive
addresses ascending in increments of 1.  This also implies that
while c(PC) is incremented by 1 during Step A in Mac-1, the
corresponding increment for DLX is 4.

Now, let us look at the instructions:

{\bf 0x8c01021c:}  This is DLX's {\bf lw} (``load word'') instruction.
The instruction has four subfields:  Bits 0-5, the op code, which is
is 100011;\footnote{In DLX notation, the most significant bit in a
word is called Bit 0, and the least significant is Bit 31.} Bits 6-10, 
which specify one register, in this particular instance r0; Bits 11-15, 
which specify a second register, here r1; and a constant in Bits 16-31,
in this case 0000001000011100 = 0x021c = 540.

As with Mac-1's {\bf lddd} instruction, {\bf lw} copies the contents 
of the specified memory location into a register, but the similarity 
ends there.  

First, in the case of {\bf lddd}, the choice of register to which the 
specified memory location is copied---the term for this is the {\bf 
destination} register---is completely inflexible; it {\it must} be AC.  
By contrast, DLX's {\bf lw} instruction can specify any general-purpose 
register as its destination.  That register is specified in Bits 
11-15,\footnote{Note that this bit field is five bits long, which it 
must be in order to be able to specify any of DLX's $32 = 2^5$ 
general-purpose registers.} in this case r1.

The {\bf lw} instruction's method for specifying the {\bf source}
operand, i.e. the address of the memory location to be copied, also
differs from that of {\bf lddd}.  Recall that the latter uses {\bf direct}
addressing mode; {\bf lw} uses {\bf indexed} addressing mode.  What
this means is that the memory address is specified as the sum of a 
constant, given in Bits 16-31, and a register, given in Bits 6-10.  As 
noted above, in this particular instance constant is 540, so the
address of the memory location to be loaded from is 540+0 = 
540.\footnote{Recall that c(r0) is always 0.}  So, the instruction
here loads c(540) to r1, just as the pseudocode said.\footnote{If
the {\bf lw} instruction consisted just of an op code, a destination
register and a constant, we would have direct addressing mode.}

We stated briefly in Chapter 2 that the name ``indexed'' addressing 
mode comes from array terminology.  Here are the details:  Consider
the C-language expression x[5], where x has been declared as an array,
say of type {\bf int}.  As we discussed in Chapter 1, the compiler
will implement the array in consecutive words in memory, within which
x[5] will be the sixth word (recall that x[0] is the first word).
So, one way to describe x[5] is that it is 5 words past the beginning
of the array x, and thus its address is 

\begin{verbatim}
(address of x) + 5*sizeof(int) 
\end{verbatim}

The idea of indexed addressing can be illustrated in this case
by saying that the address of x would be specified as a constant
within the instruction and that the quantity 5*sizeof(int) would
be stored in an index register (by a previous instruction).  The
instruction using indexed addressing would add these two quantities
together, to produce the proper address for x[5].

Many (though again not all) CISC machines dedicate certain registers
to act as index registers, but DLX and most other RISC machines
are more flexible in this regard.  Any general-purpose register can
be used in indexed addressing.  In this case we used r0 as our
index register, but we need not have.\footnote{Since r0 always 
contains 0, by using r0 as our index register you might think we have 
reduced indexed addressing to the direct addressing case.  However,
that is not true, because an addition will still be performed, which
makes the action somewhat slower than true direct addressing would
have been.}  On the other hand, one might argue that DLX's indexed
addressing is not a true indexed mode, since the 16-bit size of the
constant field implies that indexing is only usable for arrays which 
begin somewhere in the address range 0-0x0000ffff.  (If the compiler
cannot find room to assign all arrays in this range, then it will
need to use a non-indexed access for the higher-address arrays.)

{\bf 0x00015020:}  The pseudocode says that this instruction copies
c(r1) to r10.  It does do this, but in an odd way---as an addition.
Specifically, it will add c(r0) to c(r1) and store the sum in r10.
The reason this works as a copying operation is that the register
r0 has the value 0 hardwired into it, as mentioned earlier.

The DLX {\bf add} instruction's op code is split into two noncontiguous
six-bit fields:  The first field, Bits 0-5, is 000000, which means 
that it will be an instruction which inputs two register values into 
the ALU and outputs the result to a third register.  The second field 
consists of Bits 26-31, with the value 100000.  

The two source registers are specified in Bits 6-10 and 11-15, while
the destination register is given in Bits 16-20.  The reader should
verify that in this instance the three registers are indeed r0, r1
and r10.  Bits 21-25 of the instruction are unused.

As you can see, the designers of DLX set these instruction formats
up in a way that, for instance, the first register field is always
in the same place, Bits 6-10.  This greatly simplifies the design
of the decoding hardware.  On the minus side, it also forced us to
have the split op code field which we see here, which is a bit
inconvenient to read.  However, this is not much of a concern, since
we don't read or write machine language very often; by contrast, the
hardware {\it always} does decoding, on every instruction.  In other
words, we have gained speed and simplicity in our machine, at the
small cost of some rare inconvenience, a good tradeoff.

{\bf 0x20230001:}  In this case the pseudocode, ``add 1 to c(r1) and 
store the sum in r3,'' sounds at first like we have another {\bf add}
instruction.\footnote{Note that r1 itself is not changed here.}  
However, the presence of the constant 1 shows this not
to be the case, since we do not have three registers specified.  In
fact that 1 should remind you of {\bf immediate} addressing, which
we saw earlier in Mac-1's {\bf loco} instruction.  This is indeed
immediate addressing, and DLX's name for the instruction is
{\bf addi} (``add immediate'').  The op code is in Bits 0-5 and
is equal to 001000.  The source register is specified in Bits 6-10,
in this case 00001 (that is, r1), and the destination register is
given in Bits 11-15 (00011, r3).  The immediate constant is in 
Bits 16-31.

{\bf 0x8c020228:}  This is another {\bf lw} instruction, similar
to the previous one.

{\bf 0x0022202a:}  This is an {\bf slt} (``set if less than'')
instruction.  Though this sounds like it deals with condition
codes, the fact is that DLX and many RISC architectures do not
have condition codes.  Instead of having a PS register, what they
do is, in essence, allow any general-purpose register to serve as
a condition-codes register.

The {\bf slt} instruction specifies two source register and one
destination register.   The destination register is set to 1 or 0, 
depending on whether the content of the first source register is less 
than that of the second.  A subsequent branch instruction, usually 
immediately following the {\bf slt} instruction, will then branch or 
not, depending on whether the {\bf slt} instruction's destination 
register contains 1 or 0.  

The format of the {\bf slt} instruction is like that of {\bf add},
with a split op code in Bits 0-5 and 26-31, source and destination
registers given in bit fields 6-10, 11-15 and 16-20, and with Bits
21-25 unused.  Since {\bf slt} is a three-register instruction 
using the ALU, Bits 0-5 are again 00000.  Bits 26-31 are 101010.

The advantage of using this approach, as opposed to having a PS
register, is that many modern CPUs have a {\bf superscalar} design.
This means that the CPU has multiple ALUs and that several instructions
can execute simultaneously, allowing much faster processing.  If
there were only a single PS, it would be difficult if not impossible
to have the ALUs work simultaneously.

{\bf 0x10800008:}  This is the branch instruction, named {\bf beqz}
(``branch on integer equal to zero'').  It consists of the op code
in Bits 0-5, 000100, a source register specified in Bits 6-10, and
a constant in Bits 16-31.  

The action of the instruction is that if the content of the source 
register is 0, then the constant will be added to the current PC value; 
otherwise no change is made to the PC.  

Note that this is done in Step C of the instruction, so that the PC 
has already been incremented (by 4) in Step A.  So, when deciding 
what constant to write into this instruction, the programmer (or the 
compiler, if the original program was in a high-level language) 
must set the constant to be the distance to the branch target from
the instruction {\it following} the branch.

To make this concrete, let us look at the numbers in this particular
instruction, 0x10800008.  The source register is r4, the constant
is 8, and the instruction is at memory location 0x114.  Thus the 
branch target will be (0x114+4)+8 = 0x120---which you can see from
the pseudocode is exactly what we wanted.

It is important to keep in mind that the constant is interpreted as
a {\it signed} integer.  If we have a ``backward'' jump---say an
instruction at the end of a loop, making us jump up to the top of
the loop---then the constant will be negative.

This in turn implies that before the constant is added to c(PC)+4,
we must {\bf sign-extend} the constant, meaning that we must convert
the constant from a 16-bit signed number to the equivalent 32-bit
signed number.  But this is easy; we simply prepend 16 copies of
the 16-bit number's sign bit.  For instance, the number -4 in 16-bit
form is 1111111111111100, while its 32-bit form is 
11111111111111111111111111111100.

Though RISC machines differ from CISC in their handling of branches,
in terms of condition codes and a delay to be discussed below, the
idea of specifying the branch target address as a distance from the
next instruction is common in both types of machines.  Such an
arrangement has the advantage that it makes programs easy to
{\bf relocate}.  For instance, we arbitrarily chose to load our
DLX code here starting at 0x100, but if we then decided to move
it to a section of memory starting at say, 0x6040, the same machine
code would work.  The distance from our {\bf beqz} (+4) to our
target would still be 8, so the same {\bf beqz} instruction would
work.  This would not be the case for our Mac-1 code's branch
instruction 0x4106 in location 0x103, since that instruction explicitly
specifies 0x106 as its target.

{\bf 0x00000000:}  As the pseudocode says, this instruction does
absolutely nothing.  It is thus called a {\bf nop} (``no operation''),
pronounced ``no op.''

If this instruction does nothing, why do we have it here?  The answer
lies in the fact that DLX and most RISC machines feature something
called {\bf delayed branch}, which works as follows.  

The simplicity of RISC machines facilitates pipelined operation.  Recall 
from Chapter 2 that one common form of pipelining is to {\bf instruction
prefetch}, that is to fetch the next instruction from memory while 
executing the current instruction.   This means we can skip Step A of 
the next instruction, thus increasing processing speed.  But in the 
case of a conditional branch, it is not clear which instruction will 
be executed next; if the branch is taken, the next instruction 
executed will be the one at the branch target, but if not, it will be 
the one at the next sequential memory address following the branch 
instruction.  Since we will not know whether the branch is taken 
until the end of Step C of the branch, this means we cannot prefetch 
the next instruction.
  
On RISC machines most instructions execute in a single clock cycle.
The implication of this is that in the situation described in the
preceding paragraph, the lack of instruction prefetch after a branch
would mean we would have a clock cycle during which no useful work
is being done.\footnote{It is assumed here that an instruction fetch
from memory, or better from cache, can be done within one clock cycle.}

The way that the delayed branch mechanism deals with this problem is
to design things so that the instruction sequentially following the
branch is always executed, {\it even if the branch is taken}.  The
hope is that in doing so we will avoid the loss of one clock cycle,
since we will definitely prefetch the instruction sequentially 
following the branch. 

But of course we cannot do this at the expense of losing the correct
execution of the code.  In our code here, without the {\bf nop}
in 0x118, the next sequential instruction after the branch would be
the {\bf addi} in 0x11c.  As you can see from the pseudocode, if this
instruction is executed even when the branch is taken, the code
will not produce correct results.  Thus we need to put a ``harmless''
instruction in 0x118, the {\bf nop}.  

Yet putting a {\bf nop} there means we still have a clock cycle during
which no useful work is done.  Thus we have to try a little harder,
and see if we can move some other instruction into the {\bf delay
slot} at 0x118.  In fact, we can:  The {\bf add} instruction at 0x104
can be moved to 0x118, without adversely affecting the correct
execution of the code.\footnote{Note that this actually makes the
branch execute earlier.  Thus the term {\it early branch} might have
been more appropriate than {\it delayed branch}, but the latter was
chosen.} The code would then look like this (first the pseudocode,
then the actual machine code):

Here is a pseudocode guide to the code:

\begin{verbatim}
0x100: load c(540) into r1
0x104: add 1 to c(r1) and store the sum in r3
0x108: load c(552) into r2
0x10c: store 1 in r4 if c(r1) < c(r2), otherwise store 0 in r4
0x110: branch to 0x120 if c(r4) is 0
0x114: copy c(r1) into r10
0x118: add 1 to c(r2) and store the sum in r3
0x11c: store c(r3) to memory location 600
\end{verbatim}

\begin{verbatim}
     0x100: 0x8c01021c
     0x104: 0x20230001
     0x108: 0x8c020228
     0x10c: 0x0022202a
     0x110: 0x10800008
     0x114: 0x00015020
     0x118: 0x20430001
     0x11c: 0xac030258
\end{verbatim} 

It is very important that the reader understand that the reason
we could safely move the ``copy c(r1) into r10'' instruction from
its previous location of 0x104 in the original code to the delay
slot at 0x114 here (previously at 0x118) is that c(r1) does not
change between the instructions ``load c(552) into r2'' and
``branch to 0x120 if c(r4) is 0,'' and r10 is not used by those
instructions.

Here we are programming directly in machine language, but in most
cases this process of {\bf filling the delay slot} (with a ``real''
instruction rather than a {\bf nop}) is done by the compiler.

{\bf 0x20430001:}  As mentioned earlier, this is another {\bf addi}
instruction.

{\bf 0xac030258:}  This is an {\bf sw} (``store word'') instruction,
the mirror image of {\bf lw}, copying from a register to memory instead
of vice versa.  Again, indexed addressing is used, with r0.  The source
register is r3.

\section{Some CISC/RISC Comparisons}

As mentioned earlier, RISC machines feature very simple instruction
sets, a trait which RISC proponents say enables faster CPUs.  When
they first became popular in the mid-1980s, there was much controversy
over this assertion.  At the time, a major proponent of the CISC approach
was the Digital Equipment Corporation (DEC).  DEC's VAX computer line 
had up to that point been tremendously successful, and also arguably
the most ``CISC-ish'' popular machine ever built.  It had over 304
instructions, including such esoteric instruction as {\bf poly},
which evaluated polynomials.

Today, the only major company staying with CISC is Intel.\footnote{Of 
course, the word ``only'' here is somewhat misleading, since it 
ignores Intel's dominant position in the marketplace.  It is still
the case that most standalone computers (i.e. not chips in embedded
applications) use CISC chips.}  Intel has itself developed RISC chips, 
but because of the popularity of IBM-compatible PCs, Intel has 
focused on producing chips which are compatible with the earlier ones,
and thus has found it economically advantageous to stick with CISC.
 
Even DEC has switched to RISC, using the MIPS Corporation's chip in 
their inexpensive computers, and using DEC's own Alpha chip in the 
faster machines.  

Nevertheless, one must keep in mind that the electronics (and chemistry)
of chip-making technology is constantly changing.  In the future, this
technology may change in a way that CPUs will begin to have at least
some CISC features.

What, then, are the traits typifying the CISC and RISC approaches?
A full answer to this question is beyond our scope here, but we can
at least illustrate some of the differences by taking a look at the
Mac-1 and DLX examples above.

The large, flexible register set in DLX is typical in RISC machines, 
and though many CISC machines also have large general-purpose 
register sets (such as the VAX), many other CISC machines do not.  
The Intel family, for instance, has only four data registers, named AX, 
BX, CX and DX.  

Moreover, the Intel and many other CISC architectures are said to be 
less {\bf orthogonal} in design than are most RISC machines.  We say 
an architecture is orthogonal if every operand is allowed to be 
combined with every operation.  This is not a black-or-white term, 
allowing no shades of gray; instead, we say that CPU types which 
allow more combinations of operands and operations are more orthogonal.  

The Intel family is considered to be quite nonorthogonal.  For instance,
let us consider its {\bf mul} instruction, which performs multiplication.
Recall first that in the multiplication x*y, x is called the {\bf 
multiplier}, y is the {\bf multiplicand} and x*y is the {\bf product}.  
The Intel {\bf mul} instruction allows us to specify any of the four
data registers as the multiplier, but insists that the multiplicand
be in register AX.  

This allows the {\bf mul} instruction to be shorter than otherwise, since 
we do not have to use bits to specify the multiplicand register.  Shorter 
instructions save memory space, which was very important during CISC's 
heyday, when memory was expensive.  On the other hand, RISC proponents 
believe that such lack of uniformity makes smooth pipelining more 
difficult, and thus slows down the speed of CISC machines.\footnote{The
reader may protest this assertion, pointing out that Intel machines
have continued to get faster over the years.  This is true, but the
increase in speed is largely due to improved electronics.  The RISC
machines have also gotten much faster during this time, and the
general consensus (though fair comparisons are very difficult to
make) is that the RISC machines do give better performance.}
Note too that compiler writers have a tougher job on CISC machines,
since they have to work around the nonorthogonality obstacles.

If you review the Mac-1 sample code above, you will quickly see that
the fact that we have only one data register to work with (AC) made
programming much more difficult.  By contrast, DLX's large register
set, combined with the orthogonal nature of DLX, makes it much easier
to write code on this machine.  For this reason, orthogonal 
architectures also make things easier for compiler writers.

The key idea of orthogonality is uniformity.  Uniformity is also
key to another RISC characteristic, which is that all instructions
have the same length.  For instance, all DLX instructions are four
bytes long.  Though it is true that all Mac-1 instructions also have
the same length (two bytes), this is mainly due to the fact that Mac-1
was intended as a teaching tool, and thus was kept fairly simple.
By contrast, Intel instructions range in length from one to six bytes.

As mentioned earlier, RISC instructions tend to execute in a single
clock cycle, which is definitely not the case for CISC.  This especially
helps facilitate the design of a smooth, fast pipeline.  Note, though,
the single-cycle requirement then means that more complicated
instructions cannot be included.  This is why the SPARC chips, for
instance, do not even include a multiply instruction.

RISC machines tend to have a {\bf load/store} architecture, which means that
the only instructions with operands in memory are those that load from memory
to a register or store from a register to memory.  In such architectures,
instructions that do addition, subtraction and so on have only register
operands.  Mac-1 is definitely not a load/store architecture, since for example
its {\bf addd} instruction has a memory operand. 

It is from this consideration that you can begin to see why RISC
(machine-language) programs tend to be larger than their CISC
counterparts.  What Mac-1 can do in one {\bf addd} instruction takes
two instructions on DLX.\footnote{That does not mean that in general DLX
programs will be double the size of Mac-1 programs.  In fact, in
our two code examples earlier in this chapter, both were nine
instructions long, though each DLX instruction takes up four bytes,
compared to Mac-1's two.}

\section{Analytical Exercises}

{\bf 1.}  Construct pictures like those in Figures 3.2-3.7 for the DLX
example in Section 2.  Assume the same values in locations 540 and 552
as in the Mac-1 example.  Do not draw pictures, though; simply make a
table showing the register contents:  rows for the instructions, and
columns for the registers.  The relevant registers are mar, mdr, ir, pc,
r1-r4 and r10.  

{\bf 2.}  Suppose we have a C program in a file z.c, containing
a variable Y of type {\bf int}, and a statement

\begin{verbatim}
Y = 12;
\end{verbatim}

Suppose we compile, with the output file being a.out.  In the storage
on disk of the file z.c and a.out, state the exact bit strings which
correspond to that number 12.  (Assume a big-endian machine with
16-bit word size, but make no assumptions about which specific
machine it is.)

{\bf 3.}  Fill in the blank, being as specific as possible:  The fact 
that Mac-1's {\bf loco} instruction only loads to the AC, not to SP 
is an example of the \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ 
nature of the Mac-1 architecture.

{\bf 4.}   Fill in the blank:  Generally a Mac-1 program will
have more instructions which access
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ than will a
corresponding DLX program.

{\bf 5.}  Look at the Mac-1 machine code example at the beginning
of this chapter.  Answer parts (a) and (b) independently, i.e. do not 
assume the conditions in one apply to the other.

\begin{itemize}
\item [(a)]  Suppose the program were to be loaded starting at
location 0x200 instead of 0x100.  Show which changes, if any, would
need to be made to the instructions in this code.

\item [(b)]  Suppose when we typed in the machine code we accidentally
wrote 0x1103 instead of 0x1258 for the instruction at 0x101.  Assume
c(540) = 0x6100 and c(552) = 0x2304.  When we then ran the program, what
disasters, if any, would occur?  Assume no virtual memory.  Be very 
specific.
\end{itemize}

{\bf 6.}   Fill in the blanks:  The DLX instruction 0xac6c0040 is
an {\bf sw} instruction in which r3 plays the role of our
\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_ register, on an array
which begins at 0x\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_.

{\bf 7.}  Write Mac-1 machine code which will swap the contents of locations
60 and 61 in memory.

{\bf 8.}  As we have seen, DLX has two main op code formats, one being
a 6-bit format in Bits 0-5, and the other being a 12-bit format in which
bits 0-5 are 000000 and bits 26-31 contain the rest of the op code.  How
many distinct op codes, i.e. how many instruction types, could we encode
with these two formats?


\section{Programming Projects}

{\bf 1.}  Write Mac-1 code to count the number of negative numbers
in memory locations 0x200 through 0x220, inclusive, placing the count
in memory location 0x842.  Make use of Mac-1's SP register and {\bf pop}
instruction.  (Refer to Appendix A for the details of this and other
Mac-1 instructions.)  

{\bf 2.}  Write DLX code to count the number of negative numbers
in the memory locations c(r1) through c(r2), inclusive, placing the 
count in memory location c(r3).

\end{document} 

