Hardware Control Language and Y86-64 Instruction Set Details

CS:APP Chapter 4 Computer Architecture Sequential Implementation Randal E. Bryant Carnegie Mellon University http://csapp.cs.cmu.edu CS:APP3e

Y86-64 Instruction Set #1 Byte 0 1 6 7 8 9 2 3 4 5 halt 0 0 nop 1 0 cmovXX rA, rB fn rA rB 2 irmovq V, rB rB V 3 0 F rmmovq rA, D(rB) rA rB D 4 0 mrmovq D(rB), rA rA rB D 5 0 OPq rA, rB fn rA rB 6 jXX Dest Dest fn 7 call Dest Dest 8 0 ret 9 0 pushq rA rA A 0 F popq rA rA B 0 F CS:APP3e 2

Y86-64 Instruction Set #2 Byte rrmovq 7 0 6 7 8 9 0 1 2 3 4 5 cmovle 7 1 halt 0 0 cmovl 7 2 nop 1 0 cmove 7 3 cmovXX rA, rB fn rA rB 2 cmovne 7 4 irmovq V, rB rB V 3 0 F cmovge 7 5 rmmovq rA, D(rB) rA rB D 4 0 cmovg 7 6 mrmovq D(rB), rA rA rB D 5 0 OPq rA, rB fn rA rB 6 jXX Dest Dest fn 7 call Dest Dest 8 0 ret 9 0 pushq rA rA A 0 F popq rA rA B 0 F CS:APP3e 3

Y86-64 Instruction Set #3 Byte 0 1 6 7 8 9 2 3 4 5 halt 0 0 nop 1 0 cmovXX rA, rB fn rA rB 2 irmovq V, rB rB V 3 0 F rmmovq rA, D(rB) rA rB D 4 0 addq 6 0 mrmovq D(rB), rA rA rB D 5 0 subq 6 1 OPq rA, rB fn rA rB 6 andq 6 2 jXX Dest Dest fn 7 xorq 6 3 call Dest Dest 8 0 ret 9 0 pushq rA rA A 0 F popq rA rA B 0 F CS:APP3e 4

Y86-64 Instruction Set #4 Byte 0 1 6 7 8 jmp 9 7 0 2 3 4 5 halt 0 0 jle 7 1 nop 1 0 jl 7 2 cmovXX rA, rB fn rA rB 2 je 7 3 irmovq V, rB rB V 3 0 F jne 7 4 rmmovq rA, D(rB) rA rB D 4 0 jge 7 5 mrmovq D(rB), rA rA rB D 5 0 jg 7 6 OPq rA, rB fn rA rB 6 jXX Dest Dest fn 7 call Dest Dest 8 0 ret 9 0 pushq rA rA A 0 F popq rA rA B 0 F CS:APP3e 5

Building Blocks fun Combinational Logic Compute Boolean functions of inputs Continuously respond to input changes Operate on data and implement control A = A L U B 0 MUX 1 Storage Elements Store bits Addressable memories Non-addressable registers Loaded only as clock rises valA A srcA valW Register file W dstW valB B Clock srcB Clock CS:APP3e 6

Hardware Control Language Very simple hardware description language Can only express limited aspects of hardware operation Parts we want to explore and modify Data Types bool: Boolean a, b, c, int: words A, B, C, Does not specify word size---bytes, 32-bit words, Statements bool a = bool-expr ; int A = int-expr ; CS:APP3e 7

HCL Operations Classify by type of value returned Boolean Expressions Logic Operations a && b, a || b, !a Word Comparisons A == B, A != B, A < B, A <= B, A >= B, A > B Set Membership A in { B, C, D } Same as A == B || A == C || A == D Word Expressions Case expressions [ a : A; b : B; c : C ] Evaluate test expressions a, b, c, in sequence Return word expression A, B, C, for first successful test CS:APP3e 8

SEQ Hardware Structure State Program counter register (PC) Condition code register (CC) Register File Memories Access same memory space Data: for reading/writing program data Instruction: for reading instructions newPC PC valE, valM Write back valM Data Data memory memory Memory Addr, Data valE CC CC ALU ALU Execute Cnd aluA, aluB valA, valB srcA, srcB dstA, dstB Decode A A B B Instruction Flow Read instruction at address specified by PC Process through stages Update program counter M M Register Register Register Register file file file file E E icode, ifun rA , rB valP valC Instruction PC PC Instruction memory memory increment increment Fetch PC CS:APP3e 9

newPC PC SEQ Stages valE, valM Write back valM Fetch Data Data memory memory Memory Read instruction from instruction memory Addr, Data Decode valE Read program registers CC CC ALU ALU Execute Cnd Execute aluA, aluB Compute value or address valA, valB Memory Read or write data srcA, srcB dstA, dstB Decode A A B B M M Register Register Register Register file file file file Write Back Write program registers E E icode, ifun rA , rB valP valC Instruction PC PC Instruction memory memory PC increment increment Fetch Update program counter PC CS:APP3e 10

Instruction Decoding Optional Optional rA rB D 5 0 icode ifun rA rB valC Instruction Format Instruction byte Optional register byte Optional constant word valC icode:ifun rA:rB CS:APP3e 11

Executing Arith./Logical Operation OPq rA, rB fn rA rB 6 Fetch Memory Read 2 bytes Do nothing Decode Write back Update register Read operand registers Execute PC Update Increment PC by 2 Perform operation Set condition codes CS:APP3e 12

Stage Computation: Arith/Log. Ops OPq rA, rB icode:ifun rA:rB M1[PC+1] M1[PC] Read instruction byte Read register byte Fetch valP valA valB valE Set CC PC+2 R[rA] R[rB] valB OP valA Compute next PC Read operand A Read operand B Perform ALU operation Set condition code register Decode Execute Memory Write R[rB] valE Write back result back PC update PC valP Update PC Formulate instruction execution as sequence of simple steps Use same general form for all instructions CS:APP3e 13

Executing rmmovq D rmmovq rA, D(rB) 4 0 rA rB Fetch Memory Read 10 bytes Write to memory Decode Write back Do nothing Read operand registers Execute PC Update Increment PC by 10 Compute effective address CS:APP3e 14

Stage Computation: rmmovq rmmovq rA, D(rB) icode:ifun rA:rB M1[PC+1] valC M8[PC+2] valP PC+10 valA R[rA] valB R[rB] valE valB + valC M1[PC] Read instruction byte Read register byte Read displacement D Compute next PC Read operand A Read operand B Compute effective address Fetch Decode Execute M8[valE] valA Memory Write Write value to memory back PC update PC valP Update PC Use ALU for address computation CS:APP3e 15

Executing popq popq rA 0 rA 8 b Fetch Memory Read 2 bytes Read from old stack pointer Decode Write back Update stack pointer Write result to register Read stack pointer Execute PC Update Increment PC by 2 Increment stack pointer by 8 CS:APP3e 16

Stage Computation: popq popq rA icode:ifun rA:rB M1[PC+1] M1[PC] Read instruction byte Read register byte Fetch valP valA valB valE PC+2 R[%rsp] R[%rsp] valB + 8 Compute next PC Read stack pointer Read stack pointer Increment stack pointer Decode Execute valM R[%rsp] R[rA] PC valP M8[valA] valE valM Memory Write Read from stack Update stack pointer Write back result Update PC back PC update Use ALU to increment stack pointer Must update two registers Popped value New stack pointer CS:APP3e 17

Executing Conditional Moves cmovXX rA, rB fn rA rB 2 Fetch Memory Read 2 bytes Do nothing Decode Write back Update register (or not) Read operand registers Execute PC Update Increment PC by 2 If !cnd, then set destination register to 0xF CS:APP3e 18

Stage Computation: Cond. Move cmovXX rA, rB icode:ifun rA:rB M1[PC+1] M1[PC] Read instruction byte Read register byte Fetch valP valA valB valE If ! Cond(CC,ifun) rB PC+2 R[rA] 0 valB + valA Compute next PC Read operand A Decode Pass valA through ALU (Disable register update) Execute 0xF Memory Write R[rB] valE Write back result back PC update PC valP Update PC Read register rA and pass through ALU Cancel move by setting destination register to 0xF If condition codes & move condition indicate no move CS:APP3e 19

Executing Jumps jXX Dest 7 fn Dest Not taken fall thru: XX XX Taken target: XX XX Fetch Memory Read 9 bytes Increment PC by 9 Do nothing Write back Do nothing Decode Do nothing PC Update Set PC to Dest if branch taken or to incremented PC if not branch Execute Determine whether to take branch based on jump condition and condition codes CS:APP3e 20

Stage Computation: Jumps jXX Dest icode:ifun M1[PC] Read instruction byte Fetch valC valP M8[PC+1] PC+9 Read destination address Fall through address Decode Execute Cnd Cond(CC,ifun) Take branch? Memory Write back PC update PC Cnd ? valC : valP Update PC Compute both addresses Choose based on setting of condition codes and branch condition CS:APP3e 21

Executing call call Dest 8 0 Dest return: XX XX target: XX XX Fetch Memory Read 9 bytes Increment PC by 9 Write incremented PC to new value of stack pointer Write back Update stack pointer Decode Read stack pointer PC Update Set PC to Dest Execute Decrement stack pointer by 8 CS:APP3e 22

Stage Computation: call call Dest icode:ifun M1[PC] Read instruction byte Fetch valC valP M8[PC+1] PC+9 Read destination address Compute return point Decode valB valE R[%rsp] valB + 8 Read stack pointer Decrement stack pointer Execute M8[valE] R[%rsp] valP valE Memory Write Write return value on stack Update stack pointer back PC update PC valC Set PC to destination Use ALU to decrement stack pointer Store incremented PC CS:APP3e 23

Executing ret 9 0 ret return: XX XX Fetch Memory Read 1 byte Read return address from old stack pointer Decode Write back Update stack pointer Read stack pointer Execute PC Update Set PC to return address Increment stack pointer by 8 CS:APP3e 24

Stage Computation: ret ret icode:ifun M1[PC] Read instruction byte Fetch valA valB valE R[%rsp] R[%rsp] valB + 8 Read operand stack pointer Read operand stack pointer Increment stack pointer Decode Execute valM R[%rsp] M8[valA] valE Memory Write Read return address Update stack pointer back PC update PC valM Set PC to return address Use ALU to increment stack pointer Read return address from memory CS:APP3e 25

Computation Steps OPq rA, rB icode:ifun rA:rB M1[PC+1] M1[PC] icode,ifun rA,rB valC valP valA, srcA valB, srcB valE Cond code valM dstE dstM PC Read instruction byte Read register byte [Read constant word] Compute next PC Read operand A Read operand B Perform ALU operation Set/use cond. code reg [Memory read/write] Write back ALU result [Write back memory result] Update PC Fetch valP valA valB valE Set CC PC+2 R[rA] R[rB] valB OP valA Decode Execute Memory Write R[rB] valE back PC update PC valP All instructions follow same general pattern Differ in what gets computed on each step CS:APP3e 26

Computation Steps call Dest icode:ifun M1[PC] icode,ifun rA,rB valC valP valA, srcA valB, srcB valE Cond code valM dstE dstM PC Read instruction byte [Read register byte] Read constant word Compute next PC [Read operand A] Read operand B Perform ALU operation [Set /use cond. code reg] Memory read/write Write back ALU result [Write back memory result] Update PC Fetch valC valP M8[PC+1] PC+9 Decode valB valE R[%rsp] valB + 8 Execute M8[valE] R[%rsp] valP valE Memory Write back PC update PC valC All instructions follow same general pattern Differ in what gets computed on each step CS:APP3e 27

Computed Values Fetch Execute icode ifun rA rB valC valP Instruction code Instruction function Instr. Register A Instr. Register B Instruction constant Incremented PC valE Cnd ALU result Branch/move flag Memory valM Value from memory Decode srcA srcB dstE dstM valA valB Register ID A Register ID B Destination Register E Destination Register M Register value A Register value B CS:APP3e 28

SEQ Hardware Key Blue boxes: predesigned hardware blocks E.g., memories, ALU Gray boxes: control logic Describe in HCL White ovals: labels for signals Thick lines: 64-bit word values Thin lines: 4-8 bit values Dotted lines: 1-bit values CS:APP3e 29

Fetch Logic icode ifun rA rB valC valP Need valC PC Instr valid increment Need regids icode ifun Split Align Byte 0 Bytes 1-9 Instruction memory imem_error Predefined Blocks PC: Register containing PC Instruction memory: Read 10 bytes (PC to PC+9) Signal invalid address PC Split: Divide instruction byte into icode and ifun Align: Get fields for rA, rB, and valC CS:APP3e 30

Fetch Logic icode ifun rA rB valC valP Need valC PC Instr valid increment Need regids icode ifun Split Align Byte 0 Bytes 1-9 Instruction memory imem_error PC Control Logic Instr. Valid: Is this instruction valid? icode, ifun: Generate no-op if invalid address Need regids: Does this instruction have a register byte? Need valC: Does this instruction have a constant word? CS:APP3e 31

Fetch Control Logic in HCL icode ifun Split Byte 0 Instruction memory # Determine instruction code int icode = [ imem_error: INOP; 1: imem_icode; ]; imem_error PC # Determine instruction function int ifun = [ imem_error: FNONE; 1: imem_ifun; ]; CS:APP3e 32

Fetch Control Logic in HCL halt 0 0 nop 1 0 cmovXX rA, rB fn rA rB 2 irmovq V, rB rB V 3 0 8 rmmovq rA, D(rB) rA rB D 4 0 mrmovq D(rB), rA rA rB D 5 0 OPq rA, rB fn rA rB 6 jXX Dest fn Dest 7 call Dest Dest 8 0 ret 9 0 popq rA rA A 0 F popq rA rA B 0 F bool need_regids = icode in { IRRMOVQ, IOPQ, IPUSHQ, IPOPQ, IIRMOVQ, IRMMOVQ, IMRMOVQ }; bool instr_valid = icode in { INOP, IHALT, IRRMOVQ, IIRMOVQ, IRMMOVQ, IMRMOVQ, IOPQ, IJXX, ICALL, IRET, IPUSHQ, IPOPQ }; CS:APP3e 33

Decode Logic Register File Read ports A, B Write ports E, M Addresses are register IDs or 15 (0xF) (no access) Control Logic srcA, srcB: read port addresses dstE, dstM: write port addresses Signals Cnd: Indicate whether or not to perform conditional move Computed in Execute stage Cnd valA valB valM valE A B M Register file dstM E dstE srcA srcB dstE dstM srcA srcB icode rA rB CS:APP3e 34

OPq rA, rB valA R[rA] A Source Decode Read operand A cmovXX rA, rB valA R[rA] Decode Read operand A rmmovq rA, D(rB) valA R[rA] Decode Read operand A popq rA valA R[%rsp] Decode Read stack pointer jXX Dest Decode No operand call Dest Decode No operand ret valA R[%rsp] Decode Read stack pointer int srcA = [ ]; icode in { IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : rA; icode in { IPOPQ, IRET } : RRSP; 1 : RNONE; # Don't need register CS:APP3e 35

E Desti- nation OPq rA, rB R[rB] valE Write-back Write back result cmovXX rA, rB Conditionally write back result R[rB] valE Write-back rmmovq rA, D(rB) Write-back None popq rA R[%rsp] valE Write-back Update stack pointer jXX Dest Write-back None call Dest R[%rsp] valE Write-back Update stack pointer ret R[%rsp] valE Write-back Update stack pointer int dstE = [ ]; icode in { IRRMOVQ } && Cnd : rB; icode in { IIRMOVQ, IOPQ} : rB; icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP; 1 : RNONE; # Don't write any register CS:APP3e 36

Execute Logic Units ALU Implements 4 required functions Generates condition code values Cnd valE CC cond Register with 3 condition code bits ALU fun. ALU CC cond Computes conditional jump/move flag Set CC ALU A ALU B Control Logic Set CC: Should condition code register be loaded? ALU A: Input A to ALU ALU B: Input B to ALU ALU fun: What function should ALU compute? icode ifun valC valA valB CS:APP3e 37

ALU A Input OPq rA, rB Execute valE valB OP valA Perform ALU operation cmovXX rA, rB Execute valE 0 + valA Pass valA through ALU rmmovq rA, D(rB) Execute valE valB + valC Compute effective address popq rA Execute valE valB + 8 Increment stack pointer jXX Dest Execute No operation call Dest Execute valE valB + 8 Decrement stack pointer ret valE Execute valB + 8 Increment stack pointer int aluA = [ ]; icode in { IRRMOVQ, IOPQ } : valA; icode in { IIRMOVQ, IRMMOVQ, IMRMOVQ } : valC; icode in { ICALL, IPUSHQ } : -8; icode in { IRET, IPOPQ } : 8; # Other instructions don't need ALU CS:APP3e 38

ALU Oper- ation OPl rA, rB valE valB OP valA Execute Perform ALU operation cmovXX rA, rB valE 0 + valA Execute Pass valA through ALU rmmovl rA, D(rB) valE valB + valC Execute Compute effective address popq rA valE valB + 8 Execute Increment stack pointer jXX Dest Execute No operation call Dest valE valB + 8 Execute Decrement stack pointer ret valE valB + 8 Execute Increment stack pointer int alufun = [ ]; icode == IOPQ : ifun; 1 : ALUADD; CS:APP3e 39

Memory Logic Stat Memory Reads or writes memory word valM stat dmem_error data out Mem. read read instr_valid Data memory imem_error Mem. write Control Logic stat: What is instruction status? Mem. read: should word be read? Mem. write: should word be written? Mem. addr.: Select address Mem. data.: Select data write data in Mem. addr Mem. data icode valE valA valP CS:APP3e 40

Instruction Status Stat Control Logic stat: What is instruction status? valM stat dmem_error data out Mem. read read instr_valid Data memory imem_error Mem. write write data in Mem. addr Mem. data icode valE valA valP ## Determine instruction status int Stat = [ imem_error || dmem_error : SADR; !instr_valid: SINS; icode == IHALT : SHLT; 1 : SAOK; ]; CS:APP3e 41

Memory Address OPq rA, rB Memory No operation rmmovq rA, D(rB) M8[valE] valA Memory Write value to memory popq rA valM M8[valA] Memory Read from stack jXX Dest Memory No operation call Dest M8[valE] valP Memory Write return value on stack ret valM M8[valA] Memory Read return address int mem_addr = [ icode in { IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ } : valE; icode in { IPOPQ, IRET } : valA; # Other instructions don't need address ]; CS:APP3e 42

Memory Read OPq rA, rB Memory No operation rmmovq rA, D(rB) M8[valE] valA Memory Write value to memory popq rA valM M8[valA] Memory Read from stack jXX Dest Memory No operation call Dest M8[valE] valP Memory Write return value on stack ret valM M8[valA] Memory Read return address bool mem_read = icode in { IMRMOVQ, IPOPQ, IRET }; CS:APP3e 43

PC Update Logic PC New PC New PC Select next value of PC icode Cnd valC valM valP CS:APP3e 44

PC Update OPq rA, rB PC valP PC update Update PC rmmovq rA, D(rB) PC valP PC update Update PC popq rA PC valP PC update Update PC jXX Dest PC Cnd ? valC : valP PC update Update PC call Dest PC valC PC update Set PC to destination ret PC valM PC update Set PC to return address int new_pc = [ ]; icode == ICALL : valC; icode == IJXX && Cnd : valC; icode == IRET : valM; 1 : valP; CS:APP3e 45

SEQ Operation State PC register Cond. Code register Data memory Register file All updated as clock rises Read Write Combinational logic Data memory CC 100 Read ports Write ports Combinational Logic ALU Control logic Memory reads Instruction memory Register file Data memory Register file %rbx = 0x100 PC 0x014 CS:APP3e 46

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock SEQ Operation #2 Cycle 1: 0x000: irmovq $0x100,%rbx # %rbx <-- 0x100 Cycle 2: 0x00a: irmovq $0x200,%rdx # %rdx <-- 0x200 Cycle 3: 0x014: addq %rdx,%rbx # %rbx <-- 0x300 CC <-- 000 Cycle 4: 0x016: je dest # Not taken Cycle 5: 0x01f: rmmovq %rbx,0(%rdx) # M[0x200] <-- 0x300 Read Write Combinational logic state set according to second irmovq instruction combinational logic starting to react to state changes Data memory CC 100 Read ports Write ports Register file %rbx = 0x100 PC 0x014 CS:APP3e 47

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock SEQ Operation #3 Cycle 1: 0x000: irmovq $0x100,%rbx # %rbx <-- 0x100 Cycle 2: 0x00a: irmovq $0x200,%rdx # %rdx <-- 0x200 Cycle 3: 0x014: addq %rdx,%rbx # %rbx <-- 0x300 CC <-- 000 Cycle 4: 0x016: je dest # Not taken Cycle 5: 0x01f: rmmovq %rbx,0(%rdx) # M[0x200] <-- 0x300 Read Write Combinational logic state set according to second irmovq instruction combinational logic generates results for addq instruction Data memory CC 100 Read ports Write ports 000 Register file %rbx = 0x100 %rbx <-- 0x300 0x016 PC 0x014 CS:APP3e 48

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock SEQ Operation #4 Cycle 1: 0x000: irmovq $0x100,%rbx # %rbx <-- 0x100 Cycle 2: 0x00a: irmovq $0x200,%rdx # %rdx <-- 0x200 Cycle 3: 0x014: addq %rdx,%rbx # %rbx <-- 0x300 CC <-- 000 Cycle 4: 0x016: je dest # Not taken Cycle 5: 0x01f: rmmovq %rbx,0(%rdx) # M[0x200] <-- 0x300 Read Write Combinational logic state set according to addq instruction combinational logic starting to react to state changes Data memory CC 000 Read ports Write ports Register file %rbx = 0x300 PC 0x016 CS:APP3e 49

Cycle 1 Cycle 2 Cycle 3 Cycle 4 Clock SEQ Operation #5 Cycle 1: 0x000: irmovq $0x100,%rbx # %rbx <-- 0x100 Cycle 2: 0x00a: irmovq $0x200,%rdx # %rdx <-- 0x200 Cycle 3: 0x014: addq %rdx,%rbx # %rbx <-- 0x300 CC <-- 000 Cycle 4: 0x016: je dest # Not taken Cycle 5: 0x01f: rmmovq %rbx,0(%rdx) # M[0x200] <-- 0x300 Read Write Combinational logic state set according to addq instruction combinational logic generates results for je instruction Data memory CC 000 Read ports Write ports Register file %rbx = 0x300 0x01f PC 0x016 CS:APP3e 50