From 9472b6f88f8d74841be7ce2fe1ebef28a20beb23 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 | 84 ++++++++++++++++++++++++++--------
 rtl/verilog/mor1kx_cpu_cappuccino.v    |  7 ++-
 2 files changed, 71 insertions(+), 20 deletions(-)

diff --git a/rtl/verilog/mor1kx_branch_prediction.v b/rtl/verilog/mor1kx_branch_prediction.v
index a82c1f9..dfce694 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,

     // 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);
-
-   // 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];
+  // 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);
+
+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];
+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