gcc/tree-ssa-loop.c

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