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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "rtl.h"
  27 #include "tm_p.h"
  28 #include "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "output.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "tree-pass.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "flags.h"
  38 #include "tree-inline.h"
  39 #include "tree-scalar-evolution.h"
  40
  41 /* Initializes the loop structures.  */
  42
  43 static void
  44 tree_loop_optimizer_init (void)
  45 {
  46   loop_optimizer_init (LOOPS_NORMAL
  47                        | LOOPS_HAVE_RECORDED_EXITS);
  48   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
  49 }
  50
  51 /* The loop superpass.  */
  52
  53 static bool
  54 gate_tree_loop (void)
  55 {
  56   return flag_tree_loop_optimize != 0;
  57 }
  58
  59 struct tree_opt_pass pass_tree_loop =
  60 {
  61   "loop",                               /* name */
  62   gate_tree_loop,                       /* gate */
  63   NULL,                                 /* execute */
  64   NULL,                                 /* sub */
  65   NULL,                                 /* next */
  66   0,                                    /* static_pass_number */
  67   TV_TREE_LOOP,                         /* tv_id */
  68   PROP_cfg,                             /* properties_required */
  69   0,                                    /* properties_provided */
  70   0,                                    /* properties_destroyed */
  71   TODO_ggc_collect,                     /* todo_flags_start */
  72   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
  73   0                                     /* letter */
  74 };
  75
  76 /* Loop optimizer initialization.  */
  77
  78 static unsigned int
  79 tree_ssa_loop_init (void)
  80 {
  81   tree_loop_optimizer_init ();
  82   if (number_of_loops () <= 1)
  83     return 0;
  84
  85   scev_initialize ();
  86   return 0;
  87 }
  88
  89 struct tree_opt_pass pass_tree_loop_init =
  90 {
  91   "loopinit",                           /* name */
  92   NULL,                                 /* gate */
  93   tree_ssa_loop_init,                   /* execute */
  94   NULL,                                 /* sub */
  95   NULL,                                 /* next */
  96   0,                                    /* static_pass_number */
  97   TV_TREE_LOOP_INIT,                    /* tv_id */
  98   PROP_cfg,                             /* properties_required */
  99   0,                                    /* properties_provided */
 100   0,                                    /* properties_destroyed */
 101   0,                                    /* todo_flags_start */
 102   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 103   0                                     /* letter */
 104 };
 105
 106 /* Loop invariant motion pass.  */
 107
 108 static unsigned int
 109 tree_ssa_loop_im (void)
 110 {
 111   if (number_of_loops () <= 1)
 112     return 0;
 113
 114   tree_ssa_lim ();
 115   return 0;
 116 }
 117
 118 static bool
 119 gate_tree_ssa_loop_im (void)
 120 {
 121   return flag_tree_loop_im != 0;
 122 }
 123
 124 struct tree_opt_pass pass_lim =
 125 {
 126   "lim",                                /* name */
 127   gate_tree_ssa_loop_im,                /* gate */
 128   tree_ssa_loop_im,                     /* execute */
 129   NULL,                                 /* sub */
 130   NULL,                                 /* next */
 131   0,                                    /* static_pass_number */
 132   TV_LIM,                               /* tv_id */
 133   PROP_cfg,                             /* properties_required */
 134   0,                                    /* properties_provided */
 135   0,                                    /* properties_destroyed */
 136   0,                                    /* todo_flags_start */
 137   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 138   0                                     /* letter */
 139 };
 140
 141 /* Loop unswitching pass.  */
 142
 143 static unsigned int
 144 tree_ssa_loop_unswitch (void)
 145 {
 146   if (number_of_loops () <= 1)
 147     return 0;
 148
 149   return tree_ssa_unswitch_loops ();
 150 }
 151
 152 static bool
 153 gate_tree_ssa_loop_unswitch (void)
 154 {
 155   return flag_unswitch_loops != 0;
 156 }
 157
 158 struct tree_opt_pass pass_tree_unswitch =
 159 {
 160   "unswitch",                           /* name */
 161   gate_tree_ssa_loop_unswitch,          /* gate */
 162   tree_ssa_loop_unswitch,               /* execute */
 163   NULL,                                 /* sub */
 164   NULL,                                 /* next */
 165   0,                                    /* static_pass_number */
 166   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 167   PROP_cfg,                             /* properties_required */
 168   0,                                    /* properties_provided */
 169   0,                                    /* properties_destroyed */
 170   0,                                    /* todo_flags_start */
 171   TODO_ggc_collect | TODO_dump_func
 172     | TODO_verify_loops,                /* todo_flags_finish */
 173   0                                     /* letter */
 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 tree_opt_pass pass_predcom =
 195 {
 196   "pcom",                               /* name */
 197   gate_tree_predictive_commoning,       /* gate */
 198   run_tree_predictive_commoning,        /* execute */
 199   NULL,                                 /* sub */
 200   NULL,                                 /* next */
 201   0,                                    /* static_pass_number */
 202   TV_PREDCOM,                           /* tv_id */
 203   PROP_cfg,                             /* properties_required */
 204   0,                                    /* properties_provided */
 205   0,                                    /* properties_destroyed */
 206   0,                                    /* todo_flags_start */
 207   TODO_dump_func | TODO_verify_loops
 208     | TODO_update_ssa_only_virtuals,    /* todo_flags_finish */
 209   0                                     /* letter */
 210 };
 211
 212 /* Loop autovectorization.  */
 213
 214 static unsigned int
 215 tree_vectorize (void)
 216 {
 217   return vectorize_loops ();
 218 }
 219
 220 static bool
 221 gate_tree_vectorize (void)
 222 {
 223   return flag_tree_vectorize && number_of_loops () > 1;
 224 }
 225
 226 struct tree_opt_pass pass_vectorize =
 227 {
 228   "vect",                               /* name */
 229   gate_tree_vectorize,                  /* gate */
 230   tree_vectorize,                       /* execute */
 231   NULL,                                 /* sub */
 232   NULL,                                 /* next */
 233   0,                                    /* static_pass_number */
 234   TV_TREE_VECTORIZATION,                /* tv_id */
 235   PROP_cfg | PROP_ssa,                  /* properties_required */
 236   0,                                    /* properties_provided */
 237   0,                                    /* properties_destroyed */
 238   TODO_verify_loops,                    /* todo_flags_start */
 239   TODO_dump_func | TODO_update_ssa
 240     | TODO_ggc_collect,                 /* todo_flags_finish */
 241   0                                     /* letter */
 242 };
 243
 244 /* Loop nest optimizations.  */
 245
 246 static unsigned int
 247 tree_linear_transform (void)
 248 {
 249   if (number_of_loops () <= 1)
 250     return 0;
 251
 252   linear_transform_loops ();
 253   return 0;
 254 }
 255
 256 static bool
 257 gate_tree_linear_transform (void)
 258 {
 259   return flag_tree_loop_linear != 0;
 260 }
 261
 262 struct tree_opt_pass pass_linear_transform =
 263 {
 264   "ltrans",                             /* name */
 265   gate_tree_linear_transform,           /* gate */
 266   tree_linear_transform,                /* execute */
 267   NULL,                                 /* sub */
 268   NULL,                                 /* next */
 269   0,                                    /* static_pass_number */
 270   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 271   PROP_cfg | PROP_ssa,                  /* properties_required */
 272   0,                                    /* properties_provided */
 273   0,                                    /* properties_destroyed */
 274   0,                                    /* todo_flags_start */
 275   TODO_dump_func | TODO_verify_loops
 276     | TODO_ggc_collect,                 /* todo_flags_finish */
 277   0                                     /* letter */
 278 };
 279
 280 /* Check the correctness of the data dependence analyzers.  */
 281
 282 static unsigned int
 283 check_data_deps (void)
 284 {
 285   if (number_of_loops () <= 1)
 286     return 0;
 287
 288   tree_check_data_deps ();
 289   return 0;
 290 }
 291
 292 static bool
 293 gate_check_data_deps (void)
 294 {
 295   return flag_check_data_deps != 0;
 296 }
 297
 298 struct tree_opt_pass pass_check_data_deps =
 299 {
 300   "ckdd",                               /* name */
 301   gate_check_data_deps,                 /* gate */
 302   check_data_deps,                      /* execute */
 303   NULL,                                 /* sub */
 304   NULL,                                 /* next */
 305   0,                                    /* static_pass_number */
 306   TV_CHECK_DATA_DEPS,                   /* 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   0                                     /* letter */
 313 };
 314
 315 /* Canonical induction variable creation pass.  */
 316
 317 static unsigned int
 318 tree_ssa_loop_ivcanon (void)
 319 {
 320   if (number_of_loops () <= 1)
 321     return 0;
 322
 323   return canonicalize_induction_variables ();
 324 }
 325
 326 static bool
 327 gate_tree_ssa_loop_ivcanon (void)
 328 {
 329   return flag_tree_loop_ivcanon != 0;
 330 }
 331
 332 struct tree_opt_pass pass_iv_canon =
 333 {
 334   "ivcanon",                            /* name */
 335   gate_tree_ssa_loop_ivcanon,           /* gate */
 336   tree_ssa_loop_ivcanon,                /* execute */
 337   NULL,                                 /* sub */
 338   NULL,                                 /* next */
 339   0,                                    /* static_pass_number */
 340   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 341   PROP_cfg | PROP_ssa,                  /* properties_required */
 342   0,                                    /* properties_provided */
 343   0,                                    /* properties_destroyed */
 344   0,                                    /* todo_flags_start */
 345   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 346   0                                     /* letter */
 347 };
 348
 349 /* Propagation of constants using scev.  */
 350
 351 static bool
 352 gate_scev_const_prop (void)
 353 {
 354   return flag_tree_scev_cprop;
 355 }
 356
 357 struct tree_opt_pass pass_scev_cprop =
 358 {
 359   "sccp",                               /* name */
 360   gate_scev_const_prop,                 /* gate */
 361   scev_const_prop,                      /* execute */
 362   NULL,                                 /* sub */
 363   NULL,                                 /* next */
 364   0,                                    /* static_pass_number */
 365   TV_SCEV_CONST,                        /* tv_id */
 366   PROP_cfg | PROP_ssa,                  /* properties_required */
 367   0,                                    /* properties_provided */
 368   0,                                    /* properties_destroyed */
 369   0,                                    /* todo_flags_start */
 370   TODO_dump_func | TODO_cleanup_cfg
 371     | TODO_update_ssa_only_virtuals,
 372                                         /* todo_flags_finish */
 373   0                                     /* letter */
 374 };
 375
 376 /* Remove empty loops.  */
 377
 378 static unsigned int
 379 tree_ssa_empty_loop (void)
 380 {
 381   if (number_of_loops () <= 1)
 382     return 0;
 383
 384   return remove_empty_loops ();
 385 }
 386
 387 struct tree_opt_pass pass_empty_loop =
 388 {
 389   "empty",                              /* name */
 390   NULL,                                 /* gate */
 391   tree_ssa_empty_loop,                  /* execute */
 392   NULL,                                 /* sub */
 393   NULL,                                 /* next */
 394   0,                                    /* static_pass_number */
 395   TV_COMPLETE_UNROLL,                   /* 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_verify_loops
 401     | TODO_ggc_collect,                 /* todo_flags_finish */
 402   0                                     /* letter */
 403 };
 404
 405 /* Record bounds on numbers of iterations of loops.  */
 406
 407 static unsigned int
 408 tree_ssa_loop_bounds (void)
 409 {
 410   if (number_of_loops () <= 1)
 411     return 0;
 412
 413   estimate_numbers_of_iterations ();
 414   scev_reset ();
 415   return 0;
 416 }
 417
 418 struct tree_opt_pass pass_record_bounds =
 419 {
 420   NULL,                                 /* name */
 421   NULL,                                 /* gate */
 422   tree_ssa_loop_bounds,                 /* execute */
 423   NULL,                                 /* sub */
 424   NULL,                                 /* next */
 425   0,                                    /* static_pass_number */
 426   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 427   PROP_cfg | PROP_ssa,                  /* properties_required */
 428   0,                                    /* properties_provided */
 429   0,                                    /* properties_destroyed */
 430   0,                                    /* todo_flags_start */
 431   0,                                    /* todo_flags_finish */
 432   0                                     /* letter */
 433 };
 434
 435 /* Complete unrolling of loops.  */
 436
 437 static unsigned int
 438 tree_complete_unroll (void)
 439 {
 440   if (number_of_loops () <= 1)
 441     return 0;
 442
 443   return tree_unroll_loops_completely (flag_unroll_loops
 444                                        || flag_peel_loops
 445                                        || optimize >= 3);
 446 }
 447
 448 static bool
 449 gate_tree_complete_unroll (void)
 450 {
 451   return true;
 452 }
 453
 454 struct tree_opt_pass pass_complete_unroll =
 455 {
 456   "cunroll",                            /* name */
 457   gate_tree_complete_unroll,            /* gate */
 458   tree_complete_unroll,                 /* execute */
 459   NULL,                                 /* sub */
 460   NULL,                                 /* next */
 461   0,                                    /* static_pass_number */
 462   TV_COMPLETE_UNROLL,                   /* tv_id */
 463   PROP_cfg | PROP_ssa,                  /* properties_required */
 464   0,                                    /* properties_provided */
 465   0,                                    /* properties_destroyed */
 466   0,                                    /* todo_flags_start */
 467   TODO_dump_func | TODO_verify_loops
 468     | TODO_ggc_collect,                 /* todo_flags_finish */
 469   0                                     /* letter */
 470 };
 471
 472 /* Prefetching.  */
 473
 474 static unsigned int
 475 tree_ssa_loop_prefetch (void)
 476 {
 477   if (number_of_loops () <= 1)
 478     return 0;
 479
 480   return tree_ssa_prefetch_arrays ();
 481 }
 482
 483 static bool
 484 gate_tree_ssa_loop_prefetch (void)
 485 {
 486   return flag_prefetch_loop_arrays != 0;
 487 }
 488
 489 struct tree_opt_pass pass_loop_prefetch =
 490 {
 491   "aprefetch",                          /* name */
 492   gate_tree_ssa_loop_prefetch,          /* gate */
 493   tree_ssa_loop_prefetch,               /* execute */
 494   NULL,                                 /* sub */
 495   NULL,                                 /* next */
 496   0,                                    /* static_pass_number */
 497   TV_TREE_PREFETCH,                     /* 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 | TODO_verify_loops,   /* todo_flags_finish */
 503   0                                     /* letter */
 504 };
 505
 506 /* Induction variable optimizations.  */
 507
 508 static unsigned int
 509 tree_ssa_loop_ivopts (void)
 510 {
 511   if (number_of_loops () <= 1)
 512     return 0;
 513
 514   tree_ssa_iv_optimize ();
 515   return 0;
 516 }
 517
 518 static bool
 519 gate_tree_ssa_loop_ivopts (void)
 520 {
 521   return flag_ivopts != 0;
 522 }
 523
 524 struct tree_opt_pass pass_iv_optimize =
 525 {
 526   "ivopts",                             /* name */
 527   gate_tree_ssa_loop_ivopts,            /* gate */
 528   tree_ssa_loop_ivopts,                 /* execute */
 529   NULL,                                 /* sub */
 530   NULL,                                 /* next */
 531   0,                                    /* static_pass_number */
 532   TV_TREE_LOOP_IVOPTS,                  /* 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
 538   | TODO_update_ssa | TODO_ggc_collect, /* todo_flags_finish */
 539   0                                     /* letter */
 540 };
 541
 542 /* Loop optimizer finalization.  */
 543
 544 static unsigned int
 545 tree_ssa_loop_done (void)
 546 {
 547   free_numbers_of_iterations_estimates ();
 548   scev_finalize ();
 549   loop_optimizer_finalize ();
 550   return 0;
 551 }
 552
 553 struct tree_opt_pass pass_tree_loop_done =
 554 {
 555   "loopdone",                           /* name */
 556   NULL,                                 /* gate */
 557   tree_ssa_loop_done,                   /* execute */
 558   NULL,                                 /* sub */
 559   NULL,                                 /* next */
 560   0,                                    /* static_pass_number */
 561   TV_TREE_LOOP_FINI,                    /* tv_id */
 562   PROP_cfg,                             /* properties_required */
 563   0,                                    /* properties_provided */
 564   0,                                    /* properties_destroyed */
 565   0,                                    /* todo_flags_start */
 566   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 567   0                                     /* letter */
 568 };