gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003 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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "basic-block.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "tree-pass.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "flags.h"
  39 #include "tree-inline.h"
  40 #include "tree-scalar-evolution.h"
  41
  42 /* The loop tree currently optimized.  */
  43
  44 struct loops *current_loops;
  45
  46 /* Initializes the loop structures.  DUMP is the file to that the details
  47    about the analysis should be dumped.  */
  48
  49 static struct loops *
  50 tree_loop_optimizer_init (FILE *dump)
  51 {
  52   struct loops *loops = loop_optimizer_init (dump);
  53
  54   if (!loops)
  55     return NULL;
  56
  57   /* Creation of preheaders may create redundant phi nodes if the loop is
  58      entered by more than one edge, but the initial value of the induction
  59      variable is the same on all of them.  */
  60   kill_redundant_phi_nodes ();
  61   rewrite_into_ssa (false);
  62   bitmap_clear (vars_to_rename);
  63
  64   rewrite_into_loop_closed_ssa ();
  65 #ifdef ENABLE_CHECKING
  66   verify_loop_closed_ssa ();
  67 #endif
  68
  69   return loops;
  70 }
  71
  72 /* The loop superpass.  */
  73
  74 static bool
  75 gate_loop (void)
  76 {
  77   return flag_tree_loop_optimize != 0;
  78 }
  79
  80 struct tree_opt_pass pass_loop =
  81 {
  82   "loop",                               /* name */
  83   gate_loop,                            /* gate */
  84   NULL,                                 /* execute */
  85   NULL,                                 /* sub */
  86   NULL,                                 /* next */
  87   0,                                    /* static_pass_number */
  88   TV_TREE_LOOP,                         /* tv_id */
  89   PROP_cfg,                             /* properties_required */
  90   0,                                    /* properties_provided */
  91   0,                                    /* properties_destroyed */
  92   TODO_ggc_collect,                     /* todo_flags_start */
  93   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect   /* todo_flags_finish */
  94 };
  95
  96 /* Loop optimizer initialization.  */
  97
  98 static void
  99 tree_ssa_loop_init (void)
 100 {
 101   current_loops = tree_loop_optimizer_init (dump_file);
 102   if (!current_loops)
 103     return;
 104   scev_initialize (current_loops);
 105 }
 106
 107 struct tree_opt_pass pass_loop_init =
 108 {
 109   "loopinit",                           /* name */
 110   NULL,                                 /* gate */
 111   tree_ssa_loop_init,                   /* execute */
 112   NULL,                                 /* sub */
 113   NULL,                                 /* next */
 114   0,                                    /* static_pass_number */
 115   0,                                    /* tv_id */
 116   PROP_cfg,                             /* properties_required */
 117   0,                                    /* properties_provided */
 118   0,                                    /* properties_destroyed */
 119   0,                                    /* todo_flags_start */
 120   0                                     /* todo_flags_finish */
 121 };
 122
 123 /* Loop invariant motion pass.  */
 124
 125 static void
 126 tree_ssa_loop_im (void)
 127 {
 128   if (!current_loops)
 129     return;
 130
 131   tree_ssa_lim (current_loops);
 132 }
 133
 134 static bool
 135 gate_tree_ssa_loop_im (void)
 136 {
 137   return flag_tree_lim != 0;
 138 }
 139
 140 struct tree_opt_pass pass_lim =
 141 {
 142   "lim",                                /* name */
 143   gate_tree_ssa_loop_im,                /* gate */
 144   tree_ssa_loop_im,                     /* execute */
 145   NULL,                                 /* sub */
 146   NULL,                                 /* next */
 147   0,                                    /* static_pass_number */
 148   TV_LIM,                               /* tv_id */
 149   PROP_cfg,                             /* properties_required */
 150   0,                                    /* properties_provided */
 151   0,                                    /* properties_destroyed */
 152   0,                                    /* todo_flags_start */
 153   TODO_dump_func                        /* todo_flags_finish */
 154 };
 155
 156 /* Loop autovectorization.  */
 157
 158 static void
 159 tree_vectorize (void)
 160 {
 161   if (!current_loops)
 162     return;
 163
 164   bitmap_clear (vars_to_rename);
 165   vectorize_loops (current_loops);
 166 }
 167
 168 static bool
 169 gate_tree_vectorize (void)
 170 {
 171   return flag_tree_vectorize != 0;
 172 }
 173
 174 struct tree_opt_pass pass_vectorize =
 175 {
 176   "vect",                               /* name */
 177   gate_tree_vectorize,                  /* gate */
 178   tree_vectorize,                       /* execute */
 179   NULL,                                 /* sub */
 180   NULL,                                 /* next */
 181   0,                                    /* static_pass_number */
 182   TV_TREE_VECTORIZATION,                /* tv_id */
 183   PROP_cfg | PROP_ssa,                  /* properties_required */
 184   0,                                    /* properties_provided */
 185   0,                                    /* properties_destroyed */
 186   0,                                    /* todo_flags_start */
 187   TODO_dump_func                        /* todo_flags_finish */
 188 };
 189
 190 /* Loop optimizer finalization.  */
 191
 192 static void
 193 tree_ssa_loop_done (void)
 194 {
 195   if (!current_loops)
 196     return;
 197
 198   scev_finalize ();
 199
 200 #ifdef ENABLE_CHECKING
 201   verify_loop_closed_ssa ();
 202 #endif
 203
 204   loop_optimizer_finalize (current_loops,
 205                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 206   current_loops = NULL;
 207   cleanup_tree_cfg ();
 208 }
 209
 210 struct tree_opt_pass pass_loop_done =
 211 {
 212   "loopdone",                           /* name */
 213   NULL,                                 /* gate */
 214   tree_ssa_loop_done,                   /* execute */
 215   NULL,                                 /* sub */
 216   NULL,                                 /* next */
 217   0,                                    /* static_pass_number */
 218   0,                                    /* tv_id */
 219   PROP_cfg,                             /* properties_required */
 220   0,                                    /* properties_provided */
 221   0,                                    /* properties_destroyed */
 222   0,                                    /* todo_flags_start */
 223   0                                     /* todo_flags_finish */
 224 };
 225