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   return tree_ssa_lim ();
 113 }
 114
 115 static bool
 116 gate_tree_ssa_loop_im (void)
 117 {
 118   return flag_tree_loop_im != 0;
 119 }
 120
 121 struct gimple_opt_pass pass_lim =
 122 {
 123  {
 124   GIMPLE_PASS,
 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_flags_finish */
 137  }
 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 gimple_opt_pass pass_tree_unswitch =
 158 {
 159  {
 160   GIMPLE_PASS,
 161   "unswitch",                           /* name */
 162   gate_tree_ssa_loop_unswitch,          /* gate */
 163   tree_ssa_loop_unswitch,               /* execute */
 164   NULL,                                 /* sub */
 165   NULL,                                 /* next */
 166   0,                                    /* static_pass_number */
 167   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 168   PROP_cfg,                             /* properties_required */
 169   0,                                    /* properties_provided */
 170   0,                                    /* properties_destroyed */
 171   0,                                    /* todo_flags_start */
 172   TODO_ggc_collect | TODO_dump_func     /* 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
 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   0,                                    /* 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
 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_identity || flag_loop_parallelize_all)
 310     flag_graphite = 1;
 311
 312   return flag_graphite != 0;
 313 }
 314
 315 struct gimple_opt_pass pass_graphite_transforms =
 316 {
 317  {
 318   GIMPLE_PASS,
 319   "graphite",                           /* name */
 320   gate_graphite_transforms,             /* gate */
 321   graphite_transforms,                  /* execute */
 322   NULL,                                 /* sub */
 323   NULL,                                 /* next */
 324   0,                                    /* static_pass_number */
 325   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
 326   PROP_cfg | PROP_ssa,                  /* properties_required */
 327   0,                                    /* properties_provided */
 328   0,                                    /* properties_destroyed */
 329   0,                                    /* todo_flags_start */
 330   0                                     /* todo_flags_finish */
 331  }
 332 };
 333
 334 /* Check the correctness of the data dependence analyzers.  */
 335
 336 static unsigned int
 337 check_data_deps (void)
 338 {
 339   if (number_of_loops () <= 1)
 340     return 0;
 341
 342   tree_check_data_deps ();
 343   return 0;
 344 }
 345
 346 static bool
 347 gate_check_data_deps (void)
 348 {
 349   return flag_check_data_deps != 0;
 350 }
 351
 352 struct gimple_opt_pass pass_check_data_deps =
 353 {
 354  {
 355   GIMPLE_PASS,
 356   "ckdd",                               /* name */
 357   gate_check_data_deps,                 /* gate */
 358   check_data_deps,                      /* execute */
 359   NULL,                                 /* sub */
 360   NULL,                                 /* next */
 361   0,                                    /* static_pass_number */
 362   TV_CHECK_DATA_DEPS,                   /* tv_id */
 363   PROP_cfg | PROP_ssa,                  /* properties_required */
 364   0,                                    /* properties_provided */
 365   0,                                    /* properties_destroyed */
 366   0,                                    /* todo_flags_start */
 367   TODO_dump_func                        /* todo_flags_finish */
 368  }
 369 };
 370
 371 /* Canonical induction variable creation pass.  */
 372
 373 static unsigned int
 374 tree_ssa_loop_ivcanon (void)
 375 {
 376   if (number_of_loops () <= 1)
 377     return 0;
 378
 379   return canonicalize_induction_variables ();
 380 }
 381
 382 static bool
 383 gate_tree_ssa_loop_ivcanon (void)
 384 {
 385   return flag_tree_loop_ivcanon != 0;
 386 }
 387
 388 struct gimple_opt_pass pass_iv_canon =
 389 {
 390  {
 391   GIMPLE_PASS,
 392   "ivcanon",                            /* name */
 393   gate_tree_ssa_loop_ivcanon,           /* gate */
 394   tree_ssa_loop_ivcanon,                /* execute */
 395   NULL,                                 /* sub */
 396   NULL,                                 /* next */
 397   0,                                    /* static_pass_number */
 398   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 399   PROP_cfg | PROP_ssa,                  /* properties_required */
 400   0,                                    /* properties_provided */
 401   0,                                    /* properties_destroyed */
 402   0,                                    /* todo_flags_start */
 403   TODO_dump_func                        /* todo_flags_finish */
 404  }
 405 };
 406
 407 /* Propagation of constants using scev.  */
 408
 409 static bool
 410 gate_scev_const_prop (void)
 411 {
 412   return flag_tree_scev_cprop;
 413 }
 414
 415 struct gimple_opt_pass pass_scev_cprop =
 416 {
 417  {
 418   GIMPLE_PASS,
 419   "sccp",                               /* name */
 420   gate_scev_const_prop,                 /* gate */
 421   scev_const_prop,                      /* execute */
 422   NULL,                                 /* sub */
 423   NULL,                                 /* next */
 424   0,                                    /* static_pass_number */
 425   TV_SCEV_CONST,                        /* tv_id */
 426   PROP_cfg | PROP_ssa,                  /* properties_required */
 427   0,                                    /* properties_provided */
 428   0,                                    /* properties_destroyed */
 429   0,                                    /* todo_flags_start */
 430   TODO_dump_func | TODO_cleanup_cfg
 431     | TODO_update_ssa_only_virtuals
 432                                         /* todo_flags_finish */
 433  }
 434 };
 435
 436 /* Record bounds on numbers of iterations of loops.  */
 437
 438 static unsigned int
 439 tree_ssa_loop_bounds (void)
 440 {
 441   if (number_of_loops () <= 1)
 442     return 0;
 443
 444   estimate_numbers_of_iterations ();
 445   scev_reset ();
 446   return 0;
 447 }
 448
 449 struct gimple_opt_pass pass_record_bounds =
 450 {
 451  {
 452   GIMPLE_PASS,
 453   "*record_bounds",                     /* name */
 454   NULL,                                 /* gate */
 455   tree_ssa_loop_bounds,                 /* execute */
 456   NULL,                                 /* sub */
 457   NULL,                                 /* next */
 458   0,                                    /* static_pass_number */
 459   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 460   PROP_cfg | PROP_ssa,                  /* properties_required */
 461   0,                                    /* properties_provided */
 462   0,                                    /* properties_destroyed */
 463   0,                                    /* todo_flags_start */
 464   0                                     /* todo_flags_finish */
 465  }
 466 };
 467
 468 /* Complete unrolling of loops.  */
 469
 470 static unsigned int
 471 tree_complete_unroll (void)
 472 {
 473   if (number_of_loops () <= 1)
 474     return 0;
 475
 476   return tree_unroll_loops_completely (flag_unroll_loops
 477                                        || flag_peel_loops
 478                                        || optimize >= 3, true);
 479 }
 480
 481 static bool
 482 gate_tree_complete_unroll (void)
 483 {
 484   return true;
 485 }
 486
 487 struct gimple_opt_pass pass_complete_unroll =
 488 {
 489  {
 490   GIMPLE_PASS,
 491   "cunroll",                            /* name */
 492   gate_tree_complete_unroll,            /* gate */
 493   tree_complete_unroll,                 /* execute */
 494   NULL,                                 /* sub */
 495   NULL,                                 /* next */
 496   0,                                    /* static_pass_number */
 497   TV_COMPLETE_UNROLL,                   /* tv_id */
 498   PROP_cfg | PROP_ssa,                  /* properties_required */
 499   0,                                    /* properties_provided */
 500   0,                                    /* properties_destroyed */
 501   0,                                    /* todo_flags_start */
 502   TODO_dump_func
 503     | TODO_ggc_collect                  /* todo_flags_finish */
 504  }
 505 };
 506
 507 /* Complete unrolling of inner loops.  */
 508
 509 static unsigned int
 510 tree_complete_unroll_inner (void)
 511 {
 512   unsigned ret = 0;
 513
 514   loop_optimizer_init (LOOPS_NORMAL
 515                        | LOOPS_HAVE_RECORDED_EXITS);
 516   if (number_of_loops () > 1)
 517     {
 518       scev_initialize ();
 519       ret = tree_unroll_loops_completely (optimize >= 3, false);
 520       free_numbers_of_iterations_estimates ();
 521       scev_finalize ();
 522     }
 523   loop_optimizer_finalize ();
 524
 525   return ret;
 526 }
 527
 528 static bool
 529 gate_tree_complete_unroll_inner (void)
 530 {
 531   return optimize >= 2;
 532 }
 533
 534 struct gimple_opt_pass pass_complete_unrolli =
 535 {
 536  {
 537   GIMPLE_PASS,
 538   "cunrolli",                           /* name */
 539   gate_tree_complete_unroll_inner,      /* gate */
 540   tree_complete_unroll_inner,           /* execute */
 541   NULL,                                 /* sub */
 542   NULL,                                 /* next */
 543   0,                                    /* static_pass_number */
 544   TV_COMPLETE_UNROLL,                   /* tv_id */
 545   PROP_cfg | PROP_ssa,                  /* properties_required */
 546   0,                                    /* properties_provided */
 547   0,                                    /* properties_destroyed */
 548   0,                                    /* todo_flags_start */
 549   TODO_dump_func
 550     | TODO_ggc_collect                  /* todo_flags_finish */
 551  }
 552 };
 553
 554 /* Parallelization.  */
 555
 556 static bool
 557 gate_tree_parallelize_loops (void)
 558 {
 559   return flag_tree_parallelize_loops > 1;
 560 }
 561
 562 static unsigned
 563 tree_parallelize_loops (void)
 564 {
 565   if (number_of_loops () <= 1)
 566     return 0;
 567
 568   if (parallelize_loops ())
 569     return TODO_cleanup_cfg | TODO_rebuild_alias;
 570   return 0;
 571 }
 572
 573 struct gimple_opt_pass pass_parallelize_loops =
 574 {
 575  {
 576   GIMPLE_PASS,
 577   "parloops",                           /* name */
 578   gate_tree_parallelize_loops,          /* gate */
 579   tree_parallelize_loops,               /* execute */
 580   NULL,                                 /* sub */
 581   NULL,                                 /* next */
 582   0,                                    /* static_pass_number */
 583   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
 584   PROP_cfg | PROP_ssa,                  /* properties_required */
 585   0,                                    /* properties_provided */
 586   0,                                    /* properties_destroyed */
 587   0,                                    /* todo_flags_start */
 588   TODO_dump_func                        /* todo_flags_finish */
 589  }
 590 };
 591
 592 /* Prefetching.  */
 593
 594 static unsigned int
 595 tree_ssa_loop_prefetch (void)
 596 {
 597   if (number_of_loops () <= 1)
 598     return 0;
 599
 600   return tree_ssa_prefetch_arrays ();
 601 }
 602
 603 static bool
 604 gate_tree_ssa_loop_prefetch (void)
 605 {
 606   return flag_prefetch_loop_arrays != 0;
 607 }
 608
 609 struct gimple_opt_pass pass_loop_prefetch =
 610 {
 611  {
 612   GIMPLE_PASS,
 613   "aprefetch",                          /* name */
 614   gate_tree_ssa_loop_prefetch,          /* gate */
 615   tree_ssa_loop_prefetch,               /* execute */
 616   NULL,                                 /* sub */
 617   NULL,                                 /* next */
 618   0,                                    /* static_pass_number */
 619   TV_TREE_PREFETCH,                     /* tv_id */
 620   PROP_cfg | PROP_ssa,                  /* properties_required */
 621   0,                                    /* properties_provided */
 622   0,                                    /* properties_destroyed */
 623   0,                                    /* todo_flags_start */
 624   TODO_dump_func                        /* todo_flags_finish */
 625  }
 626 };
 627
 628 /* Induction variable optimizations.  */
 629
 630 static unsigned int
 631 tree_ssa_loop_ivopts (void)
 632 {
 633   if (number_of_loops () <= 1)
 634     return 0;
 635
 636   tree_ssa_iv_optimize ();
 637   return 0;
 638 }
 639
 640 static bool
 641 gate_tree_ssa_loop_ivopts (void)
 642 {
 643   return flag_ivopts != 0;
 644 }
 645
 646 struct gimple_opt_pass pass_iv_optimize =
 647 {
 648  {
 649   GIMPLE_PASS,
 650   "ivopts",                             /* name */
 651   gate_tree_ssa_loop_ivopts,            /* gate */
 652   tree_ssa_loop_ivopts,                 /* execute */
 653   NULL,                                 /* sub */
 654   NULL,                                 /* next */
 655   0,                                    /* static_pass_number */
 656   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 657   PROP_cfg | PROP_ssa,                  /* properties_required */
 658   0,                                    /* properties_provided */
 659   0,                                    /* properties_destroyed */
 660   0,                                    /* todo_flags_start */
 661   TODO_dump_func | TODO_update_ssa | TODO_ggc_collect   /* todo_flags_finish */
 662  }
 663 };
 664
 665 /* Loop optimizer finalization.  */
 666
 667 static unsigned int
 668 tree_ssa_loop_done (void)
 669 {
 670   free_numbers_of_iterations_estimates ();
 671   scev_finalize ();
 672   loop_optimizer_finalize ();
 673   return 0;
 674 }
 675
 676 struct gimple_opt_pass pass_tree_loop_done =
 677 {
 678  {
 679   GIMPLE_PASS,
 680   "loopdone",                           /* name */
 681   NULL,                                 /* gate */
 682   tree_ssa_loop_done,                   /* execute */
 683   NULL,                                 /* sub */
 684   NULL,                                 /* next */
 685   0,                                    /* static_pass_number */
 686   TV_TREE_LOOP_FINI,                    /* tv_id */
 687   PROP_cfg,                             /* properties_required */
 688   0,                                    /* properties_provided */
 689   0,                                    /* properties_destroyed */
 690   0,                                    /* todo_flags_start */
 691   TODO_cleanup_cfg | TODO_dump_func     /* todo_flags_finish */
 692  }
 693 };