gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 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 under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 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 "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "obstack.h"
  28 #include "basic-block.h"
  29 #include "cfgloop.h"
  30 #include "cfglayout.h"
  31 #include "tree-pass.h"
  32 #include "timevar.h"
  33 #include "flags.h"
  34
  35 \f
  36 /* Initialize loop optimizer.  This is used by the tree and RTL loop
  37    optimizers.  */
  38
  39 struct loops *
  40 loop_optimizer_init (FILE *dumpfile)
  41 {
  42   struct loops *loops = xcalloc (1, sizeof (struct loops));
  43   edge e;
  44   edge_iterator ei;
  45   static bool first_time = true;
  46
  47   if (first_time)
  48     {
  49       first_time = false;
  50       init_set_costs ();
  51     }
  52
  53   /* Avoid annoying special cases of edges going to exit
  54      block.  */
  55
  56   for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
  57     if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
  58       split_edge (e);
  59     else
  60       ei_next (&ei);
  61
  62   /* Find the loops.  */
  63
  64   if (flow_loops_find (loops) <= 1)
  65     {
  66       /* No loops.  */
  67       flow_loops_free (loops);
  68       free (loops);
  69
  70       return NULL;
  71     }
  72
  73   /* Not going to update these.  */
  74   free (loops->cfg.rc_order);
  75   loops->cfg.rc_order = NULL;
  76   free (loops->cfg.dfs_order);
  77   loops->cfg.dfs_order = NULL;
  78
  79   /* Create pre-headers.  */
  80   create_preheaders (loops, CP_SIMPLE_PREHEADERS);
  81
  82   /* Force all latches to have only single successor.  */
  83   force_single_succ_latches (loops);
  84
  85   /* Mark irreducible loops.  */
  86   mark_irreducible_loops (loops);
  87
  88   /* Dump loops.  */
  89   flow_loops_dump (loops, dumpfile, NULL, 1);
  90
  91 #ifdef ENABLE_CHECKING
  92   verify_dominators (CDI_DOMINATORS);
  93   verify_loop_structure (loops);
  94 #endif
  95
  96   return loops;
  97 }
  98
  99 /* Finalize loop optimizer.  */
 100 void
 101 loop_optimizer_finalize (struct loops *loops, FILE *dumpfile)
 102 {
 103   unsigned i;
 104
 105   if (!loops)
 106     return;
 107
 108   for (i = 1; i < loops->num; i++)
 109     if (loops->parray[i])
 110       free_simple_loop_desc (loops->parray[i]);
 111
 112   /* Another dump.  */
 113   flow_loops_dump (loops, dumpfile, NULL, 1);
 114
 115   /* Clean up.  */
 116   flow_loops_free (loops);
 117   free (loops);
 118
 119   /* Checking.  */
 120 #ifdef ENABLE_CHECKING
 121   verify_flow_info ();
 122 #endif
 123 }
 124
 125 \f
 126 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 127    See passes.c for more on that.  */
 128
 129 static bool
 130 gate_handle_loop2 (void)
 131 {
 132   return (optimize > 0 && flag_loop_optimize2
 133           && (flag_move_loop_invariants
 134               || flag_unswitch_loops
 135               || flag_peel_loops
 136               || flag_unroll_loops
 137               || flag_branch_on_count_reg));
 138 }
 139
 140 struct tree_opt_pass pass_loop2 =
 141 {
 142   "loop2",                              /* name */
 143   gate_handle_loop2,                    /* gate */
 144   NULL,                                 /* execute */
 145   NULL,                                 /* sub */
 146   NULL,                                 /* next */
 147   0,                                    /* static_pass_number */
 148   TV_LOOP,                              /* tv_id */
 149   0,                                    /* properties_required */
 150   0,                                    /* properties_provided */
 151   0,                                    /* properties_destroyed */
 152   0,                                    /* todo_flags_start */
 153   TODO_dump_func |
 154   TODO_ggc_collect,                     /* todo_flags_finish */
 155   'L'                                   /* letter */
 156 };
 157
 158 \f
 159 /* Initialization of the RTL loop passes.  */
 160 static void
 161 rtl_loop_init (void)
 162 {
 163   if (dump_file)
 164     dump_flow_info (dump_file);
 165
 166   /* Initialize structures for layout changes.  */
 167   cfg_layout_initialize (0);
 168
 169   current_loops = loop_optimizer_init (dump_file);
 170 }
 171
 172 struct tree_opt_pass pass_rtl_loop_init =
 173 {
 174   "loop2_init",                           /* name */
 175   NULL,                                 /* gate */
 176   rtl_loop_init,                        /* execute */
 177   NULL,                                 /* sub */
 178   NULL,                                 /* next */
 179   0,                                    /* static_pass_number */
 180   TV_LOOP,                              /* tv_id */
 181   0,                                    /* properties_required */
 182   0,                                    /* properties_provided */
 183   0,                                    /* properties_destroyed */
 184   0,                                    /* todo_flags_start */
 185   TODO_dump_func,                       /* todo_flags_finish */
 186   'L'                                   /* letter */
 187 };
 188
 189 \f
 190 /* Finalization of the RTL loop passes.  */
 191 static void
 192 rtl_loop_done (void)
 193 {
 194   basic_block bb;
 195
 196   if (current_loops)
 197     loop_optimizer_finalize (current_loops, dump_file);
 198
 199   free_dominance_info (CDI_DOMINATORS);
 200
 201   /* Finalize layout changes.  */
 202   FOR_EACH_BB (bb)
 203     if (bb->next_bb != EXIT_BLOCK_PTR)
 204       bb->aux = bb->next_bb;
 205   cfg_layout_finalize ();
 206
 207   cleanup_cfg (CLEANUP_EXPENSIVE);
 208   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 209   reg_scan (get_insns (), max_reg_num ());
 210   if (dump_file)
 211     dump_flow_info (dump_file);
 212
 213   current_loops = NULL;
 214 }
 215
 216 struct tree_opt_pass pass_rtl_loop_done =
 217 {
 218   "loop2_done",                          /* name */
 219   NULL,                                 /* gate */
 220   rtl_loop_done,                        /* execute */
 221   NULL,                                 /* sub */
 222   NULL,                                 /* next */
 223   0,                                    /* static_pass_number */
 224   TV_LOOP,                              /* tv_id */
 225   0,                                    /* properties_required */
 226   0,                                    /* properties_provided */
 227   0,                                    /* properties_destroyed */
 228   0,                                    /* todo_flags_start */
 229   TODO_dump_func,                       /* todo_flags_finish */
 230   'L'                                   /* letter */
 231 };
 232
 233 \f
 234 /* Loop invariant code motion.  */
 235 static bool
 236 gate_rtl_move_loop_invariants (void)
 237 {
 238   return flag_move_loop_invariants;
 239 }
 240
 241 static void
 242 rtl_move_loop_invariants (void)
 243 {
 244   if (current_loops)
 245     move_loop_invariants (current_loops);
 246 }
 247
 248 struct tree_opt_pass pass_rtl_move_loop_invariants =
 249 {
 250   "loop2_invariant",                     /* name */
 251   gate_rtl_move_loop_invariants,        /* gate */
 252   rtl_move_loop_invariants,             /* execute */
 253   NULL,                                 /* sub */
 254   NULL,                                 /* next */
 255   0,                                    /* static_pass_number */
 256   TV_LOOP,                              /* tv_id */
 257   0,                                    /* properties_required */
 258   0,                                    /* properties_provided */
 259   0,                                    /* properties_destroyed */
 260   0,                                    /* todo_flags_start */
 261   TODO_dump_func,                       /* todo_flags_finish */
 262   'L'                                   /* letter */
 263 };
 264
 265 \f
 266 /* Loop unswitching for RTL.  */
 267 static bool
 268 gate_rtl_unswitch (void)
 269 {
 270   return flag_unswitch_loops;
 271 }
 272
 273 static void
 274 rtl_unswitch (void)
 275 {
 276   if (current_loops)
 277     unswitch_loops (current_loops);
 278 }
 279
 280 struct tree_opt_pass pass_rtl_unswitch =
 281 {
 282   "loop2_unswitch",                      /* name */
 283   gate_rtl_unswitch,                    /* gate */
 284   rtl_unswitch,                         /* execute */
 285   NULL,                                 /* sub */
 286   NULL,                                 /* next */
 287   0,                                    /* static_pass_number */
 288   TV_LOOP,                              /* tv_id */
 289   0,                                    /* properties_required */
 290   0,                                    /* properties_provided */
 291   0,                                    /* properties_destroyed */
 292   0,                                    /* todo_flags_start */
 293   TODO_dump_func,                       /* todo_flags_finish */
 294   'L'                                   /* letter */
 295 };
 296
 297 \f
 298 /* Loop unswitching for RTL.  */
 299 static bool
 300 gate_rtl_unroll_and_peel_loops (void)
 301 {
 302   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 303 }
 304
 305 static void
 306 rtl_unroll_and_peel_loops (void)
 307 {
 308   if (current_loops)
 309     {
 310       int flags = 0;
 311
 312       if (flag_peel_loops)
 313         flags |= UAP_PEEL;
 314       if (flag_unroll_loops)
 315         flags |= UAP_UNROLL;
 316       if (flag_unroll_all_loops)
 317         flags |= UAP_UNROLL_ALL;
 318
 319       unroll_and_peel_loops (current_loops, flags);
 320     }
 321 }
 322
 323 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 324 {
 325   "loop2_unroll",                        /* name */
 326   gate_rtl_unroll_and_peel_loops,       /* gate */
 327   rtl_unroll_and_peel_loops,            /* execute */
 328   NULL,                                 /* sub */
 329   NULL,                                 /* next */
 330   0,                                    /* static_pass_number */
 331   TV_LOOP,                              /* tv_id */
 332   0,                                    /* properties_required */
 333   0,                                    /* properties_provided */
 334   0,                                    /* properties_destroyed */
 335   0,                                    /* todo_flags_start */
 336   TODO_dump_func,                       /* todo_flags_finish */
 337   'L'                                   /* letter */
 338 };
 339
 340 \f
 341 /* The doloop optimization.  */
 342 static bool
 343 gate_rtl_doloop (void)
 344 {
 345 #ifdef HAVE_doloop_end
 346   return (flag_branch_on_count_reg && HAVE_doloop_end);
 347 #else
 348   return 0;
 349 #endif
 350 }
 351
 352 static void
 353 rtl_doloop (void)
 354 {
 355 #ifdef HAVE_doloop_end
 356   if (current_loops)
 357     doloop_optimize_loops (current_loops);
 358 #endif
 359 }
 360
 361 struct tree_opt_pass pass_rtl_doloop =
 362 {
 363   "loop2_doloop",                        /* name */
 364   gate_rtl_doloop,                      /* gate */
 365   rtl_doloop,                           /* execute */
 366   NULL,                                 /* sub */
 367   NULL,                                 /* next */
 368   0,                                    /* static_pass_number */
 369   TV_LOOP,                              /* tv_id */
 370   0,                                    /* properties_required */
 371   0,                                    /* properties_provided */
 372   0,                                    /* properties_destroyed */
 373   0,                                    /* todo_flags_start */
 374   TODO_dump_func,                       /* todo_flags_finish */
 375   'L'                                   /* letter */
 376 };
 377