Instruction Set Comparisons CS 740 Procedure Examples Procedure linkage Passing of control and data stack management Sept 20 2002 Control Register tests Condition codes loop counters Topics Code Examples Procedure Linkage Sparse Matrix Code Instruction Sets Alpha PowerPC VAX x86 2 Page 1 Code Example int rfact int n if n 1 return 1 return n rfact n 1 CS 740 F 02 Alpha rfact Registers 16 Argument n 9 Saved n Callee save 0 Return Value Stack Frame 16 bytes 9 26 return PC sp 8 sp 0 save 9 save 26 3 VAX Pinnacle of CISC rfact ldgp 29 0 27 rfact ng lda 30 16 30 frame 30 16 26 0 stq 26 0 30 stq 9 8 30 mask 0x4000200 16 prologue 1 bis 16 16 9 cmple 9 1 1 bne 1 80 subq 9 1 16 bsr 26 rfact ng mulq 9 0 0 br 31 81 align 4 80 bis 31 1 0 81 ldq 26 0 30 ldq 9 8 30 addq 30 16 30 ret 31 26 1 setup gp Maximize instruction density Provide instructions closely matched to typical program operations sp 16 save return addr save 9 Instruction format OP arg1 arg2 Each argument has arbitrary specifier Accessing operands may have side effects 9 n if n 1 then branch to 80 16 n 1 recursive call 0 n rfact n 1 branch to epilogue Condition Codes Set by arithmetic and comparison instructions Basis for successive branches return val 1 Procedure Linkage restore retrn addr restore 9 sp 16 Direct implementation of stack discipline CS 740 F 02 4 Page 2 CS 740 F 02 VAX Registers VAX Operand Specifiers Forms R0 R11 General purpose Varies with push pop R2 R7 Callee save in example code Use pair to hold double SP Temp R12 AP Argument pointer Space Stack region holding procedure arguments R13 FP Frame pointer Local Current Vars Base of current stack frame Frame FP R14 SP Stack pointer Saved Caller Top of stack State R15 PC Program counter Arg Count AP Used to access data in code Previous N C V Z Condition codes Frame Args Information about last operation result Address Negative Carry 2 s OVF Zero 5 Notation Value Side Eff Use Ri ri General purpose register v v Immediate data Ri M ri Memory reference v Ri M ri v Mem ref with displacement A Ri M a ri d Array indexing A is specifier denoting address a d is size of datum Ri M ri Ri d Stepping pointer forward Ri M ri d Ri d Stepping pointer back Examples Push src Pop dest CS 740 F 02 6 Page 3 move src SP move SP dest CS 740 F 02 VAX Procedure Linkage VAX rfact Caller Registers SP Argn Push Arguments Relative to SP Execute CALLS narg proc Arg1 narg denotes number of argument words proc starts with mask denoting registers to be saved on stack CALLS Instruction Creates stack frame Saved registers PC FP AP mask PSW Sets AP FP SP Callee SP FP AP proc mask 1st instr 7 word 0x40 movl 4 ap r6 cmpl r6 1 jgtr L1 movl 1 r0 ret Stack Frame save r6 CALLS narg Save register r6 r6 n if n 1 then goto L1 r0 1 return L1 Note pushab 1 r6 push n 1 calls 1 rfact call recursively mull2 r6 r0 return result n ret Destination argument last SP Saved State FP narg Temp Space r6 Saved Caller State Argn Compute return value in R0 Execute ret Undoes effect of CALLS rfact r6 saved n r0 return value AP 1 n Arg1 CS 740 F 02 8 Page 4 Current Frame Previous Frame CS 740 F 02 x86 Pre history 8080 80486 8086 8088 P III 8 bit microprocessor Accumulator machine 16 bit machine Added registers but many implicit Extended Accumulator Machine Chosen by IBM 16 bit address space 8087 x86 Memory Architecture Segmented architecture MMX CS DS ES SS Addressing Modes Added SSE Absolute P4 0x45612789 Register indirect r Base displacement r 0x01234567 Indexed r s Indexed displacement r s 0x01234567 Base scaled index r s scale Base disp scaled index r 0x01234567 s scale Added SSE2 Now floating point looks like a general register machine too Floating point processor Extended stack machine 80286 24 bit address space 80386 32 bit machine Almost a general purpose register machine Still have 8086 compatibility mode 9 CS 740 F 02 10 Page 5 CS 740 F 02 X86 Registers X86 Instructions Very few registers Lots of meaning attached to each Accumulator AX AH AL EAX Count loop CX Data Mult Div DX Base BX Stack pointer SP Base pointer BP fp Source Dest index regs SI DI 8 Floating point Condition codes PC 11 Standard ones you would expect and Call Callf Ret retf Loop if CX goto PC 0x Push Pop MOVS Prefixes repeat lock Postfixes address specifiers Can vary in length from 1 byte to 17 CS 740 F 02 12 Page 6 CS 740 F 02 X86 rfact rfact pushl movl subl pushl movl cmpl jle leal addl pushl call imull movl jmp align 4 L3 movl L5 movl movl popl ret ebp esp ebp 20 esp ebx 8 ebp ebx 1 ebx L3 1 ebx eax 12 esp eax rfact eax ebx ebx eax L5 Sparse Matrix Code Task save old stack base point BP to args get some more stack space save reg Get argument Multiply sparse matrix times dense vector Matrix has many zero entries Save space and time by keeping only nonzero entries Common application TRICKY allocate space for args save arg make call multiply result put back in accumulator Compressed Sparse Row Representation 13 2 2 4 1 1 9 4 6 1 eax 24 ebp ebx ebp esp ebp 3 5 0 9 0 7 2 7 3 0 2 9 restore reg restore sp restore fp 1 2 2 8 3 4 CS 740 F 02 14 Page 7 0 3 5 1 0 9 3 2 2 1 4 1 3 1 9 0 4 6 2 0 7 3 2 7 5 3 0 2 2 9 2 1 2 4 2 8 5 3 4 CS 740 F 02 CSR Encoding Parameters nrow nentries Number of rows and columns Number of nonzero matrix entries Val List of nonzero values nentries CSR Example Parameters typedef struct int nrow int nentries double val int cindex int rstart csr rec csr ptr nrow 6 nentries 13 Val 3 5 0 9 2 2 4 1 1 9 4 6 0 7 2 7 3 0 2 9 1 2 2 8 3 4 Cindex Cindex List of column indices nentries 0 15 3 1 3 Rstart Rstart List of starting positions for each row 1 0 3 5 9 10 12 13 nrow 1 CS 740 F 02 16 Page 8 0 2 3 5 2 2 4 5 0 3 5 1 0 9 3 2 2 1 4 1 3 1 9 0 4 6 2 0 7 3 2 7 5 3 0 2 2 9 2 1 2 …
View Full Document
Unlocking...