bpred_unit.cc revision 11321
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      RAS(numThreads),
64      instShiftAmt(params->instShiftAmt)
65{
66    for (auto& r : RAS)
67        r.init(params->RASSize);
68}
69
70void
71BPredUnit::regStats()
72{
73    lookups
74        .name(name() + ".lookups")
75        .desc("Number of BP lookups")
76        ;
77
78    condPredicted
79        .name(name() + ".condPredicted")
80        .desc("Number of conditional branches predicted")
81        ;
82
83    condIncorrect
84        .name(name() + ".condIncorrect")
85        .desc("Number of conditional branches incorrect")
86        ;
87
88    BTBLookups
89        .name(name() + ".BTBLookups")
90        .desc("Number of BTB lookups")
91        ;
92
93    BTBHits
94        .name(name() + ".BTBHits")
95        .desc("Number of BTB hits")
96        ;
97
98    BTBCorrect
99        .name(name() + ".BTBCorrect")
100        .desc("Number of correct BTB predictions (this stat may not "
101              "work properly.")
102        ;
103
104    BTBHitPct
105        .name(name() + ".BTBHitPct")
106        .desc("BTB Hit Percentage")
107        .precision(6);
108    BTBHitPct = (BTBHits / BTBLookups) * 100;
109
110    usedRAS
111        .name(name() + ".usedRAS")
112        .desc("Number of times the RAS was used to get a target.")
113        ;
114
115    RASIncorrect
116        .name(name() + ".RASInCorrect")
117        .desc("Number of incorrect RAS predictions.")
118        ;
119}
120
121ProbePoints::PMUUPtr
122BPredUnit::pmuProbePoint(const char *name)
123{
124    ProbePoints::PMUUPtr ptr;
125    ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
126
127    return ptr;
128}
129
130void
131BPredUnit::regProbePoints()
132{
133    ppBranches = pmuProbePoint("Branches");
134    ppMisses = pmuProbePoint("Misses");
135}
136
137void
138BPredUnit::drainSanityCheck() const
139{
140    // We shouldn't have any outstanding requests when we resume from
141    // a drained system.
142    for (const auto& ph M5_VAR_USED : predHist)
143        assert(ph.empty());
144}
145
146bool
147BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
148                   TheISA::PCState &pc, ThreadID tid)
149{
150    // See if branch predictor predicts taken.
151    // If so, get its target addr either from the BTB or the RAS.
152    // Save off record of branch stuff so the RAS can be fixed
153    // up once it's done.
154
155    bool pred_taken = false;
156    TheISA::PCState target = pc;
157
158    ++lookups;
159    ppBranches->notify(1);
160
161    void *bp_history = NULL;
162
163    if (inst->isUncondCtrl()) {
164        DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
165        pred_taken = true;
166        // Tell the BP there was an unconditional branch.
167        uncondBranch(pc.instAddr(), bp_history);
168    } else {
169        ++condPredicted;
170        pred_taken = lookup(pc.instAddr(), bp_history);
171
172        DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
173                " predicted %i for PC %s\n", tid, seqNum,  pred_taken, pc);
174    }
175
176    DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
177            "for PC %s\n", tid, seqNum, pc);
178
179    PredictorHistory predict_record(seqNum, pc.instAddr(),
180                                    pred_taken, bp_history, tid);
181
182    // Now lookup in the BTB or RAS.
183    if (pred_taken) {
184        if (inst->isReturn()) {
185            ++usedRAS;
186            predict_record.wasReturn = true;
187            // If it's a function return call, then look up the address
188            // in the RAS.
189            TheISA::PCState rasTop = RAS[tid].top();
190            target = TheISA::buildRetPC(pc, rasTop);
191
192            // Record the top entry of the RAS, and its index.
193            predict_record.usedRAS = true;
194            predict_record.RASIndex = RAS[tid].topIdx();
195            predict_record.RASTarget = rasTop;
196
197            RAS[tid].pop();
198
199            DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
200                    "RAS predicted target: %s, RAS index: %i.\n",
201                    tid, pc, target, predict_record.RASIndex);
202        } else {
203            ++BTBLookups;
204
205            if (inst->isCall()) {
206                RAS[tid].push(pc);
207                predict_record.pushedRAS = true;
208
209                // Record that it was a call so that the top RAS entry can
210                // be popped off if the speculation is incorrect.
211                predict_record.wasCall = true;
212
213                DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
214                        "call, adding %s to the RAS index: %i.\n",
215                        tid, pc, pc, RAS[tid].topIdx());
216            }
217
218            if (BTB.valid(pc.instAddr(), tid)) {
219                ++BTBHits;
220
221                // If it's not a return, use the BTB to get the target addr.
222                target = BTB.lookup(pc.instAddr(), tid);
223
224                DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
225                        " target is %s.\n", tid, pc, target);
226
227            } else {
228                DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
229                        "valid entry.\n",tid);
230                pred_taken = false;
231                // The Direction of the branch predictor is altered because the
232                // BTB did not have an entry
233                // The predictor needs to be updated accordingly
234                if (!inst->isCall() && !inst->isReturn()) {
235                      btbUpdate(pc.instAddr(), bp_history);
236                      DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
237                              " called for %s\n", tid, seqNum, pc);
238                } else if (inst->isCall() && !inst->isUncondCtrl()) {
239                      RAS[tid].pop();
240                      predict_record.pushedRAS = false;
241                }
242                TheISA::advancePC(target, inst);
243            }
244        }
245    } else {
246        if (inst->isReturn()) {
247           predict_record.wasReturn = true;
248        }
249        TheISA::advancePC(target, inst);
250    }
251
252    pc = target;
253
254    predHist[tid].push_front(predict_record);
255
256    DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
257            "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
258
259    return pred_taken;
260}
261
262bool
263BPredUnit::predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum,
264                          int asid, TheISA::PCState &instPC,
265                          TheISA::PCState &predPC, ThreadID tid)
266{
267    // See if branch predictor predicts taken.
268    // If so, get its target addr either from the BTB or the RAS.
269    // Save off record of branch stuff so the RAS can be fixed
270    // up once it's done.
271
272    using TheISA::MachInst;
273
274    bool pred_taken = false;
275    TheISA::PCState target;
276
277    ++lookups;
278    ppBranches->notify(1);
279
280    DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch "
281            "prediction\n", tid, seqNum,
282            inst->disassemble(instPC.instAddr()), instPC);
283
284    void *bp_history = NULL;
285
286    if (inst->isUncondCtrl()) {
287        DPRINTF(Branch, "[tid:%i] Unconditional control.\n", tid);
288        pred_taken = true;
289        // Tell the BP there was an unconditional branch.
290        uncondBranch(instPC.instAddr(), bp_history);
291
292        if (inst->isReturn() && RAS[tid].empty()) {
293            DPRINTF(Branch, "[tid:%i] RAS is empty, predicting "
294                    "false.\n", tid);
295            pred_taken = false;
296        }
297    } else {
298        ++condPredicted;
299
300        pred_taken = lookup(predPC.instAddr(), bp_history);
301    }
302
303    PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken,
304                                    bp_history, tid);
305
306    // Now lookup in the BTB or RAS.
307    if (pred_taken) {
308        if (inst->isReturn()) {
309            ++usedRAS;
310
311            // If it's a function return call, then look up the address
312            // in the RAS.
313            TheISA::PCState rasTop = RAS[tid].top();
314            target = TheISA::buildRetPC(instPC, rasTop);
315
316            // Record the top entry of the RAS, and its index.
317            predict_record.usedRAS = true;
318            predict_record.RASIndex = RAS[tid].topIdx();
319            predict_record.RASTarget = rasTop;
320
321            assert(predict_record.RASIndex < 16);
322
323            RAS[tid].pop();
324
325            DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
326                    "RAS predicted target: %s, RAS index: %i.\n",
327                    tid, instPC, target,
328                    predict_record.RASIndex);
329        } else {
330            ++BTBLookups;
331
332            if (inst->isCall()) {
333
334                RAS[tid].push(instPC);
335                predict_record.pushedRAS = true;
336
337                // Record that it was a call so that the top RAS entry can
338                // be popped off if the speculation is incorrect.
339                predict_record.wasCall = true;
340
341                DPRINTF(Branch, "[tid:%i]: Instruction %s was a call"
342                        ", adding %s to the RAS index: %i.\n",
343                        tid, instPC, predPC,
344                        RAS[tid].topIdx());
345            }
346
347            if (inst->isCall() &&
348                inst->isUncondCtrl() &&
349                inst->isDirectCtrl()) {
350                target = inst->branchTarget(instPC);
351            } else if (BTB.valid(predPC.instAddr(), asid)) {
352                ++BTBHits;
353
354                // If it's not a return, use the BTB to get the target addr.
355                target = BTB.lookup(predPC.instAddr(), asid);
356
357                DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s "
358                        "predicted target is %s.\n",
359                        tid, asid, instPC, target);
360            } else {
361                DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
362                        "valid entry, predicting false.\n",tid);
363                pred_taken = false;
364            }
365        }
366    }
367
368    if (pred_taken) {
369        // Set the PC and the instruction's predicted target.
370        predPC = target;
371    }
372    DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n",
373            tid, seqNum, predPC);
374
375    predHist[tid].push_front(predict_record);
376
377    DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist "
378            "...predHist.size(): %i\n",
379            tid, seqNum, predHist[tid].size());
380
381    return pred_taken;
382}
383
384void
385BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
386{
387    DPRINTF(Branch, "[tid:%i]: Committing branches until "
388            "[sn:%lli].\n", tid, done_sn);
389
390    while (!predHist[tid].empty() &&
391           predHist[tid].back().seqNum <= done_sn) {
392        // Update the branch predictor with the correct results.
393        if (!predHist[tid].back().wasSquashed) {
394            update(predHist[tid].back().pc, predHist[tid].back().predTaken,
395                predHist[tid].back().bpHistory, false);
396        } else {
397            retireSquashed(predHist[tid].back().bpHistory);
398        }
399
400        predHist[tid].pop_back();
401    }
402}
403
404void
405BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
406{
407    History &pred_hist = predHist[tid];
408
409    while (!pred_hist.empty() &&
410           pred_hist.front().seqNum > squashed_sn) {
411        if (pred_hist.front().usedRAS) {
412            DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
413                    " target: %s.\n", tid,
414                    pred_hist.front().RASIndex, pred_hist.front().RASTarget);
415
416            RAS[tid].restore(pred_hist.front().RASIndex,
417                             pred_hist.front().RASTarget);
418        } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
419             // Was a call but predicated false. Pop RAS here
420             DPRINTF(Branch, "[tid: %i] Squashing"
421                     "  Call [sn:%i] PC: %s Popping RAS\n", tid,
422                     pred_hist.front().seqNum, pred_hist.front().pc);
423             RAS[tid].pop();
424        }
425
426        // This call should delete the bpHistory.
427        squash(pred_hist.front().bpHistory);
428
429        DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
430                "PC %s.\n", tid, pred_hist.front().seqNum,
431                pred_hist.front().pc);
432
433        pred_hist.pop_front();
434
435        DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
436                tid, predHist[tid].size());
437    }
438}
439
440void
441BPredUnit::squash(const InstSeqNum &squashed_sn,
442                  const TheISA::PCState &corrTarget,
443                  bool actually_taken, ThreadID tid)
444{
445    // Now that we know that a branch was mispredicted, we need to undo
446    // all the branches that have been seen up until this branch and
447    // fix up everything.
448    // NOTE: This should be call conceivably in 2 scenarios:
449    // (1) After an branch is executed, it updates its status in the ROB
450    //     The commit stage then checks the ROB update and sends a signal to
451    //     the fetch stage to squash history after the mispredict
452    // (2) In the decode stage, you can find out early if a unconditional
453    //     PC-relative, branch was predicted incorrectly. If so, a signal
454    //     to the fetch stage is sent to squash history after the mispredict
455
456    History &pred_hist = predHist[tid];
457
458    ++condIncorrect;
459    ppMisses->notify(1);
460
461    DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
462            "setting target to %s.\n", tid, squashed_sn, corrTarget);
463
464    // Squash All Branches AFTER this mispredicted branch
465    squash(squashed_sn, tid);
466
467    // If there's a squash due to a syscall, there may not be an entry
468    // corresponding to the squash.  In that case, don't bother trying to
469    // fix up the entry.
470    if (!pred_hist.empty()) {
471
472        auto hist_it = pred_hist.begin();
473        //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
474        //                       squashed_sn);
475
476        //assert(hist_it != pred_hist.end());
477        if (pred_hist.front().seqNum != squashed_sn) {
478            DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
479                    pred_hist.front().seqNum, squashed_sn);
480
481            assert(pred_hist.front().seqNum == squashed_sn);
482        }
483
484
485        if ((*hist_it).usedRAS) {
486            ++RASIncorrect;
487        }
488
489        update((*hist_it).pc, actually_taken,
490               pred_hist.front().bpHistory, true);
491        hist_it->wasSquashed = true;
492
493        if (actually_taken) {
494            if (hist_it->wasReturn && !hist_it->usedRAS) {
495                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
496                         "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
497                         hist_it->pc);
498                 RAS[tid].pop();
499                 hist_it->usedRAS = true;
500            }
501
502            DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
503                    " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
504
505            BTB.update((*hist_it).pc, corrTarget, tid);
506
507        } else {
508           //Actually not Taken
509           if (hist_it->usedRAS) {
510                DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
511                        "  return [sn:%i] PC: %s Restoring RAS\n", tid,
512                        hist_it->seqNum, hist_it->pc);
513                DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
514                        " to: %i, target: %s.\n", tid,
515                        hist_it->RASIndex, hist_it->RASTarget);
516                RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
517                hist_it->usedRAS = false;
518           } else if (hist_it->wasCall && hist_it->pushedRAS) {
519                 //Was a Call but predicated false. Pop RAS here
520                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
521                         "  Call [sn:%i] PC: %s Popping RAS\n", tid,
522                         hist_it->seqNum, hist_it->pc);
523                 RAS[tid].pop();
524                 hist_it->pushedRAS = false;
525           }
526        }
527    } else {
528        DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
529                "update.\n", tid, squashed_sn);
530    }
531}
532
533void
534BPredUnit::dump()
535{
536    int i = 0;
537    for (const auto& ph : predHist) {
538        if (!ph.empty()) {
539            auto pred_hist_it = ph.begin();
540
541            cprintf("predHist[%i].size(): %i\n", i++, ph.size());
542
543            while (pred_hist_it != ph.end()) {
544                cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
545                        "bpHistory:%#x\n",
546                        pred_hist_it->seqNum, pred_hist_it->pc,
547                        pred_hist_it->tid, pred_hist_it->predTaken,
548                        pred_hist_it->bpHistory);
549                pred_hist_it++;
550            }
551
552            cprintf("\n");
553        }
554    }
555}
556
557