gcc/cselib.c

   1 /* Common subexpression elimination library for GNU compiler.
   2    Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "regs.h"
  30 #include "hard-reg-set.h"
  31 #include "flags.h"
  32 #include "real.h"
  33 #include "insn-config.h"
  34 #include "recog.h"
  35 #include "function.h"
  36 #include "expr.h"
  37 #include "toplev.h"
  38 #include "output.h"
  39 #include "ggc.h"
  40 #include "hashtab.h"
  41 #include "cselib.h"
  42 #include "params.h"
  43 #include "alloc-pool.h"
  44
  45 static int entry_and_rtx_equal_p (const void *, const void *);
  46 static hashval_t get_value_hash (const void *);
  47 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
  48 static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
  49 static void unchain_one_value (cselib_val *);
  50 static void unchain_one_elt_list (struct elt_list **);
  51 static void unchain_one_elt_loc_list (struct elt_loc_list **);
  52 static void clear_table (void);
  53 static int discard_useless_locs (void **, void *);
  54 static int discard_useless_values (void **, void *);
  55 static void remove_useless_values (void);
  56 static rtx wrap_constant (enum machine_mode, rtx);
  57 static unsigned int hash_rtx (rtx, enum machine_mode, int);
  58 static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
  59 static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
  60 static cselib_val *cselib_lookup_mem (rtx, int);
  61 static void cselib_invalidate_regno (unsigned int, enum machine_mode);
  62 static void cselib_invalidate_mem (rtx);
  63 static void cselib_invalidate_rtx (rtx, rtx, void *);
  64 static void cselib_record_set (rtx, cselib_val *, cselib_val *);
  65 static void cselib_record_sets (rtx);
  66
  67 /* There are three ways in which cselib can look up an rtx:
  68    - for a REG, the reg_values table (which is indexed by regno) is used
  69    - for a MEM, we recursively look up its address and then follow the
  70      addr_list of that value
  71    - for everything else, we compute a hash value and go through the hash
  72      table.  Since different rtx's can still have the same hash value,
  73      this involves walking the table entries for a given value and comparing
  74      the locations of the entries with the rtx we are looking up.  */
  75
  76 /* A table that enables us to look up elts by their value.  */
  77 static GTY((param_is (cselib_val))) htab_t hash_table;
  78
  79 /* This is a global so we don't have to pass this through every function.
  80    It is used in new_elt_loc_list to set SETTING_INSN.  */
  81 static rtx cselib_current_insn;
  82 static bool cselib_current_insn_in_libcall;
  83
  84 /* Every new unknown value gets a unique number.  */
  85 static unsigned int next_unknown_value;
  86
  87 /* The number of registers we had when the varrays were last resized.  */
  88 static unsigned int cselib_nregs;
  89
  90 /* Count values without known locations.  Whenever this grows too big, we
  91    remove these useless values from the table.  */
  92 static int n_useless_values;
  93
  94 /* Number of useless values before we remove them from the hash table.  */
  95 #define MAX_USELESS_VALUES 32
  96
  97 /* This table maps from register number to values.  It does not
  98    contain pointers to cselib_val structures, but rather elt_lists.
  99    The purpose is to be able to refer to the same register in
 100    different modes.  The first element of the list defines the mode in
 101    which the register was set; if the mode is unknown or the value is
 102    no longer valid in that mode, ELT will be NULL for the first
 103    element.  */
 104 static GTY(()) varray_type reg_values;
 105 static GTY((deletable (""))) varray_type reg_values_old;
 106 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
 107
 108 /* The largest number of hard regs used by any entry added to the
 109    REG_VALUES table.  Cleared on each clear_table() invocation.  */
 110 static unsigned int max_value_regs;
 111
 112 /* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
 113    in clear_table() for fast emptying.  */
 114 static GTY(()) varray_type used_regs;
 115 static GTY((deletable (""))) varray_type used_regs_old;
 116
 117 /* We pass this to cselib_invalidate_mem to invalidate all of
 118    memory for a non-const call instruction.  */
 119 static GTY(()) rtx callmem;
 120
 121 /* Set by discard_useless_locs if it deleted the last location of any
 122    value.  */
 123 static int values_became_useless;
 124
 125 /* Used as stop element of the containing_mem list so we can check
 126    presence in the list by checking the next pointer.  */
 127 static cselib_val dummy_val;
 128
 129 /* Used to list all values that contain memory reference.
 130    May or may not contain the useless values - the list is compacted
 131    each time memory is invalidated.  */
 132 static cselib_val *first_containing_mem = &dummy_val;
 133 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool;
 134 \f
 135
 136 /* Allocate a struct elt_list and fill in its two elements with the
 137    arguments.  */
 138
 139 static inline struct elt_list *
 140 new_elt_list (struct elt_list *next, cselib_val *elt)
 141 {
 142   struct elt_list *el;
 143   el = pool_alloc (elt_list_pool);
 144   el->next = next;
 145   el->elt = elt;
 146   return el;
 147 }
 148
 149 /* Allocate a struct elt_loc_list and fill in its two elements with the
 150    arguments.  */
 151
 152 static inline struct elt_loc_list *
 153 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
 154 {
 155   struct elt_loc_list *el;
 156   el = pool_alloc (elt_loc_list_pool);
 157   el->next = next;
 158   el->loc = loc;
 159   el->canon_loc = NULL;
 160   el->setting_insn = cselib_current_insn;
 161   el->in_libcall = cselib_current_insn_in_libcall;
 162   return el;
 163 }
 164
 165 /* The elt_list at *PL is no longer needed.  Unchain it and free its
 166    storage.  */
 167
 168 static inline void
 169 unchain_one_elt_list (struct elt_list **pl)
 170 {
 171   struct elt_list *l = *pl;
 172
 173   *pl = l->next;
 174   pool_free (elt_list_pool, l);
 175 }
 176
 177 /* Likewise for elt_loc_lists.  */
 178
 179 static void
 180 unchain_one_elt_loc_list (struct elt_loc_list **pl)
 181 {
 182   struct elt_loc_list *l = *pl;
 183
 184   *pl = l->next;
 185   pool_free (elt_loc_list_pool, l);
 186 }
 187
 188 /* Likewise for cselib_vals.  This also frees the addr_list associated with
 189    V.  */
 190
 191 static void
 192 unchain_one_value (cselib_val *v)
 193 {
 194   while (v->addr_list)
 195     unchain_one_elt_list (&v->addr_list);
 196
 197   pool_free (cselib_val_pool, v);
 198 }
 199
 200 /* Remove all entries from the hash table.  Also used during
 201    initialization.  If CLEAR_ALL isn't set, then only clear the entries
 202    which are known to have been used.  */
 203
 204 static void
 205 clear_table (void)
 206 {
 207   unsigned int i;
 208
 209   for (i = 0; i < VARRAY_ACTIVE_SIZE (used_regs); i++)
 210     REG_VALUES (VARRAY_UINT (used_regs, i)) = 0;
 211
 212   max_value_regs = 0;
 213
 214   VARRAY_POP_ALL (used_regs);
 215
 216   htab_empty (hash_table);
 217
 218   n_useless_values = 0;
 219
 220   next_unknown_value = 0;
 221
 222   first_containing_mem = &dummy_val;
 223 }
 224
 225 /* The equality test for our hash table.  The first argument ENTRY is a table
 226    element (i.e. a cselib_val), while the second arg X is an rtx.  We know
 227    that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
 228    CONST of an appropriate mode.  */
 229
 230 static int
 231 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
 232 {
 233   struct elt_loc_list *l;
 234   const cselib_val *v = (const cselib_val *) entry;
 235   rtx x = (rtx) x_arg;
 236   enum machine_mode mode = GET_MODE (x);
 237
 238   if (GET_CODE (x) == CONST_INT
 239       || (mode == VOIDmode && GET_CODE (x) == CONST_DOUBLE))
 240     abort ();
 241   if (mode != GET_MODE (v->u.val_rtx))
 242     return 0;
 243
 244   /* Unwrap X if necessary.  */
 245   if (GET_CODE (x) == CONST
 246       && (GET_CODE (XEXP (x, 0)) == CONST_INT
 247           || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
 248     x = XEXP (x, 0);
 249
 250   /* We don't guarantee that distinct rtx's have different hash values,
 251      so we need to do a comparison.  */
 252   for (l = v->locs; l; l = l->next)
 253     if (rtx_equal_for_cselib_p (l->loc, x))
 254       return 1;
 255
 256   return 0;
 257 }
 258
 259 /* The hash function for our hash table.  The value is always computed with
 260    hash_rtx when adding an element; this function just extracts the hash
 261    value from a cselib_val structure.  */
 262
 263 static hashval_t
 264 get_value_hash (const void *entry)
 265 {
 266   const cselib_val *v = (const cselib_val *) entry;
 267   return v->value;
 268 }
 269
 270 /* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
 271    only return true for values which point to a cselib_val whose value
 272    element has been set to zero, which implies the cselib_val will be
 273    removed.  */
 274
 275 int
 276 references_value_p (rtx x, int only_useless)
 277 {
 278   enum rtx_code code = GET_CODE (x);
 279   const char *fmt = GET_RTX_FORMAT (code);
 280   int i, j;
 281
 282   if (GET_CODE (x) == VALUE
 283       && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
 284     return 1;
 285
 286   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 287     {
 288       if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
 289         return 1;
 290       else if (fmt[i] == 'E')
 291         for (j = 0; j < XVECLEN (x, i); j++)
 292           if (references_value_p (XVECEXP (x, i, j), only_useless))
 293             return 1;
 294     }
 295
 296   return 0;
 297 }
 298
 299 /* For all locations found in X, delete locations that reference useless
 300    values (i.e. values without any location).  Called through
 301    htab_traverse.  */
 302
 303 static int
 304 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
 305 {
 306   cselib_val *v = (cselib_val *)*x;
 307   struct elt_loc_list **p = &v->locs;
 308   int had_locs = v->locs != 0;
 309
 310   while (*p)
 311     {
 312       if (references_value_p ((*p)->loc, 1))
 313         unchain_one_elt_loc_list (p);
 314       else
 315         p = &(*p)->next;
 316     }
 317
 318   if (had_locs && v->locs == 0)
 319     {
 320       n_useless_values++;
 321       values_became_useless = 1;
 322     }
 323   return 1;
 324 }
 325
 326 /* If X is a value with no locations, remove it from the hashtable.  */
 327
 328 static int
 329 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
 330 {
 331   cselib_val *v = (cselib_val *)*x;
 332
 333   if (v->locs == 0)
 334     {
 335       htab_clear_slot (hash_table, x);
 336       unchain_one_value (v);
 337       n_useless_values--;
 338     }
 339
 340   return 1;
 341 }
 342
 343 /* Clean out useless values (i.e. those which no longer have locations
 344    associated with them) from the hash table.  */
 345
 346 static void
 347 remove_useless_values (void)
 348 {
 349   cselib_val **p, *v;
 350   /* First pass: eliminate locations that reference the value.  That in
 351      turn can make more values useless.  */
 352   do
 353     {
 354       values_became_useless = 0;
 355       htab_traverse (hash_table, discard_useless_locs, 0);
 356     }
 357   while (values_became_useless);
 358
 359   /* Second pass: actually remove the values.  */
 360   htab_traverse (hash_table, discard_useless_values, 0);
 361
 362   p = &first_containing_mem;
 363   for (v = *p; v != &dummy_val; v = v->next_containing_mem)
 364     if (v->locs)
 365       {
 366         *p = v;
 367         p = &(*p)->next_containing_mem;
 368       }
 369   *p = &dummy_val;
 370
 371   if (n_useless_values != 0)
 372     abort ();
 373 }
 374
 375 /* Return the mode in which a register was last set.  If X is not a
 376    register, return its mode.  If the mode in which the register was
 377    set is not known, or the value was already clobbered, return
 378    VOIDmode.  */
 379
 380 enum machine_mode
 381 cselib_reg_set_mode (rtx x)
 382 {
 383   if (GET_CODE (x) != REG)
 384     return GET_MODE (x);
 385
 386   if (REG_VALUES (REGNO (x)) == NULL
 387       || REG_VALUES (REGNO (x))->elt == NULL)
 388     return VOIDmode;
 389
 390   return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx);
 391 }
 392
 393 /* Return nonzero if we can prove that X and Y contain the same value, taking
 394    our gathered information into account.  */
 395
 396 int
 397 rtx_equal_for_cselib_p (rtx x, rtx y)
 398 {
 399   enum rtx_code code;
 400   const char *fmt;
 401   int i;
 402
 403   if (GET_CODE (x) == REG || GET_CODE (x) == MEM)
 404     {
 405       cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
 406
 407       if (e)
 408         x = e->u.val_rtx;
 409     }
 410
 411   if (GET_CODE (y) == REG || GET_CODE (y) == MEM)
 412     {
 413       cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
 414
 415       if (e)
 416         y = e->u.val_rtx;
 417     }
 418
 419   if (x == y)
 420     return 1;
 421
 422   if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
 423     return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
 424
 425   if (GET_CODE (x) == VALUE)
 426     {
 427       cselib_val *e = CSELIB_VAL_PTR (x);
 428       struct elt_loc_list *l;
 429
 430       for (l = e->locs; l; l = l->next)
 431         {
 432           rtx t = l->loc;
 433
 434           /* Avoid infinite recursion.  */
 435           if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
 436             continue;
 437           else if (rtx_equal_for_cselib_p (t, y))
 438             return 1;
 439         }
 440
 441       return 0;
 442     }
 443
 444   if (GET_CODE (y) == VALUE)
 445     {
 446       cselib_val *e = CSELIB_VAL_PTR (y);
 447       struct elt_loc_list *l;
 448
 449       for (l = e->locs; l; l = l->next)
 450         {
 451           rtx t = l->loc;
 452
 453           if (GET_CODE (t) == REG || GET_CODE (t) == MEM)
 454             continue;
 455           else if (rtx_equal_for_cselib_p (x, t))
 456             return 1;
 457         }
 458
 459       return 0;
 460     }
 461
 462   if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
 463     return 0;
 464
 465   /* This won't be handled correctly by the code below.  */
 466   if (GET_CODE (x) == LABEL_REF)
 467     return XEXP (x, 0) == XEXP (y, 0);
 468
 469   code = GET_CODE (x);
 470   fmt = GET_RTX_FORMAT (code);
 471
 472   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 473     {
 474       int j;
 475
 476       switch (fmt[i])
 477         {
 478         case 'w':
 479           if (XWINT (x, i) != XWINT (y, i))
 480             return 0;
 481           break;
 482
 483         case 'n':
 484         case 'i':
 485           if (XINT (x, i) != XINT (y, i))
 486             return 0;
 487           break;
 488
 489         case 'V':
 490         case 'E':
 491           /* Two vectors must have the same length.  */
 492           if (XVECLEN (x, i) != XVECLEN (y, i))
 493             return 0;
 494
 495           /* And the corresponding elements must match.  */
 496           for (j = 0; j < XVECLEN (x, i); j++)
 497             if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
 498                                           XVECEXP (y, i, j)))
 499               return 0;
 500           break;
 501
 502         case 'e':
 503           if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
 504             return 0;
 505           break;
 506
 507         case 'S':
 508         case 's':
 509           if (strcmp (XSTR (x, i), XSTR (y, i)))
 510             return 0;
 511           break;
 512
 513         case 'u':
 514           /* These are just backpointers, so they don't matter.  */
 515           break;
 516
 517         case '0':
 518         case 't':
 519           break;
 520
 521           /* It is believed that rtx's at this level will never
 522              contain anything but integers and other rtx's,
 523              except for within LABEL_REFs and SYMBOL_REFs.  */
 524         default:
 525           abort ();
 526         }
 527     }
 528   return 1;
 529 }
 530
 531 /* We need to pass down the mode of constants through the hash table
 532    functions.  For that purpose, wrap them in a CONST of the appropriate
 533    mode.  */
 534 static rtx
 535 wrap_constant (enum machine_mode mode, rtx x)
 536 {
 537   if (GET_CODE (x) != CONST_INT
 538       && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
 539     return x;
 540   if (mode == VOIDmode)
 541     abort ();
 542   return gen_rtx_CONST (mode, x);
 543 }
 544
 545 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
 546    For registers and memory locations, we look up their cselib_val structure
 547    and return its VALUE element.
 548    Possible reasons for return 0 are: the object is volatile, or we couldn't
 549    find a register or memory location in the table and CREATE is zero.  If
 550    CREATE is nonzero, table elts are created for regs and mem.
 551    MODE is used in hashing for CONST_INTs only;
 552    otherwise the mode of X is used.  */
 553
 554 static unsigned int
 555 hash_rtx (rtx x, enum machine_mode mode, int create)
 556 {
 557   cselib_val *e;
 558   int i, j;
 559   enum rtx_code code;
 560   const char *fmt;
 561   unsigned int hash = 0;
 562
 563   code = GET_CODE (x);
 564   hash += (unsigned) code + (unsigned) GET_MODE (x);
 565
 566   switch (code)
 567     {
 568     case MEM:
 569     case REG:
 570       e = cselib_lookup (x, GET_MODE (x), create);
 571       if (! e)
 572         return 0;
 573
 574       return e->value;
 575
 576     case CONST_INT:
 577       hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
 578       return hash ? hash : (unsigned int) CONST_INT;
 579
 580     case CONST_DOUBLE:
 581       /* This is like the general case, except that it only counts
 582          the integers representing the constant.  */
 583       hash += (unsigned) code + (unsigned) GET_MODE (x);
 584       if (GET_MODE (x) != VOIDmode)
 585         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
 586       else
 587         hash += ((unsigned) CONST_DOUBLE_LOW (x)
 588                  + (unsigned) CONST_DOUBLE_HIGH (x));
 589       return hash ? hash : (unsigned int) CONST_DOUBLE;
 590
 591     case CONST_VECTOR:
 592       {
 593         int units;
 594         rtx elt;
 595
 596         units = CONST_VECTOR_NUNITS (x);
 597
 598         for (i = 0; i < units; ++i)
 599           {
 600             elt = CONST_VECTOR_ELT (x, i);
 601             hash += hash_rtx (elt, GET_MODE (elt), 0);
 602           }
 603
 604         return hash;
 605       }
 606
 607       /* Assume there is only one rtx object for any given label.  */
 608     case LABEL_REF:
 609       hash
 610         += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
 611       return hash ? hash : (unsigned int) LABEL_REF;
 612
 613     case SYMBOL_REF:
 614       hash
 615         += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
 616       return hash ? hash : (unsigned int) SYMBOL_REF;
 617
 618     case PRE_DEC:
 619     case PRE_INC:
 620     case POST_DEC:
 621     case POST_INC:
 622     case POST_MODIFY:
 623     case PRE_MODIFY:
 624     case PC:
 625     case CC0:
 626     case CALL:
 627     case UNSPEC_VOLATILE:
 628       return 0;
 629
 630     case ASM_OPERANDS:
 631       if (MEM_VOLATILE_P (x))
 632         return 0;
 633
 634       break;
 635
 636     default:
 637       break;
 638     }
 639
 640   i = GET_RTX_LENGTH (code) - 1;
 641   fmt = GET_RTX_FORMAT (code);
 642   for (; i >= 0; i--)
 643     {
 644       if (fmt[i] == 'e')
 645         {
 646           rtx tem = XEXP (x, i);
 647           unsigned int tem_hash = hash_rtx (tem, 0, create);
 648
 649           if (tem_hash == 0)
 650             return 0;
 651
 652           hash += tem_hash;
 653         }
 654       else if (fmt[i] == 'E')
 655         for (j = 0; j < XVECLEN (x, i); j++)
 656           {
 657             unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
 658
 659             if (tem_hash == 0)
 660               return 0;
 661
 662             hash += tem_hash;
 663           }
 664       else if (fmt[i] == 's')
 665         {
 666           const unsigned char *p = (const unsigned char *) XSTR (x, i);
 667
 668           if (p)
 669             while (*p)
 670               hash += *p++;
 671         }
 672       else if (fmt[i] == 'i')
 673         hash += XINT (x, i);
 674       else if (fmt[i] == '0' || fmt[i] == 't')
 675         /* unused */;
 676       else
 677         abort ();
 678     }
 679
 680   return hash ? hash : 1 + (unsigned int) GET_CODE (x);
 681 }
 682
 683 /* Create a new value structure for VALUE and initialize it.  The mode of the
 684    value is MODE.  */
 685
 686 static inline cselib_val *
 687 new_cselib_val (unsigned int value, enum machine_mode mode)
 688 {
 689   cselib_val *e = pool_alloc (cselib_val_pool);
 690
 691 #ifdef ENABLE_CHECKING
 692   if (value == 0)
 693     abort ();
 694 #endif
 695
 696   e->value = value;
 697   e->u.val_rtx = gen_rtx_VALUE (mode);
 698   CSELIB_VAL_PTR (e->u.val_rtx) = e;
 699   e->addr_list = 0;
 700   e->locs = 0;
 701   e->next_containing_mem = 0;
 702   return e;
 703 }
 704
 705 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
 706    contains the data at this address.  X is a MEM that represents the
 707    value.  Update the two value structures to represent this situation.  */
 708
 709 static void
 710 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
 711 {
 712   struct elt_loc_list *l;
 713
 714   /* Avoid duplicates.  */
 715   for (l = mem_elt->locs; l; l = l->next)
 716     if (GET_CODE (l->loc) == MEM
 717         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
 718       return;
 719
 720   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
 721   mem_elt->locs
 722     = new_elt_loc_list (mem_elt->locs,
 723                         replace_equiv_address_nv (x, addr_elt->u.val_rtx));
 724   if (mem_elt->next_containing_mem == NULL)
 725     {
 726       mem_elt->next_containing_mem = first_containing_mem;
 727       first_containing_mem = mem_elt;
 728     }
 729 }
 730
 731 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
 732    If CREATE, make a new one if we haven't seen it before.  */
 733
 734 static cselib_val *
 735 cselib_lookup_mem (rtx x, int create)
 736 {
 737   enum machine_mode mode = GET_MODE (x);
 738   void **slot;
 739   cselib_val *addr;
 740   cselib_val *mem_elt;
 741   struct elt_list *l;
 742
 743   if (MEM_VOLATILE_P (x) || mode == BLKmode
 744       || (FLOAT_MODE_P (mode) && flag_float_store))
 745     return 0;
 746
 747   /* Look up the value for the address.  */
 748   addr = cselib_lookup (XEXP (x, 0), mode, create);
 749   if (! addr)
 750     return 0;
 751
 752   /* Find a value that describes a value of our mode at that address.  */
 753   for (l = addr->addr_list; l; l = l->next)
 754     if (GET_MODE (l->elt->u.val_rtx) == mode)
 755       return l->elt;
 756
 757   if (! create)
 758     return 0;
 759
 760   mem_elt = new_cselib_val (++next_unknown_value, mode);
 761   add_mem_for_addr (addr, mem_elt, x);
 762   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
 763                                    mem_elt->value, INSERT);
 764   *slot = mem_elt;
 765   return mem_elt;
 766 }
 767
 768 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
 769    with VALUE expressions.  This way, it becomes independent of changes
 770    to registers and memory.
 771    X isn't actually modified; if modifications are needed, new rtl is
 772    allocated.  However, the return value can share rtl with X.  */
 773
 774 rtx
 775 cselib_subst_to_values (rtx x)
 776 {
 777   enum rtx_code code = GET_CODE (x);
 778   const char *fmt = GET_RTX_FORMAT (code);
 779   cselib_val *e;
 780   struct elt_list *l;
 781   rtx copy = x;
 782   int i;
 783
 784   switch (code)
 785     {
 786     case REG:
 787       l = REG_VALUES (REGNO (x));
 788       if (l && l->elt == NULL)
 789         l = l->next;
 790       for (; l; l = l->next)
 791         if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
 792           return l->elt->u.val_rtx;
 793
 794       abort ();
 795
 796     case MEM:
 797       e = cselib_lookup_mem (x, 0);
 798       if (! e)
 799         {
 800           /* This happens for autoincrements.  Assign a value that doesn't
 801              match any other.  */
 802           e = new_cselib_val (++next_unknown_value, GET_MODE (x));
 803         }
 804       return e->u.val_rtx;
 805
 806     case CONST_DOUBLE:
 807     case CONST_VECTOR:
 808     case CONST_INT:
 809       return x;
 810
 811     case POST_INC:
 812     case PRE_INC:
 813     case POST_DEC:
 814     case PRE_DEC:
 815     case POST_MODIFY:
 816     case PRE_MODIFY:
 817       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
 818       return e->u.val_rtx;
 819
 820     default:
 821       break;
 822     }
 823
 824   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 825     {
 826       if (fmt[i] == 'e')
 827         {
 828           rtx t = cselib_subst_to_values (XEXP (x, i));
 829
 830           if (t != XEXP (x, i) && x == copy)
 831             copy = shallow_copy_rtx (x);
 832
 833           XEXP (copy, i) = t;
 834         }
 835       else if (fmt[i] == 'E')
 836         {
 837           int j, k;
 838
 839           for (j = 0; j < XVECLEN (x, i); j++)
 840             {
 841               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
 842
 843               if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
 844                 {
 845                   if (x == copy)
 846                     copy = shallow_copy_rtx (x);
 847
 848                   XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
 849                   for (k = 0; k < j; k++)
 850                     XVECEXP (copy, i, k) = XVECEXP (x, i, k);
 851                 }
 852
 853               XVECEXP (copy, i, j) = t;
 854             }
 855         }
 856     }
 857
 858   return copy;
 859 }
 860
 861 /* Look up the rtl expression X in our tables and return the value it has.
 862    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
 863    we create a new one if possible, using mode MODE if X doesn't have a mode
 864    (i.e. because it's a constant).  */
 865
 866 cselib_val *
 867 cselib_lookup (rtx x, enum machine_mode mode, int create)
 868 {
 869   void **slot;
 870   cselib_val *e;
 871   unsigned int hashval;
 872
 873   if (GET_MODE (x) != VOIDmode)
 874     mode = GET_MODE (x);
 875
 876   if (GET_CODE (x) == VALUE)
 877     return CSELIB_VAL_PTR (x);
 878
 879   if (GET_CODE (x) == REG)
 880     {
 881       struct elt_list *l;
 882       unsigned int i = REGNO (x);
 883
 884       l = REG_VALUES (i);
 885       if (l && l->elt == NULL)
 886         l = l->next;
 887       for (; l; l = l->next)
 888         if (mode == GET_MODE (l->elt->u.val_rtx))
 889           return l->elt;
 890
 891       if (! create)
 892         return 0;
 893
 894       if (i < FIRST_PSEUDO_REGISTER)
 895         {
 896           unsigned int n = HARD_REGNO_NREGS (i, mode);
 897
 898           if (n > max_value_regs)
 899             max_value_regs = n;
 900         }
 901
 902       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
 903       e->locs = new_elt_loc_list (e->locs, x);
 904       if (REG_VALUES (i) == 0)
 905         {
 906           /* Maintain the invariant that the first entry of
 907              REG_VALUES, if present, must be the value used to set the
 908              register, or NULL.  */
 909           VARRAY_PUSH_UINT (used_regs, i);
 910           REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
 911         }
 912       REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
 913       slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
 914       *slot = e;
 915       return e;
 916     }
 917
 918   if (GET_CODE (x) == MEM)
 919     return cselib_lookup_mem (x, create);
 920
 921   hashval = hash_rtx (x, mode, create);
 922   /* Can't even create if hashing is not possible.  */
 923   if (! hashval)
 924     return 0;
 925
 926   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
 927                                    hashval, create ? INSERT : NO_INSERT);
 928   if (slot == 0)
 929     return 0;
 930
 931   e = (cselib_val *) *slot;
 932   if (e)
 933     return e;
 934
 935   e = new_cselib_val (hashval, mode);
 936
 937   /* We have to fill the slot before calling cselib_subst_to_values:
 938      the hash table is inconsistent until we do so, and
 939      cselib_subst_to_values will need to do lookups.  */
 940   *slot = (void *) e;
 941   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
 942   return e;
 943 }
 944
 945 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
 946    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
 947    is used to determine how many hard registers are being changed.  If MODE
 948    is VOIDmode, then only REGNO is being changed; this is used when
 949    invalidating call clobbered registers across a call.  */
 950
 951 static void
 952 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
 953 {
 954   unsigned int endregno;
 955   unsigned int i;
 956
 957   /* If we see pseudos after reload, something is _wrong_.  */
 958   if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
 959       && reg_renumber[regno] >= 0)
 960     abort ();
 961
 962   /* Determine the range of registers that must be invalidated.  For
 963      pseudos, only REGNO is affected.  For hard regs, we must take MODE
 964      into account, and we must also invalidate lower register numbers
 965      if they contain values that overlap REGNO.  */
 966   if (regno < FIRST_PSEUDO_REGISTER)
 967     {
 968       if (mode == VOIDmode)
 969         abort ();
 970
 971       if (regno < max_value_regs)
 972         i = 0;
 973       else
 974         i = regno - max_value_regs;
 975
 976       endregno = regno + HARD_REGNO_NREGS (regno, mode);
 977     }
 978   else
 979     {
 980       i = regno;
 981       endregno = regno + 1;
 982     }
 983
 984   for (; i < endregno; i++)
 985     {
 986       struct elt_list **l = &REG_VALUES (i);
 987
 988       /* Go through all known values for this reg; if it overlaps the range
 989          we're invalidating, remove the value.  */
 990       while (*l)
 991         {
 992           cselib_val *v = (*l)->elt;
 993           struct elt_loc_list **p;
 994           unsigned int this_last = i;
 995
 996           if (i < FIRST_PSEUDO_REGISTER && v != NULL)
 997             this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
 998
 999           if (this_last < regno || v == NULL)
1000             {
1001               l = &(*l)->next;
1002               continue;
1003             }
1004
1005           /* We have an overlap.  */
1006           if (*l == REG_VALUES (i))
1007             {
1008               /* Maintain the invariant that the first entry of
1009                  REG_VALUES, if present, must be the value used to set
1010                  the register, or NULL.  This is also nice because
1011                  then we won't push the same regno onto user_regs
1012                  multiple times.  */
1013               (*l)->elt = NULL;
1014               l = &(*l)->next;
1015             }
1016           else
1017             unchain_one_elt_list (l);
1018
1019           /* Now, we clear the mapping from value to reg.  It must exist, so
1020              this code will crash intentionally if it doesn't.  */
1021           for (p = &v->locs; ; p = &(*p)->next)
1022             {
1023               rtx x = (*p)->loc;
1024
1025               if (GET_CODE (x) == REG && REGNO (x) == i)
1026                 {
1027                   unchain_one_elt_loc_list (p);
1028                   break;
1029                 }
1030             }
1031           if (v->locs == 0)
1032             n_useless_values++;
1033         }
1034     }
1035 }
1036 \f
1037 /* Return 1 if X has a value that can vary even between two
1038    executions of the program.  0 means X can be compared reliably
1039    against certain constants or near-constants.  */
1040
1041 static int
1042 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED)
1043 {
1044   /* We actually don't need to verify very hard.  This is because
1045      if X has actually changed, we invalidate the memory anyway,
1046      so assume that all common memory addresses are
1047      invariant.  */
1048   return 0;
1049 }
1050
1051 /* Invalidate any locations in the table which are changed because of a
1052    store to MEM_RTX.  If this is called because of a non-const call
1053    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1054
1055 static void
1056 cselib_invalidate_mem (rtx mem_rtx)
1057 {
1058   cselib_val **vp, *v, *next;
1059   int num_mems = 0;
1060   rtx mem_addr;
1061
1062   mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1063   mem_rtx = canon_rtx (mem_rtx);
1064
1065   vp = &first_containing_mem;
1066   for (v = *vp; v != &dummy_val; v = next)
1067     {
1068       bool has_mem = false;
1069       struct elt_loc_list **p = &v->locs;
1070       int had_locs = v->locs != 0;
1071
1072       while (*p)
1073         {
1074           rtx x = (*p)->loc;
1075           rtx canon_x = (*p)->canon_loc;
1076           cselib_val *addr;
1077           struct elt_list **mem_chain;
1078
1079           /* MEMs may occur in locations only at the top level; below
1080              that every MEM or REG is substituted by its VALUE.  */
1081           if (GET_CODE (x) != MEM)
1082             {
1083               p = &(*p)->next;
1084               continue;
1085             }
1086           if (!canon_x)
1087             canon_x = (*p)->canon_loc = canon_rtx (x);
1088           if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1089               && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1090                                           x, cselib_rtx_varies_p))
1091             {
1092               has_mem = true;
1093               num_mems++;
1094               p = &(*p)->next;
1095               continue;
1096             }
1097
1098           /* This one overlaps.  */
1099           /* We must have a mapping from this MEM's address to the
1100              value (E).  Remove that, too.  */
1101           addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1102           mem_chain = &addr->addr_list;
1103           for (;;)
1104             {
1105               if ((*mem_chain)->elt == v)
1106                 {
1107                   unchain_one_elt_list (mem_chain);
1108                   break;
1109                 }
1110
1111               mem_chain = &(*mem_chain)->next;
1112             }
1113
1114           unchain_one_elt_loc_list (p);
1115         }
1116
1117       if (had_locs && v->locs == 0)
1118         n_useless_values++;
1119
1120       next = v->next_containing_mem;
1121       if (has_mem)
1122         {
1123           *vp = v;
1124           vp = &(*vp)->next_containing_mem;
1125         }
1126       else
1127         v->next_containing_mem = NULL;
1128     }
1129   *vp = &dummy_val;
1130 }
1131
1132 /* Invalidate DEST, which is being assigned to or clobbered.  The second and
1133    the third parameter exist so that this function can be passed to
1134    note_stores; they are ignored.  */
1135
1136 static void
1137 cselib_invalidate_rtx (rtx dest, rtx ignore ATTRIBUTE_UNUSED,
1138                        void *data ATTRIBUTE_UNUSED)
1139 {
1140   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
1141          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
1142     dest = XEXP (dest, 0);
1143
1144   if (GET_CODE (dest) == REG)
1145     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1146   else if (GET_CODE (dest) == MEM)
1147     cselib_invalidate_mem (dest);
1148
1149   /* Some machines don't define AUTO_INC_DEC, but they still use push
1150      instructions.  We need to catch that case here in order to
1151      invalidate the stack pointer correctly.  Note that invalidating
1152      the stack pointer is different from invalidating DEST.  */
1153   if (push_operand (dest, GET_MODE (dest)))
1154     cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
1155 }
1156
1157 /* Record the result of a SET instruction.  DEST is being set; the source
1158    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1159    describes its address.  */
1160
1161 static void
1162 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1163 {
1164   int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
1165
1166   if (src_elt == 0 || side_effects_p (dest))
1167     return;
1168
1169   if (dreg >= 0)
1170     {
1171       if (dreg < FIRST_PSEUDO_REGISTER)
1172         {
1173           unsigned int n = HARD_REGNO_NREGS (dreg, GET_MODE (dest));
1174
1175           if (n > max_value_regs)
1176             max_value_regs = n;
1177         }
1178
1179       if (REG_VALUES (dreg) == 0)
1180         {
1181           VARRAY_PUSH_UINT (used_regs, dreg);
1182           REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1183         }
1184       else
1185         {
1186           if (REG_VALUES (dreg)->elt == 0)
1187             REG_VALUES (dreg)->elt = src_elt;
1188           else
1189             /* The register should have been invalidated.  */
1190             abort ();
1191         }
1192
1193       if (src_elt->locs == 0)
1194         n_useless_values--;
1195       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1196     }
1197   else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
1198     {
1199       if (src_elt->locs == 0)
1200         n_useless_values--;
1201       add_mem_for_addr (dest_addr_elt, src_elt, dest);
1202     }
1203 }
1204
1205 /* Describe a single set that is part of an insn.  */
1206 struct set
1207 {
1208   rtx src;
1209   rtx dest;
1210   cselib_val *src_elt;
1211   cselib_val *dest_addr_elt;
1212 };
1213
1214 /* There is no good way to determine how many elements there can be
1215    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
1216 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1217
1218 /* Record the effects of any sets in INSN.  */
1219 static void
1220 cselib_record_sets (rtx insn)
1221 {
1222   int n_sets = 0;
1223   int i;
1224   struct set sets[MAX_SETS];
1225   rtx body = PATTERN (insn);
1226   rtx cond = 0;
1227
1228   body = PATTERN (insn);
1229   if (GET_CODE (body) == COND_EXEC)
1230     {
1231       cond = COND_EXEC_TEST (body);
1232       body = COND_EXEC_CODE (body);
1233     }
1234
1235   /* Find all sets.  */
1236   if (GET_CODE (body) == SET)
1237     {
1238       sets[0].src = SET_SRC (body);
1239       sets[0].dest = SET_DEST (body);
1240       n_sets = 1;
1241     }
1242   else if (GET_CODE (body) == PARALLEL)
1243     {
1244       /* Look through the PARALLEL and record the values being
1245          set, if possible.  Also handle any CLOBBERs.  */
1246       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1247         {
1248           rtx x = XVECEXP (body, 0, i);
1249
1250           if (GET_CODE (x) == SET)
1251             {
1252               sets[n_sets].src = SET_SRC (x);
1253               sets[n_sets].dest = SET_DEST (x);
1254               n_sets++;
1255             }
1256         }
1257     }
1258
1259   /* Look up the values that are read.  Do this before invalidating the
1260      locations that are written.  */
1261   for (i = 0; i < n_sets; i++)
1262     {
1263       rtx dest = sets[i].dest;
1264
1265       /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1266          the low part after invalidating any knowledge about larger modes.  */
1267       if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1268         sets[i].dest = dest = XEXP (dest, 0);
1269
1270       /* We don't know how to record anything but REG or MEM.  */
1271       if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
1272         {
1273           rtx src = sets[i].src;
1274           if (cond)
1275             src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest);
1276           sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1277           if (GET_CODE (dest) == MEM)
1278             sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1279           else
1280             sets[i].dest_addr_elt = 0;
1281         }
1282     }
1283
1284   /* Invalidate all locations written by this insn.  Note that the elts we
1285      looked up in the previous loop aren't affected, just some of their
1286      locations may go away.  */
1287   note_stores (body, cselib_invalidate_rtx, NULL);
1288
1289   /* Now enter the equivalences in our tables.  */
1290   for (i = 0; i < n_sets; i++)
1291     {
1292       rtx dest = sets[i].dest;
1293       if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
1294         cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1295     }
1296 }
1297
1298 /* Record the effects of INSN.  */
1299
1300 void
1301 cselib_process_insn (rtx insn)
1302 {
1303   int i;
1304   rtx x;
1305
1306   if (find_reg_note (insn, REG_LIBCALL, NULL))
1307     cselib_current_insn_in_libcall = true;
1308   if (find_reg_note (insn, REG_RETVAL, NULL))
1309     cselib_current_insn_in_libcall = false;
1310   cselib_current_insn = insn;
1311
1312   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
1313   if (GET_CODE (insn) == CODE_LABEL
1314       || (GET_CODE (insn) == CALL_INSN
1315           && find_reg_note (insn, REG_SETJMP, NULL))
1316       || (GET_CODE (insn) == INSN
1317           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1318           && MEM_VOLATILE_P (PATTERN (insn))))
1319     {
1320       clear_table ();
1321       return;
1322     }
1323
1324   if (! INSN_P (insn))
1325     {
1326       cselib_current_insn = 0;
1327       return;
1328     }
1329
1330   /* If this is a call instruction, forget anything stored in a
1331      call clobbered register, or, if this is not a const call, in
1332      memory.  */
1333   if (GET_CODE (insn) == CALL_INSN)
1334     {
1335       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1336         if (call_used_regs[i])
1337           cselib_invalidate_regno (i, reg_raw_mode[i]);
1338
1339       if (! CONST_OR_PURE_CALL_P (insn))
1340         cselib_invalidate_mem (callmem);
1341     }
1342
1343   cselib_record_sets (insn);
1344
1345 #ifdef AUTO_INC_DEC
1346   /* Clobber any registers which appear in REG_INC notes.  We
1347      could keep track of the changes to their values, but it is
1348      unlikely to help.  */
1349   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1350     if (REG_NOTE_KIND (x) == REG_INC)
1351       cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
1352 #endif
1353
1354   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1355      after we have processed the insn.  */
1356   if (GET_CODE (insn) == CALL_INSN)
1357     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1358       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1359         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
1360
1361   cselib_current_insn = 0;
1362
1363   if (n_useless_values > MAX_USELESS_VALUES)
1364     remove_useless_values ();
1365 }
1366
1367 /* Make sure our varrays are big enough.  Not called from any cselib routines;
1368    it must be called by the user if it allocated new registers.  */
1369
1370 void
1371 cselib_update_varray_sizes (void)
1372 {
1373   unsigned int nregs = max_reg_num ();
1374
1375   if (nregs == cselib_nregs)
1376     return;
1377
1378   cselib_nregs = nregs;
1379   VARRAY_GROW (reg_values, nregs);
1380   VARRAY_GROW (used_regs, nregs);
1381 }
1382
1383 /* Initialize cselib for one pass.  The caller must also call
1384    init_alias_analysis.  */
1385
1386 void
1387 cselib_init (void)
1388 {
1389   elt_list_pool = create_alloc_pool ("elt_list",
1390                                      sizeof (struct elt_list), 10);
1391   elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
1392                                          sizeof (struct elt_loc_list), 10);
1393   cselib_val_pool = create_alloc_pool ("cselib_val_list",
1394                                        sizeof (cselib_val), 10);
1395   /* This is only created once.  */
1396   if (! callmem)
1397     callmem = gen_rtx_MEM (BLKmode, const0_rtx);
1398
1399   cselib_nregs = max_reg_num ();
1400   if (reg_values_old != NULL && VARRAY_SIZE (reg_values_old) >= cselib_nregs)
1401     {
1402       reg_values = reg_values_old;
1403       used_regs = used_regs_old;
1404     }
1405   else
1406     {
1407       VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
1408       VARRAY_UINT_INIT (used_regs, cselib_nregs, "used_regs");
1409     }
1410   hash_table = htab_create_ggc (31, get_value_hash, entry_and_rtx_equal_p,
1411                                 NULL);
1412   cselib_current_insn_in_libcall = false;
1413 }
1414
1415 /* Called when the current user is done with cselib.  */
1416
1417 void
1418 cselib_finish (void)
1419 {
1420   free_alloc_pool (elt_list_pool);
1421   free_alloc_pool (elt_loc_list_pool);
1422   free_alloc_pool (cselib_val_pool);
1423   clear_table ();
1424   reg_values_old = reg_values;
1425   reg_values = 0;
1426   used_regs_old = used_regs;
1427   used_regs = 0;
1428   hash_table = 0;
1429   n_useless_values = 0;
1430   next_unknown_value = 0;
1431 }
1432
1433 #include "gt-cselib.h"