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