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 orig_var
; /* The variable (register) for the IV before split. */
78 rtx base_var
; /* The variable on that the values in the further
79 iterations are based. */
80 rtx step
; /* Step of the induction variable. */
81 struct iv_to_split
*next
; /* Next entry in walking order. */
83 unsigned loc
[3]; /* Location where the definition of the induction
84 variable occurs in the insn. For example if
85 N_LOC is 2, the expression is located at
86 XEXP (XEXP (single_set, loc[0]), loc[1]). */
89 /* Information about accumulators to expand. */
93 rtx insn
; /* The insn in that the variable expansion occurs. */
94 rtx reg
; /* The accumulator which is expanded. */
95 vec
<rtx
> var_expansions
; /* The copies of the accumulator which is expanded. */
96 struct var_to_expand
*next
; /* Next entry in walking order. */
97 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
99 int expansion_count
; /* Count the number of expansions generated so far. */
100 int reuse_expansion
; /* The expansion we intend to reuse to expand
101 the accumulator. If REUSE_EXPANSION is 0 reuse
102 the original accumulator. Else use
103 var_expansions[REUSE_EXPANSION - 1]. */
106 /* Information about optimization applied in
107 the unrolled loop. */
111 htab_t insns_to_split
; /* A hashtable of insns to split. */
112 struct iv_to_split
*iv_to_split_head
; /* The first iv to split. */
113 struct iv_to_split
**iv_to_split_tail
; /* Pointer to the tail of the list. */
114 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
116 struct var_to_expand
*var_to_expand_head
; /* The first var to expand. */
117 struct var_to_expand
**var_to_expand_tail
; /* Pointer to the tail of the list. */
118 unsigned first_new_block
; /* The first basic block that was
120 basic_block loop_exit
; /* The loop exit basic block. */
121 basic_block loop_preheader
; /* The loop preheader basic block. */
124 static void decide_unrolling_and_peeling (int);
125 static void peel_loops_completely (int);
126 static void decide_peel_simple (struct loop
*, int);
127 static void decide_peel_once_rolling (struct loop
*, int);
128 static void decide_peel_completely (struct loop
*, int);
129 static void decide_unroll_stupid (struct loop
*, int);
130 static void decide_unroll_constant_iterations (struct loop
*, int);
131 static void decide_unroll_runtime_iterations (struct loop
*, int);
132 static void peel_loop_simple (struct loop
*);
133 static void peel_loop_completely (struct loop
*);
134 static void unroll_loop_stupid (struct loop
*);
135 static void unroll_loop_constant_iterations (struct loop
*);
136 static void unroll_loop_runtime_iterations (struct loop
*);
137 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
138 static void opt_info_start_duplication (struct opt_info
*);
139 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
140 static void free_opt_info (struct opt_info
*);
141 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
142 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
, int *);
143 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
144 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
145 static void insert_var_expansion_initialization (struct var_to_expand
*,
147 static void combine_var_copies_in_loop_exit (struct var_to_expand
*,
149 static rtx
get_expansion (struct var_to_expand
*);
151 /* Emit a message summarizing the unroll or peel that will be
152 performed for LOOP, along with the loop's location LOCUS, if
153 appropriate given the dump or -fopt-info settings. */
156 report_unroll_peel (struct loop
*loop
, location_t locus
)
158 struct niter_desc
*desc
;
160 int report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_RTL
| TDF_DETAILS
;
162 if (!dump_enabled_p ())
165 /* In the special case where the loop never iterated, emit
166 a different message so that we don't report an unroll by 0.
167 This matches the equivalent message emitted during tree unrolling. */
168 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
169 && !loop
->lpt_decision
.times
)
171 dump_printf_loc (report_flags
, locus
,
172 "Turned loop into non-loop; it never loops.\n");
176 desc
= get_simple_loop_desc (loop
);
178 if (desc
->const_iter
)
179 niters
= desc
->niter
;
180 else if (loop
->header
->count
)
181 niters
= expected_loop_iterations (loop
);
183 dump_printf_loc (report_flags
, locus
,
185 (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
186 ? "Completely unroll"
187 : (loop
->lpt_decision
.decision
== LPT_PEEL_SIMPLE
188 ? "Peel" : "Unroll")),
189 loop
->lpt_decision
.times
);
191 dump_printf (report_flags
,
192 " (header execution count %d",
193 (int)loop
->header
->count
);
194 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
195 dump_printf (report_flags
,
196 "%s%s iterations %d)",
197 profile_info
? ", " : " (",
198 desc
->const_iter
? "const" : "average",
200 else if (profile_info
)
201 dump_printf (report_flags
, ")");
203 dump_printf (report_flags
, "\n");
206 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
208 unroll_and_peel_loops (int flags
)
214 /* First perform complete loop peeling (it is almost surely a win,
215 and affects parameters for further decision a lot). */
216 peel_loops_completely (flags
);
218 /* Now decide rest of unrolling and peeling. */
219 decide_unrolling_and_peeling (flags
);
221 /* Scan the loops, inner ones first. */
222 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
225 /* And perform the appropriate transformations. */
226 switch (loop
->lpt_decision
.decision
)
228 case LPT_PEEL_COMPLETELY
:
231 case LPT_PEEL_SIMPLE
:
232 peel_loop_simple (loop
);
234 case LPT_UNROLL_CONSTANT
:
235 unroll_loop_constant_iterations (loop
);
237 case LPT_UNROLL_RUNTIME
:
238 unroll_loop_runtime_iterations (loop
);
240 case LPT_UNROLL_STUPID
:
241 unroll_loop_stupid (loop
);
251 #ifdef ENABLE_CHECKING
252 verify_loop_structure ();
260 /* Check whether exit of the LOOP is at the end of loop body. */
263 loop_exit_at_end_p (struct loop
*loop
)
265 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
268 if (desc
->in_edge
->dest
!= loop
->latch
)
271 /* Check that the latch is empty. */
272 FOR_BB_INSNS (loop
->latch
, insn
)
274 if (NONDEBUG_INSN_P (insn
))
281 /* Depending on FLAGS, check whether to peel loops completely and do so. */
283 peel_loops_completely (int flags
)
288 /* Scan the loops, the inner ones first. */
289 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
291 loop
->lpt_decision
.decision
= LPT_NONE
;
292 location_t locus
= get_loop_location (loop
);
294 if (dump_enabled_p ())
295 dump_printf_loc (TDF_RTL
, locus
,
296 ";; *** Considering loop %d at BB %d for "
297 "complete peeling ***\n",
298 loop
->num
, loop
->header
->index
);
300 loop
->ninsns
= num_loop_insns (loop
);
302 decide_peel_once_rolling (loop
, flags
);
303 if (loop
->lpt_decision
.decision
== LPT_NONE
)
304 decide_peel_completely (loop
, flags
);
306 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
308 report_unroll_peel (loop
, locus
);
309 peel_loop_completely (loop
);
310 #ifdef ENABLE_CHECKING
311 verify_loop_structure ();
317 /* Decide whether unroll or peel loops (depending on FLAGS) and how much. */
319 decide_unrolling_and_peeling (int flags
)
324 /* Scan the loops, inner ones first. */
325 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
327 loop
->lpt_decision
.decision
= LPT_NONE
;
328 location_t locus
= get_loop_location (loop
);
330 if (dump_enabled_p ())
331 dump_printf_loc (TDF_RTL
, locus
,
332 ";; *** Considering loop %d at BB %d for "
333 "unrolling and peeling ***\n",
334 loop
->num
, loop
->header
->index
);
336 /* Do not peel cold areas. */
337 if (optimize_loop_for_size_p (loop
))
340 fprintf (dump_file
, ";; Not considering loop, cold area\n");
344 /* Can the loop be manipulated? */
345 if (!can_duplicate_loop_p (loop
))
349 ";; Not considering loop, cannot duplicate\n");
353 /* Skip non-innermost loops. */
357 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
361 loop
->ninsns
= num_loop_insns (loop
);
362 loop
->av_ninsns
= average_num_loop_insns (loop
);
364 /* Try transformations one by one in decreasing order of
367 decide_unroll_constant_iterations (loop
, flags
);
368 if (loop
->lpt_decision
.decision
== LPT_NONE
)
369 decide_unroll_runtime_iterations (loop
, flags
);
370 if (loop
->lpt_decision
.decision
== LPT_NONE
)
371 decide_unroll_stupid (loop
, flags
);
372 if (loop
->lpt_decision
.decision
== LPT_NONE
)
373 decide_peel_simple (loop
, flags
);
375 report_unroll_peel (loop
, locus
);
379 /* Decide whether the LOOP is once rolling and suitable for complete
382 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
384 struct niter_desc
*desc
;
387 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
389 /* Is the loop small enough? */
390 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
393 fprintf (dump_file
, ";; Not considering loop, is too big\n");
397 /* Check for simple loops. */
398 desc
= get_simple_loop_desc (loop
);
400 /* Check number of iterations. */
406 && max_loop_iterations_int (loop
) != 0))
410 ";; Unable to prove that the loop rolls exactly once\n");
415 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
418 /* Decide whether the LOOP is suitable for complete peeling. */
420 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
423 struct niter_desc
*desc
;
426 fprintf (dump_file
, "\n;; Considering peeling completely\n");
428 /* Skip non-innermost loops. */
432 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
436 /* Do not peel cold areas. */
437 if (optimize_loop_for_size_p (loop
))
440 fprintf (dump_file
, ";; Not considering loop, cold area\n");
444 /* Can the loop be manipulated? */
445 if (!can_duplicate_loop_p (loop
))
449 ";; Not considering loop, cannot duplicate\n");
453 /* npeel = number of iterations to peel. */
454 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
455 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
456 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
458 /* Is the loop small enough? */
462 fprintf (dump_file
, ";; Not considering loop, is too big\n");
466 /* Check for simple loops. */
467 desc
= get_simple_loop_desc (loop
);
469 /* Check number of iterations. */
477 ";; Unable to prove that the loop iterates constant times\n");
481 if (desc
->niter
> npeel
- 1)
486 ";; Not peeling loop completely, rolls too much (");
487 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
488 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
494 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
497 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
498 completely. The transformation done:
500 for (i = 0; i < 4; i++)
512 peel_loop_completely (struct loop
*loop
)
515 unsigned HOST_WIDE_INT npeel
;
517 vec
<edge
> remove_edges
;
519 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
520 struct opt_info
*opt_info
= NULL
;
528 wont_exit
= sbitmap_alloc (npeel
+ 1);
529 bitmap_ones (wont_exit
);
530 bitmap_clear_bit (wont_exit
, 0);
531 if (desc
->noloop_assumptions
)
532 bitmap_clear_bit (wont_exit
, 1);
534 remove_edges
.create (0);
536 if (flag_split_ivs_in_unroller
)
537 opt_info
= analyze_insns_in_loop (loop
);
539 opt_info_start_duplication (opt_info
);
540 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
542 wont_exit
, desc
->out_edge
,
544 DLTHE_FLAG_UPDATE_FREQ
545 | DLTHE_FLAG_COMPLETTE_PEEL
547 ? DLTHE_RECORD_COPY_NUMBER
: 0));
554 apply_opt_in_copies (opt_info
, npeel
, false, true);
555 free_opt_info (opt_info
);
558 /* Remove the exit edges. */
559 FOR_EACH_VEC_ELT (remove_edges
, i
, ein
)
561 remove_edges
.release ();
565 free_simple_loop_desc (loop
);
567 /* Now remove the unreachable part of the last iteration and cancel
572 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
575 /* Decide whether to unroll LOOP iterating constant number of times
579 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
581 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
582 struct niter_desc
*desc
;
583 double_int iterations
;
585 if (!(flags
& UAP_UNROLL
))
587 /* We were not asked to, just return back silently. */
593 "\n;; Considering unrolling loop with constant "
594 "number of iterations\n");
596 /* nunroll = total number of copies of the original loop body in
597 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
598 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
600 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
601 if (nunroll
> nunroll_by_av
)
602 nunroll
= nunroll_by_av
;
603 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
604 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
606 /* Skip big loops. */
610 fprintf (dump_file
, ";; Not considering loop, is too big\n");
614 /* Check for simple loops. */
615 desc
= get_simple_loop_desc (loop
);
617 /* Check number of iterations. */
618 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
622 ";; Unable to prove that the loop iterates constant times\n");
626 /* Check whether the loop rolls enough to consider.
627 Consult also loop bounds and profile; in the case the loop has more
628 than one exit it may well loop less than determined maximal number
630 if (desc
->niter
< 2 * nunroll
631 || ((estimated_loop_iterations (loop
, &iterations
)
632 || max_loop_iterations (loop
, &iterations
))
633 && iterations
.ult (double_int::from_shwi (2 * nunroll
))))
636 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
640 /* Success; now compute number of iterations to unroll. We alter
641 nunroll so that as few as possible copies of loop body are
642 necessary, while still not decreasing the number of unrollings
643 too much (at most by 1). */
644 best_copies
= 2 * nunroll
+ 10;
647 if (i
- 1 >= desc
->niter
)
650 for (; i
>= nunroll
- 1; i
--)
652 unsigned exit_mod
= desc
->niter
% (i
+ 1);
654 if (!loop_exit_at_end_p (loop
))
655 n_copies
= exit_mod
+ i
+ 1;
656 else if (exit_mod
!= (unsigned) i
657 || desc
->noloop_assumptions
!= NULL_RTX
)
658 n_copies
= exit_mod
+ i
+ 2;
662 if (n_copies
< best_copies
)
664 best_copies
= n_copies
;
669 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
670 loop
->lpt_decision
.times
= best_unroll
;
673 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
674 The transformation does this:
676 for (i = 0; i < 102; i++)
679 ==> (LOOP->LPT_DECISION.TIMES == 3)
693 unroll_loop_constant_iterations (struct loop
*loop
)
695 unsigned HOST_WIDE_INT niter
;
699 vec
<edge
> remove_edges
;
701 unsigned max_unroll
= loop
->lpt_decision
.times
;
702 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
703 bool exit_at_end
= loop_exit_at_end_p (loop
);
704 struct opt_info
*opt_info
= NULL
;
709 /* Should not get here (such loop should be peeled instead). */
710 gcc_assert (niter
> max_unroll
+ 1);
712 exit_mod
= niter
% (max_unroll
+ 1);
714 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
715 bitmap_ones (wont_exit
);
717 remove_edges
.create (0);
718 if (flag_split_ivs_in_unroller
719 || flag_variable_expansion_in_unroller
)
720 opt_info
= analyze_insns_in_loop (loop
);
724 /* The exit is not at the end of the loop; leave exit test
725 in the first copy, so that the loops that start with test
726 of exit condition have continuous body after unrolling. */
729 fprintf (dump_file
, ";; Condition at beginning of loop.\n");
731 /* Peel exit_mod iterations. */
732 bitmap_clear_bit (wont_exit
, 0);
733 if (desc
->noloop_assumptions
)
734 bitmap_clear_bit (wont_exit
, 1);
738 opt_info_start_duplication (opt_info
);
739 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
741 wont_exit
, desc
->out_edge
,
743 DLTHE_FLAG_UPDATE_FREQ
744 | (opt_info
&& exit_mod
> 1
745 ? DLTHE_RECORD_COPY_NUMBER
749 if (opt_info
&& exit_mod
> 1)
750 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
752 desc
->noloop_assumptions
= NULL_RTX
;
753 desc
->niter
-= exit_mod
;
754 loop
->nb_iterations_upper_bound
-= double_int::from_uhwi (exit_mod
);
755 if (loop
->any_estimate
756 && double_int::from_uhwi (exit_mod
).ule
757 (loop
->nb_iterations_estimate
))
758 loop
->nb_iterations_estimate
-= double_int::from_uhwi (exit_mod
);
760 loop
->any_estimate
= false;
763 bitmap_set_bit (wont_exit
, 1);
767 /* Leave exit test in last copy, for the same reason as above if
768 the loop tests the condition at the end of loop body. */
771 fprintf (dump_file
, ";; Condition at end of loop.\n");
773 /* We know that niter >= max_unroll + 2; so we do not need to care of
774 case when we would exit before reaching the loop. So just peel
775 exit_mod + 1 iterations. */
776 if (exit_mod
!= max_unroll
777 || desc
->noloop_assumptions
)
779 bitmap_clear_bit (wont_exit
, 0);
780 if (desc
->noloop_assumptions
)
781 bitmap_clear_bit (wont_exit
, 1);
783 opt_info_start_duplication (opt_info
);
784 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
786 wont_exit
, desc
->out_edge
,
788 DLTHE_FLAG_UPDATE_FREQ
789 | (opt_info
&& exit_mod
> 0
790 ? DLTHE_RECORD_COPY_NUMBER
794 if (opt_info
&& exit_mod
> 0)
795 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
797 desc
->niter
-= exit_mod
+ 1;
798 loop
->nb_iterations_upper_bound
-= double_int::from_uhwi (exit_mod
+ 1);
799 if (loop
->any_estimate
800 && double_int::from_uhwi (exit_mod
+ 1).ule
801 (loop
->nb_iterations_estimate
))
802 loop
->nb_iterations_estimate
-= double_int::from_uhwi (exit_mod
+ 1);
804 loop
->any_estimate
= false;
805 desc
->noloop_assumptions
= NULL_RTX
;
807 bitmap_set_bit (wont_exit
, 0);
808 bitmap_set_bit (wont_exit
, 1);
811 bitmap_clear_bit (wont_exit
, max_unroll
);
814 /* Now unroll the loop. */
816 opt_info_start_duplication (opt_info
);
817 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
819 wont_exit
, desc
->out_edge
,
821 DLTHE_FLAG_UPDATE_FREQ
823 ? DLTHE_RECORD_COPY_NUMBER
829 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
830 free_opt_info (opt_info
);
837 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
838 /* Find a new in and out edge; they are in the last copy we have made. */
840 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
842 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
843 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
847 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
848 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
852 desc
->niter
/= max_unroll
+ 1;
853 loop
->nb_iterations_upper_bound
854 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (max_unroll
857 if (loop
->any_estimate
)
858 loop
->nb_iterations_estimate
859 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (max_unroll
862 desc
->niter_expr
= GEN_INT (desc
->niter
);
864 /* Remove the edges. */
865 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
867 remove_edges
.release ();
871 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
872 max_unroll
, num_loop_insns (loop
));
875 /* Decide whether to unroll LOOP iterating runtime computable number of times
878 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
880 unsigned nunroll
, nunroll_by_av
, i
;
881 struct niter_desc
*desc
;
882 double_int iterations
;
884 if (!(flags
& UAP_UNROLL
))
886 /* We were not asked to, just return back silently. */
892 "\n;; Considering unrolling loop with runtime "
893 "computable number of iterations\n");
895 /* nunroll = total number of copies of the original loop body in
896 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
897 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
898 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
899 if (nunroll
> nunroll_by_av
)
900 nunroll
= nunroll_by_av
;
901 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
902 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
904 if (targetm
.loop_unroll_adjust
)
905 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
907 /* Skip big loops. */
911 fprintf (dump_file
, ";; Not considering loop, is too big\n");
915 /* Check for simple loops. */
916 desc
= get_simple_loop_desc (loop
);
918 /* Check simpleness. */
919 if (!desc
->simple_p
|| desc
->assumptions
)
923 ";; Unable to prove that the number of iterations "
924 "can be counted in runtime\n");
928 if (desc
->const_iter
)
931 fprintf (dump_file
, ";; Loop iterates constant times\n");
935 /* Check whether the loop rolls. */
936 if ((estimated_loop_iterations (loop
, &iterations
)
937 || max_loop_iterations (loop
, &iterations
))
938 && iterations
.ult (double_int::from_shwi (2 * nunroll
)))
941 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
945 /* Success; now force nunroll to be power of 2, as we are unable to
946 cope with overflows in computation of number of iterations. */
947 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
950 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
951 loop
->lpt_decision
.times
= i
- 1;
954 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
955 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
956 and NULL is returned instead. */
959 split_edge_and_insert (edge e
, rtx insns
)
966 emit_insn_after (insns
, BB_END (bb
));
968 /* ??? We used to assume that INSNS can contain control flow insns, and
969 that we had to try to find sub basic blocks in BB to maintain a valid
970 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
971 and call break_superblocks when going out of cfglayout mode. But it
972 turns out that this never happens; and that if it does ever happen,
973 the TODO_verify_flow at the end of the RTL loop passes would fail.
975 There are two reasons why we expected we could have control flow insns
976 in INSNS. The first is when a comparison has to be done in parts, and
977 the second is when the number of iterations is computed for loops with
978 the number of iterations known at runtime. In both cases, test cases
979 to get control flow in INSNS appear to be impossible to construct:
981 * If do_compare_rtx_and_jump needs several branches to do comparison
982 in a mode that needs comparison by parts, we cannot analyze the
983 number of iterations of the loop, and we never get to unrolling it.
985 * The code in expand_divmod that was suspected to cause creation of
986 branching code seems to be only accessed for signed division. The
987 divisions used by # of iterations analysis are always unsigned.
988 Problems might arise on architectures that emits branching code
989 for some operations that may appear in the unroller (especially
990 for division), but we have no such architectures.
992 Considering all this, it was decided that we should for now assume
993 that INSNS can in theory contain control flow insns, but in practice
994 it never does. So we don't handle the theoretical case, and should
995 a real failure ever show up, we have a pretty good clue for how to
1001 /* Unroll LOOP for which we are able to count number of iterations in runtime
1002 LOOP->LPT_DECISION.TIMES times. The transformation does this (with some
1003 extra care for case n < 0):
1005 for (i = 0; i < n; i++)
1008 ==> (LOOP->LPT_DECISION.TIMES == 3)
1033 unroll_loop_runtime_iterations (struct loop
*loop
)
1035 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
1037 basic_block preheader
, *body
, swtch
, ezc_swtch
;
1038 vec
<basic_block
> dom_bbs
;
1042 vec
<edge
> remove_edges
;
1044 bool extra_zero_check
, last_may_exit
;
1045 unsigned max_unroll
= loop
->lpt_decision
.times
;
1046 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1047 bool exit_at_end
= loop_exit_at_end_p (loop
);
1048 struct opt_info
*opt_info
= NULL
;
1051 if (flag_split_ivs_in_unroller
1052 || flag_variable_expansion_in_unroller
)
1053 opt_info
= analyze_insns_in_loop (loop
);
1055 /* Remember blocks whose dominators will have to be updated. */
1058 body
= get_loop_body (loop
);
1059 for (i
= 0; i
< loop
->num_nodes
; i
++)
1061 vec
<basic_block
> ldom
;
1064 ldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
]);
1065 FOR_EACH_VEC_ELT (ldom
, j
, bb
)
1066 if (!flow_bb_inside_loop_p (loop
, bb
))
1067 dom_bbs
.safe_push (bb
);
1075 /* Leave exit in first copy (for explanation why see comment in
1076 unroll_loop_constant_iterations). */
1078 n_peel
= max_unroll
- 1;
1079 extra_zero_check
= true;
1080 last_may_exit
= false;
1084 /* Leave exit in last copy (for explanation why see comment in
1085 unroll_loop_constant_iterations). */
1086 may_exit_copy
= max_unroll
;
1087 n_peel
= max_unroll
;
1088 extra_zero_check
= false;
1089 last_may_exit
= true;
1092 /* Get expression for number of iterations. */
1094 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
1095 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
1097 emit_move_insn (niter
, tmp
);
1099 /* Count modulo by ANDing it with max_unroll; we use the fact that
1100 the number of unrollings is a power of two, and thus this is correct
1101 even if there is overflow in the computation. */
1102 niter
= expand_simple_binop (desc
->mode
, AND
,
1104 GEN_INT (max_unroll
),
1105 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1107 init_code
= get_insns ();
1109 unshare_all_rtl_in_chain (init_code
);
1111 /* Precondition the loop. */
1112 split_edge_and_insert (loop_preheader_edge (loop
), init_code
);
1114 remove_edges
.create (0);
1116 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1118 /* Peel the first copy of loop body (almost always we must leave exit test
1119 here; the only exception is when we have extra zero check and the number
1120 of iterations is reliable. Also record the place of (possible) extra
1122 bitmap_clear (wont_exit
);
1123 if (extra_zero_check
1124 && !desc
->noloop_assumptions
)
1125 bitmap_set_bit (wont_exit
, 1);
1126 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1127 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1128 1, wont_exit
, desc
->out_edge
,
1130 DLTHE_FLAG_UPDATE_FREQ
);
1133 /* Record the place where switch will be built for preconditioning. */
1134 swtch
= split_edge (loop_preheader_edge (loop
));
1136 for (i
= 0; i
< n_peel
; i
++)
1138 /* Peel the copy. */
1139 bitmap_clear (wont_exit
);
1140 if (i
!= n_peel
- 1 || !last_may_exit
)
1141 bitmap_set_bit (wont_exit
, 1);
1142 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1143 1, wont_exit
, desc
->out_edge
,
1145 DLTHE_FLAG_UPDATE_FREQ
);
1148 /* Create item for switch. */
1149 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1150 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1152 preheader
= split_edge (loop_preheader_edge (loop
));
1153 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1154 block_label (preheader
), p
,
1157 /* We rely on the fact that the compare and jump cannot be optimized out,
1158 and hence the cfg we create is correct. */
1159 gcc_assert (branch_code
!= NULL_RTX
);
1161 swtch
= split_edge_and_insert (single_pred_edge (swtch
), branch_code
);
1162 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1163 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1164 e
= make_edge (swtch
, preheader
,
1165 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1166 e
->count
= RDIV (preheader
->count
* REG_BR_PROB_BASE
, p
);
1170 if (extra_zero_check
)
1172 /* Add branch for zero iterations. */
1173 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1175 preheader
= split_edge (loop_preheader_edge (loop
));
1176 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1177 block_label (preheader
), p
,
1179 gcc_assert (branch_code
!= NULL_RTX
);
1181 swtch
= split_edge_and_insert (single_succ_edge (swtch
), branch_code
);
1182 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1183 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1184 e
= make_edge (swtch
, preheader
,
1185 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1186 e
->count
= RDIV (preheader
->count
* REG_BR_PROB_BASE
, p
);
1190 /* Recount dominators for outer blocks. */
1191 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
1193 /* And unroll loop. */
1195 bitmap_ones (wont_exit
);
1196 bitmap_clear_bit (wont_exit
, may_exit_copy
);
1197 opt_info_start_duplication (opt_info
);
1199 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1201 wont_exit
, desc
->out_edge
,
1203 DLTHE_FLAG_UPDATE_FREQ
1205 ? DLTHE_RECORD_COPY_NUMBER
1211 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1212 free_opt_info (opt_info
);
1219 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1220 /* Find a new in and out edge; they are in the last copy we have
1223 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1225 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1226 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1230 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1231 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1235 /* Remove the edges. */
1236 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
1238 remove_edges
.release ();
1240 /* We must be careful when updating the number of iterations due to
1241 preconditioning and the fact that the value must be valid at entry
1242 of the loop. After passing through the above code, we see that
1243 the correct new number of iterations is this: */
1244 gcc_assert (!desc
->const_iter
);
1246 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1247 GEN_INT (max_unroll
+ 1));
1248 loop
->nb_iterations_upper_bound
1249 = loop
->nb_iterations_upper_bound
.udiv (double_int::from_uhwi (max_unroll
1252 if (loop
->any_estimate
)
1253 loop
->nb_iterations_estimate
1254 = loop
->nb_iterations_estimate
.udiv (double_int::from_uhwi (max_unroll
1260 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1261 desc
->noloop_assumptions
= NULL_RTX
;
1262 --loop
->nb_iterations_upper_bound
;
1263 if (loop
->any_estimate
1264 && loop
->nb_iterations_estimate
!= double_int_zero
)
1265 --loop
->nb_iterations_estimate
;
1267 loop
->any_estimate
= false;
1272 ";; Unrolled loop %d times, counting # of iterations "
1273 "in runtime, %i insns\n",
1274 max_unroll
, num_loop_insns (loop
));
1279 /* Decide whether to simply peel LOOP and how much. */
1281 decide_peel_simple (struct loop
*loop
, int flags
)
1284 double_int iterations
;
1286 if (!(flags
& UAP_PEEL
))
1288 /* We were not asked to, just return back silently. */
1293 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1295 /* npeel = number of iterations to peel. */
1296 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1297 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1298 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1300 /* Skip big loops. */
1304 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1308 /* Do not simply peel loops with branches inside -- it increases number
1310 Exception is when we do have profile and we however have good chance
1311 to peel proper number of iterations loop will iterate in practice.
1312 TODO: this heuristic needs tunning; while for complette unrolling
1313 the branch inside loop mostly eliminates any improvements, for
1314 peeling it is not the case. Also a function call inside loop is
1315 also branch from branch prediction POV (and probably better reason
1316 to not unroll/peel). */
1317 if (num_loop_branches (loop
) > 1
1318 && profile_status
!= PROFILE_READ
)
1321 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1325 /* If we have realistic estimate on number of iterations, use it. */
1326 if (estimated_loop_iterations (loop
, &iterations
))
1328 if (double_int::from_shwi (npeel
).ule (iterations
))
1332 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1333 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1334 (HOST_WIDEST_INT
) (iterations
.to_shwi () + 1));
1335 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1340 npeel
= iterations
.to_shwi () + 1;
1342 /* If we have small enough bound on iterations, we can still peel (completely
1344 else if (max_loop_iterations (loop
, &iterations
)
1345 && iterations
.ult (double_int::from_shwi (npeel
)))
1346 npeel
= iterations
.to_shwi () + 1;
1349 /* For now we have no good heuristics to decide whether loop peeling
1350 will be effective, so disable it. */
1353 ";; Not peeling loop, no evidence it will be profitable\n");
1358 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1359 loop
->lpt_decision
.times
= npeel
;
1362 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1367 ==> (LOOP->LPT_DECISION.TIMES == 3)
1369 if (!cond) goto end;
1371 if (!cond) goto end;
1373 if (!cond) goto end;
1380 peel_loop_simple (struct loop
*loop
)
1383 unsigned npeel
= loop
->lpt_decision
.times
;
1384 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1385 struct opt_info
*opt_info
= NULL
;
1388 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1389 opt_info
= analyze_insns_in_loop (loop
);
1391 wont_exit
= sbitmap_alloc (npeel
+ 1);
1392 bitmap_clear (wont_exit
);
1394 opt_info_start_duplication (opt_info
);
1396 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1397 npeel
, wont_exit
, NULL
,
1398 NULL
, DLTHE_FLAG_UPDATE_FREQ
1400 ? DLTHE_RECORD_COPY_NUMBER
1408 apply_opt_in_copies (opt_info
, npeel
, false, false);
1409 free_opt_info (opt_info
);
1414 if (desc
->const_iter
)
1416 desc
->niter
-= npeel
;
1417 desc
->niter_expr
= GEN_INT (desc
->niter
);
1418 desc
->noloop_assumptions
= NULL_RTX
;
1422 /* We cannot just update niter_expr, as its value might be clobbered
1423 inside loop. We could handle this by counting the number into
1424 temporary just like we do in runtime unrolling, but it does not
1426 free_simple_loop_desc (loop
);
1430 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1433 /* Decide whether to unroll LOOP stupidly and how much. */
1435 decide_unroll_stupid (struct loop
*loop
, int flags
)
1437 unsigned nunroll
, nunroll_by_av
, i
;
1438 struct niter_desc
*desc
;
1439 double_int iterations
;
1441 if (!(flags
& UAP_UNROLL_ALL
))
1443 /* We were not asked to, just return back silently. */
1448 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1450 /* nunroll = total number of copies of the original loop body in
1451 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1452 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1454 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1455 if (nunroll
> nunroll_by_av
)
1456 nunroll
= nunroll_by_av
;
1457 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1458 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1460 if (targetm
.loop_unroll_adjust
)
1461 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
1463 /* Skip big loops. */
1467 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1471 /* Check for simple loops. */
1472 desc
= get_simple_loop_desc (loop
);
1474 /* Check simpleness. */
1475 if (desc
->simple_p
&& !desc
->assumptions
)
1478 fprintf (dump_file
, ";; The loop is simple\n");
1482 /* Do not unroll loops with branches inside -- it increases number
1484 TODO: this heuristic needs tunning; call inside the loop body
1485 is also relatively good reason to not unroll. */
1486 if (num_loop_branches (loop
) > 1)
1489 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1493 /* Check whether the loop rolls. */
1494 if ((estimated_loop_iterations (loop
, &iterations
)
1495 || max_loop_iterations (loop
, &iterations
))
1496 && iterations
.ult (double_int::from_shwi (2 * nunroll
)))
1499 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1503 /* Success. Now force nunroll to be power of 2, as it seems that this
1504 improves results (partially because of better alignments, partially
1505 because of some dark magic). */
1506 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1509 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1510 loop
->lpt_decision
.times
= i
- 1;
1513 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1518 ==> (LOOP->LPT_DECISION.TIMES == 3)
1532 unroll_loop_stupid (struct loop
*loop
)
1535 unsigned nunroll
= loop
->lpt_decision
.times
;
1536 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1537 struct opt_info
*opt_info
= NULL
;
1540 if (flag_split_ivs_in_unroller
1541 || flag_variable_expansion_in_unroller
)
1542 opt_info
= analyze_insns_in_loop (loop
);
1545 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1546 bitmap_clear (wont_exit
);
1547 opt_info_start_duplication (opt_info
);
1549 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1552 DLTHE_FLAG_UPDATE_FREQ
1554 ? DLTHE_RECORD_COPY_NUMBER
1560 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1561 free_opt_info (opt_info
);
1568 /* We indeed may get here provided that there are nontrivial assumptions
1569 for a loop to be really simple. We could update the counts, but the
1570 problem is that we are unable to decide which exit will be taken
1571 (not really true in case the number of iterations is constant,
1572 but noone will do anything with this information, so we do not
1574 desc
->simple_p
= false;
1578 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1579 nunroll
, num_loop_insns (loop
));
1582 /* A hash function for information about insns to split. */
1585 si_info_hash (const void *ivts
)
1587 return (hashval_t
) INSN_UID (((const struct iv_to_split
*) ivts
)->insn
);
1590 /* An equality functions for information about insns to split. */
1593 si_info_eq (const void *ivts1
, const void *ivts2
)
1595 const struct iv_to_split
*const i1
= (const struct iv_to_split
*) ivts1
;
1596 const struct iv_to_split
*const i2
= (const struct iv_to_split
*) ivts2
;
1598 return i1
->insn
== i2
->insn
;
1601 /* Return a hash for VES, which is really a "var_to_expand *". */
1604 ve_info_hash (const void *ves
)
1606 return (hashval_t
) INSN_UID (((const struct var_to_expand
*) ves
)->insn
);
1609 /* Return true if IVTS1 and IVTS2 (which are really both of type
1610 "var_to_expand *") refer to the same instruction. */
1613 ve_info_eq (const void *ivts1
, const void *ivts2
)
1615 const struct var_to_expand
*const i1
= (const struct var_to_expand
*) ivts1
;
1616 const struct var_to_expand
*const i2
= (const struct var_to_expand
*) ivts2
;
1618 return i1
->insn
== i2
->insn
;
1621 /* Returns true if REG is referenced in one nondebug insn in LOOP.
1622 Set *DEBUG_USES to the number of debug insns that reference the
1626 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
,
1629 basic_block
*body
, bb
;
1634 body
= get_loop_body (loop
);
1635 for (i
= 0; i
< loop
->num_nodes
; i
++)
1639 FOR_BB_INSNS (bb
, insn
)
1640 if (!rtx_referenced_p (reg
, insn
))
1642 else if (DEBUG_INSN_P (insn
))
1644 else if (++count_ref
> 1)
1648 return (count_ref
== 1);
1651 /* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1654 reset_debug_uses_in_loop (struct loop
*loop
, rtx reg
, int debug_uses
)
1656 basic_block
*body
, bb
;
1660 body
= get_loop_body (loop
);
1661 for (i
= 0; debug_uses
&& i
< loop
->num_nodes
; i
++)
1665 FOR_BB_INSNS (bb
, insn
)
1666 if (!DEBUG_INSN_P (insn
) || !rtx_referenced_p (reg
, insn
))
1670 validate_change (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1671 gen_rtx_UNKNOWN_VAR_LOC (), 0);
1679 /* Determine whether INSN contains an accumulator
1680 which can be expanded into separate copies,
1681 one for each copy of the LOOP body.
1683 for (i = 0 ; i < n; i++)
1697 Return NULL if INSN contains no opportunity for expansion of accumulator.
1698 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1699 information and return a pointer to it.
1702 static struct var_to_expand
*
1703 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1706 struct var_to_expand
*ves
;
1711 set
= single_set (insn
);
1715 dest
= SET_DEST (set
);
1716 src
= SET_SRC (set
);
1717 code
= GET_CODE (src
);
1719 if (code
!= PLUS
&& code
!= MINUS
&& code
!= MULT
&& code
!= FMA
)
1722 if (FLOAT_MODE_P (GET_MODE (dest
)))
1724 if (!flag_associative_math
)
1726 /* In the case of FMA, we're also changing the rounding. */
1727 if (code
== FMA
&& !flag_unsafe_math_optimizations
)
1731 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1732 in MD. But if there is no optab to generate the insn, we can not
1733 perform the variable expansion. This can happen if an MD provides
1734 an insn but not a named pattern to generate it, for example to avoid
1735 producing code that needs additional mode switches like for x87/mmx.
1737 So we check have_insn_for which looks for an optab for the operation
1738 in SRC. If it doesn't exist, we can't perform the expansion even
1739 though INSN is valid. */
1740 if (!have_insn_for (code
, GET_MODE (src
)))
1744 && !(GET_CODE (dest
) == SUBREG
1745 && REG_P (SUBREG_REG (dest
))))
1748 /* Find the accumulator use within the operation. */
1751 /* We only support accumulation via FMA in the ADD position. */
1752 if (!rtx_equal_p (dest
, XEXP (src
, 2)))
1756 else if (rtx_equal_p (dest
, XEXP (src
, 0)))
1758 else if (rtx_equal_p (dest
, XEXP (src
, 1)))
1760 /* The method of expansion that we are using; which includes the
1761 initialization of the expansions with zero and the summation of
1762 the expansions at the end of the computation will yield wrong
1763 results for (x = something - x) thus avoid using it in that case. */
1771 /* It must not otherwise be used. */
1774 if (rtx_referenced_p (dest
, XEXP (src
, 0))
1775 || rtx_referenced_p (dest
, XEXP (src
, 1)))
1778 else if (rtx_referenced_p (dest
, XEXP (src
, 1 - accum_pos
)))
1781 /* It must be used in exactly one insn. */
1782 if (!referenced_in_one_insn_in_loop_p (loop
, dest
, &debug_uses
))
1787 fprintf (dump_file
, "\n;; Expanding Accumulator ");
1788 print_rtl (dump_file
, dest
);
1789 fprintf (dump_file
, "\n");
1793 /* Instead of resetting the debug insns, we could replace each
1794 debug use in the loop with the sum or product of all expanded
1795 accummulators. Since we'll only know of all expansions at the
1796 end, we'd have to keep track of which vars_to_expand a debug
1797 insn in the loop references, take note of each copy of the
1798 debug insn during unrolling, and when it's all done, compute
1799 the sum or product of each variable and adjust the original
1800 debug insn and each copy thereof. What a pain! */
1801 reset_debug_uses_in_loop (loop
, dest
, debug_uses
);
1803 /* Record the accumulator to expand. */
1804 ves
= XNEW (struct var_to_expand
);
1806 ves
->reg
= copy_rtx (dest
);
1807 ves
->var_expansions
.create (1);
1809 ves
->op
= GET_CODE (src
);
1810 ves
->expansion_count
= 0;
1811 ves
->reuse_expansion
= 0;
1815 /* Determine whether there is an induction variable in INSN that
1816 we would like to split during unrolling.
1836 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1837 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1840 static struct iv_to_split
*
1841 analyze_iv_to_split_insn (rtx insn
)
1845 struct iv_to_split
*ivts
;
1848 /* For now we just split the basic induction variables. Later this may be
1849 extended for example by selecting also addresses of memory references. */
1850 set
= single_set (insn
);
1854 dest
= SET_DEST (set
);
1858 if (!biv_p (insn
, dest
))
1861 ok
= iv_analyze_result (insn
, dest
, &iv
);
1863 /* This used to be an assert under the assumption that if biv_p returns
1864 true that iv_analyze_result must also return true. However, that
1865 assumption is not strictly correct as evidenced by pr25569.
1867 Returning NULL when iv_analyze_result returns false is safe and
1868 avoids the problems in pr25569 until the iv_analyze_* routines
1869 can be fixed, which is apparently hard and time consuming
1870 according to their author. */
1874 if (iv
.step
== const0_rtx
1875 || iv
.mode
!= iv
.extend_mode
)
1878 /* Record the insn to split. */
1879 ivts
= XNEW (struct iv_to_split
);
1881 ivts
->orig_var
= dest
;
1882 ivts
->base_var
= NULL_RTX
;
1883 ivts
->step
= iv
.step
;
1891 /* Determines which of insns in LOOP can be optimized.
1892 Return a OPT_INFO struct with the relevant hash tables filled
1893 with all insns to be optimized. The FIRST_NEW_BLOCK field
1894 is undefined for the return value. */
1896 static struct opt_info
*
1897 analyze_insns_in_loop (struct loop
*loop
)
1899 basic_block
*body
, bb
;
1901 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
1903 struct iv_to_split
*ivts
= NULL
;
1904 struct var_to_expand
*ves
= NULL
;
1907 vec
<edge
> edges
= get_loop_exit_edges (loop
);
1909 bool can_apply
= false;
1911 iv_analysis_loop_init (loop
);
1913 body
= get_loop_body (loop
);
1915 if (flag_split_ivs_in_unroller
)
1917 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1918 si_info_hash
, si_info_eq
, free
);
1919 opt_info
->iv_to_split_head
= NULL
;
1920 opt_info
->iv_to_split_tail
= &opt_info
->iv_to_split_head
;
1923 /* Record the loop exit bb and loop preheader before the unrolling. */
1924 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1926 if (edges
.length () == 1)
1929 if (!(exit
->flags
& EDGE_COMPLEX
))
1931 opt_info
->loop_exit
= split_edge (exit
);
1936 if (flag_variable_expansion_in_unroller
1939 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1942 opt_info
->var_to_expand_head
= NULL
;
1943 opt_info
->var_to_expand_tail
= &opt_info
->var_to_expand_head
;
1946 for (i
= 0; i
< loop
->num_nodes
; i
++)
1949 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1952 FOR_BB_INSNS (bb
, insn
)
1957 if (opt_info
->insns_to_split
)
1958 ivts
= analyze_iv_to_split_insn (insn
);
1962 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1963 gcc_assert (*slot1
== NULL
);
1965 *opt_info
->iv_to_split_tail
= ivts
;
1966 opt_info
->iv_to_split_tail
= &ivts
->next
;
1970 if (opt_info
->insns_with_var_to_expand
)
1971 ves
= analyze_insn_to_expand_var (loop
, insn
);
1975 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1976 gcc_assert (*slot2
== NULL
);
1978 *opt_info
->var_to_expand_tail
= ves
;
1979 opt_info
->var_to_expand_tail
= &ves
->next
;
1989 /* Called just before loop duplication. Records start of duplicated area
1993 opt_info_start_duplication (struct opt_info
*opt_info
)
1996 opt_info
->first_new_block
= last_basic_block
;
1999 /* Determine the number of iterations between initialization of the base
2000 variable and the current copy (N_COPY). N_COPIES is the total number
2001 of newly created copies. UNROLLING is true if we are unrolling
2002 (not peeling) the loop. */
2005 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
2009 /* If we are unrolling, initialization is done in the original loop
2015 /* If we are peeling, the copy in that the initialization occurs has
2016 number 1. The original loop (number 0) is the last. */
2024 /* Locate in EXPR the expression corresponding to the location recorded
2025 in IVTS, and return a pointer to the RTX for this location. */
2028 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
2033 for (i
= 0; i
< ivts
->n_loc
; i
++)
2034 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
2039 /* Allocate basic variable for the induction variable chain. */
2042 allocate_basic_variable (struct iv_to_split
*ivts
)
2044 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
2046 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
2049 /* Insert initialization of basic variable of IVTS before INSN, taking
2050 the initial value from INSN. */
2053 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
2055 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
2059 expr
= force_operand (expr
, ivts
->base_var
);
2060 if (expr
!= ivts
->base_var
)
2061 emit_move_insn (ivts
->base_var
, expr
);
2065 emit_insn_before (seq
, insn
);
2068 /* Replace the use of induction variable described in IVTS in INSN
2069 by base variable + DELTA * step. */
2072 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
2074 rtx expr
, *loc
, seq
, incr
, var
;
2075 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
2078 /* Construct base + DELTA * step. */
2080 expr
= ivts
->base_var
;
2083 incr
= simplify_gen_binary (MULT
, mode
,
2084 ivts
->step
, gen_int_mode (delta
, mode
));
2085 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
2086 ivts
->base_var
, incr
);
2089 /* Figure out where to do the replacement. */
2090 loc
= get_ivts_expr (single_set (insn
), ivts
);
2092 /* If we can make the replacement right away, we're done. */
2093 if (validate_change (insn
, loc
, expr
, 0))
2096 /* Otherwise, force EXPR into a register and try again. */
2098 var
= gen_reg_rtx (mode
);
2099 expr
= force_operand (expr
, var
);
2101 emit_move_insn (var
, expr
);
2104 emit_insn_before (seq
, insn
);
2106 if (validate_change (insn
, loc
, var
, 0))
2109 /* The last chance. Try recreating the assignment in insn
2110 completely from scratch. */
2111 set
= single_set (insn
);
2116 src
= copy_rtx (SET_SRC (set
));
2117 dest
= copy_rtx (SET_DEST (set
));
2118 src
= force_operand (src
, dest
);
2120 emit_move_insn (dest
, src
);
2124 emit_insn_before (seq
, insn
);
2129 /* Return one expansion of the accumulator recorded in struct VE. */
2132 get_expansion (struct var_to_expand
*ve
)
2136 if (ve
->reuse_expansion
== 0)
2139 reg
= ve
->var_expansions
[ve
->reuse_expansion
- 1];
2141 if (ve
->var_expansions
.length () == (unsigned) ve
->reuse_expansion
)
2142 ve
->reuse_expansion
= 0;
2144 ve
->reuse_expansion
++;
2150 /* Given INSN replace the uses of the accumulator recorded in VE
2151 with a new register. */
2154 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
2157 bool really_new_expansion
= false;
2159 set
= single_set (insn
);
2162 /* Generate a new register only if the expansion limit has not been
2163 reached. Else reuse an already existing expansion. */
2164 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
2166 really_new_expansion
= true;
2167 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
2170 new_reg
= get_expansion (ve
);
2172 validate_replace_rtx_group (SET_DEST (set
), new_reg
, insn
);
2173 if (apply_change_group ())
2174 if (really_new_expansion
)
2176 ve
->var_expansions
.safe_push (new_reg
);
2177 ve
->expansion_count
++;
2181 /* Initialize the variable expansions in loop preheader. PLACE is the
2182 loop-preheader basic block where the initialization of the
2183 expansions should take place. The expansions are initialized with
2184 (-0) when the operation is plus or minus to honor sign zero. This
2185 way we can prevent cases where the sign of the final result is
2186 effected by the sign of the expansion. Here is an example to
2189 for (i = 0 ; i < n; i++)
2203 When SUM is initialized with -zero and SOMETHING is also -zero; the
2204 final result of sum should be -zero thus the expansions sum1 and sum2
2205 should be initialized with -zero as well (otherwise we will get +zero
2206 as the final result). */
2209 insert_var_expansion_initialization (struct var_to_expand
*ve
,
2212 rtx seq
, var
, zero_init
;
2214 enum machine_mode mode
= GET_MODE (ve
->reg
);
2215 bool honor_signed_zero_p
= HONOR_SIGNED_ZEROS (mode
);
2217 if (ve
->var_expansions
.length () == 0)
2224 /* Note that we only accumulate FMA via the ADD operand. */
2227 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
2229 if (honor_signed_zero_p
)
2230 zero_init
= simplify_gen_unary (NEG
, mode
, CONST0_RTX (mode
), mode
);
2232 zero_init
= CONST0_RTX (mode
);
2233 emit_move_insn (var
, zero_init
);
2238 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
2240 zero_init
= CONST1_RTX (GET_MODE (var
));
2241 emit_move_insn (var
, zero_init
);
2252 emit_insn_after (seq
, BB_END (place
));
2255 /* Combine the variable expansions at the loop exit. PLACE is the
2256 loop exit basic block where the summation of the expansions should
2260 combine_var_copies_in_loop_exit (struct var_to_expand
*ve
, basic_block place
)
2263 rtx expr
, seq
, var
, insn
;
2266 if (ve
->var_expansions
.length () == 0)
2273 /* Note that we only accumulate FMA via the ADD operand. */
2276 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
2277 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
), var
, sum
);
2281 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
2282 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
), var
, sum
);
2289 expr
= force_operand (sum
, ve
->reg
);
2290 if (expr
!= ve
->reg
)
2291 emit_move_insn (ve
->reg
, expr
);
2295 insn
= BB_HEAD (place
);
2296 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2297 insn
= NEXT_INSN (insn
);
2299 emit_insn_after (seq
, insn
);
2302 /* Strip away REG_EQUAL notes for IVs we're splitting.
2304 Updating REG_EQUAL notes for IVs we split is tricky: We
2305 cannot tell until after unrolling, DF-rescanning, and liveness
2306 updating, whether an EQ_USE is reached by the split IV while
2307 the IV reg is still live. See PR55006.
2309 ??? We cannot use remove_reg_equal_equiv_notes_for_regno,
2310 because RTL loop-iv requires us to defer rescanning insns and
2311 any notes attached to them. So resort to old techniques... */
2314 maybe_strip_eq_note_for_split_iv (struct opt_info
*opt_info
, rtx insn
)
2316 struct iv_to_split
*ivts
;
2317 rtx note
= find_reg_equal_equiv_note (insn
);
2320 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
2321 if (reg_mentioned_p (ivts
->orig_var
, note
))
2323 remove_note (insn
, note
);
2328 /* Apply loop optimizations in loop copies using the
2329 data which gathered during the unrolling. Structure
2330 OPT_INFO record that data.
2332 UNROLLING is true if we unrolled (not peeled) the loop.
2333 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2334 the loop (as it should happen in complete unrolling, but not in ordinary
2335 peeling of the loop). */
2338 apply_opt_in_copies (struct opt_info
*opt_info
,
2339 unsigned n_copies
, bool unrolling
,
2340 bool rewrite_original_loop
)
2343 basic_block bb
, orig_bb
;
2344 rtx insn
, orig_insn
, next
;
2345 struct iv_to_split ivts_templ
, *ivts
;
2346 struct var_to_expand ve_templ
, *ves
;
2348 /* Sanity check -- we need to put initialization in the original loop
2350 gcc_assert (!unrolling
|| rewrite_original_loop
);
2352 /* Allocate the basic variables (i0). */
2353 if (opt_info
->insns_to_split
)
2354 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
2355 allocate_basic_variable (ivts
);
2357 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2359 bb
= BASIC_BLOCK (i
);
2360 orig_bb
= get_bb_original (bb
);
2362 /* bb->aux holds position in copy sequence initialized by
2363 duplicate_loop_to_header_edge. */
2364 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2367 orig_insn
= BB_HEAD (orig_bb
);
2368 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
2371 || (DEBUG_INSN_P (insn
)
2372 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
))
2375 while (!INSN_P (orig_insn
)
2376 || (DEBUG_INSN_P (orig_insn
)
2377 && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn
))
2379 orig_insn
= NEXT_INSN (orig_insn
);
2381 ivts_templ
.insn
= orig_insn
;
2382 ve_templ
.insn
= orig_insn
;
2384 /* Apply splitting iv optimization. */
2385 if (opt_info
->insns_to_split
)
2387 maybe_strip_eq_note_for_split_iv (opt_info
, insn
);
2389 ivts
= (struct iv_to_split
*)
2390 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2394 gcc_assert (GET_CODE (PATTERN (insn
))
2395 == GET_CODE (PATTERN (orig_insn
)));
2398 insert_base_initialization (ivts
, insn
);
2399 split_iv (ivts
, insn
, delta
);
2402 /* Apply variable expansion optimization. */
2403 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2405 ves
= (struct var_to_expand
*)
2406 htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2409 gcc_assert (GET_CODE (PATTERN (insn
))
2410 == GET_CODE (PATTERN (orig_insn
)));
2411 expand_var_during_unrolling (ves
, insn
);
2414 orig_insn
= NEXT_INSN (orig_insn
);
2418 if (!rewrite_original_loop
)
2421 /* Initialize the variable expansions in the loop preheader
2422 and take care of combining them at the loop exit. */
2423 if (opt_info
->insns_with_var_to_expand
)
2425 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2426 insert_var_expansion_initialization (ves
, opt_info
->loop_preheader
);
2427 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2428 combine_var_copies_in_loop_exit (ves
, opt_info
->loop_exit
);
2431 /* Rewrite also the original loop body. Find them as originals of the blocks
2432 in the last copied iteration, i.e. those that have
2433 get_bb_copy (get_bb_original (bb)) == bb. */
2434 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2436 bb
= BASIC_BLOCK (i
);
2437 orig_bb
= get_bb_original (bb
);
2438 if (get_bb_copy (orig_bb
) != bb
)
2441 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2442 for (orig_insn
= BB_HEAD (orig_bb
);
2443 orig_insn
!= NEXT_INSN (BB_END (bb
));
2446 next
= NEXT_INSN (orig_insn
);
2448 if (!INSN_P (orig_insn
))
2451 ivts_templ
.insn
= orig_insn
;
2452 if (opt_info
->insns_to_split
)
2454 maybe_strip_eq_note_for_split_iv (opt_info
, orig_insn
);
2456 ivts
= (struct iv_to_split
*)
2457 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2461 insert_base_initialization (ivts
, orig_insn
);
2462 split_iv (ivts
, orig_insn
, delta
);
2471 /* Release OPT_INFO. */
2474 free_opt_info (struct opt_info
*opt_info
)
2476 if (opt_info
->insns_to_split
)
2477 htab_delete (opt_info
->insns_to_split
);
2478 if (opt_info
->insns_with_var_to_expand
)
2480 struct var_to_expand
*ves
;
2482 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2483 ves
->var_expansions
.release ();
2484 htab_delete (opt_info
->insns_with_var_to_expand
);