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 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
666 For registers and memory locations, we look up their cselib_val structure
667 and return its VALUE element.
668 Possible reasons for return 0 are: the object is volatile, or we couldn't
669 find a register or memory location in the table and CREATE is zero. If
670 CREATE is nonzero, table elts are created for regs and mem.
671 N.B. this hash function returns the same hash value for RTXes that
672 differ only in the order of operands, thus it is suitable for comparisons
673 that take commutativity into account.
674 If we wanted to also support associative rules, we'd have to use a different
675 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
676 We used to have a MODE argument for hashing for CONST_INTs, but that
677 didn't make sense, since it caused spurious hash differences between
678 (set (reg:SI 1) (const_int))
679 (plus:SI (reg:SI 2) (reg:SI 1))
681 (plus:SI (reg:SI 2) (const_int))
682 If the mode is important in any context, it must be checked specifically
683 in a comparison anyway, since relying on hash differences is unsafe. */
686 cselib_hash_rtx (rtx x, int create)
692 unsigned int hash = 0;
695 hash += (unsigned) code + (unsigned) GET_MODE (x);
701 e = cselib_lookup (x, GET_MODE (x), create);
708 hash += ((unsigned) DEBUG_EXPR << 7) + DEBUG_TEMP_UID (XTREE (x, 0));
709 return hash ? hash : (unsigned int) DEBUG_EXPR;
712 hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
713 return hash ? hash : (unsigned int) CONST_INT;
716 /* This is like the general case, except that it only counts
717 the integers representing the constant. */
718 hash += (unsigned) code + (unsigned) GET_MODE (x);
719 if (GET_MODE (x) != VOIDmode)
720 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
722 hash += ((unsigned) CONST_DOUBLE_LOW (x)
723 + (unsigned) CONST_DOUBLE_HIGH (x));
724 return hash ? hash : (unsigned int) CONST_DOUBLE;
727 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
728 hash += fixed_hash (CONST_FIXED_VALUE (x));
729 return hash ? hash : (unsigned int) CONST_FIXED;
736 units = CONST_VECTOR_NUNITS (x);
738 for (i = 0; i < units; ++i)
740 elt = CONST_VECTOR_ELT (x, i);
741 hash += cselib_hash_rtx (elt, 0);
747 /* Assume there is only one rtx object for any given label. */
749 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
750 differences and differences between each stage's debugging dumps. */
751 hash += (((unsigned int) LABEL_REF << 7)
752 + CODE_LABEL_NUMBER (XEXP (x, 0)));
753 return hash ? hash : (unsigned int) LABEL_REF;
757 /* Don't hash on the symbol's address to avoid bootstrap differences.
758 Different hash values may cause expressions to be recorded in
759 different orders and thus different registers to be used in the
760 final assembler. This also avoids differences in the dump files
761 between various stages. */
763 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
766 h += (h << 7) + *p++; /* ??? revisit */
768 hash += ((unsigned int) SYMBOL_REF << 7) + h;
769 return hash ? hash : (unsigned int) SYMBOL_REF;
781 case UNSPEC_VOLATILE:
785 if (MEM_VOLATILE_P (x))
794 i = GET_RTX_LENGTH (code) - 1;
795 fmt = GET_RTX_FORMAT (code);
802 rtx tem = XEXP (x, i);
803 unsigned int tem_hash = cselib_hash_rtx (tem, create);
812 for (j = 0; j < XVECLEN (x, i); j++)
814 unsigned int tem_hash
815 = cselib_hash_rtx (XVECEXP (x, i, j), create);
826 const unsigned char *p = (const unsigned char *) XSTR (x, i);
848 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
851 /* Create a new value structure for VALUE and initialize it. The mode of the
854 static inline cselib_val *
855 new_cselib_val (unsigned int value, enum machine_mode mode, rtx x)
857 cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
862 /* We use an alloc pool to allocate this RTL construct because it
863 accounts for about 8% of the overall memory usage. We know
864 precisely when we can have VALUE RTXen (when cselib is active)
865 so we don't need to put them in garbage collected memory.
866 ??? Why should a VALUE be an RTX in the first place? */
867 e->val_rtx = (rtx) pool_alloc (value_pool);
868 memset (e->val_rtx, 0, RTX_HDR_SIZE);
869 PUT_CODE (e->val_rtx, VALUE);
870 PUT_MODE (e->val_rtx, mode);
871 CSELIB_VAL_PTR (e->val_rtx) = e;
874 e->next_containing_mem = 0;
876 if (dump_file && (dump_flags & TDF_DETAILS))
878 fprintf (dump_file, "cselib value %u ", value);
879 if (flag_dump_noaddr || flag_dump_unnumbered)
880 fputs ("# ", dump_file);
882 fprintf (dump_file, "%p ", (void*)e);
883 print_rtl_single (dump_file, x);
884 fputc ('\n', dump_file);
890 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
891 contains the data at this address. X is a MEM that represents the
892 value. Update the two value structures to represent this situation. */
895 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
897 struct elt_loc_list *l;
899 /* Avoid duplicates. */
900 for (l = mem_elt->locs; l; l = l->next)
902 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
905 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
907 = new_elt_loc_list (mem_elt->locs,
908 replace_equiv_address_nv (x, addr_elt->val_rtx));
909 if (mem_elt->next_containing_mem == NULL)
911 mem_elt->next_containing_mem = first_containing_mem;
912 first_containing_mem = mem_elt;
916 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
917 If CREATE, make a new one if we haven't seen it before. */
920 cselib_lookup_mem (rtx x, int create)
922 enum machine_mode mode = GET_MODE (x);
928 if (MEM_VOLATILE_P (x) || mode == BLKmode
929 || !cselib_record_memory
930 || (FLOAT_MODE_P (mode) && flag_float_store))
933 /* Look up the value for the address. */
934 addr = cselib_lookup (XEXP (x, 0), mode, create);
938 /* Find a value that describes a value of our mode at that address. */
939 for (l = addr->addr_list; l; l = l->next)
940 if (GET_MODE (l->elt->val_rtx) == mode)
946 mem_elt = new_cselib_val (++next_unknown_value, mode, x);
947 add_mem_for_addr (addr, mem_elt, x);
948 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
949 mem_elt->value, INSERT);
954 /* Search thru the possible substitutions in P. We prefer a non reg
955 substitution because this allows us to expand the tree further. If
956 we find, just a reg, take the lowest regno. There may be several
957 non-reg results, we just take the first one because they will all
958 expand to the same place. */
961 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
964 rtx reg_result = NULL;
965 unsigned int regno = UINT_MAX;
966 struct elt_loc_list *p_in = p;
968 for (; p; p = p -> next)
970 /* Avoid infinite recursion trying to expand a reg into a
973 && (REGNO (p->loc) < regno)
974 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
977 regno = REGNO (p->loc);
979 /* Avoid infinite recursion and do not try to expand the
981 else if (GET_CODE (p->loc) == VALUE
982 && CSELIB_VAL_PTR (p->loc)->locs == p_in)
984 else if (!REG_P (p->loc))
987 if (dump_file && (dump_flags & TDF_DETAILS))
989 print_inline_rtx (dump_file, p->loc, 0);
990 fprintf (dump_file, "\n");
992 if (GET_CODE (p->loc) == LO_SUM
993 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
995 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
996 && XEXP (note, 0) == XEXP (p->loc, 1))
997 return XEXP (p->loc, 1);
998 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1005 if (regno != UINT_MAX)
1008 if (dump_file && (dump_flags & TDF_DETAILS))
1009 fprintf (dump_file, "r%d\n", regno);
1011 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1016 if (dump_file && (dump_flags & TDF_DETAILS))
1020 print_inline_rtx (dump_file, reg_result, 0);
1021 fprintf (dump_file, "\n");
1024 fprintf (dump_file, "NULL\n");
1030 /* Forward substitute and expand an expression out to its roots.
1031 This is the opposite of common subexpression. Because local value
1032 numbering is such a weak optimization, the expanded expression is
1033 pretty much unique (not from a pointer equals point of view but
1034 from a tree shape point of view.
1036 This function returns NULL if the expansion fails. The expansion
1037 will fail if there is no value number for one of the operands or if
1038 one of the operands has been overwritten between the current insn
1039 and the beginning of the basic block. For instance x has no
1045 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1046 It is clear on return. */
1049 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1051 struct expand_value_data evd;
1053 evd.regs_active = regs_active;
1054 evd.callback = NULL;
1055 evd.callback_arg = NULL;
1057 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1060 /* Same as cselib_expand_value_rtx, but using a callback to try to
1061 resolve some expressions. The CB function should return ORIG if it
1062 can't or does not want to deal with a certain RTX. Any other
1063 return value, including NULL, will be used as the expansion for
1064 VALUE, without any further changes. */
1067 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1068 cselib_expand_callback cb, void *data)
1070 struct expand_value_data evd;
1072 evd.regs_active = regs_active;
1074 evd.callback_arg = data;
1076 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1079 /* Internal implementation of cselib_expand_value_rtx and
1080 cselib_expand_value_rtx_cb. */
1083 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1089 const char *format_ptr;
1090 enum machine_mode mode;
1092 code = GET_CODE (orig);
1094 /* For the context of dse, if we end up expand into a huge tree, we
1095 will not have a useful address, so we might as well just give up
1104 struct elt_list *l = REG_VALUES (REGNO (orig));
1106 if (l && l->elt == NULL)
1108 for (; l; l = l->next)
1109 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1112 int regno = REGNO (orig);
1114 /* The only thing that we are not willing to do (this
1115 is requirement of dse and if others potential uses
1116 need this function we should add a parm to control
1117 it) is that we will not substitute the
1118 STACK_POINTER_REGNUM, FRAME_POINTER or the
1121 These expansions confuses the code that notices that
1122 stores into the frame go dead at the end of the
1123 function and that the frame is not effected by calls
1124 to subroutines. If you allow the
1125 STACK_POINTER_REGNUM substitution, then dse will
1126 think that parameter pushing also goes dead which is
1127 wrong. If you allow the FRAME_POINTER or the
1128 HARD_FRAME_POINTER then you lose the opportunity to
1129 make the frame assumptions. */
1130 if (regno == STACK_POINTER_REGNUM
1131 || regno == FRAME_POINTER_REGNUM
1132 || regno == HARD_FRAME_POINTER_REGNUM)
1135 bitmap_set_bit (evd->regs_active, regno);
1137 if (dump_file && (dump_flags & TDF_DETAILS))
1138 fprintf (dump_file, "expanding: r%d into: ", regno);
1140 result = expand_loc (l->elt->locs, evd, max_depth);
1141 bitmap_clear_bit (evd->regs_active, regno);
1158 /* SCRATCH must be shared because they represent distinct values. */
1161 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1166 if (shared_const_p (orig))
1176 subreg = evd->callback (orig, evd->regs_active, max_depth,
1182 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1186 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1187 GET_MODE (SUBREG_REG (orig)),
1188 SUBREG_BYTE (orig));
1190 || (GET_CODE (scopy) == SUBREG
1191 && !REG_P (SUBREG_REG (scopy))
1192 && !MEM_P (SUBREG_REG (scopy))))
1202 if (dump_file && (dump_flags & TDF_DETAILS))
1204 fputs ("\nexpanding ", dump_file);
1205 print_rtl_single (dump_file, orig);
1206 fputs (" into...", dump_file);
1211 result = evd->callback (orig, evd->regs_active, max_depth,
1218 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1224 return evd->callback (orig, evd->regs_active, max_depth,
1232 /* Copy the various flags, fields, and other information. We assume
1233 that all fields need copying, and then clear the fields that should
1234 not be copied. That is the sensible default behavior, and forces
1235 us to explicitly document why we are *not* copying a flag. */
1236 copy = shallow_copy_rtx (orig);
1238 format_ptr = GET_RTX_FORMAT (code);
1240 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1241 switch (*format_ptr++)
1244 if (XEXP (orig, i) != NULL)
1246 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1250 XEXP (copy, i) = result;
1256 if (XVEC (orig, i) != NULL)
1258 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1259 for (j = 0; j < XVECLEN (copy, i); j++)
1261 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1262 evd, max_depth - 1);
1265 XVECEXP (copy, i, j) = result;
1279 /* These are left unchanged. */
1286 mode = GET_MODE (copy);
1287 /* If an operand has been simplified into CONST_INT, which doesn't
1288 have a mode and the mode isn't derivable from whole rtx's mode,
1289 try simplify_*_operation first with mode from original's operand
1290 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1292 switch (GET_RTX_CLASS (code))
1295 if (CONST_INT_P (XEXP (copy, 0))
1296 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1298 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1299 GET_MODE (XEXP (orig, 0)));
1304 case RTX_COMM_ARITH:
1306 /* These expressions can derive operand modes from the whole rtx's mode. */
1309 case RTX_BITFIELD_OPS:
1310 if (CONST_INT_P (XEXP (copy, 0))
1311 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1313 scopy = simplify_ternary_operation (code, mode,
1314 GET_MODE (XEXP (orig, 0)),
1315 XEXP (copy, 0), XEXP (copy, 1),
1322 case RTX_COMM_COMPARE:
1323 if (CONST_INT_P (XEXP (copy, 0))
1324 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1325 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1326 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1328 scopy = simplify_relational_operation (code, mode,
1329 (GET_MODE (XEXP (orig, 0))
1331 ? GET_MODE (XEXP (orig, 0))
1332 : GET_MODE (XEXP (orig, 1)),
1342 if (scopy == NULL_RTX)
1345 = gen_rtx_CONST (GET_MODE (XEXP (orig, 0)), XEXP (copy, 0));
1346 if (dump_file && (dump_flags & TDF_DETAILS))
1347 fprintf (dump_file, " wrapping const_int result in const to preserve mode %s\n",
1348 GET_MODE_NAME (GET_MODE (XEXP (copy, 0))));
1350 scopy = simplify_rtx (copy);
1353 if (GET_MODE (copy) != GET_MODE (scopy))
1354 scopy = wrap_constant (GET_MODE (copy), scopy);
1360 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1361 with VALUE expressions. This way, it becomes independent of changes
1362 to registers and memory.
1363 X isn't actually modified; if modifications are needed, new rtl is
1364 allocated. However, the return value can share rtl with X. */
1367 cselib_subst_to_values (rtx x)
1369 enum rtx_code code = GET_CODE (x);
1370 const char *fmt = GET_RTX_FORMAT (code);
1379 l = REG_VALUES (REGNO (x));
1380 if (l && l->elt == NULL)
1382 for (; l; l = l->next)
1383 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1384 return l->elt->val_rtx;
1389 e = cselib_lookup_mem (x, 0);
1392 /* This happens for autoincrements. Assign a value that doesn't
1394 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1410 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1417 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1421 rtx t = cselib_subst_to_values (XEXP (x, i));
1423 if (t != XEXP (x, i) && x == copy)
1424 copy = shallow_copy_rtx (x);
1428 else if (fmt[i] == 'E')
1432 for (j = 0; j < XVECLEN (x, i); j++)
1434 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1436 if (t != XVECEXP (x, i, j) && XVEC (x, i) == XVEC (copy, i))
1439 copy = shallow_copy_rtx (x);
1441 XVEC (copy, i) = rtvec_alloc (XVECLEN (x, i));
1442 for (k = 0; k < j; k++)
1443 XVECEXP (copy, i, k) = XVECEXP (x, i, k);
1446 XVECEXP (copy, i, j) = t;
1454 /* Log a lookup of X to the cselib table along with the result RET. */
1457 cselib_log_lookup (rtx x, cselib_val *ret)
1459 if (dump_file && (dump_flags & TDF_DETAILS))
1461 fputs ("cselib lookup ", dump_file);
1462 print_inline_rtx (dump_file, x, 2);
1463 fprintf (dump_file, " => %u\n", ret ? ret->value : 0);
1469 /* Look up the rtl expression X in our tables and return the value it has.
1470 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1471 we create a new one if possible, using mode MODE if X doesn't have a mode
1472 (i.e. because it's a constant). */
1475 cselib_lookup (rtx x, enum machine_mode mode, int create)
1479 unsigned int hashval;
1481 if (GET_MODE (x) != VOIDmode)
1482 mode = GET_MODE (x);
1484 if (GET_CODE (x) == VALUE)
1485 return CSELIB_VAL_PTR (x);
1490 unsigned int i = REGNO (x);
1493 if (l && l->elt == NULL)
1495 for (; l; l = l->next)
1496 if (mode == GET_MODE (l->elt->val_rtx))
1497 return cselib_log_lookup (x, l->elt);
1500 return cselib_log_lookup (x, 0);
1502 if (i < FIRST_PSEUDO_REGISTER)
1504 unsigned int n = hard_regno_nregs[i][mode];
1506 if (n > max_value_regs)
1510 e = new_cselib_val (++next_unknown_value, GET_MODE (x), x);
1511 e->locs = new_elt_loc_list (e->locs, x);
1512 if (REG_VALUES (i) == 0)
1514 /* Maintain the invariant that the first entry of
1515 REG_VALUES, if present, must be the value used to set the
1516 register, or NULL. */
1517 used_regs[n_used_regs++] = i;
1518 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1520 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1521 slot = htab_find_slot_with_hash (cselib_hash_table, x, e->value, INSERT);
1523 return cselib_log_lookup (x, e);
1527 return cselib_log_lookup (x, cselib_lookup_mem (x, create));
1529 hashval = cselib_hash_rtx (x, create);
1530 /* Can't even create if hashing is not possible. */
1532 return cselib_log_lookup (x, 0);
1534 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1535 hashval, create ? INSERT : NO_INSERT);
1537 return cselib_log_lookup (x, 0);
1539 e = (cselib_val *) *slot;
1541 return cselib_log_lookup (x, e);
1543 e = new_cselib_val (hashval, mode, x);
1545 /* We have to fill the slot before calling cselib_subst_to_values:
1546 the hash table is inconsistent until we do so, and
1547 cselib_subst_to_values will need to do lookups. */
1549 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1550 return cselib_log_lookup (x, e);
1553 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1554 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1555 is used to determine how many hard registers are being changed. If MODE
1556 is VOIDmode, then only REGNO is being changed; this is used when
1557 invalidating call clobbered registers across a call. */
1560 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1562 unsigned int endregno;
1565 /* If we see pseudos after reload, something is _wrong_. */
1566 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1567 || reg_renumber[regno] < 0);
1569 /* Determine the range of registers that must be invalidated. For
1570 pseudos, only REGNO is affected. For hard regs, we must take MODE
1571 into account, and we must also invalidate lower register numbers
1572 if they contain values that overlap REGNO. */
1573 if (regno < FIRST_PSEUDO_REGISTER)
1575 gcc_assert (mode != VOIDmode);
1577 if (regno < max_value_regs)
1580 i = regno - max_value_regs;
1582 endregno = end_hard_regno (mode, regno);
1587 endregno = regno + 1;
1590 for (; i < endregno; i++)
1592 struct elt_list **l = ®_VALUES (i);
1594 /* Go through all known values for this reg; if it overlaps the range
1595 we're invalidating, remove the value. */
1598 cselib_val *v = (*l)->elt;
1599 struct elt_loc_list **p;
1600 unsigned int this_last = i;
1602 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1603 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1605 if (this_last < regno || v == NULL)
1611 /* We have an overlap. */
1612 if (*l == REG_VALUES (i))
1614 /* Maintain the invariant that the first entry of
1615 REG_VALUES, if present, must be the value used to set
1616 the register, or NULL. This is also nice because
1617 then we won't push the same regno onto user_regs
1623 unchain_one_elt_list (l);
1625 /* Now, we clear the mapping from value to reg. It must exist, so
1626 this code will crash intentionally if it doesn't. */
1627 for (p = &v->locs; ; p = &(*p)->next)
1631 if (REG_P (x) && REGNO (x) == i)
1633 unchain_one_elt_loc_list (p);
1637 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1643 /* Return 1 if X has a value that can vary even between two
1644 executions of the program. 0 means X can be compared reliably
1645 against certain constants or near-constants. */
1648 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1650 /* We actually don't need to verify very hard. This is because
1651 if X has actually changed, we invalidate the memory anyway,
1652 so assume that all common memory addresses are
1657 /* Invalidate any locations in the table which are changed because of a
1658 store to MEM_RTX. If this is called because of a non-const call
1659 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1662 cselib_invalidate_mem (rtx mem_rtx)
1664 cselib_val **vp, *v, *next;
1668 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1669 mem_rtx = canon_rtx (mem_rtx);
1671 vp = &first_containing_mem;
1672 for (v = *vp; v != &dummy_val; v = next)
1674 bool has_mem = false;
1675 struct elt_loc_list **p = &v->locs;
1676 int had_locs = v->locs != 0;
1682 struct elt_list **mem_chain;
1684 /* MEMs may occur in locations only at the top level; below
1685 that every MEM or REG is substituted by its VALUE. */
1691 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1692 && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1693 x, NULL_RTX, cselib_rtx_varies_p))
1701 /* This one overlaps. */
1702 /* We must have a mapping from this MEM's address to the
1703 value (E). Remove that, too. */
1704 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1705 mem_chain = &addr->addr_list;
1708 if ((*mem_chain)->elt == v)
1710 unchain_one_elt_list (mem_chain);
1714 mem_chain = &(*mem_chain)->next;
1717 unchain_one_elt_loc_list (p);
1720 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1723 next = v->next_containing_mem;
1727 vp = &(*vp)->next_containing_mem;
1730 v->next_containing_mem = NULL;
1735 /* Invalidate DEST, which is being assigned to or clobbered. */
1738 cselib_invalidate_rtx (rtx dest)
1740 while (GET_CODE (dest) == SUBREG
1741 || GET_CODE (dest) == ZERO_EXTRACT
1742 || GET_CODE (dest) == STRICT_LOW_PART)
1743 dest = XEXP (dest, 0);
1746 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1747 else if (MEM_P (dest))
1748 cselib_invalidate_mem (dest);
1750 /* Some machines don't define AUTO_INC_DEC, but they still use push
1751 instructions. We need to catch that case here in order to
1752 invalidate the stack pointer correctly. Note that invalidating
1753 the stack pointer is different from invalidating DEST. */
1754 if (push_operand (dest, GET_MODE (dest)))
1755 cselib_invalidate_rtx (stack_pointer_rtx);
1758 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1761 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1762 void *data ATTRIBUTE_UNUSED)
1764 cselib_invalidate_rtx (dest);
1767 /* Record the result of a SET instruction. DEST is being set; the source
1768 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1769 describes its address. */
1772 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1774 int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1776 if (src_elt == 0 || side_effects_p (dest))
1781 if (dreg < FIRST_PSEUDO_REGISTER)
1783 unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1785 if (n > max_value_regs)
1789 if (REG_VALUES (dreg) == 0)
1791 used_regs[n_used_regs++] = dreg;
1792 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1796 /* The register should have been invalidated. */
1797 gcc_assert (REG_VALUES (dreg)->elt == 0);
1798 REG_VALUES (dreg)->elt = src_elt;
1801 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1803 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1805 else if (MEM_P (dest) && dest_addr_elt != 0
1806 && cselib_record_memory)
1808 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1810 add_mem_for_addr (dest_addr_elt, src_elt, dest);
1814 /* There is no good way to determine how many elements there can be
1815 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1816 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1818 /* Record the effects of any sets in INSN. */
1820 cselib_record_sets (rtx insn)
1824 struct cselib_set sets[MAX_SETS];
1825 rtx body = PATTERN (insn);
1828 body = PATTERN (insn);
1829 if (GET_CODE (body) == COND_EXEC)
1831 cond = COND_EXEC_TEST (body);
1832 body = COND_EXEC_CODE (body);
1835 /* Find all sets. */
1836 if (GET_CODE (body) == SET)
1838 sets[0].src = SET_SRC (body);
1839 sets[0].dest = SET_DEST (body);
1842 else if (GET_CODE (body) == PARALLEL)
1844 /* Look through the PARALLEL and record the values being
1845 set, if possible. Also handle any CLOBBERs. */
1846 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1848 rtx x = XVECEXP (body, 0, i);
1850 if (GET_CODE (x) == SET)
1852 sets[n_sets].src = SET_SRC (x);
1853 sets[n_sets].dest = SET_DEST (x);
1860 && MEM_P (sets[0].src)
1861 && !cselib_record_memory
1862 && MEM_READONLY_P (sets[0].src))
1864 rtx note = find_reg_equal_equiv_note (insn);
1866 if (note && CONSTANT_P (XEXP (note, 0)))
1867 sets[0].src = XEXP (note, 0);
1870 /* Look up the values that are read. Do this before invalidating the
1871 locations that are written. */
1872 for (i = 0; i < n_sets; i++)
1874 rtx dest = sets[i].dest;
1876 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1877 the low part after invalidating any knowledge about larger modes. */
1878 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1879 sets[i].dest = dest = XEXP (dest, 0);
1881 /* We don't know how to record anything but REG or MEM. */
1883 || (MEM_P (dest) && cselib_record_memory))
1885 rtx src = sets[i].src;
1887 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1888 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1890 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0), Pmode, 1);
1892 sets[i].dest_addr_elt = 0;
1896 if (cselib_record_sets_hook)
1897 cselib_record_sets_hook (insn, sets, n_sets);
1899 /* Invalidate all locations written by this insn. Note that the elts we
1900 looked up in the previous loop aren't affected, just some of their
1901 locations may go away. */
1902 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1904 /* If this is an asm, look for duplicate sets. This can happen when the
1905 user uses the same value as an output multiple times. This is valid
1906 if the outputs are not actually used thereafter. Treat this case as
1907 if the value isn't actually set. We do this by smashing the destination
1908 to pc_rtx, so that we won't record the value later. */
1909 if (n_sets >= 2 && asm_noperands (body) >= 0)
1911 for (i = 0; i < n_sets; i++)
1913 rtx dest = sets[i].dest;
1914 if (REG_P (dest) || MEM_P (dest))
1917 for (j = i + 1; j < n_sets; j++)
1918 if (rtx_equal_p (dest, sets[j].dest))
1920 sets[i].dest = pc_rtx;
1921 sets[j].dest = pc_rtx;
1927 /* Now enter the equivalences in our tables. */
1928 for (i = 0; i < n_sets; i++)
1930 rtx dest = sets[i].dest;
1932 || (MEM_P (dest) && cselib_record_memory))
1933 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1937 /* Record the effects of INSN. */
1940 cselib_process_insn (rtx insn)
1945 cselib_current_insn = insn;
1947 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1950 && find_reg_note (insn, REG_SETJMP, NULL))
1951 || (NONJUMP_INSN_P (insn)
1952 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1953 && MEM_VOLATILE_P (PATTERN (insn))))
1955 cselib_reset_table_with_next_value (next_unknown_value);
1959 if (! INSN_P (insn))
1961 cselib_current_insn = 0;
1965 /* If this is a call instruction, forget anything stored in a
1966 call clobbered register, or, if this is not a const call, in
1970 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1971 if (call_used_regs[i]
1972 || (REG_VALUES (i) && REG_VALUES (i)->elt
1973 && HARD_REGNO_CALL_PART_CLOBBERED (i,
1974 GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1975 cselib_invalidate_regno (i, reg_raw_mode[i]);
1977 /* Since it is not clear how cselib is going to be used, be
1978 conservative here and treat looping pure or const functions
1979 as if they were regular functions. */
1980 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1981 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1982 cselib_invalidate_mem (callmem);
1985 cselib_record_sets (insn);
1988 /* Clobber any registers which appear in REG_INC notes. We
1989 could keep track of the changes to their values, but it is
1990 unlikely to help. */
1991 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1992 if (REG_NOTE_KIND (x) == REG_INC)
1993 cselib_invalidate_rtx (XEXP (x, 0));
1996 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1997 after we have processed the insn. */
1999 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2000 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
2001 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
2003 cselib_current_insn = 0;
2005 if (n_useless_values > MAX_USELESS_VALUES
2006 /* remove_useless_values is linear in the hash table size. Avoid
2007 quadratic behavior for very large hashtables with very few
2008 useless elements. */
2009 && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
2010 remove_useless_values ();
2013 /* Initialize cselib for one pass. The caller must also call
2014 init_alias_analysis. */
2017 cselib_init (bool record_memory)
2019 elt_list_pool = create_alloc_pool ("elt_list",
2020 sizeof (struct elt_list), 10);
2021 elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
2022 sizeof (struct elt_loc_list), 10);
2023 cselib_val_pool = create_alloc_pool ("cselib_val_list",
2024 sizeof (cselib_val), 10);
2025 value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2026 cselib_record_memory = record_memory;
2028 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2029 see canon_true_dependence. This is only created once. */
2031 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2033 cselib_nregs = max_reg_num ();
2035 /* We preserve reg_values to allow expensive clearing of the whole thing.
2036 Reallocate it however if it happens to be too large. */
2037 if (!reg_values || reg_values_size < cselib_nregs
2038 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2042 /* Some space for newly emit instructions so we don't end up
2043 reallocating in between passes. */
2044 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2045 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2047 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2049 cselib_hash_table = htab_create (31, get_value_hash,
2050 entry_and_rtx_equal_p, NULL);
2053 /* Called when the current user is done with cselib. */
2056 cselib_finish (void)
2058 cselib_discard_hook = NULL;
2059 free_alloc_pool (elt_list_pool);
2060 free_alloc_pool (elt_loc_list_pool);
2061 free_alloc_pool (cselib_val_pool);
2062 free_alloc_pool (value_pool);
2063 cselib_clear_table ();
2064 htab_delete (cselib_hash_table);
2067 cselib_hash_table = 0;
2068 n_useless_values = 0;
2069 next_unknown_value = 0;
2072 /* Dump the cselib_val *X to FILE *info. */
2075 dump_cselib_val (void **x, void *info)
2077 cselib_val *v = (cselib_val *)*x;
2078 FILE *out = (FILE *)info;
2079 bool need_lf = true;
2081 print_inline_rtx (out, v->val_rtx, 0);
2085 struct elt_loc_list *l = v->locs;
2091 fputs (" locs:", out);
2094 fprintf (out, "\n from insn %i ",
2095 INSN_UID (l->setting_insn));
2096 print_inline_rtx (out, l->loc, 4);
2098 while ((l = l->next));
2103 fputs (" no locs", out);
2109 struct elt_list *e = v->addr_list;
2115 fputs (" addr list:", out);
2119 print_inline_rtx (out, e->elt->val_rtx, 2);
2121 while ((e = e->next));
2126 fputs (" no addrs", out);
2130 if (v->next_containing_mem == &dummy_val)
2131 fputs (" last mem\n", out);
2132 else if (v->next_containing_mem)
2134 fputs (" next mem ", out);
2135 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2144 /* Dump to OUT everything in the CSELIB table. */
2147 dump_cselib_table (FILE *out)
2149 fprintf (out, "cselib hash table:\n");
2150 htab_traverse (cselib_hash_table, dump_cselib_val, out);
2151 if (first_containing_mem != &dummy_val)
2153 fputs ("first mem ", out);
2154 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2157 fprintf (out, "last unknown value %i\n", next_unknown_value);
2160 #include "gt-cselib.h"