gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003, 2005 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_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 175   0                                     /* letter */
 176 };
 177
 178 /* Loop autovectorization.  */
 179
 180 static unsigned int
 181 tree_vectorize (void)
 182 {
 183   return vectorize_loops ();
 184 }
 185
 186 static bool
 187 gate_tree_vectorize (void)
 188 {
 189   return flag_tree_vectorize && current_loops;
 190 }
 191
 192 struct tree_opt_pass pass_vectorize =
 193 {
 194   "vect",                               /* name */
 195   gate_tree_vectorize,                  /* gate */
 196   tree_vectorize,                       /* execute */
 197   NULL,                                 /* sub */
 198   NULL,                                 /* next */
 199   0,                                    /* static_pass_number */
 200   TV_TREE_VECTORIZATION,                /* tv_id */
 201   PROP_cfg | PROP_ssa,                  /* properties_required */
 202   0,                                    /* properties_provided */
 203   0,                                    /* properties_destroyed */
 204   TODO_verify_loops,                    /* todo_flags_start */
 205   TODO_dump_func | TODO_update_ssa,     /* todo_flags_finish */
 206   0                                     /* letter */
 207 };
 208
 209 /* Loop nest optimizations.  */
 210
 211 static unsigned int
 212 tree_linear_transform (void)
 213 {
 214   if (!current_loops)
 215     return 0;
 216
 217   linear_transform_loops ();
 218   return 0;
 219 }
 220
 221 static bool
 222 gate_tree_linear_transform (void)
 223 {
 224   return flag_tree_loop_linear != 0;
 225 }
 226
 227 struct tree_opt_pass pass_linear_transform =
 228 {
 229   "ltrans",                             /* name */
 230   gate_tree_linear_transform,           /* gate */
 231   tree_linear_transform,                /* execute */
 232   NULL,                                 /* sub */
 233   NULL,                                 /* next */
 234   0,                                    /* static_pass_number */
 235   TV_TREE_LINEAR_TRANSFORM,             /* tv_id */
 236   PROP_cfg | PROP_ssa,                  /* properties_required */
 237   0,                                    /* properties_provided */
 238   0,                                    /* properties_destroyed */
 239   0,                                    /* todo_flags_start */
 240   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 241   0                                     /* letter */
 242 };
 243
 244 /* Canonical induction variable creation pass.  */
 245
 246 static unsigned int
 247 tree_ssa_loop_ivcanon (void)
 248 {
 249   if (!current_loops)
 250     return 0;
 251
 252   return canonicalize_induction_variables ();
 253 }
 254
 255 static bool
 256 gate_tree_ssa_loop_ivcanon (void)
 257 {
 258   return flag_tree_loop_ivcanon != 0;
 259 }
 260
 261 struct tree_opt_pass pass_iv_canon =
 262 {
 263   "ivcanon",                            /* name */
 264   gate_tree_ssa_loop_ivcanon,           /* gate */
 265   tree_ssa_loop_ivcanon,                /* execute */
 266   NULL,                                 /* sub */
 267   NULL,                                 /* next */
 268   0,                                    /* static_pass_number */
 269   TV_TREE_LOOP_IVCANON,                 /* 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,   /* todo_flags_finish */
 275   0                                     /* letter */
 276 };
 277
 278 /* Propagation of constants using scev.  */
 279
 280 static bool
 281 gate_scev_const_prop (void)
 282 {
 283   return true;
 284 }
 285
 286 struct tree_opt_pass pass_scev_cprop =
 287 {
 288   "sccp",                               /* name */
 289   gate_scev_const_prop,                 /* gate */
 290   scev_const_prop,                      /* execute */
 291   NULL,                                 /* sub */
 292   NULL,                                 /* next */
 293   0,                                    /* static_pass_number */
 294   TV_SCEV_CONST,                        /* tv_id */
 295   PROP_cfg | PROP_ssa,                  /* properties_required */
 296   0,                                    /* properties_provided */
 297   0,                                    /* properties_destroyed */
 298   0,                                    /* todo_flags_start */
 299   TODO_dump_func | TODO_cleanup_cfg
 300     | TODO_update_ssa_only_virtuals,
 301                                         /* todo_flags_finish */
 302   0                                     /* letter */
 303 };
 304
 305 /* Remove empty loops.  */
 306
 307 static unsigned int
 308 tree_ssa_empty_loop (void)
 309 {
 310   if (!current_loops)
 311     return 0;
 312
 313   return remove_empty_loops ();
 314 }
 315
 316 struct tree_opt_pass pass_empty_loop =
 317 {
 318   "empty",                              /* name */
 319   NULL,                                 /* gate */
 320   tree_ssa_empty_loop,                  /* execute */
 321   NULL,                                 /* sub */
 322   NULL,                                 /* next */
 323   0,                                    /* static_pass_number */
 324   TV_COMPLETE_UNROLL,                   /* tv_id */
 325   PROP_cfg | PROP_ssa,                  /* properties_required */
 326   0,                                    /* properties_provided */
 327   0,                                    /* properties_destroyed */
 328   0,                                    /* todo_flags_start */
 329   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 330   0                                     /* letter */
 331 };
 332
 333 /* Record bounds on numbers of iterations of loops.  */
 334
 335 static unsigned int
 336 tree_ssa_loop_bounds (void)
 337 {
 338   if (!current_loops)
 339     return 0;
 340
 341   estimate_numbers_of_iterations ();
 342   scev_reset ();
 343   return 0;
 344 }
 345
 346 struct tree_opt_pass pass_record_bounds =
 347 {
 348   NULL,                                 /* name */
 349   NULL,                                 /* gate */
 350   tree_ssa_loop_bounds,                 /* execute */
 351   NULL,                                 /* sub */
 352   NULL,                                 /* next */
 353   0,                                    /* static_pass_number */
 354   TV_TREE_LOOP_BOUNDS,                  /* tv_id */
 355   PROP_cfg | PROP_ssa,                  /* properties_required */
 356   0,                                    /* properties_provided */
 357   0,                                    /* properties_destroyed */
 358   0,                                    /* todo_flags_start */
 359   0,                                    /* todo_flags_finish */
 360   0                                     /* letter */
 361 };
 362
 363 /* Complete unrolling of loops.  */
 364
 365 static unsigned int
 366 tree_complete_unroll (void)
 367 {
 368   if (!current_loops)
 369     return 0;
 370
 371   return tree_unroll_loops_completely (flag_unroll_loops
 372                                        || flag_peel_loops
 373                                        || optimize >= 3);
 374 }
 375
 376 static bool
 377 gate_tree_complete_unroll (void)
 378 {
 379   return true;
 380 }
 381
 382 struct tree_opt_pass pass_complete_unroll =
 383 {
 384   "cunroll",                            /* name */
 385   gate_tree_complete_unroll,            /* gate */
 386   tree_complete_unroll,                 /* execute */
 387   NULL,                                 /* sub */
 388   NULL,                                 /* next */
 389   0,                                    /* static_pass_number */
 390   TV_COMPLETE_UNROLL,                   /* tv_id */
 391   PROP_cfg | PROP_ssa,                  /* properties_required */
 392   0,                                    /* properties_provided */
 393   0,                                    /* properties_destroyed */
 394   0,                                    /* todo_flags_start */
 395   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 396   0                                     /* letter */
 397 };
 398
 399 /* Prefetching.  */
 400
 401 static unsigned int
 402 tree_ssa_loop_prefetch (void)
 403 {
 404   if (!current_loops)
 405     return 0;
 406
 407   return tree_ssa_prefetch_arrays ();
 408 }
 409
 410 static bool
 411 gate_tree_ssa_loop_prefetch (void)
 412 {
 413   return flag_prefetch_loop_arrays != 0;
 414 }
 415
 416 struct tree_opt_pass pass_loop_prefetch =
 417 {
 418   "aprefetch",                          /* name */
 419   gate_tree_ssa_loop_prefetch,          /* gate */
 420   tree_ssa_loop_prefetch,               /* execute */
 421   NULL,                                 /* sub */
 422   NULL,                                 /* next */
 423   0,                                    /* static_pass_number */
 424   TV_TREE_PREFETCH,                     /* tv_id */
 425   PROP_cfg | PROP_ssa,                  /* properties_required */
 426   0,                                    /* properties_provided */
 427   0,                                    /* properties_destroyed */
 428   0,                                    /* todo_flags_start */
 429   TODO_dump_func | TODO_verify_loops,   /* todo_flags_finish */
 430   0                                     /* letter */
 431 };
 432
 433 /* Induction variable optimizations.  */
 434
 435 static unsigned int
 436 tree_ssa_loop_ivopts (void)
 437 {
 438   if (!current_loops)
 439     return 0;
 440
 441   tree_ssa_iv_optimize ();
 442   return 0;
 443 }
 444
 445 static bool
 446 gate_tree_ssa_loop_ivopts (void)
 447 {
 448   return flag_ivopts != 0;
 449 }
 450
 451 struct tree_opt_pass pass_iv_optimize =
 452 {
 453   "ivopts",                             /* name */
 454   gate_tree_ssa_loop_ivopts,            /* gate */
 455   tree_ssa_loop_ivopts,                 /* execute */
 456   NULL,                                 /* sub */
 457   NULL,                                 /* next */
 458   0,                                    /* static_pass_number */
 459   TV_TREE_LOOP_IVOPTS,                  /* tv_id */
 460   PROP_cfg | PROP_ssa,                  /* properties_required */
 461   0,                                    /* properties_provided */
 462   0,                                    /* properties_destroyed */
 463   0,                                    /* todo_flags_start */
 464   TODO_dump_func
 465   | TODO_verify_loops
 466   | TODO_update_ssa,                    /* todo_flags_finish */
 467   0                                     /* letter */
 468 };
 469
 470 /* Loop optimizer finalization.  */
 471
 472 static unsigned int
 473 tree_ssa_loop_done (void)
 474 {
 475   if (!current_loops)
 476     return 0;
 477
 478   free_numbers_of_iterations_estimates ();
 479   scev_finalize ();
 480   loop_optimizer_finalize ();
 481   return 0;
 482 }
 483
 484 struct tree_opt_pass pass_tree_loop_done =
 485 {
 486   "loopdone",                           /* name */
 487   NULL,                                 /* gate */
 488   tree_ssa_loop_done,                   /* execute */
 489   NULL,                                 /* sub */
 490   NULL,                                 /* next */
 491   0,                                    /* static_pass_number */
 492   TV_TREE_LOOP_FINI,                    /* tv_id */
 493   PROP_cfg,                             /* properties_required */
 494   0,                                    /* properties_provided */
 495   0,                                    /* properties_destroyed */
 496   0,                                    /* todo_flags_start */
 497   TODO_cleanup_cfg | TODO_dump_func,    /* todo_flags_finish */
 498   0                                     /* letter */
 499 };