From 37fa9ca7adccd4cc34e4916a36ed9e6d1db51c34 Mon Sep 17 00:00:00 2001
From: "Alex L. White" <space.monkey.delivers@gmail.com>
Date: Tue, 17 May 2016 13:13:15 +0300
Subject: [PATCH] Introducing 4 state branch predictor

---
 rtl/verilog/mor1kx_branch_prediction.v | 74 ++++++++++++++++++++++++++++------
 rtl/verilog/mor1kx_cpu_cappuccino.v    |  7 +++-
 2 files changed, 66 insertions(+), 15 deletions(-)

diff --git a/rtl/verilog/mor1kx_branch_prediction.v b/rtl/verilog/mor1kx_branch_prediction.v
index a82c1f9..e903a84 100644
--- a/rtl/verilog/mor1kx_branch_prediction.v
+++ b/rtl/verilog/mor1kx_branch_prediction.v
@@ -18,35 +18,83 @@

 module mor1kx_branch_prediction
   #(
-    parameter OPTION_OPERAND_WIDTH = 32
+    parameter OPTION_OPERAND_WIDTH = 32,
+    parameter FEATURE_4_STATE_PREDICTOR = "NONE"
     )
    (
-    input  clk,
-    input  rst,
+    input clk,
+    input rst,

     // Signals belonging to the stage where the branch is predicted.
-    input  op_bf_i,
-    input  op_bnf_i,
-    input [9:0] immjbr_upper_i,
-    output     predicted_flag_o,
+    input op_bf_i,               // branch if flag
+    input op_bnf_i,              // branch if not flag
+    input [9:0] immjbr_upper_i,  // branch offset
+    output predicted_flag_o,     //result of predictor

     // Signals belonging to the stage where the branch is resolved.
-    input  prev_op_brcond_i,
-    input  prev_predicted_flag_i,
-    input  flag_i,
+    input prev_op_brcond_i,      // prev op was cond brn
+    input prev_predicted_flag_i, // prev insn predicated flag
+    input flag_i,                // prev insn real flag

     // Branch misprediction indicator
-    output     branch_mispredict_o
+    output branch_mispredict_o   // result of prediction
     );

    // Compare the real flag with the previously predicted flag and signal a
    // misprediction in case of a mismatch.
    assign branch_mispredict_o = prev_op_brcond_i &
-               (flag_i != prev_predicted_flag_i);
+                                (flag_i != prev_predicted_flag_i);
+
+generate
+if (FEATURE_4_STATE_PREDICTOR!="NONE") begin : branch_predictor_gen
+   localparam [1:0]
+      STATE_STRONGLY_NOT_TAKEN = 2'b00,
+      STATE_WEAKLY_NOT_TAKEN   = 2'b01,
+      STATE_WEAKLY_TAKEN       = 2'b10,
+      STATE_STRONGLY_TAKEN     = 2'b11;

+   reg [1:0] state = STATE_WEAKLY_TAKEN;
+
+   assign predicted_flag_o = state[1];
+
+   always @(posedge clk) begin
+      if (rst) begin
+         // set default state to STATE_WEAKLY_TAKEN
+         state <= STATE_WEAKLY_TAKEN;
+      end else begin
+         // if prev insn was a branch
+         if (prev_op_brcond_i) begin
+            // if it was mispredicted
+            if (branch_mispredict_o) begin
+               // change fsm state:
+               //   STATE_STRONGLY_TAKEN -> STATE_WEAKLY_TAKEN
+               //   STATE_WEAKLY_TAKEN -> STATE_WEAKLY_NOT_TAKEN
+               //   STATE_WEAKLY_NOT_TAKEN -> STATE_STRONGLY_NOT_TAKEN
+               //   STATE_STRONGLY_NOT_TAKEN -> STATE_STRONGLY_NOT_TAKEN
+               state <= (state == STATE_STRONGLY_TAKEN) ? STATE_WEAKLY_TAKEN :
+                        (state == STATE_WEAKLY_TAKEN)   ? STATE_WEAKLY_NOT_TAKEN
+                                                        : STATE_STRONGLY_NOT_TAKEN;
+            // if prev insn was predicted correctly
+            end else begin
+               // change fsm state:
+               //   STATE_STRONGLY_NOT_TAKEN -> STATE_WEAKLY_NOT_TAKEN
+               //   STATE_WEAKLY_NOT_TAKEN -> STATE_WEAKLY_TAKEN
+               //   STATE_WEAKLY_TAKEN -> STATE_STRONGLY_TAKEN
+               //   STATE_STRONGLY_TAKEN -> STATE_STRONGLY_TAKEN
+               state <= (state == STATE_STRONGLY_NOT_TAKEN) ? STATE_WEAKLY_NOT_TAKEN :
+                        (state == STATE_WEAKLY_NOT_TAKEN)   ? STATE_WEAKLY_TAKEN
+                                                            : STATE_STRONGLY_TAKEN;
+            end
+         end
+      end
+   end
+
+end else begin
    // Static branch prediction - backward branches are predicted as taken,
    // forward branches as not taken.
    assign predicted_flag_o = op_bf_i & immjbr_upper_i[9] |
-                op_bnf_i & !immjbr_upper_i[9];
+                             op_bnf_i & !immjbr_upper_i[9];
+end
+endgenerate

 endmodule
diff --git a/rtl/verilog/mor1kx_cpu_cappuccino.v b/rtl/verilog/mor1kx_cpu_cappuccino.v
index f282374..2af018e 100644
--- a/rtl/verilog/mor1kx_cpu_cappuccino.v
+++ b/rtl/verilog/mor1kx_cpu_cappuccino.v
@@ -96,7 +96,9 @@ module mor1kx_cpu_cappuccino

     parameter FEATURE_MULTICORE = "NONE",

-    parameter FEATURE_TRACEPORT_EXEC = "NONE"
+    parameter FEATURE_TRACEPORT_EXEC = "NONE",
+
+    parameter FEATURE_4_STATE_PREDICTOR = "NONE"
     )
    (
     input                clk,
@@ -752,7 +754,8 @@ module mor1kx_cpu_cappuccino
     );*/
    mor1kx_branch_prediction
      #(
-       .OPTION_OPERAND_WIDTH(OPTION_OPERAND_WIDTH)
+       .OPTION_OPERAND_WIDTH(OPTION_OPERAND_WIDTH),
+       .FEATURE_4_STATE_PREDICTOR(FEATURE_4_STATE_PREDICTOR)
        )
    mor1kx_branch_prediction
      (/*AUTOINST*/
--
1.9.1