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 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"
44 static int entry_and_rtx_equal_p (const void *, const void *);
45 static hashval_t
get_value_hash (const void *);
46 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
47 static struct elt_loc_list
*new_elt_loc_list (struct elt_loc_list
*, rtx
);
48 static void unchain_one_value (cselib_val
*);
49 static void unchain_one_elt_list (struct elt_list
**);
50 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
51 static void clear_table (void);
52 static int discard_useless_locs (void **, void *);
53 static int discard_useless_values (void **, void *);
54 static void remove_useless_values (void);
55 static rtx
wrap_constant (enum machine_mode
, rtx
);
56 static unsigned int hash_rtx (rtx
, enum machine_mode
, int);
57 static cselib_val
*new_cselib_val (unsigned int, enum machine_mode
);
58 static void add_mem_for_addr (cselib_val
*, cselib_val
*, rtx
);
59 static cselib_val
*cselib_lookup_mem (rtx
, int);
60 static void cselib_invalidate_regno (unsigned int, enum machine_mode
);
61 static void cselib_invalidate_mem (rtx
);
62 static void cselib_invalidate_rtx (rtx
, rtx
, void *);
63 static void cselib_record_set (rtx
, cselib_val
*, cselib_val
*);
64 static void cselib_record_sets (rtx
);
66 /* There are three ways in which cselib can look up an rtx:
67 - for a REG, the reg_values table (which is indexed by regno) is used
68 - for a MEM, we recursively look up its address and then follow the
69 addr_list of that value
70 - for everything else, we compute a hash value and go through the hash
71 table. Since different rtx's can still have the same hash value,
72 this involves walking the table entries for a given value and comparing
73 the locations of the entries with the rtx we are looking up. */
75 /* A table that enables us to look up elts by their value. */
76 static GTY((param_is (cselib_val
))) htab_t hash_table
;
78 /* This is a global so we don't have to pass this through every function.
79 It is used in new_elt_loc_list to set SETTING_INSN. */
80 static rtx cselib_current_insn
;
81 static bool cselib_current_insn_in_libcall
;
83 /* Every new unknown value gets a unique number. */
84 static unsigned int next_unknown_value
;
86 /* The number of registers we had when the varrays were last resized. */
87 static unsigned int cselib_nregs
;
89 /* Count values without known locations. Whenever this grows too big, we
90 remove these useless values from the table. */
91 static int n_useless_values
;
93 /* Number of useless values before we remove them from the hash table. */
94 #define MAX_USELESS_VALUES 32
96 /* This table maps from register number to values. It does not
97 contain pointers to cselib_val structures, but rather elt_lists.
98 The purpose is to be able to refer to the same register in
99 different modes. The first element of the list defines the mode in
100 which the register was set; if the mode is unknown or the value is
101 no longer valid in that mode, ELT will be NULL for the first
103 static GTY(()) varray_type reg_values
;
104 static GTY((deletable (""))) varray_type reg_values_old
;
105 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
107 /* The largest number of hard regs used by any entry added to the
108 REG_VALUES table. Cleared on each clear_table() invocation. */
109 static unsigned int max_value_regs
;
111 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
112 in clear_table() for fast emptying. */
113 static GTY(()) varray_type used_regs
;
114 static GTY((deletable (""))) varray_type used_regs_old
;
116 /* We pass this to cselib_invalidate_mem to invalidate all of
117 memory for a non-const call instruction. */
118 static GTY(()) rtx callmem
;
120 /* Caches for unused structures. */
121 static GTY((deletable (""))) cselib_val
*empty_vals
;
122 static GTY((deletable (""))) struct elt_list
*empty_elt_lists
;
123 static GTY((deletable (""))) struct elt_loc_list
*empty_elt_loc_lists
;
125 /* Set by discard_useless_locs if it deleted the last location of any
127 static int values_became_useless
;
129 /* Used as stop element of the containing_mem list so we can check
130 presence in the list by checking the next pointer. */
131 static cselib_val dummy_val
;
133 /* Used to list all values that contain memory reference.
134 May or may not contain the useless values - the list is compacted
135 each time memory is invalidated. */
136 static cselib_val
*first_containing_mem
= &dummy_val
;
139 /* Allocate a struct elt_list and fill in its two elements with the
142 static struct elt_list
*
143 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
145 struct elt_list
*el
= empty_elt_lists
;
148 empty_elt_lists
= el
->next
;
150 el
= ggc_alloc (sizeof (struct elt_list
));
156 /* Allocate a struct elt_loc_list and fill in its two elements with the
159 static struct elt_loc_list
*
160 new_elt_loc_list (struct elt_loc_list
*next
, rtx loc
)
162 struct elt_loc_list
*el
= empty_elt_loc_lists
;
165 empty_elt_loc_lists
= el
->next
;
167 el
= ggc_alloc (sizeof (struct elt_loc_list
));
170 el
->canon_loc
= NULL
;
171 el
->setting_insn
= cselib_current_insn
;
172 el
->in_libcall
= cselib_current_insn_in_libcall
;
176 /* The elt_list at *PL is no longer needed. Unchain it and free its
180 unchain_one_elt_list (struct elt_list
**pl
)
182 struct elt_list
*l
= *pl
;
185 l
->next
= empty_elt_lists
;
189 /* Likewise for elt_loc_lists. */
192 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
194 struct elt_loc_list
*l
= *pl
;
197 l
->next
= empty_elt_loc_lists
;
198 empty_elt_loc_lists
= l
;
201 /* Likewise for cselib_vals. This also frees the addr_list associated with
205 unchain_one_value (cselib_val
*v
)
208 unchain_one_elt_list (&v
->addr_list
);
210 v
->u
.next_free
= empty_vals
;
214 /* Remove all entries from the hash table. Also used during
215 initialization. If CLEAR_ALL isn't set, then only clear the entries
216 which are known to have been used. */
223 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (used_regs
); i
++)
224 REG_VALUES (VARRAY_UINT (used_regs
, i
)) = 0;
228 VARRAY_POP_ALL (used_regs
);
230 htab_empty (hash_table
);
232 n_useless_values
= 0;
234 next_unknown_value
= 0;
236 first_containing_mem
= &dummy_val
;
239 /* The equality test for our hash table. The first argument ENTRY is a table
240 element (i.e. a cselib_val), while the second arg X is an rtx. We know
241 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
242 CONST of an appropriate mode. */
245 entry_and_rtx_equal_p (const void *entry
, const void *x_arg
)
247 struct elt_loc_list
*l
;
248 const cselib_val
*v
= (const cselib_val
*) entry
;
250 enum machine_mode mode
= GET_MODE (x
);
252 if (GET_CODE (x
) == CONST_INT
253 || (mode
== VOIDmode
&& GET_CODE (x
) == CONST_DOUBLE
))
255 if (mode
!= GET_MODE (v
->u
.val_rtx
))
258 /* Unwrap X if necessary. */
259 if (GET_CODE (x
) == CONST
260 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
261 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
264 /* We don't guarantee that distinct rtx's have different hash values,
265 so we need to do a comparison. */
266 for (l
= v
->locs
; l
; l
= l
->next
)
267 if (rtx_equal_for_cselib_p (l
->loc
, x
))
273 /* The hash function for our hash table. The value is always computed with
274 hash_rtx when adding an element; this function just extracts the hash
275 value from a cselib_val structure. */
278 get_value_hash (const void *entry
)
280 const cselib_val
*v
= (const cselib_val
*) entry
;
284 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
285 only return true for values which point to a cselib_val whose value
286 element has been set to zero, which implies the cselib_val will be
290 references_value_p (rtx x
, int only_useless
)
292 enum rtx_code code
= GET_CODE (x
);
293 const char *fmt
= GET_RTX_FORMAT (code
);
296 if (GET_CODE (x
) == VALUE
297 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
300 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
302 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
304 else if (fmt
[i
] == 'E')
305 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
306 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
313 /* For all locations found in X, delete locations that reference useless
314 values (i.e. values without any location). Called through
318 discard_useless_locs (void **x
, void *info ATTRIBUTE_UNUSED
)
320 cselib_val
*v
= (cselib_val
*)*x
;
321 struct elt_loc_list
**p
= &v
->locs
;
322 int had_locs
= v
->locs
!= 0;
326 if (references_value_p ((*p
)->loc
, 1))
327 unchain_one_elt_loc_list (p
);
332 if (had_locs
&& v
->locs
== 0)
335 values_became_useless
= 1;
340 /* If X is a value with no locations, remove it from the hashtable. */
343 discard_useless_values (void **x
, void *info ATTRIBUTE_UNUSED
)
345 cselib_val
*v
= (cselib_val
*)*x
;
349 htab_clear_slot (hash_table
, x
);
350 unchain_one_value (v
);
357 /* Clean out useless values (i.e. those which no longer have locations
358 associated with them) from the hash table. */
361 remove_useless_values (void)
364 /* First pass: eliminate locations that reference the value. That in
365 turn can make more values useless. */
368 values_became_useless
= 0;
369 htab_traverse (hash_table
, discard_useless_locs
, 0);
371 while (values_became_useless
);
373 /* Second pass: actually remove the values. */
374 htab_traverse (hash_table
, discard_useless_values
, 0);
376 p
= &first_containing_mem
;
377 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
381 p
= &(*p
)->next_containing_mem
;
385 if (n_useless_values
!= 0)
389 /* Return the mode in which a register was last set. If X is not a
390 register, return its mode. If the mode in which the register was
391 set is not known, or the value was already clobbered, return
395 cselib_reg_set_mode (rtx x
)
397 if (GET_CODE (x
) != REG
)
400 if (REG_VALUES (REGNO (x
)) == NULL
401 || REG_VALUES (REGNO (x
))->elt
== NULL
)
404 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->u
.val_rtx
);
407 /* Return nonzero if we can prove that X and Y contain the same value, taking
408 our gathered information into account. */
411 rtx_equal_for_cselib_p (rtx x
, rtx y
)
417 if (GET_CODE (x
) == REG
|| GET_CODE (x
) == MEM
)
419 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
425 if (GET_CODE (y
) == REG
|| GET_CODE (y
) == MEM
)
427 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
436 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
437 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
439 if (GET_CODE (x
) == VALUE
)
441 cselib_val
*e
= CSELIB_VAL_PTR (x
);
442 struct elt_loc_list
*l
;
444 for (l
= e
->locs
; l
; l
= l
->next
)
448 /* Avoid infinite recursion. */
449 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
451 else if (rtx_equal_for_cselib_p (t
, y
))
458 if (GET_CODE (y
) == VALUE
)
460 cselib_val
*e
= CSELIB_VAL_PTR (y
);
461 struct elt_loc_list
*l
;
463 for (l
= e
->locs
; l
; l
= l
->next
)
467 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
469 else if (rtx_equal_for_cselib_p (x
, t
))
476 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
479 /* This won't be handled correctly by the code below. */
480 if (GET_CODE (x
) == LABEL_REF
)
481 return XEXP (x
, 0) == XEXP (y
, 0);
484 fmt
= GET_RTX_FORMAT (code
);
486 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
493 if (XWINT (x
, i
) != XWINT (y
, i
))
499 if (XINT (x
, i
) != XINT (y
, i
))
505 /* Two vectors must have the same length. */
506 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
509 /* And the corresponding elements must match. */
510 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
511 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
517 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
523 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
528 /* These are just backpointers, so they don't matter. */
535 /* It is believed that rtx's at this level will never
536 contain anything but integers and other rtx's,
537 except for within LABEL_REFs and SYMBOL_REFs. */
545 /* We need to pass down the mode of constants through the hash table
546 functions. For that purpose, wrap them in a CONST of the appropriate
549 wrap_constant (enum machine_mode mode
, rtx x
)
551 if (GET_CODE (x
) != CONST_INT
552 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
554 if (mode
== VOIDmode
)
556 return gen_rtx_CONST (mode
, x
);
559 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
560 For registers and memory locations, we look up their cselib_val structure
561 and return its VALUE element.
562 Possible reasons for return 0 are: the object is volatile, or we couldn't
563 find a register or memory location in the table and CREATE is zero. If
564 CREATE is nonzero, table elts are created for regs and mem.
565 MODE is used in hashing for CONST_INTs only;
566 otherwise the mode of X is used. */
569 hash_rtx (rtx x
, enum machine_mode mode
, int create
)
575 unsigned int hash
= 0;
578 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
584 e
= cselib_lookup (x
, GET_MODE (x
), create
);
591 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
592 return hash
? hash
: (unsigned int) CONST_INT
;
595 /* This is like the general case, except that it only counts
596 the integers representing the constant. */
597 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
598 if (GET_MODE (x
) != VOIDmode
)
599 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
601 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
602 + (unsigned) CONST_DOUBLE_HIGH (x
));
603 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
610 units
= CONST_VECTOR_NUNITS (x
);
612 for (i
= 0; i
< units
; ++i
)
614 elt
= CONST_VECTOR_ELT (x
, i
);
615 hash
+= hash_rtx (elt
, GET_MODE (elt
), 0);
621 /* Assume there is only one rtx object for any given label. */
624 += ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
625 return hash
? hash
: (unsigned int) LABEL_REF
;
629 += ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
630 return hash
? hash
: (unsigned int) SYMBOL_REF
;
641 case UNSPEC_VOLATILE
:
645 if (MEM_VOLATILE_P (x
))
654 i
= GET_RTX_LENGTH (code
) - 1;
655 fmt
= GET_RTX_FORMAT (code
);
660 rtx tem
= XEXP (x
, i
);
661 unsigned int tem_hash
= hash_rtx (tem
, 0, create
);
668 else if (fmt
[i
] == 'E')
669 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
671 unsigned int tem_hash
= hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
678 else if (fmt
[i
] == 's')
680 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
686 else if (fmt
[i
] == 'i')
688 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
694 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
697 /* Create a new value structure for VALUE and initialize it. The mode of the
701 new_cselib_val (unsigned int value
, enum machine_mode mode
)
703 cselib_val
*e
= empty_vals
;
706 empty_vals
= e
->u
.next_free
;
708 e
= ggc_alloc (sizeof (cselib_val
));
714 e
->u
.val_rtx
= gen_rtx_VALUE (mode
);
715 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
718 e
->next_containing_mem
= 0;
722 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
723 contains the data at this address. X is a MEM that represents the
724 value. Update the two value structures to represent this situation. */
727 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
729 struct elt_loc_list
*l
;
731 /* Avoid duplicates. */
732 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
733 if (GET_CODE (l
->loc
) == MEM
734 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
737 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
739 = new_elt_loc_list (mem_elt
->locs
,
740 replace_equiv_address_nv (x
, addr_elt
->u
.val_rtx
));
741 if (mem_elt
->next_containing_mem
== NULL
)
743 mem_elt
->next_containing_mem
= first_containing_mem
;
744 first_containing_mem
= mem_elt
;
748 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
749 If CREATE, make a new one if we haven't seen it before. */
752 cselib_lookup_mem (rtx x
, int create
)
754 enum machine_mode mode
= GET_MODE (x
);
760 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
761 || (FLOAT_MODE_P (mode
) && flag_float_store
))
764 /* Look up the value for the address. */
765 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
769 /* Find a value that describes a value of our mode at that address. */
770 for (l
= addr
->addr_list
; l
; l
= l
->next
)
771 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
777 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
778 add_mem_for_addr (addr
, mem_elt
, x
);
779 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
780 mem_elt
->value
, INSERT
);
785 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
786 with VALUE expressions. This way, it becomes independent of changes
787 to registers and memory.
788 X isn't actually modified; if modifications are needed, new rtl is
789 allocated. However, the return value can share rtl with X. */
792 cselib_subst_to_values (rtx x
)
794 enum rtx_code code
= GET_CODE (x
);
795 const char *fmt
= GET_RTX_FORMAT (code
);
804 l
= REG_VALUES (REGNO (x
));
805 if (l
&& l
->elt
== NULL
)
807 for (; l
; l
= l
->next
)
808 if (GET_MODE (l
->elt
->u
.val_rtx
) == GET_MODE (x
))
809 return l
->elt
->u
.val_rtx
;
814 e
= cselib_lookup_mem (x
, 0);
817 /* This happens for autoincrements. Assign a value that doesn't
819 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
834 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
841 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
845 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
847 if (t
!= XEXP (x
, i
) && x
== copy
)
848 copy
= shallow_copy_rtx (x
);
852 else if (fmt
[i
] == 'E')
856 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
858 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
860 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
863 copy
= shallow_copy_rtx (x
);
865 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
866 for (k
= 0; k
< j
; k
++)
867 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
870 XVECEXP (copy
, i
, j
) = t
;
878 /* Look up the rtl expression X in our tables and return the value it has.
879 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
880 we create a new one if possible, using mode MODE if X doesn't have a mode
881 (i.e. because it's a constant). */
884 cselib_lookup (rtx x
, enum machine_mode mode
, int create
)
888 unsigned int hashval
;
890 if (GET_MODE (x
) != VOIDmode
)
893 if (GET_CODE (x
) == VALUE
)
894 return CSELIB_VAL_PTR (x
);
896 if (GET_CODE (x
) == REG
)
899 unsigned int i
= REGNO (x
);
902 if (l
&& l
->elt
== NULL
)
904 for (; l
; l
= l
->next
)
905 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
911 if (i
< FIRST_PSEUDO_REGISTER
)
913 unsigned int n
= HARD_REGNO_NREGS (i
, mode
);
915 if (n
> max_value_regs
)
919 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
920 e
->locs
= new_elt_loc_list (e
->locs
, x
);
921 if (REG_VALUES (i
) == 0)
923 /* Maintain the invariant that the first entry of
924 REG_VALUES, if present, must be the value used to set the
925 register, or NULL. */
926 VARRAY_PUSH_UINT (used_regs
, i
);
927 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
929 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
930 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
935 if (GET_CODE (x
) == MEM
)
936 return cselib_lookup_mem (x
, create
);
938 hashval
= hash_rtx (x
, mode
, create
);
939 /* Can't even create if hashing is not possible. */
943 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
944 hashval
, create
? INSERT
: NO_INSERT
);
948 e
= (cselib_val
*) *slot
;
952 e
= new_cselib_val (hashval
, mode
);
954 /* We have to fill the slot before calling cselib_subst_to_values:
955 the hash table is inconsistent until we do so, and
956 cselib_subst_to_values will need to do lookups. */
958 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
962 /* Invalidate any entries in reg_values that overlap REGNO. This is called
963 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
964 is used to determine how many hard registers are being changed. If MODE
965 is VOIDmode, then only REGNO is being changed; this is used when
966 invalidating call clobbered registers across a call. */
969 cselib_invalidate_regno (unsigned int regno
, enum machine_mode mode
)
971 unsigned int endregno
;
974 /* If we see pseudos after reload, something is _wrong_. */
975 if (reload_completed
&& regno
>= FIRST_PSEUDO_REGISTER
976 && reg_renumber
[regno
] >= 0)
979 /* Determine the range of registers that must be invalidated. For
980 pseudos, only REGNO is affected. For hard regs, we must take MODE
981 into account, and we must also invalidate lower register numbers
982 if they contain values that overlap REGNO. */
983 if (regno
< FIRST_PSEUDO_REGISTER
)
985 if (mode
== VOIDmode
)
988 if (regno
< max_value_regs
)
991 i
= regno
- max_value_regs
;
993 endregno
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
998 endregno
= regno
+ 1;
1001 for (; i
< endregno
; i
++)
1003 struct elt_list
**l
= ®_VALUES (i
);
1005 /* Go through all known values for this reg; if it overlaps the range
1006 we're invalidating, remove the value. */
1009 cselib_val
*v
= (*l
)->elt
;
1010 struct elt_loc_list
**p
;
1011 unsigned int this_last
= i
;
1013 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
1014 this_last
+= HARD_REGNO_NREGS (i
, GET_MODE (v
->u
.val_rtx
)) - 1;
1016 if (this_last
< regno
|| v
== NULL
)
1022 /* We have an overlap. */
1023 if (*l
== REG_VALUES (i
))
1025 /* Maintain the invariant that the first entry of
1026 REG_VALUES, if present, must be the value used to set
1027 the register, or NULL. This is also nice because
1028 then we won't push the same regno onto user_regs
1034 unchain_one_elt_list (l
);
1036 /* Now, we clear the mapping from value to reg. It must exist, so
1037 this code will crash intentionally if it doesn't. */
1038 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
1042 if (GET_CODE (x
) == REG
&& REGNO (x
) == i
)
1044 unchain_one_elt_loc_list (p
);
1054 /* Return 1 if X has a value that can vary even between two
1055 executions of the program. 0 means X can be compared reliably
1056 against certain constants or near-constants. */
1059 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED
, int from_alias ATTRIBUTE_UNUSED
)
1061 /* We actually don't need to verify very hard. This is because
1062 if X has actually changed, we invalidate the memory anyway,
1063 so assume that all common memory addresses are
1068 /* Invalidate any locations in the table which are changed because of a
1069 store to MEM_RTX. If this is called because of a non-const call
1070 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1073 cselib_invalidate_mem (rtx mem_rtx
)
1075 cselib_val
**vp
, *v
, *next
;
1079 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
1080 mem_rtx
= canon_rtx (mem_rtx
);
1082 vp
= &first_containing_mem
;
1083 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
1085 bool has_mem
= false;
1086 struct elt_loc_list
**p
= &v
->locs
;
1087 int had_locs
= v
->locs
!= 0;
1092 rtx canon_x
= (*p
)->canon_loc
;
1094 struct elt_list
**mem_chain
;
1096 /* MEMs may occur in locations only at the top level; below
1097 that every MEM or REG is substituted by its VALUE. */
1098 if (GET_CODE (x
) != MEM
)
1104 canon_x
= (*p
)->canon_loc
= canon_rtx (x
);
1105 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
1106 && ! canon_true_dependence (mem_rtx
, GET_MODE (mem_rtx
), mem_addr
,
1107 x
, cselib_rtx_varies_p
))
1115 /* This one overlaps. */
1116 /* We must have a mapping from this MEM's address to the
1117 value (E). Remove that, too. */
1118 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1119 mem_chain
= &addr
->addr_list
;
1122 if ((*mem_chain
)->elt
== v
)
1124 unchain_one_elt_list (mem_chain
);
1128 mem_chain
= &(*mem_chain
)->next
;
1131 unchain_one_elt_loc_list (p
);
1134 if (had_locs
&& v
->locs
== 0)
1137 next
= v
->next_containing_mem
;
1141 vp
= &(*vp
)->next_containing_mem
;
1144 v
->next_containing_mem
= NULL
;
1149 /* Invalidate DEST, which is being assigned to or clobbered. The second and
1150 the third parameter exist so that this function can be passed to
1151 note_stores; they are ignored. */
1154 cselib_invalidate_rtx (rtx dest
, rtx ignore ATTRIBUTE_UNUSED
,
1155 void *data ATTRIBUTE_UNUSED
)
1157 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SIGN_EXTRACT
1158 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
)
1159 dest
= XEXP (dest
, 0);
1161 if (GET_CODE (dest
) == REG
)
1162 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1163 else if (GET_CODE (dest
) == MEM
)
1164 cselib_invalidate_mem (dest
);
1166 /* Some machines don't define AUTO_INC_DEC, but they still use push
1167 instructions. We need to catch that case here in order to
1168 invalidate the stack pointer correctly. Note that invalidating
1169 the stack pointer is different from invalidating DEST. */
1170 if (push_operand (dest
, GET_MODE (dest
)))
1171 cselib_invalidate_rtx (stack_pointer_rtx
, NULL_RTX
, NULL
);
1174 /* Record the result of a SET instruction. DEST is being set; the source
1175 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1176 describes its address. */
1179 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
1181 int dreg
= GET_CODE (dest
) == REG
? (int) REGNO (dest
) : -1;
1183 if (src_elt
== 0 || side_effects_p (dest
))
1188 if (dreg
< FIRST_PSEUDO_REGISTER
)
1190 unsigned int n
= HARD_REGNO_NREGS (dreg
, GET_MODE (dest
));
1192 if (n
> max_value_regs
)
1196 if (REG_VALUES (dreg
) == 0)
1198 VARRAY_PUSH_UINT (used_regs
, dreg
);
1199 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1203 if (REG_VALUES (dreg
)->elt
== 0)
1204 REG_VALUES (dreg
)->elt
= src_elt
;
1206 /* The register should have been invalidated. */
1210 if (src_elt
->locs
== 0)
1212 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1214 else if (GET_CODE (dest
) == MEM
&& dest_addr_elt
!= 0)
1216 if (src_elt
->locs
== 0)
1218 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1222 /* Describe a single set that is part of an insn. */
1227 cselib_val
*src_elt
;
1228 cselib_val
*dest_addr_elt
;
1231 /* There is no good way to determine how many elements there can be
1232 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1233 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1235 /* Record the effects of any sets in INSN. */
1237 cselib_record_sets (rtx insn
)
1241 struct set sets
[MAX_SETS
];
1242 rtx body
= PATTERN (insn
);
1245 body
= PATTERN (insn
);
1246 if (GET_CODE (body
) == COND_EXEC
)
1248 cond
= COND_EXEC_TEST (body
);
1249 body
= COND_EXEC_CODE (body
);
1252 /* Find all sets. */
1253 if (GET_CODE (body
) == SET
)
1255 sets
[0].src
= SET_SRC (body
);
1256 sets
[0].dest
= SET_DEST (body
);
1259 else if (GET_CODE (body
) == PARALLEL
)
1261 /* Look through the PARALLEL and record the values being
1262 set, if possible. Also handle any CLOBBERs. */
1263 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1265 rtx x
= XVECEXP (body
, 0, i
);
1267 if (GET_CODE (x
) == SET
)
1269 sets
[n_sets
].src
= SET_SRC (x
);
1270 sets
[n_sets
].dest
= SET_DEST (x
);
1276 /* Look up the values that are read. Do this before invalidating the
1277 locations that are written. */
1278 for (i
= 0; i
< n_sets
; i
++)
1280 rtx dest
= sets
[i
].dest
;
1282 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1283 the low part after invalidating any knowledge about larger modes. */
1284 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1285 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1287 /* We don't know how to record anything but REG or MEM. */
1288 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1290 rtx src
= sets
[i
].src
;
1292 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (src
), cond
, src
, dest
);
1293 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1);
1294 if (GET_CODE (dest
) == MEM
)
1295 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1297 sets
[i
].dest_addr_elt
= 0;
1301 /* Invalidate all locations written by this insn. Note that the elts we
1302 looked up in the previous loop aren't affected, just some of their
1303 locations may go away. */
1304 note_stores (body
, cselib_invalidate_rtx
, NULL
);
1306 /* Now enter the equivalences in our tables. */
1307 for (i
= 0; i
< n_sets
; i
++)
1309 rtx dest
= sets
[i
].dest
;
1310 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1311 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1315 /* Record the effects of INSN. */
1318 cselib_process_insn (rtx insn
)
1323 if (find_reg_note (insn
, REG_LIBCALL
, NULL
))
1324 cselib_current_insn_in_libcall
= true;
1325 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1326 cselib_current_insn_in_libcall
= false;
1327 cselib_current_insn
= insn
;
1329 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1330 if (GET_CODE (insn
) == CODE_LABEL
1331 || (GET_CODE (insn
) == CALL_INSN
1332 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1333 || (GET_CODE (insn
) == INSN
1334 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1335 && MEM_VOLATILE_P (PATTERN (insn
))))
1341 if (! INSN_P (insn
))
1343 cselib_current_insn
= 0;
1347 /* If this is a call instruction, forget anything stored in a
1348 call clobbered register, or, if this is not a const call, in
1350 if (GET_CODE (insn
) == CALL_INSN
)
1352 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1353 if (call_used_regs
[i
])
1354 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
1356 if (! CONST_OR_PURE_CALL_P (insn
))
1357 cselib_invalidate_mem (callmem
);
1360 cselib_record_sets (insn
);
1363 /* Clobber any registers which appear in REG_INC notes. We
1364 could keep track of the changes to their values, but it is
1365 unlikely to help. */
1366 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1367 if (REG_NOTE_KIND (x
) == REG_INC
)
1368 cselib_invalidate_rtx (XEXP (x
, 0), NULL_RTX
, NULL
);
1371 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1372 after we have processed the insn. */
1373 if (GET_CODE (insn
) == CALL_INSN
)
1374 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1375 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1376 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0), NULL_RTX
, NULL
);
1378 cselib_current_insn
= 0;
1380 if (n_useless_values
> MAX_USELESS_VALUES
)
1381 remove_useless_values ();
1384 /* Make sure our varrays are big enough. Not called from any cselib routines;
1385 it must be called by the user if it allocated new registers. */
1388 cselib_update_varray_sizes (void)
1390 unsigned int nregs
= max_reg_num ();
1392 if (nregs
== cselib_nregs
)
1395 cselib_nregs
= nregs
;
1396 VARRAY_GROW (reg_values
, nregs
);
1397 VARRAY_GROW (used_regs
, nregs
);
1400 /* Initialize cselib for one pass. The caller must also call
1401 init_alias_analysis. */
1406 /* This is only created once. */
1408 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1410 cselib_nregs
= max_reg_num ();
1411 if (reg_values_old
!= NULL
&& VARRAY_SIZE (reg_values_old
) >= cselib_nregs
)
1413 reg_values
= reg_values_old
;
1414 used_regs
= used_regs_old
;
1418 VARRAY_ELT_LIST_INIT (reg_values
, cselib_nregs
, "reg_values");
1419 VARRAY_UINT_INIT (used_regs
, cselib_nregs
, "used_regs");
1421 hash_table
= htab_create_ggc (31, get_value_hash
, entry_and_rtx_equal_p
,
1423 cselib_current_insn_in_libcall
= false;
1426 /* Called when the current user is done with cselib. */
1429 cselib_finish (void)
1432 reg_values_old
= reg_values
;
1434 used_regs_old
= used_regs
;
1437 n_useless_values
= 0;
1438 next_unknown_value
= 0;
1441 #include "gt-cselib.h"