1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2010, 2011
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.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. */
80 struct iv_to_split
*next
; /* Next entry in walking order. */
82 unsigned loc
[3]; /* Location where the definition of the induction
83 variable occurs in the insn. For example if
84 N_LOC is 2, the expression is located at
85 XEXP (XEXP (single_set, loc[0]), loc[1]). */
88 /* Information about accumulators to expand. */
92 rtx insn
; /* The insn in that the variable expansion occurs. */
93 rtx reg
; /* The accumulator which is expanded. */
94 VEC(rtx
,heap
) *var_expansions
; /* The copies of the accumulator which is expanded. */
95 struct var_to_expand
*next
; /* Next entry in walking order. */
96 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
98 int expansion_count
; /* Count the number of expansions generated so far. */
99 int reuse_expansion
; /* The expansion we intend to reuse to expand
100 the accumulator. If REUSE_EXPANSION is 0 reuse
101 the original accumulator. Else use
102 var_expansions[REUSE_EXPANSION - 1]. */
105 /* Information about optimization applied in
106 the unrolled loop. */
110 htab_t insns_to_split
; /* A hashtable of insns to split. */
111 struct iv_to_split
*iv_to_split_head
; /* The first iv to split. */
112 struct iv_to_split
**iv_to_split_tail
; /* Pointer to the tail of the list. */
113 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
115 struct var_to_expand
*var_to_expand_head
; /* The first var to expand. */
116 struct var_to_expand
**var_to_expand_tail
; /* Pointer to the tail of the list. */
117 unsigned first_new_block
; /* The first basic block that was
119 basic_block loop_exit
; /* The loop exit basic block. */
120 basic_block loop_preheader
; /* The loop preheader basic block. */
123 static void decide_unrolling_and_peeling (int);
124 static void peel_loops_completely (int);
125 static void decide_peel_simple (struct loop
*, int);
126 static void decide_peel_once_rolling (struct loop
*, int);
127 static void decide_peel_completely (struct loop
*, int);
128 static void decide_unroll_stupid (struct loop
*, int);
129 static void decide_unroll_constant_iterations (struct loop
*, int);
130 static void decide_unroll_runtime_iterations (struct loop
*, int);
131 static void peel_loop_simple (struct loop
*);
132 static void peel_loop_completely (struct loop
*);
133 static void unroll_loop_stupid (struct loop
*);
134 static void unroll_loop_constant_iterations (struct loop
*);
135 static void unroll_loop_runtime_iterations (struct loop
*);
136 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
137 static void opt_info_start_duplication (struct opt_info
*);
138 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
139 static void free_opt_info (struct opt_info
*);
140 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
141 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
, int *);
142 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
143 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
144 static void insert_var_expansion_initialization (struct var_to_expand
*,
146 static void combine_var_copies_in_loop_exit (struct var_to_expand
*,
148 static rtx
get_expansion (struct var_to_expand
*);
150 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
152 unroll_and_peel_loops (int flags
)
158 /* First perform complete loop peeling (it is almost surely a win,
159 and affects parameters for further decision a lot). */
160 peel_loops_completely (flags
);
162 /* Now decide rest of unrolling and peeling. */
163 decide_unrolling_and_peeling (flags
);
165 /* Scan the loops, inner ones first. */
166 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
169 /* And perform the appropriate transformations. */
170 switch (loop
->lpt_decision
.decision
)
172 case LPT_PEEL_COMPLETELY
:
175 case LPT_PEEL_SIMPLE
:
176 peel_loop_simple (loop
);
178 case LPT_UNROLL_CONSTANT
:
179 unroll_loop_constant_iterations (loop
);
181 case LPT_UNROLL_RUNTIME
:
182 unroll_loop_runtime_iterations (loop
);
184 case LPT_UNROLL_STUPID
:
185 unroll_loop_stupid (loop
);
195 #ifdef ENABLE_CHECKING
196 verify_loop_structure ();
204 /* Check whether exit of the LOOP is at the end of loop body. */
207 loop_exit_at_end_p (struct loop
*loop
)
209 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
212 if (desc
->in_edge
->dest
!= loop
->latch
)
215 /* Check that the latch is empty. */
216 FOR_BB_INSNS (loop
->latch
, insn
)
225 /* Depending on FLAGS, check whether to peel loops completely and do so. */
227 peel_loops_completely (int flags
)
232 /* Scan the loops, the inner ones first. */
233 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
235 loop
->lpt_decision
.decision
= LPT_NONE
;
239 "\n;; *** Considering loop %d for complete peeling ***\n",
242 loop
->ninsns
= num_loop_insns (loop
);
244 decide_peel_once_rolling (loop
, flags
);
245 if (loop
->lpt_decision
.decision
== LPT_NONE
)
246 decide_peel_completely (loop
, flags
);
248 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
250 peel_loop_completely (loop
);
251 #ifdef ENABLE_CHECKING
252 verify_loop_structure ();
258 /* Decide whether unroll or peel loops (depending on FLAGS) and how much. */
260 decide_unrolling_and_peeling (int flags
)
265 /* Scan the loops, inner ones first. */
266 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
268 loop
->lpt_decision
.decision
= LPT_NONE
;
271 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
273 /* Do not peel cold areas. */
274 if (optimize_loop_for_size_p (loop
))
277 fprintf (dump_file
, ";; Not considering loop, cold area\n");
281 /* Can the loop be manipulated? */
282 if (!can_duplicate_loop_p (loop
))
286 ";; Not considering loop, cannot duplicate\n");
290 /* Skip non-innermost loops. */
294 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
298 loop
->ninsns
= num_loop_insns (loop
);
299 loop
->av_ninsns
= average_num_loop_insns (loop
);
301 /* Try transformations one by one in decreasing order of
304 decide_unroll_constant_iterations (loop
, flags
);
305 if (loop
->lpt_decision
.decision
== LPT_NONE
)
306 decide_unroll_runtime_iterations (loop
, flags
);
307 if (loop
->lpt_decision
.decision
== LPT_NONE
)
308 decide_unroll_stupid (loop
, flags
);
309 if (loop
->lpt_decision
.decision
== LPT_NONE
)
310 decide_peel_simple (loop
, flags
);
314 /* Decide whether the LOOP is once rolling and suitable for complete
317 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
319 struct niter_desc
*desc
;
322 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
324 /* Is the loop small enough? */
325 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
328 fprintf (dump_file
, ";; Not considering loop, is too big\n");
332 /* Check for simple loops. */
333 desc
= get_simple_loop_desc (loop
);
335 /* Check number of iterations. */
341 && max_loop_iterations_int (loop
) != 0))
345 ";; Unable to prove that the loop rolls exactly once\n");
351 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
352 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
355 /* Decide whether the LOOP is suitable for complete peeling. */
357 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
360 struct niter_desc
*desc
;
363 fprintf (dump_file
, "\n;; Considering peeling completely\n");
365 /* Skip non-innermost loops. */
369 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
373 /* Do not peel cold areas. */
374 if (optimize_loop_for_size_p (loop
))
377 fprintf (dump_file
, ";; Not considering loop, cold area\n");
381 /* Can the loop be manipulated? */
382 if (!can_duplicate_loop_p (loop
))
386 ";; Not considering loop, cannot duplicate\n");
390 /* npeel = number of iterations to peel. */
391 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
392 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
393 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
395 /* Is the loop small enough? */
399 fprintf (dump_file
, ";; Not considering loop, is too big\n");
403 /* Check for simple loops. */
404 desc
= get_simple_loop_desc (loop
);
406 /* Check number of iterations. */
414 ";; Unable to prove that the loop iterates constant times\n");
418 if (desc
->niter
> npeel
- 1)
423 ";; Not peeling loop completely, rolls too much (");
424 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
425 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
432 fprintf (dump_file
, ";; Decided to peel loop completely\n");
433 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
436 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
437 completely. The transformation done:
439 for (i = 0; i < 4; i++)
451 peel_loop_completely (struct loop
*loop
)
454 unsigned HOST_WIDE_INT npeel
;
456 VEC (edge
, heap
) *remove_edges
;
458 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
459 struct opt_info
*opt_info
= NULL
;
467 wont_exit
= sbitmap_alloc (npeel
+ 1);
468 sbitmap_ones (wont_exit
);
469 RESET_BIT (wont_exit
, 0);
470 if (desc
->noloop_assumptions
)
471 RESET_BIT (wont_exit
, 1);
475 if (flag_split_ivs_in_unroller
)
476 opt_info
= analyze_insns_in_loop (loop
);
478 opt_info_start_duplication (opt_info
);
479 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
481 wont_exit
, desc
->out_edge
,
483 DLTHE_FLAG_UPDATE_FREQ
484 | DLTHE_FLAG_COMPLETTE_PEEL
486 ? DLTHE_RECORD_COPY_NUMBER
: 0));
493 apply_opt_in_copies (opt_info
, npeel
, false, true);
494 free_opt_info (opt_info
);
497 /* Remove the exit edges. */
498 FOR_EACH_VEC_ELT (edge
, remove_edges
, i
, ein
)
500 VEC_free (edge
, heap
, remove_edges
);
504 free_simple_loop_desc (loop
);
506 /* Now remove the unreachable part of the last iteration and cancel
511 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
514 /* Decide whether to unroll LOOP iterating constant number of times
518 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
520 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
521 struct niter_desc
*desc
;
523 if (!(flags
& UAP_UNROLL
))
525 /* We were not asked to, just return back silently. */
531 "\n;; Considering unrolling loop with constant "
532 "number of iterations\n");
534 /* nunroll = total number of copies of the original loop body in
535 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
536 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
538 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
539 if (nunroll
> nunroll_by_av
)
540 nunroll
= nunroll_by_av
;
541 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
542 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
544 /* Skip big loops. */
548 fprintf (dump_file
, ";; Not considering loop, is too big\n");
552 /* Check for simple loops. */
553 desc
= get_simple_loop_desc (loop
);
555 /* Check number of iterations. */
556 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
560 ";; Unable to prove that the loop iterates constant times\n");
564 /* Check whether the loop rolls enough to consider. */
565 if (desc
->niter
< 2 * nunroll
)
568 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
572 /* Success; now compute number of iterations to unroll. We alter
573 nunroll so that as few as possible copies of loop body are
574 necessary, while still not decreasing the number of unrollings
575 too much (at most by 1). */
576 best_copies
= 2 * nunroll
+ 10;
579 if (i
- 1 >= desc
->niter
)
582 for (; i
>= nunroll
- 1; i
--)
584 unsigned exit_mod
= desc
->niter
% (i
+ 1);
586 if (!loop_exit_at_end_p (loop
))
587 n_copies
= exit_mod
+ i
+ 1;
588 else if (exit_mod
!= (unsigned) i
589 || desc
->noloop_assumptions
!= NULL_RTX
)
590 n_copies
= exit_mod
+ i
+ 2;
594 if (n_copies
< best_copies
)
596 best_copies
= n_copies
;
601 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
602 loop
->lpt_decision
.times
= best_unroll
;
605 fprintf (dump_file
, ";; Decided to unroll the loop %d times (%d copies).\n",
606 loop
->lpt_decision
.times
, best_copies
);
609 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
610 The transformation does this:
612 for (i = 0; i < 102; i++)
615 ==> (LOOP->LPT_DECISION.TIMES == 3)
629 unroll_loop_constant_iterations (struct loop
*loop
)
631 unsigned HOST_WIDE_INT niter
;
635 VEC (edge
, heap
) *remove_edges
;
637 unsigned max_unroll
= loop
->lpt_decision
.times
;
638 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
639 bool exit_at_end
= loop_exit_at_end_p (loop
);
640 struct opt_info
*opt_info
= NULL
;
645 /* Should not get here (such loop should be peeled instead). */
646 gcc_assert (niter
> max_unroll
+ 1);
648 exit_mod
= niter
% (max_unroll
+ 1);
650 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
651 sbitmap_ones (wont_exit
);
654 if (flag_split_ivs_in_unroller
655 || flag_variable_expansion_in_unroller
)
656 opt_info
= analyze_insns_in_loop (loop
);
660 /* The exit is not at the end of the loop; leave exit test
661 in the first copy, so that the loops that start with test
662 of exit condition have continuous body after unrolling. */
665 fprintf (dump_file
, ";; Condition at beginning of loop.\n");
667 /* Peel exit_mod iterations. */
668 RESET_BIT (wont_exit
, 0);
669 if (desc
->noloop_assumptions
)
670 RESET_BIT (wont_exit
, 1);
674 opt_info_start_duplication (opt_info
);
675 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
677 wont_exit
, desc
->out_edge
,
679 DLTHE_FLAG_UPDATE_FREQ
680 | (opt_info
&& exit_mod
> 1
681 ? DLTHE_RECORD_COPY_NUMBER
685 if (opt_info
&& exit_mod
> 1)
686 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
688 desc
->noloop_assumptions
= NULL_RTX
;
689 desc
->niter
-= exit_mod
;
690 loop
->nb_iterations_upper_bound
-= double_int::from_uhwi (exit_mod
);
691 if (loop
->any_estimate
692 && double_int::from_uhwi (exit_mod
).ule
693 (loop
->nb_iterations_estimate
))
694 loop
->nb_iterations_estimate
-= double_int::from_uhwi (exit_mod
);
696 loop
->any_estimate
= false;
699 SET_BIT (wont_exit
, 1);
703 /* Leave exit test in last copy, for the same reason as above if
704 the loop tests the condition at the end of loop body. */
707 fprintf (dump_file
, ";; Condition at end of loop.\n");
709 /* We know that niter >= max_unroll + 2; so we do not need to care of
710 case when we would exit before reaching the loop. So just peel
711 exit_mod + 1 iterations. */
712 if (exit_mod
!= max_unroll
713 || desc
->noloop_assumptions
)
715 RESET_BIT (wont_exit
, 0);
716 if (desc
->noloop_assumptions
)
717 RESET_BIT (wont_exit
, 1);
719 opt_info_start_duplication (opt_info
);
720 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
722 wont_exit
, desc
->out_edge
,
724 DLTHE_FLAG_UPDATE_FREQ
725 | (opt_info
&& exit_mod
> 0
726 ? DLTHE_RECORD_COPY_NUMBER
730 if (opt_info
&& exit_mod
> 0)
731 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
733 desc
->niter
-= exit_mod
+ 1;
734 loop
->nb_iterations_upper_bound
-= double_int::from_uhwi (exit_mod
+ 1);
735 if (loop
->any_estimate
736 && double_int::from_uhwi (exit_mod
+ 1).ule
737 (loop
->nb_iterations_estimate
))
738 loop
->nb_iterations_estimate
-= double_int::from_uhwi (exit_mod
+ 1);
740 loop
->any_estimate
= false;
741 desc
->noloop_assumptions
= NULL_RTX
;
743 SET_BIT (wont_exit
, 0);
744 SET_BIT (wont_exit
, 1);
747 RESET_BIT (wont_exit
, max_unroll
);
750 /* Now unroll the loop. */
752 opt_info_start_duplication (opt_info
);
753 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
755 wont_exit
, desc
->out_edge
,
757 DLTHE_FLAG_UPDATE_FREQ
759 ? DLTHE_RECORD_COPY_NUMBER
765 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
766 free_opt_info (opt_info
);
773 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
774 /* Find a new in and out edge; they are in the last copy we have made. */
776 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
778 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
779 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
783 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
784 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
788 desc
->niter
/= max_unroll
+ 1;
789 loop
->nb_iterations_upper_bound
790 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (max_unroll
793 if (loop
->any_estimate
)
794 loop
->nb_iterations_estimate
795 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (max_unroll
798 desc
->niter_expr
= GEN_INT (desc
->niter
);
800 /* Remove the edges. */
801 FOR_EACH_VEC_ELT (edge
, remove_edges
, i
, e
)
803 VEC_free (edge
, heap
, remove_edges
);
807 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
808 max_unroll
, num_loop_insns (loop
));
811 /* Decide whether to unroll LOOP iterating runtime computable number of times
814 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
816 unsigned nunroll
, nunroll_by_av
, i
;
817 struct niter_desc
*desc
;
818 double_int iterations
;
820 if (!(flags
& UAP_UNROLL
))
822 /* We were not asked to, just return back silently. */
828 "\n;; Considering unrolling loop with runtime "
829 "computable number of iterations\n");
831 /* nunroll = total number of copies of the original loop body in
832 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
833 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
834 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
835 if (nunroll
> nunroll_by_av
)
836 nunroll
= nunroll_by_av
;
837 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
838 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
840 if (targetm
.loop_unroll_adjust
)
841 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
843 /* Skip big loops. */
847 fprintf (dump_file
, ";; Not considering loop, is too big\n");
851 /* Check for simple loops. */
852 desc
= get_simple_loop_desc (loop
);
854 /* Check simpleness. */
855 if (!desc
->simple_p
|| desc
->assumptions
)
859 ";; Unable to prove that the number of iterations "
860 "can be counted in runtime\n");
864 if (desc
->const_iter
)
867 fprintf (dump_file
, ";; Loop iterates constant times\n");
871 /* Check whether the loop rolls. */
872 if ((estimated_loop_iterations (loop
, &iterations
)
873 || max_loop_iterations (loop
, &iterations
))
874 && iterations
.ult (double_int::from_shwi (2 * nunroll
)))
877 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
881 /* Success; now force nunroll to be power of 2, as we are unable to
882 cope with overflows in computation of number of iterations. */
883 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
886 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
887 loop
->lpt_decision
.times
= i
- 1;
890 fprintf (dump_file
, ";; Decided to unroll the loop %d times.\n",
891 loop
->lpt_decision
.times
);
894 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
895 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
896 and NULL is returned instead. */
899 split_edge_and_insert (edge e
, rtx insns
)
906 emit_insn_after (insns
, BB_END (bb
));
908 /* ??? We used to assume that INSNS can contain control flow insns, and
909 that we had to try to find sub basic blocks in BB to maintain a valid
910 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
911 and call break_superblocks when going out of cfglayout mode. But it
912 turns out that this never happens; and that if it does ever happen,
913 the TODO_verify_flow at the end of the RTL loop passes would fail.
915 There are two reasons why we expected we could have control flow insns
916 in INSNS. The first is when a comparison has to be done in parts, and
917 the second is when the number of iterations is computed for loops with
918 the number of iterations known at runtime. In both cases, test cases
919 to get control flow in INSNS appear to be impossible to construct:
921 * If do_compare_rtx_and_jump needs several branches to do comparison
922 in a mode that needs comparison by parts, we cannot analyze the
923 number of iterations of the loop, and we never get to unrolling it.
925 * The code in expand_divmod that was suspected to cause creation of
926 branching code seems to be only accessed for signed division. The
927 divisions used by # of iterations analysis are always unsigned.
928 Problems might arise on architectures that emits branching code
929 for some operations that may appear in the unroller (especially
930 for division), but we have no such architectures.
932 Considering all this, it was decided that we should for now assume
933 that INSNS can in theory contain control flow insns, but in practice
934 it never does. So we don't handle the theoretical case, and should
935 a real failure ever show up, we have a pretty good clue for how to
941 /* Unroll LOOP for which we are able to count number of iterations in runtime
942 LOOP->LPT_DECISION.TIMES times. The transformation does this (with some
943 extra care for case n < 0):
945 for (i = 0; i < n; i++)
948 ==> (LOOP->LPT_DECISION.TIMES == 3)
973 unroll_loop_runtime_iterations (struct loop
*loop
)
975 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
977 basic_block preheader
, *body
, swtch
, ezc_swtch
;
978 VEC (basic_block
, heap
) *dom_bbs
;
982 VEC (edge
, heap
) *remove_edges
;
984 bool extra_zero_check
, last_may_exit
;
985 unsigned max_unroll
= loop
->lpt_decision
.times
;
986 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
987 bool exit_at_end
= loop_exit_at_end_p (loop
);
988 struct opt_info
*opt_info
= NULL
;
991 if (flag_split_ivs_in_unroller
992 || flag_variable_expansion_in_unroller
)
993 opt_info
= analyze_insns_in_loop (loop
);
995 /* Remember blocks whose dominators will have to be updated. */
998 body
= get_loop_body (loop
);
999 for (i
= 0; i
< loop
->num_nodes
; i
++)
1001 VEC (basic_block
, heap
) *ldom
;
1004 ldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
]);
1005 FOR_EACH_VEC_ELT (basic_block
, ldom
, j
, bb
)
1006 if (!flow_bb_inside_loop_p (loop
, bb
))
1007 VEC_safe_push (basic_block
, heap
, dom_bbs
, bb
);
1009 VEC_free (basic_block
, heap
, ldom
);
1015 /* Leave exit in first copy (for explanation why see comment in
1016 unroll_loop_constant_iterations). */
1018 n_peel
= max_unroll
- 1;
1019 extra_zero_check
= true;
1020 last_may_exit
= false;
1024 /* Leave exit in last copy (for explanation why see comment in
1025 unroll_loop_constant_iterations). */
1026 may_exit_copy
= max_unroll
;
1027 n_peel
= max_unroll
;
1028 extra_zero_check
= false;
1029 last_may_exit
= true;
1032 /* Get expression for number of iterations. */
1034 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
1035 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
1037 emit_move_insn (niter
, tmp
);
1039 /* Count modulo by ANDing it with max_unroll; we use the fact that
1040 the number of unrollings is a power of two, and thus this is correct
1041 even if there is overflow in the computation. */
1042 niter
= expand_simple_binop (desc
->mode
, AND
,
1044 GEN_INT (max_unroll
),
1045 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1047 init_code
= get_insns ();
1049 unshare_all_rtl_in_chain (init_code
);
1051 /* Precondition the loop. */
1052 split_edge_and_insert (loop_preheader_edge (loop
), init_code
);
1054 remove_edges
= NULL
;
1056 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1058 /* Peel the first copy of loop body (almost always we must leave exit test
1059 here; the only exception is when we have extra zero check and the number
1060 of iterations is reliable. Also record the place of (possible) extra
1062 sbitmap_zero (wont_exit
);
1063 if (extra_zero_check
1064 && !desc
->noloop_assumptions
)
1065 SET_BIT (wont_exit
, 1);
1066 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1067 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1068 1, wont_exit
, desc
->out_edge
,
1070 DLTHE_FLAG_UPDATE_FREQ
);
1073 /* Record the place where switch will be built for preconditioning. */
1074 swtch
= split_edge (loop_preheader_edge (loop
));
1076 for (i
= 0; i
< n_peel
; i
++)
1078 /* Peel the copy. */
1079 sbitmap_zero (wont_exit
);
1080 if (i
!= n_peel
- 1 || !last_may_exit
)
1081 SET_BIT (wont_exit
, 1);
1082 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1083 1, wont_exit
, desc
->out_edge
,
1085 DLTHE_FLAG_UPDATE_FREQ
);
1088 /* Create item for switch. */
1089 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1090 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1092 preheader
= split_edge (loop_preheader_edge (loop
));
1093 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1094 block_label (preheader
), p
,
1097 /* We rely on the fact that the compare and jump cannot be optimized out,
1098 and hence the cfg we create is correct. */
1099 gcc_assert (branch_code
!= NULL_RTX
);
1101 swtch
= split_edge_and_insert (single_pred_edge (swtch
), branch_code
);
1102 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1103 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1104 e
= make_edge (swtch
, preheader
,
1105 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1106 e
->count
= RDIV (preheader
->count
* REG_BR_PROB_BASE
, p
);
1110 if (extra_zero_check
)
1112 /* Add branch for zero iterations. */
1113 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1115 preheader
= split_edge (loop_preheader_edge (loop
));
1116 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1117 block_label (preheader
), p
,
1119 gcc_assert (branch_code
!= NULL_RTX
);
1121 swtch
= split_edge_and_insert (single_succ_edge (swtch
), branch_code
);
1122 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1123 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1124 e
= make_edge (swtch
, preheader
,
1125 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1126 e
->count
= RDIV (preheader
->count
* REG_BR_PROB_BASE
, p
);
1130 /* Recount dominators for outer blocks. */
1131 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
1133 /* And unroll loop. */
1135 sbitmap_ones (wont_exit
);
1136 RESET_BIT (wont_exit
, may_exit_copy
);
1137 opt_info_start_duplication (opt_info
);
1139 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1141 wont_exit
, desc
->out_edge
,
1143 DLTHE_FLAG_UPDATE_FREQ
1145 ? DLTHE_RECORD_COPY_NUMBER
1151 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1152 free_opt_info (opt_info
);
1159 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1160 /* Find a new in and out edge; they are in the last copy we have
1163 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1165 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1166 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1170 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1171 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1175 /* Remove the edges. */
1176 FOR_EACH_VEC_ELT (edge
, remove_edges
, i
, e
)
1178 VEC_free (edge
, heap
, remove_edges
);
1180 /* We must be careful when updating the number of iterations due to
1181 preconditioning and the fact that the value must be valid at entry
1182 of the loop. After passing through the above code, we see that
1183 the correct new number of iterations is this: */
1184 gcc_assert (!desc
->const_iter
);
1186 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1187 GEN_INT (max_unroll
+ 1));
1188 loop
->nb_iterations_upper_bound
1189 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (max_unroll
1192 if (loop
->any_estimate
)
1193 loop
->nb_iterations_estimate
1194 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (max_unroll
1200 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1201 desc
->noloop_assumptions
= NULL_RTX
;
1202 --loop
->nb_iterations_upper_bound
;
1203 if (loop
->any_estimate
1204 && loop
->nb_iterations_estimate
!= double_int_zero
)
1205 --loop
->nb_iterations_estimate
;
1207 loop
->any_estimate
= false;
1212 ";; Unrolled loop %d times, counting # of iterations "
1213 "in runtime, %i insns\n",
1214 max_unroll
, num_loop_insns (loop
));
1216 VEC_free (basic_block
, heap
, dom_bbs
);
1219 /* Decide whether to simply peel LOOP and how much. */
1221 decide_peel_simple (struct loop
*loop
, int flags
)
1224 struct niter_desc
*desc
;
1225 double_int iterations
;
1227 if (!(flags
& UAP_PEEL
))
1229 /* We were not asked to, just return back silently. */
1234 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1236 /* npeel = number of iterations to peel. */
1237 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1238 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1239 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1241 /* Skip big loops. */
1245 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1249 /* Check for simple loops. */
1250 desc
= get_simple_loop_desc (loop
);
1252 /* Check number of iterations. */
1253 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1256 fprintf (dump_file
, ";; Loop iterates constant times\n");
1260 /* Do not simply peel loops with branches inside -- it increases number
1262 if (num_loop_branches (loop
) > 1)
1265 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1269 /* If we have realistic estimate on number of iterations, use it. */
1270 if (estimated_loop_iterations (loop
, &iterations
))
1272 if (double_int::from_shwi (npeel
).ule (iterations
))
1276 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1277 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1278 (HOST_WIDEST_INT
) (iterations
.to_shwi () + 1));
1279 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1284 npeel
= iterations
.to_shwi () + 1;
1286 /* If we have small enough bound on iterations, we can still peel (completely
1288 else if (max_loop_iterations (loop
, &iterations
)
1289 && iterations
.ult (double_int::from_shwi (npeel
)))
1290 npeel
= iterations
.to_shwi () + 1;
1293 /* For now we have no good heuristics to decide whether loop peeling
1294 will be effective, so disable it. */
1297 ";; Not peeling loop, no evidence it will be profitable\n");
1302 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1303 loop
->lpt_decision
.times
= npeel
;
1306 fprintf (dump_file
, ";; Decided to simply peel the loop %d times.\n",
1307 loop
->lpt_decision
.times
);
1310 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1315 ==> (LOOP->LPT_DECISION.TIMES == 3)
1317 if (!cond) goto end;
1319 if (!cond) goto end;
1321 if (!cond) goto end;
1328 peel_loop_simple (struct loop
*loop
)
1331 unsigned npeel
= loop
->lpt_decision
.times
;
1332 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1333 struct opt_info
*opt_info
= NULL
;
1336 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1337 opt_info
= analyze_insns_in_loop (loop
);
1339 wont_exit
= sbitmap_alloc (npeel
+ 1);
1340 sbitmap_zero (wont_exit
);
1342 opt_info_start_duplication (opt_info
);
1344 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1345 npeel
, wont_exit
, NULL
,
1346 NULL
, DLTHE_FLAG_UPDATE_FREQ
1348 ? DLTHE_RECORD_COPY_NUMBER
1356 apply_opt_in_copies (opt_info
, npeel
, false, false);
1357 free_opt_info (opt_info
);
1362 if (desc
->const_iter
)
1364 desc
->niter
-= npeel
;
1365 desc
->niter_expr
= GEN_INT (desc
->niter
);
1366 desc
->noloop_assumptions
= NULL_RTX
;
1370 /* We cannot just update niter_expr, as its value might be clobbered
1371 inside loop. We could handle this by counting the number into
1372 temporary just like we do in runtime unrolling, but it does not
1374 free_simple_loop_desc (loop
);
1378 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1381 /* Decide whether to unroll LOOP stupidly and how much. */
1383 decide_unroll_stupid (struct loop
*loop
, int flags
)
1385 unsigned nunroll
, nunroll_by_av
, i
;
1386 struct niter_desc
*desc
;
1387 double_int iterations
;
1389 if (!(flags
& UAP_UNROLL_ALL
))
1391 /* We were not asked to, just return back silently. */
1396 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1398 /* nunroll = total number of copies of the original loop body in
1399 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1400 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1402 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1403 if (nunroll
> nunroll_by_av
)
1404 nunroll
= nunroll_by_av
;
1405 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1406 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1408 if (targetm
.loop_unroll_adjust
)
1409 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
1411 /* Skip big loops. */
1415 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1419 /* Check for simple loops. */
1420 desc
= get_simple_loop_desc (loop
);
1422 /* Check simpleness. */
1423 if (desc
->simple_p
&& !desc
->assumptions
)
1426 fprintf (dump_file
, ";; The loop is simple\n");
1430 /* Do not unroll loops with branches inside -- it increases number
1432 if (num_loop_branches (loop
) > 1)
1435 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1439 /* Check whether the loop rolls. */
1440 if ((estimated_loop_iterations (loop
, &iterations
)
1441 || max_loop_iterations (loop
, &iterations
))
1442 && iterations
.ult (double_int::from_shwi (2 * nunroll
)))
1445 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1449 /* Success. Now force nunroll to be power of 2, as it seems that this
1450 improves results (partially because of better alignments, partially
1451 because of some dark magic). */
1452 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1455 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1456 loop
->lpt_decision
.times
= i
- 1;
1459 fprintf (dump_file
, ";; Decided to unroll the loop stupidly %d times.\n",
1460 loop
->lpt_decision
.times
);
1463 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1468 ==> (LOOP->LPT_DECISION.TIMES == 3)
1482 unroll_loop_stupid (struct loop
*loop
)
1485 unsigned nunroll
= loop
->lpt_decision
.times
;
1486 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1487 struct opt_info
*opt_info
= NULL
;
1490 if (flag_split_ivs_in_unroller
1491 || flag_variable_expansion_in_unroller
)
1492 opt_info
= analyze_insns_in_loop (loop
);
1495 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1496 sbitmap_zero (wont_exit
);
1497 opt_info_start_duplication (opt_info
);
1499 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1502 DLTHE_FLAG_UPDATE_FREQ
1504 ? DLTHE_RECORD_COPY_NUMBER
1510 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1511 free_opt_info (opt_info
);
1518 /* We indeed may get here provided that there are nontrivial assumptions
1519 for a loop to be really simple. We could update the counts, but the
1520 problem is that we are unable to decide which exit will be taken
1521 (not really true in case the number of iterations is constant,
1522 but noone will do anything with this information, so we do not
1524 desc
->simple_p
= false;
1528 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1529 nunroll
, num_loop_insns (loop
));
1532 /* A hash function for information about insns to split. */
1535 si_info_hash (const void *ivts
)
1537 return (hashval_t
) INSN_UID (((const struct iv_to_split
*) ivts
)->insn
);
1540 /* An equality functions for information about insns to split. */
1543 si_info_eq (const void *ivts1
, const void *ivts2
)
1545 const struct iv_to_split
*const i1
= (const struct iv_to_split
*) ivts1
;
1546 const struct iv_to_split
*const i2
= (const struct iv_to_split
*) ivts2
;
1548 return i1
->insn
== i2
->insn
;
1551 /* Return a hash for VES, which is really a "var_to_expand *". */
1554 ve_info_hash (const void *ves
)
1556 return (hashval_t
) INSN_UID (((const struct var_to_expand
*) ves
)->insn
);
1559 /* Return true if IVTS1 and IVTS2 (which are really both of type
1560 "var_to_expand *") refer to the same instruction. */
1563 ve_info_eq (const void *ivts1
, const void *ivts2
)
1565 const struct var_to_expand
*const i1
= (const struct var_to_expand
*) ivts1
;
1566 const struct var_to_expand
*const i2
= (const struct var_to_expand
*) ivts2
;
1568 return i1
->insn
== i2
->insn
;
1571 /* Returns true if REG is referenced in one nondebug insn in LOOP.
1572 Set *DEBUG_USES to the number of debug insns that reference the
1576 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
,
1579 basic_block
*body
, bb
;
1584 body
= get_loop_body (loop
);
1585 for (i
= 0; i
< loop
->num_nodes
; i
++)
1589 FOR_BB_INSNS (bb
, insn
)
1590 if (!rtx_referenced_p (reg
, insn
))
1592 else if (DEBUG_INSN_P (insn
))
1594 else if (++count_ref
> 1)
1598 return (count_ref
== 1);
1601 /* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1604 reset_debug_uses_in_loop (struct loop
*loop
, rtx reg
, int debug_uses
)
1606 basic_block
*body
, bb
;
1610 body
= get_loop_body (loop
);
1611 for (i
= 0; debug_uses
&& i
< loop
->num_nodes
; i
++)
1615 FOR_BB_INSNS (bb
, insn
)
1616 if (!DEBUG_INSN_P (insn
) || !rtx_referenced_p (reg
, insn
))
1620 validate_change (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1621 gen_rtx_UNKNOWN_VAR_LOC (), 0);
1629 /* Determine whether INSN contains an accumulator
1630 which can be expanded into separate copies,
1631 one for each copy of the LOOP body.
1633 for (i = 0 ; i < n; i++)
1647 Return NULL if INSN contains no opportunity for expansion of accumulator.
1648 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1649 information and return a pointer to it.
1652 static struct var_to_expand
*
1653 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1656 struct var_to_expand
*ves
;
1661 set
= single_set (insn
);
1665 dest
= SET_DEST (set
);
1666 src
= SET_SRC (set
);
1667 code
= GET_CODE (src
);
1669 if (code
!= PLUS
&& code
!= MINUS
&& code
!= MULT
&& code
!= FMA
)
1672 if (FLOAT_MODE_P (GET_MODE (dest
)))
1674 if (!flag_associative_math
)
1676 /* In the case of FMA, we're also changing the rounding. */
1677 if (code
== FMA
&& !flag_unsafe_math_optimizations
)
1681 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1682 in MD. But if there is no optab to generate the insn, we can not
1683 perform the variable expansion. This can happen if an MD provides
1684 an insn but not a named pattern to generate it, for example to avoid
1685 producing code that needs additional mode switches like for x87/mmx.
1687 So we check have_insn_for which looks for an optab for the operation
1688 in SRC. If it doesn't exist, we can't perform the expansion even
1689 though INSN is valid. */
1690 if (!have_insn_for (code
, GET_MODE (src
)))
1694 && !(GET_CODE (dest
) == SUBREG
1695 && REG_P (SUBREG_REG (dest
))))
1698 /* Find the accumulator use within the operation. */
1701 /* We only support accumulation via FMA in the ADD position. */
1702 if (!rtx_equal_p (dest
, XEXP (src
, 2)))
1706 else if (rtx_equal_p (dest
, XEXP (src
, 0)))
1708 else if (rtx_equal_p (dest
, XEXP (src
, 1)))
1710 /* The method of expansion that we are using; which includes the
1711 initialization of the expansions with zero and the summation of
1712 the expansions at the end of the computation will yield wrong
1713 results for (x = something - x) thus avoid using it in that case. */
1721 /* It must not otherwise be used. */
1724 if (rtx_referenced_p (dest
, XEXP (src
, 0))
1725 || rtx_referenced_p (dest
, XEXP (src
, 1)))
1728 else if (rtx_referenced_p (dest
, XEXP (src
, 1 - accum_pos
)))
1731 /* It must be used in exactly one insn. */
1732 if (!referenced_in_one_insn_in_loop_p (loop
, dest
, &debug_uses
))
1737 fprintf (dump_file
, "\n;; Expanding Accumulator ");
1738 print_rtl (dump_file
, dest
);
1739 fprintf (dump_file
, "\n");
1743 /* Instead of resetting the debug insns, we could replace each
1744 debug use in the loop with the sum or product of all expanded
1745 accummulators. Since we'll only know of all expansions at the
1746 end, we'd have to keep track of which vars_to_expand a debug
1747 insn in the loop references, take note of each copy of the
1748 debug insn during unrolling, and when it's all done, compute
1749 the sum or product of each variable and adjust the original
1750 debug insn and each copy thereof. What a pain! */
1751 reset_debug_uses_in_loop (loop
, dest
, debug_uses
);
1753 /* Record the accumulator to expand. */
1754 ves
= XNEW (struct var_to_expand
);
1756 ves
->reg
= copy_rtx (dest
);
1757 ves
->var_expansions
= VEC_alloc (rtx
, heap
, 1);
1759 ves
->op
= GET_CODE (src
);
1760 ves
->expansion_count
= 0;
1761 ves
->reuse_expansion
= 0;
1765 /* Determine whether there is an induction variable in INSN that
1766 we would like to split during unrolling.
1786 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1787 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1790 static struct iv_to_split
*
1791 analyze_iv_to_split_insn (rtx insn
)
1795 struct iv_to_split
*ivts
;
1798 /* For now we just split the basic induction variables. Later this may be
1799 extended for example by selecting also addresses of memory references. */
1800 set
= single_set (insn
);
1804 dest
= SET_DEST (set
);
1808 if (!biv_p (insn
, dest
))
1811 ok
= iv_analyze_result (insn
, dest
, &iv
);
1813 /* This used to be an assert under the assumption that if biv_p returns
1814 true that iv_analyze_result must also return true. However, that
1815 assumption is not strictly correct as evidenced by pr25569.
1817 Returning NULL when iv_analyze_result returns false is safe and
1818 avoids the problems in pr25569 until the iv_analyze_* routines
1819 can be fixed, which is apparently hard and time consuming
1820 according to their author. */
1824 if (iv
.step
== const0_rtx
1825 || iv
.mode
!= iv
.extend_mode
)
1828 /* Record the insn to split. */
1829 ivts
= XNEW (struct iv_to_split
);
1831 ivts
->base_var
= NULL_RTX
;
1832 ivts
->step
= iv
.step
;
1840 /* Determines which of insns in LOOP can be optimized.
1841 Return a OPT_INFO struct with the relevant hash tables filled
1842 with all insns to be optimized. The FIRST_NEW_BLOCK field
1843 is undefined for the return value. */
1845 static struct opt_info
*
1846 analyze_insns_in_loop (struct loop
*loop
)
1848 basic_block
*body
, bb
;
1850 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
1852 struct iv_to_split
*ivts
= NULL
;
1853 struct var_to_expand
*ves
= NULL
;
1856 VEC (edge
, heap
) *edges
= get_loop_exit_edges (loop
);
1858 bool can_apply
= false;
1860 iv_analysis_loop_init (loop
);
1862 body
= get_loop_body (loop
);
1864 if (flag_split_ivs_in_unroller
)
1866 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1867 si_info_hash
, si_info_eq
, free
);
1868 opt_info
->iv_to_split_head
= NULL
;
1869 opt_info
->iv_to_split_tail
= &opt_info
->iv_to_split_head
;
1872 /* Record the loop exit bb and loop preheader before the unrolling. */
1873 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1875 if (VEC_length (edge
, edges
) == 1)
1877 exit
= VEC_index (edge
, edges
, 0);
1878 if (!(exit
->flags
& EDGE_COMPLEX
))
1880 opt_info
->loop_exit
= split_edge (exit
);
1885 if (flag_variable_expansion_in_unroller
1888 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1891 opt_info
->var_to_expand_head
= NULL
;
1892 opt_info
->var_to_expand_tail
= &opt_info
->var_to_expand_head
;
1895 for (i
= 0; i
< loop
->num_nodes
; i
++)
1898 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1901 FOR_BB_INSNS (bb
, insn
)
1906 if (opt_info
->insns_to_split
)
1907 ivts
= analyze_iv_to_split_insn (insn
);
1911 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1912 gcc_assert (*slot1
== NULL
);
1914 *opt_info
->iv_to_split_tail
= ivts
;
1915 opt_info
->iv_to_split_tail
= &ivts
->next
;
1919 if (opt_info
->insns_with_var_to_expand
)
1920 ves
= analyze_insn_to_expand_var (loop
, insn
);
1924 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1925 gcc_assert (*slot2
== NULL
);
1927 *opt_info
->var_to_expand_tail
= ves
;
1928 opt_info
->var_to_expand_tail
= &ves
->next
;
1933 VEC_free (edge
, heap
, edges
);
1938 /* Called just before loop duplication. Records start of duplicated area
1942 opt_info_start_duplication (struct opt_info
*opt_info
)
1945 opt_info
->first_new_block
= last_basic_block
;
1948 /* Determine the number of iterations between initialization of the base
1949 variable and the current copy (N_COPY). N_COPIES is the total number
1950 of newly created copies. UNROLLING is true if we are unrolling
1951 (not peeling) the loop. */
1954 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1958 /* If we are unrolling, initialization is done in the original loop
1964 /* If we are peeling, the copy in that the initialization occurs has
1965 number 1. The original loop (number 0) is the last. */
1973 /* Locate in EXPR the expression corresponding to the location recorded
1974 in IVTS, and return a pointer to the RTX for this location. */
1977 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1982 for (i
= 0; i
< ivts
->n_loc
; i
++)
1983 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1988 /* Allocate basic variable for the induction variable chain. */
1991 allocate_basic_variable (struct iv_to_split
*ivts
)
1993 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1995 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1998 /* Insert initialization of basic variable of IVTS before INSN, taking
1999 the initial value from INSN. */
2002 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
2004 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
2008 expr
= force_operand (expr
, ivts
->base_var
);
2009 if (expr
!= ivts
->base_var
)
2010 emit_move_insn (ivts
->base_var
, expr
);
2014 emit_insn_before (seq
, insn
);
2017 /* Replace the use of induction variable described in IVTS in INSN
2018 by base variable + DELTA * step. */
2021 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
2023 rtx expr
, *loc
, seq
, incr
, var
;
2024 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
2027 /* Construct base + DELTA * step. */
2029 expr
= ivts
->base_var
;
2032 incr
= simplify_gen_binary (MULT
, mode
,
2033 ivts
->step
, gen_int_mode (delta
, mode
));
2034 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
2035 ivts
->base_var
, incr
);
2038 /* Figure out where to do the replacement. */
2039 loc
= get_ivts_expr (single_set (insn
), ivts
);
2041 /* If we can make the replacement right away, we're done. */
2042 if (validate_change (insn
, loc
, expr
, 0))
2045 /* Otherwise, force EXPR into a register and try again. */
2047 var
= gen_reg_rtx (mode
);
2048 expr
= force_operand (expr
, var
);
2050 emit_move_insn (var
, expr
);
2053 emit_insn_before (seq
, insn
);
2055 if (validate_change (insn
, loc
, var
, 0))
2058 /* The last chance. Try recreating the assignment in insn
2059 completely from scratch. */
2060 set
= single_set (insn
);
2065 src
= copy_rtx (SET_SRC (set
));
2066 dest
= copy_rtx (SET_DEST (set
));
2067 src
= force_operand (src
, dest
);
2069 emit_move_insn (dest
, src
);
2073 emit_insn_before (seq
, insn
);
2078 /* Return one expansion of the accumulator recorded in struct VE. */
2081 get_expansion (struct var_to_expand
*ve
)
2085 if (ve
->reuse_expansion
== 0)
2088 reg
= VEC_index (rtx
, ve
->var_expansions
, ve
->reuse_expansion
- 1);
2090 if (VEC_length (rtx
, ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
2091 ve
->reuse_expansion
= 0;
2093 ve
->reuse_expansion
++;
2099 /* Given INSN replace the uses of the accumulator recorded in VE
2100 with a new register. */
2103 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
2106 bool really_new_expansion
= false;
2108 set
= single_set (insn
);
2111 /* Generate a new register only if the expansion limit has not been
2112 reached. Else reuse an already existing expansion. */
2113 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
2115 really_new_expansion
= true;
2116 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
2119 new_reg
= get_expansion (ve
);
2121 validate_replace_rtx_group (SET_DEST (set
), new_reg
, insn
);
2122 if (apply_change_group ())
2123 if (really_new_expansion
)
2125 VEC_safe_push (rtx
, heap
, ve
->var_expansions
, new_reg
);
2126 ve
->expansion_count
++;
2130 /* Initialize the variable expansions in loop preheader. PLACE is the
2131 loop-preheader basic block where the initialization of the
2132 expansions should take place. The expansions are initialized with
2133 (-0) when the operation is plus or minus to honor sign zero. This
2134 way we can prevent cases where the sign of the final result is
2135 effected by the sign of the expansion. Here is an example to
2138 for (i = 0 ; i < n; i++)
2152 When SUM is initialized with -zero and SOMETHING is also -zero; the
2153 final result of sum should be -zero thus the expansions sum1 and sum2
2154 should be initialized with -zero as well (otherwise we will get +zero
2155 as the final result). */
2158 insert_var_expansion_initialization (struct var_to_expand
*ve
,
2161 rtx seq
, var
, zero_init
;
2163 enum machine_mode mode
= GET_MODE (ve
->reg
);
2164 bool honor_signed_zero_p
= HONOR_SIGNED_ZEROS (mode
);
2166 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2173 /* Note that we only accumulate FMA via the ADD operand. */
2176 FOR_EACH_VEC_ELT (rtx
, ve
->var_expansions
, i
, var
)
2178 if (honor_signed_zero_p
)
2179 zero_init
= simplify_gen_unary (NEG
, mode
, CONST0_RTX (mode
), mode
);
2181 zero_init
= CONST0_RTX (mode
);
2182 emit_move_insn (var
, zero_init
);
2187 FOR_EACH_VEC_ELT (rtx
, ve
->var_expansions
, i
, var
)
2189 zero_init
= CONST1_RTX (GET_MODE (var
));
2190 emit_move_insn (var
, zero_init
);
2201 emit_insn_after (seq
, BB_END (place
));
2204 /* Combine the variable expansions at the loop exit. PLACE is the
2205 loop exit basic block where the summation of the expansions should
2209 combine_var_copies_in_loop_exit (struct var_to_expand
*ve
, basic_block place
)
2212 rtx expr
, seq
, var
, insn
;
2215 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2222 /* Note that we only accumulate FMA via the ADD operand. */
2225 FOR_EACH_VEC_ELT (rtx
, ve
->var_expansions
, i
, var
)
2226 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
), var
, sum
);
2230 FOR_EACH_VEC_ELT (rtx
, ve
->var_expansions
, i
, var
)
2231 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
), var
, sum
);
2238 expr
= force_operand (sum
, ve
->reg
);
2239 if (expr
!= ve
->reg
)
2240 emit_move_insn (ve
->reg
, expr
);
2244 insn
= BB_HEAD (place
);
2245 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2246 insn
= NEXT_INSN (insn
);
2248 emit_insn_after (seq
, insn
);
2251 /* Apply loop optimizations in loop copies using the
2252 data which gathered during the unrolling. Structure
2253 OPT_INFO record that data.
2255 UNROLLING is true if we unrolled (not peeled) the loop.
2256 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2257 the loop (as it should happen in complete unrolling, but not in ordinary
2258 peeling of the loop). */
2261 apply_opt_in_copies (struct opt_info
*opt_info
,
2262 unsigned n_copies
, bool unrolling
,
2263 bool rewrite_original_loop
)
2266 basic_block bb
, orig_bb
;
2267 rtx insn
, orig_insn
, next
;
2268 struct iv_to_split ivts_templ
, *ivts
;
2269 struct var_to_expand ve_templ
, *ves
;
2271 /* Sanity check -- we need to put initialization in the original loop
2273 gcc_assert (!unrolling
|| rewrite_original_loop
);
2275 /* Allocate the basic variables (i0). */
2276 if (opt_info
->insns_to_split
)
2277 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
2278 allocate_basic_variable (ivts
);
2280 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2282 bb
= BASIC_BLOCK (i
);
2283 orig_bb
= get_bb_original (bb
);
2285 /* bb->aux holds position in copy sequence initialized by
2286 duplicate_loop_to_header_edge. */
2287 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2290 orig_insn
= BB_HEAD (orig_bb
);
2291 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2293 next
= NEXT_INSN (insn
);
2295 || (DEBUG_INSN_P (insn
)
2296 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
))
2299 while (!INSN_P (orig_insn
)
2300 || (DEBUG_INSN_P (orig_insn
)
2301 && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn
))
2303 orig_insn
= NEXT_INSN (orig_insn
);
2305 ivts_templ
.insn
= orig_insn
;
2306 ve_templ
.insn
= orig_insn
;
2308 /* Apply splitting iv optimization. */
2309 if (opt_info
->insns_to_split
)
2311 ivts
= (struct iv_to_split
*)
2312 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2316 gcc_assert (GET_CODE (PATTERN (insn
))
2317 == GET_CODE (PATTERN (orig_insn
)));
2320 insert_base_initialization (ivts
, insn
);
2321 split_iv (ivts
, insn
, delta
);
2324 /* Apply variable expansion optimization. */
2325 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2327 ves
= (struct var_to_expand
*)
2328 htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2331 gcc_assert (GET_CODE (PATTERN (insn
))
2332 == GET_CODE (PATTERN (orig_insn
)));
2333 expand_var_during_unrolling (ves
, insn
);
2336 orig_insn
= NEXT_INSN (orig_insn
);
2340 if (!rewrite_original_loop
)
2343 /* Initialize the variable expansions in the loop preheader
2344 and take care of combining them at the loop exit. */
2345 if (opt_info
->insns_with_var_to_expand
)
2347 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2348 insert_var_expansion_initialization (ves
, opt_info
->loop_preheader
);
2349 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2350 combine_var_copies_in_loop_exit (ves
, opt_info
->loop_exit
);
2353 /* Rewrite also the original loop body. Find them as originals of the blocks
2354 in the last copied iteration, i.e. those that have
2355 get_bb_copy (get_bb_original (bb)) == bb. */
2356 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2358 bb
= BASIC_BLOCK (i
);
2359 orig_bb
= get_bb_original (bb
);
2360 if (get_bb_copy (orig_bb
) != bb
)
2363 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2364 for (orig_insn
= BB_HEAD (orig_bb
);
2365 orig_insn
!= NEXT_INSN (BB_END (bb
));
2368 next
= NEXT_INSN (orig_insn
);
2370 if (!INSN_P (orig_insn
))
2373 ivts_templ
.insn
= orig_insn
;
2374 if (opt_info
->insns_to_split
)
2376 ivts
= (struct iv_to_split
*)
2377 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2381 insert_base_initialization (ivts
, orig_insn
);
2382 split_iv (ivts
, orig_insn
, delta
);
2391 /* Release OPT_INFO. */
2394 free_opt_info (struct opt_info
*opt_info
)
2396 if (opt_info
->insns_to_split
)
2397 htab_delete (opt_info
->insns_to_split
);
2398 if (opt_info
->insns_with_var_to_expand
)
2400 struct var_to_expand
*ves
;
2402 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2403 VEC_free (rtx
, heap
, ves
->var_expansions
);
2404 htab_delete (opt_info
->insns_with_var_to_expand
);