Von Neumann and MIPS
Quiz 2 next Monday
• Date: May 10th
• Exact format as Quiz 1
• Syllabus: lec 7 – lec 17 as covered in class lecture session
• After this we will have midterm
• Then we will have 1 to 2 more quizzes before final exam
MIPS Overview – Commands
MIPS instructions can be broken down into 3 categories:
■ Data Movement
◆ Move data between memory and registers ★ For example: lw is load word, sw is store word
■ Operate
◆ Manipulate data directly
★ For example: add is addition, xor is logical ■
★
Control
Change the sequence of instruction execution
For example: b is branch, jal is jump and link, ret is return
◆
Program Flow
■ Branches change the flow of instructions
◆ Default is to execute the next instruction
◆ If the condition is met it will execute the instruction at a label
Conditional Branch (1)
■ Compares two registers ◆ Branch Equal (BEQ)
◆ Branch Not Equal (BNE)
■ Often used to “skip over” some instructions
■ Example:
◆ BEQ $t0, $t1, label
★ If $t0 == $t1, execute instruction at label next ★ Otherwise, execute instruction after BEQ
Branch Example
Only 2 command executed:
beq
addi $t3, $0, 3
Notice blah_label get translated to 0x2….
Time for a class poll…
■ ■ ■
Conditional Branch (2)
■ Considers only a single register for comparison and compares implicitly with zero
◆ Branch Greater than or Equal to Zero (BGEZ) ◆ Branch Greater than Zero (BGTZ)
◆ Branch Less than or Equal to Zero (BLEZ)
◆ Branch Less than Zero (BLTZ)
■ Example:
◆ BGTZ $t0, label
◆ If $t0>0, execute instruction at label next ◆ Otherwise, execute instruction after BGTZ
Program Control Flow
■ You can conditionally execute sections of code using BEQ and B
■ Why do you need the B?
BEQ $t0, $t1, true_condition
false_condition:
# statements
B end_condition
true_condition:
# statements
end_condition:
# after branch
Program Control Flow
.text main:
li $v0,4
li $t1, 10
li $t2, 4
# Define the program instructions.
# Label to define the main program.
# Load 4 into $v0 to indicate a
# print string.
condition_NOT_met:
condition_met:
exit:
.data
greeting:
.asciiz “Hello World”
bye:
.asciiz “Bye!”
la $a0, bye
syscall
beq $t0,$t0, exit la $a0, greeting syscall
li $v0, 10 syscall
# Load the address of the greeting
# into $a0.
# Print greeting. The print is
# indicated by $v0 having a value
# of 4, and the string to print
# is stored at the address in $a0.
# Load a 10 (halt) into $v0.
# The program ends.
sub $t1, $t1, $t2
bgtz $t1, condition_met
# Define the program data.
#The string to print (null terminated!).
#The string to print (null terminated!).
Branching in a Loop
Tru e
False
init:
li $t0, 0
loop_start:
beq $t0, 10, loop_end
loop_body:
move $a0, $t0
li $v0, 1
syscall update:
addi $t0, $t0, 1
b loop_start loop_end:
nop
Iterating over a String
.text: init:
la $t0, hello_string loop_start:
lb $t2, ($t0)
beq $t2, $zero, loop_end loop_body:
move $a0, $t2 li $v0, 11
update: syscall
addi $t0, $t0, 1
b loop_start loop_end:
nop .data
hello_string:
.asciiz “Hello World!”
Jumps vs Branches
■ Jump command takes you to the specified label
■ Jumps, however, do not do any comparisons (they are unconditional)
Jump region (J)
■
Address
8000 8004
……… ……… 12000
Instruction
J 12000;
Add $t4,$t4,$t5;
Addi $t5, $t3, 10;
J can jump to a label that is within the current region
◆ Main reason for having a separate Jump instruction instead of simply writing:
beq $0, $0, jump_label?
◆ Reason: separate jump instruction allows us to jump much farther than branch encoding.
Will be discussed more in advanced course CSE120; no need to worry about it now!
Jump Example
Only 2 command executed:
j blah_label addi $t3, $0, 3
■ ■
:
Jump Register (JR)
■ JR uses the instruction address in a register ◆ Example: JR $t0
◆ Full 32-bit address in register
■ JR instruction returns control to the caller. It copies the contents of $t0 into the PC (program counter), that keeps track of which instruction computer is currently executing
■ Usually you think of this as “jumping to the address contained in $t0.”
Address Instruction
8000 Addi $t2, 12000 8004 Jr $t2
………
………
12000 Addi $t5, $t3, 10
Jumping (and Linking) : JAL
■ Some jumps can store the address of the following instruction
◆ Why?….WritingFunctions(willdiscussmoreinlaterslides!)
■ This is known as “linking”
◆ SimilarbehaviortoJexceptnextaddress(PC+4)isautomatically
remembered in $ra (return address) ($r31) register
Address Instruction
8000 Jal 12000; // PC=8000, therefore ($ra)=PC+4 = 8004 8004 Add $t4, $t4,$t3;
………
………
12000 Addi $t5, $t3, 10 12004 Jr $ra
Jump and Link Example in MARS
Data Layout
Where does the data come from?
■ Data is arranged in memory
■ Data can be initialized when a program starts (.data)
◆ Must be stored in the program with the instructions ■ Data may be not-initialized (or actually just zeroed) (.bss) ◆ This doesn’t need to be stored in the program itself
■ Data may be created during execution ◆ More later in the course!
Code and Data Addresses
■ The code (text) segment starts at 0x0040_0000
◆ Each instruction is 4 bytes ■ The data segment starts at
0x1001_0000
◆ Data is placed at next adjacent location
■ Both grow “up”
■ What is the limit of my program
size?
■ What is the limit of my data size?
Data Declarations
.data
var1: .word 3
# All of this will go in the “data” segment of memory # create a single integer variable with initial value 3
# create a 2-element character array
# initialized to ASCII a and b
array1: .byte ‘a’,’b’
half1: .half 0x1234 # create 16-bit word
array2: .space 40 # allocate 40 consecutive bytes, with storage # uninitialized
string1: .asciiz “Hello!\n” # string variable with end null string2: .ascii “Hello!\n” # string variable with NO end null
Data Segment Layout (Packing)
■ Memory is arranged least significant byte first ◆ .align directive can force alignment
.data
var1: .word 3 array1: .byte ’a’,’b’
half1: .half 0x1234 string1:.asciiz “Hello!\n”
Address
0x1001_0000
0x1001_0001
0x1001_0002
0x1001_0003
0x1001_0004
0x1001_0005
0x1001_0006
0x1001_0007
0x1001_0008
0x1001_0009
0x1001_000A
0x1001_000B
0x1001_000C
0x1001_000D
0x1001_000E
0x1001_000F
Value
03
00
00
00
a
b
34
12
H
e
l
l
o
!
\n
00
Computing Data Addresses
.data
var1: .word 3 array1: .byte ’a’,’b’
half1:
.half 0x1234
■ If data segment starts at 0x1001_0000… ◆ Whatisvar1?
◆ Whatisarray1? ◆ Whatishalf1?
Label
Address
Value
var1
0x1001_0000
03
0x1001_0001
00
0x1001_0002
00
0x1001_0003
00
array1
0x1001_0004
61 (a)
0x1001_0005
62 (b)
half1
0x1001_0006
34
0x1001_0007
12
Spaces or new lines don’t matter!
Arrays
■ Arrays are a sequence of identical elements
◆ Elementscanbeanysize:byte,half word, word, or bigger
◆ Stringsareanarrayofcharacters ■ Remember iterating over a sequence
Iterating over a String (Array of
Characters)
.text: init:
la $t0, hello_string
loop_start:
lb $t2, ($t0)
beq $t2, 0, loop_end
loop_body:
move $a0, $t2
li $v0, 11
syscall update:
addi $t0, $t0, 1
b loop_start
loop_end:
nop .data
hello_string:
.asciiz “Hello World!”
Array of Integers (4 bytes)
.data
list:
.word 3, 0, 1, 2, 6, -2, 7, 3, 7
Address
Value
0x1001_0000
03
0x1001_0001
00
0x1001_0002
00
0x1001_0003
00
0x1001_0004
00
0x1001_0005
00
0x1001_0006
00
0x1001_0007
00
0x1001_0008
01
0x1001_0009
00
0x1001_000A
00
0x1001_000B
00
0x1001_000C
02
0x1001_000D
00
0x1001_000E
00
0x1001_000F
00
………..
……..
.text
la $t3, list
li $t2, 3
sll $t2, $t2, 2
add $t1, $t2, $t3
#address
lw $t4, 0($t1)
# put address of list into $t3
# put the index into $t2
# Multiple index by 4 (1 word is 4 bytes)
# combine the two parts of the
# get the value from the array cell