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