int *p; /* Pointer to integer array */ int i,j; /* integer variables */ ... j = p[i]; /* access ith element of array */The pointer variable p contains the address of a dynamically allocated array of integers. The value of p[i] is stored at the address Mem[p]+4*Mem[i] where p and i are locations containing the values of the corresponding C variables. On a conventional Beta this code fragment is translated to the following instruction sequence:
LD(...,R1) /* R1 contains p, the array base address */ LD(...,R2) /* R2 contains I, the array index */ ... SHLC(R2,2,R0) /* compute byte-addressed offset = 4*i */ ADD(R1,R0,R0) /* address of indexed element */ LD(R0,0,R3) /* fetch p[i] into R3 */Notta proposes the addition of an LDX instruction that shortens the last three instructions to
SHLC(R2,2,R0) /* compute byte-addressed offset = 4*i */ LDX(R0,R1,R3) /* fetch p[i] into R3 */Give a register-transfer language description for the LDX instruction. Examples of register-transfer language descriptions can be for other Beta instructions in the Beta Documentation handed out in lecture.
LDX( Ra, Rb, Rc ) EA <- Reg[Ra] + Reg[Rb] Reg[Rc] <- Mem[EA] PC <- PC + 4
LDX ALUFN "+" WERF 1 BSEL 0 WDSEL 2 WR 0 RA2SEL 0 PCSEL 0 ASEL 0 WASEL 0
SHLC(R2,2,R0) /* compute byte-addressed offset = 4*i */ STX(R3,R0,R1) /* R3 contains j, R1 contains p */Briefly describe what modifications to the Beta datapath would be necessary to be able to execute STX in a single cycle.
STX(Rc, Rb, Ra) EA <- Reg[Ra] + Reg[Rb] Mem[EA] <- Reg[Rc] PC <- PC + 4It's evident that we need to perform 3 register reads, but the Beta's register file has only 2 read ports. Thus we need to add a third read port to the register file. Incidentally, adding a third read port would eliminate the need for the RA2SEL mux because we no longer need to choose between Rb and Rc, since each register field has its own read port.
. = 0 BEQ(R0,.+4,R31) ADDC(R0,1,R0)Execute for 2 cycles. If fault A is not present, R0 contains 1 after the second cycle. If fault A is present, the second instruction is fetched from location 0 (instead of 4), so the value of R0 stays 0.
. = 0 ADDC(R1,1,R1) ST(R1,0,R0) LD(R0,0,R0)Execute for 3 cycles. If fault B is not present, the ST instruction writes the value 1 into location 0, which is then LDed into R0. If fault B is present, the ST instruction writes the contents of R0 instead (ie, the value 0), so now the LD instruction puts 0 into R0.
. = 0 BNE(R0,.+8,R31) ADDC(R0,1,R0)Execute for 2 cycles. If fault C is not present, R0 is incremented to 1 since the branch is not taken. If fault C is present, the BNE instruction always branches, skipping over the ADDC instruction and leaving the contents of R0 unchanged (ie, it's still 0).
. = 0 ADDC(R0,1,R0)Execute for 1 cycle. If fault D is not present, R0 is increment to 1. If fault D is present, the high-order 5-bits of the literal field (i.e., where Rb is encoded) is used as a register address, and the contents of that register is added to R0. Since the literal is "1", the second register is R0 (containing 0), so the value written into R0 is 0.
. = 0 ADDC(R1,1,R1) ST(R1,X,R31) LD(R31,X,R0) . = 0x100 X: LONG(0)Execute for 3 cycles. If fault E is not present, the ST instruction writes the value 1 into X, which is then LDed into R0. If fault B is present, the ST instruction has no effect, so now the LD instruction loads the original value of location X into R0.
. = 0 BEQ(R0,.+4,R1) SUBC(R1,3,R0)Execute for 2 cycles. If fault F is not present, the BEQ instruction loads 4 into R1 and the SUBC loads 1 into R0. If fault F is present, the BEQ instruction load 0 into R0 and the SUBC loads -3 into R0.
.macro LDR(label,RX) { BR(.+8,RX) | load address of following word into RX LONG(label) | address of constant to be loaded LD(RX,0,RX) | load address into register LD(RX,0,RX) | load constant into register }
PCSEL 0 RA2SEL - BSEL 1 ALUFN + Wr 0 WERF 1 WASEL 0 AdrSEL 0 WDSEL1 1 WDSEL0 -
// Swap register contents with memory location MSWP (Ra, literal, Rc) PC <- PC + 4 EA <- Reg[Ra] + SEXT(literal) tmp <- Mem[EA] Mem[EA] <- Reg[Rc] Reg[Rc] <- tmp // Move if zero MVZ (Ra, Rb, Rc) PC <- PC + 4 if Reg[Ra] = 0 then Reg[Rc] <- Reg[Rb] // Move constant if zero MVZC (Ra, literal, Rc) PC <- PC + 4 if Reg[Ra] = 0 then Reg[Rc] <- SEXT(literal)
MSWP MVZ MVZC ALUFN "+" "B" "B" WERF 1 Z?1:0 Z?1:0 BSEL 1 0 1 WDSEL 2 1 1 WR 1 0 0 RA2SEL 1 0 - PCSEL 0 0 0 ASEL 0 - - WASEL 0 0 0
// Push Rc onto stack pointed to by Ra PUSH(Rc, 4, Ra) PC <- PC + 4 Mem[Reg[Ra]] <- Reg[Rc] Reg[Ra] <- Reg[Ra] + 4 // Store indexed (base + index register) STX(Ra, Rb, Rc) PC <- PC + 4 Mem[Reg[Ra] + Reg[Rb]] <- Reg[Rc]