1/* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
47namespace {
48
49const 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
62class pass_fix_loops : public gimple_opt_pass
63{
64public:
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
75unsigned int
76pass_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
88gimple_opt_pass *
89make_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
98static bool
99gate_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
114namespace {
115
116const 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
129class pass_tree_loop : public gimple_opt_pass
130{
131public:
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
143gimple_opt_pass *
144make_pass_tree_loop (gcc::context *ctxt)
145{
146 return new pass_tree_loop (ctxt);
147}
148
149/* Gate for oacc kernels pass group. */
150
151static bool
152gate_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
170namespace {
171
172const 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
185class pass_oacc_kernels : public gimple_opt_pass
186{
187public:
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
199gimple_opt_pass *
200make_pass_oacc_kernels (gcc::context *ctxt)
201{
202 return new pass_oacc_kernels (ctxt);
203}
204
205/* The ipa oacc superpass. */
206
207namespace {
208
209const 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
222class pass_ipa_oacc : public simple_ipa_opt_pass
223{
224public:
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
242simple_ipa_opt_pass *
243make_pass_ipa_oacc (gcc::context *ctxt)
244{
245 return new pass_ipa_oacc (ctxt);
246}
247
248/* The ipa oacc kernels pass. */
249
250namespace {
251
252const 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
265class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
266{
267public:
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
276simple_ipa_opt_pass *
277make_pass_ipa_oacc_kernels (gcc::context *ctxt)
278{
279 return new pass_ipa_oacc_kernels (ctxt);
280}
281
282/* The no-loop superpass. */
283
284namespace {
285
286const 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
299class pass_tree_no_loop : public gimple_opt_pass
300{
301public:
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
313gimple_opt_pass *
314make_pass_tree_no_loop (gcc::context *ctxt)
315{
316 return new pass_tree_no_loop (ctxt);
317}
318
319
320/* Loop optimizer initialization. */
321
322namespace {
323
324const 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
337class pass_tree_loop_init : public gimple_opt_pass
338{
339public:
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
349unsigned int
350pass_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
368gimple_opt_pass *
369make_pass_tree_loop_init (gcc::context *ctxt)
370{
371 return new pass_tree_loop_init (ctxt);
372}
373
374/* Loop autovectorization. */
375
376namespace {
377
378const 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
391class pass_vectorize : public gimple_opt_pass
392{
393public:
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
408unsigned int
409pass_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
419gimple_opt_pass *
420make_pass_vectorize (gcc::context *ctxt)
421{
422 return new pass_vectorize (ctxt);
423}
424
425/* Propagation of constants using scev. */
426
427namespace {
428
429const 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
443class pass_scev_cprop : public gimple_opt_pass
444{
445public:
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
458gimple_opt_pass *
459make_pass_scev_cprop (gcc::context *ctxt)
460{
461 return new pass_scev_cprop (ctxt);
462}
463
464/* Induction variable optimizations. */
465
466namespace {
467
468const 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
481class pass_iv_optimize : public gimple_opt_pass
482{
483public:
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
494unsigned int
495pass_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
506gimple_opt_pass *
507make_pass_iv_optimize (gcc::context *ctxt)
508{
509 return new pass_iv_optimize (ctxt);
510}
511
512/* Loop optimizer finalization. */
513
514static unsigned int
515tree_ssa_loop_done (void)
516{
517 free_numbers_of_iterations_estimates (cfun);
518 scev_finalize ();
519 loop_optimizer_finalize ();
520 return 0;
521}
522
523namespace {
524
525const 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
538class pass_tree_loop_done : public gimple_opt_pass
539{
540public:
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
552gimple_opt_pass *
553make_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
572bool
573for_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 REAL_CST:
622 case FIXED_CST:
623 case CONSTRUCTOR:
624 return true;
625
626 case ADDR_EXPR:
627 gcc_assert (is_gimple_min_invariant (*addr_p));
628 return true;
629
630 case TARGET_MEM_REF:
631 idx = &TMR_BASE (*addr_p);
632 if (*idx
633 && !cbck (*addr_p, idx, data))
634 return false;
635 idx = &TMR_INDEX (*addr_p);
636 if (*idx
637 && !cbck (*addr_p, idx, data))
638 return false;
639 idx = &TMR_INDEX2 (*addr_p);
640 if (*idx
641 && !cbck (*addr_p, idx, data))
642 return false;
643 return true;
644
645 default:
646 gcc_unreachable ();
647 }
648 }
649}
650
651
652/* The name and the length of the currently generated variable
653 for lsm. */
654#define MAX_LSM_NAME_LENGTH 40
655static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
656static int lsm_tmp_name_length;
657
658/* Adds S to lsm_tmp_name. */
659
660static void
661lsm_tmp_name_add (const char *s)
662{
663 int l = strlen (s) + lsm_tmp_name_length;
664 if (l > MAX_LSM_NAME_LENGTH)
665 return;
666
667 strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
668 lsm_tmp_name_length = l;
669}
670
671/* Stores the name for temporary variable that replaces REF to
672 lsm_tmp_name. */
673
674static void
675gen_lsm_tmp_name (tree ref)
676{
677 const char *name;
678
679 switch (TREE_CODE (ref))
680 {
681 case MEM_REF:
682 case TARGET_MEM_REF:
683 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
684 lsm_tmp_name_add ("_");
685 break;
686
687 case ADDR_EXPR:
688 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
689 break;
690
691 case BIT_FIELD_REF:
692 case VIEW_CONVERT_EXPR:
693 case ARRAY_RANGE_REF:
694 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
695 break;
696
697 case REALPART_EXPR:
698 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
699 lsm_tmp_name_add ("_RE");
700 break;
701
702 case IMAGPART_EXPR:
703 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
704 lsm_tmp_name_add ("_IM");
705 break;
706
707 case COMPONENT_REF:
708 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
709 lsm_tmp_name_add ("_");
710 name = get_name (TREE_OPERAND (ref, 1));
711 if (!name)
712 name = "F";
713 lsm_tmp_name_add (name);
714 break;
715
716 case ARRAY_REF:
717 gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
718 lsm_tmp_name_add ("_I");
719 break;
720
721 case SSA_NAME:
722 case VAR_DECL:
723 case PARM_DECL:
724 case FUNCTION_DECL:
725 case LABEL_DECL:
726 name = get_name (ref);
727 if (!name)
728 name = "D";
729 lsm_tmp_name_add (name);
730 break;
731
732 case STRING_CST:
733 lsm_tmp_name_add ("S");
734 break;
735
736 case RESULT_DECL:
737 lsm_tmp_name_add ("R");
738 break;
739
740 case INTEGER_CST:
741 default:
742 /* Nothing. */
743 break;
744 }
745}
746
747/* Determines name for temporary variable that replaces REF.
748 The name is accumulated into the lsm_tmp_name variable.
749 N is added to the name of the temporary. */
750
751char *
752get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
753{
754 char ns[2];
755
756 lsm_tmp_name_length = 0;
757 gen_lsm_tmp_name (ref);
758 lsm_tmp_name_add ("_lsm");
759 if (n < 10)
760 {
761 ns[0] = '0' + n;
762 ns[1] = 0;
763 lsm_tmp_name_add (ns);
764 }
765 return lsm_tmp_name;
766 if (suffix != NULL)
767 lsm_tmp_name_add (suffix);
768}
769
770/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
771
772unsigned
773tree_num_loop_insns (struct loop *loop, eni_weights *weights)
774{
775 basic_block *body = get_loop_body (loop);
776 gimple_stmt_iterator gsi;
777 unsigned size = 0, i;
778
779 for (i = 0; i < loop->num_nodes; i++)
780 for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
781 size += estimate_num_insns (gsi_stmt (gsi), weights);
782 free (body);
783
784 return size;
785}
786
787
788
789