1 /* Common subexpression elimination library for GNU compiler.
2 Copyright (C) 1987-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "tree.h"/* FIXME: For hashing DEBUG_EXPR & friends. */
29 #include "hard-reg-set.h"
31 #include "insn-config.h"
40 #include "diagnostic-core.h"
42 #include "hash-table.h"
46 #include "basic-block.h"
49 #include "alloc-pool.h"
53 /* A list of cselib_val structures. */
55 struct elt_list
*next
;
59 static bool cselib_record_memory
;
60 static bool cselib_preserve_constants
;
61 static bool cselib_any_perm_equivs
;
62 static inline void promote_debug_loc (struct elt_loc_list
*l
);
63 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
64 static void new_elt_loc_list (cselib_val
*, rtx
);
65 static void unchain_one_value (cselib_val
*);
66 static void unchain_one_elt_list (struct elt_list
**);
67 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
68 static void remove_useless_values (void);
69 static int rtx_equal_for_cselib_1 (rtx
, rtx
, machine_mode
);
70 static unsigned int cselib_hash_rtx (rtx
, int, machine_mode
);
71 static cselib_val
*new_cselib_val (unsigned int, machine_mode
, rtx
);
72 static void add_mem_for_addr (cselib_val
*, cselib_val
*, rtx
);
73 static cselib_val
*cselib_lookup_mem (rtx
, int);
74 static void cselib_invalidate_regno (unsigned int, machine_mode
);
75 static void cselib_invalidate_mem (rtx
);
76 static void cselib_record_set (rtx
, cselib_val
*, cselib_val
*);
77 static void cselib_record_sets (rtx_insn
*);
79 struct expand_value_data
82 cselib_expand_callback callback
;
87 static rtx
cselib_expand_value_rtx_1 (rtx
, struct expand_value_data
*, int);
89 /* There are three ways in which cselib can look up an rtx:
90 - for a REG, the reg_values table (which is indexed by regno) is used
91 - for a MEM, we recursively look up its address and then follow the
92 addr_list of that value
93 - for everything else, we compute a hash value and go through the hash
94 table. Since different rtx's can still have the same hash value,
95 this involves walking the table entries for a given value and comparing
96 the locations of the entries with the rtx we are looking up. */
98 struct cselib_hasher
: typed_noop_remove
<cselib_val
>
100 typedef cselib_val value_type
;
101 struct compare_type
{
102 /* The rtx value and its mode (needed separately for constant
106 /* The mode of the contaning MEM, if any, otherwise VOIDmode. */
107 machine_mode memmode
;
109 static inline hashval_t
hash (const value_type
*);
110 static inline bool equal (const value_type
*, const compare_type
*);
113 /* The hash function for our hash table. The value is always computed with
114 cselib_hash_rtx when adding an element; this function just extracts the
115 hash value from a cselib_val structure. */
118 cselib_hasher::hash (const value_type
*v
)
123 /* The equality test for our hash table. The first argument V is a table
124 element (i.e. a cselib_val), while the second arg X is an rtx. We know
125 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
126 CONST of an appropriate mode. */
129 cselib_hasher::equal (const value_type
*v
, const compare_type
*x_arg
)
131 struct elt_loc_list
*l
;
133 machine_mode mode
= x_arg
->mode
;
134 machine_mode memmode
= x_arg
->memmode
;
136 if (mode
!= GET_MODE (v
->val_rtx
))
139 if (GET_CODE (x
) == VALUE
)
140 return x
== v
->val_rtx
;
142 /* We don't guarantee that distinct rtx's have different hash values,
143 so we need to do a comparison. */
144 for (l
= v
->locs
; l
; l
= l
->next
)
145 if (rtx_equal_for_cselib_1 (l
->loc
, x
, memmode
))
147 promote_debug_loc (l
);
154 /* A table that enables us to look up elts by their value. */
155 static hash_table
<cselib_hasher
> *cselib_hash_table
;
157 /* A table to hold preserved values. */
158 static hash_table
<cselib_hasher
> *cselib_preserved_hash_table
;
160 /* This is a global so we don't have to pass this through every function.
161 It is used in new_elt_loc_list to set SETTING_INSN. */
162 static rtx_insn
*cselib_current_insn
;
164 /* The unique id that the next create value will take. */
165 static unsigned int next_uid
;
167 /* The number of registers we had when the varrays were last resized. */
168 static unsigned int cselib_nregs
;
170 /* Count values without known locations, or with only locations that
171 wouldn't have been known except for debug insns. Whenever this
172 grows too big, we remove these useless values from the table.
174 Counting values with only debug values is a bit tricky. We don't
175 want to increment n_useless_values when we create a value for a
176 debug insn, for this would get n_useless_values out of sync, but we
177 want increment it if all locs in the list that were ever referenced
178 in nondebug insns are removed from the list.
180 In the general case, once we do that, we'd have to stop accepting
181 nondebug expressions in the loc list, to avoid having two values
182 equivalent that, without debug insns, would have been made into
183 separate values. However, because debug insns never introduce
184 equivalences themselves (no assignments), the only means for
185 growing loc lists is through nondebug assignments. If the locs
186 also happen to be referenced in debug insns, it will work just fine.
188 A consequence of this is that there's at most one debug-only loc in
189 each loc list. If we keep it in the first entry, testing whether
190 we have a debug-only loc list takes O(1).
192 Furthermore, since any additional entry in a loc list containing a
193 debug loc would have to come from an assignment (nondebug) that
194 references both the initial debug loc and the newly-equivalent loc,
195 the initial debug loc would be promoted to a nondebug loc, and the
196 loc list would not contain debug locs any more.
198 So the only case we have to be careful with in order to keep
199 n_useless_values in sync between debug and nondebug compilations is
200 to avoid incrementing n_useless_values when removing the single loc
201 from a value that turns out to not appear outside debug values. We
202 increment n_useless_debug_values instead, and leave such values
203 alone until, for other reasons, we garbage-collect useless
205 static int n_useless_values
;
206 static int n_useless_debug_values
;
208 /* Count values whose locs have been taken exclusively from debug
209 insns for the entire life of the value. */
210 static int n_debug_values
;
212 /* Number of useless values before we remove them from the hash table. */
213 #define MAX_USELESS_VALUES 32
215 /* This table maps from register number to values. It does not
216 contain pointers to cselib_val structures, but rather elt_lists.
217 The purpose is to be able to refer to the same register in
218 different modes. The first element of the list defines the mode in
219 which the register was set; if the mode is unknown or the value is
220 no longer valid in that mode, ELT will be NULL for the first
222 static struct elt_list
**reg_values
;
223 static unsigned int reg_values_size
;
224 #define REG_VALUES(i) reg_values[i]
226 /* The largest number of hard regs used by any entry added to the
227 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
228 static unsigned int max_value_regs
;
230 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
231 in cselib_clear_table() for fast emptying. */
232 static unsigned int *used_regs
;
233 static unsigned int n_used_regs
;
235 /* We pass this to cselib_invalidate_mem to invalidate all of
236 memory for a non-const call instruction. */
237 static GTY(()) rtx callmem
;
239 /* Set by discard_useless_locs if it deleted the last location of any
241 static int values_became_useless
;
243 /* Used as stop element of the containing_mem list so we can check
244 presence in the list by checking the next pointer. */
245 static cselib_val dummy_val
;
247 /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
248 that is constant through the whole function and should never be
250 static cselib_val
*cfa_base_preserved_val
;
251 static unsigned int cfa_base_preserved_regno
= INVALID_REGNUM
;
253 /* Used to list all values that contain memory reference.
254 May or may not contain the useless values - the list is compacted
255 each time memory is invalidated. */
256 static cselib_val
*first_containing_mem
= &dummy_val
;
257 static alloc_pool elt_loc_list_pool
, elt_list_pool
, cselib_val_pool
, value_pool
;
259 /* If nonnull, cselib will call this function before freeing useless
260 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
261 void (*cselib_discard_hook
) (cselib_val
*);
263 /* If nonnull, cselib will call this function before recording sets or
264 even clobbering outputs of INSN. All the recorded sets will be
265 represented in the array sets[n_sets]. new_val_min can be used to
266 tell whether values present in sets are introduced by this
268 void (*cselib_record_sets_hook
) (rtx_insn
*insn
, struct cselib_set
*sets
,
271 #define PRESERVED_VALUE_P(RTX) \
272 (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
274 #define SP_BASED_VALUE_P(RTX) \
275 (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump)
279 /* Allocate a struct elt_list and fill in its two elements with the
282 static inline struct elt_list
*
283 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
286 el
= (struct elt_list
*) pool_alloc (elt_list_pool
);
292 /* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc
296 new_elt_loc_list (cselib_val
*val
, rtx loc
)
298 struct elt_loc_list
*el
, *next
= val
->locs
;
300 gcc_checking_assert (!next
|| !next
->setting_insn
301 || !DEBUG_INSN_P (next
->setting_insn
)
302 || cselib_current_insn
== next
->setting_insn
);
304 /* If we're creating the first loc in a debug insn context, we've
305 just created a debug value. Count it. */
306 if (!next
&& cselib_current_insn
&& DEBUG_INSN_P (cselib_current_insn
))
309 val
= canonical_cselib_val (val
);
312 if (GET_CODE (loc
) == VALUE
)
314 loc
= canonical_cselib_val (CSELIB_VAL_PTR (loc
))->val_rtx
;
316 gcc_checking_assert (PRESERVED_VALUE_P (loc
)
317 == PRESERVED_VALUE_P (val
->val_rtx
));
319 if (val
->val_rtx
== loc
)
321 else if (val
->uid
> CSELIB_VAL_PTR (loc
)->uid
)
323 /* Reverse the insertion. */
324 new_elt_loc_list (CSELIB_VAL_PTR (loc
), val
->val_rtx
);
328 gcc_checking_assert (val
->uid
< CSELIB_VAL_PTR (loc
)->uid
);
330 if (CSELIB_VAL_PTR (loc
)->locs
)
332 /* Bring all locs from LOC to VAL. */
333 for (el
= CSELIB_VAL_PTR (loc
)->locs
; el
->next
; el
= el
->next
)
335 /* Adjust values that have LOC as canonical so that VAL
336 becomes their canonical. */
337 if (el
->loc
&& GET_CODE (el
->loc
) == VALUE
)
339 gcc_checking_assert (CSELIB_VAL_PTR (el
->loc
)->locs
->loc
341 CSELIB_VAL_PTR (el
->loc
)->locs
->loc
= val
->val_rtx
;
344 el
->next
= val
->locs
;
345 next
= val
->locs
= CSELIB_VAL_PTR (loc
)->locs
;
348 if (CSELIB_VAL_PTR (loc
)->addr_list
)
350 /* Bring in addr_list into canonical node. */
351 struct elt_list
*last
= CSELIB_VAL_PTR (loc
)->addr_list
;
354 last
->next
= val
->addr_list
;
355 val
->addr_list
= CSELIB_VAL_PTR (loc
)->addr_list
;
356 CSELIB_VAL_PTR (loc
)->addr_list
= NULL
;
359 if (CSELIB_VAL_PTR (loc
)->next_containing_mem
!= NULL
360 && val
->next_containing_mem
== NULL
)
362 /* Add VAL to the containing_mem list after LOC. LOC will
363 be removed when we notice it doesn't contain any
365 val
->next_containing_mem
= CSELIB_VAL_PTR (loc
)->next_containing_mem
;
366 CSELIB_VAL_PTR (loc
)->next_containing_mem
= val
;
369 /* Chain LOC back to VAL. */
370 el
= (struct elt_loc_list
*) pool_alloc (elt_loc_list_pool
);
371 el
->loc
= val
->val_rtx
;
372 el
->setting_insn
= cselib_current_insn
;
374 CSELIB_VAL_PTR (loc
)->locs
= el
;
377 el
= (struct elt_loc_list
*) pool_alloc (elt_loc_list_pool
);
379 el
->setting_insn
= cselib_current_insn
;
384 /* Promote loc L to a nondebug cselib_current_insn if L is marked as
385 originating from a debug insn, maintaining the debug values
389 promote_debug_loc (struct elt_loc_list
*l
)
391 if (l
&& l
->setting_insn
&& DEBUG_INSN_P (l
->setting_insn
)
392 && (!cselib_current_insn
|| !DEBUG_INSN_P (cselib_current_insn
)))
395 l
->setting_insn
= cselib_current_insn
;
396 if (cselib_preserve_constants
&& l
->next
)
398 gcc_assert (l
->next
->setting_insn
399 && DEBUG_INSN_P (l
->next
->setting_insn
)
401 l
->next
->setting_insn
= cselib_current_insn
;
404 gcc_assert (!l
->next
);
408 /* The elt_list at *PL is no longer needed. Unchain it and free its
412 unchain_one_elt_list (struct elt_list
**pl
)
414 struct elt_list
*l
= *pl
;
417 pool_free (elt_list_pool
, l
);
420 /* Likewise for elt_loc_lists. */
423 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
425 struct elt_loc_list
*l
= *pl
;
428 pool_free (elt_loc_list_pool
, l
);
431 /* Likewise for cselib_vals. This also frees the addr_list associated with
435 unchain_one_value (cselib_val
*v
)
438 unchain_one_elt_list (&v
->addr_list
);
440 pool_free (cselib_val_pool
, v
);
443 /* Remove all entries from the hash table. Also used during
447 cselib_clear_table (void)
449 cselib_reset_table (1);
452 /* Return TRUE if V is a constant, a function invariant or a VALUE
453 equivalence; FALSE otherwise. */
456 invariant_or_equiv_p (cselib_val
*v
)
458 struct elt_loc_list
*l
;
460 if (v
== cfa_base_preserved_val
)
463 /* Keep VALUE equivalences around. */
464 for (l
= v
->locs
; l
; l
= l
->next
)
465 if (GET_CODE (l
->loc
) == VALUE
)
469 && v
->locs
->next
== NULL
)
471 if (CONSTANT_P (v
->locs
->loc
)
472 && (GET_CODE (v
->locs
->loc
) != CONST
473 || !references_value_p (v
->locs
->loc
, 0)))
475 /* Although a debug expr may be bound to different expressions,
476 we can preserve it as if it was constant, to get unification
477 and proper merging within var-tracking. */
478 if (GET_CODE (v
->locs
->loc
) == DEBUG_EXPR
479 || GET_CODE (v
->locs
->loc
) == DEBUG_IMPLICIT_PTR
480 || GET_CODE (v
->locs
->loc
) == ENTRY_VALUE
481 || GET_CODE (v
->locs
->loc
) == DEBUG_PARAMETER_REF
)
484 /* (plus (value V) (const_int C)) is invariant iff V is invariant. */
485 if (GET_CODE (v
->locs
->loc
) == PLUS
486 && CONST_INT_P (XEXP (v
->locs
->loc
, 1))
487 && GET_CODE (XEXP (v
->locs
->loc
, 0)) == VALUE
488 && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v
->locs
->loc
, 0))))
495 /* Remove from hash table all VALUEs except constants, function
496 invariants and VALUE equivalences. */
499 preserve_constants_and_equivs (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
503 if (invariant_or_equiv_p (v
))
505 cselib_hasher::compare_type lookup
= {
506 GET_MODE (v
->val_rtx
), v
->val_rtx
, VOIDmode
509 = cselib_preserved_hash_table
->find_slot_with_hash (&lookup
,
515 cselib_hash_table
->clear_slot (x
);
520 /* Remove all entries from the hash table, arranging for the next
521 value to be numbered NUM. */
524 cselib_reset_table (unsigned int num
)
530 if (cfa_base_preserved_val
)
532 unsigned int regno
= cfa_base_preserved_regno
;
533 unsigned int new_used_regs
= 0;
534 for (i
= 0; i
< n_used_regs
; i
++)
535 if (used_regs
[i
] == regno
)
541 REG_VALUES (used_regs
[i
]) = 0;
542 gcc_assert (new_used_regs
== 1);
543 n_used_regs
= new_used_regs
;
544 used_regs
[0] = regno
;
546 = hard_regno_nregs
[regno
][GET_MODE (cfa_base_preserved_val
->locs
->loc
)];
550 for (i
= 0; i
< n_used_regs
; i
++)
551 REG_VALUES (used_regs
[i
]) = 0;
555 if (cselib_preserve_constants
)
556 cselib_hash_table
->traverse
<void *, preserve_constants_and_equivs
>
560 cselib_hash_table
->empty ();
561 gcc_checking_assert (!cselib_any_perm_equivs
);
564 n_useless_values
= 0;
565 n_useless_debug_values
= 0;
570 first_containing_mem
= &dummy_val
;
573 /* Return the number of the next value that will be generated. */
576 cselib_get_next_uid (void)
581 /* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE,
582 INSERTing if requested. When X is part of the address of a MEM,
583 MEMMODE should specify the mode of the MEM. */
586 cselib_find_slot (machine_mode mode
, rtx x
, hashval_t hash
,
587 enum insert_option insert
, machine_mode memmode
)
589 cselib_val
**slot
= NULL
;
590 cselib_hasher::compare_type lookup
= { mode
, x
, memmode
};
591 if (cselib_preserve_constants
)
592 slot
= cselib_preserved_hash_table
->find_slot_with_hash (&lookup
, hash
,
595 slot
= cselib_hash_table
->find_slot_with_hash (&lookup
, hash
, insert
);
599 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
600 only return true for values which point to a cselib_val whose value
601 element has been set to zero, which implies the cselib_val will be
605 references_value_p (const_rtx x
, int only_useless
)
607 const enum rtx_code code
= GET_CODE (x
);
608 const char *fmt
= GET_RTX_FORMAT (code
);
611 if (GET_CODE (x
) == VALUE
612 && (! only_useless
||
613 (CSELIB_VAL_PTR (x
)->locs
== 0 && !PRESERVED_VALUE_P (x
))))
616 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
618 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
620 else if (fmt
[i
] == 'E')
621 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
622 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
629 /* For all locations found in X, delete locations that reference useless
630 values (i.e. values without any location). Called through
634 discard_useless_locs (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
637 struct elt_loc_list
**p
= &v
->locs
;
638 bool had_locs
= v
->locs
!= NULL
;
639 rtx setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
643 if (references_value_p ((*p
)->loc
, 1))
644 unchain_one_elt_loc_list (p
);
649 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
651 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
652 n_useless_debug_values
++;
655 values_became_useless
= 1;
660 /* If X is a value with no locations, remove it from the hashtable. */
663 discard_useless_values (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
667 if (v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
669 if (cselib_discard_hook
)
670 cselib_discard_hook (v
);
672 CSELIB_VAL_PTR (v
->val_rtx
) = NULL
;
673 cselib_hash_table
->clear_slot (x
);
674 unchain_one_value (v
);
681 /* Clean out useless values (i.e. those which no longer have locations
682 associated with them) from the hash table. */
685 remove_useless_values (void)
689 /* First pass: eliminate locations that reference the value. That in
690 turn can make more values useless. */
693 values_became_useless
= 0;
694 cselib_hash_table
->traverse
<void *, discard_useless_locs
> (NULL
);
696 while (values_became_useless
);
698 /* Second pass: actually remove the values. */
700 p
= &first_containing_mem
;
701 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
702 if (v
->locs
&& v
== canonical_cselib_val (v
))
705 p
= &(*p
)->next_containing_mem
;
709 n_useless_values
+= n_useless_debug_values
;
710 n_debug_values
-= n_useless_debug_values
;
711 n_useless_debug_values
= 0;
713 cselib_hash_table
->traverse
<void *, discard_useless_values
> (NULL
);
715 gcc_assert (!n_useless_values
);
718 /* Arrange for a value to not be removed from the hash table even if
719 it becomes useless. */
722 cselib_preserve_value (cselib_val
*v
)
724 PRESERVED_VALUE_P (v
->val_rtx
) = 1;
727 /* Test whether a value is preserved. */
730 cselib_preserved_value_p (cselib_val
*v
)
732 return PRESERVED_VALUE_P (v
->val_rtx
);
735 /* Arrange for a REG value to be assumed constant through the whole function,
736 never invalidated and preserved across cselib_reset_table calls. */
739 cselib_preserve_cfa_base_value (cselib_val
*v
, unsigned int regno
)
741 if (cselib_preserve_constants
743 && REG_P (v
->locs
->loc
))
745 cfa_base_preserved_val
= v
;
746 cfa_base_preserved_regno
= regno
;
750 /* Clean all non-constant expressions in the hash table, but retain
754 cselib_preserve_only_values (void)
758 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
759 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
761 cselib_invalidate_mem (callmem
);
763 remove_useless_values ();
765 gcc_assert (first_containing_mem
== &dummy_val
);
768 /* Arrange for a value to be marked as based on stack pointer
769 for find_base_term purposes. */
772 cselib_set_value_sp_based (cselib_val
*v
)
774 SP_BASED_VALUE_P (v
->val_rtx
) = 1;
777 /* Test whether a value is based on stack pointer for
778 find_base_term purposes. */
781 cselib_sp_based_value_p (cselib_val
*v
)
783 return SP_BASED_VALUE_P (v
->val_rtx
);
786 /* Return the mode in which a register was last set. If X is not a
787 register, return its mode. If the mode in which the register was
788 set is not known, or the value was already clobbered, return
792 cselib_reg_set_mode (const_rtx x
)
797 if (REG_VALUES (REGNO (x
)) == NULL
798 || REG_VALUES (REGNO (x
))->elt
== NULL
)
801 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->val_rtx
);
804 /* Return nonzero if we can prove that X and Y contain the same value, taking
805 our gathered information into account. */
808 rtx_equal_for_cselib_p (rtx x
, rtx y
)
810 return rtx_equal_for_cselib_1 (x
, y
, VOIDmode
);
813 /* If x is a PLUS or an autoinc operation, expand the operation,
814 storing the offset, if any, in *OFF. */
817 autoinc_split (rtx x
, rtx
*off
, machine_mode memmode
)
819 switch (GET_CODE (x
))
826 if (memmode
== VOIDmode
)
829 *off
= GEN_INT (-GET_MODE_SIZE (memmode
));
834 if (memmode
== VOIDmode
)
837 *off
= GEN_INT (GET_MODE_SIZE (memmode
));
853 /* Return nonzero if we can prove that X and Y contain the same value,
854 taking our gathered information into account. MEMMODE holds the
855 mode of the enclosing MEM, if any, as required to deal with autoinc
856 addressing modes. If X and Y are not (known to be) part of
857 addresses, MEMMODE should be VOIDmode. */
860 rtx_equal_for_cselib_1 (rtx x
, rtx y
, machine_mode memmode
)
866 if (REG_P (x
) || MEM_P (x
))
868 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0, memmode
);
874 if (REG_P (y
) || MEM_P (y
))
876 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0, memmode
);
885 if (GET_CODE (x
) == VALUE
)
887 cselib_val
*e
= canonical_cselib_val (CSELIB_VAL_PTR (x
));
888 struct elt_loc_list
*l
;
890 if (GET_CODE (y
) == VALUE
)
891 return e
== canonical_cselib_val (CSELIB_VAL_PTR (y
));
893 for (l
= e
->locs
; l
; l
= l
->next
)
897 /* Avoid infinite recursion. We know we have the canonical
898 value, so we can just skip any values in the equivalence
900 if (REG_P (t
) || MEM_P (t
) || GET_CODE (t
) == VALUE
)
902 else if (rtx_equal_for_cselib_1 (t
, y
, memmode
))
908 else if (GET_CODE (y
) == VALUE
)
910 cselib_val
*e
= canonical_cselib_val (CSELIB_VAL_PTR (y
));
911 struct elt_loc_list
*l
;
913 for (l
= e
->locs
; l
; l
= l
->next
)
917 if (REG_P (t
) || MEM_P (t
) || GET_CODE (t
) == VALUE
)
919 else if (rtx_equal_for_cselib_1 (x
, t
, memmode
))
926 if (GET_MODE (x
) != GET_MODE (y
))
929 if (GET_CODE (x
) != GET_CODE (y
))
931 rtx xorig
= x
, yorig
= y
;
932 rtx xoff
= NULL
, yoff
= NULL
;
934 x
= autoinc_split (x
, &xoff
, memmode
);
935 y
= autoinc_split (y
, &yoff
, memmode
);
940 if (xoff
&& !rtx_equal_for_cselib_1 (xoff
, yoff
, memmode
))
943 /* Don't recurse if nothing changed. */
944 if (x
!= xorig
|| y
!= yorig
)
945 return rtx_equal_for_cselib_1 (x
, y
, memmode
);
950 /* These won't be handled correctly by the code below. */
951 switch (GET_CODE (x
))
957 case DEBUG_IMPLICIT_PTR
:
958 return DEBUG_IMPLICIT_PTR_DECL (x
)
959 == DEBUG_IMPLICIT_PTR_DECL (y
);
961 case DEBUG_PARAMETER_REF
:
962 return DEBUG_PARAMETER_REF_DECL (x
)
963 == DEBUG_PARAMETER_REF_DECL (y
);
966 /* ENTRY_VALUEs are function invariant, it is thus undesirable to
967 use rtx_equal_for_cselib_1 to compare the operands. */
968 return rtx_equal_p (ENTRY_VALUE_EXP (x
), ENTRY_VALUE_EXP (y
));
971 return LABEL_REF_LABEL (x
) == LABEL_REF_LABEL (y
);
974 /* We have to compare any autoinc operations in the addresses
975 using this MEM's mode. */
976 return rtx_equal_for_cselib_1 (XEXP (x
, 0), XEXP (y
, 0), GET_MODE (x
));
983 fmt
= GET_RTX_FORMAT (code
);
985 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
992 if (XWINT (x
, i
) != XWINT (y
, i
))
998 if (XINT (x
, i
) != XINT (y
, i
))
1004 /* Two vectors must have the same length. */
1005 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1008 /* And the corresponding elements must match. */
1009 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1010 if (! rtx_equal_for_cselib_1 (XVECEXP (x
, i
, j
),
1011 XVECEXP (y
, i
, j
), memmode
))
1017 && targetm
.commutative_p (x
, UNKNOWN
)
1018 && rtx_equal_for_cselib_1 (XEXP (x
, 1), XEXP (y
, 0), memmode
)
1019 && rtx_equal_for_cselib_1 (XEXP (x
, 0), XEXP (y
, 1), memmode
))
1021 if (! rtx_equal_for_cselib_1 (XEXP (x
, i
), XEXP (y
, i
), memmode
))
1027 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1032 /* These are just backpointers, so they don't matter. */
1039 /* It is believed that rtx's at this level will never
1040 contain anything but integers and other rtx's,
1041 except for within LABEL_REFs and SYMBOL_REFs. */
1049 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
1050 For registers and memory locations, we look up their cselib_val structure
1051 and return its VALUE element.
1052 Possible reasons for return 0 are: the object is volatile, or we couldn't
1053 find a register or memory location in the table and CREATE is zero. If
1054 CREATE is nonzero, table elts are created for regs and mem.
1055 N.B. this hash function returns the same hash value for RTXes that
1056 differ only in the order of operands, thus it is suitable for comparisons
1057 that take commutativity into account.
1058 If we wanted to also support associative rules, we'd have to use a different
1059 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
1060 MEMMODE indicates the mode of an enclosing MEM, and it's only
1061 used to compute autoinc values.
1062 We used to have a MODE argument for hashing for CONST_INTs, but that
1063 didn't make sense, since it caused spurious hash differences between
1064 (set (reg:SI 1) (const_int))
1065 (plus:SI (reg:SI 2) (reg:SI 1))
1067 (plus:SI (reg:SI 2) (const_int))
1068 If the mode is important in any context, it must be checked specifically
1069 in a comparison anyway, since relying on hash differences is unsafe. */
1072 cselib_hash_rtx (rtx x
, int create
, machine_mode memmode
)
1078 unsigned int hash
= 0;
1080 code
= GET_CODE (x
);
1081 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1086 e
= CSELIB_VAL_PTR (x
);
1091 e
= cselib_lookup (x
, GET_MODE (x
), create
, memmode
);
1098 hash
+= ((unsigned) DEBUG_EXPR
<< 7)
1099 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x
));
1100 return hash
? hash
: (unsigned int) DEBUG_EXPR
;
1102 case DEBUG_IMPLICIT_PTR
:
1103 hash
+= ((unsigned) DEBUG_IMPLICIT_PTR
<< 7)
1104 + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x
));
1105 return hash
? hash
: (unsigned int) DEBUG_IMPLICIT_PTR
;
1107 case DEBUG_PARAMETER_REF
:
1108 hash
+= ((unsigned) DEBUG_PARAMETER_REF
<< 7)
1109 + DECL_UID (DEBUG_PARAMETER_REF_DECL (x
));
1110 return hash
? hash
: (unsigned int) DEBUG_PARAMETER_REF
;
1113 /* ENTRY_VALUEs are function invariant, thus try to avoid
1114 recursing on argument if ENTRY_VALUE is one of the
1115 forms emitted by expand_debug_expr, otherwise
1116 ENTRY_VALUE hash would depend on the current value
1117 in some register or memory. */
1118 if (REG_P (ENTRY_VALUE_EXP (x
)))
1119 hash
+= (unsigned int) REG
1120 + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x
))
1121 + (unsigned int) REGNO (ENTRY_VALUE_EXP (x
));
1122 else if (MEM_P (ENTRY_VALUE_EXP (x
))
1123 && REG_P (XEXP (ENTRY_VALUE_EXP (x
), 0)))
1124 hash
+= (unsigned int) MEM
1125 + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x
), 0))
1126 + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x
), 0));
1128 hash
+= cselib_hash_rtx (ENTRY_VALUE_EXP (x
), create
, memmode
);
1129 return hash
? hash
: (unsigned int) ENTRY_VALUE
;
1132 hash
+= ((unsigned) CONST_INT
<< 7) + UINTVAL (x
);
1133 return hash
? hash
: (unsigned int) CONST_INT
;
1135 case CONST_WIDE_INT
:
1136 for (i
= 0; i
< CONST_WIDE_INT_NUNITS (x
); i
++)
1137 hash
+= CONST_WIDE_INT_ELT (x
, i
);
1141 /* This is like the general case, except that it only counts
1142 the integers representing the constant. */
1143 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1144 if (TARGET_SUPPORTS_WIDE_INT
== 0 && GET_MODE (x
) == VOIDmode
)
1145 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
1146 + (unsigned) CONST_DOUBLE_HIGH (x
));
1148 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
1149 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
1152 hash
+= (unsigned int) code
+ (unsigned int) GET_MODE (x
);
1153 hash
+= fixed_hash (CONST_FIXED_VALUE (x
));
1154 return hash
? hash
: (unsigned int) CONST_FIXED
;
1161 units
= CONST_VECTOR_NUNITS (x
);
1163 for (i
= 0; i
< units
; ++i
)
1165 elt
= CONST_VECTOR_ELT (x
, i
);
1166 hash
+= cselib_hash_rtx (elt
, 0, memmode
);
1172 /* Assume there is only one rtx object for any given label. */
1174 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1175 differences and differences between each stage's debugging dumps. */
1176 hash
+= (((unsigned int) LABEL_REF
<< 7)
1177 + CODE_LABEL_NUMBER (LABEL_REF_LABEL (x
)));
1178 return hash
? hash
: (unsigned int) LABEL_REF
;
1182 /* Don't hash on the symbol's address to avoid bootstrap differences.
1183 Different hash values may cause expressions to be recorded in
1184 different orders and thus different registers to be used in the
1185 final assembler. This also avoids differences in the dump files
1186 between various stages. */
1188 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
1191 h
+= (h
<< 7) + *p
++; /* ??? revisit */
1193 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
1194 return hash
? hash
: (unsigned int) SYMBOL_REF
;
1199 /* We can't compute these without knowing the MEM mode. */
1200 gcc_assert (memmode
!= VOIDmode
);
1201 i
= GET_MODE_SIZE (memmode
);
1202 if (code
== PRE_DEC
)
1204 /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1205 like (mem:MEMMODE (plus (reg) (const_int I))). */
1206 hash
+= (unsigned) PLUS
- (unsigned)code
1207 + cselib_hash_rtx (XEXP (x
, 0), create
, memmode
)
1208 + cselib_hash_rtx (GEN_INT (i
), create
, memmode
);
1209 return hash
? hash
: 1 + (unsigned) PLUS
;
1212 gcc_assert (memmode
!= VOIDmode
);
1213 return cselib_hash_rtx (XEXP (x
, 1), create
, memmode
);
1218 gcc_assert (memmode
!= VOIDmode
);
1219 return cselib_hash_rtx (XEXP (x
, 0), create
, memmode
);
1224 case UNSPEC_VOLATILE
:
1228 if (MEM_VOLATILE_P (x
))
1237 i
= GET_RTX_LENGTH (code
) - 1;
1238 fmt
= GET_RTX_FORMAT (code
);
1245 rtx tem
= XEXP (x
, i
);
1246 unsigned int tem_hash
= cselib_hash_rtx (tem
, create
, memmode
);
1255 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1257 unsigned int tem_hash
1258 = cselib_hash_rtx (XVECEXP (x
, i
, j
), create
, memmode
);
1269 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
1278 hash
+= XINT (x
, i
);
1291 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
1294 /* Create a new value structure for VALUE and initialize it. The mode of the
1297 static inline cselib_val
*
1298 new_cselib_val (unsigned int hash
, machine_mode mode
, rtx x
)
1300 cselib_val
*e
= (cselib_val
*) pool_alloc (cselib_val_pool
);
1303 gcc_assert (next_uid
);
1306 e
->uid
= next_uid
++;
1307 /* We use an alloc pool to allocate this RTL construct because it
1308 accounts for about 8% of the overall memory usage. We know
1309 precisely when we can have VALUE RTXen (when cselib is active)
1310 so we don't need to put them in garbage collected memory.
1311 ??? Why should a VALUE be an RTX in the first place? */
1312 e
->val_rtx
= (rtx
) pool_alloc (value_pool
);
1313 memset (e
->val_rtx
, 0, RTX_HDR_SIZE
);
1314 PUT_CODE (e
->val_rtx
, VALUE
);
1315 PUT_MODE (e
->val_rtx
, mode
);
1316 CSELIB_VAL_PTR (e
->val_rtx
) = e
;
1319 e
->next_containing_mem
= 0;
1321 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1323 fprintf (dump_file
, "cselib value %u:%u ", e
->uid
, hash
);
1324 if (flag_dump_noaddr
|| flag_dump_unnumbered
)
1325 fputs ("# ", dump_file
);
1327 fprintf (dump_file
, "%p ", (void*)e
);
1328 print_rtl_single (dump_file
, x
);
1329 fputc ('\n', dump_file
);
1335 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
1336 contains the data at this address. X is a MEM that represents the
1337 value. Update the two value structures to represent this situation. */
1340 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
1342 struct elt_loc_list
*l
;
1344 addr_elt
= canonical_cselib_val (addr_elt
);
1345 mem_elt
= canonical_cselib_val (mem_elt
);
1347 /* Avoid duplicates. */
1348 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
1350 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
1352 promote_debug_loc (l
);
1356 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
1357 new_elt_loc_list (mem_elt
,
1358 replace_equiv_address_nv (x
, addr_elt
->val_rtx
));
1359 if (mem_elt
->next_containing_mem
== NULL
)
1361 mem_elt
->next_containing_mem
= first_containing_mem
;
1362 first_containing_mem
= mem_elt
;
1366 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
1367 If CREATE, make a new one if we haven't seen it before. */
1370 cselib_lookup_mem (rtx x
, int create
)
1372 machine_mode mode
= GET_MODE (x
);
1373 machine_mode addr_mode
;
1376 cselib_val
*mem_elt
;
1379 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
1380 || !cselib_record_memory
1381 || (FLOAT_MODE_P (mode
) && flag_float_store
))
1384 addr_mode
= GET_MODE (XEXP (x
, 0));
1385 if (addr_mode
== VOIDmode
)
1388 /* Look up the value for the address. */
1389 addr
= cselib_lookup (XEXP (x
, 0), addr_mode
, create
, mode
);
1393 addr
= canonical_cselib_val (addr
);
1394 /* Find a value that describes a value of our mode at that address. */
1395 for (l
= addr
->addr_list
; l
; l
= l
->next
)
1396 if (GET_MODE (l
->elt
->val_rtx
) == mode
)
1398 promote_debug_loc (l
->elt
->locs
);
1405 mem_elt
= new_cselib_val (next_uid
, mode
, x
);
1406 add_mem_for_addr (addr
, mem_elt
, x
);
1407 slot
= cselib_find_slot (mode
, x
, mem_elt
->hash
, INSERT
, VOIDmode
);
1412 /* Search through the possible substitutions in P. We prefer a non reg
1413 substitution because this allows us to expand the tree further. If
1414 we find, just a reg, take the lowest regno. There may be several
1415 non-reg results, we just take the first one because they will all
1416 expand to the same place. */
1419 expand_loc (struct elt_loc_list
*p
, struct expand_value_data
*evd
,
1422 rtx reg_result
= NULL
;
1423 unsigned int regno
= UINT_MAX
;
1424 struct elt_loc_list
*p_in
= p
;
1426 for (; p
; p
= p
->next
)
1428 /* Return these right away to avoid returning stack pointer based
1429 expressions for frame pointer and vice versa, which is something
1430 that would confuse DSE. See the comment in cselib_expand_value_rtx_1
1431 for more details. */
1433 && (REGNO (p
->loc
) == STACK_POINTER_REGNUM
1434 || REGNO (p
->loc
) == FRAME_POINTER_REGNUM
1435 || REGNO (p
->loc
) == HARD_FRAME_POINTER_REGNUM
1436 || REGNO (p
->loc
) == cfa_base_preserved_regno
))
1438 /* Avoid infinite recursion trying to expand a reg into a
1440 if ((REG_P (p
->loc
))
1441 && (REGNO (p
->loc
) < regno
)
1442 && !bitmap_bit_p (evd
->regs_active
, REGNO (p
->loc
)))
1444 reg_result
= p
->loc
;
1445 regno
= REGNO (p
->loc
);
1447 /* Avoid infinite recursion and do not try to expand the
1449 else if (GET_CODE (p
->loc
) == VALUE
1450 && CSELIB_VAL_PTR (p
->loc
)->locs
== p_in
)
1452 else if (!REG_P (p
->loc
))
1455 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1457 print_inline_rtx (dump_file
, p
->loc
, 0);
1458 fprintf (dump_file
, "\n");
1460 if (GET_CODE (p
->loc
) == LO_SUM
1461 && GET_CODE (XEXP (p
->loc
, 1)) == SYMBOL_REF
1463 && (note
= find_reg_note (p
->setting_insn
, REG_EQUAL
, NULL_RTX
))
1464 && XEXP (note
, 0) == XEXP (p
->loc
, 1))
1465 return XEXP (p
->loc
, 1);
1466 result
= cselib_expand_value_rtx_1 (p
->loc
, evd
, max_depth
- 1);
1473 if (regno
!= UINT_MAX
)
1476 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1477 fprintf (dump_file
, "r%d\n", regno
);
1479 result
= cselib_expand_value_rtx_1 (reg_result
, evd
, max_depth
- 1);
1484 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1488 print_inline_rtx (dump_file
, reg_result
, 0);
1489 fprintf (dump_file
, "\n");
1492 fprintf (dump_file
, "NULL\n");
1498 /* Forward substitute and expand an expression out to its roots.
1499 This is the opposite of common subexpression. Because local value
1500 numbering is such a weak optimization, the expanded expression is
1501 pretty much unique (not from a pointer equals point of view but
1502 from a tree shape point of view.
1504 This function returns NULL if the expansion fails. The expansion
1505 will fail if there is no value number for one of the operands or if
1506 one of the operands has been overwritten between the current insn
1507 and the beginning of the basic block. For instance x has no
1513 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1514 It is clear on return. */
1517 cselib_expand_value_rtx (rtx orig
, bitmap regs_active
, int max_depth
)
1519 struct expand_value_data evd
;
1521 evd
.regs_active
= regs_active
;
1522 evd
.callback
= NULL
;
1523 evd
.callback_arg
= NULL
;
1526 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1529 /* Same as cselib_expand_value_rtx, but using a callback to try to
1530 resolve some expressions. The CB function should return ORIG if it
1531 can't or does not want to deal with a certain RTX. Any other
1532 return value, including NULL, will be used as the expansion for
1533 VALUE, without any further changes. */
1536 cselib_expand_value_rtx_cb (rtx orig
, bitmap regs_active
, int max_depth
,
1537 cselib_expand_callback cb
, void *data
)
1539 struct expand_value_data evd
;
1541 evd
.regs_active
= regs_active
;
1543 evd
.callback_arg
= data
;
1546 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1549 /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1550 or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1551 would return NULL or non-NULL, without allocating new rtx. */
1554 cselib_dummy_expand_value_rtx_cb (rtx orig
, bitmap regs_active
, int max_depth
,
1555 cselib_expand_callback cb
, void *data
)
1557 struct expand_value_data evd
;
1559 evd
.regs_active
= regs_active
;
1561 evd
.callback_arg
= data
;
1564 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
) != NULL
;
1567 /* Internal implementation of cselib_expand_value_rtx and
1568 cselib_expand_value_rtx_cb. */
1571 cselib_expand_value_rtx_1 (rtx orig
, struct expand_value_data
*evd
,
1577 const char *format_ptr
;
1580 code
= GET_CODE (orig
);
1582 /* For the context of dse, if we end up expand into a huge tree, we
1583 will not have a useful address, so we might as well just give up
1592 struct elt_list
*l
= REG_VALUES (REGNO (orig
));
1594 if (l
&& l
->elt
== NULL
)
1596 for (; l
; l
= l
->next
)
1597 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (orig
))
1600 unsigned regno
= REGNO (orig
);
1602 /* The only thing that we are not willing to do (this
1603 is requirement of dse and if others potential uses
1604 need this function we should add a parm to control
1605 it) is that we will not substitute the
1606 STACK_POINTER_REGNUM, FRAME_POINTER or the
1609 These expansions confuses the code that notices that
1610 stores into the frame go dead at the end of the
1611 function and that the frame is not effected by calls
1612 to subroutines. If you allow the
1613 STACK_POINTER_REGNUM substitution, then dse will
1614 think that parameter pushing also goes dead which is
1615 wrong. If you allow the FRAME_POINTER or the
1616 HARD_FRAME_POINTER then you lose the opportunity to
1617 make the frame assumptions. */
1618 if (regno
== STACK_POINTER_REGNUM
1619 || regno
== FRAME_POINTER_REGNUM
1620 || regno
== HARD_FRAME_POINTER_REGNUM
1621 || regno
== cfa_base_preserved_regno
)
1624 bitmap_set_bit (evd
->regs_active
, regno
);
1626 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1627 fprintf (dump_file
, "expanding: r%d into: ", regno
);
1629 result
= expand_loc (l
->elt
->locs
, evd
, max_depth
);
1630 bitmap_clear_bit (evd
->regs_active
, regno
);
1645 /* SCRATCH must be shared because they represent distinct values. */
1648 if (REG_P (XEXP (orig
, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig
, 0))))
1653 if (shared_const_p (orig
))
1663 subreg
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1669 subreg
= cselib_expand_value_rtx_1 (SUBREG_REG (orig
), evd
,
1673 scopy
= simplify_gen_subreg (GET_MODE (orig
), subreg
,
1674 GET_MODE (SUBREG_REG (orig
)),
1675 SUBREG_BYTE (orig
));
1677 || (GET_CODE (scopy
) == SUBREG
1678 && !REG_P (SUBREG_REG (scopy
))
1679 && !MEM_P (SUBREG_REG (scopy
))))
1689 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1691 fputs ("\nexpanding ", dump_file
);
1692 print_rtl_single (dump_file
, orig
);
1693 fputs (" into...", dump_file
);
1698 result
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1705 result
= expand_loc (CSELIB_VAL_PTR (orig
)->locs
, evd
, max_depth
);
1711 return evd
->callback (orig
, evd
->regs_active
, max_depth
,
1719 /* Copy the various flags, fields, and other information. We assume
1720 that all fields need copying, and then clear the fields that should
1721 not be copied. That is the sensible default behavior, and forces
1722 us to explicitly document why we are *not* copying a flag. */
1726 copy
= shallow_copy_rtx (orig
);
1728 format_ptr
= GET_RTX_FORMAT (code
);
1730 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
1731 switch (*format_ptr
++)
1734 if (XEXP (orig
, i
) != NULL
)
1736 rtx result
= cselib_expand_value_rtx_1 (XEXP (orig
, i
), evd
,
1741 XEXP (copy
, i
) = result
;
1747 if (XVEC (orig
, i
) != NULL
)
1750 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (orig
, i
));
1751 for (j
= 0; j
< XVECLEN (orig
, i
); j
++)
1753 rtx result
= cselib_expand_value_rtx_1 (XVECEXP (orig
, i
, j
),
1754 evd
, max_depth
- 1);
1758 XVECEXP (copy
, i
, j
) = result
;
1772 /* These are left unchanged. */
1782 mode
= GET_MODE (copy
);
1783 /* If an operand has been simplified into CONST_INT, which doesn't
1784 have a mode and the mode isn't derivable from whole rtx's mode,
1785 try simplify_*_operation first with mode from original's operand
1786 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1788 switch (GET_RTX_CLASS (code
))
1791 if (CONST_INT_P (XEXP (copy
, 0))
1792 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1794 scopy
= simplify_unary_operation (code
, mode
, XEXP (copy
, 0),
1795 GET_MODE (XEXP (orig
, 0)));
1800 case RTX_COMM_ARITH
:
1802 /* These expressions can derive operand modes from the whole rtx's mode. */
1805 case RTX_BITFIELD_OPS
:
1806 if (CONST_INT_P (XEXP (copy
, 0))
1807 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1809 scopy
= simplify_ternary_operation (code
, mode
,
1810 GET_MODE (XEXP (orig
, 0)),
1811 XEXP (copy
, 0), XEXP (copy
, 1),
1818 case RTX_COMM_COMPARE
:
1819 if (CONST_INT_P (XEXP (copy
, 0))
1820 && GET_MODE (XEXP (copy
, 1)) == VOIDmode
1821 && (GET_MODE (XEXP (orig
, 0)) != VOIDmode
1822 || GET_MODE (XEXP (orig
, 1)) != VOIDmode
))
1824 scopy
= simplify_relational_operation (code
, mode
,
1825 (GET_MODE (XEXP (orig
, 0))
1827 ? GET_MODE (XEXP (orig
, 0))
1828 : GET_MODE (XEXP (orig
, 1)),
1838 scopy
= simplify_rtx (copy
);
1844 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1845 with VALUE expressions. This way, it becomes independent of changes
1846 to registers and memory.
1847 X isn't actually modified; if modifications are needed, new rtl is
1848 allocated. However, the return value can share rtl with X.
1849 If X is within a MEM, MEMMODE must be the mode of the MEM. */
1852 cselib_subst_to_values (rtx x
, machine_mode memmode
)
1854 enum rtx_code code
= GET_CODE (x
);
1855 const char *fmt
= GET_RTX_FORMAT (code
);
1864 l
= REG_VALUES (REGNO (x
));
1865 if (l
&& l
->elt
== NULL
)
1867 for (; l
; l
= l
->next
)
1868 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (x
))
1869 return l
->elt
->val_rtx
;
1874 e
= cselib_lookup_mem (x
, 0);
1875 /* This used to happen for autoincrements, but we deal with them
1876 properly now. Remove the if stmt for the next release. */
1879 /* Assign a value that doesn't match any other. */
1880 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
1885 e
= cselib_lookup (x
, GET_MODE (x
), 0, memmode
);
1895 gcc_assert (memmode
!= VOIDmode
);
1896 i
= GET_MODE_SIZE (memmode
);
1897 if (code
== PRE_DEC
)
1899 return cselib_subst_to_values (plus_constant (GET_MODE (x
),
1904 gcc_assert (memmode
!= VOIDmode
);
1905 return cselib_subst_to_values (XEXP (x
, 1), memmode
);
1910 gcc_assert (memmode
!= VOIDmode
);
1911 return cselib_subst_to_values (XEXP (x
, 0), memmode
);
1917 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1921 rtx t
= cselib_subst_to_values (XEXP (x
, i
), memmode
);
1923 if (t
!= XEXP (x
, i
))
1926 copy
= shallow_copy_rtx (x
);
1930 else if (fmt
[i
] == 'E')
1934 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1936 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
), memmode
);
1938 if (t
!= XVECEXP (x
, i
, j
))
1940 if (XVEC (x
, i
) == XVEC (copy
, i
))
1943 copy
= shallow_copy_rtx (x
);
1944 XVEC (copy
, i
) = shallow_copy_rtvec (XVEC (x
, i
));
1946 XVECEXP (copy
, i
, j
) = t
;
1955 /* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */
1958 cselib_subst_to_values_from_insn (rtx x
, machine_mode memmode
, rtx_insn
*insn
)
1961 gcc_assert (!cselib_current_insn
);
1962 cselib_current_insn
= insn
;
1963 ret
= cselib_subst_to_values (x
, memmode
);
1964 cselib_current_insn
= NULL
;
1968 /* Look up the rtl expression X in our tables and return the value it
1969 has. If CREATE is zero, we return NULL if we don't know the value.
1970 Otherwise, we create a new one if possible, using mode MODE if X
1971 doesn't have a mode (i.e. because it's a constant). When X is part
1972 of an address, MEMMODE should be the mode of the enclosing MEM if
1973 we're tracking autoinc expressions. */
1976 cselib_lookup_1 (rtx x
, machine_mode mode
,
1977 int create
, machine_mode memmode
)
1981 unsigned int hashval
;
1983 if (GET_MODE (x
) != VOIDmode
)
1984 mode
= GET_MODE (x
);
1986 if (GET_CODE (x
) == VALUE
)
1987 return CSELIB_VAL_PTR (x
);
1992 unsigned int i
= REGNO (x
);
1995 if (l
&& l
->elt
== NULL
)
1997 for (; l
; l
= l
->next
)
1998 if (mode
== GET_MODE (l
->elt
->val_rtx
))
2000 promote_debug_loc (l
->elt
->locs
);
2007 if (i
< FIRST_PSEUDO_REGISTER
)
2009 unsigned int n
= hard_regno_nregs
[i
][mode
];
2011 if (n
> max_value_regs
)
2015 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
2016 new_elt_loc_list (e
, x
);
2017 if (REG_VALUES (i
) == 0)
2019 /* Maintain the invariant that the first entry of
2020 REG_VALUES, if present, must be the value used to set the
2021 register, or NULL. */
2022 used_regs
[n_used_regs
++] = i
;
2023 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
2025 else if (cselib_preserve_constants
2026 && GET_MODE_CLASS (mode
) == MODE_INT
)
2028 /* During var-tracking, try harder to find equivalences
2029 for SUBREGs. If a setter sets say a DImode register
2030 and user uses that register only in SImode, add a lowpart
2032 struct elt_list
*lwider
= NULL
;
2034 if (l
&& l
->elt
== NULL
)
2036 for (; l
; l
= l
->next
)
2037 if (GET_MODE_CLASS (GET_MODE (l
->elt
->val_rtx
)) == MODE_INT
2038 && GET_MODE_SIZE (GET_MODE (l
->elt
->val_rtx
))
2039 > GET_MODE_SIZE (mode
)
2041 || GET_MODE_SIZE (GET_MODE (l
->elt
->val_rtx
))
2042 < GET_MODE_SIZE (GET_MODE (lwider
->elt
->val_rtx
))))
2044 struct elt_loc_list
*el
;
2045 if (i
< FIRST_PSEUDO_REGISTER
2046 && hard_regno_nregs
[i
][GET_MODE (l
->elt
->val_rtx
)] != 1)
2048 for (el
= l
->elt
->locs
; el
; el
= el
->next
)
2049 if (!REG_P (el
->loc
))
2056 rtx sub
= lowpart_subreg (mode
, lwider
->elt
->val_rtx
,
2057 GET_MODE (lwider
->elt
->val_rtx
));
2059 new_elt_loc_list (e
, sub
);
2062 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
2063 slot
= cselib_find_slot (mode
, x
, e
->hash
, INSERT
, memmode
);
2069 return cselib_lookup_mem (x
, create
);
2071 hashval
= cselib_hash_rtx (x
, create
, memmode
);
2072 /* Can't even create if hashing is not possible. */
2076 slot
= cselib_find_slot (mode
, x
, hashval
,
2077 create
? INSERT
: NO_INSERT
, memmode
);
2081 e
= (cselib_val
*) *slot
;
2085 e
= new_cselib_val (hashval
, mode
, x
);
2087 /* We have to fill the slot before calling cselib_subst_to_values:
2088 the hash table is inconsistent until we do so, and
2089 cselib_subst_to_values will need to do lookups. */
2091 new_elt_loc_list (e
, cselib_subst_to_values (x
, memmode
));
2095 /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2098 cselib_lookup_from_insn (rtx x
, machine_mode mode
,
2099 int create
, machine_mode memmode
, rtx_insn
*insn
)
2103 gcc_assert (!cselib_current_insn
);
2104 cselib_current_insn
= insn
;
2106 ret
= cselib_lookup (x
, mode
, create
, memmode
);
2108 cselib_current_insn
= NULL
;
2113 /* Wrapper for cselib_lookup_1, that logs the lookup result and
2114 maintains invariants related with debug insns. */
2117 cselib_lookup (rtx x
, machine_mode mode
,
2118 int create
, machine_mode memmode
)
2120 cselib_val
*ret
= cselib_lookup_1 (x
, mode
, create
, memmode
);
2122 /* ??? Should we return NULL if we're not to create an entry, the
2123 found loc is a debug loc and cselib_current_insn is not DEBUG?
2124 If so, we should also avoid converting val to non-DEBUG; probably
2125 easiest setting cselib_current_insn to NULL before the call
2128 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
2130 fputs ("cselib lookup ", dump_file
);
2131 print_inline_rtx (dump_file
, x
, 2);
2132 fprintf (dump_file
, " => %u:%u\n",
2134 ret
? ret
->hash
: 0);
2140 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2141 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2142 is used to determine how many hard registers are being changed. If MODE
2143 is VOIDmode, then only REGNO is being changed; this is used when
2144 invalidating call clobbered registers across a call. */
2147 cselib_invalidate_regno (unsigned int regno
, machine_mode mode
)
2149 unsigned int endregno
;
2152 /* If we see pseudos after reload, something is _wrong_. */
2153 gcc_assert (!reload_completed
|| regno
< FIRST_PSEUDO_REGISTER
2154 || reg_renumber
[regno
] < 0);
2156 /* Determine the range of registers that must be invalidated. For
2157 pseudos, only REGNO is affected. For hard regs, we must take MODE
2158 into account, and we must also invalidate lower register numbers
2159 if they contain values that overlap REGNO. */
2160 if (regno
< FIRST_PSEUDO_REGISTER
)
2162 gcc_assert (mode
!= VOIDmode
);
2164 if (regno
< max_value_regs
)
2167 i
= regno
- max_value_regs
;
2169 endregno
= end_hard_regno (mode
, regno
);
2174 endregno
= regno
+ 1;
2177 for (; i
< endregno
; i
++)
2179 struct elt_list
**l
= ®_VALUES (i
);
2181 /* Go through all known values for this reg; if it overlaps the range
2182 we're invalidating, remove the value. */
2185 cselib_val
*v
= (*l
)->elt
;
2188 struct elt_loc_list
**p
;
2189 unsigned int this_last
= i
;
2191 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
2192 this_last
= end_hard_regno (GET_MODE (v
->val_rtx
), i
) - 1;
2194 if (this_last
< regno
|| v
== NULL
2195 || (v
== cfa_base_preserved_val
2196 && i
== cfa_base_preserved_regno
))
2202 /* We have an overlap. */
2203 if (*l
== REG_VALUES (i
))
2205 /* Maintain the invariant that the first entry of
2206 REG_VALUES, if present, must be the value used to set
2207 the register, or NULL. This is also nice because
2208 then we won't push the same regno onto user_regs
2214 unchain_one_elt_list (l
);
2216 v
= canonical_cselib_val (v
);
2218 had_locs
= v
->locs
!= NULL
;
2219 setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
2221 /* Now, we clear the mapping from value to reg. It must exist, so
2222 this code will crash intentionally if it doesn't. */
2223 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
2227 if (REG_P (x
) && REGNO (x
) == i
)
2229 unchain_one_elt_loc_list (p
);
2234 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
2236 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
2237 n_useless_debug_values
++;
2245 /* Invalidate any locations in the table which are changed because of a
2246 store to MEM_RTX. If this is called because of a non-const call
2247 instruction, MEM_RTX is (mem:BLK const0_rtx). */
2250 cselib_invalidate_mem (rtx mem_rtx
)
2252 cselib_val
**vp
, *v
, *next
;
2256 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
2257 mem_rtx
= canon_rtx (mem_rtx
);
2259 vp
= &first_containing_mem
;
2260 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
2262 bool has_mem
= false;
2263 struct elt_loc_list
**p
= &v
->locs
;
2264 bool had_locs
= v
->locs
!= NULL
;
2265 rtx setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
2271 struct elt_list
**mem_chain
;
2273 /* MEMs may occur in locations only at the top level; below
2274 that every MEM or REG is substituted by its VALUE. */
2280 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
2281 && ! canon_anti_dependence (x
, false, mem_rtx
,
2282 GET_MODE (mem_rtx
), mem_addr
))
2290 /* This one overlaps. */
2291 /* We must have a mapping from this MEM's address to the
2292 value (E). Remove that, too. */
2293 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0, GET_MODE (x
));
2294 addr
= canonical_cselib_val (addr
);
2295 gcc_checking_assert (v
== canonical_cselib_val (v
));
2296 mem_chain
= &addr
->addr_list
;
2299 cselib_val
*canon
= canonical_cselib_val ((*mem_chain
)->elt
);
2303 unchain_one_elt_list (mem_chain
);
2307 /* Record canonicalized elt. */
2308 (*mem_chain
)->elt
= canon
;
2310 mem_chain
= &(*mem_chain
)->next
;
2313 unchain_one_elt_loc_list (p
);
2316 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
2318 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
2319 n_useless_debug_values
++;
2324 next
= v
->next_containing_mem
;
2328 vp
= &(*vp
)->next_containing_mem
;
2331 v
->next_containing_mem
= NULL
;
2336 /* Invalidate DEST, which is being assigned to or clobbered. */
2339 cselib_invalidate_rtx (rtx dest
)
2341 while (GET_CODE (dest
) == SUBREG
2342 || GET_CODE (dest
) == ZERO_EXTRACT
2343 || GET_CODE (dest
) == STRICT_LOW_PART
)
2344 dest
= XEXP (dest
, 0);
2347 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
2348 else if (MEM_P (dest
))
2349 cselib_invalidate_mem (dest
);
2352 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2355 cselib_invalidate_rtx_note_stores (rtx dest
, const_rtx ignore ATTRIBUTE_UNUSED
,
2356 void *data ATTRIBUTE_UNUSED
)
2358 cselib_invalidate_rtx (dest
);
2361 /* Record the result of a SET instruction. DEST is being set; the source
2362 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
2363 describes its address. */
2366 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
2368 int dreg
= REG_P (dest
) ? (int) REGNO (dest
) : -1;
2370 if (src_elt
== 0 || side_effects_p (dest
))
2375 if (dreg
< FIRST_PSEUDO_REGISTER
)
2377 unsigned int n
= hard_regno_nregs
[dreg
][GET_MODE (dest
)];
2379 if (n
> max_value_regs
)
2383 if (REG_VALUES (dreg
) == 0)
2385 used_regs
[n_used_regs
++] = dreg
;
2386 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
2390 /* The register should have been invalidated. */
2391 gcc_assert (REG_VALUES (dreg
)->elt
== 0);
2392 REG_VALUES (dreg
)->elt
= src_elt
;
2395 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
2397 new_elt_loc_list (src_elt
, dest
);
2399 else if (MEM_P (dest
) && dest_addr_elt
!= 0
2400 && cselib_record_memory
)
2402 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
2404 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
2408 /* Make ELT and X's VALUE equivalent to each other at INSN. */
2411 cselib_add_permanent_equiv (cselib_val
*elt
, rtx x
, rtx_insn
*insn
)
2414 rtx_insn
*save_cselib_current_insn
= cselib_current_insn
;
2416 gcc_checking_assert (elt
);
2417 gcc_checking_assert (PRESERVED_VALUE_P (elt
->val_rtx
));
2418 gcc_checking_assert (!side_effects_p (x
));
2420 cselib_current_insn
= insn
;
2422 nelt
= cselib_lookup (x
, GET_MODE (elt
->val_rtx
), 1, VOIDmode
);
2426 cselib_any_perm_equivs
= true;
2428 if (!PRESERVED_VALUE_P (nelt
->val_rtx
))
2429 cselib_preserve_value (nelt
);
2431 new_elt_loc_list (nelt
, elt
->val_rtx
);
2434 cselib_current_insn
= save_cselib_current_insn
;
2437 /* Return TRUE if any permanent equivalences have been recorded since
2438 the table was last initialized. */
2440 cselib_have_permanent_equivalences (void)
2442 return cselib_any_perm_equivs
;
2445 /* There is no good way to determine how many elements there can be
2446 in a PARALLEL. Since it's fairly cheap, use a really large number. */
2447 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
2449 struct cselib_record_autoinc_data
2451 struct cselib_set
*sets
;
2455 /* Callback for for_each_inc_dec. Records in ARG the SETs implied by
2456 autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */
2459 cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED
, rtx op ATTRIBUTE_UNUSED
,
2460 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
2462 struct cselib_record_autoinc_data
*data
;
2463 data
= (struct cselib_record_autoinc_data
*)arg
;
2465 data
->sets
[data
->n_sets
].dest
= dest
;
2468 data
->sets
[data
->n_sets
].src
= gen_rtx_PLUS (GET_MODE (src
), src
, srcoff
);
2470 data
->sets
[data
->n_sets
].src
= src
;
2477 /* Record the effects of any sets and autoincs in INSN. */
2479 cselib_record_sets (rtx_insn
*insn
)
2483 struct cselib_set sets
[MAX_SETS
];
2484 rtx body
= PATTERN (insn
);
2486 int n_sets_before_autoinc
;
2487 struct cselib_record_autoinc_data data
;
2489 body
= PATTERN (insn
);
2490 if (GET_CODE (body
) == COND_EXEC
)
2492 cond
= COND_EXEC_TEST (body
);
2493 body
= COND_EXEC_CODE (body
);
2496 /* Find all sets. */
2497 if (GET_CODE (body
) == SET
)
2499 sets
[0].src
= SET_SRC (body
);
2500 sets
[0].dest
= SET_DEST (body
);
2503 else if (GET_CODE (body
) == PARALLEL
)
2505 /* Look through the PARALLEL and record the values being
2506 set, if possible. Also handle any CLOBBERs. */
2507 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
2509 rtx x
= XVECEXP (body
, 0, i
);
2511 if (GET_CODE (x
) == SET
)
2513 sets
[n_sets
].src
= SET_SRC (x
);
2514 sets
[n_sets
].dest
= SET_DEST (x
);
2521 && MEM_P (sets
[0].src
)
2522 && !cselib_record_memory
2523 && MEM_READONLY_P (sets
[0].src
))
2525 rtx note
= find_reg_equal_equiv_note (insn
);
2527 if (note
&& CONSTANT_P (XEXP (note
, 0)))
2528 sets
[0].src
= XEXP (note
, 0);
2532 data
.n_sets
= n_sets_before_autoinc
= n_sets
;
2533 for_each_inc_dec (PATTERN (insn
), cselib_record_autoinc_cb
, &data
);
2534 n_sets
= data
.n_sets
;
2536 /* Look up the values that are read. Do this before invalidating the
2537 locations that are written. */
2538 for (i
= 0; i
< n_sets
; i
++)
2540 rtx dest
= sets
[i
].dest
;
2542 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
2543 the low part after invalidating any knowledge about larger modes. */
2544 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
2545 sets
[i
].dest
= dest
= XEXP (dest
, 0);
2547 /* We don't know how to record anything but REG or MEM. */
2549 || (MEM_P (dest
) && cselib_record_memory
))
2551 rtx src
= sets
[i
].src
;
2553 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (dest
), cond
, src
, dest
);
2554 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1, VOIDmode
);
2557 machine_mode address_mode
= get_address_mode (dest
);
2559 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0),
2564 sets
[i
].dest_addr_elt
= 0;
2568 if (cselib_record_sets_hook
)
2569 cselib_record_sets_hook (insn
, sets
, n_sets
);
2571 /* Invalidate all locations written by this insn. Note that the elts we
2572 looked up in the previous loop aren't affected, just some of their
2573 locations may go away. */
2574 note_stores (body
, cselib_invalidate_rtx_note_stores
, NULL
);
2576 for (i
= n_sets_before_autoinc
; i
< n_sets
; i
++)
2577 cselib_invalidate_rtx (sets
[i
].dest
);
2579 /* If this is an asm, look for duplicate sets. This can happen when the
2580 user uses the same value as an output multiple times. This is valid
2581 if the outputs are not actually used thereafter. Treat this case as
2582 if the value isn't actually set. We do this by smashing the destination
2583 to pc_rtx, so that we won't record the value later. */
2584 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
2586 for (i
= 0; i
< n_sets
; i
++)
2588 rtx dest
= sets
[i
].dest
;
2589 if (REG_P (dest
) || MEM_P (dest
))
2592 for (j
= i
+ 1; j
< n_sets
; j
++)
2593 if (rtx_equal_p (dest
, sets
[j
].dest
))
2595 sets
[i
].dest
= pc_rtx
;
2596 sets
[j
].dest
= pc_rtx
;
2602 /* Now enter the equivalences in our tables. */
2603 for (i
= 0; i
< n_sets
; i
++)
2605 rtx dest
= sets
[i
].dest
;
2607 || (MEM_P (dest
) && cselib_record_memory
))
2608 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
2612 /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
2615 fp_setter_insn (rtx insn
)
2617 rtx expr
, pat
= NULL_RTX
;
2619 if (!RTX_FRAME_RELATED_P (insn
))
2622 expr
= find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
);
2624 pat
= XEXP (expr
, 0);
2625 if (!modified_in_p (hard_frame_pointer_rtx
, pat
? pat
: insn
))
2628 /* Don't return true for frame pointer restores in the epilogue. */
2629 if (find_reg_note (insn
, REG_CFA_RESTORE
, hard_frame_pointer_rtx
))
2634 /* Record the effects of INSN. */
2637 cselib_process_insn (rtx_insn
*insn
)
2642 cselib_current_insn
= insn
;
2644 /* Forget everything at a CODE_LABEL or a setjmp. */
2647 && find_reg_note (insn
, REG_SETJMP
, NULL
)))
2648 && !cselib_preserve_constants
)
2650 cselib_reset_table (next_uid
);
2651 cselib_current_insn
= NULL
;
2655 if (! INSN_P (insn
))
2657 cselib_current_insn
= NULL
;
2661 /* If this is a call instruction, forget anything stored in a
2662 call clobbered register, or, if this is not a const call, in
2666 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2667 if (call_used_regs
[i
]
2668 || (REG_VALUES (i
) && REG_VALUES (i
)->elt
2669 && HARD_REGNO_CALL_PART_CLOBBERED (i
,
2670 GET_MODE (REG_VALUES (i
)->elt
->val_rtx
))))
2671 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
2673 /* Since it is not clear how cselib is going to be used, be
2674 conservative here and treat looping pure or const functions
2675 as if they were regular functions. */
2676 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
2677 || !(RTL_CONST_OR_PURE_CALL_P (insn
)))
2678 cselib_invalidate_mem (callmem
);
2681 cselib_record_sets (insn
);
2683 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2684 after we have processed the insn. */
2687 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
2688 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
2689 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0));
2690 /* Flush evertything on setjmp. */
2691 if (cselib_preserve_constants
2692 && find_reg_note (insn
, REG_SETJMP
, NULL
))
2694 cselib_preserve_only_values ();
2695 cselib_reset_table (next_uid
);
2699 /* On setter of the hard frame pointer if frame_pointer_needed,
2700 invalidate stack_pointer_rtx, so that sp and {,h}fp based
2701 VALUEs are distinct. */
2702 if (reload_completed
2703 && frame_pointer_needed
2704 && fp_setter_insn (insn
))
2705 cselib_invalidate_rtx (stack_pointer_rtx
);
2707 cselib_current_insn
= NULL
;
2709 if (n_useless_values
> MAX_USELESS_VALUES
2710 /* remove_useless_values is linear in the hash table size. Avoid
2711 quadratic behavior for very large hashtables with very few
2712 useless elements. */
2713 && ((unsigned int)n_useless_values
2714 > (cselib_hash_table
->elements () - n_debug_values
) / 4))
2715 remove_useless_values ();
2718 /* Initialize cselib for one pass. The caller must also call
2719 init_alias_analysis. */
2722 cselib_init (int record_what
)
2724 elt_list_pool
= create_alloc_pool ("elt_list",
2725 sizeof (struct elt_list
), 10);
2726 elt_loc_list_pool
= create_alloc_pool ("elt_loc_list",
2727 sizeof (struct elt_loc_list
), 10);
2728 cselib_val_pool
= create_alloc_pool ("cselib_val_list",
2729 sizeof (cselib_val
), 10);
2730 value_pool
= create_alloc_pool ("value", RTX_CODE_SIZE (VALUE
), 100);
2731 cselib_record_memory
= record_what
& CSELIB_RECORD_MEMORY
;
2732 cselib_preserve_constants
= record_what
& CSELIB_PRESERVE_CONSTANTS
;
2733 cselib_any_perm_equivs
= false;
2735 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2736 see canon_true_dependence. This is only created once. */
2738 callmem
= gen_rtx_MEM (BLKmode
, gen_rtx_SCRATCH (VOIDmode
));
2740 cselib_nregs
= max_reg_num ();
2742 /* We preserve reg_values to allow expensive clearing of the whole thing.
2743 Reallocate it however if it happens to be too large. */
2744 if (!reg_values
|| reg_values_size
< cselib_nregs
2745 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
2748 /* Some space for newly emit instructions so we don't end up
2749 reallocating in between passes. */
2750 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
2751 reg_values
= XCNEWVEC (struct elt_list
*, reg_values_size
);
2753 used_regs
= XNEWVEC (unsigned int, cselib_nregs
);
2755 cselib_hash_table
= new hash_table
<cselib_hasher
> (31);
2756 if (cselib_preserve_constants
)
2757 cselib_preserved_hash_table
= new hash_table
<cselib_hasher
> (31);
2761 /* Called when the current user is done with cselib. */
2764 cselib_finish (void)
2766 bool preserved
= cselib_preserve_constants
;
2767 cselib_discard_hook
= NULL
;
2768 cselib_preserve_constants
= false;
2769 cselib_any_perm_equivs
= false;
2770 cfa_base_preserved_val
= NULL
;
2771 cfa_base_preserved_regno
= INVALID_REGNUM
;
2772 free_alloc_pool (elt_list_pool
);
2773 free_alloc_pool (elt_loc_list_pool
);
2774 free_alloc_pool (cselib_val_pool
);
2775 free_alloc_pool (value_pool
);
2776 cselib_clear_table ();
2777 delete cselib_hash_table
;
2778 cselib_hash_table
= NULL
;
2780 delete cselib_preserved_hash_table
;
2781 cselib_preserved_hash_table
= NULL
;
2784 n_useless_values
= 0;
2785 n_useless_debug_values
= 0;
2790 /* Dump the cselib_val *X to FILE *OUT. */
2793 dump_cselib_val (cselib_val
**x
, FILE *out
)
2796 bool need_lf
= true;
2798 print_inline_rtx (out
, v
->val_rtx
, 0);
2802 struct elt_loc_list
*l
= v
->locs
;
2808 fputs (" locs:", out
);
2811 if (l
->setting_insn
)
2812 fprintf (out
, "\n from insn %i ",
2813 INSN_UID (l
->setting_insn
));
2815 fprintf (out
, "\n ");
2816 print_inline_rtx (out
, l
->loc
, 4);
2818 while ((l
= l
->next
));
2823 fputs (" no locs", out
);
2829 struct elt_list
*e
= v
->addr_list
;
2835 fputs (" addr list:", out
);
2839 print_inline_rtx (out
, e
->elt
->val_rtx
, 2);
2841 while ((e
= e
->next
));
2846 fputs (" no addrs", out
);
2850 if (v
->next_containing_mem
== &dummy_val
)
2851 fputs (" last mem\n", out
);
2852 else if (v
->next_containing_mem
)
2854 fputs (" next mem ", out
);
2855 print_inline_rtx (out
, v
->next_containing_mem
->val_rtx
, 2);
2864 /* Dump to OUT everything in the CSELIB table. */
2867 dump_cselib_table (FILE *out
)
2869 fprintf (out
, "cselib hash table:\n");
2870 cselib_hash_table
->traverse
<FILE *, dump_cselib_val
> (out
);
2871 fprintf (out
, "cselib preserved hash table:\n");
2872 cselib_preserved_hash_table
->traverse
<FILE *, dump_cselib_val
> (out
);
2873 if (first_containing_mem
!= &dummy_val
)
2875 fputs ("first mem ", out
);
2876 print_inline_rtx (out
, first_containing_mem
->val_rtx
, 2);
2879 fprintf (out
, "next uid %i\n", next_uid
);
2882 #include "gt-cselib.h"