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
Chapter 2 — Instructions: Language of the Computer — 88
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
Chapter 2 — Instructions: Language of the Computer — 89
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 x10, … and calls main
◼ When main returns, do exit syscall
Chapter 2 — Instructions: Language of the Computer — 90
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
Chapter 2 — Instructions: Language of the Computer — 91
Lazy Linkage
Indirection table:
A nonlocal routine calls its
dummy routine entry at the end
of the program.
The dummy entry points to the
code that puts a number in a
register to identify the desired
routine and then Branches to the
dynamic linker/loader.
Stub: Loads routine ID,
Jump to linker/loader
Linker/loader code
Dynamically mapped code
Chapter 2 — Instructions: Language of the Computer — 92
Starting Java Applications
Simple portable
instruction set for
the JVM
Compiles
Interprets
bytecodes of
bytecodes
“hot” methods
into native
code for host
machine
Chapter 2 — Instructions: Language of the Computer — 93
§2.13 A C Sort Example to Put It All Together
C Sort Example
◼ Illustrates use of assembly instructions
for a C bubble sort function
◼ Swap procedure (leaf)
void swap(long long int v[],
long long int k)
{
long long int temp;
temp = v[k];
v[k] = v[k+1];
v[k+1] = temp;
}
◼ v in x10, k in x11, temp in x5
Chapter 2 — Instructions: Language of the Computer — 94
The Procedure Swap
swap:
slli x6,x11,3 // reg x6 = k * 8
add x6,x10,x6 // reg x6 = v + (k * 8)
ld x5,0(x6) // reg x5 (temp) = v[k]
ld x7,8(x6) // reg x7 = v[k + 1]
sd x7,0(x6) // v[k] = reg x7
sd x5,8(x6) // v[k+1] = reg x5 (temp)
jalr x0,0(x1) // return to calling routine
Chapter 2 — Instructions: Language of the Computer — 95
The Sort Procedure in C
◼ Non-leaf (calls swap)
void sort (long long int v[], size_t n)
{
size_t i, j;
for (i = 0; i < n; i += 1) {
for (j = i – 1;
j >= 0 && v[j] > v[j + 1];
j -= 1) {
swap(v,j);
} 0 1 2 3 . . . n-1
} j i
}
◼ v in x10, n in x11, i in x19, j in x20
Chapter 2 — Instructions: Language of the Computer — 96
The Outer Loop
◼ Skeleton of outer loop:
◼ for (i = 0; i <n; i += 1) {
li x19,0 // i = 0
for1tst:
bge x19,x11,exit1 // go to exit1 if x19 ≥ x11 (i≥n)
(body of outer for-loop)
addi x19,x19,1 // i += 1
j for1tst // branch to test of outer loop
exit1:
Chapter 2 — Instructions: Language of the Computer — 97
The Inner Loop
◼ Skeleton of inner loop:
◼ for (j = i − 1; j >= 0 && v[j] > v[j + 1]; j − = 1) {
addi x20,x19,-1 // j = i −1
for2tst:
blt x20,x0,exit2 // go to exit2 if X20 < 0 (j < 0)
slli x5,x20,3 // reg x5 = j * 8
add x5,x10,x5 // reg x5 = v + (j * 8)
ld x6,0(x5) // reg x6 = v[j]
ld x7,8(x5) // reg x7 = v[j + 1]
ble x6,x7,exit2 // go to exit2 if x6 ≤ x7
mv x10, x21 // first swap parameter is v
mv x11, x20 // second swap parameter is j
jal x1,swap // call swap
addi x20,x20,-1 // j –= 1
j for2tst // branch to test of inner loop
exit2:
Chapter 2 — Instructions: Language of the Computer — 98
Preserving Registers
◼ Preserve saved registers:
addi sp,sp,-40 // make room on stack for 5 regs
sd x1,32(sp) // save x1 on stack
sd x22,24(sp) // save x22 on stack
sd x21,16(sp) // save x21 on stack
sd x20,8(sp) // save x20 on stack
sd x19,0(sp) // save x19 on stack
◼ Restore saved registers:
exit1:
ld x19,0(sp) // restore x19 from stack
ld x20,8(sp) // restore x20 from stack
ld x21,16(sp) // restore x21 from stack
ld x22,24(sp) // restore x22 from stack
ld x1,32(sp) // restore x1 from stack
addi sp,sp, 40 // restore stack pointer
jalr x0,0(x1)
Chapter 2 — Instructions: Language of the Computer — 99
Effect of Compiler Optimization
Compiled with gcc for Pentium 4 under Linux
3 Relative Performance 140000 Instruction count
2.5 120000
100000
2
80000
1.5
60000
1
40000
0.5 20000
0 0
none O1 O2 O3 none O1 O2 O3
180000 Clock Cycles 2 CPI
160000
140000 1.5
120000
100000
1
80000
60000
40000 0.5
20000
0 0
none O1 O2 O3 none O1 O2 O3
Chapter 2 — Instructions: Language of the Computer — 100
Effect of Language and Algorithm
3 Bubblesort Relative Performance
2.5
1.5
0.5
0
C/none C/O1 C/O2 C/O3 Java/int Java/JIT
2.5 Quicksort Relative Performance
2
1.5
0.5
0
C/none C/O1 C/O2 C/O3 Java/int Java/JIT
3000 Quicksort vs. Bubblesort Speedup
2500
2000
1500
1000
500
0
C/none C/O1 C/O2 C/O3 Java/int Java/JIT
Chapter 2 — Instructions: Language of the Computer — 101
Lessons Learnt
◼ Instruction count and CPI are not good
performance indicators in isolation
◼ Compiler optimizations are sensitive to the
algorithm
◼ Java/JIT compiled code is significantly
faster than JVM interpreted
◼ Comparable to optimized C in some cases
◼ Nothing can fix a dumb algorithm!
Chapter 2 — Instructions: Language of the Computer — 102
§2.14 Arrays versus Pointers
Arrays vs. Pointers
◼ Array indexing involves
◼ Multiplying index by element size
◼ Adding to array base address
◼ Pointers correspond directly to memory
addresses
◼ Can avoid indexing complexity
Chapter 2 — Instructions: Language of the Computer — 103
Example: Clearing an Array
clear1(int array[], int size) { clear2(int *array, int size) {
int i; int *p;
for (i = 0; i < size; i += 1) for (p = &array[0]; p < &array[size];
array[i] = 0; p = p + 1)
} *p = 0;
}
li x5,0 // i = 0 mv x5,x10 // p = address
loop1: // of array[0]
slli x6,x5,2 // x6 = i * 4 slli x6,x11,2 // x6 = size * 4
add x7,x10,x6 // x7 = address add x7,x10,x6 // x7 = address
// of array[i] // of array[size]
sw x0,0(x7) // array[i] = 0 loop2:
addi x5,x5,1 // i = i + 1 sw x0,0(x5) // Memory[p] = 0
blt x5,x11,loop1 // if (i<size) addi x5,x5,4 // p = p + 4
// go to loop1 bltu x5,x7,loop2
// if (p<&array[size])
// go to loop2
Chapter 2 — Instructions: Language of the Computer — 104
Comparison of Array vs. Ptr
◼ Multiply “strength reduced” to shift
◼ Array version requires shift to be inside
loop
◼ Part of index calculation for incremented i
◼ c.f. incrementing pointer
◼ Compiler can achieve same effect as
manual use of pointers
◼ Induction variable elimination
◼ Better to make program clearer and safer
Chapter 2 — Instructions: Language of the Computer — 105
§2.16 Real Stuff: MIPS Instructions
MIPS Instructions
◼ MIPS: commercial predecessor to RISC-V
◼ Similar basic set of instructions
◼ 32-bit instructions
◼ 32 general purpose registers, register 0 is always 0
◼ 32 floating-point registers
◼ Memory accessed only by load/store instructions
◼ Consistent use of addressing modes for all data sizes
◼ Different conditional branches
◼ For <, <=, >, >=
◼ RISC-V: blt, bge, bltu, bgeu
◼ MIPS: slt, sltu (set less than, result is 0 or 1)
◼ Then use beq, bne to complete the branch
Chapter 2 — Instructions: Language of the Computer — 106
Instruction Encoding
Chapter 2 — Instructions: Language of the Computer — 107
§2.19 Real Stuff: x86 Instructions
The Intel x86 ISA
◼ Evolution with backward compatibility
◼ 8080 (1974): 8-bit microprocessor
◼ Accumulator, plus 3 index-register pairs
◼ 8086 (1978): 16-bit extension to 8080
◼ Complex instruction set (CISC)
◼ 8087 (1980): floating-point coprocessor
◼ Adds FP instructions and register stack
◼ 80286 (1982): 24-bit addresses, MMU
◼ Segmented memory mapping and protection
◼ 80386 (1985): 32-bit extension (now IA-32)
◼ Additional addressing modes and operations
◼ Paged memory mapping as well as segments
Chapter 2 — Instructions: Language of the Computer — 108
The Intel x86 ISA
◼ Further evolution…
◼ i486 (1989): pipelined, on-chip caches and FPU
◼ Compatible competitors: AMD, Cyrix, …
◼ Pentium (1993): superscalar, 64-bit datapath
◼ Later versions added MMX (Multi-Media eXtension)
instructions
◼ The infamous FDIV bug
◼ Pentium Pro (1995), Pentium II (1997)
◼ New microarchitecture (see Colwell, The Pentium Chronicles)
◼ Pentium III (1999)
◼ Added SSE (Streaming SIMD Extensions) and associated
registers
◼ Pentium 4 (2001)
◼ New microarchitecture
◼ Added SSE2 instructions
Chapter 2 — Instructions: Language of the Computer — 109
The Intel x86 ISA
◼ And further…
◼ AMD64 (2003): extended architecture to 64 bits
◼ EM64T – Extended Memory 64 Technology (2004)
◼ AMD64 adopted by Intel (with refinements)
◼ Added SSE3 instructions
◼ Intel Core (2006)
◼ Added SSE4 instructions, virtual machine support
◼ AMD64 (announced 2007): SSE5 instructions
◼ Intel declined to follow, instead…
◼ Advanced Vector Extension (announced 2008)
◼ Longer SSE registers, more instructions
◼ If Intel didn’t extend with compatibility, its
competitors would!
◼ Technical elegance ≠ market success
Chapter 2 — Instructions: Language of the Computer — 110
Basic x86 Registers
Chapter 2 — Instructions: Language of the Computer — 111
Basic x86 Addressing Modes
◼ Two operands per instruction
Source/dest operand Second source operand
Register Register
Register Immediate
Register Memory
Memory Register
Memory Immediate
◼ Memory addressing modes
◼ Address in register
◼ Address = Rbase + displacement
◼ Address = Rbase + 2scale × Rindex (scale = 0, 1, 2, or 3)
◼ Address = Rbase + 2scale × Rindex + displacement
Chapter 2 — Instructions: Language of the Computer — 112
x86 Instruction Encoding
◼ Variable length
encoding
◼ Postfix bytes specify
addressing mode
◼ Prefix bytes modify
operation
◼ Operand length,
repetition, locking, …
Chapter 2 — Instructions: Language of the Computer — 113
Implementing IA-32
◼ Complex instruction set makes
implementation difficult
◼ Hardware translates instructions to simpler
microoperations
◼ Simple instructions: 1–1
◼ Complex instructions: 1–many
◼ Microengine similar to RISC
◼ Market share makes this economically viable
◼ Comparable performance to RISC
◼ Compilers avoid complex instructions
Chapter 2 — Instructions: Language of the Computer — 114
§2.20 The Rest of the RISC-V Instruction Set
Other RISC-V Instructions
◼ Base integer instructions (RV64I)
◼ Those previously described, plus
◼ auipc rd, immed // rd = (imm<<12) + pc
◼ follow by jalr (adds 12-bit immed) for long jump
◼ slt, sltu, slti, sltui: set less than (like MIPS)
◼ addw, subw, addiw: 32-bit add/sub
◼ sllw, srlw, srlw, slliw, srliw, sraiw: 32-bit shift
◼ 32-bit variant: RV32I
◼ registers are 32-bits wide, 32-bit operations
Chapter 2 — Instructions: Language of the Computer — 115
RISC-V Instruction Set
Chapter 2 — Instructions: Language of the Computer — 116
Instruction Set Extensions
◼ M: integer multiply, divide, remainder
◼ A: atomic memory operations
◼ F: single-precision floating point
◼ D: double-precision floating point
◼ C: compressed instructions
◼ 16-bit encoding for frequently used instructions
Chapter 2 — Instructions: Language of the Computer — 117
§2.22 Fallacies and Pitfalls
Fallacies
◼ Powerful instruction higher performance
◼ Fewer instructions required
◼ But complex instructions are hard to implement
◼ May slow down all instructions, including simple ones
◼ Compilers are good at making fast code from simple
instructions
◼ Use assembly code for high performance
◼ But modern compilers are better at dealing with
modern processors
◼ More lines of code more errors and less
productivity
Chapter 2 — Instructions: Language of the Computer — 118
Fallacies
◼ Backward compatibility instruction set
doesn’t change
◼ But they do accrete more instructions
x86 instruction set
Chapter 2 — Instructions: Language of the Computer — 119
Pitfalls
◼ Sequential words are not at sequential
addresses
◼ Increment by 4, not by 1!
◼ Keeping a pointer to an automatic variable
after procedure returns
◼ e.g., passing pointer back via an argument
◼ Pointer becomes invalid when stack popped
Chapter 2 — Instructions: Language of the Computer — 120
§2.23 Concluding Remarks
Concluding Remarks
◼ Design principles
1. Simplicity favors regularity
2. Smaller is faster
3. Good design demands good compromises
◼ Make the common case fast
◼ Layers of software/hardware
◼ Compiler, assembler, hardware
◼ RISC-V: typical of RISC ISAs
◼ c.f. x86
Chapter 2 — Instructions: Language of the Computer — 121