Line data Source code
1 : /* Common subexpression elimination library for GNU compiler.
2 : Copyright (C) 1987-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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
9 : version.
10 :
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
14 : for more details.
15 :
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/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "target.h"
25 : #include "rtl.h"
26 : #include "tree.h"
27 : #include "df.h"
28 : #include "memmodel.h"
29 : #include "tm_p.h"
30 : #include "regs.h"
31 : #include "emit-rtl.h"
32 : #include "dumpfile.h"
33 : #include "cselib.h"
34 : #include "function-abi.h"
35 : #include "alias.h"
36 : #include "predict.h"
37 : #include "rtl-iter.h"
38 :
39 : /* A list of cselib_val structures. */
40 : struct elt_list
41 : {
42 : struct elt_list *next;
43 : cselib_val *elt;
44 : };
45 :
46 : static bool cselib_record_memory;
47 : static bool cselib_preserve_constants;
48 : static bool cselib_any_perm_equivs;
49 : static inline void promote_debug_loc (struct elt_loc_list *l);
50 : static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
51 : static void new_elt_loc_list (cselib_val *, rtx);
52 : static void unchain_one_value (cselib_val *);
53 : static void unchain_one_elt_list (struct elt_list **);
54 : static void unchain_one_elt_loc_list (struct elt_loc_list **);
55 : static void remove_useless_values (void);
56 : static hashval_t cselib_hash_rtx (rtx, int, machine_mode);
57 : static cselib_val *new_cselib_val (unsigned int, machine_mode, rtx);
58 : static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
59 : static cselib_val *cselib_lookup_mem (rtx, int);
60 : static void cselib_invalidate_regno (unsigned int, machine_mode);
61 : static void cselib_invalidate_mem (rtx);
62 : static void cselib_record_set (rtx, cselib_val *, cselib_val *);
63 : static void cselib_record_sets (rtx_insn *);
64 : static rtx autoinc_split (rtx, rtx *, machine_mode);
65 :
66 : #define PRESERVED_VALUE_P(RTX) \
67 : (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
68 :
69 : #define SP_BASED_VALUE_P(RTX) \
70 : (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump)
71 :
72 : #define SP_DERIVED_VALUE_P(RTX) \
73 : (RTL_FLAG_CHECK1 ("SP_DERIVED_VALUE_P", (RTX), VALUE)->call)
74 :
75 : struct expand_value_data
76 : {
77 : bitmap regs_active;
78 : cselib_expand_callback callback;
79 : void *callback_arg;
80 : bool dummy;
81 : };
82 :
83 : static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
84 :
85 : /* This is a global so we don't have to pass this through every function.
86 : It is used in new_elt_loc_list to set SETTING_INSN. */
87 : static rtx_insn *cselib_current_insn;
88 :
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. */
97 :
98 : struct cselib_hasher : nofree_ptr_hash <cselib_val>
99 : {
100 : struct key {
101 : /* The rtx value and its mode (needed separately for constant
102 : integers). */
103 : machine_mode mode;
104 : rtx x;
105 : /* The mode of the containing MEM, if any, otherwise VOIDmode. */
106 : machine_mode memmode;
107 : };
108 : typedef key *compare_type;
109 : static inline hashval_t hash (const cselib_val *);
110 : static inline bool equal (const cselib_val *, const key *);
111 : };
112 :
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. */
116 :
117 : inline hashval_t
118 103765006 : cselib_hasher::hash (const cselib_val *v)
119 : {
120 103765006 : return v->hash;
121 : }
122 :
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. */
127 :
128 : inline bool
129 588831789 : cselib_hasher::equal (const cselib_val *v, const key *x_arg)
130 : {
131 588831789 : struct elt_loc_list *l;
132 588831789 : rtx x = x_arg->x;
133 588831789 : machine_mode mode = x_arg->mode;
134 588831789 : machine_mode memmode = x_arg->memmode;
135 :
136 588831789 : if (mode != GET_MODE (v->val_rtx))
137 : return false;
138 :
139 474966399 : if (GET_CODE (x) == VALUE)
140 13187572 : return x == v->val_rtx;
141 :
142 471855353 : if (SP_DERIVED_VALUE_P (v->val_rtx) && GET_MODE (x) == Pmode)
143 : {
144 17995244 : rtx xoff = NULL;
145 17995244 : if (autoinc_split (x, &xoff, memmode) == v->val_rtx && xoff == NULL_RTX)
146 7946467 : return true;
147 : }
148 :
149 : /* We don't guarantee that distinct rtx's have different hash values,
150 : so we need to do a comparison. */
151 778382242 : for (l = v->locs; l; l = l->next)
152 506251679 : if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)
153 41906987 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
154 : {
155 11603827 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
156 : /* If l is so far a debug only loc, without debug stmts it
157 : would never be compared to x at all, so temporarily pretend
158 : current instruction is that DEBUG_INSN so that we don't
159 : promote other debug locs even for unsuccessful comparison. */
160 11603827 : cselib_current_insn = l->setting_insn;
161 11603827 : bool match = rtx_equal_for_cselib_1 (l->loc, x, memmode, 0);
162 11603827 : cselib_current_insn = save_cselib_current_insn;
163 11603827 : if (match)
164 : {
165 929282 : promote_debug_loc (l);
166 929282 : return true;
167 : }
168 : }
169 494647852 : else if (rtx_equal_for_cselib_1 (l->loc, x, memmode, 0))
170 : return true;
171 :
172 : return false;
173 : }
174 :
175 : /* A table that enables us to look up elts by their value. */
176 : static hash_table<cselib_hasher> *cselib_hash_table;
177 :
178 : /* A table to hold preserved values. */
179 : static hash_table<cselib_hasher> *cselib_preserved_hash_table;
180 :
181 : /* The subset of cselib_preserved_hash_table that might have useless locations.
182 : It excludes values for which all_locs_preserved_p is true.
183 :
184 : This is an important compile-time optimization for inputs that have
185 : many preserved values and many basic blocks (such as insn-extract.cc
186 : at the time of writing, especially with RTL checking enabled).
187 : If remove_useless_values iterated over the whole hash table for every
188 : block, it would repeat a lot of useless and cache-unfriendly work. */
189 : static vec<cselib_val *> cselib_preserved_prune_list;
190 :
191 : /* The unique id that the next create value will take. */
192 : static unsigned int next_uid;
193 :
194 : /* The number of registers we had when the varrays were last resized. */
195 : static unsigned int cselib_nregs;
196 :
197 : /* Count values without known locations, or with only locations that
198 : wouldn't have been known except for debug insns. Whenever this
199 : grows too big, we remove these useless values from the table.
200 :
201 : Counting values with only debug values is a bit tricky. We don't
202 : want to increment n_useless_values when we create a value for a
203 : debug insn, for this would get n_useless_values out of sync, but we
204 : want increment it if all locs in the list that were ever referenced
205 : in nondebug insns are removed from the list.
206 :
207 : In the general case, once we do that, we'd have to stop accepting
208 : nondebug expressions in the loc list, to avoid having two values
209 : equivalent that, without debug insns, would have been made into
210 : separate values. However, because debug insns never introduce
211 : equivalences themselves (no assignments), the only means for
212 : growing loc lists is through nondebug assignments. If the locs
213 : also happen to be referenced in debug insns, it will work just fine.
214 :
215 : A consequence of this is that there's at most one debug-only loc in
216 : each loc list. If we keep it in the first entry, testing whether
217 : we have a debug-only loc list takes O(1).
218 :
219 : Furthermore, since any additional entry in a loc list containing a
220 : debug loc would have to come from an assignment (nondebug) that
221 : references both the initial debug loc and the newly-equivalent loc,
222 : the initial debug loc would be promoted to a nondebug loc, and the
223 : loc list would not contain debug locs any more.
224 :
225 : So the only case we have to be careful with in order to keep
226 : n_useless_values in sync between debug and nondebug compilations is
227 : to avoid incrementing n_useless_values when removing the single loc
228 : from a value that turns out to not appear outside debug values. We
229 : increment n_useless_debug_values instead, and leave such values
230 : alone until, for other reasons, we garbage-collect useless
231 : values. */
232 : static int n_useless_values;
233 : static int n_useless_debug_values;
234 :
235 : /* Count values whose locs have been taken exclusively from debug
236 : insns for the entire life of the value. */
237 : static int n_debug_values;
238 :
239 : /* Number of useless values before we remove them from the hash table. */
240 : #define MAX_USELESS_VALUES 32
241 :
242 : /* This table maps from register number to values. It does not
243 : contain pointers to cselib_val structures, but rather elt_lists.
244 : The purpose is to be able to refer to the same register in
245 : different modes. The first element of the list defines the mode in
246 : which the register was set; if the mode is unknown or the value is
247 : no longer valid in that mode, ELT will be NULL for the first
248 : element. */
249 : static struct elt_list **reg_values;
250 : static unsigned int reg_values_size;
251 : #define REG_VALUES(i) reg_values[i]
252 :
253 : /* The largest number of hard regs used by any entry added to the
254 : REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
255 : static unsigned int max_value_regs;
256 :
257 : /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
258 : in cselib_clear_table() for fast emptying. */
259 : static unsigned int *used_regs;
260 : static unsigned int n_used_regs;
261 :
262 : /* We pass this to cselib_invalidate_mem to invalidate all of
263 : memory for a non-const call instruction and memory below stack pointer
264 : for const/pure calls. */
265 : static GTY(()) rtx callmem[2];
266 :
267 : /* Set by discard_useless_locs if it deleted the last location of any
268 : value. */
269 : static int values_became_useless;
270 :
271 : /* Used as stop element of the containing_mem list so we can check
272 : presence in the list by checking the next pointer. */
273 : static cselib_val dummy_val;
274 :
275 : /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
276 : that is constant through the whole function and should never be
277 : eliminated. */
278 : static cselib_val *cfa_base_preserved_val;
279 : static unsigned int cfa_base_preserved_regno = INVALID_REGNUM;
280 :
281 : /* Used to list all values that contain memory reference.
282 : May or may not contain the useless values - the list is compacted
283 : each time memory is invalidated. */
284 : static cselib_val *first_containing_mem = &dummy_val;
285 :
286 : static object_allocator<elt_list> elt_list_pool ("elt_list");
287 : static object_allocator<elt_loc_list> elt_loc_list_pool ("elt_loc_list");
288 : static object_allocator<cselib_val> cselib_val_pool ("cselib_val_list");
289 :
290 : static pool_allocator value_pool ("value", RTX_CODE_SIZE (VALUE));
291 :
292 : /* If nonnull, cselib will call this function before freeing useless
293 : VALUEs. A VALUE is deemed useless if its "locs" field is null. */
294 : void (*cselib_discard_hook) (cselib_val *);
295 :
296 : /* If nonnull, cselib will call this function before recording sets or
297 : even clobbering outputs of INSN. All the recorded sets will be
298 : represented in the array sets[n_sets]. new_val_min can be used to
299 : tell whether values present in sets are introduced by this
300 : instruction. */
301 : void (*cselib_record_sets_hook) (rtx_insn *insn, struct cselib_set *sets,
302 : int n_sets);
303 :
304 :
305 :
306 : /* Allocate a struct elt_list and fill in its two elements with the
307 : arguments. */
308 :
309 : static inline struct elt_list *
310 493941268 : new_elt_list (struct elt_list *next, cselib_val *elt)
311 : {
312 987882536 : elt_list *el = elt_list_pool.allocate ();
313 493941268 : el->next = next;
314 493941268 : el->elt = elt;
315 493941268 : return el;
316 : }
317 :
318 : /* Record that all_locs_preserved_p might no longer hold for VAL. */
319 :
320 : static inline void
321 736024186 : cselib_clear_all_locs_preserved (cselib_val *val)
322 : {
323 736024186 : if (val->all_locs_preserved_p)
324 : {
325 7885295 : val->all_locs_preserved_p = false;
326 7885295 : if (val->in_preserved_table_p)
327 : /* VAL would have been removed from cselib_preserved_prune_list
328 : but now needs to be considered by remove_useless_values. */
329 7836107 : cselib_preserved_prune_list.safe_push (val);
330 : }
331 736024186 : }
332 :
333 : /* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc
334 : list. */
335 :
336 : static inline void
337 732043588 : new_elt_loc_list (cselib_val *val, rtx loc)
338 : {
339 736029284 : struct elt_loc_list *el, *next = val->locs;
340 :
341 736029284 : gcc_checking_assert (!next || !next->setting_insn
342 : || !DEBUG_INSN_P (next->setting_insn)
343 : || cselib_current_insn == next->setting_insn);
344 :
345 : /* If we're creating the first loc in a debug insn context, we've
346 : just created a debug value. Count it. */
347 430637557 : if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
348 7038317 : n_debug_values++;
349 :
350 736029284 : val = canonical_cselib_val (val);
351 736029284 : next = val->locs;
352 :
353 736029284 : if (GET_CODE (loc) == VALUE)
354 : {
355 7976870 : loc = canonical_cselib_val (CSELIB_VAL_PTR (loc))->val_rtx;
356 7976870 : auto *loc_val = CSELIB_VAL_PTR (loc);
357 :
358 7976870 : gcc_checking_assert (PRESERVED_VALUE_P (loc)
359 : == PRESERVED_VALUE_P (val->val_rtx));
360 :
361 7976870 : if (val->val_rtx == loc)
362 : return;
363 7971582 : else if (CSELIB_VAL_UID (val->val_rtx) > CSELIB_VAL_UID (loc))
364 : {
365 : /* Reverse the insertion. */
366 : new_elt_loc_list (loc_val, val->val_rtx);
367 : return;
368 : }
369 :
370 3985886 : gcc_checking_assert (CSELIB_VAL_UID (val->val_rtx)
371 : < CSELIB_VAL_UID (loc));
372 :
373 3985886 : if (loc_val->locs)
374 : {
375 : /* Bring all locs from LOC to VAL. */
376 3037106 : for (el = loc_val->locs; el->next; el = el->next)
377 : {
378 : /* Adjust values that have LOC as canonical so that VAL
379 : becomes their canonical. */
380 18 : if (el->loc && GET_CODE (el->loc) == VALUE)
381 : {
382 0 : auto *el_val = CSELIB_VAL_PTR (el->loc);
383 0 : gcc_checking_assert (el_val->locs->loc == loc);
384 0 : el_val->locs->loc = val->val_rtx;
385 0 : cselib_clear_all_locs_preserved (el_val);
386 : }
387 : }
388 3037088 : el->next = val->locs;
389 3037088 : next = val->locs = loc_val->locs;
390 : }
391 :
392 3985886 : if (loc_val->addr_list)
393 : {
394 : /* Bring in addr_list into canonical node. */
395 : struct elt_list *last = loc_val->addr_list;
396 2 : while (last->next)
397 : last = last->next;
398 2 : last->next = val->addr_list;
399 2 : val->addr_list = loc_val->addr_list;
400 2 : loc_val->addr_list = NULL;
401 : }
402 :
403 3985886 : if (loc_val->next_containing_mem != NULL
404 0 : && val->next_containing_mem == NULL)
405 : {
406 : /* Add VAL to the containing_mem list after LOC. LOC will
407 : be removed when we notice it doesn't contain any
408 : MEMs. */
409 0 : val->next_containing_mem = loc_val->next_containing_mem;
410 0 : loc_val->next_containing_mem = val;
411 : }
412 :
413 : /* Chain LOC back to VAL. */
414 3985886 : el = elt_loc_list_pool.allocate ();
415 3985886 : el->loc = val->val_rtx;
416 3985886 : el->setting_insn = cselib_current_insn;
417 3985886 : el->next = NULL;
418 3985886 : loc_val->locs = el;
419 3985886 : cselib_clear_all_locs_preserved (loc_val);
420 : }
421 :
422 732038300 : el = elt_loc_list_pool.allocate ();
423 732038300 : el->loc = loc;
424 732038300 : el->setting_insn = cselib_current_insn;
425 732038300 : el->next = next;
426 732038300 : val->locs = el;
427 732038300 : cselib_clear_all_locs_preserved (val);
428 : }
429 :
430 : /* Promote loc L to a nondebug cselib_current_insn if L is marked as
431 : originating from a debug insn, maintaining the debug values
432 : count. */
433 :
434 : static inline void
435 1241858160 : promote_debug_loc (struct elt_loc_list *l)
436 : {
437 1241858160 : if (l && l->setting_insn && DEBUG_INSN_P (l->setting_insn)
438 23540473 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
439 : {
440 2659657 : n_debug_values--;
441 2659657 : l->setting_insn = cselib_current_insn;
442 2659657 : if (cselib_preserve_constants && l->next)
443 : {
444 22402 : gcc_assert (l->next->setting_insn
445 : && DEBUG_INSN_P (l->next->setting_insn)
446 : && !l->next->next);
447 22402 : l->next->setting_insn = cselib_current_insn;
448 : }
449 : else
450 2637255 : gcc_assert (!l->next);
451 : }
452 1241858160 : }
453 :
454 : /* The elt_list at *PL is no longer needed. Unchain it and free its
455 : storage. */
456 :
457 : static inline void
458 81040197 : unchain_one_elt_list (struct elt_list **pl)
459 : {
460 81040197 : struct elt_list *l = *pl;
461 :
462 81040197 : *pl = l->next;
463 118835948 : elt_list_pool.remove (l);
464 43244446 : }
465 :
466 : /* Likewise for elt_loc_lists. */
467 :
468 : static void
469 227113085 : unchain_one_elt_loc_list (struct elt_loc_list **pl)
470 : {
471 227113085 : struct elt_loc_list *l = *pl;
472 :
473 227113085 : *pl = l->next;
474 0 : elt_loc_list_pool.remove (l);
475 39075442 : }
476 :
477 : /* Likewise for cselib_vals. This also frees the addr_list associated with
478 : V. */
479 :
480 : static void
481 2345275 : unchain_one_value (cselib_val *v)
482 : {
483 2364747 : while (v->addr_list)
484 19472 : unchain_one_elt_list (&v->addr_list);
485 :
486 2345275 : cselib_val_pool.remove (v);
487 2345275 : }
488 :
489 : /* Remove all entries from the hash table. Also used during
490 : initialization. */
491 :
492 : void
493 61825063 : cselib_clear_table (void)
494 : {
495 61825063 : cselib_reset_table (1);
496 61825063 : }
497 :
498 : /* Return TRUE if V is a constant, a function invariant or a VALUE
499 : equivalence; FALSE otherwise. */
500 :
501 : static bool
502 58834212 : invariant_or_equiv_p (cselib_val *v)
503 : {
504 58834212 : struct elt_loc_list *l;
505 :
506 58834212 : if (v == cfa_base_preserved_val)
507 : return true;
508 :
509 : /* Keep VALUE equivalences around. */
510 81735242 : for (l = v->locs; l; l = l->next)
511 39484062 : if (GET_CODE (l->loc) == VALUE)
512 : return true;
513 :
514 42251180 : if (v->locs != NULL
515 23212074 : && v->locs->next == NULL)
516 : {
517 23156050 : if (CONSTANT_P (v->locs->loc)
518 23156050 : && (GET_CODE (v->locs->loc) != CONST
519 166943 : || !references_value_p (v->locs->loc)))
520 3565502 : return true;
521 : /* Although a debug expr may be bound to different expressions,
522 : we can preserve it as if it was constant, to get unification
523 : and proper merging within var-tracking. */
524 19590548 : if (GET_CODE (v->locs->loc) == DEBUG_EXPR
525 17971969 : || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR
526 17457926 : || GET_CODE (v->locs->loc) == ENTRY_VALUE
527 17457724 : || GET_CODE (v->locs->loc) == DEBUG_PARAMETER_REF)
528 : return true;
529 :
530 : /* (plus (value V) (const_int C)) is invariant iff V is invariant. */
531 17439819 : if (GET_CODE (v->locs->loc) == PLUS
532 10783447 : && CONST_INT_P (XEXP (v->locs->loc, 1))
533 9659252 : && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE
534 26368525 : && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v->locs->loc, 0))))
535 : return true;
536 : }
537 :
538 : return false;
539 : }
540 :
541 : /* Remove from hash table all VALUEs except constants, function
542 : invariants and VALUE equivalences. */
543 :
544 : int
545 45447679 : preserve_constants_and_equivs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
546 : {
547 45447679 : cselib_val *v = *x;
548 :
549 45447679 : if (invariant_or_equiv_p (v))
550 : {
551 17841436 : cselib_hasher::key lookup = {
552 17841436 : GET_MODE (v->val_rtx), v->val_rtx, VOIDmode
553 17841436 : };
554 17841436 : cselib_val **slot
555 35682872 : = cselib_preserved_hash_table->find_slot_with_hash (&lookup,
556 17841436 : v->hash, INSERT);
557 17841436 : gcc_assert (!*slot);
558 17841436 : *slot = v;
559 17841436 : v->in_preserved_table_p = true;
560 17841436 : if (!v->all_locs_preserved_p)
561 0 : cselib_preserved_prune_list.safe_push (v);
562 : }
563 :
564 45447679 : cselib_hash_table->clear_slot (x);
565 :
566 45447679 : return 1;
567 : }
568 :
569 : /* Remove all entries from the hash table, arranging for the next
570 : value to be numbered NUM. */
571 :
572 : void
573 102112675 : cselib_reset_table (unsigned int num)
574 : {
575 102112675 : unsigned int i;
576 :
577 102112675 : max_value_regs = 0;
578 :
579 102112675 : if (cfa_base_preserved_val)
580 : {
581 4457827 : unsigned int regno = cfa_base_preserved_regno;
582 4457827 : unsigned int new_used_regs = 0;
583 31756963 : for (i = 0; i < n_used_regs; i++)
584 27299136 : if (used_regs[i] == regno)
585 : {
586 4457827 : new_used_regs = 1;
587 4457827 : continue;
588 : }
589 : else
590 22841309 : REG_VALUES (used_regs[i]) = 0;
591 4457827 : gcc_assert (new_used_regs == 1);
592 4457827 : n_used_regs = new_used_regs;
593 4457827 : used_regs[0] = regno;
594 4457827 : max_value_regs
595 4457827 : = hard_regno_nregs (regno,
596 4457827 : GET_MODE (cfa_base_preserved_val->locs->loc));
597 :
598 : /* If cfa_base is sp + const_int, need to preserve also the
599 : SP_DERIVED_VALUE_P value. */
600 4457827 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs;
601 8915654 : l; l = l->next)
602 8915654 : if (GET_CODE (l->loc) == PLUS
603 4457827 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
604 4457827 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
605 13373481 : && CONST_INT_P (XEXP (l->loc, 1)))
606 : {
607 4457827 : if (! invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (l->loc, 0))))
608 : {
609 0 : rtx val = cfa_base_preserved_val->val_rtx;
610 0 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
611 0 : cselib_current_insn = l->setting_insn;
612 0 : new_elt_loc_list (CSELIB_VAL_PTR (XEXP (l->loc, 0)),
613 0 : plus_constant (Pmode, val,
614 0 : -UINTVAL (XEXP (l->loc, 1))));
615 0 : cselib_current_insn = save_cselib_current_insn;
616 : }
617 : break;
618 : }
619 : }
620 : else
621 : {
622 375539784 : for (i = 0; i < n_used_regs; i++)
623 277884936 : REG_VALUES (used_regs[i]) = 0;
624 97654848 : n_used_regs = 0;
625 : }
626 :
627 102112675 : if (cselib_preserve_constants)
628 49905506 : cselib_hash_table->traverse <void *, preserve_constants_and_equivs> (NULL);
629 : else
630 : {
631 97654848 : cselib_hash_table->empty ();
632 97654848 : gcc_checking_assert (!cselib_any_perm_equivs);
633 : }
634 :
635 102112675 : n_useless_values = 0;
636 102112675 : n_useless_debug_values = 0;
637 102112675 : n_debug_values = 0;
638 :
639 102112675 : next_uid = num;
640 :
641 102112675 : first_containing_mem = &dummy_val;
642 102112675 : }
643 :
644 : /* Return the number of the next value that will be generated. */
645 :
646 : unsigned int
647 4966221 : cselib_get_next_uid (void)
648 : {
649 4966221 : return next_uid;
650 : }
651 :
652 : /* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE,
653 : INSERTing if requested. When X is part of the address of a MEM,
654 : MEMMODE should specify the mode of the MEM. */
655 :
656 : static cselib_val **
657 727961299 : cselib_find_slot (machine_mode mode, rtx x, hashval_t hash,
658 : enum insert_option insert, machine_mode memmode)
659 : {
660 727961299 : cselib_val **slot = NULL;
661 727961299 : cselib_hasher::key lookup = { mode, x, memmode };
662 727961299 : if (cselib_preserve_constants)
663 165297098 : slot = cselib_preserved_hash_table->find_slot_with_hash (&lookup, hash,
664 : NO_INSERT);
665 165297098 : if (!slot)
666 670686272 : slot = cselib_hash_table->find_slot_with_hash (&lookup, hash, insert);
667 727961299 : return slot;
668 : }
669 :
670 : /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
671 : only return true for values which point to a cselib_val whose value
672 : element has been set to zero, which implies the cselib_val will be
673 : removed. */
674 :
675 : bool
676 2097707 : references_value_p (const_rtx x)
677 : {
678 2097707 : subrtx_iterator::array_type array;
679 4959664 : FOR_EACH_SUBRTX (iter, array, x, ALL)
680 2861957 : if (GET_CODE (*iter) == VALUE)
681 0 : return true;
682 2097707 : return false;
683 2097707 : }
684 :
685 : /* Return true if V is a useless VALUE and can be discarded as such. */
686 :
687 : static bool
688 723213011 : cselib_useless_value_p (cselib_val *v)
689 : {
690 723213011 : return (v->locs == 0
691 80239198 : && !PRESERVED_VALUE_P (v->val_rtx)
692 769516886 : && !SP_DERIVED_VALUE_P (v->val_rtx));
693 : }
694 :
695 : /* For all locations found in V, delete locations that reference useless
696 : values (i.e. values without any location). */
697 :
698 : static void
699 67386733 : discard_useless_locs (cselib_val *v)
700 : {
701 67386733 : struct elt_loc_list **p = &v->locs;
702 67386733 : bool had_locs = v->locs != NULL;
703 67386733 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
704 :
705 67386733 : if (v->all_locs_preserved_p)
706 : return;
707 :
708 : bool all_locs_preserved_p = true;
709 105650996 : while (*p)
710 : {
711 : /* True if every value referenced by (*p)->loc is preserved. */
712 46635986 : bool preserved_p = true;
713 46635986 : bool keep_p = true;
714 46635986 : subrtx_iterator::array_type array;
715 156400206 : FOR_EACH_SUBRTX (iter, array, (*p)->loc, ALL)
716 : {
717 111043911 : const_rtx x = *iter;
718 111043911 : if (GET_CODE (x) == VALUE && !PRESERVED_VALUE_P (x))
719 : {
720 4665474 : preserved_p = false;
721 4665474 : if (CSELIB_VAL_PTR (x)->locs == 0)
722 : {
723 : keep_p = false;
724 : break;
725 : }
726 : }
727 : }
728 46635986 : if (keep_p)
729 : {
730 45356295 : all_locs_preserved_p &= preserved_p;
731 45356295 : p = &(*p)->next;
732 : }
733 : else
734 1279691 : unchain_one_elt_loc_list (p);
735 46635986 : }
736 :
737 59015010 : if (all_locs_preserved_p)
738 56080425 : v->all_locs_preserved_p = true;
739 :
740 59015010 : if (had_locs && cselib_useless_value_p (v))
741 : {
742 1145902 : if (setting_insn && DEBUG_INSN_P (setting_insn))
743 2 : n_useless_debug_values++;
744 : else
745 1145900 : n_useless_values++;
746 1145902 : values_became_useless = 1;
747 : }
748 : }
749 :
750 : /* A hash-table traversal callback for the above. */
751 :
752 : int
753 59550626 : discard_useless_locs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
754 : {
755 59550626 : discard_useless_locs (*x);
756 59550626 : return 1;
757 : }
758 :
759 : /* If X is a value with no locations, remove it from the hashtable. */
760 :
761 : int
762 49256697 : discard_useless_values (cselib_val **x, void *info ATTRIBUTE_UNUSED)
763 : {
764 49256697 : cselib_val *v = *x;
765 :
766 49256697 : if (v->locs == 0 && cselib_useless_value_p (v))
767 : {
768 2345275 : if (cselib_discard_hook)
769 515909 : cselib_discard_hook (v);
770 :
771 2345275 : CSELIB_VAL_PTR (v->val_rtx) = NULL;
772 2345275 : cselib_hash_table->clear_slot (x);
773 2345275 : unchain_one_value (v);
774 2345275 : n_useless_values--;
775 : }
776 :
777 49256697 : return 1;
778 : }
779 :
780 : /* Clean out useless values (i.e. those which no longer have locations
781 : associated with them) from the hash table. */
782 :
783 : static void
784 4485974 : remove_useless_values (void)
785 : {
786 4540142 : cselib_val **p, *v;
787 :
788 : /* First pass: eliminate locations that reference the value. That in
789 : turn can make more values useless. */
790 4540142 : do
791 : {
792 4540142 : values_became_useless = 0;
793 64090768 : cselib_hash_table->traverse <void *, discard_useless_locs> (NULL);
794 : }
795 4540142 : while (values_became_useless);
796 :
797 : /* Second pass: actually remove the values. */
798 :
799 4485974 : p = &first_containing_mem;
800 4609977 : for (v = *p; v != &dummy_val; v = v->next_containing_mem)
801 124003 : if (v->locs && v == canonical_cselib_val (v))
802 : {
803 120784 : *p = v;
804 120784 : p = &(*p)->next_containing_mem;
805 : }
806 4485974 : *p = &dummy_val;
807 :
808 4485974 : if (cselib_preserve_constants)
809 : {
810 : /* Apply discard_useless_locs to each element of
811 : cselib_preserved_prune_list. Remove from consideration any values
812 : whose locations only reference preserved values, since those
813 : locations will never be useless in their current form. */
814 4457827 : unsigned int len = cselib_preserved_prune_list.length ();
815 4457827 : unsigned int dest_i = 0;
816 4457827 : unsigned int src_i = 0;
817 12293934 : for (; src_i < len; ++src_i)
818 : {
819 7836107 : auto *val = cselib_preserved_prune_list[src_i];
820 7836107 : discard_useless_locs (val);
821 7836107 : if (!val->all_locs_preserved_p)
822 : {
823 0 : if (dest_i < src_i)
824 0 : cselib_preserved_prune_list[dest_i] = val;
825 0 : dest_i += 1;
826 : }
827 : }
828 4457827 : if (src_i != dest_i)
829 3717389 : cselib_preserved_prune_list.truncate (dest_i);
830 : }
831 4485974 : gcc_assert (!values_became_useless);
832 :
833 4485974 : n_useless_values += n_useless_debug_values;
834 4485974 : n_debug_values -= n_useless_debug_values;
835 4485974 : n_useless_debug_values = 0;
836 :
837 53742671 : cselib_hash_table->traverse <void *, discard_useless_values> (NULL);
838 :
839 4485974 : gcc_assert (!n_useless_values);
840 4485974 : }
841 :
842 : /* Arrange for a value to not be removed from the hash table even if
843 : it becomes useless. */
844 :
845 : void
846 46075419 : cselib_preserve_value (cselib_val *v)
847 : {
848 46075419 : PRESERVED_VALUE_P (v->val_rtx) = 1;
849 46075419 : }
850 :
851 : /* Test whether a value is preserved. */
852 :
853 : bool
854 269399005 : cselib_preserved_value_p (cselib_val *v)
855 : {
856 269399005 : return PRESERVED_VALUE_P (v->val_rtx);
857 : }
858 :
859 : /* Arrange for a REG value to be assumed constant through the whole function,
860 : never invalidated and preserved across cselib_reset_table calls. */
861 :
862 : void
863 1016252 : cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)
864 : {
865 1016252 : if (cselib_preserve_constants
866 1016252 : && v->locs
867 1016252 : && REG_P (v->locs->loc))
868 : {
869 508689 : cfa_base_preserved_val = v;
870 508689 : cfa_base_preserved_regno = regno;
871 : }
872 1016252 : }
873 :
874 : /* Clean all non-constant expressions in the hash table, but retain
875 : their values. */
876 :
877 : void
878 4457827 : cselib_preserve_only_values (void)
879 : {
880 4457827 : int i;
881 :
882 414577911 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
883 410120084 : cselib_invalidate_regno (i, reg_raw_mode[i]);
884 :
885 4457827 : cselib_invalidate_mem (callmem[0]);
886 :
887 4457827 : remove_useless_values ();
888 :
889 4457827 : gcc_assert (first_containing_mem == &dummy_val);
890 4457827 : }
891 :
892 : /* Arrange for a value to be marked as based on stack pointer
893 : for find_base_term purposes. */
894 :
895 : void
896 1938698 : cselib_set_value_sp_based (cselib_val *v)
897 : {
898 1938698 : SP_BASED_VALUE_P (v->val_rtx) = 1;
899 1938698 : }
900 :
901 : /* Test whether a value is based on stack pointer for
902 : find_base_term purposes. */
903 :
904 : bool
905 838835003 : cselib_sp_based_value_p (cselib_val *v)
906 : {
907 838835003 : return SP_BASED_VALUE_P (v->val_rtx);
908 : }
909 :
910 : /* Return the mode in which a register was last set. If X is not a
911 : register, return its mode. If the mode in which the register was
912 : set is not known, or the value was already clobbered, return
913 : VOIDmode. */
914 :
915 : machine_mode
916 114549580 : cselib_reg_set_mode (const_rtx x)
917 : {
918 114549580 : if (!REG_P (x))
919 34451520 : return GET_MODE (x);
920 :
921 80098060 : if (REG_VALUES (REGNO (x)) == NULL
922 80098060 : || REG_VALUES (REGNO (x))->elt == NULL)
923 : return VOIDmode;
924 :
925 24289770 : return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
926 : }
927 :
928 : /* If x is a PLUS or an autoinc operation, expand the operation,
929 : storing the offset, if any, in *OFF. */
930 :
931 : static rtx
932 1519643428 : autoinc_split (rtx x, rtx *off, machine_mode memmode)
933 : {
934 1519643428 : switch (GET_CODE (x))
935 : {
936 832327092 : case PLUS:
937 832327092 : *off = XEXP (x, 1);
938 832327092 : x = XEXP (x, 0);
939 832327092 : break;
940 :
941 12774837 : case PRE_DEC:
942 12774837 : if (memmode == VOIDmode)
943 : return x;
944 :
945 25549674 : *off = gen_int_mode (-GET_MODE_SIZE (memmode), GET_MODE (x));
946 12774837 : x = XEXP (x, 0);
947 12774837 : break;
948 :
949 0 : case PRE_INC:
950 0 : if (memmode == VOIDmode)
951 : return x;
952 :
953 0 : *off = gen_int_mode (GET_MODE_SIZE (memmode), GET_MODE (x));
954 0 : x = XEXP (x, 0);
955 0 : break;
956 :
957 1646405 : case PRE_MODIFY:
958 1646405 : x = XEXP (x, 1);
959 1646405 : break;
960 :
961 1851455 : case POST_DEC:
962 1851455 : case POST_INC:
963 1851455 : case POST_MODIFY:
964 1851455 : x = XEXP (x, 0);
965 1851455 : break;
966 :
967 : default:
968 : break;
969 : }
970 :
971 1519643428 : if (GET_MODE (x) == Pmode
972 1469809556 : && (REG_P (x) || MEM_P (x) || GET_CODE (x) == VALUE)
973 2355503195 : && (*off == NULL_RTX || CONST_INT_P (*off)))
974 : {
975 831113654 : cselib_val *e;
976 831113654 : if (GET_CODE (x) == VALUE)
977 534326275 : e = CSELIB_VAL_PTR (x);
978 : else
979 296787379 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
980 831113654 : if (e)
981 : {
982 821713091 : if (SP_DERIVED_VALUE_P (e->val_rtx)
983 821713091 : && (*off == NULL_RTX || *off == const0_rtx))
984 : {
985 75040 : *off = NULL_RTX;
986 75040 : return e->val_rtx;
987 : }
988 1796241386 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
989 1413393885 : if (GET_CODE (l->loc) == PLUS
990 606743950 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
991 605901230 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
992 1852188713 : && CONST_INT_P (XEXP (l->loc, 1)))
993 : {
994 438790550 : if (*off == NULL_RTX)
995 1496747 : *off = XEXP (l->loc, 1);
996 : else
997 437293803 : *off = plus_constant (Pmode, *off,
998 437293803 : INTVAL (XEXP (l->loc, 1)));
999 438790550 : if (*off == const0_rtx)
1000 272834188 : *off = NULL_RTX;
1001 438790550 : return XEXP (l->loc, 0);
1002 : }
1003 : }
1004 : }
1005 : return x;
1006 : }
1007 :
1008 : /* Return true if we can prove that X and Y contain the same value,
1009 : taking our gathered information into account. MEMMODE holds the
1010 : mode of the enclosing MEM, if any, as required to deal with autoinc
1011 : addressing modes. If X and Y are not (known to be) part of
1012 : addresses, MEMMODE should be VOIDmode. */
1013 :
1014 : bool
1015 1234611240 : rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth)
1016 : {
1017 1629711709 : enum rtx_code code;
1018 1629711709 : const char *fmt;
1019 1629711709 : int i;
1020 :
1021 1629711709 : if (REG_P (x) || MEM_P (x))
1022 : {
1023 151225151 : cselib_val *e = cselib_lookup (x, GET_MODE (x), 0, memmode);
1024 :
1025 151225151 : if (e)
1026 127742636 : x = e->val_rtx;
1027 : }
1028 :
1029 1629711709 : if (REG_P (y) || MEM_P (y))
1030 : {
1031 142803691 : cselib_val *e = cselib_lookup (y, GET_MODE (y), 0, memmode);
1032 :
1033 142803691 : if (e)
1034 130839834 : y = e->val_rtx;
1035 : }
1036 :
1037 1629711709 : if (x == y)
1038 : return true;
1039 :
1040 1298523543 : if (GET_CODE (x) == VALUE)
1041 : {
1042 445680689 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (x));
1043 445680689 : struct elt_loc_list *l;
1044 :
1045 445680689 : if (GET_CODE (y) == VALUE)
1046 31511064 : return e == canonical_cselib_val (CSELIB_VAL_PTR (y));
1047 :
1048 414169625 : if ((SP_DERIVED_VALUE_P (x)
1049 151863952 : || SP_DERIVED_VALUE_P (e->val_rtx))
1050 458454054 : && GET_MODE (y) == Pmode)
1051 : {
1052 264698792 : rtx yoff = NULL;
1053 264698792 : rtx yr = autoinc_split (y, &yoff, memmode);
1054 264698792 : if ((yr == x || yr == e->val_rtx) && yoff == NULL_RTX)
1055 53711 : return true;
1056 : }
1057 :
1058 414115914 : if (depth == 128)
1059 : return false;
1060 :
1061 1274116369 : for (l = e->locs; l; l = l->next)
1062 : {
1063 883339137 : rtx t = l->loc;
1064 :
1065 : /* Avoid infinite recursion. We know we have the canonical
1066 : value, so we can just skip any values in the equivalence
1067 : list. */
1068 883339137 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
1069 524197331 : continue;
1070 359141806 : else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1))
1071 : return true;
1072 : }
1073 :
1074 : return false;
1075 : }
1076 852842854 : else if (GET_CODE (y) == VALUE)
1077 : {
1078 46620672 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y));
1079 46620672 : struct elt_loc_list *l;
1080 :
1081 46620672 : if ((SP_DERIVED_VALUE_P (y)
1082 44312558 : || SP_DERIVED_VALUE_P (e->val_rtx))
1083 47037157 : && GET_MODE (x) == Pmode)
1084 : {
1085 2231134 : rtx xoff = NULL;
1086 2231134 : rtx xr = autoinc_split (x, &xoff, memmode);
1087 2231134 : if ((xr == y || xr == e->val_rtx) && xoff == NULL_RTX)
1088 173 : return true;
1089 : }
1090 :
1091 46620499 : if (depth == 128)
1092 : return false;
1093 :
1094 111874331 : for (l = e->locs; l; l = l->next)
1095 : {
1096 65336542 : rtx t = l->loc;
1097 :
1098 65336542 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
1099 56219532 : continue;
1100 9117010 : else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1))
1101 : return true;
1102 : }
1103 :
1104 : return false;
1105 : }
1106 :
1107 806222182 : if (GET_MODE (x) != GET_MODE (y))
1108 : return false;
1109 :
1110 767105105 : if (GET_CODE (x) != GET_CODE (y)
1111 767105105 : || (GET_CODE (x) == PLUS
1112 346086300 : && GET_MODE (x) == Pmode
1113 248262104 : && CONST_INT_P (XEXP (x, 1))
1114 237788403 : && CONST_INT_P (XEXP (y, 1))))
1115 : {
1116 617359129 : rtx xorig = x, yorig = y;
1117 617359129 : rtx xoff = NULL, yoff = NULL;
1118 :
1119 617359129 : x = autoinc_split (x, &xoff, memmode);
1120 617359129 : y = autoinc_split (y, &yoff, memmode);
1121 :
1122 : /* Don't recurse if nothing changed. */
1123 617359129 : if (x != xorig || y != yorig)
1124 : {
1125 576903663 : if (!xoff != !yoff)
1126 222906994 : return false;
1127 :
1128 494479803 : if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth))
1129 : return false;
1130 :
1131 394452135 : return rtx_equal_for_cselib_1 (x, y, memmode, depth);
1132 : }
1133 :
1134 40455466 : if (GET_CODE (xorig) != GET_CODE (yorig))
1135 : return false;
1136 : }
1137 :
1138 : /* These won't be handled correctly by the code below. */
1139 149745976 : switch (GET_CODE (x))
1140 : {
1141 : CASE_CONST_UNIQUE:
1142 : case DEBUG_EXPR:
1143 : return false;
1144 :
1145 : case CONST_VECTOR:
1146 : if (!same_vector_encodings_p (x, y))
1147 : return false;
1148 : break;
1149 :
1150 2373227 : case DEBUG_IMPLICIT_PTR:
1151 2373227 : return DEBUG_IMPLICIT_PTR_DECL (x)
1152 2373227 : == DEBUG_IMPLICIT_PTR_DECL (y);
1153 :
1154 4914 : case DEBUG_PARAMETER_REF:
1155 4914 : return DEBUG_PARAMETER_REF_DECL (x)
1156 4914 : == DEBUG_PARAMETER_REF_DECL (y);
1157 :
1158 306706 : case ENTRY_VALUE:
1159 : /* ENTRY_VALUEs are function invariant, it is thus undesirable to
1160 : use rtx_equal_for_cselib_1 to compare the operands. */
1161 306706 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1162 :
1163 174 : case LABEL_REF:
1164 174 : return label_ref_label (x) == label_ref_label (y);
1165 :
1166 190 : case REG:
1167 190 : return REGNO (x) == REGNO (y);
1168 :
1169 648334 : case MEM:
1170 : /* We have to compare any autoinc operations in the addresses
1171 : using this MEM's mode. */
1172 648334 : return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x),
1173 648334 : depth);
1174 :
1175 : default:
1176 : break;
1177 : }
1178 :
1179 39244337 : code = GET_CODE (x);
1180 39244337 : fmt = GET_RTX_FORMAT (code);
1181 :
1182 68292387 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1183 : {
1184 57100485 : int j;
1185 :
1186 57100485 : switch (fmt[i])
1187 : {
1188 0 : case 'w':
1189 0 : if (XWINT (x, i) != XWINT (y, i))
1190 : return false;
1191 : break;
1192 :
1193 597287 : case 'n':
1194 597287 : case 'i':
1195 597287 : if (XINT (x, i) != XINT (y, i))
1196 : return false;
1197 : break;
1198 :
1199 5566 : case 'L':
1200 5566 : if (XLOC (x, i) != XLOC (y, i))
1201 : return false;
1202 : break;
1203 :
1204 604025 : case 'p':
1205 604025 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1206 : return false;
1207 : break;
1208 :
1209 1535016 : case 'V':
1210 1535016 : case 'E':
1211 : /* Two vectors must have the same length. */
1212 1535016 : if (XVECLEN (x, i) != XVECLEN (y, i))
1213 : return false;
1214 :
1215 : /* And the corresponding elements must match. */
1216 3820529 : for (j = 0; j < XVECLEN (x, i); j++)
1217 3177868 : if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j),
1218 3177868 : XVECEXP (y, i, j), memmode, depth))
1219 : return false;
1220 : break;
1221 :
1222 43721174 : case 'e':
1223 43721174 : if (i == 1
1224 27836088 : && targetm.commutative_p (x, UNKNOWN)
1225 19835607 : && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode,
1226 : depth)
1227 44027209 : && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode,
1228 : depth))
1229 : return true;
1230 43510627 : if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode,
1231 : depth))
1232 : return false;
1233 : break;
1234 :
1235 5409229 : case 'S':
1236 5409229 : case 's':
1237 5409229 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1238 : return false;
1239 : break;
1240 :
1241 : case 'u':
1242 : /* These are just backpointers, so they don't matter. */
1243 : break;
1244 :
1245 : case '0':
1246 : case 't':
1247 : break;
1248 :
1249 : /* It is believed that rtx's at this level will never
1250 : contain anything but integers and other rtx's,
1251 : except for within LABEL_REFs and SYMBOL_REFs. */
1252 0 : default:
1253 0 : gcc_unreachable ();
1254 : }
1255 : }
1256 : return true;
1257 : }
1258 :
1259 : /* Wrapper for rtx_equal_for_cselib_p to determine whether a SET is
1260 : truly redundant, taking into account aliasing information. */
1261 : bool
1262 114549580 : cselib_redundant_set_p (rtx set)
1263 : {
1264 114549580 : gcc_assert (GET_CODE (set) == SET);
1265 114549580 : rtx dest = SET_DEST (set);
1266 114549580 : if (cselib_reg_set_mode (dest) != GET_MODE (dest))
1267 : return false;
1268 :
1269 54730310 : rtx src = SET_SRC (set);
1270 3979560 : if ((MEM_P (src) && MEM_VOLATILE_P (src))
1271 58634467 : || !rtx_equal_for_cselib_p (dest, src))
1272 54309421 : return false;
1273 :
1274 420893 : while (GET_CODE (dest) == SUBREG
1275 420889 : || GET_CODE (dest) == ZERO_EXTRACT
1276 841782 : || GET_CODE (dest) == STRICT_LOW_PART)
1277 4 : dest = XEXP (dest, 0);
1278 :
1279 420889 : if (!flag_strict_aliasing || !MEM_P (dest))
1280 : return true;
1281 :
1282 38342 : if (MEM_VOLATILE_P (dest))
1283 : return false;
1284 :
1285 : /* For a store we need to check that suppressing it will not change
1286 : the effective alias set. */
1287 38342 : rtx dest_addr = XEXP (dest, 0);
1288 :
1289 : /* Lookup the equivalents to the original dest (rather than just the
1290 : MEM). */
1291 76684 : cselib_val *src_val = cselib_lookup (SET_DEST (set),
1292 38342 : GET_MODE (SET_DEST (set)),
1293 : 0, VOIDmode);
1294 :
1295 38342 : if (src_val)
1296 : {
1297 : /* Walk the list of source equivalents to find the MEM accessing
1298 : the same location. */
1299 87174 : for (elt_loc_list *l = src_val->locs; l; l = l->next)
1300 : {
1301 87174 : rtx src_equiv = l->loc;
1302 87174 : while (GET_CODE (src_equiv) == SUBREG
1303 87174 : || GET_CODE (src_equiv) == ZERO_EXTRACT
1304 174354 : || GET_CODE (src_equiv) == STRICT_LOW_PART)
1305 6 : src_equiv = XEXP (src_equiv, 0);
1306 :
1307 87174 : if (MEM_P (src_equiv))
1308 : {
1309 : /* Match the MEMs by comparing the addresses. We can
1310 : only remove the later store if the earlier aliases at
1311 : least all the accesses of the later one. */
1312 46402 : if (rtx_equal_for_cselib_1 (dest_addr, XEXP (src_equiv, 0),
1313 46402 : GET_MODE (dest), 0))
1314 38336 : return mems_same_for_tbaa_p (src_equiv, dest);
1315 : }
1316 : }
1317 : }
1318 :
1319 : /* We failed to find a recorded value in the cselib history, so try
1320 : the source of this set; this catches cases such as *p = *q when p
1321 : and q have the same value. */
1322 6 : while (GET_CODE (src) == SUBREG)
1323 0 : src = XEXP (src, 0);
1324 :
1325 6 : if (MEM_P (src)
1326 6 : && rtx_equal_for_cselib_1 (dest_addr, XEXP (src, 0), GET_MODE (dest), 0))
1327 6 : return mems_same_for_tbaa_p (src, dest);
1328 :
1329 : return false;
1330 : }
1331 :
1332 : /* Helper function for cselib_hash_rtx. Arguments like for cselib_hash_rtx,
1333 : except that it hashes (plus:P x c). */
1334 :
1335 : static hashval_t
1336 288841300 : cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create,
1337 : machine_mode memmode)
1338 : {
1339 288841300 : cselib_val *e = cselib_lookup (x, GET_MODE (x), create, memmode);
1340 288841300 : if (! e)
1341 : return 0;
1342 :
1343 275330569 : if (! SP_DERIVED_VALUE_P (e->val_rtx))
1344 445195447 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
1345 359668778 : if (GET_CODE (l->loc) == PLUS
1346 131435885 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
1347 130916432 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
1348 484334071 : && CONST_INT_P (XEXP (l->loc, 1)))
1349 : {
1350 124654697 : e = CSELIB_VAL_PTR (XEXP (l->loc, 0));
1351 124654697 : c = trunc_int_for_mode (c + UINTVAL (XEXP (l->loc, 1)), Pmode);
1352 124654697 : break;
1353 : }
1354 275330569 : if (c == 0)
1355 8148499 : return e->hash;
1356 :
1357 267182070 : inchash::hash hash;
1358 267182070 : hash.add_int (PLUS);
1359 267182070 : hash.add_int (GET_MODE (x));
1360 267182070 : hash.merge_hash (e->hash);
1361 267182070 : hash.add_hwi (c);
1362 :
1363 267182070 : return hash.end () ? hash.end () : 1 + (unsigned int) PLUS;
1364 : }
1365 :
1366 : /* Hash an rtx. Return 0 if we couldn't hash the rtx.
1367 : For registers and memory locations, we look up their cselib_val structure
1368 : and return its VALUE element.
1369 : Possible reasons for return 0 are: the object is volatile, or we couldn't
1370 : find a register or memory location in the table and CREATE is zero. If
1371 : CREATE is nonzero, table elts are created for regs and mem.
1372 : N.B. this hash function returns the same hash value for RTXes that
1373 : differ only in the order of operands, thus it is suitable for comparisons
1374 : that take commutativity into account.
1375 : If we wanted to also support associative rules, we'd have to use a different
1376 : strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
1377 : MEMMODE indicates the mode of an enclosing MEM, and it's only
1378 : used to compute autoinc values.
1379 : We used to have a MODE argument for hashing for CONST_INTs, but that
1380 : didn't make sense, since it caused spurious hash differences between
1381 : (set (reg:SI 1) (const_int))
1382 : (plus:SI (reg:SI 2) (reg:SI 1))
1383 : and
1384 : (plus:SI (reg:SI 2) (const_int))
1385 : If the mode is important in any context, it must be checked specifically
1386 : in a comparison anyway, since relying on hash differences is unsafe. */
1387 :
1388 : static hashval_t
1389 1003523430 : cselib_hash_rtx (rtx x, int create, machine_mode memmode)
1390 : {
1391 1003523430 : cselib_val *e;
1392 1003523430 : poly_int64 offset;
1393 1003523430 : int i, j;
1394 1003523430 : enum rtx_code code;
1395 1003523430 : const char *fmt;
1396 1003523430 : inchash::hash hash;
1397 :
1398 1003523430 : code = GET_CODE (x);
1399 1003523430 : hash.add_int (code);
1400 1003523430 : hash.add_int (GET_MODE (x));
1401 :
1402 1003523430 : switch (code)
1403 : {
1404 427205 : case VALUE:
1405 427205 : e = CSELIB_VAL_PTR (x);
1406 427205 : return e->hash;
1407 :
1408 219138653 : case MEM:
1409 219138653 : case REG:
1410 219138653 : e = cselib_lookup (x, GET_MODE (x), create, memmode);
1411 219138653 : if (! e)
1412 : return 0;
1413 :
1414 194487140 : return e->hash;
1415 :
1416 14354692 : case DEBUG_EXPR:
1417 14354692 : hash.add_int (DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)));
1418 14354692 : return hash.end () ? hash.end() : (unsigned int) DEBUG_EXPR;
1419 :
1420 3036232 : case DEBUG_IMPLICIT_PTR:
1421 3036232 : hash.add_int (DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)));
1422 3036232 : return hash.end () ? hash.end () : (unsigned int) DEBUG_IMPLICIT_PTR;
1423 :
1424 40450 : case DEBUG_PARAMETER_REF:
1425 40450 : hash.add_int (DECL_UID (DEBUG_PARAMETER_REF_DECL (x)));
1426 40450 : return hash.end () ? hash.end () : (unsigned int) DEBUG_PARAMETER_REF;
1427 :
1428 1412323 : case ENTRY_VALUE:
1429 : /* ENTRY_VALUEs are function invariant, thus try to avoid
1430 : recursing on argument if ENTRY_VALUE is one of the
1431 : forms emitted by expand_debug_expr, otherwise
1432 : ENTRY_VALUE hash would depend on the current value
1433 : in some register or memory. */
1434 1412323 : if (REG_P (ENTRY_VALUE_EXP (x)))
1435 1394629 : hash.add_int ((unsigned int) REG
1436 1394629 : + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
1437 1394629 : + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)));
1438 17694 : else if (MEM_P (ENTRY_VALUE_EXP (x))
1439 17694 : && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0)))
1440 17694 : hash.add_int ((unsigned int) MEM
1441 17694 : + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
1442 17694 : + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0)));
1443 : else
1444 0 : hash.add_int (cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode));
1445 1412323 : return hash.end () ? hash.end () : (unsigned int) ENTRY_VALUE;
1446 :
1447 174265803 : case CONST_INT:
1448 174265803 : hash.add_hwi (UINTVAL (x));
1449 174265803 : return hash.end () ? hash.end () : (unsigned int) CONST_INT;
1450 :
1451 : case CONST_WIDE_INT:
1452 2969541 : for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
1453 1981543 : hash.add_hwi (CONST_WIDE_INT_ELT (x, i));
1454 987998 : return hash.end () ? hash.end () : (unsigned int) CONST_WIDE_INT;
1455 :
1456 : case CONST_POLY_INT:
1457 : {
1458 0 : for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i)
1459 0 : hash.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]);
1460 0 : return hash.end () ? hash.end () : (unsigned int) CONST_POLY_INT;
1461 : }
1462 :
1463 3526364 : case CONST_DOUBLE:
1464 : /* This is like the general case, except that it only counts
1465 : the integers representing the constant. */
1466 3526364 : if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
1467 : {
1468 : hash.add_hwi (CONST_DOUBLE_LOW (x));
1469 : hash.add_hwi (CONST_DOUBLE_HIGH (x));
1470 : }
1471 : else
1472 3526364 : hash.merge_hash (real_hash (CONST_DOUBLE_REAL_VALUE (x)));
1473 3526364 : return hash.end () ? hash.end () : (unsigned int) CONST_DOUBLE;
1474 :
1475 0 : case CONST_FIXED:
1476 0 : hash.merge_hash (fixed_hash (CONST_FIXED_VALUE (x)));
1477 0 : return hash.end () ? hash.end () : (unsigned int) CONST_FIXED;
1478 :
1479 3211225 : case CONST_VECTOR:
1480 3211225 : {
1481 3211225 : int units;
1482 3211225 : rtx elt;
1483 :
1484 3211225 : units = const_vector_encoded_nelts (x);
1485 :
1486 8316263 : for (i = 0; i < units; ++i)
1487 : {
1488 5105038 : elt = CONST_VECTOR_ENCODED_ELT (x, i);
1489 5105038 : hash.merge_hash (cselib_hash_rtx (elt, 0, memmode));
1490 : }
1491 :
1492 3211225 : return hash.end () ? hash.end () : (unsigned int) CONST_VECTOR;
1493 : }
1494 :
1495 : /* Assume there is only one rtx object for any given label. */
1496 138278 : case LABEL_REF:
1497 : /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1498 : differences and differences between each stage's debugging dumps. */
1499 138278 : hash.add_int (CODE_LABEL_NUMBER (label_ref_label (x)));
1500 138278 : return hash.end () ? hash.end () : (unsigned int) LABEL_REF;
1501 :
1502 66154079 : case SYMBOL_REF:
1503 66154079 : {
1504 : /* Don't hash on the symbol's address to avoid bootstrap differences.
1505 : Different hash values may cause expressions to be recorded in
1506 : different orders and thus different registers to be used in the
1507 : final assembler. This also avoids differences in the dump files
1508 : between various stages. */
1509 66154079 : const char *p = (const char *) XSTR (x, 0);
1510 :
1511 66154079 : if (*p)
1512 66154079 : hash.add (p, strlen (p));
1513 :
1514 66154079 : return hash.end () ? hash.end () : (unsigned int) SYMBOL_REF;
1515 : }
1516 :
1517 17623031 : case PRE_DEC:
1518 17623031 : case PRE_INC:
1519 17623031 : {
1520 : /* We can't compute these without knowing the MEM mode. */
1521 17623031 : gcc_assert (memmode != VOIDmode);
1522 35246062 : offset = GET_MODE_SIZE (memmode);
1523 17623031 : if (code == PRE_DEC)
1524 17623031 : offset = -offset;
1525 : /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1526 : like (mem:MEMMODE (plus (reg) (const_int I))). */
1527 17623031 : if (GET_MODE (x) == Pmode
1528 17623031 : && (REG_P (XEXP (x, 0))
1529 : || MEM_P (XEXP (x, 0))
1530 : || GET_CODE (XEXP (x, 0)) == VALUE))
1531 : {
1532 17623031 : HOST_WIDE_INT c;
1533 17623031 : if (offset.is_constant (&c))
1534 17623031 : return cselib_hash_plus_const_int (XEXP (x, 0),
1535 : trunc_int_for_mode (c, Pmode),
1536 : create, memmode);
1537 : }
1538 :
1539 0 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1540 0 : if (tem_hash == 0)
1541 : return 0;
1542 0 : hash.merge_hash (tem_hash);
1543 0 : tem_hash = cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)),
1544 : create, memmode);
1545 0 : if (tem_hash == 0)
1546 : return 0;
1547 0 : hash.merge_hash (tem_hash);
1548 0 : return hash.end () ? hash.end () : 1 + (unsigned) PLUS;
1549 : }
1550 :
1551 509399 : case PRE_MODIFY:
1552 509399 : {
1553 509399 : gcc_assert (memmode != VOIDmode);
1554 509399 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1555 509399 : if (tem_hash == 0)
1556 : return 0;
1557 502809 : hash.merge_hash (tem_hash);
1558 502809 : return hash.end () ? hash.end () : 1 + (unsigned) PRE_MODIFY;
1559 : }
1560 :
1561 1813769 : case POST_DEC:
1562 1813769 : case POST_INC:
1563 1813769 : case POST_MODIFY:
1564 1813769 : {
1565 1813769 : gcc_assert (memmode != VOIDmode);
1566 1813769 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1567 1813769 : if (tem_hash == 0)
1568 : return 0;
1569 1813769 : hash.merge_hash (tem_hash);
1570 1813769 : return hash.end () ? hash.end () : 1 + (unsigned) code;
1571 : }
1572 :
1573 : case PC:
1574 : case CALL:
1575 : case UNSPEC_VOLATILE:
1576 : return 0;
1577 :
1578 485544 : case ASM_OPERANDS:
1579 485544 : if (MEM_VOLATILE_P (x))
1580 : return 0;
1581 :
1582 : break;
1583 :
1584 324403823 : case PLUS:
1585 324403823 : if (GET_MODE (x) == Pmode
1586 313635645 : && (REG_P (XEXP (x, 0))
1587 : || MEM_P (XEXP (x, 0))
1588 : || GET_CODE (XEXP (x, 0)) == VALUE)
1589 613745811 : && CONST_INT_P (XEXP (x, 1)))
1590 271218269 : return cselib_hash_plus_const_int (XEXP (x, 0), INTVAL (XEXP (x, 1)),
1591 271218269 : create, memmode);
1592 : break;
1593 :
1594 : default:
1595 : break;
1596 : }
1597 :
1598 210259964 : i = GET_RTX_LENGTH (code) - 1;
1599 210259964 : fmt = GET_RTX_FORMAT (code);
1600 :
1601 210259964 : if (COMMUTATIVE_P (x))
1602 : {
1603 78378728 : gcc_assert (i == 1 && fmt[0] == 'e' && fmt[1] == 'e');
1604 78378728 : hashval_t tem1_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1605 78378728 : if (tem1_hash == 0)
1606 : return 0;
1607 72854857 : hashval_t tem0_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1608 72854857 : if (tem0_hash == 0)
1609 : return 0;
1610 69287856 : hash.add_commutative (tem0_hash, tem1_hash);
1611 69287856 : return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
1612 : }
1613 :
1614 347787900 : for (; i >= 0; i--)
1615 : {
1616 234308982 : switch (fmt[i])
1617 : {
1618 212969936 : case 'e':
1619 212969936 : {
1620 212969936 : rtx tem = XEXP (x, i);
1621 212969936 : hashval_t tem_hash = cselib_hash_rtx (tem, create, memmode);
1622 212969936 : if (tem_hash == 0)
1623 : return 0;
1624 195505069 : hash.merge_hash (tem_hash);
1625 : }
1626 195505069 : break;
1627 : case 'E':
1628 26985102 : for (j = 0; j < XVECLEN (x, i); j++)
1629 : {
1630 18936792 : hashval_t tem_hash
1631 18936792 : = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode);
1632 18936792 : if (tem_hash == 0)
1633 : return 0;
1634 17999341 : hash.merge_hash (tem_hash);
1635 : }
1636 : break;
1637 :
1638 554005 : case 's':
1639 554005 : {
1640 554005 : const char *p = (const char *) XSTR (x, i);
1641 :
1642 554005 : if (p && *p)
1643 521529 : hash.add (p, strlen (p));
1644 : break;
1645 : }
1646 :
1647 5415619 : case 'i':
1648 5415619 : hash.add_hwi (XINT (x, i));
1649 5415619 : break;
1650 :
1651 244795 : case 'L':
1652 244795 : hash.add_hwi (XLOC (x, i));
1653 244795 : break;
1654 :
1655 6138866 : case 'p':
1656 6138866 : hash.add_int (constant_lower_bound (SUBREG_BYTE (x)));
1657 6138866 : break;
1658 :
1659 : case '0':
1660 : case 't':
1661 : /* unused */
1662 : break;
1663 :
1664 0 : default:
1665 0 : gcc_unreachable ();
1666 : }
1667 : }
1668 :
1669 113478918 : return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
1670 : }
1671 :
1672 : /* Create a new value structure for VALUE and initialize it. The mode of the
1673 : value is MODE. */
1674 :
1675 : static inline cselib_val *
1676 425270974 : new_cselib_val (hashval_t hash, machine_mode mode, rtx x)
1677 : {
1678 425270974 : cselib_val *e = cselib_val_pool.allocate ();
1679 :
1680 425270974 : gcc_assert (hash);
1681 425270974 : gcc_assert (next_uid);
1682 :
1683 425270974 : e->hash = hash;
1684 425270974 : e->in_preserved_table_p = false;
1685 425270974 : e->all_locs_preserved_p = false;
1686 : /* We use an alloc pool to allocate this RTL construct because it
1687 : accounts for about 8% of the overall memory usage. We know
1688 : precisely when we can have VALUE RTXen (when cselib is active)
1689 : so we don't need to put them in garbage collected memory.
1690 : ??? Why should a VALUE be an RTX in the first place? */
1691 425270974 : e->val_rtx = (rtx_def*) value_pool.allocate ();
1692 425270974 : memset (e->val_rtx, 0, RTX_HDR_SIZE);
1693 425270974 : PUT_CODE (e->val_rtx, VALUE);
1694 425270974 : PUT_MODE (e->val_rtx, mode);
1695 425270974 : CSELIB_VAL_PTR (e->val_rtx) = e;
1696 425270974 : CSELIB_VAL_UID (e->val_rtx) = next_uid++;
1697 425270974 : e->addr_list = 0;
1698 425270974 : e->locs = 0;
1699 425270974 : e->next_containing_mem = 0;
1700 :
1701 425270974 : scalar_int_mode int_mode;
1702 554569571 : if (REG_P (x) && is_int_mode (mode, &int_mode)
1703 129298597 : && GET_MODE_SIZE (int_mode) > 1
1704 123007769 : && REG_VALUES (REGNO (x)) != NULL
1705 432193215 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
1706 : {
1707 6768660 : rtx copy = shallow_copy_rtx (x);
1708 6768660 : scalar_int_mode narrow_mode_iter;
1709 24380361 : FOR_EACH_MODE_UNTIL (narrow_mode_iter, int_mode)
1710 : {
1711 17611701 : PUT_MODE_RAW (copy, narrow_mode_iter);
1712 17611701 : cselib_val *v = cselib_lookup (copy, narrow_mode_iter, 0, VOIDmode);
1713 17611701 : if (v)
1714 : {
1715 749373 : rtx sub = lowpart_subreg (narrow_mode_iter, e->val_rtx, int_mode);
1716 749373 : if (sub)
1717 749373 : new_elt_loc_list (v, sub);
1718 : }
1719 : }
1720 : }
1721 :
1722 425270974 : if (dump_file && (dump_flags & TDF_CSELIB))
1723 : {
1724 0 : fprintf (dump_file, "cselib value %u:%u ",
1725 0 : CSELIB_VAL_UID (e->val_rtx), hash);
1726 0 : if (flag_dump_noaddr || flag_dump_unnumbered)
1727 0 : fputs ("# ", dump_file);
1728 : else
1729 0 : fprintf (dump_file, "%p ", (void*)e);
1730 0 : print_rtl_single (dump_file, x);
1731 0 : fputc ('\n', dump_file);
1732 : }
1733 :
1734 425270974 : return e;
1735 : }
1736 :
1737 : /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
1738 : contains the data at this address. X is a MEM that represents the
1739 : value. Update the two value structures to represent this situation. */
1740 :
1741 : static void
1742 53384564 : add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
1743 : {
1744 53384564 : addr_elt = canonical_cselib_val (addr_elt);
1745 53384564 : mem_elt = canonical_cselib_val (mem_elt);
1746 :
1747 : /* Avoid duplicates. */
1748 53384564 : addr_space_t as = MEM_ADDR_SPACE (x);
1749 96280715 : for (elt_loc_list *l = mem_elt->locs; l; l = l->next)
1750 42896151 : if (MEM_P (l->loc)
1751 13089150 : && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt
1752 42896151 : && MEM_ADDR_SPACE (l->loc) == as)
1753 : {
1754 0 : promote_debug_loc (l);
1755 0 : return;
1756 : }
1757 :
1758 53384564 : addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
1759 53384564 : new_elt_loc_list (mem_elt,
1760 : replace_equiv_address_nv (x, addr_elt->val_rtx));
1761 53384564 : if (mem_elt->next_containing_mem == NULL)
1762 : {
1763 46748976 : mem_elt->next_containing_mem = first_containing_mem;
1764 46748976 : first_containing_mem = mem_elt;
1765 : }
1766 : }
1767 :
1768 : /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
1769 : If CREATE, make a new one if we haven't seen it before. */
1770 :
1771 : static cselib_val *
1772 242189543 : cselib_lookup_mem (rtx x, int create)
1773 : {
1774 242189543 : machine_mode mode = GET_MODE (x);
1775 242189543 : machine_mode addr_mode;
1776 242189543 : cselib_val **slot;
1777 242189543 : cselib_val *addr;
1778 242189543 : cselib_val *mem_elt;
1779 :
1780 480619497 : if (MEM_VOLATILE_P (x) || mode == BLKmode
1781 238223708 : || !cselib_record_memory
1782 434018007 : || (FLOAT_MODE_P (mode) && flag_float_store))
1783 : return 0;
1784 :
1785 191815872 : addr_mode = GET_MODE (XEXP (x, 0));
1786 191815872 : if (addr_mode == VOIDmode)
1787 1001508 : addr_mode = Pmode;
1788 :
1789 : /* Look up the value for the address. */
1790 191815872 : addr = cselib_lookup (XEXP (x, 0), addr_mode, create, mode);
1791 191815872 : if (! addr)
1792 : return 0;
1793 118406112 : addr = canonical_cselib_val (addr);
1794 :
1795 : /* Find a value that describes a value of our mode at that address. */
1796 118406112 : addr_space_t as = MEM_ADDR_SPACE (x);
1797 120847735 : for (elt_list *l = addr->addr_list; l; l = l->next)
1798 74949500 : if (GET_MODE (l->elt->val_rtx) == mode)
1799 : {
1800 79120079 : for (elt_loc_list *l2 = l->elt->locs; l2; l2 = l2->next)
1801 83159278 : if (MEM_P (l2->loc) && MEM_ADDR_SPACE (l2->loc) == as)
1802 : {
1803 72507877 : promote_debug_loc (l->elt->locs);
1804 72507877 : return l->elt;
1805 : }
1806 : }
1807 :
1808 45898235 : if (! create)
1809 : return 0;
1810 :
1811 28743869 : mem_elt = new_cselib_val (next_uid, mode, x);
1812 28743869 : add_mem_for_addr (addr, mem_elt, x);
1813 28743869 : slot = cselib_find_slot (mode, x, mem_elt->hash, INSERT, VOIDmode);
1814 28743869 : *slot = mem_elt;
1815 28743869 : return mem_elt;
1816 : }
1817 :
1818 : /* Search through the possible substitutions in P. We prefer a non reg
1819 : substitution because this allows us to expand the tree further. If
1820 : we find, just a reg, take the lowest regno. There may be several
1821 : non-reg results, we just take the first one because they will all
1822 : expand to the same place. */
1823 :
1824 : static rtx
1825 24363151 : expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
1826 : int max_depth)
1827 : {
1828 24363151 : rtx reg_result = NULL;
1829 24363151 : unsigned int regno = UINT_MAX;
1830 24363151 : struct elt_loc_list *p_in = p;
1831 :
1832 52891715 : for (; p; p = p->next)
1833 : {
1834 : /* Return these right away to avoid returning stack pointer based
1835 : expressions for frame pointer and vice versa, which is something
1836 : that would confuse DSE. See the comment in cselib_expand_value_rtx_1
1837 : for more details. */
1838 32379024 : if (REG_P (p->loc)
1839 32379024 : && (REGNO (p->loc) == STACK_POINTER_REGNUM
1840 : || REGNO (p->loc) == FRAME_POINTER_REGNUM
1841 : || REGNO (p->loc) == HARD_FRAME_POINTER_REGNUM
1842 25872604 : || REGNO (p->loc) == cfa_base_preserved_regno))
1843 : return p->loc;
1844 : /* Avoid infinite recursion trying to expand a reg into a
1845 : the same reg. */
1846 31869419 : if ((REG_P (p->loc))
1847 25867023 : && (REGNO (p->loc) < regno)
1848 57430561 : && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
1849 : {
1850 4437403 : reg_result = p->loc;
1851 4437403 : regno = REGNO (p->loc);
1852 : }
1853 : /* Avoid infinite recursion and do not try to expand the
1854 : value. */
1855 27432016 : else if (GET_CODE (p->loc) == VALUE
1856 343279 : && CSELIB_VAL_PTR (p->loc)->locs == p_in)
1857 0 : continue;
1858 27432016 : else if (!REG_P (p->loc))
1859 : {
1860 6002396 : rtx result, note;
1861 6002396 : if (dump_file && (dump_flags & TDF_CSELIB))
1862 : {
1863 0 : print_inline_rtx (dump_file, p->loc, 0);
1864 0 : fprintf (dump_file, "\n");
1865 : }
1866 6002396 : if (GET_CODE (p->loc) == LO_SUM
1867 0 : && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
1868 0 : && p->setting_insn
1869 0 : && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
1870 6002396 : && XEXP (note, 0) == XEXP (p->loc, 1))
1871 : return XEXP (p->loc, 1);
1872 6002396 : result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1873 6002396 : if (result)
1874 : return result;
1875 : }
1876 :
1877 : }
1878 :
1879 20512691 : if (regno != UINT_MAX)
1880 : {
1881 3662869 : rtx result;
1882 3662869 : if (dump_file && (dump_flags & TDF_CSELIB))
1883 0 : fprintf (dump_file, "r%d\n", regno);
1884 :
1885 3662869 : result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1886 3662869 : if (result)
1887 : return result;
1888 : }
1889 :
1890 17701350 : if (dump_file && (dump_flags & TDF_CSELIB))
1891 : {
1892 0 : if (reg_result)
1893 : {
1894 0 : print_inline_rtx (dump_file, reg_result, 0);
1895 0 : fprintf (dump_file, "\n");
1896 : }
1897 : else
1898 0 : fprintf (dump_file, "NULL\n");
1899 : }
1900 : return reg_result;
1901 : }
1902 :
1903 :
1904 : /* Forward substitute and expand an expression out to its roots.
1905 : This is the opposite of common subexpression. Because local value
1906 : numbering is such a weak optimization, the expanded expression is
1907 : pretty much unique (not from a pointer equals point of view but
1908 : from a tree shape point of view.
1909 :
1910 : This function returns NULL if the expansion fails. The expansion
1911 : will fail if there is no value number for one of the operands or if
1912 : one of the operands has been overwritten between the current insn
1913 : and the beginning of the basic block. For instance x has no
1914 : expansion in:
1915 :
1916 : r1 <- r1 + 3
1917 : x <- r1 + 8
1918 :
1919 : REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1920 : It is clear on return. */
1921 :
1922 : rtx
1923 37673185 : cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1924 : {
1925 37673185 : struct expand_value_data evd;
1926 :
1927 37673185 : evd.regs_active = regs_active;
1928 37673185 : evd.callback = NULL;
1929 37673185 : evd.callback_arg = NULL;
1930 37673185 : evd.dummy = false;
1931 :
1932 37673185 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1933 : }
1934 :
1935 : /* Same as cselib_expand_value_rtx, but using a callback to try to
1936 : resolve some expressions. The CB function should return ORIG if it
1937 : can't or does not want to deal with a certain RTX. Any other
1938 : return value, including NULL, will be used as the expansion for
1939 : VALUE, without any further changes. */
1940 :
1941 : rtx
1942 94208591 : cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1943 : cselib_expand_callback cb, void *data)
1944 : {
1945 94208591 : struct expand_value_data evd;
1946 :
1947 94208591 : evd.regs_active = regs_active;
1948 94208591 : evd.callback = cb;
1949 94208591 : evd.callback_arg = data;
1950 94208591 : evd.dummy = false;
1951 :
1952 94208591 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1953 : }
1954 :
1955 : /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1956 : or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1957 : would return NULL or non-NULL, without allocating new rtx. */
1958 :
1959 : bool
1960 0 : cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1961 : cselib_expand_callback cb, void *data)
1962 : {
1963 0 : struct expand_value_data evd;
1964 :
1965 0 : evd.regs_active = regs_active;
1966 0 : evd.callback = cb;
1967 0 : evd.callback_arg = data;
1968 0 : evd.dummy = true;
1969 :
1970 0 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL;
1971 : }
1972 :
1973 : /* Internal implementation of cselib_expand_value_rtx and
1974 : cselib_expand_value_rtx_cb. */
1975 :
1976 : static rtx
1977 214194682 : cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1978 : int max_depth)
1979 : {
1980 214194682 : rtx copy, scopy;
1981 214194682 : int i, j;
1982 214194682 : RTX_CODE code;
1983 214194682 : const char *format_ptr;
1984 214194682 : machine_mode mode;
1985 :
1986 214194682 : code = GET_CODE (orig);
1987 :
1988 : /* For the context of dse, if we end up expand into a huge tree, we
1989 : will not have a useful address, so we might as well just give up
1990 : quickly. */
1991 214194682 : if (max_depth <= 0)
1992 : return NULL;
1993 :
1994 211568511 : switch (code)
1995 : {
1996 51661239 : case REG:
1997 51661239 : {
1998 51661239 : struct elt_list *l = REG_VALUES (REGNO (orig));
1999 :
2000 51661239 : if (l && l->elt == NULL)
2001 25693234 : l = l->next;
2002 51676368 : for (; l; l = l->next)
2003 38635832 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
2004 : {
2005 38620703 : rtx result;
2006 38620703 : unsigned regno = REGNO (orig);
2007 :
2008 : /* The only thing that we are not willing to do (this
2009 : is requirement of dse and if others potential uses
2010 : need this function we should add a parm to control
2011 : it) is that we will not substitute the
2012 : STACK_POINTER_REGNUM, FRAME_POINTER or the
2013 : HARD_FRAME_POINTER.
2014 :
2015 : These expansions confuses the code that notices that
2016 : stores into the frame go dead at the end of the
2017 : function and that the frame is not effected by calls
2018 : to subroutines. If you allow the
2019 : STACK_POINTER_REGNUM substitution, then dse will
2020 : think that parameter pushing also goes dead which is
2021 : wrong. If you allow the FRAME_POINTER or the
2022 : HARD_FRAME_POINTER then you lose the opportunity to
2023 : make the frame assumptions. */
2024 38620703 : if (regno == STACK_POINTER_REGNUM
2025 38620703 : || regno == FRAME_POINTER_REGNUM
2026 20780993 : || regno == HARD_FRAME_POINTER_REGNUM
2027 20263128 : || regno == cfa_base_preserved_regno)
2028 : return orig;
2029 :
2030 19953800 : bitmap_set_bit (evd->regs_active, regno);
2031 :
2032 19953800 : if (dump_file && (dump_flags & TDF_CSELIB))
2033 0 : fprintf (dump_file, "expanding: r%d into: ", regno);
2034 :
2035 19953800 : result = expand_loc (l->elt->locs, evd, max_depth);
2036 19953800 : bitmap_clear_bit (evd->regs_active, regno);
2037 :
2038 19953800 : if (result)
2039 : return result;
2040 : else
2041 : return orig;
2042 : }
2043 : return orig;
2044 : }
2045 :
2046 : CASE_CONST_ANY:
2047 : case SYMBOL_REF:
2048 : case CODE_LABEL:
2049 : case PC:
2050 : case SCRATCH:
2051 : /* SCRATCH must be shared because they represent distinct values. */
2052 : return orig;
2053 0 : case CLOBBER:
2054 0 : if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
2055 : return orig;
2056 : break;
2057 :
2058 273739 : case CONST:
2059 273739 : if (shared_const_p (orig))
2060 : return orig;
2061 : break;
2062 :
2063 958119 : case SUBREG:
2064 958119 : {
2065 958119 : rtx subreg;
2066 :
2067 958119 : if (evd->callback)
2068 : {
2069 867344 : subreg = evd->callback (orig, evd->regs_active, max_depth,
2070 : evd->callback_arg);
2071 867344 : if (subreg != orig)
2072 : return subreg;
2073 : }
2074 :
2075 90775 : subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
2076 : max_depth - 1);
2077 90775 : if (!subreg)
2078 : return NULL;
2079 97824 : scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
2080 48912 : GET_MODE (SUBREG_REG (orig)),
2081 48912 : SUBREG_BYTE (orig));
2082 48912 : if (scopy == NULL
2083 48510 : || (GET_CODE (scopy) == SUBREG
2084 45814 : && !REG_P (SUBREG_REG (scopy))
2085 6109 : && !MEM_P (SUBREG_REG (scopy))))
2086 : return NULL;
2087 :
2088 : return scopy;
2089 : }
2090 :
2091 75163783 : case VALUE:
2092 75163783 : {
2093 75163783 : rtx result;
2094 :
2095 75163783 : if (dump_file && (dump_flags & TDF_CSELIB))
2096 : {
2097 0 : fputs ("\nexpanding ", dump_file);
2098 0 : print_rtl_single (dump_file, orig);
2099 0 : fputs (" into...", dump_file);
2100 : }
2101 :
2102 75163783 : if (evd->callback)
2103 : {
2104 70754432 : result = evd->callback (orig, evd->regs_active, max_depth,
2105 : evd->callback_arg);
2106 :
2107 70754432 : if (result != orig)
2108 : return result;
2109 : }
2110 :
2111 4409351 : result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
2112 4409351 : return result;
2113 : }
2114 :
2115 6542372 : case DEBUG_EXPR:
2116 6542372 : if (evd->callback)
2117 6542372 : return evd->callback (orig, evd->regs_active, max_depth,
2118 6542372 : evd->callback_arg);
2119 : return orig;
2120 :
2121 : default:
2122 : break;
2123 : }
2124 :
2125 : /* Copy the various flags, fields, and other information. We assume
2126 : that all fields need copying, and then clear the fields that should
2127 : not be copied. That is the sensible default behavior, and forces
2128 : us to explicitly document why we are *not* copying a flag. */
2129 45868901 : if (evd->dummy)
2130 : copy = NULL;
2131 : else
2132 45868901 : copy = shallow_copy_rtx (orig);
2133 :
2134 45868901 : format_ptr = GET_RTX_FORMAT (code);
2135 :
2136 120652190 : for (i = 0; i < GET_RTX_LENGTH (code); i++)
2137 79037641 : switch (*format_ptr++)
2138 : {
2139 72068760 : case 'e':
2140 72068760 : if (XEXP (orig, i) != NULL)
2141 : {
2142 72068760 : rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
2143 : max_depth - 1);
2144 72068760 : if (!result)
2145 : return NULL;
2146 67848595 : if (copy)
2147 67848595 : XEXP (copy, i) = result;
2148 : }
2149 : break;
2150 :
2151 301512 : case 'E':
2152 301512 : case 'V':
2153 301512 : if (XVEC (orig, i) != NULL)
2154 : {
2155 301512 : if (copy)
2156 301512 : XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
2157 755431 : for (j = 0; j < XVECLEN (orig, i); j++)
2158 : {
2159 488106 : rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
2160 : evd, max_depth - 1);
2161 488106 : if (!result)
2162 : return NULL;
2163 453919 : if (copy)
2164 453919 : XVECEXP (copy, i, j) = result;
2165 : }
2166 : }
2167 : break;
2168 :
2169 : case 't':
2170 : case 'w':
2171 : case 'i':
2172 : case 'L':
2173 : case 's':
2174 : case 'S':
2175 : case 'T':
2176 : case 'u':
2177 : case 'B':
2178 : case '0':
2179 : /* These are left unchanged. */
2180 : break;
2181 :
2182 0 : default:
2183 0 : gcc_unreachable ();
2184 : }
2185 :
2186 41614549 : if (evd->dummy)
2187 : return orig;
2188 :
2189 41614549 : mode = GET_MODE (copy);
2190 : /* If an operand has been simplified into CONST_INT, which doesn't
2191 : have a mode and the mode isn't derivable from whole rtx's mode,
2192 : try simplify_*_operation first with mode from original's operand
2193 : and as a fallback wrap CONST_INT into gen_rtx_CONST. */
2194 41614549 : scopy = copy;
2195 41614549 : switch (GET_RTX_CLASS (code))
2196 : {
2197 634878 : case RTX_UNARY:
2198 634878 : if (CONST_INT_P (XEXP (copy, 0))
2199 50841 : && GET_MODE (XEXP (orig, 0)) != VOIDmode)
2200 : {
2201 50833 : scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
2202 : GET_MODE (XEXP (orig, 0)));
2203 50833 : if (scopy)
2204 : return scopy;
2205 : }
2206 : break;
2207 : case RTX_COMM_ARITH:
2208 : case RTX_BIN_ARITH:
2209 : /* These expressions can derive operand modes from the whole rtx's mode. */
2210 : break;
2211 101413 : case RTX_TERNARY:
2212 101413 : case RTX_BITFIELD_OPS:
2213 101413 : if (CONST_INT_P (XEXP (copy, 0))
2214 77 : && GET_MODE (XEXP (orig, 0)) != VOIDmode)
2215 : {
2216 1 : scopy = simplify_ternary_operation (code, mode,
2217 : GET_MODE (XEXP (orig, 0)),
2218 : XEXP (copy, 0), XEXP (copy, 1),
2219 : XEXP (copy, 2));
2220 1 : if (scopy)
2221 : return scopy;
2222 : }
2223 : break;
2224 221174 : case RTX_COMPARE:
2225 221174 : case RTX_COMM_COMPARE:
2226 221174 : if (CONST_INT_P (XEXP (copy, 0))
2227 477 : && GET_MODE (XEXP (copy, 1)) == VOIDmode
2228 176 : && (GET_MODE (XEXP (orig, 0)) != VOIDmode
2229 6 : || GET_MODE (XEXP (orig, 1)) != VOIDmode))
2230 : {
2231 176 : scopy = simplify_relational_operation (code, mode,
2232 : (GET_MODE (XEXP (orig, 0))
2233 : != VOIDmode)
2234 : ? GET_MODE (XEXP (orig, 0))
2235 6 : : GET_MODE (XEXP (orig, 1)),
2236 : XEXP (copy, 0),
2237 : XEXP (copy, 1));
2238 176 : if (scopy)
2239 : return scopy;
2240 : }
2241 : break;
2242 : default:
2243 : break;
2244 : }
2245 41563540 : scopy = simplify_rtx (copy);
2246 41563540 : if (scopy)
2247 4812991 : return scopy;
2248 : return copy;
2249 : }
2250 :
2251 : /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2252 : with VALUE expressions. This way, it becomes independent of changes
2253 : to registers and memory.
2254 : X isn't actually modified; if modifications are needed, new rtl is
2255 : allocated. However, the return value can share rtl with X.
2256 : If X is within a MEM, MEMMODE must be the mode of the MEM. */
2257 :
2258 : rtx
2259 598156327 : cselib_subst_to_values (rtx x, machine_mode memmode)
2260 : {
2261 605906881 : enum rtx_code code = GET_CODE (x);
2262 605906881 : const char *fmt = GET_RTX_FORMAT (code);
2263 605906881 : cselib_val *e;
2264 605906881 : struct elt_list *l;
2265 605906881 : rtx copy = x;
2266 605906881 : int i;
2267 605906881 : poly_int64 offset;
2268 :
2269 605906881 : switch (code)
2270 : {
2271 237064762 : case REG:
2272 237064762 : l = REG_VALUES (REGNO (x));
2273 237064762 : if (l && l->elt == NULL)
2274 136098473 : l = l->next;
2275 239443196 : for (; l; l = l->next)
2276 239443196 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
2277 : return l->elt->val_rtx;
2278 :
2279 0 : gcc_unreachable ();
2280 :
2281 6266176 : case MEM:
2282 6266176 : e = cselib_lookup_mem (x, 0);
2283 : /* This used to happen for autoincrements, but we deal with them
2284 : properly now. Remove the if stmt for the next release. */
2285 6266176 : if (! e)
2286 : {
2287 : /* Assign a value that doesn't match any other. */
2288 0 : e = new_cselib_val (next_uid, GET_MODE (x), x);
2289 : }
2290 6266176 : return e->val_rtx;
2291 :
2292 688059 : case ENTRY_VALUE:
2293 688059 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
2294 688059 : if (! e)
2295 : break;
2296 912 : return e->val_rtx;
2297 :
2298 : CASE_CONST_ANY:
2299 : return x;
2300 :
2301 6419683 : case PRE_DEC:
2302 6419683 : case PRE_INC:
2303 6419683 : gcc_assert (memmode != VOIDmode);
2304 12839366 : offset = GET_MODE_SIZE (memmode);
2305 6419683 : if (code == PRE_DEC)
2306 6419683 : offset = -offset;
2307 6419683 : return cselib_subst_to_values (plus_constant (GET_MODE (x),
2308 : XEXP (x, 0), offset),
2309 6419683 : memmode);
2310 :
2311 382291 : case PRE_MODIFY:
2312 382291 : gcc_assert (memmode != VOIDmode);
2313 382291 : return cselib_subst_to_values (XEXP (x, 1), memmode);
2314 :
2315 948580 : case POST_DEC:
2316 948580 : case POST_INC:
2317 948580 : case POST_MODIFY:
2318 948580 : gcc_assert (memmode != VOIDmode);
2319 948580 : return cselib_subst_to_values (XEXP (x, 0), memmode);
2320 :
2321 116941400 : case PLUS:
2322 152382780 : if (GET_MODE (x) == Pmode && CONST_INT_P (XEXP (x, 1)))
2323 : {
2324 95558435 : rtx t = cselib_subst_to_values (XEXP (x, 0), memmode);
2325 95558435 : if (GET_CODE (t) == VALUE)
2326 : {
2327 89843140 : if (SP_DERIVED_VALUE_P (t) && XEXP (x, 1) == const0_rtx)
2328 : return t;
2329 89843140 : for (struct elt_loc_list *l = CSELIB_VAL_PTR (t)->locs;
2330 189337835 : l; l = l->next)
2331 121101476 : if (GET_CODE (l->loc) == PLUS
2332 24988325 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2333 24847251 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2334 142711770 : && CONST_INT_P (XEXP (l->loc, 1)))
2335 35475684 : return plus_constant (Pmode, l->loc, INTVAL (XEXP (x, 1)));
2336 : }
2337 73951654 : if (t != XEXP (x, 0))
2338 : {
2339 69587517 : copy = shallow_copy_rtx (x);
2340 69587517 : XEXP (copy, 0) = t;
2341 : }
2342 73951654 : return copy;
2343 : }
2344 :
2345 : default:
2346 : break;
2347 : }
2348 :
2349 484094121 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2350 : {
2351 316155061 : if (fmt[i] == 'e')
2352 : {
2353 232220919 : rtx t = cselib_subst_to_values (XEXP (x, i), memmode);
2354 :
2355 232220919 : if (t != XEXP (x, i))
2356 : {
2357 170046838 : if (x == copy)
2358 120589620 : copy = shallow_copy_rtx (x);
2359 170046838 : XEXP (copy, i) = t;
2360 : }
2361 : }
2362 83934142 : else if (fmt[i] == 'E')
2363 : {
2364 : int j;
2365 :
2366 19377709 : for (j = 0; j < XVECLEN (x, i); j++)
2367 : {
2368 13678864 : rtx t = cselib_subst_to_values (XVECEXP (x, i, j), memmode);
2369 :
2370 13678864 : if (t != XVECEXP (x, i, j))
2371 : {
2372 2620616 : if (XVEC (x, i) == XVEC (copy, i))
2373 : {
2374 1967792 : if (x == copy)
2375 1967792 : copy = shallow_copy_rtx (x);
2376 1967792 : XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
2377 : }
2378 2620616 : XVECEXP (copy, i, j) = t;
2379 : }
2380 : }
2381 : }
2382 : }
2383 :
2384 : return copy;
2385 : }
2386 :
2387 : /* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */
2388 :
2389 : rtx
2390 1463 : cselib_subst_to_values_from_insn (rtx x, machine_mode memmode, rtx_insn *insn)
2391 : {
2392 1463 : rtx ret;
2393 1463 : gcc_assert (!cselib_current_insn);
2394 1463 : cselib_current_insn = insn;
2395 1463 : ret = cselib_subst_to_values (x, memmode);
2396 1463 : cselib_current_insn = NULL;
2397 1463 : return ret;
2398 : }
2399 :
2400 : /* Look up the rtl expression X in our tables and return the value it
2401 : has. If CREATE is zero, we return NULL if we don't know the value.
2402 : Otherwise, we create a new one if possible, using mode MODE if X
2403 : doesn't have a mode (i.e. because it's a constant). When X is part
2404 : of an address, MEMMODE should be the mode of the enclosing MEM if
2405 : we're tracking autoinc expressions. */
2406 :
2407 : static cselib_val *
2408 2453610879 : cselib_lookup_1 (rtx x, machine_mode mode,
2409 : int create, machine_mode memmode)
2410 : {
2411 2453610879 : cselib_val **slot;
2412 2453610879 : cselib_val *e;
2413 :
2414 2453610879 : if (GET_MODE (x) != VOIDmode)
2415 2368668509 : mode = GET_MODE (x);
2416 :
2417 2453610879 : if (GET_CODE (x) == VALUE)
2418 65680906 : return CSELIB_VAL_PTR (x);
2419 :
2420 2387929973 : if (REG_P (x))
2421 : {
2422 1539051695 : struct elt_list *l;
2423 1539051695 : unsigned int i = REGNO (x);
2424 :
2425 1539051695 : l = REG_VALUES (i);
2426 1539051695 : if (l && l->elt == NULL)
2427 644209180 : l = l->next;
2428 1559910124 : for (; l; l = l->next)
2429 1189279430 : if (mode == GET_MODE (l->elt->val_rtx))
2430 : {
2431 1168421001 : promote_debug_loc (l->elt->locs);
2432 1168421001 : return l->elt;
2433 : }
2434 :
2435 370630694 : if (! create)
2436 : return 0;
2437 :
2438 139830459 : if (i < FIRST_PSEUDO_REGISTER)
2439 : {
2440 79441802 : unsigned int n = hard_regno_nregs (i, mode);
2441 :
2442 79441802 : if (n > max_value_regs)
2443 27477363 : max_value_regs = n;
2444 : }
2445 :
2446 139830459 : e = new_cselib_val (next_uid, GET_MODE (x), x);
2447 164357869 : if (GET_MODE (x) == Pmode && x == stack_pointer_rtx)
2448 12269314 : SP_DERIVED_VALUE_P (e->val_rtx) = 1;
2449 139830459 : new_elt_loc_list (e, x);
2450 :
2451 139830459 : scalar_int_mode int_mode;
2452 139830459 : if (REG_VALUES (i) == 0)
2453 : {
2454 : /* Maintain the invariant that the first entry of
2455 : REG_VALUES, if present, must be the value used to set the
2456 : register, or NULL. */
2457 129734307 : used_regs[n_used_regs++] = i;
2458 129734307 : REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
2459 : }
2460 10096152 : else if (cselib_preserve_constants
2461 10096152 : && is_int_mode (mode, &int_mode))
2462 : {
2463 : /* During var-tracking, try harder to find equivalences
2464 : for SUBREGs. If a setter sets say a DImode register
2465 : and user uses that register only in SImode, add a lowpart
2466 : subreg location. */
2467 1575897 : struct elt_list *lwider = NULL;
2468 1575897 : scalar_int_mode lmode;
2469 1575897 : l = REG_VALUES (i);
2470 1575897 : if (l && l->elt == NULL)
2471 1017940 : l = l->next;
2472 2369712 : for (; l; l = l->next)
2473 793815 : if (is_int_mode (GET_MODE (l->elt->val_rtx), &lmode)
2474 1118370 : && GET_MODE_SIZE (lmode) > GET_MODE_SIZE (int_mode)
2475 271164 : && (lwider == NULL
2476 1641 : || partial_subreg_p (lmode,
2477 1641 : GET_MODE (lwider->elt->val_rtx))))
2478 : {
2479 271082 : struct elt_loc_list *el;
2480 287337 : if (i < FIRST_PSEUDO_REGISTER
2481 271082 : && hard_regno_nregs (i, lmode) != 1)
2482 16255 : continue;
2483 500857 : for (el = l->elt->locs; el; el = el->next)
2484 469403 : if (!REG_P (el->loc))
2485 : break;
2486 254827 : if (el)
2487 793815 : lwider = l;
2488 : }
2489 1575897 : if (lwider)
2490 : {
2491 443630 : rtx sub = lowpart_subreg (int_mode, lwider->elt->val_rtx,
2492 221815 : GET_MODE (lwider->elt->val_rtx));
2493 221815 : if (sub)
2494 221815 : new_elt_loc_list (e, sub);
2495 : }
2496 : }
2497 139830459 : REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
2498 139830459 : slot = cselib_find_slot (mode, x, e->hash, INSERT, memmode);
2499 139830459 : *slot = e;
2500 139830459 : return e;
2501 : }
2502 :
2503 848878278 : if (MEM_P (x))
2504 235923367 : return cselib_lookup_mem (x, create);
2505 :
2506 612954911 : hashval_t hashval = cselib_hash_rtx (x, create, memmode);
2507 : /* Can't even create if hashing is not possible. */
2508 612954911 : if (! hashval)
2509 : return 0;
2510 :
2511 786200391 : slot = cselib_find_slot (mode, x, hashval,
2512 : create ? INSERT : NO_INSERT, memmode);
2513 559386971 : if (slot == 0)
2514 : return 0;
2515 :
2516 446344295 : e = (cselib_val *) *slot;
2517 446344295 : if (e)
2518 : return e;
2519 :
2520 256696646 : e = new_cselib_val (hashval, mode, x);
2521 :
2522 : /* We have to fill the slot before calling cselib_subst_to_values:
2523 : the hash table is inconsistent until we do so, and
2524 : cselib_subst_to_values will need to do lookups. */
2525 256696646 : *slot = e;
2526 256696646 : rtx v = cselib_subst_to_values (x, memmode);
2527 :
2528 : /* If cselib_preserve_constants, we might get a SP_DERIVED_VALUE_P
2529 : VALUE that isn't in the hash tables anymore. */
2530 256696646 : if (GET_CODE (v) == VALUE && SP_DERIVED_VALUE_P (v) && PRESERVED_VALUE_P (v))
2531 0 : PRESERVED_VALUE_P (e->val_rtx) = 1;
2532 :
2533 256696646 : new_elt_loc_list (e, v);
2534 256696646 : return e;
2535 : }
2536 :
2537 : /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2538 :
2539 : cselib_val *
2540 6368027 : cselib_lookup_from_insn (rtx x, machine_mode mode,
2541 : int create, machine_mode memmode, rtx_insn *insn)
2542 : {
2543 6368027 : cselib_val *ret;
2544 :
2545 6368027 : gcc_assert (!cselib_current_insn);
2546 6368027 : cselib_current_insn = insn;
2547 :
2548 6368027 : ret = cselib_lookup (x, mode, create, memmode);
2549 :
2550 6368027 : cselib_current_insn = NULL;
2551 :
2552 6368027 : return ret;
2553 : }
2554 :
2555 : /* Wrapper for cselib_lookup_1, that logs the lookup result and
2556 : maintains invariants related with debug insns. */
2557 :
2558 : cselib_val *
2559 2452553175 : cselib_lookup (rtx x, machine_mode mode,
2560 : int create, machine_mode memmode)
2561 : {
2562 2452553175 : cselib_val *ret = cselib_lookup_1 (x, mode, create, memmode);
2563 :
2564 : /* ??? Should we return NULL if we're not to create an entry, the
2565 : found loc is a debug loc and cselib_current_insn is not DEBUG?
2566 : If so, we should also avoid converting val to non-DEBUG; probably
2567 : easiest setting cselib_current_insn to NULL before the call
2568 : above. */
2569 :
2570 2452553175 : if (dump_file && (dump_flags & TDF_CSELIB))
2571 : {
2572 0 : fputs ("cselib lookup ", dump_file);
2573 0 : print_inline_rtx (dump_file, x, 2);
2574 0 : fprintf (dump_file, " => %u:%u\n",
2575 0 : ret ? CSELIB_VAL_UID (ret->val_rtx) : 0,
2576 : ret ? ret->hash : 0);
2577 : }
2578 :
2579 2452553175 : return ret;
2580 : }
2581 :
2582 : /* Invalidate the value at *L, which is part of REG_VALUES (REGNO). */
2583 :
2584 : static void
2585 188037643 : cselib_invalidate_regno_val (unsigned int regno, struct elt_list **l)
2586 : {
2587 188037643 : cselib_val *v = (*l)->elt;
2588 188037643 : if (*l == REG_VALUES (regno))
2589 : {
2590 : /* Maintain the invariant that the first entry of
2591 : REG_VALUES, if present, must be the value used to set
2592 : the register, or NULL. This is also nice because
2593 : then we won't push the same regno onto user_regs
2594 : multiple times. */
2595 144812669 : (*l)->elt = NULL;
2596 144812669 : l = &(*l)->next;
2597 : }
2598 : else
2599 43224974 : unchain_one_elt_list (l);
2600 :
2601 188037643 : v = canonical_cselib_val (v);
2602 :
2603 188037643 : bool had_locs = v->locs != NULL;
2604 188037643 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2605 :
2606 : /* Now, we clear the mapping from value to reg. It must exist, so
2607 : this code will crash intentionally if it doesn't. */
2608 188037643 : for (elt_loc_list **p = &v->locs; ; p = &(*p)->next)
2609 : {
2610 216420671 : rtx x = (*p)->loc;
2611 :
2612 216420671 : if (REG_P (x) && REGNO (x) == regno)
2613 : {
2614 188037643 : unchain_one_elt_loc_list (p);
2615 188037643 : break;
2616 : }
2617 28383028 : }
2618 :
2619 188037643 : if (had_locs && cselib_useless_value_p (v))
2620 : {
2621 21644498 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2622 0 : n_useless_debug_values++;
2623 : else
2624 21644498 : n_useless_values++;
2625 : }
2626 188037643 : }
2627 :
2628 : /* Invalidate any entries in reg_values that overlap REGNO. This is called
2629 : if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2630 : is used to determine how many hard registers are being changed. If MODE
2631 : is VOIDmode, then only REGNO is being changed; this is used when
2632 : invalidating call clobbered registers across a call. */
2633 :
2634 : static void
2635 813530110 : cselib_invalidate_regno (unsigned int regno, machine_mode mode)
2636 : {
2637 813530110 : unsigned int endregno;
2638 813530110 : unsigned int i;
2639 :
2640 : /* If we see pseudos after reload, something is _wrong_. */
2641 813530110 : gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
2642 : || reg_renumber[regno] < 0);
2643 :
2644 : /* Determine the range of registers that must be invalidated. For
2645 : pseudos, only REGNO is affected. For hard regs, we must take MODE
2646 : into account, and we must also invalidate lower register numbers
2647 : if they contain values that overlap REGNO. */
2648 225173211 : if (regno < FIRST_PSEUDO_REGISTER)
2649 : {
2650 707845242 : gcc_assert (mode != VOIDmode);
2651 :
2652 707845242 : if (regno < max_value_regs)
2653 : i = 0;
2654 : else
2655 665749910 : i = regno - max_value_regs;
2656 :
2657 707845242 : endregno = end_hard_regno (mode, regno);
2658 : }
2659 : else
2660 : {
2661 105684868 : i = regno;
2662 105684868 : endregno = regno + 1;
2663 : }
2664 :
2665 2254594385 : for (; i < endregno; i++)
2666 : {
2667 1441064275 : struct elt_list **l = ®_VALUES (i);
2668 :
2669 : /* Go through all known values for this reg; if it overlaps the range
2670 : we're invalidating, remove the value. */
2671 1832547060 : while (*l)
2672 : {
2673 391482785 : cselib_val *v = (*l)->elt;
2674 391482785 : unsigned int this_last = i;
2675 :
2676 391482785 : if (i < FIRST_PSEUDO_REGISTER && v != NULL)
2677 170138426 : this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
2678 :
2679 391482785 : if (this_last < regno || v == NULL
2680 119917229 : || (v == cfa_base_preserved_val
2681 4459478 : && i == cfa_base_preserved_regno))
2682 : {
2683 276023383 : l = &(*l)->next;
2684 276023383 : continue;
2685 : }
2686 :
2687 : /* We have an overlap. */
2688 115459402 : cselib_invalidate_regno_val (i, l);
2689 : }
2690 : }
2691 813530110 : }
2692 :
2693 : /* Invalidate any locations in the table which are changed because of a
2694 : store to MEM_RTX. If this is called because of a non-const call
2695 : instruction, MEM_RTX is (mem:BLK const0_rtx). */
2696 :
2697 : static void
2698 115934590 : cselib_invalidate_mem (rtx mem_rtx)
2699 : {
2700 115934590 : cselib_val **vp, *v, *next;
2701 115934590 : int num_mems = 0;
2702 115934590 : rtx mem_addr;
2703 :
2704 115934590 : mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
2705 115934590 : mem_rtx = canon_rtx (mem_rtx);
2706 :
2707 115934590 : vp = &first_containing_mem;
2708 288153338 : for (v = *vp; v != &dummy_val; v = next)
2709 : {
2710 172218748 : bool has_mem = false;
2711 172218748 : struct elt_loc_list **p = &v->locs;
2712 172218748 : bool had_locs = v->locs != NULL;
2713 172218748 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2714 172218748 : rtx sp_base = NULL_RTX;
2715 172218748 : HOST_WIDE_INT sp_off = 0;
2716 :
2717 513336249 : while (*p)
2718 : {
2719 341117501 : rtx x = (*p)->loc;
2720 341117501 : cselib_val *addr;
2721 341117501 : struct elt_list **mem_chain;
2722 :
2723 : /* MEMs may occur in locations only at the top level; below
2724 : that every MEM or REG is substituted by its VALUE. */
2725 341117501 : if (!MEM_P (x))
2726 : {
2727 103495265 : p = &(*p)->next;
2728 103495265 : continue;
2729 : }
2730 :
2731 : /* When invalidating memory below the stack pointer for const/pure
2732 : calls and alloca/VLAs aren't used, attempt to optimize. Values
2733 : stored into area sometimes below the stack pointer shouldn't be
2734 : addressable and should be stored just through stack pointer
2735 : derived expressions, so don't invalidate MEMs not using stack
2736 : derived addresses, or if the MEMs clearly aren't below the stack
2737 : pointer. This isn't a fully conservative approach, the hope is
2738 : that invalidating more MEMs than this isn't actually needed. */
2739 237622236 : if (mem_rtx == callmem[1]
2740 2968866 : && num_mems < param_max_cselib_memory_locations
2741 2968808 : && GET_CODE (XEXP (x, 0)) == VALUE
2742 2968808 : && !cfun->calls_alloca)
2743 : {
2744 2919133 : cselib_val *v2 = CSELIB_VAL_PTR (XEXP (x, 0));
2745 2919133 : rtx x_base = NULL_RTX;
2746 2919133 : HOST_WIDE_INT x_off = 0;
2747 2919133 : if (SP_DERIVED_VALUE_P (v2->val_rtx))
2748 : x_base = v2->val_rtx;
2749 : else
2750 4655366 : for (struct elt_loc_list *l = v2->locs; l; l = l->next)
2751 2892307 : if (GET_CODE (l->loc) == PLUS
2752 1555194 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2753 1449348 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2754 3972005 : && CONST_INT_P (XEXP (l->loc, 1)))
2755 : {
2756 1079674 : x_base = XEXP (l->loc, 0);
2757 1079674 : x_off = INTVAL (XEXP (l->loc, 1));
2758 1079674 : break;
2759 : }
2760 : /* If x_base is NULL here, don't invalidate x as its address
2761 : isn't derived from sp such that it could be in outgoing
2762 : argument area of some call in !ACCUMULATE_OUTGOING_ARGS
2763 : function. */
2764 2919133 : if (x_base)
2765 : {
2766 1156074 : if (sp_base == NULL_RTX)
2767 : {
2768 2115408 : if (cselib_val *v3
2769 1060850 : = cselib_lookup_1 (stack_pointer_rtx, Pmode, 0,
2770 : VOIDmode))
2771 : {
2772 1053234 : if (SP_DERIVED_VALUE_P (v3->val_rtx))
2773 : sp_base = v3->val_rtx;
2774 : else
2775 290564 : for (struct elt_loc_list *l = v3->locs;
2776 582842 : l; l = l->next)
2777 582828 : if (GET_CODE (l->loc) == PLUS
2778 290550 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2779 290550 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2780 873378 : && CONST_INT_P (XEXP (l->loc, 1)))
2781 : {
2782 290550 : sp_base = XEXP (l->loc, 0);
2783 290550 : sp_off = INTVAL (XEXP (l->loc, 1));
2784 290550 : break;
2785 : }
2786 : }
2787 1057704 : if (sp_base == NULL_RTX)
2788 4484 : sp_base = pc_rtx;
2789 : }
2790 : /* Otherwise, if x_base and sp_base are the same,
2791 : we know that x_base + x_off is the x's address and
2792 : sp_base + sp_off is current value of stack pointer,
2793 : so try to determine if x is certainly not below stack
2794 : pointer. */
2795 1156074 : if (sp_base == x_base)
2796 : {
2797 1148959 : if (STACK_GROWS_DOWNWARD)
2798 : {
2799 1148959 : HOST_WIDE_INT off = sp_off;
2800 : #ifdef STACK_ADDRESS_OFFSET
2801 : /* On SPARC take stack pointer bias into account as
2802 : well. */
2803 : off += (STACK_ADDRESS_OFFSET
2804 : - FIRST_PARM_OFFSET (current_function_decl));
2805 : #endif
2806 1148959 : if (x_off >= off)
2807 : /* x is at or above the current stack pointer,
2808 : no need to invalidate it. */
2809 : x_base = NULL_RTX;
2810 : }
2811 : else
2812 : {
2813 : HOST_WIDE_INT sz;
2814 : enum machine_mode mode = GET_MODE (x);
2815 : if ((MEM_SIZE_KNOWN_P (x)
2816 : && MEM_SIZE (x).is_constant (&sz))
2817 : || (mode != BLKmode
2818 : && GET_MODE_SIZE (mode).is_constant (&sz)))
2819 : if (x_off < sp_off
2820 : && ((HOST_WIDE_INT) ((unsigned HOST_WIDE_INT)
2821 : x_off + sz) <= sp_off))
2822 : /* x's end is below or at the current stack
2823 : pointer in !STACK_GROWS_DOWNWARD target,
2824 : no need to invalidate it. */
2825 : x_base = NULL_RTX;
2826 : }
2827 : }
2828 : }
2829 2911296 : if (x_base == NULL_RTX)
2830 : {
2831 2911296 : has_mem = true;
2832 2911296 : num_mems++;
2833 2911296 : p = &(*p)->next;
2834 2911296 : continue;
2835 : }
2836 : }
2837 :
2838 431626129 : if (num_mems < param_max_cselib_memory_locations
2839 469356543 : && ! canon_anti_dependence (x, false, mem_rtx,
2840 234645603 : GET_MODE (mem_rtx), mem_addr))
2841 : {
2842 196915189 : has_mem = true;
2843 196915189 : num_mems++;
2844 196915189 : p = &(*p)->next;
2845 196915189 : continue;
2846 : }
2847 :
2848 : /* This one overlaps. */
2849 : /* We must have a mapping from this MEM's address to the
2850 : value (E). Remove that, too. */
2851 37795751 : addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0, GET_MODE (x));
2852 37795751 : addr = canonical_cselib_val (addr);
2853 37795751 : gcc_checking_assert (v == canonical_cselib_val (v));
2854 37795751 : mem_chain = &addr->addr_list;
2855 37800761 : for (;;)
2856 : {
2857 37798256 : cselib_val *canon = canonical_cselib_val ((*mem_chain)->elt);
2858 :
2859 37798256 : if (canon == v)
2860 : {
2861 37795751 : unchain_one_elt_list (mem_chain);
2862 37795751 : break;
2863 : }
2864 :
2865 : /* Record canonicalized elt. */
2866 2505 : (*mem_chain)->elt = canon;
2867 :
2868 2505 : mem_chain = &(*mem_chain)->next;
2869 2505 : }
2870 :
2871 37795751 : unchain_one_elt_loc_list (p);
2872 : }
2873 :
2874 172218748 : if (had_locs && cselib_useless_value_p (v))
2875 : {
2876 8847479 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2877 0 : n_useless_debug_values++;
2878 : else
2879 8847479 : n_useless_values++;
2880 : }
2881 :
2882 172218748 : next = v->next_containing_mem;
2883 172218748 : if (has_mem)
2884 : {
2885 139358687 : *vp = v;
2886 139358687 : vp = &(*vp)->next_containing_mem;
2887 : }
2888 : else
2889 32860061 : v->next_containing_mem = NULL;
2890 : }
2891 115934590 : *vp = &dummy_val;
2892 115934590 : }
2893 :
2894 : /* Invalidate DEST. */
2895 :
2896 : void
2897 529300450 : cselib_invalidate_rtx (rtx dest)
2898 : {
2899 529300450 : while (GET_CODE (dest) == SUBREG
2900 529300450 : || GET_CODE (dest) == ZERO_EXTRACT
2901 1058606599 : || GET_CODE (dest) == STRICT_LOW_PART)
2902 5699 : dest = XEXP (dest, 0);
2903 :
2904 529300450 : if (REG_P (dest))
2905 403410026 : cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
2906 125890424 : else if (MEM_P (dest))
2907 76664606 : cselib_invalidate_mem (dest);
2908 529300450 : }
2909 :
2910 : /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2911 :
2912 : static void
2913 515121215 : cselib_invalidate_rtx_note_stores (rtx dest, const_rtx,
2914 : void *data ATTRIBUTE_UNUSED)
2915 : {
2916 515121215 : cselib_invalidate_rtx (dest);
2917 515121215 : }
2918 :
2919 : /* Record the result of a SET instruction. DEST is being set; the source
2920 : contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
2921 : describes its address. */
2922 :
2923 : static void
2924 369927552 : cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
2925 : {
2926 369927552 : if (src_elt == 0 || side_effects_p (dest))
2927 67168502 : return;
2928 :
2929 302759050 : if (REG_P (dest))
2930 : {
2931 278118355 : unsigned int dreg = REGNO (dest);
2932 278118355 : if (dreg < FIRST_PSEUDO_REGISTER)
2933 : {
2934 204367604 : unsigned int n = REG_NREGS (dest);
2935 :
2936 204367604 : if (n > max_value_regs)
2937 26119381 : max_value_regs = n;
2938 : }
2939 :
2940 278118355 : if (REG_VALUES (dreg) == 0)
2941 : {
2942 170991938 : used_regs[n_used_regs++] = dreg;
2943 170991938 : REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
2944 : }
2945 : else
2946 : {
2947 : /* The register should have been invalidated. */
2948 107126417 : gcc_assert (REG_VALUES (dreg)->elt == 0);
2949 107126417 : REG_VALUES (dreg)->elt = src_elt;
2950 : }
2951 :
2952 278118355 : if (cselib_useless_value_p (src_elt))
2953 42545 : n_useless_values--;
2954 278118355 : new_elt_loc_list (src_elt, dest);
2955 : }
2956 24640695 : else if (MEM_P (dest) && dest_addr_elt != 0
2957 24640695 : && cselib_record_memory)
2958 : {
2959 24640695 : if (cselib_useless_value_p (src_elt))
2960 30 : n_useless_values--;
2961 24640695 : add_mem_for_addr (dest_addr_elt, src_elt, dest);
2962 : }
2963 : }
2964 :
2965 : /* Make ELT and X's VALUE equivalent to each other at INSN. */
2966 :
2967 : void
2968 3913926 : cselib_add_permanent_equiv (cselib_val *elt, rtx x, rtx_insn *insn)
2969 : {
2970 3913926 : cselib_val *nelt;
2971 3913926 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
2972 :
2973 3913926 : gcc_checking_assert (elt);
2974 3913926 : gcc_checking_assert (PRESERVED_VALUE_P (elt->val_rtx));
2975 3913926 : gcc_checking_assert (!side_effects_p (x));
2976 :
2977 3913926 : cselib_current_insn = insn;
2978 :
2979 3913926 : nelt = cselib_lookup (x, GET_MODE (elt->val_rtx), 1, VOIDmode);
2980 :
2981 3913926 : if (nelt != elt)
2982 : {
2983 3042376 : cselib_any_perm_equivs = true;
2984 :
2985 3042376 : if (!PRESERVED_VALUE_P (nelt->val_rtx))
2986 3036891 : cselib_preserve_value (nelt);
2987 :
2988 3042376 : new_elt_loc_list (nelt, elt->val_rtx);
2989 : }
2990 :
2991 3913926 : cselib_current_insn = save_cselib_current_insn;
2992 3913926 : }
2993 :
2994 : /* Return TRUE if any permanent equivalences have been recorded since
2995 : the table was last initialized. */
2996 : bool
2997 1393405828 : cselib_have_permanent_equivalences (void)
2998 : {
2999 1393405828 : return cselib_any_perm_equivs;
3000 : }
3001 :
3002 : /* Record stack_pointer_rtx to be equal to
3003 : (plus:P cfa_base_preserved_val offset). Used by var-tracking
3004 : at the start of basic blocks for !frame_pointer_needed functions. */
3005 :
3006 : void
3007 3516103 : cselib_record_sp_cfa_base_equiv (HOST_WIDE_INT offset, rtx_insn *insn)
3008 : {
3009 3516103 : rtx sp_derived_value = NULL_RTX;
3010 7032206 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs; l; l = l->next)
3011 7032206 : if (GET_CODE (l->loc) == VALUE
3012 7032206 : && SP_DERIVED_VALUE_P (l->loc))
3013 : {
3014 : sp_derived_value = l->loc;
3015 : break;
3016 : }
3017 7032206 : else if (GET_CODE (l->loc) == PLUS
3018 3516103 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
3019 3516103 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
3020 10548309 : && CONST_INT_P (XEXP (l->loc, 1)))
3021 : {
3022 3516103 : sp_derived_value = XEXP (l->loc, 0);
3023 3516103 : offset = offset + UINTVAL (XEXP (l->loc, 1));
3024 3516103 : break;
3025 : }
3026 3516103 : if (sp_derived_value == NULL_RTX)
3027 : return;
3028 3516103 : cselib_val *val
3029 3516103 : = cselib_lookup_from_insn (plus_constant (Pmode, sp_derived_value, offset),
3030 3516103 : Pmode, 1, VOIDmode, insn);
3031 3516103 : if (val != NULL)
3032 : {
3033 3516103 : PRESERVED_VALUE_P (val->val_rtx) = 1;
3034 3516103 : cselib_record_set (stack_pointer_rtx, val, NULL);
3035 : }
3036 : }
3037 :
3038 : /* Return true if V is SP_DERIVED_VALUE_P (or SP_DERIVED_VALUE_P + CONST_INT)
3039 : that can be expressed using cfa_base_preserved_val + CONST_INT. */
3040 :
3041 : bool
3042 31218769 : cselib_sp_derived_value_p (cselib_val *v)
3043 : {
3044 31218769 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
3045 68694686 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
3046 37996323 : if (GET_CODE (l->loc) == PLUS
3047 7172538 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
3048 6952008 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
3049 43120406 : && CONST_INT_P (XEXP (l->loc, 1)))
3050 5124083 : v = CSELIB_VAL_PTR (XEXP (l->loc, 0));
3051 31218769 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
3052 : return false;
3053 11587118 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
3054 11587118 : if (l->loc == cfa_base_preserved_val->val_rtx)
3055 : return true;
3056 11587118 : else if (GET_CODE (l->loc) == PLUS
3057 5644489 : && XEXP (l->loc, 0) == cfa_base_preserved_val->val_rtx
3058 5644489 : && CONST_INT_P (XEXP (l->loc, 1)))
3059 : return true;
3060 : return false;
3061 : }
3062 :
3063 : /* There is no good way to determine how many elements there can be
3064 : in a PARALLEL. Since it's fairly cheap, use a really large number. */
3065 : #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
3066 :
3067 : struct cselib_record_autoinc_data
3068 : {
3069 : struct cselib_set *sets;
3070 : int n_sets;
3071 : };
3072 :
3073 : /* Callback for for_each_inc_dec. Records in ARG the SETs implied by
3074 : autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */
3075 :
3076 : static int
3077 13473651 : cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED, rtx op ATTRIBUTE_UNUSED,
3078 : rtx dest, rtx src, rtx srcoff, void *arg)
3079 : {
3080 13473651 : struct cselib_record_autoinc_data *data;
3081 13473651 : data = (struct cselib_record_autoinc_data *)arg;
3082 :
3083 13473651 : data->sets[data->n_sets].dest = dest;
3084 :
3085 13473651 : if (srcoff)
3086 13102252 : data->sets[data->n_sets].src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
3087 : else
3088 371399 : data->sets[data->n_sets].src = src;
3089 :
3090 13473651 : data->n_sets++;
3091 :
3092 13473651 : return 0;
3093 : }
3094 :
3095 : /* Record the effects of any sets and autoincs in INSN. */
3096 : static void
3097 912583824 : cselib_record_sets (rtx_insn *insn)
3098 : {
3099 912583824 : int n_sets = 0;
3100 912583824 : int i;
3101 912583824 : struct cselib_set sets[MAX_SETS];
3102 912583824 : rtx cond = 0;
3103 912583824 : int n_sets_before_autoinc;
3104 912583824 : int n_strict_low_parts = 0;
3105 912583824 : struct cselib_record_autoinc_data data;
3106 :
3107 912583824 : rtx body = PATTERN (insn);
3108 912583824 : if (GET_CODE (body) == COND_EXEC)
3109 : {
3110 0 : cond = COND_EXEC_TEST (body);
3111 0 : body = COND_EXEC_CODE (body);
3112 : }
3113 :
3114 : /* Find all sets. */
3115 912583824 : if (GET_CODE (body) == SET)
3116 : {
3117 373912969 : sets[0].src = SET_SRC (body);
3118 373912969 : sets[0].dest = SET_DEST (body);
3119 373912969 : n_sets = 1;
3120 : }
3121 538670855 : else if (GET_CODE (body) == PARALLEL)
3122 : {
3123 : /* Look through the PARALLEL and record the values being
3124 : set, if possible. Also handle any CLOBBERs. */
3125 212479922 : for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3126 : {
3127 143319058 : rtx x = XVECEXP (body, 0, i);
3128 :
3129 143319058 : if (GET_CODE (x) == SET)
3130 : {
3131 74988427 : sets[n_sets].src = SET_SRC (x);
3132 74988427 : sets[n_sets].dest = SET_DEST (x);
3133 74988427 : n_sets++;
3134 : }
3135 : }
3136 : }
3137 :
3138 373912969 : if (n_sets == 1
3139 437159866 : && MEM_P (sets[0].src)
3140 62519388 : && !cselib_record_memory
3141 109262983 : && MEM_READONLY_P (sets[0].src))
3142 : {
3143 3258332 : rtx note = find_reg_equal_equiv_note (insn);
3144 :
3145 3258332 : if (note && CONSTANT_P (XEXP (note, 0)))
3146 2059285 : sets[0].src = XEXP (note, 0);
3147 : }
3148 :
3149 912583824 : data.sets = sets;
3150 912583824 : data.n_sets = n_sets_before_autoinc = n_sets;
3151 912583824 : for_each_inc_dec (PATTERN (insn), cselib_record_autoinc_cb, &data);
3152 912583824 : n_sets = data.n_sets;
3153 :
3154 : /* Look up the values that are read. Do this before invalidating the
3155 : locations that are written. */
3156 1374958871 : for (i = 0; i < n_sets; i++)
3157 : {
3158 462375047 : rtx dest = sets[i].dest;
3159 462375047 : rtx orig = dest;
3160 :
3161 : /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
3162 : the low part after invalidating any knowledge about larger modes. */
3163 462375047 : if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
3164 51897 : sets[i].dest = dest = XEXP (dest, 0);
3165 :
3166 : /* We don't know how to record anything but REG or MEM. */
3167 462375047 : if (REG_P (dest)
3168 124773787 : || (MEM_P (dest) && cselib_record_memory))
3169 : {
3170 366411449 : rtx src = sets[i].src;
3171 366411449 : if (cond)
3172 0 : src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
3173 366411449 : sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1, VOIDmode);
3174 366411449 : if (MEM_P (dest))
3175 : {
3176 28810189 : machine_mode address_mode = get_address_mode (dest);
3177 :
3178 28810189 : sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
3179 : address_mode, 1,
3180 28810189 : GET_MODE (dest));
3181 : }
3182 : else
3183 337601260 : sets[i].dest_addr_elt = 0;
3184 : }
3185 :
3186 : /* Improve handling of STRICT_LOW_PART if the current value is known
3187 : to be const0_rtx, then the low bits will be set to dest and higher
3188 : bits will remain zero. Used in code like:
3189 :
3190 : {di:SI=0;clobber flags:CC;}
3191 : flags:CCNO=cmp(bx:SI,0)
3192 : strict_low_part(di:QI)=flags:CCNO<=0
3193 :
3194 : where we can note both that di:QI=flags:CCNO<=0 and
3195 : also that because di:SI is known to be 0 and strict_low_part(di:QI)
3196 : preserves the upper bits that di:SI=zero_extend(flags:CCNO<=0). */
3197 462375047 : scalar_int_mode mode;
3198 462375047 : if (dest != orig
3199 51897 : && cselib_record_sets_hook
3200 16487 : && REG_P (dest)
3201 16487 : && HARD_REGISTER_P (dest)
3202 16487 : && sets[i].src_elt
3203 462391534 : && is_a <scalar_int_mode> (GET_MODE (dest), &mode)
3204 462391534 : && n_sets + n_strict_low_parts < MAX_SETS)
3205 : {
3206 16487 : opt_scalar_int_mode wider_mode_iter;
3207 41205 : FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
3208 : {
3209 41205 : scalar_int_mode wider_mode = wider_mode_iter.require ();
3210 48734 : if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD)
3211 : break;
3212 :
3213 39925 : rtx reg = gen_lowpart (wider_mode, dest);
3214 39925 : if (!REG_P (reg))
3215 : break;
3216 :
3217 39861 : cselib_val *v = cselib_lookup (reg, wider_mode, 0, VOIDmode);
3218 39861 : if (!v)
3219 24718 : continue;
3220 :
3221 16093 : struct elt_loc_list *l;
3222 34018 : for (l = v->locs; l; l = l->next)
3223 33068 : if (l->loc == const0_rtx)
3224 : break;
3225 :
3226 950 : if (!l)
3227 950 : continue;
3228 :
3229 15143 : sets[n_sets + n_strict_low_parts].dest = reg;
3230 15143 : sets[n_sets + n_strict_low_parts].src = dest;
3231 15143 : sets[n_sets + n_strict_low_parts++].src_elt = sets[i].src_elt;
3232 15143 : break;
3233 : }
3234 : }
3235 : }
3236 :
3237 912583824 : if (cselib_record_sets_hook)
3238 82124252 : cselib_record_sets_hook (insn, sets, n_sets);
3239 :
3240 : /* Invalidate all locations written by this insn. Note that the elts we
3241 : looked up in the previous loop aren't affected, just some of their
3242 : locations may go away. */
3243 912583824 : note_pattern_stores (body, cselib_invalidate_rtx_note_stores, NULL);
3244 :
3245 1838641299 : for (i = n_sets_before_autoinc; i < n_sets; i++)
3246 13473651 : cselib_invalidate_rtx (sets[i].dest);
3247 :
3248 : /* If this is an asm, look for duplicate sets. This can happen when the
3249 : user uses the same value as an output multiple times. This is valid
3250 : if the outputs are not actually used thereafter. Treat this case as
3251 : if the value isn't actually set. We do this by smashing the destination
3252 : to pc_rtx, so that we won't record the value later. */
3253 912583824 : if (n_sets >= 2 && asm_noperands (body) >= 0)
3254 : {
3255 532910 : for (i = 0; i < n_sets; i++)
3256 : {
3257 409273 : rtx dest = sets[i].dest;
3258 409273 : if (REG_P (dest) || MEM_P (dest))
3259 : {
3260 409240 : int j;
3261 942792 : for (j = i + 1; j < n_sets; j++)
3262 533552 : if (rtx_equal_p (dest, sets[j].dest))
3263 : {
3264 0 : sets[i].dest = pc_rtx;
3265 0 : sets[j].dest = pc_rtx;
3266 : }
3267 : }
3268 : }
3269 : }
3270 :
3271 : /* Now enter the equivalences in our tables. */
3272 1374958871 : for (i = 0; i < n_sets; i++)
3273 : {
3274 462375047 : rtx dest = sets[i].dest;
3275 462375047 : if (REG_P (dest)
3276 124773787 : || (MEM_P (dest) && cselib_record_memory))
3277 366411449 : cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
3278 : }
3279 :
3280 : /* And deal with STRICT_LOW_PART. */
3281 912598967 : for (i = 0; i < n_strict_low_parts; i++)
3282 : {
3283 15143 : if (! PRESERVED_VALUE_P (sets[n_sets + i].src_elt->val_rtx))
3284 0 : continue;
3285 15143 : machine_mode dest_mode = GET_MODE (sets[n_sets + i].dest);
3286 15143 : cselib_val *v
3287 15143 : = cselib_lookup (sets[n_sets + i].dest, dest_mode, 1, VOIDmode);
3288 15143 : cselib_preserve_value (v);
3289 15143 : rtx r = gen_rtx_ZERO_EXTEND (dest_mode,
3290 : sets[n_sets + i].src_elt->val_rtx);
3291 15143 : cselib_add_permanent_equiv (v, r, insn);
3292 : }
3293 912583824 : }
3294 :
3295 : /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
3296 :
3297 : bool
3298 41039958 : fp_setter_insn (rtx_insn *insn)
3299 : {
3300 41039958 : rtx expr, pat = NULL_RTX;
3301 :
3302 41039958 : if (!RTX_FRAME_RELATED_P (insn))
3303 : return false;
3304 :
3305 624645 : expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
3306 624645 : if (expr)
3307 75 : pat = XEXP (expr, 0);
3308 624645 : if (!modified_in_p (hard_frame_pointer_rtx, pat ? pat : insn))
3309 : return false;
3310 :
3311 : /* Don't return true for frame pointer restores in the epilogue. */
3312 153316 : if (find_reg_note (insn, REG_CFA_RESTORE, hard_frame_pointer_rtx))
3313 : return false;
3314 : return true;
3315 : }
3316 :
3317 : /* V is one of the values in REG_VALUES (REGNO). Return true if it
3318 : would be invalidated by CALLEE_ABI. */
3319 :
3320 : static bool
3321 116051621 : cselib_invalidated_by_call_p (const function_abi &callee_abi,
3322 : unsigned int regno, cselib_val *v)
3323 : {
3324 116051621 : machine_mode mode = GET_MODE (v->val_rtx);
3325 116051621 : if (mode == VOIDmode)
3326 : {
3327 0 : v = REG_VALUES (regno)->elt;
3328 0 : if (!v)
3329 : /* If we don't know what the mode of the constant value is, and we
3330 : don't know what mode the register was set in, conservatively
3331 : assume that the register is clobbered. The value's going to be
3332 : essentially useless in this case anyway. */
3333 : return true;
3334 0 : mode = GET_MODE (v->val_rtx);
3335 : }
3336 116051621 : return callee_abi.clobbers_reg_p (mode, regno);
3337 : }
3338 :
3339 : /* Record the effects of INSN. */
3340 :
3341 : void
3342 1049454074 : cselib_process_insn (rtx_insn *insn)
3343 : {
3344 1049454074 : int i;
3345 1049454074 : rtx x;
3346 :
3347 1049454074 : cselib_current_insn = insn;
3348 :
3349 : /* Forget everything at a CODE_LABEL or a setjmp. */
3350 1049454074 : if ((LABEL_P (insn)
3351 1013628393 : || (CALL_P (insn)
3352 34673945 : && find_reg_note (insn, REG_SETJMP, NULL)))
3353 1049458406 : && !cselib_preserve_constants)
3354 : {
3355 35829785 : cselib_reset_table (next_uid);
3356 35829785 : cselib_current_insn = NULL;
3357 35829785 : return;
3358 : }
3359 :
3360 1013624289 : if (! INSN_P (insn))
3361 : {
3362 101040465 : cselib_current_insn = NULL;
3363 101040465 : return;
3364 : }
3365 :
3366 : /* If this is a call instruction, forget anything stored in a
3367 : call clobbered register, or, if this is not a const call, in
3368 : memory. */
3369 912583824 : if (CALL_P (insn))
3370 : {
3371 34669841 : function_abi callee_abi = insn_callee_abi (insn);
3372 3224295213 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3373 : {
3374 3189625372 : elt_list **l = ®_VALUES (i);
3375 3416066905 : while (*l)
3376 : {
3377 226441533 : cselib_val *v = (*l)->elt;
3378 226441533 : if (v && cselib_invalidated_by_call_p (callee_abi, i, v))
3379 72578241 : cselib_invalidate_regno_val (i, l);
3380 : else
3381 153863292 : l = &(*l)->next;
3382 : }
3383 : }
3384 :
3385 : /* Since it is not clear how cselib is going to be used, be
3386 : conservative here and treat looping pure or const functions
3387 : as if they were regular functions. */
3388 34669841 : if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
3389 34669841 : || !(RTL_CONST_OR_PURE_CALL_P (insn)))
3390 31689616 : cselib_invalidate_mem (callmem[0]);
3391 : else
3392 : {
3393 : /* For const/pure calls, invalidate any argument slots because
3394 : they are owned by the callee. */
3395 8855115 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3396 5874890 : if (GET_CODE (XEXP (x, 0)) == USE
3397 5874890 : && MEM_P (XEXP (XEXP (x, 0), 0)))
3398 142783 : cselib_invalidate_mem (XEXP (XEXP (x, 0), 0));
3399 : /* And invalidate memory below the stack (or above for
3400 : !STACK_GROWS_DOWNWARD), as even const/pure call can invalidate
3401 : that. Do this only if !ACCUMULATE_OUTGOING_ARGS or if
3402 : cfun->calls_alloca, otherwise the stack pointer shouldn't be
3403 : changing in the middle of the function and nothing should be
3404 : stored below the stack pointer. */
3405 2980225 : if (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca)
3406 2979758 : cselib_invalidate_mem (callmem[1]);
3407 : }
3408 : }
3409 :
3410 912583824 : cselib_record_sets (insn);
3411 :
3412 : /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3413 : after we have processed the insn. */
3414 912583824 : if (CALL_P (insn))
3415 : {
3416 102916323 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3417 68246482 : if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3418 0 : cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
3419 :
3420 : /* Flush everything on setjmp. */
3421 34669841 : if (cselib_preserve_constants
3422 34669841 : && find_reg_note (insn, REG_SETJMP, NULL))
3423 : {
3424 228 : cselib_preserve_only_values ();
3425 228 : cselib_reset_table (next_uid);
3426 : }
3427 : }
3428 :
3429 : /* On setter of the hard frame pointer if frame_pointer_needed,
3430 : invalidate stack_pointer_rtx, so that sp and {,h}fp based
3431 : VALUEs are distinct. */
3432 912583824 : if (reload_completed
3433 417514642 : && frame_pointer_needed
3434 953503640 : && fp_setter_insn (insn))
3435 93392 : cselib_invalidate_rtx (stack_pointer_rtx);
3436 :
3437 912583824 : cselib_current_insn = NULL;
3438 :
3439 912583824 : if (n_useless_values > MAX_USELESS_VALUES
3440 : /* remove_useless_values is linear in the hash table size. Avoid
3441 : quadratic behavior for very large hashtables with very few
3442 : useless elements. */
3443 912583824 : && ((unsigned int)n_useless_values
3444 2508634 : > (cselib_hash_table->elements () - n_debug_values) / 4))
3445 28147 : remove_useless_values ();
3446 : }
3447 :
3448 : /* Initialize cselib for one pass. The caller must also call
3449 : init_alias_analysis. */
3450 :
3451 : void
3452 10329623 : cselib_init (int record_what)
3453 : {
3454 10329623 : cselib_record_memory = record_what & CSELIB_RECORD_MEMORY;
3455 10329623 : cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS;
3456 10329623 : cselib_any_perm_equivs = false;
3457 :
3458 : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
3459 : see canon_true_dependence. This is only created once. */
3460 10329623 : if (! callmem[0])
3461 146618 : callmem[0] = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
3462 : /* Similarly create a MEM representing roughly everything below
3463 : the stack for STACK_GROWS_DOWNWARD targets or everything above
3464 : it otherwise. Do this only when !ACCUMULATE_OUTGOING_ARGS or
3465 : if cfun->calls_alloca, otherwise the stack pointer shouldn't be
3466 : changing in the middle of the function and nothing should be stored
3467 : below the stack pointer. */
3468 10329623 : if (!callmem[1] && (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca))
3469 : {
3470 146360 : if (STACK_GROWS_DOWNWARD)
3471 : {
3472 146360 : unsigned HOST_WIDE_INT off = -(GET_MODE_MASK (Pmode) >> 1);
3473 : #ifdef STACK_ADDRESS_OFFSET
3474 : /* On SPARC take stack pointer bias into account as well. */
3475 : off += (STACK_ADDRESS_OFFSET
3476 : - FIRST_PARM_OFFSET (current_function_decl));
3477 : #endif
3478 146360 : callmem[1] = plus_constant (Pmode, stack_pointer_rtx, off);
3479 : }
3480 : else
3481 : callmem[1] = stack_pointer_rtx;
3482 146360 : callmem[1] = gen_rtx_MEM (BLKmode, callmem[1]);
3483 151783 : set_mem_size (callmem[1], GET_MODE_MASK (Pmode) >> 1);
3484 : }
3485 :
3486 10329623 : cselib_nregs = max_reg_num ();
3487 :
3488 : /* We preserve reg_values to allow expensive clearing of the whole thing.
3489 : Reallocate it however if it happens to be too large. */
3490 10329623 : if (!reg_values || reg_values_size < cselib_nregs
3491 10026488 : || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
3492 : {
3493 319191 : free (reg_values);
3494 : /* Some space for newly emit instructions so we don't end up
3495 : reallocating in between passes. */
3496 319191 : reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
3497 319191 : reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
3498 : }
3499 10329623 : used_regs = XNEWVEC (unsigned int, cselib_nregs);
3500 10329623 : n_used_regs = 0;
3501 : /* FIXME: enable sanitization (PR87845) */
3502 10329623 : cselib_hash_table
3503 10329623 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3504 10329623 : /* sanitize_eq_and_hash */ false);
3505 10329623 : if (cselib_preserve_constants)
3506 508689 : cselib_preserved_hash_table
3507 508689 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3508 508689 : /* sanitize_eq_and_hash */ false);
3509 10329623 : next_uid = 1;
3510 10329623 : }
3511 :
3512 : /* Called when the current user is done with cselib. */
3513 :
3514 : void
3515 10329623 : cselib_finish (void)
3516 : {
3517 10329623 : bool preserved = cselib_preserve_constants;
3518 10329623 : cselib_discard_hook = NULL;
3519 10329623 : cselib_preserve_constants = false;
3520 10329623 : cselib_any_perm_equivs = false;
3521 10329623 : cfa_base_preserved_val = NULL;
3522 10329623 : cfa_base_preserved_regno = INVALID_REGNUM;
3523 10329623 : elt_list_pool.release ();
3524 10329623 : elt_loc_list_pool.release ();
3525 10329623 : cselib_val_pool.release ();
3526 10329623 : value_pool.release ();
3527 10329623 : cselib_clear_table ();
3528 10329623 : delete cselib_hash_table;
3529 10329623 : cselib_hash_table = NULL;
3530 10329623 : if (preserved)
3531 508689 : delete cselib_preserved_hash_table;
3532 10329623 : cselib_preserved_prune_list.release ();
3533 10329623 : cselib_preserved_hash_table = NULL;
3534 10329623 : free (used_regs);
3535 10329623 : used_regs = 0;
3536 10329623 : n_useless_values = 0;
3537 10329623 : n_useless_debug_values = 0;
3538 10329623 : n_debug_values = 0;
3539 10329623 : next_uid = 0;
3540 10329623 : }
3541 :
3542 : /* Dump the cselib_val V to FILE *OUT. */
3543 :
3544 : int
3545 93 : dump_cselib_val (cselib_val *v, FILE *out)
3546 : {
3547 93 : bool need_lf = true;
3548 :
3549 93 : print_inline_rtx (out, v->val_rtx, 0);
3550 :
3551 93 : if (v->locs)
3552 : {
3553 86 : struct elt_loc_list *l = v->locs;
3554 86 : if (need_lf)
3555 : {
3556 86 : fputc ('\n', out);
3557 86 : need_lf = false;
3558 : }
3559 86 : fputs (" locs:", out);
3560 149 : do
3561 : {
3562 149 : if (l->setting_insn)
3563 149 : fprintf (out, "\n from insn %i ",
3564 149 : INSN_UID (l->setting_insn));
3565 : else
3566 0 : fprintf (out, "\n ");
3567 149 : print_inline_rtx (out, l->loc, 4);
3568 : }
3569 149 : while ((l = l->next));
3570 86 : fputc ('\n', out);
3571 : }
3572 : else
3573 : {
3574 7 : fputs (" no locs", out);
3575 7 : need_lf = true;
3576 : }
3577 :
3578 93 : if (v->addr_list)
3579 : {
3580 6 : struct elt_list *e = v->addr_list;
3581 6 : if (need_lf)
3582 : {
3583 0 : fputc ('\n', out);
3584 0 : need_lf = false;
3585 : }
3586 6 : fputs (" addr list:", out);
3587 6 : do
3588 : {
3589 6 : fputs ("\n ", out);
3590 6 : print_inline_rtx (out, e->elt->val_rtx, 2);
3591 : }
3592 6 : while ((e = e->next));
3593 6 : fputc ('\n', out);
3594 : }
3595 : else
3596 : {
3597 87 : fputs (" no addrs", out);
3598 87 : need_lf = true;
3599 : }
3600 :
3601 93 : if (v->next_containing_mem == &dummy_val)
3602 6 : fputs (" last mem\n", out);
3603 87 : else if (v->next_containing_mem)
3604 : {
3605 0 : fputs (" next mem ", out);
3606 0 : print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
3607 0 : fputc ('\n', out);
3608 : }
3609 87 : else if (need_lf)
3610 81 : fputc ('\n', out);
3611 :
3612 93 : return 1;
3613 : }
3614 :
3615 : /* Dump the cselib_val *X to FILE *OUT. */
3616 :
3617 : static int
3618 93 : dump_cselib_val_ptr (cselib_val **x, FILE *out)
3619 : {
3620 93 : cselib_val *v = *x;
3621 93 : return dump_cselib_val (v, out);
3622 : }
3623 :
3624 : /* Dump to OUT everything in the CSELIB table. */
3625 :
3626 : void
3627 11 : dump_cselib_table (FILE *out)
3628 : {
3629 11 : fprintf (out, "cselib hash table:\n");
3630 104 : cselib_hash_table->traverse <FILE *, dump_cselib_val_ptr> (out);
3631 11 : if (cselib_preserved_hash_table)
3632 : {
3633 11 : fprintf (out, "cselib preserved hash table:\n");
3634 11 : cselib_preserved_hash_table->traverse <FILE *, dump_cselib_val_ptr> (out);
3635 : }
3636 11 : if (first_containing_mem != &dummy_val)
3637 : {
3638 6 : fputs ("first mem ", out);
3639 6 : print_inline_rtx (out, first_containing_mem->val_rtx, 2);
3640 6 : fputc ('\n', out);
3641 : }
3642 11 : fprintf (out, "next uid %i\n", next_uid);
3643 11 : }
3644 :
3645 : #include "gt-cselib.h"
|
