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