Computer Architecture

Lecture Notes
Spring 2005
Dr. Michael P. Frank
Competency Area 3:
Programming and Coding Methods

Main goals of this chapter:
To be able to derive binary MIPS instruction code from
assembler code
To be able to derive assembler code from C-code
representations

Well be working with the MIPS instruction set architecture
similar to other architectures developed since the 1980's
used by NEC, Nintendo, Silicon Graphics, Sony
MIPS instruction set architecture will be introduced in a step-
by-step approach. By the end of the chapter, you should
have a good understanding of the design rules, and be able
to analyze MIPS ISA.
Instructions
Instructions Language of the Machine

Instruction Set its vocabulary

More primitive than higher level languages
e.g., no sophisticated control flow for branches, loops

Very restrictive
e.g., MIPS Arithmetic Instructions

* Common design goal among computer designers:
maximize performance and minimize cost, reduce design time
Instructions
Four design principles will be introduced in this chapter which
are important in instruction set architecture design:

Design Principle 1: Simplicity favors regularity.

Design Principle 2: Smaller is faster.

Design Principle 3: Good design demands good
compromise.

Design Principle 4: Make the common case fast!

Instructions
In MIPS assembly language, all instructions have 3
operands only
Destination operand and 2 source operands.
Instructions can perform only one operation at a
time.
However, pipelined and superscalar implementations may
execute multiple instructions simultaneously.
Operand order is fixed (destination first):
Example:
C code: A = B + C

MIPS code: add A, B, C
A # symbol marks the start of a comment,
Comments are ignored by the compiler.
MIPS Arithmetic
MIPS architecture philosophy is to keep the hardware simple,
since complex instructions require more physical hardware
resources to implement (space, time, energy costs).
This constraint has been becoming less important as transistors
shrink.

***Design Principle 1: Simplicity favors regularity.

However, simplicity in the ISA design can lead to a larger size
for compiled code.

C code: f = (g+h) (i+j);

MIPS code: add t0, g, h
add t1, i, j
sub f, t0, t1


MIPS Arithmetic
Symbolic variable notation is used in previous
examples.
However in MIPS architecture, only registers can
be used as operands.
Registers are 32 bits word length
There are 32 registers available (for integer
arithmetic) in the MIPS architecture.
The registers (almost) all behave the same.
Simple, regular program design & HW implementation.

MIPS Arithmetic
MIPS Arithmetic
NAME Register Number Usage
$zero $r0 Hardwired to the constant value 0
$v0 - $v1 $r2 - $r3 Subroutine results and expression evaluation
$a0 - $a3 $r4 - $r7 Arguments (parameters) to subroutines
$t0 - $t7 $r8 - $r15 Temporary registers (caller saves)
$s0 - $s7 $r16 - $r23 Saved registers (callee saves)
$t8 - $t9 $r24 - $r25 More temporary registers (caller saves)
$gp $r28 Global pointer (e.g. to static data area)
$sp $r29 Stack pointer (stack grows downwards)
$fp $r30 Frame pointer (to local variables on stack)
$ra $r31 Return address for subroutine calls
MIPS register conventions:
Note: Register $r1 is reserved for use by the assembler and
Registers $r26-$r27 are reserved for the operating system.
*** Design Principle 2: smaller is faster.
Why?
Having a large number of registers will increase clock cycle
time (longer wires, more RC delay)
Recall that having a smaller clock cycle time will improve
performance!
Effective use of the principle is key to computer
performance ;
Computer designer must balance the programmers desire for
more registers with the need for a minimal clock cycle time.
Programmers also should worry about this
A program that uses less memory will often run faster.
Less cache contention, virtual memory not needed.
MIPS Arithmetic
Arithmetic instructions operands must be registers,
No arithmetic instructions operate directly on memory contents
Only 32 registers are provided.
Revisit earlier example:
C Code: f = (g+h) (i+j);
Modified MIPS code:
add $t0,$s1,$s2 #Register $t0 contains g+h
add $t1,$s3,$s4 #Register $t1 contains i+j
sub $s0,$t0,$t1 #Reg. $s0 gets $t0-$t1=(g+h)(i+j);
What if we have more than 32 variables in our program?
Must transfer values to and from main memory to work with them.
We can access single variables, arrays, and other data structures
located on the stack,
in statically allocated memory,
or on a dynamically-allocated heap.
Registers versus Memory
How can a computer represent and manipulate large
data structures, such as arrays?

Recall processor contains only small amount of data
in registers, but memory can contain millions (even
billions) of data elements.

Data transfer instructions (load/store) allow the CPU
to transfer data between registers and memory.

To access a word in memory, the instruction must
specify a memory address (location).


Registers versus Memory
Memory can be viewed as a large, 1-dimensional array.
A memory address serves as an index into the array.
Byte addressing means that there is a unique index
for each individual byte (8 bits) of memory.
Memory Organization
registers
Processor
1
114
10
100
0
1
2
3
address
data
Memory
Data transfer
Recall from last time

The instruction set architecture (ISA) of a machine can
be thought of as the hardwares user interface.
Where by users here we mean software engineers, such as
compiler writers and assembly language programmers.
We are studying the MIPS instruction set architecture;
MIPS is a reduced instruction set computer (RISC), which
allows for simplified hardware.
Recall, design principle 1:
Simplicity favors regularity .
MIPS has 32 registers, each 32 bits long.
As opposed to hundreds of registers in some architectures.
Design Principle #2: Smaller is faster
Hence improved performance through reduced
clock cycle time.
Recall, that a list of many data elements are stored in an array.
To access these elements (i.e. memory locations) we use data transfer
instructions: load and store.
The data transfer instruction that moves data from memory to a
register is called load.
Think Load the data into the CPU for processing.
Like Load the dishes into the dishwasher for cleaning.
In MIPS the actual instruction is lw for load word.
Other load instructions transfer data of different sizes.
To transfer data from registers to memory, use store.
Think Store the data back in memory after processing.
Like Store the dishes back in the cabinet after washing.
MIPS: Use sw for store word.
You can think of memory as essentially a large 1-dimensional array,
with the address acting as an index into that array.
Memory Organization
Example: The address of the third word in the following array
is 8 and the value of Memory[8]=10.
Memory Organization
1
114
10
100
0
4
8
12
address
data
Memory
* This is an example of byte addressing in which the index refers to a byte of
memory. Since words are 32 bits long, the memory address increments by 4
so that words will always start at addresses that are a multiple of 4. This
requirement is known as alignment restriction; it can help to speed up data
transfers.
Consider the following example:
Assume that A is an array of 100 words and the compiler has associated registers
$s1 and $s2 with the variables x and y. Also assume that the starting address,
or base address is contained in register $s3. Determine the MIPS instructions
associated with the following C statement:

x = y + A[8]; // adds 8
th
element in array A to y and stores result in x

Solution:
Before we can perform any arithmetic operations, we must first transfer the data
contained in A[8] to a temporary register.
lw $t0, 32($s3) # $s3 contains the base address of array and
# 32 is the offset address of the 8
th
element
add $s1, $s2, $t0 # performs addition
Memory Organization
Note that machines can use different endian-ness conventions to
order bytes within a word.





Memory Organization
Big Endian Little Endian
0
(LSB)
1 2 3
(MSB)
3
(MSB)
2 1 0
(LSB)
Byte # Byte #
-DECStation 3100 Machines
-Intel 80x86 family
- Sun SPARC
- Machintosh (PPC)
- MIPS
Address: a a+1 a+2 a+3
a a+1 a+2 a+3
From Gullivers Travels: Gulliver finds out that there is a law, proclaimed by the grandfather
of the present ruler, requiring all citizens of Lilliput to break their eggs only at the little ends.
Of course, all those citizens who broke their eggs at the big ends were angered by the
proclamation. Civil war broke out between the Little-Endians and the Big-Endians, resulting
in the Big-Endians taking refuge on a nearby island, the kingdom of Blefuscu.
Starts with
the little
end!
Starts with
the big
end!
If a machine uses byte-addressing with 8-bit
addresses, how many different byte locations can be
accessed?



If 32-bit-long byte addresses are used, how many
different aligned 32-bit word locations can be
accessed?
(Do as an in-class exercise.)





Memory Organization
256 2
8

Memory locations with addresses ranging from 0 to 255

(Hint: Memory locations increment by 4=2
2
.)
Example (using load and store)
Assume that A is an array of 100 words and the compiler has
associated registers $s1 with the variable x. Also assume that
the base address of the array is in register $s2. Determine the
MIPS instructions associated with the following C statement:
A[12] = x + A[8];

Solution:
lw $t0, 32($s2)
add $t0, $s1, $t0
sw $t0, 48($s2)



Memory Organization Example
NOTES:
(1) Store word instruction has destination last as last element.
(2) Remember arithmetic operands are registers only, not memory!

Example (using variable array index)
Assume that A is an array of 100 elements and the base is in $s3. Also
assume that the compiler associates g, h, and i with $s1, $s2, and $s4.
Determine the MIPS instructions associated with the following C statement:

g = h + A[i];
Solution:
We need to know that address of the A[i] before we can load it into a
temporary register. Recall, that to access an element in memory we must
multiply it by 4 to account for byte addressing. To accomplish this we perform
the following sequence of operations:

4i First, i + i = 2i then 2i + 2i = 4i

add $t1, $s4, $s4 # temp register holds 2i
add $t1, $t1, $t1 # temp register holds 4i
add $t1, $t1, $s3 # $t1 holds address of A[i]
lw $t0, 0($t1) # loads A[i] into temp register $t0
add $s1, $s2, $t0
Memory Organization Example
MIPS
loading words but addressing bytes
arithmetic on registers only

Instruction Meaning

add $s1, $s2, $s3 $s1 = $s2 + $s3
sub $s1, $s2, $s3 $s1 = $s2 $s3
lw $s1, 100($s2) $s1 = Memory[$s2+100]
sw $s1, 100($s2) Memory[$s2+100] = $s1


In programs containing more variables than registers, the compiler
tries to keep the most frequently used variables in registers and the
rest in memory. This process is known as spilling. Why is this
important to system performance?
Recap
Both numbers (data) and instructions are stored in computer
hardware as high and low electronic signals (e.g. binary
signals).

MIPS Assembly Instructions are converted into machine
language using a sequence of 1s and 0s (a.k.a machine code.)

MIPS Instruction Format:
Composed of different segments called fields
Instructions are exactly 32 bits long
Same size as a data word
Machine Language
op rs rt rd shamt funct
MIPS Instruction Format:



Op: Opcode the basic operation of the
instruction
Rs: First register source operand
Rt: Second register source operand
Rd: register destination operand
Shamt: Shift amount (explained in Chapter 4)
Funct: Function selects the specific variant of the
operation in the opcode
Machine Language
op rs rt rd shamt funct
Design Principle #3: Good design demand good
compromise!
Thus, all MIPS instructions have the same length (32 bits) but
different formats are used:
(1) R-Type (for Register)



(2) I-Type (for data transfer type functions)

Machine Language
op: 6bits rs: 5bits rt: 5bits rd: 5bits shamt:
5bits
funct: 6bits
Bit allocation for R-type format:
op: 6bits rs: 5bits rt: 5bits Address: 16 bits
Bit allocation for I-type format:
Examples:
Machine Language
0 17 18 8 0 32
(i) add $t0, $s1, $s2
35 19 8 32
In decimal representation:
000000 10001 10010 01000 00000 100000
In binary representation:
(ii) lw $t0, 32($s3)
Binary representation: (do on own)
In decimal representation:
Wheres the compromise?
Machine Language
Appendix A (on the CD-ROM), pages A-50 through
A-81, gives format for assembly language instructions
in the third edition.

Example:
For the given C statement, determine its MIPS
assembly code, as well as, its corresponding machine
code. Assume that the base address for A is contained
in $s2.

A[100] = x + A[50];


(do on own)
Since instructions are represented as numbers, programs can be
stored in memory to be read just like data.
This idea leads to the stored-program concept, which allows
a computer to execute different programs that are stored in
memory.











Stored-Program Concept
Processor
memory for data, programs,
compilers, editors, etc.
Book
Text
Payroll
Account
C Compiler
Code
Editor
Program
Accounting
Program
Memory
Decision making instructions:
Computers have the ability to make decisions.
The next instruction to be executed depends on the
outcome of the decision.
Many programming languages use the if statement and/or
the goto statement to represent decision-making.
MIPS language uses conditional branch instructions
(branch if equal, branch if not equal):
(1) bne register1, register2, L1
- go to statement labeled L1 if value in register 1 does
not equal value in register 2
(2) beq register1, register2, L1
- go to statement labeled L1 if value in register 1 equals
value in register 2
Instructions for Decision-making
Example:
For the given C statement, assume that variables f through j
correspond to registers $s0 through $s4. What is the compiled
MIPS code?
if (i == j) goto L1;
f = g + h;
L1: f = f - i;

Solution:
Well need a branch if equal (beq) statement to correspond to
the if command:
beq $s3, $s4, L1
add $s0, $s1, $s2 # skipped if i==j

Now we just have to identify the code for the label L1. Consider, if the
conditional branch is true, then the add instruction is skipped. How do
we specify the label such that the last instruction is always executed?
Control Flow Examples
In stored-program computers, instructions are stored
in memory,
thus they are identified using memory addresses.
L1 will correspond to the address of the subtract
instruction.
L1: sub $s0, $s0, $s3
Complete solution:
C Code:
if (i == j) go to L1;
f = g + h;
L1: f = f - i;
MIPS assembly:
beq $s3, $s4, L1
add $s0, $s1, $s2
L1: sub $s0, $s0, $s3
Control Flow Examples
Example:
For the given C statement, assume that variables f
through j correspond to registers $s0 through $s4. What
is the compiled MIPS code?
if (i == j)
f = g + h;
else
f = g - h;
MIPS Code:
bne $s3, $s4, else
add $s0, $s1, $s2
j exit
else: sub $s0, $s1, $s2
exit:
Control Flow Examples
Unconditional Branch is
used; the machine always
takes (follows) this branch.
MIPS uses j for jump
to distinguish it from
conditional branches.
We can use MIPS unconditional branch instructions to
implement if-else statements, as well as for and while
loops using the format:

j label

Example:

if (i!=j) beq $s4, $s5, Lab1
h=i+j; add $s3, $s4, $s5
else j Lab2
h=i-j; Lab1: sub $s3, $s4, $s5
Lab2: ...


Unconditional Branches
ij
i=j
i=j
Example (while loop):
Write the MIPS assembly code for the following C code segment.
Assume that i, j, k correspond to $s3, $s4, $s5 and the base of the
array SAVE is contained in $s6.
while (save [i] = = k)
i = i + j;
Solution
loop: add $t1, $s3, $s3
add $t1, $t1, $t1
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, exit
add $s3, $s3, $s4
j loop
exit:


Unconditional Branches
We looked at beq, bne, and j what about other
conditional statements?

SLT: Set-on-less-than
Compares two registers, if first register is less than
second then it sets destination to 1, otherwise
destination register contains 0.

* We use this for case/switch statements.
2
Control Flow Examples
Arrays, byte addressing, alignment restriction
Machine language conventions
(big and little endian)
Instruction format types (R-type and I-type)
Stored program concept
Decision-making instructions, conditional and
unconditional branches

Next time: case/switch statements,
supporting procedures in computer hardware,
arrays versus pointers, etc

2
Summary
Recall from last time

Memory Organization
Machine Language
Instruction Formats
Decision-making Instructions; Control Flow
Conditional Branches
Today
Case/Switch statements using branches
Procedures
MIPS addressing modes
Arrays versus pointers


Case/Switch Statements
Case/Switch statements are used in many programming
languages to allow the user to select one of many choices.

It can be implemented as a sequence of if-then-else
statements.

We can also use a jump address table to encode
alternatives. The program will index the table and them
jump to the appropriate instruction sequence.

MIPS uses a jump register (jr) instruction to identify
the proper address of the jump table.
Case/Switch Statements
Example
Assume the variables f through k correspond to $s0 through $s5
and register $t2 contains 4. What is the associated MIPS code for
the following switch statement written in C?

switch (k) {
case 0: f = i + j; break: /* k = 0 */
case 1: f = g + h; break: /* k = 1 */
case 2: f = g - h; break: /* k = 2 */
case 3: f = i - j; break: /* k = 3 */
}

k is an index that contains the address of the instruction to be
executed.
Case/Switch Statements
Example cont
k should equal 0, 1, 2, or 3 to enter the jump address table, if it doesnt then it
should exit the switch command:

slt $t3, $s5, $zero # test if k < 0
bne $t3, $zero, Exit # Exit if k <0
slt $t3, $s5, $t2 # test if k > 4
beq $t3, $zero, Exit # Exit if k 4
Convert k to a byte address:
add $t1, $s5, $s5
add $t1, $t1, $t1 # $t1 = 4k offset
Assume that 4 sequential words in memory, starting at an address contained in
$t4, have addresses corresponding to the labels L0, L1, L2, and L3. Then we
load the proper jump address as
add $t1, $t1, $t4 # $t4 base address
lw $t0, 0($t1) # $t0 contains address of instr
jr $t0 # jump to address in reg $t0

Case/Switch Statements
Example cont
Next define the labels L0, L1, L2, and L3:

L0: add $s0, $s3, $s4
j Exit
L1: add $s0, $s1, $s2
j Exit
L2: sub $s0, $s1, $s2
j Exit
L3: sub $s0, $s3, $s4
Exit:





Case/Switch Statements
Complete Example
C Code:
switch (k) {
case 0: f = i + j; break: /* k = 0 */
case 1: f = g + h; break: /* k = 1 */
case 2: f = g - h; break: /* k = 2 */
case 3: f = i - j; break: /* k = 3 */
}

MIPS Assembly Code:
slt $t3, $s5, $zero # test if k < 0
bne $t3, $zero, Exit # Exit if k <0
slt $t3, $s5, $t2 # test if k < 4
beq $t3, $zero, Exit # Exit if k > 4
add $t1, $s5, $s5
add $t1, $t1, $t1 # $t1 = 4k offset
add $t1, $t1, $t4 # $t4 base address
lw $t0, 0($t1) # $t0 contains address of instr
jr $t0 # jump to address in reg $t0
L0: add $s0, $s3, $s4 # define instructions for Case 1
j Exit
L1: add $s0, $s1, $s2 # define instructions for Case 2
j Exit
L2: sub $s0, $s1, $s2 # define instructions for Case 3
j Exit
L3: sub $s0, $s3, $s4 # define instructions for Case 4
Exit: # End of statement
Supporting Procedures
A procedure is a tool that is used to structure programs to
make them easier to understand and to reuse.
There are 6 steps to be followed when executing a procedure:

1. Place parameters in a place where procedure can
access them;
2. Transfer control to the procedure;
3. Acquire the storage resources needed for the
procedure;
4. Perform the desired task;
5. Place the result in an accessible place;
6. Return control to the point of origin.
Supporting Procedures
MIPS allocates special registers for supporting procedures and
procedure calling:

$a0 - $a3 argument registers to pass parameters
$v0 - $v1 value registers to return values
$ra return address register to return to origin

Also, an instruction just for procedures is used jump-and-link
(jal) instruction; it jumps to an address and saves the address of
the following instruction in the $ra register.
jal ProcedureAddr

The link portion stores the return address in $ra:
Return addr = PC + 4
Program Counter
Procedures
Note:
- Procedure calls preserve registers $s0 - $s7 (saved registers) and erase
values stored in temporary registers $t0 - $t7.
- Nested procedures are also possible. All of the registers that are needed in
the caller program are pushed onto the stack.

Example:
Determine the MIPS assembly code for the following C code:

int leaf_example(int g, int h, int i, int j)

{
int f;
f = (g + h) (i + j);
return f;
}
Procedures
Recall MIPS Code for the statement:

f = (g + h) (i + j);


add $t0, $s1, $s2 # register $t0 contains g+h
add $t1, $s3, $s4 # register $t1 contains i+j
sub $s0, $t0, $t1 # register $s0 contains $t0-$t1= (g+h) (i+j);

Were going to create a subroutine around this operation. Since were passing
arguments, we must use argument registers $a0 - $a3 for the variables g through j.
Well use $s0 for variable f.

add $t0, $a0, $a1 # register $t0 contains g+h
add $t1, $a2, $a3 # register $t1 contains i+j
sub $s0, $t0, $t1 # register $s0 contains $t0-$t1= (g+h) (i+j);
Procedures
- Recall were using a LIFO structure/stack so we must store the values contained in
the $t0, $t1, $s0 registers initially:
sub $sp, $sp, 12
sw $t1, 8($sp)
sw $t0, 4($sp)
sw $s0, 0($sp)

Next we can load our code for our operation:
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1

The return value for f is copied to the return value register:
add $v0, $s0, $zero # returns f ($v0 = $s0 +0)

Restore old values in registers that we saved initially:
lw $t1, 8($sp)
lw $t0, 4($sp)
lw $s0, 0($sp)
add $sp, $sp, 12
Procedures
Finally we use a jump register instruction to go to the return address:
jr $ra




$sp
$sp
$sp
Contents of $t1
Contents of $t0
Contents of $s0
BEFORE Procedure Call DURING Procedure Call
AFTER Procedure Call
- The Stack Pointer always points to the top of the stack or the last word in the stack.
- Pushing registers onto stack ensures that the stack above $sp is preserved.
Procedures
Putting it all together

C Code:

int leaf_example(int g, int h, int i, int j)

{
int f;
f = (g + h) (i + j);
return f;
}







sub $sp, $sp, 12
sw $t1, 8($sp)
sw $t0, 4($sp)
sw $s0, 0($sp)
add $t0, $a0, $a1
add $t1, $a2, $a3
sub $s0, $t0, $t1
add $v0, $s0, $zero
lw $t1, 8($sp)
lw $t0, 4($sp)
lw $s0, 0($sp)
add $sp, $sp, 12
jr $ra

MIPS Assembly
Note:
- Since $t0 and $t1 are temporary registers and are not typically
preserved during a procedure call, we can drop the 2 stores and
2 load commands. What is the updated code? (on own)
Procedures
- The stack is used to store contents of registers as well as to store local variables that
are local to the procedure.

- The segment of the stack that contains the procedures saved registers and local
variables is called the register frame or activation record.

- A frame pointer ($fp) points to the first word of the frame of a procedure. It can be
used as a stable base register within a procedure to access local memory references.
Its use is optional.









$fp
$sp
Saved Arg regs
Saves Sve regs
Local arrays
and data
structures
BEFORE Procedure Call DURING Procedure Call AFTER Procedure Call
$sp
$fp
Saved rtn addr
$fp
$sp
Representing Text
- We process numbers, as well as, text using the American Standard Code
for Information Interchange (ASCII) character representation.

- Recall that ASCII characters are represented using 8 bits = 1 byte.

- MIPS instructions allows us to move bytes from words using load byte (lb)
loads a byte from memory and places it in rightmost 8 bits of a register;
and store byte (sb) takes a rightmost byte from register and places it into
memory.

- We can copy a byte with the following sequence:

lb $t0, 0($sp) # Read byte from source
sb $t0, 0($gp) # Write byte to a destination
Example
String Copy Procedure Example:

C Code:

void strcpy(char x[ ], char y[ ])
{
int i;
i = 0;
while ((x[i] = y[i]) != 0) /* copy and test byte */
i = i + 1;
}







strcpy:
sub $sp, $sp, 4
sw $s0, 0($sp)
add $s0,$zero,$zero
L1: add $t1, $a1, $s0
lb $t2, 0($t1)
add $t3, $a0, $s0
sb $t2, 0($t3)
beq $t2, $zero, L2
addi $s0, $s0, 1
j L1
L2: lw $s0, 0($sp)
add $sp, $sp, 4
jr $ra

MIPS Assembly
Assume base addresses for x and y are
found in $a0 and $a1 and i is in $s0.

Note also that x and y are arrays of
characters so there is no need to multiply
by 4 to obtain the address.
Constants
Small constants are used quite frequently (50% of operands)
e.g. A = A + 5;
B = B + 1;
C = C - 18;

Solutions? Why not?
- put 'typical constants' in memory and load them (takes time!).
- create hard-wired registers (like $zero) for constants like one.
- Encode constant in instruction (I-type formats)
- Some immediate MIPS Instructions (addi, slti, andi, ori, lui).

This leads to design principle #4:
Make the common case fast!!


Procedures
In summary:
- Call a procedure by first putting parameters in $a0-$a3
- Use jal to jump to procedure
- Perform calculations within procedure
- Place results in $v0-$v1
- Return control to caller program by using jr $ra

If we need more registers to hold parameters we can use
spilling to accomplish this.
The ideal structure for spilling registers is called a stack (last-
in-first-out queue). A stack pointer ($sp) is used to index the
most recently allocated address on the stack.
Data placed onto stack Push
Data removed from stack Pop
We'd like to be able to load a 32 bit constant into a register
Must use two instructions, new "load upper immediate" instruction

lui $t0, 1010101010101010



Then must get the lower order bits right, i.e.,
ori $t0, $t0, 1010101010101010
1010101010101010 0000000000000000
0000000000000000 1010101010101010
1010101010101010 1010101010101010
ori
1010101010101010 0000000000000000
filled with zeros
Larger Constants
$t0
Example:
Determine the sequence of MIPS instructions for the following C segment
x[10] = x[11] + c;
Assuming that c is contained in $t0 and that array x has a base address of


First load base address into a register:

Larger Constants
10
) 000 , 000 , 4 (
2
16 10
) 0000 0000 1001 0000 1101 0011 0000 0000 (
) 0900 003 ( ) 000 , 000 , 4 (

D
lui $t1, $t1, 0000 0000 0011 1101 # load upper 16 bits
ori $t1, $t1, 0000 1001 0000 0000 # load lower 16 bits using OR imm
lw $t2, 44($t1) # load element x[11] into $t2
add $t2, $t2, $t0 # sum x[11] and c; put result in $t2
sw $t2, 40($t1) # store it back into memory


Solution:
On own: Write MIPS assembly that loads 32-bit word into register $t5:
0000 0000 0011 1101 0000 1001 0000 0000
Assembly provides convenient symbolic representation specific to a
particular architecture
This is much easier than writing down sequences of binary
numbers (machine code) which is the communication mechanism
of a machine.
Assembly can also provide 'pseudoinstructions (instructions that
are not actually implemented in hardware but make assembly
coding easier for the programmer).
e.g., move $t0, $t1 exists only in assembly
would be implemented using add $t0,$t1,$zero in MIPS
However, when considering performance you should count real
instructions that will be implemented in hardware.

Assembly Language vs Machine Language
Recall

Procedure Example
Character representations
Constants and Immediate

This time
Addressing in branches and jumps
MIPS addressing modes
Arrays versus pointers
Examples of other architectures


MIPS jump instructions have the simplest addressing:
j 10000 # go to location 10000
J-type Format:




Conditional Branches Instructions:
bne $s0, $s1, Exit # goto exit if $s0 $s1
Addressing in Branches and Jumps
2 2500
op
(6 bits)
location
(26 bits)
Address: 16 bits rt: 5bits rs: 5bits op: 6bits
I-type format:
Left-shifted by 2
(multiplied by 4)
before use
Most conditional branches are local meaning they
tend to branch to nearby locations (principle of
locality). Examples would be if-else statements. In
this case,
Program Counter (PC) = register + branch address
(PC-relative addressing)
For jump and jump-and-link instructions which
execute procedures, far away branching is more
common. These instructions use j-type format.
Consider the following: beq $s0, $s1, Label1
Replace this expression with a sequence of instructions that
allows greater branching distance.
Replace with bne $s0, $s1, L2
j L1
L2:
Addressing in Branches and Jumps
Example
Assume that the following while loop is placed starting at
memory location 80000, what is the MIPS machine code for this
segment?
loop: add $t1, $s3, $s3
add $t1, $t1, $t1
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
add $s3, $s3, $s4
j loop:
Exit:

Addressing in Branches and Jumps
0 19 19 9 0 32
80000
80008
80012
80016
80020
80024
0 9 9 9 0 32
80004
80028
0
. . .
9 22 9 0 32
35
9 8 0
5 8 21 8
0 19 20 19 0 32
2 20000
MIPS Machine Code
Note: bne instruction adds 8 bytes to the following instruction
which corresponds to 80020 + 8 = 80028 (addr of exit)
(PC-relative Addressing)
In summary:
MIPS operands
Name Example Comments
$s0-$s7, $t0-$t9, $zero,
Fast locations for data. In MIPS, data must be in registers to perform
32 registers
$a0-$a3, $v0-$v1, $gp,
arithmetic. MIPS register $zero always equals 0. Register $at is
$fp, $sp, $ra, $at
reserved for the assembler to handle large constants.
Memory[0], Accessed only by data transfer instructions. MIPS uses byte addresses, so
2
30
memory Memory[4], ..., sequential words differ by 4. Memory holds data structures, such as arrays,
words Memory[4294967292] and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Category Instruction Example Meaning Comments
add
add $s1, $s2, $s3 $s1 = $s2 + $s3
Three operands; data in registers
Arithmetic
subtract
sub $s1, $s2, $s3 $s1 = $s2 - $s3
Three operands; data in registers
add immediate
addi $s1, $s2, 100 $s1 = $s2 + 100
Used to add constants
load word
lw $s1, 100($s2) $s1 =
Memory[
$s2
+ 100] Word from memory to register
store word
sw $s1, 100($s2)
Memory[
$s2
+ 100] = $s1 Word from register to memory
Data transfer load byte
lb $s1, 100($s2) $s1 =
Memory[
$s2
+ 100] Byte from memory to register
store byte
sb $s1, 100($s2)
Memory[
$s2
+ 100] = $s1 Byte from register to memory
load upper immediate
lui $s1, 100
$s1 = 100 * 2
16
Loads constant in upper 16 bits
branch on equal
beq $s1, $s2, 25
if (
$s1 == $s2
) go to
PC + 4 + 100
Equal test; PC-relative branch
Conditional
branch on not equal
bne $s1, $s2, 25
if (
$s1 != $s2
) go to
PC + 4 + 100
Not equal test; PC-relative
branch set on less than
slt $s1, $s2, $s3
if (
$s2 < $s3
)
$s1
= 1;
else
$s1
= 0
Compare less than; for beq, bne
set less than
immediate
slti $s1, $s2, 100
if (
$s2 < 100
)
$s1
= 1;
else
$s1
= 0
Compare less than constant
jump
j 2500
go to 10000 Jump to target address
Uncondi- jump register
jr $ra
go to
$ra
For switch, procedure return
tional jump jump and link
jal 2500 $ra
= PC + 4; go to 10000 For procedure call
MIPS Addressing Modes
Different modes of addressing are used to implement different
types of instructions. MIPS addressing modes are as follows:

Immediate addressing:
operand is a constant within the instruction itself (e.g. addi)
Register addressing:
operand is a register (e.g. add)
Base or displacement addressing:
operand is at the memory location whose address is the sum of a
register and a constant in the instruction (e.g. lw)
PC-relative addressing:
address is the sum of of the PC and the constant in the instruction
(e.g. branches)
Pseudodirect addressing:
jump address is the 26bits of the instruction concatenated with the
upper bits of the PC

Byte Halfword Word
Registers
Memory
Memory
Word
Memory
Word
Register
Register
1. Immediate addressing
2. Register addressing
3. Base addressing
4. PC-relative addressing
5. Pseudodirect addressing
op rs rt
op rs rt
op rs rt
op
op
rs rt
Address
Address
Address
rd . . . funct
Immediate
PC
PC
+
+ (+4)
<<2



Decoding Machine Code
Example
What is the assembly language corresponding to this machine
code?
0000 0000 1010 1111 1000 0000 0010 0000

First consider the opcode field:
op: 000000 several different arithmetic codes
Next look at function code field:
func: 100000 this corresponds to the add instruction
Now reformat machine instruction using R-type format:
(op) (rs) (rt) (rd) (shamt) (func)
binary 000000 00101 01111 10000 00000 100000
decimal 0 5 15 16 0 32

The MIPS assembly instruction is

add $s0, $a1, $t7





Arrays versus Pointers
Example
What is the assembly language for the following C procedures:

clear1(int array[ ],int size)
{
int i;
for (i=0; i<size; i=i+1)
array[i] = 0;
}

clear2(int *array,int size)
{
int *p;
for (p=&array[0]; p<&array[size]; p=p+1)
*p = 0;
}


Array Version
Pointer Version



Arrays versus Pointers
Example cont.









move $t0, $zero
Loop1: add $t1, $t0, $t0
add $t1, $t1, $t1
add $t2, $a0, $t1
sw $zero, 0($t2)
addi $t0, $t0, 1
slt $t3, $t0, $a1
bne $t3, $zero, loop1

move $t0, $a0
add $t1, $a1, $a1
add $t1, $t1, $t1
add $t2, $a0, $t1
Loop2: sw $zero, 0($t0)
addi $t0, $t0, 4
slt $t3, $t0, $t2
bne $t3, $zero, loop2

Array Version of Clear: Pointer Version of Clear:
Design alternative:
provide more powerful operations and flexibility in
designs
goal is to reduce number of instructions executed
danger is a slower cycle time and/or a higher CPI

Example architectures: PowerPC and Intel
80x86

Refer to your textbook for more information
on these architectures.
Alternate Architectures
Instruction complexity is only one
variable
lower instruction count vs. higher CPI / lower
clock rate
Design Principles:
simplicity favors regularity
smaller is faster
good design demands compromise
make the common case fast
Instruction set architecture
a very important abstraction
Summary