1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This implements the loop invariant motion pass. It is very simple
21 (no calls, no loads/stores, etc.). This should be sufficient to cleanup
22 things like address arithmetics -- other more complicated invariants should
23 be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
25 We proceed loop by loop -- it is simpler than trying to handle things
26 globally and should not lose much. First we inspect all sets inside loop
27 and create a dependency graph on insns (saying "to move this insn, you must
28 also move the following insns").
30 We then need to determine what to move. We estimate the number of registers
31 used and move as many invariants as possible while we still have enough free
32 registers. We prefer the expensive invariants.
34 Then we move the selected invariants out of the loop, creating a new
35 temporaries for them if necessary. */
39 #include "coretypes.h"
41 #include "hard-reg-set.h"
52 #include "dominance.h"
55 #include "basic-block.h"
59 #include "statistics.h"
60 #include "double-int.h"
62 #include "fixed-value.h"
67 #include "insn-config.h"
79 #include "hash-table.h"
86 /* The data stored for the loop. */
90 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
91 bool has_call
; /* True if the loop contains a call. */
92 /* Maximal register pressure inside loop for given register class
93 (defined only for the pressure classes). */
94 int max_reg_pressure
[N_REG_CLASSES
];
95 /* Loop regs referenced and live pseudo-registers. */
97 bitmap_head regs_live
;
100 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
102 /* The description of an use. */
106 rtx
*pos
; /* Position of the use. */
107 rtx_insn
*insn
; /* The insn in that the use occurs. */
108 unsigned addr_use_p
; /* Whether the use occurs in an address. */
109 struct use
*next
; /* Next use in the list. */
112 /* The description of a def. */
116 struct use
*uses
; /* The list of uses that are uniquely reached
118 unsigned n_uses
; /* Number of such uses. */
119 unsigned n_addr_uses
; /* Number of uses in addresses. */
120 unsigned invno
; /* The corresponding invariant. */
123 /* The data stored for each invariant. */
127 /* The number of the invariant. */
130 /* The number of the invariant with the same value. */
133 /* The number of invariants which eqto this. */
136 /* If we moved the invariant out of the loop, the register that contains its
140 /* If we moved the invariant out of the loop, the original regno
141 that contained its value. */
144 /* The definition of the invariant. */
147 /* The insn in that it is defined. */
150 /* Whether it is always executed. */
151 bool always_executed
;
153 /* Whether to move the invariant. */
156 /* Whether the invariant is cheap when used as an address. */
159 /* Cost of the invariant. */
162 /* The invariants it depends on. */
165 /* Used for detecting already visited invariants during determining
166 costs of movements. */
170 /* Currently processed loop. */
171 static struct loop
*curr_loop
;
173 /* Table of invariants indexed by the df_ref uid field. */
175 static unsigned int invariant_table_size
= 0;
176 static struct invariant
** invariant_table
;
178 /* Entry for hash table of invariant expressions. */
180 struct invariant_expr_entry
183 struct invariant
*inv
;
195 /* The actual stamp for marking already visited invariants during determining
196 costs of movements. */
198 static unsigned actual_stamp
;
200 typedef struct invariant
*invariant_p
;
203 /* The invariants. */
205 static vec
<invariant_p
> invariants
;
207 /* Check the size of the invariant table and realloc if necessary. */
210 check_invariant_table_size (void)
212 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
214 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
215 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
216 memset (&invariant_table
[invariant_table_size
], 0,
217 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
218 invariant_table_size
= new_size
;
222 /* Test for possibility of invariantness of X. */
225 check_maybe_invariant (rtx x
)
227 enum rtx_code code
= GET_CODE (x
);
241 case UNSPEC_VOLATILE
:
249 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
250 It should not be hard, and might be faster than "elsewhere". */
252 /* Just handle the most trivial case where we load from an unchanging
253 location (most importantly, pic tables). */
254 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
260 /* Don't mess with insns declared volatile. */
261 if (MEM_VOLATILE_P (x
))
269 fmt
= GET_RTX_FORMAT (code
);
270 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
274 if (!check_maybe_invariant (XEXP (x
, i
)))
277 else if (fmt
[i
] == 'E')
279 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
280 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
288 /* Returns the invariant definition for USE, or NULL if USE is not
291 static struct invariant
*
292 invariant_for_use (df_ref use
)
294 struct df_link
*defs
;
296 basic_block bb
= DF_REF_BB (use
), def_bb
;
298 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
301 defs
= DF_REF_CHAIN (use
);
302 if (!defs
|| defs
->next
)
305 check_invariant_table_size ();
306 if (!invariant_table
[DF_REF_ID (def
)])
309 def_bb
= DF_REF_BB (def
);
310 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
312 return invariant_table
[DF_REF_ID (def
)];
315 /* Computes hash value for invariant expression X in INSN. */
318 hash_invariant_expr_1 (rtx_insn
*insn
, rtx x
)
320 enum rtx_code code
= GET_CODE (x
);
323 hashval_t val
= code
;
326 struct invariant
*inv
;
334 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
337 use
= df_find_use (insn
, x
);
339 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
340 inv
= invariant_for_use (use
);
342 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
344 gcc_assert (inv
->eqto
!= ~0u);
351 fmt
= GET_RTX_FORMAT (code
);
352 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
355 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
356 else if (fmt
[i
] == 'E')
358 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
359 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
361 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
368 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
369 and INSN2 have always the same value. */
372 invariant_expr_equal_p (rtx_insn
*insn1
, rtx e1
, rtx_insn
*insn2
, rtx e2
)
374 enum rtx_code code
= GET_CODE (e1
);
378 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
381 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
382 the other one. If both are VOIDmode, we rely on the caller of this
383 function to verify that their modes are the same. */
384 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
393 return rtx_equal_p (e1
, e2
);
396 use1
= df_find_use (insn1
, e1
);
397 use2
= df_find_use (insn2
, e2
);
399 inv1
= invariant_for_use (use1
);
401 inv2
= invariant_for_use (use2
);
404 return rtx_equal_p (e1
, e2
);
409 gcc_assert (inv1
->eqto
!= ~0u);
410 gcc_assert (inv2
->eqto
!= ~0u);
411 return inv1
->eqto
== inv2
->eqto
;
417 fmt
= GET_RTX_FORMAT (code
);
418 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
425 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
429 else if (fmt
[i
] == 'E')
431 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
434 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
436 sub1
= XVECEXP (e1
, i
, j
);
437 sub2
= XVECEXP (e2
, i
, j
);
439 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
443 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
445 if (XINT (e1
, i
) != XINT (e2
, i
))
448 /* Unhandled type of subexpression, we fail conservatively. */
456 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
458 typedef invariant_expr_entry
*value_type
;
459 typedef invariant_expr_entry
*compare_type
;
460 static inline hashval_t
hash (const invariant_expr_entry
*);
461 static inline bool equal (const invariant_expr_entry
*,
462 const invariant_expr_entry
*);
465 /* Returns hash value for invariant expression entry ENTRY. */
468 invariant_expr_hasher::hash (const invariant_expr_entry
*entry
)
473 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
476 invariant_expr_hasher::equal (const invariant_expr_entry
*entry1
,
477 const invariant_expr_entry
*entry2
)
479 if (entry1
->mode
!= entry2
->mode
)
482 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
483 entry2
->inv
->insn
, entry2
->expr
);
486 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
488 /* Checks whether invariant with value EXPR in machine mode MODE is
489 recorded in EQ. If this is the case, return the invariant. Otherwise
490 insert INV to the table for this expression and return INV. */
492 static struct invariant
*
493 find_or_insert_inv (invariant_htab_type
*eq
, rtx expr
, machine_mode mode
,
494 struct invariant
*inv
)
496 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
497 struct invariant_expr_entry
*entry
;
498 struct invariant_expr_entry pentry
;
499 invariant_expr_entry
**slot
;
504 slot
= eq
->find_slot_with_hash (&pentry
, hash
, INSERT
);
510 entry
= XNEW (struct invariant_expr_entry
);
520 /* Finds invariants identical to INV and records the equivalence. EQ is the
521 hash table of the invariants. */
524 find_identical_invariants (invariant_htab_type
*eq
, struct invariant
*inv
)
528 struct invariant
*dep
;
531 struct invariant
*tmp
;
533 if (inv
->eqto
!= ~0u)
536 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
538 dep
= invariants
[depno
];
539 find_identical_invariants (eq
, dep
);
542 set
= single_set (inv
->insn
);
543 expr
= SET_SRC (set
);
544 mode
= GET_MODE (expr
);
545 if (mode
== VOIDmode
)
546 mode
= GET_MODE (SET_DEST (set
));
548 tmp
= find_or_insert_inv (eq
, expr
, mode
, inv
);
549 inv
->eqto
= tmp
->invno
;
551 if (tmp
->invno
!= inv
->invno
&& inv
->always_executed
)
554 if (dump_file
&& inv
->eqto
!= inv
->invno
)
556 "Invariant %d is equivalent to invariant %d.\n",
557 inv
->invno
, inv
->eqto
);
560 /* Find invariants with the same value and record the equivalences. */
563 merge_identical_invariants (void)
566 struct invariant
*inv
;
567 invariant_htab_type
eq (invariants
.length ());
569 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
570 find_identical_invariants (&eq
, inv
);
573 /* Determines the basic blocks inside LOOP that are always executed and
574 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
575 basic blocks that may either exit the loop, or contain the call that
576 does not have to return. BODY is body of the loop obtained by
577 get_loop_body_in_dom_order. */
580 compute_always_reached (struct loop
*loop
, basic_block
*body
,
581 bitmap may_exit
, bitmap always_reached
)
585 for (i
= 0; i
< loop
->num_nodes
; i
++)
587 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
588 bitmap_set_bit (always_reached
, i
);
590 if (bitmap_bit_p (may_exit
, i
))
595 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
596 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
597 additionally mark blocks that may exit due to a call. */
600 find_exits (struct loop
*loop
, basic_block
*body
,
601 bitmap may_exit
, bitmap has_exit
)
606 struct loop
*outermost_exit
= loop
, *aexit
;
607 bool has_call
= false;
610 for (i
= 0; i
< loop
->num_nodes
; i
++)
612 if (body
[i
]->loop_father
== loop
)
614 FOR_BB_INSNS (body
[i
], insn
)
617 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
618 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
621 bitmap_set_bit (may_exit
, i
);
626 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
628 if (flow_bb_inside_loop_p (loop
, e
->dest
))
631 bitmap_set_bit (may_exit
, i
);
632 bitmap_set_bit (has_exit
, i
);
633 outermost_exit
= find_common_loop (outermost_exit
,
634 e
->dest
->loop_father
);
639 /* Use the data stored for the subloop to decide whether we may exit
640 through it. It is sufficient to do this for header of the loop,
641 as other basic blocks inside it must be dominated by it. */
642 if (body
[i
]->loop_father
->header
!= body
[i
])
645 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
648 bitmap_set_bit (may_exit
, i
);
650 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
653 bitmap_set_bit (may_exit
, i
);
654 bitmap_set_bit (has_exit
, i
);
656 if (flow_loop_nested_p (aexit
, outermost_exit
))
657 outermost_exit
= aexit
;
661 if (loop
->aux
== NULL
)
663 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
664 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
665 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
667 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
668 LOOP_DATA (loop
)->has_call
= has_call
;
671 /* Check whether we may assign a value to X from a register. */
674 may_assign_reg_p (rtx x
)
676 return (GET_MODE (x
) != VOIDmode
677 && GET_MODE (x
) != BLKmode
678 && can_copy_p (GET_MODE (x
))
680 || !HARD_REGISTER_P (x
)
681 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
684 /* Finds definitions that may correspond to invariants in LOOP with body
688 find_defs (struct loop
*loop
)
693 "*****starting processing of loop %d ******\n",
697 df_remove_problem (df_chain
);
698 df_process_deferred_rescans ();
699 df_chain_add_problem (DF_UD_CHAIN
);
700 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
701 df_analyze_loop (loop
);
702 check_invariant_table_size ();
706 df_dump_region (dump_file
);
708 "*****ending processing of loop %d ******\n",
713 /* Creates a new invariant for definition DEF in INSN, depending on invariants
714 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
715 unless the program ends due to a function call. The newly created invariant
718 static struct invariant
*
719 create_new_invariant (struct def
*def
, rtx_insn
*insn
, bitmap depends_on
,
720 bool always_executed
)
722 struct invariant
*inv
= XNEW (struct invariant
);
723 rtx set
= single_set (insn
);
724 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
727 inv
->always_executed
= always_executed
;
728 inv
->depends_on
= depends_on
;
730 /* If the set is simple, usually by moving it we move the whole store out of
731 the loop. Otherwise we save only cost of the computation. */
734 inv
->cost
= set_rtx_cost (set
, speed
);
735 /* ??? Try to determine cheapness of address computation. Unfortunately
736 the address cost is only a relative measure, we can't really compare
737 it with any absolute number, but only with other address costs.
738 But here we don't have any other addresses, so compare with a magic
739 number anyway. It has to be large enough to not regress PR33928
740 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
741 enough to not regress 410.bwaves either (by still moving reg+reg
743 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
744 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
745 ADDR_SPACE_GENERIC
, speed
) < 3;
749 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
750 inv
->cheap_address
= false;
755 inv
->orig_regno
= -1;
759 inv
->invno
= invariants
.length ();
766 def
->invno
= inv
->invno
;
767 invariants
.safe_push (inv
);
772 "Set in insn %d is invariant (%d), cost %d, depends on ",
773 INSN_UID (insn
), inv
->invno
, inv
->cost
);
774 dump_bitmap (dump_file
, inv
->depends_on
);
780 /* Record USE at DEF. */
783 record_use (struct def
*def
, df_ref use
)
785 struct use
*u
= XNEW (struct use
);
787 u
->pos
= DF_REF_REAL_LOC (use
);
788 u
->insn
= DF_REF_INSN (use
);
789 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
790 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
798 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
799 bitmap. Returns true if all dependencies of USE are known to be
800 loop invariants, false otherwise. */
803 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
807 struct df_link
*defs
;
808 struct def
*def_data
;
809 struct invariant
*inv
;
811 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
814 defs
= DF_REF_CHAIN (use
);
817 unsigned int regno
= DF_REF_REGNO (use
);
819 /* If this is the use of an uninitialized argument register that is
820 likely to be spilled, do not move it lest this might extend its
821 lifetime and cause reload to die. This can occur for a call to
822 a function taking complex number arguments and moving the insns
823 preparing the arguments without moving the call itself wouldn't
824 gain much in practice. */
825 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
826 && FUNCTION_ARG_REGNO_P (regno
)
827 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
837 check_invariant_table_size ();
838 inv
= invariant_table
[DF_REF_ID (def
)];
843 gcc_assert (def_data
!= NULL
);
845 def_bb
= DF_REF_BB (def
);
846 /* Note that in case bb == def_bb, we know that the definition
847 dominates insn, because def has invariant_table[DF_REF_ID(def)]
848 defined and we process the insns in the basic block bb
850 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
853 bitmap_set_bit (depends_on
, def_data
->invno
);
858 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
859 bitmap. Returns true if all dependencies of INSN are known to be
860 loop invariants, false otherwise. */
863 check_dependencies (rtx_insn
*insn
, bitmap depends_on
)
865 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
867 basic_block bb
= BLOCK_FOR_INSN (insn
);
869 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
870 if (!check_dependency (bb
, use
, depends_on
))
872 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
873 if (!check_dependency (bb
, use
, depends_on
))
879 /* Pre-check candidate DEST to skip the one which can not make a valid insn
880 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
882 pre_check_invariant_p (bool simple
, rtx dest
)
884 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
888 unsigned int i
= REGNO (dest
);
889 struct df_insn_info
*insn_info
;
892 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
894 ref
= DF_REF_INSN (use
);
895 insn_info
= DF_INSN_INFO_GET (ref
);
897 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
898 if (DF_REF_REGNO (def_rec
) == i
)
900 /* Multi definitions at this stage, most likely are due to
901 instruction constraints, which requires both read and write
902 on the same register. Since move_invariant_reg is not
903 powerful enough to handle such cases, just ignore the INV
904 and leave the chance to others. */
912 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
913 executed. ALWAYS_EXECUTED is true if the insn is always executed,
914 unless the program ends due to a function call. */
917 find_invariant_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
924 struct invariant
*inv
;
926 /* We can't move a CC0 setter without the user. */
927 if (HAVE_cc0
&& sets_cc0_p (insn
))
930 set
= single_set (insn
);
933 dest
= SET_DEST (set
);
936 || HARD_REGISTER_P (dest
))
939 if (!may_assign_reg_p (dest
)
940 || !pre_check_invariant_p (simple
, dest
)
941 || !check_maybe_invariant (SET_SRC (set
)))
944 /* If the insn can throw exception, we cannot move it at all without changing
946 if (can_throw_internal (insn
))
949 /* We cannot make trapping insn executed, unless it was executed before. */
950 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
953 depends_on
= BITMAP_ALLOC (NULL
);
954 if (!check_dependencies (insn
, depends_on
))
956 BITMAP_FREE (depends_on
);
961 def
= XCNEW (struct def
);
965 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
969 ref
= df_find_def (insn
, dest
);
970 check_invariant_table_size ();
971 invariant_table
[DF_REF_ID (ref
)] = inv
;
975 /* Record registers used in INSN that have a unique invariant definition. */
978 record_uses (rtx_insn
*insn
)
980 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
982 struct invariant
*inv
;
984 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
986 inv
= invariant_for_use (use
);
988 record_use (inv
->def
, use
);
990 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
992 inv
= invariant_for_use (use
);
994 record_use (inv
->def
, use
);
998 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
999 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1000 unless the program ends due to a function call. */
1003 find_invariants_insn (rtx_insn
*insn
, bool always_reached
, bool always_executed
)
1005 find_invariant_insn (insn
, always_reached
, always_executed
);
1009 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1010 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1011 block is always executed, unless the program ends due to a function
1015 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
1019 FOR_BB_INSNS (bb
, insn
)
1021 if (!NONDEBUG_INSN_P (insn
))
1024 find_invariants_insn (insn
, always_reached
, always_executed
);
1028 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
1029 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
1030 always_reached
= false;
1034 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1035 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1036 bitmap of basic blocks in BODY that are always executed unless the program
1037 ends due to a function call. */
1040 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1041 bitmap always_reached
, bitmap always_executed
)
1045 for (i
= 0; i
< loop
->num_nodes
; i
++)
1046 find_invariants_bb (body
[i
],
1047 bitmap_bit_p (always_reached
, i
),
1048 bitmap_bit_p (always_executed
, i
));
1051 /* Finds invariants in LOOP. */
1054 find_invariants (struct loop
*loop
)
1056 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1057 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1058 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1059 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1060 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1062 find_exits (loop
, body
, may_exit
, has_exit
);
1063 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1064 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1067 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1068 merge_identical_invariants ();
1070 BITMAP_FREE (always_reached
);
1071 BITMAP_FREE (always_executed
);
1072 BITMAP_FREE (may_exit
);
1073 BITMAP_FREE (has_exit
);
1077 /* Frees a list of uses USE. */
1080 free_use_list (struct use
*use
)
1084 for (; use
; use
= next
)
1091 /* Return pressure class and number of hard registers (through *NREGS)
1092 for destination of INSN. */
1093 static enum reg_class
1094 get_pressure_class_and_nregs (rtx_insn
*insn
, int *nregs
)
1097 enum reg_class pressure_class
;
1098 rtx set
= single_set (insn
);
1100 /* Considered invariant insns have only one set. */
1101 gcc_assert (set
!= NULL_RTX
);
1102 reg
= SET_DEST (set
);
1103 if (GET_CODE (reg
) == SUBREG
)
1104 reg
= SUBREG_REG (reg
);
1108 pressure_class
= NO_REGS
;
1114 if (reg
== NULL_RTX
)
1115 pressure_class
= GENERAL_REGS
;
1118 pressure_class
= reg_allocno_class (REGNO (reg
));
1119 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1122 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1124 return pressure_class
;
1127 /* Calculates cost and number of registers needed for moving invariant INV
1128 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1129 the REG_CLASS of INV. Return
1130 -1: if INV is invalid.
1131 0: if INV and its depends_on have same reg_class
1132 1: if INV and its depends_on have different reg_classes. */
1135 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
,
1139 unsigned aregs_needed
[N_REG_CLASSES
];
1141 struct invariant
*dep
;
1145 /* Find the representative of the class of the equivalent invariants. */
1146 inv
= invariants
[inv
->eqto
];
1149 if (! flag_ira_loop_pressure
)
1153 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1154 regs_needed
[ira_pressure_classes
[i
]] = 0;
1158 || inv
->stamp
== actual_stamp
)
1160 inv
->stamp
= actual_stamp
;
1162 if (! flag_ira_loop_pressure
)
1167 enum reg_class pressure_class
;
1169 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1170 regs_needed
[pressure_class
] += nregs
;
1171 *cl
= pressure_class
;
1175 if (!inv
->cheap_address
1176 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1177 (*comp_cost
) += inv
->cost
* inv
->eqno
;
1181 /* Hoisting constant pool constants into stack regs may cost more than
1182 just single register. On x87, the balance is affected both by the
1183 small number of FP registers, and by its register stack organization,
1184 that forces us to add compensation code in and around the loop to
1185 shuffle the operands to the top of stack before use, and pop them
1186 from the stack after the loop finishes.
1188 To model this effect, we increase the number of registers needed for
1189 stack registers by two: one register push, and one register pop.
1190 This usually has the effect that FP constant loads from the constant
1191 pool are not moved out of the loop.
1193 Note that this also means that dependent invariants can not be moved.
1194 However, the primary purpose of this pass is to move loop invariant
1195 address arithmetic out of loops, and address arithmetic that depends
1196 on floating point constants is unlikely to ever occur. */
1197 rtx set
= single_set (inv
->insn
);
1199 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1200 && constant_pool_constant_p (SET_SRC (set
)))
1202 if (flag_ira_loop_pressure
)
1203 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1205 regs_needed
[0] += 2;
1210 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1213 enum reg_class dep_cl
= ALL_REGS
;
1216 dep
= invariants
[depno
];
1218 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1222 dep_ret
= get_inv_cost (dep
, &acomp_cost
, aregs_needed
, &dep_cl
);
1224 if (! flag_ira_loop_pressure
)
1225 check_p
= aregs_needed
[0] != 0;
1228 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1229 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1231 check_p
= i
< ira_pressure_classes_num
;
1233 if ((dep_ret
== 1) || ((dep_ret
== 0) && (*cl
!= dep_cl
)))
1240 /* We need to check always_executed, since if the original value of
1241 the invariant may be preserved, we may need to keep it in a
1242 separate register. TODO check whether the register has an
1243 use outside of the loop. */
1244 && dep
->always_executed
1245 && !dep
->def
->uses
->next
)
1247 /* If this is a single use, after moving the dependency we will not
1248 need a new register. */
1249 if (! flag_ira_loop_pressure
)
1254 enum reg_class pressure_class
;
1256 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1257 aregs_needed
[pressure_class
] -= nregs
;
1261 if (! flag_ira_loop_pressure
)
1262 regs_needed
[0] += aregs_needed
[0];
1265 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1266 regs_needed
[ira_pressure_classes
[i
]]
1267 += aregs_needed
[ira_pressure_classes
[i
]];
1269 (*comp_cost
) += acomp_cost
;
1274 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1275 of registers used in the loop, NEW_REGS is the number of new variables
1276 already added due to the invariant motion. The number of registers needed
1277 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1278 through to estimate_reg_pressure_cost. */
1281 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1282 unsigned *new_regs
, unsigned regs_used
,
1283 bool speed
, bool call_p
)
1285 int comp_cost
, size_cost
;
1286 /* Workaround -Wmaybe-uninitialized false positive during
1287 profiledbootstrap by initializing it. */
1288 enum reg_class cl
= NO_REGS
;
1293 ret
= get_inv_cost (inv
, &comp_cost
, regs_needed
, &cl
);
1295 if (! flag_ira_loop_pressure
)
1297 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1298 regs_used
, speed
, call_p
)
1299 - estimate_reg_pressure_cost (new_regs
[0],
1300 regs_used
, speed
, call_p
));
1304 else if ((ret
== 0) && (cl
== NO_REGS
))
1305 /* Hoist it anyway since it does not impact register pressure. */
1310 enum reg_class pressure_class
;
1312 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1314 pressure_class
= ira_pressure_classes
[i
];
1316 if (!reg_classes_intersect_p (pressure_class
, cl
))
1319 if ((int) new_regs
[pressure_class
]
1320 + (int) regs_needed
[pressure_class
]
1321 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1322 + IRA_LOOP_RESERVED_REGS
1323 > ira_class_hard_regs_num
[pressure_class
])
1326 if (i
< ira_pressure_classes_num
)
1327 /* There will be register pressure excess and we want not to
1328 make this loop invariant motion. All loop invariants with
1329 non-positive gains will be rejected in function
1330 find_invariants_to_move. Therefore we return the negative
1333 One could think that this rejects also expensive loop
1334 invariant motions and this will hurt code performance.
1335 However numerous experiments with different heuristics
1336 taking invariant cost into account did not confirm this
1337 assumption. There are possible explanations for this
1339 o probably all expensive invariants were already moved out
1340 of the loop by PRE and gimple invariant motion pass.
1341 o expensive invariant execution will be hidden by insn
1342 scheduling or OOO processor hardware because usually such
1343 invariants have a lot of freedom to be executed
1345 Another reason for ignoring invariant cost vs spilling cost
1346 heuristics is also in difficulties to evaluate accurately
1347 spill cost at this stage. */
1353 return comp_cost
- size_cost
;
1356 /* Finds invariant with best gain for moving. Returns the gain, stores
1357 the invariant in *BEST and number of registers needed for it to
1358 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1359 NEW_REGS is the number of new variables already added due to invariant
1363 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1364 unsigned *new_regs
, unsigned regs_used
,
1365 bool speed
, bool call_p
)
1367 struct invariant
*inv
;
1368 int i
, gain
= 0, again
;
1369 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1371 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1376 /* Only consider the "representatives" of equivalent invariants. */
1377 if (inv
->eqto
!= inv
->invno
)
1380 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1386 if (! flag_ira_loop_pressure
)
1387 regs_needed
[0] = aregs_needed
[0];
1390 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1391 regs_needed
[ira_pressure_classes
[i
]]
1392 = aregs_needed
[ira_pressure_classes
[i
]];
1400 /* Marks invariant INVNO and all its dependencies for moving. */
1403 set_move_mark (unsigned invno
, int gain
)
1405 struct invariant
*inv
= invariants
[invno
];
1408 /* Find the representative of the class of the equivalent invariants. */
1409 inv
= invariants
[inv
->eqto
];
1418 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1421 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1425 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1427 set_move_mark (invno
, -1);
1431 /* Determines which invariants to move. */
1434 find_invariants_to_move (bool speed
, bool call_p
)
1437 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1438 struct invariant
*inv
= NULL
;
1440 if (!invariants
.length ())
1443 if (flag_ira_loop_pressure
)
1444 /* REGS_USED is actually never used when the flag is on. */
1447 /* We do not really do a good job in estimating number of
1448 registers used; we put some initial bound here to stand for
1449 induction variables etc. that we do not detect. */
1451 unsigned int n_regs
= DF_REG_SIZE (df
);
1455 for (i
= 0; i
< n_regs
; i
++)
1457 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1459 /* This is a value that is used but not changed inside loop. */
1465 if (! flag_ira_loop_pressure
)
1466 new_regs
[0] = regs_needed
[0] = 0;
1469 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1470 new_regs
[ira_pressure_classes
[i
]] = 0;
1472 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1473 new_regs
, regs_used
,
1474 speed
, call_p
)) > 0)
1476 set_move_mark (inv
->invno
, gain
);
1477 if (! flag_ira_loop_pressure
)
1478 new_regs
[0] += regs_needed
[0];
1481 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1482 new_regs
[ira_pressure_classes
[i
]]
1483 += regs_needed
[ira_pressure_classes
[i
]];
1488 /* Replace the uses, reached by the definition of invariant INV, by REG.
1490 IN_GROUP is nonzero if this is part of a group of changes that must be
1491 performed as a group. In that case, the changes will be stored. The
1492 function `apply_change_group' will validate and apply the changes. */
1495 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1497 /* Replace the uses we know to be dominated. It saves work for copy
1498 propagation, and also it is necessary so that dependent invariants
1499 are computed right. */
1503 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1504 validate_change (use
->insn
, use
->pos
, reg
, true);
1506 /* If we aren't part of a larger group, apply the changes now. */
1508 return apply_change_group ();
1514 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1515 the block preceding its header. */
1518 can_move_invariant_reg (struct loop
*loop
, struct invariant
*inv
, rtx reg
)
1521 unsigned int dest_regno
, defs_in_loop_count
= 0;
1522 rtx_insn
*insn
= inv
->insn
;
1523 basic_block bb
= BLOCK_FOR_INSN (inv
->insn
);
1525 /* We ignore hard register and memory access for cost and complexity reasons.
1526 Hard register are few at this stage and expensive to consider as they
1527 require building a separate data flow. Memory access would require using
1528 df_simulate_* and can_move_insns_across functions and is more complex. */
1529 if (!REG_P (reg
) || HARD_REGISTER_P (reg
))
1532 /* Check whether the set is always executed. We could omit this condition if
1533 we know that the register is unused outside of the loop, but it does not
1534 seem worth finding out. */
1535 if (!inv
->always_executed
)
1538 /* Check that all uses that would be dominated by def are already dominated
1540 dest_regno
= REGNO (reg
);
1541 for (use
= DF_REG_USE_CHAIN (dest_regno
); use
; use
= DF_REF_NEXT_REG (use
))
1546 use_insn
= DF_REF_INSN (use
);
1547 use_bb
= BLOCK_FOR_INSN (use_insn
);
1549 /* Ignore instruction considered for moving. */
1550 if (use_insn
== insn
)
1553 /* Don't consider uses outside loop. */
1554 if (!flow_bb_inside_loop_p (loop
, use_bb
))
1557 /* Don't move if a use is not dominated by def in insn. */
1558 if (use_bb
== bb
&& DF_INSN_LUID (insn
) >= DF_INSN_LUID (use_insn
))
1560 if (!dominated_by_p (CDI_DOMINATORS
, use_bb
, bb
))
1564 /* Check for other defs. Any other def in the loop might reach a use
1565 currently reached by the def in insn. */
1566 for (def
= DF_REG_DEF_CHAIN (dest_regno
); def
; def
= DF_REF_NEXT_REG (def
))
1568 basic_block def_bb
= DF_REF_BB (def
);
1570 /* Defs in exit block cannot reach a use they weren't already. */
1571 if (single_succ_p (def_bb
))
1573 basic_block def_bb_succ
;
1575 def_bb_succ
= single_succ (def_bb
);
1576 if (!flow_bb_inside_loop_p (loop
, def_bb_succ
))
1580 if (++defs_in_loop_count
> 1)
1587 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1591 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1593 struct invariant
*inv
= invariants
[invno
];
1594 struct invariant
*repr
= invariants
[inv
->eqto
];
1596 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1597 rtx reg
, set
, dest
, note
;
1606 /* If this is a representative of the class of equivalent invariants,
1607 really move the invariant. Otherwise just replace its use with
1608 the register used for the representative. */
1611 if (inv
->depends_on
)
1613 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1615 if (!move_invariant_reg (loop
, i
))
1620 /* If possible, just move the set out of the loop. Otherwise, we
1621 need to create a temporary register. */
1622 set
= single_set (inv
->insn
);
1623 reg
= dest
= SET_DEST (set
);
1624 if (GET_CODE (reg
) == SUBREG
)
1625 reg
= SUBREG_REG (reg
);
1627 regno
= REGNO (reg
);
1629 if (!can_move_invariant_reg (loop
, inv
, reg
))
1631 reg
= gen_reg_rtx_and_attrs (dest
);
1633 /* Try replacing the destination by a new pseudoregister. */
1634 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1636 /* As well as all the dominated uses. */
1637 replace_uses (inv
, reg
, true);
1639 /* And validate all the changes. */
1640 if (!apply_change_group ())
1643 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1646 fprintf (dump_file
, "Invariant %d moved without introducing a new "
1647 "temporary register\n", invno
);
1648 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1650 /* If there is a REG_EQUAL note on the insn we just moved, and the
1651 insn is in a basic block that is not always executed or the note
1652 contains something for which we don't know the invariant status,
1653 the note may no longer be valid after we move the insn. Note that
1654 uses in REG_EQUAL notes are taken into account in the computation
1655 of invariants, so it is safe to retain the note even if it contains
1656 register references for which we know the invariant status. */
1657 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1658 && (!inv
->always_executed
1659 || !check_maybe_invariant (XEXP (note
, 0))))
1660 remove_note (inv
->insn
, note
);
1664 if (!move_invariant_reg (loop
, repr
->invno
))
1667 regno
= repr
->orig_regno
;
1668 if (!replace_uses (inv
, reg
, false))
1670 set
= single_set (inv
->insn
);
1671 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1672 delete_insn (inv
->insn
);
1676 inv
->orig_regno
= regno
;
1681 /* If we failed, clear move flag, so that we do not try to move inv
1684 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1686 inv
->reg
= NULL_RTX
;
1687 inv
->orig_regno
= -1;
1692 /* Move selected invariant out of the LOOP. Newly created regs are marked
1693 in TEMPORARY_REGS. */
1696 move_invariants (struct loop
*loop
)
1698 struct invariant
*inv
;
1701 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1702 move_invariant_reg (loop
, i
);
1703 if (flag_ira_loop_pressure
&& resize_reg_info ())
1705 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1706 if (inv
->reg
!= NULL_RTX
)
1708 if (inv
->orig_regno
>= 0)
1709 setup_reg_classes (REGNO (inv
->reg
),
1710 reg_preferred_class (inv
->orig_regno
),
1711 reg_alternate_class (inv
->orig_regno
),
1712 reg_allocno_class (inv
->orig_regno
));
1714 setup_reg_classes (REGNO (inv
->reg
),
1715 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1720 /* Initializes invariant motion data. */
1723 init_inv_motion_data (void)
1727 invariants
.create (100);
1730 /* Frees the data allocated by invariant motion. */
1733 free_inv_motion_data (void)
1737 struct invariant
*inv
;
1739 check_invariant_table_size ();
1740 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1742 inv
= invariant_table
[i
];
1746 gcc_assert (def
!= NULL
);
1748 free_use_list (def
->uses
);
1750 invariant_table
[i
] = NULL
;
1754 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1756 BITMAP_FREE (inv
->depends_on
);
1759 invariants
.release ();
1762 /* Move the invariants out of the LOOP. */
1765 move_single_loop_invariants (struct loop
*loop
)
1767 init_inv_motion_data ();
1769 find_invariants (loop
);
1770 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1771 LOOP_DATA (loop
)->has_call
);
1772 move_invariants (loop
);
1774 free_inv_motion_data ();
1777 /* Releases the auxiliary data for LOOP. */
1780 free_loop_data (struct loop
*loop
)
1782 struct loop_data
*data
= LOOP_DATA (loop
);
1786 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1787 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1794 /* Registers currently living. */
1795 static bitmap_head curr_regs_live
;
1797 /* Current reg pressure for each pressure class. */
1798 static int curr_reg_pressure
[N_REG_CLASSES
];
1800 /* Record all regs that are set in any one insn. Communication from
1801 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1802 all hard-registers. */
1803 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1804 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1805 /* Number of regs stored in the previous array. */
1806 static int n_regs_set
;
1808 /* Return pressure class and number of needed hard registers (through
1809 *NREGS) of register REGNO. */
1810 static enum reg_class
1811 get_regno_pressure_class (int regno
, int *nregs
)
1813 if (regno
>= FIRST_PSEUDO_REGISTER
)
1815 enum reg_class pressure_class
;
1817 pressure_class
= reg_allocno_class (regno
);
1818 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1820 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1821 return pressure_class
;
1823 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1824 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1827 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1836 /* Increase (if INCR_P) or decrease current register pressure for
1839 change_pressure (int regno
, bool incr_p
)
1842 enum reg_class pressure_class
;
1844 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1846 curr_reg_pressure
[pressure_class
] -= nregs
;
1849 curr_reg_pressure
[pressure_class
] += nregs
;
1850 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1851 < curr_reg_pressure
[pressure_class
])
1852 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1853 = curr_reg_pressure
[pressure_class
];
1857 /* Mark REGNO birth. */
1859 mark_regno_live (int regno
)
1863 for (loop
= curr_loop
;
1864 loop
!= current_loops
->tree_root
;
1865 loop
= loop_outer (loop
))
1866 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1867 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1869 change_pressure (regno
, true);
1872 /* Mark REGNO death. */
1874 mark_regno_death (int regno
)
1876 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1878 change_pressure (regno
, false);
1881 /* Mark setting register REG. */
1883 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1884 void *data ATTRIBUTE_UNUSED
)
1888 if (GET_CODE (reg
) == SUBREG
)
1889 reg
= SUBREG_REG (reg
);
1894 regs_set
[n_regs_set
++] = reg
;
1896 regno
= REGNO (reg
);
1898 if (regno
>= FIRST_PSEUDO_REGISTER
)
1899 mark_regno_live (regno
);
1902 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1904 while (regno
< last
)
1906 mark_regno_live (regno
);
1912 /* Mark clobbering register REG. */
1914 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1916 if (GET_CODE (setter
) == CLOBBER
)
1917 mark_reg_store (reg
, setter
, data
);
1920 /* Mark register REG death. */
1922 mark_reg_death (rtx reg
)
1924 int regno
= REGNO (reg
);
1926 if (regno
>= FIRST_PSEUDO_REGISTER
)
1927 mark_regno_death (regno
);
1930 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1932 while (regno
< last
)
1934 mark_regno_death (regno
);
1940 /* Mark occurrence of registers in X for the current loop. */
1942 mark_ref_regs (rtx x
)
1951 code
= GET_CODE (x
);
1956 for (loop
= curr_loop
;
1957 loop
!= current_loops
->tree_root
;
1958 loop
= loop_outer (loop
))
1959 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1963 fmt
= GET_RTX_FORMAT (code
);
1964 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1966 mark_ref_regs (XEXP (x
, i
));
1967 else if (fmt
[i
] == 'E')
1971 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1972 mark_ref_regs (XVECEXP (x
, i
, j
));
1976 /* Calculate register pressure in the loops. */
1978 calculate_loop_reg_pressure (void)
1986 struct loop
*loop
, *parent
;
1988 FOR_EACH_LOOP (loop
, 0)
1989 if (loop
->aux
== NULL
)
1991 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1992 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1993 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1995 ira_setup_eliminable_regset ();
1996 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1997 FOR_EACH_BB_FN (bb
, cfun
)
1999 curr_loop
= bb
->loop_father
;
2000 if (curr_loop
== current_loops
->tree_root
)
2003 for (loop
= curr_loop
;
2004 loop
!= current_loops
->tree_root
;
2005 loop
= loop_outer (loop
))
2006 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
2008 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
2009 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2010 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
2011 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
2012 change_pressure (j
, true);
2014 FOR_BB_INSNS (bb
, insn
)
2016 if (! NONDEBUG_INSN_P (insn
))
2019 mark_ref_regs (PATTERN (insn
));
2021 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
2023 /* Mark any registers dead after INSN as dead now. */
2025 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2026 if (REG_NOTE_KIND (link
) == REG_DEAD
)
2027 mark_reg_death (XEXP (link
, 0));
2029 /* Mark any registers set in INSN as live,
2030 and mark them as conflicting with all other live regs.
2031 Clobbers are processed again, so they conflict with
2032 the registers that are set. */
2034 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
2037 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
2038 if (REG_NOTE_KIND (link
) == REG_INC
)
2039 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
2041 while (n_regs_set
-- > 0)
2043 rtx note
= find_regno_note (insn
, REG_UNUSED
,
2044 REGNO (regs_set
[n_regs_set
]));
2048 mark_reg_death (XEXP (note
, 0));
2052 bitmap_clear (&curr_regs_live
);
2053 if (flag_ira_region
== IRA_REGION_MIXED
2054 || flag_ira_region
== IRA_REGION_ALL
)
2055 FOR_EACH_LOOP (loop
, 0)
2057 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2058 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
2060 enum reg_class pressure_class
;
2063 pressure_class
= get_regno_pressure_class (j
, &nregs
);
2064 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
2067 if (dump_file
== NULL
)
2069 FOR_EACH_LOOP (loop
, 0)
2071 parent
= loop_outer (loop
);
2072 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2073 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
2074 loop
->header
->index
, loop_depth (loop
));
2075 fprintf (dump_file
, "\n ref. regnos:");
2076 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
2077 fprintf (dump_file
, " %d", j
);
2078 fprintf (dump_file
, "\n live regnos:");
2079 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
2080 fprintf (dump_file
, " %d", j
);
2081 fprintf (dump_file
, "\n Pressure:");
2082 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
2084 enum reg_class pressure_class
;
2086 pressure_class
= ira_pressure_classes
[i
];
2087 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
2089 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
2090 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
2092 fprintf (dump_file
, "\n");
2098 /* Move the invariants out of the loops. */
2101 move_loop_invariants (void)
2105 if (flag_ira_loop_pressure
)
2108 regstat_init_n_sets_and_refs ();
2109 ira_set_pseudo_classes (true, dump_file
);
2110 calculate_loop_reg_pressure ();
2111 regstat_free_n_sets_and_refs ();
2113 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
2114 /* Process the loops, innermost first. */
2115 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
2118 /* move_single_loop_invariants for very large loops
2119 is time consuming and might need a lot of memory. */
2120 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
2121 move_single_loop_invariants (loop
);
2124 FOR_EACH_LOOP (loop
, 0)
2126 free_loop_data (loop
);
2129 if (flag_ira_loop_pressure
)
2130 /* There is no sense to keep this info because it was most
2131 probably outdated by subsequent passes. */
2133 free (invariant_table
);
2134 invariant_table
= NULL
;
2135 invariant_table_size
= 0;
2137 #ifdef ENABLE_CHECKING
2138 verify_flow_info ();