1 2 /*--------------------------------------------------------------------*/ 3 /*--- Cache simulation cg_sim.c ---*/ 4 /*--------------------------------------------------------------------*/ 5 6 /* 7 This file is part of Cachegrind, a Valgrind tool for cache 8 profiling programs. 9 10 Copyright (C) 2002-2015 Nicholas Nethercote 11 njn (at) valgrind.org 12 13 This program is free software; you can redistribute it and/or 14 modify it under the terms of the GNU General Public License as 15 published by the Free Software Foundation; either version 2 of the 16 License, or (at your option) any later version. 17 18 This program is distributed in the hope that it will be useful, but 19 WITHOUT ANY WARRANTY; without even the implied warranty of 20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 21 General Public License for more details. 22 23 You should have received a copy of the GNU General Public License 24 along with this program; if not, write to the Free Software 25 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 26 02111-1307, USA. 27 28 The GNU General Public License is contained in the file COPYING. 29 */ 30 31 /* Notes: 32 - simulates a write-allocate cache 33 - (block --> set) hash function uses simple bit selection 34 - handling of references straddling two cache blocks: 35 - counts as only one cache access (not two) 36 - both blocks hit --> one hit 37 - one block hits, the other misses --> one miss 38 - both blocks miss --> one miss (not two) 39 */ 40 41 typedef struct { 42 Int size; /* bytes */ 43 Int assoc; 44 Int line_size; /* bytes */ 45 Int sets; 46 Int sets_min_1; 47 Int line_size_bits; 48 Int tag_shift; 49 HChar desc_line[128]; /* large enough */ 50 UWord* tags; 51 } cache_t2; 52 53 /* By this point, the size/assoc/line_size has been checked. */ 54 static void cachesim_initcache(cache_t config, cache_t2* c) 55 { 56 Int i; 57 58 c->size = config.size; 59 c->assoc = config.assoc; 60 c->line_size = config.line_size; 61 62 c->sets = (c->size / c->line_size) / c->assoc; 63 c->sets_min_1 = c->sets - 1; 64 c->line_size_bits = VG_(log2)(c->line_size); 65 c->tag_shift = c->line_size_bits + VG_(log2)(c->sets); 66 67 if (c->assoc == 1) { 68 VG_(sprintf)(c->desc_line, "%d B, %d B, direct-mapped", 69 c->size, c->line_size); 70 } else { 71 VG_(sprintf)(c->desc_line, "%d B, %d B, %d-way associative", 72 c->size, c->line_size, c->assoc); 73 } 74 75 c->tags = VG_(malloc)("cg.sim.ci.1", 76 sizeof(UWord) * c->sets * c->assoc); 77 78 for (i = 0; i < c->sets * c->assoc; i++) 79 c->tags[i] = 0; 80 } 81 82 /* This attribute forces GCC to inline the function, getting rid of a 83 * lot of indirection around the cache_t2 pointer, if it is known to be 84 * constant in the caller (the caller is inlined itself). 85 * Without inlining of simulator functions, cachegrind can get 40% slower. 86 */ 87 __attribute__((always_inline)) 88 static __inline__ 89 Bool cachesim_setref_is_miss(cache_t2* c, UInt set_no, UWord tag) 90 { 91 int i, j; 92 UWord *set; 93 94 set = &(c->tags[set_no * c->assoc]); 95 96 /* This loop is unrolled for just the first case, which is the most */ 97 /* common. We can't unroll any further because it would screw up */ 98 /* if we have a direct-mapped (1-way) cache. */ 99 if (tag == set[0]) 100 return False; 101 102 /* If the tag is one other than the MRU, move it into the MRU spot */ 103 /* and shuffle the rest down. */ 104 for (i = 1; i < c->assoc; i++) { 105 if (tag == set[i]) { 106 for (j = i; j > 0; j--) { 107 set[j] = set[j - 1]; 108 } 109 set[0] = tag; 110 111 return False; 112 } 113 } 114 115 /* A miss; install this tag as MRU, shuffle rest down. */ 116 for (j = c->assoc - 1; j > 0; j--) { 117 set[j] = set[j - 1]; 118 } 119 set[0] = tag; 120 121 return True; 122 } 123 124 __attribute__((always_inline)) 125 static __inline__ 126 Bool cachesim_ref_is_miss(cache_t2* c, Addr a, UChar size) 127 { 128 /* A memory block has the size of a cache line */ 129 UWord block1 = a >> c->line_size_bits; 130 UWord block2 = (a+size-1) >> c->line_size_bits; 131 UInt set1 = block1 & c->sets_min_1; 132 133 /* Tags used in real caches are minimal to save space. 134 * As the last bits of the block number of addresses mapping 135 * into one cache set are the same, real caches use as tag 136 * tag = block >> log2(#sets) 137 * But using the memory block as more specific tag is fine, 138 * and saves instructions. 139 */ 140 UWord tag1 = block1; 141 142 /* Access entirely within line. */ 143 if (block1 == block2) 144 return cachesim_setref_is_miss(c, set1, tag1); 145 146 /* Access straddles two lines. */ 147 else if (block1 + 1 == block2) { 148 UInt set2 = block2 & c->sets_min_1; 149 UWord tag2 = block2; 150 151 /* always do both, as state is updated as side effect */ 152 if (cachesim_setref_is_miss(c, set1, tag1)) { 153 cachesim_setref_is_miss(c, set2, tag2); 154 return True; 155 } 156 return cachesim_setref_is_miss(c, set2, tag2); 157 } 158 VG_(printf)("addr: %lx size: %u blocks: %lu %lu", 159 a, size, block1, block2); 160 VG_(tool_panic)("item straddles more than two cache sets"); 161 /* not reached */ 162 return True; 163 } 164 165 166 static cache_t2 LL; 167 static cache_t2 I1; 168 static cache_t2 D1; 169 170 static void cachesim_initcaches(cache_t I1c, cache_t D1c, cache_t LLc) 171 { 172 cachesim_initcache(I1c, &I1); 173 cachesim_initcache(D1c, &D1); 174 cachesim_initcache(LLc, &LL); 175 } 176 177 __attribute__((always_inline)) 178 static __inline__ 179 void cachesim_I1_doref_Gen(Addr a, UChar size, ULong* m1, ULong *mL) 180 { 181 if (cachesim_ref_is_miss(&I1, a, size)) { 182 (*m1)++; 183 if (cachesim_ref_is_miss(&LL, a, size)) 184 (*mL)++; 185 } 186 } 187 188 // common special case IrNoX 189 __attribute__((always_inline)) 190 static __inline__ 191 void cachesim_I1_doref_NoX(Addr a, UChar size, ULong* m1, ULong *mL) 192 { 193 UWord block = a >> I1.line_size_bits; 194 UInt I1_set = block & I1.sets_min_1; 195 196 // use block as tag 197 if (cachesim_setref_is_miss(&I1, I1_set, block)) { 198 UInt LL_set = block & LL.sets_min_1; 199 (*m1)++; 200 // can use block as tag as L1I and LL cache line sizes are equal 201 if (cachesim_setref_is_miss(&LL, LL_set, block)) 202 (*mL)++; 203 } 204 } 205 206 __attribute__((always_inline)) 207 static __inline__ 208 void cachesim_D1_doref(Addr a, UChar size, ULong* m1, ULong *mL) 209 { 210 if (cachesim_ref_is_miss(&D1, a, size)) { 211 (*m1)++; 212 if (cachesim_ref_is_miss(&LL, a, size)) 213 (*mL)++; 214 } 215 } 216 217 /* Check for special case IrNoX. Called at instrumentation time. 218 * 219 * Does this Ir only touch one cache line, and are L1I/LL cache 220 * line sizes the same? This allows to get rid of a runtime check. 221 * 222 * Returning false is always fine, as this calls the generic case 223 */ 224 static Bool cachesim_is_IrNoX(Addr a, UChar size) 225 { 226 UWord block1, block2; 227 228 if (I1.line_size_bits != LL.line_size_bits) return False; 229 block1 = a >> I1.line_size_bits; 230 block2 = (a+size-1) >> I1.line_size_bits; 231 if (block1 != block2) return False; 232 233 return True; 234 } 235 236 /*--------------------------------------------------------------------*/ 237 /*--- end cg_sim.c ---*/ 238 /*--------------------------------------------------------------------*/ 239 240
