1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008
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"
30 #include "cfglayout.h"
37 /* This pass performs loop unrolling and peeling. We only perform these
38 optimizations on innermost loops (with single exception) because
39 the impact on performance is greatest here, and we want to avoid
40 unnecessary code size growth. The gain is caused by greater sequentiality
41 of code, better code to optimize for further passes and in some cases
42 by fewer testings of exit conditions. The main problem is code growth,
43 that impacts performance negatively due to effect of caches.
47 -- complete peeling of once-rolling loops; this is the above mentioned
48 exception, as this causes loop to be cancelled completely and
49 does not cause code growth
50 -- complete peeling of loops that roll (small) constant times.
51 -- simple peeling of first iterations of loops that do not roll much
52 (according to profile feedback)
53 -- unrolling of loops that roll constant times; this is almost always
54 win, as we get rid of exit condition tests.
55 -- unrolling of loops that roll number of times that we can compute
56 in runtime; we also get rid of exit condition tests here, but there
57 is the extra expense for calculating the number of iterations
58 -- simple unrolling of remaining loops; this is performed only if we
59 are asked to, as the gain is questionable in this case and often
60 it may even slow down the code
61 For more detailed descriptions of each of those, see comments at
62 appropriate function below.
64 There is a lot of parameters (defined and described in params.def) that
65 control how much we unroll/peel.
67 ??? A great problem is that we don't have a good way how to determine
68 how many times we should unroll the loop; the experiments I have made
69 showed that this choice may affect performance in order of several %.
72 /* Information about induction variables to split. */
76 rtx insn
; /* The insn in that the induction variable occurs. */
77 rtx base_var
; /* The variable on that the values in the further
78 iterations are based. */
79 rtx step
; /* Step of the induction variable. */
80 struct iv_to_split
*next
; /* Next entry in walking order. */
82 unsigned loc
[3]; /* Location where the definition of the induction
83 variable occurs in the insn. For example if
84 N_LOC is 2, the expression is located at
85 XEXP (XEXP (single_set, loc[0]), loc[1]). */
88 /* Information about accumulators to expand. */
92 rtx insn
; /* The insn in that the variable expansion occurs. */
93 rtx reg
; /* The accumulator which is expanded. */
94 VEC(rtx
,heap
) *var_expansions
; /* The copies of the accumulator which is expanded. */
95 struct var_to_expand
*next
; /* Next entry in walking order. */
96 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
98 int expansion_count
; /* Count the number of expansions generated so far. */
99 int reuse_expansion
; /* The expansion we intend to reuse to expand
100 the accumulator. If REUSE_EXPANSION is 0 reuse
101 the original accumulator. Else use
102 var_expansions[REUSE_EXPANSION - 1]. */
103 unsigned accum_pos
; /* The position in which the accumulator is placed in
104 the insn src. For example in x = x + something
105 accum_pos is 0 while in x = something + x accum_pos
109 /* Information about optimization applied in
110 the unrolled loop. */
114 htab_t insns_to_split
; /* A hashtable of insns to split. */
115 struct iv_to_split
*iv_to_split_head
; /* The first iv to split. */
116 struct iv_to_split
**iv_to_split_tail
; /* Pointer to the tail of the list. */
117 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
119 struct var_to_expand
*var_to_expand_head
; /* The first var to expand. */
120 struct var_to_expand
**var_to_expand_tail
; /* Pointer to the tail of the list. */
121 unsigned first_new_block
; /* The first basic block that was
123 basic_block loop_exit
; /* The loop exit basic block. */
124 basic_block loop_preheader
; /* The loop preheader basic block. */
127 static void decide_unrolling_and_peeling (int);
128 static void peel_loops_completely (int);
129 static void decide_peel_simple (struct loop
*, int);
130 static void decide_peel_once_rolling (struct loop
*, int);
131 static void decide_peel_completely (struct loop
*, int);
132 static void decide_unroll_stupid (struct loop
*, int);
133 static void decide_unroll_constant_iterations (struct loop
*, int);
134 static void decide_unroll_runtime_iterations (struct loop
*, int);
135 static void peel_loop_simple (struct loop
*);
136 static void peel_loop_completely (struct loop
*);
137 static void unroll_loop_stupid (struct loop
*);
138 static void unroll_loop_constant_iterations (struct loop
*);
139 static void unroll_loop_runtime_iterations (struct loop
*);
140 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
141 static void opt_info_start_duplication (struct opt_info
*);
142 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
143 static void free_opt_info (struct opt_info
*);
144 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
145 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
);
146 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
147 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
148 static void insert_var_expansion_initialization (struct var_to_expand
*,
150 static void combine_var_copies_in_loop_exit (struct var_to_expand
*,
152 static rtx
get_expansion (struct var_to_expand
*);
154 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
156 unroll_and_peel_loops (int flags
)
162 /* First perform complete loop peeling (it is almost surely a win,
163 and affects parameters for further decision a lot). */
164 peel_loops_completely (flags
);
166 /* Now decide rest of unrolling and peeling. */
167 decide_unrolling_and_peeling (flags
);
169 /* Scan the loops, inner ones first. */
170 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
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 (loop
);
182 case LPT_UNROLL_CONSTANT
:
183 unroll_loop_constant_iterations (loop
);
185 case LPT_UNROLL_RUNTIME
:
186 unroll_loop_runtime_iterations (loop
);
188 case LPT_UNROLL_STUPID
:
189 unroll_loop_stupid (loop
);
199 #ifdef ENABLE_CHECKING
200 verify_dominators (CDI_DOMINATORS
);
201 verify_loop_structure ();
209 /* Check whether exit of the LOOP is at the end of loop body. */
212 loop_exit_at_end_p (struct loop
*loop
)
214 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
217 if (desc
->in_edge
->dest
!= loop
->latch
)
220 /* Check that the latch is empty. */
221 FOR_BB_INSNS (loop
->latch
, insn
)
230 /* Depending on FLAGS, check whether to peel loops completely and do so. */
232 peel_loops_completely (int flags
)
237 /* Scan the loops, the inner ones first. */
238 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
240 loop
->lpt_decision
.decision
= LPT_NONE
;
244 "\n;; *** Considering loop %d for complete peeling ***\n",
247 loop
->ninsns
= num_loop_insns (loop
);
249 decide_peel_once_rolling (loop
, flags
);
250 if (loop
->lpt_decision
.decision
== LPT_NONE
)
251 decide_peel_completely (loop
, flags
);
253 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
255 peel_loop_completely (loop
);
256 #ifdef ENABLE_CHECKING
257 verify_dominators (CDI_DOMINATORS
);
258 verify_loop_structure ();
264 /* Decide whether unroll or peel loops (depending on FLAGS) and how much. */
266 decide_unrolling_and_peeling (int flags
)
271 /* Scan the loops, inner ones first. */
272 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
274 loop
->lpt_decision
.decision
= LPT_NONE
;
277 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
279 /* Do not peel cold areas. */
280 if (optimize_loop_for_size_p (loop
))
283 fprintf (dump_file
, ";; Not considering loop, cold area\n");
287 /* Can the loop be manipulated? */
288 if (!can_duplicate_loop_p (loop
))
292 ";; Not considering loop, cannot duplicate\n");
296 /* Skip non-innermost loops. */
300 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
304 loop
->ninsns
= num_loop_insns (loop
);
305 loop
->av_ninsns
= average_num_loop_insns (loop
);
307 /* Try transformations one by one in decreasing order of
310 decide_unroll_constant_iterations (loop
, flags
);
311 if (loop
->lpt_decision
.decision
== LPT_NONE
)
312 decide_unroll_runtime_iterations (loop
, flags
);
313 if (loop
->lpt_decision
.decision
== LPT_NONE
)
314 decide_unroll_stupid (loop
, flags
);
315 if (loop
->lpt_decision
.decision
== LPT_NONE
)
316 decide_peel_simple (loop
, flags
);
320 /* Decide whether the LOOP is once rolling and suitable for complete
323 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
325 struct niter_desc
*desc
;
328 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
330 /* Is the loop small enough? */
331 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
334 fprintf (dump_file
, ";; Not considering loop, is too big\n");
338 /* Check for simple loops. */
339 desc
= get_simple_loop_desc (loop
);
341 /* Check number of iterations. */
350 ";; Unable to prove that the loop rolls exactly once\n");
356 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
357 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
360 /* Decide whether the LOOP is suitable for complete peeling. */
362 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
365 struct niter_desc
*desc
;
368 fprintf (dump_file
, "\n;; Considering peeling completely\n");
370 /* Skip non-innermost loops. */
374 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
378 /* Do not peel cold areas. */
379 if (optimize_loop_for_size_p (loop
))
382 fprintf (dump_file
, ";; Not considering loop, cold area\n");
386 /* Can the loop be manipulated? */
387 if (!can_duplicate_loop_p (loop
))
391 ";; Not considering loop, cannot duplicate\n");
395 /* npeel = number of iterations to peel. */
396 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
397 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
398 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
400 /* Is the loop small enough? */
404 fprintf (dump_file
, ";; Not considering loop, is too big\n");
408 /* Check for simple loops. */
409 desc
= get_simple_loop_desc (loop
);
411 /* Check number of iterations. */
419 ";; Unable to prove that the loop iterates constant times\n");
423 if (desc
->niter
> npeel
- 1)
428 ";; Not peeling loop completely, rolls too much (");
429 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
430 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
437 fprintf (dump_file
, ";; Decided to peel loop completely\n");
438 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
441 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
442 completely. The transformation done:
444 for (i = 0; i < 4; i++)
456 peel_loop_completely (struct loop
*loop
)
459 unsigned HOST_WIDE_INT npeel
;
461 VEC (edge
, heap
) *remove_edges
;
463 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
464 struct opt_info
*opt_info
= NULL
;
472 wont_exit
= sbitmap_alloc (npeel
+ 1);
473 sbitmap_ones (wont_exit
);
474 RESET_BIT (wont_exit
, 0);
475 if (desc
->noloop_assumptions
)
476 RESET_BIT (wont_exit
, 1);
480 if (flag_split_ivs_in_unroller
)
481 opt_info
= analyze_insns_in_loop (loop
);
483 opt_info_start_duplication (opt_info
);
484 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
486 wont_exit
, desc
->out_edge
,
488 DLTHE_FLAG_UPDATE_FREQ
489 | DLTHE_FLAG_COMPLETTE_PEEL
491 ? DLTHE_RECORD_COPY_NUMBER
: 0));
498 apply_opt_in_copies (opt_info
, npeel
, false, true);
499 free_opt_info (opt_info
);
502 /* Remove the exit edges. */
503 for (i
= 0; VEC_iterate (edge
, remove_edges
, i
, ein
); i
++)
505 VEC_free (edge
, heap
, remove_edges
);
509 free_simple_loop_desc (loop
);
511 /* Now remove the unreachable part of the last iteration and cancel
516 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
519 /* Decide whether to unroll LOOP iterating constant number of times
523 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
525 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
526 struct niter_desc
*desc
;
528 if (!(flags
& UAP_UNROLL
))
530 /* We were not asked to, just return back silently. */
536 "\n;; Considering unrolling loop with constant "
537 "number of iterations\n");
539 /* nunroll = total number of copies of the original loop body in
540 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
541 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
543 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
544 if (nunroll
> nunroll_by_av
)
545 nunroll
= nunroll_by_av
;
546 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
547 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
549 /* Skip big loops. */
553 fprintf (dump_file
, ";; Not considering loop, is too big\n");
557 /* Check for simple loops. */
558 desc
= get_simple_loop_desc (loop
);
560 /* Check number of iterations. */
561 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
565 ";; Unable to prove that the loop iterates constant times\n");
569 /* Check whether the loop rolls enough to consider. */
570 if (desc
->niter
< 2 * nunroll
)
573 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
577 /* Success; now compute number of iterations to unroll. We alter
578 nunroll so that as few as possible copies of loop body are
579 necessary, while still not decreasing the number of unrollings
580 too much (at most by 1). */
581 best_copies
= 2 * nunroll
+ 10;
584 if (i
- 1 >= desc
->niter
)
587 for (; i
>= nunroll
- 1; i
--)
589 unsigned exit_mod
= desc
->niter
% (i
+ 1);
591 if (!loop_exit_at_end_p (loop
))
592 n_copies
= exit_mod
+ i
+ 1;
593 else if (exit_mod
!= (unsigned) i
594 || desc
->noloop_assumptions
!= NULL_RTX
)
595 n_copies
= exit_mod
+ i
+ 2;
599 if (n_copies
< best_copies
)
601 best_copies
= n_copies
;
607 fprintf (dump_file
, ";; max_unroll %d (%d copies, initial %d).\n",
608 best_unroll
+ 1, best_copies
, nunroll
);
610 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
611 loop
->lpt_decision
.times
= best_unroll
;
615 ";; Decided to unroll the constant times rolling loop, %d times.\n",
616 loop
->lpt_decision
.times
);
619 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
620 times. The transformation does this:
622 for (i = 0; i < 102; i++)
639 unroll_loop_constant_iterations (struct loop
*loop
)
641 unsigned HOST_WIDE_INT niter
;
645 VEC (edge
, heap
) *remove_edges
;
647 unsigned max_unroll
= loop
->lpt_decision
.times
;
648 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
649 bool exit_at_end
= loop_exit_at_end_p (loop
);
650 struct opt_info
*opt_info
= NULL
;
655 /* Should not get here (such loop should be peeled instead). */
656 gcc_assert (niter
> max_unroll
+ 1);
658 exit_mod
= niter
% (max_unroll
+ 1);
660 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
661 sbitmap_ones (wont_exit
);
664 if (flag_split_ivs_in_unroller
665 || flag_variable_expansion_in_unroller
)
666 opt_info
= analyze_insns_in_loop (loop
);
670 /* The exit is not at the end of the loop; leave exit test
671 in the first copy, so that the loops that start with test
672 of exit condition have continuous body after unrolling. */
675 fprintf (dump_file
, ";; Condition on beginning of loop.\n");
677 /* Peel exit_mod iterations. */
678 RESET_BIT (wont_exit
, 0);
679 if (desc
->noloop_assumptions
)
680 RESET_BIT (wont_exit
, 1);
684 opt_info_start_duplication (opt_info
);
685 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
687 wont_exit
, desc
->out_edge
,
689 DLTHE_FLAG_UPDATE_FREQ
690 | (opt_info
&& exit_mod
> 1
691 ? DLTHE_RECORD_COPY_NUMBER
695 if (opt_info
&& exit_mod
> 1)
696 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
698 desc
->noloop_assumptions
= NULL_RTX
;
699 desc
->niter
-= exit_mod
;
700 desc
->niter_max
-= exit_mod
;
703 SET_BIT (wont_exit
, 1);
707 /* Leave exit test in last copy, for the same reason as above if
708 the loop tests the condition at the end of loop body. */
711 fprintf (dump_file
, ";; Condition on end of loop.\n");
713 /* We know that niter >= max_unroll + 2; so we do not need to care of
714 case when we would exit before reaching the loop. So just peel
715 exit_mod + 1 iterations. */
716 if (exit_mod
!= max_unroll
717 || desc
->noloop_assumptions
)
719 RESET_BIT (wont_exit
, 0);
720 if (desc
->noloop_assumptions
)
721 RESET_BIT (wont_exit
, 1);
723 opt_info_start_duplication (opt_info
);
724 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
726 wont_exit
, desc
->out_edge
,
728 DLTHE_FLAG_UPDATE_FREQ
729 | (opt_info
&& exit_mod
> 0
730 ? DLTHE_RECORD_COPY_NUMBER
734 if (opt_info
&& exit_mod
> 0)
735 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
737 desc
->niter
-= exit_mod
+ 1;
738 desc
->niter_max
-= exit_mod
+ 1;
739 desc
->noloop_assumptions
= NULL_RTX
;
741 SET_BIT (wont_exit
, 0);
742 SET_BIT (wont_exit
, 1);
745 RESET_BIT (wont_exit
, max_unroll
);
748 /* Now unroll the loop. */
750 opt_info_start_duplication (opt_info
);
751 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
753 wont_exit
, desc
->out_edge
,
755 DLTHE_FLAG_UPDATE_FREQ
757 ? DLTHE_RECORD_COPY_NUMBER
763 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
764 free_opt_info (opt_info
);
771 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
772 /* Find a new in and out edge; they are in the last copy we have made. */
774 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
776 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
777 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
781 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
782 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
786 desc
->niter
/= max_unroll
+ 1;
787 desc
->niter_max
/= max_unroll
+ 1;
788 desc
->niter_expr
= GEN_INT (desc
->niter
);
790 /* Remove the edges. */
791 for (i
= 0; VEC_iterate (edge
, remove_edges
, i
, e
); i
++)
793 VEC_free (edge
, heap
, remove_edges
);
797 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
798 max_unroll
, num_loop_insns (loop
));
801 /* Decide whether to unroll LOOP iterating runtime computable number of times
804 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
806 unsigned nunroll
, nunroll_by_av
, i
;
807 struct niter_desc
*desc
;
809 if (!(flags
& UAP_UNROLL
))
811 /* We were not asked to, just return back silently. */
817 "\n;; Considering unrolling loop with runtime "
818 "computable number of iterations\n");
820 /* nunroll = total number of copies of the original loop body in
821 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
822 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
823 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
824 if (nunroll
> nunroll_by_av
)
825 nunroll
= nunroll_by_av
;
826 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
827 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
829 /* Skip big loops. */
833 fprintf (dump_file
, ";; Not considering loop, is too big\n");
837 /* Check for simple loops. */
838 desc
= get_simple_loop_desc (loop
);
840 /* Check simpleness. */
841 if (!desc
->simple_p
|| desc
->assumptions
)
845 ";; Unable to prove that the number of iterations "
846 "can be counted in runtime\n");
850 if (desc
->const_iter
)
853 fprintf (dump_file
, ";; Loop iterates constant times\n");
857 /* If we have profile feedback, check whether the loop rolls. */
858 if (loop
->header
->count
&& expected_loop_iterations (loop
) < 2 * nunroll
)
861 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
865 /* Success; now force nunroll to be power of 2, as we are unable to
866 cope with overflows in computation of number of iterations. */
867 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
870 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
871 loop
->lpt_decision
.times
= i
- 1;
875 ";; Decided to unroll the runtime computable "
876 "times rolling loop, %d times.\n",
877 loop
->lpt_decision
.times
);
880 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
881 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
882 and NULL is returned instead. */
885 split_edge_and_insert (edge e
, rtx insns
)
892 emit_insn_after (insns
, BB_END (bb
));
894 /* ??? We used to assume that INSNS can contain control flow insns, and
895 that we had to try to find sub basic blocks in BB to maintain a valid
896 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
897 and call break_superblocks when going out of cfglayout mode. But it
898 turns out that this never happens; and that if it does ever happen,
899 the verify_flow_info call in loop_optimizer_finalize would fail.
901 There are two reasons why we expected we could have control flow insns
902 in INSNS. The first is when a comparison has to be done in parts, and
903 the second is when the number of iterations is computed for loops with
904 the number of iterations known at runtime. In both cases, test cases
905 to get control flow in INSNS appear to be impossible to construct:
907 * If do_compare_rtx_and_jump needs several branches to do comparison
908 in a mode that needs comparison by parts, we cannot analyze the
909 number of iterations of the loop, and we never get to unrolling it.
911 * The code in expand_divmod that was suspected to cause creation of
912 branching code seems to be only accessed for signed division. The
913 divisions used by # of iterations analysis are always unsigned.
914 Problems might arise on architectures that emits branching code
915 for some operations that may appear in the unroller (especially
916 for division), but we have no such architectures.
918 Considering all this, it was decided that we should for now assume
919 that INSNS can in theory contain control flow insns, but in practice
920 it never does. So we don't handle the theoretical case, and should
921 a real failure ever show up, we have a pretty good clue for how to
927 /* Unroll LOOP for that we are able to count number of iterations in runtime
928 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
929 extra care for case n < 0):
931 for (i = 0; i < n; i++)
959 unroll_loop_runtime_iterations (struct loop
*loop
)
961 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
963 basic_block preheader
, *body
, swtch
, ezc_swtch
;
964 VEC (basic_block
, heap
) *dom_bbs
;
968 VEC (edge
, heap
) *remove_edges
;
970 bool extra_zero_check
, last_may_exit
;
971 unsigned max_unroll
= loop
->lpt_decision
.times
;
972 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
973 bool exit_at_end
= loop_exit_at_end_p (loop
);
974 struct opt_info
*opt_info
= NULL
;
977 if (flag_split_ivs_in_unroller
978 || flag_variable_expansion_in_unroller
)
979 opt_info
= analyze_insns_in_loop (loop
);
981 /* Remember blocks whose dominators will have to be updated. */
984 body
= get_loop_body (loop
);
985 for (i
= 0; i
< loop
->num_nodes
; i
++)
987 VEC (basic_block
, heap
) *ldom
;
990 ldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
]);
991 for (j
= 0; VEC_iterate (basic_block
, ldom
, j
, bb
); j
++)
992 if (!flow_bb_inside_loop_p (loop
, bb
))
993 VEC_safe_push (basic_block
, heap
, dom_bbs
, bb
);
995 VEC_free (basic_block
, heap
, ldom
);
1001 /* Leave exit in first copy (for explanation why see comment in
1002 unroll_loop_constant_iterations). */
1004 n_peel
= max_unroll
- 1;
1005 extra_zero_check
= true;
1006 last_may_exit
= false;
1010 /* Leave exit in last copy (for explanation why see comment in
1011 unroll_loop_constant_iterations). */
1012 may_exit_copy
= max_unroll
;
1013 n_peel
= max_unroll
;
1014 extra_zero_check
= false;
1015 last_may_exit
= true;
1018 /* Get expression for number of iterations. */
1020 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
1021 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
1023 emit_move_insn (niter
, tmp
);
1025 /* Count modulo by ANDing it with max_unroll; we use the fact that
1026 the number of unrollings is a power of two, and thus this is correct
1027 even if there is overflow in the computation. */
1028 niter
= expand_simple_binop (desc
->mode
, AND
,
1030 GEN_INT (max_unroll
),
1031 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1033 init_code
= get_insns ();
1035 unshare_all_rtl_in_chain (init_code
);
1037 /* Precondition the loop. */
1038 split_edge_and_insert (loop_preheader_edge (loop
), init_code
);
1040 remove_edges
= NULL
;
1042 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1044 /* Peel the first copy of loop body (almost always we must leave exit test
1045 here; the only exception is when we have extra zero check and the number
1046 of iterations is reliable. Also record the place of (possible) extra
1048 sbitmap_zero (wont_exit
);
1049 if (extra_zero_check
1050 && !desc
->noloop_assumptions
)
1051 SET_BIT (wont_exit
, 1);
1052 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1053 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1054 1, wont_exit
, desc
->out_edge
,
1056 DLTHE_FLAG_UPDATE_FREQ
);
1059 /* Record the place where switch will be built for preconditioning. */
1060 swtch
= split_edge (loop_preheader_edge (loop
));
1062 for (i
= 0; i
< n_peel
; i
++)
1064 /* Peel the copy. */
1065 sbitmap_zero (wont_exit
);
1066 if (i
!= n_peel
- 1 || !last_may_exit
)
1067 SET_BIT (wont_exit
, 1);
1068 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1069 1, wont_exit
, desc
->out_edge
,
1071 DLTHE_FLAG_UPDATE_FREQ
);
1074 /* Create item for switch. */
1075 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1076 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1078 preheader
= split_edge (loop_preheader_edge (loop
));
1079 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1080 block_label (preheader
), p
,
1083 /* We rely on the fact that the compare and jump cannot be optimized out,
1084 and hence the cfg we create is correct. */
1085 gcc_assert (branch_code
!= NULL_RTX
);
1087 swtch
= split_edge_and_insert (single_pred_edge (swtch
), branch_code
);
1088 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1089 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1090 e
= make_edge (swtch
, preheader
,
1091 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1095 if (extra_zero_check
)
1097 /* Add branch for zero iterations. */
1098 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1100 preheader
= split_edge (loop_preheader_edge (loop
));
1101 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1102 block_label (preheader
), p
,
1104 gcc_assert (branch_code
!= NULL_RTX
);
1106 swtch
= split_edge_and_insert (single_succ_edge (swtch
), branch_code
);
1107 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1108 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1109 e
= make_edge (swtch
, preheader
,
1110 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1114 /* Recount dominators for outer blocks. */
1115 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
1117 /* And unroll loop. */
1119 sbitmap_ones (wont_exit
);
1120 RESET_BIT (wont_exit
, may_exit_copy
);
1121 opt_info_start_duplication (opt_info
);
1123 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1125 wont_exit
, desc
->out_edge
,
1127 DLTHE_FLAG_UPDATE_FREQ
1129 ? DLTHE_RECORD_COPY_NUMBER
1135 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1136 free_opt_info (opt_info
);
1143 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1144 /* Find a new in and out edge; they are in the last copy we have
1147 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1149 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1150 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1154 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1155 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1159 /* Remove the edges. */
1160 for (i
= 0; VEC_iterate (edge
, remove_edges
, i
, e
); i
++)
1162 VEC_free (edge
, heap
, remove_edges
);
1164 /* We must be careful when updating the number of iterations due to
1165 preconditioning and the fact that the value must be valid at entry
1166 of the loop. After passing through the above code, we see that
1167 the correct new number of iterations is this: */
1168 gcc_assert (!desc
->const_iter
);
1170 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1171 GEN_INT (max_unroll
+ 1));
1172 desc
->niter_max
/= max_unroll
+ 1;
1176 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1177 desc
->noloop_assumptions
= NULL_RTX
;
1183 ";; Unrolled loop %d times, counting # of iterations "
1184 "in runtime, %i insns\n",
1185 max_unroll
, num_loop_insns (loop
));
1187 VEC_free (basic_block
, heap
, dom_bbs
);
1190 /* Decide whether to simply peel LOOP and how much. */
1192 decide_peel_simple (struct loop
*loop
, int flags
)
1195 struct niter_desc
*desc
;
1197 if (!(flags
& UAP_PEEL
))
1199 /* We were not asked to, just return back silently. */
1204 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1206 /* npeel = number of iterations to peel. */
1207 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1208 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1209 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1211 /* Skip big loops. */
1215 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1219 /* Check for simple loops. */
1220 desc
= get_simple_loop_desc (loop
);
1222 /* Check number of iterations. */
1223 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1226 fprintf (dump_file
, ";; Loop iterates constant times\n");
1230 /* Do not simply peel loops with branches inside -- it increases number
1232 if (num_loop_branches (loop
) > 1)
1235 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1239 if (loop
->header
->count
)
1241 unsigned niter
= expected_loop_iterations (loop
);
1242 if (niter
+ 1 > npeel
)
1246 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1247 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1248 (HOST_WIDEST_INT
) (niter
+ 1));
1249 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1258 /* For now we have no good heuristics to decide whether loop peeling
1259 will be effective, so disable it. */
1262 ";; Not peeling loop, no evidence it will be profitable\n");
1267 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1268 loop
->lpt_decision
.times
= npeel
;
1271 fprintf (dump_file
, ";; Decided to simply peel the loop, %d times.\n",
1272 loop
->lpt_decision
.times
);
1275 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1281 if (!cond) goto end;
1283 if (!cond) goto end;
1290 peel_loop_simple (struct loop
*loop
)
1293 unsigned npeel
= loop
->lpt_decision
.times
;
1294 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1295 struct opt_info
*opt_info
= NULL
;
1298 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1299 opt_info
= analyze_insns_in_loop (loop
);
1301 wont_exit
= sbitmap_alloc (npeel
+ 1);
1302 sbitmap_zero (wont_exit
);
1304 opt_info_start_duplication (opt_info
);
1306 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1307 npeel
, wont_exit
, NULL
,
1308 NULL
, DLTHE_FLAG_UPDATE_FREQ
1310 ? DLTHE_RECORD_COPY_NUMBER
1318 apply_opt_in_copies (opt_info
, npeel
, false, false);
1319 free_opt_info (opt_info
);
1324 if (desc
->const_iter
)
1326 desc
->niter
-= npeel
;
1327 desc
->niter_expr
= GEN_INT (desc
->niter
);
1328 desc
->noloop_assumptions
= NULL_RTX
;
1332 /* We cannot just update niter_expr, as its value might be clobbered
1333 inside loop. We could handle this by counting the number into
1334 temporary just like we do in runtime unrolling, but it does not
1336 free_simple_loop_desc (loop
);
1340 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1343 /* Decide whether to unroll LOOP stupidly and how much. */
1345 decide_unroll_stupid (struct loop
*loop
, int flags
)
1347 unsigned nunroll
, nunroll_by_av
, i
;
1348 struct niter_desc
*desc
;
1350 if (!(flags
& UAP_UNROLL_ALL
))
1352 /* We were not asked to, just return back silently. */
1357 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1359 /* nunroll = total number of copies of the original loop body in
1360 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1361 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1363 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1364 if (nunroll
> nunroll_by_av
)
1365 nunroll
= nunroll_by_av
;
1366 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1367 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1369 /* Skip big loops. */
1373 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1377 /* Check for simple loops. */
1378 desc
= get_simple_loop_desc (loop
);
1380 /* Check simpleness. */
1381 if (desc
->simple_p
&& !desc
->assumptions
)
1384 fprintf (dump_file
, ";; The loop is simple\n");
1388 /* Do not unroll loops with branches inside -- it increases number
1390 if (num_loop_branches (loop
) > 1)
1393 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1397 /* If we have profile feedback, check whether the loop rolls. */
1398 if (loop
->header
->count
1399 && expected_loop_iterations (loop
) < 2 * nunroll
)
1402 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1406 /* Success. Now force nunroll to be power of 2, as it seems that this
1407 improves results (partially because of better alignments, partially
1408 because of some dark magic). */
1409 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1412 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1413 loop
->lpt_decision
.times
= i
- 1;
1417 ";; Decided to unroll the loop stupidly, %d times.\n",
1418 loop
->lpt_decision
.times
);
1421 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1439 unroll_loop_stupid (struct loop
*loop
)
1442 unsigned nunroll
= loop
->lpt_decision
.times
;
1443 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1444 struct opt_info
*opt_info
= NULL
;
1447 if (flag_split_ivs_in_unroller
1448 || flag_variable_expansion_in_unroller
)
1449 opt_info
= analyze_insns_in_loop (loop
);
1452 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1453 sbitmap_zero (wont_exit
);
1454 opt_info_start_duplication (opt_info
);
1456 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1459 DLTHE_FLAG_UPDATE_FREQ
1461 ? DLTHE_RECORD_COPY_NUMBER
1467 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1468 free_opt_info (opt_info
);
1475 /* We indeed may get here provided that there are nontrivial assumptions
1476 for a loop to be really simple. We could update the counts, but the
1477 problem is that we are unable to decide which exit will be taken
1478 (not really true in case the number of iterations is constant,
1479 but noone will do anything with this information, so we do not
1481 desc
->simple_p
= false;
1485 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1486 nunroll
, num_loop_insns (loop
));
1489 /* A hash function for information about insns to split. */
1492 si_info_hash (const void *ivts
)
1494 return (hashval_t
) INSN_UID (((const struct iv_to_split
*) ivts
)->insn
);
1497 /* An equality functions for information about insns to split. */
1500 si_info_eq (const void *ivts1
, const void *ivts2
)
1502 const struct iv_to_split
*const i1
= (const struct iv_to_split
*) ivts1
;
1503 const struct iv_to_split
*const i2
= (const struct iv_to_split
*) ivts2
;
1505 return i1
->insn
== i2
->insn
;
1508 /* Return a hash for VES, which is really a "var_to_expand *". */
1511 ve_info_hash (const void *ves
)
1513 return (hashval_t
) INSN_UID (((const struct var_to_expand
*) ves
)->insn
);
1516 /* Return true if IVTS1 and IVTS2 (which are really both of type
1517 "var_to_expand *") refer to the same instruction. */
1520 ve_info_eq (const void *ivts1
, const void *ivts2
)
1522 const struct var_to_expand
*const i1
= (const struct var_to_expand
*) ivts1
;
1523 const struct var_to_expand
*const i2
= (const struct var_to_expand
*) ivts2
;
1525 return i1
->insn
== i2
->insn
;
1528 /* Returns true if REG is referenced in one insn in LOOP. */
1531 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
)
1533 basic_block
*body
, bb
;
1538 body
= get_loop_body (loop
);
1539 for (i
= 0; i
< loop
->num_nodes
; i
++)
1543 FOR_BB_INSNS (bb
, insn
)
1545 if (rtx_referenced_p (reg
, insn
))
1549 return (count_ref
== 1);
1552 /* Determine whether INSN contains an accumulator
1553 which can be expanded into separate copies,
1554 one for each copy of the LOOP body.
1556 for (i = 0 ; i < n; i++)
1570 Return NULL if INSN contains no opportunity for expansion of accumulator.
1571 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1572 information and return a pointer to it.
1575 static struct var_to_expand
*
1576 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1578 rtx set
, dest
, src
, op1
, op2
, something
;
1579 struct var_to_expand
*ves
;
1580 enum machine_mode mode1
, mode2
;
1583 set
= single_set (insn
);
1587 dest
= SET_DEST (set
);
1588 src
= SET_SRC (set
);
1590 if (GET_CODE (src
) != PLUS
1591 && GET_CODE (src
) != MINUS
1592 && GET_CODE (src
) != MULT
)
1595 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1596 in MD. But if there is no optab to generate the insn, we can not
1597 perform the variable expansion. This can happen if an MD provides
1598 an insn but not a named pattern to generate it, for example to avoid
1599 producing code that needs additional mode switches like for x87/mmx.
1601 So we check have_insn_for which looks for an optab for the operation
1602 in SRC. If it doesn't exist, we can't perform the expansion even
1603 though INSN is valid. */
1604 if (!have_insn_for (GET_CODE (src
), GET_MODE (src
)))
1607 op1
= XEXP (src
, 0);
1608 op2
= XEXP (src
, 1);
1611 && !(GET_CODE (dest
) == SUBREG
1612 && REG_P (SUBREG_REG (dest
))))
1615 if (rtx_equal_p (dest
, op1
))
1617 else if (rtx_equal_p (dest
, op2
))
1622 /* The method of expansion that we are using; which includes
1623 the initialization of the expansions with zero and the summation of
1624 the expansions at the end of the computation will yield wrong results
1625 for (x = something - x) thus avoid using it in that case. */
1627 && GET_CODE (src
) == MINUS
)
1630 something
= (accum_pos
== 0)? op2
: op1
;
1632 if (!referenced_in_one_insn_in_loop_p (loop
, dest
))
1635 if (rtx_referenced_p (dest
, something
))
1638 mode1
= GET_MODE (dest
);
1639 mode2
= GET_MODE (something
);
1640 if ((FLOAT_MODE_P (mode1
)
1641 || FLOAT_MODE_P (mode2
))
1642 && !flag_associative_math
)
1648 "\n;; Expanding Accumulator ");
1649 print_rtl (dump_file
, dest
);
1650 fprintf (dump_file
, "\n");
1653 /* Record the accumulator to expand. */
1654 ves
= XNEW (struct var_to_expand
);
1656 ves
->reg
= copy_rtx (dest
);
1657 ves
->var_expansions
= VEC_alloc (rtx
, heap
, 1);
1659 ves
->op
= GET_CODE (src
);
1660 ves
->expansion_count
= 0;
1661 ves
->reuse_expansion
= 0;
1662 ves
->accum_pos
= accum_pos
;
1666 /* Determine whether there is an induction variable in INSN that
1667 we would like to split during unrolling.
1687 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1688 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1691 static struct iv_to_split
*
1692 analyze_iv_to_split_insn (rtx insn
)
1696 struct iv_to_split
*ivts
;
1699 /* For now we just split the basic induction variables. Later this may be
1700 extended for example by selecting also addresses of memory references. */
1701 set
= single_set (insn
);
1705 dest
= SET_DEST (set
);
1709 if (!biv_p (insn
, dest
))
1712 ok
= iv_analyze_result (insn
, dest
, &iv
);
1714 /* This used to be an assert under the assumption that if biv_p returns
1715 true that iv_analyze_result must also return true. However, that
1716 assumption is not strictly correct as evidenced by pr25569.
1718 Returning NULL when iv_analyze_result returns false is safe and
1719 avoids the problems in pr25569 until the iv_analyze_* routines
1720 can be fixed, which is apparently hard and time consuming
1721 according to their author. */
1725 if (iv
.step
== const0_rtx
1726 || iv
.mode
!= iv
.extend_mode
)
1729 /* Record the insn to split. */
1730 ivts
= XNEW (struct iv_to_split
);
1732 ivts
->base_var
= NULL_RTX
;
1733 ivts
->step
= iv
.step
;
1741 /* Determines which of insns in LOOP can be optimized.
1742 Return a OPT_INFO struct with the relevant hash tables filled
1743 with all insns to be optimized. The FIRST_NEW_BLOCK field
1744 is undefined for the return value. */
1746 static struct opt_info
*
1747 analyze_insns_in_loop (struct loop
*loop
)
1749 basic_block
*body
, bb
;
1751 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
1753 struct iv_to_split
*ivts
= NULL
;
1754 struct var_to_expand
*ves
= NULL
;
1757 VEC (edge
, heap
) *edges
= get_loop_exit_edges (loop
);
1759 bool can_apply
= false;
1761 iv_analysis_loop_init (loop
);
1763 body
= get_loop_body (loop
);
1765 if (flag_split_ivs_in_unroller
)
1767 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1768 si_info_hash
, si_info_eq
, free
);
1769 opt_info
->iv_to_split_head
= NULL
;
1770 opt_info
->iv_to_split_tail
= &opt_info
->iv_to_split_head
;
1773 /* Record the loop exit bb and loop preheader before the unrolling. */
1774 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1776 if (VEC_length (edge
, edges
) == 1)
1778 exit
= VEC_index (edge
, edges
, 0);
1779 if (!(exit
->flags
& EDGE_COMPLEX
))
1781 opt_info
->loop_exit
= split_edge (exit
);
1786 if (flag_variable_expansion_in_unroller
1789 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1792 opt_info
->var_to_expand_head
= NULL
;
1793 opt_info
->var_to_expand_tail
= &opt_info
->var_to_expand_head
;
1796 for (i
= 0; i
< loop
->num_nodes
; i
++)
1799 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1802 FOR_BB_INSNS (bb
, insn
)
1807 if (opt_info
->insns_to_split
)
1808 ivts
= analyze_iv_to_split_insn (insn
);
1812 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1813 gcc_assert (*slot1
== NULL
);
1815 *opt_info
->iv_to_split_tail
= ivts
;
1816 opt_info
->iv_to_split_tail
= &ivts
->next
;
1820 if (opt_info
->insns_with_var_to_expand
)
1821 ves
= analyze_insn_to_expand_var (loop
, insn
);
1825 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1826 gcc_assert (*slot2
== NULL
);
1828 *opt_info
->var_to_expand_tail
= ves
;
1829 opt_info
->var_to_expand_tail
= &ves
->next
;
1834 VEC_free (edge
, heap
, edges
);
1839 /* Called just before loop duplication. Records start of duplicated area
1843 opt_info_start_duplication (struct opt_info
*opt_info
)
1846 opt_info
->first_new_block
= last_basic_block
;
1849 /* Determine the number of iterations between initialization of the base
1850 variable and the current copy (N_COPY). N_COPIES is the total number
1851 of newly created copies. UNROLLING is true if we are unrolling
1852 (not peeling) the loop. */
1855 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1859 /* If we are unrolling, initialization is done in the original loop
1865 /* If we are peeling, the copy in that the initialization occurs has
1866 number 1. The original loop (number 0) is the last. */
1874 /* Locate in EXPR the expression corresponding to the location recorded
1875 in IVTS, and return a pointer to the RTX for this location. */
1878 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1883 for (i
= 0; i
< ivts
->n_loc
; i
++)
1884 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1889 /* Allocate basic variable for the induction variable chain. */
1892 allocate_basic_variable (struct iv_to_split
*ivts
)
1894 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1896 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1899 /* Insert initialization of basic variable of IVTS before INSN, taking
1900 the initial value from INSN. */
1903 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
1905 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
1909 expr
= force_operand (expr
, ivts
->base_var
);
1910 if (expr
!= ivts
->base_var
)
1911 emit_move_insn (ivts
->base_var
, expr
);
1915 emit_insn_before (seq
, insn
);
1918 /* Replace the use of induction variable described in IVTS in INSN
1919 by base variable + DELTA * step. */
1922 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
1924 rtx expr
, *loc
, seq
, incr
, var
;
1925 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
1928 /* Construct base + DELTA * step. */
1930 expr
= ivts
->base_var
;
1933 incr
= simplify_gen_binary (MULT
, mode
,
1934 ivts
->step
, gen_int_mode (delta
, mode
));
1935 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1936 ivts
->base_var
, incr
);
1939 /* Figure out where to do the replacement. */
1940 loc
= get_ivts_expr (single_set (insn
), ivts
);
1942 /* If we can make the replacement right away, we're done. */
1943 if (validate_change (insn
, loc
, expr
, 0))
1946 /* Otherwise, force EXPR into a register and try again. */
1948 var
= gen_reg_rtx (mode
);
1949 expr
= force_operand (expr
, var
);
1951 emit_move_insn (var
, expr
);
1954 emit_insn_before (seq
, insn
);
1956 if (validate_change (insn
, loc
, var
, 0))
1959 /* The last chance. Try recreating the assignment in insn
1960 completely from scratch. */
1961 set
= single_set (insn
);
1966 src
= copy_rtx (SET_SRC (set
));
1967 dest
= copy_rtx (SET_DEST (set
));
1968 src
= force_operand (src
, dest
);
1970 emit_move_insn (dest
, src
);
1974 emit_insn_before (seq
, insn
);
1979 /* Return one expansion of the accumulator recorded in struct VE. */
1982 get_expansion (struct var_to_expand
*ve
)
1986 if (ve
->reuse_expansion
== 0)
1989 reg
= VEC_index (rtx
, ve
->var_expansions
, ve
->reuse_expansion
- 1);
1991 if (VEC_length (rtx
, ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
1992 ve
->reuse_expansion
= 0;
1994 ve
->reuse_expansion
++;
2000 /* Given INSN replace the uses of the accumulator recorded in VE
2001 with a new register. */
2004 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
2007 bool really_new_expansion
= false;
2009 set
= single_set (insn
);
2012 /* Generate a new register only if the expansion limit has not been
2013 reached. Else reuse an already existing expansion. */
2014 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
2016 really_new_expansion
= true;
2017 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
2020 new_reg
= get_expansion (ve
);
2022 validate_change (insn
, &SET_DEST (set
), new_reg
, 1);
2023 validate_change (insn
, &XEXP (SET_SRC (set
), ve
->accum_pos
), new_reg
, 1);
2025 if (apply_change_group ())
2026 if (really_new_expansion
)
2028 VEC_safe_push (rtx
, heap
, ve
->var_expansions
, new_reg
);
2029 ve
->expansion_count
++;
2033 /* Initialize the variable expansions in loop preheader. PLACE is the
2034 loop-preheader basic block where the initialization of the
2035 expansions should take place. The expansions are initialized with
2036 (-0) when the operation is plus or minus to honor sign zero. This
2037 way we can prevent cases where the sign of the final result is
2038 effected by the sign of the expansion. Here is an example to
2041 for (i = 0 ; i < n; i++)
2055 When SUM is initialized with -zero and SOMETHING is also -zero; the
2056 final result of sum should be -zero thus the expansions sum1 and sum2
2057 should be initialized with -zero as well (otherwise we will get +zero
2058 as the final result). */
2061 insert_var_expansion_initialization (struct var_to_expand
*ve
,
2064 rtx seq
, var
, zero_init
, insn
;
2066 enum machine_mode mode
= GET_MODE (ve
->reg
);
2067 bool honor_signed_zero_p
= HONOR_SIGNED_ZEROS (mode
);
2069 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2073 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
2074 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2076 if (honor_signed_zero_p
)
2077 zero_init
= simplify_gen_unary (NEG
, mode
, CONST0_RTX (mode
), mode
);
2079 zero_init
= CONST0_RTX (mode
);
2081 emit_move_insn (var
, zero_init
);
2083 else if (ve
->op
== MULT
)
2084 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2086 zero_init
= CONST1_RTX (GET_MODE (var
));
2087 emit_move_insn (var
, zero_init
);
2093 insn
= BB_HEAD (place
);
2094 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2095 insn
= NEXT_INSN (insn
);
2097 emit_insn_after (seq
, insn
);
2100 /* Combine the variable expansions at the loop exit. PLACE is the
2101 loop exit basic block where the summation of the expansions should
2105 combine_var_copies_in_loop_exit (struct var_to_expand
*ve
, basic_block place
)
2108 rtx expr
, seq
, var
, insn
;
2111 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2115 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
2116 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2118 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
),
2121 else if (ve
->op
== MULT
)
2122 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2124 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
),
2128 expr
= force_operand (sum
, ve
->reg
);
2129 if (expr
!= ve
->reg
)
2130 emit_move_insn (ve
->reg
, expr
);
2134 insn
= BB_HEAD (place
);
2135 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2136 insn
= NEXT_INSN (insn
);
2138 emit_insn_after (seq
, insn
);
2141 /* Apply loop optimizations in loop copies using the
2142 data which gathered during the unrolling. Structure
2143 OPT_INFO record that data.
2145 UNROLLING is true if we unrolled (not peeled) the loop.
2146 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2147 the loop (as it should happen in complete unrolling, but not in ordinary
2148 peeling of the loop). */
2151 apply_opt_in_copies (struct opt_info
*opt_info
,
2152 unsigned n_copies
, bool unrolling
,
2153 bool rewrite_original_loop
)
2156 basic_block bb
, orig_bb
;
2157 rtx insn
, orig_insn
, next
;
2158 struct iv_to_split ivts_templ
, *ivts
;
2159 struct var_to_expand ve_templ
, *ves
;
2161 /* Sanity check -- we need to put initialization in the original loop
2163 gcc_assert (!unrolling
|| rewrite_original_loop
);
2165 /* Allocate the basic variables (i0). */
2166 if (opt_info
->insns_to_split
)
2167 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
2168 allocate_basic_variable (ivts
);
2170 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2172 bb
= BASIC_BLOCK (i
);
2173 orig_bb
= get_bb_original (bb
);
2175 /* bb->aux holds position in copy sequence initialized by
2176 duplicate_loop_to_header_edge. */
2177 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2180 orig_insn
= BB_HEAD (orig_bb
);
2181 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2183 next
= NEXT_INSN (insn
);
2187 while (!INSN_P (orig_insn
))
2188 orig_insn
= NEXT_INSN (orig_insn
);
2190 ivts_templ
.insn
= orig_insn
;
2191 ve_templ
.insn
= orig_insn
;
2193 /* Apply splitting iv optimization. */
2194 if (opt_info
->insns_to_split
)
2196 ivts
= (struct iv_to_split
*)
2197 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2201 gcc_assert (GET_CODE (PATTERN (insn
))
2202 == GET_CODE (PATTERN (orig_insn
)));
2205 insert_base_initialization (ivts
, insn
);
2206 split_iv (ivts
, insn
, delta
);
2209 /* Apply variable expansion optimization. */
2210 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2212 ves
= (struct var_to_expand
*)
2213 htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2216 gcc_assert (GET_CODE (PATTERN (insn
))
2217 == GET_CODE (PATTERN (orig_insn
)));
2218 expand_var_during_unrolling (ves
, insn
);
2221 orig_insn
= NEXT_INSN (orig_insn
);
2225 if (!rewrite_original_loop
)
2228 /* Initialize the variable expansions in the loop preheader
2229 and take care of combining them at the loop exit. */
2230 if (opt_info
->insns_with_var_to_expand
)
2232 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2233 insert_var_expansion_initialization (ves
, opt_info
->loop_preheader
);
2234 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2235 combine_var_copies_in_loop_exit (ves
, opt_info
->loop_exit
);
2238 /* Rewrite also the original loop body. Find them as originals of the blocks
2239 in the last copied iteration, i.e. those that have
2240 get_bb_copy (get_bb_original (bb)) == bb. */
2241 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2243 bb
= BASIC_BLOCK (i
);
2244 orig_bb
= get_bb_original (bb
);
2245 if (get_bb_copy (orig_bb
) != bb
)
2248 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2249 for (orig_insn
= BB_HEAD (orig_bb
);
2250 orig_insn
!= NEXT_INSN (BB_END (bb
));
2253 next
= NEXT_INSN (orig_insn
);
2255 if (!INSN_P (orig_insn
))
2258 ivts_templ
.insn
= orig_insn
;
2259 if (opt_info
->insns_to_split
)
2261 ivts
= (struct iv_to_split
*)
2262 htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2266 insert_base_initialization (ivts
, orig_insn
);
2267 split_iv (ivts
, orig_insn
, delta
);
2276 /* Release OPT_INFO. */
2279 free_opt_info (struct opt_info
*opt_info
)
2281 if (opt_info
->insns_to_split
)
2282 htab_delete (opt_info
->insns_to_split
);
2283 if (opt_info
->insns_with_var_to_expand
)
2285 struct var_to_expand
*ves
;
2287 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2288 VEC_free (rtx
, heap
, ves
->var_expansions
);
2289 htab_delete (opt_info
->insns_with_var_to_expand
);