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