PR c++/85952
[official-gcc.git] / gcc / loop-invariant.c
blobe3b2eda1695d6b80202ced7c23847a39ee4a3aa3
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2018 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
9 later version.
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
14 for more details.
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. */
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "backend.h"
41 #include "target.h"
42 #include "rtl.h"
43 #include "tree.h"
44 #include "cfghooks.h"
45 #include "df.h"
46 #include "memmodel.h"
47 #include "tm_p.h"
48 #include "insn-config.h"
49 #include "regs.h"
50 #include "ira.h"
51 #include "recog.h"
52 #include "cfgrtl.h"
53 #include "cfgloop.h"
54 #include "expr.h"
55 #include "params.h"
56 #include "rtl-iter.h"
57 #include "dumpfile.h"
59 /* The data stored for the loop. */
61 struct loop_data
63 struct loop *outermost_exit; /* The outermost exit of the loop. */
64 bool has_call; /* True if the loop contains a call. */
65 /* Maximal register pressure inside loop for given register class
66 (defined only for the pressure classes). */
67 int max_reg_pressure[N_REG_CLASSES];
68 /* Loop regs referenced and live pseudo-registers. */
69 bitmap_head regs_ref;
70 bitmap_head regs_live;
73 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
75 /* The description of an use. */
77 struct use
79 rtx *pos; /* Position of the use. */
80 rtx_insn *insn; /* The insn in that the use occurs. */
81 unsigned addr_use_p; /* Whether the use occurs in an address. */
82 struct use *next; /* Next use in the list. */
85 /* The description of a def. */
87 struct def
89 struct use *uses; /* The list of uses that are uniquely reached
90 by it. */
91 unsigned n_uses; /* Number of such uses. */
92 unsigned n_addr_uses; /* Number of uses in addresses. */
93 unsigned invno; /* The corresponding invariant. */
94 bool can_prop_to_addr_uses; /* True if the corresponding inv can be
95 propagated into its address uses. */
98 /* The data stored for each invariant. */
100 struct invariant
102 /* The number of the invariant. */
103 unsigned invno;
105 /* The number of the invariant with the same value. */
106 unsigned eqto;
108 /* The number of invariants which eqto this. */
109 unsigned eqno;
111 /* If we moved the invariant out of the loop, the original regno
112 that contained its value. */
113 int orig_regno;
115 /* If we moved the invariant out of the loop, the register that contains its
116 value. */
117 rtx reg;
119 /* The definition of the invariant. */
120 struct def *def;
122 /* The insn in that it is defined. */
123 rtx_insn *insn;
125 /* Whether it is always executed. */
126 bool always_executed;
128 /* Whether to move the invariant. */
129 bool move;
131 /* Whether the invariant is cheap when used as an address. */
132 bool cheap_address;
134 /* Cost of the invariant. */
135 unsigned cost;
137 /* Used for detecting already visited invariants during determining
138 costs of movements. */
139 unsigned stamp;
141 /* The invariants it depends on. */
142 bitmap depends_on;
145 /* Currently processed loop. */
146 static struct loop *curr_loop;
148 /* Table of invariants indexed by the df_ref uid field. */
150 static unsigned int invariant_table_size = 0;
151 static struct invariant ** invariant_table;
153 /* Entry for hash table of invariant expressions. */
155 struct invariant_expr_entry
157 /* The invariant. */
158 struct invariant *inv;
160 /* Its value. */
161 rtx expr;
163 /* Its mode. */
164 machine_mode mode;
166 /* Its hash. */
167 hashval_t hash;
170 /* The actual stamp for marking already visited invariants during determining
171 costs of movements. */
173 static unsigned actual_stamp;
175 typedef struct invariant *invariant_p;
178 /* The invariants. */
180 static vec<invariant_p> invariants;
182 /* Check the size of the invariant table and realloc if necessary. */
184 static void
185 check_invariant_table_size (void)
187 if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
189 unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
190 invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
191 memset (&invariant_table[invariant_table_size], 0,
192 (new_size - invariant_table_size) * sizeof (struct invariant *));
193 invariant_table_size = new_size;
197 /* Test for possibility of invariantness of X. */
199 static bool
200 check_maybe_invariant (rtx x)
202 enum rtx_code code = GET_CODE (x);
203 int i, j;
204 const char *fmt;
206 switch (code)
208 CASE_CONST_ANY:
209 case SYMBOL_REF:
210 case CONST:
211 case LABEL_REF:
212 return true;
214 case PC:
215 case CC0:
216 case UNSPEC_VOLATILE:
217 case CALL:
218 return false;
220 case REG:
221 return true;
223 case MEM:
224 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
225 It should not be hard, and might be faster than "elsewhere". */
227 /* Just handle the most trivial case where we load from an unchanging
228 location (most importantly, pic tables). */
229 if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
230 break;
232 return false;
234 case ASM_OPERANDS:
235 /* Don't mess with insns declared volatile. */
236 if (MEM_VOLATILE_P (x))
237 return false;
238 break;
240 default:
241 break;
244 fmt = GET_RTX_FORMAT (code);
245 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
247 if (fmt[i] == 'e')
249 if (!check_maybe_invariant (XEXP (x, i)))
250 return false;
252 else if (fmt[i] == 'E')
254 for (j = 0; j < XVECLEN (x, i); j++)
255 if (!check_maybe_invariant (XVECEXP (x, i, j)))
256 return false;
260 return true;
263 /* Returns the invariant definition for USE, or NULL if USE is not
264 invariant. */
266 static struct invariant *
267 invariant_for_use (df_ref use)
269 struct df_link *defs;
270 df_ref def;
271 basic_block bb = DF_REF_BB (use), def_bb;
273 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
274 return NULL;
276 defs = DF_REF_CHAIN (use);
277 if (!defs || defs->next)
278 return NULL;
279 def = defs->ref;
280 check_invariant_table_size ();
281 if (!invariant_table[DF_REF_ID (def)])
282 return NULL;
284 def_bb = DF_REF_BB (def);
285 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
286 return NULL;
287 return invariant_table[DF_REF_ID (def)];
290 /* Computes hash value for invariant expression X in INSN. */
292 static hashval_t
293 hash_invariant_expr_1 (rtx_insn *insn, rtx x)
295 enum rtx_code code = GET_CODE (x);
296 int i, j;
297 const char *fmt;
298 hashval_t val = code;
299 int do_not_record_p;
300 df_ref use;
301 struct invariant *inv;
303 switch (code)
305 CASE_CONST_ANY:
306 case SYMBOL_REF:
307 case CONST:
308 case LABEL_REF:
309 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
311 case REG:
312 use = df_find_use (insn, x);
313 if (!use)
314 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
315 inv = invariant_for_use (use);
316 if (!inv)
317 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
319 gcc_assert (inv->eqto != ~0u);
320 return inv->eqto;
322 default:
323 break;
326 fmt = GET_RTX_FORMAT (code);
327 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
329 if (fmt[i] == 'e')
330 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
331 else if (fmt[i] == 'E')
333 for (j = 0; j < XVECLEN (x, i); j++)
334 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
336 else if (fmt[i] == 'i' || fmt[i] == 'n')
337 val ^= XINT (x, i);
338 else if (fmt[i] == 'p')
339 val ^= constant_lower_bound (SUBREG_BYTE (x));
342 return val;
345 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
346 and INSN2 have always the same value. */
348 static bool
349 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
351 enum rtx_code code = GET_CODE (e1);
352 int i, j;
353 const char *fmt;
354 df_ref use1, use2;
355 struct invariant *inv1 = NULL, *inv2 = NULL;
356 rtx sub1, sub2;
358 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
359 the other one. If both are VOIDmode, we rely on the caller of this
360 function to verify that their modes are the same. */
361 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
362 return false;
364 switch (code)
366 CASE_CONST_ANY:
367 case SYMBOL_REF:
368 case CONST:
369 case LABEL_REF:
370 return rtx_equal_p (e1, e2);
372 case REG:
373 use1 = df_find_use (insn1, e1);
374 use2 = df_find_use (insn2, e2);
375 if (use1)
376 inv1 = invariant_for_use (use1);
377 if (use2)
378 inv2 = invariant_for_use (use2);
380 if (!inv1 && !inv2)
381 return rtx_equal_p (e1, e2);
383 if (!inv1 || !inv2)
384 return false;
386 gcc_assert (inv1->eqto != ~0u);
387 gcc_assert (inv2->eqto != ~0u);
388 return inv1->eqto == inv2->eqto;
390 default:
391 break;
394 fmt = GET_RTX_FORMAT (code);
395 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
397 if (fmt[i] == 'e')
399 sub1 = XEXP (e1, i);
400 sub2 = XEXP (e2, i);
402 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
403 return false;
406 else if (fmt[i] == 'E')
408 if (XVECLEN (e1, i) != XVECLEN (e2, i))
409 return false;
411 for (j = 0; j < XVECLEN (e1, i); j++)
413 sub1 = XVECEXP (e1, i, j);
414 sub2 = XVECEXP (e2, i, j);
416 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
417 return false;
420 else if (fmt[i] == 'i' || fmt[i] == 'n')
422 if (XINT (e1, i) != XINT (e2, i))
423 return false;
425 else if (fmt[i] == 'p')
427 if (maybe_ne (SUBREG_BYTE (e1), SUBREG_BYTE (e2)))
428 return false;
430 /* Unhandled type of subexpression, we fail conservatively. */
431 else
432 return false;
435 return true;
438 struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
440 static inline hashval_t hash (const invariant_expr_entry *);
441 static inline bool equal (const invariant_expr_entry *,
442 const invariant_expr_entry *);
445 /* Returns hash value for invariant expression entry ENTRY. */
447 inline hashval_t
448 invariant_expr_hasher::hash (const invariant_expr_entry *entry)
450 return entry->hash;
453 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
455 inline bool
456 invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
457 const invariant_expr_entry *entry2)
459 if (entry1->mode != entry2->mode)
460 return 0;
462 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
463 entry2->inv->insn, entry2->expr);
466 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
468 /* Checks whether invariant with value EXPR in machine mode MODE is
469 recorded in EQ. If this is the case, return the invariant. Otherwise
470 insert INV to the table for this expression and return INV. */
472 static struct invariant *
473 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
474 struct invariant *inv)
476 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
477 struct invariant_expr_entry *entry;
478 struct invariant_expr_entry pentry;
479 invariant_expr_entry **slot;
481 pentry.expr = expr;
482 pentry.inv = inv;
483 pentry.mode = mode;
484 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
485 entry = *slot;
487 if (entry)
488 return entry->inv;
490 entry = XNEW (struct invariant_expr_entry);
491 entry->inv = inv;
492 entry->expr = expr;
493 entry->mode = mode;
494 entry->hash = hash;
495 *slot = entry;
497 return inv;
500 /* Finds invariants identical to INV and records the equivalence. EQ is the
501 hash table of the invariants. */
503 static void
504 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
506 unsigned depno;
507 bitmap_iterator bi;
508 struct invariant *dep;
509 rtx expr, set;
510 machine_mode mode;
511 struct invariant *tmp;
513 if (inv->eqto != ~0u)
514 return;
516 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
518 dep = invariants[depno];
519 find_identical_invariants (eq, dep);
522 set = single_set (inv->insn);
523 expr = SET_SRC (set);
524 mode = GET_MODE (expr);
525 if (mode == VOIDmode)
526 mode = GET_MODE (SET_DEST (set));
528 tmp = find_or_insert_inv (eq, expr, mode, inv);
529 inv->eqto = tmp->invno;
531 if (tmp->invno != inv->invno && inv->always_executed)
532 tmp->eqno++;
534 if (dump_file && inv->eqto != inv->invno)
535 fprintf (dump_file,
536 "Invariant %d is equivalent to invariant %d.\n",
537 inv->invno, inv->eqto);
540 /* Find invariants with the same value and record the equivalences. */
542 static void
543 merge_identical_invariants (void)
545 unsigned i;
546 struct invariant *inv;
547 invariant_htab_type eq (invariants.length ());
549 FOR_EACH_VEC_ELT (invariants, i, inv)
550 find_identical_invariants (&eq, inv);
553 /* Determines the basic blocks inside LOOP that are always executed and
554 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
555 basic blocks that may either exit the loop, or contain the call that
556 does not have to return. BODY is body of the loop obtained by
557 get_loop_body_in_dom_order. */
559 static void
560 compute_always_reached (struct loop *loop, basic_block *body,
561 bitmap may_exit, bitmap always_reached)
563 unsigned i;
565 for (i = 0; i < loop->num_nodes; i++)
567 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
568 bitmap_set_bit (always_reached, i);
570 if (bitmap_bit_p (may_exit, i))
571 return;
575 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
576 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
577 additionally mark blocks that may exit due to a call. */
579 static void
580 find_exits (struct loop *loop, basic_block *body,
581 bitmap may_exit, bitmap has_exit)
583 unsigned i;
584 edge_iterator ei;
585 edge e;
586 struct loop *outermost_exit = loop, *aexit;
587 bool has_call = false;
588 rtx_insn *insn;
590 for (i = 0; i < loop->num_nodes; i++)
592 if (body[i]->loop_father == loop)
594 FOR_BB_INSNS (body[i], insn)
596 if (CALL_P (insn)
597 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
598 || !RTL_CONST_OR_PURE_CALL_P (insn)))
600 has_call = true;
601 bitmap_set_bit (may_exit, i);
602 break;
606 FOR_EACH_EDGE (e, ei, body[i]->succs)
608 if (! flow_bb_inside_loop_p (loop, e->dest))
610 bitmap_set_bit (may_exit, i);
611 bitmap_set_bit (has_exit, i);
612 outermost_exit = find_common_loop (outermost_exit,
613 e->dest->loop_father);
615 /* If we enter a subloop that might never terminate treat
616 it like a possible exit. */
617 if (flow_loop_nested_p (loop, e->dest->loop_father))
618 bitmap_set_bit (may_exit, i);
620 continue;
623 /* Use the data stored for the subloop to decide whether we may exit
624 through it. It is sufficient to do this for header of the loop,
625 as other basic blocks inside it must be dominated by it. */
626 if (body[i]->loop_father->header != body[i])
627 continue;
629 if (LOOP_DATA (body[i]->loop_father)->has_call)
631 has_call = true;
632 bitmap_set_bit (may_exit, i);
634 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
635 if (aexit != loop)
637 bitmap_set_bit (may_exit, i);
638 bitmap_set_bit (has_exit, i);
640 if (flow_loop_nested_p (aexit, outermost_exit))
641 outermost_exit = aexit;
645 if (loop->aux == NULL)
647 loop->aux = xcalloc (1, sizeof (struct loop_data));
648 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
649 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
651 LOOP_DATA (loop)->outermost_exit = outermost_exit;
652 LOOP_DATA (loop)->has_call = has_call;
655 /* Check whether we may assign a value to X from a register. */
657 static bool
658 may_assign_reg_p (rtx x)
660 return (GET_MODE (x) != VOIDmode
661 && GET_MODE (x) != BLKmode
662 && can_copy_p (GET_MODE (x))
663 /* Do not mess with the frame pointer adjustments that can
664 be generated e.g. by expand_builtin_setjmp_receiver. */
665 && x != frame_pointer_rtx
666 && (!REG_P (x)
667 || !HARD_REGISTER_P (x)
668 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
671 /* Finds definitions that may correspond to invariants in LOOP with body
672 BODY. */
674 static void
675 find_defs (struct loop *loop)
677 if (dump_file)
679 fprintf (dump_file,
680 "*****starting processing of loop %d ******\n",
681 loop->num);
684 df_remove_problem (df_chain);
685 df_process_deferred_rescans ();
686 df_chain_add_problem (DF_UD_CHAIN);
687 df_live_add_problem ();
688 df_live_set_all_dirty ();
689 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
690 df_analyze_loop (loop);
691 check_invariant_table_size ();
693 if (dump_file)
695 df_dump_region (dump_file);
696 fprintf (dump_file,
697 "*****ending processing of loop %d ******\n",
698 loop->num);
702 /* Creates a new invariant for definition DEF in INSN, depending on invariants
703 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
704 unless the program ends due to a function call. The newly created invariant
705 is returned. */
707 static struct invariant *
708 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
709 bool always_executed)
711 struct invariant *inv = XNEW (struct invariant);
712 rtx set = single_set (insn);
713 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
715 inv->def = def;
716 inv->always_executed = always_executed;
717 inv->depends_on = depends_on;
719 /* If the set is simple, usually by moving it we move the whole store out of
720 the loop. Otherwise we save only cost of the computation. */
721 if (def)
723 inv->cost = set_rtx_cost (set, speed);
724 /* ??? Try to determine cheapness of address computation. Unfortunately
725 the address cost is only a relative measure, we can't really compare
726 it with any absolute number, but only with other address costs.
727 But here we don't have any other addresses, so compare with a magic
728 number anyway. It has to be large enough to not regress PR33928
729 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
730 enough to not regress 410.bwaves either (by still moving reg+reg
731 invariants).
732 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
733 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
734 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
735 ADDR_SPACE_GENERIC, speed) < 3;
736 else
737 inv->cheap_address = false;
739 else
741 inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
742 speed);
743 inv->cheap_address = false;
746 inv->move = false;
747 inv->reg = NULL_RTX;
748 inv->orig_regno = -1;
749 inv->stamp = 0;
750 inv->insn = insn;
752 inv->invno = invariants.length ();
753 inv->eqto = ~0u;
755 /* Itself. */
756 inv->eqno = 1;
758 if (def)
759 def->invno = inv->invno;
760 invariants.safe_push (inv);
762 if (dump_file)
764 fprintf (dump_file,
765 "Set in insn %d is invariant (%d), cost %d, depends on ",
766 INSN_UID (insn), inv->invno, inv->cost);
767 dump_bitmap (dump_file, inv->depends_on);
770 return inv;
773 /* Return a canonical version of X for the address, from the point of view,
774 that all multiplications are represented as MULT instead of the multiply
775 by a power of 2 being represented as ASHIFT.
777 Callers should prepare a copy of X because this function may modify it
778 in place. */
780 static void
781 canonicalize_address_mult (rtx x)
783 subrtx_var_iterator::array_type array;
784 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
786 rtx sub = *iter;
787 scalar_int_mode sub_mode;
788 if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
789 && GET_CODE (sub) == ASHIFT
790 && CONST_INT_P (XEXP (sub, 1))
791 && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
792 && INTVAL (XEXP (sub, 1)) >= 0)
794 HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
795 PUT_CODE (sub, MULT);
796 XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
797 iter.skip_subrtxes ();
802 /* Maximum number of sub expressions in address. We set it to
803 a small integer since it's unlikely to have a complicated
804 address expression. */
806 #define MAX_CANON_ADDR_PARTS (5)
808 /* Collect sub expressions in address X with PLUS as the seperator.
809 Sub expressions are stored in vector ADDR_PARTS. */
811 static void
812 collect_address_parts (rtx x, vec<rtx> *addr_parts)
814 subrtx_var_iterator::array_type array;
815 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
817 rtx sub = *iter;
819 if (GET_CODE (sub) != PLUS)
821 addr_parts->safe_push (sub);
822 iter.skip_subrtxes ();
827 /* Compare function for sorting sub expressions X and Y based on
828 precedence defined for communitive operations. */
830 static int
831 compare_address_parts (const void *x, const void *y)
833 const rtx *rx = (const rtx *)x;
834 const rtx *ry = (const rtx *)y;
835 int px = commutative_operand_precedence (*rx);
836 int py = commutative_operand_precedence (*ry);
838 return (py - px);
841 /* Return a canonical version address for X by following steps:
842 1) Rewrite ASHIFT into MULT recursively.
843 2) Divide address into sub expressions with PLUS as the
844 separator.
845 3) Sort sub expressions according to precedence defined
846 for communative operations.
847 4) Simplify CONST_INT_P sub expressions.
848 5) Create new canonicalized address and return.
849 Callers should prepare a copy of X because this function may
850 modify it in place. */
852 static rtx
853 canonicalize_address (rtx x)
855 rtx res;
856 unsigned int i, j;
857 machine_mode mode = GET_MODE (x);
858 auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
860 /* Rewrite ASHIFT into MULT. */
861 canonicalize_address_mult (x);
862 /* Divide address into sub expressions. */
863 collect_address_parts (x, &addr_parts);
864 /* Unlikely to have very complicated address. */
865 if (addr_parts.length () < 2
866 || addr_parts.length () > MAX_CANON_ADDR_PARTS)
867 return x;
869 /* Sort sub expressions according to canonicalization precedence. */
870 addr_parts.qsort (compare_address_parts);
872 /* Simplify all constant int summary if possible. */
873 for (i = 0; i < addr_parts.length (); i++)
874 if (CONST_INT_P (addr_parts[i]))
875 break;
877 for (j = i + 1; j < addr_parts.length (); j++)
879 gcc_assert (CONST_INT_P (addr_parts[j]));
880 addr_parts[i] = simplify_gen_binary (PLUS, mode,
881 addr_parts[i],
882 addr_parts[j]);
885 /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
886 res = addr_parts[0];
887 for (j = 1; j < i; j++)
888 res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
890 /* Pickup the last CONST_INT_P sub expression. */
891 if (i < addr_parts.length ())
892 res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
894 return res;
897 /* Given invariant DEF and its address USE, check if the corresponding
898 invariant expr can be propagated into the use or not. */
900 static bool
901 inv_can_prop_to_addr_use (struct def *def, df_ref use)
903 struct invariant *inv;
904 rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
905 rtx_insn *use_insn = DF_REF_INSN (use);
906 rtx_insn *def_insn;
907 bool ok;
909 inv = invariants[def->invno];
910 /* No need to check if address expression is expensive. */
911 if (!inv->cheap_address)
912 return false;
914 def_insn = inv->insn;
915 def_set = single_set (def_insn);
916 if (!def_set)
917 return false;
919 validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
920 ok = verify_changes (0);
921 /* Try harder with canonicalization in address expression. */
922 if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
924 rtx src, dest, mem = NULL_RTX;
926 src = SET_SRC (use_set);
927 dest = SET_DEST (use_set);
928 if (MEM_P (src))
929 mem = src;
930 else if (MEM_P (dest))
931 mem = dest;
933 if (mem != NULL_RTX
934 && !memory_address_addr_space_p (GET_MODE (mem),
935 XEXP (mem, 0),
936 MEM_ADDR_SPACE (mem)))
938 rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
939 if (memory_address_addr_space_p (GET_MODE (mem),
940 addr, MEM_ADDR_SPACE (mem)))
941 ok = true;
944 cancel_changes (0);
945 return ok;
948 /* Record USE at DEF. */
950 static void
951 record_use (struct def *def, df_ref use)
953 struct use *u = XNEW (struct use);
955 u->pos = DF_REF_REAL_LOC (use);
956 u->insn = DF_REF_INSN (use);
957 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
958 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
959 u->next = def->uses;
960 def->uses = u;
961 def->n_uses++;
962 if (u->addr_use_p)
964 /* Initialize propagation information if this is the first addr
965 use of the inv def. */
966 if (def->n_addr_uses == 0)
967 def->can_prop_to_addr_uses = true;
969 def->n_addr_uses++;
970 if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
971 def->can_prop_to_addr_uses = false;
975 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
976 bitmap. Returns true if all dependencies of USE are known to be
977 loop invariants, false otherwise. */
979 static bool
980 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
982 df_ref def;
983 basic_block def_bb;
984 struct df_link *defs;
985 struct def *def_data;
986 struct invariant *inv;
988 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
989 return false;
991 defs = DF_REF_CHAIN (use);
992 if (!defs)
994 unsigned int regno = DF_REF_REGNO (use);
996 /* If this is the use of an uninitialized argument register that is
997 likely to be spilled, do not move it lest this might extend its
998 lifetime and cause reload to die. This can occur for a call to
999 a function taking complex number arguments and moving the insns
1000 preparing the arguments without moving the call itself wouldn't
1001 gain much in practice. */
1002 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
1003 && FUNCTION_ARG_REGNO_P (regno)
1004 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
1005 return false;
1007 return true;
1010 if (defs->next)
1011 return false;
1013 def = defs->ref;
1014 check_invariant_table_size ();
1015 inv = invariant_table[DF_REF_ID (def)];
1016 if (!inv)
1017 return false;
1019 def_data = inv->def;
1020 gcc_assert (def_data != NULL);
1022 def_bb = DF_REF_BB (def);
1023 /* Note that in case bb == def_bb, we know that the definition
1024 dominates insn, because def has invariant_table[DF_REF_ID(def)]
1025 defined and we process the insns in the basic block bb
1026 sequentially. */
1027 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1028 return false;
1030 bitmap_set_bit (depends_on, def_data->invno);
1031 return true;
1035 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1036 bitmap. Returns true if all dependencies of INSN are known to be
1037 loop invariants, false otherwise. */
1039 static bool
1040 check_dependencies (rtx_insn *insn, bitmap depends_on)
1042 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1043 df_ref use;
1044 basic_block bb = BLOCK_FOR_INSN (insn);
1046 FOR_EACH_INSN_INFO_USE (use, insn_info)
1047 if (!check_dependency (bb, use, depends_on))
1048 return false;
1049 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1050 if (!check_dependency (bb, use, depends_on))
1051 return false;
1053 return true;
1056 /* Pre-check candidate DEST to skip the one which can not make a valid insn
1057 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1058 static bool
1059 pre_check_invariant_p (bool simple, rtx dest)
1061 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1063 df_ref use;
1064 unsigned int i = REGNO (dest);
1065 struct df_insn_info *insn_info;
1066 df_ref def_rec;
1068 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1070 rtx_insn *ref = DF_REF_INSN (use);
1071 insn_info = DF_INSN_INFO_GET (ref);
1073 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1074 if (DF_REF_REGNO (def_rec) == i)
1076 /* Multi definitions at this stage, most likely are due to
1077 instruction constraints, which requires both read and write
1078 on the same register. Since move_invariant_reg is not
1079 powerful enough to handle such cases, just ignore the INV
1080 and leave the chance to others. */
1081 return false;
1085 return true;
1088 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
1089 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1090 unless the program ends due to a function call. */
1092 static void
1093 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1095 df_ref ref;
1096 struct def *def;
1097 bitmap depends_on;
1098 rtx set, dest;
1099 bool simple = true;
1100 struct invariant *inv;
1102 /* We can't move a CC0 setter without the user. */
1103 if (HAVE_cc0 && sets_cc0_p (insn))
1104 return;
1106 set = single_set (insn);
1107 if (!set)
1108 return;
1109 dest = SET_DEST (set);
1111 if (!REG_P (dest)
1112 || HARD_REGISTER_P (dest))
1113 simple = false;
1115 if (!may_assign_reg_p (dest)
1116 || !pre_check_invariant_p (simple, dest)
1117 || !check_maybe_invariant (SET_SRC (set)))
1118 return;
1120 /* If the insn can throw exception, we cannot move it at all without changing
1121 cfg. */
1122 if (can_throw_internal (insn))
1123 return;
1125 /* We cannot make trapping insn executed, unless it was executed before. */
1126 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1127 return;
1129 depends_on = BITMAP_ALLOC (NULL);
1130 if (!check_dependencies (insn, depends_on))
1132 BITMAP_FREE (depends_on);
1133 return;
1136 if (simple)
1137 def = XCNEW (struct def);
1138 else
1139 def = NULL;
1141 inv = create_new_invariant (def, insn, depends_on, always_executed);
1143 if (simple)
1145 ref = df_find_def (insn, dest);
1146 check_invariant_table_size ();
1147 invariant_table[DF_REF_ID (ref)] = inv;
1151 /* Record registers used in INSN that have a unique invariant definition. */
1153 static void
1154 record_uses (rtx_insn *insn)
1156 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1157 df_ref use;
1158 struct invariant *inv;
1160 FOR_EACH_INSN_INFO_USE (use, insn_info)
1162 inv = invariant_for_use (use);
1163 if (inv)
1164 record_use (inv->def, use);
1166 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1168 inv = invariant_for_use (use);
1169 if (inv)
1170 record_use (inv->def, use);
1174 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
1175 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1176 unless the program ends due to a function call. */
1178 static void
1179 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1181 find_invariant_insn (insn, always_reached, always_executed);
1182 record_uses (insn);
1185 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1186 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1187 block is always executed, unless the program ends due to a function
1188 call. */
1190 static void
1191 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1193 rtx_insn *insn;
1195 FOR_BB_INSNS (bb, insn)
1197 if (!NONDEBUG_INSN_P (insn))
1198 continue;
1200 find_invariants_insn (insn, always_reached, always_executed);
1202 if (always_reached
1203 && CALL_P (insn)
1204 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1205 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1206 always_reached = false;
1210 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1211 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1212 bitmap of basic blocks in BODY that are always executed unless the program
1213 ends due to a function call. */
1215 static void
1216 find_invariants_body (struct loop *loop, basic_block *body,
1217 bitmap always_reached, bitmap always_executed)
1219 unsigned i;
1221 for (i = 0; i < loop->num_nodes; i++)
1222 find_invariants_bb (body[i],
1223 bitmap_bit_p (always_reached, i),
1224 bitmap_bit_p (always_executed, i));
1227 /* Finds invariants in LOOP. */
1229 static void
1230 find_invariants (struct loop *loop)
1232 auto_bitmap may_exit;
1233 auto_bitmap always_reached;
1234 auto_bitmap has_exit;
1235 auto_bitmap always_executed;
1236 basic_block *body = get_loop_body_in_dom_order (loop);
1238 find_exits (loop, body, may_exit, has_exit);
1239 compute_always_reached (loop, body, may_exit, always_reached);
1240 compute_always_reached (loop, body, has_exit, always_executed);
1242 find_defs (loop);
1243 find_invariants_body (loop, body, always_reached, always_executed);
1244 merge_identical_invariants ();
1246 free (body);
1249 /* Frees a list of uses USE. */
1251 static void
1252 free_use_list (struct use *use)
1254 struct use *next;
1256 for (; use; use = next)
1258 next = use->next;
1259 free (use);
1263 /* Return pressure class and number of hard registers (through *NREGS)
1264 for destination of INSN. */
1265 static enum reg_class
1266 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1268 rtx reg;
1269 enum reg_class pressure_class;
1270 rtx set = single_set (insn);
1272 /* Considered invariant insns have only one set. */
1273 gcc_assert (set != NULL_RTX);
1274 reg = SET_DEST (set);
1275 if (GET_CODE (reg) == SUBREG)
1276 reg = SUBREG_REG (reg);
1277 if (MEM_P (reg))
1279 *nregs = 0;
1280 pressure_class = NO_REGS;
1282 else
1284 if (! REG_P (reg))
1285 reg = NULL_RTX;
1286 if (reg == NULL_RTX)
1287 pressure_class = GENERAL_REGS;
1288 else
1290 pressure_class = reg_allocno_class (REGNO (reg));
1291 pressure_class = ira_pressure_class_translate[pressure_class];
1293 *nregs
1294 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1296 return pressure_class;
1299 /* Calculates cost and number of registers needed for moving invariant INV
1300 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1301 the REG_CLASS of INV. Return
1302 -1: if INV is invalid.
1303 0: if INV and its depends_on have same reg_class
1304 1: if INV and its depends_on have different reg_classes. */
1306 static int
1307 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1308 enum reg_class *cl)
1310 int i, acomp_cost;
1311 unsigned aregs_needed[N_REG_CLASSES];
1312 unsigned depno;
1313 struct invariant *dep;
1314 bitmap_iterator bi;
1315 int ret = 1;
1317 /* Find the representative of the class of the equivalent invariants. */
1318 inv = invariants[inv->eqto];
1320 *comp_cost = 0;
1321 if (! flag_ira_loop_pressure)
1322 regs_needed[0] = 0;
1323 else
1325 for (i = 0; i < ira_pressure_classes_num; i++)
1326 regs_needed[ira_pressure_classes[i]] = 0;
1329 if (inv->move
1330 || inv->stamp == actual_stamp)
1331 return -1;
1332 inv->stamp = actual_stamp;
1334 if (! flag_ira_loop_pressure)
1335 regs_needed[0]++;
1336 else
1338 int nregs;
1339 enum reg_class pressure_class;
1341 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1342 regs_needed[pressure_class] += nregs;
1343 *cl = pressure_class;
1344 ret = 0;
1347 if (!inv->cheap_address
1348 || inv->def->n_uses == 0
1349 || inv->def->n_addr_uses < inv->def->n_uses
1350 /* Count cost if the inv can't be propagated into address uses. */
1351 || !inv->def->can_prop_to_addr_uses)
1352 (*comp_cost) += inv->cost * inv->eqno;
1354 #ifdef STACK_REGS
1356 /* Hoisting constant pool constants into stack regs may cost more than
1357 just single register. On x87, the balance is affected both by the
1358 small number of FP registers, and by its register stack organization,
1359 that forces us to add compensation code in and around the loop to
1360 shuffle the operands to the top of stack before use, and pop them
1361 from the stack after the loop finishes.
1363 To model this effect, we increase the number of registers needed for
1364 stack registers by two: one register push, and one register pop.
1365 This usually has the effect that FP constant loads from the constant
1366 pool are not moved out of the loop.
1368 Note that this also means that dependent invariants can not be moved.
1369 However, the primary purpose of this pass is to move loop invariant
1370 address arithmetic out of loops, and address arithmetic that depends
1371 on floating point constants is unlikely to ever occur. */
1372 rtx set = single_set (inv->insn);
1373 if (set
1374 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1375 && constant_pool_constant_p (SET_SRC (set)))
1377 if (flag_ira_loop_pressure)
1378 regs_needed[ira_stack_reg_pressure_class] += 2;
1379 else
1380 regs_needed[0] += 2;
1383 #endif
1385 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1387 bool check_p;
1388 enum reg_class dep_cl = ALL_REGS;
1389 int dep_ret;
1391 dep = invariants[depno];
1393 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1394 if (dep->move)
1395 continue;
1397 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1399 if (! flag_ira_loop_pressure)
1400 check_p = aregs_needed[0] != 0;
1401 else
1403 for (i = 0; i < ira_pressure_classes_num; i++)
1404 if (aregs_needed[ira_pressure_classes[i]] != 0)
1405 break;
1406 check_p = i < ira_pressure_classes_num;
1408 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1410 *cl = ALL_REGS;
1411 ret = 1;
1414 if (check_p
1415 /* We need to check always_executed, since if the original value of
1416 the invariant may be preserved, we may need to keep it in a
1417 separate register. TODO check whether the register has an
1418 use outside of the loop. */
1419 && dep->always_executed
1420 && !dep->def->uses->next)
1422 /* If this is a single use, after moving the dependency we will not
1423 need a new register. */
1424 if (! flag_ira_loop_pressure)
1425 aregs_needed[0]--;
1426 else
1428 int nregs;
1429 enum reg_class pressure_class;
1431 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1432 aregs_needed[pressure_class] -= nregs;
1436 if (! flag_ira_loop_pressure)
1437 regs_needed[0] += aregs_needed[0];
1438 else
1440 for (i = 0; i < ira_pressure_classes_num; i++)
1441 regs_needed[ira_pressure_classes[i]]
1442 += aregs_needed[ira_pressure_classes[i]];
1444 (*comp_cost) += acomp_cost;
1446 return ret;
1449 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1450 of registers used in the loop, NEW_REGS is the number of new variables
1451 already added due to the invariant motion. The number of registers needed
1452 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1453 through to estimate_reg_pressure_cost. */
1455 static int
1456 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1457 unsigned *new_regs, unsigned regs_used,
1458 bool speed, bool call_p)
1460 int comp_cost, size_cost;
1461 /* Workaround -Wmaybe-uninitialized false positive during
1462 profiledbootstrap by initializing it. */
1463 enum reg_class cl = NO_REGS;
1464 int ret;
1466 actual_stamp++;
1468 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1470 if (! flag_ira_loop_pressure)
1472 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1473 regs_used, speed, call_p)
1474 - estimate_reg_pressure_cost (new_regs[0],
1475 regs_used, speed, call_p));
1477 else if (ret < 0)
1478 return -1;
1479 else if ((ret == 0) && (cl == NO_REGS))
1480 /* Hoist it anyway since it does not impact register pressure. */
1481 return 1;
1482 else
1484 int i;
1485 enum reg_class pressure_class;
1487 for (i = 0; i < ira_pressure_classes_num; i++)
1489 pressure_class = ira_pressure_classes[i];
1491 if (!reg_classes_intersect_p (pressure_class, cl))
1492 continue;
1494 if ((int) new_regs[pressure_class]
1495 + (int) regs_needed[pressure_class]
1496 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1497 + IRA_LOOP_RESERVED_REGS
1498 > ira_class_hard_regs_num[pressure_class])
1499 break;
1501 if (i < ira_pressure_classes_num)
1502 /* There will be register pressure excess and we want not to
1503 make this loop invariant motion. All loop invariants with
1504 non-positive gains will be rejected in function
1505 find_invariants_to_move. Therefore we return the negative
1506 number here.
1508 One could think that this rejects also expensive loop
1509 invariant motions and this will hurt code performance.
1510 However numerous experiments with different heuristics
1511 taking invariant cost into account did not confirm this
1512 assumption. There are possible explanations for this
1513 result:
1514 o probably all expensive invariants were already moved out
1515 of the loop by PRE and gimple invariant motion pass.
1516 o expensive invariant execution will be hidden by insn
1517 scheduling or OOO processor hardware because usually such
1518 invariants have a lot of freedom to be executed
1519 out-of-order.
1520 Another reason for ignoring invariant cost vs spilling cost
1521 heuristics is also in difficulties to evaluate accurately
1522 spill cost at this stage. */
1523 return -1;
1524 else
1525 size_cost = 0;
1528 return comp_cost - size_cost;
1531 /* Finds invariant with best gain for moving. Returns the gain, stores
1532 the invariant in *BEST and number of registers needed for it to
1533 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1534 NEW_REGS is the number of new variables already added due to invariant
1535 motion. */
1537 static int
1538 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1539 unsigned *new_regs, unsigned regs_used,
1540 bool speed, bool call_p)
1542 struct invariant *inv;
1543 int i, gain = 0, again;
1544 unsigned aregs_needed[N_REG_CLASSES], invno;
1546 FOR_EACH_VEC_ELT (invariants, invno, inv)
1548 if (inv->move)
1549 continue;
1551 /* Only consider the "representatives" of equivalent invariants. */
1552 if (inv->eqto != inv->invno)
1553 continue;
1555 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1556 speed, call_p);
1557 if (again > gain)
1559 gain = again;
1560 *best = inv;
1561 if (! flag_ira_loop_pressure)
1562 regs_needed[0] = aregs_needed[0];
1563 else
1565 for (i = 0; i < ira_pressure_classes_num; i++)
1566 regs_needed[ira_pressure_classes[i]]
1567 = aregs_needed[ira_pressure_classes[i]];
1572 return gain;
1575 /* Marks invariant INVNO and all its dependencies for moving. */
1577 static void
1578 set_move_mark (unsigned invno, int gain)
1580 struct invariant *inv = invariants[invno];
1581 bitmap_iterator bi;
1583 /* Find the representative of the class of the equivalent invariants. */
1584 inv = invariants[inv->eqto];
1586 if (inv->move)
1587 return;
1588 inv->move = true;
1590 if (dump_file)
1592 if (gain >= 0)
1593 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1594 invno, gain);
1595 else
1596 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1597 invno);
1600 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1602 set_move_mark (invno, -1);
1606 /* Determines which invariants to move. */
1608 static void
1609 find_invariants_to_move (bool speed, bool call_p)
1611 int gain;
1612 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1613 struct invariant *inv = NULL;
1615 if (!invariants.length ())
1616 return;
1618 if (flag_ira_loop_pressure)
1619 /* REGS_USED is actually never used when the flag is on. */
1620 regs_used = 0;
1621 else
1622 /* We do not really do a good job in estimating number of
1623 registers used; we put some initial bound here to stand for
1624 induction variables etc. that we do not detect. */
1626 unsigned int n_regs = DF_REG_SIZE (df);
1628 regs_used = 2;
1630 for (i = 0; i < n_regs; i++)
1632 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1634 /* This is a value that is used but not changed inside loop. */
1635 regs_used++;
1640 if (! flag_ira_loop_pressure)
1641 new_regs[0] = regs_needed[0] = 0;
1642 else
1644 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1645 new_regs[ira_pressure_classes[i]] = 0;
1647 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1648 new_regs, regs_used,
1649 speed, call_p)) > 0)
1651 set_move_mark (inv->invno, gain);
1652 if (! flag_ira_loop_pressure)
1653 new_regs[0] += regs_needed[0];
1654 else
1656 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1657 new_regs[ira_pressure_classes[i]]
1658 += regs_needed[ira_pressure_classes[i]];
1663 /* Replace the uses, reached by the definition of invariant INV, by REG.
1665 IN_GROUP is nonzero if this is part of a group of changes that must be
1666 performed as a group. In that case, the changes will be stored. The
1667 function `apply_change_group' will validate and apply the changes. */
1669 static int
1670 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1672 /* Replace the uses we know to be dominated. It saves work for copy
1673 propagation, and also it is necessary so that dependent invariants
1674 are computed right. */
1675 if (inv->def)
1677 struct use *use;
1678 for (use = inv->def->uses; use; use = use->next)
1679 validate_change (use->insn, use->pos, reg, true);
1681 /* If we aren't part of a larger group, apply the changes now. */
1682 if (!in_group)
1683 return apply_change_group ();
1686 return 1;
1689 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1690 the block preceding its header. */
1692 static bool
1693 can_move_invariant_reg (struct loop *loop, struct invariant *inv, rtx reg)
1695 df_ref def, use;
1696 unsigned int dest_regno, defs_in_loop_count = 0;
1697 rtx_insn *insn = inv->insn;
1698 basic_block bb = BLOCK_FOR_INSN (inv->insn);
1700 /* We ignore hard register and memory access for cost and complexity reasons.
1701 Hard register are few at this stage and expensive to consider as they
1702 require building a separate data flow. Memory access would require using
1703 df_simulate_* and can_move_insns_across functions and is more complex. */
1704 if (!REG_P (reg) || HARD_REGISTER_P (reg))
1705 return false;
1707 /* Check whether the set is always executed. We could omit this condition if
1708 we know that the register is unused outside of the loop, but it does not
1709 seem worth finding out. */
1710 if (!inv->always_executed)
1711 return false;
1713 /* Check that all uses that would be dominated by def are already dominated
1714 by it. */
1715 dest_regno = REGNO (reg);
1716 for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1718 rtx_insn *use_insn;
1719 basic_block use_bb;
1721 use_insn = DF_REF_INSN (use);
1722 use_bb = BLOCK_FOR_INSN (use_insn);
1724 /* Ignore instruction considered for moving. */
1725 if (use_insn == insn)
1726 continue;
1728 /* Don't consider uses outside loop. */
1729 if (!flow_bb_inside_loop_p (loop, use_bb))
1730 continue;
1732 /* Don't move if a use is not dominated by def in insn. */
1733 if (use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1734 return false;
1735 if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1736 return false;
1739 /* Check for other defs. Any other def in the loop might reach a use
1740 currently reached by the def in insn. */
1741 for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1743 basic_block def_bb = DF_REF_BB (def);
1745 /* Defs in exit block cannot reach a use they weren't already. */
1746 if (single_succ_p (def_bb))
1748 basic_block def_bb_succ;
1750 def_bb_succ = single_succ (def_bb);
1751 if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1752 continue;
1755 if (++defs_in_loop_count > 1)
1756 return false;
1759 return true;
1762 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1763 otherwise. */
1765 static bool
1766 move_invariant_reg (struct loop *loop, unsigned invno)
1768 struct invariant *inv = invariants[invno];
1769 struct invariant *repr = invariants[inv->eqto];
1770 unsigned i;
1771 basic_block preheader = loop_preheader_edge (loop)->src;
1772 rtx reg, set, dest, note;
1773 bitmap_iterator bi;
1774 int regno = -1;
1776 if (inv->reg)
1777 return true;
1778 if (!repr->move)
1779 return false;
1781 /* If this is a representative of the class of equivalent invariants,
1782 really move the invariant. Otherwise just replace its use with
1783 the register used for the representative. */
1784 if (inv == repr)
1786 if (inv->depends_on)
1788 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1790 if (!move_invariant_reg (loop, i))
1791 goto fail;
1795 /* If possible, just move the set out of the loop. Otherwise, we
1796 need to create a temporary register. */
1797 set = single_set (inv->insn);
1798 reg = dest = SET_DEST (set);
1799 if (GET_CODE (reg) == SUBREG)
1800 reg = SUBREG_REG (reg);
1801 if (REG_P (reg))
1802 regno = REGNO (reg);
1804 if (!can_move_invariant_reg (loop, inv, dest))
1806 reg = gen_reg_rtx_and_attrs (dest);
1808 /* Try replacing the destination by a new pseudoregister. */
1809 validate_change (inv->insn, &SET_DEST (set), reg, true);
1811 /* As well as all the dominated uses. */
1812 replace_uses (inv, reg, true);
1814 /* And validate all the changes. */
1815 if (!apply_change_group ())
1816 goto fail;
1818 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1820 else if (dump_file)
1821 fprintf (dump_file, "Invariant %d moved without introducing a new "
1822 "temporary register\n", invno);
1823 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1824 df_recompute_luids (preheader);
1826 /* If there is a REG_EQUAL note on the insn we just moved, and the
1827 insn is in a basic block that is not always executed or the note
1828 contains something for which we don't know the invariant status,
1829 the note may no longer be valid after we move the insn. Note that
1830 uses in REG_EQUAL notes are taken into account in the computation
1831 of invariants, so it is safe to retain the note even if it contains
1832 register references for which we know the invariant status. */
1833 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1834 && (!inv->always_executed
1835 || !check_maybe_invariant (XEXP (note, 0))))
1836 remove_note (inv->insn, note);
1838 else
1840 if (!move_invariant_reg (loop, repr->invno))
1841 goto fail;
1842 reg = repr->reg;
1843 regno = repr->orig_regno;
1844 if (!replace_uses (inv, reg, false))
1845 goto fail;
1846 set = single_set (inv->insn);
1847 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1848 delete_insn (inv->insn);
1851 inv->reg = reg;
1852 inv->orig_regno = regno;
1854 return true;
1856 fail:
1857 /* If we failed, clear move flag, so that we do not try to move inv
1858 again. */
1859 if (dump_file)
1860 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1861 inv->move = false;
1862 inv->reg = NULL_RTX;
1863 inv->orig_regno = -1;
1865 return false;
1868 /* Move selected invariant out of the LOOP. Newly created regs are marked
1869 in TEMPORARY_REGS. */
1871 static void
1872 move_invariants (struct loop *loop)
1874 struct invariant *inv;
1875 unsigned i;
1877 FOR_EACH_VEC_ELT (invariants, i, inv)
1878 move_invariant_reg (loop, i);
1879 if (flag_ira_loop_pressure && resize_reg_info ())
1881 FOR_EACH_VEC_ELT (invariants, i, inv)
1882 if (inv->reg != NULL_RTX)
1884 if (inv->orig_regno >= 0)
1885 setup_reg_classes (REGNO (inv->reg),
1886 reg_preferred_class (inv->orig_regno),
1887 reg_alternate_class (inv->orig_regno),
1888 reg_allocno_class (inv->orig_regno));
1889 else
1890 setup_reg_classes (REGNO (inv->reg),
1891 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1896 /* Initializes invariant motion data. */
1898 static void
1899 init_inv_motion_data (void)
1901 actual_stamp = 1;
1903 invariants.create (100);
1906 /* Frees the data allocated by invariant motion. */
1908 static void
1909 free_inv_motion_data (void)
1911 unsigned i;
1912 struct def *def;
1913 struct invariant *inv;
1915 check_invariant_table_size ();
1916 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1918 inv = invariant_table[i];
1919 if (inv)
1921 def = inv->def;
1922 gcc_assert (def != NULL);
1924 free_use_list (def->uses);
1925 free (def);
1926 invariant_table[i] = NULL;
1930 FOR_EACH_VEC_ELT (invariants, i, inv)
1932 BITMAP_FREE (inv->depends_on);
1933 free (inv);
1935 invariants.release ();
1938 /* Move the invariants out of the LOOP. */
1940 static void
1941 move_single_loop_invariants (struct loop *loop)
1943 init_inv_motion_data ();
1945 find_invariants (loop);
1946 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1947 LOOP_DATA (loop)->has_call);
1948 move_invariants (loop);
1950 free_inv_motion_data ();
1953 /* Releases the auxiliary data for LOOP. */
1955 static void
1956 free_loop_data (struct loop *loop)
1958 struct loop_data *data = LOOP_DATA (loop);
1959 if (!data)
1960 return;
1962 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1963 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1964 free (data);
1965 loop->aux = NULL;
1970 /* Registers currently living. */
1971 static bitmap_head curr_regs_live;
1973 /* Current reg pressure for each pressure class. */
1974 static int curr_reg_pressure[N_REG_CLASSES];
1976 /* Record all regs that are set in any one insn. Communication from
1977 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1978 all hard-registers. */
1979 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1980 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1981 /* Number of regs stored in the previous array. */
1982 static int n_regs_set;
1984 /* Return pressure class and number of needed hard registers (through
1985 *NREGS) of register REGNO. */
1986 static enum reg_class
1987 get_regno_pressure_class (int regno, int *nregs)
1989 if (regno >= FIRST_PSEUDO_REGISTER)
1991 enum reg_class pressure_class;
1993 pressure_class = reg_allocno_class (regno);
1994 pressure_class = ira_pressure_class_translate[pressure_class];
1995 *nregs
1996 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1997 return pressure_class;
1999 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
2000 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
2002 *nregs = 1;
2003 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
2005 else
2007 *nregs = 0;
2008 return NO_REGS;
2012 /* Increase (if INCR_P) or decrease current register pressure for
2013 register REGNO. */
2014 static void
2015 change_pressure (int regno, bool incr_p)
2017 int nregs;
2018 enum reg_class pressure_class;
2020 pressure_class = get_regno_pressure_class (regno, &nregs);
2021 if (! incr_p)
2022 curr_reg_pressure[pressure_class] -= nregs;
2023 else
2025 curr_reg_pressure[pressure_class] += nregs;
2026 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2027 < curr_reg_pressure[pressure_class])
2028 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2029 = curr_reg_pressure[pressure_class];
2033 /* Mark REGNO birth. */
2034 static void
2035 mark_regno_live (int regno)
2037 struct loop *loop;
2039 for (loop = curr_loop;
2040 loop != current_loops->tree_root;
2041 loop = loop_outer (loop))
2042 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2043 if (!bitmap_set_bit (&curr_regs_live, regno))
2044 return;
2045 change_pressure (regno, true);
2048 /* Mark REGNO death. */
2049 static void
2050 mark_regno_death (int regno)
2052 if (! bitmap_clear_bit (&curr_regs_live, regno))
2053 return;
2054 change_pressure (regno, false);
2057 /* Mark setting register REG. */
2058 static void
2059 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2060 void *data ATTRIBUTE_UNUSED)
2062 if (GET_CODE (reg) == SUBREG)
2063 reg = SUBREG_REG (reg);
2065 if (! REG_P (reg))
2066 return;
2068 regs_set[n_regs_set++] = reg;
2070 unsigned int end_regno = END_REGNO (reg);
2071 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2072 mark_regno_live (regno);
2075 /* Mark clobbering register REG. */
2076 static void
2077 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2079 if (GET_CODE (setter) == CLOBBER)
2080 mark_reg_store (reg, setter, data);
2083 /* Mark register REG death. */
2084 static void
2085 mark_reg_death (rtx reg)
2087 unsigned int end_regno = END_REGNO (reg);
2088 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2089 mark_regno_death (regno);
2092 /* Mark occurrence of registers in X for the current loop. */
2093 static void
2094 mark_ref_regs (rtx x)
2096 RTX_CODE code;
2097 int i;
2098 const char *fmt;
2100 if (!x)
2101 return;
2103 code = GET_CODE (x);
2104 if (code == REG)
2106 struct loop *loop;
2108 for (loop = curr_loop;
2109 loop != current_loops->tree_root;
2110 loop = loop_outer (loop))
2111 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2112 return;
2115 fmt = GET_RTX_FORMAT (code);
2116 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2117 if (fmt[i] == 'e')
2118 mark_ref_regs (XEXP (x, i));
2119 else if (fmt[i] == 'E')
2121 int j;
2123 for (j = 0; j < XVECLEN (x, i); j++)
2124 mark_ref_regs (XVECEXP (x, i, j));
2128 /* Calculate register pressure in the loops. */
2129 static void
2130 calculate_loop_reg_pressure (void)
2132 int i;
2133 unsigned int j;
2134 bitmap_iterator bi;
2135 basic_block bb;
2136 rtx_insn *insn;
2137 rtx link;
2138 struct loop *loop, *parent;
2140 FOR_EACH_LOOP (loop, 0)
2141 if (loop->aux == NULL)
2143 loop->aux = xcalloc (1, sizeof (struct loop_data));
2144 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
2145 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
2147 ira_setup_eliminable_regset ();
2148 bitmap_initialize (&curr_regs_live, &reg_obstack);
2149 FOR_EACH_BB_FN (bb, cfun)
2151 curr_loop = bb->loop_father;
2152 if (curr_loop == current_loops->tree_root)
2153 continue;
2155 for (loop = curr_loop;
2156 loop != current_loops->tree_root;
2157 loop = loop_outer (loop))
2158 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2160 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2161 for (i = 0; i < ira_pressure_classes_num; i++)
2162 curr_reg_pressure[ira_pressure_classes[i]] = 0;
2163 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2164 change_pressure (j, true);
2166 FOR_BB_INSNS (bb, insn)
2168 if (! NONDEBUG_INSN_P (insn))
2169 continue;
2171 mark_ref_regs (PATTERN (insn));
2172 n_regs_set = 0;
2173 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
2175 /* Mark any registers dead after INSN as dead now. */
2177 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2178 if (REG_NOTE_KIND (link) == REG_DEAD)
2179 mark_reg_death (XEXP (link, 0));
2181 /* Mark any registers set in INSN as live,
2182 and mark them as conflicting with all other live regs.
2183 Clobbers are processed again, so they conflict with
2184 the registers that are set. */
2186 note_stores (PATTERN (insn), mark_reg_store, NULL);
2188 if (AUTO_INC_DEC)
2189 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2190 if (REG_NOTE_KIND (link) == REG_INC)
2191 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2193 while (n_regs_set-- > 0)
2195 rtx note = find_regno_note (insn, REG_UNUSED,
2196 REGNO (regs_set[n_regs_set]));
2197 if (! note)
2198 continue;
2200 mark_reg_death (XEXP (note, 0));
2204 bitmap_clear (&curr_regs_live);
2205 if (flag_ira_region == IRA_REGION_MIXED
2206 || flag_ira_region == IRA_REGION_ALL)
2207 FOR_EACH_LOOP (loop, 0)
2209 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2210 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2212 enum reg_class pressure_class;
2213 int nregs;
2215 pressure_class = get_regno_pressure_class (j, &nregs);
2216 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2219 if (dump_file == NULL)
2220 return;
2221 FOR_EACH_LOOP (loop, 0)
2223 parent = loop_outer (loop);
2224 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2225 loop->num, (parent == NULL ? -1 : parent->num),
2226 loop->header->index, loop_depth (loop));
2227 fprintf (dump_file, "\n ref. regnos:");
2228 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2229 fprintf (dump_file, " %d", j);
2230 fprintf (dump_file, "\n live regnos:");
2231 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2232 fprintf (dump_file, " %d", j);
2233 fprintf (dump_file, "\n Pressure:");
2234 for (i = 0; (int) i < ira_pressure_classes_num; i++)
2236 enum reg_class pressure_class;
2238 pressure_class = ira_pressure_classes[i];
2239 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2240 continue;
2241 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2242 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2244 fprintf (dump_file, "\n");
2250 /* Move the invariants out of the loops. */
2252 void
2253 move_loop_invariants (void)
2255 struct loop *loop;
2257 if (flag_ira_loop_pressure)
2259 df_analyze ();
2260 regstat_init_n_sets_and_refs ();
2261 ira_set_pseudo_classes (true, dump_file);
2262 calculate_loop_reg_pressure ();
2263 regstat_free_n_sets_and_refs ();
2265 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2266 /* Process the loops, innermost first. */
2267 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2269 curr_loop = loop;
2270 /* move_single_loop_invariants for very large loops
2271 is time consuming and might need a lot of memory. */
2272 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2273 move_single_loop_invariants (loop);
2276 FOR_EACH_LOOP (loop, 0)
2278 free_loop_data (loop);
2281 if (flag_ira_loop_pressure)
2282 /* There is no sense to keep this info because it was most
2283 probably outdated by subsequent passes. */
2284 free_reg_info ();
2285 free (invariant_table);
2286 invariant_table = NULL;
2287 invariant_table_size = 0;
2289 checking_verify_flow_info ();