1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
25 #include "hard-reg-set.h"
27 #include "basic-block.h"
29 #include "cfglayout.h"
36 /* This pass performs loop unrolling and peeling. We only perform these
37 optimizations on innermost loops (with single exception) because
38 the impact on performance is greatest here, and we want to avoid
39 unnecessary code size growth. The gain is caused by greater sequentiality
40 of code, better code to optimize for further passes and in some cases
41 by fewer testings of exit conditions. The main problem is code growth,
42 that impacts performance negatively due to effect of caches.
46 -- complete peeling of once-rolling loops; this is the above mentioned
47 exception, as this causes loop to be cancelled completely and
48 does not cause code growth
49 -- complete peeling of loops that roll (small) constant times.
50 -- simple peeling of first iterations of loops that do not roll much
51 (according to profile feedback)
52 -- unrolling of loops that roll constant times; this is almost always
53 win, as we get rid of exit condition tests.
54 -- unrolling of loops that roll number of times that we can compute
55 in runtime; we also get rid of exit condition tests here, but there
56 is the extra expense for calculating the number of iterations
57 -- simple unrolling of remaining loops; this is performed only if we
58 are asked to, as the gain is questionable in this case and often
59 it may even slow down the code
60 For more detailed descriptions of each of those, see comments at
61 appropriate function below.
63 There is a lot of parameters (defined and described in params.def) that
64 control how much we unroll/peel.
66 ??? A great problem is that we don't have a good way how to determine
67 how many times we should unroll the loop; the experiments I have made
68 showed that this choice may affect performance in order of several %.
71 /* Information about induction variables to split. */
75 rtx insn
; /* The insn in that the induction variable occurs. */
76 rtx base_var
; /* The variable on that the values in the further
77 iterations are based. */
78 rtx step
; /* Step of the induction variable. */
80 unsigned loc
[3]; /* Location where the definition of the induction
81 variable occurs in the insn. For example if
82 N_LOC is 2, the expression is located at
83 XEXP (XEXP (single_set, loc[0]), loc[1]). */
86 /* Information about accumulators to expand. */
90 rtx insn
; /* The insn in that the variable expansion occurs. */
91 rtx reg
; /* The accumulator which is expanded. */
92 VEC(rtx
,heap
) *var_expansions
; /* The copies of the accumulator which is expanded. */
93 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
95 int expansion_count
; /* Count the number of expansions generated so far. */
96 int reuse_expansion
; /* The expansion we intend to reuse to expand
97 the accumulator. If REUSE_EXPANSION is 0 reuse
98 the original accumulator. Else use
99 var_expansions[REUSE_EXPANSION - 1]. */
102 /* Information about optimization applied in
103 the unrolled loop. */
107 htab_t insns_to_split
; /* A hashtable of insns to split. */
108 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
110 unsigned first_new_block
; /* The first basic block that was
112 basic_block loop_exit
; /* The loop exit basic block. */
113 basic_block loop_preheader
; /* The loop preheader basic block. */
116 static void decide_unrolling_and_peeling (struct loops
*, int);
117 static void peel_loops_completely (struct loops
*, int);
118 static void decide_peel_simple (struct loop
*, int);
119 static void decide_peel_once_rolling (struct loop
*, int);
120 static void decide_peel_completely (struct loop
*, int);
121 static void decide_unroll_stupid (struct loop
*, int);
122 static void decide_unroll_constant_iterations (struct loop
*, int);
123 static void decide_unroll_runtime_iterations (struct loop
*, int);
124 static void peel_loop_simple (struct loops
*, struct loop
*);
125 static void peel_loop_completely (struct loops
*, struct loop
*);
126 static void unroll_loop_stupid (struct loops
*, struct loop
*);
127 static void unroll_loop_constant_iterations (struct loops
*, struct loop
*);
128 static void unroll_loop_runtime_iterations (struct loops
*, struct loop
*);
129 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
130 static void opt_info_start_duplication (struct opt_info
*);
131 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
132 static void free_opt_info (struct opt_info
*);
133 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
134 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
);
135 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
136 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
137 static int insert_var_expansion_initialization (void **, void *);
138 static int combine_var_copies_in_loop_exit (void **, void *);
139 static int release_var_copies (void **, void *);
140 static rtx
get_expansion (struct var_to_expand
*);
142 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
144 unroll_and_peel_loops (struct loops
*loops
, int flags
)
146 struct loop
*loop
, *next
;
149 /* First perform complete loop peeling (it is almost surely a win,
150 and affects parameters for further decision a lot). */
151 peel_loops_completely (loops
, flags
);
153 /* Now decide rest of unrolling and peeling. */
154 decide_unrolling_and_peeling (loops
, flags
);
156 loop
= loops
->tree_root
;
160 /* Scan the loops, inner ones first. */
161 while (loop
!= loops
->tree_root
)
173 /* And perform the appropriate transformations. */
174 switch (loop
->lpt_decision
.decision
)
176 case LPT_PEEL_COMPLETELY
:
179 case LPT_PEEL_SIMPLE
:
180 peel_loop_simple (loops
, loop
);
182 case LPT_UNROLL_CONSTANT
:
183 unroll_loop_constant_iterations (loops
, loop
);
185 case LPT_UNROLL_RUNTIME
:
186 unroll_loop_runtime_iterations (loops
, loop
);
188 case LPT_UNROLL_STUPID
:
189 unroll_loop_stupid (loops
, loop
);
199 #ifdef ENABLE_CHECKING
200 verify_dominators (CDI_DOMINATORS
);
201 verify_loop_structure (loops
);
210 /* Check whether exit of the LOOP is at the end of loop body. */
213 loop_exit_at_end_p (struct loop
*loop
)
215 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
218 if (desc
->in_edge
->dest
!= loop
->latch
)
221 /* Check that the latch is empty. */
222 FOR_BB_INSNS (loop
->latch
, insn
)
231 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
233 peel_loops_completely (struct loops
*loops
, int flags
)
238 /* Scan the loops, the inner ones first. */
239 for (i
= loops
->num
- 1; i
> 0; i
--)
241 loop
= loops
->parray
[i
];
245 loop
->lpt_decision
.decision
= LPT_NONE
;
249 "\n;; *** Considering loop %d for complete peeling ***\n",
252 loop
->ninsns
= num_loop_insns (loop
);
254 decide_peel_once_rolling (loop
, flags
);
255 if (loop
->lpt_decision
.decision
== LPT_NONE
)
256 decide_peel_completely (loop
, flags
);
258 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
260 peel_loop_completely (loops
, loop
);
261 #ifdef ENABLE_CHECKING
262 verify_dominators (CDI_DOMINATORS
);
263 verify_loop_structure (loops
);
269 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
271 decide_unrolling_and_peeling (struct loops
*loops
, int flags
)
273 struct loop
*loop
= loops
->tree_root
, *next
;
278 /* Scan the loops, inner ones first. */
279 while (loop
!= loops
->tree_root
)
290 loop
->lpt_decision
.decision
= LPT_NONE
;
293 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
295 /* Do not peel cold areas. */
296 if (!maybe_hot_bb_p (loop
->header
))
299 fprintf (dump_file
, ";; Not considering loop, cold area\n");
304 /* Can the loop be manipulated? */
305 if (!can_duplicate_loop_p (loop
))
309 ";; Not considering loop, cannot duplicate\n");
314 /* Skip non-innermost loops. */
318 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
323 loop
->ninsns
= num_loop_insns (loop
);
324 loop
->av_ninsns
= average_num_loop_insns (loop
);
326 /* Try transformations one by one in decreasing order of
329 decide_unroll_constant_iterations (loop
, flags
);
330 if (loop
->lpt_decision
.decision
== LPT_NONE
)
331 decide_unroll_runtime_iterations (loop
, flags
);
332 if (loop
->lpt_decision
.decision
== LPT_NONE
)
333 decide_unroll_stupid (loop
, flags
);
334 if (loop
->lpt_decision
.decision
== LPT_NONE
)
335 decide_peel_simple (loop
, flags
);
341 /* Decide whether the LOOP is once rolling and suitable for complete
344 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
346 struct niter_desc
*desc
;
349 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
351 /* Is the loop small enough? */
352 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
355 fprintf (dump_file
, ";; Not considering loop, is too big\n");
359 /* Check for simple loops. */
360 desc
= get_simple_loop_desc (loop
);
362 /* Check number of iterations. */
371 ";; Unable to prove that the loop rolls exactly once\n");
377 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
378 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
381 /* Decide whether the LOOP is suitable for complete peeling. */
383 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
386 struct niter_desc
*desc
;
389 fprintf (dump_file
, "\n;; Considering peeling completely\n");
391 /* Skip non-innermost loops. */
395 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
399 /* Do not peel cold areas. */
400 if (!maybe_hot_bb_p (loop
->header
))
403 fprintf (dump_file
, ";; Not considering loop, cold area\n");
407 /* Can the loop be manipulated? */
408 if (!can_duplicate_loop_p (loop
))
412 ";; Not considering loop, cannot duplicate\n");
416 /* npeel = number of iterations to peel. */
417 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
418 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
419 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
421 /* Is the loop small enough? */
425 fprintf (dump_file
, ";; Not considering loop, is too big\n");
429 /* Check for simple loops. */
430 desc
= get_simple_loop_desc (loop
);
432 /* Check number of iterations. */
440 ";; Unable to prove that the loop iterates constant times\n");
444 if (desc
->niter
> npeel
- 1)
449 ";; Not peeling loop completely, rolls too much (");
450 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
451 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
458 fprintf (dump_file
, ";; Decided to peel loop completely\n");
459 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
462 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
463 completely. The transformation done:
465 for (i = 0; i < 4; i++)
477 peel_loop_completely (struct loops
*loops
, struct loop
*loop
)
480 unsigned HOST_WIDE_INT npeel
;
481 unsigned n_remove_edges
, i
;
482 edge
*remove_edges
, ein
;
483 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
484 struct opt_info
*opt_info
= NULL
;
492 wont_exit
= sbitmap_alloc (npeel
+ 1);
493 sbitmap_ones (wont_exit
);
494 RESET_BIT (wont_exit
, 0);
495 if (desc
->noloop_assumptions
)
496 RESET_BIT (wont_exit
, 1);
498 remove_edges
= XCNEWVEC (edge
, npeel
);
501 if (flag_split_ivs_in_unroller
)
502 opt_info
= analyze_insns_in_loop (loop
);
504 opt_info_start_duplication (opt_info
);
505 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
507 wont_exit
, desc
->out_edge
,
508 remove_edges
, &n_remove_edges
,
509 DLTHE_FLAG_UPDATE_FREQ
510 | DLTHE_FLAG_COMPLETTE_PEEL
512 ? DLTHE_RECORD_COPY_NUMBER
: 0));
519 apply_opt_in_copies (opt_info
, npeel
, false, true);
520 free_opt_info (opt_info
);
523 /* Remove the exit edges. */
524 for (i
= 0; i
< n_remove_edges
; i
++)
525 remove_path (loops
, remove_edges
[i
]);
530 free_simple_loop_desc (loop
);
532 /* Now remove the unreachable part of the last iteration and cancel
534 remove_path (loops
, ein
);
537 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
540 /* Decide whether to unroll LOOP iterating constant number of times
544 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
546 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
547 struct niter_desc
*desc
;
549 if (!(flags
& UAP_UNROLL
))
551 /* We were not asked to, just return back silently. */
557 "\n;; Considering unrolling loop with constant "
558 "number of iterations\n");
560 /* nunroll = total number of copies of the original loop body in
561 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
562 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
564 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
565 if (nunroll
> nunroll_by_av
)
566 nunroll
= nunroll_by_av
;
567 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
568 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
570 /* Skip big loops. */
574 fprintf (dump_file
, ";; Not considering loop, is too big\n");
578 /* Check for simple loops. */
579 desc
= get_simple_loop_desc (loop
);
581 /* Check number of iterations. */
582 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
586 ";; Unable to prove that the loop iterates constant times\n");
590 /* Check whether the loop rolls enough to consider. */
591 if (desc
->niter
< 2 * nunroll
)
594 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
598 /* Success; now compute number of iterations to unroll. We alter
599 nunroll so that as few as possible copies of loop body are
600 necessary, while still not decreasing the number of unrollings
601 too much (at most by 1). */
602 best_copies
= 2 * nunroll
+ 10;
605 if (i
- 1 >= desc
->niter
)
608 for (; i
>= nunroll
- 1; i
--)
610 unsigned exit_mod
= desc
->niter
% (i
+ 1);
612 if (!loop_exit_at_end_p (loop
))
613 n_copies
= exit_mod
+ i
+ 1;
614 else if (exit_mod
!= (unsigned) i
615 || desc
->noloop_assumptions
!= NULL_RTX
)
616 n_copies
= exit_mod
+ i
+ 2;
620 if (n_copies
< best_copies
)
622 best_copies
= n_copies
;
628 fprintf (dump_file
, ";; max_unroll %d (%d copies, initial %d).\n",
629 best_unroll
+ 1, best_copies
, nunroll
);
631 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
632 loop
->lpt_decision
.times
= best_unroll
;
636 ";; Decided to unroll the constant times rolling loop, %d times.\n",
637 loop
->lpt_decision
.times
);
640 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
641 times. The transformation does this:
643 for (i = 0; i < 102; i++)
660 unroll_loop_constant_iterations (struct loops
*loops
, struct loop
*loop
)
662 unsigned HOST_WIDE_INT niter
;
665 unsigned n_remove_edges
, i
;
667 unsigned max_unroll
= loop
->lpt_decision
.times
;
668 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
669 bool exit_at_end
= loop_exit_at_end_p (loop
);
670 struct opt_info
*opt_info
= NULL
;
675 /* Should not get here (such loop should be peeled instead). */
676 gcc_assert (niter
> max_unroll
+ 1);
678 exit_mod
= niter
% (max_unroll
+ 1);
680 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
681 sbitmap_ones (wont_exit
);
683 remove_edges
= XCNEWVEC (edge
, max_unroll
+ exit_mod
+ 1);
685 if (flag_split_ivs_in_unroller
686 || flag_variable_expansion_in_unroller
)
687 opt_info
= analyze_insns_in_loop (loop
);
691 /* The exit is not at the end of the loop; leave exit test
692 in the first copy, so that the loops that start with test
693 of exit condition have continuous body after unrolling. */
696 fprintf (dump_file
, ";; Condition on beginning of loop.\n");
698 /* Peel exit_mod iterations. */
699 RESET_BIT (wont_exit
, 0);
700 if (desc
->noloop_assumptions
)
701 RESET_BIT (wont_exit
, 1);
705 opt_info_start_duplication (opt_info
);
706 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
708 wont_exit
, desc
->out_edge
,
709 remove_edges
, &n_remove_edges
,
710 DLTHE_FLAG_UPDATE_FREQ
711 | (opt_info
&& exit_mod
> 1
712 ? DLTHE_RECORD_COPY_NUMBER
716 if (opt_info
&& exit_mod
> 1)
717 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
719 desc
->noloop_assumptions
= NULL_RTX
;
720 desc
->niter
-= exit_mod
;
721 desc
->niter_max
-= exit_mod
;
724 SET_BIT (wont_exit
, 1);
728 /* Leave exit test in last copy, for the same reason as above if
729 the loop tests the condition at the end of loop body. */
732 fprintf (dump_file
, ";; Condition on end of loop.\n");
734 /* We know that niter >= max_unroll + 2; so we do not need to care of
735 case when we would exit before reaching the loop. So just peel
736 exit_mod + 1 iterations. */
737 if (exit_mod
!= max_unroll
738 || desc
->noloop_assumptions
)
740 RESET_BIT (wont_exit
, 0);
741 if (desc
->noloop_assumptions
)
742 RESET_BIT (wont_exit
, 1);
744 opt_info_start_duplication (opt_info
);
745 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
747 wont_exit
, desc
->out_edge
,
748 remove_edges
, &n_remove_edges
,
749 DLTHE_FLAG_UPDATE_FREQ
750 | (opt_info
&& exit_mod
> 0
751 ? DLTHE_RECORD_COPY_NUMBER
755 if (opt_info
&& exit_mod
> 0)
756 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
758 desc
->niter
-= exit_mod
+ 1;
759 desc
->niter_max
-= exit_mod
+ 1;
760 desc
->noloop_assumptions
= NULL_RTX
;
762 SET_BIT (wont_exit
, 0);
763 SET_BIT (wont_exit
, 1);
766 RESET_BIT (wont_exit
, max_unroll
);
769 /* Now unroll the loop. */
771 opt_info_start_duplication (opt_info
);
772 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
774 wont_exit
, desc
->out_edge
,
775 remove_edges
, &n_remove_edges
,
776 DLTHE_FLAG_UPDATE_FREQ
778 ? DLTHE_RECORD_COPY_NUMBER
784 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
785 free_opt_info (opt_info
);
792 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
793 /* Find a new in and out edge; they are in the last copy we have made. */
795 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
797 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
798 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
802 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
803 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
807 desc
->niter
/= max_unroll
+ 1;
808 desc
->niter_max
/= max_unroll
+ 1;
809 desc
->niter_expr
= GEN_INT (desc
->niter
);
811 /* Remove the edges. */
812 for (i
= 0; i
< n_remove_edges
; i
++)
813 remove_path (loops
, remove_edges
[i
]);
818 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
819 max_unroll
, num_loop_insns (loop
));
822 /* Decide whether to unroll LOOP iterating runtime computable number of times
825 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
827 unsigned nunroll
, nunroll_by_av
, i
;
828 struct niter_desc
*desc
;
830 if (!(flags
& UAP_UNROLL
))
832 /* We were not asked to, just return back silently. */
838 "\n;; Considering unrolling loop with runtime "
839 "computable number of iterations\n");
841 /* nunroll = total number of copies of the original loop body in
842 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
843 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
844 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
845 if (nunroll
> nunroll_by_av
)
846 nunroll
= nunroll_by_av
;
847 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
848 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
850 /* Skip big loops. */
854 fprintf (dump_file
, ";; Not considering loop, is too big\n");
858 /* Check for simple loops. */
859 desc
= get_simple_loop_desc (loop
);
861 /* Check simpleness. */
862 if (!desc
->simple_p
|| desc
->assumptions
)
866 ";; Unable to prove that the number of iterations "
867 "can be counted in runtime\n");
871 if (desc
->const_iter
)
874 fprintf (dump_file
, ";; Loop iterates constant times\n");
878 /* If we have profile feedback, check whether the loop rolls. */
879 if (loop
->header
->count
&& expected_loop_iterations (loop
) < 2 * nunroll
)
882 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
886 /* Success; now force nunroll to be power of 2, as we are unable to
887 cope with overflows in computation of number of iterations. */
888 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
891 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
892 loop
->lpt_decision
.times
= i
- 1;
896 ";; Decided to unroll the runtime computable "
897 "times rolling loop, %d times.\n",
898 loop
->lpt_decision
.times
);
901 /* Unroll LOOP for that we are able to count number of iterations in runtime
902 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
903 extra care for case n < 0):
905 for (i = 0; i < n; i++)
933 unroll_loop_runtime_iterations (struct loops
*loops
, struct loop
*loop
)
935 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
937 basic_block preheader
, *body
, *dom_bbs
, swtch
, ezc_swtch
;
941 unsigned n_peel
, n_remove_edges
;
942 edge
*remove_edges
, e
;
943 bool extra_zero_check
, last_may_exit
;
944 unsigned max_unroll
= loop
->lpt_decision
.times
;
945 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
946 bool exit_at_end
= loop_exit_at_end_p (loop
);
947 struct opt_info
*opt_info
= NULL
;
950 if (flag_split_ivs_in_unroller
951 || flag_variable_expansion_in_unroller
)
952 opt_info
= analyze_insns_in_loop (loop
);
954 /* Remember blocks whose dominators will have to be updated. */
955 dom_bbs
= XCNEWVEC (basic_block
, n_basic_blocks
);
958 body
= get_loop_body (loop
);
959 for (i
= 0; i
< loop
->num_nodes
; i
++)
964 nldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
], &ldom
);
965 for (j
= 0; j
< nldom
; j
++)
966 if (!flow_bb_inside_loop_p (loop
, ldom
[j
]))
967 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
975 /* Leave exit in first copy (for explanation why see comment in
976 unroll_loop_constant_iterations). */
978 n_peel
= max_unroll
- 1;
979 extra_zero_check
= true;
980 last_may_exit
= false;
984 /* Leave exit in last copy (for explanation why see comment in
985 unroll_loop_constant_iterations). */
986 may_exit_copy
= max_unroll
;
988 extra_zero_check
= false;
989 last_may_exit
= true;
992 /* Get expression for number of iterations. */
994 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
995 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
997 emit_move_insn (niter
, tmp
);
999 /* Count modulo by ANDing it with max_unroll; we use the fact that
1000 the number of unrollings is a power of two, and thus this is correct
1001 even if there is overflow in the computation. */
1002 niter
= expand_simple_binop (desc
->mode
, AND
,
1004 GEN_INT (max_unroll
),
1005 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1007 init_code
= get_insns ();
1010 /* Precondition the loop. */
1011 loop_split_edge_with (loop_preheader_edge (loop
), init_code
);
1013 remove_edges
= XCNEWVEC (edge
, max_unroll
+ n_peel
+ 1);
1016 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1018 /* Peel the first copy of loop body (almost always we must leave exit test
1019 here; the only exception is when we have extra zero check and the number
1020 of iterations is reliable. Also record the place of (possible) extra
1022 sbitmap_zero (wont_exit
);
1023 if (extra_zero_check
1024 && !desc
->noloop_assumptions
)
1025 SET_BIT (wont_exit
, 1);
1026 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1027 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1029 wont_exit
, desc
->out_edge
,
1030 remove_edges
, &n_remove_edges
,
1031 DLTHE_FLAG_UPDATE_FREQ
);
1034 /* Record the place where switch will be built for preconditioning. */
1035 swtch
= loop_split_edge_with (loop_preheader_edge (loop
),
1038 for (i
= 0; i
< n_peel
; i
++)
1040 /* Peel the copy. */
1041 sbitmap_zero (wont_exit
);
1042 if (i
!= n_peel
- 1 || !last_may_exit
)
1043 SET_BIT (wont_exit
, 1);
1044 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1046 wont_exit
, desc
->out_edge
,
1047 remove_edges
, &n_remove_edges
,
1048 DLTHE_FLAG_UPDATE_FREQ
);
1051 /* Create item for switch. */
1052 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1053 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1055 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1056 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1057 block_label (preheader
), p
,
1060 swtch
= loop_split_edge_with (single_pred_edge (swtch
), branch_code
);
1061 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1062 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1063 e
= make_edge (swtch
, preheader
,
1064 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1068 if (extra_zero_check
)
1070 /* Add branch for zero iterations. */
1071 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1073 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1074 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1075 block_label (preheader
), p
,
1078 swtch
= loop_split_edge_with (single_succ_edge (swtch
), branch_code
);
1079 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1080 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1081 e
= make_edge (swtch
, preheader
,
1082 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1086 /* Recount dominators for outer blocks. */
1087 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
1089 /* And unroll loop. */
1091 sbitmap_ones (wont_exit
);
1092 RESET_BIT (wont_exit
, may_exit_copy
);
1093 opt_info_start_duplication (opt_info
);
1095 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1097 wont_exit
, desc
->out_edge
,
1098 remove_edges
, &n_remove_edges
,
1099 DLTHE_FLAG_UPDATE_FREQ
1101 ? DLTHE_RECORD_COPY_NUMBER
1107 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1108 free_opt_info (opt_info
);
1115 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1116 /* Find a new in and out edge; they are in the last copy we have
1119 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1121 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1122 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1126 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1127 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1131 /* Remove the edges. */
1132 for (i
= 0; i
< n_remove_edges
; i
++)
1133 remove_path (loops
, remove_edges
[i
]);
1134 free (remove_edges
);
1136 /* We must be careful when updating the number of iterations due to
1137 preconditioning and the fact that the value must be valid at entry
1138 of the loop. After passing through the above code, we see that
1139 the correct new number of iterations is this: */
1140 gcc_assert (!desc
->const_iter
);
1142 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1143 GEN_INT (max_unroll
+ 1));
1144 desc
->niter_max
/= max_unroll
+ 1;
1148 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1149 desc
->noloop_assumptions
= NULL_RTX
;
1155 ";; Unrolled loop %d times, counting # of iterations "
1156 "in runtime, %i insns\n",
1157 max_unroll
, num_loop_insns (loop
));
1163 /* Decide whether to simply peel LOOP and how much. */
1165 decide_peel_simple (struct loop
*loop
, int flags
)
1168 struct niter_desc
*desc
;
1170 if (!(flags
& UAP_PEEL
))
1172 /* We were not asked to, just return back silently. */
1177 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1179 /* npeel = number of iterations to peel. */
1180 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1181 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1182 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1184 /* Skip big loops. */
1188 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1192 /* Check for simple loops. */
1193 desc
= get_simple_loop_desc (loop
);
1195 /* Check number of iterations. */
1196 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1199 fprintf (dump_file
, ";; Loop iterates constant times\n");
1203 /* Do not simply peel loops with branches inside -- it increases number
1205 if (num_loop_branches (loop
) > 1)
1208 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1212 if (loop
->header
->count
)
1214 unsigned niter
= expected_loop_iterations (loop
);
1215 if (niter
+ 1 > npeel
)
1219 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1220 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1221 (HOST_WIDEST_INT
) (niter
+ 1));
1222 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1231 /* For now we have no good heuristics to decide whether loop peeling
1232 will be effective, so disable it. */
1235 ";; Not peeling loop, no evidence it will be profitable\n");
1240 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1241 loop
->lpt_decision
.times
= npeel
;
1244 fprintf (dump_file
, ";; Decided to simply peel the loop, %d times.\n",
1245 loop
->lpt_decision
.times
);
1248 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1254 if (!cond) goto end;
1256 if (!cond) goto end;
1263 peel_loop_simple (struct loops
*loops
, struct loop
*loop
)
1266 unsigned npeel
= loop
->lpt_decision
.times
;
1267 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1268 struct opt_info
*opt_info
= NULL
;
1271 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1272 opt_info
= analyze_insns_in_loop (loop
);
1274 wont_exit
= sbitmap_alloc (npeel
+ 1);
1275 sbitmap_zero (wont_exit
);
1277 opt_info_start_duplication (opt_info
);
1279 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1280 loops
, npeel
, wont_exit
,
1282 NULL
, DLTHE_FLAG_UPDATE_FREQ
1284 ? DLTHE_RECORD_COPY_NUMBER
1292 apply_opt_in_copies (opt_info
, npeel
, false, false);
1293 free_opt_info (opt_info
);
1298 if (desc
->const_iter
)
1300 desc
->niter
-= npeel
;
1301 desc
->niter_expr
= GEN_INT (desc
->niter
);
1302 desc
->noloop_assumptions
= NULL_RTX
;
1306 /* We cannot just update niter_expr, as its value might be clobbered
1307 inside loop. We could handle this by counting the number into
1308 temporary just like we do in runtime unrolling, but it does not
1310 free_simple_loop_desc (loop
);
1314 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1317 /* Decide whether to unroll LOOP stupidly and how much. */
1319 decide_unroll_stupid (struct loop
*loop
, int flags
)
1321 unsigned nunroll
, nunroll_by_av
, i
;
1322 struct niter_desc
*desc
;
1324 if (!(flags
& UAP_UNROLL_ALL
))
1326 /* We were not asked to, just return back silently. */
1331 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1333 /* nunroll = total number of copies of the original loop body in
1334 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1335 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1337 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1338 if (nunroll
> nunroll_by_av
)
1339 nunroll
= nunroll_by_av
;
1340 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1341 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1343 /* Skip big loops. */
1347 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1351 /* Check for simple loops. */
1352 desc
= get_simple_loop_desc (loop
);
1354 /* Check simpleness. */
1355 if (desc
->simple_p
&& !desc
->assumptions
)
1358 fprintf (dump_file
, ";; The loop is simple\n");
1362 /* Do not unroll loops with branches inside -- it increases number
1364 if (num_loop_branches (loop
) > 1)
1367 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1371 /* If we have profile feedback, check whether the loop rolls. */
1372 if (loop
->header
->count
1373 && expected_loop_iterations (loop
) < 2 * nunroll
)
1376 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1380 /* Success. Now force nunroll to be power of 2, as it seems that this
1381 improves results (partially because of better alignments, partially
1382 because of some dark magic). */
1383 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1386 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1387 loop
->lpt_decision
.times
= i
- 1;
1391 ";; Decided to unroll the loop stupidly, %d times.\n",
1392 loop
->lpt_decision
.times
);
1395 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1413 unroll_loop_stupid (struct loops
*loops
, struct loop
*loop
)
1416 unsigned nunroll
= loop
->lpt_decision
.times
;
1417 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1418 struct opt_info
*opt_info
= NULL
;
1421 if (flag_split_ivs_in_unroller
1422 || flag_variable_expansion_in_unroller
)
1423 opt_info
= analyze_insns_in_loop (loop
);
1426 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1427 sbitmap_zero (wont_exit
);
1428 opt_info_start_duplication (opt_info
);
1430 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1431 loops
, nunroll
, wont_exit
,
1433 DLTHE_FLAG_UPDATE_FREQ
1435 ? DLTHE_RECORD_COPY_NUMBER
1441 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1442 free_opt_info (opt_info
);
1449 /* We indeed may get here provided that there are nontrivial assumptions
1450 for a loop to be really simple. We could update the counts, but the
1451 problem is that we are unable to decide which exit will be taken
1452 (not really true in case the number of iterations is constant,
1453 but noone will do anything with this information, so we do not
1455 desc
->simple_p
= false;
1459 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1460 nunroll
, num_loop_insns (loop
));
1463 /* A hash function for information about insns to split. */
1466 si_info_hash (const void *ivts
)
1468 return (hashval_t
) INSN_UID (((struct iv_to_split
*) ivts
)->insn
);
1471 /* An equality functions for information about insns to split. */
1474 si_info_eq (const void *ivts1
, const void *ivts2
)
1476 const struct iv_to_split
*i1
= ivts1
;
1477 const struct iv_to_split
*i2
= ivts2
;
1479 return i1
->insn
== i2
->insn
;
1482 /* Return a hash for VES, which is really a "var_to_expand *". */
1485 ve_info_hash (const void *ves
)
1487 return (hashval_t
) INSN_UID (((struct var_to_expand
*) ves
)->insn
);
1490 /* Return true if IVTS1 and IVTS2 (which are really both of type
1491 "var_to_expand *") refer to the same instruction. */
1494 ve_info_eq (const void *ivts1
, const void *ivts2
)
1496 const struct var_to_expand
*i1
= ivts1
;
1497 const struct var_to_expand
*i2
= ivts2
;
1499 return i1
->insn
== i2
->insn
;
1502 /* Returns true if REG is referenced in one insn in LOOP. */
1505 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
)
1507 basic_block
*body
, bb
;
1512 body
= get_loop_body (loop
);
1513 for (i
= 0; i
< loop
->num_nodes
; i
++)
1517 FOR_BB_INSNS (bb
, insn
)
1519 if (rtx_referenced_p (reg
, insn
))
1523 return (count_ref
== 1);
1526 /* Determine whether INSN contains an accumulator
1527 which can be expanded into separate copies,
1528 one for each copy of the LOOP body.
1530 for (i = 0 ; i < n; i++)
1544 Return NULL if INSN contains no opportunity for expansion of accumulator.
1545 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1546 information and return a pointer to it.
1549 static struct var_to_expand
*
1550 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1552 rtx set
, dest
, src
, op1
;
1553 struct var_to_expand
*ves
;
1554 enum machine_mode mode1
, mode2
;
1556 set
= single_set (insn
);
1560 dest
= SET_DEST (set
);
1561 src
= SET_SRC (set
);
1563 if (GET_CODE (src
) != PLUS
1564 && GET_CODE (src
) != MINUS
1565 && GET_CODE (src
) != MULT
)
1568 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1569 in MD. But if there is no optab to generate the insn, we can not
1570 perform the variable expansion. This can happen if an MD provides
1571 an insn but not a named pattern to generate it, for example to avoid
1572 producing code that needs additional mode switches like for x87/mmx.
1574 So we check have_insn_for which looks for an optab for the operation
1575 in SRC. If it doesn't exist, we can't perform the expansion even
1576 though INSN is valid. */
1577 if (!have_insn_for (GET_CODE (src
), GET_MODE (src
)))
1583 op1
= XEXP (src
, 0);
1586 && !(GET_CODE (dest
) == SUBREG
1587 && REG_P (SUBREG_REG (dest
))))
1590 if (!rtx_equal_p (dest
, op1
))
1593 if (!referenced_in_one_insn_in_loop_p (loop
, dest
))
1596 if (rtx_referenced_p (dest
, XEXP (src
, 1)))
1599 mode1
= GET_MODE (dest
);
1600 mode2
= GET_MODE (XEXP (src
, 1));
1601 if ((FLOAT_MODE_P (mode1
)
1602 || FLOAT_MODE_P (mode2
))
1603 && !flag_unsafe_math_optimizations
)
1606 /* Record the accumulator to expand. */
1607 ves
= XNEW (struct var_to_expand
);
1609 ves
->var_expansions
= VEC_alloc (rtx
, heap
, 1);
1610 ves
->reg
= copy_rtx (dest
);
1611 ves
->op
= GET_CODE (src
);
1612 ves
->expansion_count
= 0;
1613 ves
->reuse_expansion
= 0;
1617 /* Determine whether there is an induction variable in INSN that
1618 we would like to split during unrolling.
1638 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1639 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1642 static struct iv_to_split
*
1643 analyze_iv_to_split_insn (rtx insn
)
1647 struct iv_to_split
*ivts
;
1650 /* For now we just split the basic induction variables. Later this may be
1651 extended for example by selecting also addresses of memory references. */
1652 set
= single_set (insn
);
1656 dest
= SET_DEST (set
);
1660 if (!biv_p (insn
, dest
))
1663 ok
= iv_analyze_result (insn
, dest
, &iv
);
1665 /* This used to be an assert under the assumption that if biv_p returns
1666 true that iv_analyze_result must also return true. However, that
1667 assumption is not strictly correct as evidenced by pr25569.
1669 Returning NULL when iv_analyze_result returns false is safe and
1670 avoids the problems in pr25569 until the iv_analyze_* routines
1671 can be fixed, which is apparently hard and time consuming
1672 according to their author. */
1676 if (iv
.step
== const0_rtx
1677 || iv
.mode
!= iv
.extend_mode
)
1680 /* Record the insn to split. */
1681 ivts
= XNEW (struct iv_to_split
);
1683 ivts
->base_var
= NULL_RTX
;
1684 ivts
->step
= iv
.step
;
1691 /* Determines which of insns in LOOP can be optimized.
1692 Return a OPT_INFO struct with the relevant hash tables filled
1693 with all insns to be optimized. The FIRST_NEW_BLOCK field
1694 is undefined for the return value. */
1696 static struct opt_info
*
1697 analyze_insns_in_loop (struct loop
*loop
)
1699 basic_block
*body
, bb
;
1700 unsigned i
, num_edges
= 0;
1701 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
1703 struct iv_to_split
*ivts
= NULL
;
1704 struct var_to_expand
*ves
= NULL
;
1707 edge
*edges
= get_loop_exit_edges (loop
, &num_edges
);
1708 bool can_apply
= false;
1710 iv_analysis_loop_init (loop
);
1712 body
= get_loop_body (loop
);
1714 if (flag_split_ivs_in_unroller
)
1715 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1716 si_info_hash
, si_info_eq
, free
);
1718 /* Record the loop exit bb and loop preheader before the unrolling. */
1719 if (!loop_preheader_edge (loop
)->src
)
1721 loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1722 opt_info
->loop_preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1725 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1728 && !(edges
[0]->flags
& EDGE_COMPLEX
))
1730 opt_info
->loop_exit
= loop_split_edge_with (edges
[0], NULL_RTX
);
1734 if (flag_variable_expansion_in_unroller
1736 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1737 ve_info_hash
, ve_info_eq
, free
);
1739 for (i
= 0; i
< loop
->num_nodes
; i
++)
1742 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1745 FOR_BB_INSNS (bb
, insn
)
1750 if (opt_info
->insns_to_split
)
1751 ivts
= analyze_iv_to_split_insn (insn
);
1755 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1760 if (opt_info
->insns_with_var_to_expand
)
1761 ves
= analyze_insn_to_expand_var (loop
, insn
);
1765 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1776 /* Called just before loop duplication. Records start of duplicated area
1780 opt_info_start_duplication (struct opt_info
*opt_info
)
1783 opt_info
->first_new_block
= last_basic_block
;
1786 /* Determine the number of iterations between initialization of the base
1787 variable and the current copy (N_COPY). N_COPIES is the total number
1788 of newly created copies. UNROLLING is true if we are unrolling
1789 (not peeling) the loop. */
1792 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1796 /* If we are unrolling, initialization is done in the original loop
1802 /* If we are peeling, the copy in that the initialization occurs has
1803 number 1. The original loop (number 0) is the last. */
1811 /* Locate in EXPR the expression corresponding to the location recorded
1812 in IVTS, and return a pointer to the RTX for this location. */
1815 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1820 for (i
= 0; i
< ivts
->n_loc
; i
++)
1821 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1826 /* Allocate basic variable for the induction variable chain. Callback for
1830 allocate_basic_variable (void **slot
, void *data ATTRIBUTE_UNUSED
)
1832 struct iv_to_split
*ivts
= *slot
;
1833 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1835 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1840 /* Insert initialization of basic variable of IVTS before INSN, taking
1841 the initial value from INSN. */
1844 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
1846 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
1850 expr
= force_operand (expr
, ivts
->base_var
);
1851 if (expr
!= ivts
->base_var
)
1852 emit_move_insn (ivts
->base_var
, expr
);
1856 emit_insn_before (seq
, insn
);
1859 /* Replace the use of induction variable described in IVTS in INSN
1860 by base variable + DELTA * step. */
1863 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
1865 rtx expr
, *loc
, seq
, incr
, var
;
1866 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
1869 /* Construct base + DELTA * step. */
1871 expr
= ivts
->base_var
;
1874 incr
= simplify_gen_binary (MULT
, mode
,
1875 ivts
->step
, gen_int_mode (delta
, mode
));
1876 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1877 ivts
->base_var
, incr
);
1880 /* Figure out where to do the replacement. */
1881 loc
= get_ivts_expr (single_set (insn
), ivts
);
1883 /* If we can make the replacement right away, we're done. */
1884 if (validate_change (insn
, loc
, expr
, 0))
1887 /* Otherwise, force EXPR into a register and try again. */
1889 var
= gen_reg_rtx (mode
);
1890 expr
= force_operand (expr
, var
);
1892 emit_move_insn (var
, expr
);
1895 emit_insn_before (seq
, insn
);
1897 if (validate_change (insn
, loc
, var
, 0))
1900 /* The last chance. Try recreating the assignment in insn
1901 completely from scratch. */
1902 set
= single_set (insn
);
1907 src
= copy_rtx (SET_SRC (set
));
1908 dest
= copy_rtx (SET_DEST (set
));
1909 src
= force_operand (src
, dest
);
1911 emit_move_insn (dest
, src
);
1915 emit_insn_before (seq
, insn
);
1920 /* Return one expansion of the accumulator recorded in struct VE. */
1923 get_expansion (struct var_to_expand
*ve
)
1927 if (ve
->reuse_expansion
== 0)
1930 reg
= VEC_index (rtx
, ve
->var_expansions
, ve
->reuse_expansion
- 1);
1932 if (VEC_length (rtx
, ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
1933 ve
->reuse_expansion
= 0;
1935 ve
->reuse_expansion
++;
1941 /* Given INSN replace the uses of the accumulator recorded in VE
1942 with a new register. */
1945 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
1948 bool really_new_expansion
= false;
1950 set
= single_set (insn
);
1953 /* Generate a new register only if the expansion limit has not been
1954 reached. Else reuse an already existing expansion. */
1955 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
1957 really_new_expansion
= true;
1958 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1961 new_reg
= get_expansion (ve
);
1963 validate_change (insn
, &SET_DEST (set
), new_reg
, 1);
1964 validate_change (insn
, &XEXP (SET_SRC (set
), 0), new_reg
, 1);
1966 if (apply_change_group ())
1967 if (really_new_expansion
)
1969 VEC_safe_push (rtx
, heap
, ve
->var_expansions
, new_reg
);
1970 ve
->expansion_count
++;
1974 /* Initialize the variable expansions in loop preheader.
1975 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1976 basic block where the initialization of the expansions
1977 should take place. */
1980 insert_var_expansion_initialization (void **slot
, void *place_p
)
1982 struct var_to_expand
*ve
= *slot
;
1983 basic_block place
= (basic_block
)place_p
;
1984 rtx seq
, var
, zero_init
, insn
;
1987 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
1991 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1992 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
1994 zero_init
= CONST0_RTX (GET_MODE (var
));
1995 emit_move_insn (var
, zero_init
);
1997 else if (ve
->op
== MULT
)
1998 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2000 zero_init
= CONST1_RTX (GET_MODE (var
));
2001 emit_move_insn (var
, zero_init
);
2007 insn
= BB_HEAD (place
);
2008 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2009 insn
= NEXT_INSN (insn
);
2011 emit_insn_after (seq
, insn
);
2012 /* Continue traversing the hash table. */
2016 /* Combine the variable expansions at the loop exit.
2017 Callbacks for htab_traverse. PLACE_P is the loop exit
2018 basic block where the summation of the expansions should
2022 combine_var_copies_in_loop_exit (void **slot
, void *place_p
)
2024 struct var_to_expand
*ve
= *slot
;
2025 basic_block place
= (basic_block
)place_p
;
2027 rtx expr
, seq
, var
, insn
;
2030 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2034 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
2035 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2037 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
),
2040 else if (ve
->op
== MULT
)
2041 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2043 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
),
2047 expr
= force_operand (sum
, ve
->reg
);
2048 if (expr
!= ve
->reg
)
2049 emit_move_insn (ve
->reg
, expr
);
2053 insn
= BB_HEAD (place
);
2054 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2055 insn
= NEXT_INSN (insn
);
2057 emit_insn_after (seq
, insn
);
2059 /* Continue traversing the hash table. */
2063 /* Apply loop optimizations in loop copies using the
2064 data which gathered during the unrolling. Structure
2065 OPT_INFO record that data.
2067 UNROLLING is true if we unrolled (not peeled) the loop.
2068 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2069 the loop (as it should happen in complete unrolling, but not in ordinary
2070 peeling of the loop). */
2073 apply_opt_in_copies (struct opt_info
*opt_info
,
2074 unsigned n_copies
, bool unrolling
,
2075 bool rewrite_original_loop
)
2078 basic_block bb
, orig_bb
;
2079 rtx insn
, orig_insn
, next
;
2080 struct iv_to_split ivts_templ
, *ivts
;
2081 struct var_to_expand ve_templ
, *ves
;
2083 /* Sanity check -- we need to put initialization in the original loop
2085 gcc_assert (!unrolling
|| rewrite_original_loop
);
2087 /* Allocate the basic variables (i0). */
2088 if (opt_info
->insns_to_split
)
2089 htab_traverse (opt_info
->insns_to_split
, allocate_basic_variable
, NULL
);
2091 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2093 bb
= BASIC_BLOCK (i
);
2094 orig_bb
= get_bb_original (bb
);
2096 /* bb->aux holds position in copy sequence initialized by
2097 duplicate_loop_to_header_edge. */
2098 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2101 orig_insn
= BB_HEAD (orig_bb
);
2102 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2104 next
= NEXT_INSN (insn
);
2108 while (!INSN_P (orig_insn
))
2109 orig_insn
= NEXT_INSN (orig_insn
);
2111 ivts_templ
.insn
= orig_insn
;
2112 ve_templ
.insn
= orig_insn
;
2114 /* Apply splitting iv optimization. */
2115 if (opt_info
->insns_to_split
)
2117 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2121 gcc_assert (GET_CODE (PATTERN (insn
))
2122 == GET_CODE (PATTERN (orig_insn
)));
2125 insert_base_initialization (ivts
, insn
);
2126 split_iv (ivts
, insn
, delta
);
2129 /* Apply variable expansion optimization. */
2130 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2132 ves
= htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2135 gcc_assert (GET_CODE (PATTERN (insn
))
2136 == GET_CODE (PATTERN (orig_insn
)));
2137 expand_var_during_unrolling (ves
, insn
);
2140 orig_insn
= NEXT_INSN (orig_insn
);
2144 if (!rewrite_original_loop
)
2147 /* Initialize the variable expansions in the loop preheader
2148 and take care of combining them at the loop exit. */
2149 if (opt_info
->insns_with_var_to_expand
)
2151 htab_traverse (opt_info
->insns_with_var_to_expand
,
2152 insert_var_expansion_initialization
,
2153 opt_info
->loop_preheader
);
2154 htab_traverse (opt_info
->insns_with_var_to_expand
,
2155 combine_var_copies_in_loop_exit
,
2156 opt_info
->loop_exit
);
2159 /* Rewrite also the original loop body. Find them as originals of the blocks
2160 in the last copied iteration, i.e. those that have
2161 get_bb_copy (get_bb_original (bb)) == bb. */
2162 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2164 bb
= BASIC_BLOCK (i
);
2165 orig_bb
= get_bb_original (bb
);
2166 if (get_bb_copy (orig_bb
) != bb
)
2169 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2170 for (orig_insn
= BB_HEAD (orig_bb
);
2171 orig_insn
!= NEXT_INSN (BB_END (bb
));
2174 next
= NEXT_INSN (orig_insn
);
2176 if (!INSN_P (orig_insn
))
2179 ivts_templ
.insn
= orig_insn
;
2180 if (opt_info
->insns_to_split
)
2182 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2186 insert_base_initialization (ivts
, orig_insn
);
2187 split_iv (ivts
, orig_insn
, delta
);
2196 /* Release the data structures used for the variable expansion
2197 optimization. Callbacks for htab_traverse. */
2200 release_var_copies (void **slot
, void *data ATTRIBUTE_UNUSED
)
2202 struct var_to_expand
*ve
= *slot
;
2204 VEC_free (rtx
, heap
, ve
->var_expansions
);
2206 /* Continue traversing the hash table. */
2210 /* Release OPT_INFO. */
2213 free_opt_info (struct opt_info
*opt_info
)
2215 if (opt_info
->insns_to_split
)
2216 htab_delete (opt_info
->insns_to_split
);
2217 if (opt_info
->insns_with_var_to_expand
)
2219 htab_traverse (opt_info
->insns_with_var_to_expand
,
2220 release_var_copies
, NULL
);
2221 htab_delete (opt_info
->insns_with_var_to_expand
);