OSDN Git Service

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