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 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, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
43 #include "alloc-pool.h"
45 static bool cselib_record_memory
;
46 static int entry_and_rtx_equal_p (const void *, const void *);
47 static hashval_t
get_value_hash (const void *);
48 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
49 static struct elt_loc_list
*new_elt_loc_list (struct elt_loc_list
*, rtx
);
50 static void unchain_one_value (cselib_val
*);
51 static void unchain_one_elt_list (struct elt_list
**);
52 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
53 static void clear_table (void);
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
, enum machine_mode
, 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 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 struct elt_list
**reg_values
;
105 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 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 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
;
136 /* Allocate a struct elt_list and fill in its two elements with the
139 static inline struct elt_list
*
140 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
143 el
= pool_alloc (elt_list_pool
);
149 /* Allocate a struct elt_loc_list and fill in its two elements with the
152 static inline struct elt_loc_list
*
153 new_elt_loc_list (struct elt_loc_list
*next
, rtx loc
)
155 struct elt_loc_list
*el
;
156 el
= pool_alloc (elt_loc_list_pool
);
159 el
->setting_insn
= cselib_current_insn
;
160 el
->in_libcall
= cselib_current_insn_in_libcall
;
164 /* The elt_list at *PL is no longer needed. Unchain it and free its
168 unchain_one_elt_list (struct elt_list
**pl
)
170 struct elt_list
*l
= *pl
;
173 pool_free (elt_list_pool
, l
);
176 /* Likewise for elt_loc_lists. */
179 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
181 struct elt_loc_list
*l
= *pl
;
184 pool_free (elt_loc_list_pool
, l
);
187 /* Likewise for cselib_vals. This also frees the addr_list associated with
191 unchain_one_value (cselib_val
*v
)
194 unchain_one_elt_list (&v
->addr_list
);
196 pool_free (cselib_val_pool
, v
);
199 /* Remove all entries from the hash table. Also used during
200 initialization. If CLEAR_ALL isn't set, then only clear the entries
201 which are known to have been used. */
208 for (i
= 0; i
< n_used_regs
; i
++)
209 REG_VALUES (used_regs
[i
]) = 0;
215 htab_empty (hash_table
);
217 n_useless_values
= 0;
219 next_unknown_value
= 0;
221 first_containing_mem
= &dummy_val
;
224 /* The equality test for our hash table. The first argument ENTRY is a table
225 element (i.e. a cselib_val), while the second arg X is an rtx. We know
226 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
227 CONST of an appropriate mode. */
230 entry_and_rtx_equal_p (const void *entry
, const void *x_arg
)
232 struct elt_loc_list
*l
;
233 const cselib_val
*v
= (const cselib_val
*) entry
;
235 enum machine_mode mode
= GET_MODE (x
);
237 gcc_assert (GET_CODE (x
) != CONST_INT
238 && (mode
!= VOIDmode
|| GET_CODE (x
) != CONST_DOUBLE
));
240 if (mode
!= GET_MODE (v
->u
.val_rtx
))
243 /* Unwrap X if necessary. */
244 if (GET_CODE (x
) == CONST
245 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
246 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
249 /* We don't guarantee that distinct rtx's have different hash values,
250 so we need to do a comparison. */
251 for (l
= v
->locs
; l
; l
= l
->next
)
252 if (rtx_equal_for_cselib_p (l
->loc
, x
))
258 /* The hash function for our hash table. The value is always computed with
259 cselib_hash_rtx when adding an element; this function just extracts the
260 hash value from a cselib_val structure. */
263 get_value_hash (const void *entry
)
265 const cselib_val
*v
= (const cselib_val
*) entry
;
269 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
270 only return true for values which point to a cselib_val whose value
271 element has been set to zero, which implies the cselib_val will be
275 references_value_p (rtx x
, int only_useless
)
277 enum rtx_code code
= GET_CODE (x
);
278 const char *fmt
= GET_RTX_FORMAT (code
);
281 if (GET_CODE (x
) == VALUE
282 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
285 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
287 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
289 else if (fmt
[i
] == 'E')
290 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
291 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
298 /* For all locations found in X, delete locations that reference useless
299 values (i.e. values without any location). Called through
303 discard_useless_locs (void **x
, void *info ATTRIBUTE_UNUSED
)
305 cselib_val
*v
= (cselib_val
*)*x
;
306 struct elt_loc_list
**p
= &v
->locs
;
307 int had_locs
= v
->locs
!= 0;
311 if (references_value_p ((*p
)->loc
, 1))
312 unchain_one_elt_loc_list (p
);
317 if (had_locs
&& v
->locs
== 0)
320 values_became_useless
= 1;
325 /* If X is a value with no locations, remove it from the hashtable. */
328 discard_useless_values (void **x
, void *info ATTRIBUTE_UNUSED
)
330 cselib_val
*v
= (cselib_val
*)*x
;
334 CSELIB_VAL_PTR (v
->u
.val_rtx
) = NULL
;
335 htab_clear_slot (hash_table
, x
);
336 unchain_one_value (v
);
343 /* Clean out useless values (i.e. those which no longer have locations
344 associated with them) from the hash table. */
347 remove_useless_values (void)
350 /* First pass: eliminate locations that reference the value. That in
351 turn can make more values useless. */
354 values_became_useless
= 0;
355 htab_traverse (hash_table
, discard_useless_locs
, 0);
357 while (values_became_useless
);
359 /* Second pass: actually remove the values. */
361 p
= &first_containing_mem
;
362 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
366 p
= &(*p
)->next_containing_mem
;
370 htab_traverse (hash_table
, discard_useless_values
, 0);
372 gcc_assert (!n_useless_values
);
375 /* Return the mode in which a register was last set. If X is not a
376 register, return its mode. If the mode in which the register was
377 set is not known, or the value was already clobbered, return
381 cselib_reg_set_mode (rtx x
)
386 if (REG_VALUES (REGNO (x
)) == NULL
387 || REG_VALUES (REGNO (x
))->elt
== NULL
)
390 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->u
.val_rtx
);
393 /* Return nonzero if we can prove that X and Y contain the same value, taking
394 our gathered information into account. */
397 rtx_equal_for_cselib_p (rtx x
, rtx y
)
403 if (REG_P (x
) || MEM_P (x
))
405 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
411 if (REG_P (y
) || MEM_P (y
))
413 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
422 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
423 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
425 if (GET_CODE (x
) == VALUE
)
427 cselib_val
*e
= CSELIB_VAL_PTR (x
);
428 struct elt_loc_list
*l
;
430 for (l
= e
->locs
; l
; l
= l
->next
)
434 /* Avoid infinite recursion. */
435 if (REG_P (t
) || MEM_P (t
))
437 else if (rtx_equal_for_cselib_p (t
, y
))
444 if (GET_CODE (y
) == VALUE
)
446 cselib_val
*e
= CSELIB_VAL_PTR (y
);
447 struct elt_loc_list
*l
;
449 for (l
= e
->locs
; l
; l
= l
->next
)
453 if (REG_P (t
) || MEM_P (t
))
455 else if (rtx_equal_for_cselib_p (x
, t
))
462 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
465 /* This won't be handled correctly by the code below. */
466 if (GET_CODE (x
) == LABEL_REF
)
467 return XEXP (x
, 0) == XEXP (y
, 0);
470 fmt
= GET_RTX_FORMAT (code
);
472 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
479 if (XWINT (x
, i
) != XWINT (y
, i
))
485 if (XINT (x
, i
) != XINT (y
, i
))
491 /* Two vectors must have the same length. */
492 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
495 /* And the corresponding elements must match. */
496 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
497 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
503 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
509 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
514 /* These are just backpointers, so they don't matter. */
521 /* It is believed that rtx's at this level will never
522 contain anything but integers and other rtx's,
523 except for within LABEL_REFs and SYMBOL_REFs. */
531 /* We need to pass down the mode of constants through the hash table
532 functions. For that purpose, wrap them in a CONST of the appropriate
535 wrap_constant (enum machine_mode mode
, rtx x
)
537 if (GET_CODE (x
) != CONST_INT
538 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
540 gcc_assert (mode
!= VOIDmode
);
541 return gen_rtx_CONST (mode
, x
);
544 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
545 For registers and memory locations, we look up their cselib_val structure
546 and return its VALUE element.
547 Possible reasons for return 0 are: the object is volatile, or we couldn't
548 find a register or memory location in the table and CREATE is zero. If
549 CREATE is nonzero, table elts are created for regs and mem.
550 MODE is used in hashing for CONST_INTs only;
551 otherwise the mode of X is used. */
554 cselib_hash_rtx (rtx x
, enum machine_mode mode
, int create
)
560 unsigned int hash
= 0;
563 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
569 e
= cselib_lookup (x
, GET_MODE (x
), create
);
576 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
577 return hash
? hash
: (unsigned int) CONST_INT
;
580 /* This is like the general case, except that it only counts
581 the integers representing the constant. */
582 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
583 if (GET_MODE (x
) != VOIDmode
)
584 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
586 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
587 + (unsigned) CONST_DOUBLE_HIGH (x
));
588 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
595 units
= CONST_VECTOR_NUNITS (x
);
597 for (i
= 0; i
< units
; ++i
)
599 elt
= CONST_VECTOR_ELT (x
, i
);
600 hash
+= cselib_hash_rtx (elt
, GET_MODE (elt
), 0);
606 /* Assume there is only one rtx object for any given label. */
608 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
609 differences and differences between each stage's debugging dumps. */
610 hash
+= (((unsigned int) LABEL_REF
<< 7)
611 + CODE_LABEL_NUMBER (XEXP (x
, 0)));
612 return hash
? hash
: (unsigned int) LABEL_REF
;
616 /* Don't hash on the symbol's address to avoid bootstrap differences.
617 Different hash values may cause expressions to be recorded in
618 different orders and thus different registers to be used in the
619 final assembler. This also avoids differences in the dump files
620 between various stages. */
622 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
625 h
+= (h
<< 7) + *p
++; /* ??? revisit */
627 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
628 return hash
? hash
: (unsigned int) SYMBOL_REF
;
640 case UNSPEC_VOLATILE
:
644 if (MEM_VOLATILE_P (x
))
653 i
= GET_RTX_LENGTH (code
) - 1;
654 fmt
= GET_RTX_FORMAT (code
);
661 rtx tem
= XEXP (x
, i
);
662 unsigned int tem_hash
= cselib_hash_rtx (tem
, 0, create
);
671 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
673 unsigned int tem_hash
674 = cselib_hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
685 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
707 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
710 /* Create a new value structure for VALUE and initialize it. The mode of the
713 static inline cselib_val
*
714 new_cselib_val (unsigned int value
, enum machine_mode mode
)
716 cselib_val
*e
= pool_alloc (cselib_val_pool
);
721 /* We use an alloc pool to allocate this RTL construct because it
722 accounts for about 8% of the overall memory usage. We know
723 precisely when we can have VALUE RTXen (when cselib is active)
724 so we don't need to put them in garbage collected memory.
725 ??? Why should a VALUE be an RTX in the first place? */
726 e
->u
.val_rtx
= pool_alloc (value_pool
);
727 memset (e
->u
.val_rtx
, 0, RTX_HDR_SIZE
);
728 PUT_CODE (e
->u
.val_rtx
, VALUE
);
729 PUT_MODE (e
->u
.val_rtx
, mode
);
730 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
733 e
->next_containing_mem
= 0;
737 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
738 contains the data at this address. X is a MEM that represents the
739 value. Update the two value structures to represent this situation. */
742 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
744 struct elt_loc_list
*l
;
746 /* Avoid duplicates. */
747 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
749 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
752 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
754 = new_elt_loc_list (mem_elt
->locs
,
755 replace_equiv_address_nv (x
, addr_elt
->u
.val_rtx
));
756 if (mem_elt
->next_containing_mem
== NULL
)
758 mem_elt
->next_containing_mem
= first_containing_mem
;
759 first_containing_mem
= mem_elt
;
763 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
764 If CREATE, make a new one if we haven't seen it before. */
767 cselib_lookup_mem (rtx x
, int create
)
769 enum machine_mode mode
= GET_MODE (x
);
775 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
776 || !cselib_record_memory
777 || (FLOAT_MODE_P (mode
) && flag_float_store
))
780 /* Look up the value for the address. */
781 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
785 /* Find a value that describes a value of our mode at that address. */
786 for (l
= addr
->addr_list
; l
; l
= l
->next
)
787 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
793 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
794 add_mem_for_addr (addr
, mem_elt
, x
);
795 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
796 mem_elt
->value
, INSERT
);
801 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
802 with VALUE expressions. This way, it becomes independent of changes
803 to registers and memory.
804 X isn't actually modified; if modifications are needed, new rtl is
805 allocated. However, the return value can share rtl with X. */
808 cselib_subst_to_values (rtx x
)
810 enum rtx_code code
= GET_CODE (x
);
811 const char *fmt
= GET_RTX_FORMAT (code
);
820 l
= REG_VALUES (REGNO (x
));
821 if (l
&& l
->elt
== NULL
)
823 for (; l
; l
= l
->next
)
824 if (GET_MODE (l
->elt
->u
.val_rtx
) == GET_MODE (x
))
825 return l
->elt
->u
.val_rtx
;
830 e
= cselib_lookup_mem (x
, 0);
833 /* This happens for autoincrements. Assign a value that doesn't
835 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
850 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
857 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
861 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
863 if (t
!= XEXP (x
, i
) && x
== copy
)
864 copy
= shallow_copy_rtx (x
);
868 else if (fmt
[i
] == 'E')
872 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
874 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
876 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
879 copy
= shallow_copy_rtx (x
);
881 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
882 for (k
= 0; k
< j
; k
++)
883 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
886 XVECEXP (copy
, i
, j
) = t
;
894 /* Look up the rtl expression X in our tables and return the value it has.
895 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
896 we create a new one if possible, using mode MODE if X doesn't have a mode
897 (i.e. because it's a constant). */
900 cselib_lookup (rtx x
, enum machine_mode mode
, int create
)
904 unsigned int hashval
;
906 if (GET_MODE (x
) != VOIDmode
)
909 if (GET_CODE (x
) == VALUE
)
910 return CSELIB_VAL_PTR (x
);
915 unsigned int i
= REGNO (x
);
918 if (l
&& l
->elt
== NULL
)
920 for (; l
; l
= l
->next
)
921 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
927 if (i
< FIRST_PSEUDO_REGISTER
)
929 unsigned int n
= hard_regno_nregs
[i
][mode
];
931 if (n
> max_value_regs
)
935 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
936 e
->locs
= new_elt_loc_list (e
->locs
, x
);
937 if (REG_VALUES (i
) == 0)
939 /* Maintain the invariant that the first entry of
940 REG_VALUES, if present, must be the value used to set the
941 register, or NULL. */
942 used_regs
[n_used_regs
++] = i
;
943 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
945 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
946 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
952 return cselib_lookup_mem (x
, create
);
954 hashval
= cselib_hash_rtx (x
, mode
, create
);
955 /* Can't even create if hashing is not possible. */
959 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
960 hashval
, create
? INSERT
: NO_INSERT
);
964 e
= (cselib_val
*) *slot
;
968 e
= new_cselib_val (hashval
, mode
);
970 /* We have to fill the slot before calling cselib_subst_to_values:
971 the hash table is inconsistent until we do so, and
972 cselib_subst_to_values will need to do lookups. */
974 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
978 /* Invalidate any entries in reg_values that overlap REGNO. This is called
979 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
980 is used to determine how many hard registers are being changed. If MODE
981 is VOIDmode, then only REGNO is being changed; this is used when
982 invalidating call clobbered registers across a call. */
985 cselib_invalidate_regno (unsigned int regno
, enum machine_mode mode
)
987 unsigned int endregno
;
990 /* If we see pseudos after reload, something is _wrong_. */
991 gcc_assert (!reload_completed
|| regno
< FIRST_PSEUDO_REGISTER
992 || reg_renumber
[regno
] < 0);
994 /* Determine the range of registers that must be invalidated. For
995 pseudos, only REGNO is affected. For hard regs, we must take MODE
996 into account, and we must also invalidate lower register numbers
997 if they contain values that overlap REGNO. */
998 if (regno
< FIRST_PSEUDO_REGISTER
)
1000 gcc_assert (mode
!= VOIDmode
);
1002 if (regno
< max_value_regs
)
1005 i
= regno
- max_value_regs
;
1007 endregno
= regno
+ hard_regno_nregs
[regno
][mode
];
1012 endregno
= regno
+ 1;
1015 for (; i
< endregno
; i
++)
1017 struct elt_list
**l
= ®_VALUES (i
);
1019 /* Go through all known values for this reg; if it overlaps the range
1020 we're invalidating, remove the value. */
1023 cselib_val
*v
= (*l
)->elt
;
1024 struct elt_loc_list
**p
;
1025 unsigned int this_last
= i
;
1027 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
1028 this_last
+= hard_regno_nregs
[i
][GET_MODE (v
->u
.val_rtx
)] - 1;
1030 if (this_last
< regno
|| v
== NULL
)
1036 /* We have an overlap. */
1037 if (*l
== REG_VALUES (i
))
1039 /* Maintain the invariant that the first entry of
1040 REG_VALUES, if present, must be the value used to set
1041 the register, or NULL. This is also nice because
1042 then we won't push the same regno onto user_regs
1048 unchain_one_elt_list (l
);
1050 /* Now, we clear the mapping from value to reg. It must exist, so
1051 this code will crash intentionally if it doesn't. */
1052 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
1056 if (REG_P (x
) && REGNO (x
) == i
)
1058 unchain_one_elt_loc_list (p
);
1068 /* Return 1 if X has a value that can vary even between two
1069 executions of the program. 0 means X can be compared reliably
1070 against certain constants or near-constants. */
1073 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED
, int from_alias ATTRIBUTE_UNUSED
)
1075 /* We actually don't need to verify very hard. This is because
1076 if X has actually changed, we invalidate the memory anyway,
1077 so assume that all common memory addresses are
1082 /* Invalidate any locations in the table which are changed because of a
1083 store to MEM_RTX. If this is called because of a non-const call
1084 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1087 cselib_invalidate_mem (rtx mem_rtx
)
1089 cselib_val
**vp
, *v
, *next
;
1093 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
1094 mem_rtx
= canon_rtx (mem_rtx
);
1096 vp
= &first_containing_mem
;
1097 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
1099 bool has_mem
= false;
1100 struct elt_loc_list
**p
= &v
->locs
;
1101 int had_locs
= v
->locs
!= 0;
1107 struct elt_list
**mem_chain
;
1109 /* MEMs may occur in locations only at the top level; below
1110 that every MEM or REG is substituted by its VALUE. */
1116 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
1117 && ! canon_true_dependence (mem_rtx
, GET_MODE (mem_rtx
), mem_addr
,
1118 x
, cselib_rtx_varies_p
))
1126 /* This one overlaps. */
1127 /* We must have a mapping from this MEM's address to the
1128 value (E). Remove that, too. */
1129 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1130 mem_chain
= &addr
->addr_list
;
1133 if ((*mem_chain
)->elt
== v
)
1135 unchain_one_elt_list (mem_chain
);
1139 mem_chain
= &(*mem_chain
)->next
;
1142 unchain_one_elt_loc_list (p
);
1145 if (had_locs
&& v
->locs
== 0)
1148 next
= v
->next_containing_mem
;
1152 vp
= &(*vp
)->next_containing_mem
;
1155 v
->next_containing_mem
= NULL
;
1160 /* Invalidate DEST, which is being assigned to or clobbered. */
1163 cselib_invalidate_rtx (rtx dest
)
1165 while (GET_CODE (dest
) == SUBREG
1166 || GET_CODE (dest
) == ZERO_EXTRACT
1167 || GET_CODE (dest
) == STRICT_LOW_PART
)
1168 dest
= XEXP (dest
, 0);
1171 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1172 else if (MEM_P (dest
))
1173 cselib_invalidate_mem (dest
);
1175 /* Some machines don't define AUTO_INC_DEC, but they still use push
1176 instructions. We need to catch that case here in order to
1177 invalidate the stack pointer correctly. Note that invalidating
1178 the stack pointer is different from invalidating DEST. */
1179 if (push_operand (dest
, GET_MODE (dest
)))
1180 cselib_invalidate_rtx (stack_pointer_rtx
);
1183 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1186 cselib_invalidate_rtx_note_stores (rtx dest
, rtx ignore ATTRIBUTE_UNUSED
,
1187 void *data ATTRIBUTE_UNUSED
)
1189 cselib_invalidate_rtx (dest
);
1192 /* Record the result of a SET instruction. DEST is being set; the source
1193 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1194 describes its address. */
1197 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
1199 int dreg
= REG_P (dest
) ? (int) REGNO (dest
) : -1;
1201 if (src_elt
== 0 || side_effects_p (dest
))
1206 if (dreg
< FIRST_PSEUDO_REGISTER
)
1208 unsigned int n
= hard_regno_nregs
[dreg
][GET_MODE (dest
)];
1210 if (n
> max_value_regs
)
1214 if (REG_VALUES (dreg
) == 0)
1216 used_regs
[n_used_regs
++] = dreg
;
1217 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1221 /* The register should have been invalidated. */
1222 gcc_assert (REG_VALUES (dreg
)->elt
== 0);
1223 REG_VALUES (dreg
)->elt
= src_elt
;
1226 if (src_elt
->locs
== 0)
1228 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1230 else if (MEM_P (dest
) && dest_addr_elt
!= 0
1231 && cselib_record_memory
)
1233 if (src_elt
->locs
== 0)
1235 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1239 /* Describe a single set that is part of an insn. */
1244 cselib_val
*src_elt
;
1245 cselib_val
*dest_addr_elt
;
1248 /* There is no good way to determine how many elements there can be
1249 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1250 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1252 /* Record the effects of any sets in INSN. */
1254 cselib_record_sets (rtx insn
)
1258 struct set sets
[MAX_SETS
];
1259 rtx body
= PATTERN (insn
);
1262 body
= PATTERN (insn
);
1263 if (GET_CODE (body
) == COND_EXEC
)
1265 cond
= COND_EXEC_TEST (body
);
1266 body
= COND_EXEC_CODE (body
);
1269 /* Find all sets. */
1270 if (GET_CODE (body
) == SET
)
1272 sets
[0].src
= SET_SRC (body
);
1273 sets
[0].dest
= SET_DEST (body
);
1276 else if (GET_CODE (body
) == PARALLEL
)
1278 /* Look through the PARALLEL and record the values being
1279 set, if possible. Also handle any CLOBBERs. */
1280 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1282 rtx x
= XVECEXP (body
, 0, i
);
1284 if (GET_CODE (x
) == SET
)
1286 sets
[n_sets
].src
= SET_SRC (x
);
1287 sets
[n_sets
].dest
= SET_DEST (x
);
1293 /* Look up the values that are read. Do this before invalidating the
1294 locations that are written. */
1295 for (i
= 0; i
< n_sets
; i
++)
1297 rtx dest
= sets
[i
].dest
;
1299 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1300 the low part after invalidating any knowledge about larger modes. */
1301 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1302 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1304 /* We don't know how to record anything but REG or MEM. */
1306 || (MEM_P (dest
) && cselib_record_memory
))
1308 rtx src
= sets
[i
].src
;
1310 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (src
), cond
, src
, dest
);
1311 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1);
1313 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1315 sets
[i
].dest_addr_elt
= 0;
1319 /* Invalidate all locations written by this insn. Note that the elts we
1320 looked up in the previous loop aren't affected, just some of their
1321 locations may go away. */
1322 note_stores (body
, cselib_invalidate_rtx_note_stores
, NULL
);
1324 /* If this is an asm, look for duplicate sets. This can happen when the
1325 user uses the same value as an output multiple times. This is valid
1326 if the outputs are not actually used thereafter. Treat this case as
1327 if the value isn't actually set. We do this by smashing the destination
1328 to pc_rtx, so that we won't record the value later. */
1329 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
1331 for (i
= 0; i
< n_sets
; i
++)
1333 rtx dest
= sets
[i
].dest
;
1334 if (REG_P (dest
) || MEM_P (dest
))
1337 for (j
= i
+ 1; j
< n_sets
; j
++)
1338 if (rtx_equal_p (dest
, sets
[j
].dest
))
1340 sets
[i
].dest
= pc_rtx
;
1341 sets
[j
].dest
= pc_rtx
;
1347 /* Now enter the equivalences in our tables. */
1348 for (i
= 0; i
< n_sets
; i
++)
1350 rtx dest
= sets
[i
].dest
;
1352 || (MEM_P (dest
) && cselib_record_memory
))
1353 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1357 /* Record the effects of INSN. */
1360 cselib_process_insn (rtx insn
)
1365 if (find_reg_note (insn
, REG_LIBCALL
, NULL
))
1366 cselib_current_insn_in_libcall
= true;
1367 cselib_current_insn
= insn
;
1369 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1372 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1373 || (NONJUMP_INSN_P (insn
)
1374 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1375 && MEM_VOLATILE_P (PATTERN (insn
))))
1377 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1378 cselib_current_insn_in_libcall
= false;
1383 if (! INSN_P (insn
))
1385 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1386 cselib_current_insn_in_libcall
= false;
1387 cselib_current_insn
= 0;
1391 /* If this is a call instruction, forget anything stored in a
1392 call clobbered register, or, if this is not a const call, in
1396 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1397 if (call_used_regs
[i
]
1398 || (REG_VALUES (i
) && REG_VALUES (i
)->elt
1399 && HARD_REGNO_CALL_PART_CLOBBERED (i
,
1400 GET_MODE (REG_VALUES (i
)->elt
->u
.val_rtx
))))
1401 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
1403 if (! CONST_OR_PURE_CALL_P (insn
))
1404 cselib_invalidate_mem (callmem
);
1407 cselib_record_sets (insn
);
1410 /* Clobber any registers which appear in REG_INC notes. We
1411 could keep track of the changes to their values, but it is
1412 unlikely to help. */
1413 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1414 if (REG_NOTE_KIND (x
) == REG_INC
)
1415 cselib_invalidate_rtx (XEXP (x
, 0));
1418 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1419 after we have processed the insn. */
1421 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1422 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1423 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0));
1425 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1426 cselib_current_insn_in_libcall
= false;
1427 cselib_current_insn
= 0;
1429 if (n_useless_values
> MAX_USELESS_VALUES
)
1430 remove_useless_values ();
1433 /* Initialize cselib for one pass. The caller must also call
1434 init_alias_analysis. */
1437 cselib_init (bool record_memory
)
1439 elt_list_pool
= create_alloc_pool ("elt_list",
1440 sizeof (struct elt_list
), 10);
1441 elt_loc_list_pool
= create_alloc_pool ("elt_loc_list",
1442 sizeof (struct elt_loc_list
), 10);
1443 cselib_val_pool
= create_alloc_pool ("cselib_val_list",
1444 sizeof (cselib_val
), 10);
1445 value_pool
= create_alloc_pool ("value",
1446 RTX_SIZE (VALUE
), 100);
1447 cselib_record_memory
= record_memory
;
1448 /* This is only created once. */
1450 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1452 cselib_nregs
= max_reg_num ();
1454 /* We preserve reg_values to allow expensive clearing of the whole thing.
1455 Reallocate it however if it happens to be too large. */
1456 if (!reg_values
|| reg_values_size
< cselib_nregs
1457 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
1461 /* Some space for newly emit instructions so we don't end up
1462 reallocating in between passes. */
1463 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
1464 reg_values
= xcalloc (reg_values_size
, sizeof (reg_values
));
1466 used_regs
= xmalloc (sizeof (*used_regs
) * cselib_nregs
);
1468 hash_table
= htab_create (31, get_value_hash
, entry_and_rtx_equal_p
, NULL
);
1469 cselib_current_insn_in_libcall
= false;
1472 /* Called when the current user is done with cselib. */
1475 cselib_finish (void)
1477 free_alloc_pool (elt_list_pool
);
1478 free_alloc_pool (elt_loc_list_pool
);
1479 free_alloc_pool (cselib_val_pool
);
1480 free_alloc_pool (value_pool
);
1482 htab_delete (hash_table
);
1486 n_useless_values
= 0;
1487 next_unknown_value
= 0;
1490 #include "gt-cselib.h"