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))
592 return XEXP (x, 0) == XEXP (y, 0);
599 fmt = GET_RTX_FORMAT (code);
601 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
608 if (XWINT (x, i) != XWINT (y, i))
614 if (XINT (x, i) != XINT (y, i))
620 /* Two vectors must have the same length. */
621 if (XVECLEN (x, i) != XVECLEN (y, i))
624 /* And the corresponding elements must match. */
625 for (j = 0; j < XVECLEN (x, i); j++)
626 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
633 && targetm.commutative_p (x, UNKNOWN)
634 && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
635 && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
637 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
643 if (strcmp (XSTR (x, i), XSTR (y, i)))
648 /* These are just backpointers, so they don't matter. */
655 /* It is believed that rtx's at this level will never
656 contain anything but integers and other rtx's,
657 except for within LABEL_REFs and SYMBOL_REFs. */
665 /* We need to pass down the mode of constants through the hash table
666 functions. For that purpose, wrap them in a CONST of the appropriate
669 wrap_constant (enum machine_mode mode, rtx x)
671 if (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
672 && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
674 gcc_assert (mode != VOIDmode);
675 return gen_rtx_CONST (mode, x);
678 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
679 For registers and memory locations, we look up their cselib_val structure
680 and return its VALUE element.
681 Possible reasons for return 0 are: the object is volatile, or we couldn't
682 find a register or memory location in the table and CREATE is zero. If
683 CREATE is nonzero, table elts are created for regs and mem.
684 N.B. this hash function returns the same hash value for RTXes that
685 differ only in the order of operands, thus it is suitable for comparisons
686 that take commutativity into account.
687 If we wanted to also support associative rules, we'd have to use a different
688 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
689 We used to have a MODE argument for hashing for CONST_INTs, but that
690 didn't make sense, since it caused spurious hash differences between
691 (set (reg:SI 1) (const_int))
692 (plus:SI (reg:SI 2) (reg:SI 1))
694 (plus:SI (reg:SI 2) (const_int))
695 If the mode is important in any context, it must be checked specifically
696 in a comparison anyway, since relying on hash differences is unsafe. */
699 cselib_hash_rtx (rtx x, int create)
705 unsigned int hash = 0;
708 hash += (unsigned) code + (unsigned) GET_MODE (x);
714 e = cselib_lookup (x, GET_MODE (x), create);
721 hash += ((unsigned) DEBUG_EXPR << 7)
722 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
723 return hash ? hash : (unsigned int) DEBUG_EXPR;
726 hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
727 return hash ? hash : (unsigned int) CONST_INT;
730 /* This is like the general case, except that it only counts
731 the integers representing the constant. */
732 hash += (unsigned) code + (unsigned) GET_MODE (x);
733 if (GET_MODE (x) != VOIDmode)
734 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
736 hash += ((unsigned) CONST_DOUBLE_LOW (x)
737 + (unsigned) CONST_DOUBLE_HIGH (x));
738 return hash ? hash : (unsigned int) CONST_DOUBLE;
741 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
742 hash += fixed_hash (CONST_FIXED_VALUE (x));
743 return hash ? hash : (unsigned int) CONST_FIXED;
750 units = CONST_VECTOR_NUNITS (x);
752 for (i = 0; i < units; ++i)
754 elt = CONST_VECTOR_ELT (x, i);
755 hash += cselib_hash_rtx (elt, 0);
761 /* Assume there is only one rtx object for any given label. */
763 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
764 differences and differences between each stage's debugging dumps. */
765 hash += (((unsigned int) LABEL_REF << 7)
766 + CODE_LABEL_NUMBER (XEXP (x, 0)));
767 return hash ? hash : (unsigned int) LABEL_REF;
771 /* Don't hash on the symbol's address to avoid bootstrap differences.
772 Different hash values may cause expressions to be recorded in
773 different orders and thus different registers to be used in the
774 final assembler. This also avoids differences in the dump files
775 between various stages. */
777 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
780 h += (h << 7) + *p++; /* ??? revisit */
782 hash += ((unsigned int) SYMBOL_REF << 7) + h;
783 return hash ? hash : (unsigned int) SYMBOL_REF;
795 case UNSPEC_VOLATILE:
799 if (MEM_VOLATILE_P (x))
808 i = GET_RTX_LENGTH (code) - 1;
809 fmt = GET_RTX_FORMAT (code);
816 rtx tem = XEXP (x, i);
817 unsigned int tem_hash = cselib_hash_rtx (tem, create);
826 for (j = 0; j < XVECLEN (x, i); j++)
828 unsigned int tem_hash
829 = cselib_hash_rtx (XVECEXP (x, i, j), create);
840 const unsigned char *p = (const unsigned char *) XSTR (x, i);
862 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
865 /* Create a new value structure for VALUE and initialize it. The mode of the
868 static inline cselib_val *
869 new_cselib_val (unsigned int value, enum machine_mode mode, rtx x)
871 cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
876 /* We use an alloc pool to allocate this RTL construct because it
877 accounts for about 8% of the overall memory usage. We know
878 precisely when we can have VALUE RTXen (when cselib is active)
879 so we don't need to put them in garbage collected memory.
880 ??? Why should a VALUE be an RTX in the first place? */
881 e->val_rtx = (rtx) pool_alloc (value_pool);
882 memset (e->val_rtx, 0, RTX_HDR_SIZE);
883 PUT_CODE (e->val_rtx, VALUE);
884 PUT_MODE (e->val_rtx, mode);
885 CSELIB_VAL_PTR (e->val_rtx) = e;
888 e->next_containing_mem = 0;
890 if (dump_file && (dump_flags & TDF_DETAILS))
892 fprintf (dump_file, "cselib value %u ", value);
893 if (flag_dump_noaddr || flag_dump_unnumbered)
894 fputs ("# ", dump_file);
896 fprintf (dump_file, "%p ", (void*)e);
897 print_rtl_single (dump_file, x);
898 fputc ('\n', dump_file);
904 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
905 contains the data at this address. X is a MEM that represents the
906 value. Update the two value structures to represent this situation. */
909 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
911 struct elt_loc_list *l;
913 /* Avoid duplicates. */
914 for (l = mem_elt->locs; l; l = l->next)
916 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
919 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
921 = new_elt_loc_list (mem_elt->locs,
922 replace_equiv_address_nv (x, addr_elt->val_rtx));
923 if (mem_elt->next_containing_mem == NULL)
925 mem_elt->next_containing_mem = first_containing_mem;
926 first_containing_mem = mem_elt;
930 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
931 If CREATE, make a new one if we haven't seen it before. */
934 cselib_lookup_mem (rtx x, int create)
936 enum machine_mode mode = GET_MODE (x);
942 if (MEM_VOLATILE_P (x) || mode == BLKmode
943 || !cselib_record_memory
944 || (FLOAT_MODE_P (mode) && flag_float_store))
947 /* Look up the value for the address. */
948 addr = cselib_lookup (XEXP (x, 0), mode, create);
952 /* Find a value that describes a value of our mode at that address. */
953 for (l = addr->addr_list; l; l = l->next)
954 if (GET_MODE (l->elt->val_rtx) == mode)
960 mem_elt = new_cselib_val (++next_unknown_value, mode, x);
961 add_mem_for_addr (addr, mem_elt, x);
962 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
963 mem_elt->value, INSERT);
968 /* Search thru the possible substitutions in P. We prefer a non reg
969 substitution because this allows us to expand the tree further. If
970 we find, just a reg, take the lowest regno. There may be several
971 non-reg results, we just take the first one because they will all
972 expand to the same place. */
975 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
978 rtx reg_result = NULL;
979 unsigned int regno = UINT_MAX;
980 struct elt_loc_list *p_in = p;
982 for (; p; p = p -> next)
984 /* Avoid infinite recursion trying to expand a reg into a
987 && (REGNO (p->loc) < regno)
988 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
991 regno = REGNO (p->loc);
993 /* Avoid infinite recursion and do not try to expand the
995 else if (GET_CODE (p->loc) == VALUE
996 && CSELIB_VAL_PTR (p->loc)->locs == p_in)
998 else if (!REG_P (p->loc))
1001 if (dump_file && (dump_flags & TDF_DETAILS))
1003 print_inline_rtx (dump_file, p->loc, 0);
1004 fprintf (dump_file, "\n");
1006 if (GET_CODE (p->loc) == LO_SUM
1007 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
1009 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
1010 && XEXP (note, 0) == XEXP (p->loc, 1))
1011 return XEXP (p->loc, 1);
1012 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1019 if (regno != UINT_MAX)
1022 if (dump_file && (dump_flags & TDF_DETAILS))
1023 fprintf (dump_file, "r%d\n", regno);
1025 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1030 if (dump_file && (dump_flags & TDF_DETAILS))
1034 print_inline_rtx (dump_file, reg_result, 0);
1035 fprintf (dump_file, "\n");
1038 fprintf (dump_file, "NULL\n");
1044 /* Forward substitute and expand an expression out to its roots.
1045 This is the opposite of common subexpression. Because local value
1046 numbering is such a weak optimization, the expanded expression is
1047 pretty much unique (not from a pointer equals point of view but
1048 from a tree shape point of view.
1050 This function returns NULL if the expansion fails. The expansion
1051 will fail if there is no value number for one of the operands or if
1052 one of the operands has been overwritten between the current insn
1053 and the beginning of the basic block. For instance x has no
1059 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1060 It is clear on return. */
1063 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1065 struct expand_value_data evd;
1067 evd.regs_active = regs_active;
1068 evd.callback = NULL;
1069 evd.callback_arg = NULL;
1071 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1074 /* Same as cselib_expand_value_rtx, but using a callback to try to
1075 resolve some expressions. The CB function should return ORIG if it
1076 can't or does not want to deal with a certain RTX. Any other
1077 return value, including NULL, will be used as the expansion for
1078 VALUE, without any further changes. */
1081 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1082 cselib_expand_callback cb, void *data)
1084 struct expand_value_data evd;
1086 evd.regs_active = regs_active;
1088 evd.callback_arg = data;
1090 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1093 /* Internal implementation of cselib_expand_value_rtx and
1094 cselib_expand_value_rtx_cb. */
1097 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1103 const char *format_ptr;
1104 enum machine_mode mode;
1106 code = GET_CODE (orig);
1108 /* For the context of dse, if we end up expand into a huge tree, we
1109 will not have a useful address, so we might as well just give up
1118 struct elt_list *l = REG_VALUES (REGNO (orig));
1120 if (l && l->elt == NULL)
1122 for (; l; l = l->next)
1123 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1126 int regno = REGNO (orig);
1128 /* The only thing that we are not willing to do (this
1129 is requirement of dse and if others potential uses
1130 need this function we should add a parm to control
1131 it) is that we will not substitute the
1132 STACK_POINTER_REGNUM, FRAME_POINTER or the
1135 These expansions confuses the code that notices that
1136 stores into the frame go dead at the end of the
1137 function and that the frame is not effected by calls
1138 to subroutines. If you allow the
1139 STACK_POINTER_REGNUM substitution, then dse will
1140 think that parameter pushing also goes dead which is
1141 wrong. If you allow the FRAME_POINTER or the
1142 HARD_FRAME_POINTER then you lose the opportunity to
1143 make the frame assumptions. */
1144 if (regno == STACK_POINTER_REGNUM
1145 || regno == FRAME_POINTER_REGNUM
1146 || regno == HARD_FRAME_POINTER_REGNUM)
1149 bitmap_set_bit (evd->regs_active, regno);
1151 if (dump_file && (dump_flags & TDF_DETAILS))
1152 fprintf (dump_file, "expanding: r%d into: ", regno);
1154 result = expand_loc (l->elt->locs, evd, max_depth);
1155 bitmap_clear_bit (evd->regs_active, regno);
1172 /* SCRATCH must be shared because they represent distinct values. */
1175 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1180 if (shared_const_p (orig))
1190 subreg = evd->callback (orig, evd->regs_active, max_depth,
1196 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1200 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1201 GET_MODE (SUBREG_REG (orig)),
1202 SUBREG_BYTE (orig));
1204 || (GET_CODE (scopy) == SUBREG
1205 && !REG_P (SUBREG_REG (scopy))
1206 && !MEM_P (SUBREG_REG (scopy))))
1216 if (dump_file && (dump_flags & TDF_DETAILS))
1218 fputs ("\nexpanding ", dump_file);
1219 print_rtl_single (dump_file, orig);
1220 fputs (" into...", dump_file);
1225 result = evd->callback (orig, evd->regs_active, max_depth,
1232 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1238 return evd->callback (orig, evd->regs_active, max_depth,
1246 /* Copy the various flags, fields, and other information. We assume
1247 that all fields need copying, and then clear the fields that should
1248 not be copied. That is the sensible default behavior, and forces
1249 us to explicitly document why we are *not* copying a flag. */
1250 copy = shallow_copy_rtx (orig);
1252 format_ptr = GET_RTX_FORMAT (code);
1254 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1255 switch (*format_ptr++)
1258 if (XEXP (orig, i) != NULL)
1260 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1264 XEXP (copy, i) = result;
1270 if (XVEC (orig, i) != NULL)
1272 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1273 for (j = 0; j < XVECLEN (copy, i); j++)
1275 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1276 evd, max_depth - 1);
1279 XVECEXP (copy, i, j) = result;
1293 /* These are left unchanged. */
1300 mode = GET_MODE (copy);
1301 /* If an operand has been simplified into CONST_INT, which doesn't
1302 have a mode and the mode isn't derivable from whole rtx's mode,
1303 try simplify_*_operation first with mode from original's operand
1304 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1306 switch (GET_RTX_CLASS (code))
1309 if (CONST_INT_P (XEXP (copy, 0))
1310 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1312 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1313 GET_MODE (XEXP (orig, 0)));
1318 case RTX_COMM_ARITH:
1320 /* These expressions can derive operand modes from the whole rtx's mode. */
1323 case RTX_BITFIELD_OPS:
1324 if (CONST_INT_P (XEXP (copy, 0))
1325 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1327 scopy = simplify_ternary_operation (code, mode,
1328 GET_MODE (XEXP (orig, 0)),
1329 XEXP (copy, 0), XEXP (copy, 1),
1336 case RTX_COMM_COMPARE:
1337 if (CONST_INT_P (XEXP (copy, 0))
1338 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1339 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1340 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1342 scopy = simplify_relational_operation (code, mode,
1343 (GET_MODE (XEXP (orig, 0))
1345 ? GET_MODE (XEXP (orig, 0))
1346 : GET_MODE (XEXP (orig, 1)),
1356 scopy = simplify_rtx (copy);
1362 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1363 with VALUE expressions. This way, it becomes independent of changes
1364 to registers and memory.
1365 X isn't actually modified; if modifications are needed, new rtl is
1366 allocated. However, the return value can share rtl with X. */
1369 cselib_subst_to_values (rtx x)
1371 enum rtx_code code = GET_CODE (x);
1372 const char *fmt = GET_RTX_FORMAT (code);
1381 l = REG_VALUES (REGNO (x));
1382 if (l && l->elt == NULL)
1384 for (; l; l = l->next)
1385 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1386 return l->elt->val_rtx;
1391 e = cselib_lookup_mem (x, 0);
1394 /* This happens for autoincrements. Assign a value that doesn't
1396 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1412 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1419 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1423 rtx t = cselib_subst_to_values (XEXP (x, i));
1425 if (t != XEXP (x, i) && x == copy)
1426 copy = shallow_copy_rtx (x);
1430 else if (fmt[i] == 'E')
1434 for (j = 0; j < XVECLEN (x, i); j++)
1436 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1438 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
1441 copy = shallow_copy_rtx (x);
1443 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
1444 for (k = 0; k < j; k++)
1445 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
1448 XVECEXP (copy, i, j) = t;
1456 /* Log a lookup of X to the cselib table along with the result RET. */
1459 cselib_log_lookup (rtx x, cselib_val *ret)
1461 if (dump_file && (dump_flags & TDF_DETAILS))
1463 fputs ("cselib lookup ", dump_file);
1464 print_inline_rtx (dump_file, x, 2);
1465 fprintf (dump_file, " => %u\n", ret ? ret->value : 0);
1471 /* Look up the rtl expression X in our tables and return the value it has.
1472 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1473 we create a new one if possible, using mode MODE if X doesn't have a mode
1474 (i.e. because it's a constant). */
1477 cselib_lookup (rtx x, enum machine_mode mode, int create)
1481 unsigned int hashval;
1483 if (GET_MODE (x) != VOIDmode)
1484 mode = GET_MODE (x);
1486 if (GET_CODE (x) == VALUE)
1487 return CSELIB_VAL_PTR (x);
1492 unsigned int i = REGNO (x);
1495 if (l && l->elt == NULL)
1497 for (; l; l = l->next)
1498 if (mode == GET_MODE (l->elt->val_rtx))
1499 return cselib_log_lookup (x, l->elt);
1502 return cselib_log_lookup (x, 0);
1504 if (i < FIRST_PSEUDO_REGISTER)
1506 unsigned int n = hard_regno_nregs[i][mode];
1508 if (n > max_value_regs)
1512 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1513 e->locs = new_elt_loc_list (e->locs, x);
1514 if (REG_VALUES (i) == 0)
1516 /* Maintain the invariant that the first entry of
1517 REG_VALUES, if present, must be the value used to set the
1518 register, or NULL. */
1519 used_regs[n_used_regs++] = i;
1520 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1522 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1523 slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
1525 return cselib_log_lookup (x, e);
1529 return cselib_log_lookup (x, cselib_lookup_mem (x, create));
1531 hashval = cselib_hash_rtx (x, create);
1532 /* Can't even create if hashing is not possible. */
1534 return cselib_log_lookup (x, 0);
1536 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1537 hashval, create ? INSERT : NO_INSERT);
1539 return cselib_log_lookup (x, 0);
1541 e = (cselib_val *) *slot;
1543 return cselib_log_lookup (x, e);
1545 e = new_cselib_val (hashval, mode, x);
1547 /* We have to fill the slot before calling cselib_subst_to_values:
1548 the hash table is inconsistent until we do so, and
1549 cselib_subst_to_values will need to do lookups. */
1551 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1552 return cselib_log_lookup (x, e);
1555 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1556 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1557 is used to determine how many hard registers are being changed. If MODE
1558 is VOIDmode, then only REGNO is being changed; this is used when
1559 invalidating call clobbered registers across a call. */
1562 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1564 unsigned int endregno;
1567 /* If we see pseudos after reload, something is _wrong_. */
1568 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1569 || reg_renumber[regno] < 0);
1571 /* Determine the range of registers that must be invalidated. For
1572 pseudos, only REGNO is affected. For hard regs, we must take MODE
1573 into account, and we must also invalidate lower register numbers
1574 if they contain values that overlap REGNO. */
1575 if (regno < FIRST_PSEUDO_REGISTER)
1577 gcc_assert (mode != VOIDmode);
1579 if (regno < max_value_regs)
1582 i = regno - max_value_regs;
1584 endregno = end_hard_regno (mode, regno);
1589 endregno = regno + 1;
1592 for (; i < endregno; i++)
1594 struct elt_list **l = ®_VALUES (i);
1596 /* Go through all known values for this reg; if it overlaps the range
1597 we're invalidating, remove the value. */
1600 cselib_val *v = (*l)->elt;
1601 struct elt_loc_list **p;
1602 unsigned int this_last = i;
1604 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1605 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1607 if (this_last < regno || v == NULL)
1613 /* We have an overlap. */
1614 if (*l == REG_VALUES (i))
1616 /* Maintain the invariant that the first entry of
1617 REG_VALUES, if present, must be the value used to set
1618 the register, or NULL. This is also nice because
1619 then we won't push the same regno onto user_regs
1625 unchain_one_elt_list (l);
1627 /* Now, we clear the mapping from value to reg. It must exist, so
1628 this code will crash intentionally if it doesn't. */
1629 for (p = &v->locs; ; p = &(*p)->next)
1633 if (REG_P (x) && REGNO (x) == i)
1635 unchain_one_elt_loc_list (p);
1639 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1645 /* Return 1 if X has a value that can vary even between two
1646 executions of the program. 0 means X can be compared reliably
1647 against certain constants or near-constants. */
1650 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1652 /* We actually don't need to verify very hard. This is because
1653 if X has actually changed, we invalidate the memory anyway,
1654 so assume that all common memory addresses are
1659 /* Invalidate any locations in the table which are changed because of a
1660 store to MEM_RTX. If this is called because of a non-const call
1661 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1664 cselib_invalidate_mem (rtx mem_rtx)
1666 cselib_val **vp, *v, *next;
1670 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1671 mem_rtx = canon_rtx (mem_rtx);
1673 vp = &first_containing_mem;
1674 for (v = *vp; v != &dummy_val; v = next)
1676 bool has_mem = false;
1677 struct elt_loc_list **p = &v->locs;
1678 int had_locs = v->locs != 0;
1684 struct elt_list **mem_chain;
1686 /* MEMs may occur in locations only at the top level; below
1687 that every MEM or REG is substituted by its VALUE. */
1693 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1694 && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1695 x, NULL_RTX, cselib_rtx_varies_p))
1703 /* This one overlaps. */
1704 /* We must have a mapping from this MEM's address to the
1705 value (E). Remove that, too. */
1706 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1707 mem_chain = &addr->addr_list;
1710 if ((*mem_chain)->elt == v)
1712 unchain_one_elt_list (mem_chain);
1716 mem_chain = &(*mem_chain)->next;
1719 unchain_one_elt_loc_list (p);
1722 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1725 next = v->next_containing_mem;
1729 vp = &(*vp)->next_containing_mem;
1732 v->next_containing_mem = NULL;
1737 /* Invalidate DEST, which is being assigned to or clobbered. */
1740 cselib_invalidate_rtx (rtx dest)
1742 while (GET_CODE (dest) == SUBREG
1743 || GET_CODE (dest) == ZERO_EXTRACT
1744 || GET_CODE (dest) == STRICT_LOW_PART)
1745 dest = XEXP (dest, 0);
1748 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1749 else if (MEM_P (dest))
1750 cselib_invalidate_mem (dest);
1752 /* Some machines don't define AUTO_INC_DEC, but they still use push
1753 instructions. We need to catch that case here in order to
1754 invalidate the stack pointer correctly. Note that invalidating
1755 the stack pointer is different from invalidating DEST. */
1756 if (push_operand (dest, GET_MODE (dest)))
1757 cselib_invalidate_rtx (stack_pointer_rtx);
1760 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1763 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1764 void *data ATTRIBUTE_UNUSED)
1766 cselib_invalidate_rtx (dest);
1769 /* Record the result of a SET instruction. DEST is being set; the source
1770 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1771 describes its address. */
1774 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1776 int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1778 if (src_elt == 0 || side_effects_p (dest))
1783 if (dreg < FIRST_PSEUDO_REGISTER)
1785 unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1787 if (n > max_value_regs)
1791 if (REG_VALUES (dreg) == 0)
1793 used_regs[n_used_regs++] = dreg;
1794 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1798 /* The register should have been invalidated. */
1799 gcc_assert (REG_VALUES (dreg)->elt == 0);
1800 REG_VALUES (dreg)->elt = src_elt;
1803 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1805 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1807 else if (MEM_P (dest) && dest_addr_elt != 0
1808 && cselib_record_memory)
1810 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1812 add_mem_for_addr (dest_addr_elt, src_elt, dest);
1816 /* There is no good way to determine how many elements there can be
1817 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1818 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1820 /* Record the effects of any sets in INSN. */
1822 cselib_record_sets (rtx insn)
1826 struct cselib_set sets[MAX_SETS];
1827 rtx body = PATTERN (insn);
1830 body = PATTERN (insn);
1831 if (GET_CODE (body) == COND_EXEC)
1833 cond = COND_EXEC_TEST (body);
1834 body = COND_EXEC_CODE (body);
1837 /* Find all sets. */
1838 if (GET_CODE (body) == SET)
1840 sets[0].src = SET_SRC (body);
1841 sets[0].dest = SET_DEST (body);
1844 else if (GET_CODE (body) == PARALLEL)
1846 /* Look through the PARALLEL and record the values being
1847 set, if possible. Also handle any CLOBBERs. */
1848 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1850 rtx x = XVECEXP (body, 0, i);
1852 if (GET_CODE (x) == SET)
1854 sets[n_sets].src = SET_SRC (x);
1855 sets[n_sets].dest = SET_DEST (x);
1862 && MEM_P (sets[0].src)
1863 && !cselib_record_memory
1864 && MEM_READONLY_P (sets[0].src))
1866 rtx note = find_reg_equal_equiv_note (insn);
1868 if (note && CONSTANT_P (XEXP (note, 0)))
1869 sets[0].src = XEXP (note, 0);
1872 /* Look up the values that are read. Do this before invalidating the
1873 locations that are written. */
1874 for (i = 0; i < n_sets; i++)
1876 rtx dest = sets[i].dest;
1878 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1879 the low part after invalidating any knowledge about larger modes. */
1880 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1881 sets[i].dest = dest = XEXP (dest, 0);
1883 /* We don't know how to record anything but REG or MEM. */
1885 || (MEM_P (dest) && cselib_record_memory))
1887 rtx src = sets[i].src;
1889 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1890 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1892 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1894 sets[i].dest_addr_elt = 0;
1898 if (cselib_record_sets_hook)
1899 cselib_record_sets_hook (insn, sets, n_sets);
1901 /* Invalidate all locations written by this insn. Note that the elts we
1902 looked up in the previous loop aren't affected, just some of their
1903 locations may go away. */
1904 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1906 /* If this is an asm, look for duplicate sets. This can happen when the
1907 user uses the same value as an output multiple times. This is valid
1908 if the outputs are not actually used thereafter. Treat this case as
1909 if the value isn't actually set. We do this by smashing the destination
1910 to pc_rtx, so that we won't record the value later. */
1911 if (n_sets >= 2 && asm_noperands (body) >= 0)
1913 for (i = 0; i < n_sets; i++)
1915 rtx dest = sets[i].dest;
1916 if (REG_P (dest) || MEM_P (dest))
1919 for (j = i + 1; j < n_sets; j++)
1920 if (rtx_equal_p (dest, sets[j].dest))
1922 sets[i].dest = pc_rtx;
1923 sets[j].dest = pc_rtx;
1929 /* Now enter the equivalences in our tables. */
1930 for (i = 0; i < n_sets; i++)
1932 rtx dest = sets[i].dest;
1934 || (MEM_P (dest) && cselib_record_memory))
1935 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1939 /* Record the effects of INSN. */
1942 cselib_process_insn (rtx insn)
1947 cselib_current_insn = insn;
1949 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1952 && find_reg_note (insn, REG_SETJMP, NULL))
1953 || (NONJUMP_INSN_P (insn)
1954 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1955 && MEM_VOLATILE_P (PATTERN (insn))))
1957 cselib_reset_table_with_next_value (next_unknown_value);
1961 if (! INSN_P (insn))
1963 cselib_current_insn = 0;
1967 /* If this is a call instruction, forget anything stored in a
1968 call clobbered register, or, if this is not a const call, in
1972 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1973 if (call_used_regs[i]
1974 || (REG_VALUES (i) && REG_VALUES (i)->elt
1975 && HARD_REGNO_CALL_PART_CLOBBERED (i,
1976 GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1977 cselib_invalidate_regno (i, reg_raw_mode[i]);
1979 /* Since it is not clear how cselib is going to be used, be
1980 conservative here and treat looping pure or const functions
1981 as if they were regular functions. */
1982 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1983 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1984 cselib_invalidate_mem (callmem);
1987 cselib_record_sets (insn);
1990 /* Clobber any registers which appear in REG_INC notes. We
1991 could keep track of the changes to their values, but it is
1992 unlikely to help. */
1993 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1994 if (REG_NOTE_KIND (x) == REG_INC)
1995 cselib_invalidate_rtx (XEXP (x, 0));
1998 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1999 after we have processed the insn. */
2001 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2002 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
2003 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
2005 cselib_current_insn = 0;
2007 if (n_useless_values > MAX_USELESS_VALUES
2008 /* remove_useless_values is linear in the hash table size. Avoid
2009 quadratic behavior for very large hashtables with very few
2010 useless elements. */
2011 && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
2012 remove_useless_values ();
2015 /* Initialize cselib for one pass. The caller must also call
2016 init_alias_analysis. */
2019 cselib_init (bool record_memory)
2021 elt_list_pool = create_alloc_pool ("elt_list",
2022 sizeof (struct elt_list), 10);
2023 elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
2024 sizeof (struct elt_loc_list), 10);
2025 cselib_val_pool = create_alloc_pool ("cselib_val_list",
2026 sizeof (cselib_val), 10);
2027 value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2028 cselib_record_memory = record_memory;
2030 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2031 see canon_true_dependence. This is only created once. */
2033 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2035 cselib_nregs = max_reg_num ();
2037 /* We preserve reg_values to allow expensive clearing of the whole thing.
2038 Reallocate it however if it happens to be too large. */
2039 if (!reg_values || reg_values_size < cselib_nregs
2040 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2044 /* Some space for newly emit instructions so we don't end up
2045 reallocating in between passes. */
2046 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2047 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2049 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2051 cselib_hash_table = htab_create (31, get_value_hash,
2052 entry_and_rtx_equal_p, NULL);
2055 /* Called when the current user is done with cselib. */
2058 cselib_finish (void)
2060 cselib_discard_hook = NULL;
2061 free_alloc_pool (elt_list_pool);
2062 free_alloc_pool (elt_loc_list_pool);
2063 free_alloc_pool (cselib_val_pool);
2064 free_alloc_pool (value_pool);
2065 cselib_clear_table ();
2066 htab_delete (cselib_hash_table);
2069 cselib_hash_table = 0;
2070 n_useless_values = 0;
2071 next_unknown_value = 0;
2074 /* Dump the cselib_val *X to FILE *info. */
2077 dump_cselib_val (void **x, void *info)
2079 cselib_val *v = (cselib_val *)*x;
2080 FILE *out = (FILE *)info;
2081 bool need_lf = true;
2083 print_inline_rtx (out, v->val_rtx, 0);
2087 struct elt_loc_list *l = v->locs;
2093 fputs (" locs:", out);
2096 fprintf (out, "\n from insn %i ",
2097 INSN_UID (l->setting_insn));
2098 print_inline_rtx (out, l->loc, 4);
2100 while ((l = l->next));
2105 fputs (" no locs", out);
2111 struct elt_list *e = v->addr_list;
2117 fputs (" addr list:", out);
2121 print_inline_rtx (out, e->elt->val_rtx, 2);
2123 while ((e = e->next));
2128 fputs (" no addrs", out);
2132 if (v->next_containing_mem == &dummy_val)
2133 fputs (" last mem\n", out);
2134 else if (v->next_containing_mem)
2136 fputs (" next mem ", out);
2137 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2146 /* Dump to OUT everything in the CSELIB table. */
2149 dump_cselib_table (FILE *out)
2151 fprintf (out, "cselib hash table:\n");
2152 htab_traverse (cselib_hash_table, dump_cselib_val, out);
2153 if (first_containing_mem != &dummy_val)
2155 fputs ("first mem ", out);
2156 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2159 fprintf (out, "last unknown value %i\n", next_unknown_value);
2162 #include "gt-cselib.h"