gcc/tree-ssa-loop.c

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