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