1 /* Common subexpression elimination library for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
43 #include "alloc-pool.h"
45 static int entry_and_rtx_equal_p (const void *, const void *);
46 static hashval_t
get_value_hash (const void *);
47 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
48 static struct elt_loc_list
*new_elt_loc_list (struct elt_loc_list
*, rtx
);
49 static void unchain_one_value (cselib_val
*);
50 static void unchain_one_elt_list (struct elt_list
**);
51 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
52 static void clear_table (void);
53 static int discard_useless_locs (void **, void *);
54 static int discard_useless_values (void **, void *);
55 static void remove_useless_values (void);
56 static rtx
wrap_constant (enum machine_mode
, rtx
);
57 static unsigned int hash_rtx (rtx
, enum machine_mode
, int);
58 static cselib_val
*new_cselib_val (unsigned int, enum machine_mode
);
59 static void add_mem_for_addr (cselib_val
*, cselib_val
*, rtx
);
60 static cselib_val
*cselib_lookup_mem (rtx
, int);
61 static void cselib_invalidate_regno (unsigned int, enum machine_mode
);
62 static void cselib_invalidate_mem (rtx
);
63 static void cselib_invalidate_rtx (rtx
, rtx
, void *);
64 static void cselib_record_set (rtx
, cselib_val
*, cselib_val
*);
65 static void cselib_record_sets (rtx
);
67 /* There are three ways in which cselib can look up an rtx:
68 - for a REG, the reg_values table (which is indexed by regno) is used
69 - for a MEM, we recursively look up its address and then follow the
70 addr_list of that value
71 - for everything else, we compute a hash value and go through the hash
72 table. Since different rtx's can still have the same hash value,
73 this involves walking the table entries for a given value and comparing
74 the locations of the entries with the rtx we are looking up. */
76 /* A table that enables us to look up elts by their value. */
77 static htab_t hash_table
;
79 /* This is a global so we don't have to pass this through every function.
80 It is used in new_elt_loc_list to set SETTING_INSN. */
81 static rtx cselib_current_insn
;
82 static bool cselib_current_insn_in_libcall
;
84 /* Every new unknown value gets a unique number. */
85 static unsigned int next_unknown_value
;
87 /* The number of registers we had when the varrays were last resized. */
88 static unsigned int cselib_nregs
;
90 /* Count values without known locations. Whenever this grows too big, we
91 remove these useless values from the table. */
92 static int n_useless_values
;
94 /* Number of useless values before we remove them from the hash table. */
95 #define MAX_USELESS_VALUES 32
97 /* This table maps from register number to values. It does not
98 contain pointers to cselib_val structures, but rather elt_lists.
99 The purpose is to be able to refer to the same register in
100 different modes. The first element of the list defines the mode in
101 which the register was set; if the mode is unknown or the value is
102 no longer valid in that mode, ELT will be NULL for the first
104 struct elt_list
**reg_values
;
105 unsigned int reg_values_size
;
106 #define REG_VALUES(i) reg_values[i]
108 /* The largest number of hard regs used by any entry added to the
109 REG_VALUES table. Cleared on each clear_table() invocation. */
110 static unsigned int max_value_regs
;
112 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
113 in clear_table() for fast emptying. */
114 static unsigned int *used_regs
;
115 static unsigned int n_used_regs
;
117 /* We pass this to cselib_invalidate_mem to invalidate all of
118 memory for a non-const call instruction. */
119 static GTY(()) rtx callmem
;
121 /* Set by discard_useless_locs if it deleted the last location of any
123 static int values_became_useless
;
125 /* Used as stop element of the containing_mem list so we can check
126 presence in the list by checking the next pointer. */
127 static cselib_val dummy_val
;
129 /* Used to list all values that contain memory reference.
130 May or may not contain the useless values - the list is compacted
131 each time memory is invalidated. */
132 static cselib_val
*first_containing_mem
= &dummy_val
;
133 static alloc_pool elt_loc_list_pool
, elt_list_pool
, cselib_val_pool
, value_pool
;
136 /* Allocate a struct elt_list and fill in its two elements with the
139 static inline struct elt_list
*
140 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
143 el
= pool_alloc (elt_list_pool
);
149 /* Allocate a struct elt_loc_list and fill in its two elements with the
152 static inline struct elt_loc_list
*
153 new_elt_loc_list (struct elt_loc_list
*next
, rtx loc
)
155 struct elt_loc_list
*el
;
156 el
= pool_alloc (elt_loc_list_pool
);
159 el
->canon_loc
= NULL
;
160 el
->setting_insn
= cselib_current_insn
;
161 el
->in_libcall
= cselib_current_insn_in_libcall
;
165 /* The elt_list at *PL is no longer needed. Unchain it and free its
169 unchain_one_elt_list (struct elt_list
**pl
)
171 struct elt_list
*l
= *pl
;
174 pool_free (elt_list_pool
, l
);
177 /* Likewise for elt_loc_lists. */
180 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
182 struct elt_loc_list
*l
= *pl
;
185 pool_free (elt_loc_list_pool
, l
);
188 /* Likewise for cselib_vals. This also frees the addr_list associated with
192 unchain_one_value (cselib_val
*v
)
195 unchain_one_elt_list (&v
->addr_list
);
197 pool_free (cselib_val_pool
, v
);
200 /* Remove all entries from the hash table. Also used during
201 initialization. If CLEAR_ALL isn't set, then only clear the entries
202 which are known to have been used. */
209 for (i
= 0; i
< n_used_regs
; i
++)
210 REG_VALUES (used_regs
[i
]) = 0;
216 htab_empty (hash_table
);
218 n_useless_values
= 0;
220 next_unknown_value
= 0;
222 first_containing_mem
= &dummy_val
;
225 /* The equality test for our hash table. The first argument ENTRY is a table
226 element (i.e. a cselib_val), while the second arg X is an rtx. We know
227 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
228 CONST of an appropriate mode. */
231 entry_and_rtx_equal_p (const void *entry
, const void *x_arg
)
233 struct elt_loc_list
*l
;
234 const cselib_val
*v
= (const cselib_val
*) entry
;
236 enum machine_mode mode
= GET_MODE (x
);
238 if (GET_CODE (x
) == CONST_INT
239 || (mode
== VOIDmode
&& GET_CODE (x
) == CONST_DOUBLE
))
241 if (mode
!= GET_MODE (v
->u
.val_rtx
))
244 /* Unwrap X if necessary. */
245 if (GET_CODE (x
) == CONST
246 && (GET_CODE (XEXP (x
, 0)) == CONST_INT
247 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
250 /* We don't guarantee that distinct rtx's have different hash values,
251 so we need to do a comparison. */
252 for (l
= v
->locs
; l
; l
= l
->next
)
253 if (rtx_equal_for_cselib_p (l
->loc
, x
))
259 /* The hash function for our hash table. The value is always computed with
260 hash_rtx when adding an element; this function just extracts the hash
261 value from a cselib_val structure. */
264 get_value_hash (const void *entry
)
266 const cselib_val
*v
= (const cselib_val
*) entry
;
270 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
271 only return true for values which point to a cselib_val whose value
272 element has been set to zero, which implies the cselib_val will be
276 references_value_p (rtx x
, int only_useless
)
278 enum rtx_code code
= GET_CODE (x
);
279 const char *fmt
= GET_RTX_FORMAT (code
);
282 if (GET_CODE (x
) == VALUE
283 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
286 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
288 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
290 else if (fmt
[i
] == 'E')
291 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
292 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
299 /* For all locations found in X, delete locations that reference useless
300 values (i.e. values without any location). Called through
304 discard_useless_locs (void **x
, void *info ATTRIBUTE_UNUSED
)
306 cselib_val
*v
= (cselib_val
*)*x
;
307 struct elt_loc_list
**p
= &v
->locs
;
308 int had_locs
= v
->locs
!= 0;
312 if (references_value_p ((*p
)->loc
, 1))
313 unchain_one_elt_loc_list (p
);
318 if (had_locs
&& v
->locs
== 0)
321 values_became_useless
= 1;
326 /* If X is a value with no locations, remove it from the hashtable. */
329 discard_useless_values (void **x
, void *info ATTRIBUTE_UNUSED
)
331 cselib_val
*v
= (cselib_val
*)*x
;
335 CSELIB_VAL_PTR (v
->u
.val_rtx
) = NULL
;
336 htab_clear_slot (hash_table
, x
);
337 unchain_one_value (v
);
344 /* Clean out useless values (i.e. those which no longer have locations
345 associated with them) from the hash table. */
348 remove_useless_values (void)
351 /* First pass: eliminate locations that reference the value. That in
352 turn can make more values useless. */
355 values_became_useless
= 0;
356 htab_traverse (hash_table
, discard_useless_locs
, 0);
358 while (values_became_useless
);
360 /* Second pass: actually remove the values. */
362 p
= &first_containing_mem
;
363 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
367 p
= &(*p
)->next_containing_mem
;
371 htab_traverse (hash_table
, discard_useless_values
, 0);
373 if (n_useless_values
!= 0)
377 /* Return the mode in which a register was last set. If X is not a
378 register, return its mode. If the mode in which the register was
379 set is not known, or the value was already clobbered, return
383 cselib_reg_set_mode (rtx x
)
385 if (GET_CODE (x
) != REG
)
388 if (REG_VALUES (REGNO (x
)) == NULL
389 || REG_VALUES (REGNO (x
))->elt
== NULL
)
392 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->u
.val_rtx
);
395 /* Return nonzero if we can prove that X and Y contain the same value, taking
396 our gathered information into account. */
399 rtx_equal_for_cselib_p (rtx x
, rtx y
)
405 if (GET_CODE (x
) == REG
|| GET_CODE (x
) == MEM
)
407 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
413 if (GET_CODE (y
) == REG
|| GET_CODE (y
) == MEM
)
415 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
424 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
425 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
427 if (GET_CODE (x
) == VALUE
)
429 cselib_val
*e
= CSELIB_VAL_PTR (x
);
430 struct elt_loc_list
*l
;
432 for (l
= e
->locs
; l
; l
= l
->next
)
436 /* Avoid infinite recursion. */
437 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
439 else if (rtx_equal_for_cselib_p (t
, y
))
446 if (GET_CODE (y
) == VALUE
)
448 cselib_val
*e
= CSELIB_VAL_PTR (y
);
449 struct elt_loc_list
*l
;
451 for (l
= e
->locs
; l
; l
= l
->next
)
455 if (GET_CODE (t
) == REG
|| GET_CODE (t
) == MEM
)
457 else if (rtx_equal_for_cselib_p (x
, t
))
464 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
467 /* This won't be handled correctly by the code below. */
468 if (GET_CODE (x
) == LABEL_REF
)
469 return XEXP (x
, 0) == XEXP (y
, 0);
472 fmt
= GET_RTX_FORMAT (code
);
474 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
481 if (XWINT (x
, i
) != XWINT (y
, i
))
487 if (XINT (x
, i
) != XINT (y
, i
))
493 /* Two vectors must have the same length. */
494 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
497 /* And the corresponding elements must match. */
498 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
499 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
505 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
511 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
516 /* These are just backpointers, so they don't matter. */
523 /* It is believed that rtx's at this level will never
524 contain anything but integers and other rtx's,
525 except for within LABEL_REFs and SYMBOL_REFs. */
533 /* We need to pass down the mode of constants through the hash table
534 functions. For that purpose, wrap them in a CONST of the appropriate
537 wrap_constant (enum machine_mode mode
, rtx x
)
539 if (GET_CODE (x
) != CONST_INT
540 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
542 if (mode
== VOIDmode
)
544 return gen_rtx_CONST (mode
, x
);
547 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
548 For registers and memory locations, we look up their cselib_val structure
549 and return its VALUE element.
550 Possible reasons for return 0 are: the object is volatile, or we couldn't
551 find a register or memory location in the table and CREATE is zero. If
552 CREATE is nonzero, table elts are created for regs and mem.
553 MODE is used in hashing for CONST_INTs only;
554 otherwise the mode of X is used. */
557 hash_rtx (rtx x
, enum machine_mode mode
, int create
)
563 unsigned int hash
= 0;
566 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
572 e
= cselib_lookup (x
, GET_MODE (x
), create
);
579 hash
+= ((unsigned) CONST_INT
<< 7) + (unsigned) mode
+ INTVAL (x
);
580 return hash
? hash
: (unsigned int) CONST_INT
;
583 /* This is like the general case, except that it only counts
584 the integers representing the constant. */
585 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
586 if (GET_MODE (x
) != VOIDmode
)
587 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
589 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
590 + (unsigned) CONST_DOUBLE_HIGH (x
));
591 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
598 units
= CONST_VECTOR_NUNITS (x
);
600 for (i
= 0; i
< units
; ++i
)
602 elt
= CONST_VECTOR_ELT (x
, i
);
603 hash
+= hash_rtx (elt
, GET_MODE (elt
), 0);
609 /* Assume there is only one rtx object for any given label. */
612 += ((unsigned) LABEL_REF
<< 7) + (unsigned long) XEXP (x
, 0);
613 return hash
? hash
: (unsigned int) LABEL_REF
;
617 += ((unsigned) SYMBOL_REF
<< 7) + (unsigned long) XSTR (x
, 0);
618 return hash
? hash
: (unsigned int) SYMBOL_REF
;
629 case UNSPEC_VOLATILE
:
633 if (MEM_VOLATILE_P (x
))
642 i
= GET_RTX_LENGTH (code
) - 1;
643 fmt
= GET_RTX_FORMAT (code
);
648 rtx tem
= XEXP (x
, i
);
649 unsigned int tem_hash
= hash_rtx (tem
, 0, create
);
656 else if (fmt
[i
] == 'E')
657 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
659 unsigned int tem_hash
= hash_rtx (XVECEXP (x
, i
, j
), 0, create
);
666 else if (fmt
[i
] == 's')
668 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
674 else if (fmt
[i
] == 'i')
676 else if (fmt
[i
] == '0' || fmt
[i
] == 't')
682 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
685 /* Create a new value structure for VALUE and initialize it. The mode of the
688 static inline cselib_val
*
689 new_cselib_val (unsigned int value
, enum machine_mode mode
)
691 cselib_val
*e
= pool_alloc (cselib_val_pool
);
693 #ifdef ENABLE_CHECKING
699 /* We use custom method to allocate this RTL construct because it accounts
700 about 8% of overall memory usage. */
701 e
->u
.val_rtx
= pool_alloc (value_pool
);
702 memset (e
->u
.val_rtx
, 0, RTX_HDR_SIZE
);
703 PUT_CODE (e
->u
.val_rtx
, VALUE
);
704 PUT_MODE (e
->u
.val_rtx
, mode
);
705 CSELIB_VAL_PTR (e
->u
.val_rtx
) = e
;
708 e
->next_containing_mem
= 0;
712 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
713 contains the data at this address. X is a MEM that represents the
714 value. Update the two value structures to represent this situation. */
717 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
719 struct elt_loc_list
*l
;
721 /* Avoid duplicates. */
722 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
723 if (GET_CODE (l
->loc
) == MEM
724 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
727 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
729 = new_elt_loc_list (mem_elt
->locs
,
730 replace_equiv_address_nv (x
, addr_elt
->u
.val_rtx
));
731 if (mem_elt
->next_containing_mem
== NULL
)
733 mem_elt
->next_containing_mem
= first_containing_mem
;
734 first_containing_mem
= mem_elt
;
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 (rtx x
, int create
)
744 enum machine_mode mode
= GET_MODE (x
);
750 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
751 || (FLOAT_MODE_P (mode
) && flag_float_store
))
754 /* Look up the value for the address. */
755 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
759 /* Find a value that describes a value of our mode at that address. */
760 for (l
= addr
->addr_list
; l
; l
= l
->next
)
761 if (GET_MODE (l
->elt
->u
.val_rtx
) == mode
)
767 mem_elt
= new_cselib_val (++next_unknown_value
, mode
);
768 add_mem_for_addr (addr
, mem_elt
, x
);
769 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
770 mem_elt
->value
, INSERT
);
775 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
776 with VALUE expressions. This way, it becomes independent of changes
777 to registers and memory.
778 X isn't actually modified; if modifications are needed, new rtl is
779 allocated. However, the return value can share rtl with X. */
782 cselib_subst_to_values (rtx x
)
784 enum rtx_code code
= GET_CODE (x
);
785 const char *fmt
= GET_RTX_FORMAT (code
);
794 l
= REG_VALUES (REGNO (x
));
795 if (l
&& l
->elt
== NULL
)
797 for (; 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);
807 /* This happens for autoincrements. Assign a value that doesn't
809 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
824 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
831 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
835 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
837 if (t
!= XEXP (x
, i
) && x
== copy
)
838 copy
= shallow_copy_rtx (x
);
842 else if (fmt
[i
] == 'E')
846 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
848 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
850 if (t
!= XVECEXP (x
, i
, j
) && XVEC (x
, i
) == XVEC (copy
, i
))
853 copy
= shallow_copy_rtx (x
);
855 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (x
, i
));
856 for (k
= 0; k
< j
; k
++)
857 XVECEXP (copy
, i
, k
) = XVECEXP (x
, i
, k
);
860 XVECEXP (copy
, i
, j
) = t
;
868 /* Look up the rtl expression X in our tables and return the value it has.
869 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
870 we create a new one if possible, using mode MODE if X doesn't have a mode
871 (i.e. because it's a constant). */
874 cselib_lookup (rtx x
, enum machine_mode mode
, int create
)
878 unsigned int hashval
;
880 if (GET_MODE (x
) != VOIDmode
)
883 if (GET_CODE (x
) == VALUE
)
884 return CSELIB_VAL_PTR (x
);
886 if (GET_CODE (x
) == REG
)
889 unsigned int i
= REGNO (x
);
892 if (l
&& l
->elt
== NULL
)
894 for (; l
; l
= l
->next
)
895 if (mode
== GET_MODE (l
->elt
->u
.val_rtx
))
901 if (i
< FIRST_PSEUDO_REGISTER
)
903 unsigned int n
= hard_regno_nregs
[i
][mode
];
905 if (n
> max_value_regs
)
909 e
= new_cselib_val (++next_unknown_value
, GET_MODE (x
));
910 e
->locs
= new_elt_loc_list (e
->locs
, x
);
911 if (REG_VALUES (i
) == 0)
913 /* Maintain the invariant that the first entry of
914 REG_VALUES, if present, must be the value used to set the
915 register, or NULL. */
916 used_regs
[n_used_regs
++] = i
;
917 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
919 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
920 slot
= htab_find_slot_with_hash (hash_table
, x
, e
->value
, INSERT
);
925 if (GET_CODE (x
) == MEM
)
926 return cselib_lookup_mem (x
, create
);
928 hashval
= hash_rtx (x
, mode
, create
);
929 /* Can't even create if hashing is not possible. */
933 slot
= htab_find_slot_with_hash (hash_table
, wrap_constant (mode
, x
),
934 hashval
, create
? INSERT
: NO_INSERT
);
938 e
= (cselib_val
*) *slot
;
942 e
= new_cselib_val (hashval
, mode
);
944 /* We have to fill the slot before calling cselib_subst_to_values:
945 the hash table is inconsistent until we do so, and
946 cselib_subst_to_values will need to do lookups. */
948 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
952 /* Invalidate any entries in reg_values that overlap REGNO. This is called
953 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
954 is used to determine how many hard registers are being changed. If MODE
955 is VOIDmode, then only REGNO is being changed; this is used when
956 invalidating call clobbered registers across a call. */
959 cselib_invalidate_regno (unsigned int regno
, enum machine_mode mode
)
961 unsigned int endregno
;
964 /* If we see pseudos after reload, something is _wrong_. */
965 if (reload_completed
&& regno
>= FIRST_PSEUDO_REGISTER
966 && reg_renumber
[regno
] >= 0)
969 /* Determine the range of registers that must be invalidated. For
970 pseudos, only REGNO is affected. For hard regs, we must take MODE
971 into account, and we must also invalidate lower register numbers
972 if they contain values that overlap REGNO. */
973 if (regno
< FIRST_PSEUDO_REGISTER
)
975 if (mode
== VOIDmode
)
978 if (regno
< max_value_regs
)
981 i
= regno
- max_value_regs
;
983 endregno
= regno
+ hard_regno_nregs
[regno
][mode
];
988 endregno
= regno
+ 1;
991 for (; i
< endregno
; i
++)
993 struct elt_list
**l
= ®_VALUES (i
);
995 /* Go through all known values for this reg; if it overlaps the range
996 we're invalidating, remove the value. */
999 cselib_val
*v
= (*l
)->elt
;
1000 struct elt_loc_list
**p
;
1001 unsigned int this_last
= i
;
1003 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
1004 this_last
+= hard_regno_nregs
[i
][GET_MODE (v
->u
.val_rtx
)] - 1;
1006 if (this_last
< regno
|| v
== NULL
)
1012 /* We have an overlap. */
1013 if (*l
== REG_VALUES (i
))
1015 /* Maintain the invariant that the first entry of
1016 REG_VALUES, if present, must be the value used to set
1017 the register, or NULL. This is also nice because
1018 then we won't push the same regno onto user_regs
1024 unchain_one_elt_list (l
);
1026 /* Now, we clear the mapping from value to reg. It must exist, so
1027 this code will crash intentionally if it doesn't. */
1028 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
1032 if (GET_CODE (x
) == REG
&& REGNO (x
) == i
)
1034 unchain_one_elt_loc_list (p
);
1044 /* Return 1 if X has a value that can vary even between two
1045 executions of the program. 0 means X can be compared reliably
1046 against certain constants or near-constants. */
1049 cselib_rtx_varies_p (rtx x ATTRIBUTE_UNUSED
, int from_alias ATTRIBUTE_UNUSED
)
1051 /* We actually don't need to verify very hard. This is because
1052 if X has actually changed, we invalidate the memory anyway,
1053 so assume that all common memory addresses are
1058 /* Invalidate any locations in the table which are changed because of a
1059 store to MEM_RTX. If this is called because of a non-const call
1060 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1063 cselib_invalidate_mem (rtx mem_rtx
)
1065 cselib_val
**vp
, *v
, *next
;
1069 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
1070 mem_rtx
= canon_rtx (mem_rtx
);
1072 vp
= &first_containing_mem
;
1073 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
1075 bool has_mem
= false;
1076 struct elt_loc_list
**p
= &v
->locs
;
1077 int had_locs
= v
->locs
!= 0;
1082 rtx canon_x
= (*p
)->canon_loc
;
1084 struct elt_list
**mem_chain
;
1086 /* MEMs may occur in locations only at the top level; below
1087 that every MEM or REG is substituted by its VALUE. */
1088 if (GET_CODE (x
) != MEM
)
1094 canon_x
= (*p
)->canon_loc
= canon_rtx (x
);
1095 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
1096 && ! canon_true_dependence (mem_rtx
, GET_MODE (mem_rtx
), mem_addr
,
1097 x
, cselib_rtx_varies_p
))
1105 /* This one overlaps. */
1106 /* We must have a mapping from this MEM's address to the
1107 value (E). Remove that, too. */
1108 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1109 mem_chain
= &addr
->addr_list
;
1112 if ((*mem_chain
)->elt
== v
)
1114 unchain_one_elt_list (mem_chain
);
1118 mem_chain
= &(*mem_chain
)->next
;
1121 unchain_one_elt_loc_list (p
);
1124 if (had_locs
&& v
->locs
== 0)
1127 next
= v
->next_containing_mem
;
1131 vp
= &(*vp
)->next_containing_mem
;
1134 v
->next_containing_mem
= NULL
;
1139 /* Invalidate DEST, which is being assigned to or clobbered. The second and
1140 the third parameter exist so that this function can be passed to
1141 note_stores; they are ignored. */
1144 cselib_invalidate_rtx (rtx dest
, rtx ignore ATTRIBUTE_UNUSED
,
1145 void *data ATTRIBUTE_UNUSED
)
1147 while (GET_CODE (dest
) == STRICT_LOW_PART
|| GET_CODE (dest
) == SIGN_EXTRACT
1148 || GET_CODE (dest
) == ZERO_EXTRACT
|| GET_CODE (dest
) == SUBREG
)
1149 dest
= XEXP (dest
, 0);
1151 if (GET_CODE (dest
) == REG
)
1152 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1153 else if (GET_CODE (dest
) == MEM
)
1154 cselib_invalidate_mem (dest
);
1156 /* Some machines don't define AUTO_INC_DEC, but they still use push
1157 instructions. We need to catch that case here in order to
1158 invalidate the stack pointer correctly. Note that invalidating
1159 the stack pointer is different from invalidating DEST. */
1160 if (push_operand (dest
, GET_MODE (dest
)))
1161 cselib_invalidate_rtx (stack_pointer_rtx
, NULL_RTX
, NULL
);
1164 /* Record the result of a SET instruction. DEST is being set; the source
1165 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1166 describes its address. */
1169 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
1171 int dreg
= GET_CODE (dest
) == REG
? (int) REGNO (dest
) : -1;
1173 if (src_elt
== 0 || side_effects_p (dest
))
1178 if (dreg
< FIRST_PSEUDO_REGISTER
)
1180 unsigned int n
= hard_regno_nregs
[dreg
][GET_MODE (dest
)];
1182 if (n
> max_value_regs
)
1186 if (REG_VALUES (dreg
) == 0)
1188 used_regs
[n_used_regs
++] = dreg
;
1189 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1193 if (REG_VALUES (dreg
)->elt
== 0)
1194 REG_VALUES (dreg
)->elt
= src_elt
;
1196 /* The register should have been invalidated. */
1200 if (src_elt
->locs
== 0)
1202 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1204 else if (GET_CODE (dest
) == MEM
&& dest_addr_elt
!= 0)
1206 if (src_elt
->locs
== 0)
1208 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1212 /* Describe a single set that is part of an insn. */
1217 cselib_val
*src_elt
;
1218 cselib_val
*dest_addr_elt
;
1221 /* There is no good way to determine how many elements there can be
1222 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1223 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1225 /* Record the effects of any sets in INSN. */
1227 cselib_record_sets (rtx insn
)
1231 struct set sets
[MAX_SETS
];
1232 rtx body
= PATTERN (insn
);
1235 body
= PATTERN (insn
);
1236 if (GET_CODE (body
) == COND_EXEC
)
1238 cond
= COND_EXEC_TEST (body
);
1239 body
= COND_EXEC_CODE (body
);
1242 /* Find all sets. */
1243 if (GET_CODE (body
) == SET
)
1245 sets
[0].src
= SET_SRC (body
);
1246 sets
[0].dest
= SET_DEST (body
);
1249 else if (GET_CODE (body
) == PARALLEL
)
1251 /* Look through the PARALLEL and record the values being
1252 set, if possible. Also handle any CLOBBERs. */
1253 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1255 rtx x
= XVECEXP (body
, 0, i
);
1257 if (GET_CODE (x
) == SET
)
1259 sets
[n_sets
].src
= SET_SRC (x
);
1260 sets
[n_sets
].dest
= SET_DEST (x
);
1266 /* Look up the values that are read. Do this before invalidating the
1267 locations that are written. */
1268 for (i
= 0; i
< n_sets
; i
++)
1270 rtx dest
= sets
[i
].dest
;
1272 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1273 the low part after invalidating any knowledge about larger modes. */
1274 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1275 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1277 /* We don't know how to record anything but REG or MEM. */
1278 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1280 rtx src
= sets
[i
].src
;
1282 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (src
), cond
, src
, dest
);
1283 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1);
1284 if (GET_CODE (dest
) == MEM
)
1285 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0), Pmode
, 1);
1287 sets
[i
].dest_addr_elt
= 0;
1291 /* Invalidate all locations written by this insn. Note that the elts we
1292 looked up in the previous loop aren't affected, just some of their
1293 locations may go away. */
1294 note_stores (body
, cselib_invalidate_rtx
, NULL
);
1296 /* If this is an asm, look for duplicate sets. This can happen when the
1297 user uses the same value as an output multiple times. This is valid
1298 if the outputs are not actually used thereafter. Treat this case as
1299 if the value isn't actually set. We do this by smashing the destination
1300 to pc_rtx, so that we won't record the value later. */
1301 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
1303 for (i
= 0; i
< n_sets
; i
++)
1305 rtx dest
= sets
[i
].dest
;
1306 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1309 for (j
= i
+ 1; j
< n_sets
; j
++)
1310 if (rtx_equal_p (dest
, sets
[j
].dest
))
1312 sets
[i
].dest
= pc_rtx
;
1313 sets
[j
].dest
= pc_rtx
;
1319 /* Now enter the equivalences in our tables. */
1320 for (i
= 0; i
< n_sets
; i
++)
1322 rtx dest
= sets
[i
].dest
;
1323 if (GET_CODE (dest
) == REG
|| GET_CODE (dest
) == MEM
)
1324 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1328 /* Record the effects of INSN. */
1331 cselib_process_insn (rtx insn
)
1336 if (find_reg_note (insn
, REG_LIBCALL
, NULL
))
1337 cselib_current_insn_in_libcall
= true;
1338 if (find_reg_note (insn
, REG_RETVAL
, NULL
))
1339 cselib_current_insn_in_libcall
= false;
1340 cselib_current_insn
= insn
;
1342 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1343 if (GET_CODE (insn
) == CODE_LABEL
1344 || (GET_CODE (insn
) == CALL_INSN
1345 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1346 || (GET_CODE (insn
) == INSN
1347 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1348 && MEM_VOLATILE_P (PATTERN (insn
))))
1354 if (! INSN_P (insn
))
1356 cselib_current_insn
= 0;
1360 /* If this is a call instruction, forget anything stored in a
1361 call clobbered register, or, if this is not a const call, in
1363 if (GET_CODE (insn
) == CALL_INSN
)
1365 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1366 if (call_used_regs
[i
])
1367 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
1369 if (! CONST_OR_PURE_CALL_P (insn
))
1370 cselib_invalidate_mem (callmem
);
1373 cselib_record_sets (insn
);
1376 /* Clobber any registers which appear in REG_INC notes. We
1377 could keep track of the changes to their values, but it is
1378 unlikely to help. */
1379 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
1380 if (REG_NOTE_KIND (x
) == REG_INC
)
1381 cselib_invalidate_rtx (XEXP (x
, 0), NULL_RTX
, NULL
);
1384 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
1385 after we have processed the insn. */
1386 if (GET_CODE (insn
) == CALL_INSN
)
1387 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
1388 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
1389 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0), NULL_RTX
, NULL
);
1391 cselib_current_insn
= 0;
1393 if (n_useless_values
> MAX_USELESS_VALUES
)
1394 remove_useless_values ();
1397 /* Initialize cselib for one pass. The caller must also call
1398 init_alias_analysis. */
1403 elt_list_pool
= create_alloc_pool ("elt_list",
1404 sizeof (struct elt_list
), 10);
1405 elt_loc_list_pool
= create_alloc_pool ("elt_loc_list",
1406 sizeof (struct elt_loc_list
), 10);
1407 cselib_val_pool
= create_alloc_pool ("cselib_val_list",
1408 sizeof (cselib_val
), 10);
1409 value_pool
= create_alloc_pool ("value",
1410 RTX_SIZE (VALUE
), 100);
1411 /* This is only created once. */
1413 callmem
= gen_rtx_MEM (BLKmode
, const0_rtx
);
1415 cselib_nregs
= max_reg_num ();
1417 /* We preserve reg_values to allow expensive clearing of the whole thing.
1418 Reallocate it however if it happens to be too large. */
1419 if (!reg_values
|| reg_values_size
< cselib_nregs
1420 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
1424 /* Some space for newly emit instructions so we don't end up
1425 reallocating in between passes. */
1426 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
1427 reg_values
= xcalloc (reg_values_size
, sizeof (reg_values
));
1429 used_regs
= xmalloc (sizeof (*used_regs
) * cselib_nregs
);
1431 hash_table
= htab_create (31, get_value_hash
, entry_and_rtx_equal_p
, NULL
);
1432 cselib_current_insn_in_libcall
= false;
1435 /* Called when the current user is done with cselib. */
1438 cselib_finish (void)
1440 free_alloc_pool (elt_list_pool
);
1441 free_alloc_pool (elt_loc_list_pool
);
1442 free_alloc_pool (cselib_val_pool
);
1443 free_alloc_pool (value_pool
);
1445 htab_delete (hash_table
);
1450 n_useless_values
= 0;
1451 next_unknown_value
= 0;
1454 #include "gt-cselib.h"