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 3, 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 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, libcalls, etc.). This should be sufficient to cleanup things
22 like address arithmetics -- other more complicated invariants should be
23 eliminated on tree level 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. */
39 #include "coretypes.h"
43 #include "hard-reg-set.h"
45 #include "basic-block.h"
56 /* The data stored for the loop. */
60 struct loop *outermost_exit; /* The outermost exit of the loop. */
61 bool has_call; /* True if the loop contains a call. */
64 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
66 /* The description of an use. */
70 rtx *pos; /* Position of the use. */
71 rtx insn; /* The insn in that the use occurs. */
73 struct use *next; /* Next use in the list. */
76 /* The description of a def. */
80 struct use *uses; /* The list of uses that are uniquely reached
82 unsigned n_uses; /* Number of such uses. */
83 unsigned invno; /* The corresponding invariant. */
86 /* The data stored for each invariant. */
90 /* The number of the invariant. */
93 /* The number of the invariant with the same value. */
96 /* If we moved the invariant out of the loop, the register that contains its
100 /* The definition of the invariant. */
103 /* The insn in that it is defined. */
106 /* Whether it is always executed. */
107 bool always_executed;
109 /* Whether to move the invariant. */
112 /* Cost of the invariant. */
115 /* The invariants it depends on. */
118 /* Used for detecting already visited invariants during determining
119 costs of movements. */
123 /* Table of invariants indexed by the df_ref uid field. */
125 static unsigned int invariant_table_size = 0;
126 static struct invariant ** invariant_table;
128 /* Entry for hash table of invariant expressions. */
130 struct invariant_expr_entry
133 struct invariant *inv;
139 enum machine_mode mode;
145 /* The actual stamp for marking already visited invariants during determining
146 costs of movements. */
148 static unsigned actual_stamp;
150 typedef struct invariant *invariant_p;
152 DEF_VEC_P(invariant_p);
153 DEF_VEC_ALLOC_P(invariant_p, heap);
155 /* The invariants. */
157 static VEC(invariant_p,heap) *invariants;
159 /* Check the size of the invariant table and realloc if necessary. */
162 check_invariant_table_size (void)
164 if (invariant_table_size < DF_DEFS_TABLE_SIZE())
166 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
167 invariant_table = xrealloc (invariant_table,
168 sizeof (struct rtx_iv *) * new_size);
169 memset (&invariant_table[invariant_table_size], 0,
170 (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
171 invariant_table_size = new_size;
175 /* Test for possibility of invariantness of X. */
178 check_maybe_invariant (rtx x)
180 enum rtx_code code = GET_CODE (x);
195 case UNSPEC_VOLATILE:
203 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
204 It should not be hard, and might be faster than "elsewhere". */
206 /* Just handle the most trivial case where we load from an unchanging
207 location (most importantly, pic tables). */
208 if (MEM_READONLY_P (x))
214 /* Don't mess with insns declared volatile. */
215 if (MEM_VOLATILE_P (x))
223 fmt = GET_RTX_FORMAT (code);
224 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
228 if (!check_maybe_invariant (XEXP (x, i)))
231 else if (fmt[i] == 'E')
233 for (j = 0; j < XVECLEN (x, i); j++)
234 if (!check_maybe_invariant (XVECEXP (x, i, j)))
242 /* Returns the invariant definition for USE, or NULL if USE is not
245 static struct invariant *
246 invariant_for_use (struct df_ref *use)
248 struct df_link *defs;
250 basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
252 if (use->flags & DF_REF_READ_WRITE)
255 defs = DF_REF_CHAIN (use);
256 if (!defs || defs->next)
259 check_invariant_table_size ();
260 if (!invariant_table[DF_REF_ID(def)])
263 def_bb = DF_REF_BB (def);
264 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
266 return invariant_table[DF_REF_ID(def)];
269 /* Computes hash value for invariant expression X in INSN. */
272 hash_invariant_expr_1 (rtx insn, rtx x)
274 enum rtx_code code = GET_CODE (x);
277 hashval_t val = code;
280 struct invariant *inv;
289 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
292 use = df_find_use (insn, x);
294 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
295 inv = invariant_for_use (use);
297 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
299 gcc_assert (inv->eqto != ~0u);
306 fmt = GET_RTX_FORMAT (code);
307 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
310 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
311 else if (fmt[i] == 'E')
313 for (j = 0; j < XVECLEN (x, i); j++)
314 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
316 else if (fmt[i] == 'i' || fmt[i] == 'n')
323 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
324 and INSN2 have always the same value. */
327 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
329 enum rtx_code code = GET_CODE (e1);
332 struct df_ref *use1, *use2;
333 struct invariant *inv1 = NULL, *inv2 = NULL;
336 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
337 the other one. If both are VOIDmode, we rely on the caller of this
338 function to verify that their modes are the same. */
339 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
349 return rtx_equal_p (e1, e2);
352 use1 = df_find_use (insn1, e1);
353 use2 = df_find_use (insn2, e2);
355 inv1 = invariant_for_use (use1);
357 inv2 = invariant_for_use (use2);
360 return rtx_equal_p (e1, e2);
365 gcc_assert (inv1->eqto != ~0u);
366 gcc_assert (inv2->eqto != ~0u);
367 return inv1->eqto == inv2->eqto;
373 fmt = GET_RTX_FORMAT (code);
374 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
381 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
385 else if (fmt[i] == 'E')
387 if (XVECLEN (e1, i) != XVECLEN (e2, i))
390 for (j = 0; j < XVECLEN (e1, i); j++)
392 sub1 = XVECEXP (e1, i, j);
393 sub2 = XVECEXP (e2, i, j);
395 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
399 else if (fmt[i] == 'i' || fmt[i] == 'n')
401 if (XINT (e1, i) != XINT (e2, i))
404 /* Unhandled type of subexpression, we fail conservatively. */
412 /* Returns hash value for invariant expression entry E. */
415 hash_invariant_expr (const void *e)
417 const struct invariant_expr_entry *entry = e;
422 /* Compares invariant expression entries E1 and E2. */
425 eq_invariant_expr (const void *e1, const void *e2)
427 const struct invariant_expr_entry *entry1 = e1;
428 const struct invariant_expr_entry *entry2 = e2;
430 if (entry1->mode != entry2->mode)
433 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
434 entry2->inv->insn, entry2->expr);
437 /* Checks whether invariant with value EXPR in machine mode MODE is
438 recorded in EQ. If this is the case, return the invariant. Otherwise
439 insert INV to the table for this expression and return INV. */
441 static struct invariant *
442 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
443 struct invariant *inv)
445 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
446 struct invariant_expr_entry *entry;
447 struct invariant_expr_entry pentry;
453 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
459 entry = XNEW (struct invariant_expr_entry);
469 /* Finds invariants identical to INV and records the equivalence. EQ is the
470 hash table of the invariants. */
473 find_identical_invariants (htab_t eq, struct invariant *inv)
477 struct invariant *dep;
479 enum machine_mode mode;
481 if (inv->eqto != ~0u)
484 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
486 dep = VEC_index (invariant_p, invariants, depno);
487 find_identical_invariants (eq, dep);
490 set = single_set (inv->insn);
491 expr = SET_SRC (set);
492 mode = GET_MODE (expr);
493 if (mode == VOIDmode)
494 mode = GET_MODE (SET_DEST (set));
495 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
497 if (dump_file && inv->eqto != inv->invno)
499 "Invariant %d is equivalent to invariant %d.\n",
500 inv->invno, inv->eqto);
503 /* Find invariants with the same value and record the equivalences. */
506 merge_identical_invariants (void)
509 struct invariant *inv;
510 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
511 hash_invariant_expr, eq_invariant_expr, free);
513 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
514 find_identical_invariants (eq, inv);
519 /* Determines the basic blocks inside LOOP that are always executed and
520 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
521 basic blocks that may either exit the loop, or contain the call that
522 does not have to return. BODY is body of the loop obtained by
523 get_loop_body_in_dom_order. */
526 compute_always_reached (struct loop *loop, basic_block *body,
527 bitmap may_exit, bitmap always_reached)
531 for (i = 0; i < loop->num_nodes; i++)
533 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
534 bitmap_set_bit (always_reached, i);
536 if (bitmap_bit_p (may_exit, i))
541 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
542 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
543 additionally mark blocks that may exit due to a call. */
546 find_exits (struct loop *loop, basic_block *body,
547 bitmap may_exit, bitmap has_exit)
552 struct loop *outermost_exit = loop, *aexit;
553 bool has_call = false;
556 for (i = 0; i < loop->num_nodes; i++)
558 if (body[i]->loop_father == loop)
560 FOR_BB_INSNS (body[i], insn)
563 && !CONST_OR_PURE_CALL_P (insn))
566 bitmap_set_bit (may_exit, i);
571 FOR_EACH_EDGE (e, ei, body[i]->succs)
573 if (flow_bb_inside_loop_p (loop, e->dest))
576 bitmap_set_bit (may_exit, i);
577 bitmap_set_bit (has_exit, i);
578 outermost_exit = find_common_loop (outermost_exit,
579 e->dest->loop_father);
584 /* Use the data stored for the subloop to decide whether we may exit
585 through it. It is sufficient to do this for header of the loop,
586 as other basic blocks inside it must be dominated by it. */
587 if (body[i]->loop_father->header != body[i])
590 if (LOOP_DATA (body[i]->loop_father)->has_call)
593 bitmap_set_bit (may_exit, i);
595 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
598 bitmap_set_bit (may_exit, i);
599 bitmap_set_bit (has_exit, i);
601 if (flow_loop_nested_p (aexit, outermost_exit))
602 outermost_exit = aexit;
606 loop->aux = xcalloc (1, sizeof (struct loop_data));
607 LOOP_DATA (loop)->outermost_exit = outermost_exit;
608 LOOP_DATA (loop)->has_call = has_call;
611 /* Check whether we may assign a value to X from a register. */
614 may_assign_reg_p (rtx x)
616 return (GET_MODE (x) != VOIDmode
617 && GET_MODE (x) != BLKmode
618 && can_copy_p (GET_MODE (x))
620 || !HARD_REGISTER_P (x)
621 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
624 /* Finds definitions that may correspond to invariants in LOOP with body
628 find_defs (struct loop *loop, basic_block *body)
631 bitmap blocks = BITMAP_ALLOC (NULL);
633 for (i = 0; i < loop->num_nodes; i++)
634 bitmap_set_bit (blocks, body[i]->index);
636 df_remove_problem (df_chain);
637 df_process_deferred_rescans ();
638 df_chain_add_problem (DF_UD_CHAIN);
639 df_set_blocks (blocks);
644 fprintf (dump_file, "*****starting processing of loop ******\n");
645 print_rtl_with_bb (dump_file, get_insns ());
646 fprintf (dump_file, "*****ending processing of loop ******\n");
648 check_invariant_table_size ();
650 BITMAP_FREE (blocks);
653 /* Creates a new invariant for definition DEF in INSN, depending on invariants
654 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
655 unless the program ends due to a function call. The newly created invariant
658 static struct invariant *
659 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
660 bool always_executed)
662 struct invariant *inv = XNEW (struct invariant);
663 rtx set = single_set (insn);
666 inv->always_executed = always_executed;
667 inv->depends_on = depends_on;
669 /* If the set is simple, usually by moving it we move the whole store out of
670 the loop. Otherwise we save only cost of the computation. */
672 inv->cost = rtx_cost (set, SET);
674 inv->cost = rtx_cost (SET_SRC (set), SET);
681 inv->invno = VEC_length (invariant_p, invariants);
684 def->invno = inv->invno;
685 VEC_safe_push (invariant_p, heap, invariants, inv);
690 "Set in insn %d is invariant (%d), cost %d, depends on ",
691 INSN_UID (insn), inv->invno, inv->cost);
692 dump_bitmap (dump_file, inv->depends_on);
698 /* Record USE at DEF. */
701 record_use (struct def *def, rtx *use, rtx insn)
703 struct use *u = XNEW (struct use);
705 gcc_assert (REG_P (*use));
714 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
715 bitmap. Returns true if all dependencies of USE are known to be
716 loop invariants, false otherwise. */
719 check_dependency (basic_block bb, struct df_ref *use, bitmap depends_on)
723 struct df_link *defs;
724 struct def *def_data;
725 struct invariant *inv;
727 if (use->flags & DF_REF_READ_WRITE)
730 defs = DF_REF_CHAIN (use);
738 check_invariant_table_size ();
739 inv = invariant_table[DF_REF_ID(def)];
744 gcc_assert (def_data != NULL);
746 def_bb = DF_REF_BB (def);
747 /* Note that in case bb == def_bb, we know that the definition
748 dominates insn, because def has invariant_table[DF_REF_ID(def)]
749 defined and we process the insns in the basic block bb
751 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
754 bitmap_set_bit (depends_on, def_data->invno);
759 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
760 bitmap. Returns true if all dependencies of INSN are known to be
761 loop invariants, false otherwise. */
764 check_dependencies (rtx insn, bitmap depends_on)
766 struct df_ref **use_rec;
767 basic_block bb = BLOCK_FOR_INSN (insn);
769 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
770 if (!check_dependency (bb, *use_rec, depends_on))
772 for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
773 if (!check_dependency (bb, *use_rec, depends_on))
779 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
780 executed. ALWAYS_EXECUTED is true if the insn is always executed,
781 unless the program ends due to a function call. */
784 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
791 struct invariant *inv;
793 /* Until we get rid of LIBCALLS. */
794 if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
795 || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
796 || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
800 /* We can't move a CC0 setter without the user. */
801 if (sets_cc0_p (insn))
805 set = single_set (insn);
808 dest = SET_DEST (set);
811 || HARD_REGISTER_P (dest))
814 if (!may_assign_reg_p (SET_DEST (set))
815 || !check_maybe_invariant (SET_SRC (set)))
818 /* If the insn can throw exception, we cannot move it at all without changing
820 if (can_throw_internal (insn))
823 /* We cannot make trapping insn executed, unless it was executed before. */
824 if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
827 depends_on = BITMAP_ALLOC (NULL);
828 if (!check_dependencies (insn, depends_on))
830 BITMAP_FREE (depends_on);
835 def = XCNEW (struct def);
839 inv = create_new_invariant (def, insn, depends_on, always_executed);
843 ref = df_find_def (insn, dest);
844 check_invariant_table_size ();
845 invariant_table[DF_REF_ID(ref)] = inv;
849 /* Record registers used in INSN that have a unique invariant definition. */
852 record_uses (rtx insn)
854 struct df_ref **use_rec;
855 struct invariant *inv;
857 for (use_rec = DF_INSN_USES (insn); *use_rec; use_rec++)
859 struct df_ref *use = *use_rec;
860 inv = invariant_for_use (use);
862 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
864 for (use_rec = DF_INSN_EQ_USES (insn); *use_rec; use_rec++)
866 struct df_ref *use = *use_rec;
867 inv = invariant_for_use (use);
869 record_use (inv->def, DF_REF_REAL_LOC (use), DF_REF_INSN (use));
873 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
874 executed. ALWAYS_EXECUTED is true if the insn is always executed,
875 unless the program ends due to a function call. */
878 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
880 find_invariant_insn (insn, always_reached, always_executed);
884 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
885 basic block is always executed. ALWAYS_EXECUTED is true if the basic
886 block is always executed, unless the program ends due to a function
890 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
894 FOR_BB_INSNS (bb, insn)
899 find_invariants_insn (insn, always_reached, always_executed);
903 && !CONST_OR_PURE_CALL_P (insn))
904 always_reached = false;
908 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
909 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
910 bitmap of basic blocks in BODY that are always executed unless the program
911 ends due to a function call. */
914 find_invariants_body (struct loop *loop, basic_block *body,
915 bitmap always_reached, bitmap always_executed)
919 for (i = 0; i < loop->num_nodes; i++)
920 find_invariants_bb (body[i],
921 bitmap_bit_p (always_reached, i),
922 bitmap_bit_p (always_executed, i));
925 /* Finds invariants in LOOP. */
928 find_invariants (struct loop *loop)
930 bitmap may_exit = BITMAP_ALLOC (NULL);
931 bitmap always_reached = BITMAP_ALLOC (NULL);
932 bitmap has_exit = BITMAP_ALLOC (NULL);
933 bitmap always_executed = BITMAP_ALLOC (NULL);
934 basic_block *body = get_loop_body_in_dom_order (loop);
936 find_exits (loop, body, may_exit, has_exit);
937 compute_always_reached (loop, body, may_exit, always_reached);
938 compute_always_reached (loop, body, has_exit, always_executed);
940 find_defs (loop, body);
941 find_invariants_body (loop, body, always_reached, always_executed);
942 merge_identical_invariants ();
944 BITMAP_FREE (always_reached);
945 BITMAP_FREE (always_executed);
946 BITMAP_FREE (may_exit);
947 BITMAP_FREE (has_exit);
951 /* Frees a list of uses USE. */
954 free_use_list (struct use *use)
958 for (; use; use = next)
965 /* Calculates cost and number of registers needed for moving invariant INV
966 out of the loop and stores them to *COST and *REGS_NEEDED. */
969 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
972 unsigned aregs_needed;
974 struct invariant *dep;
977 /* Find the representative of the class of the equivalent invariants. */
978 inv = VEC_index (invariant_p, invariants, inv->eqto);
983 || inv->stamp == actual_stamp)
985 inv->stamp = actual_stamp;
988 (*comp_cost) += inv->cost;
992 /* Hoisting constant pool constants into stack regs may cost more than
993 just single register. On x87, the balance is affected both by the
994 small number of FP registers, and by its register stack organization,
995 that forces us to add compensation code in and around the loop to
996 shuffle the operands to the top of stack before use, and pop them
997 from the stack after the loop finishes.
999 To model this effect, we increase the number of registers needed for
1000 stack registers by two: one register push, and one register pop.
1001 This usually has the effect that FP constant loads from the constant
1002 pool are not moved out of the loop.
1004 Note that this also means that dependent invariants can not be moved.
1005 However, the primary purpose of this pass is to move loop invariant
1006 address arithmetic out of loops, and address arithmetic that depends
1007 on floating point constants is unlikely to ever occur. */
1008 rtx set = single_set (inv->insn);
1010 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1011 && constant_pool_constant_p (SET_SRC (set)))
1012 (*regs_needed) += 2;
1016 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1018 dep = VEC_index (invariant_p, invariants, depno);
1020 get_inv_cost (dep, &acomp_cost, &aregs_needed);
1023 /* We need to check always_executed, since if the original value of
1024 the invariant may be preserved, we may need to keep it in a
1025 separate register. TODO check whether the register has an
1026 use outside of the loop. */
1027 && dep->always_executed
1028 && !dep->def->uses->next)
1030 /* If this is a single use, after moving the dependency we will not
1031 need a new register. */
1035 (*regs_needed) += aregs_needed;
1036 (*comp_cost) += acomp_cost;
1040 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1041 of registers used in the loop, NEW_REGS is the number of new variables
1042 already added due to the invariant motion. The number of registers needed
1043 for it is stored in *REGS_NEEDED. */
1046 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1047 unsigned new_regs, unsigned regs_used)
1049 int comp_cost, size_cost;
1051 get_inv_cost (inv, &comp_cost, regs_needed);
1054 size_cost = (estimate_reg_pressure_cost (new_regs + *regs_needed, regs_used)
1055 - estimate_reg_pressure_cost (new_regs, regs_used));
1057 return comp_cost - size_cost;
1060 /* Finds invariant with best gain for moving. Returns the gain, stores
1061 the invariant in *BEST and number of registers needed for it to
1062 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1063 NEW_REGS is the number of new variables already added due to invariant
1067 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1068 unsigned new_regs, unsigned regs_used)
1070 struct invariant *inv;
1071 int gain = 0, again;
1072 unsigned aregs_needed, invno;
1074 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1079 /* Only consider the "representatives" of equivalent invariants. */
1080 if (inv->eqto != inv->invno)
1083 again = gain_for_invariant (inv, &aregs_needed, new_regs, regs_used);
1088 *regs_needed = aregs_needed;
1095 /* Marks invariant INVNO and all its dependencies for moving. */
1098 set_move_mark (unsigned invno)
1100 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1103 /* Find the representative of the class of the equivalent invariants. */
1104 inv = VEC_index (invariant_p, invariants, inv->eqto);
1111 fprintf (dump_file, "Decided to move invariant %d\n", invno);
1113 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1115 set_move_mark (invno);
1119 /* Determines which invariants to move. */
1122 find_invariants_to_move (void)
1124 unsigned i, regs_used, regs_needed = 0, new_regs;
1125 struct invariant *inv = NULL;
1126 unsigned int n_regs = DF_REG_SIZE ();
1128 if (!VEC_length (invariant_p, invariants))
1131 /* We do not really do a good job in estimating number of registers used;
1132 we put some initial bound here to stand for induction variables etc.
1133 that we do not detect. */
1136 for (i = 0; i < n_regs; i++)
1138 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1140 /* This is a value that is used but not changed inside loop. */
1146 while (best_gain_for_invariant (&inv, ®s_needed, new_regs, regs_used) > 0)
1148 set_move_mark (inv->invno);
1149 new_regs += regs_needed;
1153 /* Returns true if all insns in SEQ are valid. */
1156 seq_insns_valid_p (rtx seq)
1160 for (x = seq; x; x = NEXT_INSN (x))
1161 if (insn_invalid_p (x))
1167 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1171 move_invariant_reg (struct loop *loop, unsigned invno)
1173 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1174 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1176 basic_block preheader = loop_preheader_edge (loop)->src;
1177 rtx reg, set, dest, seq, op;
1185 /* If this is a representative of the class of equivalent invariants,
1186 really move the invariant. Otherwise just replace its use with
1187 the register used for the representative. */
1190 if (inv->depends_on)
1192 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1194 if (!move_invariant_reg (loop, i))
1199 /* Move the set out of the loop. If the set is always executed (we could
1200 omit this condition if we know that the register is unused outside of the
1201 loop, but it does not seem worth finding out) and it has no uses that
1202 would not be dominated by it, we may just move it (TODO). Otherwise we
1203 need to create a temporary register. */
1204 set = single_set (inv->insn);
1205 dest = SET_DEST (set);
1206 reg = gen_reg_rtx (GET_MODE (dest));
1208 /* If the SET_DEST of the invariant insn is a pseudo, we can just move
1209 the insn out of the loop. Otherwise, we have to use gen_move_insn
1210 to let emit_move_insn produce a valid instruction stream. */
1211 if (REG_P (dest) && !HARD_REGISTER_P (dest))
1215 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1216 SET_DEST (set) = reg;
1217 df_insn_rescan (inv->insn);
1218 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1220 /* If there is a REG_EQUAL note on the insn we just moved, and
1221 insn is in a basic block that is not always executed, the note
1222 may no longer be valid after we move the insn.
1223 Note that uses in REG_EQUAL notes are taken into account in
1224 the computation of invariants. Hence it is safe to retain the
1225 note even if the note contains register references. */
1226 if (! inv->always_executed
1227 && (note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX)))
1228 remove_note (inv->insn, note);
1233 op = force_operand (SET_SRC (set), reg);
1240 emit_move_insn (reg, op);
1244 if (!seq_insns_valid_p (seq))
1246 emit_insn_after (seq, BB_END (preheader));
1248 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1249 delete_insn (inv->insn);
1254 if (!move_invariant_reg (loop, repr->invno))
1257 set = single_set (inv->insn);
1258 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1259 delete_insn (inv->insn);
1265 /* Replace the uses we know to be dominated. It saves work for copy
1266 propagation, and also it is necessary so that dependent invariants
1267 are computed right. */
1270 for (use = inv->def->uses; use; use = use->next)
1273 df_insn_rescan (use->insn);
1280 /* If we failed, clear move flag, so that we do not try to move inv
1283 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1285 inv->reg = NULL_RTX;
1290 /* Move selected invariant out of the LOOP. Newly created regs are marked
1291 in TEMPORARY_REGS. */
1294 move_invariants (struct loop *loop)
1296 struct invariant *inv;
1299 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1300 move_invariant_reg (loop, i);
1303 /* Initializes invariant motion data. */
1306 init_inv_motion_data (void)
1310 invariants = VEC_alloc (invariant_p, heap, 100);
1313 /* Frees the data allocated by invariant motion. */
1316 free_inv_motion_data (void)
1320 struct invariant *inv;
1322 check_invariant_table_size ();
1323 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1325 inv = invariant_table[i];
1329 gcc_assert (def != NULL);
1331 free_use_list (def->uses);
1333 invariant_table[i] = NULL;
1337 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1339 BITMAP_FREE (inv->depends_on);
1342 VEC_free (invariant_p, heap, invariants);
1345 /* Move the invariants out of the LOOP. */
1348 move_single_loop_invariants (struct loop *loop)
1350 init_inv_motion_data ();
1352 find_invariants (loop);
1353 find_invariants_to_move ();
1354 move_invariants (loop);
1356 free_inv_motion_data ();
1359 /* Releases the auxiliary data for LOOP. */
1362 free_loop_data (struct loop *loop)
1364 struct loop_data *data = LOOP_DATA (loop);
1370 /* Move the invariants out of the loops. */
1373 move_loop_invariants (void)
1378 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1379 /* Process the loops, innermost first. */
1380 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1382 move_single_loop_invariants (loop);
1385 FOR_EACH_LOOP (li, loop, 0)
1387 free_loop_data (loop);
1390 free (invariant_table);
1391 invariant_table = NULL;
1392 invariant_table_size = 0;
1394 #ifdef ENABLE_CHECKING
1395 verify_flow_info ();