1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This implements the loop invariant motion pass. It is very simple
21 (no calls, no loads/stores, etc.). This should be sufficient to cleanup
22 things like address arithmetics -- other more complicated invariants should
23 be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
25 We proceed loop by loop -- it is simpler than trying to handle things
26 globally and should not lose much. First we inspect all sets inside loop
27 and create a dependency graph on insns (saying "to move this insn, you must
28 also move the following insns").
30 We then need to determine what to move. We estimate the number of registers
31 used and move as many invariants as possible while we still have enough free
32 registers. We prefer the expensive invariants.
34 Then we move the selected invariants out of the loop, creating a new
35 temporaries for them if necessary. */
39 #include "coretypes.h"
41 #include "hard-reg-set.h"
45 #include "basic-block.h"
53 #include "hash-table.h"
60 /* The data stored for the loop. */
64 struct loop
*outermost_exit
; /* The outermost exit of the loop. */
65 bool has_call
; /* True if the loop contains a call. */
66 /* Maximal register pressure inside loop for given register class
67 (defined only for the pressure classes). */
68 int max_reg_pressure
[N_REG_CLASSES
];
69 /* Loop regs referenced and live pseudo-registers. */
71 bitmap_head regs_live
;
74 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
76 /* The description of an use. */
80 rtx
*pos
; /* Position of the use. */
81 rtx insn
; /* The insn in that the use occurs. */
82 unsigned addr_use_p
; /* Whether the use occurs in an address. */
83 struct use
*next
; /* Next use in the list. */
86 /* The description of a def. */
90 struct use
*uses
; /* The list of uses that are uniquely reached
92 unsigned n_uses
; /* Number of such uses. */
93 unsigned n_addr_uses
; /* Number of uses in addresses. */
94 unsigned invno
; /* The corresponding invariant. */
97 /* The data stored for each invariant. */
101 /* The number of the invariant. */
104 /* The number of the invariant with the same value. */
107 /* If we moved the invariant out of the loop, the register that contains its
111 /* If we moved the invariant out of the loop, the original regno
112 that contained its value. */
115 /* The definition of the invariant. */
118 /* The insn in that it is defined. */
121 /* Whether it is always executed. */
122 bool always_executed
;
124 /* Whether to move the invariant. */
127 /* Whether the invariant is cheap when used as an address. */
130 /* Cost of the invariant. */
133 /* The invariants it depends on. */
136 /* Used for detecting already visited invariants during determining
137 costs of movements. */
141 /* Currently processed loop. */
142 static struct loop
*curr_loop
;
144 /* Table of invariants indexed by the df_ref uid field. */
146 static unsigned int invariant_table_size
= 0;
147 static struct invariant
** invariant_table
;
149 /* Entry for hash table of invariant expressions. */
151 struct invariant_expr_entry
154 struct invariant
*inv
;
160 enum machine_mode mode
;
166 /* The actual stamp for marking already visited invariants during determining
167 costs of movements. */
169 static unsigned actual_stamp
;
171 typedef struct invariant
*invariant_p
;
174 /* The invariants. */
176 static vec
<invariant_p
> invariants
;
178 /* Check the size of the invariant table and realloc if necessary. */
181 check_invariant_table_size (void)
183 if (invariant_table_size
< DF_DEFS_TABLE_SIZE ())
185 unsigned int new_size
= DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
186 invariant_table
= XRESIZEVEC (struct invariant
*, invariant_table
, new_size
);
187 memset (&invariant_table
[invariant_table_size
], 0,
188 (new_size
- invariant_table_size
) * sizeof (struct invariant
*));
189 invariant_table_size
= new_size
;
193 /* Test for possibility of invariantness of X. */
196 check_maybe_invariant (rtx x
)
198 enum rtx_code code
= GET_CODE (x
);
212 case UNSPEC_VOLATILE
:
220 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
221 It should not be hard, and might be faster than "elsewhere". */
223 /* Just handle the most trivial case where we load from an unchanging
224 location (most importantly, pic tables). */
225 if (MEM_READONLY_P (x
) && !MEM_VOLATILE_P (x
))
231 /* Don't mess with insns declared volatile. */
232 if (MEM_VOLATILE_P (x
))
240 fmt
= GET_RTX_FORMAT (code
);
241 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
245 if (!check_maybe_invariant (XEXP (x
, i
)))
248 else if (fmt
[i
] == 'E')
250 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
251 if (!check_maybe_invariant (XVECEXP (x
, i
, j
)))
259 /* Returns the invariant definition for USE, or NULL if USE is not
262 static struct invariant
*
263 invariant_for_use (df_ref use
)
265 struct df_link
*defs
;
267 basic_block bb
= DF_REF_BB (use
), def_bb
;
269 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
272 defs
= DF_REF_CHAIN (use
);
273 if (!defs
|| defs
->next
)
276 check_invariant_table_size ();
277 if (!invariant_table
[DF_REF_ID (def
)])
280 def_bb
= DF_REF_BB (def
);
281 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
283 return invariant_table
[DF_REF_ID (def
)];
286 /* Computes hash value for invariant expression X in INSN. */
289 hash_invariant_expr_1 (rtx insn
, rtx x
)
291 enum rtx_code code
= GET_CODE (x
);
294 hashval_t val
= code
;
297 struct invariant
*inv
;
305 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
308 use
= df_find_use (insn
, x
);
310 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
311 inv
= invariant_for_use (use
);
313 return hash_rtx (x
, GET_MODE (x
), &do_not_record_p
, NULL
, false);
315 gcc_assert (inv
->eqto
!= ~0u);
322 fmt
= GET_RTX_FORMAT (code
);
323 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
326 val
^= hash_invariant_expr_1 (insn
, XEXP (x
, i
));
327 else if (fmt
[i
] == 'E')
329 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
330 val
^= hash_invariant_expr_1 (insn
, XVECEXP (x
, i
, j
));
332 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
339 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
340 and INSN2 have always the same value. */
343 invariant_expr_equal_p (rtx insn1
, rtx e1
, rtx insn2
, rtx e2
)
345 enum rtx_code code
= GET_CODE (e1
);
349 struct invariant
*inv1
= NULL
, *inv2
= NULL
;
352 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
353 the other one. If both are VOIDmode, we rely on the caller of this
354 function to verify that their modes are the same. */
355 if (code
!= GET_CODE (e2
) || GET_MODE (e1
) != GET_MODE (e2
))
364 return rtx_equal_p (e1
, e2
);
367 use1
= df_find_use (insn1
, e1
);
368 use2
= df_find_use (insn2
, e2
);
370 inv1
= invariant_for_use (use1
);
372 inv2
= invariant_for_use (use2
);
375 return rtx_equal_p (e1
, e2
);
380 gcc_assert (inv1
->eqto
!= ~0u);
381 gcc_assert (inv2
->eqto
!= ~0u);
382 return inv1
->eqto
== inv2
->eqto
;
388 fmt
= GET_RTX_FORMAT (code
);
389 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
396 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
400 else if (fmt
[i
] == 'E')
402 if (XVECLEN (e1
, i
) != XVECLEN (e2
, i
))
405 for (j
= 0; j
< XVECLEN (e1
, i
); j
++)
407 sub1
= XVECEXP (e1
, i
, j
);
408 sub2
= XVECEXP (e2
, i
, j
);
410 if (!invariant_expr_equal_p (insn1
, sub1
, insn2
, sub2
))
414 else if (fmt
[i
] == 'i' || fmt
[i
] == 'n')
416 if (XINT (e1
, i
) != XINT (e2
, i
))
419 /* Unhandled type of subexpression, we fail conservatively. */
427 struct invariant_expr_hasher
: typed_free_remove
<invariant_expr_entry
>
429 typedef invariant_expr_entry value_type
;
430 typedef invariant_expr_entry compare_type
;
431 static inline hashval_t
hash (const value_type
*);
432 static inline bool equal (const value_type
*, const compare_type
*);
435 /* Returns hash value for invariant expression entry ENTRY. */
438 invariant_expr_hasher::hash (const value_type
*entry
)
443 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
446 invariant_expr_hasher::equal (const value_type
*entry1
,
447 const compare_type
*entry2
)
449 if (entry1
->mode
!= entry2
->mode
)
452 return invariant_expr_equal_p (entry1
->inv
->insn
, entry1
->expr
,
453 entry2
->inv
->insn
, entry2
->expr
);
456 typedef hash_table
<invariant_expr_hasher
> invariant_htab_type
;
458 /* Checks whether invariant with value EXPR in machine mode MODE is
459 recorded in EQ. If this is the case, return the invariant. Otherwise
460 insert INV to the table for this expression and return INV. */
462 static struct invariant
*
463 find_or_insert_inv (invariant_htab_type eq
, rtx expr
, enum machine_mode mode
,
464 struct invariant
*inv
)
466 hashval_t hash
= hash_invariant_expr_1 (inv
->insn
, expr
);
467 struct invariant_expr_entry
*entry
;
468 struct invariant_expr_entry pentry
;
469 invariant_expr_entry
**slot
;
474 slot
= eq
.find_slot_with_hash (&pentry
, hash
, INSERT
);
480 entry
= XNEW (struct invariant_expr_entry
);
490 /* Finds invariants identical to INV and records the equivalence. EQ is the
491 hash table of the invariants. */
494 find_identical_invariants (invariant_htab_type eq
, struct invariant
*inv
)
498 struct invariant
*dep
;
500 enum machine_mode mode
;
502 if (inv
->eqto
!= ~0u)
505 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
507 dep
= invariants
[depno
];
508 find_identical_invariants (eq
, dep
);
511 set
= single_set (inv
->insn
);
512 expr
= SET_SRC (set
);
513 mode
= GET_MODE (expr
);
514 if (mode
== VOIDmode
)
515 mode
= GET_MODE (SET_DEST (set
));
516 inv
->eqto
= find_or_insert_inv (eq
, expr
, mode
, inv
)->invno
;
518 if (dump_file
&& inv
->eqto
!= inv
->invno
)
520 "Invariant %d is equivalent to invariant %d.\n",
521 inv
->invno
, inv
->eqto
);
524 /* Find invariants with the same value and record the equivalences. */
527 merge_identical_invariants (void)
530 struct invariant
*inv
;
531 invariant_htab_type eq
;
532 eq
.create (invariants
.length ());
534 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
535 find_identical_invariants (eq
, inv
);
540 /* Determines the basic blocks inside LOOP that are always executed and
541 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
542 basic blocks that may either exit the loop, or contain the call that
543 does not have to return. BODY is body of the loop obtained by
544 get_loop_body_in_dom_order. */
547 compute_always_reached (struct loop
*loop
, basic_block
*body
,
548 bitmap may_exit
, bitmap always_reached
)
552 for (i
= 0; i
< loop
->num_nodes
; i
++)
554 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, body
[i
]))
555 bitmap_set_bit (always_reached
, i
);
557 if (bitmap_bit_p (may_exit
, i
))
562 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
563 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
564 additionally mark blocks that may exit due to a call. */
567 find_exits (struct loop
*loop
, basic_block
*body
,
568 bitmap may_exit
, bitmap has_exit
)
573 struct loop
*outermost_exit
= loop
, *aexit
;
574 bool has_call
= false;
577 for (i
= 0; i
< loop
->num_nodes
; i
++)
579 if (body
[i
]->loop_father
== loop
)
581 FOR_BB_INSNS (body
[i
], insn
)
584 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
585 || !RTL_CONST_OR_PURE_CALL_P (insn
)))
588 bitmap_set_bit (may_exit
, i
);
593 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
595 if (flow_bb_inside_loop_p (loop
, e
->dest
))
598 bitmap_set_bit (may_exit
, i
);
599 bitmap_set_bit (has_exit
, i
);
600 outermost_exit
= find_common_loop (outermost_exit
,
601 e
->dest
->loop_father
);
606 /* Use the data stored for the subloop to decide whether we may exit
607 through it. It is sufficient to do this for header of the loop,
608 as other basic blocks inside it must be dominated by it. */
609 if (body
[i
]->loop_father
->header
!= body
[i
])
612 if (LOOP_DATA (body
[i
]->loop_father
)->has_call
)
615 bitmap_set_bit (may_exit
, i
);
617 aexit
= LOOP_DATA (body
[i
]->loop_father
)->outermost_exit
;
620 bitmap_set_bit (may_exit
, i
);
621 bitmap_set_bit (has_exit
, i
);
623 if (flow_loop_nested_p (aexit
, outermost_exit
))
624 outermost_exit
= aexit
;
628 if (loop
->aux
== NULL
)
630 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
631 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
632 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
634 LOOP_DATA (loop
)->outermost_exit
= outermost_exit
;
635 LOOP_DATA (loop
)->has_call
= has_call
;
638 /* Check whether we may assign a value to X from a register. */
641 may_assign_reg_p (rtx x
)
643 return (GET_MODE (x
) != VOIDmode
644 && GET_MODE (x
) != BLKmode
645 && can_copy_p (GET_MODE (x
))
647 || !HARD_REGISTER_P (x
)
648 || REGNO_REG_CLASS (REGNO (x
)) != NO_REGS
));
651 /* Finds definitions that may correspond to invariants in LOOP with body
655 find_defs (struct loop
*loop
)
660 "*****starting processing of loop %d ******\n",
664 df_remove_problem (df_chain
);
665 df_process_deferred_rescans ();
666 df_chain_add_problem (DF_UD_CHAIN
);
667 df_set_flags (DF_RD_PRUNE_DEAD_DEFS
);
668 df_analyze_loop (loop
);
669 check_invariant_table_size ();
673 df_dump_region (dump_file
);
675 "*****ending processing of loop %d ******\n",
680 /* Creates a new invariant for definition DEF in INSN, depending on invariants
681 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
682 unless the program ends due to a function call. The newly created invariant
685 static struct invariant
*
686 create_new_invariant (struct def
*def
, rtx insn
, bitmap depends_on
,
687 bool always_executed
)
689 struct invariant
*inv
= XNEW (struct invariant
);
690 rtx set
= single_set (insn
);
691 bool speed
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn
));
694 inv
->always_executed
= always_executed
;
695 inv
->depends_on
= depends_on
;
697 /* If the set is simple, usually by moving it we move the whole store out of
698 the loop. Otherwise we save only cost of the computation. */
701 inv
->cost
= set_rtx_cost (set
, speed
);
702 /* ??? Try to determine cheapness of address computation. Unfortunately
703 the address cost is only a relative measure, we can't really compare
704 it with any absolute number, but only with other address costs.
705 But here we don't have any other addresses, so compare with a magic
706 number anyway. It has to be large enough to not regress PR33928
707 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
708 enough to not regress 410.bwaves either (by still moving reg+reg
710 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
711 inv
->cheap_address
= address_cost (SET_SRC (set
), word_mode
,
712 ADDR_SPACE_GENERIC
, speed
) < 3;
716 inv
->cost
= set_src_cost (SET_SRC (set
), speed
);
717 inv
->cheap_address
= false;
722 inv
->orig_regno
= -1;
726 inv
->invno
= invariants
.length ();
729 def
->invno
= inv
->invno
;
730 invariants
.safe_push (inv
);
735 "Set in insn %d is invariant (%d), cost %d, depends on ",
736 INSN_UID (insn
), inv
->invno
, inv
->cost
);
737 dump_bitmap (dump_file
, inv
->depends_on
);
743 /* Record USE at DEF. */
746 record_use (struct def
*def
, df_ref use
)
748 struct use
*u
= XNEW (struct use
);
750 u
->pos
= DF_REF_REAL_LOC (use
);
751 u
->insn
= DF_REF_INSN (use
);
752 u
->addr_use_p
= (DF_REF_TYPE (use
) == DF_REF_REG_MEM_LOAD
753 || DF_REF_TYPE (use
) == DF_REF_REG_MEM_STORE
);
761 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
762 bitmap. Returns true if all dependencies of USE are known to be
763 loop invariants, false otherwise. */
766 check_dependency (basic_block bb
, df_ref use
, bitmap depends_on
)
770 struct df_link
*defs
;
771 struct def
*def_data
;
772 struct invariant
*inv
;
774 if (DF_REF_FLAGS (use
) & DF_REF_READ_WRITE
)
777 defs
= DF_REF_CHAIN (use
);
780 unsigned int regno
= DF_REF_REGNO (use
);
782 /* If this is the use of an uninitialized argument register that is
783 likely to be spilled, do not move it lest this might extend its
784 lifetime and cause reload to die. This can occur for a call to
785 a function taking complex number arguments and moving the insns
786 preparing the arguments without moving the call itself wouldn't
787 gain much in practice. */
788 if ((DF_REF_FLAGS (use
) & DF_HARD_REG_LIVE
)
789 && FUNCTION_ARG_REGNO_P (regno
)
790 && targetm
.class_likely_spilled_p (REGNO_REG_CLASS (regno
)))
800 check_invariant_table_size ();
801 inv
= invariant_table
[DF_REF_ID (def
)];
806 gcc_assert (def_data
!= NULL
);
808 def_bb
= DF_REF_BB (def
);
809 /* Note that in case bb == def_bb, we know that the definition
810 dominates insn, because def has invariant_table[DF_REF_ID(def)]
811 defined and we process the insns in the basic block bb
813 if (!dominated_by_p (CDI_DOMINATORS
, bb
, def_bb
))
816 bitmap_set_bit (depends_on
, def_data
->invno
);
821 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
822 bitmap. Returns true if all dependencies of INSN are known to be
823 loop invariants, false otherwise. */
826 check_dependencies (rtx insn
, bitmap depends_on
)
828 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
830 basic_block bb
= BLOCK_FOR_INSN (insn
);
832 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
833 if (!check_dependency (bb
, use
, depends_on
))
835 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
836 if (!check_dependency (bb
, use
, depends_on
))
842 /* Pre-check candidate DEST to skip the one which can not make a valid insn
843 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
845 pre_check_invariant_p (bool simple
, rtx dest
)
847 if (simple
&& REG_P (dest
) && DF_REG_DEF_COUNT (REGNO (dest
)) > 1)
851 unsigned int i
= REGNO (dest
);
852 struct df_insn_info
*insn_info
;
855 for (use
= DF_REG_USE_CHAIN (i
); use
; use
= DF_REF_NEXT_REG (use
))
857 ref
= DF_REF_INSN (use
);
858 insn_info
= DF_INSN_INFO_GET (ref
);
860 FOR_EACH_INSN_INFO_DEF (def_rec
, insn_info
)
861 if (DF_REF_REGNO (def_rec
) == i
)
863 /* Multi definitions at this stage, most likely are due to
864 instruction constraints, which requires both read and write
865 on the same register. Since move_invariant_reg is not
866 powerful enough to handle such cases, just ignore the INV
867 and leave the chance to others. */
875 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
876 executed. ALWAYS_EXECUTED is true if the insn is always executed,
877 unless the program ends due to a function call. */
880 find_invariant_insn (rtx insn
, bool always_reached
, bool always_executed
)
887 struct invariant
*inv
;
890 /* We can't move a CC0 setter without the user. */
891 if (sets_cc0_p (insn
))
895 set
= single_set (insn
);
898 dest
= SET_DEST (set
);
901 || HARD_REGISTER_P (dest
))
904 if (!may_assign_reg_p (dest
)
905 || !pre_check_invariant_p (simple
, dest
)
906 || !check_maybe_invariant (SET_SRC (set
)))
909 /* If the insn can throw exception, we cannot move it at all without changing
911 if (can_throw_internal (insn
))
914 /* We cannot make trapping insn executed, unless it was executed before. */
915 if (may_trap_or_fault_p (PATTERN (insn
)) && !always_reached
)
918 depends_on
= BITMAP_ALLOC (NULL
);
919 if (!check_dependencies (insn
, depends_on
))
921 BITMAP_FREE (depends_on
);
926 def
= XCNEW (struct def
);
930 inv
= create_new_invariant (def
, insn
, depends_on
, always_executed
);
934 ref
= df_find_def (insn
, dest
);
935 check_invariant_table_size ();
936 invariant_table
[DF_REF_ID (ref
)] = inv
;
940 /* Record registers used in INSN that have a unique invariant definition. */
943 record_uses (rtx insn
)
945 struct df_insn_info
*insn_info
= DF_INSN_INFO_GET (insn
);
947 struct invariant
*inv
;
949 FOR_EACH_INSN_INFO_USE (use
, insn_info
)
951 inv
= invariant_for_use (use
);
953 record_use (inv
->def
, use
);
955 FOR_EACH_INSN_INFO_EQ_USE (use
, insn_info
)
957 inv
= invariant_for_use (use
);
959 record_use (inv
->def
, use
);
963 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
964 executed. ALWAYS_EXECUTED is true if the insn is always executed,
965 unless the program ends due to a function call. */
968 find_invariants_insn (rtx insn
, bool always_reached
, bool always_executed
)
970 find_invariant_insn (insn
, always_reached
, always_executed
);
974 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
975 basic block is always executed. ALWAYS_EXECUTED is true if the basic
976 block is always executed, unless the program ends due to a function
980 find_invariants_bb (basic_block bb
, bool always_reached
, bool always_executed
)
984 FOR_BB_INSNS (bb
, insn
)
986 if (!NONDEBUG_INSN_P (insn
))
989 find_invariants_insn (insn
, always_reached
, always_executed
);
993 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn
)
994 || ! RTL_CONST_OR_PURE_CALL_P (insn
)))
995 always_reached
= false;
999 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1000 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1001 bitmap of basic blocks in BODY that are always executed unless the program
1002 ends due to a function call. */
1005 find_invariants_body (struct loop
*loop
, basic_block
*body
,
1006 bitmap always_reached
, bitmap always_executed
)
1010 for (i
= 0; i
< loop
->num_nodes
; i
++)
1011 find_invariants_bb (body
[i
],
1012 bitmap_bit_p (always_reached
, i
),
1013 bitmap_bit_p (always_executed
, i
));
1016 /* Finds invariants in LOOP. */
1019 find_invariants (struct loop
*loop
)
1021 bitmap may_exit
= BITMAP_ALLOC (NULL
);
1022 bitmap always_reached
= BITMAP_ALLOC (NULL
);
1023 bitmap has_exit
= BITMAP_ALLOC (NULL
);
1024 bitmap always_executed
= BITMAP_ALLOC (NULL
);
1025 basic_block
*body
= get_loop_body_in_dom_order (loop
);
1027 find_exits (loop
, body
, may_exit
, has_exit
);
1028 compute_always_reached (loop
, body
, may_exit
, always_reached
);
1029 compute_always_reached (loop
, body
, has_exit
, always_executed
);
1032 find_invariants_body (loop
, body
, always_reached
, always_executed
);
1033 merge_identical_invariants ();
1035 BITMAP_FREE (always_reached
);
1036 BITMAP_FREE (always_executed
);
1037 BITMAP_FREE (may_exit
);
1038 BITMAP_FREE (has_exit
);
1042 /* Frees a list of uses USE. */
1045 free_use_list (struct use
*use
)
1049 for (; use
; use
= next
)
1056 /* Return pressure class and number of hard registers (through *NREGS)
1057 for destination of INSN. */
1058 static enum reg_class
1059 get_pressure_class_and_nregs (rtx insn
, int *nregs
)
1062 enum reg_class pressure_class
;
1063 rtx set
= single_set (insn
);
1065 /* Considered invariant insns have only one set. */
1066 gcc_assert (set
!= NULL_RTX
);
1067 reg
= SET_DEST (set
);
1068 if (GET_CODE (reg
) == SUBREG
)
1069 reg
= SUBREG_REG (reg
);
1073 pressure_class
= NO_REGS
;
1079 if (reg
== NULL_RTX
)
1080 pressure_class
= GENERAL_REGS
;
1083 pressure_class
= reg_allocno_class (REGNO (reg
));
1084 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1087 = ira_reg_class_max_nregs
[pressure_class
][GET_MODE (SET_SRC (set
))];
1089 return pressure_class
;
1092 /* Calculates cost and number of registers needed for moving invariant INV
1093 out of the loop and stores them to *COST and *REGS_NEEDED. */
1096 get_inv_cost (struct invariant
*inv
, int *comp_cost
, unsigned *regs_needed
)
1099 unsigned aregs_needed
[N_REG_CLASSES
];
1101 struct invariant
*dep
;
1104 /* Find the representative of the class of the equivalent invariants. */
1105 inv
= invariants
[inv
->eqto
];
1108 if (! flag_ira_loop_pressure
)
1112 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1113 regs_needed
[ira_pressure_classes
[i
]] = 0;
1117 || inv
->stamp
== actual_stamp
)
1119 inv
->stamp
= actual_stamp
;
1121 if (! flag_ira_loop_pressure
)
1126 enum reg_class pressure_class
;
1128 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1129 regs_needed
[pressure_class
] += nregs
;
1132 if (!inv
->cheap_address
1133 || inv
->def
->n_addr_uses
< inv
->def
->n_uses
)
1134 (*comp_cost
) += inv
->cost
;
1138 /* Hoisting constant pool constants into stack regs may cost more than
1139 just single register. On x87, the balance is affected both by the
1140 small number of FP registers, and by its register stack organization,
1141 that forces us to add compensation code in and around the loop to
1142 shuffle the operands to the top of stack before use, and pop them
1143 from the stack after the loop finishes.
1145 To model this effect, we increase the number of registers needed for
1146 stack registers by two: one register push, and one register pop.
1147 This usually has the effect that FP constant loads from the constant
1148 pool are not moved out of the loop.
1150 Note that this also means that dependent invariants can not be moved.
1151 However, the primary purpose of this pass is to move loop invariant
1152 address arithmetic out of loops, and address arithmetic that depends
1153 on floating point constants is unlikely to ever occur. */
1154 rtx set
= single_set (inv
->insn
);
1156 && IS_STACK_MODE (GET_MODE (SET_SRC (set
)))
1157 && constant_pool_constant_p (SET_SRC (set
)))
1159 if (flag_ira_loop_pressure
)
1160 regs_needed
[ira_stack_reg_pressure_class
] += 2;
1162 regs_needed
[0] += 2;
1167 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, depno
, bi
)
1171 dep
= invariants
[depno
];
1173 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1177 get_inv_cost (dep
, &acomp_cost
, aregs_needed
);
1179 if (! flag_ira_loop_pressure
)
1180 check_p
= aregs_needed
[0] != 0;
1183 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1184 if (aregs_needed
[ira_pressure_classes
[i
]] != 0)
1186 check_p
= i
< ira_pressure_classes_num
;
1189 /* We need to check always_executed, since if the original value of
1190 the invariant may be preserved, we may need to keep it in a
1191 separate register. TODO check whether the register has an
1192 use outside of the loop. */
1193 && dep
->always_executed
1194 && !dep
->def
->uses
->next
)
1196 /* If this is a single use, after moving the dependency we will not
1197 need a new register. */
1198 if (! flag_ira_loop_pressure
)
1203 enum reg_class pressure_class
;
1205 pressure_class
= get_pressure_class_and_nregs (inv
->insn
, &nregs
);
1206 aregs_needed
[pressure_class
] -= nregs
;
1210 if (! flag_ira_loop_pressure
)
1211 regs_needed
[0] += aregs_needed
[0];
1214 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1215 regs_needed
[ira_pressure_classes
[i
]]
1216 += aregs_needed
[ira_pressure_classes
[i
]];
1218 (*comp_cost
) += acomp_cost
;
1222 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1223 of registers used in the loop, NEW_REGS is the number of new variables
1224 already added due to the invariant motion. The number of registers needed
1225 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1226 through to estimate_reg_pressure_cost. */
1229 gain_for_invariant (struct invariant
*inv
, unsigned *regs_needed
,
1230 unsigned *new_regs
, unsigned regs_used
,
1231 bool speed
, bool call_p
)
1233 int comp_cost
, size_cost
;
1237 get_inv_cost (inv
, &comp_cost
, regs_needed
);
1239 if (! flag_ira_loop_pressure
)
1241 size_cost
= (estimate_reg_pressure_cost (new_regs
[0] + regs_needed
[0],
1242 regs_used
, speed
, call_p
)
1243 - estimate_reg_pressure_cost (new_regs
[0],
1244 regs_used
, speed
, call_p
));
1249 enum reg_class pressure_class
;
1251 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1253 pressure_class
= ira_pressure_classes
[i
];
1254 if ((int) new_regs
[pressure_class
]
1255 + (int) regs_needed
[pressure_class
]
1256 + LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1257 + IRA_LOOP_RESERVED_REGS
1258 > ira_class_hard_regs_num
[pressure_class
])
1261 if (i
< ira_pressure_classes_num
)
1262 /* There will be register pressure excess and we want not to
1263 make this loop invariant motion. All loop invariants with
1264 non-positive gains will be rejected in function
1265 find_invariants_to_move. Therefore we return the negative
1268 One could think that this rejects also expensive loop
1269 invariant motions and this will hurt code performance.
1270 However numerous experiments with different heuristics
1271 taking invariant cost into account did not confirm this
1272 assumption. There are possible explanations for this
1274 o probably all expensive invariants were already moved out
1275 of the loop by PRE and gimple invariant motion pass.
1276 o expensive invariant execution will be hidden by insn
1277 scheduling or OOO processor hardware because usually such
1278 invariants have a lot of freedom to be executed
1280 Another reason for ignoring invariant cost vs spilling cost
1281 heuristics is also in difficulties to evaluate accurately
1282 spill cost at this stage. */
1288 return comp_cost
- size_cost
;
1291 /* Finds invariant with best gain for moving. Returns the gain, stores
1292 the invariant in *BEST and number of registers needed for it to
1293 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1294 NEW_REGS is the number of new variables already added due to invariant
1298 best_gain_for_invariant (struct invariant
**best
, unsigned *regs_needed
,
1299 unsigned *new_regs
, unsigned regs_used
,
1300 bool speed
, bool call_p
)
1302 struct invariant
*inv
;
1303 int i
, gain
= 0, again
;
1304 unsigned aregs_needed
[N_REG_CLASSES
], invno
;
1306 FOR_EACH_VEC_ELT (invariants
, invno
, inv
)
1311 /* Only consider the "representatives" of equivalent invariants. */
1312 if (inv
->eqto
!= inv
->invno
)
1315 again
= gain_for_invariant (inv
, aregs_needed
, new_regs
, regs_used
,
1321 if (! flag_ira_loop_pressure
)
1322 regs_needed
[0] = aregs_needed
[0];
1325 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1326 regs_needed
[ira_pressure_classes
[i
]]
1327 = aregs_needed
[ira_pressure_classes
[i
]];
1335 /* Marks invariant INVNO and all its dependencies for moving. */
1338 set_move_mark (unsigned invno
, int gain
)
1340 struct invariant
*inv
= invariants
[invno
];
1343 /* Find the representative of the class of the equivalent invariants. */
1344 inv
= invariants
[inv
->eqto
];
1353 fprintf (dump_file
, "Decided to move invariant %d -- gain %d\n",
1356 fprintf (dump_file
, "Decided to move dependent invariant %d\n",
1360 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, invno
, bi
)
1362 set_move_mark (invno
, -1);
1366 /* Determines which invariants to move. */
1369 find_invariants_to_move (bool speed
, bool call_p
)
1372 unsigned i
, regs_used
, regs_needed
[N_REG_CLASSES
], new_regs
[N_REG_CLASSES
];
1373 struct invariant
*inv
= NULL
;
1375 if (!invariants
.length ())
1378 if (flag_ira_loop_pressure
)
1379 /* REGS_USED is actually never used when the flag is on. */
1382 /* We do not really do a good job in estimating number of
1383 registers used; we put some initial bound here to stand for
1384 induction variables etc. that we do not detect. */
1386 unsigned int n_regs
= DF_REG_SIZE (df
);
1390 for (i
= 0; i
< n_regs
; i
++)
1392 if (!DF_REGNO_FIRST_DEF (i
) && DF_REGNO_LAST_USE (i
))
1394 /* This is a value that is used but not changed inside loop. */
1400 if (! flag_ira_loop_pressure
)
1401 new_regs
[0] = regs_needed
[0] = 0;
1404 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1405 new_regs
[ira_pressure_classes
[i
]] = 0;
1407 while ((gain
= best_gain_for_invariant (&inv
, regs_needed
,
1408 new_regs
, regs_used
,
1409 speed
, call_p
)) > 0)
1411 set_move_mark (inv
->invno
, gain
);
1412 if (! flag_ira_loop_pressure
)
1413 new_regs
[0] += regs_needed
[0];
1416 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1417 new_regs
[ira_pressure_classes
[i
]]
1418 += regs_needed
[ira_pressure_classes
[i
]];
1423 /* Replace the uses, reached by the definition of invariant INV, by REG.
1425 IN_GROUP is nonzero if this is part of a group of changes that must be
1426 performed as a group. In that case, the changes will be stored. The
1427 function `apply_change_group' will validate and apply the changes. */
1430 replace_uses (struct invariant
*inv
, rtx reg
, bool in_group
)
1432 /* Replace the uses we know to be dominated. It saves work for copy
1433 propagation, and also it is necessary so that dependent invariants
1434 are computed right. */
1438 for (use
= inv
->def
->uses
; use
; use
= use
->next
)
1439 validate_change (use
->insn
, use
->pos
, reg
, true);
1441 /* If we aren't part of a larger group, apply the changes now. */
1443 return apply_change_group ();
1449 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1453 move_invariant_reg (struct loop
*loop
, unsigned invno
)
1455 struct invariant
*inv
= invariants
[invno
];
1456 struct invariant
*repr
= invariants
[inv
->eqto
];
1458 basic_block preheader
= loop_preheader_edge (loop
)->src
;
1459 rtx reg
, set
, dest
, note
;
1468 /* If this is a representative of the class of equivalent invariants,
1469 really move the invariant. Otherwise just replace its use with
1470 the register used for the representative. */
1473 if (inv
->depends_on
)
1475 EXECUTE_IF_SET_IN_BITMAP (inv
->depends_on
, 0, i
, bi
)
1477 if (!move_invariant_reg (loop
, i
))
1482 /* Move the set out of the loop. If the set is always executed (we could
1483 omit this condition if we know that the register is unused outside of
1484 the loop, but it does not seem worth finding out) and it has no uses
1485 that would not be dominated by it, we may just move it (TODO).
1486 Otherwise we need to create a temporary register. */
1487 set
= single_set (inv
->insn
);
1488 reg
= dest
= SET_DEST (set
);
1489 if (GET_CODE (reg
) == SUBREG
)
1490 reg
= SUBREG_REG (reg
);
1492 regno
= REGNO (reg
);
1494 reg
= gen_reg_rtx_and_attrs (dest
);
1496 /* Try replacing the destination by a new pseudoregister. */
1497 validate_change (inv
->insn
, &SET_DEST (set
), reg
, true);
1499 /* As well as all the dominated uses. */
1500 replace_uses (inv
, reg
, true);
1502 /* And validate all the changes. */
1503 if (!apply_change_group ())
1506 emit_insn_after (gen_move_insn (dest
, reg
), inv
->insn
);
1507 reorder_insns (inv
->insn
, inv
->insn
, BB_END (preheader
));
1509 /* If there is a REG_EQUAL note on the insn we just moved, and the
1510 insn is in a basic block that is not always executed or the note
1511 contains something for which we don't know the invariant status,
1512 the note may no longer be valid after we move the insn. Note that
1513 uses in REG_EQUAL notes are taken into account in the computation
1514 of invariants, so it is safe to retain the note even if it contains
1515 register references for which we know the invariant status. */
1516 if ((note
= find_reg_note (inv
->insn
, REG_EQUAL
, NULL_RTX
))
1517 && (!inv
->always_executed
1518 || !check_maybe_invariant (XEXP (note
, 0))))
1519 remove_note (inv
->insn
, note
);
1523 if (!move_invariant_reg (loop
, repr
->invno
))
1526 regno
= repr
->orig_regno
;
1527 if (!replace_uses (inv
, reg
, false))
1529 set
= single_set (inv
->insn
);
1530 emit_insn_after (gen_move_insn (SET_DEST (set
), reg
), inv
->insn
);
1531 delete_insn (inv
->insn
);
1535 inv
->orig_regno
= regno
;
1540 /* If we failed, clear move flag, so that we do not try to move inv
1543 fprintf (dump_file
, "Failed to move invariant %d\n", invno
);
1545 inv
->reg
= NULL_RTX
;
1546 inv
->orig_regno
= -1;
1551 /* Move selected invariant out of the LOOP. Newly created regs are marked
1552 in TEMPORARY_REGS. */
1555 move_invariants (struct loop
*loop
)
1557 struct invariant
*inv
;
1560 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1561 move_invariant_reg (loop
, i
);
1562 if (flag_ira_loop_pressure
&& resize_reg_info ())
1564 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1565 if (inv
->reg
!= NULL_RTX
)
1567 if (inv
->orig_regno
>= 0)
1568 setup_reg_classes (REGNO (inv
->reg
),
1569 reg_preferred_class (inv
->orig_regno
),
1570 reg_alternate_class (inv
->orig_regno
),
1571 reg_allocno_class (inv
->orig_regno
));
1573 setup_reg_classes (REGNO (inv
->reg
),
1574 GENERAL_REGS
, NO_REGS
, GENERAL_REGS
);
1579 /* Initializes invariant motion data. */
1582 init_inv_motion_data (void)
1586 invariants
.create (100);
1589 /* Frees the data allocated by invariant motion. */
1592 free_inv_motion_data (void)
1596 struct invariant
*inv
;
1598 check_invariant_table_size ();
1599 for (i
= 0; i
< DF_DEFS_TABLE_SIZE (); i
++)
1601 inv
= invariant_table
[i
];
1605 gcc_assert (def
!= NULL
);
1607 free_use_list (def
->uses
);
1609 invariant_table
[i
] = NULL
;
1613 FOR_EACH_VEC_ELT (invariants
, i
, inv
)
1615 BITMAP_FREE (inv
->depends_on
);
1618 invariants
.release ();
1621 /* Move the invariants out of the LOOP. */
1624 move_single_loop_invariants (struct loop
*loop
)
1626 init_inv_motion_data ();
1628 find_invariants (loop
);
1629 find_invariants_to_move (optimize_loop_for_speed_p (loop
),
1630 LOOP_DATA (loop
)->has_call
);
1631 move_invariants (loop
);
1633 free_inv_motion_data ();
1636 /* Releases the auxiliary data for LOOP. */
1639 free_loop_data (struct loop
*loop
)
1641 struct loop_data
*data
= LOOP_DATA (loop
);
1645 bitmap_clear (&LOOP_DATA (loop
)->regs_ref
);
1646 bitmap_clear (&LOOP_DATA (loop
)->regs_live
);
1653 /* Registers currently living. */
1654 static bitmap_head curr_regs_live
;
1656 /* Current reg pressure for each pressure class. */
1657 static int curr_reg_pressure
[N_REG_CLASSES
];
1659 /* Record all regs that are set in any one insn. Communication from
1660 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1661 all hard-registers. */
1662 static rtx regs_set
[(FIRST_PSEUDO_REGISTER
> MAX_RECOG_OPERANDS
1663 ? FIRST_PSEUDO_REGISTER
: MAX_RECOG_OPERANDS
) * 2];
1664 /* Number of regs stored in the previous array. */
1665 static int n_regs_set
;
1667 /* Return pressure class and number of needed hard registers (through
1668 *NREGS) of register REGNO. */
1669 static enum reg_class
1670 get_regno_pressure_class (int regno
, int *nregs
)
1672 if (regno
>= FIRST_PSEUDO_REGISTER
)
1674 enum reg_class pressure_class
;
1676 pressure_class
= reg_allocno_class (regno
);
1677 pressure_class
= ira_pressure_class_translate
[pressure_class
];
1679 = ira_reg_class_max_nregs
[pressure_class
][PSEUDO_REGNO_MODE (regno
)];
1680 return pressure_class
;
1682 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs
, regno
)
1683 && ! TEST_HARD_REG_BIT (eliminable_regset
, regno
))
1686 return ira_pressure_class_translate
[REGNO_REG_CLASS (regno
)];
1695 /* Increase (if INCR_P) or decrease current register pressure for
1698 change_pressure (int regno
, bool incr_p
)
1701 enum reg_class pressure_class
;
1703 pressure_class
= get_regno_pressure_class (regno
, &nregs
);
1705 curr_reg_pressure
[pressure_class
] -= nregs
;
1708 curr_reg_pressure
[pressure_class
] += nregs
;
1709 if (LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1710 < curr_reg_pressure
[pressure_class
])
1711 LOOP_DATA (curr_loop
)->max_reg_pressure
[pressure_class
]
1712 = curr_reg_pressure
[pressure_class
];
1716 /* Mark REGNO birth. */
1718 mark_regno_live (int regno
)
1722 for (loop
= curr_loop
;
1723 loop
!= current_loops
->tree_root
;
1724 loop
= loop_outer (loop
))
1725 bitmap_set_bit (&LOOP_DATA (loop
)->regs_live
, regno
);
1726 if (!bitmap_set_bit (&curr_regs_live
, regno
))
1728 change_pressure (regno
, true);
1731 /* Mark REGNO death. */
1733 mark_regno_death (int regno
)
1735 if (! bitmap_clear_bit (&curr_regs_live
, regno
))
1737 change_pressure (regno
, false);
1740 /* Mark setting register REG. */
1742 mark_reg_store (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
,
1743 void *data ATTRIBUTE_UNUSED
)
1747 if (GET_CODE (reg
) == SUBREG
)
1748 reg
= SUBREG_REG (reg
);
1753 regs_set
[n_regs_set
++] = reg
;
1755 regno
= REGNO (reg
);
1757 if (regno
>= FIRST_PSEUDO_REGISTER
)
1758 mark_regno_live (regno
);
1761 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1763 while (regno
< last
)
1765 mark_regno_live (regno
);
1771 /* Mark clobbering register REG. */
1773 mark_reg_clobber (rtx reg
, const_rtx setter
, void *data
)
1775 if (GET_CODE (setter
) == CLOBBER
)
1776 mark_reg_store (reg
, setter
, data
);
1779 /* Mark register REG death. */
1781 mark_reg_death (rtx reg
)
1783 int regno
= REGNO (reg
);
1785 if (regno
>= FIRST_PSEUDO_REGISTER
)
1786 mark_regno_death (regno
);
1789 int last
= regno
+ hard_regno_nregs
[regno
][GET_MODE (reg
)];
1791 while (regno
< last
)
1793 mark_regno_death (regno
);
1799 /* Mark occurrence of registers in X for the current loop. */
1801 mark_ref_regs (rtx x
)
1810 code
= GET_CODE (x
);
1815 for (loop
= curr_loop
;
1816 loop
!= current_loops
->tree_root
;
1817 loop
= loop_outer (loop
))
1818 bitmap_set_bit (&LOOP_DATA (loop
)->regs_ref
, REGNO (x
));
1822 fmt
= GET_RTX_FORMAT (code
);
1823 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1825 mark_ref_regs (XEXP (x
, i
));
1826 else if (fmt
[i
] == 'E')
1830 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1831 mark_ref_regs (XVECEXP (x
, i
, j
));
1835 /* Calculate register pressure in the loops. */
1837 calculate_loop_reg_pressure (void)
1844 struct loop
*loop
, *parent
;
1846 FOR_EACH_LOOP (loop
, 0)
1847 if (loop
->aux
== NULL
)
1849 loop
->aux
= xcalloc (1, sizeof (struct loop_data
));
1850 bitmap_initialize (&LOOP_DATA (loop
)->regs_ref
, ®_obstack
);
1851 bitmap_initialize (&LOOP_DATA (loop
)->regs_live
, ®_obstack
);
1853 ira_setup_eliminable_regset ();
1854 bitmap_initialize (&curr_regs_live
, ®_obstack
);
1855 FOR_EACH_BB_FN (bb
, cfun
)
1857 curr_loop
= bb
->loop_father
;
1858 if (curr_loop
== current_loops
->tree_root
)
1861 for (loop
= curr_loop
;
1862 loop
!= current_loops
->tree_root
;
1863 loop
= loop_outer (loop
))
1864 bitmap_ior_into (&LOOP_DATA (loop
)->regs_live
, DF_LR_IN (bb
));
1866 bitmap_copy (&curr_regs_live
, DF_LR_IN (bb
));
1867 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
1868 curr_reg_pressure
[ira_pressure_classes
[i
]] = 0;
1869 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live
, 0, j
, bi
)
1870 change_pressure (j
, true);
1872 FOR_BB_INSNS (bb
, insn
)
1874 if (! NONDEBUG_INSN_P (insn
))
1877 mark_ref_regs (PATTERN (insn
));
1879 note_stores (PATTERN (insn
), mark_reg_clobber
, NULL
);
1881 /* Mark any registers dead after INSN as dead now. */
1883 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1884 if (REG_NOTE_KIND (link
) == REG_DEAD
)
1885 mark_reg_death (XEXP (link
, 0));
1887 /* Mark any registers set in INSN as live,
1888 and mark them as conflicting with all other live regs.
1889 Clobbers are processed again, so they conflict with
1890 the registers that are set. */
1892 note_stores (PATTERN (insn
), mark_reg_store
, NULL
);
1895 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
1896 if (REG_NOTE_KIND (link
) == REG_INC
)
1897 mark_reg_store (XEXP (link
, 0), NULL_RTX
, NULL
);
1899 while (n_regs_set
-- > 0)
1901 rtx note
= find_regno_note (insn
, REG_UNUSED
,
1902 REGNO (regs_set
[n_regs_set
]));
1906 mark_reg_death (XEXP (note
, 0));
1910 bitmap_clear (&curr_regs_live
);
1911 if (flag_ira_region
== IRA_REGION_MIXED
1912 || flag_ira_region
== IRA_REGION_ALL
)
1913 FOR_EACH_LOOP (loop
, 0)
1915 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1916 if (! bitmap_bit_p (&LOOP_DATA (loop
)->regs_ref
, j
))
1918 enum reg_class pressure_class
;
1921 pressure_class
= get_regno_pressure_class (j
, &nregs
);
1922 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] -= nregs
;
1925 if (dump_file
== NULL
)
1927 FOR_EACH_LOOP (loop
, 0)
1929 parent
= loop_outer (loop
);
1930 fprintf (dump_file
, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
1931 loop
->num
, (parent
== NULL
? -1 : parent
->num
),
1932 loop
->header
->index
, loop_depth (loop
));
1933 fprintf (dump_file
, "\n ref. regnos:");
1934 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_ref
, 0, j
, bi
)
1935 fprintf (dump_file
, " %d", j
);
1936 fprintf (dump_file
, "\n live regnos:");
1937 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop
)->regs_live
, 0, j
, bi
)
1938 fprintf (dump_file
, " %d", j
);
1939 fprintf (dump_file
, "\n Pressure:");
1940 for (i
= 0; (int) i
< ira_pressure_classes_num
; i
++)
1942 enum reg_class pressure_class
;
1944 pressure_class
= ira_pressure_classes
[i
];
1945 if (LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
] == 0)
1947 fprintf (dump_file
, " %s=%d", reg_class_names
[pressure_class
],
1948 LOOP_DATA (loop
)->max_reg_pressure
[pressure_class
]);
1950 fprintf (dump_file
, "\n");
1956 /* Move the invariants out of the loops. */
1959 move_loop_invariants (void)
1963 if (flag_ira_loop_pressure
)
1966 regstat_init_n_sets_and_refs ();
1967 ira_set_pseudo_classes (true, dump_file
);
1968 calculate_loop_reg_pressure ();
1969 regstat_free_n_sets_and_refs ();
1971 df_set_flags (DF_EQ_NOTES
+ DF_DEFER_INSN_RESCAN
);
1972 /* Process the loops, innermost first. */
1973 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1976 /* move_single_loop_invariants for very large loops
1977 is time consuming and might need a lot of memory. */
1978 if (loop
->num_nodes
<= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP
)
1979 move_single_loop_invariants (loop
);
1982 FOR_EACH_LOOP (loop
, 0)
1984 free_loop_data (loop
);
1987 if (flag_ira_loop_pressure
)
1988 /* There is no sense to keep this info because it was most
1989 probably outdated by subsequent passes. */
1991 free (invariant_table
);
1992 invariant_table
= NULL
;
1993 invariant_table_size
= 0;
1995 #ifdef ENABLE_CHECKING
1996 verify_flow_info ();