sim/common/cgen-scache.c

   1 /* Simulator cache routines for CGEN simulators (and maybe others).
   2    Copyright (C) 1996, 1997, 1998 Free Software Foundation, Inc.
   3    Contributed by Cygnus Support.
   4
   5 This file is part of GDB, the GNU debugger.
   6
   7 This program is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 This program is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License along
  18 with this program; if not, write to the Free Software Foundation, Inc.,
  19 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  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
  94 static MODULE_INIT_FN scache_init;
  95 static MODULE_UNINSTALL_FN scache_uninstall;
  96
  97 static DECLARE_OPTION_HANDLER (scache_option_handler);
  98
  99 #define OPTION_PROFILE_SCACHE   (OPTION_START + 0)
 100
 101 static 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
 116 static SIM_RC
 117 scache_option_handler (SIM_DESC sd, sim_cpu *cpu, int opt,
 118                        char *arg, int is_command)
 119 {
 120   int n;
 121
 122   switch (opt)
 123     {
 124     case 'c' :
 125       if (WITH_SCACHE)
 126         {
 127           if (arg != NULL)
 128             {
 129               int n = strtol (arg, NULL, 0);
 130               if (n < MIN_SCACHE_SIZE)
 131                 {
 132                   sim_io_eprintf (sd, "invalid scache size `%d', must be at least 4", n);
 133                   return SIM_RC_FAIL;
 134                 }
 135               /* Ensure it's a multiple of 2.  */
 136               if ((n & (n - 1)) != 0)
 137                 {
 138                   sim_io_eprintf (sd, "scache size `%d' not a multiple of 2\n", n);
 139                   {
 140                     /* round up to nearest multiple of 2 */
 141                     int i;
 142                     for (i = 1; i < n; i <<= 1)
 143                       continue;
 144                     n = i;
 145                   }
 146                   sim_io_eprintf (sd, "rounding scache size up to %d\n", n);
 147                 }
 148               if (cpu == NULL)
 149                 STATE_SCACHE_SIZE (sd) = n;
 150               else
 151                 CPU_SCACHE_SIZE (cpu) = n;
 152             }
 153           else
 154             {
 155               if (cpu == NULL)
 156                 STATE_SCACHE_SIZE (sd) = SCACHE_DEFAULT_CACHE_SIZE;
 157               else
 158                 CPU_SCACHE_SIZE (cpu) = SCACHE_DEFAULT_CACHE_SIZE;
 159             }
 160         }
 161       else
 162         sim_io_eprintf (sd, "Simulator execution cache not enabled, `--scache-size' ignored\n");
 163       break;
 164
 165     case OPTION_PROFILE_SCACHE :
 166       if (WITH_SCACHE && WITH_PROFILE_SCACHE_P)
 167         {
 168           /* FIXME: handle cpu != NULL.  */
 169           return sim_profile_set_option (sd, "-scache", PROFILE_SCACHE_IDX,
 170                                          arg);
 171         }
 172       else
 173         sim_io_eprintf (sd, "Simulator cache profiling not compiled in, `--profile-scache' ignored\n");
 174       break;
 175     }
 176
 177   return SIM_RC_OK;
 178 }
 179
 180 SIM_RC
 181 scache_install (SIM_DESC sd)
 182 {
 183   sim_add_option_table (sd, NULL, scache_options);
 184   sim_module_add_init_fn (sd, scache_init);
 185   sim_module_add_uninstall_fn (sd, scache_uninstall);
 186
 187   /* This is the default, it may be overridden on the command line.  */
 188   STATE_SCACHE_SIZE (sd) = WITH_SCACHE;
 189
 190   return SIM_RC_OK;
 191 }
 192
 193 static SIM_RC
 194 scache_init (SIM_DESC sd)
 195 {
 196   int c;
 197
 198   for (c = 0; c < MAX_NR_PROCESSORS; ++c)
 199     {
 200       SIM_CPU *cpu = STATE_CPU (sd, c);
 201       int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu)));
 202
 203       /* elm_size is 0 if the cpu doesn't not have scache support */
 204       if (elm_size == 0)
 205         {
 206           CPU_SCACHE_SIZE (cpu) = 0;
 207           CPU_SCACHE_CACHE (cpu) = NULL;
 208         }
 209       else
 210         {
 211           if (CPU_SCACHE_SIZE (cpu) == 0)
 212             CPU_SCACHE_SIZE (cpu) = STATE_SCACHE_SIZE (sd);
 213           CPU_SCACHE_CACHE (cpu) =
 214             (SCACHE *) xmalloc (CPU_SCACHE_SIZE (cpu) * elm_size);
 215 #if WITH_SCACHE_PBB
 216           CPU_SCACHE_MAX_CHAIN_LENGTH (cpu) = MAX_CHAIN_LENGTH;
 217           CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu) = MAX_HASH_CHAIN_LENGTH;
 218           CPU_SCACHE_NUM_HASH_CHAINS (cpu) = MAX (MIN_HASH_CHAINS,
 219                                                   CPU_SCACHE_SIZE (cpu)
 220                                                   / SCACHE_HASH_RATIO);
 221           CPU_SCACHE_HASH_TABLE (cpu) =
 222             (SCACHE_MAP *) xmalloc (CPU_SCACHE_NUM_HASH_CHAINS (cpu)
 223                                     * CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu)
 224                                     * sizeof (SCACHE_MAP));
 225           CPU_SCACHE_PBB_BEGIN (cpu) = (SCACHE *) zalloc (elm_size);
 226           CPU_SCACHE_CHAIN_LENGTHS (cpu) =
 227             (unsigned long *) zalloc ((CPU_SCACHE_MAX_CHAIN_LENGTH (cpu) + 1)
 228                                       * sizeof (long));
 229 #endif
 230         }
 231     }
 232
 233   scache_flush (sd);
 234
 235   return SIM_RC_OK;
 236 }
 237
 238 static void
 239 scache_uninstall (SIM_DESC sd)
 240 {
 241   int c;
 242
 243   for (c = 0; c < MAX_NR_PROCESSORS; ++c)
 244     {
 245       SIM_CPU *cpu = STATE_CPU (sd, c);
 246
 247       if (CPU_SCACHE_CACHE (cpu) != NULL)
 248         free (CPU_SCACHE_CACHE (cpu));
 249 #if WITH_SCACHE_PBB
 250       if (CPU_SCACHE_HASH_TABLE (cpu) != NULL)
 251         free (CPU_SCACHE_HASH_TABLE (cpu));
 252       if (CPU_SCACHE_PBB_BEGIN (cpu) != NULL)
 253         free (CPU_SCACHE_PBB_BEGIN (cpu));
 254       if (CPU_SCACHE_CHAIN_LENGTHS (cpu) != NULL)
 255         free (CPU_SCACHE_CHAIN_LENGTHS (cpu));
 256 #endif
 257     }
 258 }
 259
 260 void
 261 scache_flush (SIM_DESC sd)
 262 {
 263   int c;
 264
 265   for (c = 0; c < MAX_NR_PROCESSORS; ++c)
 266     {
 267       SIM_CPU *cpu = STATE_CPU (sd, c);
 268       scache_flush_cpu (cpu);
 269     }
 270 }
 271
 272 void
 273 scache_flush_cpu (SIM_CPU *cpu)
 274 {
 275   int i,n;
 276
 277   /* Don't bother if cache not in use.  */
 278   if (CPU_SCACHE_SIZE (cpu) == 0)
 279     return;
 280
 281 #if WITH_SCACHE_PBB
 282   /* It's important that this be reasonably fast as this can be done when
 283      the simulation is running.  */
 284   CPU_SCACHE_NEXT_FREE (cpu) = CPU_SCACHE_CACHE (cpu);
 285   n = CPU_SCACHE_NUM_HASH_CHAINS (cpu) * CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu);
 286   /* ??? Might be faster to just set the first entry, then update the
 287      "last entry" marker during allocation.  */
 288   for (i = 0; i < n; ++i)
 289     CPU_SCACHE_HASH_TABLE (cpu) [i] . pc = UNUSED_ADDR;
 290 #else
 291   {
 292     int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu)));
 293     SCACHE *sc;
 294
 295     /* Technically, this may not be necessary, but it helps debugging.  */
 296     memset (CPU_SCACHE_CACHE (cpu), 0,
 297             CPU_SCACHE_SIZE (cpu) * elm_size);
 298
 299     for (i = 0, sc = CPU_SCACHE_CACHE (cpu); i < CPU_SCACHE_SIZE (cpu);
 300          ++i, sc = (SCACHE *) ((char *) sc + elm_size))
 301       {
 302         sc->argbuf.addr = UNUSED_ADDR;
 303       }
 304   }
 305 #endif
 306 }
 307
 308 #if WITH_SCACHE_PBB
 309
 310 /* Look up PC in the hash table of scache entry points.
 311    Returns the entry or NULL if not found.  */
 312
 313 SCACHE *
 314 scache_lookup (SIM_CPU *cpu, IADDR pc)
 315 {
 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
 343 SCACHE *
 344 scache_lookup_or_alloc (SIM_CPU *cpu, IADDR pc, int n, SCACHE **bufp)
 345 {
 346   unsigned int slot = HASH_PC (pc) & (CPU_SCACHE_NUM_HASH_CHAINS (cpu) - 1);
 347   int i, max_i = CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu);
 348   SCACHE_MAP *scm;
 349   SCACHE *sc;
 350
 351   scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot];
 352   for (i = 0; i < max_i && scm->pc != UNUSED_ADDR; ++i, ++scm)
 353     {
 354       if (scm->pc == pc)
 355         {
 356           PROFILE_COUNT_SCACHE_HIT (cpu);
 357           return scm->sc;
 358         }
 359     }
 360   PROFILE_COUNT_SCACHE_MISS (cpu);
 361
 362   /* The address we want isn't cached.  Bummer.
 363      If the hash chain we have for this address is full, throw out an entry
 364      to make room.  */
 365
 366   if (i == max_i)
 367     {
 368       /* Rather than do something sophisticated like LRU, we just throw out
 369          a semi-random entry.  Let someone else have the joy of saying how
 370          wrong this is.  NEXT_FREE is the entry to throw out and cycles
 371          through all possibilities.  */
 372       static int next_free = 0;
 373
 374       scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot];
 375       for (i = 0; i < next_free; ++i, ++scm)
 376         continue;
 377       ++next_free;
 378       if (next_free == CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu))
 379         next_free = 0;
 380     }
 381
 382   /* At this point SCM points to the hash table entry to use.
 383      Now make sure there's room in the cache.  */
 384
 385   {
 386     int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu)));
 387     int elms_used = (((char *) CPU_SCACHE_NEXT_FREE (cpu)
 388                       - (char *) CPU_SCACHE_CACHE (cpu))
 389                      / elm_size);
 390     int elms_left = CPU_SCACHE_SIZE (cpu) - elms_used;
 391
 392     if (elms_left < n)
 393       {
 394         PROFILE_COUNT_SCACHE_FULL_FLUSH (cpu);
 395         scache_flush_cpu (cpu);
 396       }
 397   }
 398
 399   sc = CPU_SCACHE_NEXT_FREE (cpu);
 400   scm->pc = pc;
 401   scm->sc = sc;
 402
 403   *bufp = sc;
 404   return NULL;
 405 }
 406
 407 #endif /* WITH_SCACHE_PBB */
 408
 409 /* Print cache access statics for CPU.  */
 410
 411 void
 412 scache_print_profile (SIM_CPU *cpu, int verbose)
 413 {
 414   SIM_DESC sd = CPU_STATE (cpu);
 415   unsigned long hits = CPU_SCACHE_HITS (cpu);
 416   unsigned long misses = CPU_SCACHE_MISSES (cpu);
 417   char buf[20];
 418   unsigned long max_val;
 419   unsigned long *lengths;
 420   int i;
 421
 422   if (CPU_SCACHE_SIZE (cpu) == 0)
 423     return;
 424
 425   sim_io_printf (sd, "Simulator Cache Statistics\n\n");
 426
 427   /* One could use PROFILE_LABEL_WIDTH here.  I chose not to.  */
 428   sim_io_printf (sd, "  Cache size: %s\n",
 429                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_SIZE (cpu)));
 430   sim_io_printf (sd, "  Hits:       %s\n",
 431                  sim_add_commas (buf, sizeof (buf), hits));
 432   sim_io_printf (sd, "  Misses:     %s\n",
 433                  sim_add_commas (buf, sizeof (buf), misses));
 434   if (hits + misses != 0)
 435     sim_io_printf (sd, "  Hit rate:   %.2f%%\n",
 436                    ((double) hits / ((double) hits + (double) misses)) * 100);
 437
 438 #if WITH_SCACHE_PBB
 439   sim_io_printf (sd, "\n");
 440   sim_io_printf (sd, "  Hash table size:       %s\n",
 441                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAINS (cpu)));
 442   sim_io_printf (sd, "  Max hash list length:  %s\n",
 443                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu)));
 444   sim_io_printf (sd, "  Max insn chain length: %s\n",
 445                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_MAX_CHAIN_LENGTH (cpu)));
 446   sim_io_printf (sd, "  Cache full flushes:    %s\n",
 447                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_FULL_FLUSHES (cpu)));
 448   sim_io_printf (sd, "\n");
 449
 450   if (verbose)
 451     {
 452       sim_io_printf (sd, "  Insn chain lengths:\n\n");
 453       max_val = 0;
 454       lengths = CPU_SCACHE_CHAIN_LENGTHS (cpu);
 455       for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i)
 456         if (lengths[i] > max_val)
 457           max_val = lengths[i];
 458       for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i)
 459         {
 460           sim_io_printf (sd, "  %2d: %*s: ",
 461                          i,
 462                          max_val < 10000 ? 5 : 10,
 463                          sim_add_commas (buf, sizeof (buf), lengths[i]));
 464           sim_profile_print_bar (sd, PROFILE_HISTOGRAM_WIDTH,
 465                                  lengths[i], max_val);
 466           sim_io_printf (sd, "\n");
 467         }
 468       sim_io_printf (sd, "\n");
 469     }
 470 #endif /* WITH_SCACHE_PBB */
 471 }