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"
47 #include "dominance.h"
50 #include "basic-block.h"
56 #include "insn-config.h"
74 /* The data stored for the loop. */
78 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
79 bool has_call
; /* True if the loop contains a call. */
80 /* Maximal register pressure inside loop for given register class
81 (defined only for the pressure classes). */
82 int max_reg_pressure
[N_REG_CLASSES
];
83 /* Loop regs referenced and live pseudo-registers. */
85 bitmap_head regs_live
;
88 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
90 /* The description of an use. */
94 rtx
*pos
; /* Position of the use. */
95 rtx_insn
*insn
; /* The insn in that the use occurs. */
96 unsigned addr_use_p
; /* Whether the use occurs in an address. */
97 struct use
*next
; /* Next use in the list. */
100 /* The description of a def. */
104 struct use
*uses
; /* The list of uses that are uniquely reached
106 unsigned n_uses
; /* Number of such uses. */
107 unsigned n_addr_uses
; /* Number of uses in addresses. */
108 unsigned invno
; /* The corresponding invariant. */
111 /* The data stored for each invariant. */
115 /* The number of the invariant. */
118 /* The number of the invariant with the same value. */
121 /* The number of invariants which eqto this. */
124 /* If we moved the invariant out of the loop, the register that contains its
128 /* If we moved the invariant out of the loop, the original regno
129 that contained its value. */
132 /* The definition of the invariant. */
135 /* The insn in that it is defined. */
138 /* Whether it is always executed. */
139 bool always_executed
;
141 /* Whether to move the invariant. */
144 /* Whether the invariant is cheap when used as an address. */
147 /* Cost of the invariant. */
150 /* The invariants it depends on. */
153 /* Used for detecting already visited invariants during determining
154 costs of movements. */
158 /* Currently processed loop. */
159 static struct loop
*curr_loop
;
161 /* Table of invariants indexed by the df_ref uid field. */
163 static unsigned int invariant_table_size
= 0;
164 static struct invariant
** invariant_table
;
166 /* Entry for hash table of invariant expressions. */
168 struct invariant_expr_entry
171 struct invariant
*inv
;
183 /* The actual stamp for marking already visited invariants during determining
184 costs of movements. */
186 static unsigned actual_stamp
;
188 typedef struct invariant
*invariant_p
;
191 /* The invariants. */
193 static vec
<invariant_p
> invariants
;
195 /* Check the size of the invariant table and realloc if necessary. */
198 check_invariant_table_size (void)
200 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
202 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
203 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
204 memset (&invariant_table
[invariant_table_size
], 0,
205 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
206 invariant_table_size
= new_size
;
210 /* Test for possibility of invariantness of X. */
213 check_maybe_invariant (rtx x
)
215 enum rtx_code code
= GET_CODE (x
);
229 case UNSPEC_VOLATILE
:
237 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
238 It should not be hard, and might be faster than "elsewhere". */
240 /* Just handle the most trivial case where we load from an unchanging
241 location (most importantly, pic tables). */
242 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
248 /* Don't mess with insns declared volatile. */
249 if (MEM_VOLATILE_P (x
))
257 fmt
= GET_RTX_FORMAT (code
);
258 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
262 if (!check_maybe_invariant (XEXP (x
, i
)))
265 else if (fmt
[i
] == 'E')
267 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
268 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
276 /* Returns the invariant definition for USE, or NULL if USE is not
279 static struct invariant
*
280 invariant_for_use (df_ref use
)
282 struct df_link
*defs
;
284 basic_block bb
= DF_REF_BB (use
), def_bb
;
286 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
289 defs
= DF_REF_CHAIN (use
);
290 if (!defs
|| defs
->next
)
293 check_invariant_table_size ();
294 if (!invariant_table
[DF_REF_ID (def
)])
297 def_bb
= DF_REF_BB (def
);
298 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
300 return invariant_table
[DF_REF_ID (def
)];
303 /* Computes hash value for invariant expression X in INSN. */
306 hash_invariant_expr_1 (rtx_insn
*insn
, rtx x
)
308 enum rtx_code code
= GET_CODE (x
);
311 hashval_t val
= code
;
314 struct invariant
*inv
;
322 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
325 use
= df_find_use (insn
, x
);
327 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
328 inv
= invariant_for_use (use
);
330 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
332 gcc_assert (inv
->eqto
!= ~0u);
339 fmt
= GET_RTX_FORMAT (code
);
340 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
343 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
344 else if (fmt
[i
] == 'E')
346 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
347 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
349 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
356 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
357 and INSN2 have always the same value. */
360 invariant_expr_equal_p (rtx_insn
*insn1
, rtx e1
, rtx_insn
*insn2
, rtx e2
)
362 enum rtx_code code
= GET_CODE (e1
);
366 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
369 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
370 the other one. If both are VOIDmode, we rely on the caller of this
371 function to verify that their modes are the same. */
372 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
381 return rtx_equal_p (e1
, e2
);
384 use1
= df_find_use (insn1
, e1
);
385 use2
= df_find_use (insn2
, e2
);
387 inv1
= invariant_for_use (use1
);
389 inv2
= invariant_for_use (use2
);
392 return rtx_equal_p (e1
, e2
);
397 gcc_assert (inv1
->eqto
!= ~0u);
398 gcc_assert (inv2
->eqto
!= ~0u);
399 return inv1
->eqto
== inv2
->eqto
;
405 fmt
= GET_RTX_FORMAT (code
);
406 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
413 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
417 else if (fmt
[i
] == 'E')
419 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
422 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
424 sub1
= XVECEXP (e1
, i
, j
);
425 sub2
= XVECEXP (e2
, i
, j
);
427 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
431 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
433 if (XINT (e1
, i
) != XINT (e2
, i
))
436 /* Unhandled type of subexpression, we fail conservatively. */
444 struct invariant_expr_hasher
: free_ptr_hash
<invariant_expr_entry
>
446 static inline hashval_t
hash (const invariant_expr_entry
*);
447 static inline bool equal (const invariant_expr_entry
*,
448 const invariant_expr_entry
*);
451 /* Returns hash value for invariant expression entry ENTRY. */
454 invariant_expr_hasher::hash (const invariant_expr_entry
*entry
)
459 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
462 invariant_expr_hasher::equal (const invariant_expr_entry
*entry1
,
463 const invariant_expr_entry
*entry2
)
465 if (entry1
->mode
!= entry2
->mode
)
468 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
469 entry2
->inv
->insn
, entry2
->expr
);
472 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
474 /* Checks whether invariant with value EXPR in machine mode MODE is
475 recorded in EQ. If this is the case, return the invariant. Otherwise
476 insert INV to the table for this expression and return INV. */
478 static struct invariant
*
479 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, machine_mode mode
,
480 struct invariant
*inv
)
482 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
483 struct invariant_expr_entry
*entry
;
484 struct invariant_expr_entry pentry
;
485 invariant_expr_entry
**slot
;
490 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
496 entry
= XNEW (struct invariant_expr_entry
);
506 /* Finds invariants identical to INV and records the equivalence. EQ is the
507 hash table of the invariants. */
510 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
514 struct invariant
*dep
;
517 struct invariant
*tmp
;
519 if (inv
->eqto
!= ~0u)
522 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
524 dep
= invariants
[depno
];
525 find_identical_invariants (eq
, dep
);
528 set
= single_set (inv
->insn
);
529 expr
= SET_SRC (set
);
530 mode
= GET_MODE (expr
);
531 if (mode
== VOIDmode
)
532 mode
= GET_MODE (SET_DEST (set
));
534 tmp
= find_or_insert_inv (eq
, expr
, mode
, inv
);
535 inv
->eqto
= tmp
->invno
;
537 if (tmp
->invno
!= inv
->invno
&& inv
->always_executed
)
540 if (dump_file
&& inv
->eqto
!= inv
->invno
)
542 "Invariant %d is equivalent to invariant %d.\n",
543 inv
->invno
, inv
->eqto
);
546 /* Find invariants with the same value and record the equivalences. */
549 merge_identical_invariants (void)
552 struct invariant
*inv
;
553 invariant_htab_type
eq (invariants
.length ());
555 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
556 find_identical_invariants (&eq
, inv
);
559 /* Determines the basic blocks inside LOOP that are always executed and
560 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
561 basic blocks that may either exit the loop, or contain the call that
562 does not have to return. BODY is body of the loop obtained by
563 get_loop_body_in_dom_order. */
566 compute_always_reached (struct loop
*loop
, basic_block
*body
,
567 bitmap may_exit
, bitmap always_reached
)
571 for (i
= 0; i
< loop
->num_nodes
; i
++)
573 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
574 bitmap_set_bit (always_reached
, i
);
576 if (bitmap_bit_p (may_exit
, i
))
581 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
582 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
583 additionally mark blocks that may exit due to a call. */
586 find_exits (struct loop
*loop
, basic_block
*body
,
587 bitmap may_exit
, bitmap has_exit
)
592 struct loop
*outermost_exit
= loop
, *aexit
;
593 bool has_call
= false;
596 for (i
= 0; i
< loop
->num_nodes
; i
++)
598 if (body
[i
]->loop_father
== loop
)
600 FOR_BB_INSNS (body
[i
], insn
)
603 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
604 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
607 bitmap_set_bit (may_exit
, i
);
612 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
614 if (flow_bb_inside_loop_p (loop
, e
->dest
))
617 bitmap_set_bit (may_exit
, i
);
618 bitmap_set_bit (has_exit
, i
);
619 outermost_exit
= find_common_loop (outermost_exit
,
620 e
->dest
->loop_father
);
625 /* Use the data stored for the subloop to decide whether we may exit
626 through it. It is sufficient to do this for header of the loop,
627 as other basic blocks inside it must be dominated by it. */
628 if (body
[i
]->loop_father
->header
!= body
[i
])
631 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
634 bitmap_set_bit (may_exit
, i
);
636 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
639 bitmap_set_bit (may_exit
, i
);
640 bitmap_set_bit (has_exit
, i
);
642 if (flow_loop_nested_p (aexit
, outermost_exit
))
643 outermost_exit
= aexit
;
647 if (loop
->aux
== NULL
)
649 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
650 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
651 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
653 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
654 LOOP_DATA (loop
)->has_call
= has_call
;
657 /* Check whether we may assign a value to X from a register. */
660 may_assign_reg_p (rtx x
)
662 return (GET_MODE (x
) != VOIDmode
663 && GET_MODE (x
) != BLKmode
664 && can_copy_p (GET_MODE (x
))
666 || !HARD_REGISTER_P (x
)
667 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
670 /* Finds definitions that may correspond to invariants in LOOP with body
674 find_defs (struct loop
*loop
)
679 "*****starting processing of loop %d ******\n",
683 df_remove_problem (df_chain
);
684 df_process_deferred_rescans ();
685 df_chain_add_problem (DF_UD_CHAIN
);
686 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
687 df_analyze_loop (loop
);
688 check_invariant_table_size ();
692 df_dump_region (dump_file
);
694 "*****ending processing of loop %d ******\n",
699 /* Creates a new invariant for definition DEF in INSN, depending on invariants
700 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
701 unless the program ends due to a function call. The newly created invariant
704 static struct invariant
*
705 create_new_invariant (struct def
*def
, rtx_insn
*insn
, bitmap depends_on
,
706 bool always_executed
)
708 struct invariant
*inv
= XNEW (struct invariant
);
709 rtx set
= single_set (insn
);
710 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
713 inv
->always_executed
= always_executed
;
714 inv
->depends_on
= depends_on
;
716 /* If the set is simple, usually by moving it we move the whole store out of
717 the loop. Otherwise we save only cost of the computation. */
720 inv
->cost
= set_rtx_cost (set
, speed
);
721 /* ??? Try to determine cheapness of address computation. Unfortunately
722 the address cost is only a relative measure, we can't really compare
723 it with any absolute number, but only with other address costs.
724 But here we don't have any other addresses, so compare with a magic
725 number anyway. It has to be large enough to not regress PR33928
726 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
727 enough to not regress 410.bwaves either (by still moving reg+reg
729 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
730 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set
))))
731 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
732 ADDR_SPACE_GENERIC
, speed
) < 3;
734 inv
->cheap_address
= false;
738 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
739 inv
->cheap_address
= false;
744 inv
->orig_regno
= -1;
748 inv
->invno
= invariants
.length ();
755 def
->invno
= inv
->invno
;
756 invariants
.safe_push (inv
);
761 "Set in insn %d is invariant (%d), cost %d, depends on ",
762 INSN_UID (insn
), inv
->invno
, inv
->cost
);
763 dump_bitmap (dump_file
, inv
->depends_on
);
769 /* Record USE at DEF. */
772 record_use (struct def
*def
, df_ref use
)
774 struct use
*u
= XNEW (struct use
);
776 u
->pos
= DF_REF_REAL_LOC (use
);
777 u
->insn
= DF_REF_INSN (use
);
778 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
779 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
787 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
788 bitmap. Returns true if all dependencies of USE are known to be
789 loop invariants, false otherwise. */
792 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
796 struct df_link
*defs
;
797 struct def
*def_data
;
798 struct invariant
*inv
;
800 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
803 defs
= DF_REF_CHAIN (use
);
806 unsigned int regno
= DF_REF_REGNO (use
);
808 /* If this is the use of an uninitialized argument register that is
809 likely to be spilled, do not move it lest this might extend its
810 lifetime and cause reload to die. This can occur for a call to
811 a function taking complex number arguments and moving the insns
812 preparing the arguments without moving the call itself wouldn't
813 gain much in practice. */
814 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
815 && FUNCTION_ARG_REGNO_P (regno
)
816 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
826 check_invariant_table_size ();
827 inv
= invariant_table
[DF_REF_ID (def
)];
832 gcc_assert (def_data
!= NULL
);
834 def_bb
= DF_REF_BB (def
);
835 /* Note that in case bb == def_bb, we know that the definition
836 dominates insn, because def has invariant_table[DF_REF_ID(def)]
837 defined and we process the insns in the basic block bb
839 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
842 bitmap_set_bit (depends_on
, def_data
->invno
);
847 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
848 bitmap. Returns true if all dependencies of INSN are known to be
849 loop invariants, false otherwise. */
852 check_dependencies (rtx_insn
*insn
, bitmap depends_on
)
854 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
856 basic_block bb
= BLOCK_FOR_INSN (insn
);
858 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
859 if (!check_dependency (bb
, use
, depends_on
))
861 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
862 if (!check_dependency (bb
, use
, depends_on
))
868 /* Pre-check candidate DEST to skip the one which can not make a valid insn
869 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
871 pre_check_invariant_p (bool simple
, rtx dest
)
873 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
876 unsigned int i
= REGNO (dest
);
877 struct df_insn_info
*insn_info
;
880 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
882 rtx_insn
*ref
= DF_REF_INSN (use
);
883 insn_info
= DF_INSN_INFO_GET (ref
);
885 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
886 if (DF_REF_REGNO (def_rec
) == i
)
888 /* Multi definitions at this stage, most likely are due to
889 instruction constraints, which requires both read and write
890 on the same register. Since move_invariant_reg is not
891 powerful enough to handle such cases, just ignore the INV
892 and leave the chance to others. */
900 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
901 executed. ALWAYS_EXECUTED is true if the insn is always executed,
902 unless the program ends due to a function call. */
905 find_invariant_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
912 struct invariant
*inv
;
914 /* We can't move a CC0 setter without the user. */
915 if (HAVE_cc0
&& sets_cc0_p (insn
))
918 set
= single_set (insn
);
921 dest
= SET_DEST (set
);
924 || HARD_REGISTER_P (dest
))
927 if (!may_assign_reg_p (dest
)
928 || !pre_check_invariant_p (simple
, dest
)
929 || !check_maybe_invariant (SET_SRC (set
)))
932 /* If the insn can throw exception, we cannot move it at all without changing
934 if (can_throw_internal (insn
))
937 /* We cannot make trapping insn executed, unless it was executed before. */
938 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
941 depends_on
= BITMAP_ALLOC (NULL
);
942 if (!check_dependencies (insn
, depends_on
))
944 BITMAP_FREE (depends_on
);
949 def
= XCNEW (struct def
);
953 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
957 ref
= df_find_def (insn
, dest
);
958 check_invariant_table_size ();
959 invariant_table
[DF_REF_ID (ref
)] = inv
;
963 /* Record registers used in INSN that have a unique invariant definition. */
966 record_uses (rtx_insn
*insn
)
968 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
970 struct invariant
*inv
;
972 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
974 inv
= invariant_for_use (use
);
976 record_use (inv
->def
, use
);
978 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
980 inv
= invariant_for_use (use
);
982 record_use (inv
->def
, use
);
986 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
987 executed. ALWAYS_EXECUTED is true if the insn is always executed,
988 unless the program ends due to a function call. */
991 find_invariants_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
993 find_invariant_insn (insn
, always_reached
, always_executed
);
997 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
998 basic block is always executed. ALWAYS_EXECUTED is true if the basic
999 block is always executed, unless the program ends due to a function
1003 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
1007 FOR_BB_INSNS (bb
, insn
)
1009 if (!NONDEBUG_INSN_P (insn
))
1012 find_invariants_insn (insn
, always_reached
, always_executed
);
1016 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1017 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
1018 always_reached
= false;
1022 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1023 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1024 bitmap of basic blocks in BODY that are always executed unless the program
1025 ends due to a function call. */
1028 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1029 bitmap always_reached
, bitmap always_executed
)
1033 for (i
= 0; i
< loop
->num_nodes
; i
++)
1034 find_invariants_bb (body
[i
],
1035 bitmap_bit_p (always_reached
, i
),
1036 bitmap_bit_p (always_executed
, i
));
1039 /* Finds invariants in LOOP. */
1042 find_invariants (struct loop
*loop
)
1044 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1045 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1046 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1047 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1048 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1050 find_exits (loop
, body
, may_exit
, has_exit
);
1051 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1052 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1055 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1056 merge_identical_invariants ();
1058 BITMAP_FREE (always_reached
);
1059 BITMAP_FREE (always_executed
);
1060 BITMAP_FREE (may_exit
);
1061 BITMAP_FREE (has_exit
);
1065 /* Frees a list of uses USE. */
1068 free_use_list (struct use
*use
)
1072 for (; use
; use
= next
)
1079 /* Return pressure class and number of hard registers (through *NREGS)
1080 for destination of INSN. */
1081 static enum reg_class
1082 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
1085 enum reg_class pressure_class
;
1086 rtx set
= single_set (insn
);
1088 /* Considered invariant insns have only one set. */
1089 gcc_assert (set
!= NULL_RTX
);
1090 reg
= SET_DEST (set
);
1091 if (GET_CODE (reg
) == SUBREG
)
1092 reg
= SUBREG_REG (reg
);
1096 pressure_class
= NO_REGS
;
1102 if (reg
== NULL_RTX
)
1103 pressure_class
= GENERAL_REGS
;
1106 pressure_class
= reg_allocno_class (REGNO (reg
));
1107 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1110 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1112 return pressure_class
;
1115 /* Calculates cost and number of registers needed for moving invariant INV
1116 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1117 the REG_CLASS of INV. Return
1118 -1: if INV is invalid.
1119 0: if INV and its depends_on have same reg_class
1120 1: if INV and its depends_on have different reg_classes. */
1123 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1127 unsigned aregs_needed
[N_REG_CLASSES
];
1129 struct invariant
*dep
;
1133 /* Find the representative of the class of the equivalent invariants. */
1134 inv
= invariants
[inv
->eqto
];
1137 if (! flag_ira_loop_pressure
)
1141 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1142 regs_needed
[ira_pressure_classes
[i
]] = 0;
1146 || inv
->stamp
== actual_stamp
)
1148 inv
->stamp
= actual_stamp
;
1150 if (! flag_ira_loop_pressure
)
1155 enum reg_class pressure_class
;
1157 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1158 regs_needed
[pressure_class
] += nregs
;
1159 *cl
= pressure_class
;
1163 if (!inv
->cheap_address
1164 || inv
->def
->n_uses
== 0
1165 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1166 (*comp_cost
) += inv
->cost
* inv
->eqno
;
1170 /* Hoisting constant pool constants into stack regs may cost more than
1171 just single register. On x87, the balance is affected both by the
1172 small number of FP registers, and by its register stack organization,
1173 that forces us to add compensation code in and around the loop to
1174 shuffle the operands to the top of stack before use, and pop them
1175 from the stack after the loop finishes.
1177 To model this effect, we increase the number of registers needed for
1178 stack registers by two: one register push, and one register pop.
1179 This usually has the effect that FP constant loads from the constant
1180 pool are not moved out of the loop.
1182 Note that this also means that dependent invariants can not be moved.
1183 However, the primary purpose of this pass is to move loop invariant
1184 address arithmetic out of loops, and address arithmetic that depends
1185 on floating point constants is unlikely to ever occur. */
1186 rtx set
= single_set (inv
->insn
);
1188 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1189 && constant_pool_constant_p (SET_SRC (set
)))
1191 if (flag_ira_loop_pressure
)
1192 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1194 regs_needed
[0] += 2;
1199 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1202 enum reg_class dep_cl
= ALL_REGS
;
1205 dep
= invariants
[depno
];
1207 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1211 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1213 if (! flag_ira_loop_pressure
)
1214 check_p
= aregs_needed
[0] != 0;
1217 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1218 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1220 check_p
= i
< ira_pressure_classes_num
;
1222 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1229 /* We need to check always_executed, since if the original value of
1230 the invariant may be preserved, we may need to keep it in a
1231 separate register. TODO check whether the register has an
1232 use outside of the loop. */
1233 && dep
->always_executed
1234 && !dep
->def
->uses
->next
)
1236 /* If this is a single use, after moving the dependency we will not
1237 need a new register. */
1238 if (! flag_ira_loop_pressure
)
1243 enum reg_class pressure_class
;
1245 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1246 aregs_needed
[pressure_class
] -= nregs
;
1250 if (! flag_ira_loop_pressure
)
1251 regs_needed
[0] += aregs_needed
[0];
1254 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1255 regs_needed
[ira_pressure_classes
[i
]]
1256 += aregs_needed
[ira_pressure_classes
[i
]];
1258 (*comp_cost
) += acomp_cost
;
1263 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1264 of registers used in the loop, NEW_REGS is the number of new variables
1265 already added due to the invariant motion. The number of registers needed
1266 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1267 through to estimate_reg_pressure_cost. */
1270 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1271 unsigned *new_regs
, unsigned regs_used
,
1272 bool speed
, bool call_p
)
1274 int comp_cost
, size_cost
;
1275 /* Workaround -Wmaybe-uninitialized false positive during
1276 profiledbootstrap by initializing it. */
1277 enum reg_class cl
= NO_REGS
;
1282 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1284 if (! flag_ira_loop_pressure
)
1286 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1287 regs_used
, speed
, call_p
)
1288 - estimate_reg_pressure_cost (new_regs
[0],
1289 regs_used
, speed
, call_p
));
1293 else if ((ret
== 0) && (cl
== NO_REGS
))
1294 /* Hoist it anyway since it does not impact register pressure. */
1299 enum reg_class pressure_class
;
1301 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1303 pressure_class
= ira_pressure_classes
[i
];
1305 if (!reg_classes_intersect_p (pressure_class
, cl
))
1308 if ((int) new_regs
[pressure_class
]
1309 + (int) regs_needed
[pressure_class
]
1310 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1311 + IRA_LOOP_RESERVED_REGS
1312 > ira_class_hard_regs_num
[pressure_class
])
1315 if (i
< ira_pressure_classes_num
)
1316 /* There will be register pressure excess and we want not to
1317 make this loop invariant motion. All loop invariants with
1318 non-positive gains will be rejected in function
1319 find_invariants_to_move. Therefore we return the negative
1322 One could think that this rejects also expensive loop
1323 invariant motions and this will hurt code performance.
1324 However numerous experiments with different heuristics
1325 taking invariant cost into account did not confirm this
1326 assumption. There are possible explanations for this
1328 o probably all expensive invariants were already moved out
1329 of the loop by PRE and gimple invariant motion pass.
1330 o expensive invariant execution will be hidden by insn
1331 scheduling or OOO processor hardware because usually such
1332 invariants have a lot of freedom to be executed
1334 Another reason for ignoring invariant cost vs spilling cost
1335 heuristics is also in difficulties to evaluate accurately
1336 spill cost at this stage. */
1342 return comp_cost
- size_cost
;
1345 /* Finds invariant with best gain for moving. Returns the gain, stores
1346 the invariant in *BEST and number of registers needed for it to
1347 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1348 NEW_REGS is the number of new variables already added due to invariant
1352 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1353 unsigned *new_regs
, unsigned regs_used
,
1354 bool speed
, bool call_p
)
1356 struct invariant
*inv
;
1357 int i
, gain
= 0, again
;
1358 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1360 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1365 /* Only consider the "representatives" of equivalent invariants. */
1366 if (inv
->eqto
!= inv
->invno
)
1369 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1375 if (! flag_ira_loop_pressure
)
1376 regs_needed
[0] = aregs_needed
[0];
1379 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1380 regs_needed
[ira_pressure_classes
[i
]]
1381 = aregs_needed
[ira_pressure_classes
[i
]];
1389 /* Marks invariant INVNO and all its dependencies for moving. */
1392 set_move_mark (unsigned invno
, int gain
)
1394 struct invariant
*inv
= invariants
[invno
];
1397 /* Find the representative of the class of the equivalent invariants. */
1398 inv
= invariants
[inv
->eqto
];
1407 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1410 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1414 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1416 set_move_mark (invno
, -1);
1420 /* Determines which invariants to move. */
1423 find_invariants_to_move (bool speed
, bool call_p
)
1426 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1427 struct invariant
*inv
= NULL
;
1429 if (!invariants
.length ())
1432 if (flag_ira_loop_pressure
)
1433 /* REGS_USED is actually never used when the flag is on. */
1436 /* We do not really do a good job in estimating number of
1437 registers used; we put some initial bound here to stand for
1438 induction variables etc. that we do not detect. */
1440 unsigned int n_regs
= DF_REG_SIZE (df
);
1444 for (i
= 0; i
< n_regs
; i
++)
1446 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1448 /* This is a value that is used but not changed inside loop. */
1454 if (! flag_ira_loop_pressure
)
1455 new_regs
[0] = regs_needed
[0] = 0;
1458 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1459 new_regs
[ira_pressure_classes
[i
]] = 0;
1461 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1462 new_regs
, regs_used
,
1463 speed
, call_p
)) > 0)
1465 set_move_mark (inv
->invno
, gain
);
1466 if (! flag_ira_loop_pressure
)
1467 new_regs
[0] += regs_needed
[0];
1470 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1471 new_regs
[ira_pressure_classes
[i
]]
1472 += regs_needed
[ira_pressure_classes
[i
]];
1477 /* Replace the uses, reached by the definition of invariant INV, by REG.
1479 IN_GROUP is nonzero if this is part of a group of changes that must be
1480 performed as a group. In that case, the changes will be stored. The
1481 function `apply_change_group' will validate and apply the changes. */
1484 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1486 /* Replace the uses we know to be dominated. It saves work for copy
1487 propagation, and also it is necessary so that dependent invariants
1488 are computed right. */
1492 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1493 validate_change (use
->insn
, use
->pos
, reg
, true);
1495 /* If we aren't part of a larger group, apply the changes now. */
1497 return apply_change_group ();
1503 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1504 the block preceding its header. */
1507 can_move_invariant_reg (struct loop
*loop
, struct invariant
*inv
, rtx reg
)
1510 unsigned int dest_regno
, defs_in_loop_count
= 0;
1511 rtx_insn
*insn
= inv
->insn
;
1512 basic_block bb
= BLOCK_FOR_INSN (inv
->insn
);
1514 /* We ignore hard register and memory access for cost and complexity reasons.
1515 Hard register are few at this stage and expensive to consider as they
1516 require building a separate data flow. Memory access would require using
1517 df_simulate_* and can_move_insns_across functions and is more complex. */
1518 if (!REG_P (reg
) || HARD_REGISTER_P (reg
))
1521 /* Check whether the set is always executed. We could omit this condition if
1522 we know that the register is unused outside of the loop, but it does not
1523 seem worth finding out. */
1524 if (!inv
->always_executed
)
1527 /* Check that all uses that would be dominated by def are already dominated
1529 dest_regno
= REGNO (reg
);
1530 for (use
= DF_REG_USE_CHAIN (dest_regno
); use
; use
= DF_REF_NEXT_REG (use
))
1535 use_insn
= DF_REF_INSN (use
);
1536 use_bb
= BLOCK_FOR_INSN (use_insn
);
1538 /* Ignore instruction considered for moving. */
1539 if (use_insn
== insn
)
1542 /* Don't consider uses outside loop. */
1543 if (!flow_bb_inside_loop_p (loop
, use_bb
))
1546 /* Don't move if a use is not dominated by def in insn. */
1547 if (use_bb
== bb
&& DF_INSN_LUID (insn
) >= DF_INSN_LUID (use_insn
))
1549 if (!dominated_by_p (CDI_DOMINATORS
, use_bb
, bb
))
1553 /* Check for other defs. Any other def in the loop might reach a use
1554 currently reached by the def in insn. */
1555 for (def
= DF_REG_DEF_CHAIN (dest_regno
); def
; def
= DF_REF_NEXT_REG (def
))
1557 basic_block def_bb
= DF_REF_BB (def
);
1559 /* Defs in exit block cannot reach a use they weren't already. */
1560 if (single_succ_p (def_bb
))
1562 basic_block def_bb_succ
;
1564 def_bb_succ
= single_succ (def_bb
);
1565 if (!flow_bb_inside_loop_p (loop
, def_bb_succ
))
1569 if (++defs_in_loop_count
> 1)
1576 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1580 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1582 struct invariant
*inv
= invariants
[invno
];
1583 struct invariant
*repr
= invariants
[inv
->eqto
];
1585 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1586 rtx reg
, set
, dest
, note
;
1595 /* If this is a representative of the class of equivalent invariants,
1596 really move the invariant. Otherwise just replace its use with
1597 the register used for the representative. */
1600 if (inv
->depends_on
)
1602 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1604 if (!move_invariant_reg (loop
, i
))
1609 /* If possible, just move the set out of the loop. Otherwise, we
1610 need to create a temporary register. */
1611 set
= single_set (inv
->insn
);
1612 reg
= dest
= SET_DEST (set
);
1613 if (GET_CODE (reg
) == SUBREG
)
1614 reg
= SUBREG_REG (reg
);
1616 regno
= REGNO (reg
);
1618 if (!can_move_invariant_reg (loop
, inv
, dest
))
1620 reg
= gen_reg_rtx_and_attrs (dest
);
1622 /* Try replacing the destination by a new pseudoregister. */
1623 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1625 /* As well as all the dominated uses. */
1626 replace_uses (inv
, reg
, true);
1628 /* And validate all the changes. */
1629 if (!apply_change_group ())
1632 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1635 fprintf (dump_file
, "Invariant %d moved without introducing a new "
1636 "temporary register\n", invno
);
1637 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1639 /* If there is a REG_EQUAL note on the insn we just moved, and the
1640 insn is in a basic block that is not always executed or the note
1641 contains something for which we don't know the invariant status,
1642 the note may no longer be valid after we move the insn. Note that
1643 uses in REG_EQUAL notes are taken into account in the computation
1644 of invariants, so it is safe to retain the note even if it contains
1645 register references for which we know the invariant status. */
1646 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1647 && (!inv
->always_executed
1648 || !check_maybe_invariant (XEXP (note
, 0))))
1649 remove_note (inv
->insn
, note
);
1653 if (!move_invariant_reg (loop
, repr
->invno
))
1656 regno
= repr
->orig_regno
;
1657 if (!replace_uses (inv
, reg
, false))
1659 set
= single_set (inv
->insn
);
1660 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1661 delete_insn (inv
->insn
);
1665 inv
->orig_regno
= regno
;
1670 /* If we failed, clear move flag, so that we do not try to move inv
1673 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1675 inv
->reg
= NULL_RTX
;
1676 inv
->orig_regno
= -1;
1681 /* Move selected invariant out of the LOOP. Newly created regs are marked
1682 in TEMPORARY_REGS. */
1685 move_invariants (struct loop
*loop
)
1687 struct invariant
*inv
;
1690 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1691 move_invariant_reg (loop
, i
);
1692 if (flag_ira_loop_pressure
&& resize_reg_info ())
1694 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1695 if (inv
->reg
!= NULL_RTX
)
1697 if (inv
->orig_regno
>= 0)
1698 setup_reg_classes (REGNO (inv
->reg
),
1699 reg_preferred_class (inv
->orig_regno
),
1700 reg_alternate_class (inv
->orig_regno
),
1701 reg_allocno_class (inv
->orig_regno
));
1703 setup_reg_classes (REGNO (inv
->reg
),
1704 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1709 /* Initializes invariant motion data. */
1712 init_inv_motion_data (void)
1716 invariants
.create (100);
1719 /* Frees the data allocated by invariant motion. */
1722 free_inv_motion_data (void)
1726 struct invariant
*inv
;
1728 check_invariant_table_size ();
1729 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1731 inv
= invariant_table
[i
];
1735 gcc_assert (def
!= NULL
);
1737 free_use_list (def
->uses
);
1739 invariant_table
[i
] = NULL
;
1743 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1745 BITMAP_FREE (inv
->depends_on
);
1748 invariants
.release ();
1751 /* Move the invariants out of the LOOP. */
1754 move_single_loop_invariants (struct loop
*loop
)
1756 init_inv_motion_data ();
1758 find_invariants (loop
);
1759 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1760 LOOP_DATA (loop
)->has_call
);
1761 move_invariants (loop
);
1763 free_inv_motion_data ();
1766 /* Releases the auxiliary data for LOOP. */
1769 free_loop_data (struct loop
*loop
)
1771 struct loop_data
*data
= LOOP_DATA (loop
);
1775 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1776 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1783 /* Registers currently living. */
1784 static bitmap_head curr_regs_live
;
1786 /* Current reg pressure for each pressure class. */
1787 static int curr_reg_pressure
[N_REG_CLASSES
];
1789 /* Record all regs that are set in any one insn. Communication from
1790 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1791 all hard-registers. */
1792 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1793 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1794 /* Number of regs stored in the previous array. */
1795 static int n_regs_set
;
1797 /* Return pressure class and number of needed hard registers (through
1798 *NREGS) of register REGNO. */
1799 static enum reg_class
1800 get_regno_pressure_class (int regno
, int *nregs
)
1802 if (regno
>= FIRST_PSEUDO_REGISTER
)
1804 enum reg_class pressure_class
;
1806 pressure_class
= reg_allocno_class (regno
);
1807 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1809 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1810 return pressure_class
;
1812 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1813 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1816 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1825 /* Increase (if INCR_P) or decrease current register pressure for
1828 change_pressure (int regno
, bool incr_p
)
1831 enum reg_class pressure_class
;
1833 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1835 curr_reg_pressure
[pressure_class
] -= nregs
;
1838 curr_reg_pressure
[pressure_class
] += nregs
;
1839 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1840 < curr_reg_pressure
[pressure_class
])
1841 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1842 = curr_reg_pressure
[pressure_class
];
1846 /* Mark REGNO birth. */
1848 mark_regno_live (int regno
)
1852 for (loop
= curr_loop
;
1853 loop
!= current_loops
->tree_root
;
1854 loop
= loop_outer (loop
))
1855 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1856 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1858 change_pressure (regno
, true);
1861 /* Mark REGNO death. */
1863 mark_regno_death (int regno
)
1865 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1867 change_pressure (regno
, false);
1870 /* Mark setting register REG. */
1872 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1873 void *data ATTRIBUTE_UNUSED
)
1875 if (GET_CODE (reg
) == SUBREG
)
1876 reg
= SUBREG_REG (reg
);
1881 regs_set
[n_regs_set
++] = reg
;
1883 unsigned int end_regno
= END_REGNO (reg
);
1884 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1885 mark_regno_live (regno
);
1888 /* Mark clobbering register REG. */
1890 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1892 if (GET_CODE (setter
) == CLOBBER
)
1893 mark_reg_store (reg
, setter
, data
);
1896 /* Mark register REG death. */
1898 mark_reg_death (rtx reg
)
1900 unsigned int end_regno
= END_REGNO (reg
);
1901 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1902 mark_regno_death (regno
);
1905 /* Mark occurrence of registers in X for the current loop. */
1907 mark_ref_regs (rtx x
)
1916 code
= GET_CODE (x
);
1921 for (loop
= curr_loop
;
1922 loop
!= current_loops
->tree_root
;
1923 loop
= loop_outer (loop
))
1924 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1928 fmt
= GET_RTX_FORMAT (code
);
1929 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1931 mark_ref_regs (XEXP (x
, i
));
1932 else if (fmt
[i
] == 'E')
1936 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1937 mark_ref_regs (XVECEXP (x
, i
, j
));
1941 /* Calculate register pressure in the loops. */
1943 calculate_loop_reg_pressure (void)
1951 struct loop
*loop
, *parent
;
1953 FOR_EACH_LOOP (loop
, 0)
1954 if (loop
->aux
== NULL
)
1956 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1957 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1958 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1960 ira_setup_eliminable_regset ();
1961 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1962 FOR_EACH_BB_FN (bb
, cfun
)
1964 curr_loop
= bb
->loop_father
;
1965 if (curr_loop
== current_loops
->tree_root
)
1968 for (loop
= curr_loop
;
1969 loop
!= current_loops
->tree_root
;
1970 loop
= loop_outer (loop
))
1971 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1973 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1974 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1975 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1976 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1977 change_pressure (j
, true);
1979 FOR_BB_INSNS (bb
, insn
)
1981 if (! NONDEBUG_INSN_P (insn
))
1984 mark_ref_regs (PATTERN (insn
));
1986 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1988 /* Mark any registers dead after INSN as dead now. */
1990 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1991 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1992 mark_reg_death (XEXP (link
, 0));
1994 /* Mark any registers set in INSN as live,
1995 and mark them as conflicting with all other live regs.
1996 Clobbers are processed again, so they conflict with
1997 the registers that are set. */
1999 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
2002 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2003 if (REG_NOTE_KIND (link
) == REG_INC
)
2004 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
2006 while (n_regs_set
-- > 0)
2008 rtx note
= find_regno_note (insn
, REG_UNUSED
,
2009 REGNO (regs_set
[n_regs_set
]));
2013 mark_reg_death (XEXP (note
, 0));
2017 bitmap_clear (&curr_regs_live
);
2018 if (flag_ira_region
== IRA_REGION_MIXED
2019 || flag_ira_region
== IRA_REGION_ALL
)
2020 FOR_EACH_LOOP (loop
, 0)
2022 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2023 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
2025 enum reg_class pressure_class
;
2028 pressure_class
= get_regno_pressure_class (j
, &nregs
);
2029 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
2032 if (dump_file
== NULL
)
2034 FOR_EACH_LOOP (loop
, 0)
2036 parent
= loop_outer (loop
);
2037 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2038 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
2039 loop
->header
->index
, loop_depth (loop
));
2040 fprintf (dump_file
, "\n ref. regnos:");
2041 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
2042 fprintf (dump_file
, " %d", j
);
2043 fprintf (dump_file
, "\n live regnos:");
2044 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2045 fprintf (dump_file
, " %d", j
);
2046 fprintf (dump_file
, "\n Pressure:");
2047 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
2049 enum reg_class pressure_class
;
2051 pressure_class
= ira_pressure_classes
[i
];
2052 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
2054 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
2055 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
2057 fprintf (dump_file
, "\n");
2063 /* Move the invariants out of the loops. */
2066 move_loop_invariants (void)
2070 if (flag_ira_loop_pressure
)
2073 regstat_init_n_sets_and_refs ();
2074 ira_set_pseudo_classes (true, dump_file
);
2075 calculate_loop_reg_pressure ();
2076 regstat_free_n_sets_and_refs ();
2078 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
2079 /* Process the loops, innermost first. */
2080 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2083 /* move_single_loop_invariants for very large loops
2084 is time consuming and might need a lot of memory. */
2085 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2086 move_single_loop_invariants (loop
);
2089 FOR_EACH_LOOP (loop
, 0)
2091 free_loop_data (loop
);
2094 if (flag_ira_loop_pressure
)
2095 /* There is no sense to keep this info because it was most
2096 probably outdated by subsequent passes. */
2098 free (invariant_table
);
2099 invariant_table
= NULL
;
2100 invariant_table_size
= 0;
2102 #ifdef ENABLE_CHECKING
2103 verify_flow_info ();