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