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