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"
48 #include "dominance.h"
51 #include "basic-block.h"
57 #include "insn-config.h"
75 /* The data stored for the loop. */
79 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
80 bool has_call
; /* True if the loop contains a call. */
81 /* Maximal register pressure inside loop for given register class
82 (defined only for the pressure classes). */
83 int max_reg_pressure
[N_REG_CLASSES
];
84 /* Loop regs referenced and live pseudo-registers. */
86 bitmap_head regs_live
;
89 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
91 /* The description of an use. */
95 rtx
*pos
; /* Position of the use. */
96 rtx_insn
*insn
; /* The insn in that the use occurs. */
97 unsigned addr_use_p
; /* Whether the use occurs in an address. */
98 struct use
*next
; /* Next use in the list. */
101 /* The description of a def. */
105 struct use
*uses
; /* The list of uses that are uniquely reached
107 unsigned n_uses
; /* Number of such uses. */
108 unsigned n_addr_uses
; /* Number of uses in addresses. */
109 unsigned invno
; /* The corresponding invariant. */
112 /* The data stored for each invariant. */
116 /* The number of the invariant. */
119 /* The number of the invariant with the same value. */
122 /* The number of invariants which eqto this. */
125 /* If we moved the invariant out of the loop, the register that contains its
129 /* If we moved the invariant out of the loop, the original regno
130 that contained its value. */
133 /* The definition of the invariant. */
136 /* The insn in that it is defined. */
139 /* Whether it is always executed. */
140 bool always_executed
;
142 /* Whether to move the invariant. */
145 /* Whether the invariant is cheap when used as an address. */
148 /* Cost of the invariant. */
151 /* The invariants it depends on. */
154 /* Used for detecting already visited invariants during determining
155 costs of movements. */
159 /* Currently processed loop. */
160 static struct loop
*curr_loop
;
162 /* Table of invariants indexed by the df_ref uid field. */
164 static unsigned int invariant_table_size
= 0;
165 static struct invariant
** invariant_table
;
167 /* Entry for hash table of invariant expressions. */
169 struct invariant_expr_entry
172 struct invariant
*inv
;
184 /* The actual stamp for marking already visited invariants during determining
185 costs of movements. */
187 static unsigned actual_stamp
;
189 typedef struct invariant
*invariant_p
;
192 /* The invariants. */
194 static vec
<invariant_p
> invariants
;
196 /* Check the size of the invariant table and realloc if necessary. */
199 check_invariant_table_size (void)
201 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
203 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
204 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
205 memset (&invariant_table
[invariant_table_size
], 0,
206 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
207 invariant_table_size
= new_size
;
211 /* Test for possibility of invariantness of X. */
214 check_maybe_invariant (rtx x
)
216 enum rtx_code code
= GET_CODE (x
);
230 case UNSPEC_VOLATILE
:
238 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
239 It should not be hard, and might be faster than "elsewhere". */
241 /* Just handle the most trivial case where we load from an unchanging
242 location (most importantly, pic tables). */
243 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
249 /* Don't mess with insns declared volatile. */
250 if (MEM_VOLATILE_P (x
))
258 fmt
= GET_RTX_FORMAT (code
);
259 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
263 if (!check_maybe_invariant (XEXP (x
, i
)))
266 else if (fmt
[i
] == 'E')
268 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
269 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
277 /* Returns the invariant definition for USE, or NULL if USE is not
280 static struct invariant
*
281 invariant_for_use (df_ref use
)
283 struct df_link
*defs
;
285 basic_block bb
= DF_REF_BB (use
), def_bb
;
287 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
290 defs
= DF_REF_CHAIN (use
);
291 if (!defs
|| defs
->next
)
294 check_invariant_table_size ();
295 if (!invariant_table
[DF_REF_ID (def
)])
298 def_bb
= DF_REF_BB (def
);
299 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
301 return invariant_table
[DF_REF_ID (def
)];
304 /* Computes hash value for invariant expression X in INSN. */
307 hash_invariant_expr_1 (rtx_insn
*insn
, rtx x
)
309 enum rtx_code code
= GET_CODE (x
);
312 hashval_t val
= code
;
315 struct invariant
*inv
;
323 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
326 use
= df_find_use (insn
, x
);
328 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
329 inv
= invariant_for_use (use
);
331 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
333 gcc_assert (inv
->eqto
!= ~0u);
340 fmt
= GET_RTX_FORMAT (code
);
341 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
344 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
345 else if (fmt
[i
] == 'E')
347 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
348 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
350 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
357 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
358 and INSN2 have always the same value. */
361 invariant_expr_equal_p (rtx_insn
*insn1
, rtx e1
, rtx_insn
*insn2
, rtx e2
)
363 enum rtx_code code
= GET_CODE (e1
);
367 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
370 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
371 the other one. If both are VOIDmode, we rely on the caller of this
372 function to verify that their modes are the same. */
373 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
382 return rtx_equal_p (e1
, e2
);
385 use1
= df_find_use (insn1
, e1
);
386 use2
= df_find_use (insn2
, e2
);
388 inv1
= invariant_for_use (use1
);
390 inv2
= invariant_for_use (use2
);
393 return rtx_equal_p (e1
, e2
);
398 gcc_assert (inv1
->eqto
!= ~0u);
399 gcc_assert (inv2
->eqto
!= ~0u);
400 return inv1
->eqto
== inv2
->eqto
;
406 fmt
= GET_RTX_FORMAT (code
);
407 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
414 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
418 else if (fmt
[i
] == 'E')
420 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
423 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
425 sub1
= XVECEXP (e1
, i
, j
);
426 sub2
= XVECEXP (e2
, i
, j
);
428 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
432 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
434 if (XINT (e1
, i
) != XINT (e2
, i
))
437 /* Unhandled type of subexpression, we fail conservatively. */
445 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
447 typedef invariant_expr_entry
*value_type
;
448 typedef invariant_expr_entry
*compare_type
;
449 static inline hashval_t
hash (const invariant_expr_entry
*);
450 static inline bool equal (const invariant_expr_entry
*,
451 const invariant_expr_entry
*);
454 /* Returns hash value for invariant expression entry ENTRY. */
457 invariant_expr_hasher::hash (const invariant_expr_entry
*entry
)
462 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
465 invariant_expr_hasher::equal (const invariant_expr_entry
*entry1
,
466 const invariant_expr_entry
*entry2
)
468 if (entry1
->mode
!= entry2
->mode
)
471 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
472 entry2
->inv
->insn
, entry2
->expr
);
475 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
477 /* Checks whether invariant with value EXPR in machine mode MODE is
478 recorded in EQ. If this is the case, return the invariant. Otherwise
479 insert INV to the table for this expression and return INV. */
481 static struct invariant
*
482 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, machine_mode mode
,
483 struct invariant
*inv
)
485 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
486 struct invariant_expr_entry
*entry
;
487 struct invariant_expr_entry pentry
;
488 invariant_expr_entry
**slot
;
493 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
499 entry
= XNEW (struct invariant_expr_entry
);
509 /* Finds invariants identical to INV and records the equivalence. EQ is the
510 hash table of the invariants. */
513 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
517 struct invariant
*dep
;
520 struct invariant
*tmp
;
522 if (inv
->eqto
!= ~0u)
525 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
527 dep
= invariants
[depno
];
528 find_identical_invariants (eq
, dep
);
531 set
= single_set (inv
->insn
);
532 expr
= SET_SRC (set
);
533 mode
= GET_MODE (expr
);
534 if (mode
== VOIDmode
)
535 mode
= GET_MODE (SET_DEST (set
));
537 tmp
= find_or_insert_inv (eq
, expr
, mode
, inv
);
538 inv
->eqto
= tmp
->invno
;
540 if (tmp
->invno
!= inv
->invno
&& inv
->always_executed
)
543 if (dump_file
&& inv
->eqto
!= inv
->invno
)
545 "Invariant %d is equivalent to invariant %d.\n",
546 inv
->invno
, inv
->eqto
);
549 /* Find invariants with the same value and record the equivalences. */
552 merge_identical_invariants (void)
555 struct invariant
*inv
;
556 invariant_htab_type
eq (invariants
.length ());
558 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
559 find_identical_invariants (&eq
, inv
);
562 /* Determines the basic blocks inside LOOP that are always executed and
563 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
564 basic blocks that may either exit the loop, or contain the call that
565 does not have to return. BODY is body of the loop obtained by
566 get_loop_body_in_dom_order. */
569 compute_always_reached (struct loop
*loop
, basic_block
*body
,
570 bitmap may_exit
, bitmap always_reached
)
574 for (i
= 0; i
< loop
->num_nodes
; i
++)
576 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
577 bitmap_set_bit (always_reached
, i
);
579 if (bitmap_bit_p (may_exit
, i
))
584 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
585 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
586 additionally mark blocks that may exit due to a call. */
589 find_exits (struct loop
*loop
, basic_block
*body
,
590 bitmap may_exit
, bitmap has_exit
)
595 struct loop
*outermost_exit
= loop
, *aexit
;
596 bool has_call
= false;
599 for (i
= 0; i
< loop
->num_nodes
; i
++)
601 if (body
[i
]->loop_father
== loop
)
603 FOR_BB_INSNS (body
[i
], insn
)
606 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
607 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
610 bitmap_set_bit (may_exit
, i
);
615 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
617 if (flow_bb_inside_loop_p (loop
, e
->dest
))
620 bitmap_set_bit (may_exit
, i
);
621 bitmap_set_bit (has_exit
, i
);
622 outermost_exit
= find_common_loop (outermost_exit
,
623 e
->dest
->loop_father
);
628 /* Use the data stored for the subloop to decide whether we may exit
629 through it. It is sufficient to do this for header of the loop,
630 as other basic blocks inside it must be dominated by it. */
631 if (body
[i
]->loop_father
->header
!= body
[i
])
634 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
637 bitmap_set_bit (may_exit
, i
);
639 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
642 bitmap_set_bit (may_exit
, i
);
643 bitmap_set_bit (has_exit
, i
);
645 if (flow_loop_nested_p (aexit
, outermost_exit
))
646 outermost_exit
= aexit
;
650 if (loop
->aux
== NULL
)
652 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
653 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
654 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
656 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
657 LOOP_DATA (loop
)->has_call
= has_call
;
660 /* Check whether we may assign a value to X from a register. */
663 may_assign_reg_p (rtx x
)
665 return (GET_MODE (x
) != VOIDmode
666 && GET_MODE (x
) != BLKmode
667 && can_copy_p (GET_MODE (x
))
669 || !HARD_REGISTER_P (x
)
670 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
673 /* Finds definitions that may correspond to invariants in LOOP with body
677 find_defs (struct loop
*loop
)
682 "*****starting processing of loop %d ******\n",
686 df_remove_problem (df_chain
);
687 df_process_deferred_rescans ();
688 df_chain_add_problem (DF_UD_CHAIN
);
689 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
690 df_analyze_loop (loop
);
691 check_invariant_table_size ();
695 df_dump_region (dump_file
);
697 "*****ending processing of loop %d ******\n",
702 /* Creates a new invariant for definition DEF in INSN, depending on invariants
703 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
704 unless the program ends due to a function call. The newly created invariant
707 static struct invariant
*
708 create_new_invariant (struct def
*def
, rtx_insn
*insn
, bitmap depends_on
,
709 bool always_executed
)
711 struct invariant
*inv
= XNEW (struct invariant
);
712 rtx set
= single_set (insn
);
713 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
716 inv
->always_executed
= always_executed
;
717 inv
->depends_on
= depends_on
;
719 /* If the set is simple, usually by moving it we move the whole store out of
720 the loop. Otherwise we save only cost of the computation. */
723 inv
->cost
= set_rtx_cost (set
, speed
);
724 /* ??? Try to determine cheapness of address computation. Unfortunately
725 the address cost is only a relative measure, we can't really compare
726 it with any absolute number, but only with other address costs.
727 But here we don't have any other addresses, so compare with a magic
728 number anyway. It has to be large enough to not regress PR33928
729 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
730 enough to not regress 410.bwaves either (by still moving reg+reg
732 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
733 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set
))))
734 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
735 ADDR_SPACE_GENERIC
, speed
) < 3;
737 inv
->cheap_address
= false;
741 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
742 inv
->cheap_address
= false;
747 inv
->orig_regno
= -1;
751 inv
->invno
= invariants
.length ();
758 def
->invno
= inv
->invno
;
759 invariants
.safe_push (inv
);
764 "Set in insn %d is invariant (%d), cost %d, depends on ",
765 INSN_UID (insn
), inv
->invno
, inv
->cost
);
766 dump_bitmap (dump_file
, inv
->depends_on
);
772 /* Record USE at DEF. */
775 record_use (struct def
*def
, df_ref use
)
777 struct use
*u
= XNEW (struct use
);
779 u
->pos
= DF_REF_REAL_LOC (use
);
780 u
->insn
= DF_REF_INSN (use
);
781 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
782 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
790 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
791 bitmap. Returns true if all dependencies of USE are known to be
792 loop invariants, false otherwise. */
795 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
799 struct df_link
*defs
;
800 struct def
*def_data
;
801 struct invariant
*inv
;
803 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
806 defs
= DF_REF_CHAIN (use
);
809 unsigned int regno
= DF_REF_REGNO (use
);
811 /* If this is the use of an uninitialized argument register that is
812 likely to be spilled, do not move it lest this might extend its
813 lifetime and cause reload to die. This can occur for a call to
814 a function taking complex number arguments and moving the insns
815 preparing the arguments without moving the call itself wouldn't
816 gain much in practice. */
817 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
818 && FUNCTION_ARG_REGNO_P (regno
)
819 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
829 check_invariant_table_size ();
830 inv
= invariant_table
[DF_REF_ID (def
)];
835 gcc_assert (def_data
!= NULL
);
837 def_bb
= DF_REF_BB (def
);
838 /* Note that in case bb == def_bb, we know that the definition
839 dominates insn, because def has invariant_table[DF_REF_ID(def)]
840 defined and we process the insns in the basic block bb
842 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
845 bitmap_set_bit (depends_on
, def_data
->invno
);
850 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
851 bitmap. Returns true if all dependencies of INSN are known to be
852 loop invariants, false otherwise. */
855 check_dependencies (rtx_insn
*insn
, bitmap depends_on
)
857 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
859 basic_block bb
= BLOCK_FOR_INSN (insn
);
861 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
862 if (!check_dependency (bb
, use
, depends_on
))
864 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
865 if (!check_dependency (bb
, use
, depends_on
))
871 /* Pre-check candidate DEST to skip the one which can not make a valid insn
872 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
874 pre_check_invariant_p (bool simple
, rtx dest
)
876 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
879 unsigned int i
= REGNO (dest
);
880 struct df_insn_info
*insn_info
;
883 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
885 rtx_insn
*ref
= DF_REF_INSN (use
);
886 insn_info
= DF_INSN_INFO_GET (ref
);
888 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
889 if (DF_REF_REGNO (def_rec
) == i
)
891 /* Multi definitions at this stage, most likely are due to
892 instruction constraints, which requires both read and write
893 on the same register. Since move_invariant_reg is not
894 powerful enough to handle such cases, just ignore the INV
895 and leave the chance to others. */
903 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
904 executed. ALWAYS_EXECUTED is true if the insn is always executed,
905 unless the program ends due to a function call. */
908 find_invariant_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
915 struct invariant
*inv
;
917 /* We can't move a CC0 setter without the user. */
918 if (HAVE_cc0
&& sets_cc0_p (insn
))
921 set
= single_set (insn
);
924 dest
= SET_DEST (set
);
927 || HARD_REGISTER_P (dest
))
930 if (!may_assign_reg_p (dest
)
931 || !pre_check_invariant_p (simple
, dest
)
932 || !check_maybe_invariant (SET_SRC (set
)))
935 /* If the insn can throw exception, we cannot move it at all without changing
937 if (can_throw_internal (insn
))
940 /* We cannot make trapping insn executed, unless it was executed before. */
941 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
944 depends_on
= BITMAP_ALLOC (NULL
);
945 if (!check_dependencies (insn
, depends_on
))
947 BITMAP_FREE (depends_on
);
952 def
= XCNEW (struct def
);
956 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
960 ref
= df_find_def (insn
, dest
);
961 check_invariant_table_size ();
962 invariant_table
[DF_REF_ID (ref
)] = inv
;
966 /* Record registers used in INSN that have a unique invariant definition. */
969 record_uses (rtx_insn
*insn
)
971 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
973 struct invariant
*inv
;
975 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
977 inv
= invariant_for_use (use
);
979 record_use (inv
->def
, use
);
981 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
983 inv
= invariant_for_use (use
);
985 record_use (inv
->def
, use
);
989 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
990 executed. ALWAYS_EXECUTED is true if the insn is always executed,
991 unless the program ends due to a function call. */
994 find_invariants_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
996 find_invariant_insn (insn
, always_reached
, always_executed
);
1000 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1001 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1002 block is always executed, unless the program ends due to a function
1006 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
1010 FOR_BB_INSNS (bb
, insn
)
1012 if (!NONDEBUG_INSN_P (insn
))
1015 find_invariants_insn (insn
, always_reached
, always_executed
);
1019 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1020 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
1021 always_reached
= false;
1025 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1026 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1027 bitmap of basic blocks in BODY that are always executed unless the program
1028 ends due to a function call. */
1031 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1032 bitmap always_reached
, bitmap always_executed
)
1036 for (i
= 0; i
< loop
->num_nodes
; i
++)
1037 find_invariants_bb (body
[i
],
1038 bitmap_bit_p (always_reached
, i
),
1039 bitmap_bit_p (always_executed
, i
));
1042 /* Finds invariants in LOOP. */
1045 find_invariants (struct loop
*loop
)
1047 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1048 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1049 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1050 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1051 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1053 find_exits (loop
, body
, may_exit
, has_exit
);
1054 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1055 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1058 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1059 merge_identical_invariants ();
1061 BITMAP_FREE (always_reached
);
1062 BITMAP_FREE (always_executed
);
1063 BITMAP_FREE (may_exit
);
1064 BITMAP_FREE (has_exit
);
1068 /* Frees a list of uses USE. */
1071 free_use_list (struct use
*use
)
1075 for (; use
; use
= next
)
1082 /* Return pressure class and number of hard registers (through *NREGS)
1083 for destination of INSN. */
1084 static enum reg_class
1085 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
1088 enum reg_class pressure_class
;
1089 rtx set
= single_set (insn
);
1091 /* Considered invariant insns have only one set. */
1092 gcc_assert (set
!= NULL_RTX
);
1093 reg
= SET_DEST (set
);
1094 if (GET_CODE (reg
) == SUBREG
)
1095 reg
= SUBREG_REG (reg
);
1099 pressure_class
= NO_REGS
;
1105 if (reg
== NULL_RTX
)
1106 pressure_class
= GENERAL_REGS
;
1109 pressure_class
= reg_allocno_class (REGNO (reg
));
1110 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1113 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1115 return pressure_class
;
1118 /* Calculates cost and number of registers needed for moving invariant INV
1119 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1120 the REG_CLASS of INV. Return
1121 -1: if INV is invalid.
1122 0: if INV and its depends_on have same reg_class
1123 1: if INV and its depends_on have different reg_classes. */
1126 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1130 unsigned aregs_needed
[N_REG_CLASSES
];
1132 struct invariant
*dep
;
1136 /* Find the representative of the class of the equivalent invariants. */
1137 inv
= invariants
[inv
->eqto
];
1140 if (! flag_ira_loop_pressure
)
1144 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1145 regs_needed
[ira_pressure_classes
[i
]] = 0;
1149 || inv
->stamp
== actual_stamp
)
1151 inv
->stamp
= actual_stamp
;
1153 if (! flag_ira_loop_pressure
)
1158 enum reg_class pressure_class
;
1160 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1161 regs_needed
[pressure_class
] += nregs
;
1162 *cl
= pressure_class
;
1166 if (!inv
->cheap_address
1167 || inv
->def
->n_uses
== 0
1168 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1169 (*comp_cost
) += inv
->cost
* inv
->eqno
;
1173 /* Hoisting constant pool constants into stack regs may cost more than
1174 just single register. On x87, the balance is affected both by the
1175 small number of FP registers, and by its register stack organization,
1176 that forces us to add compensation code in and around the loop to
1177 shuffle the operands to the top of stack before use, and pop them
1178 from the stack after the loop finishes.
1180 To model this effect, we increase the number of registers needed for
1181 stack registers by two: one register push, and one register pop.
1182 This usually has the effect that FP constant loads from the constant
1183 pool are not moved out of the loop.
1185 Note that this also means that dependent invariants can not be moved.
1186 However, the primary purpose of this pass is to move loop invariant
1187 address arithmetic out of loops, and address arithmetic that depends
1188 on floating point constants is unlikely to ever occur. */
1189 rtx set
= single_set (inv
->insn
);
1191 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1192 && constant_pool_constant_p (SET_SRC (set
)))
1194 if (flag_ira_loop_pressure
)
1195 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1197 regs_needed
[0] += 2;
1202 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1205 enum reg_class dep_cl
= ALL_REGS
;
1208 dep
= invariants
[depno
];
1210 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1214 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1216 if (! flag_ira_loop_pressure
)
1217 check_p
= aregs_needed
[0] != 0;
1220 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1221 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1223 check_p
= i
< ira_pressure_classes_num
;
1225 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1232 /* We need to check always_executed, since if the original value of
1233 the invariant may be preserved, we may need to keep it in a
1234 separate register. TODO check whether the register has an
1235 use outside of the loop. */
1236 && dep
->always_executed
1237 && !dep
->def
->uses
->next
)
1239 /* If this is a single use, after moving the dependency we will not
1240 need a new register. */
1241 if (! flag_ira_loop_pressure
)
1246 enum reg_class pressure_class
;
1248 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1249 aregs_needed
[pressure_class
] -= nregs
;
1253 if (! flag_ira_loop_pressure
)
1254 regs_needed
[0] += aregs_needed
[0];
1257 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1258 regs_needed
[ira_pressure_classes
[i
]]
1259 += aregs_needed
[ira_pressure_classes
[i
]];
1261 (*comp_cost
) += acomp_cost
;
1266 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1267 of registers used in the loop, NEW_REGS is the number of new variables
1268 already added due to the invariant motion. The number of registers needed
1269 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1270 through to estimate_reg_pressure_cost. */
1273 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1274 unsigned *new_regs
, unsigned regs_used
,
1275 bool speed
, bool call_p
)
1277 int comp_cost
, size_cost
;
1278 /* Workaround -Wmaybe-uninitialized false positive during
1279 profiledbootstrap by initializing it. */
1280 enum reg_class cl
= NO_REGS
;
1285 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1287 if (! flag_ira_loop_pressure
)
1289 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1290 regs_used
, speed
, call_p
)
1291 - estimate_reg_pressure_cost (new_regs
[0],
1292 regs_used
, speed
, call_p
));
1296 else if ((ret
== 0) && (cl
== NO_REGS
))
1297 /* Hoist it anyway since it does not impact register pressure. */
1302 enum reg_class pressure_class
;
1304 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1306 pressure_class
= ira_pressure_classes
[i
];
1308 if (!reg_classes_intersect_p (pressure_class
, cl
))
1311 if ((int) new_regs
[pressure_class
]
1312 + (int) regs_needed
[pressure_class
]
1313 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1314 + IRA_LOOP_RESERVED_REGS
1315 > ira_class_hard_regs_num
[pressure_class
])
1318 if (i
< ira_pressure_classes_num
)
1319 /* There will be register pressure excess and we want not to
1320 make this loop invariant motion. All loop invariants with
1321 non-positive gains will be rejected in function
1322 find_invariants_to_move. Therefore we return the negative
1325 One could think that this rejects also expensive loop
1326 invariant motions and this will hurt code performance.
1327 However numerous experiments with different heuristics
1328 taking invariant cost into account did not confirm this
1329 assumption. There are possible explanations for this
1331 o probably all expensive invariants were already moved out
1332 of the loop by PRE and gimple invariant motion pass.
1333 o expensive invariant execution will be hidden by insn
1334 scheduling or OOO processor hardware because usually such
1335 invariants have a lot of freedom to be executed
1337 Another reason for ignoring invariant cost vs spilling cost
1338 heuristics is also in difficulties to evaluate accurately
1339 spill cost at this stage. */
1345 return comp_cost
- size_cost
;
1348 /* Finds invariant with best gain for moving. Returns the gain, stores
1349 the invariant in *BEST and number of registers needed for it to
1350 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1351 NEW_REGS is the number of new variables already added due to invariant
1355 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1356 unsigned *new_regs
, unsigned regs_used
,
1357 bool speed
, bool call_p
)
1359 struct invariant
*inv
;
1360 int i
, gain
= 0, again
;
1361 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1363 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1368 /* Only consider the "representatives" of equivalent invariants. */
1369 if (inv
->eqto
!= inv
->invno
)
1372 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1378 if (! flag_ira_loop_pressure
)
1379 regs_needed
[0] = aregs_needed
[0];
1382 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1383 regs_needed
[ira_pressure_classes
[i
]]
1384 = aregs_needed
[ira_pressure_classes
[i
]];
1392 /* Marks invariant INVNO and all its dependencies for moving. */
1395 set_move_mark (unsigned invno
, int gain
)
1397 struct invariant
*inv
= invariants
[invno
];
1400 /* Find the representative of the class of the equivalent invariants. */
1401 inv
= invariants
[inv
->eqto
];
1410 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1413 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1417 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1419 set_move_mark (invno
, -1);
1423 /* Determines which invariants to move. */
1426 find_invariants_to_move (bool speed
, bool call_p
)
1429 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1430 struct invariant
*inv
= NULL
;
1432 if (!invariants
.length ())
1435 if (flag_ira_loop_pressure
)
1436 /* REGS_USED is actually never used when the flag is on. */
1439 /* We do not really do a good job in estimating number of
1440 registers used; we put some initial bound here to stand for
1441 induction variables etc. that we do not detect. */
1443 unsigned int n_regs
= DF_REG_SIZE (df
);
1447 for (i
= 0; i
< n_regs
; i
++)
1449 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1451 /* This is a value that is used but not changed inside loop. */
1457 if (! flag_ira_loop_pressure
)
1458 new_regs
[0] = regs_needed
[0] = 0;
1461 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1462 new_regs
[ira_pressure_classes
[i
]] = 0;
1464 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1465 new_regs
, regs_used
,
1466 speed
, call_p
)) > 0)
1468 set_move_mark (inv
->invno
, gain
);
1469 if (! flag_ira_loop_pressure
)
1470 new_regs
[0] += regs_needed
[0];
1473 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1474 new_regs
[ira_pressure_classes
[i
]]
1475 += regs_needed
[ira_pressure_classes
[i
]];
1480 /* Replace the uses, reached by the definition of invariant INV, by REG.
1482 IN_GROUP is nonzero if this is part of a group of changes that must be
1483 performed as a group. In that case, the changes will be stored. The
1484 function `apply_change_group' will validate and apply the changes. */
1487 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1489 /* Replace the uses we know to be dominated. It saves work for copy
1490 propagation, and also it is necessary so that dependent invariants
1491 are computed right. */
1495 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1496 validate_change (use
->insn
, use
->pos
, reg
, true);
1498 /* If we aren't part of a larger group, apply the changes now. */
1500 return apply_change_group ();
1506 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1507 the block preceding its header. */
1510 can_move_invariant_reg (struct loop
*loop
, struct invariant
*inv
, rtx reg
)
1513 unsigned int dest_regno
, defs_in_loop_count
= 0;
1514 rtx_insn
*insn
= inv
->insn
;
1515 basic_block bb
= BLOCK_FOR_INSN (inv
->insn
);
1517 /* We ignore hard register and memory access for cost and complexity reasons.
1518 Hard register are few at this stage and expensive to consider as they
1519 require building a separate data flow. Memory access would require using
1520 df_simulate_* and can_move_insns_across functions and is more complex. */
1521 if (!REG_P (reg
) || HARD_REGISTER_P (reg
))
1524 /* Check whether the set is always executed. We could omit this condition if
1525 we know that the register is unused outside of the loop, but it does not
1526 seem worth finding out. */
1527 if (!inv
->always_executed
)
1530 /* Check that all uses that would be dominated by def are already dominated
1532 dest_regno
= REGNO (reg
);
1533 for (use
= DF_REG_USE_CHAIN (dest_regno
); use
; use
= DF_REF_NEXT_REG (use
))
1538 use_insn
= DF_REF_INSN (use
);
1539 use_bb
= BLOCK_FOR_INSN (use_insn
);
1541 /* Ignore instruction considered for moving. */
1542 if (use_insn
== insn
)
1545 /* Don't consider uses outside loop. */
1546 if (!flow_bb_inside_loop_p (loop
, use_bb
))
1549 /* Don't move if a use is not dominated by def in insn. */
1550 if (use_bb
== bb
&& DF_INSN_LUID (insn
) >= DF_INSN_LUID (use_insn
))
1552 if (!dominated_by_p (CDI_DOMINATORS
, use_bb
, bb
))
1556 /* Check for other defs. Any other def in the loop might reach a use
1557 currently reached by the def in insn. */
1558 for (def
= DF_REG_DEF_CHAIN (dest_regno
); def
; def
= DF_REF_NEXT_REG (def
))
1560 basic_block def_bb
= DF_REF_BB (def
);
1562 /* Defs in exit block cannot reach a use they weren't already. */
1563 if (single_succ_p (def_bb
))
1565 basic_block def_bb_succ
;
1567 def_bb_succ
= single_succ (def_bb
);
1568 if (!flow_bb_inside_loop_p (loop
, def_bb_succ
))
1572 if (++defs_in_loop_count
> 1)
1579 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1583 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1585 struct invariant
*inv
= invariants
[invno
];
1586 struct invariant
*repr
= invariants
[inv
->eqto
];
1588 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1589 rtx reg
, set
, dest
, note
;
1598 /* If this is a representative of the class of equivalent invariants,
1599 really move the invariant. Otherwise just replace its use with
1600 the register used for the representative. */
1603 if (inv
->depends_on
)
1605 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1607 if (!move_invariant_reg (loop
, i
))
1612 /* If possible, just move the set out of the loop. Otherwise, we
1613 need to create a temporary register. */
1614 set
= single_set (inv
->insn
);
1615 reg
= dest
= SET_DEST (set
);
1616 if (GET_CODE (reg
) == SUBREG
)
1617 reg
= SUBREG_REG (reg
);
1619 regno
= REGNO (reg
);
1621 if (!can_move_invariant_reg (loop
, inv
, dest
))
1623 reg
= gen_reg_rtx_and_attrs (dest
);
1625 /* Try replacing the destination by a new pseudoregister. */
1626 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1628 /* As well as all the dominated uses. */
1629 replace_uses (inv
, reg
, true);
1631 /* And validate all the changes. */
1632 if (!apply_change_group ())
1635 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1638 fprintf (dump_file
, "Invariant %d moved without introducing a new "
1639 "temporary register\n", invno
);
1640 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1642 /* If there is a REG_EQUAL note on the insn we just moved, and the
1643 insn is in a basic block that is not always executed or the note
1644 contains something for which we don't know the invariant status,
1645 the note may no longer be valid after we move the insn. Note that
1646 uses in REG_EQUAL notes are taken into account in the computation
1647 of invariants, so it is safe to retain the note even if it contains
1648 register references for which we know the invariant status. */
1649 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1650 && (!inv
->always_executed
1651 || !check_maybe_invariant (XEXP (note
, 0))))
1652 remove_note (inv
->insn
, note
);
1656 if (!move_invariant_reg (loop
, repr
->invno
))
1659 regno
= repr
->orig_regno
;
1660 if (!replace_uses (inv
, reg
, false))
1662 set
= single_set (inv
->insn
);
1663 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1664 delete_insn (inv
->insn
);
1668 inv
->orig_regno
= regno
;
1673 /* If we failed, clear move flag, so that we do not try to move inv
1676 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1678 inv
->reg
= NULL_RTX
;
1679 inv
->orig_regno
= -1;
1684 /* Move selected invariant out of the LOOP. Newly created regs are marked
1685 in TEMPORARY_REGS. */
1688 move_invariants (struct loop
*loop
)
1690 struct invariant
*inv
;
1693 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1694 move_invariant_reg (loop
, i
);
1695 if (flag_ira_loop_pressure
&& resize_reg_info ())
1697 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1698 if (inv
->reg
!= NULL_RTX
)
1700 if (inv
->orig_regno
>= 0)
1701 setup_reg_classes (REGNO (inv
->reg
),
1702 reg_preferred_class (inv
->orig_regno
),
1703 reg_alternate_class (inv
->orig_regno
),
1704 reg_allocno_class (inv
->orig_regno
));
1706 setup_reg_classes (REGNO (inv
->reg
),
1707 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1712 /* Initializes invariant motion data. */
1715 init_inv_motion_data (void)
1719 invariants
.create (100);
1722 /* Frees the data allocated by invariant motion. */
1725 free_inv_motion_data (void)
1729 struct invariant
*inv
;
1731 check_invariant_table_size ();
1732 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1734 inv
= invariant_table
[i
];
1738 gcc_assert (def
!= NULL
);
1740 free_use_list (def
->uses
);
1742 invariant_table
[i
] = NULL
;
1746 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1748 BITMAP_FREE (inv
->depends_on
);
1751 invariants
.release ();
1754 /* Move the invariants out of the LOOP. */
1757 move_single_loop_invariants (struct loop
*loop
)
1759 init_inv_motion_data ();
1761 find_invariants (loop
);
1762 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1763 LOOP_DATA (loop
)->has_call
);
1764 move_invariants (loop
);
1766 free_inv_motion_data ();
1769 /* Releases the auxiliary data for LOOP. */
1772 free_loop_data (struct loop
*loop
)
1774 struct loop_data
*data
= LOOP_DATA (loop
);
1778 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1779 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1786 /* Registers currently living. */
1787 static bitmap_head curr_regs_live
;
1789 /* Current reg pressure for each pressure class. */
1790 static int curr_reg_pressure
[N_REG_CLASSES
];
1792 /* Record all regs that are set in any one insn. Communication from
1793 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1794 all hard-registers. */
1795 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1796 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1797 /* Number of regs stored in the previous array. */
1798 static int n_regs_set
;
1800 /* Return pressure class and number of needed hard registers (through
1801 *NREGS) of register REGNO. */
1802 static enum reg_class
1803 get_regno_pressure_class (int regno
, int *nregs
)
1805 if (regno
>= FIRST_PSEUDO_REGISTER
)
1807 enum reg_class pressure_class
;
1809 pressure_class
= reg_allocno_class (regno
);
1810 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1812 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1813 return pressure_class
;
1815 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1816 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1819 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1828 /* Increase (if INCR_P) or decrease current register pressure for
1831 change_pressure (int regno
, bool incr_p
)
1834 enum reg_class pressure_class
;
1836 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1838 curr_reg_pressure
[pressure_class
] -= nregs
;
1841 curr_reg_pressure
[pressure_class
] += nregs
;
1842 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1843 < curr_reg_pressure
[pressure_class
])
1844 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1845 = curr_reg_pressure
[pressure_class
];
1849 /* Mark REGNO birth. */
1851 mark_regno_live (int regno
)
1855 for (loop
= curr_loop
;
1856 loop
!= current_loops
->tree_root
;
1857 loop
= loop_outer (loop
))
1858 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1859 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1861 change_pressure (regno
, true);
1864 /* Mark REGNO death. */
1866 mark_regno_death (int regno
)
1868 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1870 change_pressure (regno
, false);
1873 /* Mark setting register REG. */
1875 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1876 void *data ATTRIBUTE_UNUSED
)
1878 if (GET_CODE (reg
) == SUBREG
)
1879 reg
= SUBREG_REG (reg
);
1884 regs_set
[n_regs_set
++] = reg
;
1886 unsigned int end_regno
= END_REGNO (reg
);
1887 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1888 mark_regno_live (regno
);
1891 /* Mark clobbering register REG. */
1893 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1895 if (GET_CODE (setter
) == CLOBBER
)
1896 mark_reg_store (reg
, setter
, data
);
1899 /* Mark register REG death. */
1901 mark_reg_death (rtx reg
)
1903 unsigned int end_regno
= END_REGNO (reg
);
1904 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1905 mark_regno_death (regno
);
1908 /* Mark occurrence of registers in X for the current loop. */
1910 mark_ref_regs (rtx x
)
1919 code
= GET_CODE (x
);
1924 for (loop
= curr_loop
;
1925 loop
!= current_loops
->tree_root
;
1926 loop
= loop_outer (loop
))
1927 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1931 fmt
= GET_RTX_FORMAT (code
);
1932 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1934 mark_ref_regs (XEXP (x
, i
));
1935 else if (fmt
[i
] == 'E')
1939 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1940 mark_ref_regs (XVECEXP (x
, i
, j
));
1944 /* Calculate register pressure in the loops. */
1946 calculate_loop_reg_pressure (void)
1954 struct loop
*loop
, *parent
;
1956 FOR_EACH_LOOP (loop
, 0)
1957 if (loop
->aux
== NULL
)
1959 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1960 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1961 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1963 ira_setup_eliminable_regset ();
1964 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1965 FOR_EACH_BB_FN (bb
, cfun
)
1967 curr_loop
= bb
->loop_father
;
1968 if (curr_loop
== current_loops
->tree_root
)
1971 for (loop
= curr_loop
;
1972 loop
!= current_loops
->tree_root
;
1973 loop
= loop_outer (loop
))
1974 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1976 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1977 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1978 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1979 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1980 change_pressure (j
, true);
1982 FOR_BB_INSNS (bb
, insn
)
1984 if (! NONDEBUG_INSN_P (insn
))
1987 mark_ref_regs (PATTERN (insn
));
1989 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1991 /* Mark any registers dead after INSN as dead now. */
1993 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1994 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1995 mark_reg_death (XEXP (link
, 0));
1997 /* Mark any registers set in INSN as live,
1998 and mark them as conflicting with all other live regs.
1999 Clobbers are processed again, so they conflict with
2000 the registers that are set. */
2002 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
2005 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2006 if (REG_NOTE_KIND (link
) == REG_INC
)
2007 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
2009 while (n_regs_set
-- > 0)
2011 rtx note
= find_regno_note (insn
, REG_UNUSED
,
2012 REGNO (regs_set
[n_regs_set
]));
2016 mark_reg_death (XEXP (note
, 0));
2020 bitmap_clear (&curr_regs_live
);
2021 if (flag_ira_region
== IRA_REGION_MIXED
2022 || flag_ira_region
== IRA_REGION_ALL
)
2023 FOR_EACH_LOOP (loop
, 0)
2025 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2026 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
2028 enum reg_class pressure_class
;
2031 pressure_class
= get_regno_pressure_class (j
, &nregs
);
2032 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
2035 if (dump_file
== NULL
)
2037 FOR_EACH_LOOP (loop
, 0)
2039 parent
= loop_outer (loop
);
2040 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2041 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
2042 loop
->header
->index
, loop_depth (loop
));
2043 fprintf (dump_file
, "\n ref. regnos:");
2044 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
2045 fprintf (dump_file
, " %d", j
);
2046 fprintf (dump_file
, "\n live regnos:");
2047 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2048 fprintf (dump_file
, " %d", j
);
2049 fprintf (dump_file
, "\n Pressure:");
2050 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
2052 enum reg_class pressure_class
;
2054 pressure_class
= ira_pressure_classes
[i
];
2055 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
2057 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
2058 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
2060 fprintf (dump_file
, "\n");
2066 /* Move the invariants out of the loops. */
2069 move_loop_invariants (void)
2073 if (flag_ira_loop_pressure
)
2076 regstat_init_n_sets_and_refs ();
2077 ira_set_pseudo_classes (true, dump_file
);
2078 calculate_loop_reg_pressure ();
2079 regstat_free_n_sets_and_refs ();
2081 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
2082 /* Process the loops, innermost first. */
2083 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2086 /* move_single_loop_invariants for very large loops
2087 is time consuming and might need a lot of memory. */
2088 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2089 move_single_loop_invariants (loop
);
2092 FOR_EACH_LOOP (loop
, 0)
2094 free_loop_data (loop
);
2097 if (flag_ira_loop_pressure
)
2098 /* There is no sense to keep this info because it was most
2099 probably outdated by subsequent passes. */
2101 free (invariant_table
);
2102 invariant_table
= NULL
;
2103 invariant_table_size
= 0;
2105 #ifdef ENABLE_CHECKING
2106 verify_flow_info ();