ltage.cc revision 13455:56e25a5f9603 
1/*
2 * Copyright (c) 2014 The University of Wisconsin
3 *
4 * Copyright (c) 2006 INRIA (Institut National de Recherche en
5 * Informatique et en Automatique  / French National Research Institute
6 * for Computer Science and Applied Mathematics)
7 *
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions are
12 * met: redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer;
14 * redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution;
17 * neither the name of the copyright holders nor the names of its
18 * contributors may be used to endorse or promote products derived from
19 * this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 *
33 * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais,
34 * from André Seznec's code.
35 */
36
37/* @file
38 * Implementation of a L-TAGE branch predictor
39 */
40
41#include "cpu/pred/ltage.hh"
42
43#include "base/intmath.hh"
44#include "base/logging.hh"
45#include "base/random.hh"
46#include "base/trace.hh"
47#include "debug/Fetch.hh"
48#include "debug/LTage.hh"
49
50LTAGE::LTAGE(const LTAGEParams *params)
51  : TAGE(params),
52    logSizeLoopPred(params->logSizeLoopPred),
53    loopTableAgeBits(params->loopTableAgeBits),
54    loopTableConfidenceBits(params->loopTableConfidenceBits),
55    loopTableTagBits(params->loopTableTagBits),
56    loopTableIterBits(params->loopTableIterBits),
57    logLoopTableAssoc(params->logLoopTableAssoc),
58    confidenceThreshold((1 << loopTableConfidenceBits) - 1),
59    loopTagMask((1 << loopTableTagBits) - 1),
60    loopNumIterMask((1 << loopTableIterBits) - 1),
61    loopUseCounter(0),
62    withLoopBits(params->withLoopBits)
63{
64    // we use uint16_t type for these vales, so they cannot be more than
65    // 16 bits
66    assert(loopTableTagBits <= 16);
67    assert(loopTableIterBits <= 16);
68
69    assert(logSizeLoopPred >= logLoopTableAssoc);
70
71    ltable = new LoopEntry[ULL(1) << logSizeLoopPred];
72}
73
74int
75LTAGE::lindex(Addr pc_in) const
76{
77    // The loop table is implemented as a linear table
78    // If associativity is N (N being 1 << logLoopTableAssoc),
79    // the first N entries are for set 0, the next N entries are for set 1,
80    // and so on.
81    // Thus, this function calculates the set and then it gets left shifted
82    // by logLoopTableAssoc in order to return the index of the first of the
83    // N entries of the set
84    Addr mask = (ULL(1) << (logSizeLoopPred - logLoopTableAssoc)) - 1;
85    return (((pc_in >> instShiftAmt) & mask) << logLoopTableAssoc);
86}
87
88//loop prediction: only used if high confidence
89bool
90LTAGE::getLoop(Addr pc, LTageBranchInfo* bi) const
91{
92    bi->loopHit = -1;
93    bi->loopPredValid = false;
94    bi->loopIndex = lindex(pc);
95    unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc;
96    bi->loopTag = ((pc) >> pcShift) & loopTagMask;
97
98    for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
99        if (ltable[bi->loopIndex + i].tag == bi->loopTag) {
100            bi->loopHit = i;
101            bi->loopPredValid =
102                ltable[bi->loopIndex + i].confidence == confidenceThreshold;
103            bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec;
104            if (ltable[bi->loopIndex + i].currentIterSpec + 1 ==
105                ltable[bi->loopIndex + i].numIter) {
106                return !(ltable[bi->loopIndex + i].dir);
107            }else {
108                return (ltable[bi->loopIndex + i].dir);
109            }
110        }
111    }
112    return false;
113}
114
115void
116LTAGE::specLoopUpdate(Addr pc, bool taken, LTageBranchInfo* bi)
117{
118    if (bi->loopHit>=0) {
119        int index = lindex(pc);
120        if (taken != ltable[index].dir) {
121            ltable[index].currentIterSpec = 0;
122        } else {
123            ltable[index].currentIterSpec =
124                (ltable[index].currentIterSpec + 1) & loopNumIterMask;
125        }
126    }
127}
128
129void
130LTAGE::loopUpdate(Addr pc, bool taken, LTageBranchInfo* bi)
131{
132    int idx = bi->loopIndex + bi->loopHit;
133    if (bi->loopHit >= 0) {
134        //already a hit
135        if (bi->loopPredValid) {
136            if (taken != bi->loopPred) {
137                // free the entry
138                ltable[idx].numIter = 0;
139                ltable[idx].age = 0;
140                ltable[idx].confidence = 0;
141                ltable[idx].currentIter = 0;
142                return;
143            } else if (bi->loopPred != bi->tagePred) {
144                DPRINTF(LTage, "Loop Prediction success:%lx\n",pc);
145                unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
146            }
147        }
148
149        ltable[idx].currentIter =
150            (ltable[idx].currentIter + 1) & loopNumIterMask;
151        if (ltable[idx].currentIter > ltable[idx].numIter) {
152            ltable[idx].confidence = 0;
153            if (ltable[idx].numIter != 0) {
154                // free the entry
155                ltable[idx].numIter = 0;
156                ltable[idx].age = 0;
157                ltable[idx].confidence = 0;
158            }
159        }
160
161        if (taken != ltable[idx].dir) {
162            if (ltable[idx].currentIter == ltable[idx].numIter) {
163                DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc);
164
165                unsignedCtrUpdate(ltable[idx].confidence, true,
166                                  loopTableConfidenceBits);
167                //just do not predict when the loop count is 1 or 2
168                if (ltable[idx].numIter < 3) {
169                    // free the entry
170                    ltable[idx].dir = taken;
171                    ltable[idx].numIter = 0;
172                    ltable[idx].age = 0;
173                    ltable[idx].confidence = 0;
174                }
175            } else {
176                DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc);
177                if (ltable[idx].numIter == 0) {
178                    // first complete nest;
179                    ltable[idx].confidence = 0;
180                    ltable[idx].numIter = ltable[idx].currentIter;
181                } else {
182                    //not the same number of iterations as last time: free the
183                    //entry
184                    ltable[idx].numIter = 0;
185                    ltable[idx].age = 0;
186                    ltable[idx].confidence = 0;
187                }
188            }
189            ltable[idx].currentIter = 0;
190        }
191
192    } else if (taken) {
193        //try to allocate an entry on taken branch
194        int nrand = random_mt.random<int>();
195        for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
196            int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1);
197            idx = bi->loopIndex + loop_hit;
198            if (ltable[idx].age == 0) {
199                DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n",
200                        pc);
201                ltable[idx].dir = !taken;
202                ltable[idx].tag = bi->loopTag;
203                ltable[idx].numIter = 0;
204                ltable[idx].age = (1 << loopTableAgeBits) - 1;
205                ltable[idx].confidence = 0;
206                ltable[idx].currentIter = 1;
207                break;
208
209            }
210            else
211                ltable[idx].age--;
212        }
213    }
214
215}
216
217//prediction
218bool
219LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
220{
221    LTageBranchInfo *bi = new LTageBranchInfo(nHistoryTables+1);
222    b = (void*)(bi);
223
224    bool pred_taken = tagePredict(tid, branch_pc, cond_branch, bi);
225
226    if (cond_branch) {
227        bi->loopPred = getLoop(branch_pc, bi);	// loop prediction
228
229        if ((loopUseCounter >= 0) && bi->loopPredValid) {
230            pred_taken = bi->loopPred;
231            bi->provider = LOOP;
232        }
233        DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, "
234                "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n",
235                branch_pc, pred_taken, bi->loopPred, bi->loopPredValid,
236                loopUseCounter, bi->tagePred, bi->altTaken);
237    }
238
239    specLoopUpdate(branch_pc, pred_taken, bi);
240    return pred_taken;
241}
242
243void
244LTAGE::condBranchUpdate(Addr branch_pc, bool taken,
245                        TageBranchInfo* tage_bi, int nrand)
246{
247    LTageBranchInfo* bi = static_cast<LTageBranchInfo*>(tage_bi);
248
249    // first update the loop predictor
250    loopUpdate(branch_pc, taken, bi);
251
252    if (bi->loopPredValid) {
253        if (bi->tagePred != bi->loopPred) {
254            ctrUpdate(loopUseCounter,
255                      (bi->loopPred == taken),
256                      withLoopBits);
257        }
258    }
259
260    TAGE::condBranchUpdate(branch_pc, taken, bi, nrand);
261}
262
263void
264LTAGE::squash(ThreadID tid, bool taken, void *bp_history)
265{
266    TAGE::squash(tid, taken, bp_history);
267
268    LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history);
269
270    if (bi->condBranch) {
271        if (bi->loopHit >= 0) {
272            int idx = bi->loopIndex + bi->loopHit;
273            ltable[idx].currentIterSpec = bi->currentIter;
274        }
275    }
276}
277
278void
279LTAGE::squash(ThreadID tid, void *bp_history)
280{
281    LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history);
282    if (bi->condBranch) {
283        if (bi->loopHit >= 0) {
284            int idx = bi->loopIndex + bi->loopHit;
285            ltable[idx].currentIterSpec = bi->currentIter;
286        }
287    }
288
289    TAGE::squash(tid, bp_history);
290}
291
292
293void
294LTAGE::updateStats(bool taken, TageBranchInfo* bi)
295{
296    TAGE::updateStats(taken, bi);
297
298    LTageBranchInfo * ltage_bi = static_cast<LTageBranchInfo *>(bi);
299
300    if (ltage_bi->provider == LOOP) {
301        if (taken == ltage_bi->loopPred) {
302            loopPredictorCorrect++;
303        } else {
304            loopPredictorWrong++;
305        }
306    }
307}
308
309
310
311void
312LTAGE::regStats()
313{
314    TAGE::regStats();
315
316    loopPredictorCorrect
317        .name(name() + ".loopPredictorCorrect")
318        .desc("Number of times the loop predictor is the provider and "
319              "the prediction is correct");
320
321    loopPredictorWrong
322        .name(name() + ".loopPredictorWrong")
323        .desc("Number of times the loop predictor is the provier and "
324              "the prediction is wrong");
325}
326
327
328
329LTAGE*
330LTAGEParams::create()
331{
332    return new LTAGE(this);
333}
334