COMP273 McGill
1
Binary Representations + Introduction to MIPS
• High-level language program (in C) swap (int v[], int k) {
int temp = v[k]; v[k] = v[k+1]; v[k+1] = temp;
}
• Assembly language program (for MIPS) swap: sll $2, $5, 2 add $2, $4,$2
C compiler
The Big Picture
lw $15, lw $16, sw $16, sw $15, jr $31
0($2)
4($2)
0($2)
4($2)
assembler
• Machine (object) code (for MIPS)
000000 00000 00101 0001000010000000 000000 00100 00010 0001000000100000
…
Agenda
• BinaryRepresentations
– How to represent characters?
– What can go wrong in binary representations?
• MIPS
– Registers
– Addition/subtractions – Memory access
How to Represent Characters?
Character Data Codes
Name
bits per symbol
# of symbols
Comments
IBM-BCD
6
64
Capital letters: A-Z, 0-9, $, etc.
Not to confuse with Packed Decimal.
ASCII
7
128
All letters: a-z, A-Z, 0-9, $, BEL, TAB, etc. See link below.
USACII
8
256
Includes parity (even).
EBCDIC
8
256
On IBM mainframes (odd parity)
UNICODE
16
65,536
Can represent the letters of all languages.
ASCII
American Standard Code for Information Interchange
UNICODE
The Martian
An astronaut is stranded on Mars. The communication devices are broken. Only one camera is working but no sound. How can he communicate with the Earth?
48 4F 57 41 4C 49 56 45? What was the Earth trying to say?
48 4F 57 41 4C 49 56 45?
How do we represent an Array
int arr[8]={56,26,88,45,-45,77,98,13} ;
Memory Address
Memory is a linear array of byte
Each byte in the memory has its own unique address
We can access the content by supplying the memory address
The processor can read or write the content of the memory
COMP273 McGill
13
Memory Address
16-bit address example
// An array of 8 integers in C/Java
int arr[8]={56,26,88,45,-45,77,98,13} ;
The variable arr holds the address of the first element arr: 0x1000.
arr[0]: content in address 0x1000 arr[1]: content in address 0x1004
COMP273 McGill
14
What can go wrong in binary representations?
•
Overflow / Underflow
We use a fixed # of bits to represent numbers!
– Largest number that can be represented in unsigned integer: 2^32-1 – Largest number that can be represented in signed integer: 2^31 – 1
– Largest number that can be represented in single precision: ~2.0x 2127
• Overflow: representing a number larger than the one above • Underflow: representing a number smaller than the smallest
values
e.g., int a = 123123127467634282098343726423 ;
Arithmetic Overflow/Underflow
• Arithmeticoverflowcanoccurduringcalculations
• Example: Represent 6_10 + 5_10 as 4-bit signed integer
Loss of Precision
017 220.2
https://imgur.com/r/totallynotrobots /ls Nc v
Assembly Languages
What is an Assembly Language • Assemblylanguage:directlysupportedinhardware
• The language is kept very simple!
– Limit on the type of operands
– Limit the set of operations to absolute minimum
COMP273 McGill 20
The MIPS and the MARS
E
MIPS Technology
MARS: Free MIPS Simulator
How do I learn MIPS assembly?
• Microprocessor without Interlocked Pipelined Stages (MIPS) • Used MIPS32 as the example in this course (Quickguide)
• Download the software
• Run the software java –jar pMARS.jar
• Try it out with MARS!
COMP273 McGill
21
Where can we store data?
• Disk: large space, but slow (250, 500GB)
• RAM: Relatively smaller than a disk (8, 16, 32GB)
• Register File: inside CPU, limited numbers, superfast
COMP273 McGill
22
Register File
COMP273 McGill
23
Good
Register file is small and inside of the core, so they are very fast
Bad
Since registers are implemented in the hardware, there are a predetermined number of them
• MIPS has a register file of 32 registers
• Why 32? Smaller is faster
• Each MIPS register is 32 bits = 4 bytes = a word
erasec aides
Assembly Variables: Registers
C and Java
• Operands are variables and
constants
• Declareasmanyasyouwant
MIPS
• Operands are registers
• Limited number built directly into the hardware
COMP273 McGill
24
Why? Keep the Hardware Simple!
Assembly Variables: Registers
• Registers are numbered from 0 to 31
$0, $1, $2, … $30, $31
• Each register also has a name to make it easier to code: $0 —> $zero
$16 – $23 —-> $s0 – $s7
• We will use $s0-$s7 for now.
• In general, use register names to make your code more readable
COMP273 McGill 25
Comments Assembly code is hard to read!
Another way to make your code more readable: comments!
C and Java
/* comment can span many lines */ // comment, to the end of a line
MIPS
# Anything from hash mark to end
o
of line is a comment and will be ignored
COMP273 McGill 26
Assembly Instructions
C and Java
Each statement could represent multiple operations
a=b+c-d;
Is equivalent to two small operations
a=b+c; a=a–d;
MIPS
Each statement
(called an Instruction), executes exactly one of a short list of simple commands
COMP273 McGill
27
MIPS Syntax
• Syntax of Instructions:
Operation Destination,Source1,Source2 Operation: by name (Mnemonic)
Destination: operand getting result
Source1: 1st operand for operation
Source2: 2nd operand for operation
• Syntax is rigid:
– Most of them use 1 operator + 3 operands (commas are optional) – Why? Keep Hardware simple via regularity
COMP273 McGill 28
High-level v.s. Assembly Languages
Operators: +, -, *, /, % ;
• 7/4==1, 7%4==3
Operands:
• Variables: a, b, c
• Constants: 0, 1000, -17, 15.4
Statement:
• Variable = Expression • Int a = b+c+d-e;
Operators: +, -, *, /, % ;
• Instructions
Operands:
• Registers
Statement:
• operation destination, source1, source2
COMP273 McGill
29
Addition and Subtraction
30
Addition and Subtraction
Addition
Try with Mars
// C and Java
a=b+c;
# MIPS
add $s0 $s1 $s2
registers $s0,$s1,$s2 are associated with variables a, b, c Subtraction
sis
// C and Java # MIPS
d = e – f ; sub $s3,$s4,$s5 registers $s3,$s4,$s5 are associated with variables d, e, f
COMP273 McGill
31
Addition and Subtraction
Each Instruction, executes exactly one simple commands
MIPS
add $s0, $s1, $s2 #a=b+c
add $s0, $s0, $s3 #a=a+d
sub $s0, $s0, $s4 #a=a-e
C and Java
a = b + c + d – e;
COMP273 McGill
32
Break into
multiple instructions
A single line of C may break up into several lines of MIPS.
Immediates
• Immediatesarenumericalconstants.
adding
• Syntax is similar to add instruction, except that last argument
is a number (decimal or hexadecimal) instead of a register.
• Specialinstructionsforimmediates:addi
constants
// C and Java
f = g + 10 ;
# MIPS
addi $s0 $s1 10 addi $s0 $s1 -10
• There is no subi (use a negative immediate instead)
COMP273 McGill 33
Register Zero
not
• The number zero appears very often in code. • Use this register, it’s very handy!
o
• MIPSdefinesregisterzero($0or$zero)alwaysbe0. Or
regentered
add $6$0$5 #copy$5to$6 addi $6 $0 77 # copy 77 to $6
lo gageo co g to • Register zero cannot be overwritten
cento z operations
addi $0 $0 5 # will do nothing
COMP273 McGill
34
Register Zero • What if you want to negate a number?
sub $6 $0 $5 # $6 = 0 – $5
COMP273 McGill 35
Data Transfer Instructions
36
Data Transfer Instructions
• MIPSarithmeticinstructionsonlyoperateonRegisters • What do we do if we need more? Memory!
– Add two numbers in memory (indirectly) • Load values from memory into registers
• Add two numbers
• Store result from register to memory
• UseDatatransferinstructionstotransferdatabetween registers and memory. We need to specify
– Register: specify this by number (0 – 31)
– Memory address: more difficult
COMP273 McGill 37
Memory Address
Memory is a linear array of byte
Each byte in the memory has its own unique address
We can access the content by supplying the memory address
The processor can read or write the content of the memory
COMP273 McGill
38
Memory Address
• MemoryAddressSyntax:Offset(AddrReg)
– AddrReg: A register which contains a pointer to a memory location – Offset: A numerical offset in bytes (optional)
8($t0)
# specifies the memory address in $t0 plus 8 bytes
• We might access a location with an offset from a base pointer • The resulting memory address is the sum of these two values
COMP273 McGill 39
Memory Address
16-bit address example
// An array of 8 integers in C/Java
int arr[8]={56,26,88,45,-45,77,98,13} ;
# Assume $s0 has the address 0x1000
0($s0) # 0x1000, to access arr[0] 4($s0) # 0x1004, to access arr[1]
COMP273 McGill
40
Data Transfer: Memory to Register
• Load Instruction Syntax: lw DstReg, Offset(AddrReg) – lw: Load a Word
– DstReg: register that will receive value
– Offset: numerical offset in bytes
– AddrReg: register containing pointer to memory
lw $t0, 8($s0)
# load one word from memory at
address stored in $s0 with an offset 8 and store the content in $t0
COMP273 McGill 41
Data Transfer: Register to Memory
• Storeinstructionsyntax:swDataReg,Offset(AddrReg) – sw: Store a word
– DstReg: register containing the data
– Offset: numerical offset in bytes
– AddrReg: register containing memory
sw $t0, 4($s0)
# Store one word (32 bits) to memory address $s0 + 4
COMP273 McGill 42
Byte vs. word
• Machines address memory as bytes
• Both lw and sw access one word at a time
• The sum of the base address and
the offset must be a multiple of 4 (to be word aligned)
sw $t0, 0($s0)
sw $t0, 4($s0)
sw $t0, 8($s0)
. .
COMP273 McGill 43
Byte vs. word
Index 8 requires offset of 32 Index 12 reuqires offset of 48
Try with Mars
// C and Java
A[12] = h + A[8] ;
# MIPS 5 is the base address # assume h is stored in $s0 and the base address of A is in $s1ofA lw $s2 32($ys1) # load A[8] to $s2
add $s3 $s0, $s2 # $s3 = $s0 + $s2
sw $s3 48($s1) # store result to A[12]
COMP273 McGill
44
Register vs. Memory
Operations with registers are faster than memory
Why not keep all variables in memory?
What if more variables than registers?
• MIPS arithmetic instructions can read 2 registers, operate on them, and write 1 per instruction
• MIPS data transfer only read or write 1 operand per instruction, and no operation
• Smaller is faster
COMP273 McGill
45
• Compiler tries to keep most frequently used variable in registers • Writing less common to memory: spilling
Pointers vs. Values
• A register can hold any 32-bit value. – a (signed) int,
–anunsigned int,
–a pointer (memory address), – etc.
lw $t2, 0($t0) # $t0 must contain?
add $t3, $t4, $t5 # what can you say about $t4 and $t5?
COMP273 McGill 46
Review and Information
Registers:
• The variables in assembly
Instructions:
• Addition and Subtraction: add, addi, sub • Data Transfer: lw, sw
References
• Intro-to-mips.pdf • mips-arrays.pdf
COMP273 McGill
47