tournament.hh revision 6216 
1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Kevin Lim
29 */
30
31#ifndef __CPU_O3_TOURNAMENT_PRED_HH__
32#define __CPU_O3_TOURNAMENT_PRED_HH__
33
34#include <vector>
35
36#include "base/types.hh"
37#include "cpu/o3/sat_counter.hh"
38
39/**
40 * Implements a tournament branch predictor, hopefully identical to the one
41 * used in the 21264.  It has a local predictor, which uses a local history
42 * table to index into a table of counters, and a global predictor, which
43 * uses a global history to index into a table of counters.  A choice
44 * predictor chooses between the two.  Only the global history register
45 * is speculatively updated, the rest are updated upon branches committing
46 * or misspeculating.
47 */
48class TournamentBP
49{
50  public:
51    /**
52     * Default branch predictor constructor.
53     */
54    TournamentBP(unsigned localPredictorSize,
55                 unsigned localCtrBits,
56                 unsigned localHistoryTableSize,
57                 unsigned localHistoryBits,
58                 unsigned globalPredictorSize,
59                 unsigned globalHistoryBits,
60                 unsigned globalCtrBits,
61                 unsigned choicePredictorSize,
62                 unsigned choiceCtrBits,
63                 unsigned instShiftAmt);
64
65    /**
66     * Looks up the given address in the branch predictor and returns
67     * a true/false value as to whether it is taken.  Also creates a
68     * BPHistory object to store any state it will need on squash/update.
69     * @param branch_addr The address of the branch to look up.
70     * @param bp_history Pointer that will be set to the BPHistory object.
71     * @return Whether or not the branch is taken.
72     */
73    bool lookup(Addr &branch_addr, void * &bp_history);
74
75    /**
76     * Records that there was an unconditional branch, and modifies
77     * the bp history to point to an object that has the previous
78     * global history stored in it.
79     * @param bp_history Pointer that will be set to the BPHistory object.
80     */
81    void uncondBr(void * &bp_history);
82
83    /**
84     * Updates the branch predictor with the actual result of a branch.
85     * @param branch_addr The address of the branch to update.
86     * @param taken Whether or not the branch was taken.
87     * @param bp_history Pointer to the BPHistory object that was created
88     * when the branch was predicted.
89     */
90    void update(Addr &branch_addr, bool taken, void *bp_history);
91
92    /**
93     * Restores the global branch history on a squash.
94     * @param bp_history Pointer to the BPHistory object that has the
95     * previous global branch history in it.
96     */
97    void squash(void *bp_history);
98
99    /** Returns the global history. */
100    inline unsigned readGlobalHist() { return globalHistory; }
101
102  private:
103    /**
104     * Returns if the branch should be taken or not, given a counter
105     * value.
106     * @param count The counter value.
107     */
108    inline bool getPrediction(uint8_t &count);
109
110    /**
111     * Returns the local history index, given a branch address.
112     * @param branch_addr The branch's PC address.
113     */
114    inline unsigned calcLocHistIdx(Addr &branch_addr);
115
116    /** Updates global history as taken. */
117    inline void updateGlobalHistTaken();
118
119    /** Updates global history as not taken. */
120    inline void updateGlobalHistNotTaken();
121
122    /**
123     * Updates local histories as taken.
124     * @param local_history_idx The local history table entry that
125     * will be updated.
126     */
127    inline void updateLocalHistTaken(unsigned local_history_idx);
128
129    /**
130     * Updates local histories as not taken.
131     * @param local_history_idx The local history table entry that
132     * will be updated.
133     */
134    inline void updateLocalHistNotTaken(unsigned local_history_idx);
135
136    /**
137     * The branch history information that is created upon predicting
138     * a branch.  It will be passed back upon updating and squashing,
139     * when the BP can use this information to update/restore its
140     * state properly.
141     */
142    struct BPHistory {
143#ifdef DEBUG
144        BPHistory()
145        { newCount++; }
146        ~BPHistory()
147        { newCount--; }
148
149        static int newCount;
150#endif
151        unsigned globalHistory;
152        bool localPredTaken;
153        bool globalPredTaken;
154        bool globalUsed;
155    };
156
157    /** Local counters. */
158    std::vector<SatCounter> localCtrs;
159
160    /** Size of the local predictor. */
161    unsigned localPredictorSize;
162
163    /** Mask to get the proper index bits into the predictor. */
164    unsigned localPredictorMask;
165
166    /** Number of bits of the local predictor's counters. */
167    unsigned localCtrBits;
168
169    /** Array of local history table entries. */
170    std::vector<unsigned> localHistoryTable;
171
172    /** Size of the local history table. */
173    unsigned localHistoryTableSize;
174
175    /** Number of bits for each entry of the local history table.
176     *  @todo Doesn't this come from the size of the local predictor?
177     */
178    unsigned localHistoryBits;
179
180    /** Mask to get the proper local history. */
181    unsigned localHistoryMask;
182
183    /** Array of counters that make up the global predictor. */
184    std::vector<SatCounter> globalCtrs;
185
186    /** Size of the global predictor. */
187    unsigned globalPredictorSize;
188
189    /** Number of bits of the global predictor's counters. */
190    unsigned globalCtrBits;
191
192    /** Global history register. */
193    unsigned globalHistory;
194
195    /** Number of bits for the global history. */
196    unsigned globalHistoryBits;
197
198    /** Mask to get the proper global history. */
199    unsigned globalHistoryMask;
200
201    /** Array of counters that make up the choice predictor. */
202    std::vector<SatCounter> choiceCtrs;
203
204    /** Size of the choice predictor (identical to the global predictor). */
205    unsigned choicePredictorSize;
206
207    /** Number of bits of the choice predictor's counters. */
208    unsigned choiceCtrBits;
209
210    /** Number of bits to shift the instruction over to get rid of the word
211     *  offset.
212     */
213    unsigned instShiftAmt;
214
215    /** Threshold for the counter value; above the threshold is taken,
216     *  equal to or below the threshold is not taken.
217     */
218    unsigned threshold;
219};
220
221#endif // __CPU_O3_TOURNAMENT_PRED_HH__
222