Machine-Level Programming I: Basics

15-213/18-213: Introduction to Computer Systems

Instructor:
EJ Kim
Slides are taken from the Authors and may have been
modified for the class.
Authors: Randal E. Bryant and David R. O’Hallaron

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1

 Today: Machine Programming I: Basics

• History of Intel processors and architectures

• C, assembly, machine code
• Assembly Basics: Registers, operands, move
• Arithmetic & logical operations

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2

 Intel x86 Evolution: Milestones
Name Date Transistors MHz
• 8086 1978 29K 5-10
– First 16-bit Intel processor. Basis for IBM PC & DOS
– 1MB address space
• 386 1985 275K 16-33
– First 32 bit Intel processor , referred to as IA32
– Added “flat addressing”, capable of running Unix
• Pentium 4E 2004 125M 2800-3800
– First 64-bit Intel x86 processor, referred to as x86-64
• Core 2 2006 291M 1060-3500
– First multi-core Intel processor
• Core i7 2008 731M 1700-3900
– Four cores (our shark machines)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3
 Intel x86 Processors, cont.
• Machine Evolution
– 386 1985 0.3M
– Pentium 1993 3.1M
– Pentium/MMX 1997 4.5M
– PentiumPro 1995 6.5M
– Pentium III 1999 8.2M
– Pentium 4 2001 42M
– Core 2 Duo 2006 291M
– Core i7 2008 731M
• Added Features
– Instructions to support multimedia operations
– Instructions to enable more efficient conditional operations
– Transition from 32 bits to 64 bits
– More cores

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4

 2015 State of the Art
– Core i7 Broadwell 2015

• Desktop Model
– 4 cores
– Integrated graphics
– 3.3-3.8 GHz
– 65W

• Server Model
– 8 cores
– Integrated I/O
– 2-2.6 GHz
– 45W

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5

 x86 Clones: Advanced Micro Devices (AMD)
• Historically
–AMD has followed just behind Intel
–A little bit slower, a lot cheaper
• Then
–Recruited top circuit designers from Digital Equipment Corp. and other
downward trending companies
–Built Opteron: tough competitor to Pentium 4
–Developed x86-64, their own extension to 64 bits
• Recent Years
–Intel got its act together
• Leads the world in semiconductor technology
–AMD has fallen behind
• Relies on external semiconductor manufacturer

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6

 Intel’s 64-Bit History
• 2001: Intel Attempts Radical Shift from IA32 to IA64
– Totally different architecture (Itanium)
– Executes IA32 code only as legacy
– Performance disappointing
• 2003: AMD Steps in with Evolutionary Solution
– x86-64 (now called “AMD64”)
• Intel Felt Obligated to Focus on IA64
– Hard to admit mistake or that AMD is better
• 2004: Intel Announces EM64T extension to IA32
– Extended Memory 64-bit Technology
– Almost identical to x86-64!
• All but low-end x86 processors support x86-64
– But, lots of code still runs in 32-bit mode

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7

 Our Coverage
• IA32
– The traditional x86

• x86-64
– The standard
– shark> gcc hello.c
– shark> gcc –m64 hello.c

• Presentation
– Book covers x86-64
– Web aside on IA32
– We will only cover x86-64

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8

 Today: Machine Programming I: Basics

• History of Intel processors and architectures

• C, assembly, machine code
• Assembly Basics: Registers, operands, move
• Arithmetic & logical operations

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 9

 Definitions
• Architecture: (also ISA: instruction set architecture) The parts of a
processor design that one needs to understand or write
assembly/machine code.
– Examples: instruction set specification, registers.
• Microarchitecture: Implementation of the architecture.
– Examples: cache sizes and core frequency.
• Code Forms:
– Machine Code: The byte-level programs that a processor executes
– Assembly Code: A text representation of machine code

• Example ISAs:
– Intel: x86, IA32, Itanium, x86-64
– ARM: Used in almost all mobile phones

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10

 Assembly/Machine Code View
CPU Memory
Addresses
Registers
Data Code
PC Data
Condition Instructions Stack
Codes

Programmer-Visible State
– PC: Program counter – Memory
• Address of next instruction • Byte addressable array
• Called “RIP” (x86-64) • Code and user data
– Register file • Stack to support procedures
• Heavily used program data
– Condition codes
• Store status information about most recent
arithmetic or logical operation
• Used for conditional branching

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 11

 Turning C into Object Code
– Code in files p1.c p2.c
– Compile with command: gcc –Og p1.c p2.c -o p
• Use basic optimizations (-Og) [New to recent versions of GCC]
• Put resulting binary in file p

text C program (p1.c p2.c)

Compiler (gcc –Og -S)

text Asm program (p1.s p2.s)

Assembler (gcc or as)

binary Object program (p1.o p2.o) Static libraries

(.a)
Linker (gcc or ld)

binary Executable program (p)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12

 Compiling Into Assembly
C Code (sum.c) Generated x86-64 Assembly
long plus(long x, long y); sumstore:
pushq %rbx
void sumstore(long x, long y, movq %rdx, %rbx
long *dest) call plus
{ movq %rax, (%rbx)
long t = plus(x, y); popq %rbx
*dest = t; ret
}
Obtain (on shark machine) with command
gcc –Og –S sum.c
Produces file sum.s
Warning: Will get very different results on non-Shark
machines (Andrew Linux, Mac OS-X, …) due to
different versions of gcc and different compiler
settings. 13
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
 Assembly Characteristics: Data Types
• “Integer” data of 1, 2, 4, or 8 bytes
– Data values
– Addresses (untyped pointers)

• Floating point data of 4, 8, or 10 bytes

• Code: Byte sequences encoding series of instructions

• No aggregate types such as arrays or structures

– Just contiguously allocated bytes in memory
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14
 Assembly Characteristics: Operations

• Perform arithmetic function on register or memory

data

• 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

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 15

 Object Code
Code for sumstore
• Assembler
0x0400595:
0x53 – Translates .s into .o
0x48 – Binary encoding of each instruction
0x89
0xd3
– Nearly-complete image of executable
0xe8 code
0xf2 – Missing linkages between code in
0xff
0xff
different files
0xff •
Total of 14 bytes • Linker
0x48
0x89
• Each instruction – Resolves references between files
0x03 1, 3, or 5 bytes – Combines with static run-time libraries
0x5b • Starts at address • E.g., code for malloc, printf
0xc3 0x0400595
– Some libraries are dynamically linked
• Linking occurs when program begins
execution
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16
 Machine Instruction Example
• C Code
*dest = t;
– Store value t where
designated by dest
movq %rax, (%rbx) • Assembly
– Move 8-byte value to memory
• Quad words in x86-64 parlance
– Operands:
t: Register %rax
dest: Register %rbx
*dest: Memory M[%rbx]
0x40059e: 48 89 03
• Object Code
– 3-byte instruction
– Stored at address 0x40059e
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17
 Disassembling Object Code
Disassembled
0000000000400595 <sumstore>:
400595: 53 push %rbx
400596: 48 89 d3 mov %rdx,%rbx
400599: e8 f2 ff ff ff callq 400590 <plus>
40059e: 48 89 03 mov %rax,(%rbx)
4005a1: 5b pop %rbx
4005a2: c3 retq

• Disassembler
objdump –d sum
– Useful tool for examining object code
– Analyzes bit pattern of series of instructions
– Produces approximate rendition of assembly code
– Can be run on either a.out (complete executable) or .o file

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18

 Today: Machine Programming I: Basics

• History of Intel processors and architectures

• C, assembly, machine code
• Assembly Basics: Registers, operands, move
• Arithmetic & logical operations

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19

 x86-64 Integer Registers
%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

– Can reference low-order 4 bytes (also low-order 1 &

2 bytes)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20
 Some History: IA32 Registers Origin
(mostly obsolete)

%eax %ax %ah %al accumulate

%ecx %cx %ch %cl counter

general purpose

%edx %dx %dh %dl data

%ebx %bx %bh %bl base

source
%esi %si index

destination
%edi %di index
stack
%esp %sp
pointer
base
%ebp %bp
pointer

16-bit virtual registers

(backwards compatibility)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21
 Moving Data %rax
• Moving Data %rcx
movq Source, Dest: %rdx
• Operand Types %rbx
– Immediate: Constant integer data %rsi
• Example: $0x400, $-533
%rdi
• Like C constant, but prefixed with ‘$’
• Encoded with 1, 2, or 4 bytes %rsp
– Register: One of 16 integer registers %rbp
• Example: %rax, %r13
• But %rsp reserved for special use %rN
• Others have special uses for particular instructions
– Memory: 8 consecutive bytes of memory at address given by register
• Simplest example: (%rax)
• Various other “address modes”

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22

 movq Operand Combinations

Source Dest Src,Dest C Analog

Reg movq $0x4,%rax temp = 0x4;

Imm
Mem movq $-147,(%rax) *p = -147;

Reg movq %rax,%rdx temp2 = temp1;

movq Reg
Mem movq %rax,(%rdx) *p = temp;

Mem Reg movq (%rax),%rdx temp = *p;

Cannot do memory-memory transfer with a single instruction

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23
 Simple Memory Addressing Modes

• Normal (R) Mem[Reg[R]]

– Register R specifies memory address
– Aha! Pointer dereferencing in C

movq (%rcx),%rax

• Displacement D(R) Mem[Reg[R]+D]

– Register R specifies start of memory region
– Constant displacement D specifies offset

movq 8(%rbp),%rdx

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24

 Example of Simple Addressing Modes

void swap
(long *xp, long *yp)
{ swap:
long t0 = *xp; movq (%rdi), %rax
long t1 = *yp; movq (%rsi), %rdx
*xp = t1; movq %rdx, (%rdi)
*yp = t0; movq %rax, (%rsi)
} ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25

 Understanding Swap()
Memory
void swap Registers
(long *xp, long *yp)
{ %rdi
long t0 = *xp;
%rsi
long t1 = *yp;
*xp = t1; %rax
*yp = t0;
} %rdx

Register Value
%rdi xp
%rsi yp
swap:
%rax t0
movq (%rdi), %rax # t0 = *xp
%rdx t1 movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26
 Understanding Swap()
Memory
Registers Address
123 0x120
%rdi 0x120
0x118
%rsi 0x100
0x110
%rax 0x108
%rdx 456 0x100

swap:
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27

 Understanding Swap()
Memory
Registers Address
123 0x120
%rdi 0x120
0x118
%rsi 0x100
0x110
%rax 123 0x108
%rdx 456 0x100

swap:
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28

 Understanding Swap()
Memory
Registers Address
123 0x120
%rdi 0x120
0x118
%rsi 0x100
0x110
%rax 123 0x108
%rdx 456 456 0x100

swap:
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29

 Understanding Swap()
Memory
Registers Address
456 0x120
%rdi 0x120
0x118
%rsi 0x100
0x110
%rax 123 0x108
%rdx 456 456 0x100

swap:
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30

 Understanding Swap()
Memory
Registers Address
456 0x120
%rdi 0x120
0x118
%rsi 0x100
0x110
%rax 123 0x108
%rdx 456 123 0x100

swap:
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
ret

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31

 Simple Memory Addressing Modes

• Normal (R) Mem[Reg[R]]

– Register R specifies memory address
– Aha! Pointer dereferencing in C

movq (%rcx),%rax

• Displacement D(R) Mem[Reg[R]+D]

– Register R specifies start of memory region
– Constant displacement D specifies offset

movq 8(%rbp),%rdx

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32

 Complete Memory Addressing Modes
• Most General Form
D(Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]+ D]
– D: Constant “displacement” 1, 2, or 4 bytes
– Rb: Base register: Any of 16 integer registers
– Ri: Index register: Any, except for %rsp
– S: Scale: 1, 2, 4, or 8 (why these numbers?)

• Special Cases
(Rb,Ri) Mem[Reg[Rb]+Reg[Ri]]
D(Rb,Ri)Mem[Reg[Rb]+Reg[Ri]+D]
(Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]]
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33
 Carnegie Mellon

Address Computation Examples

%rdx 0xf000
%rcx 0x0100

Expression Address Computation Address

0x8(%rdx)
0x8(%rdx) 0xf000 + 0x8 0xf008
(%rdx,%rcx) 0xf000 + 0x100 0xf100
(%rdx,%rcx)
(%rdx,%rcx,4) 0xf000 + 4*0x100 0xf400
(%rdx,%rcx,4)
0x80(,%rdx,2) 2*0xf000 + 0x80 0x1e080
0x80(,%rdx,2)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34

 Today: Machine Programming I: Basics

• History of Intel processors and architectures

• C, assembly, machine code
• Assembly Basics: Registers, operands, move
• Arithmetic & logical operations

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 35

 Carnegie Mellon

Address Computation Instruction

• leaq Src, Dst
– Src is address mode expression
– Set Dst to address denoted by expression

• Uses
– Computing addresses without a memory reference
• E.g., translation of p = &x[i];
– Computing arithmetic expressions of the form x + k*y
long •m12(long
long k = 1, 2, 4,x)
m12(long or 8
x) Converted to ASM by compiler:
{
{
• Example
return
return x*12;
x*12; leaq
leaq (%rdi,%rdi,2),
(%rdi,%rdi,2), %rax
%rax #
# t
t <-
<- x+x*2
x+x*2
}
} salq
salq $2,
$2, %rax
%rax #
# return
return t<<2
t<<2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 36
 Carnegie Mellon

Some Arithmetic Operations

• Two Operand Instructions:
Format Computation
addq Src,Dest Dest = Dest + Src
subq Src,Dest Dest = Dest  Src
imulq Src,Dest Dest = Dest * Src
salq Src,Dest Dest = Dest << Src Also called shlq
sarq Src,Dest Dest = Dest >> Src Arithmetic
shrq Src,Dest Dest = Dest >> Src Logical
xorq Src,Dest Dest = Dest ^ Src
andq Src,Dest Dest = Dest & Src
orq Src,Dest Dest = Dest | Src
• Watch out for argument order!
• No distinction between signed and unsigned int (why?)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 37

 Carnegie Mellon

Some Arithmetic Operations

• One Operand Instructions
incq Dest Dest = Dest + 1
decq Dest Dest = Dest  1
negq Dest Dest =  Dest
notq Dest Dest = ~Dest

• See book for more instructions

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 38

 Carnegie Mellon

Arithmetic Expression Example

arith:
leaq (%rdi,%rsi), %rax
long
long arith
arith addq %rdx, %rax
(long
(long x,
x, long
long y,y, long
long z)z) leaq (%rsi,%rsi,2), %rdx
{
{ salq $4, %rdx
long
long t1
t1 == x+y;
x+y; leaq 4(%rdi,%rdx), %rcx
long
long t2
t2 == z+t1;
z+t1; imulq %rcx, %rax
long
long t3
t3 == x+4;
x+4; ret
long
long t4
t4 == y
y ** 48;
48;
long
long t5
t5 == t3
t3 ++ t4;
t4; Interesting Instructions
long
long rval
rval == t2
t2 *
* t5;
t5;
return
return rval;
rval;
– leaq: address
}
} computation
– salq: shift
– imulq: multiplication
• But, only used once

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 39

 Carnegie Mellon

Understanding Arithmetic Expression

Example
arith:
leaq (%rdi,%rsi), %rax # t1
long
long arith
arith addq %rdx, %rax # t2
(long
(long x,
x, long
long y,y, long
long z)z) leaq (%rsi,%rsi,2), %rdx
{
{ salq $4, %rdx # t4
long
long t1
t1 == x+y;
x+y; leaq 4(%rdi,%rdx), %rcx # t5
long
long t2
t2 == z+t1;
z+t1; imulq %rcx, %rax # rval
long
long t3
t3 == x+4;
x+4; ret
long
long t4
t4 == y
y ** 48;
48;
long
long t5
t5 == t3
t3 ++ t4;
t4; Register Use(s)
long
long rval
rval == t2
t2 *
* t5;
t5; %rdi Argument x
return
return rval;
rval;
}
} %rsi Argument y
%rdx Argument z
%rax t1, t2, rval
%rdx t4
%rcx t5

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40

 Machine Programming I: Summary
• History of Intel processors and architectures
– Evolutionary design leads to many quirks and artifacts
• C, assembly, machine code
– New forms of visible state: program counter, registers, ...
– Compiler must transform statements, expressions, procedures into
low-level instruction sequences
• Assembly Basics: Registers, operands, move
– The x86-64 move instructions cover wide range of data movement
forms
• Arithmetic
– C compiler will figure out different instruction combinations to carry
out computation

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41