0% found this document useful (0 votes)
15 views

Chapter03 Machine Level Programming(1)Basics

Uploaded by

info.bptrades
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
15 views

Chapter03 Machine Level Programming(1)Basics

Uploaded by

info.bptrades
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 43

CSC 322

SYSTEMS PROGRAMMING

MACHINE-LEVEL REPRESENTATION OF
PROGRAMS (1) – BASICS
(based on chapter 3.1-5)

Computer Systems: A Programmer’s Perspective 3rd Edition 1


AGENDA

o Historical Perspective
o Program Encoding: C, assembly, machine code
o Assembly Basics
o Arithmetic & Logical Operations

Computer Systems: A Programmer’s Perspective 3rd Edition 2


A HISTORICAL PERSPECTIVE

Computer Systems: A Programmer’s Perspective 3rd Edition 3


INTEL X86 PROCESSORS

oDominate laptop/desktop/server market


oEvolutionary design
• Backwards compatible up until 8086, introduced in 1978
• Added more features as time goes on
oComplex 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)
• But, Intel has done just that!
 In terms of speed. Less so for low power.

Computer Systems: A Programmer’s Perspective 3rd Edition 4


INTEL X86 EVOLUTION: MILESTONES
Name Date Transistors MHz
o 8086 1978 29K 5-10
• First 16-bit Intel processor. Basis for IBM PC & DOS
• 1MB address space

o 386 1985 275K 16-33


• First 32 bit Intel processor , referred to as IA32
• Added “flat addressing”, capable of running Unix

o Pentium 4E 2004 125M 2800-3800


• First 64-bit Intel x86 processor, referred to as x86-64

o Core 2 2006 291M 1060-3500


• First multi-core Intel processor

o Core i7 2008 731M 1700-3900


• Four cores (our shark machines)
Computer Systems: A Programmer’s Perspective 3rd Edition 5
STATE-OF-THE-ART PROCESSOR

oAdded Features
• Instructions to support multimedia operations
• Instructions to enable more efficient conditional operations
• Transition from 32 bits to 64 bits
• More cores

oCore i7 Broadwell 2015


• Desktop model
 4 cores, 3.3 – 3.8 GHz
 Integrated Graphics, 65W
• Server model
 8 cores, 2 – 2.6 GHz
 Integrated I/O, 45W
Computer Systems: A Programmer’s Perspective 3rd Edition 6
X86 CLONES: ADVANCED MICRO DEVICES (AMD)

o Historically
• AMD has followed just behind Intel
• A little bit slower, a lot cheaper
o 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
o Recent Years
• Intel got its act together
Leads the world in semiconductor technology
• AMD has fallen behind
Relies on external semiconductor manufacturer
Computer Systems: A Programmer’s Perspective 3rd Edition 7
INTEL’S 64-BIT HISTORY
o 2001: Intel Attempts Radical Shift from IA32 to IA64
• Totally different architecture (Itanium)
• Executes IA32 code only as legacy
• Performance disappointing
o 2003: AMD Steps in with Evolutionary Solution
• x86-64 (now called “AMD64”)
o Intel Felt Obligated to Focus on IA64
• Hard to admit mistake or that AMD is better
o 2004: Intel Announces EM64T extension to IA32
• Extended Memory 64-bit Technology
• Almost identical to x86-64!
o All but low-end x86 processors support x86-64
• But, lots of code still runs in 32-bit mode
Computer Systems: A Programmer’s Perspective 3rd Edition 8
OUR COVERAGE
o IA32
• The traditional x86
• For 15/18-213: RIP, Summer 2015

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

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

Computer Systems: A Programmer’s Perspective 3rd Edition 9


PROGRAM ENCODINGS

Computer Systems: A Programmer’s Perspective 3rd Edition 10


DEFINITIONS
o 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.

o Microarchitecture: Implementation of the architecture.


• Examples: cache sizes and core frequency.

o Code Forms:
• Machine Code: The byte-level programs that a processor executes
• Assembly Code: A text representation of machine code

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

Computer Systems: A Programmer’s Perspective 3rd Edition 11


ASSEMBLY/MACHINE CODE VIEW
Addresses
PC Registers Code
Data Data
Stack
Condition
Codes Instructions
CPU Memory
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
Computer Systems: A Programmer’s Perspective 3rd Edition 12
TURNING C INTO BINARY CODE

oCode in files p1.c p2.c


oCompile with command: C program (p1.c p2.c) text
gcc –Og p1.c p2.c -o p Compiler (gcc –Og -S)
Use basic optimizations (-Og)
[New to recent versions of GCC] Asm program (p1.s p2.s) text

Put resulting binary in file p Assembler (gcc or as)

Object program (p1.o p2.o) binary

Linker (gcc or ld)

Executable program (p) binary

Static libraries (.a)

Computer Systems: A Programmer’s Perspective 3rd Edition 13


COMPILING INTO ASSEMBLY
o C Code (sum.c) oGenerated 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
}

o Obtain with command


gcc –Og –S sum.c

o Produces file sum.s


o Note that that it will get very different results due to different
versions of gcc and different compiler settings.
Computer Systems: A Programmer’s Perspective 3rd Edition 14
ASSEMBLY CHARACTERISTICS: DATA TYPES

o“Integer” data of 1, 2, 4, or 8 bytes


• Data values
• Addresses (untyped pointers)
oFloating point data of 4, 8, or 10 bytes
oCode: Byte sequences encoding series of instructions
oNo aggregate types such as arrays or structures
• Just contiguously allocated bytes in memory

Computer Systems: A Programmer’s Perspective 3rd Edition 15


ASSEMBLY CHARACTERISTICS: DATA TYPES

oPerform arithmetic function on register or memory data


oTransfer data between memory and register
• Load data from memory into register
• Store register data into memory
oTransfer control
• Unconditional jumps to/from procedures
• Conditional branches

Computer Systems: A Programmer’s Perspective 3rd Edition 16


OBJECT CODE
o Assembler
• Obtain with command Code for sumstore
0x0400595:
gcc –Og –c sum.c
0x53
 Translates .s into .o 0x48
• Binary encoding of each instruction 0x89
0xd3
• Nearly-complete image of executable code 0xe8
• Missing linkages between code in different files 0xf2
0xff
o Linker • Total of 14 bytes 0xff
• Resolves references between files • Each instruction 0xff
1, 3, or 5 bytes 0x48
• Combines with static run-time libraries 0x89
• Starts at address
 Code for malloc, printf 0x03
0x0400595
• Some libraries are dynamically linked 0x5b
0xc3
 Linking occurs when program begins execution

Computer Systems: A Programmer’s Perspective 3rd Edition 17


MACHINE INSTRUCTION EXAMPLE
oC Code *dest = t;
• Store value t where designated by dest
oAssembly movq %rax, (%rbx)
• Move 8-byte value to memory
Quad words in x86-64 parlance
• Operands:
t: Register %rax
dest: Register %rbx
*dest: Memory M[%rbx]

oObject Code 0x40059e: 48 89 03


• 3-byte instruction
• Stored at address 0x40059e
Computer Systems: A Programmer’s Perspective 3rd Edition 18
DISASSEMBLING OBJECT CODE

oDisassembler
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
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
Computer Systems: A Programmer’s Perspective 3rd Edition 19
ALTERNATE DISASSEMBLY

oWithin gdb Debugger


gdb sum Object:
0x0400595:
disassemble sumstore 0x53
0x48
• Disassemble procedure 0x89
x/14xb sumstore 0xd3
0xe8
• Examine the 14 bytes starting at sumstore 0xf2
Disassembled: 0xff
Dump of assembler code for function sumstore: 0xff
0x0000000000400595 <+0>: push %rbx 0xff
0x0000000000400596 <+1>: mov %rdx,%rbx 0x48
0x0000000000400599 <+4>: callq 0x400590 <plus> 0x89
0x000000000040059e <+9>: mov %rax,(%rbx) 0x03
0x00000000004005a1 <+12>:pop %rbx 0x5b
0x00000000004005a2 <+13>:retq 0xc3

Computer Systems: A Programmer’s Perspective 3rd Edition 20


WHAT CAN BE DISASSEMBLED?

oAnything that can be interpreted as executable code


oDisassembler examines bytes and reconstructs assembly source
% 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
30001001: 8b ec mov %esp,%ebp
30001003: 6a ffReverse engineering
push forbidden by
$0xffffffff
30001005: 68Microsoft
90 10 00 End User License
30 push Agreement
$0x30001090
3000100a: 68 91 dc 4c 30 push $0x304cdc91

Computer Systems: A Programmer’s Perspective 3rd Edition 21


ASSEMBLY BASICS

Computer Systems: A Programmer’s Perspective 3rd Edition 22


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

o Can reference low-order 4 bytes (also low-order 1 & 2 bytes)


Computer Systems: A Programmer’s Perspective 3rd Edition 23
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)
Computer Systems: A Programmer’s Perspective 3rd Edition 24
MOVING DATA
%rax
o Moving Data (movb, movw, movl, movq) %rcx
movq Source, Dest:
%rdx
o Operand Types %rbx
• Immediate: Constant integer data %rsi
 Example: $0x400, $-533 %rdi
 Like C constant, but prefixed with ‘$’
%rsp
 Encoded with 1, 2, or 4 bytes
%rbp
• Register: One of 16 integer registers
 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”

Computer Systems: A Programmer’s Perspective 3rd Edition 25


MOVQ OPERAND COMBINATIONS

Source Dest Src,Dest C Analog

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


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

movq Reg movq %rax,%rdx temp2 = temp1;


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

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

Cannot do memory-memory transfer with a single instruction


Computer Systems: A Programmer’s Perspective 3rd Edition 26
SIMPLE MEMORY ADDRESSING MODES

oNormal: (R) Mem[Reg[R]]


• Register R specifies memory address
• Pointer dereferencing in C
movq (%rcx),%rax

oDisplacement: D(R) Mem[Reg[R]+D]


• Register R specifies start of memory region
• Constant displacement D specifies offset
movq 8(%rbp),%rdx

Computer Systems: A Programmer’s Perspective 3rd Edition 27


EXAMPLE OF SIMPLE ADDRESSING MODES

void swap swap:


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

Computer Systems: A Programmer’s Perspective 3rd Edition 28


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 swap:


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

Computer Systems: A Programmer’s Perspective 3rd Edition 29


UNDERSTANDING SWAP() – CONT’D
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

Computer Systems: A Programmer’s Perspective 3rd Edition 30


UNDERSTANDING SWAP() – CONT’D
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

Computer Systems: A Programmer’s Perspective 3rd Edition 31


UNDERSTANDING SWAP() – CONT’D
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

Computer Systems: A Programmer’s Perspective 3rd Edition 32


UNDERSTANDING SWAP() – CONT’D
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

Computer Systems: A Programmer’s Perspective 3rd Edition 33


UNDERSTANDING SWAP() – CONT’D
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

Computer Systems: A Programmer’s Perspective 3rd Edition 34


COMPLETE MEMORY ADDRESSING MODES

oMost 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?)

oSpecial 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]]

Computer Systems: A Programmer’s Perspective 3rd Edition 35


ADDRESS COMPUTATION EXAMPLES

%rdx 0xf000
%rcx 0x0100

Expression Address Computation Address


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

Computer Systems: A Programmer’s Perspective 3rd Edition 36


ARITHMETIC & LOGICAL
OPERATIONS

Computer Systems: A Programmer’s Perspective 3rd Edition 37


ADDRESS COMPUTATION INSTRUCTION

oleaq Src, Dst


• Src is address mode expression
• Set Dst to address denoted by expression
oUses
• 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

oExample
long m12(long x) Converted to ASM by compiler:
{ leaq (%rdi,%rdi,2), %rax # t <- x+x*2
return x*12; salq $2, %rax # return t<<2
}
Computer Systems: A Programmer’s Perspective 3rd Edition 38
SOME ARITHMETIC OPERATIONS
oTwo 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

oWatch out for argument order!


oNo distinction between signed and unsigned int (why?)
Computer Systems: A Programmer’s Perspective 3rd Edition 39
SOME ARITHMETIC OPERATIONS

oOne Operand Instructions


incq DestDest = Dest + 1
decq DestDest = Dest  1
negq DestDest =  Dest
notq DestDest = ~Dest

oSee book for more instructions

Computer Systems: A Programmer’s Perspective 3rd Edition 40


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

Computer Systems: A Programmer’s Perspective 3rd Edition 41


UNDERSTANDING ARITHMETIC
EXPRESSION EXAMPLE
arith:
long arith Leaq (%rdi,%rsi), %rax # t1
(long x, long y, long z) Addq %rdx, %rax # t2
{ leaq (%rsi,%rsi,2), %rdx
long t1 = x+y; Salq $4, %rdx # t4
long t2 = z+t1; Leaq 4(%rdi,%rdx), %rcx # t5
long t3 = x+4; Imulq %rcx, %rax # rval
long t4 = y * 48; ret
long t5 = t3 + t4;
long rval = t2 * t5; Register Use(s)
return rval; %rdi Argument x
}
%rsi Argument y
%rdx Argument z
%rax t1, t2, rval
%rdx t4
%rcx t5
Computer Systems: A Programmer’s Perspective 3rd Edition 42
MACHINE PROGRAMMING I: SUMMARY

o History of Intel processors and architectures


• Evolutionary design leads to many quirks and artifacts

o C, assembly, machine code


• New forms of visible state: program counter, registers, ...
• Compiler must transform statements, expressions, procedures into low-level
instruction sequences

o Assembly Basics: Registers, operands, move


• The x86-64 move instructions cover wide range of data movement forms

o Arithmetic
• C compiler will figure out different instruction combinations to carry out
computation

Computer Systems: A Programmer’s Perspective 3rd Edition 43

You might also like