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