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