indirect.cc revision 13654:dc3878f03a0c
14238SN/A/* 24238SN/A * Copyright (c) 2014 ARM Limited 34238SN/A * All rights reserved. 44238SN/A * 54238SN/A * Redistribution and use in source and binary forms, with or without 64238SN/A * modification, are permitted provided that the following conditions are 74238SN/A * met: redistributions of source code must retain the above copyright 84238SN/A * notice, this list of conditions and the following disclaimer; 94238SN/A * redistributions in binary form must reproduce the above copyright 104238SN/A * notice, this list of conditions and the following disclaimer in the 114238SN/A * documentation and/or other materials provided with the distribution; 124238SN/A * neither the name of the copyright holders nor the names of its 134238SN/A * contributors may be used to endorse or promote products derived from 144238SN/A * this software without specific prior written permission. 154238SN/A * 164238SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 174238SN/A * "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 56void 57IndirectPredictor::updateDirectionInfo(ThreadID tid, bool taken, 58 void* & indirect_history) 59{ 60 // record the GHR as it was before this prediction 61 // It will be used to recover the history in case this prediction is 62 // wrong or belongs to bad path 63 indirect_history = new unsigned(threadInfo[tid].ghr); 64 65 threadInfo[tid].ghr <<= taken; 66} 67 68void 69IndirectPredictor::changeDirectionPrediction(ThreadID tid, 70 void * indirect_history, bool actually_taken) 71{ 72 unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 73 threadInfo[tid].ghr = ((*previousGhr) << 1) + actually_taken; 74} 75 76bool 77IndirectPredictor::lookup(Addr br_addr, TheISA::PCState& target, 78 ThreadID tid) 79{ 80 Addr set_index = getSetIndex(br_addr, threadInfo[tid].ghr, tid); 81 Addr tag = getTag(br_addr); 82 83 assert(set_index < numSets); 84 85 DPRINTF(Indirect, "Looking up %x (set:%d)\n", br_addr, set_index); 86 const auto &iset = targetCache[set_index]; 87 for (auto way = iset.begin(); way != iset.end(); ++way) { 88 if (way->tag == tag) { 89 DPRINTF(Indirect, "Hit %x (target:%s)\n", br_addr, way->target); 90 target = way->target; 91 return true; 92 } 93 } 94 DPRINTF(Indirect, "Miss %x\n", br_addr); 95 return false; 96} 97 98void 99IndirectPredictor::recordIndirect(Addr br_addr, Addr tgt_addr, 100 InstSeqNum seq_num, ThreadID tid) 101{ 102 DPRINTF(Indirect, "Recording %x seq:%d\n", br_addr, seq_num); 103 HistoryEntry entry(br_addr, tgt_addr, seq_num); 104 threadInfo[tid].pathHist.push_back(entry); 105} 106 107void 108IndirectPredictor::commit(InstSeqNum seq_num, ThreadID tid, 109 void * indirect_history) 110{ 111 DPRINTF(Indirect, "Committing seq:%d\n", seq_num); 112 ThreadInfo &t_info = threadInfo[tid]; 113 114 // we do not need to recover the GHR, so delete the information 115 unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 116 delete previousGhr; 117 118 if (t_info.pathHist.empty()) return; 119 120 if (t_info.headHistEntry < t_info.pathHist.size() && 121 t_info.pathHist[t_info.headHistEntry].seqNum <= seq_num) { 122 if (t_info.headHistEntry >= pathLength) { 123 t_info.pathHist.pop_front(); 124 } else { 125 ++t_info.headHistEntry; 126 } 127 } 128} 129 130void 131IndirectPredictor::squash(InstSeqNum seq_num, ThreadID tid) 132{ 133 DPRINTF(Indirect, "Squashing seq:%d\n", seq_num); 134 ThreadInfo &t_info = threadInfo[tid]; 135 auto squash_itr = t_info.pathHist.begin(); 136 while (squash_itr != t_info.pathHist.end()) { 137 if (squash_itr->seqNum > seq_num) { 138 break; 139 } 140 ++squash_itr; 141 } 142 if (squash_itr != t_info.pathHist.end()) { 143 DPRINTF(Indirect, "Squashing series starting with sn:%d\n", 144 squash_itr->seqNum); 145 } 146 t_info.pathHist.erase(squash_itr, t_info.pathHist.end()); 147} 148 149void 150IndirectPredictor::deleteDirectionInfo(ThreadID tid, void * indirect_history) 151{ 152 unsigned * previousGhr = static_cast<unsigned *>(indirect_history); 153 threadInfo[tid].ghr = *previousGhr; 154 155 delete previousGhr; 156} 157 158void 159IndirectPredictor::recordTarget(InstSeqNum seq_num, 160 const TheISA::PCState& target, ThreadID tid) 161{ 162 ThreadInfo &t_info = threadInfo[tid]; 163 164 // Should have just squashed so this branch should be the oldest 165 auto hist_entry = *(t_info.pathHist.rbegin()); 166 // Temporarily pop it off the history so we can calculate the set 167 t_info.pathHist.pop_back(); 168 Addr set_index = getSetIndex(hist_entry.pcAddr, t_info.ghr, tid); 169 Addr tag = getTag(hist_entry.pcAddr); 170 hist_entry.targetAddr = target.instAddr(); 171 t_info.pathHist.push_back(hist_entry); 172 173 assert(set_index < numSets); 174 175 auto &iset = targetCache[set_index]; 176 for (auto way = iset.begin(); way != iset.end(); ++way) { 177 if (way->tag == tag) { 178 DPRINTF(Indirect, "Updating Target (seq: %d br:%x set:%d target:" 179 "%s)\n", seq_num, hist_entry.pcAddr, set_index, target); 180 way->target = target; 181 return; 182 } 183 } 184 185 DPRINTF(Indirect, "Allocating Target (seq: %d br:%x set:%d target:%s)\n", 186 seq_num, hist_entry.pcAddr, set_index, target); 187 // Did not find entry, random replacement 188 auto &way = iset[rand() % numWays]; 189 way.tag = tag; 190 way.target = target; 191} 192 193 194inline Addr 195IndirectPredictor::getSetIndex(Addr br_addr, unsigned ghr, ThreadID tid) 196{ 197 ThreadInfo &t_info = threadInfo[tid]; 198 199 Addr hash = br_addr >> instShift; 200 if (hashGHR) { 201 hash ^= ghr; 202 } 203 if (hashTargets) { 204 unsigned hash_shift = floorLog2(numSets) / pathLength; 205 for (int i = t_info.pathHist.size()-1, p = 0; 206 i >= 0 && p < pathLength; i--, p++) { 207 hash ^= (t_info.pathHist[i].targetAddr >> 208 (instShift + p*hash_shift)); 209 } 210 } 211 return hash & (numSets-1); 212} 213 214inline Addr 215IndirectPredictor::getTag(Addr br_addr) 216{ 217 return (br_addr >> instShift) & ((0x1<<tagBits)-1); 218} 219