Daily bump.
[official-gcc.git] / gcc / loop-invariant.c
blobbd31a51c1d59e12220ab77778743fccce74eb8b7
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 && (!REG_P (x)
664 || !HARD_REGISTER_P (x)
665 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
668 /* Finds definitions that may correspond to invariants in LOOP with body
669 BODY. */
671 static void
672 find_defs (struct loop *loop)
674 if (dump_file)
676 fprintf (dump_file,
677 "*****starting processing of loop %d ******\n",
678 loop->num);
681 df_remove_problem (df_chain);
682 df_process_deferred_rescans ();
683 df_chain_add_problem (DF_UD_CHAIN);
684 df_live_add_problem ();
685 df_live_set_all_dirty ();
686 df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
687 df_analyze_loop (loop);
688 check_invariant_table_size ();
690 if (dump_file)
692 df_dump_region (dump_file);
693 fprintf (dump_file,
694 "*****ending processing of loop %d ******\n",
695 loop->num);
699 /* Creates a new invariant for definition DEF in INSN, depending on invariants
700 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
701 unless the program ends due to a function call. The newly created invariant
702 is returned. */
704 static struct invariant *
705 create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
706 bool always_executed)
708 struct invariant *inv = XNEW (struct invariant);
709 rtx set = single_set (insn);
710 bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
712 inv->def = def;
713 inv->always_executed = always_executed;
714 inv->depends_on = depends_on;
716 /* If the set is simple, usually by moving it we move the whole store out of
717 the loop. Otherwise we save only cost of the computation. */
718 if (def)
720 inv->cost = set_rtx_cost (set, speed);
721 /* ??? Try to determine cheapness of address computation. Unfortunately
722 the address cost is only a relative measure, we can't really compare
723 it with any absolute number, but only with other address costs.
724 But here we don't have any other addresses, so compare with a magic
725 number anyway. It has to be large enough to not regress PR33928
726 (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
727 enough to not regress 410.bwaves either (by still moving reg+reg
728 invariants).
729 See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html . */
730 if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
731 inv->cheap_address = address_cost (SET_SRC (set), word_mode,
732 ADDR_SPACE_GENERIC, speed) < 3;
733 else
734 inv->cheap_address = false;
736 else
738 inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
739 speed);
740 inv->cheap_address = false;
743 inv->move = false;
744 inv->reg = NULL_RTX;
745 inv->orig_regno = -1;
746 inv->stamp = 0;
747 inv->insn = insn;
749 inv->invno = invariants.length ();
750 inv->eqto = ~0u;
752 /* Itself. */
753 inv->eqno = 1;
755 if (def)
756 def->invno = inv->invno;
757 invariants.safe_push (inv);
759 if (dump_file)
761 fprintf (dump_file,
762 "Set in insn %d is invariant (%d), cost %d, depends on ",
763 INSN_UID (insn), inv->invno, inv->cost);
764 dump_bitmap (dump_file, inv->depends_on);
767 return inv;
770 /* Return a canonical version of X for the address, from the point of view,
771 that all multiplications are represented as MULT instead of the multiply
772 by a power of 2 being represented as ASHIFT.
774 Callers should prepare a copy of X because this function may modify it
775 in place. */
777 static void
778 canonicalize_address_mult (rtx x)
780 subrtx_var_iterator::array_type array;
781 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
783 rtx sub = *iter;
784 scalar_int_mode sub_mode;
785 if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
786 && GET_CODE (sub) == ASHIFT
787 && CONST_INT_P (XEXP (sub, 1))
788 && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
789 && INTVAL (XEXP (sub, 1)) >= 0)
791 HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
792 PUT_CODE (sub, MULT);
793 XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
794 iter.skip_subrtxes ();
799 /* Maximum number of sub expressions in address. We set it to
800 a small integer since it's unlikely to have a complicated
801 address expression. */
803 #define MAX_CANON_ADDR_PARTS (5)
805 /* Collect sub expressions in address X with PLUS as the seperator.
806 Sub expressions are stored in vector ADDR_PARTS. */
808 static void
809 collect_address_parts (rtx x, vec<rtx> *addr_parts)
811 subrtx_var_iterator::array_type array;
812 FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
814 rtx sub = *iter;
816 if (GET_CODE (sub) != PLUS)
818 addr_parts->safe_push (sub);
819 iter.skip_subrtxes ();
824 /* Compare function for sorting sub expressions X and Y based on
825 precedence defined for communitive operations. */
827 static int
828 compare_address_parts (const void *x, const void *y)
830 const rtx *rx = (const rtx *)x;
831 const rtx *ry = (const rtx *)y;
832 int px = commutative_operand_precedence (*rx);
833 int py = commutative_operand_precedence (*ry);
835 return (py - px);
838 /* Return a canonical version address for X by following steps:
839 1) Rewrite ASHIFT into MULT recursively.
840 2) Divide address into sub expressions with PLUS as the
841 separator.
842 3) Sort sub expressions according to precedence defined
843 for communative operations.
844 4) Simplify CONST_INT_P sub expressions.
845 5) Create new canonicalized address and return.
846 Callers should prepare a copy of X because this function may
847 modify it in place. */
849 static rtx
850 canonicalize_address (rtx x)
852 rtx res;
853 unsigned int i, j;
854 machine_mode mode = GET_MODE (x);
855 auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
857 /* Rewrite ASHIFT into MULT. */
858 canonicalize_address_mult (x);
859 /* Divide address into sub expressions. */
860 collect_address_parts (x, &addr_parts);
861 /* Unlikely to have very complicated address. */
862 if (addr_parts.length () < 2
863 || addr_parts.length () > MAX_CANON_ADDR_PARTS)
864 return x;
866 /* Sort sub expressions according to canonicalization precedence. */
867 addr_parts.qsort (compare_address_parts);
869 /* Simplify all constant int summary if possible. */
870 for (i = 0; i < addr_parts.length (); i++)
871 if (CONST_INT_P (addr_parts[i]))
872 break;
874 for (j = i + 1; j < addr_parts.length (); j++)
876 gcc_assert (CONST_INT_P (addr_parts[j]));
877 addr_parts[i] = simplify_gen_binary (PLUS, mode,
878 addr_parts[i],
879 addr_parts[j]);
882 /* Chain PLUS operators to the left for !CONST_INT_P sub expressions. */
883 res = addr_parts[0];
884 for (j = 1; j < i; j++)
885 res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
887 /* Pickup the last CONST_INT_P sub expression. */
888 if (i < addr_parts.length ())
889 res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
891 return res;
894 /* Given invariant DEF and its address USE, check if the corresponding
895 invariant expr can be propagated into the use or not. */
897 static bool
898 inv_can_prop_to_addr_use (struct def *def, df_ref use)
900 struct invariant *inv;
901 rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
902 rtx_insn *use_insn = DF_REF_INSN (use);
903 rtx_insn *def_insn;
904 bool ok;
906 inv = invariants[def->invno];
907 /* No need to check if address expression is expensive. */
908 if (!inv->cheap_address)
909 return false;
911 def_insn = inv->insn;
912 def_set = single_set (def_insn);
913 if (!def_set)
914 return false;
916 validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
917 ok = verify_changes (0);
918 /* Try harder with canonicalization in address expression. */
919 if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
921 rtx src, dest, mem = NULL_RTX;
923 src = SET_SRC (use_set);
924 dest = SET_DEST (use_set);
925 if (MEM_P (src))
926 mem = src;
927 else if (MEM_P (dest))
928 mem = dest;
930 if (mem != NULL_RTX
931 && !memory_address_addr_space_p (GET_MODE (mem),
932 XEXP (mem, 0),
933 MEM_ADDR_SPACE (mem)))
935 rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
936 if (memory_address_addr_space_p (GET_MODE (mem),
937 addr, MEM_ADDR_SPACE (mem)))
938 ok = true;
941 cancel_changes (0);
942 return ok;
945 /* Record USE at DEF. */
947 static void
948 record_use (struct def *def, df_ref use)
950 struct use *u = XNEW (struct use);
952 u->pos = DF_REF_REAL_LOC (use);
953 u->insn = DF_REF_INSN (use);
954 u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
955 || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
956 u->next = def->uses;
957 def->uses = u;
958 def->n_uses++;
959 if (u->addr_use_p)
961 /* Initialize propagation information if this is the first addr
962 use of the inv def. */
963 if (def->n_addr_uses == 0)
964 def->can_prop_to_addr_uses = true;
966 def->n_addr_uses++;
967 if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
968 def->can_prop_to_addr_uses = false;
972 /* Finds the invariants USE depends on and store them to the DEPENDS_ON
973 bitmap. Returns true if all dependencies of USE are known to be
974 loop invariants, false otherwise. */
976 static bool
977 check_dependency (basic_block bb, df_ref use, bitmap depends_on)
979 df_ref def;
980 basic_block def_bb;
981 struct df_link *defs;
982 struct def *def_data;
983 struct invariant *inv;
985 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
986 return false;
988 defs = DF_REF_CHAIN (use);
989 if (!defs)
991 unsigned int regno = DF_REF_REGNO (use);
993 /* If this is the use of an uninitialized argument register that is
994 likely to be spilled, do not move it lest this might extend its
995 lifetime and cause reload to die. This can occur for a call to
996 a function taking complex number arguments and moving the insns
997 preparing the arguments without moving the call itself wouldn't
998 gain much in practice. */
999 if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
1000 && FUNCTION_ARG_REGNO_P (regno)
1001 && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
1002 return false;
1004 return true;
1007 if (defs->next)
1008 return false;
1010 def = defs->ref;
1011 check_invariant_table_size ();
1012 inv = invariant_table[DF_REF_ID (def)];
1013 if (!inv)
1014 return false;
1016 def_data = inv->def;
1017 gcc_assert (def_data != NULL);
1019 def_bb = DF_REF_BB (def);
1020 /* Note that in case bb == def_bb, we know that the definition
1021 dominates insn, because def has invariant_table[DF_REF_ID(def)]
1022 defined and we process the insns in the basic block bb
1023 sequentially. */
1024 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
1025 return false;
1027 bitmap_set_bit (depends_on, def_data->invno);
1028 return true;
1032 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
1033 bitmap. Returns true if all dependencies of INSN are known to be
1034 loop invariants, false otherwise. */
1036 static bool
1037 check_dependencies (rtx_insn *insn, bitmap depends_on)
1039 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1040 df_ref use;
1041 basic_block bb = BLOCK_FOR_INSN (insn);
1043 FOR_EACH_INSN_INFO_USE (use, insn_info)
1044 if (!check_dependency (bb, use, depends_on))
1045 return false;
1046 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1047 if (!check_dependency (bb, use, depends_on))
1048 return false;
1050 return true;
1053 /* Pre-check candidate DEST to skip the one which can not make a valid insn
1054 during move_invariant_reg. SIMPLE is to skip HARD_REGISTER. */
1055 static bool
1056 pre_check_invariant_p (bool simple, rtx dest)
1058 if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
1060 df_ref use;
1061 unsigned int i = REGNO (dest);
1062 struct df_insn_info *insn_info;
1063 df_ref def_rec;
1065 for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
1067 rtx_insn *ref = DF_REF_INSN (use);
1068 insn_info = DF_INSN_INFO_GET (ref);
1070 FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
1071 if (DF_REF_REGNO (def_rec) == i)
1073 /* Multi definitions at this stage, most likely are due to
1074 instruction constraints, which requires both read and write
1075 on the same register. Since move_invariant_reg is not
1076 powerful enough to handle such cases, just ignore the INV
1077 and leave the chance to others. */
1078 return false;
1082 return true;
1085 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
1086 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1087 unless the program ends due to a function call. */
1089 static void
1090 find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1092 df_ref ref;
1093 struct def *def;
1094 bitmap depends_on;
1095 rtx set, dest;
1096 bool simple = true;
1097 struct invariant *inv;
1099 /* We can't move a CC0 setter without the user. */
1100 if (HAVE_cc0 && sets_cc0_p (insn))
1101 return;
1103 set = single_set (insn);
1104 if (!set)
1105 return;
1106 dest = SET_DEST (set);
1108 if (!REG_P (dest)
1109 || HARD_REGISTER_P (dest))
1110 simple = false;
1112 if (!may_assign_reg_p (dest)
1113 || !pre_check_invariant_p (simple, dest)
1114 || !check_maybe_invariant (SET_SRC (set)))
1115 return;
1117 /* If the insn can throw exception, we cannot move it at all without changing
1118 cfg. */
1119 if (can_throw_internal (insn))
1120 return;
1122 /* We cannot make trapping insn executed, unless it was executed before. */
1123 if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
1124 return;
1126 depends_on = BITMAP_ALLOC (NULL);
1127 if (!check_dependencies (insn, depends_on))
1129 BITMAP_FREE (depends_on);
1130 return;
1133 if (simple)
1134 def = XCNEW (struct def);
1135 else
1136 def = NULL;
1138 inv = create_new_invariant (def, insn, depends_on, always_executed);
1140 if (simple)
1142 ref = df_find_def (insn, dest);
1143 check_invariant_table_size ();
1144 invariant_table[DF_REF_ID (ref)] = inv;
1148 /* Record registers used in INSN that have a unique invariant definition. */
1150 static void
1151 record_uses (rtx_insn *insn)
1153 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1154 df_ref use;
1155 struct invariant *inv;
1157 FOR_EACH_INSN_INFO_USE (use, insn_info)
1159 inv = invariant_for_use (use);
1160 if (inv)
1161 record_use (inv->def, use);
1163 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1165 inv = invariant_for_use (use);
1166 if (inv)
1167 record_use (inv->def, use);
1171 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
1172 executed. ALWAYS_EXECUTED is true if the insn is always executed,
1173 unless the program ends due to a function call. */
1175 static void
1176 find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
1178 find_invariant_insn (insn, always_reached, always_executed);
1179 record_uses (insn);
1182 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
1183 basic block is always executed. ALWAYS_EXECUTED is true if the basic
1184 block is always executed, unless the program ends due to a function
1185 call. */
1187 static void
1188 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
1190 rtx_insn *insn;
1192 FOR_BB_INSNS (bb, insn)
1194 if (!NONDEBUG_INSN_P (insn))
1195 continue;
1197 find_invariants_insn (insn, always_reached, always_executed);
1199 if (always_reached
1200 && CALL_P (insn)
1201 && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
1202 || ! RTL_CONST_OR_PURE_CALL_P (insn)))
1203 always_reached = false;
1207 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
1208 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
1209 bitmap of basic blocks in BODY that are always executed unless the program
1210 ends due to a function call. */
1212 static void
1213 find_invariants_body (struct loop *loop, basic_block *body,
1214 bitmap always_reached, bitmap always_executed)
1216 unsigned i;
1218 for (i = 0; i < loop->num_nodes; i++)
1219 find_invariants_bb (body[i],
1220 bitmap_bit_p (always_reached, i),
1221 bitmap_bit_p (always_executed, i));
1224 /* Finds invariants in LOOP. */
1226 static void
1227 find_invariants (struct loop *loop)
1229 auto_bitmap may_exit;
1230 auto_bitmap always_reached;
1231 auto_bitmap has_exit;
1232 auto_bitmap always_executed;
1233 basic_block *body = get_loop_body_in_dom_order (loop);
1235 find_exits (loop, body, may_exit, has_exit);
1236 compute_always_reached (loop, body, may_exit, always_reached);
1237 compute_always_reached (loop, body, has_exit, always_executed);
1239 find_defs (loop);
1240 find_invariants_body (loop, body, always_reached, always_executed);
1241 merge_identical_invariants ();
1243 free (body);
1246 /* Frees a list of uses USE. */
1248 static void
1249 free_use_list (struct use *use)
1251 struct use *next;
1253 for (; use; use = next)
1255 next = use->next;
1256 free (use);
1260 /* Return pressure class and number of hard registers (through *NREGS)
1261 for destination of INSN. */
1262 static enum reg_class
1263 get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
1265 rtx reg;
1266 enum reg_class pressure_class;
1267 rtx set = single_set (insn);
1269 /* Considered invariant insns have only one set. */
1270 gcc_assert (set != NULL_RTX);
1271 reg = SET_DEST (set);
1272 if (GET_CODE (reg) == SUBREG)
1273 reg = SUBREG_REG (reg);
1274 if (MEM_P (reg))
1276 *nregs = 0;
1277 pressure_class = NO_REGS;
1279 else
1281 if (! REG_P (reg))
1282 reg = NULL_RTX;
1283 if (reg == NULL_RTX)
1284 pressure_class = GENERAL_REGS;
1285 else
1287 pressure_class = reg_allocno_class (REGNO (reg));
1288 pressure_class = ira_pressure_class_translate[pressure_class];
1290 *nregs
1291 = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1293 return pressure_class;
1296 /* Calculates cost and number of registers needed for moving invariant INV
1297 out of the loop and stores them to *COST and *REGS_NEEDED. *CL will be
1298 the REG_CLASS of INV. Return
1299 -1: if INV is invalid.
1300 0: if INV and its depends_on have same reg_class
1301 1: if INV and its depends_on have different reg_classes. */
1303 static int
1304 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
1305 enum reg_class *cl)
1307 int i, acomp_cost;
1308 unsigned aregs_needed[N_REG_CLASSES];
1309 unsigned depno;
1310 struct invariant *dep;
1311 bitmap_iterator bi;
1312 int ret = 1;
1314 /* Find the representative of the class of the equivalent invariants. */
1315 inv = invariants[inv->eqto];
1317 *comp_cost = 0;
1318 if (! flag_ira_loop_pressure)
1319 regs_needed[0] = 0;
1320 else
1322 for (i = 0; i < ira_pressure_classes_num; i++)
1323 regs_needed[ira_pressure_classes[i]] = 0;
1326 if (inv->move
1327 || inv->stamp == actual_stamp)
1328 return -1;
1329 inv->stamp = actual_stamp;
1331 if (! flag_ira_loop_pressure)
1332 regs_needed[0]++;
1333 else
1335 int nregs;
1336 enum reg_class pressure_class;
1338 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1339 regs_needed[pressure_class] += nregs;
1340 *cl = pressure_class;
1341 ret = 0;
1344 if (!inv->cheap_address
1345 || inv->def->n_uses == 0
1346 || inv->def->n_addr_uses < inv->def->n_uses
1347 /* Count cost if the inv can't be propagated into address uses. */
1348 || !inv->def->can_prop_to_addr_uses)
1349 (*comp_cost) += inv->cost * inv->eqno;
1351 #ifdef STACK_REGS
1353 /* Hoisting constant pool constants into stack regs may cost more than
1354 just single register. On x87, the balance is affected both by the
1355 small number of FP registers, and by its register stack organization,
1356 that forces us to add compensation code in and around the loop to
1357 shuffle the operands to the top of stack before use, and pop them
1358 from the stack after the loop finishes.
1360 To model this effect, we increase the number of registers needed for
1361 stack registers by two: one register push, and one register pop.
1362 This usually has the effect that FP constant loads from the constant
1363 pool are not moved out of the loop.
1365 Note that this also means that dependent invariants can not be moved.
1366 However, the primary purpose of this pass is to move loop invariant
1367 address arithmetic out of loops, and address arithmetic that depends
1368 on floating point constants is unlikely to ever occur. */
1369 rtx set = single_set (inv->insn);
1370 if (set
1371 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1372 && constant_pool_constant_p (SET_SRC (set)))
1374 if (flag_ira_loop_pressure)
1375 regs_needed[ira_stack_reg_pressure_class] += 2;
1376 else
1377 regs_needed[0] += 2;
1380 #endif
1382 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1384 bool check_p;
1385 enum reg_class dep_cl = ALL_REGS;
1386 int dep_ret;
1388 dep = invariants[depno];
1390 /* If DEP is moved out of the loop, it is not a depends_on any more. */
1391 if (dep->move)
1392 continue;
1394 dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
1396 if (! flag_ira_loop_pressure)
1397 check_p = aregs_needed[0] != 0;
1398 else
1400 for (i = 0; i < ira_pressure_classes_num; i++)
1401 if (aregs_needed[ira_pressure_classes[i]] != 0)
1402 break;
1403 check_p = i < ira_pressure_classes_num;
1405 if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
1407 *cl = ALL_REGS;
1408 ret = 1;
1411 if (check_p
1412 /* We need to check always_executed, since if the original value of
1413 the invariant may be preserved, we may need to keep it in a
1414 separate register. TODO check whether the register has an
1415 use outside of the loop. */
1416 && dep->always_executed
1417 && !dep->def->uses->next)
1419 /* If this is a single use, after moving the dependency we will not
1420 need a new register. */
1421 if (! flag_ira_loop_pressure)
1422 aregs_needed[0]--;
1423 else
1425 int nregs;
1426 enum reg_class pressure_class;
1428 pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1429 aregs_needed[pressure_class] -= nregs;
1433 if (! flag_ira_loop_pressure)
1434 regs_needed[0] += aregs_needed[0];
1435 else
1437 for (i = 0; i < ira_pressure_classes_num; i++)
1438 regs_needed[ira_pressure_classes[i]]
1439 += aregs_needed[ira_pressure_classes[i]];
1441 (*comp_cost) += acomp_cost;
1443 return ret;
1446 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
1447 of registers used in the loop, NEW_REGS is the number of new variables
1448 already added due to the invariant motion. The number of registers needed
1449 for it is stored in *REGS_NEEDED. SPEED and CALL_P are flags passed
1450 through to estimate_reg_pressure_cost. */
1452 static int
1453 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1454 unsigned *new_regs, unsigned regs_used,
1455 bool speed, bool call_p)
1457 int comp_cost, size_cost;
1458 /* Workaround -Wmaybe-uninitialized false positive during
1459 profiledbootstrap by initializing it. */
1460 enum reg_class cl = NO_REGS;
1461 int ret;
1463 actual_stamp++;
1465 ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
1467 if (! flag_ira_loop_pressure)
1469 size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1470 regs_used, speed, call_p)
1471 - estimate_reg_pressure_cost (new_regs[0],
1472 regs_used, speed, call_p));
1474 else if (ret < 0)
1475 return -1;
1476 else if ((ret == 0) && (cl == NO_REGS))
1477 /* Hoist it anyway since it does not impact register pressure. */
1478 return 1;
1479 else
1481 int i;
1482 enum reg_class pressure_class;
1484 for (i = 0; i < ira_pressure_classes_num; i++)
1486 pressure_class = ira_pressure_classes[i];
1488 if (!reg_classes_intersect_p (pressure_class, cl))
1489 continue;
1491 if ((int) new_regs[pressure_class]
1492 + (int) regs_needed[pressure_class]
1493 + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1494 + IRA_LOOP_RESERVED_REGS
1495 > ira_class_hard_regs_num[pressure_class])
1496 break;
1498 if (i < ira_pressure_classes_num)
1499 /* There will be register pressure excess and we want not to
1500 make this loop invariant motion. All loop invariants with
1501 non-positive gains will be rejected in function
1502 find_invariants_to_move. Therefore we return the negative
1503 number here.
1505 One could think that this rejects also expensive loop
1506 invariant motions and this will hurt code performance.
1507 However numerous experiments with different heuristics
1508 taking invariant cost into account did not confirm this
1509 assumption. There are possible explanations for this
1510 result:
1511 o probably all expensive invariants were already moved out
1512 of the loop by PRE and gimple invariant motion pass.
1513 o expensive invariant execution will be hidden by insn
1514 scheduling or OOO processor hardware because usually such
1515 invariants have a lot of freedom to be executed
1516 out-of-order.
1517 Another reason for ignoring invariant cost vs spilling cost
1518 heuristics is also in difficulties to evaluate accurately
1519 spill cost at this stage. */
1520 return -1;
1521 else
1522 size_cost = 0;
1525 return comp_cost - size_cost;
1528 /* Finds invariant with best gain for moving. Returns the gain, stores
1529 the invariant in *BEST and number of registers needed for it to
1530 *REGS_NEEDED. REGS_USED is the number of registers used in the loop.
1531 NEW_REGS is the number of new variables already added due to invariant
1532 motion. */
1534 static int
1535 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1536 unsigned *new_regs, unsigned regs_used,
1537 bool speed, bool call_p)
1539 struct invariant *inv;
1540 int i, gain = 0, again;
1541 unsigned aregs_needed[N_REG_CLASSES], invno;
1543 FOR_EACH_VEC_ELT (invariants, invno, inv)
1545 if (inv->move)
1546 continue;
1548 /* Only consider the "representatives" of equivalent invariants. */
1549 if (inv->eqto != inv->invno)
1550 continue;
1552 again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1553 speed, call_p);
1554 if (again > gain)
1556 gain = again;
1557 *best = inv;
1558 if (! flag_ira_loop_pressure)
1559 regs_needed[0] = aregs_needed[0];
1560 else
1562 for (i = 0; i < ira_pressure_classes_num; i++)
1563 regs_needed[ira_pressure_classes[i]]
1564 = aregs_needed[ira_pressure_classes[i]];
1569 return gain;
1572 /* Marks invariant INVNO and all its dependencies for moving. */
1574 static void
1575 set_move_mark (unsigned invno, int gain)
1577 struct invariant *inv = invariants[invno];
1578 bitmap_iterator bi;
1580 /* Find the representative of the class of the equivalent invariants. */
1581 inv = invariants[inv->eqto];
1583 if (inv->move)
1584 return;
1585 inv->move = true;
1587 if (dump_file)
1589 if (gain >= 0)
1590 fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1591 invno, gain);
1592 else
1593 fprintf (dump_file, "Decided to move dependent invariant %d\n",
1594 invno);
1597 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1599 set_move_mark (invno, -1);
1603 /* Determines which invariants to move. */
1605 static void
1606 find_invariants_to_move (bool speed, bool call_p)
1608 int gain;
1609 unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1610 struct invariant *inv = NULL;
1612 if (!invariants.length ())
1613 return;
1615 if (flag_ira_loop_pressure)
1616 /* REGS_USED is actually never used when the flag is on. */
1617 regs_used = 0;
1618 else
1619 /* We do not really do a good job in estimating number of
1620 registers used; we put some initial bound here to stand for
1621 induction variables etc. that we do not detect. */
1623 unsigned int n_regs = DF_REG_SIZE (df);
1625 regs_used = 2;
1627 for (i = 0; i < n_regs; i++)
1629 if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1631 /* This is a value that is used but not changed inside loop. */
1632 regs_used++;
1637 if (! flag_ira_loop_pressure)
1638 new_regs[0] = regs_needed[0] = 0;
1639 else
1641 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1642 new_regs[ira_pressure_classes[i]] = 0;
1644 while ((gain = best_gain_for_invariant (&inv, regs_needed,
1645 new_regs, regs_used,
1646 speed, call_p)) > 0)
1648 set_move_mark (inv->invno, gain);
1649 if (! flag_ira_loop_pressure)
1650 new_regs[0] += regs_needed[0];
1651 else
1653 for (i = 0; (int) i < ira_pressure_classes_num; i++)
1654 new_regs[ira_pressure_classes[i]]
1655 += regs_needed[ira_pressure_classes[i]];
1660 /* Replace the uses, reached by the definition of invariant INV, by REG.
1662 IN_GROUP is nonzero if this is part of a group of changes that must be
1663 performed as a group. In that case, the changes will be stored. The
1664 function `apply_change_group' will validate and apply the changes. */
1666 static int
1667 replace_uses (struct invariant *inv, rtx reg, bool in_group)
1669 /* Replace the uses we know to be dominated. It saves work for copy
1670 propagation, and also it is necessary so that dependent invariants
1671 are computed right. */
1672 if (inv->def)
1674 struct use *use;
1675 for (use = inv->def->uses; use; use = use->next)
1676 validate_change (use->insn, use->pos, reg, true);
1678 /* If we aren't part of a larger group, apply the changes now. */
1679 if (!in_group)
1680 return apply_change_group ();
1683 return 1;
1686 /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
1687 the block preceding its header. */
1689 static bool
1690 can_move_invariant_reg (struct loop *loop, struct invariant *inv, rtx reg)
1692 df_ref def, use;
1693 unsigned int dest_regno, defs_in_loop_count = 0;
1694 rtx_insn *insn = inv->insn;
1695 basic_block bb = BLOCK_FOR_INSN (inv->insn);
1697 /* We ignore hard register and memory access for cost and complexity reasons.
1698 Hard register are few at this stage and expensive to consider as they
1699 require building a separate data flow. Memory access would require using
1700 df_simulate_* and can_move_insns_across functions and is more complex. */
1701 if (!REG_P (reg) || HARD_REGISTER_P (reg))
1702 return false;
1704 /* Check whether the set is always executed. We could omit this condition if
1705 we know that the register is unused outside of the loop, but it does not
1706 seem worth finding out. */
1707 if (!inv->always_executed)
1708 return false;
1710 /* Check that all uses that would be dominated by def are already dominated
1711 by it. */
1712 dest_regno = REGNO (reg);
1713 for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
1715 rtx_insn *use_insn;
1716 basic_block use_bb;
1718 use_insn = DF_REF_INSN (use);
1719 use_bb = BLOCK_FOR_INSN (use_insn);
1721 /* Ignore instruction considered for moving. */
1722 if (use_insn == insn)
1723 continue;
1725 /* Don't consider uses outside loop. */
1726 if (!flow_bb_inside_loop_p (loop, use_bb))
1727 continue;
1729 /* Don't move if a use is not dominated by def in insn. */
1730 if (use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
1731 return false;
1732 if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
1733 return false;
1736 /* Check for other defs. Any other def in the loop might reach a use
1737 currently reached by the def in insn. */
1738 for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
1740 basic_block def_bb = DF_REF_BB (def);
1742 /* Defs in exit block cannot reach a use they weren't already. */
1743 if (single_succ_p (def_bb))
1745 basic_block def_bb_succ;
1747 def_bb_succ = single_succ (def_bb);
1748 if (!flow_bb_inside_loop_p (loop, def_bb_succ))
1749 continue;
1752 if (++defs_in_loop_count > 1)
1753 return false;
1756 return true;
1759 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1760 otherwise. */
1762 static bool
1763 move_invariant_reg (struct loop *loop, unsigned invno)
1765 struct invariant *inv = invariants[invno];
1766 struct invariant *repr = invariants[inv->eqto];
1767 unsigned i;
1768 basic_block preheader = loop_preheader_edge (loop)->src;
1769 rtx reg, set, dest, note;
1770 bitmap_iterator bi;
1771 int regno = -1;
1773 if (inv->reg)
1774 return true;
1775 if (!repr->move)
1776 return false;
1778 /* If this is a representative of the class of equivalent invariants,
1779 really move the invariant. Otherwise just replace its use with
1780 the register used for the representative. */
1781 if (inv == repr)
1783 if (inv->depends_on)
1785 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1787 if (!move_invariant_reg (loop, i))
1788 goto fail;
1792 /* If possible, just move the set out of the loop. Otherwise, we
1793 need to create a temporary register. */
1794 set = single_set (inv->insn);
1795 reg = dest = SET_DEST (set);
1796 if (GET_CODE (reg) == SUBREG)
1797 reg = SUBREG_REG (reg);
1798 if (REG_P (reg))
1799 regno = REGNO (reg);
1801 if (!can_move_invariant_reg (loop, inv, dest))
1803 reg = gen_reg_rtx_and_attrs (dest);
1805 /* Try replacing the destination by a new pseudoregister. */
1806 validate_change (inv->insn, &SET_DEST (set), reg, true);
1808 /* As well as all the dominated uses. */
1809 replace_uses (inv, reg, true);
1811 /* And validate all the changes. */
1812 if (!apply_change_group ())
1813 goto fail;
1815 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1817 else if (dump_file)
1818 fprintf (dump_file, "Invariant %d moved without introducing a new "
1819 "temporary register\n", invno);
1820 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1821 df_recompute_luids (preheader);
1823 /* If there is a REG_EQUAL note on the insn we just moved, and the
1824 insn is in a basic block that is not always executed or the note
1825 contains something for which we don't know the invariant status,
1826 the note may no longer be valid after we move the insn. Note that
1827 uses in REG_EQUAL notes are taken into account in the computation
1828 of invariants, so it is safe to retain the note even if it contains
1829 register references for which we know the invariant status. */
1830 if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1831 && (!inv->always_executed
1832 || !check_maybe_invariant (XEXP (note, 0))))
1833 remove_note (inv->insn, note);
1835 else
1837 if (!move_invariant_reg (loop, repr->invno))
1838 goto fail;
1839 reg = repr->reg;
1840 regno = repr->orig_regno;
1841 if (!replace_uses (inv, reg, false))
1842 goto fail;
1843 set = single_set (inv->insn);
1844 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1845 delete_insn (inv->insn);
1848 inv->reg = reg;
1849 inv->orig_regno = regno;
1851 return true;
1853 fail:
1854 /* If we failed, clear move flag, so that we do not try to move inv
1855 again. */
1856 if (dump_file)
1857 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1858 inv->move = false;
1859 inv->reg = NULL_RTX;
1860 inv->orig_regno = -1;
1862 return false;
1865 /* Move selected invariant out of the LOOP. Newly created regs are marked
1866 in TEMPORARY_REGS. */
1868 static void
1869 move_invariants (struct loop *loop)
1871 struct invariant *inv;
1872 unsigned i;
1874 FOR_EACH_VEC_ELT (invariants, i, inv)
1875 move_invariant_reg (loop, i);
1876 if (flag_ira_loop_pressure && resize_reg_info ())
1878 FOR_EACH_VEC_ELT (invariants, i, inv)
1879 if (inv->reg != NULL_RTX)
1881 if (inv->orig_regno >= 0)
1882 setup_reg_classes (REGNO (inv->reg),
1883 reg_preferred_class (inv->orig_regno),
1884 reg_alternate_class (inv->orig_regno),
1885 reg_allocno_class (inv->orig_regno));
1886 else
1887 setup_reg_classes (REGNO (inv->reg),
1888 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1893 /* Initializes invariant motion data. */
1895 static void
1896 init_inv_motion_data (void)
1898 actual_stamp = 1;
1900 invariants.create (100);
1903 /* Frees the data allocated by invariant motion. */
1905 static void
1906 free_inv_motion_data (void)
1908 unsigned i;
1909 struct def *def;
1910 struct invariant *inv;
1912 check_invariant_table_size ();
1913 for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1915 inv = invariant_table[i];
1916 if (inv)
1918 def = inv->def;
1919 gcc_assert (def != NULL);
1921 free_use_list (def->uses);
1922 free (def);
1923 invariant_table[i] = NULL;
1927 FOR_EACH_VEC_ELT (invariants, i, inv)
1929 BITMAP_FREE (inv->depends_on);
1930 free (inv);
1932 invariants.release ();
1935 /* Move the invariants out of the LOOP. */
1937 static void
1938 move_single_loop_invariants (struct loop *loop)
1940 init_inv_motion_data ();
1942 find_invariants (loop);
1943 find_invariants_to_move (optimize_loop_for_speed_p (loop),
1944 LOOP_DATA (loop)->has_call);
1945 move_invariants (loop);
1947 free_inv_motion_data ();
1950 /* Releases the auxiliary data for LOOP. */
1952 static void
1953 free_loop_data (struct loop *loop)
1955 struct loop_data *data = LOOP_DATA (loop);
1956 if (!data)
1957 return;
1959 bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1960 bitmap_clear (&LOOP_DATA (loop)->regs_live);
1961 free (data);
1962 loop->aux = NULL;
1967 /* Registers currently living. */
1968 static bitmap_head curr_regs_live;
1970 /* Current reg pressure for each pressure class. */
1971 static int curr_reg_pressure[N_REG_CLASSES];
1973 /* Record all regs that are set in any one insn. Communication from
1974 mark_reg_{store,clobber} and global_conflicts. Asm can refer to
1975 all hard-registers. */
1976 static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1977 ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1978 /* Number of regs stored in the previous array. */
1979 static int n_regs_set;
1981 /* Return pressure class and number of needed hard registers (through
1982 *NREGS) of register REGNO. */
1983 static enum reg_class
1984 get_regno_pressure_class (int regno, int *nregs)
1986 if (regno >= FIRST_PSEUDO_REGISTER)
1988 enum reg_class pressure_class;
1990 pressure_class = reg_allocno_class (regno);
1991 pressure_class = ira_pressure_class_translate[pressure_class];
1992 *nregs
1993 = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1994 return pressure_class;
1996 else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1997 && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1999 *nregs = 1;
2000 return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
2002 else
2004 *nregs = 0;
2005 return NO_REGS;
2009 /* Increase (if INCR_P) or decrease current register pressure for
2010 register REGNO. */
2011 static void
2012 change_pressure (int regno, bool incr_p)
2014 int nregs;
2015 enum reg_class pressure_class;
2017 pressure_class = get_regno_pressure_class (regno, &nregs);
2018 if (! incr_p)
2019 curr_reg_pressure[pressure_class] -= nregs;
2020 else
2022 curr_reg_pressure[pressure_class] += nregs;
2023 if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2024 < curr_reg_pressure[pressure_class])
2025 LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
2026 = curr_reg_pressure[pressure_class];
2030 /* Mark REGNO birth. */
2031 static void
2032 mark_regno_live (int regno)
2034 struct loop *loop;
2036 for (loop = curr_loop;
2037 loop != current_loops->tree_root;
2038 loop = loop_outer (loop))
2039 bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
2040 if (!bitmap_set_bit (&curr_regs_live, regno))
2041 return;
2042 change_pressure (regno, true);
2045 /* Mark REGNO death. */
2046 static void
2047 mark_regno_death (int regno)
2049 if (! bitmap_clear_bit (&curr_regs_live, regno))
2050 return;
2051 change_pressure (regno, false);
2054 /* Mark setting register REG. */
2055 static void
2056 mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
2057 void *data ATTRIBUTE_UNUSED)
2059 if (GET_CODE (reg) == SUBREG)
2060 reg = SUBREG_REG (reg);
2062 if (! REG_P (reg))
2063 return;
2065 regs_set[n_regs_set++] = reg;
2067 unsigned int end_regno = END_REGNO (reg);
2068 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2069 mark_regno_live (regno);
2072 /* Mark clobbering register REG. */
2073 static void
2074 mark_reg_clobber (rtx reg, const_rtx setter, void *data)
2076 if (GET_CODE (setter) == CLOBBER)
2077 mark_reg_store (reg, setter, data);
2080 /* Mark register REG death. */
2081 static void
2082 mark_reg_death (rtx reg)
2084 unsigned int end_regno = END_REGNO (reg);
2085 for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
2086 mark_regno_death (regno);
2089 /* Mark occurrence of registers in X for the current loop. */
2090 static void
2091 mark_ref_regs (rtx x)
2093 RTX_CODE code;
2094 int i;
2095 const char *fmt;
2097 if (!x)
2098 return;
2100 code = GET_CODE (x);
2101 if (code == REG)
2103 struct loop *loop;
2105 for (loop = curr_loop;
2106 loop != current_loops->tree_root;
2107 loop = loop_outer (loop))
2108 bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
2109 return;
2112 fmt = GET_RTX_FORMAT (code);
2113 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2114 if (fmt[i] == 'e')
2115 mark_ref_regs (XEXP (x, i));
2116 else if (fmt[i] == 'E')
2118 int j;
2120 for (j = 0; j < XVECLEN (x, i); j++)
2121 mark_ref_regs (XVECEXP (x, i, j));
2125 /* Calculate register pressure in the loops. */
2126 static void
2127 calculate_loop_reg_pressure (void)
2129 int i;
2130 unsigned int j;
2131 bitmap_iterator bi;
2132 basic_block bb;
2133 rtx_insn *insn;
2134 rtx link;
2135 struct loop *loop, *parent;
2137 FOR_EACH_LOOP (loop, 0)
2138 if (loop->aux == NULL)
2140 loop->aux = xcalloc (1, sizeof (struct loop_data));
2141 bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
2142 bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
2144 ira_setup_eliminable_regset ();
2145 bitmap_initialize (&curr_regs_live, &reg_obstack);
2146 FOR_EACH_BB_FN (bb, cfun)
2148 curr_loop = bb->loop_father;
2149 if (curr_loop == current_loops->tree_root)
2150 continue;
2152 for (loop = curr_loop;
2153 loop != current_loops->tree_root;
2154 loop = loop_outer (loop))
2155 bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
2157 bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
2158 for (i = 0; i < ira_pressure_classes_num; i++)
2159 curr_reg_pressure[ira_pressure_classes[i]] = 0;
2160 EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
2161 change_pressure (j, true);
2163 FOR_BB_INSNS (bb, insn)
2165 if (! NONDEBUG_INSN_P (insn))
2166 continue;
2168 mark_ref_regs (PATTERN (insn));
2169 n_regs_set = 0;
2170 note_stores (PATTERN (insn), mark_reg_clobber, NULL);
2172 /* Mark any registers dead after INSN as dead now. */
2174 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2175 if (REG_NOTE_KIND (link) == REG_DEAD)
2176 mark_reg_death (XEXP (link, 0));
2178 /* Mark any registers set in INSN as live,
2179 and mark them as conflicting with all other live regs.
2180 Clobbers are processed again, so they conflict with
2181 the registers that are set. */
2183 note_stores (PATTERN (insn), mark_reg_store, NULL);
2185 if (AUTO_INC_DEC)
2186 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2187 if (REG_NOTE_KIND (link) == REG_INC)
2188 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
2190 while (n_regs_set-- > 0)
2192 rtx note = find_regno_note (insn, REG_UNUSED,
2193 REGNO (regs_set[n_regs_set]));
2194 if (! note)
2195 continue;
2197 mark_reg_death (XEXP (note, 0));
2201 bitmap_clear (&curr_regs_live);
2202 if (flag_ira_region == IRA_REGION_MIXED
2203 || flag_ira_region == IRA_REGION_ALL)
2204 FOR_EACH_LOOP (loop, 0)
2206 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2207 if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
2209 enum reg_class pressure_class;
2210 int nregs;
2212 pressure_class = get_regno_pressure_class (j, &nregs);
2213 LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
2216 if (dump_file == NULL)
2217 return;
2218 FOR_EACH_LOOP (loop, 0)
2220 parent = loop_outer (loop);
2221 fprintf (dump_file, "\n Loop %d (parent %d, header bb%d, depth %d)\n",
2222 loop->num, (parent == NULL ? -1 : parent->num),
2223 loop->header->index, loop_depth (loop));
2224 fprintf (dump_file, "\n ref. regnos:");
2225 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
2226 fprintf (dump_file, " %d", j);
2227 fprintf (dump_file, "\n live regnos:");
2228 EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
2229 fprintf (dump_file, " %d", j);
2230 fprintf (dump_file, "\n Pressure:");
2231 for (i = 0; (int) i < ira_pressure_classes_num; i++)
2233 enum reg_class pressure_class;
2235 pressure_class = ira_pressure_classes[i];
2236 if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
2237 continue;
2238 fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
2239 LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
2241 fprintf (dump_file, "\n");
2247 /* Move the invariants out of the loops. */
2249 void
2250 move_loop_invariants (void)
2252 struct loop *loop;
2254 if (flag_ira_loop_pressure)
2256 df_analyze ();
2257 regstat_init_n_sets_and_refs ();
2258 ira_set_pseudo_classes (true, dump_file);
2259 calculate_loop_reg_pressure ();
2260 regstat_free_n_sets_and_refs ();
2262 df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
2263 /* Process the loops, innermost first. */
2264 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
2266 curr_loop = loop;
2267 /* move_single_loop_invariants for very large loops
2268 is time consuming and might need a lot of memory. */
2269 if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
2270 move_single_loop_invariants (loop);
2273 FOR_EACH_LOOP (loop, 0)
2275 free_loop_data (loop);
2278 if (flag_ira_loop_pressure)
2279 /* There is no sense to keep this info because it was most
2280 probably outdated by subsequent passes. */
2281 free_reg_info ();
2282 free (invariant_table);
2283 invariant_table = NULL;
2284 invariant_table_size = 0;
2286 checking_verify_flow_info ();