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   struct loops *loops;
  44
  45   gcc_assert (!current_loops);
  46   loops = XCNEW (struct loops);
  47
  48   /* Find the loops.  */
  49
  50   flow_loops_find (loops);
  51   current_loops = loops;
  52
  53   if (number_of_loops () <= 1)
  54     {
  55       /* No loops (the 1 returned by number_of_loops corresponds to the fake
  56          loop that we put as a root of the loop tree).  */
  57       loop_optimizer_finalize ();
  58       return;
  59     }
  60
  61   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  62     {
  63       /* If the loops may have multiple latches, we cannot canonicalize
  64          them further (and most of the loop manipulation functions will
  65          not work).  However, we avoid modifying cfg, which some
  66          passes may want.  */
  67       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  68                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  69       current_loops->state = LOOPS_MAY_HAVE_MULTIPLE_LATCHES;
  70     }
  71   else
  72     disambiguate_loops_with_multiple_latches ();
  73
  74   /* Create pre-headers.  */
  75   if (flags & LOOPS_HAVE_PREHEADERS)
  76     create_preheaders (CP_SIMPLE_PREHEADERS);
  77
  78   /* Force all latches to have only single successor.  */
  79   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  80     force_single_succ_latches ();
  81
  82   /* Mark irreducible loops.  */
  83   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  84     mark_irreducible_loops ();
  85
  86   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  87     record_loop_exits ();
  88
  89   /* Dump loops.  */
  90   flow_loops_dump (dump_file, NULL, 1);
  91
  92 #ifdef ENABLE_CHECKING
  93   verify_dominators (CDI_DOMINATORS);
  94   verify_loop_structure ();
  95 #endif
  96 }
  97
  98 /* Finalize loop structures.  */
  99
 100 void
 101 loop_optimizer_finalize (void)
 102 {
 103   loop_iterator li;
 104   struct loop *loop;
 105   basic_block bb;
 106
 107   if (!current_loops)
 108     return;
 109
 110   FOR_EACH_LOOP (li, loop, 0)
 111     {
 112       free_simple_loop_desc (loop);
 113     }
 114
 115   /* Clean up.  */
 116   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
 117     release_recorded_exits ();
 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   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 175
 176   if (dump_file)
 177     dump_flow_info (dump_file, dump_flags);
 178
 179   loop_optimizer_init (LOOPS_NORMAL);
 180   return 0;
 181 }
 182
 183 struct tree_opt_pass pass_rtl_loop_init =
 184 {
 185   "loop2_init",                           /* name */
 186   NULL,                                 /* gate */
 187   rtl_loop_init,                        /* execute */
 188   NULL,                                 /* sub */
 189   NULL,                                 /* next */
 190   0,                                    /* static_pass_number */
 191   TV_LOOP,                              /* tv_id */
 192   0,                                    /* properties_required */
 193   0,                                    /* properties_provided */
 194   0,                                    /* properties_destroyed */
 195   0,                                    /* todo_flags_start */
 196   TODO_dump_func,                       /* todo_flags_finish */
 197   'L'                                   /* letter */
 198 };
 199
 200 \f
 201 /* Finalization of the RTL loop passes.  */
 202
 203 static unsigned int
 204 rtl_loop_done (void)
 205 {
 206   loop_optimizer_finalize ();
 207   free_dominance_info (CDI_DOMINATORS);
 208
 209   cleanup_cfg (CLEANUP_EXPENSIVE);
 210   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 211   reg_scan (get_insns (), max_reg_num ());
 212   if (dump_file)
 213     dump_flow_info (dump_file, dump_flags);
 214
 215   return 0;
 216 }
 217
 218 struct tree_opt_pass pass_rtl_loop_done =
 219 {
 220   "loop2_done",                          /* name */
 221   NULL,                                 /* gate */
 222   rtl_loop_done,                        /* execute */
 223   NULL,                                 /* sub */
 224   NULL,                                 /* next */
 225   0,                                    /* static_pass_number */
 226   TV_LOOP,                              /* tv_id */
 227   0,                                    /* properties_required */
 228   0,                                    /* properties_provided */
 229   0,                                    /* properties_destroyed */
 230   0,                                    /* todo_flags_start */
 231   TODO_dump_func,                       /* todo_flags_finish */
 232   'L'                                   /* letter */
 233 };
 234
 235 \f
 236 /* Loop invariant code motion.  */
 237 static bool
 238 gate_rtl_move_loop_invariants (void)
 239 {
 240   return flag_move_loop_invariants;
 241 }
 242
 243 static unsigned int
 244 rtl_move_loop_invariants (void)
 245 {
 246   if (current_loops)
 247     move_loop_invariants ();
 248   return 0;
 249 }
 250
 251 struct tree_opt_pass pass_rtl_move_loop_invariants =
 252 {
 253   "loop2_invariant",                     /* name */
 254   gate_rtl_move_loop_invariants,        /* gate */
 255   rtl_move_loop_invariants,             /* execute */
 256   NULL,                                 /* sub */
 257   NULL,                                 /* next */
 258   0,                                    /* static_pass_number */
 259   TV_LOOP,                              /* tv_id */
 260   0,                                    /* properties_required */
 261   0,                                    /* properties_provided */
 262   0,                                    /* properties_destroyed */
 263   0,                                    /* todo_flags_start */
 264   TODO_dump_func,                       /* todo_flags_finish */
 265   'L'                                   /* letter */
 266 };
 267
 268 \f
 269 /* Loop unswitching for RTL.  */
 270 static bool
 271 gate_rtl_unswitch (void)
 272 {
 273   return flag_unswitch_loops;
 274 }
 275
 276 static unsigned int
 277 rtl_unswitch (void)
 278 {
 279   if (current_loops)
 280     unswitch_loops ();
 281   return 0;
 282 }
 283
 284 struct tree_opt_pass pass_rtl_unswitch =
 285 {
 286   "loop2_unswitch",                      /* name */
 287   gate_rtl_unswitch,                    /* gate */
 288   rtl_unswitch,                         /* execute */
 289   NULL,                                 /* sub */
 290   NULL,                                 /* next */
 291   0,                                    /* static_pass_number */
 292   TV_LOOP,                              /* tv_id */
 293   0,                                    /* properties_required */
 294   0,                                    /* properties_provided */
 295   0,                                    /* properties_destroyed */
 296   0,                                    /* todo_flags_start */
 297   TODO_dump_func,                       /* todo_flags_finish */
 298   'L'                                   /* letter */
 299 };
 300
 301 \f
 302 /* Loop unswitching for RTL.  */
 303 static bool
 304 gate_rtl_unroll_and_peel_loops (void)
 305 {
 306   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 307 }
 308
 309 static unsigned int
 310 rtl_unroll_and_peel_loops (void)
 311 {
 312   if (current_loops)
 313     {
 314       int flags = 0;
 315
 316       if (flag_peel_loops)
 317         flags |= UAP_PEEL;
 318       if (flag_unroll_loops)
 319         flags |= UAP_UNROLL;
 320       if (flag_unroll_all_loops)
 321         flags |= UAP_UNROLL_ALL;
 322
 323       unroll_and_peel_loops (flags);
 324     }
 325   return 0;
 326 }
 327
 328 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 329 {
 330   "loop2_unroll",                        /* name */
 331   gate_rtl_unroll_and_peel_loops,       /* gate */
 332   rtl_unroll_and_peel_loops,            /* execute */
 333   NULL,                                 /* sub */
 334   NULL,                                 /* next */
 335   0,                                    /* static_pass_number */
 336   TV_LOOP,                              /* tv_id */
 337   0,                                    /* properties_required */
 338   0,                                    /* properties_provided */
 339   0,                                    /* properties_destroyed */
 340   0,                                    /* todo_flags_start */
 341   TODO_dump_func,                       /* todo_flags_finish */
 342   'L'                                   /* letter */
 343 };
 344
 345 \f
 346 /* The doloop optimization.  */
 347 static bool
 348 gate_rtl_doloop (void)
 349 {
 350 #ifdef HAVE_doloop_end
 351   return (flag_branch_on_count_reg && HAVE_doloop_end);
 352 #else
 353   return 0;
 354 #endif
 355 }
 356
 357 static unsigned int
 358 rtl_doloop (void)
 359 {
 360 #ifdef HAVE_doloop_end
 361   if (current_loops)
 362     doloop_optimize_loops ();
 363 #endif
 364   return 0;
 365 }
 366
 367 struct tree_opt_pass pass_rtl_doloop =
 368 {
 369   "loop2_doloop",                        /* name */
 370   gate_rtl_doloop,                      /* gate */
 371   rtl_doloop,                           /* execute */
 372   NULL,                                 /* sub */
 373   NULL,                                 /* next */
 374   0,                                    /* static_pass_number */
 375   TV_LOOP,                              /* tv_id */
 376   0,                                    /* properties_required */
 377   0,                                    /* properties_provided */
 378   0,                                    /* properties_destroyed */
 379   0,                                    /* todo_flags_start */
 380   TODO_dump_func,                       /* todo_flags_finish */
 381   'L'                                   /* letter */
 382 };
 383