indirect.cc revision 11426:fb9d14204674 
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/indirect.hh"
32
33#include "base/intmath.hh"
34#include "debug/Indirect.hh"
35
36IndirectPredictor::IndirectPredictor(bool hash_ghr, bool hash_targets,
37    unsigned num_sets, unsigned num_ways,
38    unsigned tag_bits, unsigned path_len, unsigned inst_shift,
39    unsigned num_threads)
40    : hashGHR(hash_ghr), hashTargets(hash_targets),
41      numSets(num_sets), numWays(num_ways), tagBits(tag_bits),
42      pathLength(path_len), instShift(inst_shift)
43{
44    if (!isPowerOf2(numSets)) {
45      panic("Indirect predictor requires power of 2 number of sets");
46    }
47
48    threadInfo.resize(num_threads);
49
50    targetCache.resize(numSets);
51    for (unsigned i = 0; i < numSets; i++) {
52        targetCache[i].resize(numWays);
53    }
54}
55
56bool
57IndirectPredictor::lookup(Addr br_addr, unsigned ghr, TheISA::PCState& target,
58    ThreadID tid)
59{
60    Addr set_index = getSetIndex(br_addr, ghr, tid);
61    Addr tag = getTag(br_addr);
62
63    assert(set_index < numSets);
64
65    DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index);
66    const auto &iset = targetCache[set_index];
67    for (auto way = iset.begin(); way != iset.end(); ++way) {
68        if (way->tag == tag) {
69            DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target);
70            target = way->target;
71            return true;
72        }
73    }
74    DPRINTF(Indirect, "Miss %x\n", br_addr);
75    return false;
76}
77
78void
79IndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr,
80    InstSeqNum seq_num, ThreadID tid)
81{
82    DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num);
83    HistoryEntry entry(br_addr, tgt_addr, seq_num);
84    threadInfo[tid].pathHist.push_back(entry);
85}
86
87void
88IndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid)
89{
90    DPRINTF(Indirect, "Committing seq:%d\n", seq_num);
91    ThreadInfo &t_info = threadInfo[tid];
92
93    if (t_info.pathHist.empty()) return;
94
95    if (t_info.headHistEntry < t_info.pathHist.size() &&
96        t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) {
97        if (t_info.headHistEntry >= pathLength) {
98            t_info.pathHist.pop_front();
99        } else {
100             ++t_info.headHistEntry;
101        }
102    }
103}
104
105void
106IndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid)
107{
108    DPRINTF(Indirect, "Squashing seq:%d\n", seq_num);
109    ThreadInfo &t_info = threadInfo[tid];
110    auto squash_itr = t_info.pathHist.begin();
111    while (squash_itr != t_info.pathHist.end()) {
112        if (squash_itr->seqNum > seq_num) {
113           break;
114        }
115        ++squash_itr;
116    }
117    if (squash_itr != t_info.pathHist.end()) {
118        DPRINTF(Indirect, "Squashing series starting with sn:%d\n",
119                squash_itr->seqNum);
120    }
121    t_info.pathHist.erase(squash_itr, t_info.pathHist.end());
122}
123
124
125void
126IndirectPredictor::recordTarget(InstSeqNum seq_num, unsigned ghr,
127        const TheISA::PCState& target, ThreadID tid)
128{
129    ThreadInfo &t_info = threadInfo[tid];
130
131    // Should have just squashed so this branch should be the oldest
132    auto hist_entry = *(t_info.pathHist.rbegin());
133    // Temporarily pop it off the history so we can calculate the set
134    t_info.pathHist.pop_back();
135    Addr set_index = getSetIndex(hist_entry.pcAddr, ghr, tid);
136    Addr tag = getTag(hist_entry.pcAddr);
137    hist_entry.targetAddr = target.instAddr();
138    t_info.pathHist.push_back(hist_entry);
139
140    assert(set_index < numSets);
141
142    auto &iset = targetCache[set_index];
143    for (auto way = iset.begin(); way != iset.end(); ++way) {
144        if (way->tag == tag) {
145            DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:"
146                    "%s)\n", seq_num, hist_entry.pcAddr, set_index, target);
147            way->target = target;
148            return;
149        }
150    }
151
152    DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n",
153            seq_num, hist_entry.pcAddr, set_index, target);
154    // Did not find entry, random replacement
155    auto &way = iset[rand() % numWays];
156    way.tag = tag;
157    way.target = target;
158}
159
160
161inline Addr
162IndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid)
163{
164    ThreadInfo &t_info = threadInfo[tid];
165
166    Addr hash = br_addr >> instShift;
167    if (hashGHR) {
168        hash ^= ghr;
169    }
170    if (hashTargets) {
171        unsigned hash_shift = floorLog2(numSets) / pathLength;
172        for (int i = t_info.pathHist.size()-1, p = 0;
173             i >= 0 && p < pathLength; i--, p++) {
174            hash ^= (t_info.pathHist[i].targetAddr >>
175                     (instShift + p*hash_shift));
176        }
177    }
178    return hash & (numSets-1);
179}
180
181inline Addr
182IndirectPredictor::getTag(Addr br_addr)
183{
184    return (br_addr >> instShift) & ((0x1<<tagBits)-1);
185}
186