ltage.cc revision 13626:d6a6358aa6db 
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    loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1),
62    loopUseCounter(0),
63    withLoopBits(params->withLoopBits),
64    useDirectionBit(params->useDirectionBit),
65    useSpeculation(params->useSpeculation),
66    useHashing(params->useHashing)
67{
68    // we use uint16_t type for these vales, so they cannot be more than
69    // 16 bits
70    assert(loopTableTagBits <= 16);
71    assert(loopTableIterBits <= 16);
72
73    assert(logSizeLoopPred >= logLoopTableAssoc);
74
75    ltable = new LoopEntry[ULL(1) << logSizeLoopPred];
76}
77
78int
79LTAGE::lindex(Addr pc_in) const
80{
81    // The loop table is implemented as a linear table
82    // If associativity is N (N being 1 << logLoopTableAssoc),
83    // the first N entries are for set 0, the next N entries are for set 1,
84    // and so on.
85    // Thus, this function calculates the set and then it gets left shifted
86    // by logLoopTableAssoc in order to return the index of the first of the
87    // N entries of the set
88    Addr mask = (ULL(1) << (logSizeLoopPred - logLoopTableAssoc)) - 1;
89    Addr pc = pc_in >> instShiftAmt;
90    if (useHashing) {
91        // copied from TAGE-SC-L
92        // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
93        pc ^= (pc_in >> (instShiftAmt + logLoopTableAssoc));
94    }
95    return ((pc & mask) << logLoopTableAssoc);
96}
97
98int
99LTAGE::finallindex(int index, int lowPcBits, int way) const
100{
101    // copied from TAGE-SC-L
102    // (http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz)
103    return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) :
104                         (index))
105           + way;
106}
107
108//loop prediction: only used if high confidence
109bool
110LTAGE::getLoop(Addr pc, LTageBranchInfo* bi, bool speculative) const
111{
112    bi->loopHit = -1;
113    bi->loopPredValid = false;
114    bi->loopIndex = lindex(pc);
115    unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc;
116    bi->loopTag = ((pc) >> pcShift) & loopTagMask;
117
118    if (useHashing) {
119        bi->loopTag ^= ((pc >> (pcShift + logSizeLoopPred)) & loopTagMask);
120        bi->loopLowPcBits = (pc >> pcShift) & loopSetMask;
121    }
122
123    for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
124        int idx = finallindex(bi->loopIndex, bi->loopLowPcBits, i);
125        if (ltable[idx].tag == bi->loopTag) {
126            bi->loopHit = i;
127            bi->loopPredValid =
128                ltable[idx].confidence == confidenceThreshold;
129
130            uint16_t iter = speculative ? ltable[idx].currentIterSpec
131                                        : ltable[idx].currentIter;
132
133            if ((iter + 1) == ltable[idx].numIter) {
134                return useDirectionBit ? !(ltable[idx].dir) : false;
135            } else {
136                return useDirectionBit ? (ltable[idx].dir) : true;
137            }
138        }
139    }
140    return false;
141}
142
143void
144LTAGE::specLoopUpdate(bool taken, LTageBranchInfo* bi)
145{
146    if (bi->loopHit>=0) {
147        int index = finallindex(bi->loopIndex, bi->loopLowPcBits, bi->loopHit);
148        if (taken != ltable[index].dir) {
149            ltable[index].currentIterSpec = 0;
150        } else {
151            ltable[index].currentIterSpec =
152                (ltable[index].currentIterSpec + 1) & loopNumIterMask;
153        }
154    }
155}
156
157void
158LTAGE::loopUpdate(Addr pc, bool taken, LTageBranchInfo* bi)
159{
160    int idx = finallindex(bi->loopIndex, bi->loopLowPcBits, bi->loopHit);
161    if (bi->loopHit >= 0) {
162        //already a hit
163        if (bi->loopPredValid) {
164            if (taken != bi->loopPred) {
165                // free the entry
166                ltable[idx].numIter = 0;
167                ltable[idx].age = 0;
168                ltable[idx].confidence = 0;
169                ltable[idx].currentIter = 0;
170                return;
171            } else if (bi->loopPred != bi->tageBranchInfo->tagePred) {
172                DPRINTF(LTage, "Loop Prediction success:%lx\n",pc);
173                TAGEBase::unsignedCtrUpdate(ltable[idx].age, true,
174                                            loopTableAgeBits);
175            }
176        }
177
178        ltable[idx].currentIter =
179            (ltable[idx].currentIter + 1) & loopNumIterMask;
180        if (ltable[idx].currentIter > ltable[idx].numIter) {
181            ltable[idx].confidence = 0;
182            if (ltable[idx].numIter != 0) {
183                // free the entry
184                ltable[idx].numIter = 0;
185                ltable[idx].age = 0;
186                ltable[idx].confidence = 0;
187            }
188        }
189
190        if (taken != (useDirectionBit ? ltable[idx].dir : true)) {
191            if (ltable[idx].currentIter == ltable[idx].numIter) {
192                DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc);
193
194                TAGEBase::unsignedCtrUpdate(ltable[idx].confidence, true,
195                                  loopTableConfidenceBits);
196                //just do not predict when the loop count is 1 or 2
197                if (ltable[idx].numIter < 3) {
198                    // free the entry
199                    ltable[idx].dir = taken; // ignored if no useDirectionBit
200                    ltable[idx].numIter = 0;
201                    ltable[idx].age = 0;
202                    ltable[idx].confidence = 0;
203                }
204            } else {
205                DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc);
206                if (ltable[idx].numIter == 0) {
207                    // first complete nest;
208                    ltable[idx].confidence = 0;
209                    ltable[idx].numIter = ltable[idx].currentIter;
210                } else {
211                    //not the same number of iterations as last time: free the
212                    //entry
213                    ltable[idx].numIter = 0;
214                    ltable[idx].age = 0;
215                    ltable[idx].confidence = 0;
216                }
217            }
218            ltable[idx].currentIter = 0;
219        }
220
221    } else if (useDirectionBit ?
222                ((bi->loopPredValid ?
223                    bi->loopPred : bi->tageBranchInfo->tagePred) != taken) :
224                taken) {
225        //try to allocate an entry on taken branch
226        int nrand = TAGEBase::getRandom();
227        for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
228            int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1);
229            idx = bi->loopIndex + loop_hit;
230            if (ltable[idx].age == 0) {
231                DPRINTF(LTage, "Allocating loop pred entry for branch %lx\n",
232                        pc);
233                ltable[idx].dir = !taken; // ignored if no useDirectionBit
234                ltable[idx].tag = bi->loopTag;
235                ltable[idx].numIter = 0;
236                ltable[idx].age = (1 << loopTableAgeBits) - 1;
237                ltable[idx].confidence = 0;
238                ltable[idx].currentIter = 1;
239                break;
240
241            }
242            else
243                ltable[idx].age--;
244        }
245    }
246
247}
248
249//prediction
250bool
251LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b)
252{
253    LTageBranchInfo *bi = new LTageBranchInfo(*tage);
254    b = (void*)(bi);
255
256    bool pred_taken = tage->tagePredict(tid, branch_pc, cond_branch,
257                                        bi->tageBranchInfo);
258
259    if (cond_branch) {
260        // loop prediction
261        bi->loopPred = getLoop(branch_pc, bi, useSpeculation);
262
263        if ((loopUseCounter >= 0) && bi->loopPredValid) {
264            pred_taken = bi->loopPred;
265            bi->tageBranchInfo->provider = LOOP;
266        }
267        DPRINTF(LTage, "Predict for %lx: taken?:%d, loopTaken?:%d, "
268                "loopValid?:%d, loopUseCounter:%d, tagePred:%d, altPred:%d\n",
269                branch_pc, pred_taken, bi->loopPred, bi->loopPredValid,
270                loopUseCounter, bi->tageBranchInfo->tagePred,
271                bi->tageBranchInfo->altTaken);
272
273        if (useSpeculation) {
274            specLoopUpdate(pred_taken, bi);
275        }
276    }
277
278    return pred_taken;
279}
280
281void
282LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history,
283              bool squashed, const StaticInstPtr & inst, Addr corrTarget)
284{
285    assert(bp_history);
286
287    LTageBranchInfo* bi = static_cast<LTageBranchInfo*>(bp_history);
288
289    if (squashed) {
290        if (tage->isSpeculativeUpdateEnabled()) {
291            // This restores the global history, then update it
292            // and recomputes the folded histories.
293            tage->squash(tid, taken, bi->tageBranchInfo, corrTarget);
294            squashLoop(bi);
295        }
296        return;
297    }
298
299    int nrand = TAGEBase::getRandom() & 3;
300    if (bi->tageBranchInfo->condBranch) {
301        DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n",
302                branch_pc, taken);
303        tage->updateStats(taken, bi->tageBranchInfo);
304        // update stats
305        if (bi->tageBranchInfo->provider == LOOP) {
306            if (taken == bi->loopPred) {
307                loopPredictorCorrect++;
308            } else {
309                loopPredictorWrong++;
310            }
311        }
312        // cond Branch Update
313        if (useSpeculation) {
314            // recalculate loop prediction without speculation
315            // It is ok to overwrite the loop prediction fields in bi
316            // as the stats have already been updated with the previous
317            // values
318            bi->loopPred = getLoop(branch_pc, bi, false);
319        }
320        if (bi->loopPredValid) {
321            if (bi->tageBranchInfo->tagePred != bi->loopPred) {
322                TAGEBase::ctrUpdate(loopUseCounter,
323                        (bi->loopPred == taken),
324                        withLoopBits);
325            }
326        }
327
328        loopUpdate(branch_pc, taken, bi);
329
330        tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo,
331                               nrand, corrTarget);
332    }
333
334    tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false,
335                          inst, corrTarget);
336
337    delete bi;
338}
339
340void
341LTAGE::squashLoop(LTageBranchInfo* bi)
342{
343    if (bi->tageBranchInfo->condBranch) {
344        if (bi->loopHit >= 0) {
345            int idx = finallindex(bi->loopIndex,
346                                  bi->loopLowPcBits,
347                                  bi->loopHit);
348            ltable[idx].currentIterSpec = bi->currentIter;
349        }
350    }
351}
352
353void
354LTAGE::squash(ThreadID tid, void *bp_history)
355{
356    LTageBranchInfo* bi = (LTageBranchInfo*)(bp_history);
357
358    if (bi->tageBranchInfo->condBranch) {
359        squashLoop(bi);
360    }
361
362    TAGE::squash(tid, bp_history);
363}
364
365void
366LTAGE::regStats()
367{
368    TAGE::regStats();
369
370    loopPredictorCorrect
371        .name(name() + ".loopPredictorCorrect")
372        .desc("Number of times the loop predictor is the provider and "
373              "the prediction is correct");
374
375    loopPredictorWrong
376        .name(name() + ".loopPredictorWrong")
377        .desc("Number of times the loop predictor is the provider and "
378              "the prediction is wrong");
379}
380
381
382
383LTAGE*
384LTAGEParams::create()
385{
386    return new LTAGE(this);
387}
388