Von Neumann and MIPS
• I Cannot help you unless you help yourselves be attentive to Piazza posts to some extent! There is too much information in this course that simply cannot be just addressed in lectures alone.
PLEASE be understanding of this!!
• Many instructors make lecture attendance mandatory! (part of final grade)
• Many instructors enforce ProctorU during exams
• I am not enforcing the above two rules to help you feel more comfortable with CSE12. I thereby expect in return you pay more attention to the concepts
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
Data-Movement: Load Instructions
■ Move data from memory to a register Data transfer
Register
Memory
4
Endianness: Memory aid for exams
Lol
Least significant byte of data occupies lower address position in memory!
Most significant byte of data occupies lower address position in memory!
Little Endians
Big Endians
Base addressing
■ lw $t1, ($t2)
◆ $t2 contains a 32-bit address ◆ Effective address is $t2
◆ ($t1) = memory[$t2]
■ NOTE: lw $t1, $t2 is not valid syntax! Example:
Assume four 32-bit registers, Little Endian ordering in memory Reg0
Memory address
0x10
0xA0
0x09 10
0x00 11
0x99
0xA5
0x54 14 0xFD 15 0x29 16 0xA5 17 0x01 18 0xFF 19
1210
Reg1 Reg2
Reg3
lw Reg1, (Reg2);
(Reg1)=?
(Reg1)= 0x FD 54 A5 99
8
9
12
13
Base + offset addressing
■ lw $t1, 4($t2)
◆ $t2containsa32-bitaddress
◆ Instructioncontains16-bitimmediateoffset(4) ◆ Effectiveaddressis$t2+4
◆ $t1=memory[$t2+4]
■ NOTE: lw $t1, 0($t2) is the same as indirect addressing!
■ Immediate offset is 16-bit *signed* and we can load adjacent words:
◆ lw$t1,-4($t2) ◆ lw$t2,0($t2) ◆ lw$t3,4($t2)
Base addressing
Example:
Assume four 32-bit registers, Little Endian ordering in memory, byte addressable (always implicit if not mentioned)
Reg0
Reg1 Reg2
Reg3
Memory
address
8
9 10
11
12
13 14
15 16
17 18
19
0x10
0xA0
0x09
0x00
0x99
0xA5
0x54
0xFD
0x29
0xA5
0x01
0xFF
1210
Problem 1:
lw Reg1, 0(Reg2);
(Reg1)=?
(Reg1)= 0x FD 54 A5 99
Problem 2:
lw Reg1, 4(Reg2);
(Reg1)=?
(Reg1)= 0x FF 01 A5 29
Problem 3:
lw Reg1, -4(Reg2);
(Reg1)=?
(Reg1)= 0x 00 09 A0 10
Load data sizes
■ Words are 32-bit values
◆ Load word (lw)
◆ Samesizeastheregisters ◆ Samesizeastheaddresses
■ Half-Words
◆ Load half word (lh)
◆ Are 16-bit values
◆ Samesizeastheimmediatevalues
■ Bytes
◆ Load byte (lb) ◆ Are 8-bit values
Data sizes (cont’d)
■ Where are half word and bytes placed? ◆ Half word is put in lower register bits [15:0] ◆ Byte is put in lower register byte [7:0]
■ What about the other bits?
◆ Half word
★ LH fills upper bits [31:16] with sign ★ LHU fillers upper bits [31:16] with 0
◆ Byte
★ LB fills upper bits [31:8] with sign ★ LBU fillers upper bits [31:8] with 0
Data-Movement: Store Instructions ■ Move data from memory to a register
11
Register
Data transfer
Memory
Data-Movement: Stores
■ Stores are similar to loads…
◆ Address modes are the same.
◆ Data sizes are the same.
★ Upper bits are ignored for byte and half word writes
◆ Except… register contents are put in memory. ★ sw $t1, 4($t2)
★ Memory[$t2+4] = ($t1)
Base addressing
■ sw $t1, ($t2)
◆ $t2 contains a 32-bit address ◆ Effective address is $t2
◆ memory[$t2] = ($t1)
■ NOTE: sw $t1, $t2 is not valid syntax! Example:
Memory address 8
9 10
11
12
BA 13
FE 14
CA 15 16
17 18
19
Assume four 32-bit registers, Little Endian ordering in memory Reg0
0xCAFEBABE Reg1
sw Reg1, (Reg2); Mem[Reg2]=?
Mem[Reg2]= 0x CA FE BA BE
1210
Reg2 Reg3
BE
Summary of Loads/Stores
Use the GREEN!
Don’t use Grey!
MIPS Overview – Pseudo Instructions
• 2 such instructions covered so far in lab3: li, la
• Li : load an integer value directly into the register example: li $t0, -14
This gives us ($t0) = -14
equivalent to int x= -14 ; in C/C++
• La : Load the address of a string that you want printed don output terminal example:
.data
greeting: .asciiz “Hello World“ # greeting is a label which points to an address in main
#memory that stores the string “Hello World” .text # Define the program instructions.
li $v0,4 # Load 4 into $v0 to indicate a print string.
la $a0, greeting # Load the address of the greeting into $a0.
syscall
• In above example, if “Hello World”is stored at address 0x1001 0000, then ($a0)= 0x1001 0000
• Li and la are Pseudo instructions because they are not actual legitimate MIPS instructions. They are “shortcut” instructions made by doing many actual MIPS instructions under the hood
System Call (syscall)
■ Calls special system code to do things like… ◆ Input from keyboard
◆ Output to screen ◆ Exit program
■ Code for system call is in register $v0
■ Arguments are (if needed) in $a0 and $a1
Hello World!
.text
main:
li $v0,4
la $a0, greeting
syscall
li $v0, 10
syscall
.data
greeting:
.asciiz “Hello World”
terminated!).
# Define the program instructions.
# Label to define the main program.
# Load 4 into $v0 to indicate a
# print string.
# 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.
# Define the program data.
#The string to print (null
Prog1.asm (in Lab3 folder)
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
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
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
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!”
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
array1: .byte ‘a’,’b’
# 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
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