1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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, no loads/stores, etc.). This should be sufficient to cleanup
22 things like address arithmetics -- other more complicated invariants should
23 be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
25 We proceed loop by loop -- it is simpler than trying to handle things
26 globally and should not lose much. First we inspect all sets inside loop
27 and create a dependency graph on insns (saying "to move this insn, you must
28 also move the following insns").
30 We then need to determine what to move. We estimate the number of registers
31 used and move as many invariants as possible while we still have enough free
32 registers. We prefer the expensive invariants.
34 Then we move the selected invariants out of the loop, creating a new
35 temporaries for them if necessary. */
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
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
168 memset (&invariant_table
[invariant_table_size
], 0,
169 (new_size
- invariant_table_size
) * sizeof (struct rtx_iv
*));
170 invariant_table_size
= new_size
;
174 /* Test for possibility of invariantness of X. */
177 check_maybe_invariant (rtx x
)
179 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
) && !MEM_VOLATILE_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
= DF_REF_BB (use
), 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
;
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
))
351 return rtx_equal_p (e1
, e2
);
354 use1
= df_find_use (insn1
, e1
);
355 use2
= df_find_use (insn2
, e2
);
357 inv1
= invariant_for_use (use1
);
359 inv2
= invariant_for_use (use2
);
362 return rtx_equal_p (e1
, e2
);
367 gcc_assert (inv1
->eqto
!= ~0u);
368 gcc_assert (inv2
->eqto
!= ~0u);
369 return inv1
->eqto
== inv2
->eqto
;
375 fmt
= GET_RTX_FORMAT (code
);
376 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
383 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
387 else if (fmt
[i
] == 'E')
389 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
392 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
394 sub1
= XVECEXP (e1
, i
, j
);
395 sub2
= XVECEXP (e2
, i
, j
);
397 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
401 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
403 if (XINT (e1
, i
) != XINT (e2
, i
))
406 /* Unhandled type of subexpression, we fail conservatively. */
414 /* Returns hash value for invariant expression entry E. */
417 hash_invariant_expr (const void *e
)
419 const struct invariant_expr_entry
*const entry
=
420 (const struct invariant_expr_entry
*) e
;
425 /* Compares invariant expression entries E1 and E2. */
428 eq_invariant_expr (const void *e1
, const void *e2
)
430 const struct invariant_expr_entry
*const entry1
=
431 (const struct invariant_expr_entry
*) e1
;
432 const struct invariant_expr_entry
*const entry2
=
433 (const struct invariant_expr_entry
*) e2
;
435 if (entry1
->mode
!= entry2
->mode
)
438 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
439 entry2
->inv
->insn
, entry2
->expr
);
442 /* Checks whether invariant with value EXPR in machine mode MODE is
443 recorded in EQ. If this is the case, return the invariant. Otherwise
444 insert INV to the table for this expression and return INV. */
446 static struct invariant
*
447 find_or_insert_inv (htab_t eq
, rtx expr
, enum machine_mode mode
,
448 struct invariant
*inv
)
450 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
451 struct invariant_expr_entry
*entry
;
452 struct invariant_expr_entry pentry
;
458 slot
= htab_find_slot_with_hash (eq
, &pentry
, hash
, INSERT
);
459 entry
= (struct invariant_expr_entry
*) *slot
;
464 entry
= XNEW (struct invariant_expr_entry
);
474 /* Finds invariants identical to INV and records the equivalence. EQ is the
475 hash table of the invariants. */
478 find_identical_invariants (htab_t eq
, struct invariant
*inv
)
482 struct invariant
*dep
;
484 enum machine_mode mode
;
486 if (inv
->eqto
!= ~0u)
489 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
491 dep
= VEC_index (invariant_p
, invariants
, depno
);
492 find_identical_invariants (eq
, dep
);
495 set
= single_set (inv
->insn
);
496 expr
= SET_SRC (set
);
497 mode
= GET_MODE (expr
);
498 if (mode
== VOIDmode
)
499 mode
= GET_MODE (SET_DEST (set
));
500 inv
->eqto
= find_or_insert_inv (eq
, expr
, mode
, inv
)->invno
;
502 if (dump_file
&& inv
->eqto
!= inv
->invno
)
504 "Invariant %d is equivalent to invariant %d.\n",
505 inv
->invno
, inv
->eqto
);
508 /* Find invariants with the same value and record the equivalences. */
511 merge_identical_invariants (void)
514 struct invariant
*inv
;
515 htab_t eq
= htab_create (VEC_length (invariant_p
, invariants
),
516 hash_invariant_expr
, eq_invariant_expr
, free
);
518 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
519 find_identical_invariants (eq
, inv
);
524 /* Determines the basic blocks inside LOOP that are always executed and
525 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
526 basic blocks that may either exit the loop, or contain the call that
527 does not have to return. BODY is body of the loop obtained by
528 get_loop_body_in_dom_order. */
531 compute_always_reached (struct loop
*loop
, basic_block
*body
,
532 bitmap may_exit
, bitmap always_reached
)
536 for (i
= 0; i
< loop
->num_nodes
; i
++)
538 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
539 bitmap_set_bit (always_reached
, i
);
541 if (bitmap_bit_p (may_exit
, i
))
546 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
547 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
548 additionally mark blocks that may exit due to a call. */
551 find_exits (struct loop
*loop
, basic_block
*body
,
552 bitmap may_exit
, bitmap has_exit
)
557 struct loop
*outermost_exit
= loop
, *aexit
;
558 bool has_call
= false;
561 for (i
= 0; i
< loop
->num_nodes
; i
++)
563 if (body
[i
]->loop_father
== loop
)
565 FOR_BB_INSNS (body
[i
], insn
)
568 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
569 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
572 bitmap_set_bit (may_exit
, i
);
577 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
579 if (flow_bb_inside_loop_p (loop
, e
->dest
))
582 bitmap_set_bit (may_exit
, i
);
583 bitmap_set_bit (has_exit
, i
);
584 outermost_exit
= find_common_loop (outermost_exit
,
585 e
->dest
->loop_father
);
590 /* Use the data stored for the subloop to decide whether we may exit
591 through it. It is sufficient to do this for header of the loop,
592 as other basic blocks inside it must be dominated by it. */
593 if (body
[i
]->loop_father
->header
!= body
[i
])
596 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
599 bitmap_set_bit (may_exit
, i
);
601 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
604 bitmap_set_bit (may_exit
, i
);
605 bitmap_set_bit (has_exit
, i
);
607 if (flow_loop_nested_p (aexit
, outermost_exit
))
608 outermost_exit
= aexit
;
612 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
613 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
614 LOOP_DATA (loop
)->has_call
= has_call
;
617 /* Check whether we may assign a value to X from a register. */
620 may_assign_reg_p (rtx x
)
622 return (GET_MODE (x
) != VOIDmode
623 && GET_MODE (x
) != BLKmode
624 && can_copy_p (GET_MODE (x
))
626 || !HARD_REGISTER_P (x
)
627 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
630 /* Finds definitions that may correspond to invariants in LOOP with body
634 find_defs (struct loop
*loop
, basic_block
*body
)
637 bitmap blocks
= BITMAP_ALLOC (NULL
);
639 for (i
= 0; i
< loop
->num_nodes
; i
++)
640 bitmap_set_bit (blocks
, body
[i
]->index
);
642 df_remove_problem (df_chain
);
643 df_process_deferred_rescans ();
644 df_chain_add_problem (DF_UD_CHAIN
);
645 df_set_blocks (blocks
);
650 df_dump_region (dump_file
);
651 fprintf (dump_file
, "*****starting processing of loop ******\n");
652 print_rtl_with_bb (dump_file
, get_insns ());
653 fprintf (dump_file
, "*****ending processing of loop ******\n");
655 check_invariant_table_size ();
657 BITMAP_FREE (blocks
);
660 /* Creates a new invariant for definition DEF in INSN, depending on invariants
661 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
662 unless the program ends due to a function call. The newly created invariant
665 static struct invariant
*
666 create_new_invariant (struct def
*def
, rtx insn
, bitmap depends_on
,
667 bool always_executed
)
669 struct invariant
*inv
= XNEW (struct invariant
);
670 rtx set
= single_set (insn
);
673 inv
->always_executed
= always_executed
;
674 inv
->depends_on
= depends_on
;
676 /* If the set is simple, usually by moving it we move the whole store out of
677 the loop. Otherwise we save only cost of the computation. */
679 inv
->cost
= rtx_cost (set
, SET
);
681 inv
->cost
= rtx_cost (SET_SRC (set
), SET
);
688 inv
->invno
= VEC_length (invariant_p
, invariants
);
691 def
->invno
= inv
->invno
;
692 VEC_safe_push (invariant_p
, heap
, invariants
, inv
);
697 "Set in insn %d is invariant (%d), cost %d, depends on ",
698 INSN_UID (insn
), inv
->invno
, inv
->cost
);
699 dump_bitmap (dump_file
, inv
->depends_on
);
705 /* Record USE at DEF. */
708 record_use (struct def
*def
, rtx
*use
, rtx insn
)
710 struct use
*u
= XNEW (struct use
);
712 gcc_assert (REG_P (*use
));
721 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
722 bitmap. Returns true if all dependencies of USE are known to be
723 loop invariants, false otherwise. */
726 check_dependency (basic_block bb
, struct df_ref
*use
, bitmap depends_on
)
730 struct df_link
*defs
;
731 struct def
*def_data
;
732 struct invariant
*inv
;
734 if (use
->flags
& DF_REF_READ_WRITE
)
737 defs
= DF_REF_CHAIN (use
);
745 check_invariant_table_size ();
746 inv
= invariant_table
[DF_REF_ID(def
)];
751 gcc_assert (def_data
!= NULL
);
753 def_bb
= DF_REF_BB (def
);
754 /* Note that in case bb == def_bb, we know that the definition
755 dominates insn, because def has invariant_table[DF_REF_ID(def)]
756 defined and we process the insns in the basic block bb
758 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
761 bitmap_set_bit (depends_on
, def_data
->invno
);
766 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
767 bitmap. Returns true if all dependencies of INSN are known to be
768 loop invariants, false otherwise. */
771 check_dependencies (rtx insn
, bitmap depends_on
)
773 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
774 struct df_ref
**use_rec
;
775 basic_block bb
= BLOCK_FOR_INSN (insn
);
777 for (use_rec
= DF_INSN_INFO_USES (insn_info
); *use_rec
; use_rec
++)
778 if (!check_dependency (bb
, *use_rec
, depends_on
))
780 for (use_rec
= DF_INSN_INFO_EQ_USES (insn_info
); *use_rec
; use_rec
++)
781 if (!check_dependency (bb
, *use_rec
, depends_on
))
787 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
788 executed. ALWAYS_EXECUTED is true if the insn is always executed,
789 unless the program ends due to a function call. */
792 find_invariant_insn (rtx insn
, bool always_reached
, bool always_executed
)
799 struct invariant
*inv
;
802 /* We can't move a CC0 setter without the user. */
803 if (sets_cc0_p (insn
))
807 set
= single_set (insn
);
810 dest
= SET_DEST (set
);
813 || HARD_REGISTER_P (dest
))
816 if (!may_assign_reg_p (SET_DEST (set
))
817 || !check_maybe_invariant (SET_SRC (set
)))
820 /* If the insn can throw exception, we cannot move it at all without changing
822 if (can_throw_internal (insn
))
825 /* We cannot make trapping insn executed, unless it was executed before. */
826 if (may_trap_after_code_motion_p (PATTERN (insn
)) && !always_reached
)
829 depends_on
= BITMAP_ALLOC (NULL
);
830 if (!check_dependencies (insn
, depends_on
))
832 BITMAP_FREE (depends_on
);
837 def
= XCNEW (struct def
);
841 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
845 ref
= df_find_def (insn
, dest
);
846 check_invariant_table_size ();
847 invariant_table
[DF_REF_ID(ref
)] = inv
;
851 /* Record registers used in INSN that have a unique invariant definition. */
854 record_uses (rtx insn
)
856 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
857 struct df_ref
**use_rec
;
858 struct invariant
*inv
;
860 for (use_rec
= DF_INSN_INFO_USES (insn_info
); *use_rec
; use_rec
++)
862 struct df_ref
*use
= *use_rec
;
863 inv
= invariant_for_use (use
);
865 record_use (inv
->def
, DF_REF_REAL_LOC (use
), DF_REF_INSN (use
));
867 for (use_rec
= DF_INSN_INFO_EQ_USES (insn_info
); *use_rec
; use_rec
++)
869 struct df_ref
*use
= *use_rec
;
870 inv
= invariant_for_use (use
);
872 record_use (inv
->def
, DF_REF_REAL_LOC (use
), DF_REF_INSN (use
));
876 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
877 executed. ALWAYS_EXECUTED is true if the insn is always executed,
878 unless the program ends due to a function call. */
881 find_invariants_insn (rtx insn
, bool always_reached
, bool always_executed
)
883 find_invariant_insn (insn
, always_reached
, always_executed
);
887 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
888 basic block is always executed. ALWAYS_EXECUTED is true if the basic
889 block is always executed, unless the program ends due to a function
893 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
897 FOR_BB_INSNS (bb
, insn
)
902 find_invariants_insn (insn
, always_reached
, always_executed
);
906 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
907 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
908 always_reached
= false;
912 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
913 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
914 bitmap of basic blocks in BODY that are always executed unless the program
915 ends due to a function call. */
918 find_invariants_body (struct loop
*loop
, basic_block
*body
,
919 bitmap always_reached
, bitmap always_executed
)
923 for (i
= 0; i
< loop
->num_nodes
; i
++)
924 find_invariants_bb (body
[i
],
925 bitmap_bit_p (always_reached
, i
),
926 bitmap_bit_p (always_executed
, i
));
929 /* Finds invariants in LOOP. */
932 find_invariants (struct loop
*loop
)
934 bitmap may_exit
= BITMAP_ALLOC (NULL
);
935 bitmap always_reached
= BITMAP_ALLOC (NULL
);
936 bitmap has_exit
= BITMAP_ALLOC (NULL
);
937 bitmap always_executed
= BITMAP_ALLOC (NULL
);
938 basic_block
*body
= get_loop_body_in_dom_order (loop
);
940 find_exits (loop
, body
, may_exit
, has_exit
);
941 compute_always_reached (loop
, body
, may_exit
, always_reached
);
942 compute_always_reached (loop
, body
, has_exit
, always_executed
);
944 find_defs (loop
, body
);
945 find_invariants_body (loop
, body
, always_reached
, always_executed
);
946 merge_identical_invariants ();
948 BITMAP_FREE (always_reached
);
949 BITMAP_FREE (always_executed
);
950 BITMAP_FREE (may_exit
);
951 BITMAP_FREE (has_exit
);
955 /* Frees a list of uses USE. */
958 free_use_list (struct use
*use
)
962 for (; use
; use
= next
)
969 /* Calculates cost and number of registers needed for moving invariant INV
970 out of the loop and stores them to *COST and *REGS_NEEDED. */
973 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
)
976 unsigned aregs_needed
;
978 struct invariant
*dep
;
981 /* Find the representative of the class of the equivalent invariants. */
982 inv
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
987 || inv
->stamp
== actual_stamp
)
989 inv
->stamp
= actual_stamp
;
992 (*comp_cost
) += inv
->cost
;
996 /* Hoisting constant pool constants into stack regs may cost more than
997 just single register. On x87, the balance is affected both by the
998 small number of FP registers, and by its register stack organization,
999 that forces us to add compensation code in and around the loop to
1000 shuffle the operands to the top of stack before use, and pop them
1001 from the stack after the loop finishes.
1003 To model this effect, we increase the number of registers needed for
1004 stack registers by two: one register push, and one register pop.
1005 This usually has the effect that FP constant loads from the constant
1006 pool are not moved out of the loop.
1008 Note that this also means that dependent invariants can not be moved.
1009 However, the primary purpose of this pass is to move loop invariant
1010 address arithmetic out of loops, and address arithmetic that depends
1011 on floating point constants is unlikely to ever occur. */
1012 rtx set
= single_set (inv
->insn
);
1014 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1015 && constant_pool_constant_p (SET_SRC (set
)))
1016 (*regs_needed
) += 2;
1020 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1022 dep
= VEC_index (invariant_p
, invariants
, depno
);
1024 get_inv_cost (dep
, &acomp_cost
, &aregs_needed
);
1027 /* We need to check always_executed, since if the original value of
1028 the invariant may be preserved, we may need to keep it in a
1029 separate register. TODO check whether the register has an
1030 use outside of the loop. */
1031 && dep
->always_executed
1032 && !dep
->def
->uses
->next
)
1034 /* If this is a single use, after moving the dependency we will not
1035 need a new register. */
1039 (*regs_needed
) += aregs_needed
;
1040 (*comp_cost
) += acomp_cost
;
1044 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1045 of registers used in the loop, NEW_REGS is the number of new variables
1046 already added due to the invariant motion. The number of registers needed
1047 for it is stored in *REGS_NEEDED. */
1050 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1051 unsigned new_regs
, unsigned regs_used
)
1053 int comp_cost
, size_cost
;
1055 get_inv_cost (inv
, &comp_cost
, regs_needed
);
1058 size_cost
= (estimate_reg_pressure_cost (new_regs
+ *regs_needed
, regs_used
)
1059 - estimate_reg_pressure_cost (new_regs
, regs_used
));
1061 return comp_cost
- size_cost
;
1064 /* Finds invariant with best gain for moving. Returns the gain, stores
1065 the invariant in *BEST and number of registers needed for it to
1066 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1067 NEW_REGS is the number of new variables already added due to invariant
1071 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1072 unsigned new_regs
, unsigned regs_used
)
1074 struct invariant
*inv
;
1075 int gain
= 0, again
;
1076 unsigned aregs_needed
, invno
;
1078 for (invno
= 0; VEC_iterate (invariant_p
, invariants
, invno
, inv
); invno
++)
1083 /* Only consider the "representatives" of equivalent invariants. */
1084 if (inv
->eqto
!= inv
->invno
)
1087 again
= gain_for_invariant (inv
, &aregs_needed
, new_regs
, regs_used
);
1092 *regs_needed
= aregs_needed
;
1099 /* Marks invariant INVNO and all its dependencies for moving. */
1102 set_move_mark (unsigned invno
)
1104 struct invariant
*inv
= VEC_index (invariant_p
, invariants
, invno
);
1107 /* Find the representative of the class of the equivalent invariants. */
1108 inv
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
1115 fprintf (dump_file
, "Decided to move invariant %d\n", invno
);
1117 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1119 set_move_mark (invno
);
1123 /* Determines which invariants to move. */
1126 find_invariants_to_move (void)
1128 unsigned i
, regs_used
, regs_needed
= 0, new_regs
;
1129 struct invariant
*inv
= NULL
;
1130 unsigned int n_regs
= DF_REG_SIZE (df
);
1132 if (!VEC_length (invariant_p
, invariants
))
1135 /* We do not really do a good job in estimating number of registers used;
1136 we put some initial bound here to stand for induction variables etc.
1137 that we do not detect. */
1140 for (i
= 0; i
< n_regs
; i
++)
1142 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1144 /* This is a value that is used but not changed inside loop. */
1150 while (best_gain_for_invariant (&inv
, ®s_needed
, new_regs
, regs_used
) > 0)
1152 set_move_mark (inv
->invno
);
1153 new_regs
+= regs_needed
;
1157 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1161 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1163 struct invariant
*inv
= VEC_index (invariant_p
, invariants
, invno
);
1164 struct invariant
*repr
= VEC_index (invariant_p
, invariants
, inv
->eqto
);
1166 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1167 rtx reg
, set
, dest
, note
;
1175 /* If this is a representative of the class of equivalent invariants,
1176 really move the invariant. Otherwise just replace its use with
1177 the register used for the representative. */
1180 if (inv
->depends_on
)
1182 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1184 if (!move_invariant_reg (loop
, i
))
1189 /* Move the set out of the loop. If the set is always executed (we could
1190 omit this condition if we know that the register is unused outside of the
1191 loop, but it does not seem worth finding out) and it has no uses that
1192 would not be dominated by it, we may just move it (TODO). Otherwise we
1193 need to create a temporary register. */
1194 set
= single_set (inv
->insn
);
1195 dest
= SET_DEST (set
);
1196 reg
= gen_reg_rtx_and_attrs (dest
);
1198 /* Try replacing the destination by a new pseudoregister. */
1199 if (!validate_change (inv
->insn
, &SET_DEST (set
), reg
, false))
1201 df_insn_rescan (inv
->insn
);
1203 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1204 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1206 /* If there is a REG_EQUAL note on the insn we just moved, and
1207 insn is in a basic block that is not always executed, the note
1208 may no longer be valid after we move the insn.
1209 Note that uses in REG_EQUAL notes are taken into account in
1210 the computation of invariants. Hence it is safe to retain the
1211 note even if the note contains register references. */
1212 if (! inv
->always_executed
1213 && (note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
)))
1214 remove_note (inv
->insn
, note
);
1218 if (!move_invariant_reg (loop
, repr
->invno
))
1221 set
= single_set (inv
->insn
);
1222 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1223 delete_insn (inv
->insn
);
1229 /* Replace the uses we know to be dominated. It saves work for copy
1230 propagation, and also it is necessary so that dependent invariants
1231 are computed right. */
1234 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1237 df_insn_rescan (use
->insn
);
1244 /* If we failed, clear move flag, so that we do not try to move inv
1247 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1249 inv
->reg
= NULL_RTX
;
1254 /* Move selected invariant out of the LOOP. Newly created regs are marked
1255 in TEMPORARY_REGS. */
1258 move_invariants (struct loop
*loop
)
1260 struct invariant
*inv
;
1263 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
1264 move_invariant_reg (loop
, i
);
1267 /* Initializes invariant motion data. */
1270 init_inv_motion_data (void)
1274 invariants
= VEC_alloc (invariant_p
, heap
, 100);
1277 /* Frees the data allocated by invariant motion. */
1280 free_inv_motion_data (void)
1284 struct invariant
*inv
;
1286 check_invariant_table_size ();
1287 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1289 inv
= invariant_table
[i
];
1293 gcc_assert (def
!= NULL
);
1295 free_use_list (def
->uses
);
1297 invariant_table
[i
] = NULL
;
1301 for (i
= 0; VEC_iterate (invariant_p
, invariants
, i
, inv
); i
++)
1303 BITMAP_FREE (inv
->depends_on
);
1306 VEC_free (invariant_p
, heap
, invariants
);
1309 /* Move the invariants out of the LOOP. */
1312 move_single_loop_invariants (struct loop
*loop
)
1314 init_inv_motion_data ();
1316 find_invariants (loop
);
1317 find_invariants_to_move ();
1318 move_invariants (loop
);
1320 free_inv_motion_data ();
1323 /* Releases the auxiliary data for LOOP. */
1326 free_loop_data (struct loop
*loop
)
1328 struct loop_data
*data
= LOOP_DATA (loop
);
1334 /* Move the invariants out of the loops. */
1337 move_loop_invariants (void)
1342 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
1343 /* Process the loops, innermost first. */
1344 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1346 move_single_loop_invariants (loop
);
1349 FOR_EACH_LOOP (li
, loop
, 0)
1351 free_loop_data (loop
);
1354 free (invariant_table
);
1355 invariant_table
= NULL
;
1356 invariant_table_size
= 0;
1358 #ifdef ENABLE_CHECKING
1359 verify_flow_info ();