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 /* Prefetching.  */
 472
 473 static unsigned int
 474 tree_ssa_loop_prefetch (void)
 475 {
 476   if (number_of_loops () <= 1)
 477     return 0;
 478
 479   return tree_ssa_prefetch_arrays ();
 480 }
 481
 482 static bool
 483 gate_tree_ssa_loop_prefetch (void)
 484 {
 485   return flag_prefetch_loop_arrays != 0;
 486 }
 487
 488 struct tree_opt_pass pass_loop_prefetch =
 489 {
 490   "aprefetch",                          /* name */
 491   gate_tree_ssa_loop_prefetch,          /* gate */
 492   tree_ssa_loop_prefetch,               /* execute */
 493   NULL,                                 /* sub */
 494   NULL,                                 /* next */
 495   0,                                    /* static_pass_number */
 496   TV_TREE_PREFETCH,                     /* tv_id */
 497   PROP_cfg | PROP_ssa,                  /* properties_required */
 498   0,                                    /* properties_provided */
 499   0,                                    /* properties_destroyed */
 500   0,                                    /* todo_flags_start */
 501   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 502   0                                     /* letter */
 503 };
 504
 505 /* Induction variable optimizations.  */
 506
 507 static unsigned int
 508 tree_ssa_loop_ivopts (void)
 509 {
 510   if (number_of_loops () <= 1)
 511     return 0;
 512
 513   tree_ssa_iv_optimize ();
 514   return 0;
 515 }
 516
 517 static bool
 518 gate_tree_ssa_loop_ivopts (void)
 519 {
 520   return flag_ivopts != 0;
 521 }
 522
 523 struct tree_opt_pass pass_iv_optimize =
 524 {
 525   "ivopts",                             /* name */
 526   gate_tree_ssa_loop_ivopts,            /* gate */
 527   tree_ssa_loop_ivopts,                 /* execute */
 528   NULL,                                 /* sub */
 529   NULL,                                 /* next */
 530   0,                                    /* static_pass_number */
 531   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 532   PROP_cfg | PROP_ssa,                  /* properties_required */
 533   0,                                    /* properties_provided */
 534   0,                                    /* properties_destroyed */
 535   0,                                    /* todo_flags_start */
 536   TODO_dump_func | TODO_verify_loops
 537   | TODO_update_ssa | TODO_ggc_collect, /* todo_flags_finish */
 538   0                                     /* letter */
 539 };
 540
 541 /* Loop optimizer finalization.  */
 542
 543 static unsigned int
 544 tree_ssa_loop_done (void)
 545 {
 546   free_numbers_of_iterations_estimates ();
 547   scev_finalize ();
 548   loop_optimizer_finalize ();
 549   return 0;
 550 }
 551
 552 struct tree_opt_pass pass_tree_loop_done =
 553 {
 554   "loopdone",                           /* name */
 555   NULL,                                 /* gate */
 556   tree_ssa_loop_done,                   /* execute */
 557   NULL,                                 /* sub */
 558   NULL,                                 /* next */
 559   0,                                    /* static_pass_number */
 560   TV_TREE_LOOP_FINI,                    /* tv_id */
 561   PROP_cfg,                             /* properties_required */
 562   0,                                    /* properties_provided */
 563   0,                                    /* properties_destroyed */
 564   0,                                    /* todo_flags_start */
 565   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 566   0                                     /* letter */
 567 };