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 (struct loops *, int);
118 static void peel_loops_completely (struct loops *, 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 loops *, struct loop *);
126 static void peel_loop_completely (struct loops *, struct loop *);
127 static void unroll_loop_stupid (struct loops *, struct loop *);
128 static void unroll_loop_constant_iterations (struct loops *, struct loop *);
129 static void unroll_loop_runtime_iterations (struct loops *, 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 (struct loops *loops, int flags)
147 struct loop *loop, *next;
150 /* First perform complete loop peeling (it is almost surely a win,
151 and affects parameters for further decision a lot). */
152 peel_loops_completely (loops, flags);
154 /* Now decide rest of unrolling and peeling. */
155 decide_unrolling_and_peeling (loops, flags);
157 loop = loops->tree_root;
161 /* Scan the loops, inner ones first. */
162 while (loop != loops->tree_root)
174 /* And perform the appropriate transformations. */
175 switch (loop->lpt_decision.decision)
177 case LPT_PEEL_COMPLETELY:
180 case LPT_PEEL_SIMPLE:
181 peel_loop_simple (loops, loop);
183 case LPT_UNROLL_CONSTANT:
184 unroll_loop_constant_iterations (loops, loop);
186 case LPT_UNROLL_RUNTIME:
187 unroll_loop_runtime_iterations (loops, loop);
189 case LPT_UNROLL_STUPID:
190 unroll_loop_stupid (loops, loop);
200 #ifdef ENABLE_CHECKING
201 verify_dominators (CDI_DOMINATORS);
202 verify_loop_structure (loops);
211 /* Check whether exit of the LOOP is at the end of loop body. */
214 loop_exit_at_end_p (struct loop *loop)
216 struct niter_desc *desc = get_simple_loop_desc (loop);
219 if (desc->in_edge->dest != loop->latch)
222 /* Check that the latch is empty. */
223 FOR_BB_INSNS (loop->latch, insn)
232 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
234 peel_loops_completely (struct loops *loops, int flags)
239 /* Scan the loops, the inner ones first. */
240 for (i = loops->num - 1; i > 0; i--)
242 loop = loops->parray[i];
246 loop->lpt_decision.decision = LPT_NONE;
250 "\n;; *** Considering loop %d for complete peeling ***\n",
253 loop->ninsns = num_loop_insns (loop);
255 decide_peel_once_rolling (loop, flags);
256 if (loop->lpt_decision.decision == LPT_NONE)
257 decide_peel_completely (loop, flags);
259 if (loop->lpt_decision.decision == LPT_PEEL_COMPLETELY)
261 peel_loop_completely (loops, loop);
262 #ifdef ENABLE_CHECKING
263 verify_dominators (CDI_DOMINATORS);
264 verify_loop_structure (loops);
270 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
272 decide_unrolling_and_peeling (struct loops *loops, int flags)
274 struct loop *loop = loops->tree_root, *next;
279 /* Scan the loops, inner ones first. */
280 while (loop != loops->tree_root)
291 loop->lpt_decision.decision = LPT_NONE;
294 fprintf (dump_file, "\n;; *** Considering loop %d ***\n", loop->num);
296 /* Do not peel cold areas. */
297 if (!maybe_hot_bb_p (loop->header))
300 fprintf (dump_file, ";; Not considering loop, cold area\n");
305 /* Can the loop be manipulated? */
306 if (!can_duplicate_loop_p (loop))
310 ";; Not considering loop, cannot duplicate\n");
315 /* Skip non-innermost loops. */
319 fprintf (dump_file, ";; Not considering loop, is not innermost\n");
324 loop->ninsns = num_loop_insns (loop);
325 loop->av_ninsns = average_num_loop_insns (loop);
327 /* Try transformations one by one in decreasing order of
330 decide_unroll_constant_iterations (loop, flags);
331 if (loop->lpt_decision.decision == LPT_NONE)
332 decide_unroll_runtime_iterations (loop, flags);
333 if (loop->lpt_decision.decision == LPT_NONE)
334 decide_unroll_stupid (loop, flags);
335 if (loop->lpt_decision.decision == LPT_NONE)
336 decide_peel_simple (loop, flags);
342 /* Decide whether the LOOP is once rolling and suitable for complete
345 decide_peel_once_rolling (struct loop *loop, int flags ATTRIBUTE_UNUSED)
347 struct niter_desc *desc;
350 fprintf (dump_file, "\n;; Considering peeling once rolling loop\n");
352 /* Is the loop small enough? */
353 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS) < loop->ninsns)
356 fprintf (dump_file, ";; Not considering loop, is too big\n");
360 /* Check for simple loops. */
361 desc = get_simple_loop_desc (loop);
363 /* Check number of iterations. */
372 ";; Unable to prove that the loop rolls exactly once\n");
378 fprintf (dump_file, ";; Decided to peel exactly once rolling loop\n");
379 loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
382 /* Decide whether the LOOP is suitable for complete peeling. */
384 decide_peel_completely (struct loop *loop, int flags ATTRIBUTE_UNUSED)
387 struct niter_desc *desc;
390 fprintf (dump_file, "\n;; Considering peeling completely\n");
392 /* Skip non-innermost loops. */
396 fprintf (dump_file, ";; Not considering loop, is not innermost\n");
400 /* Do not peel cold areas. */
401 if (!maybe_hot_bb_p (loop->header))
404 fprintf (dump_file, ";; Not considering loop, cold area\n");
408 /* Can the loop be manipulated? */
409 if (!can_duplicate_loop_p (loop))
413 ";; Not considering loop, cannot duplicate\n");
417 /* npeel = number of iterations to peel. */
418 npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS) / loop->ninsns;
419 if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES))
420 npeel = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
422 /* Is the loop small enough? */
426 fprintf (dump_file, ";; Not considering loop, is too big\n");
430 /* Check for simple loops. */
431 desc = get_simple_loop_desc (loop);
433 /* Check number of iterations. */
441 ";; Unable to prove that the loop iterates constant times\n");
445 if (desc->niter > npeel - 1)
450 ";; Not peeling loop completely, rolls too much (");
451 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
452 fprintf (dump_file, " iterations > %d [maximum peelings])\n", npeel);
459 fprintf (dump_file, ";; Decided to peel loop completely\n");
460 loop->lpt_decision.decision = LPT_PEEL_COMPLETELY;
463 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
464 completely. The transformation done:
466 for (i = 0; i < 4; i++)
478 peel_loop_completely (struct loops *loops, struct loop *loop)
481 unsigned HOST_WIDE_INT npeel;
482 unsigned n_remove_edges, i;
483 edge *remove_edges, ein;
484 struct niter_desc *desc = get_simple_loop_desc (loop);
485 struct opt_info *opt_info = NULL;
493 wont_exit = sbitmap_alloc (npeel + 1);
494 sbitmap_ones (wont_exit);
495 RESET_BIT (wont_exit, 0);
496 if (desc->noloop_assumptions)
497 RESET_BIT (wont_exit, 1);
499 remove_edges = XCNEWVEC (edge, npeel);
502 if (flag_split_ivs_in_unroller)
503 opt_info = analyze_insns_in_loop (loop);
505 opt_info_start_duplication (opt_info);
506 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
508 wont_exit, desc->out_edge,
509 remove_edges, &n_remove_edges,
510 DLTHE_FLAG_UPDATE_FREQ
511 | DLTHE_FLAG_COMPLETTE_PEEL
513 ? DLTHE_RECORD_COPY_NUMBER : 0));
520 apply_opt_in_copies (opt_info, npeel, false, true);
521 free_opt_info (opt_info);
524 /* Remove the exit edges. */
525 for (i = 0; i < n_remove_edges; i++)
526 remove_path (loops, remove_edges[i]);
531 free_simple_loop_desc (loop);
533 /* Now remove the unreachable part of the last iteration and cancel
535 remove_path (loops, ein);
538 fprintf (dump_file, ";; Peeled loop completely, %d times\n", (int) npeel);
541 /* Decide whether to unroll LOOP iterating constant number of times
545 decide_unroll_constant_iterations (struct loop *loop, int flags)
547 unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
548 struct niter_desc *desc;
550 if (!(flags & UAP_UNROLL))
552 /* We were not asked to, just return back silently. */
558 "\n;; Considering unrolling loop with constant "
559 "number of iterations\n");
561 /* nunroll = total number of copies of the original loop body in
562 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
563 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
565 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
566 if (nunroll > nunroll_by_av)
567 nunroll = nunroll_by_av;
568 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
569 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
571 /* Skip big loops. */
575 fprintf (dump_file, ";; Not considering loop, is too big\n");
579 /* Check for simple loops. */
580 desc = get_simple_loop_desc (loop);
582 /* Check number of iterations. */
583 if (!desc->simple_p || !desc->const_iter || desc->assumptions)
587 ";; Unable to prove that the loop iterates constant times\n");
591 /* Check whether the loop rolls enough to consider. */
592 if (desc->niter < 2 * nunroll)
595 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
599 /* Success; now compute number of iterations to unroll. We alter
600 nunroll so that as few as possible copies of loop body are
601 necessary, while still not decreasing the number of unrollings
602 too much (at most by 1). */
603 best_copies = 2 * nunroll + 10;
606 if (i - 1 >= desc->niter)
609 for (; i >= nunroll - 1; i--)
611 unsigned exit_mod = desc->niter % (i + 1);
613 if (!loop_exit_at_end_p (loop))
614 n_copies = exit_mod + i + 1;
615 else if (exit_mod != (unsigned) i
616 || desc->noloop_assumptions != NULL_RTX)
617 n_copies = exit_mod + i + 2;
621 if (n_copies < best_copies)
623 best_copies = n_copies;
629 fprintf (dump_file, ";; max_unroll %d (%d copies, initial %d).\n",
630 best_unroll + 1, best_copies, nunroll);
632 loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
633 loop->lpt_decision.times = best_unroll;
637 ";; Decided to unroll the constant times rolling loop, %d times.\n",
638 loop->lpt_decision.times);
641 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
642 times. The transformation does this:
644 for (i = 0; i < 102; i++)
661 unroll_loop_constant_iterations (struct loops *loops, struct loop *loop)
663 unsigned HOST_WIDE_INT niter;
666 unsigned n_remove_edges, i;
668 unsigned max_unroll = loop->lpt_decision.times;
669 struct niter_desc *desc = get_simple_loop_desc (loop);
670 bool exit_at_end = loop_exit_at_end_p (loop);
671 struct opt_info *opt_info = NULL;
676 /* Should not get here (such loop should be peeled instead). */
677 gcc_assert (niter > max_unroll + 1);
679 exit_mod = niter % (max_unroll + 1);
681 wont_exit = sbitmap_alloc (max_unroll + 1);
682 sbitmap_ones (wont_exit);
684 remove_edges = XCNEWVEC (edge, max_unroll + exit_mod + 1);
686 if (flag_split_ivs_in_unroller
687 || flag_variable_expansion_in_unroller)
688 opt_info = analyze_insns_in_loop (loop);
692 /* The exit is not at the end of the loop; leave exit test
693 in the first copy, so that the loops that start with test
694 of exit condition have continuous body after unrolling. */
697 fprintf (dump_file, ";; Condition on beginning of loop.\n");
699 /* Peel exit_mod iterations. */
700 RESET_BIT (wont_exit, 0);
701 if (desc->noloop_assumptions)
702 RESET_BIT (wont_exit, 1);
706 opt_info_start_duplication (opt_info);
707 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
709 wont_exit, desc->out_edge,
710 remove_edges, &n_remove_edges,
711 DLTHE_FLAG_UPDATE_FREQ
712 | (opt_info && exit_mod > 1
713 ? DLTHE_RECORD_COPY_NUMBER
717 if (opt_info && exit_mod > 1)
718 apply_opt_in_copies (opt_info, exit_mod, false, false);
720 desc->noloop_assumptions = NULL_RTX;
721 desc->niter -= exit_mod;
722 desc->niter_max -= exit_mod;
725 SET_BIT (wont_exit, 1);
729 /* Leave exit test in last copy, for the same reason as above if
730 the loop tests the condition at the end of loop body. */
733 fprintf (dump_file, ";; Condition on end of loop.\n");
735 /* We know that niter >= max_unroll + 2; so we do not need to care of
736 case when we would exit before reaching the loop. So just peel
737 exit_mod + 1 iterations. */
738 if (exit_mod != max_unroll
739 || desc->noloop_assumptions)
741 RESET_BIT (wont_exit, 0);
742 if (desc->noloop_assumptions)
743 RESET_BIT (wont_exit, 1);
745 opt_info_start_duplication (opt_info);
746 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
748 wont_exit, desc->out_edge,
749 remove_edges, &n_remove_edges,
750 DLTHE_FLAG_UPDATE_FREQ
751 | (opt_info && exit_mod > 0
752 ? DLTHE_RECORD_COPY_NUMBER
756 if (opt_info && exit_mod > 0)
757 apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
759 desc->niter -= exit_mod + 1;
760 desc->niter_max -= exit_mod + 1;
761 desc->noloop_assumptions = NULL_RTX;
763 SET_BIT (wont_exit, 0);
764 SET_BIT (wont_exit, 1);
767 RESET_BIT (wont_exit, max_unroll);
770 /* Now unroll the loop. */
772 opt_info_start_duplication (opt_info);
773 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
775 wont_exit, desc->out_edge,
776 remove_edges, &n_remove_edges,
777 DLTHE_FLAG_UPDATE_FREQ
779 ? DLTHE_RECORD_COPY_NUMBER
785 apply_opt_in_copies (opt_info, max_unroll, true, true);
786 free_opt_info (opt_info);
793 basic_block exit_block = get_bb_copy (desc->in_edge->src);
794 /* Find a new in and out edge; they are in the last copy we have made. */
796 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
798 desc->out_edge = EDGE_SUCC (exit_block, 0);
799 desc->in_edge = EDGE_SUCC (exit_block, 1);
803 desc->out_edge = EDGE_SUCC (exit_block, 1);
804 desc->in_edge = EDGE_SUCC (exit_block, 0);
808 desc->niter /= max_unroll + 1;
809 desc->niter_max /= max_unroll + 1;
810 desc->niter_expr = GEN_INT (desc->niter);
812 /* Remove the edges. */
813 for (i = 0; i < n_remove_edges; i++)
814 remove_path (loops, remove_edges[i]);
819 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
820 max_unroll, num_loop_insns (loop));
823 /* Decide whether to unroll LOOP iterating runtime computable number of times
826 decide_unroll_runtime_iterations (struct loop *loop, int flags)
828 unsigned nunroll, nunroll_by_av, i;
829 struct niter_desc *desc;
831 if (!(flags & UAP_UNROLL))
833 /* We were not asked to, just return back silently. */
839 "\n;; Considering unrolling loop with runtime "
840 "computable number of iterations\n");
842 /* nunroll = total number of copies of the original loop body in
843 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
844 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
845 nunroll_by_av = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
846 if (nunroll > nunroll_by_av)
847 nunroll = nunroll_by_av;
848 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
849 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
851 /* Skip big loops. */
855 fprintf (dump_file, ";; Not considering loop, is too big\n");
859 /* Check for simple loops. */
860 desc = get_simple_loop_desc (loop);
862 /* Check simpleness. */
863 if (!desc->simple_p || desc->assumptions)
867 ";; Unable to prove that the number of iterations "
868 "can be counted in runtime\n");
872 if (desc->const_iter)
875 fprintf (dump_file, ";; Loop iterates constant times\n");
879 /* If we have profile feedback, check whether the loop rolls. */
880 if (loop->header->count && expected_loop_iterations (loop) < 2 * nunroll)
883 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
887 /* Success; now force nunroll to be power of 2, as we are unable to
888 cope with overflows in computation of number of iterations. */
889 for (i = 1; 2 * i <= nunroll; i *= 2)
892 loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
893 loop->lpt_decision.times = i - 1;
897 ";; Decided to unroll the runtime computable "
898 "times rolling loop, %d times.\n",
899 loop->lpt_decision.times);
902 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
903 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
904 and NULL is returned instead. */
907 split_edge_and_insert (edge e, rtx insns)
914 emit_insn_after (insns, BB_END (bb));
915 bb->flags |= BB_SUPERBLOCK;
919 /* Unroll LOOP for that we are able to count number of iterations in runtime
920 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
921 extra care for case n < 0):
923 for (i = 0; i < n; i++)
951 unroll_loop_runtime_iterations (struct loops *loops, struct loop *loop)
953 rtx old_niter, niter, init_code, branch_code, tmp;
955 basic_block preheader, *body, *dom_bbs, swtch, ezc_swtch;
959 unsigned n_peel, n_remove_edges;
960 edge *remove_edges, e;
961 bool extra_zero_check, last_may_exit;
962 unsigned max_unroll = loop->lpt_decision.times;
963 struct niter_desc *desc = get_simple_loop_desc (loop);
964 bool exit_at_end = loop_exit_at_end_p (loop);
965 struct opt_info *opt_info = NULL;
968 if (flag_split_ivs_in_unroller
969 || flag_variable_expansion_in_unroller)
970 opt_info = analyze_insns_in_loop (loop);
972 /* Remember blocks whose dominators will have to be updated. */
973 dom_bbs = XCNEWVEC (basic_block, n_basic_blocks);
976 body = get_loop_body (loop);
977 for (i = 0; i < loop->num_nodes; i++)
982 nldom = get_dominated_by (CDI_DOMINATORS, body[i], &ldom);
983 for (j = 0; j < nldom; j++)
984 if (!flow_bb_inside_loop_p (loop, ldom[j]))
985 dom_bbs[n_dom_bbs++] = ldom[j];
993 /* Leave exit in first copy (for explanation why see comment in
994 unroll_loop_constant_iterations). */
996 n_peel = max_unroll - 1;
997 extra_zero_check = true;
998 last_may_exit = false;
1002 /* Leave exit in last copy (for explanation why see comment in
1003 unroll_loop_constant_iterations). */
1004 may_exit_copy = max_unroll;
1005 n_peel = max_unroll;
1006 extra_zero_check = false;
1007 last_may_exit = true;
1010 /* Get expression for number of iterations. */
1012 old_niter = niter = gen_reg_rtx (desc->mode);
1013 tmp = force_operand (copy_rtx (desc->niter_expr), niter);
1015 emit_move_insn (niter, tmp);
1017 /* Count modulo by ANDing it with max_unroll; we use the fact that
1018 the number of unrollings is a power of two, and thus this is correct
1019 even if there is overflow in the computation. */
1020 niter = expand_simple_binop (desc->mode, AND,
1022 GEN_INT (max_unroll),
1023 NULL_RTX, 0, OPTAB_LIB_WIDEN);
1025 init_code = get_insns ();
1028 /* Precondition the loop. */
1029 split_edge_and_insert (loop_preheader_edge (loop), init_code);
1031 remove_edges = XCNEWVEC (edge, max_unroll + n_peel + 1);
1034 wont_exit = sbitmap_alloc (max_unroll + 2);
1036 /* Peel the first copy of loop body (almost always we must leave exit test
1037 here; the only exception is when we have extra zero check and the number
1038 of iterations is reliable. Also record the place of (possible) extra
1040 sbitmap_zero (wont_exit);
1041 if (extra_zero_check
1042 && !desc->noloop_assumptions)
1043 SET_BIT (wont_exit, 1);
1044 ezc_swtch = loop_preheader_edge (loop)->src;
1045 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1047 wont_exit, desc->out_edge,
1048 remove_edges, &n_remove_edges,
1049 DLTHE_FLAG_UPDATE_FREQ);
1052 /* Record the place where switch will be built for preconditioning. */
1053 swtch = split_edge (loop_preheader_edge (loop));
1055 for (i = 0; i < n_peel; i++)
1057 /* Peel the copy. */
1058 sbitmap_zero (wont_exit);
1059 if (i != n_peel - 1 || !last_may_exit)
1060 SET_BIT (wont_exit, 1);
1061 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1063 wont_exit, desc->out_edge,
1064 remove_edges, &n_remove_edges,
1065 DLTHE_FLAG_UPDATE_FREQ);
1068 /* Create item for switch. */
1069 j = n_peel - i - (extra_zero_check ? 0 : 1);
1070 p = REG_BR_PROB_BASE / (i + 2);
1072 preheader = split_edge (loop_preheader_edge (loop));
1073 branch_code = compare_and_jump_seq (copy_rtx (niter), GEN_INT (j), EQ,
1074 block_label (preheader), p,
1077 /* We rely on the fact that the compare and jump cannot be optimized out,
1078 and hence the cfg we create is correct. */
1079 gcc_assert (branch_code != NULL_RTX);
1081 swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
1082 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1083 single_pred_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1084 e = make_edge (swtch, preheader,
1085 single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1089 if (extra_zero_check)
1091 /* Add branch for zero iterations. */
1092 p = REG_BR_PROB_BASE / (max_unroll + 1);
1094 preheader = split_edge (loop_preheader_edge (loop));
1095 branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
1096 block_label (preheader), p,
1098 gcc_assert (branch_code != NULL_RTX);
1100 swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
1101 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1102 single_succ_edge (swtch)->probability = REG_BR_PROB_BASE - p;
1103 e = make_edge (swtch, preheader,
1104 single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1108 /* Recount dominators for outer blocks. */
1109 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, n_dom_bbs);
1111 /* And unroll loop. */
1113 sbitmap_ones (wont_exit);
1114 RESET_BIT (wont_exit, may_exit_copy);
1115 opt_info_start_duplication (opt_info);
1117 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1119 wont_exit, desc->out_edge,
1120 remove_edges, &n_remove_edges,
1121 DLTHE_FLAG_UPDATE_FREQ
1123 ? DLTHE_RECORD_COPY_NUMBER
1129 apply_opt_in_copies (opt_info, max_unroll, true, true);
1130 free_opt_info (opt_info);
1137 basic_block exit_block = get_bb_copy (desc->in_edge->src);
1138 /* Find a new in and out edge; they are in the last copy we have
1141 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
1143 desc->out_edge = EDGE_SUCC (exit_block, 0);
1144 desc->in_edge = EDGE_SUCC (exit_block, 1);
1148 desc->out_edge = EDGE_SUCC (exit_block, 1);
1149 desc->in_edge = EDGE_SUCC (exit_block, 0);
1153 /* Remove the edges. */
1154 for (i = 0; i < n_remove_edges; i++)
1155 remove_path (loops, remove_edges[i]);
1156 free (remove_edges);
1158 /* We must be careful when updating the number of iterations due to
1159 preconditioning and the fact that the value must be valid at entry
1160 of the loop. After passing through the above code, we see that
1161 the correct new number of iterations is this: */
1162 gcc_assert (!desc->const_iter);
1164 simplify_gen_binary (UDIV, desc->mode, old_niter,
1165 GEN_INT (max_unroll + 1));
1166 desc->niter_max /= max_unroll + 1;
1170 simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
1171 desc->noloop_assumptions = NULL_RTX;
1177 ";; Unrolled loop %d times, counting # of iterations "
1178 "in runtime, %i insns\n",
1179 max_unroll, num_loop_insns (loop));
1185 /* Decide whether to simply peel LOOP and how much. */
1187 decide_peel_simple (struct loop *loop, int flags)
1190 struct niter_desc *desc;
1192 if (!(flags & UAP_PEEL))
1194 /* We were not asked to, just return back silently. */
1199 fprintf (dump_file, "\n;; Considering simply peeling loop\n");
1201 /* npeel = number of iterations to peel. */
1202 npeel = PARAM_VALUE (PARAM_MAX_PEELED_INSNS) / loop->ninsns;
1203 if (npeel > (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES))
1204 npeel = PARAM_VALUE (PARAM_MAX_PEEL_TIMES);
1206 /* Skip big loops. */
1210 fprintf (dump_file, ";; Not considering loop, is too big\n");
1214 /* Check for simple loops. */
1215 desc = get_simple_loop_desc (loop);
1217 /* Check number of iterations. */
1218 if (desc->simple_p && !desc->assumptions && desc->const_iter)
1221 fprintf (dump_file, ";; Loop iterates constant times\n");
1225 /* Do not simply peel loops with branches inside -- it increases number
1227 if (num_loop_branches (loop) > 1)
1230 fprintf (dump_file, ";; Not peeling, contains branches\n");
1234 if (loop->header->count)
1236 unsigned niter = expected_loop_iterations (loop);
1237 if (niter + 1 > npeel)
1241 fprintf (dump_file, ";; Not peeling loop, rolls too much (");
1242 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC,
1243 (HOST_WIDEST_INT) (niter + 1));
1244 fprintf (dump_file, " iterations > %d [maximum peelings])\n",
1253 /* For now we have no good heuristics to decide whether loop peeling
1254 will be effective, so disable it. */
1257 ";; Not peeling loop, no evidence it will be profitable\n");
1262 loop->lpt_decision.decision = LPT_PEEL_SIMPLE;
1263 loop->lpt_decision.times = npeel;
1266 fprintf (dump_file, ";; Decided to simply peel the loop, %d times.\n",
1267 loop->lpt_decision.times);
1270 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1276 if (!cond) goto end;
1278 if (!cond) goto end;
1285 peel_loop_simple (struct loops *loops, struct loop *loop)
1288 unsigned npeel = loop->lpt_decision.times;
1289 struct niter_desc *desc = get_simple_loop_desc (loop);
1290 struct opt_info *opt_info = NULL;
1293 if (flag_split_ivs_in_unroller && npeel > 1)
1294 opt_info = analyze_insns_in_loop (loop);
1296 wont_exit = sbitmap_alloc (npeel + 1);
1297 sbitmap_zero (wont_exit);
1299 opt_info_start_duplication (opt_info);
1301 ok = duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
1302 loops, npeel, wont_exit,
1304 NULL, DLTHE_FLAG_UPDATE_FREQ
1306 ? DLTHE_RECORD_COPY_NUMBER
1314 apply_opt_in_copies (opt_info, npeel, false, false);
1315 free_opt_info (opt_info);
1320 if (desc->const_iter)
1322 desc->niter -= npeel;
1323 desc->niter_expr = GEN_INT (desc->niter);
1324 desc->noloop_assumptions = NULL_RTX;
1328 /* We cannot just update niter_expr, as its value might be clobbered
1329 inside loop. We could handle this by counting the number into
1330 temporary just like we do in runtime unrolling, but it does not
1332 free_simple_loop_desc (loop);
1336 fprintf (dump_file, ";; Peeling loop %d times\n", npeel);
1339 /* Decide whether to unroll LOOP stupidly and how much. */
1341 decide_unroll_stupid (struct loop *loop, int flags)
1343 unsigned nunroll, nunroll_by_av, i;
1344 struct niter_desc *desc;
1346 if (!(flags & UAP_UNROLL_ALL))
1348 /* We were not asked to, just return back silently. */
1353 fprintf (dump_file, "\n;; Considering unrolling loop stupidly\n");
1355 /* nunroll = total number of copies of the original loop body in
1356 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1357 nunroll = PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS) / loop->ninsns;
1359 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS) / loop->av_ninsns;
1360 if (nunroll > nunroll_by_av)
1361 nunroll = nunroll_by_av;
1362 if (nunroll > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES))
1363 nunroll = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1365 /* Skip big loops. */
1369 fprintf (dump_file, ";; Not considering loop, is too big\n");
1373 /* Check for simple loops. */
1374 desc = get_simple_loop_desc (loop);
1376 /* Check simpleness. */
1377 if (desc->simple_p && !desc->assumptions)
1380 fprintf (dump_file, ";; The loop is simple\n");
1384 /* Do not unroll loops with branches inside -- it increases number
1386 if (num_loop_branches (loop) > 1)
1389 fprintf (dump_file, ";; Not unrolling, contains branches\n");
1393 /* If we have profile feedback, check whether the loop rolls. */
1394 if (loop->header->count
1395 && expected_loop_iterations (loop) < 2 * nunroll)
1398 fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1402 /* Success. Now force nunroll to be power of 2, as it seems that this
1403 improves results (partially because of better alignments, partially
1404 because of some dark magic). */
1405 for (i = 1; 2 * i <= nunroll; i *= 2)
1408 loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1409 loop->lpt_decision.times = i - 1;
1413 ";; Decided to unroll the loop stupidly, %d times.\n",
1414 loop->lpt_decision.times);
1417 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1435 unroll_loop_stupid (struct loops *loops, struct loop *loop)
1438 unsigned nunroll = loop->lpt_decision.times;
1439 struct niter_desc *desc = get_simple_loop_desc (loop);
1440 struct opt_info *opt_info = NULL;
1443 if (flag_split_ivs_in_unroller
1444 || flag_variable_expansion_in_unroller)
1445 opt_info = analyze_insns_in_loop (loop);
1448 wont_exit = sbitmap_alloc (nunroll + 1);
1449 sbitmap_zero (wont_exit);
1450 opt_info_start_duplication (opt_info);
1452 ok = duplicate_loop_to_header_edge (loop, loop_latch_edge (loop),
1453 loops, nunroll, wont_exit,
1455 DLTHE_FLAG_UPDATE_FREQ
1457 ? DLTHE_RECORD_COPY_NUMBER
1463 apply_opt_in_copies (opt_info, nunroll, true, true);
1464 free_opt_info (opt_info);
1471 /* We indeed may get here provided that there are nontrivial assumptions
1472 for a loop to be really simple. We could update the counts, but the
1473 problem is that we are unable to decide which exit will be taken
1474 (not really true in case the number of iterations is constant,
1475 but noone will do anything with this information, so we do not
1477 desc->simple_p = false;
1481 fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1482 nunroll, num_loop_insns (loop));
1485 /* A hash function for information about insns to split. */
1488 si_info_hash (const void *ivts)
1490 return (hashval_t) INSN_UID (((struct iv_to_split *) ivts)->insn);
1493 /* An equality functions for information about insns to split. */
1496 si_info_eq (const void *ivts1, const void *ivts2)
1498 const struct iv_to_split *i1 = ivts1;
1499 const struct iv_to_split *i2 = ivts2;
1501 return i1->insn == i2->insn;
1504 /* Return a hash for VES, which is really a "var_to_expand *". */
1507 ve_info_hash (const void *ves)
1509 return (hashval_t) INSN_UID (((struct var_to_expand *) ves)->insn);
1512 /* Return true if IVTS1 and IVTS2 (which are really both of type
1513 "var_to_expand *") refer to the same instruction. */
1516 ve_info_eq (const void *ivts1, const void *ivts2)
1518 const struct var_to_expand *i1 = ivts1;
1519 const struct var_to_expand *i2 = ivts2;
1521 return i1->insn == i2->insn;
1524 /* Returns true if REG is referenced in one insn in LOOP. */
1527 referenced_in_one_insn_in_loop_p (struct loop *loop, rtx reg)
1529 basic_block *body, bb;
1534 body = get_loop_body (loop);
1535 for (i = 0; i < loop->num_nodes; i++)
1539 FOR_BB_INSNS (bb, insn)
1541 if (rtx_referenced_p (reg, insn))
1545 return (count_ref == 1);
1548 /* Determine whether INSN contains an accumulator
1549 which can be expanded into separate copies,
1550 one for each copy of the LOOP body.
1552 for (i = 0 ; i < n; i++)
1566 Return NULL if INSN contains no opportunity for expansion of accumulator.
1567 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1568 information and return a pointer to it.
1571 static struct var_to_expand *
1572 analyze_insn_to_expand_var (struct loop *loop, rtx insn)
1574 rtx set, dest, src, op1;
1575 struct var_to_expand *ves;
1576 enum machine_mode mode1, mode2;
1578 set = single_set (insn);
1582 dest = SET_DEST (set);
1583 src = SET_SRC (set);
1585 if (GET_CODE (src) != PLUS
1586 && GET_CODE (src) != MINUS
1587 && GET_CODE (src) != MULT)
1590 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1591 in MD. But if there is no optab to generate the insn, we can not
1592 perform the variable expansion. This can happen if an MD provides
1593 an insn but not a named pattern to generate it, for example to avoid
1594 producing code that needs additional mode switches like for x87/mmx.
1596 So we check have_insn_for which looks for an optab for the operation
1597 in SRC. If it doesn't exist, we can't perform the expansion even
1598 though INSN is valid. */
1599 if (!have_insn_for (GET_CODE (src), GET_MODE (src)))
1605 op1 = XEXP (src, 0);
1608 && !(GET_CODE (dest) == SUBREG
1609 && REG_P (SUBREG_REG (dest))))
1612 if (!rtx_equal_p (dest, op1))
1615 if (!referenced_in_one_insn_in_loop_p (loop, dest))
1618 if (rtx_referenced_p (dest, XEXP (src, 1)))
1621 mode1 = GET_MODE (dest);
1622 mode2 = GET_MODE (XEXP (src, 1));
1623 if ((FLOAT_MODE_P (mode1)
1624 || FLOAT_MODE_P (mode2))
1625 && !flag_unsafe_math_optimizations)
1628 /* Record the accumulator to expand. */
1629 ves = XNEW (struct var_to_expand);
1631 ves->var_expansions = VEC_alloc (rtx, heap, 1);
1632 ves->reg = copy_rtx (dest);
1633 ves->op = GET_CODE (src);
1634 ves->expansion_count = 0;
1635 ves->reuse_expansion = 0;
1639 /* Determine whether there is an induction variable in INSN that
1640 we would like to split during unrolling.
1660 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1661 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1664 static struct iv_to_split *
1665 analyze_iv_to_split_insn (rtx insn)
1669 struct iv_to_split *ivts;
1672 /* For now we just split the basic induction variables. Later this may be
1673 extended for example by selecting also addresses of memory references. */
1674 set = single_set (insn);
1678 dest = SET_DEST (set);
1682 if (!biv_p (insn, dest))
1685 ok = iv_analyze_result (insn, dest, &iv);
1687 /* This used to be an assert under the assumption that if biv_p returns
1688 true that iv_analyze_result must also return true. However, that
1689 assumption is not strictly correct as evidenced by pr25569.
1691 Returning NULL when iv_analyze_result returns false is safe and
1692 avoids the problems in pr25569 until the iv_analyze_* routines
1693 can be fixed, which is apparently hard and time consuming
1694 according to their author. */
1698 if (iv.step == const0_rtx
1699 || iv.mode != iv.extend_mode)
1702 /* Record the insn to split. */
1703 ivts = XNEW (struct iv_to_split);
1705 ivts->base_var = NULL_RTX;
1706 ivts->step = iv.step;
1713 /* Determines which of insns in LOOP can be optimized.
1714 Return a OPT_INFO struct with the relevant hash tables filled
1715 with all insns to be optimized. The FIRST_NEW_BLOCK field
1716 is undefined for the return value. */
1718 static struct opt_info *
1719 analyze_insns_in_loop (struct loop *loop)
1721 basic_block *body, bb;
1723 struct opt_info *opt_info = XCNEW (struct opt_info);
1725 struct iv_to_split *ivts = NULL;
1726 struct var_to_expand *ves = NULL;
1729 VEC (edge, heap) *edges = get_loop_exit_edges (loop);
1731 bool can_apply = false;
1733 iv_analysis_loop_init (loop);
1735 body = get_loop_body (loop);
1737 if (flag_split_ivs_in_unroller)
1738 opt_info->insns_to_split = htab_create (5 * loop->num_nodes,
1739 si_info_hash, si_info_eq, free);
1741 /* Record the loop exit bb and loop preheader before the unrolling. */
1742 opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1744 if (VEC_length (edge, edges) == 1)
1746 exit = VEC_index (edge, edges, 0);
1747 if (!(exit->flags & EDGE_COMPLEX))
1749 opt_info->loop_exit = split_edge (exit);
1754 if (flag_variable_expansion_in_unroller
1756 opt_info->insns_with_var_to_expand = htab_create (5 * loop->num_nodes,
1757 ve_info_hash, ve_info_eq, free);
1759 for (i = 0; i < loop->num_nodes; i++)
1762 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1765 FOR_BB_INSNS (bb, insn)
1770 if (opt_info->insns_to_split)
1771 ivts = analyze_iv_to_split_insn (insn);
1775 slot1 = htab_find_slot (opt_info->insns_to_split, ivts, INSERT);
1780 if (opt_info->insns_with_var_to_expand)
1781 ves = analyze_insn_to_expand_var (loop, insn);
1785 slot2 = htab_find_slot (opt_info->insns_with_var_to_expand, ves, INSERT);
1791 VEC_free (edge, heap, edges);
1796 /* Called just before loop duplication. Records start of duplicated area
1800 opt_info_start_duplication (struct opt_info *opt_info)
1803 opt_info->first_new_block = last_basic_block;
1806 /* Determine the number of iterations between initialization of the base
1807 variable and the current copy (N_COPY). N_COPIES is the total number
1808 of newly created copies. UNROLLING is true if we are unrolling
1809 (not peeling) the loop. */
1812 determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
1816 /* If we are unrolling, initialization is done in the original loop
1822 /* If we are peeling, the copy in that the initialization occurs has
1823 number 1. The original loop (number 0) is the last. */
1831 /* Locate in EXPR the expression corresponding to the location recorded
1832 in IVTS, and return a pointer to the RTX for this location. */
1835 get_ivts_expr (rtx expr, struct iv_to_split *ivts)
1840 for (i = 0; i < ivts->n_loc; i++)
1841 ret = &XEXP (*ret, ivts->loc[i]);
1846 /* Allocate basic variable for the induction variable chain. Callback for
1850 allocate_basic_variable (void **slot, void *data ATTRIBUTE_UNUSED)
1852 struct iv_to_split *ivts = *slot;
1853 rtx expr = *get_ivts_expr (single_set (ivts->insn), ivts);
1855 ivts->base_var = gen_reg_rtx (GET_MODE (expr));
1860 /* Insert initialization of basic variable of IVTS before INSN, taking
1861 the initial value from INSN. */
1864 insert_base_initialization (struct iv_to_split *ivts, rtx insn)
1866 rtx expr = copy_rtx (*get_ivts_expr (single_set (insn), ivts));
1870 expr = force_operand (expr, ivts->base_var);
1871 if (expr != ivts->base_var)
1872 emit_move_insn (ivts->base_var, expr);
1876 emit_insn_before (seq, insn);
1879 /* Replace the use of induction variable described in IVTS in INSN
1880 by base variable + DELTA * step. */
1883 split_iv (struct iv_to_split *ivts, rtx insn, unsigned delta)
1885 rtx expr, *loc, seq, incr, var;
1886 enum machine_mode mode = GET_MODE (ivts->base_var);
1889 /* Construct base + DELTA * step. */
1891 expr = ivts->base_var;
1894 incr = simplify_gen_binary (MULT, mode,
1895 ivts->step, gen_int_mode (delta, mode));
1896 expr = simplify_gen_binary (PLUS, GET_MODE (ivts->base_var),
1897 ivts->base_var, incr);
1900 /* Figure out where to do the replacement. */
1901 loc = get_ivts_expr (single_set (insn), ivts);
1903 /* If we can make the replacement right away, we're done. */
1904 if (validate_change (insn, loc, expr, 0))
1907 /* Otherwise, force EXPR into a register and try again. */
1909 var = gen_reg_rtx (mode);
1910 expr = force_operand (expr, var);
1912 emit_move_insn (var, expr);
1915 emit_insn_before (seq, insn);
1917 if (validate_change (insn, loc, var, 0))
1920 /* The last chance. Try recreating the assignment in insn
1921 completely from scratch. */
1922 set = single_set (insn);
1927 src = copy_rtx (SET_SRC (set));
1928 dest = copy_rtx (SET_DEST (set));
1929 src = force_operand (src, dest);
1931 emit_move_insn (dest, src);
1935 emit_insn_before (seq, insn);
1940 /* Return one expansion of the accumulator recorded in struct VE. */
1943 get_expansion (struct var_to_expand *ve)
1947 if (ve->reuse_expansion == 0)
1950 reg = VEC_index (rtx, ve->var_expansions, ve->reuse_expansion - 1);
1952 if (VEC_length (rtx, ve->var_expansions) == (unsigned) ve->reuse_expansion)
1953 ve->reuse_expansion = 0;
1955 ve->reuse_expansion++;
1961 /* Given INSN replace the uses of the accumulator recorded in VE
1962 with a new register. */
1965 expand_var_during_unrolling (struct var_to_expand *ve, rtx insn)
1968 bool really_new_expansion = false;
1970 set = single_set (insn);
1973 /* Generate a new register only if the expansion limit has not been
1974 reached. Else reuse an already existing expansion. */
1975 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS) > ve->expansion_count)
1977 really_new_expansion = true;
1978 new_reg = gen_reg_rtx (GET_MODE (ve->reg));
1981 new_reg = get_expansion (ve);
1983 validate_change (insn, &SET_DEST (set), new_reg, 1);
1984 validate_change (insn, &XEXP (SET_SRC (set), 0), new_reg, 1);
1986 if (apply_change_group ())
1987 if (really_new_expansion)
1989 VEC_safe_push (rtx, heap, ve->var_expansions, new_reg);
1990 ve->expansion_count++;
1994 /* Initialize the variable expansions in loop preheader.
1995 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1996 basic block where the initialization of the expansions
1997 should take place. */
2000 insert_var_expansion_initialization (void **slot, void *place_p)
2002 struct var_to_expand *ve = *slot;
2003 basic_block place = (basic_block)place_p;
2004 rtx seq, var, zero_init, insn;
2007 if (VEC_length (rtx, ve->var_expansions) == 0)
2011 if (ve->op == PLUS || ve->op == MINUS)
2012 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2014 zero_init = CONST0_RTX (GET_MODE (var));
2015 emit_move_insn (var, zero_init);
2017 else if (ve->op == MULT)
2018 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2020 zero_init = CONST1_RTX (GET_MODE (var));
2021 emit_move_insn (var, zero_init);
2027 insn = BB_HEAD (place);
2028 while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2029 insn = NEXT_INSN (insn);
2031 emit_insn_after (seq, insn);
2032 /* Continue traversing the hash table. */
2036 /* Combine the variable expansions at the loop exit.
2037 Callbacks for htab_traverse. PLACE_P is the loop exit
2038 basic block where the summation of the expansions should
2042 combine_var_copies_in_loop_exit (void **slot, void *place_p)
2044 struct var_to_expand *ve = *slot;
2045 basic_block place = (basic_block)place_p;
2047 rtx expr, seq, var, insn;
2050 if (VEC_length (rtx, ve->var_expansions) == 0)
2054 if (ve->op == PLUS || ve->op == MINUS)
2055 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2057 sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg),
2060 else if (ve->op == MULT)
2061 for (i = 0; VEC_iterate (rtx, ve->var_expansions, i, var); i++)
2063 sum = simplify_gen_binary (MULT, GET_MODE (ve->reg),
2067 expr = force_operand (sum, ve->reg);
2068 if (expr != ve->reg)
2069 emit_move_insn (ve->reg, expr);
2073 insn = BB_HEAD (place);
2074 while (!NOTE_INSN_BASIC_BLOCK_P (insn))
2075 insn = NEXT_INSN (insn);
2077 emit_insn_after (seq, insn);
2079 /* Continue traversing the hash table. */
2083 /* Apply loop optimizations in loop copies using the
2084 data which gathered during the unrolling. Structure
2085 OPT_INFO record that data.
2087 UNROLLING is true if we unrolled (not peeled) the loop.
2088 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2089 the loop (as it should happen in complete unrolling, but not in ordinary
2090 peeling of the loop). */
2093 apply_opt_in_copies (struct opt_info *opt_info,
2094 unsigned n_copies, bool unrolling,
2095 bool rewrite_original_loop)
2098 basic_block bb, orig_bb;
2099 rtx insn, orig_insn, next;
2100 struct iv_to_split ivts_templ, *ivts;
2101 struct var_to_expand ve_templ, *ves;
2103 /* Sanity check -- we need to put initialization in the original loop
2105 gcc_assert (!unrolling || rewrite_original_loop);
2107 /* Allocate the basic variables (i0). */
2108 if (opt_info->insns_to_split)
2109 htab_traverse (opt_info->insns_to_split, allocate_basic_variable, NULL);
2111 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2113 bb = BASIC_BLOCK (i);
2114 orig_bb = get_bb_original (bb);
2116 /* bb->aux holds position in copy sequence initialized by
2117 duplicate_loop_to_header_edge. */
2118 delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
2121 orig_insn = BB_HEAD (orig_bb);
2122 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
2124 next = NEXT_INSN (insn);
2128 while (!INSN_P (orig_insn))
2129 orig_insn = NEXT_INSN (orig_insn);
2131 ivts_templ.insn = orig_insn;
2132 ve_templ.insn = orig_insn;
2134 /* Apply splitting iv optimization. */
2135 if (opt_info->insns_to_split)
2137 ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2141 gcc_assert (GET_CODE (PATTERN (insn))
2142 == GET_CODE (PATTERN (orig_insn)));
2145 insert_base_initialization (ivts, insn);
2146 split_iv (ivts, insn, delta);
2149 /* Apply variable expansion optimization. */
2150 if (unrolling && opt_info->insns_with_var_to_expand)
2152 ves = htab_find (opt_info->insns_with_var_to_expand, &ve_templ);
2155 gcc_assert (GET_CODE (PATTERN (insn))
2156 == GET_CODE (PATTERN (orig_insn)));
2157 expand_var_during_unrolling (ves, insn);
2160 orig_insn = NEXT_INSN (orig_insn);
2164 if (!rewrite_original_loop)
2167 /* Initialize the variable expansions in the loop preheader
2168 and take care of combining them at the loop exit. */
2169 if (opt_info->insns_with_var_to_expand)
2171 htab_traverse (opt_info->insns_with_var_to_expand,
2172 insert_var_expansion_initialization,
2173 opt_info->loop_preheader);
2174 htab_traverse (opt_info->insns_with_var_to_expand,
2175 combine_var_copies_in_loop_exit,
2176 opt_info->loop_exit);
2179 /* Rewrite also the original loop body. Find them as originals of the blocks
2180 in the last copied iteration, i.e. those that have
2181 get_bb_copy (get_bb_original (bb)) == bb. */
2182 for (i = opt_info->first_new_block; i < (unsigned) last_basic_block; i++)
2184 bb = BASIC_BLOCK (i);
2185 orig_bb = get_bb_original (bb);
2186 if (get_bb_copy (orig_bb) != bb)
2189 delta = determine_split_iv_delta (0, n_copies, unrolling);
2190 for (orig_insn = BB_HEAD (orig_bb);
2191 orig_insn != NEXT_INSN (BB_END (bb));
2194 next = NEXT_INSN (orig_insn);
2196 if (!INSN_P (orig_insn))
2199 ivts_templ.insn = orig_insn;
2200 if (opt_info->insns_to_split)
2202 ivts = htab_find (opt_info->insns_to_split, &ivts_templ);
2206 insert_base_initialization (ivts, orig_insn);
2207 split_iv (ivts, orig_insn, delta);
2216 /* Release the data structures used for the variable expansion
2217 optimization. Callbacks for htab_traverse. */
2220 release_var_copies (void **slot, void *data ATTRIBUTE_UNUSED)
2222 struct var_to_expand *ve = *slot;
2224 VEC_free (rtx, heap, ve->var_expansions);
2226 /* Continue traversing the hash table. */
2230 /* Release OPT_INFO. */
2233 free_opt_info (struct opt_info *opt_info)
2235 if (opt_info->insns_to_split)
2236 htab_delete (opt_info->insns_to_split);
2237 if (opt_info->insns_with_var_to_expand)
2239 htab_traverse (opt_info->insns_with_var_to_expand,
2240 release_var_copies, NULL);
2241 htab_delete (opt_info->insns_with_var_to_expand);