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"
51 #include "dominance.h"
54 #include "basic-block.h"
58 #include "statistics.h"
62 #include "insn-config.h"
74 #include "hash-table.h"
81 /* The data stored for the loop. */
85 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
86 bool has_call
; /* True if the loop contains a call. */
87 /* Maximal register pressure inside loop for given register class
88 (defined only for the pressure classes). */
89 int max_reg_pressure
[N_REG_CLASSES
];
90 /* Loop regs referenced and live pseudo-registers. */
92 bitmap_head regs_live
;
95 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
97 /* The description of an use. */
101 rtx
*pos
; /* Position of the use. */
102 rtx_insn
*insn
; /* The insn in that the use occurs. */
103 unsigned addr_use_p
; /* Whether the use occurs in an address. */
104 struct use
*next
; /* Next use in the list. */
107 /* The description of a def. */
111 struct use
*uses
; /* The list of uses that are uniquely reached
113 unsigned n_uses
; /* Number of such uses. */
114 unsigned n_addr_uses
; /* Number of uses in addresses. */
115 unsigned invno
; /* The corresponding invariant. */
118 /* The data stored for each invariant. */
122 /* The number of the invariant. */
125 /* The number of the invariant with the same value. */
128 /* The number of invariants which eqto this. */
131 /* If we moved the invariant out of the loop, the register that contains its
135 /* If we moved the invariant out of the loop, the original regno
136 that contained its value. */
139 /* The definition of the invariant. */
142 /* The insn in that it is defined. */
145 /* Whether it is always executed. */
146 bool always_executed
;
148 /* Whether to move the invariant. */
151 /* Whether the invariant is cheap when used as an address. */
154 /* Cost of the invariant. */
157 /* The invariants it depends on. */
160 /* Used for detecting already visited invariants during determining
161 costs of movements. */
165 /* Currently processed loop. */
166 static struct loop
*curr_loop
;
168 /* Table of invariants indexed by the df_ref uid field. */
170 static unsigned int invariant_table_size
= 0;
171 static struct invariant
** invariant_table
;
173 /* Entry for hash table of invariant expressions. */
175 struct invariant_expr_entry
178 struct invariant
*inv
;
190 /* The actual stamp for marking already visited invariants during determining
191 costs of movements. */
193 static unsigned actual_stamp
;
195 typedef struct invariant
*invariant_p
;
198 /* The invariants. */
200 static vec
<invariant_p
> invariants
;
202 /* Check the size of the invariant table and realloc if necessary. */
205 check_invariant_table_size (void)
207 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
209 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
210 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
211 memset (&invariant_table
[invariant_table_size
], 0,
212 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
213 invariant_table_size
= new_size
;
217 /* Test for possibility of invariantness of X. */
220 check_maybe_invariant (rtx x
)
222 enum rtx_code code
= GET_CODE (x
);
236 case UNSPEC_VOLATILE
:
244 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
245 It should not be hard, and might be faster than "elsewhere". */
247 /* Just handle the most trivial case where we load from an unchanging
248 location (most importantly, pic tables). */
249 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
255 /* Don't mess with insns declared volatile. */
256 if (MEM_VOLATILE_P (x
))
264 fmt
= GET_RTX_FORMAT (code
);
265 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
269 if (!check_maybe_invariant (XEXP (x
, i
)))
272 else if (fmt
[i
] == 'E')
274 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
275 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
283 /* Returns the invariant definition for USE, or NULL if USE is not
286 static struct invariant
*
287 invariant_for_use (df_ref use
)
289 struct df_link
*defs
;
291 basic_block bb
= DF_REF_BB (use
), def_bb
;
293 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
296 defs
= DF_REF_CHAIN (use
);
297 if (!defs
|| defs
->next
)
300 check_invariant_table_size ();
301 if (!invariant_table
[DF_REF_ID (def
)])
304 def_bb
= DF_REF_BB (def
);
305 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
307 return invariant_table
[DF_REF_ID (def
)];
310 /* Computes hash value for invariant expression X in INSN. */
313 hash_invariant_expr_1 (rtx_insn
*insn
, rtx x
)
315 enum rtx_code code
= GET_CODE (x
);
318 hashval_t val
= code
;
321 struct invariant
*inv
;
329 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
332 use
= df_find_use (insn
, x
);
334 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
335 inv
= invariant_for_use (use
);
337 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
339 gcc_assert (inv
->eqto
!= ~0u);
346 fmt
= GET_RTX_FORMAT (code
);
347 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
350 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
351 else if (fmt
[i
] == 'E')
353 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
354 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
356 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
363 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
364 and INSN2 have always the same value. */
367 invariant_expr_equal_p (rtx_insn
*insn1
, rtx e1
, rtx_insn
*insn2
, rtx e2
)
369 enum rtx_code code
= GET_CODE (e1
);
373 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
376 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
377 the other one. If both are VOIDmode, we rely on the caller of this
378 function to verify that their modes are the same. */
379 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
388 return rtx_equal_p (e1
, e2
);
391 use1
= df_find_use (insn1
, e1
);
392 use2
= df_find_use (insn2
, e2
);
394 inv1
= invariant_for_use (use1
);
396 inv2
= invariant_for_use (use2
);
399 return rtx_equal_p (e1
, e2
);
404 gcc_assert (inv1
->eqto
!= ~0u);
405 gcc_assert (inv2
->eqto
!= ~0u);
406 return inv1
->eqto
== inv2
->eqto
;
412 fmt
= GET_RTX_FORMAT (code
);
413 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
420 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
424 else if (fmt
[i
] == 'E')
426 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
429 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
431 sub1
= XVECEXP (e1
, i
, j
);
432 sub2
= XVECEXP (e2
, i
, j
);
434 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
438 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
440 if (XINT (e1
, i
) != XINT (e2
, i
))
443 /* Unhandled type of subexpression, we fail conservatively. */
451 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
453 typedef invariant_expr_entry
*value_type
;
454 typedef invariant_expr_entry
*compare_type
;
455 static inline hashval_t
hash (const invariant_expr_entry
*);
456 static inline bool equal (const invariant_expr_entry
*,
457 const invariant_expr_entry
*);
460 /* Returns hash value for invariant expression entry ENTRY. */
463 invariant_expr_hasher::hash (const invariant_expr_entry
*entry
)
468 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
471 invariant_expr_hasher::equal (const invariant_expr_entry
*entry1
,
472 const invariant_expr_entry
*entry2
)
474 if (entry1
->mode
!= entry2
->mode
)
477 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
478 entry2
->inv
->insn
, entry2
->expr
);
481 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
483 /* Checks whether invariant with value EXPR in machine mode MODE is
484 recorded in EQ. If this is the case, return the invariant. Otherwise
485 insert INV to the table for this expression and return INV. */
487 static struct invariant
*
488 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, machine_mode mode
,
489 struct invariant
*inv
)
491 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
492 struct invariant_expr_entry
*entry
;
493 struct invariant_expr_entry pentry
;
494 invariant_expr_entry
**slot
;
499 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
505 entry
= XNEW (struct invariant_expr_entry
);
515 /* Finds invariants identical to INV and records the equivalence. EQ is the
516 hash table of the invariants. */
519 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
523 struct invariant
*dep
;
526 struct invariant
*tmp
;
528 if (inv
->eqto
!= ~0u)
531 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
533 dep
= invariants
[depno
];
534 find_identical_invariants (eq
, dep
);
537 set
= single_set (inv
->insn
);
538 expr
= SET_SRC (set
);
539 mode
= GET_MODE (expr
);
540 if (mode
== VOIDmode
)
541 mode
= GET_MODE (SET_DEST (set
));
543 tmp
= find_or_insert_inv (eq
, expr
, mode
, inv
);
544 inv
->eqto
= tmp
->invno
;
546 if (tmp
->invno
!= inv
->invno
&& inv
->always_executed
)
549 if (dump_file
&& inv
->eqto
!= inv
->invno
)
551 "Invariant %d is equivalent to invariant %d.\n",
552 inv
->invno
, inv
->eqto
);
555 /* Find invariants with the same value and record the equivalences. */
558 merge_identical_invariants (void)
561 struct invariant
*inv
;
562 invariant_htab_type
eq (invariants
.length ());
564 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
565 find_identical_invariants (&eq
, inv
);
568 /* Determines the basic blocks inside LOOP that are always executed and
569 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
570 basic blocks that may either exit the loop, or contain the call that
571 does not have to return. BODY is body of the loop obtained by
572 get_loop_body_in_dom_order. */
575 compute_always_reached (struct loop
*loop
, basic_block
*body
,
576 bitmap may_exit
, bitmap always_reached
)
580 for (i
= 0; i
< loop
->num_nodes
; i
++)
582 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
583 bitmap_set_bit (always_reached
, i
);
585 if (bitmap_bit_p (may_exit
, i
))
590 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
591 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
592 additionally mark blocks that may exit due to a call. */
595 find_exits (struct loop
*loop
, basic_block
*body
,
596 bitmap may_exit
, bitmap has_exit
)
601 struct loop
*outermost_exit
= loop
, *aexit
;
602 bool has_call
= false;
605 for (i
= 0; i
< loop
->num_nodes
; i
++)
607 if (body
[i
]->loop_father
== loop
)
609 FOR_BB_INSNS (body
[i
], insn
)
612 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
613 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
616 bitmap_set_bit (may_exit
, i
);
621 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
623 if (flow_bb_inside_loop_p (loop
, e
->dest
))
626 bitmap_set_bit (may_exit
, i
);
627 bitmap_set_bit (has_exit
, i
);
628 outermost_exit
= find_common_loop (outermost_exit
,
629 e
->dest
->loop_father
);
634 /* Use the data stored for the subloop to decide whether we may exit
635 through it. It is sufficient to do this for header of the loop,
636 as other basic blocks inside it must be dominated by it. */
637 if (body
[i
]->loop_father
->header
!= body
[i
])
640 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
643 bitmap_set_bit (may_exit
, i
);
645 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
648 bitmap_set_bit (may_exit
, i
);
649 bitmap_set_bit (has_exit
, i
);
651 if (flow_loop_nested_p (aexit
, outermost_exit
))
652 outermost_exit
= aexit
;
656 if (loop
->aux
== NULL
)
658 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
659 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
660 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
662 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
663 LOOP_DATA (loop
)->has_call
= has_call
;
666 /* Check whether we may assign a value to X from a register. */
669 may_assign_reg_p (rtx x
)
671 return (GET_MODE (x
) != VOIDmode
672 && GET_MODE (x
) != BLKmode
673 && can_copy_p (GET_MODE (x
))
675 || !HARD_REGISTER_P (x
)
676 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
679 /* Finds definitions that may correspond to invariants in LOOP with body
683 find_defs (struct loop
*loop
)
688 "*****starting processing of loop %d ******\n",
692 df_remove_problem (df_chain
);
693 df_process_deferred_rescans ();
694 df_chain_add_problem (DF_UD_CHAIN
);
695 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
696 df_analyze_loop (loop
);
697 check_invariant_table_size ();
701 df_dump_region (dump_file
);
703 "*****ending processing of loop %d ******\n",
708 /* Creates a new invariant for definition DEF in INSN, depending on invariants
709 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
710 unless the program ends due to a function call. The newly created invariant
713 static struct invariant
*
714 create_new_invariant (struct def
*def
, rtx_insn
*insn
, bitmap depends_on
,
715 bool always_executed
)
717 struct invariant
*inv
= XNEW (struct invariant
);
718 rtx set
= single_set (insn
);
719 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
722 inv
->always_executed
= always_executed
;
723 inv
->depends_on
= depends_on
;
725 /* If the set is simple, usually by moving it we move the whole store out of
726 the loop. Otherwise we save only cost of the computation. */
729 inv
->cost
= set_rtx_cost (set
, speed
);
730 /* ??? Try to determine cheapness of address computation. Unfortunately
731 the address cost is only a relative measure, we can't really compare
732 it with any absolute number, but only with other address costs.
733 But here we don't have any other addresses, so compare with a magic
734 number anyway. It has to be large enough to not regress PR33928
735 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
736 enough to not regress 410.bwaves either (by still moving reg+reg
738 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
739 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set
))))
740 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
741 ADDR_SPACE_GENERIC
, speed
) < 3;
743 inv
->cheap_address
= false;
747 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
748 inv
->cheap_address
= false;
753 inv
->orig_regno
= -1;
757 inv
->invno
= invariants
.length ();
764 def
->invno
= inv
->invno
;
765 invariants
.safe_push (inv
);
770 "Set in insn %d is invariant (%d), cost %d, depends on ",
771 INSN_UID (insn
), inv
->invno
, inv
->cost
);
772 dump_bitmap (dump_file
, inv
->depends_on
);
778 /* Record USE at DEF. */
781 record_use (struct def
*def
, df_ref use
)
783 struct use
*u
= XNEW (struct use
);
785 u
->pos
= DF_REF_REAL_LOC (use
);
786 u
->insn
= DF_REF_INSN (use
);
787 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
788 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
796 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
797 bitmap. Returns true if all dependencies of USE are known to be
798 loop invariants, false otherwise. */
801 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
805 struct df_link
*defs
;
806 struct def
*def_data
;
807 struct invariant
*inv
;
809 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
812 defs
= DF_REF_CHAIN (use
);
815 unsigned int regno
= DF_REF_REGNO (use
);
817 /* If this is the use of an uninitialized argument register that is
818 likely to be spilled, do not move it lest this might extend its
819 lifetime and cause reload to die. This can occur for a call to
820 a function taking complex number arguments and moving the insns
821 preparing the arguments without moving the call itself wouldn't
822 gain much in practice. */
823 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
824 && FUNCTION_ARG_REGNO_P (regno
)
825 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
835 check_invariant_table_size ();
836 inv
= invariant_table
[DF_REF_ID (def
)];
841 gcc_assert (def_data
!= NULL
);
843 def_bb
= DF_REF_BB (def
);
844 /* Note that in case bb == def_bb, we know that the definition
845 dominates insn, because def has invariant_table[DF_REF_ID(def)]
846 defined and we process the insns in the basic block bb
848 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
851 bitmap_set_bit (depends_on
, def_data
->invno
);
856 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
857 bitmap. Returns true if all dependencies of INSN are known to be
858 loop invariants, false otherwise. */
861 check_dependencies (rtx_insn
*insn
, bitmap depends_on
)
863 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
865 basic_block bb
= BLOCK_FOR_INSN (insn
);
867 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
868 if (!check_dependency (bb
, use
, depends_on
))
870 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
871 if (!check_dependency (bb
, use
, depends_on
))
877 /* Pre-check candidate DEST to skip the one which can not make a valid insn
878 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
880 pre_check_invariant_p (bool simple
, rtx dest
)
882 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
885 unsigned int i
= REGNO (dest
);
886 struct df_insn_info
*insn_info
;
889 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
891 rtx_insn
*ref
= DF_REF_INSN (use
);
892 insn_info
= DF_INSN_INFO_GET (ref
);
894 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
895 if (DF_REF_REGNO (def_rec
) == i
)
897 /* Multi definitions at this stage, most likely are due to
898 instruction constraints, which requires both read and write
899 on the same register. Since move_invariant_reg is not
900 powerful enough to handle such cases, just ignore the INV
901 and leave the chance to others. */
909 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
910 executed. ALWAYS_EXECUTED is true if the insn is always executed,
911 unless the program ends due to a function call. */
914 find_invariant_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
921 struct invariant
*inv
;
923 /* We can't move a CC0 setter without the user. */
924 if (HAVE_cc0
&& sets_cc0_p (insn
))
927 set
= single_set (insn
);
930 dest
= SET_DEST (set
);
933 || HARD_REGISTER_P (dest
))
936 if (!may_assign_reg_p (dest
)
937 || !pre_check_invariant_p (simple
, dest
)
938 || !check_maybe_invariant (SET_SRC (set
)))
941 /* If the insn can throw exception, we cannot move it at all without changing
943 if (can_throw_internal (insn
))
946 /* We cannot make trapping insn executed, unless it was executed before. */
947 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
950 depends_on
= BITMAP_ALLOC (NULL
);
951 if (!check_dependencies (insn
, depends_on
))
953 BITMAP_FREE (depends_on
);
958 def
= XCNEW (struct def
);
962 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
966 ref
= df_find_def (insn
, dest
);
967 check_invariant_table_size ();
968 invariant_table
[DF_REF_ID (ref
)] = inv
;
972 /* Record registers used in INSN that have a unique invariant definition. */
975 record_uses (rtx_insn
*insn
)
977 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
979 struct invariant
*inv
;
981 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
983 inv
= invariant_for_use (use
);
985 record_use (inv
->def
, use
);
987 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
989 inv
= invariant_for_use (use
);
991 record_use (inv
->def
, use
);
995 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
996 executed. ALWAYS_EXECUTED is true if the insn is always executed,
997 unless the program ends due to a function call. */
1000 find_invariants_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
1002 find_invariant_insn (insn
, always_reached
, always_executed
);
1006 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1007 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1008 block is always executed, unless the program ends due to a function
1012 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
1016 FOR_BB_INSNS (bb
, insn
)
1018 if (!NONDEBUG_INSN_P (insn
))
1021 find_invariants_insn (insn
, always_reached
, always_executed
);
1025 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1026 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
1027 always_reached
= false;
1031 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1032 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1033 bitmap of basic blocks in BODY that are always executed unless the program
1034 ends due to a function call. */
1037 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1038 bitmap always_reached
, bitmap always_executed
)
1042 for (i
= 0; i
< loop
->num_nodes
; i
++)
1043 find_invariants_bb (body
[i
],
1044 bitmap_bit_p (always_reached
, i
),
1045 bitmap_bit_p (always_executed
, i
));
1048 /* Finds invariants in LOOP. */
1051 find_invariants (struct loop
*loop
)
1053 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1054 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1055 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1056 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1057 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1059 find_exits (loop
, body
, may_exit
, has_exit
);
1060 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1061 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1064 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1065 merge_identical_invariants ();
1067 BITMAP_FREE (always_reached
);
1068 BITMAP_FREE (always_executed
);
1069 BITMAP_FREE (may_exit
);
1070 BITMAP_FREE (has_exit
);
1074 /* Frees a list of uses USE. */
1077 free_use_list (struct use
*use
)
1081 for (; use
; use
= next
)
1088 /* Return pressure class and number of hard registers (through *NREGS)
1089 for destination of INSN. */
1090 static enum reg_class
1091 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
1094 enum reg_class pressure_class
;
1095 rtx set
= single_set (insn
);
1097 /* Considered invariant insns have only one set. */
1098 gcc_assert (set
!= NULL_RTX
);
1099 reg
= SET_DEST (set
);
1100 if (GET_CODE (reg
) == SUBREG
)
1101 reg
= SUBREG_REG (reg
);
1105 pressure_class
= NO_REGS
;
1111 if (reg
== NULL_RTX
)
1112 pressure_class
= GENERAL_REGS
;
1115 pressure_class
= reg_allocno_class (REGNO (reg
));
1116 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1119 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1121 return pressure_class
;
1124 /* Calculates cost and number of registers needed for moving invariant INV
1125 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1126 the REG_CLASS of INV. Return
1127 -1: if INV is invalid.
1128 0: if INV and its depends_on have same reg_class
1129 1: if INV and its depends_on have different reg_classes. */
1132 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1136 unsigned aregs_needed
[N_REG_CLASSES
];
1138 struct invariant
*dep
;
1142 /* Find the representative of the class of the equivalent invariants. */
1143 inv
= invariants
[inv
->eqto
];
1146 if (! flag_ira_loop_pressure
)
1150 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1151 regs_needed
[ira_pressure_classes
[i
]] = 0;
1155 || inv
->stamp
== actual_stamp
)
1157 inv
->stamp
= actual_stamp
;
1159 if (! flag_ira_loop_pressure
)
1164 enum reg_class pressure_class
;
1166 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1167 regs_needed
[pressure_class
] += nregs
;
1168 *cl
= pressure_class
;
1172 if (!inv
->cheap_address
1173 || inv
->def
->n_uses
== 0
1174 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1175 (*comp_cost
) += inv
->cost
* inv
->eqno
;
1179 /* Hoisting constant pool constants into stack regs may cost more than
1180 just single register. On x87, the balance is affected both by the
1181 small number of FP registers, and by its register stack organization,
1182 that forces us to add compensation code in and around the loop to
1183 shuffle the operands to the top of stack before use, and pop them
1184 from the stack after the loop finishes.
1186 To model this effect, we increase the number of registers needed for
1187 stack registers by two: one register push, and one register pop.
1188 This usually has the effect that FP constant loads from the constant
1189 pool are not moved out of the loop.
1191 Note that this also means that dependent invariants can not be moved.
1192 However, the primary purpose of this pass is to move loop invariant
1193 address arithmetic out of loops, and address arithmetic that depends
1194 on floating point constants is unlikely to ever occur. */
1195 rtx set
= single_set (inv
->insn
);
1197 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1198 && constant_pool_constant_p (SET_SRC (set
)))
1200 if (flag_ira_loop_pressure
)
1201 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1203 regs_needed
[0] += 2;
1208 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1211 enum reg_class dep_cl
= ALL_REGS
;
1214 dep
= invariants
[depno
];
1216 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1220 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1222 if (! flag_ira_loop_pressure
)
1223 check_p
= aregs_needed
[0] != 0;
1226 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1227 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1229 check_p
= i
< ira_pressure_classes_num
;
1231 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1238 /* We need to check always_executed, since if the original value of
1239 the invariant may be preserved, we may need to keep it in a
1240 separate register. TODO check whether the register has an
1241 use outside of the loop. */
1242 && dep
->always_executed
1243 && !dep
->def
->uses
->next
)
1245 /* If this is a single use, after moving the dependency we will not
1246 need a new register. */
1247 if (! flag_ira_loop_pressure
)
1252 enum reg_class pressure_class
;
1254 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1255 aregs_needed
[pressure_class
] -= nregs
;
1259 if (! flag_ira_loop_pressure
)
1260 regs_needed
[0] += aregs_needed
[0];
1263 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1264 regs_needed
[ira_pressure_classes
[i
]]
1265 += aregs_needed
[ira_pressure_classes
[i
]];
1267 (*comp_cost
) += acomp_cost
;
1272 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1273 of registers used in the loop, NEW_REGS is the number of new variables
1274 already added due to the invariant motion. The number of registers needed
1275 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1276 through to estimate_reg_pressure_cost. */
1279 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1280 unsigned *new_regs
, unsigned regs_used
,
1281 bool speed
, bool call_p
)
1283 int comp_cost
, size_cost
;
1284 /* Workaround -Wmaybe-uninitialized false positive during
1285 profiledbootstrap by initializing it. */
1286 enum reg_class cl
= NO_REGS
;
1291 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1293 if (! flag_ira_loop_pressure
)
1295 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1296 regs_used
, speed
, call_p
)
1297 - estimate_reg_pressure_cost (new_regs
[0],
1298 regs_used
, speed
, call_p
));
1302 else if ((ret
== 0) && (cl
== NO_REGS
))
1303 /* Hoist it anyway since it does not impact register pressure. */
1308 enum reg_class pressure_class
;
1310 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1312 pressure_class
= ira_pressure_classes
[i
];
1314 if (!reg_classes_intersect_p (pressure_class
, cl
))
1317 if ((int) new_regs
[pressure_class
]
1318 + (int) regs_needed
[pressure_class
]
1319 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1320 + IRA_LOOP_RESERVED_REGS
1321 > ira_class_hard_regs_num
[pressure_class
])
1324 if (i
< ira_pressure_classes_num
)
1325 /* There will be register pressure excess and we want not to
1326 make this loop invariant motion. All loop invariants with
1327 non-positive gains will be rejected in function
1328 find_invariants_to_move. Therefore we return the negative
1331 One could think that this rejects also expensive loop
1332 invariant motions and this will hurt code performance.
1333 However numerous experiments with different heuristics
1334 taking invariant cost into account did not confirm this
1335 assumption. There are possible explanations for this
1337 o probably all expensive invariants were already moved out
1338 of the loop by PRE and gimple invariant motion pass.
1339 o expensive invariant execution will be hidden by insn
1340 scheduling or OOO processor hardware because usually such
1341 invariants have a lot of freedom to be executed
1343 Another reason for ignoring invariant cost vs spilling cost
1344 heuristics is also in difficulties to evaluate accurately
1345 spill cost at this stage. */
1351 return comp_cost
- size_cost
;
1354 /* Finds invariant with best gain for moving. Returns the gain, stores
1355 the invariant in *BEST and number of registers needed for it to
1356 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1357 NEW_REGS is the number of new variables already added due to invariant
1361 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1362 unsigned *new_regs
, unsigned regs_used
,
1363 bool speed
, bool call_p
)
1365 struct invariant
*inv
;
1366 int i
, gain
= 0, again
;
1367 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1369 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1374 /* Only consider the "representatives" of equivalent invariants. */
1375 if (inv
->eqto
!= inv
->invno
)
1378 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1384 if (! flag_ira_loop_pressure
)
1385 regs_needed
[0] = aregs_needed
[0];
1388 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1389 regs_needed
[ira_pressure_classes
[i
]]
1390 = aregs_needed
[ira_pressure_classes
[i
]];
1398 /* Marks invariant INVNO and all its dependencies for moving. */
1401 set_move_mark (unsigned invno
, int gain
)
1403 struct invariant
*inv
= invariants
[invno
];
1406 /* Find the representative of the class of the equivalent invariants. */
1407 inv
= invariants
[inv
->eqto
];
1416 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1419 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1423 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1425 set_move_mark (invno
, -1);
1429 /* Determines which invariants to move. */
1432 find_invariants_to_move (bool speed
, bool call_p
)
1435 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1436 struct invariant
*inv
= NULL
;
1438 if (!invariants
.length ())
1441 if (flag_ira_loop_pressure
)
1442 /* REGS_USED is actually never used when the flag is on. */
1445 /* We do not really do a good job in estimating number of
1446 registers used; we put some initial bound here to stand for
1447 induction variables etc. that we do not detect. */
1449 unsigned int n_regs
= DF_REG_SIZE (df
);
1453 for (i
= 0; i
< n_regs
; i
++)
1455 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1457 /* This is a value that is used but not changed inside loop. */
1463 if (! flag_ira_loop_pressure
)
1464 new_regs
[0] = regs_needed
[0] = 0;
1467 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1468 new_regs
[ira_pressure_classes
[i
]] = 0;
1470 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1471 new_regs
, regs_used
,
1472 speed
, call_p
)) > 0)
1474 set_move_mark (inv
->invno
, gain
);
1475 if (! flag_ira_loop_pressure
)
1476 new_regs
[0] += regs_needed
[0];
1479 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1480 new_regs
[ira_pressure_classes
[i
]]
1481 += regs_needed
[ira_pressure_classes
[i
]];
1486 /* Replace the uses, reached by the definition of invariant INV, by REG.
1488 IN_GROUP is nonzero if this is part of a group of changes that must be
1489 performed as a group. In that case, the changes will be stored. The
1490 function `apply_change_group' will validate and apply the changes. */
1493 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1495 /* Replace the uses we know to be dominated. It saves work for copy
1496 propagation, and also it is necessary so that dependent invariants
1497 are computed right. */
1501 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1502 validate_change (use
->insn
, use
->pos
, reg
, true);
1504 /* If we aren't part of a larger group, apply the changes now. */
1506 return apply_change_group ();
1512 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1513 the block preceding its header. */
1516 can_move_invariant_reg (struct loop
*loop
, struct invariant
*inv
, rtx reg
)
1519 unsigned int dest_regno
, defs_in_loop_count
= 0;
1520 rtx_insn
*insn
= inv
->insn
;
1521 basic_block bb
= BLOCK_FOR_INSN (inv
->insn
);
1523 /* We ignore hard register and memory access for cost and complexity reasons.
1524 Hard register are few at this stage and expensive to consider as they
1525 require building a separate data flow. Memory access would require using
1526 df_simulate_* and can_move_insns_across functions and is more complex. */
1527 if (!REG_P (reg
) || HARD_REGISTER_P (reg
))
1530 /* Check whether the set is always executed. We could omit this condition if
1531 we know that the register is unused outside of the loop, but it does not
1532 seem worth finding out. */
1533 if (!inv
->always_executed
)
1536 /* Check that all uses that would be dominated by def are already dominated
1538 dest_regno
= REGNO (reg
);
1539 for (use
= DF_REG_USE_CHAIN (dest_regno
); use
; use
= DF_REF_NEXT_REG (use
))
1544 use_insn
= DF_REF_INSN (use
);
1545 use_bb
= BLOCK_FOR_INSN (use_insn
);
1547 /* Ignore instruction considered for moving. */
1548 if (use_insn
== insn
)
1551 /* Don't consider uses outside loop. */
1552 if (!flow_bb_inside_loop_p (loop
, use_bb
))
1555 /* Don't move if a use is not dominated by def in insn. */
1556 if (use_bb
== bb
&& DF_INSN_LUID (insn
) >= DF_INSN_LUID (use_insn
))
1558 if (!dominated_by_p (CDI_DOMINATORS
, use_bb
, bb
))
1562 /* Check for other defs. Any other def in the loop might reach a use
1563 currently reached by the def in insn. */
1564 for (def
= DF_REG_DEF_CHAIN (dest_regno
); def
; def
= DF_REF_NEXT_REG (def
))
1566 basic_block def_bb
= DF_REF_BB (def
);
1568 /* Defs in exit block cannot reach a use they weren't already. */
1569 if (single_succ_p (def_bb
))
1571 basic_block def_bb_succ
;
1573 def_bb_succ
= single_succ (def_bb
);
1574 if (!flow_bb_inside_loop_p (loop
, def_bb_succ
))
1578 if (++defs_in_loop_count
> 1)
1585 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1589 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1591 struct invariant
*inv
= invariants
[invno
];
1592 struct invariant
*repr
= invariants
[inv
->eqto
];
1594 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1595 rtx reg
, set
, dest
, note
;
1604 /* If this is a representative of the class of equivalent invariants,
1605 really move the invariant. Otherwise just replace its use with
1606 the register used for the representative. */
1609 if (inv
->depends_on
)
1611 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1613 if (!move_invariant_reg (loop
, i
))
1618 /* If possible, just move the set out of the loop. Otherwise, we
1619 need to create a temporary register. */
1620 set
= single_set (inv
->insn
);
1621 reg
= dest
= SET_DEST (set
);
1622 if (GET_CODE (reg
) == SUBREG
)
1623 reg
= SUBREG_REG (reg
);
1625 regno
= REGNO (reg
);
1627 if (!can_move_invariant_reg (loop
, inv
, dest
))
1629 reg
= gen_reg_rtx_and_attrs (dest
);
1631 /* Try replacing the destination by a new pseudoregister. */
1632 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1634 /* As well as all the dominated uses. */
1635 replace_uses (inv
, reg
, true);
1637 /* And validate all the changes. */
1638 if (!apply_change_group ())
1641 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1644 fprintf (dump_file
, "Invariant %d moved without introducing a new "
1645 "temporary register\n", invno
);
1646 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1648 /* If there is a REG_EQUAL note on the insn we just moved, and the
1649 insn is in a basic block that is not always executed or the note
1650 contains something for which we don't know the invariant status,
1651 the note may no longer be valid after we move the insn. Note that
1652 uses in REG_EQUAL notes are taken into account in the computation
1653 of invariants, so it is safe to retain the note even if it contains
1654 register references for which we know the invariant status. */
1655 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1656 && (!inv
->always_executed
1657 || !check_maybe_invariant (XEXP (note
, 0))))
1658 remove_note (inv
->insn
, note
);
1662 if (!move_invariant_reg (loop
, repr
->invno
))
1665 regno
= repr
->orig_regno
;
1666 if (!replace_uses (inv
, reg
, false))
1668 set
= single_set (inv
->insn
);
1669 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1670 delete_insn (inv
->insn
);
1674 inv
->orig_regno
= regno
;
1679 /* If we failed, clear move flag, so that we do not try to move inv
1682 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1684 inv
->reg
= NULL_RTX
;
1685 inv
->orig_regno
= -1;
1690 /* Move selected invariant out of the LOOP. Newly created regs are marked
1691 in TEMPORARY_REGS. */
1694 move_invariants (struct loop
*loop
)
1696 struct invariant
*inv
;
1699 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1700 move_invariant_reg (loop
, i
);
1701 if (flag_ira_loop_pressure
&& resize_reg_info ())
1703 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1704 if (inv
->reg
!= NULL_RTX
)
1706 if (inv
->orig_regno
>= 0)
1707 setup_reg_classes (REGNO (inv
->reg
),
1708 reg_preferred_class (inv
->orig_regno
),
1709 reg_alternate_class (inv
->orig_regno
),
1710 reg_allocno_class (inv
->orig_regno
));
1712 setup_reg_classes (REGNO (inv
->reg
),
1713 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1718 /* Initializes invariant motion data. */
1721 init_inv_motion_data (void)
1725 invariants
.create (100);
1728 /* Frees the data allocated by invariant motion. */
1731 free_inv_motion_data (void)
1735 struct invariant
*inv
;
1737 check_invariant_table_size ();
1738 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1740 inv
= invariant_table
[i
];
1744 gcc_assert (def
!= NULL
);
1746 free_use_list (def
->uses
);
1748 invariant_table
[i
] = NULL
;
1752 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1754 BITMAP_FREE (inv
->depends_on
);
1757 invariants
.release ();
1760 /* Move the invariants out of the LOOP. */
1763 move_single_loop_invariants (struct loop
*loop
)
1765 init_inv_motion_data ();
1767 find_invariants (loop
);
1768 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1769 LOOP_DATA (loop
)->has_call
);
1770 move_invariants (loop
);
1772 free_inv_motion_data ();
1775 /* Releases the auxiliary data for LOOP. */
1778 free_loop_data (struct loop
*loop
)
1780 struct loop_data
*data
= LOOP_DATA (loop
);
1784 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1785 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1792 /* Registers currently living. */
1793 static bitmap_head curr_regs_live
;
1795 /* Current reg pressure for each pressure class. */
1796 static int curr_reg_pressure
[N_REG_CLASSES
];
1798 /* Record all regs that are set in any one insn. Communication from
1799 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1800 all hard-registers. */
1801 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1802 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1803 /* Number of regs stored in the previous array. */
1804 static int n_regs_set
;
1806 /* Return pressure class and number of needed hard registers (through
1807 *NREGS) of register REGNO. */
1808 static enum reg_class
1809 get_regno_pressure_class (int regno
, int *nregs
)
1811 if (regno
>= FIRST_PSEUDO_REGISTER
)
1813 enum reg_class pressure_class
;
1815 pressure_class
= reg_allocno_class (regno
);
1816 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1818 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1819 return pressure_class
;
1821 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1822 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1825 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1834 /* Increase (if INCR_P) or decrease current register pressure for
1837 change_pressure (int regno
, bool incr_p
)
1840 enum reg_class pressure_class
;
1842 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1844 curr_reg_pressure
[pressure_class
] -= nregs
;
1847 curr_reg_pressure
[pressure_class
] += nregs
;
1848 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1849 < curr_reg_pressure
[pressure_class
])
1850 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1851 = curr_reg_pressure
[pressure_class
];
1855 /* Mark REGNO birth. */
1857 mark_regno_live (int regno
)
1861 for (loop
= curr_loop
;
1862 loop
!= current_loops
->tree_root
;
1863 loop
= loop_outer (loop
))
1864 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1865 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1867 change_pressure (regno
, true);
1870 /* Mark REGNO death. */
1872 mark_regno_death (int regno
)
1874 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1876 change_pressure (regno
, false);
1879 /* Mark setting register REG. */
1881 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1882 void *data ATTRIBUTE_UNUSED
)
1884 if (GET_CODE (reg
) == SUBREG
)
1885 reg
= SUBREG_REG (reg
);
1890 regs_set
[n_regs_set
++] = reg
;
1892 unsigned int end_regno
= END_REGNO (reg
);
1893 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1894 mark_regno_live (regno
);
1897 /* Mark clobbering register REG. */
1899 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1901 if (GET_CODE (setter
) == CLOBBER
)
1902 mark_reg_store (reg
, setter
, data
);
1905 /* Mark register REG death. */
1907 mark_reg_death (rtx reg
)
1909 unsigned int end_regno
= END_REGNO (reg
);
1910 for (unsigned int regno
= REGNO (reg
); regno
< end_regno
; ++regno
)
1911 mark_regno_death (regno
);
1914 /* Mark occurrence of registers in X for the current loop. */
1916 mark_ref_regs (rtx x
)
1925 code
= GET_CODE (x
);
1930 for (loop
= curr_loop
;
1931 loop
!= current_loops
->tree_root
;
1932 loop
= loop_outer (loop
))
1933 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1937 fmt
= GET_RTX_FORMAT (code
);
1938 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1940 mark_ref_regs (XEXP (x
, i
));
1941 else if (fmt
[i
] == 'E')
1945 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1946 mark_ref_regs (XVECEXP (x
, i
, j
));
1950 /* Calculate register pressure in the loops. */
1952 calculate_loop_reg_pressure (void)
1960 struct loop
*loop
, *parent
;
1962 FOR_EACH_LOOP (loop
, 0)
1963 if (loop
->aux
== NULL
)
1965 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1966 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1967 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1969 ira_setup_eliminable_regset ();
1970 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1971 FOR_EACH_BB_FN (bb
, cfun
)
1973 curr_loop
= bb
->loop_father
;
1974 if (curr_loop
== current_loops
->tree_root
)
1977 for (loop
= curr_loop
;
1978 loop
!= current_loops
->tree_root
;
1979 loop
= loop_outer (loop
))
1980 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1982 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1983 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1984 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1985 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1986 change_pressure (j
, true);
1988 FOR_BB_INSNS (bb
, insn
)
1990 if (! NONDEBUG_INSN_P (insn
))
1993 mark_ref_regs (PATTERN (insn
));
1995 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1997 /* Mark any registers dead after INSN as dead now. */
1999 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2000 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2001 mark_reg_death (XEXP (link
, 0));
2003 /* Mark any registers set in INSN as live,
2004 and mark them as conflicting with all other live regs.
2005 Clobbers are processed again, so they conflict with
2006 the registers that are set. */
2008 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
2011 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2012 if (REG_NOTE_KIND (link
) == REG_INC
)
2013 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
2015 while (n_regs_set
-- > 0)
2017 rtx note
= find_regno_note (insn
, REG_UNUSED
,
2018 REGNO (regs_set
[n_regs_set
]));
2022 mark_reg_death (XEXP (note
, 0));
2026 bitmap_clear (&curr_regs_live
);
2027 if (flag_ira_region
== IRA_REGION_MIXED
2028 || flag_ira_region
== IRA_REGION_ALL
)
2029 FOR_EACH_LOOP (loop
, 0)
2031 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2032 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
2034 enum reg_class pressure_class
;
2037 pressure_class
= get_regno_pressure_class (j
, &nregs
);
2038 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
2041 if (dump_file
== NULL
)
2043 FOR_EACH_LOOP (loop
, 0)
2045 parent
= loop_outer (loop
);
2046 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2047 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
2048 loop
->header
->index
, loop_depth (loop
));
2049 fprintf (dump_file
, "\n ref. regnos:");
2050 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
2051 fprintf (dump_file
, " %d", j
);
2052 fprintf (dump_file
, "\n live regnos:");
2053 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2054 fprintf (dump_file
, " %d", j
);
2055 fprintf (dump_file
, "\n Pressure:");
2056 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
2058 enum reg_class pressure_class
;
2060 pressure_class
= ira_pressure_classes
[i
];
2061 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
2063 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
2064 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
2066 fprintf (dump_file
, "\n");
2072 /* Move the invariants out of the loops. */
2075 move_loop_invariants (void)
2079 if (flag_ira_loop_pressure
)
2082 regstat_init_n_sets_and_refs ();
2083 ira_set_pseudo_classes (true, dump_file
);
2084 calculate_loop_reg_pressure ();
2085 regstat_free_n_sets_and_refs ();
2087 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
2088 /* Process the loops, innermost first. */
2089 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2092 /* move_single_loop_invariants for very large loops
2093 is time consuming and might need a lot of memory. */
2094 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2095 move_single_loop_invariants (loop
);
2098 FOR_EACH_LOOP (loop
, 0)
2100 free_loop_data (loop
);
2103 if (flag_ira_loop_pressure
)
2104 /* There is no sense to keep this info because it was most
2105 probably outdated by subsequent passes. */
2107 free (invariant_table
);
2108 invariant_table
= NULL
;
2109 invariant_table_size
= 0;
2111 #ifdef ENABLE_CHECKING
2112 verify_flow_info ();