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