1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 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 under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 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
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
37 /* This pass performs loop unrolling and peeling. We only perform these
38 optimizations on innermost loops (with single exception) because
39 the impact on performance is greatest here, and we want to avoid
40 unnecessary code size growth. The gain is caused by greater sequentiality
41 of code, better code to optimize for further passes and in some cases
42 by fewer testings of exit conditions. The main problem is code growth,
43 that impacts performance negatively due to effect of caches.
47 -- complete peeling of once-rolling loops; this is the above mentioned
48 exception, as this causes loop to be cancelled completely and
49 does not cause code growth
50 -- complete peeling of loops that roll (small) constant times.
51 -- simple peeling of first iterations of loops that do not roll much
52 (according to profile feedback)
53 -- unrolling of loops that roll constant times; this is almost always
54 win, as we get rid of exit condition tests.
55 -- unrolling of loops that roll number of times that we can compute
56 in runtime; we also get rid of exit condition tests here, but there
57 is the extra expense for calculating the number of iterations
58 -- simple unrolling of remaining loops; this is performed only if we
59 are asked to, as the gain is questionable in this case and often
60 it may even slow down the code
61 For more detailed descriptions of each of those, see comments at
62 appropriate function below.
64 There is a lot of parameters (defined and described in params.def) that
65 control how much we unroll/peel.
67 ??? A great problem is that we don't have a good way how to determine
68 how many times we should unroll the loop; the experiments I have made
69 showed that this choice may affect performance in order of several %.
72 /* Information about induction variables to split. */
76 rtx insn; /* The insn in that the induction variable occurs. */
77 rtx base_var; /* The variable on that the values in the further
78 iterations are based. */
79 rtx step; /* Step of the induction variable. */
81 unsigned loc[3]; /* Location where the definition of the induction
82 variable occurs in the insn. For example if
83 N_LOC is 2, the expression is located at
84 XEXP (XEXP (single_set, loc[0]), loc[1]). */
87 /* Information about accumulators to expand. */
91 rtx insn; /* The insn in that the variable expansion occurs. */
92 rtx reg; /* The accumulator which is expanded. */
93 VEC(rtx,heap) *var_expansions; /* The copies of the accumulator which is expanded. */
94 enum rtx_code op; /* The type of the accumulation - addition, subtraction
96 int expansion_count; /* Count the number of expansions generated so far. */
97 int reuse_expansion; /* The expansion we intend to reuse to expand
98 the accumulator. If REUSE_EXPANSION is 0 reuse
99 the original accumulator. Else use
100 var_expansions[REUSE_EXPANSION - 1]. */
103 /* Information about optimization applied in
104 the unrolled loop. */
108 htab_t insns_to_split; /* A hashtable of insns to split. */
109 htab_t insns_with_var_to_expand; /* A hashtable of insns with accumulators
111 unsigned first_new_block; /* The first basic block that was
113 basic_block loop_exit; /* The loop exit basic block. */
114 basic_block loop_preheader; /* The loop preheader basic block. */
117 static void decide_unrolling_and_peeling (int);
118 static void peel_loops_completely (int);
119 static void decide_peel_simple (struct loop *, int);
120 static void decide_peel_once_rolling (struct loop *, int);
121 static void decide_peel_completely (struct loop *, int);
122 static void decide_unroll_stupid (struct loop *, int);
123 static void decide_unroll_constant_iterations (struct loop *, int);
124 static void decide_unroll_runtime_iterations (struct loop *, int);
125 static void peel_loop_simple (struct loop *);
126 static void peel_loop_completely (struct loop *);
127 static void unroll_loop_stupid (struct loop *);
128 static void unroll_loop_constant_iterations (struct loop *);
129 static void unroll_loop_runtime_iterations (struct loop *);
130 static struct opt_info *analyze_insns_in_loop (struct loop *);
131 static void opt_info_start_duplication (struct opt_info *);
132 static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
133 static void free_opt_info (struct opt_info *);
134 static struct var_to_expand *analyze_insn_to_expand_var (struct loop*, rtx);
135 static bool referenced_in_one_insn_in_loop_p (struct loop *, rtx);
136 static struct iv_to_split *analyze_iv_to_split_insn (rtx);
137 static void expand_var_during_unrolling (struct var_to_expand *, rtx);
138 static int insert_var_expansion_initialization (void **, void *);
139 static int combine_var_copies_in_loop_exit (void **, void *);
140 static int release_var_copies (void **, void *);
141 static rtx get_expansion (struct var_to_expand *);
143 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
145 unroll_and_peel_loops (int flags)
151 /* First perform complete loop peeling (it is almost surely a win,
152 and affects parameters for further decision a lot). */
153 peel_loops_completely (flags);
155 /* Now decide rest of unrolling and peeling. */
156 decide_unrolling_and_peeling (flags);
158 /* Scan the loops, inner ones first. */
159 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
162 /* And perform the appropriate transformations. */
163 switch (loop->lpt_decision.decision)
165 case LPT_PEEL_COMPLETELY:
168 case LPT_PEEL_SIMPLE:
169 peel_loop_simple (loop);
171 case LPT_UNROLL_CONSTANT:
172 unroll_loop_constant_iterations (loop);
174 case LPT_UNROLL_RUNTIME:
175 unroll_loop_runtime_iterations (loop);
177 case LPT_UNROLL_STUPID:
178 unroll_loop_stupid (loop);
188 #ifdef ENABLE_CHECKING
189 verify_dominators (CDI_DOMINATORS);
190 verify_loop_structure ();
198 /* Check whether exit of the LOOP is at the end of loop body. */
201 loop_exit_at_end_p (struct loop *loop)
203 struct niter_desc *desc = get_simple_loop_desc (loop);
206 if (desc->in_edge->dest != loop->latch)
209 /* Check that the latch is empty. */
210 FOR_BB_INSNS (loop->latch, insn)
219 /* Depending on FLAGS, check whether to peel loops completely and do so. */
221 peel_loops_completely (int flags)
226 /* Scan the loops, the inner ones first. */
227 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
229 loop->lpt_decision.decision = LPT_NONE;
233 "\n;; *** Considering loop %d for complete peeling ***\n",
236 loop->ninsns = num_loop_insns (loop);
238 decide_peel_once_rolling (loop, flags);
239 if (loop->lpt_decision.decision == LPT_NONE)
240 decide_peel_completely (loop, flags);
242 if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
244 peel_loop_completely (loop);
245 #ifdef ENABLE_CHECKING
246 verify_dominators (CDI_DOMINATORS);
247 verify_loop_structure ();
253 /* Decide whether unroll or peel loops (depending on FLAGS) and how much. */
255 decide_unrolling_and_peeling (int flags)
260 /* Scan the loops, inner ones first. */
261 FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
263 loop->lpt_decision.decision = LPT_NONE;
266 fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num);
268 /* Do not peel cold areas. */
269 if (!maybe_hot_bb_p (loop->header))
272 fprintf (dump_file, ";; Not considering loop, cold area\n");
276 /* Can the loop be manipulated? */
277 if (!can_duplicate_loop_p (loop))
281 ";; Not considering loop, cannot duplicate\n");
285 /* Skip non-innermost loops. */
289 fprintf (dump_file, ";; Not considering loop, is not innermost\n");
293 loop->ninsns = num_loop_insns (loop);
294 loop->av_ninsns = average_num_loop_insns (loop);
296 /* Try transformations one by one in decreasing order of
299 decide_unroll_constant_iterations (loop, flags);
300 if (loop->lpt_decision.decision == LPT_NONE)
301 decide_unroll_runtime_iterations (loop, flags);
302 if (loop->lpt_decision.decision == LPT_NONE)
303 decide_unroll_stupid (loop, flags);
304 if (loop->lpt_decision.decision == LPT_NONE)
305 decide_peel_simple (loop, flags);
309 /* Decide whether the LOOP is once rolling and suitable for complete
312 decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
314 struct niter_desc *desc;
317 fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
319 /* Is the loop small enough? */
320 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
323 fprintf (dump_file, ";; Not considering loop, is too big\n");
327 /* Check for simple loops. */
328 desc = get_simple_loop_desc (loop);
330 /* Check number of iterations. */
339 ";; Unable to prove that the loop rolls exactly once\n");
345 fprintf (dump_file, ";; Decided to peel exactly once rolling loop\n");
346 loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
349 /* Decide whether the LOOP is suitable for complete peeling. */
351 decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
354 struct niter_desc *desc;
357 fprintf (dump_file, "\n;; Considering peeling completely\n");
359 /* Skip non-innermost loops. */
363 fprintf (dump_file, ";; Not considering loop, is not innermost\n");
367 /* Do not peel cold areas. */
368 if (!maybe_hot_bb_p (loop->header))
371 fprintf (dump_file, ";; Not considering loop, cold area\n");
375 /* Can the loop be manipulated? */
376 if (!can_duplicate_loop_p (loop))
380 ";; Not considering loop, cannot duplicate\n");
384 /* npeel = number of iterations to peel. */
385 npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
386 if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
387 npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
389 /* Is the loop small enough? */
393 fprintf (dump_file, ";; Not considering loop, is too big\n");
397 /* Check for simple loops. */
398 desc = get_simple_loop_desc (loop);
400 /* Check number of iterations. */
408 ";; Unable to prove that the loop iterates constant times\n");
412 if (desc->niter > npeel - 1)
417 ";; Not peeling loop completely, rolls too much (");
418 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
419 fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
426 fprintf (dump_file, ";; Decided to peel loop completely\n");
427 loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
430 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
431 completely. The transformation done:
433 for (i = 0; i < 4; i++)
445 peel_loop_completely (struct loop *loop)
448 unsigned HOST_WIDE_INT npeel;
450 VEC (edge, heap) *remove_edges;
452 struct niter_desc *desc = get_simple_loop_desc (loop);
453 struct opt_info *opt_info = NULL;
461 wont_exit = sbitmap_alloc (npeel + 1);
462 sbitmap_ones (wont_exit);
463 RESET_BIT (wont_exit, 0);
464 if (desc->noloop_assumptions)
465 RESET_BIT (wont_exit, 1);
469 if (flag_split_ivs_in_unroller)
470 opt_info = analyze_insns_in_loop (loop);
472 opt_info_start_duplication (opt_info);
473 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
475 wont_exit, desc->out_edge,
477 DLTHE_FLAG_UPDATE_FREQ
478 | DLTHE_FLAG_COMPLETTE_PEEL
480 ? DLTHE_RECORD_COPY_NUMBER : 0));
487 apply_opt_in_copies (opt_info, npeel, false, true);
488 free_opt_info (opt_info);
491 /* Remove the exit edges. */
492 for (i = 0; VEC_iterate (edge, remove_edges, i, ein); i++)
494 VEC_free (edge, heap, remove_edges);
498 free_simple_loop_desc (loop);
500 /* Now remove the unreachable part of the last iteration and cancel
505 fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
508 /* Decide whether to unroll LOOP iterating constant number of times
512 decide_unroll_constant_iterations (struct loop *loop, int flags)
514 unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
515 struct niter_desc *desc;
517 if (!(flags & UAP_UNROLL))
519 /* We were not asked to, just return back silently. */
525 "\n;; Considering unrolling loop with constant "
526 "number of iterations\n");
528 /* nunroll = total number of copies of the original loop body in
529 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
530 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
532 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
533 if (nunroll > nunroll_by_av)
534 nunroll = nunroll_by_av;
535 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
536 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
538 /* Skip big loops. */
542 fprintf (dump_file, ";; Not considering loop, is too big\n");
546 /* Check for simple loops. */
547 desc = get_simple_loop_desc (loop);
549 /* Check number of iterations. */
550 if (!desc->simple_p || !desc->const_iter || desc->assumptions)
554 ";; Unable to prove that the loop iterates constant times\n");
558 /* Check whether the loop rolls enough to consider. */
559 if (desc->niter < 2 * nunroll)
562 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
566 /* Success; now compute number of iterations to unroll. We alter
567 nunroll so that as few as possible copies of loop body are
568 necessary, while still not decreasing the number of unrollings
569 too much (at most by 1). */
570 best_copies = 2 * nunroll + 10;
573 if (i - 1 >= desc->niter)
576 for (; i >= nunroll - 1; i--)
578 unsigned exit_mod = desc->niter % (i + 1);
580 if (!loop_exit_at_end_p (loop))
581 n_copies = exit_mod + i + 1;
582 else if (exit_mod != (unsigned) i
583 || desc->noloop_assumptions != NULL_RTX)
584 n_copies = exit_mod + i + 2;
588 if (n_copies < best_copies)
590 best_copies = n_copies;
596 fprintf (dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
597 best_unroll + 1, best_copies, nunroll);
599 loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
600 loop->lpt_decision.times = best_unroll;
604 ";; Decided to unroll the constant times rolling loop, %d times.\n",
605 loop->lpt_decision.times);
608 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
609 times. The transformation does this:
611 for (i = 0; i < 102; i++)
628 unroll_loop_constant_iterations (struct loop *loop)
630 unsigned HOST_WIDE_INT niter;
634 VEC (edge, heap) *remove_edges;
636 unsigned max_unroll = loop->lpt_decision.times;
637 struct niter_desc *desc = get_simple_loop_desc (loop);
638 bool exit_at_end = loop_exit_at_end_p (loop);
639 struct opt_info *opt_info = NULL;
644 /* Should not get here (such loop should be peeled instead). */
645 gcc_assert (niter > max_unroll + 1);
647 exit_mod = niter % (max_unroll + 1);
649 wont_exit = sbitmap_alloc (max_unroll + 1);
650 sbitmap_ones (wont_exit);
653 if (flag_split_ivs_in_unroller
654 || flag_variable_expansion_in_unroller)
655 opt_info = analyze_insns_in_loop (loop);
659 /* The exit is not at the end of the loop; leave exit test
660 in the first copy, so that the loops that start with test
661 of exit condition have continuous body after unrolling. */
664 fprintf (dump_file, ";; Condition on beginning of loop.\n");
666 /* Peel exit_mod iterations. */
667 RESET_BIT (wont_exit, 0);
668 if (desc->noloop_assumptions)
669 RESET_BIT (wont_exit, 1);
673 opt_info_start_duplication (opt_info);
674 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
676 wont_exit, desc->out_edge,
678 DLTHE_FLAG_UPDATE_FREQ
679 | (opt_info && exit_mod > 1
680 ? DLTHE_RECORD_COPY_NUMBER
684 if (opt_info && exit_mod > 1)
685 apply_opt_in_copies (opt_info, exit_mod, false, false);
687 desc->noloop_assumptions = NULL_RTX;
688 desc->niter -= exit_mod;
689 desc->niter_max -= exit_mod;
692 SET_BIT (wont_exit, 1);
696 /* Leave exit test in last copy, for the same reason as above if
697 the loop tests the condition at the end of loop body. */
700 fprintf (dump_file, ";; Condition on end of loop.\n");
702 /* We know that niter >= max_unroll + 2; so we do not need to care of
703 case when we would exit before reaching the loop. So just peel
704 exit_mod + 1 iterations. */
705 if (exit_mod != max_unroll
706 || desc->noloop_assumptions)
708 RESET_BIT (wont_exit, 0);
709 if (desc->noloop_assumptions)
710 RESET_BIT (wont_exit, 1);
712 opt_info_start_duplication (opt_info);
713 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
715 wont_exit, desc->out_edge,
717 DLTHE_FLAG_UPDATE_FREQ
718 | (opt_info && exit_mod > 0
719 ? DLTHE_RECORD_COPY_NUMBER
723 if (opt_info && exit_mod > 0)
724 apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
726 desc->niter -= exit_mod + 1;
727 desc->niter_max -= exit_mod + 1;
728 desc->noloop_assumptions = NULL_RTX;
730 SET_BIT (wont_exit, 0);
731 SET_BIT (wont_exit, 1);
734 RESET_BIT (wont_exit, max_unroll);
737 /* Now unroll the loop. */
739 opt_info_start_duplication (opt_info);
740 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
742 wont_exit, desc->out_edge,
744 DLTHE_FLAG_UPDATE_FREQ
746 ? DLTHE_RECORD_COPY_NUMBER
752 apply_opt_in_copies (opt_info, max_unroll, true, true);
753 free_opt_info (opt_info);
760 basic_block exit_block = get_bb_copy (desc->in_edge->src);
761 /* Find a new in and out edge; they are in the last copy we have made. */
763 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
765 desc->out_edge = EDGE_SUCC (exit_block, 0);
766 desc->in_edge = EDGE_SUCC (exit_block, 1);
770 desc->out_edge = EDGE_SUCC (exit_block, 1);
771 desc->in_edge = EDGE_SUCC (exit_block, 0);
775 desc->niter /= max_unroll + 1;
776 desc->niter_max /= max_unroll + 1;
777 desc->niter_expr = GEN_INT (desc->niter);
779 /* Remove the edges. */
780 for (i = 0; VEC_iterate (edge, remove_edges, i, e); i++)
782 VEC_free (edge, heap, remove_edges);
786 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
787 max_unroll, num_loop_insns (loop));
790 /* Decide whether to unroll LOOP iterating runtime computable number of times
793 decide_unroll_runtime_iterations (struct loop *loop, int flags)
795 unsigned nunroll, nunroll_by_av, i;
796 struct niter_desc *desc;
798 if (!(flags & UAP_UNROLL))
800 /* We were not asked to, just return back silently. */
806 "\n;; Considering unrolling loop with runtime "
807 "computable number of iterations\n");
809 /* nunroll = total number of copies of the original loop body in
810 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
811 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
812 nunroll_by_av = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
813 if (nunroll > nunroll_by_av)
814 nunroll = nunroll_by_av;
815 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
816 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
818 /* Skip big loops. */
822 fprintf (dump_file, ";; Not considering loop, is too big\n");
826 /* Check for simple loops. */
827 desc = get_simple_loop_desc (loop);
829 /* Check simpleness. */
830 if (!desc->simple_p || desc->assumptions)
834 ";; Unable to prove that the number of iterations "
835 "can be counted in runtime\n");
839 if (desc->const_iter)
842 fprintf (dump_file, ";; Loop iterates constant times\n");
846 /* If we have profile feedback, check whether the loop rolls. */
847 if (loop->header->count && expected_loop_iterations (loop) < 2 * nunroll)
850 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
854 /* Success; now force nunroll to be power of 2, as we are unable to
855 cope with overflows in computation of number of iterations. */
856 for (i = 1; 2 * i <= nunroll; i *= 2)
859 loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
860 loop->lpt_decision.times = i - 1;
864 ";; Decided to unroll the runtime computable "
865 "times rolling loop, %d times.\n",
866 loop->lpt_decision.times);
869 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
870 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
871 and NULL is returned instead. */
874 split_edge_and_insert (edge e, rtx insns)
881 emit_insn_after (insns, BB_END (bb));
883 /* ??? We used to assume that INSNS can contain control flow insns, and
884 that we had to try to find sub basic blocks in BB to maintain a valid
885 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
886 and call break_superblocks when going out of cfglayout mode. But it
887 turns out that this never happens; and that if it does ever happen,
888 the verify_flow_info call in loop_optimizer_finalize would fail.
890 There are two reasons why we expected we could have control flow insns
891 in INSNS. The first is when a comparison has to be done in parts, and
892 the second is when the number of iterations is computed for loops with
893 the number of iterations known at runtime. In both cases, test cases
894 to get control flow in INSNS appear to be impossible to construct:
896 * If do_compare_rtx_and_jump needs several branches to do comparison
897 in a mode that needs comparison by parts, we cannot analyze the
898 number of iterations of the loop, and we never get to unrolling it.
900 * The code in expand_divmod that was suspected to cause creation of
901 branching code seems to be only accessed for signed division. The
902 divisions used by # of iterations analysis are always unsigned.
903 Problems might arise on architectures that emits branching code
904 for some operations that may appear in the unroller (especially
905 for division), but we have no such architectures.
907 Considering all this, it was decided that we should for now assume
908 that INSNS can in theory contain control flow insns, but in practice
909 it never does. So we don't handle the theoretical case, and should
910 a real failure ever show up, we have a pretty good clue for how to
916 /* Unroll LOOP for that we are able to count number of iterations in runtime
917 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
918 extra care for case n < 0):
920 for (i = 0; i < n; i++)
948 unroll_loop_runtime_iterations (struct loop *loop)
950 rtx old_niter, niter, init_code, branch_code, tmp;
952 basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
957 VEC (edge, heap) *remove_edges;
959 bool extra_zero_check, last_may_exit;
960 unsigned max_unroll = loop->lpt_decision.times;
961 struct niter_desc *desc = get_simple_loop_desc (loop);
962 bool exit_at_end = loop_exit_at_end_p (loop);
963 struct opt_info *opt_info = NULL;
966 if (flag_split_ivs_in_unroller
967 || flag_variable_expansion_in_unroller)
968 opt_info = analyze_insns_in_loop (loop);
970 /* Remember blocks whose dominators will have to be updated. */
971 dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
974 body = get_loop_body (loop);
975 for (i = 0; i < loop->num_nodes; i++)
980 nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
981 for (j = 0; j < nldom; j++)
982 if (!flow_bb_inside_loop_p (loop, ldom[j]))
983 dom_bbs[n_dom_bbs++] = ldom[j];
991 /* Leave exit in first copy (for explanation why see comment in
992 unroll_loop_constant_iterations). */
994 n_peel = max_unroll - 1;
995 extra_zero_check = true;
996 last_may_exit = false;
1000 /* Leave exit in last copy (for explanation why see comment in
1001 unroll_loop_constant_iterations). */
1002 may_exit_copy = max_unroll;
1003 n_peel = max_unroll;
1004 extra_zero_check = false;
1005 last_may_exit = true;
1008 /* Get expression for number of iterations. */
1010 old_niter = niter = gen_reg_rtx (desc->mode);
1011 tmp = force_operand (copy_rtx (desc->niter_expr), niter);
1013 emit_move_insn (niter, tmp);
1015 /* Count modulo by ANDing it with max_unroll; we use the fact that
1016 the number of unrollings is a power of two, and thus this is correct
1017 even if there is overflow in the computation. */
1018 niter = expand_simple_binop (desc->mode, AND,
1020 GEN_INT (max_unroll),
1021 NULL_RTX, 0, OPTAB_LIB_WIDEN);
1023 init_code = get_insns ();
1026 /* Precondition the loop. */
1027 split_edge_and_insert (loop_preheader_edge (loop), init_code);
1029 remove_edges = NULL;
1031 wont_exit = sbitmap_alloc (max_unroll + 2);
1033 /* Peel the first copy of loop body (almost always we must leave exit test
1034 here; the only exception is when we have extra zero check and the number
1035 of iterations is reliable. Also record the place of (possible) extra
1037 sbitmap_zero (wont_exit);
1038 if (extra_zero_check
1039 && !desc->noloop_assumptions)
1040 SET_BIT (wont_exit, 1);
1041 ezc_swtch = loop_preheader_edge (loop)->src;
1042 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1043 1, wont_exit, desc->out_edge,
1045 DLTHE_FLAG_UPDATE_FREQ);
1048 /* Record the place where switch will be built for preconditioning. */
1049 swtch = split_edge (loop_preheader_edge (loop));
1051 for (i = 0; i < n_peel; i++)
1053 /* Peel the copy. */
1054 sbitmap_zero (wont_exit);
1055 if (i != n_peel - 1 || !last_may_exit)
1056 SET_BIT (wont_exit, 1);
1057 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1058 1, wont_exit, desc->out_edge,
1060 DLTHE_FLAG_UPDATE_FREQ);
1063 /* Create item for switch. */
1064 j = n_peel - i - (extra_zero_check ? 0 : 1);
1065 p = REG_BR_PROB_BASE / (i + 2);
1067 preheader = split_edge (loop_preheader_edge (loop));
1068 branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
1069 block_label (preheader), p,
1072 /* We rely on the fact that the compare and jump cannot be optimized out,
1073 and hence the cfg we create is correct. */
1074 gcc_assert (branch_code != NULL_RTX);
1076 swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
1077 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1078 single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1079 e = make_edge (swtch, preheader,
1080 single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1084 if (extra_zero_check)
1086 /* Add branch for zero iterations. */
1087 p = REG_BR_PROB_BASE / (max_unroll + 1);
1089 preheader = split_edge (loop_preheader_edge (loop));
1090 branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
1091 block_label (preheader), p,
1093 gcc_assert (branch_code != NULL_RTX);
1095 swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
1096 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1097 single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1098 e = make_edge (swtch, preheader,
1099 single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1103 /* Recount dominators for outer blocks. */
1104 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
1106 /* And unroll loop. */
1108 sbitmap_ones (wont_exit);
1109 RESET_BIT (wont_exit, may_exit_copy);
1110 opt_info_start_duplication (opt_info);
1112 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1114 wont_exit, desc->out_edge,
1116 DLTHE_FLAG_UPDATE_FREQ
1118 ? DLTHE_RECORD_COPY_NUMBER
1124 apply_opt_in_copies (opt_info, max_unroll, true, true);
1125 free_opt_info (opt_info);
1132 basic_block exit_block = get_bb_copy (desc->in_edge->src);
1133 /* Find a new in and out edge; they are in the last copy we have
1136 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
1138 desc->out_edge = EDGE_SUCC (exit_block, 0);
1139 desc->in_edge = EDGE_SUCC (exit_block, 1);
1143 desc->out_edge = EDGE_SUCC (exit_block, 1);
1144 desc->in_edge = EDGE_SUCC (exit_block, 0);
1148 /* Remove the edges. */
1149 for (i = 0; VEC_iterate (edge, remove_edges, i, e); i++)
1151 VEC_free (edge, heap, remove_edges);
1153 /* We must be careful when updating the number of iterations due to
1154 preconditioning and the fact that the value must be valid at entry
1155 of the loop. After passing through the above code, we see that
1156 the correct new number of iterations is this: */
1157 gcc_assert (!desc->const_iter);
1159 simplify_gen_binary (UDIV, desc->mode, old_niter,
1160 GEN_INT (max_unroll + 1));
1161 desc->niter_max /= max_unroll + 1;
1165 simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
1166 desc->noloop_assumptions = NULL_RTX;
1172 ";; Unrolled loop %d times, counting # of iterations "
1173 "in runtime, %i insns\n",
1174 max_unroll, num_loop_insns (loop));
1180 /* Decide whether to simply peel LOOP and how much. */
1182 decide_peel_simple (struct loop *loop, int flags)
1185 struct niter_desc *desc;
1187 if (!(flags & UAP_PEEL))
1189 /* We were not asked to, just return back silently. */
1194 fprintf (dump_file, "\n;; Considering simply peeling loop\n");
1196 /* npeel = number of iterations to peel. */
1197 npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
1198 if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES))
1199 npeel = PARAM_VALUE (PARAM_MAX_PEEL_TIMES);
1201 /* Skip big loops. */
1205 fprintf (dump_file, ";; Not considering loop, is too big\n");
1209 /* Check for simple loops. */
1210 desc = get_simple_loop_desc (loop);
1212 /* Check number of iterations. */
1213 if (desc->simple_p && !desc->assumptions && desc->const_iter)
1216 fprintf (dump_file, ";; Loop iterates constant times\n");
1220 /* Do not simply peel loops with branches inside -- it increases number
1222 if (num_loop_branches (loop) > 1)
1225 fprintf (dump_file, ";; Not peeling, contains branches\n");
1229 if (loop->header->count)
1231 unsigned niter = expected_loop_iterations (loop);
1232 if (niter + 1 > npeel)
1236 fprintf (dump_file, ";; Not peeling loop, rolls too much (");
1237 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1238 (HOST_WIDEST_INT) (niter + 1));
1239 fprintf (dump_file, " iterations > %d [maximum peelings])\n",
1248 /* For now we have no good heuristics to decide whether loop peeling
1249 will be effective, so disable it. */
1252 ";; Not peeling loop, no evidence it will be profitable\n");
1257 loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
1258 loop->lpt_decision.times = npeel;
1261 fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
1262 loop->lpt_decision.times);
1265 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1271 if (!cond) goto end;
1273 if (!cond) goto end;
1280 peel_loop_simple (struct loop *loop)
1283 unsigned npeel = loop->lpt_decision.times;
1284 struct niter_desc *desc = get_simple_loop_desc (loop);
1285 struct opt_info *opt_info = NULL;
1288 if (flag_split_ivs_in_unroller && npeel > 1)
1289 opt_info = analyze_insns_in_loop (loop);
1291 wont_exit = sbitmap_alloc (npeel + 1);
1292 sbitmap_zero (wont_exit);
1294 opt_info_start_duplication (opt_info);
1296 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1297 npeel, wont_exit, NULL,
1298 NULL, DLTHE_FLAG_UPDATE_FREQ
1300 ? DLTHE_RECORD_COPY_NUMBER
1308 apply_opt_in_copies (opt_info, npeel, false, false);
1309 free_opt_info (opt_info);
1314 if (desc->const_iter)
1316 desc->niter -= npeel;
1317 desc->niter_expr = GEN_INT (desc->niter);
1318 desc->noloop_assumptions = NULL_RTX;
1322 /* We cannot just update niter_expr, as its value might be clobbered
1323 inside loop. We could handle this by counting the number into
1324 temporary just like we do in runtime unrolling, but it does not
1326 free_simple_loop_desc (loop);
1330 fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
1333 /* Decide whether to unroll LOOP stupidly and how much. */
1335 decide_unroll_stupid (struct loop *loop, int flags)
1337 unsigned nunroll, nunroll_by_av, i;
1338 struct niter_desc *desc;
1340 if (!(flags & UAP_UNROLL_ALL))
1342 /* We were not asked to, just return back silently. */
1347 fprintf (dump_file, "\n;; Considering unrolling loop stupidly\n");
1349 /* nunroll = total number of copies of the original loop body in
1350 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1351 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
1353 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
1354 if (nunroll > nunroll_by_av)
1355 nunroll = nunroll_by_av;
1356 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
1357 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1359 /* Skip big loops. */
1363 fprintf (dump_file, ";; Not considering loop, is too big\n");
1367 /* Check for simple loops. */
1368 desc = get_simple_loop_desc (loop);
1370 /* Check simpleness. */
1371 if (desc->simple_p && !desc->assumptions)
1374 fprintf (dump_file, ";; The loop is simple\n");
1378 /* Do not unroll loops with branches inside -- it increases number
1380 if (num_loop_branches (loop) > 1)
1383 fprintf (dump_file, ";; Not unrolling, contains branches\n");
1387 /* If we have profile feedback, check whether the loop rolls. */
1388 if (loop->header->count
1389 && expected_loop_iterations (loop) < 2 * nunroll)
1392 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1396 /* Success. Now force nunroll to be power of 2, as it seems that this
1397 improves results (partially because of better alignments, partially
1398 because of some dark magic). */
1399 for (i = 1; 2 * i <= nunroll; i *= 2)
1402 loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1403 loop->lpt_decision.times = i - 1;
1407 ";; Decided to unroll the loop stupidly, %d times.\n",
1408 loop->lpt_decision.times);
1411 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1429 unroll_loop_stupid (struct loop *loop)
1432 unsigned nunroll = loop->lpt_decision.times;
1433 struct niter_desc *desc = get_simple_loop_desc (loop);
1434 struct opt_info *opt_info = NULL;
1437 if (flag_split_ivs_in_unroller
1438 || flag_variable_expansion_in_unroller)
1439 opt_info = analyze_insns_in_loop (loop);
1442 wont_exit = sbitmap_alloc (nunroll + 1);
1443 sbitmap_zero (wont_exit);
1444 opt_info_start_duplication (opt_info);
1446 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1449 DLTHE_FLAG_UPDATE_FREQ
1451 ? DLTHE_RECORD_COPY_NUMBER
1457 apply_opt_in_copies (opt_info, nunroll, true, true);
1458 free_opt_info (opt_info);
1465 /* We indeed may get here provided that there are nontrivial assumptions
1466 for a loop to be really simple. We could update the counts, but the
1467 problem is that we are unable to decide which exit will be taken
1468 (not really true in case the number of iterations is constant,
1469 but noone will do anything with this information, so we do not
1471 desc->simple_p = false;
1475 fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1476 nunroll, num_loop_insns (loop));
1479 /* A hash function for information about insns to split. */
1482 si_info_hash (const void *ivts)
1484 return (hashval_t) INSN_UID (((struct iv_to_split *) ivts)->insn);
1487 /* An equality functions for information about insns to split. */
1490 si_info_eq (const void *ivts1, const void *ivts2)
1492 const struct iv_to_split *i1 = ivts1;
1493 const struct iv_to_split *i2 = ivts2;
1495 return i1->insn == i2->insn;
1498 /* Return a hash for VES, which is really a "var_to_expand *". */
1501 ve_info_hash (const void *ves)
1503 return (hashval_t) INSN_UID (((struct var_to_expand *) ves)->insn);
1506 /* Return true if IVTS1 and IVTS2 (which are really both of type
1507 "var_to_expand *") refer to the same instruction. */
1510 ve_info_eq (const void *ivts1, const void *ivts2)
1512 const struct var_to_expand *i1 = ivts1;
1513 const struct var_to_expand *i2 = ivts2;
1515 return i1->insn == i2->insn;
1518 /* Returns true if REG is referenced in one insn in LOOP. */
1521 referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg)
1523 basic_block *body, bb;
1528 body = get_loop_body (loop);
1529 for (i = 0; i < loop->num_nodes; i++)
1533 FOR_BB_INSNS (bb, insn)
1535 if (rtx_referenced_p (reg, insn))
1539 return (count_ref == 1);
1542 /* Determine whether INSN contains an accumulator
1543 which can be expanded into separate copies,
1544 one for each copy of the LOOP body.
1546 for (i = 0 ; i < n; i++)
1560 Return NULL if INSN contains no opportunity for expansion of accumulator.
1561 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1562 information and return a pointer to it.
1565 static struct var_to_expand *
1566 analyze_insn_to_expand_var (struct loop *loop, rtx insn)
1568 rtx set, dest, src, op1;
1569 struct var_to_expand *ves;
1570 enum machine_mode mode1, mode2;
1572 set = single_set (insn);
1576 dest = SET_DEST (set);
1577 src = SET_SRC (set);
1579 if (GET_CODE (src) != PLUS
1580 && GET_CODE (src) != MINUS
1581 && GET_CODE (src) != MULT)
1584 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1585 in MD. But if there is no optab to generate the insn, we can not
1586 perform the variable expansion. This can happen if an MD provides
1587 an insn but not a named pattern to generate it, for example to avoid
1588 producing code that needs additional mode switches like for x87/mmx.
1590 So we check have_insn_for which looks for an optab for the operation
1591 in SRC. If it doesn't exist, we can't perform the expansion even
1592 though INSN is valid. */
1593 if (!have_insn_for (GET_CODE (src), GET_MODE (src)))
1599 op1 = XEXP (src, 0);
1602 && !(GET_CODE (dest) == SUBREG
1603 && REG_P (SUBREG_REG (dest))))
1606 if (!rtx_equal_p (dest, op1))
1609 if (!referenced_in_one_insn_in_loop_p (loop, dest))
1612 if (rtx_referenced_p (dest, XEXP (src, 1)))
1615 mode1 = GET_MODE (dest);
1616 mode2 = GET_MODE (XEXP (src, 1));
1617 if ((FLOAT_MODE_P (mode1)
1618 || FLOAT_MODE_P (mode2))
1619 && !flag_unsafe_math_optimizations)
1625 "\n;; Expanding Accumulator ");
1626 print_rtl (dump_file, dest);
1627 fprintf (dump_file, "\n");
1630 /* Record the accumulator to expand. */
1631 ves = XNEW (struct var_to_expand);
1633 ves->var_expansions = VEC_alloc (rtx, heap, 1);
1634 ves->reg = copy_rtx (dest);
1635 ves->op = GET_CODE (src);
1636 ves->expansion_count = 0;
1637 ves->reuse_expansion = 0;
1641 /* Determine whether there is an induction variable in INSN that
1642 we would like to split during unrolling.
1662 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1663 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1666 static struct iv_to_split *
1667 analyze_iv_to_split_insn (rtx insn)
1671 struct iv_to_split *ivts;
1674 /* For now we just split the basic induction variables. Later this may be
1675 extended for example by selecting also addresses of memory references. */
1676 set = single_set (insn);
1680 dest = SET_DEST (set);
1684 if (!biv_p (insn, dest))
1687 ok = iv_analyze_result (insn, dest, &iv);
1689 /* This used to be an assert under the assumption that if biv_p returns
1690 true that iv_analyze_result must also return true. However, that
1691 assumption is not strictly correct as evidenced by pr25569.
1693 Returning NULL when iv_analyze_result returns false is safe and
1694 avoids the problems in pr25569 until the iv_analyze_* routines
1695 can be fixed, which is apparently hard and time consuming
1696 according to their author. */
1700 if (iv.step == const0_rtx
1701 || iv.mode != iv.extend_mode)
1704 /* Record the insn to split. */
1705 ivts = XNEW (struct iv_to_split);
1707 ivts->base_var = NULL_RTX;
1708 ivts->step = iv.step;
1715 /* Determines which of insns in LOOP can be optimized.
1716 Return a OPT_INFO struct with the relevant hash tables filled
1717 with all insns to be optimized. The FIRST_NEW_BLOCK field
1718 is undefined for the return value. */
1720 static struct opt_info *
1721 analyze_insns_in_loop (struct loop *loop)
1723 basic_block *body, bb;
1725 struct opt_info *opt_info = XCNEW (struct opt_info);
1727 struct iv_to_split *ivts = NULL;
1728 struct var_to_expand *ves = NULL;
1731 VEC (edge, heap) *edges = get_loop_exit_edges (loop);
1733 bool can_apply = false;
1735 iv_analysis_loop_init (loop);
1737 body = get_loop_body (loop);
1739 if (flag_split_ivs_in_unroller)
1740 opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
1741 si_info_hash, si_info_eq, free);
1743 /* Record the loop exit bb and loop preheader before the unrolling. */
1744 opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1746 if (VEC_length (edge, edges) == 1)
1748 exit = VEC_index (edge, edges, 0);
1749 if (!(exit->flags & EDGE_COMPLEX))
1751 opt_info->loop_exit = split_edge (exit);
1756 if (flag_variable_expansion_in_unroller
1758 opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
1759 ve_info_hash, ve_info_eq, free);
1761 for (i = 0; i < loop->num_nodes; i++)
1764 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1767 FOR_BB_INSNS (bb, insn)
1772 if (opt_info->insns_to_split)
1773 ivts = analyze_iv_to_split_insn (insn);
1777 slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT);
1782 if (opt_info->insns_with_var_to_expand)
1783 ves = analyze_insn_to_expand_var (loop, insn);
1787 slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT);
1793 VEC_free (edge, heap, edges);
1798 /* Called just before loop duplication. Records start of duplicated area
1802 opt_info_start_duplication (struct opt_info *opt_info)
1805 opt_info->first_new_block = last_basic_block;
1808 /* Determine the number of iterations between initialization of the base
1809 variable and the current copy (N_COPY). N_COPIES is the total number
1810 of newly created copies. UNROLLING is true if we are unrolling
1811 (not peeling) the loop. */
1814 determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
1818 /* If we are unrolling, initialization is done in the original loop
1824 /* If we are peeling, the copy in that the initialization occurs has
1825 number 1. The original loop (number 0) is the last. */
1833 /* Locate in EXPR the expression corresponding to the location recorded
1834 in IVTS, and return a pointer to the RTX for this location. */
1837 get_ivts_expr (rtx expr, struct iv_to_split *ivts)
1842 for (i = 0; i < ivts->n_loc; i++)
1843 ret = &XEXP (*ret, ivts->loc[i]);
1848 /* Allocate basic variable for the induction variable chain. Callback for
1852 allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1854 struct iv_to_split *ivts = *slot;
1855 rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
1857 ivts->base_var = gen_reg_rtx (GET_MODE (expr));
1862 /* Insert initialization of basic variable of IVTS before INSN, taking
1863 the initial value from INSN. */
1866 insert_base_initialization (struct iv_to_split *ivts, rtx insn)
1868 rtx expr = copy_rtx (*get_ivts_expr (single_set (insn), ivts));
1872 expr = force_operand (expr, ivts->base_var);
1873 if (expr != ivts->base_var)
1874 emit_move_insn (ivts->base_var, expr);
1878 emit_insn_before (seq, insn);
1881 /* Replace the use of induction variable described in IVTS in INSN
1882 by base variable + DELTA * step. */
1885 split_iv (struct iv_to_split *ivts, rtx insn, unsigned delta)
1887 rtx expr, *loc, seq, incr, var;
1888 enum machine_mode mode = GET_MODE (ivts->base_var);
1891 /* Construct base + DELTA * step. */
1893 expr = ivts->base_var;
1896 incr = simplify_gen_binary (MULT, mode,
1897 ivts->step, gen_int_mode (delta, mode));
1898 expr = simplify_gen_binary (PLUS, GET_MODE (ivts->base_var),
1899 ivts->base_var, incr);
1902 /* Figure out where to do the replacement. */
1903 loc = get_ivts_expr (single_set (insn), ivts);
1905 /* If we can make the replacement right away, we're done. */
1906 if (validate_change (insn, loc, expr, 0))
1909 /* Otherwise, force EXPR into a register and try again. */
1911 var = gen_reg_rtx (mode);
1912 expr = force_operand (expr, var);
1914 emit_move_insn (var, expr);
1917 emit_insn_before (seq, insn);
1919 if (validate_change (insn, loc, var, 0))
1922 /* The last chance. Try recreating the assignment in insn
1923 completely from scratch. */
1924 set = single_set (insn);
1929 src = copy_rtx (SET_SRC (set));
1930 dest = copy_rtx (SET_DEST (set));
1931 src = force_operand (src, dest);
1933 emit_move_insn (dest, src);
1937 emit_insn_before (seq, insn);
1942 /* Return one expansion of the accumulator recorded in struct VE. */
1945 get_expansion (struct var_to_expand *ve)
1949 if (ve->reuse_expansion == 0)
1952 reg = VEC_index (rtx, ve->var_expansions, ve->reuse_expansion - 1);
1954 if (VEC_length (rtx, ve->var_expansions) == (unsigned) ve->reuse_expansion)
1955 ve->reuse_expansion = 0;
1957 ve->reuse_expansion++;
1963 /* Given INSN replace the uses of the accumulator recorded in VE
1964 with a new register. */
1967 expand_var_during_unrolling (struct var_to_expand *ve, rtx insn)
1970 bool really_new_expansion = false;
1972 set = single_set (insn);
1975 /* Generate a new register only if the expansion limit has not been
1976 reached. Else reuse an already existing expansion. */
1977 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS) > ve->expansion_count)
1979 really_new_expansion = true;
1980 new_reg = gen_reg_rtx (GET_MODE (ve->reg));
1983 new_reg = get_expansion (ve);
1985 validate_change (insn, &SET_DEST (set), new_reg, 1);
1986 validate_change (insn, &XEXP (SET_SRC (set), 0), new_reg, 1);
1988 if (apply_change_group ())
1989 if (really_new_expansion)
1991 VEC_safe_push (rtx, heap, ve->var_expansions, new_reg);
1992 ve->expansion_count++;
1996 /* Initialize the variable expansions in loop preheader.
1997 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1998 basic block where the initialization of the expansions
1999 should take place. */
2002 insert_var_expansion_initialization (void **slot, void *place_p)
2004 struct var_to_expand *ve = *slot;
2005 basic_block place = (basic_block)place_p;
2006 rtx seq, var, zero_init, insn;
2009 if (VEC_length (rtx, ve->var_expansions) == 0)
2013 if (ve->op == PLUS || ve->op == MINUS)
2014 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2016 zero_init = CONST0_RTX (GET_MODE (var));
2017 emit_move_insn (var, zero_init);
2019 else if (ve->op == MULT)
2020 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2022 zero_init = CONST1_RTX (GET_MODE (var));
2023 emit_move_insn (var, zero_init);
2029 insn = BB_HEAD (place);
2030 while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2031 insn = NEXT_INSN (insn);
2033 emit_insn_after (seq, insn);
2034 /* Continue traversing the hash table. */
2038 /* Combine the variable expansions at the loop exit.
2039 Callbacks for htab_traverse. PLACE_P is the loop exit
2040 basic block where the summation of the expansions should
2044 combine_var_copies_in_loop_exit (void **slot, void *place_p)
2046 struct var_to_expand *ve = *slot;
2047 basic_block place = (basic_block)place_p;
2049 rtx expr, seq, var, insn;
2052 if (VEC_length (rtx, ve->var_expansions) == 0)
2056 if (ve->op == PLUS || ve->op == MINUS)
2057 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2059 sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg),
2062 else if (ve->op == MULT)
2063 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2065 sum = simplify_gen_binary (MULT, GET_MODE (ve->reg),
2069 expr = force_operand (sum, ve->reg);
2070 if (expr != ve->reg)
2071 emit_move_insn (ve->reg, expr);
2075 insn = BB_HEAD (place);
2076 while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2077 insn = NEXT_INSN (insn);
2079 emit_insn_after (seq, insn);
2081 /* Continue traversing the hash table. */
2085 /* Apply loop optimizations in loop copies using the
2086 data which gathered during the unrolling. Structure
2087 OPT_INFO record that data.
2089 UNROLLING is true if we unrolled (not peeled) the loop.
2090 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2091 the loop (as it should happen in complete unrolling, but not in ordinary
2092 peeling of the loop). */
2095 apply_opt_in_copies (struct opt_info *opt_info,
2096 unsigned n_copies, bool unrolling,
2097 bool rewrite_original_loop)
2100 basic_block bb, orig_bb;
2101 rtx insn, orig_insn, next;
2102 struct iv_to_split ivts_templ, *ivts;
2103 struct var_to_expand ve_templ, *ves;
2105 /* Sanity check -- we need to put initialization in the original loop
2107 gcc_assert (!unrolling || rewrite_original_loop);
2109 /* Allocate the basic variables (i0). */
2110 if (opt_info->insns_to_split)
2111 htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL);
2113 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2115 bb = BASIC_BLOCK (i);
2116 orig_bb = get_bb_original (bb);
2118 /* bb->aux holds position in copy sequence initialized by
2119 duplicate_loop_to_header_edge. */
2120 delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
2123 orig_insn = BB_HEAD (orig_bb);
2124 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
2126 next = NEXT_INSN (insn);
2130 while (!INSN_P (orig_insn))
2131 orig_insn = NEXT_INSN (orig_insn);
2133 ivts_templ.insn = orig_insn;
2134 ve_templ.insn = orig_insn;
2136 /* Apply splitting iv optimization. */
2137 if (opt_info->insns_to_split)
2139 ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2143 gcc_assert (GET_CODE (PATTERN (insn))
2144 == GET_CODE (PATTERN (orig_insn)));
2147 insert_base_initialization (ivts, insn);
2148 split_iv (ivts, insn, delta);
2151 /* Apply variable expansion optimization. */
2152 if (unrolling && opt_info->insns_with_var_to_expand)
2154 ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ);
2157 gcc_assert (GET_CODE (PATTERN (insn))
2158 == GET_CODE (PATTERN (orig_insn)));
2159 expand_var_during_unrolling (ves, insn);
2162 orig_insn = NEXT_INSN (orig_insn);
2166 if (!rewrite_original_loop)
2169 /* Initialize the variable expansions in the loop preheader
2170 and take care of combining them at the loop exit. */
2171 if (opt_info->insns_with_var_to_expand)
2173 htab_traverse (opt_info->insns_with_var_to_expand,
2174 insert_var_expansion_initialization,
2175 opt_info->loop_preheader);
2176 htab_traverse (opt_info->insns_with_var_to_expand,
2177 combine_var_copies_in_loop_exit,
2178 opt_info->loop_exit);
2181 /* Rewrite also the original loop body. Find them as originals of the blocks
2182 in the last copied iteration, i.e. those that have
2183 get_bb_copy (get_bb_original (bb)) == bb. */
2184 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2186 bb = BASIC_BLOCK (i);
2187 orig_bb = get_bb_original (bb);
2188 if (get_bb_copy (orig_bb) != bb)
2191 delta = determine_split_iv_delta (0, n_copies, unrolling);
2192 for (orig_insn = BB_HEAD (orig_bb);
2193 orig_insn != NEXT_INSN (BB_END (bb));
2196 next = NEXT_INSN (orig_insn);
2198 if (!INSN_P (orig_insn))
2201 ivts_templ.insn = orig_insn;
2202 if (opt_info->insns_to_split)
2204 ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2208 insert_base_initialization (ivts, orig_insn);
2209 split_iv (ivts, orig_insn, delta);
2218 /* Release the data structures used for the variable expansion
2219 optimization. Callbacks for htab_traverse. */
2222 release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED)
2224 struct var_to_expand *ve = *slot;
2226 VEC_free (rtx, heap, ve->var_expansions);
2228 /* Continue traversing the hash table. */
2232 /* Release OPT_INFO. */
2235 free_opt_info (struct opt_info *opt_info)
2237 if (opt_info->insns_to_split)
2238 htab_delete (opt_info->insns_to_split);
2239 if (opt_info->insns_with_var_to_expand)
2241 htab_traverse (opt_info->insns_with_var_to_expand,
2242 release_var_copies, NULL);
2243 htab_delete (opt_info->insns_with_var_to_expand);