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