1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This implements the loop invariant motion pass. It is very simple
22 (no calls, no loads/stores, etc.). This should be sufficient to cleanup
23 things like address arithmetics -- other more complicated invariants should
24 be eliminated on GIMPLE 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"
58 /* The data stored for the loop. */
62 struct loop *outermost_exit; /* The outermost exit of the loop. */
63 bool has_call; /* True if the loop contains a call. */
66 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
68 /* The description of an use. */
72 rtx *pos; /* Position of the use. */
73 rtx insn; /* The insn in that the use occurs. */
75 struct use *next; /* Next use in the list. */
78 /* The description of a def. */
82 struct use *uses; /* The list of uses that are uniquely reached
84 unsigned n_uses; /* Number of such uses. */
85 unsigned invno; /* The corresponding invariant. */
88 /* The data stored for each invariant. */
92 /* The number of the invariant. */
95 /* The number of the invariant with the same value. */
98 /* If we moved the invariant out of the loop, the register that contains its
102 /* The definition of the invariant. */
105 /* The insn in that it is defined. */
108 /* Whether it is always executed. */
109 bool always_executed;
111 /* Whether to move the invariant. */
114 /* Cost of the invariant. */
117 /* The invariants it depends on. */
120 /* Used for detecting already visited invariants during determining
121 costs of movements. */
125 /* Table of invariants indexed by the df_ref uid field. */
127 static unsigned int invariant_table_size = 0;
128 static struct invariant ** invariant_table;
130 /* Entry for hash table of invariant expressions. */
132 struct invariant_expr_entry
135 struct invariant *inv;
141 enum machine_mode mode;
147 /* The actual stamp for marking already visited invariants during determining
148 costs of movements. */
150 static unsigned actual_stamp;
152 typedef struct invariant *invariant_p;
154 DEF_VEC_P(invariant_p);
155 DEF_VEC_ALLOC_P(invariant_p, heap);
157 /* The invariants. */
159 static VEC(invariant_p,heap) *invariants;
161 /* Check the size of the invariant table and realloc if necessary. */
164 check_invariant_table_size (void)
166 if (invariant_table_size < DF_DEFS_TABLE_SIZE())
168 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
169 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, 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);
197 case UNSPEC_VOLATILE:
205 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
206 It should not be hard, and might be faster than "elsewhere". */
208 /* Just handle the most trivial case where we load from an unchanging
209 location (most importantly, pic tables). */
210 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
216 /* Don't mess with insns declared volatile. */
217 if (MEM_VOLATILE_P (x))
225 fmt = GET_RTX_FORMAT (code);
226 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
230 if (!check_maybe_invariant (XEXP (x, i)))
233 else if (fmt[i] == 'E')
235 for (j = 0; j < XVECLEN (x, i); j++)
236 if (!check_maybe_invariant (XVECEXP (x, i, j)))
244 /* Returns the invariant definition for USE, or NULL if USE is not
247 static struct invariant *
248 invariant_for_use (df_ref use)
250 struct df_link *defs;
252 basic_block bb = DF_REF_BB (use), def_bb;
254 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
257 defs = DF_REF_CHAIN (use);
258 if (!defs || defs->next)
261 check_invariant_table_size ();
262 if (!invariant_table[DF_REF_ID(def)])
265 def_bb = DF_REF_BB (def);
266 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
268 return invariant_table[DF_REF_ID(def)];
271 /* Computes hash value for invariant expression X in INSN. */
274 hash_invariant_expr_1 (rtx insn, rtx x)
276 enum rtx_code code = GET_CODE (x);
279 hashval_t val = code;
282 struct invariant *inv;
292 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
295 use = df_find_use (insn, x);
297 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
298 inv = invariant_for_use (use);
300 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
302 gcc_assert (inv->eqto != ~0u);
309 fmt = GET_RTX_FORMAT (code);
310 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
313 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
314 else if (fmt[i] == 'E')
316 for (j = 0; j < XVECLEN (x, i); j++)
317 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
319 else if (fmt[i] == 'i' || fmt[i] == 'n')
326 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
327 and INSN2 have always the same value. */
330 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
332 enum rtx_code code = GET_CODE (e1);
336 struct invariant *inv1 = NULL, *inv2 = NULL;
339 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
340 the other one. If both are VOIDmode, we rely on the caller of this
341 function to verify that their modes are the same. */
342 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
353 return rtx_equal_p (e1, e2);
356 use1 = df_find_use (insn1, e1);
357 use2 = df_find_use (insn2, e2);
359 inv1 = invariant_for_use (use1);
361 inv2 = invariant_for_use (use2);
364 return rtx_equal_p (e1, e2);
369 gcc_assert (inv1->eqto != ~0u);
370 gcc_assert (inv2->eqto != ~0u);
371 return inv1->eqto == inv2->eqto;
377 fmt = GET_RTX_FORMAT (code);
378 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
385 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
389 else if (fmt[i] == 'E')
391 if (XVECLEN (e1, i) != XVECLEN (e2, i))
394 for (j = 0; j < XVECLEN (e1, i); j++)
396 sub1 = XVECEXP (e1, i, j);
397 sub2 = XVECEXP (e2, i, j);
399 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
403 else if (fmt[i] == 'i' || fmt[i] == 'n')
405 if (XINT (e1, i) != XINT (e2, i))
408 /* Unhandled type of subexpression, we fail conservatively. */
416 /* Returns hash value for invariant expression entry E. */
419 hash_invariant_expr (const void *e)
421 const struct invariant_expr_entry *const entry =
422 (const struct invariant_expr_entry *) e;
427 /* Compares invariant expression entries E1 and E2. */
430 eq_invariant_expr (const void *e1, const void *e2)
432 const struct invariant_expr_entry *const entry1 =
433 (const struct invariant_expr_entry *) e1;
434 const struct invariant_expr_entry *const entry2 =
435 (const struct invariant_expr_entry *) e2;
437 if (entry1->mode != entry2->mode)
440 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
441 entry2->inv->insn, entry2->expr);
444 /* Checks whether invariant with value EXPR in machine mode MODE is
445 recorded in EQ. If this is the case, return the invariant. Otherwise
446 insert INV to the table for this expression and return INV. */
448 static struct invariant *
449 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
450 struct invariant *inv)
452 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
453 struct invariant_expr_entry *entry;
454 struct invariant_expr_entry pentry;
460 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
461 entry = (struct invariant_expr_entry *) *slot;
466 entry = XNEW (struct invariant_expr_entry);
476 /* Finds invariants identical to INV and records the equivalence. EQ is the
477 hash table of the invariants. */
480 find_identical_invariants (htab_t eq, struct invariant *inv)
484 struct invariant *dep;
486 enum machine_mode mode;
488 if (inv->eqto != ~0u)
491 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
493 dep = VEC_index (invariant_p, invariants, depno);
494 find_identical_invariants (eq, dep);
497 set = single_set (inv->insn);
498 expr = SET_SRC (set);
499 mode = GET_MODE (expr);
500 if (mode == VOIDmode)
501 mode = GET_MODE (SET_DEST (set));
502 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
504 if (dump_file && inv->eqto != inv->invno)
506 "Invariant %d is equivalent to invariant %d.\n",
507 inv->invno, inv->eqto);
510 /* Find invariants with the same value and record the equivalences. */
513 merge_identical_invariants (void)
516 struct invariant *inv;
517 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
518 hash_invariant_expr, eq_invariant_expr, free);
520 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
521 find_identical_invariants (eq, inv);
526 /* Determines the basic blocks inside LOOP that are always executed and
527 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
528 basic blocks that may either exit the loop, or contain the call that
529 does not have to return. BODY is body of the loop obtained by
530 get_loop_body_in_dom_order. */
533 compute_always_reached (struct loop *loop, basic_block *body,
534 bitmap may_exit, bitmap always_reached)
538 for (i = 0; i < loop->num_nodes; i++)
540 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
541 bitmap_set_bit (always_reached, i);
543 if (bitmap_bit_p (may_exit, i))
548 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
549 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
550 additionally mark blocks that may exit due to a call. */
553 find_exits (struct loop *loop, basic_block *body,
554 bitmap may_exit, bitmap has_exit)
559 struct loop *outermost_exit = loop, *aexit;
560 bool has_call = false;
563 for (i = 0; i < loop->num_nodes; i++)
565 if (body[i]->loop_father == loop)
567 FOR_BB_INSNS (body[i], insn)
570 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
571 || !RTL_CONST_OR_PURE_CALL_P (insn)))
574 bitmap_set_bit (may_exit, i);
579 FOR_EACH_EDGE (e, ei, body[i]->succs)
581 if (flow_bb_inside_loop_p (loop, e->dest))
584 bitmap_set_bit (may_exit, i);
585 bitmap_set_bit (has_exit, i);
586 outermost_exit = find_common_loop (outermost_exit,
587 e->dest->loop_father);
592 /* Use the data stored for the subloop to decide whether we may exit
593 through it. It is sufficient to do this for header of the loop,
594 as other basic blocks inside it must be dominated by it. */
595 if (body[i]->loop_father->header != body[i])
598 if (LOOP_DATA (body[i]->loop_father)->has_call)
601 bitmap_set_bit (may_exit, i);
603 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
606 bitmap_set_bit (may_exit, i);
607 bitmap_set_bit (has_exit, i);
609 if (flow_loop_nested_p (aexit, outermost_exit))
610 outermost_exit = aexit;
614 loop->aux = xcalloc (1, sizeof (struct loop_data));
615 LOOP_DATA (loop)->outermost_exit = outermost_exit;
616 LOOP_DATA (loop)->has_call = has_call;
619 /* Check whether we may assign a value to X from a register. */
622 may_assign_reg_p (rtx x)
624 return (GET_MODE (x) != VOIDmode
625 && GET_MODE (x) != BLKmode
626 && can_copy_p (GET_MODE (x))
628 || !HARD_REGISTER_P (x)
629 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
632 /* Finds definitions that may correspond to invariants in LOOP with body
636 find_defs (struct loop *loop, basic_block *body)
639 bitmap blocks = BITMAP_ALLOC (NULL);
641 for (i = 0; i < loop->num_nodes; i++)
642 bitmap_set_bit (blocks, body[i]->index);
644 df_remove_problem (df_chain);
645 df_process_deferred_rescans ();
646 df_chain_add_problem (DF_UD_CHAIN);
647 df_set_blocks (blocks);
652 df_dump_region (dump_file);
653 fprintf (dump_file, "*****starting processing of loop ******\n");
654 print_rtl_with_bb (dump_file, get_insns ());
655 fprintf (dump_file, "*****ending processing of loop ******\n");
657 check_invariant_table_size ();
659 BITMAP_FREE (blocks);
662 /* Creates a new invariant for definition DEF in INSN, depending on invariants
663 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
664 unless the program ends due to a function call. The newly created invariant
667 static struct invariant *
668 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
669 bool always_executed)
671 struct invariant *inv = XNEW (struct invariant);
672 rtx set = single_set (insn);
673 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
676 inv->always_executed = always_executed;
677 inv->depends_on = depends_on;
679 /* If the set is simple, usually by moving it we move the whole store out of
680 the loop. Otherwise we save only cost of the computation. */
682 inv->cost = rtx_cost (set, SET, speed);
684 inv->cost = rtx_cost (SET_SRC (set), SET, speed);
691 inv->invno = VEC_length (invariant_p, invariants);
694 def->invno = inv->invno;
695 VEC_safe_push (invariant_p, heap, invariants, inv);
700 "Set in insn %d is invariant (%d), cost %d, depends on ",
701 INSN_UID (insn), inv->invno, inv->cost);
702 dump_bitmap (dump_file, inv->depends_on);
708 /* Record USE at DEF. */
711 record_use (struct def *def, rtx *use, rtx insn)
713 struct use *u = XNEW (struct use);
715 gcc_assert (REG_P (*use));
724 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
725 bitmap. Returns true if all dependencies of USE are known to be
726 loop invariants, false otherwise. */
729 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
733 struct df_link *defs;
734 struct def *def_data;
735 struct invariant *inv;
737 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
740 defs = DF_REF_CHAIN (use);
748 check_invariant_table_size ();
749 inv = invariant_table[DF_REF_ID(def)];
754 gcc_assert (def_data != NULL);
756 def_bb = DF_REF_BB (def);
757 /* Note that in case bb == def_bb, we know that the definition
758 dominates insn, because def has invariant_table[DF_REF_ID(def)]
759 defined and we process the insns in the basic block bb
761 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
764 bitmap_set_bit (depends_on, def_data->invno);
769 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
770 bitmap. Returns true if all dependencies of INSN are known to be
771 loop invariants, false otherwise. */
774 check_dependencies (rtx insn, bitmap depends_on)
776 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
778 basic_block bb = BLOCK_FOR_INSN (insn);
780 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
781 if (!check_dependency (bb, *use_rec, depends_on))
783 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
784 if (!check_dependency (bb, *use_rec, depends_on))
790 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
791 executed. ALWAYS_EXECUTED is true if the insn is always executed,
792 unless the program ends due to a function call. */
795 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
802 struct invariant *inv;
805 /* We can't move a CC0 setter without the user. */
806 if (sets_cc0_p (insn))
810 set = single_set (insn);
813 dest = SET_DEST (set);
816 || HARD_REGISTER_P (dest))
819 if (!may_assign_reg_p (SET_DEST (set))
820 || !check_maybe_invariant (SET_SRC (set)))
823 /* If the insn can throw exception, we cannot move it at all without changing
825 if (can_throw_internal (insn))
828 /* We cannot make trapping insn executed, unless it was executed before. */
829 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
832 depends_on = BITMAP_ALLOC (NULL);
833 if (!check_dependencies (insn, depends_on))
835 BITMAP_FREE (depends_on);
840 def = XCNEW (struct def);
844 inv = create_new_invariant (def, insn, depends_on, always_executed);
848 ref = df_find_def (insn, dest);
849 check_invariant_table_size ();
850 invariant_table[DF_REF_ID(ref)] = inv;
854 /* Record registers used in INSN that have a unique invariant definition. */
857 record_uses (rtx insn)
859 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
861 struct invariant *inv;
863 for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
865 df_ref use = *use_rec;
866 inv = invariant_for_use (use);
868 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
870 for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
872 df_ref use = *use_rec;
873 inv = invariant_for_use (use);
875 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
879 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
880 executed. ALWAYS_EXECUTED is true if the insn is always executed,
881 unless the program ends due to a function call. */
884 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
886 find_invariant_insn (insn, always_reached, always_executed);
890 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
891 basic block is always executed. ALWAYS_EXECUTED is true if the basic
892 block is always executed, unless the program ends due to a function
896 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
900 FOR_BB_INSNS (bb, insn)
905 find_invariants_insn (insn, always_reached, always_executed);
909 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
910 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
911 always_reached = false;
915 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
916 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
917 bitmap of basic blocks in BODY that are always executed unless the program
918 ends due to a function call. */
921 find_invariants_body (struct loop *loop, basic_block *body,
922 bitmap always_reached, bitmap always_executed)
926 for (i = 0; i < loop->num_nodes; i++)
927 find_invariants_bb (body[i],
928 bitmap_bit_p (always_reached, i),
929 bitmap_bit_p (always_executed, i));
932 /* Finds invariants in LOOP. */
935 find_invariants (struct loop *loop)
937 bitmap may_exit = BITMAP_ALLOC (NULL);
938 bitmap always_reached = BITMAP_ALLOC (NULL);
939 bitmap has_exit = BITMAP_ALLOC (NULL);
940 bitmap always_executed = BITMAP_ALLOC (NULL);
941 basic_block *body = get_loop_body_in_dom_order (loop);
943 find_exits (loop, body, may_exit, has_exit);
944 compute_always_reached (loop, body, may_exit, always_reached);
945 compute_always_reached (loop, body, has_exit, always_executed);
947 find_defs (loop, body);
948 find_invariants_body (loop, body, always_reached, always_executed);
949 merge_identical_invariants ();
951 BITMAP_FREE (always_reached);
952 BITMAP_FREE (always_executed);
953 BITMAP_FREE (may_exit);
954 BITMAP_FREE (has_exit);
958 /* Frees a list of uses USE. */
961 free_use_list (struct use *use)
965 for (; use; use = next)
972 /* Calculates cost and number of registers needed for moving invariant INV
973 out of the loop and stores them to *COST and *REGS_NEEDED. */
976 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
979 unsigned aregs_needed;
981 struct invariant *dep;
984 /* Find the representative of the class of the equivalent invariants. */
985 inv = VEC_index (invariant_p, invariants, inv->eqto);
990 || inv->stamp == actual_stamp)
992 inv->stamp = actual_stamp;
995 (*comp_cost) += inv->cost;
999 /* Hoisting constant pool constants into stack regs may cost more than
1000 just single register. On x87, the balance is affected both by the
1001 small number of FP registers, and by its register stack organization,
1002 that forces us to add compensation code in and around the loop to
1003 shuffle the operands to the top of stack before use, and pop them
1004 from the stack after the loop finishes.
1006 To model this effect, we increase the number of registers needed for
1007 stack registers by two: one register push, and one register pop.
1008 This usually has the effect that FP constant loads from the constant
1009 pool are not moved out of the loop.
1011 Note that this also means that dependent invariants can not be moved.
1012 However, the primary purpose of this pass is to move loop invariant
1013 address arithmetic out of loops, and address arithmetic that depends
1014 on floating point constants is unlikely to ever occur. */
1015 rtx set = single_set (inv->insn);
1017 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1018 && constant_pool_constant_p (SET_SRC (set)))
1019 (*regs_needed) += 2;
1023 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1025 dep = VEC_index (invariant_p, invariants, depno);
1027 get_inv_cost (dep, &acomp_cost, &aregs_needed);
1030 /* We need to check always_executed, since if the original value of
1031 the invariant may be preserved, we may need to keep it in a
1032 separate register. TODO check whether the register has an
1033 use outside of the loop. */
1034 && dep->always_executed
1035 && !dep->def->uses->next)
1037 /* If this is a single use, after moving the dependency we will not
1038 need a new register. */
1042 (*regs_needed) += aregs_needed;
1043 (*comp_cost) += acomp_cost;
1047 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1048 of registers used in the loop, NEW_REGS is the number of new variables
1049 already added due to the invariant motion. The number of registers needed
1050 for it is stored in *REGS_NEEDED. */
1053 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1054 unsigned new_regs, unsigned regs_used, bool speed)
1056 int comp_cost, size_cost;
1058 get_inv_cost (inv, &comp_cost, regs_needed);
1061 size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used, speed)
1062 - estimate_reg_pressure_cost (new_regs, regs_used, speed));
1064 return comp_cost - size_cost;
1067 /* Finds invariant with best gain for moving. Returns the gain, stores
1068 the invariant in *BEST and number of registers needed for it to
1069 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1070 NEW_REGS is the number of new variables already added due to invariant
1074 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1075 unsigned new_regs, unsigned regs_used, bool speed)
1077 struct invariant *inv;
1078 int gain = 0, again;
1079 unsigned aregs_needed, invno;
1081 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1086 /* Only consider the "representatives" of equivalent invariants. */
1087 if (inv->eqto != inv->invno)
1090 again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used,
1096 *regs_needed = aregs_needed;
1103 /* Marks invariant INVNO and all its dependencies for moving. */
1106 set_move_mark (unsigned invno)
1108 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1111 /* Find the representative of the class of the equivalent invariants. */
1112 inv = VEC_index (invariant_p, invariants, inv->eqto);
1119 fprintf (dump_file, "Decided to move invariant %d\n", invno);
1121 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1123 set_move_mark (invno);
1127 /* Determines which invariants to move. */
1130 find_invariants_to_move (bool speed)
1132 unsigned i, regs_used, regs_needed = 0, new_regs;
1133 struct invariant *inv = NULL;
1134 unsigned int n_regs = DF_REG_SIZE (df);
1136 if (!VEC_length (invariant_p, invariants))
1139 /* We do not really do a good job in estimating number of registers used;
1140 we put some initial bound here to stand for induction variables etc.
1141 that we do not detect. */
1144 for (i = 0; i < n_regs; i++)
1146 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1148 /* This is a value that is used but not changed inside loop. */
1154 while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used, speed) > 0)
1156 set_move_mark (inv->invno);
1157 new_regs += regs_needed;
1161 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1165 move_invariant_reg (struct loop *loop, unsigned invno)
1167 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1168 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1170 basic_block preheader = loop_preheader_edge (loop)->src;
1171 rtx reg, set, dest, note;
1179 /* If this is a representative of the class of equivalent invariants,
1180 really move the invariant. Otherwise just replace its use with
1181 the register used for the representative. */
1184 if (inv->depends_on)
1186 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1188 if (!move_invariant_reg (loop, i))
1193 /* Move the set out of the loop. If the set is always executed (we could
1194 omit this condition if we know that the register is unused outside of the
1195 loop, but it does not seem worth finding out) and it has no uses that
1196 would not be dominated by it, we may just move it (TODO). Otherwise we
1197 need to create a temporary register. */
1198 set = single_set (inv->insn);
1199 dest = SET_DEST (set);
1200 reg = gen_reg_rtx_and_attrs (dest);
1202 /* Try replacing the destination by a new pseudoregister. */
1203 if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
1205 df_insn_rescan (inv->insn);
1207 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1208 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1210 /* If there is a REG_EQUAL note on the insn we just moved, and
1211 insn is in a basic block that is not always executed, the note
1212 may no longer be valid after we move the insn.
1213 Note that uses in REG_EQUAL notes are taken into account in
1214 the computation of invariants. Hence it is safe to retain the
1215 note even if the note contains register references. */
1216 if (! inv->always_executed
1217 && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1218 remove_note (inv->insn, note);
1222 if (!move_invariant_reg (loop, repr->invno))
1225 set = single_set (inv->insn);
1226 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1227 delete_insn (inv->insn);
1233 /* Replace the uses we know to be dominated. It saves work for copy
1234 propagation, and also it is necessary so that dependent invariants
1235 are computed right. */
1238 for (use = inv->def->uses; use; use = use->next)
1241 df_insn_rescan (use->insn);
1248 /* If we failed, clear move flag, so that we do not try to move inv
1251 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1253 inv->reg = NULL_RTX;
1258 /* Move selected invariant out of the LOOP. Newly created regs are marked
1259 in TEMPORARY_REGS. */
1262 move_invariants (struct loop *loop)
1264 struct invariant *inv;
1267 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1268 move_invariant_reg (loop, i);
1271 /* Initializes invariant motion data. */
1274 init_inv_motion_data (void)
1278 invariants = VEC_alloc (invariant_p, heap, 100);
1281 /* Frees the data allocated by invariant motion. */
1284 free_inv_motion_data (void)
1288 struct invariant *inv;
1290 check_invariant_table_size ();
1291 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1293 inv = invariant_table[i];
1297 gcc_assert (def != NULL);
1299 free_use_list (def->uses);
1301 invariant_table[i] = NULL;
1305 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1307 BITMAP_FREE (inv->depends_on);
1310 VEC_free (invariant_p, heap, invariants);
1313 /* Move the invariants out of the LOOP. */
1316 move_single_loop_invariants (struct loop *loop)
1318 init_inv_motion_data ();
1320 find_invariants (loop);
1321 find_invariants_to_move (optimize_loop_for_speed_p (loop));
1322 move_invariants (loop);
1324 free_inv_motion_data ();
1327 /* Releases the auxiliary data for LOOP. */
1330 free_loop_data (struct loop *loop)
1332 struct loop_data *data = LOOP_DATA (loop);
1338 /* Move the invariants out of the loops. */
1341 move_loop_invariants (void)
1346 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1347 /* Process the loops, innermost first. */
1348 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1350 /* move_single_loop_invariants for very large loops
1351 is time consuming and might need a lot of memory. */
1352 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
1353 move_single_loop_invariants (loop);
1356 FOR_EACH_LOOP (li, loop, 0)
1358 free_loop_data (loop);
1361 free (invariant_table);
1362 invariant_table = NULL;
1363 invariant_table_size = 0;
1365 #ifdef ENABLE_CHECKING
1366 verify_flow_info ();