OSDN Git Service

f45803e8e4de4799de09baef5135da850f81a8df
[pf3gnuchains/gcc-fork.git] / 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, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.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 "emit-rtl.h"
36 #include "toplev.h"
37 #include "output.h"
38 #include "ggc.h"
39 #include "hashtab.h"
40 #include "cselib.h"
41 #include "params.h"
42 #include "alloc-pool.h"
43 #include "target.h"
44
45 static bool cselib_record_memory;
46 static int entry_and_rtx_equal_p (const void *, const void *);
47 static hashval_t get_value_hash (const void *);
48 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
49 static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
50 static void unchain_one_value (cselib_val *);
51 static void unchain_one_elt_list (struct elt_list **);
52 static void unchain_one_elt_loc_list (struct elt_loc_list **);
53 static int discard_useless_locs (void **, void *);
54 static int discard_useless_values (void **, void *);
55 static void remove_useless_values (void);
56 static rtx wrap_constant (enum machine_mode, rtx);
57 static unsigned int cselib_hash_rtx (rtx, int);
58 static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
59 static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
60 static cselib_val *cselib_lookup_mem (rtx, int);
61 static void cselib_invalidate_regno (unsigned int, enum machine_mode);
62 static void cselib_invalidate_mem (rtx);
63 static void cselib_record_set (rtx, cselib_val *, cselib_val *);
64 static void cselib_record_sets (rtx);
65
66 /* There are three ways in which cselib can look up an rtx:
67    - for a REG, the reg_values table (which is indexed by regno) is used
68    - for a MEM, we recursively look up its address and then follow the
69      addr_list of that value
70    - for everything else, we compute a hash value and go through the hash
71      table.  Since different rtx's can still have the same hash value,
72      this involves walking the table entries for a given value and comparing
73      the locations of the entries with the rtx we are looking up.  */
74
75 /* A table that enables us to look up elts by their value.  */
76 static htab_t cselib_hash_table;
77
78 /* This is a global so we don't have to pass this through every function.
79    It is used in new_elt_loc_list to set SETTING_INSN.  */
80 static rtx cselib_current_insn;
81 static bool cselib_current_insn_in_libcall;
82
83 /* Every new unknown value gets a unique number.  */
84 static unsigned int next_unknown_value;
85
86 /* The number of registers we had when the varrays were last resized.  */
87 static unsigned int cselib_nregs;
88
89 /* Count values without known locations.  Whenever this grows too big, we
90    remove these useless values from the table.  */
91 static int n_useless_values;
92
93 /* Number of useless values before we remove them from the hash table.  */
94 #define MAX_USELESS_VALUES 32
95
96 /* This table maps from register number to values.  It does not
97    contain pointers to cselib_val structures, but rather elt_lists.
98    The purpose is to be able to refer to the same register in
99    different modes.  The first element of the list defines the mode in
100    which the register was set; if the mode is unknown or the value is
101    no longer valid in that mode, ELT will be NULL for the first
102    element.  */
103 static struct elt_list **reg_values;
104 static unsigned int reg_values_size;
105 #define REG_VALUES(i) reg_values[i]
106
107 /* The largest number of hard regs used by any entry added to the
108    REG_VALUES table.  Cleared on each cselib_clear_table() invocation.  */
109 static unsigned int max_value_regs;
110
111 /* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
112    in cselib_clear_table() for fast emptying.  */
113 static unsigned int *used_regs;
114 static unsigned int n_used_regs;
115
116 /* We pass this to cselib_invalidate_mem to invalidate all of
117    memory for a non-const call instruction.  */
118 static GTY(()) rtx callmem;
119
120 /* Set by discard_useless_locs if it deleted the last location of any
121    value.  */
122 static int values_became_useless;
123
124 /* Used as stop element of the containing_mem list so we can check
125    presence in the list by checking the next pointer.  */
126 static cselib_val dummy_val;
127
128 /* Used to list all values that contain memory reference.
129    May or may not contain the useless values - the list is compacted
130    each time memory is invalidated.  */
131 static cselib_val *first_containing_mem = &dummy_val;
132 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
133
134 /* If nonnull, cselib will call this function before freeing useless
135    VALUEs.  A VALUE is deemed useless if its "locs" field is null.  */
136 void (*cselib_discard_hook) (cselib_val *);
137 \f
138
139 /* Allocate a struct elt_list and fill in its two elements with the
140    arguments.  */
141
142 static inline struct elt_list *
143 new_elt_list (struct elt_list *next, cselib_val *elt)
144 {
145   struct elt_list *el;
146   el = pool_alloc (elt_list_pool);
147   el->next = next;
148   el->elt = elt;
149   return el;
150 }
151
152 /* Allocate a struct elt_loc_list and fill in its two elements with the
153    arguments.  */
154
155 static inline struct elt_loc_list *
156 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
157 {
158   struct elt_loc_list *el;
159   el = pool_alloc (elt_loc_list_pool);
160   el->next = next;
161   el->loc = loc;
162   el->setting_insn = cselib_current_insn;
163   el->in_libcall = cselib_current_insn_in_libcall;
164   return el;
165 }
166
167 /* The elt_list at *PL is no longer needed.  Unchain it and free its
168    storage.  */
169
170 static inline void
171 unchain_one_elt_list (struct elt_list **pl)
172 {
173   struct elt_list *l = *pl;
174
175   *pl = l->next;
176   pool_free (elt_list_pool, l);
177 }
178
179 /* Likewise for elt_loc_lists.  */
180
181 static void
182 unchain_one_elt_loc_list (struct elt_loc_list **pl)
183 {
184   struct elt_loc_list *l = *pl;
185
186   *pl = l->next;
187   pool_free (elt_loc_list_pool, l);
188 }
189
190 /* Likewise for cselib_vals.  This also frees the addr_list associated with
191    V.  */
192
193 static void
194 unchain_one_value (cselib_val *v)
195 {
196   while (v->addr_list)
197     unchain_one_elt_list (&v->addr_list);
198
199   pool_free (cselib_val_pool, v);
200 }
201
202 /* Remove all entries from the hash table.  Also used during
203    initialization.  If CLEAR_ALL isn't set, then only clear the entries
204    which are known to have been used.  */
205
206 void
207 cselib_clear_table (void)
208 {
209   unsigned int i;
210
211   for (i = 0; i < n_used_regs; i++)
212     REG_VALUES (used_regs[i]) = 0;
213
214   max_value_regs = 0;
215
216   n_used_regs = 0;
217
218   htab_empty (cselib_hash_table);
219
220   n_useless_values = 0;
221
222   next_unknown_value = 0;
223
224   first_containing_mem = &dummy_val;
225 }
226
227 /* The equality test for our hash table.  The first argument ENTRY is a table
228    element (i.e. a cselib_val), while the second arg X is an rtx.  We know
229    that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
230    CONST of an appropriate mode.  */
231
232 static int
233 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
234 {
235   struct elt_loc_list *l;
236   const cselib_val *const v = (const cselib_val *) entry;
237   rtx x = (rtx) x_arg;
238   enum machine_mode mode = GET_MODE (x);
239
240   gcc_assert (GET_CODE (x) != CONST_INT && GET_CODE (x) != CONST_FIXED
241               && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
242   
243   if (mode != GET_MODE (v->val_rtx))
244     return 0;
245
246   /* Unwrap X if necessary.  */
247   if (GET_CODE (x) == CONST
248       && (GET_CODE (XEXP (x, 0)) == CONST_INT
249           || GET_CODE (XEXP (x, 0)) == CONST_FIXED
250           || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
251     x = XEXP (x, 0);
252
253   /* We don't guarantee that distinct rtx's have different hash values,
254      so we need to do a comparison.  */
255   for (l = v->locs; l; l = l->next)
256     if (rtx_equal_for_cselib_p (l->loc, x))
257       return 1;
258
259   return 0;
260 }
261
262 /* The hash function for our hash table.  The value is always computed with
263    cselib_hash_rtx when adding an element; this function just extracts the
264    hash value from a cselib_val structure.  */
265
266 static hashval_t
267 get_value_hash (const void *entry)
268 {
269   const cselib_val *const v = (const cselib_val *) entry;
270   return v->value;
271 }
272
273 /* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
274    only return true for values which point to a cselib_val whose value
275    element has been set to zero, which implies the cselib_val will be
276    removed.  */
277
278 int
279 references_value_p (const_rtx x, int only_useless)
280 {
281   const enum rtx_code code = GET_CODE (x);
282   const char *fmt = GET_RTX_FORMAT (code);
283   int i, j;
284
285   if (GET_CODE (x) == VALUE
286       && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
287     return 1;
288
289   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
290     {
291       if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
292         return 1;
293       else if (fmt[i] == 'E')
294         for (j = 0; j < XVECLEN (x, i); j++)
295           if (references_value_p (XVECEXP (x, i, j), only_useless))
296             return 1;
297     }
298
299   return 0;
300 }
301
302 /* For all locations found in X, delete locations that reference useless
303    values (i.e. values without any location).  Called through
304    htab_traverse.  */
305
306 static int
307 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
308 {
309   cselib_val *v = (cselib_val *)*x;
310   struct elt_loc_list **p = &v->locs;
311   int had_locs = v->locs != 0;
312
313   while (*p)
314     {
315       if (references_value_p ((*p)->loc, 1))
316         unchain_one_elt_loc_list (p);
317       else
318         p = &(*p)->next;
319     }
320
321   if (had_locs && v->locs == 0)
322     {
323       n_useless_values++;
324       values_became_useless = 1;
325     }
326   return 1;
327 }
328
329 /* If X is a value with no locations, remove it from the hashtable.  */
330
331 static int
332 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
333 {
334   cselib_val *v = (cselib_val *)*x;
335
336   if (v->locs == 0)
337     {
338       if (cselib_discard_hook)
339         cselib_discard_hook (v);
340
341       CSELIB_VAL_PTR (v->val_rtx) = NULL;
342       htab_clear_slot (cselib_hash_table, x);
343       unchain_one_value (v);
344       n_useless_values--;
345     }
346
347   return 1;
348 }
349
350 /* Clean out useless values (i.e. those which no longer have locations
351    associated with them) from the hash table.  */
352
353 static void
354 remove_useless_values (void)
355 {
356   cselib_val **p, *v;
357   /* First pass: eliminate locations that reference the value.  That in
358      turn can make more values useless.  */
359   do
360     {
361       values_became_useless = 0;
362       htab_traverse (cselib_hash_table, discard_useless_locs, 0);
363     }
364   while (values_became_useless);
365
366   /* Second pass: actually remove the values.  */
367
368   p = &first_containing_mem;
369   for (v = *p; v != &dummy_val; v = v->next_containing_mem)
370     if (v->locs)
371       {
372         *p = v;
373         p = &(*p)->next_containing_mem;
374       }
375   *p = &dummy_val;
376
377   htab_traverse (cselib_hash_table, discard_useless_values, 0);
378
379   gcc_assert (!n_useless_values);
380 }
381
382 /* Return the mode in which a register was last set.  If X is not a
383    register, return its mode.  If the mode in which the register was
384    set is not known, or the value was already clobbered, return
385    VOIDmode.  */
386
387 enum machine_mode
388 cselib_reg_set_mode (const_rtx x)
389 {
390   if (!REG_P (x))
391     return GET_MODE (x);
392
393   if (REG_VALUES (REGNO (x)) == NULL
394       || REG_VALUES (REGNO (x))->elt == NULL)
395     return VOIDmode;
396
397   return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
398 }
399
400 /* Return nonzero if we can prove that X and Y contain the same value, taking
401    our gathered information into account.  */
402
403 int
404 rtx_equal_for_cselib_p (rtx x, rtx y)
405 {
406   enum rtx_code code;
407   const char *fmt;
408   int i;
409
410   if (REG_P (x) || MEM_P (x))
411     {
412       cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
413
414       if (e)
415         x = e->val_rtx;
416     }
417
418   if (REG_P (y) || MEM_P (y))
419     {
420       cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
421
422       if (e)
423         y = e->val_rtx;
424     }
425
426   if (x == y)
427     return 1;
428
429   if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
430     return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
431
432   if (GET_CODE (x) == VALUE)
433     {
434       cselib_val *e = CSELIB_VAL_PTR (x);
435       struct elt_loc_list *l;
436
437       for (l = e->locs; l; l = l->next)
438         {
439           rtx t = l->loc;
440
441           /* Avoid infinite recursion.  */
442           if (REG_P (t) || MEM_P (t))
443             continue;
444           else if (rtx_equal_for_cselib_p (t, y))
445             return 1;
446         }
447
448       return 0;
449     }
450
451   if (GET_CODE (y) == VALUE)
452     {
453       cselib_val *e = CSELIB_VAL_PTR (y);
454       struct elt_loc_list *l;
455
456       for (l = e->locs; l; l = l->next)
457         {
458           rtx t = l->loc;
459
460           if (REG_P (t) || MEM_P (t))
461             continue;
462           else if (rtx_equal_for_cselib_p (x, t))
463             return 1;
464         }
465
466       return 0;
467     }
468
469   if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
470     return 0;
471
472   /* These won't be handled correctly by the code below.  */
473   switch (GET_CODE (x))
474     {
475     case CONST_DOUBLE:
476     case CONST_FIXED:
477       return 0;
478
479     case LABEL_REF:
480       return XEXP (x, 0) == XEXP (y, 0);
481
482     default:
483       break;
484     }
485
486   code = GET_CODE (x);
487   fmt = GET_RTX_FORMAT (code);
488
489   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
490     {
491       int j;
492
493       switch (fmt[i])
494         {
495         case 'w':
496           if (XWINT (x, i) != XWINT (y, i))
497             return 0;
498           break;
499
500         case 'n':
501         case 'i':
502           if (XINT (x, i) != XINT (y, i))
503             return 0;
504           break;
505
506         case 'V':
507         case 'E':
508           /* Two vectors must have the same length.  */
509           if (XVECLEN (x, i) != XVECLEN (y, i))
510             return 0;
511
512           /* And the corresponding elements must match.  */
513           for (j = 0; j < XVECLEN (x, i); j++)
514             if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
515                                           XVECEXP (y, i, j)))
516               return 0;
517           break;
518
519         case 'e':
520           if (i == 1
521               && targetm.commutative_p (x, UNKNOWN)
522               && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
523               && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
524             return 1;
525           if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
526             return 0;
527           break;
528
529         case 'S':
530         case 's':
531           if (strcmp (XSTR (x, i), XSTR (y, i)))
532             return 0;
533           break;
534
535         case 'u':
536           /* These are just backpointers, so they don't matter.  */
537           break;
538
539         case '0':
540         case 't':
541           break;
542
543           /* It is believed that rtx's at this level will never
544              contain anything but integers and other rtx's,
545              except for within LABEL_REFs and SYMBOL_REFs.  */
546         default:
547           gcc_unreachable ();
548         }
549     }
550   return 1;
551 }
552
553 /* We need to pass down the mode of constants through the hash table
554    functions.  For that purpose, wrap them in a CONST of the appropriate
555    mode.  */
556 static rtx
557 wrap_constant (enum machine_mode mode, rtx x)
558 {
559   if (GET_CODE (x) != CONST_INT && GET_CODE (x) != CONST_FIXED
560       && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
561     return x;
562   gcc_assert (mode != VOIDmode);
563   return gen_rtx_CONST (mode, x);
564 }
565
566 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
567    For registers and memory locations, we look up their cselib_val structure
568    and return its VALUE element.
569    Possible reasons for return 0 are: the object is volatile, or we couldn't
570    find a register or memory location in the table and CREATE is zero.  If
571    CREATE is nonzero, table elts are created for regs and mem.
572    N.B. this hash function returns the same hash value for RTXes that
573    differ only in the order of operands, thus it is suitable for comparisons
574    that take commutativity into account.
575    If we wanted to also support associative rules, we'd have to use a different
576    strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
577    We used to have a MODE argument for hashing for CONST_INTs, but that
578    didn't make sense, since it caused spurious hash differences between
579     (set (reg:SI 1) (const_int))
580     (plus:SI (reg:SI 2) (reg:SI 1))
581    and
582     (plus:SI (reg:SI 2) (const_int))
583    If the mode is important in any context, it must be checked specifically
584    in a comparison anyway, since relying on hash differences is unsafe.  */
585
586 static unsigned int
587 cselib_hash_rtx (rtx x, int create)
588 {
589   cselib_val *e;
590   int i, j;
591   enum rtx_code code;
592   const char *fmt;
593   unsigned int hash = 0;
594
595   code = GET_CODE (x);
596   hash += (unsigned) code + (unsigned) GET_MODE (x);
597
598   switch (code)
599     {
600     case MEM:
601     case REG:
602       e = cselib_lookup (x, GET_MODE (x), create);
603       if (! e)
604         return 0;
605
606       return e->value;
607
608     case CONST_INT:
609       hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
610       return hash ? hash : (unsigned int) CONST_INT;
611
612     case CONST_DOUBLE:
613       /* This is like the general case, except that it only counts
614          the integers representing the constant.  */
615       hash += (unsigned) code + (unsigned) GET_MODE (x);
616       if (GET_MODE (x) != VOIDmode)
617         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
618       else
619         hash += ((unsigned) CONST_DOUBLE_LOW (x)
620                  + (unsigned) CONST_DOUBLE_HIGH (x));
621       return hash ? hash : (unsigned int) CONST_DOUBLE;
622
623     case CONST_FIXED:
624       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
625       hash += fixed_hash (CONST_FIXED_VALUE (x));
626       return hash ? hash : (unsigned int) CONST_FIXED;
627
628     case CONST_VECTOR:
629       {
630         int units;
631         rtx elt;
632
633         units = CONST_VECTOR_NUNITS (x);
634
635         for (i = 0; i < units; ++i)
636           {
637             elt = CONST_VECTOR_ELT (x, i);
638             hash += cselib_hash_rtx (elt, 0);
639           }
640
641         return hash;
642       }
643
644       /* Assume there is only one rtx object for any given label.  */
645     case LABEL_REF:
646       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
647          differences and differences between each stage's debugging dumps.  */
648       hash += (((unsigned int) LABEL_REF << 7)
649                + CODE_LABEL_NUMBER (XEXP (x, 0)));
650       return hash ? hash : (unsigned int) LABEL_REF;
651
652     case SYMBOL_REF:
653       {
654         /* Don't hash on the symbol's address to avoid bootstrap differences.
655            Different hash values may cause expressions to be recorded in
656            different orders and thus different registers to be used in the
657            final assembler.  This also avoids differences in the dump files
658            between various stages.  */
659         unsigned int h = 0;
660         const unsigned char *p = (const unsigned char *) XSTR (x, 0);
661
662         while (*p)
663           h += (h << 7) + *p++; /* ??? revisit */
664
665         hash += ((unsigned int) SYMBOL_REF << 7) + h;
666         return hash ? hash : (unsigned int) SYMBOL_REF;
667       }
668
669     case PRE_DEC:
670     case PRE_INC:
671     case POST_DEC:
672     case POST_INC:
673     case POST_MODIFY:
674     case PRE_MODIFY:
675     case PC:
676     case CC0:
677     case CALL:
678     case UNSPEC_VOLATILE:
679       return 0;
680
681     case ASM_OPERANDS:
682       if (MEM_VOLATILE_P (x))
683         return 0;
684
685       break;
686
687     default:
688       break;
689     }
690
691   i = GET_RTX_LENGTH (code) - 1;
692   fmt = GET_RTX_FORMAT (code);
693   for (; i >= 0; i--)
694     {
695       switch (fmt[i])
696         {
697         case 'e':
698           {
699             rtx tem = XEXP (x, i);
700             unsigned int tem_hash = cselib_hash_rtx (tem, create);
701             
702             if (tem_hash == 0)
703               return 0;
704             
705             hash += tem_hash;
706           }
707           break;
708         case 'E':
709           for (j = 0; j < XVECLEN (x, i); j++)
710             {
711               unsigned int tem_hash
712                 = cselib_hash_rtx (XVECEXP (x, i, j), create);
713               
714               if (tem_hash == 0)
715                 return 0;
716               
717               hash += tem_hash;
718             }
719           break;
720
721         case 's':
722           {
723             const unsigned char *p = (const unsigned char *) XSTR (x, i);
724             
725             if (p)
726               while (*p)
727                 hash += *p++;
728             break;
729           }
730           
731         case 'i':
732           hash += XINT (x, i);
733           break;
734
735         case '0':
736         case 't':
737           /* unused */
738           break;
739           
740         default:
741           gcc_unreachable ();
742         }
743     }
744
745   return hash ? hash : 1 + (unsigned int) GET_CODE (x);
746 }
747
748 /* Create a new value structure for VALUE and initialize it.  The mode of the
749    value is MODE.  */
750
751 static inline cselib_val *
752 new_cselib_val (unsigned int value, enum machine_mode mode)
753 {
754   cselib_val *e = pool_alloc (cselib_val_pool);
755
756   gcc_assert (value);
757
758   e->value = value;
759   /* We use an alloc pool to allocate this RTL construct because it
760      accounts for about 8% of the overall memory usage.  We know
761      precisely when we can have VALUE RTXen (when cselib is active)
762      so we don't need to put them in garbage collected memory.
763      ??? Why should a VALUE be an RTX in the first place?  */
764   e->val_rtx = pool_alloc (value_pool);
765   memset (e->val_rtx, 0, RTX_HDR_SIZE);
766   PUT_CODE (e->val_rtx, VALUE);
767   PUT_MODE (e->val_rtx, mode);
768   CSELIB_VAL_PTR (e->val_rtx) = e;
769   e->addr_list = 0;
770   e->locs = 0;
771   e->next_containing_mem = 0;
772   return e;
773 }
774
775 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
776    contains the data at this address.  X is a MEM that represents the
777    value.  Update the two value structures to represent this situation.  */
778
779 static void
780 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
781 {
782   struct elt_loc_list *l;
783
784   /* Avoid duplicates.  */
785   for (l = mem_elt->locs; l; l = l->next)
786     if (MEM_P (l->loc)
787         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
788       return;
789
790   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
791   mem_elt->locs
792     = new_elt_loc_list (mem_elt->locs,
793                         replace_equiv_address_nv (x, addr_elt->val_rtx));
794   if (mem_elt->next_containing_mem == NULL)
795     {
796       mem_elt->next_containing_mem = first_containing_mem;
797       first_containing_mem = mem_elt;
798     }
799 }
800
801 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
802    If CREATE, make a new one if we haven't seen it before.  */
803
804 static cselib_val *
805 cselib_lookup_mem (rtx x, int create)
806 {
807   enum machine_mode mode = GET_MODE (x);
808   void **slot;
809   cselib_val *addr;
810   cselib_val *mem_elt;
811   struct elt_list *l;
812
813   if (MEM_VOLATILE_P (x) || mode == BLKmode
814       || !cselib_record_memory
815       || (FLOAT_MODE_P (mode) && flag_float_store))
816     return 0;
817
818   /* Look up the value for the address.  */
819   addr = cselib_lookup (XEXP (x, 0), mode, create);
820   if (! addr)
821     return 0;
822
823   /* Find a value that describes a value of our mode at that address.  */
824   for (l = addr->addr_list; l; l = l->next)
825     if (GET_MODE (l->elt->val_rtx) == mode)
826       return l->elt;
827
828   if (! create)
829     return 0;
830
831   mem_elt = new_cselib_val (++next_unknown_value, mode);
832   add_mem_for_addr (addr, mem_elt, x);
833   slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
834                                    mem_elt->value, INSERT);
835   *slot = mem_elt;
836   return mem_elt;
837 }
838
839 /* Search thru the possible substitutions in P.  We prefer a non reg
840    substitution because this allows us to expand the tree further.  If
841    we find, just a reg, take the lowest regno.  There may be several
842    non-reg results, we just take the first one because they will all
843    expand to the same place.  */
844
845 static rtx 
846 expand_loc (struct elt_loc_list *p, bitmap regs_active, int max_depth)
847 {
848   rtx reg_result = NULL;
849   unsigned int regno = UINT_MAX;
850   struct elt_loc_list *p_in = p;
851
852   for (; p; p = p -> next)
853     {
854       /* Avoid infinite recursion trying to expand a reg into a
855          the same reg.  */
856       if ((REG_P (p->loc)) 
857           && (REGNO (p->loc) < regno) 
858           && !bitmap_bit_p (regs_active, REGNO (p->loc)))
859         {
860           reg_result = p->loc;
861           regno = REGNO (p->loc);
862         }
863       /* Avoid infinite recursion and do not try to expand the
864          value.  */
865       else if (GET_CODE (p->loc) == VALUE 
866                && CSELIB_VAL_PTR (p->loc)->locs == p_in)
867         continue;
868       else if (!REG_P (p->loc))
869         {
870           rtx result;
871           if (dump_file)
872             {
873               print_inline_rtx (dump_file, p->loc, 0);
874               fprintf (dump_file, "\n");
875             }
876           result = cselib_expand_value_rtx (p->loc, regs_active, max_depth - 1);
877           if (result)
878             return result;
879         }
880         
881     }
882   
883   if (regno != UINT_MAX)
884     {
885       rtx result;
886       if (dump_file)
887         fprintf (dump_file, "r%d\n", regno);
888
889       result = cselib_expand_value_rtx (reg_result, regs_active, max_depth - 1);
890       if (result)
891         return result;
892     }
893
894   if (dump_file)
895     {
896       if (reg_result)
897         {
898           print_inline_rtx (dump_file, reg_result, 0);
899           fprintf (dump_file, "\n");
900         }
901       else 
902         fprintf (dump_file, "NULL\n");
903     }
904   return reg_result;
905 }
906
907
908 /* Forward substitute and expand an expression out to its roots.
909    This is the opposite of common subexpression.  Because local value
910    numbering is such a weak optimization, the expanded expression is
911    pretty much unique (not from a pointer equals point of view but
912    from a tree shape point of view.  
913
914    This function returns NULL if the expansion fails.  The expansion
915    will fail if there is no value number for one of the operands or if
916    one of the operands has been overwritten between the current insn
917    and the beginning of the basic block.  For instance x has no
918    expansion in:
919
920    r1 <- r1 + 3
921    x <- r1 + 8
922
923    REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
924    It is clear on return.  */
925
926 rtx
927 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
928 {
929   rtx copy, scopy;
930   int i, j;
931   RTX_CODE code;
932   const char *format_ptr;
933
934   code = GET_CODE (orig);
935
936   /* For the context of dse, if we end up expand into a huge tree, we
937      will not have a useful address, so we might as well just give up
938      quickly.  */
939   if (max_depth <= 0)
940     return NULL;
941
942   switch (code)
943     {
944     case REG:
945       {
946         struct elt_list *l = REG_VALUES (REGNO (orig));
947
948         if (l && l->elt == NULL)
949           l = l->next;
950         for (; l; l = l->next)
951           if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
952             {
953               rtx result;
954               int regno = REGNO (orig);
955               
956               /* The only thing that we are not willing to do (this
957                  is requirement of dse and if others potential uses
958                  need this function we should add a parm to control
959                  it) is that we will not substitute the
960                  STACK_POINTER_REGNUM, FRAME_POINTER or the
961                  HARD_FRAME_POINTER.
962
963                  These expansions confuses the code that notices that
964                  stores into the frame go dead at the end of the
965                  function and that the frame is not effected by calls
966                  to subroutines.  If you allow the
967                  STACK_POINTER_REGNUM substitution, then dse will
968                  think that parameter pushing also goes dead which is
969                  wrong.  If you allow the FRAME_POINTER or the
970                  HARD_FRAME_POINTER then you lose the opportunity to
971                  make the frame assumptions.  */
972               if (regno == STACK_POINTER_REGNUM
973                   || regno == FRAME_POINTER_REGNUM
974                   || regno == HARD_FRAME_POINTER_REGNUM)
975                 return orig;
976
977               bitmap_set_bit (regs_active, regno);
978
979               if (dump_file)
980                 fprintf (dump_file, "expanding: r%d into: ", regno);
981
982               result = expand_loc (l->elt->locs, regs_active, max_depth);
983               bitmap_clear_bit (regs_active, regno);
984
985               if (result)
986                 return result;
987               else 
988                 return orig;
989             }
990       }
991       
992     case CONST_INT:
993     case CONST_DOUBLE:
994     case CONST_VECTOR:
995     case SYMBOL_REF:
996     case CODE_LABEL:
997     case PC:
998     case CC0:
999     case SCRATCH:
1000       /* SCRATCH must be shared because they represent distinct values.  */
1001       return orig;
1002     case CLOBBER:
1003       if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1004         return orig;
1005       break;
1006
1007     case CONST:
1008       if (shared_const_p (orig))
1009         return orig;
1010       break;
1011
1012
1013     case VALUE:
1014       {
1015         rtx result;
1016         if (dump_file)
1017           fprintf (dump_file, "expanding value %s into: ", GET_MODE_NAME (GET_MODE (orig)));
1018         
1019         result = expand_loc (CSELIB_VAL_PTR (orig)->locs, regs_active, max_depth);
1020         if (result 
1021             && GET_CODE (result) == CONST_INT
1022             && GET_MODE (orig) != VOIDmode)
1023           {
1024             result = gen_rtx_CONST (GET_MODE (orig), result);
1025             if (dump_file)
1026               fprintf (dump_file, "  wrapping const_int result in const to preserve mode %s\n", 
1027                        GET_MODE_NAME (GET_MODE (orig)));
1028           }
1029         return result;
1030       }
1031     default:
1032       break;
1033     }
1034
1035   /* Copy the various flags, fields, and other information.  We assume
1036      that all fields need copying, and then clear the fields that should
1037      not be copied.  That is the sensible default behavior, and forces
1038      us to explicitly document why we are *not* copying a flag.  */
1039   copy = shallow_copy_rtx (orig);
1040
1041   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
1042
1043   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
1044     switch (*format_ptr++)
1045       {
1046       case 'e':
1047         if (XEXP (orig, i) != NULL)
1048           {
1049             rtx result = cselib_expand_value_rtx (XEXP (orig, i), regs_active, max_depth - 1);
1050             if (!result)
1051               return NULL;
1052             XEXP (copy, i) = result;
1053           }
1054         break;
1055
1056       case 'E':
1057       case 'V':
1058         if (XVEC (orig, i) != NULL)
1059           {
1060             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1061             for (j = 0; j < XVECLEN (copy, i); j++)
1062               {
1063                 rtx result = cselib_expand_value_rtx (XVECEXP (orig, i, j), regs_active, max_depth - 1);
1064                 if (!result)
1065                   return NULL;
1066                 XVECEXP (copy, i, j) = result;
1067               }
1068           }
1069         break;
1070
1071       case 't':
1072       case 'w':
1073       case 'i':
1074       case 's':
1075       case 'S':
1076       case 'T':
1077       case 'u':
1078       case 'B':
1079       case '0':
1080         /* These are left unchanged.  */
1081         break;
1082
1083       default:
1084         gcc_unreachable ();
1085       }
1086
1087   scopy = simplify_rtx (copy);
1088   if (scopy)
1089     return scopy;
1090   return copy;
1091 }
1092
1093 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1094    with VALUE expressions.  This way, it becomes independent of changes
1095    to registers and memory.
1096    X isn't actually modified; if modifications are needed, new rtl is
1097    allocated.  However, the return value can share rtl with X.  */
1098
1099 rtx
1100 cselib_subst_to_values (rtx x)
1101 {
1102   enum rtx_code code = GET_CODE (x);
1103   const char *fmt = GET_RTX_FORMAT (code);
1104   cselib_val *e;
1105   struct elt_list *l;
1106   rtx copy = x;
1107   int i;
1108
1109   switch (code)
1110     {
1111     case REG:
1112       l = REG_VALUES (REGNO (x));
1113       if (l && l->elt == NULL)
1114         l = l->next;
1115       for (; l; l = l->next)
1116         if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1117           return l->elt->val_rtx;
1118
1119       gcc_unreachable ();
1120
1121     case MEM:
1122       e = cselib_lookup_mem (x, 0);
1123       if (! e)
1124         {
1125           /* This happens for autoincrements.  Assign a value that doesn't
1126              match any other.  */
1127           e = new_cselib_val (++next_unknown_value, GET_MODE (x));
1128         }
1129       return e->val_rtx;
1130
1131     case CONST_DOUBLE:
1132     case CONST_VECTOR:
1133     case CONST_INT:
1134     case CONST_FIXED:
1135       return x;
1136
1137     case POST_INC:
1138     case PRE_INC:
1139     case POST_DEC:
1140     case PRE_DEC:
1141     case POST_MODIFY:
1142     case PRE_MODIFY:
1143       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
1144       return e->val_rtx;
1145
1146     default:
1147       break;
1148     }
1149
1150   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1151     {
1152       if (fmt[i] == 'e')
1153         {
1154           rtx t = cselib_subst_to_values (XEXP (x, i));
1155
1156           if (t != XEXP (x, i) && x == copy)
1157             copy = shallow_copy_rtx (x);
1158
1159           XEXP (copy, i) = t;
1160         }
1161       else if (fmt[i] == 'E')
1162         {
1163           int j, k;
1164
1165           for (j = 0; j < XVECLEN (x, i); j++)
1166             {
1167               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1168
1169               if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
1170                 {
1171                   if (x == copy)
1172                     copy = shallow_copy_rtx (x);
1173
1174                   XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
1175                   for (k = 0; k < j; k++)
1176                     XVECEXP (copy, i, k) = XVECEXP (x, i, k);
1177                 }
1178
1179               XVECEXP (copy, i, j) = t;
1180             }
1181         }
1182     }
1183
1184   return copy;
1185 }
1186
1187 /* Look up the rtl expression X in our tables and return the value it has.
1188    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
1189    we create a new one if possible, using mode MODE if X doesn't have a mode
1190    (i.e. because it's a constant).  */
1191
1192 cselib_val *
1193 cselib_lookup (rtx x, enum machine_mode mode, int create)
1194 {
1195   void **slot;
1196   cselib_val *e;
1197   unsigned int hashval;
1198
1199   if (GET_MODE (x) != VOIDmode)
1200     mode = GET_MODE (x);
1201
1202   if (GET_CODE (x) == VALUE)
1203     return CSELIB_VAL_PTR (x);
1204
1205   if (REG_P (x))
1206     {
1207       struct elt_list *l;
1208       unsigned int i = REGNO (x);
1209
1210       l = REG_VALUES (i);
1211       if (l && l->elt == NULL)
1212         l = l->next;
1213       for (; l; l = l->next)
1214         if (mode == GET_MODE (l->elt->val_rtx))
1215           return l->elt;
1216
1217       if (! create)
1218         return 0;
1219
1220       if (i < FIRST_PSEUDO_REGISTER)
1221         {
1222           unsigned int n = hard_regno_nregs[i][mode];
1223
1224           if (n > max_value_regs)
1225             max_value_regs = n;
1226         }
1227
1228       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
1229       e->locs = new_elt_loc_list (e->locs, x);
1230       if (REG_VALUES (i) == 0)
1231         {
1232           /* Maintain the invariant that the first entry of
1233              REG_VALUES, if present, must be the value used to set the
1234              register, or NULL.  */
1235           used_regs[n_used_regs++] = i;
1236           REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1237         }
1238       REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1239       slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
1240       *slot = e;
1241       return e;
1242     }
1243
1244   if (MEM_P (x))
1245     return cselib_lookup_mem (x, create);
1246
1247   hashval = cselib_hash_rtx (x, create);
1248   /* Can't even create if hashing is not possible.  */
1249   if (! hashval)
1250     return 0;
1251
1252   slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1253                                    hashval, create ? INSERT : NO_INSERT);
1254   if (slot == 0)
1255     return 0;
1256
1257   e = (cselib_val *) *slot;
1258   if (e)
1259     return e;
1260
1261   e = new_cselib_val (hashval, mode);
1262
1263   /* We have to fill the slot before calling cselib_subst_to_values:
1264      the hash table is inconsistent until we do so, and
1265      cselib_subst_to_values will need to do lookups.  */
1266   *slot = (void *) e;
1267   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1268   return e;
1269 }
1270
1271 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
1272    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
1273    is used to determine how many hard registers are being changed.  If MODE
1274    is VOIDmode, then only REGNO is being changed; this is used when
1275    invalidating call clobbered registers across a call.  */
1276
1277 static void
1278 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1279 {
1280   unsigned int endregno;
1281   unsigned int i;
1282
1283   /* If we see pseudos after reload, something is _wrong_.  */
1284   gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1285               || reg_renumber[regno] < 0);
1286
1287   /* Determine the range of registers that must be invalidated.  For
1288      pseudos, only REGNO is affected.  For hard regs, we must take MODE
1289      into account, and we must also invalidate lower register numbers
1290      if they contain values that overlap REGNO.  */
1291   if (regno < FIRST_PSEUDO_REGISTER)
1292     {
1293       gcc_assert (mode != VOIDmode);
1294
1295       if (regno < max_value_regs)
1296         i = 0;
1297       else
1298         i = regno - max_value_regs;
1299
1300       endregno = end_hard_regno (mode, regno);
1301     }
1302   else
1303     {
1304       i = regno;
1305       endregno = regno + 1;
1306     }
1307
1308   for (; i < endregno; i++)
1309     {
1310       struct elt_list **l = &REG_VALUES (i);
1311
1312       /* Go through all known values for this reg; if it overlaps the range
1313          we're invalidating, remove the value.  */
1314       while (*l)
1315         {
1316           cselib_val *v = (*l)->elt;
1317           struct elt_loc_list **p;
1318           unsigned int this_last = i;
1319
1320           if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1321             this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1322
1323           if (this_last < regno || v == NULL)
1324             {
1325               l = &(*l)->next;
1326               continue;
1327             }
1328
1329           /* We have an overlap.  */
1330           if (*l == REG_VALUES (i))
1331             {
1332               /* Maintain the invariant that the first entry of
1333                  REG_VALUES, if present, must be the value used to set
1334                  the register, or NULL.  This is also nice because
1335                  then we won't push the same regno onto user_regs
1336                  multiple times.  */
1337               (*l)->elt = NULL;
1338               l = &(*l)->next;
1339             }
1340           else
1341             unchain_one_elt_list (l);
1342
1343           /* Now, we clear the mapping from value to reg.  It must exist, so
1344              this code will crash intentionally if it doesn't.  */
1345           for (p = &v->locs; ; p = &(*p)->next)
1346             {
1347               rtx x = (*p)->loc;
1348
1349               if (REG_P (x) && REGNO (x) == i)
1350                 {
1351                   unchain_one_elt_loc_list (p);
1352                   break;
1353                 }
1354             }
1355           if (v->locs == 0)
1356             n_useless_values++;
1357         }
1358     }
1359 }
1360 \f
1361 /* Return 1 if X has a value that can vary even between two
1362    executions of the program.  0 means X can be compared reliably
1363    against certain constants or near-constants.  */
1364
1365 static bool
1366 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1367 {
1368   /* We actually don't need to verify very hard.  This is because
1369      if X has actually changed, we invalidate the memory anyway,
1370      so assume that all common memory addresses are
1371      invariant.  */
1372   return 0;
1373 }
1374
1375 /* Invalidate any locations in the table which are changed because of a
1376    store to MEM_RTX.  If this is called because of a non-const call
1377    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1378
1379 static void
1380 cselib_invalidate_mem (rtx mem_rtx)
1381 {
1382   cselib_val **vp, *v, *next;
1383   int num_mems = 0;
1384   rtx mem_addr;
1385
1386   mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1387   mem_rtx = canon_rtx (mem_rtx);
1388
1389   vp = &first_containing_mem;
1390   for (v = *vp; v != &dummy_val; v = next)
1391     {
1392       bool has_mem = false;
1393       struct elt_loc_list **p = &v->locs;
1394       int had_locs = v->locs != 0;
1395
1396       while (*p)
1397         {
1398           rtx x = (*p)->loc;
1399           cselib_val *addr;
1400           struct elt_list **mem_chain;
1401
1402           /* MEMs may occur in locations only at the top level; below
1403              that every MEM or REG is substituted by its VALUE.  */
1404           if (!MEM_P (x))
1405             {
1406               p = &(*p)->next;
1407               continue;
1408             }
1409           if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1410               && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1411                                           x, cselib_rtx_varies_p))
1412             {
1413               has_mem = true;
1414               num_mems++;
1415               p = &(*p)->next;
1416               continue;
1417             }
1418
1419           /* This one overlaps.  */
1420           /* We must have a mapping from this MEM's address to the
1421              value (E).  Remove that, too.  */
1422           addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1423           mem_chain = &addr->addr_list;
1424           for (;;)
1425             {
1426               if ((*mem_chain)->elt == v)
1427                 {
1428                   unchain_one_elt_list (mem_chain);
1429                   break;
1430                 }
1431
1432               mem_chain = &(*mem_chain)->next;
1433             }
1434
1435           unchain_one_elt_loc_list (p);
1436         }
1437
1438       if (had_locs && v->locs == 0)
1439         n_useless_values++;
1440
1441       next = v->next_containing_mem;
1442       if (has_mem)
1443         {
1444           *vp = v;
1445           vp = &(*vp)->next_containing_mem;
1446         }
1447       else
1448         v->next_containing_mem = NULL;
1449     }
1450   *vp = &dummy_val;
1451 }
1452
1453 /* Invalidate DEST, which is being assigned to or clobbered.  */
1454
1455 void
1456 cselib_invalidate_rtx (rtx dest)
1457 {
1458   while (GET_CODE (dest) == SUBREG
1459          || GET_CODE (dest) == ZERO_EXTRACT
1460          || GET_CODE (dest) == STRICT_LOW_PART)
1461     dest = XEXP (dest, 0);
1462
1463   if (REG_P (dest))
1464     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1465   else if (MEM_P (dest))
1466     cselib_invalidate_mem (dest);
1467
1468   /* Some machines don't define AUTO_INC_DEC, but they still use push
1469      instructions.  We need to catch that case here in order to
1470      invalidate the stack pointer correctly.  Note that invalidating
1471      the stack pointer is different from invalidating DEST.  */
1472   if (push_operand (dest, GET_MODE (dest)))
1473     cselib_invalidate_rtx (stack_pointer_rtx);
1474 }
1475
1476 /* A wrapper for cselib_invalidate_rtx to be called via note_stores.  */
1477
1478 static void
1479 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1480                                    void *data ATTRIBUTE_UNUSED)
1481 {
1482   cselib_invalidate_rtx (dest);
1483 }
1484
1485 /* Record the result of a SET instruction.  DEST is being set; the source
1486    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1487    describes its address.  */
1488
1489 static void
1490 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1491 {
1492   int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1493
1494   if (src_elt == 0 || side_effects_p (dest))
1495     return;
1496
1497   if (dreg >= 0)
1498     {
1499       if (dreg < FIRST_PSEUDO_REGISTER)
1500         {
1501           unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1502
1503           if (n > max_value_regs)
1504             max_value_regs = n;
1505         }
1506
1507       if (REG_VALUES (dreg) == 0)
1508         {
1509           used_regs[n_used_regs++] = dreg;
1510           REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1511         }
1512       else
1513         {
1514           /* The register should have been invalidated.  */
1515           gcc_assert (REG_VALUES (dreg)->elt == 0);
1516           REG_VALUES (dreg)->elt = src_elt;
1517         }
1518
1519       if (src_elt->locs == 0)
1520         n_useless_values--;
1521       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1522     }
1523   else if (MEM_P (dest) && dest_addr_elt != 0
1524            && cselib_record_memory)
1525     {
1526       if (src_elt->locs == 0)
1527         n_useless_values--;
1528       add_mem_for_addr (dest_addr_elt, src_elt, dest);
1529     }
1530 }
1531
1532 /* Describe a single set that is part of an insn.  */
1533 struct set
1534 {
1535   rtx src;
1536   rtx dest;
1537   cselib_val *src_elt;
1538   cselib_val *dest_addr_elt;
1539 };
1540
1541 /* There is no good way to determine how many elements there can be
1542    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
1543 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1544
1545 /* Record the effects of any sets in INSN.  */
1546 static void
1547 cselib_record_sets (rtx insn)
1548 {
1549   int n_sets = 0;
1550   int i;
1551   struct set sets[MAX_SETS];
1552   rtx body = PATTERN (insn);
1553   rtx cond = 0;
1554
1555   body = PATTERN (insn);
1556   if (GET_CODE (body) == COND_EXEC)
1557     {
1558       cond = COND_EXEC_TEST (body);
1559       body = COND_EXEC_CODE (body);
1560     }
1561
1562   /* Find all sets.  */
1563   if (GET_CODE (body) == SET)
1564     {
1565       sets[0].src = SET_SRC (body);
1566       sets[0].dest = SET_DEST (body);
1567       n_sets = 1;
1568     }
1569   else if (GET_CODE (body) == PARALLEL)
1570     {
1571       /* Look through the PARALLEL and record the values being
1572          set, if possible.  Also handle any CLOBBERs.  */
1573       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1574         {
1575           rtx x = XVECEXP (body, 0, i);
1576
1577           if (GET_CODE (x) == SET)
1578             {
1579               sets[n_sets].src = SET_SRC (x);
1580               sets[n_sets].dest = SET_DEST (x);
1581               n_sets++;
1582             }
1583         }
1584     }
1585
1586   /* Look up the values that are read.  Do this before invalidating the
1587      locations that are written.  */
1588   for (i = 0; i < n_sets; i++)
1589     {
1590       rtx dest = sets[i].dest;
1591
1592       /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1593          the low part after invalidating any knowledge about larger modes.  */
1594       if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1595         sets[i].dest = dest = XEXP (dest, 0);
1596
1597       /* We don't know how to record anything but REG or MEM.  */
1598       if (REG_P (dest)
1599           || (MEM_P (dest) && cselib_record_memory))
1600         {
1601           rtx src = sets[i].src;
1602           if (cond)
1603             src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1604           sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1605           if (MEM_P (dest))
1606             sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1607           else
1608             sets[i].dest_addr_elt = 0;
1609         }
1610     }
1611
1612   /* Invalidate all locations written by this insn.  Note that the elts we
1613      looked up in the previous loop aren't affected, just some of their
1614      locations may go away.  */
1615   note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1616
1617   /* If this is an asm, look for duplicate sets.  This can happen when the
1618      user uses the same value as an output multiple times.  This is valid
1619      if the outputs are not actually used thereafter.  Treat this case as
1620      if the value isn't actually set.  We do this by smashing the destination
1621      to pc_rtx, so that we won't record the value later.  */
1622   if (n_sets >= 2 && asm_noperands (body) >= 0)
1623     {
1624       for (i = 0; i < n_sets; i++)
1625         {
1626           rtx dest = sets[i].dest;
1627           if (REG_P (dest) || MEM_P (dest))
1628             {
1629               int j;
1630               for (j = i + 1; j < n_sets; j++)
1631                 if (rtx_equal_p (dest, sets[j].dest))
1632                   {
1633                     sets[i].dest = pc_rtx;
1634                     sets[j].dest = pc_rtx;
1635                   }
1636             }
1637         }
1638     }
1639
1640   /* Now enter the equivalences in our tables.  */
1641   for (i = 0; i < n_sets; i++)
1642     {
1643       rtx dest = sets[i].dest;
1644       if (REG_P (dest)
1645           || (MEM_P (dest) && cselib_record_memory))
1646         cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1647     }
1648 }
1649
1650 /* Record the effects of INSN.  */
1651
1652 void
1653 cselib_process_insn (rtx insn)
1654 {
1655   int i;
1656   rtx x;
1657
1658   if (find_reg_note (insn, REG_LIBCALL, NULL))
1659     cselib_current_insn_in_libcall = true;
1660   cselib_current_insn = insn;
1661
1662   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
1663   if (LABEL_P (insn)
1664       || (CALL_P (insn)
1665           && find_reg_note (insn, REG_SETJMP, NULL))
1666       || (NONJUMP_INSN_P (insn)
1667           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1668           && MEM_VOLATILE_P (PATTERN (insn))))
1669     {
1670       if (find_reg_note (insn, REG_RETVAL, NULL))
1671         cselib_current_insn_in_libcall = false;
1672       cselib_clear_table ();
1673       return;
1674     }
1675
1676   if (! INSN_P (insn))
1677     {
1678       if (find_reg_note (insn, REG_RETVAL, NULL))
1679         cselib_current_insn_in_libcall = false;
1680       cselib_current_insn = 0;
1681       return;
1682     }
1683
1684   /* If this is a call instruction, forget anything stored in a
1685      call clobbered register, or, if this is not a const call, in
1686      memory.  */
1687   if (CALL_P (insn))
1688     {
1689       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1690         if (call_used_regs[i]
1691             || (REG_VALUES (i) && REG_VALUES (i)->elt
1692                 && HARD_REGNO_CALL_PART_CLOBBERED (i, 
1693                       GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1694           cselib_invalidate_regno (i, reg_raw_mode[i]);
1695
1696       /* Since it is not clear how cselib is going to be used, be
1697          conservative here and treat looping pure or const functions
1698          as if they were regular functions.  */
1699       if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1700           || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1701         cselib_invalidate_mem (callmem);
1702     }
1703
1704   cselib_record_sets (insn);
1705
1706 #ifdef AUTO_INC_DEC
1707   /* Clobber any registers which appear in REG_INC notes.  We
1708      could keep track of the changes to their values, but it is
1709      unlikely to help.  */
1710   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1711     if (REG_NOTE_KIND (x) == REG_INC)
1712       cselib_invalidate_rtx (XEXP (x, 0));
1713 #endif
1714
1715   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1716      after we have processed the insn.  */
1717   if (CALL_P (insn))
1718     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1719       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1720         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
1721
1722   if (find_reg_note (insn, REG_RETVAL, NULL))
1723     cselib_current_insn_in_libcall = false;
1724   cselib_current_insn = 0;
1725
1726   if (n_useless_values > MAX_USELESS_VALUES
1727       /* remove_useless_values is linear in the hash table size.  Avoid
1728          quadratic behavior for very large hashtables with very few
1729          useless elements.  */
1730       && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
1731     remove_useless_values ();
1732 }
1733
1734 /* Initialize cselib for one pass.  The caller must also call
1735    init_alias_analysis.  */
1736
1737 void
1738 cselib_init (bool record_memory)
1739 {
1740   elt_list_pool = create_alloc_pool ("elt_list", 
1741                                      sizeof (struct elt_list), 10);
1742   elt_loc_list_pool = create_alloc_pool ("elt_loc_list", 
1743                                          sizeof (struct elt_loc_list), 10);
1744   cselib_val_pool = create_alloc_pool ("cselib_val_list", 
1745                                        sizeof (cselib_val), 10);
1746   value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
1747   cselib_record_memory = record_memory;
1748
1749   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
1750      see canon_true_dependence.  This is only created once.  */
1751   if (! callmem)
1752     callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
1753
1754   cselib_nregs = max_reg_num ();
1755
1756   /* We preserve reg_values to allow expensive clearing of the whole thing.
1757      Reallocate it however if it happens to be too large.  */
1758   if (!reg_values || reg_values_size < cselib_nregs
1759       || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
1760     {
1761       if (reg_values)
1762         free (reg_values);
1763       /* Some space for newly emit instructions so we don't end up
1764          reallocating in between passes.  */
1765       reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
1766       reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
1767     }
1768   used_regs = XNEWVEC (unsigned int, cselib_nregs);
1769   n_used_regs = 0;
1770   cselib_hash_table = htab_create (31, get_value_hash,
1771                                    entry_and_rtx_equal_p, NULL);
1772   cselib_current_insn_in_libcall = false;
1773 }
1774
1775 /* Called when the current user is done with cselib.  */
1776
1777 void
1778 cselib_finish (void)
1779 {
1780   cselib_discard_hook = NULL;
1781   free_alloc_pool (elt_list_pool);
1782   free_alloc_pool (elt_loc_list_pool);
1783   free_alloc_pool (cselib_val_pool);
1784   free_alloc_pool (value_pool);
1785   cselib_clear_table ();
1786   htab_delete (cselib_hash_table);
1787   free (used_regs);
1788   used_regs = 0;
1789   cselib_hash_table = 0;
1790   n_useless_values = 0;
1791   next_unknown_value = 0;
1792 }
1793
1794 #include "gt-cselib.h"