1/* Simulator cache routines for CGEN simulators (and maybe others). 2 Copyright (C) 1996, 1997, 1998, 2007, 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Cygnus Support. 5 6This file is part of GDB, the GNU debugger. 7 8This program is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3 of the License, or 11(at your option) any later version. 12 13This program is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with this program. If not, see <http://www.gnu.org/licenses/>. */ 20 21#define SCACHE_DEFINE_INLINE 22 23#include "sim-main.h" 24#ifdef HAVE_STDLIB_H 25#include <stdlib.h> 26#endif 27#include "libiberty.h" 28#include "sim-options.h" 29#include "sim-io.h" 30 31#define MAX(a,b) ((a) > (b) ? (a) : (b)) 32 33/* Unused address. */ 34#define UNUSED_ADDR 0xffffffff 35 36/* Scache configuration parameters. 37 ??? Experiments to determine reasonable values is wip. 38 These are just guesses. */ 39 40/* Default number of scache elements. 41 The size of an element is typically 32-64 bytes, so the size of the 42 default scache will be between 512K and 1M bytes. */ 43#ifdef CONFIG_SIM_CACHE_SIZE 44#define SCACHE_DEFAULT_CACHE_SIZE CONFIG_SIM_CACHE_SIZE 45#else 46#define SCACHE_DEFAULT_CACHE_SIZE 16384 47#endif 48 49/* Minimum cache size. 50 The m32r port assumes a cache size of at least 2 so it can decode both 16 51 bit insns. When compiling we need an extra for the chain entry. And this 52 must be a multiple of 2. Hence 4 is the minimum (though, for those with 53 featuritis or itchy pedantic bits, we could make this conditional on 54 WITH_SCACHE_PBB). */ 55#define MIN_SCACHE_SIZE 4 56 57/* Ratio of size of text section to size of scache. 58 When compiling, we don't want to flush the scache more than we have to 59 but we also don't want it to be exorbitantly(sp?) large. So we pick a high 60 default value, then reduce it by the size of the program being simulated, 61 but we don't override any value specified on the command line. 62 If not specified on the command line, the size to use is computed as 63 max (MIN_SCACHE_SIZE, 64 min (DEFAULT_SCACHE_SIZE, 65 text_size / (base_insn_size * INSN_SCACHE_RATIO))). */ 66/* ??? Interesting idea but not currently used. */ 67#define INSN_SCACHE_RATIO 4 68 69/* Default maximum insn chain length. 70 The only reason for a maximum is so we can place a maximum size on the 71 profiling table. Chain lengths are determined by cti's. 72 32 is a more reasonable number, but when profiling, the before/after 73 handlers take up that much more space. The scache is filled from front to 74 back so all this determines is when the scache needs to be flushed. */ 75#define MAX_CHAIN_LENGTH 64 76 77/* Default maximum hash list length. */ 78#define MAX_HASH_CHAIN_LENGTH 4 79 80/* Minimum hash table size. */ 81#define MIN_HASH_CHAINS 32 82 83/* Ratio of number of scache elements to number of hash lists. 84 Since the user can only specify the size of the scache, we compute the 85 size of the hash table as 86 max (MIN_HASH_CHAINS, scache_size / SCACHE_HASH_RATIO). */ 87#define SCACHE_HASH_RATIO 8 88 89/* Hash a PC value. 90 FIXME: May wish to make the hashing architecture specific. 91 FIXME: revisit */ 92#define HASH_PC(pc) (((pc) >> 2) + ((pc) >> 5)) 93 94static MODULE_INIT_FN scache_init; 95static MODULE_UNINSTALL_FN scache_uninstall; 96 97static DECLARE_OPTION_HANDLER (scache_option_handler); 98 99#define OPTION_PROFILE_SCACHE (OPTION_START + 0) 100 101static const OPTION scache_options[] = { 102 { {"scache-size", optional_argument, NULL, 'c'}, 103 'c', "[SIZE]", "Specify size of simulator execution cache", 104 scache_option_handler }, 105#if WITH_SCACHE_PBB 106 /* ??? It might be nice to allow the user to specify the size of the hash 107 table, the maximum hash list length, and the maximum chain length, but 108 for now that might be more akin to featuritis. */ 109#endif 110 { {"profile-scache", optional_argument, NULL, OPTION_PROFILE_SCACHE}, 111 '\0', "on|off", "Perform simulator execution cache profiling", 112 scache_option_handler }, 113 { {NULL, no_argument, NULL, 0}, '\0', NULL, NULL, NULL } 114}; 115 116static SIM_RC 117scache_option_handler (SIM_DESC sd, sim_cpu *cpu, int opt, 118 char *arg, int is_command) 119{ 120 switch (opt) 121 { 122 case 'c' : 123 if (WITH_SCACHE) 124 { 125 if (arg != NULL) 126 { 127 int n = strtol (arg, NULL, 0); 128 if (n < MIN_SCACHE_SIZE) 129 { 130 sim_io_eprintf (sd, "invalid scache size `%d', must be at least 4", n); 131 return SIM_RC_FAIL; 132 } 133 /* Ensure it's a multiple of 2. */ 134 if ((n & (n - 1)) != 0) 135 { 136 sim_io_eprintf (sd, "scache size `%d' not a multiple of 2\n", n); 137 { 138 /* round up to nearest multiple of 2 */ 139 int i; 140 for (i = 1; i < n; i <<= 1) 141 continue; 142 n = i; 143 } 144 sim_io_eprintf (sd, "rounding scache size up to %d\n", n); 145 } 146 if (cpu == NULL) 147 STATE_SCACHE_SIZE (sd) = n; 148 else 149 CPU_SCACHE_SIZE (cpu) = n; 150 } 151 else 152 { 153 if (cpu == NULL) 154 STATE_SCACHE_SIZE (sd) = SCACHE_DEFAULT_CACHE_SIZE; 155 else 156 CPU_SCACHE_SIZE (cpu) = SCACHE_DEFAULT_CACHE_SIZE; 157 } 158 } 159 else 160 sim_io_eprintf (sd, "Simulator execution cache not enabled, `--scache-size' ignored\n"); 161 break; 162 163 case OPTION_PROFILE_SCACHE : 164 if (WITH_SCACHE && WITH_PROFILE_SCACHE_P) 165 { 166 /* FIXME: handle cpu != NULL. */ 167 return sim_profile_set_option (sd, "-scache", PROFILE_SCACHE_IDX, 168 arg); 169 } 170 else 171 sim_io_eprintf (sd, "Simulator cache profiling not compiled in, `--profile-scache' ignored\n"); 172 break; 173 } 174 175 return SIM_RC_OK; 176} 177 178SIM_RC 179scache_install (SIM_DESC sd) 180{ 181 sim_add_option_table (sd, NULL, scache_options); 182 sim_module_add_init_fn (sd, scache_init); 183 sim_module_add_uninstall_fn (sd, scache_uninstall); 184 185 /* This is the default, it may be overridden on the command line. */ 186 STATE_SCACHE_SIZE (sd) = WITH_SCACHE; 187 188 return SIM_RC_OK; 189} 190 191static SIM_RC 192scache_init (SIM_DESC sd) 193{ 194 int c; 195 196 for (c = 0; c < MAX_NR_PROCESSORS; ++c) 197 { 198 SIM_CPU *cpu = STATE_CPU (sd, c); 199 int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu))); 200 201 /* elm_size is 0 if the cpu doesn't not have scache support */ 202 if (elm_size == 0) 203 { 204 CPU_SCACHE_SIZE (cpu) = 0; 205 CPU_SCACHE_CACHE (cpu) = NULL; 206 } 207 else 208 { 209 if (CPU_SCACHE_SIZE (cpu) == 0) 210 CPU_SCACHE_SIZE (cpu) = STATE_SCACHE_SIZE (sd); 211 CPU_SCACHE_CACHE (cpu) = 212 (SCACHE *) xmalloc (CPU_SCACHE_SIZE (cpu) * elm_size); 213#if WITH_SCACHE_PBB 214 CPU_SCACHE_MAX_CHAIN_LENGTH (cpu) = MAX_CHAIN_LENGTH; 215 CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu) = MAX_HASH_CHAIN_LENGTH; 216 CPU_SCACHE_NUM_HASH_CHAINS (cpu) = MAX (MIN_HASH_CHAINS, 217 CPU_SCACHE_SIZE (cpu) 218 / SCACHE_HASH_RATIO); 219 CPU_SCACHE_HASH_TABLE (cpu) = 220 (SCACHE_MAP *) xmalloc (CPU_SCACHE_NUM_HASH_CHAINS (cpu) 221 * CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu) 222 * sizeof (SCACHE_MAP)); 223 CPU_SCACHE_PBB_BEGIN (cpu) = (SCACHE *) zalloc (elm_size); 224 CPU_SCACHE_CHAIN_LENGTHS (cpu) = 225 (unsigned long *) zalloc ((CPU_SCACHE_MAX_CHAIN_LENGTH (cpu) + 1) 226 * sizeof (long)); 227#endif 228 } 229 } 230 231 scache_flush (sd); 232 233 return SIM_RC_OK; 234} 235 236static void 237scache_uninstall (SIM_DESC sd) 238{ 239 int c; 240 241 for (c = 0; c < MAX_NR_PROCESSORS; ++c) 242 { 243 SIM_CPU *cpu = STATE_CPU (sd, c); 244 245 if (CPU_SCACHE_CACHE (cpu) != NULL) 246 free (CPU_SCACHE_CACHE (cpu)); 247#if WITH_SCACHE_PBB 248 if (CPU_SCACHE_HASH_TABLE (cpu) != NULL) 249 free (CPU_SCACHE_HASH_TABLE (cpu)); 250 if (CPU_SCACHE_PBB_BEGIN (cpu) != NULL) 251 free (CPU_SCACHE_PBB_BEGIN (cpu)); 252 if (CPU_SCACHE_CHAIN_LENGTHS (cpu) != NULL) 253 free (CPU_SCACHE_CHAIN_LENGTHS (cpu)); 254#endif 255 } 256} 257 258void 259scache_flush (SIM_DESC sd) 260{ 261 int c; 262 263 for (c = 0; c < MAX_NR_PROCESSORS; ++c) 264 { 265 SIM_CPU *cpu = STATE_CPU (sd, c); 266 scache_flush_cpu (cpu); 267 } 268} 269 270void 271scache_flush_cpu (SIM_CPU *cpu) 272{ 273 int i,n; 274 275 /* Don't bother if cache not in use. */ 276 if (CPU_SCACHE_SIZE (cpu) == 0) 277 return; 278 279#if WITH_SCACHE_PBB 280 /* It's important that this be reasonably fast as this can be done when 281 the simulation is running. */ 282 CPU_SCACHE_NEXT_FREE (cpu) = CPU_SCACHE_CACHE (cpu); 283 n = CPU_SCACHE_NUM_HASH_CHAINS (cpu) * CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu); 284 /* ??? Might be faster to just set the first entry, then update the 285 "last entry" marker during allocation. */ 286 for (i = 0; i < n; ++i) 287 CPU_SCACHE_HASH_TABLE (cpu) [i] . pc = UNUSED_ADDR; 288#else 289 { 290 int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu))); 291 SCACHE *sc; 292 293 /* Technically, this may not be necessary, but it helps debugging. */ 294 memset (CPU_SCACHE_CACHE (cpu), 0, 295 CPU_SCACHE_SIZE (cpu) * elm_size); 296 297 for (i = 0, sc = CPU_SCACHE_CACHE (cpu); i < CPU_SCACHE_SIZE (cpu); 298 ++i, sc = (SCACHE *) ((char *) sc + elm_size)) 299 { 300 sc->argbuf.addr = UNUSED_ADDR; 301 } 302 } 303#endif 304} 305 306#if WITH_SCACHE_PBB 307 308/* Look up PC in the hash table of scache entry points. 309 Returns the entry or NULL if not found. */ 310 311SCACHE * 312scache_lookup (SIM_CPU *cpu, IADDR pc) 313{ 314 /* FIXME: hash computation is wrong, doesn't take into account 315 NUM_HASH_CHAIN_ENTRIES. A lot of the hash table will be unused! */ 316 unsigned int slot = HASH_PC (pc) & (CPU_SCACHE_NUM_HASH_CHAINS (cpu) - 1); 317 int i, max_i = CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu); 318 SCACHE_MAP *scm; 319 320 /* We don't update hit/miss statistics as this is only used when recording 321 branch target addresses. */ 322 323 scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot]; 324 for (i = 0; i < max_i && scm->pc != UNUSED_ADDR; ++i, ++scm) 325 { 326 if (scm->pc == pc) 327 return scm->sc; 328 } 329 return 0; 330} 331 332/* Look up PC and if not found create an entry for it. 333 If found the result is a pointer to the SCACHE entry. 334 If not found the result is NULL, and the address of a buffer of at least 335 N entries is stored in BUFP. 336 It's done this way so the caller can still distinguish found/not-found. 337 If the table is full, it is emptied to make room. 338 If the maximum length of a hash list is reached a random entry is thrown out 339 to make room. 340 ??? One might want to try to make this smarter, but let's see some 341 measurable benefit first. */ 342 343SCACHE * 344scache_lookup_or_alloc (SIM_CPU *cpu, IADDR pc, int n, SCACHE **bufp) 345{ 346 /* FIXME: hash computation is wrong, doesn't take into account 347 NUM_HASH_CHAIN_ENTRIES. A lot of the hash table will be unused! */ 348 unsigned int slot = HASH_PC (pc) & (CPU_SCACHE_NUM_HASH_CHAINS (cpu) - 1); 349 int i, max_i = CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu); 350 SCACHE_MAP *scm; 351 SCACHE *sc; 352 353 scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot]; 354 for (i = 0; i < max_i && scm->pc != UNUSED_ADDR; ++i, ++scm) 355 { 356 if (scm->pc == pc) 357 { 358 PROFILE_COUNT_SCACHE_HIT (cpu); 359 return scm->sc; 360 } 361 } 362 PROFILE_COUNT_SCACHE_MISS (cpu); 363 364 /* The address we want isn't cached. Bummer. 365 If the hash chain we have for this address is full, throw out an entry 366 to make room. */ 367 368 if (i == max_i) 369 { 370 /* Rather than do something sophisticated like LRU, we just throw out 371 a semi-random entry. Let someone else have the joy of saying how 372 wrong this is. NEXT_FREE is the entry to throw out and cycles 373 through all possibilities. */ 374 static int next_free = 0; 375 376 scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot]; 377 /* FIXME: This seems rather clumsy. */ 378 for (i = 0; i < next_free; ++i, ++scm) 379 continue; 380 ++next_free; 381 if (next_free == CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu)) 382 next_free = 0; 383 } 384 385 /* At this point SCM points to the hash table entry to use. 386 Now make sure there's room in the cache. */ 387 /* FIXME: Kinda weird to use a next_free adjusted scm when cache is 388 flushed. */ 389 390 { 391 int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu))); 392 int elms_used = (((char *) CPU_SCACHE_NEXT_FREE (cpu) 393 - (char *) CPU_SCACHE_CACHE (cpu)) 394 / elm_size); 395 int elms_left = CPU_SCACHE_SIZE (cpu) - elms_used; 396 397 if (elms_left < n) 398 { 399 PROFILE_COUNT_SCACHE_FULL_FLUSH (cpu); 400 scache_flush_cpu (cpu); 401 } 402 } 403 404 sc = CPU_SCACHE_NEXT_FREE (cpu); 405 scm->pc = pc; 406 scm->sc = sc; 407 408 *bufp = sc; 409 return NULL; 410} 411 412#endif /* WITH_SCACHE_PBB */ 413 414/* Print cache access statics for CPU. */ 415 416void 417scache_print_profile (SIM_CPU *cpu, int verbose) 418{ 419 SIM_DESC sd = CPU_STATE (cpu); 420 unsigned long hits = CPU_SCACHE_HITS (cpu); 421 unsigned long misses = CPU_SCACHE_MISSES (cpu); 422 char buf[20]; 423 unsigned long max_val; 424 unsigned long *lengths; 425 int i; 426 427 if (CPU_SCACHE_SIZE (cpu) == 0) 428 return; 429 430 sim_io_printf (sd, "Simulator Cache Statistics\n\n"); 431 432 /* One could use PROFILE_LABEL_WIDTH here. I chose not to. */ 433 sim_io_printf (sd, " Cache size: %s\n", 434 sim_add_commas (buf, sizeof (buf), CPU_SCACHE_SIZE (cpu))); 435 sim_io_printf (sd, " Hits: %s\n", 436 sim_add_commas (buf, sizeof (buf), hits)); 437 sim_io_printf (sd, " Misses: %s\n", 438 sim_add_commas (buf, sizeof (buf), misses)); 439 if (hits + misses != 0) 440 sim_io_printf (sd, " Hit rate: %.2f%%\n", 441 ((double) hits / ((double) hits + (double) misses)) * 100); 442 443#if WITH_SCACHE_PBB 444 sim_io_printf (sd, "\n"); 445 sim_io_printf (sd, " Hash table size: %s\n", 446 sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAINS (cpu))); 447 sim_io_printf (sd, " Max hash list length: %s\n", 448 sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu))); 449 sim_io_printf (sd, " Max insn chain length: %s\n", 450 sim_add_commas (buf, sizeof (buf), CPU_SCACHE_MAX_CHAIN_LENGTH (cpu))); 451 sim_io_printf (sd, " Cache full flushes: %s\n", 452 sim_add_commas (buf, sizeof (buf), CPU_SCACHE_FULL_FLUSHES (cpu))); 453 sim_io_printf (sd, "\n"); 454 455 if (verbose) 456 { 457 sim_io_printf (sd, " Insn chain lengths:\n\n"); 458 max_val = 0; 459 lengths = CPU_SCACHE_CHAIN_LENGTHS (cpu); 460 for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i) 461 if (lengths[i] > max_val) 462 max_val = lengths[i]; 463 for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i) 464 { 465 sim_io_printf (sd, " %2d: %*s: ", 466 i, 467 max_val < 10000 ? 5 : 10, 468 sim_add_commas (buf, sizeof (buf), lengths[i])); 469 sim_profile_print_bar (sd, cpu, PROFILE_HISTOGRAM_WIDTH, 470 lengths[i], max_val); 471 sim_io_printf (sd, "\n"); 472 } 473 sim_io_printf (sd, "\n"); 474 } 475#endif /* WITH_SCACHE_PBB */ 476} 477