Daily bump.
[official-gcc.git] / gcc / loop-invariant.c
blobe3b560d683cd254039299596ed96a6ff354e10c3
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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.c or in tree-ssa-pre.c.
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").
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.
34 Then we move the selected invariants out of the loop, creating a new
35 temporaries for them if necessary. */
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "tm.h"
41 #include "hard-reg-set.h"
42 #include "rtl.h"
43 #include "tm_p.h"
44 #include "obstack.h"
45 #include "predict.h"
46 #include "vec.h"
47 #include "hashtab.h"
48 #include "hash-set.h"
49 #include "machmode.h"
50 #include "input.h"
51 #include "function.h"
52 #include "dominance.h"
53 #include "cfg.h"
54 #include "cfgrtl.h"
55 #include "basic-block.h"
56 #include "cfgloop.h"
57 #include "symtab.h"
58 #include "flags.h"
59 #include "statistics.h"
60 #include "double-int.h"
61 #include "real.h"
62 #include "fixed-value.h"
63 #include "alias.h"
64 #include "wide-int.h"
65 #include "inchash.h"
66 #include "tree.h"
67 #include "insn-config.h"
68 #include "expmed.h"
69 #include "dojump.h"
70 #include "explow.h"
71 #include "calls.h"
72 #include "emit-rtl.h"
73 #include "varasm.h"
74 #include "stmt.h"
75 #include "expr.h"
76 #include "recog.h"
77 #include "target.h"
78 #include "df.h"
79 #include "hash-table.h"
80 #include "except.h"
81 #include "params.h"
82 #include "regs.h"
83 #include "ira.h"
84 #include "dumpfile.h"
86 /* The data stored for the loop. */
88 struct loop_data
90 struct loop *outermost_exit; /* The outermost exit of the loop. */
91 bool has_call; /* True if the loop contains a call. */
92 /* Maximal register pressure inside loop for given register class
93 (defined only for the pressure classes). */
94 int max_reg_pressure[N_REG_CLASSES];
95 /* Loop regs referenced and live pseudo-registers. */
96 bitmap_head regs_ref;
97 bitmap_head regs_live;
100 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
102 /* The description of an use. */
104 struct use
106 rtx *pos; /* Position of the use. */
107 rtx_insn *insn; /* The insn in that the use occurs. */
108 unsigned addr_use_p; /* Whether the use occurs in an address. */
109 struct use *next; /* Next use in the list. */
112 /* The description of a def. */
114 struct def
116 struct use *uses; /* The list of uses that are uniquely reached
117 by it. */
118 unsigned n_uses; /* Number of such uses. */
119 unsigned n_addr_uses; /* Number of uses in addresses. */
120 unsigned invno; /* The corresponding invariant. */
123 /* The data stored for each invariant. */
125 struct invariant
127 /* The number of the invariant. */
128 unsigned invno;
130 /* The number of the invariant with the same value. */
131 unsigned eqto;
133 /* The number of invariants which eqto this. */
134 unsigned eqno;
136 /* If we moved the invariant out of the loop, the register that contains its
137 value. */
138 rtx reg;
140 /* If we moved the invariant out of the loop, the original regno
141 that contained its value. */
142 int orig_regno;
144 /* The definition of the invariant. */
145 struct def *def;
147 /* The insn in that it is defined. */
148 rtx_insn *insn;
150 /* Whether it is always executed. */
151 bool always_executed;
153 /* Whether to move the invariant. */
154 bool move;
156 /* Whether the invariant is cheap when used as an address. */
157 bool cheap_address;
159 /* Cost of the invariant. */
160 unsigned cost;
162 /* The invariants it depends on. */
163 bitmap depends_on;
165 /* Used for detecting already visited invariants during determining
166 costs of movements. */
167 unsigned stamp;
170 /* Currently processed loop. */
171 static struct loop *curr_loop;
173 /* Table of invariants indexed by the df_ref uid field. */
175 static unsigned int invariant_table_size = 0;
176 static struct invariant ** invariant_table;
178 /* Entry for hash table of invariant expressions. */
180 struct invariant_expr_entry
182 /* The invariant. */
183 struct invariant *inv;
185 /* Its value. */
186 rtx expr;
188 /* Its mode. */
189 machine_mode mode;
191 /* Its hash. */
192 hashval_t hash;
195 /* The actual stamp for marking already visited invariants during determining
196 costs of movements. */
198 static unsigned actual_stamp;
200 typedef struct invariant *invariant_p;
203 /* The invariants. */
205 static vec<invariant_p> invariants;
207 /* Check the size of the invariant table and realloc if necessary. */
209 static void
210 check_invariant_table_size (void)
212 if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
214 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
215 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
216 memset (&invariant_table[invariant_table_size], 0,
217 (new_size - invariant_table_size) * sizeof (struct invariant *));
218 invariant_table_size = new_size;
222 /* Test for possibility of invariantness of X. */
224 static bool
225 check_maybe_invariant (rtx x)
227 enum rtx_code code = GET_CODE (x);
228 int i, j;
229 const char *fmt;
231 switch (code)
233 CASE_CONST_ANY:
234 case SYMBOL_REF:
235 case CONST:
236 case LABEL_REF:
237 return true;
239 case PC:
240 case CC0:
241 case UNSPEC_VOLATILE:
242 case CALL:
243 return false;
245 case REG:
246 return true;
248 case MEM:
249 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
250 It should not be hard, and might be faster than "elsewhere". */
252 /* Just handle the most trivial case where we load from an unchanging
253 location (most importantly, pic tables). */
254 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
255 break;
257 return false;
259 case ASM_OPERANDS:
260 /* Don't mess with insns declared volatile. */
261 if (MEM_VOLATILE_P (x))
262 return false;
263 break;
265 default:
266 break;
269 fmt = GET_RTX_FORMAT (code);
270 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
272 if (fmt[i] == 'e')
274 if (!check_maybe_invariant (XEXP (x, i)))
275 return false;
277 else if (fmt[i] == 'E')
279 for (j = 0; j < XVECLEN (x, i); j++)
280 if (!check_maybe_invariant (XVECEXP (x, i, j)))
281 return false;
285 return true;
288 /* Returns the invariant definition for USE, or NULL if USE is not
289 invariant. */
291 static struct invariant *
292 invariant_for_use (df_ref use)
294 struct df_link *defs;
295 df_ref def;
296 basic_block bb = DF_REF_BB (use), def_bb;
298 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
299 return NULL;
301 defs = DF_REF_CHAIN (use);
302 if (!defs || defs->next)
303 return NULL;
304 def = defs->ref;
305 check_invariant_table_size ();
306 if (!invariant_table[DF_REF_ID (def)])
307 return NULL;
309 def_bb = DF_REF_BB (def);
310 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
311 return NULL;
312 return invariant_table[DF_REF_ID (def)];
315 /* Computes hash value for invariant expression X in INSN. */
317 static hashval_t
318 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
320 enum rtx_code code = GET_CODE (x);
321 int i, j;
322 const char *fmt;
323 hashval_t val = code;
324 int do_not_record_p;
325 df_ref use;
326 struct invariant *inv;
328 switch (code)
330 CASE_CONST_ANY:
331 case SYMBOL_REF:
332 case CONST:
333 case LABEL_REF:
334 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
336 case REG:
337 use = df_find_use (insn, x);
338 if (!use)
339 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
340 inv = invariant_for_use (use);
341 if (!inv)
342 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
344 gcc_assert (inv->eqto != ~0u);
345 return inv->eqto;
347 default:
348 break;
351 fmt = GET_RTX_FORMAT (code);
352 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
354 if (fmt[i] == 'e')
355 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
356 else if (fmt[i] == 'E')
358 for (j = 0; j < XVECLEN (x, i); j++)
359 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
361 else if (fmt[i] == 'i' || fmt[i] == 'n')
362 val ^= XINT (x, i);
365 return val;
368 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
369 and INSN2 have always the same value. */
371 static bool
372 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
374 enum rtx_code code = GET_CODE (e1);
375 int i, j;
376 const char *fmt;
377 df_ref use1, use2;
378 struct invariant *inv1 = NULL, *inv2 = NULL;
379 rtx sub1, sub2;
381 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
382 the other one. If both are VOIDmode, we rely on the caller of this
383 function to verify that their modes are the same. */
384 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
385 return false;
387 switch (code)
389 CASE_CONST_ANY:
390 case SYMBOL_REF:
391 case CONST:
392 case LABEL_REF:
393 return rtx_equal_p (e1, e2);
395 case REG:
396 use1 = df_find_use (insn1, e1);
397 use2 = df_find_use (insn2, e2);
398 if (use1)
399 inv1 = invariant_for_use (use1);
400 if (use2)
401 inv2 = invariant_for_use (use2);
403 if (!inv1 && !inv2)
404 return rtx_equal_p (e1, e2);
406 if (!inv1 || !inv2)
407 return false;
409 gcc_assert (inv1->eqto != ~0u);
410 gcc_assert (inv2->eqto != ~0u);
411 return inv1->eqto == inv2->eqto;
413 default:
414 break;
417 fmt = GET_RTX_FORMAT (code);
418 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
420 if (fmt[i] == 'e')
422 sub1 = XEXP (e1, i);
423 sub2 = XEXP (e2, i);
425 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
426 return false;
429 else if (fmt[i] == 'E')
431 if (XVECLEN (e1, i) != XVECLEN (e2, i))
432 return false;
434 for (j = 0; j < XVECLEN (e1, i); j++)
436 sub1 = XVECEXP (e1, i, j);
437 sub2 = XVECEXP (e2, i, j);
439 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
440 return false;
443 else if (fmt[i] == 'i' || fmt[i] == 'n')
445 if (XINT (e1, i) != XINT (e2, i))
446 return false;
448 /* Unhandled type of subexpression, we fail conservatively. */
449 else
450 return false;
453 return true;
456 struct invariant_expr_hasher : typed_free_remove <invariant_expr_entry>
458 typedef invariant_expr_entry *value_type;
459 typedef invariant_expr_entry *compare_type;
460 static inline hashval_t hash (const invariant_expr_entry *);
461 static inline bool equal (const invariant_expr_entry *,
462 const invariant_expr_entry *);
465 /* Returns hash value for invariant expression entry ENTRY. */
467 inline hashval_t
468 invariant_expr_hasher::hash (const invariant_expr_entry *entry)
470 return entry->hash;
473 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
475 inline bool
476 invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
477 const invariant_expr_entry *entry2)
479 if (entry1->mode != entry2->mode)
480 return 0;
482 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
483 entry2->inv->insn, entry2->expr);
486 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
488 /* Checks whether invariant with value EXPR in machine mode MODE is
489 recorded in EQ. If this is the case, return the invariant. Otherwise
490 insert INV to the table for this expression and return INV. */
492 static struct invariant *
493 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
494 struct invariant *inv)
496 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
497 struct invariant_expr_entry *entry;
498 struct invariant_expr_entry pentry;
499 invariant_expr_entry **slot;
501 pentry.expr = expr;
502 pentry.inv = inv;
503 pentry.mode = mode;
504 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
505 entry = *slot;
507 if (entry)
508 return entry->inv;
510 entry = XNEW (struct invariant_expr_entry);
511 entry->inv = inv;
512 entry->expr = expr;
513 entry->mode = mode;
514 entry->hash = hash;
515 *slot = entry;
517 return inv;
520 /* Finds invariants identical to INV and records the equivalence. EQ is the
521 hash table of the invariants. */
523 static void
524 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
526 unsigned depno;
527 bitmap_iterator bi;
528 struct invariant *dep;
529 rtx expr, set;
530 machine_mode mode;
531 struct invariant *tmp;
533 if (inv->eqto != ~0u)
534 return;
536 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
538 dep = invariants[depno];
539 find_identical_invariants (eq, dep);
542 set = single_set (inv->insn);
543 expr = SET_SRC (set);
544 mode = GET_MODE (expr);
545 if (mode == VOIDmode)
546 mode = GET_MODE (SET_DEST (set));
548 tmp = find_or_insert_inv (eq, expr, mode, inv);
549 inv->eqto = tmp->invno;
551 if (tmp->invno != inv->invno && inv->always_executed)
552 tmp->eqno++;
554 if (dump_file && inv->eqto != inv->invno)
555 fprintf (dump_file,
556 "Invariant %d is equivalent to invariant %d.\n",
557 inv->invno, inv->eqto);
560 /* Find invariants with the same value and record the equivalences. */
562 static void
563 merge_identical_invariants (void)
565 unsigned i;
566 struct invariant *inv;
567 invariant_htab_type eq (invariants.length ());
569 FOR_EACH_VEC_ELT (invariants, i, inv)
570 find_identical_invariants (&eq, inv);
573 /* Determines the basic blocks inside LOOP that are always executed and
574 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
575 basic blocks that may either exit the loop, or contain the call that
576 does not have to return. BODY is body of the loop obtained by
577 get_loop_body_in_dom_order. */
579 static void
580 compute_always_reached (struct loop *loop, basic_block *body,
581 bitmap may_exit, bitmap always_reached)
583 unsigned i;
585 for (i = 0; i < loop->num_nodes; i++)
587 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
588 bitmap_set_bit (always_reached, i);
590 if (bitmap_bit_p (may_exit, i))
591 return;
595 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
596 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
597 additionally mark blocks that may exit due to a call. */
599 static void
600 find_exits (struct loop *loop, basic_block *body,
601 bitmap may_exit, bitmap has_exit)
603 unsigned i;
604 edge_iterator ei;
605 edge e;
606 struct loop *outermost_exit = loop, *aexit;
607 bool has_call = false;
608 rtx_insn *insn;
610 for (i = 0; i < loop->num_nodes; i++)
612 if (body[i]->loop_father == loop)
614 FOR_BB_INSNS (body[i], insn)
616 if (CALL_P (insn)
617 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
618 || !RTL_CONST_OR_PURE_CALL_P (insn)))
620 has_call = true;
621 bitmap_set_bit (may_exit, i);
622 break;
626 FOR_EACH_EDGE (e, ei, body[i]->succs)
628 if (flow_bb_inside_loop_p (loop, e->dest))
629 continue;
631 bitmap_set_bit (may_exit, i);
632 bitmap_set_bit (has_exit, i);
633 outermost_exit = find_common_loop (outermost_exit,
634 e->dest->loop_father);
636 continue;
639 /* Use the data stored for the subloop to decide whether we may exit
640 through it. It is sufficient to do this for header of the loop,
641 as other basic blocks inside it must be dominated by it. */
642 if (body[i]->loop_father->header != body[i])
643 continue;
645 if (LOOP_DATA (body[i]->loop_father)->has_call)
647 has_call = true;
648 bitmap_set_bit (may_exit, i);
650 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
651 if (aexit != loop)
653 bitmap_set_bit (may_exit, i);
654 bitmap_set_bit (has_exit, i);
656 if (flow_loop_nested_p (aexit, outermost_exit))
657 outermost_exit = aexit;
661 if (loop->aux == NULL)
663 loop->aux = xcalloc (1, sizeof (struct loop_data));
664 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
665 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
667 LOOP_DATA (loop)->outermost_exit = outermost_exit;
668 LOOP_DATA (loop)->has_call = has_call;
671 /* Check whether we may assign a value to X from a register. */
673 static bool
674 may_assign_reg_p (rtx x)
676 return (GET_MODE (x) != VOIDmode
677 && GET_MODE (x) != BLKmode
678 && can_copy_p (GET_MODE (x))
679 && (!REG_P (x)
680 || !HARD_REGISTER_P (x)
681 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
684 /* Finds definitions that may correspond to invariants in LOOP with body
685 BODY. */
687 static void
688 find_defs (struct loop *loop)
690 if (dump_file)
692 fprintf (dump_file,
693 "*****starting processing of loop %d ******\n",
694 loop->num);
697 df_remove_problem (df_chain);
698 df_process_deferred_rescans ();
699 df_chain_add_problem (DF_UD_CHAIN);
700 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
701 df_analyze_loop (loop);
702 check_invariant_table_size ();
704 if (dump_file)
706 df_dump_region (dump_file);
707 fprintf (dump_file,
708 "*****ending processing of loop %d ******\n",
709 loop->num);
713 /* Creates a new invariant for definition DEF in INSN, depending on invariants
714 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
715 unless the program ends due to a function call. The newly created invariant
716 is returned. */
718 static struct invariant *
719 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
720 bool always_executed)
722 struct invariant *inv = XNEW (struct invariant);
723 rtx set = single_set (insn);
724 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
726 inv->def = def;
727 inv->always_executed = always_executed;
728 inv->depends_on = depends_on;
730 /* If the set is simple, usually by moving it we move the whole store out of
731 the loop. Otherwise we save only cost of the computation. */
732 if (def)
734 inv->cost = set_rtx_cost (set, speed);
735 /* ??? Try to determine cheapness of address computation. Unfortunately
736 the address cost is only a relative measure, we can't really compare
737 it with any absolute number, but only with other address costs.
738 But here we don't have any other addresses, so compare with a magic
739 number anyway. It has to be large enough to not regress PR33928
740 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
741 enough to not regress 410.bwaves either (by still moving reg+reg
742 invariants).
743 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
744 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
745 ADDR_SPACE_GENERIC, speed) < 3;
747 else
749 inv->cost = set_src_cost (SET_SRC (set), speed);
750 inv->cheap_address = false;
753 inv->move = false;
754 inv->reg = NULL_RTX;
755 inv->orig_regno = -1;
756 inv->stamp = 0;
757 inv->insn = insn;
759 inv->invno = invariants.length ();
760 inv->eqto = ~0u;
762 /* Itself. */
763 inv->eqno = 1;
765 if (def)
766 def->invno = inv->invno;
767 invariants.safe_push (inv);
769 if (dump_file)
771 fprintf (dump_file,
772 "Set in insn %d is invariant (%d), cost %d, depends on ",
773 INSN_UID (insn), inv->invno, inv->cost);
774 dump_bitmap (dump_file, inv->depends_on);
777 return inv;
780 /* Record USE at DEF. */
782 static void
783 record_use (struct def *def, df_ref use)
785 struct use *u = XNEW (struct use);
787 u->pos = DF_REF_REAL_LOC (use);
788 u->insn = DF_REF_INSN (use);
789 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
790 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
791 u->next = def->uses;
792 def->uses = u;
793 def->n_uses++;
794 if (u->addr_use_p)
795 def->n_addr_uses++;
798 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
799 bitmap. Returns true if all dependencies of USE are known to be
800 loop invariants, false otherwise. */
802 static bool
803 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
805 df_ref def;
806 basic_block def_bb;
807 struct df_link *defs;
808 struct def *def_data;
809 struct invariant *inv;
811 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
812 return false;
814 defs = DF_REF_CHAIN (use);
815 if (!defs)
817 unsigned int regno = DF_REF_REGNO (use);
819 /* If this is the use of an uninitialized argument register that is
820 likely to be spilled, do not move it lest this might extend its
821 lifetime and cause reload to die. This can occur for a call to
822 a function taking complex number arguments and moving the insns
823 preparing the arguments without moving the call itself wouldn't
824 gain much in practice. */
825 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
826 && FUNCTION_ARG_REGNO_P (regno)
827 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
828 return false;
830 return true;
833 if (defs->next)
834 return false;
836 def = defs->ref;
837 check_invariant_table_size ();
838 inv = invariant_table[DF_REF_ID (def)];
839 if (!inv)
840 return false;
842 def_data = inv->def;
843 gcc_assert (def_data != NULL);
845 def_bb = DF_REF_BB (def);
846 /* Note that in case bb == def_bb, we know that the definition
847 dominates insn, because def has invariant_table[DF_REF_ID(def)]
848 defined and we process the insns in the basic block bb
849 sequentially. */
850 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
851 return false;
853 bitmap_set_bit (depends_on, def_data->invno);
854 return true;
858 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
859 bitmap. Returns true if all dependencies of INSN are known to be
860 loop invariants, false otherwise. */
862 static bool
863 check_dependencies (rtx_insn *insn, bitmap depends_on)
865 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
866 df_ref use;
867 basic_block bb = BLOCK_FOR_INSN (insn);
869 FOR_EACH_INSN_INFO_USE (use, insn_info)
870 if (!check_dependency (bb, use, depends_on))
871 return false;
872 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
873 if (!check_dependency (bb, use, depends_on))
874 return false;
876 return true;
879 /* Pre-check candidate DEST to skip the one which can not make a valid insn
880 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
881 static bool
882 pre_check_invariant_p (bool simple, rtx dest)
884 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
886 df_ref use;
887 rtx ref;
888 unsigned int i = REGNO (dest);
889 struct df_insn_info *insn_info;
890 df_ref def_rec;
892 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
894 ref = DF_REF_INSN (use);
895 insn_info = DF_INSN_INFO_GET (ref);
897 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
898 if (DF_REF_REGNO (def_rec) == i)
900 /* Multi definitions at this stage, most likely are due to
901 instruction constraints, which requires both read and write
902 on the same register. Since move_invariant_reg is not
903 powerful enough to handle such cases, just ignore the INV
904 and leave the chance to others. */
905 return false;
909 return true;
912 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
913 executed. ALWAYS_EXECUTED is true if the insn is always executed,
914 unless the program ends due to a function call. */
916 static void
917 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
919 df_ref ref;
920 struct def *def;
921 bitmap depends_on;
922 rtx set, dest;
923 bool simple = true;
924 struct invariant *inv;
926 /* We can't move a CC0 setter without the user. */
927 if (HAVE_cc0 && sets_cc0_p (insn))
928 return;
930 set = single_set (insn);
931 if (!set)
932 return;
933 dest = SET_DEST (set);
935 if (!REG_P (dest)
936 || HARD_REGISTER_P (dest))
937 simple = false;
939 if (!may_assign_reg_p (dest)
940 || !pre_check_invariant_p (simple, dest)
941 || !check_maybe_invariant (SET_SRC (set)))
942 return;
944 /* If the insn can throw exception, we cannot move it at all without changing
945 cfg. */
946 if (can_throw_internal (insn))
947 return;
949 /* We cannot make trapping insn executed, unless it was executed before. */
950 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
951 return;
953 depends_on = BITMAP_ALLOC (NULL);
954 if (!check_dependencies (insn, depends_on))
956 BITMAP_FREE (depends_on);
957 return;
960 if (simple)
961 def = XCNEW (struct def);
962 else
963 def = NULL;
965 inv = create_new_invariant (def, insn, depends_on, always_executed);
967 if (simple)
969 ref = df_find_def (insn, dest);
970 check_invariant_table_size ();
971 invariant_table[DF_REF_ID (ref)] = inv;
975 /* Record registers used in INSN that have a unique invariant definition. */
977 static void
978 record_uses (rtx_insn *insn)
980 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
981 df_ref use;
982 struct invariant *inv;
984 FOR_EACH_INSN_INFO_USE (use, insn_info)
986 inv = invariant_for_use (use);
987 if (inv)
988 record_use (inv->def, use);
990 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
992 inv = invariant_for_use (use);
993 if (inv)
994 record_use (inv->def, use);
998 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
999 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1000 unless the program ends due to a function call. */
1002 static void
1003 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1005 find_invariant_insn (insn, always_reached, always_executed);
1006 record_uses (insn);
1009 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1010 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1011 block is always executed, unless the program ends due to a function
1012 call. */
1014 static void
1015 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1017 rtx_insn *insn;
1019 FOR_BB_INSNS (bb, insn)
1021 if (!NONDEBUG_INSN_P (insn))
1022 continue;
1024 find_invariants_insn (insn, always_reached, always_executed);
1026 if (always_reached
1027 && CALL_P (insn)
1028 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1029 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1030 always_reached = false;
1034 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1035 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1036 bitmap of basic blocks in BODY that are always executed unless the program
1037 ends due to a function call. */
1039 static void
1040 find_invariants_body (struct loop *loop, basic_block *body,
1041 bitmap always_reached, bitmap always_executed)
1043 unsigned i;
1045 for (i = 0; i < loop->num_nodes; i++)
1046 find_invariants_bb (body[i],
1047 bitmap_bit_p (always_reached, i),
1048 bitmap_bit_p (always_executed, i));
1051 /* Finds invariants in LOOP. */
1053 static void
1054 find_invariants (struct loop *loop)
1056 bitmap may_exit = BITMAP_ALLOC (NULL);
1057 bitmap always_reached = BITMAP_ALLOC (NULL);
1058 bitmap has_exit = BITMAP_ALLOC (NULL);
1059 bitmap always_executed = BITMAP_ALLOC (NULL);
1060 basic_block *body = get_loop_body_in_dom_order (loop);
1062 find_exits (loop, body, may_exit, has_exit);
1063 compute_always_reached (loop, body, may_exit, always_reached);
1064 compute_always_reached (loop, body, has_exit, always_executed);
1066 find_defs (loop);
1067 find_invariants_body (loop, body, always_reached, always_executed);
1068 merge_identical_invariants ();
1070 BITMAP_FREE (always_reached);
1071 BITMAP_FREE (always_executed);
1072 BITMAP_FREE (may_exit);
1073 BITMAP_FREE (has_exit);
1074 free (body);
1077 /* Frees a list of uses USE. */
1079 static void
1080 free_use_list (struct use *use)
1082 struct use *next;
1084 for (; use; use = next)
1086 next = use->next;
1087 free (use);
1091 /* Return pressure class and number of hard registers (through *NREGS)
1092 for destination of INSN. */
1093 static enum reg_class
1094 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1096 rtx reg;
1097 enum reg_class pressure_class;
1098 rtx set = single_set (insn);
1100 /* Considered invariant insns have only one set. */
1101 gcc_assert (set != NULL_RTX);
1102 reg = SET_DEST (set);
1103 if (GET_CODE (reg) == SUBREG)
1104 reg = SUBREG_REG (reg);
1105 if (MEM_P (reg))
1107 *nregs = 0;
1108 pressure_class = NO_REGS;
1110 else
1112 if (! REG_P (reg))
1113 reg = NULL_RTX;
1114 if (reg == NULL_RTX)
1115 pressure_class = GENERAL_REGS;
1116 else
1118 pressure_class = reg_allocno_class (REGNO (reg));
1119 pressure_class = ira_pressure_class_translate[pressure_class];
1121 *nregs
1122 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1124 return pressure_class;
1127 /* Calculates cost and number of registers needed for moving invariant INV
1128 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1129 the REG_CLASS of INV. Return
1130 -1: if INV is invalid.
1131 0: if INV and its depends_on have same reg_class
1132 1: if INV and its depends_on have different reg_classes. */
1134 static int
1135 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1136 enum reg_class *cl)
1138 int i, acomp_cost;
1139 unsigned aregs_needed[N_REG_CLASSES];
1140 unsigned depno;
1141 struct invariant *dep;
1142 bitmap_iterator bi;
1143 int ret = 1;
1145 /* Find the representative of the class of the equivalent invariants. */
1146 inv = invariants[inv->eqto];
1148 *comp_cost = 0;
1149 if (! flag_ira_loop_pressure)
1150 regs_needed[0] = 0;
1151 else
1153 for (i = 0; i < ira_pressure_classes_num; i++)
1154 regs_needed[ira_pressure_classes[i]] = 0;
1157 if (inv->move
1158 || inv->stamp == actual_stamp)
1159 return -1;
1160 inv->stamp = actual_stamp;
1162 if (! flag_ira_loop_pressure)
1163 regs_needed[0]++;
1164 else
1166 int nregs;
1167 enum reg_class pressure_class;
1169 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1170 regs_needed[pressure_class] += nregs;
1171 *cl = pressure_class;
1172 ret = 0;
1175 if (!inv->cheap_address
1176 || inv->def->n_addr_uses < inv->def->n_uses)
1177 (*comp_cost) += inv->cost * inv->eqno;
1179 #ifdef STACK_REGS
1181 /* Hoisting constant pool constants into stack regs may cost more than
1182 just single register. On x87, the balance is affected both by the
1183 small number of FP registers, and by its register stack organization,
1184 that forces us to add compensation code in and around the loop to
1185 shuffle the operands to the top of stack before use, and pop them
1186 from the stack after the loop finishes.
1188 To model this effect, we increase the number of registers needed for
1189 stack registers by two: one register push, and one register pop.
1190 This usually has the effect that FP constant loads from the constant
1191 pool are not moved out of the loop.
1193 Note that this also means that dependent invariants can not be moved.
1194 However, the primary purpose of this pass is to move loop invariant
1195 address arithmetic out of loops, and address arithmetic that depends
1196 on floating point constants is unlikely to ever occur. */
1197 rtx set = single_set (inv->insn);
1198 if (set
1199 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1200 && constant_pool_constant_p (SET_SRC (set)))
1202 if (flag_ira_loop_pressure)
1203 regs_needed[ira_stack_reg_pressure_class] += 2;
1204 else
1205 regs_needed[0] += 2;
1208 #endif
1210 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1212 bool check_p;
1213 enum reg_class dep_cl = ALL_REGS;
1214 int dep_ret;
1216 dep = invariants[depno];
1218 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1219 if (dep->move)
1220 continue;
1222 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1224 if (! flag_ira_loop_pressure)
1225 check_p = aregs_needed[0] != 0;
1226 else
1228 for (i = 0; i < ira_pressure_classes_num; i++)
1229 if (aregs_needed[ira_pressure_classes[i]] != 0)
1230 break;
1231 check_p = i < ira_pressure_classes_num;
1233 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1235 *cl = ALL_REGS;
1236 ret = 1;
1239 if (check_p
1240 /* We need to check always_executed, since if the original value of
1241 the invariant may be preserved, we may need to keep it in a
1242 separate register. TODO check whether the register has an
1243 use outside of the loop. */
1244 && dep->always_executed
1245 && !dep->def->uses->next)
1247 /* If this is a single use, after moving the dependency we will not
1248 need a new register. */
1249 if (! flag_ira_loop_pressure)
1250 aregs_needed[0]--;
1251 else
1253 int nregs;
1254 enum reg_class pressure_class;
1256 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1257 aregs_needed[pressure_class] -= nregs;
1261 if (! flag_ira_loop_pressure)
1262 regs_needed[0] += aregs_needed[0];
1263 else
1265 for (i = 0; i < ira_pressure_classes_num; i++)
1266 regs_needed[ira_pressure_classes[i]]
1267 += aregs_needed[ira_pressure_classes[i]];
1269 (*comp_cost) += acomp_cost;
1271 return ret;
1274 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1275 of registers used in the loop, NEW_REGS is the number of new variables
1276 already added due to the invariant motion. The number of registers needed
1277 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1278 through to estimate_reg_pressure_cost. */
1280 static int
1281 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1282 unsigned *new_regs, unsigned regs_used,
1283 bool speed, bool call_p)
1285 int comp_cost, size_cost;
1286 /* Workaround -Wmaybe-uninitialized false positive during
1287 profiledbootstrap by initializing it. */
1288 enum reg_class cl = NO_REGS;
1289 int ret;
1291 actual_stamp++;
1293 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1295 if (! flag_ira_loop_pressure)
1297 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1298 regs_used, speed, call_p)
1299 - estimate_reg_pressure_cost (new_regs[0],
1300 regs_used, speed, call_p));
1302 else if (ret < 0)
1303 return -1;
1304 else if ((ret == 0) && (cl == NO_REGS))
1305 /* Hoist it anyway since it does not impact register pressure. */
1306 return 1;
1307 else
1309 int i;
1310 enum reg_class pressure_class;
1312 for (i = 0; i < ira_pressure_classes_num; i++)
1314 pressure_class = ira_pressure_classes[i];
1316 if (!reg_classes_intersect_p (pressure_class, cl))
1317 continue;
1319 if ((int) new_regs[pressure_class]
1320 + (int) regs_needed[pressure_class]
1321 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1322 + IRA_LOOP_RESERVED_REGS
1323 > ira_class_hard_regs_num[pressure_class])
1324 break;
1326 if (i < ira_pressure_classes_num)
1327 /* There will be register pressure excess and we want not to
1328 make this loop invariant motion. All loop invariants with
1329 non-positive gains will be rejected in function
1330 find_invariants_to_move. Therefore we return the negative
1331 number here.
1333 One could think that this rejects also expensive loop
1334 invariant motions and this will hurt code performance.
1335 However numerous experiments with different heuristics
1336 taking invariant cost into account did not confirm this
1337 assumption. There are possible explanations for this
1338 result:
1339 o probably all expensive invariants were already moved out
1340 of the loop by PRE and gimple invariant motion pass.
1341 o expensive invariant execution will be hidden by insn
1342 scheduling or OOO processor hardware because usually such
1343 invariants have a lot of freedom to be executed
1344 out-of-order.
1345 Another reason for ignoring invariant cost vs spilling cost
1346 heuristics is also in difficulties to evaluate accurately
1347 spill cost at this stage. */
1348 return -1;
1349 else
1350 size_cost = 0;
1353 return comp_cost - size_cost;
1356 /* Finds invariant with best gain for moving. Returns the gain, stores
1357 the invariant in *BEST and number of registers needed for it to
1358 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1359 NEW_REGS is the number of new variables already added due to invariant
1360 motion. */
1362 static int
1363 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1364 unsigned *new_regs, unsigned regs_used,
1365 bool speed, bool call_p)
1367 struct invariant *inv;
1368 int i, gain = 0, again;
1369 unsigned aregs_needed[N_REG_CLASSES], invno;
1371 FOR_EACH_VEC_ELT (invariants, invno, inv)
1373 if (inv->move)
1374 continue;
1376 /* Only consider the "representatives" of equivalent invariants. */
1377 if (inv->eqto != inv->invno)
1378 continue;
1380 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1381 speed, call_p);
1382 if (again > gain)
1384 gain = again;
1385 *best = inv;
1386 if (! flag_ira_loop_pressure)
1387 regs_needed[0] = aregs_needed[0];
1388 else
1390 for (i = 0; i < ira_pressure_classes_num; i++)
1391 regs_needed[ira_pressure_classes[i]]
1392 = aregs_needed[ira_pressure_classes[i]];
1397 return gain;
1400 /* Marks invariant INVNO and all its dependencies for moving. */
1402 static void
1403 set_move_mark (unsigned invno, int gain)
1405 struct invariant *inv = invariants[invno];
1406 bitmap_iterator bi;
1408 /* Find the representative of the class of the equivalent invariants. */
1409 inv = invariants[inv->eqto];
1411 if (inv->move)
1412 return;
1413 inv->move = true;
1415 if (dump_file)
1417 if (gain >= 0)
1418 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1419 invno, gain);
1420 else
1421 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1422 invno);
1425 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1427 set_move_mark (invno, -1);
1431 /* Determines which invariants to move. */
1433 static void
1434 find_invariants_to_move (bool speed, bool call_p)
1436 int gain;
1437 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1438 struct invariant *inv = NULL;
1440 if (!invariants.length ())
1441 return;
1443 if (flag_ira_loop_pressure)
1444 /* REGS_USED is actually never used when the flag is on. */
1445 regs_used = 0;
1446 else
1447 /* We do not really do a good job in estimating number of
1448 registers used; we put some initial bound here to stand for
1449 induction variables etc. that we do not detect. */
1451 unsigned int n_regs = DF_REG_SIZE (df);
1453 regs_used = 2;
1455 for (i = 0; i < n_regs; i++)
1457 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1459 /* This is a value that is used but not changed inside loop. */
1460 regs_used++;
1465 if (! flag_ira_loop_pressure)
1466 new_regs[0] = regs_needed[0] = 0;
1467 else
1469 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1470 new_regs[ira_pressure_classes[i]] = 0;
1472 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1473 new_regs, regs_used,
1474 speed, call_p)) > 0)
1476 set_move_mark (inv->invno, gain);
1477 if (! flag_ira_loop_pressure)
1478 new_regs[0] += regs_needed[0];
1479 else
1481 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1482 new_regs[ira_pressure_classes[i]]
1483 += regs_needed[ira_pressure_classes[i]];
1488 /* Replace the uses, reached by the definition of invariant INV, by REG.
1490 IN_GROUP is nonzero if this is part of a group of changes that must be
1491 performed as a group. In that case, the changes will be stored. The
1492 function `apply_change_group' will validate and apply the changes. */
1494 static int
1495 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1497 /* Replace the uses we know to be dominated. It saves work for copy
1498 propagation, and also it is necessary so that dependent invariants
1499 are computed right. */
1500 if (inv->def)
1502 struct use *use;
1503 for (use = inv->def->uses; use; use = use->next)
1504 validate_change (use->insn, use->pos, reg, true);
1506 /* If we aren't part of a larger group, apply the changes now. */
1507 if (!in_group)
1508 return apply_change_group ();
1511 return 1;
1514 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1515 otherwise. */
1517 static bool
1518 move_invariant_reg (struct loop *loop, unsigned invno)
1520 struct invariant *inv = invariants[invno];
1521 struct invariant *repr = invariants[inv->eqto];
1522 unsigned i;
1523 basic_block preheader = loop_preheader_edge (loop)->src;
1524 rtx reg, set, dest, note;
1525 bitmap_iterator bi;
1526 int regno = -1;
1528 if (inv->reg)
1529 return true;
1530 if (!repr->move)
1531 return false;
1533 /* If this is a representative of the class of equivalent invariants,
1534 really move the invariant. Otherwise just replace its use with
1535 the register used for the representative. */
1536 if (inv == repr)
1538 if (inv->depends_on)
1540 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1542 if (!move_invariant_reg (loop, i))
1543 goto fail;
1547 /* Move the set out of the loop. If the set is always executed (we could
1548 omit this condition if we know that the register is unused outside of
1549 the loop, but it does not seem worth finding out) and it has no uses
1550 that would not be dominated by it, we may just move it (TODO).
1551 Otherwise we need to create a temporary register. */
1552 set = single_set (inv->insn);
1553 reg = dest = SET_DEST (set);
1554 if (GET_CODE (reg) == SUBREG)
1555 reg = SUBREG_REG (reg);
1556 if (REG_P (reg))
1557 regno = REGNO (reg);
1559 reg = gen_reg_rtx_and_attrs (dest);
1561 /* Try replacing the destination by a new pseudoregister. */
1562 validate_change (inv->insn, &SET_DEST (set), reg, true);
1564 /* As well as all the dominated uses. */
1565 replace_uses (inv, reg, true);
1567 /* And validate all the changes. */
1568 if (!apply_change_group ())
1569 goto fail;
1571 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1572 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1574 /* If there is a REG_EQUAL note on the insn we just moved, and the
1575 insn is in a basic block that is not always executed or the note
1576 contains something for which we don't know the invariant status,
1577 the note may no longer be valid after we move the insn. Note that
1578 uses in REG_EQUAL notes are taken into account in the computation
1579 of invariants, so it is safe to retain the note even if it contains
1580 register references for which we know the invariant status. */
1581 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1582 && (!inv->always_executed
1583 || !check_maybe_invariant (XEXP (note, 0))))
1584 remove_note (inv->insn, note);
1586 else
1588 if (!move_invariant_reg (loop, repr->invno))
1589 goto fail;
1590 reg = repr->reg;
1591 regno = repr->orig_regno;
1592 if (!replace_uses (inv, reg, false))
1593 goto fail;
1594 set = single_set (inv->insn);
1595 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1596 delete_insn (inv->insn);
1599 inv->reg = reg;
1600 inv->orig_regno = regno;
1602 return true;
1604 fail:
1605 /* If we failed, clear move flag, so that we do not try to move inv
1606 again. */
1607 if (dump_file)
1608 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1609 inv->move = false;
1610 inv->reg = NULL_RTX;
1611 inv->orig_regno = -1;
1613 return false;
1616 /* Move selected invariant out of the LOOP. Newly created regs are marked
1617 in TEMPORARY_REGS. */
1619 static void
1620 move_invariants (struct loop *loop)
1622 struct invariant *inv;
1623 unsigned i;
1625 FOR_EACH_VEC_ELT (invariants, i, inv)
1626 move_invariant_reg (loop, i);
1627 if (flag_ira_loop_pressure && resize_reg_info ())
1629 FOR_EACH_VEC_ELT (invariants, i, inv)
1630 if (inv->reg != NULL_RTX)
1632 if (inv->orig_regno >= 0)
1633 setup_reg_classes (REGNO (inv->reg),
1634 reg_preferred_class (inv->orig_regno),
1635 reg_alternate_class (inv->orig_regno),
1636 reg_allocno_class (inv->orig_regno));
1637 else
1638 setup_reg_classes (REGNO (inv->reg),
1639 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1644 /* Initializes invariant motion data. */
1646 static void
1647 init_inv_motion_data (void)
1649 actual_stamp = 1;
1651 invariants.create (100);
1654 /* Frees the data allocated by invariant motion. */
1656 static void
1657 free_inv_motion_data (void)
1659 unsigned i;
1660 struct def *def;
1661 struct invariant *inv;
1663 check_invariant_table_size ();
1664 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1666 inv = invariant_table[i];
1667 if (inv)
1669 def = inv->def;
1670 gcc_assert (def != NULL);
1672 free_use_list (def->uses);
1673 free (def);
1674 invariant_table[i] = NULL;
1678 FOR_EACH_VEC_ELT (invariants, i, inv)
1680 BITMAP_FREE (inv->depends_on);
1681 free (inv);
1683 invariants.release ();
1686 /* Move the invariants out of the LOOP. */
1688 static void
1689 move_single_loop_invariants (struct loop *loop)
1691 init_inv_motion_data ();
1693 find_invariants (loop);
1694 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1695 LOOP_DATA (loop)->has_call);
1696 move_invariants (loop);
1698 free_inv_motion_data ();
1701 /* Releases the auxiliary data for LOOP. */
1703 static void
1704 free_loop_data (struct loop *loop)
1706 struct loop_data *data = LOOP_DATA (loop);
1707 if (!data)
1708 return;
1710 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1711 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1712 free (data);
1713 loop->aux = NULL;
1718 /* Registers currently living. */
1719 static bitmap_head curr_regs_live;
1721 /* Current reg pressure for each pressure class. */
1722 static int curr_reg_pressure[N_REG_CLASSES];
1724 /* Record all regs that are set in any one insn. Communication from
1725 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1726 all hard-registers. */
1727 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1728 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1729 /* Number of regs stored in the previous array. */
1730 static int n_regs_set;
1732 /* Return pressure class and number of needed hard registers (through
1733 *NREGS) of register REGNO. */
1734 static enum reg_class
1735 get_regno_pressure_class (int regno, int *nregs)
1737 if (regno >= FIRST_PSEUDO_REGISTER)
1739 enum reg_class pressure_class;
1741 pressure_class = reg_allocno_class (regno);
1742 pressure_class = ira_pressure_class_translate[pressure_class];
1743 *nregs
1744 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1745 return pressure_class;
1747 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1748 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1750 *nregs = 1;
1751 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1753 else
1755 *nregs = 0;
1756 return NO_REGS;
1760 /* Increase (if INCR_P) or decrease current register pressure for
1761 register REGNO. */
1762 static void
1763 change_pressure (int regno, bool incr_p)
1765 int nregs;
1766 enum reg_class pressure_class;
1768 pressure_class = get_regno_pressure_class (regno, &nregs);
1769 if (! incr_p)
1770 curr_reg_pressure[pressure_class] -= nregs;
1771 else
1773 curr_reg_pressure[pressure_class] += nregs;
1774 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1775 < curr_reg_pressure[pressure_class])
1776 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1777 = curr_reg_pressure[pressure_class];
1781 /* Mark REGNO birth. */
1782 static void
1783 mark_regno_live (int regno)
1785 struct loop *loop;
1787 for (loop = curr_loop;
1788 loop != current_loops->tree_root;
1789 loop = loop_outer (loop))
1790 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
1791 if (!bitmap_set_bit (&curr_regs_live, regno))
1792 return;
1793 change_pressure (regno, true);
1796 /* Mark REGNO death. */
1797 static void
1798 mark_regno_death (int regno)
1800 if (! bitmap_clear_bit (&curr_regs_live, regno))
1801 return;
1802 change_pressure (regno, false);
1805 /* Mark setting register REG. */
1806 static void
1807 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1808 void *data ATTRIBUTE_UNUSED)
1810 int regno;
1812 if (GET_CODE (reg) == SUBREG)
1813 reg = SUBREG_REG (reg);
1815 if (! REG_P (reg))
1816 return;
1818 regs_set[n_regs_set++] = reg;
1820 regno = REGNO (reg);
1822 if (regno >= FIRST_PSEUDO_REGISTER)
1823 mark_regno_live (regno);
1824 else
1826 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1828 while (regno < last)
1830 mark_regno_live (regno);
1831 regno++;
1836 /* Mark clobbering register REG. */
1837 static void
1838 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1840 if (GET_CODE (setter) == CLOBBER)
1841 mark_reg_store (reg, setter, data);
1844 /* Mark register REG death. */
1845 static void
1846 mark_reg_death (rtx reg)
1848 int regno = REGNO (reg);
1850 if (regno >= FIRST_PSEUDO_REGISTER)
1851 mark_regno_death (regno);
1852 else
1854 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1856 while (regno < last)
1858 mark_regno_death (regno);
1859 regno++;
1864 /* Mark occurrence of registers in X for the current loop. */
1865 static void
1866 mark_ref_regs (rtx x)
1868 RTX_CODE code;
1869 int i;
1870 const char *fmt;
1872 if (!x)
1873 return;
1875 code = GET_CODE (x);
1876 if (code == REG)
1878 struct loop *loop;
1880 for (loop = curr_loop;
1881 loop != current_loops->tree_root;
1882 loop = loop_outer (loop))
1883 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
1884 return;
1887 fmt = GET_RTX_FORMAT (code);
1888 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1889 if (fmt[i] == 'e')
1890 mark_ref_regs (XEXP (x, i));
1891 else if (fmt[i] == 'E')
1893 int j;
1895 for (j = 0; j < XVECLEN (x, i); j++)
1896 mark_ref_regs (XVECEXP (x, i, j));
1900 /* Calculate register pressure in the loops. */
1901 static void
1902 calculate_loop_reg_pressure (void)
1904 int i;
1905 unsigned int j;
1906 bitmap_iterator bi;
1907 basic_block bb;
1908 rtx_insn *insn;
1909 rtx link;
1910 struct loop *loop, *parent;
1912 FOR_EACH_LOOP (loop, 0)
1913 if (loop->aux == NULL)
1915 loop->aux = xcalloc (1, sizeof (struct loop_data));
1916 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1917 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1919 ira_setup_eliminable_regset ();
1920 bitmap_initialize (&curr_regs_live, &reg_obstack);
1921 FOR_EACH_BB_FN (bb, cfun)
1923 curr_loop = bb->loop_father;
1924 if (curr_loop == current_loops->tree_root)
1925 continue;
1927 for (loop = curr_loop;
1928 loop != current_loops->tree_root;
1929 loop = loop_outer (loop))
1930 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1932 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1933 for (i = 0; i < ira_pressure_classes_num; i++)
1934 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1935 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1936 change_pressure (j, true);
1938 FOR_BB_INSNS (bb, insn)
1940 if (! NONDEBUG_INSN_P (insn))
1941 continue;
1943 mark_ref_regs (PATTERN (insn));
1944 n_regs_set = 0;
1945 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
1947 /* Mark any registers dead after INSN as dead now. */
1949 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1950 if (REG_NOTE_KIND (link) == REG_DEAD)
1951 mark_reg_death (XEXP (link, 0));
1953 /* Mark any registers set in INSN as live,
1954 and mark them as conflicting with all other live regs.
1955 Clobbers are processed again, so they conflict with
1956 the registers that are set. */
1958 note_stores (PATTERN (insn), mark_reg_store, NULL);
1960 #ifdef AUTO_INC_DEC
1961 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1962 if (REG_NOTE_KIND (link) == REG_INC)
1963 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1964 #endif
1965 while (n_regs_set-- > 0)
1967 rtx note = find_regno_note (insn, REG_UNUSED,
1968 REGNO (regs_set[n_regs_set]));
1969 if (! note)
1970 continue;
1972 mark_reg_death (XEXP (note, 0));
1976 bitmap_clear (&curr_regs_live);
1977 if (flag_ira_region == IRA_REGION_MIXED
1978 || flag_ira_region == IRA_REGION_ALL)
1979 FOR_EACH_LOOP (loop, 0)
1981 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1982 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1984 enum reg_class pressure_class;
1985 int nregs;
1987 pressure_class = get_regno_pressure_class (j, &nregs);
1988 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
1991 if (dump_file == NULL)
1992 return;
1993 FOR_EACH_LOOP (loop, 0)
1995 parent = loop_outer (loop);
1996 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1997 loop->num, (parent == NULL ? -1 : parent->num),
1998 loop->header->index, loop_depth (loop));
1999 fprintf (dump_file, "\n ref. regnos:");
2000 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2001 fprintf (dump_file, " %d", j);
2002 fprintf (dump_file, "\n live regnos:");
2003 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2004 fprintf (dump_file, " %d", j);
2005 fprintf (dump_file, "\n Pressure:");
2006 for (i = 0; (int) i < ira_pressure_classes_num; i++)
2008 enum reg_class pressure_class;
2010 pressure_class = ira_pressure_classes[i];
2011 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2012 continue;
2013 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2014 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2016 fprintf (dump_file, "\n");
2022 /* Move the invariants out of the loops. */
2024 void
2025 move_loop_invariants (void)
2027 struct loop *loop;
2029 if (flag_ira_loop_pressure)
2031 df_analyze ();
2032 regstat_init_n_sets_and_refs ();
2033 ira_set_pseudo_classes (true, dump_file);
2034 calculate_loop_reg_pressure ();
2035 regstat_free_n_sets_and_refs ();
2037 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2038 /* Process the loops, innermost first. */
2039 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2041 curr_loop = loop;
2042 /* move_single_loop_invariants for very large loops
2043 is time consuming and might need a lot of memory. */
2044 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2045 move_single_loop_invariants (loop);
2048 FOR_EACH_LOOP (loop, 0)
2050 free_loop_data (loop);
2053 if (flag_ira_loop_pressure)
2054 /* There is no sense to keep this info because it was most
2055 probably outdated by subsequent passes. */
2056 free_reg_info ();
2057 free (invariant_table);
2058 invariant_table = NULL;
2059 invariant_table_size = 0;
2061 #ifdef ENABLE_CHECKING
2062 verify_flow_info ();
2063 #endif