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 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
43 #include "alloc-pool.h"
46 static bool cselib_record_memory
;
47 static int entry_and_rtx_equal_p (const void *, const void *);
48 static hashval_t
get_value_hash (const void *);
49 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
50 static struct elt_loc_list
*new_elt_loc_list (struct elt_loc_list
*, rtx
);
51 static void unchain_one_value (cselib_val
*);
52 static void unchain_one_elt_list (struct elt_list
**);
53 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
54 static int discard_useless_locs (void **, void *);
55 static int discard_useless_values (void **, void *);
56 static void remove_useless_values (void);
57 static rtx
wrap_constant (enum machine_mode
, rtx
);
58 static unsigned int cselib_hash_rtx (rtx
, int);
59 static cselib_val
*new_cselib_val (unsigned int, enum machine_mode
);
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 /* There are three ways in which cselib can look up an rtx:
68 - for a REG, the reg_values table (which is indexed by regno) is used
69 - for a MEM, we recursively look up its address and then follow the
70 addr_list of that value
71 - for everything else, we compute a hash value and go through the hash
72 table. Since different rtx's can still have the same hash value,
73 this involves walking the table entries for a given value and comparing
74 the locations of the entries with the rtx we are looking up. */
76 /* A table that enables us to look up elts by their value. */
77 static htab_t cselib_hash_table
;
79 /* This is a global so we don't have to pass this through every function.
80 It is used in new_elt_loc_list to set SETTING_INSN. */
81 static rtx cselib_current_insn
;
82 static bool cselib_current_insn_in_libcall
;
84 /* Every new unknown value gets a unique number. */
85 static unsigned int next_unknown_value
;
87 /* The number of registers we had when the varrays were last resized. */
88 static unsigned int cselib_nregs
;
90 /* Count values without known locations. Whenever this grows too big, we
91 remove these useless values from the table. */
92 static int n_useless_values
;
94 /* Number of useless values before we remove them from the hash table. */
95 #define MAX_USELESS_VALUES 32
97 /* This table maps from register number to values. It does not
98 contain pointers to cselib_val structures, but rather elt_lists.
99 The purpose is to be able to refer to the same register in
100 different modes. The first element of the list defines the mode in
101 which the register was set; if the mode is unknown or the value is
102 no longer valid in that mode, ELT will be NULL for the first
104 static struct elt_list
**reg_values
;
105 static unsigned int reg_values_size
;
106 #define REG_VALUES(i) reg_values[i]
108 /* The largest number of hard regs used by any entry added to the
109 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
110 static unsigned int max_value_regs
;
112 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
113 in cselib_clear_table() for fast emptying. */
114 static unsigned int *used_regs
;
115 static unsigned int n_used_regs
;
117 /* We pass this to cselib_invalidate_mem to invalidate all of
118 memory for a non-const call instruction. */
119 static GTY(()) rtx callmem
;
121 /* Set by discard_useless_locs if it deleted the last location of any
123 static int values_became_useless
;
125 /* Used as stop element of the containing_mem list so we can check
126 presence in the list by checking the next pointer. */
127 static cselib_val dummy_val
;
129 /* Used to list all values that contain memory reference.
130 May or may not contain the useless values - the list is compacted
131 each time memory is invalidated. */
132 static cselib_val
*first_containing_mem
= &dummy_val
;
133 static alloc_pool elt_loc_list_pool
, elt_list_pool
, cselib_val_pool
, value_pool
;
135 /* If nonnull, cselib will call this function before freeing useless
136 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
137 void (*cselib_discard_hook
) (cselib_val
*);
140 /* Allocate a struct elt_list and fill in its two elements with the
143 static inline struct elt_list
*
144 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
147 el
= pool_alloc (elt_list_pool
);
153 /* Allocate a struct elt_loc_list and fill in its two elements with the
156 static inline struct elt_loc_list
*
157 new_elt_loc_list (struct elt_loc_list
*next
, rtx loc
)
159 struct elt_loc_list
*el
;
160 el
= pool_alloc (elt_loc_list_pool
);
163 el
->setting_insn
= cselib_current_insn
;
164 el
->in_libcall
= cselib_current_insn_in_libcall
;
168 /* The elt_list at *PL is no longer needed. Unchain it and free its
172 unchain_one_elt_list (struct elt_list
**pl
)
174 struct elt_list
*l
= *pl
;
177 pool_free (elt_list_pool
, l
);
180 /* Likewise for elt_loc_lists. */
183 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
185 struct elt_loc_list
*l
= *pl
;
188 pool_free (elt_loc_list_pool
, l
);
191 /* Likewise for cselib_vals. This also frees the addr_list associated with
195 unchain_one_value (cselib_val
*v
)
198 unchain_one_elt_list (&v
->addr_list
);
200 pool_free (cselib_val_pool
, v
);
203 /* Remove all entries from the hash table. Also used during
204 initialization. If CLEAR_ALL isn't set, then only clear the entries
205 which are known to have been used. */
208 cselib_clear_table (void)
212 for (i
= 0; i
< n_used_regs
; i
++)
213 REG_VALUES (used_regs
[i
]) = 0;
219 htab_empty (cselib_hash_table
);
221 n_useless_values
= 0;
223 next_unknown_value
= 0;
225 first_containing_mem
= &dummy_val
;
228 /* The equality test for our hash table. The first argument ENTRY is a table
229 element (i.e. a cselib_val), while the second arg X is an rtx. We know
230 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
231 CONST of an appropriate mode. */
234 entry_and_rtx_equal_p (const void *entry
, const void *x_arg
)
236 struct elt_loc_list
*l
;
237 const cselib_val
*v
= (const cselib_val
*) entry
;
239 enum machine_mode mode
= GET_MODE (x
);
241 gcc_assert (GET_CODE (x
) != CONST_INT
242 && (mode
!= VOIDmode
|| GET_CODE (x
) != CONST_DOUBLE
));
244 if (mode
!= GET_MODE (v
->val_rtx
))
247 /* Unwrap X if necessary. */
248 if (GET_CODE (x
) == CONST
249 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
250 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
253 /* We don't guarantee that distinct rtx's have different hash values,
254 so we need to do a comparison. */
255 for (l
= v
->locs
; l
; l
= l
->next
)
256 if (rtx_equal_for_cselib_p (l
->loc
, x
))
262 /* The hash function for our hash table. The value is always computed with
263 cselib_hash_rtx when adding an element; this function just extracts the
264 hash value from a cselib_val structure. */
267 get_value_hash (const void *entry
)
269 const cselib_val
*v
= (const cselib_val
*) entry
;
273 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
274 only return true for values which point to a cselib_val whose value
275 element has been set to zero, which implies the cselib_val will be
279 references_value_p (rtx x
, int only_useless
)
281 enum rtx_code code
= GET_CODE (x
);
282 const char *fmt
= GET_RTX_FORMAT (code
);
285 if (GET_CODE (x
) == VALUE
286 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
289 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
291 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
293 else if (fmt
[i
] == 'E')
294 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
295 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
302 /* For all locations found in X, delete locations that reference useless
303 values (i.e. values without any location). Called through
307 discard_useless_locs (void **x
, void *info ATTRIBUTE_UNUSED
)
309 cselib_val
*v
= (cselib_val
*)*x
;
310 struct elt_loc_list
**p
= &v
->locs
;
311 int had_locs
= v
->locs
!= 0;
315 if (references_value_p ((*p
)->loc
, 1))
316 unchain_one_elt_loc_list (p
);
321 if (had_locs
&& v
->locs
== 0)
324 values_became_useless
= 1;
329 /* If X is a value with no locations, remove it from the hashtable. */
332 discard_useless_values (void **x
, void *info ATTRIBUTE_UNUSED
)
334 cselib_val
*v
= (cselib_val
*)*x
;
338 if (cselib_discard_hook
)
339 cselib_discard_hook (v
);
341 CSELIB_VAL_PTR (v
->val_rtx
) = NULL
;
342 htab_clear_slot (cselib_hash_table
, x
);
343 unchain_one_value (v
);
350 /* Clean out useless values (i.e. those which no longer have locations
351 associated with them) from the hash table. */
354 remove_useless_values (void)
357 /* First pass: eliminate locations that reference the value. That in
358 turn can make more values useless. */
361 values_became_useless
= 0;
362 htab_traverse (cselib_hash_table
, discard_useless_locs
, 0);
364 while (values_became_useless
);
366 /* Second pass: actually remove the values. */
368 p
= &first_containing_mem
;
369 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
373 p
= &(*p
)->next_containing_mem
;
377 htab_traverse (cselib_hash_table
, discard_useless_values
, 0);
379 gcc_assert (!n_useless_values
);
382 /* Return the mode in which a register was last set. If X is not a
383 register, return its mode. If the mode in which the register was
384 set is not known, or the value was already clobbered, return
388 cselib_reg_set_mode (rtx x
)
393 if (REG_VALUES (REGNO (x
)) == NULL
394 || REG_VALUES (REGNO (x
))->elt
== NULL
)
397 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->val_rtx
);
400 /* Return nonzero if we can prove that X and Y contain the same value, taking
401 our gathered information into account. */
404 rtx_equal_for_cselib_p (rtx x
, rtx y
)
410 if (REG_P (x
) || MEM_P (x
))
412 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
418 if (REG_P (y
) || MEM_P (y
))
420 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
429 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
430 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
432 if (GET_CODE (x
) == VALUE
)
434 cselib_val
*e
= CSELIB_VAL_PTR (x
);
435 struct elt_loc_list
*l
;
437 for (l
= e
->locs
; l
; l
= l
->next
)
441 /* Avoid infinite recursion. */
442 if (REG_P (t
) || MEM_P (t
))
444 else if (rtx_equal_for_cselib_p (t
, y
))
451 if (GET_CODE (y
) == VALUE
)
453 cselib_val
*e
= CSELIB_VAL_PTR (y
);
454 struct elt_loc_list
*l
;
456 for (l
= e
->locs
; l
; l
= l
->next
)
460 if (REG_P (t
) || MEM_P (t
))
462 else if (rtx_equal_for_cselib_p (x
, t
))
469 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
472 /* These won't be handled correctly by the code below. */
473 switch (GET_CODE (x
))
479 return XEXP (x
, 0) == XEXP (y
, 0);
486 fmt
= GET_RTX_FORMAT (code
);
488 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
495 if (XWINT (x
, i
) != XWINT (y
, i
))
501 if (XINT (x
, i
) != XINT (y
, i
))
507 /* Two vectors must have the same length. */
508 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
511 /* And the corresponding elements must match. */
512 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
513 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
520 && targetm
.commutative_p (x
, UNKNOWN
)
521 && rtx_equal_for_cselib_p (XEXP (x
, 1), XEXP (y
, 0))
522 && rtx_equal_for_cselib_p (XEXP (x
, 0), XEXP (y
, 1)))
524 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
530 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
535 /* These are just backpointers, so they don't matter. */
542 /* It is believed that rtx's at this level will never
543 contain anything but integers and other rtx's,
544 except for within LABEL_REFs and SYMBOL_REFs. */
552 /* We need to pass down the mode of constants through the hash table
553 functions. For that purpose, wrap them in a CONST of the appropriate
556 wrap_constant (enum machine_mode mode
, rtx x
)
558 if (GET_CODE (x
) != CONST_INT
559 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
561 gcc_assert (mode
!= VOIDmode
);
562 return gen_rtx_CONST (mode
, x
);
565 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
566 For registers and memory locations, we look up their cselib_val structure
567 and return its VALUE element.
568 Possible reasons for return 0 are: the object is volatile, or we couldn't
569 find a register or memory location in the table and CREATE is zero. If
570 CREATE is nonzero, table elts are created for regs and mem.
571 N.B. this hash function returns the same hash value for RTXes that
572 differ only in the order of operands, thus it is suitable for comparisons
573 that take commutativity into account.
574 If we wanted to also support associative rules, we'd have to use a different
575 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
576 We used to have a MODE argument for hashing for CONST_INTs, but that
577 didn't make sense, since it caused spurious hash differences between
578 (set (reg:SI 1) (const_int))
579 (plus:SI (reg:SI 2) (reg:SI 1))
581 (plus:SI (reg:SI 2) (const_int))
582 If the mode is important in any context, it must be checked specifically
583 in a comparison anyway, since relying on hash differences is unsafe. */
586 cselib_hash_rtx (rtx x
, int create
)
592 unsigned int hash
= 0;
595 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
601 e
= cselib_lookup (x
, GET_MODE (x
), create
);
608 hash
+= ((unsigned) CONST_INT
<< 7) + INTVAL (x
);
609 return hash
? hash
: (unsigned int) CONST_INT
;
612 /* This is like the general case, except that it only counts
613 the integers representing the constant. */
614 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
615 if (GET_MODE (x
) != VOIDmode
)
616 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
618 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
619 + (unsigned) CONST_DOUBLE_HIGH (x
));
620 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
627 units
= CONST_VECTOR_NUNITS (x
);
629 for (i
= 0; i
< units
; ++i
)
631 elt
= CONST_VECTOR_ELT (x
, i
);
632 hash
+= cselib_hash_rtx (elt
, 0);
638 /* Assume there is only one rtx object for any given label. */
640 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
641 differences and differences between each stage's debugging dumps. */
642 hash
+= (((unsigned int) LABEL_REF
<< 7)
643 + CODE_LABEL_NUMBER (XEXP (x
, 0)));
644 return hash
? hash
: (unsigned int) LABEL_REF
;
648 /* Don't hash on the symbol's address to avoid bootstrap differences.
649 Different hash values may cause expressions to be recorded in
650 different orders and thus different registers to be used in the
651 final assembler. This also avoids differences in the dump files
652 between various stages. */
654 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
657 h
+= (h
<< 7) + *p
++; /* ??? revisit */
659 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
660 return hash
? hash
: (unsigned int) SYMBOL_REF
;
672 case UNSPEC_VOLATILE
:
676 if (MEM_VOLATILE_P (x
))
685 i
= GET_RTX_LENGTH (code
) - 1;
686 fmt
= GET_RTX_FORMAT (code
);
693 rtx tem
= XEXP (x
, i
);
694 unsigned int tem_hash
= cselib_hash_rtx (tem
, create
);
703 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
705 unsigned int tem_hash
706 = cselib_hash_rtx (XVECEXP (x
, i
, j
), create
);
717 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
739 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
742 /* Create a new value structure for VALUE and initialize it. The mode of the
745 static inline cselib_val
*
746 new_cselib_val (unsigned int value
, enum machine_mode mode
)
748 cselib_val
*e
= pool_alloc (cselib_val_pool
);
753 /* We use an alloc pool to allocate this RTL construct because it
754 accounts for about 8% of the overall memory usage. We know
755 precisely when we can have VALUE RTXen (when cselib is active)
756 so we don't need to put them in garbage collected memory.
757 ??? Why should a VALUE be an RTX in the first place? */
758 e
->val_rtx
= pool_alloc (value_pool
);
759 memset (e
->val_rtx
, 0, RTX_HDR_SIZE
);
760 PUT_CODE (e
->val_rtx
, VALUE
);
761 PUT_MODE (e
->val_rtx
, mode
);
762 CSELIB_VAL_PTR (e
->val_rtx
) = e
;
765 e
->next_containing_mem
= 0;
769 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
770 contains the data at this address. X is a MEM that represents the
771 value. Update the two value structures to represent this situation. */
774 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
776 struct elt_loc_list
*l
;
778 /* Avoid duplicates. */
779 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
781 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
784 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
786 = new_elt_loc_list (mem_elt
->locs
,
787 replace_equiv_address_nv (x
, addr_elt
->val_rtx
));
788 if (mem_elt
->next_containing_mem
== NULL
)
790 mem_elt
->next_containing_mem
= first_containing_mem
;
791 first_containing_mem
= mem_elt
;
795 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
796 If CREATE, make a new one if we haven't seen it before. */
799 cselib_lookup_mem (rtx x
, int create
)
801 enum machine_mode mode
= GET_MODE (x
);
807 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
808 || !cselib_record_memory
809 || (FLOAT_MODE_P (mode
) && flag_float_store
))
812 /* Look up the value for the address. */
813 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
817 /* Find a value that describes a value of our mode at that address. */
818 for (l
= addr
->addr_list
; l
; l
= l
->next
)
819 if (GET_MODE (l
->elt
->val_rtx
) == mode
)
825 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
826 add_mem_for_addr (addr
, mem_elt
, x
);
827 slot
= htab_find_slot_with_hash (cselib_hash_table
, wrap_constant (mode
, x
),
828 mem_elt
->value
, INSERT
);
833 /* Search thru the possible substitutions in P. We prefer a non reg
834 substitution because this allows us to expand the tree further. If
835 we find, just a reg, take the lowest regno. There may be several
836 non-reg results, we just take the first one because they will all
837 expand to the same place. */
840 expand_loc (struct elt_loc_list
*p
, bitmap regs_active
, int max_depth
)
842 rtx reg_result
= NULL
;
843 unsigned int regno
= UINT_MAX
;
844 struct elt_loc_list
*p_in
= p
;
846 for (; p
; p
= p
-> next
)
848 /* Avoid infinite recursion trying to expand a reg into a
851 && (REGNO (p
->loc
) < regno
)
852 && !bitmap_bit_p (regs_active
, REGNO (p
->loc
)))
855 regno
= REGNO (p
->loc
);
857 /* Avoid infinite recursion and do not try to expand the
859 else if (GET_CODE (p
->loc
) == VALUE
860 && CSELIB_VAL_PTR (p
->loc
)->locs
== p_in
)
862 else if (!REG_P (p
->loc
))
867 print_inline_rtx (dump_file
, p
->loc
, 0);
868 fprintf (dump_file
, "\n");
870 result
= cselib_expand_value_rtx (p
->loc
, regs_active
, max_depth
- 1);
877 if (regno
!= UINT_MAX
)
881 fprintf (dump_file
, "r%d\n", regno
);
883 result
= cselib_expand_value_rtx (reg_result
, regs_active
, max_depth
- 1);
892 print_inline_rtx (dump_file
, reg_result
, 0);
893 fprintf (dump_file
, "\n");
896 fprintf (dump_file
, "NULL\n");
902 /* Forward substitute and expand an expression out to its roots.
903 This is the opposite of common subexpression. Because local value
904 numbering is such a weak optimization, the expanded expression is
905 pretty much unique (not from a pointer equals point of view but
906 from a tree shape point of view.
908 This function returns NULL if the expansion fails. The expansion
909 will fail if there is no value number for one of the operands or if
910 one of the operands has been overwritten between the current insn
911 and the beginning of the basic block. For instance x has no
917 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
918 It is clear on return. */
921 cselib_expand_value_rtx (rtx orig
, bitmap regs_active
, int max_depth
)
926 const char *format_ptr
;
928 code
= GET_CODE (orig
);
930 /* For the context of dse, if we end up expand into a huge tree, we
931 will not have a useful address, so we might as well just give up
940 struct elt_list
*l
= REG_VALUES (REGNO (orig
));
942 if (l
&& l
->elt
== NULL
)
944 for (; l
; l
= l
->next
)
945 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (orig
))
948 int regno
= REGNO (orig
);
950 /* The only thing that we are not willing to do (this
951 is requirement of dse and if others potiential uses
952 need this function we should add a parm to control
953 it) is that we will not substitute the
954 STACK_POINTER_REGNUM, FRAME_POINTER or the
957 Thses expansions confuses the code that notices that
958 stores into the frame go dead at the end of the
959 function and that the frame is not effected by calls
960 to subroutines. If you allow the
961 STACK_POINTER_REGNUM substitution, then dse will
962 think that parameter pushing also goes dead which is
963 wrong. If you allow the FRAME_POINTER or the
964 HARD_FRAME_POINTER then you lose the opportunity to
965 make the frame assumptions. */
966 if (regno
== STACK_POINTER_REGNUM
967 || regno
== FRAME_POINTER_REGNUM
968 || regno
== HARD_FRAME_POINTER_REGNUM
)
971 bitmap_set_bit (regs_active
, regno
);
974 fprintf (dump_file
, "expanding: r%d into: ", regno
);
976 result
= expand_loc (l
->elt
->locs
, regs_active
, max_depth
);
977 bitmap_clear_bit (regs_active
, regno
);
994 /* SCRATCH must be shared because they represent distinct values. */
997 if (REG_P (XEXP (orig
, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig
, 0))))
1002 if (shared_const_p (orig
))
1011 fprintf (dump_file
, "expanding value %s into: ", GET_MODE_NAME (GET_MODE (orig
)));
1013 result
= expand_loc (CSELIB_VAL_PTR (orig
)->locs
, regs_active
, max_depth
);
1015 && GET_CODE (result
) == CONST_INT
1016 && GET_MODE (orig
) != VOIDmode
)
1018 result
= gen_rtx_CONST (GET_MODE (orig
), result
);
1020 fprintf (dump_file
, " wrapping const_int result in const to preserve mode %s\n",
1021 GET_MODE_NAME (GET_MODE (orig
)));
1029 /* Copy the various flags, fields, and other information. We assume
1030 that all fields need copying, and then clear the fields that should
1031 not be copied. That is the sensible default behavior, and forces
1032 us to explicitly document why we are *not* copying a flag. */
1033 copy
= shallow_copy_rtx (orig
);
1035 format_ptr
= GET_RTX_FORMAT (GET_CODE (copy
));
1037 for (i
= 0; i
< GET_RTX_LENGTH (GET_CODE (copy
)); i
++)
1038 switch (*format_ptr
++)
1041 if (XEXP (orig
, i
) != NULL
)
1043 rtx result
= cselib_expand_value_rtx (XEXP (orig
, i
), regs_active
, max_depth
- 1);
1046 XEXP (copy
, i
) = result
;
1052 if (XVEC (orig
, i
) != NULL
)
1054 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (orig
, i
));
1055 for (j
= 0; j
< XVECLEN (copy
, i
); j
++)
1057 rtx result
= cselib_expand_value_rtx (XVECEXP (orig
, i
, j
), regs_active
, max_depth
- 1);
1060 XVECEXP (copy
, i
, j
) = result
;
1074 /* These are left unchanged. */
1081 scopy
= simplify_rtx (copy
);
1087 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1088 with VALUE expressions. This way, it becomes independent of changes
1089 to registers and memory.
1090 X isn't actually modified; if modifications are needed, new rtl is
1091 allocated. However, the return value can share rtl with X. */
1094 cselib_subst_to_values (rtx x
)
1096 enum rtx_code code
= GET_CODE (x
);
1097 const char *fmt
= GET_RTX_FORMAT (code
);
1106 l
= REG_VALUES (REGNO (x
));
1107 if (l
&& l
->elt
== NULL
)
1109 for (; l
; l
= l
->next
)
1110 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (x
))
1111 return l
->elt
->val_rtx
;
1116 e
= cselib_lookup_mem (x
, 0);
1119 /* This happens for autoincrements. Assign a value that doesn't
1121 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
1136 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
1143 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1147 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
1149 if (t
!= XEXP (x
, i
) && x
== copy
)
1150 copy
= shallow_copy_rtx (x
);
1154 else if (fmt
[i
] == 'E')
1158 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1160 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
1162 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
1165 copy
= shallow_copy_rtx (x
);
1167 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
1168 for (k
= 0; k
< j
; k
++)
1169 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
1172 XVECEXP (copy
, i
, j
) = t
;
1180 /* Look up the rtl expression X in our tables and return the value it has.
1181 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1182 we create a new one if possible, using mode MODE if X doesn't have a mode
1183 (i.e. because it's a constant). */
1186 cselib_lookup (rtx x
, enum machine_mode mode
, int create
)
1190 unsigned int hashval
;
1192 if (GET_MODE (x
) != VOIDmode
)
1193 mode
= GET_MODE (x
);
1195 if (GET_CODE (x
) == VALUE
)
1196 return CSELIB_VAL_PTR (x
);
1201 unsigned int i
= REGNO (x
);
1204 if (l
&& l
->elt
== NULL
)
1206 for (; l
; l
= l
->next
)
1207 if (mode
== GET_MODE (l
->elt
->val_rtx
))
1213 if (i
< FIRST_PSEUDO_REGISTER
)
1215 unsigned int n
= hard_regno_nregs
[i
][mode
];
1217 if (n
> max_value_regs
)
1221 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
1222 e
->locs
= new_elt_loc_list (e
->locs
, x
);
1223 if (REG_VALUES (i
) == 0)
1225 /* Maintain the invariant that the first entry of
1226 REG_VALUES, if present, must be the value used to set the
1227 register, or NULL. */
1228 used_regs
[n_used_regs
++] = i
;
1229 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
1231 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
1232 slot
= htab_find_slot_with_hash (cselib_hash_table
, x
, e
->value
, INSERT
);
1238 return cselib_lookup_mem (x
, create
);
1240 hashval
= cselib_hash_rtx (x
, create
);
1241 /* Can't even create if hashing is not possible. */
1245 slot
= htab_find_slot_with_hash (cselib_hash_table
, wrap_constant (mode
, x
),
1246 hashval
, create
? INSERT
: NO_INSERT
);
1250 e
= (cselib_val
*) *slot
;
1254 e
= new_cselib_val (hashval
, mode
);
1256 /* We have to fill the slot before calling cselib_subst_to_values:
1257 the hash table is inconsistent until we do so, and
1258 cselib_subst_to_values will need to do lookups. */
1260 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
1264 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1265 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1266 is used to determine how many hard registers are being changed. If MODE
1267 is VOIDmode, then only REGNO is being changed; this is used when
1268 invalidating call clobbered registers across a call. */
1271 cselib_invalidate_regno (unsigned int regno
, enum machine_mode mode
)
1273 unsigned int endregno
;
1276 /* If we see pseudos after reload, something is _wrong_. */
1277 gcc_assert (!reload_completed
|| regno
< FIRST_PSEUDO_REGISTER
1278 || reg_renumber
[regno
] < 0);
1280 /* Determine the range of registers that must be invalidated. For
1281 pseudos, only REGNO is affected. For hard regs, we must take MODE
1282 into account, and we must also invalidate lower register numbers
1283 if they contain values that overlap REGNO. */
1284 if (regno
< FIRST_PSEUDO_REGISTER
)
1286 gcc_assert (mode
!= VOIDmode
);
1288 if (regno
< max_value_regs
)
1291 i
= regno
- max_value_regs
;
1293 endregno
= end_hard_regno (mode
, regno
);
1298 endregno
= regno
+ 1;
1301 for (; i
< endregno
; i
++)
1303 struct elt_list
**l
= ®_VALUES (i
);
1305 /* Go through all known values for this reg; if it overlaps the range
1306 we're invalidating, remove the value. */
1309 cselib_val
*v
= (*l
)->elt
;
1310 struct elt_loc_list
**p
;
1311 unsigned int this_last
= i
;
1313 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
1314 this_last
= end_hard_regno (GET_MODE (v
->val_rtx
), i
) - 1;
1316 if (this_last
< regno
|| v
== NULL
)
1322 /* We have an overlap. */
1323 if (*l
== REG_VALUES (i
))
1325 /* Maintain the invariant that the first entry of
1326 REG_VALUES, if present, must be the value used to set
1327 the register, or NULL. This is also nice because
1328 then we won't push the same regno onto user_regs
1334 unchain_one_elt_list (l
);
1336 /* Now, we clear the mapping from value to reg. It must exist, so
1337 this code will crash intentionally if it doesn't. */
1338 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
1342 if (REG_P (x
) && REGNO (x
) == i
)
1344 unchain_one_elt_loc_list (p
);
1354 /* Return 1 if X has a value that can vary even between two
1355 executions of the program. 0 means X can be compared reliably
1356 against certain constants or near-constants. */
1359 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED
, int from_alias ATTRIBUTE_UNUSED
)
1361 /* We actually don't need to verify very hard. This is because
1362 if X has actually changed, we invalidate the memory anyway,
1363 so assume that all common memory addresses are
1368 /* Invalidate any locations in the table which are changed because of a
1369 store to MEM_RTX. If this is called because of a non-const call
1370 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1373 cselib_invalidate_mem (rtx mem_rtx
)
1375 cselib_val
**vp
, *v
, *next
;
1379 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
1380 mem_rtx
= canon_rtx (mem_rtx
);
1382 vp
= &first_containing_mem
;
1383 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
1385 bool has_mem
= false;
1386 struct elt_loc_list
**p
= &v
->locs
;
1387 int had_locs
= v
->locs
!= 0;
1393 struct elt_list
**mem_chain
;
1395 /* MEMs may occur in locations only at the top level; below
1396 that every MEM or REG is substituted by its VALUE. */
1402 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
1403 && ! canon_true_dependence (mem_rtx
, GET_MODE (mem_rtx
), mem_addr
,
1404 x
, cselib_rtx_varies_p
))
1412 /* This one overlaps. */
1413 /* We must have a mapping from this MEM's address to the
1414 value (E). Remove that, too. */
1415 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1416 mem_chain
= &addr
->addr_list
;
1419 if ((*mem_chain
)->elt
== v
)
1421 unchain_one_elt_list (mem_chain
);
1425 mem_chain
= &(*mem_chain
)->next
;
1428 unchain_one_elt_loc_list (p
);
1431 if (had_locs
&& v
->locs
== 0)
1434 next
= v
->next_containing_mem
;
1438 vp
= &(*vp
)->next_containing_mem
;
1441 v
->next_containing_mem
= NULL
;
1446 /* Invalidate DEST, which is being assigned to or clobbered. */
1449 cselib_invalidate_rtx (rtx dest
)
1451 while (GET_CODE (dest
) == SUBREG
1452 || GET_CODE (dest
) == ZERO_EXTRACT
1453 || GET_CODE (dest
) == STRICT_LOW_PART
)
1454 dest
= XEXP (dest
, 0);
1457 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1458 else if (MEM_P (dest
))
1459 cselib_invalidate_mem (dest
);
1461 /* Some machines don't define AUTO_INC_DEC, but they still use push
1462 instructions. We need to catch that case here in order to
1463 invalidate the stack pointer correctly. Note that invalidating
1464 the stack pointer is different from invalidating DEST. */
1465 if (push_operand (dest
, GET_MODE (dest
)))
1466 cselib_invalidate_rtx (stack_pointer_rtx
);
1469 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1472 cselib_invalidate_rtx_note_stores (rtx dest
, rtx ignore ATTRIBUTE_UNUSED
,
1473 void *data ATTRIBUTE_UNUSED
)
1475 cselib_invalidate_rtx (dest
);
1478 /* Record the result of a SET instruction. DEST is being set; the source
1479 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1480 describes its address. */
1483 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
1485 int dreg
= REG_P (dest
) ? (int) REGNO (dest
) : -1;
1487 if (src_elt
== 0 || side_effects_p (dest
))
1492 if (dreg
< FIRST_PSEUDO_REGISTER
)
1494 unsigned int n
= hard_regno_nregs
[dreg
][GET_MODE (dest
)];
1496 if (n
> max_value_regs
)
1500 if (REG_VALUES (dreg
) == 0)
1502 used_regs
[n_used_regs
++] = dreg
;
1503 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1507 /* The register should have been invalidated. */
1508 gcc_assert (REG_VALUES (dreg
)->elt
== 0);
1509 REG_VALUES (dreg
)->elt
= src_elt
;
1512 if (src_elt
->locs
== 0)
1514 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1516 else if (MEM_P (dest
) && dest_addr_elt
!= 0
1517 && cselib_record_memory
)
1519 if (src_elt
->locs
== 0)
1521 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1525 /* Describe a single set that is part of an insn. */
1530 cselib_val
*src_elt
;
1531 cselib_val
*dest_addr_elt
;
1534 /* There is no good way to determine how many elements there can be
1535 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1536 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1538 /* Record the effects of any sets in INSN. */
1540 cselib_record_sets (rtx insn
)
1544 struct set sets
[MAX_SETS
];
1545 rtx body
= PATTERN (insn
);
1548 body
= PATTERN (insn
);
1549 if (GET_CODE (body
) == COND_EXEC
)
1551 cond
= COND_EXEC_TEST (body
);
1552 body
= COND_EXEC_CODE (body
);
1555 /* Find all sets. */
1556 if (GET_CODE (body
) == SET
)
1558 sets
[0].src
= SET_SRC (body
);
1559 sets
[0].dest
= SET_DEST (body
);
1562 else if (GET_CODE (body
) == PARALLEL
)
1564 /* Look through the PARALLEL and record the values being
1565 set, if possible. Also handle any CLOBBERs. */
1566 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1568 rtx x
= XVECEXP (body
, 0, i
);
1570 if (GET_CODE (x
) == SET
)
1572 sets
[n_sets
].src
= SET_SRC (x
);
1573 sets
[n_sets
].dest
= SET_DEST (x
);
1579 /* Look up the values that are read. Do this before invalidating the
1580 locations that are written. */
1581 for (i
= 0; i
< n_sets
; i
++)
1583 rtx dest
= sets
[i
].dest
;
1585 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1586 the low part after invalidating any knowledge about larger modes. */
1587 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1588 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1590 /* We don't know how to record anything but REG or MEM. */
1592 || (MEM_P (dest
) && cselib_record_memory
))
1594 rtx src
= sets
[i
].src
;
1596 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (src
), cond
, src
, dest
);
1597 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1);
1599 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1601 sets
[i
].dest_addr_elt
= 0;
1605 /* Invalidate all locations written by this insn. Note that the elts we
1606 looked up in the previous loop aren't affected, just some of their
1607 locations may go away. */
1608 note_stores (body
, cselib_invalidate_rtx_note_stores
, NULL
);
1610 /* If this is an asm, look for duplicate sets. This can happen when the
1611 user uses the same value as an output multiple times. This is valid
1612 if the outputs are not actually used thereafter. Treat this case as
1613 if the value isn't actually set. We do this by smashing the destination
1614 to pc_rtx, so that we won't record the value later. */
1615 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
1617 for (i
= 0; i
< n_sets
; i
++)
1619 rtx dest
= sets
[i
].dest
;
1620 if (REG_P (dest
) || MEM_P (dest
))
1623 for (j
= i
+ 1; j
< n_sets
; j
++)
1624 if (rtx_equal_p (dest
, sets
[j
].dest
))
1626 sets
[i
].dest
= pc_rtx
;
1627 sets
[j
].dest
= pc_rtx
;
1633 /* Now enter the equivalences in our tables. */
1634 for (i
= 0; i
< n_sets
; i
++)
1636 rtx dest
= sets
[i
].dest
;
1638 || (MEM_P (dest
) && cselib_record_memory
))
1639 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1643 /* Record the effects of INSN. */
1646 cselib_process_insn (rtx insn
)
1651 if (find_reg_note (insn
, REG_LIBCALL
, NULL
))
1652 cselib_current_insn_in_libcall
= true;
1653 cselib_current_insn
= insn
;
1655 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1658 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1659 || (NONJUMP_INSN_P (insn
)
1660 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1661 && MEM_VOLATILE_P (PATTERN (insn
))))
1663 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1664 cselib_current_insn_in_libcall
= false;
1665 cselib_clear_table ();
1669 if (! INSN_P (insn
))
1671 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1672 cselib_current_insn_in_libcall
= false;
1673 cselib_current_insn
= 0;
1677 /* If this is a call instruction, forget anything stored in a
1678 call clobbered register, or, if this is not a const call, in
1682 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1683 if (call_used_regs
[i
]
1684 || (REG_VALUES (i
) && REG_VALUES (i
)->elt
1685 && HARD_REGNO_CALL_PART_CLOBBERED (i
,
1686 GET_MODE (REG_VALUES (i
)->elt
->val_rtx
))))
1687 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
1689 if (! CONST_OR_PURE_CALL_P (insn
))
1690 cselib_invalidate_mem (callmem
);
1693 cselib_record_sets (insn
);
1696 /* Clobber any registers which appear in REG_INC notes. We
1697 could keep track of the changes to their values, but it is
1698 unlikely to help. */
1699 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1700 if (REG_NOTE_KIND (x
) == REG_INC
)
1701 cselib_invalidate_rtx (XEXP (x
, 0));
1704 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1705 after we have processed the insn. */
1707 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1708 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1709 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0));
1711 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1712 cselib_current_insn_in_libcall
= false;
1713 cselib_current_insn
= 0;
1715 if (n_useless_values
> MAX_USELESS_VALUES
1716 /* remove_useless_values is linear in the hash table size. Avoid
1717 quadratic behavior for very large hashtables with very few
1718 useless elements. */
1719 && (unsigned int)n_useless_values
> cselib_hash_table
->n_elements
/ 4)
1720 remove_useless_values ();
1723 /* Initialize cselib for one pass. The caller must also call
1724 init_alias_analysis. */
1727 cselib_init (bool record_memory
)
1729 elt_list_pool
= create_alloc_pool ("elt_list",
1730 sizeof (struct elt_list
), 10);
1731 elt_loc_list_pool
= create_alloc_pool ("elt_loc_list",
1732 sizeof (struct elt_loc_list
), 10);
1733 cselib_val_pool
= create_alloc_pool ("cselib_val_list",
1734 sizeof (cselib_val
), 10);
1735 value_pool
= create_alloc_pool ("value", RTX_CODE_SIZE (VALUE
), 100);
1736 cselib_record_memory
= record_memory
;
1738 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
1739 see canon_true_dependence. This is only created once. */
1741 callmem
= gen_rtx_MEM (BLKmode
, gen_rtx_SCRATCH (VOIDmode
));
1743 cselib_nregs
= max_reg_num ();
1745 /* We preserve reg_values to allow expensive clearing of the whole thing.
1746 Reallocate it however if it happens to be too large. */
1747 if (!reg_values
|| reg_values_size
< cselib_nregs
1748 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
1752 /* Some space for newly emit instructions so we don't end up
1753 reallocating in between passes. */
1754 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
1755 reg_values
= XCNEWVEC (struct elt_list
*, reg_values_size
);
1757 used_regs
= XNEWVEC (unsigned int, cselib_nregs
);
1759 cselib_hash_table
= htab_create (31, get_value_hash
,
1760 entry_and_rtx_equal_p
, NULL
);
1761 cselib_current_insn_in_libcall
= false;
1764 /* Called when the current user is done with cselib. */
1767 cselib_finish (void)
1769 cselib_discard_hook
= NULL
;
1770 free_alloc_pool (elt_list_pool
);
1771 free_alloc_pool (elt_loc_list_pool
);
1772 free_alloc_pool (cselib_val_pool
);
1773 free_alloc_pool (value_pool
);
1774 cselib_clear_table ();
1775 htab_delete (cselib_hash_table
);
1778 cselib_hash_table
= 0;
1779 n_useless_values
= 0;
1780 next_unknown_value
= 0;
1783 #include "gt-cselib.h"