OSDN Git Service

351d22d411003f3f90eb9f2d8fe7a600084eb960
[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 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
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 "cselib.h"
42 #include "params.h"
43 #include "alloc-pool.h"
44
45 static bool cselib_record_memory;
46 static int entry_and_rtx_equal_p (const void *, const void *);
47 static hashval_t get_value_hash (const void *);
48 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
49 static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
50 static void unchain_one_value (cselib_val *);
51 static void unchain_one_elt_list (struct elt_list **);
52 static void unchain_one_elt_loc_list (struct elt_loc_list **);
53 static void clear_table (void);
54 static int discard_useless_locs (void **, void *);
55 static int discard_useless_values (void **, void *);
56 static void remove_useless_values (void);
57 static rtx wrap_constant (enum machine_mode, rtx);
58 static unsigned int cselib_hash_rtx (rtx, enum machine_mode, int);
59 static cselib_val *new_cselib_val (unsigned int, enum machine_mode);
60 static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
61 static cselib_val *cselib_lookup_mem (rtx, int);
62 static void cselib_invalidate_regno (unsigned int, enum machine_mode);
63 static void cselib_invalidate_mem (rtx);
64 static void cselib_record_set (rtx, cselib_val *, cselib_val *);
65 static void cselib_record_sets (rtx);
66
67 /* There are three ways in which cselib can look up an rtx:
68    - for a REG, the reg_values table (which is indexed by regno) is used
69    - for a MEM, we recursively look up its address and then follow the
70      addr_list of that value
71    - for everything else, we compute a hash value and go through the hash
72      table.  Since different rtx's can still have the same hash value,
73      this involves walking the table entries for a given value and comparing
74      the locations of the entries with the rtx we are looking up.  */
75
76 /* A table that enables us to look up elts by their value.  */
77 static htab_t hash_table;
78
79 /* This is a global so we don't have to pass this through every function.
80    It is used in new_elt_loc_list to set SETTING_INSN.  */
81 static rtx cselib_current_insn;
82 static bool cselib_current_insn_in_libcall;
83
84 /* Every new unknown value gets a unique number.  */
85 static unsigned int next_unknown_value;
86
87 /* The number of registers we had when the varrays were last resized.  */
88 static unsigned int cselib_nregs;
89
90 /* Count values without known locations.  Whenever this grows too big, we
91    remove these useless values from the table.  */
92 static int n_useless_values;
93
94 /* Number of useless values before we remove them from the hash table.  */
95 #define MAX_USELESS_VALUES 32
96
97 /* This table maps from register number to values.  It does not
98    contain pointers to cselib_val structures, but rather elt_lists.
99    The purpose is to be able to refer to the same register in
100    different modes.  The first element of the list defines the mode in
101    which the register was set; if the mode is unknown or the value is
102    no longer valid in that mode, ELT will be NULL for the first
103    element.  */
104 static struct elt_list **reg_values;
105 static unsigned int reg_values_size;
106 #define REG_VALUES(i) reg_values[i]
107
108 /* The largest number of hard regs used by any entry added to the
109    REG_VALUES table.  Cleared on each clear_table() invocation.  */
110 static unsigned int max_value_regs;
111
112 /* Here the set of indices I with REG_VALUES(I) != 0 is saved.  This is used
113    in clear_table() for fast emptying.  */
114 static unsigned int *used_regs;
115 static unsigned int n_used_regs;
116
117 /* We pass this to cselib_invalidate_mem to invalidate all of
118    memory for a non-const call instruction.  */
119 static GTY(()) rtx callmem;
120
121 /* Set by discard_useless_locs if it deleted the last location of any
122    value.  */
123 static int values_became_useless;
124
125 /* Used as stop element of the containing_mem list so we can check
126    presence in the list by checking the next pointer.  */
127 static cselib_val dummy_val;
128
129 /* Used to list all values that contain memory reference.
130    May or may not contain the useless values - the list is compacted
131    each time memory is invalidated.  */
132 static cselib_val *first_containing_mem = &dummy_val;
133 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
134 \f
135
136 /* Allocate a struct elt_list and fill in its two elements with the
137    arguments.  */
138
139 static inline struct elt_list *
140 new_elt_list (struct elt_list *next, cselib_val *elt)
141 {
142   struct elt_list *el;
143   el = pool_alloc (elt_list_pool);
144   el->next = next;
145   el->elt = elt;
146   return el;
147 }
148
149 /* Allocate a struct elt_loc_list and fill in its two elements with the
150    arguments.  */
151
152 static inline struct elt_loc_list *
153 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
154 {
155   struct elt_loc_list *el;
156   el = pool_alloc (elt_loc_list_pool);
157   el->next = next;
158   el->loc = loc;
159   el->setting_insn = cselib_current_insn;
160   el->in_libcall = cselib_current_insn_in_libcall;
161   return el;
162 }
163
164 /* The elt_list at *PL is no longer needed.  Unchain it and free its
165    storage.  */
166
167 static inline void
168 unchain_one_elt_list (struct elt_list **pl)
169 {
170   struct elt_list *l = *pl;
171
172   *pl = l->next;
173   pool_free (elt_list_pool, l);
174 }
175
176 /* Likewise for elt_loc_lists.  */
177
178 static void
179 unchain_one_elt_loc_list (struct elt_loc_list **pl)
180 {
181   struct elt_loc_list *l = *pl;
182
183   *pl = l->next;
184   pool_free (elt_loc_list_pool, l);
185 }
186
187 /* Likewise for cselib_vals.  This also frees the addr_list associated with
188    V.  */
189
190 static void
191 unchain_one_value (cselib_val *v)
192 {
193   while (v->addr_list)
194     unchain_one_elt_list (&v->addr_list);
195
196   pool_free (cselib_val_pool, v);
197 }
198
199 /* Remove all entries from the hash table.  Also used during
200    initialization.  If CLEAR_ALL isn't set, then only clear the entries
201    which are known to have been used.  */
202
203 static void
204 clear_table (void)
205 {
206   unsigned int i;
207
208   for (i = 0; i < n_used_regs; i++)
209     REG_VALUES (used_regs[i]) = 0;
210
211   max_value_regs = 0;
212
213   n_used_regs = 0;
214
215   htab_empty (hash_table);
216
217   n_useless_values = 0;
218
219   next_unknown_value = 0;
220
221   first_containing_mem = &dummy_val;
222 }
223
224 /* The equality test for our hash table.  The first argument ENTRY is a table
225    element (i.e. a cselib_val), while the second arg X is an rtx.  We know
226    that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
227    CONST of an appropriate mode.  */
228
229 static int
230 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
231 {
232   struct elt_loc_list *l;
233   const cselib_val *v = (const cselib_val *) entry;
234   rtx x = (rtx) x_arg;
235   enum machine_mode mode = GET_MODE (x);
236
237   gcc_assert (GET_CODE (x) != CONST_INT
238               && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
239   
240   if (mode != GET_MODE (v->u.val_rtx))
241     return 0;
242
243   /* Unwrap X if necessary.  */
244   if (GET_CODE (x) == CONST
245       && (GET_CODE (XEXP (x, 0)) == CONST_INT
246           || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
247     x = XEXP (x, 0);
248
249   /* We don't guarantee that distinct rtx's have different hash values,
250      so we need to do a comparison.  */
251   for (l = v->locs; l; l = l->next)
252     if (rtx_equal_for_cselib_p (l->loc, x))
253       return 1;
254
255   return 0;
256 }
257
258 /* The hash function for our hash table.  The value is always computed with
259    cselib_hash_rtx when adding an element; this function just extracts the
260    hash value from a cselib_val structure.  */
261
262 static hashval_t
263 get_value_hash (const void *entry)
264 {
265   const cselib_val *v = (const cselib_val *) entry;
266   return v->value;
267 }
268
269 /* Return true if X contains a VALUE rtx.  If ONLY_USELESS is set, we
270    only return true for values which point to a cselib_val whose value
271    element has been set to zero, which implies the cselib_val will be
272    removed.  */
273
274 int
275 references_value_p (rtx x, int only_useless)
276 {
277   enum rtx_code code = GET_CODE (x);
278   const char *fmt = GET_RTX_FORMAT (code);
279   int i, j;
280
281   if (GET_CODE (x) == VALUE
282       && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
283     return 1;
284
285   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
286     {
287       if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
288         return 1;
289       else if (fmt[i] == 'E')
290         for (j = 0; j < XVECLEN (x, i); j++)
291           if (references_value_p (XVECEXP (x, i, j), only_useless))
292             return 1;
293     }
294
295   return 0;
296 }
297
298 /* For all locations found in X, delete locations that reference useless
299    values (i.e. values without any location).  Called through
300    htab_traverse.  */
301
302 static int
303 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
304 {
305   cselib_val *v = (cselib_val *)*x;
306   struct elt_loc_list **p = &v->locs;
307   int had_locs = v->locs != 0;
308
309   while (*p)
310     {
311       if (references_value_p ((*p)->loc, 1))
312         unchain_one_elt_loc_list (p);
313       else
314         p = &(*p)->next;
315     }
316
317   if (had_locs && v->locs == 0)
318     {
319       n_useless_values++;
320       values_became_useless = 1;
321     }
322   return 1;
323 }
324
325 /* If X is a value with no locations, remove it from the hashtable.  */
326
327 static int
328 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
329 {
330   cselib_val *v = (cselib_val *)*x;
331
332   if (v->locs == 0)
333     {
334       CSELIB_VAL_PTR (v->u.val_rtx) = NULL;
335       htab_clear_slot (hash_table, x);
336       unchain_one_value (v);
337       n_useless_values--;
338     }
339
340   return 1;
341 }
342
343 /* Clean out useless values (i.e. those which no longer have locations
344    associated with them) from the hash table.  */
345
346 static void
347 remove_useless_values (void)
348 {
349   cselib_val **p, *v;
350   /* First pass: eliminate locations that reference the value.  That in
351      turn can make more values useless.  */
352   do
353     {
354       values_became_useless = 0;
355       htab_traverse (hash_table, discard_useless_locs, 0);
356     }
357   while (values_became_useless);
358
359   /* Second pass: actually remove the values.  */
360
361   p = &first_containing_mem;
362   for (v = *p; v != &dummy_val; v = v->next_containing_mem)
363     if (v->locs)
364       {
365         *p = v;
366         p = &(*p)->next_containing_mem;
367       }
368   *p = &dummy_val;
369
370   htab_traverse (hash_table, discard_useless_values, 0);
371
372   gcc_assert (!n_useless_values);
373 }
374
375 /* Return the mode in which a register was last set.  If X is not a
376    register, return its mode.  If the mode in which the register was
377    set is not known, or the value was already clobbered, return
378    VOIDmode.  */
379
380 enum machine_mode
381 cselib_reg_set_mode (rtx x)
382 {
383   if (!REG_P (x))
384     return GET_MODE (x);
385
386   if (REG_VALUES (REGNO (x)) == NULL
387       || REG_VALUES (REGNO (x))->elt == NULL)
388     return VOIDmode;
389
390   return GET_MODE (REG_VALUES (REGNO (x))->elt->u.val_rtx);
391 }
392
393 /* Return nonzero if we can prove that X and Y contain the same value, taking
394    our gathered information into account.  */
395
396 int
397 rtx_equal_for_cselib_p (rtx x, rtx y)
398 {
399   enum rtx_code code;
400   const char *fmt;
401   int i;
402
403   if (REG_P (x) || MEM_P (x))
404     {
405       cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
406
407       if (e)
408         x = e->u.val_rtx;
409     }
410
411   if (REG_P (y) || MEM_P (y))
412     {
413       cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
414
415       if (e)
416         y = e->u.val_rtx;
417     }
418
419   if (x == y)
420     return 1;
421
422   if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
423     return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
424
425   if (GET_CODE (x) == VALUE)
426     {
427       cselib_val *e = CSELIB_VAL_PTR (x);
428       struct elt_loc_list *l;
429
430       for (l = e->locs; l; l = l->next)
431         {
432           rtx t = l->loc;
433
434           /* Avoid infinite recursion.  */
435           if (REG_P (t) || MEM_P (t))
436             continue;
437           else if (rtx_equal_for_cselib_p (t, y))
438             return 1;
439         }
440
441       return 0;
442     }
443
444   if (GET_CODE (y) == VALUE)
445     {
446       cselib_val *e = CSELIB_VAL_PTR (y);
447       struct elt_loc_list *l;
448
449       for (l = e->locs; l; l = l->next)
450         {
451           rtx t = l->loc;
452
453           if (REG_P (t) || MEM_P (t))
454             continue;
455           else if (rtx_equal_for_cselib_p (x, t))
456             return 1;
457         }
458
459       return 0;
460     }
461
462   if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
463     return 0;
464
465   /* This won't be handled correctly by the code below.  */
466   if (GET_CODE (x) == LABEL_REF)
467     return XEXP (x, 0) == XEXP (y, 0);
468
469   code = GET_CODE (x);
470   fmt = GET_RTX_FORMAT (code);
471
472   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
473     {
474       int j;
475
476       switch (fmt[i])
477         {
478         case 'w':
479           if (XWINT (x, i) != XWINT (y, i))
480             return 0;
481           break;
482
483         case 'n':
484         case 'i':
485           if (XINT (x, i) != XINT (y, i))
486             return 0;
487           break;
488
489         case 'V':
490         case 'E':
491           /* Two vectors must have the same length.  */
492           if (XVECLEN (x, i) != XVECLEN (y, i))
493             return 0;
494
495           /* And the corresponding elements must match.  */
496           for (j = 0; j < XVECLEN (x, i); j++)
497             if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
498                                           XVECEXP (y, i, j)))
499               return 0;
500           break;
501
502         case 'e':
503           if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
504             return 0;
505           break;
506
507         case 'S':
508         case 's':
509           if (strcmp (XSTR (x, i), XSTR (y, i)))
510             return 0;
511           break;
512
513         case 'u':
514           /* These are just backpointers, so they don't matter.  */
515           break;
516
517         case '0':
518         case 't':
519           break;
520
521           /* It is believed that rtx's at this level will never
522              contain anything but integers and other rtx's,
523              except for within LABEL_REFs and SYMBOL_REFs.  */
524         default:
525           gcc_unreachable ();
526         }
527     }
528   return 1;
529 }
530
531 /* We need to pass down the mode of constants through the hash table
532    functions.  For that purpose, wrap them in a CONST of the appropriate
533    mode.  */
534 static rtx
535 wrap_constant (enum machine_mode mode, rtx x)
536 {
537   if (GET_CODE (x) != CONST_INT
538       && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
539     return x;
540   gcc_assert (mode != VOIDmode);
541   return gen_rtx_CONST (mode, x);
542 }
543
544 /* Hash an rtx.  Return 0 if we couldn't hash the rtx.
545    For registers and memory locations, we look up their cselib_val structure
546    and return its VALUE element.
547    Possible reasons for return 0 are: the object is volatile, or we couldn't
548    find a register or memory location in the table and CREATE is zero.  If
549    CREATE is nonzero, table elts are created for regs and mem.
550    MODE is used in hashing for CONST_INTs only;
551    otherwise the mode of X is used.  */
552
553 static unsigned int
554 cselib_hash_rtx (rtx x, enum machine_mode mode, int create)
555 {
556   cselib_val *e;
557   int i, j;
558   enum rtx_code code;
559   const char *fmt;
560   unsigned int hash = 0;
561
562   code = GET_CODE (x);
563   hash += (unsigned) code + (unsigned) GET_MODE (x);
564
565   switch (code)
566     {
567     case MEM:
568     case REG:
569       e = cselib_lookup (x, GET_MODE (x), create);
570       if (! e)
571         return 0;
572
573       return e->value;
574
575     case CONST_INT:
576       hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + INTVAL (x);
577       return hash ? hash : (unsigned int) CONST_INT;
578
579     case CONST_DOUBLE:
580       /* This is like the general case, except that it only counts
581          the integers representing the constant.  */
582       hash += (unsigned) code + (unsigned) GET_MODE (x);
583       if (GET_MODE (x) != VOIDmode)
584         hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
585       else
586         hash += ((unsigned) CONST_DOUBLE_LOW (x)
587                  + (unsigned) CONST_DOUBLE_HIGH (x));
588       return hash ? hash : (unsigned int) CONST_DOUBLE;
589
590     case CONST_VECTOR:
591       {
592         int units;
593         rtx elt;
594
595         units = CONST_VECTOR_NUNITS (x);
596
597         for (i = 0; i < units; ++i)
598           {
599             elt = CONST_VECTOR_ELT (x, i);
600             hash += cselib_hash_rtx (elt, GET_MODE (elt), 0);
601           }
602
603         return hash;
604       }
605
606       /* Assume there is only one rtx object for any given label.  */
607     case LABEL_REF:
608       hash
609         += ((unsigned) LABEL_REF << 7) + (unsigned long) XEXP (x, 0);
610       return hash ? hash : (unsigned int) LABEL_REF;
611
612     case SYMBOL_REF:
613       hash
614         += ((unsigned) SYMBOL_REF << 7) + (unsigned long) XSTR (x, 0);
615       return hash ? hash : (unsigned int) SYMBOL_REF;
616
617     case PRE_DEC:
618     case PRE_INC:
619     case POST_DEC:
620     case POST_INC:
621     case POST_MODIFY:
622     case PRE_MODIFY:
623     case PC:
624     case CC0:
625     case CALL:
626     case UNSPEC_VOLATILE:
627       return 0;
628
629     case ASM_OPERANDS:
630       if (MEM_VOLATILE_P (x))
631         return 0;
632
633       break;
634
635     default:
636       break;
637     }
638
639   i = GET_RTX_LENGTH (code) - 1;
640   fmt = GET_RTX_FORMAT (code);
641   for (; i >= 0; i--)
642     {
643       switch (fmt[i])
644         {
645         case 'e':
646           {
647             rtx tem = XEXP (x, i);
648             unsigned int tem_hash = cselib_hash_rtx (tem, 0, create);
649             
650             if (tem_hash == 0)
651               return 0;
652             
653             hash += tem_hash;
654           }
655           break;
656         case 'E':
657           for (j = 0; j < XVECLEN (x, i); j++)
658             {
659               unsigned int tem_hash
660                 = cselib_hash_rtx (XVECEXP (x, i, j), 0, create);
661               
662               if (tem_hash == 0)
663                 return 0;
664               
665               hash += tem_hash;
666             }
667           break;
668
669         case 's':
670           {
671             const unsigned char *p = (const unsigned char *) XSTR (x, i);
672             
673             if (p)
674               while (*p)
675                 hash += *p++;
676             break;
677           }
678           
679         case 'i':
680           hash += XINT (x, i);
681           break;
682
683         case '0':
684         case 't':
685           /* unused */
686           break;
687           
688         default:
689           gcc_unreachable ();
690         }
691     }
692
693   return hash ? hash : 1 + (unsigned int) GET_CODE (x);
694 }
695
696 /* Create a new value structure for VALUE and initialize it.  The mode of the
697    value is MODE.  */
698
699 static inline cselib_val *
700 new_cselib_val (unsigned int value, enum machine_mode mode)
701 {
702   cselib_val *e = pool_alloc (cselib_val_pool);
703
704   gcc_assert (value);
705
706   e->value = value;
707   /* We use an alloc pool to allocate this RTL construct because it
708      accounts for about 8% of the overall memory usage.  We know
709      precisely when we can have VALUE RTXen (when cselib is active)
710      so we don't need to put them in garbage collected memory.
711      ??? Why should a VALUE be an RTX in the first place?  */
712   e->u.val_rtx = pool_alloc (value_pool);
713   memset (e->u.val_rtx, 0, RTX_HDR_SIZE);
714   PUT_CODE (e->u.val_rtx, VALUE);
715   PUT_MODE (e->u.val_rtx, mode);
716   CSELIB_VAL_PTR (e->u.val_rtx) = e;
717   e->addr_list = 0;
718   e->locs = 0;
719   e->next_containing_mem = 0;
720   return e;
721 }
722
723 /* ADDR_ELT is a value that is used as address.  MEM_ELT is the value that
724    contains the data at this address.  X is a MEM that represents the
725    value.  Update the two value structures to represent this situation.  */
726
727 static void
728 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
729 {
730   struct elt_loc_list *l;
731
732   /* Avoid duplicates.  */
733   for (l = mem_elt->locs; l; l = l->next)
734     if (MEM_P (l->loc)
735         && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
736       return;
737
738   addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
739   mem_elt->locs
740     = new_elt_loc_list (mem_elt->locs,
741                         replace_equiv_address_nv (x, addr_elt->u.val_rtx));
742   if (mem_elt->next_containing_mem == NULL)
743     {
744       mem_elt->next_containing_mem = first_containing_mem;
745       first_containing_mem = mem_elt;
746     }
747 }
748
749 /* Subroutine of cselib_lookup.  Return a value for X, which is a MEM rtx.
750    If CREATE, make a new one if we haven't seen it before.  */
751
752 static cselib_val *
753 cselib_lookup_mem (rtx x, int create)
754 {
755   enum machine_mode mode = GET_MODE (x);
756   void **slot;
757   cselib_val *addr;
758   cselib_val *mem_elt;
759   struct elt_list *l;
760
761   if (MEM_VOLATILE_P (x) || mode == BLKmode
762       || !cselib_record_memory
763       || (FLOAT_MODE_P (mode) && flag_float_store))
764     return 0;
765
766   /* Look up the value for the address.  */
767   addr = cselib_lookup (XEXP (x, 0), mode, create);
768   if (! addr)
769     return 0;
770
771   /* Find a value that describes a value of our mode at that address.  */
772   for (l = addr->addr_list; l; l = l->next)
773     if (GET_MODE (l->elt->u.val_rtx) == mode)
774       return l->elt;
775
776   if (! create)
777     return 0;
778
779   mem_elt = new_cselib_val (++next_unknown_value, mode);
780   add_mem_for_addr (addr, mem_elt, x);
781   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
782                                    mem_elt->value, INSERT);
783   *slot = mem_elt;
784   return mem_elt;
785 }
786
787 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
788    with VALUE expressions.  This way, it becomes independent of changes
789    to registers and memory.
790    X isn't actually modified; if modifications are needed, new rtl is
791    allocated.  However, the return value can share rtl with X.  */
792
793 rtx
794 cselib_subst_to_values (rtx x)
795 {
796   enum rtx_code code = GET_CODE (x);
797   const char *fmt = GET_RTX_FORMAT (code);
798   cselib_val *e;
799   struct elt_list *l;
800   rtx copy = x;
801   int i;
802
803   switch (code)
804     {
805     case REG:
806       l = REG_VALUES (REGNO (x));
807       if (l && l->elt == NULL)
808         l = l->next;
809       for (; l; l = l->next)
810         if (GET_MODE (l->elt->u.val_rtx) == GET_MODE (x))
811           return l->elt->u.val_rtx;
812
813       gcc_unreachable ();
814
815     case MEM:
816       e = cselib_lookup_mem (x, 0);
817       if (! e)
818         {
819           /* This happens for autoincrements.  Assign a value that doesn't
820              match any other.  */
821           e = new_cselib_val (++next_unknown_value, GET_MODE (x));
822         }
823       return e->u.val_rtx;
824
825     case CONST_DOUBLE:
826     case CONST_VECTOR:
827     case CONST_INT:
828       return x;
829
830     case POST_INC:
831     case PRE_INC:
832     case POST_DEC:
833     case PRE_DEC:
834     case POST_MODIFY:
835     case PRE_MODIFY:
836       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
837       return e->u.val_rtx;
838
839     default:
840       break;
841     }
842
843   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
844     {
845       if (fmt[i] == 'e')
846         {
847           rtx t = cselib_subst_to_values (XEXP (x, i));
848
849           if (t != XEXP (x, i) && x == copy)
850             copy = shallow_copy_rtx (x);
851
852           XEXP (copy, i) = t;
853         }
854       else if (fmt[i] == 'E')
855         {
856           int j, k;
857
858           for (j = 0; j < XVECLEN (x, i); j++)
859             {
860               rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
861
862               if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
863                 {
864                   if (x == copy)
865                     copy = shallow_copy_rtx (x);
866
867                   XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
868                   for (k = 0; k < j; k++)
869                     XVECEXP (copy, i, k) = XVECEXP (x, i, k);
870                 }
871
872               XVECEXP (copy, i, j) = t;
873             }
874         }
875     }
876
877   return copy;
878 }
879
880 /* Look up the rtl expression X in our tables and return the value it has.
881    If CREATE is zero, we return NULL if we don't know the value.  Otherwise,
882    we create a new one if possible, using mode MODE if X doesn't have a mode
883    (i.e. because it's a constant).  */
884
885 cselib_val *
886 cselib_lookup (rtx x, enum machine_mode mode, int create)
887 {
888   void **slot;
889   cselib_val *e;
890   unsigned int hashval;
891
892   if (GET_MODE (x) != VOIDmode)
893     mode = GET_MODE (x);
894
895   if (GET_CODE (x) == VALUE)
896     return CSELIB_VAL_PTR (x);
897
898   if (REG_P (x))
899     {
900       struct elt_list *l;
901       unsigned int i = REGNO (x);
902
903       l = REG_VALUES (i);
904       if (l && l->elt == NULL)
905         l = l->next;
906       for (; l; l = l->next)
907         if (mode == GET_MODE (l->elt->u.val_rtx))
908           return l->elt;
909
910       if (! create)
911         return 0;
912
913       if (i < FIRST_PSEUDO_REGISTER)
914         {
915           unsigned int n = hard_regno_nregs[i][mode];
916
917           if (n > max_value_regs)
918             max_value_regs = n;
919         }
920
921       e = new_cselib_val (++next_unknown_value, GET_MODE (x));
922       e->locs = new_elt_loc_list (e->locs, x);
923       if (REG_VALUES (i) == 0)
924         {
925           /* Maintain the invariant that the first entry of
926              REG_VALUES, if present, must be the value used to set the
927              register, or NULL.  */
928           used_regs[n_used_regs++] = i;
929           REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
930         }
931       REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
932       slot = htab_find_slot_with_hash (hash_table, x, e->value, INSERT);
933       *slot = e;
934       return e;
935     }
936
937   if (MEM_P (x))
938     return cselib_lookup_mem (x, create);
939
940   hashval = cselib_hash_rtx (x, mode, create);
941   /* Can't even create if hashing is not possible.  */
942   if (! hashval)
943     return 0;
944
945   slot = htab_find_slot_with_hash (hash_table, wrap_constant (mode, x),
946                                    hashval, create ? INSERT : NO_INSERT);
947   if (slot == 0)
948     return 0;
949
950   e = (cselib_val *) *slot;
951   if (e)
952     return e;
953
954   e = new_cselib_val (hashval, mode);
955
956   /* We have to fill the slot before calling cselib_subst_to_values:
957      the hash table is inconsistent until we do so, and
958      cselib_subst_to_values will need to do lookups.  */
959   *slot = (void *) e;
960   e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
961   return e;
962 }
963
964 /* Invalidate any entries in reg_values that overlap REGNO.  This is called
965    if REGNO is changing.  MODE is the mode of the assignment to REGNO, which
966    is used to determine how many hard registers are being changed.  If MODE
967    is VOIDmode, then only REGNO is being changed; this is used when
968    invalidating call clobbered registers across a call.  */
969
970 static void
971 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
972 {
973   unsigned int endregno;
974   unsigned int i;
975
976   /* If we see pseudos after reload, something is _wrong_.  */
977   gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
978               || reg_renumber[regno] < 0);
979
980   /* Determine the range of registers that must be invalidated.  For
981      pseudos, only REGNO is affected.  For hard regs, we must take MODE
982      into account, and we must also invalidate lower register numbers
983      if they contain values that overlap REGNO.  */
984   if (regno < FIRST_PSEUDO_REGISTER)
985     {
986       gcc_assert (mode != VOIDmode);
987
988       if (regno < max_value_regs)
989         i = 0;
990       else
991         i = regno - max_value_regs;
992
993       endregno = regno + hard_regno_nregs[regno][mode];
994     }
995   else
996     {
997       i = regno;
998       endregno = regno + 1;
999     }
1000
1001   for (; i < endregno; i++)
1002     {
1003       struct elt_list **l = &REG_VALUES (i);
1004
1005       /* Go through all known values for this reg; if it overlaps the range
1006          we're invalidating, remove the value.  */
1007       while (*l)
1008         {
1009           cselib_val *v = (*l)->elt;
1010           struct elt_loc_list **p;
1011           unsigned int this_last = i;
1012
1013           if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1014             this_last += hard_regno_nregs[i][GET_MODE (v->u.val_rtx)] - 1;
1015
1016           if (this_last < regno || v == NULL)
1017             {
1018               l = &(*l)->next;
1019               continue;
1020             }
1021
1022           /* We have an overlap.  */
1023           if (*l == REG_VALUES (i))
1024             {
1025               /* Maintain the invariant that the first entry of
1026                  REG_VALUES, if present, must be the value used to set
1027                  the register, or NULL.  This is also nice because
1028                  then we won't push the same regno onto user_regs
1029                  multiple times.  */
1030               (*l)->elt = NULL;
1031               l = &(*l)->next;
1032             }
1033           else
1034             unchain_one_elt_list (l);
1035
1036           /* Now, we clear the mapping from value to reg.  It must exist, so
1037              this code will crash intentionally if it doesn't.  */
1038           for (p = &v->locs; ; p = &(*p)->next)
1039             {
1040               rtx x = (*p)->loc;
1041
1042               if (REG_P (x) && REGNO (x) == i)
1043                 {
1044                   unchain_one_elt_loc_list (p);
1045                   break;
1046                 }
1047             }
1048           if (v->locs == 0)
1049             n_useless_values++;
1050         }
1051     }
1052 }
1053 \f
1054 /* Return 1 if X has a value that can vary even between two
1055    executions of the program.  0 means X can be compared reliably
1056    against certain constants or near-constants.  */
1057
1058 static int
1059 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED, int from_alias ATTRIBUTE_UNUSED)
1060 {
1061   /* We actually don't need to verify very hard.  This is because
1062      if X has actually changed, we invalidate the memory anyway,
1063      so assume that all common memory addresses are
1064      invariant.  */
1065   return 0;
1066 }
1067
1068 /* Invalidate any locations in the table which are changed because of a
1069    store to MEM_RTX.  If this is called because of a non-const call
1070    instruction, MEM_RTX is (mem:BLK const0_rtx).  */
1071
1072 static void
1073 cselib_invalidate_mem (rtx mem_rtx)
1074 {
1075   cselib_val **vp, *v, *next;
1076   int num_mems = 0;
1077   rtx mem_addr;
1078
1079   mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1080   mem_rtx = canon_rtx (mem_rtx);
1081
1082   vp = &first_containing_mem;
1083   for (v = *vp; v != &dummy_val; v = next)
1084     {
1085       bool has_mem = false;
1086       struct elt_loc_list **p = &v->locs;
1087       int had_locs = v->locs != 0;
1088
1089       while (*p)
1090         {
1091           rtx x = (*p)->loc;
1092           cselib_val *addr;
1093           struct elt_list **mem_chain;
1094
1095           /* MEMs may occur in locations only at the top level; below
1096              that every MEM or REG is substituted by its VALUE.  */
1097           if (!MEM_P (x))
1098             {
1099               p = &(*p)->next;
1100               continue;
1101             }
1102           if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1103               && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1104                                           x, cselib_rtx_varies_p))
1105             {
1106               has_mem = true;
1107               num_mems++;
1108               p = &(*p)->next;
1109               continue;
1110             }
1111
1112           /* This one overlaps.  */
1113           /* We must have a mapping from this MEM's address to the
1114              value (E).  Remove that, too.  */
1115           addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1116           mem_chain = &addr->addr_list;
1117           for (;;)
1118             {
1119               if ((*mem_chain)->elt == v)
1120                 {
1121                   unchain_one_elt_list (mem_chain);
1122                   break;
1123                 }
1124
1125               mem_chain = &(*mem_chain)->next;
1126             }
1127
1128           unchain_one_elt_loc_list (p);
1129         }
1130
1131       if (had_locs && v->locs == 0)
1132         n_useless_values++;
1133
1134       next = v->next_containing_mem;
1135       if (has_mem)
1136         {
1137           *vp = v;
1138           vp = &(*vp)->next_containing_mem;
1139         }
1140       else
1141         v->next_containing_mem = NULL;
1142     }
1143   *vp = &dummy_val;
1144 }
1145
1146 /* Invalidate DEST, which is being assigned to or clobbered.  */
1147
1148 void
1149 cselib_invalidate_rtx (rtx dest)
1150 {
1151   while (GET_CODE (dest) == SUBREG
1152          || GET_CODE (dest) == ZERO_EXTRACT
1153          || GET_CODE (dest) == STRICT_LOW_PART)
1154     dest = XEXP (dest, 0);
1155
1156   if (REG_P (dest))
1157     cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1158   else if (MEM_P (dest))
1159     cselib_invalidate_mem (dest);
1160
1161   /* Some machines don't define AUTO_INC_DEC, but they still use push
1162      instructions.  We need to catch that case here in order to
1163      invalidate the stack pointer correctly.  Note that invalidating
1164      the stack pointer is different from invalidating DEST.  */
1165   if (push_operand (dest, GET_MODE (dest)))
1166     cselib_invalidate_rtx (stack_pointer_rtx);
1167 }
1168
1169 /* A wrapper for cselib_invalidate_rtx to be called via note_stores.  */
1170
1171 static void
1172 cselib_invalidate_rtx_note_stores (rtx dest, rtx ignore ATTRIBUTE_UNUSED,
1173                                    void *data ATTRIBUTE_UNUSED)
1174 {
1175   cselib_invalidate_rtx (dest);
1176 }
1177
1178 /* Record the result of a SET instruction.  DEST is being set; the source
1179    contains the value described by SRC_ELT.  If DEST is a MEM, DEST_ADDR_ELT
1180    describes its address.  */
1181
1182 static void
1183 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1184 {
1185   int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1186
1187   if (src_elt == 0 || side_effects_p (dest))
1188     return;
1189
1190   if (dreg >= 0)
1191     {
1192       if (dreg < FIRST_PSEUDO_REGISTER)
1193         {
1194           unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1195
1196           if (n > max_value_regs)
1197             max_value_regs = n;
1198         }
1199
1200       if (REG_VALUES (dreg) == 0)
1201         {
1202           used_regs[n_used_regs++] = dreg;
1203           REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1204         }
1205       else
1206         {
1207           /* The register should have been invalidated.  */
1208           gcc_assert (REG_VALUES (dreg)->elt == 0);
1209           REG_VALUES (dreg)->elt = src_elt;
1210         }
1211
1212       if (src_elt->locs == 0)
1213         n_useless_values--;
1214       src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1215     }
1216   else if (MEM_P (dest) && dest_addr_elt != 0
1217            && cselib_record_memory)
1218     {
1219       if (src_elt->locs == 0)
1220         n_useless_values--;
1221       add_mem_for_addr (dest_addr_elt, src_elt, dest);
1222     }
1223 }
1224
1225 /* Describe a single set that is part of an insn.  */
1226 struct set
1227 {
1228   rtx src;
1229   rtx dest;
1230   cselib_val *src_elt;
1231   cselib_val *dest_addr_elt;
1232 };
1233
1234 /* There is no good way to determine how many elements there can be
1235    in a PARALLEL.  Since it's fairly cheap, use a really large number.  */
1236 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1237
1238 /* Record the effects of any sets in INSN.  */
1239 static void
1240 cselib_record_sets (rtx insn)
1241 {
1242   int n_sets = 0;
1243   int i;
1244   struct set sets[MAX_SETS];
1245   rtx body = PATTERN (insn);
1246   rtx cond = 0;
1247
1248   body = PATTERN (insn);
1249   if (GET_CODE (body) == COND_EXEC)
1250     {
1251       cond = COND_EXEC_TEST (body);
1252       body = COND_EXEC_CODE (body);
1253     }
1254
1255   /* Find all sets.  */
1256   if (GET_CODE (body) == SET)
1257     {
1258       sets[0].src = SET_SRC (body);
1259       sets[0].dest = SET_DEST (body);
1260       n_sets = 1;
1261     }
1262   else if (GET_CODE (body) == PARALLEL)
1263     {
1264       /* Look through the PARALLEL and record the values being
1265          set, if possible.  Also handle any CLOBBERs.  */
1266       for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1267         {
1268           rtx x = XVECEXP (body, 0, i);
1269
1270           if (GET_CODE (x) == SET)
1271             {
1272               sets[n_sets].src = SET_SRC (x);
1273               sets[n_sets].dest = SET_DEST (x);
1274               n_sets++;
1275             }
1276         }
1277     }
1278
1279   /* Look up the values that are read.  Do this before invalidating the
1280      locations that are written.  */
1281   for (i = 0; i < n_sets; i++)
1282     {
1283       rtx dest = sets[i].dest;
1284
1285       /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1286          the low part after invalidating any knowledge about larger modes.  */
1287       if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1288         sets[i].dest = dest = XEXP (dest, 0);
1289
1290       /* We don't know how to record anything but REG or MEM.  */
1291       if (REG_P (dest)
1292           || (MEM_P (dest) && cselib_record_memory))
1293         {
1294           rtx src = sets[i].src;
1295           if (cond)
1296             src = gen_rtx_IF_THEN_ELSE (GET_MODE (src), cond, src, dest);
1297           sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1298           if (MEM_P (dest))
1299             sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1300           else
1301             sets[i].dest_addr_elt = 0;
1302         }
1303     }
1304
1305   /* Invalidate all locations written by this insn.  Note that the elts we
1306      looked up in the previous loop aren't affected, just some of their
1307      locations may go away.  */
1308   note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1309
1310   /* If this is an asm, look for duplicate sets.  This can happen when the
1311      user uses the same value as an output multiple times.  This is valid
1312      if the outputs are not actually used thereafter.  Treat this case as
1313      if the value isn't actually set.  We do this by smashing the destination
1314      to pc_rtx, so that we won't record the value later.  */
1315   if (n_sets >= 2 && asm_noperands (body) >= 0)
1316     {
1317       for (i = 0; i < n_sets; i++)
1318         {
1319           rtx dest = sets[i].dest;
1320           if (REG_P (dest) || MEM_P (dest))
1321             {
1322               int j;
1323               for (j = i + 1; j < n_sets; j++)
1324                 if (rtx_equal_p (dest, sets[j].dest))
1325                   {
1326                     sets[i].dest = pc_rtx;
1327                     sets[j].dest = pc_rtx;
1328                   }
1329             }
1330         }
1331     }
1332
1333   /* Now enter the equivalences in our tables.  */
1334   for (i = 0; i < n_sets; i++)
1335     {
1336       rtx dest = sets[i].dest;
1337       if (REG_P (dest)
1338           || (MEM_P (dest) && cselib_record_memory))
1339         cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1340     }
1341 }
1342
1343 /* Record the effects of INSN.  */
1344
1345 void
1346 cselib_process_insn (rtx insn)
1347 {
1348   int i;
1349   rtx x;
1350
1351   if (find_reg_note (insn, REG_LIBCALL, NULL))
1352     cselib_current_insn_in_libcall = true;
1353   cselib_current_insn = insn;
1354
1355   /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp.  */
1356   if (LABEL_P (insn)
1357       || (CALL_P (insn)
1358           && find_reg_note (insn, REG_SETJMP, NULL))
1359       || (NONJUMP_INSN_P (insn)
1360           && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1361           && MEM_VOLATILE_P (PATTERN (insn))))
1362     {
1363       if (find_reg_note (insn, REG_RETVAL, NULL))
1364         cselib_current_insn_in_libcall = false;
1365       clear_table ();
1366       return;
1367     }
1368
1369   if (! INSN_P (insn))
1370     {
1371       if (find_reg_note (insn, REG_RETVAL, NULL))
1372         cselib_current_insn_in_libcall = false;
1373       cselib_current_insn = 0;
1374       return;
1375     }
1376
1377   /* If this is a call instruction, forget anything stored in a
1378      call clobbered register, or, if this is not a const call, in
1379      memory.  */
1380   if (CALL_P (insn))
1381     {
1382       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1383         if (call_used_regs[i]
1384             || (REG_VALUES (i) && REG_VALUES (i)->elt
1385                 && HARD_REGNO_CALL_PART_CLOBBERED (i, 
1386                       GET_MODE (REG_VALUES (i)->elt->u.val_rtx))))
1387           cselib_invalidate_regno (i, reg_raw_mode[i]);
1388
1389       if (! CONST_OR_PURE_CALL_P (insn))
1390         cselib_invalidate_mem (callmem);
1391     }
1392
1393   cselib_record_sets (insn);
1394
1395 #ifdef AUTO_INC_DEC
1396   /* Clobber any registers which appear in REG_INC notes.  We
1397      could keep track of the changes to their values, but it is
1398      unlikely to help.  */
1399   for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1400     if (REG_NOTE_KIND (x) == REG_INC)
1401       cselib_invalidate_rtx (XEXP (x, 0));
1402 #endif
1403
1404   /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1405      after we have processed the insn.  */
1406   if (CALL_P (insn))
1407     for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1408       if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1409         cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
1410
1411   if (find_reg_note (insn, REG_RETVAL, NULL))
1412     cselib_current_insn_in_libcall = false;
1413   cselib_current_insn = 0;
1414
1415   if (n_useless_values > MAX_USELESS_VALUES)
1416     remove_useless_values ();
1417 }
1418
1419 /* Initialize cselib for one pass.  The caller must also call
1420    init_alias_analysis.  */
1421
1422 void
1423 cselib_init (bool record_memory)
1424 {
1425   elt_list_pool = create_alloc_pool ("elt_list", 
1426                                      sizeof (struct elt_list), 10);
1427   elt_loc_list_pool = create_alloc_pool ("elt_loc_list", 
1428                                          sizeof (struct elt_loc_list), 10);
1429   cselib_val_pool = create_alloc_pool ("cselib_val_list", 
1430                                        sizeof (cselib_val), 10);
1431   value_pool = create_alloc_pool ("value", 
1432                                   RTX_SIZE (VALUE), 100);
1433   cselib_record_memory = record_memory;
1434   /* This is only created once.  */
1435   if (! callmem)
1436     callmem = gen_rtx_MEM (BLKmode, const0_rtx);
1437
1438   cselib_nregs = max_reg_num ();
1439
1440   /* We preserve reg_values to allow expensive clearing of the whole thing.
1441      Reallocate it however if it happens to be too large.  */
1442   if (!reg_values || reg_values_size < cselib_nregs
1443       || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
1444     {
1445       if (reg_values)
1446         free (reg_values);
1447       /* Some space for newly emit instructions so we don't end up
1448          reallocating in between passes.  */
1449       reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
1450       reg_values = xcalloc (reg_values_size, sizeof (reg_values));
1451     }
1452   used_regs = xmalloc (sizeof (*used_regs) * cselib_nregs);
1453   n_used_regs = 0;
1454   hash_table = htab_create (31, get_value_hash, entry_and_rtx_equal_p, NULL);
1455   cselib_current_insn_in_libcall = false;
1456 }
1457
1458 /* Called when the current user is done with cselib.  */
1459
1460 void
1461 cselib_finish (void)
1462 {
1463   free_alloc_pool (elt_list_pool);
1464   free_alloc_pool (elt_loc_list_pool);
1465   free_alloc_pool (cselib_val_pool);
1466   free_alloc_pool (value_pool);
1467   clear_table ();
1468   htab_delete (hash_table);
1469   free (used_regs);
1470   used_regs = 0;
1471   hash_table = 0;
1472   n_useless_values = 0;
1473   next_unknown_value = 0;
1474 }
1475
1476 #include "gt-cselib.h"