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