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