Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-ssa-loop.c
1 /* Loop optimizations over tree-ssa.
2    Copyright (C) 2003-2015 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 "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"
60
61
62 /* A pass making sure loops are fixed up.  */
63
64 namespace {
65
66 const pass_data pass_data_fix_loops =
67 {
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 */
77 };
78
79 class pass_fix_loops : public gimple_opt_pass
80 {
81 public:
82   pass_fix_loops (gcc::context *ctxt)
83     : gimple_opt_pass (pass_data_fix_loops, ctxt)
84   {}
85
86   /* opt_pass methods: */
87   virtual bool gate (function *) { return flag_tree_loop_optimize; }
88
89   virtual unsigned int execute (function *fn);
90 }; // class pass_fix_loops
91
92 unsigned int
93 pass_fix_loops::execute (function *)
94 {
95   if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
96     {
97       calculate_dominance_info (CDI_DOMINATORS);
98       fix_loop_structure (NULL);
99     }
100   return 0;
101 }
102
103 } // anon namespace
104
105 gimple_opt_pass *
106 make_pass_fix_loops (gcc::context *ctxt)
107 {
108   return new pass_fix_loops (ctxt);
109 }
110
111
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.  */
114
115 static bool
116 gate_loop (function *fn)
117 {
118   if (!flag_tree_loop_optimize)
119     return false;
120
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;
125
126   return number_of_loops (fn) > 1;
127 }
128
129 /* The loop superpass.  */
130
131 namespace {
132
133 const pass_data pass_data_tree_loop =
134 {
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 */
144 };
145
146 class pass_tree_loop : public gimple_opt_pass
147 {
148 public:
149   pass_tree_loop (gcc::context *ctxt)
150     : gimple_opt_pass (pass_data_tree_loop, ctxt)
151   {}
152
153   /* opt_pass methods: */
154   virtual bool gate (function *fn) { return gate_loop (fn); }
155
156 }; // class pass_tree_loop
157
158 } // anon namespace
159
160 gimple_opt_pass *
161 make_pass_tree_loop (gcc::context *ctxt)
162 {
163   return new pass_tree_loop (ctxt);
164 }
165
166 /* The no-loop superpass.  */
167
168 namespace {
169
170 const pass_data pass_data_tree_no_loop =
171 {
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 */
181 };
182
183 class pass_tree_no_loop : public gimple_opt_pass
184 {
185 public:
186   pass_tree_no_loop (gcc::context *ctxt)
187     : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
188   {}
189
190   /* opt_pass methods: */
191   virtual bool gate (function *fn) { return !gate_loop (fn); }
192
193 }; // class pass_tree_no_loop
194
195 } // anon namespace
196
197 gimple_opt_pass *
198 make_pass_tree_no_loop (gcc::context *ctxt)
199 {
200   return new pass_tree_no_loop (ctxt);
201 }
202
203
204 /* Loop optimizer initialization.  */
205
206 namespace {
207
208 const pass_data pass_data_tree_loop_init =
209 {
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 */
219 };
220
221 class pass_tree_loop_init : public gimple_opt_pass
222 {
223 public:
224   pass_tree_loop_init (gcc::context *ctxt)
225     : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
226   {}
227
228   /* opt_pass methods: */
229   virtual unsigned int execute (function *);
230
231 }; // class pass_tree_loop_init
232
233 unsigned int
234 pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
235 {
236   loop_optimizer_init (LOOPS_NORMAL
237                        | LOOPS_HAVE_RECORDED_EXITS);
238   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
239
240   /* We might discover new loops, e.g. when turning irreducible
241      regions into reducible.  */
242   scev_initialize ();
243
244   return 0;
245 }
246
247 } // anon namespace
248
249 gimple_opt_pass *
250 make_pass_tree_loop_init (gcc::context *ctxt)
251 {
252   return new pass_tree_loop_init (ctxt);
253 }
254
255 /* Loop autovectorization.  */
256
257 namespace {
258
259 const pass_data pass_data_vectorize =
260 {
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 */
270 };
271
272 class pass_vectorize : public gimple_opt_pass
273 {
274 public:
275   pass_vectorize (gcc::context *ctxt)
276     : gimple_opt_pass (pass_data_vectorize, ctxt)
277   {}
278
279   /* opt_pass methods: */
280   virtual bool gate (function *fun)
281     {
282       return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
283     }
284
285   virtual unsigned int execute (function *);
286
287 }; // class pass_vectorize
288
289 unsigned int
290 pass_vectorize::execute (function *fun)
291 {
292   if (number_of_loops (fun) <= 1)
293     return 0;
294
295   return vectorize_loops ();
296 }
297
298 } // anon namespace
299
300 gimple_opt_pass *
301 make_pass_vectorize (gcc::context *ctxt)
302 {
303   return new pass_vectorize (ctxt);
304 }
305
306 /* Check the correctness of the data dependence analyzers.  */
307
308 namespace {
309
310 const pass_data pass_data_check_data_deps =
311 {
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 */
321 };
322
323 class pass_check_data_deps : public gimple_opt_pass
324 {
325 public:
326   pass_check_data_deps (gcc::context *ctxt)
327     : gimple_opt_pass (pass_data_check_data_deps, ctxt)
328   {}
329
330   /* opt_pass methods: */
331   virtual bool gate (function *) { return flag_check_data_deps != 0; }
332   virtual unsigned int execute (function *);
333
334 }; // class pass_check_data_deps
335
336 unsigned int
337 pass_check_data_deps::execute (function *fun)
338 {
339   if (number_of_loops (fun) <= 1)
340     return 0;
341
342   tree_check_data_deps ();
343   return 0;
344 }
345
346 } // anon namespace
347
348 gimple_opt_pass *
349 make_pass_check_data_deps (gcc::context *ctxt)
350 {
351   return new pass_check_data_deps (ctxt);
352 }
353
354 /* Propagation of constants using scev.  */
355
356 namespace {
357
358 const pass_data pass_data_scev_cprop =
359 {
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 */
370 };
371
372 class pass_scev_cprop : public gimple_opt_pass
373 {
374 public:
375   pass_scev_cprop (gcc::context *ctxt)
376     : gimple_opt_pass (pass_data_scev_cprop, ctxt)
377   {}
378
379   /* opt_pass methods: */
380   virtual bool gate (function *) { return flag_tree_scev_cprop; }
381   virtual unsigned int execute (function *) { return scev_const_prop (); }
382
383 }; // class pass_scev_cprop
384
385 } // anon namespace
386
387 gimple_opt_pass *
388 make_pass_scev_cprop (gcc::context *ctxt)
389 {
390   return new pass_scev_cprop (ctxt);
391 }
392
393 /* Record bounds on numbers of iterations of loops.  */
394
395 namespace {
396
397 const pass_data pass_data_record_bounds =
398 {
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 */
408 };
409
410 class pass_record_bounds : public gimple_opt_pass
411 {
412 public:
413   pass_record_bounds (gcc::context *ctxt)
414     : gimple_opt_pass (pass_data_record_bounds, ctxt)
415   {}
416
417   /* opt_pass methods: */
418   virtual unsigned int execute (function *);
419
420 }; // class pass_record_bounds
421
422 unsigned int
423 pass_record_bounds::execute (function *fun)
424 {
425   if (number_of_loops (fun) <= 1)
426     return 0;
427
428   estimate_numbers_of_iterations ();
429   scev_reset ();
430   return 0;
431 }
432
433 } // anon namespace
434
435 gimple_opt_pass *
436 make_pass_record_bounds (gcc::context *ctxt)
437 {
438   return new pass_record_bounds (ctxt);
439 }
440
441 /* Induction variable optimizations.  */
442
443 namespace {
444
445 const pass_data pass_data_iv_optimize =
446 {
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 */
456 };
457
458 class pass_iv_optimize : public gimple_opt_pass
459 {
460 public:
461   pass_iv_optimize (gcc::context *ctxt)
462     : gimple_opt_pass (pass_data_iv_optimize, ctxt)
463   {}
464
465   /* opt_pass methods: */
466   virtual bool gate (function *) { return flag_ivopts != 0; }
467   virtual unsigned int execute (function *);
468
469 }; // class pass_iv_optimize
470
471 unsigned int
472 pass_iv_optimize::execute (function *fun)
473 {
474   if (number_of_loops (fun) <= 1)
475     return 0;
476
477   tree_ssa_iv_optimize ();
478   return 0;
479 }
480
481 } // anon namespace
482
483 gimple_opt_pass *
484 make_pass_iv_optimize (gcc::context *ctxt)
485 {
486   return new pass_iv_optimize (ctxt);
487 }
488
489 /* Loop optimizer finalization.  */
490
491 static unsigned int
492 tree_ssa_loop_done (void)
493 {
494   free_numbers_of_iterations_estimates ();
495   scev_finalize ();
496   loop_optimizer_finalize ();
497   return 0;
498 }
499
500 namespace {
501
502 const pass_data pass_data_tree_loop_done =
503 {
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 */
513 };
514
515 class pass_tree_loop_done : public gimple_opt_pass
516 {
517 public:
518   pass_tree_loop_done (gcc::context *ctxt)
519     : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
520   {}
521
522   /* opt_pass methods: */
523   virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
524
525 }; // class pass_tree_loop_done
526
527 } // anon namespace
528
529 gimple_opt_pass *
530 make_pass_tree_loop_done (gcc::context *ctxt)
531 {
532   return new pass_tree_loop_done (ctxt);
533 }
534
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:
538
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.
541
542    Pointer dereference: INDIRECT_REF (addr).  In this case we also pass the
543    pointer to addr to the callback.
544
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.  */
548
549 bool
550 for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
551 {
552   tree *nxt, *idx;
553
554   for (; ; addr_p = nxt)
555     {
556       switch (TREE_CODE (*addr_p))
557         {
558         case SSA_NAME:
559           return cbck (*addr_p, addr_p, data);
560
561         case MEM_REF:
562           nxt = &TREE_OPERAND (*addr_p, 0);
563           return cbck (*addr_p, nxt, data);
564
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;
571
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;
579
580           nxt = &TREE_OPERAND (*addr_p, 0);
581           break;
582
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;
589
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;
602
603         case ADDR_EXPR:
604           gcc_assert (is_gimple_min_invariant (*addr_p));
605           return true;
606
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;
621
622         default:
623           gcc_unreachable ();
624         }
625     }
626 }
627
628
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;
634
635 /* Adds S to lsm_tmp_name.  */
636
637 static void
638 lsm_tmp_name_add (const char *s)
639 {
640   int l = strlen (s) + lsm_tmp_name_length;
641   if (l > MAX_LSM_NAME_LENGTH)
642     return;
643
644   strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
645   lsm_tmp_name_length = l;
646 }
647
648 /* Stores the name for temporary variable that replaces REF to
649    lsm_tmp_name.  */
650
651 static void
652 gen_lsm_tmp_name (tree ref)
653 {
654   const char *name;
655
656   switch (TREE_CODE (ref))
657     {
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;
663
664     case ADDR_EXPR:
665       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
666       break;
667
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;
673
674     case REALPART_EXPR:
675       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
676       lsm_tmp_name_add ("_RE");
677       break;
678
679     case IMAGPART_EXPR:
680       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
681       lsm_tmp_name_add ("_IM");
682       break;
683
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;
692
693     case ARRAY_REF:
694       gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
695       lsm_tmp_name_add ("_I");
696       break;
697
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;
706
707     case STRING_CST:
708       lsm_tmp_name_add ("S");
709       break;
710
711     case RESULT_DECL:
712       lsm_tmp_name_add ("R");
713       break;
714
715     case INTEGER_CST:
716       /* Nothing.  */
717       break;
718
719     default:
720       gcc_unreachable ();
721     }
722 }
723
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.  */
727
728 char *
729 get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
730 {
731   char ns[2];
732
733   lsm_tmp_name_length = 0;
734   gen_lsm_tmp_name (ref);
735   lsm_tmp_name_add ("_lsm");
736   if (n < 10)
737     {
738       ns[0] = '0' + n;
739       ns[1] = 0;
740       lsm_tmp_name_add (ns);
741     }
742   return lsm_tmp_name;
743   if (suffix != NULL)
744     lsm_tmp_name_add (suffix);
745 }
746
747 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
748
749 unsigned
750 tree_num_loop_insns (struct loop *loop, eni_weights *weights)
751 {
752   basic_block *body = get_loop_body (loop);
753   gimple_stmt_iterator gsi;
754   unsigned size = 0, i;
755
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);
760
761   return size;
762 }
763
764
765