Homework3: SoftCPU

Setup

Follow the instruction of Lab2: RISC-V RV32I[MACF] emulator with ELF support and srv32 - RISCV RV32IM Soft CPU to install riscv toolchain and srv32.

Run ISS and RTL Simulator

Follow the dirtectory structure of srv32/sw/hello to create another dirtectory hw3 under srv32/sw. There are two files in this directory, hw3.c and Makefile.

• hw3_isLongPressedName.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isLongPressedName(char *name, char *typed){
    int i = 0, j = 0;
    if (name[0] != typed[0]) return false;
    while (i < strlen(name))
    {
        if(name[i] == typed[j]){
            j++; i++;
        }
        else{
            if(typed[j] == name[i-1])/* long typing */
                j++;
            else
                return false;
        }
    }
    while (j < strlen(typed))
    {
        if (typed[j++] != name[strlen(name)-1])
            return false;
    }
    return true;
}

int main()
{    
    if (isLongPressedName("alex", "aalexx")) 
        printf("PASS\n");
    else
        printf("FAIL\n");
    return 0;
}

• Makefile

include ../common/Makefile.common

EXE      = .elf
SRC      = hw3_isLongPressedName.c
CFLAGS  += -L../common
LDFLAGS += -T ../common/default.ld
TARGET   = hw3_isLongPressedName
OUTPUT   = $(TARGET)$(EXE)

.PHONY: all clean

all: $(TARGET)

$(TARGET): $(SRC)
	$(CC) $(CFLAGS) -o $(OUTPUT) $(SRC) $(LDFLAGS)
	$(OBJCOPY) -j .text -O binary $(OUTPUT) imem.bin
	$(OBJCOPY) -j .data -O binary $(OUTPUT) dmem.bin
	$(OBJCOPY) -O binary $(OUTPUT) memory.bin
	$(OBJDUMP) -d $(OUTPUT) > $(TARGET).dis
	$(READELF) -a $(OUTPUT) > $(TARGET).symbol

clean:
	$(RM) *.o $(OUTPUT) $(TARGET).dis $(TARGET).symbol [id]mem.bin memory.bin

Compile

Enter following command under srv32

$ make hw3

• Result

Optimization

The original assembly code of function isLongPressedName shows below, we can find that there are lots of branch instructions and load/store instructions in it. Moreover, this function implements with string library, so it need to jump to function strlen.

• Assembly code

0000003c <isLongPressedName>:
  3c:	00054703          	lbu	a4,0(a0)
  40:	0005c783          	lbu	a5,0(a1)
  44:	0af71c63          	bne	a4,a5,fc <isLongPressedName+0xc0>
  48:	fe010113          	addi	sp,sp,-32
  4c:	00912a23          	sw	s1,20(sp)
  50:	01212823          	sw	s2,16(sp)
  54:	01312623          	sw	s3,12(sp)
  58:	00050493          	mv	s1,a0
  5c:	00058913          	mv	s2,a1
  60:	00112e23          	sw	ra,28(sp)
  64:	00812c23          	sw	s0,24(sp)
  68:	0c4000ef          	jal	ra,12c <strlen>
  6c:	00100793          	li	a5,1
  70:	00000713          	li	a4,0
  74:	00050993          	mv	s3,a0
  78:	00e486b3          	add	a3,s1,a4
  7c:	00f90633          	add	a2,s2,a5
  80:	03377463          	bgeu	a4,s3,a8 <isLongPressedName+0x6c>
  84:	fff64603          	lbu	a2,-1(a2)
  88:	0006c583          	lbu	a1,0(a3)
  8c:	06c58263          	beq	a1,a2,f0 <isLongPressedName+0xb4>
  90:	fff6c683          	lbu	a3,-1(a3)
  94:	02c69e63          	bne	a3,a2,d0 <isLongPressedName+0x94>
  98:	00178793          	addi	a5,a5,1
  9c:	00e486b3          	add	a3,s1,a4
  a0:	00f90633          	add	a2,s2,a5
  a4:	ff3760e3          	bltu	a4,s3,84 <isLongPressedName+0x48>
  a8:	00090513          	mv	a0,s2
  ac:	fff78413          	addi	s0,a5,-1
  b0:	013484b3          	add	s1,s1,s3
  b4:	078000ef          	jal	ra,12c <strlen>
  b8:	04a47663          	bgeu	s0,a0,104 <isLongPressedName+0xc8>
  bc:	00140413          	addi	s0,s0,1
  c0:	008907b3          	add	a5,s2,s0
  c4:	fff7c703          	lbu	a4,-1(a5)
  c8:	fff4c783          	lbu	a5,-1(s1)
  cc:	fef706e3          	beq	a4,a5,b8 <isLongPressedName+0x7c>
  d0:	01c12083          	lw	ra,28(sp)
  d4:	01812403          	lw	s0,24(sp)
  d8:	01412483          	lw	s1,20(sp)
  dc:	01012903          	lw	s2,16(sp)
  e0:	00c12983          	lw	s3,12(sp)
  e4:	00000513          	li	a0,0
  e8:	02010113          	addi	sp,sp,32
  ec:	00008067          	ret
  f0:	00170713          	addi	a4,a4,1
  f4:	00178793          	addi	a5,a5,1
  f8:	fa5ff06f          	j	9c <isLongPressedName+0x60>
  fc:	00000513          	li	a0,0
 100:	00008067          	ret
 104:	01c12083          	lw	ra,28(sp)
 108:	01812403          	lw	s0,24(sp)
 10c:	01412483          	lw	s1,20(sp)
 110:	01012903          	lw	s2,16(sp)
 114:	00c12983          	lw	s3,12(sp)
 118:	00100513          	li	a0,1
 11c:	02010113          	addi	sp,sp,32
 120:	00008067          	ret

Result for ISS & RTL

...
Excuting 1692 instructions, 2414 cycles, 1.426 CPI
Program terminate
- ../rtl/../testbench/testbench.v:434: Verilog $finish

Simulation statistics
=====================
Simulation time  : 0.042 s
Simulation cycles: 2425
Simulation speed : 0.0577381 MHz
...

Excuting 1692 instructions, 2414 cycles, 1.427 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.001 s
Simulation cycles: 2414
Simulation speed : 4.389 MHz

make[1]: Leaving directory '/home/qwe661234/srv32/tools'
Compare the trace between RTL and ISS simulator
=== Simulation passed ===

Tail-Call Optimization

For tail-call optimization, I put its details and some examples in this document. I rewrite isLongPressedName to meet the constraint of tail call, so compiler can use tail-call optimization to optimize this function. We can find lots of load/store instrucations have been eliminated, it is the effect of tail-call optimization. Moreover, I implement this funciton without using string library.

• C code

bool isLongPressedName(char *name, char *typed, char prev){
    if (!name[0] && !typed[0])
        return true;
    if (name[0] == typed[0]) {
        prev = name[0];
        name++;
        typed++;
    } else if (typed[0] == prev)
        typed++;
    else
        return false;
    return isLongPressedName(name, typed, prev);
}

• Assembly code

0000003c <isLongPressedName>:
  3c:	00054703          	lbu	a4,0(a0)
  40:	0005c783          	lbu	a5,0(a1)
  44:	00158593          	addi	a1,a1,1
  48:	00f766b3          	or	a3,a4,a5
  4c:	02068063          	beqz	a3,6c <isLongPressedName+0x30>
  50:	00f71863          	bne	a4,a5,60 <isLongPressedName+0x24>
  54:	00150513          	addi	a0,a0,1
  58:	00070613          	mv	a2,a4
  5c:	fe1ff06f          	j	3c <isLongPressedName>
  60:	fcc78ee3          	beq	a5,a2,3c <isLongPressedName>
  64:	00000513          	li	a0,0
  68:	00008067          	ret
  6c:	00100513          	li	a0,1
  70:	00008067          	ret

Result for ISS & RTL

...
Excuting 1672 instructions, 2402 cycles, 1.436 CPI
Program terminate
- ../rtl/../testbench/testbench.v:434: Verilog $finish

Simulation statistics
=====================
Simulation time  : 0.07 s
Simulation cycles: 2413
Simulation speed : 0.0344714 MHz

...

Excuting 1672 instructions, 2402 cycles, 1.437 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.001 s
Simulation cycles: 2402
Simulation speed : 4.163 MHz

make[1]: Leaving directory '/home/qwe661234/srv32/tools'
Compare the trace between RTL and ISS simulator
=== Simulation passed ===

Unfortunately, I just save about 12 cycles after optimizing. The reason is lots of cycle is account for printf, so the optimization of function isLongPressedName is not significant for overall program. However, we can enlarge the test case to make function isLongPressedName account lots of cycle.

new test string

name:abcdefghijklmopqrstuvwxyz
typed:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccccccccccccccddddddddddddddeffffffffffffffffffffffffgggggggggggggggghhhhhhhhhhhhhhhhiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkklllllllllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooppppppppppppppppppppppppppppppppppppppppppppppppppppppppppqrstuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

Result without Optimization

...
Excuting 94629 instructions, 156275 cycles, 1.651 CPI
Program terminate
- ../rtl/../testbench/testbench.v:434: Verilog $finish

Simulation statistics
=====================
Simulation time  : 0.709 s
Simulation cycles: 156286
Simulation speed : 0.220432 MHz

...

Excuting 94629 instructions, 156275 cycles, 1.651 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.030 s
Simulation cycles: 156275
Simulation speed : 5.265 MHz

...
=== Simulation passed ===

Result with Optimization

Compare the result between with and without optimization, we can find that tail-call optimization save more than 40000 cycles. This optimization is significant!

...

Simulation statistics
=====================
Simulation time  : 0.596 s
Simulation cycles: 110374
Simulation speed : 0.185191 MHz

...

Excuting 70419 instructions, 110363 cycles, 1.567 CPI
Program terminate

Simulation statistics
=====================
Simulation time  : 0.029 s
Simulation cycles: 110363
Simulation speed : 3.807 MHz

...
=== Simulation passed ===

Analyze waveform

Input following command under directory srv32/sim.

$ make hw3.run
$ gtkwave wave.fst

Control hazard

Branch determines flow of control, and fetching next instruction depends on branch outcome.

Solution

Result of branch is known at the EX stage.

• Stall: wait until the branch determined, then fetching next instruction.
• Branch Prediction:
  • Correct prediction: no stall required.
  • Incorrect prediction: clean incorrect instruction and wait previous instruction finish. We also call the action that CPU cleans incorrect instruction as penalty.

Branch Prediction and Penalty

The cycle in the first image below is at PC 60, the instruction is beq a5,a2,3c <isLongPressedName>. We can find that CPU flushes two cycles after this branch executing. However, The cycle in the second image below is at PC 4c, the instruction is beqz a3,6c <isLongPressedName+0x30>. We can't find CPU flushes any cycle after this branch executing. Based on this result, I speculate the two cycles is penalty for bracnch prediction. Because srv32 is a 3-stage pipeline CPU, it exist control hazard when executing branch instruction. If this CPU apply branch prediction to deal with control hazard, it would get penalty when it misses prediction.