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