computer and organisation and architecture (GC230) {assemble language}

GC312 Homework1. Consider a small direct-mapped cache with 256 blocks, cache is initially
empty, Block size = 256 bytes. The following memory addresses are
referenced: 0x01FFF8AC, 0x01EFF8AA, 0x01EFF8AC, 0x01AFF88C,
0x01AFF8BC, 0x01AFF8B7.
– Divide the address to offset, index, tag
– Map the addresses to cache blocks and indicate whether the block is hit
or miss and if miss explain why
2. Write a complete assembly program that read tow integer from the user
and compare it. If equal, print equal. Otherwise, print not equal.
GC230 – Computer
Organization & Architecture
L2: Introduction to Assembly Language
2
Outlines
´ The MIPS Instruction Set Architecture
´ Introduction to Assembly Language
´ Defining data
´ Memory Alignment and Byte Ordering
´ System Calls
GC230_1442(2)
3
Instructional set Architecture (ISA)
´ It is a critical interface between the software and the hardware.
´ ISA includes:
´ Instructions and its formats
´ Data types, encodings and representations
´ Programmable storage: resigters and memory
´ Addressing modes to address instructions and data
´ Handling exceptional conditions (e.g., overflow)
Example
Version
Year
Intel
8086, 80386, Pentium, Core,..
1978
MIPS
MIPS I, II, …., MIPS32, MIPS64
1986
ARM
Version 1, 2, …
1985
GC230_1442(2)
4
The edit-assemblelink-run cycle
´ Assemble: translate the MIPS assembly
language code into a binary object file.
This is done by the assembler. If there is
more than one assembly language file,
then each should be assembled
separately.
´ Link: combine all the object files together
(if there is more than one) as well as with
libraries. This is done by the linker. The
linker checks if there are any calls to
functions in libraries. The result is an
executable file
GC230_1442(2)
Instructions
5
´ Instructions are the language of the machine
´ We will study the MIPS instruction set architecture
´ Known as Reduced Instruction Set Computer (RISC)
´ Elegant and relatively simple design
´ Like RISC architectures developed in mid-1980’s and 90’s
´ Popular, used in many products e.g., Silicon Graphics, ATI, Cisco, Sony, etc.
´ Alternative to: Intel x86 architecture
´ Known as Complex Instruction Set Computer (CISC)
GC230_1442(2)
Overview of the MIPS Architecture
6
…
Memory
4 bytes per word
Up to 232 bytes = 230 words
…
EIU
32 General
Purpose
Registers
$0
$1
$2
$31
Arithmetic &
Logic Unit
ALU
Execution &
Integer Unit
(Main proc)
Integer
mul/div
Hi
Integer
Multiplier/Divider
GC230_1442(2)
Lo
FPU
FP
Arith
TMU
F0
F1
F2
Floating
Point Unit
(Coproc 1)
32 Floating-Point
Registers
F31
Floating-Point
Arithmetic Unit
BadVaddr
Status
Cause
EPC
Trap &
Memory Unit
(Coproc 0)
MIPS
General-Purpose
Registers
7
§ 32 General Purpose Registers (GPRs)
–
All registers are 32-bit wide in the MIPS 32-bit architecture
–
Software defines names for registers to standardize their use
–
Assembler can refer to registers by name or by number ($ notation)
Name
$zero
$at
$v0 – $v1
$a0 – $a3
$t0 – $t7
$s0 – $s7
$t8 – $t9
$k0 – $k1
$gp
$sp
$fp
$ra GC230_1442(2)
Register
$0
$1
$2 – $3
$4 – $7
$8 – $15
$16 – $23
$24 – $25
$26 – $27
$28
$29
$30
$31
Usage
Always 0
(forced by hardware)
Reserved for assembler use
Result values of a function
Arguments of a function
Temporary Values
Saved registers
(preserved across call)
More temporaries
Reserved for OS kernel
Global pointer
(points to global data)
Stack pointer
(points to top of stack)
Frame pointer
(points to stack frame)
Return address
(used by jal for function call)
8
Instruction Formats
´ All instructions are 32-bit wide, Three instruction formats:
´ Register (R-Type)
´ Register-to-register instructions
´ Op: operation code specifies the format of the instruction
Op6
Rs5
Rt5
Rd5
sa5
´ Immediate (I-Type)
´ 16-bit immediate constant is part in the instruction
Op6
Rs5
Rt5
immediate16
´ Jump (J-Type)
´ Used by jump instructions
Op6
GC230_1442(2)
immediate26
funct6
9
What is Assembly Language?
´ Low-level programming language for a computer
´ One-to-one correspondence with the machine instructions
´ Assembly language is specific to a given processor
´ Assembler: converts assembly program into machine code
´ Assembly language uses:
´ Mnemonics: to represent the names of low-level machine instructions
´ Labels: to represent the names of variables or memory addresses
´ Directives: to define data and constants
´ Macros: to facilitate the inline expansion of text into other code
GC230_1442(2)
10
Assembly Language Statements
´
Three types of statements in assembly language
´
1.
Executable Instructions
´
´
2.
Generate machine code for the processor to execute at runtime
Instructions tell the processor what to do
Pseudo-Instructions and Macros
´
´
3.
Typically, one statement should appear on a line
Translated by the assembler into real instructions
Simplify the programmer task
Assembler Directives
´
´
´
Provide information to the assembler while translating a program
Used to define segments, allocate memory variables, etc.
Non-executable: directives are not part of the instruction set
GC230_1442(2)
11
Assembly Language Instructions
´ Assembly language instructions have the format:
[label:]
mnemonic
´ Label: (optional)
[operands]
[#comment]
´ Marks the address of a memory location, must have a colon
´ Typically appear in data and text segments
´ Mnemonic
´ Identifies the operation (e.g., add, sub, etc.)
´ Operands
´ Specify the data required by the operation
´ Operands can be registers, memory variables, or constants
´ Most instructions have three operands
L1:
GC230_1442(2)
addiu $t0, $t0, 1
#increment $t0
12
Comments
´ Single-line comment
´ Begins with a hash symbol # and terminates at end of line
´ Comments are very important!
´ Explain the program’s purpose
´ When it was written, revised, and by whom
´ Explain data used in the program, input, and output
´ Explain instruction sequences and algorithms used
´ Comments are also required at the beginning of every procedure
´ Indicate input parameters and results of a procedure
´ Describe what the procedure does
GC230_1442(2)
13
Program Template
# Title:
Filename:
# Author:
Date:
# Description:
# Input:
# Output:
################# Data segment #####################
.data
. . .
################# Code segment #####################
.text
.globl main
main:
# main program entry
. . .
li $v0, 10
# Exit program
syscall
GC230_1442(2)
14
.DATA, .TEXT, & .GLOBL Directives
´ .DATA directive
´ Defines the data segment of a program containing data
´ The program’s variables should be defined under this directive
´ Assembler will allocate and initialize the storage of variables
´ .TEXT directive
´ Defines the code segment of a program containing instructions
´ .GLOBL directive
´ Declares a symbol as global
´ Global symbols can be referenced from other files
´ We use this directive to declare main function of a program
GC230_1442(2)
15
Layout of a Program in Memory
0x7FFFFFFF
Memory
Addresses
in Hex
0x10000000
Stack Segment
Stack Grows
Downwards
Dynamic Area (Heap)
Data Segment
Static Area
Static data
appear here
Text Segment
Instructions
appear here
0x04000000
GC230_1442(2)
0
Reserved
16
Data Definition Statement
´ The assembler uses directives to define data
´ It allocates storage in the static data segment for a variable
´ May optionally assign a name (label) to the data
´ Syntax:
[name:] directive initializer [, initializer] . . .
var1: .WORD
10
´ All initializers become binary data in memory
GC230_1442(2)
17
Data Directives
´ .BYTE Directive
´ Stores the list of values as 8-bit bytes
´ .HALF Directive
´ Stores the list as 16-bit values aligned on half-word boundary
´ .WORD Directive
´ Stores the list as 32-bit values aligned on a word boundary
´ .FLOAT Directive
´ Stores the listed values as single-precision floating point
´ .DOUBLE Directive
´ Stores the listed values as double-precision floating point
GC230_1442(2)
18
String Directives
´ .ASCII Directive
´ Allocates a sequence of bytes for an ASCII string
´ .ASCIIZ Directive
´ Same as .ASCII directive, but adds a NULL char at end of string
´ Strings are null-terminated, as in the C programming language
´ .SPACE Directive
´ Allocates space of n uninitialized bytes in the data segment
GC230_1442(2)
19
Examples of Data Definitions
.DATA
var1:
.BYTE
‘A’, ‘E’, 127, -1, ‘\n’
var2:
.HALF
-10, 0xffff
var3:
.WORD
0x12345678:100
var4:
.FLOAT
12.3, -0.1
var5:
.DOUBLE
1.5e-10
str1:
.ASCII
“A String\n”
str2:
.ASCIIZ
“NULL Terminated String”
array: .SPACE
GC230_1442(2)
100
Array of 100 words
Initialized with
the same value
100 bytes (not initialized)
Memory Alignment
´ Memory is viewed as an addressable array of bytes
´ Byte Addressing: address points to a byte in memory
´ However, words occupy 4 consecutive bytes in memory
´ MIPS instructions and integers occupy 4 bytes
´ Memory Alignment:
´ Address must be multiple of size
´ Word address should be a multiple of 4
´ Double-word address should be a multiple of 8
´ .ALIGN n directive
´ Aligns the next data definition on a 2n byte boundary
´ Forces the address of next data definition to be multiple of 2n
GC230_1442(2)
Memory
address
20
12
…
aligned word
not aligned
8
4
0
not aligned
21
Byte Ordering (Endianness)
´
´
Processors can order bytes within a word in two ways
Little Endian Byte Ordering
´ Memory address = Address of least significant byte
´ Example: Intel IA-32
MSB
Byte 3
Byte 2
Byte 1
LSB
Byte 0
address a
. . . Byte 0
32-bit Register
´
a+1
a+2
a+3
Byte 1
Byte 2
Byte 3
…
Memory
Big Endian Byte Ordering
´ Memory address = Address of most significant byte
´ Example: SPARC architecture
MSB
Byte 3
Byte 2
Byte 1
LSB
Byte 0
32-bit Register
´
MIPS can operate with both byte orderings
GC230_1442(2)
address a
. . . Byte 3
a+1
a+2
a+3
Byte 2
Byte 1
Byte 0
Memory
…
22
Symbol Table
´ Assembler builds a symbol table for labels
´ Assembler computes the address of each label in data segment
´ Example
.DATA
var1: .BYTE
1, 2,’Z’
str1: .ASCIIZ “My String\n”
var2: .WORD
0x12345678
.ALIGN 3
var3: .HALF
1000
GC230_1442(2)
Symbol Table
Label
Address
var1
0x10010000
str1
0x10010003
var2
0x10010010
var3
0x10010018
23
System Calls
´ Programs do input/output through system calls
´ The MIPS architecture provides a syscall instruction
´ To obtain services from the operating system
´ The operating system handles all system calls requested by program
´ Since MARS is a simulator, it simulates the syscall services
´ To use the syscall services:
´ Load the service number in register $v0
´ Load argument values, if any, in registers $a0, $a1, etc.
´ Issue the syscall instruction
´ Retrieve return values, if any, from result registers
GC230_1442(2)
24
Syscall Services
Service
$v0
Print Integer
1
$a0 = integer value to print
Print Float
2
$f12 = float value to print
Print Double
3
$f12 = double value to print
Print String
4
$a0 = address of null-terminated string
Read Integer
5
Return integer value in $v0
Read Float
6
Return float value in $f0
Read Double
7
Return double value in $f0
Read String
8
$a0 = address of input buffer
$a1 = maximum number of characters to read
Allocate Heap
memory
9
$a0 = number of bytes to allocate
Return address of allocated memory in $v0
Exit Program
10
GC230_1442(2)
Arguments / Result
25
Print Char
11
$a0 = character to print
Read Char
12
Return character read in $v0
13
$a0 = address of null-terminated filename string
$a1 = flags (0 = read-only, 1 = write-only)
$a2 = mode (ignored)
Return file descriptor in $v0 (negative if error)
14
$a0 = File descriptor
$a1 = address of input buffer
$a2 = maximum number of characters to read
Return number of characters read in $v0
Write to File
15
$a0 = File descriptor
$a1 = address of buffer
$a2 = number of characters to write
Return number of characters written in $v0
Close File
16
$a0 = File descriptor
Open File
Read
from File
GC230_1442(2)
26
Reading and Printing an Integer
################# Code segment #####################
.text
.globl main
main:
# main program entry
li
$v0, 5
# Read integer
syscall
# $v0 = value read
move
$a0, $v0
li
$v0, 1
syscall
# $a0 = value to print
# Print integer
li
$v0, 10
syscall
# Exit program
GC230_1442(2)
27
Reading and Printing a String
################# Data segment #####################
.data
str: .space 10
# array of 10 bytes
################# Code segment #####################
.text
.globl main
main:
# main program entry
la
$a0, str
# $a0 = address of str
li
$a1, 10
# $a1 = max string length
li
$v0, 8
# read string
syscall
li
$v0, 4
# Print string str
syscall
li
$v0, 10
# Exit program
syscall
GC230_1442(2)
28
Sum of Three Integers
# Sum of three integers
# Objective: Computes the sum of three integers.
# Input: Requests three numbers, Output: sum
################### Data segment ###################
.data
prompt: .asciiz
“Please enter three numbers: \n”
sum_msg: .asciiz
“The sum is: ”
################### Code segment ###################
.text
.globl main
main:
la
$a0,prompt
# display prompt string
li
$v0,4
syscall
li
$v0,5
# read 1st integer into $t0
syscall
move $t0,$v0
GC230_1442(2)
29
li
$v0,5
syscall
move $t1,$v0
li
$v0,5
syscall
move $t2,$v0
addu $t0,$t0,$t1
addu $t0,$t0,$t2
la
$a0,sum_msg
li
$v0,4
syscall
move $a0,$t0
li
$v0,1
syscall
li
$v0,10
syscall
GC230_1442(2)
# read 2nd integer into $t1
# read 3rd integer into $t2
# accumulate the sum
# write sum message
# output sum
# exit
GC230 – Computer
Organization & Architecture
L3: Assembly Part II
2
Outlines
´ Introduction
´ Operations of the computer hardware
´ Operands of the computer hardware
´ Signed and Unsigned numbers
´ Representing instructions in the computer
´ Logical Operations.
GC230_1442(2)
3
Introduction
´ Instruction set: “the vocabulary of commands understood by a given
architecture”
´ Different computers have different instruction sets
´ But with many aspects in common
´ This similarity of instruction sets occurs because:
´ All computers are constructed from hardware technologies
´ Computers provide a few basic operations
´ Computer designers concentrate on maximize performance and minimize cost
and energy while keep building hardware and the compiler easy.
´ Our aim is to learn instruction set from the hardware perspective and its
relationship to the high-level programming languages.
GC230_1442(2)
4
GC230_1442(2)
5
GC230_1442(2)
6
Arithmatic Operations
´Add and subtract, three operands
´Two sources and one destination
add a, b, c
# a gets b + c
´All arithmetic operations have this form
´Design Principle 1: Simplicity favors regularity
´Regularity makes implementation simpler
´Simplicity enables higher performance at lower cost
GC230_1442(2)
7
Arithmetic Example
´C code:
f = (g + h) – (i + j);
´Compiled MIPS code:
add t0, g, h
add t1, i, j
sub f, t0, t1
GC230_1442(2)
# temp t0 = g + h
# temp t1 = i + j
# f = t0 – t1
8
Register operands
´ Arithmetic instructions use register operands
´ MIPS has a 32 × 32-bit register file
´ Use for frequently accessed data
´ Numbered 0 to 31
´ 32-bit data called a “word”
´ Assembler names
´ $t0, $t1, …, $t9 for temporary values
´ $s0, $s1, …, $s7 for saved variables
´ Design Principle 2: Smaller is faster
´ main memory: millions of locations
GC230_1442(2)
9
Register operand example
´C code:
f = (g + h) – (i + j);
´f, …, j in $s0, …, $s4
´Compiled MIPS code:
add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1
GC230_1442(2)
10
Memory operand
´Main memory used for composite data
´Arrays, structures, dynamic data
´To apply arithmetic operations
´Load values from memory into registers
´Store result from register to memory
´Memory addressed is in word(4 byte) ordered
based on endianness.
GC230_1442(2)
11
Memory operand example 1
´ C code:
g = h + A[8];
´g in $s1, h in $s2, base address of A in $s3
´ Compiled MIPS code:
´Index 8 requires offset of 32(8*4)
´4 bytes per word
lw $t0, 32($s3)
add $s1, $s2, $t0
offset
GC230_1442(2)
# load word
base register
12
Memory operand example 2
´C code:
A[12] = h + A[8];
´h in $s2, base address of A in $s3
´Compiled MIPS code:
´Index 8 requires offset of 32
lw $t0, 32($s3)
add $t0, $s2, $t0
sw $t0, 48($s3)
GC230_1442(2)
# load word
# store word
Register
13
Memory
1
Registers hold the operands or
instruction that CPU is currently
processing.
2
Register holds the small amount of data Memory of the computer can range from
around 32-bits to 64-bits.
some GB to TB.
3
CPU can operate on register contents
at the rate of more than one operation
in one clock cycle.
CPU accesses memory at the slower rate
than register.
4
Types are Accumulator register,
Program counter, Instruction register,
Address register, etc.
Type of memory are RAM,etc.
Registers can be control i.e., you can
store and retrieve information from
them.
Memory is almost not controllable.
Registers are faster than memory.
RAM is much slower than registers.
5
6
GC230_1442(2)
Memory holds the instructions and the
data that the currently executing program
in CPU requires
14
Immediate Operands
´Constant data specified in an instruction
addi $s3, $s3, 4
´No subtract immediate instruction
´Just use a negative constant
addi $s2, $s1, -1
´Design Principle 3: Make the common case fast
´Small constants are common
´Immediate operand avoids a load instruction
GC230_1442(2)
15
The Constant Zero
´MIPS register 0 ($zero) is the constant 0
´Cannot be overwritten
´Useful for common operations
´E.g., move between registers
add $t2, $s1, $zero
GC230_1442(2)
16
Unsigned Binary Integers
´ Given an n-bit number
x = x n-1 2
n -1
+ x n-2 2
n-2
+ ! + x1 2 + x 0 2
1
´ Range: 0 to +2n – 1
´ Example
´ 0000 0000 0000 0000 0000 0000 0000 10112
= 0 + … + 1×23 + 0×22 +1×21 +1×20
= 0 + … + 8 + 0 + 2 + 1 = 1110
´ Using 32 bits
´ 0 to +4,294,967,295
GC230_1442(2)
0
17
2s-Complement Signed Integers
´ Given an n-bit number
x = – x n-1 2n-1 + x n-2 2n-2 + ! + x1 21 + x 0 20
´ Range: –2n – 1 to +2n – 1 – 1
´ Example
´1111 1111 1111 1111 1111 1111 1111 11002
= –1×231 + 1×230 + … + 1×22 +0×21 +0×20
= –2,147,483,648 + 2,147,483,644 = –410
´ Using 32 bits
´–2,147,483,648 to +2,147,483,647
GC230_1442(2)
18
2s-Complement Signed Integers
´ Bit 31 is sign bit
´ 1 for negative numbers
´ 0 for non-negative numbers
´ –(–2n – 1) can’t be represented
´ Non-negative numbers have the same unsigned and 2scomplement representation
´ Some specific numbers
´ 0: 0000 0000 … 0000
´ –1: 1111 1111 … 1111
´ Most-negative:
1000 0000 … 0000
´ Most-positive:
0111 1111 … 1111
GC230_1442(2)
19
Signed Negation
´ Complement and add 1
´ Complement means 1 → 0, 0 → 1
x + x = 1111…1112 = -1
x + 1 = -x
´ Example: negate +2
´ +2 = 0000 0000 … 00102
´ –2 = 1111 1111 … 11012 + 1
= 1111 1111 … 11102
GC230_1442(2)
20
Sign Extension
´ Representing a number using more bits
´ Preserve the numeric value
´ In MIPS instruction set
´ addi: extend immediate value
´ lb, lh: extend loaded byte/halfword
´ beq, bne: extend the displacement
´ Replicate the sign bit to the left
´ c.f. unsigned values: extend with 0s
´ Examples: 8-bit to 16-bit
´ +2: 0000 0010 => 0000 0000 0000 0010
´ –2: 1111 1110 => 1111 1111 1111 1110
GC230_1442(2)
21
Representing Instructions
´ Instructions are encoded in binary that called machine
code
´ MIPS instructions
´ Encoded as 32-bit instruction words
´ Small number of formats encoding operation code (opcode),
register numbers, …
´ Regularity!
´ Register numbers
´ $t0 – $t7 are reg’s 8 – 15
´ $t8 – $t9 are reg’s 24 – 25
´ $s0 – $s7 are reg’s 16 – 23
GC230_1442(2)
22
Hexadecimal
´Base 16
´Compact representation of
bit strings
´4 bits per hex digit
´Example: eca8 6420
´1110 1100 1010 1000 0110
0100 0010 0000
GC230_1442(2)
Binary
Hex
Binary
Hex
0000
0
1000
8
0001
1
1001
9
0010
2
1010
A
0011
3
1011
B
0100
4
1100
C
0101
5
1101
D
0110
6
1110
E
0111
7
1111
F
23
MIPS R-format Instructions
´Instruction fields
´op: operation code (opcode)
´rs: first source register number
´rt: second source register number
´rd: destination register number
´Shamt (sa): shift amount (00000 for now)
´funct: function code (extends opcode)
Op6
GC230_1442(2)
Rs5
Rt5
Rd5
sa5
funct6
24
R-format Example
add $t0, $s1, $s2
Op6
Rs5
Rt5
Rd5
sa5
funct6
special
$s1
$s2
$t0
0
add
0
17
18
8
0
32
000000
10001
10010
01000
00000
100000
000000100011001001000000001000002 = 0232402016
GC230_1442(2)
25
MIPS I-format instruction
Op6
Rs5
Rt5
immediate16
´ Immediate arithmetic and load/store instructions
´ rt: destination or source register number
´ Constant: –215 to +215 – 1
´ Address: offset added to base address in rs
´ Design Principle 4: Good design demands good
compromises
´ Different formats complicate decoding, but allow 32-bit
instructions uniformly
´ Keep formats as similar as possible
GC230_1442(2)
26
Stored program Computers
´ Instructions represented in
binary, just like data
´ Instructions and data stored in
memory
´ Programs can operate on
programs
´ e.g., compilers, linkers, …
´ Binary compatibility allows
compiled programs to work on
different computers
´ Standardized ISAs
GC230_1442(2)
27
Logical Operations
´ Useful for extracting and inserting groups of bits in a word
´ Instructions for bitwise manipulation
Operation
Shift left
Shift right
Bitwise AND
Bitwise OR
Bitwise NOT
GC230_1442(2)
C
>
&
|
~
Java
>>
&
|
~
MIPS
sll
srl
and, andi
or, ori
nor
28
Shift Operations
Op6
Rs5
Rt5
Rd5
sa5
´ shamt: how many positions to shift
´ Shift left logical
´ Shift left and fill with 0 bits
´ sll by i bits multiplies by 2i
´ Shift right logical
´ Shift right and fill with 0 bits
´ srl by i bits divides by 2i (unsigned only)
GC230_1442(2)
funct6
29
AND Operations
´Useful to mask bits in a word
´Select some bits, clear others to 0
and $t0, $t1, $t2
GC230_1442(2)
30
OR Operations
´Useful to include bits in a word
´Set some bits to 1, leave others unchanged
or $t0, $t1, $t2
GC230_1442(2)
31
NOT Operations
´Useful to invert bits in a word
´Change 0 to 1, and 1 to 0
´MIPS has NOR 3-operand instruction
´a NOR b == NOT ( a OR b )
nor $t0, $t1, $zero
GC230_1442(2)
Register 0: always
read as zero
32
Conditional Operations
´Branch to a labeled instruction if a condition is
true
´Otherwise, continue sequentially
´beq rs, rt, L1
´if (rs == rt) branch to instruction labeled L1;
´bne rs, rt, L1
´if (rs != rt) branch to instruction labeled L1;
´j L1
´unconditional jump to instruction labeled L1
GC230_1442(2)
33
Compiling If Statement
´C code:
if (i==j) f = g+h;
else f = g-h;
´f, g, … in $s0, $s1, …
´Compiled MIPS code:
bne $s3, $s4, Else
add $s0, $s1, $s2
j
Exit
Else: sub $s0, $s1, $s2
Exit: …
GC230_1442(2)
Assembler calculates addresses
34
Compiling Loop Statements
´C code:
while (save[i] == k) i += 1;
´i in $s3, k in $s5, address of save in $s6
´Compiled MIPS code:
Loop: sll $t1, $s3, 2
add $t1, $t1, $s6
lw
$t0, 0($t1)
bne $t0, $s5, Exit
addi $s3, $s3, 1
j
Loop
Exit: …
GC230_1442(2)
35
Basic Blocks
´ A basic block is a sequence of
instructions with
´ No embedded branches (except at end)
´ No branch targets (except at beginning)
´ A compiler identifies basic blocks for
optimization
´ An advanced processor can
accelerate execution of basic blocks
GC230_1442(2)
36
More Conditional Operations
´Set result to 1 if a condition is true
´Otherwise, set to 0
´slt rd, rs, rt
´if (rs < rt) rd = 1; else rd = 0; ´slti rt, rs, constant ´if (rs < constant) rt = 1; else rt = 0; ´Use in combination with beq, bne slt $t0, $s1, $s2 bne $t0, $zero, L GC230_1442(2) # if ($s1 < $s2) # branch to L 37 Branch Instruction Design ´Why not blt, bge, etc? ´Hardware for +1 Þ $t0 = 0 GC230_1442(2) GC230 – Computer Organization & Architecture L4: Assembly Part II 2 Presentation Outline ´ Control Flow: Branch and Jump Instructions ´ Translating If Statements and Boolean Expressions ´ Arrays ´ Load and Store Instructions ´ Translating Loops and Traversing Arrays ´ Addressing Modes GC230_1442(2) Control Flow 3 ´ High-level programming languages provide constructs: ´ To make decisions in a program: IF-ELSE ´ To repeat the execution of a sequence of instructions: LOOP ´ The ability to make decisions and repeat a sequence of instructions distinguishes a computer from a calculator ´ All computer architectures provide control flow instructions ´ Essential for making decisions and repetitions ´ These are the conditional branch and jump instructions GC230_1442(2) 4 MIPS Conditional Branch Instructions ´ MIPS compare and branch instructions: beq Rs, Rt, label if (Rs == Rt) branch to label bne Rs, Rt, label if (Rs != Rt) branch to label ´ MIPS compare to zero & branch instructions: Compare to zero is used frequently and implemented efficiently bltz Rs, label if (Rs < 0) branch to label bgtz Rs, label if (Rs > 0) branch to label
blez Rs, label
if (Rs = 0) branch to label
´ beqz and bnez are defined as pseudo-instructions.
GC230_1442(2)
5
Branch Instruction Format
v Branch Instructions are of the I-type Format:
Op6
Rs5
Rt5
16-bit offset
Instruction
beq Rs, Rt, label
bne Rs, Rt, label
blez Rs, label
bgtz Rs, label
bltz Rs, label
bgez Rs, label
I-Type Format
Op = 4
Op = 5
Op = 6
Op = 7
Op = 1
Op = 1
Rs
Rs
Rs
Rs
Rs
Rs
Rt
Rt
0
0
0
1
16-bit Offset
16-bit Offset
16-bit Offset
16-bit Offset
16-bit Offset
16-bit Offset
´ The branch instructions modify the PC register only
´ PC-Relative addressing:
If (branch is taken) PC = PC + 4 + 4×offset else PC = PC+4
GC230_1442(2)
6
Unconditional Jump Instruction
´ The unconditional Jump instruction has the following syntax:
j
label
. . .
# jump to label
label:
´ The jump instruction is always taken
´ The Jump instruction is of the J-type format:
Op6 = 2
26-bit address
´ The jump instruction modifies the program counter PC:
PC4
26-bit address
´ The upper 4 bits of the PC are unchanged
GC230_1442(2)
00
multiple
of 4
7
Translating an IF Statement
´ Consider the following IF statement:
if (a == b) c = d + e; else c = d – e;
Given that a, b, c, d, e are in $t0 … $t4 respectively
´ How to translate the above IF statement?
bne
$t0, $t1, else
addu
$t2, $t3, $t4
j
next
else:
subu
$t2, $t3, $t4
next:
. . .
GC230_1442(2)
8
Logical AND Expression
´ Programming languages use short-circuit evaluation
´ If first condition is false, second condition is skipped
if (($t1 > 0) && ($t2 < 0)) {$t3++;} # One Possible Translation ... L1: L2: bgtz $t1, L1 # first condition j next # skip if false bltz $t2, L2 # second condition j next # skip if false addiu $t3, $t3, 1 # both are true next: GC230_1442(2) 9 Better Translation of Logical AND if (($t1 > 0) && ($t2 < 0)) {$t3++;} Allow the program to fall through to second condition !($t1 > 0) is equivalent to ($t1 = 0)
Number of instructions is reduced from 5 to 3
# Better Translation …
blez
$t1, next
# 1st condition false?
bgez
$t2, next
# 2nd condition false?
addiu
$t3, $t3, 1
# both are true
next:
GC230_1442(2)
10
Logical OR Expression
Ø Short-circuit evaluation for logical OR
Ø If first condition is true, second condition is skipped
if (($t1 > 0) || ($t2 < 0)) {$t3++;} Ø Use fall-through to keep the code as short as possible L1: bgtz $t1, L1 # 1st condition true? bgez $t2, next # 2nd condition false? addiu $t3, $t3, 1 next: GC230_1442(2) # increment $t3 11 Compare Instructions ´ MIPS also provides set less than instructions slt Rd, Rs, Rt if (Rs < Rt) Rd = 1 else Rd = 0 sltu Rd, Rs, Rt unsigned < slti Rt, Rs, imm if (Rs < imm) Rt = 1 else Rt = 0 sltiu Rt, Rs, imm unsigned < ´ Signed / Unsigned comparisons compute different results Given that: $t0 = 1 and $t1 = -1 = 0xffffffff slt $t2, $t0, $t1 computes $t2 = 0 sltu $t2, $t0, $t1 computes $t2 = 1 GC230_1442(2) Compare Instruction Formats 12 Instruction Format Meaning slt Rd, Rs, Rt Rd=(Rs