2 * Copyright (c) 2004-2005 The Regents of The University of Michigan
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.
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.
29 #include "cpu/o3/tournament_pred.hh"
31 TournamentBP::TournamentBP(unsigned _local_predictor_size
,
32 unsigned _local_ctr_bits
,
33 unsigned _local_history_table_size
,
34 unsigned _local_history_bits
,
35 unsigned _global_predictor_size
,
36 unsigned _global_ctr_bits
,
37 unsigned _global_history_bits
,
38 unsigned _choice_predictor_size
,
39 unsigned _choice_ctr_bits
,
40 unsigned _instShiftAmt
)
41 : localPredictorSize(_local_predictor_size
),
42 localCtrBits(_local_ctr_bits
),
43 localHistoryTableSize(_local_history_table_size
),
44 localHistoryBits(_local_history_bits
),
45 globalPredictorSize(_global_predictor_size
),
46 globalCtrBits(_global_ctr_bits
),
47 globalHistoryBits(_global_history_bits
),
48 choicePredictorSize(_global_predictor_size
),
49 choiceCtrBits(_choice_ctr_bits
),
50 instShiftAmt(_instShiftAmt
)
52 //Should do checks here to make sure sizes are correct (powers of 2)
54 //Setup the array of counters for the local predictor
55 localCtrs
= new SatCounter
[localPredictorSize
];
57 for (int i
= 0; i
< localPredictorSize
; ++i
)
58 localCtrs
[i
].setBits(localCtrBits
);
60 //Setup the history table for the local table
61 localHistoryTable
= new unsigned[localHistoryTableSize
];
63 for (int i
= 0; i
< localHistoryTableSize
; ++i
)
64 localHistoryTable
[i
] = 0;
66 // Setup the local history mask
67 localHistoryMask
= (1 << localHistoryBits
) - 1;
69 //Setup the array of counters for the global predictor
70 globalCtrs
= new SatCounter
[globalPredictorSize
];
72 for (int i
= 0; i
< globalPredictorSize
; ++i
)
73 globalCtrs
[i
].setBits(globalCtrBits
);
75 //Clear the global history
77 // Setup the global history mask
78 globalHistoryMask
= (1 << globalHistoryBits
) - 1;
80 //Setup the array of counters for the choice predictor
81 choiceCtrs
= new SatCounter
[choicePredictorSize
];
83 for (int i
= 0; i
< choicePredictorSize
; ++i
)
84 choiceCtrs
[i
].setBits(choiceCtrBits
);
86 threshold
= (1 << (localCtrBits
- 1)) - 1;
87 threshold
= threshold
/ 2;
92 TournamentBP::calcLocHistIdx(Addr
&branch_addr
)
94 return (branch_addr
>> instShiftAmt
) & (localHistoryTableSize
- 1);
99 TournamentBP::updateHistoriesTaken(unsigned local_history_idx
)
101 globalHistory
= (globalHistory
<< 1) | 1;
102 globalHistory
= globalHistory
& globalHistoryMask
;
104 localHistoryTable
[local_history_idx
] =
105 (localHistoryTable
[local_history_idx
] << 1) | 1;
110 TournamentBP::updateHistoriesNotTaken(unsigned local_history_idx
)
112 globalHistory
= (globalHistory
<< 1);
113 globalHistory
= globalHistory
& globalHistoryMask
;
115 localHistoryTable
[local_history_idx
] =
116 (localHistoryTable
[local_history_idx
] << 1);
120 TournamentBP::lookup(Addr
&branch_addr
)
122 uint8_t local_prediction
;
123 unsigned local_history_idx
;
124 unsigned local_predictor_idx
;
126 uint8_t global_prediction
;
127 uint8_t choice_prediction
;
129 //Lookup in the local predictor to get its branch prediction
130 local_history_idx
= calcLocHistIdx(branch_addr
);
131 local_predictor_idx
= localHistoryTable
[local_history_idx
]
133 local_prediction
= localCtrs
[local_predictor_idx
].read();
135 //Lookup in the global predictor to get its branch prediction
136 global_prediction
= globalCtrs
[globalHistory
].read();
138 //Lookup in the choice predictor to see which one to use
139 choice_prediction
= choiceCtrs
[globalHistory
].read();
141 //@todo Put a threshold value in for the three predictors that can
142 // be set through the constructor (so this isn't hard coded).
143 //Also should put some of this code into functions.
144 if (choice_prediction
> threshold
) {
145 if (global_prediction
> threshold
) {
146 updateHistoriesTaken(local_history_idx
);
148 assert(globalHistory
< globalPredictorSize
&&
149 local_history_idx
< localPredictorSize
);
151 globalCtrs
[globalHistory
].increment();
152 localCtrs
[local_history_idx
].increment();
156 updateHistoriesNotTaken(local_history_idx
);
158 assert(globalHistory
< globalPredictorSize
&&
159 local_history_idx
< localPredictorSize
);
161 globalCtrs
[globalHistory
].decrement();
162 localCtrs
[local_history_idx
].decrement();
167 if (local_prediction
> threshold
) {
168 updateHistoriesTaken(local_history_idx
);
170 assert(globalHistory
< globalPredictorSize
&&
171 local_history_idx
< localPredictorSize
);
173 globalCtrs
[globalHistory
].increment();
174 localCtrs
[local_history_idx
].increment();
178 updateHistoriesNotTaken(local_history_idx
);
180 assert(globalHistory
< globalPredictorSize
&&
181 local_history_idx
< localPredictorSize
);
183 globalCtrs
[globalHistory
].decrement();
184 localCtrs
[local_history_idx
].decrement();
191 // Update the branch predictor if it predicted a branch wrong.
193 TournamentBP::update(Addr
&branch_addr
, unsigned correct_gh
, bool taken
)
196 uint8_t local_prediction
;
197 unsigned local_history_idx
;
198 unsigned local_predictor_idx
;
199 bool local_pred_taken
;
201 uint8_t global_prediction
;
202 bool global_pred_taken
;
204 // Load the correct global history into the register.
205 globalHistory
= correct_gh
;
207 // Get the local predictor's current prediction, remove the incorrect
208 // update, and update the local predictor
209 local_history_idx
= calcLocHistIdx(branch_addr
);
210 local_predictor_idx
= localHistoryTable
[local_history_idx
];
211 local_predictor_idx
= (local_predictor_idx
>> 1) & localHistoryMask
;
213 local_prediction
= localCtrs
[local_predictor_idx
].read();
214 local_pred_taken
= local_prediction
> threshold
;
216 //Get the global predictor's current prediction, and update the
218 global_prediction
= globalCtrs
[globalHistory
].read();
219 global_pred_taken
= global_prediction
> threshold
;
221 //Update the choice predictor to tell it which one was correct
222 if (local_pred_taken
!= global_pred_taken
) {
223 //If the local prediction matches the actual outcome, decerement
224 //the counter. Otherwise increment the counter.
225 if (local_pred_taken
== taken
) {
226 choiceCtrs
[globalHistory
].decrement();
228 choiceCtrs
[globalHistory
].increment();
233 assert(globalHistory
< globalPredictorSize
&&
234 local_predictor_idx
< localPredictorSize
);
236 localCtrs
[local_predictor_idx
].increment();
237 globalCtrs
[globalHistory
].increment();
239 globalHistory
= (globalHistory
<< 1) | 1;
240 globalHistory
= globalHistory
& globalHistoryMask
;
242 localHistoryTable
[local_history_idx
] |= 1;
245 assert(globalHistory
< globalPredictorSize
&&
246 local_predictor_idx
< localPredictorSize
);
248 localCtrs
[local_predictor_idx
].decrement();
249 globalCtrs
[globalHistory
].decrement();
251 globalHistory
= (globalHistory
<< 1);
252 globalHistory
= globalHistory
& globalHistoryMask
;
254 localHistoryTable
[local_history_idx
] &= ~1;