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   if (!current_loops)
  49     return;
  50
  51   rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
  52 }
  53
  54 /* The loop superpass.  */
  55
  56 static bool
  57 gate_tree_loop (void)
  58 {
  59   return flag_tree_loop_optimize != 0;
  60 }
  61
  62 struct tree_opt_pass pass_tree_loop =
  63 {
  64   "loop",                               /* name */
  65   gate_tree_loop,                       /* gate */
  66   NULL,                                 /* execute */
  67   NULL,                                 /* sub */
  68   NULL,                                 /* next */
  69   0,                                    /* static_pass_number */
  70   TV_TREE_LOOP,                         /* tv_id */
  71   PROP_cfg,                             /* properties_required */
  72   0,                                    /* properties_provided */
  73   0,                                    /* properties_destroyed */
  74   TODO_ggc_collect,                     /* todo_flags_start */
  75   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,  /* todo_flags_finish */
  76   0                                     /* letter */
  77 };
  78
  79 /* Loop optimizer initialization.  */
  80
  81 static unsigned int
  82 tree_ssa_loop_init (void)
  83 {
  84   tree_loop_optimizer_init ();
  85   if (!current_loops)
  86     return 0;
  87
  88   scev_initialize ();
  89   return 0;
  90 }
  91
  92 struct tree_opt_pass pass_tree_loop_init =
  93 {
  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   0                                     /* letter */
 107 };
 108
 109 /* Loop invariant motion pass.  */
 110
 111 static unsigned int
 112 tree_ssa_loop_im (void)
 113 {
 114   if (!current_loops)
 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 tree_opt_pass pass_lim =
 128 {
 129   "lim",                                /* name */
 130   gate_tree_ssa_loop_im,                /* gate */
 131   tree_ssa_loop_im,                     /* execute */
 132   NULL,                                 /* sub */
 133   NULL,                                 /* next */
 134   0,                                    /* static_pass_number */
 135   TV_LIM,                               /* tv_id */
 136   PROP_cfg,                             /* properties_required */
 137   0,                                    /* properties_provided */
 138   0,                                    /* properties_destroyed */
 139   0,                                    /* todo_flags_start */
 140   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 141   0                                     /* letter */
 142 };
 143
 144 /* Loop unswitching pass.  */
 145
 146 static unsigned int
 147 tree_ssa_loop_unswitch (void)
 148 {
 149   if (!current_loops)
 150     return 0;
 151
 152   return tree_ssa_unswitch_loops ();
 153 }
 154
 155 static bool
 156 gate_tree_ssa_loop_unswitch (void)
 157 {
 158   return flag_unswitch_loops != 0;
 159 }
 160
 161 struct tree_opt_pass pass_tree_unswitch =
 162 {
 163   "unswitch",                           /* name */
 164   gate_tree_ssa_loop_unswitch,          /* gate */
 165   tree_ssa_loop_unswitch,               /* execute */
 166   NULL,                                 /* sub */
 167   NULL,                                 /* next */
 168   0,                                    /* static_pass_number */
 169   TV_TREE_LOOP_UNSWITCH,                /* tv_id */
 170   PROP_cfg,                             /* properties_required */
 171   0,                                    /* properties_provided */
 172   0,                                    /* properties_destroyed */
 173   0,                                    /* todo_flags_start */
 174   TODO_ggc_collect | TODO_dump_func
 175     | TODO_verify_loops,                /* todo_flags_finish */
 176   0                                     /* letter */
 177 };
 178
 179 /* Loop autovectorization.  */
 180
 181 static unsigned int
 182 tree_vectorize (void)
 183 {
 184   return vectorize_loops ();
 185 }
 186
 187 static bool
 188 gate_tree_vectorize (void)
 189 {
 190   return flag_tree_vectorize && current_loops;
 191 }
 192
 193 struct tree_opt_pass pass_vectorize =
 194 {
 195   "vect",                               /* name */
 196   gate_tree_vectorize,                  /* gate */
 197   tree_vectorize,                       /* execute */
 198   NULL,                                 /* sub */
 199   NULL,                                 /* next */
 200   0,                                    /* static_pass_number */
 201   TV_TREE_VECTORIZATION,                /* tv_id */
 202   PROP_cfg | PROP_ssa,                  /* properties_required */
 203   0,                                    /* properties_provided */
 204   0,                                    /* properties_destroyed */
 205   TODO_verify_loops,                    /* todo_flags_start */
 206   TODO_dump_func | TODO_update_ssa
 207     | TODO_ggc_collect,                 /* todo_flags_finish */
 208   0                                     /* letter */
 209 };
 210
 211 /* Loop nest optimizations.  */
 212
 213 static unsigned int
 214 tree_linear_transform (void)
 215 {
 216   if (!current_loops)
 217     return 0;
 218
 219   linear_transform_loops ();
 220   return 0;
 221 }
 222
 223 static bool
 224 gate_tree_linear_transform (void)
 225 {
 226   return flag_tree_loop_linear != 0;
 227 }
 228
 229 struct tree_opt_pass pass_linear_transform =
 230 {
 231   "ltrans",                             /* name */
 232   gate_tree_linear_transform,           /* gate */
 233   tree_linear_transform,                /* execute */
 234   NULL,                                 /* sub */
 235   NULL,                                 /* next */
 236   0,                                    /* static_pass_number */
 237   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 238   PROP_cfg | PROP_ssa,                  /* properties_required */
 239   0,                                    /* properties_provided */
 240   0,                                    /* properties_destroyed */
 241   0,                                    /* todo_flags_start */
 242   TODO_dump_func | TODO_verify_loops
 243     | TODO_ggc_collect,                 /* todo_flags_finish */
 244   0                                     /* letter */
 245 };
 246
 247 /* Check the correctness of the data dependence analyzers.  */
 248
 249 static unsigned int
 250 check_data_deps (void)
 251 {
 252   if (!current_loops)
 253     return 0;
 254
 255   tree_check_data_deps ();
 256   return 0;
 257 }
 258
 259 static bool
 260 gate_check_data_deps (void)
 261 {
 262   return flag_check_data_deps != 0;
 263 }
 264
 265 struct tree_opt_pass pass_check_data_deps =
 266 {
 267   "ckdd",                               /* name */
 268   gate_check_data_deps,                 /* gate */
 269   check_data_deps,                      /* execute */
 270   NULL,                                 /* sub */
 271   NULL,                                 /* next */
 272   0,                                    /* static_pass_number */
 273   TV_CHECK_DATA_DEPS,                   /* tv_id */
 274   PROP_cfg | PROP_ssa,                  /* properties_required */
 275   0,                                    /* properties_provided */
 276   0,                                    /* properties_destroyed */
 277   0,                                    /* todo_flags_start */
 278   TODO_dump_func,                       /* todo_flags_finish */
 279   0                                     /* letter */
 280 };
 281
 282 /* Canonical induction variable creation pass.  */
 283
 284 static unsigned int
 285 tree_ssa_loop_ivcanon (void)
 286 {
 287   if (!current_loops)
 288     return 0;
 289
 290   return canonicalize_induction_variables ();
 291 }
 292
 293 static bool
 294 gate_tree_ssa_loop_ivcanon (void)
 295 {
 296   return flag_tree_loop_ivcanon != 0;
 297 }
 298
 299 struct tree_opt_pass pass_iv_canon =
 300 {
 301   "ivcanon",                            /* name */
 302   gate_tree_ssa_loop_ivcanon,           /* gate */
 303   tree_ssa_loop_ivcanon,                /* execute */
 304   NULL,                                 /* sub */
 305   NULL,                                 /* next */
 306   0,                                    /* static_pass_number */
 307   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 308   PROP_cfg | PROP_ssa,                  /* properties_required */
 309   0,                                    /* properties_provided */
 310   0,                                    /* properties_destroyed */
 311   0,                                    /* todo_flags_start */
 312   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 313   0                                     /* letter */
 314 };
 315
 316 /* Propagation of constants using scev.  */
 317
 318 static bool
 319 gate_scev_const_prop (void)
 320 {
 321   return flag_tree_scev_cprop;
 322 }
 323
 324 struct tree_opt_pass pass_scev_cprop =
 325 {
 326   "sccp",                               /* name */
 327   gate_scev_const_prop,                 /* gate */
 328   scev_const_prop,                      /* execute */
 329   NULL,                                 /* sub */
 330   NULL,                                 /* next */
 331   0,                                    /* static_pass_number */
 332   TV_SCEV_CONST,                        /* tv_id */
 333   PROP_cfg | PROP_ssa,                  /* properties_required */
 334   0,                                    /* properties_provided */
 335   0,                                    /* properties_destroyed */
 336   0,                                    /* todo_flags_start */
 337   TODO_dump_func | TODO_cleanup_cfg
 338     | TODO_update_ssa_only_virtuals,
 339                                         /* todo_flags_finish */
 340   0                                     /* letter */
 341 };
 342
 343 /* Remove empty loops.  */
 344
 345 static unsigned int
 346 tree_ssa_empty_loop (void)
 347 {
 348   if (!current_loops)
 349     return 0;
 350
 351   return remove_empty_loops ();
 352 }
 353
 354 struct tree_opt_pass pass_empty_loop =
 355 {
 356   "empty",                              /* name */
 357   NULL,                                 /* gate */
 358   tree_ssa_empty_loop,                  /* execute */
 359   NULL,                                 /* sub */
 360   NULL,                                 /* next */
 361   0,                                    /* static_pass_number */
 362   TV_COMPLETE_UNROLL,                   /* tv_id */
 363   PROP_cfg | PROP_ssa,                  /* properties_required */
 364   0,                                    /* properties_provided */
 365   0,                                    /* properties_destroyed */
 366   0,                                    /* todo_flags_start */
 367   TODO_dump_func | TODO_verify_loops
 368     | TODO_ggc_collect,                 /* todo_flags_finish */
 369   0                                     /* letter */
 370 };
 371
 372 /* Record bounds on numbers of iterations of loops.  */
 373
 374 static unsigned int
 375 tree_ssa_loop_bounds (void)
 376 {
 377   if (!current_loops)
 378     return 0;
 379
 380   estimate_numbers_of_iterations ();
 381   scev_reset ();
 382   return 0;
 383 }
 384
 385 struct tree_opt_pass pass_record_bounds =
 386 {
 387   NULL,                                 /* name */
 388   NULL,                                 /* gate */
 389   tree_ssa_loop_bounds,                 /* execute */
 390   NULL,                                 /* sub */
 391   NULL,                                 /* next */
 392   0,                                    /* static_pass_number */
 393   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 394   PROP_cfg | PROP_ssa,                  /* properties_required */
 395   0,                                    /* properties_provided */
 396   0,                                    /* properties_destroyed */
 397   0,                                    /* todo_flags_start */
 398   0,                                    /* todo_flags_finish */
 399   0                                     /* letter */
 400 };
 401
 402 /* Complete unrolling of loops.  */
 403
 404 static unsigned int
 405 tree_complete_unroll (void)
 406 {
 407   if (!current_loops)
 408     return 0;
 409
 410   return tree_unroll_loops_completely (flag_unroll_loops
 411                                        || flag_peel_loops
 412                                        || optimize >= 3);
 413 }
 414
 415 static bool
 416 gate_tree_complete_unroll (void)
 417 {
 418   return true;
 419 }
 420
 421 struct tree_opt_pass pass_complete_unroll =
 422 {
 423   "cunroll",                            /* name */
 424   gate_tree_complete_unroll,            /* gate */
 425   tree_complete_unroll,                 /* execute */
 426   NULL,                                 /* sub */
 427   NULL,                                 /* next */
 428   0,                                    /* static_pass_number */
 429   TV_COMPLETE_UNROLL,                   /* tv_id */
 430   PROP_cfg | PROP_ssa,                  /* properties_required */
 431   0,                                    /* properties_provided */
 432   0,                                    /* properties_destroyed */
 433   0,                                    /* todo_flags_start */
 434   TODO_dump_func | TODO_verify_loops
 435     | TODO_ggc_collect,                 /* todo_flags_finish */
 436   0                                     /* letter */
 437 };
 438
 439 /* Prefetching.  */
 440
 441 static unsigned int
 442 tree_ssa_loop_prefetch (void)
 443 {
 444   if (!current_loops)
 445     return 0;
 446
 447   return tree_ssa_prefetch_arrays ();
 448 }
 449
 450 static bool
 451 gate_tree_ssa_loop_prefetch (void)
 452 {
 453   return flag_prefetch_loop_arrays != 0;
 454 }
 455
 456 struct tree_opt_pass pass_loop_prefetch =
 457 {
 458   "aprefetch",                          /* name */
 459   gate_tree_ssa_loop_prefetch,          /* gate */
 460   tree_ssa_loop_prefetch,               /* execute */
 461   NULL,                                 /* sub */
 462   NULL,                                 /* next */
 463   0,                                    /* static_pass_number */
 464   TV_TREE_PREFETCH,                     /* tv_id */
 465   PROP_cfg | PROP_ssa,                  /* properties_required */
 466   0,                                    /* properties_provided */
 467   0,                                    /* properties_destroyed */
 468   0,                                    /* todo_flags_start */
 469   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 470   0                                     /* letter */
 471 };
 472
 473 /* Induction variable optimizations.  */
 474
 475 static unsigned int
 476 tree_ssa_loop_ivopts (void)
 477 {
 478   if (!current_loops)
 479     return 0;
 480
 481   tree_ssa_iv_optimize ();
 482   return 0;
 483 }
 484
 485 static bool
 486 gate_tree_ssa_loop_ivopts (void)
 487 {
 488   return flag_ivopts != 0;
 489 }
 490
 491 struct tree_opt_pass pass_iv_optimize =
 492 {
 493   "ivopts",                             /* name */
 494   gate_tree_ssa_loop_ivopts,            /* gate */
 495   tree_ssa_loop_ivopts,                 /* execute */
 496   NULL,                                 /* sub */
 497   NULL,                                 /* next */
 498   0,                                    /* static_pass_number */
 499   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 500   PROP_cfg | PROP_ssa,                  /* properties_required */
 501   0,                                    /* properties_provided */
 502   0,                                    /* properties_destroyed */
 503   0,                                    /* todo_flags_start */
 504   TODO_dump_func | TODO_verify_loops
 505   | TODO_update_ssa | TODO_ggc_collect, /* todo_flags_finish */
 506   0                                     /* letter */
 507 };
 508
 509 /* Loop optimizer finalization.  */
 510
 511 static unsigned int
 512 tree_ssa_loop_done (void)
 513 {
 514   if (!current_loops)
 515     return 0;
 516
 517   free_numbers_of_iterations_estimates ();
 518   scev_finalize ();
 519   loop_optimizer_finalize ();
 520   return 0;
 521 }
 522
 523 struct tree_opt_pass pass_tree_loop_done =
 524 {
 525   "loopdone",                           /* name */
 526   NULL,                                 /* gate */
 527   tree_ssa_loop_done,                   /* execute */
 528   NULL,                                 /* sub */
 529   NULL,                                 /* next */
 530   0,                                    /* static_pass_number */
 531   TV_TREE_LOOP_FINI,                    /* tv_id */
 532   PROP_cfg,                             /* properties_required */
 533   0,                                    /* properties_provided */
 534   0,                                    /* properties_destroyed */
 535   0,                                    /* todo_flags_start */
 536   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 537   0                                     /* letter */
 538 };