1/*
2 * Copyright (c) 2014 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: Anthony Gutierrez
29 */
30
31/* @file
32 * Implementation of a bi-mode branch predictor
33 */
34
35#include "cpu/pred/bi_mode.hh"
36
37#include "base/bitfield.hh"
38#include "base/intmath.hh"
39
40BiModeBP::BiModeBP(const BiModeBPParams *params)
41    : BPredUnit(params),
42      globalHistoryReg(params->numThreads, 0),
43      globalHistoryBits(ceilLog2(params->globalPredictorSize)),
44      choicePredictorSize(params->choicePredictorSize),
45      choiceCtrBits(params->choiceCtrBits),
46      globalPredictorSize(params->globalPredictorSize),
47      globalCtrBits(params->globalCtrBits),
48      choiceCounters(choicePredictorSize, SatCounter(choiceCtrBits)),
49      takenCounters(globalPredictorSize, SatCounter(globalCtrBits)),
50      notTakenCounters(globalPredictorSize, SatCounter(globalCtrBits))
51{
52    if (!isPowerOf2(choicePredictorSize))
53        fatal("Invalid choice predictor size.\n");
54    if (!isPowerOf2(globalPredictorSize))
55        fatal("Invalid global history predictor size.\n");
56
57    historyRegisterMask = mask(globalHistoryBits);
58    choiceHistoryMask = choicePredictorSize - 1;
59    globalHistoryMask = globalPredictorSize - 1;
60
61    choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
62    takenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
63    notTakenThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
64}
65
66/*
67 * For an unconditional branch we set its history such that
68 * everything is set to taken. I.e., its choice predictor
69 * chooses the taken array and the taken array predicts taken.
70 */
71void
72BiModeBP::uncondBranch(ThreadID tid, Addr pc, void * &bpHistory)
73{
74    BPHistory *history = new BPHistory;
75    history->globalHistoryReg = globalHistoryReg[tid];
76    history->takenUsed = true;
77    history->takenPred = true;
78    history->notTakenPred = true;
79    history->finalPred = true;
80    bpHistory = static_cast<void*>(history);
81    updateGlobalHistReg(tid, true);
82}
83
84void
85BiModeBP::squash(ThreadID tid, void *bpHistory)
86{
87    BPHistory *history = static_cast<BPHistory*>(bpHistory);
88    globalHistoryReg[tid] = history->globalHistoryReg;
89
90    delete history;
91}
92
93/*
94 * Here we lookup the actual branch prediction. We use the PC to
95 * identify the bias of a particular branch, which is based on the
96 * prediction in the choice array. A hash of the global history
97 * register and a branch's PC is used to index into both the taken
98 * and not-taken predictors, which both present a prediction. The
99 * choice array's prediction is used to select between the two
100 * direction predictors for the final branch prediction.
101 */
102bool
103BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory)
104{
105    unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
106                                & choiceHistoryMask);
107    unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
108                                ^ globalHistoryReg[tid])
109                                & globalHistoryMask);
110
111    assert(choiceHistoryIdx < choicePredictorSize);
112    assert(globalHistoryIdx < globalPredictorSize);
113
114    bool choicePrediction = choiceCounters[choiceHistoryIdx]
115                            > choiceThreshold;
116    bool takenGHBPrediction = takenCounters[globalHistoryIdx]
117                              > takenThreshold;
118    bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx]
119                                 > notTakenThreshold;
120    bool finalPrediction;
121
122    BPHistory *history = new BPHistory;
123    history->globalHistoryReg = globalHistoryReg[tid];
124    history->takenUsed = choicePrediction;
125    history->takenPred = takenGHBPrediction;
126    history->notTakenPred = notTakenGHBPrediction;
127
128    if (choicePrediction) {
129        finalPrediction = takenGHBPrediction;
130    } else {
131        finalPrediction = notTakenGHBPrediction;
132    }
133
134    history->finalPred = finalPrediction;
135    bpHistory = static_cast<void*>(history);
136    updateGlobalHistReg(tid, finalPrediction);
137
138    return finalPrediction;
139}
140
141void
142BiModeBP::btbUpdate(ThreadID tid, Addr branchAddr, void * &bpHistory)
143{
144    globalHistoryReg[tid] &= (historyRegisterMask & ~ULL(1));
145}
146
147/* Only the selected direction predictor will be updated with the final
148 * outcome; the status of the unselected one will not be altered. The choice
149 * predictor is always updated with the branch outcome, except when the
150 * choice is opposite to the branch outcome but the selected counter of
151 * the direction predictors makes a correct final prediction.
152 */
153void
154BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory,
155                 bool squashed, const StaticInstPtr & inst, Addr corrTarget)
156{
157    assert(bpHistory);
158
159    BPHistory *history = static_cast<BPHistory*>(bpHistory);
160
161    // We do not update the counters speculatively on a squash.
162    // We just restore the global history register.
163    if (squashed) {
164        globalHistoryReg[tid] = (history->globalHistoryReg << 1) | taken;
165        return;
166    }
167
168    unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
169                                & choiceHistoryMask);
170    unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
171                                ^ history->globalHistoryReg)
172                                & globalHistoryMask);
173
174    assert(choiceHistoryIdx < choicePredictorSize);
175    assert(globalHistoryIdx < globalPredictorSize);
176
177    if (history->takenUsed) {
178        // if the taken array's prediction was used, update it
179        if (taken) {
180            takenCounters[globalHistoryIdx]++;
181        } else {
182            takenCounters[globalHistoryIdx]--;
183        }
184    } else {
185        // if the not-taken array's prediction was used, update it
186        if (taken) {
187            notTakenCounters[globalHistoryIdx]++;
188        } else {
189            notTakenCounters[globalHistoryIdx]--;
190        }
191    }
192
193    if (history->finalPred == taken) {
194       /* If the final prediction matches the actual branch's
195        * outcome and the choice predictor matches the final
196        * outcome, we update the choice predictor, otherwise it
197        * is not updated. While the designers of the bi-mode
198        * predictor don't explicity say why this is done, one
199        * can infer that it is to preserve the choice predictor's
200        * bias with respect to the branch being predicted; afterall,
201        * the whole point of the bi-mode predictor is to identify the
202        * atypical case when a branch deviates from its bias.
203        */
204        if (history->finalPred == history->takenUsed) {
205            if (taken) {
206                choiceCounters[choiceHistoryIdx]++;
207            } else {
208                choiceCounters[choiceHistoryIdx]--;
209            }
210        }
211    } else {
212        // always update the choice predictor on an incorrect prediction
213        if (taken) {
214            choiceCounters[choiceHistoryIdx]++;
215        } else {
216            choiceCounters[choiceHistoryIdx]--;
217        }
218    }
219
220    delete history;
221}
222
223void
224BiModeBP::updateGlobalHistReg(ThreadID tid, bool taken)
225{
226    globalHistoryReg[tid] = taken ? (globalHistoryReg[tid] << 1) | 1 :
227                               (globalHistoryReg[tid] << 1);
228    globalHistoryReg[tid] &= historyRegisterMask;
229}
230
231BiModeBP*
232BiModeBPParams::create()
233{
234    return new BiModeBP(this);
235}
236