PR c++/64359
[official-gcc.git] / gcc / loop-invariant.c
blob19e536f5a426761f68e7fe51d76d22814f6dcc25
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 "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 "expr.h"
58 #include "recog.h"
59 #include "target.h"
60 #include "flags.h"
61 #include "df.h"
62 #include "hash-table.h"
63 #include "except.h"
64 #include "params.h"
65 #include "regs.h"
66 #include "ira.h"
67 #include "dumpfile.h"
69 /* The data stored for the loop. */
71 struct loop_data
73 struct loop *outermost_exit; /* The outermost exit of the loop. */
74 bool has_call; /* True if the loop contains a call. */
75 /* Maximal register pressure inside loop for given register class
76 (defined only for the pressure classes). */
77 int max_reg_pressure[N_REG_CLASSES];
78 /* Loop regs referenced and live pseudo-registers. */
79 bitmap_head regs_ref;
80 bitmap_head regs_live;
83 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
85 /* The description of an use. */
87 struct use
89 rtx *pos; /* Position of the use. */
90 rtx_insn *insn; /* The insn in that the use occurs. */
91 unsigned addr_use_p; /* Whether the use occurs in an address. */
92 struct use *next; /* Next use in the list. */
95 /* The description of a def. */
97 struct def
99 struct use *uses; /* The list of uses that are uniquely reached
100 by it. */
101 unsigned n_uses; /* Number of such uses. */
102 unsigned n_addr_uses; /* Number of uses in addresses. */
103 unsigned invno; /* The corresponding invariant. */
106 /* The data stored for each invariant. */
108 struct invariant
110 /* The number of the invariant. */
111 unsigned invno;
113 /* The number of the invariant with the same value. */
114 unsigned eqto;
116 /* The number of invariants which eqto this. */
117 unsigned eqno;
119 /* If we moved the invariant out of the loop, the register that contains its
120 value. */
121 rtx reg;
123 /* If we moved the invariant out of the loop, the original regno
124 that contained its value. */
125 int orig_regno;
127 /* The definition of the invariant. */
128 struct def *def;
130 /* The insn in that it is defined. */
131 rtx_insn *insn;
133 /* Whether it is always executed. */
134 bool always_executed;
136 /* Whether to move the invariant. */
137 bool move;
139 /* Whether the invariant is cheap when used as an address. */
140 bool cheap_address;
142 /* Cost of the invariant. */
143 unsigned cost;
145 /* The invariants it depends on. */
146 bitmap depends_on;
148 /* Used for detecting already visited invariants during determining
149 costs of movements. */
150 unsigned stamp;
153 /* Currently processed loop. */
154 static struct loop *curr_loop;
156 /* Table of invariants indexed by the df_ref uid field. */
158 static unsigned int invariant_table_size = 0;
159 static struct invariant ** invariant_table;
161 /* Entry for hash table of invariant expressions. */
163 struct invariant_expr_entry
165 /* The invariant. */
166 struct invariant *inv;
168 /* Its value. */
169 rtx expr;
171 /* Its mode. */
172 machine_mode mode;
174 /* Its hash. */
175 hashval_t hash;
178 /* The actual stamp for marking already visited invariants during determining
179 costs of movements. */
181 static unsigned actual_stamp;
183 typedef struct invariant *invariant_p;
186 /* The invariants. */
188 static vec<invariant_p> invariants;
190 /* Check the size of the invariant table and realloc if necessary. */
192 static void
193 check_invariant_table_size (void)
195 if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
197 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
198 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
199 memset (&invariant_table[invariant_table_size], 0,
200 (new_size - invariant_table_size) * sizeof (struct invariant *));
201 invariant_table_size = new_size;
205 /* Test for possibility of invariantness of X. */
207 static bool
208 check_maybe_invariant (rtx x)
210 enum rtx_code code = GET_CODE (x);
211 int i, j;
212 const char *fmt;
214 switch (code)
216 CASE_CONST_ANY:
217 case SYMBOL_REF:
218 case CONST:
219 case LABEL_REF:
220 return true;
222 case PC:
223 case CC0:
224 case UNSPEC_VOLATILE:
225 case CALL:
226 return false;
228 case REG:
229 return true;
231 case MEM:
232 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
233 It should not be hard, and might be faster than "elsewhere". */
235 /* Just handle the most trivial case where we load from an unchanging
236 location (most importantly, pic tables). */
237 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
238 break;
240 return false;
242 case ASM_OPERANDS:
243 /* Don't mess with insns declared volatile. */
244 if (MEM_VOLATILE_P (x))
245 return false;
246 break;
248 default:
249 break;
252 fmt = GET_RTX_FORMAT (code);
253 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
255 if (fmt[i] == 'e')
257 if (!check_maybe_invariant (XEXP (x, i)))
258 return false;
260 else if (fmt[i] == 'E')
262 for (j = 0; j < XVECLEN (x, i); j++)
263 if (!check_maybe_invariant (XVECEXP (x, i, j)))
264 return false;
268 return true;
271 /* Returns the invariant definition for USE, or NULL if USE is not
272 invariant. */
274 static struct invariant *
275 invariant_for_use (df_ref use)
277 struct df_link *defs;
278 df_ref def;
279 basic_block bb = DF_REF_BB (use), def_bb;
281 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
282 return NULL;
284 defs = DF_REF_CHAIN (use);
285 if (!defs || defs->next)
286 return NULL;
287 def = defs->ref;
288 check_invariant_table_size ();
289 if (!invariant_table[DF_REF_ID (def)])
290 return NULL;
292 def_bb = DF_REF_BB (def);
293 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
294 return NULL;
295 return invariant_table[DF_REF_ID (def)];
298 /* Computes hash value for invariant expression X in INSN. */
300 static hashval_t
301 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
303 enum rtx_code code = GET_CODE (x);
304 int i, j;
305 const char *fmt;
306 hashval_t val = code;
307 int do_not_record_p;
308 df_ref use;
309 struct invariant *inv;
311 switch (code)
313 CASE_CONST_ANY:
314 case SYMBOL_REF:
315 case CONST:
316 case LABEL_REF:
317 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
319 case REG:
320 use = df_find_use (insn, x);
321 if (!use)
322 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
323 inv = invariant_for_use (use);
324 if (!inv)
325 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
327 gcc_assert (inv->eqto != ~0u);
328 return inv->eqto;
330 default:
331 break;
334 fmt = GET_RTX_FORMAT (code);
335 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
337 if (fmt[i] == 'e')
338 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
339 else if (fmt[i] == 'E')
341 for (j = 0; j < XVECLEN (x, i); j++)
342 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
344 else if (fmt[i] == 'i' || fmt[i] == 'n')
345 val ^= XINT (x, i);
348 return val;
351 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
352 and INSN2 have always the same value. */
354 static bool
355 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
357 enum rtx_code code = GET_CODE (e1);
358 int i, j;
359 const char *fmt;
360 df_ref use1, use2;
361 struct invariant *inv1 = NULL, *inv2 = NULL;
362 rtx sub1, sub2;
364 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
365 the other one. If both are VOIDmode, we rely on the caller of this
366 function to verify that their modes are the same. */
367 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
368 return false;
370 switch (code)
372 CASE_CONST_ANY:
373 case SYMBOL_REF:
374 case CONST:
375 case LABEL_REF:
376 return rtx_equal_p (e1, e2);
378 case REG:
379 use1 = df_find_use (insn1, e1);
380 use2 = df_find_use (insn2, e2);
381 if (use1)
382 inv1 = invariant_for_use (use1);
383 if (use2)
384 inv2 = invariant_for_use (use2);
386 if (!inv1 && !inv2)
387 return rtx_equal_p (e1, e2);
389 if (!inv1 || !inv2)
390 return false;
392 gcc_assert (inv1->eqto != ~0u);
393 gcc_assert (inv2->eqto != ~0u);
394 return inv1->eqto == inv2->eqto;
396 default:
397 break;
400 fmt = GET_RTX_FORMAT (code);
401 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
403 if (fmt[i] == 'e')
405 sub1 = XEXP (e1, i);
406 sub2 = XEXP (e2, i);
408 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
409 return false;
412 else if (fmt[i] == 'E')
414 if (XVECLEN (e1, i) != XVECLEN (e2, i))
415 return false;
417 for (j = 0; j < XVECLEN (e1, i); j++)
419 sub1 = XVECEXP (e1, i, j);
420 sub2 = XVECEXP (e2, i, j);
422 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
423 return false;
426 else if (fmt[i] == 'i' || fmt[i] == 'n')
428 if (XINT (e1, i) != XINT (e2, i))
429 return false;
431 /* Unhandled type of subexpression, we fail conservatively. */
432 else
433 return false;
436 return true;
439 struct invariant_expr_hasher : typed_free_remove <invariant_expr_entry>
441 typedef invariant_expr_entry value_type;
442 typedef invariant_expr_entry compare_type;
443 static inline hashval_t hash (const value_type *);
444 static inline bool equal (const value_type *, const compare_type *);
447 /* Returns hash value for invariant expression entry ENTRY. */
449 inline hashval_t
450 invariant_expr_hasher::hash (const value_type *entry)
452 return entry->hash;
455 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
457 inline bool
458 invariant_expr_hasher::equal (const value_type *entry1,
459 const compare_type *entry2)
461 if (entry1->mode != entry2->mode)
462 return 0;
464 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
465 entry2->inv->insn, entry2->expr);
468 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
470 /* Checks whether invariant with value EXPR in machine mode MODE is
471 recorded in EQ. If this is the case, return the invariant. Otherwise
472 insert INV to the table for this expression and return INV. */
474 static struct invariant *
475 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
476 struct invariant *inv)
478 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
479 struct invariant_expr_entry *entry;
480 struct invariant_expr_entry pentry;
481 invariant_expr_entry **slot;
483 pentry.expr = expr;
484 pentry.inv = inv;
485 pentry.mode = mode;
486 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
487 entry = *slot;
489 if (entry)
490 return entry->inv;
492 entry = XNEW (struct invariant_expr_entry);
493 entry->inv = inv;
494 entry->expr = expr;
495 entry->mode = mode;
496 entry->hash = hash;
497 *slot = entry;
499 return inv;
502 /* Finds invariants identical to INV and records the equivalence. EQ is the
503 hash table of the invariants. */
505 static void
506 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
508 unsigned depno;
509 bitmap_iterator bi;
510 struct invariant *dep;
511 rtx expr, set;
512 machine_mode mode;
513 struct invariant *tmp;
515 if (inv->eqto != ~0u)
516 return;
518 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
520 dep = invariants[depno];
521 find_identical_invariants (eq, dep);
524 set = single_set (inv->insn);
525 expr = SET_SRC (set);
526 mode = GET_MODE (expr);
527 if (mode == VOIDmode)
528 mode = GET_MODE (SET_DEST (set));
530 tmp = find_or_insert_inv (eq, expr, mode, inv);
531 inv->eqto = tmp->invno;
533 if (tmp->invno != inv->invno && inv->always_executed)
534 tmp->eqno++;
536 if (dump_file && inv->eqto != inv->invno)
537 fprintf (dump_file,
538 "Invariant %d is equivalent to invariant %d.\n",
539 inv->invno, inv->eqto);
542 /* Find invariants with the same value and record the equivalences. */
544 static void
545 merge_identical_invariants (void)
547 unsigned i;
548 struct invariant *inv;
549 invariant_htab_type eq (invariants.length ());
551 FOR_EACH_VEC_ELT (invariants, i, inv)
552 find_identical_invariants (&eq, inv);
555 /* Determines the basic blocks inside LOOP that are always executed and
556 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
557 basic blocks that may either exit the loop, or contain the call that
558 does not have to return. BODY is body of the loop obtained by
559 get_loop_body_in_dom_order. */
561 static void
562 compute_always_reached (struct loop *loop, basic_block *body,
563 bitmap may_exit, bitmap always_reached)
565 unsigned i;
567 for (i = 0; i < loop->num_nodes; i++)
569 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
570 bitmap_set_bit (always_reached, i);
572 if (bitmap_bit_p (may_exit, i))
573 return;
577 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
578 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
579 additionally mark blocks that may exit due to a call. */
581 static void
582 find_exits (struct loop *loop, basic_block *body,
583 bitmap may_exit, bitmap has_exit)
585 unsigned i;
586 edge_iterator ei;
587 edge e;
588 struct loop *outermost_exit = loop, *aexit;
589 bool has_call = false;
590 rtx_insn *insn;
592 for (i = 0; i < loop->num_nodes; i++)
594 if (body[i]->loop_father == loop)
596 FOR_BB_INSNS (body[i], insn)
598 if (CALL_P (insn)
599 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
600 || !RTL_CONST_OR_PURE_CALL_P (insn)))
602 has_call = true;
603 bitmap_set_bit (may_exit, i);
604 break;
608 FOR_EACH_EDGE (e, ei, body[i]->succs)
610 if (flow_bb_inside_loop_p (loop, e->dest))
611 continue;
613 bitmap_set_bit (may_exit, i);
614 bitmap_set_bit (has_exit, i);
615 outermost_exit = find_common_loop (outermost_exit,
616 e->dest->loop_father);
618 continue;
621 /* Use the data stored for the subloop to decide whether we may exit
622 through it. It is sufficient to do this for header of the loop,
623 as other basic blocks inside it must be dominated by it. */
624 if (body[i]->loop_father->header != body[i])
625 continue;
627 if (LOOP_DATA (body[i]->loop_father)->has_call)
629 has_call = true;
630 bitmap_set_bit (may_exit, i);
632 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
633 if (aexit != loop)
635 bitmap_set_bit (may_exit, i);
636 bitmap_set_bit (has_exit, i);
638 if (flow_loop_nested_p (aexit, outermost_exit))
639 outermost_exit = aexit;
643 if (loop->aux == NULL)
645 loop->aux = xcalloc (1, sizeof (struct loop_data));
646 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
647 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
649 LOOP_DATA (loop)->outermost_exit = outermost_exit;
650 LOOP_DATA (loop)->has_call = has_call;
653 /* Check whether we may assign a value to X from a register. */
655 static bool
656 may_assign_reg_p (rtx x)
658 return (GET_MODE (x) != VOIDmode
659 && GET_MODE (x) != BLKmode
660 && can_copy_p (GET_MODE (x))
661 && (!REG_P (x)
662 || !HARD_REGISTER_P (x)
663 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
666 /* Finds definitions that may correspond to invariants in LOOP with body
667 BODY. */
669 static void
670 find_defs (struct loop *loop)
672 if (dump_file)
674 fprintf (dump_file,
675 "*****starting processing of loop %d ******\n",
676 loop->num);
679 df_remove_problem (df_chain);
680 df_process_deferred_rescans ();
681 df_chain_add_problem (DF_UD_CHAIN);
682 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
683 df_analyze_loop (loop);
684 check_invariant_table_size ();
686 if (dump_file)
688 df_dump_region (dump_file);
689 fprintf (dump_file,
690 "*****ending processing of loop %d ******\n",
691 loop->num);
695 /* Creates a new invariant for definition DEF in INSN, depending on invariants
696 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
697 unless the program ends due to a function call. The newly created invariant
698 is returned. */
700 static struct invariant *
701 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
702 bool always_executed)
704 struct invariant *inv = XNEW (struct invariant);
705 rtx set = single_set (insn);
706 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
708 inv->def = def;
709 inv->always_executed = always_executed;
710 inv->depends_on = depends_on;
712 /* If the set is simple, usually by moving it we move the whole store out of
713 the loop. Otherwise we save only cost of the computation. */
714 if (def)
716 inv->cost = set_rtx_cost (set, speed);
717 /* ??? Try to determine cheapness of address computation. Unfortunately
718 the address cost is only a relative measure, we can't really compare
719 it with any absolute number, but only with other address costs.
720 But here we don't have any other addresses, so compare with a magic
721 number anyway. It has to be large enough to not regress PR33928
722 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
723 enough to not regress 410.bwaves either (by still moving reg+reg
724 invariants).
725 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
726 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
727 ADDR_SPACE_GENERIC, speed) < 3;
729 else
731 inv->cost = set_src_cost (SET_SRC (set), speed);
732 inv->cheap_address = false;
735 inv->move = false;
736 inv->reg = NULL_RTX;
737 inv->orig_regno = -1;
738 inv->stamp = 0;
739 inv->insn = insn;
741 inv->invno = invariants.length ();
742 inv->eqto = ~0u;
744 /* Itself. */
745 inv->eqno = 1;
747 if (def)
748 def->invno = inv->invno;
749 invariants.safe_push (inv);
751 if (dump_file)
753 fprintf (dump_file,
754 "Set in insn %d is invariant (%d), cost %d, depends on ",
755 INSN_UID (insn), inv->invno, inv->cost);
756 dump_bitmap (dump_file, inv->depends_on);
759 return inv;
762 /* Record USE at DEF. */
764 static void
765 record_use (struct def *def, df_ref use)
767 struct use *u = XNEW (struct use);
769 u->pos = DF_REF_REAL_LOC (use);
770 u->insn = DF_REF_INSN (use);
771 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
772 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
773 u->next = def->uses;
774 def->uses = u;
775 def->n_uses++;
776 if (u->addr_use_p)
777 def->n_addr_uses++;
780 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
781 bitmap. Returns true if all dependencies of USE are known to be
782 loop invariants, false otherwise. */
784 static bool
785 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
787 df_ref def;
788 basic_block def_bb;
789 struct df_link *defs;
790 struct def *def_data;
791 struct invariant *inv;
793 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
794 return false;
796 defs = DF_REF_CHAIN (use);
797 if (!defs)
799 unsigned int regno = DF_REF_REGNO (use);
801 /* If this is the use of an uninitialized argument register that is
802 likely to be spilled, do not move it lest this might extend its
803 lifetime and cause reload to die. This can occur for a call to
804 a function taking complex number arguments and moving the insns
805 preparing the arguments without moving the call itself wouldn't
806 gain much in practice. */
807 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
808 && FUNCTION_ARG_REGNO_P (regno)
809 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
810 return false;
812 return true;
815 if (defs->next)
816 return false;
818 def = defs->ref;
819 check_invariant_table_size ();
820 inv = invariant_table[DF_REF_ID (def)];
821 if (!inv)
822 return false;
824 def_data = inv->def;
825 gcc_assert (def_data != NULL);
827 def_bb = DF_REF_BB (def);
828 /* Note that in case bb == def_bb, we know that the definition
829 dominates insn, because def has invariant_table[DF_REF_ID(def)]
830 defined and we process the insns in the basic block bb
831 sequentially. */
832 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
833 return false;
835 bitmap_set_bit (depends_on, def_data->invno);
836 return true;
840 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
841 bitmap. Returns true if all dependencies of INSN are known to be
842 loop invariants, false otherwise. */
844 static bool
845 check_dependencies (rtx_insn *insn, bitmap depends_on)
847 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
848 df_ref use;
849 basic_block bb = BLOCK_FOR_INSN (insn);
851 FOR_EACH_INSN_INFO_USE (use, insn_info)
852 if (!check_dependency (bb, use, depends_on))
853 return false;
854 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
855 if (!check_dependency (bb, use, depends_on))
856 return false;
858 return true;
861 /* Pre-check candidate DEST to skip the one which can not make a valid insn
862 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
863 static bool
864 pre_check_invariant_p (bool simple, rtx dest)
866 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
868 df_ref use;
869 rtx ref;
870 unsigned int i = REGNO (dest);
871 struct df_insn_info *insn_info;
872 df_ref def_rec;
874 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
876 ref = DF_REF_INSN (use);
877 insn_info = DF_INSN_INFO_GET (ref);
879 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
880 if (DF_REF_REGNO (def_rec) == i)
882 /* Multi definitions at this stage, most likely are due to
883 instruction constraints, which requires both read and write
884 on the same register. Since move_invariant_reg is not
885 powerful enough to handle such cases, just ignore the INV
886 and leave the chance to others. */
887 return false;
891 return true;
894 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
895 executed. ALWAYS_EXECUTED is true if the insn is always executed,
896 unless the program ends due to a function call. */
898 static void
899 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
901 df_ref ref;
902 struct def *def;
903 bitmap depends_on;
904 rtx set, dest;
905 bool simple = true;
906 struct invariant *inv;
908 #ifdef HAVE_cc0
909 /* We can't move a CC0 setter without the user. */
910 if (sets_cc0_p (insn))
911 return;
912 #endif
914 set = single_set (insn);
915 if (!set)
916 return;
917 dest = SET_DEST (set);
919 if (!REG_P (dest)
920 || HARD_REGISTER_P (dest))
921 simple = false;
923 if (!may_assign_reg_p (dest)
924 || !pre_check_invariant_p (simple, dest)
925 || !check_maybe_invariant (SET_SRC (set)))
926 return;
928 /* If the insn can throw exception, we cannot move it at all without changing
929 cfg. */
930 if (can_throw_internal (insn))
931 return;
933 /* We cannot make trapping insn executed, unless it was executed before. */
934 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
935 return;
937 depends_on = BITMAP_ALLOC (NULL);
938 if (!check_dependencies (insn, depends_on))
940 BITMAP_FREE (depends_on);
941 return;
944 if (simple)
945 def = XCNEW (struct def);
946 else
947 def = NULL;
949 inv = create_new_invariant (def, insn, depends_on, always_executed);
951 if (simple)
953 ref = df_find_def (insn, dest);
954 check_invariant_table_size ();
955 invariant_table[DF_REF_ID (ref)] = inv;
959 /* Record registers used in INSN that have a unique invariant definition. */
961 static void
962 record_uses (rtx_insn *insn)
964 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
965 df_ref use;
966 struct invariant *inv;
968 FOR_EACH_INSN_INFO_USE (use, insn_info)
970 inv = invariant_for_use (use);
971 if (inv)
972 record_use (inv->def, use);
974 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
976 inv = invariant_for_use (use);
977 if (inv)
978 record_use (inv->def, use);
982 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
983 executed. ALWAYS_EXECUTED is true if the insn is always executed,
984 unless the program ends due to a function call. */
986 static void
987 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
989 find_invariant_insn (insn, always_reached, always_executed);
990 record_uses (insn);
993 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
994 basic block is always executed. ALWAYS_EXECUTED is true if the basic
995 block is always executed, unless the program ends due to a function
996 call. */
998 static void
999 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1001 rtx_insn *insn;
1003 FOR_BB_INSNS (bb, insn)
1005 if (!NONDEBUG_INSN_P (insn))
1006 continue;
1008 find_invariants_insn (insn, always_reached, always_executed);
1010 if (always_reached
1011 && CALL_P (insn)
1012 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1013 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1014 always_reached = false;
1018 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1019 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1020 bitmap of basic blocks in BODY that are always executed unless the program
1021 ends due to a function call. */
1023 static void
1024 find_invariants_body (struct loop *loop, basic_block *body,
1025 bitmap always_reached, bitmap always_executed)
1027 unsigned i;
1029 for (i = 0; i < loop->num_nodes; i++)
1030 find_invariants_bb (body[i],
1031 bitmap_bit_p (always_reached, i),
1032 bitmap_bit_p (always_executed, i));
1035 /* Finds invariants in LOOP. */
1037 static void
1038 find_invariants (struct loop *loop)
1040 bitmap may_exit = BITMAP_ALLOC (NULL);
1041 bitmap always_reached = BITMAP_ALLOC (NULL);
1042 bitmap has_exit = BITMAP_ALLOC (NULL);
1043 bitmap always_executed = BITMAP_ALLOC (NULL);
1044 basic_block *body = get_loop_body_in_dom_order (loop);
1046 find_exits (loop, body, may_exit, has_exit);
1047 compute_always_reached (loop, body, may_exit, always_reached);
1048 compute_always_reached (loop, body, has_exit, always_executed);
1050 find_defs (loop);
1051 find_invariants_body (loop, body, always_reached, always_executed);
1052 merge_identical_invariants ();
1054 BITMAP_FREE (always_reached);
1055 BITMAP_FREE (always_executed);
1056 BITMAP_FREE (may_exit);
1057 BITMAP_FREE (has_exit);
1058 free (body);
1061 /* Frees a list of uses USE. */
1063 static void
1064 free_use_list (struct use *use)
1066 struct use *next;
1068 for (; use; use = next)
1070 next = use->next;
1071 free (use);
1075 /* Return pressure class and number of hard registers (through *NREGS)
1076 for destination of INSN. */
1077 static enum reg_class
1078 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1080 rtx reg;
1081 enum reg_class pressure_class;
1082 rtx set = single_set (insn);
1084 /* Considered invariant insns have only one set. */
1085 gcc_assert (set != NULL_RTX);
1086 reg = SET_DEST (set);
1087 if (GET_CODE (reg) == SUBREG)
1088 reg = SUBREG_REG (reg);
1089 if (MEM_P (reg))
1091 *nregs = 0;
1092 pressure_class = NO_REGS;
1094 else
1096 if (! REG_P (reg))
1097 reg = NULL_RTX;
1098 if (reg == NULL_RTX)
1099 pressure_class = GENERAL_REGS;
1100 else
1102 pressure_class = reg_allocno_class (REGNO (reg));
1103 pressure_class = ira_pressure_class_translate[pressure_class];
1105 *nregs
1106 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1108 return pressure_class;
1111 /* Calculates cost and number of registers needed for moving invariant INV
1112 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1113 the REG_CLASS of INV. Return
1114 -1: if INV is invalid.
1115 0: if INV and its depends_on have same reg_class
1116 1: if INV and its depends_on have different reg_classes. */
1118 static int
1119 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1120 enum reg_class *cl)
1122 int i, acomp_cost;
1123 unsigned aregs_needed[N_REG_CLASSES];
1124 unsigned depno;
1125 struct invariant *dep;
1126 bitmap_iterator bi;
1127 int ret = 1;
1129 /* Find the representative of the class of the equivalent invariants. */
1130 inv = invariants[inv->eqto];
1132 *comp_cost = 0;
1133 if (! flag_ira_loop_pressure)
1134 regs_needed[0] = 0;
1135 else
1137 for (i = 0; i < ira_pressure_classes_num; i++)
1138 regs_needed[ira_pressure_classes[i]] = 0;
1141 if (inv->move
1142 || inv->stamp == actual_stamp)
1143 return -1;
1144 inv->stamp = actual_stamp;
1146 if (! flag_ira_loop_pressure)
1147 regs_needed[0]++;
1148 else
1150 int nregs;
1151 enum reg_class pressure_class;
1153 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1154 regs_needed[pressure_class] += nregs;
1155 *cl = pressure_class;
1156 ret = 0;
1159 if (!inv->cheap_address
1160 || inv->def->n_addr_uses < inv->def->n_uses)
1161 (*comp_cost) += inv->cost * inv->eqno;
1163 #ifdef STACK_REGS
1165 /* Hoisting constant pool constants into stack regs may cost more than
1166 just single register. On x87, the balance is affected both by the
1167 small number of FP registers, and by its register stack organization,
1168 that forces us to add compensation code in and around the loop to
1169 shuffle the operands to the top of stack before use, and pop them
1170 from the stack after the loop finishes.
1172 To model this effect, we increase the number of registers needed for
1173 stack registers by two: one register push, and one register pop.
1174 This usually has the effect that FP constant loads from the constant
1175 pool are not moved out of the loop.
1177 Note that this also means that dependent invariants can not be moved.
1178 However, the primary purpose of this pass is to move loop invariant
1179 address arithmetic out of loops, and address arithmetic that depends
1180 on floating point constants is unlikely to ever occur. */
1181 rtx set = single_set (inv->insn);
1182 if (set
1183 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1184 && constant_pool_constant_p (SET_SRC (set)))
1186 if (flag_ira_loop_pressure)
1187 regs_needed[ira_stack_reg_pressure_class] += 2;
1188 else
1189 regs_needed[0] += 2;
1192 #endif
1194 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1196 bool check_p;
1197 enum reg_class dep_cl = ALL_REGS;
1198 int dep_ret;
1200 dep = invariants[depno];
1202 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1203 if (dep->move)
1204 continue;
1206 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1208 if (! flag_ira_loop_pressure)
1209 check_p = aregs_needed[0] != 0;
1210 else
1212 for (i = 0; i < ira_pressure_classes_num; i++)
1213 if (aregs_needed[ira_pressure_classes[i]] != 0)
1214 break;
1215 check_p = i < ira_pressure_classes_num;
1217 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1219 *cl = ALL_REGS;
1220 ret = 1;
1223 if (check_p
1224 /* We need to check always_executed, since if the original value of
1225 the invariant may be preserved, we may need to keep it in a
1226 separate register. TODO check whether the register has an
1227 use outside of the loop. */
1228 && dep->always_executed
1229 && !dep->def->uses->next)
1231 /* If this is a single use, after moving the dependency we will not
1232 need a new register. */
1233 if (! flag_ira_loop_pressure)
1234 aregs_needed[0]--;
1235 else
1237 int nregs;
1238 enum reg_class pressure_class;
1240 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1241 aregs_needed[pressure_class] -= nregs;
1245 if (! flag_ira_loop_pressure)
1246 regs_needed[0] += aregs_needed[0];
1247 else
1249 for (i = 0; i < ira_pressure_classes_num; i++)
1250 regs_needed[ira_pressure_classes[i]]
1251 += aregs_needed[ira_pressure_classes[i]];
1253 (*comp_cost) += acomp_cost;
1255 return ret;
1258 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1259 of registers used in the loop, NEW_REGS is the number of new variables
1260 already added due to the invariant motion. The number of registers needed
1261 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1262 through to estimate_reg_pressure_cost. */
1264 static int
1265 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1266 unsigned *new_regs, unsigned regs_used,
1267 bool speed, bool call_p)
1269 int comp_cost, size_cost;
1270 enum reg_class cl;
1271 int ret;
1273 actual_stamp++;
1275 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1277 if (! flag_ira_loop_pressure)
1279 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1280 regs_used, speed, call_p)
1281 - estimate_reg_pressure_cost (new_regs[0],
1282 regs_used, speed, call_p));
1284 else if (ret < 0)
1285 return -1;
1286 else if ((ret == 0) && (cl == NO_REGS))
1287 /* Hoist it anyway since it does not impact register pressure. */
1288 return 1;
1289 else
1291 int i;
1292 enum reg_class pressure_class;
1294 for (i = 0; i < ira_pressure_classes_num; i++)
1296 pressure_class = ira_pressure_classes[i];
1298 if (!reg_classes_intersect_p (pressure_class, cl))
1299 continue;
1301 if ((int) new_regs[pressure_class]
1302 + (int) regs_needed[pressure_class]
1303 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1304 + IRA_LOOP_RESERVED_REGS
1305 > ira_class_hard_regs_num[pressure_class])
1306 break;
1308 if (i < ira_pressure_classes_num)
1309 /* There will be register pressure excess and we want not to
1310 make this loop invariant motion. All loop invariants with
1311 non-positive gains will be rejected in function
1312 find_invariants_to_move. Therefore we return the negative
1313 number here.
1315 One could think that this rejects also expensive loop
1316 invariant motions and this will hurt code performance.
1317 However numerous experiments with different heuristics
1318 taking invariant cost into account did not confirm this
1319 assumption. There are possible explanations for this
1320 result:
1321 o probably all expensive invariants were already moved out
1322 of the loop by PRE and gimple invariant motion pass.
1323 o expensive invariant execution will be hidden by insn
1324 scheduling or OOO processor hardware because usually such
1325 invariants have a lot of freedom to be executed
1326 out-of-order.
1327 Another reason for ignoring invariant cost vs spilling cost
1328 heuristics is also in difficulties to evaluate accurately
1329 spill cost at this stage. */
1330 return -1;
1331 else
1332 size_cost = 0;
1335 return comp_cost - size_cost;
1338 /* Finds invariant with best gain for moving. Returns the gain, stores
1339 the invariant in *BEST and number of registers needed for it to
1340 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1341 NEW_REGS is the number of new variables already added due to invariant
1342 motion. */
1344 static int
1345 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1346 unsigned *new_regs, unsigned regs_used,
1347 bool speed, bool call_p)
1349 struct invariant *inv;
1350 int i, gain = 0, again;
1351 unsigned aregs_needed[N_REG_CLASSES], invno;
1353 FOR_EACH_VEC_ELT (invariants, invno, inv)
1355 if (inv->move)
1356 continue;
1358 /* Only consider the "representatives" of equivalent invariants. */
1359 if (inv->eqto != inv->invno)
1360 continue;
1362 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1363 speed, call_p);
1364 if (again > gain)
1366 gain = again;
1367 *best = inv;
1368 if (! flag_ira_loop_pressure)
1369 regs_needed[0] = aregs_needed[0];
1370 else
1372 for (i = 0; i < ira_pressure_classes_num; i++)
1373 regs_needed[ira_pressure_classes[i]]
1374 = aregs_needed[ira_pressure_classes[i]];
1379 return gain;
1382 /* Marks invariant INVNO and all its dependencies for moving. */
1384 static void
1385 set_move_mark (unsigned invno, int gain)
1387 struct invariant *inv = invariants[invno];
1388 bitmap_iterator bi;
1390 /* Find the representative of the class of the equivalent invariants. */
1391 inv = invariants[inv->eqto];
1393 if (inv->move)
1394 return;
1395 inv->move = true;
1397 if (dump_file)
1399 if (gain >= 0)
1400 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1401 invno, gain);
1402 else
1403 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1404 invno);
1407 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1409 set_move_mark (invno, -1);
1413 /* Determines which invariants to move. */
1415 static void
1416 find_invariants_to_move (bool speed, bool call_p)
1418 int gain;
1419 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1420 struct invariant *inv = NULL;
1422 if (!invariants.length ())
1423 return;
1425 if (flag_ira_loop_pressure)
1426 /* REGS_USED is actually never used when the flag is on. */
1427 regs_used = 0;
1428 else
1429 /* We do not really do a good job in estimating number of
1430 registers used; we put some initial bound here to stand for
1431 induction variables etc. that we do not detect. */
1433 unsigned int n_regs = DF_REG_SIZE (df);
1435 regs_used = 2;
1437 for (i = 0; i < n_regs; i++)
1439 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1441 /* This is a value that is used but not changed inside loop. */
1442 regs_used++;
1447 if (! flag_ira_loop_pressure)
1448 new_regs[0] = regs_needed[0] = 0;
1449 else
1451 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1452 new_regs[ira_pressure_classes[i]] = 0;
1454 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1455 new_regs, regs_used,
1456 speed, call_p)) > 0)
1458 set_move_mark (inv->invno, gain);
1459 if (! flag_ira_loop_pressure)
1460 new_regs[0] += regs_needed[0];
1461 else
1463 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1464 new_regs[ira_pressure_classes[i]]
1465 += regs_needed[ira_pressure_classes[i]];
1470 /* Replace the uses, reached by the definition of invariant INV, by REG.
1472 IN_GROUP is nonzero if this is part of a group of changes that must be
1473 performed as a group. In that case, the changes will be stored. The
1474 function `apply_change_group' will validate and apply the changes. */
1476 static int
1477 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1479 /* Replace the uses we know to be dominated. It saves work for copy
1480 propagation, and also it is necessary so that dependent invariants
1481 are computed right. */
1482 if (inv->def)
1484 struct use *use;
1485 for (use = inv->def->uses; use; use = use->next)
1486 validate_change (use->insn, use->pos, reg, true);
1488 /* If we aren't part of a larger group, apply the changes now. */
1489 if (!in_group)
1490 return apply_change_group ();
1493 return 1;
1496 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1497 otherwise. */
1499 static bool
1500 move_invariant_reg (struct loop *loop, unsigned invno)
1502 struct invariant *inv = invariants[invno];
1503 struct invariant *repr = invariants[inv->eqto];
1504 unsigned i;
1505 basic_block preheader = loop_preheader_edge (loop)->src;
1506 rtx reg, set, dest, note;
1507 bitmap_iterator bi;
1508 int regno = -1;
1510 if (inv->reg)
1511 return true;
1512 if (!repr->move)
1513 return false;
1515 /* If this is a representative of the class of equivalent invariants,
1516 really move the invariant. Otherwise just replace its use with
1517 the register used for the representative. */
1518 if (inv == repr)
1520 if (inv->depends_on)
1522 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1524 if (!move_invariant_reg (loop, i))
1525 goto fail;
1529 /* Move the set out of the loop. If the set is always executed (we could
1530 omit this condition if we know that the register is unused outside of
1531 the loop, but it does not seem worth finding out) and it has no uses
1532 that would not be dominated by it, we may just move it (TODO).
1533 Otherwise we need to create a temporary register. */
1534 set = single_set (inv->insn);
1535 reg = dest = SET_DEST (set);
1536 if (GET_CODE (reg) == SUBREG)
1537 reg = SUBREG_REG (reg);
1538 if (REG_P (reg))
1539 regno = REGNO (reg);
1541 reg = gen_reg_rtx_and_attrs (dest);
1543 /* Try replacing the destination by a new pseudoregister. */
1544 validate_change (inv->insn, &SET_DEST (set), reg, true);
1546 /* As well as all the dominated uses. */
1547 replace_uses (inv, reg, true);
1549 /* And validate all the changes. */
1550 if (!apply_change_group ())
1551 goto fail;
1553 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1554 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1556 /* If there is a REG_EQUAL note on the insn we just moved, and the
1557 insn is in a basic block that is not always executed or the note
1558 contains something for which we don't know the invariant status,
1559 the note may no longer be valid after we move the insn. Note that
1560 uses in REG_EQUAL notes are taken into account in the computation
1561 of invariants, so it is safe to retain the note even if it contains
1562 register references for which we know the invariant status. */
1563 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1564 && (!inv->always_executed
1565 || !check_maybe_invariant (XEXP (note, 0))))
1566 remove_note (inv->insn, note);
1568 else
1570 if (!move_invariant_reg (loop, repr->invno))
1571 goto fail;
1572 reg = repr->reg;
1573 regno = repr->orig_regno;
1574 if (!replace_uses (inv, reg, false))
1575 goto fail;
1576 set = single_set (inv->insn);
1577 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1578 delete_insn (inv->insn);
1581 inv->reg = reg;
1582 inv->orig_regno = regno;
1584 return true;
1586 fail:
1587 /* If we failed, clear move flag, so that we do not try to move inv
1588 again. */
1589 if (dump_file)
1590 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1591 inv->move = false;
1592 inv->reg = NULL_RTX;
1593 inv->orig_regno = -1;
1595 return false;
1598 /* Move selected invariant out of the LOOP. Newly created regs are marked
1599 in TEMPORARY_REGS. */
1601 static void
1602 move_invariants (struct loop *loop)
1604 struct invariant *inv;
1605 unsigned i;
1607 FOR_EACH_VEC_ELT (invariants, i, inv)
1608 move_invariant_reg (loop, i);
1609 if (flag_ira_loop_pressure && resize_reg_info ())
1611 FOR_EACH_VEC_ELT (invariants, i, inv)
1612 if (inv->reg != NULL_RTX)
1614 if (inv->orig_regno >= 0)
1615 setup_reg_classes (REGNO (inv->reg),
1616 reg_preferred_class (inv->orig_regno),
1617 reg_alternate_class (inv->orig_regno),
1618 reg_allocno_class (inv->orig_regno));
1619 else
1620 setup_reg_classes (REGNO (inv->reg),
1621 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1626 /* Initializes invariant motion data. */
1628 static void
1629 init_inv_motion_data (void)
1631 actual_stamp = 1;
1633 invariants.create (100);
1636 /* Frees the data allocated by invariant motion. */
1638 static void
1639 free_inv_motion_data (void)
1641 unsigned i;
1642 struct def *def;
1643 struct invariant *inv;
1645 check_invariant_table_size ();
1646 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1648 inv = invariant_table[i];
1649 if (inv)
1651 def = inv->def;
1652 gcc_assert (def != NULL);
1654 free_use_list (def->uses);
1655 free (def);
1656 invariant_table[i] = NULL;
1660 FOR_EACH_VEC_ELT (invariants, i, inv)
1662 BITMAP_FREE (inv->depends_on);
1663 free (inv);
1665 invariants.release ();
1668 /* Move the invariants out of the LOOP. */
1670 static void
1671 move_single_loop_invariants (struct loop *loop)
1673 init_inv_motion_data ();
1675 find_invariants (loop);
1676 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1677 LOOP_DATA (loop)->has_call);
1678 move_invariants (loop);
1680 free_inv_motion_data ();
1683 /* Releases the auxiliary data for LOOP. */
1685 static void
1686 free_loop_data (struct loop *loop)
1688 struct loop_data *data = LOOP_DATA (loop);
1689 if (!data)
1690 return;
1692 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1693 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1694 free (data);
1695 loop->aux = NULL;
1700 /* Registers currently living. */
1701 static bitmap_head curr_regs_live;
1703 /* Current reg pressure for each pressure class. */
1704 static int curr_reg_pressure[N_REG_CLASSES];
1706 /* Record all regs that are set in any one insn. Communication from
1707 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1708 all hard-registers. */
1709 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1710 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1711 /* Number of regs stored in the previous array. */
1712 static int n_regs_set;
1714 /* Return pressure class and number of needed hard registers (through
1715 *NREGS) of register REGNO. */
1716 static enum reg_class
1717 get_regno_pressure_class (int regno, int *nregs)
1719 if (regno >= FIRST_PSEUDO_REGISTER)
1721 enum reg_class pressure_class;
1723 pressure_class = reg_allocno_class (regno);
1724 pressure_class = ira_pressure_class_translate[pressure_class];
1725 *nregs
1726 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1727 return pressure_class;
1729 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1730 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1732 *nregs = 1;
1733 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1735 else
1737 *nregs = 0;
1738 return NO_REGS;
1742 /* Increase (if INCR_P) or decrease current register pressure for
1743 register REGNO. */
1744 static void
1745 change_pressure (int regno, bool incr_p)
1747 int nregs;
1748 enum reg_class pressure_class;
1750 pressure_class = get_regno_pressure_class (regno, &nregs);
1751 if (! incr_p)
1752 curr_reg_pressure[pressure_class] -= nregs;
1753 else
1755 curr_reg_pressure[pressure_class] += nregs;
1756 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1757 < curr_reg_pressure[pressure_class])
1758 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1759 = curr_reg_pressure[pressure_class];
1763 /* Mark REGNO birth. */
1764 static void
1765 mark_regno_live (int regno)
1767 struct loop *loop;
1769 for (loop = curr_loop;
1770 loop != current_loops->tree_root;
1771 loop = loop_outer (loop))
1772 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
1773 if (!bitmap_set_bit (&curr_regs_live, regno))
1774 return;
1775 change_pressure (regno, true);
1778 /* Mark REGNO death. */
1779 static void
1780 mark_regno_death (int regno)
1782 if (! bitmap_clear_bit (&curr_regs_live, regno))
1783 return;
1784 change_pressure (regno, false);
1787 /* Mark setting register REG. */
1788 static void
1789 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1790 void *data ATTRIBUTE_UNUSED)
1792 int regno;
1794 if (GET_CODE (reg) == SUBREG)
1795 reg = SUBREG_REG (reg);
1797 if (! REG_P (reg))
1798 return;
1800 regs_set[n_regs_set++] = reg;
1802 regno = REGNO (reg);
1804 if (regno >= FIRST_PSEUDO_REGISTER)
1805 mark_regno_live (regno);
1806 else
1808 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1810 while (regno < last)
1812 mark_regno_live (regno);
1813 regno++;
1818 /* Mark clobbering register REG. */
1819 static void
1820 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1822 if (GET_CODE (setter) == CLOBBER)
1823 mark_reg_store (reg, setter, data);
1826 /* Mark register REG death. */
1827 static void
1828 mark_reg_death (rtx reg)
1830 int regno = REGNO (reg);
1832 if (regno >= FIRST_PSEUDO_REGISTER)
1833 mark_regno_death (regno);
1834 else
1836 int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1838 while (regno < last)
1840 mark_regno_death (regno);
1841 regno++;
1846 /* Mark occurrence of registers in X for the current loop. */
1847 static void
1848 mark_ref_regs (rtx x)
1850 RTX_CODE code;
1851 int i;
1852 const char *fmt;
1854 if (!x)
1855 return;
1857 code = GET_CODE (x);
1858 if (code == REG)
1860 struct loop *loop;
1862 for (loop = curr_loop;
1863 loop != current_loops->tree_root;
1864 loop = loop_outer (loop))
1865 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
1866 return;
1869 fmt = GET_RTX_FORMAT (code);
1870 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1871 if (fmt[i] == 'e')
1872 mark_ref_regs (XEXP (x, i));
1873 else if (fmt[i] == 'E')
1875 int j;
1877 for (j = 0; j < XVECLEN (x, i); j++)
1878 mark_ref_regs (XVECEXP (x, i, j));
1882 /* Calculate register pressure in the loops. */
1883 static void
1884 calculate_loop_reg_pressure (void)
1886 int i;
1887 unsigned int j;
1888 bitmap_iterator bi;
1889 basic_block bb;
1890 rtx_insn *insn;
1891 rtx link;
1892 struct loop *loop, *parent;
1894 FOR_EACH_LOOP (loop, 0)
1895 if (loop->aux == NULL)
1897 loop->aux = xcalloc (1, sizeof (struct loop_data));
1898 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1899 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1901 ira_setup_eliminable_regset ();
1902 bitmap_initialize (&curr_regs_live, &reg_obstack);
1903 FOR_EACH_BB_FN (bb, cfun)
1905 curr_loop = bb->loop_father;
1906 if (curr_loop == current_loops->tree_root)
1907 continue;
1909 for (loop = curr_loop;
1910 loop != current_loops->tree_root;
1911 loop = loop_outer (loop))
1912 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1914 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1915 for (i = 0; i < ira_pressure_classes_num; i++)
1916 curr_reg_pressure[ira_pressure_classes[i]] = 0;
1917 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1918 change_pressure (j, true);
1920 FOR_BB_INSNS (bb, insn)
1922 if (! NONDEBUG_INSN_P (insn))
1923 continue;
1925 mark_ref_regs (PATTERN (insn));
1926 n_regs_set = 0;
1927 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
1929 /* Mark any registers dead after INSN as dead now. */
1931 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1932 if (REG_NOTE_KIND (link) == REG_DEAD)
1933 mark_reg_death (XEXP (link, 0));
1935 /* Mark any registers set in INSN as live,
1936 and mark them as conflicting with all other live regs.
1937 Clobbers are processed again, so they conflict with
1938 the registers that are set. */
1940 note_stores (PATTERN (insn), mark_reg_store, NULL);
1942 #ifdef AUTO_INC_DEC
1943 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1944 if (REG_NOTE_KIND (link) == REG_INC)
1945 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1946 #endif
1947 while (n_regs_set-- > 0)
1949 rtx note = find_regno_note (insn, REG_UNUSED,
1950 REGNO (regs_set[n_regs_set]));
1951 if (! note)
1952 continue;
1954 mark_reg_death (XEXP (note, 0));
1958 bitmap_clear (&curr_regs_live);
1959 if (flag_ira_region == IRA_REGION_MIXED
1960 || flag_ira_region == IRA_REGION_ALL)
1961 FOR_EACH_LOOP (loop, 0)
1963 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1964 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1966 enum reg_class pressure_class;
1967 int nregs;
1969 pressure_class = get_regno_pressure_class (j, &nregs);
1970 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
1973 if (dump_file == NULL)
1974 return;
1975 FOR_EACH_LOOP (loop, 0)
1977 parent = loop_outer (loop);
1978 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1979 loop->num, (parent == NULL ? -1 : parent->num),
1980 loop->header->index, loop_depth (loop));
1981 fprintf (dump_file, "\n ref. regnos:");
1982 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
1983 fprintf (dump_file, " %d", j);
1984 fprintf (dump_file, "\n live regnos:");
1985 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1986 fprintf (dump_file, " %d", j);
1987 fprintf (dump_file, "\n Pressure:");
1988 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1990 enum reg_class pressure_class;
1992 pressure_class = ira_pressure_classes[i];
1993 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
1994 continue;
1995 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
1996 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
1998 fprintf (dump_file, "\n");
2004 /* Move the invariants out of the loops. */
2006 void
2007 move_loop_invariants (void)
2009 struct loop *loop;
2011 if (flag_ira_loop_pressure)
2013 df_analyze ();
2014 regstat_init_n_sets_and_refs ();
2015 ira_set_pseudo_classes (true, dump_file);
2016 calculate_loop_reg_pressure ();
2017 regstat_free_n_sets_and_refs ();
2019 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2020 /* Process the loops, innermost first. */
2021 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2023 curr_loop = loop;
2024 /* move_single_loop_invariants for very large loops
2025 is time consuming and might need a lot of memory. */
2026 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2027 move_single_loop_invariants (loop);
2030 FOR_EACH_LOOP (loop, 0)
2032 free_loop_data (loop);
2035 if (flag_ira_loop_pressure)
2036 /* There is no sense to keep this info because it was most
2037 probably outdated by subsequent passes. */
2038 free_reg_info ();
2039 free (invariant_table);
2040 invariant_table = NULL;
2041 invariant_table_size = 0;
2043 #ifdef ENABLE_CHECKING
2044 verify_flow_info ();
2045 #endif