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