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   code = GET_CODE (x);
 570   hash += (unsigned) code + (unsigned) GET_MODE (x);
 571
 572   switch (code)
 573     {
 574     case MEM:
 575     case REG:
 576       e = cselib_lookup (x, GET_MODE (x), create);
 577       if (! e)
 578         return 0;
 579
 580       return e->value;
 581
 582     case CONST_INT:
 583       hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
 584       return hash ? hash : (unsigned int) CONST_INT;
 585
 586     case CONST_DOUBLE:
 587       /* This is like the general case, except that it only counts
 588          the integers representing the constant.  */
 589       hash += (unsigned) code + (unsigned) GET_MODE (x);
 590       if (GET_MODE (x) != VOIDmode)
 591         for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
 592           hash += XWINT (x, i);
 593       else
 594         hash += ((unsigned) CONST_DOUBLE_LOW (x)
 595                  + (unsigned) CONST_DOUBLE_HIGH (x));
 596       return hash ? hash : (unsigned int) CONST_DOUBLE;
 597
 598       /* Assume there is only one rtx object for any given label.  */
 599     case LABEL_REF:
 600       hash
 601         += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
 602       return hash ? hash : (unsigned int) LABEL_REF;
 603
 604     case SYMBOL_REF:
 605       hash
 606         += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
 607       return hash ? hash : (unsigned int) SYMBOL_REF;
 608
 609     case PRE_DEC:
 610     case PRE_INC:
 611     case POST_DEC:
 612     case POST_INC:
 613     case POST_MODIFY:
 614     case PRE_MODIFY:
 615     case PC:
 616     case CC0:
 617     case CALL:
 618     case UNSPEC_VOLATILE:
 619       return 0;
 620
 621     case ASM_OPERANDS:
 622       if (MEM_VOLATILE_P (x))
 623         return 0;
 624
 625       break;
 626
 627     default:
 628       break;
 629     }
 630
 631   i = GET_RTX_LENGTH (code) - 1;
 632   fmt = GET_RTX_FORMAT (code);
 633   for (; i >= 0; i--)
 634     {
 635       if (fmt[i] == 'e')
 636         {
 637           rtx tem = XEXP (x, i);
 638           unsigned int tem_hash = hash_rtx (tem, 0, create);
 639
 640           if (tem_hash == 0)
 641             return 0;
 642
 643           hash += tem_hash;
 644         }
 645       else if (fmt[i] == 'E')
 646         for (j = 0; j < XVECLEN (x, i); j++)
 647           {
 648             unsigned int tem_hash = hash_rtx (XVECEXP (x, i, j), 0, create);
 649
 650             if (tem_hash == 0)
 651               return 0;
 652
 653             hash += tem_hash;
 654           }
 655       else if (fmt[i] == 's')
 656         {
 657           const unsigned char *p = (const unsigned char *) XSTR (x, i);
 658
 659           if (p)
 660             while (*p)
 661               hash += *p++;
 662         }
 663       else if (fmt[i] == 'i')
 664         hash += XINT (x, i);
 665       else if (fmt[i] == '0' || fmt[i] == 't')
 666         /* unused */;
 667       else
 668         abort ();
 669     }
 670
 671   return hash ? hash : 1 + (unsigned int) GET_CODE (x);
 672 }
 673
 674 /* Create a new value structure for VALUE and initialize it.  The mode of the
 675    value is MODE.  */
 676
 677 static cselib_val *
 678 new_cselib_val (value, mode)
 679      unsigned int value;
 680      enum machine_mode mode;
 681 {
 682   cselib_val *e = empty_vals;
 683
 684   if (e)
 685     empty_vals = e->u.next_free;
 686   else
 687     e = (cselib_val *) obstack_alloc (&cselib_obstack, sizeof (cselib_val));
 688
 689   if (value == 0)
 690     abort ();
 691
 692   e->value = value;
 693   e->u.val_rtx = gen_rtx_VALUE (mode);
 694   CSELIB_VAL_PTR (e->u.val_rtx) = e;
 695   e->addr_list = 0;
 696   e->locs = 0;
 697   return e;
 698 }
 699
 700 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
 701    contains the data at this address.  X is a MEM that represents the
 702    value.  Update the two value structures to represent this situation.  */
 703
 704 static void
 705 add_mem_for_addr (addr_elt, mem_elt, x)
 706      cselib_val *addr_elt, *mem_elt;
 707      rtx x;
 708 {
 709   struct elt_loc_list *l;
 710
 711   /* Avoid duplicates.  */
 712   for (l = mem_elt->locs; l; l = l->next)
 713     if (GET_CODE (l->loc) == MEM
 714         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
 715       return;
 716
 717   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
 718   mem_elt->locs
 719     = new_elt_loc_list (mem_elt->locs,
 720                         replace_equiv_address_nv (x, addr_elt->u.val_rtx));
 721 }
 722
 723 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
 724    If CREATE, make a new one if we haven't seen it before.  */
 725
 726 static cselib_val *
 727 cselib_lookup_mem (x, create)
 728      rtx x;
 729      int create;
 730 {
 731   enum machine_mode mode = GET_MODE (x);
 732   void **slot;
 733   cselib_val *addr;
 734   cselib_val *mem_elt;
 735   struct elt_list *l;
 736
 737   if (MEM_VOLATILE_P (x) || mode == BLKmode
 738       || (FLOAT_MODE_P (mode) && flag_float_store))
 739     return 0;
 740
 741   /* Look up the value for the address.  */
 742   addr = cselib_lookup (XEXP (x, 0), mode, create);
 743   if (! addr)
 744     return 0;
 745
 746   /* Find a value that describes a value of our mode at that address.  */
 747   for (l = addr->addr_list; l; l = l->next)
 748     if (GET_MODE (l->elt->u.val_rtx) == mode)
 749       return l->elt;
 750
 751   if (! create)
 752     return 0;
 753
 754   mem_elt = new_cselib_val (++next_unknown_value, mode);
 755   add_mem_for_addr (addr, mem_elt, x);
 756   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
 757                                    mem_elt->value, INSERT);
 758   *slot = mem_elt;
 759   return mem_elt;
 760 }
 761
 762 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
 763    with VALUE expressions.  This way, it becomes independent of changes
 764    to registers and memory.
 765    X isn't actually modified; if modifications are needed, new rtl is
 766    allocated.  However, the return value can share rtl with X.  */
 767
 768 static rtx
 769 cselib_subst_to_values (x)
 770      rtx x;
 771 {
 772   enum rtx_code code = GET_CODE (x);
 773   const char *fmt = GET_RTX_FORMAT (code);
 774   cselib_val *e;
 775   struct elt_list *l;
 776   rtx copy = x;
 777   int i;
 778
 779   switch (code)
 780     {
 781     case REG:
 782       for (l = REG_VALUES (REGNO (x)); l; l = l->next)
 783         if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
 784           return l->elt->u.val_rtx;
 785
 786       abort ();
 787
 788     case MEM:
 789       e = cselib_lookup_mem (x, 0);
 790       if (! e)
 791         abort ();
 792       return e->u.val_rtx;
 793
 794       /* CONST_DOUBLEs must be special-cased here so that we won't try to
 795          look up the CONST_DOUBLE_MEM inside.  */
 796     case CONST_DOUBLE:
 797     case CONST_INT:
 798       return x;
 799
 800     default:
 801       break;
 802     }
 803
 804   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 805     {
 806       if (fmt[i] == 'e')
 807         {
 808           rtx t = cselib_subst_to_values (XEXP (x, i));
 809
 810           if (t != XEXP (x, i) && x == copy)
 811             copy = shallow_copy_rtx (x);
 812
 813           XEXP (copy, i) = t;
 814         }
 815       else if (fmt[i] == 'E')
 816         {
 817           int j, k;
 818
 819           for (j = 0; j < XVECLEN (x, i); j++)
 820             {
 821               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
 822
 823               if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
 824                 {
 825                   if (x == copy)
 826                     copy = shallow_copy_rtx (x);
 827
 828                   XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
 829                   for (k = 0; k < j; k++)
 830                     XVECEXP (copy, i, k) = XVECEXP (x, i, k);
 831                 }
 832
 833               XVECEXP (copy, i, j) = t;
 834             }
 835         }
 836     }
 837
 838   return copy;
 839 }
 840
 841 /* Look up the rtl expression X in our tables and return the value it has.
 842    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
 843    we create a new one if possible, using mode MODE if X doesn't have a mode
 844    (i.e. because it's a constant).  */
 845
 846 cselib_val *
 847 cselib_lookup (x, mode, create)
 848      rtx x;
 849      enum machine_mode mode;
 850      int create;
 851 {
 852   void **slot;
 853   cselib_val *e;
 854   unsigned int hashval;
 855
 856   if (GET_MODE (x) != VOIDmode)
 857     mode = GET_MODE (x);
 858
 859   if (GET_CODE (x) == VALUE)
 860     return CSELIB_VAL_PTR (x);
 861
 862   if (GET_CODE (x) == REG)
 863     {
 864       struct elt_list *l;
 865       unsigned int i = REGNO (x);
 866
 867       for (l = REG_VALUES (i); l; l = l->next)
 868         if (mode == GET_MODE (l->elt->u.val_rtx))
 869           return l->elt;
 870
 871       if (! create)
 872         return 0;
 873
 874       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
 875       e->locs = new_elt_loc_list (e->locs, x);
 876       if (REG_VALUES (i) == 0)
 877         VARRAY_PUSH_UINT (used_regs, i);
 878       REG_VALUES (i) = new_elt_list (REG_VALUES (i), e);
 879       slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
 880       *slot = e;
 881       return e;
 882     }
 883
 884   if (GET_CODE (x) == MEM)
 885     return cselib_lookup_mem (x, create);
 886
 887   hashval = hash_rtx (x, mode, create);
 888   /* Can't even create if hashing is not possible.  */
 889   if (! hashval)
 890     return 0;
 891
 892   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
 893                                    hashval, create ? INSERT : NO_INSERT);
 894   if (slot == 0)
 895     return 0;
 896
 897   e = (cselib_val *) *slot;
 898   if (e)
 899     return e;
 900
 901   e = new_cselib_val (hashval, mode);
 902
 903   /* We have to fill the slot before calling cselib_subst_to_values:
 904      the hash table is inconsistent until we do so, and
 905      cselib_subst_to_values will need to do lookups.  */
 906   *slot = (void *) e;
 907   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
 908   return e;
 909 }
 910
 911 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
 912    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
 913    is used to determine how many hard registers are being changed.  If MODE
 914    is VOIDmode, then only REGNO is being changed; this is used when
 915    invalidating call clobbered registers across a call.  */
 916
 917 static void
 918 cselib_invalidate_regno (regno, mode)
 919      unsigned int regno;
 920      enum machine_mode mode;
 921 {
 922   unsigned int endregno;
 923   unsigned int i;
 924
 925   /* If we see pseudos after reload, something is _wrong_.  */
 926   if (reload_completed && regno >= FIRST_PSEUDO_REGISTER
 927       && reg_renumber[regno] >= 0)
 928     abort ();
 929
 930   /* Determine the range of registers that must be invalidated.  For
 931      pseudos, only REGNO is affected.  For hard regs, we must take MODE
 932      into account, and we must also invalidate lower register numbers
 933      if they contain values that overlap REGNO.  */
 934   endregno = regno + 1;
 935   if (regno < FIRST_PSEUDO_REGISTER && mode != VOIDmode)
 936     endregno = regno + HARD_REGNO_NREGS (regno, mode);
 937
 938   for (i = 0; i < endregno; i++)
 939     {
 940       struct elt_list **l = &REG_VALUES (i);
 941
 942       /* Go through all known values for this reg; if it overlaps the range
 943          we're invalidating, remove the value.  */
 944       while (*l)
 945         {
 946           cselib_val *v = (*l)->elt;
 947           struct elt_loc_list **p;
 948           unsigned int this_last = i;
 949
 950           if (i < FIRST_PSEUDO_REGISTER)
 951             this_last += HARD_REGNO_NREGS (i, GET_MODE (v->u.val_rtx)) - 1;
 952
 953           if (this_last < regno)
 954             {
 955               l = &(*l)->next;
 956               continue;
 957             }
 958
 959           /* We have an overlap.  */
 960           unchain_one_elt_list (l);
 961
 962           /* Now, we clear the mapping from value to reg.  It must exist, so
 963              this code will crash intentionally if it doesn't.  */
 964           for (p = &v->locs; ; p = &(*p)->next)
 965             {
 966               rtx x = (*p)->loc;
 967
 968               if (GET_CODE (x) == REG && REGNO (x) == i)
 969                 {
 970                   unchain_one_elt_loc_list (p);
 971                   break;
 972                 }
 973             }
 974           if (v->locs == 0)
 975             n_useless_values++;
 976         }
 977     }
 978 }
 979
 980 /* The memory at address MEM_BASE is being changed.
 981    Return whether this change will invalidate VAL.  */
 982
 983 static int
 984 cselib_mem_conflict_p (mem_base, val)
 985      rtx mem_base;
 986      rtx val;
 987 {
 988   enum rtx_code code;
 989   const char *fmt;
 990   int i, j;
 991
 992   code = GET_CODE (val);
 993   switch (code)
 994     {
 995       /* Get rid of a few simple cases quickly.  */
 996     case REG:
 997     case PC:
 998     case CC0:
 999     case SCRATCH:
1000     case CONST:
1001     case CONST_INT:
1002     case CONST_DOUBLE:
1003     case SYMBOL_REF:
1004     case LABEL_REF:
1005       return 0;
1006
1007     case MEM:
1008       if (GET_MODE (mem_base) == BLKmode
1009           || GET_MODE (val) == BLKmode
1010           || anti_dependence (val, mem_base))
1011         return 1;
1012
1013       /* The address may contain nested MEMs.  */
1014       break;
1015
1016     default:
1017       break;
1018     }
1019
1020   fmt = GET_RTX_FORMAT (code);
1021   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1022     {
1023       if (fmt[i] == 'e')
1024         {
1025           if (cselib_mem_conflict_p (mem_base, XEXP (val, i)))
1026             return 1;
1027         }
1028       else if (fmt[i] == 'E')
1029         for (j = 0; j < XVECLEN (val, i); j++)
1030           if (cselib_mem_conflict_p (mem_base, XVECEXP (val, i, j)))
1031             return 1;
1032     }
1033
1034   return 0;
1035 }
1036
1037 /* For the value found in SLOT, walk its locations to determine if any overlap
1038    INFO (which is a MEM rtx).  */
1039
1040 static int
1041 cselib_invalidate_mem_1 (slot, info)
1042      void **slot;
1043      void *info;
1044 {
1045   cselib_val *v = (cselib_val *) *slot;
1046   rtx mem_rtx = (rtx) info;
1047   struct elt_loc_list **p = &v->locs;
1048   int had_locs = v->locs != 0;
1049
1050   while (*p)
1051     {
1052       rtx x = (*p)->loc;
1053       cselib_val *addr;
1054       struct elt_list **mem_chain;
1055
1056       /* MEMs may occur in locations only at the top level; below
1057          that every MEM or REG is substituted by its VALUE.  */
1058       if (GET_CODE (x) != MEM
1059           || ! cselib_mem_conflict_p (mem_rtx, x))
1060         {
1061           p = &(*p)->next;
1062           continue;
1063         }
1064
1065       /* This one overlaps.  */
1066       /* We must have a mapping from this MEM's address to the
1067          value (E).  Remove that, too.  */
1068       addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1069       mem_chain = &addr->addr_list;
1070       for (;;)
1071         {
1072           if ((*mem_chain)->elt == v)
1073             {
1074               unchain_one_elt_list (mem_chain);
1075               break;
1076             }
1077
1078           mem_chain = &(*mem_chain)->next;
1079         }
1080
1081       unchain_one_elt_loc_list (p);
1082     }
1083
1084   if (had_locs && v->locs == 0)
1085     n_useless_values++;
1086
1087   return 1;
1088 }
1089
1090 /* Invalidate any locations in the table which are changed because of a
1091    store to MEM_RTX.  If this is called because of a non-const call
1092    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1093
1094 static void
1095 cselib_invalidate_mem (mem_rtx)
1096      rtx mem_rtx;
1097 {
1098   htab_traverse (hash_table, cselib_invalidate_mem_1, mem_rtx);
1099 }
1100
1101 /* Invalidate DEST, which is being assigned to or clobbered.  The second and
1102    the third parameter exist so that this function can be passed to
1103    note_stores; they are ignored.  */
1104
1105 static void
1106 cselib_invalidate_rtx (dest, ignore, data)
1107      rtx dest;
1108      rtx ignore ATTRIBUTE_UNUSED;
1109      void *data ATTRIBUTE_UNUSED;
1110 {
1111   while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SIGN_EXTRACT
1112          || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SUBREG)
1113     dest = XEXP (dest, 0);
1114
1115   if (GET_CODE (dest) == REG)
1116     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1117   else if (GET_CODE (dest) == MEM)
1118     cselib_invalidate_mem (dest);
1119
1120   /* Some machines don't define AUTO_INC_DEC, but they still use push
1121      instructions.  We need to catch that case here in order to
1122      invalidate the stack pointer correctly.  Note that invalidating
1123      the stack pointer is different from invalidating DEST.  */
1124   if (push_operand (dest, GET_MODE (dest)))
1125     cselib_invalidate_rtx (stack_pointer_rtx, NULL_RTX, NULL);
1126 }
1127
1128 /* Record the result of a SET instruction.  DEST is being set; the source
1129    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1130    describes its address.  */
1131
1132 static void
1133 cselib_record_set (dest, src_elt, dest_addr_elt)
1134      rtx dest;
1135      cselib_val *src_elt, *dest_addr_elt;
1136 {
1137   int dreg = GET_CODE (dest) == REG ? (int) REGNO (dest) : -1;
1138
1139   if (src_elt == 0 || side_effects_p (dest))
1140     return;
1141
1142   if (dreg >= 0)
1143     {
1144       if (REG_VALUES (dreg) == 0)
1145         VARRAY_PUSH_UINT (used_regs, dreg);
1146
1147       REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1148       if (src_elt->locs == 0)
1149         n_useless_values--;
1150       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1151     }
1152   else if (GET_CODE (dest) == MEM && dest_addr_elt != 0)
1153     {
1154       if (src_elt->locs == 0)
1155         n_useless_values--;
1156       add_mem_for_addr (dest_addr_elt, src_elt, dest);
1157     }
1158 }
1159
1160 /* Describe a single set that is part of an insn.  */
1161 struct set
1162 {
1163   rtx src;
1164   rtx dest;
1165   cselib_val *src_elt;
1166   cselib_val *dest_addr_elt;
1167 };
1168
1169 /* There is no good way to determine how many elements there can be
1170    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
1171 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1172
1173 /* Record the effects of any sets in INSN.  */
1174 static void
1175 cselib_record_sets (insn)
1176      rtx insn;
1177 {
1178   int n_sets = 0;
1179   int i;
1180   struct set sets[MAX_SETS];
1181   rtx body = PATTERN (insn);
1182
1183   body = PATTERN (insn);
1184   /* Find all sets.  */
1185   if (GET_CODE (body) == SET)
1186     {
1187       sets[0].src = SET_SRC (body);
1188       sets[0].dest = SET_DEST (body);
1189       n_sets = 1;
1190     }
1191   else if (GET_CODE (body) == PARALLEL)
1192     {
1193       /* Look through the PARALLEL and record the values being
1194          set, if possible.  Also handle any CLOBBERs.  */
1195       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1196         {
1197           rtx x = XVECEXP (body, 0, i);
1198
1199           if (GET_CODE (x) == SET)
1200             {
1201               sets[n_sets].src = SET_SRC (x);
1202               sets[n_sets].dest = SET_DEST (x);
1203               n_sets++;
1204             }
1205         }
1206     }
1207
1208   /* Look up the values that are read.  Do this before invalidating the
1209      locations that are written.  */
1210   for (i = 0; i < n_sets; i++)
1211     {
1212       rtx dest = sets[i].dest;
1213
1214       /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1215          the low part after invalidating any knowledge about larger modes.  */
1216       if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1217         sets[i].dest = dest = XEXP (dest, 0);
1218
1219       /* We don't know how to record anything but REG or MEM.  */
1220       if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
1221         {
1222           sets[i].src_elt = cselib_lookup (sets[i].src, GET_MODE (dest), 1);
1223           if (GET_CODE (dest) == MEM)
1224             sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1225           else
1226             sets[i].dest_addr_elt = 0;
1227         }
1228     }
1229
1230   /* Invalidate all locations written by this insn.  Note that the elts we
1231      looked up in the previous loop aren't affected, just some of their
1232      locations may go away.  */
1233   note_stores (body, cselib_invalidate_rtx, NULL);
1234
1235   /* Now enter the equivalences in our tables.  */
1236   for (i = 0; i < n_sets; i++)
1237     {
1238       rtx dest = sets[i].dest;
1239       if (GET_CODE (dest) == REG || GET_CODE (dest) == MEM)
1240         cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1241     }
1242 }
1243
1244 /* Record the effects of INSN.  */
1245
1246 void
1247 cselib_process_insn (insn)
1248      rtx insn;
1249 {
1250   int i;
1251   rtx x;
1252
1253   cselib_current_insn = insn;
1254
1255   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
1256   if (GET_CODE (insn) == CODE_LABEL
1257       || (GET_CODE (insn) == NOTE
1258           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
1259       || (GET_CODE (insn) == INSN
1260           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1261           && MEM_VOLATILE_P (PATTERN (insn))))
1262     {
1263       clear_table (0);
1264       return;
1265     }
1266
1267   if (! INSN_P (insn))
1268     {
1269       cselib_current_insn = 0;
1270       return;
1271     }
1272
1273   /* If this is a call instruction, forget anything stored in a
1274      call clobbered register, or, if this is not a const call, in
1275      memory.  */
1276   if (GET_CODE (insn) == CALL_INSN)
1277     {
1278       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1279         if (call_used_regs[i])
1280           cselib_invalidate_regno (i, VOIDmode);
1281
1282       if (! CONST_CALL_P (insn))
1283         cselib_invalidate_mem (callmem);
1284     }
1285
1286   cselib_record_sets (insn);
1287
1288 #ifdef AUTO_INC_DEC
1289   /* Clobber any registers which appear in REG_INC notes.  We
1290      could keep track of the changes to their values, but it is
1291      unlikely to help.  */
1292   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1293     if (REG_NOTE_KIND (x) == REG_INC)
1294       cselib_invalidate_rtx (XEXP (x, 0), NULL_RTX, NULL);
1295 #endif
1296
1297   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1298      after we have processed the insn.  */
1299   if (GET_CODE (insn) == CALL_INSN)
1300     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1301       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1302         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0), NULL_RTX, NULL);
1303
1304   cselib_current_insn = 0;
1305
1306   if (n_useless_values > MAX_USELESS_VALUES)
1307     remove_useless_values ();
1308 }
1309
1310 /* Make sure our varrays are big enough.  Not called from any cselib routines;
1311    it must be called by the user if it allocated new registers.  */
1312
1313 void
1314 cselib_update_varray_sizes ()
1315 {
1316   unsigned int nregs = max_reg_num ();
1317
1318   if (nregs == cselib_nregs)
1319     return;
1320
1321   cselib_nregs = nregs;
1322   VARRAY_GROW (reg_values, nregs);
1323   VARRAY_GROW (used_regs, nregs);
1324 }
1325
1326 /* Initialize cselib for one pass.  The caller must also call
1327    init_alias_analysis.  */
1328
1329 void
1330 cselib_init ()
1331 {
1332   /* These are only created once.  */
1333   if (! callmem)
1334     {
1335       gcc_obstack_init (&cselib_obstack);
1336       cselib_startobj = obstack_alloc (&cselib_obstack, 0);
1337
1338       callmem = gen_rtx_MEM (BLKmode, const0_rtx);
1339       ggc_add_rtx_root (&callmem, 1);
1340     }
1341
1342   cselib_nregs = max_reg_num ();
1343   VARRAY_ELT_LIST_INIT (reg_values, cselib_nregs, "reg_values");
1344   VARRAY_UINT_INIT (used_regs, cselib_nregs, "used_regs");
1345   hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
1346   clear_table (1);
1347 }
1348
1349 /* Called when the current user is done with cselib.  */
1350
1351 void
1352 cselib_finish ()
1353 {
1354   clear_table (0);
1355   VARRAY_FREE (reg_values);
1356   VARRAY_FREE (used_regs);
1357   htab_delete (hash_table);
1358 }