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, 2010
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;
75 static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
77 /* There are three ways in which cselib can look up an rtx:
78 - for a REG, the reg_values table (which is indexed by regno) is used
79 - for a MEM, we recursively look up its address and then follow the
80 addr_list of that value
81 - for everything else, we compute a hash value and go through the hash
82 table. Since different rtx's can still have the same hash value,
83 this involves walking the table entries for a given value and comparing
84 the locations of the entries with the rtx we are looking up. */
86 /* A table that enables us to look up elts by their value. */
87 static htab_t cselib_hash_table;
89 /* This is a global so we don't have to pass this through every function.
90 It is used in new_elt_loc_list to set SETTING_INSN. */
91 static rtx cselib_current_insn;
93 /* The unique id that the next create value will take. */
94 static unsigned int next_uid;
96 /* The number of registers we had when the varrays were last resized. */
97 static unsigned int cselib_nregs;
99 /* Count values without known locations. Whenever this grows too big, we
100 remove these useless values from the table. */
101 static int n_useless_values;
103 /* Number of useless values before we remove them from the hash table. */
104 #define MAX_USELESS_VALUES 32
106 /* This table maps from register number to values. It does not
107 contain pointers to cselib_val structures, but rather elt_lists.
108 The purpose is to be able to refer to the same register in
109 different modes. The first element of the list defines the mode in
110 which the register was set; if the mode is unknown or the value is
111 no longer valid in that mode, ELT will be NULL for the first
113 static struct elt_list **reg_values;
114 static unsigned int reg_values_size;
115 #define REG_VALUES(i) reg_values[i]
117 /* The largest number of hard regs used by any entry added to the
118 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
119 static unsigned int max_value_regs;
121 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
122 in cselib_clear_table() for fast emptying. */
123 static unsigned int *used_regs;
124 static unsigned int n_used_regs;
126 /* We pass this to cselib_invalidate_mem to invalidate all of
127 memory for a non-const call instruction. */
128 static GTY(()) rtx callmem;
130 /* Set by discard_useless_locs if it deleted the last location of any
132 static int values_became_useless;
134 /* Used as stop element of the containing_mem list so we can check
135 presence in the list by checking the next pointer. */
136 static cselib_val dummy_val;
138 /* Used to list all values that contain memory reference.
139 May or may not contain the useless values - the list is compacted
140 each time memory is invalidated. */
141 static cselib_val *first_containing_mem = &dummy_val;
142 static alloc_pool elt_loc_list_pool, elt_list_pool, cselib_val_pool, value_pool;
144 /* If nonnull, cselib will call this function before freeing useless
145 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
146 void (*cselib_discard_hook) (cselib_val *);
148 /* If nonnull, cselib will call this function before recording sets or
149 even clobbering outputs of INSN. All the recorded sets will be
150 represented in the array sets[n_sets]. new_val_min can be used to
151 tell whether values present in sets are introduced by this
153 void (*cselib_record_sets_hook) (rtx insn, struct cselib_set *sets,
156 #define PRESERVED_VALUE_P(RTX) \
157 (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
161 /* Allocate a struct elt_list and fill in its two elements with the
164 static inline struct elt_list *
165 new_elt_list (struct elt_list *next, cselib_val *elt)
168 el = (struct elt_list *) pool_alloc (elt_list_pool);
174 /* Allocate a struct elt_loc_list and fill in its two elements with the
177 static inline struct elt_loc_list *
178 new_elt_loc_list (struct elt_loc_list *next, rtx loc)
180 struct elt_loc_list *el;
181 el = (struct elt_loc_list *) pool_alloc (elt_loc_list_pool);
184 el->setting_insn = cselib_current_insn;
188 /* The elt_list at *PL is no longer needed. Unchain it and free its
192 unchain_one_elt_list (struct elt_list **pl)
194 struct elt_list *l = *pl;
197 pool_free (elt_list_pool, l);
200 /* Likewise for elt_loc_lists. */
203 unchain_one_elt_loc_list (struct elt_loc_list **pl)
205 struct elt_loc_list *l = *pl;
208 pool_free (elt_loc_list_pool, l);
211 /* Likewise for cselib_vals. This also frees the addr_list associated with
215 unchain_one_value (cselib_val *v)
218 unchain_one_elt_list (&v->addr_list);
220 pool_free (cselib_val_pool, v);
223 /* Remove all entries from the hash table. Also used during
227 cselib_clear_table (void)
229 cselib_reset_table (1);
232 /* Remove all entries from the hash table, arranging for the next
233 value to be numbered NUM. */
236 cselib_reset_table (unsigned int num)
240 for (i = 0; i < n_used_regs; i++)
241 REG_VALUES (used_regs[i]) = 0;
247 /* ??? Preserve constants? */
248 htab_empty (cselib_hash_table);
250 n_useless_values = 0;
254 first_containing_mem = &dummy_val;
257 /* Return the number of the next value that will be generated. */
260 cselib_get_next_uid (void)
265 /* The equality test for our hash table. The first argument ENTRY is a table
266 element (i.e. a cselib_val), while the second arg X is an rtx. We know
267 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
268 CONST of an appropriate mode. */
271 entry_and_rtx_equal_p (const void *entry, const void *x_arg)
273 struct elt_loc_list *l;
274 const cselib_val *const v = (const cselib_val *) entry;
275 rtx x = CONST_CAST_RTX ((const_rtx)x_arg);
276 enum machine_mode mode = GET_MODE (x);
278 gcc_assert (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
279 && (mode != VOIDmode || GET_CODE (x) != CONST_DOUBLE));
281 if (mode != GET_MODE (v->val_rtx))
284 /* Unwrap X if necessary. */
285 if (GET_CODE (x) == CONST
286 && (CONST_INT_P (XEXP (x, 0))
287 || GET_CODE (XEXP (x, 0)) == CONST_FIXED
288 || GET_CODE (XEXP (x, 0)) == CONST_DOUBLE))
291 /* We don't guarantee that distinct rtx's have different hash values,
292 so we need to do a comparison. */
293 for (l = v->locs; l; l = l->next)
294 if (rtx_equal_for_cselib_p (l->loc, x))
300 /* The hash function for our hash table. The value is always computed with
301 cselib_hash_rtx when adding an element; this function just extracts the
302 hash value from a cselib_val structure. */
305 get_value_hash (const void *entry)
307 const cselib_val *const v = (const cselib_val *) entry;
311 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
312 only return true for values which point to a cselib_val whose value
313 element has been set to zero, which implies the cselib_val will be
317 references_value_p (const_rtx x, int only_useless)
319 const enum rtx_code code = GET_CODE (x);
320 const char *fmt = GET_RTX_FORMAT (code);
323 if (GET_CODE (x) == VALUE
324 && (! only_useless || CSELIB_VAL_PTR (x)->locs == 0))
327 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
329 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
331 else if (fmt[i] == 'E')
332 for (j = 0; j < XVECLEN (x, i); j++)
333 if (references_value_p (XVECEXP (x, i, j), only_useless))
340 /* For all locations found in X, delete locations that reference useless
341 values (i.e. values without any location). Called through
345 discard_useless_locs (void **x, void *info ATTRIBUTE_UNUSED)
347 cselib_val *v = (cselib_val *)*x;
348 struct elt_loc_list **p = &v->locs;
349 int had_locs = v->locs != 0;
353 if (references_value_p ((*p)->loc, 1))
354 unchain_one_elt_loc_list (p);
359 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
362 values_became_useless = 1;
367 /* If X is a value with no locations, remove it from the hashtable. */
370 discard_useless_values (void **x, void *info ATTRIBUTE_UNUSED)
372 cselib_val *v = (cselib_val *)*x;
374 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
376 if (cselib_discard_hook)
377 cselib_discard_hook (v);
379 CSELIB_VAL_PTR (v->val_rtx) = NULL;
380 htab_clear_slot (cselib_hash_table, x);
381 unchain_one_value (v);
388 /* Clean out useless values (i.e. those which no longer have locations
389 associated with them) from the hash table. */
392 remove_useless_values (void)
395 /* First pass: eliminate locations that reference the value. That in
396 turn can make more values useless. */
399 values_became_useless = 0;
400 htab_traverse (cselib_hash_table, discard_useless_locs, 0);
402 while (values_became_useless);
404 /* Second pass: actually remove the values. */
406 p = &first_containing_mem;
407 for (v = *p; v != &dummy_val; v = v->next_containing_mem)
411 p = &(*p)->next_containing_mem;
415 htab_traverse (cselib_hash_table, discard_useless_values, 0);
417 gcc_assert (!n_useless_values);
420 /* Arrange for a value to not be removed from the hash table even if
421 it becomes useless. */
424 cselib_preserve_value (cselib_val *v)
426 PRESERVED_VALUE_P (v->val_rtx) = 1;
429 /* Test whether a value is preserved. */
432 cselib_preserved_value_p (cselib_val *v)
434 return PRESERVED_VALUE_P (v->val_rtx);
437 /* Clean all non-constant expressions in the hash table, but retain
441 cselib_preserve_only_values (void)
445 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
446 cselib_invalidate_regno (i, reg_raw_mode[i]);
448 cselib_invalidate_mem (callmem);
450 remove_useless_values ();
452 gcc_assert (first_containing_mem == &dummy_val);
455 /* Return the mode in which a register was last set. If X is not a
456 register, return its mode. If the mode in which the register was
457 set is not known, or the value was already clobbered, return
461 cselib_reg_set_mode (const_rtx x)
466 if (REG_VALUES (REGNO (x)) == NULL
467 || REG_VALUES (REGNO (x))->elt == NULL)
470 return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
473 /* Return nonzero if we can prove that X and Y contain the same value, taking
474 our gathered information into account. */
477 rtx_equal_for_cselib_p (rtx x, rtx y)
483 if (REG_P (x) || MEM_P (x))
485 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0);
491 if (REG_P (y) || MEM_P (y))
493 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0);
502 if (GET_CODE (x) == VALUE && GET_CODE (y) == VALUE)
503 return CSELIB_VAL_PTR (x) == CSELIB_VAL_PTR (y);
505 if (GET_CODE (x) == VALUE)
507 cselib_val *e = CSELIB_VAL_PTR (x);
508 struct elt_loc_list *l;
510 for (l = e->locs; l; l = l->next)
514 /* Avoid infinite recursion. */
515 if (REG_P (t) || MEM_P (t))
517 else if (rtx_equal_for_cselib_p (t, y))
524 if (GET_CODE (y) == VALUE)
526 cselib_val *e = CSELIB_VAL_PTR (y);
527 struct elt_loc_list *l;
529 for (l = e->locs; l; l = l->next)
533 if (REG_P (t) || MEM_P (t))
535 else if (rtx_equal_for_cselib_p (x, t))
542 if (GET_CODE (x) != GET_CODE (y) || GET_MODE (x) != GET_MODE (y))
545 /* These won't be handled correctly by the code below. */
546 switch (GET_CODE (x))
554 return XEXP (x, 0) == XEXP (y, 0);
561 fmt = GET_RTX_FORMAT (code);
563 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
570 if (XWINT (x, i) != XWINT (y, i))
576 if (XINT (x, i) != XINT (y, i))
582 /* Two vectors must have the same length. */
583 if (XVECLEN (x, i) != XVECLEN (y, i))
586 /* And the corresponding elements must match. */
587 for (j = 0; j < XVECLEN (x, i); j++)
588 if (! rtx_equal_for_cselib_p (XVECEXP (x, i, j),
595 && targetm.commutative_p (x, UNKNOWN)
596 && rtx_equal_for_cselib_p (XEXP (x, 1), XEXP (y, 0))
597 && rtx_equal_for_cselib_p (XEXP (x, 0), XEXP (y, 1)))
599 if (! rtx_equal_for_cselib_p (XEXP (x, i), XEXP (y, i)))
605 if (strcmp (XSTR (x, i), XSTR (y, i)))
610 /* These are just backpointers, so they don't matter. */
617 /* It is believed that rtx's at this level will never
618 contain anything but integers and other rtx's,
619 except for within LABEL_REFs and SYMBOL_REFs. */
627 /* We need to pass down the mode of constants through the hash table
628 functions. For that purpose, wrap them in a CONST of the appropriate
631 wrap_constant (enum machine_mode mode, rtx x)
633 if (!CONST_INT_P (x) && GET_CODE (x) != CONST_FIXED
634 && (GET_CODE (x) != CONST_DOUBLE || GET_MODE (x) != VOIDmode))
636 gcc_assert (mode != VOIDmode);
637 return gen_rtx_CONST (mode, x);
640 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
641 For registers and memory locations, we look up their cselib_val structure
642 and return its VALUE element.
643 Possible reasons for return 0 are: the object is volatile, or we couldn't
644 find a register or memory location in the table and CREATE is zero. If
645 CREATE is nonzero, table elts are created for regs and mem.
646 N.B. this hash function returns the same hash value for RTXes that
647 differ only in the order of operands, thus it is suitable for comparisons
648 that take commutativity into account.
649 If we wanted to also support associative rules, we'd have to use a different
650 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
651 We used to have a MODE argument for hashing for CONST_INTs, but that
652 didn't make sense, since it caused spurious hash differences between
653 (set (reg:SI 1) (const_int))
654 (plus:SI (reg:SI 2) (reg:SI 1))
656 (plus:SI (reg:SI 2) (const_int))
657 If the mode is important in any context, it must be checked specifically
658 in a comparison anyway, since relying on hash differences is unsafe. */
661 cselib_hash_rtx (rtx x, int create)
667 unsigned int hash = 0;
670 hash += (unsigned) code + (unsigned) GET_MODE (x);
676 e = cselib_lookup (x, GET_MODE (x), create);
683 hash += ((unsigned) DEBUG_EXPR << 7)
684 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
685 return hash ? hash : (unsigned int) DEBUG_EXPR;
688 hash += ((unsigned) CONST_INT << 7) + INTVAL (x);
689 return hash ? hash : (unsigned int) CONST_INT;
692 /* This is like the general case, except that it only counts
693 the integers representing the constant. */
694 hash += (unsigned) code + (unsigned) GET_MODE (x);
695 if (GET_MODE (x) != VOIDmode)
696 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
698 hash += ((unsigned) CONST_DOUBLE_LOW (x)
699 + (unsigned) CONST_DOUBLE_HIGH (x));
700 return hash ? hash : (unsigned int) CONST_DOUBLE;
703 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
704 hash += fixed_hash (CONST_FIXED_VALUE (x));
705 return hash ? hash : (unsigned int) CONST_FIXED;
712 units = CONST_VECTOR_NUNITS (x);
714 for (i = 0; i < units; ++i)
716 elt = CONST_VECTOR_ELT (x, i);
717 hash += cselib_hash_rtx (elt, 0);
723 /* Assume there is only one rtx object for any given label. */
725 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
726 differences and differences between each stage's debugging dumps. */
727 hash += (((unsigned int) LABEL_REF << 7)
728 + CODE_LABEL_NUMBER (XEXP (x, 0)));
729 return hash ? hash : (unsigned int) LABEL_REF;
733 /* Don't hash on the symbol's address to avoid bootstrap differences.
734 Different hash values may cause expressions to be recorded in
735 different orders and thus different registers to be used in the
736 final assembler. This also avoids differences in the dump files
737 between various stages. */
739 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
742 h += (h << 7) + *p++; /* ??? revisit */
744 hash += ((unsigned int) SYMBOL_REF << 7) + h;
745 return hash ? hash : (unsigned int) SYMBOL_REF;
757 case UNSPEC_VOLATILE:
761 if (MEM_VOLATILE_P (x))
770 i = GET_RTX_LENGTH (code) - 1;
771 fmt = GET_RTX_FORMAT (code);
778 rtx tem = XEXP (x, i);
779 unsigned int tem_hash = cselib_hash_rtx (tem, create);
788 for (j = 0; j < XVECLEN (x, i); j++)
790 unsigned int tem_hash
791 = cselib_hash_rtx (XVECEXP (x, i, j), create);
802 const unsigned char *p = (const unsigned char *) XSTR (x, i);
824 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
827 /* Create a new value structure for VALUE and initialize it. The mode of the
830 static inline cselib_val *
831 new_cselib_val (unsigned int hash, enum machine_mode mode, rtx x)
833 cselib_val *e = (cselib_val *) pool_alloc (cselib_val_pool);
836 gcc_assert (next_uid);
840 /* We use an alloc pool to allocate this RTL construct because it
841 accounts for about 8% of the overall memory usage. We know
842 precisely when we can have VALUE RTXen (when cselib is active)
843 so we don't need to put them in garbage collected memory.
844 ??? Why should a VALUE be an RTX in the first place? */
845 e->val_rtx = (rtx) pool_alloc (value_pool);
846 memset (e->val_rtx, 0, RTX_HDR_SIZE);
847 PUT_CODE (e->val_rtx, VALUE);
848 PUT_MODE (e->val_rtx, mode);
849 CSELIB_VAL_PTR (e->val_rtx) = e;
852 e->next_containing_mem = 0;
854 if (dump_file && (dump_flags & TDF_DETAILS))
856 fprintf (dump_file, "cselib value %u:%u ", e->uid, hash);
857 if (flag_dump_noaddr || flag_dump_unnumbered)
858 fputs ("# ", dump_file);
860 fprintf (dump_file, "%p ", (void*)e);
861 print_rtl_single (dump_file, x);
862 fputc ('\n', dump_file);
868 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
869 contains the data at this address. X is a MEM that represents the
870 value. Update the two value structures to represent this situation. */
873 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
875 struct elt_loc_list *l;
877 /* Avoid duplicates. */
878 for (l = mem_elt->locs; l; l = l->next)
880 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt)
883 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
885 = new_elt_loc_list (mem_elt->locs,
886 replace_equiv_address_nv (x, addr_elt->val_rtx));
887 if (mem_elt->next_containing_mem == NULL)
889 mem_elt->next_containing_mem = first_containing_mem;
890 first_containing_mem = mem_elt;
894 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
895 If CREATE, make a new one if we haven't seen it before. */
898 cselib_lookup_mem (rtx x, int create)
900 enum machine_mode mode = GET_MODE (x);
906 if (MEM_VOLATILE_P (x) || mode == BLKmode
907 || !cselib_record_memory
908 || (FLOAT_MODE_P (mode) && flag_float_store))
911 /* Look up the value for the address. */
912 addr = cselib_lookup (XEXP (x, 0), mode, create);
916 /* Find a value that describes a value of our mode at that address. */
917 for (l = addr->addr_list; l; l = l->next)
918 if (GET_MODE (l->elt->val_rtx) == mode)
924 mem_elt = new_cselib_val (next_uid, mode, x);
925 add_mem_for_addr (addr, mem_elt, x);
926 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
927 mem_elt->hash, INSERT);
932 /* Search thru the possible substitutions in P. We prefer a non reg
933 substitution because this allows us to expand the tree further. If
934 we find, just a reg, take the lowest regno. There may be several
935 non-reg results, we just take the first one because they will all
936 expand to the same place. */
939 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
942 rtx reg_result = NULL;
943 unsigned int regno = UINT_MAX;
944 struct elt_loc_list *p_in = p;
946 for (; p; p = p -> next)
948 /* Avoid infinite recursion trying to expand a reg into a
951 && (REGNO (p->loc) < regno)
952 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
955 regno = REGNO (p->loc);
957 /* Avoid infinite recursion and do not try to expand the
959 else if (GET_CODE (p->loc) == VALUE
960 && CSELIB_VAL_PTR (p->loc)->locs == p_in)
962 else if (!REG_P (p->loc))
965 if (dump_file && (dump_flags & TDF_DETAILS))
967 print_inline_rtx (dump_file, p->loc, 0);
968 fprintf (dump_file, "\n");
970 if (GET_CODE (p->loc) == LO_SUM
971 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
973 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
974 && XEXP (note, 0) == XEXP (p->loc, 1))
975 return XEXP (p->loc, 1);
976 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
983 if (regno != UINT_MAX)
986 if (dump_file && (dump_flags & TDF_DETAILS))
987 fprintf (dump_file, "r%d\n", regno);
989 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
994 if (dump_file && (dump_flags & TDF_DETAILS))
998 print_inline_rtx (dump_file, reg_result, 0);
999 fprintf (dump_file, "\n");
1002 fprintf (dump_file, "NULL\n");
1008 /* Forward substitute and expand an expression out to its roots.
1009 This is the opposite of common subexpression. Because local value
1010 numbering is such a weak optimization, the expanded expression is
1011 pretty much unique (not from a pointer equals point of view but
1012 from a tree shape point of view.
1014 This function returns NULL if the expansion fails. The expansion
1015 will fail if there is no value number for one of the operands or if
1016 one of the operands has been overwritten between the current insn
1017 and the beginning of the basic block. For instance x has no
1023 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1024 It is clear on return. */
1027 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1029 struct expand_value_data evd;
1031 evd.regs_active = regs_active;
1032 evd.callback = NULL;
1033 evd.callback_arg = NULL;
1036 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1039 /* Same as cselib_expand_value_rtx, but using a callback to try to
1040 resolve some expressions. The CB function should return ORIG if it
1041 can't or does not want to deal with a certain RTX. Any other
1042 return value, including NULL, will be used as the expansion for
1043 VALUE, without any further changes. */
1046 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1047 cselib_expand_callback cb, void *data)
1049 struct expand_value_data evd;
1051 evd.regs_active = regs_active;
1053 evd.callback_arg = data;
1056 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1059 /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1060 or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1061 would return NULL or non-NULL, without allocating new rtx. */
1064 cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1065 cselib_expand_callback cb, void *data)
1067 struct expand_value_data evd;
1069 evd.regs_active = regs_active;
1071 evd.callback_arg = data;
1074 return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL;
1077 /* Internal implementation of cselib_expand_value_rtx and
1078 cselib_expand_value_rtx_cb. */
1081 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1087 const char *format_ptr;
1088 enum machine_mode mode;
1090 code = GET_CODE (orig);
1092 /* For the context of dse, if we end up expand into a huge tree, we
1093 will not have a useful address, so we might as well just give up
1102 struct elt_list *l = REG_VALUES (REGNO (orig));
1104 if (l && l->elt == NULL)
1106 for (; l; l = l->next)
1107 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1110 int regno = REGNO (orig);
1112 /* The only thing that we are not willing to do (this
1113 is requirement of dse and if others potential uses
1114 need this function we should add a parm to control
1115 it) is that we will not substitute the
1116 STACK_POINTER_REGNUM, FRAME_POINTER or the
1119 These expansions confuses the code that notices that
1120 stores into the frame go dead at the end of the
1121 function and that the frame is not effected by calls
1122 to subroutines. If you allow the
1123 STACK_POINTER_REGNUM substitution, then dse will
1124 think that parameter pushing also goes dead which is
1125 wrong. If you allow the FRAME_POINTER or the
1126 HARD_FRAME_POINTER then you lose the opportunity to
1127 make the frame assumptions. */
1128 if (regno == STACK_POINTER_REGNUM
1129 || regno == FRAME_POINTER_REGNUM
1130 || regno == HARD_FRAME_POINTER_REGNUM)
1133 bitmap_set_bit (evd->regs_active, regno);
1135 if (dump_file && (dump_flags & TDF_DETAILS))
1136 fprintf (dump_file, "expanding: r%d into: ", regno);
1138 result = expand_loc (l->elt->locs, evd, max_depth);
1139 bitmap_clear_bit (evd->regs_active, regno);
1156 /* SCRATCH must be shared because they represent distinct values. */
1159 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1164 if (shared_const_p (orig))
1174 subreg = evd->callback (orig, evd->regs_active, max_depth,
1180 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1184 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1185 GET_MODE (SUBREG_REG (orig)),
1186 SUBREG_BYTE (orig));
1188 || (GET_CODE (scopy) == SUBREG
1189 && !REG_P (SUBREG_REG (scopy))
1190 && !MEM_P (SUBREG_REG (scopy))))
1200 if (dump_file && (dump_flags & TDF_DETAILS))
1202 fputs ("\nexpanding ", dump_file);
1203 print_rtl_single (dump_file, orig);
1204 fputs (" into...", dump_file);
1209 result = evd->callback (orig, evd->regs_active, max_depth,
1216 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1222 return evd->callback (orig, evd->regs_active, max_depth,
1230 /* Copy the various flags, fields, and other information. We assume
1231 that all fields need copying, and then clear the fields that should
1232 not be copied. That is the sensible default behavior, and forces
1233 us to explicitly document why we are *not* copying a flag. */
1237 copy = shallow_copy_rtx (orig);
1239 format_ptr = GET_RTX_FORMAT (code);
1241 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1242 switch (*format_ptr++)
1245 if (XEXP (orig, i) != NULL)
1247 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1252 XEXP (copy, i) = result;
1258 if (XVEC (orig, i) != NULL)
1261 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1262 for (j = 0; j < XVECLEN (orig, i); j++)
1264 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1265 evd, max_depth - 1);
1269 XVECEXP (copy, i, j) = result;
1283 /* These are left unchanged. */
1293 mode = GET_MODE (copy);
1294 /* If an operand has been simplified into CONST_INT, which doesn't
1295 have a mode and the mode isn't derivable from whole rtx's mode,
1296 try simplify_*_operation first with mode from original's operand
1297 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1299 switch (GET_RTX_CLASS (code))
1302 if (CONST_INT_P (XEXP (copy, 0))
1303 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1305 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1306 GET_MODE (XEXP (orig, 0)));
1311 case RTX_COMM_ARITH:
1313 /* These expressions can derive operand modes from the whole rtx's mode. */
1316 case RTX_BITFIELD_OPS:
1317 if (CONST_INT_P (XEXP (copy, 0))
1318 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1320 scopy = simplify_ternary_operation (code, mode,
1321 GET_MODE (XEXP (orig, 0)),
1322 XEXP (copy, 0), XEXP (copy, 1),
1329 case RTX_COMM_COMPARE:
1330 if (CONST_INT_P (XEXP (copy, 0))
1331 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1332 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1333 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1335 scopy = simplify_relational_operation (code, mode,
1336 (GET_MODE (XEXP (orig, 0))
1338 ? GET_MODE (XEXP (orig, 0))
1339 : GET_MODE (XEXP (orig, 1)),
1349 scopy = simplify_rtx (copy);
1355 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1356 with VALUE expressions. This way, it becomes independent of changes
1357 to registers and memory.
1358 X isn't actually modified; if modifications are needed, new rtl is
1359 allocated. However, the return value can share rtl with X. */
1362 cselib_subst_to_values (rtx x)
1364 enum rtx_code code = GET_CODE (x);
1365 const char *fmt = GET_RTX_FORMAT (code);
1374 l = REG_VALUES (REGNO (x));
1375 if (l && l->elt == NULL)
1377 for (; l; l = l->next)
1378 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1379 return l->elt->val_rtx;
1384 e = cselib_lookup_mem (x, 0);
1387 /* This happens for autoincrements. Assign a value that doesn't
1389 e = new_cselib_val (next_uid, GET_MODE (x), x);
1405 e = new_cselib_val (next_uid, GET_MODE (x), x);
1412 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1416 rtx t = cselib_subst_to_values (XEXP (x, i));
1418 if (t != XEXP (x, i))
1421 copy = shallow_copy_rtx (x);
1425 else if (fmt[i] == 'E')
1429 for (j = 0; j < XVECLEN (x, i); j++)
1431 rtx t = cselib_subst_to_values (XVECEXP (x, i, j));
1433 if (t != XVECEXP (x, i, j))
1435 if (XVEC (x, i) == XVEC (copy, i))
1438 copy = shallow_copy_rtx (x);
1439 XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
1441 XVECEXP (copy, i, j) = t;
1450 /* Log a lookup of X to the cselib table along with the result RET. */
1453 cselib_log_lookup (rtx x, cselib_val *ret)
1455 if (dump_file && (dump_flags & TDF_DETAILS))
1457 fputs ("cselib lookup ", dump_file);
1458 print_inline_rtx (dump_file, x, 2);
1459 fprintf (dump_file, " => %u:%u\n",
1461 ret ? ret->hash : 0);
1467 /* Look up the rtl expression X in our tables and return the value it has.
1468 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1469 we create a new one if possible, using mode MODE if X doesn't have a mode
1470 (i.e. because it's a constant). */
1473 cselib_lookup (rtx x, enum machine_mode mode, int create)
1477 unsigned int hashval;
1479 if (GET_MODE (x) != VOIDmode)
1480 mode = GET_MODE (x);
1482 if (GET_CODE (x) == VALUE)
1483 return CSELIB_VAL_PTR (x);
1488 unsigned int i = REGNO (x);
1491 if (l && l->elt == NULL)
1493 for (; l; l = l->next)
1494 if (mode == GET_MODE (l->elt->val_rtx))
1495 return cselib_log_lookup (x, l->elt);
1498 return cselib_log_lookup (x, 0);
1500 if (i < FIRST_PSEUDO_REGISTER)
1502 unsigned int n = hard_regno_nregs[i][mode];
1504 if (n > max_value_regs)
1508 e = new_cselib_val (next_uid, GET_MODE (x), x);
1509 e->locs = new_elt_loc_list (e->locs, x);
1510 if (REG_VALUES (i) == 0)
1512 /* Maintain the invariant that the first entry of
1513 REG_VALUES, if present, must be the value used to set the
1514 register, or NULL. */
1515 used_regs[n_used_regs++] = i;
1516 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
1518 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
1519 slot = htab_find_slot_with_hash (cselib_hash_table, x, e->hash, INSERT);
1521 return cselib_log_lookup (x, e);
1525 return cselib_log_lookup (x, cselib_lookup_mem (x, create));
1527 hashval = cselib_hash_rtx (x, create);
1528 /* Can't even create if hashing is not possible. */
1530 return cselib_log_lookup (x, 0);
1532 slot = htab_find_slot_with_hash (cselib_hash_table, wrap_constant (mode, x),
1533 hashval, create ? INSERT : NO_INSERT);
1535 return cselib_log_lookup (x, 0);
1537 e = (cselib_val *) *slot;
1539 return cselib_log_lookup (x, e);
1541 e = new_cselib_val (hashval, mode, x);
1543 /* We have to fill the slot before calling cselib_subst_to_values:
1544 the hash table is inconsistent until we do so, and
1545 cselib_subst_to_values will need to do lookups. */
1547 e->locs = new_elt_loc_list (e->locs, cselib_subst_to_values (x));
1548 return cselib_log_lookup (x, e);
1551 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1552 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1553 is used to determine how many hard registers are being changed. If MODE
1554 is VOIDmode, then only REGNO is being changed; this is used when
1555 invalidating call clobbered registers across a call. */
1558 cselib_invalidate_regno (unsigned int regno, enum machine_mode mode)
1560 unsigned int endregno;
1563 /* If we see pseudos after reload, something is _wrong_. */
1564 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
1565 || reg_renumber[regno] < 0);
1567 /* Determine the range of registers that must be invalidated. For
1568 pseudos, only REGNO is affected. For hard regs, we must take MODE
1569 into account, and we must also invalidate lower register numbers
1570 if they contain values that overlap REGNO. */
1571 if (regno < FIRST_PSEUDO_REGISTER)
1573 gcc_assert (mode != VOIDmode);
1575 if (regno < max_value_regs)
1578 i = regno - max_value_regs;
1580 endregno = end_hard_regno (mode, regno);
1585 endregno = regno + 1;
1588 for (; i < endregno; i++)
1590 struct elt_list **l = ®_VALUES (i);
1592 /* Go through all known values for this reg; if it overlaps the range
1593 we're invalidating, remove the value. */
1596 cselib_val *v = (*l)->elt;
1597 struct elt_loc_list **p;
1598 unsigned int this_last = i;
1600 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
1601 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
1603 if (this_last < regno || v == NULL)
1609 /* We have an overlap. */
1610 if (*l == REG_VALUES (i))
1612 /* Maintain the invariant that the first entry of
1613 REG_VALUES, if present, must be the value used to set
1614 the register, or NULL. This is also nice because
1615 then we won't push the same regno onto user_regs
1621 unchain_one_elt_list (l);
1623 /* Now, we clear the mapping from value to reg. It must exist, so
1624 this code will crash intentionally if it doesn't. */
1625 for (p = &v->locs; ; p = &(*p)->next)
1629 if (REG_P (x) && REGNO (x) == i)
1631 unchain_one_elt_loc_list (p);
1635 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1641 /* Return 1 if X has a value that can vary even between two
1642 executions of the program. 0 means X can be compared reliably
1643 against certain constants or near-constants. */
1646 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED, bool from_alias ATTRIBUTE_UNUSED)
1648 /* We actually don't need to verify very hard. This is because
1649 if X has actually changed, we invalidate the memory anyway,
1650 so assume that all common memory addresses are
1655 /* Invalidate any locations in the table which are changed because of a
1656 store to MEM_RTX. If this is called because of a non-const call
1657 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1660 cselib_invalidate_mem (rtx mem_rtx)
1662 cselib_val **vp, *v, *next;
1666 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
1667 mem_rtx = canon_rtx (mem_rtx);
1669 vp = &first_containing_mem;
1670 for (v = *vp; v != &dummy_val; v = next)
1672 bool has_mem = false;
1673 struct elt_loc_list **p = &v->locs;
1674 int had_locs = v->locs != 0;
1680 struct elt_list **mem_chain;
1682 /* MEMs may occur in locations only at the top level; below
1683 that every MEM or REG is substituted by its VALUE. */
1689 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
1690 && ! canon_true_dependence (mem_rtx, GET_MODE (mem_rtx), mem_addr,
1691 x, NULL_RTX, cselib_rtx_varies_p))
1699 /* This one overlaps. */
1700 /* We must have a mapping from this MEM's address to the
1701 value (E). Remove that, too. */
1702 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0);
1703 mem_chain = &addr->addr_list;
1706 if ((*mem_chain)->elt == v)
1708 unchain_one_elt_list (mem_chain);
1712 mem_chain = &(*mem_chain)->next;
1715 unchain_one_elt_loc_list (p);
1718 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
1721 next = v->next_containing_mem;
1725 vp = &(*vp)->next_containing_mem;
1728 v->next_containing_mem = NULL;
1733 /* Invalidate DEST, which is being assigned to or clobbered. */
1736 cselib_invalidate_rtx (rtx dest)
1738 while (GET_CODE (dest) == SUBREG
1739 || GET_CODE (dest) == ZERO_EXTRACT
1740 || GET_CODE (dest) == STRICT_LOW_PART)
1741 dest = XEXP (dest, 0);
1744 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
1745 else if (MEM_P (dest))
1746 cselib_invalidate_mem (dest);
1748 /* Some machines don't define AUTO_INC_DEC, but they still use push
1749 instructions. We need to catch that case here in order to
1750 invalidate the stack pointer correctly. Note that invalidating
1751 the stack pointer is different from invalidating DEST. */
1752 if (push_operand (dest, GET_MODE (dest)))
1753 cselib_invalidate_rtx (stack_pointer_rtx);
1756 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1759 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx ignore ATTRIBUTE_UNUSED,
1760 void *data ATTRIBUTE_UNUSED)
1762 cselib_invalidate_rtx (dest);
1765 /* Record the result of a SET instruction. DEST is being set; the source
1766 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1767 describes its address. */
1770 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
1772 int dreg = REG_P (dest) ? (int) REGNO (dest) : -1;
1774 if (src_elt == 0 || side_effects_p (dest))
1779 if (dreg < FIRST_PSEUDO_REGISTER)
1781 unsigned int n = hard_regno_nregs[dreg][GET_MODE (dest)];
1783 if (n > max_value_regs)
1787 if (REG_VALUES (dreg) == 0)
1789 used_regs[n_used_regs++] = dreg;
1790 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
1794 /* The register should have been invalidated. */
1795 gcc_assert (REG_VALUES (dreg)->elt == 0);
1796 REG_VALUES (dreg)->elt = src_elt;
1799 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1801 src_elt->locs = new_elt_loc_list (src_elt->locs, dest);
1803 else if (MEM_P (dest) && dest_addr_elt != 0
1804 && cselib_record_memory)
1806 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
1808 add_mem_for_addr (dest_addr_elt, src_elt, dest);
1812 /* There is no good way to determine how many elements there can be
1813 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1814 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1816 /* Record the effects of any sets in INSN. */
1818 cselib_record_sets (rtx insn)
1822 struct cselib_set sets[MAX_SETS];
1823 rtx body = PATTERN (insn);
1826 body = PATTERN (insn);
1827 if (GET_CODE (body) == COND_EXEC)
1829 cond = COND_EXEC_TEST (body);
1830 body = COND_EXEC_CODE (body);
1833 /* Find all sets. */
1834 if (GET_CODE (body) == SET)
1836 sets[0].src = SET_SRC (body);
1837 sets[0].dest = SET_DEST (body);
1840 else if (GET_CODE (body) == PARALLEL)
1842 /* Look through the PARALLEL and record the values being
1843 set, if possible. Also handle any CLOBBERs. */
1844 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
1846 rtx x = XVECEXP (body, 0, i);
1848 if (GET_CODE (x) == SET)
1850 sets[n_sets].src = SET_SRC (x);
1851 sets[n_sets].dest = SET_DEST (x);
1858 && MEM_P (sets[0].src)
1859 && !cselib_record_memory
1860 && MEM_READONLY_P (sets[0].src))
1862 rtx note = find_reg_equal_equiv_note (insn);
1864 if (note && CONSTANT_P (XEXP (note, 0)))
1865 sets[0].src = XEXP (note, 0);
1868 /* Look up the values that are read. Do this before invalidating the
1869 locations that are written. */
1870 for (i = 0; i < n_sets; i++)
1872 rtx dest = sets[i].dest;
1874 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1875 the low part after invalidating any knowledge about larger modes. */
1876 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
1877 sets[i].dest = dest = XEXP (dest, 0);
1879 /* We don't know how to record anything but REG or MEM. */
1881 || (MEM_P (dest) && cselib_record_memory))
1883 rtx src = sets[i].src;
1885 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
1886 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1);
1889 enum machine_mode address_mode
1890 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (dest));
1892 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
1896 sets[i].dest_addr_elt = 0;
1900 if (cselib_record_sets_hook)
1901 cselib_record_sets_hook (insn, sets, n_sets);
1903 /* Invalidate all locations written by this insn. Note that the elts we
1904 looked up in the previous loop aren't affected, just some of their
1905 locations may go away. */
1906 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
1908 /* If this is an asm, look for duplicate sets. This can happen when the
1909 user uses the same value as an output multiple times. This is valid
1910 if the outputs are not actually used thereafter. Treat this case as
1911 if the value isn't actually set. We do this by smashing the destination
1912 to pc_rtx, so that we won't record the value later. */
1913 if (n_sets >= 2 && asm_noperands (body) >= 0)
1915 for (i = 0; i < n_sets; i++)
1917 rtx dest = sets[i].dest;
1918 if (REG_P (dest) || MEM_P (dest))
1921 for (j = i + 1; j < n_sets; j++)
1922 if (rtx_equal_p (dest, sets[j].dest))
1924 sets[i].dest = pc_rtx;
1925 sets[j].dest = pc_rtx;
1931 /* Now enter the equivalences in our tables. */
1932 for (i = 0; i < n_sets; i++)
1934 rtx dest = sets[i].dest;
1936 || (MEM_P (dest) && cselib_record_memory))
1937 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
1941 /* Record the effects of INSN. */
1944 cselib_process_insn (rtx insn)
1949 cselib_current_insn = insn;
1951 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1954 && find_reg_note (insn, REG_SETJMP, NULL))
1955 || (NONJUMP_INSN_P (insn)
1956 && GET_CODE (PATTERN (insn)) == ASM_OPERANDS
1957 && MEM_VOLATILE_P (PATTERN (insn))))
1959 cselib_reset_table (next_uid);
1963 if (! INSN_P (insn))
1965 cselib_current_insn = 0;
1969 /* If this is a call instruction, forget anything stored in a
1970 call clobbered register, or, if this is not a const call, in
1974 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1975 if (call_used_regs[i]
1976 || (REG_VALUES (i) && REG_VALUES (i)->elt
1977 && HARD_REGNO_CALL_PART_CLOBBERED (i,
1978 GET_MODE (REG_VALUES (i)->elt->val_rtx))))
1979 cselib_invalidate_regno (i, reg_raw_mode[i]);
1981 /* Since it is not clear how cselib is going to be used, be
1982 conservative here and treat looping pure or const functions
1983 as if they were regular functions. */
1984 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1985 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
1986 cselib_invalidate_mem (callmem);
1989 cselib_record_sets (insn);
1992 /* Clobber any registers which appear in REG_INC notes. We
1993 could keep track of the changes to their values, but it is
1994 unlikely to help. */
1995 for (x = REG_NOTES (insn); x; x = XEXP (x, 1))
1996 if (REG_NOTE_KIND (x) == REG_INC)
1997 cselib_invalidate_rtx (XEXP (x, 0));
2000 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2001 after we have processed the insn. */
2003 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2004 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
2005 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
2007 cselib_current_insn = 0;
2009 if (n_useless_values > MAX_USELESS_VALUES
2010 /* remove_useless_values is linear in the hash table size. Avoid
2011 quadratic behavior for very large hashtables with very few
2012 useless elements. */
2013 && (unsigned int)n_useless_values > cselib_hash_table->n_elements / 4)
2014 remove_useless_values ();
2017 /* Initialize cselib for one pass. The caller must also call
2018 init_alias_analysis. */
2021 cselib_init (bool record_memory)
2023 elt_list_pool = create_alloc_pool ("elt_list",
2024 sizeof (struct elt_list), 10);
2025 elt_loc_list_pool = create_alloc_pool ("elt_loc_list",
2026 sizeof (struct elt_loc_list), 10);
2027 cselib_val_pool = create_alloc_pool ("cselib_val_list",
2028 sizeof (cselib_val), 10);
2029 value_pool = create_alloc_pool ("value", RTX_CODE_SIZE (VALUE), 100);
2030 cselib_record_memory = record_memory;
2032 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2033 see canon_true_dependence. This is only created once. */
2035 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2037 cselib_nregs = max_reg_num ();
2039 /* We preserve reg_values to allow expensive clearing of the whole thing.
2040 Reallocate it however if it happens to be too large. */
2041 if (!reg_values || reg_values_size < cselib_nregs
2042 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2046 /* Some space for newly emit instructions so we don't end up
2047 reallocating in between passes. */
2048 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2049 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2051 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2053 cselib_hash_table = htab_create (31, get_value_hash,
2054 entry_and_rtx_equal_p, NULL);
2058 /* Called when the current user is done with cselib. */
2061 cselib_finish (void)
2063 cselib_discard_hook = NULL;
2064 free_alloc_pool (elt_list_pool);
2065 free_alloc_pool (elt_loc_list_pool);
2066 free_alloc_pool (cselib_val_pool);
2067 free_alloc_pool (value_pool);
2068 cselib_clear_table ();
2069 htab_delete (cselib_hash_table);
2072 cselib_hash_table = 0;
2073 n_useless_values = 0;
2077 /* Dump the cselib_val *X to FILE *info. */
2080 dump_cselib_val (void **x, void *info)
2082 cselib_val *v = (cselib_val *)*x;
2083 FILE *out = (FILE *)info;
2084 bool need_lf = true;
2086 print_inline_rtx (out, v->val_rtx, 0);
2090 struct elt_loc_list *l = v->locs;
2096 fputs (" locs:", out);
2099 fprintf (out, "\n from insn %i ",
2100 INSN_UID (l->setting_insn));
2101 print_inline_rtx (out, l->loc, 4);
2103 while ((l = l->next));
2108 fputs (" no locs", out);
2114 struct elt_list *e = v->addr_list;
2120 fputs (" addr list:", out);
2124 print_inline_rtx (out, e->elt->val_rtx, 2);
2126 while ((e = e->next));
2131 fputs (" no addrs", out);
2135 if (v->next_containing_mem == &dummy_val)
2136 fputs (" last mem\n", out);
2137 else if (v->next_containing_mem)
2139 fputs (" next mem ", out);
2140 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2149 /* Dump to OUT everything in the CSELIB table. */
2152 dump_cselib_table (FILE *out)
2154 fprintf (out, "cselib hash table:\n");
2155 htab_traverse (cselib_hash_table, dump_cselib_val, out);
2156 if (first_containing_mem != &dummy_val)
2158 fputs ("first mem ", out);
2159 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2162 fprintf (out, "next uid %i\n", next_uid);
2165 #include "gt-cselib.h"