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