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