1/* Loop optimizations over tree-ssa.
2   Copyright (C) 2003-2015 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 "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
64namespace {
65
66const 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
79class pass_fix_loops : public gimple_opt_pass
80{
81public:
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
92unsigned int
93pass_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
105gimple_opt_pass *
106make_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
115static bool
116gate_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
131namespace {
132
133const 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
146class pass_tree_loop : public gimple_opt_pass
147{
148public:
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
160gimple_opt_pass *
161make_pass_tree_loop (gcc::context *ctxt)
162{
163  return new pass_tree_loop (ctxt);
164}
165
166/* The no-loop superpass.  */
167
168namespace {
169
170const 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
183class pass_tree_no_loop : public gimple_opt_pass
184{
185public:
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
197gimple_opt_pass *
198make_pass_tree_no_loop (gcc::context *ctxt)
199{
200  return new pass_tree_no_loop (ctxt);
201}
202
203
204/* Loop optimizer initialization.  */
205
206namespace {
207
208const 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
221class pass_tree_loop_init : public gimple_opt_pass
222{
223public:
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
233unsigned int
234pass_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
249gimple_opt_pass *
250make_pass_tree_loop_init (gcc::context *ctxt)
251{
252  return new pass_tree_loop_init (ctxt);
253}
254
255/* Loop autovectorization.  */
256
257namespace {
258
259const 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
272class pass_vectorize : public gimple_opt_pass
273{
274public:
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
289unsigned int
290pass_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
300gimple_opt_pass *
301make_pass_vectorize (gcc::context *ctxt)
302{
303  return new pass_vectorize (ctxt);
304}
305
306/* Check the correctness of the data dependence analyzers.  */
307
308namespace {
309
310const 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
323class pass_check_data_deps : public gimple_opt_pass
324{
325public:
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
336unsigned int
337pass_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
348gimple_opt_pass *
349make_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
356namespace {
357
358const 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
372class pass_scev_cprop : public gimple_opt_pass
373{
374public:
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
387gimple_opt_pass *
388make_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
395namespace {
396
397const 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
410class pass_record_bounds : public gimple_opt_pass
411{
412public:
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
422unsigned int
423pass_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
435gimple_opt_pass *
436make_pass_record_bounds (gcc::context *ctxt)
437{
438  return new pass_record_bounds (ctxt);
439}
440
441/* Induction variable optimizations.  */
442
443namespace {
444
445const 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
458class pass_iv_optimize : public gimple_opt_pass
459{
460public:
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
471unsigned int
472pass_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
483gimple_opt_pass *
484make_pass_iv_optimize (gcc::context *ctxt)
485{
486  return new pass_iv_optimize (ctxt);
487}
488
489/* Loop optimizer finalization.  */
490
491static unsigned int
492tree_ssa_loop_done (void)
493{
494  free_numbers_of_iterations_estimates ();
495  scev_finalize ();
496  loop_optimizer_finalize ();
497  return 0;
498}
499
500namespace {
501
502const 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
515class pass_tree_loop_done : public gimple_opt_pass
516{
517public:
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
529gimple_opt_pass *
530make_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
549bool
550for_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
632static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
633static int lsm_tmp_name_length;
634
635/* Adds S to lsm_tmp_name.  */
636
637static void
638lsm_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
651static void
652gen_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    case FUNCTION_DECL:
702    case LABEL_DECL:
703      name = get_name (ref);
704      if (!name)
705	name = "D";
706      lsm_tmp_name_add (name);
707      break;
708
709    case STRING_CST:
710      lsm_tmp_name_add ("S");
711      break;
712
713    case RESULT_DECL:
714      lsm_tmp_name_add ("R");
715      break;
716
717    case INTEGER_CST:
718    default:
719      /* Nothing.  */
720      break;
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
728char *
729get_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
749unsigned
750tree_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
766