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, 2005, 2006, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
33 #include "insn-config.h"
41 #include "tree-pass.h"
44 #include "alloc-pool.h"
47 static bool cselib_record_memory
;
48 static int entry_and_rtx_equal_p (const void *, const void *);
49 static hashval_t
get_value_hash (const void *);
50 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
51 static struct elt_loc_list
*new_elt_loc_list (struct elt_loc_list
*, rtx
);
52 static void unchain_one_value (cselib_val
*);
53 static void unchain_one_elt_list (struct elt_list
**);
54 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
55 static int discard_useless_locs (void **, void *);
56 static int discard_useless_values (void **, void *);
57 static void remove_useless_values (void);
58 static unsigned int cselib_hash_rtx (rtx
, int);
59 static cselib_val
*new_cselib_val (unsigned int, enum machine_mode
, rtx
);
60 static void add_mem_for_addr (cselib_val
*, cselib_val
*, rtx
);
61 static cselib_val
*cselib_lookup_mem (rtx
, int);
62 static void cselib_invalidate_regno (unsigned int, enum machine_mode
);
63 static void cselib_invalidate_mem (rtx
);
64 static void cselib_record_set (rtx
, cselib_val
*, cselib_val
*);
65 static void cselib_record_sets (rtx
);
67 struct expand_value_data
70 cselib_expand_callback callback
;
74 static rtx
cselib_expand_value_rtx_1 (rtx
, struct expand_value_data
*, int);
76 /* There are three ways in which cselib can look up an rtx:
77 - for a REG, the reg_values table (which is indexed by regno) is used
78 - for a MEM, we recursively look up its address and then follow the
79 addr_list of that value
80 - for everything else, we compute a hash value and go through the hash
81 table. Since different rtx's can still have the same hash value,
82 this involves walking the table entries for a given value and comparing
83 the locations of the entries with the rtx we are looking up. */
85 /* A table that enables us to look up elts by their value. */
86 static htab_t cselib_hash_table
;
88 /* This is a global so we don't have to pass this through every function.
89 It is used in new_elt_loc_list to set SETTING_INSN. */
90 static rtx cselib_current_insn
;
92 /* The unique id that the next create value will take. */
93 static unsigned int next_uid
;
95 /* The number of registers we had when the varrays were last resized. */
96 static unsigned int cselib_nregs
;
98 /* Count values without known locations. Whenever this grows too big, we
99 remove these useless values from the table. */
100 static int n_useless_values
;
102 /* Number of useless values before we remove them from the hash table. */
103 #define MAX_USELESS_VALUES 32
105 /* This table maps from register number to values. It does not
106 contain pointers to cselib_val structures, but rather elt_lists.
107 The purpose is to be able to refer to the same register in
108 different modes. The first element of the list defines the mode in
109 which the register was set; if the mode is unknown or the value is
110 no longer valid in that mode, ELT will be NULL for the first
112 static struct elt_list
**reg_values
;
113 static unsigned int reg_values_size
;
114 #define REG_VALUES(i) reg_values[i]
116 /* The largest number of hard regs used by any entry added to the
117 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
118 static unsigned int max_value_regs
;
120 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
121 in cselib_clear_table() for fast emptying. */
122 static unsigned int *used_regs
;
123 static unsigned int n_used_regs
;
125 /* We pass this to cselib_invalidate_mem to invalidate all of
126 memory for a non-const call instruction. */
127 static GTY(()) rtx callmem
;
129 /* Set by discard_useless_locs if it deleted the last location of any
131 static int values_became_useless
;
133 /* Used as stop element of the containing_mem list so we can check
134 presence in the list by checking the next pointer. */
135 static cselib_val dummy_val
;
137 /* Used to list all values that contain memory reference.
138 May or may not contain the useless values - the list is compacted
139 each time memory is invalidated. */
140 static cselib_val
*first_containing_mem
= &dummy_val
;
141 static alloc_pool elt_loc_list_pool
, elt_list_pool
, cselib_val_pool
, value_pool
;
143 /* If nonnull, cselib will call this function before freeing useless
144 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
145 void (*cselib_discard_hook
) (cselib_val
*);
147 /* If nonnull, cselib will call this function before recording sets or
148 even clobbering outputs of INSN. All the recorded sets will be
149 represented in the array sets[n_sets]. new_val_min can be used to
150 tell whether values present in sets are introduced by this
152 void (*cselib_record_sets_hook
) (rtx insn
, struct cselib_set
*sets
,
155 #define PRESERVED_VALUE_P(RTX) \
156 (RTL_FLAG_CHECK1("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
157 #define LONG_TERM_PRESERVED_VALUE_P(RTX) \
158 (RTL_FLAG_CHECK1("LONG_TERM_PRESERVED_VALUE_P", (RTX), VALUE)->in_struct)
162 /* Allocate a struct elt_list and fill in its two elements with the
165 static inline struct elt_list
*
166 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
169 el
= (struct elt_list
*) pool_alloc (elt_list_pool
);
175 /* Allocate a struct elt_loc_list and fill in its two elements with the
178 static inline struct elt_loc_list
*
179 new_elt_loc_list (struct elt_loc_list
*next
, rtx loc
)
181 struct elt_loc_list
*el
;
182 el
= (struct elt_loc_list
*) pool_alloc (elt_loc_list_pool
);
185 el
->setting_insn
= cselib_current_insn
;
189 /* The elt_list at *PL is no longer needed. Unchain it and free its
193 unchain_one_elt_list (struct elt_list
**pl
)
195 struct elt_list
*l
= *pl
;
198 pool_free (elt_list_pool
, l
);
201 /* Likewise for elt_loc_lists. */
204 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
206 struct elt_loc_list
*l
= *pl
;
209 pool_free (elt_loc_list_pool
, l
);
212 /* Likewise for cselib_vals. This also frees the addr_list associated with
216 unchain_one_value (cselib_val
*v
)
219 unchain_one_elt_list (&v
->addr_list
);
221 pool_free (cselib_val_pool
, v
);
224 /* Remove all entries from the hash table. Also used during
228 cselib_clear_table (void)
230 cselib_reset_table (1);
233 /* Remove all entries from the hash table, arranging for the next
234 value to be numbered NUM. */
237 cselib_reset_table (unsigned int num
)
241 for (i
= 0; i
< n_used_regs
; i
++)
242 REG_VALUES (used_regs
[i
]) = 0;
248 /* ??? Preserve constants? */
249 htab_empty (cselib_hash_table
);
251 n_useless_values
= 0;
255 first_containing_mem
= &dummy_val
;
258 /* Return the number of the next value that will be generated. */
261 cselib_get_next_uid (void)
266 /* The equality test for our hash table. The first argument ENTRY is a table
267 element (i.e. a cselib_val), while the second arg X is an rtx. We know
268 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
269 CONST of an appropriate mode. */
272 entry_and_rtx_equal_p (const void *entry
, const void *x_arg
)
274 struct elt_loc_list
*l
;
275 const cselib_val
*const v
= (const cselib_val
*) entry
;
276 rtx x
= CONST_CAST_RTX ((const_rtx
)x_arg
);
277 enum machine_mode mode
= GET_MODE (x
);
279 gcc_assert (!CONST_INT_P (x
) && GET_CODE (x
) != CONST_FIXED
280 && (mode
!= VOIDmode
|| GET_CODE (x
) != CONST_DOUBLE
));
282 if (mode
!= GET_MODE (v
->val_rtx
))
285 /* Unwrap X if necessary. */
286 if (GET_CODE (x
) == CONST
287 && (CONST_INT_P (XEXP (x
, 0))
288 || GET_CODE (XEXP (x
, 0)) == CONST_FIXED
289 || GET_CODE (XEXP (x
, 0)) == CONST_DOUBLE
))
292 /* We don't guarantee that distinct rtx's have different hash values,
293 so we need to do a comparison. */
294 for (l
= v
->locs
; l
; l
= l
->next
)
295 if (rtx_equal_for_cselib_p (l
->loc
, x
))
301 /* The hash function for our hash table. The value is always computed with
302 cselib_hash_rtx when adding an element; this function just extracts the
303 hash value from a cselib_val structure. */
306 get_value_hash (const void *entry
)
308 const cselib_val
*const v
= (const cselib_val
*) entry
;
312 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
313 only return true for values which point to a cselib_val whose value
314 element has been set to zero, which implies the cselib_val will be
318 references_value_p (const_rtx x
, int only_useless
)
320 const enum rtx_code code
= GET_CODE (x
);
321 const char *fmt
= GET_RTX_FORMAT (code
);
324 if (GET_CODE (x
) == VALUE
325 && (! only_useless
|| CSELIB_VAL_PTR (x
)->locs
== 0))
328 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
330 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
332 else if (fmt
[i
] == 'E')
333 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
334 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
341 /* For all locations found in X, delete locations that reference useless
342 values (i.e. values without any location). Called through
346 discard_useless_locs (void **x
, void *info ATTRIBUTE_UNUSED
)
348 cselib_val
*v
= (cselib_val
*)*x
;
349 struct elt_loc_list
**p
= &v
->locs
;
350 int had_locs
= v
->locs
!= 0;
354 if (references_value_p ((*p
)->loc
, 1))
355 unchain_one_elt_loc_list (p
);
360 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
363 values_became_useless
= 1;
368 /* If X is a value with no locations, remove it from the hashtable. */
371 discard_useless_values (void **x
, void *info ATTRIBUTE_UNUSED
)
373 cselib_val
*v
= (cselib_val
*)*x
;
375 if (v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
377 if (cselib_discard_hook
)
378 cselib_discard_hook (v
);
380 CSELIB_VAL_PTR (v
->val_rtx
) = NULL
;
381 htab_clear_slot (cselib_hash_table
, x
);
382 unchain_one_value (v
);
389 /* Clean out useless values (i.e. those which no longer have locations
390 associated with them) from the hash table. */
393 remove_useless_values (void)
396 /* First pass: eliminate locations that reference the value. That in
397 turn can make more values useless. */
400 values_became_useless
= 0;
401 htab_traverse (cselib_hash_table
, discard_useless_locs
, 0);
403 while (values_became_useless
);
405 /* Second pass: actually remove the values. */
407 p
= &first_containing_mem
;
408 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
412 p
= &(*p
)->next_containing_mem
;
416 htab_traverse (cselib_hash_table
, discard_useless_values
, 0);
418 gcc_assert (!n_useless_values
);
421 /* Arrange for a value to not be removed from the hash table even if
422 it becomes useless. */
425 cselib_preserve_value (cselib_val
*v
)
427 PRESERVED_VALUE_P (v
->val_rtx
) = 1;
430 /* Test whether a value is preserved. */
433 cselib_preserved_value_p (cselib_val
*v
)
435 return PRESERVED_VALUE_P (v
->val_rtx
);
438 /* Mark preserved values as preserved for the long term. */
441 cselib_preserve_definitely (void **slot
, void *info ATTRIBUTE_UNUSED
)
443 cselib_val
*v
= (cselib_val
*)*slot
;
445 if (PRESERVED_VALUE_P (v
->val_rtx
)
446 && !LONG_TERM_PRESERVED_VALUE_P (v
->val_rtx
))
447 LONG_TERM_PRESERVED_VALUE_P (v
->val_rtx
) = true;
452 /* Clear the preserve marks for values not preserved for the long
456 cselib_clear_preserve (void **slot
, void *info ATTRIBUTE_UNUSED
)
458 cselib_val
*v
= (cselib_val
*)*slot
;
460 if (PRESERVED_VALUE_P (v
->val_rtx
)
461 && !LONG_TERM_PRESERVED_VALUE_P (v
->val_rtx
))
463 PRESERVED_VALUE_P (v
->val_rtx
) = false;
471 /* Clean all non-constant expressions in the hash table, but retain
475 cselib_preserve_only_values (bool retain
)
479 htab_traverse (cselib_hash_table
,
480 retain
? cselib_preserve_definitely
: cselib_clear_preserve
,
483 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
484 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
486 cselib_invalidate_mem (callmem
);
488 remove_useless_values ();
490 gcc_assert (first_containing_mem
== &dummy_val
);
493 /* Return the mode in which a register was last set. If X is not a
494 register, return its mode. If the mode in which the register was
495 set is not known, or the value was already clobbered, return
499 cselib_reg_set_mode (const_rtx x
)
504 if (REG_VALUES (REGNO (x
)) == NULL
505 || REG_VALUES (REGNO (x
))->elt
== NULL
)
508 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->val_rtx
);
511 /* Return nonzero if we can prove that X and Y contain the same value, taking
512 our gathered information into account. */
515 rtx_equal_for_cselib_p (rtx x
, rtx y
)
521 if (REG_P (x
) || MEM_P (x
))
523 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0);
529 if (REG_P (y
) || MEM_P (y
))
531 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0);
540 if (GET_CODE (x
) == VALUE
&& GET_CODE (y
) == VALUE
)
541 return CSELIB_VAL_PTR (x
) == CSELIB_VAL_PTR (y
);
543 if (GET_CODE (x
) == VALUE
)
545 cselib_val
*e
= CSELIB_VAL_PTR (x
);
546 struct elt_loc_list
*l
;
548 for (l
= e
->locs
; l
; l
= l
->next
)
552 /* Avoid infinite recursion. */
553 if (REG_P (t
) || MEM_P (t
))
555 else if (rtx_equal_for_cselib_p (t
, y
))
562 if (GET_CODE (y
) == VALUE
)
564 cselib_val
*e
= CSELIB_VAL_PTR (y
);
565 struct elt_loc_list
*l
;
567 for (l
= e
->locs
; l
; l
= l
->next
)
571 if (REG_P (t
) || MEM_P (t
))
573 else if (rtx_equal_for_cselib_p (x
, t
))
580 if (GET_CODE (x
) != GET_CODE (y
) || GET_MODE (x
) != GET_MODE (y
))
583 /* These won't be handled correctly by the code below. */
584 switch (GET_CODE (x
))
592 return XEXP (x
, 0) == XEXP (y
, 0);
599 fmt
= GET_RTX_FORMAT (code
);
601 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
608 if (XWINT (x
, i
) != XWINT (y
, i
))
614 if (XINT (x
, i
) != XINT (y
, i
))
620 /* Two vectors must have the same length. */
621 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
624 /* And the corresponding elements must match. */
625 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
626 if (! rtx_equal_for_cselib_p (XVECEXP (x
, i
, j
),
633 && targetm
.commutative_p (x
, UNKNOWN
)
634 && rtx_equal_for_cselib_p (XEXP (x
, 1), XEXP (y
, 0))
635 && rtx_equal_for_cselib_p (XEXP (x
, 0), XEXP (y
, 1)))
637 if (! rtx_equal_for_cselib_p (XEXP (x
, i
), XEXP (y
, i
)))
643 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
648 /* These are just backpointers, so they don't matter. */
655 /* It is believed that rtx's at this level will never
656 contain anything but integers and other rtx's,
657 except for within LABEL_REFs and SYMBOL_REFs. */
665 /* We need to pass down the mode of constants through the hash table
666 functions. For that purpose, wrap them in a CONST of the appropriate
669 wrap_constant (enum machine_mode mode
, rtx x
)
671 if (!CONST_INT_P (x
) && GET_CODE (x
) != CONST_FIXED
672 && (GET_CODE (x
) != CONST_DOUBLE
|| GET_MODE (x
) != VOIDmode
))
674 gcc_assert (mode
!= VOIDmode
);
675 return gen_rtx_CONST (mode
, x
);
678 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
679 For registers and memory locations, we look up their cselib_val structure
680 and return its VALUE element.
681 Possible reasons for return 0 are: the object is volatile, or we couldn't
682 find a register or memory location in the table and CREATE is zero. If
683 CREATE is nonzero, table elts are created for regs and mem.
684 N.B. this hash function returns the same hash value for RTXes that
685 differ only in the order of operands, thus it is suitable for comparisons
686 that take commutativity into account.
687 If we wanted to also support associative rules, we'd have to use a different
688 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
689 We used to have a MODE argument for hashing for CONST_INTs, but that
690 didn't make sense, since it caused spurious hash differences between
691 (set (reg:SI 1) (const_int))
692 (plus:SI (reg:SI 2) (reg:SI 1))
694 (plus:SI (reg:SI 2) (const_int))
695 If the mode is important in any context, it must be checked specifically
696 in a comparison anyway, since relying on hash differences is unsafe. */
699 cselib_hash_rtx (rtx x
, int create
)
705 unsigned int hash
= 0;
708 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
714 e
= cselib_lookup (x
, GET_MODE (x
), create
);
721 hash
+= ((unsigned) DEBUG_EXPR
<< 7)
722 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x
));
723 return hash
? hash
: (unsigned int) DEBUG_EXPR
;
726 hash
+= ((unsigned) CONST_INT
<< 7) + INTVAL (x
);
727 return hash
? hash
: (unsigned int) CONST_INT
;
730 /* This is like the general case, except that it only counts
731 the integers representing the constant. */
732 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
733 if (GET_MODE (x
) != VOIDmode
)
734 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
736 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
737 + (unsigned) CONST_DOUBLE_HIGH (x
));
738 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
741 hash
+= (unsigned int) code
+ (unsigned int) GET_MODE (x
);
742 hash
+= fixed_hash (CONST_FIXED_VALUE (x
));
743 return hash
? hash
: (unsigned int) CONST_FIXED
;
750 units
= CONST_VECTOR_NUNITS (x
);
752 for (i
= 0; i
< units
; ++i
)
754 elt
= CONST_VECTOR_ELT (x
, i
);
755 hash
+= cselib_hash_rtx (elt
, 0);
761 /* Assume there is only one rtx object for any given label. */
763 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
764 differences and differences between each stage's debugging dumps. */
765 hash
+= (((unsigned int) LABEL_REF
<< 7)
766 + CODE_LABEL_NUMBER (XEXP (x
, 0)));
767 return hash
? hash
: (unsigned int) LABEL_REF
;
771 /* Don't hash on the symbol's address to avoid bootstrap differences.
772 Different hash values may cause expressions to be recorded in
773 different orders and thus different registers to be used in the
774 final assembler. This also avoids differences in the dump files
775 between various stages. */
777 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
780 h
+= (h
<< 7) + *p
++; /* ??? revisit */
782 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
783 return hash
? hash
: (unsigned int) SYMBOL_REF
;
795 case UNSPEC_VOLATILE
:
799 if (MEM_VOLATILE_P (x
))
808 i
= GET_RTX_LENGTH (code
) - 1;
809 fmt
= GET_RTX_FORMAT (code
);
816 rtx tem
= XEXP (x
, i
);
817 unsigned int tem_hash
= cselib_hash_rtx (tem
, create
);
826 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
828 unsigned int tem_hash
829 = cselib_hash_rtx (XVECEXP (x
, i
, j
), create
);
840 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
862 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
865 /* Create a new value structure for VALUE and initialize it. The mode of the
868 static inline cselib_val
*
869 new_cselib_val (unsigned int hash
, enum machine_mode mode
, rtx x
)
871 cselib_val
*e
= (cselib_val
*) pool_alloc (cselib_val_pool
);
874 gcc_assert (next_uid
);
878 /* We use an alloc pool to allocate this RTL construct because it
879 accounts for about 8% of the overall memory usage. We know
880 precisely when we can have VALUE RTXen (when cselib is active)
881 so we don't need to put them in garbage collected memory.
882 ??? Why should a VALUE be an RTX in the first place? */
883 e
->val_rtx
= (rtx
) pool_alloc (value_pool
);
884 memset (e
->val_rtx
, 0, RTX_HDR_SIZE
);
885 PUT_CODE (e
->val_rtx
, VALUE
);
886 PUT_MODE (e
->val_rtx
, mode
);
887 CSELIB_VAL_PTR (e
->val_rtx
) = e
;
890 e
->next_containing_mem
= 0;
892 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
894 fprintf (dump_file
, "cselib value %u:%u ", e
->uid
, hash
);
895 if (flag_dump_noaddr
|| flag_dump_unnumbered
)
896 fputs ("# ", dump_file
);
898 fprintf (dump_file
, "%p ", (void*)e
);
899 print_rtl_single (dump_file
, x
);
900 fputc ('\n', dump_file
);
906 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
907 contains the data at this address. X is a MEM that represents the
908 value. Update the two value structures to represent this situation. */
911 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
913 struct elt_loc_list
*l
;
915 /* Avoid duplicates. */
916 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
918 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
921 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
923 = new_elt_loc_list (mem_elt
->locs
,
924 replace_equiv_address_nv (x
, addr_elt
->val_rtx
));
925 if (mem_elt
->next_containing_mem
== NULL
)
927 mem_elt
->next_containing_mem
= first_containing_mem
;
928 first_containing_mem
= mem_elt
;
932 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
933 If CREATE, make a new one if we haven't seen it before. */
936 cselib_lookup_mem (rtx x
, int create
)
938 enum machine_mode mode
= GET_MODE (x
);
944 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
945 || !cselib_record_memory
946 || (FLOAT_MODE_P (mode
) && flag_float_store
))
949 /* Look up the value for the address. */
950 addr
= cselib_lookup (XEXP (x
, 0), mode
, create
);
954 /* Find a value that describes a value of our mode at that address. */
955 for (l
= addr
->addr_list
; l
; l
= l
->next
)
956 if (GET_MODE (l
->elt
->val_rtx
) == mode
)
962 mem_elt
= new_cselib_val (next_uid
, mode
, x
);
963 add_mem_for_addr (addr
, mem_elt
, x
);
964 slot
= htab_find_slot_with_hash (cselib_hash_table
, wrap_constant (mode
, x
),
965 mem_elt
->hash
, INSERT
);
970 /* Search thru the possible substitutions in P. We prefer a non reg
971 substitution because this allows us to expand the tree further. If
972 we find, just a reg, take the lowest regno. There may be several
973 non-reg results, we just take the first one because they will all
974 expand to the same place. */
977 expand_loc (struct elt_loc_list
*p
, struct expand_value_data
*evd
,
980 rtx reg_result
= NULL
;
981 unsigned int regno
= UINT_MAX
;
982 struct elt_loc_list
*p_in
= p
;
984 for (; p
; p
= p
-> next
)
986 /* Avoid infinite recursion trying to expand a reg into a
989 && (REGNO (p
->loc
) < regno
)
990 && !bitmap_bit_p (evd
->regs_active
, REGNO (p
->loc
)))
993 regno
= REGNO (p
->loc
);
995 /* Avoid infinite recursion and do not try to expand the
997 else if (GET_CODE (p
->loc
) == VALUE
998 && CSELIB_VAL_PTR (p
->loc
)->locs
== p_in
)
1000 else if (!REG_P (p
->loc
))
1003 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1005 print_inline_rtx (dump_file
, p
->loc
, 0);
1006 fprintf (dump_file
, "\n");
1008 if (GET_CODE (p
->loc
) == LO_SUM
1009 && GET_CODE (XEXP (p
->loc
, 1)) == SYMBOL_REF
1011 && (note
= find_reg_note (p
->setting_insn
, REG_EQUAL
, NULL_RTX
))
1012 && XEXP (note
, 0) == XEXP (p
->loc
, 1))
1013 return XEXP (p
->loc
, 1);
1014 result
= cselib_expand_value_rtx_1 (p
->loc
, evd
, max_depth
- 1);
1021 if (regno
!= UINT_MAX
)
1024 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1025 fprintf (dump_file
, "r%d\n", regno
);
1027 result
= cselib_expand_value_rtx_1 (reg_result
, evd
, max_depth
- 1);
1032 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1036 print_inline_rtx (dump_file
, reg_result
, 0);
1037 fprintf (dump_file
, "\n");
1040 fprintf (dump_file
, "NULL\n");
1046 /* Forward substitute and expand an expression out to its roots.
1047 This is the opposite of common subexpression. Because local value
1048 numbering is such a weak optimization, the expanded expression is
1049 pretty much unique (not from a pointer equals point of view but
1050 from a tree shape point of view.
1052 This function returns NULL if the expansion fails. The expansion
1053 will fail if there is no value number for one of the operands or if
1054 one of the operands has been overwritten between the current insn
1055 and the beginning of the basic block. For instance x has no
1061 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1062 It is clear on return. */
1065 cselib_expand_value_rtx (rtx orig
, bitmap regs_active
, int max_depth
)
1067 struct expand_value_data evd
;
1069 evd
.regs_active
= regs_active
;
1070 evd
.callback
= NULL
;
1071 evd
.callback_arg
= NULL
;
1073 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1076 /* Same as cselib_expand_value_rtx, but using a callback to try to
1077 resolve some expressions. The CB function should return ORIG if it
1078 can't or does not want to deal with a certain RTX. Any other
1079 return value, including NULL, will be used as the expansion for
1080 VALUE, without any further changes. */
1083 cselib_expand_value_rtx_cb (rtx orig
, bitmap regs_active
, int max_depth
,
1084 cselib_expand_callback cb
, void *data
)
1086 struct expand_value_data evd
;
1088 evd
.regs_active
= regs_active
;
1090 evd
.callback_arg
= data
;
1092 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1095 /* Internal implementation of cselib_expand_value_rtx and
1096 cselib_expand_value_rtx_cb. */
1099 cselib_expand_value_rtx_1 (rtx orig
, struct expand_value_data
*evd
,
1105 const char *format_ptr
;
1106 enum machine_mode mode
;
1108 code
= GET_CODE (orig
);
1110 /* For the context of dse, if we end up expand into a huge tree, we
1111 will not have a useful address, so we might as well just give up
1120 struct elt_list
*l
= REG_VALUES (REGNO (orig
));
1122 if (l
&& l
->elt
== NULL
)
1124 for (; l
; l
= l
->next
)
1125 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (orig
))
1128 int regno
= REGNO (orig
);
1130 /* The only thing that we are not willing to do (this
1131 is requirement of dse and if others potential uses
1132 need this function we should add a parm to control
1133 it) is that we will not substitute the
1134 STACK_POINTER_REGNUM, FRAME_POINTER or the
1137 These expansions confuses the code that notices that
1138 stores into the frame go dead at the end of the
1139 function and that the frame is not effected by calls
1140 to subroutines. If you allow the
1141 STACK_POINTER_REGNUM substitution, then dse will
1142 think that parameter pushing also goes dead which is
1143 wrong. If you allow the FRAME_POINTER or the
1144 HARD_FRAME_POINTER then you lose the opportunity to
1145 make the frame assumptions. */
1146 if (regno
== STACK_POINTER_REGNUM
1147 || regno
== FRAME_POINTER_REGNUM
1148 || regno
== HARD_FRAME_POINTER_REGNUM
)
1151 bitmap_set_bit (evd
->regs_active
, regno
);
1153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1154 fprintf (dump_file
, "expanding: r%d into: ", regno
);
1156 result
= expand_loc (l
->elt
->locs
, evd
, max_depth
);
1157 bitmap_clear_bit (evd
->regs_active
, regno
);
1174 /* SCRATCH must be shared because they represent distinct values. */
1177 if (REG_P (XEXP (orig
, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig
, 0))))
1182 if (shared_const_p (orig
))
1192 subreg
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1198 subreg
= cselib_expand_value_rtx_1 (SUBREG_REG (orig
), evd
,
1202 scopy
= simplify_gen_subreg (GET_MODE (orig
), subreg
,
1203 GET_MODE (SUBREG_REG (orig
)),
1204 SUBREG_BYTE (orig
));
1206 || (GET_CODE (scopy
) == SUBREG
1207 && !REG_P (SUBREG_REG (scopy
))
1208 && !MEM_P (SUBREG_REG (scopy
))))
1218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1220 fputs ("\nexpanding ", dump_file
);
1221 print_rtl_single (dump_file
, orig
);
1222 fputs (" into...", dump_file
);
1227 result
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1234 result
= expand_loc (CSELIB_VAL_PTR (orig
)->locs
, evd
, max_depth
);
1240 return evd
->callback (orig
, evd
->regs_active
, max_depth
,
1248 /* Copy the various flags, fields, and other information. We assume
1249 that all fields need copying, and then clear the fields that should
1250 not be copied. That is the sensible default behavior, and forces
1251 us to explicitly document why we are *not* copying a flag. */
1252 copy
= shallow_copy_rtx (orig
);
1254 format_ptr
= GET_RTX_FORMAT (code
);
1256 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
1257 switch (*format_ptr
++)
1260 if (XEXP (orig
, i
) != NULL
)
1262 rtx result
= cselib_expand_value_rtx_1 (XEXP (orig
, i
), evd
,
1266 XEXP (copy
, i
) = result
;
1272 if (XVEC (orig
, i
) != NULL
)
1274 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (orig
, i
));
1275 for (j
= 0; j
< XVECLEN (copy
, i
); j
++)
1277 rtx result
= cselib_expand_value_rtx_1 (XVECEXP (orig
, i
, j
),
1278 evd
, max_depth
- 1);
1281 XVECEXP (copy
, i
, j
) = result
;
1295 /* These are left unchanged. */
1302 mode
= GET_MODE (copy
);
1303 /* If an operand has been simplified into CONST_INT, which doesn't
1304 have a mode and the mode isn't derivable from whole rtx's mode,
1305 try simplify_*_operation first with mode from original's operand
1306 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1308 switch (GET_RTX_CLASS (code
))
1311 if (CONST_INT_P (XEXP (copy
, 0))
1312 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1314 scopy
= simplify_unary_operation (code
, mode
, XEXP (copy
, 0),
1315 GET_MODE (XEXP (orig
, 0)));
1320 case RTX_COMM_ARITH
:
1322 /* These expressions can derive operand modes from the whole rtx's mode. */
1325 case RTX_BITFIELD_OPS
:
1326 if (CONST_INT_P (XEXP (copy
, 0))
1327 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1329 scopy
= simplify_ternary_operation (code
, mode
,
1330 GET_MODE (XEXP (orig
, 0)),
1331 XEXP (copy
, 0), XEXP (copy
, 1),
1338 case RTX_COMM_COMPARE
:
1339 if (CONST_INT_P (XEXP (copy
, 0))
1340 && GET_MODE (XEXP (copy
, 1)) == VOIDmode
1341 && (GET_MODE (XEXP (orig
, 0)) != VOIDmode
1342 || GET_MODE (XEXP (orig
, 1)) != VOIDmode
))
1344 scopy
= simplify_relational_operation (code
, mode
,
1345 (GET_MODE (XEXP (orig
, 0))
1347 ? GET_MODE (XEXP (orig
, 0))
1348 : GET_MODE (XEXP (orig
, 1)),
1358 scopy
= simplify_rtx (copy
);
1364 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1365 with VALUE expressions. This way, it becomes independent of changes
1366 to registers and memory.
1367 X isn't actually modified; if modifications are needed, new rtl is
1368 allocated. However, the return value can share rtl with X. */
1371 cselib_subst_to_values (rtx x
)
1373 enum rtx_code code
= GET_CODE (x
);
1374 const char *fmt
= GET_RTX_FORMAT (code
);
1383 l
= REG_VALUES (REGNO (x
));
1384 if (l
&& l
->elt
== NULL
)
1386 for (; l
; l
= l
->next
)
1387 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (x
))
1388 return l
->elt
->val_rtx
;
1393 e
= cselib_lookup_mem (x
, 0);
1396 /* This happens for autoincrements. Assign a value that doesn't
1398 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
1414 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
1421 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1425 rtx t
= cselib_subst_to_values (XEXP (x
, i
));
1427 if (t
!= XEXP (x
, i
))
1430 copy
= shallow_copy_rtx (x
);
1434 else if (fmt
[i
] == 'E')
1438 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1440 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
));
1442 if (t
!= XVECEXP (x
, i
, j
))
1444 if (XVEC (x
, i
) == XVEC (copy
, i
))
1447 copy
= shallow_copy_rtx (x
);
1448 XVEC (copy
, i
) = shallow_copy_rtvec (XVEC (x
, i
));
1450 XVECEXP (copy
, i
, j
) = t
;
1459 /* Log a lookup of X to the cselib table along with the result RET. */
1462 cselib_log_lookup (rtx x
, cselib_val
*ret
)
1464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1466 fputs ("cselib lookup ", dump_file
);
1467 print_inline_rtx (dump_file
, x
, 2);
1468 fprintf (dump_file
, " => %u:%u\n",
1470 ret
? ret
->hash
: 0);
1476 /* Look up the rtl expression X in our tables and return the value it has.
1477 If CREATE is zero, we return NULL if we don't know the value. Otherwise,
1478 we create a new one if possible, using mode MODE if X doesn't have a mode
1479 (i.e. because it's a constant). */
1482 cselib_lookup (rtx x
, enum machine_mode mode
, int create
)
1486 unsigned int hashval
;
1488 if (GET_MODE (x
) != VOIDmode
)
1489 mode
= GET_MODE (x
);
1491 if (GET_CODE (x
) == VALUE
)
1492 return CSELIB_VAL_PTR (x
);
1497 unsigned int i
= REGNO (x
);
1500 if (l
&& l
->elt
== NULL
)
1502 for (; l
; l
= l
->next
)
1503 if (mode
== GET_MODE (l
->elt
->val_rtx
))
1504 return cselib_log_lookup (x
, l
->elt
);
1507 return cselib_log_lookup (x
, 0);
1509 if (i
< FIRST_PSEUDO_REGISTER
)
1511 unsigned int n
= hard_regno_nregs
[i
][mode
];
1513 if (n
> max_value_regs
)
1517 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
1518 e
->locs
= new_elt_loc_list (e
->locs
, x
);
1519 if (REG_VALUES (i
) == 0)
1521 /* Maintain the invariant that the first entry of
1522 REG_VALUES, if present, must be the value used to set the
1523 register, or NULL. */
1524 used_regs
[n_used_regs
++] = i
;
1525 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
1527 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
1528 slot
= htab_find_slot_with_hash (cselib_hash_table
, x
, e
->hash
, INSERT
);
1530 return cselib_log_lookup (x
, e
);
1534 return cselib_log_lookup (x
, cselib_lookup_mem (x
, create
));
1536 hashval
= cselib_hash_rtx (x
, create
);
1537 /* Can't even create if hashing is not possible. */
1539 return cselib_log_lookup (x
, 0);
1541 slot
= htab_find_slot_with_hash (cselib_hash_table
, wrap_constant (mode
, x
),
1542 hashval
, create
? INSERT
: NO_INSERT
);
1544 return cselib_log_lookup (x
, 0);
1546 e
= (cselib_val
*) *slot
;
1548 return cselib_log_lookup (x
, e
);
1550 e
= new_cselib_val (hashval
, mode
, x
);
1552 /* We have to fill the slot before calling cselib_subst_to_values:
1553 the hash table is inconsistent until we do so, and
1554 cselib_subst_to_values will need to do lookups. */
1556 e
->locs
= new_elt_loc_list (e
->locs
, cselib_subst_to_values (x
));
1557 return cselib_log_lookup (x
, e
);
1560 /* Invalidate any entries in reg_values that overlap REGNO. This is called
1561 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
1562 is used to determine how many hard registers are being changed. If MODE
1563 is VOIDmode, then only REGNO is being changed; this is used when
1564 invalidating call clobbered registers across a call. */
1567 cselib_invalidate_regno (unsigned int regno
, enum machine_mode mode
)
1569 unsigned int endregno
;
1572 /* If we see pseudos after reload, something is _wrong_. */
1573 gcc_assert (!reload_completed
|| regno
< FIRST_PSEUDO_REGISTER
1574 || reg_renumber
[regno
] < 0);
1576 /* Determine the range of registers that must be invalidated. For
1577 pseudos, only REGNO is affected. For hard regs, we must take MODE
1578 into account, and we must also invalidate lower register numbers
1579 if they contain values that overlap REGNO. */
1580 if (regno
< FIRST_PSEUDO_REGISTER
)
1582 gcc_assert (mode
!= VOIDmode
);
1584 if (regno
< max_value_regs
)
1587 i
= regno
- max_value_regs
;
1589 endregno
= end_hard_regno (mode
, regno
);
1594 endregno
= regno
+ 1;
1597 for (; i
< endregno
; i
++)
1599 struct elt_list
**l
= ®_VALUES (i
);
1601 /* Go through all known values for this reg; if it overlaps the range
1602 we're invalidating, remove the value. */
1605 cselib_val
*v
= (*l
)->elt
;
1606 struct elt_loc_list
**p
;
1607 unsigned int this_last
= i
;
1609 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
1610 this_last
= end_hard_regno (GET_MODE (v
->val_rtx
), i
) - 1;
1612 if (this_last
< regno
|| v
== NULL
)
1618 /* We have an overlap. */
1619 if (*l
== REG_VALUES (i
))
1621 /* Maintain the invariant that the first entry of
1622 REG_VALUES, if present, must be the value used to set
1623 the register, or NULL. This is also nice because
1624 then we won't push the same regno onto user_regs
1630 unchain_one_elt_list (l
);
1632 /* Now, we clear the mapping from value to reg. It must exist, so
1633 this code will crash intentionally if it doesn't. */
1634 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
1638 if (REG_P (x
) && REGNO (x
) == i
)
1640 unchain_one_elt_loc_list (p
);
1644 if (v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
1650 /* Return 1 if X has a value that can vary even between two
1651 executions of the program. 0 means X can be compared reliably
1652 against certain constants or near-constants. */
1655 cselib_rtx_varies_p (const_rtx x ATTRIBUTE_UNUSED
, bool from_alias ATTRIBUTE_UNUSED
)
1657 /* We actually don't need to verify very hard. This is because
1658 if X has actually changed, we invalidate the memory anyway,
1659 so assume that all common memory addresses are
1664 /* Invalidate any locations in the table which are changed because of a
1665 store to MEM_RTX. If this is called because of a non-const call
1666 instruction, MEM_RTX is (mem:BLK const0_rtx). */
1669 cselib_invalidate_mem (rtx mem_rtx
)
1671 cselib_val
**vp
, *v
, *next
;
1675 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
1676 mem_rtx
= canon_rtx (mem_rtx
);
1678 vp
= &first_containing_mem
;
1679 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
1681 bool has_mem
= false;
1682 struct elt_loc_list
**p
= &v
->locs
;
1683 int had_locs
= v
->locs
!= 0;
1689 struct elt_list
**mem_chain
;
1691 /* MEMs may occur in locations only at the top level; below
1692 that every MEM or REG is substituted by its VALUE. */
1698 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
1699 && ! canon_true_dependence (mem_rtx
, GET_MODE (mem_rtx
), mem_addr
,
1700 x
, NULL_RTX
, cselib_rtx_varies_p
))
1708 /* This one overlaps. */
1709 /* We must have a mapping from this MEM's address to the
1710 value (E). Remove that, too. */
1711 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0);
1712 mem_chain
= &addr
->addr_list
;
1715 if ((*mem_chain
)->elt
== v
)
1717 unchain_one_elt_list (mem_chain
);
1721 mem_chain
= &(*mem_chain
)->next
;
1724 unchain_one_elt_loc_list (p
);
1727 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
1730 next
= v
->next_containing_mem
;
1734 vp
= &(*vp
)->next_containing_mem
;
1737 v
->next_containing_mem
= NULL
;
1742 /* Invalidate DEST, which is being assigned to or clobbered. */
1745 cselib_invalidate_rtx (rtx dest
)
1747 while (GET_CODE (dest
) == SUBREG
1748 || GET_CODE (dest
) == ZERO_EXTRACT
1749 || GET_CODE (dest
) == STRICT_LOW_PART
)
1750 dest
= XEXP (dest
, 0);
1753 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
1754 else if (MEM_P (dest
))
1755 cselib_invalidate_mem (dest
);
1757 /* Some machines don't define AUTO_INC_DEC, but they still use push
1758 instructions. We need to catch that case here in order to
1759 invalidate the stack pointer correctly. Note that invalidating
1760 the stack pointer is different from invalidating DEST. */
1761 if (push_operand (dest
, GET_MODE (dest
)))
1762 cselib_invalidate_rtx (stack_pointer_rtx
);
1765 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
1768 cselib_invalidate_rtx_note_stores (rtx dest
, const_rtx ignore ATTRIBUTE_UNUSED
,
1769 void *data ATTRIBUTE_UNUSED
)
1771 cselib_invalidate_rtx (dest
);
1774 /* Record the result of a SET instruction. DEST is being set; the source
1775 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
1776 describes its address. */
1779 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
1781 int dreg
= REG_P (dest
) ? (int) REGNO (dest
) : -1;
1783 if (src_elt
== 0 || side_effects_p (dest
))
1788 if (dreg
< FIRST_PSEUDO_REGISTER
)
1790 unsigned int n
= hard_regno_nregs
[dreg
][GET_MODE (dest
)];
1792 if (n
> max_value_regs
)
1796 if (REG_VALUES (dreg
) == 0)
1798 used_regs
[n_used_regs
++] = dreg
;
1799 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
1803 /* The register should have been invalidated. */
1804 gcc_assert (REG_VALUES (dreg
)->elt
== 0);
1805 REG_VALUES (dreg
)->elt
= src_elt
;
1808 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
1810 src_elt
->locs
= new_elt_loc_list (src_elt
->locs
, dest
);
1812 else if (MEM_P (dest
) && dest_addr_elt
!= 0
1813 && cselib_record_memory
)
1815 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
1817 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
1821 /* There is no good way to determine how many elements there can be
1822 in a PARALLEL. Since it's fairly cheap, use a really large number. */
1823 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
1825 /* Record the effects of any sets in INSN. */
1827 cselib_record_sets (rtx insn
)
1831 struct cselib_set sets
[MAX_SETS
];
1832 rtx body
= PATTERN (insn
);
1835 body
= PATTERN (insn
);
1836 if (GET_CODE (body
) == COND_EXEC
)
1838 cond
= COND_EXEC_TEST (body
);
1839 body
= COND_EXEC_CODE (body
);
1842 /* Find all sets. */
1843 if (GET_CODE (body
) == SET
)
1845 sets
[0].src
= SET_SRC (body
);
1846 sets
[0].dest
= SET_DEST (body
);
1849 else if (GET_CODE (body
) == PARALLEL
)
1851 /* Look through the PARALLEL and record the values being
1852 set, if possible. Also handle any CLOBBERs. */
1853 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
1855 rtx x
= XVECEXP (body
, 0, i
);
1857 if (GET_CODE (x
) == SET
)
1859 sets
[n_sets
].src
= SET_SRC (x
);
1860 sets
[n_sets
].dest
= SET_DEST (x
);
1867 && MEM_P (sets
[0].src
)
1868 && !cselib_record_memory
1869 && MEM_READONLY_P (sets
[0].src
))
1871 rtx note
= find_reg_equal_equiv_note (insn
);
1873 if (note
&& CONSTANT_P (XEXP (note
, 0)))
1874 sets
[0].src
= XEXP (note
, 0);
1877 /* Look up the values that are read. Do this before invalidating the
1878 locations that are written. */
1879 for (i
= 0; i
< n_sets
; i
++)
1881 rtx dest
= sets
[i
].dest
;
1883 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
1884 the low part after invalidating any knowledge about larger modes. */
1885 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
1886 sets
[i
].dest
= dest
= XEXP (dest
, 0);
1888 /* We don't know how to record anything but REG or MEM. */
1890 || (MEM_P (dest
) && cselib_record_memory
))
1892 rtx src
= sets
[i
].src
;
1894 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (dest
), cond
, src
, dest
);
1895 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1);
1898 enum machine_mode address_mode
1899 = targetm
.addr_space
.address_mode (MEM_ADDR_SPACE (dest
));
1901 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0),
1905 sets
[i
].dest_addr_elt
= 0;
1909 if (cselib_record_sets_hook
)
1910 cselib_record_sets_hook (insn
, sets
, n_sets
);
1912 /* Invalidate all locations written by this insn. Note that the elts we
1913 looked up in the previous loop aren't affected, just some of their
1914 locations may go away. */
1915 note_stores (body
, cselib_invalidate_rtx_note_stores
, NULL
);
1917 /* If this is an asm, look for duplicate sets. This can happen when the
1918 user uses the same value as an output multiple times. This is valid
1919 if the outputs are not actually used thereafter. Treat this case as
1920 if the value isn't actually set. We do this by smashing the destination
1921 to pc_rtx, so that we won't record the value later. */
1922 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
1924 for (i
= 0; i
< n_sets
; i
++)
1926 rtx dest
= sets
[i
].dest
;
1927 if (REG_P (dest
) || MEM_P (dest
))
1930 for (j
= i
+ 1; j
< n_sets
; j
++)
1931 if (rtx_equal_p (dest
, sets
[j
].dest
))
1933 sets
[i
].dest
= pc_rtx
;
1934 sets
[j
].dest
= pc_rtx
;
1940 /* Now enter the equivalences in our tables. */
1941 for (i
= 0; i
< n_sets
; i
++)
1943 rtx dest
= sets
[i
].dest
;
1945 || (MEM_P (dest
) && cselib_record_memory
))
1946 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
1950 /* Record the effects of INSN. */
1953 cselib_process_insn (rtx insn
)
1958 cselib_current_insn
= insn
;
1960 /* Forget everything at a CODE_LABEL, a volatile asm, or a setjmp. */
1963 && find_reg_note (insn
, REG_SETJMP
, NULL
))
1964 || (NONJUMP_INSN_P (insn
)
1965 && GET_CODE (PATTERN (insn
)) == ASM_OPERANDS
1966 && MEM_VOLATILE_P (PATTERN (insn
))))
1968 cselib_reset_table (next_uid
);
1972 if (! INSN_P (insn
))
1974 cselib_current_insn
= 0;
1978 /* If this is a call instruction, forget anything stored in a
1979 call clobbered register, or, if this is not a const call, in
1983 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
1984 if (call_used_regs
[i
]
1985 || (REG_VALUES (i
) && REG_VALUES (i
)->elt
1986 && HARD_REGNO_CALL_PART_CLOBBERED (i
,
1987 GET_MODE (REG_VALUES (i
)->elt
->val_rtx
))))
1988 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
1990 /* Since it is not clear how cselib is going to be used, be
1991 conservative here and treat looping pure or const functions
1992 as if they were regular functions. */
1993 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1994 || !(RTL_CONST_OR_PURE_CALL_P (insn
)))
1995 cselib_invalidate_mem (callmem
);
1998 cselib_record_sets (insn
);
2001 /* Clobber any registers which appear in REG_INC notes. We
2002 could keep track of the changes to their values, but it is
2003 unlikely to help. */
2004 for (x
= REG_NOTES (insn
); x
; x
= XEXP (x
, 1))
2005 if (REG_NOTE_KIND (x
) == REG_INC
)
2006 cselib_invalidate_rtx (XEXP (x
, 0));
2009 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2010 after we have processed the insn. */
2012 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
2013 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
2014 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0));
2016 cselib_current_insn
= 0;
2018 if (n_useless_values
> MAX_USELESS_VALUES
2019 /* remove_useless_values is linear in the hash table size. Avoid
2020 quadratic behavior for very large hashtables with very few
2021 useless elements. */
2022 && (unsigned int)n_useless_values
> cselib_hash_table
->n_elements
/ 4)
2023 remove_useless_values ();
2026 /* Initialize cselib for one pass. The caller must also call
2027 init_alias_analysis. */
2030 cselib_init (bool record_memory
)
2032 elt_list_pool
= create_alloc_pool ("elt_list",
2033 sizeof (struct elt_list
), 10);
2034 elt_loc_list_pool
= create_alloc_pool ("elt_loc_list",
2035 sizeof (struct elt_loc_list
), 10);
2036 cselib_val_pool
= create_alloc_pool ("cselib_val_list",
2037 sizeof (cselib_val
), 10);
2038 value_pool
= create_alloc_pool ("value", RTX_CODE_SIZE (VALUE
), 100);
2039 cselib_record_memory
= record_memory
;
2041 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2042 see canon_true_dependence. This is only created once. */
2044 callmem
= gen_rtx_MEM (BLKmode
, gen_rtx_SCRATCH (VOIDmode
));
2046 cselib_nregs
= max_reg_num ();
2048 /* We preserve reg_values to allow expensive clearing of the whole thing.
2049 Reallocate it however if it happens to be too large. */
2050 if (!reg_values
|| reg_values_size
< cselib_nregs
2051 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
2055 /* Some space for newly emit instructions so we don't end up
2056 reallocating in between passes. */
2057 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
2058 reg_values
= XCNEWVEC (struct elt_list
*, reg_values_size
);
2060 used_regs
= XNEWVEC (unsigned int, cselib_nregs
);
2062 cselib_hash_table
= htab_create (31, get_value_hash
,
2063 entry_and_rtx_equal_p
, NULL
);
2067 /* Called when the current user is done with cselib. */
2070 cselib_finish (void)
2072 cselib_discard_hook
= NULL
;
2073 free_alloc_pool (elt_list_pool
);
2074 free_alloc_pool (elt_loc_list_pool
);
2075 free_alloc_pool (cselib_val_pool
);
2076 free_alloc_pool (value_pool
);
2077 cselib_clear_table ();
2078 htab_delete (cselib_hash_table
);
2081 cselib_hash_table
= 0;
2082 n_useless_values
= 0;
2086 /* Dump the cselib_val *X to FILE *info. */
2089 dump_cselib_val (void **x
, void *info
)
2091 cselib_val
*v
= (cselib_val
*)*x
;
2092 FILE *out
= (FILE *)info
;
2093 bool need_lf
= true;
2095 print_inline_rtx (out
, v
->val_rtx
, 0);
2099 struct elt_loc_list
*l
= v
->locs
;
2105 fputs (" locs:", out
);
2108 fprintf (out
, "\n from insn %i ",
2109 INSN_UID (l
->setting_insn
));
2110 print_inline_rtx (out
, l
->loc
, 4);
2112 while ((l
= l
->next
));
2117 fputs (" no locs", out
);
2123 struct elt_list
*e
= v
->addr_list
;
2129 fputs (" addr list:", out
);
2133 print_inline_rtx (out
, e
->elt
->val_rtx
, 2);
2135 while ((e
= e
->next
));
2140 fputs (" no addrs", out
);
2144 if (v
->next_containing_mem
== &dummy_val
)
2145 fputs (" last mem\n", out
);
2146 else if (v
->next_containing_mem
)
2148 fputs (" next mem ", out
);
2149 print_inline_rtx (out
, v
->next_containing_mem
->val_rtx
, 2);
2158 /* Dump to OUT everything in the CSELIB table. */
2161 dump_cselib_table (FILE *out
)
2163 fprintf (out
, "cselib hash table:\n");
2164 htab_traverse (cselib_hash_table
, dump_cselib_val
, out
);
2165 if (first_containing_mem
!= &dummy_val
)
2167 fputs ("first mem ", out
);
2168 print_inline_rtx (out
, first_containing_mem
->val_rtx
, 2);
2171 fprintf (out
, "next uid %i\n", next_uid
);
2174 #include "gt-cselib.h"