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 "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "tree-pass.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "flags.h"
  38 #include "tree-inline.h"
  39 #include "tree-scalar-evolution.h"
  40
  41 /* The loop tree currently optimized.  */
  42
  43 struct loops *current_loops;
  44
  45 /* Initializes the loop structures.  DUMP is the file to that the details
  46    about the analysis should be dumped.  */
  47
  48 static struct loops *
  49 tree_loop_optimizer_init (FILE *dump)
  50 {
  51   struct loops *loops = loop_optimizer_init (dump);
  52
  53   if (!loops)
  54     return NULL;
  55
  56   /* Creation of preheaders may create redundant phi nodes if the loop is
  57      entered by more than one edge, but the initial value of the induction
  58      variable is the same on all of them.  */
  59   kill_redundant_phi_nodes ();
  60   rewrite_into_ssa (false);
  61   bitmap_clear (vars_to_rename);
  62
  63   rewrite_into_loop_closed_ssa ();
  64 #ifdef ENABLE_CHECKING
  65   verify_loop_closed_ssa ();
  66 #endif
  67
  68   return loops;
  69 }
  70
  71 /* The loop superpass.  */
  72
  73 static bool
  74 gate_loop (void)
  75 {
  76   return flag_tree_loop_optimize != 0;
  77 }
  78
  79 struct tree_opt_pass pass_loop =
  80 {
  81   "loop",                               /* name */
  82   gate_loop,                            /* gate */
  83   NULL,                                 /* execute */
  84   NULL,                                 /* sub */
  85   NULL,                                 /* next */
  86   0,                                    /* static_pass_number */
  87   TV_TREE_LOOP,                         /* tv_id */
  88   PROP_cfg,                             /* properties_required */
  89   0,                                    /* properties_provided */
  90   0,                                    /* properties_destroyed */
  91   TODO_ggc_collect,                     /* todo_flags_start */
  92   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
  93   0                                     /* letter */
  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
 105   /* Find the loops that are exited just through a single edge.  */
 106   mark_single_exit_loops (current_loops);
 107
 108   scev_initialize (current_loops);
 109 }
 110
 111 struct tree_opt_pass pass_loop_init =
 112 {
 113   "loopinit",                           /* name */
 114   NULL,                                 /* gate */
 115   tree_ssa_loop_init,                   /* execute */
 116   NULL,                                 /* sub */
 117   NULL,                                 /* next */
 118   0,                                    /* static_pass_number */
 119   0,                                    /* tv_id */
 120   PROP_cfg,                             /* properties_required */
 121   0,                                    /* properties_provided */
 122   0,                                    /* properties_destroyed */
 123   0,                                    /* todo_flags_start */
 124   TODO_dump_func,                       /* todo_flags_finish */
 125   0                                     /* letter */
 126 };
 127
 128 /* Loop invariant motion pass.  */
 129
 130 static void
 131 tree_ssa_loop_im (void)
 132 {
 133   if (!current_loops)
 134     return;
 135
 136   tree_ssa_lim (current_loops);
 137 }
 138
 139 static bool
 140 gate_tree_ssa_loop_im (void)
 141 {
 142   return flag_tree_loop_im != 0;
 143 }
 144
 145 struct tree_opt_pass pass_lim =
 146 {
 147   "lim",                                /* name */
 148   gate_tree_ssa_loop_im,                /* gate */
 149   tree_ssa_loop_im,                     /* execute */
 150   NULL,                                 /* sub */
 151   NULL,                                 /* next */
 152   0,                                    /* static_pass_number */
 153   TV_LIM,                               /* tv_id */
 154   PROP_cfg,                             /* properties_required */
 155   0,                                    /* properties_provided */
 156   0,                                    /* properties_destroyed */
 157   0,                                    /* todo_flags_start */
 158   TODO_dump_func,                       /* todo_flags_finish */
 159   0                                     /* letter */
 160 };
 161
 162 /* Loop autovectorization.  */
 163
 164 static void
 165 tree_vectorize (void)
 166 {
 167   if (!current_loops)
 168     return;
 169
 170   bitmap_clear (vars_to_rename);
 171   vectorize_loops (current_loops);
 172 }
 173
 174 static bool
 175 gate_tree_vectorize (void)
 176 {
 177   return flag_tree_vectorize != 0;
 178 }
 179
 180 struct tree_opt_pass pass_vectorize =
 181 {
 182   "vect",                               /* name */
 183   gate_tree_vectorize,                  /* gate */
 184   tree_vectorize,                       /* execute */
 185   NULL,                                 /* sub */
 186   NULL,                                 /* next */
 187   0,                                    /* static_pass_number */
 188   TV_TREE_VECTORIZATION,                /* tv_id */
 189   PROP_cfg | PROP_ssa,                  /* properties_required */
 190   0,                                    /* properties_provided */
 191   0,                                    /* properties_destroyed */
 192   0,                                    /* todo_flags_start */
 193   TODO_dump_func,                       /* todo_flags_finish */
 194   0                                     /* letter */
 195 };
 196
 197 /* Canonical induction variable creation pass.  */
 198
 199 static void
 200 tree_ssa_loop_ivcanon (void)
 201 {
 202   if (!current_loops)
 203     return;
 204
 205   canonicalize_induction_variables (current_loops);
 206 }
 207
 208 static bool
 209 gate_tree_ssa_loop_ivcanon (void)
 210 {
 211   return flag_tree_loop_ivcanon != 0;
 212 }
 213
 214 struct tree_opt_pass pass_iv_canon =
 215 {
 216   "ivcanon",                            /* name */
 217   gate_tree_ssa_loop_ivcanon,           /* gate */
 218   tree_ssa_loop_ivcanon,                /* execute */
 219   NULL,                                 /* sub */
 220   NULL,                                 /* next */
 221   0,                                    /* static_pass_number */
 222   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 223   PROP_cfg | PROP_ssa,                  /* properties_required */
 224   0,                                    /* properties_provided */
 225   0,                                    /* properties_destroyed */
 226   0,                                    /* todo_flags_start */
 227   TODO_dump_func,                       /* todo_flags_finish */
 228   0                                     /* letter */
 229 };
 230
 231 /* Complete unrolling of loops.  */
 232
 233 static void
 234 tree_complete_unroll (void)
 235 {
 236   if (!current_loops)
 237     return;
 238
 239   tree_unroll_loops_completely (current_loops);
 240 }
 241
 242 static bool
 243 gate_tree_complete_unroll (void)
 244 {
 245   return flag_unroll_loops != 0;
 246 }
 247
 248 struct tree_opt_pass pass_complete_unroll =
 249 {
 250   "cunroll",                            /* name */
 251   gate_tree_complete_unroll,            /* gate */
 252   tree_complete_unroll,                 /* execute */
 253   NULL,                                 /* sub */
 254   NULL,                                 /* next */
 255   0,                                    /* static_pass_number */
 256   TV_COMPLETE_UNROLL,                   /* tv_id */
 257   PROP_cfg | PROP_ssa,                  /* properties_required */
 258   0,                                    /* properties_provided */
 259   0,                                    /* properties_destroyed */
 260   0,                                    /* todo_flags_start */
 261   TODO_dump_func,                       /* todo_flags_finish */
 262   0                                     /* letter */
 263 };
 264
 265 /* Induction variable optimizations.  */
 266
 267 static void
 268 tree_ssa_loop_ivopts (void)
 269 {
 270   if (!current_loops)
 271     return;
 272
 273   tree_ssa_iv_optimize (current_loops);
 274 }
 275
 276 static bool
 277 gate_tree_ssa_loop_ivopts (void)
 278 {
 279   return flag_ivopts != 0;
 280 }
 281
 282 struct tree_opt_pass pass_iv_optimize =
 283 {
 284   "ivopts",                             /* name */
 285   gate_tree_ssa_loop_ivopts,            /* gate */
 286   tree_ssa_loop_ivopts,                 /* execute */
 287   NULL,                                 /* sub */
 288   NULL,                                 /* next */
 289   0,                                    /* static_pass_number */
 290   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 291   PROP_cfg | PROP_ssa,                  /* properties_required */
 292   0,                                    /* properties_provided */
 293   0,                                    /* properties_destroyed */
 294   0,                                    /* todo_flags_start */
 295   TODO_dump_func,                       /* todo_flags_finish */
 296   0                                     /* letter */
 297 };
 298
 299 /* Loop optimizer finalization.  */
 300
 301 static void
 302 tree_ssa_loop_done (void)
 303 {
 304   if (!current_loops)
 305     return;
 306
 307 #ifdef ENABLE_CHECKING
 308   verify_loop_closed_ssa ();
 309 #endif
 310
 311   free_numbers_of_iterations_estimates (current_loops);
 312   scev_finalize ();
 313   loop_optimizer_finalize (current_loops,
 314                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 315   current_loops = NULL;
 316   cleanup_tree_cfg ();
 317 }
 318
 319 struct tree_opt_pass pass_loop_done =
 320 {
 321   "loopdone",                           /* name */
 322   NULL,                                 /* gate */
 323   tree_ssa_loop_done,                   /* execute */
 324   NULL,                                 /* sub */
 325   NULL,                                 /* next */
 326   0,                                    /* static_pass_number */
 327   0,                                    /* tv_id */
 328   PROP_cfg,                             /* properties_required */
 329   0,                                    /* properties_provided */
 330   0,                                    /* properties_destroyed */
 331   0,                                    /* todo_flags_start */
 332   TODO_dump_func,                       /* todo_flags_finish */
 333   0                                     /* letter */
 334 };
 335