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