tournament.hh revision 1062 
1#ifndef __TOURNAMENT_PRED_HH__
2#define __TOURNAMENT_PRED_HH__
3
4// For Addr type.
5#include "arch/alpha/isa_traits.hh"
6
7class TournamentBP
8{
9  public:
10    /**
11     * Default branch predictor constructor.
12     */
13    TournamentBP(unsigned local_predictor_size,
14                 unsigned local_ctr_bits,
15                 unsigned local_history_table_size,
16                 unsigned local_history_bits,
17                 unsigned global_predictor_size,
18                 unsigned global_history_bits,
19                 unsigned global_ctr_bits,
20                 unsigned choice_predictor_size,
21                 unsigned choice_ctr_bits,
22                 unsigned instShiftAmt);
23
24    /**
25     * Looks up the given address in the branch predictor and returns
26     * a true/false value as to whether it is taken.
27     * @param branch_addr The address of the branch to look up.
28     * @return Whether or not the branch is taken.
29     */
30    bool lookup(Addr &branch_addr);
31
32    /**
33     * Updates the branch predictor with the actual result of a branch.
34     * @param branch_addr The address of the branch to update.
35     * @param taken Whether or not the branch was taken.
36     */
37    void update(Addr &branch_addr, unsigned global_history, bool taken);
38
39    inline unsigned readGlobalHist() { return global_history; }
40
41  private:
42
43    inline bool getPrediction(uint8_t &count);
44
45    inline unsigned calcLocHistIdx(Addr &branch_addr);
46
47    inline void updateHistoriesTaken(unsigned local_history_idx);
48
49    inline void updateHistoriesNotTaken(unsigned local_history_idx);
50
51    /**
52     * Private counter class for the internal saturating counters.
53     * Implements an n bit saturating counter and provides methods to
54     * increment, decrement, and read it.
55     * @todo Consider making this something that more closely mimics a
56     * built in class so you can use ++ or --.
57     */
58    class SatCounter
59    {
60      public:
61        /**
62         * Constructor for the counter.
63         * @param bits How many bits the counter will have.
64         */
65        SatCounter(unsigned bits);
66
67        /**
68         * Constructor for the counter.
69         * @param bits How many bits the counter will have.
70         * @param initial_val Starting value for each counter.
71         */
72        SatCounter(unsigned bits, unsigned initial_val);
73
74        /**
75         * Increments the counter's current value.
76         */
77        void increment();
78
79        /**
80         * Decrements the counter's current value.
81         */
82        void decrement();
83
84        /**
85         * Read the counter's value.
86         */
87        uint8_t read()
88        {
89            return counter;
90        }
91
92      private:
93        uint8_t maxVal;
94        uint8_t counter;
95    };
96
97    /** Local counters. */
98    SatCounter *local_ctrs;
99
100    /** Size of the local predictor. */
101    unsigned local_predictor_size;
102
103    /** Number of bits of the local predictor's counters. */
104    unsigned local_ctr_bits;
105
106    /** Array of local history table entries. */
107    unsigned *local_history_table;
108
109    /** Size of the local history table. */
110    unsigned local_history_table_size;
111
112    /** Number of bits for each entry of the local history table.
113     *  @todo Doesn't this come from the size of the local predictor?
114     */
115    unsigned local_history_bits;
116
117    /** Mask to get the proper local history. */
118    unsigned localHistoryMask;
119
120
121    /** Array of counters that make up the global predictor. */
122    SatCounter *global_ctrs;
123
124    /** Size of the global predictor. */
125    unsigned global_predictor_size;
126
127    /** Number of bits of the global predictor's counters. */
128    unsigned global_ctr_bits;
129
130    /** Global history register. */
131    unsigned global_history;
132
133    /** Number of bits for the global history. */
134    unsigned global_history_bits;
135
136    /** Mask to get the proper global history. */
137    unsigned globalHistoryMask;
138
139
140    /** Array of counters that make up the choice predictor. */
141    SatCounter *choice_ctrs;
142
143    /** Size of the choice predictor (identical to the global predictor). */
144    unsigned choice_predictor_size;
145
146    /** Number of bits of the choice predictor's counters. */
147    unsigned choice_ctr_bits;
148
149    /** Number of bits to shift the instruction over to get rid of the word
150     *  offset.
151     */
152    unsigned instShiftAmt;
153
154    /** Threshold for the counter value; above the threshold is taken,
155     *  equal to or below the threshold is not taken.
156     */
157    unsigned threshold;
158};
159
160#endif // __TOURNAMENT_PRED_HH__
161