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
 198 /* Loop nest optimizations.  */
 199
 200 static void
 201 tree_linear_transform (void)
 202 {
 203   if (!current_loops)
 204     return;
 205
 206   linear_transform_loops (current_loops);
 207 }
 208
 209 static bool
 210 gate_tree_linear_transform (void)
 211 {
 212   return flag_tree_loop_linear != 0;
 213 }
 214
 215 struct tree_opt_pass pass_linear_transform =
 216 {
 217   "ltrans",                             /* name */
 218   gate_tree_linear_transform,           /* gate */
 219   tree_linear_transform,                /* execute */
 220   NULL,                                 /* sub */
 221   NULL,                                 /* next */
 222   0,                                    /* static_pass_number */
 223   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 224   PROP_cfg | PROP_ssa,                  /* properties_required */
 225   0,                                    /* properties_provided */
 226   0,                                    /* properties_destroyed */
 227   0,                                    /* todo_flags_start */
 228   TODO_dump_func,                       /* todo_flags_finish */
 229   0                                     /* letter */
 230 };
 231
 232 /* Canonical induction variable creation pass.  */
 233
 234 static void
 235 tree_ssa_loop_ivcanon (void)
 236 {
 237   if (!current_loops)
 238     return;
 239
 240   canonicalize_induction_variables (current_loops);
 241 }
 242
 243 static bool
 244 gate_tree_ssa_loop_ivcanon (void)
 245 {
 246   return flag_tree_loop_ivcanon != 0;
 247 }
 248
 249 struct tree_opt_pass pass_iv_canon =
 250 {
 251   "ivcanon",                            /* name */
 252   gate_tree_ssa_loop_ivcanon,           /* gate */
 253   tree_ssa_loop_ivcanon,                /* execute */
 254   NULL,                                 /* sub */
 255   NULL,                                 /* next */
 256   0,                                    /* static_pass_number */
 257   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 258   PROP_cfg | PROP_ssa,                  /* properties_required */
 259   0,                                    /* properties_provided */
 260   0,                                    /* properties_destroyed */
 261   0,                                    /* todo_flags_start */
 262   TODO_dump_func,                       /* todo_flags_finish */
 263   0                                     /* letter */
 264 };
 265
 266 /* Complete unrolling of loops.  */
 267
 268 static void
 269 tree_complete_unroll (void)
 270 {
 271   if (!current_loops)
 272     return;
 273
 274   tree_unroll_loops_completely (current_loops);
 275 }
 276
 277 static bool
 278 gate_tree_complete_unroll (void)
 279 {
 280   return flag_unroll_loops != 0;
 281 }
 282
 283 struct tree_opt_pass pass_complete_unroll =
 284 {
 285   "cunroll",                            /* name */
 286   gate_tree_complete_unroll,            /* gate */
 287   tree_complete_unroll,                 /* execute */
 288   NULL,                                 /* sub */
 289   NULL,                                 /* next */
 290   0,                                    /* static_pass_number */
 291   TV_COMPLETE_UNROLL,                   /* tv_id */
 292   PROP_cfg | PROP_ssa,                  /* properties_required */
 293   0,                                    /* properties_provided */
 294   0,                                    /* properties_destroyed */
 295   0,                                    /* todo_flags_start */
 296   TODO_dump_func,                       /* todo_flags_finish */
 297   0                                     /* letter */
 298 };
 299
 300 /* Induction variable optimizations.  */
 301
 302 static void
 303 tree_ssa_loop_ivopts (void)
 304 {
 305   if (!current_loops)
 306     return;
 307
 308   tree_ssa_iv_optimize (current_loops);
 309 }
 310
 311 static bool
 312 gate_tree_ssa_loop_ivopts (void)
 313 {
 314   return flag_ivopts != 0;
 315 }
 316
 317 struct tree_opt_pass pass_iv_optimize =
 318 {
 319   "ivopts",                             /* name */
 320   gate_tree_ssa_loop_ivopts,            /* gate */
 321   tree_ssa_loop_ivopts,                 /* execute */
 322   NULL,                                 /* sub */
 323   NULL,                                 /* next */
 324   0,                                    /* static_pass_number */
 325   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 326   PROP_cfg | PROP_ssa,                  /* properties_required */
 327   0,                                    /* properties_provided */
 328   0,                                    /* properties_destroyed */
 329   0,                                    /* todo_flags_start */
 330   TODO_dump_func,                       /* todo_flags_finish */
 331   0                                     /* letter */
 332 };
 333
 334 /* Loop optimizer finalization.  */
 335
 336 static void
 337 tree_ssa_loop_done (void)
 338 {
 339   if (!current_loops)
 340     return;
 341
 342 #ifdef ENABLE_CHECKING
 343   verify_loop_closed_ssa ();
 344 #endif
 345
 346   free_numbers_of_iterations_estimates (current_loops);
 347   scev_finalize ();
 348   loop_optimizer_finalize (current_loops,
 349                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 350   current_loops = NULL;
 351   cleanup_tree_cfg ();
 352 }
 353
 354 struct tree_opt_pass pass_loop_done =
 355 {
 356   "loopdone",                           /* name */
 357   NULL,                                 /* gate */
 358   tree_ssa_loop_done,                   /* execute */
 359   NULL,                                 /* sub */
 360   NULL,                                 /* next */
 361   0,                                    /* static_pass_number */
 362   0,                                    /* tv_id */
 363   PROP_cfg,                             /* properties_required */
 364   0,                                    /* properties_provided */
 365   0,                                    /* properties_destroyed */
 366   0,                                    /* todo_flags_start */
 367   TODO_dump_func,                       /* todo_flags_finish */
 368   0                                     /* letter */
 369 };
 370