Carnegie Mellon
Machine-Level Programming
I: Basics
15-213/18-213: Introduction to Computer Systems
5th Lecture, Sep. 15, 2015
Instructors:
Randal E. Bryant and David R. OHallaron
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
Today: Machine
Programming I: Basics
History of Intel processors and
architectures
C, assembly, machine code
Assembly Basics: Registers, operands,
move
Arithmetic & logical operations
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
Intel x86 Processors
Dominate laptop/desktop/server market
Evolutionary design
Backwards compatible up until 8086, introduced in
1978
Added more features as time goes on
Complex instruction set computer (CISC)
Many different instructions with many different
formats
But, only small subset encountered with Linux
programs
Hard to match performance of Reduced Instruction
Set Computers (RISC)
Computer
But, Systems:
IntelAhas
done
just Third
that!
t and OHallaron,
Programmers
Perspective,
Edition
Carnegie Mellon
Intel x86 Evolution: Milestones
Name
8086
Date Transistors MHz
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
3800
125M
2800-
First 64-bit Intel x86 processor, referred to as x86-64
Core 2
3500
2006
291M
1060-
First multi-core Intel processor
Core i7
2008
731M
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
1700-
Carnegie Mellon
Intel x86 Processors, cont.
Machine Evolution
386
Pentium
Pentium/MMX
PentiumPro
Pentium III
Pentium 4
Core 2 Duo
Core i7
1985
1993
1997
1995
1999
2001
2006
2008
0.3M
3.1M
4.5M
6.5M
8.2M
42M
291M
731M
Added Features
Instructions to support multimedia operations
Instructions to enable more efficient conditional
operations
Transition from 32 bits to 64 bits
More cores
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
Intels 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
t and OHallaron,
Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
Our Coverage
IA32
The traditional x86
For 15/18-213: RIP, Summer 2015
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
Carnegie Mellon
Today: Machine
Programming I: Basics
History of Intel processors and
architectures
C, assembly, machine code
Assembly Basics: Registers, operands,
move
Arithmetic & logical operations
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
10
Carnegie Mellon
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
t and OHallaron,
Computer Systems: A Programmers Perspective, Third Edition
11
Assembly/Machine Code
View
CPU
Registers
PC
Condition
Codes
Code
Data
Stack
Data
Instructions
PC: Program counter
Address of next instruction
Called RIP (x86-64)
Register file
Memory
Addresses
Programmer-Visible State
Heavily used program data
Carnegie Mellon
Memory
Byte addressable array
Code and user data
Stack to support
procedures
Condition codes
Store status information about
most recent arithmetic or logical
operation
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
12
Turning C into Object
Code
Code in files p1.c p2.c
Carnegie Mellon
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
te
C program (p1.c
p2.c)
xt
Compiler (gcc Og
-S)
Asm program (p1.s
te
p2.s)
xt
Assembler (gcc or
as)
bina
Object program (p1.o
Static
p2.o)
libraries (.a)
ry
Linker (gcc or
ld)
bina
Executable program (p)
ry
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
13
Carnegie Mellon
Compiling Into Assembly
C Code
long(sum.c)
plus(long
x, long y);
void sumstore(long x, long y,
long *dest)
{
long t = plus(x, y);
*dest = t;
}
Generated x86-64
Assembly
sumstore:
pushq
movq
call
movq
popq
ret
%rbx
%rdx, %rbx
plus
%rax, (%rbx)
%rbx
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.
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
14
Carnegie Mellon
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
15
Carnegie Mellon
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
16
Carnegie Mellon
Object Code
Code for
sumstore
0x0400595:
0x53
0x48
0x89
0xd3
0xe8
0xf2
0xff
0xff
0xff
0x48
0x89
0x03
0x5b
0xc3
Assembler
Translates .s into .o
Binary encoding of each instruction
Nearly-complete image of
executable code
Missing linkages between code in
different files
Total of 14
bytes
Each
instruction
1, 3, or 5
bytes
Starts at
address
0x0400595
Linker
Resolves references between files
Combines with static run-time
libraries
E.g., code for malloc, printf
Some libraries are dynamically
linked
Linking occurs when program
begins execution
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
17
Machine Instruction
Example
C Code
Carnegie Mellon
*dest = t;
Store value t where
designated by dest
movq %rax, (%rbx)
0x40059e:
48 89 03
Assembly
Move 8-byte value to
memory
Quad words in x86-64
parlance
Operands:
t: Register %rax
dest: Register %rbx
*dest: Memory M[%rbx]
Object Code
3-byte instruction
Stored at address 0x40059e
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
18
Disassembling Object
Code
Carnegie Mellon
Disassembled
0000000000400595
400595: 53
400596: 48 89
400599: e8 f2
40059e: 48 89
4005a1: 5b
4005a2: c3
<sumstore>:
d3
ff ff ff
03
push
mov
callq
mov
pop
retq
%rbx
%rdx,%rbx
400590 <plus>
%rax,(%rbx)
%rbx
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
19
Carnegie Mellon
Alternate Disassembly
Disassembled
Object
0x0400595:
0x53
0x48
0x89
0xd3
0xe8
0xf2
0xff
0xff
0xff
0x48
0x89
0x03
0x5b
0xc3
Dump of assembler code for function sumstore:
0x0000000000400595 <+0>: push
%rbx
0x0000000000400596 <+1>: mov
%rdx,%rbx
0x0000000000400599 <+4>: callq 0x400590 <plus>
0x000000000040059e <+9>: mov
%rax,(%rbx)
0x00000000004005a1 <+12>:pop
%rbx
0x00000000004005a2 <+13>:retq
Within gdb Debugger
gdb sum
disassemble sumstore
Disassemble procedure
x/14xb sumstore
Examine the 14 bytes starting at
sumstore
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
20
Carnegie Mellon
What Can be
Disassembled?
% objdump -d WINWORD.EXE
WINWORD.EXE:
file format pei-i386
No symbols in "WINWORD.EXE".
Disassembly of section .text:
30001000 <.text>:
30001000: 55
push
%ebp
Reverse
engineering
30001001: 8b ec
mov
%esp,%ebp
forbidden
by
30001003: 6a ff
push
$0xffffffff
30001005: 68 Microsoft
90 10 00 30 push
$0x30001090
End User
License
3000100a: 68 91 dc 4c 30 push
$0x304cdc91
Agreement
Anything that can be interpreted as
executable code
Disassembler examines bytes and
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
21
Carnegie Mellon
Today: Machine
Programming I: Basics
History of Intel processors and
architectures
C, assembly, machine code
Assembly Basics: Registers, operands,
move
Arithmetic & logical operations
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
22
Carnegie Mellon
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)
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
23
Carnegie Mellon
general purpose
Some History: IA32
Registers
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
16-bit virtual registers
(backwards compatibility)
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
stack
pointer
base
pointer
24
Carnegie Mellon
Moving Data
%rax
%rcx
Moving Data
movq Source, Dest:
%rdx
%rbx
Operand Types
Immediate: Constant integer data
%rsi
Example: $0x400, $-533
%rdi
Like C constant, but prefixed with $
%rsp
Encoded with 1, 2, or 4 bytes
Register: One of 16 integer registers %rbp
Example: %rax, %r13
%rN
But %rsp reserved for special use
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
25
Carnegie Mellon
movq Operand
Combinations
Source Dest
movq
Src,Dest
C Analog
Imm
Reg movq $0x4,%rax
Mem movq $-147,(%rax)
temp = 0x4;
Reg
Reg movq %rax,%rdx
Mem movq %rax,(%rdx)
temp2 = temp1;
Mem
Reg
temp = *p;
movq (%rax),%rdx
*p = -147;
*p = temp;
Cannot do memory-memory transfer with a
single instruction
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
26
Carnegie Mellon
Simple Memory
Addressing Modes
Normal
(R)
Mem[Reg[R]]
Register R specifies memory address
Aha! Pointer dereferencing in C
movq (%rcx),%rax
DisplacementD(R)
Mem[Reg[R]+D]
Register R specifies start of memory region
Constant displacement D specifies offset
movq 8(%rbp),%rdx
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
27
Carnegie Mellon
Example of Simple
Addressing Modes
void swap
(long *xp, long *yp)
{
long t0 = *xp;
long t1 = *yp;
*xp = t1;
*yp = t0;
}
swap:
movq
movq
movq
movq
ret
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
28
Carnegie Mellon
Understanding Swap()
void swap
(long *xp, long *yp)
{
long t0 = *xp;
long t1 = *yp;
*xp = t1;
*yp = t0;
}
Register
%rdi
%rsi
%rax
%rdx
Value
xp
yp
t0
t1
swap:
movq
movq
movq
movq
ret
Memory
Registers
%rdi
%rsi
%rax
%rdx
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
#
#
#
#
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
29
Carnegie Mellon
Understanding Swap()
Memory
Registers
%rdi
0x120
%rsi
0x100
Address
123
0x118
0x110
%rax
0x108
456
%rdx
swap:
movq
movq
movq
movq
ret
0x120
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
#
#
#
#
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
0x100
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
30
Carnegie Mellon
Understanding Swap()
Memory
Registers
%rdi
0x120
%rsi
0x100
%rax
123
Address
123
0x118
0x110
0x108
%rdx
swap:
movq
movq
movq
movq
ret
0x120
456
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
#
#
#
#
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
0x100
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
31
Carnegie Mellon
Understanding Swap()
Memory
Registers
%rdi
0x120
%rsi
0x100
%rax
123
%rdx
456
swap:
movq
movq
movq
movq
ret
Address
123
0x120
0x118
0x110
0x108
456
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
#
#
#
#
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
0x100
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
32
Carnegie Mellon
Understanding Swap()
Memory
Registers
%rdi
0x120
%rsi
0x100
%rax
123
%rdx
456
swap:
movq
movq
movq
movq
ret
Address
456
0x120
0x118
0x110
0x108
456
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
#
#
#
#
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
0x100
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
33
Carnegie Mellon
Understanding Swap()
Memory
Registers
%rdi
0x120
%rsi
0x100
%rax
123
%rdx
456
swap:
movq
movq
movq
movq
ret
Address
456
0x120
0x118
0x110
0x108
123
(%rdi), %rax
(%rsi), %rdx
%rdx, (%rdi)
%rax, (%rsi)
#
#
#
#
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
0x100
t0 = *xp
t1 = *yp
*xp = t1
*yp = t0
34
Carnegie Mellon
Simple Memory
Addressing Modes
Normal
(R)
Mem[Reg[R]]
Register R specifies memory address
Aha! Pointer dereferencing in C
movq (%rcx),%rax
DisplacementD(R)
Mem[Reg[R]+D]
Register R specifies start of memory region
Constant displacement D specifies offset
movq 8(%rbp),%rdx
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
35
Carnegie Mellon
Complete Memory Addressing
Modes
Most General Form
D(Rb,Ri,S) Mem[Reg[Rb]+S*Reg[Ri]+ D]
D:
Rb:
Ri:
S:
Constant displacement 1, 2, or 4 bytes
Base register: Any of 16 integer registers
Index register: Any, except for %rsp
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]]
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
36
Carnegie
Carnegie Mellon
Mellon
Address Computation
Examples
%rdx
0xf000
%rcx
0x0100
Expression
Address
Computation
Address
0x8(%rdx)
0xf000 + 0x8
0xf008
(%rdx,%rcx)
(%rdx,%rcx)
0xf000 + 0x100
0xf100
(%rdx,%rcx,4)
(%rdx,%rcx,4)
0x80(,%rdx,2)
0x80(,%rdx,2)
0xf000 + 4*0x100
0xf400
2*0xf000 + 0x80
0x1e080
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
37
Carnegie Mellon
Today: Machine
Programming I: Basics
History of Intel processors and
architectures
C, assembly, machine code
Assembly Basics: Registers, operands,
move
Arithmetic & logical operations
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
38
Carnegie
Carnegie Mellon
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
k = 1, 2, 4, or 8
Example
long
long m12(long
m12(long x)
x)Converted to ASM by compiler:
{
{
return
leaq
return x*12;
x*12;
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
39
Carnegie
Carnegie Mellon
Mellon
Some Arithmetic Operations
Two Operand Instructions:
FormatComputation
addq Src,Dest Dest
subq Src,Dest Dest
imulq Src,Dest Dest
salq Src,Dest Dest
sarq Src,Dest Dest
shrq Src,Dest Dest
xorq Src,Dest Dest
andq Src,Dest Dest
orq
Src,Dest Dest
=
=
=
=
=
=
=
=
=
Dest
Dest
Dest
Dest
Dest
Dest
Dest
Dest
Dest
+ Src
Src
* Src
<< Src Also called shlq
>> Src Arithmetic
>> Src Logical
^ Src
& Src
| Src
Watch out for argument order!
No distinction between signed and
unsigned int (why?)
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
40
Carnegie
Carnegie Mellon
Mellon
Some Arithmetic Operations
One Operand Instructions
incq
decq
negq
notq
Dest
Dest
Dest
Dest
Dest
Dest
Dest
Dest
=
=
=
=
Dest + 1
Dest 1
Dest
~Dest
See book for more instructions
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
41
Carnegie
Carnegie Mellon
Mellon
Arithmetic Expression
Example
arith:
long
long arith
arith
(long
(long x,
x, long
long y,
y, long
long z)
z)
{
{
long
long t1
t1 =
= x+y;
x+y;
long
long t2
t2 =
= z+t1;
z+t1;
long
long t3
t3 =
= x+4;
x+4;
long
long t4
t4 =
= y
y *
* 48;
48;
long
long t5
t5 =
= t3
t3 +
+ t4;
t4;
long
long rval
rval =
= t2
t2 *
* t5;
t5;
return
return rval;
rval;
}
}
leaq
addq
leaq
salq
leaq
imulq
ret
(%rdi,%rsi), %rax
%rdx, %rax
(%rsi,%rsi,2), %rdx
$4, %rdx
4(%rdi,%rdx), %rcx
%rcx, %rax
Interesting Instructions
leaq: address computation
salq: shift
imulq: multiplication
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
But, only used once
42
Carnegie
Carnegie Mellon
Mellon
Understanding Arithmetic
Expression Example
arith:
long
long arith
arith
(long
(long x,
x, long
long y,
y, long
long z)
z)
{
{
long
long t1
t1 =
= x+y;
x+y;
long
long t2
t2 =
= z+t1;
z+t1;
long
long t3
t3 =
= x+4;
x+4;
long
long t4
t4 =
= y
y *
* 48;
48;
long
long t5
t5 =
= t3
t3 +
+ t4;
t4;
long
long rval
rval =
= t2
t2 *
* t5;
t5;
return
return rval;
rval;
}
}
leaq
addq
leaq
salq
leaq
imulq
ret
(%rdi,%rsi), %rax
%rdx, %rax
(%rsi,%rsi,2), %rdx
$4, %rdx
4(%rdi,%rdx), %rcx
%rcx, %rax
Register
Use(s)
%rdi
Argument x
%rsi
Argument y
%rdx
Argument z
%rax
t1, t2, rval
%rdx
t4
%rcx
t5
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
# t1
# t2
# t4
# t5
# rval
43
Carnegie Mellon
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
t and OHallaron, Computer Systems: A Programmers Perspective, Third Edition
44
