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

source code of gcc/tree-ssa-loop.cc