1 /* Common subexpression elimination library for GNU compiler.
2 Copyright (C) 1987-2019 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 "params.h"
35
36 /* A list of cselib_val structures. */
37 struct elt_list
38 {
39 struct elt_list *next;
40 cselib_val *elt;
41 };
42
43 static bool cselib_record_memory;
44 static bool cselib_preserve_constants;
45 static bool cselib_any_perm_equivs;
46 static inline void promote_debug_loc (struct elt_loc_list *l);
47 static struct elt_list *new_elt_list (struct elt_list *, cselib_val *);
48 static void new_elt_loc_list (cselib_val *, rtx);
49 static void unchain_one_value (cselib_val *);
50 static void unchain_one_elt_list (struct elt_list **);
51 static void unchain_one_elt_loc_list (struct elt_loc_list **);
52 static void remove_useless_values (void);
53 static unsigned int cselib_hash_rtx (rtx, int, machine_mode);
54 static cselib_val *new_cselib_val (unsigned int, machine_mode, rtx);
55 static void add_mem_for_addr (cselib_val *, cselib_val *, rtx);
56 static cselib_val *cselib_lookup_mem (rtx, int);
57 static void cselib_invalidate_regno (unsigned int, machine_mode,
58 const_rtx = NULL);
59 static void cselib_invalidate_mem (rtx);
60 static void cselib_record_set (rtx, cselib_val *, cselib_val *);
61 static void cselib_record_sets (rtx_insn *);
62
63 struct expand_value_data
64 {
65 bitmap regs_active;
66 cselib_expand_callback callback;
67 void *callback_arg;
68 bool dummy;
69 };
70
71 static rtx cselib_expand_value_rtx_1 (rtx, struct expand_value_data *, int);
72
73 /* There are three ways in which cselib can look up an rtx:
74 - for a REG, the reg_values table (which is indexed by regno) is used
75 - for a MEM, we recursively look up its address and then follow the
76 addr_list of that value
77 - for everything else, we compute a hash value and go through the hash
78 table. Since different rtx's can still have the same hash value,
79 this involves walking the table entries for a given value and comparing
80 the locations of the entries with the rtx we are looking up. */
81
82 struct cselib_hasher : nofree_ptr_hash <cselib_val>
83 {
84 struct key {
85 /* The rtx value and its mode (needed separately for constant
86 integers). */
87 machine_mode mode;
88 rtx x;
89 /* The mode of the contaning MEM, if any, otherwise VOIDmode. */
90 machine_mode memmode;
91 };
92 typedef key *compare_type;
93 static inline hashval_t hash (const cselib_val *);
94 static inline bool equal (const cselib_val *, const key *);
95 };
96
97 /* The hash function for our hash table. The value is always computed with
98 cselib_hash_rtx when adding an element; this function just extracts the
99 hash value from a cselib_val structure. */
100
101 inline hashval_t
hash(const cselib_val * v)102 cselib_hasher::hash (const cselib_val *v)
103 {
104 return v->hash;
105 }
106
107 /* The equality test for our hash table. The first argument V is a table
108 element (i.e. a cselib_val), while the second arg X is an rtx. We know
109 that all callers of htab_find_slot_with_hash will wrap CONST_INTs into a
110 CONST of an appropriate mode. */
111
112 inline bool
equal(const cselib_val * v,const key * x_arg)113 cselib_hasher::equal (const cselib_val *v, const key *x_arg)
114 {
115 struct elt_loc_list *l;
116 rtx x = x_arg->x;
117 machine_mode mode = x_arg->mode;
118 machine_mode memmode = x_arg->memmode;
119
120 if (mode != GET_MODE (v->val_rtx))
121 return false;
122
123 if (GET_CODE (x) == VALUE)
124 return x == v->val_rtx;
125
126 /* We don't guarantee that distinct rtx's have different hash values,
127 so we need to do a comparison. */
128 for (l = v->locs; l; l = l->next)
129 if (rtx_equal_for_cselib_1 (l->loc, x, memmode, 0))
130 {
131 promote_debug_loc (l);
132 return true;
133 }
134
135 return false;
136 }
137
138 /* A table that enables us to look up elts by their value. */
139 static hash_table<cselib_hasher> *cselib_hash_table;
140
141 /* A table to hold preserved values. */
142 static hash_table<cselib_hasher> *cselib_preserved_hash_table;
143
144 /* This is a global so we don't have to pass this through every function.
145 It is used in new_elt_loc_list to set SETTING_INSN. */
146 static rtx_insn *cselib_current_insn;
147
148 /* The unique id that the next create value will take. */
149 static unsigned int next_uid;
150
151 /* The number of registers we had when the varrays were last resized. */
152 static unsigned int cselib_nregs;
153
154 /* Count values without known locations, or with only locations that
155 wouldn't have been known except for debug insns. Whenever this
156 grows too big, we remove these useless values from the table.
157
158 Counting values with only debug values is a bit tricky. We don't
159 want to increment n_useless_values when we create a value for a
160 debug insn, for this would get n_useless_values out of sync, but we
161 want increment it if all locs in the list that were ever referenced
162 in nondebug insns are removed from the list.
163
164 In the general case, once we do that, we'd have to stop accepting
165 nondebug expressions in the loc list, to avoid having two values
166 equivalent that, without debug insns, would have been made into
167 separate values. However, because debug insns never introduce
168 equivalences themselves (no assignments), the only means for
169 growing loc lists is through nondebug assignments. If the locs
170 also happen to be referenced in debug insns, it will work just fine.
171
172 A consequence of this is that there's at most one debug-only loc in
173 each loc list. If we keep it in the first entry, testing whether
174 we have a debug-only loc list takes O(1).
175
176 Furthermore, since any additional entry in a loc list containing a
177 debug loc would have to come from an assignment (nondebug) that
178 references both the initial debug loc and the newly-equivalent loc,
179 the initial debug loc would be promoted to a nondebug loc, and the
180 loc list would not contain debug locs any more.
181
182 So the only case we have to be careful with in order to keep
183 n_useless_values in sync between debug and nondebug compilations is
184 to avoid incrementing n_useless_values when removing the single loc
185 from a value that turns out to not appear outside debug values. We
186 increment n_useless_debug_values instead, and leave such values
187 alone until, for other reasons, we garbage-collect useless
188 values. */
189 static int n_useless_values;
190 static int n_useless_debug_values;
191
192 /* Count values whose locs have been taken exclusively from debug
193 insns for the entire life of the value. */
194 static int n_debug_values;
195
196 /* Number of useless values before we remove them from the hash table. */
197 #define MAX_USELESS_VALUES 32
198
199 /* This table maps from register number to values. It does not
200 contain pointers to cselib_val structures, but rather elt_lists.
201 The purpose is to be able to refer to the same register in
202 different modes. The first element of the list defines the mode in
203 which the register was set; if the mode is unknown or the value is
204 no longer valid in that mode, ELT will be NULL for the first
205 element. */
206 static struct elt_list **reg_values;
207 static unsigned int reg_values_size;
208 #define REG_VALUES(i) reg_values[i]
209
210 /* The largest number of hard regs used by any entry added to the
211 REG_VALUES table. Cleared on each cselib_clear_table() invocation. */
212 static unsigned int max_value_regs;
213
214 /* Here the set of indices I with REG_VALUES(I) != 0 is saved. This is used
215 in cselib_clear_table() for fast emptying. */
216 static unsigned int *used_regs;
217 static unsigned int n_used_regs;
218
219 /* We pass this to cselib_invalidate_mem to invalidate all of
220 memory for a non-const call instruction. */
221 static GTY(()) rtx callmem;
222
223 /* Set by discard_useless_locs if it deleted the last location of any
224 value. */
225 static int values_became_useless;
226
227 /* Used as stop element of the containing_mem list so we can check
228 presence in the list by checking the next pointer. */
229 static cselib_val dummy_val;
230
231 /* If non-NULL, value of the eliminated arg_pointer_rtx or frame_pointer_rtx
232 that is constant through the whole function and should never be
233 eliminated. */
234 static cselib_val *cfa_base_preserved_val;
235 static unsigned int cfa_base_preserved_regno = INVALID_REGNUM;
236
237 /* Used to list all values that contain memory reference.
238 May or may not contain the useless values - the list is compacted
239 each time memory is invalidated. */
240 static cselib_val *first_containing_mem = &dummy_val;
241
242 static object_allocator<elt_list> elt_list_pool ("elt_list");
243 static object_allocator<elt_loc_list> elt_loc_list_pool ("elt_loc_list");
244 static object_allocator<cselib_val> cselib_val_pool ("cselib_val_list");
245
246 static pool_allocator value_pool ("value", RTX_CODE_SIZE (VALUE));
247
248 /* If nonnull, cselib will call this function before freeing useless
249 VALUEs. A VALUE is deemed useless if its "locs" field is null. */
250 void (*cselib_discard_hook) (cselib_val *);
251
252 /* If nonnull, cselib will call this function before recording sets or
253 even clobbering outputs of INSN. All the recorded sets will be
254 represented in the array sets[n_sets]. new_val_min can be used to
255 tell whether values present in sets are introduced by this
256 instruction. */
257 void (*cselib_record_sets_hook) (rtx_insn *insn, struct cselib_set *sets,
258 int n_sets);
259
260 #define PRESERVED_VALUE_P(RTX) \
261 (RTL_FLAG_CHECK1 ("PRESERVED_VALUE_P", (RTX), VALUE)->unchanging)
262
263 #define SP_BASED_VALUE_P(RTX) \
264 (RTL_FLAG_CHECK1 ("SP_BASED_VALUE_P", (RTX), VALUE)->jump)
265
266
267
268 /* Allocate a struct elt_list and fill in its two elements with the
269 arguments. */
270
271 static inline struct elt_list *
new_elt_list(struct elt_list * next,cselib_val * elt)272 new_elt_list (struct elt_list *next, cselib_val *elt)
273 {
274 elt_list *el = elt_list_pool.allocate ();
275 el->next = next;
276 el->elt = elt;
277 return el;
278 }
279
280 /* Allocate a struct elt_loc_list with LOC and prepend it to VAL's loc
281 list. */
282
283 static inline void
new_elt_loc_list(cselib_val * val,rtx loc)284 new_elt_loc_list (cselib_val *val, rtx loc)
285 {
286 struct elt_loc_list *el, *next = val->locs;
287
288 gcc_checking_assert (!next || !next->setting_insn
289 || !DEBUG_INSN_P (next->setting_insn)
290 || cselib_current_insn == next->setting_insn);
291
292 /* If we're creating the first loc in a debug insn context, we've
293 just created a debug value. Count it. */
294 if (!next && cselib_current_insn && DEBUG_INSN_P (cselib_current_insn))
295 n_debug_values++;
296
297 val = canonical_cselib_val (val);
298 next = val->locs;
299
300 if (GET_CODE (loc) == VALUE)
301 {
302 loc = canonical_cselib_val (CSELIB_VAL_PTR (loc))->val_rtx;
303
304 gcc_checking_assert (PRESERVED_VALUE_P (loc)
305 == PRESERVED_VALUE_P (val->val_rtx));
306
307 if (val->val_rtx == loc)
308 return;
309 else if (val->uid > CSELIB_VAL_PTR (loc)->uid)
310 {
311 /* Reverse the insertion. */
312 new_elt_loc_list (CSELIB_VAL_PTR (loc), val->val_rtx);
313 return;
314 }
315
316 gcc_checking_assert (val->uid < CSELIB_VAL_PTR (loc)->uid);
317
318 if (CSELIB_VAL_PTR (loc)->locs)
319 {
320 /* Bring all locs from LOC to VAL. */
321 for (el = CSELIB_VAL_PTR (loc)->locs; el->next; el = el->next)
322 {
323 /* Adjust values that have LOC as canonical so that VAL
324 becomes their canonical. */
325 if (el->loc && GET_CODE (el->loc) == VALUE)
326 {
327 gcc_checking_assert (CSELIB_VAL_PTR (el->loc)->locs->loc
328 == loc);
329 CSELIB_VAL_PTR (el->loc)->locs->loc = val->val_rtx;
330 }
331 }
332 el->next = val->locs;
333 next = val->locs = CSELIB_VAL_PTR (loc)->locs;
334 }
335
336 if (CSELIB_VAL_PTR (loc)->addr_list)
337 {
338 /* Bring in addr_list into canonical node. */
339 struct elt_list *last = CSELIB_VAL_PTR (loc)->addr_list;
340 while (last->next)
341 last = last->next;
342 last->next = val->addr_list;
343 val->addr_list = CSELIB_VAL_PTR (loc)->addr_list;
344 CSELIB_VAL_PTR (loc)->addr_list = NULL;
345 }
346
347 if (CSELIB_VAL_PTR (loc)->next_containing_mem != NULL
348 && val->next_containing_mem == NULL)
349 {
350 /* Add VAL to the containing_mem list after LOC. LOC will
351 be removed when we notice it doesn't contain any
352 MEMs. */
353 val->next_containing_mem = CSELIB_VAL_PTR (loc)->next_containing_mem;
354 CSELIB_VAL_PTR (loc)->next_containing_mem = val;
355 }
356
357 /* Chain LOC back to VAL. */
358 el = elt_loc_list_pool.allocate ();
359 el->loc = val->val_rtx;
360 el->setting_insn = cselib_current_insn;
361 el->next = NULL;
362 CSELIB_VAL_PTR (loc)->locs = el;
363 }
364
365 el = elt_loc_list_pool.allocate ();
366 el->loc = loc;
367 el->setting_insn = cselib_current_insn;
368 el->next = next;
369 val->locs = el;
370 }
371
372 /* Promote loc L to a nondebug cselib_current_insn if L is marked as
373 originating from a debug insn, maintaining the debug values
374 count. */
375
376 static inline void
promote_debug_loc(struct elt_loc_list * l)377 promote_debug_loc (struct elt_loc_list *l)
378 {
379 if (l && l->setting_insn && DEBUG_INSN_P (l->setting_insn)
380 && (!cselib_current_insn || !DEBUG_INSN_P (cselib_current_insn)))
381 {
382 n_debug_values--;
383 l->setting_insn = cselib_current_insn;
384 if (cselib_preserve_constants && l->next)
385 {
386 gcc_assert (l->next->setting_insn
387 && DEBUG_INSN_P (l->next->setting_insn)
388 && !l->next->next);
389 l->next->setting_insn = cselib_current_insn;
390 }
391 else
392 gcc_assert (!l->next);
393 }
394 }
395
396 /* The elt_list at *PL is no longer needed. Unchain it and free its
397 storage. */
398
399 static inline void
unchain_one_elt_list(struct elt_list ** pl)400 unchain_one_elt_list (struct elt_list **pl)
401 {
402 struct elt_list *l = *pl;
403
404 *pl = l->next;
405 elt_list_pool.remove (l);
406 }
407
408 /* Likewise for elt_loc_lists. */
409
410 static void
unchain_one_elt_loc_list(struct elt_loc_list ** pl)411 unchain_one_elt_loc_list (struct elt_loc_list **pl)
412 {
413 struct elt_loc_list *l = *pl;
414
415 *pl = l->next;
416 elt_loc_list_pool.remove (l);
417 }
418
419 /* Likewise for cselib_vals. This also frees the addr_list associated with
420 V. */
421
422 static void
unchain_one_value(cselib_val * v)423 unchain_one_value (cselib_val *v)
424 {
425 while (v->addr_list)
426 unchain_one_elt_list (&v->addr_list);
427
428 cselib_val_pool.remove (v);
429 }
430
431 /* Remove all entries from the hash table. Also used during
432 initialization. */
433
434 void
cselib_clear_table(void)435 cselib_clear_table (void)
436 {
437 cselib_reset_table (1);
438 }
439
440 /* Return TRUE if V is a constant, a function invariant or a VALUE
441 equivalence; FALSE otherwise. */
442
443 static bool
invariant_or_equiv_p(cselib_val * v)444 invariant_or_equiv_p (cselib_val *v)
445 {
446 struct elt_loc_list *l;
447
448 if (v == cfa_base_preserved_val)
449 return true;
450
451 /* Keep VALUE equivalences around. */
452 for (l = v->locs; l; l = l->next)
453 if (GET_CODE (l->loc) == VALUE)
454 return true;
455
456 if (v->locs != NULL
457 && v->locs->next == NULL)
458 {
459 if (CONSTANT_P (v->locs->loc)
460 && (GET_CODE (v->locs->loc) != CONST
461 || !references_value_p (v->locs->loc, 0)))
462 return true;
463 /* Although a debug expr may be bound to different expressions,
464 we can preserve it as if it was constant, to get unification
465 and proper merging within var-tracking. */
466 if (GET_CODE (v->locs->loc) == DEBUG_EXPR
467 || GET_CODE (v->locs->loc) == DEBUG_IMPLICIT_PTR
468 || GET_CODE (v->locs->loc) == ENTRY_VALUE
469 || GET_CODE (v->locs->loc) == DEBUG_PARAMETER_REF)
470 return true;
471
472 /* (plus (value V) (const_int C)) is invariant iff V is invariant. */
473 if (GET_CODE (v->locs->loc) == PLUS
474 && CONST_INT_P (XEXP (v->locs->loc, 1))
475 && GET_CODE (XEXP (v->locs->loc, 0)) == VALUE
476 && invariant_or_equiv_p (CSELIB_VAL_PTR (XEXP (v->locs->loc, 0))))
477 return true;
478 }
479
480 return false;
481 }
482
483 /* Remove from hash table all VALUEs except constants, function
484 invariants and VALUE equivalences. */
485
486 int
preserve_constants_and_equivs(cselib_val ** x,void * info ATTRIBUTE_UNUSED)487 preserve_constants_and_equivs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
488 {
489 cselib_val *v = *x;
490
491 if (invariant_or_equiv_p (v))
492 {
493 cselib_hasher::key lookup = {
494 GET_MODE (v->val_rtx), v->val_rtx, VOIDmode
495 };
496 cselib_val **slot
497 = cselib_preserved_hash_table->find_slot_with_hash (&lookup,
498 v->hash, INSERT);
499 gcc_assert (!*slot);
500 *slot = v;
501 }
502
503 cselib_hash_table->clear_slot (x);
504
505 return 1;
506 }
507
508 /* Remove all entries from the hash table, arranging for the next
509 value to be numbered NUM. */
510
511 void
cselib_reset_table(unsigned int num)512 cselib_reset_table (unsigned int num)
513 {
514 unsigned int i;
515
516 max_value_regs = 0;
517
518 if (cfa_base_preserved_val)
519 {
520 unsigned int regno = cfa_base_preserved_regno;
521 unsigned int new_used_regs = 0;
522 for (i = 0; i < n_used_regs; i++)
523 if (used_regs[i] == regno)
524 {
525 new_used_regs = 1;
526 continue;
527 }
528 else
529 REG_VALUES (used_regs[i]) = 0;
530 gcc_assert (new_used_regs == 1);
531 n_used_regs = new_used_regs;
532 used_regs[0] = regno;
533 max_value_regs
534 = hard_regno_nregs (regno,
535 GET_MODE (cfa_base_preserved_val->locs->loc));
536 }
537 else
538 {
539 for (i = 0; i < n_used_regs; i++)
540 REG_VALUES (used_regs[i]) = 0;
541 n_used_regs = 0;
542 }
543
544 if (cselib_preserve_constants)
545 cselib_hash_table->traverse <void *, preserve_constants_and_equivs>
546 (NULL);
547 else
548 {
549 cselib_hash_table->empty ();
550 gcc_checking_assert (!cselib_any_perm_equivs);
551 }
552
553 n_useless_values = 0;
554 n_useless_debug_values = 0;
555 n_debug_values = 0;
556
557 next_uid = num;
558
559 first_containing_mem = &dummy_val;
560 }
561
562 /* Return the number of the next value that will be generated. */
563
564 unsigned int
cselib_get_next_uid(void)565 cselib_get_next_uid (void)
566 {
567 return next_uid;
568 }
569
570 /* Search for X, whose hashcode is HASH, in CSELIB_HASH_TABLE,
571 INSERTing if requested. When X is part of the address of a MEM,
572 MEMMODE should specify the mode of the MEM. */
573
574 static cselib_val **
cselib_find_slot(machine_mode mode,rtx x,hashval_t hash,enum insert_option insert,machine_mode memmode)575 cselib_find_slot (machine_mode mode, rtx x, hashval_t hash,
576 enum insert_option insert, machine_mode memmode)
577 {
578 cselib_val **slot = NULL;
579 cselib_hasher::key lookup = { mode, x, memmode };
580 if (cselib_preserve_constants)
581 slot = cselib_preserved_hash_table->find_slot_with_hash (&lookup, hash,
582 NO_INSERT);
583 if (!slot)
584 slot = cselib_hash_table->find_slot_with_hash (&lookup, hash, insert);
585 return slot;
586 }
587
588 /* Return true if X contains a VALUE rtx. If ONLY_USELESS is set, we
589 only return true for values which point to a cselib_val whose value
590 element has been set to zero, which implies the cselib_val will be
591 removed. */
592
593 int
references_value_p(const_rtx x,int only_useless)594 references_value_p (const_rtx x, int only_useless)
595 {
596 const enum rtx_code code = GET_CODE (x);
597 const char *fmt = GET_RTX_FORMAT (code);
598 int i, j;
599
600 if (GET_CODE (x) == VALUE
601 && (! only_useless ||
602 (CSELIB_VAL_PTR (x)->locs == 0 && !PRESERVED_VALUE_P (x))))
603 return 1;
604
605 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
606 {
607 if (fmt[i] == 'e' && references_value_p (XEXP (x, i), only_useless))
608 return 1;
609 else if (fmt[i] == 'E')
610 for (j = 0; j < XVECLEN (x, i); j++)
611 if (references_value_p (XVECEXP (x, i, j), only_useless))
612 return 1;
613 }
614
615 return 0;
616 }
617
618 /* For all locations found in X, delete locations that reference useless
619 values (i.e. values without any location). Called through
620 htab_traverse. */
621
622 int
discard_useless_locs(cselib_val ** x,void * info ATTRIBUTE_UNUSED)623 discard_useless_locs (cselib_val **x, void *info ATTRIBUTE_UNUSED)
624 {
625 cselib_val *v = *x;
626 struct elt_loc_list **p = &v->locs;
627 bool had_locs = v->locs != NULL;
628 rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
629
630 while (*p)
631 {
632 if (references_value_p ((*p)->loc, 1))
633 unchain_one_elt_loc_list (p);
634 else
635 p = &(*p)->next;
636 }
637
638 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
639 {
640 if (setting_insn && DEBUG_INSN_P (setting_insn))
641 n_useless_debug_values++;
642 else
643 n_useless_values++;
644 values_became_useless = 1;
645 }
646 return 1;
647 }
648
649 /* If X is a value with no locations, remove it from the hashtable. */
650
651 int
discard_useless_values(cselib_val ** x,void * info ATTRIBUTE_UNUSED)652 discard_useless_values (cselib_val **x, void *info ATTRIBUTE_UNUSED)
653 {
654 cselib_val *v = *x;
655
656 if (v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
657 {
658 if (cselib_discard_hook)
659 cselib_discard_hook (v);
660
661 CSELIB_VAL_PTR (v->val_rtx) = NULL;
662 cselib_hash_table->clear_slot (x);
663 unchain_one_value (v);
664 n_useless_values--;
665 }
666
667 return 1;
668 }
669
670 /* Clean out useless values (i.e. those which no longer have locations
671 associated with them) from the hash table. */
672
673 static void
remove_useless_values(void)674 remove_useless_values (void)
675 {
676 cselib_val **p, *v;
677
678 /* First pass: eliminate locations that reference the value. That in
679 turn can make more values useless. */
680 do
681 {
682 values_became_useless = 0;
683 cselib_hash_table->traverse <void *, discard_useless_locs> (NULL);
684 }
685 while (values_became_useless);
686
687 /* Second pass: actually remove the values. */
688
689 p = &first_containing_mem;
690 for (v = *p; v != &dummy_val; v = v->next_containing_mem)
691 if (v->locs && v == canonical_cselib_val (v))
692 {
693 *p = v;
694 p = &(*p)->next_containing_mem;
695 }
696 *p = &dummy_val;
697
698 n_useless_values += n_useless_debug_values;
699 n_debug_values -= n_useless_debug_values;
700 n_useless_debug_values = 0;
701
702 cselib_hash_table->traverse <void *, discard_useless_values> (NULL);
703
704 gcc_assert (!n_useless_values);
705 }
706
707 /* Arrange for a value to not be removed from the hash table even if
708 it becomes useless. */
709
710 void
cselib_preserve_value(cselib_val * v)711 cselib_preserve_value (cselib_val *v)
712 {
713 PRESERVED_VALUE_P (v->val_rtx) = 1;
714 }
715
716 /* Test whether a value is preserved. */
717
718 bool
cselib_preserved_value_p(cselib_val * v)719 cselib_preserved_value_p (cselib_val *v)
720 {
721 return PRESERVED_VALUE_P (v->val_rtx);
722 }
723
724 /* Arrange for a REG value to be assumed constant through the whole function,
725 never invalidated and preserved across cselib_reset_table calls. */
726
727 void
cselib_preserve_cfa_base_value(cselib_val * v,unsigned int regno)728 cselib_preserve_cfa_base_value (cselib_val *v, unsigned int regno)
729 {
730 if (cselib_preserve_constants
731 && v->locs
732 && REG_P (v->locs->loc))
733 {
734 cfa_base_preserved_val = v;
735 cfa_base_preserved_regno = regno;
736 }
737 }
738
739 /* Clean all non-constant expressions in the hash table, but retain
740 their values. */
741
742 void
cselib_preserve_only_values(void)743 cselib_preserve_only_values (void)
744 {
745 int i;
746
747 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
748 cselib_invalidate_regno (i, reg_raw_mode[i]);
749
750 cselib_invalidate_mem (callmem);
751
752 remove_useless_values ();
753
754 gcc_assert (first_containing_mem == &dummy_val);
755 }
756
757 /* Arrange for a value to be marked as based on stack pointer
758 for find_base_term purposes. */
759
760 void
cselib_set_value_sp_based(cselib_val * v)761 cselib_set_value_sp_based (cselib_val *v)
762 {
763 SP_BASED_VALUE_P (v->val_rtx) = 1;
764 }
765
766 /* Test whether a value is based on stack pointer for
767 find_base_term purposes. */
768
769 bool
cselib_sp_based_value_p(cselib_val * v)770 cselib_sp_based_value_p (cselib_val *v)
771 {
772 return SP_BASED_VALUE_P (v->val_rtx);
773 }
774
775 /* Return the mode in which a register was last set. If X is not a
776 register, return its mode. If the mode in which the register was
777 set is not known, or the value was already clobbered, return
778 VOIDmode. */
779
780 machine_mode
cselib_reg_set_mode(const_rtx x)781 cselib_reg_set_mode (const_rtx x)
782 {
783 if (!REG_P (x))
784 return GET_MODE (x);
785
786 if (REG_VALUES (REGNO (x)) == NULL
787 || REG_VALUES (REGNO (x))->elt == NULL)
788 return VOIDmode;
789
790 return GET_MODE (REG_VALUES (REGNO (x))->elt->val_rtx);
791 }
792
793 /* If x is a PLUS or an autoinc operation, expand the operation,
794 storing the offset, if any, in *OFF. */
795
796 static rtx
autoinc_split(rtx x,rtx * off,machine_mode memmode)797 autoinc_split (rtx x, rtx *off, machine_mode memmode)
798 {
799 switch (GET_CODE (x))
800 {
801 case PLUS:
802 *off = XEXP (x, 1);
803 return XEXP (x, 0);
804
805 case PRE_DEC:
806 if (memmode == VOIDmode)
807 return x;
808
809 *off = gen_int_mode (-GET_MODE_SIZE (memmode), GET_MODE (x));
810 return XEXP (x, 0);
811
812 case PRE_INC:
813 if (memmode == VOIDmode)
814 return x;
815
816 *off = gen_int_mode (GET_MODE_SIZE (memmode), GET_MODE (x));
817 return XEXP (x, 0);
818
819 case PRE_MODIFY:
820 return XEXP (x, 1);
821
822 case POST_DEC:
823 case POST_INC:
824 case POST_MODIFY:
825 return XEXP (x, 0);
826
827 default:
828 return x;
829 }
830 }
831
832 /* Return nonzero if we can prove that X and Y contain the same value,
833 taking our gathered information into account. MEMMODE holds the
834 mode of the enclosing MEM, if any, as required to deal with autoinc
835 addressing modes. If X and Y are not (known to be) part of
836 addresses, MEMMODE should be VOIDmode. */
837
838 int
rtx_equal_for_cselib_1(rtx x,rtx y,machine_mode memmode,int depth)839 rtx_equal_for_cselib_1 (rtx x, rtx y, machine_mode memmode, int depth)
840 {
841 enum rtx_code code;
842 const char *fmt;
843 int i;
844
845 if (REG_P (x) || MEM_P (x))
846 {
847 cselib_val *e = cselib_lookup (x, GET_MODE (x), 0, memmode);
848
849 if (e)
850 x = e->val_rtx;
851 }
852
853 if (REG_P (y) || MEM_P (y))
854 {
855 cselib_val *e = cselib_lookup (y, GET_MODE (y), 0, memmode);
856
857 if (e)
858 y = e->val_rtx;
859 }
860
861 if (x == y)
862 return 1;
863
864 if (GET_CODE (x) == VALUE)
865 {
866 cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (x));
867 struct elt_loc_list *l;
868
869 if (GET_CODE (y) == VALUE)
870 return e == canonical_cselib_val (CSELIB_VAL_PTR (y));
871
872 if (depth == 128)
873 return 0;
874
875 for (l = e->locs; l; l = l->next)
876 {
877 rtx t = l->loc;
878
879 /* Avoid infinite recursion. We know we have the canonical
880 value, so we can just skip any values in the equivalence
881 list. */
882 if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
883 continue;
884 else if (rtx_equal_for_cselib_1 (t, y, memmode, depth + 1))
885 return 1;
886 }
887
888 return 0;
889 }
890 else if (GET_CODE (y) == VALUE)
891 {
892 cselib_val *e = canonical_cselib_val (CSELIB_VAL_PTR (y));
893 struct elt_loc_list *l;
894
895 if (depth == 128)
896 return 0;
897
898 for (l = e->locs; l; l = l->next)
899 {
900 rtx t = l->loc;
901
902 if (REG_P (t) || MEM_P (t) || GET_CODE (t) == VALUE)
903 continue;
904 else if (rtx_equal_for_cselib_1 (x, t, memmode, depth + 1))
905 return 1;
906 }
907
908 return 0;
909 }
910
911 if (GET_MODE (x) != GET_MODE (y))
912 return 0;
913
914 if (GET_CODE (x) != GET_CODE (y))
915 {
916 rtx xorig = x, yorig = y;
917 rtx xoff = NULL, yoff = NULL;
918
919 x = autoinc_split (x, &xoff, memmode);
920 y = autoinc_split (y, &yoff, memmode);
921
922 if (!xoff != !yoff)
923 return 0;
924
925 if (xoff && !rtx_equal_for_cselib_1 (xoff, yoff, memmode, depth))
926 return 0;
927
928 /* Don't recurse if nothing changed. */
929 if (x != xorig || y != yorig)
930 return rtx_equal_for_cselib_1 (x, y, memmode, depth);
931
932 return 0;
933 }
934
935 /* These won't be handled correctly by the code below. */
936 switch (GET_CODE (x))
937 {
938 CASE_CONST_UNIQUE:
939 case DEBUG_EXPR:
940 return 0;
941
942 case CONST_VECTOR:
943 if (!same_vector_encodings_p (x, y))
944 return false;
945 break;
946
947 case DEBUG_IMPLICIT_PTR:
948 return DEBUG_IMPLICIT_PTR_DECL (x)
949 == DEBUG_IMPLICIT_PTR_DECL (y);
950
951 case DEBUG_PARAMETER_REF:
952 return DEBUG_PARAMETER_REF_DECL (x)
953 == DEBUG_PARAMETER_REF_DECL (y);
954
955 case ENTRY_VALUE:
956 /* ENTRY_VALUEs are function invariant, it is thus undesirable to
957 use rtx_equal_for_cselib_1 to compare the operands. */
958 return rtx_equal_p (ENTRY_VALUE_EXP (x), ENTRY_VALUE_EXP (y));
959
960 case LABEL_REF:
961 return label_ref_label (x) == label_ref_label (y);
962
963 case REG:
964 return REGNO (x) == REGNO (y);
965
966 case MEM:
967 /* We have to compare any autoinc operations in the addresses
968 using this MEM's mode. */
969 return rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 0), GET_MODE (x),
970 depth);
971
972 default:
973 break;
974 }
975
976 code = GET_CODE (x);
977 fmt = GET_RTX_FORMAT (code);
978
979 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
980 {
981 int j;
982
983 switch (fmt[i])
984 {
985 case 'w':
986 if (XWINT (x, i) != XWINT (y, i))
987 return 0;
988 break;
989
990 case 'n':
991 case 'i':
992 if (XINT (x, i) != XINT (y, i))
993 return 0;
994 break;
995
996 case 'p':
997 if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
998 return 0;
999 break;
1000
1001 case 'V':
1002 case 'E':
1003 /* Two vectors must have the same length. */
1004 if (XVECLEN (x, i) != XVECLEN (y, i))
1005 return 0;
1006
1007 /* And the corresponding elements must match. */
1008 for (j = 0; j < XVECLEN (x, i); j++)
1009 if (! rtx_equal_for_cselib_1 (XVECEXP (x, i, j),
1010 XVECEXP (y, i, j), memmode, depth))
1011 return 0;
1012 break;
1013
1014 case 'e':
1015 if (i == 1
1016 && targetm.commutative_p (x, UNKNOWN)
1017 && rtx_equal_for_cselib_1 (XEXP (x, 1), XEXP (y, 0), memmode,
1018 depth)
1019 && rtx_equal_for_cselib_1 (XEXP (x, 0), XEXP (y, 1), memmode,
1020 depth))
1021 return 1;
1022 if (! rtx_equal_for_cselib_1 (XEXP (x, i), XEXP (y, i), memmode,
1023 depth))
1024 return 0;
1025 break;
1026
1027 case 'S':
1028 case 's':
1029 if (strcmp (XSTR (x, i), XSTR (y, i)))
1030 return 0;
1031 break;
1032
1033 case 'u':
1034 /* These are just backpointers, so they don't matter. */
1035 break;
1036
1037 case '0':
1038 case 't':
1039 break;
1040
1041 /* It is believed that rtx's at this level will never
1042 contain anything but integers and other rtx's,
1043 except for within LABEL_REFs and SYMBOL_REFs. */
1044 default:
1045 gcc_unreachable ();
1046 }
1047 }
1048 return 1;
1049 }
1050
1051 /* Hash an rtx. Return 0 if we couldn't hash the rtx.
1052 For registers and memory locations, we look up their cselib_val structure
1053 and return its VALUE element.
1054 Possible reasons for return 0 are: the object is volatile, or we couldn't
1055 find a register or memory location in the table and CREATE is zero. If
1056 CREATE is nonzero, table elts are created for regs and mem.
1057 N.B. this hash function returns the same hash value for RTXes that
1058 differ only in the order of operands, thus it is suitable for comparisons
1059 that take commutativity into account.
1060 If we wanted to also support associative rules, we'd have to use a different
1061 strategy to avoid returning spurious 0, e.g. return ~(~0U >> 1) .
1062 MEMMODE indicates the mode of an enclosing MEM, and it's only
1063 used to compute autoinc values.
1064 We used to have a MODE argument for hashing for CONST_INTs, but that
1065 didn't make sense, since it caused spurious hash differences between
1066 (set (reg:SI 1) (const_int))
1067 (plus:SI (reg:SI 2) (reg:SI 1))
1068 and
1069 (plus:SI (reg:SI 2) (const_int))
1070 If the mode is important in any context, it must be checked specifically
1071 in a comparison anyway, since relying on hash differences is unsafe. */
1072
1073 static unsigned int
cselib_hash_rtx(rtx x,int create,machine_mode memmode)1074 cselib_hash_rtx (rtx x, int create, machine_mode memmode)
1075 {
1076 cselib_val *e;
1077 poly_int64 offset;
1078 int i, j;
1079 enum rtx_code code;
1080 const char *fmt;
1081 unsigned int hash = 0;
1082
1083 code = GET_CODE (x);
1084 hash += (unsigned) code + (unsigned) GET_MODE (x);
1085
1086 switch (code)
1087 {
1088 case VALUE:
1089 e = CSELIB_VAL_PTR (x);
1090 return e->hash;
1091
1092 case MEM:
1093 case REG:
1094 e = cselib_lookup (x, GET_MODE (x), create, memmode);
1095 if (! e)
1096 return 0;
1097
1098 return e->hash;
1099
1100 case DEBUG_EXPR:
1101 hash += ((unsigned) DEBUG_EXPR << 7)
1102 + DEBUG_TEMP_UID (DEBUG_EXPR_TREE_DECL (x));
1103 return hash ? hash : (unsigned int) DEBUG_EXPR;
1104
1105 case DEBUG_IMPLICIT_PTR:
1106 hash += ((unsigned) DEBUG_IMPLICIT_PTR << 7)
1107 + DECL_UID (DEBUG_IMPLICIT_PTR_DECL (x));
1108 return hash ? hash : (unsigned int) DEBUG_IMPLICIT_PTR;
1109
1110 case DEBUG_PARAMETER_REF:
1111 hash += ((unsigned) DEBUG_PARAMETER_REF << 7)
1112 + DECL_UID (DEBUG_PARAMETER_REF_DECL (x));
1113 return hash ? hash : (unsigned int) DEBUG_PARAMETER_REF;
1114
1115 case ENTRY_VALUE:
1116 /* ENTRY_VALUEs are function invariant, thus try to avoid
1117 recursing on argument if ENTRY_VALUE is one of the
1118 forms emitted by expand_debug_expr, otherwise
1119 ENTRY_VALUE hash would depend on the current value
1120 in some register or memory. */
1121 if (REG_P (ENTRY_VALUE_EXP (x)))
1122 hash += (unsigned int) REG
1123 + (unsigned int) GET_MODE (ENTRY_VALUE_EXP (x))
1124 + (unsigned int) REGNO (ENTRY_VALUE_EXP (x));
1125 else if (MEM_P (ENTRY_VALUE_EXP (x))
1126 && REG_P (XEXP (ENTRY_VALUE_EXP (x), 0)))
1127 hash += (unsigned int) MEM
1128 + (unsigned int) GET_MODE (XEXP (ENTRY_VALUE_EXP (x), 0))
1129 + (unsigned int) REGNO (XEXP (ENTRY_VALUE_EXP (x), 0));
1130 else
1131 hash += cselib_hash_rtx (ENTRY_VALUE_EXP (x), create, memmode);
1132 return hash ? hash : (unsigned int) ENTRY_VALUE;
1133
1134 case CONST_INT:
1135 hash += ((unsigned) CONST_INT << 7) + UINTVAL (x);
1136 return hash ? hash : (unsigned int) CONST_INT;
1137
1138 case CONST_WIDE_INT:
1139 for (i = 0; i < CONST_WIDE_INT_NUNITS (x); i++)
1140 hash += CONST_WIDE_INT_ELT (x, i);
1141 return hash;
1142
1143 case CONST_POLY_INT:
1144 {
1145 inchash::hash h;
1146 h.add_int (hash);
1147 for (unsigned int i = 0; i < NUM_POLY_INT_COEFFS; ++i)
1148 h.add_wide_int (CONST_POLY_INT_COEFFS (x)[i]);
1149 return h.end ();
1150 }
1151
1152 case CONST_DOUBLE:
1153 /* This is like the general case, except that it only counts
1154 the integers representing the constant. */
1155 hash += (unsigned) code + (unsigned) GET_MODE (x);
1156 if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
1157 hash += ((unsigned) CONST_DOUBLE_LOW (x)
1158 + (unsigned) CONST_DOUBLE_HIGH (x));
1159 else
1160 hash += real_hash (CONST_DOUBLE_REAL_VALUE (x));
1161 return hash ? hash : (unsigned int) CONST_DOUBLE;
1162
1163 case CONST_FIXED:
1164 hash += (unsigned int) code + (unsigned int) GET_MODE (x);
1165 hash += fixed_hash (CONST_FIXED_VALUE (x));
1166 return hash ? hash : (unsigned int) CONST_FIXED;
1167
1168 case CONST_VECTOR:
1169 {
1170 int units;
1171 rtx elt;
1172
1173 units = const_vector_encoded_nelts (x);
1174
1175 for (i = 0; i < units; ++i)
1176 {
1177 elt = CONST_VECTOR_ENCODED_ELT (x, i);
1178 hash += cselib_hash_rtx (elt, 0, memmode);
1179 }
1180
1181 return hash;
1182 }
1183
1184 /* Assume there is only one rtx object for any given label. */
1185 case LABEL_REF:
1186 /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1187 differences and differences between each stage's debugging dumps. */
1188 hash += (((unsigned int) LABEL_REF << 7)
1189 + CODE_LABEL_NUMBER (label_ref_label (x)));
1190 return hash ? hash : (unsigned int) LABEL_REF;
1191
1192 case SYMBOL_REF:
1193 {
1194 /* Don't hash on the symbol's address to avoid bootstrap differences.
1195 Different hash values may cause expressions to be recorded in
1196 different orders and thus different registers to be used in the
1197 final assembler. This also avoids differences in the dump files
1198 between various stages. */
1199 unsigned int h = 0;
1200 const unsigned char *p = (const unsigned char *) XSTR (x, 0);
1201
1202 while (*p)
1203 h += (h << 7) + *p++; /* ??? revisit */
1204
1205 hash += ((unsigned int) SYMBOL_REF << 7) + h;
1206 return hash ? hash : (unsigned int) SYMBOL_REF;
1207 }
1208
1209 case PRE_DEC:
1210 case PRE_INC:
1211 /* We can't compute these without knowing the MEM mode. */
1212 gcc_assert (memmode != VOIDmode);
1213 offset = GET_MODE_SIZE (memmode);
1214 if (code == PRE_DEC)
1215 offset = -offset;
1216 /* Adjust the hash so that (mem:MEMMODE (pre_* (reg))) hashes
1217 like (mem:MEMMODE (plus (reg) (const_int I))). */
1218 hash += (unsigned) PLUS - (unsigned)code
1219 + cselib_hash_rtx (XEXP (x, 0), create, memmode)
1220 + cselib_hash_rtx (gen_int_mode (offset, GET_MODE (x)),
1221 create, memmode);
1222 return hash ? hash : 1 + (unsigned) PLUS;
1223
1224 case PRE_MODIFY:
1225 gcc_assert (memmode != VOIDmode);
1226 return cselib_hash_rtx (XEXP (x, 1), create, memmode);
1227
1228 case POST_DEC:
1229 case POST_INC:
1230 case POST_MODIFY:
1231 gcc_assert (memmode != VOIDmode);
1232 return cselib_hash_rtx (XEXP (x, 0), create, memmode);
1233
1234 case PC:
1235 case CC0:
1236 case CALL:
1237 case UNSPEC_VOLATILE:
1238 return 0;
1239
1240 case ASM_OPERANDS:
1241 if (MEM_VOLATILE_P (x))
1242 return 0;
1243
1244 break;
1245
1246 default:
1247 break;
1248 }
1249
1250 i = GET_RTX_LENGTH (code) - 1;
1251 fmt = GET_RTX_FORMAT (code);
1252 for (; i >= 0; i--)
1253 {
1254 switch (fmt[i])
1255 {
1256 case 'e':
1257 {
1258 rtx tem = XEXP (x, i);
1259 unsigned int tem_hash = cselib_hash_rtx (tem, create, memmode);
1260
1261 if (tem_hash == 0)
1262 return 0;
1263
1264 hash += tem_hash;
1265 }
1266 break;
1267 case 'E':
1268 for (j = 0; j < XVECLEN (x, i); j++)
1269 {
1270 unsigned int tem_hash
1271 = cselib_hash_rtx (XVECEXP (x, i, j), create, memmode);
1272
1273 if (tem_hash == 0)
1274 return 0;
1275
1276 hash += tem_hash;
1277 }
1278 break;
1279
1280 case 's':
1281 {
1282 const unsigned char *p = (const unsigned char *) XSTR (x, i);
1283
1284 if (p)
1285 while (*p)
1286 hash += *p++;
1287 break;
1288 }
1289
1290 case 'i':
1291 hash += XINT (x, i);
1292 break;
1293
1294 case 'p':
1295 hash += constant_lower_bound (SUBREG_BYTE (x));
1296 break;
1297
1298 case '0':
1299 case 't':
1300 /* unused */
1301 break;
1302
1303 default:
1304 gcc_unreachable ();
1305 }
1306 }
1307
1308 return hash ? hash : 1 + (unsigned int) GET_CODE (x);
1309 }
1310
1311 /* Create a new value structure for VALUE and initialize it. The mode of the
1312 value is MODE. */
1313
1314 static inline cselib_val *
new_cselib_val(unsigned int hash,machine_mode mode,rtx x)1315 new_cselib_val (unsigned int hash, machine_mode mode, rtx x)
1316 {
1317 cselib_val *e = cselib_val_pool.allocate ();
1318
1319 gcc_assert (hash);
1320 gcc_assert (next_uid);
1321
1322 e->hash = hash;
1323 e->uid = next_uid++;
1324 /* We use an alloc pool to allocate this RTL construct because it
1325 accounts for about 8% of the overall memory usage. We know
1326 precisely when we can have VALUE RTXen (when cselib is active)
1327 so we don't need to put them in garbage collected memory.
1328 ??? Why should a VALUE be an RTX in the first place? */
1329 e->val_rtx = (rtx_def*) value_pool.allocate ();
1330 memset (e->val_rtx, 0, RTX_HDR_SIZE);
1331 PUT_CODE (e->val_rtx, VALUE);
1332 PUT_MODE (e->val_rtx, mode);
1333 CSELIB_VAL_PTR (e->val_rtx) = e;
1334 e->addr_list = 0;
1335 e->locs = 0;
1336 e->next_containing_mem = 0;
1337
1338 if (dump_file && (dump_flags & TDF_CSELIB))
1339 {
1340 fprintf (dump_file, "cselib value %u:%u ", e->uid, hash);
1341 if (flag_dump_noaddr || flag_dump_unnumbered)
1342 fputs ("# ", dump_file);
1343 else
1344 fprintf (dump_file, "%p ", (void*)e);
1345 print_rtl_single (dump_file, x);
1346 fputc ('\n', dump_file);
1347 }
1348
1349 return e;
1350 }
1351
1352 /* ADDR_ELT is a value that is used as address. MEM_ELT is the value that
1353 contains the data at this address. X is a MEM that represents the
1354 value. Update the two value structures to represent this situation. */
1355
1356 static void
add_mem_for_addr(cselib_val * addr_elt,cselib_val * mem_elt,rtx x)1357 add_mem_for_addr (cselib_val *addr_elt, cselib_val *mem_elt, rtx x)
1358 {
1359 addr_elt = canonical_cselib_val (addr_elt);
1360 mem_elt = canonical_cselib_val (mem_elt);
1361
1362 /* Avoid duplicates. */
1363 addr_space_t as = MEM_ADDR_SPACE (x);
1364 for (elt_loc_list *l = mem_elt->locs; l; l = l->next)
1365 if (MEM_P (l->loc)
1366 && CSELIB_VAL_PTR (XEXP (l->loc, 0)) == addr_elt
1367 && MEM_ADDR_SPACE (l->loc) == as)
1368 {
1369 promote_debug_loc (l);
1370 return;
1371 }
1372
1373 addr_elt->addr_list = new_elt_list (addr_elt->addr_list, mem_elt);
1374 new_elt_loc_list (mem_elt,
1375 replace_equiv_address_nv (x, addr_elt->val_rtx));
1376 if (mem_elt->next_containing_mem == NULL)
1377 {
1378 mem_elt->next_containing_mem = first_containing_mem;
1379 first_containing_mem = mem_elt;
1380 }
1381 }
1382
1383 /* Subroutine of cselib_lookup. Return a value for X, which is a MEM rtx.
1384 If CREATE, make a new one if we haven't seen it before. */
1385
1386 static cselib_val *
cselib_lookup_mem(rtx x,int create)1387 cselib_lookup_mem (rtx x, int create)
1388 {
1389 machine_mode mode = GET_MODE (x);
1390 machine_mode addr_mode;
1391 cselib_val **slot;
1392 cselib_val *addr;
1393 cselib_val *mem_elt;
1394
1395 if (MEM_VOLATILE_P (x) || mode == BLKmode
1396 || !cselib_record_memory
1397 || (FLOAT_MODE_P (mode) && flag_float_store))
1398 return 0;
1399
1400 addr_mode = GET_MODE (XEXP (x, 0));
1401 if (addr_mode == VOIDmode)
1402 addr_mode = Pmode;
1403
1404 /* Look up the value for the address. */
1405 addr = cselib_lookup (XEXP (x, 0), addr_mode, create, mode);
1406 if (! addr)
1407 return 0;
1408 addr = canonical_cselib_val (addr);
1409
1410 /* Find a value that describes a value of our mode at that address. */
1411 addr_space_t as = MEM_ADDR_SPACE (x);
1412 for (elt_list *l = addr->addr_list; l; l = l->next)
1413 if (GET_MODE (l->elt->val_rtx) == mode)
1414 {
1415 for (elt_loc_list *l2 = l->elt->locs; l2; l2 = l2->next)
1416 if (MEM_P (l2->loc) && MEM_ADDR_SPACE (l2->loc) == as)
1417 {
1418 promote_debug_loc (l->elt->locs);
1419 return l->elt;
1420 }
1421 }
1422
1423 if (! create)
1424 return 0;
1425
1426 mem_elt = new_cselib_val (next_uid, mode, x);
1427 add_mem_for_addr (addr, mem_elt, x);
1428 slot = cselib_find_slot (mode, x, mem_elt->hash, INSERT, VOIDmode);
1429 *slot = mem_elt;
1430 return mem_elt;
1431 }
1432
1433 /* Search through the possible substitutions in P. We prefer a non reg
1434 substitution because this allows us to expand the tree further. If
1435 we find, just a reg, take the lowest regno. There may be several
1436 non-reg results, we just take the first one because they will all
1437 expand to the same place. */
1438
1439 static rtx
expand_loc(struct elt_loc_list * p,struct expand_value_data * evd,int max_depth)1440 expand_loc (struct elt_loc_list *p, struct expand_value_data *evd,
1441 int max_depth)
1442 {
1443 rtx reg_result = NULL;
1444 unsigned int regno = UINT_MAX;
1445 struct elt_loc_list *p_in = p;
1446
1447 for (; p; p = p->next)
1448 {
1449 /* Return these right away to avoid returning stack pointer based
1450 expressions for frame pointer and vice versa, which is something
1451 that would confuse DSE. See the comment in cselib_expand_value_rtx_1
1452 for more details. */
1453 if (REG_P (p->loc)
1454 && (REGNO (p->loc) == STACK_POINTER_REGNUM
1455 || REGNO (p->loc) == FRAME_POINTER_REGNUM
1456 || REGNO (p->loc) == HARD_FRAME_POINTER_REGNUM
1457 || REGNO (p->loc) == cfa_base_preserved_regno))
1458 return p->loc;
1459 /* Avoid infinite recursion trying to expand a reg into a
1460 the same reg. */
1461 if ((REG_P (p->loc))
1462 && (REGNO (p->loc) < regno)
1463 && !bitmap_bit_p (evd->regs_active, REGNO (p->loc)))
1464 {
1465 reg_result = p->loc;
1466 regno = REGNO (p->loc);
1467 }
1468 /* Avoid infinite recursion and do not try to expand the
1469 value. */
1470 else if (GET_CODE (p->loc) == VALUE
1471 && CSELIB_VAL_PTR (p->loc)->locs == p_in)
1472 continue;
1473 else if (!REG_P (p->loc))
1474 {
1475 rtx result, note;
1476 if (dump_file && (dump_flags & TDF_CSELIB))
1477 {
1478 print_inline_rtx (dump_file, p->loc, 0);
1479 fprintf (dump_file, "\n");
1480 }
1481 if (GET_CODE (p->loc) == LO_SUM
1482 && GET_CODE (XEXP (p->loc, 1)) == SYMBOL_REF
1483 && p->setting_insn
1484 && (note = find_reg_note (p->setting_insn, REG_EQUAL, NULL_RTX))
1485 && XEXP (note, 0) == XEXP (p->loc, 1))
1486 return XEXP (p->loc, 1);
1487 result = cselib_expand_value_rtx_1 (p->loc, evd, max_depth - 1);
1488 if (result)
1489 return result;
1490 }
1491
1492 }
1493
1494 if (regno != UINT_MAX)
1495 {
1496 rtx result;
1497 if (dump_file && (dump_flags & TDF_CSELIB))
1498 fprintf (dump_file, "r%d\n", regno);
1499
1500 result = cselib_expand_value_rtx_1 (reg_result, evd, max_depth - 1);
1501 if (result)
1502 return result;
1503 }
1504
1505 if (dump_file && (dump_flags & TDF_CSELIB))
1506 {
1507 if (reg_result)
1508 {
1509 print_inline_rtx (dump_file, reg_result, 0);
1510 fprintf (dump_file, "\n");
1511 }
1512 else
1513 fprintf (dump_file, "NULL\n");
1514 }
1515 return reg_result;
1516 }
1517
1518
1519 /* Forward substitute and expand an expression out to its roots.
1520 This is the opposite of common subexpression. Because local value
1521 numbering is such a weak optimization, the expanded expression is
1522 pretty much unique (not from a pointer equals point of view but
1523 from a tree shape point of view.
1524
1525 This function returns NULL if the expansion fails. The expansion
1526 will fail if there is no value number for one of the operands or if
1527 one of the operands has been overwritten between the current insn
1528 and the beginning of the basic block. For instance x has no
1529 expansion in:
1530
1531 r1 <- r1 + 3
1532 x <- r1 + 8
1533
1534 REGS_ACTIVE is a scratch bitmap that should be clear when passing in.
1535 It is clear on return. */
1536
1537 rtx
cselib_expand_value_rtx(rtx orig,bitmap regs_active,int max_depth)1538 cselib_expand_value_rtx (rtx orig, bitmap regs_active, int max_depth)
1539 {
1540 struct expand_value_data evd;
1541
1542 evd.regs_active = regs_active;
1543 evd.callback = NULL;
1544 evd.callback_arg = NULL;
1545 evd.dummy = false;
1546
1547 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1548 }
1549
1550 /* Same as cselib_expand_value_rtx, but using a callback to try to
1551 resolve some expressions. The CB function should return ORIG if it
1552 can't or does not want to deal with a certain RTX. Any other
1553 return value, including NULL, will be used as the expansion for
1554 VALUE, without any further changes. */
1555
1556 rtx
cselib_expand_value_rtx_cb(rtx orig,bitmap regs_active,int max_depth,cselib_expand_callback cb,void * data)1557 cselib_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1558 cselib_expand_callback cb, void *data)
1559 {
1560 struct expand_value_data evd;
1561
1562 evd.regs_active = regs_active;
1563 evd.callback = cb;
1564 evd.callback_arg = data;
1565 evd.dummy = false;
1566
1567 return cselib_expand_value_rtx_1 (orig, &evd, max_depth);
1568 }
1569
1570 /* Similar to cselib_expand_value_rtx_cb, but no rtxs are actually copied
1571 or simplified. Useful to find out whether cselib_expand_value_rtx_cb
1572 would return NULL or non-NULL, without allocating new rtx. */
1573
1574 bool
cselib_dummy_expand_value_rtx_cb(rtx orig,bitmap regs_active,int max_depth,cselib_expand_callback cb,void * data)1575 cselib_dummy_expand_value_rtx_cb (rtx orig, bitmap regs_active, int max_depth,
1576 cselib_expand_callback cb, void *data)
1577 {
1578 struct expand_value_data evd;
1579
1580 evd.regs_active = regs_active;
1581 evd.callback = cb;
1582 evd.callback_arg = data;
1583 evd.dummy = true;
1584
1585 return cselib_expand_value_rtx_1 (orig, &evd, max_depth) != NULL;
1586 }
1587
1588 /* Internal implementation of cselib_expand_value_rtx and
1589 cselib_expand_value_rtx_cb. */
1590
1591 static rtx
cselib_expand_value_rtx_1(rtx orig,struct expand_value_data * evd,int max_depth)1592 cselib_expand_value_rtx_1 (rtx orig, struct expand_value_data *evd,
1593 int max_depth)
1594 {
1595 rtx copy, scopy;
1596 int i, j;
1597 RTX_CODE code;
1598 const char *format_ptr;
1599 machine_mode mode;
1600
1601 code = GET_CODE (orig);
1602
1603 /* For the context of dse, if we end up expand into a huge tree, we
1604 will not have a useful address, so we might as well just give up
1605 quickly. */
1606 if (max_depth <= 0)
1607 return NULL;
1608
1609 switch (code)
1610 {
1611 case REG:
1612 {
1613 struct elt_list *l = REG_VALUES (REGNO (orig));
1614
1615 if (l && l->elt == NULL)
1616 l = l->next;
1617 for (; l; l = l->next)
1618 if (GET_MODE (l->elt->val_rtx) == GET_MODE (orig))
1619 {
1620 rtx result;
1621 unsigned regno = REGNO (orig);
1622
1623 /* The only thing that we are not willing to do (this
1624 is requirement of dse and if others potential uses
1625 need this function we should add a parm to control
1626 it) is that we will not substitute the
1627 STACK_POINTER_REGNUM, FRAME_POINTER or the
1628 HARD_FRAME_POINTER.
1629
1630 These expansions confuses the code that notices that
1631 stores into the frame go dead at the end of the
1632 function and that the frame is not effected by calls
1633 to subroutines. If you allow the
1634 STACK_POINTER_REGNUM substitution, then dse will
1635 think that parameter pushing also goes dead which is
1636 wrong. If you allow the FRAME_POINTER or the
1637 HARD_FRAME_POINTER then you lose the opportunity to
1638 make the frame assumptions. */
1639 if (regno == STACK_POINTER_REGNUM
1640 || regno == FRAME_POINTER_REGNUM
1641 || regno == HARD_FRAME_POINTER_REGNUM
1642 || regno == cfa_base_preserved_regno)
1643 return orig;
1644
1645 bitmap_set_bit (evd->regs_active, regno);
1646
1647 if (dump_file && (dump_flags & TDF_CSELIB))
1648 fprintf (dump_file, "expanding: r%d into: ", regno);
1649
1650 result = expand_loc (l->elt->locs, evd, max_depth);
1651 bitmap_clear_bit (evd->regs_active, regno);
1652
1653 if (result)
1654 return result;
1655 else
1656 return orig;
1657 }
1658 return orig;
1659 }
1660
1661 CASE_CONST_ANY:
1662 case SYMBOL_REF:
1663 case CODE_LABEL:
1664 case PC:
1665 case CC0:
1666 case SCRATCH:
1667 /* SCRATCH must be shared because they represent distinct values. */
1668 return orig;
1669 case CLOBBER:
1670 case CLOBBER_HIGH:
1671 if (REG_P (XEXP (orig, 0)) && HARD_REGISTER_NUM_P (REGNO (XEXP (orig, 0))))
1672 return orig;
1673 break;
1674
1675 case CONST:
1676 if (shared_const_p (orig))
1677 return orig;
1678 break;
1679
1680 case SUBREG:
1681 {
1682 rtx subreg;
1683
1684 if (evd->callback)
1685 {
1686 subreg = evd->callback (orig, evd->regs_active, max_depth,
1687 evd->callback_arg);
1688 if (subreg != orig)
1689 return subreg;
1690 }
1691
1692 subreg = cselib_expand_value_rtx_1 (SUBREG_REG (orig), evd,
1693 max_depth - 1);
1694 if (!subreg)
1695 return NULL;
1696 scopy = simplify_gen_subreg (GET_MODE (orig), subreg,
1697 GET_MODE (SUBREG_REG (orig)),
1698 SUBREG_BYTE (orig));
1699 if (scopy == NULL
1700 || (GET_CODE (scopy) == SUBREG
1701 && !REG_P (SUBREG_REG (scopy))
1702 && !MEM_P (SUBREG_REG (scopy))))
1703 return NULL;
1704
1705 return scopy;
1706 }
1707
1708 case VALUE:
1709 {
1710 rtx result;
1711
1712 if (dump_file && (dump_flags & TDF_CSELIB))
1713 {
1714 fputs ("\nexpanding ", dump_file);
1715 print_rtl_single (dump_file, orig);
1716 fputs (" into...", dump_file);
1717 }
1718
1719 if (evd->callback)
1720 {
1721 result = evd->callback (orig, evd->regs_active, max_depth,
1722 evd->callback_arg);
1723
1724 if (result != orig)
1725 return result;
1726 }
1727
1728 result = expand_loc (CSELIB_VAL_PTR (orig)->locs, evd, max_depth);
1729 return result;
1730 }
1731
1732 case DEBUG_EXPR:
1733 if (evd->callback)
1734 return evd->callback (orig, evd->regs_active, max_depth,
1735 evd->callback_arg);
1736 return orig;
1737
1738 default:
1739 break;
1740 }
1741
1742 /* Copy the various flags, fields, and other information. We assume
1743 that all fields need copying, and then clear the fields that should
1744 not be copied. That is the sensible default behavior, and forces
1745 us to explicitly document why we are *not* copying a flag. */
1746 if (evd->dummy)
1747 copy = NULL;
1748 else
1749 copy = shallow_copy_rtx (orig);
1750
1751 format_ptr = GET_RTX_FORMAT (code);
1752
1753 for (i = 0; i < GET_RTX_LENGTH (code); i++)
1754 switch (*format_ptr++)
1755 {
1756 case 'e':
1757 if (XEXP (orig, i) != NULL)
1758 {
1759 rtx result = cselib_expand_value_rtx_1 (XEXP (orig, i), evd,
1760 max_depth - 1);
1761 if (!result)
1762 return NULL;
1763 if (copy)
1764 XEXP (copy, i) = result;
1765 }
1766 break;
1767
1768 case 'E':
1769 case 'V':
1770 if (XVEC (orig, i) != NULL)
1771 {
1772 if (copy)
1773 XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
1774 for (j = 0; j < XVECLEN (orig, i); j++)
1775 {
1776 rtx result = cselib_expand_value_rtx_1 (XVECEXP (orig, i, j),
1777 evd, max_depth - 1);
1778 if (!result)
1779 return NULL;
1780 if (copy)
1781 XVECEXP (copy, i, j) = result;
1782 }
1783 }
1784 break;
1785
1786 case 't':
1787 case 'w':
1788 case 'i':
1789 case 's':
1790 case 'S':
1791 case 'T':
1792 case 'u':
1793 case 'B':
1794 case '0':
1795 /* These are left unchanged. */
1796 break;
1797
1798 default:
1799 gcc_unreachable ();
1800 }
1801
1802 if (evd->dummy)
1803 return orig;
1804
1805 mode = GET_MODE (copy);
1806 /* If an operand has been simplified into CONST_INT, which doesn't
1807 have a mode and the mode isn't derivable from whole rtx's mode,
1808 try simplify_*_operation first with mode from original's operand
1809 and as a fallback wrap CONST_INT into gen_rtx_CONST. */
1810 scopy = copy;
1811 switch (GET_RTX_CLASS (code))
1812 {
1813 case RTX_UNARY:
1814 if (CONST_INT_P (XEXP (copy, 0))
1815 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1816 {
1817 scopy = simplify_unary_operation (code, mode, XEXP (copy, 0),
1818 GET_MODE (XEXP (orig, 0)));
1819 if (scopy)
1820 return scopy;
1821 }
1822 break;
1823 case RTX_COMM_ARITH:
1824 case RTX_BIN_ARITH:
1825 /* These expressions can derive operand modes from the whole rtx's mode. */
1826 break;
1827 case RTX_TERNARY:
1828 case RTX_BITFIELD_OPS:
1829 if (CONST_INT_P (XEXP (copy, 0))
1830 && GET_MODE (XEXP (orig, 0)) != VOIDmode)
1831 {
1832 scopy = simplify_ternary_operation (code, mode,
1833 GET_MODE (XEXP (orig, 0)),
1834 XEXP (copy, 0), XEXP (copy, 1),
1835 XEXP (copy, 2));
1836 if (scopy)
1837 return scopy;
1838 }
1839 break;
1840 case RTX_COMPARE:
1841 case RTX_COMM_COMPARE:
1842 if (CONST_INT_P (XEXP (copy, 0))
1843 && GET_MODE (XEXP (copy, 1)) == VOIDmode
1844 && (GET_MODE (XEXP (orig, 0)) != VOIDmode
1845 || GET_MODE (XEXP (orig, 1)) != VOIDmode))
1846 {
1847 scopy = simplify_relational_operation (code, mode,
1848 (GET_MODE (XEXP (orig, 0))
1849 != VOIDmode)
1850 ? GET_MODE (XEXP (orig, 0))
1851 : GET_MODE (XEXP (orig, 1)),
1852 XEXP (copy, 0),
1853 XEXP (copy, 1));
1854 if (scopy)
1855 return scopy;
1856 }
1857 break;
1858 default:
1859 break;
1860 }
1861 scopy = simplify_rtx (copy);
1862 if (scopy)
1863 return scopy;
1864 return copy;
1865 }
1866
1867 /* Walk rtx X and replace all occurrences of REG and MEM subexpressions
1868 with VALUE expressions. This way, it becomes independent of changes
1869 to registers and memory.
1870 X isn't actually modified; if modifications are needed, new rtl is
1871 allocated. However, the return value can share rtl with X.
1872 If X is within a MEM, MEMMODE must be the mode of the MEM. */
1873
1874 rtx
cselib_subst_to_values(rtx x,machine_mode memmode)1875 cselib_subst_to_values (rtx x, machine_mode memmode)
1876 {
1877 enum rtx_code code = GET_CODE (x);
1878 const char *fmt = GET_RTX_FORMAT (code);
1879 cselib_val *e;
1880 struct elt_list *l;
1881 rtx copy = x;
1882 int i;
1883 poly_int64 offset;
1884
1885 switch (code)
1886 {
1887 case REG:
1888 l = REG_VALUES (REGNO (x));
1889 if (l && l->elt == NULL)
1890 l = l->next;
1891 for (; l; l = l->next)
1892 if (GET_MODE (l->elt->val_rtx) == GET_MODE (x))
1893 return l->elt->val_rtx;
1894
1895 gcc_unreachable ();
1896
1897 case MEM:
1898 e = cselib_lookup_mem (x, 0);
1899 /* This used to happen for autoincrements, but we deal with them
1900 properly now. Remove the if stmt for the next release. */
1901 if (! e)
1902 {
1903 /* Assign a value that doesn't match any other. */
1904 e = new_cselib_val (next_uid, GET_MODE (x), x);
1905 }
1906 return e->val_rtx;
1907
1908 case ENTRY_VALUE:
1909 e = cselib_lookup (x, GET_MODE (x), 0, memmode);
1910 if (! e)
1911 break;
1912 return e->val_rtx;
1913
1914 CASE_CONST_ANY:
1915 return x;
1916
1917 case PRE_DEC:
1918 case PRE_INC:
1919 gcc_assert (memmode != VOIDmode);
1920 offset = GET_MODE_SIZE (memmode);
1921 if (code == PRE_DEC)
1922 offset = -offset;
1923 return cselib_subst_to_values (plus_constant (GET_MODE (x),
1924 XEXP (x, 0), offset),
1925 memmode);
1926
1927 case PRE_MODIFY:
1928 gcc_assert (memmode != VOIDmode);
1929 return cselib_subst_to_values (XEXP (x, 1), memmode);
1930
1931 case POST_DEC:
1932 case POST_INC:
1933 case POST_MODIFY:
1934 gcc_assert (memmode != VOIDmode);
1935 return cselib_subst_to_values (XEXP (x, 0), memmode);
1936
1937 default:
1938 break;
1939 }
1940
1941 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1942 {
1943 if (fmt[i] == 'e')
1944 {
1945 rtx t = cselib_subst_to_values (XEXP (x, i), memmode);
1946
1947 if (t != XEXP (x, i))
1948 {
1949 if (x == copy)
1950 copy = shallow_copy_rtx (x);
1951 XEXP (copy, i) = t;
1952 }
1953 }
1954 else if (fmt[i] == 'E')
1955 {
1956 int j;
1957
1958 for (j = 0; j < XVECLEN (x, i); j++)
1959 {
1960 rtx t = cselib_subst_to_values (XVECEXP (x, i, j), memmode);
1961
1962 if (t != XVECEXP (x, i, j))
1963 {
1964 if (XVEC (x, i) == XVEC (copy, i))
1965 {
1966 if (x == copy)
1967 copy = shallow_copy_rtx (x);
1968 XVEC (copy, i) = shallow_copy_rtvec (XVEC (x, i));
1969 }
1970 XVECEXP (copy, i, j) = t;
1971 }
1972 }
1973 }
1974 }
1975
1976 return copy;
1977 }
1978
1979 /* Wrapper for cselib_subst_to_values, that indicates X is in INSN. */
1980
1981 rtx
cselib_subst_to_values_from_insn(rtx x,machine_mode memmode,rtx_insn * insn)1982 cselib_subst_to_values_from_insn (rtx x, machine_mode memmode, rtx_insn *insn)
1983 {
1984 rtx ret;
1985 gcc_assert (!cselib_current_insn);
1986 cselib_current_insn = insn;
1987 ret = cselib_subst_to_values (x, memmode);
1988 cselib_current_insn = NULL;
1989 return ret;
1990 }
1991
1992 /* Look up the rtl expression X in our tables and return the value it
1993 has. If CREATE is zero, we return NULL if we don't know the value.
1994 Otherwise, we create a new one if possible, using mode MODE if X
1995 doesn't have a mode (i.e. because it's a constant). When X is part
1996 of an address, MEMMODE should be the mode of the enclosing MEM if
1997 we're tracking autoinc expressions. */
1998
1999 static cselib_val *
cselib_lookup_1(rtx x,machine_mode mode,int create,machine_mode memmode)2000 cselib_lookup_1 (rtx x, machine_mode mode,
2001 int create, machine_mode memmode)
2002 {
2003 cselib_val **slot;
2004 cselib_val *e;
2005 unsigned int hashval;
2006
2007 if (GET_MODE (x) != VOIDmode)
2008 mode = GET_MODE (x);
2009
2010 if (GET_CODE (x) == VALUE)
2011 return CSELIB_VAL_PTR (x);
2012
2013 if (REG_P (x))
2014 {
2015 struct elt_list *l;
2016 unsigned int i = REGNO (x);
2017
2018 l = REG_VALUES (i);
2019 if (l && l->elt == NULL)
2020 l = l->next;
2021 for (; l; l = l->next)
2022 if (mode == GET_MODE (l->elt->val_rtx))
2023 {
2024 promote_debug_loc (l->elt->locs);
2025 return l->elt;
2026 }
2027
2028 if (! create)
2029 return 0;
2030
2031 if (i < FIRST_PSEUDO_REGISTER)
2032 {
2033 unsigned int n = hard_regno_nregs (i, mode);
2034
2035 if (n > max_value_regs)
2036 max_value_regs = n;
2037 }
2038
2039 e = new_cselib_val (next_uid, GET_MODE (x), x);
2040 new_elt_loc_list (e, x);
2041
2042 scalar_int_mode int_mode;
2043 if (REG_VALUES (i) == 0)
2044 {
2045 /* Maintain the invariant that the first entry of
2046 REG_VALUES, if present, must be the value used to set the
2047 register, or NULL. */
2048 used_regs[n_used_regs++] = i;
2049 REG_VALUES (i) = new_elt_list (REG_VALUES (i), NULL);
2050 }
2051 else if (cselib_preserve_constants
2052 && is_int_mode (mode, &int_mode))
2053 {
2054 /* During var-tracking, try harder to find equivalences
2055 for SUBREGs. If a setter sets say a DImode register
2056 and user uses that register only in SImode, add a lowpart
2057 subreg location. */
2058 struct elt_list *lwider = NULL;
2059 scalar_int_mode lmode;
2060 l = REG_VALUES (i);
2061 if (l && l->elt == NULL)
2062 l = l->next;
2063 for (; l; l = l->next)
2064 if (is_int_mode (GET_MODE (l->elt->val_rtx), &lmode)
2065 && GET_MODE_SIZE (lmode) > GET_MODE_SIZE (int_mode)
2066 && (lwider == NULL
2067 || partial_subreg_p (lmode,
2068 GET_MODE (lwider->elt->val_rtx))))
2069 {
2070 struct elt_loc_list *el;
2071 if (i < FIRST_PSEUDO_REGISTER
2072 && hard_regno_nregs (i, lmode) != 1)
2073 continue;
2074 for (el = l->elt->locs; el; el = el->next)
2075 if (!REG_P (el->loc))
2076 break;
2077 if (el)
2078 lwider = l;
2079 }
2080 if (lwider)
2081 {
2082 rtx sub = lowpart_subreg (int_mode, lwider->elt->val_rtx,
2083 GET_MODE (lwider->elt->val_rtx));
2084 if (sub)
2085 new_elt_loc_list (e, sub);
2086 }
2087 }
2088 REG_VALUES (i)->next = new_elt_list (REG_VALUES (i)->next, e);
2089 slot = cselib_find_slot (mode, x, e->hash, INSERT, memmode);
2090 *slot = e;
2091 return e;
2092 }
2093
2094 if (MEM_P (x))
2095 return cselib_lookup_mem (x, create);
2096
2097 hashval = cselib_hash_rtx (x, create, memmode);
2098 /* Can't even create if hashing is not possible. */
2099 if (! hashval)
2100 return 0;
2101
2102 slot = cselib_find_slot (mode, x, hashval,
2103 create ? INSERT : NO_INSERT, memmode);
2104 if (slot == 0)
2105 return 0;
2106
2107 e = (cselib_val *) *slot;
2108 if (e)
2109 return e;
2110
2111 e = new_cselib_val (hashval, mode, x);
2112
2113 /* We have to fill the slot before calling cselib_subst_to_values:
2114 the hash table is inconsistent until we do so, and
2115 cselib_subst_to_values will need to do lookups. */
2116 *slot = e;
2117 new_elt_loc_list (e, cselib_subst_to_values (x, memmode));
2118 return e;
2119 }
2120
2121 /* Wrapper for cselib_lookup, that indicates X is in INSN. */
2122
2123 cselib_val *
cselib_lookup_from_insn(rtx x,machine_mode mode,int create,machine_mode memmode,rtx_insn * insn)2124 cselib_lookup_from_insn (rtx x, machine_mode mode,
2125 int create, machine_mode memmode, rtx_insn *insn)
2126 {
2127 cselib_val *ret;
2128
2129 gcc_assert (!cselib_current_insn);
2130 cselib_current_insn = insn;
2131
2132 ret = cselib_lookup (x, mode, create, memmode);
2133
2134 cselib_current_insn = NULL;
2135
2136 return ret;
2137 }
2138
2139 /* Wrapper for cselib_lookup_1, that logs the lookup result and
2140 maintains invariants related with debug insns. */
2141
2142 cselib_val *
cselib_lookup(rtx x,machine_mode mode,int create,machine_mode memmode)2143 cselib_lookup (rtx x, machine_mode mode,
2144 int create, machine_mode memmode)
2145 {
2146 cselib_val *ret = cselib_lookup_1 (x, mode, create, memmode);
2147
2148 /* ??? Should we return NULL if we're not to create an entry, the
2149 found loc is a debug loc and cselib_current_insn is not DEBUG?
2150 If so, we should also avoid converting val to non-DEBUG; probably
2151 easiest setting cselib_current_insn to NULL before the call
2152 above. */
2153
2154 if (dump_file && (dump_flags & TDF_CSELIB))
2155 {
2156 fputs ("cselib lookup ", dump_file);
2157 print_inline_rtx (dump_file, x, 2);
2158 fprintf (dump_file, " => %u:%u\n",
2159 ret ? ret->uid : 0,
2160 ret ? ret->hash : 0);
2161 }
2162
2163 return ret;
2164 }
2165
2166 /* Invalidate any entries in reg_values that overlap REGNO. This is called
2167 if REGNO is changing. MODE is the mode of the assignment to REGNO, which
2168 is used to determine how many hard registers are being changed. If MODE
2169 is VOIDmode, then only REGNO is being changed; this is used when
2170 invalidating call clobbered registers across a call. */
2171
2172 static void
cselib_invalidate_regno(unsigned int regno,machine_mode mode,const_rtx setter)2173 cselib_invalidate_regno (unsigned int regno, machine_mode mode,
2174 const_rtx setter)
2175 {
2176 unsigned int endregno;
2177 unsigned int i;
2178
2179 /* If we see pseudos after reload, something is _wrong_. */
2180 gcc_assert (!reload_completed || regno < FIRST_PSEUDO_REGISTER
2181 || reg_renumber[regno] < 0);
2182
2183 /* Determine the range of registers that must be invalidated. For
2184 pseudos, only REGNO is affected. For hard regs, we must take MODE
2185 into account, and we must also invalidate lower register numbers
2186 if they contain values that overlap REGNO. */
2187 if (regno < FIRST_PSEUDO_REGISTER)
2188 {
2189 gcc_assert (mode != VOIDmode);
2190
2191 if (regno < max_value_regs)
2192 i = 0;
2193 else
2194 i = regno - max_value_regs;
2195
2196 endregno = end_hard_regno (mode, regno);
2197
2198 if (setter && GET_CODE (setter) == CLOBBER_HIGH)
2199 gcc_assert (endregno == regno + 1);
2200 }
2201 else
2202 {
2203 i = regno;
2204 endregno = regno + 1;
2205 }
2206
2207 for (; i < endregno; i++)
2208 {
2209 struct elt_list **l = ®_VALUES (i);
2210
2211 /* Go through all known values for this reg; if it overlaps the range
2212 we're invalidating, remove the value. */
2213 while (*l)
2214 {
2215 cselib_val *v = (*l)->elt;
2216 bool had_locs;
2217 rtx_insn *setting_insn;
2218 struct elt_loc_list **p;
2219 unsigned int this_last = i;
2220
2221 if (i < FIRST_PSEUDO_REGISTER && v != NULL)
2222 this_last = end_hard_regno (GET_MODE (v->val_rtx), i) - 1;
2223
2224 if (this_last < regno || v == NULL
2225 || (v == cfa_base_preserved_val
2226 && i == cfa_base_preserved_regno))
2227 {
2228 l = &(*l)->next;
2229 continue;
2230 }
2231
2232 /* Ignore if clobber high and the register isn't clobbered. */
2233 if (setter && GET_CODE (setter) == CLOBBER_HIGH)
2234 {
2235 gcc_assert (endregno == regno + 1);
2236 const_rtx x = XEXP (setter, 0);
2237 if (!reg_is_clobbered_by_clobber_high (i, GET_MODE (v->val_rtx),
2238 x))
2239 {
2240 l = &(*l)->next;
2241 continue;
2242 }
2243 }
2244
2245 /* We have an overlap. */
2246 if (*l == REG_VALUES (i))
2247 {
2248 /* Maintain the invariant that the first entry of
2249 REG_VALUES, if present, must be the value used to set
2250 the register, or NULL. This is also nice because
2251 then we won't push the same regno onto user_regs
2252 multiple times. */
2253 (*l)->elt = NULL;
2254 l = &(*l)->next;
2255 }
2256 else
2257 unchain_one_elt_list (l);
2258
2259 v = canonical_cselib_val (v);
2260
2261 had_locs = v->locs != NULL;
2262 setting_insn = v->locs ? v->locs->setting_insn : NULL;
2263
2264 /* Now, we clear the mapping from value to reg. It must exist, so
2265 this code will crash intentionally if it doesn't. */
2266 for (p = &v->locs; ; p = &(*p)->next)
2267 {
2268 rtx x = (*p)->loc;
2269
2270 if (REG_P (x) && REGNO (x) == i)
2271 {
2272 unchain_one_elt_loc_list (p);
2273 break;
2274 }
2275 }
2276
2277 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
2278 {
2279 if (setting_insn && DEBUG_INSN_P (setting_insn))
2280 n_useless_debug_values++;
2281 else
2282 n_useless_values++;
2283 }
2284 }
2285 }
2286 }
2287
2288 /* Invalidate any locations in the table which are changed because of a
2289 store to MEM_RTX. If this is called because of a non-const call
2290 instruction, MEM_RTX is (mem:BLK const0_rtx). */
2291
2292 static void
cselib_invalidate_mem(rtx mem_rtx)2293 cselib_invalidate_mem (rtx mem_rtx)
2294 {
2295 cselib_val **vp, *v, *next;
2296 int num_mems = 0;
2297 rtx mem_addr;
2298
2299 mem_addr = canon_rtx (get_addr (XEXP (mem_rtx, 0)));
2300 mem_rtx = canon_rtx (mem_rtx);
2301
2302 vp = &first_containing_mem;
2303 for (v = *vp; v != &dummy_val; v = next)
2304 {
2305 bool has_mem = false;
2306 struct elt_loc_list **p = &v->locs;
2307 bool had_locs = v->locs != NULL;
2308 rtx_insn *setting_insn = v->locs ? v->locs->setting_insn : NULL;
2309
2310 while (*p)
2311 {
2312 rtx x = (*p)->loc;
2313 cselib_val *addr;
2314 struct elt_list **mem_chain;
2315
2316 /* MEMs may occur in locations only at the top level; below
2317 that every MEM or REG is substituted by its VALUE. */
2318 if (!MEM_P (x))
2319 {
2320 p = &(*p)->next;
2321 continue;
2322 }
2323 if (num_mems < PARAM_VALUE (PARAM_MAX_CSELIB_MEMORY_LOCATIONS)
2324 && ! canon_anti_dependence (x, false, mem_rtx,
2325 GET_MODE (mem_rtx), mem_addr))
2326 {
2327 has_mem = true;
2328 num_mems++;
2329 p = &(*p)->next;
2330 continue;
2331 }
2332
2333 /* This one overlaps. */
2334 /* We must have a mapping from this MEM's address to the
2335 value (E). Remove that, too. */
2336 addr = cselib_lookup (XEXP (x, 0), VOIDmode, 0, GET_MODE (x));
2337 addr = canonical_cselib_val (addr);
2338 gcc_checking_assert (v == canonical_cselib_val (v));
2339 mem_chain = &addr->addr_list;
2340 for (;;)
2341 {
2342 cselib_val *canon = canonical_cselib_val ((*mem_chain)->elt);
2343
2344 if (canon == v)
2345 {
2346 unchain_one_elt_list (mem_chain);
2347 break;
2348 }
2349
2350 /* Record canonicalized elt. */
2351 (*mem_chain)->elt = canon;
2352
2353 mem_chain = &(*mem_chain)->next;
2354 }
2355
2356 unchain_one_elt_loc_list (p);
2357 }
2358
2359 if (had_locs && v->locs == 0 && !PRESERVED_VALUE_P (v->val_rtx))
2360 {
2361 if (setting_insn && DEBUG_INSN_P (setting_insn))
2362 n_useless_debug_values++;
2363 else
2364 n_useless_values++;
2365 }
2366
2367 next = v->next_containing_mem;
2368 if (has_mem)
2369 {
2370 *vp = v;
2371 vp = &(*vp)->next_containing_mem;
2372 }
2373 else
2374 v->next_containing_mem = NULL;
2375 }
2376 *vp = &dummy_val;
2377 }
2378
2379 /* Invalidate DEST, which is being assigned to or clobbered by SETTER. */
2380
2381 void
cselib_invalidate_rtx(rtx dest,const_rtx setter)2382 cselib_invalidate_rtx (rtx dest, const_rtx setter)
2383 {
2384 while (GET_CODE (dest) == SUBREG
2385 || GET_CODE (dest) == ZERO_EXTRACT
2386 || GET_CODE (dest) == STRICT_LOW_PART)
2387 dest = XEXP (dest, 0);
2388
2389 if (REG_P (dest))
2390 cselib_invalidate_regno (REGNO (dest), GET_MODE (dest), setter);
2391 else if (MEM_P (dest))
2392 cselib_invalidate_mem (dest);
2393 }
2394
2395 /* A wrapper for cselib_invalidate_rtx to be called via note_stores. */
2396
2397 static void
cselib_invalidate_rtx_note_stores(rtx dest,const_rtx setter,void * data ATTRIBUTE_UNUSED)2398 cselib_invalidate_rtx_note_stores (rtx dest, const_rtx setter,
2399 void *data ATTRIBUTE_UNUSED)
2400 {
2401 cselib_invalidate_rtx (dest, setter);
2402 }
2403
2404 /* Record the result of a SET instruction. DEST is being set; the source
2405 contains the value described by SRC_ELT. If DEST is a MEM, DEST_ADDR_ELT
2406 describes its address. */
2407
2408 static void
cselib_record_set(rtx dest,cselib_val * src_elt,cselib_val * dest_addr_elt)2409 cselib_record_set (rtx dest, cselib_val *src_elt, cselib_val *dest_addr_elt)
2410 {
2411 if (src_elt == 0 || side_effects_p (dest))
2412 return;
2413
2414 if (REG_P (dest))
2415 {
2416 unsigned int dreg = REGNO (dest);
2417 if (dreg < FIRST_PSEUDO_REGISTER)
2418 {
2419 unsigned int n = REG_NREGS (dest);
2420
2421 if (n > max_value_regs)
2422 max_value_regs = n;
2423 }
2424
2425 if (REG_VALUES (dreg) == 0)
2426 {
2427 used_regs[n_used_regs++] = dreg;
2428 REG_VALUES (dreg) = new_elt_list (REG_VALUES (dreg), src_elt);
2429 }
2430 else
2431 {
2432 /* The register should have been invalidated. */
2433 gcc_assert (REG_VALUES (dreg)->elt == 0);
2434 REG_VALUES (dreg)->elt = src_elt;
2435 }
2436
2437 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
2438 n_useless_values--;
2439 new_elt_loc_list (src_elt, dest);
2440 }
2441 else if (MEM_P (dest) && dest_addr_elt != 0
2442 && cselib_record_memory)
2443 {
2444 if (src_elt->locs == 0 && !PRESERVED_VALUE_P (src_elt->val_rtx))
2445 n_useless_values--;
2446 add_mem_for_addr (dest_addr_elt, src_elt, dest);
2447 }
2448 }
2449
2450 /* Make ELT and X's VALUE equivalent to each other at INSN. */
2451
2452 void
cselib_add_permanent_equiv(cselib_val * elt,rtx x,rtx_insn * insn)2453 cselib_add_permanent_equiv (cselib_val *elt, rtx x, rtx_insn *insn)
2454 {
2455 cselib_val *nelt;
2456 rtx_insn *save_cselib_current_insn = cselib_current_insn;
2457
2458 gcc_checking_assert (elt);
2459 gcc_checking_assert (PRESERVED_VALUE_P (elt->val_rtx));
2460 gcc_checking_assert (!side_effects_p (x));
2461
2462 cselib_current_insn = insn;
2463
2464 nelt = cselib_lookup (x, GET_MODE (elt->val_rtx), 1, VOIDmode);
2465
2466 if (nelt != elt)
2467 {
2468 cselib_any_perm_equivs = true;
2469
2470 if (!PRESERVED_VALUE_P (nelt->val_rtx))
2471 cselib_preserve_value (nelt);
2472
2473 new_elt_loc_list (nelt, elt->val_rtx);
2474 }
2475
2476 cselib_current_insn = save_cselib_current_insn;
2477 }
2478
2479 /* Return TRUE if any permanent equivalences have been recorded since
2480 the table was last initialized. */
2481 bool
cselib_have_permanent_equivalences(void)2482 cselib_have_permanent_equivalences (void)
2483 {
2484 return cselib_any_perm_equivs;
2485 }
2486
2487 /* There is no good way to determine how many elements there can be
2488 in a PARALLEL. Since it's fairly cheap, use a really large number. */
2489 #define MAX_SETS (FIRST_PSEUDO_REGISTER * 2)
2490
2491 struct cselib_record_autoinc_data
2492 {
2493 struct cselib_set *sets;
2494 int n_sets;
2495 };
2496
2497 /* Callback for for_each_inc_dec. Records in ARG the SETs implied by
2498 autoinc RTXs: SRC plus SRCOFF if non-NULL is stored in DEST. */
2499
2500 static int
cselib_record_autoinc_cb(rtx mem ATTRIBUTE_UNUSED,rtx op ATTRIBUTE_UNUSED,rtx dest,rtx src,rtx srcoff,void * arg)2501 cselib_record_autoinc_cb (rtx mem ATTRIBUTE_UNUSED, rtx op ATTRIBUTE_UNUSED,
2502 rtx dest, rtx src, rtx srcoff, void *arg)
2503 {
2504 struct cselib_record_autoinc_data *data;
2505 data = (struct cselib_record_autoinc_data *)arg;
2506
2507 data->sets[data->n_sets].dest = dest;
2508
2509 if (srcoff)
2510 data->sets[data->n_sets].src = gen_rtx_PLUS (GET_MODE (src), src, srcoff);
2511 else
2512 data->sets[data->n_sets].src = src;
2513
2514 data->n_sets++;
2515
2516 return 0;
2517 }
2518
2519 /* Record the effects of any sets and autoincs in INSN. */
2520 static void
cselib_record_sets(rtx_insn * insn)2521 cselib_record_sets (rtx_insn *insn)
2522 {
2523 int n_sets = 0;
2524 int i;
2525 struct cselib_set sets[MAX_SETS];
2526 rtx body = PATTERN (insn);
2527 rtx cond = 0;
2528 int n_sets_before_autoinc;
2529 int n_strict_low_parts = 0;
2530 struct cselib_record_autoinc_data data;
2531
2532 body = PATTERN (insn);
2533 if (GET_CODE (body) == COND_EXEC)
2534 {
2535 cond = COND_EXEC_TEST (body);
2536 body = COND_EXEC_CODE (body);
2537 }
2538
2539 /* Find all sets. */
2540 if (GET_CODE (body) == SET)
2541 {
2542 sets[0].src = SET_SRC (body);
2543 sets[0].dest = SET_DEST (body);
2544 n_sets = 1;
2545 }
2546 else if (GET_CODE (body) == PARALLEL)
2547 {
2548 /* Look through the PARALLEL and record the values being
2549 set, if possible. Also handle any CLOBBERs. */
2550 for (i = XVECLEN (body, 0) - 1; i >= 0; --i)
2551 {
2552 rtx x = XVECEXP (body, 0, i);
2553
2554 if (GET_CODE (x) == SET)
2555 {
2556 sets[n_sets].src = SET_SRC (x);
2557 sets[n_sets].dest = SET_DEST (x);
2558 n_sets++;
2559 }
2560 }
2561 }
2562
2563 if (n_sets == 1
2564 && MEM_P (sets[0].src)
2565 && !cselib_record_memory
2566 && MEM_READONLY_P (sets[0].src))
2567 {
2568 rtx note = find_reg_equal_equiv_note (insn);
2569
2570 if (note && CONSTANT_P (XEXP (note, 0)))
2571 sets[0].src = XEXP (note, 0);
2572 }
2573
2574 data.sets = sets;
2575 data.n_sets = n_sets_before_autoinc = n_sets;
2576 for_each_inc_dec (PATTERN (insn), cselib_record_autoinc_cb, &data);
2577 n_sets = data.n_sets;
2578
2579 /* Look up the values that are read. Do this before invalidating the
2580 locations that are written. */
2581 for (i = 0; i < n_sets; i++)
2582 {
2583 rtx dest = sets[i].dest;
2584 rtx orig = dest;
2585
2586 /* A STRICT_LOW_PART can be ignored; we'll record the equivalence for
2587 the low part after invalidating any knowledge about larger modes. */
2588 if (GET_CODE (sets[i].dest) == STRICT_LOW_PART)
2589 sets[i].dest = dest = XEXP (dest, 0);
2590
2591 /* We don't know how to record anything but REG or MEM. */
2592 if (REG_P (dest)
2593 || (MEM_P (dest) && cselib_record_memory))
2594 {
2595 rtx src = sets[i].src;
2596 if (cond)
2597 src = gen_rtx_IF_THEN_ELSE (GET_MODE (dest), cond, src, dest);
2598 sets[i].src_elt = cselib_lookup (src, GET_MODE (dest), 1, VOIDmode);
2599 if (MEM_P (dest))
2600 {
2601 machine_mode address_mode = get_address_mode (dest);
2602
2603 sets[i].dest_addr_elt = cselib_lookup (XEXP (dest, 0),
2604 address_mode, 1,
2605 GET_MODE (dest));
2606 }
2607 else
2608 sets[i].dest_addr_elt = 0;
2609 }
2610
2611 /* Improve handling of STRICT_LOW_PART if the current value is known
2612 to be const0_rtx, then the low bits will be set to dest and higher
2613 bits will remain zero. Used in code like:
2614
2615 {di:SI=0;clobber flags:CC;}
2616 flags:CCNO=cmp(bx:SI,0)
2617 strict_low_part(di:QI)=flags:CCNO<=0
2618
2619 where we can note both that di:QI=flags:CCNO<=0 and
2620 also that because di:SI is known to be 0 and strict_low_part(di:QI)
2621 preserves the upper bits that di:SI=zero_extend(flags:CCNO<=0). */
2622 scalar_int_mode mode;
2623 if (dest != orig
2624 && cselib_record_sets_hook
2625 && REG_P (dest)
2626 && HARD_REGISTER_P (dest)
2627 && sets[i].src_elt
2628 && is_a <scalar_int_mode> (GET_MODE (dest), &mode)
2629 && n_sets + n_strict_low_parts < MAX_SETS)
2630 {
2631 opt_scalar_int_mode wider_mode_iter;
2632 FOR_EACH_WIDER_MODE (wider_mode_iter, mode)
2633 {
2634 scalar_int_mode wider_mode = wider_mode_iter.require ();
2635 if (GET_MODE_PRECISION (wider_mode) > BITS_PER_WORD)
2636 break;
2637
2638 rtx reg = gen_lowpart (wider_mode, dest);
2639 if (!REG_P (reg))
2640 break;
2641
2642 cselib_val *v = cselib_lookup (reg, wider_mode, 0, VOIDmode);
2643 if (!v)
2644 continue;
2645
2646 struct elt_loc_list *l;
2647 for (l = v->locs; l; l = l->next)
2648 if (l->loc == const0_rtx)
2649 break;
2650
2651 if (!l)
2652 continue;
2653
2654 sets[n_sets + n_strict_low_parts].dest = reg;
2655 sets[n_sets + n_strict_low_parts].src = dest;
2656 sets[n_sets + n_strict_low_parts++].src_elt = sets[i].src_elt;
2657 break;
2658 }
2659 }
2660 }
2661
2662 if (cselib_record_sets_hook)
2663 cselib_record_sets_hook (insn, sets, n_sets);
2664
2665 /* Invalidate all locations written by this insn. Note that the elts we
2666 looked up in the previous loop aren't affected, just some of their
2667 locations may go away. */
2668 note_stores (body, cselib_invalidate_rtx_note_stores, NULL);
2669
2670 for (i = n_sets_before_autoinc; i < n_sets; i++)
2671 cselib_invalidate_rtx (sets[i].dest);
2672
2673 /* If this is an asm, look for duplicate sets. This can happen when the
2674 user uses the same value as an output multiple times. This is valid
2675 if the outputs are not actually used thereafter. Treat this case as
2676 if the value isn't actually set. We do this by smashing the destination
2677 to pc_rtx, so that we won't record the value later. */
2678 if (n_sets >= 2 && asm_noperands (body) >= 0)
2679 {
2680 for (i = 0; i < n_sets; i++)
2681 {
2682 rtx dest = sets[i].dest;
2683 if (REG_P (dest) || MEM_P (dest))
2684 {
2685 int j;
2686 for (j = i + 1; j < n_sets; j++)
2687 if (rtx_equal_p (dest, sets[j].dest))
2688 {
2689 sets[i].dest = pc_rtx;
2690 sets[j].dest = pc_rtx;
2691 }
2692 }
2693 }
2694 }
2695
2696 /* Now enter the equivalences in our tables. */
2697 for (i = 0; i < n_sets; i++)
2698 {
2699 rtx dest = sets[i].dest;
2700 if (REG_P (dest)
2701 || (MEM_P (dest) && cselib_record_memory))
2702 cselib_record_set (dest, sets[i].src_elt, sets[i].dest_addr_elt);
2703 }
2704
2705 /* And deal with STRICT_LOW_PART. */
2706 for (i = 0; i < n_strict_low_parts; i++)
2707 {
2708 if (! PRESERVED_VALUE_P (sets[n_sets + i].src_elt->val_rtx))
2709 continue;
2710 machine_mode dest_mode = GET_MODE (sets[n_sets + i].dest);
2711 cselib_val *v
2712 = cselib_lookup (sets[n_sets + i].dest, dest_mode, 1, VOIDmode);
2713 cselib_preserve_value (v);
2714 rtx r = gen_rtx_ZERO_EXTEND (dest_mode,
2715 sets[n_sets + i].src_elt->val_rtx);
2716 cselib_add_permanent_equiv (v, r, insn);
2717 }
2718 }
2719
2720 /* Return true if INSN in the prologue initializes hard_frame_pointer_rtx. */
2721
2722 bool
fp_setter_insn(rtx_insn * insn)2723 fp_setter_insn (rtx_insn *insn)
2724 {
2725 rtx expr, pat = NULL_RTX;
2726
2727 if (!RTX_FRAME_RELATED_P (insn))
2728 return false;
2729
2730 expr = find_reg_note (insn, REG_FRAME_RELATED_EXPR, NULL_RTX);
2731 if (expr)
2732 pat = XEXP (expr, 0);
2733 if (!modified_in_p (hard_frame_pointer_rtx, pat ? pat : insn))
2734 return false;
2735
2736 /* Don't return true for frame pointer restores in the epilogue. */
2737 if (find_reg_note (insn, REG_CFA_RESTORE, hard_frame_pointer_rtx))
2738 return false;
2739 return true;
2740 }
2741
2742 /* Record the effects of INSN. */
2743
2744 void
cselib_process_insn(rtx_insn * insn)2745 cselib_process_insn (rtx_insn *insn)
2746 {
2747 int i;
2748 rtx x;
2749
2750 cselib_current_insn = insn;
2751
2752 /* Forget everything at a CODE_LABEL or a setjmp. */
2753 if ((LABEL_P (insn)
2754 || (CALL_P (insn)
2755 && find_reg_note (insn, REG_SETJMP, NULL)))
2756 && !cselib_preserve_constants)
2757 {
2758 cselib_reset_table (next_uid);
2759 cselib_current_insn = NULL;
2760 return;
2761 }
2762
2763 if (! INSN_P (insn))
2764 {
2765 cselib_current_insn = NULL;
2766 return;
2767 }
2768
2769 /* If this is a call instruction, forget anything stored in a
2770 call clobbered register, or, if this is not a const call, in
2771 memory. */
2772 if (CALL_P (insn))
2773 {
2774 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2775 if (call_used_regs[i]
2776 || (REG_VALUES (i) && REG_VALUES (i)->elt
2777 && (targetm.hard_regno_call_part_clobbered
2778 (insn, i, GET_MODE (REG_VALUES (i)->elt->val_rtx)))))
2779 cselib_invalidate_regno (i, reg_raw_mode[i]);
2780
2781 /* Since it is not clear how cselib is going to be used, be
2782 conservative here and treat looping pure or const functions
2783 as if they were regular functions. */
2784 if (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
2785 || !(RTL_CONST_OR_PURE_CALL_P (insn)))
2786 cselib_invalidate_mem (callmem);
2787 else
2788 /* For const/pure calls, invalidate any argument slots because
2789 they are owned by the callee. */
2790 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2791 if (GET_CODE (XEXP (x, 0)) == USE
2792 && MEM_P (XEXP (XEXP (x, 0), 0)))
2793 cselib_invalidate_mem (XEXP (XEXP (x, 0), 0));
2794 }
2795
2796 cselib_record_sets (insn);
2797
2798 /* Look for any CLOBBERs in CALL_INSN_FUNCTION_USAGE, but only
2799 after we have processed the insn. */
2800 if (CALL_P (insn))
2801 {
2802 for (x = CALL_INSN_FUNCTION_USAGE (insn); x; x = XEXP (x, 1))
2803 {
2804 gcc_assert (GET_CODE (XEXP (x, 0)) != CLOBBER_HIGH);
2805 if (GET_CODE (XEXP (x, 0)) == CLOBBER)
2806 cselib_invalidate_rtx (XEXP (XEXP (x, 0), 0));
2807 }
2808 /* Flush everything on setjmp. */
2809 if (cselib_preserve_constants
2810 && find_reg_note (insn, REG_SETJMP, NULL))
2811 {
2812 cselib_preserve_only_values ();
2813 cselib_reset_table (next_uid);
2814 }
2815 }
2816
2817 /* On setter of the hard frame pointer if frame_pointer_needed,
2818 invalidate stack_pointer_rtx, so that sp and {,h}fp based
2819 VALUEs are distinct. */
2820 if (reload_completed
2821 && frame_pointer_needed
2822 && fp_setter_insn (insn))
2823 cselib_invalidate_rtx (stack_pointer_rtx);
2824
2825 cselib_current_insn = NULL;
2826
2827 if (n_useless_values > MAX_USELESS_VALUES
2828 /* remove_useless_values is linear in the hash table size. Avoid
2829 quadratic behavior for very large hashtables with very few
2830 useless elements. */
2831 && ((unsigned int)n_useless_values
2832 > (cselib_hash_table->elements () - n_debug_values) / 4))
2833 remove_useless_values ();
2834 }
2835
2836 /* Initialize cselib for one pass. The caller must also call
2837 init_alias_analysis. */
2838
2839 void
cselib_init(int record_what)2840 cselib_init (int record_what)
2841 {
2842 cselib_record_memory = record_what & CSELIB_RECORD_MEMORY;
2843 cselib_preserve_constants = record_what & CSELIB_PRESERVE_CONSTANTS;
2844 cselib_any_perm_equivs = false;
2845
2846 /* (mem:BLK (scratch)) is a special mechanism to conflict with everything,
2847 see canon_true_dependence. This is only created once. */
2848 if (! callmem)
2849 callmem = gen_rtx_MEM (BLKmode, gen_rtx_SCRATCH (VOIDmode));
2850
2851 cselib_nregs = max_reg_num ();
2852
2853 /* We preserve reg_values to allow expensive clearing of the whole thing.
2854 Reallocate it however if it happens to be too large. */
2855 if (!reg_values || reg_values_size < cselib_nregs
2856 || (reg_values_size > 10 && reg_values_size > cselib_nregs * 4))
2857 {
2858 free (reg_values);
2859 /* Some space for newly emit instructions so we don't end up
2860 reallocating in between passes. */
2861 reg_values_size = cselib_nregs + (63 + cselib_nregs) / 16;
2862 reg_values = XCNEWVEC (struct elt_list *, reg_values_size);
2863 }
2864 used_regs = XNEWVEC (unsigned int, cselib_nregs);
2865 n_used_regs = 0;
2866 cselib_hash_table = new hash_table<cselib_hasher> (31);
2867 if (cselib_preserve_constants)
2868 cselib_preserved_hash_table = new hash_table<cselib_hasher> (31);
2869 next_uid = 1;
2870 }
2871
2872 /* Called when the current user is done with cselib. */
2873
2874 void
cselib_finish(void)2875 cselib_finish (void)
2876 {
2877 bool preserved = cselib_preserve_constants;
2878 cselib_discard_hook = NULL;
2879 cselib_preserve_constants = false;
2880 cselib_any_perm_equivs = false;
2881 cfa_base_preserved_val = NULL;
2882 cfa_base_preserved_regno = INVALID_REGNUM;
2883 elt_list_pool.release ();
2884 elt_loc_list_pool.release ();
2885 cselib_val_pool.release ();
2886 value_pool.release ();
2887 cselib_clear_table ();
2888 delete cselib_hash_table;
2889 cselib_hash_table = NULL;
2890 if (preserved)
2891 delete cselib_preserved_hash_table;
2892 cselib_preserved_hash_table = NULL;
2893 free (used_regs);
2894 used_regs = 0;
2895 n_useless_values = 0;
2896 n_useless_debug_values = 0;
2897 n_debug_values = 0;
2898 next_uid = 0;
2899 }
2900
2901 /* Dump the cselib_val *X to FILE *OUT. */
2902
2903 int
dump_cselib_val(cselib_val ** x,FILE * out)2904 dump_cselib_val (cselib_val **x, FILE *out)
2905 {
2906 cselib_val *v = *x;
2907 bool need_lf = true;
2908
2909 print_inline_rtx (out, v->val_rtx, 0);
2910
2911 if (v->locs)
2912 {
2913 struct elt_loc_list *l = v->locs;
2914 if (need_lf)
2915 {
2916 fputc ('\n', out);
2917 need_lf = false;
2918 }
2919 fputs (" locs:", out);
2920 do
2921 {
2922 if (l->setting_insn)
2923 fprintf (out, "\n from insn %i ",
2924 INSN_UID (l->setting_insn));
2925 else
2926 fprintf (out, "\n ");
2927 print_inline_rtx (out, l->loc, 4);
2928 }
2929 while ((l = l->next));
2930 fputc ('\n', out);
2931 }
2932 else
2933 {
2934 fputs (" no locs", out);
2935 need_lf = true;
2936 }
2937
2938 if (v->addr_list)
2939 {
2940 struct elt_list *e = v->addr_list;
2941 if (need_lf)
2942 {
2943 fputc ('\n', out);
2944 need_lf = false;
2945 }
2946 fputs (" addr list:", out);
2947 do
2948 {
2949 fputs ("\n ", out);
2950 print_inline_rtx (out, e->elt->val_rtx, 2);
2951 }
2952 while ((e = e->next));
2953 fputc ('\n', out);
2954 }
2955 else
2956 {
2957 fputs (" no addrs", out);
2958 need_lf = true;
2959 }
2960
2961 if (v->next_containing_mem == &dummy_val)
2962 fputs (" last mem\n", out);
2963 else if (v->next_containing_mem)
2964 {
2965 fputs (" next mem ", out);
2966 print_inline_rtx (out, v->next_containing_mem->val_rtx, 2);
2967 fputc ('\n', out);
2968 }
2969 else if (need_lf)
2970 fputc ('\n', out);
2971
2972 return 1;
2973 }
2974
2975 /* Dump to OUT everything in the CSELIB table. */
2976
2977 void
dump_cselib_table(FILE * out)2978 dump_cselib_table (FILE *out)
2979 {
2980 fprintf (out, "cselib hash table:\n");
2981 cselib_hash_table->traverse <FILE *, dump_cselib_val> (out);
2982 fprintf (out, "cselib preserved hash table:\n");
2983 cselib_preserved_hash_table->traverse <FILE *, dump_cselib_val> (out);
2984 if (first_containing_mem != &dummy_val)
2985 {
2986 fputs ("first mem ", out);
2987 print_inline_rtx (out, first_containing_mem->val_rtx, 2);
2988 fputc ('\n', out);
2989 }
2990 fprintf (out, "next uid %i\n", next_uid);
2991 }
2992
2993 #include "gt-cselib.h"
2994