loop_predictor.cc revision 13627 
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#include "cpu/pred/loop_predictor.hh"
38
39#include "params/LoopPredictor.hh"
40
41LoopPredictor::LoopPredictor(LoopPredictorParams *p)
42  : SimObject(p), logSizeLoopPred(p->logSizeLoopPred),
43    loopTableAgeBits(p->loopTableAgeBits),
44    loopTableConfidenceBits(p->loopTableConfidenceBits),
45    loopTableTagBits(p->loopTableTagBits),
46    loopTableIterBits(p->loopTableIterBits),
47    logLoopTableAssoc(p->logLoopTableAssoc),
48    confidenceThreshold((1 << loopTableConfidenceBits) - 1),
49    loopTagMask((1 << loopTableTagBits) - 1),
50    loopNumIterMask((1 << loopTableIterBits) - 1),
51    loopSetMask((1 << (logSizeLoopPred - logLoopTableAssoc)) - 1),
52    loopUseCounter(-1),
53    withLoopBits(p->withLoopBits),
54    useDirectionBit(p->useDirectionBit),
55    useSpeculation(p->useSpeculation),
56    useHashing(p->useHashing),
57    restrictAllocation(p->restrictAllocation),
58    initialLoopIter(p->initialLoopIter),
59    initialLoopAge(p->initialLoopAge),
60    optionalAgeReset(p->optionalAgeReset)
61{
62    assert(initialLoopAge <= ((1 << loopTableAgeBits) - 1));
63}
64
65void
66LoopPredictor::init()
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
78LoopPredictor::BranchInfo*
79LoopPredictor::makeBranchInfo()
80{
81    return new BranchInfo();
82}
83
84int
85LoopPredictor::lindex(Addr pc_in, unsigned instShiftAmt) const
86{
87    // The loop table is implemented as a linear table
88    // If associativity is N (N being 1 << logLoopTableAssoc),
89    // the first N entries are for set 0, the next N entries are for set 1,
90    // and so on.
91    // Thus, this function calculates the set and then it gets left shifted
92    // by logLoopTableAssoc in order to return the index of the first of the
93    // N entries of the set
94    Addr pc = pc_in >> instShiftAmt;
95    if (useHashing) {
96        pc ^= pc_in;
97    }
98    return ((pc & loopSetMask) << logLoopTableAssoc);
99}
100
101int
102LoopPredictor::finallindex(int index, int lowPcBits, int way) const
103{
104    return (useHashing ? (index ^ ((lowPcBits >> way) << logLoopTableAssoc)) :
105                         (index))
106           + way;
107}
108
109//loop prediction: only used if high confidence
110bool
111LoopPredictor::getLoop(Addr pc, BranchInfo* bi, bool speculative,
112                       unsigned instShiftAmt) const
113{
114    bi->loopHit = -1;
115    bi->loopPredValid = false;
116    bi->loopIndex = lindex(pc, instShiftAmt);
117
118    if (useHashing) {
119        unsigned pcShift = logSizeLoopPred - logLoopTableAssoc;
120        bi->loopIndexB = (pc >> pcShift) & loopSetMask;
121        bi->loopTag = (pc >> pcShift) ^ (pc >> (pcShift + loopTableTagBits));
122        bi->loopTag &= loopTagMask;
123    } else {
124        unsigned pcShift = instShiftAmt + logSizeLoopPred - logLoopTableAssoc;
125        bi->loopTag = (pc >> pcShift) & loopTagMask;
126        // bi->loopIndexB is not used without hash
127    }
128
129    for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
130        int idx = finallindex(bi->loopIndex, bi->loopIndexB, i);
131        if (ltable[idx].tag == bi->loopTag) {
132            bi->loopHit = i;
133            bi->loopPredValid = calcConf(idx);
134
135            uint16_t iter = speculative ? ltable[idx].currentIterSpec
136                                        : ltable[idx].currentIter;
137
138            if ((iter + 1) == ltable[idx].numIter) {
139                return useDirectionBit ? !(ltable[idx].dir) : false;
140            } else {
141                return useDirectionBit ? (ltable[idx].dir) : true;
142            }
143        }
144    }
145    return false;
146}
147
148bool
149LoopPredictor::calcConf(int index) const
150{
151    return ltable[index].confidence == confidenceThreshold;
152}
153
154void
155LoopPredictor::specLoopUpdate(bool taken, BranchInfo* bi)
156{
157    if (bi->loopHit>=0) {
158        int index = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
159        if (taken != ltable[index].dir) {
160            ltable[index].currentIterSpec = 0;
161        } else {
162            ltable[index].currentIterSpec =
163                (ltable[index].currentIterSpec + 1) & loopNumIterMask;
164        }
165    }
166}
167
168bool
169LoopPredictor::optionalAgeInc(int nrand) const
170{
171    return false;
172}
173
174void
175LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred,
176                          int random0, int random1, int random2)
177{
178    int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit);
179    if (bi->loopHit >= 0) {
180        //already a hit
181        if (bi->loopPredValid) {
182            if (taken != bi->loopPred) {
183                // free the entry
184                ltable[idx].numIter = 0;
185                ltable[idx].age = 0;
186                ltable[idx].confidence = 0;
187                ltable[idx].currentIter = 0;
188                return;
189            } else if (bi->loopPred != tage_pred || optionalAgeInc(random0)) {
190                unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits);
191            }
192        }
193
194        ltable[idx].currentIter =
195            (ltable[idx].currentIter + 1) & loopNumIterMask;
196        if (ltable[idx].currentIter > ltable[idx].numIter) {
197            ltable[idx].confidence = 0;
198            if (ltable[idx].numIter != 0) {
199                // free the entry
200                ltable[idx].numIter = 0;
201                if (optionalAgeReset) {
202                    ltable[idx].age = 0;
203                }
204            }
205        }
206
207        if (taken != (useDirectionBit ? ltable[idx].dir : true)) {
208            if (ltable[idx].currentIter == ltable[idx].numIter) {
209                unsignedCtrUpdate(ltable[idx].confidence, true,
210                                  loopTableConfidenceBits);
211                //just do not predict when the loop count is 1 or 2
212                if (ltable[idx].numIter < 3) {
213                    // free the entry
214                    ltable[idx].dir = taken; // ignored if no useDirectionBit
215                    ltable[idx].numIter = 0;
216                    ltable[idx].age = 0;
217                    ltable[idx].confidence = 0;
218                }
219            } else {
220                if (ltable[idx].numIter == 0) {
221                    // first complete nest;
222                    ltable[idx].confidence = 0;
223                    ltable[idx].numIter = ltable[idx].currentIter;
224                } else {
225                    //not the same number of iterations as last time: free the
226                    //entry
227                    ltable[idx].numIter = 0;
228                    if (optionalAgeReset) {
229                        ltable[idx].age = 0;
230                    }
231                    ltable[idx].confidence = 0;
232                }
233            }
234            ltable[idx].currentIter = 0;
235        }
236
237    } else if (useDirectionBit ? (bi->predTaken != taken) : taken) {
238        if ((random2 & 3) == 0 || !restrictAllocation) {
239            //try to allocate an entry on taken branch
240            int nrand = random1;
241            for (int i = 0; i < (1 << logLoopTableAssoc); i++) {
242                int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1);
243                idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit);
244                if (ltable[idx].age == 0) {
245                    ltable[idx].dir = !taken; // ignored if no useDirectionBit
246                    ltable[idx].tag = bi->loopTag;
247                    ltable[idx].numIter = 0;
248                    ltable[idx].age = initialLoopAge;
249                    ltable[idx].confidence = 0;
250                    ltable[idx].currentIter = initialLoopIter;
251                    break;
252
253                } else {
254                    ltable[idx].age--;
255                }
256                if (restrictAllocation) {
257                    break;
258                }
259            }
260        }
261    }
262}
263
264bool
265LoopPredictor::loopPredict(ThreadID tid, Addr branch_pc, bool cond_branch,
266                   BranchInfo* bi, bool prev_pred_taken, unsigned instShiftAmt)
267{
268    bool pred_taken = prev_pred_taken;
269    if (cond_branch) {
270        // loop prediction
271        bi->loopPred = getLoop(branch_pc, bi, useSpeculation, instShiftAmt);
272
273        if ((loopUseCounter >= 0) && bi->loopPredValid) {
274            pred_taken = bi->loopPred;
275            bi->loopPredUsed = true;
276        }
277
278        if (useSpeculation) {
279            specLoopUpdate(pred_taken, bi);
280        }
281    }
282
283    return pred_taken;
284}
285
286void
287LoopPredictor::squash(ThreadID tid, BranchInfo *bi)
288{
289    if (bi->loopHit >= 0) {
290        int idx = finallindex(bi->loopIndex,
291                bi->loopIndexB,
292                bi->loopHit);
293        ltable[idx].currentIterSpec = bi->currentIter;
294    }
295}
296
297void
298LoopPredictor::squashLoop(BranchInfo* bi)
299{
300    if (bi->loopHit >= 0) {
301        int idx = finallindex(bi->loopIndex,
302                bi->loopIndexB,
303                bi->loopHit);
304        ltable[idx].currentIterSpec = bi->currentIter;
305    }
306}
307
308void
309LoopPredictor::updateStats(bool taken, BranchInfo* bi)
310{
311    if (taken == bi->loopPred) {
312        loopPredictorCorrect++;
313    } else {
314        loopPredictorWrong++;
315    }
316}
317
318void
319LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
320                                bool tage_pred, BranchInfo* bi,
321                                unsigned instShiftAmt, int rand0, int rand1,
322                                int rand2)
323{
324    if (useSpeculation) {
325        // recalculate loop prediction without speculation
326        // It is ok to overwrite the loop prediction fields in bi
327        // as the stats have already been updated with the previous
328        // values
329        bi->loopPred = getLoop(branch_pc, bi, false, instShiftAmt);
330    }
331
332    if (bi->loopPredValid) {
333        if (bi->predTaken != bi->loopPred) {
334            signedCtrUpdate(loopUseCounter,
335                      (bi->loopPred == taken),
336                      withLoopBits);
337        }
338    }
339
340    loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1, rand2);
341}
342
343void
344LoopPredictor::regStats()
345{
346    loopPredictorCorrect
347        .name(name() + ".loopPredictorCorrect")
348        .desc("Number of times the loop predictor is the provider and "
349              "the prediction is correct");
350
351    loopPredictorWrong
352        .name(name() + ".loopPredictorWrong")
353        .desc("Number of times the loop predictor is the provider and "
354              "the prediction is wrong");
355}
356
357LoopPredictor *
358LoopPredictorParams::create()
359{
360    return new LoopPredictor(this);
361}
362