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