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 gimple_opt_pass pass_tree_loop =
  59 {
  60  {
  61   GIMPLE_PASS,
  62   "loop",                               /* name */
  63   gate_tree_loop,                       /* gate */
  64   NULL,                                 /* execute */
  65   NULL,                                 /* sub */
  66   NULL,                                 /* next */
  67   0,                                    /* static_pass_number */
  68   TV_TREE_LOOP,                         /* tv_id */
  69   PROP_cfg,                             /* properties_required */
  70   0,                                    /* properties_provided */
  71   0,                                    /* properties_destroyed */
  72   TODO_ggc_collect,                     /* todo_flags_start */
  73   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect   /* todo_flags_finish */
  74  }
  75 };
  76
  77 /* Loop optimizer initialization.  */
  78
  79 static unsigned int
  80 tree_ssa_loop_init (void)
  81 {
  82   tree_loop_optimizer_init ();
  83   if (number_of_loops () <= 1)
  84     return 0;
  85
  86   scev_initialize ();
  87   return 0;
  88 }
  89
  90 struct gimple_opt_pass pass_tree_loop_init =
  91 {
  92  {
  93   GIMPLE_PASS,
  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  }
 107 };
 108
 109 /* Loop invariant motion pass.  */
 110
 111 static unsigned int
 112 tree_ssa_loop_im (void)
 113 {
 114   if (number_of_loops () <= 1)
 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 gimple_opt_pass pass_lim =
 128 {
 129  {
 130   GIMPLE_PASS,
 131   "lim",                                /* name */
 132   gate_tree_ssa_loop_im,                /* gate */
 133   tree_ssa_loop_im,                     /* execute */
 134   NULL,                                 /* sub */
 135   NULL,                                 /* next */
 136   0,                                    /* static_pass_number */
 137   TV_LIM,                               /* tv_id */
 138   PROP_cfg,                             /* properties_required */
 139   0,                                    /* properties_provided */
 140   0,                                    /* properties_destroyed */
 141   0,                                    /* todo_flags_start */
 142   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 143  }
 144 };
 145
 146 /* Loop unswitching pass.  */
 147
 148 static unsigned int
 149 tree_ssa_loop_unswitch (void)
 150 {
 151   if (number_of_loops () <= 1)
 152     return 0;
 153
 154   return tree_ssa_unswitch_loops ();
 155 }
 156
 157 static bool
 158 gate_tree_ssa_loop_unswitch (void)
 159 {
 160   return flag_unswitch_loops != 0;
 161 }
 162
 163 struct gimple_opt_pass pass_tree_unswitch =
 164 {
 165  {
 166   GIMPLE_PASS,
 167   "unswitch",                           /* name */
 168   gate_tree_ssa_loop_unswitch,          /* gate */
 169   tree_ssa_loop_unswitch,               /* execute */
 170   NULL,                                 /* sub */
 171   NULL,                                 /* next */
 172   0,                                    /* static_pass_number */
 173   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 174   PROP_cfg,                             /* properties_required */
 175   0,                                    /* properties_provided */
 176   0,                                    /* properties_destroyed */
 177   0,                                    /* todo_flags_start */
 178   TODO_ggc_collect | TODO_dump_func
 179     | TODO_verify_loops                 /* todo_flags_finish */
 180  }
 181 };
 182
 183 /* Predictive commoning.  */
 184
 185 static unsigned
 186 run_tree_predictive_commoning (void)
 187 {
 188   if (!current_loops)
 189     return 0;
 190
 191   tree_predictive_commoning ();
 192   return 0;
 193 }
 194
 195 static bool
 196 gate_tree_predictive_commoning (void)
 197 {
 198   return flag_predictive_commoning != 0;
 199 }
 200
 201 struct gimple_opt_pass pass_predcom =
 202 {
 203  {
 204   GIMPLE_PASS,
 205   "pcom",                               /* name */
 206   gate_tree_predictive_commoning,       /* gate */
 207   run_tree_predictive_commoning,        /* execute */
 208   NULL,                                 /* sub */
 209   NULL,                                 /* next */
 210   0,                                    /* static_pass_number */
 211   TV_PREDCOM,                           /* tv_id */
 212   PROP_cfg,                             /* properties_required */
 213   0,                                    /* properties_provided */
 214   0,                                    /* properties_destroyed */
 215   0,                                    /* todo_flags_start */
 216   TODO_dump_func | TODO_verify_loops
 217     | TODO_update_ssa_only_virtuals     /* todo_flags_finish */
 218  }
 219 };
 220
 221 /* Loop autovectorization.  */
 222
 223 static unsigned int
 224 tree_vectorize (void)
 225 {
 226   if (number_of_loops () <= 1)
 227     return 0;
 228
 229   return vectorize_loops ();
 230 }
 231
 232 static bool
 233 gate_tree_vectorize (void)
 234 {
 235   return flag_tree_vectorize;
 236 }
 237
 238 struct gimple_opt_pass pass_vectorize =
 239 {
 240  {
 241   GIMPLE_PASS,
 242   "vect",                               /* name */
 243   gate_tree_vectorize,                  /* gate */
 244   tree_vectorize,                       /* execute */
 245   NULL,                                 /* sub */
 246   NULL,                                 /* next */
 247   0,                                    /* static_pass_number */
 248   TV_TREE_VECTORIZATION,                /* tv_id */
 249   PROP_cfg | PROP_ssa,                  /* properties_required */
 250   0,                                    /* properties_provided */
 251   0,                                    /* properties_destroyed */
 252   TODO_verify_loops,                    /* todo_flags_start */
 253   TODO_dump_func | TODO_update_ssa
 254     | TODO_ggc_collect                  /* todo_flags_finish */
 255  }
 256 };
 257
 258 /* Loop nest optimizations.  */
 259
 260 static unsigned int
 261 tree_linear_transform (void)
 262 {
 263   if (number_of_loops () <= 1)
 264     return 0;
 265
 266   linear_transform_loops ();
 267   return 0;
 268 }
 269
 270 static bool
 271 gate_tree_linear_transform (void)
 272 {
 273   return flag_tree_loop_linear != 0;
 274 }
 275
 276 struct gimple_opt_pass pass_linear_transform =
 277 {
 278  {
 279   GIMPLE_PASS,
 280   "ltrans",                             /* name */
 281   gate_tree_linear_transform,           /* gate */
 282   tree_linear_transform,                /* execute */
 283   NULL,                                 /* sub */
 284   NULL,                                 /* next */
 285   0,                                    /* static_pass_number */
 286   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 287   PROP_cfg | PROP_ssa,                  /* properties_required */
 288   0,                                    /* properties_provided */
 289   0,                                    /* properties_destroyed */
 290   0,                                    /* todo_flags_start */
 291   TODO_dump_func | TODO_verify_loops
 292     | TODO_update_ssa_only_virtuals
 293     | TODO_ggc_collect                  /* todo_flags_finish */
 294  }
 295 };
 296
 297 /* Check the correctness of the data dependence analyzers.  */
 298
 299 static unsigned int
 300 check_data_deps (void)
 301 {
 302   if (number_of_loops () <= 1)
 303     return 0;
 304
 305   tree_check_data_deps ();
 306   return 0;
 307 }
 308
 309 static bool
 310 gate_check_data_deps (void)
 311 {
 312   return flag_check_data_deps != 0;
 313 }
 314
 315 struct gimple_opt_pass pass_check_data_deps =
 316 {
 317  {
 318   GIMPLE_PASS,
 319   "ckdd",                               /* name */
 320   gate_check_data_deps,                 /* gate */
 321   check_data_deps,                      /* execute */
 322   NULL,                                 /* sub */
 323   NULL,                                 /* next */
 324   0,                                    /* static_pass_number */
 325   TV_CHECK_DATA_DEPS,                   /* 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  }
 332 };
 333
 334 /* Canonical induction variable creation pass.  */
 335
 336 static unsigned int
 337 tree_ssa_loop_ivcanon (void)
 338 {
 339   if (number_of_loops () <= 1)
 340     return 0;
 341
 342   return canonicalize_induction_variables ();
 343 }
 344
 345 static bool
 346 gate_tree_ssa_loop_ivcanon (void)
 347 {
 348   return flag_tree_loop_ivcanon != 0;
 349 }
 350
 351 struct gimple_opt_pass pass_iv_canon =
 352 {
 353  {
 354   GIMPLE_PASS,
 355   "ivcanon",                            /* name */
 356   gate_tree_ssa_loop_ivcanon,           /* gate */
 357   tree_ssa_loop_ivcanon,                /* execute */
 358   NULL,                                 /* sub */
 359   NULL,                                 /* next */
 360   0,                                    /* static_pass_number */
 361   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 362   PROP_cfg | PROP_ssa,                  /* properties_required */
 363   0,                                    /* properties_provided */
 364   0,                                    /* properties_destroyed */
 365   0,                                    /* todo_flags_start */
 366   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 367  }
 368 };
 369
 370 /* Propagation of constants using scev.  */
 371
 372 static bool
 373 gate_scev_const_prop (void)
 374 {
 375   return flag_tree_scev_cprop;
 376 }
 377
 378 struct gimple_opt_pass pass_scev_cprop =
 379 {
 380  {
 381   GIMPLE_PASS,
 382   "sccp",                               /* name */
 383   gate_scev_const_prop,                 /* gate */
 384   scev_const_prop,                      /* execute */
 385   NULL,                                 /* sub */
 386   NULL,                                 /* next */
 387   0,                                    /* static_pass_number */
 388   TV_SCEV_CONST,                        /* 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_cleanup_cfg
 394     | TODO_update_ssa_only_virtuals
 395                                         /* todo_flags_finish */
 396  }
 397 };
 398
 399 /* Remove empty loops.  */
 400
 401 static unsigned int
 402 tree_ssa_empty_loop (void)
 403 {
 404   if (number_of_loops () <= 1)
 405     return 0;
 406
 407   return remove_empty_loops ();
 408 }
 409
 410 struct gimple_opt_pass pass_empty_loop =
 411 {
 412  {
 413   GIMPLE_PASS,
 414   "empty",                              /* name */
 415   NULL,                                 /* gate */
 416   tree_ssa_empty_loop,                  /* execute */
 417   NULL,                                 /* sub */
 418   NULL,                                 /* next */
 419   0,                                    /* static_pass_number */
 420   TV_COMPLETE_UNROLL,                   /* tv_id */
 421   PROP_cfg | PROP_ssa,                  /* properties_required */
 422   0,                                    /* properties_provided */
 423   0,                                    /* properties_destroyed */
 424   0,                                    /* todo_flags_start */
 425   TODO_dump_func | TODO_verify_loops
 426     | TODO_ggc_collect                  /* todo_flags_finish */
 427  }
 428 };
 429
 430 /* Record bounds on numbers of iterations of loops.  */
 431
 432 static unsigned int
 433 tree_ssa_loop_bounds (void)
 434 {
 435   if (number_of_loops () <= 1)
 436     return 0;
 437
 438   estimate_numbers_of_iterations ();
 439   scev_reset ();
 440   return 0;
 441 }
 442
 443 struct gimple_opt_pass pass_record_bounds =
 444 {
 445  {
 446   GIMPLE_PASS,
 447   NULL,                                 /* name */
 448   NULL,                                 /* gate */
 449   tree_ssa_loop_bounds,                 /* execute */
 450   NULL,                                 /* sub */
 451   NULL,                                 /* next */
 452   0,                                    /* static_pass_number */
 453   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 454   PROP_cfg | PROP_ssa,                  /* properties_required */
 455   0,                                    /* properties_provided */
 456   0,                                    /* properties_destroyed */
 457   0,                                    /* todo_flags_start */
 458   0                                     /* todo_flags_finish */
 459  }
 460 };
 461
 462 /* Complete unrolling of loops.  */
 463
 464 static unsigned int
 465 tree_complete_unroll (void)
 466 {
 467   if (number_of_loops () <= 1)
 468     return 0;
 469
 470   return tree_unroll_loops_completely (flag_unroll_loops
 471                                        || flag_peel_loops
 472                                        || optimize >= 3, true);
 473 }
 474
 475 static bool
 476 gate_tree_complete_unroll (void)
 477 {
 478   return true;
 479 }
 480
 481 struct gimple_opt_pass pass_complete_unroll =
 482 {
 483  {
 484   GIMPLE_PASS,
 485   "cunroll",                            /* name */
 486   gate_tree_complete_unroll,            /* gate */
 487   tree_complete_unroll,                 /* execute */
 488   NULL,                                 /* sub */
 489   NULL,                                 /* next */
 490   0,                                    /* static_pass_number */
 491   TV_COMPLETE_UNROLL,                   /* tv_id */
 492   PROP_cfg | PROP_ssa,                  /* properties_required */
 493   0,                                    /* properties_provided */
 494   0,                                    /* properties_destroyed */
 495   0,                                    /* todo_flags_start */
 496   TODO_dump_func | TODO_verify_loops
 497     | TODO_ggc_collect                  /* todo_flags_finish */
 498  }
 499 };
 500
 501 /* Complete unrolling of inner loops.  */
 502
 503 static unsigned int
 504 tree_complete_unroll_inner (void)
 505 {
 506   unsigned ret = 0;
 507
 508   loop_optimizer_init (LOOPS_NORMAL
 509                        | LOOPS_HAVE_RECORDED_EXITS);
 510   if (number_of_loops () > 1)
 511     {
 512       scev_initialize ();
 513       ret = tree_unroll_loops_completely (optimize >= 3, false);
 514       free_numbers_of_iterations_estimates ();
 515       scev_finalize ();
 516     }
 517   loop_optimizer_finalize ();
 518
 519   return ret;
 520 }
 521
 522 static bool
 523 gate_tree_complete_unroll_inner (void)
 524 {
 525   return optimize >= 2;
 526 }
 527
 528 struct gimple_opt_pass pass_complete_unrolli =
 529 {
 530  {
 531   GIMPLE_PASS,
 532   "cunrolli",                           /* name */
 533   gate_tree_complete_unroll_inner,      /* gate */
 534   tree_complete_unroll_inner,           /* execute */
 535   NULL,                                 /* sub */
 536   NULL,                                 /* next */
 537   0,                                    /* static_pass_number */
 538   TV_COMPLETE_UNROLL,                   /* tv_id */
 539   PROP_cfg | PROP_ssa,                  /* properties_required */
 540   0,                                    /* properties_provided */
 541   0,                                    /* properties_destroyed */
 542   0,                                    /* todo_flags_start */
 543   TODO_dump_func | TODO_verify_loops
 544     | TODO_ggc_collect                  /* todo_flags_finish */
 545  }
 546 };
 547
 548 /* Parallelization.  */
 549
 550 static bool
 551 gate_tree_parallelize_loops (void)
 552 {
 553   return flag_tree_parallelize_loops > 1;
 554 }
 555
 556 static unsigned
 557 tree_parallelize_loops (void)
 558 {
 559   if (number_of_loops () <= 1)
 560     return 0;
 561
 562   if (parallelize_loops ())
 563     return TODO_cleanup_cfg | TODO_rebuild_alias;
 564   return 0;
 565 }
 566
 567 struct gimple_opt_pass pass_parallelize_loops =
 568 {
 569  {
 570   GIMPLE_PASS,
 571   "parloops",                           /* name */
 572   gate_tree_parallelize_loops,          /* gate */
 573   tree_parallelize_loops,               /* execute */
 574   NULL,                                 /* sub */
 575   NULL,                                 /* next */
 576   0,                                    /* static_pass_number */
 577   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
 578   PROP_cfg | PROP_ssa,                  /* properties_required */
 579   0,                                    /* properties_provided */
 580   0,                                    /* properties_destroyed */
 581   0,                                    /* todo_flags_start */
 582   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 583  }
 584 };
 585
 586 /* Prefetching.  */
 587
 588 static unsigned int
 589 tree_ssa_loop_prefetch (void)
 590 {
 591   if (number_of_loops () <= 1)
 592     return 0;
 593
 594   return tree_ssa_prefetch_arrays ();
 595 }
 596
 597 static bool
 598 gate_tree_ssa_loop_prefetch (void)
 599 {
 600   return flag_prefetch_loop_arrays != 0;
 601 }
 602
 603 struct gimple_opt_pass pass_loop_prefetch =
 604 {
 605  {
 606   GIMPLE_PASS,
 607   "aprefetch",                          /* name */
 608   gate_tree_ssa_loop_prefetch,          /* gate */
 609   tree_ssa_loop_prefetch,               /* execute */
 610   NULL,                                 /* sub */
 611   NULL,                                 /* next */
 612   0,                                    /* static_pass_number */
 613   TV_TREE_PREFETCH,                     /* tv_id */
 614   PROP_cfg | PROP_ssa,                  /* properties_required */
 615   0,                                    /* properties_provided */
 616   0,                                    /* properties_destroyed */
 617   0,                                    /* todo_flags_start */
 618   TODO_dump_func | TODO_verify_loops    /* todo_flags_finish */
 619  }
 620 };
 621
 622 /* Induction variable optimizations.  */
 623
 624 static unsigned int
 625 tree_ssa_loop_ivopts (void)
 626 {
 627   if (number_of_loops () <= 1)
 628     return 0;
 629
 630   tree_ssa_iv_optimize ();
 631   return 0;
 632 }
 633
 634 static bool
 635 gate_tree_ssa_loop_ivopts (void)
 636 {
 637   return flag_ivopts != 0;
 638 }
 639
 640 struct gimple_opt_pass pass_iv_optimize =
 641 {
 642  {
 643   GIMPLE_PASS,
 644   "ivopts",                             /* name */
 645   gate_tree_ssa_loop_ivopts,            /* gate */
 646   tree_ssa_loop_ivopts,                 /* execute */
 647   NULL,                                 /* sub */
 648   NULL,                                 /* next */
 649   0,                                    /* static_pass_number */
 650   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 651   PROP_cfg | PROP_ssa,                  /* properties_required */
 652   0,                                    /* properties_provided */
 653   0,                                    /* properties_destroyed */
 654   0,                                    /* todo_flags_start */
 655   TODO_dump_func | TODO_verify_loops
 656   | TODO_update_ssa | TODO_ggc_collect  /* todo_flags_finish */
 657  }
 658 };
 659
 660 /* Loop optimizer finalization.  */
 661
 662 static unsigned int
 663 tree_ssa_loop_done (void)
 664 {
 665   free_numbers_of_iterations_estimates ();
 666   scev_finalize ();
 667   loop_optimizer_finalize ();
 668   return 0;
 669 }
 670
 671 struct gimple_opt_pass pass_tree_loop_done =
 672 {
 673  {
 674   GIMPLE_PASS,
 675   "loopdone",                           /* name */
 676   NULL,                                 /* gate */
 677   tree_ssa_loop_done,                   /* execute */
 678   NULL,                                 /* sub */
 679   NULL,                                 /* next */
 680   0,                                    /* static_pass_number */
 681   TV_TREE_LOOP_FINI,                    /* tv_id */
 682   PROP_cfg,                             /* properties_required */
 683   0,                                    /* properties_provided */
 684   0,                                    /* properties_destroyed */
 685   0,                                    /* todo_flags_start */
 686   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
 687  }
 688 };