Y86-64学习2-Y86-64 SEQ Stages

Made by Mike_Zhang

Computer System 相关文章:
有符号二进制数表示方法 Signed binary number representation
浮点数二进制数表示方法 Floating point numbers representation
UltraFish Plus - 有符号二进制数转换器 Signed binary number convertor
UltraFish Plus - 浮点数表示方法转换器 Floating Point Numbers Representation Convertor
UltraFish Plus - 多进制整数转换器 Multiple Bases Unsigned Integer Convertor
Y86-64学习1-State & Instruction & Basic Encoding
Y86-64学习2-Y86-64 SEQ Stages
x86-64学习1-Introduction & Data Formats & Information Accessing & Arithmetic Logical Operation
x86-64学习2-Control

The last article describes the components of each Y86-64 instruction. It is important to learn the SEQ (sequential processor) before reach the final goal - pipeline processor. The SEQ is slow because it requires a whole cycle to perform all steps in a instruction. Each instruction has a very different actions. However, the SEQ makes all different instructions follow a uniform sequence, which makes the best use of the hardware, even though it requires a long cycle time.

1 Stages Description

6 stages: Fetch, Decode, Execute, Memory, Write Back, and PC Update.

1.1 Fetch

  • According to the PC as the RAM address, read instruction byte from memory;
  • Read first two 4-bit(1 Byte) instruction specifier byte, including the icode and ifun;
  • Read the register specifier byte - rA and rB;
  • Read 8-byte constant word - valC;
  • Compute the next instruction address following the current one, valP = PC + len(fetched instruction)

1.2 Decode

Read register value from Register File.

  • Read from rA, rB;
  • Assign value to valA and valB;
  • OR read from stack pointer %rsp(e.g., pushq, popq, call, ret).

1.3 Execute

  • The ALU(Arithmetic/Logic Unit):
    • Do the operation based on the ifun, or
    • Compute the effective memory address(e.g., base address ADD displacement), or
    • Increase or decrease the stack pointer.
  • Assign the result value to valE;
  • Set the CC (Condition Code);

For cmovXX(conditional move) and jXX(jump) instruction:
This stage will evaluate the CC with ifun(move condition OR jump condition);
if condition holds, do the move or jump.

1.4 Memory

  • 8-byte;
  • Write data into memory, usually write into $M_8[valE]$;
  • Read data from memory, store in valM.

1.5 Write Back

  • Write the data back to register from the Decode Stage (e.g., rA, rB, %rsp)

1.6 PC Update

  • Set PC (Program Counter) to the address of next instruction;
  • In Fetch Stage, valP = PC + len(fetched instruction) does not update the value of PC, but in this Stage, assign valP to PC to truly update PC, PC = valP;
  • Based on execute result, set PC to valC or valP(e.g., in jXX or cmovXX).

2 Stages Implementation

2.1 OPq rrmovq irmovq Implementation

  • Compute a value and store the result in a register.

Computations in sequential implementation of Y86-64 instructions(OPq, rrmovq, irmovq)(CS: APP)

$M_x[PC]$ refers to accessing x bytes at location of PC in memory.

Common:

  • Fetch:
    • icode, ifun: $M_1[PC]$;
    • rA, rB: $M_1[PC+1]$;
  • Memory: No operation on memory;
  • Write Back: Write valE into rB register;
  • PC Update: Update PC to valP.

Diff:

  • OPq rA, rB
    • 2-byte
    • 6(PC) | fn | rA(PC+1) | rB
    • Decode:
      • Read both rA and rB;
    • Execute:
      • valB(rB) OP valA(rA) (OP based on ifun)
      • Set CC
  • rrmovq rA, rB
    • 2-byte
    • 2(PC) | 0 | rA(PC+1) | rB
    • Decode:
      • Read rA only;
    • Execute:
      • valE = 0 + valA $\to$ valE = valA ;
      • No set to CC;
  • irmovq V,rB
    • 10-byte
    • 3(PC) | 0 | F(PC+1)| rB | V(PC+2)
    • Fetch:
      • valC = $M_8[PC+2]$ to get the constant words;
    • Decode:
      • No read from register;
    • Execute:
      • valE = 0 + valC $\to$ valE = valC ;
      • No set to CC;

Example Sample:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1  0x000: 30f20900000000000000  |       irmovq $9, %rdx
2  0x00a: 30f31500000000000000  |       irmovq $21, %rbx
3  0x014: 6123                  |       subq %rdx, %rbx           # subtract [Example 1]
4  0x016: 30f48000000000000000  |       irmovq $128,%rsp          # [Example 2]
5  0x020: 40436400000000000000  |       rmmovq %rsp, 100(%rbx)    # store [Example 3]
6  0x02a: a02f                  |       pushq %rdx                # push [Example 4]
7  0x02c: b00f                  |       popq %rax                 # [Example 5]
8  0x02e: 734000000000000000    |       je done                   # Not taken [Example 6]
9  0x037: 804100000000000000    |       call proc                 # [Example 7]
10 0x040:                       | done:
11 0x040: 00                    |       halt
12 0x041:                       | proc:
13 0x041: 90                    |       ret                       # Return [Example 8]
14                              |

Sample Y86-64 instruction sequence(CS: APP)

Example 1:


Example 1 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

Example 2:


Example 2 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

2.2 rmmovq mrmovq Implementation

  • Read or write memory

Computations in sequential implementation of Y86-64 instructions(rmmovq, mrmovq)(CS: APP)

Common:

  • Same Fetch Stage
  • Execute:
    • valB: the value of register rB, as the base address;
    • valC: the value of the constant word, as the displacement;
    • valE: the effective address = valB ADD valC;
    • PC Update: Update PC to valP.

Diff:

  • rmmovq
    • 10-byte
    • 4(PC) | 0 | rA(PC+1) | rB | D(PC+2)
    • rA $\to$ rB, register $\to$ memory
    • Decode:
      • valA: R[rA], as the value to write into memory;
      • valB: R[rB], as the base address;
    • Memory:
      • write valA into memory at effective address valE from register;
    • Write Back: NO write back to register;
  • mrmovq:
    • 10-byte
    • 5(PC) | 0 | rA(PC+1) | rB | D(PC+2)
    • rB $\to$ rA, memory $\to$ register
    • Decode:
      • valB: R[rB], as the base address;
      • the value to write into register is read from memory
    • Memory:
      • read value from memory at effective address valE, as valM;
    • Write Back: write valE back to rA.

Example 3:


Example 3 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

2.3 pushq popq Implementation

  • Push or pop the stack

Computations in sequential implementation of Y86-64 instructions(pushq, popq)(CS: APP)
  • pushq rA
    • 2-byte
    • A(PC) | 0 | rA(PC+1) | F
    • Decode:
      • valA: read from rA, as the value push into memory;
      • valB: read from %rsp, as the top pointer of stack;
    • Execute:
      • valE = valB - 8, push the top pointer of stack forward, valE as the new peak;
    • Memory:
      • write the value valA into the stack at the new top address valE in the memory;
    • Write Back:
      • R[%rsp] = valE, truly update the stack pointer %rsp.
  • popq rA
    • 2-byte
    • B(PC) | 0 | rA(PC+1) | F
    • Decode:
      • valA: read from %rsp, unincremented value, as the peak of stack in the memory;
      • valB: read from %rsp, incremented value, as the top pointer of stack, will be incremented;
    • Execute:
      • valE = valB + 8, push the top pointer of stack backward, valE as the new peak;
    • Memory:
      • read the value at address valA from the stack at the original top address valA in the memory, as valM;
    • Write Back:
      • R[%rsp] = valE, truly update the stack pointer %rsp.
      • R[A] = valM, write the popped value from memory valM into register rA.

Example 4:


Example 4 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

Example 5:


Example 5 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

2.4 jXX call ret cmovXX Implementation

  • Control transfer

Computations in sequential implementation of Y86-64 instructions(jXX, call, ret)(CS: APP)

Computations in sequential implementation of Y86-64 instructions(cmovXX)(CS: APP)
  • jXX Dest
    • 9-byte
    • 7(PC) | fn | Dest(PC+1)
    • Fetch:
      • valC: as the destination address for jump;
      • valP: the address of next instruction for non-jump;
    • NO decode stage;
    • Execute:
      • Evaluate the CC with ifun(move condition OR jump condition);
      • Cnd = flag: 1 or 0
        • 1: hold condition, PC = valC, jump;
        • 0 : escape condition, PC = valP, next;
    • NO memory and register read or write;
    • PC Update:
      • PC $\leftarrow$ Cnd?valC:valP:
        • if (Cnd == 1): PC = valC;
        • if (Cnd == 0): PC = valP;

  • cmovXX rA, rB

    • 2-byte
    • 2(PC) | fn | rA(PC+1) | rB
    • Combination of rrmovq and conditional instruction;

  • call Dest

    • 9-byte
    • 7(PC) | fn | Dest(PC+1)
    • Based on pushq;
    • Write the next address valP into the memory, for return;
  • ret
    • 1-byte
    • 9(PC) | 0
    • Based on popq;
    • Read the next address valM from the memory, for jump;
    • Set PC to valM, return to the next instruction of call instruction;

Example 6:


Example 6 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

Example 7:


Example 7 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

Example 8:


Example 8 of Computations in sequential implementation of Y86-64 instructions(CS: APP)

参考

B. Randal, D. R. O’Hallaron, Computer systems : a programmer’s perspective, Third edition. Boston: Pearson, 2016.

写在最后

Y86-64相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Computer System > Y86-64
#学习 #Y86-64 #Computer System
Y86-64学习2-Y86-64 SEQ Stages
https://ultrafish.io/post/Y86-64-learning-2/
Author
Mike_Zhang
Posted on
January 8, 2022
Licensed under