1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2014 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"
45 #include "basic-block.h"
53 #include "hash-table.h"
60 /* The data stored for the loop. */
64 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
65 bool has_call
; /* True if the loop contains a call. */
66 /* Maximal register pressure inside loop for given register class
67 (defined only for the pressure classes). */
68 int max_reg_pressure
[N_REG_CLASSES
];
69 /* Loop regs referenced and live pseudo-registers. */
71 bitmap_head regs_live
;
74 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
76 /* The description of an use. */
80 rtx
*pos
; /* Position of the use. */
81 rtx insn
; /* The insn in that the use occurs. */
82 unsigned addr_use_p
; /* Whether the use occurs in an address. */
83 struct use
*next
; /* Next use in the list. */
86 /* The description of a def. */
90 struct use
*uses
; /* The list of uses that are uniquely reached
92 unsigned n_uses
; /* Number of such uses. */
93 unsigned n_addr_uses
; /* Number of uses in addresses. */
94 unsigned invno
; /* The corresponding invariant. */
97 /* The data stored for each invariant. */
101 /* The number of the invariant. */
104 /* The number of the invariant with the same value. */
107 /* If we moved the invariant out of the loop, the register that contains its
111 /* If we moved the invariant out of the loop, the original regno
112 that contained its value. */
115 /* The definition of the invariant. */
118 /* The insn in that it is defined. */
121 /* Whether it is always executed. */
122 bool always_executed
;
124 /* Whether to move the invariant. */
127 /* Whether the invariant is cheap when used as an address. */
130 /* Cost of the invariant. */
133 /* The invariants it depends on. */
136 /* Used for detecting already visited invariants during determining
137 costs of movements. */
141 /* Currently processed loop. */
142 static struct loop
*curr_loop
;
144 /* Table of invariants indexed by the df_ref uid field. */
146 static unsigned int invariant_table_size
= 0;
147 static struct invariant
** invariant_table
;
149 /* Entry for hash table of invariant expressions. */
151 struct invariant_expr_entry
154 struct invariant
*inv
;
160 enum machine_mode mode
;
166 /* The actual stamp for marking already visited invariants during determining
167 costs of movements. */
169 static unsigned actual_stamp
;
171 typedef struct invariant
*invariant_p
;
174 /* The invariants. */
176 static vec
<invariant_p
> invariants
;
178 /* Check the size of the invariant table and realloc if necessary. */
181 check_invariant_table_size (void)
183 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
185 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
186 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
187 memset (&invariant_table
[invariant_table_size
], 0,
188 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
189 invariant_table_size
= new_size
;
193 /* Test for possibility of invariantness of X. */
196 check_maybe_invariant (rtx x
)
198 enum rtx_code code
= GET_CODE (x
);
212 case UNSPEC_VOLATILE
:
220 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
221 It should not be hard, and might be faster than "elsewhere". */
223 /* Just handle the most trivial case where we load from an unchanging
224 location (most importantly, pic tables). */
225 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
231 /* Don't mess with insns declared volatile. */
232 if (MEM_VOLATILE_P (x
))
240 fmt
= GET_RTX_FORMAT (code
);
241 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
245 if (!check_maybe_invariant (XEXP (x
, i
)))
248 else if (fmt
[i
] == 'E')
250 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
251 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
259 /* Returns the invariant definition for USE, or NULL if USE is not
262 static struct invariant
*
263 invariant_for_use (df_ref use
)
265 struct df_link
*defs
;
267 basic_block bb
= DF_REF_BB (use
), def_bb
;
269 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
272 defs
= DF_REF_CHAIN (use
);
273 if (!defs
|| defs
->next
)
276 check_invariant_table_size ();
277 if (!invariant_table
[DF_REF_ID (def
)])
280 def_bb
= DF_REF_BB (def
);
281 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
283 return invariant_table
[DF_REF_ID (def
)];
286 /* Computes hash value for invariant expression X in INSN. */
289 hash_invariant_expr_1 (rtx insn
, rtx x
)
291 enum rtx_code code
= GET_CODE (x
);
294 hashval_t val
= code
;
297 struct invariant
*inv
;
305 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
308 use
= df_find_use (insn
, x
);
310 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
311 inv
= invariant_for_use (use
);
313 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
315 gcc_assert (inv
->eqto
!= ~0u);
322 fmt
= GET_RTX_FORMAT (code
);
323 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
326 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
327 else if (fmt
[i
] == 'E')
329 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
330 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
332 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
339 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
340 and INSN2 have always the same value. */
343 invariant_expr_equal_p (rtx insn1
, rtx e1
, rtx insn2
, rtx e2
)
345 enum rtx_code code
= GET_CODE (e1
);
349 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
352 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
353 the other one. If both are VOIDmode, we rely on the caller of this
354 function to verify that their modes are the same. */
355 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
364 return rtx_equal_p (e1
, e2
);
367 use1
= df_find_use (insn1
, e1
);
368 use2
= df_find_use (insn2
, e2
);
370 inv1
= invariant_for_use (use1
);
372 inv2
= invariant_for_use (use2
);
375 return rtx_equal_p (e1
, e2
);
380 gcc_assert (inv1
->eqto
!= ~0u);
381 gcc_assert (inv2
->eqto
!= ~0u);
382 return inv1
->eqto
== inv2
->eqto
;
388 fmt
= GET_RTX_FORMAT (code
);
389 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
396 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
400 else if (fmt
[i
] == 'E')
402 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
405 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
407 sub1
= XVECEXP (e1
, i
, j
);
408 sub2
= XVECEXP (e2
, i
, j
);
410 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
414 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
416 if (XINT (e1
, i
) != XINT (e2
, i
))
419 /* Unhandled type of subexpression, we fail conservatively. */
427 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
429 typedef invariant_expr_entry value_type
;
430 typedef invariant_expr_entry compare_type
;
431 static inline hashval_t
hash (const value_type
*);
432 static inline bool equal (const value_type
*, const compare_type
*);
435 /* Returns hash value for invariant expression entry ENTRY. */
438 invariant_expr_hasher::hash (const value_type
*entry
)
443 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
446 invariant_expr_hasher::equal (const value_type
*entry1
,
447 const compare_type
*entry2
)
449 if (entry1
->mode
!= entry2
->mode
)
452 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
453 entry2
->inv
->insn
, entry2
->expr
);
456 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
458 /* Checks whether invariant with value EXPR in machine mode MODE is
459 recorded in EQ. If this is the case, return the invariant. Otherwise
460 insert INV to the table for this expression and return INV. */
462 static struct invariant
*
463 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, enum machine_mode mode
,
464 struct invariant
*inv
)
466 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
467 struct invariant_expr_entry
*entry
;
468 struct invariant_expr_entry pentry
;
469 invariant_expr_entry
**slot
;
474 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
480 entry
= XNEW (struct invariant_expr_entry
);
490 /* Finds invariants identical to INV and records the equivalence. EQ is the
491 hash table of the invariants. */
494 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
498 struct invariant
*dep
;
500 enum machine_mode mode
;
502 if (inv
->eqto
!= ~0u)
505 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
507 dep
= invariants
[depno
];
508 find_identical_invariants (eq
, dep
);
511 set
= single_set (inv
->insn
);
512 expr
= SET_SRC (set
);
513 mode
= GET_MODE (expr
);
514 if (mode
== VOIDmode
)
515 mode
= GET_MODE (SET_DEST (set
));
516 inv
->eqto
= find_or_insert_inv (eq
, expr
, mode
, inv
)->invno
;
518 if (dump_file
&& inv
->eqto
!= inv
->invno
)
520 "Invariant %d is equivalent to invariant %d.\n",
521 inv
->invno
, inv
->eqto
);
524 /* Find invariants with the same value and record the equivalences. */
527 merge_identical_invariants (void)
530 struct invariant
*inv
;
531 invariant_htab_type
eq (invariants
.length ());
533 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
534 find_identical_invariants (&eq
, inv
);
537 /* Determines the basic blocks inside LOOP that are always executed and
538 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
539 basic blocks that may either exit the loop, or contain the call that
540 does not have to return. BODY is body of the loop obtained by
541 get_loop_body_in_dom_order. */
544 compute_always_reached (struct loop
*loop
, basic_block
*body
,
545 bitmap may_exit
, bitmap always_reached
)
549 for (i
= 0; i
< loop
->num_nodes
; i
++)
551 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
552 bitmap_set_bit (always_reached
, i
);
554 if (bitmap_bit_p (may_exit
, i
))
559 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
560 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
561 additionally mark blocks that may exit due to a call. */
564 find_exits (struct loop
*loop
, basic_block
*body
,
565 bitmap may_exit
, bitmap has_exit
)
570 struct loop
*outermost_exit
= loop
, *aexit
;
571 bool has_call
= false;
574 for (i
= 0; i
< loop
->num_nodes
; i
++)
576 if (body
[i
]->loop_father
== loop
)
578 FOR_BB_INSNS (body
[i
], insn
)
581 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
582 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
585 bitmap_set_bit (may_exit
, i
);
590 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
592 if (flow_bb_inside_loop_p (loop
, e
->dest
))
595 bitmap_set_bit (may_exit
, i
);
596 bitmap_set_bit (has_exit
, i
);
597 outermost_exit
= find_common_loop (outermost_exit
,
598 e
->dest
->loop_father
);
603 /* Use the data stored for the subloop to decide whether we may exit
604 through it. It is sufficient to do this for header of the loop,
605 as other basic blocks inside it must be dominated by it. */
606 if (body
[i
]->loop_father
->header
!= body
[i
])
609 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
612 bitmap_set_bit (may_exit
, i
);
614 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
617 bitmap_set_bit (may_exit
, i
);
618 bitmap_set_bit (has_exit
, i
);
620 if (flow_loop_nested_p (aexit
, outermost_exit
))
621 outermost_exit
= aexit
;
625 if (loop
->aux
== NULL
)
627 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
628 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
629 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
631 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
632 LOOP_DATA (loop
)->has_call
= has_call
;
635 /* Check whether we may assign a value to X from a register. */
638 may_assign_reg_p (rtx x
)
640 return (GET_MODE (x
) != VOIDmode
641 && GET_MODE (x
) != BLKmode
642 && can_copy_p (GET_MODE (x
))
644 || !HARD_REGISTER_P (x
)
645 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
648 /* Finds definitions that may correspond to invariants in LOOP with body
652 find_defs (struct loop
*loop
)
657 "*****starting processing of loop %d ******\n",
661 df_remove_problem (df_chain
);
662 df_process_deferred_rescans ();
663 df_chain_add_problem (DF_UD_CHAIN
);
664 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
665 df_analyze_loop (loop
);
666 check_invariant_table_size ();
670 df_dump_region (dump_file
);
672 "*****ending processing of loop %d ******\n",
677 /* Creates a new invariant for definition DEF in INSN, depending on invariants
678 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
679 unless the program ends due to a function call. The newly created invariant
682 static struct invariant
*
683 create_new_invariant (struct def
*def
, rtx insn
, bitmap depends_on
,
684 bool always_executed
)
686 struct invariant
*inv
= XNEW (struct invariant
);
687 rtx set
= single_set (insn
);
688 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
691 inv
->always_executed
= always_executed
;
692 inv
->depends_on
= depends_on
;
694 /* If the set is simple, usually by moving it we move the whole store out of
695 the loop. Otherwise we save only cost of the computation. */
698 inv
->cost
= set_rtx_cost (set
, speed
);
699 /* ??? Try to determine cheapness of address computation. Unfortunately
700 the address cost is only a relative measure, we can't really compare
701 it with any absolute number, but only with other address costs.
702 But here we don't have any other addresses, so compare with a magic
703 number anyway. It has to be large enough to not regress PR33928
704 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
705 enough to not regress 410.bwaves either (by still moving reg+reg
707 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
708 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
709 ADDR_SPACE_GENERIC
, speed
) < 3;
713 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
714 inv
->cheap_address
= false;
719 inv
->orig_regno
= -1;
723 inv
->invno
= invariants
.length ();
726 def
->invno
= inv
->invno
;
727 invariants
.safe_push (inv
);
732 "Set in insn %d is invariant (%d), cost %d, depends on ",
733 INSN_UID (insn
), inv
->invno
, inv
->cost
);
734 dump_bitmap (dump_file
, inv
->depends_on
);
740 /* Record USE at DEF. */
743 record_use (struct def
*def
, df_ref use
)
745 struct use
*u
= XNEW (struct use
);
747 u
->pos
= DF_REF_REAL_LOC (use
);
748 u
->insn
= DF_REF_INSN (use
);
749 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
750 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
758 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
759 bitmap. Returns true if all dependencies of USE are known to be
760 loop invariants, false otherwise. */
763 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
767 struct df_link
*defs
;
768 struct def
*def_data
;
769 struct invariant
*inv
;
771 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
774 defs
= DF_REF_CHAIN (use
);
777 unsigned int regno
= DF_REF_REGNO (use
);
779 /* If this is the use of an uninitialized argument register that is
780 likely to be spilled, do not move it lest this might extend its
781 lifetime and cause reload to die. This can occur for a call to
782 a function taking complex number arguments and moving the insns
783 preparing the arguments without moving the call itself wouldn't
784 gain much in practice. */
785 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
786 && FUNCTION_ARG_REGNO_P (regno
)
787 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
797 check_invariant_table_size ();
798 inv
= invariant_table
[DF_REF_ID (def
)];
803 gcc_assert (def_data
!= NULL
);
805 def_bb
= DF_REF_BB (def
);
806 /* Note that in case bb == def_bb, we know that the definition
807 dominates insn, because def has invariant_table[DF_REF_ID(def)]
808 defined and we process the insns in the basic block bb
810 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
813 bitmap_set_bit (depends_on
, def_data
->invno
);
818 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
819 bitmap. Returns true if all dependencies of INSN are known to be
820 loop invariants, false otherwise. */
823 check_dependencies (rtx insn
, bitmap depends_on
)
825 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
827 basic_block bb
= BLOCK_FOR_INSN (insn
);
829 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
830 if (!check_dependency (bb
, use
, depends_on
))
832 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
833 if (!check_dependency (bb
, use
, depends_on
))
839 /* Pre-check candidate DEST to skip the one which can not make a valid insn
840 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
842 pre_check_invariant_p (bool simple
, rtx dest
)
844 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
848 unsigned int i
= REGNO (dest
);
849 struct df_insn_info
*insn_info
;
852 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
854 ref
= DF_REF_INSN (use
);
855 insn_info
= DF_INSN_INFO_GET (ref
);
857 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
858 if (DF_REF_REGNO (def_rec
) == i
)
860 /* Multi definitions at this stage, most likely are due to
861 instruction constraints, which requires both read and write
862 on the same register. Since move_invariant_reg is not
863 powerful enough to handle such cases, just ignore the INV
864 and leave the chance to others. */
872 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
873 executed. ALWAYS_EXECUTED is true if the insn is always executed,
874 unless the program ends due to a function call. */
877 find_invariant_insn (rtx insn
, bool always_reached
, bool always_executed
)
884 struct invariant
*inv
;
887 /* We can't move a CC0 setter without the user. */
888 if (sets_cc0_p (insn
))
892 set
= single_set (insn
);
895 dest
= SET_DEST (set
);
898 || HARD_REGISTER_P (dest
))
901 if (!may_assign_reg_p (dest
)
902 || !pre_check_invariant_p (simple
, dest
)
903 || !check_maybe_invariant (SET_SRC (set
)))
906 /* If the insn can throw exception, we cannot move it at all without changing
908 if (can_throw_internal (insn
))
911 /* We cannot make trapping insn executed, unless it was executed before. */
912 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
915 depends_on
= BITMAP_ALLOC (NULL
);
916 if (!check_dependencies (insn
, depends_on
))
918 BITMAP_FREE (depends_on
);
923 def
= XCNEW (struct def
);
927 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
931 ref
= df_find_def (insn
, dest
);
932 check_invariant_table_size ();
933 invariant_table
[DF_REF_ID (ref
)] = inv
;
937 /* Record registers used in INSN that have a unique invariant definition. */
940 record_uses (rtx insn
)
942 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
944 struct invariant
*inv
;
946 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
948 inv
= invariant_for_use (use
);
950 record_use (inv
->def
, use
);
952 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
954 inv
= invariant_for_use (use
);
956 record_use (inv
->def
, use
);
960 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
961 executed. ALWAYS_EXECUTED is true if the insn is always executed,
962 unless the program ends due to a function call. */
965 find_invariants_insn (rtx insn
, bool always_reached
, bool always_executed
)
967 find_invariant_insn (insn
, always_reached
, always_executed
);
971 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
972 basic block is always executed. ALWAYS_EXECUTED is true if the basic
973 block is always executed, unless the program ends due to a function
977 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
981 FOR_BB_INSNS (bb
, insn
)
983 if (!NONDEBUG_INSN_P (insn
))
986 find_invariants_insn (insn
, always_reached
, always_executed
);
990 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
991 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
992 always_reached
= false;
996 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
997 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
998 bitmap of basic blocks in BODY that are always executed unless the program
999 ends due to a function call. */
1002 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1003 bitmap always_reached
, bitmap always_executed
)
1007 for (i
= 0; i
< loop
->num_nodes
; i
++)
1008 find_invariants_bb (body
[i
],
1009 bitmap_bit_p (always_reached
, i
),
1010 bitmap_bit_p (always_executed
, i
));
1013 /* Finds invariants in LOOP. */
1016 find_invariants (struct loop
*loop
)
1018 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1019 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1020 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1021 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1022 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1024 find_exits (loop
, body
, may_exit
, has_exit
);
1025 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1026 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1029 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1030 merge_identical_invariants ();
1032 BITMAP_FREE (always_reached
);
1033 BITMAP_FREE (always_executed
);
1034 BITMAP_FREE (may_exit
);
1035 BITMAP_FREE (has_exit
);
1039 /* Frees a list of uses USE. */
1042 free_use_list (struct use
*use
)
1046 for (; use
; use
= next
)
1053 /* Return pressure class and number of hard registers (through *NREGS)
1054 for destination of INSN. */
1055 static enum reg_class
1056 get_pressure_class_and_nregs (rtx insn
, int *nregs
)
1059 enum reg_class pressure_class
;
1060 rtx set
= single_set (insn
);
1062 /* Considered invariant insns have only one set. */
1063 gcc_assert (set
!= NULL_RTX
);
1064 reg
= SET_DEST (set
);
1065 if (GET_CODE (reg
) == SUBREG
)
1066 reg
= SUBREG_REG (reg
);
1070 pressure_class
= NO_REGS
;
1076 if (reg
== NULL_RTX
)
1077 pressure_class
= GENERAL_REGS
;
1080 pressure_class
= reg_allocno_class (REGNO (reg
));
1081 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1084 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1086 return pressure_class
;
1089 /* Calculates cost and number of registers needed for moving invariant INV
1090 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1091 the REG_CLASS of INV. Return
1092 -1: if INV is invalid.
1093 0: if INV and its depends_on have same reg_class
1094 1: if INV and its depends_on have different reg_classes. */
1097 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1101 unsigned aregs_needed
[N_REG_CLASSES
];
1103 struct invariant
*dep
;
1107 /* Find the representative of the class of the equivalent invariants. */
1108 inv
= invariants
[inv
->eqto
];
1111 if (! flag_ira_loop_pressure
)
1115 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1116 regs_needed
[ira_pressure_classes
[i
]] = 0;
1120 || inv
->stamp
== actual_stamp
)
1122 inv
->stamp
= actual_stamp
;
1124 if (! flag_ira_loop_pressure
)
1129 enum reg_class pressure_class
;
1131 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1132 regs_needed
[pressure_class
] += nregs
;
1133 *cl
= pressure_class
;
1137 if (!inv
->cheap_address
1138 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1139 (*comp_cost
) += inv
->cost
;
1143 /* Hoisting constant pool constants into stack regs may cost more than
1144 just single register. On x87, the balance is affected both by the
1145 small number of FP registers, and by its register stack organization,
1146 that forces us to add compensation code in and around the loop to
1147 shuffle the operands to the top of stack before use, and pop them
1148 from the stack after the loop finishes.
1150 To model this effect, we increase the number of registers needed for
1151 stack registers by two: one register push, and one register pop.
1152 This usually has the effect that FP constant loads from the constant
1153 pool are not moved out of the loop.
1155 Note that this also means that dependent invariants can not be moved.
1156 However, the primary purpose of this pass is to move loop invariant
1157 address arithmetic out of loops, and address arithmetic that depends
1158 on floating point constants is unlikely to ever occur. */
1159 rtx set
= single_set (inv
->insn
);
1161 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1162 && constant_pool_constant_p (SET_SRC (set
)))
1164 if (flag_ira_loop_pressure
)
1165 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1167 regs_needed
[0] += 2;
1172 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1175 enum reg_class dep_cl
= ALL_REGS
;
1178 dep
= invariants
[depno
];
1180 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1184 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1186 if (! flag_ira_loop_pressure
)
1187 check_p
= aregs_needed
[0] != 0;
1190 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1191 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1193 check_p
= i
< ira_pressure_classes_num
;
1195 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1202 /* We need to check always_executed, since if the original value of
1203 the invariant may be preserved, we may need to keep it in a
1204 separate register. TODO check whether the register has an
1205 use outside of the loop. */
1206 && dep
->always_executed
1207 && !dep
->def
->uses
->next
)
1209 /* If this is a single use, after moving the dependency we will not
1210 need a new register. */
1211 if (! flag_ira_loop_pressure
)
1216 enum reg_class pressure_class
;
1218 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1219 aregs_needed
[pressure_class
] -= nregs
;
1223 if (! flag_ira_loop_pressure
)
1224 regs_needed
[0] += aregs_needed
[0];
1227 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1228 regs_needed
[ira_pressure_classes
[i
]]
1229 += aregs_needed
[ira_pressure_classes
[i
]];
1231 (*comp_cost
) += acomp_cost
;
1236 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1237 of registers used in the loop, NEW_REGS is the number of new variables
1238 already added due to the invariant motion. The number of registers needed
1239 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1240 through to estimate_reg_pressure_cost. */
1243 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1244 unsigned *new_regs
, unsigned regs_used
,
1245 bool speed
, bool call_p
)
1247 int comp_cost
, size_cost
;
1253 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1255 if (! flag_ira_loop_pressure
)
1257 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1258 regs_used
, speed
, call_p
)
1259 - estimate_reg_pressure_cost (new_regs
[0],
1260 regs_used
, speed
, call_p
));
1264 else if ((ret
== 0) && (cl
== NO_REGS
))
1265 /* Hoist it anyway since it does not impact register pressure. */
1270 enum reg_class pressure_class
;
1272 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1274 pressure_class
= ira_pressure_classes
[i
];
1276 if (!reg_classes_intersect_p (pressure_class
, cl
))
1279 if ((int) new_regs
[pressure_class
]
1280 + (int) regs_needed
[pressure_class
]
1281 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1282 + IRA_LOOP_RESERVED_REGS
1283 > ira_class_hard_regs_num
[pressure_class
])
1286 if (i
< ira_pressure_classes_num
)
1287 /* There will be register pressure excess and we want not to
1288 make this loop invariant motion. All loop invariants with
1289 non-positive gains will be rejected in function
1290 find_invariants_to_move. Therefore we return the negative
1293 One could think that this rejects also expensive loop
1294 invariant motions and this will hurt code performance.
1295 However numerous experiments with different heuristics
1296 taking invariant cost into account did not confirm this
1297 assumption. There are possible explanations for this
1299 o probably all expensive invariants were already moved out
1300 of the loop by PRE and gimple invariant motion pass.
1301 o expensive invariant execution will be hidden by insn
1302 scheduling or OOO processor hardware because usually such
1303 invariants have a lot of freedom to be executed
1305 Another reason for ignoring invariant cost vs spilling cost
1306 heuristics is also in difficulties to evaluate accurately
1307 spill cost at this stage. */
1313 return comp_cost
- size_cost
;
1316 /* Finds invariant with best gain for moving. Returns the gain, stores
1317 the invariant in *BEST and number of registers needed for it to
1318 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1319 NEW_REGS is the number of new variables already added due to invariant
1323 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1324 unsigned *new_regs
, unsigned regs_used
,
1325 bool speed
, bool call_p
)
1327 struct invariant
*inv
;
1328 int i
, gain
= 0, again
;
1329 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1331 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1336 /* Only consider the "representatives" of equivalent invariants. */
1337 if (inv
->eqto
!= inv
->invno
)
1340 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1346 if (! flag_ira_loop_pressure
)
1347 regs_needed
[0] = aregs_needed
[0];
1350 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1351 regs_needed
[ira_pressure_classes
[i
]]
1352 = aregs_needed
[ira_pressure_classes
[i
]];
1360 /* Marks invariant INVNO and all its dependencies for moving. */
1363 set_move_mark (unsigned invno
, int gain
)
1365 struct invariant
*inv
= invariants
[invno
];
1368 /* Find the representative of the class of the equivalent invariants. */
1369 inv
= invariants
[inv
->eqto
];
1378 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1381 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1385 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1387 set_move_mark (invno
, -1);
1391 /* Determines which invariants to move. */
1394 find_invariants_to_move (bool speed
, bool call_p
)
1397 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1398 struct invariant
*inv
= NULL
;
1400 if (!invariants
.length ())
1403 if (flag_ira_loop_pressure
)
1404 /* REGS_USED is actually never used when the flag is on. */
1407 /* We do not really do a good job in estimating number of
1408 registers used; we put some initial bound here to stand for
1409 induction variables etc. that we do not detect. */
1411 unsigned int n_regs
= DF_REG_SIZE (df
);
1415 for (i
= 0; i
< n_regs
; i
++)
1417 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1419 /* This is a value that is used but not changed inside loop. */
1425 if (! flag_ira_loop_pressure
)
1426 new_regs
[0] = regs_needed
[0] = 0;
1429 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1430 new_regs
[ira_pressure_classes
[i
]] = 0;
1432 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1433 new_regs
, regs_used
,
1434 speed
, call_p
)) > 0)
1436 set_move_mark (inv
->invno
, gain
);
1437 if (! flag_ira_loop_pressure
)
1438 new_regs
[0] += regs_needed
[0];
1441 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1442 new_regs
[ira_pressure_classes
[i
]]
1443 += regs_needed
[ira_pressure_classes
[i
]];
1448 /* Replace the uses, reached by the definition of invariant INV, by REG.
1450 IN_GROUP is nonzero if this is part of a group of changes that must be
1451 performed as a group. In that case, the changes will be stored. The
1452 function `apply_change_group' will validate and apply the changes. */
1455 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1457 /* Replace the uses we know to be dominated. It saves work for copy
1458 propagation, and also it is necessary so that dependent invariants
1459 are computed right. */
1463 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1464 validate_change (use
->insn
, use
->pos
, reg
, true);
1466 /* If we aren't part of a larger group, apply the changes now. */
1468 return apply_change_group ();
1474 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1478 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1480 struct invariant
*inv
= invariants
[invno
];
1481 struct invariant
*repr
= invariants
[inv
->eqto
];
1483 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1484 rtx reg
, set
, dest
, note
;
1493 /* If this is a representative of the class of equivalent invariants,
1494 really move the invariant. Otherwise just replace its use with
1495 the register used for the representative. */
1498 if (inv
->depends_on
)
1500 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1502 if (!move_invariant_reg (loop
, i
))
1507 /* Move the set out of the loop. If the set is always executed (we could
1508 omit this condition if we know that the register is unused outside of
1509 the loop, but it does not seem worth finding out) and it has no uses
1510 that would not be dominated by it, we may just move it (TODO).
1511 Otherwise we need to create a temporary register. */
1512 set
= single_set (inv
->insn
);
1513 reg
= dest
= SET_DEST (set
);
1514 if (GET_CODE (reg
) == SUBREG
)
1515 reg
= SUBREG_REG (reg
);
1517 regno
= REGNO (reg
);
1519 reg
= gen_reg_rtx_and_attrs (dest
);
1521 /* Try replacing the destination by a new pseudoregister. */
1522 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1524 /* As well as all the dominated uses. */
1525 replace_uses (inv
, reg
, true);
1527 /* And validate all the changes. */
1528 if (!apply_change_group ())
1531 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1532 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1534 /* If there is a REG_EQUAL note on the insn we just moved, and the
1535 insn is in a basic block that is not always executed or the note
1536 contains something for which we don't know the invariant status,
1537 the note may no longer be valid after we move the insn. Note that
1538 uses in REG_EQUAL notes are taken into account in the computation
1539 of invariants, so it is safe to retain the note even if it contains
1540 register references for which we know the invariant status. */
1541 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1542 && (!inv
->always_executed
1543 || !check_maybe_invariant (XEXP (note
, 0))))
1544 remove_note (inv
->insn
, note
);
1548 if (!move_invariant_reg (loop
, repr
->invno
))
1551 regno
= repr
->orig_regno
;
1552 if (!replace_uses (inv
, reg
, false))
1554 set
= single_set (inv
->insn
);
1555 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1556 delete_insn (inv
->insn
);
1560 inv
->orig_regno
= regno
;
1565 /* If we failed, clear move flag, so that we do not try to move inv
1568 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1570 inv
->reg
= NULL_RTX
;
1571 inv
->orig_regno
= -1;
1576 /* Move selected invariant out of the LOOP. Newly created regs are marked
1577 in TEMPORARY_REGS. */
1580 move_invariants (struct loop
*loop
)
1582 struct invariant
*inv
;
1585 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1586 move_invariant_reg (loop
, i
);
1587 if (flag_ira_loop_pressure
&& resize_reg_info ())
1589 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1590 if (inv
->reg
!= NULL_RTX
)
1592 if (inv
->orig_regno
>= 0)
1593 setup_reg_classes (REGNO (inv
->reg
),
1594 reg_preferred_class (inv
->orig_regno
),
1595 reg_alternate_class (inv
->orig_regno
),
1596 reg_allocno_class (inv
->orig_regno
));
1598 setup_reg_classes (REGNO (inv
->reg
),
1599 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1604 /* Initializes invariant motion data. */
1607 init_inv_motion_data (void)
1611 invariants
.create (100);
1614 /* Frees the data allocated by invariant motion. */
1617 free_inv_motion_data (void)
1621 struct invariant
*inv
;
1623 check_invariant_table_size ();
1624 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1626 inv
= invariant_table
[i
];
1630 gcc_assert (def
!= NULL
);
1632 free_use_list (def
->uses
);
1634 invariant_table
[i
] = NULL
;
1638 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1640 BITMAP_FREE (inv
->depends_on
);
1643 invariants
.release ();
1646 /* Move the invariants out of the LOOP. */
1649 move_single_loop_invariants (struct loop
*loop
)
1651 init_inv_motion_data ();
1653 find_invariants (loop
);
1654 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1655 LOOP_DATA (loop
)->has_call
);
1656 move_invariants (loop
);
1658 free_inv_motion_data ();
1661 /* Releases the auxiliary data for LOOP. */
1664 free_loop_data (struct loop
*loop
)
1666 struct loop_data
*data
= LOOP_DATA (loop
);
1670 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1671 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1678 /* Registers currently living. */
1679 static bitmap_head curr_regs_live
;
1681 /* Current reg pressure for each pressure class. */
1682 static int curr_reg_pressure
[N_REG_CLASSES
];
1684 /* Record all regs that are set in any one insn. Communication from
1685 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1686 all hard-registers. */
1687 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1688 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1689 /* Number of regs stored in the previous array. */
1690 static int n_regs_set
;
1692 /* Return pressure class and number of needed hard registers (through
1693 *NREGS) of register REGNO. */
1694 static enum reg_class
1695 get_regno_pressure_class (int regno
, int *nregs
)
1697 if (regno
>= FIRST_PSEUDO_REGISTER
)
1699 enum reg_class pressure_class
;
1701 pressure_class
= reg_allocno_class (regno
);
1702 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1704 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1705 return pressure_class
;
1707 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1708 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1711 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1720 /* Increase (if INCR_P) or decrease current register pressure for
1723 change_pressure (int regno
, bool incr_p
)
1726 enum reg_class pressure_class
;
1728 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1730 curr_reg_pressure
[pressure_class
] -= nregs
;
1733 curr_reg_pressure
[pressure_class
] += nregs
;
1734 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1735 < curr_reg_pressure
[pressure_class
])
1736 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1737 = curr_reg_pressure
[pressure_class
];
1741 /* Mark REGNO birth. */
1743 mark_regno_live (int regno
)
1747 for (loop
= curr_loop
;
1748 loop
!= current_loops
->tree_root
;
1749 loop
= loop_outer (loop
))
1750 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1751 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1753 change_pressure (regno
, true);
1756 /* Mark REGNO death. */
1758 mark_regno_death (int regno
)
1760 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1762 change_pressure (regno
, false);
1765 /* Mark setting register REG. */
1767 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1768 void *data ATTRIBUTE_UNUSED
)
1772 if (GET_CODE (reg
) == SUBREG
)
1773 reg
= SUBREG_REG (reg
);
1778 regs_set
[n_regs_set
++] = reg
;
1780 regno
= REGNO (reg
);
1782 if (regno
>= FIRST_PSEUDO_REGISTER
)
1783 mark_regno_live (regno
);
1786 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1788 while (regno
< last
)
1790 mark_regno_live (regno
);
1796 /* Mark clobbering register REG. */
1798 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1800 if (GET_CODE (setter
) == CLOBBER
)
1801 mark_reg_store (reg
, setter
, data
);
1804 /* Mark register REG death. */
1806 mark_reg_death (rtx reg
)
1808 int regno
= REGNO (reg
);
1810 if (regno
>= FIRST_PSEUDO_REGISTER
)
1811 mark_regno_death (regno
);
1814 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1816 while (regno
< last
)
1818 mark_regno_death (regno
);
1824 /* Mark occurrence of registers in X for the current loop. */
1826 mark_ref_regs (rtx x
)
1835 code
= GET_CODE (x
);
1840 for (loop
= curr_loop
;
1841 loop
!= current_loops
->tree_root
;
1842 loop
= loop_outer (loop
))
1843 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1847 fmt
= GET_RTX_FORMAT (code
);
1848 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1850 mark_ref_regs (XEXP (x
, i
));
1851 else if (fmt
[i
] == 'E')
1855 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1856 mark_ref_regs (XVECEXP (x
, i
, j
));
1860 /* Calculate register pressure in the loops. */
1862 calculate_loop_reg_pressure (void)
1869 struct loop
*loop
, *parent
;
1871 FOR_EACH_LOOP (loop
, 0)
1872 if (loop
->aux
== NULL
)
1874 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1875 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1876 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1878 ira_setup_eliminable_regset ();
1879 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1880 FOR_EACH_BB_FN (bb
, cfun
)
1882 curr_loop
= bb
->loop_father
;
1883 if (curr_loop
== current_loops
->tree_root
)
1886 for (loop
= curr_loop
;
1887 loop
!= current_loops
->tree_root
;
1888 loop
= loop_outer (loop
))
1889 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1891 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1892 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1893 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1894 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1895 change_pressure (j
, true);
1897 FOR_BB_INSNS (bb
, insn
)
1899 if (! NONDEBUG_INSN_P (insn
))
1902 mark_ref_regs (PATTERN (insn
));
1904 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1906 /* Mark any registers dead after INSN as dead now. */
1908 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1909 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1910 mark_reg_death (XEXP (link
, 0));
1912 /* Mark any registers set in INSN as live,
1913 and mark them as conflicting with all other live regs.
1914 Clobbers are processed again, so they conflict with
1915 the registers that are set. */
1917 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
1920 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1921 if (REG_NOTE_KIND (link
) == REG_INC
)
1922 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
1924 while (n_regs_set
-- > 0)
1926 rtx note
= find_regno_note (insn
, REG_UNUSED
,
1927 REGNO (regs_set
[n_regs_set
]));
1931 mark_reg_death (XEXP (note
, 0));
1935 bitmap_clear (&curr_regs_live
);
1936 if (flag_ira_region
== IRA_REGION_MIXED
1937 || flag_ira_region
== IRA_REGION_ALL
)
1938 FOR_EACH_LOOP (loop
, 0)
1940 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1941 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
1943 enum reg_class pressure_class
;
1946 pressure_class
= get_regno_pressure_class (j
, &nregs
);
1947 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
1950 if (dump_file
== NULL
)
1952 FOR_EACH_LOOP (loop
, 0)
1954 parent
= loop_outer (loop
);
1955 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1956 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
1957 loop
->header
->index
, loop_depth (loop
));
1958 fprintf (dump_file
, "\n ref. regnos:");
1959 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
1960 fprintf (dump_file
, " %d", j
);
1961 fprintf (dump_file
, "\n live regnos:");
1962 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1963 fprintf (dump_file
, " %d", j
);
1964 fprintf (dump_file
, "\n Pressure:");
1965 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1967 enum reg_class pressure_class
;
1969 pressure_class
= ira_pressure_classes
[i
];
1970 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
1972 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
1973 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
1975 fprintf (dump_file
, "\n");
1981 /* Move the invariants out of the loops. */
1984 move_loop_invariants (void)
1988 if (flag_ira_loop_pressure
)
1991 regstat_init_n_sets_and_refs ();
1992 ira_set_pseudo_classes (true, dump_file
);
1993 calculate_loop_reg_pressure ();
1994 regstat_free_n_sets_and_refs ();
1996 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
1997 /* Process the loops, innermost first. */
1998 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2001 /* move_single_loop_invariants for very large loops
2002 is time consuming and might need a lot of memory. */
2003 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2004 move_single_loop_invariants (loop
);
2007 FOR_EACH_LOOP (loop
, 0)
2009 free_loop_data (loop
);
2012 if (flag_ira_loop_pressure
)
2013 /* There is no sense to keep this info because it was most
2014 probably outdated by subsequent passes. */
2016 free (invariant_table
);
2017 invariant_table
= NULL
;
2018 invariant_table_size
= 0;
2020 #ifdef ENABLE_CHECKING
2021 verify_flow_info ();