Branch data Line data Source code
1 : : /* RTL-level loop invariant motion.
2 : : Copyright (C) 2004-2024 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 : 22929777 : check_invariant_table_size (void)
186 : : {
187 : 22929777 : if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
188 : : {
189 : 276241 : unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
190 : 276241 : invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
191 : 276241 : memset (&invariant_table[invariant_table_size], 0,
192 : 276241 : (new_size - invariant_table_size) * sizeof (struct invariant *));
193 : 276241 : invariant_table_size = new_size;
194 : : }
195 : 22929777 : }
196 : :
197 : : /* Test for possibility of invariantness of X. */
198 : :
199 : : static bool
200 : 18048126 : check_maybe_invariant (rtx x)
201 : : {
202 : 18048126 : enum rtx_code code = GET_CODE (x);
203 : 18048126 : int i, j;
204 : 18048126 : const char *fmt;
205 : :
206 : 18048126 : 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 : 1673381 : 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 : 1673381 : if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
229 : : break;
230 : :
231 : : return false;
232 : :
233 : 500 : case ASM_OPERANDS:
234 : : /* Don't mess with insns declared volatile. */
235 : 500 : if (MEM_VOLATILE_P (x))
236 : : return false;
237 : : break;
238 : :
239 : : default:
240 : : break;
241 : : }
242 : :
243 : 4763033 : fmt = GET_RTX_FORMAT (code);
244 : 13363996 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
245 : : {
246 : 8747347 : if (fmt[i] == 'e')
247 : : {
248 : 7837577 : if (!check_maybe_invariant (XEXP (x, i)))
249 : : return false;
250 : : }
251 : 909770 : else if (fmt[i] == 'E')
252 : : {
253 : 1587420 : for (j = 0; j < XVECLEN (x, i); j++)
254 : 1237276 : 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 : 22736932 : invariant_for_use (df_ref use)
267 : : {
268 : 22736932 : struct df_link *defs;
269 : 22736932 : df_ref def;
270 : 22736932 : basic_block bb = DF_REF_BB (use), def_bb;
271 : :
272 : 22736932 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
273 : : return NULL;
274 : :
275 : 22687177 : defs = DF_REF_CHAIN (use);
276 : 22687177 : if (!defs || defs->next)
277 : : return NULL;
278 : 16209457 : def = defs->ref;
279 : 16209457 : check_invariant_table_size ();
280 : 16209457 : if (!invariant_table[DF_REF_ID (def)])
281 : : return NULL;
282 : :
283 : 1459332 : def_bb = DF_REF_BB (def);
284 : 1459332 : if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
285 : : return NULL;
286 : 1458966 : 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 : 1784376 : hash_invariant_expr_1 (rtx_insn *insn, rtx x)
293 : : {
294 : 1784376 : enum rtx_code code = GET_CODE (x);
295 : 1784376 : int i, j;
296 : 1784376 : const char *fmt;
297 : 1784376 : hashval_t val = code;
298 : 1784376 : int do_not_record_p;
299 : 1784376 : df_ref use;
300 : 1784376 : struct invariant *inv;
301 : :
302 : 1784376 : switch (code)
303 : : {
304 : 775028 : CASE_CONST_ANY:
305 : 775028 : case SYMBOL_REF:
306 : 775028 : case CONST:
307 : 775028 : case LABEL_REF:
308 : 775028 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
309 : :
310 : 704396 : case REG:
311 : 704396 : use = df_find_use (insn, x);
312 : 704396 : if (!use)
313 : 0 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
314 : 704396 : inv = invariant_for_use (use);
315 : 704396 : if (!inv)
316 : 458656 : return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
317 : :
318 : 245740 : gcc_assert (inv->eqto != ~0u);
319 : : return inv->eqto;
320 : :
321 : 304952 : default:
322 : 304952 : break;
323 : : }
324 : :
325 : 304952 : fmt = GET_RTX_FORMAT (code);
326 : 872965 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
327 : : {
328 : 568013 : if (fmt[i] == 'e')
329 : 522338 : val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
330 : : else if (fmt[i] == 'E')
331 : : {
332 : 4748 : for (j = 0; j < XVECLEN (x, i); j++)
333 : 3895 : val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
334 : : }
335 : : else if (fmt[i] == 'i' || fmt[i] == 'n')
336 : 208 : val ^= XINT (x, i);
337 : : else if (fmt[i] == 'L')
338 : 56 : val ^= XLOC (x, i);
339 : : else if (fmt[i] == 'p')
340 : 6435 : 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 : 2368545 : invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
351 : : {
352 : 2368545 : enum rtx_code code = GET_CODE (e1);
353 : 2368545 : int i, j;
354 : 2368545 : const char *fmt;
355 : 2368545 : df_ref use1, use2;
356 : 2368545 : struct invariant *inv1 = NULL, *inv2 = NULL;
357 : 2368545 : 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 : 2368545 : if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
363 : : return false;
364 : :
365 : 1221897 : switch (code)
366 : : {
367 : 496300 : CASE_CONST_ANY:
368 : 496300 : case SYMBOL_REF:
369 : 496300 : case CONST:
370 : 496300 : case LABEL_REF:
371 : 496300 : return rtx_equal_p (e1, e2);
372 : :
373 : 543045 : case REG:
374 : 543045 : use1 = df_find_use (insn1, e1);
375 : 543045 : use2 = df_find_use (insn2, e2);
376 : 543045 : if (use1)
377 : 543045 : inv1 = invariant_for_use (use1);
378 : 543045 : if (use2)
379 : 543045 : inv2 = invariant_for_use (use2);
380 : :
381 : 543045 : if (!inv1 && !inv2)
382 : 205070 : return rtx_equal_p (e1, e2);
383 : :
384 : 337975 : if (!inv1 || !inv2)
385 : : return false;
386 : :
387 : 238832 : gcc_assert (inv1->eqto != ~0u);
388 : 238832 : gcc_assert (inv2->eqto != ~0u);
389 : 238832 : return inv1->eqto == inv2->eqto;
390 : :
391 : 182552 : default:
392 : 182552 : break;
393 : : }
394 : :
395 : 182552 : fmt = GET_RTX_FORMAT (code);
396 : 233896 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
397 : : {
398 : 211567 : if (fmt[i] == 'e')
399 : : {
400 : 185937 : sub1 = XEXP (e1, i);
401 : 185937 : sub2 = XEXP (e2, i);
402 : :
403 : 185937 : if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
404 : : return false;
405 : : }
406 : :
407 : : else if (fmt[i] == 'E')
408 : : {
409 : 522 : if (XVECLEN (e1, i) != XVECLEN (e2, i))
410 : : return false;
411 : :
412 : 1660 : for (j = 0; j < XVECLEN (e1, i); j++)
413 : : {
414 : 1395 : sub1 = XVECEXP (e1, i, j);
415 : 1395 : sub2 = XVECEXP (e2, i, j);
416 : :
417 : 1395 : 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 : 110 : if (XINT (e1, i) != XINT (e2, i))
424 : : return false;
425 : : }
426 : : else if (fmt[i] == 'p')
427 : : {
428 : 4332 : 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 : 2888188 : invariant_expr_hasher::hash (const invariant_expr_entry *entry)
450 : : {
451 : 2888188 : return entry->hash;
452 : : }
453 : :
454 : : /* Compares invariant expression entries ENTRY1 and ENTRY2. */
455 : :
456 : : inline bool
457 : 3356409 : invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
458 : : const invariant_expr_entry *entry2)
459 : : {
460 : 3356409 : if (entry1->mode != entry2->mode)
461 : : return 0;
462 : :
463 : 2181213 : return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
464 : 2181213 : 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 : 1258143 : find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
475 : : struct invariant *inv)
476 : : {
477 : 1258143 : hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
478 : 1258143 : struct invariant_expr_entry *entry;
479 : 1258143 : struct invariant_expr_entry pentry;
480 : 1258143 : invariant_expr_entry **slot;
481 : :
482 : 1258143 : pentry.expr = expr;
483 : 1258143 : pentry.inv = inv;
484 : 1258143 : pentry.mode = mode;
485 : 1258143 : slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
486 : 1258143 : entry = *slot;
487 : :
488 : 1258143 : if (entry)
489 : 352172 : return entry->inv;
490 : :
491 : 905971 : entry = XNEW (struct invariant_expr_entry);
492 : 905971 : entry->inv = inv;
493 : 905971 : entry->expr = expr;
494 : 905971 : entry->mode = mode;
495 : 905971 : entry->hash = hash;
496 : 905971 : *slot = entry;
497 : :
498 : 905971 : 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 : 1504273 : find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
506 : : {
507 : 1504273 : unsigned depno;
508 : 1504273 : bitmap_iterator bi;
509 : 1504273 : struct invariant *dep;
510 : 1504273 : rtx expr, set;
511 : 1504273 : machine_mode mode;
512 : 1504273 : struct invariant *tmp;
513 : :
514 : 1504273 : if (inv->eqto != ~0u)
515 : 246130 : return;
516 : :
517 : 1504273 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
518 : : {
519 : 246130 : dep = invariants[depno];
520 : 246130 : find_identical_invariants (eq, dep);
521 : : }
522 : :
523 : 1258143 : set = single_set (inv->insn);
524 : 1258143 : expr = SET_SRC (set);
525 : 1258143 : mode = GET_MODE (expr);
526 : 1258143 : if (mode == VOIDmode)
527 : 367922 : mode = GET_MODE (SET_DEST (set));
528 : :
529 : 1258143 : tmp = find_or_insert_inv (eq, expr, mode, inv);
530 : 1258143 : inv->eqto = tmp->invno;
531 : :
532 : 1258143 : if (tmp->invno != inv->invno && inv->always_executed)
533 : 62465 : tmp->eqno++;
534 : :
535 : 1258143 : 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 : 601647 : merge_identical_invariants (void)
545 : : {
546 : 601647 : unsigned i;
547 : 601647 : struct invariant *inv;
548 : 601647 : invariant_htab_type eq (invariants.length ());
549 : :
550 : 2461437 : FOR_EACH_VEC_ELT (invariants, i, inv)
551 : 1258143 : find_identical_invariants (&eq, inv);
552 : 601647 : }
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 : 1203294 : compute_always_reached (class loop *loop, basic_block *body,
562 : : bitmap may_exit, bitmap always_reached)
563 : : {
564 : 1203294 : unsigned i;
565 : :
566 : 2253829 : for (i = 0; i < loop->num_nodes; i++)
567 : : {
568 : 2240405 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
569 : 1438553 : bitmap_set_bit (always_reached, i);
570 : :
571 : 2240405 : 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 : 601647 : find_exits (class loop *loop, basic_block *body,
582 : : bitmap may_exit, bitmap has_exit)
583 : : {
584 : 601647 : unsigned i;
585 : 601647 : edge_iterator ei;
586 : 601647 : edge e;
587 : 601647 : class loop *outermost_exit = loop, *aexit;
588 : 601647 : bool has_call = false;
589 : 601647 : rtx_insn *insn;
590 : :
591 : 4319648 : for (i = 0; i < loop->num_nodes; i++)
592 : : {
593 : 3718001 : if (body[i]->loop_father == loop)
594 : : {
595 : 26323560 : FOR_BB_INSNS (body[i], insn)
596 : : {
597 : 23959482 : if (CALL_P (insn)
598 : 23959482 : && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
599 : 472089 : || !RTL_CONST_OR_PURE_CALL_P (insn)))
600 : : {
601 : 428949 : has_call = true;
602 : 428949 : bitmap_set_bit (may_exit, i);
603 : 428949 : break;
604 : : }
605 : : }
606 : :
607 : 7162519 : FOR_EACH_EDGE (e, ei, body[i]->succs)
608 : : {
609 : 4369492 : if (! flow_bb_inside_loop_p (loop, e->dest))
610 : : {
611 : 1052780 : bitmap_set_bit (may_exit, i);
612 : 1052780 : bitmap_set_bit (has_exit, i);
613 : 1052780 : outermost_exit = find_common_loop (outermost_exit,
614 : 1052780 : e->dest->loop_father);
615 : : }
616 : : /* If we enter a subloop that might never terminate treat
617 : : it like a possible exit. */
618 : 4369492 : if (flow_loop_nested_p (loop, e->dest->loop_father))
619 : 138474 : bitmap_set_bit (may_exit, i);
620 : : }
621 : 2793027 : continue;
622 : 2793027 : }
623 : :
624 : : /* Use the data stored for the subloop to decide whether we may exit
625 : : through it. It is sufficient to do this for header of the loop,
626 : : as other basic blocks inside it must be dominated by it. */
627 : 924974 : if (body[i]->loop_father->header != body[i])
628 : 713799 : continue;
629 : :
630 : 211175 : if (LOOP_DATA (body[i]->loop_father)->has_call)
631 : : {
632 : 59824 : has_call = true;
633 : 59824 : bitmap_set_bit (may_exit, i);
634 : : }
635 : 211175 : aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
636 : 211175 : if (aexit != loop)
637 : : {
638 : 111278 : bitmap_set_bit (may_exit, i);
639 : 111278 : bitmap_set_bit (has_exit, i);
640 : :
641 : 111278 : if (flow_loop_nested_p (aexit, outermost_exit))
642 : 3718001 : outermost_exit = aexit;
643 : : }
644 : : }
645 : :
646 : 601647 : if (loop->aux == NULL)
647 : : {
648 : 601646 : loop->aux = xcalloc (1, sizeof (class loop_data));
649 : 601646 : bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack);
650 : 601646 : bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack);
651 : : }
652 : 601647 : LOOP_DATA (loop)->outermost_exit = outermost_exit;
653 : 601647 : LOOP_DATA (loop)->has_call = has_call;
654 : 601647 : }
655 : :
656 : : /* Check whether we may assign a value to X from a register. */
657 : :
658 : : static bool
659 : 12544563 : may_assign_reg_p (rtx x)
660 : : {
661 : 12544563 : return (GET_MODE (x) != VOIDmode
662 : 12543045 : && GET_MODE (x) != BLKmode
663 : 12522467 : && can_copy_p (GET_MODE (x))
664 : : /* Do not mess with the frame pointer adjustments that can
665 : : be generated e.g. by expand_builtin_setjmp_receiver. */
666 : 10714997 : && x != frame_pointer_rtx
667 : 23259560 : && (!REG_P (x)
668 : 9125091 : || !HARD_REGISTER_P (x)
669 : 1583684 : || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
670 : : }
671 : :
672 : : /* Finds definitions that may correspond to invariants in LOOP with body
673 : : BODY. */
674 : :
675 : : static void
676 : 601647 : find_defs (class loop *loop)
677 : : {
678 : 601647 : if (dump_file)
679 : : {
680 : 21 : fprintf (dump_file,
681 : : "*****starting processing of loop %d ******\n",
682 : : loop->num);
683 : : }
684 : :
685 : 601647 : df_chain_add_problem (DF_UD_CHAIN);
686 : 601647 : df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
687 : 601647 : df_analyze_loop (loop);
688 : 601647 : check_invariant_table_size ();
689 : :
690 : 601647 : if (dump_file)
691 : : {
692 : 21 : df_dump_region (dump_file);
693 : 21 : fprintf (dump_file,
694 : : "*****ending processing of loop %d ******\n",
695 : : loop->num);
696 : : }
697 : 601647 : }
698 : :
699 : : /* Creates a new invariant for definition DEF in INSN, depending on invariants
700 : : in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
701 : : unless the program ends due to a function call. The newly created invariant
702 : : is returned. */
703 : :
704 : : static struct invariant *
705 : 1258143 : create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
706 : : bool always_executed)
707 : : {
708 : 1258143 : struct invariant *inv = XNEW (struct invariant);
709 : 1258143 : rtx set = single_set (insn);
710 : 1258143 : bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
711 : :
712 : 1258143 : inv->def = def;
713 : 1258143 : inv->always_executed = always_executed;
714 : 1258143 : inv->depends_on = depends_on;
715 : :
716 : : /* If the set is simple, usually by moving it we move the whole store out of
717 : : the loop. Otherwise we save only cost of the computation. */
718 : 1258143 : if (def)
719 : : {
720 : 606179 : inv->cost = set_rtx_cost (set, speed);
721 : : /* ??? Try to determine cheapness of address computation. Unfortunately
722 : : the address cost is only a relative measure, we can't really compare
723 : : it with any absolute number, but only with other address costs.
724 : : But here we don't have any other addresses, so compare with a magic
725 : : number anyway. It has to be large enough to not regress PR33928
726 : : (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
727 : : enough to not regress 410.bwaves either (by still moving reg+reg
728 : : invariants).
729 : : See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
730 : 606179 : if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
731 : 459070 : inv->cheap_address = address_cost (SET_SRC (set), word_mode,
732 : 459070 : ADDR_SPACE_GENERIC, speed) < 3;
733 : : else
734 : 147109 : inv->cheap_address = false;
735 : : }
736 : : else
737 : : {
738 : 651964 : inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
739 : : speed);
740 : 651964 : inv->cheap_address = false;
741 : : }
742 : :
743 : 1258143 : inv->move = false;
744 : 1258143 : inv->reg = NULL_RTX;
745 : 1258143 : inv->orig_regno = -1;
746 : 1258143 : inv->stamp = 0;
747 : 1258143 : inv->insn = insn;
748 : :
749 : 1258143 : inv->invno = invariants.length ();
750 : 1258143 : inv->eqto = ~0u;
751 : :
752 : : /* Itself. */
753 : 1258143 : inv->eqno = 1;
754 : :
755 : 1258143 : if (def)
756 : 606179 : def->invno = inv->invno;
757 : 1258143 : invariants.safe_push (inv);
758 : :
759 : 1258143 : if (dump_file)
760 : : {
761 : 12 : fprintf (dump_file,
762 : : "Set in insn %d is invariant (%d), cost %d, depends on ",
763 : 12 : INSN_UID (insn), inv->invno, inv->cost);
764 : 12 : dump_bitmap (dump_file, inv->depends_on);
765 : : }
766 : :
767 : 1258143 : return inv;
768 : : }
769 : :
770 : : /* Return a canonical version of X for the address, from the point of view,
771 : : that all multiplications are represented as MULT instead of the multiply
772 : : by a power of 2 being represented as ASHIFT.
773 : :
774 : : Callers should prepare a copy of X because this function may modify it
775 : : in place. */
776 : :
777 : : static void
778 : 27406 : canonicalize_address_mult (rtx x)
779 : : {
780 : 27406 : subrtx_var_iterator::array_type array;
781 : 195031 : FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
782 : : {
783 : 167625 : rtx sub = *iter;
784 : 167625 : scalar_int_mode sub_mode;
785 : 289981 : if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
786 : 122356 : && GET_CODE (sub) == ASHIFT
787 : 187 : && CONST_INT_P (XEXP (sub, 1))
788 : 374 : && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
789 : 187 : && INTVAL (XEXP (sub, 1)) >= 0)
790 : : {
791 : 187 : HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
792 : 187 : PUT_CODE (sub, MULT);
793 : 187 : XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
794 : 187 : iter.skip_subrtxes ();
795 : : }
796 : : }
797 : 27406 : }
798 : :
799 : : /* Maximum number of sub expressions in address. We set it to
800 : : a small integer since it's unlikely to have a complicated
801 : : address expression. */
802 : :
803 : : #define MAX_CANON_ADDR_PARTS (5)
804 : :
805 : : /* Collect sub expressions in address X with PLUS as the seperator.
806 : : Sub expressions are stored in vector ADDR_PARTS. */
807 : :
808 : : static void
809 : 27406 : collect_address_parts (rtx x, vec<rtx> *addr_parts)
810 : : {
811 : 27406 : subrtx_var_iterator::array_type array;
812 : 158404 : FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
813 : : {
814 : 130998 : rtx sub = *iter;
815 : :
816 : 130998 : if (GET_CODE (sub) != PLUS)
817 : : {
818 : 79202 : addr_parts->safe_push (sub);
819 : 79202 : iter.skip_subrtxes ();
820 : : }
821 : : }
822 : 27406 : }
823 : :
824 : : /* Compare function for sorting sub expressions X and Y based on
825 : : precedence defined for communitive operations. */
826 : :
827 : : static int
828 : 281126 : compare_address_parts (const void *x, const void *y)
829 : : {
830 : 281126 : const rtx *rx = (const rtx *)x;
831 : 281126 : const rtx *ry = (const rtx *)y;
832 : 281126 : int px = commutative_operand_precedence (*rx);
833 : 281126 : int py = commutative_operand_precedence (*ry);
834 : :
835 : 281126 : return (py - px);
836 : : }
837 : :
838 : : /* Return a canonical version address for X by following steps:
839 : : 1) Rewrite ASHIFT into MULT recursively.
840 : : 2) Divide address into sub expressions with PLUS as the
841 : : separator.
842 : : 3) Sort sub expressions according to precedence defined
843 : : for communative operations.
844 : : 4) Simplify CONST_INT_P sub expressions.
845 : : 5) Create new canonicalized address and return.
846 : : Callers should prepare a copy of X because this function may
847 : : modify it in place. */
848 : :
849 : : static rtx
850 : 27406 : canonicalize_address (rtx x)
851 : : {
852 : 27406 : rtx res;
853 : 27406 : unsigned int i, j;
854 : 27406 : machine_mode mode = GET_MODE (x);
855 : 27406 : auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
856 : :
857 : : /* Rewrite ASHIFT into MULT. */
858 : 27406 : canonicalize_address_mult (x);
859 : : /* Divide address into sub expressions. */
860 : 27406 : collect_address_parts (x, &addr_parts);
861 : : /* Unlikely to have very complicated address. */
862 : 27406 : if (addr_parts.length () < 2
863 : 27406 : || addr_parts.length () > MAX_CANON_ADDR_PARTS)
864 : : return x;
865 : :
866 : : /* Sort sub expressions according to canonicalization precedence. */
867 : 27374 : addr_parts.qsort (compare_address_parts);
868 : :
869 : : /* Simplify all constant int summary if possible. */
870 : 106325 : for (i = 0; i < addr_parts.length (); i++)
871 : 77094 : if (CONST_INT_P (addr_parts[i]))
872 : : break;
873 : :
874 : 29450 : for (j = i + 1; j < addr_parts.length (); j++)
875 : : {
876 : 2076 : gcc_assert (CONST_INT_P (addr_parts[j]));
877 : 2076 : addr_parts[i] = simplify_gen_binary (PLUS, mode,
878 : 2076 : addr_parts[i],
879 : 2076 : addr_parts[j]);
880 : : }
881 : :
882 : : /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
883 : 27374 : res = addr_parts[0];
884 : 51591 : for (j = 1; j < i; j++)
885 : 24217 : res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
886 : :
887 : : /* Pickup the last CONST_INT_P sub expression. */
888 : 52923 : if (i < addr_parts.length ())
889 : 25517 : res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
890 : :
891 : : return res;
892 : 27406 : }
893 : :
894 : : /* Given invariant DEF and its address USE, check if the corresponding
895 : : invariant expr can be propagated into the use or not. */
896 : :
897 : : static bool
898 : 49376 : inv_can_prop_to_addr_use (struct def *def, df_ref use)
899 : : {
900 : 49376 : struct invariant *inv;
901 : 49376 : rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
902 : 49376 : rtx_insn *use_insn = DF_REF_INSN (use);
903 : 49376 : rtx_insn *def_insn;
904 : 49376 : bool ok;
905 : :
906 : 49376 : inv = invariants[def->invno];
907 : : /* No need to check if address expression is expensive. */
908 : 49376 : if (!inv->cheap_address)
909 : : return false;
910 : :
911 : 43642 : def_insn = inv->insn;
912 : 43642 : def_set = single_set (def_insn);
913 : 43642 : if (!def_set)
914 : : return false;
915 : :
916 : 43642 : validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
917 : 43642 : ok = verify_changes (0);
918 : : /* Try harder with canonicalization in address expression. */
919 : 43642 : if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
920 : : {
921 : 31709 : rtx src, dest, mem = NULL_RTX;
922 : :
923 : 31709 : src = SET_SRC (use_set);
924 : 31709 : dest = SET_DEST (use_set);
925 : 31709 : if (MEM_P (src))
926 : : mem = src;
927 : 8505 : else if (MEM_P (dest))
928 : : mem = dest;
929 : :
930 : : if (mem != NULL_RTX
931 : 59708 : && !memory_address_addr_space_p (GET_MODE (mem),
932 : : XEXP (mem, 0),
933 : 27999 : MEM_ADDR_SPACE (mem)))
934 : : {
935 : 27406 : rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
936 : 54812 : if (memory_address_addr_space_p (GET_MODE (mem),
937 : 27406 : addr, MEM_ADDR_SPACE (mem)))
938 : 43642 : ok = true;
939 : : }
940 : : }
941 : 43642 : cancel_changes (0);
942 : 43642 : return ok;
943 : : }
944 : :
945 : : /* Record USE at DEF. */
946 : :
947 : : static void
948 : 636419 : record_use (struct def *def, df_ref use)
949 : : {
950 : 636419 : struct use *u = XNEW (struct use);
951 : :
952 : 636419 : u->pos = DF_REF_REAL_LOC (use);
953 : 636419 : u->insn = DF_REF_INSN (use);
954 : 636419 : u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
955 : 636419 : || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
956 : 636419 : u->next = def->uses;
957 : 636419 : def->uses = u;
958 : 636419 : def->n_uses++;
959 : 636419 : if (u->addr_use_p)
960 : : {
961 : : /* Initialize propagation information if this is the first addr
962 : : use of the inv def. */
963 : 53107 : if (def->n_addr_uses == 0)
964 : 44727 : def->can_prop_to_addr_uses = true;
965 : :
966 : 53107 : def->n_addr_uses++;
967 : 53107 : if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
968 : 12105 : def->can_prop_to_addr_uses = false;
969 : : }
970 : 636419 : }
971 : :
972 : : /* Finds the invariants USE depends on and store them to the DEPENDS_ON
973 : : bitmap. Returns true if all dependencies of USE are known to be
974 : : loop invariants, false otherwise. */
975 : :
976 : : static bool
977 : 6638085 : check_dependency (basic_block bb, df_ref use, bitmap depends_on)
978 : : {
979 : 6638085 : df_ref def;
980 : 6638085 : basic_block def_bb;
981 : 6638085 : struct df_link *defs;
982 : 6638085 : struct def *def_data;
983 : 6638085 : struct invariant *inv;
984 : :
985 : 6638085 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
986 : : return false;
987 : :
988 : 6601049 : defs = DF_REF_CHAIN (use);
989 : 6601049 : if (!defs)
990 : : {
991 : 1194444 : unsigned int regno = DF_REF_REGNO (use);
992 : :
993 : : /* If this is the use of an uninitialized argument register that is
994 : : likely to be spilled, do not move it lest this might extend its
995 : : lifetime and cause reload to die. This can occur for a call to
996 : : a function taking complex number arguments and moving the insns
997 : : preparing the arguments without moving the call itself wouldn't
998 : : gain much in practice. */
999 : 1194444 : if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
1000 : 321 : && FUNCTION_ARG_REGNO_P (regno)
1001 : 1194449 : && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
1002 : : return false;
1003 : :
1004 : 1194443 : return true;
1005 : : }
1006 : :
1007 : 5406605 : if (defs->next)
1008 : : return false;
1009 : :
1010 : 4910847 : def = defs->ref;
1011 : 4910847 : check_invariant_table_size ();
1012 : 4910847 : inv = invariant_table[DF_REF_ID (def)];
1013 : 4910847 : if (!inv)
1014 : : return false;
1015 : :
1016 : 273335 : def_data = inv->def;
1017 : 273335 : gcc_assert (def_data != NULL);
1018 : :
1019 : 273335 : def_bb = DF_REF_BB (def);
1020 : : /* Note that in case bb == def_bb, we know that the definition
1021 : : dominates insn, because def has invariant_table[DF_REF_ID(def)]
1022 : : defined and we process the insns in the basic block bb
1023 : : sequentially. */
1024 : 273335 : if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1025 : : return false;
1026 : :
1027 : 273235 : bitmap_set_bit (depends_on, def_data->invno);
1028 : 273235 : return true;
1029 : : }
1030 : :
1031 : :
1032 : : /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1033 : : bitmap. Returns true if all dependencies of INSN are known to be
1034 : : loop invariants, false otherwise. */
1035 : :
1036 : : static bool
1037 : 6428550 : check_dependencies (rtx_insn *insn, bitmap depends_on)
1038 : : {
1039 : 6428550 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1040 : 6428550 : df_ref use;
1041 : 6428550 : basic_block bb = BLOCK_FOR_INSN (insn);
1042 : :
1043 : 7765234 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1044 : 6507091 : if (!check_dependency (bb, use, depends_on))
1045 : : return false;
1046 : 1389137 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1047 : 130994 : if (!check_dependency (bb, use, depends_on))
1048 : : return false;
1049 : :
1050 : : return true;
1051 : : }
1052 : :
1053 : : /* Pre-check candidate DEST to skip the one which cannot make a valid insn
1054 : : during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1055 : : static bool
1056 : 10714997 : pre_check_invariant_p (bool simple, rtx dest)
1057 : : {
1058 : 10714997 : if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1059 : : {
1060 : 2501418 : df_ref use;
1061 : 2501418 : unsigned int i = REGNO (dest);
1062 : 2501418 : struct df_insn_info *insn_info;
1063 : 2501418 : df_ref def_rec;
1064 : :
1065 : 11144375 : for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1066 : : {
1067 : 10418801 : rtx_insn *ref = DF_REF_INSN (use);
1068 : 10418801 : insn_info = DF_INSN_INFO_GET (ref);
1069 : :
1070 : 18509119 : FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1071 : 9866162 : if (DF_REF_REGNO (def_rec) == i)
1072 : : {
1073 : : /* Multi definitions at this stage, most likely are due to
1074 : : instruction constraints, which requires both read and write
1075 : : on the same register. Since move_invariant_reg is not
1076 : : powerful enough to handle such cases, just ignore the INV
1077 : : and leave the chance to others. */
1078 : : return false;
1079 : : }
1080 : : }
1081 : : }
1082 : : return true;
1083 : : }
1084 : :
1085 : : /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
1086 : : executed. ALWAYS_EXECUTED is true if the insn is always executed,
1087 : : unless the program ends due to a function call. */
1088 : :
1089 : : static void
1090 : 14589678 : find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1091 : : {
1092 : 14589678 : df_ref ref;
1093 : 14589678 : struct def *def;
1094 : 14589678 : bitmap depends_on;
1095 : 14589678 : rtx set, dest;
1096 : 14589678 : bool simple = true;
1097 : 14589678 : struct invariant *inv;
1098 : :
1099 : : /* Jumps have control flow side-effects. */
1100 : 14589678 : if (JUMP_P (insn))
1101 : : return;
1102 : :
1103 : 12893060 : set = single_set (insn);
1104 : 12893060 : if (!set)
1105 : : return;
1106 : 12544563 : dest = SET_DEST (set);
1107 : :
1108 : 12544563 : if (!REG_P (dest)
1109 : 12544563 : || HARD_REGISTER_P (dest))
1110 : : simple = false;
1111 : :
1112 : 12544563 : if (!may_assign_reg_p (dest)
1113 : 10714997 : || !pre_check_invariant_p (simple, dest)
1114 : 21483716 : || !check_maybe_invariant (SET_SRC (set)))
1115 : : return;
1116 : :
1117 : : /* If the insn can throw exception, we cannot move it at all without changing
1118 : : cfg. */
1119 : 7030329 : if (can_throw_internal (insn))
1120 : : return;
1121 : :
1122 : : /* We cannot make trapping insn executed, unless it was executed before. */
1123 : 7023144 : if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1124 : : return;
1125 : :
1126 : 6428550 : depends_on = BITMAP_ALLOC (NULL);
1127 : 6428550 : if (!check_dependencies (insn, depends_on))
1128 : : {
1129 : 5170407 : BITMAP_FREE (depends_on);
1130 : 5170407 : return;
1131 : : }
1132 : :
1133 : 1258143 : if (simple)
1134 : 606179 : def = XCNEW (struct def);
1135 : : else
1136 : : def = NULL;
1137 : :
1138 : 1258143 : inv = create_new_invariant (def, insn, depends_on, always_executed);
1139 : :
1140 : 1258143 : if (simple)
1141 : : {
1142 : 606179 : ref = df_find_def (insn, dest);
1143 : 606179 : check_invariant_table_size ();
1144 : 606179 : invariant_table[DF_REF_ID (ref)] = inv;
1145 : : }
1146 : : }
1147 : :
1148 : : /* Record registers used in INSN that have a unique invariant definition. */
1149 : :
1150 : : static void
1151 : 14589678 : record_uses (rtx_insn *insn)
1152 : : {
1153 : 14589678 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1154 : 14589678 : df_ref use;
1155 : 14589678 : struct invariant *inv;
1156 : :
1157 : 35106431 : FOR_EACH_INSN_INFO_USE (use, insn_info)
1158 : : {
1159 : 20516753 : inv = invariant_for_use (use);
1160 : 20516753 : if (inv)
1161 : 635696 : record_use (inv->def, use);
1162 : : }
1163 : 15019371 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1164 : : {
1165 : 429693 : inv = invariant_for_use (use);
1166 : 429693 : if (inv)
1167 : 723 : record_use (inv->def, use);
1168 : : }
1169 : 14589678 : }
1170 : :
1171 : : /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
1172 : : executed. ALWAYS_EXECUTED is true if the insn is always executed,
1173 : : unless the program ends due to a function call. */
1174 : :
1175 : : static void
1176 : 14589678 : find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1177 : : {
1178 : 0 : find_invariant_insn (insn, always_reached, always_executed);
1179 : 14589678 : record_uses (insn);
1180 : 0 : }
1181 : :
1182 : : /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1183 : : basic block is always executed. ALWAYS_EXECUTED is true if the basic
1184 : : block is always executed, unless the program ends due to a function
1185 : : call. */
1186 : :
1187 : : static void
1188 : 3718001 : find_invariants_bb (class loop *loop, basic_block bb, bool always_reached,
1189 : : bool always_executed)
1190 : : {
1191 : 3718001 : rtx_insn *insn;
1192 : 3718001 : basic_block preheader = loop_preheader_edge (loop)->src;
1193 : :
1194 : : /* Don't move insn of cold BB out of loop to preheader to reduce calculations
1195 : : and register live range in hot loop with cold BB. */
1196 : 3718001 : if (!always_executed && preheader->count > bb->count)
1197 : : {
1198 : 586574 : if (dump_file)
1199 : 2 : fprintf (dump_file, "Don't move invariant from bb: %d out of loop %d\n",
1200 : : bb->index, loop->num);
1201 : 586574 : return;
1202 : : }
1203 : :
1204 : 34351064 : FOR_BB_INSNS (bb, insn)
1205 : : {
1206 : 31219637 : if (!NONDEBUG_INSN_P (insn))
1207 : 16629959 : continue;
1208 : :
1209 : 14589678 : find_invariants_insn (insn, always_reached, always_executed);
1210 : :
1211 : 14589678 : if (always_reached
1212 : 3636920 : && CALL_P (insn)
1213 : 14699841 : && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1214 : 109665 : || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1215 : : always_reached = false;
1216 : : }
1217 : : }
1218 : :
1219 : : /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1220 : : basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1221 : : bitmap of basic blocks in BODY that are always executed unless the program
1222 : : ends due to a function call. */
1223 : :
1224 : : static void
1225 : 601647 : find_invariants_body (class loop *loop, basic_block *body,
1226 : : bitmap always_reached, bitmap always_executed)
1227 : : {
1228 : 601647 : unsigned i;
1229 : :
1230 : 4319648 : for (i = 0; i < loop->num_nodes; i++)
1231 : 3718001 : find_invariants_bb (loop, body[i], bitmap_bit_p (always_reached, i),
1232 : 3718001 : bitmap_bit_p (always_executed, i));
1233 : 601647 : }
1234 : :
1235 : : /* Finds invariants in LOOP. */
1236 : :
1237 : : static void
1238 : 601647 : find_invariants (class loop *loop)
1239 : : {
1240 : 601647 : auto_bitmap may_exit;
1241 : 601647 : auto_bitmap always_reached;
1242 : 601647 : auto_bitmap has_exit;
1243 : 601647 : auto_bitmap always_executed;
1244 : 601647 : basic_block *body = get_loop_body_in_dom_order (loop);
1245 : :
1246 : 601647 : find_exits (loop, body, may_exit, has_exit);
1247 : 601647 : compute_always_reached (loop, body, may_exit, always_reached);
1248 : 601647 : compute_always_reached (loop, body, has_exit, always_executed);
1249 : :
1250 : 601647 : find_defs (loop);
1251 : 601647 : find_invariants_body (loop, body, always_reached, always_executed);
1252 : 601647 : merge_identical_invariants ();
1253 : :
1254 : 601647 : free (body);
1255 : 601647 : }
1256 : :
1257 : : /* Frees a list of uses USE. */
1258 : :
1259 : : static void
1260 : 606179 : free_use_list (struct use *use)
1261 : : {
1262 : 606179 : struct use *next;
1263 : :
1264 : 1242598 : for (; use; use = next)
1265 : : {
1266 : 636419 : next = use->next;
1267 : 636419 : free (use);
1268 : : }
1269 : 0 : }
1270 : :
1271 : : /* Return pressure class and number of hard registers (through *NREGS)
1272 : : for destination of INSN. */
1273 : : static enum reg_class
1274 : 15 : get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1275 : : {
1276 : 15 : rtx reg;
1277 : 15 : enum reg_class pressure_class;
1278 : 15 : rtx set = single_set (insn);
1279 : :
1280 : : /* Considered invariant insns have only one set. */
1281 : 15 : gcc_assert (set != NULL_RTX);
1282 : 15 : reg = SET_DEST (set);
1283 : 15 : if (GET_CODE (reg) == SUBREG)
1284 : 0 : reg = SUBREG_REG (reg);
1285 : 15 : if (MEM_P (reg))
1286 : : {
1287 : 0 : *nregs = 0;
1288 : 0 : pressure_class = NO_REGS;
1289 : : }
1290 : : else
1291 : : {
1292 : 15 : if (! REG_P (reg))
1293 : : reg = NULL_RTX;
1294 : 15 : if (reg == NULL_RTX)
1295 : : pressure_class = GENERAL_REGS;
1296 : : else
1297 : : {
1298 : 15 : pressure_class = reg_allocno_class (REGNO (reg));
1299 : 15 : pressure_class = ira_pressure_class_translate[pressure_class];
1300 : : }
1301 : 15 : *nregs
1302 : 15 : = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1303 : : }
1304 : 15 : return pressure_class;
1305 : : }
1306 : :
1307 : : /* Calculates cost and number of registers needed for moving invariant INV
1308 : : out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1309 : : the REG_CLASS of INV. Return
1310 : : -1: if INV is invalid.
1311 : : 0: if INV and its depends_on have same reg_class
1312 : : 1: if INV and its depends_on have different reg_classes. */
1313 : :
1314 : : static int
1315 : 2494176 : get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1316 : : enum reg_class *cl)
1317 : : {
1318 : 2494176 : int i, acomp_cost;
1319 : 2494176 : unsigned aregs_needed[N_REG_CLASSES];
1320 : 2494176 : unsigned depno;
1321 : 2494176 : struct invariant *dep;
1322 : 2494176 : bitmap_iterator bi;
1323 : 2494176 : int ret = 1;
1324 : :
1325 : : /* Find the representative of the class of the equivalent invariants. */
1326 : 2494176 : inv = invariants[inv->eqto];
1327 : :
1328 : 2494176 : *comp_cost = 0;
1329 : 2494176 : if (! flag_ira_loop_pressure)
1330 : 2494161 : regs_needed[0] = 0;
1331 : : else
1332 : : {
1333 : 75 : for (i = 0; i < ira_pressure_classes_num; i++)
1334 : 60 : regs_needed[ira_pressure_classes[i]] = 0;
1335 : : }
1336 : :
1337 : 2494176 : if (inv->move
1338 : 2491105 : || inv->stamp == actual_stamp)
1339 : : return -1;
1340 : 2489332 : inv->stamp = actual_stamp;
1341 : :
1342 : 2489332 : if (! flag_ira_loop_pressure)
1343 : 2489317 : regs_needed[0]++;
1344 : : else
1345 : : {
1346 : 15 : int nregs;
1347 : 15 : enum reg_class pressure_class;
1348 : :
1349 : 15 : pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1350 : 15 : regs_needed[pressure_class] += nregs;
1351 : 15 : *cl = pressure_class;
1352 : 15 : ret = 0;
1353 : : }
1354 : :
1355 : 2489332 : if (!inv->cheap_address
1356 : 994243 : || inv->def->n_uses == 0
1357 : 789585 : || inv->def->n_addr_uses < inv->def->n_uses
1358 : : /* Count cost if the inv can't be propagated into address uses. */
1359 : 71441 : || !inv->def->can_prop_to_addr_uses)
1360 : 2425670 : (*comp_cost) += inv->cost * inv->eqno;
1361 : :
1362 : : #ifdef STACK_REGS
1363 : 2489332 : {
1364 : : /* Hoisting constant pool constants into stack regs may cost more than
1365 : : just single register. On x87, the balance is affected both by the
1366 : : small number of FP registers, and by its register stack organization,
1367 : : that forces us to add compensation code in and around the loop to
1368 : : shuffle the operands to the top of stack before use, and pop them
1369 : : from the stack after the loop finishes.
1370 : :
1371 : : To model this effect, we increase the number of registers needed for
1372 : : stack registers by two: one register push, and one register pop.
1373 : : This usually has the effect that FP constant loads from the constant
1374 : : pool are not moved out of the loop.
1375 : :
1376 : : Note that this also means that dependent invariants cannot be moved.
1377 : : However, the primary purpose of this pass is to move loop invariant
1378 : : address arithmetic out of loops, and address arithmetic that depends
1379 : : on floating point constants is unlikely to ever occur. */
1380 : 2489332 : rtx set = single_set (inv->insn);
1381 : 2489332 : if (set
1382 : 2489332 : && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1383 : 2500972 : && constant_pool_constant_p (SET_SRC (set)))
1384 : : {
1385 : 7441 : if (flag_ira_loop_pressure)
1386 : 0 : regs_needed[ira_stack_reg_pressure_class] += 2;
1387 : : else
1388 : 7441 : regs_needed[0] += 2;
1389 : : }
1390 : : }
1391 : : #endif
1392 : :
1393 : 3068362 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1394 : : {
1395 : 579030 : bool check_p;
1396 : 579030 : enum reg_class dep_cl = ALL_REGS;
1397 : 579030 : int dep_ret;
1398 : :
1399 : 579030 : dep = invariants[depno];
1400 : :
1401 : : /* If DEP is moved out of the loop, it is not a depends_on any more. */
1402 : 579030 : if (dep->move)
1403 : 89326 : continue;
1404 : :
1405 : 489704 : dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1406 : :
1407 : 489704 : if (! flag_ira_loop_pressure)
1408 : 489704 : check_p = aregs_needed[0] != 0;
1409 : : else
1410 : : {
1411 : 0 : for (i = 0; i < ira_pressure_classes_num; i++)
1412 : 0 : if (aregs_needed[ira_pressure_classes[i]] != 0)
1413 : : break;
1414 : 0 : check_p = i < ira_pressure_classes_num;
1415 : :
1416 : 0 : if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1417 : : {
1418 : 0 : *cl = ALL_REGS;
1419 : 0 : ret = 1;
1420 : : }
1421 : : }
1422 : 489704 : if (check_p
1423 : : /* We need to check always_executed, since if the original value of
1424 : : the invariant may be preserved, we may need to keep it in a
1425 : : separate register. TODO check whether the register has an
1426 : : use outside of the loop. */
1427 : 484860 : && dep->always_executed
1428 : 155456 : && !dep->def->uses->next)
1429 : : {
1430 : : /* If this is a single use, after moving the dependency we will not
1431 : : need a new register. */
1432 : 94936 : if (! flag_ira_loop_pressure)
1433 : 94936 : aregs_needed[0]--;
1434 : : else
1435 : : {
1436 : 0 : int nregs;
1437 : 0 : enum reg_class pressure_class;
1438 : :
1439 : 0 : pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1440 : 0 : aregs_needed[pressure_class] -= nregs;
1441 : : }
1442 : : }
1443 : :
1444 : 489704 : if (! flag_ira_loop_pressure)
1445 : 489704 : regs_needed[0] += aregs_needed[0];
1446 : : else
1447 : : {
1448 : 0 : for (i = 0; i < ira_pressure_classes_num; i++)
1449 : 0 : regs_needed[ira_pressure_classes[i]]
1450 : 0 : += aregs_needed[ira_pressure_classes[i]];
1451 : : }
1452 : 489704 : (*comp_cost) += acomp_cost;
1453 : : }
1454 : : return ret;
1455 : : }
1456 : :
1457 : : /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1458 : : of registers used in the loop, NEW_REGS is the number of new variables
1459 : : already added due to the invariant motion. The number of registers needed
1460 : : for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1461 : : through to estimate_reg_pressure_cost. */
1462 : :
1463 : : static int
1464 : 2004472 : gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1465 : : unsigned *new_regs, unsigned regs_used,
1466 : : bool speed, bool call_p)
1467 : : {
1468 : 2004472 : int comp_cost, size_cost;
1469 : : /* Workaround -Wmaybe-uninitialized false positive during
1470 : : profiledbootstrap by initializing it. */
1471 : 2004472 : enum reg_class cl = NO_REGS;
1472 : 2004472 : int ret;
1473 : :
1474 : 2004472 : actual_stamp++;
1475 : :
1476 : 2004472 : ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1477 : :
1478 : 2004472 : if (! flag_ira_loop_pressure)
1479 : : {
1480 : 2004457 : size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1481 : : regs_used, speed, call_p)
1482 : 2004457 : - estimate_reg_pressure_cost (new_regs[0],
1483 : : regs_used, speed, call_p));
1484 : : }
1485 : 15 : else if (ret < 0)
1486 : : return -1;
1487 : 15 : else if ((ret == 0) && (cl == NO_REGS))
1488 : : /* Hoist it anyway since it does not impact register pressure. */
1489 : : return 1;
1490 : : else
1491 : : {
1492 : : int i;
1493 : : enum reg_class pressure_class;
1494 : :
1495 : 19 : for (i = 0; i < ira_pressure_classes_num; i++)
1496 : : {
1497 : 18 : pressure_class = ira_pressure_classes[i];
1498 : :
1499 : 18 : if (!reg_classes_intersect_p (pressure_class, cl))
1500 : 3 : continue;
1501 : :
1502 : 15 : if ((int) new_regs[pressure_class]
1503 : 15 : + (int) regs_needed[pressure_class]
1504 : 15 : + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1505 : 15 : + param_ira_loop_reserved_regs
1506 : 15 : > ira_class_hard_regs_num[pressure_class])
1507 : : break;
1508 : : }
1509 : 15 : if (i < ira_pressure_classes_num)
1510 : : /* There will be register pressure excess and we want not to
1511 : : make this loop invariant motion. All loop invariants with
1512 : : non-positive gains will be rejected in function
1513 : : find_invariants_to_move. Therefore we return the negative
1514 : : number here.
1515 : :
1516 : : One could think that this rejects also expensive loop
1517 : : invariant motions and this will hurt code performance.
1518 : : However numerous experiments with different heuristics
1519 : : taking invariant cost into account did not confirm this
1520 : : assumption. There are possible explanations for this
1521 : : result:
1522 : : o probably all expensive invariants were already moved out
1523 : : of the loop by PRE and gimple invariant motion pass.
1524 : : o expensive invariant execution will be hidden by insn
1525 : : scheduling or OOO processor hardware because usually such
1526 : : invariants have a lot of freedom to be executed
1527 : : out-of-order.
1528 : : Another reason for ignoring invariant cost vs spilling cost
1529 : : heuristics is also in difficulties to evaluate accurately
1530 : : spill cost at this stage. */
1531 : : return -1;
1532 : : else
1533 : : size_cost = 0;
1534 : : }
1535 : :
1536 : 2004458 : return comp_cost - size_cost;
1537 : : }
1538 : :
1539 : : /* Finds invariant with best gain for moving. Returns the gain, stores
1540 : : the invariant in *BEST and number of registers needed for it to
1541 : : *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1542 : : NEW_REGS is the number of new variables already added due to invariant
1543 : : motion. */
1544 : :
1545 : : static int
1546 : 476683 : best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1547 : : unsigned *new_regs, unsigned regs_used,
1548 : : bool speed, bool call_p)
1549 : : {
1550 : 476683 : struct invariant *inv;
1551 : 476683 : int i, gain = 0, again;
1552 : 476683 : unsigned aregs_needed[N_REG_CLASSES], invno;
1553 : :
1554 : 4177953 : FOR_EACH_VEC_ELT (invariants, invno, inv)
1555 : : {
1556 : 3701270 : if (inv->move)
1557 : 631533 : continue;
1558 : :
1559 : : /* Only consider the "representatives" of equivalent invariants. */
1560 : 3069737 : if (inv->eqto != inv->invno)
1561 : 1065265 : continue;
1562 : :
1563 : 2004472 : again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1564 : : speed, call_p);
1565 : 2004472 : if (again > gain)
1566 : : {
1567 : 339692 : gain = again;
1568 : 339692 : *best = inv;
1569 : 339692 : if (! flag_ira_loop_pressure)
1570 : 339691 : regs_needed[0] = aregs_needed[0];
1571 : : else
1572 : : {
1573 : 5 : for (i = 0; i < ira_pressure_classes_num; i++)
1574 : 4 : regs_needed[ira_pressure_classes[i]]
1575 : 4 : = aregs_needed[ira_pressure_classes[i]];
1576 : : }
1577 : : }
1578 : : }
1579 : :
1580 : 476683 : return gain;
1581 : : }
1582 : :
1583 : : /* Marks invariant INVNO and all its dependencies for moving. */
1584 : :
1585 : : static void
1586 : 325447 : set_move_mark (unsigned invno, int gain)
1587 : : {
1588 : 325447 : struct invariant *inv = invariants[invno];
1589 : 325447 : bitmap_iterator bi;
1590 : :
1591 : : /* Find the representative of the class of the equivalent invariants. */
1592 : 325447 : inv = invariants[inv->eqto];
1593 : :
1594 : 325447 : if (inv->move)
1595 : 3060 : return;
1596 : 322387 : inv->move = true;
1597 : :
1598 : 322387 : if (dump_file)
1599 : : {
1600 : 3 : if (gain >= 0)
1601 : 3 : fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1602 : : invno, gain);
1603 : : else
1604 : 0 : fprintf (dump_file, "Decided to move dependent invariant %d\n",
1605 : : invno);
1606 : 322387 : };
1607 : :
1608 : 400906 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1609 : : {
1610 : 78519 : set_move_mark (invno, -1);
1611 : : }
1612 : : }
1613 : :
1614 : : /* Determines which invariants to move. */
1615 : :
1616 : : static void
1617 : 601647 : find_invariants_to_move (bool speed, bool call_p)
1618 : : {
1619 : 601647 : int gain;
1620 : 601647 : unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1621 : 601647 : struct invariant *inv = NULL;
1622 : :
1623 : 601647 : if (!invariants.length ())
1624 : 371892 : return;
1625 : :
1626 : 229755 : if (flag_ira_loop_pressure)
1627 : : /* REGS_USED is actually never used when the flag is on. */
1628 : : regs_used = 0;
1629 : : else
1630 : : /* We do not really do a good job in estimating number of
1631 : : registers used; we put some initial bound here to stand for
1632 : : induction variables etc. that we do not detect. */
1633 : : {
1634 : 229754 : unsigned int n_regs = DF_REG_SIZE (df);
1635 : :
1636 : 229754 : regs_used = 2;
1637 : :
1638 : 126755522 : for (i = 0; i < n_regs; i++)
1639 : : {
1640 : 126525768 : if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1641 : : {
1642 : : /* This is a value that is used but not changed inside loop. */
1643 : 0 : regs_used++;
1644 : : }
1645 : : }
1646 : : }
1647 : :
1648 : 229755 : if (! flag_ira_loop_pressure)
1649 : 229754 : new_regs[0] = regs_needed[0] = 0;
1650 : : else
1651 : : {
1652 : 5 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
1653 : 4 : new_regs[ira_pressure_classes[i]] = 0;
1654 : : }
1655 : 953366 : while ((gain = best_gain_for_invariant (&inv, regs_needed,
1656 : : new_regs, regs_used,
1657 : 476683 : speed, call_p)) > 0)
1658 : : {
1659 : 246928 : set_move_mark (inv->invno, gain);
1660 : 246928 : if (! flag_ira_loop_pressure)
1661 : 246927 : new_regs[0] += regs_needed[0];
1662 : : else
1663 : : {
1664 : 5 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
1665 : 4 : new_regs[ira_pressure_classes[i]]
1666 : 4 : += regs_needed[ira_pressure_classes[i]];
1667 : : }
1668 : : }
1669 : : }
1670 : :
1671 : : /* Replace the uses, reached by the definition of invariant INV, by REG.
1672 : :
1673 : : IN_GROUP is nonzero if this is part of a group of changes that must be
1674 : : performed as a group. In that case, the changes will be stored. The
1675 : : function `apply_change_group' will validate and apply the changes. */
1676 : :
1677 : : static int
1678 : 235110 : replace_uses (struct invariant *inv, rtx reg, bool in_group)
1679 : : {
1680 : : /* Replace the uses we know to be dominated. It saves work for copy
1681 : : propagation, and also it is necessary so that dependent invariants
1682 : : are computed right. */
1683 : 235110 : if (inv->def)
1684 : : {
1685 : 229307 : struct use *use;
1686 : 441607 : for (use = inv->def->uses; use; use = use->next)
1687 : 212300 : validate_change (use->insn, use->pos, reg, true);
1688 : :
1689 : : /* If we aren't part of a larger group, apply the changes now. */
1690 : 229307 : if (!in_group)
1691 : 42758 : return apply_change_group ();
1692 : : }
1693 : :
1694 : : return 1;
1695 : : }
1696 : :
1697 : : /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1698 : : the block preceding its header. */
1699 : :
1700 : : static bool
1701 : 322387 : can_move_invariant_reg (class loop *loop, struct invariant *inv, rtx reg)
1702 : : {
1703 : 322387 : df_ref def, use;
1704 : 322387 : unsigned int dest_regno, defs_in_loop_count = 0;
1705 : 322387 : rtx_insn *insn = inv->insn;
1706 : 322387 : basic_block bb = BLOCK_FOR_INSN (inv->insn);
1707 : 322387 : auto_vec <rtx_insn *, 16> debug_insns_to_reset;
1708 : :
1709 : : /* We ignore hard register and memory access for cost and complexity reasons.
1710 : : Hard register are few at this stage and expensive to consider as they
1711 : : require building a separate data flow. Memory access would require using
1712 : : df_simulate_* and can_move_insns_across functions and is more complex. */
1713 : 322387 : if (!REG_P (reg) || HARD_REGISTER_P (reg))
1714 : : return false;
1715 : :
1716 : : /* Check whether the set is always executed. We could omit this condition if
1717 : : we know that the register is unused outside of the loop, but it does not
1718 : : seem worth finding out. */
1719 : 321597 : if (!inv->always_executed)
1720 : : return false;
1721 : :
1722 : : /* Check that all uses that would be dominated by def are already dominated
1723 : : by it. */
1724 : 143676 : dest_regno = REGNO (reg);
1725 : 359927 : for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1726 : : {
1727 : 218164 : rtx_insn *use_insn;
1728 : 218164 : basic_block use_bb;
1729 : :
1730 : 218164 : use_insn = DF_REF_INSN (use);
1731 : 218164 : use_bb = BLOCK_FOR_INSN (use_insn);
1732 : :
1733 : : /* Ignore instruction considered for moving. */
1734 : 218164 : if (use_insn == insn)
1735 : 11551 : continue;
1736 : :
1737 : : /* Don't consider uses outside loop. */
1738 : 218164 : if (!flow_bb_inside_loop_p (loop, use_bb))
1739 : 11551 : continue;
1740 : :
1741 : : /* Don't move if a use is not dominated by def in insn. */
1742 : 141222 : if ((use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1743 : 346340 : || !dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1744 : : {
1745 : 1921 : if (!DEBUG_INSN_P (use_insn))
1746 : 1913 : return false;
1747 : 8 : debug_insns_to_reset.safe_push (use_insn);
1748 : : }
1749 : : }
1750 : :
1751 : : /* Check for other defs. Any other def in the loop might reach a use
1752 : : currently reached by the def in insn. */
1753 : 284366 : for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1754 : : {
1755 : 149318 : basic_block def_bb = DF_REF_BB (def);
1756 : :
1757 : : /* Defs in exit block cannot reach a use they weren't already. */
1758 : 149318 : if (single_succ_p (def_bb))
1759 : : {
1760 : 45094 : basic_block def_bb_succ;
1761 : :
1762 : 45094 : def_bb_succ = single_succ (def_bb);
1763 : 45094 : if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1764 : 840 : continue;
1765 : : }
1766 : :
1767 : 148478 : if (++defs_in_loop_count > 1)
1768 : : return false;
1769 : : }
1770 : :
1771 : : /* Reset debug uses if a use is not dominated by def in insn. */
1772 : 405146 : for (auto use_insn : debug_insns_to_reset)
1773 : : {
1774 : 2 : INSN_VAR_LOCATION_LOC (use_insn) = gen_rtx_UNKNOWN_VAR_LOC ();
1775 : 2 : df_insn_rescan (use_insn);
1776 : : }
1777 : :
1778 : : return true;
1779 : 322387 : }
1780 : :
1781 : : /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1782 : : otherwise. */
1783 : :
1784 : : static bool
1785 : 1384433 : move_invariant_reg (class loop *loop, unsigned invno)
1786 : : {
1787 : 1384433 : struct invariant *inv = invariants[invno];
1788 : 1384433 : struct invariant *repr = invariants[inv->eqto];
1789 : 1384433 : unsigned i;
1790 : 1384433 : basic_block preheader = loop_preheader_edge (loop)->src;
1791 : 1384433 : rtx reg, set, dest, note;
1792 : 1384433 : bitmap_iterator bi;
1793 : 1384433 : int regno = -1;
1794 : :
1795 : 1384433 : if (inv->reg)
1796 : : return true;
1797 : 1258143 : if (!repr->move)
1798 : : return false;
1799 : :
1800 : : /* If this is a representative of the class of equivalent invariants,
1801 : : really move the invariant. Otherwise just replace its use with
1802 : : the register used for the representative. */
1803 : 370158 : if (inv == repr)
1804 : : {
1805 : 322387 : if (inv->depends_on)
1806 : : {
1807 : 400906 : EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1808 : : {
1809 : 78519 : if (!move_invariant_reg (loop, i))
1810 : 0 : goto fail;
1811 : : }
1812 : : }
1813 : :
1814 : : /* If possible, just move the set out of the loop. Otherwise, we
1815 : : need to create a temporary register. */
1816 : 322387 : set = single_set (inv->insn);
1817 : 322387 : reg = dest = SET_DEST (set);
1818 : 322387 : if (GET_CODE (reg) == SUBREG)
1819 : 32 : reg = SUBREG_REG (reg);
1820 : 322387 : if (REG_P (reg))
1821 : 322276 : regno = REGNO (reg);
1822 : :
1823 : 322387 : if (!can_move_invariant_reg (loop, inv, dest))
1824 : : {
1825 : 187339 : reg = gen_reg_rtx_and_attrs (dest);
1826 : :
1827 : : /* Try replacing the destination by a new pseudoregister. */
1828 : 187339 : validate_change (inv->insn, &SET_DEST (set), reg, true);
1829 : :
1830 : : /* As well as all the dominated uses. */
1831 : 187339 : replace_uses (inv, reg, true);
1832 : :
1833 : : /* And validate all the changes. */
1834 : 187339 : if (!apply_change_group ())
1835 : 43 : goto fail;
1836 : :
1837 : 187296 : emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1838 : : }
1839 : 135048 : else if (dump_file)
1840 : 1 : fprintf (dump_file, "Invariant %d moved without introducing a new "
1841 : : "temporary register\n", invno);
1842 : 322344 : if (JUMP_P (BB_END (preheader)))
1843 : 6 : preheader = split_edge (loop_preheader_edge (loop));
1844 : 322344 : reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1845 : 322344 : df_recompute_luids (preheader);
1846 : :
1847 : : /* If there is a REG_EQUAL note on the insn we just moved, and the
1848 : : insn is in a basic block that is not always executed or the note
1849 : : contains something for which we don't know the invariant status,
1850 : : the note may no longer be valid after we move the insn. Note that
1851 : : uses in REG_EQUAL notes are taken into account in the computation
1852 : : of invariants, so it is safe to retain the note even if it contains
1853 : : register references for which we know the invariant status. */
1854 : 322344 : if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1855 : 322344 : && (!inv->always_executed
1856 : 34120 : || !check_maybe_invariant (XEXP (note, 0))))
1857 : 25491 : remove_note (inv->insn, note);
1858 : : }
1859 : : else
1860 : : {
1861 : 47771 : if (!move_invariant_reg (loop, repr->invno))
1862 : 0 : goto fail;
1863 : 47771 : reg = repr->reg;
1864 : 47771 : regno = repr->orig_regno;
1865 : 47771 : if (!replace_uses (inv, reg, false))
1866 : 0 : goto fail;
1867 : 47771 : set = single_set (inv->insn);
1868 : 47771 : emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1869 : 47771 : delete_insn (inv->insn);
1870 : : }
1871 : :
1872 : 370115 : inv->reg = reg;
1873 : 370115 : inv->orig_regno = regno;
1874 : :
1875 : 370115 : return true;
1876 : :
1877 : 43 : fail:
1878 : : /* If we failed, clear move flag, so that we do not try to move inv
1879 : : again. */
1880 : 43 : if (dump_file)
1881 : 0 : fprintf (dump_file, "Failed to move invariant %d\n", invno);
1882 : 43 : inv->move = false;
1883 : 43 : inv->reg = NULL_RTX;
1884 : 43 : inv->orig_regno = -1;
1885 : :
1886 : 43 : return false;
1887 : : }
1888 : :
1889 : : /* Move selected invariant out of the LOOP. Newly created regs are marked
1890 : : in TEMPORARY_REGS. */
1891 : :
1892 : : static void
1893 : 601647 : move_invariants (class loop *loop)
1894 : : {
1895 : 601647 : struct invariant *inv;
1896 : 601647 : unsigned i;
1897 : :
1898 : 1859790 : FOR_EACH_VEC_ELT (invariants, i, inv)
1899 : 1258143 : move_invariant_reg (loop, i);
1900 : 601647 : if (flag_ira_loop_pressure && resize_reg_info ())
1901 : : {
1902 : 9 : FOR_EACH_VEC_ELT (invariants, i, inv)
1903 : 8 : if (inv->reg != NULL_RTX)
1904 : : {
1905 : 1 : if (inv->orig_regno >= 0)
1906 : 1 : setup_reg_classes (REGNO (inv->reg),
1907 : : reg_preferred_class (inv->orig_regno),
1908 : : reg_alternate_class (inv->orig_regno),
1909 : : reg_allocno_class (inv->orig_regno));
1910 : : else
1911 : 0 : setup_reg_classes (REGNO (inv->reg),
1912 : : GENERAL_REGS, NO_REGS, GENERAL_REGS);
1913 : : }
1914 : : }
1915 : : /* Remove the DF_UD_CHAIN problem added in find_defs before rescanning,
1916 : : to save a bit of compile time. */
1917 : 601647 : df_remove_problem (df_chain);
1918 : 601647 : df_process_deferred_rescans ();
1919 : 601647 : }
1920 : :
1921 : : /* Initializes invariant motion data. */
1922 : :
1923 : : static void
1924 : 601647 : init_inv_motion_data (void)
1925 : : {
1926 : 601647 : actual_stamp = 1;
1927 : :
1928 : 601647 : invariants.create (100);
1929 : 601647 : }
1930 : :
1931 : : /* Frees the data allocated by invariant motion. */
1932 : :
1933 : : static void
1934 : 601647 : free_inv_motion_data (void)
1935 : : {
1936 : 601647 : unsigned i;
1937 : 601647 : struct def *def;
1938 : 601647 : struct invariant *inv;
1939 : :
1940 : 601647 : check_invariant_table_size ();
1941 : 78688613 : for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1942 : : {
1943 : 77485319 : inv = invariant_table[i];
1944 : 77485319 : if (inv)
1945 : : {
1946 : 606179 : def = inv->def;
1947 : 606179 : gcc_assert (def != NULL);
1948 : :
1949 : 606179 : free_use_list (def->uses);
1950 : 606179 : free (def);
1951 : 606179 : invariant_table[i] = NULL;
1952 : : }
1953 : : }
1954 : :
1955 : 1859790 : FOR_EACH_VEC_ELT (invariants, i, inv)
1956 : : {
1957 : 1258143 : BITMAP_FREE (inv->depends_on);
1958 : 1258143 : free (inv);
1959 : : }
1960 : 601647 : invariants.release ();
1961 : 601647 : }
1962 : :
1963 : : /* Move the invariants out of the LOOP. */
1964 : :
1965 : : static void
1966 : 601647 : move_single_loop_invariants (class loop *loop)
1967 : : {
1968 : 601647 : init_inv_motion_data ();
1969 : :
1970 : 601647 : find_invariants (loop);
1971 : 601647 : find_invariants_to_move (optimize_loop_for_speed_p (loop),
1972 : 601647 : LOOP_DATA (loop)->has_call);
1973 : 601647 : move_invariants (loop);
1974 : :
1975 : 601647 : free_inv_motion_data ();
1976 : 601647 : }
1977 : :
1978 : : /* Releases the auxiliary data for LOOP. */
1979 : :
1980 : : static void
1981 : 601647 : free_loop_data (class loop *loop)
1982 : : {
1983 : 601647 : class loop_data *data = LOOP_DATA (loop);
1984 : 601647 : if (!data)
1985 : : return;
1986 : :
1987 : 601647 : bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1988 : 601647 : bitmap_clear (&LOOP_DATA (loop)->regs_live);
1989 : 601647 : free (data);
1990 : 601647 : loop->aux = NULL;
1991 : : }
1992 : :
1993 : :
1994 : :
1995 : : /* Registers currently living. */
1996 : : static bitmap_head curr_regs_live;
1997 : :
1998 : : /* Current reg pressure for each pressure class. */
1999 : : static int curr_reg_pressure[N_REG_CLASSES];
2000 : :
2001 : : /* Record all regs that are set in any one insn. Communication from
2002 : : mark_reg_{store,clobber} and global_conflicts. Asm can refer to
2003 : : all hard-registers. */
2004 : : static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
2005 : : ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
2006 : : /* Number of regs stored in the previous array. */
2007 : : static int n_regs_set;
2008 : :
2009 : : /* Return pressure class and number of needed hard registers (through
2010 : : *NREGS) of register REGNO. */
2011 : : static enum reg_class
2012 : 137 : get_regno_pressure_class (int regno, int *nregs)
2013 : : {
2014 : 137 : if (regno >= FIRST_PSEUDO_REGISTER)
2015 : : {
2016 : 82 : enum reg_class pressure_class;
2017 : :
2018 : 82 : pressure_class = reg_allocno_class (regno);
2019 : 82 : pressure_class = ira_pressure_class_translate[pressure_class];
2020 : 82 : *nregs
2021 : 82 : = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
2022 : 82 : return pressure_class;
2023 : : }
2024 : 55 : else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
2025 : 55 : && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
2026 : : {
2027 : 12 : *nregs = 1;
2028 : 12 : return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
2029 : : }
2030 : : else
2031 : : {
2032 : 43 : *nregs = 0;
2033 : 43 : return NO_REGS;
2034 : : }
2035 : : }
2036 : :
2037 : : /* Increase (if INCR_P) or decrease current register pressure for
2038 : : register REGNO. */
2039 : : static void
2040 : 134 : change_pressure (int regno, bool incr_p)
2041 : : {
2042 : 134 : int nregs;
2043 : 134 : enum reg_class pressure_class;
2044 : :
2045 : 134 : pressure_class = get_regno_pressure_class (regno, &nregs);
2046 : 134 : if (! incr_p)
2047 : 32 : curr_reg_pressure[pressure_class] -= nregs;
2048 : : else
2049 : : {
2050 : 102 : curr_reg_pressure[pressure_class] += nregs;
2051 : 102 : if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2052 : : < curr_reg_pressure[pressure_class])
2053 : 20 : LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2054 : 20 : = curr_reg_pressure[pressure_class];
2055 : : }
2056 : 134 : }
2057 : :
2058 : : /* Mark REGNO birth. */
2059 : : static void
2060 : 48 : mark_regno_live (int regno)
2061 : : {
2062 : 48 : class loop *loop;
2063 : :
2064 : 48 : for (loop = curr_loop;
2065 : 96 : loop != current_loops->tree_root;
2066 : 48 : loop = loop_outer (loop))
2067 : 48 : bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2068 : 48 : if (!bitmap_set_bit (&curr_regs_live, regno))
2069 : : return;
2070 : 37 : change_pressure (regno, true);
2071 : : }
2072 : :
2073 : : /* Mark REGNO death. */
2074 : : static void
2075 : 42 : mark_regno_death (int regno)
2076 : : {
2077 : 42 : if (! bitmap_clear_bit (&curr_regs_live, regno))
2078 : : return;
2079 : 32 : change_pressure (regno, false);
2080 : : }
2081 : :
2082 : : /* Mark setting register REG. */
2083 : : static void
2084 : 53 : mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2085 : : void *data ATTRIBUTE_UNUSED)
2086 : : {
2087 : 53 : if (GET_CODE (reg) == SUBREG)
2088 : 0 : reg = SUBREG_REG (reg);
2089 : :
2090 : 53 : if (! REG_P (reg))
2091 : : return;
2092 : :
2093 : 48 : regs_set[n_regs_set++] = reg;
2094 : :
2095 : 48 : unsigned int end_regno = END_REGNO (reg);
2096 : 96 : for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2097 : 48 : mark_regno_live (regno);
2098 : : }
2099 : :
2100 : : /* Mark clobbering register REG. */
2101 : : static void
2102 : 43 : mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2103 : : {
2104 : 43 : if (GET_CODE (setter) == CLOBBER)
2105 : 10 : mark_reg_store (reg, setter, data);
2106 : 43 : }
2107 : :
2108 : : /* Mark register REG death. */
2109 : : static void
2110 : 42 : mark_reg_death (rtx reg)
2111 : : {
2112 : 42 : unsigned int end_regno = END_REGNO (reg);
2113 : 84 : for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2114 : 42 : mark_regno_death (regno);
2115 : 42 : }
2116 : :
2117 : : /* Mark occurrence of registers in X for the current loop. */
2118 : : static void
2119 : 197 : mark_ref_regs (rtx x)
2120 : : {
2121 : 197 : RTX_CODE code;
2122 : 197 : int i;
2123 : 197 : const char *fmt;
2124 : :
2125 : 197 : if (!x)
2126 : : return;
2127 : :
2128 : 197 : code = GET_CODE (x);
2129 : 197 : if (code == REG)
2130 : : {
2131 : 82 : class loop *loop;
2132 : :
2133 : 82 : for (loop = curr_loop;
2134 : 164 : loop != current_loops->tree_root;
2135 : 82 : loop = loop_outer (loop))
2136 : 82 : bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2137 : : return;
2138 : : }
2139 : :
2140 : 115 : fmt = GET_RTX_FORMAT (code);
2141 : 305 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2142 : 190 : if (fmt[i] == 'e')
2143 : 143 : mark_ref_regs (XEXP (x, i));
2144 : 47 : else if (fmt[i] == 'E')
2145 : : {
2146 : : int j;
2147 : :
2148 : 30 : for (j = 0; j < XVECLEN (x, i); j++)
2149 : 20 : mark_ref_regs (XVECEXP (x, i, j));
2150 : : }
2151 : : }
2152 : :
2153 : : /* Calculate register pressure in the loops. */
2154 : : static void
2155 : 1 : calculate_loop_reg_pressure (void)
2156 : : {
2157 : 1 : int i;
2158 : 1 : unsigned int j;
2159 : 1 : bitmap_iterator bi;
2160 : 1 : basic_block bb;
2161 : 1 : rtx_insn *insn;
2162 : 1 : rtx link;
2163 : 1 : class loop *parent;
2164 : :
2165 : 4 : for (auto loop : loops_list (cfun, 0))
2166 : 1 : if (loop->aux == NULL)
2167 : : {
2168 : 1 : loop->aux = xcalloc (1, sizeof (class loop_data));
2169 : 1 : bitmap_initialize (&LOOP_DATA (loop)->regs_ref, ®_obstack);
2170 : 1 : bitmap_initialize (&LOOP_DATA (loop)->regs_live, ®_obstack);
2171 : 1 : }
2172 : 1 : ira_setup_eliminable_regset ();
2173 : 1 : bitmap_initialize (&curr_regs_live, ®_obstack);
2174 : 9 : FOR_EACH_BB_FN (bb, cfun)
2175 : : {
2176 : 8 : curr_loop = bb->loop_father;
2177 : 8 : if (curr_loop == current_loops->tree_root)
2178 : 4 : continue;
2179 : :
2180 : 4 : for (class loop *loop = curr_loop;
2181 : 8 : loop != current_loops->tree_root;
2182 : 4 : loop = loop_outer (loop))
2183 : 8 : bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2184 : :
2185 : 4 : bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2186 : 24 : for (i = 0; i < ira_pressure_classes_num; i++)
2187 : 16 : curr_reg_pressure[ira_pressure_classes[i]] = 0;
2188 : 69 : EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2189 : 65 : change_pressure (j, true);
2190 : :
2191 : 45 : FOR_BB_INSNS (bb, insn)
2192 : : {
2193 : 41 : if (! NONDEBUG_INSN_P (insn))
2194 : 7 : continue;
2195 : :
2196 : 34 : mark_ref_regs (PATTERN (insn));
2197 : 34 : n_regs_set = 0;
2198 : 34 : note_stores (insn, mark_reg_clobber, NULL);
2199 : :
2200 : : /* Mark any registers dead after INSN as dead now. */
2201 : :
2202 : 78 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2203 : 44 : if (REG_NOTE_KIND (link) == REG_DEAD)
2204 : 22 : mark_reg_death (XEXP (link, 0));
2205 : :
2206 : : /* Mark any registers set in INSN as live,
2207 : : and mark them as conflicting with all other live regs.
2208 : : Clobbers are processed again, so they conflict with
2209 : : the registers that are set. */
2210 : :
2211 : 34 : note_stores (insn, mark_reg_store, NULL);
2212 : :
2213 : 34 : if (AUTO_INC_DEC)
2214 : : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2215 : : if (REG_NOTE_KIND (link) == REG_INC)
2216 : : mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2217 : :
2218 : 116 : while (n_regs_set-- > 0)
2219 : : {
2220 : 96 : rtx note = find_regno_note (insn, REG_UNUSED,
2221 : 48 : REGNO (regs_set[n_regs_set]));
2222 : 48 : if (! note)
2223 : 28 : continue;
2224 : :
2225 : 20 : mark_reg_death (XEXP (note, 0));
2226 : : }
2227 : : }
2228 : : }
2229 : 1 : bitmap_release (&curr_regs_live);
2230 : 1 : if (flag_ira_region == IRA_REGION_MIXED
2231 : 1 : || flag_ira_region == IRA_REGION_ALL)
2232 : 4 : for (auto loop : loops_list (cfun, 0))
2233 : : {
2234 : 41 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2235 : 40 : if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2236 : : {
2237 : 3 : enum reg_class pressure_class;
2238 : 3 : int nregs;
2239 : :
2240 : 3 : pressure_class = get_regno_pressure_class (j, &nregs);
2241 : 3 : LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2242 : : }
2243 : 1 : }
2244 : 1 : if (dump_file == NULL)
2245 : 0 : return;
2246 : 4 : for (auto loop : loops_list (cfun, 0))
2247 : : {
2248 : 1 : parent = loop_outer (loop);
2249 : 2 : fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2250 : : loop->num, (parent == NULL ? -1 : parent->num),
2251 : 1 : loop->header->index, loop_depth (loop));
2252 : 1 : fprintf (dump_file, "\n ref. regnos:");
2253 : 38 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2254 : 37 : fprintf (dump_file, " %d", j);
2255 : 1 : fprintf (dump_file, "\n live regnos:");
2256 : 41 : EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2257 : 40 : fprintf (dump_file, " %d", j);
2258 : 1 : fprintf (dump_file, "\n Pressure:");
2259 : 5 : for (i = 0; (int) i < ira_pressure_classes_num; i++)
2260 : : {
2261 : 4 : enum reg_class pressure_class;
2262 : :
2263 : 4 : pressure_class = ira_pressure_classes[i];
2264 : 4 : if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2265 : 2 : continue;
2266 : 2 : fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2267 : : LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2268 : : }
2269 : 1 : fprintf (dump_file, "\n");
2270 : 1 : }
2271 : : }
2272 : :
2273 : :
2274 : :
2275 : : /* Move the invariants out of the loops. */
2276 : :
2277 : : void
2278 : 229199 : move_loop_invariants (void)
2279 : : {
2280 : 229199 : if (optimize == 1)
2281 : 15080 : df_live_add_problem ();
2282 : : /* ??? This is a hack. We should only need to call df_live_set_all_dirty
2283 : : for optimize == 1, but can_move_invariant_reg relies on DF_INSN_LUID
2284 : : being up-to-date. That isn't always true (even after df_analyze)
2285 : : because df_process_deferred_rescans doesn't necessarily cause
2286 : : blocks to be rescanned. */
2287 : 229199 : df_live_set_all_dirty ();
2288 : 229199 : if (flag_ira_loop_pressure)
2289 : : {
2290 : 1 : df_analyze ();
2291 : 1 : regstat_init_n_sets_and_refs ();
2292 : 1 : ira_set_pseudo_classes (true, dump_file);
2293 : 1 : calculate_loop_reg_pressure ();
2294 : 1 : regstat_free_n_sets_and_refs ();
2295 : : }
2296 : 229199 : df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2297 : : /* Process the loops, innermost first. */
2298 : 1289244 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
2299 : : {
2300 : 601647 : curr_loop = loop;
2301 : : /* move_single_loop_invariants for very large loops is time consuming
2302 : : and might need a lot of memory. For -O1 only do loop invariant
2303 : : motion for very small loops. */
2304 : 601647 : unsigned max_bbs = param_loop_invariant_max_bbs_in_loop;
2305 : 601647 : if (optimize < 2)
2306 : 40091 : max_bbs /= 10;
2307 : 601647 : if (loop->num_nodes <= max_bbs)
2308 : 601647 : move_single_loop_invariants (loop);
2309 : 229199 : }
2310 : :
2311 : 1289244 : for (auto loop : loops_list (cfun, 0))
2312 : 601647 : free_loop_data (loop);
2313 : :
2314 : 229199 : if (flag_ira_loop_pressure)
2315 : : /* There is no sense to keep this info because it was most
2316 : : probably outdated by subsequent passes. */
2317 : 1 : free_reg_info ();
2318 : 229199 : free (invariant_table);
2319 : 229199 : invariant_table = NULL;
2320 : 229199 : invariant_table_size = 0;
2321 : :
2322 : 229199 : if (optimize == 1)
2323 : 15080 : df_remove_problem (df_live);
2324 : :
2325 : 229199 : checking_verify_flow_info ();
2326 : 229199 : }
|
