Chapter 2 Instructions Language Of The Computer.ppt
Chapter 2 Instructions: Language p of the Computer The repertoire of instructions of a co pute computer Different computers have different instruction sets But with many aspects in common Early computers had very simple instruction sets §2.1 Intro oduction Instruction Set Simplified p implementation p Many modern computers also have simple instruction sets Chapter 2 — Instructions: Language of the Computer — 2
The MIPS Instruction Set Used as the example throughout the book Stanford MIPS commercialized by MIPS Technologies (www.mips.com) Large share of embedded core market Applications in consumer electronics, network/storage equipment, cameras, printers, Typical of many modern ISAs See MIPS Reference Data tear-out card, and A Appendixes di B and dE Chapter 2 — Instructions: Language of the Computer — 3 Add and subtract, three operands Two sources and one destination add a, b, c # a gets b c All arithmetic operations have this form Design g Principle 1: Simplicityy favours regularity §2.2 Ope erations off the Comp puter Hard dware Arithmetic Operations Regularity g y makes implementation p simpler p Simplicity enables higher performance at lower cost Chapter 2 — Instructions: Language of the Computer — 4
Arithmetic Example C code: f (g ( h) - (i j); j) Compiled p MIPS code: add t0, g, h add t1, t1 i, i j sub f, t0, t1 # temp t0 g h # temp t1 i j # f t0 - t1 Chapter 2 — Instructions: Language of the Computer — 5 Arithmetic instructions use register operands MIPS has a 32 32-bit register file Assembler names Use for frequently accessed data N b d 0 tto 31 Numbered 32-bit data called a “word” t0, t1, , t9 for temporary values s0, s1, , s7 for saved variables §2.3 Ope erands of tthe Compu uter Hardw ware Register Operands Design Principle 2: Smaller is faster c.f. main memory: millions of locations Chapter 2 — Instructions: Language of the Computer — 6
Register Operand Example C code: f (g h) - (i j); f, , j in s0, , s4 C Compiled il d MIPS code: d add t0, s1, s2 add dd t1, t1 s3, 3 s4 4 sub s0, t0, t1 Chapter 2 — Instructions: Language of the Computer — 7 Memory Operands Main memory used for composite data To apply arithmetic operations Each address identifies an 8-bit byte Words are aligned in memory Load values from memory into registers Store result from register to memory Memory is byte addressed Arrays, structures, dynamic data Address must be a multiple of 4 MIPS is Big Endian Most-significant byte at least address of a word c.f. Little Endian: least-significant byte at least address Chapter 2 — Instructions: Language of the Computer — 8
Memory Operand Example 1 C code: g h A[8]; g in s1, h in s2, base address of A in s3 C Compiled il d MIPS code: d Index 8 requires offset of 32 4 bytes per word lw t0, 32( s3) add s1, s1 s2, s2 t0 offset # load word base register Chapter 2 — Instructions: Language of the Computer — 9 Memory Operand Example 2 C code: A[12] h A[8]; h in s2, base address of A in s3 C Compiled il d MIPS code: d Index 8 requires offset of 32 lw t0, 32( s3) # load word add t0, s2, t0 sw t0, t0 48( s3) # store word Chapter 2 — Instructions: Language of the Computer — 10
Registers vs. Memory Registers are faster to access than e oy memory Operating on memory data requires loads and stores More instructions to be executed Compiler must use registers for variables as much as possible Onlyy spill p to memory y for less frequently q y used variables Register optimization is important! Chapter 2 — Instructions: Language of the Computer — 11 Immediate Operands Constant data specified in an instruction addi s3, s3 s3, s3 4 No subtract immediate instruction J Just use a negative i constant addi s2, s1, -1 Design D i P Principle i i l 3 3: Make M k the th common case fast Small constants are common Immediate operand avoids a load instruction Chapter 2 — Instructions: Language of the Computer — 12
The Constant Zero MIPS register 0 ( zero) is the constant 0 Cannot be overwritten Useful for common operations E.g., move between E b registers i add t2, s1, zero Chapter 2 — Instructions: Language of the Computer — 13 Given an n-bit number x Range: 0 to 2n – 1 Example x n 1 2n 1 x n 2 2n 2 x1 21 x 0 20 §2.4 Sign ned and U Unsigned N Numbers Unsigned Binary Integers 0000 0000 0000 0000 0000 0000 0000 10112 0 1 23 0 22 1 21 1 20 0 8 0 2 1 1110 Using 32 bits 0 to o 4,294,967,295 , 9 ,96 , 95 Chapter 2 — Instructions: Language of the Computer — 14
2s-Complement Signed Integers Given an n-bit number x Range: –2 2n – 1 to 2n – 1 – 1 Example x n 1 2n 1 x n 2 2n 2 x1 21 x 0 20 1111 1111 1111 1111 1111 1111 1111 11002 –1 231 1 230 1 22 0 21 0 20 –2,147,483,648 2,147,483,644 –410 Using 32 bits –2,147,483,648 , , 83,6 8 to o 2,147,483,647 , , 83,6 Chapter 2 — Instructions: Language of the Computer — 15 2s-Complement Signed Integers Bit 31 is sign bit 1 for negative numbers 0 for non-negative numbers –(–2n – 1) can’t be represented Non-negative numbers have the same unsigned and 2s-complement representation Some specific numbers 0: 0000 0000 0000 –1: 1111 1111 1111 Most-negative: 1000 0000 0000 Most-positive: 0111 1111 1111 Chapter 2 — Instructions: Language of the Computer — 16
Signed Negation Complement and add 1 Complement means 1 0, 0 0 1 x x 1111.1112 1 x 1 x Example: negate 2 2 2 0000 0000 00102 –2 1111 1111 11012 1 1111 1111 11102 Chapter 2 — Instructions: Language of the Computer — 17 Sign Extension Representing a number using more bits In MIPS instruction set addi: extend immediate value lb lh: lb, lh extend loaded byte/halfword / f beq, bne: extend the displacement Replicate the sign bit to the left Preserve the numeric value c.f. unsigned values: extend with 0s Examples: a p es 8 8-bit b t to 16-bit 6 bt 2: 0000 0010 0000 0000 0000 0010 –2: 1111 1110 1111 1111 1111 1110 Chapter 2 — Instructions: Language of the Computer — 18
Instructions are encoded in binary MIPS instructions Called machine code Encoded as 32-bit instruction words Small number of formats encoding operation code (opcode), register numbers, Regularity! Register numbers §2.5 Rep presenting Instructio ons in the C Computer Representing Instructions t0 0 – t7 are reg’s ’ 8 – 15 1 t8 – t9 are reg’s 24 – 25 s0 – s7 are reg’s reg s 16 – 23 Chapter 2 — Instructions: Language of the Computer — 19 MIPS R-format Instructions op rs rt rd shamt funct 6 bit bits 5 bit bits 5 bit bits 5 bit bits 5 bit bits 6 bit bits Instruction fields op: operation code (opcode) rs: first source register number rt: second source register number rd: destination register number shamt: shift amount (00000 for now) funct: function code ((extends opcode)) Chapter 2 — Instructions: Language of the Computer — 20
R-format Example op rs rt rd shamt funct 6 bit bits 5 bit bits 5 bit bits 5 bit bits 5 bit bits 6 bit bits add t0, , s1, , s2 special s1 s2 t0 0 add 0 17 18 8 0 32 000000 10001 10010 01000 00000 100000 000000100011001001000000001000002 0232402016 Chapter 2 — Instructions: Language of the Computer — 21 Hexadecimal Base 16 0 1 2 3 Compact representation of bit strings 4 bits per hex digit 0000 0001 0010 0011 4 5 6 7 0100 0101 0110 0111 8 9 a b 1000 1001 1010 1011 c d e f 1100 1101 1110 1111 Example: eca8 6420 1110 1100 1010 1000 0110 0100 0010 0000 Chapter 2 — Instructions: Language of the Computer — 22
MIPS I-format Instructions rs rt constant or address 6 bit bits 5 bit bits 5 bit bits 16 bit bits Immediate arithmetic and load/store instructions op rt: t destination d ti ti or source register i t number b 15 15 Constant: –2 to 2 – 1 Address: dd ess o offset set added to base add address ess in rs s Design Principle 4: Good design demands good compromises Different formats complicate decoding, but allow 32-bit instructions uniformly Keep formats as similar as possible Chapter 2 — Instructions: Language of the Computer — 23 Stored Program Computers The BIG Picture Instructions represented in binary, just like data Instructions and data stored in memory P Programs can operate t on programs e g compilers e.g., compilers, linkers linkers, Binary compatibility allows compiled programs g to work on different computers Standardized ISAs Chapter 2 — Instructions: Language of the Computer — 24
Instructions for bitwise manipulation Operation C Java MIPS Shift left sll Shift right srl Bitwise AND & & and, andi Bitwise OR i or, ori Bitwise NOT nor §2.6 Logical Opera ations Logical Operations Useful for extracting and inserting groups of bits in a word Chapter 2 — Instructions: Language of the Computer — 25 Shift Operations rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits shamt: how many positions to shift Shift left logical op Shift left and fill with 0 bits sll by i bits multiplies by 2i Shift right logical Shift right and fill with 0 bits srl by i bits divides by 2i (unsigned only) Chapter 2 — Instructions: Language of the Computer — 26
AND Operations Useful to mask bits in a word Select some bits, bits clear others to 0 and t0, t1, t2 t2 0000 0000 0000 0000 0000 1101 1100 0000 t1 0000 0000 0000 0000 0011 1100 0000 0000 t0 0000 0000 0000 0000 0000 1100 0000 0000 Chapter 2 — Instructions: Language of the Computer — 27 OR Operations Useful to include bits in a word Set some bits to 1, 1 leave others unchanged or t0, t1, t2 t2 0000 0000 0000 0000 0000 1101 1100 0000 t1 0000 0000 0000 0000 0011 1100 0000 0000 t0 0000 0000 0000 0000 0011 1101 1100 0000 Chapter 2 — Instructions: Language of the Computer — 28
NOT Operations Useful to invert bits in a word Change 0 to 1 1, and 1 to 0 MIPS has NOR 3-operand instruction a NOR b NOT ( a OR b ) nor t0, t1, zero Register 0: always read as zero t1 0000 0000 0000 0000 0011 1100 0000 0000 t0 1111 1111 1111 1111 1100 0011 1111 1111 Chapter 2 — Instructions: Language of the Computer — 29 Branch to a labeled instruction if a condition co d t o is s ttrue ue beq rs, rt, L1 if (rs rt) branch to instruction labeled L1; bne rs, rt, L1 Otherwise, continue sequentially §2.7 Instructions fo or Making Decisions s Conditional Operations if (rs ! rt) branch to instruction labeled L1; j L1 unconditional jump to instruction labeled L1 Chapter 2 — Instructions: Language of the Computer — 30
Compiling If Statements C code: if (i (i j) j) f g h; else f g-h; f g, f, g in s0, s0 s1 s1, Compiled MIPS code: bne add j Else: sub Exit: s3, s4, Else s0, s1, s2 Exit s0, s1, s2 Assembler calculates addresses Chapter 2 — Instructions: Language of the Computer — 31 Compiling Loop Statements C code: while (save[i] k) i 1; i in s3, k in s5, address of save in s6 Compiled MIPS code: Loop: sll add lw bne addi j Exit: t1, t1, t1 t0, t0, s3, s3 Loop s3, 2 t1, t1 s6 0( t1) s5, Exit s3, s3 1 Chapter 2 — Instructions: Language of the Computer — 32
Basic Blocks A basic block is a sequence of instructions with No embedded branches (except at end) No branch targets (except at beginning) A compiler il id identifies tifi b basic i blocks for optimization An advanced processor can accelerate execution of basic blocks Chapter 2 — Instructions: Language of the Computer — 33 More Conditional Operations Set result to 1 if a condition is true slt rd, rs, rt if ((rs rt)) rd d 1 1; else l rd d 0 0; slti rt, rs, constant Otherwise set to 0 Otherwise, if (rs constant) rt 1; else rt 0; Use in combination with beq, q, bne slt t0, s1, s2 bne t0, zero, L # if ( s1 s2) # branch to L Chapter 2 — Instructions: Language of the Computer — 34
Branch Instruction Design Why not blt, bge, etc? Hardware for , , slower than , Combining with branch involves more work per instruction instruction, requiring a slower clock All instructions penalized! beq and b d bne b are the th common case This is a good design compromise Chapter 2 — Instructions: Language of the Computer — 35 Signed vs. Unsigned Signed comparison: slt, slti Unsigned comparison: sltu, sltu sltui Example s0 1111 1111 1111 1111 1111 1111 1111 1111 s1 0000 0000 0000 0000 0000 0000 0000 0001 slt t0, s0, s1 # signed –1 1 t0 1 sltu t0, s0, s1 # unsigned 4,294,967,295 1 t0 0 Chapter 2 — Instructions: Language of the Computer — 36
Steps required 1. 1 2. 3 3. 4. 5 5. 6. Place parameters in registers Transfer control to procedure Acquire storage for procedure Perform procedure’s operations Pl Place resultlt in i register i t for f caller ll Return to place of call §2.8 Sup pporting Prrocedures in Compu uter Hardw ware Procedure Calling Chapter 2 — Instructions: Language of the Computer — 37 Register Usage a0 – a3: arguments (reg’s 4 – 7) v0,, v1: result values ((reg’s g 2 and 3)) t0 – t9: temporaries s0 – s7: saved Can be overwritten by callee Must be saved/restored by callee gp: global l b l pointer i t ffor static t ti d data t ((reg 28) sp: stack pointer (reg 29) f frame fp: f pointer i t (reg ( 30) ra: return address (reg 31) Chapter 2 — Instructions: Language of the Computer — 38
Procedure Call Instructions Procedure call: jump and link jal ProcedureLabel Address of following instruction put in ra Jumps to target address Procedure return: jump register jr ra Copies ra to program counter Can also be used for computed jumps e.g., for case/switch statements Chapter 2 — Instructions: Language of the Computer — 39 Leaf Procedure Example C code: int leaf example leaf example (int g, g h, h i, i j) { int f; f (g h) ) - ( (i j); return f; } Arguments g, , j in a0, , a3 f in s0 ( (hence, need to save s0 on stack)) Result in v0 Chapter 2 — Instructions: Language of the Computer — 40
Leaf Procedure Example MIPS code: leaf example: leaf example: addi sp, sp, -4 sw s0, 0( sp) add dd t0, t0 a0, 0 a1 1 add t1, a2, a3 sub s0, , t0, , t1 add v0, s0, zero lw s0, 0( sp) addi sp sp, sp, sp 4 jr ra Save s0 on stack Procedure body Result Restore s0 Return Chapter 2 — Instructions: Language of the Computer — 41 Non-Leaf Procedures Procedures that call other procedures For nested call call, caller needs to save on the stack: Its return It t address dd Any arguments and temporaries needed after the call Restore from the stack after the call Chapter 2 — Instructions: Language of the Computer — 42
Non-Leaf Procedure Example C code: int fact (int n) { if ( (n 1) ) return etu f; ; else return n * fact(n - 1); } Argument n in a0 Result in v0 Chapter 2 — Instructions: Language of the Computer — 43 Non-Leaf Procedure Example MIPS code: fact: addi sw sw slti beq addi addi j jr L1: addi jal lw lw addi mul jr sp, ra, a0, t0, t0, v0, sp, ra a0, fact a0, , ra, sp, v0, ra sp, -8 4( sp) 0( sp) a0, 1 zero, L1 zero, 1 sp, 8 a0, -1 0( sp) ( p) 4( sp) sp, 8 a0, v0 # # # # adjust stack for 2 items save return address save argument test for n 1 # # # # # # # # # # if so, result is 1 pop 2 items from stack and d return else decrement n recursive call restore original g n and return address pop 2 items from stack multiply to get result and return Chapter 2 — Instructions: Language of the Computer — 44
Local Data on the Stack Local data allocated byy callee e.g., C automatic variables Procedure frame (activation record) U db Used by some compilers il tto manage stack t k storage t Chapter 2 — Instructions: Language of the Computer — 45 Memory Layout Text: program code Static data: global g variables Dynamic data: heap e.g., static variables in C, constant arrays and strings gp initialized to address allowing offsets into this segment E.g., E g malloc in C C, new in Java Stack: automatic storage Chapter 2 — Instructions: Language of the Computer — 46
Byte-encoded character sets ASCII: 128 characters Latin-1: 256 characters 95 graphic, 33 control ASCII, 96 more graphic characters §2.9 Com mmunicatin ng with Pe eople Character Data Unicode: 32 32-bit bit character set Used in Java, C wide characters, M t off the Most th world’s ld’ alphabets, l h b t plus l symbols b l UTF-8, UTF-16: variable-length encodings Chapter 2 — Instructions: Language of the Computer — 47 Byte/Halfword Operations Could use bitwise operations MIPS byte/halfword load/store String processing is a common case lb rt, offset(rs) ff ( ) Sign extend to 32 bits in rt lb rt, offset(rs) lbu ff ( ) lhu lh rt, offset(rs) ff ( ) Zero extend to 32 bits in rt sb b rt, offset(rs) ff ( ) lh rt, offset(rs) ff ( ) sh h rt, offset(rs) ff ( ) Store just rightmost byte/halfword Chapter 2 — Instructions: Language of the Computer — 48
String Copy Example C code (naïve): Null-terminated Null terminated string void strcpy (char x[], char y[]) { int i; i 0; while ((x[i] y[i])! '\0') (( [ ] y[ ]) \ ) i 1; } Addresses of x, y in a0, a1 i in s0 Chapter 2 — Instructions: Language of the Computer — 49 String Copy Example MIPS code: strcpy: addi sw add L1: add lbu add sb b beq addi j L2: lw addi jr sp, s0, s0, t1, t2, t3, t2, t2, 2 s0, L1 s0, , sp, ra sp, -4 0( sp) zero, zero s0, a1 0( t1) s0, a0 0( t3) zero, L2 2 s0, 1 0( sp) ( p) sp, 4 # # # # # # # # # # # # # adjust stack for 1 item save s0 i 0 addr of y[i] in t1 t2 y[i] addr of x[i] in t3 x[i] y[i] exit i loop l if y[i] [i] 0 i i 1 next iteration of loop restore saved s0 pop 1 item from stack and return Chapter 2 — Instructions: Language of the Computer — 50
Most constants are small 16 bit immediate is sufficient 16-bit For the occasional 32-bit constant l i rt, constant lui Copies 16-bit constant to left 16 bits of rt Clears right 16 bits of rt to 0 lhi s0, 61 0000 0000 0111 1101 0000 0000 0000 0000 ori s0, , s0, , 2304 0000 0000 0111 1101 0000 1001 0000 0000 §2.10 MIPS Addres ssing for 3 32-Bit Imm mediates and Addressses 32-bit Constants Chapter 2 — Instructions: Language of the Computer — 51 Branch Addressing Branch instructions specify Opcode two registers, Opcode, registers target address Most branch targets are near branch F Forward d or backward b k d op rs rt constant or address 6 bits 5 bits 5 bits 16 bits PC relative addressing PC-relative Target address PC offset 4 PC already l d incremented i t d by b 4 by b thi this titime Chapter 2 — Instructions: Language of the Computer — 52
Jump Addressing Jump (j and jal) targets could be anywhere in text segment Encode full address in instruction op address 6 bits 26 bits (Pseudo)Direct jump addressing Target address PC31 28 : (address 4) Chapter 2 — Instructions: Language of the Computer — 53 Target Addressing Example Loop code from earlier example Assume Loop at location 80000 Loop: sll t1, s3, 2 80000 0 0 19 9 4 0 add t1, t1, s6 80004 0 9 22 9 0 32 lw t0, 0( t1) 80008 35 9 8 0 bne t0, s5, Exit 80012 5 8 21 2 19 19 1 addi s3, s3, 1 80016 8 j 80020 2 Exit: Loop 20000 80024 Chapter 2 — Instructions: Language of the Computer — 54
Branching Far Away If branch target is too far to encode with 16-bit offset, offset assembler rewrites the code Example b beq s0, s1, 0 1 L1 b bne s0, s1, 0 1 L2 2 j L1 L2: Chapter 2 — Instructions: Language of the Computer — 55 Addressing Mode Summary Chapter 2 — Instructions: Language of the Computer — 56
Two processors sharing an area of memory P1 writes, then P2 reads Data race if P1 and P2 don’t synchronize Hardware support required Result depends of order of accesses Atomic read/write memory operation No other access to the location allowed between the read and write Could be a single instruction §2.11 Parallelism a and Instruc ctions: Syn nchronizattion Synchronization E.g., atomic swap of register memory Or an atomic pair of instructions Chapter 2 — Instructions: Language of the Computer — 57 Synchronization in MIPS Load linked: ll rt, offset(rs) Store conditional: sc rt, , offset(rs) ( ) Succeeds if location not changed since the ll Fails if location is changed Returns 1 in rt Returns 0 in rt Example: p atomic swap p ((to test/set lock variable)) try: add ll sc beq add t0, zero, s4 t1,0( s1) t0,0( s1) t0 0( s1) t0, zero,try s4, zero, t1 ;copy exchange value ;load linked ;store conditional ;branch store fails ;put load value in s4 Chapter 2 — Instructions: Language of the Computer — 58
Many compilers produce object modules directly Static linking §2.12 Tra anslating a and Startin ng a Progrram Translation and Startup Chapter 2 — Instructions: Language of the Computer — 59 Assembler Pseudoinstructions Most assembler instructions represent machine instructions one-to-one Pseudoinstructions: figments of the assembler’s assembler s imagination add t0, zero, t1 blt t0, t1, L slt at, t0, t1 move t0, t1 bne at, zero, L t ((register at i t 1) 1): assembler bl ttemporary Chapter 2 — Instructions: Language of the Computer — 60
Producing an Object Module Assembler (or compiler) translates program into machine instructions Provides information for building a complete program from the pieces Header: H d d described ib d contents t t off object bj t module d l Text segment: translated instructions Static data segment: data allocated for the life of the program Relocation info: for contents that depend on absolute location of loaded program Symbol table: global definitions and external refs Debug info: for associating with source code Chapter 2 — Instructions: Language of the Computer — 61 Linking Object Modules Produces an executable image 1. Merges segments 1 2. Resolve labels (determine their addresses) 3 Patch location-dependent 3. location dependent and external refs Could leave location dependencies for fi i b fixing by a relocating l ti lloader d But with virtual memory, no need to do this Program can be loaded into absolute location in virtual memory space Chapter 2 — Instructions: Language of the Computer — 62
Loading a Program Load from image file on disk into memory 1. Read header to determine segment sizes 1 2. Create virtual address space 3 Copy text and initialized data into memory 3. Or set page table entries so they can be faulted in 4. Set up arguments on stack 4 5. Initialize registers (including sp, fp, gp) 6 Jump 6. J to t startup t t routine ti Copies arguments to a0, and calls main When main returns returns, do exit syscall Chapter 2 — Instructions: Language of the Computer — 63 Dynamic Linking Only link/load library procedure when it is called Requires procedure code to be relocatable Avoids image bloat caused by static linking of all (transitively) referenced libraries Automatically picks up new library versions Chapter 2 — Instructions: Language of the Computer — 64
Lazy Linkage Indirection table Stub: Loads routine ID, Jump to linker/loader Linker/loader code Dynamically mapped code Chapter 2 — Instructions: Language of the Computer — 65 Starting Java Applications Si l portable Simple t bl instruction set for the JVM Compiles bytecodes of “hot” methods into native code for host machine Interprets bytecodes Chapter 2 — Instructions: Language of the Computer — 66
Illustrates use of assembly instructions o a C bubb bubble e so sortt function u ct o for Swap procedure (leaf) void swap(int v[], int k) { int temp; t temp v[k]; [k] v[k] v[k 1]; v[k 1] [ ] temp; p; } v in a0, k in a1, temp in t0 §2.13 A C Sort Exa ample to P Put It All To ogether C Sort Example Chapter 2 — Instructions: Language of the Computer — 67 The Procedure Swap swap: sll t1, a1, 2 # t1 k * 4 add t1, a0, t1 # t1 v (k*4) # (address of v[k]) lw t0, 0( t1) # t0 (temp) v[k] lw t2, 4( t1) # t2 v[k 1] sw t2, 0( t1) # v[k] t2 (v[k 1]) sw t0, 4( t1) # v[k 1] t0 (temp) jr ra j # return to calling g routine Chapter 2 — Instructions: Language of the Computer — 68
The Sort Procedure in C Non-leaf (calls swap) void sort (int v[], int n) { int i, j; (i 0; ; i n; ; i 1) ) { for ( for (j i – 1; j 0 && v[j] v[j 1]; j - 1) { swap(v,j); } } } v in a0,, k in a1,, i in s0,, j in s1 Chapter 2 — Instructions: Language of the Computer — 69 The Procedure Body move move move for1tst: slt beq addi for2tst: slti bne sll add lw lw slt beq move move jal addi j exit2: addi j s2, a0 s3, a1 s0, zero t0 t0, s0 s0, s3 t0, zero, exit1 s1, s0, –1 t0, s1, 0 t0, t0 zero, zero exit2 t1, s1, 2 t2, s2, t1 t3, 0( t2) t4, t4 4( t2) t0, t4, t3 t0, zero, exit2 a0, s2 a1, a1 s1 swap s1, s1, –1 for2tst s0 s0, s0, s0 1 for1tst # # # # # # # # # # # # # # # # # # # # # save a0 into s2 save a1 into s3 i 0 t0 0 if s0 s3 (i n) go to exit1 if s0 s3 (i n) j i – 1 t0 1 if s1 0 (j 0) go to exit2 if s1 0 (j 0) t1 j * 4 t2 v (j * 4) t3 v[j] t4 v[j 1] t0 0 if t4 t3 go to exit2 if t4 t3 1st param of swap is v (old a0) 2nd param of swap is j call swap procedure j – 1 jump to test of inner loop i 1 jump to test of outer loop Move params Outer loop p Inner loop Pass params & call Inner loop Outer loop Chapter 2 — Instructions: Language of the Computer — 70
The Full Procedure sort: addi sp, sp, –20 sw ra, 16( sp) sw s3,12( sp) sw s2, 8( sp) sw s1, 4( sp) sw s0, 0( sp) exit1: lw s0, 0( sp) lw s1, 4( sp) lw s2, 8( sp) lw s3,12( sp) lw ra,16( sp) addi sp, sp, 20 jr ra # # # # # # # make room on stack for 5 registers save ra on stack save s3 on stack save s2 on stack save s1 on stack save s0 on stack procedure body # # # # # # # restore s0 from stack restore s1 from stack restore s2 from stack restore s3 from stack restore ra from stack restore stack pointer return to calling routine Chapter 2 — Instructions: Language of the Computer — 71 Effect of Compiler Optimization Compiled with gcc for Pentium 4 under Linux Relative Performance 3 140000 Instruction count 120000 2.5 100000 2 80000 1.5 60000 1 40000 0.5 20000 0 0 none O1 O2 Clock Cycles 180000 160000 140000 120000 100000 80000 60000 40000 20000 0 none O3 O1 O2 O3 O2 O3 CPI 2 1.5 1 0.5 0 none O1 O2 O3 none O1 Chapter 2 — Instructions: Language of the Computer — 72
Effect of Language and Algorithm Bubblesort Relative Performance 3 2.5 2 15 1.5 1 0.5 0 C/none C/O1 C/O2 C/O3 Java/int Java/JIT Quicksort Relative Performance 2.5 2 1.5 1 0.5 0 C/none C/O1 C/O2 C/O3 Java/int Java/JIT Quicksort vs. Bubblesort Speedup 3000 2500 2000 1500 1000 500 0 C/none C/O1 C/O2 C/O3 Java/int Java/JIT Chapter 2 — Instructions: Language of the Computer — 73 Lessons Learnt Instruction count and CPI are not good performance indicators in isolation Compiler optimizations are sensitive to the algorithm Java/JIT compiled code is significantly f t than faster th JVM interpreted i t t d Comparable to optimized C in some cases Nothing can fix a dumb algorithm! Chapter 2 — Instructions: Language of the Computer — 74
Array indexing involves Multiplying index by element size Adding to array base address Pointers P i t correspond d directly di tl tto memory addresses §2.14 Arrrays versu us Pointers s Arrays vs. Pointers Can avoid indexing complexity Chapter 2 — Instructions: Language of the Computer — 75 Example: Clearing and Array clear1(int array[], int size) { int i; for (i 0; i size; i 1) array[i] 0; } clear2(int *array, int size) { int *p; for (p &array[0]; p &array[size]; p p 1) *p 0; } move t0, zero loop1: sll t1, t0,2 add t2, a0, t1 move t0, a0 # p & array[0] sll t1, a1,2 # t1 size * 4 add t2, a0, t1 # t2 y[ ] # &array[size] loop2: sw zero,0( t0) # Memory[p] 0 addi t0, t0,4 # p p 4 slt t3, t0, t2 # t3 #(p &array[size]) bne t3, zero,loop2 # if ( ) # goto loop2 # i 0 # t1 i * 4 # t2 y[ ] # &array[i] sw zero, 0( t2) # array[i] 0 addi t0, t0,1 # i i 1 slt t3, t0, a1 # t3 # (i size) bne t3, zero,loop1 # if ( ) # goto loop1 Chapter 2 — Instructions: Language of the Computer — 76
Comparison of Array vs. Ptr Multiply “strength reduced” to shift Array version requires shift to be inside loop Partt off index P i d calculation l l ti ffor iincremented t di c.f. incrementing pointer Compiler can achieve same effect as manual use of pointers Induction variable elimination Better to make program clearer and safer Chapter 2 — Instructions: Language of the Computer — 77 ARM: the most popular embedded core Similar basic set of instructions to MIPS ARM MIPS 1985 1985 Instruction size 32 bits 32 bits Address space 32-bit flat 32-bit flat Data alignment Aligned Aligned 9 3 15 32-bit 31 32-bit Memory mapped Memory mapped Date announced Data addressing modes Registers Input/output §2.16 Re eal Stuff: ARM Instru uctions ARM & MIPS Similarities Chapter 2 — Instructions: Language of the Computer — 78
Compare and Branch in ARM Uses condition codes for result of an arithmetic/logical instruction Negative, zero, carry, overflow Compare instructions to set condition codes without keeping the result Each instruction can be conditional Top 4 bits of instruction word: condition value C avoid Can id b branches h over single i l iinstructions t ti Chapter 2 —
of the Computer Instruction Set §2.1 Intr o The repertoire of instructions of a computer duction co pute Different computers have different instruction sets But with many aspects in common Early computers had very simpleEarly computers had very simple instruction sets Simppplified implementation Many modern computers also have simple .
Part One: Heir of Ash Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26 Chapter 27 Chapter 28 Chapter 29 Chapter 30 .
TO KILL A MOCKINGBIRD. Contents Dedication Epigraph Part One Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Part Two Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18. Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 Chapter 24 Chapter 25 Chapter 26
DEDICATION PART ONE Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 PART TWO Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Chapter 22 Chapter 23 .
About the husband’s secret. Dedication Epigraph Pandora Monday Chapter One Chapter Two Chapter Three Chapter Four Chapter Five Tuesday Chapter Six Chapter Seven. Chapter Eight Chapter Nine Chapter Ten Chapter Eleven Chapter Twelve Chapter Thirteen Chapter Fourteen Chapter Fifteen Chapter Sixteen Chapter Seventeen Chapter Eighteen
18.4 35 18.5 35 I Solutions to Applying the Concepts Questions II Answers to End-of-chapter Conceptual Questions Chapter 1 37 Chapter 2 38 Chapter 3 39 Chapter 4 40 Chapter 5 43 Chapter 6 45 Chapter 7 46 Chapter 8 47 Chapter 9 50 Chapter 10 52 Chapter 11 55 Chapter 12 56 Chapter 13 57 Chapter 14 61 Chapter 15 62 Chapter 16 63 Chapter 17 65 .
HUNTER. Special thanks to Kate Cary. Contents Cover Title Page Prologue Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter
Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 . Within was a room as familiar to her as her home back in Oparium. A large desk was situated i
The Hunger Games Book 2 Suzanne Collins Table of Contents PART 1 – THE SPARK Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Chapter 6 Chapter 7 Chapter 8. Chapter 9 PART 2 – THE QUELL Chapter 10 Chapter 11 Chapter 12 Chapter 13 Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapt
