2006-08-07 Andrew John Hughes <gnu_andrew@member.fsf.org>
[official-gcc.git] / gcc / loop-invariant.c
blob026af40822ceee6c83fcfcd9c549d40fcdfab03b
1 /* RTL-level loop invariant motion.
2 Copyright (C) 2004, 2005, 2006 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19 02110-1301, USA. */
21 /* This implements the loop invariant motion pass. It is very simple
22 (no calls, libcalls, etc.). This should be sufficient to cleanup things
23 like address arithmetics -- other more complicated invariants should be
24 eliminated on tree level either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
26 We proceed loop by loop -- it is simpler than trying to handle things
27 globally and should not lose much. First we inspect all sets inside loop
28 and create a dependency graph on insns (saying "to move this insn, you must
29 also move the following insns").
31 We then need to determine what to move. We estimate the number of registers
32 used and move as many invariants as possible while we still have enough free
33 registers. We prefer the expensive invariants.
35 Then we move the selected invariants out of the loop, creating a new
36 temporaries for them if necessary. */
38 #include "config.h"
39 #include "system.h"
40 #include "coretypes.h"
41 #include "tm.h"
42 #include "rtl.h"
43 #include "tm_p.h"
44 #include "hard-reg-set.h"
45 #include "obstack.h"
46 #include "basic-block.h"
47 #include "cfgloop.h"
48 #include "expr.h"
49 #include "recog.h"
50 #include "output.h"
51 #include "function.h"
52 #include "flags.h"
53 #include "df.h"
54 #include "hashtab.h"
55 #include "except.h"
57 /* The data stored for the loop. */
59 struct loop_data
61 struct loop *outermost_exit; /* The outermost exit of the loop. */
62 bool has_call; /* True if the loop contains a call. */
65 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
67 /* The description of an use. */
69 struct use
71 rtx *pos; /* Position of the use. */
72 rtx insn; /* The insn in that the use occurs. */
74 struct use *next; /* Next use in the list. */
77 /* The description of a def. */
79 struct def
81 struct use *uses; /* The list of uses that are uniquely reached
82 by it. */
83 unsigned n_uses; /* Number of such uses. */
84 unsigned invno; /* The corresponding invariant. */
87 /* The data stored for each invariant. */
89 struct invariant
91 /* The number of the invariant. */
92 unsigned invno;
94 /* The number of the invariant with the same value. */
95 unsigned eqto;
97 /* If we moved the invariant out of the loop, the register that contains its
98 value. */
99 rtx reg;
101 /* The definition of the invariant. */
102 struct def *def;
104 /* The insn in that it is defined. */
105 rtx insn;
107 /* Whether it is always executed. */
108 bool always_executed;
110 /* Whether to move the invariant. */
111 bool move;
113 /* Cost of the invariant. */
114 unsigned cost;
116 /* The invariants it depends on. */
117 bitmap depends_on;
119 /* Used for detecting already visited invariants during determining
120 costs of movements. */
121 unsigned stamp;
124 /* Entry for hash table of invariant expressions. */
126 struct invariant_expr_entry
128 /* The invariant. */
129 struct invariant *inv;
131 /* Its value. */
132 rtx expr;
134 /* Its mode. */
135 enum machine_mode mode;
137 /* Its hash. */
138 hashval_t hash;
141 /* The actual stamp for marking already visited invariants during determining
142 costs of movements. */
144 static unsigned actual_stamp;
146 typedef struct invariant *invariant_p;
148 DEF_VEC_P(invariant_p);
149 DEF_VEC_ALLOC_P(invariant_p, heap);
151 /* The invariants. */
153 static VEC(invariant_p,heap) *invariants;
155 /* The dataflow object. */
157 static struct df *df = NULL;
159 /* Test for possibility of invariantness of X. */
161 static bool
162 check_maybe_invariant (rtx x)
164 enum rtx_code code = GET_CODE (x);
165 int i, j;
166 const char *fmt;
168 switch (code)
170 case CONST_INT:
171 case CONST_DOUBLE:
172 case SYMBOL_REF:
173 case CONST:
174 case LABEL_REF:
175 return true;
177 case PC:
178 case CC0:
179 case UNSPEC_VOLATILE:
180 case CALL:
181 return false;
183 case REG:
184 return true;
186 case MEM:
187 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
188 It should not be hard, and might be faster than "elsewhere". */
190 /* Just handle the most trivial case where we load from an unchanging
191 location (most importantly, pic tables). */
192 if (MEM_READONLY_P (x))
193 break;
195 return false;
197 case ASM_OPERANDS:
198 /* Don't mess with insns declared volatile. */
199 if (MEM_VOLATILE_P (x))
200 return false;
201 break;
203 default:
204 break;
207 fmt = GET_RTX_FORMAT (code);
208 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
210 if (fmt[i] == 'e')
212 if (!check_maybe_invariant (XEXP (x, i)))
213 return false;
215 else if (fmt[i] == 'E')
217 for (j = 0; j < XVECLEN (x, i); j++)
218 if (!check_maybe_invariant (XVECEXP (x, i, j)))
219 return false;
223 return true;
226 /* Returns the invariant definition for USE, or NULL if USE is not
227 invariant. */
229 static struct invariant *
230 invariant_for_use (struct df_ref *use)
232 struct df_link *defs;
233 struct df_ref *def;
234 basic_block bb = BLOCK_FOR_INSN (use->insn), def_bb;
236 if (use->flags & DF_REF_READ_WRITE)
237 return NULL;
239 defs = DF_REF_CHAIN (use);
240 if (!defs || defs->next)
241 return NULL;
242 def = defs->ref;
243 if (!DF_REF_DATA (def))
244 return NULL;
246 def_bb = DF_REF_BB (def);
247 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
248 return NULL;
249 return DF_REF_DATA (def);
252 /* Computes hash value for invariant expression X in INSN. */
254 static hashval_t
255 hash_invariant_expr_1 (rtx insn, rtx x)
257 enum rtx_code code = GET_CODE (x);
258 int i, j;
259 const char *fmt;
260 hashval_t val = code;
261 int do_not_record_p;
262 struct df_ref *use;
263 struct invariant *inv;
265 switch (code)
267 case CONST_INT:
268 case CONST_DOUBLE:
269 case SYMBOL_REF:
270 case CONST:
271 case LABEL_REF:
272 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
274 case REG:
275 use = df_find_use (df, insn, x);
276 if (!use)
277 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
278 inv = invariant_for_use (use);
279 if (!inv)
280 return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
282 gcc_assert (inv->eqto != ~0u);
283 return inv->eqto;
285 default:
286 break;
289 fmt = GET_RTX_FORMAT (code);
290 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
292 if (fmt[i] == 'e')
293 val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
294 else if (fmt[i] == 'E')
296 for (j = 0; j < XVECLEN (x, i); j++)
297 val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
299 else if (fmt[i] == 'i' || fmt[i] == 'n')
300 val ^= XINT (x, i);
303 return val;
306 /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
307 and INSN2 have always the same value. */
309 static bool
310 invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
312 enum rtx_code code = GET_CODE (e1);
313 int i, j;
314 const char *fmt;
315 struct df_ref *use1, *use2;
316 struct invariant *inv1 = NULL, *inv2 = NULL;
317 rtx sub1, sub2;
319 /* If mode of only one of the operands is VOIDmode, it is not equivalent to
320 the other one. If both are VOIDmode, we rely on the caller of this
321 function to verify that their modes are the same. */
322 if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
323 return false;
325 switch (code)
327 case CONST_INT:
328 case CONST_DOUBLE:
329 case SYMBOL_REF:
330 case CONST:
331 case LABEL_REF:
332 return rtx_equal_p (e1, e2);
334 case REG:
335 use1 = df_find_use (df, insn1, e1);
336 use2 = df_find_use (df, insn2, e2);
337 if (use1)
338 inv1 = invariant_for_use (use1);
339 if (use2)
340 inv2 = invariant_for_use (use2);
342 if (!inv1 && !inv2)
343 return rtx_equal_p (e1, e2);
345 if (!inv1 || !inv2)
346 return false;
348 gcc_assert (inv1->eqto != ~0u);
349 gcc_assert (inv2->eqto != ~0u);
350 return inv1->eqto == inv2->eqto;
352 default:
353 break;
356 fmt = GET_RTX_FORMAT (code);
357 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
359 if (fmt[i] == 'e')
361 sub1 = XEXP (e1, i);
362 sub2 = XEXP (e2, i);
364 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
365 return false;
368 else if (fmt[i] == 'E')
370 if (XVECLEN (e1, i) != XVECLEN (e2, i))
371 return false;
373 for (j = 0; j < XVECLEN (e1, i); j++)
375 sub1 = XVECEXP (e1, i, j);
376 sub2 = XVECEXP (e2, i, j);
378 if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
379 return false;
382 else if (fmt[i] == 'i' || fmt[i] == 'n')
384 if (XINT (e1, i) != XINT (e2, i))
385 return false;
387 /* Unhandled type of subexpression, we fail conservatively. */
388 else
389 return false;
392 return true;
395 /* Returns hash value for invariant expression entry E. */
397 static hashval_t
398 hash_invariant_expr (const void *e)
400 const struct invariant_expr_entry *entry = e;
402 return entry->hash;
405 /* Compares invariant expression entries E1 and E2. */
407 static int
408 eq_invariant_expr (const void *e1, const void *e2)
410 const struct invariant_expr_entry *entry1 = e1;
411 const struct invariant_expr_entry *entry2 = e2;
413 if (entry1->mode != entry2->mode)
414 return 0;
416 return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
417 entry2->inv->insn, entry2->expr);
420 /* Checks whether invariant with value EXPR in machine mode MODE is
421 recorded in EQ. If this is the case, return the invariant. Otherwise
422 insert INV to the table for this expression and return INV. */
424 static struct invariant *
425 find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
426 struct invariant *inv)
428 hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
429 struct invariant_expr_entry *entry;
430 struct invariant_expr_entry pentry;
431 PTR *slot;
433 pentry.expr = expr;
434 pentry.inv = inv;
435 pentry.mode = mode;
436 slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
437 entry = *slot;
439 if (entry)
440 return entry->inv;
442 entry = XNEW (struct invariant_expr_entry);
443 entry->inv = inv;
444 entry->expr = expr;
445 entry->mode = mode;
446 entry->hash = hash;
447 *slot = entry;
449 return inv;
452 /* Finds invariants identical to INV and records the equivalence. EQ is the
453 hash table of the invariants. */
455 static void
456 find_identical_invariants (htab_t eq, struct invariant *inv)
458 unsigned depno;
459 bitmap_iterator bi;
460 struct invariant *dep;
461 rtx expr, set;
462 enum machine_mode mode;
464 if (inv->eqto != ~0u)
465 return;
467 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
469 dep = VEC_index (invariant_p, invariants, depno);
470 find_identical_invariants (eq, dep);
473 set = single_set (inv->insn);
474 expr = SET_SRC (set);
475 mode = GET_MODE (expr);
476 if (mode == VOIDmode)
477 mode = GET_MODE (SET_DEST (set));
478 inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
480 if (dump_file && inv->eqto != inv->invno)
481 fprintf (dump_file,
482 "Invariant %d is equivalent to invariant %d.\n",
483 inv->invno, inv->eqto);
486 /* Find invariants with the same value and record the equivalences. */
488 static void
489 merge_identical_invariants (void)
491 unsigned i;
492 struct invariant *inv;
493 htab_t eq = htab_create (VEC_length (invariant_p, invariants),
494 hash_invariant_expr, eq_invariant_expr, free);
496 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
497 find_identical_invariants (eq, inv);
499 htab_delete (eq);
502 /* Determines the basic blocks inside LOOP that are always executed and
503 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
504 basic blocks that may either exit the loop, or contain the call that
505 does not have to return. BODY is body of the loop obtained by
506 get_loop_body_in_dom_order. */
508 static void
509 compute_always_reached (struct loop *loop, basic_block *body,
510 bitmap may_exit, bitmap always_reached)
512 unsigned i;
514 for (i = 0; i < loop->num_nodes; i++)
516 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
517 bitmap_set_bit (always_reached, i);
519 if (bitmap_bit_p (may_exit, i))
520 return;
524 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
525 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
526 additionally mark blocks that may exit due to a call. */
528 static void
529 find_exits (struct loop *loop, basic_block *body,
530 bitmap may_exit, bitmap has_exit)
532 unsigned i;
533 edge_iterator ei;
534 edge e;
535 struct loop *outermost_exit = loop, *aexit;
536 bool has_call = false;
537 rtx insn;
539 for (i = 0; i < loop->num_nodes; i++)
541 if (body[i]->loop_father == loop)
543 FOR_BB_INSNS (body[i], insn)
545 if (CALL_P (insn)
546 && !CONST_OR_PURE_CALL_P (insn))
548 has_call = true;
549 bitmap_set_bit (may_exit, i);
550 break;
554 FOR_EACH_EDGE (e, ei, body[i]->succs)
556 if (flow_bb_inside_loop_p (loop, e->dest))
557 continue;
559 bitmap_set_bit (may_exit, i);
560 bitmap_set_bit (has_exit, i);
561 outermost_exit = find_common_loop (outermost_exit,
562 e->dest->loop_father);
564 continue;
567 /* Use the data stored for the subloop to decide whether we may exit
568 through it. It is sufficient to do this for header of the loop,
569 as other basic blocks inside it must be dominated by it. */
570 if (body[i]->loop_father->header != body[i])
571 continue;
573 if (LOOP_DATA (body[i]->loop_father)->has_call)
575 has_call = true;
576 bitmap_set_bit (may_exit, i);
578 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
579 if (aexit != loop)
581 bitmap_set_bit (may_exit, i);
582 bitmap_set_bit (has_exit, i);
584 if (flow_loop_nested_p (aexit, outermost_exit))
585 outermost_exit = aexit;
589 loop->aux = xcalloc (1, sizeof (struct loop_data));
590 LOOP_DATA (loop)->outermost_exit = outermost_exit;
591 LOOP_DATA (loop)->has_call = has_call;
594 /* Check whether we may assign a value to X from a register. */
596 static bool
597 may_assign_reg_p (rtx x)
599 return (GET_MODE (x) != VOIDmode
600 && GET_MODE (x) != BLKmode
601 && can_copy_p (GET_MODE (x))
602 && (!REG_P (x)
603 || !HARD_REGISTER_P (x)
604 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
607 /* Finds definitions that may correspond to invariants in LOOP with body
608 BODY. */
610 static void
611 find_defs (struct loop *loop, basic_block *body)
613 unsigned i;
614 bitmap blocks = BITMAP_ALLOC (NULL);
616 for (i = 0; i < loop->num_nodes; i++)
617 bitmap_set_bit (blocks, body[i]->index);
619 df_set_blocks (df, blocks);
620 df_analyze (df);
621 BITMAP_FREE (blocks);
624 /* Creates a new invariant for definition DEF in INSN, depending on invariants
625 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
626 unless the program ends due to a function call. The newly created invariant
627 is returned. */
629 static struct invariant *
630 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
631 bool always_executed)
633 struct invariant *inv = XNEW (struct invariant);
634 rtx set = single_set (insn);
636 inv->def = def;
637 inv->always_executed = always_executed;
638 inv->depends_on = depends_on;
640 /* If the set is simple, usually by moving it we move the whole store out of
641 the loop. Otherwise we save only cost of the computation. */
642 if (def)
643 inv->cost = rtx_cost (set, SET);
644 else
645 inv->cost = rtx_cost (SET_SRC (set), SET);
647 inv->move = false;
648 inv->reg = NULL_RTX;
649 inv->stamp = 0;
650 inv->insn = insn;
652 inv->invno = VEC_length (invariant_p, invariants);
653 inv->eqto = ~0u;
654 if (def)
655 def->invno = inv->invno;
656 VEC_safe_push (invariant_p, heap, invariants, inv);
658 if (dump_file)
660 fprintf (dump_file,
661 "Set in insn %d is invariant (%d), cost %d, depends on ",
662 INSN_UID (insn), inv->invno, inv->cost);
663 dump_bitmap (dump_file, inv->depends_on);
666 return inv;
669 /* Record USE at DEF. */
671 static void
672 record_use (struct def *def, rtx *use, rtx insn)
674 struct use *u = XNEW (struct use);
676 if (GET_CODE (*use) == SUBREG)
677 use = &SUBREG_REG (*use);
678 gcc_assert (REG_P (*use));
680 u->pos = use;
681 u->insn = insn;
682 u->next = def->uses;
683 def->uses = u;
684 def->n_uses++;
687 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
688 bitmap. Returns true if all dependencies of INSN are known to be
689 loop invariants, false otherwise. */
691 static bool
692 check_dependencies (rtx insn, bitmap depends_on)
694 struct df_link *defs;
695 struct df_ref *use, *def;
696 basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
697 struct def *def_data;
698 struct invariant *inv;
700 for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
702 if (use->flags & DF_REF_READ_WRITE)
703 return false;
705 defs = DF_REF_CHAIN (use);
706 if (!defs)
707 continue;
709 if (defs->next)
710 return false;
712 def = defs->ref;
713 inv = DF_REF_DATA (def);
714 if (!inv)
715 return false;
717 def_data = inv->def;
718 gcc_assert (def_data != NULL);
720 def_bb = DF_REF_BB (def);
721 /* Note that in case bb == def_bb, we know that the definition dominates
722 insn, because def has DF_REF_DATA defined and we process the insns
723 in the basic block bb sequentially. */
724 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
725 return false;
727 bitmap_set_bit (depends_on, def_data->invno);
730 return true;
733 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
734 executed. ALWAYS_EXECUTED is true if the insn is always executed,
735 unless the program ends due to a function call. */
737 static void
738 find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
740 struct df_ref *ref;
741 struct def *def;
742 bitmap depends_on;
743 rtx set, dest;
744 bool simple = true;
745 struct invariant *inv;
747 /* Until we get rid of LIBCALLS. */
748 if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
749 || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
750 || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
751 return;
753 #ifdef HAVE_cc0
754 /* We can't move a CC0 setter without the user. */
755 if (sets_cc0_p (insn))
756 return;
757 #endif
759 set = single_set (insn);
760 if (!set)
761 return;
762 dest = SET_DEST (set);
764 if (!REG_P (dest)
765 || HARD_REGISTER_P (dest))
766 simple = false;
768 if (!may_assign_reg_p (SET_DEST (set))
769 || !check_maybe_invariant (SET_SRC (set)))
770 return;
772 /* If the insn can throw exception, we cannot move it at all without changing
773 cfg. */
774 if (can_throw_internal (insn))
775 return;
777 /* We cannot make trapping insn executed, unless it was executed before. */
778 if (may_trap_after_code_motion_p (PATTERN (insn)) && !always_reached)
779 return;
781 depends_on = BITMAP_ALLOC (NULL);
782 if (!check_dependencies (insn, depends_on))
784 BITMAP_FREE (depends_on);
785 return;
788 if (simple)
789 def = XCNEW (struct def);
790 else
791 def = NULL;
793 inv = create_new_invariant (def, insn, depends_on, always_executed);
795 if (simple)
797 ref = df_find_def (df, insn, dest);
798 DF_REF_DATA (ref) = inv;
802 /* Record registers used in INSN that have a unique invariant definition. */
804 static void
805 record_uses (rtx insn)
807 struct df_ref *use;
808 struct invariant *inv;
810 for (use = DF_INSN_GET (df, insn)->uses; use; use = use->next_ref)
812 inv = invariant_for_use (use);
813 if (inv)
814 record_use (inv->def, DF_REF_LOC (use), DF_REF_INSN (use));
818 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
819 executed. ALWAYS_EXECUTED is true if the insn is always executed,
820 unless the program ends due to a function call. */
822 static void
823 find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
825 find_invariant_insn (insn, always_reached, always_executed);
826 record_uses (insn);
829 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
830 basic block is always executed. ALWAYS_EXECUTED is true if the basic
831 block is always executed, unless the program ends due to a function
832 call. */
834 static void
835 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
837 rtx insn;
839 FOR_BB_INSNS (bb, insn)
841 if (!INSN_P (insn))
842 continue;
844 find_invariants_insn (insn, always_reached, always_executed);
846 if (always_reached
847 && CALL_P (insn)
848 && !CONST_OR_PURE_CALL_P (insn))
849 always_reached = false;
853 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
854 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
855 bitmap of basic blocks in BODY that are always executed unless the program
856 ends due to a function call. */
858 static void
859 find_invariants_body (struct loop *loop, basic_block *body,
860 bitmap always_reached, bitmap always_executed)
862 unsigned i;
864 for (i = 0; i < loop->num_nodes; i++)
865 find_invariants_bb (body[i],
866 bitmap_bit_p (always_reached, i),
867 bitmap_bit_p (always_executed, i));
870 /* Finds invariants in LOOP. */
872 static void
873 find_invariants (struct loop *loop)
875 bitmap may_exit = BITMAP_ALLOC (NULL);
876 bitmap always_reached = BITMAP_ALLOC (NULL);
877 bitmap has_exit = BITMAP_ALLOC (NULL);
878 bitmap always_executed = BITMAP_ALLOC (NULL);
879 basic_block *body = get_loop_body_in_dom_order (loop);
881 find_exits (loop, body, may_exit, has_exit);
882 compute_always_reached (loop, body, may_exit, always_reached);
883 compute_always_reached (loop, body, has_exit, always_executed);
885 find_defs (loop, body);
886 find_invariants_body (loop, body, always_reached, always_executed);
887 merge_identical_invariants ();
889 BITMAP_FREE (always_reached);
890 BITMAP_FREE (always_executed);
891 BITMAP_FREE (may_exit);
892 BITMAP_FREE (has_exit);
893 free (body);
896 /* Frees a list of uses USE. */
898 static void
899 free_use_list (struct use *use)
901 struct use *next;
903 for (; use; use = next)
905 next = use->next;
906 free (use);
910 /* Calculates cost and number of registers needed for moving invariant INV
911 out of the loop and stores them to *COST and *REGS_NEEDED. */
913 static void
914 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
916 int acomp_cost;
917 unsigned aregs_needed;
918 unsigned depno;
919 struct invariant *dep;
920 bitmap_iterator bi;
922 /* Find the representative of the class of the equivalent invariants. */
923 inv = VEC_index (invariant_p, invariants, inv->eqto);
925 *comp_cost = 0;
926 *regs_needed = 0;
927 if (inv->move
928 || inv->stamp == actual_stamp)
929 return;
930 inv->stamp = actual_stamp;
932 (*regs_needed)++;
933 (*comp_cost) += inv->cost;
935 #ifdef STACK_REGS
937 /* Hoisting constant pool constants into stack regs may cost more than
938 just single register. On x87, the balance is affected both by the
939 small number of FP registers, and by its register stack organization,
940 that forces us to add compensation code in and around the loop to
941 shuffle the operands to the top of stack before use, and pop them
942 from the stack after the loop finishes.
944 To model this effect, we increase the number of registers needed for
945 stack registers by two: one register push, and one register pop.
946 This usually has the effect that FP constant loads from the constant
947 pool are not moved out of the loop.
949 Note that this also means that dependent invariants can not be moved.
950 However, the primary purpose of this pass is to move loop invariant
951 address arithmetic out of loops, and address arithmetic that depends
952 on floating point constants is unlikely to ever occur. */
953 rtx set = single_set (inv->insn);
954 if (set
955 && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
956 && constant_pool_constant_p (SET_SRC (set)))
957 (*regs_needed) += 2;
959 #endif
961 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
963 dep = VEC_index (invariant_p, invariants, depno);
965 get_inv_cost (dep, &acomp_cost, &aregs_needed);
967 if (aregs_needed
968 /* We need to check always_executed, since if the original value of
969 the invariant may be preserved, we may need to keep it in a
970 separate register. TODO check whether the register has an
971 use outside of the loop. */
972 && dep->always_executed
973 && !dep->def->uses->next)
975 /* If this is a single use, after moving the dependency we will not
976 need a new register. */
977 aregs_needed--;
980 (*regs_needed) += aregs_needed;
981 (*comp_cost) += acomp_cost;
985 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
986 of registers used in the loop, N_INV_USES is the number of uses of
987 invariants, NEW_REGS is the number of new variables already added due to
988 the invariant motion. The number of registers needed for it is stored in
989 *REGS_NEEDED. */
991 static int
992 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
993 unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
995 int comp_cost, size_cost;
997 get_inv_cost (inv, &comp_cost, regs_needed);
998 actual_stamp++;
1000 size_cost = (global_cost_for_size (new_regs + *regs_needed,
1001 regs_used, n_inv_uses)
1002 - global_cost_for_size (new_regs, regs_used, n_inv_uses));
1004 return comp_cost - size_cost;
1007 /* Finds invariant with best gain for moving. Returns the gain, stores
1008 the invariant in *BEST and number of registers needed for it to
1009 *REGS_NEEDED. REGS_USED is the number of registers used in
1010 the loop, N_INV_USES is the number of uses of invariants. NEW_REGS
1011 is the number of new variables already added due to invariant motion. */
1013 static int
1014 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1015 unsigned new_regs, unsigned regs_used,
1016 unsigned n_inv_uses)
1018 struct invariant *inv;
1019 int gain = 0, again;
1020 unsigned aregs_needed, invno;
1022 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1024 if (inv->move)
1025 continue;
1027 /* Only consider the "representatives" of equivalent invariants. */
1028 if (inv->eqto != inv->invno)
1029 continue;
1031 again = gain_for_invariant (inv, &aregs_needed,
1032 new_regs, regs_used, n_inv_uses);
1033 if (again > gain)
1035 gain = again;
1036 *best = inv;
1037 *regs_needed = aregs_needed;
1041 return gain;
1044 /* Marks invariant INVNO and all its dependencies for moving. */
1046 static void
1047 set_move_mark (unsigned invno)
1049 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1050 bitmap_iterator bi;
1052 /* Find the representative of the class of the equivalent invariants. */
1053 inv = VEC_index (invariant_p, invariants, inv->eqto);
1055 if (inv->move)
1056 return;
1057 inv->move = true;
1059 if (dump_file)
1060 fprintf (dump_file, "Decided to move invariant %d\n", invno);
1062 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1064 set_move_mark (invno);
1068 /* Determines which invariants to move. */
1070 static void
1071 find_invariants_to_move (void)
1073 unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
1074 struct invariant *inv = NULL;
1075 unsigned int n_regs = DF_REG_SIZE (df);
1077 if (!VEC_length (invariant_p, invariants))
1078 return;
1080 /* Now something slightly more involved. First estimate the number of used
1081 registers. */
1082 n_inv_uses = 0;
1084 /* We do not really do a good job in this estimation; put some initial bound
1085 here to stand for induction variables etc. that we do not detect. */
1086 regs_used = 2;
1088 for (i = 0; i < n_regs; i++)
1090 if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
1092 /* This is a value that is used but not changed inside loop. */
1093 regs_used++;
1097 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1099 if (inv->def)
1100 n_inv_uses += inv->def->n_uses;
1103 new_regs = 0;
1104 while (best_gain_for_invariant (&inv, &regs_needed,
1105 new_regs, regs_used, n_inv_uses) > 0)
1107 set_move_mark (inv->invno);
1108 new_regs += regs_needed;
1112 /* Returns true if all insns in SEQ are valid. */
1114 static bool
1115 seq_insns_valid_p (rtx seq)
1117 rtx x;
1119 for (x = seq; x; x = NEXT_INSN (x))
1120 if (insn_invalid_p (x))
1121 return false;
1123 return true;
1126 /* Move invariant INVNO out of the LOOP. Returns true if this succeeds, false
1127 otherwise. */
1129 static bool
1130 move_invariant_reg (struct loop *loop, unsigned invno)
1132 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1133 struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1134 unsigned i;
1135 basic_block preheader = loop_preheader_edge (loop)->src;
1136 rtx reg, set, dest, seq, op;
1137 struct use *use;
1138 bitmap_iterator bi;
1140 if (inv->reg)
1141 return true;
1142 if (!repr->move)
1143 return false;
1145 /* If this is a representative of the class of equivalent invariants,
1146 really move the invariant. Otherwise just replace its use with
1147 the register used for the representative. */
1148 if (inv == repr)
1150 if (inv->depends_on)
1152 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1154 if (!move_invariant_reg (loop, i))
1155 goto fail;
1159 /* Move the set out of the loop. If the set is always executed (we could
1160 omit this condition if we know that the register is unused outside of the
1161 loop, but it does not seem worth finding out) and it has no uses that
1162 would not be dominated by it, we may just move it (TODO). Otherwise we
1163 need to create a temporary register. */
1164 set = single_set (inv->insn);
1165 dest = SET_DEST (set);
1166 reg = gen_reg_rtx (GET_MODE (dest));
1168 /* If the SET_DEST of the invariant insn is a pseudo, we can just move
1169 the insn out of the loop. Otherwise, we have to use gen_move_insn
1170 to let emit_move_insn produce a valid instruction stream. */
1171 if (REG_P (dest) && !HARD_REGISTER_P (dest))
1173 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1174 SET_DEST (set) = reg;
1175 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1177 else
1179 start_sequence ();
1180 op = force_operand (SET_SRC (set), reg);
1181 if (op != reg)
1182 emit_move_insn (reg, op);
1183 seq = get_insns ();
1184 end_sequence ();
1186 if (!seq_insns_valid_p (seq))
1187 goto fail;
1188 emit_insn_after (seq, BB_END (preheader));
1190 emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1191 delete_insn (inv->insn);
1194 else
1196 if (!move_invariant_reg (loop, repr->invno))
1197 goto fail;
1198 reg = repr->reg;
1199 set = single_set (inv->insn);
1200 emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1201 delete_insn (inv->insn);
1204 inv->reg = reg;
1206 /* Replace the uses we know to be dominated. It saves work for copy
1207 propagation, and also it is necessary so that dependent invariants
1208 are computed right. */
1209 if (inv->def)
1211 for (use = inv->def->uses; use; use = use->next)
1212 *use->pos = reg;
1215 return true;
1217 fail:
1218 /* If we failed, clear move flag, so that we do not try to move inv
1219 again. */
1220 if (dump_file)
1221 fprintf (dump_file, "Failed to move invariant %d\n", invno);
1222 inv->move = false;
1223 inv->reg = NULL_RTX;
1224 return false;
1227 /* Move selected invariant out of the LOOP. Newly created regs are marked
1228 in TEMPORARY_REGS. */
1230 static void
1231 move_invariants (struct loop *loop)
1233 struct invariant *inv;
1234 unsigned i;
1236 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1237 move_invariant_reg (loop, i);
1240 /* Initializes invariant motion data. */
1242 static void
1243 init_inv_motion_data (void)
1245 actual_stamp = 1;
1247 invariants = VEC_alloc (invariant_p, heap, 100);
1250 /* Frees the data allocated by invariant motion. */
1252 static void
1253 free_inv_motion_data (void)
1255 unsigned i;
1256 struct def *def;
1257 struct invariant *inv;
1259 for (i = 0; i < DF_DEFS_SIZE (df); i++)
1261 struct df_ref * ref = DF_DEFS_GET (df, i);
1262 if (!ref)
1263 continue;
1265 inv = DF_REF_DATA (ref);
1266 if (!inv)
1267 continue;
1269 def = inv->def;
1270 gcc_assert (def != NULL);
1272 free_use_list (def->uses);
1273 free (def);
1274 DF_REF_DATA (ref) = NULL;
1277 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1279 BITMAP_FREE (inv->depends_on);
1280 free (inv);
1282 VEC_free (invariant_p, heap, invariants);
1285 /* Move the invariants out of the LOOP. */
1287 static void
1288 move_single_loop_invariants (struct loop *loop)
1290 init_inv_motion_data ();
1292 find_invariants (loop);
1293 find_invariants_to_move ();
1294 move_invariants (loop);
1296 free_inv_motion_data ();
1299 /* Releases the auxiliary data for LOOP. */
1301 static void
1302 free_loop_data (struct loop *loop)
1304 struct loop_data *data = LOOP_DATA (loop);
1306 free (data);
1307 loop->aux = NULL;
1310 /* Move the invariants out of the LOOPS. */
1312 void
1313 move_loop_invariants (struct loops *loops)
1315 struct loop *loop;
1316 unsigned i;
1318 df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES);
1319 df_chain_add_problem (df, DF_UD_CHAIN);
1321 /* Process the loops, innermost first. */
1322 loop = loops->tree_root;
1323 while (loop->inner)
1324 loop = loop->inner;
1326 while (loop != loops->tree_root)
1328 move_single_loop_invariants (loop);
1330 if (loop->next)
1332 loop = loop->next;
1333 while (loop->inner)
1334 loop = loop->inner;
1336 else
1337 loop = loop->outer;
1340 for (i = 1; i < loops->num; i++)
1341 if (loops->parray[i])
1342 free_loop_data (loops->parray[i]);
1344 df_finish (df);
1345 df = NULL;
1347 #ifdef ENABLE_CHECKING
1348 verify_flow_info ();
1349 #endif