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"
28 #include "double-int.h"
34 #include "tree.h"/* FIXME: For hashing DEBUG_EXPR & friends. */
37 #include "hard-reg-set.h"
39 #include "insn-config.h"
45 #include "diagnostic-core.h"
47 #include "hash-table.h"
49 #include "alloc-pool.h"
52 #include "basic-block.h"
55 #include "alloc-pool.h"
59 /* A list of cselib_val structures. */
62 struct elt_list
*next
;
65 /* Pool allocation new operator. */
66 inline void *operator new (size_t)
68 return pool
.allocate ();
71 /* Delete operator utilizing pool allocation. */
72 inline void operator delete (void *ptr
)
74 pool
.remove ((elt_list
*) ptr
);
77 /* Memory allocation pool. */
78 static pool_allocator
<elt_list
> pool
;
81 static bool cselib_record_memory
;
82 static bool cselib_preserve_constants
;
83 static bool cselib_any_perm_equivs
;
84 static inline void promote_debug_loc (struct elt_loc_list
*l
);
85 static struct elt_list
*new_elt_list (struct elt_list
*, cselib_val
*);
86 static void new_elt_loc_list (cselib_val
*, rtx
);
87 static void unchain_one_value (cselib_val
*);
88 static void unchain_one_elt_list (struct elt_list
**);
89 static void unchain_one_elt_loc_list (struct elt_loc_list
**);
90 static void remove_useless_values (void);
91 static int rtx_equal_for_cselib_1 (rtx
, rtx
, machine_mode
);
92 static unsigned int cselib_hash_rtx (rtx
, int, machine_mode
);
93 static cselib_val
*new_cselib_val (unsigned int, machine_mode
, rtx
);
94 static void add_mem_for_addr (cselib_val
*, cselib_val
*, rtx
);
95 static cselib_val
*cselib_lookup_mem (rtx
, int);
96 static void cselib_invalidate_regno (unsigned int, machine_mode
);
97 static void cselib_invalidate_mem (rtx
);
98 static void cselib_record_set (rtx
, cselib_val
*, cselib_val
*);
99 static void cselib_record_sets (rtx_insn
*);
101 struct expand_value_data
104 cselib_expand_callback callback
;
109 static rtx
cselib_expand_value_rtx_1 (rtx
, struct expand_value_data
*, int);
111 /* There are three ways in which cselib can look up an rtx:
112 - for a REG, the reg_values table (which is indexed by regno) is used
113 - for a MEM, we recursively look up its address and then follow the
114 addr_list of that value
115 - for everything else, we compute a hash value and go through the hash
116 table. Since different rtx's can still have the same hash value,
117 this involves walking the table entries for a given value and comparing
118 the locations of the entries with the rtx we are looking up. */
120 struct cselib_hasher
: typed_noop_remove
<cselib_val
>
122 typedef cselib_val
*value_type
;
124 /* The rtx value and its mode (needed separately for constant
128 /* The mode of the contaning MEM, if any, otherwise VOIDmode. */
129 machine_mode memmode
;
131 typedef key
*compare_type
;
132 static inline hashval_t
hash (const cselib_val
*);
133 static inline bool equal (const cselib_val
*, const key
*);
136 /* The hash function for our hash table. The value is always computed with
137 cselib_hash_rtx when adding an element; this function just extracts the
138 hash value from a cselib_val structure. */
141 cselib_hasher::hash (const cselib_val
*v
)
146 /* The equality test for our hash table. The first argument V is a table
147 element (i.e. a cselib_val), while the second arg X is an rtx. We know
148 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
149 CONST of an appropriate mode. */
152 cselib_hasher::equal (const cselib_val
*v
, const key
*x_arg
)
154 struct elt_loc_list
*l
;
156 machine_mode mode
= x_arg
->mode
;
157 machine_mode memmode
= x_arg
->memmode
;
159 if (mode
!= GET_MODE (v
->val_rtx
))
162 if (GET_CODE (x
) == VALUE
)
163 return x
== v
->val_rtx
;
165 /* We don't guarantee that distinct rtx's have different hash values,
166 so we need to do a comparison. */
167 for (l
= v
->locs
; l
; l
= l
->next
)
168 if (rtx_equal_for_cselib_1 (l
->loc
, x
, memmode
))
170 promote_debug_loc (l
);
177 /* A table that enables us to look up elts by their value. */
178 static hash_table
<cselib_hasher
> *cselib_hash_table
;
180 /* A table to hold preserved values. */
181 static hash_table
<cselib_hasher
> *cselib_preserved_hash_table
;
183 /* This is a global so we don't have to pass this through every function.
184 It is used in new_elt_loc_list to set SETTING_INSN. */
185 static rtx_insn
*cselib_current_insn
;
187 /* The unique id that the next create value will take. */
188 static unsigned int next_uid
;
190 /* The number of registers we had when the varrays were last resized. */
191 static unsigned int cselib_nregs
;
193 /* Count values without known locations, or with only locations that
194 wouldn't have been known except for debug insns. Whenever this
195 grows too big, we remove these useless values from the table.
197 Counting values with only debug values is a bit tricky. We don't
198 want to increment n_useless_values when we create a value for a
199 debug insn, for this would get n_useless_values out of sync, but we
200 want increment it if all locs in the list that were ever referenced
201 in nondebug insns are removed from the list.
203 In the general case, once we do that, we'd have to stop accepting
204 nondebug expressions in the loc list, to avoid having two values
205 equivalent that, without debug insns, would have been made into
206 separate values. However, because debug insns never introduce
207 equivalences themselves (no assignments), the only means for
208 growing loc lists is through nondebug assignments. If the locs
209 also happen to be referenced in debug insns, it will work just fine.
211 A consequence of this is that there's at most one debug-only loc in
212 each loc list. If we keep it in the first entry, testing whether
213 we have a debug-only loc list takes O(1).
215 Furthermore, since any additional entry in a loc list containing a
216 debug loc would have to come from an assignment (nondebug) that
217 references both the initial debug loc and the newly-equivalent loc,
218 the initial debug loc would be promoted to a nondebug loc, and the
219 loc list would not contain debug locs any more.
221 So the only case we have to be careful with in order to keep
222 n_useless_values in sync between debug and nondebug compilations is
223 to avoid incrementing n_useless_values when removing the single loc
224 from a value that turns out to not appear outside debug values. We
225 increment n_useless_debug_values instead, and leave such values
226 alone until, for other reasons, we garbage-collect useless
228 static int n_useless_values
;
229 static int n_useless_debug_values
;
231 /* Count values whose locs have been taken exclusively from debug
232 insns for the entire life of the value. */
233 static int n_debug_values
;
235 /* Number of useless values before we remove them from the hash table. */
236 #define MAX_USELESS_VALUES 32
238 /* This table maps from register number to values. It does not
239 contain pointers to cselib_val structures, but rather elt_lists.
240 The purpose is to be able to refer to the same register in
241 different modes. The first element of the list defines the mode in
242 which the register was set; if the mode is unknown or the value is
243 no longer valid in that mode, ELT will be NULL for the first
245 static struct elt_list
**reg_values
;
246 static unsigned int reg_values_size
;
247 #define REG_VALUES(i) reg_values[i]
249 /* The largest number of hard regs used by any entry added to the
250 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
251 static unsigned int max_value_regs
;
253 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
254 in cselib_clear_table() for fast emptying. */
255 static unsigned int *used_regs
;
256 static unsigned int n_used_regs
;
258 /* We pass this to cselib_invalidate_mem to invalidate all of
259 memory for a non-const call instruction. */
260 static GTY(()) rtx callmem
;
262 /* Set by discard_useless_locs if it deleted the last location of any
264 static int values_became_useless
;
266 /* Used as stop element of the containing_mem list so we can check
267 presence in the list by checking the next pointer. */
268 static cselib_val dummy_val
;
270 /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
271 that is constant through the whole function and should never be
273 static cselib_val
*cfa_base_preserved_val
;
274 static unsigned int cfa_base_preserved_regno
= INVALID_REGNUM
;
276 /* Used to list all values that contain memory reference.
277 May or may not contain the useless values - the list is compacted
278 each time memory is invalidated. */
279 static cselib_val
*first_containing_mem
= &dummy_val
;
281 pool_allocator
<elt_list
> elt_list::pool ("elt_list", 10);
282 pool_allocator
<elt_loc_list
> elt_loc_list::pool ("elt_loc_list", 10);
283 pool_allocator
<cselib_val
> cselib_val::pool ("cselib_val_list", 10);
285 static pool_allocator
<rtx_def
> value_pool ("value", 100, RTX_CODE_SIZE (VALUE
),
288 /* If nonnull, cselib will call this function before freeing useless
289 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
290 void (*cselib_discard_hook
) (cselib_val
*);
292 /* If nonnull, cselib will call this function before recording sets or
293 even clobbering outputs of INSN. All the recorded sets will be
294 represented in the array sets[n_sets]. new_val_min can be used to
295 tell whether values present in sets are introduced by this
297 void (*cselib_record_sets_hook
) (rtx_insn
*insn
, struct cselib_set
*sets
,
300 #define PRESERVED_VALUE_P(RTX) \
301 (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
303 #define SP_BASED_VALUE_P(RTX) \
304 (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump)
308 /* Allocate a struct elt_list and fill in its two elements with the
311 static inline struct elt_list
*
312 new_elt_list (struct elt_list
*next
, cselib_val
*elt
)
314 elt_list
*el
= new elt_list ();
320 /* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc
324 new_elt_loc_list (cselib_val
*val
, rtx loc
)
326 struct elt_loc_list
*el
, *next
= val
->locs
;
328 gcc_checking_assert (!next
|| !next
->setting_insn
329 || !DEBUG_INSN_P (next
->setting_insn
)
330 || cselib_current_insn
== next
->setting_insn
);
332 /* If we're creating the first loc in a debug insn context, we've
333 just created a debug value. Count it. */
334 if (!next
&& cselib_current_insn
&& DEBUG_INSN_P (cselib_current_insn
))
337 val
= canonical_cselib_val (val
);
340 if (GET_CODE (loc
) == VALUE
)
342 loc
= canonical_cselib_val (CSELIB_VAL_PTR (loc
))->val_rtx
;
344 gcc_checking_assert (PRESERVED_VALUE_P (loc
)
345 == PRESERVED_VALUE_P (val
->val_rtx
));
347 if (val
->val_rtx
== loc
)
349 else if (val
->uid
> CSELIB_VAL_PTR (loc
)->uid
)
351 /* Reverse the insertion. */
352 new_elt_loc_list (CSELIB_VAL_PTR (loc
), val
->val_rtx
);
356 gcc_checking_assert (val
->uid
< CSELIB_VAL_PTR (loc
)->uid
);
358 if (CSELIB_VAL_PTR (loc
)->locs
)
360 /* Bring all locs from LOC to VAL. */
361 for (el
= CSELIB_VAL_PTR (loc
)->locs
; el
->next
; el
= el
->next
)
363 /* Adjust values that have LOC as canonical so that VAL
364 becomes their canonical. */
365 if (el
->loc
&& GET_CODE (el
->loc
) == VALUE
)
367 gcc_checking_assert (CSELIB_VAL_PTR (el
->loc
)->locs
->loc
369 CSELIB_VAL_PTR (el
->loc
)->locs
->loc
= val
->val_rtx
;
372 el
->next
= val
->locs
;
373 next
= val
->locs
= CSELIB_VAL_PTR (loc
)->locs
;
376 if (CSELIB_VAL_PTR (loc
)->addr_list
)
378 /* Bring in addr_list into canonical node. */
379 struct elt_list
*last
= CSELIB_VAL_PTR (loc
)->addr_list
;
382 last
->next
= val
->addr_list
;
383 val
->addr_list
= CSELIB_VAL_PTR (loc
)->addr_list
;
384 CSELIB_VAL_PTR (loc
)->addr_list
= NULL
;
387 if (CSELIB_VAL_PTR (loc
)->next_containing_mem
!= NULL
388 && val
->next_containing_mem
== NULL
)
390 /* Add VAL to the containing_mem list after LOC. LOC will
391 be removed when we notice it doesn't contain any
393 val
->next_containing_mem
= CSELIB_VAL_PTR (loc
)->next_containing_mem
;
394 CSELIB_VAL_PTR (loc
)->next_containing_mem
= val
;
397 /* Chain LOC back to VAL. */
398 el
= new elt_loc_list
;
399 el
->loc
= val
->val_rtx
;
400 el
->setting_insn
= cselib_current_insn
;
402 CSELIB_VAL_PTR (loc
)->locs
= el
;
405 el
= new elt_loc_list
;
407 el
->setting_insn
= cselib_current_insn
;
412 /* Promote loc L to a nondebug cselib_current_insn if L is marked as
413 originating from a debug insn, maintaining the debug values
417 promote_debug_loc (struct elt_loc_list
*l
)
419 if (l
&& l
->setting_insn
&& DEBUG_INSN_P (l
->setting_insn
)
420 && (!cselib_current_insn
|| !DEBUG_INSN_P (cselib_current_insn
)))
423 l
->setting_insn
= cselib_current_insn
;
424 if (cselib_preserve_constants
&& l
->next
)
426 gcc_assert (l
->next
->setting_insn
427 && DEBUG_INSN_P (l
->next
->setting_insn
)
429 l
->next
->setting_insn
= cselib_current_insn
;
432 gcc_assert (!l
->next
);
436 /* The elt_list at *PL is no longer needed. Unchain it and free its
440 unchain_one_elt_list (struct elt_list
**pl
)
442 struct elt_list
*l
= *pl
;
448 /* Likewise for elt_loc_lists. */
451 unchain_one_elt_loc_list (struct elt_loc_list
**pl
)
453 struct elt_loc_list
*l
= *pl
;
459 /* Likewise for cselib_vals. This also frees the addr_list associated with
463 unchain_one_value (cselib_val
*v
)
466 unchain_one_elt_list (&v
->addr_list
);
471 /* Remove all entries from the hash table. Also used during
475 cselib_clear_table (void)
477 cselib_reset_table (1);
480 /* Return TRUE if V is a constant, a function invariant or a VALUE
481 equivalence; FALSE otherwise. */
484 invariant_or_equiv_p (cselib_val
*v
)
486 struct elt_loc_list
*l
;
488 if (v
== cfa_base_preserved_val
)
491 /* Keep VALUE equivalences around. */
492 for (l
= v
->locs
; l
; l
= l
->next
)
493 if (GET_CODE (l
->loc
) == VALUE
)
497 && v
->locs
->next
== NULL
)
499 if (CONSTANT_P (v
->locs
->loc
)
500 && (GET_CODE (v
->locs
->loc
) != CONST
501 || !references_value_p (v
->locs
->loc
, 0)))
503 /* Although a debug expr may be bound to different expressions,
504 we can preserve it as if it was constant, to get unification
505 and proper merging within var-tracking. */
506 if (GET_CODE (v
->locs
->loc
) == DEBUG_EXPR
507 || GET_CODE (v
->locs
->loc
) == DEBUG_IMPLICIT_PTR
508 || GET_CODE (v
->locs
->loc
) == ENTRY_VALUE
509 || GET_CODE (v
->locs
->loc
) == DEBUG_PARAMETER_REF
)
512 /* (plus (value V) (const_int C)) is invariant iff V is invariant. */
513 if (GET_CODE (v
->locs
->loc
) == PLUS
514 && CONST_INT_P (XEXP (v
->locs
->loc
, 1))
515 && GET_CODE (XEXP (v
->locs
->loc
, 0)) == VALUE
516 && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v
->locs
->loc
, 0))))
523 /* Remove from hash table all VALUEs except constants, function
524 invariants and VALUE equivalences. */
527 preserve_constants_and_equivs (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
531 if (invariant_or_equiv_p (v
))
533 cselib_hasher::key lookup
= {
534 GET_MODE (v
->val_rtx
), v
->val_rtx
, VOIDmode
537 = cselib_preserved_hash_table
->find_slot_with_hash (&lookup
,
543 cselib_hash_table
->clear_slot (x
);
548 /* Remove all entries from the hash table, arranging for the next
549 value to be numbered NUM. */
552 cselib_reset_table (unsigned int num
)
558 if (cfa_base_preserved_val
)
560 unsigned int regno
= cfa_base_preserved_regno
;
561 unsigned int new_used_regs
= 0;
562 for (i
= 0; i
< n_used_regs
; i
++)
563 if (used_regs
[i
] == regno
)
569 REG_VALUES (used_regs
[i
]) = 0;
570 gcc_assert (new_used_regs
== 1);
571 n_used_regs
= new_used_regs
;
572 used_regs
[0] = regno
;
574 = hard_regno_nregs
[regno
][GET_MODE (cfa_base_preserved_val
->locs
->loc
)];
578 for (i
= 0; i
< n_used_regs
; i
++)
579 REG_VALUES (used_regs
[i
]) = 0;
583 if (cselib_preserve_constants
)
584 cselib_hash_table
->traverse
<void *, preserve_constants_and_equivs
>
588 cselib_hash_table
->empty ();
589 gcc_checking_assert (!cselib_any_perm_equivs
);
592 n_useless_values
= 0;
593 n_useless_debug_values
= 0;
598 first_containing_mem
= &dummy_val
;
601 /* Return the number of the next value that will be generated. */
604 cselib_get_next_uid (void)
609 /* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE,
610 INSERTing if requested. When X is part of the address of a MEM,
611 MEMMODE should specify the mode of the MEM. */
614 cselib_find_slot (machine_mode mode
, rtx x
, hashval_t hash
,
615 enum insert_option insert
, machine_mode memmode
)
617 cselib_val
**slot
= NULL
;
618 cselib_hasher::key lookup
= { mode
, x
, memmode
};
619 if (cselib_preserve_constants
)
620 slot
= cselib_preserved_hash_table
->find_slot_with_hash (&lookup
, hash
,
623 slot
= cselib_hash_table
->find_slot_with_hash (&lookup
, hash
, insert
);
627 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
628 only return true for values which point to a cselib_val whose value
629 element has been set to zero, which implies the cselib_val will be
633 references_value_p (const_rtx x
, int only_useless
)
635 const enum rtx_code code
= GET_CODE (x
);
636 const char *fmt
= GET_RTX_FORMAT (code
);
639 if (GET_CODE (x
) == VALUE
640 && (! only_useless
||
641 (CSELIB_VAL_PTR (x
)->locs
== 0 && !PRESERVED_VALUE_P (x
))))
644 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
646 if (fmt
[i
] == 'e' && references_value_p (XEXP (x
, i
), only_useless
))
648 else if (fmt
[i
] == 'E')
649 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
650 if (references_value_p (XVECEXP (x
, i
, j
), only_useless
))
657 /* For all locations found in X, delete locations that reference useless
658 values (i.e. values without any location). Called through
662 discard_useless_locs (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
665 struct elt_loc_list
**p
= &v
->locs
;
666 bool had_locs
= v
->locs
!= NULL
;
667 rtx_insn
*setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
671 if (references_value_p ((*p
)->loc
, 1))
672 unchain_one_elt_loc_list (p
);
677 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
679 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
680 n_useless_debug_values
++;
683 values_became_useless
= 1;
688 /* If X is a value with no locations, remove it from the hashtable. */
691 discard_useless_values (cselib_val
**x
, void *info ATTRIBUTE_UNUSED
)
695 if (v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
697 if (cselib_discard_hook
)
698 cselib_discard_hook (v
);
700 CSELIB_VAL_PTR (v
->val_rtx
) = NULL
;
701 cselib_hash_table
->clear_slot (x
);
702 unchain_one_value (v
);
709 /* Clean out useless values (i.e. those which no longer have locations
710 associated with them) from the hash table. */
713 remove_useless_values (void)
717 /* First pass: eliminate locations that reference the value. That in
718 turn can make more values useless. */
721 values_became_useless
= 0;
722 cselib_hash_table
->traverse
<void *, discard_useless_locs
> (NULL
);
724 while (values_became_useless
);
726 /* Second pass: actually remove the values. */
728 p
= &first_containing_mem
;
729 for (v
= *p
; v
!= &dummy_val
; v
= v
->next_containing_mem
)
730 if (v
->locs
&& v
== canonical_cselib_val (v
))
733 p
= &(*p
)->next_containing_mem
;
737 n_useless_values
+= n_useless_debug_values
;
738 n_debug_values
-= n_useless_debug_values
;
739 n_useless_debug_values
= 0;
741 cselib_hash_table
->traverse
<void *, discard_useless_values
> (NULL
);
743 gcc_assert (!n_useless_values
);
746 /* Arrange for a value to not be removed from the hash table even if
747 it becomes useless. */
750 cselib_preserve_value (cselib_val
*v
)
752 PRESERVED_VALUE_P (v
->val_rtx
) = 1;
755 /* Test whether a value is preserved. */
758 cselib_preserved_value_p (cselib_val
*v
)
760 return PRESERVED_VALUE_P (v
->val_rtx
);
763 /* Arrange for a REG value to be assumed constant through the whole function,
764 never invalidated and preserved across cselib_reset_table calls. */
767 cselib_preserve_cfa_base_value (cselib_val
*v
, unsigned int regno
)
769 if (cselib_preserve_constants
771 && REG_P (v
->locs
->loc
))
773 cfa_base_preserved_val
= v
;
774 cfa_base_preserved_regno
= regno
;
778 /* Clean all non-constant expressions in the hash table, but retain
782 cselib_preserve_only_values (void)
786 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
787 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
789 cselib_invalidate_mem (callmem
);
791 remove_useless_values ();
793 gcc_assert (first_containing_mem
== &dummy_val
);
796 /* Arrange for a value to be marked as based on stack pointer
797 for find_base_term purposes. */
800 cselib_set_value_sp_based (cselib_val
*v
)
802 SP_BASED_VALUE_P (v
->val_rtx
) = 1;
805 /* Test whether a value is based on stack pointer for
806 find_base_term purposes. */
809 cselib_sp_based_value_p (cselib_val
*v
)
811 return SP_BASED_VALUE_P (v
->val_rtx
);
814 /* Return the mode in which a register was last set. If X is not a
815 register, return its mode. If the mode in which the register was
816 set is not known, or the value was already clobbered, return
820 cselib_reg_set_mode (const_rtx x
)
825 if (REG_VALUES (REGNO (x
)) == NULL
826 || REG_VALUES (REGNO (x
))->elt
== NULL
)
829 return GET_MODE (REG_VALUES (REGNO (x
))->elt
->val_rtx
);
832 /* Return nonzero if we can prove that X and Y contain the same value, taking
833 our gathered information into account. */
836 rtx_equal_for_cselib_p (rtx x
, rtx y
)
838 return rtx_equal_for_cselib_1 (x
, y
, VOIDmode
);
841 /* If x is a PLUS or an autoinc operation, expand the operation,
842 storing the offset, if any, in *OFF. */
845 autoinc_split (rtx x
, rtx
*off
, machine_mode memmode
)
847 switch (GET_CODE (x
))
854 if (memmode
== VOIDmode
)
857 *off
= GEN_INT (-GET_MODE_SIZE (memmode
));
862 if (memmode
== VOIDmode
)
865 *off
= GEN_INT (GET_MODE_SIZE (memmode
));
881 /* Return nonzero if we can prove that X and Y contain the same value,
882 taking our gathered information into account. MEMMODE holds the
883 mode of the enclosing MEM, if any, as required to deal with autoinc
884 addressing modes. If X and Y are not (known to be) part of
885 addresses, MEMMODE should be VOIDmode. */
888 rtx_equal_for_cselib_1 (rtx x
, rtx y
, machine_mode memmode
)
894 if (REG_P (x
) || MEM_P (x
))
896 cselib_val
*e
= cselib_lookup (x
, GET_MODE (x
), 0, memmode
);
902 if (REG_P (y
) || MEM_P (y
))
904 cselib_val
*e
= cselib_lookup (y
, GET_MODE (y
), 0, memmode
);
913 if (GET_CODE (x
) == VALUE
)
915 cselib_val
*e
= canonical_cselib_val (CSELIB_VAL_PTR (x
));
916 struct elt_loc_list
*l
;
918 if (GET_CODE (y
) == VALUE
)
919 return e
== canonical_cselib_val (CSELIB_VAL_PTR (y
));
921 for (l
= e
->locs
; l
; l
= l
->next
)
925 /* Avoid infinite recursion. We know we have the canonical
926 value, so we can just skip any values in the equivalence
928 if (REG_P (t
) || MEM_P (t
) || GET_CODE (t
) == VALUE
)
930 else if (rtx_equal_for_cselib_1 (t
, y
, memmode
))
936 else if (GET_CODE (y
) == VALUE
)
938 cselib_val
*e
= canonical_cselib_val (CSELIB_VAL_PTR (y
));
939 struct elt_loc_list
*l
;
941 for (l
= e
->locs
; l
; l
= l
->next
)
945 if (REG_P (t
) || MEM_P (t
) || GET_CODE (t
) == VALUE
)
947 else if (rtx_equal_for_cselib_1 (x
, t
, memmode
))
954 if (GET_MODE (x
) != GET_MODE (y
))
957 if (GET_CODE (x
) != GET_CODE (y
))
959 rtx xorig
= x
, yorig
= y
;
960 rtx xoff
= NULL
, yoff
= NULL
;
962 x
= autoinc_split (x
, &xoff
, memmode
);
963 y
= autoinc_split (y
, &yoff
, memmode
);
968 if (xoff
&& !rtx_equal_for_cselib_1 (xoff
, yoff
, memmode
))
971 /* Don't recurse if nothing changed. */
972 if (x
!= xorig
|| y
!= yorig
)
973 return rtx_equal_for_cselib_1 (x
, y
, memmode
);
978 /* These won't be handled correctly by the code below. */
979 switch (GET_CODE (x
))
985 case DEBUG_IMPLICIT_PTR
:
986 return DEBUG_IMPLICIT_PTR_DECL (x
)
987 == DEBUG_IMPLICIT_PTR_DECL (y
);
989 case DEBUG_PARAMETER_REF
:
990 return DEBUG_PARAMETER_REF_DECL (x
)
991 == DEBUG_PARAMETER_REF_DECL (y
);
994 /* ENTRY_VALUEs are function invariant, it is thus undesirable to
995 use rtx_equal_for_cselib_1 to compare the operands. */
996 return rtx_equal_p (ENTRY_VALUE_EXP (x
), ENTRY_VALUE_EXP (y
));
999 return LABEL_REF_LABEL (x
) == LABEL_REF_LABEL (y
);
1002 return REGNO (x
) == REGNO (y
);
1005 /* We have to compare any autoinc operations in the addresses
1006 using this MEM's mode. */
1007 return rtx_equal_for_cselib_1 (XEXP (x
, 0), XEXP (y
, 0), GET_MODE (x
));
1013 code
= GET_CODE (x
);
1014 fmt
= GET_RTX_FORMAT (code
);
1016 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1023 if (XWINT (x
, i
) != XWINT (y
, i
))
1029 if (XINT (x
, i
) != XINT (y
, i
))
1035 /* Two vectors must have the same length. */
1036 if (XVECLEN (x
, i
) != XVECLEN (y
, i
))
1039 /* And the corresponding elements must match. */
1040 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1041 if (! rtx_equal_for_cselib_1 (XVECEXP (x
, i
, j
),
1042 XVECEXP (y
, i
, j
), memmode
))
1048 && targetm
.commutative_p (x
, UNKNOWN
)
1049 && rtx_equal_for_cselib_1 (XEXP (x
, 1), XEXP (y
, 0), memmode
)
1050 && rtx_equal_for_cselib_1 (XEXP (x
, 0), XEXP (y
, 1), memmode
))
1052 if (! rtx_equal_for_cselib_1 (XEXP (x
, i
), XEXP (y
, i
), memmode
))
1058 if (strcmp (XSTR (x
, i
), XSTR (y
, i
)))
1063 /* These are just backpointers, so they don't matter. */
1070 /* It is believed that rtx's at this level will never
1071 contain anything but integers and other rtx's,
1072 except for within LABEL_REFs and SYMBOL_REFs. */
1080 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
1081 For registers and memory locations, we look up their cselib_val structure
1082 and return its VALUE element.
1083 Possible reasons for return 0 are: the object is volatile, or we couldn't
1084 find a register or memory location in the table and CREATE is zero. If
1085 CREATE is nonzero, table elts are created for regs and mem.
1086 N.B. this hash function returns the same hash value for RTXes that
1087 differ only in the order of operands, thus it is suitable for comparisons
1088 that take commutativity into account.
1089 If we wanted to also support associative rules, we'd have to use a different
1090 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
1091 MEMMODE indicates the mode of an enclosing MEM, and it's only
1092 used to compute autoinc values.
1093 We used to have a MODE argument for hashing for CONST_INTs, but that
1094 didn't make sense, since it caused spurious hash differences between
1095 (set (reg:SI 1) (const_int))
1096 (plus:SI (reg:SI 2) (reg:SI 1))
1098 (plus:SI (reg:SI 2) (const_int))
1099 If the mode is important in any context, it must be checked specifically
1100 in a comparison anyway, since relying on hash differences is unsafe. */
1103 cselib_hash_rtx (rtx x
, int create
, machine_mode memmode
)
1109 unsigned int hash
= 0;
1111 code
= GET_CODE (x
);
1112 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1117 e
= CSELIB_VAL_PTR (x
);
1122 e
= cselib_lookup (x
, GET_MODE (x
), create
, memmode
);
1129 hash
+= ((unsigned) DEBUG_EXPR
<< 7)
1130 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x
));
1131 return hash
? hash
: (unsigned int) DEBUG_EXPR
;
1133 case DEBUG_IMPLICIT_PTR
:
1134 hash
+= ((unsigned) DEBUG_IMPLICIT_PTR
<< 7)
1135 + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x
));
1136 return hash
? hash
: (unsigned int) DEBUG_IMPLICIT_PTR
;
1138 case DEBUG_PARAMETER_REF
:
1139 hash
+= ((unsigned) DEBUG_PARAMETER_REF
<< 7)
1140 + DECL_UID (DEBUG_PARAMETER_REF_DECL (x
));
1141 return hash
? hash
: (unsigned int) DEBUG_PARAMETER_REF
;
1144 /* ENTRY_VALUEs are function invariant, thus try to avoid
1145 recursing on argument if ENTRY_VALUE is one of the
1146 forms emitted by expand_debug_expr, otherwise
1147 ENTRY_VALUE hash would depend on the current value
1148 in some register or memory. */
1149 if (REG_P (ENTRY_VALUE_EXP (x
)))
1150 hash
+= (unsigned int) REG
1151 + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x
))
1152 + (unsigned int) REGNO (ENTRY_VALUE_EXP (x
));
1153 else if (MEM_P (ENTRY_VALUE_EXP (x
))
1154 && REG_P (XEXP (ENTRY_VALUE_EXP (x
), 0)))
1155 hash
+= (unsigned int) MEM
1156 + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x
), 0))
1157 + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x
), 0));
1159 hash
+= cselib_hash_rtx (ENTRY_VALUE_EXP (x
), create
, memmode
);
1160 return hash
? hash
: (unsigned int) ENTRY_VALUE
;
1163 hash
+= ((unsigned) CONST_INT
<< 7) + UINTVAL (x
);
1164 return hash
? hash
: (unsigned int) CONST_INT
;
1166 case CONST_WIDE_INT
:
1167 for (i
= 0; i
< CONST_WIDE_INT_NUNITS (x
); i
++)
1168 hash
+= CONST_WIDE_INT_ELT (x
, i
);
1172 /* This is like the general case, except that it only counts
1173 the integers representing the constant. */
1174 hash
+= (unsigned) code
+ (unsigned) GET_MODE (x
);
1175 if (TARGET_SUPPORTS_WIDE_INT
== 0 && GET_MODE (x
) == VOIDmode
)
1176 hash
+= ((unsigned) CONST_DOUBLE_LOW (x
)
1177 + (unsigned) CONST_DOUBLE_HIGH (x
));
1179 hash
+= real_hash (CONST_DOUBLE_REAL_VALUE (x
));
1180 return hash
? hash
: (unsigned int) CONST_DOUBLE
;
1183 hash
+= (unsigned int) code
+ (unsigned int) GET_MODE (x
);
1184 hash
+= fixed_hash (CONST_FIXED_VALUE (x
));
1185 return hash
? hash
: (unsigned int) CONST_FIXED
;
1192 units
= CONST_VECTOR_NUNITS (x
);
1194 for (i
= 0; i
< units
; ++i
)
1196 elt
= CONST_VECTOR_ELT (x
, i
);
1197 hash
+= cselib_hash_rtx (elt
, 0, memmode
);
1203 /* Assume there is only one rtx object for any given label. */
1205 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1206 differences and differences between each stage's debugging dumps. */
1207 hash
+= (((unsigned int) LABEL_REF
<< 7)
1208 + CODE_LABEL_NUMBER (LABEL_REF_LABEL (x
)));
1209 return hash
? hash
: (unsigned int) LABEL_REF
;
1213 /* Don't hash on the symbol's address to avoid bootstrap differences.
1214 Different hash values may cause expressions to be recorded in
1215 different orders and thus different registers to be used in the
1216 final assembler. This also avoids differences in the dump files
1217 between various stages. */
1219 const unsigned char *p
= (const unsigned char *) XSTR (x
, 0);
1222 h
+= (h
<< 7) + *p
++; /* ??? revisit */
1224 hash
+= ((unsigned int) SYMBOL_REF
<< 7) + h
;
1225 return hash
? hash
: (unsigned int) SYMBOL_REF
;
1230 /* We can't compute these without knowing the MEM mode. */
1231 gcc_assert (memmode
!= VOIDmode
);
1232 i
= GET_MODE_SIZE (memmode
);
1233 if (code
== PRE_DEC
)
1235 /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1236 like (mem:MEMMODE (plus (reg) (const_int I))). */
1237 hash
+= (unsigned) PLUS
- (unsigned)code
1238 + cselib_hash_rtx (XEXP (x
, 0), create
, memmode
)
1239 + cselib_hash_rtx (GEN_INT (i
), create
, memmode
);
1240 return hash
? hash
: 1 + (unsigned) PLUS
;
1243 gcc_assert (memmode
!= VOIDmode
);
1244 return cselib_hash_rtx (XEXP (x
, 1), create
, memmode
);
1249 gcc_assert (memmode
!= VOIDmode
);
1250 return cselib_hash_rtx (XEXP (x
, 0), create
, memmode
);
1255 case UNSPEC_VOLATILE
:
1259 if (MEM_VOLATILE_P (x
))
1268 i
= GET_RTX_LENGTH (code
) - 1;
1269 fmt
= GET_RTX_FORMAT (code
);
1276 rtx tem
= XEXP (x
, i
);
1277 unsigned int tem_hash
= cselib_hash_rtx (tem
, create
, memmode
);
1286 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1288 unsigned int tem_hash
1289 = cselib_hash_rtx (XVECEXP (x
, i
, j
), create
, memmode
);
1300 const unsigned char *p
= (const unsigned char *) XSTR (x
, i
);
1309 hash
+= XINT (x
, i
);
1322 return hash
? hash
: 1 + (unsigned int) GET_CODE (x
);
1325 /* Create a new value structure for VALUE and initialize it. The mode of the
1328 static inline cselib_val
*
1329 new_cselib_val (unsigned int hash
, machine_mode mode
, rtx x
)
1331 cselib_val
*e
= new cselib_val
;
1334 gcc_assert (next_uid
);
1337 e
->uid
= next_uid
++;
1338 /* We use an alloc pool to allocate this RTL construct because it
1339 accounts for about 8% of the overall memory usage. We know
1340 precisely when we can have VALUE RTXen (when cselib is active)
1341 so we don't need to put them in garbage collected memory.
1342 ??? Why should a VALUE be an RTX in the first place? */
1343 e
->val_rtx
= value_pool
.allocate ();
1344 memset (e
->val_rtx
, 0, RTX_HDR_SIZE
);
1345 PUT_CODE (e
->val_rtx
, VALUE
);
1346 PUT_MODE (e
->val_rtx
, mode
);
1347 CSELIB_VAL_PTR (e
->val_rtx
) = e
;
1350 e
->next_containing_mem
= 0;
1352 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1354 fprintf (dump_file
, "cselib value %u:%u ", e
->uid
, hash
);
1355 if (flag_dump_noaddr
|| flag_dump_unnumbered
)
1356 fputs ("# ", dump_file
);
1358 fprintf (dump_file
, "%p ", (void*)e
);
1359 print_rtl_single (dump_file
, x
);
1360 fputc ('\n', dump_file
);
1366 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
1367 contains the data at this address. X is a MEM that represents the
1368 value. Update the two value structures to represent this situation. */
1371 add_mem_for_addr (cselib_val
*addr_elt
, cselib_val
*mem_elt
, rtx x
)
1373 struct elt_loc_list
*l
;
1375 addr_elt
= canonical_cselib_val (addr_elt
);
1376 mem_elt
= canonical_cselib_val (mem_elt
);
1378 /* Avoid duplicates. */
1379 for (l
= mem_elt
->locs
; l
; l
= l
->next
)
1381 && CSELIB_VAL_PTR (XEXP (l
->loc
, 0)) == addr_elt
)
1383 promote_debug_loc (l
);
1387 addr_elt
->addr_list
= new_elt_list (addr_elt
->addr_list
, mem_elt
);
1388 new_elt_loc_list (mem_elt
,
1389 replace_equiv_address_nv (x
, addr_elt
->val_rtx
));
1390 if (mem_elt
->next_containing_mem
== NULL
)
1392 mem_elt
->next_containing_mem
= first_containing_mem
;
1393 first_containing_mem
= mem_elt
;
1397 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
1398 If CREATE, make a new one if we haven't seen it before. */
1401 cselib_lookup_mem (rtx x
, int create
)
1403 machine_mode mode
= GET_MODE (x
);
1404 machine_mode addr_mode
;
1407 cselib_val
*mem_elt
;
1410 if (MEM_VOLATILE_P (x
) || mode
== BLKmode
1411 || !cselib_record_memory
1412 || (FLOAT_MODE_P (mode
) && flag_float_store
))
1415 addr_mode
= GET_MODE (XEXP (x
, 0));
1416 if (addr_mode
== VOIDmode
)
1419 /* Look up the value for the address. */
1420 addr
= cselib_lookup (XEXP (x
, 0), addr_mode
, create
, mode
);
1424 addr
= canonical_cselib_val (addr
);
1425 /* Find a value that describes a value of our mode at that address. */
1426 for (l
= addr
->addr_list
; l
; l
= l
->next
)
1427 if (GET_MODE (l
->elt
->val_rtx
) == mode
)
1429 promote_debug_loc (l
->elt
->locs
);
1436 mem_elt
= new_cselib_val (next_uid
, mode
, x
);
1437 add_mem_for_addr (addr
, mem_elt
, x
);
1438 slot
= cselib_find_slot (mode
, x
, mem_elt
->hash
, INSERT
, VOIDmode
);
1443 /* Search through the possible substitutions in P. We prefer a non reg
1444 substitution because this allows us to expand the tree further. If
1445 we find, just a reg, take the lowest regno. There may be several
1446 non-reg results, we just take the first one because they will all
1447 expand to the same place. */
1450 expand_loc (struct elt_loc_list
*p
, struct expand_value_data
*evd
,
1453 rtx reg_result
= NULL
;
1454 unsigned int regno
= UINT_MAX
;
1455 struct elt_loc_list
*p_in
= p
;
1457 for (; p
; p
= p
->next
)
1459 /* Return these right away to avoid returning stack pointer based
1460 expressions for frame pointer and vice versa, which is something
1461 that would confuse DSE. See the comment in cselib_expand_value_rtx_1
1462 for more details. */
1464 && (REGNO (p
->loc
) == STACK_POINTER_REGNUM
1465 || REGNO (p
->loc
) == FRAME_POINTER_REGNUM
1466 || REGNO (p
->loc
) == HARD_FRAME_POINTER_REGNUM
1467 || REGNO (p
->loc
) == cfa_base_preserved_regno
))
1469 /* Avoid infinite recursion trying to expand a reg into a
1471 if ((REG_P (p
->loc
))
1472 && (REGNO (p
->loc
) < regno
)
1473 && !bitmap_bit_p (evd
->regs_active
, REGNO (p
->loc
)))
1475 reg_result
= p
->loc
;
1476 regno
= REGNO (p
->loc
);
1478 /* Avoid infinite recursion and do not try to expand the
1480 else if (GET_CODE (p
->loc
) == VALUE
1481 && CSELIB_VAL_PTR (p
->loc
)->locs
== p_in
)
1483 else if (!REG_P (p
->loc
))
1486 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1488 print_inline_rtx (dump_file
, p
->loc
, 0);
1489 fprintf (dump_file
, "\n");
1491 if (GET_CODE (p
->loc
) == LO_SUM
1492 && GET_CODE (XEXP (p
->loc
, 1)) == SYMBOL_REF
1494 && (note
= find_reg_note (p
->setting_insn
, REG_EQUAL
, NULL_RTX
))
1495 && XEXP (note
, 0) == XEXP (p
->loc
, 1))
1496 return XEXP (p
->loc
, 1);
1497 result
= cselib_expand_value_rtx_1 (p
->loc
, evd
, max_depth
- 1);
1504 if (regno
!= UINT_MAX
)
1507 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1508 fprintf (dump_file
, "r%d\n", regno
);
1510 result
= cselib_expand_value_rtx_1 (reg_result
, evd
, max_depth
- 1);
1515 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1519 print_inline_rtx (dump_file
, reg_result
, 0);
1520 fprintf (dump_file
, "\n");
1523 fprintf (dump_file
, "NULL\n");
1529 /* Forward substitute and expand an expression out to its roots.
1530 This is the opposite of common subexpression. Because local value
1531 numbering is such a weak optimization, the expanded expression is
1532 pretty much unique (not from a pointer equals point of view but
1533 from a tree shape point of view.
1535 This function returns NULL if the expansion fails. The expansion
1536 will fail if there is no value number for one of the operands or if
1537 one of the operands has been overwritten between the current insn
1538 and the beginning of the basic block. For instance x has no
1544 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1545 It is clear on return. */
1548 cselib_expand_value_rtx (rtx orig
, bitmap regs_active
, int max_depth
)
1550 struct expand_value_data evd
;
1552 evd
.regs_active
= regs_active
;
1553 evd
.callback
= NULL
;
1554 evd
.callback_arg
= NULL
;
1557 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1560 /* Same as cselib_expand_value_rtx, but using a callback to try to
1561 resolve some expressions. The CB function should return ORIG if it
1562 can't or does not want to deal with a certain RTX. Any other
1563 return value, including NULL, will be used as the expansion for
1564 VALUE, without any further changes. */
1567 cselib_expand_value_rtx_cb (rtx orig
, bitmap regs_active
, int max_depth
,
1568 cselib_expand_callback cb
, void *data
)
1570 struct expand_value_data evd
;
1572 evd
.regs_active
= regs_active
;
1574 evd
.callback_arg
= data
;
1577 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
);
1580 /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1581 or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1582 would return NULL or non-NULL, without allocating new rtx. */
1585 cselib_dummy_expand_value_rtx_cb (rtx orig
, bitmap regs_active
, int max_depth
,
1586 cselib_expand_callback cb
, void *data
)
1588 struct expand_value_data evd
;
1590 evd
.regs_active
= regs_active
;
1592 evd
.callback_arg
= data
;
1595 return cselib_expand_value_rtx_1 (orig
, &evd
, max_depth
) != NULL
;
1598 /* Internal implementation of cselib_expand_value_rtx and
1599 cselib_expand_value_rtx_cb. */
1602 cselib_expand_value_rtx_1 (rtx orig
, struct expand_value_data
*evd
,
1608 const char *format_ptr
;
1611 code
= GET_CODE (orig
);
1613 /* For the context of dse, if we end up expand into a huge tree, we
1614 will not have a useful address, so we might as well just give up
1623 struct elt_list
*l
= REG_VALUES (REGNO (orig
));
1625 if (l
&& l
->elt
== NULL
)
1627 for (; l
; l
= l
->next
)
1628 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (orig
))
1631 unsigned regno
= REGNO (orig
);
1633 /* The only thing that we are not willing to do (this
1634 is requirement of dse and if others potential uses
1635 need this function we should add a parm to control
1636 it) is that we will not substitute the
1637 STACK_POINTER_REGNUM, FRAME_POINTER or the
1640 These expansions confuses the code that notices that
1641 stores into the frame go dead at the end of the
1642 function and that the frame is not effected by calls
1643 to subroutines. If you allow the
1644 STACK_POINTER_REGNUM substitution, then dse will
1645 think that parameter pushing also goes dead which is
1646 wrong. If you allow the FRAME_POINTER or the
1647 HARD_FRAME_POINTER then you lose the opportunity to
1648 make the frame assumptions. */
1649 if (regno
== STACK_POINTER_REGNUM
1650 || regno
== FRAME_POINTER_REGNUM
1651 || regno
== HARD_FRAME_POINTER_REGNUM
1652 || regno
== cfa_base_preserved_regno
)
1655 bitmap_set_bit (evd
->regs_active
, regno
);
1657 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1658 fprintf (dump_file
, "expanding: r%d into: ", regno
);
1660 result
= expand_loc (l
->elt
->locs
, evd
, max_depth
);
1661 bitmap_clear_bit (evd
->regs_active
, regno
);
1676 /* SCRATCH must be shared because they represent distinct values. */
1679 if (REG_P (XEXP (orig
, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig
, 0))))
1684 if (shared_const_p (orig
))
1694 subreg
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1700 subreg
= cselib_expand_value_rtx_1 (SUBREG_REG (orig
), evd
,
1704 scopy
= simplify_gen_subreg (GET_MODE (orig
), subreg
,
1705 GET_MODE (SUBREG_REG (orig
)),
1706 SUBREG_BYTE (orig
));
1708 || (GET_CODE (scopy
) == SUBREG
1709 && !REG_P (SUBREG_REG (scopy
))
1710 && !MEM_P (SUBREG_REG (scopy
))))
1720 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
1722 fputs ("\nexpanding ", dump_file
);
1723 print_rtl_single (dump_file
, orig
);
1724 fputs (" into...", dump_file
);
1729 result
= evd
->callback (orig
, evd
->regs_active
, max_depth
,
1736 result
= expand_loc (CSELIB_VAL_PTR (orig
)->locs
, evd
, max_depth
);
1742 return evd
->callback (orig
, evd
->regs_active
, max_depth
,
1750 /* Copy the various flags, fields, and other information. We assume
1751 that all fields need copying, and then clear the fields that should
1752 not be copied. That is the sensible default behavior, and forces
1753 us to explicitly document why we are *not* copying a flag. */
1757 copy
= shallow_copy_rtx (orig
);
1759 format_ptr
= GET_RTX_FORMAT (code
);
1761 for (i
= 0; i
< GET_RTX_LENGTH (code
); i
++)
1762 switch (*format_ptr
++)
1765 if (XEXP (orig
, i
) != NULL
)
1767 rtx result
= cselib_expand_value_rtx_1 (XEXP (orig
, i
), evd
,
1772 XEXP (copy
, i
) = result
;
1778 if (XVEC (orig
, i
) != NULL
)
1781 XVEC (copy
, i
) = rtvec_alloc (XVECLEN (orig
, i
));
1782 for (j
= 0; j
< XVECLEN (orig
, i
); j
++)
1784 rtx result
= cselib_expand_value_rtx_1 (XVECEXP (orig
, i
, j
),
1785 evd
, max_depth
- 1);
1789 XVECEXP (copy
, i
, j
) = result
;
1803 /* These are left unchanged. */
1813 mode
= GET_MODE (copy
);
1814 /* If an operand has been simplified into CONST_INT, which doesn't
1815 have a mode and the mode isn't derivable from whole rtx's mode,
1816 try simplify_*_operation first with mode from original's operand
1817 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1819 switch (GET_RTX_CLASS (code
))
1822 if (CONST_INT_P (XEXP (copy
, 0))
1823 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1825 scopy
= simplify_unary_operation (code
, mode
, XEXP (copy
, 0),
1826 GET_MODE (XEXP (orig
, 0)));
1831 case RTX_COMM_ARITH
:
1833 /* These expressions can derive operand modes from the whole rtx's mode. */
1836 case RTX_BITFIELD_OPS
:
1837 if (CONST_INT_P (XEXP (copy
, 0))
1838 && GET_MODE (XEXP (orig
, 0)) != VOIDmode
)
1840 scopy
= simplify_ternary_operation (code
, mode
,
1841 GET_MODE (XEXP (orig
, 0)),
1842 XEXP (copy
, 0), XEXP (copy
, 1),
1849 case RTX_COMM_COMPARE
:
1850 if (CONST_INT_P (XEXP (copy
, 0))
1851 && GET_MODE (XEXP (copy
, 1)) == VOIDmode
1852 && (GET_MODE (XEXP (orig
, 0)) != VOIDmode
1853 || GET_MODE (XEXP (orig
, 1)) != VOIDmode
))
1855 scopy
= simplify_relational_operation (code
, mode
,
1856 (GET_MODE (XEXP (orig
, 0))
1858 ? GET_MODE (XEXP (orig
, 0))
1859 : GET_MODE (XEXP (orig
, 1)),
1869 scopy
= simplify_rtx (copy
);
1875 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1876 with VALUE expressions. This way, it becomes independent of changes
1877 to registers and memory.
1878 X isn't actually modified; if modifications are needed, new rtl is
1879 allocated. However, the return value can share rtl with X.
1880 If X is within a MEM, MEMMODE must be the mode of the MEM. */
1883 cselib_subst_to_values (rtx x
, machine_mode memmode
)
1885 enum rtx_code code
= GET_CODE (x
);
1886 const char *fmt
= GET_RTX_FORMAT (code
);
1895 l
= REG_VALUES (REGNO (x
));
1896 if (l
&& l
->elt
== NULL
)
1898 for (; l
; l
= l
->next
)
1899 if (GET_MODE (l
->elt
->val_rtx
) == GET_MODE (x
))
1900 return l
->elt
->val_rtx
;
1905 e
= cselib_lookup_mem (x
, 0);
1906 /* This used to happen for autoincrements, but we deal with them
1907 properly now. Remove the if stmt for the next release. */
1910 /* Assign a value that doesn't match any other. */
1911 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
1916 e
= cselib_lookup (x
, GET_MODE (x
), 0, memmode
);
1926 gcc_assert (memmode
!= VOIDmode
);
1927 i
= GET_MODE_SIZE (memmode
);
1928 if (code
== PRE_DEC
)
1930 return cselib_subst_to_values (plus_constant (GET_MODE (x
),
1935 gcc_assert (memmode
!= VOIDmode
);
1936 return cselib_subst_to_values (XEXP (x
, 1), memmode
);
1941 gcc_assert (memmode
!= VOIDmode
);
1942 return cselib_subst_to_values (XEXP (x
, 0), memmode
);
1948 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1952 rtx t
= cselib_subst_to_values (XEXP (x
, i
), memmode
);
1954 if (t
!= XEXP (x
, i
))
1957 copy
= shallow_copy_rtx (x
);
1961 else if (fmt
[i
] == 'E')
1965 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1967 rtx t
= cselib_subst_to_values (XVECEXP (x
, i
, j
), memmode
);
1969 if (t
!= XVECEXP (x
, i
, j
))
1971 if (XVEC (x
, i
) == XVEC (copy
, i
))
1974 copy
= shallow_copy_rtx (x
);
1975 XVEC (copy
, i
) = shallow_copy_rtvec (XVEC (x
, i
));
1977 XVECEXP (copy
, i
, j
) = t
;
1986 /* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */
1989 cselib_subst_to_values_from_insn (rtx x
, machine_mode memmode
, rtx_insn
*insn
)
1992 gcc_assert (!cselib_current_insn
);
1993 cselib_current_insn
= insn
;
1994 ret
= cselib_subst_to_values (x
, memmode
);
1995 cselib_current_insn
= NULL
;
1999 /* Look up the rtl expression X in our tables and return the value it
2000 has. If CREATE is zero, we return NULL if we don't know the value.
2001 Otherwise, we create a new one if possible, using mode MODE if X
2002 doesn't have a mode (i.e. because it's a constant). When X is part
2003 of an address, MEMMODE should be the mode of the enclosing MEM if
2004 we're tracking autoinc expressions. */
2007 cselib_lookup_1 (rtx x
, machine_mode mode
,
2008 int create
, machine_mode memmode
)
2012 unsigned int hashval
;
2014 if (GET_MODE (x
) != VOIDmode
)
2015 mode
= GET_MODE (x
);
2017 if (GET_CODE (x
) == VALUE
)
2018 return CSELIB_VAL_PTR (x
);
2023 unsigned int i
= REGNO (x
);
2026 if (l
&& l
->elt
== NULL
)
2028 for (; l
; l
= l
->next
)
2029 if (mode
== GET_MODE (l
->elt
->val_rtx
))
2031 promote_debug_loc (l
->elt
->locs
);
2038 if (i
< FIRST_PSEUDO_REGISTER
)
2040 unsigned int n
= hard_regno_nregs
[i
][mode
];
2042 if (n
> max_value_regs
)
2046 e
= new_cselib_val (next_uid
, GET_MODE (x
), x
);
2047 new_elt_loc_list (e
, x
);
2048 if (REG_VALUES (i
) == 0)
2050 /* Maintain the invariant that the first entry of
2051 REG_VALUES, if present, must be the value used to set the
2052 register, or NULL. */
2053 used_regs
[n_used_regs
++] = i
;
2054 REG_VALUES (i
) = new_elt_list (REG_VALUES (i
), NULL
);
2056 else if (cselib_preserve_constants
2057 && GET_MODE_CLASS (mode
) == MODE_INT
)
2059 /* During var-tracking, try harder to find equivalences
2060 for SUBREGs. If a setter sets say a DImode register
2061 and user uses that register only in SImode, add a lowpart
2063 struct elt_list
*lwider
= NULL
;
2065 if (l
&& l
->elt
== NULL
)
2067 for (; l
; l
= l
->next
)
2068 if (GET_MODE_CLASS (GET_MODE (l
->elt
->val_rtx
)) == MODE_INT
2069 && GET_MODE_SIZE (GET_MODE (l
->elt
->val_rtx
))
2070 > GET_MODE_SIZE (mode
)
2072 || GET_MODE_SIZE (GET_MODE (l
->elt
->val_rtx
))
2073 < GET_MODE_SIZE (GET_MODE (lwider
->elt
->val_rtx
))))
2075 struct elt_loc_list
*el
;
2076 if (i
< FIRST_PSEUDO_REGISTER
2077 && hard_regno_nregs
[i
][GET_MODE (l
->elt
->val_rtx
)] != 1)
2079 for (el
= l
->elt
->locs
; el
; el
= el
->next
)
2080 if (!REG_P (el
->loc
))
2087 rtx sub
= lowpart_subreg (mode
, lwider
->elt
->val_rtx
,
2088 GET_MODE (lwider
->elt
->val_rtx
));
2090 new_elt_loc_list (e
, sub
);
2093 REG_VALUES (i
)->next
= new_elt_list (REG_VALUES (i
)->next
, e
);
2094 slot
= cselib_find_slot (mode
, x
, e
->hash
, INSERT
, memmode
);
2100 return cselib_lookup_mem (x
, create
);
2102 hashval
= cselib_hash_rtx (x
, create
, memmode
);
2103 /* Can't even create if hashing is not possible. */
2107 slot
= cselib_find_slot (mode
, x
, hashval
,
2108 create
? INSERT
: NO_INSERT
, memmode
);
2112 e
= (cselib_val
*) *slot
;
2116 e
= new_cselib_val (hashval
, mode
, x
);
2118 /* We have to fill the slot before calling cselib_subst_to_values:
2119 the hash table is inconsistent until we do so, and
2120 cselib_subst_to_values will need to do lookups. */
2122 new_elt_loc_list (e
, cselib_subst_to_values (x
, memmode
));
2126 /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2129 cselib_lookup_from_insn (rtx x
, machine_mode mode
,
2130 int create
, machine_mode memmode
, rtx_insn
*insn
)
2134 gcc_assert (!cselib_current_insn
);
2135 cselib_current_insn
= insn
;
2137 ret
= cselib_lookup (x
, mode
, create
, memmode
);
2139 cselib_current_insn
= NULL
;
2144 /* Wrapper for cselib_lookup_1, that logs the lookup result and
2145 maintains invariants related with debug insns. */
2148 cselib_lookup (rtx x
, machine_mode mode
,
2149 int create
, machine_mode memmode
)
2151 cselib_val
*ret
= cselib_lookup_1 (x
, mode
, create
, memmode
);
2153 /* ??? Should we return NULL if we're not to create an entry, the
2154 found loc is a debug loc and cselib_current_insn is not DEBUG?
2155 If so, we should also avoid converting val to non-DEBUG; probably
2156 easiest setting cselib_current_insn to NULL before the call
2159 if (dump_file
&& (dump_flags
& TDF_CSELIB
))
2161 fputs ("cselib lookup ", dump_file
);
2162 print_inline_rtx (dump_file
, x
, 2);
2163 fprintf (dump_file
, " => %u:%u\n",
2165 ret
? ret
->hash
: 0);
2171 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2172 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2173 is used to determine how many hard registers are being changed. If MODE
2174 is VOIDmode, then only REGNO is being changed; this is used when
2175 invalidating call clobbered registers across a call. */
2178 cselib_invalidate_regno (unsigned int regno
, machine_mode mode
)
2180 unsigned int endregno
;
2183 /* If we see pseudos after reload, something is _wrong_. */
2184 gcc_assert (!reload_completed
|| regno
< FIRST_PSEUDO_REGISTER
2185 || reg_renumber
[regno
] < 0);
2187 /* Determine the range of registers that must be invalidated. For
2188 pseudos, only REGNO is affected. For hard regs, we must take MODE
2189 into account, and we must also invalidate lower register numbers
2190 if they contain values that overlap REGNO. */
2191 if (regno
< FIRST_PSEUDO_REGISTER
)
2193 gcc_assert (mode
!= VOIDmode
);
2195 if (regno
< max_value_regs
)
2198 i
= regno
- max_value_regs
;
2200 endregno
= end_hard_regno (mode
, regno
);
2205 endregno
= regno
+ 1;
2208 for (; i
< endregno
; i
++)
2210 struct elt_list
**l
= ®_VALUES (i
);
2212 /* Go through all known values for this reg; if it overlaps the range
2213 we're invalidating, remove the value. */
2216 cselib_val
*v
= (*l
)->elt
;
2218 rtx_insn
*setting_insn
;
2219 struct elt_loc_list
**p
;
2220 unsigned int this_last
= i
;
2222 if (i
< FIRST_PSEUDO_REGISTER
&& v
!= NULL
)
2223 this_last
= end_hard_regno (GET_MODE (v
->val_rtx
), i
) - 1;
2225 if (this_last
< regno
|| v
== NULL
2226 || (v
== cfa_base_preserved_val
2227 && i
== cfa_base_preserved_regno
))
2233 /* We have an overlap. */
2234 if (*l
== REG_VALUES (i
))
2236 /* Maintain the invariant that the first entry of
2237 REG_VALUES, if present, must be the value used to set
2238 the register, or NULL. This is also nice because
2239 then we won't push the same regno onto user_regs
2245 unchain_one_elt_list (l
);
2247 v
= canonical_cselib_val (v
);
2249 had_locs
= v
->locs
!= NULL
;
2250 setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
2252 /* Now, we clear the mapping from value to reg. It must exist, so
2253 this code will crash intentionally if it doesn't. */
2254 for (p
= &v
->locs
; ; p
= &(*p
)->next
)
2258 if (REG_P (x
) && REGNO (x
) == i
)
2260 unchain_one_elt_loc_list (p
);
2265 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
2267 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
2268 n_useless_debug_values
++;
2276 /* Invalidate any locations in the table which are changed because of a
2277 store to MEM_RTX. If this is called because of a non-const call
2278 instruction, MEM_RTX is (mem:BLK const0_rtx). */
2281 cselib_invalidate_mem (rtx mem_rtx
)
2283 cselib_val
**vp
, *v
, *next
;
2287 mem_addr
= canon_rtx (get_addr (XEXP (mem_rtx
, 0)));
2288 mem_rtx
= canon_rtx (mem_rtx
);
2290 vp
= &first_containing_mem
;
2291 for (v
= *vp
; v
!= &dummy_val
; v
= next
)
2293 bool has_mem
= false;
2294 struct elt_loc_list
**p
= &v
->locs
;
2295 bool had_locs
= v
->locs
!= NULL
;
2296 rtx_insn
*setting_insn
= v
->locs
? v
->locs
->setting_insn
: NULL
;
2302 struct elt_list
**mem_chain
;
2304 /* MEMs may occur in locations only at the top level; below
2305 that every MEM or REG is substituted by its VALUE. */
2311 if (num_mems
< PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS
)
2312 && ! canon_anti_dependence (x
, false, mem_rtx
,
2313 GET_MODE (mem_rtx
), mem_addr
))
2321 /* This one overlaps. */
2322 /* We must have a mapping from this MEM's address to the
2323 value (E). Remove that, too. */
2324 addr
= cselib_lookup (XEXP (x
, 0), VOIDmode
, 0, GET_MODE (x
));
2325 addr
= canonical_cselib_val (addr
);
2326 gcc_checking_assert (v
== canonical_cselib_val (v
));
2327 mem_chain
= &addr
->addr_list
;
2330 cselib_val
*canon
= canonical_cselib_val ((*mem_chain
)->elt
);
2334 unchain_one_elt_list (mem_chain
);
2338 /* Record canonicalized elt. */
2339 (*mem_chain
)->elt
= canon
;
2341 mem_chain
= &(*mem_chain
)->next
;
2344 unchain_one_elt_loc_list (p
);
2347 if (had_locs
&& v
->locs
== 0 && !PRESERVED_VALUE_P (v
->val_rtx
))
2349 if (setting_insn
&& DEBUG_INSN_P (setting_insn
))
2350 n_useless_debug_values
++;
2355 next
= v
->next_containing_mem
;
2359 vp
= &(*vp
)->next_containing_mem
;
2362 v
->next_containing_mem
= NULL
;
2367 /* Invalidate DEST, which is being assigned to or clobbered. */
2370 cselib_invalidate_rtx (rtx dest
)
2372 while (GET_CODE (dest
) == SUBREG
2373 || GET_CODE (dest
) == ZERO_EXTRACT
2374 || GET_CODE (dest
) == STRICT_LOW_PART
)
2375 dest
= XEXP (dest
, 0);
2378 cselib_invalidate_regno (REGNO (dest
), GET_MODE (dest
));
2379 else if (MEM_P (dest
))
2380 cselib_invalidate_mem (dest
);
2383 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2386 cselib_invalidate_rtx_note_stores (rtx dest
, const_rtx ignore ATTRIBUTE_UNUSED
,
2387 void *data ATTRIBUTE_UNUSED
)
2389 cselib_invalidate_rtx (dest
);
2392 /* Record the result of a SET instruction. DEST is being set; the source
2393 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
2394 describes its address. */
2397 cselib_record_set (rtx dest
, cselib_val
*src_elt
, cselib_val
*dest_addr_elt
)
2399 if (src_elt
== 0 || side_effects_p (dest
))
2404 unsigned int dreg
= REGNO (dest
);
2405 if (dreg
< FIRST_PSEUDO_REGISTER
)
2407 unsigned int n
= REG_NREGS (dest
);
2409 if (n
> max_value_regs
)
2413 if (REG_VALUES (dreg
) == 0)
2415 used_regs
[n_used_regs
++] = dreg
;
2416 REG_VALUES (dreg
) = new_elt_list (REG_VALUES (dreg
), src_elt
);
2420 /* The register should have been invalidated. */
2421 gcc_assert (REG_VALUES (dreg
)->elt
== 0);
2422 REG_VALUES (dreg
)->elt
= src_elt
;
2425 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
2427 new_elt_loc_list (src_elt
, dest
);
2429 else if (MEM_P (dest
) && dest_addr_elt
!= 0
2430 && cselib_record_memory
)
2432 if (src_elt
->locs
== 0 && !PRESERVED_VALUE_P (src_elt
->val_rtx
))
2434 add_mem_for_addr (dest_addr_elt
, src_elt
, dest
);
2438 /* Make ELT and X's VALUE equivalent to each other at INSN. */
2441 cselib_add_permanent_equiv (cselib_val
*elt
, rtx x
, rtx_insn
*insn
)
2444 rtx_insn
*save_cselib_current_insn
= cselib_current_insn
;
2446 gcc_checking_assert (elt
);
2447 gcc_checking_assert (PRESERVED_VALUE_P (elt
->val_rtx
));
2448 gcc_checking_assert (!side_effects_p (x
));
2450 cselib_current_insn
= insn
;
2452 nelt
= cselib_lookup (x
, GET_MODE (elt
->val_rtx
), 1, VOIDmode
);
2456 cselib_any_perm_equivs
= true;
2458 if (!PRESERVED_VALUE_P (nelt
->val_rtx
))
2459 cselib_preserve_value (nelt
);
2461 new_elt_loc_list (nelt
, elt
->val_rtx
);
2464 cselib_current_insn
= save_cselib_current_insn
;
2467 /* Return TRUE if any permanent equivalences have been recorded since
2468 the table was last initialized. */
2470 cselib_have_permanent_equivalences (void)
2472 return cselib_any_perm_equivs
;
2475 /* There is no good way to determine how many elements there can be
2476 in a PARALLEL. Since it's fairly cheap, use a really large number. */
2477 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
2479 struct cselib_record_autoinc_data
2481 struct cselib_set
*sets
;
2485 /* Callback for for_each_inc_dec. Records in ARG the SETs implied by
2486 autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */
2489 cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED
, rtx op ATTRIBUTE_UNUSED
,
2490 rtx dest
, rtx src
, rtx srcoff
, void *arg
)
2492 struct cselib_record_autoinc_data
*data
;
2493 data
= (struct cselib_record_autoinc_data
*)arg
;
2495 data
->sets
[data
->n_sets
].dest
= dest
;
2498 data
->sets
[data
->n_sets
].src
= gen_rtx_PLUS (GET_MODE (src
), src
, srcoff
);
2500 data
->sets
[data
->n_sets
].src
= src
;
2507 /* Record the effects of any sets and autoincs in INSN. */
2509 cselib_record_sets (rtx_insn
*insn
)
2513 struct cselib_set sets
[MAX_SETS
];
2514 rtx body
= PATTERN (insn
);
2516 int n_sets_before_autoinc
;
2517 struct cselib_record_autoinc_data data
;
2519 body
= PATTERN (insn
);
2520 if (GET_CODE (body
) == COND_EXEC
)
2522 cond
= COND_EXEC_TEST (body
);
2523 body
= COND_EXEC_CODE (body
);
2526 /* Find all sets. */
2527 if (GET_CODE (body
) == SET
)
2529 sets
[0].src
= SET_SRC (body
);
2530 sets
[0].dest
= SET_DEST (body
);
2533 else if (GET_CODE (body
) == PARALLEL
)
2535 /* Look through the PARALLEL and record the values being
2536 set, if possible. Also handle any CLOBBERs. */
2537 for (i
= XVECLEN (body
, 0) - 1; i
>= 0; --i
)
2539 rtx x
= XVECEXP (body
, 0, i
);
2541 if (GET_CODE (x
) == SET
)
2543 sets
[n_sets
].src
= SET_SRC (x
);
2544 sets
[n_sets
].dest
= SET_DEST (x
);
2551 && MEM_P (sets
[0].src
)
2552 && !cselib_record_memory
2553 && MEM_READONLY_P (sets
[0].src
))
2555 rtx note
= find_reg_equal_equiv_note (insn
);
2557 if (note
&& CONSTANT_P (XEXP (note
, 0)))
2558 sets
[0].src
= XEXP (note
, 0);
2562 data
.n_sets
= n_sets_before_autoinc
= n_sets
;
2563 for_each_inc_dec (PATTERN (insn
), cselib_record_autoinc_cb
, &data
);
2564 n_sets
= data
.n_sets
;
2566 /* Look up the values that are read. Do this before invalidating the
2567 locations that are written. */
2568 for (i
= 0; i
< n_sets
; i
++)
2570 rtx dest
= sets
[i
].dest
;
2572 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
2573 the low part after invalidating any knowledge about larger modes. */
2574 if (GET_CODE (sets
[i
].dest
) == STRICT_LOW_PART
)
2575 sets
[i
].dest
= dest
= XEXP (dest
, 0);
2577 /* We don't know how to record anything but REG or MEM. */
2579 || (MEM_P (dest
) && cselib_record_memory
))
2581 rtx src
= sets
[i
].src
;
2583 src
= gen_rtx_IF_THEN_ELSE (GET_MODE (dest
), cond
, src
, dest
);
2584 sets
[i
].src_elt
= cselib_lookup (src
, GET_MODE (dest
), 1, VOIDmode
);
2587 machine_mode address_mode
= get_address_mode (dest
);
2589 sets
[i
].dest_addr_elt
= cselib_lookup (XEXP (dest
, 0),
2594 sets
[i
].dest_addr_elt
= 0;
2598 if (cselib_record_sets_hook
)
2599 cselib_record_sets_hook (insn
, sets
, n_sets
);
2601 /* Invalidate all locations written by this insn. Note that the elts we
2602 looked up in the previous loop aren't affected, just some of their
2603 locations may go away. */
2604 note_stores (body
, cselib_invalidate_rtx_note_stores
, NULL
);
2606 for (i
= n_sets_before_autoinc
; i
< n_sets
; i
++)
2607 cselib_invalidate_rtx (sets
[i
].dest
);
2609 /* If this is an asm, look for duplicate sets. This can happen when the
2610 user uses the same value as an output multiple times. This is valid
2611 if the outputs are not actually used thereafter. Treat this case as
2612 if the value isn't actually set. We do this by smashing the destination
2613 to pc_rtx, so that we won't record the value later. */
2614 if (n_sets
>= 2 && asm_noperands (body
) >= 0)
2616 for (i
= 0; i
< n_sets
; i
++)
2618 rtx dest
= sets
[i
].dest
;
2619 if (REG_P (dest
) || MEM_P (dest
))
2622 for (j
= i
+ 1; j
< n_sets
; j
++)
2623 if (rtx_equal_p (dest
, sets
[j
].dest
))
2625 sets
[i
].dest
= pc_rtx
;
2626 sets
[j
].dest
= pc_rtx
;
2632 /* Now enter the equivalences in our tables. */
2633 for (i
= 0; i
< n_sets
; i
++)
2635 rtx dest
= sets
[i
].dest
;
2637 || (MEM_P (dest
) && cselib_record_memory
))
2638 cselib_record_set (dest
, sets
[i
].src_elt
, sets
[i
].dest_addr_elt
);
2642 /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
2645 fp_setter_insn (rtx_insn
*insn
)
2647 rtx expr
, pat
= NULL_RTX
;
2649 if (!RTX_FRAME_RELATED_P (insn
))
2652 expr
= find_reg_note (insn
, REG_FRAME_RELATED_EXPR
, NULL_RTX
);
2654 pat
= XEXP (expr
, 0);
2655 if (!modified_in_p (hard_frame_pointer_rtx
, pat
? pat
: insn
))
2658 /* Don't return true for frame pointer restores in the epilogue. */
2659 if (find_reg_note (insn
, REG_CFA_RESTORE
, hard_frame_pointer_rtx
))
2664 /* Record the effects of INSN. */
2667 cselib_process_insn (rtx_insn
*insn
)
2672 cselib_current_insn
= insn
;
2674 /* Forget everything at a CODE_LABEL or a setjmp. */
2677 && find_reg_note (insn
, REG_SETJMP
, NULL
)))
2678 && !cselib_preserve_constants
)
2680 cselib_reset_table (next_uid
);
2681 cselib_current_insn
= NULL
;
2685 if (! INSN_P (insn
))
2687 cselib_current_insn
= NULL
;
2691 /* If this is a call instruction, forget anything stored in a
2692 call clobbered register, or, if this is not a const call, in
2696 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2697 if (call_used_regs
[i
]
2698 || (REG_VALUES (i
) && REG_VALUES (i
)->elt
2699 && HARD_REGNO_CALL_PART_CLOBBERED (i
,
2700 GET_MODE (REG_VALUES (i
)->elt
->val_rtx
))))
2701 cselib_invalidate_regno (i
, reg_raw_mode
[i
]);
2703 /* Since it is not clear how cselib is going to be used, be
2704 conservative here and treat looping pure or const functions
2705 as if they were regular functions. */
2706 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
2707 || !(RTL_CONST_OR_PURE_CALL_P (insn
)))
2708 cselib_invalidate_mem (callmem
);
2711 cselib_record_sets (insn
);
2713 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2714 after we have processed the insn. */
2717 for (x
= CALL_INSN_FUNCTION_USAGE (insn
); x
; x
= XEXP (x
, 1))
2718 if (GET_CODE (XEXP (x
, 0)) == CLOBBER
)
2719 cselib_invalidate_rtx (XEXP (XEXP (x
, 0), 0));
2720 /* Flush evertything on setjmp. */
2721 if (cselib_preserve_constants
2722 && find_reg_note (insn
, REG_SETJMP
, NULL
))
2724 cselib_preserve_only_values ();
2725 cselib_reset_table (next_uid
);
2729 /* On setter of the hard frame pointer if frame_pointer_needed,
2730 invalidate stack_pointer_rtx, so that sp and {,h}fp based
2731 VALUEs are distinct. */
2732 if (reload_completed
2733 && frame_pointer_needed
2734 && fp_setter_insn (insn
))
2735 cselib_invalidate_rtx (stack_pointer_rtx
);
2737 cselib_current_insn
= NULL
;
2739 if (n_useless_values
> MAX_USELESS_VALUES
2740 /* remove_useless_values is linear in the hash table size. Avoid
2741 quadratic behavior for very large hashtables with very few
2742 useless elements. */
2743 && ((unsigned int)n_useless_values
2744 > (cselib_hash_table
->elements () - n_debug_values
) / 4))
2745 remove_useless_values ();
2748 /* Initialize cselib for one pass. The caller must also call
2749 init_alias_analysis. */
2752 cselib_init (int record_what
)
2754 cselib_record_memory
= record_what
& CSELIB_RECORD_MEMORY
;
2755 cselib_preserve_constants
= record_what
& CSELIB_PRESERVE_CONSTANTS
;
2756 cselib_any_perm_equivs
= false;
2758 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2759 see canon_true_dependence. This is only created once. */
2761 callmem
= gen_rtx_MEM (BLKmode
, gen_rtx_SCRATCH (VOIDmode
));
2763 cselib_nregs
= max_reg_num ();
2765 /* We preserve reg_values to allow expensive clearing of the whole thing.
2766 Reallocate it however if it happens to be too large. */
2767 if (!reg_values
|| reg_values_size
< cselib_nregs
2768 || (reg_values_size
> 10 && reg_values_size
> cselib_nregs
* 4))
2771 /* Some space for newly emit instructions so we don't end up
2772 reallocating in between passes. */
2773 reg_values_size
= cselib_nregs
+ (63 + cselib_nregs
) / 16;
2774 reg_values
= XCNEWVEC (struct elt_list
*, reg_values_size
);
2776 used_regs
= XNEWVEC (unsigned int, cselib_nregs
);
2778 cselib_hash_table
= new hash_table
<cselib_hasher
> (31);
2779 if (cselib_preserve_constants
)
2780 cselib_preserved_hash_table
= new hash_table
<cselib_hasher
> (31);
2784 /* Called when the current user is done with cselib. */
2787 cselib_finish (void)
2789 bool preserved
= cselib_preserve_constants
;
2790 cselib_discard_hook
= NULL
;
2791 cselib_preserve_constants
= false;
2792 cselib_any_perm_equivs
= false;
2793 cfa_base_preserved_val
= NULL
;
2794 cfa_base_preserved_regno
= INVALID_REGNUM
;
2795 elt_list::pool
.release ();
2796 elt_loc_list::pool
.release ();
2797 cselib_val::pool
.release ();
2798 value_pool
.release ();
2799 cselib_clear_table ();
2800 delete cselib_hash_table
;
2801 cselib_hash_table
= NULL
;
2803 delete cselib_preserved_hash_table
;
2804 cselib_preserved_hash_table
= NULL
;
2807 n_useless_values
= 0;
2808 n_useless_debug_values
= 0;
2813 /* Dump the cselib_val *X to FILE *OUT. */
2816 dump_cselib_val (cselib_val
**x
, FILE *out
)
2819 bool need_lf
= true;
2821 print_inline_rtx (out
, v
->val_rtx
, 0);
2825 struct elt_loc_list
*l
= v
->locs
;
2831 fputs (" locs:", out
);
2834 if (l
->setting_insn
)
2835 fprintf (out
, "\n from insn %i ",
2836 INSN_UID (l
->setting_insn
));
2838 fprintf (out
, "\n ");
2839 print_inline_rtx (out
, l
->loc
, 4);
2841 while ((l
= l
->next
));
2846 fputs (" no locs", out
);
2852 struct elt_list
*e
= v
->addr_list
;
2858 fputs (" addr list:", out
);
2862 print_inline_rtx (out
, e
->elt
->val_rtx
, 2);
2864 while ((e
= e
->next
));
2869 fputs (" no addrs", out
);
2873 if (v
->next_containing_mem
== &dummy_val
)
2874 fputs (" last mem\n", out
);
2875 else if (v
->next_containing_mem
)
2877 fputs (" next mem ", out
);
2878 print_inline_rtx (out
, v
->next_containing_mem
->val_rtx
, 2);
2887 /* Dump to OUT everything in the CSELIB table. */
2890 dump_cselib_table (FILE *out
)
2892 fprintf (out
, "cselib hash table:\n");
2893 cselib_hash_table
->traverse
<FILE *, dump_cselib_val
> (out
);
2894 fprintf (out
, "cselib preserved hash table:\n");
2895 cselib_preserved_hash_table
->traverse
<FILE *, dump_cselib_val
> (out
);
2896 if (first_containing_mem
!= &dummy_val
)
2898 fputs ("first mem ", out
);
2899 print_inline_rtx (out
, first_containing_mem
->val_rtx
, 2);
2902 fprintf (out
, "next uid %i\n", next_uid
);
2905 #include "gt-cselib.h"