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 /* Predictive commoning.  */
 180
 181 static unsigned
 182 run_tree_predictive_commoning (void)
 183 {
 184   if (!current_loops)
 185     return 0;
 186
 187   tree_predictive_commoning ();
 188   return 0;
 189 }
 190
 191 static bool
 192 gate_tree_predictive_commoning (void)
 193 {
 194   return flag_predictive_commoning != 0;
 195 }
 196
 197 struct tree_opt_pass pass_predcom =
 198 {
 199   "pcom",                               /* name */
 200   gate_tree_predictive_commoning,       /* gate */
 201   run_tree_predictive_commoning,        /* execute */
 202   NULL,                                 /* sub */
 203   NULL,                                 /* next */
 204   0,                                    /* static_pass_number */
 205   TV_PREDCOM,                           /* tv_id */
 206   PROP_cfg,                             /* properties_required */
 207   0,                                    /* properties_provided */
 208   0,                                    /* properties_destroyed */
 209   0,                                    /* todo_flags_start */
 210   TODO_dump_func | TODO_verify_loops
 211     | TODO_update_ssa_only_virtuals,    /* todo_flags_finish */
 212   0                                     /* letter */
 213 };
 214
 215 /* Loop autovectorization.  */
 216
 217 static unsigned int
 218 tree_vectorize (void)
 219 {
 220   return vectorize_loops ();
 221 }
 222
 223 static bool
 224 gate_tree_vectorize (void)
 225 {
 226   return flag_tree_vectorize && current_loops;
 227 }
 228
 229 struct tree_opt_pass pass_vectorize =
 230 {
 231   "vect",                               /* name */
 232   gate_tree_vectorize,                  /* gate */
 233   tree_vectorize,                       /* execute */
 234   NULL,                                 /* sub */
 235   NULL,                                 /* next */
 236   0,                                    /* static_pass_number */
 237   TV_TREE_VECTORIZATION,                /* tv_id */
 238   PROP_cfg | PROP_ssa,                  /* properties_required */
 239   0,                                    /* properties_provided */
 240   0,                                    /* properties_destroyed */
 241   TODO_verify_loops,                    /* todo_flags_start */
 242   TODO_dump_func | TODO_update_ssa
 243     | TODO_ggc_collect,                 /* todo_flags_finish */
 244   0                                     /* letter */
 245 };
 246
 247 /* Loop nest optimizations.  */
 248
 249 static unsigned int
 250 tree_linear_transform (void)
 251 {
 252   if (!current_loops)
 253     return 0;
 254
 255   linear_transform_loops ();
 256   return 0;
 257 }
 258
 259 static bool
 260 gate_tree_linear_transform (void)
 261 {
 262   return flag_tree_loop_linear != 0;
 263 }
 264
 265 struct tree_opt_pass pass_linear_transform =
 266 {
 267   "ltrans",                             /* name */
 268   gate_tree_linear_transform,           /* gate */
 269   tree_linear_transform,                /* execute */
 270   NULL,                                 /* sub */
 271   NULL,                                 /* next */
 272   0,                                    /* static_pass_number */
 273   TV_TREE_LINEAR_TRANSFORM,             /* 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_verify_loops
 279     | TODO_ggc_collect,                 /* todo_flags_finish */
 280   0                                     /* letter */
 281 };
 282
 283 /* Check the correctness of the data dependence analyzers.  */
 284
 285 static unsigned int
 286 check_data_deps (void)
 287 {
 288   if (!current_loops)
 289     return 0;
 290
 291   tree_check_data_deps ();
 292   return 0;
 293 }
 294
 295 static bool
 296 gate_check_data_deps (void)
 297 {
 298   return flag_check_data_deps != 0;
 299 }
 300
 301 struct tree_opt_pass pass_check_data_deps =
 302 {
 303   "ckdd",                               /* name */
 304   gate_check_data_deps,                 /* gate */
 305   check_data_deps,                      /* execute */
 306   NULL,                                 /* sub */
 307   NULL,                                 /* next */
 308   0,                                    /* static_pass_number */
 309   TV_CHECK_DATA_DEPS,                   /* tv_id */
 310   PROP_cfg | PROP_ssa,                  /* properties_required */
 311   0,                                    /* properties_provided */
 312   0,                                    /* properties_destroyed */
 313   0,                                    /* todo_flags_start */
 314   TODO_dump_func,                       /* todo_flags_finish */
 315   0                                     /* letter */
 316 };
 317
 318 /* Canonical induction variable creation pass.  */
 319
 320 static unsigned int
 321 tree_ssa_loop_ivcanon (void)
 322 {
 323   if (!current_loops)
 324     return 0;
 325
 326   return canonicalize_induction_variables ();
 327 }
 328
 329 static bool
 330 gate_tree_ssa_loop_ivcanon (void)
 331 {
 332   return flag_tree_loop_ivcanon != 0;
 333 }
 334
 335 struct tree_opt_pass pass_iv_canon =
 336 {
 337   "ivcanon",                            /* name */
 338   gate_tree_ssa_loop_ivcanon,           /* gate */
 339   tree_ssa_loop_ivcanon,                /* execute */
 340   NULL,                                 /* sub */
 341   NULL,                                 /* next */
 342   0,                                    /* static_pass_number */
 343   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 344   PROP_cfg | PROP_ssa,                  /* properties_required */
 345   0,                                    /* properties_provided */
 346   0,                                    /* properties_destroyed */
 347   0,                                    /* todo_flags_start */
 348   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 349   0                                     /* letter */
 350 };
 351
 352 /* Propagation of constants using scev.  */
 353
 354 static bool
 355 gate_scev_const_prop (void)
 356 {
 357   return flag_tree_scev_cprop;
 358 }
 359
 360 struct tree_opt_pass pass_scev_cprop =
 361 {
 362   "sccp",                               /* name */
 363   gate_scev_const_prop,                 /* gate */
 364   scev_const_prop,                      /* execute */
 365   NULL,                                 /* sub */
 366   NULL,                                 /* next */
 367   0,                                    /* static_pass_number */
 368   TV_SCEV_CONST,                        /* tv_id */
 369   PROP_cfg | PROP_ssa,                  /* properties_required */
 370   0,                                    /* properties_provided */
 371   0,                                    /* properties_destroyed */
 372   0,                                    /* todo_flags_start */
 373   TODO_dump_func | TODO_cleanup_cfg
 374     | TODO_update_ssa_only_virtuals,
 375                                         /* todo_flags_finish */
 376   0                                     /* letter */
 377 };
 378
 379 /* Remove empty loops.  */
 380
 381 static unsigned int
 382 tree_ssa_empty_loop (void)
 383 {
 384   if (!current_loops)
 385     return 0;
 386
 387   return remove_empty_loops ();
 388 }
 389
 390 struct tree_opt_pass pass_empty_loop =
 391 {
 392   "empty",                              /* name */
 393   NULL,                                 /* gate */
 394   tree_ssa_empty_loop,                  /* execute */
 395   NULL,                                 /* sub */
 396   NULL,                                 /* next */
 397   0,                                    /* static_pass_number */
 398   TV_COMPLETE_UNROLL,                   /* tv_id */
 399   PROP_cfg | PROP_ssa,                  /* properties_required */
 400   0,                                    /* properties_provided */
 401   0,                                    /* properties_destroyed */
 402   0,                                    /* todo_flags_start */
 403   TODO_dump_func | TODO_verify_loops
 404     | TODO_ggc_collect,                 /* todo_flags_finish */
 405   0                                     /* letter */
 406 };
 407
 408 /* Record bounds on numbers of iterations of loops.  */
 409
 410 static unsigned int
 411 tree_ssa_loop_bounds (void)
 412 {
 413   if (!current_loops)
 414     return 0;
 415
 416   estimate_numbers_of_iterations ();
 417   scev_reset ();
 418   return 0;
 419 }
 420
 421 struct tree_opt_pass pass_record_bounds =
 422 {
 423   NULL,                                 /* name */
 424   NULL,                                 /* gate */
 425   tree_ssa_loop_bounds,                 /* execute */
 426   NULL,                                 /* sub */
 427   NULL,                                 /* next */
 428   0,                                    /* static_pass_number */
 429   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 430   PROP_cfg | PROP_ssa,                  /* properties_required */
 431   0,                                    /* properties_provided */
 432   0,                                    /* properties_destroyed */
 433   0,                                    /* todo_flags_start */
 434   0,                                    /* todo_flags_finish */
 435   0                                     /* letter */
 436 };
 437
 438 /* Complete unrolling of loops.  */
 439
 440 static unsigned int
 441 tree_complete_unroll (void)
 442 {
 443   if (!current_loops)
 444     return 0;
 445
 446   return tree_unroll_loops_completely (flag_unroll_loops
 447                                        || flag_peel_loops
 448                                        || optimize >= 3);
 449 }
 450
 451 static bool
 452 gate_tree_complete_unroll (void)
 453 {
 454   return true;
 455 }
 456
 457 struct tree_opt_pass pass_complete_unroll =
 458 {
 459   "cunroll",                            /* name */
 460   gate_tree_complete_unroll,            /* gate */
 461   tree_complete_unroll,                 /* execute */
 462   NULL,                                 /* sub */
 463   NULL,                                 /* next */
 464   0,                                    /* static_pass_number */
 465   TV_COMPLETE_UNROLL,                   /* tv_id */
 466   PROP_cfg | PROP_ssa,                  /* properties_required */
 467   0,                                    /* properties_provided */
 468   0,                                    /* properties_destroyed */
 469   0,                                    /* todo_flags_start */
 470   TODO_dump_func | TODO_verify_loops
 471     | TODO_ggc_collect,                 /* todo_flags_finish */
 472   0                                     /* letter */
 473 };
 474
 475 /* Prefetching.  */
 476
 477 static unsigned int
 478 tree_ssa_loop_prefetch (void)
 479 {
 480   if (!current_loops)
 481     return 0;
 482
 483   return tree_ssa_prefetch_arrays ();
 484 }
 485
 486 static bool
 487 gate_tree_ssa_loop_prefetch (void)
 488 {
 489   return flag_prefetch_loop_arrays != 0;
 490 }
 491
 492 struct tree_opt_pass pass_loop_prefetch =
 493 {
 494   "aprefetch",                          /* name */
 495   gate_tree_ssa_loop_prefetch,          /* gate */
 496   tree_ssa_loop_prefetch,               /* execute */
 497   NULL,                                 /* sub */
 498   NULL,                                 /* next */
 499   0,                                    /* static_pass_number */
 500   TV_TREE_PREFETCH,                     /* tv_id */
 501   PROP_cfg | PROP_ssa,                  /* properties_required */
 502   0,                                    /* properties_provided */
 503   0,                                    /* properties_destroyed */
 504   0,                                    /* todo_flags_start */
 505   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 506   0                                     /* letter */
 507 };
 508
 509 /* Induction variable optimizations.  */
 510
 511 static unsigned int
 512 tree_ssa_loop_ivopts (void)
 513 {
 514   if (!current_loops)
 515     return 0;
 516
 517   tree_ssa_iv_optimize ();
 518   return 0;
 519 }
 520
 521 static bool
 522 gate_tree_ssa_loop_ivopts (void)
 523 {
 524   return flag_ivopts != 0;
 525 }
 526
 527 struct tree_opt_pass pass_iv_optimize =
 528 {
 529   "ivopts",                             /* name */
 530   gate_tree_ssa_loop_ivopts,            /* gate */
 531   tree_ssa_loop_ivopts,                 /* execute */
 532   NULL,                                 /* sub */
 533   NULL,                                 /* next */
 534   0,                                    /* static_pass_number */
 535   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 536   PROP_cfg | PROP_ssa,                  /* properties_required */
 537   0,                                    /* properties_provided */
 538   0,                                    /* properties_destroyed */
 539   0,                                    /* todo_flags_start */
 540   TODO_dump_func | TODO_verify_loops
 541   | TODO_update_ssa | TODO_ggc_collect, /* todo_flags_finish */
 542   0                                     /* letter */
 543 };
 544
 545 /* Loop optimizer finalization.  */
 546
 547 static unsigned int
 548 tree_ssa_loop_done (void)
 549 {
 550   if (!current_loops)
 551     return 0;
 552
 553   free_numbers_of_iterations_estimates ();
 554   scev_finalize ();
 555   loop_optimizer_finalize ();
 556   return 0;
 557 }
 558
 559 struct tree_opt_pass pass_tree_loop_done =
 560 {
 561   "loopdone",                           /* name */
 562   NULL,                                 /* gate */
 563   tree_ssa_loop_done,                   /* execute */
 564   NULL,                                 /* sub */
 565   NULL,                                 /* next */
 566   0,                                    /* static_pass_number */
 567   TV_TREE_LOOP_FINI,                    /* tv_id */
 568   PROP_cfg,                             /* properties_required */
 569   0,                                    /* properties_provided */
 570   0,                                    /* properties_destroyed */
 571   0,                                    /* todo_flags_start */
 572   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 573   0                                     /* letter */
 574 };