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