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;
569 /* repeat is used to turn tail-recursion into iteration. */
572 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
578 e
= cselib_lookup (x
, GET_MODE (x
), create
);
586 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
587 return hash
? hash
: CONST_INT
;
590 /* This is like the general case, except that it only counts
591 the integers representing the constant. */
592 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
593 if (GET_MODE (x
) != VOIDmode
)
594 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
595 hash
+= XWINT (x
, i
);
597 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
598 + (unsigned) CONST_DOUBLE_HIGH (x
));
599 return hash
? hash
: CONST_DOUBLE
;
601 /* Assume there is only one rtx object for any given label. */
604 += ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
605 return hash
? hash
: LABEL_REF
;
609 += ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
610 return hash
? hash
: SYMBOL_REF
;
621 case UNSPEC_VOLATILE
:
625 if (MEM_VOLATILE_P (x
))
634 i
= GET_RTX_LENGTH (code
) - 1;
635 fmt
= GET_RTX_FORMAT (code
);
640 rtx tem
= XEXP (x
, i
);
641 unsigned int tem_hash
;
643 /* If we are about to do the last recursive call
644 needed at this level, change it into iteration.
645 This function is called enough to be worth it. */
652 tem_hash
= hash_rtx (tem
, 0, create
);
658 else if (fmt
[i
] == 'E')
659 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
661 unsigned int tem_hash
= hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
668 else if (fmt
[i
] == 's')
670 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
676 else if (fmt
[i
] == 'i')
678 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
684 return hash
? hash
: 1 + GET_CODE (x
);
687 /* Create a new value structure for VALUE and initialize it. The mode of the
691 new_cselib_val (value
, mode
)
693 enum machine_mode mode
;
695 cselib_val
*e
= empty_vals
;
698 empty_vals
= e
->u
.next_free
;
700 e
= (cselib_val
*) obstack_alloc (&cselib_obstack
, sizeof (cselib_val
));
706 e
->u
.val_rtx
= gen_rtx_VALUE (mode
);
707 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
713 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
714 contains the data at this address. X is a MEM that represents the
715 value. Update the two value structures to represent this situation. */
718 add_mem_for_addr (addr_elt
, mem_elt
, x
)
719 cselib_val
*addr_elt
, *mem_elt
;
723 struct elt_loc_list
*l
;
725 /* Avoid duplicates. */
726 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
727 if (GET_CODE (l
->loc
) == MEM
728 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
731 new = gen_rtx_MEM (GET_MODE (x
), addr_elt
->u
.val_rtx
);
732 MEM_COPY_ATTRIBUTES (new, x
);
734 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
735 mem_elt
->locs
= new_elt_loc_list (mem_elt
->locs
, new);
738 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
739 If CREATE, make a new one if we haven't seen it before. */
742 cselib_lookup_mem (x
, create
)
746 enum machine_mode mode
= GET_MODE (x
);
752 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
753 || (FLOAT_MODE_P (mode
) && flag_float_store
))
756 /* Look up the value for the address. */
757 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
761 /* Find a value that describes a value of our mode at that address. */
762 for (l
= addr
->addr_list
; l
; l
= l
->next
)
763 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
769 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
770 add_mem_for_addr (addr
, mem_elt
, x
);
771 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
772 mem_elt
->value
, INSERT
);
777 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
778 with VALUE expressions. This way, it becomes independent of changes
779 to registers and memory.
780 X isn't actually modified; if modifications are needed, new rtl is
781 allocated. However, the return value can share rtl with X. */
784 cselib_subst_to_values (x
)
787 enum rtx_code code
= GET_CODE (x
);
788 const char *fmt
= GET_RTX_FORMAT (code
);
797 for (l
= REG_VALUES (REGNO (x
)); l
; l
= l
->next
)
798 if (GET_MODE (l
->elt
->u
.val_rtx
) == GET_MODE (x
))
799 return l
->elt
->u
.val_rtx
;
804 e
= cselib_lookup_mem (x
, 0);
809 /* CONST_DOUBLEs must be special-cased here so that we won't try to
810 look up the CONST_DOUBLE_MEM inside. */
819 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
823 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
825 if (t
!= XEXP (x
, i
) && x
== copy
)
826 copy
= shallow_copy_rtx (x
);
830 else if (fmt
[i
] == 'E')
834 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
836 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
838 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
841 copy
= shallow_copy_rtx (x
);
843 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
844 for (k
= 0; k
< j
; k
++)
845 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
848 XVECEXP (copy
, i
, j
) = t
;
856 /* Look up the rtl expression X in our tables and return the value it has.
857 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
858 we create a new one if possible, using mode MODE if X doesn't have a mode
859 (i.e. because it's a constant). */
862 cselib_lookup (x
, mode
, create
)
864 enum machine_mode mode
;
869 unsigned int hashval
;
871 if (GET_MODE (x
) != VOIDmode
)
874 if (GET_CODE (x
) == VALUE
)
875 return CSELIB_VAL_PTR (x
);
877 if (GET_CODE (x
) == REG
)
880 unsigned int i
= REGNO (x
);
882 for (l
= REG_VALUES (i
); l
; l
= l
->next
)
883 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
889 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
890 e
->locs
= new_elt_loc_list (e
->locs
, x
);
891 if (REG_VALUES (i
) == 0)
892 VARRAY_PUSH_UINT (used_regs
, i
);
893 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), e
);
894 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
899 if (GET_CODE (x
) == MEM
)
900 return cselib_lookup_mem (x
, create
);
902 hashval
= hash_rtx (x
, mode
, create
);
903 /* Can't even create if hashing is not possible. */
907 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
908 hashval
, create
? INSERT
: NO_INSERT
);
912 e
= (cselib_val
*) *slot
;
916 e
= new_cselib_val (hashval
, mode
);
918 /* We have to fill the slot before calling cselib_subst_to_values:
919 the hash table is inconsistent until we do so, and
920 cselib_subst_to_values will need to do lookups. */
922 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
926 /* Invalidate any entries in reg_values that overlap REGNO. This is called
927 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
928 is used to determine how many hard registers are being changed. If MODE
929 is VOIDmode, then only REGNO is being changed; this is used when
930 invalidating call clobbered registers across a call. */
933 cselib_invalidate_regno (regno
, mode
)
935 enum machine_mode mode
;
937 unsigned int endregno
;
940 /* If we see pseudos after reload, something is _wrong_. */
941 if (reload_completed
&& regno
>= FIRST_PSEUDO_REGISTER
942 && reg_renumber
[regno
] >= 0)
945 /* Determine the range of registers that must be invalidated. For
946 pseudos, only REGNO is affected. For hard regs, we must take MODE
947 into account, and we must also invalidate lower register numbers
948 if they contain values that overlap REGNO. */
949 endregno
= regno
+ 1;
950 if (regno
< FIRST_PSEUDO_REGISTER
&& mode
!= VOIDmode
)
951 endregno
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
953 for (i
= 0; i
< endregno
; i
++)
955 struct elt_list
**l
= ®_VALUES (i
);
957 /* Go through all known values for this reg; if it overlaps the range
958 we're invalidating, remove the value. */
961 cselib_val
*v
= (*l
)->elt
;
962 struct elt_loc_list
**p
;
963 unsigned int this_last
= i
;
965 if (i
< FIRST_PSEUDO_REGISTER
)
966 this_last
+= HARD_REGNO_NREGS (i
, GET_MODE (v
->u
.val_rtx
)) - 1;
968 if (this_last
< regno
)
974 /* We have an overlap. */
975 unchain_one_elt_list (l
);
977 /* Now, we clear the mapping from value to reg. It must exist, so
978 this code will crash intentionally if it doesn't. */
979 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
983 if (GET_CODE (x
) == REG
&& REGNO (x
) == i
)
985 unchain_one_elt_loc_list (p
);
995 /* The memory at address MEM_BASE is being changed.
996 Return whether this change will invalidate VAL. */
999 cselib_mem_conflict_p (mem_base
, val
)
1007 code
= GET_CODE (val
);
1010 /* Get rid of a few simple cases quickly. */
1023 if (GET_MODE (mem_base
) == BLKmode
1024 || GET_MODE (val
) == BLKmode
1025 || anti_dependence (val
, mem_base
))
1028 /* The address may contain nested MEMs. */
1035 fmt
= GET_RTX_FORMAT (code
);
1036 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1040 if (cselib_mem_conflict_p (mem_base
, XEXP (val
, i
)))
1043 else if (fmt
[i
] == 'E')
1044 for (j
= 0; j
< XVECLEN (val
, i
); j
++)
1045 if (cselib_mem_conflict_p (mem_base
, XVECEXP (val
, i
, j
)))
1052 /* For the value found in SLOT, walk its locations to determine if any overlap
1053 INFO (which is a MEM rtx). */
1056 cselib_invalidate_mem_1 (slot
, info
)
1060 cselib_val
*v
= (cselib_val
*) *slot
;
1061 rtx mem_rtx
= (rtx
) info
;
1062 struct elt_loc_list
**p
= &v
->locs
;
1063 int had_locs
= v
->locs
!= 0;
1069 struct elt_list
**mem_chain
;
1071 /* MEMs may occur in locations only at the top level; below
1072 that every MEM or REG is substituted by its VALUE. */
1073 if (GET_CODE (x
) != MEM
1074 || ! cselib_mem_conflict_p (mem_rtx
, x
))
1080 /* This one overlaps. */
1081 /* We must have a mapping from this MEM's address to the
1082 value (E). Remove that, too. */
1083 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1084 mem_chain
= &addr
->addr_list
;
1087 if ((*mem_chain
)->elt
== v
)
1089 unchain_one_elt_list (mem_chain
);
1093 mem_chain
= &(*mem_chain
)->next
;
1096 unchain_one_elt_loc_list (p
);
1099 if (had_locs
&& v
->locs
== 0)
1105 /* Invalidate any locations in the table which are changed because of a
1106 store to MEM_RTX. If this is called because of a non-const call
1107 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1110 cselib_invalidate_mem (mem_rtx
)
1113 htab_traverse (hash_table
, cselib_invalidate_mem_1
, mem_rtx
);
1116 /* Invalidate DEST, which is being assigned to or clobbered. The second and
1117 the third parameter exist so that this function can be passed to
1118 note_stores; they are ignored. */
1121 cselib_invalidate_rtx (dest
, ignore
, data
)
1123 rtx ignore ATTRIBUTE_UNUSED
;
1124 void *data ATTRIBUTE_UNUSED
;
1126 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SIGN_EXTRACT
1127 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
)
1128 dest
= XEXP (dest
, 0);
1130 if (GET_CODE (dest
) == REG
)
1131 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1132 else if (GET_CODE (dest
) == MEM
)
1133 cselib_invalidate_mem (dest
);
1135 /* Some machines don't define AUTO_INC_DEC, but they still use push
1136 instructions. We need to catch that case here in order to
1137 invalidate the stack pointer correctly. Note that invalidating
1138 the stack pointer is different from invalidating DEST. */
1139 if (push_operand (dest
, GET_MODE (dest
)))
1140 cselib_invalidate_rtx (stack_pointer_rtx
, NULL_RTX
, NULL
);
1143 /* Record the result of a SET instruction. DEST is being set; the source
1144 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1145 describes its address. */
1148 cselib_record_set (dest
, src_elt
, dest_addr_elt
)
1150 cselib_val
*src_elt
, *dest_addr_elt
;
1152 int dreg
= GET_CODE (dest
) == REG
? (int) REGNO (dest
) : -1;
1154 if (src_elt
== 0 || side_effects_p (dest
))
1159 if (REG_VALUES (dreg
) == 0)
1160 VARRAY_PUSH_UINT (used_regs
, dreg
);
1162 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1163 if (src_elt
->locs
== 0)
1165 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1167 else if (GET_CODE (dest
) == MEM
&& dest_addr_elt
!= 0)
1169 if (src_elt
->locs
== 0)
1171 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1175 /* Describe a single set that is part of an insn. */
1180 cselib_val
*src_elt
;
1181 cselib_val
*dest_addr_elt
;
1184 /* There is no good way to determine how many elements there can be
1185 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1186 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1188 /* Record the effects of any sets in INSN. */
1190 cselib_record_sets (insn
)
1195 struct set sets
[MAX_SETS
];
1196 rtx body
= PATTERN (insn
);
1198 body
= PATTERN (insn
);
1199 /* Find all sets. */
1200 if (GET_CODE (body
) == SET
)
1202 sets
[0].src
= SET_SRC (body
);
1203 sets
[0].dest
= SET_DEST (body
);
1206 else if (GET_CODE (body
) == PARALLEL
)
1208 /* Look through the PARALLEL and record the values being
1209 set, if possible. Also handle any CLOBBERs. */
1210 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1212 rtx x
= XVECEXP (body
, 0, i
);
1214 if (GET_CODE (x
) == SET
)
1216 sets
[n_sets
].src
= SET_SRC (x
);
1217 sets
[n_sets
].dest
= SET_DEST (x
);
1223 /* Look up the values that are read. Do this before invalidating the
1224 locations that are written. */
1225 for (i
= 0; i
< n_sets
; i
++)
1227 rtx dest
= sets
[i
].dest
;
1229 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1230 the low part after invalidating any knowledge about larger modes. */
1231 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1232 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1234 /* We don't know how to record anything but REG or MEM. */
1235 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1237 sets
[i
].src_elt
= cselib_lookup (sets
[i
].src
, GET_MODE (dest
), 1);
1238 if (GET_CODE (dest
) == MEM
)
1239 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1241 sets
[i
].dest_addr_elt
= 0;
1245 /* Invalidate all locations written by this insn. Note that the elts we
1246 looked up in the previous loop aren't affected, just some of their
1247 locations may go away. */
1248 note_stores (body
, cselib_invalidate_rtx
, NULL
);
1250 /* Now enter the equivalences in our tables. */
1251 for (i
= 0; i
< n_sets
; i
++)
1253 rtx dest
= sets
[i
].dest
;
1254 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1255 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1259 /* Record the effects of INSN. */
1262 cselib_process_insn (insn
)
1268 cselib_current_insn
= insn
;
1270 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1271 if (GET_CODE (insn
) == CODE_LABEL
1272 || (GET_CODE (insn
) == NOTE
1273 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_SETJMP
)
1274 || (GET_CODE (insn
) == INSN
1275 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1276 && MEM_VOLATILE_P (PATTERN (insn
))))
1282 if (! INSN_P (insn
))
1284 cselib_current_insn
= 0;
1288 /* If this is a call instruction, forget anything stored in a
1289 call clobbered register, or, if this is not a const call, in
1291 if (GET_CODE (insn
) == CALL_INSN
)
1293 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1294 if (call_used_regs
[i
])
1295 cselib_invalidate_regno (i
, VOIDmode
);
1297 if (! CONST_CALL_P (insn
))
1298 cselib_invalidate_mem (callmem
);
1301 cselib_record_sets (insn
);
1304 /* Clobber any registers which appear in REG_INC notes. We
1305 could keep track of the changes to their values, but it is
1306 unlikely to help. */
1307 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1308 if (REG_NOTE_KIND (x
) == REG_INC
)
1309 cselib_invalidate_rtx (XEXP (x
, 0), NULL_RTX
, NULL
);
1312 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1313 after we have processed the insn. */
1314 if (GET_CODE (insn
) == CALL_INSN
)
1315 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1316 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1317 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0), NULL_RTX
, NULL
);
1319 cselib_current_insn
= 0;
1321 if (n_useless_values
> MAX_USELESS_VALUES
)
1322 remove_useless_values ();
1325 /* Make sure our varrays are big enough. Not called from any cselib routines;
1326 it must be called by the user if it allocated new registers. */
1329 cselib_update_varray_sizes ()
1331 unsigned int nregs
= max_reg_num ();
1333 if (nregs
== cselib_nregs
)
1336 cselib_nregs
= nregs
;
1337 VARRAY_GROW (reg_values
, nregs
);
1338 VARRAY_GROW (used_regs
, nregs
);
1341 /* Initialize cselib for one pass. The caller must also call
1342 init_alias_analysis. */
1347 /* These are only created once. */
1350 gcc_obstack_init (&cselib_obstack
);
1351 cselib_startobj
= obstack_alloc (&cselib_obstack
, 0);
1353 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1354 ggc_add_rtx_root (&callmem
, 1);
1357 cselib_nregs
= max_reg_num ();
1358 VARRAY_ELT_LIST_INIT (reg_values
, cselib_nregs
, "reg_values");
1359 VARRAY_UINT_INIT (used_regs
, cselib_nregs
, "used_regs");
1360 hash_table
= htab_create (31, get_value_hash
, entry_and_rtx_equal_p
, NULL
);
1364 /* Called when the current user is done with cselib. */
1370 VARRAY_FREE (reg_values
);
1371 VARRAY_FREE (used_regs
);
1372 htab_delete (hash_table
);