Transcript cs281_lec09

Systems Architecture
Lecture 9: Assemblers, Linkers, and Loaders
Jeremy R. Johnson
Anatole D. Ruslanov
William M. Mongan
Some or all figures from Computer Organization and Design: The
Hardware/Software Approach, Third Edition, by David Patterson and
John Hennessy, are copyrighted material (COPYRIGHT 2004
MORGAN KAUFMANN PUBLISHERS, INC. ALL RIGHTS RESERVED).
Lec 9
Systems Architecture
1
Introduction
• Objective: To review the MIPS instruction set and encoding.
• Objective: To learn how the MIPS assembler, linker, and
loader work.
• Topics
–
–
–
–
–
–
–
Lec 9
Immediate instructions
Addressing in branches and jumps
Review MIPS instruction set and addressing modes
Instruction formats and encoding
Assembler
Linker and object files
Loader and executable files
Systems Architecture
2
MIPS Instruction Set
• Arithmetic/Logical
– add, sub, and, or
– addi, andi, ori
• Data Transfer
– lw, lb
– sw, sb
– lui
• Control
– beq, bne
– slt, slti
– j, jal, jr
Lec 9
Systems Architecture
3
Assembler Pseudoinstructions
• Most assembler instructions represent machine instructions
one-to-one
• Pseudoinstructions: figments of the assembler’s imagination
move $t0, $t1→
add $t0, $zero, $t1
blt $t0, $t1, L
→ slt $at, $t0, $t1
bne $at, $zero, L
– $at (register 1): assembler temporary
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
4
Immediate Addressing – Why?
• Small constants are used frequently (~50% of operands)
e.g.,
A = A + 5;
B = B + 1;
C = C - 18;
• Solution: use immediate format and hardwired registers
– store / imbed constants in the low order 16-bits.
– create hard-wired registers (like $zero) for constants.
• Design Principle: Make the common case fast.
– Memory access can be 20-100 x slower than accessing registers
– Remove memory load delay / overhead
– Store the constant in the instruction itself
Lec 9
Systems Architecture
5
Immediate Addressing
• MIPS Instruction Examples
addi $29, $29, 4
slti $8, $18, 10
andi $29, $29, 6
ori $29, $29, 4
• I-Format machine code Example: addi $s0, $s0, 4
8
Lec 9
16
16
Systems Architecture
4
6
How about larger constants?
• Since MIPS only allows 16-bit constants (a common case)
• Two instructions are required to imbed a 32-bit constant
• li $s0, 0x003c0900 will be translated by the assembler to
– lui $s0, 0x003c; load upper immediate instruction
– ori $s0, $s0, 0x0900
• When constructing 32 bit offsets for memory addresses the
MIPS assembler uses the $at register for temporary space
• $at stands for “assembler temporary” register
Lec 9
Systems Architecture
7
Loading a 32-bit Constant
• “load upper immediate instruction”
• lui places its 16-bit constant in the upper 31-16 bit space
lui $t0, 1010101010101010
• Use ori (or immediate) to place the lower 15-0 bit space:
ori $t0, $t0, 1010101010101010
lui
1010101010101010
0000000000000000
ori
0000000000000000
1010101010101010
result
1010101010101010
1010101010101010
Lec 9
Systems Architecture
8
Assembly Language vs. Machine
Language
• Assembly provides convenient symbolic representation
– “Mnemonics” are much easier than writing down numbers
– Uniform feel to the instructions that hides machine code
• Machine language is the underlying reality
– E.g., destination is no longer first
– Difficult for human to use: time-consuming and error-prone
• Assembly can provide 'pseudoinstructions'
– move, bgt, blt, etc. exist only in assembly code
– Pseudoinstructions are translated to real instructions.
• When considering performance count the real
instructions!
Lec 9
Systems Architecture
9
Overview of MIPS
•Simple instructions all 32 bits wide
•Well-organized and structured, no unnecessary baggage
•Only three instruction formats
Lec 9
Systems Architecture
10
PC-relative Addressing in Branches
• Instructions:
bne $t4,$t5,Label Next instruction is at Label if $t4≠$t5
beq $t4,$t5,Label Next instruction is at Label if $t4=$t5
• I-Format :
I
op
rs
rt
16 bit address
• How to construct the branch target address: use PC+4
and add the (signed) value of immediate constant to it.
• This works because most branches are local,
-- the target address is near by (principle of locality).
• Note: branches are restricted to 217 byte “distance”
jumps.
Lec 9
Systems Architecture
11
Pseudodirect Addressing in Jumps
• J-Format:
26-bit constant
6-bits
• Jump instructions use 28 high order bits of PC
– Jumps are restricted to 228 byte jumps (256 MB)
• 32-bit address construction:
– Take bits 31-28 of PC+4
– Concatenate them to 26-bit constant (forms bits 27-2)
– Append “00” to the “end” (bits 1-0) to reconstruct the byte address
PC+4[31-28]
31
Lec 9
26-bit constant from j instruction
28 27
00
2
Systems Architecture
0
13
MIPS Encoding
•
•
•
•
All instructions are 32-bits long
Opcode is always in the high-order 6 bits
Only three instruction formats
32 registers implies 5 bit register addresses:
–
–
–
–
–
–
–
–
–
–
–
–
Lec 9
$zero
$at
$v0 - $v1
$a0 - $a3
$t0 - $t7
$s0 - $s7
$t8 - $t9
$k0 - $k1
$gp
$sp
$fp
$ra
R0
R1
R2-R3
R4-R7
R8-R15
R16-R23
R24-R25
R26-R27
R28
R29
R30
R31
; zero register always equal to 0
; temporary register (assembler temporary)
; return registers
; argument registers
; temporary - not preserved across calls
; saved registers - preserved across calls
; temporary not preserved across calls
; reserved by OS kernel
; global pointer
; stack pointer
; frame pointer
; return address
Systems Architecture
14
MIPS Addressing Modes
• Immediate Addressing
– 16 bit constant from low order bits of instruction
– addi $t0, $s0, 4
• Register Addressing
– add $t0, $s0, $s1
• Base Addressing (displacement addressing)
– 16-bit constant from low order bits of instruction plus base register
– lw $t0, 16($sp)
• PC-Relative Addressing
– (PC+4) + 16-bit address (word) from instruction
– bne $s0, $s1, Target
• Pseudodirect Addressing
– high order 4 bits of PC+4 concatenated with 26 bit word address - low
order 26 bits from instruction shifted 2 bits to the left
– j Address
Lec 9
Systems Architecture
15
Decoding Machine Code
• Example:
0000 0000 1010 1111 1000 0000 0010 0000
Lec 9
Systems Architecture
16
Design Principles
• Simplicity favors regularity
– uniform instruction length
– all ALU operations have 3 register operands
– register addresses in the same location for all instruction formats
• Smaller is faster
– register architecture
– small number of registers
• Good design demands good compromises
– fixed length instructions and only 16 bit constants
– several instruction formats but consistent length
• Make common cases fast
– immediate addressing
– 16 bit constants
– only beq and bne
Lec 9
Systems Architecture
17
Translation Hierarchy
Lec 9
Systems Architecture
18
Assembler
•
•
•
•
•
•
•
•
Translates assembly code to machine code
Creates object file
Symbolic labels to addresses
Pseudoinstructions (move, la, li, blt, bgt, ...)
Assembly directives (.text, .globl, .space, .byte, .asciiz,...)
Loading a 32-bit constant (lui and ori)
Constructing 32-bit addresses (use $at)
Branching far away (beq $s0, $s1, L1 => bne and j)
Lec 9
Systems Architecture
19
Producing an Object Module
• Assembler (or compiler) translates program
into machine instructions
• Provides information for building a complete
program from the pieces
– Header: described contents of object module
– Text segment: translated instructions
– Static data segment: data allocated for the life of
the program
– Relocation info: for contents that depend on
absolute location of loaded program
– Symbol table: global definitions and external refs
– Debug info: for associating with source code
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
20
Format of Object File
• Object file header (size and position)
• Text segment (instructions - machine code)
• Data segment (data that comes with the program, both
static and dynamic)
• Relocation information (instructions and data words that
depend on absolute addresses when program is loaded
into memory)
• Symbol table (external references)
• Debugging information
Lec 9
Systems Architecture
21
Linker
• Place code and data modules symbolically in memory
• Determine the addresses of data and instruction labels
• Patch both the internal and external references
Lec 9
Systems Architecture
22
Linking Object Modules
• Produces an executable image
1. Merges segments
2. Resolve labels (determine their addresses)
3. Patch location-dependent and external refs
• Could leave location dependencies for fixing by a relocating
loader
– But with virtual memory, no need to do this
– Program can be loaded into absolute location in virtual memory space
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
23
Dynamic Linking
• Only link/load library procedure when it is called
– Requires procedure code to be relocatable
– Avoids image bloat caused by static linking of all (transitively) referenced
libraries
– Automatically picks up new library versions
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
24
Lazy Linkage
Indirection table
Stub: Loads routine ID,
Jump to linker/loader
Linker/loader code
Dynamically
mapped code
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
25
MIPS Memory Convention
Lec 9
Systems Architecture
26
Loader
• Read executable file header to determine size of text and
data segments
• Creates an address space large enough for the text and
data
• Copies instructions and data from executable file into
memory
• Copies parameters (if any) to the main program onto the
stack
• Initializes the machine registers and sets stack pointer to
first free location
• Jumps to a start-up routine that copies the parameters into
the argument registers and calls the main routine of the
program. When the main routine returns, the start-up
routine terminates the program with an exit system call.
Lec 9
Systems Architecture
27
Loading a Program
• Load from image file on disk into memory
1. Read header to determine segment sizes
2. Create virtual address space
3. Copy text and initialized data into memory
• Or set page table entries so they can be faulted in
4. Set up arguments on stack
5. Initialize registers (including $sp, $fp, $gp)
6. Jump to startup routine
• Copies arguments to $a0, … and calls main
• When main returns, do exit syscall
10 April 2016
Chapter 2 — Instructions: Language
of the Computer
28
Starting Java Applications
Simple portable
instruction set for
the JVM
Compiles
bytecodes of
“hot” methods
into native
code for host
machine
10 April 2016
Interprets
bytecodes
Chapter 2 — Instructions: Language
of the Computer
29
Linking Example
Object File Header
Object File Header
Name
Procedure A
Text size
0x100
Data size
0x20
Text Segment
Address Instruction
0
lw $a0, 0($gp)
4
jal 0
…
…
Data Segment
0
(X)
…
…
Relocation Information Address
Instruction Type Dependency
0
lw
X
4
jal
B
Symbol Table
Label
Address
X
B
-
Name
Procedure B
Text size
0x200
Data size
0x30
Text Segment
Address Instruction
0 sw $a1, 0($gp)
4
jal 0
…
…
Data Segment
0
(Y)
…
…
Relocation Information Address
Instruction Type Dependency
0
sw
Y
4
jal
A
Symbol Table
Label
Address
Y
A
-
Lec 9
Systems Architecture
30
Resulting Executable File
Executable File Header
Text Segment
Data Segment
Lec 9
Text size
Data size
Address
0x00400000
0x00400004
…
0x00400100
0x00400104
0x10000000
…
0x10000020
…
Systems Architecture
0x300
0x50
Instruction
lw $a0, 0x8000($gp)
jal 400100
…
lw $a0, 0x8020($gp)
jal 400000
(X)
…
(Y)
…
31