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 some expressions. The CB function should return ORIG if it
1057 can't or does not want to deal with a certain RTX. Any other
1058 return value, including NULL, will be used as the expansion for
1059 VALUE, without any further changes. */
1062 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1063 cselib_expand_callback cb, void *data)
1065 struct expand_value_data evd;
1067 evd.regs_active = regs_active;
1069 evd.callback_arg = data;
1071 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1074 /* Internal implementation of cselib_expand_value_rtx and
1075 cselib_expand_value_rtx_cb. */
1078 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1084 const char *format_ptr;
1085 enum machine_mode mode;
1087 code = GET_CODE (orig);
1089 /* For the context of dse, if we end up expand into a huge tree, we
1090 will not have a useful address, so we might as well just give up
1099 struct elt_list *l = REG_VALUES (REGNO (orig));
1101 if (l && l->elt == NULL)
1103 for (; l; l = l->next)
1104 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1107 int regno = REGNO (orig);
1109 /* The only thing that we are not willing to do (this
1110 is requirement of dse and if others potential uses
1111 need this function we should add a parm to control
1112 it) is that we will not substitute the
1113 STACK_POINTER_REGNUM, FRAME_POINTER or the
1116 These expansions confuses the code that notices that
1117 stores into the frame go dead at the end of the
1118 function and that the frame is not effected by calls
1119 to subroutines. If you allow the
1120 STACK_POINTER_REGNUM substitution, then dse will
1121 think that parameter pushing also goes dead which is
1122 wrong. If you allow the FRAME_POINTER or the
1123 HARD_FRAME_POINTER then you lose the opportunity to
1124 make the frame assumptions. */
1125 if (regno == STACK_POINTER_REGNUM
1126 || regno == FRAME_POINTER_REGNUM
1127 || regno == HARD_FRAME_POINTER_REGNUM)
1130 bitmap_set_bit (evd->regs_active, regno);
1132 if (dump_file && (dump_flags & TDF_DETAILS))
1133 fprintf (dump_file, "expanding: r%d into: ", regno);
1135 result = expand_loc (l->elt->locs, evd, max_depth);
1136 bitmap_clear_bit (evd->regs_active, regno);
1153 /* SCRATCH must be shared because they represent distinct values. */
1156 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1161 if (shared_const_p (orig))
1171 subreg = evd->callback (orig, evd->regs_active, max_depth,
1177 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1181 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1182 GET_MODE (SUBREG_REG (orig)),
1183 SUBREG_BYTE (orig));
1185 || (GET_CODE (scopy) == SUBREG
1186 && !REG_P (SUBREG_REG (scopy))
1187 && !MEM_P (SUBREG_REG (scopy))))
1197 if (dump_file && (dump_flags & TDF_DETAILS))
1199 fputs ("\nexpanding ", dump_file);
1200 print_rtl_single (dump_file, orig);
1201 fputs (" into...", dump_file);
1206 result = evd->callback (orig, evd->regs_active, max_depth,
1213 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1220 /* Copy the various flags, fields, and other information. We assume
1221 that all fields need copying, and then clear the fields that should
1222 not be copied. That is the sensible default behavior, and forces
1223 us to explicitly document why we are *not* copying a flag. */
1224 copy = shallow_copy_rtx (orig);
1226 format_ptr = GET_RTX_FORMAT (code);
1228 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1229 switch (*format_ptr++)
1232 if (XEXP (orig, i) != NULL)
1234 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1238 XEXP (copy, i) = result;
1244 if (XVEC (orig, i) != NULL)
1246 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1247 for (j = 0; j < XVECLEN (copy, i); j++)
1249 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1250 evd, max_depth - 1);
1253 XVECEXP (copy, i, j) = result;
1267 /* These are left unchanged. */
1274 mode = GET_MODE (copy);
1275 /* If an operand has been simplified into CONST_INT, which doesn't
1276 have a mode and the mode isn't derivable from whole rtx's mode,
1277 try simplify_*_operation first with mode from original's operand
1278 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1280 switch (GET_RTX_CLASS (code))
1283 if (CONST_INT_P (XEXP (copy, 0))
1284 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1286 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1287 GET_MODE (XEXP (orig, 0)));
1292 case RTX_COMM_ARITH:
1294 /* These expressions can derive operand modes from the whole rtx's mode. */
1297 case RTX_BITFIELD_OPS:
1298 if (CONST_INT_P (XEXP (copy, 0))
1299 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1301 scopy = simplify_ternary_operation (code, mode,
1302 GET_MODE (XEXP (orig, 0)),
1303 XEXP (copy, 0), XEXP (copy, 1),
1310 case RTX_COMM_COMPARE:
1311 if (CONST_INT_P (XEXP (copy, 0))
1312 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1313 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1314 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1316 scopy = simplify_relational_operation (code, mode,
1317 (GET_MODE (XEXP (orig, 0))
1319 ? GET_MODE (XEXP (orig, 0))
1320 : GET_MODE (XEXP (orig, 1)),
1330 if (scopy == NULL_RTX)
1333 = gen_rtx_CONST (GET_MODE (XEXP (orig, 0)), XEXP (copy, 0));
1334 if (dump_file && (dump_flags & TDF_DETAILS))
1335 fprintf (dump_file, " wrapping const_int result in const to preserve mode %s\n",
1336 GET_MODE_NAME (GET_MODE (XEXP (copy, 0))));
1338 scopy = simplify_rtx (copy);
1341 if (GET_MODE (copy) != GET_MODE (scopy))
1342 scopy = wrap_constant (GET_MODE (copy), scopy);
1348 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1349 with VALUE expressions. This way, it becomes independent of changes
1350 to registers and memory.
1351 X isn't actually modified; if modifications are needed, new rtl is
1352 allocated. However, the return value can share rtl with X. */
1355 cselib_subst_to_values (rtx x)
1357 enum rtx_code code = GET_CODE (x);
1358 const char *fmt = GET_RTX_FORMAT (code);
1367 l = REG_VALUES (REGNO (x));
1368 if (l && l->elt == NULL)
1370 for (; l; l = l->next)
1371 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1372 return l->elt->val_rtx;
1377 e = cselib_lookup_mem (x, 0);
1380 /* This happens for autoincrements. Assign a value that doesn't
1382 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1398 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1405 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1409 rtx t = cselib_subst_to_values (XEXP (x, i));
1411 if (t != XEXP (x, i) && x == copy)
1412 copy = shallow_copy_rtx (x);
1416 else if (fmt[i] == 'E')
1420 for (j = 0; j < XVECLEN (x, i); j++)
1422 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1424 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
1427 copy = shallow_copy_rtx (x);
1429 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
1430 for (k = 0; k < j; k++)
1431 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
1434 XVECEXP (copy, i, j) = t;
1442 /* Log a lookup of X to the cselib table along with the result RET. */
1445 cselib_log_lookup (rtx x, cselib_val *ret)
1447 if (dump_file && (dump_flags & TDF_DETAILS))
1449 fputs ("cselib lookup ", dump_file);
1450 print_inline_rtx (dump_file, x, 2);
1451 fprintf (dump_file, " => %u\n", ret ? ret->value : 0);
1457 /* Look up the rtl expression X in our tables and return the value it has.
1458 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1459 we create a new one if possible, using mode MODE if X doesn't have a mode
1460 (i.e. because it's a constant). */
1463 cselib_lookup (rtx x, enum machine_mode mode, int create)
1467 unsigned int hashval;
1469 if (GET_MODE (x) != VOIDmode)
1470 mode = GET_MODE (x);
1472 if (GET_CODE (x) == VALUE)
1473 return CSELIB_VAL_PTR (x);
1478 unsigned int i = REGNO (x);
1481 if (l && l->elt == NULL)
1483 for (; l; l = l->next)
1484 if (mode == GET_MODE (l->elt->val_rtx))
1485 return cselib_log_lookup (x, l->elt);
1488 return cselib_log_lookup (x, 0);
1490 if (i < FIRST_PSEUDO_REGISTER)
1492 unsigned int n = hard_regno_nregs[i][mode];
1494 if (n > max_value_regs)
1498 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1499 e->locs = new_elt_loc_list (e->locs, x);
1500 if (REG_VALUES (i) == 0)
1502 /* Maintain the invariant that the first entry of
1503 REG_VALUES, if present, must be the value used to set the
1504 register, or NULL. */
1505 used_regs[n_used_regs++] = i;
1506 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1508 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1509 slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
1511 return cselib_log_lookup (x, e);
1515 return cselib_log_lookup (x, cselib_lookup_mem (x, create));
1517 hashval = cselib_hash_rtx (x, create);
1518 /* Can't even create if hashing is not possible. */
1520 return cselib_log_lookup (x, 0);
1522 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1523 hashval, create ? INSERT : NO_INSERT);
1525 return cselib_log_lookup (x, 0);
1527 e = (cselib_val *) *slot;
1529 return cselib_log_lookup (x, e);
1531 e = new_cselib_val (hashval, mode, x);
1533 /* We have to fill the slot before calling cselib_subst_to_values:
1534 the hash table is inconsistent until we do so, and
1535 cselib_subst_to_values will need to do lookups. */
1537 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1538 return cselib_log_lookup (x, e);
1541 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1542 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1543 is used to determine how many hard registers are being changed. If MODE
1544 is VOIDmode, then only REGNO is being changed; this is used when
1545 invalidating call clobbered registers across a call. */
1548 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1550 unsigned int endregno;
1553 /* If we see pseudos after reload, something is _wrong_. */
1554 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1555 || reg_renumber[regno] < 0);
1557 /* Determine the range of registers that must be invalidated. For
1558 pseudos, only REGNO is affected. For hard regs, we must take MODE
1559 into account, and we must also invalidate lower register numbers
1560 if they contain values that overlap REGNO. */
1561 if (regno < FIRST_PSEUDO_REGISTER)
1563 gcc_assert (mode != VOIDmode);
1565 if (regno < max_value_regs)
1568 i = regno - max_value_regs;
1570 endregno = end_hard_regno (mode, regno);
1575 endregno = regno + 1;
1578 for (; i < endregno; i++)
1580 struct elt_list **l = ®_VALUES (i);
1582 /* Go through all known values for this reg; if it overlaps the range
1583 we're invalidating, remove the value. */
1586 cselib_val *v = (*l)->elt;
1587 struct elt_loc_list **p;
1588 unsigned int this_last = i;
1590 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1591 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1593 if (this_last < regno || v == NULL)
1599 /* We have an overlap. */
1600 if (*l == REG_VALUES (i))
1602 /* Maintain the invariant that the first entry of
1603 REG_VALUES, if present, must be the value used to set
1604 the register, or NULL. This is also nice because
1605 then we won't push the same regno onto user_regs
1611 unchain_one_elt_list (l);
1613 /* Now, we clear the mapping from value to reg. It must exist, so
1614 this code will crash intentionally if it doesn't. */
1615 for (p = &v->locs; ; p = &(*p)->next)
1619 if (REG_P (x) && REGNO (x) == i)
1621 unchain_one_elt_loc_list (p);
1625 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1631 /* Return 1 if X has a value that can vary even between two
1632 executions of the program. 0 means X can be compared reliably
1633 against certain constants or near-constants. */
1636 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1638 /* We actually don't need to verify very hard. This is because
1639 if X has actually changed, we invalidate the memory anyway,
1640 so assume that all common memory addresses are
1645 /* Invalidate any locations in the table which are changed because of a
1646 store to MEM_RTX. If this is called because of a non-const call
1647 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1650 cselib_invalidate_mem (rtx mem_rtx)
1652 cselib_val **vp, *v, *next;
1656 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1657 mem_rtx = canon_rtx (mem_rtx);
1659 vp = &first_containing_mem;
1660 for (v = *vp; v != &dummy_val; v = next)
1662 bool has_mem = false;
1663 struct elt_loc_list **p = &v->locs;
1664 int had_locs = v->locs != 0;
1670 struct elt_list **mem_chain;
1672 /* MEMs may occur in locations only at the top level; below
1673 that every MEM or REG is substituted by its VALUE. */
1679 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1680 && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1681 x, NULL_RTX, cselib_rtx_varies_p))
1689 /* This one overlaps. */
1690 /* We must have a mapping from this MEM's address to the
1691 value (E). Remove that, too. */
1692 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1693 mem_chain = &addr->addr_list;
1696 if ((*mem_chain)->elt == v)
1698 unchain_one_elt_list (mem_chain);
1702 mem_chain = &(*mem_chain)->next;
1705 unchain_one_elt_loc_list (p);
1708 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1711 next = v->next_containing_mem;
1715 vp = &(*vp)->next_containing_mem;
1718 v->next_containing_mem = NULL;
1723 /* Invalidate DEST, which is being assigned to or clobbered. */
1726 cselib_invalidate_rtx (rtx dest)
1728 while (GET_CODE (dest) == SUBREG
1729 || GET_CODE (dest) == ZERO_EXTRACT
1730 || GET_CODE (dest) == STRICT_LOW_PART)
1731 dest = XEXP (dest, 0);
1734 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1735 else if (MEM_P (dest))
1736 cselib_invalidate_mem (dest);
1738 /* Some machines don't define AUTO_INC_DEC, but they still use push
1739 instructions. We need to catch that case here in order to
1740 invalidate the stack pointer correctly. Note that invalidating
1741 the stack pointer is different from invalidating DEST. */
1742 if (push_operand (dest, GET_MODE (dest)))
1743 cselib_invalidate_rtx (stack_pointer_rtx);
1746 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1749 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1750 void *data ATTRIBUTE_UNUSED)
1752 cselib_invalidate_rtx (dest);
1755 /* Record the result of a SET instruction. DEST is being set; the source
1756 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1757 describes its address. */
1760 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1762 int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1764 if (src_elt == 0 || side_effects_p (dest))
1769 if (dreg < FIRST_PSEUDO_REGISTER)
1771 unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1773 if (n > max_value_regs)
1777 if (REG_VALUES (dreg) == 0)
1779 used_regs[n_used_regs++] = dreg;
1780 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1784 /* The register should have been invalidated. */
1785 gcc_assert (REG_VALUES (dreg)->elt == 0);
1786 REG_VALUES (dreg)->elt = src_elt;
1789 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1791 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1793 else if (MEM_P (dest) && dest_addr_elt != 0
1794 && cselib_record_memory)
1796 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1798 add_mem_for_addr (dest_addr_elt, src_elt, dest);
1802 /* There is no good way to determine how many elements there can be
1803 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1804 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1806 /* Record the effects of any sets in INSN. */
1808 cselib_record_sets (rtx insn)
1812 struct cselib_set sets[MAX_SETS];
1813 rtx body = PATTERN (insn);
1816 body = PATTERN (insn);
1817 if (GET_CODE (body) == COND_EXEC)
1819 cond = COND_EXEC_TEST (body);
1820 body = COND_EXEC_CODE (body);
1823 /* Find all sets. */
1824 if (GET_CODE (body) == SET)
1826 sets[0].src = SET_SRC (body);
1827 sets[0].dest = SET_DEST (body);
1830 else if (GET_CODE (body) == PARALLEL)
1832 /* Look through the PARALLEL and record the values being
1833 set, if possible. Also handle any CLOBBERs. */
1834 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1836 rtx x = XVECEXP (body, 0, i);
1838 if (GET_CODE (x) == SET)
1840 sets[n_sets].src = SET_SRC (x);
1841 sets[n_sets].dest = SET_DEST (x);
1848 && MEM_P (sets[0].src)
1849 && !cselib_record_memory
1850 && MEM_READONLY_P (sets[0].src))
1852 rtx note = find_reg_equal_equiv_note (insn);
1854 if (note && CONSTANT_P (XEXP (note, 0)))
1855 sets[0].src = XEXP (note, 0);
1858 /* Look up the values that are read. Do this before invalidating the
1859 locations that are written. */
1860 for (i = 0; i < n_sets; i++)
1862 rtx dest = sets[i].dest;
1864 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1865 the low part after invalidating any knowledge about larger modes. */
1866 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1867 sets[i].dest = dest = XEXP (dest, 0);
1869 /* We don't know how to record anything but REG or MEM. */
1871 || (MEM_P (dest) && cselib_record_memory))
1873 rtx src = sets[i].src;
1875 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1876 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1878 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1880 sets[i].dest_addr_elt = 0;
1884 if (cselib_record_sets_hook)
1885 cselib_record_sets_hook (insn, sets, n_sets);
1887 /* Invalidate all locations written by this insn. Note that the elts we
1888 looked up in the previous loop aren't affected, just some of their
1889 locations may go away. */
1890 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1892 /* If this is an asm, look for duplicate sets. This can happen when the
1893 user uses the same value as an output multiple times. This is valid
1894 if the outputs are not actually used thereafter. Treat this case as
1895 if the value isn't actually set. We do this by smashing the destination
1896 to pc_rtx, so that we won't record the value later. */
1897 if (n_sets >= 2 && asm_noperands (body) >= 0)
1899 for (i = 0; i < n_sets; i++)
1901 rtx dest = sets[i].dest;
1902 if (REG_P (dest) || MEM_P (dest))
1905 for (j = i + 1; j < n_sets; j++)
1906 if (rtx_equal_p (dest, sets[j].dest))
1908 sets[i].dest = pc_rtx;
1909 sets[j].dest = pc_rtx;
1915 /* Now enter the equivalences in our tables. */
1916 for (i = 0; i < n_sets; i++)
1918 rtx dest = sets[i].dest;
1920 || (MEM_P (dest) && cselib_record_memory))
1921 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1925 /* Record the effects of INSN. */
1928 cselib_process_insn (rtx insn)
1933 cselib_current_insn = insn;
1935 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1938 && find_reg_note (insn, REG_SETJMP, NULL))
1939 || (NONJUMP_INSN_P (insn)
1940 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1941 && MEM_VOLATILE_P (PATTERN (insn))))
1943 cselib_reset_table_with_next_value (next_unknown_value);
1947 if (! INSN_P (insn))
1949 cselib_current_insn = 0;
1953 /* If this is a call instruction, forget anything stored in a
1954 call clobbered register, or, if this is not a const call, in
1958 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1959 if (call_used_regs[i]
1960 || (REG_VALUES (i) && REG_VALUES (i)->elt
1961 && HARD_REGNO_CALL_PART_CLOBBERED (i,
1962 GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1963 cselib_invalidate_regno (i, reg_raw_mode[i]);
1965 /* Since it is not clear how cselib is going to be used, be
1966 conservative here and treat looping pure or const functions
1967 as if they were regular functions. */
1968 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1969 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1970 cselib_invalidate_mem (callmem);
1973 cselib_record_sets (insn);
1976 /* Clobber any registers which appear in REG_INC notes. We
1977 could keep track of the changes to their values, but it is
1978 unlikely to help. */
1979 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1980 if (REG_NOTE_KIND (x) == REG_INC)
1981 cselib_invalidate_rtx (XEXP (x, 0));
1984 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1985 after we have processed the insn. */
1987 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
1988 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
1989 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
1991 cselib_current_insn = 0;
1993 if (n_useless_values > MAX_USELESS_VALUES
1994 /* remove_useless_values is linear in the hash table size. Avoid
1995 quadratic behavior for very large hashtables with very few
1996 useless elements. */
1997 && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
1998 remove_useless_values ();
2001 /* Initialize cselib for one pass. The caller must also call
2002 init_alias_analysis. */
2005 cselib_init (bool record_memory)
2007 elt_list_pool = create_alloc_pool ("elt_list",
2008 sizeof (struct elt_list), 10);
2009 elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
2010 sizeof (struct elt_loc_list), 10);
2011 cselib_val_pool = create_alloc_pool ("cselib_val_list",
2012 sizeof (cselib_val), 10);
2013 value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2014 cselib_record_memory = record_memory;
2016 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2017 see canon_true_dependence. This is only created once. */
2019 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2021 cselib_nregs = max_reg_num ();
2023 /* We preserve reg_values to allow expensive clearing of the whole thing.
2024 Reallocate it however if it happens to be too large. */
2025 if (!reg_values || reg_values_size < cselib_nregs
2026 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2030 /* Some space for newly emit instructions so we don't end up
2031 reallocating in between passes. */
2032 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2033 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2035 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2037 cselib_hash_table = htab_create (31, get_value_hash,
2038 entry_and_rtx_equal_p, NULL);
2041 /* Called when the current user is done with cselib. */
2044 cselib_finish (void)
2046 cselib_discard_hook = NULL;
2047 free_alloc_pool (elt_list_pool);
2048 free_alloc_pool (elt_loc_list_pool);
2049 free_alloc_pool (cselib_val_pool);
2050 free_alloc_pool (value_pool);
2051 cselib_clear_table ();
2052 htab_delete (cselib_hash_table);
2055 cselib_hash_table = 0;
2056 n_useless_values = 0;
2057 next_unknown_value = 0;
2060 /* Dump the cselib_val *X to FILE *info. */
2063 dump_cselib_val (void **x, void *info)
2065 cselib_val *v = (cselib_val *)*x;
2066 FILE *out = (FILE *)info;
2067 bool need_lf = true;
2069 print_inline_rtx (out, v->val_rtx, 0);
2073 struct elt_loc_list *l = v->locs;
2079 fputs (" locs:", out);
2082 fprintf (out, "\n from insn %i ",
2083 INSN_UID (l->setting_insn));
2084 print_inline_rtx (out, l->loc, 4);
2086 while ((l = l->next));
2091 fputs (" no locs", out);
2097 struct elt_list *e = v->addr_list;
2103 fputs (" addr list:", out);
2107 print_inline_rtx (out, e->elt->val_rtx, 2);
2109 while ((e = e->next));
2114 fputs (" no addrs", out);
2118 if (v->next_containing_mem == &dummy_val)
2119 fputs (" last mem\n", out);
2120 else if (v->next_containing_mem)
2122 fputs (" next mem ", out);
2123 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2132 /* Dump to OUT everything in the CSELIB table. */
2135 dump_cselib_table (FILE *out)
2137 fprintf (out, "cselib hash table:\n");
2138 htab_traverse (cselib_hash_table, dump_cselib_val, out);
2139 if (first_containing_mem != &dummy_val)
2141 fputs ("first mem ", out);
2142 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2145 fprintf (out, "last unknown value %i\n", next_unknown_value);
2148 #include "gt-cselib.h"