gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it
   8 under the terms of the GNU General Public License as published by the
   9 Free Software Foundation; either version 3, or (at your option) any
  10 later version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT
  13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "tm_p.h"
  27 #include "basic-block.h"
  28 #include "output.h"
  29 #include "tree-flow.h"
  30 #include "tree-dump.h"
  31 #include "tree-pass.h"
  32 #include "timevar.h"
  33 #include "cfgloop.h"
  34 #include "flags.h"
  35 #include "tree-inline.h"
  36 #include "tree-scalar-evolution.h"
  37 #include "diagnostic-core.h"
  38 #include "tree-vectorizer.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_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   return tree_ssa_lim ();
 111 }
 112
 113 static bool
 114 gate_tree_ssa_loop_im (void)
 115 {
 116   return flag_tree_loop_im != 0;
 117 }
 118
 119 struct gimple_opt_pass pass_lim =
 120 {
 121  {
 122   GIMPLE_PASS,
 123   "lim",                                /* name */
 124   gate_tree_ssa_loop_im,                /* gate */
 125   tree_ssa_loop_im,                     /* execute */
 126   NULL,                                 /* sub */
 127   NULL,                                 /* next */
 128   0,                                    /* static_pass_number */
 129   TV_LIM,                               /* tv_id */
 130   PROP_cfg,                             /* properties_required */
 131   0,                                    /* properties_provided */
 132   0,                                    /* properties_destroyed */
 133   0,                                    /* todo_flags_start */
 134   TODO_dump_func                        /* todo_flags_finish */
 135  }
 136 };
 137
 138 /* Loop unswitching pass.  */
 139
 140 static unsigned int
 141 tree_ssa_loop_unswitch (void)
 142 {
 143   if (number_of_loops () <= 1)
 144     return 0;
 145
 146   return tree_ssa_unswitch_loops ();
 147 }
 148
 149 static bool
 150 gate_tree_ssa_loop_unswitch (void)
 151 {
 152   return flag_unswitch_loops != 0;
 153 }
 154
 155 struct gimple_opt_pass pass_tree_unswitch =
 156 {
 157  {
 158   GIMPLE_PASS,
 159   "unswitch",                           /* name */
 160   gate_tree_ssa_loop_unswitch,          /* gate */
 161   tree_ssa_loop_unswitch,               /* execute */
 162   NULL,                                 /* sub */
 163   NULL,                                 /* next */
 164   0,                                    /* static_pass_number */
 165   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 166   PROP_cfg,                             /* properties_required */
 167   0,                                    /* properties_provided */
 168   0,                                    /* properties_destroyed */
 169   0,                                    /* todo_flags_start */
 170   TODO_ggc_collect | TODO_dump_func     /* todo_flags_finish */
 171  }
 172 };
 173
 174 /* Predictive commoning.  */
 175
 176 static unsigned
 177 run_tree_predictive_commoning (void)
 178 {
 179   if (!current_loops)
 180     return 0;
 181
 182   return tree_predictive_commoning ();
 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 /* GRAPHITE optimizations.  */
 249
 250 static unsigned int
 251 graphite_transforms (void)
 252 {
 253   if (!current_loops)
 254     return 0;
 255
 256   graphite_transform_loops ();
 257
 258   return 0;
 259 }
 260
 261 static bool
 262 gate_graphite_transforms (void)
 263 {
 264   /* Enable -fgraphite pass if any one of the graphite optimization flags
 265      is turned on.  */
 266   if (flag_loop_block
 267       || flag_loop_interchange
 268       || flag_loop_strip_mine
 269       || flag_graphite_identity
 270       || flag_loop_parallelize_all
 271       || flag_loop_flatten)
 272     flag_graphite = 1;
 273
 274   return flag_graphite != 0;
 275 }
 276
 277 struct gimple_opt_pass pass_graphite =
 278 {
 279  {
 280   GIMPLE_PASS,
 281   "graphite0",                          /* name */
 282   gate_graphite_transforms,             /* gate */
 283   NULL,                                 /* execute */
 284   NULL,                                 /* sub */
 285   NULL,                                 /* next */
 286   0,                                    /* static_pass_number */
 287   TV_GRAPHITE,                          /* tv_id */
 288   PROP_cfg | PROP_ssa,                  /* properties_required */
 289   0,                                    /* properties_provided */
 290   0,                                    /* properties_destroyed */
 291   0,                                    /* todo_flags_start */
 292   0                                     /* todo_flags_finish */
 293  }
 294 };
 295
 296 struct gimple_opt_pass pass_graphite_transforms =
 297 {
 298  {
 299   GIMPLE_PASS,
 300   "graphite",                           /* name */
 301   gate_graphite_transforms,             /* gate */
 302   graphite_transforms,                  /* execute */
 303   NULL,                                 /* sub */
 304   NULL,                                 /* next */
 305   0,                                    /* static_pass_number */
 306   TV_GRAPHITE_TRANSFORMS,               /* tv_id */
 307   PROP_cfg | PROP_ssa,                  /* properties_required */
 308   0,                                    /* properties_provided */
 309   0,                                    /* properties_destroyed */
 310   0,                                    /* todo_flags_start */
 311   TODO_dump_func                        /* todo_flags_finish */
 312  }
 313 };
 314
 315 /* Check the correctness of the data dependence analyzers.  */
 316
 317 static unsigned int
 318 check_data_deps (void)
 319 {
 320   if (number_of_loops () <= 1)
 321     return 0;
 322
 323   tree_check_data_deps ();
 324   return 0;
 325 }
 326
 327 static bool
 328 gate_check_data_deps (void)
 329 {
 330   return flag_check_data_deps != 0;
 331 }
 332
 333 struct gimple_opt_pass pass_check_data_deps =
 334 {
 335  {
 336   GIMPLE_PASS,
 337   "ckdd",                               /* name */
 338   gate_check_data_deps,                 /* gate */
 339   check_data_deps,                      /* execute */
 340   NULL,                                 /* sub */
 341   NULL,                                 /* next */
 342   0,                                    /* static_pass_number */
 343   TV_CHECK_DATA_DEPS,                   /* tv_id */
 344   PROP_cfg | PROP_ssa,                  /* properties_required */
 345   0,                                    /* properties_provided */
 346   0,                                    /* properties_destroyed */
 347   0,                                    /* todo_flags_start */
 348   TODO_dump_func                        /* todo_flags_finish */
 349  }
 350 };
 351
 352 /* Canonical induction variable creation pass.  */
 353
 354 static unsigned int
 355 tree_ssa_loop_ivcanon (void)
 356 {
 357   if (number_of_loops () <= 1)
 358     return 0;
 359
 360   return canonicalize_induction_variables ();
 361 }
 362
 363 static bool
 364 gate_tree_ssa_loop_ivcanon (void)
 365 {
 366   return flag_tree_loop_ivcanon != 0;
 367 }
 368
 369 struct gimple_opt_pass pass_iv_canon =
 370 {
 371  {
 372   GIMPLE_PASS,
 373   "ivcanon",                            /* name */
 374   gate_tree_ssa_loop_ivcanon,           /* gate */
 375   tree_ssa_loop_ivcanon,                /* execute */
 376   NULL,                                 /* sub */
 377   NULL,                                 /* next */
 378   0,                                    /* static_pass_number */
 379   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 380   PROP_cfg | PROP_ssa,                  /* properties_required */
 381   0,                                    /* properties_provided */
 382   0,                                    /* properties_destroyed */
 383   0,                                    /* todo_flags_start */
 384   TODO_dump_func                        /* todo_flags_finish */
 385  }
 386 };
 387
 388 /* Propagation of constants using scev.  */
 389
 390 static bool
 391 gate_scev_const_prop (void)
 392 {
 393   return flag_tree_scev_cprop;
 394 }
 395
 396 struct gimple_opt_pass pass_scev_cprop =
 397 {
 398  {
 399   GIMPLE_PASS,
 400   "sccp",                               /* name */
 401   gate_scev_const_prop,                 /* gate */
 402   scev_const_prop,                      /* execute */
 403   NULL,                                 /* sub */
 404   NULL,                                 /* next */
 405   0,                                    /* static_pass_number */
 406   TV_SCEV_CONST,                        /* tv_id */
 407   PROP_cfg | PROP_ssa,                  /* properties_required */
 408   0,                                    /* properties_provided */
 409   0,                                    /* properties_destroyed */
 410   0,                                    /* todo_flags_start */
 411   TODO_dump_func | TODO_cleanup_cfg
 412     | TODO_update_ssa_only_virtuals
 413                                         /* todo_flags_finish */
 414  }
 415 };
 416
 417 /* Record bounds on numbers of iterations of loops.  */
 418
 419 static unsigned int
 420 tree_ssa_loop_bounds (void)
 421 {
 422   if (number_of_loops () <= 1)
 423     return 0;
 424
 425   estimate_numbers_of_iterations (true);
 426   scev_reset ();
 427   return 0;
 428 }
 429
 430 struct gimple_opt_pass pass_record_bounds =
 431 {
 432  {
 433   GIMPLE_PASS,
 434   "*record_bounds",                     /* name */
 435   NULL,                                 /* gate */
 436   tree_ssa_loop_bounds,                 /* execute */
 437   NULL,                                 /* sub */
 438   NULL,                                 /* next */
 439   0,                                    /* static_pass_number */
 440   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 441   PROP_cfg | PROP_ssa,                  /* properties_required */
 442   0,                                    /* properties_provided */
 443   0,                                    /* properties_destroyed */
 444   0,                                    /* todo_flags_start */
 445   0                                     /* todo_flags_finish */
 446  }
 447 };
 448
 449 /* Complete unrolling of loops.  */
 450
 451 static unsigned int
 452 tree_complete_unroll (void)
 453 {
 454   if (number_of_loops () <= 1)
 455     return 0;
 456
 457   return tree_unroll_loops_completely (flag_unroll_loops
 458                                        || flag_peel_loops
 459                                        || optimize >= 3, true);
 460 }
 461
 462 static bool
 463 gate_tree_complete_unroll (void)
 464 {
 465   return true;
 466 }
 467
 468 struct gimple_opt_pass pass_complete_unroll =
 469 {
 470  {
 471   GIMPLE_PASS,
 472   "cunroll",                            /* name */
 473   gate_tree_complete_unroll,            /* gate */
 474   tree_complete_unroll,                 /* execute */
 475   NULL,                                 /* sub */
 476   NULL,                                 /* next */
 477   0,                                    /* static_pass_number */
 478   TV_COMPLETE_UNROLL,                   /* tv_id */
 479   PROP_cfg | PROP_ssa,                  /* properties_required */
 480   0,                                    /* properties_provided */
 481   0,                                    /* properties_destroyed */
 482   0,                                    /* todo_flags_start */
 483   TODO_dump_func
 484     | TODO_ggc_collect                  /* todo_flags_finish */
 485  }
 486 };
 487
 488 /* Complete unrolling of inner loops.  */
 489
 490 static unsigned int
 491 tree_complete_unroll_inner (void)
 492 {
 493   unsigned ret = 0;
 494
 495   loop_optimizer_init (LOOPS_NORMAL
 496                        | LOOPS_HAVE_RECORDED_EXITS);
 497   if (number_of_loops () > 1)
 498     {
 499       scev_initialize ();
 500       ret = tree_unroll_loops_completely (optimize >= 3, false);
 501       free_numbers_of_iterations_estimates ();
 502       scev_finalize ();
 503     }
 504   loop_optimizer_finalize ();
 505
 506   return ret;
 507 }
 508
 509 static bool
 510 gate_tree_complete_unroll_inner (void)
 511 {
 512   return optimize >= 2;
 513 }
 514
 515 struct gimple_opt_pass pass_complete_unrolli =
 516 {
 517  {
 518   GIMPLE_PASS,
 519   "cunrolli",                           /* name */
 520   gate_tree_complete_unroll_inner,      /* gate */
 521   tree_complete_unroll_inner,           /* execute */
 522   NULL,                                 /* sub */
 523   NULL,                                 /* next */
 524   0,                                    /* static_pass_number */
 525   TV_COMPLETE_UNROLL,                   /* tv_id */
 526   PROP_cfg | PROP_ssa,                  /* properties_required */
 527   0,                                    /* properties_provided */
 528   0,                                    /* properties_destroyed */
 529   0,                                    /* todo_flags_start */
 530   TODO_verify_flow
 531     | TODO_dump_func
 532     | TODO_ggc_collect                  /* todo_flags_finish */
 533  }
 534 };
 535
 536 /* Parallelization.  */
 537
 538 static bool
 539 gate_tree_parallelize_loops (void)
 540 {
 541   return flag_tree_parallelize_loops > 1;
 542 }
 543
 544 static unsigned
 545 tree_parallelize_loops (void)
 546 {
 547   if (number_of_loops () <= 1)
 548     return 0;
 549
 550   if (parallelize_loops ())
 551     return TODO_cleanup_cfg | TODO_rebuild_alias;
 552   return 0;
 553 }
 554
 555 struct gimple_opt_pass pass_parallelize_loops =
 556 {
 557  {
 558   GIMPLE_PASS,
 559   "parloops",                           /* name */
 560   gate_tree_parallelize_loops,          /* gate */
 561   tree_parallelize_loops,               /* execute */
 562   NULL,                                 /* sub */
 563   NULL,                                 /* next */
 564   0,                                    /* static_pass_number */
 565   TV_TREE_PARALLELIZE_LOOPS,            /* tv_id */
 566   PROP_cfg | PROP_ssa,                  /* properties_required */
 567   0,                                    /* properties_provided */
 568   0,                                    /* properties_destroyed */
 569   0,                                    /* todo_flags_start */
 570   TODO_dump_func                        /* todo_flags_finish */
 571  }
 572 };
 573
 574 /* Prefetching.  */
 575
 576 static unsigned int
 577 tree_ssa_loop_prefetch (void)
 578 {
 579   if (number_of_loops () <= 1)
 580     return 0;
 581
 582   return tree_ssa_prefetch_arrays ();
 583 }
 584
 585 static bool
 586 gate_tree_ssa_loop_prefetch (void)
 587 {
 588   return flag_prefetch_loop_arrays > 0;
 589 }
 590
 591 struct gimple_opt_pass pass_loop_prefetch =
 592 {
 593  {
 594   GIMPLE_PASS,
 595   "aprefetch",                          /* name */
 596   gate_tree_ssa_loop_prefetch,          /* gate */
 597   tree_ssa_loop_prefetch,               /* execute */
 598   NULL,                                 /* sub */
 599   NULL,                                 /* next */
 600   0,                                    /* static_pass_number */
 601   TV_TREE_PREFETCH,                     /* tv_id */
 602   PROP_cfg | PROP_ssa,                  /* properties_required */
 603   0,                                    /* properties_provided */
 604   0,                                    /* properties_destroyed */
 605   0,                                    /* todo_flags_start */
 606   TODO_dump_func                        /* todo_flags_finish */
 607  }
 608 };
 609
 610 /* Induction variable optimizations.  */
 611
 612 static unsigned int
 613 tree_ssa_loop_ivopts (void)
 614 {
 615   if (number_of_loops () <= 1)
 616     return 0;
 617
 618   tree_ssa_iv_optimize ();
 619   return 0;
 620 }
 621
 622 static bool
 623 gate_tree_ssa_loop_ivopts (void)
 624 {
 625   return flag_ivopts != 0;
 626 }
 627
 628 struct gimple_opt_pass pass_iv_optimize =
 629 {
 630  {
 631   GIMPLE_PASS,
 632   "ivopts",                             /* name */
 633   gate_tree_ssa_loop_ivopts,            /* gate */
 634   tree_ssa_loop_ivopts,                 /* execute */
 635   NULL,                                 /* sub */
 636   NULL,                                 /* next */
 637   0,                                    /* static_pass_number */
 638   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 639   PROP_cfg | PROP_ssa,                  /* properties_required */
 640   0,                                    /* properties_provided */
 641   0,                                    /* properties_destroyed */
 642   0,                                    /* todo_flags_start */
 643   TODO_dump_func | TODO_update_ssa | TODO_ggc_collect   /* todo_flags_finish */
 644  }
 645 };
 646
 647 /* Loop optimizer finalization.  */
 648
 649 static unsigned int
 650 tree_ssa_loop_done (void)
 651 {
 652   free_numbers_of_iterations_estimates ();
 653   scev_finalize ();
 654   loop_optimizer_finalize ();
 655   return 0;
 656 }
 657
 658 struct gimple_opt_pass pass_tree_loop_done =
 659 {
 660  {
 661   GIMPLE_PASS,
 662   "loopdone",                           /* name */
 663   NULL,                                 /* gate */
 664   tree_ssa_loop_done,                   /* execute */
 665   NULL,                                 /* sub */
 666   NULL,                                 /* next */
 667   0,                                    /* static_pass_number */
 668   TV_TREE_LOOP_FINI,                    /* tv_id */
 669   PROP_cfg,                             /* properties_required */
 670   0,                                    /* properties_provided */
 671   0,                                    /* properties_destroyed */
 672   0,                                    /* todo_flags_start */
 673   TODO_cleanup_cfg
 674     | TODO_verify_flow
 675     | TODO_dump_func                    /* todo_flags_finish */
 676  }
 677 };