1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006, 2007 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 2, or (at your option) any
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This implements the loop invariant motion pass. It is very simple
22 (no calls, libcalls, etc.). This should be sufficient to cleanup things
23 like address arithmetics -- other more complicated invariants should be
24 eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
26 We proceed loop by loop -- it is simpler than trying to handle things
27 globally and should not lose much. First we inspect all sets inside loop
28 and create a dependency graph on insns (saying "to move this insn, you must
29 also move the following insns").
31 We then need to determine what to move. We estimate the number of registers
32 used and move as many invariants as possible while we still have enough free
33 registers. We prefer the expensive invariants.
35 Then we move the selected invariants out of the loop, creating a new
36 temporaries for them if necessary. */
40 #include "coretypes.h"
44 #include "hard-reg-set.h"
46 #include "basic-block.h"
57 /* The data stored for the loop. */
61 struct loop *outermost_exit; /* The outermost exit of the loop. */
62 bool has_call; /* True if the loop contains a call. */
65 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
67 /* The description of an use. */
71 rtx *pos; /* Position of the use. */
72 rtx insn; /* The insn in that the use occurs. */
74 struct use *next; /* Next use in the list. */
77 /* The description of a def. */
81 struct use *uses; /* The list of uses that are uniquely reached
83 unsigned n_uses; /* Number of such uses. */
84 unsigned invno; /* The corresponding invariant. */
87 /* The data stored for each invariant. */
91 /* The number of the invariant. */
94 /* The number of the invariant with the same value. */
97 /* If we moved the invariant out of the loop, the register that contains its
101 /* The definition of the invariant. */
104 /* The insn in that it is defined. */
107 /* Whether it is always executed. */
108 bool always_executed;
110 /* Whether to move the invariant. */
113 /* Cost of the invariant. */
116 /* The invariants it depends on. */
119 /* Used for detecting already visited invariants during determining
120 costs of movements. */
124 /* Table of invariants indexed by the df_ref uid field. */
126 static unsigned int invariant_table_size = 0;
127 static struct invariant ** invariant_table;
129 /* Entry for hash table of invariant expressions. */
131 struct invariant_expr_entry
134 struct invariant *inv;
140 enum machine_mode mode;
146 /* The actual stamp for marking already visited invariants during determining
147 costs of movements. */
149 static unsigned actual_stamp;
151 typedef struct invariant *invariant_p;
153 DEF_VEC_P(invariant_p);
154 DEF_VEC_ALLOC_P(invariant_p, heap);
156 /* The invariants. */
158 static VEC(invariant_p,heap) *invariants;
160 /* Check the size of the invariant table and realloc if necessary. */
163 check_invariant_table_size (void)
165 if (invariant_table_size < DF_DEFS_TABLE_SIZE())
167 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
168 invariant_table = xrealloc (invariant_table,
169 sizeof (struct rtx_iv *) * new_size);
170 memset (&invariant_table[invariant_table_size], 0,
171 (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
172 invariant_table_size = new_size;
176 /* Test for possibility of invariantness of X. */
179 check_maybe_invariant (rtx x)
181 enum rtx_code code = GET_CODE (x);
196 case UNSPEC_VOLATILE:
204 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
205 It should not be hard, and might be faster than "elsewhere". */
207 /* Just handle the most trivial case where we load from an unchanging
208 location (most importantly, pic tables). */
209 if (MEM_READONLY_P (x))
215 /* Don't mess with insns declared volatile. */
216 if (MEM_VOLATILE_P (x))
224 fmt = GET_RTX_FORMAT (code);
225 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
229 if (!check_maybe_invariant (XEXP (x, i)))
232 else if (fmt[i] == 'E')
234 for (j = 0; j < XVECLEN (x, i); j++)
235 if (!check_maybe_invariant (XVECEXP (x, i, j)))
243 /* Returns the invariant definition for USE, or NULL if USE is not
246 static struct invariant *
247 invariant_for_use (struct df_ref *use)
249 struct df_link *defs;
251 basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
253 if (use->flags & DF_REF_READ_WRITE)
256 defs = DF_REF_CHAIN (use);
257 if (!defs || defs->next)
260 check_invariant_table_size ();
261 if (!invariant_table[DF_REF_ID(def)])
264 def_bb = DF_REF_BB (def);
265 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
267 return invariant_table[DF_REF_ID(def)];
270 /* Computes hash value for invariant expression X in INSN. */
273 hash_invariant_expr_1 (rtx insn, rtx x)
275 enum rtx_code code = GET_CODE (x);
278 hashval_t val = code;
281 struct invariant *inv;
290 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
293 use = df_find_use (insn, x);
295 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
296 inv = invariant_for_use (use);
298 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
300 gcc_assert (inv->eqto != ~0u);
307 fmt = GET_RTX_FORMAT (code);
308 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
311 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
312 else if (fmt[i] == 'E')
314 for (j = 0; j < XVECLEN (x, i); j++)
315 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
317 else if (fmt[i] == 'i' || fmt[i] == 'n')
324 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
325 and INSN2 have always the same value. */
328 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
330 enum rtx_code code = GET_CODE (e1);
333 struct df_ref *use1, *use2;
334 struct invariant *inv1 = NULL, *inv2 = NULL;
337 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
338 the other one. If both are VOIDmode, we rely on the caller of this
339 function to verify that their modes are the same. */
340 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
350 return rtx_equal_p (e1, e2);
353 use1 = df_find_use (insn1, e1);
354 use2 = df_find_use (insn2, e2);
356 inv1 = invariant_for_use (use1);
358 inv2 = invariant_for_use (use2);
361 return rtx_equal_p (e1, e2);
366 gcc_assert (inv1->eqto != ~0u);
367 gcc_assert (inv2->eqto != ~0u);
368 return inv1->eqto == inv2->eqto;
374 fmt = GET_RTX_FORMAT (code);
375 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
382 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
386 else if (fmt[i] == 'E')
388 if (XVECLEN (e1, i) != XVECLEN (e2, i))
391 for (j = 0; j < XVECLEN (e1, i); j++)
393 sub1 = XVECEXP (e1, i, j);
394 sub2 = XVECEXP (e2, i, j);
396 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
400 else if (fmt[i] == 'i' || fmt[i] == 'n')
402 if (XINT (e1, i) != XINT (e2, i))
405 /* Unhandled type of subexpression, we fail conservatively. */
413 /* Returns hash value for invariant expression entry E. */
416 hash_invariant_expr (const void *e)
418 const struct invariant_expr_entry *entry = e;
423 /* Compares invariant expression entries E1 and E2. */
426 eq_invariant_expr (const void *e1, const void *e2)
428 const struct invariant_expr_entry *entry1 = e1;
429 const struct invariant_expr_entry *entry2 = e2;
431 if (entry1->mode != entry2->mode)
434 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
435 entry2->inv->insn, entry2->expr);
438 /* Checks whether invariant with value EXPR in machine mode MODE is
439 recorded in EQ. If this is the case, return the invariant. Otherwise
440 insert INV to the table for this expression and return INV. */
442 static struct invariant *
443 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
444 struct invariant *inv)
446 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
447 struct invariant_expr_entry *entry;
448 struct invariant_expr_entry pentry;
454 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
460 entry = XNEW (struct invariant_expr_entry);
470 /* Finds invariants identical to INV and records the equivalence. EQ is the
471 hash table of the invariants. */
474 find_identical_invariants (htab_t eq, struct invariant *inv)
478 struct invariant *dep;
480 enum machine_mode mode;
482 if (inv->eqto != ~0u)
485 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
487 dep = VEC_index (invariant_p, invariants, depno);
488 find_identical_invariants (eq, dep);
491 set = single_set (inv->insn);
492 expr = SET_SRC (set);
493 mode = GET_MODE (expr);
494 if (mode == VOIDmode)
495 mode = GET_MODE (SET_DEST (set));
496 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
498 if (dump_file && inv->eqto != inv->invno)
500 "Invariant %d is equivalent to invariant %d.\n",
501 inv->invno, inv->eqto);
504 /* Find invariants with the same value and record the equivalences. */
507 merge_identical_invariants (void)
510 struct invariant *inv;
511 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
512 hash_invariant_expr, eq_invariant_expr, free);
514 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
515 find_identical_invariants (eq, inv);
520 /* Determines the basic blocks inside LOOP that are always executed and
521 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
522 basic blocks that may either exit the loop, or contain the call that
523 does not have to return. BODY is body of the loop obtained by
524 get_loop_body_in_dom_order. */
527 compute_always_reached (struct loop *loop, basic_block *body,
528 bitmap may_exit, bitmap always_reached)
532 for (i = 0; i < loop->num_nodes; i++)
534 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
535 bitmap_set_bit (always_reached, i);
537 if (bitmap_bit_p (may_exit, i))
542 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
543 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
544 additionally mark blocks that may exit due to a call. */
547 find_exits (struct loop *loop, basic_block *body,
548 bitmap may_exit, bitmap has_exit)
553 struct loop *outermost_exit = loop, *aexit;
554 bool has_call = false;
557 for (i = 0; i < loop->num_nodes; i++)
559 if (body[i]->loop_father == loop)
561 FOR_BB_INSNS (body[i], insn)
564 && !CONST_OR_PURE_CALL_P (insn))
567 bitmap_set_bit (may_exit, i);
572 FOR_EACH_EDGE (e, ei, body[i]->succs)
574 if (flow_bb_inside_loop_p (loop, e->dest))
577 bitmap_set_bit (may_exit, i);
578 bitmap_set_bit (has_exit, i);
579 outermost_exit = find_common_loop (outermost_exit,
580 e->dest->loop_father);
585 /* Use the data stored for the subloop to decide whether we may exit
586 through it. It is sufficient to do this for header of the loop,
587 as other basic blocks inside it must be dominated by it. */
588 if (body[i]->loop_father->header != body[i])
591 if (LOOP_DATA (body[i]->loop_father)->has_call)
594 bitmap_set_bit (may_exit, i);
596 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
599 bitmap_set_bit (may_exit, i);
600 bitmap_set_bit (has_exit, i);
602 if (flow_loop_nested_p (aexit, outermost_exit))
603 outermost_exit = aexit;
607 loop->aux = xcalloc (1, sizeof (struct loop_data));
608 LOOP_DATA (loop)->outermost_exit = outermost_exit;
609 LOOP_DATA (loop)->has_call = has_call;
612 /* Check whether we may assign a value to X from a register. */
615 may_assign_reg_p (rtx x)
617 return (GET_MODE (x) != VOIDmode
618 && GET_MODE (x) != BLKmode
619 && can_copy_p (GET_MODE (x))
621 || !HARD_REGISTER_P (x)
622 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
625 /* Finds definitions that may correspond to invariants in LOOP with body
629 find_defs (struct loop *loop, basic_block *body)
632 bitmap blocks = BITMAP_ALLOC (NULL);
634 for (i = 0; i < loop->num_nodes; i++)
635 bitmap_set_bit (blocks, body[i]->index);
637 df_remove_problem (df_chain);
638 df_process_deferred_rescans ();
639 df_chain_add_problem (DF_UD_CHAIN);
640 df_set_blocks (blocks);
645 fprintf (dump_file, "*****starting processing of loop ******\n");
646 print_rtl_with_bb (dump_file, get_insns ());
647 fprintf (dump_file, "*****ending processing of loop ******\n");
649 check_invariant_table_size ();
651 BITMAP_FREE (blocks);
654 /* Creates a new invariant for definition DEF in INSN, depending on invariants
655 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
656 unless the program ends due to a function call. The newly created invariant
659 static struct invariant *
660 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
661 bool always_executed)
663 struct invariant *inv = XNEW (struct invariant);
664 rtx set = single_set (insn);
667 inv->always_executed = always_executed;
668 inv->depends_on = depends_on;
670 /* If the set is simple, usually by moving it we move the whole store out of
671 the loop. Otherwise we save only cost of the computation. */
673 inv->cost = rtx_cost (set, SET);
675 inv->cost = rtx_cost (SET_SRC (set), SET);
682 inv->invno = VEC_length (invariant_p, invariants);
685 def->invno = inv->invno;
686 VEC_safe_push (invariant_p, heap, invariants, inv);
691 "Set in insn %d is invariant (%d), cost %d, depends on ",
692 INSN_UID (insn), inv->invno, inv->cost);
693 dump_bitmap (dump_file, inv->depends_on);
699 /* Record USE at DEF. */
702 record_use (struct def *def, rtx *use, rtx insn)
704 struct use *u = XNEW (struct use);
706 gcc_assert (REG_P (*use));
715 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
716 bitmap. Returns true if all dependencies of USE are known to be
717 loop invariants, false otherwise. */
720 check_dependency (basic_block bb, struct df_ref *use, bitmap depends_on)
724 struct df_link *defs;
725 struct def *def_data;
726 struct invariant *inv;
728 if (use->flags & DF_REF_READ_WRITE)
731 defs = DF_REF_CHAIN (use);
739 check_invariant_table_size ();
740 inv = invariant_table[DF_REF_ID(def)];
745 gcc_assert (def_data != NULL);
747 def_bb = DF_REF_BB (def);
748 /* Note that in case bb == def_bb, we know that the definition
749 dominates insn, because def has invariant_table[DF_REF_ID(def)]
750 defined and we process the insns in the basic block bb
752 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
755 bitmap_set_bit (depends_on, def_data->invno);
760 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
761 bitmap. Returns true if all dependencies of INSN are known to be
762 loop invariants, false otherwise. */
765 check_dependencies (rtx insn, bitmap depends_on)
767 struct df_ref **use_rec;
768 basic_block bb = BLOCK_FOR_INSN (insn);
770 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
771 if (!check_dependency (bb, *use_rec, depends_on))
773 for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
774 if (!check_dependency (bb, *use_rec, depends_on))
780 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
781 executed. ALWAYS_EXECUTED is true if the insn is always executed,
782 unless the program ends due to a function call. */
785 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
792 struct invariant *inv;
794 /* Until we get rid of LIBCALLS. */
795 if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
796 || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
797 || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
801 /* We can't move a CC0 setter without the user. */
802 if (sets_cc0_p (insn))
806 set = single_set (insn);
809 dest = SET_DEST (set);
812 || HARD_REGISTER_P (dest))
815 if (!may_assign_reg_p (SET_DEST (set))
816 || !check_maybe_invariant (SET_SRC (set)))
819 /* If the insn can throw exception, we cannot move it at all without changing
821 if (can_throw_internal (insn))
824 /* We cannot make trapping insn executed, unless it was executed before. */
825 if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
828 depends_on = BITMAP_ALLOC (NULL);
829 if (!check_dependencies (insn, depends_on))
831 BITMAP_FREE (depends_on);
836 def = XCNEW (struct def);
840 inv = create_new_invariant (def, insn, depends_on, always_executed);
844 ref = df_find_def (insn, dest);
845 check_invariant_table_size ();
846 invariant_table[DF_REF_ID(ref)] = inv;
850 /* Record registers used in INSN that have a unique invariant definition. */
853 record_uses (rtx insn)
855 struct df_ref **use_rec;
856 struct invariant *inv;
858 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
860 struct df_ref *use = *use_rec;
861 inv = invariant_for_use (use);
863 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
865 for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
867 struct df_ref *use = *use_rec;
868 inv = invariant_for_use (use);
870 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
874 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
875 executed. ALWAYS_EXECUTED is true if the insn is always executed,
876 unless the program ends due to a function call. */
879 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
881 find_invariant_insn (insn, always_reached, always_executed);
885 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
886 basic block is always executed. ALWAYS_EXECUTED is true if the basic
887 block is always executed, unless the program ends due to a function
891 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
895 FOR_BB_INSNS (bb, insn)
900 find_invariants_insn (insn, always_reached, always_executed);
904 && !CONST_OR_PURE_CALL_P (insn))
905 always_reached = false;
909 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
910 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
911 bitmap of basic blocks in BODY that are always executed unless the program
912 ends due to a function call. */
915 find_invariants_body (struct loop *loop, basic_block *body,
916 bitmap always_reached, bitmap always_executed)
920 for (i = 0; i < loop->num_nodes; i++)
921 find_invariants_bb (body[i],
922 bitmap_bit_p (always_reached, i),
923 bitmap_bit_p (always_executed, i));
926 /* Finds invariants in LOOP. */
929 find_invariants (struct loop *loop)
931 bitmap may_exit = BITMAP_ALLOC (NULL);
932 bitmap always_reached = BITMAP_ALLOC (NULL);
933 bitmap has_exit = BITMAP_ALLOC (NULL);
934 bitmap always_executed = BITMAP_ALLOC (NULL);
935 basic_block *body = get_loop_body_in_dom_order (loop);
937 find_exits (loop, body, may_exit, has_exit);
938 compute_always_reached (loop, body, may_exit, always_reached);
939 compute_always_reached (loop, body, has_exit, always_executed);
941 find_defs (loop, body);
942 find_invariants_body (loop, body, always_reached, always_executed);
943 merge_identical_invariants ();
945 BITMAP_FREE (always_reached);
946 BITMAP_FREE (always_executed);
947 BITMAP_FREE (may_exit);
948 BITMAP_FREE (has_exit);
952 /* Frees a list of uses USE. */
955 free_use_list (struct use *use)
959 for (; use; use = next)
966 /* Calculates cost and number of registers needed for moving invariant INV
967 out of the loop and stores them to *COST and *REGS_NEEDED. */
970 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
973 unsigned aregs_needed;
975 struct invariant *dep;
978 /* Find the representative of the class of the equivalent invariants. */
979 inv = VEC_index (invariant_p, invariants, inv->eqto);
984 || inv->stamp == actual_stamp)
986 inv->stamp = actual_stamp;
989 (*comp_cost) += inv->cost;
993 /* Hoisting constant pool constants into stack regs may cost more than
994 just single register. On x87, the balance is affected both by the
995 small number of FP registers, and by its register stack organization,
996 that forces us to add compensation code in and around the loop to
997 shuffle the operands to the top of stack before use, and pop them
998 from the stack after the loop finishes.
1000 To model this effect, we increase the number of registers needed for
1001 stack registers by two: one register push, and one register pop.
1002 This usually has the effect that FP constant loads from the constant
1003 pool are not moved out of the loop.
1005 Note that this also means that dependent invariants can not be moved.
1006 However, the primary purpose of this pass is to move loop invariant
1007 address arithmetic out of loops, and address arithmetic that depends
1008 on floating point constants is unlikely to ever occur. */
1009 rtx set = single_set (inv->insn);
1011 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1012 && constant_pool_constant_p (SET_SRC (set)))
1013 (*regs_needed) += 2;
1017 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1019 dep = VEC_index (invariant_p, invariants, depno);
1021 get_inv_cost (dep, &acomp_cost, &aregs_needed);
1024 /* We need to check always_executed, since if the original value of
1025 the invariant may be preserved, we may need to keep it in a
1026 separate register. TODO check whether the register has an
1027 use outside of the loop. */
1028 && dep->always_executed
1029 && !dep->def->uses->next)
1031 /* If this is a single use, after moving the dependency we will not
1032 need a new register. */
1036 (*regs_needed) += aregs_needed;
1037 (*comp_cost) += acomp_cost;
1041 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1042 of registers used in the loop, NEW_REGS is the number of new variables
1043 already added due to the invariant motion. The number of registers needed
1044 for it is stored in *REGS_NEEDED. */
1047 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1048 unsigned new_regs, unsigned regs_used)
1050 int comp_cost, size_cost;
1052 get_inv_cost (inv, &comp_cost, regs_needed);
1055 size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used)
1056 - estimate_reg_pressure_cost (new_regs, regs_used));
1058 return comp_cost - size_cost;
1061 /* Finds invariant with best gain for moving. Returns the gain, stores
1062 the invariant in *BEST and number of registers needed for it to
1063 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1064 NEW_REGS is the number of new variables already added due to invariant
1068 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1069 unsigned new_regs, unsigned regs_used)
1071 struct invariant *inv;
1072 int gain = 0, again;
1073 unsigned aregs_needed, invno;
1075 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1080 /* Only consider the "representatives" of equivalent invariants. */
1081 if (inv->eqto != inv->invno)
1084 again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used);
1089 *regs_needed = aregs_needed;
1096 /* Marks invariant INVNO and all its dependencies for moving. */
1099 set_move_mark (unsigned invno)
1101 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1104 /* Find the representative of the class of the equivalent invariants. */
1105 inv = VEC_index (invariant_p, invariants, inv->eqto);
1112 fprintf (dump_file, "Decided to move invariant %d\n", invno);
1114 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1116 set_move_mark (invno);
1120 /* Determines which invariants to move. */
1123 find_invariants_to_move (void)
1125 unsigned i, regs_used, regs_needed = 0, new_regs;
1126 struct invariant *inv = NULL;
1127 unsigned int n_regs = DF_REG_SIZE ();
1129 if (!VEC_length (invariant_p, invariants))
1132 /* We do not really do a good job in estimating number of registers used;
1133 we put some initial bound here to stand for induction variables etc.
1134 that we do not detect. */
1137 for (i = 0; i < n_regs; i++)
1139 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1141 /* This is a value that is used but not changed inside loop. */
1147 while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used) > 0)
1149 set_move_mark (inv->invno);
1150 new_regs += regs_needed;
1154 /* Returns true if all insns in SEQ are valid. */
1157 seq_insns_valid_p (rtx seq)
1161 for (x = seq; x; x = NEXT_INSN (x))
1162 if (insn_invalid_p (x))
1168 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1172 move_invariant_reg (struct loop *loop, unsigned invno)
1174 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1175 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1177 basic_block preheader = loop_preheader_edge (loop)->src;
1178 rtx reg, set, dest, seq, op;
1186 /* If this is a representative of the class of equivalent invariants,
1187 really move the invariant. Otherwise just replace its use with
1188 the register used for the representative. */
1191 if (inv->depends_on)
1193 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1195 if (!move_invariant_reg (loop, i))
1200 /* Move the set out of the loop. If the set is always executed (we could
1201 omit this condition if we know that the register is unused outside of the
1202 loop, but it does not seem worth finding out) and it has no uses that
1203 would not be dominated by it, we may just move it (TODO). Otherwise we
1204 need to create a temporary register. */
1205 set = single_set (inv->insn);
1206 dest = SET_DEST (set);
1207 reg = gen_reg_rtx (GET_MODE (dest));
1209 /* If the SET_DEST of the invariant insn is a pseudo, we can just move
1210 the insn out of the loop. Otherwise, we have to use gen_move_insn
1211 to let emit_move_insn produce a valid instruction stream. */
1212 if (REG_P (dest) && !HARD_REGISTER_P (dest))
1216 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1217 SET_DEST (set) = reg;
1218 df_insn_rescan (inv->insn);
1219 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1221 /* If there is a REG_EQUAL note on the insn we just moved, and
1222 insn is in a basic block that is not always executed, the note
1223 may no longer be valid after we move the insn.
1224 Note that uses in REG_EQUAL notes are taken into account in
1225 the computation of invariants. Hence it is safe to retain the
1226 note even if the note contains register references. */
1227 if (! inv->always_executed
1228 && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1229 remove_note (inv->insn, note);
1234 op = force_operand (SET_SRC (set), reg);
1241 emit_move_insn (reg, op);
1245 if (!seq_insns_valid_p (seq))
1247 emit_insn_after (seq, BB_END (preheader));
1249 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1250 delete_insn (inv->insn);
1255 if (!move_invariant_reg (loop, repr->invno))
1258 set = single_set (inv->insn);
1259 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1260 delete_insn (inv->insn);
1266 /* Replace the uses we know to be dominated. It saves work for copy
1267 propagation, and also it is necessary so that dependent invariants
1268 are computed right. */
1271 for (use = inv->def->uses; use; use = use->next)
1274 df_insn_rescan (use->insn);
1281 /* If we failed, clear move flag, so that we do not try to move inv
1284 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1286 inv->reg = NULL_RTX;
1291 /* Move selected invariant out of the LOOP. Newly created regs are marked
1292 in TEMPORARY_REGS. */
1295 move_invariants (struct loop *loop)
1297 struct invariant *inv;
1300 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1301 move_invariant_reg (loop, i);
1304 /* Initializes invariant motion data. */
1307 init_inv_motion_data (void)
1311 invariants = VEC_alloc (invariant_p, heap, 100);
1314 /* Frees the data allocated by invariant motion. */
1317 free_inv_motion_data (void)
1321 struct invariant *inv;
1323 check_invariant_table_size ();
1324 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1326 inv = invariant_table[i];
1330 gcc_assert (def != NULL);
1332 free_use_list (def->uses);
1334 invariant_table[i] = NULL;
1338 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1340 BITMAP_FREE (inv->depends_on);
1343 VEC_free (invariant_p, heap, invariants);
1346 /* Move the invariants out of the LOOP. */
1349 move_single_loop_invariants (struct loop *loop)
1351 init_inv_motion_data ();
1353 find_invariants (loop);
1354 find_invariants_to_move ();
1355 move_invariants (loop);
1357 free_inv_motion_data ();
1360 /* Releases the auxiliary data for LOOP. */
1363 free_loop_data (struct loop *loop)
1365 struct loop_data *data = LOOP_DATA (loop);
1371 /* Move the invariants out of the loops. */
1374 move_loop_invariants (void)
1379 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1380 /* Process the loops, innermost first. */
1381 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1383 move_single_loop_invariants (loop);
1386 FOR_EACH_LOOP (li, loop, 0)
1388 free_loop_data (loop);
1391 free (invariant_table);
1392 invariant_table = NULL;
1393 invariant_table_size = 0;
1395 #ifdef ENABLE_CHECKING
1396 verify_flow_info ();