gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003, 2005 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   update_ssa (TODO_update_ssa);
  57   rewrite_into_loop_closed_ssa (NULL);
  58
  59   return loops;
  60 }
  61
  62 /* The loop superpass.  */
  63
  64 static bool
  65 gate_loop (void)
  66 {
  67   return flag_tree_loop_optimize != 0;
  68 }
  69
  70 struct tree_opt_pass pass_loop =
  71 {
  72   "loop",                               /* name */
  73   gate_loop,                            /* gate */
  74   NULL,                                 /* execute */
  75   NULL,                                 /* sub */
  76   NULL,                                 /* next */
  77   0,                                    /* static_pass_number */
  78   TV_TREE_LOOP,                         /* tv_id */
  79   PROP_cfg,                             /* properties_required */
  80   0,                                    /* properties_provided */
  81   0,                                    /* properties_destroyed */
  82   TODO_ggc_collect,                     /* todo_flags_start */
  83   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
  84   0                                     /* letter */
  85 };
  86
  87 /* Loop optimizer initialization.  */
  88
  89 static void
  90 tree_ssa_loop_init (void)
  91 {
  92   current_loops = tree_loop_optimizer_init (dump_file);
  93   if (!current_loops)
  94     return;
  95
  96   /* Find the loops that are exited just through a single edge.  */
  97   mark_single_exit_loops (current_loops);
  98
  99   scev_initialize (current_loops);
 100 }
 101
 102 struct tree_opt_pass pass_loop_init =
 103 {
 104   "loopinit",                           /* name */
 105   NULL,                                 /* gate */
 106   tree_ssa_loop_init,                   /* execute */
 107   NULL,                                 /* sub */
 108   NULL,                                 /* next */
 109   0,                                    /* static_pass_number */
 110   TV_TREE_LOOP_INIT,                    /* tv_id */
 111   PROP_cfg,                             /* properties_required */
 112   0,                                    /* properties_provided */
 113   0,                                    /* properties_destroyed */
 114   0,                                    /* todo_flags_start */
 115   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 116   0                                     /* letter */
 117 };
 118
 119 /* Loop invariant motion pass.  */
 120
 121 static void
 122 tree_ssa_loop_im (void)
 123 {
 124   if (!current_loops)
 125     return;
 126
 127   tree_ssa_lim (current_loops);
 128 }
 129
 130 static bool
 131 gate_tree_ssa_loop_im (void)
 132 {
 133   return flag_tree_loop_im != 0;
 134 }
 135
 136 struct tree_opt_pass pass_lim =
 137 {
 138   "lim",                                /* name */
 139   gate_tree_ssa_loop_im,                /* gate */
 140   tree_ssa_loop_im,                     /* execute */
 141   NULL,                                 /* sub */
 142   NULL,                                 /* next */
 143   0,                                    /* static_pass_number */
 144   TV_LIM,                               /* tv_id */
 145   PROP_cfg,                             /* properties_required */
 146   0,                                    /* properties_provided */
 147   0,                                    /* properties_destroyed */
 148   0,                                    /* todo_flags_start */
 149   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 150   0                                     /* letter */
 151 };
 152
 153 /* Loop unswitching pass.  */
 154
 155 static void
 156 tree_ssa_loop_unswitch (void)
 157 {
 158   if (!current_loops)
 159     return;
 160
 161   tree_ssa_unswitch_loops (current_loops);
 162 }
 163
 164 static bool
 165 gate_tree_ssa_loop_unswitch (void)
 166 {
 167   return flag_unswitch_loops != 0;
 168 }
 169
 170 struct tree_opt_pass pass_unswitch =
 171 {
 172   "unswitch",                           /* name */
 173   gate_tree_ssa_loop_unswitch,          /* gate */
 174   tree_ssa_loop_unswitch,               /* execute */
 175   NULL,                                 /* sub */
 176   NULL,                                 /* next */
 177   0,                                    /* static_pass_number */
 178   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 179   PROP_cfg,                             /* properties_required */
 180   0,                                    /* properties_provided */
 181   0,                                    /* properties_destroyed */
 182   0,                                    /* todo_flags_start */
 183   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 184   0                                     /* letter */
 185 };
 186
 187 /* Loop autovectorization.  */
 188
 189 static void
 190 tree_vectorize (void)
 191 {
 192   if (!current_loops)
 193     return;
 194
 195   vectorize_loops (current_loops);
 196 }
 197
 198 static bool
 199 gate_tree_vectorize (void)
 200 {
 201   return flag_tree_vectorize != 0;
 202 }
 203
 204 struct tree_opt_pass pass_vectorize =
 205 {
 206   "vect",                               /* name */
 207   gate_tree_vectorize,                  /* gate */
 208   tree_vectorize,                       /* execute */
 209   NULL,                                 /* sub */
 210   NULL,                                 /* next */
 211   0,                                    /* static_pass_number */
 212   TV_TREE_VECTORIZATION,                /* tv_id */
 213   PROP_cfg | PROP_ssa,                  /* properties_required */
 214   0,                                    /* properties_provided */
 215   0,                                    /* properties_destroyed */
 216   0,                                    /* todo_flags_start */
 217   TODO_dump_func | TODO_update_ssa,     /* todo_flags_finish */
 218   0                                     /* letter */
 219 };
 220
 221
 222 /* Loop nest optimizations.  */
 223
 224 static void
 225 tree_linear_transform (void)
 226 {
 227   if (!current_loops)
 228     return;
 229
 230   linear_transform_loops (current_loops);
 231 }
 232
 233 static bool
 234 gate_tree_linear_transform (void)
 235 {
 236   return flag_tree_loop_linear != 0;
 237 }
 238
 239 struct tree_opt_pass pass_linear_transform =
 240 {
 241   "ltrans",                             /* name */
 242   gate_tree_linear_transform,           /* gate */
 243   tree_linear_transform,                /* execute */
 244   NULL,                                 /* sub */
 245   NULL,                                 /* next */
 246   0,                                    /* static_pass_number */
 247   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 248   PROP_cfg | PROP_ssa,                  /* properties_required */
 249   0,                                    /* properties_provided */
 250   0,                                    /* properties_destroyed */
 251   0,                                    /* todo_flags_start */
 252   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 253   0                                     /* letter */
 254 };
 255
 256 /* Canonical induction variable creation pass.  */
 257
 258 static void
 259 tree_ssa_loop_ivcanon (void)
 260 {
 261   if (!current_loops)
 262     return;
 263
 264   canonicalize_induction_variables (current_loops);
 265 }
 266
 267 static bool
 268 gate_tree_ssa_loop_ivcanon (void)
 269 {
 270   return flag_tree_loop_ivcanon != 0;
 271 }
 272
 273 struct tree_opt_pass pass_iv_canon =
 274 {
 275   "ivcanon",                            /* name */
 276   gate_tree_ssa_loop_ivcanon,           /* gate */
 277   tree_ssa_loop_ivcanon,                /* execute */
 278   NULL,                                 /* sub */
 279   NULL,                                 /* next */
 280   0,                                    /* static_pass_number */
 281   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 282   PROP_cfg | PROP_ssa,                  /* properties_required */
 283   0,                                    /* properties_provided */
 284   0,                                    /* properties_destroyed */
 285   0,                                    /* todo_flags_start */
 286   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 287   0                                     /* letter */
 288 };
 289
 290 /* Record bounds on numbers of iterations of loops.  */
 291
 292 static void
 293 tree_ssa_loop_bounds (void)
 294 {
 295   if (!current_loops)
 296     return;
 297
 298   estimate_numbers_of_iterations (current_loops);
 299   scev_reset ();
 300 }
 301
 302 struct tree_opt_pass pass_record_bounds =
 303 {
 304   NULL,                                 /* name */
 305   NULL,                                 /* gate */
 306   tree_ssa_loop_bounds,                 /* execute */
 307   NULL,                                 /* sub */
 308   NULL,                                 /* next */
 309   0,                                    /* static_pass_number */
 310   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 311   PROP_cfg | PROP_ssa,                  /* properties_required */
 312   0,                                    /* properties_provided */
 313   0,                                    /* properties_destroyed */
 314   0,                                    /* todo_flags_start */
 315   0,                                    /* todo_flags_finish */
 316   0                                     /* letter */
 317 };
 318
 319 /* Complete unrolling of loops.  */
 320
 321 static void
 322 tree_complete_unroll (void)
 323 {
 324   if (!current_loops)
 325     return;
 326
 327   tree_unroll_loops_completely (current_loops);
 328 }
 329
 330 static bool
 331 gate_tree_complete_unroll (void)
 332 {
 333   return flag_peel_loops || flag_unroll_loops;
 334 }
 335
 336 struct tree_opt_pass pass_complete_unroll =
 337 {
 338   "cunroll",                            /* name */
 339   gate_tree_complete_unroll,            /* gate */
 340   tree_complete_unroll,                 /* execute */
 341   NULL,                                 /* sub */
 342   NULL,                                 /* next */
 343   0,                                    /* static_pass_number */
 344   TV_COMPLETE_UNROLL,                   /* tv_id */
 345   PROP_cfg | PROP_ssa,                  /* properties_required */
 346   0,                                    /* properties_provided */
 347   0,                                    /* properties_destroyed */
 348   0,                                    /* todo_flags_start */
 349   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 350   0                                     /* letter */
 351 };
 352
 353 /* Induction variable optimizations.  */
 354
 355 static void
 356 tree_ssa_loop_ivopts (void)
 357 {
 358   if (!current_loops)
 359     return;
 360
 361   tree_ssa_iv_optimize (current_loops);
 362 }
 363
 364 static bool
 365 gate_tree_ssa_loop_ivopts (void)
 366 {
 367   return flag_ivopts != 0;
 368 }
 369
 370 struct tree_opt_pass pass_iv_optimize =
 371 {
 372   "ivopts",                             /* name */
 373   gate_tree_ssa_loop_ivopts,            /* gate */
 374   tree_ssa_loop_ivopts,                 /* execute */
 375   NULL,                                 /* sub */
 376   NULL,                                 /* next */
 377   0,                                    /* static_pass_number */
 378   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 379   PROP_cfg | PROP_ssa,                  /* properties_required */
 380   0,                                    /* properties_provided */
 381   0,                                    /* properties_destroyed */
 382   0,                                    /* todo_flags_start */
 383   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 384   0                                     /* letter */
 385 };
 386
 387 /* Loop optimizer finalization.  */
 388
 389 static void
 390 tree_ssa_loop_done (void)
 391 {
 392   if (!current_loops)
 393     return;
 394
 395   free_numbers_of_iterations_estimates (current_loops);
 396   scev_finalize ();
 397   loop_optimizer_finalize (current_loops,
 398                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 399   current_loops = NULL;
 400 }
 401
 402 struct tree_opt_pass pass_loop_done =
 403 {
 404   "loopdone",                           /* name */
 405   NULL,                                 /* gate */
 406   tree_ssa_loop_done,                   /* execute */
 407   NULL,                                 /* sub */
 408   NULL,                                 /* next */
 409   0,                                    /* static_pass_number */
 410   TV_TREE_LOOP_FINI,                    /* tv_id */
 411   PROP_cfg,                             /* properties_required */
 412   0,                                    /* properties_provided */
 413   0,                                    /* properties_destroyed */
 414   0,                                    /* todo_flags_start */
 415   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 416   0                                     /* letter */
 417 };