Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop.c
blob8b25b41dbec2a41f96d23e5283c9081a6fd9aea9
1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2017 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"
43 /* A pass making sure loops are fixed up. */
45 namespace {
47 const pass_data pass_data_fix_loops =
49 GIMPLE_PASS, /* type */
50 "fix_loops", /* name */
51 OPTGROUP_LOOP, /* optinfo_flags */
52 TV_TREE_LOOP, /* tv_id */
53 PROP_cfg, /* properties_required */
54 0, /* properties_provided */
55 0, /* properties_destroyed */
56 0, /* todo_flags_start */
57 0, /* todo_flags_finish */
60 class pass_fix_loops : public gimple_opt_pass
62 public:
63 pass_fix_loops (gcc::context *ctxt)
64 : gimple_opt_pass (pass_data_fix_loops, ctxt)
67 /* opt_pass methods: */
68 virtual bool gate (function *) { return flag_tree_loop_optimize; }
70 virtual unsigned int execute (function *fn);
71 }; // class pass_fix_loops
73 unsigned int
74 pass_fix_loops::execute (function *)
76 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
78 calculate_dominance_info (CDI_DOMINATORS);
79 fix_loop_structure (NULL);
81 return 0;
84 } // anon namespace
86 gimple_opt_pass *
87 make_pass_fix_loops (gcc::context *ctxt)
89 return new pass_fix_loops (ctxt);
93 /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
94 but we also avoid running it when the IL doesn't contain any loop. */
96 static bool
97 gate_loop (function *fn)
99 if (!flag_tree_loop_optimize)
100 return false;
102 /* For -fdump-passes which runs before loop discovery print the
103 state of -ftree-loop-optimize. */
104 if (!loops_for_fn (fn))
105 return true;
107 return number_of_loops (fn) > 1;
110 /* The loop superpass. */
112 namespace {
114 const pass_data pass_data_tree_loop =
116 GIMPLE_PASS, /* type */
117 "loop", /* name */
118 OPTGROUP_LOOP, /* optinfo_flags */
119 TV_TREE_LOOP, /* tv_id */
120 PROP_cfg, /* properties_required */
121 0, /* properties_provided */
122 0, /* properties_destroyed */
123 0, /* todo_flags_start */
124 0, /* todo_flags_finish */
127 class pass_tree_loop : public gimple_opt_pass
129 public:
130 pass_tree_loop (gcc::context *ctxt)
131 : gimple_opt_pass (pass_data_tree_loop, ctxt)
134 /* opt_pass methods: */
135 virtual bool gate (function *fn) { return gate_loop (fn); }
137 }; // class pass_tree_loop
139 } // anon namespace
141 gimple_opt_pass *
142 make_pass_tree_loop (gcc::context *ctxt)
144 return new pass_tree_loop (ctxt);
147 /* Gate for oacc kernels pass group. */
149 static bool
150 gate_oacc_kernels (function *fn)
152 if (!flag_openacc)
153 return false;
155 tree oacc_function_attr = oacc_get_fn_attrib (fn->decl);
156 if (oacc_function_attr == NULL_TREE)
157 return false;
158 if (!oacc_fn_attrib_kernels_p (oacc_function_attr))
159 return false;
161 struct loop *loop;
162 FOR_EACH_LOOP (loop, 0)
163 if (loop->in_oacc_kernels_region)
164 return true;
166 return false;
169 /* The oacc kernels superpass. */
171 namespace {
173 const pass_data pass_data_oacc_kernels =
175 GIMPLE_PASS, /* type */
176 "oacc_kernels", /* name */
177 OPTGROUP_LOOP, /* optinfo_flags */
178 TV_TREE_LOOP, /* tv_id */
179 PROP_cfg, /* properties_required */
180 0, /* properties_provided */
181 0, /* properties_destroyed */
182 0, /* todo_flags_start */
183 0, /* todo_flags_finish */
186 class pass_oacc_kernels : public gimple_opt_pass
188 public:
189 pass_oacc_kernels (gcc::context *ctxt)
190 : gimple_opt_pass (pass_data_oacc_kernels, ctxt)
193 /* opt_pass methods: */
194 virtual bool gate (function *fn) { return gate_oacc_kernels (fn); }
196 }; // class pass_oacc_kernels
198 } // anon namespace
200 gimple_opt_pass *
201 make_pass_oacc_kernels (gcc::context *ctxt)
203 return new pass_oacc_kernels (ctxt);
206 /* The ipa oacc superpass. */
208 namespace {
210 const pass_data pass_data_ipa_oacc =
212 SIMPLE_IPA_PASS, /* type */
213 "ipa_oacc", /* name */
214 OPTGROUP_LOOP, /* optinfo_flags */
215 TV_TREE_LOOP, /* tv_id */
216 PROP_cfg, /* properties_required */
217 0, /* properties_provided */
218 0, /* properties_destroyed */
219 0, /* todo_flags_start */
220 0, /* todo_flags_finish */
223 class pass_ipa_oacc : public simple_ipa_opt_pass
225 public:
226 pass_ipa_oacc (gcc::context *ctxt)
227 : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt)
230 /* opt_pass methods: */
231 virtual bool gate (function *)
233 return (optimize
234 && flag_openacc
235 /* Don't bother doing anything if the program has errors. */
236 && !seen_error ());
239 }; // class pass_ipa_oacc
241 } // anon namespace
243 simple_ipa_opt_pass *
244 make_pass_ipa_oacc (gcc::context *ctxt)
246 return new pass_ipa_oacc (ctxt);
249 /* The ipa oacc kernels pass. */
251 namespace {
253 const pass_data pass_data_ipa_oacc_kernels =
255 SIMPLE_IPA_PASS, /* type */
256 "ipa_oacc_kernels", /* name */
257 OPTGROUP_LOOP, /* optinfo_flags */
258 TV_TREE_LOOP, /* tv_id */
259 PROP_cfg, /* properties_required */
260 0, /* properties_provided */
261 0, /* properties_destroyed */
262 0, /* todo_flags_start */
263 0, /* todo_flags_finish */
266 class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
268 public:
269 pass_ipa_oacc_kernels (gcc::context *ctxt)
270 : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt)
273 }; // class pass_ipa_oacc_kernels
275 } // anon namespace
277 simple_ipa_opt_pass *
278 make_pass_ipa_oacc_kernels (gcc::context *ctxt)
280 return new pass_ipa_oacc_kernels (ctxt);
283 /* The no-loop superpass. */
285 namespace {
287 const pass_data pass_data_tree_no_loop =
289 GIMPLE_PASS, /* type */
290 "no_loop", /* name */
291 OPTGROUP_NONE, /* optinfo_flags */
292 TV_TREE_NOLOOP, /* tv_id */
293 PROP_cfg, /* properties_required */
294 0, /* properties_provided */
295 0, /* properties_destroyed */
296 0, /* todo_flags_start */
297 0, /* todo_flags_finish */
300 class pass_tree_no_loop : public gimple_opt_pass
302 public:
303 pass_tree_no_loop (gcc::context *ctxt)
304 : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
307 /* opt_pass methods: */
308 virtual bool gate (function *fn) { return !gate_loop (fn); }
310 }; // class pass_tree_no_loop
312 } // anon namespace
314 gimple_opt_pass *
315 make_pass_tree_no_loop (gcc::context *ctxt)
317 return new pass_tree_no_loop (ctxt);
321 /* Loop optimizer initialization. */
323 namespace {
325 const pass_data pass_data_tree_loop_init =
327 GIMPLE_PASS, /* type */
328 "loopinit", /* name */
329 OPTGROUP_LOOP, /* optinfo_flags */
330 TV_NONE, /* tv_id */
331 PROP_cfg, /* properties_required */
332 0, /* properties_provided */
333 0, /* properties_destroyed */
334 0, /* todo_flags_start */
335 0, /* todo_flags_finish */
338 class pass_tree_loop_init : public gimple_opt_pass
340 public:
341 pass_tree_loop_init (gcc::context *ctxt)
342 : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
345 /* opt_pass methods: */
346 virtual unsigned int execute (function *);
348 }; // class pass_tree_loop_init
350 unsigned int
351 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
353 /* When processing a loop in the loop pipeline, we should be able to assert
354 that:
355 (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
356 | LOOP_CLOSED_SSA)
357 && scev_initialized_p ())
359 loop_optimizer_init (LOOPS_NORMAL
360 | LOOPS_HAVE_RECORDED_EXITS);
361 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
362 scev_initialize ();
364 return 0;
367 } // anon namespace
369 gimple_opt_pass *
370 make_pass_tree_loop_init (gcc::context *ctxt)
372 return new pass_tree_loop_init (ctxt);
375 /* Loop autovectorization. */
377 namespace {
379 const pass_data pass_data_vectorize =
381 GIMPLE_PASS, /* type */
382 "vect", /* name */
383 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
384 TV_TREE_VECTORIZATION, /* tv_id */
385 ( PROP_cfg | PROP_ssa ), /* properties_required */
386 0, /* properties_provided */
387 0, /* properties_destroyed */
388 0, /* todo_flags_start */
389 0, /* todo_flags_finish */
392 class pass_vectorize : public gimple_opt_pass
394 public:
395 pass_vectorize (gcc::context *ctxt)
396 : gimple_opt_pass (pass_data_vectorize, ctxt)
399 /* opt_pass methods: */
400 virtual bool gate (function *fun)
402 return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
405 virtual unsigned int execute (function *);
407 }; // class pass_vectorize
409 unsigned int
410 pass_vectorize::execute (function *fun)
412 if (number_of_loops (fun) <= 1)
413 return 0;
415 return vectorize_loops ();
418 } // anon namespace
420 gimple_opt_pass *
421 make_pass_vectorize (gcc::context *ctxt)
423 return new pass_vectorize (ctxt);
426 /* Propagation of constants using scev. */
428 namespace {
430 const pass_data pass_data_scev_cprop =
432 GIMPLE_PASS, /* type */
433 "sccp", /* name */
434 OPTGROUP_LOOP, /* optinfo_flags */
435 TV_SCEV_CONST, /* tv_id */
436 ( PROP_cfg | PROP_ssa ), /* properties_required */
437 0, /* properties_provided */
438 0, /* properties_destroyed */
439 0, /* todo_flags_start */
440 ( TODO_cleanup_cfg
441 | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */
444 class pass_scev_cprop : public gimple_opt_pass
446 public:
447 pass_scev_cprop (gcc::context *ctxt)
448 : gimple_opt_pass (pass_data_scev_cprop, ctxt)
451 /* opt_pass methods: */
452 virtual bool gate (function *) { return flag_tree_scev_cprop; }
453 virtual unsigned int execute (function *) { return scev_const_prop (); }
455 }; // class pass_scev_cprop
457 } // anon namespace
459 gimple_opt_pass *
460 make_pass_scev_cprop (gcc::context *ctxt)
462 return new pass_scev_cprop (ctxt);
465 /* Record bounds on numbers of iterations of loops. */
467 namespace {
469 const pass_data pass_data_record_bounds =
471 GIMPLE_PASS, /* type */
472 "*record_bounds", /* name */
473 OPTGROUP_NONE, /* optinfo_flags */
474 TV_TREE_LOOP_BOUNDS, /* tv_id */
475 ( PROP_cfg | PROP_ssa ), /* properties_required */
476 0, /* properties_provided */
477 0, /* properties_destroyed */
478 0, /* todo_flags_start */
479 0, /* todo_flags_finish */
482 class pass_record_bounds : public gimple_opt_pass
484 public:
485 pass_record_bounds (gcc::context *ctxt)
486 : gimple_opt_pass (pass_data_record_bounds, ctxt)
489 /* opt_pass methods: */
490 virtual unsigned int execute (function *);
492 }; // class pass_record_bounds
494 unsigned int
495 pass_record_bounds::execute (function *fun)
497 if (number_of_loops (fun) <= 1)
498 return 0;
500 estimate_numbers_of_iterations ();
501 scev_reset ();
502 return 0;
505 } // anon namespace
507 gimple_opt_pass *
508 make_pass_record_bounds (gcc::context *ctxt)
510 return new pass_record_bounds (ctxt);
513 /* Induction variable optimizations. */
515 namespace {
517 const pass_data pass_data_iv_optimize =
519 GIMPLE_PASS, /* type */
520 "ivopts", /* name */
521 OPTGROUP_LOOP, /* optinfo_flags */
522 TV_TREE_LOOP_IVOPTS, /* tv_id */
523 ( PROP_cfg | PROP_ssa ), /* properties_required */
524 0, /* properties_provided */
525 0, /* properties_destroyed */
526 0, /* todo_flags_start */
527 TODO_update_ssa, /* todo_flags_finish */
530 class pass_iv_optimize : public gimple_opt_pass
532 public:
533 pass_iv_optimize (gcc::context *ctxt)
534 : gimple_opt_pass (pass_data_iv_optimize, ctxt)
537 /* opt_pass methods: */
538 virtual bool gate (function *) { return flag_ivopts != 0; }
539 virtual unsigned int execute (function *);
541 }; // class pass_iv_optimize
543 unsigned int
544 pass_iv_optimize::execute (function *fun)
546 if (number_of_loops (fun) <= 1)
547 return 0;
549 tree_ssa_iv_optimize ();
550 return 0;
553 } // anon namespace
555 gimple_opt_pass *
556 make_pass_iv_optimize (gcc::context *ctxt)
558 return new pass_iv_optimize (ctxt);
561 /* Loop optimizer finalization. */
563 static unsigned int
564 tree_ssa_loop_done (void)
566 free_numbers_of_iterations_estimates (cfun);
567 scev_finalize ();
568 loop_optimizer_finalize ();
569 return 0;
572 namespace {
574 const pass_data pass_data_tree_loop_done =
576 GIMPLE_PASS, /* type */
577 "loopdone", /* name */
578 OPTGROUP_LOOP, /* optinfo_flags */
579 TV_NONE, /* tv_id */
580 PROP_cfg, /* properties_required */
581 0, /* properties_provided */
582 0, /* properties_destroyed */
583 0, /* todo_flags_start */
584 TODO_cleanup_cfg, /* todo_flags_finish */
587 class pass_tree_loop_done : public gimple_opt_pass
589 public:
590 pass_tree_loop_done (gcc::context *ctxt)
591 : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
594 /* opt_pass methods: */
595 virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
597 }; // class pass_tree_loop_done
599 } // anon namespace
601 gimple_opt_pass *
602 make_pass_tree_loop_done (gcc::context *ctxt)
604 return new pass_tree_loop_done (ctxt);
607 /* Calls CBCK for each index in memory reference ADDR_P. There are two
608 kinds situations handled; in each of these cases, the memory reference
609 and DATA are passed to the callback:
611 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
612 pass the pointer to the index to the callback.
614 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
615 pointer to addr to the callback.
617 If the callback returns false, the whole search stops and false is returned.
618 Otherwise the function returns true after traversing through the whole
619 reference *ADDR_P. */
621 bool
622 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
624 tree *nxt, *idx;
626 for (; ; addr_p = nxt)
628 switch (TREE_CODE (*addr_p))
630 case SSA_NAME:
631 return cbck (*addr_p, addr_p, data);
633 case MEM_REF:
634 nxt = &TREE_OPERAND (*addr_p, 0);
635 return cbck (*addr_p, nxt, data);
637 case BIT_FIELD_REF:
638 case VIEW_CONVERT_EXPR:
639 case REALPART_EXPR:
640 case IMAGPART_EXPR:
641 nxt = &TREE_OPERAND (*addr_p, 0);
642 break;
644 case COMPONENT_REF:
645 /* If the component has varying offset, it behaves like index
646 as well. */
647 idx = &TREE_OPERAND (*addr_p, 2);
648 if (*idx
649 && !cbck (*addr_p, idx, data))
650 return false;
652 nxt = &TREE_OPERAND (*addr_p, 0);
653 break;
655 case ARRAY_REF:
656 case ARRAY_RANGE_REF:
657 nxt = &TREE_OPERAND (*addr_p, 0);
658 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
659 return false;
660 break;
662 case VAR_DECL:
663 case PARM_DECL:
664 case CONST_DECL:
665 case STRING_CST:
666 case RESULT_DECL:
667 case VECTOR_CST:
668 case COMPLEX_CST:
669 case INTEGER_CST:
670 case REAL_CST:
671 case FIXED_CST:
672 case CONSTRUCTOR:
673 return true;
675 case ADDR_EXPR:
676 gcc_assert (is_gimple_min_invariant (*addr_p));
677 return true;
679 case TARGET_MEM_REF:
680 idx = &TMR_BASE (*addr_p);
681 if (*idx
682 && !cbck (*addr_p, idx, data))
683 return false;
684 idx = &TMR_INDEX (*addr_p);
685 if (*idx
686 && !cbck (*addr_p, idx, data))
687 return false;
688 idx = &TMR_INDEX2 (*addr_p);
689 if (*idx
690 && !cbck (*addr_p, idx, data))
691 return false;
692 return true;
694 default:
695 gcc_unreachable ();
701 /* The name and the length of the currently generated variable
702 for lsm. */
703 #define MAX_LSM_NAME_LENGTH 40
704 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
705 static int lsm_tmp_name_length;
707 /* Adds S to lsm_tmp_name. */
709 static void
710 lsm_tmp_name_add (const char *s)
712 int l = strlen (s) + lsm_tmp_name_length;
713 if (l > MAX_LSM_NAME_LENGTH)
714 return;
716 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
717 lsm_tmp_name_length = l;
720 /* Stores the name for temporary variable that replaces REF to
721 lsm_tmp_name. */
723 static void
724 gen_lsm_tmp_name (tree ref)
726 const char *name;
728 switch (TREE_CODE (ref))
730 case MEM_REF:
731 case TARGET_MEM_REF:
732 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
733 lsm_tmp_name_add ("_");
734 break;
736 case ADDR_EXPR:
737 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
738 break;
740 case BIT_FIELD_REF:
741 case VIEW_CONVERT_EXPR:
742 case ARRAY_RANGE_REF:
743 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
744 break;
746 case REALPART_EXPR:
747 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
748 lsm_tmp_name_add ("_RE");
749 break;
751 case IMAGPART_EXPR:
752 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
753 lsm_tmp_name_add ("_IM");
754 break;
756 case COMPONENT_REF:
757 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
758 lsm_tmp_name_add ("_");
759 name = get_name (TREE_OPERAND (ref, 1));
760 if (!name)
761 name = "F";
762 lsm_tmp_name_add (name);
763 break;
765 case ARRAY_REF:
766 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
767 lsm_tmp_name_add ("_I");
768 break;
770 case SSA_NAME:
771 case VAR_DECL:
772 case PARM_DECL:
773 case FUNCTION_DECL:
774 case LABEL_DECL:
775 name = get_name (ref);
776 if (!name)
777 name = "D";
778 lsm_tmp_name_add (name);
779 break;
781 case STRING_CST:
782 lsm_tmp_name_add ("S");
783 break;
785 case RESULT_DECL:
786 lsm_tmp_name_add ("R");
787 break;
789 case INTEGER_CST:
790 default:
791 /* Nothing. */
792 break;
796 /* Determines name for temporary variable that replaces REF.
797 The name is accumulated into the lsm_tmp_name variable.
798 N is added to the name of the temporary. */
800 char *
801 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
803 char ns[2];
805 lsm_tmp_name_length = 0;
806 gen_lsm_tmp_name (ref);
807 lsm_tmp_name_add ("_lsm");
808 if (n < 10)
810 ns[0] = '0' + n;
811 ns[1] = 0;
812 lsm_tmp_name_add (ns);
814 return lsm_tmp_name;
815 if (suffix != NULL)
816 lsm_tmp_name_add (suffix);
819 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
821 unsigned
822 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
824 basic_block *body = get_loop_body (loop);
825 gimple_stmt_iterator gsi;
826 unsigned size = 0, i;
828 for (i = 0; i < loop->num_nodes; i++)
829 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
830 size += estimate_num_insns (gsi_stmt (gsi), weights);
831 free (body);
833 return size;