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