OSDN Git Service

f46c5ecb29b23295225c979ebabc275fd40512e0
[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, 2008, 2009, 2010
4    Free Software Foundation, Inc.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "regs.h"
30 #include "hard-reg-set.h"
31 #include "flags.h"
32 #include "real.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "function.h"
36 #include "emit-rtl.h"
37 #include "toplev.h"
38 #include "output.h"
39 #include "ggc.h"
40 #include "hashtab.h"
41 #include "tree-pass.h"
42 #include "cselib.h"
43 #include "params.h"
44 #include "alloc-pool.h"
45 #include "target.h"
46
47 static bool cselib_record_memory;
48 static bool cselib_preserve_constants;
49 static int entry_and_rtx_equal_p (const void *, const void *);
50 static hashval_t get_value_hash (const void *);
51 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
52 static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
53 static void unchain_one_value (cselib_val *);
54 static void unchain_one_elt_list (struct elt_list **);
55 static void unchain_one_elt_loc_list (struct elt_loc_list **);
56 static int discard_useless_locs (void **, void *);
57 static int discard_useless_values (void **, void *);
58 static void remove_useless_values (void);
59 static unsigned int cselib_hash_rtx (rtx, int);
60 static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx);
61 static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
62 static cselib_val *cselib_lookup_mem (rtx, int);
63 static void cselib_invalidate_regno (unsigned int, enum machine_mode);
64 static void cselib_invalidate_mem (rtx);
65 static void cselib_record_set (rtx, cselib_val *, cselib_val *);
66 static void cselib_record_sets (rtx);
67
68 struct expand_value_data
69 {
70   bitmap regs_active;
71   cselib_expand_callback callback;
72   void *callback_arg;
73   bool dummy;
74 };
75
76 static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
77
78 /* There are three ways in which cselib can look up an rtx:
79    - for a REG, the reg_values table (which is indexed by regno) is used
80    - for a MEM, we recursively look up its address and then follow the
81      addr_list of that value
82    - for everything else, we compute a hash value and go through the hash
83      table.  Since different rtx's can still have the same hash value,
84      this involves walking the table entries for a given value and comparing
85      the locations of the entries with the rtx we are looking up.  */
86
87 /* A table that enables us to look up elts by their value.  */
88 static htab_t cselib_hash_table;
89
90 /* This is a global so we don't have to pass this through every function.
91    It is used in new_elt_loc_list to set SETTING_INSN.  */
92 static rtx cselib_current_insn;
93
94 /* The unique id that the next create value will take.  */
95 static unsigned int next_uid;
96
97 /* The number of registers we had when the varrays were last resized.  */
98 static unsigned int cselib_nregs;
99
100 /* Count values without known locations, or with only locations that
101    wouldn't have been known except for debug insns.  Whenever this
102    grows too big, we remove these useless values from the table.
103
104    Counting values with only debug values is a bit tricky.  We don't
105    want to increment n_useless_values when we create a value for a
106    debug insn, for this would get n_useless_values out of sync, but we
107    want increment it if all locs in the list that were ever referenced
108    in nondebug insns are removed from the list.
109
110    In the general case, once we do that, we'd have to stop accepting
111    nondebug expressions in the loc list, to avoid having two values
112    equivalent that, without debug insns, would have been made into
113    separate values.  However, because debug insns never introduce
114    equivalences themselves (no assignments), the only means for
115    growing loc lists is through nondebug assignments.  If the locs
116    also happen to be referenced in debug insns, it will work just fine.
117
118    A consequence of this is that there's at most one debug-only loc in
119    each loc list.  If we keep it in the first entry, testing whether
120    we have a debug-only loc list takes O(1).
121
122    Furthermore, since any additional entry in a loc list containing a
123    debug loc would have to come from an assignment (nondebug) that
124    references both the initial debug loc and the newly-equivalent loc,
125    the initial debug loc would be promoted to a nondebug loc, and the
126    loc list would not contain debug locs any more.
127
128    So the only case we have to be careful with in order to keep
129    n_useless_values in sync between debug and nondebug compilations is
130    to avoid incrementing n_useless_values when removing the single loc
131    from a value that turns out to not appear outside debug values.  We
132    increment n_useless_debug_values instead, and leave such values
133    alone until, for other reasons, we garbage-collect useless
134    values.  */
135 static int n_useless_values;
136 static int n_useless_debug_values;
137
138 /* Count values whose locs have been taken exclusively from debug
139    insns for the entire life of the value.  */
140 static int n_debug_values;
141
142 /* Number of useless values before we remove them from the hash table.  */
143 #define MAX_USELESS_VALUES 32
144
145 /* This table maps from register number to values.  It does not
146    contain pointers to cselib_val structures, but rather elt_lists.
147    The purpose is to be able to refer to the same register in
148    different modes.  The first element of the list defines the mode in
149    which the register was set; if the mode is unknown or the value is
150    no longer valid in that mode, ELT will be NULL for the first
151    element.  */
152 static struct elt_list **reg_values;
153 static unsigned int reg_values_size;
154 #define REG_VALUES(i) reg_values[i]
155
156 /* The largest number of hard regs used by any entry added to the
157    REG_VALUES table.  Cleared on each cselib_clear_table() invocation.  */
158 static unsigned int max_value_regs;
159
160 /* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
161    in cselib_clear_table() for fast emptying.  */
162 static unsigned int *used_regs;
163 static unsigned int n_used_regs;
164
165 /* We pass this to cselib_invalidate_mem to invalidate all of
166    memory for a non-const call instruction.  */
167 static GTY(()) rtx callmem;
168
169 /* Set by discard_useless_locs if it deleted the last location of any
170    value.  */
171 static int values_became_useless;
172
173 /* Used as stop element of the containing_mem list so we can check
174    presence in the list by checking the next pointer.  */
175 static cselib_val dummy_val;
176
177 /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
178    that is constant through the whole function and should never be
179    eliminated.  */
180 static cselib_val *cfa_base_preserved_val;
181
182 /* Used to list all values that contain memory reference.
183    May or may not contain the useless values - the list is compacted
184    each time memory is invalidated.  */
185 static cselib_val *first_containing_mem = &dummy_val;
186 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
187
188 /* If nonnull, cselib will call this function before freeing useless
189    VALUEs.  A VALUE is deemed useless if its "locs" field is null.  */
190 void (*cselib_discard_hook) (cselib_val *);
191
192 /* If nonnull, cselib will call this function before recording sets or
193    even clobbering outputs of INSN.  All the recorded sets will be
194    represented in the array sets[n_sets].  new_val_min can be used to
195    tell whether values present in sets are introduced by this
196    instruction.  */
197 void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,
198                                  int n_sets);
199
200 #define PRESERVED_VALUE_P(RTX) \
201   (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
202
203 \f
204
205 /* Allocate a struct elt_list and fill in its two elements with the
206    arguments.  */
207
208 static inline struct elt_list *
209 new_elt_list (struct elt_list *next, cselib_val *elt)
210 {
211   struct elt_list *el;
212   el = (struct elt_list *) pool_alloc (elt_list_pool);
213   el->next = next;
214   el->elt = elt;
215   return el;
216 }
217
218 /* Allocate a struct elt_loc_list and fill in its two elements with the
219    arguments.  */
220
221 static inline struct elt_loc_list *
222 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
223 {
224   struct elt_loc_list *el;
225   el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool);
226   el->next = next;
227   el->loc = loc;
228   el->setting_insn = cselib_current_insn;
229   gcc_assert (!next || !next->setting_insn
230               || !DEBUG_INSN_P (next->setting_insn));
231
232   /* If we're creating the first loc in a debug insn context, we've
233      just created a debug value.  Count it.  */
234   if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
235     n_debug_values++;
236
237   return el;
238 }
239
240 /* Promote loc L to a nondebug cselib_current_insn if L is marked as
241    originating from a debug insn, maintaining the debug values
242    count.  */
243
244 static inline void
245 promote_debug_loc (struct elt_loc_list *l)
246 {
247   if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)
248       && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
249     {
250       n_debug_values--;
251       l->setting_insn = cselib_current_insn;
252       gcc_assert (!l->next);
253     }
254 }
255
256 /* The elt_list at *PL is no longer needed.  Unchain it and free its
257    storage.  */
258
259 static inline void
260 unchain_one_elt_list (struct elt_list **pl)
261 {
262   struct elt_list *l = *pl;
263
264   *pl = l->next;
265   pool_free (elt_list_pool, l);
266 }
267
268 /* Likewise for elt_loc_lists.  */
269
270 static void
271 unchain_one_elt_loc_list (struct elt_loc_list **pl)
272 {
273   struct elt_loc_list *l = *pl;
274
275   *pl = l->next;
276   pool_free (elt_loc_list_pool, l);
277 }
278
279 /* Likewise for cselib_vals.  This also frees the addr_list associated with
280    V.  */
281
282 static void
283 unchain_one_value (cselib_val *v)
284 {
285   while (v->addr_list)
286     unchain_one_elt_list (&v->addr_list);
287
288   pool_free (cselib_val_pool, v);
289 }
290
291 /* Remove all entries from the hash table.  Also used during
292    initialization.  */
293
294 void
295 cselib_clear_table (void)
296 {
297   cselib_reset_table (1);
298 }
299
300 /* Remove from hash table all VALUEs except constants.  */
301
302 static int
303 preserve_only_constants (void **x, void *info ATTRIBUTE_UNUSED)
304 {
305   cselib_val *v = (cselib_val *)*x;
306
307   if (v->locs != NULL
308       && v->locs->next == NULL)
309     {
310       if (CONSTANT_P (v->locs->loc)
311           && (GET_CODE (v->locs->loc) != CONST
312               || !references_value_p (v->locs->loc, 0)))
313         return 1;
314       if (cfa_base_preserved_val)
315         {
316           if (v == cfa_base_preserved_val)
317             return 1;
318           if (GET_CODE (v->locs->loc) == PLUS
319               && CONST_INT_P (XEXP (v->locs->loc, 1))
320               && XEXP (v->locs->loc, 0) == cfa_base_preserved_val->val_rtx)
321             return 1;
322         }
323     }
324
325   htab_clear_slot (cselib_hash_table, x);
326   return 1;
327 }
328
329 /* Remove all entries from the hash table, arranging for the next
330    value to be numbered NUM.  */
331
332 void
333 cselib_reset_table (unsigned int num)
334 {
335   unsigned int i;
336
337   max_value_regs = 0;
338
339   if (cfa_base_preserved_val)
340     {
341       unsigned int regno = REGNO (cfa_base_preserved_val->locs->loc);
342       unsigned int new_used_regs = 0;
343       for (i = 0; i < n_used_regs; i++)
344         if (used_regs[i] == regno)
345           {
346             new_used_regs = 1;
347             continue;
348           }
349         else
350           REG_VALUES (used_regs[i]) = 0;
351       gcc_assert (new_used_regs == 1);
352       n_used_regs = new_used_regs;
353       used_regs[0] = regno;
354       max_value_regs
355         = hard_regno_nregs[regno][GET_MODE (cfa_base_preserved_val->locs->loc)];
356     }
357   else
358     {
359       for (i = 0; i < n_used_regs; i++)
360         REG_VALUES (used_regs[i]) = 0;
361       n_used_regs = 0;
362     }
363
364   if (cselib_preserve_constants)
365     htab_traverse (cselib_hash_table, preserve_only_constants, NULL);
366   else
367     htab_empty (cselib_hash_table);
368
369   n_useless_values = 0;
370   n_useless_debug_values = 0;
371   n_debug_values = 0;
372
373   next_uid = num;
374
375   first_containing_mem = &dummy_val;
376 }
377
378 /* Return the number of the next value that will be generated.  */
379
380 unsigned int
381 cselib_get_next_uid (void)
382 {
383   return next_uid;
384 }
385
386 /* The equality test for our hash table.  The first argument ENTRY is a table
387    element (i.e. a cselib_val), while the second arg X is an rtx.  We know
388    that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
389    CONST of an appropriate mode.  */
390
391 static int
392 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
393 {
394   struct elt_loc_list *l;
395   const cselib_val *const v = (const cselib_val *) entry;
396   rtx x = CONST_CAST_RTX ((const_rtx)x_arg);
397   enum machine_mode mode = GET_MODE (x);
398
399   gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
400               && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
401
402   if (mode != GET_MODE (v->val_rtx))
403     return 0;
404
405   /* Unwrap X if necessary.  */
406   if (GET_CODE (x) == CONST
407       && (CONST_INT_P (XEXP (x, 0))
408           || GET_CODE (XEXP (x, 0)) == CONST_FIXED
409           || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
410     x = XEXP (x, 0);
411
412   /* We don't guarantee that distinct rtx's have different hash values,
413      so we need to do a comparison.  */
414   for (l = v->locs; l; l = l->next)
415     if (rtx_equal_for_cselib_p (l->loc, x))
416       {
417         promote_debug_loc (l);
418         return 1;
419       }
420
421   return 0;
422 }
423
424 /* The hash function for our hash table.  The value is always computed with
425    cselib_hash_rtx when adding an element; this function just extracts the
426    hash value from a cselib_val structure.  */
427
428 static hashval_t
429 get_value_hash (const void *entry)
430 {
431   const cselib_val *const v = (const cselib_val *) entry;
432   return v->hash;
433 }
434
435 /* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
436    only return true for values which point to a cselib_val whose value
437    element has been set to zero, which implies the cselib_val will be
438    removed.  */
439
440 int
441 references_value_p (const_rtx x, int only_useless)
442 {
443   const enum rtx_code code = GET_CODE (x);
444   const char *fmt = GET_RTX_FORMAT (code);
445   int i, j;
446
447   if (GET_CODE (x) == VALUE
448       && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
449     return 1;
450
451   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
452     {
453       if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
454         return 1;
455       else if (fmt[i] == 'E')
456         for (j = 0; j < XVECLEN (x, i); j++)
457           if (references_value_p (XVECEXP (x, i, j), only_useless))
458             return 1;
459     }
460
461   return 0;
462 }
463
464 /* For all locations found in X, delete locations that reference useless
465    values (i.e. values without any location).  Called through
466    htab_traverse.  */
467
468 static int
469 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
470 {
471   cselib_val *v = (cselib_val *)*x;
472   struct elt_loc_list **p = &v->locs;
473   bool had_locs = v->locs != NULL;
474   rtx setting_insn = v->locs ? v->locs->setting_insn : NULL;
475
476   while (*p)
477     {
478       if (references_value_p ((*p)->loc, 1))
479         unchain_one_elt_loc_list (p);
480       else
481         p = &(*p)->next;
482     }
483
484   if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
485     {
486       if (setting_insn && DEBUG_INSN_P (setting_insn))
487         n_useless_debug_values++;
488       else
489         n_useless_values++;
490       values_became_useless = 1;
491     }
492   return 1;
493 }
494
495 /* If X is a value with no locations, remove it from the hashtable.  */
496
497 static int
498 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
499 {
500   cselib_val *v = (cselib_val *)*x;
501
502   if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
503     {
504       if (cselib_discard_hook)
505         cselib_discard_hook (v);
506
507       CSELIB_VAL_PTR (v->val_rtx) = NULL;
508       htab_clear_slot (cselib_hash_table, x);
509       unchain_one_value (v);
510       n_useless_values--;
511     }
512
513   return 1;
514 }
515
516 /* Clean out useless values (i.e. those which no longer have locations
517    associated with them) from the hash table.  */
518
519 static void
520 remove_useless_values (void)
521 {
522   cselib_val **p, *v;
523
524   /* First pass: eliminate locations that reference the value.  That in
525      turn can make more values useless.  */
526   do
527     {
528       values_became_useless = 0;
529       htab_traverse (cselib_hash_table, discard_useless_locs, 0);
530     }
531   while (values_became_useless);
532
533   /* Second pass: actually remove the values.  */
534
535   p = &first_containing_mem;
536   for (v = *p; v != &dummy_val; v = v->next_containing_mem)
537     if (v->locs)
538       {
539         *p = v;
540         p = &(*p)->next_containing_mem;
541       }
542   *p = &dummy_val;
543
544   n_useless_values += n_useless_debug_values;
545   n_debug_values -= n_useless_debug_values;
546   n_useless_debug_values = 0;
547
548   htab_traverse (cselib_hash_table, discard_useless_values, 0);
549
550   gcc_assert (!n_useless_values);
551 }
552
553 /* Arrange for a value to not be removed from the hash table even if
554    it becomes useless.  */
555
556 void
557 cselib_preserve_value (cselib_val *v)
558 {
559   PRESERVED_VALUE_P (v->val_rtx) = 1;
560 }
561
562 /* Test whether a value is preserved.  */
563
564 bool
565 cselib_preserved_value_p (cselib_val *v)
566 {
567   return PRESERVED_VALUE_P (v->val_rtx);
568 }
569
570 /* Arrange for a REG value to be assumed constant through the whole function,
571    never invalidated and preserved across cselib_reset_table calls.  */
572
573 void
574 cselib_preserve_cfa_base_value (cselib_val *v)
575 {
576   if (cselib_preserve_constants
577       && v->locs
578       && REG_P (v->locs->loc))
579     cfa_base_preserved_val = v;
580 }
581
582 /* Clean all non-constant expressions in the hash table, but retain
583    their values.  */
584
585 void
586 cselib_preserve_only_values (void)
587 {
588   int i;
589
590   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
591     cselib_invalidate_regno (i, reg_raw_mode[i]);
592
593   cselib_invalidate_mem (callmem);
594
595   remove_useless_values ();
596
597   gcc_assert (first_containing_mem == &dummy_val);
598 }
599
600 /* Return the mode in which a register was last set.  If X is not a
601    register, return its mode.  If the mode in which the register was
602    set is not known, or the value was already clobbered, return
603    VOIDmode.  */
604
605 enum machine_mode
606 cselib_reg_set_mode (const_rtx x)
607 {
608   if (!REG_P (x))
609     return GET_MODE (x);
610
611   if (REG_VALUES (REGNO (x)) == NULL
612       || REG_VALUES (REGNO (x))->elt == NULL)
613     return VOIDmode;
614
615   return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
616 }
617
618 /* Return nonzero if we can prove that X and Y contain the same value, taking
619    our gathered information into account.  */
620
621 int
622 rtx_equal_for_cselib_p (rtx x, rtx y)
623 {
624   enum rtx_code code;
625   const char *fmt;
626   int i;
627
628   if (REG_P (x) || MEM_P (x))
629     {
630       cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
631
632       if (e)
633         x = e->val_rtx;
634     }
635
636   if (REG_P (y) || MEM_P (y))
637     {
638       cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
639
640       if (e)
641         y = e->val_rtx;
642     }
643
644   if (x == y)
645     return 1;
646
647   if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
648     return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
649
650   if (GET_CODE (x) == VALUE)
651     {
652       cselib_val *e = CSELIB_VAL_PTR (x);
653       struct elt_loc_list *l;
654
655       for (l = e->locs; l; l = l->next)
656         {
657           rtx t = l->loc;
658
659           /* Avoid infinite recursion.  */
660           if (REG_P (t) || MEM_P (t))
661             continue;
662           else if (rtx_equal_for_cselib_p (t, y))
663             return 1;
664         }
665
666       return 0;
667     }
668
669   if (GET_CODE (y) == VALUE)
670     {
671       cselib_val *e = CSELIB_VAL_PTR (y);
672       struct elt_loc_list *l;
673
674       for (l = e->locs; l; l = l->next)
675         {
676           rtx t = l->loc;
677
678           if (REG_P (t) || MEM_P (t))
679             continue;
680           else if (rtx_equal_for_cselib_p (x, t))
681             return 1;
682         }
683
684       return 0;
685     }
686
687   if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
688     return 0;
689
690   /* These won't be handled correctly by the code below.  */
691   switch (GET_CODE (x))
692     {
693     case CONST_DOUBLE:
694     case CONST_FIXED:
695     case DEBUG_EXPR:
696       return 0;
697
698     case LABEL_REF:
699       return XEXP (x, 0) == XEXP (y, 0);
700
701     default:
702       break;
703     }
704
705   code = GET_CODE (x);
706   fmt = GET_RTX_FORMAT (code);
707
708   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
709     {
710       int j;
711
712       switch (fmt[i])
713         {
714         case 'w':
715           if (XWINT (x, i) != XWINT (y, i))
716             return 0;
717           break;
718
719         case 'n':
720         case 'i':
721           if (XINT (x, i) != XINT (y, i))
722             return 0;
723           break;
724
725         case 'V':
726         case 'E':
727           /* Two vectors must have the same length.  */
728           if (XVECLEN (x, i) != XVECLEN (y, i))
729             return 0;
730
731           /* And the corresponding elements must match.  */
732           for (j = 0; j < XVECLEN (x, i); j++)
733             if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
734                                           XVECEXP (y, i, j)))
735               return 0;
736           break;
737
738         case 'e':
739           if (i == 1
740               && targetm.commutative_p (x, UNKNOWN)
741               && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
742               && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
743             return 1;
744           if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
745             return 0;
746           break;
747
748         case 'S':
749         case 's':
750           if (strcmp (XSTR (x, i), XSTR (y, i)))
751             return 0;
752           break;
753
754         case 'u':
755           /* These are just backpointers, so they don't matter.  */
756           break;
757
758         case '0':
759         case 't':
760           break;
761
762           /* It is believed that rtx's at this level will never
763              contain anything but integers and other rtx's,
764              except for within LABEL_REFs and SYMBOL_REFs.  */
765         default:
766           gcc_unreachable ();
767         }
768     }
769   return 1;
770 }
771
772 /* We need to pass down the mode of constants through the hash table
773    functions.  For that purpose, wrap them in a CONST of the appropriate
774    mode.  */
775 static rtx
776 wrap_constant (enum machine_mode mode, rtx x)
777 {
778   if (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
779       && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
780     return x;
781   gcc_assert (mode != VOIDmode);
782   return gen_rtx_CONST (mode, x);
783 }
784
785 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
786    For registers and memory locations, we look up their cselib_val structure
787    and return its VALUE element.
788    Possible reasons for return 0 are: the object is volatile, or we couldn't
789    find a register or memory location in the table and CREATE is zero.  If
790    CREATE is nonzero, table elts are created for regs and mem.
791    N.B. this hash function returns the same hash value for RTXes that
792    differ only in the order of operands, thus it is suitable for comparisons
793    that take commutativity into account.
794    If we wanted to also support associative rules, we'd have to use a different
795    strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
796    We used to have a MODE argument for hashing for CONST_INTs, but that
797    didn't make sense, since it caused spurious hash differences between
798     (set (reg:SI 1) (const_int))
799     (plus:SI (reg:SI 2) (reg:SI 1))
800    and
801     (plus:SI (reg:SI 2) (const_int))
802    If the mode is important in any context, it must be checked specifically
803    in a comparison anyway, since relying on hash differences is unsafe.  */
804
805 static unsigned int
806 cselib_hash_rtx (rtx x, int create)
807 {
808   cselib_val *e;
809   int i, j;
810   enum rtx_code code;
811   const char *fmt;
812   unsigned int hash = 0;
813
814   code = GET_CODE (x);
815   hash += (unsigned) code + (unsigned) GET_MODE (x);
816
817   switch (code)
818     {
819     case MEM:
820     case REG:
821       e = cselib_lookup (x, GET_MODE (x), create);
822       if (! e)
823         return 0;
824
825       return e->hash;
826
827     case DEBUG_EXPR:
828       hash += ((unsigned) DEBUG_EXPR << 7)
829               + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
830       return hash ? hash : (unsigned int) DEBUG_EXPR;
831
832     case CONST_INT:
833       hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
834       return hash ? hash : (unsigned int) CONST_INT;
835
836     case CONST_DOUBLE:
837       /* This is like the general case, except that it only counts
838          the integers representing the constant.  */
839       hash += (unsigned) code + (unsigned) GET_MODE (x);
840       if (GET_MODE (x) != VOIDmode)
841         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
842       else
843         hash += ((unsigned) CONST_DOUBLE_LOW (x)
844                  + (unsigned) CONST_DOUBLE_HIGH (x));
845       return hash ? hash : (unsigned int) CONST_DOUBLE;
846
847     case CONST_FIXED:
848       hash += (unsigned int) code + (unsigned int) GET_MODE (x);
849       hash += fixed_hash (CONST_FIXED_VALUE (x));
850       return hash ? hash : (unsigned int) CONST_FIXED;
851
852     case CONST_VECTOR:
853       {
854         int units;
855         rtx elt;
856
857         units = CONST_VECTOR_NUNITS (x);
858
859         for (i = 0; i < units; ++i)
860           {
861             elt = CONST_VECTOR_ELT (x, i);
862             hash += cselib_hash_rtx (elt, 0);
863           }
864
865         return hash;
866       }
867
868       /* Assume there is only one rtx object for any given label.  */
869     case LABEL_REF:
870       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
871          differences and differences between each stage's debugging dumps.  */
872       hash += (((unsigned int) LABEL_REF << 7)
873                + CODE_LABEL_NUMBER (XEXP (x, 0)));
874       return hash ? hash : (unsigned int) LABEL_REF;
875
876     case SYMBOL_REF:
877       {
878         /* Don't hash on the symbol's address to avoid bootstrap differences.
879            Different hash values may cause expressions to be recorded in
880            different orders and thus different registers to be used in the
881            final assembler.  This also avoids differences in the dump files
882            between various stages.  */
883         unsigned int h = 0;
884         const unsigned char *p = (const unsigned char *) XSTR (x, 0);
885
886         while (*p)
887           h += (h << 7) + *p++; /* ??? revisit */
888
889         hash += ((unsigned int) SYMBOL_REF << 7) + h;
890         return hash ? hash : (unsigned int) SYMBOL_REF;
891       }
892
893     case PRE_DEC:
894     case PRE_INC:
895     case POST_DEC:
896     case POST_INC:
897     case POST_MODIFY:
898     case PRE_MODIFY:
899     case PC:
900     case CC0:
901     case CALL:
902     case UNSPEC_VOLATILE:
903       return 0;
904
905     case ASM_OPERANDS:
906       if (MEM_VOLATILE_P (x))
907         return 0;
908
909       break;
910
911     default:
912       break;
913     }
914
915   i = GET_RTX_LENGTH (code) - 1;
916   fmt = GET_RTX_FORMAT (code);
917   for (; i >= 0; i--)
918     {
919       switch (fmt[i])
920         {
921         case 'e':
922           {
923             rtx tem = XEXP (x, i);
924             unsigned int tem_hash = cselib_hash_rtx (tem, create);
925
926             if (tem_hash == 0)
927               return 0;
928
929             hash += tem_hash;
930           }
931           break;
932         case 'E':
933           for (j = 0; j < XVECLEN (x, i); j++)
934             {
935               unsigned int tem_hash
936                 = cselib_hash_rtx (XVECEXP (x, i, j), create);
937
938               if (tem_hash == 0)
939                 return 0;
940
941               hash += tem_hash;
942             }
943           break;
944
945         case 's':
946           {
947             const unsigned char *p = (const unsigned char *) XSTR (x, i);
948
949             if (p)
950               while (*p)
951                 hash += *p++;
952             break;
953           }
954
955         case 'i':
956           hash += XINT (x, i);
957           break;
958
959         case '0':
960         case 't':
961           /* unused */
962           break;
963
964         default:
965           gcc_unreachable ();
966         }
967     }
968
969   return hash ? hash : 1 + (unsigned int) GET_CODE (x);
970 }
971
972 /* Create a new value structure for VALUE and initialize it.  The mode of the
973    value is MODE.  */
974
975 static inline cselib_val *
976 new_cselib_val (unsigned int hash, enum machine_mode mode, rtx x)
977 {
978   cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
979
980   gcc_assert (hash);
981   gcc_assert (next_uid);
982
983   e->hash = hash;
984   e->uid = next_uid++;
985   /* We use an alloc pool to allocate this RTL construct because it
986      accounts for about 8% of the overall memory usage.  We know
987      precisely when we can have VALUE RTXen (when cselib is active)
988      so we don't need to put them in garbage collected memory.
989      ??? Why should a VALUE be an RTX in the first place?  */
990   e->val_rtx = (rtx) pool_alloc (value_pool);
991   memset (e->val_rtx, 0, RTX_HDR_SIZE);
992   PUT_CODE (e->val_rtx, VALUE);
993   PUT_MODE (e->val_rtx, mode);
994   CSELIB_VAL_PTR (e->val_rtx) = e;
995   e->addr_list = 0;
996   e->locs = 0;
997   e->next_containing_mem = 0;
998
999   if (dump_file && (dump_flags & TDF_DETAILS))
1000     {
1001       fprintf (dump_file, "cselib value %u:%u ", e->uid, hash);
1002       if (flag_dump_noaddr || flag_dump_unnumbered)
1003         fputs ("# ", dump_file);
1004       else
1005         fprintf (dump_file, "%p ", (void*)e);
1006       print_rtl_single (dump_file, x);
1007       fputc ('\n', dump_file);
1008     }
1009
1010   return e;
1011 }
1012
1013 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
1014    contains the data at this address.  X is a MEM that represents the
1015    value.  Update the two value structures to represent this situation.  */
1016
1017 static void
1018 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
1019 {
1020   struct elt_loc_list *l;
1021
1022   /* Avoid duplicates.  */
1023   for (l = mem_elt->locs; l; l = l->next)
1024     if (MEM_P (l->loc)
1025         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
1026       {
1027         promote_debug_loc (l);
1028         return;
1029       }
1030
1031   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
1032   mem_elt->locs
1033     = new_elt_loc_list (mem_elt->locs,
1034                         replace_equiv_address_nv (x, addr_elt->val_rtx));
1035   if (mem_elt->next_containing_mem == NULL)
1036     {
1037       mem_elt->next_containing_mem = first_containing_mem;
1038       first_containing_mem = mem_elt;
1039     }
1040 }
1041
1042 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
1043    If CREATE, make a new one if we haven't seen it before.  */
1044
1045 static cselib_val *
1046 cselib_lookup_mem (rtx x, int create)
1047 {
1048   enum machine_mode mode = GET_MODE (x);
1049   void **slot;
1050   cselib_val *addr;
1051   cselib_val *mem_elt;
1052   struct elt_list *l;
1053
1054   if (MEM_VOLATILE_P (x) || mode == BLKmode
1055       || !cselib_record_memory
1056       || (FLOAT_MODE_P (mode) && flag_float_store))
1057     return 0;
1058
1059   /* Look up the value for the address.  */
1060   addr = cselib_lookup (XEXP (x, 0), mode, create);
1061   if (! addr)
1062     return 0;
1063
1064   /* Find a value that describes a value of our mode at that address.  */
1065   for (l = addr->addr_list; l; l = l->next)
1066     if (GET_MODE (l->elt->val_rtx) == mode)
1067       {
1068         promote_debug_loc (l->elt->locs);
1069         return l->elt;
1070       }
1071
1072   if (! create)
1073     return 0;
1074
1075   mem_elt = new_cselib_val (next_uid, mode, x);
1076   add_mem_for_addr (addr, mem_elt, x);
1077   slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1078                                    mem_elt->hash, INSERT);
1079   *slot = mem_elt;
1080   return mem_elt;
1081 }
1082
1083 /* Search thru the possible substitutions in P.  We prefer a non reg
1084    substitution because this allows us to expand the tree further.  If
1085    we find, just a reg, take the lowest regno.  There may be several
1086    non-reg results, we just take the first one because they will all
1087    expand to the same place.  */
1088
1089 static rtx
1090 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
1091             int max_depth)
1092 {
1093   rtx reg_result = NULL;
1094   unsigned int regno = UINT_MAX;
1095   struct elt_loc_list *p_in = p;
1096
1097   for (; p; p = p -> next)
1098     {
1099       /* Avoid infinite recursion trying to expand a reg into a
1100          the same reg.  */
1101       if ((REG_P (p->loc))
1102           && (REGNO (p->loc) < regno)
1103           && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
1104         {
1105           reg_result = p->loc;
1106           regno = REGNO (p->loc);
1107         }
1108       /* Avoid infinite recursion and do not try to expand the
1109          value.  */
1110       else if (GET_CODE (p->loc) == VALUE
1111                && CSELIB_VAL_PTR (p->loc)->locs == p_in)
1112         continue;
1113       else if (!REG_P (p->loc))
1114         {
1115           rtx result, note;
1116           if (dump_file && (dump_flags & TDF_DETAILS))
1117             {
1118               print_inline_rtx (dump_file, p->loc, 0);
1119               fprintf (dump_file, "\n");
1120             }
1121           if (GET_CODE (p->loc) == LO_SUM
1122               && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
1123               && p->setting_insn
1124               && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
1125               && XEXP (note, 0) == XEXP (p->loc, 1))
1126             return XEXP (p->loc, 1);
1127           result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1128           if (result)
1129             return result;
1130         }
1131
1132     }
1133
1134   if (regno != UINT_MAX)
1135     {
1136       rtx result;
1137       if (dump_file && (dump_flags & TDF_DETAILS))
1138         fprintf (dump_file, "r%d\n", regno);
1139
1140       result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1141       if (result)
1142         return result;
1143     }
1144
1145   if (dump_file && (dump_flags & TDF_DETAILS))
1146     {
1147       if (reg_result)
1148         {
1149           print_inline_rtx (dump_file, reg_result, 0);
1150           fprintf (dump_file, "\n");
1151         }
1152       else
1153         fprintf (dump_file, "NULL\n");
1154     }
1155   return reg_result;
1156 }
1157
1158
1159 /* Forward substitute and expand an expression out to its roots.
1160    This is the opposite of common subexpression.  Because local value
1161    numbering is such a weak optimization, the expanded expression is
1162    pretty much unique (not from a pointer equals point of view but
1163    from a tree shape point of view.
1164
1165    This function returns NULL if the expansion fails.  The expansion
1166    will fail if there is no value number for one of the operands or if
1167    one of the operands has been overwritten between the current insn
1168    and the beginning of the basic block.  For instance x has no
1169    expansion in:
1170
1171    r1 <- r1 + 3
1172    x <- r1 + 8
1173
1174    REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1175    It is clear on return.  */
1176
1177 rtx
1178 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1179 {
1180   struct expand_value_data evd;
1181
1182   evd.regs_active = regs_active;
1183   evd.callback = NULL;
1184   evd.callback_arg = NULL;
1185   evd.dummy = false;
1186
1187   return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1188 }
1189
1190 /* Same as cselib_expand_value_rtx, but using a callback to try to
1191    resolve some expressions.  The CB function should return ORIG if it
1192    can't or does not want to deal with a certain RTX.  Any other
1193    return value, including NULL, will be used as the expansion for
1194    VALUE, without any further changes.  */
1195
1196 rtx
1197 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1198                             cselib_expand_callback cb, void *data)
1199 {
1200   struct expand_value_data evd;
1201
1202   evd.regs_active = regs_active;
1203   evd.callback = cb;
1204   evd.callback_arg = data;
1205   evd.dummy = false;
1206
1207   return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1208 }
1209
1210 /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1211    or simplified.  Useful to find out whether cselib_expand_value_rtx_cb
1212    would return NULL or non-NULL, without allocating new rtx.  */
1213
1214 bool
1215 cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1216                                   cselib_expand_callback cb, void *data)
1217 {
1218   struct expand_value_data evd;
1219
1220   evd.regs_active = regs_active;
1221   evd.callback = cb;
1222   evd.callback_arg = data;
1223   evd.dummy = true;
1224
1225   return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL;
1226 }
1227
1228 /* Internal implementation of cselib_expand_value_rtx and
1229    cselib_expand_value_rtx_cb.  */
1230
1231 static rtx
1232 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1233                            int max_depth)
1234 {
1235   rtx copy, scopy;
1236   int i, j;
1237   RTX_CODE code;
1238   const char *format_ptr;
1239   enum machine_mode mode;
1240
1241   code = GET_CODE (orig);
1242
1243   /* For the context of dse, if we end up expand into a huge tree, we
1244      will not have a useful address, so we might as well just give up
1245      quickly.  */
1246   if (max_depth <= 0)
1247     return NULL;
1248
1249   switch (code)
1250     {
1251     case REG:
1252       {
1253         struct elt_list *l = REG_VALUES (REGNO (orig));
1254
1255         if (l && l->elt == NULL)
1256           l = l->next;
1257         for (; l; l = l->next)
1258           if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1259             {
1260               rtx result;
1261               int regno = REGNO (orig);
1262
1263               /* The only thing that we are not willing to do (this
1264                  is requirement of dse and if others potential uses
1265                  need this function we should add a parm to control
1266                  it) is that we will not substitute the
1267                  STACK_POINTER_REGNUM, FRAME_POINTER or the
1268                  HARD_FRAME_POINTER.
1269
1270                  These expansions confuses the code that notices that
1271                  stores into the frame go dead at the end of the
1272                  function and that the frame is not effected by calls
1273                  to subroutines.  If you allow the
1274                  STACK_POINTER_REGNUM substitution, then dse will
1275                  think that parameter pushing also goes dead which is
1276                  wrong.  If you allow the FRAME_POINTER or the
1277                  HARD_FRAME_POINTER then you lose the opportunity to
1278                  make the frame assumptions.  */
1279               if (regno == STACK_POINTER_REGNUM
1280                   || regno == FRAME_POINTER_REGNUM
1281                   || regno == HARD_FRAME_POINTER_REGNUM)
1282                 return orig;
1283
1284               bitmap_set_bit (evd->regs_active, regno);
1285
1286               if (dump_file && (dump_flags & TDF_DETAILS))
1287                 fprintf (dump_file, "expanding: r%d into: ", regno);
1288
1289               result = expand_loc (l->elt->locs, evd, max_depth);
1290               bitmap_clear_bit (evd->regs_active, regno);
1291
1292               if (result)
1293                 return result;
1294               else
1295                 return orig;
1296             }
1297       }
1298
1299     case CONST_INT:
1300     case CONST_DOUBLE:
1301     case CONST_VECTOR:
1302     case SYMBOL_REF:
1303     case CODE_LABEL:
1304     case PC:
1305     case CC0:
1306     case SCRATCH:
1307       /* SCRATCH must be shared because they represent distinct values.  */
1308       return orig;
1309     case CLOBBER:
1310       if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1311         return orig;
1312       break;
1313
1314     case CONST:
1315       if (shared_const_p (orig))
1316         return orig;
1317       break;
1318
1319     case SUBREG:
1320       {
1321         rtx subreg;
1322
1323         if (evd->callback)
1324           {
1325             subreg = evd->callback (orig, evd->regs_active, max_depth,
1326                                     evd->callback_arg);
1327             if (subreg != orig)
1328               return subreg;
1329           }
1330
1331         subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1332                                             max_depth - 1);
1333         if (!subreg)
1334           return NULL;
1335         scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1336                                      GET_MODE (SUBREG_REG (orig)),
1337                                      SUBREG_BYTE (orig));
1338         if (scopy == NULL
1339             || (GET_CODE (scopy) == SUBREG
1340                 && !REG_P (SUBREG_REG (scopy))
1341                 && !MEM_P (SUBREG_REG (scopy))))
1342           return NULL;
1343
1344         return scopy;
1345       }
1346
1347     case VALUE:
1348       {
1349         rtx result;
1350
1351         if (dump_file && (dump_flags & TDF_DETAILS))
1352           {
1353             fputs ("\nexpanding ", dump_file);
1354             print_rtl_single (dump_file, orig);
1355             fputs (" into...", dump_file);
1356           }
1357
1358         if (evd->callback)
1359           {
1360             result = evd->callback (orig, evd->regs_active, max_depth,
1361                                     evd->callback_arg);
1362
1363             if (result != orig)
1364               return result;
1365           }
1366
1367         result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1368         return result;
1369       }
1370
1371     case DEBUG_EXPR:
1372       if (evd->callback)
1373         return evd->callback (orig, evd->regs_active, max_depth,
1374                               evd->callback_arg);
1375       return orig;
1376
1377     default:
1378       break;
1379     }
1380
1381   /* Copy the various flags, fields, and other information.  We assume
1382      that all fields need copying, and then clear the fields that should
1383      not be copied.  That is the sensible default behavior, and forces
1384      us to explicitly document why we are *not* copying a flag.  */
1385   if (evd->dummy)
1386     copy = NULL;
1387   else
1388     copy = shallow_copy_rtx (orig);
1389
1390   format_ptr = GET_RTX_FORMAT (code);
1391
1392   for (i = 0; i < GET_RTX_LENGTH (code); i++)
1393     switch (*format_ptr++)
1394       {
1395       case 'e':
1396         if (XEXP (orig, i) != NULL)
1397           {
1398             rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1399                                                     max_depth - 1);
1400             if (!result)
1401               return NULL;
1402             if (copy)
1403               XEXP (copy, i) = result;
1404           }
1405         break;
1406
1407       case 'E':
1408       case 'V':
1409         if (XVEC (orig, i) != NULL)
1410           {
1411             if (copy)
1412               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1413             for (j = 0; j < XVECLEN (orig, i); j++)
1414               {
1415                 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1416                                                         evd, max_depth - 1);
1417                 if (!result)
1418                   return NULL;
1419                 if (copy)
1420                   XVECEXP (copy, i, j) = result;
1421               }
1422           }
1423         break;
1424
1425       case 't':
1426       case 'w':
1427       case 'i':
1428       case 's':
1429       case 'S':
1430       case 'T':
1431       case 'u':
1432       case 'B':
1433       case '0':
1434         /* These are left unchanged.  */
1435         break;
1436
1437       default:
1438         gcc_unreachable ();
1439       }
1440
1441   if (evd->dummy)
1442     return orig;
1443
1444   mode = GET_MODE (copy);
1445   /* If an operand has been simplified into CONST_INT, which doesn't
1446      have a mode and the mode isn't derivable from whole rtx's mode,
1447      try simplify_*_operation first with mode from original's operand
1448      and as a fallback wrap CONST_INT into gen_rtx_CONST.  */
1449   scopy = copy;
1450   switch (GET_RTX_CLASS (code))
1451     {
1452     case RTX_UNARY:
1453       if (CONST_INT_P (XEXP (copy, 0))
1454           && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1455         {
1456           scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1457                                             GET_MODE (XEXP (orig, 0)));
1458           if (scopy)
1459             return scopy;
1460         }
1461       break;
1462     case RTX_COMM_ARITH:
1463     case RTX_BIN_ARITH:
1464       /* These expressions can derive operand modes from the whole rtx's mode.  */
1465       break;
1466     case RTX_TERNARY:
1467     case RTX_BITFIELD_OPS:
1468       if (CONST_INT_P (XEXP (copy, 0))
1469           && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1470         {
1471           scopy = simplify_ternary_operation (code, mode,
1472                                               GET_MODE (XEXP (orig, 0)),
1473                                               XEXP (copy, 0), XEXP (copy, 1),
1474                                               XEXP (copy, 2));
1475           if (scopy)
1476             return scopy;
1477         }
1478       break;
1479     case RTX_COMPARE:
1480     case RTX_COMM_COMPARE:
1481       if (CONST_INT_P (XEXP (copy, 0))
1482           && GET_MODE (XEXP (copy, 1)) == VOIDmode
1483           && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1484               || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1485         {
1486           scopy = simplify_relational_operation (code, mode,
1487                                                  (GET_MODE (XEXP (orig, 0))
1488                                                   != VOIDmode)
1489                                                  ? GET_MODE (XEXP (orig, 0))
1490                                                  : GET_MODE (XEXP (orig, 1)),
1491                                                  XEXP (copy, 0),
1492                                                  XEXP (copy, 1));
1493           if (scopy)
1494             return scopy;
1495         }
1496       break;
1497     default:
1498       break;
1499     }
1500   scopy = simplify_rtx (copy);
1501   if (scopy)
1502     return scopy;
1503   return copy;
1504 }
1505
1506 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1507    with VALUE expressions.  This way, it becomes independent of changes
1508    to registers and memory.
1509    X isn't actually modified; if modifications are needed, new rtl is
1510    allocated.  However, the return value can share rtl with X.  */
1511
1512 rtx
1513 cselib_subst_to_values (rtx x)
1514 {
1515   enum rtx_code code = GET_CODE (x);
1516   const char *fmt = GET_RTX_FORMAT (code);
1517   cselib_val *e;
1518   struct elt_list *l;
1519   rtx copy = x;
1520   int i;
1521
1522   switch (code)
1523     {
1524     case REG:
1525       l = REG_VALUES (REGNO (x));
1526       if (l && l->elt == NULL)
1527         l = l->next;
1528       for (; l; l = l->next)
1529         if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1530           return l->elt->val_rtx;
1531
1532       gcc_unreachable ();
1533
1534     case MEM:
1535       e = cselib_lookup_mem (x, 0);
1536       if (! e)
1537         {
1538           /* This happens for autoincrements.  Assign a value that doesn't
1539              match any other.  */
1540           e = new_cselib_val (next_uid, GET_MODE (x), x);
1541         }
1542       return e->val_rtx;
1543
1544     case CONST_DOUBLE:
1545     case CONST_VECTOR:
1546     case CONST_INT:
1547     case CONST_FIXED:
1548       return x;
1549
1550     case POST_INC:
1551     case PRE_INC:
1552     case POST_DEC:
1553     case PRE_DEC:
1554     case POST_MODIFY:
1555     case PRE_MODIFY:
1556       e = new_cselib_val (next_uid, GET_MODE (x), x);
1557       return e->val_rtx;
1558
1559     default:
1560       break;
1561     }
1562
1563   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1564     {
1565       if (fmt[i] == 'e')
1566         {
1567           rtx t = cselib_subst_to_values (XEXP (x, i));
1568
1569           if (t != XEXP (x, i))
1570             {
1571               if (x == copy)
1572                 copy = shallow_copy_rtx (x);
1573               XEXP (copy, i) = t;
1574             }
1575         }
1576       else if (fmt[i] == 'E')
1577         {
1578           int j;
1579
1580           for (j = 0; j < XVECLEN (x, i); j++)
1581             {
1582               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1583
1584               if (t != XVECEXP (x, i, j))
1585                 {
1586                   if (XVEC (x, i) == XVEC (copy, i))
1587                     {
1588                       if (x == copy)
1589                         copy = shallow_copy_rtx (x);
1590                       XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
1591                     }
1592                   XVECEXP (copy, i, j) = t;
1593                 }
1594             }
1595         }
1596     }
1597
1598   return copy;
1599 }
1600
1601 /* Look up the rtl expression X in our tables and return the value it has.
1602    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
1603    we create a new one if possible, using mode MODE if X doesn't have a mode
1604    (i.e. because it's a constant).  */
1605
1606 static cselib_val *
1607 cselib_lookup_1 (rtx x, enum machine_mode mode, int create)
1608 {
1609   void **slot;
1610   cselib_val *e;
1611   unsigned int hashval;
1612
1613   if (GET_MODE (x) != VOIDmode)
1614     mode = GET_MODE (x);
1615
1616   if (GET_CODE (x) == VALUE)
1617     return CSELIB_VAL_PTR (x);
1618
1619   if (REG_P (x))
1620     {
1621       struct elt_list *l;
1622       unsigned int i = REGNO (x);
1623
1624       l = REG_VALUES (i);
1625       if (l && l->elt == NULL)
1626         l = l->next;
1627       for (; l; l = l->next)
1628         if (mode == GET_MODE (l->elt->val_rtx))
1629           {
1630             promote_debug_loc (l->elt->locs);
1631             return l->elt;
1632           }
1633
1634       if (! create)
1635         return 0;
1636
1637       if (i < FIRST_PSEUDO_REGISTER)
1638         {
1639           unsigned int n = hard_regno_nregs[i][mode];
1640
1641           if (n > max_value_regs)
1642             max_value_regs = n;
1643         }
1644
1645       e = new_cselib_val (next_uid, GET_MODE (x), x);
1646       e->locs = new_elt_loc_list (e->locs, x);
1647       if (REG_VALUES (i) == 0)
1648         {
1649           /* Maintain the invariant that the first entry of
1650              REG_VALUES, if present, must be the value used to set the
1651              register, or NULL.  */
1652           used_regs[n_used_regs++] = i;
1653           REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1654         }
1655       REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1656       slot = htab_find_slot_with_hash (cselib_hash_table, x, e->hash, INSERT);
1657       *slot = e;
1658       return e;
1659     }
1660
1661   if (MEM_P (x))
1662     return cselib_lookup_mem (x, create);
1663
1664   hashval = cselib_hash_rtx (x, create);
1665   /* Can't even create if hashing is not possible.  */
1666   if (! hashval)
1667     return 0;
1668
1669   slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1670                                    hashval, create ? INSERT : NO_INSERT);
1671   if (slot == 0)
1672     return 0;
1673
1674   e = (cselib_val *) *slot;
1675   if (e)
1676     return e;
1677
1678   e = new_cselib_val (hashval, mode, x);
1679
1680   /* We have to fill the slot before calling cselib_subst_to_values:
1681      the hash table is inconsistent until we do so, and
1682      cselib_subst_to_values will need to do lookups.  */
1683   *slot = (void *) e;
1684   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1685   return e;
1686 }
1687
1688 /* Wrapper for cselib_lookup, that indicates X is in INSN.  */
1689
1690 cselib_val *
1691 cselib_lookup_from_insn (rtx x, enum machine_mode mode,
1692                          int create, rtx insn)
1693 {
1694   cselib_val *ret;
1695
1696   gcc_assert (!cselib_current_insn);
1697   cselib_current_insn = insn;
1698
1699   ret = cselib_lookup (x, mode, create);
1700
1701   cselib_current_insn = NULL;
1702
1703   return ret;
1704 }
1705
1706 /* Wrapper for cselib_lookup_1, that logs the lookup result and
1707    maintains invariants related with debug insns.  */
1708
1709 cselib_val *
1710 cselib_lookup (rtx x, enum machine_mode mode, int create)
1711 {
1712   cselib_val *ret = cselib_lookup_1 (x, mode, create);
1713
1714   /* ??? Should we return NULL if we're not to create an entry, the
1715      found loc is a debug loc and cselib_current_insn is not DEBUG?
1716      If so, we should also avoid converting val to non-DEBUG; probably
1717      easiest setting cselib_current_insn to NULL before the call
1718      above.  */
1719
1720   if (dump_file && (dump_flags & TDF_DETAILS))
1721     {
1722       fputs ("cselib lookup ", dump_file);
1723       print_inline_rtx (dump_file, x, 2);
1724       fprintf (dump_file, " => %u:%u\n",
1725                ret ? ret->uid : 0,
1726                ret ? ret->hash : 0);
1727     }
1728
1729   return ret;
1730 }
1731
1732 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
1733    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
1734    is used to determine how many hard registers are being changed.  If MODE
1735    is VOIDmode, then only REGNO is being changed; this is used when
1736    invalidating call clobbered registers across a call.  */
1737
1738 static void
1739 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1740 {
1741   unsigned int endregno;
1742   unsigned int i;
1743
1744   /* If we see pseudos after reload, something is _wrong_.  */
1745   gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1746               || reg_renumber[regno] < 0);
1747
1748   /* Determine the range of registers that must be invalidated.  For
1749      pseudos, only REGNO is affected.  For hard regs, we must take MODE
1750      into account, and we must also invalidate lower register numbers
1751      if they contain values that overlap REGNO.  */
1752   if (regno < FIRST_PSEUDO_REGISTER)
1753     {
1754       gcc_assert (mode != VOIDmode);
1755
1756       if (regno < max_value_regs)
1757         i = 0;
1758       else
1759         i = regno - max_value_regs;
1760
1761       endregno = end_hard_regno (mode, regno);
1762     }
1763   else
1764     {
1765       i = regno;
1766       endregno = regno + 1;
1767     }
1768
1769   for (; i < endregno; i++)
1770     {
1771       struct elt_list **l = &REG_VALUES (i);
1772
1773       /* Go through all known values for this reg; if it overlaps the range
1774          we're invalidating, remove the value.  */
1775       while (*l)
1776         {
1777           cselib_val *v = (*l)->elt;
1778           bool had_locs;
1779           rtx setting_insn;
1780           struct elt_loc_list **p;
1781           unsigned int this_last = i;
1782
1783           if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1784             this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1785
1786           if (this_last < regno || v == NULL || v == cfa_base_preserved_val)
1787             {
1788               l = &(*l)->next;
1789               continue;
1790             }
1791
1792           /* We have an overlap.  */
1793           if (*l == REG_VALUES (i))
1794             {
1795               /* Maintain the invariant that the first entry of
1796                  REG_VALUES, if present, must be the value used to set
1797                  the register, or NULL.  This is also nice because
1798                  then we won't push the same regno onto user_regs
1799                  multiple times.  */
1800               (*l)->elt = NULL;
1801               l = &(*l)->next;
1802             }
1803           else
1804             unchain_one_elt_list (l);
1805
1806           had_locs = v->locs != NULL;
1807           setting_insn = v->locs ? v->locs->setting_insn : NULL;
1808
1809           /* Now, we clear the mapping from value to reg.  It must exist, so
1810              this code will crash intentionally if it doesn't.  */
1811           for (p = &v->locs; ; p = &(*p)->next)
1812             {
1813               rtx x = (*p)->loc;
1814
1815               if (REG_P (x) && REGNO (x) == i)
1816                 {
1817                   unchain_one_elt_loc_list (p);
1818                   break;
1819                 }
1820             }
1821
1822           if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1823             {
1824               if (setting_insn && DEBUG_INSN_P (setting_insn))
1825                 n_useless_debug_values++;
1826               else
1827                 n_useless_values++;
1828             }
1829         }
1830     }
1831 }
1832 \f
1833 /* Return 1 if X has a value that can vary even between two
1834    executions of the program.  0 means X can be compared reliably
1835    against certain constants or near-constants.  */
1836
1837 static bool
1838 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1839 {
1840   /* We actually don't need to verify very hard.  This is because
1841      if X has actually changed, we invalidate the memory anyway,
1842      so assume that all common memory addresses are
1843      invariant.  */
1844   return 0;
1845 }
1846
1847 /* Invalidate any locations in the table which are changed because of a
1848    store to MEM_RTX.  If this is called because of a non-const call
1849    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1850
1851 static void
1852 cselib_invalidate_mem (rtx mem_rtx)
1853 {
1854   cselib_val **vp, *v, *next;
1855   int num_mems = 0;
1856   rtx mem_addr;
1857
1858   mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1859   mem_rtx = canon_rtx (mem_rtx);
1860
1861   vp = &first_containing_mem;
1862   for (v = *vp; v != &dummy_val; v = next)
1863     {
1864       bool has_mem = false;
1865       struct elt_loc_list **p = &v->locs;
1866       bool had_locs = v->locs != NULL;
1867       rtx setting_insn = v->locs ? v->locs->setting_insn : NULL;
1868
1869       while (*p)
1870         {
1871           rtx x = (*p)->loc;
1872           cselib_val *addr;
1873           struct elt_list **mem_chain;
1874
1875           /* MEMs may occur in locations only at the top level; below
1876              that every MEM or REG is substituted by its VALUE.  */
1877           if (!MEM_P (x))
1878             {
1879               p = &(*p)->next;
1880               continue;
1881             }
1882           if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1883               && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1884                                           x, NULL_RTX, cselib_rtx_varies_p))
1885             {
1886               has_mem = true;
1887               num_mems++;
1888               p = &(*p)->next;
1889               continue;
1890             }
1891
1892           /* This one overlaps.  */
1893           /* We must have a mapping from this MEM's address to the
1894              value (E).  Remove that, too.  */
1895           addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1896           mem_chain = &addr->addr_list;
1897           for (;;)
1898             {
1899               if ((*mem_chain)->elt == v)
1900                 {
1901                   unchain_one_elt_list (mem_chain);
1902                   break;
1903                 }
1904
1905               mem_chain = &(*mem_chain)->next;
1906             }
1907
1908           unchain_one_elt_loc_list (p);
1909         }
1910
1911       if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1912         {
1913           if (setting_insn && DEBUG_INSN_P (setting_insn))
1914             n_useless_debug_values++;
1915           else
1916             n_useless_values++;
1917         }
1918
1919       next = v->next_containing_mem;
1920       if (has_mem)
1921         {
1922           *vp = v;
1923           vp = &(*vp)->next_containing_mem;
1924         }
1925       else
1926         v->next_containing_mem = NULL;
1927     }
1928   *vp = &dummy_val;
1929 }
1930
1931 /* Invalidate DEST, which is being assigned to or clobbered.  */
1932
1933 void
1934 cselib_invalidate_rtx (rtx dest)
1935 {
1936   while (GET_CODE (dest) == SUBREG
1937          || GET_CODE (dest) == ZERO_EXTRACT
1938          || GET_CODE (dest) == STRICT_LOW_PART)
1939     dest = XEXP (dest, 0);
1940
1941   if (REG_P (dest))
1942     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1943   else if (MEM_P (dest))
1944     cselib_invalidate_mem (dest);
1945
1946   /* Some machines don't define AUTO_INC_DEC, but they still use push
1947      instructions.  We need to catch that case here in order to
1948      invalidate the stack pointer correctly.  Note that invalidating
1949      the stack pointer is different from invalidating DEST.  */
1950   if (push_operand (dest, GET_MODE (dest)))
1951     cselib_invalidate_rtx (stack_pointer_rtx);
1952 }
1953
1954 /* A wrapper for cselib_invalidate_rtx to be called via note_stores.  */
1955
1956 static void
1957 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1958                                    void *data ATTRIBUTE_UNUSED)
1959 {
1960   cselib_invalidate_rtx (dest);
1961 }
1962
1963 /* Record the result of a SET instruction.  DEST is being set; the source
1964    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1965    describes its address.  */
1966
1967 static void
1968 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1969 {
1970   int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1971
1972   if (src_elt == 0 || side_effects_p (dest))
1973     return;
1974
1975   if (dreg >= 0)
1976     {
1977       if (dreg < FIRST_PSEUDO_REGISTER)
1978         {
1979           unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1980
1981           if (n > max_value_regs)
1982             max_value_regs = n;
1983         }
1984
1985       if (REG_VALUES (dreg) == 0)
1986         {
1987           used_regs[n_used_regs++] = dreg;
1988           REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1989         }
1990       else
1991         {
1992           /* The register should have been invalidated.  */
1993           gcc_assert (REG_VALUES (dreg)->elt == 0);
1994           REG_VALUES (dreg)->elt = src_elt;
1995         }
1996
1997       if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1998         n_useless_values--;
1999       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
2000     }
2001   else if (MEM_P (dest) && dest_addr_elt != 0
2002            && cselib_record_memory)
2003     {
2004       if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
2005         n_useless_values--;
2006       add_mem_for_addr (dest_addr_elt, src_elt, dest);
2007     }
2008 }
2009
2010 /* There is no good way to determine how many elements there can be
2011    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
2012 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
2013
2014 /* Record the effects of any sets in INSN.  */
2015 static void
2016 cselib_record_sets (rtx insn)
2017 {
2018   int n_sets = 0;
2019   int i;
2020   struct cselib_set sets[MAX_SETS];
2021   rtx body = PATTERN (insn);
2022   rtx cond = 0;
2023
2024   body = PATTERN (insn);
2025   if (GET_CODE (body) == COND_EXEC)
2026     {
2027       cond = COND_EXEC_TEST (body);
2028       body = COND_EXEC_CODE (body);
2029     }
2030
2031   /* Find all sets.  */
2032   if (GET_CODE (body) == SET)
2033     {
2034       sets[0].src = SET_SRC (body);
2035       sets[0].dest = SET_DEST (body);
2036       n_sets = 1;
2037     }
2038   else if (GET_CODE (body) == PARALLEL)
2039     {
2040       /* Look through the PARALLEL and record the values being
2041          set, if possible.  Also handle any CLOBBERs.  */
2042       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
2043         {
2044           rtx x = XVECEXP (body, 0, i);
2045
2046           if (GET_CODE (x) == SET)
2047             {
2048               sets[n_sets].src = SET_SRC (x);
2049               sets[n_sets].dest = SET_DEST (x);
2050               n_sets++;
2051             }
2052         }
2053     }
2054
2055   if (n_sets == 1
2056       && MEM_P (sets[0].src)
2057       && !cselib_record_memory
2058       && MEM_READONLY_P (sets[0].src))
2059     {
2060       rtx note = find_reg_equal_equiv_note (insn);
2061
2062       if (note && CONSTANT_P (XEXP (note, 0)))
2063         sets[0].src = XEXP (note, 0);
2064     }
2065
2066   /* Look up the values that are read.  Do this before invalidating the
2067      locations that are written.  */
2068   for (i = 0; i < n_sets; i++)
2069     {
2070       rtx dest = sets[i].dest;
2071
2072       /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
2073          the low part after invalidating any knowledge about larger modes.  */
2074       if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
2075         sets[i].dest = dest = XEXP (dest, 0);
2076
2077       /* We don't know how to record anything but REG or MEM.  */
2078       if (REG_P (dest)
2079           || (MEM_P (dest) && cselib_record_memory))
2080         {
2081           rtx src = sets[i].src;
2082           if (cond)
2083             src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
2084           sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
2085           if (MEM_P (dest))
2086             {
2087               enum machine_mode address_mode
2088                 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest));
2089
2090               sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
2091                                                      address_mode, 1);
2092             }
2093           else
2094             sets[i].dest_addr_elt = 0;
2095         }
2096     }
2097
2098   if (cselib_record_sets_hook)
2099     cselib_record_sets_hook (insn, sets, n_sets);
2100
2101   /* Invalidate all locations written by this insn.  Note that the elts we
2102      looked up in the previous loop aren't affected, just some of their
2103      locations may go away.  */
2104   note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
2105
2106   /* If this is an asm, look for duplicate sets.  This can happen when the
2107      user uses the same value as an output multiple times.  This is valid
2108      if the outputs are not actually used thereafter.  Treat this case as
2109      if the value isn't actually set.  We do this by smashing the destination
2110      to pc_rtx, so that we won't record the value later.  */
2111   if (n_sets >= 2 && asm_noperands (body) >= 0)
2112     {
2113       for (i = 0; i < n_sets; i++)
2114         {
2115           rtx dest = sets[i].dest;
2116           if (REG_P (dest) || MEM_P (dest))
2117             {
2118               int j;
2119               for (j = i + 1; j < n_sets; j++)
2120                 if (rtx_equal_p (dest, sets[j].dest))
2121                   {
2122                     sets[i].dest = pc_rtx;
2123                     sets[j].dest = pc_rtx;
2124                   }
2125             }
2126         }
2127     }
2128
2129   /* Now enter the equivalences in our tables.  */
2130   for (i = 0; i < n_sets; i++)
2131     {
2132       rtx dest = sets[i].dest;
2133       if (REG_P (dest)
2134           || (MEM_P (dest) && cselib_record_memory))
2135         cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
2136     }
2137 }
2138
2139 /* Record the effects of INSN.  */
2140
2141 void
2142 cselib_process_insn (rtx insn)
2143 {
2144   int i;
2145   rtx x;
2146
2147   cselib_current_insn = insn;
2148
2149   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
2150   if (LABEL_P (insn)
2151       || (CALL_P (insn)
2152           && find_reg_note (insn, REG_SETJMP, NULL))
2153       || (NONJUMP_INSN_P (insn)
2154           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2155           && MEM_VOLATILE_P (PATTERN (insn))))
2156     {
2157       cselib_reset_table (next_uid);
2158       cselib_current_insn = NULL_RTX;
2159       return;
2160     }
2161
2162   if (! INSN_P (insn))
2163     {
2164       cselib_current_insn = NULL_RTX;
2165       return;
2166     }
2167
2168   /* If this is a call instruction, forget anything stored in a
2169      call clobbered register, or, if this is not a const call, in
2170      memory.  */
2171   if (CALL_P (insn))
2172     {
2173       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2174         if (call_used_regs[i]
2175             || (REG_VALUES (i) && REG_VALUES (i)->elt
2176                 && HARD_REGNO_CALL_PART_CLOBBERED (i,
2177                       GET_MODE (REG_VALUES (i)->elt->val_rtx))))
2178           cselib_invalidate_regno (i, reg_raw_mode[i]);
2179
2180       /* Since it is not clear how cselib is going to be used, be
2181          conservative here and treat looping pure or const functions
2182          as if they were regular functions.  */
2183       if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
2184           || !(RTL_CONST_OR_PURE_CALL_P (insn)))
2185         cselib_invalidate_mem (callmem);
2186     }
2187
2188   cselib_record_sets (insn);
2189
2190 #ifdef AUTO_INC_DEC
2191   /* Clobber any registers which appear in REG_INC notes.  We
2192      could keep track of the changes to their values, but it is
2193      unlikely to help.  */
2194   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
2195     if (REG_NOTE_KIND (x) == REG_INC)
2196       cselib_invalidate_rtx (XEXP (x, 0));
2197 #endif
2198
2199   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2200      after we have processed the insn.  */
2201   if (CALL_P (insn))
2202     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2203       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
2204         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
2205
2206   cselib_current_insn = NULL_RTX;
2207
2208   if (n_useless_values > MAX_USELESS_VALUES
2209       /* remove_useless_values is linear in the hash table size.  Avoid
2210          quadratic behavior for very large hashtables with very few
2211          useless elements.  */
2212       && ((unsigned int)n_useless_values
2213           > (cselib_hash_table->n_elements
2214              - cselib_hash_table->n_deleted
2215              - n_debug_values) / 4))
2216     remove_useless_values ();
2217 }
2218
2219 /* Initialize cselib for one pass.  The caller must also call
2220    init_alias_analysis.  */
2221
2222 void
2223 cselib_init (int record_what)
2224 {
2225   elt_list_pool = create_alloc_pool ("elt_list",
2226                                      sizeof (struct elt_list), 10);
2227   elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
2228                                          sizeof (struct elt_loc_list), 10);
2229   cselib_val_pool = create_alloc_pool ("cselib_val_list",
2230                                        sizeof (cselib_val), 10);
2231   value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2232   cselib_record_memory = record_what & CSELIB_RECORD_MEMORY;
2233   cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS;
2234
2235   /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2236      see canon_true_dependence.  This is only created once.  */
2237   if (! callmem)
2238     callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2239
2240   cselib_nregs = max_reg_num ();
2241
2242   /* We preserve reg_values to allow expensive clearing of the whole thing.
2243      Reallocate it however if it happens to be too large.  */
2244   if (!reg_values || reg_values_size < cselib_nregs
2245       || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2246     {
2247       if (reg_values)
2248         free (reg_values);
2249       /* Some space for newly emit instructions so we don't end up
2250          reallocating in between passes.  */
2251       reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2252       reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2253     }
2254   used_regs = XNEWVEC (unsigned int, cselib_nregs);
2255   n_used_regs = 0;
2256   cselib_hash_table = htab_create (31, get_value_hash,
2257                                    entry_and_rtx_equal_p, NULL);
2258   next_uid = 1;
2259 }
2260
2261 /* Called when the current user is done with cselib.  */
2262
2263 void
2264 cselib_finish (void)
2265 {
2266   cselib_discard_hook = NULL;
2267   cselib_preserve_constants = false;
2268   cfa_base_preserved_val = NULL;
2269   free_alloc_pool (elt_list_pool);
2270   free_alloc_pool (elt_loc_list_pool);
2271   free_alloc_pool (cselib_val_pool);
2272   free_alloc_pool (value_pool);
2273   cselib_clear_table ();
2274   htab_delete (cselib_hash_table);
2275   free (used_regs);
2276   used_regs = 0;
2277   cselib_hash_table = 0;
2278   n_useless_values = 0;
2279   n_useless_debug_values = 0;
2280   n_debug_values = 0;
2281   next_uid = 0;
2282 }
2283
2284 /* Dump the cselib_val *X to FILE *info.  */
2285
2286 static int
2287 dump_cselib_val (void **x, void *info)
2288 {
2289   cselib_val *v = (cselib_val *)*x;
2290   FILE *out = (FILE *)info;
2291   bool need_lf = true;
2292
2293   print_inline_rtx (out, v->val_rtx, 0);
2294
2295   if (v->locs)
2296     {
2297       struct elt_loc_list *l = v->locs;
2298       if (need_lf)
2299         {
2300           fputc ('\n', out);
2301           need_lf = false;
2302         }
2303       fputs (" locs:", out);
2304       do
2305         {
2306           fprintf (out, "\n  from insn %i ",
2307                    INSN_UID (l->setting_insn));
2308           print_inline_rtx (out, l->loc, 4);
2309         }
2310       while ((l = l->next));
2311       fputc ('\n', out);
2312     }
2313   else
2314     {
2315       fputs (" no locs", out);
2316       need_lf = true;
2317     }
2318
2319   if (v->addr_list)
2320     {
2321       struct elt_list *e = v->addr_list;
2322       if (need_lf)
2323         {
2324           fputc ('\n', out);
2325           need_lf = false;
2326         }
2327       fputs (" addr list:", out);
2328       do
2329         {
2330           fputs ("\n  ", out);
2331           print_inline_rtx (out, e->elt->val_rtx, 2);
2332         }
2333       while ((e = e->next));
2334       fputc ('\n', out);
2335     }
2336   else
2337     {
2338       fputs (" no addrs", out);
2339       need_lf = true;
2340     }
2341
2342   if (v->next_containing_mem == &dummy_val)
2343     fputs (" last mem\n", out);
2344   else if (v->next_containing_mem)
2345     {
2346       fputs (" next mem ", out);
2347       print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2348       fputc ('\n', out);
2349     }
2350   else if (need_lf)
2351     fputc ('\n', out);
2352
2353   return 1;
2354 }
2355
2356 /* Dump to OUT everything in the CSELIB table.  */
2357
2358 void
2359 dump_cselib_table (FILE *out)
2360 {
2361   fprintf (out, "cselib hash table:\n");
2362   htab_traverse (cselib_hash_table, dump_cselib_val, out);
2363   if (first_containing_mem != &dummy_val)
2364     {
2365       fputs ("first mem ", out);
2366       print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2367       fputc ('\n', out);
2368     }
2369   fprintf (out, "next uid %i\n", next_uid);
2370 }
2371
2372 #include "gt-cselib.h"