gcc/tree-ssa-loop.c

   1 /* Loop optimizations over tree-ssa.
   2    Copyright (C) 2003 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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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;
  44
  45 /* Initializes the loop structures.  DUMP is the file to that the details
  46    about the analysis should be dumped.  */
  47
  48 static struct loops *
  49 tree_loop_optimizer_init (FILE *dump)
  50 {
  51   struct loops *loops = loop_optimizer_init (dump);
  52
  53   if (!loops)
  54     return NULL;
  55
  56   /* Creation of preheaders may create redundant phi nodes if the loop is
  57      entered by more than one edge, but the initial value of the induction
  58      variable is the same on all of them.  */
  59   kill_redundant_phi_nodes ();
  60   rewrite_into_ssa (false);
  61   bitmap_clear (vars_to_rename);
  62
  63   rewrite_into_loop_closed_ssa ();
  64 #ifdef ENABLE_CHECKING
  65   verify_loop_closed_ssa ();
  66 #endif
  67
  68   return loops;
  69 }
  70
  71 /* The loop superpass.  */
  72
  73 static bool
  74 gate_loop (void)
  75 {
  76   return flag_tree_loop_optimize != 0;
  77 }
  78
  79 struct tree_opt_pass pass_loop =
  80 {
  81   "loop",                               /* name */
  82   gate_loop,                            /* gate */
  83   NULL,                                 /* execute */
  84   NULL,                                 /* sub */
  85   NULL,                                 /* next */
  86   0,                                    /* static_pass_number */
  87   TV_TREE_LOOP,                         /* tv_id */
  88   PROP_cfg,                             /* properties_required */
  89   0,                                    /* properties_provided */
  90   0,                                    /* properties_destroyed */
  91   TODO_ggc_collect,                     /* todo_flags_start */
  92   TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect   /* todo_flags_finish */
  93 };
  94
  95 /* Loop optimizer initialization.  */
  96
  97 static void
  98 tree_ssa_loop_init (void)
  99 {
 100   current_loops = tree_loop_optimizer_init (dump_file);
 101   if (!current_loops)
 102     return;
 103
 104   /* Find the loops that are exited just through a single edge.  */
 105   mark_single_exit_loops (current_loops);
 106
 107   scev_initialize (current_loops);
 108 }
 109
 110 struct tree_opt_pass pass_loop_init =
 111 {
 112   "loopinit",                           /* name */
 113   NULL,                                 /* gate */
 114   tree_ssa_loop_init,                   /* execute */
 115   NULL,                                 /* sub */
 116   NULL,                                 /* next */
 117   0,                                    /* static_pass_number */
 118   0,                                    /* tv_id */
 119   PROP_cfg,                             /* properties_required */
 120   0,                                    /* properties_provided */
 121   0,                                    /* properties_destroyed */
 122   0,                                    /* todo_flags_start */
 123   TODO_dump_func                        /* todo_flags_finish */
 124 };
 125
 126 /* Loop invariant motion pass.  */
 127
 128 static void
 129 tree_ssa_loop_im (void)
 130 {
 131   if (!current_loops)
 132     return;
 133
 134   tree_ssa_lim (current_loops);
 135 }
 136
 137 static bool
 138 gate_tree_ssa_loop_im (void)
 139 {
 140   return flag_tree_loop_im != 0;
 141 }
 142
 143 struct tree_opt_pass pass_lim =
 144 {
 145   "lim",                                /* name */
 146   gate_tree_ssa_loop_im,                /* gate */
 147   tree_ssa_loop_im,                     /* execute */
 148   NULL,                                 /* sub */
 149   NULL,                                 /* next */
 150   0,                                    /* static_pass_number */
 151   TV_LIM,                               /* tv_id */
 152   PROP_cfg,                             /* properties_required */
 153   0,                                    /* properties_provided */
 154   0,                                    /* properties_destroyed */
 155   0,                                    /* todo_flags_start */
 156   TODO_dump_func                        /* todo_flags_finish */
 157 };
 158
 159 /* Loop autovectorization.  */
 160
 161 static void
 162 tree_vectorize (void)
 163 {
 164   if (!current_loops)
 165     return;
 166
 167   bitmap_clear (vars_to_rename);
 168   vectorize_loops (current_loops);
 169 }
 170
 171 static bool
 172 gate_tree_vectorize (void)
 173 {
 174   return flag_tree_vectorize != 0;
 175 }
 176
 177 struct tree_opt_pass pass_vectorize =
 178 {
 179   "vect",                               /* name */
 180   gate_tree_vectorize,                  /* gate */
 181   tree_vectorize,                       /* execute */
 182   NULL,                                 /* sub */
 183   NULL,                                 /* next */
 184   0,                                    /* static_pass_number */
 185   TV_TREE_VECTORIZATION,                /* tv_id */
 186   PROP_cfg | PROP_ssa,                  /* properties_required */
 187   0,                                    /* properties_provided */
 188   0,                                    /* properties_destroyed */
 189   0,                                    /* todo_flags_start */
 190   TODO_dump_func                        /* todo_flags_finish */
 191 };
 192
 193 /* Canonical induction variable creation pass.  */
 194
 195 static void
 196 tree_ssa_loop_ivcanon (void)
 197 {
 198   if (!current_loops)
 199     return;
 200
 201   canonicalize_induction_variables (current_loops);
 202 }
 203
 204 static bool
 205 gate_tree_ssa_loop_ivcanon (void)
 206 {
 207   return flag_tree_loop_ivcanon != 0;
 208 }
 209
 210 struct tree_opt_pass pass_iv_canon =
 211 {
 212   "ivcanon",                            /* name */
 213   gate_tree_ssa_loop_ivcanon,           /* gate */
 214   tree_ssa_loop_ivcanon,                /* execute */
 215   NULL,                                 /* sub */
 216   NULL,                                 /* next */
 217   0,                                    /* static_pass_number */
 218   TV_TREE_LOOP_IVCANON,                 /* tv_id */
 219   PROP_cfg | PROP_ssa,                  /* properties_required */
 220   0,                                    /* properties_provided */
 221   0,                                    /* properties_destroyed */
 222   0,                                    /* todo_flags_start */
 223   TODO_dump_func                        /* todo_flags_finish */
 224 };
 225
 226 /* Complete unrolling of loops.  */
 227
 228 static void
 229 tree_complete_unroll (void)
 230 {
 231   if (!current_loops)
 232     return;
 233
 234   tree_unroll_loops_completely (current_loops);
 235 }
 236
 237 static bool
 238 gate_tree_complete_unroll (void)
 239 {
 240   return flag_unroll_loops != 0;
 241 }
 242
 243 struct tree_opt_pass pass_complete_unroll =
 244 {
 245   "cunroll",                            /* name */
 246   gate_tree_complete_unroll,            /* gate */
 247   tree_complete_unroll,                 /* execute */
 248   NULL,                                 /* sub */
 249   NULL,                                 /* next */
 250   0,                                    /* static_pass_number */
 251   TV_COMPLETE_UNROLL,                   /* tv_id */
 252   PROP_cfg | PROP_ssa,                  /* properties_required */
 253   0,                                    /* properties_provided */
 254   0,                                    /* properties_destroyed */
 255   0,                                    /* todo_flags_start */
 256   TODO_dump_func                        /* todo_flags_finish */
 257 };
 258
 259 /* Loop optimizer finalization.  */
 260
 261 static void
 262 tree_ssa_loop_done (void)
 263 {
 264   if (!current_loops)
 265     return;
 266
 267 #ifdef ENABLE_CHECKING
 268   verify_loop_closed_ssa ();
 269 #endif
 270
 271   free_numbers_of_iterations_estimates (current_loops);
 272   scev_finalize ();
 273   loop_optimizer_finalize (current_loops,
 274                            (dump_flags & TDF_DETAILS ? dump_file : NULL));
 275   current_loops = NULL;
 276   cleanup_tree_cfg ();
 277 }
 278
 279 struct tree_opt_pass pass_loop_done =
 280 {
 281   "loopdone",                           /* name */
 282   NULL,                                 /* gate */
 283   tree_ssa_loop_done,                   /* execute */
 284   NULL,                                 /* sub */
 285   NULL,                                 /* next */
 286   0,                                    /* static_pass_number */
 287   0,                                    /* tv_id */
 288   PROP_cfg,                             /* properties_required */
 289   0,                                    /* properties_provided */
 290   0,                                    /* properties_destroyed */
 291   0,                                    /* todo_flags_start */
 292   TODO_dump_func                        /* todo_flags_finish */
 293 };
 294