1/*
2 * Copyright (c) 2014 ARM Limited
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: Mitch Hayenga
29 */
30
31#include "cpu/pred/simple_indirect.hh"
32
33#include "base/intmath.hh"
34#include "debug/Indirect.hh"
35
36SimpleIndirectPredictor::SimpleIndirectPredictor(
37        const SimpleIndirectPredictorParams * params)
38    : IndirectPredictor(params),
39      hashGHR(params->indirectHashGHR),
40      hashTargets(params->indirectHashTargets),
41      numSets(params->indirectSets),
42      numWays(params->indirectWays),
43      tagBits(params->indirectTagSize),
44      pathLength(params->indirectPathLength),
45      instShift(params->instShiftAmt),
46      ghrNumBits(params->indirectGHRBits),
47      ghrMask((1 << params->indirectGHRBits)-1)
48{
49    if (!isPowerOf2(numSets)) {
50      panic("Indirect predictor requires power of 2 number of sets");
51    }
52
53    threadInfo.resize(params->numThreads);
54
55    targetCache.resize(numSets);
56    for (unsigned i = 0; i < numSets; i++) {
57        targetCache[i].resize(numWays);
58    }
59
60    fatal_if(ghrNumBits > (sizeof(ThreadInfo::ghr)*8), "ghr_size is too big");
61}
62
63void
64SimpleIndirectPredictor::genIndirectInfo(ThreadID tid,
65                                         void* & indirect_history)
66{
67    // record the GHR as it was before this prediction
68    // It will be used to recover the history in case this prediction is
69    // wrong or belongs to bad path
70    indirect_history = new unsigned(threadInfo[tid].ghr);
71}
72
73void
74SimpleIndirectPredictor::updateDirectionInfo(
75    ThreadID tid, bool actually_taken)
76{
77    threadInfo[tid].ghr <<= 1;
78    threadInfo[tid].ghr |= actually_taken;
79    threadInfo[tid].ghr &= ghrMask;
80}
81
82void
83SimpleIndirectPredictor::changeDirectionPrediction(ThreadID tid,
84    void * indirect_history, bool actually_taken)
85{
86    unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
87    threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken;
88    threadInfo[tid].ghr &= ghrMask;
89}
90
91bool
92SimpleIndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target,
93    ThreadID tid)
94{
95    Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid);
96    Addr tag = getTag(br_addr);
97
98    assert(set_index < numSets);
99
100    DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index);
101    const auto &iset = targetCache[set_index];
102    for (auto way = iset.begin(); way != iset.end(); ++way) {
103        if (way->tag == tag) {
104            DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target);
105            target = way->target;
106            return true;
107        }
108    }
109    DPRINTF(Indirect, "Miss %x\n", br_addr);
110    return false;
111}
112
113void
114SimpleIndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr,
115    InstSeqNum seq_num, ThreadID tid)
116{
117    DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num);
118    HistoryEntry entry(br_addr, tgt_addr, seq_num);
119    threadInfo[tid].pathHist.push_back(entry);
120}
121
122void
123SimpleIndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid,
124                          void * indirect_history)
125{
126    DPRINTF(Indirect, "Committing seq:%d\n", seq_num);
127    ThreadInfo &t_info = threadInfo[tid];
128
129    // we do not need to recover the GHR, so delete the information
130    unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
131    delete previousGhr;
132
133    if (t_info.pathHist.empty()) return;
134
135    if (t_info.headHistEntry < t_info.pathHist.size() &&
136        t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) {
137        if (t_info.headHistEntry >= pathLength) {
138            t_info.pathHist.pop_front();
139        } else {
140             ++t_info.headHistEntry;
141        }
142    }
143}
144
145void
146SimpleIndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid)
147{
148    DPRINTF(Indirect, "Squashing seq:%d\n", seq_num);
149    ThreadInfo &t_info = threadInfo[tid];
150    auto squash_itr = t_info.pathHist.begin();
151    while (squash_itr != t_info.pathHist.end()) {
152        if (squash_itr->seqNum > seq_num) {
153           break;
154        }
155        ++squash_itr;
156    }
157    if (squash_itr != t_info.pathHist.end()) {
158        DPRINTF(Indirect, "Squashing series starting with sn:%d\n",
159                squash_itr->seqNum);
160    }
161    t_info.pathHist.erase(squash_itr, t_info.pathHist.end());
162}
163
164void
165SimpleIndirectPredictor::deleteIndirectInfo(ThreadID tid,
166                                            void * indirect_history)
167{
168    unsigned * previousGhr = static_cast<unsigned *>(indirect_history);
169    threadInfo[tid].ghr = *previousGhr;
170
171    delete previousGhr;
172}
173
174void
175SimpleIndirectPredictor::recordTarget(
176    InstSeqNum seq_num, void * indirect_history, const TheISA::PCState& target,
177    ThreadID tid)
178{
179    ThreadInfo &t_info = threadInfo[tid];
180
181    unsigned * ghr = static_cast<unsigned *>(indirect_history);
182
183    // Should have just squashed so this branch should be the oldest
184    auto hist_entry = *(t_info.pathHist.rbegin());
185    // Temporarily pop it off the history so we can calculate the set
186    t_info.pathHist.pop_back();
187    Addr set_index = getSetIndex(hist_entry.pcAddr, *ghr, tid);
188    Addr tag = getTag(hist_entry.pcAddr);
189    hist_entry.targetAddr = target.instAddr();
190    t_info.pathHist.push_back(hist_entry);
191
192    assert(set_index < numSets);
193
194    auto &iset = targetCache[set_index];
195    for (auto way = iset.begin(); way != iset.end(); ++way) {
196        if (way->tag == tag) {
197            DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:"
198                    "%s)\n", seq_num, hist_entry.pcAddr, set_index, target);
199            way->target = target;
200            return;
201        }
202    }
203
204    DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n",
205            seq_num, hist_entry.pcAddr, set_index, target);
206    // Did not find entry, random replacement
207    auto &way = iset[rand() % numWays];
208    way.tag = tag;
209    way.target = target;
210}
211
212
213inline Addr
214SimpleIndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid)
215{
216    ThreadInfo &t_info = threadInfo[tid];
217
218    Addr hash = br_addr >> instShift;
219    if (hashGHR) {
220        hash ^= ghr;
221    }
222    if (hashTargets) {
223        unsigned hash_shift = floorLog2(numSets) / pathLength;
224        for (int i = t_info.pathHist.size()-1, p = 0;
225             i >= 0 && p < pathLength; i--, p++) {
226            hash ^= (t_info.pathHist[i].targetAddr >>
227                     (instShift + p*hash_shift));
228        }
229    }
230    return hash & (numSets-1);
231}
232
233inline Addr
234SimpleIndirectPredictor::getTag(Addr br_addr)
235{
236    return (br_addr >> instShift) & ((0x1<<tagBits)-1);
237}
238
239SimpleIndirectPredictor *
240SimpleIndirectPredictorParams::create()
241{
242    return new SimpleIndirectPredictor(this);
243}
244