* doc/install.texi (Specific): Tweak link to mkssoftware.com.
[official-gcc.git] / gcc / loop-invariant.c
blob1cdb5cbf5854ea738d2f50e4c1d128fc39df2b55
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004-2017 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);
340 return val;
343 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
344 and INSN2 have always the same value. */
346 static bool
347 invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
349 enum rtx_code code = GET_CODE (e1);
350 int i, j;
351 const char *fmt;
352 df_ref use1, use2;
353 struct invariant *inv1 = NULL, *inv2 = NULL;
354 rtx sub1, sub2;
356 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
357 the other one. If both are VOIDmode, we rely on the caller of this
358 function to verify that their modes are the same. */
359 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
360 return false;
362 switch (code)
364 CASE_CONST_ANY:
365 case SYMBOL_REF:
366 case CONST:
367 case LABEL_REF:
368 return rtx_equal_p (e1, e2);
370 case REG:
371 use1 = df_find_use (insn1, e1);
372 use2 = df_find_use (insn2, e2);
373 if (use1)
374 inv1 = invariant_for_use (use1);
375 if (use2)
376 inv2 = invariant_for_use (use2);
378 if (!inv1 && !inv2)
379 return rtx_equal_p (e1, e2);
381 if (!inv1 || !inv2)
382 return false;
384 gcc_assert (inv1->eqto != ~0u);
385 gcc_assert (inv2->eqto != ~0u);
386 return inv1->eqto == inv2->eqto;
388 default:
389 break;
392 fmt = GET_RTX_FORMAT (code);
393 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
395 if (fmt[i] == 'e')
397 sub1 = XEXP (e1, i);
398 sub2 = XEXP (e2, i);
400 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
401 return false;
404 else if (fmt[i] == 'E')
406 if (XVECLEN (e1, i) != XVECLEN (e2, i))
407 return false;
409 for (j = 0; j < XVECLEN (e1, i); j++)
411 sub1 = XVECEXP (e1, i, j);
412 sub2 = XVECEXP (e2, i, j);
414 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
415 return false;
418 else if (fmt[i] == 'i' || fmt[i] == 'n')
420 if (XINT (e1, i) != XINT (e2, i))
421 return false;
423 /* Unhandled type of subexpression, we fail conservatively. */
424 else
425 return false;
428 return true;
431 struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
433 static inline hashval_t hash (const invariant_expr_entry *);
434 static inline bool equal (const invariant_expr_entry *,
435 const invariant_expr_entry *);
438 /* Returns hash value for invariant expression entry ENTRY. */
440 inline hashval_t
441 invariant_expr_hasher::hash (const invariant_expr_entry *entry)
443 return entry->hash;
446 /* Compares invariant expression entries ENTRY1 and ENTRY2. */
448 inline bool
449 invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
450 const invariant_expr_entry *entry2)
452 if (entry1->mode != entry2->mode)
453 return 0;
455 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
456 entry2->inv->insn, entry2->expr);
459 typedef hash_table<invariant_expr_hasher> invariant_htab_type;
461 /* Checks whether invariant with value EXPR in machine mode MODE is
462 recorded in EQ. If this is the case, return the invariant. Otherwise
463 insert INV to the table for this expression and return INV. */
465 static struct invariant *
466 find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
467 struct invariant *inv)
469 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
470 struct invariant_expr_entry *entry;
471 struct invariant_expr_entry pentry;
472 invariant_expr_entry **slot;
474 pentry.expr = expr;
475 pentry.inv = inv;
476 pentry.mode = mode;
477 slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
478 entry = *slot;
480 if (entry)
481 return entry->inv;
483 entry = XNEW (struct invariant_expr_entry);
484 entry->inv = inv;
485 entry->expr = expr;
486 entry->mode = mode;
487 entry->hash = hash;
488 *slot = entry;
490 return inv;
493 /* Finds invariants identical to INV and records the equivalence. EQ is the
494 hash table of the invariants. */
496 static void
497 find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
499 unsigned depno;
500 bitmap_iterator bi;
501 struct invariant *dep;
502 rtx expr, set;
503 machine_mode mode;
504 struct invariant *tmp;
506 if (inv->eqto != ~0u)
507 return;
509 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
511 dep = invariants[depno];
512 find_identical_invariants (eq, dep);
515 set = single_set (inv->insn);
516 expr = SET_SRC (set);
517 mode = GET_MODE (expr);
518 if (mode == VOIDmode)
519 mode = GET_MODE (SET_DEST (set));
521 tmp = find_or_insert_inv (eq, expr, mode, inv);
522 inv->eqto = tmp->invno;
524 if (tmp->invno != inv->invno && inv->always_executed)
525 tmp->eqno++;
527 if (dump_file && inv->eqto != inv->invno)
528 fprintf (dump_file,
529 "Invariant %d is equivalent to invariant %d.\n",
530 inv->invno, inv->eqto);
533 /* Find invariants with the same value and record the equivalences. */
535 static void
536 merge_identical_invariants (void)
538 unsigned i;
539 struct invariant *inv;
540 invariant_htab_type eq (invariants.length ());
542 FOR_EACH_VEC_ELT (invariants, i, inv)
543 find_identical_invariants (&eq, inv);
546 /* Determines the basic blocks inside LOOP that are always executed and
547 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
548 basic blocks that may either exit the loop, or contain the call that
549 does not have to return. BODY is body of the loop obtained by
550 get_loop_body_in_dom_order. */
552 static void
553 compute_always_reached (struct loop *loop, basic_block *body,
554 bitmap may_exit, bitmap always_reached)
556 unsigned i;
558 for (i = 0; i < loop->num_nodes; i++)
560 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
561 bitmap_set_bit (always_reached, i);
563 if (bitmap_bit_p (may_exit, i))
564 return;
568 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
569 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
570 additionally mark blocks that may exit due to a call. */
572 static void
573 find_exits (struct loop *loop, basic_block *body,
574 bitmap may_exit, bitmap has_exit)
576 unsigned i;
577 edge_iterator ei;
578 edge e;
579 struct loop *outermost_exit = loop, *aexit;
580 bool has_call = false;
581 rtx_insn *insn;
583 for (i = 0; i < loop->num_nodes; i++)
585 if (body[i]->loop_father == loop)
587 FOR_BB_INSNS (body[i], insn)
589 if (CALL_P (insn)
590 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
591 || !RTL_CONST_OR_PURE_CALL_P (insn)))
593 has_call = true;
594 bitmap_set_bit (may_exit, i);
595 break;
599 FOR_EACH_EDGE (e, ei, body[i]->succs)
601 if (! flow_bb_inside_loop_p (loop, e->dest))
603 bitmap_set_bit (may_exit, i);
604 bitmap_set_bit (has_exit, i);
605 outermost_exit = find_common_loop (outermost_exit,
606 e->dest->loop_father);
608 /* If we enter a subloop that might never terminate treat
609 it like a possible exit. */
610 if (flow_loop_nested_p (loop, e->dest->loop_father))
611 bitmap_set_bit (may_exit, i);
613 continue;
616 /* Use the data stored for the subloop to decide whether we may exit
617 through it. It is sufficient to do this for header of the loop,
618 as other basic blocks inside it must be dominated by it. */
619 if (body[i]->loop_father->header != body[i])
620 continue;
622 if (LOOP_DATA (body[i]->loop_father)->has_call)
624 has_call = true;
625 bitmap_set_bit (may_exit, i);
627 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
628 if (aexit != loop)
630 bitmap_set_bit (may_exit, i);
631 bitmap_set_bit (has_exit, i);
633 if (flow_loop_nested_p (aexit, outermost_exit))
634 outermost_exit = aexit;
638 if (loop->aux == NULL)
640 loop->aux = xcalloc (1, sizeof (struct loop_data));
641 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
642 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
644 LOOP_DATA (loop)->outermost_exit = outermost_exit;
645 LOOP_DATA (loop)->has_call = has_call;
648 /* Check whether we may assign a value to X from a register. */
650 static bool
651 may_assign_reg_p (rtx x)
653 return (GET_MODE (x) != VOIDmode
654 && GET_MODE (x) != BLKmode
655 && can_copy_p (GET_MODE (x))
656 && (!REG_P (x)
657 || !HARD_REGISTER_P (x)
658 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
661 /* Finds definitions that may correspond to invariants in LOOP with body
662 BODY. */
664 static void
665 find_defs (struct loop *loop)
667 if (dump_file)
669 fprintf (dump_file,
670 "*****starting processing of loop %d ******\n",
671 loop->num);
674 df_remove_problem (df_chain);
675 df_process_deferred_rescans ();
676 df_chain_add_problem (DF_UD_CHAIN);
677 df_live_add_problem ();
678 df_live_set_all_dirty ();
679 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
680 df_analyze_loop (loop);
681 check_invariant_table_size ();
683 if (dump_file)
685 df_dump_region (dump_file);
686 fprintf (dump_file,
687 "*****ending processing of loop %d ******\n",
688 loop->num);
692 /* Creates a new invariant for definition DEF in INSN, depending on invariants
693 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
694 unless the program ends due to a function call. The newly created invariant
695 is returned. */
697 static struct invariant *
698 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
699 bool always_executed)
701 struct invariant *inv = XNEW (struct invariant);
702 rtx set = single_set (insn);
703 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
705 inv->def = def;
706 inv->always_executed = always_executed;
707 inv->depends_on = depends_on;
709 /* If the set is simple, usually by moving it we move the whole store out of
710 the loop. Otherwise we save only cost of the computation. */
711 if (def)
713 inv->cost = set_rtx_cost (set, speed);
714 /* ??? Try to determine cheapness of address computation. Unfortunately
715 the address cost is only a relative measure, we can't really compare
716 it with any absolute number, but only with other address costs.
717 But here we don't have any other addresses, so compare with a magic
718 number anyway. It has to be large enough to not regress PR33928
719 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
720 enough to not regress 410.bwaves either (by still moving reg+reg
721 invariants).
722 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
723 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
724 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
725 ADDR_SPACE_GENERIC, speed) < 3;
726 else
727 inv->cheap_address = false;
729 else
731 inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
732 speed);
733 inv->cheap_address = false;
736 inv->move = false;
737 inv->reg = NULL_RTX;
738 inv->orig_regno = -1;
739 inv->stamp = 0;
740 inv->insn = insn;
742 inv->invno = invariants.length ();
743 inv->eqto = ~0u;
745 /* Itself. */
746 inv->eqno = 1;
748 if (def)
749 def->invno = inv->invno;
750 invariants.safe_push (inv);
752 if (dump_file)
754 fprintf (dump_file,
755 "Set in insn %d is invariant (%d), cost %d, depends on ",
756 INSN_UID (insn), inv->invno, inv->cost);
757 dump_bitmap (dump_file, inv->depends_on);
760 return inv;
763 /* Return a canonical version of X for the address, from the point of view,
764 that all multiplications are represented as MULT instead of the multiply
765 by a power of 2 being represented as ASHIFT.
767 Callers should prepare a copy of X because this function may modify it
768 in place. */
770 static void
771 canonicalize_address_mult (rtx x)
773 subrtx_var_iterator::array_type array;
774 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
776 rtx sub = *iter;
777 scalar_int_mode sub_mode;
778 if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
779 && GET_CODE (sub) == ASHIFT
780 && CONST_INT_P (XEXP (sub, 1))
781 && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
782 && INTVAL (XEXP (sub, 1)) >= 0)
784 HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
785 PUT_CODE (sub, MULT);
786 XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
787 iter.skip_subrtxes ();
792 /* Maximum number of sub expressions in address. We set it to
793 a small integer since it's unlikely to have a complicated
794 address expression. */
796 #define MAX_CANON_ADDR_PARTS (5)
798 /* Collect sub expressions in address X with PLUS as the seperator.
799 Sub expressions are stored in vector ADDR_PARTS. */
801 static void
802 collect_address_parts (rtx x, vec<rtx> *addr_parts)
804 subrtx_var_iterator::array_type array;
805 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
807 rtx sub = *iter;
809 if (GET_CODE (sub) != PLUS)
811 addr_parts->safe_push (sub);
812 iter.skip_subrtxes ();
817 /* Compare function for sorting sub expressions X and Y based on
818 precedence defined for communitive operations. */
820 static int
821 compare_address_parts (const void *x, const void *y)
823 const rtx *rx = (const rtx *)x;
824 const rtx *ry = (const rtx *)y;
825 int px = commutative_operand_precedence (*rx);
826 int py = commutative_operand_precedence (*ry);
828 return (py - px);
831 /* Return a canonical version address for X by following steps:
832 1) Rewrite ASHIFT into MULT recursively.
833 2) Divide address into sub expressions with PLUS as the
834 separator.
835 3) Sort sub expressions according to precedence defined
836 for communative operations.
837 4) Simplify CONST_INT_P sub expressions.
838 5) Create new canonicalized address and return.
839 Callers should prepare a copy of X because this function may
840 modify it in place. */
842 static rtx
843 canonicalize_address (rtx x)
845 rtx res;
846 unsigned int i, j;
847 machine_mode mode = GET_MODE (x);
848 auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
850 /* Rewrite ASHIFT into MULT. */
851 canonicalize_address_mult (x);
852 /* Divide address into sub expressions. */
853 collect_address_parts (x, &addr_parts);
854 /* Unlikely to have very complicated address. */
855 if (addr_parts.length () < 2
856 || addr_parts.length () > MAX_CANON_ADDR_PARTS)
857 return x;
859 /* Sort sub expressions according to canonicalization precedence. */
860 addr_parts.qsort (compare_address_parts);
862 /* Simplify all constant int summary if possible. */
863 for (i = 0; i < addr_parts.length (); i++)
864 if (CONST_INT_P (addr_parts[i]))
865 break;
867 for (j = i + 1; j < addr_parts.length (); j++)
869 gcc_assert (CONST_INT_P (addr_parts[j]));
870 addr_parts[i] = simplify_gen_binary (PLUS, mode,
871 addr_parts[i],
872 addr_parts[j]);
875 /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
876 res = addr_parts[0];
877 for (j = 1; j < i; j++)
878 res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
880 /* Pickup the last CONST_INT_P sub expression. */
881 if (i < addr_parts.length ())
882 res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
884 return res;
887 /* Given invariant DEF and its address USE, check if the corresponding
888 invariant expr can be propagated into the use or not. */
890 static bool
891 inv_can_prop_to_addr_use (struct def *def, df_ref use)
893 struct invariant *inv;
894 rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
895 rtx_insn *use_insn = DF_REF_INSN (use);
896 rtx_insn *def_insn;
897 bool ok;
899 inv = invariants[def->invno];
900 /* No need to check if address expression is expensive. */
901 if (!inv->cheap_address)
902 return false;
904 def_insn = inv->insn;
905 def_set = single_set (def_insn);
906 if (!def_set)
907 return false;
909 validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
910 ok = verify_changes (0);
911 /* Try harder with canonicalization in address expression. */
912 if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
914 rtx src, dest, mem = NULL_RTX;
916 src = SET_SRC (use_set);
917 dest = SET_DEST (use_set);
918 if (MEM_P (src))
919 mem = src;
920 else if (MEM_P (dest))
921 mem = dest;
923 if (mem != NULL_RTX
924 && !memory_address_addr_space_p (GET_MODE (mem),
925 XEXP (mem, 0),
926 MEM_ADDR_SPACE (mem)))
928 rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
929 if (memory_address_addr_space_p (GET_MODE (mem),
930 addr, MEM_ADDR_SPACE (mem)))
931 ok = true;
934 cancel_changes (0);
935 return ok;
938 /* Record USE at DEF. */
940 static void
941 record_use (struct def *def, df_ref use)
943 struct use *u = XNEW (struct use);
945 u->pos = DF_REF_REAL_LOC (use);
946 u->insn = DF_REF_INSN (use);
947 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
948 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
949 u->next = def->uses;
950 def->uses = u;
951 def->n_uses++;
952 if (u->addr_use_p)
954 /* Initialize propagation information if this is the first addr
955 use of the inv def. */
956 if (def->n_addr_uses == 0)
957 def->can_prop_to_addr_uses = true;
959 def->n_addr_uses++;
960 if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
961 def->can_prop_to_addr_uses = false;
965 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
966 bitmap. Returns true if all dependencies of USE are known to be
967 loop invariants, false otherwise. */
969 static bool
970 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
972 df_ref def;
973 basic_block def_bb;
974 struct df_link *defs;
975 struct def *def_data;
976 struct invariant *inv;
978 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
979 return false;
981 defs = DF_REF_CHAIN (use);
982 if (!defs)
984 unsigned int regno = DF_REF_REGNO (use);
986 /* If this is the use of an uninitialized argument register that is
987 likely to be spilled, do not move it lest this might extend its
988 lifetime and cause reload to die. This can occur for a call to
989 a function taking complex number arguments and moving the insns
990 preparing the arguments without moving the call itself wouldn't
991 gain much in practice. */
992 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
993 && FUNCTION_ARG_REGNO_P (regno)
994 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
995 return false;
997 return true;
1000 if (defs->next)
1001 return false;
1003 def = defs->ref;
1004 check_invariant_table_size ();
1005 inv = invariant_table[DF_REF_ID (def)];
1006 if (!inv)
1007 return false;
1009 def_data = inv->def;
1010 gcc_assert (def_data != NULL);
1012 def_bb = DF_REF_BB (def);
1013 /* Note that in case bb == def_bb, we know that the definition
1014 dominates insn, because def has invariant_table[DF_REF_ID(def)]
1015 defined and we process the insns in the basic block bb
1016 sequentially. */
1017 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1018 return false;
1020 bitmap_set_bit (depends_on, def_data->invno);
1021 return true;
1025 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1026 bitmap. Returns true if all dependencies of INSN are known to be
1027 loop invariants, false otherwise. */
1029 static bool
1030 check_dependencies (rtx_insn *insn, bitmap depends_on)
1032 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1033 df_ref use;
1034 basic_block bb = BLOCK_FOR_INSN (insn);
1036 FOR_EACH_INSN_INFO_USE (use, insn_info)
1037 if (!check_dependency (bb, use, depends_on))
1038 return false;
1039 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1040 if (!check_dependency (bb, use, depends_on))
1041 return false;
1043 return true;
1046 /* Pre-check candidate DEST to skip the one which can not make a valid insn
1047 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1048 static bool
1049 pre_check_invariant_p (bool simple, rtx dest)
1051 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1053 df_ref use;
1054 unsigned int i = REGNO (dest);
1055 struct df_insn_info *insn_info;
1056 df_ref def_rec;
1058 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1060 rtx_insn *ref = DF_REF_INSN (use);
1061 insn_info = DF_INSN_INFO_GET (ref);
1063 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1064 if (DF_REF_REGNO (def_rec) == i)
1066 /* Multi definitions at this stage, most likely are due to
1067 instruction constraints, which requires both read and write
1068 on the same register. Since move_invariant_reg is not
1069 powerful enough to handle such cases, just ignore the INV
1070 and leave the chance to others. */
1071 return false;
1075 return true;
1078 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
1079 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1080 unless the program ends due to a function call. */
1082 static void
1083 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1085 df_ref ref;
1086 struct def *def;
1087 bitmap depends_on;
1088 rtx set, dest;
1089 bool simple = true;
1090 struct invariant *inv;
1092 /* We can't move a CC0 setter without the user. */
1093 if (HAVE_cc0 && sets_cc0_p (insn))
1094 return;
1096 set = single_set (insn);
1097 if (!set)
1098 return;
1099 dest = SET_DEST (set);
1101 if (!REG_P (dest)
1102 || HARD_REGISTER_P (dest))
1103 simple = false;
1105 if (!may_assign_reg_p (dest)
1106 || !pre_check_invariant_p (simple, dest)
1107 || !check_maybe_invariant (SET_SRC (set)))
1108 return;
1110 /* If the insn can throw exception, we cannot move it at all without changing
1111 cfg. */
1112 if (can_throw_internal (insn))
1113 return;
1115 /* We cannot make trapping insn executed, unless it was executed before. */
1116 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1117 return;
1119 depends_on = BITMAP_ALLOC (NULL);
1120 if (!check_dependencies (insn, depends_on))
1122 BITMAP_FREE (depends_on);
1123 return;
1126 if (simple)
1127 def = XCNEW (struct def);
1128 else
1129 def = NULL;
1131 inv = create_new_invariant (def, insn, depends_on, always_executed);
1133 if (simple)
1135 ref = df_find_def (insn, dest);
1136 check_invariant_table_size ();
1137 invariant_table[DF_REF_ID (ref)] = inv;
1141 /* Record registers used in INSN that have a unique invariant definition. */
1143 static void
1144 record_uses (rtx_insn *insn)
1146 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1147 df_ref use;
1148 struct invariant *inv;
1150 FOR_EACH_INSN_INFO_USE (use, insn_info)
1152 inv = invariant_for_use (use);
1153 if (inv)
1154 record_use (inv->def, use);
1156 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1158 inv = invariant_for_use (use);
1159 if (inv)
1160 record_use (inv->def, use);
1164 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
1165 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1166 unless the program ends due to a function call. */
1168 static void
1169 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1171 find_invariant_insn (insn, always_reached, always_executed);
1172 record_uses (insn);
1175 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1176 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1177 block is always executed, unless the program ends due to a function
1178 call. */
1180 static void
1181 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1183 rtx_insn *insn;
1185 FOR_BB_INSNS (bb, insn)
1187 if (!NONDEBUG_INSN_P (insn))
1188 continue;
1190 find_invariants_insn (insn, always_reached, always_executed);
1192 if (always_reached
1193 && CALL_P (insn)
1194 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1195 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1196 always_reached = false;
1200 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1201 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1202 bitmap of basic blocks in BODY that are always executed unless the program
1203 ends due to a function call. */
1205 static void
1206 find_invariants_body (struct loop *loop, basic_block *body,
1207 bitmap always_reached, bitmap always_executed)
1209 unsigned i;
1211 for (i = 0; i < loop->num_nodes; i++)
1212 find_invariants_bb (body[i],
1213 bitmap_bit_p (always_reached, i),
1214 bitmap_bit_p (always_executed, i));
1217 /* Finds invariants in LOOP. */
1219 static void
1220 find_invariants (struct loop *loop)
1222 auto_bitmap may_exit;
1223 auto_bitmap always_reached;
1224 auto_bitmap has_exit;
1225 auto_bitmap always_executed;
1226 basic_block *body = get_loop_body_in_dom_order (loop);
1228 find_exits (loop, body, may_exit, has_exit);
1229 compute_always_reached (loop, body, may_exit, always_reached);
1230 compute_always_reached (loop, body, has_exit, always_executed);
1232 find_defs (loop);
1233 find_invariants_body (loop, body, always_reached, always_executed);
1234 merge_identical_invariants ();
1236 free (body);
1239 /* Frees a list of uses USE. */
1241 static void
1242 free_use_list (struct use *use)
1244 struct use *next;
1246 for (; use; use = next)
1248 next = use->next;
1249 free (use);
1253 /* Return pressure class and number of hard registers (through *NREGS)
1254 for destination of INSN. */
1255 static enum reg_class
1256 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1258 rtx reg;
1259 enum reg_class pressure_class;
1260 rtx set = single_set (insn);
1262 /* Considered invariant insns have only one set. */
1263 gcc_assert (set != NULL_RTX);
1264 reg = SET_DEST (set);
1265 if (GET_CODE (reg) == SUBREG)
1266 reg = SUBREG_REG (reg);
1267 if (MEM_P (reg))
1269 *nregs = 0;
1270 pressure_class = NO_REGS;
1272 else
1274 if (! REG_P (reg))
1275 reg = NULL_RTX;
1276 if (reg == NULL_RTX)
1277 pressure_class = GENERAL_REGS;
1278 else
1280 pressure_class = reg_allocno_class (REGNO (reg));
1281 pressure_class = ira_pressure_class_translate[pressure_class];
1283 *nregs
1284 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1286 return pressure_class;
1289 /* Calculates cost and number of registers needed for moving invariant INV
1290 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1291 the REG_CLASS of INV. Return
1292 -1: if INV is invalid.
1293 0: if INV and its depends_on have same reg_class
1294 1: if INV and its depends_on have different reg_classes. */
1296 static int
1297 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1298 enum reg_class *cl)
1300 int i, acomp_cost;
1301 unsigned aregs_needed[N_REG_CLASSES];
1302 unsigned depno;
1303 struct invariant *dep;
1304 bitmap_iterator bi;
1305 int ret = 1;
1307 /* Find the representative of the class of the equivalent invariants. */
1308 inv = invariants[inv->eqto];
1310 *comp_cost = 0;
1311 if (! flag_ira_loop_pressure)
1312 regs_needed[0] = 0;
1313 else
1315 for (i = 0; i < ira_pressure_classes_num; i++)
1316 regs_needed[ira_pressure_classes[i]] = 0;
1319 if (inv->move
1320 || inv->stamp == actual_stamp)
1321 return -1;
1322 inv->stamp = actual_stamp;
1324 if (! flag_ira_loop_pressure)
1325 regs_needed[0]++;
1326 else
1328 int nregs;
1329 enum reg_class pressure_class;
1331 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1332 regs_needed[pressure_class] += nregs;
1333 *cl = pressure_class;
1334 ret = 0;
1337 if (!inv->cheap_address
1338 || inv->def->n_uses == 0
1339 || inv->def->n_addr_uses < inv->def->n_uses
1340 /* Count cost if the inv can't be propagated into address uses. */
1341 || !inv->def->can_prop_to_addr_uses)
1342 (*comp_cost) += inv->cost * inv->eqno;
1344 #ifdef STACK_REGS
1346 /* Hoisting constant pool constants into stack regs may cost more than
1347 just single register. On x87, the balance is affected both by the
1348 small number of FP registers, and by its register stack organization,
1349 that forces us to add compensation code in and around the loop to
1350 shuffle the operands to the top of stack before use, and pop them
1351 from the stack after the loop finishes.
1353 To model this effect, we increase the number of registers needed for
1354 stack registers by two: one register push, and one register pop.
1355 This usually has the effect that FP constant loads from the constant
1356 pool are not moved out of the loop.
1358 Note that this also means that dependent invariants can not be moved.
1359 However, the primary purpose of this pass is to move loop invariant
1360 address arithmetic out of loops, and address arithmetic that depends
1361 on floating point constants is unlikely to ever occur. */
1362 rtx set = single_set (inv->insn);
1363 if (set
1364 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1365 && constant_pool_constant_p (SET_SRC (set)))
1367 if (flag_ira_loop_pressure)
1368 regs_needed[ira_stack_reg_pressure_class] += 2;
1369 else
1370 regs_needed[0] += 2;
1373 #endif
1375 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1377 bool check_p;
1378 enum reg_class dep_cl = ALL_REGS;
1379 int dep_ret;
1381 dep = invariants[depno];
1383 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1384 if (dep->move)
1385 continue;
1387 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1389 if (! flag_ira_loop_pressure)
1390 check_p = aregs_needed[0] != 0;
1391 else
1393 for (i = 0; i < ira_pressure_classes_num; i++)
1394 if (aregs_needed[ira_pressure_classes[i]] != 0)
1395 break;
1396 check_p = i < ira_pressure_classes_num;
1398 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1400 *cl = ALL_REGS;
1401 ret = 1;
1404 if (check_p
1405 /* We need to check always_executed, since if the original value of
1406 the invariant may be preserved, we may need to keep it in a
1407 separate register. TODO check whether the register has an
1408 use outside of the loop. */
1409 && dep->always_executed
1410 && !dep->def->uses->next)
1412 /* If this is a single use, after moving the dependency we will not
1413 need a new register. */
1414 if (! flag_ira_loop_pressure)
1415 aregs_needed[0]--;
1416 else
1418 int nregs;
1419 enum reg_class pressure_class;
1421 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1422 aregs_needed[pressure_class] -= nregs;
1426 if (! flag_ira_loop_pressure)
1427 regs_needed[0] += aregs_needed[0];
1428 else
1430 for (i = 0; i < ira_pressure_classes_num; i++)
1431 regs_needed[ira_pressure_classes[i]]
1432 += aregs_needed[ira_pressure_classes[i]];
1434 (*comp_cost) += acomp_cost;
1436 return ret;
1439 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1440 of registers used in the loop, NEW_REGS is the number of new variables
1441 already added due to the invariant motion. The number of registers needed
1442 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1443 through to estimate_reg_pressure_cost. */
1445 static int
1446 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1447 unsigned *new_regs, unsigned regs_used,
1448 bool speed, bool call_p)
1450 int comp_cost, size_cost;
1451 /* Workaround -Wmaybe-uninitialized false positive during
1452 profiledbootstrap by initializing it. */
1453 enum reg_class cl = NO_REGS;
1454 int ret;
1456 actual_stamp++;
1458 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1460 if (! flag_ira_loop_pressure)
1462 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1463 regs_used, speed, call_p)
1464 - estimate_reg_pressure_cost (new_regs[0],
1465 regs_used, speed, call_p));
1467 else if (ret < 0)
1468 return -1;
1469 else if ((ret == 0) && (cl == NO_REGS))
1470 /* Hoist it anyway since it does not impact register pressure. */
1471 return 1;
1472 else
1474 int i;
1475 enum reg_class pressure_class;
1477 for (i = 0; i < ira_pressure_classes_num; i++)
1479 pressure_class = ira_pressure_classes[i];
1481 if (!reg_classes_intersect_p (pressure_class, cl))
1482 continue;
1484 if ((int) new_regs[pressure_class]
1485 + (int) regs_needed[pressure_class]
1486 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1487 + IRA_LOOP_RESERVED_REGS
1488 > ira_class_hard_regs_num[pressure_class])
1489 break;
1491 if (i < ira_pressure_classes_num)
1492 /* There will be register pressure excess and we want not to
1493 make this loop invariant motion. All loop invariants with
1494 non-positive gains will be rejected in function
1495 find_invariants_to_move. Therefore we return the negative
1496 number here.
1498 One could think that this rejects also expensive loop
1499 invariant motions and this will hurt code performance.
1500 However numerous experiments with different heuristics
1501 taking invariant cost into account did not confirm this
1502 assumption. There are possible explanations for this
1503 result:
1504 o probably all expensive invariants were already moved out
1505 of the loop by PRE and gimple invariant motion pass.
1506 o expensive invariant execution will be hidden by insn
1507 scheduling or OOO processor hardware because usually such
1508 invariants have a lot of freedom to be executed
1509 out-of-order.
1510 Another reason for ignoring invariant cost vs spilling cost
1511 heuristics is also in difficulties to evaluate accurately
1512 spill cost at this stage. */
1513 return -1;
1514 else
1515 size_cost = 0;
1518 return comp_cost - size_cost;
1521 /* Finds invariant with best gain for moving. Returns the gain, stores
1522 the invariant in *BEST and number of registers needed for it to
1523 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1524 NEW_REGS is the number of new variables already added due to invariant
1525 motion. */
1527 static int
1528 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1529 unsigned *new_regs, unsigned regs_used,
1530 bool speed, bool call_p)
1532 struct invariant *inv;
1533 int i, gain = 0, again;
1534 unsigned aregs_needed[N_REG_CLASSES], invno;
1536 FOR_EACH_VEC_ELT (invariants, invno, inv)
1538 if (inv->move)
1539 continue;
1541 /* Only consider the "representatives" of equivalent invariants. */
1542 if (inv->eqto != inv->invno)
1543 continue;
1545 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1546 speed, call_p);
1547 if (again > gain)
1549 gain = again;
1550 *best = inv;
1551 if (! flag_ira_loop_pressure)
1552 regs_needed[0] = aregs_needed[0];
1553 else
1555 for (i = 0; i < ira_pressure_classes_num; i++)
1556 regs_needed[ira_pressure_classes[i]]
1557 = aregs_needed[ira_pressure_classes[i]];
1562 return gain;
1565 /* Marks invariant INVNO and all its dependencies for moving. */
1567 static void
1568 set_move_mark (unsigned invno, int gain)
1570 struct invariant *inv = invariants[invno];
1571 bitmap_iterator bi;
1573 /* Find the representative of the class of the equivalent invariants. */
1574 inv = invariants[inv->eqto];
1576 if (inv->move)
1577 return;
1578 inv->move = true;
1580 if (dump_file)
1582 if (gain >= 0)
1583 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1584 invno, gain);
1585 else
1586 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1587 invno);
1590 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1592 set_move_mark (invno, -1);
1596 /* Determines which invariants to move. */
1598 static void
1599 find_invariants_to_move (bool speed, bool call_p)
1601 int gain;
1602 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1603 struct invariant *inv = NULL;
1605 if (!invariants.length ())
1606 return;
1608 if (flag_ira_loop_pressure)
1609 /* REGS_USED is actually never used when the flag is on. */
1610 regs_used = 0;
1611 else
1612 /* We do not really do a good job in estimating number of
1613 registers used; we put some initial bound here to stand for
1614 induction variables etc. that we do not detect. */
1616 unsigned int n_regs = DF_REG_SIZE (df);
1618 regs_used = 2;
1620 for (i = 0; i < n_regs; i++)
1622 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1624 /* This is a value that is used but not changed inside loop. */
1625 regs_used++;
1630 if (! flag_ira_loop_pressure)
1631 new_regs[0] = regs_needed[0] = 0;
1632 else
1634 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1635 new_regs[ira_pressure_classes[i]] = 0;
1637 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1638 new_regs, regs_used,
1639 speed, call_p)) > 0)
1641 set_move_mark (inv->invno, gain);
1642 if (! flag_ira_loop_pressure)
1643 new_regs[0] += regs_needed[0];
1644 else
1646 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1647 new_regs[ira_pressure_classes[i]]
1648 += regs_needed[ira_pressure_classes[i]];
1653 /* Replace the uses, reached by the definition of invariant INV, by REG.
1655 IN_GROUP is nonzero if this is part of a group of changes that must be
1656 performed as a group. In that case, the changes will be stored. The
1657 function `apply_change_group' will validate and apply the changes. */
1659 static int
1660 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1662 /* Replace the uses we know to be dominated. It saves work for copy
1663 propagation, and also it is necessary so that dependent invariants
1664 are computed right. */
1665 if (inv->def)
1667 struct use *use;
1668 for (use = inv->def->uses; use; use = use->next)
1669 validate_change (use->insn, use->pos, reg, true);
1671 /* If we aren't part of a larger group, apply the changes now. */
1672 if (!in_group)
1673 return apply_change_group ();
1676 return 1;
1679 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1680 the block preceding its header. */
1682 static bool
1683 can_move_invariant_reg (struct loop *loop, struct invariant *inv, rtx reg)
1685 df_ref def, use;
1686 unsigned int dest_regno, defs_in_loop_count = 0;
1687 rtx_insn *insn = inv->insn;
1688 basic_block bb = BLOCK_FOR_INSN (inv->insn);
1690 /* We ignore hard register and memory access for cost and complexity reasons.
1691 Hard register are few at this stage and expensive to consider as they
1692 require building a separate data flow. Memory access would require using
1693 df_simulate_* and can_move_insns_across functions and is more complex. */
1694 if (!REG_P (reg) || HARD_REGISTER_P (reg))
1695 return false;
1697 /* Check whether the set is always executed. We could omit this condition if
1698 we know that the register is unused outside of the loop, but it does not
1699 seem worth finding out. */
1700 if (!inv->always_executed)
1701 return false;
1703 /* Check that all uses that would be dominated by def are already dominated
1704 by it. */
1705 dest_regno = REGNO (reg);
1706 for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1708 rtx_insn *use_insn;
1709 basic_block use_bb;
1711 use_insn = DF_REF_INSN (use);
1712 use_bb = BLOCK_FOR_INSN (use_insn);
1714 /* Ignore instruction considered for moving. */
1715 if (use_insn == insn)
1716 continue;
1718 /* Don't consider uses outside loop. */
1719 if (!flow_bb_inside_loop_p (loop, use_bb))
1720 continue;
1722 /* Don't move if a use is not dominated by def in insn. */
1723 if (use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1724 return false;
1725 if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1726 return false;
1729 /* Check for other defs. Any other def in the loop might reach a use
1730 currently reached by the def in insn. */
1731 for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1733 basic_block def_bb = DF_REF_BB (def);
1735 /* Defs in exit block cannot reach a use they weren't already. */
1736 if (single_succ_p (def_bb))
1738 basic_block def_bb_succ;
1740 def_bb_succ = single_succ (def_bb);
1741 if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1742 continue;
1745 if (++defs_in_loop_count > 1)
1746 return false;
1749 return true;
1752 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1753 otherwise. */
1755 static bool
1756 move_invariant_reg (struct loop *loop, unsigned invno)
1758 struct invariant *inv = invariants[invno];
1759 struct invariant *repr = invariants[inv->eqto];
1760 unsigned i;
1761 basic_block preheader = loop_preheader_edge (loop)->src;
1762 rtx reg, set, dest, note;
1763 bitmap_iterator bi;
1764 int regno = -1;
1766 if (inv->reg)
1767 return true;
1768 if (!repr->move)
1769 return false;
1771 /* If this is a representative of the class of equivalent invariants,
1772 really move the invariant. Otherwise just replace its use with
1773 the register used for the representative. */
1774 if (inv == repr)
1776 if (inv->depends_on)
1778 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1780 if (!move_invariant_reg (loop, i))
1781 goto fail;
1785 /* If possible, just move the set out of the loop. Otherwise, we
1786 need to create a temporary register. */
1787 set = single_set (inv->insn);
1788 reg = dest = SET_DEST (set);
1789 if (GET_CODE (reg) == SUBREG)
1790 reg = SUBREG_REG (reg);
1791 if (REG_P (reg))
1792 regno = REGNO (reg);
1794 if (!can_move_invariant_reg (loop, inv, dest))
1796 reg = gen_reg_rtx_and_attrs (dest);
1798 /* Try replacing the destination by a new pseudoregister. */
1799 validate_change (inv->insn, &SET_DEST (set), reg, true);
1801 /* As well as all the dominated uses. */
1802 replace_uses (inv, reg, true);
1804 /* And validate all the changes. */
1805 if (!apply_change_group ())
1806 goto fail;
1808 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1810 else if (dump_file)
1811 fprintf (dump_file, "Invariant %d moved without introducing a new "
1812 "temporary register\n", invno);
1813 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1814 df_recompute_luids (preheader);
1816 /* If there is a REG_EQUAL note on the insn we just moved, and the
1817 insn is in a basic block that is not always executed or the note
1818 contains something for which we don't know the invariant status,
1819 the note may no longer be valid after we move the insn. Note that
1820 uses in REG_EQUAL notes are taken into account in the computation
1821 of invariants, so it is safe to retain the note even if it contains
1822 register references for which we know the invariant status. */
1823 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1824 && (!inv->always_executed
1825 || !check_maybe_invariant (XEXP (note, 0))))
1826 remove_note (inv->insn, note);
1828 else
1830 if (!move_invariant_reg (loop, repr->invno))
1831 goto fail;
1832 reg = repr->reg;
1833 regno = repr->orig_regno;
1834 if (!replace_uses (inv, reg, false))
1835 goto fail;
1836 set = single_set (inv->insn);
1837 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1838 delete_insn (inv->insn);
1841 inv->reg = reg;
1842 inv->orig_regno = regno;
1844 return true;
1846 fail:
1847 /* If we failed, clear move flag, so that we do not try to move inv
1848 again. */
1849 if (dump_file)
1850 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1851 inv->move = false;
1852 inv->reg = NULL_RTX;
1853 inv->orig_regno = -1;
1855 return false;
1858 /* Move selected invariant out of the LOOP. Newly created regs are marked
1859 in TEMPORARY_REGS. */
1861 static void
1862 move_invariants (struct loop *loop)
1864 struct invariant *inv;
1865 unsigned i;
1867 FOR_EACH_VEC_ELT (invariants, i, inv)
1868 move_invariant_reg (loop, i);
1869 if (flag_ira_loop_pressure && resize_reg_info ())
1871 FOR_EACH_VEC_ELT (invariants, i, inv)
1872 if (inv->reg != NULL_RTX)
1874 if (inv->orig_regno >= 0)
1875 setup_reg_classes (REGNO (inv->reg),
1876 reg_preferred_class (inv->orig_regno),
1877 reg_alternate_class (inv->orig_regno),
1878 reg_allocno_class (inv->orig_regno));
1879 else
1880 setup_reg_classes (REGNO (inv->reg),
1881 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1886 /* Initializes invariant motion data. */
1888 static void
1889 init_inv_motion_data (void)
1891 actual_stamp = 1;
1893 invariants.create (100);
1896 /* Frees the data allocated by invariant motion. */
1898 static void
1899 free_inv_motion_data (void)
1901 unsigned i;
1902 struct def *def;
1903 struct invariant *inv;
1905 check_invariant_table_size ();
1906 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1908 inv = invariant_table[i];
1909 if (inv)
1911 def = inv->def;
1912 gcc_assert (def != NULL);
1914 free_use_list (def->uses);
1915 free (def);
1916 invariant_table[i] = NULL;
1920 FOR_EACH_VEC_ELT (invariants, i, inv)
1922 BITMAP_FREE (inv->depends_on);
1923 free (inv);
1925 invariants.release ();
1928 /* Move the invariants out of the LOOP. */
1930 static void
1931 move_single_loop_invariants (struct loop *loop)
1933 init_inv_motion_data ();
1935 find_invariants (loop);
1936 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1937 LOOP_DATA (loop)->has_call);
1938 move_invariants (loop);
1940 free_inv_motion_data ();
1943 /* Releases the auxiliary data for LOOP. */
1945 static void
1946 free_loop_data (struct loop *loop)
1948 struct loop_data *data = LOOP_DATA (loop);
1949 if (!data)
1950 return;
1952 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1953 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1954 free (data);
1955 loop->aux = NULL;
1960 /* Registers currently living. */
1961 static bitmap_head curr_regs_live;
1963 /* Current reg pressure for each pressure class. */
1964 static int curr_reg_pressure[N_REG_CLASSES];
1966 /* Record all regs that are set in any one insn. Communication from
1967 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1968 all hard-registers. */
1969 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1970 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1971 /* Number of regs stored in the previous array. */
1972 static int n_regs_set;
1974 /* Return pressure class and number of needed hard registers (through
1975 *NREGS) of register REGNO. */
1976 static enum reg_class
1977 get_regno_pressure_class (int regno, int *nregs)
1979 if (regno >= FIRST_PSEUDO_REGISTER)
1981 enum reg_class pressure_class;
1983 pressure_class = reg_allocno_class (regno);
1984 pressure_class = ira_pressure_class_translate[pressure_class];
1985 *nregs
1986 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1987 return pressure_class;
1989 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1990 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1992 *nregs = 1;
1993 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1995 else
1997 *nregs = 0;
1998 return NO_REGS;
2002 /* Increase (if INCR_P) or decrease current register pressure for
2003 register REGNO. */
2004 static void
2005 change_pressure (int regno, bool incr_p)
2007 int nregs;
2008 enum reg_class pressure_class;
2010 pressure_class = get_regno_pressure_class (regno, &nregs);
2011 if (! incr_p)
2012 curr_reg_pressure[pressure_class] -= nregs;
2013 else
2015 curr_reg_pressure[pressure_class] += nregs;
2016 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2017 < curr_reg_pressure[pressure_class])
2018 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2019 = curr_reg_pressure[pressure_class];
2023 /* Mark REGNO birth. */
2024 static void
2025 mark_regno_live (int regno)
2027 struct loop *loop;
2029 for (loop = curr_loop;
2030 loop != current_loops->tree_root;
2031 loop = loop_outer (loop))
2032 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2033 if (!bitmap_set_bit (&curr_regs_live, regno))
2034 return;
2035 change_pressure (regno, true);
2038 /* Mark REGNO death. */
2039 static void
2040 mark_regno_death (int regno)
2042 if (! bitmap_clear_bit (&curr_regs_live, regno))
2043 return;
2044 change_pressure (regno, false);
2047 /* Mark setting register REG. */
2048 static void
2049 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2050 void *data ATTRIBUTE_UNUSED)
2052 if (GET_CODE (reg) == SUBREG)
2053 reg = SUBREG_REG (reg);
2055 if (! REG_P (reg))
2056 return;
2058 regs_set[n_regs_set++] = reg;
2060 unsigned int end_regno = END_REGNO (reg);
2061 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2062 mark_regno_live (regno);
2065 /* Mark clobbering register REG. */
2066 static void
2067 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2069 if (GET_CODE (setter) == CLOBBER)
2070 mark_reg_store (reg, setter, data);
2073 /* Mark register REG death. */
2074 static void
2075 mark_reg_death (rtx reg)
2077 unsigned int end_regno = END_REGNO (reg);
2078 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2079 mark_regno_death (regno);
2082 /* Mark occurrence of registers in X for the current loop. */
2083 static void
2084 mark_ref_regs (rtx x)
2086 RTX_CODE code;
2087 int i;
2088 const char *fmt;
2090 if (!x)
2091 return;
2093 code = GET_CODE (x);
2094 if (code == REG)
2096 struct loop *loop;
2098 for (loop = curr_loop;
2099 loop != current_loops->tree_root;
2100 loop = loop_outer (loop))
2101 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2102 return;
2105 fmt = GET_RTX_FORMAT (code);
2106 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2107 if (fmt[i] == 'e')
2108 mark_ref_regs (XEXP (x, i));
2109 else if (fmt[i] == 'E')
2111 int j;
2113 for (j = 0; j < XVECLEN (x, i); j++)
2114 mark_ref_regs (XVECEXP (x, i, j));
2118 /* Calculate register pressure in the loops. */
2119 static void
2120 calculate_loop_reg_pressure (void)
2122 int i;
2123 unsigned int j;
2124 bitmap_iterator bi;
2125 basic_block bb;
2126 rtx_insn *insn;
2127 rtx link;
2128 struct loop *loop, *parent;
2130 FOR_EACH_LOOP (loop, 0)
2131 if (loop->aux == NULL)
2133 loop->aux = xcalloc (1, sizeof (struct loop_data));
2134 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
2135 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
2137 ira_setup_eliminable_regset ();
2138 bitmap_initialize (&curr_regs_live, &reg_obstack);
2139 FOR_EACH_BB_FN (bb, cfun)
2141 curr_loop = bb->loop_father;
2142 if (curr_loop == current_loops->tree_root)
2143 continue;
2145 for (loop = curr_loop;
2146 loop != current_loops->tree_root;
2147 loop = loop_outer (loop))
2148 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2150 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2151 for (i = 0; i < ira_pressure_classes_num; i++)
2152 curr_reg_pressure[ira_pressure_classes[i]] = 0;
2153 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2154 change_pressure (j, true);
2156 FOR_BB_INSNS (bb, insn)
2158 if (! NONDEBUG_INSN_P (insn))
2159 continue;
2161 mark_ref_regs (PATTERN (insn));
2162 n_regs_set = 0;
2163 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
2165 /* Mark any registers dead after INSN as dead now. */
2167 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2168 if (REG_NOTE_KIND (link) == REG_DEAD)
2169 mark_reg_death (XEXP (link, 0));
2171 /* Mark any registers set in INSN as live,
2172 and mark them as conflicting with all other live regs.
2173 Clobbers are processed again, so they conflict with
2174 the registers that are set. */
2176 note_stores (PATTERN (insn), mark_reg_store, NULL);
2178 if (AUTO_INC_DEC)
2179 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2180 if (REG_NOTE_KIND (link) == REG_INC)
2181 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2183 while (n_regs_set-- > 0)
2185 rtx note = find_regno_note (insn, REG_UNUSED,
2186 REGNO (regs_set[n_regs_set]));
2187 if (! note)
2188 continue;
2190 mark_reg_death (XEXP (note, 0));
2194 bitmap_clear (&curr_regs_live);
2195 if (flag_ira_region == IRA_REGION_MIXED
2196 || flag_ira_region == IRA_REGION_ALL)
2197 FOR_EACH_LOOP (loop, 0)
2199 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2200 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2202 enum reg_class pressure_class;
2203 int nregs;
2205 pressure_class = get_regno_pressure_class (j, &nregs);
2206 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2209 if (dump_file == NULL)
2210 return;
2211 FOR_EACH_LOOP (loop, 0)
2213 parent = loop_outer (loop);
2214 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2215 loop->num, (parent == NULL ? -1 : parent->num),
2216 loop->header->index, loop_depth (loop));
2217 fprintf (dump_file, "\n ref. regnos:");
2218 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2219 fprintf (dump_file, " %d", j);
2220 fprintf (dump_file, "\n live regnos:");
2221 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2222 fprintf (dump_file, " %d", j);
2223 fprintf (dump_file, "\n Pressure:");
2224 for (i = 0; (int) i < ira_pressure_classes_num; i++)
2226 enum reg_class pressure_class;
2228 pressure_class = ira_pressure_classes[i];
2229 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2230 continue;
2231 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2232 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2234 fprintf (dump_file, "\n");
2240 /* Move the invariants out of the loops. */
2242 void
2243 move_loop_invariants (void)
2245 struct loop *loop;
2247 if (flag_ira_loop_pressure)
2249 df_analyze ();
2250 regstat_init_n_sets_and_refs ();
2251 ira_set_pseudo_classes (true, dump_file);
2252 calculate_loop_reg_pressure ();
2253 regstat_free_n_sets_and_refs ();
2255 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2256 /* Process the loops, innermost first. */
2257 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2259 curr_loop = loop;
2260 /* move_single_loop_invariants for very large loops
2261 is time consuming and might need a lot of memory. */
2262 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2263 move_single_loop_invariants (loop);
2266 FOR_EACH_LOOP (loop, 0)
2268 free_loop_data (loop);
2271 if (flag_ira_loop_pressure)
2272 /* There is no sense to keep this info because it was most
2273 probably outdated by subsequent passes. */
2274 free_reg_info ();
2275 free (invariant_table);
2276 invariant_table = NULL;
2277 invariant_table_size = 0;
2279 checking_verify_flow_info ();