1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2022 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
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 3, or (at your option) any
9 later version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY 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 "tree.h"
25 #include "gimple.h"
26 #include "tree-pass.h"
27 #include "memmodel.h"
28 #include "tm_p.h"
29 #include "fold-const.h"
30 #include "gimple-iterator.h"
31 #include "tree-ssa-loop-ivopts.h"
32 #include "tree-ssa-loop-manip.h"
33 #include "tree-ssa-loop-niter.h"
34 #include "tree-ssa-loop.h"
35 #include "cfgloop.h"
36 #include "tree-inline.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "omp-general.h"
40 #include "diagnostic-core.h"
41 #include "stringpool.h"
42 #include "attribs.h"
43
44
45 /* A pass making sure loops are fixed up. */
46
47 namespace {
48
49 const pass_data pass_data_fix_loops =
50 {
51 GIMPLE_PASS, /* type */
52 "fix_loops", /* name */
53 OPTGROUP_LOOP, /* optinfo_flags */
54 TV_TREE_LOOP, /* tv_id */
55 PROP_cfg, /* properties_required */
56 0, /* properties_provided */
57 0, /* properties_destroyed */
58 0, /* todo_flags_start */
59 0, /* todo_flags_finish */
60 };
61
62 class pass_fix_loops : public gimple_opt_pass
63 {
64 public:
pass_fix_loops(gcc::context * ctxt)65 pass_fix_loops (gcc::context *ctxt)
66 : gimple_opt_pass (pass_data_fix_loops, ctxt)
67 {}
68
69 /* opt_pass methods: */
gate(function *)70 virtual bool gate (function *) { return flag_tree_loop_optimize; }
71
72 virtual unsigned int execute (function *fn);
73 }; // class pass_fix_loops
74
75 unsigned int
execute(function *)76 pass_fix_loops::execute (function *)
77 {
78 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
79 {
80 calculate_dominance_info (CDI_DOMINATORS);
81 fix_loop_structure (NULL);
82 }
83 return 0;
84 }
85
86 } // anon namespace
87
88 gimple_opt_pass *
make_pass_fix_loops(gcc::context * ctxt)89 make_pass_fix_loops (gcc::context *ctxt)
90 {
91 return new pass_fix_loops (ctxt);
92 }
93
94
95 /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
96 but we also avoid running it when the IL doesn't contain any loop. */
97
98 static bool
gate_loop(function * fn)99 gate_loop (function *fn)
100 {
101 if (!flag_tree_loop_optimize)
102 return false;
103
104 /* For -fdump-passes which runs before loop discovery print the
105 state of -ftree-loop-optimize. */
106 if (!loops_for_fn (fn))
107 return true;
108
109 return number_of_loops (fn) > 1;
110 }
111
112 /* The loop superpass. */
113
114 namespace {
115
116 const pass_data pass_data_tree_loop =
117 {
118 GIMPLE_PASS, /* type */
119 "loop", /* name */
120 OPTGROUP_LOOP, /* optinfo_flags */
121 TV_TREE_LOOP, /* tv_id */
122 PROP_cfg, /* properties_required */
123 0, /* properties_provided */
124 0, /* properties_destroyed */
125 0, /* todo_flags_start */
126 0, /* todo_flags_finish */
127 };
128
129 class pass_tree_loop : public gimple_opt_pass
130 {
131 public:
pass_tree_loop(gcc::context * ctxt)132 pass_tree_loop (gcc::context *ctxt)
133 : gimple_opt_pass (pass_data_tree_loop, ctxt)
134 {}
135
136 /* opt_pass methods: */
gate(function * fn)137 virtual bool gate (function *fn) { return gate_loop (fn); }
138
139 }; // class pass_tree_loop
140
141 } // anon namespace
142
143 gimple_opt_pass *
make_pass_tree_loop(gcc::context * ctxt)144 make_pass_tree_loop (gcc::context *ctxt)
145 {
146 return new pass_tree_loop (ctxt);
147 }
148
149 /* Gate for oacc kernels pass group. */
150
151 static bool
gate_oacc_kernels(function * fn)152 gate_oacc_kernels (function *fn)
153 {
154 if (!flag_openacc)
155 return false;
156
157 if (!lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn->decl)))
158 return false;
159
160 for (auto loop : loops_list (cfun, 0))
161 if (loop->in_oacc_kernels_region)
162 return true;
163
164 return false;
165 }
166
167 /* The oacc kernels superpass. */
168
169 namespace {
170
171 const pass_data pass_data_oacc_kernels =
172 {
173 GIMPLE_PASS, /* type */
174 "oacc_kernels", /* name */
175 OPTGROUP_LOOP, /* optinfo_flags */
176 TV_TREE_LOOP, /* tv_id */
177 PROP_cfg, /* properties_required */
178 0, /* properties_provided */
179 0, /* properties_destroyed */
180 0, /* todo_flags_start */
181 0, /* todo_flags_finish */
182 };
183
184 class pass_oacc_kernels : public gimple_opt_pass
185 {
186 public:
pass_oacc_kernels(gcc::context * ctxt)187 pass_oacc_kernels (gcc::context *ctxt)
188 : gimple_opt_pass (pass_data_oacc_kernels, ctxt)
189 {}
190
191 /* opt_pass methods: */
gate(function * fn)192 virtual bool gate (function *fn) { return gate_oacc_kernels (fn); }
193
194 }; // class pass_oacc_kernels
195
196 } // anon namespace
197
198 gimple_opt_pass *
make_pass_oacc_kernels(gcc::context * ctxt)199 make_pass_oacc_kernels (gcc::context *ctxt)
200 {
201 return new pass_oacc_kernels (ctxt);
202 }
203
204 /* The ipa oacc superpass. */
205
206 namespace {
207
208 const pass_data pass_data_ipa_oacc =
209 {
210 SIMPLE_IPA_PASS, /* type */
211 "ipa_oacc", /* name */
212 OPTGROUP_LOOP, /* optinfo_flags */
213 TV_TREE_LOOP, /* tv_id */
214 PROP_cfg, /* properties_required */
215 0, /* properties_provided */
216 0, /* properties_destroyed */
217 0, /* todo_flags_start */
218 0, /* todo_flags_finish */
219 };
220
221 class pass_ipa_oacc : public simple_ipa_opt_pass
222 {
223 public:
pass_ipa_oacc(gcc::context * ctxt)224 pass_ipa_oacc (gcc::context *ctxt)
225 : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt)
226 {}
227
228 /* opt_pass methods: */
gate(function *)229 virtual bool gate (function *)
230 {
231 return (optimize
232 && flag_openacc
233 /* Don't bother doing anything if the program has errors. */
234 && !seen_error ());
235 }
236
237 }; // class pass_ipa_oacc
238
239 } // anon namespace
240
241 simple_ipa_opt_pass *
make_pass_ipa_oacc(gcc::context * ctxt)242 make_pass_ipa_oacc (gcc::context *ctxt)
243 {
244 return new pass_ipa_oacc (ctxt);
245 }
246
247 /* The ipa oacc kernels pass. */
248
249 namespace {
250
251 const pass_data pass_data_ipa_oacc_kernels =
252 {
253 SIMPLE_IPA_PASS, /* type */
254 "ipa_oacc_kernels", /* name */
255 OPTGROUP_LOOP, /* optinfo_flags */
256 TV_TREE_LOOP, /* tv_id */
257 PROP_cfg, /* properties_required */
258 0, /* properties_provided */
259 0, /* properties_destroyed */
260 0, /* todo_flags_start */
261 0, /* todo_flags_finish */
262 };
263
264 class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
265 {
266 public:
pass_ipa_oacc_kernels(gcc::context * ctxt)267 pass_ipa_oacc_kernels (gcc::context *ctxt)
268 : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt)
269 {}
270
271 }; // class pass_ipa_oacc_kernels
272
273 } // anon namespace
274
275 simple_ipa_opt_pass *
make_pass_ipa_oacc_kernels(gcc::context * ctxt)276 make_pass_ipa_oacc_kernels (gcc::context *ctxt)
277 {
278 return new pass_ipa_oacc_kernels (ctxt);
279 }
280
281 /* The no-loop superpass. */
282
283 namespace {
284
285 const pass_data pass_data_tree_no_loop =
286 {
287 GIMPLE_PASS, /* type */
288 "no_loop", /* name */
289 OPTGROUP_NONE, /* optinfo_flags */
290 TV_TREE_NOLOOP, /* tv_id */
291 PROP_cfg, /* properties_required */
292 0, /* properties_provided */
293 0, /* properties_destroyed */
294 0, /* todo_flags_start */
295 0, /* todo_flags_finish */
296 };
297
298 class pass_tree_no_loop : public gimple_opt_pass
299 {
300 public:
pass_tree_no_loop(gcc::context * ctxt)301 pass_tree_no_loop (gcc::context *ctxt)
302 : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
303 {}
304
305 /* opt_pass methods: */
gate(function * fn)306 virtual bool gate (function *fn) { return !gate_loop (fn); }
307
308 }; // class pass_tree_no_loop
309
310 } // anon namespace
311
312 gimple_opt_pass *
make_pass_tree_no_loop(gcc::context * ctxt)313 make_pass_tree_no_loop (gcc::context *ctxt)
314 {
315 return new pass_tree_no_loop (ctxt);
316 }
317
318
319 /* Loop optimizer initialization. */
320
321 namespace {
322
323 const pass_data pass_data_tree_loop_init =
324 {
325 GIMPLE_PASS, /* type */
326 "loopinit", /* name */
327 OPTGROUP_LOOP, /* optinfo_flags */
328 TV_NONE, /* tv_id */
329 PROP_cfg, /* properties_required */
330 0, /* properties_provided */
331 0, /* properties_destroyed */
332 TODO_update_address_taken, /* todo_flags_start */
333 0, /* todo_flags_finish */
334 };
335
336 class pass_tree_loop_init : public gimple_opt_pass
337 {
338 public:
pass_tree_loop_init(gcc::context * ctxt)339 pass_tree_loop_init (gcc::context *ctxt)
340 : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
341 {}
342
343 /* opt_pass methods: */
344 virtual unsigned int execute (function *);
345
346 }; // class pass_tree_loop_init
347
348 unsigned int
execute(function * fun ATTRIBUTE_UNUSED)349 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
350 {
351 /* When processing a loop in the loop pipeline, we should be able to assert
352 that:
353 (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
354 | LOOP_CLOSED_SSA)
355 && scev_initialized_p ())
356 */
357 loop_optimizer_init (LOOPS_NORMAL
358 | LOOPS_HAVE_RECORDED_EXITS);
359 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
360 scev_initialize ();
361
362 return 0;
363 }
364
365 } // anon namespace
366
367 gimple_opt_pass *
make_pass_tree_loop_init(gcc::context * ctxt)368 make_pass_tree_loop_init (gcc::context *ctxt)
369 {
370 return new pass_tree_loop_init (ctxt);
371 }
372
373 /* Propagation of constants using scev. */
374
375 namespace {
376
377 const pass_data pass_data_scev_cprop =
378 {
379 GIMPLE_PASS, /* type */
380 "sccp", /* name */
381 OPTGROUP_LOOP, /* optinfo_flags */
382 TV_SCEV_CONST, /* tv_id */
383 ( PROP_cfg | PROP_ssa ), /* properties_required */
384 0, /* properties_provided */
385 0, /* properties_destroyed */
386 0, /* todo_flags_start */
387 0, /* todo_flags_finish */
388 };
389
390 class pass_scev_cprop : public gimple_opt_pass
391 {
392 public:
pass_scev_cprop(gcc::context * ctxt)393 pass_scev_cprop (gcc::context *ctxt)
394 : gimple_opt_pass (pass_data_scev_cprop, ctxt)
395 {}
396
397 /* opt_pass methods: */
gate(function *)398 virtual bool gate (function *) { return flag_tree_scev_cprop; }
399 virtual unsigned int execute (function *);
400
401 }; // class pass_scev_cprop
402
403 unsigned
execute(function *)404 pass_scev_cprop::execute (function *)
405 {
406 bool any = false;
407
408 /* Perform final value replacement in loops, in case the replacement
409 expressions are cheap. */
410 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
411 any |= final_value_replacement_loop (loop);
412
413 return any ? TODO_cleanup_cfg | TODO_update_ssa_only_virtuals : 0;
414 }
415
416 } // anon namespace
417
418 gimple_opt_pass *
make_pass_scev_cprop(gcc::context * ctxt)419 make_pass_scev_cprop (gcc::context *ctxt)
420 {
421 return new pass_scev_cprop (ctxt);
422 }
423
424 /* Induction variable optimizations. */
425
426 namespace {
427
428 const pass_data pass_data_iv_optimize =
429 {
430 GIMPLE_PASS, /* type */
431 "ivopts", /* name */
432 OPTGROUP_LOOP, /* optinfo_flags */
433 TV_TREE_LOOP_IVOPTS, /* tv_id */
434 ( PROP_cfg | PROP_ssa ), /* properties_required */
435 0, /* properties_provided */
436 0, /* properties_destroyed */
437 0, /* todo_flags_start */
438 TODO_update_ssa, /* todo_flags_finish */
439 };
440
441 class pass_iv_optimize : public gimple_opt_pass
442 {
443 public:
pass_iv_optimize(gcc::context * ctxt)444 pass_iv_optimize (gcc::context *ctxt)
445 : gimple_opt_pass (pass_data_iv_optimize, ctxt)
446 {}
447
448 /* opt_pass methods: */
gate(function *)449 virtual bool gate (function *) { return flag_ivopts != 0; }
450 virtual unsigned int execute (function *);
451
452 }; // class pass_iv_optimize
453
454 unsigned int
execute(function * fun)455 pass_iv_optimize::execute (function *fun)
456 {
457 if (number_of_loops (fun) <= 1)
458 return 0;
459
460 tree_ssa_iv_optimize ();
461 return 0;
462 }
463
464 } // anon namespace
465
466 gimple_opt_pass *
make_pass_iv_optimize(gcc::context * ctxt)467 make_pass_iv_optimize (gcc::context *ctxt)
468 {
469 return new pass_iv_optimize (ctxt);
470 }
471
472 /* Loop optimizer finalization. */
473
474 static unsigned int
tree_ssa_loop_done(void)475 tree_ssa_loop_done (void)
476 {
477 free_numbers_of_iterations_estimates (cfun);
478 scev_finalize ();
479 loop_optimizer_finalize (cfun, true);
480 return 0;
481 }
482
483 namespace {
484
485 const pass_data pass_data_tree_loop_done =
486 {
487 GIMPLE_PASS, /* type */
488 "loopdone", /* name */
489 OPTGROUP_LOOP, /* optinfo_flags */
490 TV_NONE, /* tv_id */
491 PROP_cfg, /* properties_required */
492 PROP_loop_opts_done, /* properties_provided */
493 0, /* properties_destroyed */
494 0, /* todo_flags_start */
495 TODO_cleanup_cfg, /* todo_flags_finish */
496 };
497
498 class pass_tree_loop_done : public gimple_opt_pass
499 {
500 public:
pass_tree_loop_done(gcc::context * ctxt)501 pass_tree_loop_done (gcc::context *ctxt)
502 : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
503 {}
504
505 /* opt_pass methods: */
execute(function *)506 virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
507
508 }; // class pass_tree_loop_done
509
510 } // anon namespace
511
512 gimple_opt_pass *
make_pass_tree_loop_done(gcc::context * ctxt)513 make_pass_tree_loop_done (gcc::context *ctxt)
514 {
515 return new pass_tree_loop_done (ctxt);
516 }
517
518 /* Calls CBCK for each index in memory reference ADDR_P. There are two
519 kinds situations handled; in each of these cases, the memory reference
520 and DATA are passed to the callback:
521
522 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
523 pass the pointer to the index to the callback.
524
525 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
526 pointer to addr to the callback.
527
528 If the callback returns false, the whole search stops and false is returned.
529 Otherwise the function returns true after traversing through the whole
530 reference *ADDR_P. */
531
532 bool
for_each_index(tree * addr_p,bool (* cbck)(tree,tree *,void *),void * data)533 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
534 {
535 tree *nxt, *idx;
536
537 for (; ; addr_p = nxt)
538 {
539 switch (TREE_CODE (*addr_p))
540 {
541 case SSA_NAME:
542 return cbck (*addr_p, addr_p, data);
543
544 case MEM_REF:
545 nxt = &TREE_OPERAND (*addr_p, 0);
546 return cbck (*addr_p, nxt, data);
547
548 case BIT_FIELD_REF:
549 case VIEW_CONVERT_EXPR:
550 case REALPART_EXPR:
551 case IMAGPART_EXPR:
552 nxt = &TREE_OPERAND (*addr_p, 0);
553 break;
554
555 case COMPONENT_REF:
556 /* If the component has varying offset, it behaves like index
557 as well. */
558 idx = &TREE_OPERAND (*addr_p, 2);
559 if (*idx
560 && !cbck (*addr_p, idx, data))
561 return false;
562
563 nxt = &TREE_OPERAND (*addr_p, 0);
564 break;
565
566 case ARRAY_REF:
567 case ARRAY_RANGE_REF:
568 nxt = &TREE_OPERAND (*addr_p, 0);
569 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
570 return false;
571 break;
572
573 case CONSTRUCTOR:
574 return true;
575
576 case ADDR_EXPR:
577 gcc_assert (is_gimple_min_invariant (*addr_p));
578 return true;
579
580 case TARGET_MEM_REF:
581 idx = &TMR_BASE (*addr_p);
582 if (*idx
583 && !cbck (*addr_p, idx, data))
584 return false;
585 idx = &TMR_INDEX (*addr_p);
586 if (*idx
587 && !cbck (*addr_p, idx, data))
588 return false;
589 idx = &TMR_INDEX2 (*addr_p);
590 if (*idx
591 && !cbck (*addr_p, idx, data))
592 return false;
593 return true;
594
595 default:
596 if (DECL_P (*addr_p)
597 || CONSTANT_CLASS_P (*addr_p))
598 return true;
599 gcc_unreachable ();
600 }
601 }
602 }
603
604
605 /* The name and the length of the currently generated variable
606 for lsm. */
607 #define MAX_LSM_NAME_LENGTH 40
608 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
609 static int lsm_tmp_name_length;
610
611 /* Adds S to lsm_tmp_name. */
612
613 static void
lsm_tmp_name_add(const char * s)614 lsm_tmp_name_add (const char *s)
615 {
616 int l = strlen (s) + lsm_tmp_name_length;
617 if (l > MAX_LSM_NAME_LENGTH)
618 return;
619
620 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
621 lsm_tmp_name_length = l;
622 }
623
624 /* Stores the name for temporary variable that replaces REF to
625 lsm_tmp_name. */
626
627 static void
gen_lsm_tmp_name(tree ref)628 gen_lsm_tmp_name (tree ref)
629 {
630 const char *name;
631
632 switch (TREE_CODE (ref))
633 {
634 case MEM_REF:
635 case TARGET_MEM_REF:
636 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
637 lsm_tmp_name_add ("_");
638 break;
639
640 case ADDR_EXPR:
641 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
642 break;
643
644 case BIT_FIELD_REF:
645 case VIEW_CONVERT_EXPR:
646 case ARRAY_RANGE_REF:
647 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
648 break;
649
650 case REALPART_EXPR:
651 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
652 lsm_tmp_name_add ("_RE");
653 break;
654
655 case IMAGPART_EXPR:
656 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
657 lsm_tmp_name_add ("_IM");
658 break;
659
660 case COMPONENT_REF:
661 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
662 lsm_tmp_name_add ("_");
663 name = get_name (TREE_OPERAND (ref, 1));
664 if (!name)
665 name = "F";
666 lsm_tmp_name_add (name);
667 break;
668
669 case ARRAY_REF:
670 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
671 lsm_tmp_name_add ("_I");
672 break;
673
674 case SSA_NAME:
675 case VAR_DECL:
676 case PARM_DECL:
677 case FUNCTION_DECL:
678 case LABEL_DECL:
679 name = get_name (ref);
680 if (!name)
681 name = "D";
682 lsm_tmp_name_add (name);
683 break;
684
685 case STRING_CST:
686 lsm_tmp_name_add ("S");
687 break;
688
689 case RESULT_DECL:
690 lsm_tmp_name_add ("R");
691 break;
692
693 case INTEGER_CST:
694 default:
695 /* Nothing. */
696 break;
697 }
698 }
699
700 /* Determines name for temporary variable that replaces REF.
701 The name is accumulated into the lsm_tmp_name variable.
702 N is added to the name of the temporary. */
703
704 char *
get_lsm_tmp_name(tree ref,unsigned n,const char * suffix)705 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
706 {
707 char ns[2];
708
709 lsm_tmp_name_length = 0;
710 gen_lsm_tmp_name (ref);
711 lsm_tmp_name_add ("_lsm");
712 if (n < 10)
713 {
714 ns[0] = '0' + n;
715 ns[1] = 0;
716 lsm_tmp_name_add (ns);
717 }
718 if (suffix != NULL)
719 lsm_tmp_name_add (suffix);
720 return lsm_tmp_name;
721 }
722
723 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
724
725 unsigned
tree_num_loop_insns(class loop * loop,eni_weights * weights)726 tree_num_loop_insns (class loop *loop, eni_weights *weights)
727 {
728 basic_block *body = get_loop_body (loop);
729 gimple_stmt_iterator gsi;
730 unsigned size = 0, i;
731
732 for (i = 0; i < loop->num_nodes; i++)
733 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
734 size += estimate_num_insns (gsi_stmt (gsi), weights);
735 free (body);
736
737 return size;
738 }
739
740
741
742