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 : 97066479 : cselib_hasher::hash (const cselib_val *v)
118 : : {
119 : 97066479 : 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 : 540145564 : cselib_hasher::equal (const cselib_val *v, const key *x_arg)
129 : : {
130 : 540145564 : struct elt_loc_list *l;
131 : 540145564 : rtx x = x_arg->x;
132 : 540145564 : machine_mode mode = x_arg->mode;
133 : 540145564 : machine_mode memmode = x_arg->memmode;
134 : :
135 : 540145564 : if (mode != GET_MODE (v->val_rtx))
136 : : return false;
137 : :
138 : 433968198 : if (GET_CODE (x) == VALUE)
139 : 11882028 : return x == v->val_rtx;
140 : :
141 : 422086170 : if (SP_DERIVED_VALUE_P (v->val_rtx) && GET_MODE (x) == Pmode)
142 : : {
143 : 17088015 : rtx xoff = NULL;
144 : 17088015 : if (autoinc_split (x, &xoff, memmode) == v->val_rtx && xoff == NULL_RTX)
145 : 7761397 : 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 : 709970919 : for (l = v->locs; l; l = l->next)
151 : 461601643 : if (l->setting_insn && DEBUG_INSN_P (l->setting_insn)
152 : 32049450 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
153 : : {
154 : 9784084 : 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 : 9784084 : cselib_current_insn = l->setting_insn;
160 : 9784084 : bool match = rtx_equal_for_cselib_1 (l->loc, x, memmode, 0);
161 : 9784084 : cselib_current_insn = save_cselib_current_insn;
162 : 9784084 : if (match)
163 : : {
164 : 842554 : promote_debug_loc (l);
165 : 842554 : return true;
166 : : }
167 : : }
168 : 451817559 : 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 : 451750891 : new_elt_list (struct elt_list *next, cselib_val *elt)
300 : : {
301 : 903501782 : elt_list *el = elt_list_pool.allocate ();
302 : 451750891 : el->next = next;
303 : 451750891 : el->elt = elt;
304 : 451750891 : 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 : 677441859 : new_elt_loc_list (cselib_val *val, rtx loc)
312 : : {
313 : 681342521 : struct elt_loc_list *el, *next = val->locs;
314 : :
315 : 681342521 : 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 : 396489407 : if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
322 : 6028234 : n_debug_values++;
323 : :
324 : 681342521 : val = canonical_cselib_val (val);
325 : 681342521 : next = val->locs;
326 : :
327 : 681342521 : if (GET_CODE (loc) == VALUE)
328 : : {
329 : 7806654 : loc = canonical_cselib_val (CSELIB_VAL_PTR (loc))->val_rtx;
330 : :
331 : 7806654 : gcc_checking_assert (PRESERVED_VALUE_P (loc)
332 : : == PRESERVED_VALUE_P (val->val_rtx));
333 : :
334 : 7806654 : if (val->val_rtx == loc)
335 : : return;
336 : 7801398 : 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 : 3900736 : gcc_checking_assert (val->uid < CSELIB_VAL_PTR (loc)->uid);
344 : :
345 : 3900736 : if (CSELIB_VAL_PTR (loc)->locs)
346 : : {
347 : : /* Bring all locs from LOC to VAL. */
348 : 2798108 : 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 : 16 : 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 : 2798092 : el->next = val->locs;
360 : 2798092 : next = val->locs = CSELIB_VAL_PTR (loc)->locs;
361 : : }
362 : :
363 : 3900736 : 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 : 2 : while (last->next)
368 : : last = last->next;
369 : 2 : last->next = val->addr_list;
370 : 2 : val->addr_list = CSELIB_VAL_PTR (loc)->addr_list;
371 : 2 : CSELIB_VAL_PTR (loc)->addr_list = NULL;
372 : : }
373 : :
374 : 3900736 : 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 : 3900736 : el = elt_loc_list_pool.allocate ();
386 : 3900736 : el->loc = val->val_rtx;
387 : 3900736 : el->setting_insn = cselib_current_insn;
388 : 3900736 : el->next = NULL;
389 : 3900736 : CSELIB_VAL_PTR (loc)->locs = el;
390 : : }
391 : :
392 : 677436603 : el = elt_loc_list_pool.allocate ();
393 : 677436603 : el->loc = loc;
394 : 677436603 : el->setting_insn = cselib_current_insn;
395 : 677436603 : el->next = next;
396 : 677436603 : 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 : 1143697628 : promote_debug_loc (struct elt_loc_list *l)
405 : : {
406 : 1143697628 : if (l && l->setting_insn && DEBUG_INSN_P (l->setting_insn)
407 : 18654139 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
408 : : {
409 : 2319997 : n_debug_values--;
410 : 2319997 : l->setting_insn = cselib_current_insn;
411 : 2319997 : if (cselib_preserve_constants && l->next)
412 : : {
413 : 19460 : gcc_assert (l->next->setting_insn
414 : : && DEBUG_INSN_P (l->next->setting_insn)
415 : : && !l->next->next);
416 : 19460 : l->next->setting_insn = cselib_current_insn;
417 : : }
418 : : else
419 : 2300537 : gcc_assert (!l->next);
420 : : }
421 : 1143697628 : }
422 : :
423 : : /* The elt_list at *PL is no longer needed. Unchain it and free its
424 : : storage. */
425 : :
426 : : static inline void
427 : 75134264 : unchain_one_elt_list (struct elt_list **pl)
428 : : {
429 : 75134264 : struct elt_list *l = *pl;
430 : :
431 : 75134264 : *pl = l->next;
432 : 109959896 : elt_list_pool.remove (l);
433 : 40308632 : }
434 : :
435 : : /* Likewise for elt_loc_lists. */
436 : :
437 : : static void
438 : 212802490 : unchain_one_elt_loc_list (struct elt_loc_list **pl)
439 : : {
440 : 212802490 : struct elt_loc_list *l = *pl;
441 : :
442 : 212802490 : *pl = l->next;
443 : 0 : elt_loc_list_pool.remove (l);
444 : 36220994 : }
445 : :
446 : : /* Likewise for cselib_vals. This also frees the addr_list associated with
447 : : V. */
448 : :
449 : : static void
450 : 2620454 : unchain_one_value (cselib_val *v)
451 : : {
452 : 2639143 : while (v->addr_list)
453 : 18689 : unchain_one_elt_list (&v->addr_list);
454 : :
455 : 2620454 : cselib_val_pool.remove (v);
456 : 2620454 : }
457 : :
458 : : /* Remove all entries from the hash table. Also used during
459 : : initialization. */
460 : :
461 : : void
462 : 56874083 : cselib_clear_table (void)
463 : : {
464 : 56874083 : cselib_reset_table (1);
465 : 56874083 : }
466 : :
467 : : /* Return TRUE if V is a constant, a function invariant or a VALUE
468 : : equivalence; FALSE otherwise. */
469 : :
470 : : static bool
471 : 53719370 : invariant_or_equiv_p (cselib_val *v)
472 : : {
473 : 53719370 : struct elt_loc_list *l;
474 : :
475 : 53719370 : if (v == cfa_base_preserved_val)
476 : : return true;
477 : :
478 : : /* Keep VALUE equivalences around. */
479 : 74483401 : for (l = v->locs; l; l = l->next)
480 : 36088130 : if (GET_CODE (l->loc) == VALUE)
481 : : return true;
482 : :
483 : 38395271 : if (v->locs != NULL
484 : 21039560 : && v->locs->next == NULL)
485 : : {
486 : 20979061 : if (CONSTANT_P (v->locs->loc)
487 : 20979061 : && (GET_CODE (v->locs->loc) != CONST
488 : 150188 : || !references_value_p (v->locs->loc, 0)))
489 : 3327147 : 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 : 17651914 : if (GET_CODE (v->locs->loc) == DEBUG_EXPR
494 : 16300798 : || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR
495 : 15933110 : || GET_CODE (v->locs->loc) == ENTRY_VALUE
496 : 15932943 : || 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 : 15921277 : if (GET_CODE (v->locs->loc) == PLUS
501 : 9842530 : && CONST_INT_P (XEXP (v->locs->loc, 1))
502 : 8780096 : && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE
503 : 24171886 : && 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 : 41413780 : preserve_constants_and_equivs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
515 : : {
516 : 41413780 : cselib_val *v = *x;
517 : :
518 : 41413780 : if (invariant_or_equiv_p (v))
519 : : {
520 : 16326902 : cselib_hasher::key lookup = {
521 : 16326902 : GET_MODE (v->val_rtx), v->val_rtx, VOIDmode
522 : 16326902 : };
523 : 16326902 : cselib_val **slot
524 : 16326902 : = cselib_preserved_hash_table->find_slot_with_hash (&lookup,
525 : : v->hash, INSERT);
526 : 16326902 : gcc_assert (!*slot);
527 : 16326902 : *slot = v;
528 : : }
529 : :
530 : 41413780 : cselib_hash_table->clear_slot (x);
531 : :
532 : 41413780 : 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 : 93796704 : cselib_reset_table (unsigned int num)
540 : : {
541 : 93796704 : unsigned int i;
542 : :
543 : 93796704 : max_value_regs = 0;
544 : :
545 : 93796704 : if (cfa_base_preserved_val)
546 : : {
547 : 4054981 : unsigned int regno = cfa_base_preserved_regno;
548 : 4054981 : unsigned int new_used_regs = 0;
549 : 28743082 : for (i = 0; i < n_used_regs; i++)
550 : 24688101 : if (used_regs[i] == regno)
551 : : {
552 : 4054981 : new_used_regs = 1;
553 : 4054981 : continue;
554 : : }
555 : : else
556 : 20633120 : REG_VALUES (used_regs[i]) = 0;
557 : 4054981 : gcc_assert (new_used_regs == 1);
558 : 4054981 : n_used_regs = new_used_regs;
559 : 4054981 : used_regs[0] = regno;
560 : 4054981 : max_value_regs
561 : 4054981 : = hard_regno_nregs (regno,
562 : 4054981 : 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 : 4054981 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs;
567 : 8109962 : l; l = l->next)
568 : 8109962 : if (GET_CODE (l->loc) == PLUS
569 : 4054981 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
570 : 4054981 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
571 : 12164943 : && CONST_INT_P (XEXP (l->loc, 1)))
572 : : {
573 : 4054981 : 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 : 344695319 : for (i = 0; i < n_used_regs; i++)
589 : 254953596 : REG_VALUES (used_regs[i]) = 0;
590 : 89741723 : n_used_regs = 0;
591 : : }
592 : :
593 : 93796704 : if (cselib_preserve_constants)
594 : 45468761 : cselib_hash_table->traverse <void *, preserve_constants_and_equivs> (NULL);
595 : : else
596 : : {
597 : 89741723 : cselib_hash_table->empty ();
598 : 89741723 : gcc_checking_assert (!cselib_any_perm_equivs);
599 : : }
600 : :
601 : 93796704 : n_useless_values = 0;
602 : 93796704 : n_useless_debug_values = 0;
603 : 93796704 : n_debug_values = 0;
604 : :
605 : 93796704 : next_uid = num;
606 : :
607 : 93796704 : first_containing_mem = &dummy_val;
608 : 93796704 : }
609 : :
610 : : /* Return the number of the next value that will be generated. */
611 : :
612 : : unsigned int
613 : 4532256 : cselib_get_next_uid (void)
614 : : {
615 : 4532256 : 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 : 670088688 : cselib_find_slot (machine_mode mode, rtx x, hashval_t hash,
624 : : enum insert_option insert, machine_mode memmode)
625 : : {
626 : 670088688 : cselib_val **slot = NULL;
627 : 670088688 : cselib_hasher::key lookup = { mode, x, memmode };
628 : 670088688 : if (cselib_preserve_constants)
629 : 147699639 : slot = cselib_preserved_hash_table->find_slot_with_hash (&lookup, hash,
630 : : NO_INSERT);
631 : 147699639 : if (!slot)
632 : 619577330 : slot = cselib_hash_table->find_slot_with_hash (&lookup, hash, insert);
633 : 670088688 : 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 : 1169129005 : references_value_p (const_rtx x, int only_useless)
643 : : {
644 : 1169129005 : const enum rtx_code code = GET_CODE (x);
645 : 1169129005 : const char *fmt = GET_RTX_FORMAT (code);
646 : 1169129005 : int i, j;
647 : :
648 : 1169129005 : if (GET_CODE (x) == VALUE
649 : 1169129005 : && (! only_useless
650 : 412700598 : || (CSELIB_VAL_PTR (x)->locs == 0 && !PRESERVED_VALUE_P (x))))
651 : : return true;
652 : :
653 : 2673192709 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
654 : : {
655 : 1507068961 : if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
656 : : return true;
657 : 1505560199 : else if (fmt[i] == 'E')
658 : 42421195 : for (j = 0; j < XVECLEN (x, i); j++)
659 : 35108286 : 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 : 1125434598 : cselib_useless_value_p (cselib_val *v)
670 : : {
671 : 1125434598 : return (v->locs == 0
672 : 75568841 : && !PRESERVED_VALUE_P (v->val_rtx)
673 : 1169954832 : && !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 : 509216856 : discard_useless_locs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
682 : : {
683 : 509216856 : cselib_val *v = *x;
684 : 509216856 : struct elt_loc_list **p = &v->locs;
685 : 509216856 : bool had_locs = v->locs != NULL;
686 : 509216856 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
687 : :
688 : 1077314522 : while (*p)
689 : : {
690 : 568097666 : if (references_value_p ((*p)->loc, 1))
691 : 1395362 : unchain_one_elt_loc_list (p);
692 : : else
693 : 566702304 : p = &(*p)->next;
694 : : }
695 : :
696 : 509216856 : if (had_locs && cselib_useless_value_p (v))
697 : : {
698 : 1265231 : if (setting_insn && DEBUG_INSN_P (setting_insn))
699 : 2 : n_useless_debug_values++;
700 : : else
701 : 1265229 : n_useless_values++;
702 : 1265231 : values_became_useless = 1;
703 : : }
704 : 509216856 : return 1;
705 : : }
706 : :
707 : : /* If X is a value with no locations, remove it from the hashtable. */
708 : :
709 : : int
710 : 45780220 : discard_useless_values (cselib_val **x, void *info ATTRIBUTE_UNUSED)
711 : : {
712 : 45780220 : cselib_val *v = *x;
713 : :
714 : 45780220 : if (v->locs == 0 && cselib_useless_value_p (v))
715 : : {
716 : 2620454 : if (cselib_discard_hook)
717 : 511378 : cselib_discard_hook (v);
718 : :
719 : 2620454 : CSELIB_VAL_PTR (v->val_rtx) = NULL;
720 : 2620454 : cselib_hash_table->clear_slot (x);
721 : 2620454 : unchain_one_value (v);
722 : 2620454 : n_useless_values--;
723 : : }
724 : :
725 : 45780220 : 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 : 4086375 : remove_useless_values (void)
733 : : {
734 : 4144613 : cselib_val **p, *v;
735 : :
736 : : /* First pass: eliminate locations that reference the value. That in
737 : : turn can make more values useless. */
738 : 4144613 : do
739 : : {
740 : 4144613 : values_became_useless = 0;
741 : 513361469 : cselib_hash_table->traverse <void *, discard_useless_locs> (NULL);
742 : : }
743 : 4144613 : while (values_became_useless);
744 : :
745 : : /* Second pass: actually remove the values. */
746 : :
747 : 4086375 : p = &first_containing_mem;
748 : 4217989 : for (v = *p; v != &dummy_val; v = v->next_containing_mem)
749 : 131614 : if (v->locs && v == canonical_cselib_val (v))
750 : : {
751 : 129128 : *p = v;
752 : 129128 : p = &(*p)->next_containing_mem;
753 : : }
754 : 4086375 : *p = &dummy_val;
755 : :
756 : 4086375 : if (cselib_preserve_constants)
757 : 4054981 : cselib_preserved_hash_table->traverse <void *,
758 : 4054981 : discard_useless_locs> (NULL);
759 : 4086375 : gcc_assert (!values_became_useless);
760 : :
761 : 4086375 : n_useless_values += n_useless_debug_values;
762 : 4086375 : n_debug_values -= n_useless_debug_values;
763 : 4086375 : n_useless_debug_values = 0;
764 : :
765 : 49866595 : cselib_hash_table->traverse <void *, discard_useless_values> (NULL);
766 : :
767 : 4086375 : gcc_assert (!n_useless_values);
768 : 4086375 : }
769 : :
770 : : /* Arrange for a value to not be removed from the hash table even if
771 : : it becomes useless. */
772 : :
773 : : void
774 : 41989093 : cselib_preserve_value (cselib_val *v)
775 : : {
776 : 41989093 : PRESERVED_VALUE_P (v->val_rtx) = 1;
777 : 41989093 : }
778 : :
779 : : /* Test whether a value is preserved. */
780 : :
781 : : bool
782 : 242749896 : cselib_preserved_value_p (cselib_val *v)
783 : : {
784 : 242749896 : 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 : 954019 : cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)
792 : : {
793 : 954019 : if (cselib_preserve_constants
794 : 954019 : && v->locs
795 : 954019 : && REG_P (v->locs->loc))
796 : : {
797 : 477567 : cfa_base_preserved_val = v;
798 : 477567 : cfa_base_preserved_regno = regno;
799 : : }
800 : 954019 : }
801 : :
802 : : /* Clean all non-constant expressions in the hash table, but retain
803 : : their values. */
804 : :
805 : : void
806 : 4054981 : cselib_preserve_only_values (void)
807 : : {
808 : 4054981 : int i;
809 : :
810 : 377113233 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
811 : 373058252 : cselib_invalidate_regno (i, reg_raw_mode[i]);
812 : :
813 : 4054981 : cselib_invalidate_mem (callmem[0]);
814 : :
815 : 4054981 : remove_useless_values ();
816 : :
817 : 4054981 : gcc_assert (first_containing_mem == &dummy_val);
818 : 4054981 : }
819 : :
820 : : /* Arrange for a value to be marked as based on stack pointer
821 : : for find_base_term purposes. */
822 : :
823 : : void
824 : 1978496 : cselib_set_value_sp_based (cselib_val *v)
825 : : {
826 : 1978496 : SP_BASED_VALUE_P (v->val_rtx) = 1;
827 : 1978496 : }
828 : :
829 : : /* Test whether a value is based on stack pointer for
830 : : find_base_term purposes. */
831 : :
832 : : bool
833 : 822728332 : cselib_sp_based_value_p (cselib_val *v)
834 : : {
835 : 822728332 : 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 : 105861320 : cselib_reg_set_mode (const_rtx x)
845 : : {
846 : 105861320 : if (!REG_P (x))
847 : 31509233 : return GET_MODE (x);
848 : :
849 : 74352087 : if (REG_VALUES (REGNO (x)) == NULL
850 : 74352087 : || REG_VALUES (REGNO (x))->elt == NULL)
851 : : return VOIDmode;
852 : :
853 : 23023501 : 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 : 1339536433 : autoinc_split (rtx x, rtx *off, machine_mode memmode)
861 : : {
862 : 1339536433 : switch (GET_CODE (x))
863 : : {
864 : 748166075 : case PLUS:
865 : 748166075 : *off = XEXP (x, 1);
866 : 748166075 : x = XEXP (x, 0);
867 : 748166075 : break;
868 : :
869 : 12575151 : case PRE_DEC:
870 : 12575151 : if (memmode == VOIDmode)
871 : : return x;
872 : :
873 : 25150302 : *off = gen_int_mode (-GET_MODE_SIZE (memmode), GET_MODE (x));
874 : 12575151 : x = XEXP (x, 0);
875 : 12575151 : 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 : 1727315 : case PRE_MODIFY:
886 : 1727315 : x = XEXP (x, 1);
887 : 1727315 : break;
888 : :
889 : 2128250 : case POST_DEC:
890 : 2128250 : case POST_INC:
891 : 2128250 : case POST_MODIFY:
892 : 2128250 : x = XEXP (x, 0);
893 : 2128250 : break;
894 : :
895 : : default:
896 : : break;
897 : : }
898 : :
899 : 1339536433 : if (GET_MODE (x) == Pmode
900 : 1292744547 : && (REG_P (x) || MEM_P (x) || GET_CODE (x) == VALUE)
901 : 2094187388 : && (*off == NULL_RTX || CONST_INT_P (*off)))
902 : : {
903 : 750431394 : cselib_val *e;
904 : 750431394 : if (GET_CODE (x) == VALUE)
905 : 474309700 : e = CSELIB_VAL_PTR (x);
906 : : else
907 : 276121694 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
908 : 750431394 : if (e)
909 : : {
910 : 741749822 : if (SP_DERIVED_VALUE_P (e->val_rtx)
911 : 741749822 : && (*off == NULL_RTX || *off == const0_rtx))
912 : : {
913 : 70417 : *off = NULL_RTX;
914 : 70417 : return e->val_rtx;
915 : : }
916 : 1624858307 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
917 : 1272642335 : if (GET_CODE (l->loc) == PLUS
918 : 544811434 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
919 : 544062736 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
920 : 1662107333 : && CONST_INT_P (XEXP (l->loc, 1)))
921 : : {
922 : 389463433 : if (*off == NULL_RTX)
923 : 1753477 : *off = XEXP (l->loc, 1);
924 : : else
925 : 387709956 : *off = plus_constant (Pmode, *off,
926 : 387709956 : INTVAL (XEXP (l->loc, 1)));
927 : 389463433 : if (*off == const0_rtx)
928 : 232835542 : *off = NULL_RTX;
929 : 389463433 : 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 : 1117458543 : rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth)
944 : : {
945 : 1463170286 : enum rtx_code code;
946 : 1463170286 : const char *fmt;
947 : 1463170286 : int i;
948 : :
949 : 1463170286 : if (REG_P (x) || MEM_P (x))
950 : : {
951 : 141342532 : cselib_val *e = cselib_lookup (x, GET_MODE (x), 0, memmode);
952 : :
953 : 141342532 : if (e)
954 : 119814089 : x = e->val_rtx;
955 : : }
956 : :
957 : 1463170286 : if (REG_P (y) || MEM_P (y))
958 : : {
959 : 130775930 : cselib_val *e = cselib_lookup (y, GET_MODE (y), 0, memmode);
960 : :
961 : 130775930 : if (e)
962 : 119283738 : y = e->val_rtx;
963 : : }
964 : :
965 : 1463170286 : if (x == y)
966 : : return true;
967 : :
968 : 1158582398 : if (GET_CODE (x) == VALUE)
969 : : {
970 : 393128933 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (x));
971 : 393128933 : struct elt_loc_list *l;
972 : :
973 : 393128933 : if (GET_CODE (y) == VALUE)
974 : 28958931 : return e == canonical_cselib_val (CSELIB_VAL_PTR (y));
975 : :
976 : 364170002 : if ((SP_DERIVED_VALUE_P (x)
977 : 141378369 : || SP_DERIVED_VALUE_P (e->val_rtx))
978 : 366983900 : && GET_MODE (y) == Pmode)
979 : : {
980 : 224923193 : rtx yoff = NULL;
981 : 224923193 : rtx yr = autoinc_split (y, &yoff, memmode);
982 : 224923193 : if ((yr == x || yr == e->val_rtx) && yoff == NULL_RTX)
983 : 56803 : return true;
984 : : }
985 : :
986 : 364113199 : if (depth == 128)
987 : : return false;
988 : :
989 : 1121425628 : for (l = e->locs; l; l = l->next)
990 : : {
991 : 779810382 : 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 : 779810382 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
997 : 466540846 : continue;
998 : 313269536 : else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1))
999 : : return true;
1000 : : }
1001 : :
1002 : : return false;
1003 : : }
1004 : 765453465 : else if (GET_CODE (y) == VALUE)
1005 : : {
1006 : 42927354 : cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y));
1007 : 42927354 : struct elt_loc_list *l;
1008 : :
1009 : 42927354 : if ((SP_DERIVED_VALUE_P (y)
1010 : 40844083 : || SP_DERIVED_VALUE_P (e->val_rtx))
1011 : 42927354 : && GET_MODE (x) == Pmode)
1012 : : {
1013 : 2014293 : rtx xoff = NULL;
1014 : 2014293 : rtx xr = autoinc_split (x, &xoff, memmode);
1015 : 2014293 : if ((xr == y || xr == e->val_rtx) && xoff == NULL_RTX)
1016 : 161 : return true;
1017 : : }
1018 : :
1019 : 42927193 : if (depth == 128)
1020 : : return false;
1021 : :
1022 : 103139640 : for (l = e->locs; l; l = l->next)
1023 : : {
1024 : 60286422 : rtx t = l->loc;
1025 : :
1026 : 60286422 : if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
1027 : 51657930 : continue;
1028 : 8628492 : else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1))
1029 : : return true;
1030 : : }
1031 : :
1032 : : return false;
1033 : : }
1034 : :
1035 : 722526111 : if (GET_MODE (x) != GET_MODE (y))
1036 : : return false;
1037 : :
1038 : 685713453 : if (GET_CODE (x) != GET_CODE (y)
1039 : 685713453 : || (GET_CODE (x) == PLUS
1040 : 231165472 : && GET_MODE (x) == Pmode
1041 : 229467455 : && CONST_INT_P (XEXP (x, 1))
1042 : 219830373 : && CONST_INT_P (XEXP (y, 1))))
1043 : : {
1044 : 547755466 : rtx xorig = x, yorig = y;
1045 : 547755466 : rtx xoff = NULL, yoff = NULL;
1046 : :
1047 : 547755466 : x = autoinc_split (x, &xoff, memmode);
1048 : 547755466 : y = autoinc_split (y, &yoff, memmode);
1049 : :
1050 : : /* Don't recurse if nothing changed. */
1051 : 547755466 : if (x != xorig || y != yorig)
1052 : : {
1053 : 511576849 : if (!xoff != !yoff)
1054 : 202702815 : return false;
1055 : :
1056 : 438128417 : if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth))
1057 : : return false;
1058 : :
1059 : 345052651 : return rtx_equal_for_cselib_1 (x, y, memmode, depth);
1060 : : }
1061 : :
1062 : 36178617 : if (GET_CODE (xorig) != GET_CODE (yorig))
1063 : : return false;
1064 : : }
1065 : :
1066 : : /* These won't be handled correctly by the code below. */
1067 : 137957987 : 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 : 1672054 : case DEBUG_IMPLICIT_PTR:
1079 : 1672054 : return DEBUG_IMPLICIT_PTR_DECL (x)
1080 : 1672054 : == DEBUG_IMPLICIT_PTR_DECL (y);
1081 : :
1082 : 5058 : case DEBUG_PARAMETER_REF:
1083 : 5058 : return DEBUG_PARAMETER_REF_DECL (x)
1084 : 5058 : == DEBUG_PARAMETER_REF_DECL (y);
1085 : :
1086 : 297704 : 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 : 297704 : return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
1090 : :
1091 : 313 : case LABEL_REF:
1092 : 313 : return label_ref_label (x) == label_ref_label (y);
1093 : :
1094 : 129 : case REG:
1095 : 129 : return REGNO (x) == REGNO (y);
1096 : :
1097 : 659092 : case MEM:
1098 : : /* We have to compare any autoinc operations in the addresses
1099 : : using this MEM's mode. */
1100 : 659092 : return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x),
1101 : 659092 : depth);
1102 : :
1103 : : default:
1104 : : break;
1105 : : }
1106 : :
1107 : 36389439 : code = GET_CODE (x);
1108 : 36389439 : fmt = GET_RTX_FORMAT (code);
1109 : :
1110 : 62585026 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1111 : : {
1112 : 52730759 : int j;
1113 : :
1114 : 52730759 : switch (fmt[i])
1115 : : {
1116 : 0 : case 'w':
1117 : 0 : if (XWINT (x, i) != XWINT (y, i))
1118 : : return false;
1119 : : break;
1120 : :
1121 : 565680 : case 'n':
1122 : 565680 : case 'i':
1123 : 565680 : if (XINT (x, i) != XINT (y, i))
1124 : : return false;
1125 : : break;
1126 : :
1127 : 5507 : case 'L':
1128 : 5507 : if (XLOC (x, i) != XLOC (y, i))
1129 : : return false;
1130 : : break;
1131 : :
1132 : 551278 : case 'p':
1133 : 551278 : if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1134 : : return false;
1135 : : break;
1136 : :
1137 : 1428098 : case 'V':
1138 : 1428098 : case 'E':
1139 : : /* Two vectors must have the same length. */
1140 : 1428098 : if (XVECLEN (x, i) != XVECLEN (y, i))
1141 : : return false;
1142 : :
1143 : : /* And the corresponding elements must match. */
1144 : 3617376 : for (j = 0; j < XVECLEN (x, i); j++)
1145 : 3029780 : if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j),
1146 : 3029780 : XVECEXP (y, i, j), memmode, depth))
1147 : : return false;
1148 : : break;
1149 : :
1150 : 40048930 : case 'e':
1151 : 40048930 : if (i == 1
1152 : 25916875 : && targetm.commutative_p (x, UNKNOWN)
1153 : 18745925 : && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode,
1154 : : depth)
1155 : 40353595 : && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode,
1156 : : depth))
1157 : : return true;
1158 : 39841757 : if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode,
1159 : : depth))
1160 : : return false;
1161 : : break;
1162 : :
1163 : 5133135 : case 'S':
1164 : 5133135 : case 's':
1165 : 5133135 : 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 : 105861320 : cselib_redundant_set_p (rtx set)
1191 : : {
1192 : 105861320 : gcc_assert (GET_CODE (set) == SET);
1193 : 105861320 : rtx dest = SET_DEST (set);
1194 : 105861320 : if (cselib_reg_set_mode (dest) != GET_MODE (dest))
1195 : : return false;
1196 : :
1197 : 50540717 : if (!rtx_equal_for_cselib_p (dest, SET_SRC (set)))
1198 : : return false;
1199 : :
1200 : 412344 : while (GET_CODE (dest) == SUBREG
1201 : 412344 : || GET_CODE (dest) == ZERO_EXTRACT
1202 : 824688 : || GET_CODE (dest) == STRICT_LOW_PART)
1203 : 0 : dest = XEXP (dest, 0);
1204 : :
1205 : 412344 : 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 : 32134 : rtx dest_addr = XEXP (dest, 0);
1211 : :
1212 : : /* Lookup the equivalents to the original dest (rather than just the
1213 : : MEM). */
1214 : 64268 : cselib_val *src_val = cselib_lookup (SET_DEST (set),
1215 : 32134 : GET_MODE (SET_DEST (set)),
1216 : : 0, VOIDmode);
1217 : :
1218 : 32134 : if (src_val)
1219 : : {
1220 : : /* Walk the list of source equivalents to find the MEM accessing
1221 : : the same location. */
1222 : 68246 : for (elt_loc_list *l = src_val->locs; l; l = l->next)
1223 : : {
1224 : 68246 : rtx src_equiv = l->loc;
1225 : 68246 : while (GET_CODE (src_equiv) == SUBREG
1226 : 68246 : || GET_CODE (src_equiv) == ZERO_EXTRACT
1227 : 136492 : || GET_CODE (src_equiv) == STRICT_LOW_PART)
1228 : 0 : src_equiv = XEXP (src_equiv, 0);
1229 : :
1230 : 68246 : 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 : 35780 : if (rtx_equal_for_cselib_1 (dest_addr, XEXP (src_equiv, 0),
1236 : 35780 : GET_MODE (dest), 0))
1237 : 32072 : 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 : 268146224 : cselib_hash_plus_const_int (rtx x, HOST_WIDE_INT c, int create,
1261 : : machine_mode memmode)
1262 : : {
1263 : 268146224 : cselib_val *e = cselib_lookup (x, GET_MODE (x), create, memmode);
1264 : 268146224 : if (! e)
1265 : : return 0;
1266 : :
1267 : 256009110 : if (! SP_DERIVED_VALUE_P (e->val_rtx))
1268 : 414442956 : for (struct elt_loc_list *l = e->locs; l; l = l->next)
1269 : 337794275 : if (GET_CODE (l->loc) == PLUS
1270 : 125371977 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
1271 : 124914931 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
1272 : 456999353 : && CONST_INT_P (XEXP (l->loc, 1)))
1273 : : {
1274 : 119203635 : e = CSELIB_VAL_PTR (XEXP (l->loc, 0));
1275 : 119203635 : c = trunc_int_for_mode (c + UINTVAL (XEXP (l->loc, 1)), Pmode);
1276 : 119203635 : break;
1277 : : }
1278 : 256009110 : if (c == 0)
1279 : 7962797 : return e->hash;
1280 : :
1281 : 248046313 : inchash::hash hash;
1282 : 248046313 : hash.add_int (PLUS);
1283 : 248046313 : hash.add_int (GET_MODE (x));
1284 : 248046313 : hash.merge_hash (e->hash);
1285 : 248046313 : hash.add_hwi (c);
1286 : :
1287 : 248046313 : 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 : 921563837 : cselib_hash_rtx (rtx x, int create, machine_mode memmode)
1314 : : {
1315 : 921563837 : cselib_val *e;
1316 : 921563837 : poly_int64 offset;
1317 : 921563837 : int i, j;
1318 : 921563837 : enum rtx_code code;
1319 : 921563837 : const char *fmt;
1320 : 921563837 : inchash::hash hash;
1321 : :
1322 : 921563837 : code = GET_CODE (x);
1323 : 921563837 : hash.add_int (code);
1324 : 921563837 : hash.add_int (GET_MODE (x));
1325 : :
1326 : 921563837 : switch (code)
1327 : : {
1328 : 399648 : case VALUE:
1329 : 399648 : e = CSELIB_VAL_PTR (x);
1330 : 399648 : return e->hash;
1331 : :
1332 : 199311619 : case MEM:
1333 : 199311619 : case REG:
1334 : 199311619 : e = cselib_lookup (x, GET_MODE (x), create, memmode);
1335 : 199311619 : if (! e)
1336 : : return 0;
1337 : :
1338 : 176753170 : return e->hash;
1339 : :
1340 : 10906333 : case DEBUG_EXPR:
1341 : 10906333 : hash.add_int (DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x)));
1342 : 10906333 : return hash.end () ? hash.end() : (unsigned int) DEBUG_EXPR;
1343 : :
1344 : 2180770 : case DEBUG_IMPLICIT_PTR:
1345 : 2180770 : hash.add_int (DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x)));
1346 : 2180770 : return hash.end () ? hash.end () : (unsigned int) DEBUG_IMPLICIT_PTR;
1347 : :
1348 : 28098 : case DEBUG_PARAMETER_REF:
1349 : 28098 : hash.add_int (DECL_UID (DEBUG_PARAMETER_REF_DECL (x)));
1350 : 28098 : return hash.end () ? hash.end () : (unsigned int) DEBUG_PARAMETER_REF;
1351 : :
1352 : 1337746 : 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 : 1337746 : if (REG_P (ENTRY_VALUE_EXP (x)))
1359 : 1320503 : hash.add_int ((unsigned int) REG
1360 : 1320503 : + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
1361 : 1320503 : + (unsigned int) REGNO (ENTRY_VALUE_EXP (x)));
1362 : 17243 : else if (MEM_P (ENTRY_VALUE_EXP (x))
1363 : 17243 : && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0)))
1364 : 17243 : hash.add_int ((unsigned int) MEM
1365 : 17243 : + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
1366 : 17243 : + (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 : 1337746 : return hash.end () ? hash.end () : (unsigned int) ENTRY_VALUE;
1370 : :
1371 : 161976797 : case CONST_INT:
1372 : 161976797 : hash.add_hwi (UINTVAL (x));
1373 : 161976797 : return hash.end () ? hash.end () : (unsigned int) CONST_INT;
1374 : :
1375 : : case CONST_WIDE_INT:
1376 : 3138399 : for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
1377 : 2094143 : hash.add_hwi (CONST_WIDE_INT_ELT (x, i));
1378 : 1044256 : 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 : 3573308 : case CONST_DOUBLE:
1388 : : /* This is like the general case, except that it only counts
1389 : : the integers representing the constant. */
1390 : 3573308 : 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 : 3573308 : hash.merge_hash (real_hash (CONST_DOUBLE_REAL_VALUE (x)));
1397 : 3573308 : 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 : 2935897 : case CONST_VECTOR:
1404 : 2935897 : {
1405 : 2935897 : int units;
1406 : 2935897 : rtx elt;
1407 : :
1408 : 2935897 : units = const_vector_encoded_nelts (x);
1409 : :
1410 : 7732674 : for (i = 0; i < units; ++i)
1411 : : {
1412 : 4796777 : elt = CONST_VECTOR_ENCODED_ELT (x, i);
1413 : 4796777 : hash.merge_hash (cselib_hash_rtx (elt, 0, memmode));
1414 : : }
1415 : :
1416 : 2935897 : return hash.end () ? hash.end () : (unsigned int) CONST_VECTOR;
1417 : : }
1418 : :
1419 : : /* Assume there is only one rtx object for any given label. */
1420 : 136343 : 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 : 136343 : hash.add_int (CODE_LABEL_NUMBER (label_ref_label (x)));
1424 : 136343 : return hash.end () ? hash.end () : (unsigned int) LABEL_REF;
1425 : :
1426 : 60773652 : case SYMBOL_REF:
1427 : 60773652 : {
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 : 60773652 : const char *p = (const char *) XSTR (x, 0);
1434 : :
1435 : 60773652 : if (*p)
1436 : 60773652 : hash.add (p, strlen (p));
1437 : :
1438 : 60773652 : return hash.end () ? hash.end () : (unsigned int) SYMBOL_REF;
1439 : : }
1440 : :
1441 : 17472406 : case PRE_DEC:
1442 : 17472406 : case PRE_INC:
1443 : 17472406 : {
1444 : : /* We can't compute these without knowing the MEM mode. */
1445 : 17472406 : gcc_assert (memmode != VOIDmode);
1446 : 34944812 : offset = GET_MODE_SIZE (memmode);
1447 : 17472406 : if (code == PRE_DEC)
1448 : 17472406 : offset = -offset;
1449 : : /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1450 : : like (mem:MEMMODE (plus (reg) (const_int I))). */
1451 : 17472406 : if (GET_MODE (x) == Pmode
1452 : 17472406 : && (REG_P (XEXP (x, 0))
1453 : : || MEM_P (XEXP (x, 0))
1454 : : || GET_CODE (XEXP (x, 0)) == VALUE))
1455 : : {
1456 : 17472406 : HOST_WIDE_INT c;
1457 : 17472406 : if (offset.is_constant (&c))
1458 : 17472406 : return cselib_hash_plus_const_int (XEXP (x, 0),
1459 : 17472406 : 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 : 610472 : case PRE_MODIFY:
1476 : 610472 : {
1477 : 610472 : gcc_assert (memmode != VOIDmode);
1478 : 610472 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1479 : 610472 : if (tem_hash == 0)
1480 : : return 0;
1481 : 603418 : hash.merge_hash (tem_hash);
1482 : 603418 : return hash.end () ? hash.end () : 1 + (unsigned) PRE_MODIFY;
1483 : : }
1484 : :
1485 : 2122807 : case POST_DEC:
1486 : 2122807 : case POST_INC:
1487 : 2122807 : case POST_MODIFY:
1488 : 2122807 : {
1489 : 2122807 : gcc_assert (memmode != VOIDmode);
1490 : 2122807 : hashval_t tem_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1491 : 2122807 : if (tem_hash == 0)
1492 : : return 0;
1493 : 2122807 : hash.merge_hash (tem_hash);
1494 : 2122807 : 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 : 433798 : case ASM_OPERANDS:
1503 : 433798 : if (MEM_VOLATILE_P (x))
1504 : : return 0;
1505 : :
1506 : : break;
1507 : :
1508 : 297774928 : case PLUS:
1509 : 297774928 : if (GET_MODE (x) == Pmode
1510 : 287157442 : && (REG_P (XEXP (x, 0))
1511 : : || MEM_P (XEXP (x, 0))
1512 : : || GET_CODE (XEXP (x, 0)) == VALUE)
1513 : 563689940 : && CONST_INT_P (XEXP (x, 1)))
1514 : 250673818 : return cselib_hash_plus_const_int (XEXP (x, 0), INTVAL (XEXP (x, 1)),
1515 : 250673818 : create, memmode);
1516 : : break;
1517 : :
1518 : : default:
1519 : : break;
1520 : : }
1521 : :
1522 : 191786451 : i = GET_RTX_LENGTH (code) - 1;
1523 : 191786451 : fmt = GET_RTX_FORMAT (code);
1524 : :
1525 : 191786451 : if (COMMUTATIVE_P (x))
1526 : : {
1527 : 71349710 : gcc_assert (i == 1 && fmt[0] == 'e' && fmt[1] == 'e');
1528 : 71349710 : hashval_t tem1_hash = cselib_hash_rtx (XEXP (x, 1), create, memmode);
1529 : 71349710 : if (tem1_hash == 0)
1530 : : return 0;
1531 : 66285316 : hashval_t tem0_hash = cselib_hash_rtx (XEXP (x, 0), create, memmode);
1532 : 66285316 : if (tem0_hash == 0)
1533 : : return 0;
1534 : 62890833 : hash.add_commutative (tem0_hash, tem1_hash);
1535 : 62890833 : return hash.end () ? hash.end () : 1 + (unsigned int) GET_CODE (x);
1536 : : }
1537 : :
1538 : 317130875 : for (; i >= 0; i--)
1539 : : {
1540 : 213472367 : switch (fmt[i])
1541 : : {
1542 : 193341893 : case 'e':
1543 : 193341893 : {
1544 : 193341893 : rtx tem = XEXP (x, i);
1545 : 193341893 : hashval_t tem_hash = cselib_hash_rtx (tem, create, memmode);
1546 : 193341893 : if (tem_hash == 0)
1547 : : return 0;
1548 : 177468889 : hash.merge_hash (tem_hash);
1549 : : }
1550 : 177468889 : break;
1551 : : case 'E':
1552 : 25461775 : for (j = 0; j < XVECLEN (x, i); j++)
1553 : : {
1554 : 17899964 : hashval_t tem_hash
1555 : 17899964 : = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode);
1556 : 17899964 : if (tem_hash == 0)
1557 : : return 0;
1558 : 16994735 : hash.merge_hash (tem_hash);
1559 : : }
1560 : : break;
1561 : :
1562 : 488988 : case 's':
1563 : 488988 : {
1564 : 488988 : const char *p = (const char *) XSTR (x, i);
1565 : :
1566 : 488988 : if (p && *p)
1567 : 456457 : hash.add (p, strlen (p));
1568 : : break;
1569 : : }
1570 : :
1571 : 5179791 : case 'i':
1572 : 5179791 : hash.add_hwi (XINT (x, i));
1573 : 5179791 : break;
1574 : :
1575 : 241689 : case 'L':
1576 : 241689 : hash.add_hwi (XLOC (x, i));
1577 : 241689 : break;
1578 : :
1579 : 5752966 : case 'p':
1580 : 5752966 : hash.add_int (constant_lower_bound (SUBREG_BYTE (x)));
1581 : 5752966 : break;
1582 : :
1583 : : case '0':
1584 : : case 't':
1585 : : /* unused */
1586 : : break;
1587 : :
1588 : 0 : default:
1589 : 0 : gcc_unreachable ();
1590 : : }
1591 : : }
1592 : :
1593 : 103658508 : 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 : 391239851 : new_cselib_val (hashval_t hash, machine_mode mode, rtx x)
1601 : : {
1602 : 391239851 : cselib_val *e = cselib_val_pool.allocate ();
1603 : :
1604 : 391239851 : gcc_assert (hash);
1605 : 391239851 : gcc_assert (next_uid);
1606 : :
1607 : 391239851 : e->hash = hash;
1608 : 391239851 : 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 : 391239851 : e->val_rtx = (rtx_def*) value_pool.allocate ();
1615 : 391239851 : memset (e->val_rtx, 0, RTX_HDR_SIZE);
1616 : 391239851 : PUT_CODE (e->val_rtx, VALUE);
1617 : 391239851 : PUT_MODE (e->val_rtx, mode);
1618 : 391239851 : CSELIB_VAL_PTR (e->val_rtx) = e;
1619 : 391239851 : e->addr_list = 0;
1620 : 391239851 : e->locs = 0;
1621 : 391239851 : e->next_containing_mem = 0;
1622 : :
1623 : 391239851 : scalar_int_mode int_mode;
1624 : 508669193 : if (REG_P (x) && is_int_mode (mode, &int_mode)
1625 : 117429342 : && GET_MODE_SIZE (int_mode) > 1
1626 : 111742628 : && REG_VALUES (REGNO (x)) != NULL
1627 : 397989785 : && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
1628 : : {
1629 : 6603736 : rtx copy = shallow_copy_rtx (x);
1630 : 6603736 : scalar_int_mode narrow_mode_iter;
1631 : 23595721 : FOR_EACH_MODE_UNTIL (narrow_mode_iter, int_mode)
1632 : : {
1633 : 16991985 : PUT_MODE_RAW (copy, narrow_mode_iter);
1634 : 16991985 : cselib_val *v = cselib_lookup (copy, narrow_mode_iter, 0, VOIDmode);
1635 : 16991985 : if (v)
1636 : : {
1637 : 754217 : rtx sub = lowpart_subreg (narrow_mode_iter, e->val_rtx, int_mode);
1638 : 754217 : if (sub)
1639 : 754217 : new_elt_loc_list (v, sub);
1640 : : }
1641 : : }
1642 : : }
1643 : :
1644 : 391239851 : 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 : 391239851 : 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 : 49005007 : add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
1664 : : {
1665 : 49005007 : addr_elt = canonical_cselib_val (addr_elt);
1666 : 49005007 : mem_elt = canonical_cselib_val (mem_elt);
1667 : :
1668 : : /* Avoid duplicates. */
1669 : 49005007 : addr_space_t as = MEM_ADDR_SPACE (x);
1670 : 86290437 : for (elt_loc_list *l = mem_elt->locs; l; l = l->next)
1671 : 37285433 : if (MEM_P (l->loc)
1672 : 10274249 : && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt
1673 : 37285436 : && MEM_ADDR_SPACE (l->loc) == as)
1674 : : {
1675 : 3 : promote_debug_loc (l);
1676 : 3 : return;
1677 : : }
1678 : :
1679 : 49005004 : addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
1680 : 49005004 : new_elt_loc_list (mem_elt,
1681 : : replace_equiv_address_nv (x, addr_elt->val_rtx));
1682 : 49005004 : if (mem_elt->next_containing_mem == NULL)
1683 : : {
1684 : 42977477 : mem_elt->next_containing_mem = first_containing_mem;
1685 : 42977477 : 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 : 224054819 : cselib_lookup_mem (rtx x, int create)
1694 : : {
1695 : 224054819 : machine_mode mode = GET_MODE (x);
1696 : 224054819 : machine_mode addr_mode;
1697 : 224054819 : cselib_val **slot;
1698 : 224054819 : cselib_val *addr;
1699 : 224054819 : cselib_val *mem_elt;
1700 : :
1701 : 444177028 : if (MEM_VOLATILE_P (x) || mode == BLKmode
1702 : 219852893 : || !cselib_record_memory
1703 : 401366688 : || (FLOAT_MODE_P (mode) && flag_float_store))
1704 : : return 0;
1705 : :
1706 : 177299195 : addr_mode = GET_MODE (XEXP (x, 0));
1707 : 177299195 : if (addr_mode == VOIDmode)
1708 : 998957 : addr_mode = Pmode;
1709 : :
1710 : : /* Look up the value for the address. */
1711 : 177299195 : addr = cselib_lookup (XEXP (x, 0), addr_mode, create, mode);
1712 : 177299195 : if (! addr)
1713 : : return 0;
1714 : 109679644 : addr = canonical_cselib_val (addr);
1715 : :
1716 : : /* Find a value that describes a value of our mode at that address. */
1717 : 109679644 : addr_space_t as = MEM_ADDR_SPACE (x);
1718 : 112154262 : for (elt_list *l = addr->addr_list; l; l = l->next)
1719 : 69565921 : if (GET_MODE (l->elt->val_rtx) == mode)
1720 : : {
1721 : 73049688 : for (elt_loc_list *l2 = l->elt->locs; l2; l2 = l2->next)
1722 : 77400385 : if (MEM_P (l2->loc) && MEM_ADDR_SPACE (l2->loc) == as)
1723 : : {
1724 : 67091303 : promote_debug_loc (l->elt->locs);
1725 : 67091303 : return l->elt;
1726 : : }
1727 : : }
1728 : :
1729 : 42588341 : if (! create)
1730 : : return 0;
1731 : :
1732 : 26761598 : mem_elt = new_cselib_val (next_uid, mode, x);
1733 : 26761598 : add_mem_for_addr (addr, mem_elt, x);
1734 : 26761598 : slot = cselib_find_slot (mode, x, mem_elt->hash, INSERT, VOIDmode);
1735 : 26761598 : *slot = mem_elt;
1736 : 26761598 : 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 : 21532171 : expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
1747 : : int max_depth)
1748 : : {
1749 : 21532171 : rtx reg_result = NULL;
1750 : 21532171 : unsigned int regno = UINT_MAX;
1751 : 21532171 : struct elt_loc_list *p_in = p;
1752 : :
1753 : 46846865 : 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 : 28812536 : if (REG_P (p->loc)
1760 : 28812536 : && (REGNO (p->loc) == STACK_POINTER_REGNUM
1761 : : || REGNO (p->loc) == FRAME_POINTER_REGNUM
1762 : : || REGNO (p->loc) == HARD_FRAME_POINTER_REGNUM
1763 : 22863824 : || 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 : 28321840 : if ((REG_P (p->loc))
1768 : 22857499 : && (REGNO (p->loc) < regno)
1769 : 50883888 : && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
1770 : : {
1771 : 3989850 : reg_result = p->loc;
1772 : 3989850 : regno = REGNO (p->loc);
1773 : : }
1774 : : /* Avoid infinite recursion and do not try to expand the
1775 : : value. */
1776 : 24331990 : else if (GET_CODE (p->loc) == VALUE
1777 : 357104 : && CSELIB_VAL_PTR (p->loc)->locs == p_in)
1778 : 0 : continue;
1779 : 24331990 : else if (!REG_P (p->loc))
1780 : : {
1781 : 5464341 : rtx result, note;
1782 : 5464341 : 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 : 5464341 : 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 : 5464341 : && XEXP (note, 0) == XEXP (p->loc, 1))
1792 : : return XEXP (p->loc, 1);
1793 : 5464341 : result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1794 : 5464341 : if (result)
1795 : : return result;
1796 : : }
1797 : :
1798 : : }
1799 : :
1800 : 18034329 : if (regno != UINT_MAX)
1801 : : {
1802 : 3191610 : rtx result;
1803 : 3191610 : if (dump_file && (dump_flags & TDF_CSELIB))
1804 : 0 : fprintf (dump_file, "r%d\n", regno);
1805 : :
1806 : 3191610 : result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1807 : 3191610 : if (result)
1808 : : return result;
1809 : : }
1810 : :
1811 : 15619310 : 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 : 32841938 : cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1845 : : {
1846 : 32841938 : struct expand_value_data evd;
1847 : :
1848 : 32841938 : evd.regs_active = regs_active;
1849 : 32841938 : evd.callback = NULL;
1850 : 32841938 : evd.callback_arg = NULL;
1851 : 32841938 : evd.dummy = false;
1852 : :
1853 : 32841938 : 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 : 77949348 : cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1864 : : cselib_expand_callback cb, void *data)
1865 : : {
1866 : 77949348 : struct expand_value_data evd;
1867 : :
1868 : 77949348 : evd.regs_active = regs_active;
1869 : 77949348 : evd.callback = cb;
1870 : 77949348 : evd.callback_arg = data;
1871 : 77949348 : evd.dummy = false;
1872 : :
1873 : 77949348 : 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 : 184174703 : cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1899 : : int max_depth)
1900 : : {
1901 : 184174703 : rtx copy, scopy;
1902 : 184174703 : int i, j;
1903 : 184174703 : RTX_CODE code;
1904 : 184174703 : const char *format_ptr;
1905 : 184174703 : machine_mode mode;
1906 : :
1907 : 184174703 : 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 : 184174703 : if (max_depth <= 0)
1913 : : return NULL;
1914 : :
1915 : 181775141 : switch (code)
1916 : : {
1917 : 45137007 : case REG:
1918 : 45137007 : {
1919 : 45137007 : struct elt_list *l = REG_VALUES (REGNO (orig));
1920 : :
1921 : 45137007 : if (l && l->elt == NULL)
1922 : 22364071 : l = l->next;
1923 : 45153975 : for (; l; l = l->next)
1924 : 33521649 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1925 : : {
1926 : 33504681 : rtx result;
1927 : 33504681 : 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 : 33504681 : if (regno == STACK_POINTER_REGNUM
1946 : 33504681 : || regno == FRAME_POINTER_REGNUM
1947 : 18281399 : || regno == HARD_FRAME_POINTER_REGNUM
1948 : 17827043 : || regno == cfa_base_preserved_regno)
1949 : : return orig;
1950 : :
1951 : 17530925 : bitmap_set_bit (evd->regs_active, regno);
1952 : :
1953 : 17530925 : if (dump_file && (dump_flags & TDF_CSELIB))
1954 : 0 : fprintf (dump_file, "expanding: r%d into: ", regno);
1955 : :
1956 : 17530925 : result = expand_loc (l->elt->locs, evd, max_depth);
1957 : 17530925 : bitmap_clear_bit (evd->regs_active, regno);
1958 : :
1959 : 17530925 : 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 : 5 : case CLOBBER:
1975 : 5 : if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1976 : : return orig;
1977 : : break;
1978 : :
1979 : 250259 : case CONST:
1980 : 250259 : if (shared_const_p (orig))
1981 : : return orig;
1982 : : break;
1983 : :
1984 : 876709 : case SUBREG:
1985 : 876709 : {
1986 : 876709 : rtx subreg;
1987 : :
1988 : 876709 : if (evd->callback)
1989 : : {
1990 : 774972 : subreg = evd->callback (orig, evd->regs_active, max_depth,
1991 : : evd->callback_arg);
1992 : 774972 : if (subreg != orig)
1993 : : return subreg;
1994 : : }
1995 : :
1996 : 101737 : subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1997 : : max_depth - 1);
1998 : 101737 : if (!subreg)
1999 : : return NULL;
2000 : 103548 : scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
2001 : 51774 : GET_MODE (SUBREG_REG (orig)),
2002 : 51774 : SUBREG_BYTE (orig));
2003 : 51774 : if (scopy == NULL
2004 : 51072 : || (GET_CODE (scopy) == SUBREG
2005 : 47340 : && !REG_P (SUBREG_REG (scopy))
2006 : 7454 : && !MEM_P (SUBREG_REG (scopy))))
2007 : : return NULL;
2008 : :
2009 : : return scopy;
2010 : : }
2011 : :
2012 : 61894648 : case VALUE:
2013 : 61894648 : {
2014 : 61894648 : rtx result;
2015 : :
2016 : 61894648 : 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 : 61894648 : if (evd->callback)
2024 : : {
2025 : 57893402 : result = evd->callback (orig, evd->regs_active, max_depth,
2026 : : evd->callback_arg);
2027 : :
2028 : 57893402 : if (result != orig)
2029 : : return result;
2030 : : }
2031 : :
2032 : 4001246 : result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
2033 : 4001246 : return result;
2034 : : }
2035 : :
2036 : 5270592 : case DEBUG_EXPR:
2037 : 5270592 : if (evd->callback)
2038 : 5270592 : return evd->callback (orig, evd->regs_active, max_depth,
2039 : 5270592 : 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 : 41298018 : if (evd->dummy)
2051 : : copy = NULL;
2052 : : else
2053 : 41298018 : copy = shallow_copy_rtx (orig);
2054 : :
2055 : 41298018 : format_ptr = GET_RTX_FORMAT (code);
2056 : :
2057 : 108053160 : for (i = 0; i < GET_RTX_LENGTH (code); i++)
2058 : 70487574 : switch (*format_ptr++)
2059 : : {
2060 : 64154937 : case 'e':
2061 : 64154937 : if (XEXP (orig, i) != NULL)
2062 : : {
2063 : 64154937 : rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
2064 : : max_depth - 1);
2065 : 64154937 : if (!result)
2066 : : return NULL;
2067 : 60457902 : if (copy)
2068 : 60457902 : XEXP (copy, i) = result;
2069 : : }
2070 : : break;
2071 : :
2072 : 295614 : case 'E':
2073 : 295614 : case 'V':
2074 : 295614 : if (XVEC (orig, i) != NULL)
2075 : : {
2076 : 295614 : if (copy)
2077 : 295614 : XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
2078 : 731009 : for (j = 0; j < XVECLEN (orig, i); j++)
2079 : : {
2080 : 470792 : rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
2081 : : evd, max_depth - 1);
2082 : 470792 : if (!result)
2083 : : return NULL;
2084 : 435395 : if (copy)
2085 : 435395 : 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 : 37565586 : if (evd->dummy)
2108 : : return orig;
2109 : :
2110 : 37565586 : 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 : 37565586 : scopy = copy;
2116 : 37565586 : switch (GET_RTX_CLASS (code))
2117 : : {
2118 : 608533 : case RTX_UNARY:
2119 : 608533 : if (CONST_INT_P (XEXP (copy, 0))
2120 : 50242 : && GET_MODE (XEXP (orig, 0)) != VOIDmode)
2121 : : {
2122 : 50234 : scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
2123 : : GET_MODE (XEXP (orig, 0)));
2124 : 50234 : 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 : 48393 : case RTX_TERNARY:
2133 : 48393 : case RTX_BITFIELD_OPS:
2134 : 48393 : if (CONST_INT_P (XEXP (copy, 0))
2135 : 112 : && 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 : 166800 : case RTX_COMPARE:
2146 : 166800 : case RTX_COMM_COMPARE:
2147 : 166800 : if (CONST_INT_P (XEXP (copy, 0))
2148 : 516 : && GET_MODE (XEXP (copy, 1)) == VOIDmode
2149 : 165 : && (GET_MODE (XEXP (orig, 0)) != VOIDmode
2150 : 2 : || GET_MODE (XEXP (orig, 1)) != VOIDmode))
2151 : : {
2152 : 165 : 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 : 165 : if (scopy)
2160 : : return scopy;
2161 : : }
2162 : : break;
2163 : : default:
2164 : : break;
2165 : : }
2166 : 37515187 : scopy = simplify_rtx (copy);
2167 : 37515187 : if (scopy)
2168 : 4141936 : 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 : 551643260 : cselib_subst_to_values (rtx x, machine_mode memmode)
2181 : : {
2182 : 559607639 : enum rtx_code code = GET_CODE (x);
2183 : 559607639 : const char *fmt = GET_RTX_FORMAT (code);
2184 : 559607639 : cselib_val *e;
2185 : 559607639 : struct elt_list *l;
2186 : 559607639 : rtx copy = x;
2187 : 559607639 : int i;
2188 : 559607639 : poly_int64 offset;
2189 : :
2190 : 559607639 : switch (code)
2191 : : {
2192 : 217349433 : case REG:
2193 : 217349433 : l = REG_VALUES (REGNO (x));
2194 : 217349433 : if (l && l->elt == NULL)
2195 : 122360116 : l = l->next;
2196 : 219528792 : for (; l; l = l->next)
2197 : 219528792 : if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
2198 : : return l->elt->val_rtx;
2199 : :
2200 : 0 : gcc_unreachable ();
2201 : :
2202 : 5850429 : case MEM:
2203 : 5850429 : 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 : 5850429 : 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 : 5850429 : return e->val_rtx;
2212 : :
2213 : 653537 : case ENTRY_VALUE:
2214 : 653537 : e = cselib_lookup (x, GET_MODE (x), 0, memmode);
2215 : 653537 : if (! e)
2216 : : break;
2217 : 973 : return e->val_rtx;
2218 : :
2219 : : CASE_CONST_ANY:
2220 : : return x;
2221 : :
2222 : 6404434 : case PRE_DEC:
2223 : 6404434 : case PRE_INC:
2224 : 6404434 : gcc_assert (memmode != VOIDmode);
2225 : 12808868 : offset = GET_MODE_SIZE (memmode);
2226 : 6404434 : if (code == PRE_DEC)
2227 : 6404434 : offset = -offset;
2228 : 6404434 : return cselib_subst_to_values (plus_constant (GET_MODE (x),
2229 : : XEXP (x, 0), offset),
2230 : 6404434 : memmode);
2231 : :
2232 : 457705 : case PRE_MODIFY:
2233 : 457705 : gcc_assert (memmode != VOIDmode);
2234 : 457705 : return cselib_subst_to_values (XEXP (x, 1), memmode);
2235 : :
2236 : 1102240 : case POST_DEC:
2237 : 1102240 : case POST_INC:
2238 : 1102240 : case POST_MODIFY:
2239 : 1102240 : gcc_assert (memmode != VOIDmode);
2240 : 1102240 : return cselib_subst_to_values (XEXP (x, 0), memmode);
2241 : :
2242 : 107600464 : case PLUS:
2243 : 107600464 : if (GET_MODE (x) == Pmode && CONST_INT_P (XEXP (x, 1)))
2244 : : {
2245 : 87873386 : rtx t = cselib_subst_to_values (XEXP (x, 0), memmode);
2246 : 87873386 : if (GET_CODE (t) == VALUE)
2247 : : {
2248 : 83200855 : if (SP_DERIVED_VALUE_P (t) && XEXP (x, 1) == const0_rtx)
2249 : : return t;
2250 : 83200855 : for (struct elt_loc_list *l = CSELIB_VAL_PTR (t)->locs;
2251 : 175496602 : l; l = l->next)
2252 : 113700711 : if (GET_CODE (l->loc) == PLUS
2253 : 24573467 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2254 : 24451076 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2255 : 135106197 : && CONST_INT_P (XEXP (l->loc, 1)))
2256 : 21404964 : return plus_constant (Pmode, l->loc, INTVAL (XEXP (x, 1)));
2257 : : }
2258 : 66468422 : if (t != XEXP (x, 0))
2259 : : {
2260 : 62642797 : copy = shallow_copy_rtx (x);
2261 : 62642797 : XEXP (copy, 0) = t;
2262 : : }
2263 : 66468422 : return copy;
2264 : : }
2265 : :
2266 : : default:
2267 : : break;
2268 : : }
2269 : :
2270 : 445529658 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2271 : : {
2272 : 290883042 : if (fmt[i] == 'e')
2273 : : {
2274 : 213562209 : rtx t = cselib_subst_to_values (XEXP (x, i), memmode);
2275 : :
2276 : 213562209 : if (t != XEXP (x, i))
2277 : : {
2278 : 155796436 : if (x == copy)
2279 : 111319853 : copy = shallow_copy_rtx (x);
2280 : 155796436 : XEXP (copy, i) = t;
2281 : : }
2282 : : }
2283 : 77320833 : else if (fmt[i] == 'E')
2284 : : {
2285 : : int j;
2286 : :
2287 : 18223401 : for (j = 0; j < XVECLEN (x, i); j++)
2288 : : {
2289 : 12887120 : rtx t = cselib_subst_to_values (XVECEXP (x, i, j), memmode);
2290 : :
2291 : 12887120 : if (t != XVECEXP (x, i, j))
2292 : : {
2293 : 2427138 : if (XVEC (x, i) == XVEC (copy, i))
2294 : : {
2295 : 1852300 : if (x == copy)
2296 : 1852300 : copy = shallow_copy_rtx (x);
2297 : 1852300 : XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
2298 : : }
2299 : 2427138 : 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 : 1463 : cselib_subst_to_values_from_insn (rtx x, machine_mode memmode, rtx_insn *insn)
2312 : : {
2313 : 1463 : rtx ret;
2314 : 1463 : gcc_assert (!cselib_current_insn);
2315 : 1463 : cselib_current_insn = insn;
2316 : 1463 : ret = cselib_subst_to_values (x, memmode);
2317 : 1463 : cselib_current_insn = NULL;
2318 : 1463 : 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 : 2256170355 : cselib_lookup_1 (rtx x, machine_mode mode,
2330 : : int create, machine_mode memmode)
2331 : : {
2332 : 2256170355 : cselib_val **slot;
2333 : 2256170355 : cselib_val *e;
2334 : :
2335 : 2256170355 : if (GET_MODE (x) != VOIDmode)
2336 : 2176106259 : mode = GET_MODE (x);
2337 : :
2338 : 2256170355 : if (GET_CODE (x) == VALUE)
2339 : 60796440 : return CSELIB_VAL_PTR (x);
2340 : :
2341 : 2195373915 : if (REG_P (x))
2342 : : {
2343 : 1412012627 : struct elt_list *l;
2344 : 1412012627 : unsigned int i = REGNO (x);
2345 : :
2346 : 1412012627 : l = REG_VALUES (i);
2347 : 1412012627 : if (l && l->elt == NULL)
2348 : 583363131 : l = l->next;
2349 : 1431794335 : for (; l; l = l->next)
2350 : 1095545476 : if (mode == GET_MODE (l->elt->val_rtx))
2351 : : {
2352 : 1075763768 : promote_debug_loc (l->elt->locs);
2353 : 1075763768 : return l->elt;
2354 : : }
2355 : :
2356 : 336248859 : if (! create)
2357 : : return 0;
2358 : :
2359 : 127159171 : if (i < FIRST_PSEUDO_REGISTER)
2360 : : {
2361 : 73058288 : unsigned int n = hard_regno_nregs (i, mode);
2362 : :
2363 : 73058288 : if (n > max_value_regs)
2364 : 25383631 : max_value_regs = n;
2365 : : }
2366 : :
2367 : 127159171 : e = new_cselib_val (next_uid, GET_MODE (x), x);
2368 : 127159171 : if (GET_MODE (x) == Pmode && x == stack_pointer_rtx)
2369 : 11406553 : SP_DERIVED_VALUE_P (e->val_rtx) = 1;
2370 : 127159171 : new_elt_loc_list (e, x);
2371 : :
2372 : 127159171 : scalar_int_mode int_mode;
2373 : 127159171 : 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 : 117477721 : used_regs[n_used_regs++] = i;
2379 : 117477721 : REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
2380 : : }
2381 : 9681450 : else if (cselib_preserve_constants
2382 : 9681450 : && 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 : 1524966 : struct elt_list *lwider = NULL;
2389 : 1524966 : scalar_int_mode lmode;
2390 : 1524966 : l = REG_VALUES (i);
2391 : 1524966 : if (l && l->elt == NULL)
2392 : 959496 : l = l->next;
2393 : 2325564 : for (; l; l = l->next)
2394 : 800598 : if (is_int_mode (GET_MODE (l->elt->val_rtx), &lmode)
2395 : 1130094 : && GET_MODE_SIZE (lmode) > GET_MODE_SIZE (int_mode)
2396 : 280190 : && (lwider == NULL
2397 : 5569 : || partial_subreg_p (lmode,
2398 : 5569 : GET_MODE (lwider->elt->val_rtx))))
2399 : : {
2400 : 279126 : struct elt_loc_list *el;
2401 : 295518 : if (i < FIRST_PSEUDO_REGISTER
2402 : 279126 : && hard_regno_nregs (i, lmode) != 1)
2403 : 16392 : continue;
2404 : 514851 : for (el = l->elt->locs; el; el = el->next)
2405 : 485372 : if (!REG_P (el->loc))
2406 : : break;
2407 : 262734 : if (el)
2408 : 800598 : lwider = l;
2409 : : }
2410 : 1524966 : if (lwider)
2411 : : {
2412 : 457500 : rtx sub = lowpart_subreg (int_mode, lwider->elt->val_rtx,
2413 : 228750 : GET_MODE (lwider->elt->val_rtx));
2414 : 228750 : if (sub)
2415 : 228750 : new_elt_loc_list (e, sub);
2416 : : }
2417 : : }
2418 : 127159171 : REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
2419 : 127159171 : slot = cselib_find_slot (mode, x, e->hash, INSERT, memmode);
2420 : 127159171 : *slot = e;
2421 : 127159171 : return e;
2422 : : }
2423 : :
2424 : 783361288 : if (MEM_P (x))
2425 : 218204390 : return cselib_lookup_mem (x, create);
2426 : :
2427 : 565156898 : hashval_t hashval = cselib_hash_rtx (x, create, memmode);
2428 : : /* Can't even create if hashing is not possible. */
2429 : 565156898 : if (! hashval)
2430 : : return 0;
2431 : :
2432 : 724406304 : slot = cselib_find_slot (mode, x, hashval,
2433 : : create ? INSERT : NO_INSERT, memmode);
2434 : 516167919 : if (slot == 0)
2435 : : return 0;
2436 : :
2437 : 411035439 : e = (cselib_val *) *slot;
2438 : 411035439 : if (e)
2439 : : return e;
2440 : :
2441 : 237319082 : 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 : 237319082 : *slot = e;
2447 : 237319082 : 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 : 237319082 : 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 : 237319082 : new_elt_loc_list (e, v);
2455 : 237319082 : return e;
2456 : : }
2457 : :
2458 : : /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2459 : :
2460 : : cselib_val *
2461 : 5876281 : cselib_lookup_from_insn (rtx x, machine_mode mode,
2462 : : int create, machine_mode memmode, rtx_insn *insn)
2463 : : {
2464 : 5876281 : cselib_val *ret;
2465 : :
2466 : 5876281 : gcc_assert (!cselib_current_insn);
2467 : 5876281 : cselib_current_insn = insn;
2468 : :
2469 : 5876281 : ret = cselib_lookup (x, mode, create, memmode);
2470 : :
2471 : 5876281 : cselib_current_insn = NULL;
2472 : :
2473 : 5876281 : 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 : 2255087915 : cselib_lookup (rtx x, machine_mode mode,
2481 : : int create, machine_mode memmode)
2482 : : {
2483 : 2255087915 : 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 : 2255087915 : 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 : 2255087915 : return ret;
2501 : : }
2502 : :
2503 : : /* Invalidate the value at *L, which is part of REG_VALUES (REGNO). */
2504 : :
2505 : : static void
2506 : 176581496 : cselib_invalidate_regno_val (unsigned int regno, struct elt_list **l)
2507 : : {
2508 : 176581496 : cselib_val *v = (*l)->elt;
2509 : 176581496 : 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 : 136291553 : (*l)->elt = NULL;
2517 : 136291553 : l = &(*l)->next;
2518 : : }
2519 : : else
2520 : 40289943 : unchain_one_elt_list (l);
2521 : :
2522 : 176581496 : v = canonical_cselib_val (v);
2523 : :
2524 : 176581496 : bool had_locs = v->locs != NULL;
2525 : 176581496 : 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 : 176581496 : for (elt_loc_list **p = &v->locs; ; p = &(*p)->next)
2530 : : {
2531 : 203118721 : rtx x = (*p)->loc;
2532 : :
2533 : 203118721 : if (REG_P (x) && REGNO (x) == regno)
2534 : : {
2535 : 176581496 : unchain_one_elt_loc_list (p);
2536 : 176581496 : break;
2537 : : }
2538 : 26537225 : }
2539 : :
2540 : 176581496 : if (had_locs && cselib_useless_value_p (v))
2541 : : {
2542 : 20460398 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2543 : 0 : n_useless_debug_values++;
2544 : : else
2545 : 20460398 : n_useless_values++;
2546 : : }
2547 : 176581496 : }
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 : 751545988 : cselib_invalidate_regno (unsigned int regno, machine_mode mode)
2557 : : {
2558 : 751545988 : unsigned int endregno;
2559 : 751545988 : unsigned int i;
2560 : :
2561 : : /* If we see pseudos after reload, something is _wrong_. */
2562 : 751545988 : 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 : 209691885 : if (regno < FIRST_PSEUDO_REGISTER)
2570 : : {
2571 : 652870231 : gcc_assert (mode != VOIDmode);
2572 : :
2573 : 652870231 : if (regno < max_value_regs)
2574 : : i = 0;
2575 : : else
2576 : 613811053 : i = regno - max_value_regs;
2577 : :
2578 : 652870231 : endregno = end_hard_regno (mode, regno);
2579 : : }
2580 : : else
2581 : : {
2582 : 98675757 : i = regno;
2583 : 98675757 : endregno = regno + 1;
2584 : : }
2585 : :
2586 : 2082983451 : for (; i < endregno; i++)
2587 : : {
2588 : 1331437463 : 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 : 1700476375 : while (*l)
2593 : : {
2594 : 369038912 : cselib_val *v = (*l)->elt;
2595 : 369038912 : unsigned int this_last = i;
2596 : :
2597 : 369038912 : if (i < FIRST_PSEUDO_REGISTER && v != NULL)
2598 : 161227309 : this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
2599 : :
2600 : 369038912 : if (this_last < regno || v == NULL
2601 : 114149619 : || (v == cfa_base_preserved_val
2602 : 4056568 : && i == cfa_base_preserved_regno))
2603 : : {
2604 : 258944274 : l = &(*l)->next;
2605 : 258944274 : continue;
2606 : : }
2607 : :
2608 : : /* We have an overlap. */
2609 : 110094638 : cselib_invalidate_regno_val (i, l);
2610 : : }
2611 : : }
2612 : 751545988 : }
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 : 106215789 : cselib_invalidate_mem (rtx mem_rtx)
2620 : : {
2621 : 106215789 : cselib_val **vp, *v, *next;
2622 : 106215789 : int num_mems = 0;
2623 : 106215789 : rtx mem_addr;
2624 : :
2625 : 106215789 : mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
2626 : 106215789 : mem_rtx = canon_rtx (mem_rtx);
2627 : :
2628 : 106215789 : vp = &first_containing_mem;
2629 : 268895104 : for (v = *vp; v != &dummy_val; v = next)
2630 : : {
2631 : 162679315 : bool has_mem = false;
2632 : 162679315 : struct elt_loc_list **p = &v->locs;
2633 : 162679315 : bool had_locs = v->locs != NULL;
2634 : 162679315 : rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2635 : 162679315 : rtx sp_base = NULL_RTX;
2636 : 162679315 : HOST_WIDE_INT sp_off = 0;
2637 : :
2638 : 483428309 : while (*p)
2639 : : {
2640 : 320748994 : rtx x = (*p)->loc;
2641 : 320748994 : cselib_val *addr;
2642 : 320748994 : 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 : 320748994 : if (!MEM_P (x))
2647 : : {
2648 : 96426669 : p = &(*p)->next;
2649 : 96426669 : 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 : 224322325 : if (mem_rtx == callmem[1]
2661 : 2889847 : && num_mems < param_max_cselib_memory_locations
2662 : 2889789 : && GET_CODE (XEXP (x, 0)) == VALUE
2663 : 2889789 : && !cfun->calls_alloca)
2664 : : {
2665 : 2843430 : cselib_val *v2 = CSELIB_VAL_PTR (XEXP (x, 0));
2666 : 2843430 : rtx x_base = NULL_RTX;
2667 : 2843430 : HOST_WIDE_INT x_off = 0;
2668 : 2843430 : if (SP_DERIVED_VALUE_P (v2->val_rtx))
2669 : : x_base = v2->val_rtx;
2670 : : else
2671 : 4535942 : for (struct elt_loc_list *l = v2->locs; l; l = l->next)
2672 : 2830571 : if (GET_CODE (l->loc) == PLUS
2673 : 1508823 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2674 : 1395657 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2675 : 3895033 : && CONST_INT_P (XEXP (l->loc, 1)))
2676 : : {
2677 : 1064437 : x_base = XEXP (l->loc, 0);
2678 : 1064437 : x_off = INTVAL (XEXP (l->loc, 1));
2679 : 1064437 : 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 : 2843430 : if (x_base)
2686 : : {
2687 : 1138059 : if (sp_base == NULL_RTX)
2688 : : {
2689 : 2164880 : if (cselib_val *v3
2690 : 1082440 : = cselib_lookup_1 (stack_pointer_rtx, Pmode, 0,
2691 : : VOIDmode))
2692 : : {
2693 : 1077164 : if (SP_DERIVED_VALUE_P (v3->val_rtx))
2694 : : sp_base = v3->val_rtx;
2695 : : else
2696 : 304403 : for (struct elt_loc_list *l = v3->locs;
2697 : 610212 : l; l = l->next)
2698 : 610174 : if (GET_CODE (l->loc) == PLUS
2699 : 304365 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2700 : 304365 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2701 : 914539 : && CONST_INT_P (XEXP (l->loc, 1)))
2702 : : {
2703 : 304365 : sp_base = XEXP (l->loc, 0);
2704 : 304365 : sp_off = INTVAL (XEXP (l->loc, 1));
2705 : 304365 : break;
2706 : : }
2707 : : }
2708 : 1082440 : if (sp_base == NULL_RTX)
2709 : 5314 : 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 : 1138059 : if (sp_base == x_base)
2717 : : {
2718 : 1130626 : if (STACK_GROWS_DOWNWARD)
2719 : : {
2720 : 1130626 : 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 : 1130626 : 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 : 2834596 : if (x_base == NULL_RTX)
2751 : : {
2752 : 2834596 : has_mem = true;
2753 : 2834596 : num_mems++;
2754 : 2834596 : p = &(*p)->next;
2755 : 2834596 : continue;
2756 : : }
2757 : : }
2758 : :
2759 : 408149826 : if (num_mems < param_max_cselib_memory_locations
2760 : 442910151 : && ! canon_anti_dependence (x, false, mem_rtx,
2761 : 221422422 : GET_MODE (mem_rtx), mem_addr))
2762 : : {
2763 : 186662097 : has_mem = true;
2764 : 186662097 : num_mems++;
2765 : 186662097 : p = &(*p)->next;
2766 : 186662097 : 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 : 34825632 : addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0, GET_MODE (x));
2773 : 34825632 : addr = canonical_cselib_val (addr);
2774 : 34825632 : gcc_checking_assert (v == canonical_cselib_val (v));
2775 : 34825632 : mem_chain = &addr->addr_list;
2776 : 34832162 : for (;;)
2777 : : {
2778 : 34828897 : cselib_val *canon = canonical_cselib_val ((*mem_chain)->elt);
2779 : :
2780 : 34828897 : if (canon == v)
2781 : : {
2782 : 34825632 : unchain_one_elt_list (mem_chain);
2783 : 34825632 : break;
2784 : : }
2785 : :
2786 : : /* Record canonicalized elt. */
2787 : 3265 : (*mem_chain)->elt = canon;
2788 : :
2789 : 3265 : mem_chain = &(*mem_chain)->next;
2790 : 3265 : }
2791 : :
2792 : 34825632 : unchain_one_elt_loc_list (p);
2793 : : }
2794 : :
2795 : 162679315 : if (had_locs && cselib_useless_value_p (v))
2796 : : {
2797 : 8185166 : if (setting_insn && DEBUG_INSN_P (setting_insn))
2798 : 0 : n_useless_debug_values++;
2799 : : else
2800 : 8185166 : n_useless_values++;
2801 : : }
2802 : :
2803 : 162679315 : next = v->next_containing_mem;
2804 : 162679315 : if (has_mem)
2805 : : {
2806 : 132330390 : *vp = v;
2807 : 132330390 : vp = &(*vp)->next_containing_mem;
2808 : : }
2809 : : else
2810 : 30348925 : v->next_containing_mem = NULL;
2811 : : }
2812 : 106215789 : *vp = &dummy_val;
2813 : 106215789 : }
2814 : :
2815 : : /* Invalidate DEST. */
2816 : :
2817 : : void
2818 : 493104812 : cselib_invalidate_rtx (rtx dest)
2819 : : {
2820 : 493104812 : while (GET_CODE (dest) == SUBREG
2821 : 493104812 : || GET_CODE (dest) == ZERO_EXTRACT
2822 : 986216156 : || GET_CODE (dest) == STRICT_LOW_PART)
2823 : 6532 : dest = XEXP (dest, 0);
2824 : :
2825 : 493104812 : if (REG_P (dest))
2826 : 378487736 : cselib_invalidate_regno (REGNO (dest), GET_MODE (dest));
2827 : 114617076 : else if (MEM_P (dest))
2828 : 69838381 : cselib_invalidate_mem (dest);
2829 : 493104812 : }
2830 : :
2831 : : /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2832 : :
2833 : : static void
2834 : 477036108 : cselib_invalidate_rtx_note_stores (rtx dest, const_rtx,
2835 : : void *data ATTRIBUTE_UNUSED)
2836 : : {
2837 : 477036108 : cselib_invalidate_rtx (dest);
2838 : 477036108 : }
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 : 344655942 : cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
2846 : : {
2847 : 344655942 : if (src_elt == 0 || side_effects_p (dest))
2848 : 62240246 : return;
2849 : :
2850 : 282415696 : if (REG_P (dest))
2851 : : {
2852 : 260172287 : unsigned int dreg = REGNO (dest);
2853 : 260172287 : if (dreg < FIRST_PSEUDO_REGISTER)
2854 : : {
2855 : 190992966 : unsigned int n = REG_NREGS (dest);
2856 : :
2857 : 190992966 : if (n > max_value_regs)
2858 : 23700542 : max_value_regs = n;
2859 : : }
2860 : :
2861 : 260172287 : if (REG_VALUES (dreg) == 0)
2862 : : {
2863 : 158108995 : used_regs[n_used_regs++] = dreg;
2864 : 158108995 : REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
2865 : : }
2866 : : else
2867 : : {
2868 : : /* The register should have been invalidated. */
2869 : 102063292 : gcc_assert (REG_VALUES (dreg)->elt == 0);
2870 : 102063292 : REG_VALUES (dreg)->elt = src_elt;
2871 : : }
2872 : :
2873 : 260172287 : if (cselib_useless_value_p (src_elt))
2874 : 33073 : n_useless_values--;
2875 : 260172287 : new_elt_loc_list (src_elt, dest);
2876 : : }
2877 : 22243409 : else if (MEM_P (dest) && dest_addr_elt != 0
2878 : 22243409 : && cselib_record_memory)
2879 : : {
2880 : 22243409 : if (cselib_useless_value_p (src_elt))
2881 : 28 : n_useless_values--;
2882 : 22243409 : 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 : 3635464 : cselib_add_permanent_equiv (cselib_val *elt, rtx x, rtx_insn *insn)
2890 : : {
2891 : 3635464 : cselib_val *nelt;
2892 : 3635464 : rtx_insn *save_cselib_current_insn = cselib_current_insn;
2893 : :
2894 : 3635464 : gcc_checking_assert (elt);
2895 : 3635464 : gcc_checking_assert (PRESERVED_VALUE_P (elt->val_rtx));
2896 : 3635464 : gcc_checking_assert (!side_effects_p (x));
2897 : :
2898 : 3635464 : cselib_current_insn = insn;
2899 : :
2900 : 3635464 : nelt = cselib_lookup (x, GET_MODE (elt->val_rtx), 1, VOIDmode);
2901 : :
2902 : 3635464 : if (nelt != elt)
2903 : : {
2904 : 2803348 : cselib_any_perm_equivs = true;
2905 : :
2906 : 2803348 : if (!PRESERVED_VALUE_P (nelt->val_rtx))
2907 : 2798010 : cselib_preserve_value (nelt);
2908 : :
2909 : 2803348 : new_elt_loc_list (nelt, elt->val_rtx);
2910 : : }
2911 : :
2912 : 3635464 : cselib_current_insn = save_cselib_current_insn;
2913 : 3635464 : }
2914 : :
2915 : : /* Return TRUE if any permanent equivalences have been recorded since
2916 : : the table was last initialized. */
2917 : : bool
2918 : 1361349665 : cselib_have_permanent_equivalences (void)
2919 : : {
2920 : 1361349665 : 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 : 3159586 : cselib_record_sp_cfa_base_equiv (HOST_WIDE_INT offset, rtx_insn *insn)
2929 : : {
2930 : 3159586 : rtx sp_derived_value = NULL_RTX;
2931 : 6319172 : for (struct elt_loc_list *l = cfa_base_preserved_val->locs; l; l = l->next)
2932 : 6319172 : if (GET_CODE (l->loc) == VALUE
2933 : 6319172 : && SP_DERIVED_VALUE_P (l->loc))
2934 : : {
2935 : : sp_derived_value = l->loc;
2936 : : break;
2937 : : }
2938 : 6319172 : else if (GET_CODE (l->loc) == PLUS
2939 : 3159586 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2940 : 3159586 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2941 : 9478758 : && CONST_INT_P (XEXP (l->loc, 1)))
2942 : : {
2943 : 3159586 : sp_derived_value = XEXP (l->loc, 0);
2944 : 3159586 : offset = offset + UINTVAL (XEXP (l->loc, 1));
2945 : 3159586 : break;
2946 : : }
2947 : 3159586 : if (sp_derived_value == NULL_RTX)
2948 : : return;
2949 : 3159586 : cselib_val *val
2950 : 3159586 : = cselib_lookup_from_insn (plus_constant (Pmode, sp_derived_value, offset),
2951 : 3159586 : Pmode, 1, VOIDmode, insn);
2952 : 3159586 : if (val != NULL)
2953 : : {
2954 : 3159586 : PRESERVED_VALUE_P (val->val_rtx) = 1;
2955 : 3159586 : 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 : 29153908 : cselib_sp_derived_value_p (cselib_val *v)
2964 : : {
2965 : 29153908 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
2966 : 63691794 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
2967 : 35032501 : if (GET_CODE (l->loc) == PLUS
2968 : 7081682 : && GET_CODE (XEXP (l->loc, 0)) == VALUE
2969 : 6872223 : && SP_DERIVED_VALUE_P (XEXP (l->loc, 0))
2970 : 40247277 : && CONST_INT_P (XEXP (l->loc, 1)))
2971 : 5214776 : v = CSELIB_VAL_PTR (XEXP (l->loc, 0));
2972 : 29153908 : if (!SP_DERIVED_VALUE_P (v->val_rtx))
2973 : : return false;
2974 : 11714902 : for (struct elt_loc_list *l = v->locs; l; l = l->next)
2975 : 11714902 : if (l->loc == cfa_base_preserved_val->val_rtx)
2976 : : return true;
2977 : 11714902 : else if (GET_CODE (l->loc) == PLUS
2978 : 5709391 : && XEXP (l->loc, 0) == cfa_base_preserved_val->val_rtx
2979 : 5709391 : && 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 : 13560322 : cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED, rtx op ATTRIBUTE_UNUSED,
2999 : : rtx dest, rtx src, rtx srcoff, void *arg)
3000 : : {
3001 : 13560322 : struct cselib_record_autoinc_data *data;
3002 : 13560322 : data = (struct cselib_record_autoinc_data *)arg;
3003 : :
3004 : 13560322 : data->sets[data->n_sets].dest = dest;
3005 : :
3006 : 13560322 : if (srcoff)
3007 : 13102529 : data->sets[data->n_sets].src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
3008 : : else
3009 : 457793 : data->sets[data->n_sets].src = src;
3010 : :
3011 : 13560322 : data->n_sets++;
3012 : :
3013 : 13560322 : return 0;
3014 : : }
3015 : :
3016 : : /* Record the effects of any sets and autoincs in INSN. */
3017 : : static void
3018 : 774891156 : cselib_record_sets (rtx_insn *insn)
3019 : : {
3020 : 774891156 : int n_sets = 0;
3021 : 774891156 : int i;
3022 : 774891156 : struct cselib_set sets[MAX_SETS];
3023 : 774891156 : rtx cond = 0;
3024 : 774891156 : int n_sets_before_autoinc;
3025 : 774891156 : int n_strict_low_parts = 0;
3026 : 774891156 : struct cselib_record_autoinc_data data;
3027 : :
3028 : 774891156 : rtx body = PATTERN (insn);
3029 : 774891156 : 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 : 774891156 : if (GET_CODE (body) == SET)
3037 : : {
3038 : 344095204 : sets[0].src = SET_SRC (body);
3039 : 344095204 : sets[0].dest = SET_DEST (body);
3040 : 344095204 : n_sets = 1;
3041 : : }
3042 : 430795952 : 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 : 200160287 : for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
3047 : : {
3048 : 135130077 : rtx x = XVECEXP (body, 0, i);
3049 : :
3050 : 135130077 : if (GET_CODE (x) == SET)
3051 : : {
3052 : 71031031 : sets[n_sets].src = SET_SRC (x);
3053 : 71031031 : sets[n_sets].dest = SET_DEST (x);
3054 : 71031031 : n_sets++;
3055 : : }
3056 : : }
3057 : : }
3058 : :
3059 : 344095204 : if (n_sets == 1
3060 : 403214210 : && MEM_P (sets[0].src)
3061 : 58115670 : && !cselib_record_memory
3062 : 102255035 : && MEM_READONLY_P (sets[0].src))
3063 : : {
3064 : 3203446 : rtx note = find_reg_equal_equiv_note (insn);
3065 : :
3066 : 3203446 : if (note && CONSTANT_P (XEXP (note, 0)))
3067 : 2083481 : sets[0].src = XEXP (note, 0);
3068 : : }
3069 : :
3070 : 774891156 : data.sets = sets;
3071 : 774891156 : data.n_sets = n_sets_before_autoinc = n_sets;
3072 : 774891156 : for_each_inc_dec (PATTERN (insn), cselib_record_autoinc_cb, &data);
3073 : 774891156 : 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 : 1203577713 : for (i = 0; i < n_sets; i++)
3078 : : {
3079 : 428686557 : rtx dest = sets[i].dest;
3080 : 428686557 : 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 : 428686557 : if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
3085 : 51683 : sets[i].dest = dest = XEXP (dest, 0);
3086 : :
3087 : : /* We don't know how to record anything but REG or MEM. */
3088 : 428686557 : if (REG_P (dest)
3089 : 113545981 : || (MEM_P (dest) && cselib_record_memory))
3090 : : {
3091 : 341496356 : rtx src = sets[i].src;
3092 : 341496356 : if (cond)
3093 : 0 : src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
3094 : 341496356 : sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1, VOIDmode);
3095 : 341496356 : if (MEM_P (dest))
3096 : : {
3097 : 26355780 : machine_mode address_mode = get_address_mode (dest);
3098 : :
3099 : 26355780 : sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
3100 : : address_mode, 1,
3101 : 26355780 : GET_MODE (dest));
3102 : : }
3103 : : else
3104 : 315140576 : 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 : 428686557 : scalar_int_mode mode;
3119 : 428686557 : if (dest != orig
3120 : 51683 : && cselib_record_sets_hook
3121 : 18675 : && REG_P (dest)
3122 : 18675 : && HARD_REGISTER_P (dest)
3123 : 18675 : && sets[i].src_elt
3124 : 428705232 : && is_a <scalar_int_mode> (GET_MODE (dest), &mode)
3125 : 428705232 : && n_sets + n_strict_low_parts < MAX_SETS)
3126 : : {
3127 : 18675 : opt_scalar_int_mode wider_mode_iter;
3128 : 46141 : FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
3129 : : {
3130 : 46141 : scalar_int_mode wider_mode = wider_mode_iter.require ();
3131 : 53243 : if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD)
3132 : : break;
3133 : :
3134 : 44868 : rtx reg = gen_lowpart (wider_mode, dest);
3135 : 44868 : if (!REG_P (reg))
3136 : : break;
3137 : :
3138 : 44864 : cselib_val *v = cselib_lookup (reg, wider_mode, 0, VOIDmode);
3139 : 44864 : if (!v)
3140 : 27466 : continue;
3141 : :
3142 : 18441 : struct elt_loc_list *l;
3143 : 38819 : for (l = v->locs; l; l = l->next)
3144 : 37776 : if (l->loc == const0_rtx)
3145 : : break;
3146 : :
3147 : 1043 : if (!l)
3148 : 1043 : continue;
3149 : :
3150 : 17398 : sets[n_sets + n_strict_low_parts].dest = reg;
3151 : 17398 : sets[n_sets + n_strict_low_parts].src = dest;
3152 : 17398 : sets[n_sets + n_strict_low_parts++].src_elt = sets[i].src_elt;
3153 : 17398 : break;
3154 : : }
3155 : : }
3156 : : }
3157 : :
3158 : 774891156 : if (cselib_record_sets_hook)
3159 : 68962943 : 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 : 774891156 : note_pattern_stores (body, cselib_invalidate_rtx_note_stores, NULL);
3165 : :
3166 : 1563342634 : for (i = n_sets_before_autoinc; i < n_sets; i++)
3167 : 13560322 : 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 : 774891156 : if (n_sets >= 2 && asm_noperands (body) >= 0)
3175 : : {
3176 : 447730 : for (i = 0; i < n_sets; i++)
3177 : : {
3178 : 348518 : rtx dest = sets[i].dest;
3179 : 348518 : if (REG_P (dest) || MEM_P (dest))
3180 : : {
3181 : 348485 : int j;
3182 : 827052 : for (j = i + 1; j < n_sets; j++)
3183 : 478567 : 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 : 1203577713 : for (i = 0; i < n_sets; i++)
3194 : : {
3195 : 428686557 : rtx dest = sets[i].dest;
3196 : 428686557 : if (REG_P (dest)
3197 : 113545981 : || (MEM_P (dest) && cselib_record_memory))
3198 : 341496356 : cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
3199 : : }
3200 : :
3201 : : /* And deal with STRICT_LOW_PART. */
3202 : 774908554 : for (i = 0; i < n_strict_low_parts; i++)
3203 : : {
3204 : 17398 : if (! PRESERVED_VALUE_P (sets[n_sets + i].src_elt->val_rtx))
3205 : 0 : continue;
3206 : 17398 : machine_mode dest_mode = GET_MODE (sets[n_sets + i].dest);
3207 : 17398 : cselib_val *v
3208 : 17398 : = cselib_lookup (sets[n_sets + i].dest, dest_mode, 1, VOIDmode);
3209 : 17398 : cselib_preserve_value (v);
3210 : 17398 : rtx r = gen_rtx_ZERO_EXTEND (dest_mode,
3211 : : sets[n_sets + i].src_elt->val_rtx);
3212 : 17398 : cselib_add_permanent_equiv (v, r, insn);
3213 : : }
3214 : 774891156 : }
3215 : :
3216 : : /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
3217 : :
3218 : : bool
3219 : 38415286 : fp_setter_insn (rtx_insn *insn)
3220 : : {
3221 : 38415286 : rtx expr, pat = NULL_RTX;
3222 : :
3223 : 38415286 : if (!RTX_FRAME_RELATED_P (insn))
3224 : : return false;
3225 : :
3226 : 589650 : expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
3227 : 589650 : if (expr)
3228 : 36 : pat = XEXP (expr, 0);
3229 : 589650 : 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 : 148294 : 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 : 107527280 : cselib_invalidated_by_call_p (const function_abi &callee_abi,
3243 : : unsigned int regno, cselib_val *v)
3244 : : {
3245 : 107527280 : machine_mode mode = GET_MODE (v->val_rtx);
3246 : 107527280 : 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 : 107527280 : return callee_abi.clobbers_reg_p (mode, regno);
3258 : : }
3259 : :
3260 : : /* Record the effects of INSN. */
3261 : :
3262 : : void
3263 : 900895025 : cselib_process_insn (rtx_insn *insn)
3264 : : {
3265 : 900895025 : int i;
3266 : 900895025 : rtx x;
3267 : :
3268 : 900895025 : cselib_current_insn = insn;
3269 : :
3270 : : /* Forget everything at a CODE_LABEL or a setjmp. */
3271 : 900895025 : if ((LABEL_P (insn)
3272 : 868031196 : || (CALL_P (insn)
3273 : 32295609 : && find_reg_note (insn, REG_SETJMP, NULL)))
3274 : 900899048 : && !cselib_preserve_constants)
3275 : : {
3276 : 32867640 : cselib_reset_table (next_uid);
3277 : 32867640 : cselib_current_insn = NULL;
3278 : 32867640 : return;
3279 : : }
3280 : :
3281 : 868027385 : if (! INSN_P (insn))
3282 : : {
3283 : 93136229 : cselib_current_insn = NULL;
3284 : 93136229 : 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 : 774891156 : if (CALL_P (insn))
3291 : : {
3292 : 32291798 : function_abi callee_abi = insn_callee_abi (insn);
3293 : 3003137214 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3294 : : {
3295 : 2970845416 : elt_list **l = ®_VALUES (i);
3296 : 3179943752 : while (*l)
3297 : : {
3298 : 209098336 : cselib_val *v = (*l)->elt;
3299 : 209098336 : if (v && cselib_invalidated_by_call_p (callee_abi, i, v))
3300 : 66486858 : cselib_invalidate_regno_val (i, l);
3301 : : else
3302 : 142611478 : 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 : 32291798 : if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
3310 : 32291798 : || !(RTL_CONST_OR_PURE_CALL_P (insn)))
3311 : 29311815 : 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 : 8560484 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3317 : 5580501 : if (GET_CODE (XEXP (x, 0)) == USE
3318 : 5580225 : && MEM_P (XEXP (XEXP (x, 0), 0)))
3319 : 31085 : 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 : 2979983 : if (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca)
3327 : 2979527 : cselib_invalidate_mem (callmem[1]);
3328 : : }
3329 : : }
3330 : :
3331 : 774891156 : 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 : 774891156 : if (CALL_P (insn))
3336 : : {
3337 : 90969127 : for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
3338 : 58677329 : if (GET_CODE (XEXP (x, 0)) == CLOBBER)
3339 : 1856820 : cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
3340 : :
3341 : : /* Flush everything on setjmp. */
3342 : 32291798 : if (cselib_preserve_constants
3343 : 32291798 : && find_reg_note (insn, REG_SETJMP, NULL))
3344 : : {
3345 : 212 : cselib_preserve_only_values ();
3346 : 212 : 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 : 774891156 : if (reload_completed
3354 : 356362691 : && frame_pointer_needed
3355 : 813190202 : && fp_setter_insn (insn))
3356 : 90791 : cselib_invalidate_rtx (stack_pointer_rtx);
3357 : :
3358 : 774891156 : cselib_current_insn = NULL;
3359 : :
3360 : 774891156 : 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 : 774891156 : && ((unsigned int)n_useless_values
3365 : 2219986 : > (cselib_hash_table->elements () - n_debug_values) / 4))
3366 : 31394 : remove_useless_values ();
3367 : : }
3368 : :
3369 : : /* Initialize cselib for one pass. The caller must also call
3370 : : init_alias_analysis. */
3371 : :
3372 : : void
3373 : 9541551 : cselib_init (int record_what)
3374 : : {
3375 : 9541551 : cselib_record_memory = record_what & CSELIB_RECORD_MEMORY;
3376 : 9541551 : cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS;
3377 : 9541551 : 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 : 9541551 : if (! callmem[0])
3382 : 139856 : 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 : 9541551 : if (!callmem[1] && (!ACCUMULATE_OUTGOING_ARGS || cfun->calls_alloca))
3390 : : {
3391 : 139605 : if (STACK_GROWS_DOWNWARD)
3392 : : {
3393 : 139605 : 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 : 139605 : callmem[1] = plus_constant (Pmode, stack_pointer_rtx, off);
3400 : : }
3401 : : else
3402 : : callmem[1] = stack_pointer_rtx;
3403 : 139605 : callmem[1] = gen_rtx_MEM (BLKmode, callmem[1]);
3404 : 139605 : set_mem_size (callmem[1], GET_MODE_MASK (Pmode) >> 1);
3405 : : }
3406 : :
3407 : 9541551 : 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 : 9541551 : if (!reg_values || reg_values_size < cselib_nregs
3412 : 9252844 : || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
3413 : : {
3414 : 303072 : free (reg_values);
3415 : : /* Some space for newly emit instructions so we don't end up
3416 : : reallocating in between passes. */
3417 : 303072 : reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
3418 : 303072 : reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
3419 : : }
3420 : 9541551 : used_regs = XNEWVEC (unsigned int, cselib_nregs);
3421 : 9541551 : n_used_regs = 0;
3422 : : /* FIXME: enable sanitization (PR87845) */
3423 : 9541551 : cselib_hash_table
3424 : 9541551 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3425 : 9541551 : /* sanitize_eq_and_hash */ false);
3426 : 9541551 : if (cselib_preserve_constants)
3427 : 477567 : cselib_preserved_hash_table
3428 : 477567 : = new hash_table<cselib_hasher> (31, /* ggc */ false,
3429 : 477567 : /* sanitize_eq_and_hash */ false);
3430 : 9541551 : next_uid = 1;
3431 : 9541551 : }
3432 : :
3433 : : /* Called when the current user is done with cselib. */
3434 : :
3435 : : void
3436 : 9541551 : cselib_finish (void)
3437 : : {
3438 : 9541551 : bool preserved = cselib_preserve_constants;
3439 : 9541551 : cselib_discard_hook = NULL;
3440 : 9541551 : cselib_preserve_constants = false;
3441 : 9541551 : cselib_any_perm_equivs = false;
3442 : 9541551 : cfa_base_preserved_val = NULL;
3443 : 9541551 : cfa_base_preserved_regno = INVALID_REGNUM;
3444 : 9541551 : elt_list_pool.release ();
3445 : 9541551 : elt_loc_list_pool.release ();
3446 : 9541551 : cselib_val_pool.release ();
3447 : 9541551 : value_pool.release ();
3448 : 9541551 : cselib_clear_table ();
3449 : 9541551 : delete cselib_hash_table;
3450 : 9541551 : cselib_hash_table = NULL;
3451 : 9541551 : if (preserved)
3452 : 477567 : delete cselib_preserved_hash_table;
3453 : 9541551 : cselib_preserved_hash_table = NULL;
3454 : 9541551 : free (used_regs);
3455 : 9541551 : used_regs = 0;
3456 : 9541551 : n_useless_values = 0;
3457 : 9541551 : n_useless_debug_values = 0;
3458 : 9541551 : n_debug_values = 0;
3459 : 9541551 : next_uid = 0;
3460 : 9541551 : }
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"
|
