1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
|
/*
* Copyright (c) 2004-2005 The Regents of The University of Michigan
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met: redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer;
* redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution;
* neither the name of the copyright holders nor the names of its
* contributors may be used to endorse or promote products derived from
* this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* Authors: Kevin Lim
* Korey Sewell
*/
#ifndef __CPU_INORDER_BPRED_UNIT_HH__
#define __CPU_INORDER_BPRED_UNIT_HH__
#include <list>
#include "arch/isa_traits.hh"
#include "base/statistics.hh"
#include "cpu/inst_seq.hh"
#include "cpu/inorder/inorder_dyn_inst.hh"
#include "cpu/inorder/pipeline_traits.hh"
#include "cpu/inorder/resource.hh"
#include "cpu/pred/2bit_local.hh"
#include "cpu/pred/btb.hh"
#include "cpu/pred/ras.hh"
#include "cpu/pred/tournament.hh"
#include "params/InOrderCPU.hh"
/**
* Basically a wrapper class to hold both the branch predictor
* and the BTB.
*/
class BPredUnit
{
private:
enum PredType {
Local,
Tournament
};
PredType predictor;
public:
/**
* @param params The params object, that has the size of the BP and BTB.
*/
BPredUnit(Resource *_res, ThePipeline::Params *params);
std::string name();
/**
* Registers statistics.
*/
void regStats();
void switchOut();
void takeOverFrom();
/**
* Predicts whether or not the instruction is a taken branch, and the
* target of the branch if it is taken.
* @param inst The branch instruction.
* @param predPC The predicted PC is passed back through this parameter.
* @param tid The thread id.
* @return Returns if the branch is taken or not.
*/
bool predict(ThePipeline::DynInstPtr &inst,
TheISA::PCState &predPC, ThreadID tid);
// @todo: Rename this function.
void BPUncond(void * &bp_history);
/**
* Tells the branch predictor to commit any updates until the given
* sequence number.
* @param done_sn The sequence number to commit any older updates up until.
* @param tid The thread id.
*/
void update(const InstSeqNum &done_sn, ThreadID tid);
/**
* Squashes all outstanding updates until a given sequence number.
* @param squashed_sn The sequence number to squash any younger updates up
* until.
* @param tid The thread id.
*/
void squash(const InstSeqNum &squashed_sn, ThreadID tid,
ThreadID asid = 0);
/**
* Squashes all outstanding updates until a given sequence number, and
* corrects that sn's update with the proper address and taken/not taken.
* @param squashed_sn The sequence number to squash any younger updates up
* until.
* @param corrTarget The correct branch target.
* @param actually_taken The correct branch direction.
* @param tid The thread id.
*/
void squash(const InstSeqNum &squashed_sn,
const TheISA::PCState &corrTarget, bool actually_taken,
ThreadID tid, ThreadID asid = 0);
/**
* @param bp_history Pointer to the history object. The predictor
* will need to update any state and delete the object.
*/
void BPSquash(void *bp_history);
/**
* Looks up a given PC in the BP to see if it is taken or not taken.
* @param inst_PC The PC to look up.
* @param bp_history Pointer that will be set to an object that
* has the branch predictor state associated with the lookup.
* @return Whether the branch is taken or not taken.
*/
bool BPLookup(Addr instPC, void * &bp_history);
/**
* Looks up a given PC in the BTB to see if a matching entry exists.
* @param inst_PC The PC to look up.
* @return Whether the BTB contains the given PC.
*/
bool BTBValid(Addr &inst_PC)
{ return BTB.valid(inst_PC, 0); }
/**
* Looks up a given PC in the BTB to get the predicted target.
* @param inst_PC The PC to look up.
* @return The address of the target of the branch.
*/
TheISA::PCState BTBLookup(Addr instPC)
{ return BTB.lookup(instPC, 0); }
/**
* Updates the BP with taken/not taken information.
* @param instPC The branch's PC that will be updated.
* @param taken Whether the branch was taken or not taken.
* @param bp_history Pointer to the branch predictor state that is
* associated with the branch lookup that is being updated.
* @todo Make this update flexible enough to handle a global predictor.
*/
void BPUpdate(Addr instPC, bool taken, void *bp_history);
/**
* Updates the BTB with the target of a branch.
* @param inst_PC The branch's PC that will be updated.
* @param target_PC The branch's target that will be added to the BTB.
*/
void BTBUpdate(Addr instPC, const TheISA::PCState &targetPC)
{ BTB.update(instPC, targetPC, 0); }
void dump();
private:
int instSize;
Resource *res;
struct PredictorHistory {
/**
* Makes a predictor history struct that contains any
* information needed to update the predictor, BTB, and RAS.
*/
PredictorHistory(const InstSeqNum &seq_num,
const TheISA::PCState &instPC, bool pred_taken,
void *bp_history, ThreadID _tid)
: seqNum(seq_num), pc(instPC), rasTarget(0), RASIndex(0),
tid(_tid), predTaken(pred_taken), usedRAS(0), wasCall(0),
bpHistory(bp_history)
{}
/** The sequence number for the predictor history entry. */
InstSeqNum seqNum;
/** The PC associated with the sequence number. */
TheISA::PCState pc;
/** The RAS target (only valid if a return). */
TheISA::PCState rasTarget;
/** The RAS index of the instruction (only valid if a call). */
unsigned RASIndex;
/** The thread id. */
ThreadID tid;
/** Whether or not it was predicted taken. */
bool predTaken;
/** Whether or not the RAS was used. */
bool usedRAS;
/** Whether or not the instruction was a call. */
bool wasCall;
/** Pointer to the history object passed back from the branch
* predictor. It is used to update or restore state of the
* branch predictor.
*/
void *bpHistory;
};
typedef std::list<PredictorHistory> History;
typedef History::iterator HistoryIt;
/**
* The per-thread predictor history. This is used to update the predictor
* as instructions are committed, or restore it to the proper state after
* a squash.
*/
History predHist[ThePipeline::MaxThreads];
/** The local branch predictor. */
LocalBP *localBP;
/** The tournament branch predictor. */
TournamentBP *tournamentBP;
/** The BTB. */
DefaultBTB BTB;
/** The per-thread return address stack. */
ReturnAddrStack RAS[ThePipeline::MaxThreads];
/** Stat for number of BP lookups. */
Stats::Scalar lookups;
/** Stat for number of conditional branches predicted. */
Stats::Scalar condPredicted;
/** Stat for number of conditional branches predicted incorrectly. */
Stats::Scalar condIncorrect;
/** Stat for number of BTB lookups. */
Stats::Scalar BTBLookups;
/** Stat for number of BTB hits. */
Stats::Scalar BTBHits;
/** Stat for number of times the BTB is correct. */
Stats::Scalar BTBCorrect;
/** Stat for number of times the RAS is used to get a target. */
Stats::Scalar usedRAS;
/** Stat for number of times the RAS is incorrect. */
Stats::Scalar RASIncorrect;
Stats::Formula BTBHitPct;
};
#endif // __CPU_INORDER_BPRED_UNIT_HH__
|
