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 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
29 #include "hard-reg-set.h"
32 #include "insn-config.h"
43 static int entry_and_rtx_equal_p
PARAMS ((const void *, const void *));
44 static unsigned int get_value_hash
PARAMS ((const void *));
45 static struct elt_list
*new_elt_list
PARAMS ((struct elt_list
*,
47 static struct elt_loc_list
*new_elt_loc_list
PARAMS ((struct elt_loc_list
*,
49 static void unchain_one_value
PARAMS ((cselib_val
*));
50 static void unchain_one_elt_list
PARAMS ((struct elt_list
**));
51 static void unchain_one_elt_loc_list
PARAMS ((struct elt_loc_list
**));
52 static void clear_table
PARAMS ((int));
53 static int discard_useless_locs
PARAMS ((void **, void *));
54 static int discard_useless_values
PARAMS ((void **, void *));
55 static void remove_useless_values
PARAMS ((void));
56 static rtx wrap_constant
PARAMS ((enum machine_mode
, rtx
));
57 static unsigned int hash_rtx
PARAMS ((rtx
, enum machine_mode
, int));
58 static cselib_val
*new_cselib_val
PARAMS ((unsigned int,
60 static void add_mem_for_addr
PARAMS ((cselib_val
*, cselib_val
*,
62 static cselib_val
*cselib_lookup_mem
PARAMS ((rtx
, int));
63 static rtx cselib_subst_to_values
PARAMS ((rtx
));
64 static void cselib_invalidate_regno
PARAMS ((unsigned int,
66 static int cselib_mem_conflict_p
PARAMS ((rtx
, rtx
));
67 static int cselib_invalidate_mem_1
PARAMS ((void **, void *));
68 static void cselib_invalidate_mem
PARAMS ((rtx
));
69 static void cselib_invalidate_rtx
PARAMS ((rtx
, rtx
, void *));
70 static void cselib_record_set
PARAMS ((rtx
, cselib_val
*,
72 static void cselib_record_sets
PARAMS ((rtx
));
74 /* There are three ways in which cselib can look up an rtx:
75 - for a REG, the reg_values table (which is indexed by regno) is used
76 - for a MEM, we recursively look up its address and then follow the
77 addr_list of that value
78 - for everything else, we compute a hash value and go through the hash
79 table. Since different rtx's can still have the same hash value,
80 this involves walking the table entries for a given value and comparing
81 the locations of the entries with the rtx we are looking up. */
83 /* A table that enables us to look up elts by their value. */
84 static htab_t hash_table
;
86 /* This is a global so we don't have to pass this through every function.
87 It is used in new_elt_loc_list to set SETTING_INSN. */
88 static rtx cselib_current_insn
;
90 /* Every new unknown value gets a unique number. */
91 static unsigned int next_unknown_value
;
93 /* The number of registers we had when the varrays were last resized. */
94 static unsigned int cselib_nregs
;
96 /* Count values without known locations. Whenever this grows too big, we
97 remove these useless values from the table. */
98 static int n_useless_values
;
100 /* Number of useless values before we remove them from the hash table. */
101 #define MAX_USELESS_VALUES 32
103 /* This table maps from register number to values. It does not contain
104 pointers to cselib_val structures, but rather elt_lists. The purpose is
105 to be able to refer to the same register in different modes. */
106 static varray_type reg_values
;
107 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
109 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
110 in clear_table() for fast emptying. */
111 static varray_type used_regs
;
113 /* We pass this to cselib_invalidate_mem to invalidate all of
114 memory for a non-const call instruction. */
117 /* Memory for our structures is allocated from this obstack. */
118 static struct obstack cselib_obstack
;
120 /* Used to quickly free all memory. */
121 static char *cselib_startobj
;
123 /* Caches for unused structures. */
124 static cselib_val
*empty_vals
;
125 static struct elt_list
*empty_elt_lists
;
126 static struct elt_loc_list
*empty_elt_loc_lists
;
128 /* Set by discard_useless_locs if it deleted the last location of any
130 static int values_became_useless
;
133 /* Allocate a struct elt_list and fill in its two elements with the
136 static struct elt_list
*
137 new_elt_list (next
, elt
)
138 struct elt_list
*next
;
141 struct elt_list
*el
= empty_elt_lists
;
144 empty_elt_lists
= el
->next
;
146 el
= (struct elt_list
*) obstack_alloc (&cselib_obstack
,
147 sizeof (struct elt_list
));
153 /* Allocate a struct elt_loc_list and fill in its two elements with the
156 static struct elt_loc_list
*
157 new_elt_loc_list (next
, loc
)
158 struct elt_loc_list
*next
;
161 struct elt_loc_list
*el
= empty_elt_loc_lists
;
164 empty_elt_loc_lists
= el
->next
;
166 el
= (struct elt_loc_list
*) obstack_alloc (&cselib_obstack
,
167 sizeof (struct elt_loc_list
));
170 el
->setting_insn
= cselib_current_insn
;
174 /* The elt_list at *PL is no longer needed. Unchain it and free its
178 unchain_one_elt_list (pl
)
179 struct elt_list
**pl
;
181 struct elt_list
*l
= *pl
;
184 l
->next
= empty_elt_lists
;
188 /* Likewise for elt_loc_lists. */
191 unchain_one_elt_loc_list (pl
)
192 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 (v
)
209 unchain_one_elt_list (&v
->addr_list
);
211 v
->u
.next_free
= empty_vals
;
215 /* Remove all entries from the hash table. Also used during
216 initialization. If CLEAR_ALL isn't set, then only clear the entries
217 which are known to have been used. */
220 clear_table (clear_all
)
226 for (i
= 0; i
< cselib_nregs
; i
++)
229 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (used_regs
); i
++)
230 REG_VALUES (VARRAY_UINT (used_regs
, i
)) = 0;
232 VARRAY_POP_ALL (used_regs
);
234 htab_empty (hash_table
);
235 obstack_free (&cselib_obstack
, cselib_startobj
);
239 empty_elt_loc_lists
= 0;
240 n_useless_values
= 0;
242 next_unknown_value
= 0;
245 /* The equality test for our hash table. The first argument ENTRY is a table
246 element (i.e. a cselib_val), while the second arg X is an rtx. We know
247 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
248 CONST of an appropriate mode. */
251 entry_and_rtx_equal_p (entry
, x_arg
)
252 const void *entry
, *x_arg
;
254 struct elt_loc_list
*l
;
255 const cselib_val
*v
= (const cselib_val
*) entry
;
257 enum machine_mode mode
= GET_MODE (x
);
259 if (GET_CODE (x
) == CONST_INT
260 || (mode
== VOIDmode
&& GET_CODE (x
) == CONST_DOUBLE
))
262 if (mode
!= GET_MODE (v
->u
.val_rtx
))
265 /* Unwrap X if necessary. */
266 if (GET_CODE (x
) == CONST
267 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
268 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
271 /* We don't guarantee that distinct rtx's have different hash values,
272 so we need to do a comparison. */
273 for (l
= v
->locs
; l
; l
= l
->next
)
274 if (rtx_equal_for_cselib_p (l
->loc
, x
))
280 /* The hash function for our hash table. The value is always computed with
281 hash_rtx when adding an element; this function just extracts the hash
282 value from a cselib_val structure. */
285 get_value_hash (entry
)
288 const cselib_val
*v
= (const cselib_val
*) entry
;
292 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
293 only return true for values which point to a cselib_val whose value
294 element has been set to zero, which implies the cselib_val will be
298 references_value_p (x
, only_useless
)
302 enum rtx_code code
= GET_CODE (x
);
303 const char *fmt
= GET_RTX_FORMAT (code
);
306 if (GET_CODE (x
) == VALUE
307 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
310 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
312 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
314 else if (fmt
[i
] == 'E')
315 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
316 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
323 /* For all locations found in X, delete locations that reference useless
324 values (i.e. values without any location). Called through
328 discard_useless_locs (x
, info
)
330 void *info ATTRIBUTE_UNUSED
;
332 cselib_val
*v
= (cselib_val
*)*x
;
333 struct elt_loc_list
**p
= &v
->locs
;
334 int had_locs
= v
->locs
!= 0;
338 if (references_value_p ((*p
)->loc
, 1))
339 unchain_one_elt_loc_list (p
);
344 if (had_locs
&& v
->locs
== 0)
347 values_became_useless
= 1;
352 /* If X is a value with no locations, remove it from the hashtable. */
355 discard_useless_values (x
, info
)
357 void *info ATTRIBUTE_UNUSED
;
359 cselib_val
*v
= (cselib_val
*)*x
;
363 htab_clear_slot (hash_table
, x
);
364 unchain_one_value (v
);
371 /* Clean out useless values (i.e. those which no longer have locations
372 associated with them) from the hash table. */
375 remove_useless_values ()
377 /* First pass: eliminate locations that reference the value. That in
378 turn can make more values useless. */
381 values_became_useless
= 0;
382 htab_traverse (hash_table
, discard_useless_locs
, 0);
384 while (values_became_useless
);
386 /* Second pass: actually remove the values. */
387 htab_traverse (hash_table
, discard_useless_values
, 0);
389 if (n_useless_values
!= 0)
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 (x
, y
)
404 if (GET_CODE (x
) == REG
|| GET_CODE (x
) == MEM
)
406 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
412 if (GET_CODE (y
) == REG
|| GET_CODE (y
) == MEM
)
414 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
423 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
424 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
426 if (GET_CODE (x
) == VALUE
)
428 cselib_val
*e
= CSELIB_VAL_PTR (x
);
429 struct elt_loc_list
*l
;
431 for (l
= e
->locs
; l
; l
= l
->next
)
435 /* Avoid infinite recursion. */
436 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
438 else if (rtx_equal_for_cselib_p (t
, y
))
445 if (GET_CODE (y
) == VALUE
)
447 cselib_val
*e
= CSELIB_VAL_PTR (y
);
448 struct elt_loc_list
*l
;
450 for (l
= e
->locs
; l
; l
= l
->next
)
454 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
456 else if (rtx_equal_for_cselib_p (x
, t
))
463 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
466 /* This won't be handled correctly by the code below. */
467 if (GET_CODE (x
) == LABEL_REF
)
468 return XEXP (x
, 0) == XEXP (y
, 0);
471 fmt
= GET_RTX_FORMAT (code
);
473 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
480 if (XWINT (x
, i
) != XWINT (y
, i
))
486 if (XINT (x
, i
) != XINT (y
, i
))
492 /* Two vectors must have the same length. */
493 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
496 /* And the corresponding elements must match. */
497 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
498 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
504 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
510 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
515 /* These are just backpointers, so they don't matter. */
522 /* It is believed that rtx's at this level will never
523 contain anything but integers and other rtx's,
524 except for within LABEL_REFs and SYMBOL_REFs. */
532 /* We need to pass down the mode of constants through the hash table
533 functions. For that purpose, wrap them in a CONST of the appropriate
536 wrap_constant (mode
, x
)
537 enum machine_mode mode
;
540 if (GET_CODE (x
) != CONST_INT
541 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
543 if (mode
== VOIDmode
)
545 return gen_rtx_CONST (mode
, x
);
548 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
549 For registers and memory locations, we look up their cselib_val structure
550 and return its VALUE element.
551 Possible reasons for return 0 are: the object is volatile, or we couldn't
552 find a register or memory location in the table and CREATE is zero. If
553 CREATE is nonzero, table elts are created for regs and mem.
554 MODE is used in hashing for CONST_INTs only;
555 otherwise the mode of X is used. */
558 hash_rtx (x
, mode
, create
)
560 enum machine_mode mode
;
567 unsigned int hash
= 0;
570 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
576 e
= cselib_lookup (x
, GET_MODE (x
), create
);
583 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
584 return hash
? hash
: (unsigned int) CONST_INT
;
587 /* This is like the general case, except that it only counts
588 the integers representing the constant. */
589 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
590 if (GET_MODE (x
) != VOIDmode
)
591 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
592 hash
+= XWINT (x
, i
);
594 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
595 + (unsigned) CONST_DOUBLE_HIGH (x
));
596 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
598 /* Assume there is only one rtx object for any given label. */
601 += ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
602 return hash
? hash
: (unsigned int) LABEL_REF
;
606 += ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
607 return hash
? hash
: (unsigned int) SYMBOL_REF
;
618 case UNSPEC_VOLATILE
:
622 if (MEM_VOLATILE_P (x
))
631 i
= GET_RTX_LENGTH (code
) - 1;
632 fmt
= GET_RTX_FORMAT (code
);
637 rtx tem
= XEXP (x
, i
);
638 unsigned int tem_hash
= hash_rtx (tem
, 0, create
);
645 else if (fmt
[i
] == 'E')
646 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
648 unsigned int tem_hash
= hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
655 else if (fmt
[i
] == 's')
657 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
663 else if (fmt
[i
] == 'i')
665 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
671 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
674 /* Create a new value structure for VALUE and initialize it. The mode of the
678 new_cselib_val (value
, mode
)
680 enum machine_mode mode
;
682 cselib_val
*e
= empty_vals
;
685 empty_vals
= e
->u
.next_free
;
687 e
= (cselib_val
*) obstack_alloc (&cselib_obstack
, sizeof (cselib_val
));
693 e
->u
.val_rtx
= gen_rtx_VALUE (mode
);
694 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
700 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
701 contains the data at this address. X is a MEM that represents the
702 value. Update the two value structures to represent this situation. */
705 add_mem_for_addr (addr_elt
, mem_elt
, x
)
706 cselib_val
*addr_elt
, *mem_elt
;
709 struct elt_loc_list
*l
;
711 /* Avoid duplicates. */
712 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
713 if (GET_CODE (l
->loc
) == MEM
714 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
717 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
719 = new_elt_loc_list (mem_elt
->locs
,
720 replace_equiv_address_nv (x
, addr_elt
->u
.val_rtx
));
723 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
724 If CREATE, make a new one if we haven't seen it before. */
727 cselib_lookup_mem (x
, create
)
731 enum machine_mode mode
= GET_MODE (x
);
737 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
738 || (FLOAT_MODE_P (mode
) && flag_float_store
))
741 /* Look up the value for the address. */
742 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
746 /* Find a value that describes a value of our mode at that address. */
747 for (l
= addr
->addr_list
; l
; l
= l
->next
)
748 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
754 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
755 add_mem_for_addr (addr
, mem_elt
, x
);
756 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
757 mem_elt
->value
, INSERT
);
762 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
763 with VALUE expressions. This way, it becomes independent of changes
764 to registers and memory.
765 X isn't actually modified; if modifications are needed, new rtl is
766 allocated. However, the return value can share rtl with X. */
769 cselib_subst_to_values (x
)
772 enum rtx_code code
= GET_CODE (x
);
773 const char *fmt
= GET_RTX_FORMAT (code
);
782 for (l
= REG_VALUES (REGNO (x
)); l
; l
= l
->next
)
783 if (GET_MODE (l
->elt
->u
.val_rtx
) == GET_MODE (x
))
784 return l
->elt
->u
.val_rtx
;
789 e
= cselib_lookup_mem (x
, 0);
794 /* CONST_DOUBLEs must be special-cased here so that we won't try to
795 look up the CONST_DOUBLE_MEM inside. */
804 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
808 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
810 if (t
!= XEXP (x
, i
) && x
== copy
)
811 copy
= shallow_copy_rtx (x
);
815 else if (fmt
[i
] == 'E')
819 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
821 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
823 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
826 copy
= shallow_copy_rtx (x
);
828 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
829 for (k
= 0; k
< j
; k
++)
830 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
833 XVECEXP (copy
, i
, j
) = t
;
841 /* Look up the rtl expression X in our tables and return the value it has.
842 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
843 we create a new one if possible, using mode MODE if X doesn't have a mode
844 (i.e. because it's a constant). */
847 cselib_lookup (x
, mode
, create
)
849 enum machine_mode mode
;
854 unsigned int hashval
;
856 if (GET_MODE (x
) != VOIDmode
)
859 if (GET_CODE (x
) == VALUE
)
860 return CSELIB_VAL_PTR (x
);
862 if (GET_CODE (x
) == REG
)
865 unsigned int i
= REGNO (x
);
867 for (l
= REG_VALUES (i
); l
; l
= l
->next
)
868 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
874 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
875 e
->locs
= new_elt_loc_list (e
->locs
, x
);
876 if (REG_VALUES (i
) == 0)
877 VARRAY_PUSH_UINT (used_regs
, i
);
878 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), e
);
879 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
884 if (GET_CODE (x
) == MEM
)
885 return cselib_lookup_mem (x
, create
);
887 hashval
= hash_rtx (x
, mode
, create
);
888 /* Can't even create if hashing is not possible. */
892 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
893 hashval
, create
? INSERT
: NO_INSERT
);
897 e
= (cselib_val
*) *slot
;
901 e
= new_cselib_val (hashval
, mode
);
903 /* We have to fill the slot before calling cselib_subst_to_values:
904 the hash table is inconsistent until we do so, and
905 cselib_subst_to_values will need to do lookups. */
907 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
911 /* Invalidate any entries in reg_values that overlap REGNO. This is called
912 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
913 is used to determine how many hard registers are being changed. If MODE
914 is VOIDmode, then only REGNO is being changed; this is used when
915 invalidating call clobbered registers across a call. */
918 cselib_invalidate_regno (regno
, mode
)
920 enum machine_mode mode
;
922 unsigned int endregno
;
925 /* If we see pseudos after reload, something is _wrong_. */
926 if (reload_completed
&& regno
>= FIRST_PSEUDO_REGISTER
927 && reg_renumber
[regno
] >= 0)
930 /* Determine the range of registers that must be invalidated. For
931 pseudos, only REGNO is affected. For hard regs, we must take MODE
932 into account, and we must also invalidate lower register numbers
933 if they contain values that overlap REGNO. */
934 endregno
= regno
+ 1;
935 if (regno
< FIRST_PSEUDO_REGISTER
&& mode
!= VOIDmode
)
936 endregno
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
938 for (i
= 0; i
< endregno
; i
++)
940 struct elt_list
**l
= ®_VALUES (i
);
942 /* Go through all known values for this reg; if it overlaps the range
943 we're invalidating, remove the value. */
946 cselib_val
*v
= (*l
)->elt
;
947 struct elt_loc_list
**p
;
948 unsigned int this_last
= i
;
950 if (i
< FIRST_PSEUDO_REGISTER
)
951 this_last
+= HARD_REGNO_NREGS (i
, GET_MODE (v
->u
.val_rtx
)) - 1;
953 if (this_last
< regno
)
959 /* We have an overlap. */
960 unchain_one_elt_list (l
);
962 /* Now, we clear the mapping from value to reg. It must exist, so
963 this code will crash intentionally if it doesn't. */
964 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
968 if (GET_CODE (x
) == REG
&& REGNO (x
) == i
)
970 unchain_one_elt_loc_list (p
);
980 /* The memory at address MEM_BASE is being changed.
981 Return whether this change will invalidate VAL. */
984 cselib_mem_conflict_p (mem_base
, val
)
992 code
= GET_CODE (val
);
995 /* Get rid of a few simple cases quickly. */
1008 if (GET_MODE (mem_base
) == BLKmode
1009 || GET_MODE (val
) == BLKmode
1010 || anti_dependence (val
, mem_base
))
1013 /* The address may contain nested MEMs. */
1020 fmt
= GET_RTX_FORMAT (code
);
1021 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1025 if (cselib_mem_conflict_p (mem_base
, XEXP (val
, i
)))
1028 else if (fmt
[i
] == 'E')
1029 for (j
= 0; j
< XVECLEN (val
, i
); j
++)
1030 if (cselib_mem_conflict_p (mem_base
, XVECEXP (val
, i
, j
)))
1037 /* For the value found in SLOT, walk its locations to determine if any overlap
1038 INFO (which is a MEM rtx). */
1041 cselib_invalidate_mem_1 (slot
, info
)
1045 cselib_val
*v
= (cselib_val
*) *slot
;
1046 rtx mem_rtx
= (rtx
) info
;
1047 struct elt_loc_list
**p
= &v
->locs
;
1048 int had_locs
= v
->locs
!= 0;
1054 struct elt_list
**mem_chain
;
1056 /* MEMs may occur in locations only at the top level; below
1057 that every MEM or REG is substituted by its VALUE. */
1058 if (GET_CODE (x
) != MEM
1059 || ! cselib_mem_conflict_p (mem_rtx
, x
))
1065 /* This one overlaps. */
1066 /* We must have a mapping from this MEM's address to the
1067 value (E). Remove that, too. */
1068 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1069 mem_chain
= &addr
->addr_list
;
1072 if ((*mem_chain
)->elt
== v
)
1074 unchain_one_elt_list (mem_chain
);
1078 mem_chain
= &(*mem_chain
)->next
;
1081 unchain_one_elt_loc_list (p
);
1084 if (had_locs
&& v
->locs
== 0)
1090 /* Invalidate any locations in the table which are changed because of a
1091 store to MEM_RTX. If this is called because of a non-const call
1092 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1095 cselib_invalidate_mem (mem_rtx
)
1098 htab_traverse (hash_table
, cselib_invalidate_mem_1
, mem_rtx
);
1101 /* Invalidate DEST, which is being assigned to or clobbered. The second and
1102 the third parameter exist so that this function can be passed to
1103 note_stores; they are ignored. */
1106 cselib_invalidate_rtx (dest
, ignore
, data
)
1108 rtx ignore ATTRIBUTE_UNUSED
;
1109 void *data ATTRIBUTE_UNUSED
;
1111 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SIGN_EXTRACT
1112 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
)
1113 dest
= XEXP (dest
, 0);
1115 if (GET_CODE (dest
) == REG
)
1116 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1117 else if (GET_CODE (dest
) == MEM
)
1118 cselib_invalidate_mem (dest
);
1120 /* Some machines don't define AUTO_INC_DEC, but they still use push
1121 instructions. We need to catch that case here in order to
1122 invalidate the stack pointer correctly. Note that invalidating
1123 the stack pointer is different from invalidating DEST. */
1124 if (push_operand (dest
, GET_MODE (dest
)))
1125 cselib_invalidate_rtx (stack_pointer_rtx
, NULL_RTX
, NULL
);
1128 /* Record the result of a SET instruction. DEST is being set; the source
1129 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1130 describes its address. */
1133 cselib_record_set (dest
, src_elt
, dest_addr_elt
)
1135 cselib_val
*src_elt
, *dest_addr_elt
;
1137 int dreg
= GET_CODE (dest
) == REG
? (int) REGNO (dest
) : -1;
1139 if (src_elt
== 0 || side_effects_p (dest
))
1144 if (REG_VALUES (dreg
) == 0)
1145 VARRAY_PUSH_UINT (used_regs
, dreg
);
1147 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1148 if (src_elt
->locs
== 0)
1150 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1152 else if (GET_CODE (dest
) == MEM
&& dest_addr_elt
!= 0)
1154 if (src_elt
->locs
== 0)
1156 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1160 /* Describe a single set that is part of an insn. */
1165 cselib_val
*src_elt
;
1166 cselib_val
*dest_addr_elt
;
1169 /* There is no good way to determine how many elements there can be
1170 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1171 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1173 /* Record the effects of any sets in INSN. */
1175 cselib_record_sets (insn
)
1180 struct set sets
[MAX_SETS
];
1181 rtx body
= PATTERN (insn
);
1183 body
= PATTERN (insn
);
1184 /* Find all sets. */
1185 if (GET_CODE (body
) == SET
)
1187 sets
[0].src
= SET_SRC (body
);
1188 sets
[0].dest
= SET_DEST (body
);
1191 else if (GET_CODE (body
) == PARALLEL
)
1193 /* Look through the PARALLEL and record the values being
1194 set, if possible. Also handle any CLOBBERs. */
1195 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1197 rtx x
= XVECEXP (body
, 0, i
);
1199 if (GET_CODE (x
) == SET
)
1201 sets
[n_sets
].src
= SET_SRC (x
);
1202 sets
[n_sets
].dest
= SET_DEST (x
);
1208 /* Look up the values that are read. Do this before invalidating the
1209 locations that are written. */
1210 for (i
= 0; i
< n_sets
; i
++)
1212 rtx dest
= sets
[i
].dest
;
1214 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1215 the low part after invalidating any knowledge about larger modes. */
1216 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1217 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1219 /* We don't know how to record anything but REG or MEM. */
1220 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1222 sets
[i
].src_elt
= cselib_lookup (sets
[i
].src
, GET_MODE (dest
), 1);
1223 if (GET_CODE (dest
) == MEM
)
1224 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1226 sets
[i
].dest_addr_elt
= 0;
1230 /* Invalidate all locations written by this insn. Note that the elts we
1231 looked up in the previous loop aren't affected, just some of their
1232 locations may go away. */
1233 note_stores (body
, cselib_invalidate_rtx
, NULL
);
1235 /* Now enter the equivalences in our tables. */
1236 for (i
= 0; i
< n_sets
; i
++)
1238 rtx dest
= sets
[i
].dest
;
1239 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1240 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1244 /* Record the effects of INSN. */
1247 cselib_process_insn (insn
)
1253 cselib_current_insn
= insn
;
1255 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1256 if (GET_CODE (insn
) == CODE_LABEL
1257 || (GET_CODE (insn
) == NOTE
1258 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
)
1259 || (GET_CODE (insn
) == INSN
1260 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1261 && MEM_VOLATILE_P (PATTERN (insn
))))
1267 if (! INSN_P (insn
))
1269 cselib_current_insn
= 0;
1273 /* If this is a call instruction, forget anything stored in a
1274 call clobbered register, or, if this is not a const call, in
1276 if (GET_CODE (insn
) == CALL_INSN
)
1278 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1279 if (call_used_regs
[i
])
1280 cselib_invalidate_regno (i
, VOIDmode
);
1282 if (! CONST_CALL_P (insn
))
1283 cselib_invalidate_mem (callmem
);
1286 cselib_record_sets (insn
);
1289 /* Clobber any registers which appear in REG_INC notes. We
1290 could keep track of the changes to their values, but it is
1291 unlikely to help. */
1292 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1293 if (REG_NOTE_KIND (x
) == REG_INC
)
1294 cselib_invalidate_rtx (XEXP (x
, 0), NULL_RTX
, NULL
);
1297 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1298 after we have processed the insn. */
1299 if (GET_CODE (insn
) == CALL_INSN
)
1300 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1301 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1302 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0), NULL_RTX
, NULL
);
1304 cselib_current_insn
= 0;
1306 if (n_useless_values
> MAX_USELESS_VALUES
)
1307 remove_useless_values ();
1310 /* Make sure our varrays are big enough. Not called from any cselib routines;
1311 it must be called by the user if it allocated new registers. */
1314 cselib_update_varray_sizes ()
1316 unsigned int nregs
= max_reg_num ();
1318 if (nregs
== cselib_nregs
)
1321 cselib_nregs
= nregs
;
1322 VARRAY_GROW (reg_values
, nregs
);
1323 VARRAY_GROW (used_regs
, nregs
);
1326 /* Initialize cselib for one pass. The caller must also call
1327 init_alias_analysis. */
1332 /* These are only created once. */
1335 gcc_obstack_init (&cselib_obstack
);
1336 cselib_startobj
= obstack_alloc (&cselib_obstack
, 0);
1338 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1339 ggc_add_rtx_root (&callmem
, 1);
1342 cselib_nregs
= max_reg_num ();
1343 VARRAY_ELT_LIST_INIT (reg_values
, cselib_nregs
, "reg_values");
1344 VARRAY_UINT_INIT (used_regs
, cselib_nregs
, "used_regs");
1345 hash_table
= htab_create (31, get_value_hash
, entry_and_rtx_equal_p
, NULL
);
1349 /* Called when the current user is done with cselib. */
1355 VARRAY_FREE (reg_values
);
1356 VARRAY_FREE (used_regs
);
1357 htab_delete (hash_table
);