PowerPoint Presentation – Introduction to Computer Systems 15-213/18-213
Machine language I
Copyright By PowCoder代写 加微信 powcoder
Acknowledgement: These slides are based on the textbook
(Computer Systems: A Programmer’s Perspective) and its slides.
Why do we learn machine language?
Programmers write programs in high-level languages
CPU runs the machine code
(compiled from a program)
Why do we learn machine code?
Understand compiler optimizations
Understand inefficiencies in codes
Understand the implementation of abstract concepts at the machine level
Understand vulnerabilities in codes
Executable file
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
Intel x86 Processors
Dominate laptop/desktop/server market
Complex instruction set computer (CISC)
A single instruction consists of several lower-level operations
Example 1: addq (%rdi),%rsi
It involves data transfer from memory, computation, saving result into register
Example 2: movq Source, Dest
Different memory addressing modes can be used
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Intel x86 Processors, cont.
Machine Evolution
Year # transistors
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
Example: Core i7 Broadwell in 2015
Desktop Model
Integrated graphics
3.3-3.8 GHz
Server Model
Integrated I/O
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
Definitions
Architecture: [ISA: instruction set architecture]
The parts of a processor design that one needs to understand or write assembly/machine code
It contains the specification of the instruction set and registers
Example ISAs:
Intel: IA32, x86-64
ARM: Used in almost all mobile phones
We will focus on the standard (x86-64)
gcc hello.c
gcc –m64 hello.c
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Definitions
Microarchitecture: Implementation of the architecture
Examples: https://en.wikipedia.org/wiki/List_of_Intel_CPU_microarchitectures
We will cover this part in lecture 6
Code Forms:
Machine Code: The byte-level programs that a processor executes
Assembly Code: A text representation of machine code
E.g., addq (%rdi),%rsi
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Assembly/Machine Code View
Programmer-Visible State
PC: Program counter
Address of next instruction
Called “RIP” (x86-64)
Register file
Heavily used program data
Condition codes
Store status information about most recent arithmetic / logical operation
Used for conditional branching
Instructions
Byte addressable array
Code and user data
Stack to support procedures
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Compiler (gcc –Og -S)
Assembler (gcc or as)
Linker (gcc or ld)
C program (p1.c p2.c)
Asm program (p1.s p2.s)
Object program (p1.o p2.o)
Executable program (p)
Static libraries (.a)
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) [e.g., O1, O2, O3]
Put resulting binary in file p
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Example C code
C Code (sum.c)
long plus(long x, long y);
void sumstore(long x, long y,
long *dest)
long t = plus(x, y);
*dest = t;
Variables x, y store values
dest is a pointer variable; it stores an address
*dest refers to the variable pointed to by dest
Note: In the executable program, registers may be used to store values of temporary variables
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Compiling Into Assembly:
gcc –O1 –S sum.c
C Code (sum.c)
long plus(long x, long y);
void sumstore(long x, long y,
long *dest)
long t = plus(x, y);
*dest = t;
Generated x86-64 Assembly
pushq %rbx
movq %rdx, %rbx
call plus
movq %rax, (%rbx)
popq %rbx
We may get different results on different machines (Linux, Mac OS-X, …) due to different versions of gcc and different compiler settings.
optimization, optional
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Assembly Characteristics: Data Types
“Integer” data of 1, 2, 4, 8 bytes
Data values
Addresses (untyped pointers)
Floating point data of 4, 8 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
Size of C Data Types in x86-64
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
cmpq %rsi, %rdi
jle .L4
movq %rdi, %rax
subq %rsi, %rax
movq %rsi, %rax
subq %rdi, %rax
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Code for sumstore
0x0400595:
Object Code
Translates .s into .o
Binary encoding of each instruction
Nearly-complete image of executable code
Missing linkages between code in different files
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
Total of 14 bytes
Each instruction 1, 3, or 5 bytes
Starts at address 0x0400595
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Code for sumstore
0x0400595:
Object Code
Total of 14 bytes
Each instruction 1, 3, or 5 bytes
Starts at address 0x0400595
0000000000400595
400595: 53 push %rbx
400596: 48 89 d3 mov %rdx,%rbx
400599: e8 f2 ff ff ff callq 400590
4005a1: 5b pop %rbx
4005a2: c3 retq
Disassembled
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Machine Instruction Example
Store value t at the memory pointed to by dest
Move 8-byte value to memory
t: Register %rax
dest: Register %rbx
*dest: Memory M[%rbx]
Object Code
3-byte instruction
Stored at address 0x40059e
*dest = t;
movq %rax, (%rbx)
0x40059e: 48 89 03
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Disassembled
Disassembling Object Code
Disassembler
objdump –d sum
Useful tool for examining the instructions in object code
Can be run on either a.out (complete executable) or .o file
0000000000400595
400595: 53 push %rbx
400596: 48 89 d3 mov %rdx,%rbx
400599: e8 f2 ff ff ff callq 400590
4005a1: 5b pop %rbx
4005a2: c3 retq
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Disassembled
Dump of assembler code for function sumstore:
0x0000000000400595 <+0>: push %rbx
0x0000000000400596 <+1>: mov %rdx,%rbx
0x0000000000400599 <+4>: callq 0x400590
0x00000000004005a1 <+12>:pop %rbx
0x00000000004005a2 <+13>:retq
Alternate Disassembly
Within gdb Debugger
disassemble sumstore
Disassemble procedure
x/14xb sumstore
Examine the 14 bytes starting at sumstore
0x0400595:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
x86-64 Integer Registers
Can reference low-order 4 bytes (also low-order 1 & 2 bytes)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Size of C Data Types in x86-64
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Moving Data
Moving Data
movq Source, Dest
Operand Types
Immediate: Constant integer data
Example: $0x400, $-533
Like C constant, but prefixed with ‘$’
Encoded with 1, 2, or 4 bytes
Register: One of 16 integer registers
Example: %rax, %r13
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”
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
movq Operand Combinations
Cannot do memory-memory transfer with a single instruction!
movq $0x4,%rax
temp = 0x4;
movq $-147,(%rax)
*p = -147;
movq %rax,%rdx
temp2 = temp1;
movq %rax,(%rdx)
*p = temp;
movq (%rax),%rdx
temp = *p;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Simple Memory Addressing Modes
Normal (R) Mem[Reg[R]]
Register R specifies memory address
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
Example of Simple Addressing Modes
(long *xp, long *yp)
long t0 = *xp;
long t1 = *yp;
movq (%rdi), %rax
movq (%rsi), %rdx
movq %rdx, (%rdi)
movq %rax, (%rsi)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
(long *xp, long *yp)
long t0 = *xp;
long t1 = *yp;
Register Value
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Swap()
movq (%rdi), %rax # t0 = *xp
movq (%rsi), %rdx # t1 = *yp
movq %rdx, (%rdi) # *xp = t1
movq %rax, (%rsi) # *yp = t0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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]]
May be useful in for-loop?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Expression Address Computation Address
(%rdx,%rcx)
(%rdx,%rcx,4)
0x80(,%rdx,2)
Address Computation Examples
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
%rdx 0xf000
%rcx 0x0100
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
0xf000 + 0x8 = 0xf008
0xf000 + 0x0100 = 0xf100
0xf000 + 4*0x0100 = 0xf400
2*0xf000 + 0x80 = 0x1d080
Summary on Memory Addressing
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
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
Some Arithmetic Operations
Two Operand Instructions:
Format Computation
addq Src, = Dest + Src
subq Src, = Dest Src
imulq Src, = Dest * Src
salq Src, = Dest << Src Also called shlq
sarq Src, = Dest >> Src Arithmetic
shrq Src, = Dest >> Src Logical
xorq Src, = Dest ^ Src
andq Src, = Dest & Src
orq Src, = 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
Some Arithmetic Operations
One Operand Instructions
incq = Dest + 1
decq = Dest 1
negq = Dest
notq = ~Dest
Please check the costs of instructions here:
https://www.agner.org/optimize/instruction_tables.pdf
(see pages 222-236 for Intel Broadwell CPU)
Some instructions are more time consuming than others
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Address Computation Instruction
leaq Src, is address mode expression
Set Dst to address denoted by expression
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
long m12(long x)
return x*12;
leaq (%rdi,%rdi,2), %rax # t <- x+x*2
salq $2, %rax # return t<<2
Converted to ASM by compiler:
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Arithmetic Expression Example
Interesting Instructions
leaq: address computation
salq: shift
imulq: multiplication
But, only used once
long arith
(long x, long y, long z)
long t1 = x+y;
long t2 = z+t1;
long t3 = x+4;
long t4 = y * 48;
long t5 = t3 + t4;
long rval = t2 * t5;
return rval;
leaq (%rdi,%rsi), %rax
addq %rdx, %rax
leaq (%rsi,%rsi,2), %rdx
salq $4, %rdx
leaq 4(%rdi,%rdx), %rcx
imulq %rcx, %rax
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Understanding Arithmetic Expression Example
long arith
(long x, long y, long z)
long t1 = x+y;
long t2 = z+t1;
long t3 = x+4;
long t4 = y * 48;
long t5 = t3 + t4;
long rval = t2 * t5;
return rval;
leaq (%rdi,%rsi), %rax # t1
addq %rdx, %rax # t2
leaq (%rsi,%rsi,2), %rdx
salq $4, %rdx # t4
leaq 4(%rdi,%rdx), %rcx # t5
imulq %rcx, %rax # rval
Register Use(s)
%rdi Argument x
%rsi Argument y
%rdx Argument z
%rax t1, t2, rval
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Machine Programming I: Summary
History of Intel processors and architectures
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 generate faster code
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com