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