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