1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006 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"
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 /* Entry for hash table of invariant expressions. */
125 struct invariant_expr_entry
128 struct invariant
*inv
;
134 enum machine_mode mode
;
140 /* The actual stamp for marking already visited invariants during determining
141 costs of movements. */
143 static unsigned actual_stamp
;
145 typedef struct invariant
*invariant_p
;
147 DEF_VEC_P(invariant_p
);
148 DEF_VEC_ALLOC_P(invariant_p
, heap
);
150 /* The invariants. */
152 static VEC(invariant_p
,heap
) *invariants
;
154 /* The dataflow object. */
156 static struct df
*df
= NULL
;
158 /* Test for possibility of invariantness of X. */
161 check_maybe_invariant (rtx x
)
163 enum rtx_code code
= GET_CODE (x
);
178 case UNSPEC_VOLATILE
:
186 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
187 It should not be hard, and might be faster than "elsewhere". */
189 /* Just handle the most trivial case where we load from an unchanging
190 location (most importantly, pic tables). */
191 if (MEM_READONLY_P (x
))
197 /* Don't mess with insns declared volatile. */
198 if (MEM_VOLATILE_P (x
))
206 fmt
= GET_RTX_FORMAT (code
);
207 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
211 if (!check_maybe_invariant (XEXP (x
, i
)))
214 else if (fmt
[i
] == 'E')
216 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
217 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
225 /* Returns the invariant definition for USE, or NULL if USE is not
228 static struct invariant
*
229 invariant_for_use (struct df_ref
*use
)
231 struct df_link
*defs
;
233 basic_block bb
= BLOCK_FOR_INSN (use
->insn
), def_bb
;
235 defs
= DF_REF_CHAIN (use
);
236 if (!defs
|| defs
->next
)
239 if (!DF_REF_DATA (def
))
242 def_bb
= DF_REF_BB (def
);
243 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
245 return DF_REF_DATA (def
);
248 /* Computes hash value for invariant expression X in INSN. */
251 hash_invariant_expr_1 (rtx insn
, rtx x
)
253 enum rtx_code code
= GET_CODE (x
);
256 hashval_t val
= code
;
259 struct invariant
*inv
;
268 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
271 use
= df_find_use (df
, insn
, x
);
273 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
274 inv
= invariant_for_use (use
);
276 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
278 gcc_assert (inv
->eqto
!= ~0u);
285 fmt
= GET_RTX_FORMAT (code
);
286 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
289 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
290 else if (fmt
[i
] == 'E')
292 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
293 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
295 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
302 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
303 and INSN2 have always the same value. */
306 invariant_expr_equal_p (rtx insn1
, rtx e1
, rtx insn2
, rtx e2
)
308 enum rtx_code code
= GET_CODE (e1
);
311 struct df_ref
*use1
, *use2
;
312 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
315 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
316 the other one. If both are VOIDmode, we rely on the caller of this
317 function to verify that their modes are the same. */
318 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
328 return rtx_equal_p (e1
, e2
);
331 use1
= df_find_use (df
, insn1
, e1
);
332 use2
= df_find_use (df
, insn2
, e2
);
334 inv1
= invariant_for_use (use1
);
336 inv2
= invariant_for_use (use2
);
339 return rtx_equal_p (e1
, e2
);
344 gcc_assert (inv1
->eqto
!= ~0u);
345 gcc_assert (inv2
->eqto
!= ~0u);
346 return inv1
->eqto
== inv2
->eqto
;
352 fmt
= GET_RTX_FORMAT (code
);
353 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
360 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
364 else if (fmt
[i
] == 'E')
366 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
369 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
371 sub1
= XVECEXP (e1
, i
, j
);
372 sub2
= XVECEXP (e2
, i
, j
);
374 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
378 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
380 if (XINT (e1
, i
) != XINT (e2
, i
))
383 /* Unhandled type of subexpression, we fail conservatively. */
391 /* Returns hash value for invariant expression entry E. */
394 hash_invariant_expr (const void *e
)
396 const struct invariant_expr_entry
*entry
= e
;
401 /* Compares invariant expression entries E1 and E2. */
404 eq_invariant_expr (const void *e1
, const void *e2
)
406 const struct invariant_expr_entry
*entry1
= e1
;
407 const struct invariant_expr_entry
*entry2
= e2
;
409 if (entry1
->mode
!= entry2
->mode
)
412 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
413 entry2
->inv
->insn
, entry2
->expr
);
416 /* Checks whether invariant with value EXPR in machine mode MODE is
417 recorded in EQ. If this is the case, return the invariant. Otherwise
418 insert INV to the table for this expression and return INV. */
420 static struct invariant
*
421 find_or_insert_inv (htab_t eq
, rtx expr
, enum machine_mode mode
,
422 struct invariant
*inv
)
424 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
425 struct invariant_expr_entry
*entry
;
426 struct invariant_expr_entry pentry
;
432 slot
= htab_find_slot_with_hash (eq
, &pentry
, hash
, INSERT
);
438 entry
= XNEW (struct invariant_expr_entry
);
448 /* Finds invariants identical to INV and records the equivalence. EQ is the
449 hash table of the invariants. */
452 find_identical_invariants (htab_t eq
, struct invariant
*inv
)
456 struct invariant
*dep
;
458 enum machine_mode mode
;
460 if (inv
->eqto
!= ~0u)
463 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
465 dep
= VEC_index (invariant_p
, invariants
, depno
);
466 find_identical_invariants (eq
, dep
);
469 set
= single_set (inv
->insn
);
470 expr
= SET_SRC (set
);
471 mode
= GET_MODE (expr
);
472 if (mode
== VOIDmode
)
473 mode
= GET_MODE (SET_DEST (set
));
474 inv
->eqto
= find_or_insert_inv (eq
, expr
, mode
, inv
)->invno
;
476 if (dump_file
&& inv
->eqto
!= inv
->invno
)
478 "Invariant %d is equivalent to invariant %d.\n ",
479 inv
->invno
, inv
->eqto
);
482 /* Find invariants with the same value and record the equivalences. */
485 merge_identical_invariants (void)
488 struct invariant
*inv
;
489 htab_t eq
= htab_create (VEC_length (invariant_p
, invariants
),
490 hash_invariant_expr
, eq_invariant_expr
, free
);
492 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
493 find_identical_invariants (eq
, inv
);
498 /* Determines the basic blocks inside LOOP that are always executed and
499 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
500 basic blocks that may either exit the loop, or contain the call that
501 does not have to return. BODY is body of the loop obtained by
502 get_loop_body_in_dom_order. */
505 compute_always_reached (struct loop
*loop
, basic_block
*body
,
506 bitmap may_exit
, bitmap always_reached
)
510 for (i
= 0; i
< loop
->num_nodes
; i
++)
512 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
513 bitmap_set_bit (always_reached
, i
);
515 if (bitmap_bit_p (may_exit
, i
))
520 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
521 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
522 additionally mark blocks that may exit due to a call. */
525 find_exits (struct loop
*loop
, basic_block
*body
,
526 bitmap may_exit
, bitmap has_exit
)
531 struct loop
*outermost_exit
= loop
, *aexit
;
532 bool has_call
= false;
535 for (i
= 0; i
< loop
->num_nodes
; i
++)
537 if (body
[i
]->loop_father
== loop
)
539 FOR_BB_INSNS (body
[i
], insn
)
542 && !CONST_OR_PURE_CALL_P (insn
))
545 bitmap_set_bit (may_exit
, i
);
550 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
552 if (flow_bb_inside_loop_p (loop
, e
->dest
))
555 bitmap_set_bit (may_exit
, i
);
556 bitmap_set_bit (has_exit
, i
);
557 outermost_exit
= find_common_loop (outermost_exit
,
558 e
->dest
->loop_father
);
563 /* Use the data stored for the subloop to decide whether we may exit
564 through it. It is sufficient to do this for header of the loop,
565 as other basic blocks inside it must be dominated by it. */
566 if (body
[i
]->loop_father
->header
!= body
[i
])
569 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
572 bitmap_set_bit (may_exit
, i
);
574 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
577 bitmap_set_bit (may_exit
, i
);
578 bitmap_set_bit (has_exit
, i
);
580 if (flow_loop_nested_p (aexit
, outermost_exit
))
581 outermost_exit
= aexit
;
585 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
586 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
587 LOOP_DATA (loop
)->has_call
= has_call
;
590 /* Check whether we may assign a value to X from a register. */
593 may_assign_reg_p (rtx x
)
595 return (GET_MODE (x
) != VOIDmode
596 && GET_MODE (x
) != BLKmode
597 && can_copy_p (GET_MODE (x
))
599 || !HARD_REGISTER_P (x
)
600 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
603 /* Finds definitions that may correspond to invariants in LOOP with body
607 find_defs (struct loop
*loop
, basic_block
*body
)
610 bitmap blocks
= BITMAP_ALLOC (NULL
);
612 for (i
= 0; i
< loop
->num_nodes
; i
++)
613 bitmap_set_bit (blocks
, body
[i
]->index
);
615 df_set_blocks (df
, blocks
);
617 BITMAP_FREE (blocks
);
620 /* Creates a new invariant for definition DEF in INSN, depending on invariants
621 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
622 unless the program ends due to a function call. The newly created invariant
625 static struct invariant
*
626 create_new_invariant (struct def
*def
, rtx insn
, bitmap depends_on
,
627 bool always_executed
)
629 struct invariant
*inv
= XNEW (struct invariant
);
630 rtx set
= single_set (insn
);
633 inv
->always_executed
= always_executed
;
634 inv
->depends_on
= depends_on
;
636 /* If the set is simple, usually by moving it we move the whole store out of
637 the loop. Otherwise we save only cost of the computation. */
639 inv
->cost
= rtx_cost (set
, SET
);
641 inv
->cost
= rtx_cost (SET_SRC (set
), SET
);
648 inv
->invno
= VEC_length (invariant_p
, invariants
);
651 def
->invno
= inv
->invno
;
652 VEC_safe_push (invariant_p
, heap
, invariants
, inv
);
657 "Set in insn %d is invariant (%d), cost %d, depends on ",
658 INSN_UID (insn
), inv
->invno
, inv
->cost
);
659 dump_bitmap (dump_file
, inv
->depends_on
);
665 /* Record USE at DEF. */
668 record_use (struct def
*def
, rtx
*use
, rtx insn
)
670 struct use
*u
= XNEW (struct use
);
672 if (GET_CODE (*use
) == SUBREG
)
673 use
= &SUBREG_REG (*use
);
674 gcc_assert (REG_P (*use
));
683 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
687 check_dependencies (rtx insn
, bitmap depends_on
)
689 struct df_link
*defs
;
690 struct df_ref
*use
, *def
;
691 basic_block bb
= BLOCK_FOR_INSN (insn
), def_bb
;
692 struct def
*def_data
;
693 struct invariant
*inv
;
695 for (use
= DF_INSN_GET (df
, insn
)->uses
; use
; use
= use
->next_ref
)
697 defs
= DF_REF_CHAIN (use
);
705 inv
= DF_REF_DATA (def
);
710 gcc_assert (def_data
!= NULL
);
712 def_bb
= DF_REF_BB (def
);
713 /* Note that in case bb == def_bb, we know that the definition dominates
714 insn, because def has DF_REF_DATA defined and we process the insns
715 in the basic block bb sequentially. */
716 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
719 bitmap_set_bit (depends_on
, def_data
->invno
);
725 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
726 executed. ALWAYS_EXECUTED is true if the insn is always executed,
727 unless the program ends due to a function call. */
730 find_invariant_insn (rtx insn
, bool always_reached
, bool always_executed
)
737 struct invariant
*inv
;
739 /* Until we get rid of LIBCALLS. */
740 if (find_reg_note (insn
, REG_RETVAL
, NULL_RTX
)
741 || find_reg_note (insn
, REG_LIBCALL
, NULL_RTX
)
742 || find_reg_note (insn
, REG_NO_CONFLICT
, NULL_RTX
))
746 /* We can't move a CC0 setter without the user. */
747 if (sets_cc0_p (insn
))
751 set
= single_set (insn
);
754 dest
= SET_DEST (set
);
757 || HARD_REGISTER_P (dest
))
760 if (!may_assign_reg_p (SET_DEST (set
))
761 || !check_maybe_invariant (SET_SRC (set
)))
764 if (may_trap_p (PATTERN (insn
)))
769 /* Unless the exceptions are handled, the behavior is undefined
770 if the trap occurs. */
771 if (flag_non_call_exceptions
)
775 depends_on
= BITMAP_ALLOC (NULL
);
776 if (!check_dependencies (insn
, depends_on
))
778 BITMAP_FREE (depends_on
);
783 def
= XCNEW (struct def
);
787 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
791 ref
= df_find_def (df
, insn
, dest
);
792 DF_REF_DATA (ref
) = inv
;
796 /* Record registers used in INSN that have a unique invariant definition. */
799 record_uses (rtx insn
)
802 struct invariant
*inv
;
804 for (use
= DF_INSN_GET (df
, insn
)->uses
; use
; use
= use
->next_ref
)
806 inv
= invariant_for_use (use
);
808 record_use (inv
->def
, DF_REF_LOC (use
), DF_REF_INSN (use
));
812 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
813 executed. ALWAYS_EXECUTED is true if the insn is always executed,
814 unless the program ends due to a function call. */
817 find_invariants_insn (rtx insn
, bool always_reached
, bool always_executed
)
819 find_invariant_insn (insn
, always_reached
, always_executed
);
823 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
824 basic block is always executed. ALWAYS_EXECUTED is true if the basic
825 block is always executed, unless the program ends due to a function
829 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
833 FOR_BB_INSNS (bb
, insn
)
838 find_invariants_insn (insn
, always_reached
, always_executed
);
842 && !CONST_OR_PURE_CALL_P (insn
))
843 always_reached
= false;
847 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
848 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
849 bitmap of basic blocks in BODY that are always executed unless the program
850 ends due to a function call. */
853 find_invariants_body (struct loop
*loop
, basic_block
*body
,
854 bitmap always_reached
, bitmap always_executed
)
858 for (i
= 0; i
< loop
->num_nodes
; i
++)
859 find_invariants_bb (body
[i
],
860 bitmap_bit_p (always_reached
, i
),
861 bitmap_bit_p (always_executed
, i
));
864 /* Finds invariants in LOOP. */
867 find_invariants (struct loop
*loop
)
869 bitmap may_exit
= BITMAP_ALLOC (NULL
);
870 bitmap always_reached
= BITMAP_ALLOC (NULL
);
871 bitmap has_exit
= BITMAP_ALLOC (NULL
);
872 bitmap always_executed
= BITMAP_ALLOC (NULL
);
873 basic_block
*body
= get_loop_body_in_dom_order (loop
);
875 find_exits (loop
, body
, may_exit
, has_exit
);
876 compute_always_reached (loop
, body
, may_exit
, always_reached
);
877 compute_always_reached (loop
, body
, has_exit
, always_executed
);
879 find_defs (loop
, body
);
880 find_invariants_body (loop
, body
, always_reached
, always_executed
);
881 merge_identical_invariants ();
883 BITMAP_FREE (always_reached
);
884 BITMAP_FREE (always_executed
);
885 BITMAP_FREE (may_exit
);
886 BITMAP_FREE (has_exit
);
890 /* Frees a list of uses USE. */
893 free_use_list (struct use
*use
)
897 for (; use
; use
= next
)
904 /* Calculates cost and number of registers needed for moving invariant INV
905 out of the loop and stores them to *COST and *REGS_NEEDED. */
908 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
)
911 unsigned aregs_needed
;
913 struct invariant
*dep
;
916 /* Find the representative of the class of the equivalent invariants. */
917 inv
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
922 || inv
->stamp
== actual_stamp
)
924 inv
->stamp
= actual_stamp
;
927 (*comp_cost
) += inv
->cost
;
929 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
931 dep
= VEC_index (invariant_p
, invariants
, depno
);
933 get_inv_cost (dep
, &acomp_cost
, &aregs_needed
);
936 /* We need to check always_executed, since if the original value of
937 the invariant may be preserved, we may need to keep it in a
938 separate register. TODO check whether the register has an
939 use outside of the loop. */
940 && dep
->always_executed
941 && !dep
->def
->uses
->next
)
943 /* If this is a single use, after moving the dependency we will not
944 need a new register. */
948 (*regs_needed
) += aregs_needed
;
949 (*comp_cost
) += acomp_cost
;
953 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
954 of registers used in the loop, N_INV_USES is the number of uses of
955 invariants, NEW_REGS is the number of new variables already added due to
956 the invariant motion. The number of registers needed for it is stored in
960 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
961 unsigned new_regs
, unsigned regs_used
, unsigned n_inv_uses
)
963 int comp_cost
, size_cost
;
965 get_inv_cost (inv
, &comp_cost
, regs_needed
);
968 size_cost
= (global_cost_for_size (new_regs
+ *regs_needed
,
969 regs_used
, n_inv_uses
)
970 - global_cost_for_size (new_regs
, regs_used
, n_inv_uses
));
972 return comp_cost
- size_cost
;
975 /* Finds invariant with best gain for moving. Returns the gain, stores
976 the invariant in *BEST and number of registers needed for it to
977 *REGS_NEEDED. REGS_USED is the number of registers used in
978 the loop, N_INV_USES is the number of uses of invariants. NEW_REGS
979 is the number of new variables already added due to invariant motion. */
982 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
983 unsigned new_regs
, unsigned regs_used
,
986 struct invariant
*inv
;
988 unsigned aregs_needed
, invno
;
990 for (invno
= 0; VEC_iterate (invariant_p
, invariants
, invno
, inv
); invno
++)
995 /* Only consider the "representatives" of equivalent invariants. */
996 if (inv
->eqto
!= inv
->invno
)
999 again
= gain_for_invariant (inv
, &aregs_needed
,
1000 new_regs
, regs_used
, n_inv_uses
);
1005 *regs_needed
= aregs_needed
;
1012 /* Marks invariant INVNO and all its dependencies for moving. */
1015 set_move_mark (unsigned invno
)
1017 struct invariant
*inv
= VEC_index (invariant_p
, invariants
, invno
);
1020 /* Find the representative of the class of the equivalent invariants. */
1021 inv
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
1028 fprintf (dump_file
, "Decided to move invariant %d\n", invno
);
1030 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1032 set_move_mark (invno
);
1036 /* Determines which invariants to move. */
1039 find_invariants_to_move (void)
1041 unsigned i
, regs_used
, n_inv_uses
, regs_needed
= 0, new_regs
;
1042 struct invariant
*inv
= NULL
;
1043 unsigned int n_regs
= DF_REG_SIZE (df
);
1045 if (!VEC_length (invariant_p
, invariants
))
1048 /* Now something slightly more involved. First estimate the number of used
1052 /* We do not really do a good job in this estimation; put some initial bound
1053 here to stand for induction variables etc. that we do not detect. */
1056 for (i
= 0; i
< n_regs
; i
++)
1058 if (!DF_REGNO_FIRST_DEF (df
, i
) && DF_REGNO_LAST_USE (df
, i
))
1060 /* This is a value that is used but not changed inside loop. */
1065 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
1068 n_inv_uses
+= inv
->def
->n_uses
;
1072 while (best_gain_for_invariant (&inv
, ®s_needed
,
1073 new_regs
, regs_used
, n_inv_uses
) > 0)
1075 set_move_mark (inv
->invno
);
1076 new_regs
+= regs_needed
;
1080 /* Move invariant INVNO out of the LOOP. */
1083 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1085 struct invariant
*inv
= VEC_index (invariant_p
, invariants
, invno
);
1086 struct invariant
*repr
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
1088 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1089 rtx reg
, set
, seq
, op
;
1097 /* If this is a representative of the class of equivalent invariants,
1098 really move the invariant. Otherwise just replace its use with
1099 the register used for the representative. */
1102 if (inv
->depends_on
)
1104 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1106 move_invariant_reg (loop
, i
);
1110 /* Move the set out of the loop. If the set is always executed (we could
1111 omit this condition if we know that the register is unused outside of the
1112 loop, but it does not seem worth finding out) and it has no uses that
1113 would not be dominated by it, we may just move it (TODO). Otherwise we
1114 need to create a temporary register. */
1115 set
= single_set (inv
->insn
);
1116 reg
= gen_reg_rtx (GET_MODE (SET_DEST (set
)));
1117 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1119 /* If the SET_DEST of the invariant insn is a reg, we can just move
1120 the insn out of the loop. Otherwise, we have to use gen_move_insn
1121 to let emit_move_insn produce a valid instruction stream. */
1122 if (REG_P (SET_DEST (set
)))
1124 SET_DEST (set
) = reg
;
1125 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1130 op
= force_operand (SET_SRC (set
), reg
);
1132 emit_move_insn (reg
, op
);
1136 emit_insn_after (seq
, BB_END (preheader
));
1137 delete_insn (inv
->insn
);
1142 move_invariant_reg (loop
, repr
->invno
);
1144 set
= single_set (inv
->insn
);
1145 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1146 delete_insn (inv
->insn
);
1151 /* Replace the uses we know to be dominated. It saves work for copy
1152 propagation, and also it is necessary so that dependent invariants
1153 are computed right. */
1156 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1161 /* Move selected invariant out of the LOOP. Newly created regs are marked
1162 in TEMPORARY_REGS. */
1165 move_invariants (struct loop
*loop
)
1167 struct invariant
*inv
;
1170 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
1171 move_invariant_reg (loop
, i
);
1174 /* Initializes invariant motion data. */
1177 init_inv_motion_data (void)
1181 invariants
= VEC_alloc (invariant_p
, heap
, 100);
1184 /* Frees the data allocated by invariant motion. */
1187 free_inv_motion_data (void)
1191 struct invariant
*inv
;
1193 for (i
= 0; i
< DF_DEFS_SIZE (df
); i
++)
1195 struct df_ref
* ref
= DF_DEFS_GET (df
, i
);
1199 inv
= DF_REF_DATA (ref
);
1204 gcc_assert (def
!= NULL
);
1206 free_use_list (def
->uses
);
1208 DF_REF_DATA (ref
) = NULL
;
1211 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
1213 BITMAP_FREE (inv
->depends_on
);
1216 VEC_free (invariant_p
, heap
, invariants
);
1219 /* Move the invariants out of the LOOP. */
1222 move_single_loop_invariants (struct loop
*loop
)
1224 init_inv_motion_data ();
1226 find_invariants (loop
);
1227 find_invariants_to_move ();
1228 move_invariants (loop
);
1230 free_inv_motion_data ();
1233 /* Releases the auxiliary data for LOOP. */
1236 free_loop_data (struct loop
*loop
)
1238 struct loop_data
*data
= LOOP_DATA (loop
);
1244 /* Move the invariants out of the LOOPS. */
1247 move_loop_invariants (struct loops
*loops
)
1252 df
= df_init (DF_HARD_REGS
| DF_EQUIV_NOTES
);
1253 df_chain_add_problem (df
, DF_UD_CHAIN
);
1255 /* Process the loops, innermost first. */
1256 loop
= loops
->tree_root
;
1260 while (loop
!= loops
->tree_root
)
1262 move_single_loop_invariants (loop
);
1274 for (i
= 1; i
< loops
->num
; i
++)
1275 if (loops
->parray
[i
])
1276 free_loop_data (loops
->parray
[i
]);
1281 #ifdef ENABLE_CHECKING
1282 verify_flow_info ();