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 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 /* Complete unrolling of loops.  */
 301
 302 static void
 303 tree_complete_unroll (void)
 304 {
 305   if (!current_loops)
 306     return;
 307
 308   tree_unroll_loops_completely (current_loops);
 309 }
 310
 311 static bool
 312 gate_tree_complete_unroll (void)
 313 {
 314   return flag_unroll_loops != 0;
 315 }
 316
 317 struct tree_opt_pass pass_complete_unroll =
 318 {
 319   "cunroll",                            /* name */
 320   gate_tree_complete_unroll,            /* gate */
 321   tree_complete_unroll,                 /* execute */
 322   NULL,                                 /* sub */
 323   NULL,                                 /* next */
 324   0,                                    /* static_pass_number */
 325   TV_COMPLETE_UNROLL,                   /* 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 /* Induction variable optimizations.  */
 335
 336 static void
 337 tree_ssa_loop_ivopts (void)
 338 {
 339   if (!current_loops)
 340     return;
 341
 342   tree_ssa_iv_optimize (current_loops);
 343 }
 344
 345 static bool
 346 gate_tree_ssa_loop_ivopts (void)
 347 {
 348   return flag_ivopts != 0;
 349 }
 350
 351 struct tree_opt_pass pass_iv_optimize =
 352 {
 353   "ivopts",                             /* name */
 354   gate_tree_ssa_loop_ivopts,            /* gate */
 355   tree_ssa_loop_ivopts,                 /* execute */
 356   NULL,                                 /* sub */
 357   NULL,                                 /* next */
 358   0,                                    /* static_pass_number */
 359   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 360   PROP_cfg | PROP_ssa,                  /* properties_required */
 361   0,                                    /* properties_provided */
 362   0,                                    /* properties_destroyed */
 363   0,                                    /* todo_flags_start */
 364   TODO_dump_func,                       /* todo_flags_finish */
 365   0                                     /* letter */
 366 };
 367
 368 /* Loop optimizer finalization.  */
 369
 370 static void
 371 tree_ssa_loop_done (void)
 372 {
 373   if (!current_loops)
 374     return;
 375
 376 #ifdef ENABLE_CHECKING
 377   verify_loop_closed_ssa ();
 378 #endif
 379
 380   free_numbers_of_iterations_estimates (current_loops);
 381   scev_finalize ();
 382   loop_optimizer_finalize (current_loops,
 383                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 384   current_loops = NULL;
 385   cleanup_tree_cfg ();
 386 }
 387
 388 struct tree_opt_pass pass_loop_done =
 389 {
 390   "loopdone",                           /* name */
 391   NULL,                                 /* gate */
 392   tree_ssa_loop_done,                   /* execute */
 393   NULL,                                 /* sub */
 394   NULL,                                 /* next */
 395   0,                                    /* static_pass_number */
 396   0,                                    /* tv_id */
 397   PROP_cfg,                             /* properties_required */
 398   0,                                    /* properties_provided */
 399   0,                                    /* properties_destroyed */
 400   0,                                    /* todo_flags_start */
 401   TODO_dump_func,                       /* todo_flags_finish */
 402   0                                     /* letter */
 403 };
 404