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   /* FIXME: hash computation is wrong, doesn't take into account
 317      NUM_HASH_CHAIN_ENTRIES.  A lot of the hash table will be unused!  */
 318   unsigned int slot = HASH_PC (pc) & (CPU_SCACHE_NUM_HASH_CHAINS (cpu) - 1);
 319   int i, max_i = CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu);
 320   SCACHE_MAP *scm;
 321
 322   /* We don't update hit/miss statistics as this is only used when recording
 323      branch target addresses.  */
 324
 325   scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot];
 326   for (i = 0; i < max_i && scm->pc != UNUSED_ADDR; ++i, ++scm)
 327     {
 328       if (scm->pc == pc)
 329         return scm->sc;
 330     }
 331   return 0;
 332 }
 333
 334 /* Look up PC and if not found create an entry for it.
 335    If found the result is a pointer to the SCACHE entry.
 336    If not found the result is NULL, and the address of a buffer of at least
 337    N entries is stored in BUFP.
 338    It's done this way so the caller can still distinguish found/not-found.
 339    If the table is full, it is emptied to make room.
 340    If the maximum length of a hash list is reached a random entry is thrown out
 341    to make room.
 342    ??? One might want to try to make this smarter, but let's see some
 343    measurable benefit first.  */
 344
 345 SCACHE *
 346 scache_lookup_or_alloc (SIM_CPU *cpu, IADDR pc, int n, SCACHE **bufp)
 347 {
 348   /* FIXME: hash computation is wrong, doesn't take into account
 349      NUM_HASH_CHAIN_ENTRIES.  A lot of the hash table will be unused!  */
 350   unsigned int slot = HASH_PC (pc) & (CPU_SCACHE_NUM_HASH_CHAINS (cpu) - 1);
 351   int i, max_i = CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu);
 352   SCACHE_MAP *scm;
 353   SCACHE *sc;
 354
 355   scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot];
 356   for (i = 0; i < max_i && scm->pc != UNUSED_ADDR; ++i, ++scm)
 357     {
 358       if (scm->pc == pc)
 359         {
 360           PROFILE_COUNT_SCACHE_HIT (cpu);
 361           return scm->sc;
 362         }
 363     }
 364   PROFILE_COUNT_SCACHE_MISS (cpu);
 365
 366   /* The address we want isn't cached.  Bummer.
 367      If the hash chain we have for this address is full, throw out an entry
 368      to make room.  */
 369
 370   if (i == max_i)
 371     {
 372       /* Rather than do something sophisticated like LRU, we just throw out
 373          a semi-random entry.  Let someone else have the joy of saying how
 374          wrong this is.  NEXT_FREE is the entry to throw out and cycles
 375          through all possibilities.  */
 376       static int next_free = 0;
 377
 378       scm = & CPU_SCACHE_HASH_TABLE (cpu) [slot];
 379       /* FIXME: This seems rather clumsy.  */
 380       for (i = 0; i < next_free; ++i, ++scm)
 381         continue;
 382       ++next_free;
 383       if (next_free == CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu))
 384         next_free = 0;
 385     }
 386
 387   /* At this point SCM points to the hash table entry to use.
 388      Now make sure there's room in the cache.  */
 389   /* FIXME: Kinda weird to use a next_free adjusted scm when cache is
 390      flushed.  */
 391
 392   {
 393     int elm_size = IMP_PROPS_SCACHE_ELM_SIZE (MACH_IMP_PROPS (CPU_MACH (cpu)));
 394     int elms_used = (((char *) CPU_SCACHE_NEXT_FREE (cpu)
 395                       - (char *) CPU_SCACHE_CACHE (cpu))
 396                      / elm_size);
 397     int elms_left = CPU_SCACHE_SIZE (cpu) - elms_used;
 398
 399     if (elms_left < n)
 400       {
 401         PROFILE_COUNT_SCACHE_FULL_FLUSH (cpu);
 402         scache_flush_cpu (cpu);
 403       }
 404   }
 405
 406   sc = CPU_SCACHE_NEXT_FREE (cpu);
 407   scm->pc = pc;
 408   scm->sc = sc;
 409
 410   *bufp = sc;
 411   return NULL;
 412 }
 413
 414 #endif /* WITH_SCACHE_PBB */
 415
 416 /* Print cache access statics for CPU.  */
 417
 418 void
 419 scache_print_profile (SIM_CPU *cpu, int verbose)
 420 {
 421   SIM_DESC sd = CPU_STATE (cpu);
 422   unsigned long hits = CPU_SCACHE_HITS (cpu);
 423   unsigned long misses = CPU_SCACHE_MISSES (cpu);
 424   char buf[20];
 425   unsigned long max_val;
 426   unsigned long *lengths;
 427   int i;
 428
 429   if (CPU_SCACHE_SIZE (cpu) == 0)
 430     return;
 431
 432   sim_io_printf (sd, "Simulator Cache Statistics\n\n");
 433
 434   /* One could use PROFILE_LABEL_WIDTH here.  I chose not to.  */
 435   sim_io_printf (sd, "  Cache size: %s\n",
 436                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_SIZE (cpu)));
 437   sim_io_printf (sd, "  Hits:       %s\n",
 438                  sim_add_commas (buf, sizeof (buf), hits));
 439   sim_io_printf (sd, "  Misses:     %s\n",
 440                  sim_add_commas (buf, sizeof (buf), misses));
 441   if (hits + misses != 0)
 442     sim_io_printf (sd, "  Hit rate:   %.2f%%\n",
 443                    ((double) hits / ((double) hits + (double) misses)) * 100);
 444
 445 #if WITH_SCACHE_PBB
 446   sim_io_printf (sd, "\n");
 447   sim_io_printf (sd, "  Hash table size:       %s\n",
 448                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAINS (cpu)));
 449   sim_io_printf (sd, "  Max hash list length:  %s\n",
 450                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_NUM_HASH_CHAIN_ENTRIES (cpu)));
 451   sim_io_printf (sd, "  Max insn chain length: %s\n",
 452                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_MAX_CHAIN_LENGTH (cpu)));
 453   sim_io_printf (sd, "  Cache full flushes:    %s\n",
 454                  sim_add_commas (buf, sizeof (buf), CPU_SCACHE_FULL_FLUSHES (cpu)));
 455   sim_io_printf (sd, "\n");
 456
 457   if (verbose)
 458     {
 459       sim_io_printf (sd, "  Insn chain lengths:\n\n");
 460       max_val = 0;
 461       lengths = CPU_SCACHE_CHAIN_LENGTHS (cpu);
 462       for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i)
 463         if (lengths[i] > max_val)
 464           max_val = lengths[i];
 465       for (i = 1; i < CPU_SCACHE_MAX_CHAIN_LENGTH (cpu); ++i)
 466         {
 467           sim_io_printf (sd, "  %2d: %*s: ",
 468                          i,
 469                          max_val < 10000 ? 5 : 10,
 470                          sim_add_commas (buf, sizeof (buf), lengths[i]));
 471           sim_profile_print_bar (sd, PROFILE_HISTOGRAM_WIDTH,
 472                                  lengths[i], max_val);
 473           sim_io_printf (sd, "\n");
 474         }
 475       sim_io_printf (sd, "\n");
 476     }
 477 #endif /* WITH_SCACHE_PBB */
 478 }