1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
38 /* This pass performs loop unrolling and peeling. We only perform these
39 optimizations on innermost loops (with single exception) because
40 the impact on performance is greatest here, and we want to avoid
41 unnecessary code size growth. The gain is caused by greater sequentiality
42 of code, better code to optimize for further passes and in some cases
43 by fewer testings of exit conditions. The main problem is code growth,
44 that impacts performance negatively due to effect of caches.
48 -- complete peeling of once-rolling loops; this is the above mentioned
49 exception, as this causes loop to be cancelled completely and
50 does not cause code growth
51 -- complete peeling of loops that roll (small) constant times.
52 -- simple peeling of first iterations of loops that do not roll much
53 (according to profile feedback)
54 -- unrolling of loops that roll constant times; this is almost always
55 win, as we get rid of exit condition tests.
56 -- unrolling of loops that roll number of times that we can compute
57 in runtime; we also get rid of exit condition tests here, but there
58 is the extra expense for calculating the number of iterations
59 -- simple unrolling of remaining loops; this is performed only if we
60 are asked to, as the gain is questionable in this case and often
61 it may even slow down the code
62 For more detailed descriptions of each of those, see comments at
63 appropriate function below.
65 There is a lot of parameters (defined and described in params.def) that
66 control how much we unroll/peel.
68 ??? A great problem is that we don't have a good way how to determine
69 how many times we should unroll the loop; the experiments I have made
70 showed that this choice may affect performance in order of several %.
73 /* Information about induction variables to split. */
77 rtx insn
; /* The insn in that the induction variable occurs. */
78 rtx base_var
; /* The variable on that the values in the further
79 iterations are based. */
80 rtx step
; /* Step of the induction variable. */
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 varray_type var_expansions
; /* The copies of the accumulator which is expanded. */
95 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
97 int expansion_count
; /* Count the number of expansions generated so far. */
98 int reuse_expansion
; /* The expansion we intend to reuse to expand
99 the accumulator. If REUSE_EXPANSION is 0 reuse
100 the original accumulator. Else use
101 var_expansions[REUSE_EXPANSION - 1]. */
104 /* Information about optimization applied in
105 the unrolled loop. */
109 htab_t insns_to_split
; /* A hashtable of insns to split. */
110 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
112 unsigned first_new_block
; /* The first basic block that was
114 basic_block loop_exit
; /* The loop exit basic block. */
115 basic_block loop_preheader
; /* The loop preheader basic block. */
118 static void decide_unrolling_and_peeling (struct loops
*, int);
119 static void peel_loops_completely (struct loops
*, int);
120 static void decide_peel_simple (struct loop
*, int);
121 static void decide_peel_once_rolling (struct loop
*, int);
122 static void decide_peel_completely (struct loop
*, int);
123 static void decide_unroll_stupid (struct loop
*, int);
124 static void decide_unroll_constant_iterations (struct loop
*, int);
125 static void decide_unroll_runtime_iterations (struct loop
*, int);
126 static void peel_loop_simple (struct loops
*, struct loop
*);
127 static void peel_loop_completely (struct loops
*, struct loop
*);
128 static void unroll_loop_stupid (struct loops
*, struct loop
*);
129 static void unroll_loop_constant_iterations (struct loops
*, struct loop
*);
130 static void unroll_loop_runtime_iterations (struct loops
*, struct loop
*);
131 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
132 static void opt_info_start_duplication (struct opt_info
*);
133 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
134 static void free_opt_info (struct opt_info
*);
135 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
136 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
);
137 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
138 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
139 static int insert_var_expansion_initialization (void **, void *);
140 static int combine_var_copies_in_loop_exit (void **, void *);
141 static int release_var_copies (void **, void *);
142 static rtx
get_expansion (struct var_to_expand
*);
144 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
146 unroll_and_peel_loops (struct loops
*loops
, int flags
)
148 struct loop
*loop
, *next
;
151 /* First perform complete loop peeling (it is almost surely a win,
152 and affects parameters for further decision a lot). */
153 peel_loops_completely (loops
, flags
);
155 /* Now decide rest of unrolling and peeling. */
156 decide_unrolling_and_peeling (loops
, flags
);
158 loop
= loops
->tree_root
;
162 /* Scan the loops, inner ones first. */
163 while (loop
!= loops
->tree_root
)
175 /* And perform the appropriate transformations. */
176 switch (loop
->lpt_decision
.decision
)
178 case LPT_PEEL_COMPLETELY
:
181 case LPT_PEEL_SIMPLE
:
182 peel_loop_simple (loops
, loop
);
184 case LPT_UNROLL_CONSTANT
:
185 unroll_loop_constant_iterations (loops
, loop
);
187 case LPT_UNROLL_RUNTIME
:
188 unroll_loop_runtime_iterations (loops
, loop
);
190 case LPT_UNROLL_STUPID
:
191 unroll_loop_stupid (loops
, loop
);
201 #ifdef ENABLE_CHECKING
202 verify_dominators (CDI_DOMINATORS
);
203 verify_loop_structure (loops
);
212 /* Check whether exit of the LOOP is at the end of loop body. */
215 loop_exit_at_end_p (struct loop
*loop
)
217 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
220 if (desc
->in_edge
->dest
!= loop
->latch
)
223 /* Check that the latch is empty. */
224 FOR_BB_INSNS (loop
->latch
, insn
)
233 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
235 peel_loops_completely (struct loops
*loops
, int flags
)
240 /* Scan the loops, the inner ones first. */
241 for (i
= loops
->num
- 1; i
> 0; i
--)
243 loop
= loops
->parray
[i
];
247 loop
->lpt_decision
.decision
= LPT_NONE
;
251 "\n;; *** Considering loop %d for complete peeling ***\n",
254 loop
->ninsns
= num_loop_insns (loop
);
256 decide_peel_once_rolling (loop
, flags
);
257 if (loop
->lpt_decision
.decision
== LPT_NONE
)
258 decide_peel_completely (loop
, flags
);
260 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
262 peel_loop_completely (loops
, loop
);
263 #ifdef ENABLE_CHECKING
264 verify_dominators (CDI_DOMINATORS
);
265 verify_loop_structure (loops
);
271 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
273 decide_unrolling_and_peeling (struct loops
*loops
, int flags
)
275 struct loop
*loop
= loops
->tree_root
, *next
;
280 /* Scan the loops, inner ones first. */
281 while (loop
!= loops
->tree_root
)
292 loop
->lpt_decision
.decision
= LPT_NONE
;
295 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
297 /* Do not peel cold areas. */
298 if (!maybe_hot_bb_p (loop
->header
))
301 fprintf (dump_file
, ";; Not considering loop, cold area\n");
306 /* Can the loop be manipulated? */
307 if (!can_duplicate_loop_p (loop
))
311 ";; Not considering loop, cannot duplicate\n");
316 /* Skip non-innermost loops. */
320 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
325 loop
->ninsns
= num_loop_insns (loop
);
326 loop
->av_ninsns
= average_num_loop_insns (loop
);
328 /* Try transformations one by one in decreasing order of
331 decide_unroll_constant_iterations (loop
, flags
);
332 if (loop
->lpt_decision
.decision
== LPT_NONE
)
333 decide_unroll_runtime_iterations (loop
, flags
);
334 if (loop
->lpt_decision
.decision
== LPT_NONE
)
335 decide_unroll_stupid (loop
, flags
);
336 if (loop
->lpt_decision
.decision
== LPT_NONE
)
337 decide_peel_simple (loop
, flags
);
343 /* Decide whether the LOOP is once rolling and suitable for complete
346 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
348 struct niter_desc
*desc
;
351 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
353 /* Is the loop small enough? */
354 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
357 fprintf (dump_file
, ";; Not considering loop, is too big\n");
361 /* Check for simple loops. */
362 desc
= get_simple_loop_desc (loop
);
364 /* Check number of iterations. */
373 ";; Unable to prove that the loop rolls exactly once\n");
379 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
380 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
383 /* Decide whether the LOOP is suitable for complete peeling. */
385 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
388 struct niter_desc
*desc
;
391 fprintf (dump_file
, "\n;; Considering peeling completely\n");
393 /* Skip non-innermost loops. */
397 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
401 /* Do not peel cold areas. */
402 if (!maybe_hot_bb_p (loop
->header
))
405 fprintf (dump_file
, ";; Not considering loop, cold area\n");
409 /* Can the loop be manipulated? */
410 if (!can_duplicate_loop_p (loop
))
414 ";; Not considering loop, cannot duplicate\n");
418 /* npeel = number of iterations to peel. */
419 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
420 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
421 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
423 /* Is the loop small enough? */
427 fprintf (dump_file
, ";; Not considering loop, is too big\n");
431 /* Check for simple loops. */
432 desc
= get_simple_loop_desc (loop
);
434 /* Check number of iterations. */
442 ";; Unable to prove that the loop iterates constant times\n");
446 if (desc
->niter
> npeel
- 1)
451 ";; Not peeling loop completely, rolls too much (");
452 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
453 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
460 fprintf (dump_file
, ";; Decided to peel loop completely\n");
461 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
464 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
465 completely. The transformation done:
467 for (i = 0; i < 4; i++)
479 peel_loop_completely (struct loops
*loops
, struct loop
*loop
)
482 unsigned HOST_WIDE_INT npeel
;
483 unsigned n_remove_edges
, i
;
484 edge
*remove_edges
, ein
;
485 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
486 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
= xcalloc (npeel
, sizeof (edge
));
501 if (flag_split_ivs_in_unroller
)
502 opt_info
= analyze_insns_in_loop (loop
);
504 opt_info_start_duplication (opt_info
);
505 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
507 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
508 DLTHE_FLAG_UPDATE_FREQ
))
515 apply_opt_in_copies (opt_info
, npeel
, false, true);
516 free_opt_info (opt_info
);
519 /* Remove the exit edges. */
520 for (i
= 0; i
< n_remove_edges
; i
++)
521 remove_path (loops
, remove_edges
[i
]);
526 free_simple_loop_desc (loop
);
528 /* Now remove the unreachable part of the last iteration and cancel
530 remove_path (loops
, ein
);
533 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
536 /* Decide whether to unroll LOOP iterating constant number of times
540 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
542 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
543 struct niter_desc
*desc
;
545 if (!(flags
& UAP_UNROLL
))
547 /* We were not asked to, just return back silently. */
553 "\n;; Considering unrolling loop with constant "
554 "number of iterations\n");
556 /* nunroll = total number of copies of the original loop body in
557 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
558 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
560 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
561 if (nunroll
> nunroll_by_av
)
562 nunroll
= nunroll_by_av
;
563 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
564 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
566 /* Skip big loops. */
570 fprintf (dump_file
, ";; Not considering loop, is too big\n");
574 /* Check for simple loops. */
575 desc
= get_simple_loop_desc (loop
);
577 /* Check number of iterations. */
578 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
582 ";; Unable to prove that the loop iterates constant times\n");
586 /* Check whether the loop rolls enough to consider. */
587 if (desc
->niter
< 2 * nunroll
)
590 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
594 /* Success; now compute number of iterations to unroll. We alter
595 nunroll so that as few as possible copies of loop body are
596 necessary, while still not decreasing the number of unrollings
597 too much (at most by 1). */
598 best_copies
= 2 * nunroll
+ 10;
601 if (i
- 1 >= desc
->niter
)
604 for (; i
>= nunroll
- 1; i
--)
606 unsigned exit_mod
= desc
->niter
% (i
+ 1);
608 if (!loop_exit_at_end_p (loop
))
609 n_copies
= exit_mod
+ i
+ 1;
610 else if (exit_mod
!= (unsigned) i
611 || desc
->noloop_assumptions
!= NULL_RTX
)
612 n_copies
= exit_mod
+ i
+ 2;
616 if (n_copies
< best_copies
)
618 best_copies
= n_copies
;
624 fprintf (dump_file
, ";; max_unroll %d (%d copies, initial %d).\n",
625 best_unroll
+ 1, best_copies
, nunroll
);
627 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
628 loop
->lpt_decision
.times
= best_unroll
;
632 ";; Decided to unroll the constant times rolling loop, %d times.\n",
633 loop
->lpt_decision
.times
);
636 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
637 times. The transformation does this:
639 for (i = 0; i < 102; i++)
656 unroll_loop_constant_iterations (struct loops
*loops
, struct loop
*loop
)
658 unsigned HOST_WIDE_INT niter
;
661 unsigned n_remove_edges
, i
;
663 unsigned max_unroll
= loop
->lpt_decision
.times
;
664 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
665 bool exit_at_end
= loop_exit_at_end_p (loop
);
666 struct opt_info
*opt_info
= NULL
;
670 /* Should not get here (such loop should be peeled instead). */
671 gcc_assert (niter
> max_unroll
+ 1);
673 exit_mod
= niter
% (max_unroll
+ 1);
675 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
676 sbitmap_ones (wont_exit
);
678 remove_edges
= xcalloc (max_unroll
+ exit_mod
+ 1, sizeof (edge
));
680 if (flag_split_ivs_in_unroller
681 || flag_variable_expansion_in_unroller
)
682 opt_info
= analyze_insns_in_loop (loop
);
686 /* The exit is not at the end of the loop; leave exit test
687 in the first copy, so that the loops that start with test
688 of exit condition have continuous body after unrolling. */
691 fprintf (dump_file
, ";; Condition on beginning of loop.\n");
693 /* Peel exit_mod iterations. */
694 RESET_BIT (wont_exit
, 0);
695 if (desc
->noloop_assumptions
)
696 RESET_BIT (wont_exit
, 1);
700 opt_info_start_duplication (opt_info
);
701 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
703 wont_exit
, desc
->out_edge
,
704 remove_edges
, &n_remove_edges
,
705 DLTHE_FLAG_UPDATE_FREQ
))
708 if (opt_info
&& exit_mod
> 1)
709 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
711 desc
->noloop_assumptions
= NULL_RTX
;
712 desc
->niter
-= exit_mod
;
713 desc
->niter_max
-= exit_mod
;
716 SET_BIT (wont_exit
, 1);
720 /* Leave exit test in last copy, for the same reason as above if
721 the loop tests the condition at the end of loop body. */
724 fprintf (dump_file
, ";; Condition on end of loop.\n");
726 /* We know that niter >= max_unroll + 2; so we do not need to care of
727 case when we would exit before reaching the loop. So just peel
728 exit_mod + 1 iterations. */
729 if (exit_mod
!= max_unroll
730 || desc
->noloop_assumptions
)
732 RESET_BIT (wont_exit
, 0);
733 if (desc
->noloop_assumptions
)
734 RESET_BIT (wont_exit
, 1);
736 opt_info_start_duplication (opt_info
);
737 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
739 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
740 DLTHE_FLAG_UPDATE_FREQ
))
743 if (opt_info
&& exit_mod
> 0)
744 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
746 desc
->niter
-= exit_mod
+ 1;
747 desc
->niter_max
-= exit_mod
+ 1;
748 desc
->noloop_assumptions
= NULL_RTX
;
750 SET_BIT (wont_exit
, 0);
751 SET_BIT (wont_exit
, 1);
754 RESET_BIT (wont_exit
, max_unroll
);
757 /* Now unroll the loop. */
759 opt_info_start_duplication (opt_info
);
760 if (!duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
762 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
763 DLTHE_FLAG_UPDATE_FREQ
))
768 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
769 free_opt_info (opt_info
);
776 basic_block exit_block
= desc
->in_edge
->src
->rbi
->copy
;
777 /* Find a new in and out edge; they are in the last copy we have made. */
779 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
781 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
782 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
786 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
787 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
791 desc
->niter
/= max_unroll
+ 1;
792 desc
->niter_max
/= max_unroll
+ 1;
793 desc
->niter_expr
= GEN_INT (desc
->niter
);
795 /* Remove the edges. */
796 for (i
= 0; i
< n_remove_edges
; i
++)
797 remove_path (loops
, remove_edges
[i
]);
802 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
803 max_unroll
, num_loop_insns (loop
));
806 /* Decide whether to unroll LOOP iterating runtime computable number of times
809 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
811 unsigned nunroll
, nunroll_by_av
, i
;
812 struct niter_desc
*desc
;
814 if (!(flags
& UAP_UNROLL
))
816 /* We were not asked to, just return back silently. */
822 "\n;; Considering unrolling loop with runtime "
823 "computable number of iterations\n");
825 /* nunroll = total number of copies of the original loop body in
826 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
827 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
828 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
829 if (nunroll
> nunroll_by_av
)
830 nunroll
= nunroll_by_av
;
831 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
832 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
834 /* Skip big loops. */
838 fprintf (dump_file
, ";; Not considering loop, is too big\n");
842 /* Check for simple loops. */
843 desc
= get_simple_loop_desc (loop
);
845 /* Check simpleness. */
846 if (!desc
->simple_p
|| desc
->assumptions
)
850 ";; Unable to prove that the number of iterations "
851 "can be counted in runtime\n");
855 if (desc
->const_iter
)
858 fprintf (dump_file
, ";; Loop iterates constant times\n");
862 /* If we have profile feedback, check whether the loop rolls. */
863 if (loop
->header
->count
&& expected_loop_iterations (loop
) < 2 * nunroll
)
866 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
870 /* Success; now force nunroll to be power of 2, as we are unable to
871 cope with overflows in computation of number of iterations. */
872 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
875 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
876 loop
->lpt_decision
.times
= i
- 1;
880 ";; Decided to unroll the runtime computable "
881 "times rolling loop, %d times.\n",
882 loop
->lpt_decision
.times
);
885 /* Unroll LOOP for that we are able to count number of iterations in runtime
886 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
887 extra care for case n < 0):
889 for (i = 0; i < n; i++)
917 unroll_loop_runtime_iterations (struct loops
*loops
, struct loop
*loop
)
919 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
921 basic_block preheader
, *body
, *dom_bbs
, swtch
, ezc_swtch
;
925 unsigned n_peel
, n_remove_edges
;
926 edge
*remove_edges
, e
;
927 bool extra_zero_check
, last_may_exit
;
928 unsigned max_unroll
= loop
->lpt_decision
.times
;
929 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
930 bool exit_at_end
= loop_exit_at_end_p (loop
);
931 struct opt_info
*opt_info
= NULL
;
933 if (flag_split_ivs_in_unroller
934 || flag_variable_expansion_in_unroller
)
935 opt_info
= analyze_insns_in_loop (loop
);
937 /* Remember blocks whose dominators will have to be updated. */
938 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
941 body
= get_loop_body (loop
);
942 for (i
= 0; i
< loop
->num_nodes
; i
++)
947 nldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
], &ldom
);
948 for (j
= 0; j
< nldom
; j
++)
949 if (!flow_bb_inside_loop_p (loop
, ldom
[j
]))
950 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
958 /* Leave exit in first copy (for explanation why see comment in
959 unroll_loop_constant_iterations). */
961 n_peel
= max_unroll
- 1;
962 extra_zero_check
= true;
963 last_may_exit
= false;
967 /* Leave exit in last copy (for explanation why see comment in
968 unroll_loop_constant_iterations). */
969 may_exit_copy
= max_unroll
;
971 extra_zero_check
= false;
972 last_may_exit
= true;
975 /* Get expression for number of iterations. */
977 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
978 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
980 emit_move_insn (niter
, tmp
);
982 /* Count modulo by ANDing it with max_unroll; we use the fact that
983 the number of unrollings is a power of two, and thus this is correct
984 even if there is overflow in the computation. */
985 niter
= expand_simple_binop (desc
->mode
, AND
,
987 GEN_INT (max_unroll
),
988 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
990 init_code
= get_insns ();
993 /* Precondition the loop. */
994 loop_split_edge_with (loop_preheader_edge (loop
), init_code
);
996 remove_edges
= xcalloc (max_unroll
+ n_peel
+ 1, sizeof (edge
));
999 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1001 /* Peel the first copy of loop body (almost always we must leave exit test
1002 here; the only exception is when we have extra zero check and the number
1003 of iterations is reliable. Also record the place of (possible) extra
1005 sbitmap_zero (wont_exit
);
1006 if (extra_zero_check
1007 && !desc
->noloop_assumptions
)
1008 SET_BIT (wont_exit
, 1);
1009 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1010 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1012 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
1013 DLTHE_FLAG_UPDATE_FREQ
))
1016 /* Record the place where switch will be built for preconditioning. */
1017 swtch
= loop_split_edge_with (loop_preheader_edge (loop
),
1020 for (i
= 0; i
< n_peel
; i
++)
1022 /* Peel the copy. */
1023 sbitmap_zero (wont_exit
);
1024 if (i
!= n_peel
- 1 || !last_may_exit
)
1025 SET_BIT (wont_exit
, 1);
1026 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1028 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
1029 DLTHE_FLAG_UPDATE_FREQ
))
1032 /* Create item for switch. */
1033 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1034 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1036 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1037 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1038 block_label (preheader
), p
, NULL_RTX
);
1040 swtch
= loop_split_edge_with (EDGE_PRED (swtch
, 0), branch_code
);
1041 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1042 EDGE_SUCC (swtch
, 0)->probability
= REG_BR_PROB_BASE
- p
;
1043 e
= make_edge (swtch
, preheader
,
1044 EDGE_SUCC (swtch
, 0)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1048 if (extra_zero_check
)
1050 /* Add branch for zero iterations. */
1051 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1053 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1054 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1055 block_label (preheader
), p
, NULL_RTX
);
1057 swtch
= loop_split_edge_with (EDGE_SUCC (swtch
, 0), branch_code
);
1058 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1059 EDGE_SUCC (swtch
, 0)->probability
= REG_BR_PROB_BASE
- p
;
1060 e
= make_edge (swtch
, preheader
,
1061 EDGE_SUCC (swtch
, 0)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1065 /* Recount dominators for outer blocks. */
1066 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
1068 /* And unroll loop. */
1070 sbitmap_ones (wont_exit
);
1071 RESET_BIT (wont_exit
, may_exit_copy
);
1072 opt_info_start_duplication (opt_info
);
1074 if (!duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1076 wont_exit
, desc
->out_edge
, remove_edges
, &n_remove_edges
,
1077 DLTHE_FLAG_UPDATE_FREQ
))
1082 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1083 free_opt_info (opt_info
);
1090 basic_block exit_block
= desc
->in_edge
->src
->rbi
->copy
;
1091 /* Find a new in and out edge; they are in the last copy we have made. */
1093 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1095 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1096 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1100 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1101 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1105 /* Remove the edges. */
1106 for (i
= 0; i
< n_remove_edges
; i
++)
1107 remove_path (loops
, remove_edges
[i
]);
1108 free (remove_edges
);
1110 /* We must be careful when updating the number of iterations due to
1111 preconditioning and the fact that the value must be valid at entry
1112 of the loop. After passing through the above code, we see that
1113 the correct new number of iterations is this: */
1114 gcc_assert (!desc
->const_iter
);
1116 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
, GEN_INT (max_unroll
+ 1));
1117 desc
->niter_max
/= max_unroll
+ 1;
1121 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1122 desc
->noloop_assumptions
= NULL_RTX
;
1128 ";; Unrolled loop %d times, counting # of iterations "
1129 "in runtime, %i insns\n",
1130 max_unroll
, num_loop_insns (loop
));
1133 /* Decide whether to simply peel LOOP and how much. */
1135 decide_peel_simple (struct loop
*loop
, int flags
)
1138 struct niter_desc
*desc
;
1140 if (!(flags
& UAP_PEEL
))
1142 /* We were not asked to, just return back silently. */
1147 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1149 /* npeel = number of iterations to peel. */
1150 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1151 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1152 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1154 /* Skip big loops. */
1158 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1162 /* Check for simple loops. */
1163 desc
= get_simple_loop_desc (loop
);
1165 /* Check number of iterations. */
1166 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1169 fprintf (dump_file
, ";; Loop iterates constant times\n");
1173 /* Do not simply peel loops with branches inside -- it increases number
1175 if (num_loop_branches (loop
) > 1)
1178 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1182 if (loop
->header
->count
)
1184 unsigned niter
= expected_loop_iterations (loop
);
1185 if (niter
+ 1 > npeel
)
1189 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1190 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1191 (HOST_WIDEST_INT
) (niter
+ 1));
1192 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1201 /* For now we have no good heuristics to decide whether loop peeling
1202 will be effective, so disable it. */
1205 ";; Not peeling loop, no evidence it will be profitable\n");
1210 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1211 loop
->lpt_decision
.times
= npeel
;
1214 fprintf (dump_file
, ";; Decided to simply peel the loop, %d times.\n",
1215 loop
->lpt_decision
.times
);
1218 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1224 if (!cond) goto end;
1226 if (!cond) goto end;
1233 peel_loop_simple (struct loops
*loops
, struct loop
*loop
)
1236 unsigned npeel
= loop
->lpt_decision
.times
;
1237 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1238 struct opt_info
*opt_info
= NULL
;
1240 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1241 opt_info
= analyze_insns_in_loop (loop
);
1243 wont_exit
= sbitmap_alloc (npeel
+ 1);
1244 sbitmap_zero (wont_exit
);
1246 opt_info_start_duplication (opt_info
);
1248 if (!duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1249 loops
, npeel
, wont_exit
, NULL
, NULL
, NULL
,
1250 DLTHE_FLAG_UPDATE_FREQ
))
1257 apply_opt_in_copies (opt_info
, npeel
, false, false);
1258 free_opt_info (opt_info
);
1263 if (desc
->const_iter
)
1265 desc
->niter
-= npeel
;
1266 desc
->niter_expr
= GEN_INT (desc
->niter
);
1267 desc
->noloop_assumptions
= NULL_RTX
;
1271 /* We cannot just update niter_expr, as its value might be clobbered
1272 inside loop. We could handle this by counting the number into
1273 temporary just like we do in runtime unrolling, but it does not
1275 free_simple_loop_desc (loop
);
1279 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1282 /* Decide whether to unroll LOOP stupidly and how much. */
1284 decide_unroll_stupid (struct loop
*loop
, int flags
)
1286 unsigned nunroll
, nunroll_by_av
, i
;
1287 struct niter_desc
*desc
;
1289 if (!(flags
& UAP_UNROLL_ALL
))
1291 /* We were not asked to, just return back silently. */
1296 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1298 /* nunroll = total number of copies of the original loop body in
1299 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1300 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1302 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1303 if (nunroll
> nunroll_by_av
)
1304 nunroll
= nunroll_by_av
;
1305 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1306 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1308 /* Skip big loops. */
1312 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1316 /* Check for simple loops. */
1317 desc
= get_simple_loop_desc (loop
);
1319 /* Check simpleness. */
1320 if (desc
->simple_p
&& !desc
->assumptions
)
1323 fprintf (dump_file
, ";; The loop is simple\n");
1327 /* Do not unroll loops with branches inside -- it increases number
1329 if (num_loop_branches (loop
) > 1)
1332 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1336 /* If we have profile feedback, check whether the loop rolls. */
1337 if (loop
->header
->count
1338 && expected_loop_iterations (loop
) < 2 * nunroll
)
1341 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1345 /* Success. Now force nunroll to be power of 2, as it seems that this
1346 improves results (partially because of better alignments, partially
1347 because of some dark magic). */
1348 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1351 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1352 loop
->lpt_decision
.times
= i
- 1;
1356 ";; Decided to unroll the loop stupidly, %d times.\n",
1357 loop
->lpt_decision
.times
);
1360 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1378 unroll_loop_stupid (struct loops
*loops
, struct loop
*loop
)
1381 unsigned nunroll
= loop
->lpt_decision
.times
;
1382 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1383 struct opt_info
*opt_info
= NULL
;
1385 if (flag_split_ivs_in_unroller
1386 || flag_variable_expansion_in_unroller
)
1387 opt_info
= analyze_insns_in_loop (loop
);
1390 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1391 sbitmap_zero (wont_exit
);
1392 opt_info_start_duplication (opt_info
);
1394 if (!duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1395 loops
, nunroll
, wont_exit
, NULL
, NULL
, NULL
,
1396 DLTHE_FLAG_UPDATE_FREQ
))
1401 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1402 free_opt_info (opt_info
);
1409 /* We indeed may get here provided that there are nontrivial assumptions
1410 for a loop to be really simple. We could update the counts, but the
1411 problem is that we are unable to decide which exit will be taken
1412 (not really true in case the number of iterations is constant,
1413 but noone will do anything with this information, so we do not
1415 desc
->simple_p
= false;
1419 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1420 nunroll
, num_loop_insns (loop
));
1423 /* A hash function for information about insns to split. */
1426 si_info_hash (const void *ivts
)
1428 return htab_hash_pointer (((struct iv_to_split
*) ivts
)->insn
);
1431 /* An equality functions for information about insns to split. */
1434 si_info_eq (const void *ivts1
, const void *ivts2
)
1436 const struct iv_to_split
*i1
= ivts1
;
1437 const struct iv_to_split
*i2
= ivts2
;
1439 return i1
->insn
== i2
->insn
;
1442 /* Return a hash for VES, which is really a "var_to_expand *". */
1445 ve_info_hash (const void *ves
)
1447 return htab_hash_pointer (((struct var_to_expand
*) ves
)->insn
);
1450 /* Return true if IVTS1 and IVTS2 (which are really both of type
1451 "var_to_expand *") refer to the same instruction. */
1454 ve_info_eq (const void *ivts1
, const void *ivts2
)
1456 const struct var_to_expand
*i1
= ivts1
;
1457 const struct var_to_expand
*i2
= ivts2
;
1459 return i1
->insn
== i2
->insn
;
1462 /* Returns true if REG is referenced in one insn in LOOP. */
1465 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
)
1467 basic_block
*body
, bb
;
1472 body
= get_loop_body (loop
);
1473 for (i
= 0; i
< loop
->num_nodes
; i
++)
1477 FOR_BB_INSNS (bb
, insn
)
1479 if (rtx_referenced_p (reg
, insn
))
1483 return (count_ref
== 1);
1486 /* Determine whether INSN contains an accumulator
1487 which can be expanded into separate copies,
1488 one for each copy of the LOOP body.
1490 for (i = 0 ; i < n; i++)
1504 Return NULL if INSN contains no opportunity for expansion of accumulator.
1505 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1506 information and return a pointer to it.
1509 static struct var_to_expand
*
1510 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1512 rtx set
, dest
, src
, op1
;
1513 struct var_to_expand
*ves
;
1514 enum machine_mode mode1
, mode2
;
1516 set
= single_set (insn
);
1520 dest
= SET_DEST (set
);
1521 src
= SET_SRC (set
);
1523 if (GET_CODE (src
) != PLUS
1524 && GET_CODE (src
) != MINUS
1525 && GET_CODE (src
) != MULT
)
1531 op1
= XEXP (src
, 0);
1534 && !(GET_CODE (dest
) == SUBREG
1535 && REG_P (SUBREG_REG (dest
))))
1538 if (!rtx_equal_p (dest
, op1
))
1541 if (!referenced_in_one_insn_in_loop_p (loop
, dest
))
1544 if (rtx_referenced_p (dest
, XEXP (src
, 1)))
1547 mode1
= GET_MODE (dest
);
1548 mode2
= GET_MODE (XEXP (src
, 1));
1549 if ((FLOAT_MODE_P (mode1
)
1550 || FLOAT_MODE_P (mode2
))
1551 && !flag_unsafe_math_optimizations
)
1554 /* Record the accumulator to expand. */
1555 ves
= xmalloc (sizeof (struct var_to_expand
));
1557 VARRAY_RTX_INIT (ves
->var_expansions
, 1, "var_expansions");
1558 ves
->reg
= copy_rtx (dest
);
1559 ves
->op
= GET_CODE (src
);
1560 ves
->expansion_count
= 0;
1561 ves
->reuse_expansion
= 0;
1565 /* Determine whether there is an induction variable in INSN that
1566 we would like to split during unrolling.
1586 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1587 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1590 static struct iv_to_split
*
1591 analyze_iv_to_split_insn (rtx insn
)
1595 struct iv_to_split
*ivts
;
1597 /* For now we just split the basic induction variables. Later this may be
1598 extended for example by selecting also addresses of memory references. */
1599 set
= single_set (insn
);
1603 dest
= SET_DEST (set
);
1607 if (!biv_p (insn
, dest
))
1610 if (!iv_analyze (insn
, dest
, &iv
))
1613 if (iv
.step
== const0_rtx
1614 || iv
.mode
!= iv
.extend_mode
)
1617 /* Record the insn to split. */
1618 ivts
= xmalloc (sizeof (struct iv_to_split
));
1620 ivts
->base_var
= NULL_RTX
;
1621 ivts
->step
= iv
.step
;
1628 /* Determines which of insns in LOOP can be optimized.
1629 Return a OPT_INFO struct with the relevant hash tables filled
1630 with all insns to be optimized. The FIRST_NEW_BLOCK field
1631 is undefined for the return value. */
1633 static struct opt_info
*
1634 analyze_insns_in_loop (struct loop
*loop
)
1636 basic_block
*body
, bb
;
1637 unsigned i
, n_edges
= 0;
1638 struct opt_info
*opt_info
= xcalloc (1, sizeof (struct opt_info
));
1640 struct iv_to_split
*ivts
= NULL
;
1641 struct var_to_expand
*ves
= NULL
;
1644 edge
*edges
= get_loop_exit_edges (loop
, &n_edges
);
1645 basic_block preheader
;
1646 bool can_apply
= false;
1648 iv_analysis_loop_init (loop
);
1650 body
= get_loop_body (loop
);
1652 if (flag_split_ivs_in_unroller
)
1653 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1654 si_info_hash
, si_info_eq
, free
);
1656 /* Record the loop exit bb and loop preheader before the unrolling. */
1657 if (!loop_preheader_edge (loop
)->src
)
1659 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1660 opt_info
->loop_preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1663 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1666 && !(edges
[0]->flags
& EDGE_COMPLEX
)
1667 && (edges
[0]->flags
& EDGE_LOOP_EXIT
))
1669 opt_info
->loop_exit
= loop_split_edge_with (edges
[0], NULL_RTX
);
1673 if (flag_variable_expansion_in_unroller
1675 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1676 ve_info_hash
, ve_info_eq
, free
);
1678 for (i
= 0; i
< loop
->num_nodes
; i
++)
1681 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1684 FOR_BB_INSNS (bb
, insn
)
1689 if (opt_info
->insns_to_split
)
1690 ivts
= analyze_iv_to_split_insn (insn
);
1694 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1699 if (opt_info
->insns_with_var_to_expand
)
1700 ves
= analyze_insn_to_expand_var (loop
, insn
);
1704 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1715 /* Called just before loop duplication. Records start of duplicated area
1719 opt_info_start_duplication (struct opt_info
*opt_info
)
1722 opt_info
->first_new_block
= last_basic_block
;
1725 /* Determine the number of iterations between initialization of the base
1726 variable and the current copy (N_COPY). N_COPIES is the total number
1727 of newly created copies. UNROLLING is true if we are unrolling
1728 (not peeling) the loop. */
1731 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1735 /* If we are unrolling, initialization is done in the original loop
1741 /* If we are peeling, the copy in that the initialization occurs has
1742 number 1. The original loop (number 0) is the last. */
1750 /* Locate in EXPR the expression corresponding to the location recorded
1751 in IVTS, and return a pointer to the RTX for this location. */
1754 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1759 for (i
= 0; i
< ivts
->n_loc
; i
++)
1760 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1765 /* Allocate basic variable for the induction variable chain. Callback for
1769 allocate_basic_variable (void **slot
, void *data ATTRIBUTE_UNUSED
)
1771 struct iv_to_split
*ivts
= *slot
;
1772 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1774 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1779 /* Insert initialization of basic variable of IVTS before INSN, taking
1780 the initial value from INSN. */
1783 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
1785 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
1789 expr
= force_operand (expr
, ivts
->base_var
);
1790 if (expr
!= ivts
->base_var
)
1791 emit_move_insn (ivts
->base_var
, expr
);
1795 emit_insn_before (seq
, insn
);
1798 /* Replace the use of induction variable described in IVTS in INSN
1799 by base variable + DELTA * step. */
1802 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
1804 rtx expr
, *loc
, seq
, incr
, var
;
1805 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
1808 /* Construct base + DELTA * step. */
1810 expr
= ivts
->base_var
;
1813 incr
= simplify_gen_binary (MULT
, mode
,
1814 ivts
->step
, gen_int_mode (delta
, mode
));
1815 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1816 ivts
->base_var
, incr
);
1819 /* Figure out where to do the replacement. */
1820 loc
= get_ivts_expr (single_set (insn
), ivts
);
1822 /* If we can make the replacement right away, we're done. */
1823 if (validate_change (insn
, loc
, expr
, 0))
1826 /* Otherwise, force EXPR into a register and try again. */
1828 var
= gen_reg_rtx (mode
);
1829 expr
= force_operand (expr
, var
);
1831 emit_move_insn (var
, expr
);
1834 emit_insn_before (seq
, insn
);
1836 if (validate_change (insn
, loc
, var
, 0))
1839 /* The last chance. Try recreating the assignment in insn
1840 completely from scratch. */
1841 set
= single_set (insn
);
1846 src
= copy_rtx (SET_SRC (set
));
1847 dest
= copy_rtx (SET_DEST (set
));
1848 src
= force_operand (src
, dest
);
1850 emit_move_insn (dest
, src
);
1854 emit_insn_before (seq
, insn
);
1859 /* Return one expansion of the accumulator recorded in struct VE. */
1862 get_expansion (struct var_to_expand
*ve
)
1866 if (ve
->reuse_expansion
== 0)
1869 reg
= VARRAY_RTX (ve
->var_expansions
, ve
->reuse_expansion
- 1);
1871 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
1872 ve
->reuse_expansion
= 0;
1874 ve
->reuse_expansion
++;
1880 /* Given INSN replace the uses of the accumulator recorded in VE
1881 with a new register. */
1884 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
1887 bool really_new_expansion
= false;
1889 set
= single_set (insn
);
1893 /* Generate a new register only if the expansion limit has not been
1894 reached. Else reuse an already existing expansion. */
1895 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
1897 really_new_expansion
= true;
1898 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1901 new_reg
= get_expansion (ve
);
1903 validate_change (insn
, &SET_DEST (set
), new_reg
, 1);
1904 validate_change (insn
, &XEXP (SET_SRC (set
), 0), new_reg
, 1);
1906 if (apply_change_group ())
1907 if (really_new_expansion
)
1909 VARRAY_PUSH_RTX (ve
->var_expansions
, new_reg
);
1910 ve
->expansion_count
++;
1914 /* Initialize the variable expansions in loop preheader.
1915 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1916 basic block where the initialization of the expansions
1917 should take place. */
1920 insert_var_expansion_initialization (void **slot
, void *place_p
)
1922 struct var_to_expand
*ve
= *slot
;
1923 basic_block place
= (basic_block
)place_p
;
1924 rtx seq
, var
, zero_init
, insn
;
1927 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == 0)
1931 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1932 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1934 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1935 zero_init
= CONST0_RTX (GET_MODE (var
));
1936 emit_move_insn (var
, zero_init
);
1938 else if (ve
->op
== MULT
)
1939 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1941 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1942 zero_init
= CONST1_RTX (GET_MODE (var
));
1943 emit_move_insn (var
, zero_init
);
1949 insn
= BB_HEAD (place
);
1950 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
1951 insn
= NEXT_INSN (insn
);
1953 emit_insn_after (seq
, insn
);
1954 /* Continue traversing the hash table. */
1958 /* Combine the variable expansions at the loop exit.
1959 Callbacks for htab_traverse. PLACE_P is the loop exit
1960 basic block where the summation of the expansions should
1964 combine_var_copies_in_loop_exit (void **slot
, void *place_p
)
1966 struct var_to_expand
*ve
= *slot
;
1967 basic_block place
= (basic_block
)place_p
;
1969 rtx expr
, seq
, var
, insn
;
1972 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == 0)
1976 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1977 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1979 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1980 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
),
1983 else if (ve
->op
== MULT
)
1984 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1986 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1987 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
),
1991 expr
= force_operand (sum
, ve
->reg
);
1992 if (expr
!= ve
->reg
)
1993 emit_move_insn (ve
->reg
, expr
);
1997 insn
= BB_HEAD (place
);
1998 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
1999 insn
= NEXT_INSN (insn
);
2001 emit_insn_after (seq
, insn
);
2003 /* Continue traversing the hash table. */
2007 /* Apply loop optimizations in loop copies using the
2008 data which gathered during the unrolling. Structure
2009 OPT_INFO record that data.
2011 UNROLLING is true if we unrolled (not peeled) the loop.
2012 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2013 the loop (as it should happen in complete unrolling, but not in ordinary
2014 peeling of the loop). */
2017 apply_opt_in_copies (struct opt_info
*opt_info
,
2018 unsigned n_copies
, bool unrolling
,
2019 bool rewrite_original_loop
)
2022 basic_block bb
, orig_bb
;
2023 rtx insn
, orig_insn
, next
;
2024 struct iv_to_split ivts_templ
, *ivts
;
2025 struct var_to_expand ve_templ
, *ves
;
2027 /* Sanity check -- we need to put initialization in the original loop
2029 gcc_assert (!unrolling
|| rewrite_original_loop
);
2031 /* Allocate the basic variables (i0). */
2032 if (opt_info
->insns_to_split
)
2033 htab_traverse (opt_info
->insns_to_split
, allocate_basic_variable
, NULL
);
2035 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2037 bb
= BASIC_BLOCK (i
);
2038 orig_bb
= bb
->rbi
->original
;
2040 delta
= determine_split_iv_delta (bb
->rbi
->copy_number
, n_copies
,
2042 orig_insn
= BB_HEAD (orig_bb
);
2043 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2045 next
= NEXT_INSN (insn
);
2049 while (!INSN_P (orig_insn
))
2050 orig_insn
= NEXT_INSN (orig_insn
);
2052 ivts_templ
.insn
= orig_insn
;
2053 ve_templ
.insn
= orig_insn
;
2055 /* Apply splitting iv optimization. */
2056 if (opt_info
->insns_to_split
)
2058 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2062 #ifdef ENABLE_CHECKING
2063 gcc_assert (rtx_equal_p (PATTERN (insn
), PATTERN (orig_insn
)));
2067 insert_base_initialization (ivts
, insn
);
2068 split_iv (ivts
, insn
, delta
);
2071 /* Apply variable expansion optimization. */
2072 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2074 ves
= htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2077 #ifdef ENABLE_CHECKING
2078 gcc_assert (rtx_equal_p (PATTERN (insn
), PATTERN (orig_insn
)));
2080 expand_var_during_unrolling (ves
, insn
);
2083 orig_insn
= NEXT_INSN (orig_insn
);
2087 if (!rewrite_original_loop
)
2090 /* Initialize the variable expansions in the loop preheader
2091 and take care of combining them at the loop exit. */
2092 if (opt_info
->insns_with_var_to_expand
)
2094 htab_traverse (opt_info
->insns_with_var_to_expand
,
2095 insert_var_expansion_initialization
,
2096 opt_info
->loop_preheader
);
2097 htab_traverse (opt_info
->insns_with_var_to_expand
,
2098 combine_var_copies_in_loop_exit
,
2099 opt_info
->loop_exit
);
2102 /* Rewrite also the original loop body. Find them as originals of the blocks
2103 in the last copied iteration, i.e. those that have
2104 bb->rbi->original->copy == bb. */
2105 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2107 bb
= BASIC_BLOCK (i
);
2108 orig_bb
= bb
->rbi
->original
;
2109 if (orig_bb
->rbi
->copy
!= bb
)
2112 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2113 for (orig_insn
= BB_HEAD (orig_bb
);
2114 orig_insn
!= NEXT_INSN (BB_END (bb
));
2117 next
= NEXT_INSN (orig_insn
);
2119 if (!INSN_P (orig_insn
))
2122 ivts_templ
.insn
= orig_insn
;
2123 if (opt_info
->insns_to_split
)
2125 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2129 insert_base_initialization (ivts
, orig_insn
);
2130 split_iv (ivts
, orig_insn
, delta
);
2139 /* Release the data structures used for the variable expansion
2140 optimization. Callbacks for htab_traverse. */
2143 release_var_copies (void **slot
, void *data ATTRIBUTE_UNUSED
)
2145 struct var_to_expand
*ve
= *slot
;
2147 VARRAY_CLEAR (ve
->var_expansions
);
2149 /* Continue traversing the hash table. */
2153 /* Release OPT_INFO. */
2156 free_opt_info (struct opt_info
*opt_info
)
2158 if (opt_info
->insns_to_split
)
2159 htab_delete (opt_info
->insns_to_split
);
2160 if (opt_info
->insns_with_var_to_expand
)
2162 htab_traverse (opt_info
->insns_with_var_to_expand
,
2163 release_var_copies
, NULL
);
2164 htab_delete (opt_info
->insns_with_var_to_expand
);