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