1 /* Rtl-level loop invariant motion.
2 Copyright (C) 2004, 2005 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
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 /* This implements the loop invariant motion pass. It is very simple
22 (no calls, libcalls, etc.). This should be sufficient to cleanup things like
23 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. */
40 #include "coretypes.h"
43 #include "hard-reg-set.h"
45 #include "basic-block.h"
53 /* The data stored for the loop. */
57 struct loop *outermost_exit; /* The outermost exit of the loop. */
58 bool has_call; /* True if the loop contains a call. */
61 #define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
63 /* The description of an use. */
67 rtx *pos; /* Position of the use. */
68 rtx insn; /* The insn in that the use occurs. */
70 struct use *next; /* Next use in the list. */
73 /* The description of a def. */
77 struct use *uses; /* The list of uses that are uniquely reached
79 unsigned n_uses; /* Number of such uses. */
80 unsigned invno; /* The corresponding invariant. */
83 /* The data stored for each invariant. */
87 /* The number of the invariant. */
90 /* Whether we already processed the invariant. */
93 /* The definition of the invariant. */
96 /* The insn in that it is defined. */
99 /* Whether it is always executed. */
100 bool always_executed;
102 /* Whether to move the invariant. */
105 /* Cost if the invariant. */
108 /* The invariants it depends on. */
111 /* Used for detecting already visited invariants during determining
112 costs of movements. */
116 /* The actual stamp for marking already visited invariants during determining
117 costs of movements. */
119 static unsigned actual_stamp;
121 typedef struct invariant *invariant_p;
123 DEF_VEC_P(invariant_p);
124 DEF_VEC_ALLOC_P(invariant_p, heap);
126 /* The invariants. */
128 static VEC(invariant_p,heap) *invariants;
130 /* Test for possibility of invariantness of X. */
133 check_maybe_invariant (rtx x)
135 enum rtx_code code = GET_CODE (x);
150 case UNSPEC_VOLATILE:
158 /* Load/store motion is done elsewhere. ??? Perhaps also add it here?
159 It should not be hard, and might be faster than "elsewhere". */
161 /* Just handle the most trivial case where we load from an unchanging
162 location (most importantly, pic tables). */
163 if (MEM_READONLY_P (x))
169 /* Don't mess with insns declared volatile. */
170 if (MEM_VOLATILE_P (x))
178 fmt = GET_RTX_FORMAT (code);
179 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
183 if (!check_maybe_invariant (XEXP (x, i)))
186 else if (fmt[i] == 'E')
188 for (j = 0; j < XVECLEN (x, i); j++)
189 if (!check_maybe_invariant (XVECEXP (x, i, j)))
197 /* Determines the basic blocks inside LOOP that are always executed and
198 stores their bitmap to ALWAYS_REACHED. MAY_EXIT is a bitmap of
199 basic blocks that may either exit the loop, or contain the call that
200 does not have to return. BODY is body of the loop obtained by
201 get_loop_body_in_dom_order. */
204 compute_always_reached (struct loop *loop, basic_block *body,
205 bitmap may_exit, bitmap always_reached)
209 for (i = 0; i < loop->num_nodes; i++)
211 if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
212 bitmap_set_bit (always_reached, i);
214 if (bitmap_bit_p (may_exit, i))
219 /* Finds exits out of the LOOP with body BODY. Marks blocks in that we may
220 exit the loop by cfg edge to HAS_EXIT and MAY_EXIT. In MAY_EXIT
221 additionally mark blocks that may exit due to a call. */
224 find_exits (struct loop *loop, basic_block *body,
225 bitmap may_exit, bitmap has_exit)
230 struct loop *outermost_exit = loop, *aexit;
231 bool has_call = false;
234 for (i = 0; i < loop->num_nodes; i++)
236 if (body[i]->loop_father == loop)
238 FOR_BB_INSNS (body[i], insn)
241 && !CONST_OR_PURE_CALL_P (insn))
244 bitmap_set_bit (may_exit, i);
249 FOR_EACH_EDGE (e, ei, body[i]->succs)
251 if (flow_bb_inside_loop_p (loop, e->dest))
254 bitmap_set_bit (may_exit, i);
255 bitmap_set_bit (has_exit, i);
256 outermost_exit = find_common_loop (outermost_exit,
257 e->dest->loop_father);
262 /* Use the data stored for the subloop to decide whether we may exit
263 through it. It is sufficient to do this for header of the loop,
264 as other basic blocks inside it must be dominated by it. */
265 if (body[i]->loop_father->header != body[i])
268 if (LOOP_DATA (body[i]->loop_father)->has_call)
271 bitmap_set_bit (may_exit, i);
273 aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
276 bitmap_set_bit (may_exit, i);
277 bitmap_set_bit (has_exit, i);
279 if (flow_loop_nested_p (aexit, outermost_exit))
280 outermost_exit = aexit;
284 loop->aux = xcalloc (1, sizeof (struct loop_data));
285 LOOP_DATA (loop)->outermost_exit = outermost_exit;
286 LOOP_DATA (loop)->has_call = has_call;
289 /* Check whether we may assign a value to X from a register. */
292 may_assign_reg_p (rtx x)
294 return (can_copy_p (GET_MODE (x))
296 || !HARD_REGISTER_P (x)
297 || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
300 /* Finds definitions that may correspond to invariants in LOOP with body BODY.
301 DF is the dataflow object. */
304 find_defs (struct loop *loop, basic_block *body, struct df *df)
307 bitmap blocks = BITMAP_ALLOC (NULL);
309 for (i = 0; i < loop->num_nodes; i++)
310 bitmap_set_bit (blocks, body[i]->index);
312 df_analyze_subcfg (df, blocks, DF_UD_CHAIN | DF_HARD_REGS | DF_EQUIV_NOTES);
313 BITMAP_FREE (blocks);
316 /* Creates a new invariant for definition DEF in INSN, depending on invariants
317 in DEPENDS_ON. ALWAYS_EXECUTED is true if the insn is always executed,
318 unless the program ends due to a function call. */
321 create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
322 bool always_executed)
324 struct invariant *inv = xmalloc (sizeof (struct invariant));
325 rtx set = single_set (insn);
328 inv->always_executed = always_executed;
329 inv->depends_on = depends_on;
331 /* If the set is simple, usually by moving it we move the whole store out of
332 the loop. Otherwise we save only cost of the computation. */
334 inv->cost = rtx_cost (set, SET);
336 inv->cost = rtx_cost (SET_SRC (set), SET);
339 inv->processed = false;
343 inv->invno = VEC_length (invariant_p, invariants);
345 def->invno = inv->invno;
346 VEC_safe_push (invariant_p, heap, invariants, inv);
351 "Set in insn %d is invariant (%d), cost %d, depends on ",
352 INSN_UID (insn), inv->invno, inv->cost);
353 dump_bitmap (dump_file, inv->depends_on);
357 /* Record USE at DEF. */
360 record_use (struct def *def, rtx *use, rtx insn)
362 struct use *u = xmalloc (sizeof (struct use));
364 if (GET_CODE (*use) == SUBREG)
365 use = &SUBREG_REG (*use);
366 gcc_assert (REG_P (*use));
375 /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
376 bitmap. DF is the dataflow object. */
379 check_dependencies (rtx insn, struct df *df, bitmap depends_on)
381 struct df_link *uses, *defs;
382 struct ref *use, *def;
383 basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
384 struct def *def_data;
386 for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
390 defs = DF_REF_CHAIN (use);
398 def_data = DF_REF_DATA (def);
402 def_bb = DF_REF_BB (def);
403 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
406 bitmap_set_bit (depends_on, def_data->invno);
412 /* Finds invariant in INSN. ALWAYS_REACHED is true if the insn is always
413 executed. ALWAYS_EXECUTED is true if the insn is always executed,
414 unless the program ends due to a function call. DF is the dataflow
418 find_invariant_insn (rtx insn, bool always_reached, bool always_executed,
427 /* Until we get rid of LIBCALLS. */
428 if (find_reg_note (insn, REG_RETVAL, NULL_RTX)
429 || find_reg_note (insn, REG_LIBCALL, NULL_RTX)
430 || find_reg_note (insn, REG_NO_CONFLICT, NULL_RTX))
433 set = single_set (insn);
436 dest = SET_DEST (set);
439 || HARD_REGISTER_P (dest))
442 if (!may_assign_reg_p (SET_DEST (set))
443 || !check_maybe_invariant (SET_SRC (set)))
446 if (may_trap_p (PATTERN (insn)))
451 /* Unless the exceptions are handled, the behavior is undefined
452 if the trap occurs. */
453 if (flag_non_call_exceptions)
457 depends_on = BITMAP_ALLOC (NULL);
458 if (!check_dependencies (insn, df, depends_on))
460 BITMAP_FREE (depends_on);
466 ref = df_find_def (df, insn, dest);
467 def = xcalloc (1, sizeof (struct def));
468 DF_REF_DATA (ref) = def;
473 create_new_invariant (def, insn, depends_on, always_executed);
476 /* Record registers used in INSN that have a unique invariant definition.
477 DF is the dataflow object. */
480 record_uses (rtx insn, struct df *df)
482 struct df_link *uses, *defs;
483 struct ref *use, *def;
484 basic_block bb = BLOCK_FOR_INSN (insn), def_bb;
486 for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
490 defs = DF_REF_CHAIN (use);
491 if (!defs || defs->next)
494 if (!DF_REF_DATA (def))
497 def_bb = DF_REF_BB (def);
498 if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
501 record_use (DF_REF_DATA (def), DF_REF_LOC (use), DF_REF_INSN (use));
505 /* Finds invariants in INSN. ALWAYS_REACHED is true if the insn is always
506 executed. ALWAYS_EXECUTED is true if the insn is always executed,
507 unless the program ends due to a function call. DF is the dataflow
511 find_invariants_insn (rtx insn, bool always_reached, bool always_executed,
514 find_invariant_insn (insn, always_reached, always_executed, df);
515 record_uses (insn, df);
518 /* Finds invariants in basic block BB. ALWAYS_REACHED is true if the
519 basic block is always executed. ALWAYS_EXECUTED is true if the basic
520 block is always executed, unless the program ends due to a function
521 call. DF is the dataflow object. */
524 find_invariants_bb (basic_block bb, bool always_reached, bool always_executed,
529 FOR_BB_INSNS (bb, insn)
534 find_invariants_insn (insn, always_reached, always_executed, df);
538 && !CONST_OR_PURE_CALL_P (insn))
539 always_reached = false;
543 /* Finds invariants in LOOP with body BODY. ALWAYS_REACHED is the bitmap of
544 basic blocks in BODY that are always executed. ALWAYS_EXECUTED is the
545 bitmap of basic blocks in BODY that are always executed unless the program
546 ends due to a function call. DF is the dataflow object. */
549 find_invariants_body (struct loop *loop, basic_block *body,
550 bitmap always_reached, bitmap always_executed,
555 for (i = 0; i < loop->num_nodes; i++)
556 find_invariants_bb (body[i],
557 bitmap_bit_p (always_reached, i),
558 bitmap_bit_p (always_executed, i),
562 /* Finds invariants in LOOP. DF is the dataflow object. */
565 find_invariants (struct loop *loop, struct df *df)
567 bitmap may_exit = BITMAP_ALLOC (NULL);
568 bitmap always_reached = BITMAP_ALLOC (NULL);
569 bitmap has_exit = BITMAP_ALLOC (NULL);
570 bitmap always_executed = BITMAP_ALLOC (NULL);
571 basic_block *body = get_loop_body_in_dom_order (loop);
573 find_exits (loop, body, may_exit, has_exit);
574 compute_always_reached (loop, body, may_exit, always_reached);
575 compute_always_reached (loop, body, has_exit, always_executed);
577 find_defs (loop, body, df);
578 find_invariants_body (loop, body, always_reached, always_executed, df);
580 BITMAP_FREE (always_reached);
581 BITMAP_FREE (always_executed);
582 BITMAP_FREE (may_exit);
583 BITMAP_FREE (has_exit);
587 /* Frees a list of uses USE. */
590 free_use_list (struct use *use)
594 for (; use; use = next)
601 /* Calculates cost and number of registers needed for moving invariant INV
602 out of the loop and stores them to *COST and *REGS_NEEDED. */
605 get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
608 unsigned aregs_needed;
610 struct invariant *dep;
616 || inv->stamp == actual_stamp)
618 inv->stamp = actual_stamp;
621 (*comp_cost) += inv->cost;
623 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
625 dep = VEC_index (invariant_p, invariants, depno);
627 get_inv_cost (dep, &acomp_cost, &aregs_needed);
630 /* We need to check always_executed, since if the original value of
631 the invariant may be preserved, we may need to keep it in a
632 separate register. TODO check whether the register has an
633 use outside of the loop. */
634 && dep->always_executed
635 && !dep->def->uses->next)
637 /* If this is a single use, after moving the dependency we will not
638 need a new register. */
642 (*regs_needed) += aregs_needed;
643 (*comp_cost) += acomp_cost;
647 /* Calculates gain for eliminating invariant INV. REGS_USED is the number
648 of registers used in the loop, N_INV_USES is the number of uses of
649 invariants, NEW_REGS is the number of new variables already added due to
650 the invariant motion. The number of registers needed for it is stored in
654 gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
655 unsigned new_regs, unsigned regs_used, unsigned n_inv_uses)
657 int comp_cost, size_cost;
659 get_inv_cost (inv, &comp_cost, regs_needed);
662 size_cost = (global_cost_for_size (new_regs + *regs_needed,
663 regs_used, n_inv_uses)
664 - global_cost_for_size (new_regs, regs_used, n_inv_uses));
666 return comp_cost - size_cost;
669 /* Finds invariant with best gain for moving. Returns the gain, stores
670 the invariant in *BEST and number of registers needed for it to
671 *REGS_NEEDED. REGS_USED is the number of registers used in
672 the loop, N_INV_USES is the number of uses of invariants. NEW_REGS
673 is the number of new variables already added due to invariant motion. */
676 best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
677 unsigned new_regs, unsigned regs_used,
680 struct invariant *inv;
682 unsigned aregs_needed, invno;
684 for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
689 again = gain_for_invariant (inv, &aregs_needed,
690 new_regs, regs_used, n_inv_uses);
695 *regs_needed = aregs_needed;
702 /* Marks invariant INVNO and all its dependencies for moving. */
705 set_move_mark (unsigned invno)
707 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
715 fprintf (dump_file, "Decided to move invariant %d\n", invno);
717 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
719 set_move_mark (invno);
723 /* Determines which invariants to move. DF is the dataflow object. */
726 find_invariants_to_move (struct df *df)
728 unsigned i, regs_used, n_inv_uses, regs_needed = 0, new_regs;
729 struct invariant *inv = NULL;
731 if (!VEC_length (invariant_p, invariants))
734 /* Now something slightly more involved. First estimate the number of used
738 /* We do not really do a good job in this estimation; put some initial bound
739 here to stand for induction variables etc. that we do not detect. */
742 for (i = 0; i < df->n_regs; i++)
744 if (!DF_REGNO_FIRST_DEF (df, i) && DF_REGNO_LAST_USE (df, i))
746 /* This is a value that is used but not changed inside loop. */
751 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
754 n_inv_uses += inv->def->n_uses;
758 while (best_gain_for_invariant (&inv, ®s_needed,
759 new_regs, regs_used, n_inv_uses) > 0)
761 set_move_mark (inv->invno);
762 new_regs += regs_needed;
766 /* Move invariant INVNO out of the LOOP. DF is the dataflow object. */
769 move_invariant_reg (struct loop *loop, unsigned invno, struct df *df)
771 struct invariant *inv = VEC_index (invariant_p, invariants, invno);
773 basic_block preheader = loop_preheader_edge (loop)->src;
780 inv->processed = true;
784 EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
786 move_invariant_reg (loop, i, df);
790 /* Move the set out of the loop. If the set is always executed (we could
791 omit this condition if we know that the register is unused outside of the
792 loop, but it does not seem worth finding out) and it has no uses that
793 would not be dominated by it, we may just move it (TODO). Otherwise we
794 need to create a temporary register. */
795 set = single_set (inv->insn);
796 reg = gen_reg_rtx (GET_MODE (SET_DEST (set)));
797 df_pattern_emit_after (df, gen_move_insn (SET_DEST (set), reg),
798 BLOCK_FOR_INSN (inv->insn), inv->insn);
800 /* If the SET_DEST of the invariant insn is a reg, we can just move
801 the insn out of the loop. Otherwise, we have to use gen_move_insn
802 to let emit_move_insn produce a valid instruction stream. */
803 if (REG_P (SET_DEST (set)))
805 SET_DEST (set) = reg;
806 reorder_insns (inv->insn, inv->insn, BB_END (preheader));
807 df_insn_modify (df, preheader, inv->insn);
811 df_pattern_emit_after (df, gen_move_insn (reg, SET_SRC (set)),
812 preheader, BB_END (preheader));
813 df_insn_delete (df, BLOCK_FOR_INSN (inv->insn), inv->insn);
816 /* Replace the uses we know to be dominated. It saves work for copy
817 propagation, and also it is necessary so that dependent invariants
818 are computed right. */
821 for (use = inv->def->uses; use; use = use->next)
824 df_insn_modify (df, BLOCK_FOR_INSN (use->insn), use->insn);
829 /* Move selected invariant out of the LOOP. Newly created regs are marked
830 in TEMPORARY_REGS. DF is the dataflow object. */
833 move_invariants (struct loop *loop, struct df *df)
835 struct invariant *inv;
838 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
841 move_invariant_reg (loop, i, df);
845 /* Initializes invariant motion data. */
848 init_inv_motion_data (void)
852 invariants = VEC_alloc (invariant_p, heap, 100);
855 /* Frees the data allocated by invariant motion. DF is the dataflow
859 free_inv_motion_data (struct df *df)
863 struct invariant *inv;
865 for (i = 0; i < df->n_defs; i++)
870 def = DF_REF_DATA (df->defs[i]);
874 free_use_list (def->uses);
876 DF_REF_DATA (df->defs[i]) = NULL;
879 for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
881 BITMAP_FREE (inv->depends_on);
884 VEC_free (invariant_p, heap, invariants);
887 /* Move the invariants out of the LOOP. DF is the dataflow object. */
890 move_single_loop_invariants (struct loop *loop, struct df *df)
892 init_inv_motion_data ();
894 find_invariants (loop, df);
895 find_invariants_to_move (df);
896 move_invariants (loop, df);
898 free_inv_motion_data (df);
901 /* Releases the auxiliary data for LOOP. */
904 free_loop_data (struct loop *loop)
906 struct loop_data *data = LOOP_DATA (loop);
912 /* Move the invariants out of the LOOPS. */
915 move_loop_invariants (struct loops *loops)
919 struct df *df = df_init ();
921 /* Process the loops, innermost first. */
922 loop = loops->tree_root;
926 while (loop != loops->tree_root)
928 move_single_loop_invariants (loop, df);
940 for (i = 1; i < loops->num; i++)
941 if (loops->parray[i])
942 free_loop_data (loops->parray[i]);
946 #ifdef ENABLE_CHECKING