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