1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2015 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"
41 #include "hard-reg-set.h"
52 #include "dominance.h"
55 #include "basic-block.h"
63 #include "hash-table.h"
70 /* The data stored for the loop. */
74 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
75 bool has_call
; /* True if the loop contains a call. */
76 /* Maximal register pressure inside loop for given register class
77 (defined only for the pressure classes). */
78 int max_reg_pressure
[N_REG_CLASSES
];
79 /* Loop regs referenced and live pseudo-registers. */
81 bitmap_head regs_live
;
84 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
86 /* The description of an use. */
90 rtx
*pos
; /* Position of the use. */
91 rtx_insn
*insn
; /* The insn in that the use occurs. */
92 unsigned addr_use_p
; /* Whether the use occurs in an address. */
93 struct use
*next
; /* Next use in the list. */
96 /* The description of a def. */
100 struct use
*uses
; /* The list of uses that are uniquely reached
102 unsigned n_uses
; /* Number of such uses. */
103 unsigned n_addr_uses
; /* Number of uses in addresses. */
104 unsigned invno
; /* The corresponding invariant. */
107 /* The data stored for each invariant. */
111 /* The number of the invariant. */
114 /* The number of the invariant with the same value. */
117 /* The number of invariants which eqto this. */
120 /* If we moved the invariant out of the loop, the register that contains its
124 /* If we moved the invariant out of the loop, the original regno
125 that contained its value. */
128 /* The definition of the invariant. */
131 /* The insn in that it is defined. */
134 /* Whether it is always executed. */
135 bool always_executed
;
137 /* Whether to move the invariant. */
140 /* Whether the invariant is cheap when used as an address. */
143 /* Cost of the invariant. */
146 /* The invariants it depends on. */
149 /* Used for detecting already visited invariants during determining
150 costs of movements. */
154 /* Currently processed loop. */
155 static struct loop
*curr_loop
;
157 /* Table of invariants indexed by the df_ref uid field. */
159 static unsigned int invariant_table_size
= 0;
160 static struct invariant
** invariant_table
;
162 /* Entry for hash table of invariant expressions. */
164 struct invariant_expr_entry
167 struct invariant
*inv
;
179 /* The actual stamp for marking already visited invariants during determining
180 costs of movements. */
182 static unsigned actual_stamp
;
184 typedef struct invariant
*invariant_p
;
187 /* The invariants. */
189 static vec
<invariant_p
> invariants
;
191 /* Check the size of the invariant table and realloc if necessary. */
194 check_invariant_table_size (void)
196 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
198 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
199 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
200 memset (&invariant_table
[invariant_table_size
], 0,
201 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
202 invariant_table_size
= new_size
;
206 /* Test for possibility of invariantness of X. */
209 check_maybe_invariant (rtx x
)
211 enum rtx_code code
= GET_CODE (x
);
225 case UNSPEC_VOLATILE
:
233 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
234 It should not be hard, and might be faster than "elsewhere". */
236 /* Just handle the most trivial case where we load from an unchanging
237 location (most importantly, pic tables). */
238 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
244 /* Don't mess with insns declared volatile. */
245 if (MEM_VOLATILE_P (x
))
253 fmt
= GET_RTX_FORMAT (code
);
254 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
258 if (!check_maybe_invariant (XEXP (x
, i
)))
261 else if (fmt
[i
] == 'E')
263 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
264 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
272 /* Returns the invariant definition for USE, or NULL if USE is not
275 static struct invariant
*
276 invariant_for_use (df_ref use
)
278 struct df_link
*defs
;
280 basic_block bb
= DF_REF_BB (use
), def_bb
;
282 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
285 defs
= DF_REF_CHAIN (use
);
286 if (!defs
|| defs
->next
)
289 check_invariant_table_size ();
290 if (!invariant_table
[DF_REF_ID (def
)])
293 def_bb
= DF_REF_BB (def
);
294 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
296 return invariant_table
[DF_REF_ID (def
)];
299 /* Computes hash value for invariant expression X in INSN. */
302 hash_invariant_expr_1 (rtx_insn
*insn
, rtx x
)
304 enum rtx_code code
= GET_CODE (x
);
307 hashval_t val
= code
;
310 struct invariant
*inv
;
318 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
321 use
= df_find_use (insn
, x
);
323 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
324 inv
= invariant_for_use (use
);
326 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
328 gcc_assert (inv
->eqto
!= ~0u);
335 fmt
= GET_RTX_FORMAT (code
);
336 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
339 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
340 else if (fmt
[i
] == 'E')
342 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
343 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
345 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
352 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
353 and INSN2 have always the same value. */
356 invariant_expr_equal_p (rtx_insn
*insn1
, rtx e1
, rtx_insn
*insn2
, rtx e2
)
358 enum rtx_code code
= GET_CODE (e1
);
362 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
365 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
366 the other one. If both are VOIDmode, we rely on the caller of this
367 function to verify that their modes are the same. */
368 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
377 return rtx_equal_p (e1
, e2
);
380 use1
= df_find_use (insn1
, e1
);
381 use2
= df_find_use (insn2
, e2
);
383 inv1
= invariant_for_use (use1
);
385 inv2
= invariant_for_use (use2
);
388 return rtx_equal_p (e1
, e2
);
393 gcc_assert (inv1
->eqto
!= ~0u);
394 gcc_assert (inv2
->eqto
!= ~0u);
395 return inv1
->eqto
== inv2
->eqto
;
401 fmt
= GET_RTX_FORMAT (code
);
402 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
409 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
413 else if (fmt
[i
] == 'E')
415 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
418 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
420 sub1
= XVECEXP (e1
, i
, j
);
421 sub2
= XVECEXP (e2
, i
, j
);
423 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
427 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
429 if (XINT (e1
, i
) != XINT (e2
, i
))
432 /* Unhandled type of subexpression, we fail conservatively. */
440 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
442 typedef invariant_expr_entry value_type
;
443 typedef invariant_expr_entry compare_type
;
444 static inline hashval_t
hash (const value_type
*);
445 static inline bool equal (const value_type
*, const compare_type
*);
448 /* Returns hash value for invariant expression entry ENTRY. */
451 invariant_expr_hasher::hash (const value_type
*entry
)
456 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
459 invariant_expr_hasher::equal (const value_type
*entry1
,
460 const compare_type
*entry2
)
462 if (entry1
->mode
!= entry2
->mode
)
465 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
466 entry2
->inv
->insn
, entry2
->expr
);
469 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
471 /* Checks whether invariant with value EXPR in machine mode MODE is
472 recorded in EQ. If this is the case, return the invariant. Otherwise
473 insert INV to the table for this expression and return INV. */
475 static struct invariant
*
476 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, machine_mode mode
,
477 struct invariant
*inv
)
479 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
480 struct invariant_expr_entry
*entry
;
481 struct invariant_expr_entry pentry
;
482 invariant_expr_entry
**slot
;
487 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
493 entry
= XNEW (struct invariant_expr_entry
);
503 /* Finds invariants identical to INV and records the equivalence. EQ is the
504 hash table of the invariants. */
507 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
511 struct invariant
*dep
;
514 struct invariant
*tmp
;
516 if (inv
->eqto
!= ~0u)
519 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
521 dep
= invariants
[depno
];
522 find_identical_invariants (eq
, dep
);
525 set
= single_set (inv
->insn
);
526 expr
= SET_SRC (set
);
527 mode
= GET_MODE (expr
);
528 if (mode
== VOIDmode
)
529 mode
= GET_MODE (SET_DEST (set
));
531 tmp
= find_or_insert_inv (eq
, expr
, mode
, inv
);
532 inv
->eqto
= tmp
->invno
;
534 if (tmp
->invno
!= inv
->invno
&& inv
->always_executed
)
537 if (dump_file
&& inv
->eqto
!= inv
->invno
)
539 "Invariant %d is equivalent to invariant %d.\n",
540 inv
->invno
, inv
->eqto
);
543 /* Find invariants with the same value and record the equivalences. */
546 merge_identical_invariants (void)
549 struct invariant
*inv
;
550 invariant_htab_type
eq (invariants
.length ());
552 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
553 find_identical_invariants (&eq
, inv
);
556 /* Determines the basic blocks inside LOOP that are always executed and
557 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
558 basic blocks that may either exit the loop, or contain the call that
559 does not have to return. BODY is body of the loop obtained by
560 get_loop_body_in_dom_order. */
563 compute_always_reached (struct loop
*loop
, basic_block
*body
,
564 bitmap may_exit
, bitmap always_reached
)
568 for (i
= 0; i
< loop
->num_nodes
; i
++)
570 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
571 bitmap_set_bit (always_reached
, i
);
573 if (bitmap_bit_p (may_exit
, i
))
578 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
579 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
580 additionally mark blocks that may exit due to a call. */
583 find_exits (struct loop
*loop
, basic_block
*body
,
584 bitmap may_exit
, bitmap has_exit
)
589 struct loop
*outermost_exit
= loop
, *aexit
;
590 bool has_call
= false;
593 for (i
= 0; i
< loop
->num_nodes
; i
++)
595 if (body
[i
]->loop_father
== loop
)
597 FOR_BB_INSNS (body
[i
], insn
)
600 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
601 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
604 bitmap_set_bit (may_exit
, i
);
609 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
611 if (flow_bb_inside_loop_p (loop
, e
->dest
))
614 bitmap_set_bit (may_exit
, i
);
615 bitmap_set_bit (has_exit
, i
);
616 outermost_exit
= find_common_loop (outermost_exit
,
617 e
->dest
->loop_father
);
622 /* Use the data stored for the subloop to decide whether we may exit
623 through it. It is sufficient to do this for header of the loop,
624 as other basic blocks inside it must be dominated by it. */
625 if (body
[i
]->loop_father
->header
!= body
[i
])
628 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
631 bitmap_set_bit (may_exit
, i
);
633 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
636 bitmap_set_bit (may_exit
, i
);
637 bitmap_set_bit (has_exit
, i
);
639 if (flow_loop_nested_p (aexit
, outermost_exit
))
640 outermost_exit
= aexit
;
644 if (loop
->aux
== NULL
)
646 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
647 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
648 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
650 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
651 LOOP_DATA (loop
)->has_call
= has_call
;
654 /* Check whether we may assign a value to X from a register. */
657 may_assign_reg_p (rtx x
)
659 return (GET_MODE (x
) != VOIDmode
660 && GET_MODE (x
) != BLKmode
661 && can_copy_p (GET_MODE (x
))
663 || !HARD_REGISTER_P (x
)
664 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
667 /* Finds definitions that may correspond to invariants in LOOP with body
671 find_defs (struct loop
*loop
)
676 "*****starting processing of loop %d ******\n",
680 df_remove_problem (df_chain
);
681 df_process_deferred_rescans ();
682 df_chain_add_problem (DF_UD_CHAIN
);
683 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
684 df_analyze_loop (loop
);
685 check_invariant_table_size ();
689 df_dump_region (dump_file
);
691 "*****ending processing of loop %d ******\n",
696 /* Creates a new invariant for definition DEF in INSN, depending on invariants
697 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
698 unless the program ends due to a function call. The newly created invariant
701 static struct invariant
*
702 create_new_invariant (struct def
*def
, rtx_insn
*insn
, bitmap depends_on
,
703 bool always_executed
)
705 struct invariant
*inv
= XNEW (struct invariant
);
706 rtx set
= single_set (insn
);
707 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
710 inv
->always_executed
= always_executed
;
711 inv
->depends_on
= depends_on
;
713 /* If the set is simple, usually by moving it we move the whole store out of
714 the loop. Otherwise we save only cost of the computation. */
717 inv
->cost
= set_rtx_cost (set
, speed
);
718 /* ??? Try to determine cheapness of address computation. Unfortunately
719 the address cost is only a relative measure, we can't really compare
720 it with any absolute number, but only with other address costs.
721 But here we don't have any other addresses, so compare with a magic
722 number anyway. It has to be large enough to not regress PR33928
723 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
724 enough to not regress 410.bwaves either (by still moving reg+reg
726 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
727 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
728 ADDR_SPACE_GENERIC
, speed
) < 3;
732 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
733 inv
->cheap_address
= false;
738 inv
->orig_regno
= -1;
742 inv
->invno
= invariants
.length ();
749 def
->invno
= inv
->invno
;
750 invariants
.safe_push (inv
);
755 "Set in insn %d is invariant (%d), cost %d, depends on ",
756 INSN_UID (insn
), inv
->invno
, inv
->cost
);
757 dump_bitmap (dump_file
, inv
->depends_on
);
763 /* Record USE at DEF. */
766 record_use (struct def
*def
, df_ref use
)
768 struct use
*u
= XNEW (struct use
);
770 u
->pos
= DF_REF_REAL_LOC (use
);
771 u
->insn
= DF_REF_INSN (use
);
772 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
773 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
781 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
782 bitmap. Returns true if all dependencies of USE are known to be
783 loop invariants, false otherwise. */
786 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
790 struct df_link
*defs
;
791 struct def
*def_data
;
792 struct invariant
*inv
;
794 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
797 defs
= DF_REF_CHAIN (use
);
800 unsigned int regno
= DF_REF_REGNO (use
);
802 /* If this is the use of an uninitialized argument register that is
803 likely to be spilled, do not move it lest this might extend its
804 lifetime and cause reload to die. This can occur for a call to
805 a function taking complex number arguments and moving the insns
806 preparing the arguments without moving the call itself wouldn't
807 gain much in practice. */
808 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
809 && FUNCTION_ARG_REGNO_P (regno
)
810 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
820 check_invariant_table_size ();
821 inv
= invariant_table
[DF_REF_ID (def
)];
826 gcc_assert (def_data
!= NULL
);
828 def_bb
= DF_REF_BB (def
);
829 /* Note that in case bb == def_bb, we know that the definition
830 dominates insn, because def has invariant_table[DF_REF_ID(def)]
831 defined and we process the insns in the basic block bb
833 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
836 bitmap_set_bit (depends_on
, def_data
->invno
);
841 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
842 bitmap. Returns true if all dependencies of INSN are known to be
843 loop invariants, false otherwise. */
846 check_dependencies (rtx_insn
*insn
, bitmap depends_on
)
848 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
850 basic_block bb
= BLOCK_FOR_INSN (insn
);
852 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
853 if (!check_dependency (bb
, use
, depends_on
))
855 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
856 if (!check_dependency (bb
, use
, depends_on
))
862 /* Pre-check candidate DEST to skip the one which can not make a valid insn
863 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
865 pre_check_invariant_p (bool simple
, rtx dest
)
867 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
871 unsigned int i
= REGNO (dest
);
872 struct df_insn_info
*insn_info
;
875 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
877 ref
= DF_REF_INSN (use
);
878 insn_info
= DF_INSN_INFO_GET (ref
);
880 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
881 if (DF_REF_REGNO (def_rec
) == i
)
883 /* Multi definitions at this stage, most likely are due to
884 instruction constraints, which requires both read and write
885 on the same register. Since move_invariant_reg is not
886 powerful enough to handle such cases, just ignore the INV
887 and leave the chance to others. */
895 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
896 executed. ALWAYS_EXECUTED is true if the insn is always executed,
897 unless the program ends due to a function call. */
900 find_invariant_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
907 struct invariant
*inv
;
910 /* We can't move a CC0 setter without the user. */
911 if (sets_cc0_p (insn
))
915 set
= single_set (insn
);
918 dest
= SET_DEST (set
);
921 || HARD_REGISTER_P (dest
))
924 if (!may_assign_reg_p (dest
)
925 || !pre_check_invariant_p (simple
, dest
)
926 || !check_maybe_invariant (SET_SRC (set
)))
929 /* If the insn can throw exception, we cannot move it at all without changing
931 if (can_throw_internal (insn
))
934 /* We cannot make trapping insn executed, unless it was executed before. */
935 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
938 depends_on
= BITMAP_ALLOC (NULL
);
939 if (!check_dependencies (insn
, depends_on
))
941 BITMAP_FREE (depends_on
);
946 def
= XCNEW (struct def
);
950 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
954 ref
= df_find_def (insn
, dest
);
955 check_invariant_table_size ();
956 invariant_table
[DF_REF_ID (ref
)] = inv
;
960 /* Record registers used in INSN that have a unique invariant definition. */
963 record_uses (rtx_insn
*insn
)
965 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
967 struct invariant
*inv
;
969 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
971 inv
= invariant_for_use (use
);
973 record_use (inv
->def
, use
);
975 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
977 inv
= invariant_for_use (use
);
979 record_use (inv
->def
, use
);
983 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
984 executed. ALWAYS_EXECUTED is true if the insn is always executed,
985 unless the program ends due to a function call. */
988 find_invariants_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
990 find_invariant_insn (insn
, always_reached
, always_executed
);
994 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
995 basic block is always executed. ALWAYS_EXECUTED is true if the basic
996 block is always executed, unless the program ends due to a function
1000 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
1004 FOR_BB_INSNS (bb
, insn
)
1006 if (!NONDEBUG_INSN_P (insn
))
1009 find_invariants_insn (insn
, always_reached
, always_executed
);
1013 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1014 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
1015 always_reached
= false;
1019 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1020 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1021 bitmap of basic blocks in BODY that are always executed unless the program
1022 ends due to a function call. */
1025 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1026 bitmap always_reached
, bitmap always_executed
)
1030 for (i
= 0; i
< loop
->num_nodes
; i
++)
1031 find_invariants_bb (body
[i
],
1032 bitmap_bit_p (always_reached
, i
),
1033 bitmap_bit_p (always_executed
, i
));
1036 /* Finds invariants in LOOP. */
1039 find_invariants (struct loop
*loop
)
1041 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1042 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1043 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1044 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1045 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1047 find_exits (loop
, body
, may_exit
, has_exit
);
1048 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1049 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1052 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1053 merge_identical_invariants ();
1055 BITMAP_FREE (always_reached
);
1056 BITMAP_FREE (always_executed
);
1057 BITMAP_FREE (may_exit
);
1058 BITMAP_FREE (has_exit
);
1062 /* Frees a list of uses USE. */
1065 free_use_list (struct use
*use
)
1069 for (; use
; use
= next
)
1076 /* Return pressure class and number of hard registers (through *NREGS)
1077 for destination of INSN. */
1078 static enum reg_class
1079 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
1082 enum reg_class pressure_class
;
1083 rtx set
= single_set (insn
);
1085 /* Considered invariant insns have only one set. */
1086 gcc_assert (set
!= NULL_RTX
);
1087 reg
= SET_DEST (set
);
1088 if (GET_CODE (reg
) == SUBREG
)
1089 reg
= SUBREG_REG (reg
);
1093 pressure_class
= NO_REGS
;
1099 if (reg
== NULL_RTX
)
1100 pressure_class
= GENERAL_REGS
;
1103 pressure_class
= reg_allocno_class (REGNO (reg
));
1104 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1107 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1109 return pressure_class
;
1112 /* Calculates cost and number of registers needed for moving invariant INV
1113 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1114 the REG_CLASS of INV. Return
1115 -1: if INV is invalid.
1116 0: if INV and its depends_on have same reg_class
1117 1: if INV and its depends_on have different reg_classes. */
1120 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1124 unsigned aregs_needed
[N_REG_CLASSES
];
1126 struct invariant
*dep
;
1130 /* Find the representative of the class of the equivalent invariants. */
1131 inv
= invariants
[inv
->eqto
];
1134 if (! flag_ira_loop_pressure
)
1138 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1139 regs_needed
[ira_pressure_classes
[i
]] = 0;
1143 || inv
->stamp
== actual_stamp
)
1145 inv
->stamp
= actual_stamp
;
1147 if (! flag_ira_loop_pressure
)
1152 enum reg_class pressure_class
;
1154 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1155 regs_needed
[pressure_class
] += nregs
;
1156 *cl
= pressure_class
;
1160 if (!inv
->cheap_address
1161 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1162 (*comp_cost
) += inv
->cost
* inv
->eqno
;
1166 /* Hoisting constant pool constants into stack regs may cost more than
1167 just single register. On x87, the balance is affected both by the
1168 small number of FP registers, and by its register stack organization,
1169 that forces us to add compensation code in and around the loop to
1170 shuffle the operands to the top of stack before use, and pop them
1171 from the stack after the loop finishes.
1173 To model this effect, we increase the number of registers needed for
1174 stack registers by two: one register push, and one register pop.
1175 This usually has the effect that FP constant loads from the constant
1176 pool are not moved out of the loop.
1178 Note that this also means that dependent invariants can not be moved.
1179 However, the primary purpose of this pass is to move loop invariant
1180 address arithmetic out of loops, and address arithmetic that depends
1181 on floating point constants is unlikely to ever occur. */
1182 rtx set
= single_set (inv
->insn
);
1184 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1185 && constant_pool_constant_p (SET_SRC (set
)))
1187 if (flag_ira_loop_pressure
)
1188 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1190 regs_needed
[0] += 2;
1195 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1198 enum reg_class dep_cl
= ALL_REGS
;
1201 dep
= invariants
[depno
];
1203 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1207 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1209 if (! flag_ira_loop_pressure
)
1210 check_p
= aregs_needed
[0] != 0;
1213 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1214 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1216 check_p
= i
< ira_pressure_classes_num
;
1218 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1225 /* We need to check always_executed, since if the original value of
1226 the invariant may be preserved, we may need to keep it in a
1227 separate register. TODO check whether the register has an
1228 use outside of the loop. */
1229 && dep
->always_executed
1230 && !dep
->def
->uses
->next
)
1232 /* If this is a single use, after moving the dependency we will not
1233 need a new register. */
1234 if (! flag_ira_loop_pressure
)
1239 enum reg_class pressure_class
;
1241 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1242 aregs_needed
[pressure_class
] -= nregs
;
1246 if (! flag_ira_loop_pressure
)
1247 regs_needed
[0] += aregs_needed
[0];
1250 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1251 regs_needed
[ira_pressure_classes
[i
]]
1252 += aregs_needed
[ira_pressure_classes
[i
]];
1254 (*comp_cost
) += acomp_cost
;
1259 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1260 of registers used in the loop, NEW_REGS is the number of new variables
1261 already added due to the invariant motion. The number of registers needed
1262 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1263 through to estimate_reg_pressure_cost. */
1266 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1267 unsigned *new_regs
, unsigned regs_used
,
1268 bool speed
, bool call_p
)
1270 int comp_cost
, size_cost
;
1271 /* Workaround -Wmaybe-uninitialized false positive during
1272 profiledbootstrap by initializing it. */
1273 enum reg_class cl
= NO_REGS
;
1278 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1280 if (! flag_ira_loop_pressure
)
1282 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1283 regs_used
, speed
, call_p
)
1284 - estimate_reg_pressure_cost (new_regs
[0],
1285 regs_used
, speed
, call_p
));
1289 else if ((ret
== 0) && (cl
== NO_REGS
))
1290 /* Hoist it anyway since it does not impact register pressure. */
1295 enum reg_class pressure_class
;
1297 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1299 pressure_class
= ira_pressure_classes
[i
];
1301 if (!reg_classes_intersect_p (pressure_class
, cl
))
1304 if ((int) new_regs
[pressure_class
]
1305 + (int) regs_needed
[pressure_class
]
1306 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1307 + IRA_LOOP_RESERVED_REGS
1308 > ira_class_hard_regs_num
[pressure_class
])
1311 if (i
< ira_pressure_classes_num
)
1312 /* There will be register pressure excess and we want not to
1313 make this loop invariant motion. All loop invariants with
1314 non-positive gains will be rejected in function
1315 find_invariants_to_move. Therefore we return the negative
1318 One could think that this rejects also expensive loop
1319 invariant motions and this will hurt code performance.
1320 However numerous experiments with different heuristics
1321 taking invariant cost into account did not confirm this
1322 assumption. There are possible explanations for this
1324 o probably all expensive invariants were already moved out
1325 of the loop by PRE and gimple invariant motion pass.
1326 o expensive invariant execution will be hidden by insn
1327 scheduling or OOO processor hardware because usually such
1328 invariants have a lot of freedom to be executed
1330 Another reason for ignoring invariant cost vs spilling cost
1331 heuristics is also in difficulties to evaluate accurately
1332 spill cost at this stage. */
1338 return comp_cost
- size_cost
;
1341 /* Finds invariant with best gain for moving. Returns the gain, stores
1342 the invariant in *BEST and number of registers needed for it to
1343 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1344 NEW_REGS is the number of new variables already added due to invariant
1348 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1349 unsigned *new_regs
, unsigned regs_used
,
1350 bool speed
, bool call_p
)
1352 struct invariant
*inv
;
1353 int i
, gain
= 0, again
;
1354 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1356 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1361 /* Only consider the "representatives" of equivalent invariants. */
1362 if (inv
->eqto
!= inv
->invno
)
1365 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1371 if (! flag_ira_loop_pressure
)
1372 regs_needed
[0] = aregs_needed
[0];
1375 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1376 regs_needed
[ira_pressure_classes
[i
]]
1377 = aregs_needed
[ira_pressure_classes
[i
]];
1385 /* Marks invariant INVNO and all its dependencies for moving. */
1388 set_move_mark (unsigned invno
, int gain
)
1390 struct invariant
*inv
= invariants
[invno
];
1393 /* Find the representative of the class of the equivalent invariants. */
1394 inv
= invariants
[inv
->eqto
];
1403 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1406 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1410 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1412 set_move_mark (invno
, -1);
1416 /* Determines which invariants to move. */
1419 find_invariants_to_move (bool speed
, bool call_p
)
1422 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1423 struct invariant
*inv
= NULL
;
1425 if (!invariants
.length ())
1428 if (flag_ira_loop_pressure
)
1429 /* REGS_USED is actually never used when the flag is on. */
1432 /* We do not really do a good job in estimating number of
1433 registers used; we put some initial bound here to stand for
1434 induction variables etc. that we do not detect. */
1436 unsigned int n_regs
= DF_REG_SIZE (df
);
1440 for (i
= 0; i
< n_regs
; i
++)
1442 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1444 /* This is a value that is used but not changed inside loop. */
1450 if (! flag_ira_loop_pressure
)
1451 new_regs
[0] = regs_needed
[0] = 0;
1454 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1455 new_regs
[ira_pressure_classes
[i
]] = 0;
1457 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1458 new_regs
, regs_used
,
1459 speed
, call_p
)) > 0)
1461 set_move_mark (inv
->invno
, gain
);
1462 if (! flag_ira_loop_pressure
)
1463 new_regs
[0] += regs_needed
[0];
1466 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1467 new_regs
[ira_pressure_classes
[i
]]
1468 += regs_needed
[ira_pressure_classes
[i
]];
1473 /* Replace the uses, reached by the definition of invariant INV, by REG.
1475 IN_GROUP is nonzero if this is part of a group of changes that must be
1476 performed as a group. In that case, the changes will be stored. The
1477 function `apply_change_group' will validate and apply the changes. */
1480 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1482 /* Replace the uses we know to be dominated. It saves work for copy
1483 propagation, and also it is necessary so that dependent invariants
1484 are computed right. */
1488 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1489 validate_change (use
->insn
, use
->pos
, reg
, true);
1491 /* If we aren't part of a larger group, apply the changes now. */
1493 return apply_change_group ();
1499 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1503 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1505 struct invariant
*inv
= invariants
[invno
];
1506 struct invariant
*repr
= invariants
[inv
->eqto
];
1508 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1509 rtx reg
, set
, dest
, note
;
1518 /* If this is a representative of the class of equivalent invariants,
1519 really move the invariant. Otherwise just replace its use with
1520 the register used for the representative. */
1523 if (inv
->depends_on
)
1525 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1527 if (!move_invariant_reg (loop
, i
))
1532 /* Move the set out of the loop. If the set is always executed (we could
1533 omit this condition if we know that the register is unused outside of
1534 the loop, but it does not seem worth finding out) and it has no uses
1535 that would not be dominated by it, we may just move it (TODO).
1536 Otherwise we need to create a temporary register. */
1537 set
= single_set (inv
->insn
);
1538 reg
= dest
= SET_DEST (set
);
1539 if (GET_CODE (reg
) == SUBREG
)
1540 reg
= SUBREG_REG (reg
);
1542 regno
= REGNO (reg
);
1544 reg
= gen_reg_rtx_and_attrs (dest
);
1546 /* Try replacing the destination by a new pseudoregister. */
1547 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1549 /* As well as all the dominated uses. */
1550 replace_uses (inv
, reg
, true);
1552 /* And validate all the changes. */
1553 if (!apply_change_group ())
1556 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1557 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1559 /* If there is a REG_EQUAL note on the insn we just moved, and the
1560 insn is in a basic block that is not always executed or the note
1561 contains something for which we don't know the invariant status,
1562 the note may no longer be valid after we move the insn. Note that
1563 uses in REG_EQUAL notes are taken into account in the computation
1564 of invariants, so it is safe to retain the note even if it contains
1565 register references for which we know the invariant status. */
1566 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1567 && (!inv
->always_executed
1568 || !check_maybe_invariant (XEXP (note
, 0))))
1569 remove_note (inv
->insn
, note
);
1573 if (!move_invariant_reg (loop
, repr
->invno
))
1576 regno
= repr
->orig_regno
;
1577 if (!replace_uses (inv
, reg
, false))
1579 set
= single_set (inv
->insn
);
1580 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1581 delete_insn (inv
->insn
);
1585 inv
->orig_regno
= regno
;
1590 /* If we failed, clear move flag, so that we do not try to move inv
1593 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1595 inv
->reg
= NULL_RTX
;
1596 inv
->orig_regno
= -1;
1601 /* Move selected invariant out of the LOOP. Newly created regs are marked
1602 in TEMPORARY_REGS. */
1605 move_invariants (struct loop
*loop
)
1607 struct invariant
*inv
;
1610 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1611 move_invariant_reg (loop
, i
);
1612 if (flag_ira_loop_pressure
&& resize_reg_info ())
1614 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1615 if (inv
->reg
!= NULL_RTX
)
1617 if (inv
->orig_regno
>= 0)
1618 setup_reg_classes (REGNO (inv
->reg
),
1619 reg_preferred_class (inv
->orig_regno
),
1620 reg_alternate_class (inv
->orig_regno
),
1621 reg_allocno_class (inv
->orig_regno
));
1623 setup_reg_classes (REGNO (inv
->reg
),
1624 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1629 /* Initializes invariant motion data. */
1632 init_inv_motion_data (void)
1636 invariants
.create (100);
1639 /* Frees the data allocated by invariant motion. */
1642 free_inv_motion_data (void)
1646 struct invariant
*inv
;
1648 check_invariant_table_size ();
1649 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1651 inv
= invariant_table
[i
];
1655 gcc_assert (def
!= NULL
);
1657 free_use_list (def
->uses
);
1659 invariant_table
[i
] = NULL
;
1663 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1665 BITMAP_FREE (inv
->depends_on
);
1668 invariants
.release ();
1671 /* Move the invariants out of the LOOP. */
1674 move_single_loop_invariants (struct loop
*loop
)
1676 init_inv_motion_data ();
1678 find_invariants (loop
);
1679 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1680 LOOP_DATA (loop
)->has_call
);
1681 move_invariants (loop
);
1683 free_inv_motion_data ();
1686 /* Releases the auxiliary data for LOOP. */
1689 free_loop_data (struct loop
*loop
)
1691 struct loop_data
*data
= LOOP_DATA (loop
);
1695 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1696 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1703 /* Registers currently living. */
1704 static bitmap_head curr_regs_live
;
1706 /* Current reg pressure for each pressure class. */
1707 static int curr_reg_pressure
[N_REG_CLASSES
];
1709 /* Record all regs that are set in any one insn. Communication from
1710 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1711 all hard-registers. */
1712 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1713 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1714 /* Number of regs stored in the previous array. */
1715 static int n_regs_set
;
1717 /* Return pressure class and number of needed hard registers (through
1718 *NREGS) of register REGNO. */
1719 static enum reg_class
1720 get_regno_pressure_class (int regno
, int *nregs
)
1722 if (regno
>= FIRST_PSEUDO_REGISTER
)
1724 enum reg_class pressure_class
;
1726 pressure_class
= reg_allocno_class (regno
);
1727 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1729 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1730 return pressure_class
;
1732 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1733 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1736 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1745 /* Increase (if INCR_P) or decrease current register pressure for
1748 change_pressure (int regno
, bool incr_p
)
1751 enum reg_class pressure_class
;
1753 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1755 curr_reg_pressure
[pressure_class
] -= nregs
;
1758 curr_reg_pressure
[pressure_class
] += nregs
;
1759 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1760 < curr_reg_pressure
[pressure_class
])
1761 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1762 = curr_reg_pressure
[pressure_class
];
1766 /* Mark REGNO birth. */
1768 mark_regno_live (int regno
)
1772 for (loop
= curr_loop
;
1773 loop
!= current_loops
->tree_root
;
1774 loop
= loop_outer (loop
))
1775 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1776 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1778 change_pressure (regno
, true);
1781 /* Mark REGNO death. */
1783 mark_regno_death (int regno
)
1785 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1787 change_pressure (regno
, false);
1790 /* Mark setting register REG. */
1792 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1793 void *data ATTRIBUTE_UNUSED
)
1797 if (GET_CODE (reg
) == SUBREG
)
1798 reg
= SUBREG_REG (reg
);
1803 regs_set
[n_regs_set
++] = reg
;
1805 regno
= REGNO (reg
);
1807 if (regno
>= FIRST_PSEUDO_REGISTER
)
1808 mark_regno_live (regno
);
1811 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1813 while (regno
< last
)
1815 mark_regno_live (regno
);
1821 /* Mark clobbering register REG. */
1823 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1825 if (GET_CODE (setter
) == CLOBBER
)
1826 mark_reg_store (reg
, setter
, data
);
1829 /* Mark register REG death. */
1831 mark_reg_death (rtx reg
)
1833 int regno
= REGNO (reg
);
1835 if (regno
>= FIRST_PSEUDO_REGISTER
)
1836 mark_regno_death (regno
);
1839 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1841 while (regno
< last
)
1843 mark_regno_death (regno
);
1849 /* Mark occurrence of registers in X for the current loop. */
1851 mark_ref_regs (rtx x
)
1860 code
= GET_CODE (x
);
1865 for (loop
= curr_loop
;
1866 loop
!= current_loops
->tree_root
;
1867 loop
= loop_outer (loop
))
1868 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1872 fmt
= GET_RTX_FORMAT (code
);
1873 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1875 mark_ref_regs (XEXP (x
, i
));
1876 else if (fmt
[i
] == 'E')
1880 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1881 mark_ref_regs (XVECEXP (x
, i
, j
));
1885 /* Calculate register pressure in the loops. */
1887 calculate_loop_reg_pressure (void)
1895 struct loop
*loop
, *parent
;
1897 FOR_EACH_LOOP (loop
, 0)
1898 if (loop
->aux
== NULL
)
1900 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1901 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1902 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1904 ira_setup_eliminable_regset ();
1905 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1906 FOR_EACH_BB_FN (bb
, cfun
)
1908 curr_loop
= bb
->loop_father
;
1909 if (curr_loop
== current_loops
->tree_root
)
1912 for (loop
= curr_loop
;
1913 loop
!= current_loops
->tree_root
;
1914 loop
= loop_outer (loop
))
1915 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1917 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1918 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1919 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1920 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1921 change_pressure (j
, true);
1923 FOR_BB_INSNS (bb
, insn
)
1925 if (! NONDEBUG_INSN_P (insn
))
1928 mark_ref_regs (PATTERN (insn
));
1930 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1932 /* Mark any registers dead after INSN as dead now. */
1934 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1935 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1936 mark_reg_death (XEXP (link
, 0));
1938 /* Mark any registers set in INSN as live,
1939 and mark them as conflicting with all other live regs.
1940 Clobbers are processed again, so they conflict with
1941 the registers that are set. */
1943 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
1946 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1947 if (REG_NOTE_KIND (link
) == REG_INC
)
1948 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
1950 while (n_regs_set
-- > 0)
1952 rtx note
= find_regno_note (insn
, REG_UNUSED
,
1953 REGNO (regs_set
[n_regs_set
]));
1957 mark_reg_death (XEXP (note
, 0));
1961 bitmap_clear (&curr_regs_live
);
1962 if (flag_ira_region
== IRA_REGION_MIXED
1963 || flag_ira_region
== IRA_REGION_ALL
)
1964 FOR_EACH_LOOP (loop
, 0)
1966 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1967 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
1969 enum reg_class pressure_class
;
1972 pressure_class
= get_regno_pressure_class (j
, &nregs
);
1973 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
1976 if (dump_file
== NULL
)
1978 FOR_EACH_LOOP (loop
, 0)
1980 parent
= loop_outer (loop
);
1981 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1982 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
1983 loop
->header
->index
, loop_depth (loop
));
1984 fprintf (dump_file
, "\n ref. regnos:");
1985 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
1986 fprintf (dump_file
, " %d", j
);
1987 fprintf (dump_file
, "\n live regnos:");
1988 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1989 fprintf (dump_file
, " %d", j
);
1990 fprintf (dump_file
, "\n Pressure:");
1991 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1993 enum reg_class pressure_class
;
1995 pressure_class
= ira_pressure_classes
[i
];
1996 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
1998 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
1999 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
2001 fprintf (dump_file
, "\n");
2007 /* Move the invariants out of the loops. */
2010 move_loop_invariants (void)
2014 if (flag_ira_loop_pressure
)
2017 regstat_init_n_sets_and_refs ();
2018 ira_set_pseudo_classes (true, dump_file
);
2019 calculate_loop_reg_pressure ();
2020 regstat_free_n_sets_and_refs ();
2022 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
2023 /* Process the loops, innermost first. */
2024 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2027 /* move_single_loop_invariants for very large loops
2028 is time consuming and might need a lot of memory. */
2029 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2030 move_single_loop_invariants (loop
);
2033 FOR_EACH_LOOP (loop
, 0)
2035 free_loop_data (loop
);
2038 if (flag_ira_loop_pressure
)
2039 /* There is no sense to keep this info because it was most
2040 probably outdated by subsequent passes. */
2042 free (invariant_table
);
2043 invariant_table
= NULL
;
2044 invariant_table_size
= 0;
2046 #ifdef ENABLE_CHECKING
2047 verify_flow_info ();