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 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
28 #include "hard-reg-set.h"
31 #include "insn-config.h"
42 static int entry_and_rtx_equal_p
PARAMS ((const void *, const void *));
43 static unsigned int get_value_hash
PARAMS ((const void *));
44 static struct elt_list
*new_elt_list
PARAMS ((struct elt_list
*,
46 static struct elt_loc_list
*new_elt_loc_list
PARAMS ((struct elt_loc_list
*,
48 static void unchain_one_value
PARAMS ((cselib_val
*));
49 static void unchain_one_elt_list
PARAMS ((struct elt_list
**));
50 static void unchain_one_elt_loc_list
PARAMS ((struct elt_loc_list
**));
51 static void clear_table
PARAMS ((int));
52 static int discard_useless_locs
PARAMS ((void **, void *));
53 static int discard_useless_values
PARAMS ((void **, void *));
54 static void remove_useless_values
PARAMS ((void));
55 static rtx wrap_constant
PARAMS ((enum machine_mode
, rtx
));
56 static unsigned int hash_rtx
PARAMS ((rtx
, enum machine_mode
, int));
57 static cselib_val
*new_cselib_val
PARAMS ((unsigned int,
59 static void add_mem_for_addr
PARAMS ((cselib_val
*, cselib_val
*,
61 static cselib_val
*cselib_lookup_mem
PARAMS ((rtx
, int));
62 static void cselib_invalidate_regno
PARAMS ((unsigned int,
64 static int cselib_mem_conflict_p
PARAMS ((rtx
, rtx
));
65 static int cselib_invalidate_mem_1
PARAMS ((void **, void *));
66 static void cselib_invalidate_mem
PARAMS ((rtx
));
67 static void cselib_invalidate_rtx
PARAMS ((rtx
, rtx
, void *));
68 static void cselib_record_set
PARAMS ((rtx
, cselib_val
*,
70 static void cselib_record_sets
PARAMS ((rtx
));
72 /* There are three ways in which cselib can look up an rtx:
73 - for a REG, the reg_values table (which is indexed by regno) is used
74 - for a MEM, we recursively look up its address and then follow the
75 addr_list of that value
76 - for everything else, we compute a hash value and go through the hash
77 table. Since different rtx's can still have the same hash value,
78 this involves walking the table entries for a given value and comparing
79 the locations of the entries with the rtx we are looking up. */
81 /* A table that enables us to look up elts by their value. */
82 static htab_t hash_table
;
84 /* This is a global so we don't have to pass this through every function.
85 It is used in new_elt_loc_list to set SETTING_INSN. */
86 static rtx cselib_current_insn
;
88 /* Every new unknown value gets a unique number. */
89 static unsigned int next_unknown_value
;
91 /* The number of registers we had when the varrays were last resized. */
92 static unsigned int cselib_nregs
;
94 /* Count values without known locations. Whenever this grows too big, we
95 remove these useless values from the table. */
96 static int n_useless_values
;
98 /* Number of useless values before we remove them from the hash table. */
99 #define MAX_USELESS_VALUES 32
101 /* This table maps from register number to values. It does not contain
102 pointers to cselib_val structures, but rather elt_lists. The purpose is
103 to be able to refer to the same register in different modes. */
104 static varray_type reg_values
;
105 #define REG_VALUES(I) VARRAY_ELT_LIST (reg_values, (I))
107 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
108 in clear_table() for fast emptying. */
109 static varray_type used_regs
;
111 /* We pass this to cselib_invalidate_mem to invalidate all of
112 memory for a non-const call instruction. */
115 /* Memory for our structures is allocated from this obstack. */
116 static struct obstack cselib_obstack
;
118 /* Used to quickly free all memory. */
119 static char *cselib_startobj
;
121 /* Caches for unused structures. */
122 static cselib_val
*empty_vals
;
123 static struct elt_list
*empty_elt_lists
;
124 static struct elt_loc_list
*empty_elt_loc_lists
;
126 /* Set by discard_useless_locs if it deleted the last location of any
128 static int values_became_useless
;
131 /* Allocate a struct elt_list and fill in its two elements with the
134 static struct elt_list
*
135 new_elt_list (next
, elt
)
136 struct elt_list
*next
;
139 struct elt_list
*el
= empty_elt_lists
;
142 empty_elt_lists
= el
->next
;
144 el
= (struct elt_list
*) obstack_alloc (&cselib_obstack
,
145 sizeof (struct elt_list
));
151 /* Allocate a struct elt_loc_list and fill in its two elements with the
154 static struct elt_loc_list
*
155 new_elt_loc_list (next
, loc
)
156 struct elt_loc_list
*next
;
159 struct elt_loc_list
*el
= empty_elt_loc_lists
;
162 empty_elt_loc_lists
= el
->next
;
164 el
= (struct elt_loc_list
*) obstack_alloc (&cselib_obstack
,
165 sizeof (struct elt_loc_list
));
168 el
->setting_insn
= cselib_current_insn
;
172 /* The elt_list at *PL is no longer needed. Unchain it and free its
176 unchain_one_elt_list (pl
)
177 struct elt_list
**pl
;
179 struct elt_list
*l
= *pl
;
182 l
->next
= empty_elt_lists
;
186 /* Likewise for elt_loc_lists. */
189 unchain_one_elt_loc_list (pl
)
190 struct elt_loc_list
**pl
;
192 struct elt_loc_list
*l
= *pl
;
195 l
->next
= empty_elt_loc_lists
;
196 empty_elt_loc_lists
= l
;
199 /* Likewise for cselib_vals. This also frees the addr_list associated with
203 unchain_one_value (v
)
207 unchain_one_elt_list (&v
->addr_list
);
209 v
->u
.next_free
= empty_vals
;
213 /* Remove all entries from the hash table. Also used during
214 initialization. If CLEAR_ALL isn't set, then only clear the entries
215 which are known to have been used. */
218 clear_table (clear_all
)
224 for (i
= 0; i
< cselib_nregs
; i
++)
227 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (used_regs
); i
++)
228 REG_VALUES (VARRAY_UINT (used_regs
, i
)) = 0;
230 VARRAY_POP_ALL (used_regs
);
232 htab_empty (hash_table
);
233 obstack_free (&cselib_obstack
, cselib_startobj
);
237 empty_elt_loc_lists
= 0;
238 n_useless_values
= 0;
240 next_unknown_value
= 0;
243 /* The equality test for our hash table. The first argument ENTRY is a table
244 element (i.e. a cselib_val), while the second arg X is an rtx. We know
245 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
246 CONST of an appropriate mode. */
249 entry_and_rtx_equal_p (entry
, x_arg
)
250 const void *entry
, *x_arg
;
252 struct elt_loc_list
*l
;
253 const cselib_val
*v
= (const cselib_val
*) entry
;
255 enum machine_mode mode
= GET_MODE (x
);
257 if (GET_CODE (x
) == CONST_INT
258 || (mode
== VOIDmode
&& GET_CODE (x
) == CONST_DOUBLE
))
260 if (mode
!= GET_MODE (v
->u
.val_rtx
))
263 /* Unwrap X if necessary. */
264 if (GET_CODE (x
) == CONST
265 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
266 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
269 /* We don't guarantee that distinct rtx's have different hash values,
270 so we need to do a comparison. */
271 for (l
= v
->locs
; l
; l
= l
->next
)
272 if (rtx_equal_for_cselib_p (l
->loc
, x
))
278 /* The hash function for our hash table. The value is always computed with
279 hash_rtx when adding an element; this function just extracts the hash
280 value from a cselib_val structure. */
283 get_value_hash (entry
)
286 const cselib_val
*v
= (const cselib_val
*) entry
;
290 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
291 only return true for values which point to a cselib_val whose value
292 element has been set to zero, which implies the cselib_val will be
296 references_value_p (x
, only_useless
)
300 enum rtx_code code
= GET_CODE (x
);
301 const char *fmt
= GET_RTX_FORMAT (code
);
304 if (GET_CODE (x
) == VALUE
305 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
308 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
310 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
312 else if (fmt
[i
] == 'E')
313 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
314 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
321 /* For all locations found in X, delete locations that reference useless
322 values (i.e. values without any location). Called through
326 discard_useless_locs (x
, info
)
328 void *info ATTRIBUTE_UNUSED
;
330 cselib_val
*v
= (cselib_val
*)*x
;
331 struct elt_loc_list
**p
= &v
->locs
;
332 int had_locs
= v
->locs
!= 0;
336 if (references_value_p ((*p
)->loc
, 1))
337 unchain_one_elt_loc_list (p
);
342 if (had_locs
&& v
->locs
== 0)
345 values_became_useless
= 1;
350 /* If X is a value with no locations, remove it from the hashtable. */
353 discard_useless_values (x
, info
)
355 void *info ATTRIBUTE_UNUSED
;
357 cselib_val
*v
= (cselib_val
*)*x
;
361 htab_clear_slot (hash_table
, x
);
362 unchain_one_value (v
);
369 /* Clean out useless values (i.e. those which no longer have locations
370 associated with them) from the hash table. */
373 remove_useless_values ()
375 /* First pass: eliminate locations that reference the value. That in
376 turn can make more values useless. */
379 values_became_useless
= 0;
380 htab_traverse (hash_table
, discard_useless_locs
, 0);
382 while (values_became_useless
);
384 /* Second pass: actually remove the values. */
385 htab_traverse (hash_table
, discard_useless_values
, 0);
387 if (n_useless_values
!= 0)
391 /* Return nonzero if we can prove that X and Y contain the same value, taking
392 our gathered information into account. */
395 rtx_equal_for_cselib_p (x
, y
)
402 if (GET_CODE (x
) == REG
|| GET_CODE (x
) == MEM
)
404 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
410 if (GET_CODE (y
) == REG
|| GET_CODE (y
) == MEM
)
412 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
421 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
422 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
424 if (GET_CODE (x
) == VALUE
)
426 cselib_val
*e
= CSELIB_VAL_PTR (x
);
427 struct elt_loc_list
*l
;
429 for (l
= e
->locs
; l
; l
= l
->next
)
433 /* Avoid infinite recursion. */
434 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
436 else if (rtx_equal_for_cselib_p (t
, y
))
443 if (GET_CODE (y
) == VALUE
)
445 cselib_val
*e
= CSELIB_VAL_PTR (y
);
446 struct elt_loc_list
*l
;
448 for (l
= e
->locs
; l
; l
= l
->next
)
452 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
454 else if (rtx_equal_for_cselib_p (x
, t
))
461 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
464 /* This won't be handled correctly by the code below. */
465 if (GET_CODE (x
) == LABEL_REF
)
466 return XEXP (x
, 0) == XEXP (y
, 0);
469 fmt
= GET_RTX_FORMAT (code
);
471 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
478 if (XWINT (x
, i
) != XWINT (y
, i
))
484 if (XINT (x
, i
) != XINT (y
, i
))
490 /* Two vectors must have the same length. */
491 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
494 /* And the corresponding elements must match. */
495 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
496 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
502 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
508 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
513 /* These are just backpointers, so they don't matter. */
520 /* It is believed that rtx's at this level will never
521 contain anything but integers and other rtx's,
522 except for within LABEL_REFs and SYMBOL_REFs. */
530 /* We need to pass down the mode of constants through the hash table
531 functions. For that purpose, wrap them in a CONST of the appropriate
534 wrap_constant (mode
, x
)
535 enum machine_mode mode
;
538 if (GET_CODE (x
) != CONST_INT
539 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
541 if (mode
== VOIDmode
)
543 return gen_rtx_CONST (mode
, x
);
546 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
547 For registers and memory locations, we look up their cselib_val structure
548 and return its VALUE element.
549 Possible reasons for return 0 are: the object is volatile, or we couldn't
550 find a register or memory location in the table and CREATE is zero. If
551 CREATE is nonzero, table elts are created for regs and mem.
552 MODE is used in hashing for CONST_INTs only;
553 otherwise the mode of X is used. */
556 hash_rtx (x
, mode
, create
)
558 enum machine_mode mode
;
565 unsigned int hash
= 0;
568 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
574 e
= cselib_lookup (x
, GET_MODE (x
), create
);
581 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
582 return hash
? hash
: (unsigned int) CONST_INT
;
585 /* This is like the general case, except that it only counts
586 the integers representing the constant. */
587 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
588 if (GET_MODE (x
) != VOIDmode
)
589 for (i
= 2; i
< GET_RTX_LENGTH (CONST_DOUBLE
); i
++)
590 hash
+= XWINT (x
, i
);
592 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
593 + (unsigned) CONST_DOUBLE_HIGH (x
));
594 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
596 /* Assume there is only one rtx object for any given label. */
599 += ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
600 return hash
? hash
: (unsigned int) LABEL_REF
;
604 += ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
605 return hash
? hash
: (unsigned int) SYMBOL_REF
;
616 case UNSPEC_VOLATILE
:
620 if (MEM_VOLATILE_P (x
))
629 i
= GET_RTX_LENGTH (code
) - 1;
630 fmt
= GET_RTX_FORMAT (code
);
635 rtx tem
= XEXP (x
, i
);
636 unsigned int tem_hash
= hash_rtx (tem
, 0, create
);
643 else if (fmt
[i
] == 'E')
644 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
646 unsigned int tem_hash
= hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
653 else if (fmt
[i
] == 's')
655 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
661 else if (fmt
[i
] == 'i')
663 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
669 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
672 /* Create a new value structure for VALUE and initialize it. The mode of the
676 new_cselib_val (value
, mode
)
678 enum machine_mode mode
;
680 cselib_val
*e
= empty_vals
;
683 empty_vals
= e
->u
.next_free
;
685 e
= (cselib_val
*) obstack_alloc (&cselib_obstack
, sizeof (cselib_val
));
691 e
->u
.val_rtx
= gen_rtx_VALUE (mode
);
692 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
698 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
699 contains the data at this address. X is a MEM that represents the
700 value. Update the two value structures to represent this situation. */
703 add_mem_for_addr (addr_elt
, mem_elt
, x
)
704 cselib_val
*addr_elt
, *mem_elt
;
707 struct elt_loc_list
*l
;
709 /* Avoid duplicates. */
710 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
711 if (GET_CODE (l
->loc
) == MEM
712 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
715 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
717 = new_elt_loc_list (mem_elt
->locs
,
718 replace_equiv_address_nv (x
, addr_elt
->u
.val_rtx
));
721 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
722 If CREATE, make a new one if we haven't seen it before. */
725 cselib_lookup_mem (x
, create
)
729 enum machine_mode mode
= GET_MODE (x
);
735 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
736 || (FLOAT_MODE_P (mode
) && flag_float_store
))
739 /* Look up the value for the address. */
740 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
744 /* Find a value that describes a value of our mode at that address. */
745 for (l
= addr
->addr_list
; l
; l
= l
->next
)
746 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
752 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
753 add_mem_for_addr (addr
, mem_elt
, x
);
754 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
755 mem_elt
->value
, INSERT
);
760 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
761 with VALUE expressions. This way, it becomes independent of changes
762 to registers and memory.
763 X isn't actually modified; if modifications are needed, new rtl is
764 allocated. However, the return value can share rtl with X. */
767 cselib_subst_to_values (x
)
770 enum rtx_code code
= GET_CODE (x
);
771 const char *fmt
= GET_RTX_FORMAT (code
);
780 for (l
= REG_VALUES (REGNO (x
)); l
; l
= l
->next
)
781 if (GET_MODE (l
->elt
->u
.val_rtx
) == GET_MODE (x
))
782 return l
->elt
->u
.val_rtx
;
787 e
= cselib_lookup_mem (x
, 0);
790 /* This happens for autoincrements. Assign a value that doesn't
792 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
806 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
813 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
817 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
819 if (t
!= XEXP (x
, i
) && x
== copy
)
820 copy
= shallow_copy_rtx (x
);
824 else if (fmt
[i
] == 'E')
828 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
830 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
832 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
835 copy
= shallow_copy_rtx (x
);
837 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
838 for (k
= 0; k
< j
; k
++)
839 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
842 XVECEXP (copy
, i
, j
) = t
;
850 /* Look up the rtl expression X in our tables and return the value it has.
851 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
852 we create a new one if possible, using mode MODE if X doesn't have a mode
853 (i.e. because it's a constant). */
856 cselib_lookup (x
, mode
, create
)
858 enum machine_mode mode
;
863 unsigned int hashval
;
865 if (GET_MODE (x
) != VOIDmode
)
868 if (GET_CODE (x
) == VALUE
)
869 return CSELIB_VAL_PTR (x
);
871 if (GET_CODE (x
) == REG
)
874 unsigned int i
= REGNO (x
);
876 for (l
= REG_VALUES (i
); l
; l
= l
->next
)
877 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
883 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
884 e
->locs
= new_elt_loc_list (e
->locs
, x
);
885 if (REG_VALUES (i
) == 0)
886 VARRAY_PUSH_UINT (used_regs
, i
);
887 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), e
);
888 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
893 if (GET_CODE (x
) == MEM
)
894 return cselib_lookup_mem (x
, create
);
896 hashval
= hash_rtx (x
, mode
, create
);
897 /* Can't even create if hashing is not possible. */
901 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
902 hashval
, create
? INSERT
: NO_INSERT
);
906 e
= (cselib_val
*) *slot
;
910 e
= new_cselib_val (hashval
, mode
);
912 /* We have to fill the slot before calling cselib_subst_to_values:
913 the hash table is inconsistent until we do so, and
914 cselib_subst_to_values will need to do lookups. */
916 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
920 /* Invalidate any entries in reg_values that overlap REGNO. This is called
921 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
922 is used to determine how many hard registers are being changed. If MODE
923 is VOIDmode, then only REGNO is being changed; this is used when
924 invalidating call clobbered registers across a call. */
927 cselib_invalidate_regno (regno
, mode
)
929 enum machine_mode mode
;
931 unsigned int endregno
;
934 /* If we see pseudos after reload, something is _wrong_. */
935 if (reload_completed
&& regno
>= FIRST_PSEUDO_REGISTER
936 && reg_renumber
[regno
] >= 0)
939 /* Determine the range of registers that must be invalidated. For
940 pseudos, only REGNO is affected. For hard regs, we must take MODE
941 into account, and we must also invalidate lower register numbers
942 if they contain values that overlap REGNO. */
943 endregno
= regno
+ 1;
944 if (regno
< FIRST_PSEUDO_REGISTER
&& mode
!= VOIDmode
)
945 endregno
= regno
+ HARD_REGNO_NREGS (regno
, mode
);
947 for (i
= 0; i
< endregno
; i
++)
949 struct elt_list
**l
= ®_VALUES (i
);
951 /* Go through all known values for this reg; if it overlaps the range
952 we're invalidating, remove the value. */
955 cselib_val
*v
= (*l
)->elt
;
956 struct elt_loc_list
**p
;
957 unsigned int this_last
= i
;
959 if (i
< FIRST_PSEUDO_REGISTER
)
960 this_last
+= HARD_REGNO_NREGS (i
, GET_MODE (v
->u
.val_rtx
)) - 1;
962 if (this_last
< regno
)
968 /* We have an overlap. */
969 unchain_one_elt_list (l
);
971 /* Now, we clear the mapping from value to reg. It must exist, so
972 this code will crash intentionally if it doesn't. */
973 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
977 if (GET_CODE (x
) == REG
&& REGNO (x
) == i
)
979 unchain_one_elt_loc_list (p
);
989 /* The memory at address MEM_BASE is being changed.
990 Return whether this change will invalidate VAL. */
993 cselib_mem_conflict_p (mem_base
, val
)
1001 code
= GET_CODE (val
);
1004 /* Get rid of a few simple cases quickly. */
1017 if (GET_MODE (mem_base
) == BLKmode
1018 || GET_MODE (val
) == BLKmode
1019 || anti_dependence (val
, mem_base
))
1022 /* The address may contain nested MEMs. */
1029 fmt
= GET_RTX_FORMAT (code
);
1030 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1034 if (cselib_mem_conflict_p (mem_base
, XEXP (val
, i
)))
1037 else if (fmt
[i
] == 'E')
1038 for (j
= 0; j
< XVECLEN (val
, i
); j
++)
1039 if (cselib_mem_conflict_p (mem_base
, XVECEXP (val
, i
, j
)))
1046 /* For the value found in SLOT, walk its locations to determine if any overlap
1047 INFO (which is a MEM rtx). */
1050 cselib_invalidate_mem_1 (slot
, info
)
1054 cselib_val
*v
= (cselib_val
*) *slot
;
1055 rtx mem_rtx
= (rtx
) info
;
1056 struct elt_loc_list
**p
= &v
->locs
;
1057 int had_locs
= v
->locs
!= 0;
1063 struct elt_list
**mem_chain
;
1065 /* MEMs may occur in locations only at the top level; below
1066 that every MEM or REG is substituted by its VALUE. */
1067 if (GET_CODE (x
) != MEM
1068 || ! cselib_mem_conflict_p (mem_rtx
, x
))
1074 /* This one overlaps. */
1075 /* We must have a mapping from this MEM's address to the
1076 value (E). Remove that, too. */
1077 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1078 mem_chain
= &addr
->addr_list
;
1081 if ((*mem_chain
)->elt
== v
)
1083 unchain_one_elt_list (mem_chain
);
1087 mem_chain
= &(*mem_chain
)->next
;
1090 unchain_one_elt_loc_list (p
);
1093 if (had_locs
&& v
->locs
== 0)
1099 /* Invalidate any locations in the table which are changed because of a
1100 store to MEM_RTX. If this is called because of a non-const call
1101 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1104 cselib_invalidate_mem (mem_rtx
)
1107 htab_traverse (hash_table
, cselib_invalidate_mem_1
, mem_rtx
);
1110 /* Invalidate DEST, which is being assigned to or clobbered. The second and
1111 the third parameter exist so that this function can be passed to
1112 note_stores; they are ignored. */
1115 cselib_invalidate_rtx (dest
, ignore
, data
)
1117 rtx ignore ATTRIBUTE_UNUSED
;
1118 void *data ATTRIBUTE_UNUSED
;
1120 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SIGN_EXTRACT
1121 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
)
1122 dest
= XEXP (dest
, 0);
1124 if (GET_CODE (dest
) == REG
)
1125 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1126 else if (GET_CODE (dest
) == MEM
)
1127 cselib_invalidate_mem (dest
);
1129 /* Some machines don't define AUTO_INC_DEC, but they still use push
1130 instructions. We need to catch that case here in order to
1131 invalidate the stack pointer correctly. Note that invalidating
1132 the stack pointer is different from invalidating DEST. */
1133 if (push_operand (dest
, GET_MODE (dest
)))
1134 cselib_invalidate_rtx (stack_pointer_rtx
, NULL_RTX
, NULL
);
1137 /* Record the result of a SET instruction. DEST is being set; the source
1138 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1139 describes its address. */
1142 cselib_record_set (dest
, src_elt
, dest_addr_elt
)
1144 cselib_val
*src_elt
, *dest_addr_elt
;
1146 int dreg
= GET_CODE (dest
) == REG
? (int) REGNO (dest
) : -1;
1148 if (src_elt
== 0 || side_effects_p (dest
))
1153 if (REG_VALUES (dreg
) == 0)
1154 VARRAY_PUSH_UINT (used_regs
, dreg
);
1156 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1157 if (src_elt
->locs
== 0)
1159 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1161 else if (GET_CODE (dest
) == MEM
&& dest_addr_elt
!= 0)
1163 if (src_elt
->locs
== 0)
1165 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1169 /* Describe a single set that is part of an insn. */
1174 cselib_val
*src_elt
;
1175 cselib_val
*dest_addr_elt
;
1178 /* There is no good way to determine how many elements there can be
1179 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1180 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1182 /* Record the effects of any sets in INSN. */
1184 cselib_record_sets (insn
)
1189 struct set sets
[MAX_SETS
];
1190 rtx body
= PATTERN (insn
);
1193 body
= PATTERN (insn
);
1194 if (GET_CODE (body
) == COND_EXEC
)
1196 cond
= COND_EXEC_TEST (body
);
1197 body
= COND_EXEC_CODE (body
);
1200 /* Find all sets. */
1201 if (GET_CODE (body
) == SET
)
1203 sets
[0].src
= SET_SRC (body
);
1204 sets
[0].dest
= SET_DEST (body
);
1207 else if (GET_CODE (body
) == PARALLEL
)
1209 /* Look through the PARALLEL and record the values being
1210 set, if possible. Also handle any CLOBBERs. */
1211 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1213 rtx x
= XVECEXP (body
, 0, i
);
1215 if (GET_CODE (x
) == SET
)
1217 sets
[n_sets
].src
= SET_SRC (x
);
1218 sets
[n_sets
].dest
= SET_DEST (x
);
1224 /* Look up the values that are read. Do this before invalidating the
1225 locations that are written. */
1226 for (i
= 0; i
< n_sets
; i
++)
1228 rtx dest
= sets
[i
].dest
;
1230 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1231 the low part after invalidating any knowledge about larger modes. */
1232 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1233 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1235 /* We don't know how to record anything but REG or MEM. */
1236 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1238 rtx src
= sets
[i
].src
;
1240 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (src
), cond
, src
, dest
);
1241 sets
[i
].src_elt
= cselib_lookup (sets
[i
].src
, GET_MODE (dest
), 1);
1242 if (GET_CODE (dest
) == MEM
)
1243 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1245 sets
[i
].dest_addr_elt
= 0;
1249 /* Invalidate all locations written by this insn. Note that the elts we
1250 looked up in the previous loop aren't affected, just some of their
1251 locations may go away. */
1252 note_stores (body
, cselib_invalidate_rtx
, NULL
);
1254 /* Now enter the equivalences in our tables. */
1255 for (i
= 0; i
< n_sets
; i
++)
1257 rtx dest
= sets
[i
].dest
;
1258 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1259 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1263 /* Record the effects of INSN. */
1266 cselib_process_insn (insn
)
1272 cselib_current_insn
= insn
;
1274 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1275 if (GET_CODE (insn
) == CODE_LABEL
1276 || (GET_CODE (insn
) == CALL_INSN
1277 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1278 || (GET_CODE (insn
) == INSN
1279 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1280 && MEM_VOLATILE_P (PATTERN (insn
))))
1286 if (! INSN_P (insn
))
1288 cselib_current_insn
= 0;
1292 /* If this is a call instruction, forget anything stored in a
1293 call clobbered register, or, if this is not a const call, in
1295 if (GET_CODE (insn
) == CALL_INSN
)
1297 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1298 if (call_used_regs
[i
])
1299 cselib_invalidate_regno (i
, VOIDmode
);
1301 if (! CONST_OR_PURE_CALL_P (insn
))
1302 cselib_invalidate_mem (callmem
);
1305 cselib_record_sets (insn
);
1308 /* Clobber any registers which appear in REG_INC notes. We
1309 could keep track of the changes to their values, but it is
1310 unlikely to help. */
1311 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1312 if (REG_NOTE_KIND (x
) == REG_INC
)
1313 cselib_invalidate_rtx (XEXP (x
, 0), NULL_RTX
, NULL
);
1316 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1317 after we have processed the insn. */
1318 if (GET_CODE (insn
) == CALL_INSN
)
1319 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1320 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1321 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0), NULL_RTX
, NULL
);
1323 cselib_current_insn
= 0;
1325 if (n_useless_values
> MAX_USELESS_VALUES
)
1326 remove_useless_values ();
1329 /* Make sure our varrays are big enough. Not called from any cselib routines;
1330 it must be called by the user if it allocated new registers. */
1333 cselib_update_varray_sizes ()
1335 unsigned int nregs
= max_reg_num ();
1337 if (nregs
== cselib_nregs
)
1340 cselib_nregs
= nregs
;
1341 VARRAY_GROW (reg_values
, nregs
);
1342 VARRAY_GROW (used_regs
, nregs
);
1345 /* Initialize cselib for one pass. The caller must also call
1346 init_alias_analysis. */
1351 /* These are only created once. */
1354 gcc_obstack_init (&cselib_obstack
);
1355 cselib_startobj
= obstack_alloc (&cselib_obstack
, 0);
1357 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1358 ggc_add_rtx_root (&callmem
, 1);
1361 cselib_nregs
= max_reg_num ();
1362 VARRAY_ELT_LIST_INIT (reg_values
, cselib_nregs
, "reg_values");
1363 VARRAY_UINT_INIT (used_regs
, cselib_nregs
, "used_regs");
1364 hash_table
= htab_create (31, get_value_hash
, entry_and_rtx_equal_p
, NULL
);
1368 /* Called when the current user is done with cselib. */
1374 VARRAY_FREE (reg_values
);
1375 VARRAY_FREE (used_regs
);
1376 htab_delete (hash_table
);