Line data Source code
1 : /* RTL-level loop invariant motion.
2 : Copyright (C) 2004-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it
7 : under the terms of the GNU General Public License as published by the
8 : Free Software Foundation; either version 3, or (at your option) any
9 : later version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : ANY 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 : /* This implements the loop invariant motion pass. It is very simple
21 : (no calls, no loads/stores, etc.). This should be sufficient to cleanup
22 : things like address arithmetics -- other more complicated invariants should
23 : be eliminated on GIMPLE either in tree-ssa-loop-im.cc or in tree-ssa-pre.cc.
24 :
25 : We proceed loop by loop -- it is simpler than trying to handle things
26 : globally and should not lose much. First we inspect all sets inside loop
27 : and create a dependency graph on insns (saying "to move this insn, you must
28 : also move the following insns").
29 :
30 : We then need to determine what to move. We estimate the number of registers
31 : used and move as many invariants as possible while we still have enough free
32 : registers. We prefer the expensive invariants.
33 :
34 : Then we move the selected invariants out of the loop, creating a new
35 : temporaries for them if necessary. */
36 :
37 : #include "config.h"
38 : #include "system.h"
39 : #include "coretypes.h"
40 : #include "backend.h"
41 : #include "target.h"
42 : #include "rtl.h"
43 : #include "tree.h"
44 : #include "cfghooks.h"
45 : #include "df.h"
46 : #include "memmodel.h"
47 : #include "tm_p.h"
48 : #include "insn-config.h"
49 : #include "regs.h"
50 : #include "ira.h"
51 : #include "recog.h"
52 : #include "cfgrtl.h"
53 : #include "cfgloop.h"
54 : #include "expr.h"
55 : #include "rtl-iter.h"
56 : #include "dumpfile.h"
57 :
58 : /* The data stored for the loop. */
59 :
60 : class loop_data
61 : {
62 : public:
63 : class loop *outermost_exit; /* The outermost exit of the loop. */
64 : bool has_call; /* True if the loop contains a call. */
65 : /* Maximal register pressure inside loop for given register class
66 : (defined only for the pressure classes). */
67 : int max_reg_pressure[N_REG_CLASSES];
68 : /* Loop regs referenced and live pseudo-registers. */
69 : bitmap_head regs_ref;
70 : bitmap_head regs_live;
71 : };
72 :
73 : #define LOOP_DATA(LOOP) ((class loop_data *) (LOOP)->aux)
74 :
75 : /* The description of an use. */
76 :
77 : struct use
78 : {
79 : rtx *pos; /* Position of the use. */
80 : rtx_insn *insn; /* The insn in that the use occurs. */
81 : unsigned addr_use_p; /* Whether the use occurs in an address. */
82 : struct use *next; /* Next use in the list. */
83 : };
84 :
85 : /* The description of a def. */
86 :
87 : struct def
88 : {
89 : struct use *uses; /* The list of uses that are uniquely reached
90 : by it. */
91 : unsigned n_uses; /* Number of such uses. */
92 : unsigned n_addr_uses; /* Number of uses in addresses. */
93 : unsigned invno; /* The corresponding invariant. */
94 : bool can_prop_to_addr_uses; /* True if the corresponding inv can be
95 : propagated into its address uses. */
96 : };
97 :
98 : /* The data stored for each invariant. */
99 :
100 : struct invariant
101 : {
102 : /* The number of the invariant. */
103 : unsigned invno;
104 :
105 : /* The number of the invariant with the same value. */
106 : unsigned eqto;
107 :
108 : /* The number of invariants which eqto this. */
109 : unsigned eqno;
110 :
111 : /* If we moved the invariant out of the loop, the original regno
112 : that contained its value. */
113 : int orig_regno;
114 :
115 : /* If we moved the invariant out of the loop, the register that contains its
116 : value. */
117 : rtx reg;
118 :
119 : /* The definition of the invariant. */
120 : struct def *def;
121 :
122 : /* The insn in that it is defined. */
123 : rtx_insn *insn;
124 :
125 : /* Whether it is always executed. */
126 : bool always_executed;
127 :
128 : /* Whether to move the invariant. */
129 : bool move;
130 :
131 : /* Whether the invariant is cheap when used as an address. */
132 : bool cheap_address;
133 :
134 : /* Cost of the invariant. */
135 : unsigned cost;
136 :
137 : /* Used for detecting already visited invariants during determining
138 : costs of movements. */
139 : unsigned stamp;
140 :
141 : /* The invariants it depends on. */
142 : bitmap depends_on;
143 : };
144 :
145 : /* Currently processed loop. */
146 : static class loop *curr_loop;
147 :
148 : /* Table of invariants indexed by the df_ref uid field. */
149 :
150 : static unsigned int invariant_table_size = 0;
151 : static struct invariant ** invariant_table;
152 :
153 : /* Entry for hash table of invariant expressions. */
154 :
155 : struct invariant_expr_entry
156 : {
157 : /* The invariant. */
158 : struct invariant *inv;
159 :
160 : /* Its value. */
161 : rtx expr;
162 :
163 : /* Its mode. */
164 : machine_mode mode;
165 :
166 : /* Its hash. */
167 : hashval_t hash;
168 : };
169 :
170 : /* The actual stamp for marking already visited invariants during determining
171 : costs of movements. */
172 :
173 : static unsigned actual_stamp;
174 :
175 : typedef struct invariant *invariant_p;
176 :
177 :
178 : /* The invariants. */
179 :
180 : static vec<invariant_p> invariants;
181 :
182 : /* Check the size of the invariant table and realloc if necessary. */
183 :
184 : static void
185 25091102 : check_invariant_table_size (void)
186 : {
187 25091102 : if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
188 : {
189 302054 : unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
190 302054 : invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
191 302054 : memset (&invariant_table[invariant_table_size], 0,
192 302054 : (new_size - invariant_table_size) * sizeof (struct invariant *));
193 302054 : invariant_table_size = new_size;
194 : }
195 25091102 : }
196 :
197 : /* Test for possibility of invariantness of X. */
198 :
199 : static bool
200 19256134 : check_maybe_invariant (rtx x)
201 : {
202 19256134 : enum rtx_code code = GET_CODE (x);
203 19256134 : int i, j;
204 19256134 : const char *fmt;
205 :
206 19256134 : switch (code)
207 : {
208 : CASE_CONST_ANY:
209 : case SYMBOL_REF:
210 : case CONST:
211 : case LABEL_REF:
212 : return true;
213 :
214 : case PC:
215 : case UNSPEC_VOLATILE:
216 : case CALL:
217 : return false;
218 :
219 : case REG:
220 : return true;
221 :
222 1844401 : case MEM:
223 : /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
224 : It should not be hard, and might be faster than "elsewhere". */
225 :
226 : /* Just handle the most trivial case where we load from an unchanging
227 : location (most importantly, pic tables). */
228 1844401 : if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
229 : break;
230 :
231 : return false;
232 :
233 580 : case ASM_OPERANDS:
234 : /* Don't mess with insns declared volatile. */
235 580 : if (MEM_VOLATILE_P (x))
236 : return false;
237 : break;
238 :
239 : default:
240 : break;
241 : }
242 :
243 5058420 : fmt = GET_RTX_FORMAT (code);
244 14127554 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
245 : {
246 9252687 : if (fmt[i] == 'e')
247 : {
248 8300626 : if (!check_maybe_invariant (XEXP (x, i)))
249 : return false;
250 : }
251 952061 : else if (fmt[i] == 'E')
252 : {
253 1594705 : for (j = 0; j < XVECLEN (x, i); j++)
254 1222557 : if (!check_maybe_invariant (XVECEXP (x, i, j)))
255 : return false;
256 : }
257 : }
258 :
259 : return true;
260 : }
261 :
262 : /* Returns the invariant definition for USE, or NULL if USE is not
263 : invariant. */
264 :
265 : static struct invariant *
266 24972890 : invariant_for_use (df_ref use)
267 : {
268 24972890 : struct df_link *defs;
269 24972890 : df_ref def;
270 24972890 : basic_block bb = DF_REF_BB (use), def_bb;
271 :
272 24972890 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
273 : return NULL;
274 :
275 24926478 : defs = DF_REF_CHAIN (use);
276 24926478 : if (!defs || defs->next)
277 : return NULL;
278 17883721 : def = defs->ref;
279 17883721 : check_invariant_table_size ();
280 17883721 : if (!invariant_table[DF_REF_ID (def)])
281 : return NULL;
282 :
283 1520236 : def_bb = DF_REF_BB (def);
284 1520236 : if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
285 : return NULL;
286 1519908 : return invariant_table[DF_REF_ID (def)];
287 : }
288 :
289 : /* Computes hash value for invariant expression X in INSN. */
290 :
291 : static hashval_t
292 1875233 : hash_invariant_expr_1 (rtx_insn *insn, rtx x)
293 : {
294 1875233 : enum rtx_code code = GET_CODE (x);
295 1875233 : int i, j;
296 1875233 : const char *fmt;
297 1875233 : hashval_t val = code;
298 1875233 : int do_not_record_p;
299 1875233 : df_ref use;
300 1875233 : struct invariant *inv;
301 :
302 1875233 : switch (code)
303 : {
304 845474 : CASE_CONST_ANY:
305 845474 : case SYMBOL_REF:
306 845474 : case CONST:
307 845474 : case LABEL_REF:
308 845474 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
309 :
310 733645 : case REG:
311 733645 : use = df_find_use (insn, x);
312 733645 : if (!use)
313 0 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
314 733645 : inv = invariant_for_use (use);
315 733645 : if (!inv)
316 476064 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
317 :
318 257581 : gcc_assert (inv->eqto != ~0u);
319 : return inv->eqto;
320 :
321 296114 : default:
322 296114 : break;
323 : }
324 :
325 296114 : fmt = GET_RTX_FORMAT (code);
326 841992 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
327 : {
328 545878 : if (fmt[i] == 'e')
329 497394 : val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
330 : else if (fmt[i] == 'E')
331 : {
332 7085 : for (j = 0; j < XVECLEN (x, i); j++)
333 5781 : val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
334 : }
335 : else if (fmt[i] == 'i' || fmt[i] == 'n')
336 228 : val ^= XINT (x, i);
337 : else if (fmt[i] == 'L')
338 51 : val ^= XLOC (x, i);
339 : else if (fmt[i] == 'p')
340 7637 : val ^= constant_lower_bound (SUBREG_BYTE (x));
341 : }
342 :
343 : return val;
344 : }
345 :
346 : /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
347 : and INSN2 have always the same value. */
348 :
349 : static bool
350 2556023 : invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
351 : {
352 2556023 : enum rtx_code code = GET_CODE (e1);
353 2556023 : int i, j;
354 2556023 : const char *fmt;
355 2556023 : df_ref use1, use2;
356 2556023 : struct invariant *inv1 = NULL, *inv2 = NULL;
357 2556023 : rtx sub1, sub2;
358 :
359 : /* If mode of only one of the operands is VOIDmode, it is not equivalent to
360 : the other one. If both are VOIDmode, we rely on the caller of this
361 : function to verify that their modes are the same. */
362 2556023 : if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
363 : return false;
364 :
365 1390561 : switch (code)
366 : {
367 629956 : CASE_CONST_ANY:
368 629956 : case SYMBOL_REF:
369 629956 : case CONST:
370 629956 : case LABEL_REF:
371 629956 : return rtx_equal_p (e1, e2);
372 :
373 583966 : case REG:
374 583966 : use1 = df_find_use (insn1, e1);
375 583966 : use2 = df_find_use (insn2, e2);
376 583966 : if (use1)
377 583966 : inv1 = invariant_for_use (use1);
378 583966 : if (use2)
379 583966 : inv2 = invariant_for_use (use2);
380 :
381 583966 : if (!inv1 && !inv2)
382 229664 : return rtx_equal_p (e1, e2);
383 :
384 354302 : if (!inv1 || !inv2)
385 : return false;
386 :
387 243949 : gcc_assert (inv1->eqto != ~0u);
388 243949 : gcc_assert (inv2->eqto != ~0u);
389 243949 : return inv1->eqto == inv2->eqto;
390 :
391 176639 : default:
392 176639 : break;
393 : }
394 :
395 176639 : fmt = GET_RTX_FORMAT (code);
396 231104 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
397 : {
398 207545 : if (fmt[i] == 'e')
399 : {
400 180201 : sub1 = XEXP (e1, i);
401 180201 : sub2 = XEXP (e2, i);
402 :
403 180201 : if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
404 : return false;
405 : }
406 :
407 : else if (fmt[i] == 'E')
408 : {
409 860 : if (XVECLEN (e1, i) != XVECLEN (e2, i))
410 : return false;
411 :
412 3296 : for (j = 0; j < XVECLEN (e1, i); j++)
413 : {
414 2809 : sub1 = XVECEXP (e1, i, j);
415 2809 : sub2 = XVECEXP (e2, i, j);
416 :
417 2809 : if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
418 : return false;
419 : }
420 : }
421 : else if (fmt[i] == 'i' || fmt[i] == 'n')
422 : {
423 79 : if (XINT (e1, i) != XINT (e2, i))
424 : return false;
425 : }
426 : else if (fmt[i] == 'p')
427 : {
428 4948 : if (maybe_ne (SUBREG_BYTE (e1), SUBREG_BYTE (e2)))
429 : return false;
430 : }
431 : /* Unhandled type of subexpression, we fail conservatively. */
432 : else
433 : return false;
434 : }
435 :
436 : return true;
437 : }
438 :
439 : struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
440 : {
441 : static inline hashval_t hash (const invariant_expr_entry *);
442 : static inline bool equal (const invariant_expr_entry *,
443 : const invariant_expr_entry *);
444 : };
445 :
446 : /* Returns hash value for invariant expression entry ENTRY. */
447 :
448 : inline hashval_t
449 3144089 : invariant_expr_hasher::hash (const invariant_expr_entry *entry)
450 : {
451 3144089 : return entry->hash;
452 : }
453 :
454 : /* Compares invariant expression entries ENTRY1 and ENTRY2. */
455 :
456 : inline bool
457 3631180 : invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
458 : const invariant_expr_entry *entry2)
459 : {
460 3631180 : if (entry1->mode != entry2->mode)
461 : return 0;
462 :
463 2373013 : return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
464 2373013 : entry2->inv->insn, entry2->expr);
465 : }
466 :
467 : typedef hash_table<invariant_expr_hasher> invariant_htab_type;
468 :
469 : /* Checks whether invariant with value EXPR in machine mode MODE is
470 : recorded in EQ. If this is the case, return the invariant. Otherwise
471 : insert INV to the table for this expression and return INV. */
472 :
473 : static struct invariant *
474 1372058 : find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
475 : struct invariant *inv)
476 : {
477 1372058 : hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
478 1372058 : struct invariant_expr_entry *entry;
479 1372058 : struct invariant_expr_entry pentry;
480 1372058 : invariant_expr_entry **slot;
481 :
482 1372058 : pentry.expr = expr;
483 1372058 : pentry.inv = inv;
484 1372058 : pentry.mode = mode;
485 1372058 : slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
486 1372058 : entry = *slot;
487 :
488 1372058 : if (entry)
489 388275 : return entry->inv;
490 :
491 983783 : entry = XNEW (struct invariant_expr_entry);
492 983783 : entry->inv = inv;
493 983783 : entry->expr = expr;
494 983783 : entry->mode = mode;
495 983783 : entry->hash = hash;
496 983783 : *slot = entry;
497 :
498 983783 : return inv;
499 : }
500 :
501 : /* Finds invariants identical to INV and records the equivalence. EQ is the
502 : hash table of the invariants. */
503 :
504 : static void
505 1631177 : find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
506 : {
507 1631177 : unsigned depno;
508 1631177 : bitmap_iterator bi;
509 1631177 : struct invariant *dep;
510 1631177 : rtx expr, set;
511 1631177 : machine_mode mode;
512 1631177 : struct invariant *tmp;
513 :
514 1631177 : if (inv->eqto != ~0u)
515 259119 : return;
516 :
517 1631177 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
518 : {
519 259119 : dep = invariants[depno];
520 259119 : find_identical_invariants (eq, dep);
521 : }
522 :
523 1372058 : set = single_set (inv->insn);
524 1372058 : expr = SET_SRC (set);
525 1372058 : mode = GET_MODE (expr);
526 1372058 : if (mode == VOIDmode)
527 439870 : mode = GET_MODE (SET_DEST (set));
528 :
529 1372058 : tmp = find_or_insert_inv (eq, expr, mode, inv);
530 1372058 : inv->eqto = tmp->invno;
531 :
532 1372058 : if (tmp->invno != inv->invno && inv->always_executed)
533 68321 : tmp->eqno++;
534 :
535 1372058 : if (dump_file && inv->eqto != inv->invno)
536 0 : fprintf (dump_file,
537 : "Invariant %d is equivalent to invariant %d.\n",
538 : inv->invno, inv->eqto);
539 : }
540 :
541 : /* Find invariants with the same value and record the equivalences. */
542 :
543 : static void
544 671721 : merge_identical_invariants (void)
545 : {
546 671721 : unsigned i;
547 671721 : struct invariant *inv;
548 671721 : invariant_htab_type eq (invariants.length ());
549 :
550 2715500 : FOR_EACH_VEC_ELT (invariants, i, inv)
551 1372058 : find_identical_invariants (&eq, inv);
552 671721 : }
553 :
554 : /* Determines the basic blocks inside LOOP that are always executed and
555 : stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
556 : basic blocks that may either exit the loop, or contain the call that
557 : does not have to return. BODY is body of the loop obtained by
558 : get_loop_body_in_dom_order. */
559 :
560 : static void
561 1343442 : compute_always_reached (class loop *loop, basic_block *body,
562 : bitmap may_exit, bitmap always_reached)
563 : {
564 1343442 : unsigned i;
565 :
566 2552955 : for (i = 0; i < loop->num_nodes; i++)
567 : {
568 2540284 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
569 1609773 : bitmap_set_bit (always_reached, i);
570 :
571 2540284 : if (bitmap_bit_p (may_exit, i))
572 : return;
573 : }
574 : }
575 :
576 : /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
577 : exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
578 : additionally mark blocks that may exit due to a call. */
579 :
580 : static void
581 671721 : find_exits (class loop *loop, basic_block *body,
582 : bitmap may_exit, bitmap has_exit)
583 : {
584 671721 : unsigned i;
585 671721 : edge_iterator ei;
586 671721 : edge e;
587 671721 : class loop *outermost_exit = loop, *aexit;
588 671721 : bool has_call = false;
589 671721 : rtx_insn *insn;
590 :
591 4901640 : for (i = 0; i < loop->num_nodes; i++)
592 : {
593 4229919 : if (body[i]->loop_father == loop)
594 : {
595 31138647 : FOR_BB_INSNS (body[i], insn)
596 : {
597 28487508 : auto call = dyn_cast<rtx_call_insn *> (insn);
598 486552 : if (call
599 486552 : && (RTL_LOOPING_CONST_OR_PURE_CALL_P (call)
600 484559 : || !RTL_CONST_OR_PURE_CALL_P (call)))
601 : {
602 446277 : has_call = true;
603 446277 : bitmap_set_bit (may_exit, i);
604 446277 : break;
605 : }
606 : }
607 :
608 8027320 : FOR_EACH_EDGE (e, ei, body[i]->succs)
609 : {
610 4889629 : if (! flow_bb_inside_loop_p (loop, e->dest))
611 : {
612 1141003 : bitmap_set_bit (may_exit, i);
613 1141003 : bitmap_set_bit (has_exit, i);
614 1141003 : outermost_exit = find_common_loop (outermost_exit,
615 1141003 : e->dest->loop_father);
616 : }
617 : /* If we enter a subloop that might never terminate treat
618 : it like a possible exit. */
619 4889629 : if (flow_loop_nested_p (loop, e->dest->loop_father))
620 160321 : bitmap_set_bit (may_exit, i);
621 : }
622 3137691 : continue;
623 3137691 : }
624 :
625 : /* Use the data stored for the subloop to decide whether we may exit
626 : through it. It is sufficient to do this for header of the loop,
627 : as other basic blocks inside it must be dominated by it. */
628 1092228 : if (body[i]->loop_father->header != body[i])
629 849246 : continue;
630 :
631 242982 : if (LOOP_DATA (body[i]->loop_father)->has_call)
632 : {
633 67976 : has_call = true;
634 67976 : bitmap_set_bit (may_exit, i);
635 : }
636 242982 : aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
637 242982 : if (aexit != loop)
638 : {
639 127564 : bitmap_set_bit (may_exit, i);
640 127564 : bitmap_set_bit (has_exit, i);
641 :
642 127564 : if (flow_loop_nested_p (aexit, outermost_exit))
643 4229919 : outermost_exit = aexit;
644 : }
645 : }
646 :
647 671721 : if (loop->aux == NULL)
648 : {
649 671720 : loop->aux = xcalloc (1, sizeof (class loop_data));
650 671720 : bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack);
651 671720 : bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack);
652 : }
653 671721 : LOOP_DATA (loop)->outermost_exit = outermost_exit;
654 671721 : LOOP_DATA (loop)->has_call = has_call;
655 671721 : }
656 :
657 : /* Check whether we may assign a value to X from a register. */
658 :
659 : static bool
660 13702924 : may_assign_reg_p (rtx x)
661 : {
662 13702924 : return (GET_MODE (x) != VOIDmode
663 13701410 : && GET_MODE (x) != BLKmode
664 13683967 : && can_copy_p (GET_MODE (x))
665 : /* Do not mess with the frame pointer adjustments that can
666 : be generated e.g. by expand_builtin_setjmp_receiver. */
667 11647546 : && x != frame_pointer_rtx
668 25350470 : && (!REG_P (x)
669 9823349 : || !HARD_REGISTER_P (x)
670 1692589 : || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
671 : }
672 :
673 : /* Finds definitions that may correspond to invariants in LOOP with body
674 : BODY. */
675 :
676 : static void
677 671721 : find_defs (class loop *loop)
678 : {
679 671721 : if (dump_file)
680 : {
681 21 : fprintf (dump_file,
682 : "*****starting processing of loop %d ******\n",
683 : loop->num);
684 : }
685 :
686 671721 : df_chain_add_problem (DF_UD_CHAIN);
687 671721 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
688 671721 : df_analyze_loop (loop);
689 671721 : check_invariant_table_size ();
690 :
691 671721 : if (dump_file)
692 : {
693 21 : df_dump_region (dump_file);
694 21 : fprintf (dump_file,
695 : "*****ending processing of loop %d ******\n",
696 : loop->num);
697 : }
698 671721 : }
699 :
700 : /* Creates a new invariant for definition DEF in INSN, depending on invariants
701 : in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
702 : unless the program ends due to a function call. The newly created invariant
703 : is returned. */
704 :
705 : static struct invariant *
706 1372058 : create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
707 : bool always_executed)
708 : {
709 1372058 : struct invariant *inv = XNEW (struct invariant);
710 1372058 : rtx set = single_set (insn);
711 1372058 : bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
712 :
713 1372058 : inv->def = def;
714 1372058 : inv->always_executed = always_executed;
715 1372058 : inv->depends_on = depends_on;
716 :
717 : /* If the set is simple, usually by moving it we move the whole store out of
718 : the loop. Otherwise we save only cost of the computation. */
719 1372058 : if (def)
720 : {
721 621442 : inv->cost = set_rtx_cost (set, speed);
722 : /* ??? Try to determine cheapness of address computation. Unfortunately
723 : the address cost is only a relative measure, we can't really compare
724 : it with any absolute number, but only with other address costs.
725 : But here we don't have any other addresses, so compare with a magic
726 : number anyway. It has to be large enough to not regress PR33928
727 : (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
728 : enough to not regress 410.bwaves either (by still moving reg+reg
729 : invariants).
730 : See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
731 621442 : if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
732 467904 : inv->cheap_address = address_cost (SET_SRC (set), word_mode,
733 467904 : ADDR_SPACE_GENERIC, speed) < 3;
734 : else
735 153538 : inv->cheap_address = false;
736 : }
737 : else
738 : {
739 750616 : inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
740 : speed);
741 750616 : inv->cheap_address = false;
742 : }
743 :
744 1372058 : inv->move = false;
745 1372058 : inv->reg = NULL_RTX;
746 1372058 : inv->orig_regno = -1;
747 1372058 : inv->stamp = 0;
748 1372058 : inv->insn = insn;
749 :
750 1372058 : inv->invno = invariants.length ();
751 1372058 : inv->eqto = ~0u;
752 :
753 : /* Itself. */
754 1372058 : inv->eqno = 1;
755 :
756 1372058 : if (def)
757 621442 : def->invno = inv->invno;
758 1372058 : invariants.safe_push (inv);
759 :
760 1372058 : if (dump_file)
761 : {
762 12 : fprintf (dump_file,
763 : "Set in insn %d is invariant (%d), cost %d, depends on ",
764 12 : INSN_UID (insn), inv->invno, inv->cost);
765 12 : dump_bitmap (dump_file, inv->depends_on);
766 : }
767 :
768 1372058 : return inv;
769 : }
770 :
771 : /* Return a canonical version of X for the address, from the point of view,
772 : that all multiplications are represented as MULT instead of the multiply
773 : by a power of 2 being represented as ASHIFT.
774 :
775 : Callers should prepare a copy of X because this function may modify it
776 : in place. */
777 :
778 : static void
779 32722 : canonicalize_address_mult (rtx x)
780 : {
781 32722 : subrtx_var_iterator::array_type array;
782 213940 : FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
783 : {
784 181218 : rtx sub = *iter;
785 181218 : scalar_int_mode sub_mode;
786 311967 : if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
787 130749 : && GET_CODE (sub) == ASHIFT
788 210 : && CONST_INT_P (XEXP (sub, 1))
789 420 : && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
790 210 : && INTVAL (XEXP (sub, 1)) >= 0)
791 : {
792 210 : HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
793 210 : PUT_CODE (sub, MULT);
794 210 : XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
795 210 : iter.skip_subrtxes ();
796 : }
797 : }
798 32722 : }
799 :
800 : /* Maximum number of sub expressions in address. We set it to
801 : a small integer since it's unlikely to have a complicated
802 : address expression. */
803 :
804 : #define MAX_CANON_ADDR_PARTS (5)
805 :
806 : /* Collect sub expressions in address X with PLUS as the separator.
807 : Sub expressions are stored in vector ADDR_PARTS. */
808 :
809 : static void
810 32722 : collect_address_parts (rtx x, vec<rtx> *addr_parts)
811 : {
812 32722 : subrtx_var_iterator::array_type array;
813 178776 : FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
814 : {
815 146054 : rtx sub = *iter;
816 :
817 146054 : if (GET_CODE (sub) != PLUS)
818 : {
819 89388 : addr_parts->safe_push (sub);
820 89388 : iter.skip_subrtxes ();
821 : }
822 : }
823 32722 : }
824 :
825 : /* Compare function for sorting sub expressions X and Y based on
826 : precedence defined for communitive operations. */
827 :
828 : static int
829 299046 : compare_address_parts (const void *x, const void *y)
830 : {
831 299046 : const rtx *rx = (const rtx *)x;
832 299046 : const rtx *ry = (const rtx *)y;
833 299046 : int px = commutative_operand_precedence (*rx);
834 299046 : int py = commutative_operand_precedence (*ry);
835 :
836 299046 : return (py - px);
837 : }
838 :
839 : /* Return a canonical version address for X by following steps:
840 : 1) Rewrite ASHIFT into MULT recursively.
841 : 2) Divide address into sub expressions with PLUS as the
842 : separator.
843 : 3) Sort sub expressions according to precedence defined
844 : for communative operations.
845 : 4) Simplify CONST_INT_P sub expressions.
846 : 5) Create new canonicalized address and return.
847 : Callers should prepare a copy of X because this function may
848 : modify it in place. */
849 :
850 : static rtx
851 32722 : canonicalize_address (rtx x)
852 : {
853 32722 : rtx res;
854 32722 : unsigned int i, j;
855 32722 : machine_mode mode = GET_MODE (x);
856 32722 : auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
857 :
858 : /* Rewrite ASHIFT into MULT. */
859 32722 : canonicalize_address_mult (x);
860 : /* Divide address into sub expressions. */
861 32722 : collect_address_parts (x, &addr_parts);
862 : /* Unlikely to have very complicated address. */
863 32722 : if (addr_parts.length () < 2
864 32722 : || addr_parts.length () > MAX_CANON_ADDR_PARTS)
865 : return x;
866 :
867 : /* Sort sub expressions according to canonicalization precedence. */
868 32697 : addr_parts.qsort (compare_address_parts);
869 :
870 : /* Simplify all constant int summary if possible. */
871 121115 : for (i = 0; i < addr_parts.length (); i++)
872 86173 : if (CONST_INT_P (addr_parts[i]))
873 : break;
874 :
875 35887 : for (j = i + 1; j < addr_parts.length (); j++)
876 : {
877 3190 : gcc_assert (CONST_INT_P (addr_parts[j]));
878 3190 : addr_parts[i] = simplify_gen_binary (PLUS, mode,
879 3190 : addr_parts[i],
880 3190 : addr_parts[j]);
881 : }
882 :
883 : /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
884 32697 : res = addr_parts[0];
885 55735 : for (j = 1; j < i; j++)
886 23038 : res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
887 :
888 : /* Pickup the last CONST_INT_P sub expression. */
889 63174 : if (i < addr_parts.length ())
890 30452 : res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
891 :
892 : return res;
893 32722 : }
894 :
895 : /* Given invariant DEF and its address USE, check if the corresponding
896 : invariant expr can be propagated into the use or not. */
897 :
898 : static bool
899 57912 : inv_can_prop_to_addr_use (struct def *def, df_ref use)
900 : {
901 57912 : struct invariant *inv;
902 57912 : rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
903 57912 : rtx_insn *use_insn = DF_REF_INSN (use);
904 57912 : rtx_insn *def_insn;
905 57912 : bool ok;
906 :
907 57912 : inv = invariants[def->invno];
908 : /* No need to check if address expression is expensive. */
909 57912 : if (!inv->cheap_address)
910 : return false;
911 :
912 48522 : def_insn = inv->insn;
913 48522 : def_set = single_set (def_insn);
914 48522 : if (!def_set)
915 : return false;
916 :
917 48522 : validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
918 48522 : ok = verify_changes (0);
919 : /* Try harder with canonicalization in address expression. */
920 48522 : if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
921 : {
922 36219 : rtx src, dest, mem = NULL_RTX;
923 :
924 36219 : src = SET_SRC (use_set);
925 36219 : dest = SET_DEST (use_set);
926 36219 : if (MEM_P (src))
927 : mem = src;
928 14224 : else if (MEM_P (dest))
929 : mem = dest;
930 :
931 : if (mem != NULL_RTX
932 68967 : && !memory_address_addr_space_p (GET_MODE (mem),
933 : XEXP (mem, 0),
934 32748 : MEM_ADDR_SPACE (mem)))
935 : {
936 32722 : rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
937 65444 : if (memory_address_addr_space_p (GET_MODE (mem),
938 32722 : addr, MEM_ADDR_SPACE (mem)))
939 42424 : ok = true;
940 : }
941 : }
942 48522 : cancel_changes (0);
943 48522 : return ok;
944 : }
945 :
946 : /* Record USE at DEF. */
947 :
948 : static void
949 664076 : record_use (struct def *def, df_ref use)
950 : {
951 664076 : struct use *u = XNEW (struct use);
952 :
953 664076 : u->pos = DF_REF_REAL_LOC (use);
954 664076 : u->insn = DF_REF_INSN (use);
955 664076 : u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
956 664076 : || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
957 664076 : u->next = def->uses;
958 664076 : def->uses = u;
959 664076 : def->n_uses++;
960 664076 : if (u->addr_use_p)
961 : {
962 : /* Initialize propagation information if this is the first addr
963 : use of the inv def. */
964 63784 : if (def->n_addr_uses == 0)
965 45429 : def->can_prop_to_addr_uses = true;
966 :
967 63784 : def->n_addr_uses++;
968 63784 : if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
969 15488 : def->can_prop_to_addr_uses = false;
970 : }
971 664076 : }
972 :
973 : /* Finds the invariants USE depends on and store them to the DEPENDS_ON
974 : bitmap. Returns true if all dependencies of USE are known to be
975 : loop invariants, false otherwise. */
976 :
977 : static bool
978 7105259 : check_dependency (basic_block bb, df_ref use, bitmap depends_on)
979 : {
980 7105259 : df_ref def;
981 7105259 : basic_block def_bb;
982 7105259 : struct df_link *defs;
983 7105259 : struct def *def_data;
984 7105259 : struct invariant *inv;
985 :
986 7105259 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
987 : return false;
988 :
989 7070771 : defs = DF_REF_CHAIN (use);
990 7070771 : if (!defs)
991 : {
992 1307343 : unsigned int regno = DF_REF_REGNO (use);
993 :
994 : /* If this is the use of an uninitialized argument register that is
995 : likely to be spilled, do not move it lest this might extend its
996 : lifetime and cause reload to die. This can occur for a call to
997 : a function taking complex number arguments and moving the insns
998 : preparing the arguments without moving the call itself wouldn't
999 : gain much in practice. */
1000 1307343 : if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
1001 308 : && FUNCTION_ARG_REGNO_P (regno)
1002 1307348 : && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
1003 : return false;
1004 :
1005 1307342 : return true;
1006 : }
1007 :
1008 5763428 : if (defs->next)
1009 : return false;
1010 :
1011 5242497 : def = defs->ref;
1012 5242497 : check_invariant_table_size ();
1013 5242497 : inv = invariant_table[DF_REF_ID (def)];
1014 5242497 : if (!inv)
1015 : return false;
1016 :
1017 285406 : def_data = inv->def;
1018 285406 : gcc_assert (def_data != NULL);
1019 :
1020 285406 : def_bb = DF_REF_BB (def);
1021 : /* Note that in case bb == def_bb, we know that the definition
1022 : dominates insn, because def has invariant_table[DF_REF_ID(def)]
1023 : defined and we process the insns in the basic block bb
1024 : sequentially. */
1025 285406 : if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1026 : return false;
1027 :
1028 285317 : bitmap_set_bit (depends_on, def_data->invno);
1029 285317 : return true;
1030 : }
1031 :
1032 :
1033 : /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1034 : bitmap. Returns true if all dependencies of INSN are known to be
1035 : loop invariants, false otherwise. */
1036 :
1037 : static bool
1038 6884658 : check_dependencies (rtx_insn *insn, bitmap depends_on)
1039 : {
1040 6884658 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1041 6884658 : df_ref use;
1042 6884658 : basic_block bb = BLOCK_FOR_INSN (insn);
1043 :
1044 8331326 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1045 6959268 : if (!check_dependency (bb, use, depends_on))
1046 : return false;
1047 1518049 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1048 145991 : if (!check_dependency (bb, use, depends_on))
1049 : return false;
1050 :
1051 : return true;
1052 : }
1053 :
1054 : /* Pre-check candidate DEST to skip the one which cannot make a valid insn
1055 : during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1056 : static bool
1057 11647546 : pre_check_invariant_p (bool simple, rtx dest)
1058 : {
1059 11647546 : if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1060 : {
1061 2770085 : df_ref use;
1062 2770085 : unsigned int i = REGNO (dest);
1063 2770085 : struct df_insn_info *insn_info;
1064 2770085 : df_ref def_rec;
1065 :
1066 12565607 : for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1067 : {
1068 11746094 : rtx_insn *ref = DF_REF_INSN (use);
1069 11746094 : insn_info = DF_INSN_INFO_GET (ref);
1070 :
1071 20579878 : FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1072 10784356 : if (DF_REF_REGNO (def_rec) == i)
1073 : {
1074 : /* Multi definitions at this stage, most likely are due to
1075 : instruction constraints, which requires both read and write
1076 : on the same register. Since move_invariant_reg is not
1077 : powerful enough to handle such cases, just ignore the INV
1078 : and leave the chance to others. */
1079 : return false;
1080 : }
1081 : }
1082 : }
1083 : return true;
1084 : }
1085 :
1086 : /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
1087 : executed. ALWAYS_EXECUTED is true if the insn is always executed,
1088 : unless the program ends due to a function call. */
1089 :
1090 : static void
1091 15997161 : find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1092 : {
1093 15997161 : df_ref ref;
1094 15997161 : struct def *def;
1095 15997161 : bitmap depends_on;
1096 15997161 : rtx set, dest;
1097 15997161 : bool simple = true;
1098 15997161 : struct invariant *inv;
1099 :
1100 : /* Jumps have control flow side-effects. */
1101 15997161 : if (JUMP_P (insn))
1102 : return;
1103 :
1104 14076573 : set = single_set (insn);
1105 14076573 : if (!set)
1106 : return;
1107 13702924 : dest = SET_DEST (set);
1108 :
1109 13702924 : if (!REG_P (dest)
1110 13702924 : || HARD_REGISTER_P (dest))
1111 : simple = false;
1112 :
1113 13702924 : if (!may_assign_reg_p (dest)
1114 11647546 : || !pre_check_invariant_p (simple, dest)
1115 23399898 : || !check_maybe_invariant (SET_SRC (set)))
1116 : return;
1117 :
1118 : /* If the insn can throw exception, we cannot move it at all without changing
1119 : cfg. */
1120 7603268 : if (can_throw_internal (insn))
1121 : return;
1122 :
1123 : /* We cannot make trapping insn executed, unless it was executed before. */
1124 7596491 : if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1125 : return;
1126 :
1127 : /* inline-asm that is not always executed cannot be moved
1128 : as it might conditionally trap. */
1129 6884739 : if (!always_reached && asm_noperands (PATTERN (insn)) >= 0)
1130 : return;
1131 :
1132 6884658 : depends_on = BITMAP_ALLOC (NULL);
1133 6884658 : if (!check_dependencies (insn, depends_on))
1134 : {
1135 5512600 : BITMAP_FREE (depends_on);
1136 5512600 : return;
1137 : }
1138 :
1139 1372058 : if (simple)
1140 621442 : def = XCNEW (struct def);
1141 : else
1142 : def = NULL;
1143 :
1144 1372058 : inv = create_new_invariant (def, insn, depends_on, always_executed);
1145 :
1146 1372058 : if (simple)
1147 : {
1148 621442 : ref = df_find_def (insn, dest);
1149 621442 : check_invariant_table_size ();
1150 621442 : invariant_table[DF_REF_ID (ref)] = inv;
1151 : }
1152 : }
1153 :
1154 : /* Record registers used in INSN that have a unique invariant definition. */
1155 :
1156 : static void
1157 15997161 : record_uses (rtx_insn *insn)
1158 : {
1159 15997161 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1160 15997161 : df_ref use;
1161 15997161 : struct invariant *inv;
1162 :
1163 38572984 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1164 : {
1165 22575823 : inv = invariant_for_use (use);
1166 22575823 : if (inv)
1167 663074 : record_use (inv->def, use);
1168 : }
1169 16492651 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1170 : {
1171 495490 : inv = invariant_for_use (use);
1172 495490 : if (inv)
1173 1002 : record_use (inv->def, use);
1174 : }
1175 15997161 : }
1176 :
1177 : /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
1178 : executed. ALWAYS_EXECUTED is true if the insn is always executed,
1179 : unless the program ends due to a function call. */
1180 :
1181 : static void
1182 15997161 : find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1183 : {
1184 0 : find_invariant_insn (insn, always_reached, always_executed);
1185 15997161 : record_uses (insn);
1186 0 : }
1187 :
1188 : /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1189 : basic block is always executed. ALWAYS_EXECUTED is true if the basic
1190 : block is always executed, unless the program ends due to a function
1191 : call. */
1192 :
1193 : static void
1194 4229919 : find_invariants_bb (class loop *loop, basic_block bb, bool always_reached,
1195 : bool always_executed)
1196 : {
1197 4229919 : rtx_insn *insn;
1198 4229919 : basic_block preheader = loop_preheader_edge (loop)->src;
1199 :
1200 : /* Don't move insn of cold BB out of loop to preheader to reduce calculations
1201 : and register live range in hot loop with cold BB. */
1202 4229919 : if (!always_executed && preheader->count > bb->count)
1203 : {
1204 719252 : if (dump_file)
1205 2 : fprintf (dump_file, "Don't move invariant from bb: %d out of loop %d\n",
1206 : bb->index, loop->num);
1207 : return;
1208 : }
1209 :
1210 40680574 : FOR_BB_INSNS (bb, insn)
1211 : {
1212 37169907 : if (!NONDEBUG_INSN_P (insn))
1213 21172746 : continue;
1214 :
1215 15997161 : find_invariants_insn (insn, always_reached, always_executed);
1216 :
1217 15997161 : auto call = dyn_cast<rtx_call_insn *> (insn);
1218 15997161 : if (always_reached
1219 15997161 : && call
1220 15997161 : && (RTL_LOOPING_CONST_OR_PURE_CALL_P (call)
1221 118659 : || ! RTL_CONST_OR_PURE_CALL_P (call)))
1222 : always_reached = false;
1223 : }
1224 : }
1225 :
1226 : /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1227 : basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1228 : bitmap of basic blocks in BODY that are always executed unless the program
1229 : ends due to a function call. */
1230 :
1231 : static void
1232 671721 : find_invariants_body (class loop *loop, basic_block *body,
1233 : bitmap always_reached, bitmap always_executed)
1234 : {
1235 671721 : unsigned i;
1236 :
1237 4901640 : for (i = 0; i < loop->num_nodes; i++)
1238 4229919 : find_invariants_bb (loop, body[i], bitmap_bit_p (always_reached, i),
1239 : bitmap_bit_p (always_executed, i));
1240 671721 : }
1241 :
1242 : /* Finds invariants in LOOP. */
1243 :
1244 : static void
1245 671721 : find_invariants (class loop *loop)
1246 : {
1247 671721 : auto_bitmap may_exit;
1248 671721 : auto_bitmap always_reached;
1249 671721 : auto_bitmap has_exit;
1250 671721 : auto_bitmap always_executed;
1251 671721 : basic_block *body = get_loop_body_in_dom_order (loop);
1252 :
1253 671721 : find_exits (loop, body, may_exit, has_exit);
1254 671721 : compute_always_reached (loop, body, may_exit, always_reached);
1255 671721 : compute_always_reached (loop, body, has_exit, always_executed);
1256 :
1257 671721 : find_defs (loop);
1258 671721 : find_invariants_body (loop, body, always_reached, always_executed);
1259 671721 : merge_identical_invariants ();
1260 :
1261 671721 : free (body);
1262 671721 : }
1263 :
1264 : /* Frees a list of uses USE. */
1265 :
1266 : static void
1267 621442 : free_use_list (struct use *use)
1268 : {
1269 621442 : struct use *next;
1270 :
1271 1285518 : for (; use; use = next)
1272 : {
1273 664076 : next = use->next;
1274 664076 : free (use);
1275 : }
1276 0 : }
1277 :
1278 : /* Return pressure class and number of hard registers (through *NREGS)
1279 : for destination of INSN. */
1280 : static enum reg_class
1281 15 : get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1282 : {
1283 15 : rtx reg;
1284 15 : enum reg_class pressure_class;
1285 15 : rtx set = single_set (insn);
1286 :
1287 : /* Considered invariant insns have only one set. */
1288 15 : gcc_assert (set != NULL_RTX);
1289 15 : reg = SET_DEST (set);
1290 15 : if (GET_CODE (reg) == SUBREG)
1291 0 : reg = SUBREG_REG (reg);
1292 15 : if (MEM_P (reg))
1293 : {
1294 0 : *nregs = 0;
1295 0 : pressure_class = NO_REGS;
1296 : }
1297 : else
1298 : {
1299 15 : if (! REG_P (reg))
1300 : reg = NULL_RTX;
1301 15 : if (reg == NULL_RTX)
1302 : pressure_class = GENERAL_REGS;
1303 : else
1304 : {
1305 15 : pressure_class = reg_allocno_class (REGNO (reg));
1306 15 : pressure_class = ira_pressure_class_translate[pressure_class];
1307 : }
1308 15 : *nregs
1309 15 : = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1310 : }
1311 15 : return pressure_class;
1312 : }
1313 :
1314 : /* Calculates cost and number of registers needed for moving invariant INV
1315 : out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1316 : the REG_CLASS of INV. Return
1317 : -1: if INV is invalid.
1318 : 0: if INV and its depends_on have same reg_class
1319 : 1: if INV and its depends_on have different reg_classes. */
1320 :
1321 : static int
1322 2590034 : get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1323 : enum reg_class *cl)
1324 : {
1325 2590034 : int i, acomp_cost;
1326 2590034 : unsigned aregs_needed[N_REG_CLASSES];
1327 2590034 : unsigned depno;
1328 2590034 : struct invariant *dep;
1329 2590034 : bitmap_iterator bi;
1330 2590034 : int ret = 1;
1331 :
1332 : /* Find the representative of the class of the equivalent invariants. */
1333 2590034 : inv = invariants[inv->eqto];
1334 :
1335 2590034 : *comp_cost = 0;
1336 2590034 : if (! flag_ira_loop_pressure)
1337 2590019 : regs_needed[0] = 0;
1338 : else
1339 : {
1340 75 : for (i = 0; i < ira_pressure_classes_num; i++)
1341 60 : regs_needed[ira_pressure_classes[i]] = 0;
1342 : }
1343 :
1344 2590034 : if (inv->move
1345 2587827 : || inv->stamp == actual_stamp)
1346 : return -1;
1347 2586537 : inv->stamp = actual_stamp;
1348 :
1349 2586537 : if (! flag_ira_loop_pressure)
1350 2586522 : regs_needed[0]++;
1351 : else
1352 : {
1353 15 : int nregs;
1354 15 : enum reg_class pressure_class;
1355 :
1356 15 : pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1357 15 : regs_needed[pressure_class] += nregs;
1358 15 : *cl = pressure_class;
1359 15 : ret = 0;
1360 : }
1361 :
1362 2586537 : if (!inv->cheap_address
1363 1030973 : || inv->def->n_uses == 0
1364 818851 : || inv->def->n_addr_uses < inv->def->n_uses
1365 : /* Count cost if the inv can't be propagated into address uses. */
1366 66381 : || !inv->def->can_prop_to_addr_uses)
1367 2528551 : (*comp_cost) += inv->cost * inv->eqno;
1368 :
1369 : #ifdef STACK_REGS
1370 2586537 : {
1371 : /* Hoisting constant pool constants into stack regs may cost more than
1372 : just single register. On x87, the balance is affected both by the
1373 : small number of FP registers, and by its register stack organization,
1374 : that forces us to add compensation code in and around the loop to
1375 : shuffle the operands to the top of stack before use, and pop them
1376 : from the stack after the loop finishes.
1377 :
1378 : To model this effect, we increase the number of registers needed for
1379 : stack registers by two: one register push, and one register pop.
1380 : This usually has the effect that FP constant loads from the constant
1381 : pool are not moved out of the loop.
1382 :
1383 : Note that this also means that dependent invariants cannot be moved.
1384 : However, the primary purpose of this pass is to move loop invariant
1385 : address arithmetic out of loops, and address arithmetic that depends
1386 : on floating point constants is unlikely to ever occur. */
1387 2586537 : rtx set = single_set (inv->insn);
1388 2586537 : if (set
1389 2586537 : && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1390 2598425 : && constant_pool_constant_p (SET_SRC (set)))
1391 : {
1392 7617 : if (flag_ira_loop_pressure)
1393 0 : regs_needed[ira_stack_reg_pressure_class] += 2;
1394 : else
1395 7617 : regs_needed[0] += 2;
1396 : }
1397 : }
1398 : #endif
1399 :
1400 3151814 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1401 : {
1402 565277 : bool check_p;
1403 565277 : enum reg_class dep_cl = ALL_REGS;
1404 565277 : int dep_ret;
1405 :
1406 565277 : dep = invariants[depno];
1407 :
1408 : /* If DEP is moved out of the loop, it is not a depends_on any more. */
1409 565277 : if (dep->move)
1410 83461 : continue;
1411 :
1412 481816 : dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1413 :
1414 481816 : if (! flag_ira_loop_pressure)
1415 481816 : check_p = aregs_needed[0] != 0;
1416 : else
1417 : {
1418 0 : for (i = 0; i < ira_pressure_classes_num; i++)
1419 0 : if (aregs_needed[ira_pressure_classes[i]] != 0)
1420 : break;
1421 0 : check_p = i < ira_pressure_classes_num;
1422 :
1423 0 : if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1424 : {
1425 0 : *cl = ALL_REGS;
1426 0 : ret = 1;
1427 : }
1428 : }
1429 481816 : if (check_p
1430 : /* We need to check always_executed, since if the original value of
1431 : the invariant may be preserved, we may need to keep it in a
1432 : separate register. TODO check whether the register has an
1433 : use outside of the loop. */
1434 478319 : && dep->always_executed
1435 158154 : && !dep->def->uses->next)
1436 : {
1437 : /* If this is a single use, after moving the dependency we will not
1438 : need a new register. */
1439 95647 : if (! flag_ira_loop_pressure)
1440 95647 : aregs_needed[0]--;
1441 : else
1442 : {
1443 0 : int nregs;
1444 0 : enum reg_class pressure_class;
1445 :
1446 0 : pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1447 0 : aregs_needed[pressure_class] -= nregs;
1448 : }
1449 : }
1450 :
1451 481816 : if (! flag_ira_loop_pressure)
1452 481816 : regs_needed[0] += aregs_needed[0];
1453 : else
1454 : {
1455 0 : for (i = 0; i < ira_pressure_classes_num; i++)
1456 0 : regs_needed[ira_pressure_classes[i]]
1457 0 : += aregs_needed[ira_pressure_classes[i]];
1458 : }
1459 481816 : (*comp_cost) += acomp_cost;
1460 : }
1461 : return ret;
1462 : }
1463 :
1464 : /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1465 : of registers used in the loop, NEW_REGS is the number of new variables
1466 : already added due to the invariant motion. The number of registers needed
1467 : for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1468 : through to estimate_reg_pressure_cost. */
1469 :
1470 : static int
1471 2108218 : gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1472 : unsigned *new_regs, unsigned regs_used,
1473 : bool speed, bool call_p)
1474 : {
1475 2108218 : int comp_cost, size_cost;
1476 : /* Workaround -Wmaybe-uninitialized false positive during
1477 : profiledbootstrap by initializing it. */
1478 2108218 : enum reg_class cl = NO_REGS;
1479 2108218 : int ret;
1480 :
1481 2108218 : actual_stamp++;
1482 :
1483 2108218 : ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1484 :
1485 2108218 : if (! flag_ira_loop_pressure)
1486 : {
1487 2108203 : size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1488 : regs_used, speed, call_p)
1489 2108203 : - estimate_reg_pressure_cost (new_regs[0],
1490 : regs_used, speed, call_p));
1491 : }
1492 15 : else if (ret < 0)
1493 : return -1;
1494 15 : else if ((ret == 0) && (cl == NO_REGS))
1495 : /* Hoist it anyway since it does not impact register pressure. */
1496 : return 1;
1497 : else
1498 : {
1499 : int i;
1500 : enum reg_class pressure_class;
1501 :
1502 19 : for (i = 0; i < ira_pressure_classes_num; i++)
1503 : {
1504 18 : pressure_class = ira_pressure_classes[i];
1505 :
1506 18 : if (!reg_classes_intersect_p (pressure_class, cl))
1507 3 : continue;
1508 :
1509 15 : if ((int) new_regs[pressure_class]
1510 15 : + (int) regs_needed[pressure_class]
1511 15 : + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1512 15 : + param_ira_loop_reserved_regs
1513 15 : > ira_class_hard_regs_num[pressure_class])
1514 : break;
1515 : }
1516 15 : if (i < ira_pressure_classes_num)
1517 : /* There will be register pressure excess and we want not to
1518 : make this loop invariant motion. All loop invariants with
1519 : non-positive gains will be rejected in function
1520 : find_invariants_to_move. Therefore we return the negative
1521 : number here.
1522 :
1523 : One could think that this rejects also expensive loop
1524 : invariant motions and this will hurt code performance.
1525 : However numerous experiments with different heuristics
1526 : taking invariant cost into account did not confirm this
1527 : assumption. There are possible explanations for this
1528 : result:
1529 : o probably all expensive invariants were already moved out
1530 : of the loop by PRE and gimple invariant motion pass.
1531 : o expensive invariant execution will be hidden by insn
1532 : scheduling or OOO processor hardware because usually such
1533 : invariants have a lot of freedom to be executed
1534 : out-of-order.
1535 : Another reason for ignoring invariant cost vs spilling cost
1536 : heuristics is also in difficulties to evaluate accurately
1537 : spill cost at this stage. */
1538 : return -1;
1539 : else
1540 : size_cost = 0;
1541 : }
1542 :
1543 2108204 : return comp_cost - size_cost;
1544 : }
1545 :
1546 : /* Finds invariant with best gain for moving. Returns the gain, stores
1547 : the invariant in *BEST and number of registers needed for it to
1548 : *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1549 : NEW_REGS is the number of new variables already added due to invariant
1550 : motion. */
1551 :
1552 : static int
1553 506477 : best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1554 : unsigned *new_regs, unsigned regs_used,
1555 : bool speed, bool call_p)
1556 : {
1557 506477 : struct invariant *inv;
1558 506477 : int i, gain = 0, again;
1559 506477 : unsigned aregs_needed[N_REG_CLASSES], invno;
1560 :
1561 4362080 : FOR_EACH_VEC_ELT (invariants, invno, inv)
1562 : {
1563 3855603 : if (inv->move)
1564 625074 : continue;
1565 :
1566 : /* Only consider the "representatives" of equivalent invariants. */
1567 3230529 : if (inv->eqto != inv->invno)
1568 1122311 : continue;
1569 :
1570 2108218 : again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1571 : speed, call_p);
1572 2108218 : if (again > gain)
1573 : {
1574 352660 : gain = again;
1575 352660 : *best = inv;
1576 352660 : if (! flag_ira_loop_pressure)
1577 352659 : regs_needed[0] = aregs_needed[0];
1578 : else
1579 : {
1580 5 : for (i = 0; i < ira_pressure_classes_num; i++)
1581 4 : regs_needed[ira_pressure_classes[i]]
1582 4 : = aregs_needed[ira_pressure_classes[i]];
1583 : }
1584 : }
1585 : }
1586 :
1587 506477 : return gain;
1588 : }
1589 :
1590 : /* Marks invariant INVNO and all its dependencies for moving. */
1591 :
1592 : static void
1593 336177 : set_move_mark (unsigned invno, int gain)
1594 : {
1595 336177 : struct invariant *inv = invariants[invno];
1596 336177 : bitmap_iterator bi;
1597 :
1598 : /* Find the representative of the class of the equivalent invariants. */
1599 336177 : inv = invariants[inv->eqto];
1600 :
1601 336177 : if (inv->move)
1602 2226 : return;
1603 333951 : inv->move = true;
1604 :
1605 333951 : if (dump_file)
1606 : {
1607 3 : if (gain >= 0)
1608 3 : fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1609 : invno, gain);
1610 : else
1611 0 : fprintf (dump_file, "Decided to move dependent invariant %d\n",
1612 : invno);
1613 333951 : };
1614 :
1615 410676 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1616 : {
1617 76725 : set_move_mark (invno, -1);
1618 : }
1619 : }
1620 :
1621 : /* Determines which invariants to move. */
1622 :
1623 : static void
1624 671721 : find_invariants_to_move (bool speed, bool call_p)
1625 : {
1626 671721 : int gain;
1627 671721 : unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1628 671721 : struct invariant *inv = NULL;
1629 :
1630 671721 : if (!invariants.length ())
1631 424696 : return;
1632 :
1633 247025 : if (flag_ira_loop_pressure)
1634 : /* REGS_USED is actually never used when the flag is on. */
1635 : regs_used = 0;
1636 : else
1637 : /* We do not really do a good job in estimating number of
1638 : registers used; we put some initial bound here to stand for
1639 : induction variables etc. that we do not detect. */
1640 : {
1641 247024 : unsigned int n_regs = DF_REG_SIZE (df);
1642 :
1643 247024 : regs_used = 2;
1644 :
1645 134517053 : for (i = 0; i < n_regs; i++)
1646 : {
1647 134270029 : if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1648 : {
1649 : /* This is a value that is used but not changed inside loop. */
1650 0 : regs_used++;
1651 : }
1652 : }
1653 : }
1654 :
1655 247025 : if (! flag_ira_loop_pressure)
1656 247024 : new_regs[0] = regs_needed[0] = 0;
1657 : else
1658 : {
1659 5 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
1660 4 : new_regs[ira_pressure_classes[i]] = 0;
1661 : }
1662 1012954 : while ((gain = best_gain_for_invariant (&inv, regs_needed,
1663 : new_regs, regs_used,
1664 506477 : speed, call_p)) > 0)
1665 : {
1666 259452 : set_move_mark (inv->invno, gain);
1667 259452 : if (! flag_ira_loop_pressure)
1668 259451 : new_regs[0] += regs_needed[0];
1669 : else
1670 : {
1671 5 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
1672 4 : new_regs[ira_pressure_classes[i]]
1673 4 : += regs_needed[ira_pressure_classes[i]];
1674 : }
1675 : }
1676 : }
1677 :
1678 : /* Replace the uses, reached by the definition of invariant INV, by REG.
1679 :
1680 : IN_GROUP is nonzero if this is part of a group of changes that must be
1681 : performed as a group. In that case, the changes will be stored. The
1682 : function `apply_change_group' will validate and apply the changes. */
1683 :
1684 : static int
1685 248599 : replace_uses (struct invariant *inv, rtx reg, bool in_group)
1686 : {
1687 : /* Replace the uses we know to be dominated. It saves work for copy
1688 : propagation, and also it is necessary so that dependent invariants
1689 : are computed right. */
1690 248599 : if (inv->def)
1691 : {
1692 242458 : struct use *use;
1693 457746 : for (use = inv->def->uses; use; use = use->next)
1694 215288 : validate_change (use->insn, use->pos, reg, true);
1695 :
1696 : /* If we aren't part of a larger group, apply the changes now. */
1697 242458 : if (!in_group)
1698 48141 : return apply_change_group ();
1699 : }
1700 :
1701 : return 1;
1702 : }
1703 :
1704 : /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1705 : the block preceding its header. */
1706 :
1707 : static bool
1708 333951 : can_move_invariant_reg (class loop *loop, struct invariant *inv, rtx reg)
1709 : {
1710 333951 : df_ref def, use;
1711 333951 : unsigned int dest_regno, defs_in_loop_count = 0;
1712 333951 : rtx_insn *insn = inv->insn;
1713 333951 : basic_block bb = BLOCK_FOR_INSN (inv->insn);
1714 333951 : auto_vec <rtx_insn *, 16> debug_insns_to_reset;
1715 :
1716 : /* We ignore hard register and memory access for cost and complexity reasons.
1717 : Hard register are few at this stage and expensive to consider as they
1718 : require building a separate data flow. Memory access would require using
1719 : df_simulate_* and can_move_insns_across functions and is more complex. */
1720 333951 : if (!REG_P (reg) || HARD_REGISTER_P (reg))
1721 : return false;
1722 :
1723 : /* Check whether the set is always executed. We could omit this condition if
1724 : we know that the register is unused outside of the loop, but it does not
1725 : seem worth finding out. */
1726 333017 : if (!inv->always_executed)
1727 : return false;
1728 :
1729 : /* Check that all uses that would be dominated by def are already dominated
1730 : by it. */
1731 146964 : dest_regno = REGNO (reg);
1732 375454 : for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1733 : {
1734 230275 : rtx_insn *use_insn;
1735 230275 : basic_block use_bb;
1736 :
1737 230275 : use_insn = DF_REF_INSN (use);
1738 230275 : use_bb = BLOCK_FOR_INSN (use_insn);
1739 :
1740 : /* Ignore instruction considered for moving. */
1741 230275 : if (use_insn == insn)
1742 9646 : continue;
1743 :
1744 : /* Don't consider uses outside loop. */
1745 230275 : if (!flow_bb_inside_loop_p (loop, use_bb))
1746 9646 : continue;
1747 :
1748 : /* Don't move if a use is not dominated by def in insn. */
1749 148088 : if ((use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1750 367688 : || !dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1751 : {
1752 1788 : if (!DEBUG_INSN_P (use_insn))
1753 1785 : return false;
1754 3 : debug_insns_to_reset.safe_push (use_insn);
1755 : }
1756 : }
1757 :
1758 : /* Check for other defs. Any other def in the loop might reach a use
1759 : currently reached by the def in insn. */
1760 291129 : for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1761 : {
1762 152429 : basic_block def_bb = DF_REF_BB (def);
1763 :
1764 : /* Defs in exit block cannot reach a use they weren't already. */
1765 152429 : if (single_succ_p (def_bb))
1766 : {
1767 45662 : basic_block def_bb_succ;
1768 :
1769 45662 : def_bb_succ = single_succ (def_bb);
1770 45662 : if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1771 771 : continue;
1772 : }
1773 :
1774 151658 : if (++defs_in_loop_count > 1)
1775 : return false;
1776 : }
1777 :
1778 : /* Reset debug uses if a use is not dominated by def in insn. */
1779 416102 : for (auto use_insn : debug_insns_to_reset)
1780 : {
1781 2 : INSN_VAR_LOCATION_LOC (use_insn) = gen_rtx_UNKNOWN_VAR_LOC ();
1782 2 : df_insn_rescan (use_insn);
1783 : }
1784 :
1785 : return true;
1786 333951 : }
1787 :
1788 : /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1789 : otherwise. */
1790 :
1791 : static bool
1792 1502131 : move_invariant_reg (class loop *loop, unsigned invno)
1793 : {
1794 1502131 : struct invariant *inv = invariants[invno];
1795 1502131 : struct invariant *repr = invariants[inv->eqto];
1796 1502131 : unsigned i;
1797 1502131 : basic_block preheader = loop_preheader_edge (loop)->src;
1798 1502131 : rtx reg, set, dest, note;
1799 1502131 : bitmap_iterator bi;
1800 1502131 : int regno = -1;
1801 :
1802 1502131 : if (inv->reg)
1803 : return true;
1804 1372058 : if (!repr->move)
1805 : return false;
1806 :
1807 : /* If this is a representative of the class of equivalent invariants,
1808 : really move the invariant. Otherwise just replace its use with
1809 : the register used for the representative. */
1810 387299 : if (inv == repr)
1811 : {
1812 333951 : if (inv->depends_on)
1813 : {
1814 410676 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1815 : {
1816 76725 : if (!move_invariant_reg (loop, i))
1817 0 : goto fail;
1818 : }
1819 : }
1820 :
1821 : /* If possible, just move the set out of the loop. Otherwise, we
1822 : need to create a temporary register. */
1823 333951 : set = single_set (inv->insn);
1824 333951 : reg = dest = SET_DEST (set);
1825 333951 : if (GET_CODE (reg) == SUBREG)
1826 38 : reg = SUBREG_REG (reg);
1827 333951 : if (REG_P (reg))
1828 333705 : regno = REGNO (reg);
1829 :
1830 333951 : if (!can_move_invariant_reg (loop, inv, dest))
1831 : {
1832 195251 : reg = gen_reg_rtx_and_attrs (dest);
1833 :
1834 : /* Try replacing the destination by a new pseudoregister. */
1835 195251 : validate_change (inv->insn, &SET_DEST (set), reg, true);
1836 :
1837 : /* As well as all the dominated uses. */
1838 195251 : replace_uses (inv, reg, true);
1839 :
1840 : /* And validate all the changes. */
1841 195251 : if (!apply_change_group ())
1842 41 : goto fail;
1843 :
1844 195210 : emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1845 : }
1846 138700 : else if (dump_file)
1847 1 : fprintf (dump_file, "Invariant %d moved without introducing a new "
1848 : "temporary register\n", invno);
1849 333910 : if (JUMP_P (BB_END (preheader)))
1850 6 : preheader = split_edge (loop_preheader_edge (loop));
1851 333910 : reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1852 333910 : df_recompute_luids (preheader);
1853 :
1854 : /* If there is a REG_EQUAL note on the insn we just moved, and the
1855 : insn is in a basic block that is not always executed or the note
1856 : contains something for which we don't know the invariant status,
1857 : the note may no longer be valid after we move the insn. Note that
1858 : uses in REG_EQUAL notes are taken into account in the computation
1859 : of invariants, so it is safe to retain the note even if it contains
1860 : register references for which we know the invariant status. */
1861 333910 : if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1862 333910 : && (!inv->always_executed
1863 35977 : || !check_maybe_invariant (XEXP (note, 0))))
1864 26417 : remove_note (inv->insn, note);
1865 : }
1866 : else
1867 : {
1868 53348 : if (!move_invariant_reg (loop, repr->invno))
1869 0 : goto fail;
1870 53348 : reg = repr->reg;
1871 53348 : regno = repr->orig_regno;
1872 53348 : if (!replace_uses (inv, reg, false))
1873 0 : goto fail;
1874 53348 : set = single_set (inv->insn);
1875 53348 : emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1876 53348 : delete_insn (inv->insn);
1877 : }
1878 :
1879 387258 : inv->reg = reg;
1880 387258 : inv->orig_regno = regno;
1881 :
1882 387258 : return true;
1883 :
1884 41 : fail:
1885 : /* If we failed, clear move flag, so that we do not try to move inv
1886 : again. */
1887 41 : if (dump_file)
1888 0 : fprintf (dump_file, "Failed to move invariant %d\n", invno);
1889 41 : inv->move = false;
1890 41 : inv->reg = NULL_RTX;
1891 41 : inv->orig_regno = -1;
1892 :
1893 41 : return false;
1894 : }
1895 :
1896 : /* Move selected invariant out of the LOOP. Newly created regs are marked
1897 : in TEMPORARY_REGS. */
1898 :
1899 : static void
1900 671721 : move_invariants (class loop *loop)
1901 : {
1902 671721 : struct invariant *inv;
1903 671721 : unsigned i;
1904 :
1905 2043779 : FOR_EACH_VEC_ELT (invariants, i, inv)
1906 1372058 : move_invariant_reg (loop, i);
1907 671721 : if (flag_ira_loop_pressure && resize_reg_info ())
1908 : {
1909 9 : FOR_EACH_VEC_ELT (invariants, i, inv)
1910 8 : if (inv->reg != NULL_RTX)
1911 : {
1912 1 : if (inv->orig_regno >= 0)
1913 1 : setup_reg_classes (REGNO (inv->reg),
1914 : reg_preferred_class (inv->orig_regno),
1915 : reg_alternate_class (inv->orig_regno),
1916 : reg_allocno_class (inv->orig_regno));
1917 : else
1918 0 : setup_reg_classes (REGNO (inv->reg),
1919 : GENERAL_REGS, NO_REGS, GENERAL_REGS);
1920 : }
1921 : }
1922 : /* Remove the DF_UD_CHAIN problem added in find_defs before rescanning,
1923 : to save a bit of compile time. */
1924 671721 : df_remove_problem (df_chain);
1925 671721 : df_process_deferred_rescans ();
1926 671721 : }
1927 :
1928 : /* Initializes invariant motion data. */
1929 :
1930 : static void
1931 671721 : init_inv_motion_data (void)
1932 : {
1933 671721 : actual_stamp = 1;
1934 :
1935 671721 : invariants.create (100);
1936 671721 : }
1937 :
1938 : /* Frees the data allocated by invariant motion. */
1939 :
1940 : static void
1941 671721 : free_inv_motion_data (void)
1942 : {
1943 671721 : unsigned i;
1944 671721 : struct def *def;
1945 671721 : struct invariant *inv;
1946 :
1947 671721 : check_invariant_table_size ();
1948 85959590 : for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1949 : {
1950 84616148 : inv = invariant_table[i];
1951 84616148 : if (inv)
1952 : {
1953 621442 : def = inv->def;
1954 621442 : gcc_assert (def != NULL);
1955 :
1956 621442 : free_use_list (def->uses);
1957 621442 : free (def);
1958 621442 : invariant_table[i] = NULL;
1959 : }
1960 : }
1961 :
1962 2043779 : FOR_EACH_VEC_ELT (invariants, i, inv)
1963 : {
1964 1372058 : BITMAP_FREE (inv->depends_on);
1965 1372058 : free (inv);
1966 : }
1967 671721 : invariants.release ();
1968 671721 : }
1969 :
1970 : /* Move the invariants out of the LOOP. */
1971 :
1972 : static void
1973 671721 : move_single_loop_invariants (class loop *loop)
1974 : {
1975 671721 : init_inv_motion_data ();
1976 :
1977 671721 : find_invariants (loop);
1978 671721 : find_invariants_to_move (optimize_loop_for_speed_p (loop),
1979 671721 : LOOP_DATA (loop)->has_call);
1980 671721 : move_invariants (loop);
1981 :
1982 671721 : free_inv_motion_data ();
1983 671721 : }
1984 :
1985 : /* Releases the auxiliary data for LOOP. */
1986 :
1987 : static void
1988 671721 : free_loop_data (class loop *loop)
1989 : {
1990 671721 : class loop_data *data = LOOP_DATA (loop);
1991 671721 : if (!data)
1992 : return;
1993 :
1994 671721 : bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1995 671721 : bitmap_clear (&LOOP_DATA (loop)->regs_live);
1996 671721 : free (data);
1997 671721 : loop->aux = NULL;
1998 : }
1999 :
2000 :
2001 :
2002 : /* Registers currently living. */
2003 : static bitmap_head curr_regs_live;
2004 :
2005 : /* Current reg pressure for each pressure class. */
2006 : static int curr_reg_pressure[N_REG_CLASSES];
2007 :
2008 : /* Record all regs that are set in any one insn. Communication from
2009 : mark_reg_{store,clobber} and global_conflicts. Asm can refer to
2010 : all hard-registers. */
2011 : static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
2012 : ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
2013 : /* Number of regs stored in the previous array. */
2014 : static int n_regs_set;
2015 :
2016 : /* Return pressure class and number of needed hard registers (through
2017 : *NREGS) of register REGNO. */
2018 : static enum reg_class
2019 137 : get_regno_pressure_class (int regno, int *nregs)
2020 : {
2021 137 : if (regno >= FIRST_PSEUDO_REGISTER)
2022 : {
2023 82 : enum reg_class pressure_class;
2024 :
2025 82 : pressure_class = reg_allocno_class (regno);
2026 82 : pressure_class = ira_pressure_class_translate[pressure_class];
2027 82 : *nregs
2028 82 : = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
2029 82 : return pressure_class;
2030 : }
2031 55 : else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
2032 55 : && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
2033 : {
2034 12 : *nregs = 1;
2035 12 : return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
2036 : }
2037 : else
2038 : {
2039 43 : *nregs = 0;
2040 43 : return NO_REGS;
2041 : }
2042 : }
2043 :
2044 : /* Increase (if INCR_P) or decrease current register pressure for
2045 : register REGNO. */
2046 : static void
2047 134 : change_pressure (int regno, bool incr_p)
2048 : {
2049 134 : int nregs;
2050 134 : enum reg_class pressure_class;
2051 :
2052 134 : pressure_class = get_regno_pressure_class (regno, &nregs);
2053 134 : if (! incr_p)
2054 32 : curr_reg_pressure[pressure_class] -= nregs;
2055 : else
2056 : {
2057 102 : curr_reg_pressure[pressure_class] += nregs;
2058 102 : if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2059 : < curr_reg_pressure[pressure_class])
2060 20 : LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2061 20 : = curr_reg_pressure[pressure_class];
2062 : }
2063 134 : }
2064 :
2065 : /* Mark REGNO birth. */
2066 : static void
2067 48 : mark_regno_live (int regno)
2068 : {
2069 48 : class loop *loop;
2070 :
2071 48 : for (loop = curr_loop;
2072 96 : loop != current_loops->tree_root;
2073 48 : loop = loop_outer (loop))
2074 48 : bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2075 48 : if (!bitmap_set_bit (&curr_regs_live, regno))
2076 : return;
2077 37 : change_pressure (regno, true);
2078 : }
2079 :
2080 : /* Mark REGNO death. */
2081 : static void
2082 42 : mark_regno_death (int regno)
2083 : {
2084 42 : if (! bitmap_clear_bit (&curr_regs_live, regno))
2085 : return;
2086 32 : change_pressure (regno, false);
2087 : }
2088 :
2089 : /* Mark setting register REG. */
2090 : static void
2091 53 : mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2092 : void *data ATTRIBUTE_UNUSED)
2093 : {
2094 53 : if (GET_CODE (reg) == SUBREG)
2095 0 : reg = SUBREG_REG (reg);
2096 :
2097 53 : if (! REG_P (reg))
2098 : return;
2099 :
2100 48 : regs_set[n_regs_set++] = reg;
2101 :
2102 48 : unsigned int end_regno = END_REGNO (reg);
2103 96 : for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2104 48 : mark_regno_live (regno);
2105 : }
2106 :
2107 : /* Mark clobbering register REG. */
2108 : static void
2109 43 : mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2110 : {
2111 43 : if (GET_CODE (setter) == CLOBBER)
2112 10 : mark_reg_store (reg, setter, data);
2113 43 : }
2114 :
2115 : /* Mark register REG death. */
2116 : static void
2117 42 : mark_reg_death (rtx reg)
2118 : {
2119 42 : unsigned int end_regno = END_REGNO (reg);
2120 84 : for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2121 42 : mark_regno_death (regno);
2122 42 : }
2123 :
2124 : /* Mark occurrence of registers in X for the current loop. */
2125 : static void
2126 197 : mark_ref_regs (rtx x)
2127 : {
2128 197 : RTX_CODE code;
2129 197 : int i;
2130 197 : const char *fmt;
2131 :
2132 197 : if (!x)
2133 : return;
2134 :
2135 197 : code = GET_CODE (x);
2136 197 : if (code == REG)
2137 : {
2138 82 : class loop *loop;
2139 :
2140 82 : for (loop = curr_loop;
2141 164 : loop != current_loops->tree_root;
2142 82 : loop = loop_outer (loop))
2143 82 : bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2144 : return;
2145 : }
2146 :
2147 115 : fmt = GET_RTX_FORMAT (code);
2148 305 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2149 190 : if (fmt[i] == 'e')
2150 143 : mark_ref_regs (XEXP (x, i));
2151 47 : else if (fmt[i] == 'E')
2152 : {
2153 : int j;
2154 :
2155 30 : for (j = 0; j < XVECLEN (x, i); j++)
2156 20 : mark_ref_regs (XVECEXP (x, i, j));
2157 : }
2158 : }
2159 :
2160 : /* Calculate register pressure in the loops. */
2161 : static void
2162 1 : calculate_loop_reg_pressure (void)
2163 : {
2164 1 : int i;
2165 1 : unsigned int j;
2166 1 : bitmap_iterator bi;
2167 1 : basic_block bb;
2168 1 : rtx_insn *insn;
2169 1 : rtx link;
2170 1 : class loop *parent;
2171 :
2172 4 : for (auto loop : loops_list (cfun, 0))
2173 1 : if (loop->aux == NULL)
2174 : {
2175 1 : loop->aux = xcalloc (1, sizeof (class loop_data));
2176 1 : bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack);
2177 1 : bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack);
2178 1 : }
2179 1 : ira_setup_eliminable_regset ();
2180 1 : bitmap_initialize (&curr_regs_live, ®_obstack);
2181 9 : FOR_EACH_BB_FN (bb, cfun)
2182 : {
2183 8 : curr_loop = bb->loop_father;
2184 8 : if (curr_loop == current_loops->tree_root)
2185 4 : continue;
2186 :
2187 4 : for (class loop *loop = curr_loop;
2188 8 : loop != current_loops->tree_root;
2189 4 : loop = loop_outer (loop))
2190 8 : bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2191 :
2192 4 : bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2193 24 : for (i = 0; i < ira_pressure_classes_num; i++)
2194 16 : curr_reg_pressure[ira_pressure_classes[i]] = 0;
2195 69 : EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2196 65 : change_pressure (j, true);
2197 :
2198 45 : FOR_BB_INSNS (bb, insn)
2199 : {
2200 41 : if (! NONDEBUG_INSN_P (insn))
2201 7 : continue;
2202 :
2203 34 : mark_ref_regs (PATTERN (insn));
2204 34 : n_regs_set = 0;
2205 34 : note_stores (insn, mark_reg_clobber, NULL);
2206 :
2207 : /* Mark any registers dead after INSN as dead now. */
2208 :
2209 78 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2210 44 : if (REG_NOTE_KIND (link) == REG_DEAD)
2211 22 : mark_reg_death (XEXP (link, 0));
2212 :
2213 : /* Mark any registers set in INSN as live,
2214 : and mark them as conflicting with all other live regs.
2215 : Clobbers are processed again, so they conflict with
2216 : the registers that are set. */
2217 :
2218 34 : note_stores (insn, mark_reg_store, NULL);
2219 :
2220 34 : if (AUTO_INC_DEC)
2221 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2222 : if (REG_NOTE_KIND (link) == REG_INC)
2223 : mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2224 :
2225 116 : while (n_regs_set-- > 0)
2226 : {
2227 96 : rtx note = find_regno_note (insn, REG_UNUSED,
2228 48 : REGNO (regs_set[n_regs_set]));
2229 48 : if (! note)
2230 28 : continue;
2231 :
2232 20 : mark_reg_death (XEXP (note, 0));
2233 : }
2234 : }
2235 : }
2236 1 : bitmap_release (&curr_regs_live);
2237 1 : if (flag_ira_region == IRA_REGION_MIXED
2238 1 : || flag_ira_region == IRA_REGION_ALL)
2239 4 : for (auto loop : loops_list (cfun, 0))
2240 : {
2241 41 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2242 40 : if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2243 : {
2244 3 : enum reg_class pressure_class;
2245 3 : int nregs;
2246 :
2247 3 : pressure_class = get_regno_pressure_class (j, &nregs);
2248 3 : LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2249 : }
2250 1 : }
2251 1 : if (dump_file == NULL)
2252 0 : return;
2253 4 : for (auto loop : loops_list (cfun, 0))
2254 : {
2255 1 : parent = loop_outer (loop);
2256 2 : fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2257 : loop->num, (parent == NULL ? -1 : parent->num),
2258 1 : loop->header->index, loop_depth (loop));
2259 1 : fprintf (dump_file, "\n ref. regnos:");
2260 38 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2261 37 : fprintf (dump_file, " %d", j);
2262 1 : fprintf (dump_file, "\n live regnos:");
2263 41 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2264 40 : fprintf (dump_file, " %d", j);
2265 1 : fprintf (dump_file, "\n Pressure:");
2266 6 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
2267 : {
2268 4 : enum reg_class pressure_class;
2269 :
2270 4 : pressure_class = ira_pressure_classes[i];
2271 4 : if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2272 2 : continue;
2273 2 : fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2274 : LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2275 : }
2276 1 : fprintf (dump_file, "\n");
2277 1 : }
2278 : }
2279 :
2280 :
2281 :
2282 : /* Move the invariants out of the loops. */
2283 :
2284 : void
2285 251838 : move_loop_invariants (void)
2286 : {
2287 251838 : if (optimize == 1)
2288 17137 : df_live_add_problem ();
2289 : /* ??? This is a hack. We should only need to call df_live_set_all_dirty
2290 : for optimize == 1, but can_move_invariant_reg relies on DF_INSN_LUID
2291 : being up-to-date. That isn't always true (even after df_analyze)
2292 : because df_process_deferred_rescans doesn't necessarily cause
2293 : blocks to be rescanned. */
2294 251838 : df_live_set_all_dirty ();
2295 251838 : if (flag_ira_loop_pressure)
2296 : {
2297 1 : df_analyze ();
2298 1 : regstat_init_n_sets_and_refs ();
2299 1 : ira_set_pseudo_classes (true, dump_file);
2300 1 : calculate_loop_reg_pressure ();
2301 1 : regstat_free_n_sets_and_refs ();
2302 : }
2303 251838 : df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2304 : /* Process the loops, innermost first. */
2305 1427235 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
2306 : {
2307 671721 : curr_loop = loop;
2308 : /* move_single_loop_invariants for very large loops is time consuming
2309 : and might need a lot of memory. For -O1 only do loop invariant
2310 : motion for very small loops. */
2311 671721 : unsigned max_bbs = param_loop_invariant_max_bbs_in_loop;
2312 671721 : if (optimize < 2)
2313 44837 : max_bbs /= 10;
2314 671721 : if (loop->num_nodes <= max_bbs)
2315 671721 : move_single_loop_invariants (loop);
2316 251838 : }
2317 :
2318 1427235 : for (auto loop : loops_list (cfun, 0))
2319 671721 : free_loop_data (loop);
2320 :
2321 251838 : if (flag_ira_loop_pressure)
2322 : /* There is no sense to keep this info because it was most
2323 : probably outdated by subsequent passes. */
2324 1 : free_reg_info ();
2325 251838 : free (invariant_table);
2326 251838 : invariant_table = NULL;
2327 251838 : invariant_table_size = 0;
2328 :
2329 251838 : if (optimize == 1)
2330 17137 : df_remove_problem (df_live);
2331 :
2332 251838 : checking_verify_flow_info ();
2333 251838 : }
|