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
4 Free Software Foundation, Inc.
6 This file is part of GCC.
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
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
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/>. */
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
41 #include "tree-pass.h"
44 #include "alloc-pool.h"
47 static bool cselib_record_memory;
48 static int entry_and_rtx_equal_p (const void *, const void *);
49 static hashval_t get_value_hash (const void *);
50 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
51 static struct elt_loc_list *new_elt_loc_list (struct elt_loc_list *, rtx);
52 static void unchain_one_value (cselib_val *);
53 static void unchain_one_elt_list (struct elt_list **);
54 static void unchain_one_elt_loc_list (struct elt_loc_list **);
55 static int discard_useless_locs (void **, void *);
56 static int discard_useless_values (void **, void *);
57 static void remove_useless_values (void);
58 static unsigned int cselib_hash_rtx (rtx, int);
59 static cselib_val *new_cselib_val (unsigned int, enum machine_mode, rtx);
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);
67 struct expand_value_data
70 cselib_expand_callback callback;
74 static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
76 /* There are three ways in which cselib can look up an rtx:
77 - for a REG, the reg_values table (which is indexed by regno) is used
78 - for a MEM, we recursively look up its address and then follow the
79 addr_list of that value
80 - for everything else, we compute a hash value and go through the hash
81 table. Since different rtx's can still have the same hash value,
82 this involves walking the table entries for a given value and comparing
83 the locations of the entries with the rtx we are looking up. */
85 /* A table that enables us to look up elts by their value. */
86 static htab_t cselib_hash_table;
88 /* This is a global so we don't have to pass this through every function.
89 It is used in new_elt_loc_list to set SETTING_INSN. */
90 static rtx cselib_current_insn;
92 /* Every new unknown value gets a unique number. */
93 static unsigned int next_unknown_value;
95 /* The number of registers we had when the varrays were last resized. */
96 static unsigned int cselib_nregs;
98 /* Count values without known locations. Whenever this grows too big, we
99 remove these useless values from the table. */
100 static int n_useless_values;
102 /* Number of useless values before we remove them from the hash table. */
103 #define MAX_USELESS_VALUES 32
105 /* This table maps from register number to values. It does not
106 contain pointers to cselib_val structures, but rather elt_lists.
107 The purpose is to be able to refer to the same register in
108 different modes. The first element of the list defines the mode in
109 which the register was set; if the mode is unknown or the value is
110 no longer valid in that mode, ELT will be NULL for the first
112 static struct elt_list **reg_values;
113 static unsigned int reg_values_size;
114 #define REG_VALUES(i) reg_values[i]
116 /* The largest number of hard regs used by any entry added to the
117 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
118 static unsigned int max_value_regs;
120 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
121 in cselib_clear_table() for fast emptying. */
122 static unsigned int *used_regs;
123 static unsigned int n_used_regs;
125 /* We pass this to cselib_invalidate_mem to invalidate all of
126 memory for a non-const call instruction. */
127 static GTY(()) rtx callmem;
129 /* Set by discard_useless_locs if it deleted the last location of any
131 static int values_became_useless;
133 /* Used as stop element of the containing_mem list so we can check
134 presence in the list by checking the next pointer. */
135 static cselib_val dummy_val;
137 /* Used to list all values that contain memory reference.
138 May or may not contain the useless values - the list is compacted
139 each time memory is invalidated. */
140 static cselib_val *first_containing_mem = &dummy_val;
141 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
143 /* If nonnull, cselib will call this function before freeing useless
144 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
145 void (*cselib_discard_hook) (cselib_val *);
147 /* If nonnull, cselib will call this function before recording sets or
148 even clobbering outputs of INSN. All the recorded sets will be
149 represented in the array sets[n_sets]. new_val_min can be used to
150 tell whether values present in sets are introduced by this
152 void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,
155 #define PRESERVED_VALUE_P(RTX) \
156 (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
157 #define LONG_TERM_PRESERVED_VALUE_P(RTX) \
158 (RTL_FLAG_CHECK1("LONG_TERM_PRESERVED_VALUE_P", (RTX), VALUE)->in_struct)
162 /* Allocate a struct elt_list and fill in its two elements with the
165 static inline struct elt_list *
166 new_elt_list (struct elt_list *next, cselib_val *elt)
169 el = (struct elt_list *) pool_alloc (elt_list_pool);
175 /* Allocate a struct elt_loc_list and fill in its two elements with the
178 static inline struct elt_loc_list *
179 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
181 struct elt_loc_list *el;
182 el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool);
185 el->setting_insn = cselib_current_insn;
189 /* The elt_list at *PL is no longer needed. Unchain it and free its
193 unchain_one_elt_list (struct elt_list **pl)
195 struct elt_list *l = *pl;
198 pool_free (elt_list_pool, l);
201 /* Likewise for elt_loc_lists. */
204 unchain_one_elt_loc_list (struct elt_loc_list **pl)
206 struct elt_loc_list *l = *pl;
209 pool_free (elt_loc_list_pool, l);
212 /* Likewise for cselib_vals. This also frees the addr_list associated with
216 unchain_one_value (cselib_val *v)
219 unchain_one_elt_list (&v->addr_list);
221 pool_free (cselib_val_pool, v);
224 /* Remove all entries from the hash table. Also used during
228 cselib_clear_table (void)
230 cselib_reset_table_with_next_value (0);
233 /* Remove all entries from the hash table, arranging for the next
234 value to be numbered NUM. */
237 cselib_reset_table_with_next_value (unsigned int num)
241 for (i = 0; i < n_used_regs; i++)
242 REG_VALUES (used_regs[i]) = 0;
248 /* ??? Preserve constants? */
249 htab_empty (cselib_hash_table);
251 n_useless_values = 0;
253 next_unknown_value = num;
255 first_containing_mem = &dummy_val;
258 /* Return the number of the next value that will be generated. */
261 cselib_get_next_unknown_value (void)
263 return next_unknown_value;
266 /* The equality test for our hash table. The first argument ENTRY is a table
267 element (i.e. a cselib_val), while the second arg X is an rtx. We know
268 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
269 CONST of an appropriate mode. */
272 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
274 struct elt_loc_list *l;
275 const cselib_val *const v = (const cselib_val *) entry;
276 rtx x = CONST_CAST_RTX ((const_rtx)x_arg);
277 enum machine_mode mode = GET_MODE (x);
279 gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
280 && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
282 if (mode != GET_MODE (v->val_rtx))
285 /* Unwrap X if necessary. */
286 if (GET_CODE (x) == CONST
287 && (CONST_INT_P (XEXP (x, 0))
288 || GET_CODE (XEXP (x, 0)) == CONST_FIXED
289 || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
292 /* We don't guarantee that distinct rtx's have different hash values,
293 so we need to do a comparison. */
294 for (l = v->locs; l; l = l->next)
295 if (rtx_equal_for_cselib_p (l->loc, x))
301 /* The hash function for our hash table. The value is always computed with
302 cselib_hash_rtx when adding an element; this function just extracts the
303 hash value from a cselib_val structure. */
306 get_value_hash (const void *entry)
308 const cselib_val *const v = (const cselib_val *) entry;
312 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
313 only return true for values which point to a cselib_val whose value
314 element has been set to zero, which implies the cselib_val will be
318 references_value_p (const_rtx x, int only_useless)
320 const enum rtx_code code = GET_CODE (x);
321 const char *fmt = GET_RTX_FORMAT (code);
324 if (GET_CODE (x) == VALUE
325 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
328 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
330 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
332 else if (fmt[i] == 'E')
333 for (j = 0; j < XVECLEN (x, i); j++)
334 if (references_value_p (XVECEXP (x, i, j), only_useless))
341 /* For all locations found in X, delete locations that reference useless
342 values (i.e. values without any location). Called through
346 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
348 cselib_val *v = (cselib_val *)*x;
349 struct elt_loc_list **p = &v->locs;
350 int had_locs = v->locs != 0;
354 if (references_value_p ((*p)->loc, 1))
355 unchain_one_elt_loc_list (p);
360 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
363 values_became_useless = 1;
368 /* If X is a value with no locations, remove it from the hashtable. */
371 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
373 cselib_val *v = (cselib_val *)*x;
375 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
377 if (cselib_discard_hook)
378 cselib_discard_hook (v);
380 CSELIB_VAL_PTR (v->val_rtx) = NULL;
381 htab_clear_slot (cselib_hash_table, x);
382 unchain_one_value (v);
389 /* Clean out useless values (i.e. those which no longer have locations
390 associated with them) from the hash table. */
393 remove_useless_values (void)
396 /* First pass: eliminate locations that reference the value. That in
397 turn can make more values useless. */
400 values_became_useless = 0;
401 htab_traverse (cselib_hash_table, discard_useless_locs, 0);
403 while (values_became_useless);
405 /* Second pass: actually remove the values. */
407 p = &first_containing_mem;
408 for (v = *p; v != &dummy_val; v = v->next_containing_mem)
412 p = &(*p)->next_containing_mem;
416 htab_traverse (cselib_hash_table, discard_useless_values, 0);
418 gcc_assert (!n_useless_values);
421 /* Arrange for a value to not be removed from the hash table even if
422 it becomes useless. */
425 cselib_preserve_value (cselib_val *v)
427 PRESERVED_VALUE_P (v->val_rtx) = 1;
430 /* Test whether a value is preserved. */
433 cselib_preserved_value_p (cselib_val *v)
435 return PRESERVED_VALUE_P (v->val_rtx);
438 /* Mark preserved values as preserved for the long term. */
441 cselib_preserve_definitely (void **slot, void *info ATTRIBUTE_UNUSED)
443 cselib_val *v = (cselib_val *)*slot;
445 if (PRESERVED_VALUE_P (v->val_rtx)
446 && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx))
447 LONG_TERM_PRESERVED_VALUE_P (v->val_rtx) = true;
452 /* Clear the preserve marks for values not preserved for the long
456 cselib_clear_preserve (void **slot, void *info ATTRIBUTE_UNUSED)
458 cselib_val *v = (cselib_val *)*slot;
460 if (PRESERVED_VALUE_P (v->val_rtx)
461 && !LONG_TERM_PRESERVED_VALUE_P (v->val_rtx))
463 PRESERVED_VALUE_P (v->val_rtx) = false;
471 /* Clean all non-constant expressions in the hash table, but retain
475 cselib_preserve_only_values (bool retain)
479 htab_traverse (cselib_hash_table,
480 retain ? cselib_preserve_definitely : cselib_clear_preserve,
483 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
484 cselib_invalidate_regno (i, reg_raw_mode[i]);
486 cselib_invalidate_mem (callmem);
488 remove_useless_values ();
490 gcc_assert (first_containing_mem == &dummy_val);
493 /* Return the mode in which a register was last set. If X is not a
494 register, return its mode. If the mode in which the register was
495 set is not known, or the value was already clobbered, return
499 cselib_reg_set_mode (const_rtx x)
504 if (REG_VALUES (REGNO (x)) == NULL
505 || REG_VALUES (REGNO (x))->elt == NULL)
508 return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
511 /* Return nonzero if we can prove that X and Y contain the same value, taking
512 our gathered information into account. */
515 rtx_equal_for_cselib_p (rtx x, rtx y)
521 if (REG_P (x) || MEM_P (x))
523 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
529 if (REG_P (y) || MEM_P (y))
531 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
540 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
541 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
543 if (GET_CODE (x) == VALUE)
545 cselib_val *e = CSELIB_VAL_PTR (x);
546 struct elt_loc_list *l;
548 for (l = e->locs; l; l = l->next)
552 /* Avoid infinite recursion. */
553 if (REG_P (t) || MEM_P (t))
555 else if (rtx_equal_for_cselib_p (t, y))
562 if (GET_CODE (y) == VALUE)
564 cselib_val *e = CSELIB_VAL_PTR (y);
565 struct elt_loc_list *l;
567 for (l = e->locs; l; l = l->next)
571 if (REG_P (t) || MEM_P (t))
573 else if (rtx_equal_for_cselib_p (x, t))
580 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
583 /* These won't be handled correctly by the code below. */
584 switch (GET_CODE (x))
591 return XEXP (x, 0) == XEXP (y, 0);
598 fmt = GET_RTX_FORMAT (code);
600 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
607 if (XWINT (x, i) != XWINT (y, i))
613 if (XINT (x, i) != XINT (y, i))
619 /* Two vectors must have the same length. */
620 if (XVECLEN (x, i) != XVECLEN (y, i))
623 /* And the corresponding elements must match. */
624 for (j = 0; j < XVECLEN (x, i); j++)
625 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
632 && targetm.commutative_p (x, UNKNOWN)
633 && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
634 && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
636 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
642 if (strcmp (XSTR (x, i), XSTR (y, i)))
647 /* These are just backpointers, so they don't matter. */
654 /* It is believed that rtx's at this level will never
655 contain anything but integers and other rtx's,
656 except for within LABEL_REFs and SYMBOL_REFs. */
664 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
665 For registers and memory locations, we look up their cselib_val structure
666 and return its VALUE element.
667 Possible reasons for return 0 are: the object is volatile, or we couldn't
668 find a register or memory location in the table and CREATE is zero. If
669 CREATE is nonzero, table elts are created for regs and mem.
670 N.B. this hash function returns the same hash value for RTXes that
671 differ only in the order of operands, thus it is suitable for comparisons
672 that take commutativity into account.
673 If we wanted to also support associative rules, we'd have to use a different
674 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
675 We used to have a MODE argument for hashing for CONST_INTs, but that
676 didn't make sense, since it caused spurious hash differences between
677 (set (reg:SI 1) (const_int))
678 (plus:SI (reg:SI 2) (reg:SI 1))
680 (plus:SI (reg:SI 2) (const_int))
681 If the mode is important in any context, it must be checked specifically
682 in a comparison anyway, since relying on hash differences is unsafe. */
685 cselib_hash_rtx (rtx x, int create)
691 unsigned int hash = 0;
694 hash += (unsigned) code + (unsigned) GET_MODE (x);
700 e = cselib_lookup (x, GET_MODE (x), create);
707 hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
708 return hash ? hash : (unsigned int) CONST_INT;
711 /* This is like the general case, except that it only counts
712 the integers representing the constant. */
713 hash += (unsigned) code + (unsigned) GET_MODE (x);
714 if (GET_MODE (x) != VOIDmode)
715 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
717 hash += ((unsigned) CONST_DOUBLE_LOW (x)
718 + (unsigned) CONST_DOUBLE_HIGH (x));
719 return hash ? hash : (unsigned int) CONST_DOUBLE;
722 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
723 hash += fixed_hash (CONST_FIXED_VALUE (x));
724 return hash ? hash : (unsigned int) CONST_FIXED;
731 units = CONST_VECTOR_NUNITS (x);
733 for (i = 0; i < units; ++i)
735 elt = CONST_VECTOR_ELT (x, i);
736 hash += cselib_hash_rtx (elt, 0);
742 /* Assume there is only one rtx object for any given label. */
744 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
745 differences and differences between each stage's debugging dumps. */
746 hash += (((unsigned int) LABEL_REF << 7)
747 + CODE_LABEL_NUMBER (XEXP (x, 0)));
748 return hash ? hash : (unsigned int) LABEL_REF;
752 /* Don't hash on the symbol's address to avoid bootstrap differences.
753 Different hash values may cause expressions to be recorded in
754 different orders and thus different registers to be used in the
755 final assembler. This also avoids differences in the dump files
756 between various stages. */
758 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
761 h += (h << 7) + *p++; /* ??? revisit */
763 hash += ((unsigned int) SYMBOL_REF << 7) + h;
764 return hash ? hash : (unsigned int) SYMBOL_REF;
776 case UNSPEC_VOLATILE:
780 if (MEM_VOLATILE_P (x))
789 i = GET_RTX_LENGTH (code) - 1;
790 fmt = GET_RTX_FORMAT (code);
797 rtx tem = XEXP (x, i);
798 unsigned int tem_hash = cselib_hash_rtx (tem, create);
807 for (j = 0; j < XVECLEN (x, i); j++)
809 unsigned int tem_hash
810 = cselib_hash_rtx (XVECEXP (x, i, j), create);
821 const unsigned char *p = (const unsigned char *) XSTR (x, i);
843 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
846 /* Create a new value structure for VALUE and initialize it. The mode of the
849 static inline cselib_val *
850 new_cselib_val (unsigned int value, enum machine_mode mode, rtx x)
852 cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
857 /* We use an alloc pool to allocate this RTL construct because it
858 accounts for about 8% of the overall memory usage. We know
859 precisely when we can have VALUE RTXen (when cselib is active)
860 so we don't need to put them in garbage collected memory.
861 ??? Why should a VALUE be an RTX in the first place? */
862 e->val_rtx = (rtx) pool_alloc (value_pool);
863 memset (e->val_rtx, 0, RTX_HDR_SIZE);
864 PUT_CODE (e->val_rtx, VALUE);
865 PUT_MODE (e->val_rtx, mode);
866 CSELIB_VAL_PTR (e->val_rtx) = e;
869 e->next_containing_mem = 0;
871 if (dump_file && (dump_flags & TDF_DETAILS))
873 fprintf (dump_file, "cselib value %u ", value);
874 if (flag_dump_noaddr || flag_dump_unnumbered)
875 fputs ("# ", dump_file);
877 fprintf (dump_file, "%p ", (void*)e);
878 print_rtl_single (dump_file, x);
879 fputc ('\n', dump_file);
885 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
886 contains the data at this address. X is a MEM that represents the
887 value. Update the two value structures to represent this situation. */
890 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
892 struct elt_loc_list *l;
894 /* Avoid duplicates. */
895 for (l = mem_elt->locs; l; l = l->next)
897 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
900 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
902 = new_elt_loc_list (mem_elt->locs,
903 replace_equiv_address_nv (x, addr_elt->val_rtx));
904 if (mem_elt->next_containing_mem == NULL)
906 mem_elt->next_containing_mem = first_containing_mem;
907 first_containing_mem = mem_elt;
911 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
912 If CREATE, make a new one if we haven't seen it before. */
915 cselib_lookup_mem (rtx x, int create)
917 enum machine_mode mode = GET_MODE (x);
923 if (MEM_VOLATILE_P (x) || mode == BLKmode
924 || !cselib_record_memory
925 || (FLOAT_MODE_P (mode) && flag_float_store))
928 /* Look up the value for the address. */
929 addr = cselib_lookup (XEXP (x, 0), mode, create);
933 /* Find a value that describes a value of our mode at that address. */
934 for (l = addr->addr_list; l; l = l->next)
935 if (GET_MODE (l->elt->val_rtx) == mode)
941 mem_elt = new_cselib_val (++next_unknown_value, mode, x);
942 add_mem_for_addr (addr, mem_elt, x);
943 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
944 mem_elt->value, INSERT);
949 /* Search thru the possible substitutions in P. We prefer a non reg
950 substitution because this allows us to expand the tree further. If
951 we find, just a reg, take the lowest regno. There may be several
952 non-reg results, we just take the first one because they will all
953 expand to the same place. */
956 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
959 rtx reg_result = NULL;
960 unsigned int regno = UINT_MAX;
961 struct elt_loc_list *p_in = p;
963 for (; p; p = p -> next)
965 /* Avoid infinite recursion trying to expand a reg into a
968 && (REGNO (p->loc) < regno)
969 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
972 regno = REGNO (p->loc);
974 /* Avoid infinite recursion and do not try to expand the
976 else if (GET_CODE (p->loc) == VALUE
977 && CSELIB_VAL_PTR (p->loc)->locs == p_in)
979 else if (!REG_P (p->loc))
982 if (dump_file && (dump_flags & TDF_DETAILS))
984 print_inline_rtx (dump_file, p->loc, 0);
985 fprintf (dump_file, "\n");
987 if (GET_CODE (p->loc) == LO_SUM
988 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
990 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
991 && XEXP (note, 0) == XEXP (p->loc, 1))
992 return XEXP (p->loc, 1);
993 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1000 if (regno != UINT_MAX)
1003 if (dump_file && (dump_flags & TDF_DETAILS))
1004 fprintf (dump_file, "r%d\n", regno);
1006 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1011 if (dump_file && (dump_flags & TDF_DETAILS))
1015 print_inline_rtx (dump_file, reg_result, 0);
1016 fprintf (dump_file, "\n");
1019 fprintf (dump_file, "NULL\n");
1025 /* Forward substitute and expand an expression out to its roots.
1026 This is the opposite of common subexpression. Because local value
1027 numbering is such a weak optimization, the expanded expression is
1028 pretty much unique (not from a pointer equals point of view but
1029 from a tree shape point of view.
1031 This function returns NULL if the expansion fails. The expansion
1032 will fail if there is no value number for one of the operands or if
1033 one of the operands has been overwritten between the current insn
1034 and the beginning of the basic block. For instance x has no
1040 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1041 It is clear on return. */
1044 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1046 struct expand_value_data evd;
1048 evd.regs_active = regs_active;
1049 evd.callback = NULL;
1050 evd.callback_arg = NULL;
1052 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1055 /* Same as cselib_expand_value_rtx, but using a callback to try to
1056 resolve VALUEs that expand to nothing. */
1059 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1060 cselib_expand_callback cb, void *data)
1062 struct expand_value_data evd;
1064 evd.regs_active = regs_active;
1066 evd.callback_arg = data;
1068 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1072 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1078 const char *format_ptr;
1079 enum machine_mode mode;
1081 code = GET_CODE (orig);
1083 /* For the context of dse, if we end up expand into a huge tree, we
1084 will not have a useful address, so we might as well just give up
1093 struct elt_list *l = REG_VALUES (REGNO (orig));
1095 if (l && l->elt == NULL)
1097 for (; l; l = l->next)
1098 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1101 int regno = REGNO (orig);
1103 /* The only thing that we are not willing to do (this
1104 is requirement of dse and if others potential uses
1105 need this function we should add a parm to control
1106 it) is that we will not substitute the
1107 STACK_POINTER_REGNUM, FRAME_POINTER or the
1110 These expansions confuses the code that notices that
1111 stores into the frame go dead at the end of the
1112 function and that the frame is not effected by calls
1113 to subroutines. If you allow the
1114 STACK_POINTER_REGNUM substitution, then dse will
1115 think that parameter pushing also goes dead which is
1116 wrong. If you allow the FRAME_POINTER or the
1117 HARD_FRAME_POINTER then you lose the opportunity to
1118 make the frame assumptions. */
1119 if (regno == STACK_POINTER_REGNUM
1120 || regno == FRAME_POINTER_REGNUM
1121 || regno == HARD_FRAME_POINTER_REGNUM)
1124 bitmap_set_bit (evd->regs_active, regno);
1126 if (dump_file && (dump_flags & TDF_DETAILS))
1127 fprintf (dump_file, "expanding: r%d into: ", regno);
1129 result = expand_loc (l->elt->locs, evd, max_depth);
1130 bitmap_clear_bit (evd->regs_active, regno);
1147 /* SCRATCH must be shared because they represent distinct values. */
1150 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1155 if (shared_const_p (orig))
1161 rtx subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1165 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1166 GET_MODE (SUBREG_REG (orig)),
1167 SUBREG_BYTE (orig));
1169 || (GET_CODE (scopy) == SUBREG
1170 && !REG_P (SUBREG_REG (scopy))
1171 && !MEM_P (SUBREG_REG (scopy))))
1172 && (REG_P (SUBREG_REG (orig))
1173 || MEM_P (SUBREG_REG (orig))))
1174 return shallow_copy_rtx (orig);
1181 if (dump_file && (dump_flags & TDF_DETAILS))
1183 fputs ("\nexpanding ", dump_file);
1184 print_rtl_single (dump_file, orig);
1185 fputs (" into...", dump_file);
1192 result = evd->callback (orig, evd->regs_active, max_depth,
1197 result = cselib_expand_value_rtx_1 (result, evd, max_depth);
1201 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1208 /* Copy the various flags, fields, and other information. We assume
1209 that all fields need copying, and then clear the fields that should
1210 not be copied. That is the sensible default behavior, and forces
1211 us to explicitly document why we are *not* copying a flag. */
1212 copy = shallow_copy_rtx (orig);
1214 format_ptr = GET_RTX_FORMAT (code);
1216 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1217 switch (*format_ptr++)
1220 if (XEXP (orig, i) != NULL)
1222 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1226 XEXP (copy, i) = result;
1232 if (XVEC (orig, i) != NULL)
1234 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1235 for (j = 0; j < XVECLEN (copy, i); j++)
1237 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1238 evd, max_depth - 1);
1241 XVECEXP (copy, i, j) = result;
1255 /* These are left unchanged. */
1262 mode = GET_MODE (copy);
1263 /* If an operand has been simplified into CONST_INT, which doesn't
1264 have a mode and the mode isn't derivable from whole rtx's mode,
1265 try simplify_*_operation first with mode from original's operand
1266 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1268 switch (GET_RTX_CLASS (code))
1271 if (CONST_INT_P (XEXP (copy, 0))
1272 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1274 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1275 GET_MODE (XEXP (orig, 0)));
1280 case RTX_COMM_ARITH:
1282 /* These expressions can derive operand modes from the whole rtx's mode. */
1285 case RTX_BITFIELD_OPS:
1286 if (CONST_INT_P (XEXP (copy, 0))
1287 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1289 scopy = simplify_ternary_operation (code, mode,
1290 GET_MODE (XEXP (orig, 0)),
1291 XEXP (copy, 0), XEXP (copy, 1),
1298 case RTX_COMM_COMPARE:
1299 if (CONST_INT_P (XEXP (copy, 0))
1300 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1301 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1302 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1304 scopy = simplify_relational_operation (code, mode,
1305 (GET_MODE (XEXP (orig, 0))
1307 ? GET_MODE (XEXP (orig, 0))
1308 : GET_MODE (XEXP (orig, 1)),
1318 if (scopy == NULL_RTX)
1321 = gen_rtx_CONST (GET_MODE (XEXP (orig, 0)), XEXP (copy, 0));
1322 if (dump_file && (dump_flags & TDF_DETAILS))
1323 fprintf (dump_file, " wrapping const_int result in const to preserve mode %s\n",
1324 GET_MODE_NAME (GET_MODE (XEXP (copy, 0))));
1326 scopy = simplify_rtx (copy);
1329 if (GET_MODE (copy) != GET_MODE (scopy))
1330 scopy = wrap_constant (GET_MODE (copy), scopy);
1336 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1337 with VALUE expressions. This way, it becomes independent of changes
1338 to registers and memory.
1339 X isn't actually modified; if modifications are needed, new rtl is
1340 allocated. However, the return value can share rtl with X. */
1343 cselib_subst_to_values (rtx x)
1345 enum rtx_code code = GET_CODE (x);
1346 const char *fmt = GET_RTX_FORMAT (code);
1355 l = REG_VALUES (REGNO (x));
1356 if (l && l->elt == NULL)
1358 for (; l; l = l->next)
1359 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1360 return l->elt->val_rtx;
1365 e = cselib_lookup_mem (x, 0);
1368 /* This happens for autoincrements. Assign a value that doesn't
1370 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1386 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1393 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1397 rtx t = cselib_subst_to_values (XEXP (x, i));
1399 if (t != XEXP (x, i) && x == copy)
1400 copy = shallow_copy_rtx (x);
1404 else if (fmt[i] == 'E')
1408 for (j = 0; j < XVECLEN (x, i); j++)
1410 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1412 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
1415 copy = shallow_copy_rtx (x);
1417 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
1418 for (k = 0; k < j; k++)
1419 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
1422 XVECEXP (copy, i, j) = t;
1430 /* Log a lookup of X to the cselib table along with the result RET. */
1433 cselib_log_lookup (rtx x, cselib_val *ret)
1435 if (dump_file && (dump_flags & TDF_DETAILS))
1437 fputs ("cselib lookup ", dump_file);
1438 print_inline_rtx (dump_file, x, 2);
1439 fprintf (dump_file, " => %u\n", ret ? ret->value : 0);
1445 /* Look up the rtl expression X in our tables and return the value it has.
1446 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1447 we create a new one if possible, using mode MODE if X doesn't have a mode
1448 (i.e. because it's a constant). */
1451 cselib_lookup (rtx x, enum machine_mode mode, int create)
1455 unsigned int hashval;
1457 if (GET_MODE (x) != VOIDmode)
1458 mode = GET_MODE (x);
1460 if (GET_CODE (x) == VALUE)
1461 return CSELIB_VAL_PTR (x);
1466 unsigned int i = REGNO (x);
1469 if (l && l->elt == NULL)
1471 for (; l; l = l->next)
1472 if (mode == GET_MODE (l->elt->val_rtx))
1473 return cselib_log_lookup (x, l->elt);
1476 return cselib_log_lookup (x, 0);
1478 if (i < FIRST_PSEUDO_REGISTER)
1480 unsigned int n = hard_regno_nregs[i][mode];
1482 if (n > max_value_regs)
1486 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1487 e->locs = new_elt_loc_list (e->locs, x);
1488 if (REG_VALUES (i) == 0)
1490 /* Maintain the invariant that the first entry of
1491 REG_VALUES, if present, must be the value used to set the
1492 register, or NULL. */
1493 used_regs[n_used_regs++] = i;
1494 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1496 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1497 slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
1499 return cselib_log_lookup (x, e);
1503 return cselib_log_lookup (x, cselib_lookup_mem (x, create));
1505 hashval = cselib_hash_rtx (x, create);
1506 /* Can't even create if hashing is not possible. */
1508 return cselib_log_lookup (x, 0);
1510 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1511 hashval, create ? INSERT : NO_INSERT);
1513 return cselib_log_lookup (x, 0);
1515 e = (cselib_val *) *slot;
1517 return cselib_log_lookup (x, e);
1519 e = new_cselib_val (hashval, mode, x);
1521 /* We have to fill the slot before calling cselib_subst_to_values:
1522 the hash table is inconsistent until we do so, and
1523 cselib_subst_to_values will need to do lookups. */
1525 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1526 return cselib_log_lookup (x, e);
1529 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1530 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1531 is used to determine how many hard registers are being changed. If MODE
1532 is VOIDmode, then only REGNO is being changed; this is used when
1533 invalidating call clobbered registers across a call. */
1536 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1538 unsigned int endregno;
1541 /* If we see pseudos after reload, something is _wrong_. */
1542 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1543 || reg_renumber[regno] < 0);
1545 /* Determine the range of registers that must be invalidated. For
1546 pseudos, only REGNO is affected. For hard regs, we must take MODE
1547 into account, and we must also invalidate lower register numbers
1548 if they contain values that overlap REGNO. */
1549 if (regno < FIRST_PSEUDO_REGISTER)
1551 gcc_assert (mode != VOIDmode);
1553 if (regno < max_value_regs)
1556 i = regno - max_value_regs;
1558 endregno = end_hard_regno (mode, regno);
1563 endregno = regno + 1;
1566 for (; i < endregno; i++)
1568 struct elt_list **l = ®_VALUES (i);
1570 /* Go through all known values for this reg; if it overlaps the range
1571 we're invalidating, remove the value. */
1574 cselib_val *v = (*l)->elt;
1575 struct elt_loc_list **p;
1576 unsigned int this_last = i;
1578 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1579 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1581 if (this_last < regno || v == NULL)
1587 /* We have an overlap. */
1588 if (*l == REG_VALUES (i))
1590 /* Maintain the invariant that the first entry of
1591 REG_VALUES, if present, must be the value used to set
1592 the register, or NULL. This is also nice because
1593 then we won't push the same regno onto user_regs
1599 unchain_one_elt_list (l);
1601 /* Now, we clear the mapping from value to reg. It must exist, so
1602 this code will crash intentionally if it doesn't. */
1603 for (p = &v->locs; ; p = &(*p)->next)
1607 if (REG_P (x) && REGNO (x) == i)
1609 unchain_one_elt_loc_list (p);
1613 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1619 /* Return 1 if X has a value that can vary even between two
1620 executions of the program. 0 means X can be compared reliably
1621 against certain constants or near-constants. */
1624 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1626 /* We actually don't need to verify very hard. This is because
1627 if X has actually changed, we invalidate the memory anyway,
1628 so assume that all common memory addresses are
1633 /* Invalidate any locations in the table which are changed because of a
1634 store to MEM_RTX. If this is called because of a non-const call
1635 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1638 cselib_invalidate_mem (rtx mem_rtx)
1640 cselib_val **vp, *v, *next;
1644 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1645 mem_rtx = canon_rtx (mem_rtx);
1647 vp = &first_containing_mem;
1648 for (v = *vp; v != &dummy_val; v = next)
1650 bool has_mem = false;
1651 struct elt_loc_list **p = &v->locs;
1652 int had_locs = v->locs != 0;
1658 struct elt_list **mem_chain;
1660 /* MEMs may occur in locations only at the top level; below
1661 that every MEM or REG is substituted by its VALUE. */
1667 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1668 && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1669 x, NULL_RTX, cselib_rtx_varies_p))
1677 /* This one overlaps. */
1678 /* We must have a mapping from this MEM's address to the
1679 value (E). Remove that, too. */
1680 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1681 mem_chain = &addr->addr_list;
1684 if ((*mem_chain)->elt == v)
1686 unchain_one_elt_list (mem_chain);
1690 mem_chain = &(*mem_chain)->next;
1693 unchain_one_elt_loc_list (p);
1696 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1699 next = v->next_containing_mem;
1703 vp = &(*vp)->next_containing_mem;
1706 v->next_containing_mem = NULL;
1711 /* Invalidate DEST, which is being assigned to or clobbered. */
1714 cselib_invalidate_rtx (rtx dest)
1716 while (GET_CODE (dest) == SUBREG
1717 || GET_CODE (dest) == ZERO_EXTRACT
1718 || GET_CODE (dest) == STRICT_LOW_PART)
1719 dest = XEXP (dest, 0);
1722 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1723 else if (MEM_P (dest))
1724 cselib_invalidate_mem (dest);
1726 /* Some machines don't define AUTO_INC_DEC, but they still use push
1727 instructions. We need to catch that case here in order to
1728 invalidate the stack pointer correctly. Note that invalidating
1729 the stack pointer is different from invalidating DEST. */
1730 if (push_operand (dest, GET_MODE (dest)))
1731 cselib_invalidate_rtx (stack_pointer_rtx);
1734 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1737 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1738 void *data ATTRIBUTE_UNUSED)
1740 cselib_invalidate_rtx (dest);
1743 /* Record the result of a SET instruction. DEST is being set; the source
1744 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1745 describes its address. */
1748 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1750 int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1752 if (src_elt == 0 || side_effects_p (dest))
1757 if (dreg < FIRST_PSEUDO_REGISTER)
1759 unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1761 if (n > max_value_regs)
1765 if (REG_VALUES (dreg) == 0)
1767 used_regs[n_used_regs++] = dreg;
1768 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1772 /* The register should have been invalidated. */
1773 gcc_assert (REG_VALUES (dreg)->elt == 0);
1774 REG_VALUES (dreg)->elt = src_elt;
1777 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1779 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1781 else if (MEM_P (dest) && dest_addr_elt != 0
1782 && cselib_record_memory)
1784 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1786 add_mem_for_addr (dest_addr_elt, src_elt, dest);
1790 /* There is no good way to determine how many elements there can be
1791 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1792 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1794 /* Record the effects of any sets in INSN. */
1796 cselib_record_sets (rtx insn)
1800 struct cselib_set sets[MAX_SETS];
1801 rtx body = PATTERN (insn);
1804 body = PATTERN (insn);
1805 if (GET_CODE (body) == COND_EXEC)
1807 cond = COND_EXEC_TEST (body);
1808 body = COND_EXEC_CODE (body);
1811 /* Find all sets. */
1812 if (GET_CODE (body) == SET)
1814 sets[0].src = SET_SRC (body);
1815 sets[0].dest = SET_DEST (body);
1818 else if (GET_CODE (body) == PARALLEL)
1820 /* Look through the PARALLEL and record the values being
1821 set, if possible. Also handle any CLOBBERs. */
1822 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1824 rtx x = XVECEXP (body, 0, i);
1826 if (GET_CODE (x) == SET)
1828 sets[n_sets].src = SET_SRC (x);
1829 sets[n_sets].dest = SET_DEST (x);
1836 && MEM_P (sets[0].src)
1837 && !cselib_record_memory
1838 && MEM_READONLY_P (sets[0].src))
1840 rtx note = find_reg_equal_equiv_note (insn);
1842 if (note && CONSTANT_P (XEXP (note, 0)))
1843 sets[0].src = XEXP (note, 0);
1846 /* Look up the values that are read. Do this before invalidating the
1847 locations that are written. */
1848 for (i = 0; i < n_sets; i++)
1850 rtx dest = sets[i].dest;
1852 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1853 the low part after invalidating any knowledge about larger modes. */
1854 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1855 sets[i].dest = dest = XEXP (dest, 0);
1857 /* We don't know how to record anything but REG or MEM. */
1859 || (MEM_P (dest) && cselib_record_memory))
1861 rtx src = sets[i].src;
1863 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1864 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1866 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1868 sets[i].dest_addr_elt = 0;
1872 if (cselib_record_sets_hook)
1873 cselib_record_sets_hook (insn, sets, n_sets);
1875 /* Invalidate all locations written by this insn. Note that the elts we
1876 looked up in the previous loop aren't affected, just some of their
1877 locations may go away. */
1878 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1880 /* If this is an asm, look for duplicate sets. This can happen when the
1881 user uses the same value as an output multiple times. This is valid
1882 if the outputs are not actually used thereafter. Treat this case as
1883 if the value isn't actually set. We do this by smashing the destination
1884 to pc_rtx, so that we won't record the value later. */
1885 if (n_sets >= 2 && asm_noperands (body) >= 0)
1887 for (i = 0; i < n_sets; i++)
1889 rtx dest = sets[i].dest;
1890 if (REG_P (dest) || MEM_P (dest))
1893 for (j = i + 1; j < n_sets; j++)
1894 if (rtx_equal_p (dest, sets[j].dest))
1896 sets[i].dest = pc_rtx;
1897 sets[j].dest = pc_rtx;
1903 /* Now enter the equivalences in our tables. */
1904 for (i = 0; i < n_sets; i++)
1906 rtx dest = sets[i].dest;
1908 || (MEM_P (dest) && cselib_record_memory))
1909 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1913 /* Record the effects of INSN. */
1916 cselib_process_insn (rtx insn)
1921 cselib_current_insn = insn;
1923 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1926 && find_reg_note (insn, REG_SETJMP, NULL))
1927 || (NONJUMP_INSN_P (insn)
1928 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1929 && MEM_VOLATILE_P (PATTERN (insn))))
1931 cselib_reset_table_with_next_value (next_unknown_value);
1935 if (! INSN_P (insn))
1937 cselib_current_insn = 0;
1941 /* If this is a call instruction, forget anything stored in a
1942 call clobbered register, or, if this is not a const call, in
1946 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1947 if (call_used_regs[i]
1948 || (REG_VALUES (i) && REG_VALUES (i)->elt
1949 && HARD_REGNO_CALL_PART_CLOBBERED (i,
1950 GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1951 cselib_invalidate_regno (i, reg_raw_mode[i]);
1953 /* Since it is not clear how cselib is going to be used, be
1954 conservative here and treat looping pure or const functions
1955 as if they were regular functions. */
1956 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1957 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1958 cselib_invalidate_mem (callmem);
1961 cselib_record_sets (insn);
1964 /* Clobber any registers which appear in REG_INC notes. We
1965 could keep track of the changes to their values, but it is
1966 unlikely to help. */
1967 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1968 if (REG_NOTE_KIND (x) == REG_INC)
1969 cselib_invalidate_rtx (XEXP (x, 0));
1972 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1973 after we have processed the insn. */
1975 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1976 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1977 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
1979 cselib_current_insn = 0;
1981 if (n_useless_values > MAX_USELESS_VALUES
1982 /* remove_useless_values is linear in the hash table size. Avoid
1983 quadratic behavior for very large hashtables with very few
1984 useless elements. */
1985 && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
1986 remove_useless_values ();
1989 /* Initialize cselib for one pass. The caller must also call
1990 init_alias_analysis. */
1993 cselib_init (bool record_memory)
1995 elt_list_pool = create_alloc_pool ("elt_list",
1996 sizeof (struct elt_list), 10);
1997 elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
1998 sizeof (struct elt_loc_list), 10);
1999 cselib_val_pool = create_alloc_pool ("cselib_val_list",
2000 sizeof (cselib_val), 10);
2001 value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2002 cselib_record_memory = record_memory;
2004 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2005 see canon_true_dependence. This is only created once. */
2007 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2009 cselib_nregs = max_reg_num ();
2011 /* We preserve reg_values to allow expensive clearing of the whole thing.
2012 Reallocate it however if it happens to be too large. */
2013 if (!reg_values || reg_values_size < cselib_nregs
2014 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2018 /* Some space for newly emit instructions so we don't end up
2019 reallocating in between passes. */
2020 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2021 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2023 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2025 cselib_hash_table = htab_create (31, get_value_hash,
2026 entry_and_rtx_equal_p, NULL);
2029 /* Called when the current user is done with cselib. */
2032 cselib_finish (void)
2034 cselib_discard_hook = NULL;
2035 free_alloc_pool (elt_list_pool);
2036 free_alloc_pool (elt_loc_list_pool);
2037 free_alloc_pool (cselib_val_pool);
2038 free_alloc_pool (value_pool);
2039 cselib_clear_table ();
2040 htab_delete (cselib_hash_table);
2043 cselib_hash_table = 0;
2044 n_useless_values = 0;
2045 next_unknown_value = 0;
2048 /* Dump the cselib_val *X to FILE *info. */
2051 dump_cselib_val (void **x, void *info)
2053 cselib_val *v = (cselib_val *)*x;
2054 FILE *out = (FILE *)info;
2055 bool need_lf = true;
2057 print_inline_rtx (out, v->val_rtx, 0);
2061 struct elt_loc_list *l = v->locs;
2067 fputs (" locs:", out);
2070 fprintf (out, "\n from insn %i ",
2071 INSN_UID (l->setting_insn));
2072 print_inline_rtx (out, l->loc, 4);
2074 while ((l = l->next));
2079 fputs (" no locs", out);
2085 struct elt_list *e = v->addr_list;
2091 fputs (" addr list:", out);
2095 print_inline_rtx (out, e->elt->val_rtx, 2);
2097 while ((e = e->next));
2102 fputs (" no addrs", out);
2106 if (v->next_containing_mem == &dummy_val)
2107 fputs (" last mem\n", out);
2108 else if (v->next_containing_mem)
2110 fputs (" next mem ", out);
2111 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2120 /* Dump to OUT everything in the CSELIB table. */
2123 dump_cselib_table (FILE *out)
2125 fprintf (out, "cselib hash table:\n");
2126 htab_traverse (cselib_hash_table, dump_cselib_val, out);
2127 if (first_containing_mem != &dummy_val)
2129 fputs ("first mem ", out);
2130 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2133 fprintf (out, "last unknown value %i\n", next_unknown_value);
2136 #include "gt-cselib.h"