Transcript Introduction to Computer Systems 15-213/18

Machine-Level Programming I: Basics
Computer Systems Organization
Andrew Case
Slides adapted from Jinyang Li, Randy Bryant and Dave O’Hallaron
1
x86 Processors

Totally dominate laptop/desktop/server market

Evolutionary design
 Backwards compatible all the way to 8086, introduced in 1978
 Added more features as time goes on

Complex instruction set computer (CISC)
 Many different instructions with many different formats
 By contrast, ARM architecture (in cell phones) is RISC (Reduced
Instruction Set Computers)
 Generally better for low power devices
2
Intel x86 Evolution: Milestones
Name
 8086 (1978)
Transistors
29K
MHz
5-10
 First 16-bit processor. Basis for IBM PC & DOS
 1MB address space

386 (1985)
275K
16-33
 First 32 bit processor , referred to as IA32
 Capable of running Unix

Pentium 4F (2004) 125M
Instruction Set Architecture
2800-3800
 First Intel 64-bit processor, referred to as x86-64

Core i7 (2008)
731M
2667-3333
We cover both IA32 and x86-64. Labs are done in IA32.
3
Intel x86 Processors: Overview
Architectures
X86-16
Processors
8086
286
X86-32/IA32
MMX
386
486
Pentium
Pentium MMX
SSE
Pentium III
SSE2
Pentium 4
SSE3
Pentium 4E
X86-64 / EM64t
Pentium 4F
SSE4
Core 2 Duo
Core i7
time
IA: often redefined as latest Intel architecture
4
Ia64 - Itanium
Name
 Itanium
Date
2001
Transistors
10M
 First shot at 64-bit architecture: first called IA64
 Not 32-bit compatible (emulation)

Basic reason for failure
5
x86 Clones: Advanced Micro Devices (AMD)
 Developed x86-64, their own extension to 64 bits
AMD implementation name: AMD64
 Intel implementation name: Intel64/EM64T

6
Today: Machine Programming I: Basics




History of Intel processors and architectures
C, assembly, machine code
Assembly Basics: Registers, operands, move
Intro to x86-64
7
Assembly Programmer’s View
CPU
Addresses
PC
Registers
Condition
Codes

Data
Instructions
Memory
Object Code
Program Data
OS Data
Execution context
 PC: Program counter
Address of next instruction
 Called “EIP” (IA32) or “RIP” (x86-64)

 Registers

Heavily used program data
 Condition codes
Info of recent arithmetic operation
 Used for conditional branching

8
Assembly Data Types

“Integer” data of 1, 2, or 4 bytes
 Represent either data value or address (untyped pointer)

Floating point data of 4, 8, or 10 bytes

No arrays or structures
9
3 Kind of Assembly Operations

Perform arithmetic on register or memory data
 Add, subtract, multiplication…

Transfer data between memory and register
 Load data from memory into register
 Store register data into memory

Transfer control
 Unconditional jumps to/from procedures
 Conditional branches
10
Turning C into Object Code
Optimization
level
Output file
is p
 Code in files p1.c p2.c
 Compile with command: gcc –O1 p1.c p2.c -o p
text
C program (p1.c p2.c)
Compiler (gcc –S)
text
Asm program (p1.s p2.s)
Assembler (gcc –c)
binary
Object program (p1.o p2.o)
Linker
binary
Static libraries
(.a)
Executable program (p)
11
Compiling Into Assembly
sum.s
sum.c
int sum(int x, int y)
{
int t = x+y;
return t;
}
gcc –c sum.c
gcc –S sum.c
gcc –c sum.s
sum:
pushl %ebp
movl %esp,%ebp
movl 12(%ebp),%eax
addl 8(%ebp),%eax
popl %ebp
ret
objdump –d sum.o
(gdb) disassemble sum
sum.o
80483c4:
55 89 e5 8b 45 0c 03 45 08 5d c3
12
Compiling Into Assembly
sum.s
sum.c
int sum(int x, int y)
{
int t = x+y;
return t;
}
sum:
pushl %ebp
movl %esp,%ebp
movl 12(%ebp),%eax
addl 8(%ebp),%eax
popl %ebp
ret
Refer to register %eax
Refer to memory
at address %ebp+8
sum.o
80483c4:
55 89 e5 8b 45 0c 03 45 08 5d c3
13
Machine Instruction Example
int t = x+y;

 Add two signed integers

“Long” words in GCC parlance
 Same instruction whether signed
or unsigned
 Operands:
x: Register
%eax
y: Memory
M[%ebp+8]
t: Register
%eax
– Return function value in %eax

Similar to expression:
x += y
More precisely:
int eax;
int *ebp;
eax += ebp[2]
03 45 08
Assembly
 Add 2 4-byte integers
addl 8(%ebp),%eax
0x80483ca:
C Code

Object Code
 3-byte instruction
 Stored at address 0x80483ca
14
Today: Machine Programming I: Basics




History of Intel processors and architectures
C, assembly, machine code
Assembly Basics: Registers, operands, move
Intro to x86-64
15
general purpose
Integer Registers (IA32)
Origin
(mostly obsolete)
%eax
%ax
%ah
%al
accumulate
%ecx
%cx
%ch
%cl
counter
%edx
%dx
%dh
%dl
data
%ebx
%bx
%bh
%bl
base
%esi
%si
source
index
%edi
%di
destination
index
%esp
%sp
%ebp
%bp
stack
pointer
base
pointer
16-bit virtual registers
(backwards compatibility)
16
Moving Data: IA32

movl Source, Dest:

Operand Types
 Immediate: Constant integer data
%eax
%ecx
%edx
%ebx
%esi
%edi
%esp
Example: $0x400, $-533
 Like C constant, but prefixed with ‘$’
 Register: One of 8 integer registers
%ebp
 Example: %eax, %edx
 But %esp and %ebp reserved for special use
 Others have special uses for particular instructions
 Memory: 4 consecutive bytes of memory at address given by register
 Example: (%eax)

17
movl Operand Combinations
Source
movl
Dest
Src,Dest
C Analog
Imm
Reg movl $0x4,%eax
Mem movl $-147,(%eax)
temp = 0x4;
Reg
Reg movl %eax,%edx
Mem movl %eax,(%edx)
temp2 = temp1;
Mem
Reg
movl (%eax),%edx
*p = -147;
*p = temp;
temp = *p;
No memory-to-memory instruction
18
Simple Memory Addressing Modes

Normal
(R)
Mem[Reg[R]]
 Register R specifies memory address
movl (%ecx),%eax

Displacement D(R)
Mem[Reg[R]+D]
 Register R specifies start of memory region
 Constant displacement D specifies offset
movl 8(%ebp),%edx
19
Using Simple Addressing Modes
void swap(int *xp, int *yp)
{
int t0 = *xp;
int t1 = *yp;
*xp = t1;
*yp = t0;
}
swap:
pushl %ebp
movl %esp,%ebp
pushl %ebx
Set
Up
Point to first argument
Point to second argument
movl
movl
movl
movl
movl
movl
popl
popl
ret
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
%ebx
%ebp
Body
Finish
20
Understanding Swap
123
Address
0x124
456
0x120
0x11c
%eax
0x118
Offset
%edx
%ecx
%ebx
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
21
Understanding Swap
123
Address
0x124
456
0x120
0x11c
%eax
%edx
0x118
Offset
0x124
%ecx
%ebx
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
22
Understanding Swap
123
Address
0x124
456
0x120
0x11c
%eax
0x118
%edx
0x124
%ecx
0x120
Offset
%ebx
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
23
Understanding Swap
123
Address
0x124
456
0x120
0x11c
%eax
0x118
%edx
0x124
%ecx
0x120
%ebx
Offset
123
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
24
Understanding Swap
123
Address
0x124
456
0x120
0x11c
%eax
456
%edx
0x124
%ecx
0x120
%ebx
0x118
Offset
123
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
25
Understanding Swap
456
Address
0x124
456
0x120
0x11c
%eax
456
456
%edx
0x124
%ecx
0x120
%ebx
0x118
Offset
123
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
26
Understanding Swap
456
Address
0x124
123
0x120
0x11c
%eax
456
%edx
0x124
%ecx
0x120
%ebx
0x118
Offset
123
%esi
12
0x120
0x110
xp
8
0x124
0x10c
4
Rtn adr
0x108
0
0x104
-4
%esp
%ebp
yp
%ebp
%edi
0x114
0x104
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
#
#
#
#
#
#
0x100
edx
ecx
ebx
eax
*xp
*yp
=
=
=
=
=
=
xp
yp
*xp (t0)
*yp (t1)
t1
t0
27
General Memory Addressing Modes

Most General Form
D ( Rb, Ri, S )
Mem[Reg[Rb]+S*Reg[Ri]+ D]
Constant Base register
Scale
displacement
Index register (1,2,4,8)
(no %esp)

Special Cases
(Rb,Ri)
D(Rb,Ri)
(Rb,Ri,S)
Mem[Reg[Rb]+Reg[Ri]]
Mem[Reg[Rb]+Reg[Ri]+D]
Mem[Reg[Rb]+S*Reg[Ri]]
28
Today: Machine Programming I: Basics




History of Intel processors and architectures
C, assembly, machine code
Assembly Basics: Registers, operands, move
Intro to x86-64
29
Size of C objects on IA32 and x86-64

C Data Type
Generic 32-bit
 unsigned
4
 int
4
 long int
4
 char
1
 short
2
 float
4
 double
8
 char *
4
– Or any other pointer
Intel IA32
4
4
4
1
2
4
8
4
x86-64
4
4
8
1
2
4
8
8
30
%rax
%eax
%r8
%r8d
%rbx
%ebx
%r9
%r9d
%rcx
%ecx
%r10
%r10d
%rdx
%edx
%r11
%r11d
%rsi
%esi
%r12
%r12d
%rdi
%edi
%r13
%r13d
%rsp
%esp
%r14
%r14d
%rbp
%ebp
%r15
%r15d
Add 8 new ones
Extend existing registers
x86-64 Integer Registers
31
Instructions

New instructions for 8-byte types:





movl ➙ movq
addl ➙ addq
sall ➙ salq
etc.
32-bit instructions that generate 32-bit results
 Set higher order bits of destination register to 0
 Example: addl
32
32-bit code for swap
void swap(int *xp, int *yp)
{
int t0 = *xp;
int t1 = *yp;
*xp = t1;
*yp = t0;
}
swap:
pushl %ebp
movl %esp,%ebp
pushl %ebx
movl
movl
movl
movl
movl
movl
8(%ebp), %edx
12(%ebp), %ecx
(%edx), %ebx
(%ecx), %eax
%eax, (%edx)
%ebx, (%ecx)
popl
popl
ret
%ebx
%ebp
Set
Up
Body
Finish
33
64-bit code for swap
swap:
void swap(int *xp, int *yp)
{
int t0 = *xp;
int t1 = *yp;
*xp = t1;
*yp = t0;
}

…
movl
movl
movl
movl
…
ret
(%rdi), %edx
(%rsi), %eax
%eax, (%rdi)
%edx, (%rsi)
Set
Up
Body
Finish
Operands passed in registers (why useful?)
 First (xp) in %rdi, second (yp) in %rsi
 64-bit pointers

32-bit data (int)
 Data held in %eax and %edx (instead of %rax and %rdx)
 movl operation instead of movq
34
64-bit code for long int swap
swap_l:
void swap(long *xp, long *yp)
{
long t0 = *xp;
long t1 = *yp;
*xp = t1;
*yp = t0;
}

…
movq
movq
movq
movq
…
ret
(%rdi), %rdx
(%rsi), %rax
%rax, (%rdi)
%rdx, (%rsi)
Set
Up
Body
Finish
64-bit data
 Data held in registers %rax and %rdx
 movq operation

“q” stands for quad-word
35
Machine Programming I: Summary

History of Intel processors and architectures
 Evolutionary design leads to many quirks and artifacts

C, assembly, machine code
 Compiler must transform statements, expressions, procedures into
low-level instruction sequences

Assembly Basics: Registers, operands, move
 The x86 move instructions cover wide range of data movement
forms

Intro to x86-64
 A major departure from the style of code seen in IA32
36