Daily bump.
[official-gcc.git] / gcc / tree-ssa-loop.c
blobccb8f9762bb3e25f4b8a3b5f1fcb509035cc4f43
1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2015 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 "tm.h"
24 #include "hash-set.h"
25 #include "machmode.h"
26 #include "vec.h"
27 #include "double-int.h"
28 #include "input.h"
29 #include "alias.h"
30 #include "symtab.h"
31 #include "wide-int.h"
32 #include "inchash.h"
33 #include "tree.h"
34 #include "fold-const.h"
35 #include "tm_p.h"
36 #include "predict.h"
37 #include "hard-reg-set.h"
38 #include "input.h"
39 #include "function.h"
40 #include "dominance.h"
41 #include "cfg.h"
42 #include "basic-block.h"
43 #include "tree-ssa-alias.h"
44 #include "internal-fn.h"
45 #include "gimple-expr.h"
46 #include "is-a.h"
47 #include "gimple.h"
48 #include "gimple-iterator.h"
49 #include "tree-ssa-loop-ivopts.h"
50 #include "tree-ssa-loop-manip.h"
51 #include "tree-ssa-loop-niter.h"
52 #include "tree-ssa-loop.h"
53 #include "tree-pass.h"
54 #include "cfgloop.h"
55 #include "flags.h"
56 #include "tree-inline.h"
57 #include "tree-scalar-evolution.h"
58 #include "diagnostic-core.h"
59 #include "tree-vectorizer.h"
62 /* A pass making sure loops are fixed up. */
64 namespace {
66 const pass_data pass_data_fix_loops =
68 GIMPLE_PASS, /* type */
69 "fix_loops", /* name */
70 OPTGROUP_LOOP, /* optinfo_flags */
71 TV_TREE_LOOP, /* tv_id */
72 PROP_cfg, /* properties_required */
73 0, /* properties_provided */
74 0, /* properties_destroyed */
75 0, /* todo_flags_start */
76 0, /* todo_flags_finish */
79 class pass_fix_loops : public gimple_opt_pass
81 public:
82 pass_fix_loops (gcc::context *ctxt)
83 : gimple_opt_pass (pass_data_fix_loops, ctxt)
86 /* opt_pass methods: */
87 virtual bool gate (function *) { return flag_tree_loop_optimize; }
89 virtual unsigned int execute (function *fn);
90 }; // class pass_fix_loops
92 unsigned int
93 pass_fix_loops::execute (function *)
95 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
97 calculate_dominance_info (CDI_DOMINATORS);
98 fix_loop_structure (NULL);
100 return 0;
103 } // anon namespace
105 gimple_opt_pass *
106 make_pass_fix_loops (gcc::context *ctxt)
108 return new pass_fix_loops (ctxt);
112 /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
113 but we also avoid running it when the IL doesn't contain any loop. */
115 static bool
116 gate_loop (function *fn)
118 if (!flag_tree_loop_optimize)
119 return false;
121 /* For -fdump-passes which runs before loop discovery print the
122 state of -ftree-loop-optimize. */
123 if (!loops_for_fn (fn))
124 return true;
126 return number_of_loops (fn) > 1;
129 /* The loop superpass. */
131 namespace {
133 const pass_data pass_data_tree_loop =
135 GIMPLE_PASS, /* type */
136 "loop", /* name */
137 OPTGROUP_LOOP, /* optinfo_flags */
138 TV_TREE_LOOP, /* tv_id */
139 PROP_cfg, /* properties_required */
140 0, /* properties_provided */
141 0, /* properties_destroyed */
142 0, /* todo_flags_start */
143 0, /* todo_flags_finish */
146 class pass_tree_loop : public gimple_opt_pass
148 public:
149 pass_tree_loop (gcc::context *ctxt)
150 : gimple_opt_pass (pass_data_tree_loop, ctxt)
153 /* opt_pass methods: */
154 virtual bool gate (function *fn) { return gate_loop (fn); }
156 }; // class pass_tree_loop
158 } // anon namespace
160 gimple_opt_pass *
161 make_pass_tree_loop (gcc::context *ctxt)
163 return new pass_tree_loop (ctxt);
166 /* The no-loop superpass. */
168 namespace {
170 const pass_data pass_data_tree_no_loop =
172 GIMPLE_PASS, /* type */
173 "no_loop", /* name */
174 OPTGROUP_NONE, /* optinfo_flags */
175 TV_TREE_NOLOOP, /* tv_id */
176 PROP_cfg, /* properties_required */
177 0, /* properties_provided */
178 0, /* properties_destroyed */
179 0, /* todo_flags_start */
180 0, /* todo_flags_finish */
183 class pass_tree_no_loop : public gimple_opt_pass
185 public:
186 pass_tree_no_loop (gcc::context *ctxt)
187 : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
190 /* opt_pass methods: */
191 virtual bool gate (function *fn) { return !gate_loop (fn); }
193 }; // class pass_tree_no_loop
195 } // anon namespace
197 gimple_opt_pass *
198 make_pass_tree_no_loop (gcc::context *ctxt)
200 return new pass_tree_no_loop (ctxt);
204 /* Loop optimizer initialization. */
206 namespace {
208 const pass_data pass_data_tree_loop_init =
210 GIMPLE_PASS, /* type */
211 "loopinit", /* name */
212 OPTGROUP_LOOP, /* optinfo_flags */
213 TV_NONE, /* 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_tree_loop_init : public gimple_opt_pass
223 public:
224 pass_tree_loop_init (gcc::context *ctxt)
225 : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
228 /* opt_pass methods: */
229 virtual unsigned int execute (function *);
231 }; // class pass_tree_loop_init
233 unsigned int
234 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
236 loop_optimizer_init (LOOPS_NORMAL
237 | LOOPS_HAVE_RECORDED_EXITS);
238 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
240 /* We might discover new loops, e.g. when turning irreducible
241 regions into reducible. */
242 scev_initialize ();
244 return 0;
247 } // anon namespace
249 gimple_opt_pass *
250 make_pass_tree_loop_init (gcc::context *ctxt)
252 return new pass_tree_loop_init (ctxt);
255 /* Loop autovectorization. */
257 namespace {
259 const pass_data pass_data_vectorize =
261 GIMPLE_PASS, /* type */
262 "vect", /* name */
263 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
264 TV_TREE_VECTORIZATION, /* tv_id */
265 ( PROP_cfg | PROP_ssa ), /* properties_required */
266 0, /* properties_provided */
267 0, /* properties_destroyed */
268 0, /* todo_flags_start */
269 0, /* todo_flags_finish */
272 class pass_vectorize : public gimple_opt_pass
274 public:
275 pass_vectorize (gcc::context *ctxt)
276 : gimple_opt_pass (pass_data_vectorize, ctxt)
279 /* opt_pass methods: */
280 virtual bool gate (function *fun)
282 return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
285 virtual unsigned int execute (function *);
287 }; // class pass_vectorize
289 unsigned int
290 pass_vectorize::execute (function *fun)
292 if (number_of_loops (fun) <= 1)
293 return 0;
295 return vectorize_loops ();
298 } // anon namespace
300 gimple_opt_pass *
301 make_pass_vectorize (gcc::context *ctxt)
303 return new pass_vectorize (ctxt);
306 /* Check the correctness of the data dependence analyzers. */
308 namespace {
310 const pass_data pass_data_check_data_deps =
312 GIMPLE_PASS, /* type */
313 "ckdd", /* name */
314 OPTGROUP_LOOP, /* optinfo_flags */
315 TV_CHECK_DATA_DEPS, /* tv_id */
316 ( PROP_cfg | PROP_ssa ), /* properties_required */
317 0, /* properties_provided */
318 0, /* properties_destroyed */
319 0, /* todo_flags_start */
320 0, /* todo_flags_finish */
323 class pass_check_data_deps : public gimple_opt_pass
325 public:
326 pass_check_data_deps (gcc::context *ctxt)
327 : gimple_opt_pass (pass_data_check_data_deps, ctxt)
330 /* opt_pass methods: */
331 virtual bool gate (function *) { return flag_check_data_deps != 0; }
332 virtual unsigned int execute (function *);
334 }; // class pass_check_data_deps
336 unsigned int
337 pass_check_data_deps::execute (function *fun)
339 if (number_of_loops (fun) <= 1)
340 return 0;
342 tree_check_data_deps ();
343 return 0;
346 } // anon namespace
348 gimple_opt_pass *
349 make_pass_check_data_deps (gcc::context *ctxt)
351 return new pass_check_data_deps (ctxt);
354 /* Propagation of constants using scev. */
356 namespace {
358 const pass_data pass_data_scev_cprop =
360 GIMPLE_PASS, /* type */
361 "sccp", /* name */
362 OPTGROUP_LOOP, /* optinfo_flags */
363 TV_SCEV_CONST, /* tv_id */
364 ( PROP_cfg | PROP_ssa ), /* properties_required */
365 0, /* properties_provided */
366 0, /* properties_destroyed */
367 0, /* todo_flags_start */
368 ( TODO_cleanup_cfg
369 | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */
372 class pass_scev_cprop : public gimple_opt_pass
374 public:
375 pass_scev_cprop (gcc::context *ctxt)
376 : gimple_opt_pass (pass_data_scev_cprop, ctxt)
379 /* opt_pass methods: */
380 virtual bool gate (function *) { return flag_tree_scev_cprop; }
381 virtual unsigned int execute (function *) { return scev_const_prop (); }
383 }; // class pass_scev_cprop
385 } // anon namespace
387 gimple_opt_pass *
388 make_pass_scev_cprop (gcc::context *ctxt)
390 return new pass_scev_cprop (ctxt);
393 /* Record bounds on numbers of iterations of loops. */
395 namespace {
397 const pass_data pass_data_record_bounds =
399 GIMPLE_PASS, /* type */
400 "*record_bounds", /* name */
401 OPTGROUP_NONE, /* optinfo_flags */
402 TV_TREE_LOOP_BOUNDS, /* tv_id */
403 ( PROP_cfg | PROP_ssa ), /* properties_required */
404 0, /* properties_provided */
405 0, /* properties_destroyed */
406 0, /* todo_flags_start */
407 0, /* todo_flags_finish */
410 class pass_record_bounds : public gimple_opt_pass
412 public:
413 pass_record_bounds (gcc::context *ctxt)
414 : gimple_opt_pass (pass_data_record_bounds, ctxt)
417 /* opt_pass methods: */
418 virtual unsigned int execute (function *);
420 }; // class pass_record_bounds
422 unsigned int
423 pass_record_bounds::execute (function *fun)
425 if (number_of_loops (fun) <= 1)
426 return 0;
428 estimate_numbers_of_iterations ();
429 scev_reset ();
430 return 0;
433 } // anon namespace
435 gimple_opt_pass *
436 make_pass_record_bounds (gcc::context *ctxt)
438 return new pass_record_bounds (ctxt);
441 /* Induction variable optimizations. */
443 namespace {
445 const pass_data pass_data_iv_optimize =
447 GIMPLE_PASS, /* type */
448 "ivopts", /* name */
449 OPTGROUP_LOOP, /* optinfo_flags */
450 TV_TREE_LOOP_IVOPTS, /* tv_id */
451 ( PROP_cfg | PROP_ssa ), /* properties_required */
452 0, /* properties_provided */
453 0, /* properties_destroyed */
454 0, /* todo_flags_start */
455 TODO_update_ssa, /* todo_flags_finish */
458 class pass_iv_optimize : public gimple_opt_pass
460 public:
461 pass_iv_optimize (gcc::context *ctxt)
462 : gimple_opt_pass (pass_data_iv_optimize, ctxt)
465 /* opt_pass methods: */
466 virtual bool gate (function *) { return flag_ivopts != 0; }
467 virtual unsigned int execute (function *);
469 }; // class pass_iv_optimize
471 unsigned int
472 pass_iv_optimize::execute (function *fun)
474 if (number_of_loops (fun) <= 1)
475 return 0;
477 tree_ssa_iv_optimize ();
478 return 0;
481 } // anon namespace
483 gimple_opt_pass *
484 make_pass_iv_optimize (gcc::context *ctxt)
486 return new pass_iv_optimize (ctxt);
489 /* Loop optimizer finalization. */
491 static unsigned int
492 tree_ssa_loop_done (void)
494 free_numbers_of_iterations_estimates ();
495 scev_finalize ();
496 loop_optimizer_finalize ();
497 return 0;
500 namespace {
502 const pass_data pass_data_tree_loop_done =
504 GIMPLE_PASS, /* type */
505 "loopdone", /* name */
506 OPTGROUP_LOOP, /* optinfo_flags */
507 TV_NONE, /* tv_id */
508 PROP_cfg, /* properties_required */
509 0, /* properties_provided */
510 0, /* properties_destroyed */
511 0, /* todo_flags_start */
512 TODO_cleanup_cfg, /* todo_flags_finish */
515 class pass_tree_loop_done : public gimple_opt_pass
517 public:
518 pass_tree_loop_done (gcc::context *ctxt)
519 : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
522 /* opt_pass methods: */
523 virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
525 }; // class pass_tree_loop_done
527 } // anon namespace
529 gimple_opt_pass *
530 make_pass_tree_loop_done (gcc::context *ctxt)
532 return new pass_tree_loop_done (ctxt);
535 /* Calls CBCK for each index in memory reference ADDR_P. There are two
536 kinds situations handled; in each of these cases, the memory reference
537 and DATA are passed to the callback:
539 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
540 pass the pointer to the index to the callback.
542 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
543 pointer to addr to the callback.
545 If the callback returns false, the whole search stops and false is returned.
546 Otherwise the function returns true after traversing through the whole
547 reference *ADDR_P. */
549 bool
550 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
552 tree *nxt, *idx;
554 for (; ; addr_p = nxt)
556 switch (TREE_CODE (*addr_p))
558 case SSA_NAME:
559 return cbck (*addr_p, addr_p, data);
561 case MEM_REF:
562 nxt = &TREE_OPERAND (*addr_p, 0);
563 return cbck (*addr_p, nxt, data);
565 case BIT_FIELD_REF:
566 case VIEW_CONVERT_EXPR:
567 case REALPART_EXPR:
568 case IMAGPART_EXPR:
569 nxt = &TREE_OPERAND (*addr_p, 0);
570 break;
572 case COMPONENT_REF:
573 /* If the component has varying offset, it behaves like index
574 as well. */
575 idx = &TREE_OPERAND (*addr_p, 2);
576 if (*idx
577 && !cbck (*addr_p, idx, data))
578 return false;
580 nxt = &TREE_OPERAND (*addr_p, 0);
581 break;
583 case ARRAY_REF:
584 case ARRAY_RANGE_REF:
585 nxt = &TREE_OPERAND (*addr_p, 0);
586 if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
587 return false;
588 break;
590 case VAR_DECL:
591 case PARM_DECL:
592 case CONST_DECL:
593 case STRING_CST:
594 case RESULT_DECL:
595 case VECTOR_CST:
596 case COMPLEX_CST:
597 case INTEGER_CST:
598 case REAL_CST:
599 case FIXED_CST:
600 case CONSTRUCTOR:
601 return true;
603 case ADDR_EXPR:
604 gcc_assert (is_gimple_min_invariant (*addr_p));
605 return true;
607 case TARGET_MEM_REF:
608 idx = &TMR_BASE (*addr_p);
609 if (*idx
610 && !cbck (*addr_p, idx, data))
611 return false;
612 idx = &TMR_INDEX (*addr_p);
613 if (*idx
614 && !cbck (*addr_p, idx, data))
615 return false;
616 idx = &TMR_INDEX2 (*addr_p);
617 if (*idx
618 && !cbck (*addr_p, idx, data))
619 return false;
620 return true;
622 default:
623 gcc_unreachable ();
629 /* The name and the length of the currently generated variable
630 for lsm. */
631 #define MAX_LSM_NAME_LENGTH 40
632 static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
633 static int lsm_tmp_name_length;
635 /* Adds S to lsm_tmp_name. */
637 static void
638 lsm_tmp_name_add (const char *s)
640 int l = strlen (s) + lsm_tmp_name_length;
641 if (l > MAX_LSM_NAME_LENGTH)
642 return;
644 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
645 lsm_tmp_name_length = l;
648 /* Stores the name for temporary variable that replaces REF to
649 lsm_tmp_name. */
651 static void
652 gen_lsm_tmp_name (tree ref)
654 const char *name;
656 switch (TREE_CODE (ref))
658 case MEM_REF:
659 case TARGET_MEM_REF:
660 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
661 lsm_tmp_name_add ("_");
662 break;
664 case ADDR_EXPR:
665 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
666 break;
668 case BIT_FIELD_REF:
669 case VIEW_CONVERT_EXPR:
670 case ARRAY_RANGE_REF:
671 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
672 break;
674 case REALPART_EXPR:
675 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
676 lsm_tmp_name_add ("_RE");
677 break;
679 case IMAGPART_EXPR:
680 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
681 lsm_tmp_name_add ("_IM");
682 break;
684 case COMPONENT_REF:
685 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
686 lsm_tmp_name_add ("_");
687 name = get_name (TREE_OPERAND (ref, 1));
688 if (!name)
689 name = "F";
690 lsm_tmp_name_add (name);
691 break;
693 case ARRAY_REF:
694 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
695 lsm_tmp_name_add ("_I");
696 break;
698 case SSA_NAME:
699 case VAR_DECL:
700 case PARM_DECL:
701 name = get_name (ref);
702 if (!name)
703 name = "D";
704 lsm_tmp_name_add (name);
705 break;
707 case STRING_CST:
708 lsm_tmp_name_add ("S");
709 break;
711 case RESULT_DECL:
712 lsm_tmp_name_add ("R");
713 break;
715 case INTEGER_CST:
716 /* Nothing. */
717 break;
719 default:
720 gcc_unreachable ();
724 /* Determines name for temporary variable that replaces REF.
725 The name is accumulated into the lsm_tmp_name variable.
726 N is added to the name of the temporary. */
728 char *
729 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
731 char ns[2];
733 lsm_tmp_name_length = 0;
734 gen_lsm_tmp_name (ref);
735 lsm_tmp_name_add ("_lsm");
736 if (n < 10)
738 ns[0] = '0' + n;
739 ns[1] = 0;
740 lsm_tmp_name_add (ns);
742 return lsm_tmp_name;
743 if (suffix != NULL)
744 lsm_tmp_name_add (suffix);
747 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
749 unsigned
750 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
752 basic_block *body = get_loop_body (loop);
753 gimple_stmt_iterator gsi;
754 unsigned size = 0, i;
756 for (i = 0; i < loop->num_nodes; i++)
757 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
758 size += estimate_num_insns (gsi_stmt (gsi), weights);
759 free (body);
761 return size;