2014-10-24 Christophe Lyon <christophe.lyon@linaro.org>
[official-gcc.git] / gcc / loop-invariant.c
blob783d74a45fe7466d0a09e3a3db4b7bb64fd2c54e
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2014 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 "basic-block.h"
46 #include "cfgloop.h"
47 #include "expr.h"
48 #include "recog.h"
49 #include "target.h"
50 #include "hashtab.h"
51 #include "hash-set.h"
52 #include "vec.h"
53 #include "machmode.h"
54 #include "input.h"
55 #include "function.h"
56 #include "flags.h"
57 #include "df.h"
58 #include "hash-table.h"
59 #include "except.h"
60 #include "params.h"
61 #include "regs.h"
62 #include "ira.h"
63 #include "dumpfile.h"
65 /* The data stored for the loop. */
67 struct loop_data
69 struct loop *outermost_exit; /* The outermost exit of the loop. */
70 bool has_call; /* True if the loop contains a call. */
71 /* Maximal register pressure inside loop for given register class
72 (defined only for the pressure classes). */
73 int max_reg_pressure[N_REG_CLASSES];
74 /* Loop regs referenced and live pseudo-registers. */
75 bitmap_head regs_ref;
76 bitmap_head regs_live;
79 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
81 /* The description of an use. */
83 struct use
85 rtx *pos; /* Position of the use. */
86 rtx_insn *insn; /* The insn in that the use occurs. */
87 unsigned addr_use_p; /* Whether the use occurs in an address. */
88 struct use *next; /* Next use in the list. */
91 /* The description of a def. */
93 struct def
95 struct use *uses; /* The list of uses that are uniquely reached
96 by it. */
97 unsigned n_uses; /* Number of such uses. */
98 unsigned n_addr_uses; /* Number of uses in addresses. */
99 unsigned invno; /* The corresponding invariant. */
102 /* The data stored for each invariant. */
104 struct invariant
106 /* The number of the invariant. */
107 unsigned invno;
109 /* The number of the invariant with the same value. */
110 unsigned eqto;
112 /* The number of invariants which eqto this. */
113 unsigned eqno;
115 /* If we moved the invariant out of the loop, the register that contains its
116 value. */
117 rtx reg;
119 /* If we moved the invariant out of the loop, the original regno
120 that contained its value. */
121 int orig_regno;
123 /* The definition of the invariant. */
124 struct def *def;
126 /* The insn in that it is defined. */
127 rtx_insn *insn;
129 /* Whether it is always executed. */
130 bool always_executed;
132 /* Whether to move the invariant. */
133 bool move;
135 /* Whether the invariant is cheap when used as an address. */
136 bool cheap_address;
138 /* Cost of the invariant. */
139 unsigned cost;
141 /* The invariants it depends on. */
142 bitmap depends_on;
144 /* Used for detecting already visited invariants during determining
145 costs of movements. */
146 unsigned stamp;
149 /* Currently processed loop. */
150 static struct loop *curr_loop;
152 /* Table of invariants indexed by the df_ref uid field. */
154 static unsigned int invariant_table_size = 0;
155 static struct invariant ** invariant_table;
157 /* Entry for hash table of invariant expressions. */
159 struct invariant_expr_entry
161 /* The invariant. */
162 struct invariant *inv;
164 /* Its value. */
165 rtx expr;
167 /* Its mode. */
168 enum machine_mode mode;
170 /* Its hash. */
171 hashval_t hash;
174 /* The actual stamp for marking already visited invariants during determining
175 costs of movements. */
177 static unsigned actual_stamp;
179 typedef struct invariant *invariant_p;
182 /* The invariants. */
184 static vec<invariant_p> invariants;
186 /* Check the size of the invariant table and realloc if necessary. */
188 static void
189 check_invariant_table_size (void)
191 if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
193 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
194 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
195 memset (&invariant_table[invariant_table_size], 0,
196 (new_size - invariant_table_size) * sizeof (struct invariant *));
197 invariant_table_size = new_size;
201 /* Test for possibility of invariantness of X. */
203 static bool
204 check_maybe_invariant (rtx x)
206 enum rtx_code code = GET_CODE (x);
207 int i, j;
208 const char *fmt;
210 switch (code)
212 CASE_CONST_ANY:
213 case SYMBOL_REF:
214 case CONST:
215 case LABEL_REF:
216 return true;
218 case PC:
219 case CC0:
220 case UNSPEC_VOLATILE:
221 case CALL:
222 return false;
224 case REG:
225 return true;
227 case MEM:
228 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
229 It should not be hard, and might be faster than "elsewhere". */
231 /* Just handle the most trivial case where we load from an unchanging
232 location (most importantly, pic tables). */
233 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
234 break;
236 return false;
238 case ASM_OPERANDS:
239 /* Don't mess with insns declared volatile. */
240 if (MEM_VOLATILE_P (x))
241 return false;
242 break;
244 default:
245 break;
248 fmt = GET_RTX_FORMAT (code);
249 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
251 if (fmt[i] == 'e')
253 if (!check_maybe_invariant (XEXP (x, i)))
254 return false;
256 else if (fmt[i] == 'E')
258 for (j = 0; j < XVECLEN (x, i); j++)
259 if (!check_maybe_invariant (XVECEXP (x, i, j)))
260 return false;
264 return true;
267 /* Returns the invariant definition for USE, or NULL if USE is not
268 invariant. */
270 static struct invariant *
271 invariant_for_use (df_ref use)
273 struct df_link *defs;
274 df_ref def;
275 basic_block bb = DF_REF_BB (use), def_bb;
277 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
278 return NULL;
280 defs = DF_REF_CHAIN (use);
281 if (!defs || defs->next)
282 return NULL;
283 def = defs->ref;
284 check_invariant_table_size ();
285 if (!invariant_table[DF_REF_ID (def)])
286 return NULL;
288 def_bb = DF_REF_BB (def);
289 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
290 return NULL;
291 return invariant_table[DF_REF_ID (def)];
294 /* Computes hash value for invariant expression X in INSN. */
296 static hashval_t
297 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
299 enum rtx_code code = GET_CODE (x);
300 int i, j;
301 const char *fmt;
302 hashval_t val = code;
303 int do_not_record_p;
304 df_ref use;
305 struct invariant *inv;
307 switch (code)
309 CASE_CONST_ANY:
310 case SYMBOL_REF:
311 case CONST:
312 case LABEL_REF:
313 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
315 case REG:
316 use = df_find_use (insn, x);
317 if (!use)
318 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
319 inv = invariant_for_use (use);
320 if (!inv)
321 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
323 gcc_assert (inv->eqto != ~0u);
324 return inv->eqto;
326 default:
327 break;
330 fmt = GET_RTX_FORMAT (code);
331 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
333 if (fmt[i] == 'e')
334 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
335 else if (fmt[i] == 'E')
337 for (j = 0; j < XVECLEN (x, i); j++)
338 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
340 else if (fmt[i] == 'i' || fmt[i] == 'n')
341 val ^= XINT (x, i);
344 return val;
347 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
348 and INSN2 have always the same value. */
350 static bool
351 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
353 enum rtx_code code = GET_CODE (e1);
354 int i, j;
355 const char *fmt;
356 df_ref use1, use2;
357 struct invariant *inv1 = NULL, *inv2 = NULL;
358 rtx sub1, sub2;
360 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
361 the other one. If both are VOIDmode, we rely on the caller of this
362 function to verify that their modes are the same. */
363 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
364 return false;
366 switch (code)
368 CASE_CONST_ANY:
369 case SYMBOL_REF:
370 case CONST:
371 case LABEL_REF:
372 return rtx_equal_p (e1, e2);
374 case REG:
375 use1 = df_find_use (insn1, e1);
376 use2 = df_find_use (insn2, e2);
377 if (use1)
378 inv1 = invariant_for_use (use1);
379 if (use2)
380 inv2 = invariant_for_use (use2);
382 if (!inv1 && !inv2)
383 return rtx_equal_p (e1, e2);
385 if (!inv1 || !inv2)
386 return false;
388 gcc_assert (inv1->eqto != ~0u);
389 gcc_assert (inv2->eqto != ~0u);
390 return inv1->eqto == inv2->eqto;
392 default:
393 break;
396 fmt = GET_RTX_FORMAT (code);
397 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
399 if (fmt[i] == 'e')
401 sub1 = XEXP (e1, i);
402 sub2 = XEXP (e2, i);
404 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
405 return false;
408 else if (fmt[i] == 'E')
410 if (XVECLEN (e1, i) != XVECLEN (e2, i))
411 return false;
413 for (j = 0; j < XVECLEN (e1, i); j++)
415 sub1 = XVECEXP (e1, i, j);
416 sub2 = XVECEXP (e2, i, j);
418 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
419 return false;
422 else if (fmt[i] == 'i' || fmt[i] == 'n')
424 if (XINT (e1, i) != XINT (e2, i))
425 return false;
427 /* Unhandled type of subexpression, we fail conservatively. */
428 else
429 return false;
432 return true;
435 struct invariant_expr_hasher : typed_free_remove <invariant_expr_entry>
437 typedef invariant_expr_entry value_type;
438 typedef invariant_expr_entry compare_type;
439 static inline hashval_t hash (const value_type *);
440 static inline bool equal (const value_type *, const compare_type *);
443 /* Returns hash value for invariant expression entry ENTRY. */
445 inline hashval_t
446 invariant_expr_hasher::hash (const value_type *entry)
448 return entry->hash;
451 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
453 inline bool
454 invariant_expr_hasher::equal (const value_type *entry1,
455 const compare_type *entry2)
457 if (entry1->mode != entry2->mode)
458 return 0;
460 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
461 entry2->inv->insn, entry2->expr);
464 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
466 /* Checks whether invariant with value EXPR in machine mode MODE is
467 recorded in EQ. If this is the case, return the invariant. Otherwise
468 insert INV to the table for this expression and return INV. */
470 static struct invariant *
471 find_or_insert_inv (invariant_htab_type *eq, rtx expr, enum machine_mode mode,
472 struct invariant *inv)
474 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
475 struct invariant_expr_entry *entry;
476 struct invariant_expr_entry pentry;
477 invariant_expr_entry **slot;
479 pentry.expr = expr;
480 pentry.inv = inv;
481 pentry.mode = mode;
482 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
483 entry = *slot;
485 if (entry)
486 return entry->inv;
488 entry = XNEW (struct invariant_expr_entry);
489 entry->inv = inv;
490 entry->expr = expr;
491 entry->mode = mode;
492 entry->hash = hash;
493 *slot = entry;
495 return inv;
498 /* Finds invariants identical to INV and records the equivalence. EQ is the
499 hash table of the invariants. */
501 static void
502 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
504 unsigned depno;
505 bitmap_iterator bi;
506 struct invariant *dep;
507 rtx expr, set;
508 enum machine_mode mode;
509 struct invariant *tmp;
511 if (inv->eqto != ~0u)
512 return;
514 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
516 dep = invariants[depno];
517 find_identical_invariants (eq, dep);
520 set = single_set (inv->insn);
521 expr = SET_SRC (set);
522 mode = GET_MODE (expr);
523 if (mode == VOIDmode)
524 mode = GET_MODE (SET_DEST (set));
526 tmp = find_or_insert_inv (eq, expr, mode, inv);
527 inv->eqto = tmp->invno;
529 if (tmp->invno != inv->invno && inv->always_executed)
530 tmp->eqno++;
532 if (dump_file && inv->eqto != inv->invno)
533 fprintf (dump_file,
534 "Invariant %d is equivalent to invariant %d.\n",
535 inv->invno, inv->eqto);
538 /* Find invariants with the same value and record the equivalences. */
540 static void
541 merge_identical_invariants (void)
543 unsigned i;
544 struct invariant *inv;
545 invariant_htab_type eq (invariants.length ());
547 FOR_EACH_VEC_ELT (invariants, i, inv)
548 find_identical_invariants (&eq, inv);
551 /* Determines the basic blocks inside LOOP that are always executed and
552 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
553 basic blocks that may either exit the loop, or contain the call that
554 does not have to return. BODY is body of the loop obtained by
555 get_loop_body_in_dom_order. */
557 static void
558 compute_always_reached (struct loop *loop, basic_block *body,
559 bitmap may_exit, bitmap always_reached)
561 unsigned i;
563 for (i = 0; i < loop->num_nodes; i++)
565 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
566 bitmap_set_bit (always_reached, i);
568 if (bitmap_bit_p (may_exit, i))
569 return;
573 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
574 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
575 additionally mark blocks that may exit due to a call. */
577 static void
578 find_exits (struct loop *loop, basic_block *body,
579 bitmap may_exit, bitmap has_exit)
581 unsigned i;
582 edge_iterator ei;
583 edge e;
584 struct loop *outermost_exit = loop, *aexit;
585 bool has_call = false;
586 rtx_insn *insn;
588 for (i = 0; i < loop->num_nodes; i++)
590 if (body[i]->loop_father == loop)
592 FOR_BB_INSNS (body[i], insn)
594 if (CALL_P (insn)
595 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
596 || !RTL_CONST_OR_PURE_CALL_P (insn)))
598 has_call = true;
599 bitmap_set_bit (may_exit, i);
600 break;
604 FOR_EACH_EDGE (e, ei, body[i]->succs)
606 if (flow_bb_inside_loop_p (loop, e->dest))
607 continue;
609 bitmap_set_bit (may_exit, i);
610 bitmap_set_bit (has_exit, i);
611 outermost_exit = find_common_loop (outermost_exit,
612 e->dest->loop_father);
614 continue;
617 /* Use the data stored for the subloop to decide whether we may exit
618 through it. It is sufficient to do this for header of the loop,
619 as other basic blocks inside it must be dominated by it. */
620 if (body[i]->loop_father->header != body[i])
621 continue;
623 if (LOOP_DATA (body[i]->loop_father)->has_call)
625 has_call = true;
626 bitmap_set_bit (may_exit, i);
628 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
629 if (aexit != loop)
631 bitmap_set_bit (may_exit, i);
632 bitmap_set_bit (has_exit, i);
634 if (flow_loop_nested_p (aexit, outermost_exit))
635 outermost_exit = aexit;
639 if (loop->aux == NULL)
641 loop->aux = xcalloc (1, sizeof (struct loop_data));
642 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
643 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
645 LOOP_DATA (loop)->outermost_exit = outermost_exit;
646 LOOP_DATA (loop)->has_call = has_call;
649 /* Check whether we may assign a value to X from a register. */
651 static bool
652 may_assign_reg_p (rtx x)
654 return (GET_MODE (x) != VOIDmode
655 && GET_MODE (x) != BLKmode
656 && can_copy_p (GET_MODE (x))
657 && (!REG_P (x)
658 || !HARD_REGISTER_P (x)
659 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
662 /* Finds definitions that may correspond to invariants in LOOP with body
663 BODY. */
665 static void
666 find_defs (struct loop *loop)
668 if (dump_file)
670 fprintf (dump_file,
671 "*****starting processing of loop %d ******\n",
672 loop->num);
675 df_remove_problem (df_chain);
676 df_process_deferred_rescans ();
677 df_chain_add_problem (DF_UD_CHAIN);
678 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
679 df_analyze_loop (loop);
680 check_invariant_table_size ();
682 if (dump_file)
684 df_dump_region (dump_file);
685 fprintf (dump_file,
686 "*****ending processing of loop %d ******\n",
687 loop->num);
691 /* Creates a new invariant for definition DEF in INSN, depending on invariants
692 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
693 unless the program ends due to a function call. The newly created invariant
694 is returned. */
696 static struct invariant *
697 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
698 bool always_executed)
700 struct invariant *inv = XNEW (struct invariant);
701 rtx set = single_set (insn);
702 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
704 inv->def = def;
705 inv->always_executed = always_executed;
706 inv->depends_on = depends_on;
708 /* If the set is simple, usually by moving it we move the whole store out of
709 the loop. Otherwise we save only cost of the computation. */
710 if (def)
712 inv->cost = set_rtx_cost (set, speed);
713 /* ??? Try to determine cheapness of address computation. Unfortunately
714 the address cost is only a relative measure, we can't really compare
715 it with any absolute number, but only with other address costs.
716 But here we don't have any other addresses, so compare with a magic
717 number anyway. It has to be large enough to not regress PR33928
718 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
719 enough to not regress 410.bwaves either (by still moving reg+reg
720 invariants).
721 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
722 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
723 ADDR_SPACE_GENERIC, speed) < 3;
725 else
727 inv->cost = set_src_cost (SET_SRC (set), speed);
728 inv->cheap_address = false;
731 inv->move = false;
732 inv->reg = NULL_RTX;
733 inv->orig_regno = -1;
734 inv->stamp = 0;
735 inv->insn = insn;
737 inv->invno = invariants.length ();
738 inv->eqto = ~0u;
740 /* Itself. */
741 inv->eqno = 1;
743 if (def)
744 def->invno = inv->invno;
745 invariants.safe_push (inv);
747 if (dump_file)
749 fprintf (dump_file,
750 "Set in insn %d is invariant (%d), cost %d, depends on ",
751 INSN_UID (insn), inv->invno, inv->cost);
752 dump_bitmap (dump_file, inv->depends_on);
755 return inv;
758 /* Record USE at DEF. */
760 static void
761 record_use (struct def *def, df_ref use)
763 struct use *u = XNEW (struct use);
765 u->pos = DF_REF_REAL_LOC (use);
766 u->insn = DF_REF_INSN (use);
767 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
768 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
769 u->next = def->uses;
770 def->uses = u;
771 def->n_uses++;
772 if (u->addr_use_p)
773 def->n_addr_uses++;
776 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
777 bitmap. Returns true if all dependencies of USE are known to be
778 loop invariants, false otherwise. */
780 static bool
781 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
783 df_ref def;
784 basic_block def_bb;
785 struct df_link *defs;
786 struct def *def_data;
787 struct invariant *inv;
789 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
790 return false;
792 defs = DF_REF_CHAIN (use);
793 if (!defs)
795 unsigned int regno = DF_REF_REGNO (use);
797 /* If this is the use of an uninitialized argument register that is
798 likely to be spilled, do not move it lest this might extend its
799 lifetime and cause reload to die. This can occur for a call to
800 a function taking complex number arguments and moving the insns
801 preparing the arguments without moving the call itself wouldn't
802 gain much in practice. */
803 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
804 && FUNCTION_ARG_REGNO_P (regno)
805 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
806 return false;
808 return true;
811 if (defs->next)
812 return false;
814 def = defs->ref;
815 check_invariant_table_size ();
816 inv = invariant_table[DF_REF_ID (def)];
817 if (!inv)
818 return false;
820 def_data = inv->def;
821 gcc_assert (def_data != NULL);
823 def_bb = DF_REF_BB (def);
824 /* Note that in case bb == def_bb, we know that the definition
825 dominates insn, because def has invariant_table[DF_REF_ID(def)]
826 defined and we process the insns in the basic block bb
827 sequentially. */
828 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
829 return false;
831 bitmap_set_bit (depends_on, def_data->invno);
832 return true;
836 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
837 bitmap. Returns true if all dependencies of INSN are known to be
838 loop invariants, false otherwise. */
840 static bool
841 check_dependencies (rtx_insn *insn, bitmap depends_on)
843 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844 df_ref use;
845 basic_block bb = BLOCK_FOR_INSN (insn);
847 FOR_EACH_INSN_INFO_USE (use, insn_info)
848 if (!check_dependency (bb, use, depends_on))
849 return false;
850 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
851 if (!check_dependency (bb, use, depends_on))
852 return false;
854 return true;
857 /* Pre-check candidate DEST to skip the one which can not make a valid insn
858 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
859 static bool
860 pre_check_invariant_p (bool simple, rtx dest)
862 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
864 df_ref use;
865 rtx ref;
866 unsigned int i = REGNO (dest);
867 struct df_insn_info *insn_info;
868 df_ref def_rec;
870 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
872 ref = DF_REF_INSN (use);
873 insn_info = DF_INSN_INFO_GET (ref);
875 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
876 if (DF_REF_REGNO (def_rec) == i)
878 /* Multi definitions at this stage, most likely are due to
879 instruction constraints, which requires both read and write
880 on the same register. Since move_invariant_reg is not
881 powerful enough to handle such cases, just ignore the INV
882 and leave the chance to others. */
883 return false;
887 return true;
890 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
891 executed. ALWAYS_EXECUTED is true if the insn is always executed,
892 unless the program ends due to a function call. */
894 static void
895 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
897 df_ref ref;
898 struct def *def;
899 bitmap depends_on;
900 rtx set, dest;
901 bool simple = true;
902 struct invariant *inv;
904 #ifdef HAVE_cc0
905 /* We can't move a CC0 setter without the user. */
906 if (sets_cc0_p (insn))
907 return;
908 #endif
910 set = single_set (insn);
911 if (!set)
912 return;
913 dest = SET_DEST (set);
915 if (!REG_P (dest)
916 || HARD_REGISTER_P (dest))
917 simple = false;
919 if (!may_assign_reg_p (dest)
920 || !pre_check_invariant_p (simple, dest)
921 || !check_maybe_invariant (SET_SRC (set)))
922 return;
924 /* If the insn can throw exception, we cannot move it at all without changing
925 cfg. */
926 if (can_throw_internal (insn))
927 return;
929 /* We cannot make trapping insn executed, unless it was executed before. */
930 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
931 return;
933 depends_on = BITMAP_ALLOC (NULL);
934 if (!check_dependencies (insn, depends_on))
936 BITMAP_FREE (depends_on);
937 return;
940 if (simple)
941 def = XCNEW (struct def);
942 else
943 def = NULL;
945 inv = create_new_invariant (def, insn, depends_on, always_executed);
947 if (simple)
949 ref = df_find_def (insn, dest);
950 check_invariant_table_size ();
951 invariant_table[DF_REF_ID (ref)] = inv;
955 /* Record registers used in INSN that have a unique invariant definition. */
957 static void
958 record_uses (rtx_insn *insn)
960 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
961 df_ref use;
962 struct invariant *inv;
964 FOR_EACH_INSN_INFO_USE (use, insn_info)
966 inv = invariant_for_use (use);
967 if (inv)
968 record_use (inv->def, use);
970 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
972 inv = invariant_for_use (use);
973 if (inv)
974 record_use (inv->def, use);
978 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
979 executed. ALWAYS_EXECUTED is true if the insn is always executed,
980 unless the program ends due to a function call. */
982 static void
983 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
985 find_invariant_insn (insn, always_reached, always_executed);
986 record_uses (insn);
989 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
990 basic block is always executed. ALWAYS_EXECUTED is true if the basic
991 block is always executed, unless the program ends due to a function
992 call. */
994 static void
995 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
997 rtx_insn *insn;
999 FOR_BB_INSNS (bb, insn)
1001 if (!NONDEBUG_INSN_P (insn))
1002 continue;
1004 find_invariants_insn (insn, always_reached, always_executed);
1006 if (always_reached
1007 && CALL_P (insn)
1008 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1009 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1010 always_reached = false;
1014 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1015 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1016 bitmap of basic blocks in BODY that are always executed unless the program
1017 ends due to a function call. */
1019 static void
1020 find_invariants_body (struct loop *loop, basic_block *body,
1021 bitmap always_reached, bitmap always_executed)
1023 unsigned i;
1025 for (i = 0; i < loop->num_nodes; i++)
1026 find_invariants_bb (body[i],
1027 bitmap_bit_p (always_reached, i),
1028 bitmap_bit_p (always_executed, i));
1031 /* Finds invariants in LOOP. */
1033 static void
1034 find_invariants (struct loop *loop)
1036 bitmap may_exit = BITMAP_ALLOC (NULL);
1037 bitmap always_reached = BITMAP_ALLOC (NULL);
1038 bitmap has_exit = BITMAP_ALLOC (NULL);
1039 bitmap always_executed = BITMAP_ALLOC (NULL);
1040 basic_block *body = get_loop_body_in_dom_order (loop);
1042 find_exits (loop, body, may_exit, has_exit);
1043 compute_always_reached (loop, body, may_exit, always_reached);
1044 compute_always_reached (loop, body, has_exit, always_executed);
1046 find_defs (loop);
1047 find_invariants_body (loop, body, always_reached, always_executed);
1048 merge_identical_invariants ();
1050 BITMAP_FREE (always_reached);
1051 BITMAP_FREE (always_executed);
1052 BITMAP_FREE (may_exit);
1053 BITMAP_FREE (has_exit);
1054 free (body);
1057 /* Frees a list of uses USE. */
1059 static void
1060 free_use_list (struct use *use)
1062 struct use *next;
1064 for (; use; use = next)
1066 next = use->next;
1067 free (use);
1071 /* Return pressure class and number of hard registers (through *NREGS)
1072 for destination of INSN. */
1073 static enum reg_class
1074 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1076 rtx reg;
1077 enum reg_class pressure_class;
1078 rtx set = single_set (insn);
1080 /* Considered invariant insns have only one set. */
1081 gcc_assert (set != NULL_RTX);
1082 reg = SET_DEST (set);
1083 if (GET_CODE (reg) == SUBREG)
1084 reg = SUBREG_REG (reg);
1085 if (MEM_P (reg))
1087 *nregs = 0;
1088 pressure_class = NO_REGS;
1090 else
1092 if (! REG_P (reg))
1093 reg = NULL_RTX;
1094 if (reg == NULL_RTX)
1095 pressure_class = GENERAL_REGS;
1096 else
1098 pressure_class = reg_allocno_class (REGNO (reg));
1099 pressure_class = ira_pressure_class_translate[pressure_class];
1101 *nregs
1102 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1104 return pressure_class;
1107 /* Calculates cost and number of registers needed for moving invariant INV
1108 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1109 the REG_CLASS of INV. Return
1110 -1: if INV is invalid.
1111 0: if INV and its depends_on have same reg_class
1112 1: if INV and its depends_on have different reg_classes. */
1114 static int
1115 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1116 enum reg_class *cl)
1118 int i, acomp_cost;
1119 unsigned aregs_needed[N_REG_CLASSES];
1120 unsigned depno;
1121 struct invariant *dep;
1122 bitmap_iterator bi;
1123 int ret = 1;
1125 /* Find the representative of the class of the equivalent invariants. */
1126 inv = invariants[inv->eqto];
1128 *comp_cost = 0;
1129 if (! flag_ira_loop_pressure)
1130 regs_needed[0] = 0;
1131 else
1133 for (i = 0; i < ira_pressure_classes_num; i++)
1134 regs_needed[ira_pressure_classes[i]] = 0;
1137 if (inv->move
1138 || inv->stamp == actual_stamp)
1139 return -1;
1140 inv->stamp = actual_stamp;
1142 if (! flag_ira_loop_pressure)
1143 regs_needed[0]++;
1144 else
1146 int nregs;
1147 enum reg_class pressure_class;
1149 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1150 regs_needed[pressure_class] += nregs;
1151 *cl = pressure_class;
1152 ret = 0;
1155 if (!inv->cheap_address
1156 || inv->def->n_addr_uses < inv->def->n_uses)
1157 (*comp_cost) += inv->cost * inv->eqno;
1159 #ifdef STACK_REGS
1161 /* Hoisting constant pool constants into stack regs may cost more than
1162 just single register. On x87, the balance is affected both by the
1163 small number of FP registers, and by its register stack organization,
1164 that forces us to add compensation code in and around the loop to
1165 shuffle the operands to the top of stack before use, and pop them
1166 from the stack after the loop finishes.
1168 To model this effect, we increase the number of registers needed for
1169 stack registers by two: one register push, and one register pop.
1170 This usually has the effect that FP constant loads from the constant
1171 pool are not moved out of the loop.
1173 Note that this also means that dependent invariants can not be moved.
1174 However, the primary purpose of this pass is to move loop invariant
1175 address arithmetic out of loops, and address arithmetic that depends
1176 on floating point constants is unlikely to ever occur. */
1177 rtx set = single_set (inv->insn);
1178 if (set
1179 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1180 && constant_pool_constant_p (SET_SRC (set)))
1182 if (flag_ira_loop_pressure)
1183 regs_needed[ira_stack_reg_pressure_class] += 2;
1184 else
1185 regs_needed[0] += 2;
1188 #endif
1190 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1192 bool check_p;
1193 enum reg_class dep_cl = ALL_REGS;
1194 int dep_ret;
1196 dep = invariants[depno];
1198 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1199 if (dep->move)
1200 continue;
1202 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1204 if (! flag_ira_loop_pressure)
1205 check_p = aregs_needed[0] != 0;
1206 else
1208 for (i = 0; i < ira_pressure_classes_num; i++)
1209 if (aregs_needed[ira_pressure_classes[i]] != 0)
1210 break;
1211 check_p = i < ira_pressure_classes_num;
1213 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1215 *cl = ALL_REGS;
1216 ret = 1;
1219 if (check_p
1220 /* We need to check always_executed, since if the original value of
1221 the invariant may be preserved, we may need to keep it in a
1222 separate register. TODO check whether the register has an
1223 use outside of the loop. */
1224 && dep->always_executed
1225 && !dep->def->uses->next)
1227 /* If this is a single use, after moving the dependency we will not
1228 need a new register. */
1229 if (! flag_ira_loop_pressure)
1230 aregs_needed[0]--;
1231 else
1233 int nregs;
1234 enum reg_class pressure_class;
1236 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1237 aregs_needed[pressure_class] -= nregs;
1241 if (! flag_ira_loop_pressure)
1242 regs_needed[0] += aregs_needed[0];
1243 else
1245 for (i = 0; i < ira_pressure_classes_num; i++)
1246 regs_needed[ira_pressure_classes[i]]
1247 += aregs_needed[ira_pressure_classes[i]];
1249 (*comp_cost) += acomp_cost;
1251 return ret;
1254 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1255 of registers used in the loop, NEW_REGS is the number of new variables
1256 already added due to the invariant motion. The number of registers needed
1257 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1258 through to estimate_reg_pressure_cost. */
1260 static int
1261 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1262 unsigned *new_regs, unsigned regs_used,
1263 bool speed, bool call_p)
1265 int comp_cost, size_cost;
1266 enum reg_class cl;
1267 int ret;
1269 actual_stamp++;
1271 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1273 if (! flag_ira_loop_pressure)
1275 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1276 regs_used, speed, call_p)
1277 - estimate_reg_pressure_cost (new_regs[0],
1278 regs_used, speed, call_p));
1280 else if (ret < 0)
1281 return -1;
1282 else if ((ret == 0) && (cl == NO_REGS))
1283 /* Hoist it anyway since it does not impact register pressure. */
1284 return 1;
1285 else
1287 int i;
1288 enum reg_class pressure_class;
1290 for (i = 0; i < ira_pressure_classes_num; i++)
1292 pressure_class = ira_pressure_classes[i];
1294 if (!reg_classes_intersect_p (pressure_class, cl))
1295 continue;
1297 if ((int) new_regs[pressure_class]
1298 + (int) regs_needed[pressure_class]
1299 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1300 + IRA_LOOP_RESERVED_REGS
1301 > ira_class_hard_regs_num[pressure_class])
1302 break;
1304 if (i < ira_pressure_classes_num)
1305 /* There will be register pressure excess and we want not to
1306 make this loop invariant motion. All loop invariants with
1307 non-positive gains will be rejected in function
1308 find_invariants_to_move. Therefore we return the negative
1309 number here.
1311 One could think that this rejects also expensive loop
1312 invariant motions and this will hurt code performance.
1313 However numerous experiments with different heuristics
1314 taking invariant cost into account did not confirm this
1315 assumption. There are possible explanations for this
1316 result:
1317 o probably all expensive invariants were already moved out
1318 of the loop by PRE and gimple invariant motion pass.
1319 o expensive invariant execution will be hidden by insn
1320 scheduling or OOO processor hardware because usually such
1321 invariants have a lot of freedom to be executed
1322 out-of-order.
1323 Another reason for ignoring invariant cost vs spilling cost
1324 heuristics is also in difficulties to evaluate accurately
1325 spill cost at this stage. */
1326 return -1;
1327 else
1328 size_cost = 0;
1331 return comp_cost - size_cost;
1334 /* Finds invariant with best gain for moving. Returns the gain, stores
1335 the invariant in *BEST and number of registers needed for it to
1336 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1337 NEW_REGS is the number of new variables already added due to invariant
1338 motion. */
1340 static int
1341 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1342 unsigned *new_regs, unsigned regs_used,
1343 bool speed, bool call_p)
1345 struct invariant *inv;
1346 int i, gain = 0, again;
1347 unsigned aregs_needed[N_REG_CLASSES], invno;
1349 FOR_EACH_VEC_ELT (invariants, invno, inv)
1351 if (inv->move)
1352 continue;
1354 /* Only consider the "representatives" of equivalent invariants. */
1355 if (inv->eqto != inv->invno)
1356 continue;
1358 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1359 speed, call_p);
1360 if (again > gain)
1362 gain = again;
1363 *best = inv;
1364 if (! flag_ira_loop_pressure)
1365 regs_needed[0] = aregs_needed[0];
1366 else
1368 for (i = 0; i < ira_pressure_classes_num; i++)
1369 regs_needed[ira_pressure_classes[i]]
1370 = aregs_needed[ira_pressure_classes[i]];
1375 return gain;
1378 /* Marks invariant INVNO and all its dependencies for moving. */
1380 static void
1381 set_move_mark (unsigned invno, int gain)
1383 struct invariant *inv = invariants[invno];
1384 bitmap_iterator bi;
1386 /* Find the representative of the class of the equivalent invariants. */
1387 inv = invariants[inv->eqto];
1389 if (inv->move)
1390 return;
1391 inv->move = true;
1393 if (dump_file)
1395 if (gain >= 0)
1396 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1397 invno, gain);
1398 else
1399 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1400 invno);
1403 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1405 set_move_mark (invno, -1);
1409 /* Determines which invariants to move. */
1411 static void
1412 find_invariants_to_move (bool speed, bool call_p)
1414 int gain;
1415 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1416 struct invariant *inv = NULL;
1418 if (!invariants.length ())
1419 return;
1421 if (flag_ira_loop_pressure)
1422 /* REGS_USED is actually never used when the flag is on. */
1423 regs_used = 0;
1424 else
1425 /* We do not really do a good job in estimating number of
1426 registers used; we put some initial bound here to stand for
1427 induction variables etc. that we do not detect. */
1429 unsigned int n_regs = DF_REG_SIZE (df);
1431 regs_used = 2;
1433 for (i = 0; i < n_regs; i++)
1435 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1437 /* This is a value that is used but not changed inside loop. */
1438 regs_used++;
1443 if (! flag_ira_loop_pressure)
1444 new_regs[0] = regs_needed[0] = 0;
1445 else
1447 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1448 new_regs[ira_pressure_classes[i]] = 0;
1450 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1451 new_regs, regs_used,
1452 speed, call_p)) > 0)
1454 set_move_mark (inv->invno, gain);
1455 if (! flag_ira_loop_pressure)
1456 new_regs[0] += regs_needed[0];
1457 else
1459 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1460 new_regs[ira_pressure_classes[i]]
1461 += regs_needed[ira_pressure_classes[i]];
1466 /* Replace the uses, reached by the definition of invariant INV, by REG.
1468 IN_GROUP is nonzero if this is part of a group of changes that must be
1469 performed as a group. In that case, the changes will be stored. The
1470 function `apply_change_group' will validate and apply the changes. */
1472 static int
1473 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1475 /* Replace the uses we know to be dominated. It saves work for copy
1476 propagation, and also it is necessary so that dependent invariants
1477 are computed right. */
1478 if (inv->def)
1480 struct use *use;
1481 for (use = inv->def->uses; use; use = use->next)
1482 validate_change (use->insn, use->pos, reg, true);
1484 /* If we aren't part of a larger group, apply the changes now. */
1485 if (!in_group)
1486 return apply_change_group ();
1489 return 1;
1492 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1493 otherwise. */
1495 static bool
1496 move_invariant_reg (struct loop *loop, unsigned invno)
1498 struct invariant *inv = invariants[invno];
1499 struct invariant *repr = invariants[inv->eqto];
1500 unsigned i;
1501 basic_block preheader = loop_preheader_edge (loop)->src;
1502 rtx reg, set, dest, note;
1503 bitmap_iterator bi;
1504 int regno = -1;
1506 if (inv->reg)
1507 return true;
1508 if (!repr->move)
1509 return false;
1511 /* If this is a representative of the class of equivalent invariants,
1512 really move the invariant. Otherwise just replace its use with
1513 the register used for the representative. */
1514 if (inv == repr)
1516 if (inv->depends_on)
1518 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1520 if (!move_invariant_reg (loop, i))
1521 goto fail;
1525 /* Move the set out of the loop. If the set is always executed (we could
1526 omit this condition if we know that the register is unused outside of
1527 the loop, but it does not seem worth finding out) and it has no uses
1528 that would not be dominated by it, we may just move it (TODO).
1529 Otherwise we need to create a temporary register. */
1530 set = single_set (inv->insn);
1531 reg = dest = SET_DEST (set);
1532 if (GET_CODE (reg) == SUBREG)
1533 reg = SUBREG_REG (reg);
1534 if (REG_P (reg))
1535 regno = REGNO (reg);
1537 reg = gen_reg_rtx_and_attrs (dest);
1539 /* Try replacing the destination by a new pseudoregister. */
1540 validate_change (inv->insn, &SET_DEST (set), reg, true);
1542 /* As well as all the dominated uses. */
1543 replace_uses (inv, reg, true);
1545 /* And validate all the changes. */
1546 if (!apply_change_group ())
1547 goto fail;
1549 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1550 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1552 /* If there is a REG_EQUAL note on the insn we just moved, and the
1553 insn is in a basic block that is not always executed or the note
1554 contains something for which we don't know the invariant status,
1555 the note may no longer be valid after we move the insn. Note that
1556 uses in REG_EQUAL notes are taken into account in the computation
1557 of invariants, so it is safe to retain the note even if it contains
1558 register references for which we know the invariant status. */
1559 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1560 && (!inv->always_executed
1561 || !check_maybe_invariant (XEXP (note, 0))))
1562 remove_note (inv->insn, note);
1564 else
1566 if (!move_invariant_reg (loop, repr->invno))
1567 goto fail;
1568 reg = repr->reg;
1569 regno = repr->orig_regno;
1570 if (!replace_uses (inv, reg, false))
1571 goto fail;
1572 set = single_set (inv->insn);
1573 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1574 delete_insn (inv->insn);
1577 inv->reg = reg;
1578 inv->orig_regno = regno;
1580 return true;
1582 fail:
1583 /* If we failed, clear move flag, so that we do not try to move inv
1584 again. */
1585 if (dump_file)
1586 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1587 inv->move = false;
1588 inv->reg = NULL_RTX;
1589 inv->orig_regno = -1;
1591 return false;
1594 /* Move selected invariant out of the LOOP. Newly created regs are marked
1595 in TEMPORARY_REGS. */
1597 static void
1598 move_invariants (struct loop *loop)
1600 struct invariant *inv;
1601 unsigned i;
1603 FOR_EACH_VEC_ELT (invariants, i, inv)
1604 move_invariant_reg (loop, i);
1605 if (flag_ira_loop_pressure && resize_reg_info ())
1607 FOR_EACH_VEC_ELT (invariants, i, inv)
1608 if (inv->reg != NULL_RTX)
1610 if (inv->orig_regno >= 0)
1611 setup_reg_classes (REGNO (inv->reg),
1612 reg_preferred_class (inv->orig_regno),
1613 reg_alternate_class (inv->orig_regno),
1614 reg_allocno_class (inv->orig_regno));
1615 else
1616 setup_reg_classes (REGNO (inv->reg),
1617 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1622 /* Initializes invariant motion data. */
1624 static void
1625 init_inv_motion_data (void)
1627 actual_stamp = 1;
1629 invariants.create (100);
1632 /* Frees the data allocated by invariant motion. */
1634 static void
1635 free_inv_motion_data (void)
1637 unsigned i;
1638 struct def *def;
1639 struct invariant *inv;
1641 check_invariant_table_size ();
1642 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1644 inv = invariant_table[i];
1645 if (inv)
1647 def = inv->def;
1648 gcc_assert (def != NULL);
1650 free_use_list (def->uses);
1651 free (def);
1652 invariant_table[i] = NULL;
1656 FOR_EACH_VEC_ELT (invariants, i, inv)
1658 BITMAP_FREE (inv->depends_on);
1659 free (inv);
1661 invariants.release ();
1664 /* Move the invariants out of the LOOP. */
1666 static void
1667 move_single_loop_invariants (struct loop *loop)
1669 init_inv_motion_data ();
1671 find_invariants (loop);
1672 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1673 LOOP_DATA (loop)->has_call);
1674 move_invariants (loop);
1676 free_inv_motion_data ();
1679 /* Releases the auxiliary data for LOOP. */
1681 static void
1682 free_loop_data (struct loop *loop)
1684 struct loop_data *data = LOOP_DATA (loop);
1685 if (!data)
1686 return;
1688 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1689 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1690 free (data);
1691 loop->aux = NULL;
1696 /* Registers currently living. */
1697 static bitmap_head curr_regs_live;
1699 /* Current reg pressure for each pressure class. */
1700 static int curr_reg_pressure[N_REG_CLASSES];
1702 /* Record all regs that are set in any one insn. Communication from
1703 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1704 all hard-registers. */
1705 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1706 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1707 /* Number of regs stored in the previous array. */
1708 static int n_regs_set;
1710 /* Return pressure class and number of needed hard registers (through
1711 *NREGS) of register REGNO. */
1712 static enum reg_class
1713 get_regno_pressure_class (int regno, int *nregs)
1715 if (regno >= FIRST_PSEUDO_REGISTER)
1717 enum reg_class pressure_class;
1719 pressure_class = reg_allocno_class (regno);
1720 pressure_class = ira_pressure_class_translate[pressure_class];
1721 *nregs
1722 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1723 return pressure_class;
1725 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1726 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1728 *nregs = 1;
1729 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1731 else
1733 *nregs = 0;
1734 return NO_REGS;
1738 /* Increase (if INCR_P) or decrease current register pressure for
1739 register REGNO. */
1740 static void
1741 change_pressure (int regno, bool incr_p)
1743 int nregs;
1744 enum reg_class pressure_class;
1746 pressure_class = get_regno_pressure_class (regno, &nregs);
1747 if (! incr_p)
1748 curr_reg_pressure[pressure_class] -= nregs;
1749 else
1751 curr_reg_pressure[pressure_class] += nregs;
1752 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1753 < curr_reg_pressure[pressure_class])
1754 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1755 = curr_reg_pressure[pressure_class];
1759 /* Mark REGNO birth. */
1760 static void
1761 mark_regno_live (int regno)
1763 struct loop *loop;
1765 for (loop = curr_loop;
1766 loop != current_loops->tree_root;
1767 loop = loop_outer (loop))
1768 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
1769 if (!bitmap_set_bit (&curr_regs_live, regno))
1770 return;
1771 change_pressure (regno, true);
1774 /* Mark REGNO death. */
1775 static void
1776 mark_regno_death (int regno)
1778 if (! bitmap_clear_bit (&curr_regs_live, regno))
1779 return;
1780 change_pressure (regno, false);
1783 /* Mark setting register REG. */
1784 static void
1785 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1786 void *data ATTRIBUTE_UNUSED)
1788 int regno;
1790 if (GET_CODE (reg) == SUBREG)
1791 reg = SUBREG_REG (reg);
1793 if (! REG_P (reg))
1794 return;
1796 regs_set[n_regs_set++] = reg;
1798 regno = REGNO (reg);
1800 if (regno >= FIRST_PSEUDO_REGISTER)
1801 mark_regno_live (regno);
1802 else
1804 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1806 while (regno < last)
1808 mark_regno_live (regno);
1809 regno++;
1814 /* Mark clobbering register REG. */
1815 static void
1816 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1818 if (GET_CODE (setter) == CLOBBER)
1819 mark_reg_store (reg, setter, data);
1822 /* Mark register REG death. */
1823 static void
1824 mark_reg_death (rtx reg)
1826 int regno = REGNO (reg);
1828 if (regno >= FIRST_PSEUDO_REGISTER)
1829 mark_regno_death (regno);
1830 else
1832 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1834 while (regno < last)
1836 mark_regno_death (regno);
1837 regno++;
1842 /* Mark occurrence of registers in X for the current loop. */
1843 static void
1844 mark_ref_regs (rtx x)
1846 RTX_CODE code;
1847 int i;
1848 const char *fmt;
1850 if (!x)
1851 return;
1853 code = GET_CODE (x);
1854 if (code == REG)
1856 struct loop *loop;
1858 for (loop = curr_loop;
1859 loop != current_loops->tree_root;
1860 loop = loop_outer (loop))
1861 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
1862 return;
1865 fmt = GET_RTX_FORMAT (code);
1866 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1867 if (fmt[i] == 'e')
1868 mark_ref_regs (XEXP (x, i));
1869 else if (fmt[i] == 'E')
1871 int j;
1873 for (j = 0; j < XVECLEN (x, i); j++)
1874 mark_ref_regs (XVECEXP (x, i, j));
1878 /* Calculate register pressure in the loops. */
1879 static void
1880 calculate_loop_reg_pressure (void)
1882 int i;
1883 unsigned int j;
1884 bitmap_iterator bi;
1885 basic_block bb;
1886 rtx_insn *insn;
1887 rtx link;
1888 struct loop *loop, *parent;
1890 FOR_EACH_LOOP (loop, 0)
1891 if (loop->aux == NULL)
1893 loop->aux = xcalloc (1, sizeof (struct loop_data));
1894 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1895 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1897 ira_setup_eliminable_regset ();
1898 bitmap_initialize (&curr_regs_live, &reg_obstack);
1899 FOR_EACH_BB_FN (bb, cfun)
1901 curr_loop = bb->loop_father;
1902 if (curr_loop == current_loops->tree_root)
1903 continue;
1905 for (loop = curr_loop;
1906 loop != current_loops->tree_root;
1907 loop = loop_outer (loop))
1908 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1910 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1911 for (i = 0; i < ira_pressure_classes_num; i++)
1912 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1913 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1914 change_pressure (j, true);
1916 FOR_BB_INSNS (bb, insn)
1918 if (! NONDEBUG_INSN_P (insn))
1919 continue;
1921 mark_ref_regs (PATTERN (insn));
1922 n_regs_set = 0;
1923 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
1925 /* Mark any registers dead after INSN as dead now. */
1927 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1928 if (REG_NOTE_KIND (link) == REG_DEAD)
1929 mark_reg_death (XEXP (link, 0));
1931 /* Mark any registers set in INSN as live,
1932 and mark them as conflicting with all other live regs.
1933 Clobbers are processed again, so they conflict with
1934 the registers that are set. */
1936 note_stores (PATTERN (insn), mark_reg_store, NULL);
1938 #ifdef AUTO_INC_DEC
1939 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1940 if (REG_NOTE_KIND (link) == REG_INC)
1941 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1942 #endif
1943 while (n_regs_set-- > 0)
1945 rtx note = find_regno_note (insn, REG_UNUSED,
1946 REGNO (regs_set[n_regs_set]));
1947 if (! note)
1948 continue;
1950 mark_reg_death (XEXP (note, 0));
1954 bitmap_clear (&curr_regs_live);
1955 if (flag_ira_region == IRA_REGION_MIXED
1956 || flag_ira_region == IRA_REGION_ALL)
1957 FOR_EACH_LOOP (loop, 0)
1959 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1960 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1962 enum reg_class pressure_class;
1963 int nregs;
1965 pressure_class = get_regno_pressure_class (j, &nregs);
1966 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
1969 if (dump_file == NULL)
1970 return;
1971 FOR_EACH_LOOP (loop, 0)
1973 parent = loop_outer (loop);
1974 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1975 loop->num, (parent == NULL ? -1 : parent->num),
1976 loop->header->index, loop_depth (loop));
1977 fprintf (dump_file, "\n ref. regnos:");
1978 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
1979 fprintf (dump_file, " %d", j);
1980 fprintf (dump_file, "\n live regnos:");
1981 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1982 fprintf (dump_file, " %d", j);
1983 fprintf (dump_file, "\n Pressure:");
1984 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1986 enum reg_class pressure_class;
1988 pressure_class = ira_pressure_classes[i];
1989 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
1990 continue;
1991 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
1992 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
1994 fprintf (dump_file, "\n");
2000 /* Move the invariants out of the loops. */
2002 void
2003 move_loop_invariants (void)
2005 struct loop *loop;
2007 if (flag_ira_loop_pressure)
2009 df_analyze ();
2010 regstat_init_n_sets_and_refs ();
2011 ira_set_pseudo_classes (true, dump_file);
2012 calculate_loop_reg_pressure ();
2013 regstat_free_n_sets_and_refs ();
2015 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2016 /* Process the loops, innermost first. */
2017 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2019 curr_loop = loop;
2020 /* move_single_loop_invariants for very large loops
2021 is time consuming and might need a lot of memory. */
2022 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2023 move_single_loop_invariants (loop);
2026 FOR_EACH_LOOP (loop, 0)
2028 free_loop_data (loop);
2031 if (flag_ira_loop_pressure)
2032 /* There is no sense to keep this info because it was most
2033 probably outdated by subsequent passes. */
2034 free_reg_info ();
2035 free (invariant_table);
2036 invariant_table = NULL;
2037 invariant_table_size = 0;
2039 #ifdef ENABLE_CHECKING
2040 verify_flow_info ();
2041 #endif