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   TV_TREE_LOOP_INIT,                    /* 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 unswitching pass.  */
 163
 164 static void
 165 tree_ssa_loop_unswitch (void)
 166 {
 167   if (!current_loops)
 168     return;
 169
 170   tree_ssa_unswitch_loops (current_loops);
 171 }
 172
 173 static bool
 174 gate_tree_ssa_loop_unswitch (void)
 175 {
 176   return flag_unswitch_loops != 0;
 177 }
 178
 179 struct tree_opt_pass pass_unswitch =
 180 {
 181   "unswitch",                           /* name */
 182   gate_tree_ssa_loop_unswitch,          /* gate */
 183   tree_ssa_loop_unswitch,               /* execute */
 184   NULL,                                 /* sub */
 185   NULL,                                 /* next */
 186   0,                                    /* static_pass_number */
 187   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 188   PROP_cfg,                             /* properties_required */
 189   0,                                    /* properties_provided */
 190   0,                                    /* properties_destroyed */
 191   0,                                    /* todo_flags_start */
 192   TODO_dump_func,                       /* todo_flags_finish */
 193   0                                     /* letter */
 194 };
 195
 196 /* Loop autovectorization.  */
 197
 198 static void
 199 tree_vectorize (void)
 200 {
 201   if (!current_loops)
 202     return;
 203
 204   bitmap_clear (vars_to_rename);
 205   vectorize_loops (current_loops);
 206 }
 207
 208 static bool
 209 gate_tree_vectorize (void)
 210 {
 211   return flag_tree_vectorize != 0;
 212 }
 213
 214 struct tree_opt_pass pass_vectorize =
 215 {
 216   "vect",                               /* name */
 217   gate_tree_vectorize,                  /* gate */
 218   tree_vectorize,                       /* execute */
 219   NULL,                                 /* sub */
 220   NULL,                                 /* next */
 221   0,                                    /* static_pass_number */
 222   TV_TREE_VECTORIZATION,                /* 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
 232 /* Loop nest optimizations.  */
 233
 234 static void
 235 tree_linear_transform (void)
 236 {
 237   if (!current_loops)
 238     return;
 239
 240   linear_transform_loops (current_loops);
 241 }
 242
 243 static bool
 244 gate_tree_linear_transform (void)
 245 {
 246   return flag_tree_loop_linear != 0;
 247 }
 248
 249 struct tree_opt_pass pass_linear_transform =
 250 {
 251   "ltrans",                             /* name */
 252   gate_tree_linear_transform,           /* gate */
 253   tree_linear_transform,                /* execute */
 254   NULL,                                 /* sub */
 255   NULL,                                 /* next */
 256   0,                                    /* static_pass_number */
 257   TV_TREE_LINEAR_TRANSFORM,             /* 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 /* Canonical induction variable creation pass.  */
 267
 268 static void
 269 tree_ssa_loop_ivcanon (void)
 270 {
 271   if (!current_loops)
 272     return;
 273
 274   canonicalize_induction_variables (current_loops);
 275 }
 276
 277 static bool
 278 gate_tree_ssa_loop_ivcanon (void)
 279 {
 280   return flag_tree_loop_ivcanon != 0;
 281 }
 282
 283 struct tree_opt_pass pass_iv_canon =
 284 {
 285   "ivcanon",                            /* name */
 286   gate_tree_ssa_loop_ivcanon,           /* gate */
 287   tree_ssa_loop_ivcanon,                /* execute */
 288   NULL,                                 /* sub */
 289   NULL,                                 /* next */
 290   0,                                    /* static_pass_number */
 291   TV_TREE_LOOP_IVCANON,                 /* 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 /* Record bounds on numbers of iterations of loops.  */
 301
 302 static void
 303 tree_ssa_loop_bounds (void)
 304 {
 305   if (!current_loops)
 306     return;
 307
 308   estimate_numbers_of_iterations (current_loops);
 309   scev_reset ();
 310 }
 311
 312 struct tree_opt_pass pass_record_bounds =
 313 {
 314   NULL,                                 /* name */
 315   NULL,                                 /* gate */
 316   tree_ssa_loop_bounds,                 /* execute */
 317   NULL,                                 /* sub */
 318   NULL,                                 /* next */
 319   0,                                    /* static_pass_number */
 320   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 321   PROP_cfg | PROP_ssa,                  /* properties_required */
 322   0,                                    /* properties_provided */
 323   0,                                    /* properties_destroyed */
 324   0,                                    /* todo_flags_start */
 325   0,                                    /* todo_flags_finish */
 326   0                                     /* letter */
 327 };
 328
 329 /* Complete unrolling of loops.  */
 330
 331 static void
 332 tree_complete_unroll (void)
 333 {
 334   if (!current_loops)
 335     return;
 336
 337   tree_unroll_loops_completely (current_loops);
 338 }
 339
 340 static bool
 341 gate_tree_complete_unroll (void)
 342 {
 343   return flag_unroll_loops != 0;
 344 }
 345
 346 struct tree_opt_pass pass_complete_unroll =
 347 {
 348   "cunroll",                            /* name */
 349   gate_tree_complete_unroll,            /* gate */
 350   tree_complete_unroll,                 /* execute */
 351   NULL,                                 /* sub */
 352   NULL,                                 /* next */
 353   0,                                    /* static_pass_number */
 354   TV_COMPLETE_UNROLL,                   /* tv_id */
 355   PROP_cfg | PROP_ssa,                  /* properties_required */
 356   0,                                    /* properties_provided */
 357   0,                                    /* properties_destroyed */
 358   0,                                    /* todo_flags_start */
 359   TODO_dump_func,                       /* todo_flags_finish */
 360   0                                     /* letter */
 361 };
 362
 363 /* Induction variable optimizations.  */
 364
 365 static void
 366 tree_ssa_loop_ivopts (void)
 367 {
 368   if (!current_loops)
 369     return;
 370
 371   tree_ssa_iv_optimize (current_loops);
 372 }
 373
 374 static bool
 375 gate_tree_ssa_loop_ivopts (void)
 376 {
 377   return flag_ivopts != 0;
 378 }
 379
 380 struct tree_opt_pass pass_iv_optimize =
 381 {
 382   "ivopts",                             /* name */
 383   gate_tree_ssa_loop_ivopts,            /* gate */
 384   tree_ssa_loop_ivopts,                 /* execute */
 385   NULL,                                 /* sub */
 386   NULL,                                 /* next */
 387   0,                                    /* static_pass_number */
 388   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 389   PROP_cfg | PROP_ssa,                  /* properties_required */
 390   0,                                    /* properties_provided */
 391   0,                                    /* properties_destroyed */
 392   0,                                    /* todo_flags_start */
 393   TODO_dump_func,                       /* todo_flags_finish */
 394   0                                     /* letter */
 395 };
 396
 397 /* Loop optimizer finalization.  */
 398
 399 static void
 400 tree_ssa_loop_done (void)
 401 {
 402   if (!current_loops)
 403     return;
 404
 405 #ifdef ENABLE_CHECKING
 406   verify_loop_closed_ssa ();
 407 #endif
 408
 409   free_numbers_of_iterations_estimates (current_loops);
 410   scev_finalize ();
 411   loop_optimizer_finalize (current_loops,
 412                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 413   current_loops = NULL;
 414 }
 415
 416 struct tree_opt_pass pass_loop_done =
 417 {
 418   "loopdone",                           /* name */
 419   NULL,                                 /* gate */
 420   tree_ssa_loop_done,                   /* execute */
 421   NULL,                                 /* sub */
 422   NULL,                                 /* next */
 423   0,                                    /* static_pass_number */
 424   TV_TREE_LOOP_FINI,                    /* tv_id */
 425   PROP_cfg,                             /* properties_required */
 426   0,                                    /* properties_provided */
 427   0,                                    /* properties_destroyed */
 428   0,                                    /* todo_flags_start */
 429   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 430   0                                     /* letter */
 431 };
 432