Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop.c
blob1bbf2f1fb2c8dde790906813a7908bd7deb13b3f
1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
45 /* A pass making sure loops are fixed up. */
47 namespace {
49 const pass_data pass_data_fix_loops =
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 */
62 class pass_fix_loops : public gimple_opt_pass
64 public:
65 pass_fix_loops (gcc::context *ctxt)
66 : gimple_opt_pass (pass_data_fix_loops, ctxt)
69 /* opt_pass methods: */
70 virtual bool gate (function *) { return flag_tree_loop_optimize; }
72 virtual unsigned int execute (function *fn);
73 }; // class pass_fix_loops
75 unsigned int
76 pass_fix_loops::execute (function *)
78 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
80 calculate_dominance_info (CDI_DOMINATORS);
81 fix_loop_structure (NULL);
83 return 0;
86 } // anon namespace
88 gimple_opt_pass *
89 make_pass_fix_loops (gcc::context *ctxt)
91 return new pass_fix_loops (ctxt);
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. */
98 static bool
99 gate_loop (function *fn)
101 if (!flag_tree_loop_optimize)
102 return false;
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;
109 return number_of_loops (fn) > 1;
112 /* The loop superpass. */
114 namespace {
116 const pass_data pass_data_tree_loop =
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 */
129 class pass_tree_loop : public gimple_opt_pass
131 public:
132 pass_tree_loop (gcc::context *ctxt)
133 : gimple_opt_pass (pass_data_tree_loop, ctxt)
136 /* opt_pass methods: */
137 virtual bool gate (function *fn) { return gate_loop (fn); }
139 }; // class pass_tree_loop
141 } // anon namespace
143 gimple_opt_pass *
144 make_pass_tree_loop (gcc::context *ctxt)
146 return new pass_tree_loop (ctxt);
149 /* Gate for oacc kernels pass group. */
151 static bool
152 gate_oacc_kernels (function *fn)
154 if (!flag_openacc)
155 return false;
157 if (!lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn->decl)))
158 return false;
160 for (auto loop : loops_list (cfun, 0))
161 if (loop->in_oacc_kernels_region)
162 return true;
164 return false;
167 /* The oacc kernels superpass. */
169 namespace {
171 const pass_data pass_data_oacc_kernels =
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 */
184 class pass_oacc_kernels : public gimple_opt_pass
186 public:
187 pass_oacc_kernels (gcc::context *ctxt)
188 : gimple_opt_pass (pass_data_oacc_kernels, ctxt)
191 /* opt_pass methods: */
192 virtual bool gate (function *fn) { return gate_oacc_kernels (fn); }
194 }; // class pass_oacc_kernels
196 } // anon namespace
198 gimple_opt_pass *
199 make_pass_oacc_kernels (gcc::context *ctxt)
201 return new pass_oacc_kernels (ctxt);
204 /* The ipa oacc superpass. */
206 namespace {
208 const pass_data pass_data_ipa_oacc =
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 */
221 class pass_ipa_oacc : public simple_ipa_opt_pass
223 public:
224 pass_ipa_oacc (gcc::context *ctxt)
225 : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt)
228 /* opt_pass methods: */
229 virtual bool gate (function *)
231 return (optimize
232 && flag_openacc
233 /* Don't bother doing anything if the program has errors. */
234 && !seen_error ());
237 }; // class pass_ipa_oacc
239 } // anon namespace
241 simple_ipa_opt_pass *
242 make_pass_ipa_oacc (gcc::context *ctxt)
244 return new pass_ipa_oacc (ctxt);
247 /* The ipa oacc kernels pass. */
249 namespace {
251 const pass_data pass_data_ipa_oacc_kernels =
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 */
264 class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
266 public:
267 pass_ipa_oacc_kernels (gcc::context *ctxt)
268 : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt)
271 }; // class pass_ipa_oacc_kernels
273 } // anon namespace
275 simple_ipa_opt_pass *
276 make_pass_ipa_oacc_kernels (gcc::context *ctxt)
278 return new pass_ipa_oacc_kernels (ctxt);
281 /* The no-loop superpass. */
283 namespace {
285 const pass_data pass_data_tree_no_loop =
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 */
298 class pass_tree_no_loop : public gimple_opt_pass
300 public:
301 pass_tree_no_loop (gcc::context *ctxt)
302 : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
305 /* opt_pass methods: */
306 virtual bool gate (function *fn) { return !gate_loop (fn); }
308 }; // class pass_tree_no_loop
310 } // anon namespace
312 gimple_opt_pass *
313 make_pass_tree_no_loop (gcc::context *ctxt)
315 return new pass_tree_no_loop (ctxt);
319 /* Loop optimizer initialization. */
321 namespace {
323 const pass_data pass_data_tree_loop_init =
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 */
336 class pass_tree_loop_init : public gimple_opt_pass
338 public:
339 pass_tree_loop_init (gcc::context *ctxt)
340 : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
343 /* opt_pass methods: */
344 virtual unsigned int execute (function *);
346 }; // class pass_tree_loop_init
348 unsigned int
349 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
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 ())
357 loop_optimizer_init (LOOPS_NORMAL
358 | LOOPS_HAVE_RECORDED_EXITS);
359 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
360 scev_initialize ();
362 return 0;
365 } // anon namespace
367 gimple_opt_pass *
368 make_pass_tree_loop_init (gcc::context *ctxt)
370 return new pass_tree_loop_init (ctxt);
373 /* Loop autovectorization. */
375 namespace {
377 const pass_data pass_data_vectorize =
379 GIMPLE_PASS, /* type */
380 "vect", /* name */
381 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
382 TV_TREE_VECTORIZATION, /* 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 */
390 class pass_vectorize : public gimple_opt_pass
392 public:
393 pass_vectorize (gcc::context *ctxt)
394 : gimple_opt_pass (pass_data_vectorize, ctxt)
397 /* opt_pass methods: */
398 virtual bool gate (function *fun)
400 return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
403 virtual unsigned int execute (function *);
405 }; // class pass_vectorize
407 unsigned int
408 pass_vectorize::execute (function *fun)
410 if (number_of_loops (fun) <= 1)
411 return 0;
413 return vectorize_loops ();
416 } // anon namespace
418 gimple_opt_pass *
419 make_pass_vectorize (gcc::context *ctxt)
421 return new pass_vectorize (ctxt);
424 /* Propagation of constants using scev. */
426 namespace {
428 const pass_data pass_data_scev_cprop =
430 GIMPLE_PASS, /* type */
431 "sccp", /* name */
432 OPTGROUP_LOOP, /* optinfo_flags */
433 TV_SCEV_CONST, /* tv_id */
434 ( PROP_cfg | PROP_ssa ), /* properties_required */
435 0, /* properties_provided */
436 0, /* properties_destroyed */
437 0, /* todo_flags_start */
438 0, /* todo_flags_finish */
441 class pass_scev_cprop : public gimple_opt_pass
443 public:
444 pass_scev_cprop (gcc::context *ctxt)
445 : gimple_opt_pass (pass_data_scev_cprop, ctxt)
448 /* opt_pass methods: */
449 virtual bool gate (function *) { return flag_tree_scev_cprop; }
450 virtual unsigned int execute (function *);
452 }; // class pass_scev_cprop
454 unsigned
455 pass_scev_cprop::execute (function *)
457 bool any = false;
459 /* Perform final value replacement in loops, in case the replacement
460 expressions are cheap. */
461 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
462 any |= final_value_replacement_loop (loop);
464 return any ? TODO_cleanup_cfg | TODO_update_ssa_only_virtuals : 0;
467 } // anon namespace
469 gimple_opt_pass *
470 make_pass_scev_cprop (gcc::context *ctxt)
472 return new pass_scev_cprop (ctxt);
475 /* Induction variable optimizations. */
477 namespace {
479 const pass_data pass_data_iv_optimize =
481 GIMPLE_PASS, /* type */
482 "ivopts", /* name */
483 OPTGROUP_LOOP, /* optinfo_flags */
484 TV_TREE_LOOP_IVOPTS, /* tv_id */
485 ( PROP_cfg | PROP_ssa ), /* properties_required */
486 0, /* properties_provided */
487 0, /* properties_destroyed */
488 0, /* todo_flags_start */
489 TODO_update_ssa, /* todo_flags_finish */
492 class pass_iv_optimize : public gimple_opt_pass
494 public:
495 pass_iv_optimize (gcc::context *ctxt)
496 : gimple_opt_pass (pass_data_iv_optimize, ctxt)
499 /* opt_pass methods: */
500 virtual bool gate (function *) { return flag_ivopts != 0; }
501 virtual unsigned int execute (function *);
503 }; // class pass_iv_optimize
505 unsigned int
506 pass_iv_optimize::execute (function *fun)
508 if (number_of_loops (fun) <= 1)
509 return 0;
511 tree_ssa_iv_optimize ();
512 return 0;
515 } // anon namespace
517 gimple_opt_pass *
518 make_pass_iv_optimize (gcc::context *ctxt)
520 return new pass_iv_optimize (ctxt);
523 /* Loop optimizer finalization. */
525 static unsigned int
526 tree_ssa_loop_done (void)
528 free_numbers_of_iterations_estimates (cfun);
529 scev_finalize ();
530 loop_optimizer_finalize (cfun, true);
531 return 0;
534 namespace {
536 const pass_data pass_data_tree_loop_done =
538 GIMPLE_PASS, /* type */
539 "loopdone", /* name */
540 OPTGROUP_LOOP, /* optinfo_flags */
541 TV_NONE, /* tv_id */
542 PROP_cfg, /* properties_required */
543 PROP_loop_opts_done, /* properties_provided */
544 0, /* properties_destroyed */
545 0, /* todo_flags_start */
546 TODO_cleanup_cfg, /* todo_flags_finish */
549 class pass_tree_loop_done : public gimple_opt_pass
551 public:
552 pass_tree_loop_done (gcc::context *ctxt)
553 : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
556 /* opt_pass methods: */
557 virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
559 }; // class pass_tree_loop_done
561 } // anon namespace
563 gimple_opt_pass *
564 make_pass_tree_loop_done (gcc::context *ctxt)
566 return new pass_tree_loop_done (ctxt);
569 /* Calls CBCK for each index in memory reference ADDR_P. There are two
570 kinds situations handled; in each of these cases, the memory reference
571 and DATA are passed to the callback:
573 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
574 pass the pointer to the index to the callback.
576 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
577 pointer to addr to the callback.
579 If the callback returns false, the whole search stops and false is returned.
580 Otherwise the function returns true after traversing through the whole
581 reference *ADDR_P. */
583 bool
584 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
586 tree *nxt, *idx;
588 for (; ; addr_p = nxt)
590 switch (TREE_CODE (*addr_p))
592 case SSA_NAME:
593 return cbck (*addr_p, addr_p, data);
595 case MEM_REF:
596 nxt = &TREE_OPERAND (*addr_p, 0);
597 return cbck (*addr_p, nxt, data);
599 case BIT_FIELD_REF:
600 case VIEW_CONVERT_EXPR:
601 case REALPART_EXPR:
602 case IMAGPART_EXPR:
603 nxt = &TREE_OPERAND (*addr_p, 0);
604 break;
606 case COMPONENT_REF:
607 /* If the component has varying offset, it behaves like index
608 as well. */
609 idx = &TREE_OPERAND (*addr_p, 2);
610 if (*idx
611 && !cbck (*addr_p, idx, data))
612 return false;
614 nxt = &TREE_OPERAND (*addr_p, 0);
615 break;
617 case ARRAY_REF:
618 case ARRAY_RANGE_REF:
619 nxt = &TREE_OPERAND (*addr_p, 0);
620 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
621 return false;
622 break;
624 case CONSTRUCTOR:
625 return true;
627 case ADDR_EXPR:
628 gcc_assert (is_gimple_min_invariant (*addr_p));
629 return true;
631 case TARGET_MEM_REF:
632 idx = &TMR_BASE (*addr_p);
633 if (*idx
634 && !cbck (*addr_p, idx, data))
635 return false;
636 idx = &TMR_INDEX (*addr_p);
637 if (*idx
638 && !cbck (*addr_p, idx, data))
639 return false;
640 idx = &TMR_INDEX2 (*addr_p);
641 if (*idx
642 && !cbck (*addr_p, idx, data))
643 return false;
644 return true;
646 default:
647 if (DECL_P (*addr_p)
648 || CONSTANT_CLASS_P (*addr_p))
649 return true;
650 gcc_unreachable ();
656 /* The name and the length of the currently generated variable
657 for lsm. */
658 #define MAX_LSM_NAME_LENGTH 40
659 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
660 static int lsm_tmp_name_length;
662 /* Adds S to lsm_tmp_name. */
664 static void
665 lsm_tmp_name_add (const char *s)
667 int l = strlen (s) + lsm_tmp_name_length;
668 if (l > MAX_LSM_NAME_LENGTH)
669 return;
671 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
672 lsm_tmp_name_length = l;
675 /* Stores the name for temporary variable that replaces REF to
676 lsm_tmp_name. */
678 static void
679 gen_lsm_tmp_name (tree ref)
681 const char *name;
683 switch (TREE_CODE (ref))
685 case MEM_REF:
686 case TARGET_MEM_REF:
687 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
688 lsm_tmp_name_add ("_");
689 break;
691 case ADDR_EXPR:
692 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
693 break;
695 case BIT_FIELD_REF:
696 case VIEW_CONVERT_EXPR:
697 case ARRAY_RANGE_REF:
698 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
699 break;
701 case REALPART_EXPR:
702 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
703 lsm_tmp_name_add ("_RE");
704 break;
706 case IMAGPART_EXPR:
707 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
708 lsm_tmp_name_add ("_IM");
709 break;
711 case COMPONENT_REF:
712 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
713 lsm_tmp_name_add ("_");
714 name = get_name (TREE_OPERAND (ref, 1));
715 if (!name)
716 name = "F";
717 lsm_tmp_name_add (name);
718 break;
720 case ARRAY_REF:
721 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
722 lsm_tmp_name_add ("_I");
723 break;
725 case SSA_NAME:
726 case VAR_DECL:
727 case PARM_DECL:
728 case FUNCTION_DECL:
729 case LABEL_DECL:
730 name = get_name (ref);
731 if (!name)
732 name = "D";
733 lsm_tmp_name_add (name);
734 break;
736 case STRING_CST:
737 lsm_tmp_name_add ("S");
738 break;
740 case RESULT_DECL:
741 lsm_tmp_name_add ("R");
742 break;
744 case INTEGER_CST:
745 default:
746 /* Nothing. */
747 break;
751 /* Determines name for temporary variable that replaces REF.
752 The name is accumulated into the lsm_tmp_name variable.
753 N is added to the name of the temporary. */
755 char *
756 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
758 char ns[2];
760 lsm_tmp_name_length = 0;
761 gen_lsm_tmp_name (ref);
762 lsm_tmp_name_add ("_lsm");
763 if (n < 10)
765 ns[0] = '0' + n;
766 ns[1] = 0;
767 lsm_tmp_name_add (ns);
769 if (suffix != NULL)
770 lsm_tmp_name_add (suffix);
771 return lsm_tmp_name;
774 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
776 unsigned
777 tree_num_loop_insns (class loop *loop, eni_weights *weights)
779 basic_block *body = get_loop_body (loop);
780 gimple_stmt_iterator gsi;
781 unsigned size = 0, i;
783 for (i = 0; i < loop->num_nodes; i++)
784 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
785 size += estimate_num_insns (gsi_stmt (gsi), weights);
786 free (body);
788 return size;