Transcript 投影片 1 - National Chung Cheng University

Instructions: Language of The
Computer
Bo Cheng
[email protected]
Compiler - Assembler - Linker - Loader



Compiler: transforms a C program into an assembly language
program, a symbolic form of what the machine understand.
Assembler: turns the assembly language program into an
object file, which is a combination of machine language
instructions, data and information needed to place instructions
properly in memory.
Linker or link editor: takes all the independently assembled
machine language programs and ‘stitches’ them together into
an executable file that can be run on a computer.
–

The linker uses the relocation information and symbol table in
each object module to resolve all undefined labels.
Loader: load the executable file into memory for execution.
Other Information


Symbol table: A table that matches names of
labels to the addresses of the memory words
that instructions occupy
Executable file: A functional program in the
format of an object file that contains no
unresolved references, relocation information,
symbol table, or debugging information.
Library: Static vs. Dynamic

Static:
–
–
–

Fast
Becoming a part of the executable code
Loading the whole library no matter that is running
or not
Dynamic:
–
–
Not linked and loaded until the program is run
Pay a good deal of overhead the first time a
routine is called.
A Translation Hierarchy For C
X.c
X.c
Compiler
Assembly Language Program
Assembler
C Program
Object: Machine Language Module
X.o
X.obj
X.s
X.asm
static
Y.a
Y.lib
dynamic
Y.so
Y.dll
Object: Binary Routine (Machine Language)
Linker
a.out
X.exe
Executable: Machine Language Program
Loader
Memory
Language, Language, Language
Machine language




Computer instructions can be represented as
sequences of bits.
This is the lowest possible level of
representation for a program
Can be understood directly by the machine.
Each instruction is equivalent to a single,
indivisible action of the CPU.
Assembly Language



A slightly higher-level representation (and one that is
much easier for humans to use)
Very closely related to machine language
Assembler
–

Translate programs written in assembly language into
machine language.
Because of the close relationship between machine
and assembly languages, each different machine
architecture usually has its own assembly language
–
Sometimes, each architecture may have several
MIPS




Microprocessor without interlocked pipeline stages
A RISC microprocessor architecture developed by
MIPS Computer Systems Inc.
MIPS designs are used in SGI's computer product
line, and have found broad application in embedded
systems, Windows CE devices, and Cisco routers.
The Nintendo 64 console, Sony PlayStation 2
console, and Sony PSP handheld system use MIPS
processors.
http://en.wikipedia.org/wiki/MIPS_architecture
MIPS History (I)



In 1981, a team led by John Hennessy at Stanford
University started work on what would become the
first MIPS processor.
The basic concept was to dramatically increase
performance through the use of deep instruction
pipelines
Generally a pipeline spreads out the task of running
an instruction into several steps, and then start
working on "step one" of an instruction even before
the preceding instruction is complete.
MIPS History (II)





In 1984, Hennessy left Stanford to form MIPS
Computer Systems.
They released their first design, the R2000, in 1985,
improving the design as the R3000 in 1988.
These 32-bit CPUs formed the basis of their
company through the 1980s, used primarily in SGI's
series of workstations.
In 1991 MIPS released the first 64-bit
microprocessor, the R4000.
SGI bought the company outright in 1992
–
Becoming an internal group at SGI, the company was now
known as MIPS Technologies.
MIPS History (III)

By the late 1990s MIPS was a powerhouse in the
embedded processor field, and in 1997 the 48th
million MIPS-based CPU shipped
–

The first RISC CPU to outship the famous Motorola 68000
family (CISC).
This proved fairly successful due to the simplicity of
the core
–
–
much less capable CISC designs of similar gate count and
price
the two are strongly related, the price of a CPU is generally
the number of gates plus the number of external pins.
MIPS R2000 CPU and FPU

A MIPS processor consists of
–
–
an integer processing unit (the
CPU) and
a collection of coprocessors


that perform ancillary tasks or
operate on other types of data
such as floating point numbers
SPIM simulates two
coprocessors
–
Coprocessor 0

–
handles traps, exceptions, and
the virtual memory system.
Coprocessor 1

floating point unit.
Central Processing Unit - CPU





the brains of the computer
Sometimes referred to simply as the processor or central
processor
On large machines, CPUs require one or more printed circuit
boards.
On personal computers and small workstations, the CPU is
housed in a single chip called a microprocessor.
Two typical components of a CPU are:
–
–
The arithmetic logic unit (ALU), which performs arithmetic and
logical operations.
The control unit, which extracts instructions from memory and
decodes and executes them, calling on the ALU when necessary.
http://www.webopedia.com/TERM/C/CPU.html
SPIM







A software simulator that runs programs written for
MIPS R2000/R3000 processors.
SPIM is MIPS backwards
PC-SPIM is the windows version of SPIM
SPIM can read and immediately execute assembly
language files, but not binary.
Contains a debugger and provides a few operating
system-like services.
It is much slower than real computer (100 or more
times)
Can be downloaded from
http://www.cs.wisc.edu/~larus/spim.html
Use PC-SPIM
Source: http://www.cs.ait.ac.th/~guha/COA/Spim/spimSlides.ppt
PCSpim Windows Interface

Registers window
–

Text segment window
–

shows assembly instructions &
corresponding machine code
Data segment window
–

shows the values of all registers in
the MIPS CPU and FPU
shows the data loaded into the
program’s memory and the data of
the program’s stack
Messages window
–
shows PCSpim messages
Separate console window appears for I/O
Opening Window




Register Display: This shows the contents (bit
patterns in hex) of all 32 general purpose
registers, the floating point registers, and a few
others.
Text Display: This shows the assembly
language program source, the machine
instructions (bit patterns in hex) they correspond
to, and the addresses of their memory locations.
Data and Stack Display: This shows the
sections of MIPS memory that hold ordinary
data and data which has been pushed onto a
stack.
SPIM Messages: This shows messages from
the simulator (often error messages).
Character output from the simulated computer is in the SPIM console window
Setting ….
Message

Messages from the simulated computer
appear in the console window when an
assembly program that is running (in
simulation) writes to the (simulated) monitor.
If a real MIPS computer were running you
would see the same messages on a real
monitor.
Writing an Assembly Program




A source file (in assembly language or in any
programming language) is the text file containing
programming language statements created (usually)
by a human programmer.
An editor like Notepad will work. You will probably
want to use a better editor.
Word processors usually create "binary" files and so
are not suitable for creating source files.
With your program (text) editor create a file with asm
extension, e.g., addup.asm.
Use Notepad To Edit Your Program
Program Template
# Comment giving name of program and description of function
# Template.s
# Bare-bones outline of MIPS assembly language program
main:
.data
# variable declarations follow this line
# ...
.text
# instructions follow this line
# indicates start of code (first instruction to execute)
# ...
# End of program, leave a blank line afterwards to make SPIM happy
Two Sections

Text
–
–

Instructions go here
Contains the beginning of the program
Data
–
Where the variables are declared
Example 1
# Daniel J. Ellard -- 02/21/94
# add.asm-- A program that computes the sum of 1 and 2,
# leaving the result in register $t0.
# Registers used:
# t0 - used to hold the result.
# t1 - used to hold the constant 1.
# v0 - syscall parameter.
main:
# SPIM starts execution at main.
li $t1, 1
# load 1 into $t1.
add $t0, $t1, 2
# compute the sum of $t1 and 2, and
# put it into $t0.
li $v0, 10
# syscall code 10 is for exit.
syscall
# make the syscall.
# end of add.asm
Comments



Any text between a pound sign (#) and the
subsequent newline is considered to be a
comment.
Comments are absolutely essential!
Assembly language programs are notoriously
difficult to read unless they are properly
documented.
Labels and Main

To begin with, we need to tell the assembler
where the program starts.
–

In SPIM, program execution begins at the location
with the label main.
A label is a symbolic name for an address in
memory.
–
–
–
a label is a symbol name followed by a colon
e.g., main:
The names of instructions can not be used as
labels
Registers




The MIPS R2000 CPU has 32 registers.
31 of these are general-purpose registers
that can be used in any of the instructions.
The last one, denoted register zero, is
defined to contain the number zero at all
times.
MIPS programmers have agreed upon a set
of guidelines that specify how each of the
registers should be used.
The MIPS Register Set (32 Registers)
The MIPS Instruction Set (I)

If an instruction description begins with an , o
then the instruction is not a member of the
native MIPS instruction set
–
–
For example, abs
The assembler translates pseudoinstructions into
one or more native instructions
The MIPS Instruction Set (II)


If the op contains a (u), then this instruction
can either use signed or unsigned arithmetic,
depending on whether or not a u is
appended to the name of the instruction.
For example, if the op is given as add(u)
–
–
add (add signed) or
addu (add unsigned).
The MIPS Instruction Set (III)
The MIPS Instruction Set (IV)





des must always be a register.
src1 must always be a register.
reg2 must always be a register.
src2 may be either a register or a 32-bit
integer.
addr must be an address
The Load Instructions
• Fetch a byte, halfword, or word from memory and put it
into a register.
• The li and lui instructions load a constant into a register.
Arithmetic Instructions
Arithmetic Examples




<op> <des> <src1> <src2>
Have 3 operands
Operand order is fixed: destination first
Only 32 registers are provided
Examples
–
–
add $t0, $s0, $s2
sub $s0, $t0, $t1
# $t0 = $s0 + $s2
# $s0 = $t0 – $t1
Syscalls (I)
Syscalls (II)


The syscall instruction suspends the
execution of your program and transfers
control to the operating system.
The operating system then looks at the
contents of register $v0 to determine what it
is that your program is asking it to do.
For example: Similar to C, where the exit function can be called in
order to halt the execution of a program
Syscalls (III) - Example
syscall 5 can be used to read an integer into register $v0.
syscall 1 can be used to print out the integer stored in $a0.
Data Movement Instructions
•The data movement instructions move data
among registers.
•Special instructions are provided to move data in
and out of special registers such as hi and lo.
Example 2 (I)
# Daniel J. Ellard -- 02/21/94
# add2.asm-- A program that computes and prints the sum
# of two numbers specified at runtime by the user.
# Registers used:
# $t0 - used to hold the first number.
# $t1 - used to hold the second number.
# $t2 - used to hold the sum of the $t1 and $t2.
# $v0 - syscall parameter and return value.
# $a0 - syscall parameter.
Example 2 (II)
main:
## Get first number from user, put into $t0.
li $v0, 5
# load syscall read_int into $v0.
syscall
# make the syscall.
move $t0, $v0
# move the number read into $t0.
## Get second number from user, put into $t1.
li $v0, 5
# load syscall read_int into $v0.
syscall
# make the syscall.
move $t1, $v0
# move the number read into $t1.
# Compute the sum.
add $t2, $t0, $t1 # Sum it up
## Print out $t2.
move $a0, $t2
# move the number to print into $a0.
li $v0, 1
# load syscall print_int into $v0.
syscall
# make the syscall.
# Exit the program
li $v0, 10
# syscall code 10 is for exit.
syscall
# make the syscall.
# end of add2.asm.
Example 3 – Hello World
# Daniel J. Ellard -- 02/21/94
# hello.asm-- A "Hello World" program.
# Registers used:
# $v0 - syscall parameter and return value.
# $a0 - syscall parameter-- the string to print.
.text
main:
la $a0, hello_msg
# load the addr of hello_msg into $a0.
li $v0, 4
# 4 is the print_string syscall.
syscall
# do the syscall.
# Exit the program
li $v0, 10
# 10 is the exit syscall.
syscall
# do the syscall.
# Data for the program:
.data
hello_msg: .asciiz "Hello World\n"
# end hello.asm
Directives


A directive is an instruction for the assembler (not
the CPU) for reserving memory, telling the assembler
where to place instructions, etc.
Data segment
–
–

Text segment
–
–

Tagged with the .data directive.
Is used to allocate storage and initialize global variables
Indicated by the .text directive.
This is where we put the instructions we want the processor
to execute.
By default, the assembler starts in the text segment
Data Directives
They Are The Same
Example 4 (I) – Larger Number
# Daniel J. Ellard -- 02/21/94
# larger.asm-- prints the larger of two numbers specified
# at runtime by the user.
# Registers used:
# $t0 - used to hold the first number.
# $t1 - used to hold the second number.
# $t2 - used to store the larger of $t1 and $t2.
# $v0 - syscall parameter and return value.
# $a0 - syscall parameter.
.text
main:
## Get first number from user, put into $t0.
li $v0, 5
# load syscall read_int into $v0.
syscall
# make the syscall.
move $t0, $v0
# move the number read into $t0.
## Get second number from user, put into $t1.
li $v0, 5
# load syscall read_int into $v0.
syscall
# make the syscall.
move $t1, $v0
# move the number read into $t1.
Example 4 (II) – Larger Number
## put the larger of $t0 and $t1 into $t2.
bgt $t0, $t1, t0_bigger
move $t2, $t1
b endif
t0_bigger:
move $t2, $t0 # copy $t0 into $t2
endif:
## Print out $t2.
move $a0, $t2
li $v0, 1
syscall
## exit the program.
li $v0, 10
syscall
# end of larger.asm.
# If $t0 > $t1, branch to t0_bigger,
# otherwise, copy $t1 into $t2.
# and then branch to endif
# move the number to print into $a0.
# load syscall print_int into $v0.
# make the syscall.
# syscall code 10 is for exit.
# make the syscall.
Branch Instructions
Bgt and b statement



<bgt> <Src1> <Src2><Label>
The rst two are numbers, and the last is a
label.
If (Src1 > Src2) Go to <Label>; otherwise go
next
<b> <Label>
Simply branches to the given label.
MIPS/SPIM Version
Computing Integer Division
Iterative C++ Version
int a = 12;
int b = 4;
int result = 0;
main () {
x:
while (a >= b) {y:
a = a - b;
res:
result ++;
}
}
main:
}
C++
while:
.data
# Use HLL program as a comment
.word
12
# int x = 12;
.word
4
# int y = 4;
.word
0
# int res = 0;
.globl
main
.text
la
$s0, x
# Allocate registers for globals
lw
$s1, 0($s0)
#
x in $s1
lw
$s2, 4($s0)
#
y in $s2
lw
$s3, 8($s0)
#
res in $s3
bgt
$s2, $s1, endwhile
# while (x >= y) {
sub
$s1, $s1, $s2
addi
$s3, $s3, 1
#
j
while
# }
la
$s0, x
# Update variables in memory
sw
$s1, 0($s0)
sw
$s2, 4($s0)
sw
$s3, 8($s0)
#
x = x - y;
res ++;
endwhile:
MIPS
Assembly Language
Simple One
int a = 12;
int b = 4;
# $t0 = a
int result = 0;
# $t1 = b
main () {
# $t2 = res
while (a >= b) {
main:
a = a - b;
result ++;
}
printf(“%d %d %d, a , b, res); while:
}
C++
MIPS
Assembly Language
.text
li $t0, 12
li $t1, 4
li $t2, 0
bgt
sub
addi
j
$t1, $t0, endwhile
$t0, $t0, $t1
$t2, $t2, 1
while
# while (a >= b) {
# a = a - b;
# res ++;
#}
endwhile:
move $a0, $t0
li $v0, 1
syscall
move $a0, $t1
li $v0, 1
syscall
move $a0, $t2
li $v0, 1
syscall
# make the syscall.
# make the syscall.
# make the syscall.
#
li $v0, 10
syscall
# syscall code 10 is for exit.
# make the syscall.
Jump Instructions
Comparison Instructions
The Address Mode


The second operand of all of the load and store
instructions must be an address. The
MIPS architecture supports the following
addressing modes:
Subroutine



Sometimes called procedure, function, or
method
Is a logical division of the code that may be
regarded as a self-contained operation.
A subroutine might be executed several
times with different data as the program
executes.
Chap 26 & 27
http://chortle.ccsu.edu/AssemblyTutorial/TutorialContents.html
Callers and Callees



A subroutine call is when a main routine (or
other routine) passes control to a subroutine.
The main routine is said to be the CALLER
and the subroutine is said to be the CALLEE.
A return from a subroutine is when a
subroutine passes control back to its
CALLER.
The jal Instruction (I)


The jal instruction and register
$31 ($ra) provide the hardware
support necessary to elegantly
implement subroutines.
Machine Cycle
The jal Instruction (II)
jal sub # $ra <― PC+4
# $ra <― address 8 bytes away from the jal
# PC <― sub
# load the PC with the subroutine entry point

So now $ra holds the address
of the second instruction
after the jal instruction.
The jr Instruction




Returns control to the caller.
jr $ra
# PC <― $ra
It copies the contents of $ra into the PC:
Think as "jumping to the address in $ra."
The jr instruction is followed by a branch
delay slot (nop instruction).
Calling Convention



A subroutine is called using jal.
The subroutine returns to its caller using jr $ra.
Registers are used as follows:
–
–
–
–

$t0 - $t9 — The subroutine is free to change these registers.
$s0 - $s7 — The subroutine must not change these
registers.
$a0 - $a3 — These registers contain arguments for the
subroutine. The subroutine can change them.
$v0 - $v1 — These registers contain values returned from
the subroutine.
The main routine returns control by using the exit
service (service 10) of the SPIM exception handler.
Main Calling Mysub Example


Two arguments
are passed, in
$a0 and $a1.
The subroutine
reads the
arguments from
those registers.
Example 5
# Bo Cheng -- 02/08/05
# ex5.asm-- A program that exercises the function calls
.data
in_main_msg1: .asciiz "Before The Call \n"
in_sub_msg: .asciiz "In sub Program \n"
in_main_msg2: .asciiz "After The Call \n"
.text
main:
# SPIM starts execution at main.
# Print the "before" message
la $a0, in_main_msg1
li $v0, 4
syscall
# Call the subroutine sub_pro
# the subrouine body
jal sub_pro
sub_pro:
nop
la $a0, in_sub_msg
# Print "after" message
li $v0, 4
la $a0, in_main_msg2
li $v0, 4
syscall
syscall
# return the call
# exit the program
jr $ra
li $v0, 10 # syscall code 10 is for exit.
syscall
# make the syscall.
nop
# end of add.asm
The Example 6 - Sum
main:
li $s0, 0x06
# load 6 into Register S0
li $s1, 0x10
# load 16 into Register S1
move $a0, $s0 # use argument 1 in Register a0
move $a1, $s1 # use argument 2 in Register a1
jal sum_it
# call subroutine sum_it
nop
# branch delay slot
# Get the result
move $s3, $v0
# get# the
from Register
the result
subroutine
sum_it v0
# Print the sum
sum_it:
move $a0, $s3 # place the result
into $a0,
Register
add $t1,
$a1 a0
li $v0, 1
# load syscallmove
print_int
$v0,into
$t1$v0.
syscall
# make the syscall.
jr $ra
# exit the program
nop
li $v0, 10
# syscall code 10 is for exit.
syscall
# make the syscall.
# end of sum_example.asm
# sum it up
# place the result
# return
# branch delay slot
Pushing the Return Address



To return to the caller a
subroutine must have the
correct return address in
$ra when the jr instruction
is performed.
But this address does not
have to remain in $ra all
the time the subroutine is
running.
It works fine to save the
value of $ra and then to
restore it when needed.
Chain of Subroutine Calls

Only one $ra would be lost
if nested subroutine
–

Solution: push the return
address it gets onto the stack.
When it returns to its caller, it
pops the stack to get the
return address.
Need to change registers in
subroutine
–
Solution: push the contents
onto stack
Stack




LIFO (Last-In, Fist-Out)
Grows from larger memory
addresses to smaller memory
addresses
Use stack pointer ($SP=$29) to
point the top of stack.
Push: SP = SP – 4
sub $sp, 4
sw $ra, ($sp)

Pop: SP = SP + 4
lw $ra, ($sp)
add $sp, 4
SP
0x01000000
0x00FFFFFC
0x00FFFFF8
0x00FFFFF4
0x00FFFFF0
Push on MIPS
Source: users.ece.gatech.edu/~rdanse/ ECE2030/slides/ECE2030_Chapter15_2pp.pdf
Pop On MIPS
Nested Procedure Calls
Stack-based Linkage Convention

Subroutine Call (done by the caller):
–
–
–

Subroutine Prolog (done by the subroutine at its beginning):
–
–

–
The subroutine may alter any "T" or "A" register, or any "S" register
If the subroutine calls another subroutine, then it does so by following these rules.
Subroutine Epilog (done by the subroutine just before it returns to the caller):
–
–
–
–

If this subroutine might call other subroutines, push $ra onto the stack.
Push onto the stack any registers $s0-$s7 that this subroutine might alter.
Subroutine Body:
–

Push onto the stack any registers $t0-$t9 that contain values that must be saved.
Put argument values into $a0-$a3.
Call the subroutine using jal.
Put returned values in $v0-$v1
Pop from the stack (in reverse order) any registers $s0-$s7 that were pushed in the
prolog (step 5).
If it was pushed in the prolog (step 4), pop the return address from the stack into $ra.
Return to the caller using jr $ra.
Regaining Control from a subroutine (done by the caller):
–
Pop from the stack (in reverse order) any registers $t0-$t9 that were previously
pushed (step 1).
Pushing and Popping Registers


if a subroutine is expected to alter any of the
"S" registers, it must first push their values
onto the stack.
Just before returning to the caller it must pop
these values from the stack back into the
registers they came from.
The Call Chain Example
subB:
sub $sp,$sp,4 # push $ra
sw $ra,($sp)
....
jal subC
# call subC
nop
....
lw $ra,($sp) # pop return address
add $sp,$sp,4
jr $ra
# return to caller
nop
# subC expects to use $s0 and $s1
# subC does not call another subroutine
#
subC:
sub $sp,$sp,4 # push $s0
sw $s0,($sp)
sub $sp,$sp,4 # push $s1
sw $s1,($sp)
....
# statements using $s0 and $s1
lw $s1,($sp) # pop s1
add $sp,$sp,4
lw $s0,($sp) # pop s0
add $sp,$sp,4
jr $ra
# return to subB
nop
Example 7 – Find Min
main:
li $a0, 3 # set arg 0
li $a1, 4 # set arg 1
li $a2, 5 # set arg 2
jal findMin3
move $t0, $v0 # save return value to $t0
## Print out the min.
move $a0, $t0
# move the number to print into $a0.
li $v0, 1
# load syscall print_int into $v0.
syscall
# make the syscall.
findMin3: move $t0, $a0
# min = x
# exit the program
bge $a1, $t0, IF2 # branch if !( y < min )
li $v0, 10
# syscall codemove
10 is for
$t0,exit.
$a1
# min = y
syscall # make the syscall.
IF2: bge $a1, $t0, END # branch if !( z < min )
# end of add.asm
move $t0, $a2
# min = z
END:
move $v0, $t0
# retval = min
jr $ra
# return