src/cpu/pred/indirect.cc

   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
  36 IndirectPredictor::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
  56 bool
  57 IndirectPredictor::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
  78 void
  79 IndirectPredictor::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
  87 void
  88 IndirectPredictor::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
 105 void
 106 IndirectPredictor::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
 125 void
 126 IndirectPredictor::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
 161 inline Addr
 162 IndirectPredictor::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
 181 inline Addr
 182 IndirectPredictor::getTag(Addr br_addr)
 183 {
 184     return (br_addr >> instShift) & ((0x1<<tagBits)-1);
 185 }