Branch data Line data Source code
1 : : /* Loop unrolling.
2 : : Copyright (C) 2002-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it under
7 : : the terms of the GNU General Public License as published by the Free
8 : : Software Foundation; either version 3, or (at your option) any later
9 : : version.
10 : :
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
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : #include "config.h"
21 : : #include "system.h"
22 : : #include "coretypes.h"
23 : : #include "backend.h"
24 : : #include "target.h"
25 : : #include "rtl.h"
26 : : #include "tree.h"
27 : : #include "cfghooks.h"
28 : : #include "memmodel.h"
29 : : #include "optabs.h"
30 : : #include "emit-rtl.h"
31 : : #include "recog.h"
32 : : #include "profile.h"
33 : : #include "cfgrtl.h"
34 : : #include "cfgloop.h"
35 : : #include "dojump.h"
36 : : #include "expr.h"
37 : : #include "dumpfile.h"
38 : :
39 : : /* This pass performs loop unrolling. We only perform this
40 : : optimization on innermost loops (with single exception) because
41 : : the impact on performance is greatest here, and we want to avoid
42 : : unnecessary code size growth. The gain is caused by greater sequentiality
43 : : of code, better code to optimize for further passes and in some cases
44 : : by fewer testings of exit conditions. The main problem is code growth,
45 : : that impacts performance negatively due to effect of caches.
46 : :
47 : : What we do:
48 : :
49 : : -- unrolling of loops that roll constant times; this is almost always
50 : : win, as we get rid of exit condition tests.
51 : : -- unrolling of loops that roll number of times that we can compute
52 : : in runtime; we also get rid of exit condition tests here, but there
53 : : is the extra expense for calculating the number of iterations
54 : : -- simple unrolling of remaining loops; this is performed only if we
55 : : are asked to, as the gain is questionable in this case and often
56 : : it may even slow down the code
57 : : For more detailed descriptions of each of those, see comments at
58 : : appropriate function below.
59 : :
60 : : There is a lot of parameters (defined and described in params.def) that
61 : : control how much we unroll.
62 : :
63 : : ??? A great problem is that we don't have a good way how to determine
64 : : how many times we should unroll the loop; the experiments I have made
65 : : showed that this choice may affect performance in order of several %.
66 : : */
67 : :
68 : : /* Information about induction variables to split. */
69 : :
70 : : struct iv_to_split
71 : : {
72 : : rtx_insn *insn; /* The insn in that the induction variable occurs. */
73 : : rtx orig_var; /* The variable (register) for the IV before split. */
74 : : rtx base_var; /* The variable on that the values in the further
75 : : iterations are based. */
76 : : rtx step; /* Step of the induction variable. */
77 : : struct iv_to_split *next; /* Next entry in walking order. */
78 : : };
79 : :
80 : : /* Information about accumulators to expand. */
81 : :
82 : : struct var_to_expand
83 : : {
84 : : rtx_insn *insn; /* The insn in that the variable expansion occurs. */
85 : : rtx reg; /* The accumulator which is expanded. */
86 : : vec<rtx> var_expansions; /* The copies of the accumulator which is expanded. */
87 : : struct var_to_expand *next; /* Next entry in walking order. */
88 : : enum rtx_code op; /* The type of the accumulation - addition, subtraction
89 : : or multiplication. */
90 : : int expansion_count; /* Count the number of expansions generated so far. */
91 : : int reuse_expansion; /* The expansion we intend to reuse to expand
92 : : the accumulator. If REUSE_EXPANSION is 0 reuse
93 : : the original accumulator. Else use
94 : : var_expansions[REUSE_EXPANSION - 1]. */
95 : : };
96 : :
97 : : /* Hashtable helper for iv_to_split. */
98 : :
99 : : struct iv_split_hasher : free_ptr_hash <iv_to_split>
100 : : {
101 : : static inline hashval_t hash (const iv_to_split *);
102 : : static inline bool equal (const iv_to_split *, const iv_to_split *);
103 : : };
104 : :
105 : :
106 : : /* A hash function for information about insns to split. */
107 : :
108 : : inline hashval_t
109 : 217754285 : iv_split_hasher::hash (const iv_to_split *ivts)
110 : : {
111 : 217754285 : return (hashval_t) INSN_UID (ivts->insn);
112 : : }
113 : :
114 : : /* An equality functions for information about insns to split. */
115 : :
116 : : inline bool
117 : 102287076 : iv_split_hasher::equal (const iv_to_split *i1, const iv_to_split *i2)
118 : : {
119 : 102287076 : return i1->insn == i2->insn;
120 : : }
121 : :
122 : : /* Hashtable helper for iv_to_split. */
123 : :
124 : : struct var_expand_hasher : free_ptr_hash <var_to_expand>
125 : : {
126 : : static inline hashval_t hash (const var_to_expand *);
127 : : static inline bool equal (const var_to_expand *, const var_to_expand *);
128 : : };
129 : :
130 : : /* Return a hash for VES. */
131 : :
132 : : inline hashval_t
133 : 360 : var_expand_hasher::hash (const var_to_expand *ves)
134 : : {
135 : 360 : return (hashval_t) INSN_UID (ves->insn);
136 : : }
137 : :
138 : : /* Return true if I1 and I2 refer to the same instruction. */
139 : :
140 : : inline bool
141 : 84 : var_expand_hasher::equal (const var_to_expand *i1, const var_to_expand *i2)
142 : : {
143 : 84 : return i1->insn == i2->insn;
144 : : }
145 : :
146 : : /* Information about optimization applied in
147 : : the unrolled loop. */
148 : :
149 : : struct opt_info
150 : : {
151 : : hash_table<iv_split_hasher> *insns_to_split; /* A hashtable of insns to
152 : : split. */
153 : : struct iv_to_split *iv_to_split_head; /* The first iv to split. */
154 : : struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list. */
155 : : hash_table<var_expand_hasher> *insns_with_var_to_expand; /* A hashtable of
156 : : insns with accumulators to expand. */
157 : : struct var_to_expand *var_to_expand_head; /* The first var to expand. */
158 : : struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list. */
159 : : unsigned first_new_block; /* The first basic block that was
160 : : duplicated. */
161 : : basic_block loop_exit; /* The loop exit basic block. */
162 : : basic_block loop_preheader; /* The loop preheader basic block. */
163 : : };
164 : :
165 : : static void decide_unroll_stupid (class loop *, int);
166 : : static void decide_unroll_constant_iterations (class loop *, int);
167 : : static void decide_unroll_runtime_iterations (class loop *, int);
168 : : static void unroll_loop_stupid (class loop *);
169 : : static void decide_unrolling (int);
170 : : static void unroll_loop_constant_iterations (class loop *);
171 : : static void unroll_loop_runtime_iterations (class loop *);
172 : : static struct opt_info *analyze_insns_in_loop (class loop *);
173 : : static void opt_info_start_duplication (struct opt_info *);
174 : : static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
175 : : static void free_opt_info (struct opt_info *);
176 : : static struct var_to_expand *analyze_insn_to_expand_var (class loop*, rtx_insn *);
177 : : static bool referenced_in_one_insn_in_loop_p (class loop *, rtx, int *);
178 : : static struct iv_to_split *analyze_iv_to_split_insn (rtx_insn *);
179 : : static void expand_var_during_unrolling (struct var_to_expand *, rtx_insn *);
180 : : static void insert_var_expansion_initialization (struct var_to_expand *,
181 : : basic_block);
182 : : static void combine_var_copies_in_loop_exit (struct var_to_expand *,
183 : : basic_block);
184 : : static rtx get_expansion (struct var_to_expand *);
185 : :
186 : : /* Emit a message summarizing the unroll that will be
187 : : performed for LOOP, along with the loop's location LOCUS, if
188 : : appropriate given the dump or -fopt-info settings. */
189 : :
190 : : static void
191 : 376190 : report_unroll (class loop *loop, dump_location_t locus)
192 : : {
193 : 376190 : dump_flags_t report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS;
194 : :
195 : 376190 : if (loop->lpt_decision.decision == LPT_NONE)
196 : 376116 : return;
197 : :
198 : 48010 : if (!dump_enabled_p ())
199 : : return;
200 : :
201 : 74 : dump_metadata_t metadata (report_flags, locus.get_impl_location ());
202 : 74 : dump_printf_loc (metadata, locus.get_user_location (),
203 : : "loop unrolled %d times",
204 : : loop->lpt_decision.times);
205 : 74 : if (profile_info && loop->header->count.initialized_p ())
206 : 1 : dump_printf (metadata,
207 : : " (header execution count %d)",
208 : 1 : (int)loop->header->count.to_gcov_type ());
209 : :
210 : 74 : dump_printf (metadata, "\n");
211 : : }
212 : :
213 : : /* Decide whether unroll loops and how much. */
214 : : static void
215 : 205556 : decide_unrolling (int flags)
216 : : {
217 : : /* Scan the loops, inner ones first. */
218 : 1155656 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
219 : : {
220 : 538988 : loop->lpt_decision.decision = LPT_NONE;
221 : 538988 : dump_user_location_t locus = get_loop_location (loop);
222 : :
223 : 538988 : if (dump_enabled_p ())
224 : 450 : dump_printf_loc (MSG_NOTE, locus,
225 : : "considering unrolling loop %d at BB %d\n",
226 : 450 : loop->num, loop->header->index);
227 : :
228 : 538988 : if (loop->unroll == 1)
229 : : {
230 : 35 : if (dump_file)
231 : 13 : fprintf (dump_file,
232 : : ";; Not unrolling loop, user didn't want it unrolled\n");
233 : 162798 : continue;
234 : : }
235 : :
236 : : /* Do not peel cold areas. */
237 : 538953 : if (optimize_loop_for_size_p (loop))
238 : : {
239 : 69220 : if (dump_file)
240 : 0 : fprintf (dump_file, ";; Not considering loop, cold area\n");
241 : 69220 : continue;
242 : : }
243 : :
244 : : /* Can the loop be manipulated? */
245 : 469733 : if (!can_duplicate_loop_p (loop))
246 : : {
247 : 10995 : if (dump_file)
248 : 0 : fprintf (dump_file,
249 : : ";; Not considering loop, cannot duplicate\n");
250 : 10995 : continue;
251 : : }
252 : :
253 : : /* Skip non-innermost loops. */
254 : 458738 : if (loop->inner)
255 : : {
256 : 82548 : if (dump_file)
257 : 0 : fprintf (dump_file, ";; Not considering loop, is not innermost\n");
258 : 82548 : continue;
259 : : }
260 : :
261 : 376190 : loop->ninsns = num_loop_insns (loop);
262 : 376190 : loop->av_ninsns = average_num_loop_insns (loop);
263 : :
264 : : /* Try transformations one by one in decreasing order of priority. */
265 : 376190 : decide_unroll_constant_iterations (loop, flags);
266 : 376190 : if (loop->lpt_decision.decision == LPT_NONE)
267 : 347601 : decide_unroll_runtime_iterations (loop, flags);
268 : 376190 : if (loop->lpt_decision.decision == LPT_NONE)
269 : 328284 : decide_unroll_stupid (loop, flags);
270 : :
271 : 376190 : report_unroll (loop, locus);
272 : 205556 : }
273 : 205556 : }
274 : :
275 : : /* Unroll LOOPS. */
276 : : void
277 : 205556 : unroll_loops (int flags)
278 : : {
279 : 205556 : bool changed = false;
280 : :
281 : : /* Now decide rest of unrolling. */
282 : 205556 : decide_unrolling (flags);
283 : :
284 : : /* Scan the loops, inner ones first. */
285 : 1155656 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
286 : : {
287 : : /* And perform the appropriate transformations. */
288 : 538988 : switch (loop->lpt_decision.decision)
289 : : {
290 : 28589 : case LPT_UNROLL_CONSTANT:
291 : 28589 : unroll_loop_constant_iterations (loop);
292 : 28589 : changed = true;
293 : 28589 : break;
294 : 19317 : case LPT_UNROLL_RUNTIME:
295 : 19317 : unroll_loop_runtime_iterations (loop);
296 : 19317 : changed = true;
297 : 19317 : break;
298 : 104 : case LPT_UNROLL_STUPID:
299 : 104 : unroll_loop_stupid (loop);
300 : 104 : changed = true;
301 : 104 : break;
302 : : case LPT_NONE:
303 : : break;
304 : 0 : default:
305 : 0 : gcc_unreachable ();
306 : : }
307 : 205556 : }
308 : :
309 : 205556 : if (changed)
310 : : {
311 : 17903 : calculate_dominance_info (CDI_DOMINATORS);
312 : 17903 : fix_loop_structure (NULL);
313 : : }
314 : :
315 : 205556 : iv_analysis_done ();
316 : 205556 : }
317 : :
318 : : /* Check whether exit of the LOOP is at the end of loop body. */
319 : :
320 : : static bool
321 : 226683 : loop_exit_at_end_p (class loop *loop)
322 : : {
323 : 226683 : class niter_desc *desc = get_simple_loop_desc (loop);
324 : 226683 : rtx_insn *insn;
325 : :
326 : : /* We should never have conditional in latch block. */
327 : 226683 : gcc_assert (desc->in_edge->dest != loop->header);
328 : :
329 : 226683 : if (desc->in_edge->dest != loop->latch)
330 : : return false;
331 : :
332 : : /* Check that the latch is empty. */
333 : 674542 : FOR_BB_INSNS (loop->latch, insn)
334 : : {
335 : 449380 : if (INSN_P (insn) && active_insn_p (insn))
336 : : return false;
337 : : }
338 : :
339 : : return true;
340 : : }
341 : :
342 : : /* Decide whether to unroll LOOP iterating constant number of times
343 : : and how much. */
344 : :
345 : : static void
346 : 376190 : decide_unroll_constant_iterations (class loop *loop, int flags)
347 : : {
348 : 376190 : unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
349 : 376190 : class niter_desc *desc;
350 : 376190 : widest_int iterations;
351 : :
352 : : /* If we were not asked to unroll this loop, just return back silently. */
353 : 376190 : if (!(flags & UAP_UNROLL) && !loop->unroll)
354 : : return;
355 : :
356 : 376113 : if (dump_enabled_p ())
357 : 399 : dump_printf (MSG_NOTE,
358 : : "considering unrolling loop with constant "
359 : : "number of iterations\n");
360 : :
361 : : /* nunroll = total number of copies of the original loop body in
362 : : unrolled loop (i.e. if it is 2, we have to duplicate loop body once). */
363 : 376113 : nunroll = param_max_unrolled_insns / loop->ninsns;
364 : 376113 : nunroll_by_av
365 : 376113 : = param_max_average_unrolled_insns / loop->av_ninsns;
366 : 376113 : if (nunroll > nunroll_by_av)
367 : : nunroll = nunroll_by_av;
368 : 376113 : if (nunroll > (unsigned) param_max_unroll_times)
369 : : nunroll = param_max_unroll_times;
370 : :
371 : 376113 : if (targetm.loop_unroll_adjust)
372 : 376113 : nunroll = targetm.loop_unroll_adjust (nunroll, loop);
373 : :
374 : : /* Skip big loops. */
375 : 376113 : if (nunroll <= 1
376 : 308694 : && !(loop->unroll > 1 && loop->unroll < USHRT_MAX))
377 : : {
378 : 308694 : if (dump_file)
379 : 8 : fprintf (dump_file, ";; Not considering loop, is too big\n");
380 : 308694 : return;
381 : : }
382 : :
383 : : /* Check for simple loops. */
384 : 67419 : desc = get_simple_loop_desc (loop);
385 : :
386 : : /* Check number of iterations. */
387 : 67419 : if (!desc->simple_p || !desc->const_iter || desc->assumptions)
388 : : {
389 : 36954 : if (dump_file)
390 : 39 : fprintf (dump_file,
391 : : ";; Unable to prove that the loop iterates constant times\n");
392 : 36954 : return;
393 : : }
394 : :
395 : : /* Check for an explicit unrolling factor. */
396 : 30465 : if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
397 : : {
398 : : /* However we cannot unroll completely at the RTL level a loop with
399 : : constant number of iterations; it should have been peeled instead. */
400 : 288 : if (desc->niter == 0 || (unsigned) loop->unroll > desc->niter - 1)
401 : : {
402 : 17 : if (dump_file)
403 : 9 : fprintf (dump_file, ";; Loop should have been peeled\n");
404 : : }
405 : : else
406 : : {
407 : 271 : loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
408 : 271 : loop->lpt_decision.times = loop->unroll - 1;
409 : : }
410 : 288 : return;
411 : : }
412 : :
413 : : /* Check whether the loop rolls enough to consider.
414 : : Consult also loop bounds and profile; in the case the loop has more
415 : : than one exit it may well loop less than determined maximal number
416 : : of iterations. */
417 : 30177 : if (desc->niter < 2 * nunroll
418 : 30177 : || ((get_estimated_loop_iterations (loop, &iterations)
419 : 547 : || get_likely_max_loop_iterations (loop, &iterations))
420 : 28320 : && wi::ltu_p (iterations, 2 * nunroll)))
421 : : {
422 : 1859 : if (dump_file)
423 : 1 : fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
424 : 1859 : return;
425 : : }
426 : :
427 : : /* Success; now compute number of iterations to unroll. We alter
428 : : nunroll so that as few as possible copies of loop body are
429 : : necessary, while still not decreasing the number of unrollings
430 : : too much (at most by 1). */
431 : 28318 : best_copies = 2 * nunroll + 10;
432 : :
433 : 28318 : i = 2 * nunroll + 2;
434 : 28318 : if (i > desc->niter - 2)
435 : 473 : i = desc->niter - 2;
436 : :
437 : 207095 : for (; i >= nunroll - 1; i--)
438 : : {
439 : 178777 : unsigned exit_mod = desc->niter % (i + 1);
440 : :
441 : 178777 : if (!loop_exit_at_end_p (loop))
442 : 762 : n_copies = exit_mod + i + 1;
443 : 178015 : else if (exit_mod != (unsigned) i
444 : 70439 : || desc->noloop_assumptions != NULL_RTX)
445 : 107576 : n_copies = exit_mod + i + 2;
446 : : else
447 : : n_copies = i + 1;
448 : :
449 : 178777 : if (n_copies < best_copies)
450 : : {
451 : 135699 : best_copies = n_copies;
452 : 135699 : best_unroll = i;
453 : : }
454 : : }
455 : :
456 : 28318 : loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
457 : 28318 : loop->lpt_decision.times = best_unroll;
458 : 376190 : }
459 : :
460 : : /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
461 : : The transformation does this:
462 : :
463 : : for (i = 0; i < 102; i++)
464 : : body;
465 : :
466 : : ==> (LOOP->LPT_DECISION.TIMES == 3)
467 : :
468 : : i = 0;
469 : : body; i++;
470 : : body; i++;
471 : : while (i < 102)
472 : : {
473 : : body; i++;
474 : : body; i++;
475 : : body; i++;
476 : : body; i++;
477 : : }
478 : : */
479 : : static void
480 : 28589 : unroll_loop_constant_iterations (class loop *loop)
481 : : {
482 : 28589 : unsigned HOST_WIDE_INT niter;
483 : 28589 : unsigned exit_mod;
484 : 28589 : unsigned i;
485 : 28589 : edge e;
486 : 28589 : unsigned max_unroll = loop->lpt_decision.times;
487 : 28589 : class niter_desc *desc = get_simple_loop_desc (loop);
488 : 28589 : bool exit_at_end = loop_exit_at_end_p (loop);
489 : 28589 : struct opt_info *opt_info = NULL;
490 : 28589 : bool ok;
491 : 28589 : bool flat = maybe_flat_loop_profile (loop);
492 : 28589 : profile_count orig_exit_count = desc->out_edge->count ();
493 : :
494 : 28589 : niter = desc->niter;
495 : :
496 : : /* Should not get here (such loop should be peeled instead). */
497 : 28589 : gcc_assert (niter > max_unroll + 1);
498 : :
499 : 28589 : exit_mod = niter % (max_unroll + 1);
500 : :
501 : 28589 : auto_sbitmap wont_exit (max_unroll + 2);
502 : 28589 : bitmap_ones (wont_exit);
503 : :
504 : 28589 : auto_vec<edge> remove_edges;
505 : 28589 : if (flag_split_ivs_in_unroller
506 : 0 : || flag_variable_expansion_in_unroller)
507 : 28589 : opt_info = analyze_insns_in_loop (loop);
508 : :
509 : 28589 : if (!exit_at_end)
510 : : {
511 : : /* The exit is not at the end of the loop; leave exit test
512 : : in the first copy, so that the loops that start with test
513 : : of exit condition have continuous body after unrolling. */
514 : :
515 : 84 : if (dump_file)
516 : 0 : fprintf (dump_file, ";; Condition at beginning of loop.\n");
517 : :
518 : : /* Peel exit_mod iterations. */
519 : 84 : bitmap_clear_bit (wont_exit, 0);
520 : 84 : if (desc->noloop_assumptions)
521 : 0 : bitmap_clear_bit (wont_exit, 1);
522 : :
523 : 84 : if (exit_mod)
524 : : {
525 : 90 : opt_info_start_duplication (opt_info);
526 : 30 : ok = duplicate_loop_body_to_header_edge (
527 : : loop, loop_preheader_edge (loop), exit_mod, wont_exit,
528 : : desc->out_edge, &remove_edges,
529 : : DLTHE_FLAG_UPDATE_FREQ
530 : 30 : | (opt_info && exit_mod > 1 ? DLTHE_RECORD_COPY_NUMBER : 0));
531 : 30 : gcc_assert (ok);
532 : :
533 : 30 : if (opt_info && exit_mod > 1)
534 : 16 : apply_opt_in_copies (opt_info, exit_mod, false, false);
535 : :
536 : 30 : desc->noloop_assumptions = NULL_RTX;
537 : 30 : desc->niter -= exit_mod;
538 : 30 : loop->nb_iterations_upper_bound -= exit_mod;
539 : 30 : if (loop->any_estimate
540 : 30 : && wi::leu_p (exit_mod, loop->nb_iterations_estimate))
541 : 18 : loop->nb_iterations_estimate -= exit_mod;
542 : : else
543 : 12 : loop->any_estimate = false;
544 : 30 : if (loop->any_likely_upper_bound
545 : 30 : && wi::leu_p (exit_mod, loop->nb_iterations_likely_upper_bound))
546 : 30 : loop->nb_iterations_likely_upper_bound -= exit_mod;
547 : : else
548 : 0 : loop->any_likely_upper_bound = false;
549 : : }
550 : :
551 : 84 : bitmap_set_bit (wont_exit, 1);
552 : : }
553 : : else
554 : : {
555 : : /* Leave exit test in last copy, for the same reason as above if
556 : : the loop tests the condition at the end of loop body. */
557 : :
558 : 28505 : if (dump_file)
559 : 33 : fprintf (dump_file, ";; Condition at end of loop.\n");
560 : :
561 : : /* We know that niter >= max_unroll + 2; so we do not need to care of
562 : : case when we would exit before reaching the loop. So just peel
563 : : exit_mod + 1 iterations. */
564 : 28505 : if (exit_mod != max_unroll
565 : 26955 : || desc->noloop_assumptions)
566 : : {
567 : 1550 : bitmap_clear_bit (wont_exit, 0);
568 : 1550 : if (desc->noloop_assumptions)
569 : 0 : bitmap_clear_bit (wont_exit, 1);
570 : :
571 : 4650 : opt_info_start_duplication (opt_info);
572 : 1550 : ok = duplicate_loop_body_to_header_edge (
573 : : loop, loop_preheader_edge (loop), exit_mod + 1, wont_exit,
574 : : desc->out_edge, &remove_edges,
575 : : DLTHE_FLAG_UPDATE_FREQ
576 : 1550 : | (opt_info && exit_mod > 0 ? DLTHE_RECORD_COPY_NUMBER : 0));
577 : 1550 : gcc_assert (ok);
578 : :
579 : 1550 : if (opt_info && exit_mod > 0)
580 : 461 : apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
581 : :
582 : 1550 : desc->niter -= exit_mod + 1;
583 : 1550 : loop->nb_iterations_upper_bound -= exit_mod + 1;
584 : 1550 : if (loop->any_estimate
585 : 1550 : && wi::leu_p (exit_mod + 1, loop->nb_iterations_estimate))
586 : 1066 : loop->nb_iterations_estimate -= exit_mod + 1;
587 : : else
588 : 484 : loop->any_estimate = false;
589 : 1550 : if (loop->any_likely_upper_bound
590 : 1550 : && wi::leu_p (exit_mod + 1, loop->nb_iterations_likely_upper_bound))
591 : 1550 : loop->nb_iterations_likely_upper_bound -= exit_mod + 1;
592 : : else
593 : 0 : loop->any_likely_upper_bound = false;
594 : 1550 : desc->noloop_assumptions = NULL_RTX;
595 : :
596 : 1550 : bitmap_set_bit (wont_exit, 0);
597 : 1550 : bitmap_set_bit (wont_exit, 1);
598 : : }
599 : :
600 : 28505 : bitmap_clear_bit (wont_exit, max_unroll);
601 : : }
602 : :
603 : : /* Now unroll the loop. */
604 : :
605 : 85767 : opt_info_start_duplication (opt_info);
606 : 28589 : ok = duplicate_loop_body_to_header_edge (
607 : : loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
608 : : &remove_edges,
609 : : DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0)
610 : 28589 : | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
611 : 28589 : gcc_assert (ok);
612 : :
613 : 28589 : edge exit = update_loop_exit_probability_scale_dom_bbs
614 : 28589 : (loop, desc->out_edge, orig_exit_count);
615 : 28589 : if (exit)
616 : 28583 : update_br_prob_note (exit->src);
617 : :
618 : 28589 : if (opt_info)
619 : : {
620 : 28589 : apply_opt_in_copies (opt_info, max_unroll, true, true);
621 : 28589 : free_opt_info (opt_info);
622 : : }
623 : :
624 : 28589 : if (exit_at_end)
625 : : {
626 : 28505 : basic_block exit_block = get_bb_copy (desc->in_edge->src);
627 : : /* Find a new in and out edge; they are in the last copy we have made. */
628 : :
629 : 28505 : if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
630 : : {
631 : 1388 : desc->out_edge = EDGE_SUCC (exit_block, 0);
632 : 1388 : desc->in_edge = EDGE_SUCC (exit_block, 1);
633 : : }
634 : : else
635 : : {
636 : 27117 : desc->out_edge = EDGE_SUCC (exit_block, 1);
637 : 27117 : desc->in_edge = EDGE_SUCC (exit_block, 0);
638 : : }
639 : : }
640 : :
641 : 28589 : desc->niter /= max_unroll + 1;
642 : 28589 : loop->nb_iterations_upper_bound
643 : 28589 : = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
644 : 28589 : if (loop->any_estimate)
645 : 27823 : loop->nb_iterations_estimate
646 : 27823 : = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
647 : 28589 : if (loop->any_likely_upper_bound)
648 : 28589 : loop->nb_iterations_likely_upper_bound
649 : 28589 : = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
650 : 28589 : desc->niter_expr = gen_int_mode (desc->niter, desc->mode);
651 : :
652 : : /* Remove the edges. */
653 : 71920 : FOR_EACH_VEC_ELT (remove_edges, i, e)
654 : 43331 : remove_path (e);
655 : :
656 : 28589 : if (dump_file)
657 : 33 : fprintf (dump_file,
658 : : ";; Unrolled loop %d times, constant # of iterations %i insns\n",
659 : : max_unroll, num_loop_insns (loop));
660 : 28589 : }
661 : :
662 : : /* Decide whether to unroll LOOP iterating runtime computable number of times
663 : : and how much. */
664 : : static void
665 : 347601 : decide_unroll_runtime_iterations (class loop *loop, int flags)
666 : : {
667 : 347601 : unsigned nunroll, nunroll_by_av, i;
668 : 347601 : class niter_desc *desc;
669 : 347601 : widest_int iterations;
670 : :
671 : : /* If we were not asked to unroll this loop, just return back silently. */
672 : 347601 : if (!(flags & UAP_UNROLL) && !loop->unroll)
673 : : return;
674 : :
675 : 347524 : if (dump_enabled_p ())
676 : 366 : dump_printf (MSG_NOTE,
677 : : "considering unrolling loop with runtime-"
678 : : "computable number of iterations\n");
679 : :
680 : : /* nunroll = total number of copies of the original loop body in
681 : : unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
682 : 347524 : nunroll = param_max_unrolled_insns / loop->ninsns;
683 : 347524 : nunroll_by_av = param_max_average_unrolled_insns / loop->av_ninsns;
684 : 347524 : if (nunroll > nunroll_by_av)
685 : : nunroll = nunroll_by_av;
686 : 347524 : if (nunroll > (unsigned) param_max_unroll_times)
687 : : nunroll = param_max_unroll_times;
688 : :
689 : 347524 : if (targetm.loop_unroll_adjust)
690 : 347524 : nunroll = targetm.loop_unroll_adjust (nunroll, loop);
691 : :
692 : 347524 : if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
693 : 698 : nunroll = loop->unroll;
694 : :
695 : : /* Skip big loops. */
696 : 347524 : if (nunroll <= 1)
697 : : {
698 : 308694 : if (dump_file)
699 : 8 : fprintf (dump_file, ";; Not considering loop, is too big\n");
700 : 308694 : return;
701 : : }
702 : :
703 : : /* Check for simple loops. */
704 : 38830 : desc = get_simple_loop_desc (loop);
705 : :
706 : : /* Check simpleness. */
707 : 38830 : if (!desc->simple_p || desc->assumptions)
708 : : {
709 : 16464 : if (dump_file)
710 : 24 : fprintf (dump_file,
711 : : ";; Unable to prove that the number of iterations "
712 : : "can be counted in runtime\n");
713 : 16464 : return;
714 : : }
715 : :
716 : 22366 : if (desc->const_iter)
717 : : {
718 : 1876 : if (dump_file)
719 : 10 : fprintf (dump_file, ";; Loop iterates constant times\n");
720 : 1876 : return;
721 : : }
722 : :
723 : : /* Check whether the loop rolls. */
724 : 20490 : if ((get_estimated_loop_iterations (loop, &iterations)
725 : 19296 : || get_likely_max_loop_iterations (loop, &iterations))
726 : 39786 : && wi::ltu_p (iterations, 2 * nunroll))
727 : : {
728 : 1173 : if (dump_file)
729 : 1 : fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
730 : 1173 : return;
731 : : }
732 : :
733 : : /* Success; now force nunroll to be power of 2, as code-gen
734 : : requires it, we are unable to cope with overflows in
735 : : computation of number of iterations. */
736 : 53180 : for (i = 1; 2 * i <= nunroll; i *= 2)
737 : 33863 : continue;
738 : :
739 : 19317 : loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
740 : 19317 : loop->lpt_decision.times = i - 1;
741 : 347601 : }
742 : :
743 : : /* Splits edge E and inserts the sequence of instructions INSNS on it, and
744 : : returns the newly created block. If INSNS is NULL_RTX, nothing is changed
745 : : and NULL is returned instead. */
746 : :
747 : : basic_block
748 : 76896 : split_edge_and_insert (edge e, rtx_insn *insns)
749 : : {
750 : 76896 : basic_block bb;
751 : :
752 : 76896 : if (!insns)
753 : : return NULL;
754 : 76896 : bb = split_edge (e);
755 : 76896 : emit_insn_after (insns, BB_END (bb));
756 : :
757 : : /* ??? We used to assume that INSNS can contain control flow insns, and
758 : : that we had to try to find sub basic blocks in BB to maintain a valid
759 : : CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
760 : : and call break_superblocks when going out of cfglayout mode. But it
761 : : turns out that this never happens; and that if it does ever happen,
762 : : the verify_flow_info at the end of the RTL loop passes would fail.
763 : :
764 : : There are two reasons why we expected we could have control flow insns
765 : : in INSNS. The first is when a comparison has to be done in parts, and
766 : : the second is when the number of iterations is computed for loops with
767 : : the number of iterations known at runtime. In both cases, test cases
768 : : to get control flow in INSNS appear to be impossible to construct:
769 : :
770 : : * If do_compare_rtx_and_jump needs several branches to do comparison
771 : : in a mode that needs comparison by parts, we cannot analyze the
772 : : number of iterations of the loop, and we never get to unrolling it.
773 : :
774 : : * The code in expand_divmod that was suspected to cause creation of
775 : : branching code seems to be only accessed for signed division. The
776 : : divisions used by # of iterations analysis are always unsigned.
777 : : Problems might arise on architectures that emits branching code
778 : : for some operations that may appear in the unroller (especially
779 : : for division), but we have no such architectures.
780 : :
781 : : Considering all this, it was decided that we should for now assume
782 : : that INSNS can in theory contain control flow insns, but in practice
783 : : it never does. So we don't handle the theoretical case, and should
784 : : a real failure ever show up, we have a pretty good clue for how to
785 : : fix it. */
786 : :
787 : 76896 : return bb;
788 : : }
789 : :
790 : : /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
791 : : true, with probability PROB. If CINSN is not NULL, it is the insn to copy
792 : : in order to create a jump. */
793 : :
794 : : static rtx_insn *
795 : 57579 : compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp,
796 : : rtx_code_label *label, profile_probability prob,
797 : : rtx_insn *cinsn)
798 : : {
799 : 57579 : rtx_insn *seq;
800 : 57579 : rtx_jump_insn *jump;
801 : 57579 : rtx cond;
802 : 57579 : machine_mode mode;
803 : :
804 : 57579 : mode = GET_MODE (op0);
805 : 57579 : if (mode == VOIDmode)
806 : 0 : mode = GET_MODE (op1);
807 : :
808 : 57579 : start_sequence ();
809 : 57579 : if (GET_MODE_CLASS (mode) == MODE_CC)
810 : : {
811 : : /* A hack -- there seems to be no easy generic way how to make a
812 : : conditional jump from a ccmode comparison. */
813 : 0 : gcc_assert (cinsn);
814 : 0 : cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
815 : 0 : gcc_assert (GET_CODE (cond) == comp);
816 : 0 : gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
817 : 0 : gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
818 : 0 : emit_jump_insn (copy_insn (PATTERN (cinsn)));
819 : 0 : jump = as_a <rtx_jump_insn *> (get_last_insn ());
820 : 0 : JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
821 : 0 : LABEL_NUSES (JUMP_LABEL (jump))++;
822 : 0 : redirect_jump (jump, label, 0);
823 : : }
824 : : else
825 : : {
826 : 57579 : gcc_assert (!cinsn);
827 : :
828 : 57579 : op0 = force_operand (op0, NULL_RTX);
829 : 57579 : op1 = force_operand (op1, NULL_RTX);
830 : 57579 : do_compare_rtx_and_jump (op0, op1, comp, 0,
831 : : mode, NULL_RTX, NULL, label,
832 : : profile_probability::uninitialized ());
833 : 57579 : jump = as_a <rtx_jump_insn *> (get_last_insn ());
834 : 57579 : jump->set_jump_target (label);
835 : 57579 : LABEL_NUSES (label)++;
836 : : }
837 : 57579 : if (prob.initialized_p ())
838 : 57579 : add_reg_br_prob_note (jump, prob);
839 : :
840 : 57579 : seq = get_insns ();
841 : 57579 : end_sequence ();
842 : :
843 : 57579 : return seq;
844 : : }
845 : :
846 : : /* Unroll LOOP for which we are able to count number of iterations in
847 : : runtime LOOP->LPT_DECISION.TIMES times. The times value must be a
848 : : power of two. The transformation does this (with some extra care
849 : : for case n < 0):
850 : :
851 : : for (i = 0; i < n; i++)
852 : : body;
853 : :
854 : : ==> (LOOP->LPT_DECISION.TIMES == 3)
855 : :
856 : : i = 0;
857 : : mod = n % 4;
858 : :
859 : : switch (mod)
860 : : {
861 : : case 3:
862 : : body; i++;
863 : : case 2:
864 : : body; i++;
865 : : case 1:
866 : : body; i++;
867 : : case 0: ;
868 : : }
869 : :
870 : : while (i < n)
871 : : {
872 : : body; i++;
873 : : body; i++;
874 : : body; i++;
875 : : body; i++;
876 : : }
877 : : */
878 : : static void
879 : 19317 : unroll_loop_runtime_iterations (class loop *loop)
880 : : {
881 : 19317 : rtx old_niter, niter, tmp;
882 : 19317 : rtx_insn *init_code, *branch_code;
883 : 19317 : unsigned i;
884 : 19317 : profile_probability p;
885 : 19317 : basic_block preheader, *body, swtch, ezc_swtch = NULL;
886 : 19317 : int may_exit_copy;
887 : 19317 : profile_count iter_count, new_count;
888 : 19317 : unsigned n_peel;
889 : 19317 : edge e;
890 : 19317 : bool extra_zero_check, last_may_exit;
891 : 19317 : unsigned max_unroll = loop->lpt_decision.times;
892 : 19317 : class niter_desc *desc = get_simple_loop_desc (loop);
893 : 19317 : bool exit_at_end = loop_exit_at_end_p (loop);
894 : 19317 : struct opt_info *opt_info = NULL;
895 : 19317 : bool ok;
896 : :
897 : 19317 : if (flag_split_ivs_in_unroller
898 : 0 : || flag_variable_expansion_in_unroller)
899 : 19317 : opt_info = analyze_insns_in_loop (loop);
900 : :
901 : : /* Remember blocks whose dominators will have to be updated. */
902 : 19317 : auto_vec<basic_block> dom_bbs;
903 : :
904 : 19317 : body = get_loop_body (loop);
905 : 64494 : for (i = 0; i < loop->num_nodes; i++)
906 : : {
907 : 142191 : for (basic_block bb : get_dominated_by (CDI_DOMINATORS, body[i]))
908 : 46808 : if (!flow_bb_inside_loop_p (loop, bb))
909 : 66125 : dom_bbs.safe_push (bb);
910 : : }
911 : 19317 : free (body);
912 : :
913 : 19317 : if (!exit_at_end)
914 : : {
915 : : /* Leave exit in first copy (for explanation why see comment in
916 : : unroll_loop_constant_iterations). */
917 : 675 : may_exit_copy = 0;
918 : 675 : n_peel = max_unroll - 1;
919 : 675 : extra_zero_check = true;
920 : 675 : last_may_exit = false;
921 : : }
922 : : else
923 : : {
924 : : /* Leave exit in last copy (for explanation why see comment in
925 : : unroll_loop_constant_iterations). */
926 : 18642 : may_exit_copy = max_unroll;
927 : 18642 : n_peel = max_unroll;
928 : 18642 : extra_zero_check = false;
929 : 18642 : last_may_exit = true;
930 : : }
931 : :
932 : : /* Get expression for number of iterations. */
933 : 19317 : start_sequence ();
934 : 19317 : old_niter = niter = gen_reg_rtx (desc->mode);
935 : 19317 : tmp = force_operand (copy_rtx (desc->niter_expr), niter);
936 : 19317 : if (tmp != niter)
937 : 443 : emit_move_insn (niter, tmp);
938 : :
939 : : /* For loops that exit at end and whose number of iterations is reliable,
940 : : add one to niter to account for first pass through loop body before
941 : : reaching exit test. */
942 : 19317 : if (exit_at_end && !desc->noloop_assumptions)
943 : : {
944 : 12887 : niter = expand_simple_binop (desc->mode, PLUS,
945 : : niter, const1_rtx,
946 : : NULL_RTX, 0, OPTAB_LIB_WIDEN);
947 : 12887 : old_niter = niter;
948 : : }
949 : :
950 : : /* Count modulo by ANDing it with max_unroll; we use the fact that
951 : : the number of unrollings is a power of two, and thus this is correct
952 : : even if there is overflow in the computation. */
953 : 19317 : niter = expand_simple_binop (desc->mode, AND,
954 : 19317 : niter, gen_int_mode (max_unroll, desc->mode),
955 : : NULL_RTX, 0, OPTAB_LIB_WIDEN);
956 : :
957 : 19317 : init_code = get_insns ();
958 : 19317 : end_sequence ();
959 : 19317 : unshare_all_rtl_in_chain (init_code);
960 : :
961 : : /* Precondition the loop. */
962 : 19317 : split_edge_and_insert (loop_preheader_edge (loop), init_code);
963 : :
964 : 19317 : auto_vec<edge> remove_edges;
965 : :
966 : 19317 : auto_sbitmap wont_exit (max_unroll + 2);
967 : :
968 : 19317 : if (extra_zero_check || desc->noloop_assumptions)
969 : : {
970 : : /* Peel the first copy of loop body. Leave the exit test if the number
971 : : of iterations is not reliable. Also record the place of the extra zero
972 : : check. */
973 : 6430 : bitmap_clear (wont_exit);
974 : 6430 : if (!desc->noloop_assumptions)
975 : 509 : bitmap_set_bit (wont_exit, 1);
976 : 6430 : ezc_swtch = loop_preheader_edge (loop)->src;
977 : 6430 : ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
978 : : 1, wont_exit, desc->out_edge,
979 : : &remove_edges,
980 : : DLTHE_FLAG_UPDATE_FREQ);
981 : 6430 : gcc_assert (ok);
982 : : }
983 : :
984 : : /* Record the place where switch will be built for preconditioning. */
985 : 19317 : swtch = split_edge (loop_preheader_edge (loop));
986 : :
987 : : /* Compute count increments for each switch block and initialize
988 : : innermost switch block. Switch blocks and peeled loop copies are built
989 : : from innermost outward. */
990 : 19317 : iter_count = new_count = swtch->count / (max_unroll + 1);
991 : 19317 : swtch->count = new_count;
992 : :
993 : 76221 : for (i = 0; i < n_peel; i++)
994 : : {
995 : : /* Peel the copy. */
996 : 56904 : bitmap_clear (wont_exit);
997 : 56904 : if (i != n_peel - 1 || !last_may_exit)
998 : 38262 : bitmap_set_bit (wont_exit, 1);
999 : 56904 : ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
1000 : : 1, wont_exit, desc->out_edge,
1001 : : &remove_edges,
1002 : : DLTHE_FLAG_UPDATE_FREQ);
1003 : 56904 : gcc_assert (ok);
1004 : :
1005 : : /* Create item for switch. */
1006 : 56904 : unsigned j = n_peel - i - (extra_zero_check ? 0 : 1);
1007 : 56904 : p = profile_probability::always () / (i + 2);
1008 : :
1009 : 56904 : preheader = split_edge (loop_preheader_edge (loop));
1010 : : /* Add in count of edge from switch block. */
1011 : 56904 : preheader->count += iter_count;
1012 : 56904 : branch_code = compare_and_jump_seq (copy_rtx (niter),
1013 : 56904 : gen_int_mode (j, desc->mode), EQ,
1014 : : block_label (preheader), p, NULL);
1015 : :
1016 : : /* We rely on the fact that the compare and jump cannot be optimized out,
1017 : : and hence the cfg we create is correct. */
1018 : 56904 : gcc_assert (branch_code != NULL_RTX);
1019 : :
1020 : 56904 : swtch = split_edge_and_insert (single_pred_edge (swtch), branch_code);
1021 : 56904 : set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1022 : 56904 : single_succ_edge (swtch)->probability = p.invert ();
1023 : 56904 : new_count += iter_count;
1024 : 56904 : swtch->count = new_count;
1025 : 170712 : e = make_edge (swtch, preheader,
1026 : 56904 : single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1027 : 56904 : e->probability = p;
1028 : : }
1029 : :
1030 : 19317 : if (extra_zero_check)
1031 : : {
1032 : : /* Add branch for zero iterations. */
1033 : 675 : p = profile_probability::always () / (max_unroll + 1);
1034 : 675 : swtch = ezc_swtch;
1035 : 675 : preheader = split_edge (loop_preheader_edge (loop));
1036 : : /* Recompute count adjustments since initial peel copy may
1037 : : have exited and reduced those values that were computed above. */
1038 : 675 : iter_count = swtch->count / (max_unroll + 1);
1039 : : /* Add in count of edge from switch block. */
1040 : 675 : preheader->count += iter_count;
1041 : 675 : branch_code = compare_and_jump_seq (copy_rtx (niter), const0_rtx, EQ,
1042 : : block_label (preheader), p,
1043 : : NULL);
1044 : 675 : gcc_assert (branch_code != NULL_RTX);
1045 : :
1046 : 675 : swtch = split_edge_and_insert (single_succ_edge (swtch), branch_code);
1047 : 675 : set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1048 : 675 : single_succ_edge (swtch)->probability = p.invert ();
1049 : 2025 : e = make_edge (swtch, preheader,
1050 : 675 : single_succ_edge (swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1051 : 675 : e->probability = p;
1052 : : }
1053 : :
1054 : : /* Recount dominators for outer blocks. */
1055 : 19317 : iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
1056 : :
1057 : : /* And unroll loop. */
1058 : :
1059 : 19317 : bitmap_ones (wont_exit);
1060 : 19317 : bitmap_clear_bit (wont_exit, may_exit_copy);
1061 : 57951 : opt_info_start_duplication (opt_info);
1062 : :
1063 : 19317 : ok = duplicate_loop_body_to_header_edge (
1064 : : loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
1065 : : &remove_edges,
1066 : : DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
1067 : 19317 : gcc_assert (ok);
1068 : :
1069 : 19317 : if (opt_info)
1070 : : {
1071 : 19317 : apply_opt_in_copies (opt_info, max_unroll, true, true);
1072 : 19317 : free_opt_info (opt_info);
1073 : : }
1074 : :
1075 : 19317 : if (exit_at_end)
1076 : : {
1077 : 18642 : basic_block exit_block = get_bb_copy (desc->in_edge->src);
1078 : : /* Find a new in and out edge; they are in the last copy we have
1079 : : made. */
1080 : :
1081 : 18642 : if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
1082 : : {
1083 : 3600 : desc->out_edge = EDGE_SUCC (exit_block, 0);
1084 : 3600 : desc->in_edge = EDGE_SUCC (exit_block, 1);
1085 : : }
1086 : : else
1087 : : {
1088 : 15042 : desc->out_edge = EDGE_SUCC (exit_block, 1);
1089 : 15042 : desc->in_edge = EDGE_SUCC (exit_block, 0);
1090 : : }
1091 : : }
1092 : :
1093 : : /* Remove the edges. */
1094 : 115667 : FOR_EACH_VEC_ELT (remove_edges, i, e)
1095 : 96350 : remove_path (e);
1096 : :
1097 : : /* We must be careful when updating the number of iterations due to
1098 : : preconditioning and the fact that the value must be valid at entry
1099 : : of the loop. After passing through the above code, we see that
1100 : : the correct new number of iterations is this: */
1101 : 19317 : gcc_assert (!desc->const_iter);
1102 : 38634 : desc->niter_expr =
1103 : 19317 : simplify_gen_binary (UDIV, desc->mode, old_niter,
1104 : 19317 : gen_int_mode (max_unroll + 1, desc->mode));
1105 : 19317 : loop->nb_iterations_upper_bound
1106 : 19317 : = wi::udiv_trunc (loop->nb_iterations_upper_bound, max_unroll + 1);
1107 : 19317 : if (loop->any_estimate)
1108 : 672 : loop->nb_iterations_estimate
1109 : 672 : = wi::udiv_trunc (loop->nb_iterations_estimate, max_unroll + 1);
1110 : 19317 : if (loop->any_likely_upper_bound)
1111 : 18192 : loop->nb_iterations_likely_upper_bound
1112 : 18192 : = wi::udiv_trunc (loop->nb_iterations_likely_upper_bound, max_unroll + 1);
1113 : 19317 : if (exit_at_end)
1114 : : {
1115 : 37284 : desc->niter_expr =
1116 : 18642 : simplify_gen_binary (MINUS, desc->mode, desc->niter_expr, const1_rtx);
1117 : 18642 : desc->noloop_assumptions = NULL_RTX;
1118 : 18642 : --loop->nb_iterations_upper_bound;
1119 : 18642 : if (loop->any_estimate
1120 : 18642 : && loop->nb_iterations_estimate != 0)
1121 : 671 : --loop->nb_iterations_estimate;
1122 : : else
1123 : 17971 : loop->any_estimate = false;
1124 : 18642 : if (loop->any_likely_upper_bound
1125 : 18642 : && loop->nb_iterations_likely_upper_bound != 0)
1126 : 17549 : --loop->nb_iterations_likely_upper_bound;
1127 : : else
1128 : 1093 : loop->any_likely_upper_bound = false;
1129 : : }
1130 : :
1131 : 19317 : if (dump_file)
1132 : 14 : fprintf (dump_file,
1133 : : ";; Unrolled loop %d times, counting # of iterations "
1134 : : "in runtime, %i insns\n",
1135 : : max_unroll, num_loop_insns (loop));
1136 : 19317 : }
1137 : :
1138 : : /* Decide whether to unroll LOOP stupidly and how much. */
1139 : : static void
1140 : 328284 : decide_unroll_stupid (class loop *loop, int flags)
1141 : : {
1142 : 328284 : unsigned nunroll, nunroll_by_av, i;
1143 : 328284 : class niter_desc *desc;
1144 : 328284 : widest_int iterations;
1145 : :
1146 : : /* If we were not asked to unroll this loop, just return back silently. */
1147 : 328284 : if (!(flags & UAP_UNROLL_ALL) && !loop->unroll)
1148 : : return;
1149 : :
1150 : 150 : if (dump_enabled_p ())
1151 : 33 : dump_printf (MSG_NOTE, "considering unrolling loop stupidly\n");
1152 : :
1153 : : /* nunroll = total number of copies of the original loop body in
1154 : : unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1155 : 150 : nunroll = param_max_unrolled_insns / loop->ninsns;
1156 : 150 : nunroll_by_av
1157 : 150 : = param_max_average_unrolled_insns / loop->av_ninsns;
1158 : 150 : if (nunroll > nunroll_by_av)
1159 : : nunroll = nunroll_by_av;
1160 : 150 : if (nunroll > (unsigned) param_max_unroll_times)
1161 : : nunroll = param_max_unroll_times;
1162 : :
1163 : 150 : if (targetm.loop_unroll_adjust)
1164 : 150 : nunroll = targetm.loop_unroll_adjust (nunroll, loop);
1165 : :
1166 : 150 : if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
1167 : 131 : nunroll = loop->unroll;
1168 : :
1169 : : /* Skip big loops. */
1170 : 150 : if (nunroll <= 1)
1171 : : {
1172 : 1 : if (dump_file)
1173 : 0 : fprintf (dump_file, ";; Not considering loop, is too big\n");
1174 : 1 : return;
1175 : : }
1176 : :
1177 : : /* Check for simple loops. */
1178 : 149 : desc = get_simple_loop_desc (loop);
1179 : :
1180 : : /* Check simpleness. */
1181 : 149 : if (desc->simple_p && !desc->assumptions)
1182 : : {
1183 : 27 : if (dump_file)
1184 : 9 : fprintf (dump_file, ";; Loop is simple\n");
1185 : 27 : return;
1186 : : }
1187 : :
1188 : : /* Do not unroll loops with branches inside -- it increases number
1189 : : of mispredicts.
1190 : : TODO: this heuristic needs tunning; call inside the loop body
1191 : : is also relatively good reason to not unroll. */
1192 : 122 : if (num_loop_branches (loop) > 1)
1193 : : {
1194 : 18 : if (dump_file)
1195 : 0 : fprintf (dump_file, ";; Not unrolling, contains branches\n");
1196 : 18 : return;
1197 : : }
1198 : :
1199 : : /* Check whether the loop rolls. */
1200 : 104 : if ((get_estimated_loop_iterations (loop, &iterations)
1201 : 104 : || get_likely_max_loop_iterations (loop, &iterations))
1202 : 208 : && wi::ltu_p (iterations, 2 * nunroll))
1203 : : {
1204 : 0 : if (dump_file)
1205 : 0 : fprintf (dump_file, ";; Not unrolling loop, doesn't roll\n");
1206 : 0 : return;
1207 : : }
1208 : :
1209 : : /* Success. Now force nunroll to be power of 2, as it seems that this
1210 : : improves results (partially because of better alignments, partially
1211 : : because of some dark magic). */
1212 : 288 : for (i = 1; 2 * i <= nunroll; i *= 2)
1213 : 184 : continue;
1214 : :
1215 : 104 : loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1216 : 104 : loop->lpt_decision.times = i - 1;
1217 : 328284 : }
1218 : :
1219 : : /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1220 : :
1221 : : while (cond)
1222 : : body;
1223 : :
1224 : : ==> (LOOP->LPT_DECISION.TIMES == 3)
1225 : :
1226 : : while (cond)
1227 : : {
1228 : : body;
1229 : : if (!cond) break;
1230 : : body;
1231 : : if (!cond) break;
1232 : : body;
1233 : : if (!cond) break;
1234 : : body;
1235 : : }
1236 : : */
1237 : : static void
1238 : 104 : unroll_loop_stupid (class loop *loop)
1239 : : {
1240 : 104 : unsigned nunroll = loop->lpt_decision.times;
1241 : 104 : class niter_desc *desc = get_simple_loop_desc (loop);
1242 : 104 : struct opt_info *opt_info = NULL;
1243 : 104 : bool ok;
1244 : :
1245 : 104 : if (flag_split_ivs_in_unroller
1246 : 0 : || flag_variable_expansion_in_unroller)
1247 : 104 : opt_info = analyze_insns_in_loop (loop);
1248 : :
1249 : 104 : auto_sbitmap wont_exit (nunroll + 1);
1250 : 104 : bitmap_clear (wont_exit);
1251 : 312 : opt_info_start_duplication (opt_info);
1252 : :
1253 : 104 : ok = duplicate_loop_body_to_header_edge (
1254 : : loop, loop_latch_edge (loop), nunroll, wont_exit, NULL, NULL,
1255 : : DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
1256 : 104 : gcc_assert (ok);
1257 : :
1258 : 104 : if (opt_info)
1259 : : {
1260 : 104 : apply_opt_in_copies (opt_info, nunroll, true, true);
1261 : 104 : free_opt_info (opt_info);
1262 : : }
1263 : :
1264 : 104 : if (desc->simple_p)
1265 : : {
1266 : : /* We indeed may get here provided that there are nontrivial assumptions
1267 : : for a loop to be really simple. We could update the counts, but the
1268 : : problem is that we are unable to decide which exit will be taken
1269 : : (not really true in case the number of iterations is constant,
1270 : : but no one will do anything with this information, so we do not
1271 : : worry about it). */
1272 : 0 : desc->simple_p = false;
1273 : : }
1274 : :
1275 : 104 : if (dump_file)
1276 : 24 : fprintf (dump_file, ";; Unrolled loop %d times, %i insns\n",
1277 : : nunroll, num_loop_insns (loop));
1278 : 104 : }
1279 : :
1280 : : /* Returns true if REG is referenced in one nondebug insn in LOOP.
1281 : : Set *DEBUG_USES to the number of debug insns that reference the
1282 : : variable. */
1283 : :
1284 : : static bool
1285 : 3 : referenced_in_one_insn_in_loop_p (class loop *loop, rtx reg,
1286 : : int *debug_uses)
1287 : : {
1288 : 3 : basic_block *body, bb;
1289 : 3 : unsigned i;
1290 : 3 : int count_ref = 0;
1291 : 3 : rtx_insn *insn;
1292 : :
1293 : 3 : body = get_loop_body (loop);
1294 : 12 : for (i = 0; i < loop->num_nodes; i++)
1295 : : {
1296 : 6 : bb = body[i];
1297 : :
1298 : 30 : FOR_BB_INSNS (bb, insn)
1299 : 24 : if (!rtx_referenced_p (reg, insn))
1300 : 21 : continue;
1301 : 3 : else if (DEBUG_INSN_P (insn))
1302 : 0 : ++*debug_uses;
1303 : 3 : else if (++count_ref > 1)
1304 : : break;
1305 : : }
1306 : 3 : free (body);
1307 : 3 : return (count_ref == 1);
1308 : : }
1309 : :
1310 : : /* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1311 : :
1312 : : static void
1313 : 0 : reset_debug_uses_in_loop (class loop *loop, rtx reg, int debug_uses)
1314 : : {
1315 : 0 : basic_block *body, bb;
1316 : 0 : unsigned i;
1317 : 0 : rtx_insn *insn;
1318 : :
1319 : 0 : body = get_loop_body (loop);
1320 : 0 : for (i = 0; debug_uses && i < loop->num_nodes; i++)
1321 : : {
1322 : 0 : bb = body[i];
1323 : :
1324 : 0 : FOR_BB_INSNS (bb, insn)
1325 : 0 : if (!DEBUG_INSN_P (insn) || !rtx_referenced_p (reg, insn))
1326 : 0 : continue;
1327 : : else
1328 : : {
1329 : 0 : validate_change (insn, &INSN_VAR_LOCATION_LOC (insn),
1330 : : gen_rtx_UNKNOWN_VAR_LOC (), 0);
1331 : 0 : if (!--debug_uses)
1332 : : break;
1333 : : }
1334 : : }
1335 : 0 : free (body);
1336 : 0 : }
1337 : :
1338 : : /* Determine whether INSN contains an accumulator
1339 : : which can be expanded into separate copies,
1340 : : one for each copy of the LOOP body.
1341 : :
1342 : : for (i = 0 ; i < n; i++)
1343 : : sum += a[i];
1344 : :
1345 : : ==>
1346 : :
1347 : : sum += a[i]
1348 : : ....
1349 : : i = i+1;
1350 : : sum1 += a[i]
1351 : : ....
1352 : : i = i+1
1353 : : sum2 += a[i];
1354 : : ....
1355 : :
1356 : : Return NULL if INSN contains no opportunity for expansion of accumulator.
1357 : : Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1358 : : information and return a pointer to it.
1359 : : */
1360 : :
1361 : : static struct var_to_expand *
1362 : 33 : analyze_insn_to_expand_var (class loop *loop, rtx_insn *insn)
1363 : : {
1364 : 33 : rtx set, dest, src;
1365 : 33 : struct var_to_expand *ves;
1366 : 33 : unsigned accum_pos;
1367 : 33 : enum rtx_code code;
1368 : 33 : int debug_uses = 0;
1369 : :
1370 : 33 : set = single_set (insn);
1371 : 33 : if (!set)
1372 : : return NULL;
1373 : :
1374 : 22 : dest = SET_DEST (set);
1375 : 22 : src = SET_SRC (set);
1376 : 22 : code = GET_CODE (src);
1377 : :
1378 : 22 : if (code != PLUS && code != MINUS && code != MULT && code != FMA)
1379 : : return NULL;
1380 : :
1381 : 5 : if (FLOAT_MODE_P (GET_MODE (dest)))
1382 : : {
1383 : 2 : if (!flag_associative_math)
1384 : : return NULL;
1385 : : /* In the case of FMA, we're also changing the rounding. */
1386 : 2 : if (code == FMA && !flag_unsafe_math_optimizations)
1387 : : return NULL;
1388 : : }
1389 : :
1390 : : /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1391 : : in MD. But if there is no optab to generate the insn, we cannot
1392 : : perform the variable expansion. This can happen if an MD provides
1393 : : an insn but not a named pattern to generate it, for example to avoid
1394 : : producing code that needs additional mode switches like for x87/mmx.
1395 : :
1396 : : So we check have_insn_for which looks for an optab for the operation
1397 : : in SRC. If it doesn't exist, we can't perform the expansion even
1398 : : though INSN is valid. */
1399 : 5 : if (!have_insn_for (code, GET_MODE (src)))
1400 : : return NULL;
1401 : :
1402 : 5 : if (!REG_P (dest)
1403 : 0 : && !(GET_CODE (dest) == SUBREG
1404 : 0 : && REG_P (SUBREG_REG (dest))))
1405 : : return NULL;
1406 : :
1407 : : /* Find the accumulator use within the operation. */
1408 : 5 : if (code == FMA)
1409 : : {
1410 : : /* We only support accumulation via FMA in the ADD position. */
1411 : 0 : if (!rtx_equal_p (dest, XEXP (src, 2)))
1412 : : return NULL;
1413 : : accum_pos = 2;
1414 : : }
1415 : 5 : else if (rtx_equal_p (dest, XEXP (src, 0)))
1416 : : accum_pos = 0;
1417 : 2 : else if (rtx_equal_p (dest, XEXP (src, 1)))
1418 : : {
1419 : : /* The method of expansion that we are using; which includes the
1420 : : initialization of the expansions with zero and the summation of
1421 : : the expansions at the end of the computation will yield wrong
1422 : : results for (x = something - x) thus avoid using it in that case. */
1423 : 0 : if (code == MINUS)
1424 : : return NULL;
1425 : : accum_pos = 1;
1426 : : }
1427 : : else
1428 : : return NULL;
1429 : :
1430 : : /* It must not otherwise be used. */
1431 : 3 : if (code == FMA)
1432 : : {
1433 : 0 : if (rtx_referenced_p (dest, XEXP (src, 0))
1434 : 0 : || rtx_referenced_p (dest, XEXP (src, 1)))
1435 : 0 : return NULL;
1436 : : }
1437 : 3 : else if (rtx_referenced_p (dest, XEXP (src, 1 - accum_pos)))
1438 : : return NULL;
1439 : :
1440 : : /* It must be used in exactly one insn. */
1441 : 3 : if (!referenced_in_one_insn_in_loop_p (loop, dest, &debug_uses))
1442 : : return NULL;
1443 : :
1444 : 3 : if (dump_file)
1445 : : {
1446 : 1 : fprintf (dump_file, "\n;; Expanding Accumulator ");
1447 : 1 : print_rtl (dump_file, dest);
1448 : 1 : fprintf (dump_file, "\n");
1449 : : }
1450 : :
1451 : 3 : if (debug_uses)
1452 : : /* Instead of resetting the debug insns, we could replace each
1453 : : debug use in the loop with the sum or product of all expanded
1454 : : accumulators. Since we'll only know of all expansions at the
1455 : : end, we'd have to keep track of which vars_to_expand a debug
1456 : : insn in the loop references, take note of each copy of the
1457 : : debug insn during unrolling, and when it's all done, compute
1458 : : the sum or product of each variable and adjust the original
1459 : : debug insn and each copy thereof. What a pain! */
1460 : 0 : reset_debug_uses_in_loop (loop, dest, debug_uses);
1461 : :
1462 : : /* Record the accumulator to expand. */
1463 : 3 : ves = XNEW (struct var_to_expand);
1464 : 3 : ves->insn = insn;
1465 : 3 : ves->reg = copy_rtx (dest);
1466 : 3 : ves->var_expansions.create (1);
1467 : 3 : ves->next = NULL;
1468 : 3 : ves->op = GET_CODE (src);
1469 : 3 : ves->expansion_count = 0;
1470 : 3 : ves->reuse_expansion = 0;
1471 : 3 : return ves;
1472 : : }
1473 : :
1474 : : /* Determine whether there is an induction variable in INSN that
1475 : : we would like to split during unrolling.
1476 : :
1477 : : I.e. replace
1478 : :
1479 : : i = i + 1;
1480 : : ...
1481 : : i = i + 1;
1482 : : ...
1483 : : i = i + 1;
1484 : : ...
1485 : :
1486 : : type chains by
1487 : :
1488 : : i0 = i + 1
1489 : : ...
1490 : : i = i0 + 1
1491 : : ...
1492 : : i = i0 + 2
1493 : : ...
1494 : :
1495 : : Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1496 : : an IV_TO_SPLIT structure, fill it with the relevant information and return a
1497 : : pointer to it. */
1498 : :
1499 : : static struct iv_to_split *
1500 : 409407 : analyze_iv_to_split_insn (rtx_insn *insn)
1501 : : {
1502 : 409407 : rtx set, dest;
1503 : 409407 : class rtx_iv iv;
1504 : 409407 : struct iv_to_split *ivts;
1505 : 409407 : scalar_int_mode mode;
1506 : 409407 : bool ok;
1507 : :
1508 : : /* For now we just split the basic induction variables. Later this may be
1509 : : extended for example by selecting also addresses of memory references. */
1510 : 409407 : set = single_set (insn);
1511 : 409407 : if (!set)
1512 : : return NULL;
1513 : :
1514 : 266813 : dest = SET_DEST (set);
1515 : 444805 : if (!REG_P (dest) || !is_a <scalar_int_mode> (GET_MODE (dest), &mode))
1516 : : return NULL;
1517 : :
1518 : 85982 : if (!biv_p (insn, mode, dest))
1519 : : return NULL;
1520 : :
1521 : 50589 : ok = iv_analyze_result (insn, dest, &iv);
1522 : :
1523 : : /* This used to be an assert under the assumption that if biv_p returns
1524 : : true that iv_analyze_result must also return true. However, that
1525 : : assumption is not strictly correct as evidenced by pr25569.
1526 : :
1527 : : Returning NULL when iv_analyze_result returns false is safe and
1528 : : avoids the problems in pr25569 until the iv_analyze_* routines
1529 : : can be fixed, which is apparently hard and time consuming
1530 : : according to their author. */
1531 : 50589 : if (! ok)
1532 : : return NULL;
1533 : :
1534 : 50589 : if (iv.step == const0_rtx
1535 : 50589 : || iv.mode != iv.extend_mode)
1536 : : return NULL;
1537 : :
1538 : : /* Record the insn to split. */
1539 : 50584 : ivts = XNEW (struct iv_to_split);
1540 : 50584 : ivts->insn = insn;
1541 : 50584 : ivts->orig_var = dest;
1542 : 50584 : ivts->base_var = NULL_RTX;
1543 : 50584 : ivts->step = iv.step;
1544 : 50584 : ivts->next = NULL;
1545 : :
1546 : 50584 : return ivts;
1547 : : }
1548 : :
1549 : : /* Determines which of insns in LOOP can be optimized.
1550 : : Return a OPT_INFO struct with the relevant hash tables filled
1551 : : with all insns to be optimized. The FIRST_NEW_BLOCK field
1552 : : is undefined for the return value. */
1553 : :
1554 : : static struct opt_info *
1555 : 48010 : analyze_insns_in_loop (class loop *loop)
1556 : : {
1557 : 48010 : basic_block *body, bb;
1558 : 48010 : unsigned i;
1559 : 48010 : struct opt_info *opt_info = XCNEW (struct opt_info);
1560 : 48010 : rtx_insn *insn;
1561 : 48010 : struct iv_to_split *ivts = NULL;
1562 : 48010 : struct var_to_expand *ves = NULL;
1563 : 48010 : iv_to_split **slot1;
1564 : 48010 : var_to_expand **slot2;
1565 : 48010 : auto_vec<edge> edges = get_loop_exit_edges (loop);
1566 : 48010 : edge exit;
1567 : 48010 : bool can_apply = false;
1568 : :
1569 : 48010 : iv_analysis_loop_init (loop);
1570 : :
1571 : 48010 : body = get_loop_body (loop);
1572 : :
1573 : 48010 : if (flag_split_ivs_in_unroller)
1574 : : {
1575 : 48010 : opt_info->insns_to_split
1576 : 48010 : = new hash_table<iv_split_hasher> (5 * loop->num_nodes);
1577 : 48010 : opt_info->iv_to_split_head = NULL;
1578 : 48010 : opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
1579 : : }
1580 : :
1581 : : /* Record the loop exit bb and loop preheader before the unrolling. */
1582 : 48010 : opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1583 : :
1584 : 48010 : if (edges.length () == 1)
1585 : : {
1586 : 42964 : exit = edges[0];
1587 : 42964 : if (!(exit->flags & EDGE_COMPLEX))
1588 : : {
1589 : 42964 : opt_info->loop_exit = split_edge (exit);
1590 : 42964 : can_apply = true;
1591 : : }
1592 : : }
1593 : :
1594 : 48010 : if (flag_variable_expansion_in_unroller
1595 : 6 : && can_apply)
1596 : : {
1597 : 6 : opt_info->insns_with_var_to_expand
1598 : 6 : = new hash_table<var_expand_hasher> (5 * loop->num_nodes);
1599 : 6 : opt_info->var_to_expand_head = NULL;
1600 : 6 : opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
1601 : : }
1602 : :
1603 : 153297 : for (i = 0; i < loop->num_nodes; i++)
1604 : : {
1605 : 105287 : bb = body[i];
1606 : 105287 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1607 : 2389 : continue;
1608 : :
1609 : 711920 : FOR_BB_INSNS (bb, insn)
1610 : : {
1611 : 609022 : if (!INSN_P (insn))
1612 : 199615 : continue;
1613 : :
1614 : 409407 : if (opt_info->insns_to_split)
1615 : 409407 : ivts = analyze_iv_to_split_insn (insn);
1616 : :
1617 : 409407 : if (ivts)
1618 : : {
1619 : 50584 : slot1 = opt_info->insns_to_split->find_slot (ivts, INSERT);
1620 : 50584 : gcc_assert (*slot1 == NULL);
1621 : 50584 : *slot1 = ivts;
1622 : 50584 : *opt_info->iv_to_split_tail = ivts;
1623 : 50584 : opt_info->iv_to_split_tail = &ivts->next;
1624 : 50584 : continue;
1625 : : }
1626 : :
1627 : 358823 : if (opt_info->insns_with_var_to_expand)
1628 : 33 : ves = analyze_insn_to_expand_var (loop, insn);
1629 : :
1630 : 358823 : if (ves)
1631 : : {
1632 : 3 : slot2 = opt_info->insns_with_var_to_expand->find_slot (ves, INSERT);
1633 : 3 : gcc_assert (*slot2 == NULL);
1634 : 3 : *slot2 = ves;
1635 : 3 : *opt_info->var_to_expand_tail = ves;
1636 : 3 : opt_info->var_to_expand_tail = &ves->next;
1637 : : }
1638 : : }
1639 : : }
1640 : :
1641 : 48010 : free (body);
1642 : 48010 : return opt_info;
1643 : 48010 : }
1644 : :
1645 : : /* Called just before loop duplication. Records start of duplicated area
1646 : : to OPT_INFO. */
1647 : :
1648 : : static void
1649 : 49590 : opt_info_start_duplication (struct opt_info *opt_info)
1650 : : {
1651 : 49590 : if (opt_info)
1652 : 49590 : opt_info->first_new_block = last_basic_block_for_fn (cfun);
1653 : 0 : }
1654 : :
1655 : : /* Determine the number of iterations between initialization of the base
1656 : : variable and the current copy (N_COPY). N_COPIES is the total number
1657 : : of newly created copies. UNROLLING is true if we are unrolling
1658 : : (not peeling) the loop. */
1659 : :
1660 : : static unsigned
1661 : 341980 : determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
1662 : : {
1663 : 0 : if (unrolling)
1664 : : {
1665 : : /* If we are unrolling, initialization is done in the original loop
1666 : : body (number 0). */
1667 : : return n_copy;
1668 : : }
1669 : : else
1670 : : {
1671 : : /* If we are peeling, the copy in that the initialization occurs has
1672 : : number 1. The original loop (number 0) is the last. */
1673 : 3601 : if (n_copy)
1674 : 3601 : return n_copy - 1;
1675 : : else
1676 : : return n_copies;
1677 : : }
1678 : : }
1679 : :
1680 : : /* Allocate basic variable for the induction variable chain. */
1681 : :
1682 : : static void
1683 : 51075 : allocate_basic_variable (struct iv_to_split *ivts)
1684 : : {
1685 : 51075 : rtx expr = SET_SRC (single_set (ivts->insn));
1686 : :
1687 : 51075 : ivts->base_var = gen_reg_rtx (GET_MODE (expr));
1688 : 51075 : }
1689 : :
1690 : : /* Insert initialization of basic variable of IVTS before INSN, taking
1691 : : the initial value from INSN. */
1692 : :
1693 : : static void
1694 : 61076 : insert_base_initialization (struct iv_to_split *ivts, rtx_insn *insn)
1695 : : {
1696 : 61076 : rtx expr = copy_rtx (SET_SRC (single_set (insn)));
1697 : 61076 : rtx_insn *seq;
1698 : :
1699 : 61076 : start_sequence ();
1700 : 61076 : expr = force_operand (expr, ivts->base_var);
1701 : 61076 : if (expr != ivts->base_var)
1702 : 236 : emit_move_insn (ivts->base_var, expr);
1703 : 61076 : seq = get_insns ();
1704 : 61076 : end_sequence ();
1705 : :
1706 : 61076 : emit_insn_before (seq, insn);
1707 : 61076 : }
1708 : :
1709 : : /* Replace the use of induction variable described in IVTS in INSN
1710 : : by base variable + DELTA * step. */
1711 : :
1712 : : static void
1713 : 169113 : split_iv (struct iv_to_split *ivts, rtx_insn *insn, unsigned delta)
1714 : : {
1715 : 169113 : rtx expr, *loc, incr, var;
1716 : 169113 : rtx_insn *seq;
1717 : 169113 : machine_mode mode = GET_MODE (ivts->base_var);
1718 : 169113 : rtx src, dest, set;
1719 : :
1720 : : /* Construct base + DELTA * step. */
1721 : 169113 : if (!delta)
1722 : : expr = ivts->base_var;
1723 : : else
1724 : : {
1725 : 108037 : incr = simplify_gen_binary (MULT, mode,
1726 : : copy_rtx (ivts->step),
1727 : 108037 : gen_int_mode (delta, mode));
1728 : 108037 : expr = simplify_gen_binary (PLUS, GET_MODE (ivts->base_var),
1729 : : ivts->base_var, incr);
1730 : : }
1731 : :
1732 : : /* Figure out where to do the replacement. */
1733 : 169113 : loc = &SET_SRC (single_set (insn));
1734 : :
1735 : : /* If we can make the replacement right away, we're done. */
1736 : 169113 : if (validate_change (insn, loc, expr, 0))
1737 : : return;
1738 : :
1739 : : /* Otherwise, force EXPR into a register and try again. */
1740 : 256 : start_sequence ();
1741 : 256 : var = gen_reg_rtx (mode);
1742 : 256 : expr = force_operand (expr, var);
1743 : 256 : if (expr != var)
1744 : 0 : emit_move_insn (var, expr);
1745 : 256 : seq = get_insns ();
1746 : 256 : end_sequence ();
1747 : 256 : emit_insn_before (seq, insn);
1748 : :
1749 : 256 : if (validate_change (insn, loc, var, 0))
1750 : : return;
1751 : :
1752 : : /* The last chance. Try recreating the assignment in insn
1753 : : completely from scratch. */
1754 : 0 : set = single_set (insn);
1755 : 0 : gcc_assert (set);
1756 : :
1757 : 0 : start_sequence ();
1758 : 0 : *loc = var;
1759 : 0 : src = copy_rtx (SET_SRC (set));
1760 : 0 : dest = copy_rtx (SET_DEST (set));
1761 : 0 : src = force_operand (src, dest);
1762 : 0 : if (src != dest)
1763 : 0 : emit_move_insn (dest, src);
1764 : 0 : seq = get_insns ();
1765 : 0 : end_sequence ();
1766 : :
1767 : 0 : emit_insn_before (seq, insn);
1768 : 0 : delete_insn (insn);
1769 : : }
1770 : :
1771 : :
1772 : : /* Return one expansion of the accumulator recorded in struct VE. */
1773 : :
1774 : : static rtx
1775 : 18 : get_expansion (struct var_to_expand *ve)
1776 : : {
1777 : 18 : rtx reg;
1778 : :
1779 : 18 : if (ve->reuse_expansion == 0)
1780 : 9 : reg = ve->reg;
1781 : : else
1782 : 9 : reg = ve->var_expansions[ve->reuse_expansion - 1];
1783 : :
1784 : 36 : if (ve->var_expansions.length () == (unsigned) ve->reuse_expansion)
1785 : 9 : ve->reuse_expansion = 0;
1786 : : else
1787 : 9 : ve->reuse_expansion++;
1788 : :
1789 : 18 : return reg;
1790 : : }
1791 : :
1792 : :
1793 : : /* Given INSN replace the uses of the accumulator recorded in VE
1794 : : with a new register. */
1795 : :
1796 : : static void
1797 : 21 : expand_var_during_unrolling (struct var_to_expand *ve, rtx_insn *insn)
1798 : : {
1799 : 21 : rtx new_reg, set;
1800 : 21 : bool really_new_expansion = false;
1801 : :
1802 : 21 : set = single_set (insn);
1803 : 21 : gcc_assert (set);
1804 : :
1805 : : /* Generate a new register only if the expansion limit has not been
1806 : : reached. Else reuse an already existing expansion. */
1807 : 21 : if (param_max_variable_expansions > ve->expansion_count)
1808 : : {
1809 : 3 : really_new_expansion = true;
1810 : 3 : new_reg = gen_reg_rtx (GET_MODE (ve->reg));
1811 : : }
1812 : : else
1813 : 18 : new_reg = get_expansion (ve);
1814 : :
1815 : 21 : validate_replace_rtx_group (SET_DEST (set), new_reg, insn);
1816 : 21 : if (apply_change_group ())
1817 : 21 : if (really_new_expansion)
1818 : : {
1819 : 3 : ve->var_expansions.safe_push (new_reg);
1820 : 3 : ve->expansion_count++;
1821 : : }
1822 : 21 : }
1823 : :
1824 : : /* Initialize the variable expansions in loop preheader. PLACE is the
1825 : : loop-preheader basic block where the initialization of the
1826 : : expansions should take place. The expansions are initialized with
1827 : : (-0) when the operation is plus or minus to honor sign zero. This
1828 : : way we can prevent cases where the sign of the final result is
1829 : : effected by the sign of the expansion. Here is an example to
1830 : : demonstrate this:
1831 : :
1832 : : for (i = 0 ; i < n; i++)
1833 : : sum += something;
1834 : :
1835 : : ==>
1836 : :
1837 : : sum += something
1838 : : ....
1839 : : i = i+1;
1840 : : sum1 += something
1841 : : ....
1842 : : i = i+1
1843 : : sum2 += something;
1844 : : ....
1845 : :
1846 : : When SUM is initialized with -zero and SOMETHING is also -zero; the
1847 : : final result of sum should be -zero thus the expansions sum1 and sum2
1848 : : should be initialized with -zero as well (otherwise we will get +zero
1849 : : as the final result). */
1850 : :
1851 : : static void
1852 : 3 : insert_var_expansion_initialization (struct var_to_expand *ve,
1853 : : basic_block place)
1854 : : {
1855 : 3 : rtx_insn *seq;
1856 : 3 : rtx var, zero_init;
1857 : 3 : unsigned i;
1858 : 3 : machine_mode mode = GET_MODE (ve->reg);
1859 : 9 : bool has_signed_zero_p = MODE_HAS_SIGNED_ZEROS (mode);
1860 : :
1861 : 3 : if (ve->var_expansions.length () == 0)
1862 : 3 : return;
1863 : :
1864 : 3 : start_sequence ();
1865 : 3 : switch (ve->op)
1866 : : {
1867 : : case FMA:
1868 : : /* Note that we only accumulate FMA via the ADD operand. */
1869 : : case PLUS:
1870 : : case MINUS:
1871 : 6 : FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1872 : : {
1873 : 3 : if (has_signed_zero_p)
1874 : 2 : zero_init = simplify_gen_unary (NEG, mode, CONST0_RTX (mode), mode);
1875 : : else
1876 : 1 : zero_init = CONST0_RTX (mode);
1877 : 3 : emit_move_insn (var, zero_init);
1878 : : }
1879 : : break;
1880 : :
1881 : : case MULT:
1882 : 0 : FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1883 : : {
1884 : 0 : zero_init = CONST1_RTX (GET_MODE (var));
1885 : 0 : emit_move_insn (var, zero_init);
1886 : : }
1887 : : break;
1888 : :
1889 : 0 : default:
1890 : 0 : gcc_unreachable ();
1891 : : }
1892 : :
1893 : 3 : seq = get_insns ();
1894 : 3 : end_sequence ();
1895 : :
1896 : 3 : emit_insn_after (seq, BB_END (place));
1897 : : }
1898 : :
1899 : : /* Combine the variable expansions at the loop exit. PLACE is the
1900 : : loop exit basic block where the summation of the expansions should
1901 : : take place. */
1902 : :
1903 : : static void
1904 : 3 : combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
1905 : : {
1906 : 3 : rtx sum = ve->reg;
1907 : 3 : rtx expr, var;
1908 : 3 : rtx_insn *seq, *insn;
1909 : 3 : unsigned i;
1910 : :
1911 : 3 : if (ve->var_expansions.length () == 0)
1912 : 3 : return;
1913 : :
1914 : : /* ve->reg might be SUBREG or some other non-shareable RTL, and we use
1915 : : it both here and as the destination of the assignment. */
1916 : 3 : sum = copy_rtx (sum);
1917 : 3 : start_sequence ();
1918 : 3 : switch (ve->op)
1919 : : {
1920 : : case FMA:
1921 : : /* Note that we only accumulate FMA via the ADD operand. */
1922 : : case PLUS:
1923 : : case MINUS:
1924 : 6 : FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1925 : 3 : sum = simplify_gen_binary (PLUS, GET_MODE (ve->reg), var, sum);
1926 : : break;
1927 : :
1928 : : case MULT:
1929 : 0 : FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1930 : 0 : sum = simplify_gen_binary (MULT, GET_MODE (ve->reg), var, sum);
1931 : : break;
1932 : :
1933 : 0 : default:
1934 : 0 : gcc_unreachable ();
1935 : : }
1936 : :
1937 : 3 : expr = force_operand (sum, ve->reg);
1938 : 3 : if (expr != ve->reg)
1939 : 0 : emit_move_insn (ve->reg, expr);
1940 : 3 : seq = get_insns ();
1941 : 3 : end_sequence ();
1942 : :
1943 : 3 : insn = BB_HEAD (place);
1944 : 3 : while (!NOTE_INSN_BASIC_BLOCK_P (insn))
1945 : 0 : insn = NEXT_INSN (insn);
1946 : :
1947 : 3 : emit_insn_after (seq, insn);
1948 : : }
1949 : :
1950 : : /* Strip away REG_EQUAL notes for IVs we're splitting.
1951 : :
1952 : : Updating REG_EQUAL notes for IVs we split is tricky: We
1953 : : cannot tell until after unrolling, DF-rescanning, and liveness
1954 : : updating, whether an EQ_USE is reached by the split IV while
1955 : : the IV reg is still live. See PR55006.
1956 : :
1957 : : ??? We cannot use remove_reg_equal_equiv_notes_for_regno,
1958 : : because RTL loop-iv requires us to defer rescanning insns and
1959 : : any notes attached to them. So resort to old techniques... */
1960 : :
1961 : : static void
1962 : 124309479 : maybe_strip_eq_note_for_split_iv (struct opt_info *opt_info, rtx_insn *insn)
1963 : : {
1964 : 124309479 : struct iv_to_split *ivts;
1965 : 124309479 : rtx note = find_reg_equal_equiv_note (insn);
1966 : 124309479 : if (! note)
1967 : : return;
1968 : 8111210 : for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
1969 : 4162386 : if (reg_mentioned_p (ivts->orig_var, note))
1970 : : {
1971 : 21807 : remove_note (insn, note);
1972 : 21807 : return;
1973 : : }
1974 : : }
1975 : :
1976 : : /* Apply loop optimizations in loop copies using the
1977 : : data which gathered during the unrolling. Structure
1978 : : OPT_INFO record that data.
1979 : :
1980 : : UNROLLING is true if we unrolled (not peeled) the loop.
1981 : : REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
1982 : : the loop (as it should happen in complete unrolling, but not in ordinary
1983 : : peeling of the loop). */
1984 : :
1985 : : static void
1986 : 48487 : apply_opt_in_copies (struct opt_info *opt_info,
1987 : : unsigned n_copies, bool unrolling,
1988 : : bool rewrite_original_loop)
1989 : : {
1990 : 48487 : unsigned i, delta;
1991 : 48487 : basic_block bb, orig_bb;
1992 : 48487 : rtx_insn *insn, *orig_insn, *next;
1993 : 48487 : struct iv_to_split ivts_templ, *ivts;
1994 : 48487 : struct var_to_expand ve_templ, *ves;
1995 : :
1996 : : /* Sanity check -- we need to put initialization in the original loop
1997 : : body. */
1998 : 48487 : gcc_assert (!unrolling || rewrite_original_loop);
1999 : :
2000 : : /* Allocate the basic variables (i0). */
2001 : 48487 : if (opt_info->insns_to_split)
2002 : 99562 : for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
2003 : 51075 : allocate_basic_variable (ivts);
2004 : :
2005 : 285180 : for (i = opt_info->first_new_block;
2006 : 285180 : i < (unsigned) last_basic_block_for_fn (cfun);
2007 : : i++)
2008 : : {
2009 : 236693 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
2010 : 236693 : orig_bb = get_bb_original (bb);
2011 : :
2012 : : /* bb->aux holds position in copy sequence initialized by
2013 : : duplicate_loop_body_to_header_edge. */
2014 : 236693 : delta = determine_split_iv_delta ((size_t)bb->aux, n_copies,
2015 : : unrolling);
2016 : 236693 : bb->aux = 0;
2017 : 236693 : orig_insn = BB_HEAD (orig_bb);
2018 : 3199964 : FOR_BB_INSNS_SAFE (bb, insn, next)
2019 : : {
2020 : 1702856 : if (!INSN_P (insn)
2021 : 1363289 : || (DEBUG_BIND_INSN_P (insn)
2022 : 229684 : && INSN_VAR_LOCATION_DECL (insn)
2023 : 229684 : && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL))
2024 : 339567 : continue;
2025 : :
2026 : 1281328 : while (!INSN_P (orig_insn)
2027 : 1281328 : || (DEBUG_BIND_INSN_P (orig_insn)
2028 : 229696 : && INSN_VAR_LOCATION_DECL (orig_insn)
2029 : 229696 : && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn))
2030 : : == LABEL_DECL)))
2031 : 257606 : orig_insn = NEXT_INSN (orig_insn);
2032 : :
2033 : 1023722 : ivts_templ.insn = orig_insn;
2034 : 1023722 : ve_templ.insn = orig_insn;
2035 : :
2036 : : /* Apply splitting iv optimization. */
2037 : 1023722 : if (opt_info->insns_to_split)
2038 : : {
2039 : 1023722 : maybe_strip_eq_note_for_split_iv (opt_info, insn);
2040 : :
2041 : 1023722 : ivts = opt_info->insns_to_split->find (&ivts_templ);
2042 : :
2043 : 1023722 : if (ivts)
2044 : : {
2045 : 108528 : gcc_assert (GET_CODE (PATTERN (insn))
2046 : : == GET_CODE (PATTERN (orig_insn)));
2047 : :
2048 : 108528 : if (!delta)
2049 : 491 : insert_base_initialization (ivts, insn);
2050 : 108528 : split_iv (ivts, insn, delta);
2051 : : }
2052 : : }
2053 : : /* Apply variable expansion optimization. */
2054 : 1023722 : if (unrolling && opt_info->insns_with_var_to_expand)
2055 : : {
2056 : 546 : ves = (struct var_to_expand *)
2057 : 273 : opt_info->insns_with_var_to_expand->find (&ve_templ);
2058 : 273 : if (ves)
2059 : : {
2060 : 21 : gcc_assert (GET_CODE (PATTERN (insn))
2061 : : == GET_CODE (PATTERN (orig_insn)));
2062 : 21 : expand_var_during_unrolling (ves, insn);
2063 : : }
2064 : : }
2065 : 1023722 : orig_insn = NEXT_INSN (orig_insn);
2066 : : }
2067 : : }
2068 : :
2069 : 48487 : if (!rewrite_original_loop)
2070 : 477 : return;
2071 : :
2072 : : /* Initialize the variable expansions in the loop preheader
2073 : : and take care of combining them at the loop exit. */
2074 : 48010 : if (opt_info->insns_with_var_to_expand)
2075 : : {
2076 : 9 : for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2077 : 3 : insert_var_expansion_initialization (ves, opt_info->loop_preheader);
2078 : 9 : for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2079 : 3 : combine_var_copies_in_loop_exit (ves, opt_info->loop_exit);
2080 : : }
2081 : :
2082 : : /* Rewrite also the original loop body. Find them as originals of the blocks
2083 : : in the last copied iteration, i.e. those that have
2084 : : get_bb_copy (get_bb_original (bb)) == bb. */
2085 : 281102 : for (i = opt_info->first_new_block;
2086 : 281102 : i < (unsigned) last_basic_block_for_fn (cfun);
2087 : : i++)
2088 : : {
2089 : 233092 : bb = BASIC_BLOCK_FOR_FN (cfun, i);
2090 : 233092 : orig_bb = get_bb_original (bb);
2091 : 233092 : if (get_bb_copy (orig_bb) != bb)
2092 : 127805 : continue;
2093 : :
2094 : 105287 : delta = determine_split_iv_delta (0, n_copies, unrolling);
2095 : 105287 : for (orig_insn = BB_HEAD (orig_bb);
2096 : 166491280 : orig_insn != NEXT_INSN (BB_END (bb));
2097 : : orig_insn = next)
2098 : : {
2099 : 166385993 : next = NEXT_INSN (orig_insn);
2100 : :
2101 : 166385993 : if (!INSN_P (orig_insn))
2102 : 43100236 : continue;
2103 : :
2104 : 123285757 : ivts_templ.insn = orig_insn;
2105 : 123285757 : if (opt_info->insns_to_split)
2106 : : {
2107 : 123285757 : maybe_strip_eq_note_for_split_iv (opt_info, orig_insn);
2108 : :
2109 : 246571514 : ivts = (struct iv_to_split *)
2110 : 123285757 : opt_info->insns_to_split->find (&ivts_templ);
2111 : 123285757 : if (ivts)
2112 : : {
2113 : 60585 : if (!delta)
2114 : 60585 : insert_base_initialization (ivts, orig_insn);
2115 : 60585 : split_iv (ivts, orig_insn, delta);
2116 : 60585 : continue;
2117 : : }
2118 : : }
2119 : :
2120 : : }
2121 : : }
2122 : : }
2123 : :
2124 : : /* Release OPT_INFO. */
2125 : :
2126 : : static void
2127 : 48010 : free_opt_info (struct opt_info *opt_info)
2128 : : {
2129 : 48010 : delete opt_info->insns_to_split;
2130 : 48010 : opt_info->insns_to_split = NULL;
2131 : 48010 : if (opt_info->insns_with_var_to_expand)
2132 : : {
2133 : 6 : struct var_to_expand *ves;
2134 : :
2135 : 9 : for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2136 : 3 : ves->var_expansions.release ();
2137 : 6 : delete opt_info->insns_with_var_to_expand;
2138 : 6 : opt_info->insns_with_var_to_expand = NULL;
2139 : : }
2140 : 48010 : free (opt_info);
2141 : 48010 : }
|