bpred_unit.cc revision 11721:b0853929e223 
1/*
2 * Copyright (c) 2011-2012, 2014 ARM Limited
3 * Copyright (c) 2010 The University of Edinburgh
4 * Copyright (c) 2012 Mark D. Hill and David A. Wood
5 * All rights reserved
6 *
7 * The license below extends only to copyright in the software and shall
8 * not be construed as granting a license to any other intellectual
9 * property including but not limited to intellectual property relating
10 * to a hardware implementation of the functionality of the software
11 * licensed hereunder.  You may use the software subject to the license
12 * terms below provided that you ensure that this notice is replicated
13 * unmodified and in its entirety in all distributions of the software,
14 * modified or unmodified, in source code or in binary form.
15 *
16 * Copyright (c) 2004-2005 The Regents of The University of Michigan
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met: redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer;
23 * redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution;
26 * neither the name of the copyright holders nor the names of its
27 * contributors may be used to endorse or promote products derived from
28 * this software without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Authors: Kevin Lim
43 */
44
45#include "cpu/pred/bpred_unit.hh"
46
47#include <algorithm>
48
49#include "arch/isa_traits.hh"
50#include "arch/types.hh"
51#include "arch/utility.hh"
52#include "base/trace.hh"
53#include "config/the_isa.hh"
54#include "debug/Branch.hh"
55
56BPredUnit::BPredUnit(const Params *params)
57    : SimObject(params),
58      numThreads(params->numThreads),
59      predHist(numThreads),
60      BTB(params->BTBEntries,
61          params->BTBTagSize,
62          params->instShiftAmt,
63          params->numThreads),
64      RAS(numThreads),
65      useIndirect(params->useIndirect),
66      iPred(params->indirectHashGHR,
67            params->indirectHashTargets,
68            params->indirectSets,
69            params->indirectWays,
70            params->indirectTagSize,
71            params->indirectPathLength,
72            params->instShiftAmt,
73            params->numThreads),
74      instShiftAmt(params->instShiftAmt)
75{
76    for (auto& r : RAS)
77        r.init(params->RASSize);
78}
79
80void
81BPredUnit::regStats()
82{
83    SimObject::regStats();
84
85    lookups
86        .name(name() + ".lookups")
87        .desc("Number of BP lookups")
88        ;
89
90    condPredicted
91        .name(name() + ".condPredicted")
92        .desc("Number of conditional branches predicted")
93        ;
94
95    condIncorrect
96        .name(name() + ".condIncorrect")
97        .desc("Number of conditional branches incorrect")
98        ;
99
100    BTBLookups
101        .name(name() + ".BTBLookups")
102        .desc("Number of BTB lookups")
103        ;
104
105    BTBHits
106        .name(name() + ".BTBHits")
107        .desc("Number of BTB hits")
108        ;
109
110    BTBCorrect
111        .name(name() + ".BTBCorrect")
112        .desc("Number of correct BTB predictions (this stat may not "
113              "work properly.")
114        ;
115
116    BTBHitPct
117        .name(name() + ".BTBHitPct")
118        .desc("BTB Hit Percentage")
119        .precision(6);
120    BTBHitPct = (BTBHits / BTBLookups) * 100;
121
122    usedRAS
123        .name(name() + ".usedRAS")
124        .desc("Number of times the RAS was used to get a target.")
125        ;
126
127    RASIncorrect
128        .name(name() + ".RASInCorrect")
129        .desc("Number of incorrect RAS predictions.")
130        ;
131
132    indirectLookups
133        .name(name() + ".indirectLookups")
134        .desc("Number of indirect predictor lookups.")
135        ;
136
137    indirectHits
138        .name(name() + ".indirectHits")
139        .desc("Number of indirect target hits.")
140        ;
141
142    indirectMisses
143        .name(name() + ".indirectMisses")
144        .desc("Number of indirect misses.")
145        ;
146
147    indirectMispredicted
148        .name(name() + "indirectMispredicted")
149        .desc("Number of mispredicted indirect branches.")
150        ;
151
152}
153
154ProbePoints::PMUUPtr
155BPredUnit::pmuProbePoint(const char *name)
156{
157    ProbePoints::PMUUPtr ptr;
158    ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
159
160    return ptr;
161}
162
163void
164BPredUnit::regProbePoints()
165{
166    ppBranches = pmuProbePoint("Branches");
167    ppMisses = pmuProbePoint("Misses");
168}
169
170void
171BPredUnit::drainSanityCheck() const
172{
173    // We shouldn't have any outstanding requests when we resume from
174    // a drained system.
175    for (const auto& ph M5_VAR_USED : predHist)
176        assert(ph.empty());
177}
178
179bool
180BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
181                   TheISA::PCState &pc, ThreadID tid)
182{
183    // See if branch predictor predicts taken.
184    // If so, get its target addr either from the BTB or the RAS.
185    // Save off record of branch stuff so the RAS can be fixed
186    // up once it's done.
187
188    bool pred_taken = false;
189    TheISA::PCState target = pc;
190
191    ++lookups;
192    ppBranches->notify(1);
193
194    void *bp_history = NULL;
195
196    if (inst->isUncondCtrl()) {
197        DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
198        pred_taken = true;
199        // Tell the BP there was an unconditional branch.
200        uncondBranch(tid, pc.instAddr(), bp_history);
201    } else {
202        ++condPredicted;
203        pred_taken = lookup(tid, pc.instAddr(), bp_history);
204
205        DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
206                " predicted %i for PC %s\n", tid, seqNum,  pred_taken, pc);
207    }
208
209    DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
210            "for PC %s\n", tid, seqNum, pc);
211
212    PredictorHistory predict_record(seqNum, pc.instAddr(),
213                                    pred_taken, bp_history, tid);
214
215    // Now lookup in the BTB or RAS.
216    if (pred_taken) {
217        if (inst->isReturn()) {
218            ++usedRAS;
219            predict_record.wasReturn = true;
220            // If it's a function return call, then look up the address
221            // in the RAS.
222            TheISA::PCState rasTop = RAS[tid].top();
223            target = TheISA::buildRetPC(pc, rasTop);
224
225            // Record the top entry of the RAS, and its index.
226            predict_record.usedRAS = true;
227            predict_record.RASIndex = RAS[tid].topIdx();
228            predict_record.RASTarget = rasTop;
229
230            RAS[tid].pop();
231
232            DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
233                    "RAS predicted target: %s, RAS index: %i.\n",
234                    tid, pc, target, predict_record.RASIndex);
235        } else {
236            ++BTBLookups;
237
238            if (inst->isCall()) {
239                RAS[tid].push(pc);
240                predict_record.pushedRAS = true;
241
242                // Record that it was a call so that the top RAS entry can
243                // be popped off if the speculation is incorrect.
244                predict_record.wasCall = true;
245
246                DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
247                        "call, adding %s to the RAS index: %i.\n",
248                        tid, pc, pc, RAS[tid].topIdx());
249            }
250
251            if (inst->isDirectCtrl() || !useIndirect) {
252                // Check BTB on direct branches
253                if (BTB.valid(pc.instAddr(), tid)) {
254                    ++BTBHits;
255
256                    // If it's not a return, use the BTB to get target addr.
257                    target = BTB.lookup(pc.instAddr(), tid);
258
259                    DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
260                            " target is %s.\n", tid, pc, target);
261
262                } else {
263                    DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
264                            "valid entry.\n",tid);
265                    pred_taken = false;
266                    // The Direction of the branch predictor is altered
267                    // because the BTB did not have an entry
268                    // The predictor needs to be updated accordingly
269                    if (!inst->isCall() && !inst->isReturn()) {
270                        btbUpdate(tid, pc.instAddr(), bp_history);
271                        DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
272                                " called for %s\n", tid, seqNum, pc);
273                    } else if (inst->isCall() && !inst->isUncondCtrl()) {
274                        RAS[tid].pop();
275                        predict_record.pushedRAS = false;
276                    }
277                    TheISA::advancePC(target, inst);
278                }
279            } else {
280                predict_record.wasIndirect = true;
281                ++indirectLookups;
282                //Consult indirect predictor on indirect control
283                if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history),
284                        target, tid)) {
285                    // Indirect predictor hit
286                    ++indirectHits;
287                    DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
288                            "indirect target is %s.\n", tid, pc, target);
289                } else {
290                    ++indirectMisses;
291                    pred_taken = false;
292                    DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
293                            "target.\n", tid, pc);
294                    if (!inst->isCall() && !inst->isReturn()) {
295
296                    } else if (inst->isCall() && !inst->isUncondCtrl()) {
297                        RAS[tid].pop();
298                        predict_record.pushedRAS = false;
299                    }
300                    TheISA::advancePC(target, inst);
301                }
302                iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
303                        tid);
304            }
305        }
306    } else {
307        if (inst->isReturn()) {
308           predict_record.wasReturn = true;
309        }
310        TheISA::advancePC(target, inst);
311    }
312
313    pc = target;
314
315    predHist[tid].push_front(predict_record);
316
317    DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
318            "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
319
320    return pred_taken;
321}
322
323void
324BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
325{
326    DPRINTF(Branch, "[tid:%i]: Committing branches until "
327            "[sn:%lli].\n", tid, done_sn);
328
329    iPred.commit(done_sn, tid);
330    while (!predHist[tid].empty() &&
331           predHist[tid].back().seqNum <= done_sn) {
332        // Update the branch predictor with the correct results.
333        if (!predHist[tid].back().wasSquashed) {
334            update(tid, predHist[tid].back().pc,
335                        predHist[tid].back().predTaken,
336                        predHist[tid].back().bpHistory, false);
337        } else {
338            retireSquashed(tid, predHist[tid].back().bpHistory);
339        }
340
341        predHist[tid].pop_back();
342    }
343}
344
345void
346BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
347{
348    History &pred_hist = predHist[tid];
349
350    iPred.squash(squashed_sn, tid);
351    while (!pred_hist.empty() &&
352           pred_hist.front().seqNum > squashed_sn) {
353        if (pred_hist.front().usedRAS) {
354            DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
355                    " target: %s.\n", tid,
356                    pred_hist.front().RASIndex, pred_hist.front().RASTarget);
357
358            RAS[tid].restore(pred_hist.front().RASIndex,
359                             pred_hist.front().RASTarget);
360        } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
361             // Was a call but predicated false. Pop RAS here
362             DPRINTF(Branch, "[tid: %i] Squashing"
363                     "  Call [sn:%i] PC: %s Popping RAS\n", tid,
364                     pred_hist.front().seqNum, pred_hist.front().pc);
365             RAS[tid].pop();
366        }
367
368        // This call should delete the bpHistory.
369        squash(tid, pred_hist.front().bpHistory);
370
371        DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
372                "PC %s.\n", tid, pred_hist.front().seqNum,
373                pred_hist.front().pc);
374
375        pred_hist.pop_front();
376
377        DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
378                tid, predHist[tid].size());
379    }
380}
381
382void
383BPredUnit::squash(const InstSeqNum &squashed_sn,
384                  const TheISA::PCState &corrTarget,
385                  bool actually_taken, ThreadID tid)
386{
387    // Now that we know that a branch was mispredicted, we need to undo
388    // all the branches that have been seen up until this branch and
389    // fix up everything.
390    // NOTE: This should be call conceivably in 2 scenarios:
391    // (1) After an branch is executed, it updates its status in the ROB
392    //     The commit stage then checks the ROB update and sends a signal to
393    //     the fetch stage to squash history after the mispredict
394    // (2) In the decode stage, you can find out early if a unconditional
395    //     PC-relative, branch was predicted incorrectly. If so, a signal
396    //     to the fetch stage is sent to squash history after the mispredict
397
398    History &pred_hist = predHist[tid];
399
400    ++condIncorrect;
401    ppMisses->notify(1);
402
403    DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
404            "setting target to %s.\n", tid, squashed_sn, corrTarget);
405
406    // Squash All Branches AFTER this mispredicted branch
407    squash(squashed_sn, tid);
408
409    // If there's a squash due to a syscall, there may not be an entry
410    // corresponding to the squash.  In that case, don't bother trying to
411    // fix up the entry.
412    if (!pred_hist.empty()) {
413
414        auto hist_it = pred_hist.begin();
415        //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
416        //                       squashed_sn);
417
418        //assert(hist_it != pred_hist.end());
419        if (pred_hist.front().seqNum != squashed_sn) {
420            DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
421                    pred_hist.front().seqNum, squashed_sn);
422
423            assert(pred_hist.front().seqNum == squashed_sn);
424        }
425
426
427        if ((*hist_it).usedRAS) {
428            ++RASIncorrect;
429            DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
430                    tid, hist_it->seqNum);
431        }
432
433        // Have to get GHR here because the update deletes bpHistory
434        unsigned ghr = getGHR(tid, hist_it->bpHistory);
435
436        update(tid, (*hist_it).pc, actually_taken,
437               pred_hist.front().bpHistory, true);
438        hist_it->wasSquashed = true;
439
440        if (actually_taken) {
441            if (hist_it->wasReturn && !hist_it->usedRAS) {
442                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
443                         "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
444                         hist_it->pc);
445                 RAS[tid].pop();
446                 hist_it->usedRAS = true;
447            }
448            if (hist_it->wasIndirect) {
449                ++indirectMispredicted;
450                iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid);
451            } else {
452                DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
453                        " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
454
455                BTB.update((*hist_it).pc, corrTarget, tid);
456            }
457        } else {
458           //Actually not Taken
459           if (hist_it->usedRAS) {
460                DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
461                        "  return [sn:%i] PC: %s Restoring RAS\n", tid,
462                        hist_it->seqNum, hist_it->pc);
463                DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
464                        " to: %i, target: %s.\n", tid,
465                        hist_it->RASIndex, hist_it->RASTarget);
466                RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
467                hist_it->usedRAS = false;
468           } else if (hist_it->wasCall && hist_it->pushedRAS) {
469                 //Was a Call but predicated false. Pop RAS here
470                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
471                         "  Call [sn:%i] PC: %s Popping RAS\n", tid,
472                         hist_it->seqNum, hist_it->pc);
473                 RAS[tid].pop();
474                 hist_it->pushedRAS = false;
475           }
476        }
477    } else {
478        DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
479                "update.\n", tid, squashed_sn);
480    }
481}
482
483void
484BPredUnit::dump()
485{
486    int i = 0;
487    for (const auto& ph : predHist) {
488        if (!ph.empty()) {
489            auto pred_hist_it = ph.begin();
490
491            cprintf("predHist[%i].size(): %i\n", i++, ph.size());
492
493            while (pred_hist_it != ph.end()) {
494                cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
495                        "bpHistory:%#x\n",
496                        pred_hist_it->seqNum, pred_hist_it->pc,
497                        pred_hist_it->tid, pred_hist_it->predTaken,
498                        pred_hist_it->bpHistory);
499                pred_hist_it++;
500            }
501
502            cprintf("\n");
503        }
504    }
505}
506
507