Branch data Line data Source code
1 : : /* Common subexpression elimination library for GNU compiler.
2 : : Copyright (C) 1987-2025 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 : :
38 : : /* A list of cselib_val structures. */
39 : : struct elt_list
40 : : {
41 : : struct elt_list *next;
42 : : cselib_val *elt;
43 : : };
44 : :
45 : : static bool cselib_record_memory;
46 : : static bool cselib_preserve_constants;
47 : : static bool cselib_any_perm_equivs;
48 : : static inline void promote_debug_loc (struct elt_loc_list *l);
49 : : static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
50 : : static void new_elt_loc_list (cselib_val *, rtx);
51 : : static void unchain_one_value (cselib_val *);
52 : : static void unchain_one_elt_list (struct elt_list **);
53 : : static void unchain_one_elt_loc_list (struct elt_loc_list **);
54 : : static void remove_useless_values (void);
55 : : static hashval_t cselib_hash_rtx (rtx, int, machine_mode);
56 : : static cselib_val *new_cselib_val (unsigned int, machine_mode, rtx);
57 : : static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
58 : : static cselib_val *cselib_lookup_mem (rtx, int);
59 : : static void cselib_invalidate_regno (unsigned int, machine_mode);
60 : : static void cselib_invalidate_mem (rtx);
61 : : static void cselib_record_set (rtx, cselib_val *, cselib_val *);
62 : : static void cselib_record_sets (rtx_insn *);
63 : : static rtx autoinc_split (rtx, rtx *, machine_mode);
64 : :
65 : : #define PRESERVED_VALUE_P(RTX) \
66 : : (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
67 : :
68 : : #define SP_BASED_VALUE_P(RTX) \
69 : : (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump)
70 : :
71 : : #define SP_DERIVED_VALUE_P(RTX) \
72 : : (RTL_FLAG_CHECK1 ("SP_DERIVED_VALUE_P", (RTX), VALUE)->call)
73 : :
74 : : struct expand_value_data
75 : : {
76 : : bitmap regs_active;
77 : : cselib_expand_callback callback;
78 : : void *callback_arg;
79 : : bool dummy;
80 : : };
81 : :
82 : : static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
83 : :
84 : : /* This is a global so we don't have to pass this through every function.
85 : : It is used in new_elt_loc_list to set SETTING_INSN. */
86 : : static rtx_insn *cselib_current_insn;
87 : :
88 : : /* There are three ways in which cselib can look up an rtx:
89 : : - for a REG, the reg_values table (which is indexed by regno) is used
90 : : - for a MEM, we recursively look up its address and then follow the
91 : : addr_list of that value
92 : : - for everything else, we compute a hash value and go through the hash
93 : : table. Since different rtx's can still have the same hash value,
94 : : this involves walking the table entries for a given value and comparing
95 : : the locations of the entries with the rtx we are looking up. */
96 : :
97 : : struct cselib_hasher : nofree_ptr_hash <cselib_val>
98 : : {
99 : : struct key {
100 : : /* The rtx value and its mode (needed separately for constant
101 : : integers). */
102 : : machine_mode mode;
103 : : rtx x;
104 : : /* The mode of the contaning MEM, if any, otherwise VOIDmode. */
105 : : machine_mode memmode;
106 : : };
107 : : typedef key *compare_type;
108 : : static inline hashval_t hash (const cselib_val *);
109 : : static inline bool equal (const cselib_val *, const key *);
110 : : };
111 : :
112 : : /* The hash function for our hash table. The value is always computed with
113 : : cselib_hash_rtx when adding an element; this function just extracts the
114 : : hash value from a cselib_val structure. */
115 : :
116 : : inline hashval_t
117 : 102805029 : cselib_hasher::hash (const cselib_val *v)
118 : : {
119 : 102805029 : return v->hash;
120 : : }
121 : :
122 : : /* The equality test for our hash table. The first argument V is a table
123 : : element (i.e. a cselib_val), while the second arg X is an rtx. We know
124 : : that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
125 : : CONST of an appropriate mode. */
126 : :
127 : : inline bool
128 : 574762098 : cselib_hasher::equal (const cselib_val *v, const key *x_arg)
129 : : {
130 : 574762098 : struct elt_loc_list *l;
131 : 574762098 : rtx x = x_arg->x;
132 : 574762098 : machine_mode mode = x_arg->mode;
133 : 574762098 : machine_mode memmode = x_arg->memmode;
134 : :
135 : 574762098 : if (mode != GET_MODE (v->val_rtx))
136 : : return false;
137 : :
138 : 460592838 : if (GET_CODE (x) == VALUE)
139 : 12910513 : return x == v->val_rtx;
140 : :
141 : 457670929 : if (SP_DERIVED_VALUE_P (v->val_rtx) && GET_MODE (x) == Pmode)
142 : : {
143 : 17645329 : rtx xoff = NULL;
144 : 17645329 : if (autoinc_split (x, &xoff, memmode) == v->val_rtx && xoff == NULL_RTX)
145 : 7820173 : return true;
146 : : }
147 : :
148 : : /* We don't guarantee that distinct rtx's have different hash values,
149 : : so we need to do a comparison. */
150 : 754982365 : for (l = v->locs; l; l = l->next)
151 : 491590271 : if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)
152 : 38323070 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
153 : : {
154 : 11210935 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
155 : : /* If l is so far a debug only loc, without debug stmts it
156 : : would never be compared to x at all, so temporarily pretend
157 : : current instruction is that DEBUG_INSN so that we don't
158 : : promote other debug locs even for unsuccessful comparison. */
159 : 11210935 : cselib_current_insn = l->setting_insn;
160 : 11210935 : bool match = rtx_equal_for_cselib_1 (l->loc, x, memmode, 0);
161 : 11210935 : cselib_current_insn = save_cselib_current_insn;
162 : 11210935 : if (match)
163 : : {
164 : 928937 : promote_debug_loc (l);
165 : 928937 : return true;
166 : : }
167 : : }
168 : 480379336 : else if (rtx_equal_for_cselib_1 (l->loc, x, memmode, 0))
169 : : return true;
170 : :
171 : : return false;
172 : : }
173 : :
174 : : /* A table that enables us to look up elts by their value. */
175 : : static hash_table<cselib_hasher> *cselib_hash_table;
176 : :
177 : : /* A table to hold preserved values. */
178 : : static hash_table<cselib_hasher> *cselib_preserved_hash_table;
179 : :
180 : : /* The unique id that the next create value will take. */
181 : : static unsigned int next_uid;
182 : :
183 : : /* The number of registers we had when the varrays were last resized. */
184 : : static unsigned int cselib_nregs;
185 : :
186 : : /* Count values without known locations, or with only locations that
187 : : wouldn't have been known except for debug insns. Whenever this
188 : : grows too big, we remove these useless values from the table.
189 : :
190 : : Counting values with only debug values is a bit tricky. We don't
191 : : want to increment n_useless_values when we create a value for a
192 : : debug insn, for this would get n_useless_values out of sync, but we
193 : : want increment it if all locs in the list that were ever referenced
194 : : in nondebug insns are removed from the list.
195 : :
196 : : In the general case, once we do that, we'd have to stop accepting
197 : : nondebug expressions in the loc list, to avoid having two values
198 : : equivalent that, without debug insns, would have been made into
199 : : separate values. However, because debug insns never introduce
200 : : equivalences themselves (no assignments), the only means for
201 : : growing loc lists is through nondebug assignments. If the locs
202 : : also happen to be referenced in debug insns, it will work just fine.
203 : :
204 : : A consequence of this is that there's at most one debug-only loc in
205 : : each loc list. If we keep it in the first entry, testing whether
206 : : we have a debug-only loc list takes O(1).
207 : :
208 : : Furthermore, since any additional entry in a loc list containing a
209 : : debug loc would have to come from an assignment (nondebug) that
210 : : references both the initial debug loc and the newly-equivalent loc,
211 : : the initial debug loc would be promoted to a nondebug loc, and the
212 : : loc list would not contain debug locs any more.
213 : :
214 : : So the only case we have to be careful with in order to keep
215 : : n_useless_values in sync between debug and nondebug compilations is
216 : : to avoid incrementing n_useless_values when removing the single loc
217 : : from a value that turns out to not appear outside debug values. We
218 : : increment n_useless_debug_values instead, and leave such values
219 : : alone until, for other reasons, we garbage-collect useless
220 : : values. */
221 : : static int n_useless_values;
222 : : static int n_useless_debug_values;
223 : :
224 : : /* Count values whose locs have been taken exclusively from debug
225 : : insns for the entire life of the value. */
226 : : static int n_debug_values;
227 : :
228 : : /* Number of useless values before we remove them from the hash table. */
229 : : #define MAX_USELESS_VALUES 32
230 : :
231 : : /* This table maps from register number to values. It does not
232 : : contain pointers to cselib_val structures, but rather elt_lists.
233 : : The purpose is to be able to refer to the same register in
234 : : different modes. The first element of the list defines the mode in
235 : : which the register was set; if the mode is unknown or the value is
236 : : no longer valid in that mode, ELT will be NULL for the first
237 : : element. */
238 : : static struct elt_list **reg_values;
239 : : static unsigned int reg_values_size;
240 : : #define REG_VALUES(i) reg_values[i]
241 : :
242 : : /* The largest number of hard regs used by any entry added to the
243 : : REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
244 : : static unsigned int max_value_regs;
245 : :
246 : : /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
247 : : in cselib_clear_table() for fast emptying. */
248 : : static unsigned int *used_regs;
249 : : static unsigned int n_used_regs;
250 : :
251 : : /* We pass this to cselib_invalidate_mem to invalidate all of
252 : : memory for a non-const call instruction and memory below stack pointer
253 : : for const/pure calls. */
254 : : static GTY(()) rtx callmem[2];
255 : :
256 : : /* Set by discard_useless_locs if it deleted the last location of any
257 : : value. */
258 : : static int values_became_useless;
259 : :
260 : : /* Used as stop element of the containing_mem list so we can check
261 : : presence in the list by checking the next pointer. */
262 : : static cselib_val dummy_val;
263 : :
264 : : /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
265 : : that is constant through the whole function and should never be
266 : : eliminated. */
267 : : static cselib_val *cfa_base_preserved_val;
268 : : static unsigned int cfa_base_preserved_regno = INVALID_REGNUM;
269 : :
270 : : /* Used to list all values that contain memory reference.
271 : : May or may not contain the useless values - the list is compacted
272 : : each time memory is invalidated. */
273 : : static cselib_val *first_containing_mem = &dummy_val;
274 : :
275 : : static object_allocator<elt_list> elt_list_pool ("elt_list");
276 : : static object_allocator<elt_loc_list> elt_loc_list_pool ("elt_loc_list");
277 : : static object_allocator<cselib_val> cselib_val_pool ("cselib_val_list");
278 : :
279 : : static pool_allocator value_pool ("value", RTX_CODE_SIZE (VALUE));
280 : :
281 : : /* If nonnull, cselib will call this function before freeing useless
282 : : VALUEs. A VALUE is deemed useless if its "locs" field is null. */
283 : : void (*cselib_discard_hook) (cselib_val *);
284 : :
285 : : /* If nonnull, cselib will call this function before recording sets or
286 : : even clobbering outputs of INSN. All the recorded sets will be
287 : : represented in the array sets[n_sets]. new_val_min can be used to
288 : : tell whether values present in sets are introduced by this
289 : : instruction. */
290 : : void (*cselib_record_sets_hook) (rtx_insn *insn, struct cselib_set *sets,
291 : : int n_sets);
292 : :
293 : :
294 : :
295 : : /* Allocate a struct elt_list and fill in its two elements with the
296 : : arguments. */
297 : :
298 : : static inline struct elt_list *
299 : 484731042 : new_elt_list (struct elt_list *next, cselib_val *elt)
300 : : {
301 : 969462084 : elt_list *el = elt_list_pool.allocate ();
302 : 484731042 : el->next = next;
303 : 484731042 : el->elt = elt;
304 : 484731042 : return el;
305 : : }
306 : :
307 : : /* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc
308 : : list. */
309 : :
310 : : static inline void
311 : 720458025 : new_elt_loc_list (cselib_val *val, rtx loc)
312 : : {
313 : 724420789 : struct elt_loc_list *el, *next = val->locs;
314 : :
315 : 724420789 : gcc_checking_assert (!next || !next->setting_insn
316 : : || !DEBUG_INSN_P (next->setting_insn)
317 : : || cselib_current_insn == next->setting_insn);
318 : :
319 : : /* If we're creating the first loc in a debug insn context, we've
320 : : just created a debug value. Count it. */
321 : 422430934 : if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
322 : 6889153 : n_debug_values++;
323 : :
324 : 724420789 : val = canonical_cselib_val (val);
325 : 724420789 : next = val->locs;
326 : :
327 : 724420789 : if (GET_CODE (loc) == VALUE)
328 : : {
329 : 7930364 : loc = canonical_cselib_val (CSELIB_VAL_PTR (loc))->val_rtx;
330 : :
331 : 7930364 : gcc_checking_assert (PRESERVED_VALUE_P (loc)
332 : : == PRESERVED_VALUE_P (val->val_rtx));
333 : :
334 : 7930364 : if (val->val_rtx == loc)
335 : : return;
336 : 7925600 : else if (val->uid > CSELIB_VAL_PTR (loc)->uid)
337 : : {
338 : : /* Reverse the insertion. */
339 : : new_elt_loc_list (CSELIB_VAL_PTR (loc), val->val_rtx);
340 : : return;
341 : : }
342 : :
343 : 3962836 : gcc_checking_assert (val->uid < CSELIB_VAL_PTR (loc)->uid);
344 : :
345 : 3962836 : if (CSELIB_VAL_PTR (loc)->locs)
346 : : {
347 : : /* Bring all locs from LOC to VAL. */
348 : 3024159 : for (el = CSELIB_VAL_PTR (loc)->locs; el->next; el = el->next)
349 : : {
350 : : /* Adjust values that have LOC as canonical so that VAL
351 : : becomes their canonical. */
352 : 14 : if (el->loc && GET_CODE (el->loc) == VALUE)
353 : : {
354 : 0 : gcc_checking_assert (CSELIB_VAL_PTR (el->loc)->locs->loc
355 : : == loc);
356 : 0 : CSELIB_VAL_PTR (el->loc)->locs->loc = val->val_rtx;
357 : : }
358 : : }
359 : 3024145 : el->next = val->locs;
360 : 3024145 : next = val->locs = CSELIB_VAL_PTR (loc)->locs;
361 : : }
362 : :
363 : 3962836 : if (CSELIB_VAL_PTR (loc)->addr_list)
364 : : {
365 : : /* Bring in addr_list into canonical node. */
366 : : struct elt_list *last = CSELIB_VAL_PTR (loc)->addr_list;
367 : 1 : while (last->next)
368 : : last = last->next;
369 : 1 : last->next = val->addr_list;
370 : 1 : val->addr_list = CSELIB_VAL_PTR (loc)->addr_list;
371 : 1 : CSELIB_VAL_PTR (loc)->addr_list = NULL;
372 : : }
373 : :
374 : 3962836 : if (CSELIB_VAL_PTR (loc)->next_containing_mem != NULL
375 : 0 : && val->next_containing_mem == NULL)
376 : : {
377 : : /* Add VAL to the containing_mem list after LOC. LOC will
378 : : be removed when we notice it doesn't contain any
379 : : MEMs. */
380 : 0 : val->next_containing_mem = CSELIB_VAL_PTR (loc)->next_containing_mem;
381 : 0 : CSELIB_VAL_PTR (loc)->next_containing_mem = val;
382 : : }
383 : :
384 : : /* Chain LOC back to VAL. */
385 : 3962836 : el = elt_loc_list_pool.allocate ();
386 : 3962836 : el->loc = val->val_rtx;
387 : 3962836 : el->setting_insn = cselib_current_insn;
388 : 3962836 : el->next = NULL;
389 : 3962836 : CSELIB_VAL_PTR (loc)->locs = el;
390 : : }
391 : :
392 : 720453261 : el = elt_loc_list_pool.allocate ();
393 : 720453261 : el->loc = loc;
394 : 720453261 : el->setting_insn = cselib_current_insn;
395 : 720453261 : el->next = next;
396 : 720453261 : val->locs = el;
397 : : }
398 : :
399 : : /* Promote loc L to a nondebug cselib_current_insn if L is marked as
400 : : originating from a debug insn, maintaining the debug values
401 : : count. */
402 : :
403 : : static inline void
404 : 1210505604 : promote_debug_loc (struct elt_loc_list *l)
405 : : {
406 : 1210505604 : if (l && l->setting_insn && DEBUG_INSN_P (l->setting_insn)
407 : 20836733 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
408 : : {
409 : 2570664 : n_debug_values--;
410 : 2570664 : l->setting_insn = cselib_current_insn;
411 : 2570664 : if (cselib_preserve_constants && l->next)
412 : : {
413 : 27650 : gcc_assert (l->next->setting_insn
414 : : && DEBUG_INSN_P (l->next->setting_insn)
415 : : && !l->next->next);
416 : 27650 : l->next->setting_insn = cselib_current_insn;
417 : : }
418 : : else
419 : 2543014 : gcc_assert (!l->next);
420 : : }
421 : 1210505604 : }
422 : :
423 : : /* The elt_list at *PL is no longer needed. Unchain it and free its
424 : : storage. */
425 : :
426 : : static inline void
427 : 79387627 : unchain_one_elt_list (struct elt_list **pl)
428 : : {
429 : 79387627 : struct elt_list *l = *pl;
430 : :
431 : 79387627 : *pl = l->next;
432 : 116158267 : elt_list_pool.remove (l);
433 : 42616987 : }
434 : :
435 : : /* Likewise for elt_loc_lists. */
436 : :
437 : : static void
438 : 223960983 : unchain_one_elt_loc_list (struct elt_loc_list **pl)
439 : : {
440 : 223960983 : struct elt_loc_list *l = *pl;
441 : :
442 : 223960983 : *pl = l->next;
443 : 0 : elt_loc_list_pool.remove (l);
444 : 38176639 : }
445 : :
446 : : /* Likewise for cselib_vals. This also frees the addr_list associated with
447 : : V. */
448 : :
449 : : static void
450 : 2641623 : unchain_one_value (cselib_val *v)
451 : : {
452 : 2660366 : while (v->addr_list)
453 : 18743 : unchain_one_elt_list (&v->addr_list);
454 : :
455 : 2641623 : cselib_val_pool.remove (v);
456 : 2641623 : }
457 : :
458 : : /* Remove all entries from the hash table. Also used during
459 : : initialization. */
460 : :
461 : : void
462 : 60700800 : cselib_clear_table (void)
463 : : {
464 : 60700800 : cselib_reset_table (1);
465 : 60700800 : }
466 : :
467 : : /* Return TRUE if V is a constant, a function invariant or a VALUE
468 : : equivalence; FALSE otherwise. */
469 : :
470 : : static bool
471 : 58053121 : invariant_or_equiv_p (cselib_val *v)
472 : : {
473 : 58053121 : struct elt_loc_list *l;
474 : :
475 : 58053121 : if (v == cfa_base_preserved_val)
476 : : return true;
477 : :
478 : : /* Keep VALUE equivalences around. */
479 : 80753693 : for (l = v->locs; l; l = l->next)
480 : 39175392 : if (GET_CODE (l->loc) == VALUE)
481 : : return true;
482 : :
483 : 41578301 : if (v->locs != NULL
484 : 22974798 : && v->locs->next == NULL)
485 : : {
486 : 22911018 : if (CONSTANT_P (v->locs->loc)
487 : 22911018 : && (GET_CODE (v->locs->loc) != CONST
488 : 177234 : || !references_value_p (v->locs->loc, 0)))
489 : 3549240 : return true;
490 : : /* Although a debug expr may be bound to different expressions,
491 : : we can preserve it as if it was constant, to get unification
492 : : and proper merging within var-tracking. */
493 : 19361778 : if (GET_CODE (v->locs->loc) == DEBUG_EXPR
494 : 17799054 : || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR
495 : 17303187 : || GET_CODE (v->locs->loc) == ENTRY_VALUE
496 : 17302973 : || GET_CODE (v->locs->loc) == DEBUG_PARAMETER_REF)
497 : : return true;
498 : :
499 : : /* (plus (value V) (const_int C)) is invariant iff V is invariant. */
500 : 17287147 : if (GET_CODE (v->locs->loc) == PLUS
501 : 10516801 : && CONST_INT_P (XEXP (v->locs->loc, 1))
502 : 9375450 : && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE
503 : 26038398 : && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v->locs->loc, 0))))
504 : : return true;
505 : : }
506 : :
507 : : return false;
508 : : }
509 : :
510 : : /* Remove from hash table all VALUEs except constants, function
511 : : invariants and VALUE equivalences. */
512 : :
513 : : int
514 : 44883207 : preserve_constants_and_equivs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
515 : : {
516 : 44883207 : cselib_val *v = *x;
517 : :
518 : 44883207 : if (invariant_or_equiv_p (v))
519 : : {
520 : 17680028 : cselib_hasher::key lookup = {
521 : 17680028 : GET_MODE (v->val_rtx), v->val_rtx, VOIDmode
522 : 17680028 : };
523 : 17680028 : cselib_val **slot
524 : 35360056 : = cselib_preserved_hash_table->find_slot_with_hash (&lookup,
525 : 17680028 : v->hash, INSERT);
526 : 17680028 : gcc_assert (!*slot);
527 : 17680028 : *slot = v;
528 : : }
529 : :
530 : 44883207 : cselib_hash_table->clear_slot (x);
531 : :
532 : 44883207 : return 1;
533 : : }
534 : :
535 : : /* Remove all entries from the hash table, arranging for the next
536 : : value to be numbered NUM. */
537 : :
538 : : void
539 : 100631635 : cselib_reset_table (unsigned int num)
540 : : {
541 : 100631635 : unsigned int i;
542 : :
543 : 100631635 : max_value_regs = 0;
544 : :
545 : 100631635 : if (cfa_base_preserved_val)
546 : : {
547 : 4418663 : unsigned int regno = cfa_base_preserved_regno;
548 : 4418663 : unsigned int new_used_regs = 0;
549 : 31433557 : for (i = 0; i < n_used_regs; i++)
550 : 27014894 : if (used_regs[i] == regno)
551 : : {
552 : 4418663 : new_used_regs = 1;
553 : 4418663 : continue;
554 : : }
555 : : else
556 : 22596231 : REG_VALUES (used_regs[i]) = 0;
557 : 4418663 : gcc_assert (new_used_regs == 1);
558 : 4418663 : n_used_regs = new_used_regs;
559 : 4418663 : used_regs[0] = regno;
560 : 4418663 : max_value_regs
561 : 4418663 : = hard_regno_nregs (regno,
562 : 4418663 : GET_MODE (cfa_base_preserved_val->locs->loc));
563 : :
564 : : /* If cfa_base is sp + const_int, need to preserve also the
565 : : SP_DERIVED_VALUE_P value. */
566 : 4418663 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs;
567 : 8837326 : l; l = l->next)
568 : 8837326 : if (GET_CODE (l->loc) == PLUS
569 : 4418663 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
570 : 4418663 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
571 : 13255989 : && CONST_INT_P (XEXP (l->loc, 1)))
572 : : {
573 : 4418663 : if (! invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (l->loc, 0))))
574 : : {
575 : 0 : rtx val = cfa_base_preserved_val->val_rtx;
576 : 0 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
577 : 0 : cselib_current_insn = l->setting_insn;
578 : 0 : new_elt_loc_list (CSELIB_VAL_PTR (XEXP (l->loc, 0)),
579 : 0 : plus_constant (Pmode, val,
580 : 0 : -UINTVAL (XEXP (l->loc, 1))));
581 : 0 : cselib_current_insn = save_cselib_current_insn;
582 : : }
583 : : break;
584 : : }
585 : : }
586 : : else
587 : : {
588 : 369856598 : for (i = 0; i < n_used_regs; i++)
589 : 273643626 : REG_VALUES (used_regs[i]) = 0;
590 : 96212972 : n_used_regs = 0;
591 : : }
592 : :
593 : 100631635 : if (cselib_preserve_constants)
594 : 49301870 : cselib_hash_table->traverse <void *, preserve_constants_and_equivs> (NULL);
595 : : else
596 : : {
597 : 96212972 : cselib_hash_table->empty ();
598 : 96212972 : gcc_checking_assert (!cselib_any_perm_equivs);
599 : : }
600 : :
601 : 100631635 : n_useless_values = 0;
602 : 100631635 : n_useless_debug_values = 0;
603 : 100631635 : n_debug_values = 0;
604 : :
605 : 100631635 : next_uid = num;
606 : :
607 : 100631635 : first_containing_mem = &dummy_val;
608 : 100631635 : }
609 : :
610 : : /* Return the number of the next value that will be generated. */
611 : :
612 : : unsigned int
613 : 4915000 : cselib_get_next_uid (void)
614 : : {
615 : 4915000 : return next_uid;
616 : : }
617 : :
618 : : /* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE,
619 : : INSERTing if requested. When X is part of the address of a MEM,
620 : : MEMMODE should specify the mode of the MEM. */
621 : :
622 : : static cselib_val **
623 : 712243216 : cselib_find_slot (machine_mode mode, rtx x, hashval_t hash,
624 : : enum insert_option insert, machine_mode memmode)
625 : : {
626 : 712243216 : cselib_val **slot = NULL;
627 : 712243216 : cselib_hasher::key lookup = { mode, x, memmode };
628 : 712243216 : if (cselib_preserve_constants)
629 : 160596267 : slot = cselib_preserved_hash_table->find_slot_with_hash (&lookup, hash,
630 : : NO_INSERT);
631 : 160596267 : if (!slot)
632 : 656644823 : slot = cselib_hash_table->find_slot_with_hash (&lookup, hash, insert);
633 : 712243216 : return slot;
634 : : }
635 : :
636 : : /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
637 : : only return true for values which point to a cselib_val whose value
638 : : element has been set to zero, which implies the cselib_val will be
639 : : removed. */
640 : :
641 : : bool
642 : 1247470243 : references_value_p (const_rtx x, int only_useless)
643 : : {
644 : 1247470243 : const enum rtx_code code = GET_CODE (x);
645 : 1247470243 : const char *fmt = GET_RTX_FORMAT (code);
646 : 1247470243 : int i, j;
647 : :
648 : 1247470243 : if (GET_CODE (x) == VALUE
649 : 1247470243 : && (! only_useless
650 : 441333314 : || (CSELIB_VAL_PTR (x)->locs == 0 && !PRESERVED_VALUE_P (x))))
651 : : return true;
652 : :
653 : 2849443102 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
654 : : {
655 : 1605000150 : if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
656 : : return true;
657 : 1603480701 : else if (fmt[i] == 'E')
658 : 44815752 : for (j = 0; j < XVECLEN (x, i); j++)
659 : 37147541 : if (references_value_p (XVECEXP (x, i, j), only_useless))
660 : : return true;
661 : : }
662 : :
663 : : return false;
664 : : }
665 : :
666 : : /* Return true if V is a useless VALUE and can be discarded as such. */
667 : :
668 : : static bool
669 : 1195574605 : cselib_useless_value_p (cselib_val *v)
670 : : {
671 : 1195574605 : return (v->locs == 0
672 : 79468166 : && !PRESERVED_VALUE_P (v->val_rtx)
673 : 1241707511 : && !SP_DERIVED_VALUE_P (v->val_rtx));
674 : : }
675 : :
676 : : /* For all locations found in X, delete locations that reference useless
677 : : values (i.e. values without any location). Called through
678 : : htab_traverse. */
679 : :
680 : : int
681 : 545839033 : discard_useless_locs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
682 : : {
683 : 545839033 : cselib_val *v = *x;
684 : 545839033 : struct elt_loc_list **p = &v->locs;
685 : 545839033 : bool had_locs = v->locs != NULL;
686 : 545839033 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
687 : :
688 : 1157332177 : while (*p)
689 : : {
690 : 611493144 : if (references_value_p ((*p)->loc, 1))
691 : 1405999 : unchain_one_elt_loc_list (p);
692 : : else
693 : 610087145 : p = &(*p)->next;
694 : : }
695 : :
696 : 545839033 : if (had_locs && cselib_useless_value_p (v))
697 : : {
698 : 1274691 : if (setting_insn && DEBUG_INSN_P (setting_insn))
699 : 2 : n_useless_debug_values++;
700 : : else
701 : 1274689 : n_useless_values++;
702 : 1274691 : values_became_useless = 1;
703 : : }
704 : 545839033 : return 1;
705 : : }
706 : :
707 : : /* If X is a value with no locations, remove it from the hashtable. */
708 : :
709 : : int
710 : 49286079 : discard_useless_values (cselib_val **x, void *info ATTRIBUTE_UNUSED)
711 : : {
712 : 49286079 : cselib_val *v = *x;
713 : :
714 : 49286079 : if (v->locs == 0 && cselib_useless_value_p (v))
715 : : {
716 : 2641623 : if (cselib_discard_hook)
717 : 518826 : cselib_discard_hook (v);
718 : :
719 : 2641623 : CSELIB_VAL_PTR (v->val_rtx) = NULL;
720 : 2641623 : cselib_hash_table->clear_slot (x);
721 : 2641623 : unchain_one_value (v);
722 : 2641623 : n_useless_values--;
723 : : }
724 : :
725 : 49286079 : return 1;
726 : : }
727 : :
728 : : /* Clean out useless values (i.e. those which no longer have locations
729 : : associated with them) from the hash table. */
730 : :
731 : : static void
732 : 4450345 : remove_useless_values (void)
733 : : {
734 : 4508845 : cselib_val **p, *v;
735 : :
736 : : /* First pass: eliminate locations that reference the value. That in
737 : : turn can make more values useless. */
738 : 4508845 : do
739 : : {
740 : 4508845 : values_became_useless = 0;
741 : 550347878 : cselib_hash_table->traverse <void *, discard_useless_locs> (NULL);
742 : : }
743 : 4508845 : while (values_became_useless);
744 : :
745 : : /* Second pass: actually remove the values. */
746 : :
747 : 4450345 : p = &first_containing_mem;
748 : 4582655 : for (v = *p; v != &dummy_val; v = v->next_containing_mem)
749 : 132310 : if (v->locs && v == canonical_cselib_val (v))
750 : : {
751 : 129935 : *p = v;
752 : 129935 : p = &(*p)->next_containing_mem;
753 : : }
754 : 4450345 : *p = &dummy_val;
755 : :
756 : 4450345 : if (cselib_preserve_constants)
757 : 4418663 : cselib_preserved_hash_table->traverse <void *,
758 : 4418663 : discard_useless_locs> (NULL);
759 : 4450345 : gcc_assert (!values_became_useless);
760 : :
761 : 4450345 : n_useless_values += n_useless_debug_values;
762 : 4450345 : n_debug_values -= n_useless_debug_values;
763 : 4450345 : n_useless_debug_values = 0;
764 : :
765 : 53736424 : cselib_hash_table->traverse <void *, discard_useless_values> (NULL);
766 : :
767 : 4450345 : gcc_assert (!n_useless_values);
768 : 4450345 : }
769 : :
770 : : /* Arrange for a value to not be removed from the hash table even if
771 : : it becomes useless. */
772 : :
773 : : void
774 : 45534291 : cselib_preserve_value (cselib_val *v)
775 : : {
776 : 45534291 : PRESERVED_VALUE_P (v->val_rtx) = 1;
777 : 45534291 : }
778 : :
779 : : /* Test whether a value is preserved. */
780 : :
781 : : bool
782 : 263765646 : cselib_preserved_value_p (cselib_val *v)
783 : : {
784 : 263765646 : return PRESERVED_VALUE_P (v->val_rtx);
785 : : }
786 : :
787 : : /* Arrange for a REG value to be assumed constant through the whole function,
788 : : never invalidated and preserved across cselib_reset_table calls. */
789 : :
790 : : void
791 : 992151 : cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)
792 : : {
793 : 992151 : if (cselib_preserve_constants
794 : 992151 : && v->locs
795 : 992151 : && REG_P (v->locs->loc))
796 : : {
797 : 496634 : cfa_base_preserved_val = v;
798 : 496634 : cfa_base_preserved_regno = regno;
799 : : }
800 : 992151 : }
801 : :
802 : : /* Clean all non-constant expressions in the hash table, but retain
803 : : their values. */
804 : :
805 : : void
806 : 4418663 : cselib_preserve_only_values (void)
807 : : {
808 : 4418663 : int i;
809 : :
810 : 410935659 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
811 : 406516996 : cselib_invalidate_regno (i, reg_raw_mode[i]);
812 : :
813 : 4418663 : cselib_invalidate_mem (callmem[0]);
814 : :
815 : 4418663 : remove_useless_values ();
816 : :
817 : 4418663 : gcc_assert (first_containing_mem == &dummy_val);
818 : 4418663 : }
819 : :
820 : : /* Arrange for a value to be marked as based on stack pointer
821 : : for find_base_term purposes. */
822 : :
823 : : void
824 : 1902542 : cselib_set_value_sp_based (cselib_val *v)
825 : : {
826 : 1902542 : SP_BASED_VALUE_P (v->val_rtx) = 1;
827 : 1902542 : }
828 : :
829 : : /* Test whether a value is based on stack pointer for
830 : : find_base_term purposes. */
831 : :
832 : : bool
833 : 841105697 : cselib_sp_based_value_p (cselib_val *v)
834 : : {
835 : 841105697 : return SP_BASED_VALUE_P (v->val_rtx);
836 : : }
837 : :
838 : : /* Return the mode in which a register was last set. If X is not a
839 : : register, return its mode. If the mode in which the register was
840 : : set is not known, or the value was already clobbered, return
841 : : VOIDmode. */
842 : :
843 : : machine_mode
844 : 112261075 : cselib_reg_set_mode (const_rtx x)
845 : : {
846 : 112261075 : if (!REG_P (x))
847 : 33582815 : return GET_MODE (x);
848 : :
849 : 78678260 : if (REG_VALUES (REGNO (x)) == NULL
850 : 78678260 : || REG_VALUES (REGNO (x))->elt == NULL)
851 : : return VOIDmode;
852 : :
853 : 24078181 : return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
854 : : }
855 : :
856 : : /* If x is a PLUS or an autoinc operation, expand the operation,
857 : : storing the offset, if any, in *OFF. */
858 : :
859 : : static rtx
860 : 1477271572 : autoinc_split (rtx x, rtx *off, machine_mode memmode)
861 : : {
862 : 1477271572 : switch (GET_CODE (x))
863 : : {
864 : 810957118 : case PLUS:
865 : 810957118 : *off = XEXP (x, 1);
866 : 810957118 : x = XEXP (x, 0);
867 : 810957118 : break;
868 : :
869 : 12539665 : case PRE_DEC:
870 : 12539665 : if (memmode == VOIDmode)
871 : : return x;
872 : :
873 : 25079330 : *off = gen_int_mode (-GET_MODE_SIZE (memmode), GET_MODE (x));
874 : 12539665 : x = XEXP (x, 0);
875 : 12539665 : break;
876 : :
877 : 0 : case PRE_INC:
878 : 0 : if (memmode == VOIDmode)
879 : : return x;
880 : :
881 : 0 : *off = gen_int_mode (GET_MODE_SIZE (memmode), GET_MODE (x));
882 : 0 : x = XEXP (x, 0);
883 : 0 : break;
884 : :
885 : 1631779 : case PRE_MODIFY:
886 : 1631779 : x = XEXP (x, 1);
887 : 1631779 : break;
888 : :
889 : 1838750 : case POST_DEC:
890 : 1838750 : case POST_INC:
891 : 1838750 : case POST_MODIFY:
892 : 1838750 : x = XEXP (x, 0);
893 : 1838750 : break;
894 : :
895 : : default:
896 : : break;
897 : : }
898 : :
899 : 1477271572 : if (GET_MODE (x) == Pmode
900 : 1427282394 : && (REG_P (x) || MEM_P (x) || GET_CODE (x) == VALUE)
901 : 2292533368 : && (*off == NULL_RTX || CONST_INT_P (*off)))
902 : : {
903 : 810772533 : cselib_val *e;
904 : 810772533 : if (GET_CODE (x) == VALUE)
905 : 520323293 : e = CSELIB_VAL_PTR (x);
906 : : else
907 : 290449240 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
908 : 810772533 : if (e)
909 : : {
910 : 801693514 : if (SP_DERIVED_VALUE_P (e->val_rtx)
911 : 801693514 : && (*off == NULL_RTX || *off == const0_rtx))
912 : : {
913 : 65720 : *off = NULL_RTX;
914 : 65720 : return e->val_rtx;
915 : : }
916 : 1757184152 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
917 : 1383413428 : if (GET_CODE (l->loc) == PLUS
918 : 594903943 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
919 : 594074906 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
920 : 1811272234 : && CONST_INT_P (XEXP (l->loc, 1)))
921 : : {
922 : 427857070 : if (*off == NULL_RTX)
923 : 1487325 : *off = XEXP (l->loc, 1);
924 : : else
925 : 426369745 : *off = plus_constant (Pmode, *off,
926 : 426369745 : INTVAL (XEXP (l->loc, 1)));
927 : 427857070 : if (*off == const0_rtx)
928 : 264337432 : *off = NULL_RTX;
929 : 427857070 : return XEXP (l->loc, 0);
930 : : }
931 : : }
932 : : }
933 : : return x;
934 : : }
935 : :
936 : : /* Return true if we can prove that X and Y contain the same value,
937 : : taking our gathered information into account. MEMMODE holds the
938 : : mode of the enclosing MEM, if any, as required to deal with autoinc
939 : : addressing modes. If X and Y are not (known to be) part of
940 : : addresses, MEMMODE should be VOIDmode. */
941 : :
942 : : bool
943 : 1205048214 : rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth)
944 : : {
945 : 1588668499 : enum rtx_code code;
946 : 1588668499 : const char *fmt;
947 : 1588668499 : int i;
948 : :
949 : 1588668499 : if (REG_P (x) || MEM_P (x))
950 : : {
951 : 148650764 : cselib_val *e = cselib_lookup (x, GET_MODE (x), 0, memmode);
952 : :
953 : 148650764 : if (e)
954 : 125915020 : x = e->val_rtx;
955 : : }
956 : :
957 : 1588668499 : if (REG_P (y) || MEM_P (y))
958 : : {
959 : 138673504 : cselib_val *e = cselib_lookup (y, GET_MODE (y), 0, memmode);
960 : :
961 : 138673504 : if (e)
962 : 126803205 : y = e->val_rtx;
963 : : }
964 : :
965 : 1588668499 : if (x == y)
966 : : return true;
967 : :
968 : 1266462213 : if (GET_CODE (x) == VALUE)
969 : : {
970 : 433913449 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (x));
971 : 433913449 : struct elt_loc_list *l;
972 : :
973 : 433913449 : if (GET_CODE (y) == VALUE)
974 : 30560979 : return e == canonical_cselib_val (CSELIB_VAL_PTR (y));
975 : :
976 : 403352470 : if ((SP_DERIVED_VALUE_P (x)
977 : 149059727 : || SP_DERIVED_VALUE_P (e->val_rtx))
978 : 447062187 : && GET_MODE (y) == Pmode)
979 : : {
980 : 256598438 : rtx yoff = NULL;
981 : 256598438 : rtx yr = autoinc_split (y, &yoff, memmode);
982 : 256598438 : if ((yr == x || yr == e->val_rtx) && yoff == NULL_RTX)
983 : 52810 : return true;
984 : : }
985 : :
986 : 403299660 : if (depth == 128)
987 : : return false;
988 : :
989 : 1245489556 : for (l = e->locs; l; l = l->next)
990 : : {
991 : 865171952 : rtx t = l->loc;
992 : :
993 : : /* Avoid infinite recursion. We know we have the canonical
994 : : value, so we can just skip any values in the equivalence
995 : : list. */
996 : 865171952 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
997 : 514212247 : continue;
998 : 350959705 : else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1))
999 : : return true;
1000 : : }
1001 : :
1002 : : return false;
1003 : : }
1004 : 832548764 : else if (GET_CODE (y) == VALUE)
1005 : : {
1006 : 45681222 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y));
1007 : 45681222 : struct elt_loc_list *l;
1008 : :
1009 : 45681222 : if ((SP_DERIVED_VALUE_P (y)
1010 : 43497694 : || SP_DERIVED_VALUE_P (e->val_rtx))
1011 : 46091501 : && GET_MODE (x) == Pmode)
1012 : : {
1013 : 2111265 : rtx xoff = NULL;
1014 : 2111265 : rtx xr = autoinc_split (x, &xoff, memmode);
1015 : 2111265 : if ((xr == y || xr == e->val_rtx) && xoff == NULL_RTX)
1016 : 168 : return true;
1017 : : }
1018 : :
1019 : 45681054 : if (depth == 128)
1020 : : return false;
1021 : :
1022 : 109909037 : for (l = e->locs; l; l = l->next)
1023 : : {
1024 : 64303886 : rtx t = l->loc;
1025 : :
1026 : 64303886 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
1027 : 55055708 : continue;
1028 : 9248178 : else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1))
1029 : : return true;
1030 : : }
1031 : :
1032 : : return false;
1033 : : }
1034 : :
1035 : 786867542 : if (GET_MODE (x) != GET_MODE (y))
1036 : : return false;
1037 : :
1038 : 747649733 : if (GET_CODE (x) != GET_CODE (y)
1039 : 747649733 : || (GET_CODE (x) == PLUS
1040 : 340003921 : && GET_MODE (x) == Pmode
1041 : 243161669 : && CONST_INT_P (XEXP (x, 1))
1042 : 232927617 : && CONST_INT_P (XEXP (y, 1))))
1043 : : {
1044 : 600458270 : rtx xorig = x, yorig = y;
1045 : 600458270 : rtx xoff = NULL, yoff = NULL;
1046 : :
1047 : 600458270 : x = autoinc_split (x, &xoff, memmode);
1048 : 600458270 : y = autoinc_split (y, &yoff, memmode);
1049 : :
1050 : : /* Don't recurse if nothing changed. */
1051 : 600458270 : if (x != xorig || y != yorig)
1052 : : {
1053 : 560739119 : if (!xoff != !yoff)
1054 : 217508661 : return false;
1055 : :
1056 : 481365783 : if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth))
1057 : : return false;
1058 : :
1059 : 382949609 : return rtx_equal_for_cselib_1 (x, y, memmode, depth);
1060 : : }
1061 : :
1062 : 39719151 : if (GET_CODE (xorig) != GET_CODE (yorig))
1063 : : return false;
1064 : : }
1065 : :
1066 : : /* These won't be handled correctly by the code below. */
1067 : 147191463 : switch (GET_CODE (x))
1068 : : {
1069 : : CASE_CONST_UNIQUE:
1070 : : case DEBUG_EXPR:
1071 : : return false;
1072 : :
1073 : : case CONST_VECTOR:
1074 : : if (!same_vector_encodings_p (x, y))
1075 : : return false;
1076 : : break;
1077 : :
1078 : 2301664 : case DEBUG_IMPLICIT_PTR:
1079 : 2301664 : return DEBUG_IMPLICIT_PTR_DECL (x)
1080 : 2301664 : == DEBUG_IMPLICIT_PTR_DECL (y);
1081 : :
1082 : 5650 : case DEBUG_PARAMETER_REF:
1083 : 5650 : return DEBUG_PARAMETER_REF_DECL (x)
1084 : 5650 : == DEBUG_PARAMETER_REF_DECL (y);
1085 : :
1086 : 320557 : case ENTRY_VALUE:
1087 : : /* ENTRY_VALUEs are function invariant, it is thus undesirable to
1088 : : use rtx_equal_for_cselib_1 to compare the operands. */
1089 : 320557 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1090 : :
1091 : 336 : case LABEL_REF:
1092 : 336 : return label_ref_label (x) == label_ref_label (y);
1093 : :
1094 : 201 : case REG:
1095 : 201 : return REGNO (x) == REGNO (y);
1096 : :
1097 : 670676 : case MEM:
1098 : : /* We have to compare any autoinc operations in the addresses
1099 : : using this MEM's mode. */
1100 : 670676 : return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x),
1101 : 670676 : depth);
1102 : :
1103 : : default:
1104 : : break;
1105 : : }
1106 : :
1107 : 38825739 : code = GET_CODE (x);
1108 : 38825739 : fmt = GET_RTX_FORMAT (code);
1109 : :
1110 : 66970022 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1111 : : {
1112 : 56203640 : int j;
1113 : :
1114 : 56203640 : switch (fmt[i])
1115 : : {
1116 : 0 : case 'w':
1117 : 0 : if (XWINT (x, i) != XWINT (y, i))
1118 : : return false;
1119 : : break;
1120 : :
1121 : 567971 : case 'n':
1122 : 567971 : case 'i':
1123 : 567971 : if (XINT (x, i) != XINT (y, i))
1124 : : return false;
1125 : : break;
1126 : :
1127 : 5683 : case 'L':
1128 : 5683 : if (XLOC (x, i) != XLOC (y, i))
1129 : : return false;
1130 : : break;
1131 : :
1132 : 603830 : case 'p':
1133 : 603830 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1134 : : return false;
1135 : : break;
1136 : :
1137 : 1452776 : case 'V':
1138 : 1452776 : case 'E':
1139 : : /* Two vectors must have the same length. */
1140 : 1452776 : if (XVECLEN (x, i) != XVECLEN (y, i))
1141 : : return false;
1142 : :
1143 : : /* And the corresponding elements must match. */
1144 : 3682018 : for (j = 0; j < XVECLEN (x, i); j++)
1145 : 3089206 : if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j),
1146 : 3089206 : XVECEXP (y, i, j), memmode, depth))
1147 : : return false;
1148 : : break;
1149 : :
1150 : 43004449 : case 'e':
1151 : 43004449 : if (i == 1
1152 : 27558976 : && targetm.commutative_p (x, UNKNOWN)
1153 : 19896308 : && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode,
1154 : : depth)
1155 : 43325213 : && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode,
1156 : : depth))
1157 : : return true;
1158 : 42780807 : if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode,
1159 : : depth))
1160 : : return false;
1161 : : break;
1162 : :
1163 : 5375163 : case 'S':
1164 : 5375163 : case 's':
1165 : 5375163 : if (strcmp (XSTR (x, i), XSTR (y, i)))
1166 : : return false;
1167 : : break;
1168 : :
1169 : : case 'u':
1170 : : /* These are just backpointers, so they don't matter. */
1171 : : break;
1172 : :
1173 : : case '0':
1174 : : case 't':
1175 : : break;
1176 : :
1177 : : /* It is believed that rtx's at this level will never
1178 : : contain anything but integers and other rtx's,
1179 : : except for within LABEL_REFs and SYMBOL_REFs. */
1180 : 0 : default:
1181 : 0 : gcc_unreachable ();
1182 : : }
1183 : : }
1184 : : return true;
1185 : : }
1186 : :
1187 : : /* Wrapper for rtx_equal_for_cselib_p to determine whether a SET is
1188 : : truly redundant, taking into account aliasing information. */
1189 : : bool
1190 : 112261075 : cselib_redundant_set_p (rtx set)
1191 : : {
1192 : 112261075 : gcc_assert (GET_CODE (set) == SET);
1193 : 112261075 : rtx dest = SET_DEST (set);
1194 : 112261075 : if (cselib_reg_set_mode (dest) != GET_MODE (dest))
1195 : : return false;
1196 : :
1197 : 53527333 : if (!rtx_equal_for_cselib_p (dest, SET_SRC (set)))
1198 : : return false;
1199 : :
1200 : 418882 : while (GET_CODE (dest) == SUBREG
1201 : 418882 : || GET_CODE (dest) == ZERO_EXTRACT
1202 : 837764 : || GET_CODE (dest) == STRICT_LOW_PART)
1203 : 0 : dest = XEXP (dest, 0);
1204 : :
1205 : 418882 : if (!flag_strict_aliasing || !MEM_P (dest))
1206 : : return true;
1207 : :
1208 : : /* For a store we need to check that suppressing it will not change
1209 : : the effective alias set. */
1210 : 35030 : rtx dest_addr = XEXP (dest, 0);
1211 : :
1212 : : /* Lookup the equivalents to the original dest (rather than just the
1213 : : MEM). */
1214 : 70060 : cselib_val *src_val = cselib_lookup (SET_DEST (set),
1215 : 35030 : GET_MODE (SET_DEST (set)),
1216 : : 0, VOIDmode);
1217 : :
1218 : 35030 : if (src_val)
1219 : : {
1220 : : /* Walk the list of source equivalents to find the MEM accessing
1221 : : the same location. */
1222 : 75000 : for (elt_loc_list *l = src_val->locs; l; l = l->next)
1223 : : {
1224 : 75000 : rtx src_equiv = l->loc;
1225 : 75000 : while (GET_CODE (src_equiv) == SUBREG
1226 : 75000 : || GET_CODE (src_equiv) == ZERO_EXTRACT
1227 : 150006 : || GET_CODE (src_equiv) == STRICT_LOW_PART)
1228 : 6 : src_equiv = XEXP (src_equiv, 0);
1229 : :
1230 : 75000 : if (MEM_P (src_equiv))
1231 : : {
1232 : : /* Match the MEMs by comparing the addresses. We can
1233 : : only remove the later store if the earlier aliases at
1234 : : least all the accesses of the later one. */
1235 : 40018 : if (rtx_equal_for_cselib_1 (dest_addr, XEXP (src_equiv, 0),
1236 : 40018 : GET_MODE (dest), 0))
1237 : 34968 : return mems_same_for_tbaa_p (src_equiv, dest);
1238 : : }
1239 : : }
1240 : : }
1241 : :
1242 : : /* We failed to find a recorded value in the cselib history, so try
1243 : : the source of this set; this catches cases such as *p = *q when p
1244 : : and q have the same value. */
1245 : 62 : rtx src = SET_SRC (set);
1246 : 62 : while (GET_CODE (src) == SUBREG)
1247 : 0 : src = XEXP (src, 0);
1248 : :
1249 : 62 : if (MEM_P (src)
1250 : 62 : && rtx_equal_for_cselib_1 (dest_addr, XEXP (src, 0), GET_MODE (dest), 0))
1251 : 62 : return mems_same_for_tbaa_p (src, dest);
1252 : :
1253 : : return false;
1254 : : }
1255 : :
1256 : : /* Helper function for cselib_hash_rtx. Arguments like for cselib_hash_rtx,
1257 : : except that it hashes (plus:P x c). */
1258 : :
1259 : : static hashval_t
1260 : 282370150 : cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create,
1261 : : machine_mode memmode)
1262 : : {
1263 : 282370150 : cselib_val *e = cselib_lookup (x, GET_MODE (x), create, memmode);
1264 : 282370150 : if (! e)
1265 : : return 0;
1266 : :
1267 : 269234480 : if (! SP_DERIVED_VALUE_P (e->val_rtx))
1268 : 433184673 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
1269 : 351734172 : if (GET_CODE (l->loc) == PLUS
1270 : 129547995 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
1271 : 129059323 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
1272 : 474782613 : && CONST_INT_P (XEXP (l->loc, 1)))
1273 : : {
1274 : 123046685 : e = CSELIB_VAL_PTR (XEXP (l->loc, 0));
1275 : 123046685 : c = trunc_int_for_mode (c + UINTVAL (XEXP (l->loc, 1)), Pmode);
1276 : 123046685 : break;
1277 : : }
1278 : 269234480 : if (c == 0)
1279 : 8021375 : return e->hash;
1280 : :
1281 : 261213105 : inchash::hash hash;
1282 : 261213105 : hash.add_int (PLUS);
1283 : 261213105 : hash.add_int (GET_MODE (x));
1284 : 261213105 : hash.merge_hash (e->hash);
1285 : 261213105 : hash.add_hwi (c);
1286 : :
1287 : 261213105 : return hash.end () ? hash.end () : 1 + (unsigned int) PLUS;
1288 : : }
1289 : :
1290 : : /* Hash an rtx. Return 0 if we couldn't hash the rtx.
1291 : : For registers and memory locations, we look up their cselib_val structure
1292 : : and return its VALUE element.
1293 : : Possible reasons for return 0 are: the object is volatile, or we couldn't
1294 : : find a register or memory location in the table and CREATE is zero. If
1295 : : CREATE is nonzero, table elts are created for regs and mem.
1296 : : N.B. this hash function returns the same hash value for RTXes that
1297 : : differ only in the order of operands, thus it is suitable for comparisons
1298 : : that take commutativity into account.
1299 : : If we wanted to also support associative rules, we'd have to use a different
1300 : : strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
1301 : : MEMMODE indicates the mode of an enclosing MEM, and it's only
1302 : : used to compute autoinc values.
1303 : : We used to have a MODE argument for hashing for CONST_INTs, but that
1304 : : didn't make sense, since it caused spurious hash differences between
1305 : : (set (reg:SI 1) (const_int))
1306 : : (plus:SI (reg:SI 2) (reg:SI 1))
1307 : : and
1308 : : (plus:SI (reg:SI 2) (const_int))
1309 : : If the mode is important in any context, it must be checked specifically
1310 : : in a comparison anyway, since relying on hash differences is unsafe. */
1311 : :
1312 : : static hashval_t
1313 : 979761822 : cselib_hash_rtx (rtx x, int create, machine_mode memmode)
1314 : : {
1315 : 979761822 : cselib_val *e;
1316 : 979761822 : poly_int64 offset;
1317 : 979761822 : int i, j;
1318 : 979761822 : enum rtx_code code;
1319 : 979761822 : const char *fmt;
1320 : 979761822 : inchash::hash hash;
1321 : :
1322 : 979761822 : code = GET_CODE (x);
1323 : 979761822 : hash.add_int (code);
1324 : 979761822 : hash.add_int (GET_MODE (x));
1325 : :
1326 : 979761822 : switch (code)
1327 : : {
1328 : 477302 : case VALUE:
1329 : 477302 : e = CSELIB_VAL_PTR (x);
1330 : 477302 : return e->hash;
1331 : :
1332 : 212442398 : case MEM:
1333 : 212442398 : case REG:
1334 : 212442398 : e = cselib_lookup (x, GET_MODE (x), create, memmode);
1335 : 212442398 : if (! e)
1336 : : return 0;
1337 : :
1338 : 188643225 : return e->hash;
1339 : :
1340 : 13212167 : case DEBUG_EXPR:
1341 : 13212167 : hash.add_int (DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)));
1342 : 13212167 : return hash.end () ? hash.end() : (unsigned int) DEBUG_EXPR;
1343 : :
1344 : 2977740 : case DEBUG_IMPLICIT_PTR:
1345 : 2977740 : hash.add_int (DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)));
1346 : 2977740 : return hash.end () ? hash.end () : (unsigned int) DEBUG_IMPLICIT_PTR;
1347 : :
1348 : 36998 : case DEBUG_PARAMETER_REF:
1349 : 36998 : hash.add_int (DECL_UID (DEBUG_PARAMETER_REF_DECL (x)));
1350 : 36998 : return hash.end () ? hash.end () : (unsigned int) DEBUG_PARAMETER_REF;
1351 : :
1352 : 1418361 : case ENTRY_VALUE:
1353 : : /* ENTRY_VALUEs are function invariant, thus try to avoid
1354 : : recursing on argument if ENTRY_VALUE is one of the
1355 : : forms emitted by expand_debug_expr, otherwise
1356 : : ENTRY_VALUE hash would depend on the current value
1357 : : in some register or memory. */
1358 : 1418361 : if (REG_P (ENTRY_VALUE_EXP (x)))
1359 : 1400720 : hash.add_int ((unsigned int) REG
1360 : 1400720 : + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
1361 : 1400720 : + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)));
1362 : 17641 : else if (MEM_P (ENTRY_VALUE_EXP (x))
1363 : 17641 : && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0)))
1364 : 17641 : hash.add_int ((unsigned int) MEM
1365 : 17641 : + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
1366 : 17641 : + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0)));
1367 : : else
1368 : 0 : hash.add_int (cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode));
1369 : 1418361 : return hash.end () ? hash.end () : (unsigned int) ENTRY_VALUE;
1370 : :
1371 : 172862601 : case CONST_INT:
1372 : 172862601 : hash.add_hwi (UINTVAL (x));
1373 : 172862601 : return hash.end () ? hash.end () : (unsigned int) CONST_INT;
1374 : :
1375 : : case CONST_WIDE_INT:
1376 : 3232392 : for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
1377 : 2156885 : hash.add_hwi (CONST_WIDE_INT_ELT (x, i));
1378 : 1075507 : return hash.end () ? hash.end () : (unsigned int) CONST_WIDE_INT;
1379 : :
1380 : : case CONST_POLY_INT:
1381 : : {
1382 : 0 : for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i)
1383 : 0 : hash.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]);
1384 : 0 : return hash.end () ? hash.end () : (unsigned int) CONST_POLY_INT;
1385 : : }
1386 : :
1387 : 3613926 : case CONST_DOUBLE:
1388 : : /* This is like the general case, except that it only counts
1389 : : the integers representing the constant. */
1390 : 3613926 : if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
1391 : : {
1392 : : hash.add_hwi (CONST_DOUBLE_LOW (x));
1393 : : hash.add_hwi (CONST_DOUBLE_HIGH (x));
1394 : : }
1395 : : else
1396 : 3613926 : hash.merge_hash (real_hash (CONST_DOUBLE_REAL_VALUE (x)));
1397 : 3613926 : return hash.end () ? hash.end () : (unsigned int) CONST_DOUBLE;
1398 : :
1399 : 0 : case CONST_FIXED:
1400 : 0 : hash.merge_hash (fixed_hash (CONST_FIXED_VALUE (x)));
1401 : 0 : return hash.end () ? hash.end () : (unsigned int) CONST_FIXED;
1402 : :
1403 : 2967879 : case CONST_VECTOR:
1404 : 2967879 : {
1405 : 2967879 : int units;
1406 : 2967879 : rtx elt;
1407 : :
1408 : 2967879 : units = const_vector_encoded_nelts (x);
1409 : :
1410 : 7845664 : for (i = 0; i < units; ++i)
1411 : : {
1412 : 4877785 : elt = CONST_VECTOR_ENCODED_ELT (x, i);
1413 : 4877785 : hash.merge_hash (cselib_hash_rtx (elt, 0, memmode));
1414 : : }
1415 : :
1416 : 2967879 : return hash.end () ? hash.end () : (unsigned int) CONST_VECTOR;
1417 : : }
1418 : :
1419 : : /* Assume there is only one rtx object for any given label. */
1420 : 152883 : case LABEL_REF:
1421 : : /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1422 : : differences and differences between each stage's debugging dumps. */
1423 : 152883 : hash.add_int (CODE_LABEL_NUMBER (label_ref_label (x)));
1424 : 152883 : return hash.end () ? hash.end () : (unsigned int) LABEL_REF;
1425 : :
1426 : 63749064 : case SYMBOL_REF:
1427 : 63749064 : {
1428 : : /* Don't hash on the symbol's address to avoid bootstrap differences.
1429 : : Different hash values may cause expressions to be recorded in
1430 : : different orders and thus different registers to be used in the
1431 : : final assembler. This also avoids differences in the dump files
1432 : : between various stages. */
1433 : 63749064 : const char *p = (const char *) XSTR (x, 0);
1434 : :
1435 : 63749064 : if (*p)
1436 : 63749064 : hash.add (p, strlen (p));
1437 : :
1438 : 63749064 : return hash.end () ? hash.end () : (unsigned int) SYMBOL_REF;
1439 : : }
1440 : :
1441 : 17350867 : case PRE_DEC:
1442 : 17350867 : case PRE_INC:
1443 : 17350867 : {
1444 : : /* We can't compute these without knowing the MEM mode. */
1445 : 17350867 : gcc_assert (memmode != VOIDmode);
1446 : 34701734 : offset = GET_MODE_SIZE (memmode);
1447 : 17350867 : if (code == PRE_DEC)
1448 : 17350867 : offset = -offset;
1449 : : /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1450 : : like (mem:MEMMODE (plus (reg) (const_int I))). */
1451 : 17350867 : if (GET_MODE (x) == Pmode
1452 : 17350867 : && (REG_P (XEXP (x, 0))
1453 : : || MEM_P (XEXP (x, 0))
1454 : : || GET_CODE (XEXP (x, 0)) == VALUE))
1455 : : {
1456 : 17350867 : HOST_WIDE_INT c;
1457 : 17350867 : if (offset.is_constant (&c))
1458 : 17350867 : return cselib_hash_plus_const_int (XEXP (x, 0),
1459 : : trunc_int_for_mode (c, Pmode),
1460 : : create, memmode);
1461 : : }
1462 : :
1463 : 0 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1464 : 0 : if (tem_hash == 0)
1465 : : return 0;
1466 : 0 : hash.merge_hash (tem_hash);
1467 : 0 : tem_hash = cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)),
1468 : : create, memmode);
1469 : 0 : if (tem_hash == 0)
1470 : : return 0;
1471 : 0 : hash.merge_hash (tem_hash);
1472 : 0 : return hash.end () ? hash.end () : 1 + (unsigned) PLUS;
1473 : : }
1474 : :
1475 : 497097 : case PRE_MODIFY:
1476 : 497097 : {
1477 : 497097 : gcc_assert (memmode != VOIDmode);
1478 : 497097 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1479 : 497097 : if (tem_hash == 0)
1480 : : return 0;
1481 : 490445 : hash.merge_hash (tem_hash);
1482 : 490445 : return hash.end () ? hash.end () : 1 + (unsigned) PRE_MODIFY;
1483 : : }
1484 : :
1485 : 1791623 : case POST_DEC:
1486 : 1791623 : case POST_INC:
1487 : 1791623 : case POST_MODIFY:
1488 : 1791623 : {
1489 : 1791623 : gcc_assert (memmode != VOIDmode);
1490 : 1791623 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1491 : 1791623 : if (tem_hash == 0)
1492 : : return 0;
1493 : 1791623 : hash.merge_hash (tem_hash);
1494 : 1791623 : return hash.end () ? hash.end () : 1 + (unsigned) code;
1495 : : }
1496 : :
1497 : : case PC:
1498 : : case CALL:
1499 : : case UNSPEC_VOLATILE:
1500 : : return 0;
1501 : :
1502 : 434333 : case ASM_OPERANDS:
1503 : 434333 : if (MEM_VOLATILE_P (x))
1504 : : return 0;
1505 : :
1506 : : break;
1507 : :
1508 : 315277101 : case PLUS:
1509 : 315277101 : if (GET_MODE (x) == Pmode
1510 : 304017640 : && (REG_P (XEXP (x, 0))
1511 : : || MEM_P (XEXP (x, 0))
1512 : : || GET_CODE (XEXP (x, 0)) == VALUE)
1513 : 596465154 : && CONST_INT_P (XEXP (x, 1)))
1514 : 265019283 : return cselib_hash_plus_const_int (XEXP (x, 0), INTVAL (XEXP (x, 1)),
1515 : 265019283 : create, memmode);
1516 : : break;
1517 : :
1518 : : default:
1519 : : break;
1520 : : }
1521 : :
1522 : 204959681 : i = GET_RTX_LENGTH (code) - 1;
1523 : 204959681 : fmt = GET_RTX_FORMAT (code);
1524 : :
1525 : 204959681 : if (COMMUTATIVE_P (x))
1526 : : {
1527 : 76029871 : gcc_assert (i == 1 && fmt[0] == 'e' && fmt[1] == 'e');
1528 : 76029871 : hashval_t tem1_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1529 : 76029871 : if (tem1_hash == 0)
1530 : : return 0;
1531 : 70861495 : hashval_t tem0_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1532 : 70861495 : if (tem0_hash == 0)
1533 : : return 0;
1534 : 67268667 : hash.add_commutative (tem0_hash, tem1_hash);
1535 : 67268667 : return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
1536 : : }
1537 : :
1538 : 339460103 : for (; i >= 0; i--)
1539 : : {
1540 : 228370394 : switch (fmt[i])
1541 : : {
1542 : 207952363 : case 'e':
1543 : 207952363 : {
1544 : 207952363 : rtx tem = XEXP (x, i);
1545 : 207952363 : hashval_t tem_hash = cselib_hash_rtx (tem, create, memmode);
1546 : 207952363 : if (tem_hash == 0)
1547 : : return 0;
1548 : 191009680 : hash.merge_hash (tem_hash);
1549 : : }
1550 : 191009680 : break;
1551 : : case 'E':
1552 : 25671754 : for (j = 0; j < XVECLEN (x, i); j++)
1553 : : {
1554 : 18077881 : hashval_t tem_hash
1555 : 18077881 : = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode);
1556 : 18077881 : if (tem_hash == 0)
1557 : : return 0;
1558 : 17180463 : hash.merge_hash (tem_hash);
1559 : : }
1560 : : break;
1561 : :
1562 : 543750 : case 's':
1563 : 543750 : {
1564 : 543750 : const char *p = (const char *) XSTR (x, i);
1565 : :
1566 : 543750 : if (p && *p)
1567 : 509860 : hash.add (p, strlen (p));
1568 : : break;
1569 : : }
1570 : :
1571 : 5164372 : case 'i':
1572 : 5164372 : hash.add_hwi (XINT (x, i));
1573 : 5164372 : break;
1574 : :
1575 : 241913 : case 'L':
1576 : 241913 : hash.add_hwi (XLOC (x, i));
1577 : 241913 : break;
1578 : :
1579 : 5976705 : case 'p':
1580 : 5976705 : hash.add_int (constant_lower_bound (SUBREG_BYTE (x)));
1581 : 5976705 : break;
1582 : :
1583 : : case '0':
1584 : : case 't':
1585 : : /* unused */
1586 : : break;
1587 : :
1588 : 0 : default:
1589 : 0 : gcc_unreachable ();
1590 : : }
1591 : : }
1592 : :
1593 : 111089709 : return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
1594 : : }
1595 : :
1596 : : /* Create a new value structure for VALUE and initialize it. The mode of the
1597 : : value is MODE. */
1598 : :
1599 : : static inline cselib_val *
1600 : 417152411 : new_cselib_val (hashval_t hash, machine_mode mode, rtx x)
1601 : : {
1602 : 417152411 : cselib_val *e = cselib_val_pool.allocate ();
1603 : :
1604 : 417152411 : gcc_assert (hash);
1605 : 417152411 : gcc_assert (next_uid);
1606 : :
1607 : 417152411 : e->hash = hash;
1608 : 417152411 : e->uid = next_uid++;
1609 : : /* We use an alloc pool to allocate this RTL construct because it
1610 : : accounts for about 8% of the overall memory usage. We know
1611 : : precisely when we can have VALUE RTXen (when cselib is active)
1612 : : so we don't need to put them in garbage collected memory.
1613 : : ??? Why should a VALUE be an RTX in the first place? */
1614 : 417152411 : e->val_rtx = (rtx_def*) value_pool.allocate ();
1615 : 417152411 : memset (e->val_rtx, 0, RTX_HDR_SIZE);
1616 : 417152411 : PUT_CODE (e->val_rtx, VALUE);
1617 : 417152411 : PUT_MODE (e->val_rtx, mode);
1618 : 417152411 : CSELIB_VAL_PTR (e->val_rtx) = e;
1619 : 417152411 : e->addr_list = 0;
1620 : 417152411 : e->locs = 0;
1621 : 417152411 : e->next_containing_mem = 0;
1622 : :
1623 : 417152411 : scalar_int_mode int_mode;
1624 : 543851019 : if (REG_P (x) && is_int_mode (mode, &int_mode)
1625 : 126698608 : && GET_MODE_SIZE (int_mode) > 1
1626 : 119965768 : && REG_VALUES (REGNO (x)) != NULL
1627 : 424275441 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
1628 : : {
1629 : 6958716 : rtx copy = shallow_copy_rtx (x);
1630 : 6958716 : scalar_int_mode narrow_mode_iter;
1631 : 24913149 : FOR_EACH_MODE_UNTIL (narrow_mode_iter, int_mode)
1632 : : {
1633 : 17954433 : PUT_MODE_RAW (copy, narrow_mode_iter);
1634 : 17954433 : cselib_val *v = cselib_lookup (copy, narrow_mode_iter, 0, VOIDmode);
1635 : 17954433 : if (v)
1636 : : {
1637 : 821311 : rtx sub = lowpart_subreg (narrow_mode_iter, e->val_rtx, int_mode);
1638 : 821311 : if (sub)
1639 : 821311 : new_elt_loc_list (v, sub);
1640 : : }
1641 : : }
1642 : : }
1643 : :
1644 : 417152411 : if (dump_file && (dump_flags & TDF_CSELIB))
1645 : : {
1646 : 0 : fprintf (dump_file, "cselib value %u:%u ", e->uid, hash);
1647 : 0 : if (flag_dump_noaddr || flag_dump_unnumbered)
1648 : 0 : fputs ("# ", dump_file);
1649 : : else
1650 : 0 : fprintf (dump_file, "%p ", (void*)e);
1651 : 0 : print_rtl_single (dump_file, x);
1652 : 0 : fputc ('\n', dump_file);
1653 : : }
1654 : :
1655 : 417152411 : return e;
1656 : : }
1657 : :
1658 : : /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
1659 : : contains the data at this address. X is a MEM that represents the
1660 : : value. Update the two value structures to represent this situation. */
1661 : :
1662 : : static void
1663 : 51897285 : add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
1664 : : {
1665 : 51897285 : addr_elt = canonical_cselib_val (addr_elt);
1666 : 51897285 : mem_elt = canonical_cselib_val (mem_elt);
1667 : :
1668 : : /* Avoid duplicates. */
1669 : 51897285 : addr_space_t as = MEM_ADDR_SPACE (x);
1670 : 92066455 : for (elt_loc_list *l = mem_elt->locs; l; l = l->next)
1671 : 40169170 : if (MEM_P (l->loc)
1672 : 11268650 : && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt
1673 : 40169170 : && MEM_ADDR_SPACE (l->loc) == as)
1674 : : {
1675 : 0 : promote_debug_loc (l);
1676 : 0 : return;
1677 : : }
1678 : :
1679 : 51897285 : addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
1680 : 51897285 : new_elt_loc_list (mem_elt,
1681 : : replace_equiv_address_nv (x, addr_elt->val_rtx));
1682 : 51897285 : if (mem_elt->next_containing_mem == NULL)
1683 : : {
1684 : 45372543 : mem_elt->next_containing_mem = first_containing_mem;
1685 : 45372543 : first_containing_mem = mem_elt;
1686 : : }
1687 : : }
1688 : :
1689 : : /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
1690 : : If CREATE, make a new one if we haven't seen it before. */
1691 : :
1692 : : static cselib_val *
1693 : 235998253 : cselib_lookup_mem (rtx x, int create)
1694 : : {
1695 : 235998253 : machine_mode mode = GET_MODE (x);
1696 : 235998253 : machine_mode addr_mode;
1697 : 235998253 : cselib_val **slot;
1698 : 235998253 : cselib_val *addr;
1699 : 235998253 : cselib_val *mem_elt;
1700 : :
1701 : 468033203 : if (MEM_VOLATILE_P (x) || mode == BLKmode
1702 : 231765323 : || !cselib_record_memory
1703 : 422692119 : || (FLOAT_MODE_P (mode) && flag_float_store))
1704 : : return 0;
1705 : :
1706 : 186681176 : addr_mode = GET_MODE (XEXP (x, 0));
1707 : 186681176 : if (addr_mode == VOIDmode)
1708 : 999803 : addr_mode = Pmode;
1709 : :
1710 : : /* Look up the value for the address. */
1711 : 186681176 : addr = cselib_lookup (XEXP (x, 0), addr_mode, create, mode);
1712 : 186681176 : if (! addr)
1713 : : return 0;
1714 : 115446520 : addr = canonical_cselib_val (addr);
1715 : :
1716 : : /* Find a value that describes a value of our mode at that address. */
1717 : 115446520 : addr_space_t as = MEM_ADDR_SPACE (x);
1718 : 117945936 : for (elt_list *l = addr->addr_list; l; l = l->next)
1719 : 73340651 : if (GET_MODE (l->elt->val_rtx) == mode)
1720 : : {
1721 : 77110151 : for (elt_loc_list *l2 = l->elt->locs; l2; l2 = l2->next)
1722 : 80956645 : if (MEM_P (l2->loc) && MEM_ADDR_SPACE (l2->loc) == as)
1723 : : {
1724 : 70841235 : promote_debug_loc (l->elt->locs);
1725 : 70841235 : return l->elt;
1726 : : }
1727 : : }
1728 : :
1729 : 44605285 : if (! create)
1730 : : return 0;
1731 : :
1732 : 28066897 : mem_elt = new_cselib_val (next_uid, mode, x);
1733 : 28066897 : add_mem_for_addr (addr, mem_elt, x);
1734 : 28066897 : slot = cselib_find_slot (mode, x, mem_elt->hash, INSERT, VOIDmode);
1735 : 28066897 : *slot = mem_elt;
1736 : 28066897 : return mem_elt;
1737 : : }
1738 : :
1739 : : /* Search through the possible substitutions in P. We prefer a non reg
1740 : : substitution because this allows us to expand the tree further. If
1741 : : we find, just a reg, take the lowest regno. There may be several
1742 : : non-reg results, we just take the first one because they will all
1743 : : expand to the same place. */
1744 : :
1745 : : static rtx
1746 : 23008109 : expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
1747 : : int max_depth)
1748 : : {
1749 : 23008109 : rtx reg_result = NULL;
1750 : 23008109 : unsigned int regno = UINT_MAX;
1751 : 23008109 : struct elt_loc_list *p_in = p;
1752 : :
1753 : 50054929 : for (; p; p = p->next)
1754 : : {
1755 : : /* Return these right away to avoid returning stack pointer based
1756 : : expressions for frame pointer and vice versa, which is something
1757 : : that would confuse DSE. See the comment in cselib_expand_value_rtx_1
1758 : : for more details. */
1759 : 30729942 : if (REG_P (p->loc)
1760 : 30729942 : && (REGNO (p->loc) == STACK_POINTER_REGNUM
1761 : : || REGNO (p->loc) == FRAME_POINTER_REGNUM
1762 : : || REGNO (p->loc) == HARD_FRAME_POINTER_REGNUM
1763 : 24410621 : || REGNO (p->loc) == cfa_base_preserved_regno))
1764 : : return p->loc;
1765 : : /* Avoid infinite recursion trying to expand a reg into a
1766 : : the same reg. */
1767 : 30224103 : if ((REG_P (p->loc))
1768 : 24402074 : && (REGNO (p->loc) < regno)
1769 : 54319045 : && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
1770 : : {
1771 : 4214293 : reg_result = p->loc;
1772 : 4214293 : regno = REGNO (p->loc);
1773 : : }
1774 : : /* Avoid infinite recursion and do not try to expand the
1775 : : value. */
1776 : 26009810 : else if (GET_CODE (p->loc) == VALUE
1777 : 393483 : && CSELIB_VAL_PTR (p->loc)->locs == p_in)
1778 : 0 : continue;
1779 : 26009810 : else if (!REG_P (p->loc))
1780 : : {
1781 : 5822029 : rtx result, note;
1782 : 5822029 : if (dump_file && (dump_flags & TDF_CSELIB))
1783 : : {
1784 : 0 : print_inline_rtx (dump_file, p->loc, 0);
1785 : 0 : fprintf (dump_file, "\n");
1786 : : }
1787 : 5822029 : if (GET_CODE (p->loc) == LO_SUM
1788 : 0 : && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
1789 : 0 : && p->setting_insn
1790 : 0 : && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
1791 : 5822029 : && XEXP (note, 0) == XEXP (p->loc, 1))
1792 : : return XEXP (p->loc, 1);
1793 : 5822029 : result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1794 : 5822029 : if (result)
1795 : : return result;
1796 : : }
1797 : :
1798 : : }
1799 : :
1800 : 19324987 : if (regno != UINT_MAX)
1801 : : {
1802 : 3408508 : rtx result;
1803 : 3408508 : if (dump_file && (dump_flags & TDF_CSELIB))
1804 : 0 : fprintf (dump_file, "r%d\n", regno);
1805 : :
1806 : 3408508 : result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1807 : 3408508 : if (result)
1808 : : return result;
1809 : : }
1810 : :
1811 : 16712621 : if (dump_file && (dump_flags & TDF_CSELIB))
1812 : : {
1813 : 0 : if (reg_result)
1814 : : {
1815 : 0 : print_inline_rtx (dump_file, reg_result, 0);
1816 : 0 : fprintf (dump_file, "\n");
1817 : : }
1818 : : else
1819 : 0 : fprintf (dump_file, "NULL\n");
1820 : : }
1821 : : return reg_result;
1822 : : }
1823 : :
1824 : :
1825 : : /* Forward substitute and expand an expression out to its roots.
1826 : : This is the opposite of common subexpression. Because local value
1827 : : numbering is such a weak optimization, the expanded expression is
1828 : : pretty much unique (not from a pointer equals point of view but
1829 : : from a tree shape point of view.
1830 : :
1831 : : This function returns NULL if the expansion fails. The expansion
1832 : : will fail if there is no value number for one of the operands or if
1833 : : one of the operands has been overwritten between the current insn
1834 : : and the beginning of the basic block. For instance x has no
1835 : : expansion in:
1836 : :
1837 : : r1 <- r1 + 3
1838 : : x <- r1 + 8
1839 : :
1840 : : REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1841 : : It is clear on return. */
1842 : :
1843 : : rtx
1844 : 34924182 : cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1845 : : {
1846 : 34924182 : struct expand_value_data evd;
1847 : :
1848 : 34924182 : evd.regs_active = regs_active;
1849 : 34924182 : evd.callback = NULL;
1850 : 34924182 : evd.callback_arg = NULL;
1851 : 34924182 : evd.dummy = false;
1852 : :
1853 : 34924182 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1854 : : }
1855 : :
1856 : : /* Same as cselib_expand_value_rtx, but using a callback to try to
1857 : : resolve some expressions. The CB function should return ORIG if it
1858 : : can't or does not want to deal with a certain RTX. Any other
1859 : : return value, including NULL, will be used as the expansion for
1860 : : VALUE, without any further changes. */
1861 : :
1862 : : rtx
1863 : 88686749 : cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1864 : : cselib_expand_callback cb, void *data)
1865 : : {
1866 : 88686749 : struct expand_value_data evd;
1867 : :
1868 : 88686749 : evd.regs_active = regs_active;
1869 : 88686749 : evd.callback = cb;
1870 : 88686749 : evd.callback_arg = data;
1871 : 88686749 : evd.dummy = false;
1872 : :
1873 : 88686749 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1874 : : }
1875 : :
1876 : : /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1877 : : or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1878 : : would return NULL or non-NULL, without allocating new rtx. */
1879 : :
1880 : : bool
1881 : 0 : cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1882 : : cselib_expand_callback cb, void *data)
1883 : : {
1884 : 0 : struct expand_value_data evd;
1885 : :
1886 : 0 : evd.regs_active = regs_active;
1887 : 0 : evd.callback = cb;
1888 : 0 : evd.callback_arg = data;
1889 : 0 : evd.dummy = true;
1890 : :
1891 : 0 : return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL;
1892 : : }
1893 : :
1894 : : /* Internal implementation of cselib_expand_value_rtx and
1895 : : cselib_expand_value_rtx_cb. */
1896 : :
1897 : : static rtx
1898 : 202986390 : cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1899 : : int max_depth)
1900 : : {
1901 : 202986390 : rtx copy, scopy;
1902 : 202986390 : int i, j;
1903 : 202986390 : RTX_CODE code;
1904 : 202986390 : const char *format_ptr;
1905 : 202986390 : machine_mode mode;
1906 : :
1907 : 202986390 : code = GET_CODE (orig);
1908 : :
1909 : : /* For the context of dse, if we end up expand into a huge tree, we
1910 : : will not have a useful address, so we might as well just give up
1911 : : quickly. */
1912 : 202986390 : if (max_depth <= 0)
1913 : : return NULL;
1914 : :
1915 : 200447431 : switch (code)
1916 : : {
1917 : 48459846 : case REG:
1918 : 48459846 : {
1919 : 48459846 : struct elt_list *l = REG_VALUES (REGNO (orig));
1920 : :
1921 : 48459846 : if (l && l->elt == NULL)
1922 : 24761594 : l = l->next;
1923 : 48480474 : for (; l; l = l->next)
1924 : 35674167 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1925 : : {
1926 : 35653539 : rtx result;
1927 : 35653539 : unsigned regno = REGNO (orig);
1928 : :
1929 : : /* The only thing that we are not willing to do (this
1930 : : is requirement of dse and if others potential uses
1931 : : need this function we should add a parm to control
1932 : : it) is that we will not substitute the
1933 : : STACK_POINTER_REGNUM, FRAME_POINTER or the
1934 : : HARD_FRAME_POINTER.
1935 : :
1936 : : These expansions confuses the code that notices that
1937 : : stores into the frame go dead at the end of the
1938 : : function and that the frame is not effected by calls
1939 : : to subroutines. If you allow the
1940 : : STACK_POINTER_REGNUM substitution, then dse will
1941 : : think that parameter pushing also goes dead which is
1942 : : wrong. If you allow the FRAME_POINTER or the
1943 : : HARD_FRAME_POINTER then you lose the opportunity to
1944 : : make the frame assumptions. */
1945 : 35653539 : if (regno == STACK_POINTER_REGNUM
1946 : 35653539 : || regno == FRAME_POINTER_REGNUM
1947 : 19572889 : || regno == HARD_FRAME_POINTER_REGNUM
1948 : 19071733 : || regno == cfa_base_preserved_regno)
1949 : : return orig;
1950 : :
1951 : 18762966 : bitmap_set_bit (evd->regs_active, regno);
1952 : :
1953 : 18762966 : if (dump_file && (dump_flags & TDF_CSELIB))
1954 : 0 : fprintf (dump_file, "expanding: r%d into: ", regno);
1955 : :
1956 : 18762966 : result = expand_loc (l->elt->locs, evd, max_depth);
1957 : 18762966 : bitmap_clear_bit (evd->regs_active, regno);
1958 : :
1959 : 18762966 : if (result)
1960 : : return result;
1961 : : else
1962 : : return orig;
1963 : : }
1964 : : return orig;
1965 : : }
1966 : :
1967 : : CASE_CONST_ANY:
1968 : : case SYMBOL_REF:
1969 : : case CODE_LABEL:
1970 : : case PC:
1971 : : case SCRATCH:
1972 : : /* SCRATCH must be shared because they represent distinct values. */
1973 : : return orig;
1974 : 6 : case CLOBBER:
1975 : 6 : if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1976 : : return orig;
1977 : : break;
1978 : :
1979 : 265633 : case CONST:
1980 : 265633 : if (shared_const_p (orig))
1981 : : return orig;
1982 : : break;
1983 : :
1984 : 1133091 : case SUBREG:
1985 : 1133091 : {
1986 : 1133091 : rtx subreg;
1987 : :
1988 : 1133091 : if (evd->callback)
1989 : : {
1990 : 1019989 : subreg = evd->callback (orig, evd->regs_active, max_depth,
1991 : : evd->callback_arg);
1992 : 1019989 : if (subreg != orig)
1993 : : return subreg;
1994 : : }
1995 : :
1996 : 113102 : subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1997 : : max_depth - 1);
1998 : 113102 : if (!subreg)
1999 : : return NULL;
2000 : 107788 : scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
2001 : 53894 : GET_MODE (SUBREG_REG (orig)),
2002 : 53894 : SUBREG_BYTE (orig));
2003 : 53894 : if (scopy == NULL
2004 : 53192 : || (GET_CODE (scopy) == SUBREG
2005 : 49209 : && !REG_P (SUBREG_REG (scopy))
2006 : 7006 : && !MEM_P (SUBREG_REG (scopy))))
2007 : : return NULL;
2008 : :
2009 : : return scopy;
2010 : : }
2011 : :
2012 : 70065144 : case VALUE:
2013 : 70065144 : {
2014 : 70065144 : rtx result;
2015 : :
2016 : 70065144 : if (dump_file && (dump_flags & TDF_CSELIB))
2017 : : {
2018 : 0 : fputs ("\nexpanding ", dump_file);
2019 : 0 : print_rtl_single (dump_file, orig);
2020 : 0 : fputs (" into...", dump_file);
2021 : : }
2022 : :
2023 : 70065144 : if (evd->callback)
2024 : : {
2025 : 65820001 : result = evd->callback (orig, evd->regs_active, max_depth,
2026 : : evd->callback_arg);
2027 : :
2028 : 65820001 : if (result != orig)
2029 : : return result;
2030 : : }
2031 : :
2032 : 4245143 : result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
2033 : 4245143 : return result;
2034 : : }
2035 : :
2036 : 6200429 : case DEBUG_EXPR:
2037 : 6200429 : if (evd->callback)
2038 : 6200429 : return evd->callback (orig, evd->regs_active, max_depth,
2039 : 6200429 : evd->callback_arg);
2040 : : return orig;
2041 : :
2042 : : default:
2043 : : break;
2044 : : }
2045 : :
2046 : : /* Copy the various flags, fields, and other information. We assume
2047 : : that all fields need copying, and then clear the fields that should
2048 : : not be copied. That is the sensible default behavior, and forces
2049 : : us to explicitly document why we are *not* copying a flag. */
2050 : 44480265 : if (evd->dummy)
2051 : : copy = NULL;
2052 : : else
2053 : 44480265 : copy = shallow_copy_rtx (orig);
2054 : :
2055 : 44480265 : format_ptr = GET_RTX_FORMAT (code);
2056 : :
2057 : 116775372 : for (i = 0; i < GET_RTX_LENGTH (code); i++)
2058 : 76394063 : switch (*format_ptr++)
2059 : : {
2060 : 69551349 : case 'e':
2061 : 69551349 : if (XEXP (orig, i) != NULL)
2062 : : {
2063 : 69551349 : rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
2064 : : max_depth - 1);
2065 : 69551349 : if (!result)
2066 : : return NULL;
2067 : 65488731 : if (copy)
2068 : 65488731 : XEXP (copy, i) = result;
2069 : : }
2070 : : break;
2071 : :
2072 : 301154 : case 'E':
2073 : 301154 : case 'V':
2074 : 301154 : if (XVEC (orig, i) != NULL)
2075 : : {
2076 : 301154 : if (copy)
2077 : 301154 : XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
2078 : 745287 : for (j = 0; j < XVECLEN (orig, i); j++)
2079 : : {
2080 : 480471 : rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
2081 : : evd, max_depth - 1);
2082 : 480471 : if (!result)
2083 : : return NULL;
2084 : 444133 : if (copy)
2085 : 444133 : XVECEXP (copy, i, j) = result;
2086 : : }
2087 : : }
2088 : : break;
2089 : :
2090 : : case 't':
2091 : : case 'w':
2092 : : case 'i':
2093 : : case 'L':
2094 : : case 's':
2095 : : case 'S':
2096 : : case 'T':
2097 : : case 'u':
2098 : : case 'B':
2099 : : case '0':
2100 : : /* These are left unchanged. */
2101 : : break;
2102 : :
2103 : 0 : default:
2104 : 0 : gcc_unreachable ();
2105 : : }
2106 : :
2107 : 40381309 : if (evd->dummy)
2108 : : return orig;
2109 : :
2110 : 40381309 : mode = GET_MODE (copy);
2111 : : /* If an operand has been simplified into CONST_INT, which doesn't
2112 : : have a mode and the mode isn't derivable from whole rtx's mode,
2113 : : try simplify_*_operation first with mode from original's operand
2114 : : and as a fallback wrap CONST_INT into gen_rtx_CONST. */
2115 : 40381309 : scopy = copy;
2116 : 40381309 : switch (GET_RTX_CLASS (code))
2117 : : {
2118 : 675702 : case RTX_UNARY:
2119 : 675702 : if (CONST_INT_P (XEXP (copy, 0))
2120 : 50064 : && GET_MODE (XEXP (orig, 0)) != VOIDmode)
2121 : : {
2122 : 50056 : scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
2123 : : GET_MODE (XEXP (orig, 0)));
2124 : 50056 : if (scopy)
2125 : : return scopy;
2126 : : }
2127 : : break;
2128 : : case RTX_COMM_ARITH:
2129 : : case RTX_BIN_ARITH:
2130 : : /* These expressions can derive operand modes from the whole rtx's mode. */
2131 : : break;
2132 : 58234 : case RTX_TERNARY:
2133 : 58234 : case RTX_BITFIELD_OPS:
2134 : 58234 : if (CONST_INT_P (XEXP (copy, 0))
2135 : 648 : && GET_MODE (XEXP (orig, 0)) != VOIDmode)
2136 : : {
2137 : 0 : scopy = simplify_ternary_operation (code, mode,
2138 : : GET_MODE (XEXP (orig, 0)),
2139 : : XEXP (copy, 0), XEXP (copy, 1),
2140 : : XEXP (copy, 2));
2141 : 0 : if (scopy)
2142 : : return scopy;
2143 : : }
2144 : : break;
2145 : 192211 : case RTX_COMPARE:
2146 : 192211 : case RTX_COMM_COMPARE:
2147 : 192211 : if (CONST_INT_P (XEXP (copy, 0))
2148 : 596 : && GET_MODE (XEXP (copy, 1)) == VOIDmode
2149 : 242 : && (GET_MODE (XEXP (orig, 0)) != VOIDmode
2150 : 2 : || GET_MODE (XEXP (orig, 1)) != VOIDmode))
2151 : : {
2152 : 242 : scopy = simplify_relational_operation (code, mode,
2153 : : (GET_MODE (XEXP (orig, 0))
2154 : : != VOIDmode)
2155 : : ? GET_MODE (XEXP (orig, 0))
2156 : 2 : : GET_MODE (XEXP (orig, 1)),
2157 : : XEXP (copy, 0),
2158 : : XEXP (copy, 1));
2159 : 242 : if (scopy)
2160 : : return scopy;
2161 : : }
2162 : : break;
2163 : : default:
2164 : : break;
2165 : : }
2166 : 40331011 : scopy = simplify_rtx (copy);
2167 : 40331011 : if (scopy)
2168 : 4456608 : return scopy;
2169 : : return copy;
2170 : : }
2171 : :
2172 : : /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
2173 : : with VALUE expressions. This way, it becomes independent of changes
2174 : : to registers and memory.
2175 : : X isn't actually modified; if modifications are needed, new rtl is
2176 : : allocated. However, the return value can share rtl with X.
2177 : : If X is within a MEM, MEMMODE must be the mode of the MEM. */
2178 : :
2179 : : rtx
2180 : 587429998 : cselib_subst_to_values (rtx x, machine_mode memmode)
2181 : : {
2182 : 595066464 : enum rtx_code code = GET_CODE (x);
2183 : 595066464 : const char *fmt = GET_RTX_FORMAT (code);
2184 : 595066464 : cselib_val *e;
2185 : 595066464 : struct elt_list *l;
2186 : 595066464 : rtx copy = x;
2187 : 595066464 : int i;
2188 : 595066464 : poly_int64 offset;
2189 : :
2190 : 595066464 : switch (code)
2191 : : {
2192 : 231304803 : case REG:
2193 : 231304803 : l = REG_VALUES (REGNO (x));
2194 : 231304803 : if (l && l->elt == NULL)
2195 : 131806604 : l = l->next;
2196 : 233639842 : for (; l; l = l->next)
2197 : 233639842 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
2198 : : return l->elt->val_rtx;
2199 : :
2200 : 0 : gcc_unreachable ();
2201 : :
2202 : 6126811 : case MEM:
2203 : 6126811 : e = cselib_lookup_mem (x, 0);
2204 : : /* This used to happen for autoincrements, but we deal with them
2205 : : properly now. Remove the if stmt for the next release. */
2206 : 6126811 : if (! e)
2207 : : {
2208 : : /* Assign a value that doesn't match any other. */
2209 : 0 : e = new_cselib_val (next_uid, GET_MODE (x), x);
2210 : : }
2211 : 6126811 : return e->val_rtx;
2212 : :
2213 : 693227 : case ENTRY_VALUE:
2214 : 693227 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
2215 : 693227 : if (! e)
2216 : : break;
2217 : 800 : return e->val_rtx;
2218 : :
2219 : : CASE_CONST_ANY:
2220 : : return x;
2221 : :
2222 : 6325191 : case PRE_DEC:
2223 : 6325191 : case PRE_INC:
2224 : 6325191 : gcc_assert (memmode != VOIDmode);
2225 : 12650382 : offset = GET_MODE_SIZE (memmode);
2226 : 6325191 : if (code == PRE_DEC)
2227 : 6325191 : offset = -offset;
2228 : 6325191 : return cselib_subst_to_values (plus_constant (GET_MODE (x),
2229 : : XEXP (x, 0), offset),
2230 : 6325191 : memmode);
2231 : :
2232 : 372772 : case PRE_MODIFY:
2233 : 372772 : gcc_assert (memmode != VOIDmode);
2234 : 372772 : return cselib_subst_to_values (XEXP (x, 1), memmode);
2235 : :
2236 : 938503 : case POST_DEC:
2237 : 938503 : case POST_INC:
2238 : 938503 : case POST_MODIFY:
2239 : 938503 : gcc_assert (memmode != VOIDmode);
2240 : 938503 : return cselib_subst_to_values (XEXP (x, 0), memmode);
2241 : :
2242 : 113709714 : case PLUS:
2243 : 148609013 : if (GET_MODE (x) == Pmode && CONST_INT_P (XEXP (x, 1)))
2244 : : {
2245 : 92856109 : rtx t = cselib_subst_to_values (XEXP (x, 0), memmode);
2246 : 92856109 : if (GET_CODE (t) == VALUE)
2247 : : {
2248 : 87789751 : if (SP_DERIVED_VALUE_P (t) && XEXP (x, 1) == const0_rtx)
2249 : : return t;
2250 : 87789751 : for (struct elt_loc_list *l = CSELIB_VAL_PTR (t)->locs;
2251 : 185020189 : l; l = l->next)
2252 : 118638136 : if (GET_CODE (l->loc) == PLUS
2253 : 24745257 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2254 : 24615658 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2255 : 140046656 : && CONST_INT_P (XEXP (l->loc, 1)))
2256 : 35229327 : return plus_constant (Pmode, l->loc, INTVAL (XEXP (x, 1)));
2257 : : }
2258 : 71448411 : if (t != XEXP (x, 0))
2259 : : {
2260 : 67259202 : copy = shallow_copy_rtx (x);
2261 : 67259202 : XEXP (copy, 0) = t;
2262 : : }
2263 : 71448411 : return copy;
2264 : : }
2265 : :
2266 : : default:
2267 : : break;
2268 : : }
2269 : :
2270 : 475476228 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2271 : : {
2272 : 310293979 : if (fmt[i] == 'e')
2273 : : {
2274 : 229028634 : rtx t = cselib_subst_to_values (XEXP (x, i), memmode);
2275 : :
2276 : 229028634 : if (t != XEXP (x, i))
2277 : : {
2278 : 166502845 : if (x == copy)
2279 : 119238368 : copy = shallow_copy_rtx (x);
2280 : 166502845 : XEXP (copy, i) = t;
2281 : : }
2282 : : }
2283 : 81265345 : else if (fmt[i] == 'E')
2284 : : {
2285 : : int j;
2286 : :
2287 : 18417335 : for (j = 0; j < XVECLEN (x, i); j++)
2288 : : {
2289 : 13052176 : rtx t = cselib_subst_to_values (XVECEXP (x, i, j), memmode);
2290 : :
2291 : 13052176 : if (t != XVECEXP (x, i, j))
2292 : : {
2293 : 2427162 : if (XVEC (x, i) == XVEC (copy, i))
2294 : : {
2295 : 1848600 : if (x == copy)
2296 : 1848600 : copy = shallow_copy_rtx (x);
2297 : 1848600 : XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
2298 : : }
2299 : 2427162 : XVECEXP (copy, i, j) = t;
2300 : : }
2301 : : }
2302 : : }
2303 : : }
2304 : :
2305 : : return copy;
2306 : : }
2307 : :
2308 : : /* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */
2309 : :
2310 : : rtx
2311 : 1465 : cselib_subst_to_values_from_insn (rtx x, machine_mode memmode, rtx_insn *insn)
2312 : : {
2313 : 1465 : rtx ret;
2314 : 1465 : gcc_assert (!cselib_current_insn);
2315 : 1465 : cselib_current_insn = insn;
2316 : 1465 : ret = cselib_subst_to_values (x, memmode);
2317 : 1465 : cselib_current_insn = NULL;
2318 : 1465 : return ret;
2319 : : }
2320 : :
2321 : : /* Look up the rtl expression X in our tables and return the value it
2322 : : has. If CREATE is zero, we return NULL if we don't know the value.
2323 : : Otherwise, we create a new one if possible, using mode MODE if X
2324 : : doesn't have a mode (i.e. because it's a constant). When X is part
2325 : : of an address, MEMMODE should be the mode of the enclosing MEM if
2326 : : we're tracking autoinc expressions. */
2327 : :
2328 : : static cselib_val *
2329 : 2393541737 : cselib_lookup_1 (rtx x, machine_mode mode,
2330 : : int create, machine_mode memmode)
2331 : : {
2332 : 2393541737 : cselib_val **slot;
2333 : 2393541737 : cselib_val *e;
2334 : :
2335 : 2393541737 : if (GET_MODE (x) != VOIDmode)
2336 : 2308759215 : mode = GET_MODE (x);
2337 : :
2338 : 2393541737 : if (GET_CODE (x) == VALUE)
2339 : 64372328 : return CSELIB_VAL_PTR (x);
2340 : :
2341 : 2329169409 : if (REG_P (x))
2342 : : {
2343 : 1499624260 : struct elt_list *l;
2344 : 1499624260 : unsigned int i = REGNO (x);
2345 : :
2346 : 1499624260 : l = REG_VALUES (i);
2347 : 1499624260 : if (l && l->elt == NULL)
2348 : 626490528 : l = l->next;
2349 : 1520535399 : for (; l; l = l->next)
2350 : 1159646571 : if (mode == GET_MODE (l->elt->val_rtx))
2351 : : {
2352 : 1138735432 : promote_debug_loc (l->elt->locs);
2353 : 1138735432 : return l->elt;
2354 : : }
2355 : :
2356 : 360888828 : if (! create)
2357 : : return 0;
2358 : :
2359 : 136593900 : if (i < FIRST_PSEUDO_REGISTER)
2360 : : {
2361 : 78075655 : unsigned int n = hard_regno_nregs (i, mode);
2362 : :
2363 : 78075655 : if (n > max_value_regs)
2364 : 27236720 : max_value_regs = n;
2365 : : }
2366 : :
2367 : 136593900 : e = new_cselib_val (next_uid, GET_MODE (x), x);
2368 : 160681482 : if (GET_MODE (x) == Pmode && x == stack_pointer_rtx)
2369 : 12139179 : SP_DERIVED_VALUE_P (e->val_rtx) = 1;
2370 : 136593900 : new_elt_loc_list (e, x);
2371 : :
2372 : 136593900 : scalar_int_mode int_mode;
2373 : 136593900 : if (REG_VALUES (i) == 0)
2374 : : {
2375 : : /* Maintain the invariant that the first entry of
2376 : : REG_VALUES, if present, must be the value used to set the
2377 : : register, or NULL. */
2378 : 126465966 : used_regs[n_used_regs++] = i;
2379 : 126465966 : REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
2380 : : }
2381 : 10127934 : else if (cselib_preserve_constants
2382 : 10127934 : && is_int_mode (mode, &int_mode))
2383 : : {
2384 : : /* During var-tracking, try harder to find equivalences
2385 : : for SUBREGs. If a setter sets say a DImode register
2386 : : and user uses that register only in SImode, add a lowpart
2387 : : subreg location. */
2388 : 1680642 : struct elt_list *lwider = NULL;
2389 : 1680642 : scalar_int_mode lmode;
2390 : 1680642 : l = REG_VALUES (i);
2391 : 1680642 : if (l && l->elt == NULL)
2392 : 1060559 : l = l->next;
2393 : 2568979 : for (; l; l = l->next)
2394 : 888337 : if (is_int_mode (GET_MODE (l->elt->val_rtx), &lmode)
2395 : 1313110 : && GET_MODE_SIZE (lmode) > GET_MODE_SIZE (int_mode)
2396 : 326805 : && (lwider == NULL
2397 : 6168 : || partial_subreg_p (lmode,
2398 : 6168 : GET_MODE (lwider->elt->val_rtx))))
2399 : : {
2400 : 325611 : struct elt_loc_list *el;
2401 : 342346 : if (i < FIRST_PSEUDO_REGISTER
2402 : 325611 : && hard_regno_nregs (i, lmode) != 1)
2403 : 16735 : continue;
2404 : 610352 : for (el = l->elt->locs; el; el = el->next)
2405 : 578264 : if (!REG_P (el->loc))
2406 : : break;
2407 : 308876 : if (el)
2408 : 888337 : lwider = l;
2409 : : }
2410 : 1680642 : if (lwider)
2411 : : {
2412 : 543628 : rtx sub = lowpart_subreg (int_mode, lwider->elt->val_rtx,
2413 : 271814 : GET_MODE (lwider->elt->val_rtx));
2414 : 271814 : if (sub)
2415 : 271814 : new_elt_loc_list (e, sub);
2416 : : }
2417 : : }
2418 : 136593900 : REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
2419 : 136593900 : slot = cselib_find_slot (mode, x, e->hash, INSERT, memmode);
2420 : 136593900 : *slot = e;
2421 : 136593900 : return e;
2422 : : }
2423 : :
2424 : 829545149 : if (MEM_P (x))
2425 : 229871442 : return cselib_lookup_mem (x, create);
2426 : :
2427 : 599673707 : hashval_t hashval = cselib_hash_rtx (x, create, memmode);
2428 : : /* Can't even create if hashing is not possible. */
2429 : 599673707 : if (! hashval)
2430 : : return 0;
2431 : :
2432 : 768797398 : slot = cselib_find_slot (mode, x, hashval,
2433 : : create ? INSERT : NO_INSERT, memmode);
2434 : 547582419 : if (slot == 0)
2435 : : return 0;
2436 : :
2437 : 436781036 : e = (cselib_val *) *slot;
2438 : 436781036 : if (e)
2439 : : return e;
2440 : :
2441 : 252491614 : e = new_cselib_val (hashval, mode, x);
2442 : :
2443 : : /* We have to fill the slot before calling cselib_subst_to_values:
2444 : : the hash table is inconsistent until we do so, and
2445 : : cselib_subst_to_values will need to do lookups. */
2446 : 252491614 : *slot = e;
2447 : 252491614 : rtx v = cselib_subst_to_values (x, memmode);
2448 : :
2449 : : /* If cselib_preserve_constants, we might get a SP_DERIVED_VALUE_P
2450 : : VALUE that isn't in the hash tables anymore. */
2451 : 252491614 : if (GET_CODE (v) == VALUE && SP_DERIVED_VALUE_P (v) && PRESERVED_VALUE_P (v))
2452 : 0 : PRESERVED_VALUE_P (e->val_rtx) = 1;
2453 : :
2454 : 252491614 : new_elt_loc_list (e, v);
2455 : 252491614 : return e;
2456 : : }
2457 : :
2458 : : /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2459 : :
2460 : : cselib_val *
2461 : 6319842 : cselib_lookup_from_insn (rtx x, machine_mode mode,
2462 : : int create, machine_mode memmode, rtx_insn *insn)
2463 : : {
2464 : 6319842 : cselib_val *ret;
2465 : :
2466 : 6319842 : gcc_assert (!cselib_current_insn);
2467 : 6319842 : cselib_current_insn = insn;
2468 : :
2469 : 6319842 : ret = cselib_lookup (x, mode, create, memmode);
2470 : :
2471 : 6319842 : cselib_current_insn = NULL;
2472 : :
2473 : 6319842 : return ret;
2474 : : }
2475 : :
2476 : : /* Wrapper for cselib_lookup_1, that logs the lookup result and
2477 : : maintains invariants related with debug insns. */
2478 : :
2479 : : cselib_val *
2480 : 2392366503 : cselib_lookup (rtx x, machine_mode mode,
2481 : : int create, machine_mode memmode)
2482 : : {
2483 : 2392366503 : cselib_val *ret = cselib_lookup_1 (x, mode, create, memmode);
2484 : :
2485 : : /* ??? Should we return NULL if we're not to create an entry, the
2486 : : found loc is a debug loc and cselib_current_insn is not DEBUG?
2487 : : If so, we should also avoid converting val to non-DEBUG; probably
2488 : : easiest setting cselib_current_insn to NULL before the call
2489 : : above. */
2490 : :
2491 : 2392366503 : if (dump_file && (dump_flags & TDF_CSELIB))
2492 : : {
2493 : 0 : fputs ("cselib lookup ", dump_file);
2494 : 0 : print_inline_rtx (dump_file, x, 2);
2495 : 0 : fprintf (dump_file, " => %u:%u\n",
2496 : : ret ? ret->uid : 0,
2497 : : ret ? ret->hash : 0);
2498 : : }
2499 : :
2500 : 2392366503 : return ret;
2501 : : }
2502 : :
2503 : : /* Invalidate the value at *L, which is part of REG_VALUES (REGNO). */
2504 : :
2505 : : static void
2506 : 185784344 : cselib_invalidate_regno_val (unsigned int regno, struct elt_list **l)
2507 : : {
2508 : 185784344 : cselib_val *v = (*l)->elt;
2509 : 185784344 : if (*l == REG_VALUES (regno))
2510 : : {
2511 : : /* Maintain the invariant that the first entry of
2512 : : REG_VALUES, if present, must be the value used to set
2513 : : the register, or NULL. This is also nice because
2514 : : then we won't push the same regno onto user_regs
2515 : : multiple times. */
2516 : 143186100 : (*l)->elt = NULL;
2517 : 143186100 : l = &(*l)->next;
2518 : : }
2519 : : else
2520 : 42598244 : unchain_one_elt_list (l);
2521 : :
2522 : 185784344 : v = canonical_cselib_val (v);
2523 : :
2524 : 185784344 : bool had_locs = v->locs != NULL;
2525 : 185784344 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2526 : :
2527 : : /* Now, we clear the mapping from value to reg. It must exist, so
2528 : : this code will crash intentionally if it doesn't. */
2529 : 185784344 : for (elt_loc_list **p = &v->locs; ; p = &(*p)->next)
2530 : : {
2531 : 213825117 : rtx x = (*p)->loc;
2532 : :
2533 : 213825117 : if (REG_P (x) && REGNO (x) == regno)
2534 : : {
2535 : 185784344 : unchain_one_elt_loc_list (p);
2536 : 185784344 : break;
2537 : : }
2538 : 28040773 : }
2539 : :
2540 : 185784344 : if (had_locs && cselib_useless_value_p (v))
2541 : : {
2542 : 21502256 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2543 : 0 : n_useless_debug_values++;
2544 : : else
2545 : 21502256 : n_useless_values++;
2546 : : }
2547 : 185784344 : }
2548 : :
2549 : : /* Invalidate any entries in reg_values that overlap REGNO. This is called
2550 : : if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2551 : : is used to determine how many hard registers are being changed. If MODE
2552 : : is VOIDmode, then only REGNO is being changed; this is used when
2553 : : invalidating call clobbered registers across a call. */
2554 : :
2555 : : static void
2556 : 807115759 : cselib_invalidate_regno (unsigned int regno, machine_mode mode)
2557 : : {
2558 : 807115759 : unsigned int endregno;
2559 : 807115759 : unsigned int i;
2560 : :
2561 : : /* If we see pseudos after reload, something is _wrong_. */
2562 : 807115759 : gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
2563 : : || reg_renumber[regno] < 0);
2564 : :
2565 : : /* Determine the range of registers that must be invalidated. For
2566 : : pseudos, only REGNO is affected. For hard regs, we must take MODE
2567 : : into account, and we must also invalidate lower register numbers
2568 : : if they contain values that overlap REGNO. */
2569 : 222999680 : if (regno < FIRST_PSEUDO_REGISTER)
2570 : : {
2571 : 702166997 : gcc_assert (mode != VOIDmode);
2572 : :
2573 : 702166997 : if (regno < max_value_regs)
2574 : : i = 0;
2575 : : else
2576 : 660486368 : i = regno - max_value_regs;
2577 : :
2578 : 702166997 : endregno = end_hard_regno (mode, regno);
2579 : : }
2580 : : else
2581 : : {
2582 : 104948762 : i = regno;
2583 : 104948762 : endregno = regno + 1;
2584 : : }
2585 : :
2586 : 2237915516 : for (; i < endregno; i++)
2587 : : {
2588 : 1430799757 : struct elt_list **l = ®_VALUES (i);
2589 : :
2590 : : /* Go through all known values for this reg; if it overlaps the range
2591 : : we're invalidating, remove the value. */
2592 : 1819058664 : while (*l)
2593 : : {
2594 : 388258907 : cselib_val *v = (*l)->elt;
2595 : 388258907 : unsigned int this_last = i;
2596 : :
2597 : 388258907 : if (i < FIRST_PSEUDO_REGISTER && v != NULL)
2598 : 168834657 : this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
2599 : :
2600 : 388258907 : if (this_last < regno || v == NULL
2601 : 119327703 : || (v == cfa_base_preserved_val
2602 : 4420293 : && i == cfa_base_preserved_regno))
2603 : : {
2604 : 273349867 : l = &(*l)->next;
2605 : 273349867 : continue;
2606 : : }
2607 : :
2608 : : /* We have an overlap. */
2609 : 114909040 : cselib_invalidate_regno_val (i, l);
2610 : : }
2611 : : }
2612 : 807115759 : }
2613 : :
2614 : : /* Invalidate any locations in the table which are changed because of a
2615 : : store to MEM_RTX. If this is called because of a non-const call
2616 : : instruction, MEM_RTX is (mem:BLK const0_rtx). */
2617 : :
2618 : : static void
2619 : 112542175 : cselib_invalidate_mem (rtx mem_rtx)
2620 : : {
2621 : 112542175 : cselib_val **vp, *v, *next;
2622 : 112542175 : int num_mems = 0;
2623 : 112542175 : rtx mem_addr;
2624 : :
2625 : 112542175 : mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
2626 : 112542175 : mem_rtx = canon_rtx (mem_rtx);
2627 : :
2628 : 112542175 : vp = &first_containing_mem;
2629 : 282592284 : for (v = *vp; v != &dummy_val; v = next)
2630 : : {
2631 : 170050109 : bool has_mem = false;
2632 : 170050109 : struct elt_loc_list **p = &v->locs;
2633 : 170050109 : bool had_locs = v->locs != NULL;
2634 : 170050109 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2635 : 170050109 : rtx sp_base = NULL_RTX;
2636 : 170050109 : HOST_WIDE_INT sp_off = 0;
2637 : :
2638 : 506432561 : while (*p)
2639 : : {
2640 : 336382452 : rtx x = (*p)->loc;
2641 : 336382452 : cselib_val *addr;
2642 : 336382452 : struct elt_list **mem_chain;
2643 : :
2644 : : /* MEMs may occur in locations only at the top level; below
2645 : : that every MEM or REG is substituted by its VALUE. */
2646 : 336382452 : if (!MEM_P (x))
2647 : : {
2648 : 102210674 : p = &(*p)->next;
2649 : 102210674 : continue;
2650 : : }
2651 : :
2652 : : /* When invalidating memory below the stack pointer for const/pure
2653 : : calls and alloca/VLAs aren't used, attempt to optimize. Values
2654 : : stored into area sometimes below the stack pointer shouldn't be
2655 : : addressable and should be stored just through stack pointer
2656 : : derived expressions, so don't invalidate MEMs not using stack
2657 : : derived addresses, or if the MEMs clearly aren't below the stack
2658 : : pointer. This isn't a fully conservative approach, the hope is
2659 : : that invalidating more MEMs than this isn't actually needed. */
2660 : 234171778 : if (mem_rtx == callmem[1]
2661 : 3057084 : && num_mems < param_max_cselib_memory_locations
2662 : 3057026 : && GET_CODE (XEXP (x, 0)) == VALUE
2663 : 3057026 : && !cfun->calls_alloca)
2664 : : {
2665 : 3010803 : cselib_val *v2 = CSELIB_VAL_PTR (XEXP (x, 0));
2666 : 3010803 : rtx x_base = NULL_RTX;
2667 : 3010803 : HOST_WIDE_INT x_off = 0;
2668 : 3010803 : if (SP_DERIVED_VALUE_P (v2->val_rtx))
2669 : : x_base = v2->val_rtx;
2670 : : else
2671 : 4729569 : for (struct elt_loc_list *l = v2->locs; l; l = l->next)
2672 : 2993436 : if (GET_CODE (l->loc) == PLUS
2673 : 1648770 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2674 : 1536175 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2675 : 4188971 : && CONST_INT_P (XEXP (l->loc, 1)))
2676 : : {
2677 : 1195510 : x_base = XEXP (l->loc, 0);
2678 : 1195510 : x_off = INTVAL (XEXP (l->loc, 1));
2679 : 1195510 : break;
2680 : : }
2681 : : /* If x_base is NULL here, don't invalidate x as its address
2682 : : isn't derived from sp such that it could be in outgoing
2683 : : argument area of some call in !ACCUMULATE_OUTGOING_ARGS
2684 : : function. */
2685 : 3010803 : if (x_base)
2686 : : {
2687 : 1274670 : if (sp_base == NULL_RTX)
2688 : : {
2689 : 2350468 : if (cselib_val *v3
2690 : 1210884 : = cselib_lookup_1 (stack_pointer_rtx, Pmode, 0,
2691 : : VOIDmode))
2692 : : {
2693 : 1170335 : if (SP_DERIVED_VALUE_P (v3->val_rtx))
2694 : : sp_base = v3->val_rtx;
2695 : : else
2696 : 346050 : for (struct elt_loc_list *l = v3->locs;
2697 : 693312 : l; l = l->next)
2698 : 693272 : if (GET_CODE (l->loc) == PLUS
2699 : 346012 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2700 : 346012 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2701 : 1039282 : && CONST_INT_P (XEXP (l->loc, 1)))
2702 : : {
2703 : 346010 : sp_base = XEXP (l->loc, 0);
2704 : 346010 : sp_off = INTVAL (XEXP (l->loc, 1));
2705 : 346010 : break;
2706 : : }
2707 : : }
2708 : 1175234 : if (sp_base == NULL_RTX)
2709 : 4939 : sp_base = pc_rtx;
2710 : : }
2711 : : /* Otherwise, if x_base and sp_base are the same,
2712 : : we know that x_base + x_off is the x's address and
2713 : : sp_base + sp_off is current value of stack pointer,
2714 : : so try to determine if x is certainly not below stack
2715 : : pointer. */
2716 : 1274670 : if (sp_base == x_base)
2717 : : {
2718 : 1267117 : if (STACK_GROWS_DOWNWARD)
2719 : : {
2720 : 1267117 : HOST_WIDE_INT off = sp_off;
2721 : : #ifdef STACK_ADDRESS_OFFSET
2722 : : /* On SPARC take stack pointer bias into account as
2723 : : well. */
2724 : : off += (STACK_ADDRESS_OFFSET
2725 : : - FIRST_PARM_OFFSET (current_function_decl));
2726 : : #endif
2727 : 1267117 : if (x_off >= off)
2728 : : /* x is at or above the current stack pointer,
2729 : : no need to invalidate it. */
2730 : : x_base = NULL_RTX;
2731 : : }
2732 : : else
2733 : : {
2734 : : HOST_WIDE_INT sz;
2735 : : enum machine_mode mode = GET_MODE (x);
2736 : : if ((MEM_SIZE_KNOWN_P (x)
2737 : : && MEM_SIZE (x).is_constant (&sz))
2738 : : || (mode != BLKmode
2739 : : && GET_MODE_SIZE (mode).is_constant (&sz)))
2740 : : if (x_off < sp_off
2741 : : && ((HOST_WIDE_INT) ((unsigned HOST_WIDE_INT)
2742 : : x_off + sz) <= sp_off))
2743 : : /* x's end is below or at the current stack
2744 : : pointer in !STACK_GROWS_DOWNWARD target,
2745 : : no need to invalidate it. */
2746 : : x_base = NULL_RTX;
2747 : : }
2748 : : }
2749 : : }
2750 : 3001786 : if (x_base == NULL_RTX)
2751 : : {
2752 : 3001786 : has_mem = true;
2753 : 3001786 : num_mems++;
2754 : 3001786 : p = &(*p)->next;
2755 : 3001786 : continue;
2756 : : }
2757 : : }
2758 : :
2759 : 425569344 : if (num_mems < param_max_cselib_memory_locations
2760 : 462274619 : && ! canon_anti_dependence (x, false, mem_rtx,
2761 : 231104627 : GET_MODE (mem_rtx), mem_addr))
2762 : : {
2763 : 194399352 : has_mem = true;
2764 : 194399352 : num_mems++;
2765 : 194399352 : p = &(*p)->next;
2766 : 194399352 : continue;
2767 : : }
2768 : :
2769 : : /* This one overlaps. */
2770 : : /* We must have a mapping from this MEM's address to the
2771 : : value (E). Remove that, too. */
2772 : 36770640 : addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0, GET_MODE (x));
2773 : 36770640 : addr = canonical_cselib_val (addr);
2774 : 36770640 : gcc_checking_assert (v == canonical_cselib_val (v));
2775 : 36770640 : mem_chain = &addr->addr_list;
2776 : 36775984 : for (;;)
2777 : : {
2778 : 36773312 : cselib_val *canon = canonical_cselib_val ((*mem_chain)->elt);
2779 : :
2780 : 36773312 : if (canon == v)
2781 : : {
2782 : 36770640 : unchain_one_elt_list (mem_chain);
2783 : 36770640 : break;
2784 : : }
2785 : :
2786 : : /* Record canonicalized elt. */
2787 : 2672 : (*mem_chain)->elt = canon;
2788 : :
2789 : 2672 : mem_chain = &(*mem_chain)->next;
2790 : 2672 : }
2791 : :
2792 : 36770640 : unchain_one_elt_loc_list (p);
2793 : : }
2794 : :
2795 : 170050109 : if (had_locs && cselib_useless_value_p (v))
2796 : : {
2797 : 8636824 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2798 : 0 : n_useless_debug_values++;
2799 : : else
2800 : 8636824 : n_useless_values++;
2801 : : }
2802 : :
2803 : 170050109 : next = v->next_containing_mem;
2804 : 170050109 : if (has_mem)
2805 : : {
2806 : 138074799 : *vp = v;
2807 : 138074799 : vp = &(*vp)->next_containing_mem;
2808 : : }
2809 : : else
2810 : 31975310 : v->next_containing_mem = NULL;
2811 : : }
2812 : 112542175 : *vp = &dummy_val;
2813 : 112542175 : }
2814 : :
2815 : : /* Invalidate DEST. */
2816 : :
2817 : : void
2818 : 523108607 : cselib_invalidate_rtx (rtx dest)
2819 : : {
2820 : 523108607 : while (GET_CODE (dest) == SUBREG
2821 : 523108607 : || GET_CODE (dest) == ZERO_EXTRACT
2822 : 1046223226 : || GET_CODE (dest) == STRICT_LOW_PART)
2823 : 6012 : dest = XEXP (dest, 0);
2824 : :
2825 : 523108607 : if (REG_P (dest))
2826 : 400598763 : cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
2827 : 122509844 : else if (MEM_P (dest))
2828 : 74197985 : cselib_invalidate_mem (dest);
2829 : 523108607 : }
2830 : :
2831 : : /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2832 : :
2833 : : static void
2834 : 507235384 : cselib_invalidate_rtx_note_stores (rtx dest, const_rtx,
2835 : : void *data ATTRIBUTE_UNUSED)
2836 : : {
2837 : 507235384 : cselib_invalidate_rtx (dest);
2838 : 507235384 : }
2839 : :
2840 : : /* Record the result of a SET instruction. DEST is being set; the source
2841 : : contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
2842 : : describes its address. */
2843 : :
2844 : : static void
2845 : 364751913 : cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
2846 : : {
2847 : 364751913 : if (src_elt == 0 || side_effects_p (dest))
2848 : 65568333 : return;
2849 : :
2850 : 299183580 : if (REG_P (dest))
2851 : : {
2852 : 275353192 : unsigned int dreg = REGNO (dest);
2853 : 275353192 : if (dreg < FIRST_PSEUDO_REGISTER)
2854 : : {
2855 : 201439388 : unsigned int n = REG_NREGS (dest);
2856 : :
2857 : 201439388 : if (n > max_value_regs)
2858 : 25380093 : max_value_regs = n;
2859 : : }
2860 : :
2861 : 275353192 : if (REG_VALUES (dreg) == 0)
2862 : : {
2863 : 169773891 : used_regs[n_used_regs++] = dreg;
2864 : 169773891 : REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
2865 : : }
2866 : : else
2867 : : {
2868 : : /* The register should have been invalidated. */
2869 : 105579301 : gcc_assert (REG_VALUES (dreg)->elt == 0);
2870 : 105579301 : REG_VALUES (dreg)->elt = src_elt;
2871 : : }
2872 : :
2873 : 275353192 : if (cselib_useless_value_p (src_elt))
2874 : 41252 : n_useless_values--;
2875 : 275353192 : new_elt_loc_list (src_elt, dest);
2876 : : }
2877 : 23830388 : else if (MEM_P (dest) && dest_addr_elt != 0
2878 : 23830388 : && cselib_record_memory)
2879 : : {
2880 : 23830388 : if (cselib_useless_value_p (src_elt))
2881 : 28 : n_useless_values--;
2882 : 23830388 : add_mem_for_addr (dest_addr_elt, src_elt, dest);
2883 : : }
2884 : : }
2885 : :
2886 : : /* Make ELT and X's VALUE equivalent to each other at INSN. */
2887 : :
2888 : : void
2889 : 3843782 : cselib_add_permanent_equiv (cselib_val *elt, rtx x, rtx_insn *insn)
2890 : : {
2891 : 3843782 : cselib_val *nelt;
2892 : 3843782 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
2893 : :
2894 : 3843782 : gcc_checking_assert (elt);
2895 : 3843782 : gcc_checking_assert (PRESERVED_VALUE_P (elt->val_rtx));
2896 : 3843782 : gcc_checking_assert (!side_effects_p (x));
2897 : :
2898 : 3843782 : cselib_current_insn = insn;
2899 : :
2900 : 3843782 : nelt = cselib_lookup (x, GET_MODE (elt->val_rtx), 1, VOIDmode);
2901 : :
2902 : 3843782 : if (nelt != elt)
2903 : : {
2904 : 3028909 : cselib_any_perm_equivs = true;
2905 : :
2906 : 3028909 : if (!PRESERVED_VALUE_P (nelt->val_rtx))
2907 : 3024069 : cselib_preserve_value (nelt);
2908 : :
2909 : 3028909 : new_elt_loc_list (nelt, elt->val_rtx);
2910 : : }
2911 : :
2912 : 3843782 : cselib_current_insn = save_cselib_current_insn;
2913 : 3843782 : }
2914 : :
2915 : : /* Return TRUE if any permanent equivalences have been recorded since
2916 : : the table was last initialized. */
2917 : : bool
2918 : 1383268039 : cselib_have_permanent_equivalences (void)
2919 : : {
2920 : 1383268039 : return cselib_any_perm_equivs;
2921 : : }
2922 : :
2923 : : /* Record stack_pointer_rtx to be equal to
2924 : : (plus:P cfa_base_preserved_val offset). Used by var-tracking
2925 : : at the start of basic blocks for !frame_pointer_needed functions. */
2926 : :
2927 : : void
2928 : 3504817 : cselib_record_sp_cfa_base_equiv (HOST_WIDE_INT offset, rtx_insn *insn)
2929 : : {
2930 : 3504817 : rtx sp_derived_value = NULL_RTX;
2931 : 7009634 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs; l; l = l->next)
2932 : 7009634 : if (GET_CODE (l->loc) == VALUE
2933 : 7009634 : && SP_DERIVED_VALUE_P (l->loc))
2934 : : {
2935 : : sp_derived_value = l->loc;
2936 : : break;
2937 : : }
2938 : 7009634 : else if (GET_CODE (l->loc) == PLUS
2939 : 3504817 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2940 : 3504817 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2941 : 10514451 : && CONST_INT_P (XEXP (l->loc, 1)))
2942 : : {
2943 : 3504817 : sp_derived_value = XEXP (l->loc, 0);
2944 : 3504817 : offset = offset + UINTVAL (XEXP (l->loc, 1));
2945 : 3504817 : break;
2946 : : }
2947 : 3504817 : if (sp_derived_value == NULL_RTX)
2948 : : return;
2949 : 3504817 : cselib_val *val
2950 : 3504817 : = cselib_lookup_from_insn (plus_constant (Pmode, sp_derived_value, offset),
2951 : 3504817 : Pmode, 1, VOIDmode, insn);
2952 : 3504817 : if (val != NULL)
2953 : : {
2954 : 3504817 : PRESERVED_VALUE_P (val->val_rtx) = 1;
2955 : 3504817 : cselib_record_set (stack_pointer_rtx, val, NULL);
2956 : : }
2957 : : }
2958 : :
2959 : : /* Return true if V is SP_DERIVED_VALUE_P (or SP_DERIVED_VALUE_P + CONST_INT)
2960 : : that can be expressed using cfa_base_preserved_val + CONST_INT. */
2961 : :
2962 : : bool
2963 : 31241713 : cselib_sp_derived_value_p (cselib_val *v)
2964 : : {
2965 : 31241713 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
2966 : 68355190 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
2967 : 37624160 : if (GET_CODE (l->loc) == PLUS
2968 : 7207449 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2969 : 6971835 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2970 : 42797614 : && CONST_INT_P (XEXP (l->loc, 1)))
2971 : 5173454 : v = CSELIB_VAL_PTR (XEXP (l->loc, 0));
2972 : 31241713 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
2973 : : return false;
2974 : 11667283 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
2975 : 11667283 : if (l->loc == cfa_base_preserved_val->val_rtx)
2976 : : return true;
2977 : 11667283 : else if (GET_CODE (l->loc) == PLUS
2978 : 5684137 : && XEXP (l->loc, 0) == cfa_base_preserved_val->val_rtx
2979 : 5684137 : && CONST_INT_P (XEXP (l->loc, 1)))
2980 : : return true;
2981 : : return false;
2982 : : }
2983 : :
2984 : : /* There is no good way to determine how many elements there can be
2985 : : in a PARALLEL. Since it's fairly cheap, use a really large number. */
2986 : : #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
2987 : :
2988 : : struct cselib_record_autoinc_data
2989 : : {
2990 : : struct cselib_set *sets;
2991 : : int n_sets;
2992 : : };
2993 : :
2994 : : /* Callback for for_each_inc_dec. Records in ARG the SETs implied by
2995 : : autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */
2996 : :
2997 : : static int
2998 : 13286210 : cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED, rtx op ATTRIBUTE_UNUSED,
2999 : : rtx dest, rtx src, rtx srcoff, void *arg)
3000 : : {
3001 : 13286210 : struct cselib_record_autoinc_data *data;
3002 : 13286210 : data = (struct cselib_record_autoinc_data *)arg;
3003 : :
3004 : 13286210 : data->sets[data->n_sets].dest = dest;
3005 : :
3006 : 13286210 : if (srcoff)
3007 : 12926555 : data->sets[data->n_sets].src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
3008 : : else
3009 : 359655 : data->sets[data->n_sets].src = src;
3010 : :
3011 : 13286210 : data->n_sets++;
3012 : :
3013 : 13286210 : return 0;
3014 : : }
3015 : :
3016 : : /* Record the effects of any sets and autoincs in INSN. */
3017 : : static void
3018 : 868779145 : cselib_record_sets (rtx_insn *insn)
3019 : : {
3020 : 868779145 : int n_sets = 0;
3021 : 868779145 : int i;
3022 : 868779145 : struct cselib_set sets[MAX_SETS];
3023 : 868779145 : rtx cond = 0;
3024 : 868779145 : int n_sets_before_autoinc;
3025 : 868779145 : int n_strict_low_parts = 0;
3026 : 868779145 : struct cselib_record_autoinc_data data;
3027 : :
3028 : 868779145 : rtx body = PATTERN (insn);
3029 : 868779145 : if (GET_CODE (body) == COND_EXEC)
3030 : : {
3031 : 0 : cond = COND_EXEC_TEST (body);
3032 : 0 : body = COND_EXEC_CODE (body);
3033 : : }
3034 : :
3035 : : /* Find all sets. */
3036 : 868779145 : if (GET_CODE (body) == SET)
3037 : : {
3038 : 366445872 : sets[0].src = SET_SRC (body);
3039 : 366445872 : sets[0].dest = SET_DEST (body);
3040 : 366445872 : n_sets = 1;
3041 : : }
3042 : 502333273 : else if (GET_CODE (body) == PARALLEL)
3043 : : {
3044 : : /* Look through the PARALLEL and record the values being
3045 : : set, if possible. Also handle any CLOBBERs. */
3046 : 211990909 : for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3047 : : {
3048 : 143023917 : rtx x = XVECEXP (body, 0, i);
3049 : :
3050 : 143023917 : if (GET_CODE (x) == SET)
3051 : : {
3052 : 74856661 : sets[n_sets].src = SET_SRC (x);
3053 : 74856661 : sets[n_sets].dest = SET_DEST (x);
3054 : 74856661 : n_sets++;
3055 : : }
3056 : : }
3057 : : }
3058 : :
3059 : 366445872 : if (n_sets == 1
3060 : 429611251 : && MEM_P (sets[0].src)
3061 : 61392005 : && !cselib_record_memory
3062 : 108261525 : && MEM_READONLY_P (sets[0].src))
3063 : : {
3064 : 3322848 : rtx note = find_reg_equal_equiv_note (insn);
3065 : :
3066 : 3322848 : if (note && CONSTANT_P (XEXP (note, 0)))
3067 : 2155041 : sets[0].src = XEXP (note, 0);
3068 : : }
3069 : :
3070 : 868779145 : data.sets = sets;
3071 : 868779145 : data.n_sets = n_sets_before_autoinc = n_sets;
3072 : 868779145 : for_each_inc_dec (PATTERN (insn), cselib_record_autoinc_cb, &data);
3073 : 868779145 : n_sets = data.n_sets;
3074 : :
3075 : : /* Look up the values that are read. Do this before invalidating the
3076 : : locations that are written. */
3077 : 1323367888 : for (i = 0; i < n_sets; i++)
3078 : : {
3079 : 454588743 : rtx dest = sets[i].dest;
3080 : 454588743 : rtx orig = dest;
3081 : :
3082 : : /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
3083 : : the low part after invalidating any knowledge about larger modes. */
3084 : 454588743 : if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
3085 : 49940 : sets[i].dest = dest = XEXP (dest, 0);
3086 : :
3087 : : /* We don't know how to record anything but REG or MEM. */
3088 : 454588743 : if (REG_P (dest)
3089 : 121302534 : || (MEM_P (dest) && cselib_record_memory))
3090 : : {
3091 : 361247096 : rtx src = sets[i].src;
3092 : 361247096 : if (cond)
3093 : 0 : src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
3094 : 361247096 : sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1, VOIDmode);
3095 : 361247096 : if (MEM_P (dest))
3096 : : {
3097 : 27960887 : machine_mode address_mode = get_address_mode (dest);
3098 : :
3099 : 27960887 : sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
3100 : : address_mode, 1,
3101 : 27960887 : GET_MODE (dest));
3102 : : }
3103 : : else
3104 : 333286209 : sets[i].dest_addr_elt = 0;
3105 : : }
3106 : :
3107 : : /* Improve handling of STRICT_LOW_PART if the current value is known
3108 : : to be const0_rtx, then the low bits will be set to dest and higher
3109 : : bits will remain zero. Used in code like:
3110 : :
3111 : : {di:SI=0;clobber flags:CC;}
3112 : : flags:CCNO=cmp(bx:SI,0)
3113 : : strict_low_part(di:QI)=flags:CCNO<=0
3114 : :
3115 : : where we can note both that di:QI=flags:CCNO<=0 and
3116 : : also that because di:SI is known to be 0 and strict_low_part(di:QI)
3117 : : preserves the upper bits that di:SI=zero_extend(flags:CCNO<=0). */
3118 : 454588743 : scalar_int_mode mode;
3119 : 454588743 : if (dest != orig
3120 : 49940 : && cselib_record_sets_hook
3121 : 18912 : && REG_P (dest)
3122 : 18912 : && HARD_REGISTER_P (dest)
3123 : 18912 : && sets[i].src_elt
3124 : 454607655 : && is_a <scalar_int_mode> (GET_MODE (dest), &mode)
3125 : 454607655 : && n_sets + n_strict_low_parts < MAX_SETS)
3126 : : {
3127 : 18912 : opt_scalar_int_mode wider_mode_iter;
3128 : 47555 : FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
3129 : : {
3130 : 47555 : scalar_int_mode wider_mode = wider_mode_iter.require ();
3131 : 54908 : if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD)
3132 : : break;
3133 : :
3134 : 46247 : rtx reg = gen_lowpart (wider_mode, dest);
3135 : 46247 : if (!REG_P (reg))
3136 : : break;
3137 : :
3138 : 46243 : cselib_val *v = cselib_lookup (reg, wider_mode, 0, VOIDmode);
3139 : 46243 : if (!v)
3140 : 28643 : continue;
3141 : :
3142 : 18607 : struct elt_loc_list *l;
3143 : 39216 : for (l = v->locs; l; l = l->next)
3144 : 38209 : if (l->loc == const0_rtx)
3145 : : break;
3146 : :
3147 : 1007 : if (!l)
3148 : 1007 : continue;
3149 : :
3150 : 17600 : sets[n_sets + n_strict_low_parts].dest = reg;
3151 : 17600 : sets[n_sets + n_strict_low_parts].src = dest;
3152 : 17600 : sets[n_sets + n_strict_low_parts++].src_elt = sets[i].src_elt;
3153 : 17600 : break;
3154 : : }
3155 : : }
3156 : : }
3157 : :
3158 : 868779145 : if (cselib_record_sets_hook)
3159 : 77658406 : cselib_record_sets_hook (insn, sets, n_sets);
3160 : :
3161 : : /* Invalidate all locations written by this insn. Note that the elts we
3162 : : looked up in the previous loop aren't affected, just some of their
3163 : : locations may go away. */
3164 : 868779145 : note_pattern_stores (body, cselib_invalidate_rtx_note_stores, NULL);
3165 : :
3166 : 1750844500 : for (i = n_sets_before_autoinc; i < n_sets; i++)
3167 : 13286210 : cselib_invalidate_rtx (sets[i].dest);
3168 : :
3169 : : /* If this is an asm, look for duplicate sets. This can happen when the
3170 : : user uses the same value as an output multiple times. This is valid
3171 : : if the outputs are not actually used thereafter. Treat this case as
3172 : : if the value isn't actually set. We do this by smashing the destination
3173 : : to pc_rtx, so that we won't record the value later. */
3174 : 868779145 : if (n_sets >= 2 && asm_noperands (body) >= 0)
3175 : : {
3176 : 448201 : for (i = 0; i < n_sets; i++)
3177 : : {
3178 : 348884 : rtx dest = sets[i].dest;
3179 : 348884 : if (REG_P (dest) || MEM_P (dest))
3180 : : {
3181 : 348851 : int j;
3182 : 827913 : for (j = i + 1; j < n_sets; j++)
3183 : 479062 : if (rtx_equal_p (dest, sets[j].dest))
3184 : : {
3185 : 0 : sets[i].dest = pc_rtx;
3186 : 0 : sets[j].dest = pc_rtx;
3187 : : }
3188 : : }
3189 : : }
3190 : : }
3191 : :
3192 : : /* Now enter the equivalences in our tables. */
3193 : 1323367888 : for (i = 0; i < n_sets; i++)
3194 : : {
3195 : 454588743 : rtx dest = sets[i].dest;
3196 : 454588743 : if (REG_P (dest)
3197 : 121302534 : || (MEM_P (dest) && cselib_record_memory))
3198 : 361247096 : cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
3199 : : }
3200 : :
3201 : : /* And deal with STRICT_LOW_PART. */
3202 : 868796745 : for (i = 0; i < n_strict_low_parts; i++)
3203 : : {
3204 : 17600 : if (! PRESERVED_VALUE_P (sets[n_sets + i].src_elt->val_rtx))
3205 : 0 : continue;
3206 : 17600 : machine_mode dest_mode = GET_MODE (sets[n_sets + i].dest);
3207 : 17600 : cselib_val *v
3208 : 17600 : = cselib_lookup (sets[n_sets + i].dest, dest_mode, 1, VOIDmode);
3209 : 17600 : cselib_preserve_value (v);
3210 : 17600 : rtx r = gen_rtx_ZERO_EXTEND (dest_mode,
3211 : : sets[n_sets + i].src_elt->val_rtx);
3212 : 17600 : cselib_add_permanent_equiv (v, r, insn);
3213 : : }
3214 : 868779145 : }
3215 : :
3216 : : /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
3217 : :
3218 : : bool
3219 : 38475564 : fp_setter_insn (rtx_insn *insn)
3220 : : {
3221 : 38475564 : rtx expr, pat = NULL_RTX;
3222 : :
3223 : 38475564 : if (!RTX_FRAME_RELATED_P (insn))
3224 : : return false;
3225 : :
3226 : 606307 : expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
3227 : 606307 : if (expr)
3228 : 53 : pat = XEXP (expr, 0);
3229 : 606307 : if (!modified_in_p (hard_frame_pointer_rtx, pat ? pat : insn))
3230 : : return false;
3231 : :
3232 : : /* Don't return true for frame pointer restores in the epilogue. */
3233 : 149406 : if (find_reg_note (insn, REG_CFA_RESTORE, hard_frame_pointer_rtx))
3234 : : return false;
3235 : : return true;
3236 : : }
3237 : :
3238 : : /* V is one of the values in REG_VALUES (REGNO). Return true if it
3239 : : would be invalidated by CALLEE_ABI. */
3240 : :
3241 : : static bool
3242 : 113824711 : cselib_invalidated_by_call_p (const function_abi &callee_abi,
3243 : : unsigned int regno, cselib_val *v)
3244 : : {
3245 : 113824711 : machine_mode mode = GET_MODE (v->val_rtx);
3246 : 113824711 : if (mode == VOIDmode)
3247 : : {
3248 : 0 : v = REG_VALUES (regno)->elt;
3249 : 0 : if (!v)
3250 : : /* If we don't know what the mode of the constant value is, and we
3251 : : don't know what mode the register was set in, conservatively
3252 : : assume that the register is clobbered. The value's going to be
3253 : : essentially useless in this case anyway. */
3254 : : return true;
3255 : 0 : mode = GET_MODE (v->val_rtx);
3256 : : }
3257 : 113824711 : return callee_abi.clobbers_reg_p (mode, regno);
3258 : : }
3259 : :
3260 : : /* Record the effects of INSN. */
3261 : :
3262 : : void
3263 : 1003184242 : cselib_process_insn (rtx_insn *insn)
3264 : : {
3265 : 1003184242 : int i;
3266 : 1003184242 : rtx x;
3267 : :
3268 : 1003184242 : cselib_current_insn = insn;
3269 : :
3270 : : /* Forget everything at a CODE_LABEL or a setjmp. */
3271 : 1003184242 : if ((LABEL_P (insn)
3272 : 967675904 : || (CALL_P (insn)
3273 : 33898133 : && find_reg_note (insn, REG_SETJMP, NULL)))
3274 : 1003188290 : && !cselib_preserve_constants)
3275 : : {
3276 : 35512172 : cselib_reset_table (next_uid);
3277 : 35512172 : cselib_current_insn = NULL;
3278 : 35512172 : return;
3279 : : }
3280 : :
3281 : 967672070 : if (! INSN_P (insn))
3282 : : {
3283 : 98892925 : cselib_current_insn = NULL;
3284 : 98892925 : return;
3285 : : }
3286 : :
3287 : : /* If this is a call instruction, forget anything stored in a
3288 : : call clobbered register, or, if this is not a const call, in
3289 : : memory. */
3290 : 868779145 : if (CALL_P (insn))
3291 : : {
3292 : 33894299 : function_abi callee_abi = insn_callee_abi (insn);
3293 : 3152169807 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3294 : : {
3295 : 3118275508 : elt_list **l = ®_VALUES (i);
3296 : 3339947352 : while (*l)
3297 : : {
3298 : 221671844 : cselib_val *v = (*l)->elt;
3299 : 221671844 : if (v && cselib_invalidated_by_call_p (callee_abi, i, v))
3300 : 70875304 : cselib_invalidate_regno_val (i, l);
3301 : : else
3302 : 150796540 : l = &(*l)->next;
3303 : : }
3304 : : }
3305 : :
3306 : : /* Since it is not clear how cselib is going to be used, be
3307 : : conservative here and treat looping pure or const functions
3308 : : as if they were regular functions. */
3309 : 33894299 : if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
3310 : 33894299 : || !(RTL_CONST_OR_PURE_CALL_P (insn)))
3311 : 30777667 : cselib_invalidate_mem (callmem[0]);
3312 : : else
3313 : : {
3314 : : /* For const/pure calls, invalidate any argument slots because
3315 : : they are owned by the callee. */
3316 : 8980969 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3317 : 5864337 : if (GET_CODE (XEXP (x, 0)) == USE
3318 : 5864061 : && MEM_P (XEXP (XEXP (x, 0), 0)))
3319 : 31677 : cselib_invalidate_mem (XEXP (XEXP (x, 0), 0));
3320 : : /* And invalidate memory below the stack (or above for
3321 : : !STACK_GROWS_DOWNWARD), as even const/pure call can invalidate
3322 : : that. Do this only if !ACCUMULATE_OUTGOING_ARGS or if
3323 : : cfun->calls_alloca, otherwise the stack pointer shouldn't be
3324 : : changing in the middle of the function and nothing should be
3325 : : stored below the stack pointer. */
3326 : 3116632 : if (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca)
3327 : 3116183 : cselib_invalidate_mem (callmem[1]);
3328 : : }
3329 : : }
3330 : :
3331 : 868779145 : cselib_record_sets (insn);
3332 : :
3333 : : /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
3334 : : after we have processed the insn. */
3335 : 868779145 : if (CALL_P (insn))
3336 : : {
3337 : 96426156 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3338 : 62531857 : if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3339 : 1856944 : cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
3340 : :
3341 : : /* Flush everything on setjmp. */
3342 : 33894299 : if (cselib_preserve_constants
3343 : 33894299 : && find_reg_note (insn, REG_SETJMP, NULL))
3344 : : {
3345 : 214 : cselib_preserve_only_values ();
3346 : 214 : cselib_reset_table (next_uid);
3347 : : }
3348 : : }
3349 : :
3350 : : /* On setter of the hard frame pointer if frame_pointer_needed,
3351 : : invalidate stack_pointer_rtx, so that sp and {,h}fp based
3352 : : VALUEs are distinct. */
3353 : 868779145 : if (reload_completed
3354 : 397521368 : && frame_pointer_needed
3355 : 907138308 : && fp_setter_insn (insn))
3356 : 91293 : cselib_invalidate_rtx (stack_pointer_rtx);
3357 : :
3358 : 868779145 : cselib_current_insn = NULL;
3359 : :
3360 : 868779145 : if (n_useless_values > MAX_USELESS_VALUES
3361 : : /* remove_useless_values is linear in the hash table size. Avoid
3362 : : quadratic behavior for very large hashtables with very few
3363 : : useless elements. */
3364 : 868779145 : && ((unsigned int)n_useless_values
3365 : 2222768 : > (cselib_hash_table->elements () - n_debug_values) / 4))
3366 : 31682 : remove_useless_values ();
3367 : : }
3368 : :
3369 : : /* Initialize cselib for one pass. The caller must also call
3370 : : init_alias_analysis. */
3371 : :
3372 : : void
3373 : 10044511 : cselib_init (int record_what)
3374 : : {
3375 : 10044511 : cselib_record_memory = record_what & CSELIB_RECORD_MEMORY;
3376 : 10044511 : cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS;
3377 : 10044511 : cselib_any_perm_equivs = false;
3378 : :
3379 : : /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
3380 : : see canon_true_dependence. This is only created once. */
3381 : 10044511 : if (! callmem[0])
3382 : 140936 : callmem[0] = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
3383 : : /* Similarly create a MEM representing roughly everything below
3384 : : the stack for STACK_GROWS_DOWNWARD targets or everything above
3385 : : it otherwise. Do this only when !ACCUMULATE_OUTGOING_ARGS or
3386 : : if cfun->calls_alloca, otherwise the stack pointer shouldn't be
3387 : : changing in the middle of the function and nothing should be stored
3388 : : below the stack pointer. */
3389 : 10044511 : if (!callmem[1] && (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca))
3390 : : {
3391 : 140687 : if (STACK_GROWS_DOWNWARD)
3392 : : {
3393 : 140687 : unsigned HOST_WIDE_INT off = -(GET_MODE_MASK (Pmode) >> 1);
3394 : : #ifdef STACK_ADDRESS_OFFSET
3395 : : /* On SPARC take stack pointer bias into account as well. */
3396 : : off += (STACK_ADDRESS_OFFSET
3397 : : - FIRST_PARM_OFFSET (current_function_decl));
3398 : : #endif
3399 : 140687 : callmem[1] = plus_constant (Pmode, stack_pointer_rtx, off);
3400 : : }
3401 : : else
3402 : : callmem[1] = stack_pointer_rtx;
3403 : 140687 : callmem[1] = gen_rtx_MEM (BLKmode, callmem[1]);
3404 : 146049 : set_mem_size (callmem[1], GET_MODE_MASK (Pmode) >> 1);
3405 : : }
3406 : :
3407 : 10044511 : cselib_nregs = max_reg_num ();
3408 : :
3409 : : /* We preserve reg_values to allow expensive clearing of the whole thing.
3410 : : Reallocate it however if it happens to be too large. */
3411 : 10044511 : if (!reg_values || reg_values_size < cselib_nregs
3412 : 9749622 : || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
3413 : : {
3414 : 310097 : free (reg_values);
3415 : : /* Some space for newly emit instructions so we don't end up
3416 : : reallocating in between passes. */
3417 : 310097 : reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
3418 : 310097 : reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
3419 : : }
3420 : 10044511 : used_regs = XNEWVEC (unsigned int, cselib_nregs);
3421 : 10044511 : n_used_regs = 0;
3422 : : /* FIXME: enable sanitization (PR87845) */
3423 : 10044511 : cselib_hash_table
3424 : 10044511 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3425 : 10044511 : /* sanitize_eq_and_hash */ false);
3426 : 10044511 : if (cselib_preserve_constants)
3427 : 496634 : cselib_preserved_hash_table
3428 : 496634 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3429 : 496634 : /* sanitize_eq_and_hash */ false);
3430 : 10044511 : next_uid = 1;
3431 : 10044511 : }
3432 : :
3433 : : /* Called when the current user is done with cselib. */
3434 : :
3435 : : void
3436 : 10044511 : cselib_finish (void)
3437 : : {
3438 : 10044511 : bool preserved = cselib_preserve_constants;
3439 : 10044511 : cselib_discard_hook = NULL;
3440 : 10044511 : cselib_preserve_constants = false;
3441 : 10044511 : cselib_any_perm_equivs = false;
3442 : 10044511 : cfa_base_preserved_val = NULL;
3443 : 10044511 : cfa_base_preserved_regno = INVALID_REGNUM;
3444 : 10044511 : elt_list_pool.release ();
3445 : 10044511 : elt_loc_list_pool.release ();
3446 : 10044511 : cselib_val_pool.release ();
3447 : 10044511 : value_pool.release ();
3448 : 10044511 : cselib_clear_table ();
3449 : 10044511 : delete cselib_hash_table;
3450 : 10044511 : cselib_hash_table = NULL;
3451 : 10044511 : if (preserved)
3452 : 496634 : delete cselib_preserved_hash_table;
3453 : 10044511 : cselib_preserved_hash_table = NULL;
3454 : 10044511 : free (used_regs);
3455 : 10044511 : used_regs = 0;
3456 : 10044511 : n_useless_values = 0;
3457 : 10044511 : n_useless_debug_values = 0;
3458 : 10044511 : n_debug_values = 0;
3459 : 10044511 : next_uid = 0;
3460 : 10044511 : }
3461 : :
3462 : : /* Dump the cselib_val *X to FILE *OUT. */
3463 : :
3464 : : int
3465 : 120 : dump_cselib_val (cselib_val **x, FILE *out)
3466 : : {
3467 : 120 : cselib_val *v = *x;
3468 : 120 : bool need_lf = true;
3469 : :
3470 : 120 : print_inline_rtx (out, v->val_rtx, 0);
3471 : :
3472 : 120 : if (v->locs)
3473 : : {
3474 : 113 : struct elt_loc_list *l = v->locs;
3475 : 113 : if (need_lf)
3476 : : {
3477 : 113 : fputc ('\n', out);
3478 : 113 : need_lf = false;
3479 : : }
3480 : 113 : fputs (" locs:", out);
3481 : 200 : do
3482 : : {
3483 : 200 : if (l->setting_insn)
3484 : 200 : fprintf (out, "\n from insn %i ",
3485 : 200 : INSN_UID (l->setting_insn));
3486 : : else
3487 : 0 : fprintf (out, "\n ");
3488 : 200 : print_inline_rtx (out, l->loc, 4);
3489 : : }
3490 : 200 : while ((l = l->next));
3491 : 113 : fputc ('\n', out);
3492 : : }
3493 : : else
3494 : : {
3495 : 7 : fputs (" no locs", out);
3496 : 7 : need_lf = true;
3497 : : }
3498 : :
3499 : 120 : if (v->addr_list)
3500 : : {
3501 : 7 : struct elt_list *e = v->addr_list;
3502 : 7 : if (need_lf)
3503 : : {
3504 : 0 : fputc ('\n', out);
3505 : 0 : need_lf = false;
3506 : : }
3507 : 7 : fputs (" addr list:", out);
3508 : 7 : do
3509 : : {
3510 : 7 : fputs ("\n ", out);
3511 : 7 : print_inline_rtx (out, e->elt->val_rtx, 2);
3512 : : }
3513 : 7 : while ((e = e->next));
3514 : 7 : fputc ('\n', out);
3515 : : }
3516 : : else
3517 : : {
3518 : 113 : fputs (" no addrs", out);
3519 : 113 : need_lf = true;
3520 : : }
3521 : :
3522 : 120 : if (v->next_containing_mem == &dummy_val)
3523 : 7 : fputs (" last mem\n", out);
3524 : 113 : else if (v->next_containing_mem)
3525 : : {
3526 : 0 : fputs (" next mem ", out);
3527 : 0 : print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
3528 : 0 : fputc ('\n', out);
3529 : : }
3530 : 113 : else if (need_lf)
3531 : 106 : fputc ('\n', out);
3532 : :
3533 : 120 : return 1;
3534 : : }
3535 : :
3536 : : /* Dump to OUT everything in the CSELIB table. */
3537 : :
3538 : : void
3539 : 12 : dump_cselib_table (FILE *out)
3540 : : {
3541 : 12 : fprintf (out, "cselib hash table:\n");
3542 : 132 : cselib_hash_table->traverse <FILE *, dump_cselib_val> (out);
3543 : 12 : fprintf (out, "cselib preserved hash table:\n");
3544 : 12 : cselib_preserved_hash_table->traverse <FILE *, dump_cselib_val> (out);
3545 : 12 : if (first_containing_mem != &dummy_val)
3546 : : {
3547 : 7 : fputs ("first mem ", out);
3548 : 7 : print_inline_rtx (out, first_containing_mem->val_rtx, 2);
3549 : 7 : fputc ('\n', out);
3550 : : }
3551 : 12 : fprintf (out, "next uid %i\n", next_uid);
3552 : 12 : }
3553 : :
3554 : : #include "gt-cselib.h"
|
