`timescale 1ns / 1ps

// Testbench for G-Share Branch Predictor
// Tests prediction, training, misprediction recovery, and simultaneous operations
module tb_gshare_predictor;
    // Clock and Reset
    reg clk;
    reg areset;
    
    // Prediction interface
    reg predict_valid;
    reg [6:0] predict_pc;
    wire predict_taken;
    wire [6:0] predict_history;
    
    // Training interface
    reg train_valid;
    reg train_taken;
    reg train_mispredicted;
    reg [6:0] train_history;
    reg [6:0] train_pc;
    
    // Test control
    integer errors = 0;
    
    // Golden model state (tracks what RTL registers SHOULD be after last clock edge)
    reg [1:0] pht_golden [0:127];
    reg [6:0] ghr_golden;
    
    // Pending updates (to be applied after clock edge)
    reg [6:0] next_ghr;
    reg [1:0] next_pht_val;
    reg [6:0] next_pht_idx;
    reg pht_update_pending;
    
    integer i;
    
    // Instantiate UUT
    gshare_predictor uut (
        .clk(clk),
        .areset(areset),
        .predict_valid(predict_valid),
        .predict_pc(predict_pc),
        .predict_taken(predict_taken),
        .predict_history(predict_history),
        .train_valid(train_valid),
        .train_taken(train_taken),
        .train_mispredicted(train_mispredicted),
        .train_history(train_history),
        .train_pc(train_pc)
    );
    
    // Clock Generation (100MHz)
    initial begin
        clk = 0;
        forever #5 clk = ~clk;
    end
    
    // Golden model reset
    task golden_reset;
        begin
            ghr_golden = 7'b0;
            for (i = 0; i < 128; i = i + 1)
                pht_golden[i] = 2'b01;  // Weakly not-taken
            next_ghr = 7'b0;
            pht_update_pending = 0;
        end
    endtask
    
    // Compute expected combinational output given current golden state
    function [0:0] expected_predict_taken;
        input [6:0] pc;
        reg [6:0] idx;
        begin
            idx = pc ^ ghr_golden;
            expected_predict_taken = pht_golden[idx][1];
        end
    endfunction
    
    // Apply a reset cycle
    task do_reset;
        begin
            areset = 1;
            predict_valid = 0;
            predict_pc = 0;
            train_valid = 0;
            train_pc = 0;
            train_history = 0;
            train_taken = 0;
            train_mispredicted = 0;
            golden_reset;
            @(posedge clk);
            @(posedge clk);
            areset = 0;
            @(posedge clk);
            #1;
        end
    endtask
    
    // Apply inputs, wait for clock, then update golden model
    // Check prediction outputs BEFORE clock edge (they're combinational)
    task cycle;
        input [255:0] test_name;
        input pv;
        input [6:0] ppc;
        input tv;
        input [6:0] tpc;
        input [6:0] th;
        input tt;
        input tm;
        
        reg [6:0] golden_idx;
        reg expected_taken;
        reg [6:0] train_idx;
        begin
            // Set inputs
            predict_valid = pv;
            predict_pc = ppc;
            train_valid = tv;
            train_pc = tpc;
            train_history = th;
            train_taken = tt;
            train_mispredicted = tm;
            
            // Wait for combinational logic to settle
            #1;
            
            // Check prediction outputs (combinational, based on CURRENT ghr_golden)
            if (pv) begin
                golden_idx = ppc ^ ghr_golden;
                expected_taken = pht_golden[golden_idx][1];
                
                if (predict_taken !== expected_taken) begin
                    $display("ERROR [%s]: predict_taken mismatch. Expected %b, got %b (idx=%0d, pht=%b)", 
                             test_name, expected_taken, predict_taken, golden_idx, pht_golden[golden_idx]);
                    errors = errors + 1;
                end
                if (predict_history !== ghr_golden) begin
                    $display("ERROR [%s]: predict_history mismatch. Expected %0d, got %0d", 
                             test_name, ghr_golden, predict_history);
                    errors = errors + 1;
                end
            end
            
            // Wait for clock edge (updates happen here in RTL)
            @(posedge clk);
            #1;
            
            // Now update golden model to match what RTL did at clock edge
            
            // PHT update from training
            if (tv) begin
                train_idx = tpc ^ th;
                if (tt) begin
                    if (pht_golden[train_idx] != 2'b11)
                        pht_golden[train_idx] = pht_golden[train_idx] + 1;
                end else begin
                    if (pht_golden[train_idx] != 2'b00)
                        pht_golden[train_idx] = pht_golden[train_idx] - 1;
                end
            end
            
            // GHR update (training misprediction takes priority over prediction)
            if (tv && tm) begin
                ghr_golden = {th[5:0], tt};
            end else if (pv) begin
                // Shift in the predicted value (which was based on OLD ghr)
                golden_idx = ppc ^ (ghr_golden);  // Recalculate with OLD ghr
                expected_taken = pht_golden[golden_idx][1];  // Note: PHT may have been updated above
                // But wait - we need the pre-update PHT value for the prediction!
            end
        end
    endtask
    
    // Simplified cycle that properly handles timing
    // Key insight: prediction is combinational (based on current cycle's GHR)
    // GHR and PHT updates happen at clock edge
    task apply_cycle;
        input [255:0] test_name;
        input pv;
        input [6:0] ppc;
        input tv;
        input [6:0] tpc;
        input [6:0] th;
        input tt;
        input tm;
        
        reg [6:0] predict_idx;
        reg expected_taken;
        reg [6:0] train_idx;
        reg [1:0] old_pht_val;
        begin
            // Set inputs
            predict_valid = pv;
            predict_pc = ppc;
            train_valid = tv;
            train_pc = tpc;
            train_history = th;
            train_taken = tt;
            train_mispredicted = tm;
            
            // Calculate expected COMBINATIONAL outputs (using current ghr_golden and pht_golden)
            predict_idx = ppc ^ ghr_golden;
            expected_taken = pht_golden[predict_idx][1];
            
            // Wait for combinational logic
            #1;
            
            // Check prediction outputs
            if (pv) begin
                if (predict_taken !== expected_taken) begin
                    $display("ERROR [%s]: predict_taken mismatch. Expected %b, got %b (idx=%0d)", 
                             test_name, expected_taken, predict_taken, predict_idx);
                    errors = errors + 1;
                end
                if (predict_history !== ghr_golden) begin
                    $display("ERROR [%s]: predict_history mismatch. Expected %0d, got %0d", 
                             test_name, ghr_golden, predict_history);
                    errors = errors + 1;
                end
            end
            
            // Wait for clock edge
            @(posedge clk);
            #1;
            
            // Update golden model to reflect what happened at clock edge
            
            // PHT update from training
            if (tv) begin
                train_idx = tpc ^ th;
                if (tt) begin
                    if (pht_golden[train_idx] != 2'b11)
                        pht_golden[train_idx] = pht_golden[train_idx] + 1;
                end else begin
                    if (pht_golden[train_idx] != 2'b00)
                        pht_golden[train_idx] = pht_golden[train_idx] - 1;
                end
            end
            
            // GHR update: training misprediction takes priority
            if (tv && tm) begin
                ghr_golden = {th[5:0], tt};
            end else if (pv) begin
                // Shift in the prediction we made (which was expected_taken)
                ghr_golden = {ghr_golden[5:0], expected_taken};
            end
        end
    endtask
    
    // Main test procedure
    initial begin
        $display("===========================================");
        $display("  G-Share Branch Predictor Testbench");
        $display("===========================================");
        
        // Initialize
        areset = 1;
        predict_valid = 0;
        predict_pc = 0;
        train_valid = 0;
        train_pc = 0;
        train_history = 0;
        train_taken = 0;
        train_mispredicted = 0;
        
        // ========================================
        // Test 1: Reset state verification
        // ========================================
        $display("\n--- Test 1: Reset State ---");
        do_reset;
        
        // Predict with PC=0, should see weakly not-taken (counter=01) -> predict 0
        apply_cycle("Reset-Predict", 1, 7'h00, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: Initial prediction correct");
        
        // ========================================
        // Test 2: Basic prediction sequence
        // ========================================
        $display("\n--- Test 2: Basic Predictions ---");
        do_reset;
        
        apply_cycle("Pred-PC0", 1, 7'h00, 0, 0, 0, 0, 0);
        apply_cycle("Pred-PC1", 1, 7'h01, 0, 0, 0, 0, 0);
        apply_cycle("Pred-PC7F", 1, 7'h7F, 0, 0, 0, 0, 0);
        apply_cycle("Pred-PC55", 1, 7'h55, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: Basic predictions correct");
        
        // ========================================
        // Test 3: Training to taken
        // ========================================
        $display("\n--- Test 3: Training to Taken ---");
        do_reset;
        
        // Train entry 0 to taken: 01 -> 10 -> 11
        apply_cycle("Train1", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        apply_cycle("Train2", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        
        // Now predict - should be taken (PHT[0] = 11)
        apply_cycle("Pred-After-Train", 1, 7'h00, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: Prediction changes after training");
        
        // ========================================
        // Test 4: Training saturation
        // ========================================
        $display("\n--- Test 4: Training Saturation ---");
        do_reset;
        
        // Train to not-taken until saturation: 01 -> 00
        apply_cycle("TrainNT1", 0, 0, 1, 7'h00, 7'h00, 0, 0);
        apply_cycle("TrainNT2", 0, 0, 1, 7'h00, 7'h00, 0, 0);  // Should saturate
        apply_cycle("TrainNT3", 0, 0, 1, 7'h00, 7'h00, 0, 0);  // Should stay at 00
        
        apply_cycle("Pred-NT", 1, 7'h00, 0, 0, 0, 0, 0);
        
        // Train back to taken: 00 -> 01 -> 10 -> 11
        apply_cycle("TrainT1", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        apply_cycle("TrainT2", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        apply_cycle("TrainT3", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        apply_cycle("TrainT4", 0, 0, 1, 7'h00, 7'h00, 1, 0);  // Should saturate
        
        apply_cycle("Pred-T", 1, 7'h00, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: Counter saturation works");
        
        // ========================================
        // Test 5: GHR shifts on prediction
        // ========================================
        $display("\n--- Test 5: GHR Update from Prediction ---");
        do_reset;
        
        // Train entry 0 to taken
        apply_cycle("Setup1", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        apply_cycle("Setup2", 0, 0, 1, 7'h00, 7'h00, 1, 0);
        
        // Predict - should be taken, GHR should become 1
        apply_cycle("PredT", 1, 7'h00, 0, 0, 0, 0, 0);
        
        // Check that GHR is now 1
        if (ghr_golden != 7'd1) begin
            $display("ERROR: GHR should be 1 after taken prediction, got %0d", ghr_golden);
            errors = errors + 1;
        end
        
        // Predict again - now accesses different entry (PC=0, GHR=1 -> idx=1)
        apply_cycle("PredAgain", 1, 7'h00, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: GHR shifts correctly");
        
        // ========================================
        // Test 6: Misprediction GHR recovery
        // ========================================
        $display("\n--- Test 6: Misprediction Recovery ---");
        do_reset;
        
        // Make predictions (all not-taken, so GHR stays 0)
        apply_cycle("P1", 1, 7'h10, 0, 0, 0, 0, 0);
        apply_cycle("P2", 1, 7'h20, 0, 0, 0, 0, 0);
        apply_cycle("P3", 1, 7'h30, 0, 0, 0, 0, 0);
        
        // Train with misprediction - GHR should recover to {train_history[5:0], train_taken}
        // train_history = 0b1010101, train_taken = 1
        // new GHR = {010101, 1} = 0b0101011 = 43
        apply_cycle("Mispredict", 0, 0, 1, 7'h00, 7'b1010101, 1, 1);
        
        // Verify GHR recovered
        if (ghr_golden != 7'd43) begin
            $display("ERROR: GHR should be 43 after recovery, got %0d", ghr_golden);
            errors = errors + 1;
        end else begin
            $display("  PASS: GHR recovered correctly to %0d", ghr_golden);
        end
        
        // ========================================
        // Test 7: XOR indexing verification
        // ========================================
        $display("\n--- Test 7: XOR Indexing ---");
        do_reset;
        
        // Train PC=0x55, history=0x2A -> index = 0x55 ^ 0x2A = 0x7F
        apply_cycle("TrainXOR1", 0, 0, 1, 7'h55, 7'h2A, 1, 0);  // PHT[0x7F]: 01->10
        apply_cycle("TrainXOR2", 0, 0, 1, 7'h55, 7'h2A, 1, 0);  // PHT[0x7F]: 10->11
        
        // Set GHR to 0x2A: train with history=0b0010101, taken=0/mispredicted
        // GHR = {010101, 0} = 0b0101010 = 0x2A
        apply_cycle("SetGHR", 0, 0, 1, 7'h00, 7'b0010101, 0, 1);
        
        // Verify GHR
        if (ghr_golden != 7'h2A) begin
            $display("DEBUG: GHR is %0d, expected 42", ghr_golden);
        end
        
        // Predict PC=0x55 with GHR=0x2A -> index = 0x7F -> should be taken
        apply_cycle("PredXOR", 1, 7'h55, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: XOR indexing correct");
        
        // ========================================
        // Test 8: Simultaneous train + predict (same entry)
        // ========================================
        $display("\n--- Test 8: Simultaneous Train + Predict (same entry) ---");
        do_reset;
        
        // Both access entry 0 - prediction sees OLD PHT value
        // Initial PHT[0] = 01 -> predict not-taken
        apply_cycle("Simul-Same", 1, 7'h00, 1, 7'h00, 7'h00, 1, 0);
        
        // After this cycle, PHT[0] = 10, GHR = 0 (shifted in not-taken prediction)
        // Predict again - should now be taken
        apply_cycle("Verify-After", 1, 7'h00, 0, 0, 0, 0, 0);
        if (errors == 0) $display("  PASS: Prediction sees pre-training PHT state");
        
        // ========================================
        // Test 9: Training priority for GHR
        // ========================================
        $display("\n--- Test 9: Training Priority for GHR ---");
        do_reset;
        
        // Both train (mispredict) and predict in same cycle
        // Training should take priority for GHR
        // train_history = 0b0101010, train_taken = 0, mispredicted = 1
        // GHR should become {101010, 0} = 0b1010100 = 84
        apply_cycle("Priority", 1, 7'h00, 1, 7'h00, 7'b0101010, 0, 1);
        
        // Verify GHR reflects training, not prediction
        if (ghr_golden != 7'd84) begin
            $display("ERROR: GHR should be 84 (training priority), got %0d", ghr_golden);
            errors = errors + 1;
        end else begin
            $display("  PASS: Training takes priority for GHR update");
        end
        
        // ========================================
        // Test 10: Extended sequence
        // ========================================
        $display("\n--- Test 10: Extended Sequence ---");
        do_reset;
        
        // Series of predictions
        for (i = 0; i < 16; i = i + 1) begin
            apply_cycle("ExtPred", 1, i[6:0], 0, 0, 0, 0, 0);
        end
        
        // Series of training
        for (i = 0; i < 8; i = i + 1) begin
            apply_cycle("ExtTrain", 0, 0, 1, i[6:0], 7'h00, i[0], 0);
        end
        
        if (errors == 0) $display("  PASS: Extended sequence completed");
        
        // ========================================
        // Test 11: PHT Entry Coverage (verify indexing works for various entries)
        // ========================================
        $display("\n--- Test 11: PHT Entry Coverage ---");
        do_reset;
        
        // Test a subset of PHT entries using XOR with different PCs and histories
        // Train entry 10 (PC=5, history=15 -> 5^15=10)
        apply_cycle("TrainE10a", 0, 0, 1, 7'd5, 7'd15, 1, 0);
        apply_cycle("TrainE10b", 0, 0, 1, 7'd5, 7'd15, 1, 0);
        
        // Train entry 100 (PC=50, history=86 -> 50^86=100)
        apply_cycle("TrainE100a", 0, 0, 1, 7'd50, 7'd86, 1, 0);
        apply_cycle("TrainE100b", 0, 0, 1, 7'd50, 7'd86, 1, 0);
        
        // Train entry 127 (PC=64, history=63 -> 64^63=127)
        apply_cycle("TrainE127a", 0, 0, 1, 7'd64, 7'd63, 1, 0);
        apply_cycle("TrainE127b", 0, 0, 1, 7'd64, 7'd63, 1, 0);
        
        // Verify entries by setting GHR via misprediction and predicting
        
        // Verify entry 10: set GHR=15, predict PC=5
        apply_cycle("SetGHR15", 0, 0, 1, 7'd0, 7'd7, 1, 1);  // GHR = {0000111, 1} = 15
        if (ghr_golden != 7'd15) begin
            $display("DEBUG: GHR is %0d, expected 15", ghr_golden);
        end
        apply_cycle("VerifyE10", 1, 7'd5, 0, 0, 0, 0, 0);
        
        // Verify entry 100: set GHR=86, predict PC=50
        apply_cycle("SetGHR86", 0, 0, 1, 7'd0, 7'd43, 0, 1);  // GHR = {0101011, 0} = 86
        if (ghr_golden != 7'd86) begin
            $display("DEBUG: GHR is %0d, expected 86", ghr_golden);
        end
        apply_cycle("VerifyE100", 1, 7'd50, 0, 0, 0, 0, 0);
        
        // Verify entry 127: set GHR=63, predict PC=64
        apply_cycle("SetGHR63", 0, 0, 1, 7'd0, 7'd31, 1, 1);  // GHR = {0011111, 1} = 63
        if (ghr_golden != 7'd63) begin
            $display("DEBUG: GHR is %0d, expected 63", ghr_golden);
        end
        apply_cycle("VerifyE127", 1, 7'd64, 0, 0, 0, 0, 0);
        
        if (errors == 0) $display("  PASS: PHT entry coverage verified");
        
        // ========================================
        // Final Results
        // ========================================
        $display("\n===========================================");
        if (errors == 0) begin
            $display("TEST_RESULT: PASS");
        end else begin
            $display("TEST_RESULT: FAIL (%0d errors)", errors);
        end
        $display("===========================================");
        
        $finish;
    end

endmodule