gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "rtl.h"
  25 #include "hard-reg-set.h"
  26 #include "obstack.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "tree-pass.h"
  31 #include "timevar.h"
  32 #include "flags.h"
  33 #include "df.h"
  34 #include "ggc.h"
  35
  36 \f
  37 /* Initialize loop structures.  This is used by the tree and RTL loop
  38    optimizers.  FLAGS specify what properties to compute and/or ensure for
  39    loops.  */
  40
  41 void
  42 loop_optimizer_init (unsigned flags)
  43 {
  44   struct loops *loops;
  45
  46   gcc_assert (!current_loops);
  47   loops = GGC_CNEW (struct loops);
  48
  49   /* Find the loops.  */
  50
  51   flow_loops_find (loops);
  52   current_loops = loops;
  53
  54   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  55     {
  56       /* If the loops may have multiple latches, we cannot canonicalize
  57          them further (and most of the loop manipulation functions will
  58          not work).  However, we avoid modifying cfg, which some
  59          passes may want.  */
  60       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  61                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  62       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  63     }
  64   else
  65     disambiguate_loops_with_multiple_latches ();
  66
  67   /* Create pre-headers.  */
  68   if (flags & LOOPS_HAVE_PREHEADERS)
  69     create_preheaders (CP_SIMPLE_PREHEADERS);
  70
  71   /* Force all latches to have only single successor.  */
  72   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  73     force_single_succ_latches ();
  74
  75   /* Mark irreducible loops.  */
  76   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  77     mark_irreducible_loops ();
  78
  79   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  80     record_loop_exits ();
  81
  82   /* Dump loops.  */
  83   flow_loops_dump (dump_file, NULL, 1);
  84
  85 #ifdef ENABLE_CHECKING
  86   verify_dominators (CDI_DOMINATORS);
  87   verify_loop_structure ();
  88 #endif
  89 }
  90
  91 /* Finalize loop structures.  */
  92
  93 void
  94 loop_optimizer_finalize (void)
  95 {
  96   loop_iterator li;
  97   struct loop *loop;
  98   basic_block bb;
  99
 100   gcc_assert (current_loops != NULL);
 101
 102   FOR_EACH_LOOP (li, loop, 0)
 103     {
 104       free_simple_loop_desc (loop);
 105     }
 106
 107   /* Clean up.  */
 108   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 109     release_recorded_exits ();
 110   flow_loops_free (current_loops);
 111   ggc_free (current_loops);
 112   current_loops = NULL;
 113
 114   FOR_ALL_BB (bb)
 115     {
 116       bb->loop_father = NULL;
 117     }
 118
 119   /* Checking.  */
 120 #ifdef ENABLE_CHECKING
 121   verify_flow_info ();
 122 #endif
 123 }
 124
 125 \f
 126 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 127    See passes.c for more on that.  */
 128
 129 static bool
 130 gate_handle_loop2 (void)
 131 {
 132   return (optimize > 0
 133           && (flag_move_loop_invariants
 134               || flag_unswitch_loops
 135               || flag_peel_loops
 136               || flag_unroll_loops
 137 #ifdef HAVE_doloop_end
 138               || (flag_branch_on_count_reg && HAVE_doloop_end)
 139 #endif
 140               ));
 141 }
 142
 143 struct tree_opt_pass pass_loop2 =
 144 {
 145   "loop2",                              /* name */
 146   gate_handle_loop2,                    /* gate */
 147   NULL,                                 /* execute */
 148   NULL,                                 /* sub */
 149   NULL,                                 /* next */
 150   0,                                    /* static_pass_number */
 151   TV_LOOP,                              /* tv_id */
 152   0,                                    /* properties_required */
 153   0,                                    /* properties_provided */
 154   0,                                    /* properties_destroyed */
 155   0,                                    /* todo_flags_start */
 156   TODO_dump_func |
 157   TODO_ggc_collect,                     /* todo_flags_finish */
 158   'L'                                   /* letter */
 159 };
 160
 161 \f
 162 /* Initialization of the RTL loop passes.  */
 163 static unsigned int
 164 rtl_loop_init (void)
 165 {
 166   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 167
 168   if (dump_file)
 169     dump_flow_info (dump_file, dump_flags);
 170
 171   loop_optimizer_init (LOOPS_NORMAL);
 172   return 0;
 173 }
 174
 175 struct tree_opt_pass pass_rtl_loop_init =
 176 {
 177   "loop2_init",                           /* name */
 178   NULL,                                 /* gate */
 179   rtl_loop_init,                        /* execute */
 180   NULL,                                 /* sub */
 181   NULL,                                 /* next */
 182   0,                                    /* static_pass_number */
 183   TV_LOOP,                              /* tv_id */
 184   0,                                    /* properties_required */
 185   0,                                    /* properties_provided */
 186   0,                                    /* properties_destroyed */
 187   0,                                    /* todo_flags_start */
 188   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 189   'L'                                   /* letter */
 190 };
 191
 192 \f
 193 /* Finalization of the RTL loop passes.  */
 194
 195 static unsigned int
 196 rtl_loop_done (void)
 197 {
 198   loop_optimizer_finalize ();
 199   free_dominance_info (CDI_DOMINATORS);
 200
 201   cleanup_cfg (0);
 202   if (dump_file)
 203     dump_flow_info (dump_file, dump_flags);
 204
 205   return 0;
 206 }
 207
 208 struct tree_opt_pass pass_rtl_loop_done =
 209 {
 210   "loop2_done",                          /* name */
 211   NULL,                                 /* gate */
 212   rtl_loop_done,                        /* execute */
 213   NULL,                                 /* sub */
 214   NULL,                                 /* next */
 215   0,                                    /* static_pass_number */
 216   TV_LOOP,                              /* tv_id */
 217   0,                                    /* properties_required */
 218   0,                                    /* properties_provided */
 219   0,                                    /* properties_destroyed */
 220   0,                                    /* todo_flags_start */
 221   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 222   'L'                                   /* letter */
 223 };
 224
 225 \f
 226 /* Loop invariant code motion.  */
 227 static bool
 228 gate_rtl_move_loop_invariants (void)
 229 {
 230   return flag_move_loop_invariants;
 231 }
 232
 233 static unsigned int
 234 rtl_move_loop_invariants (void)
 235 {
 236   if (number_of_loops () > 1)
 237     move_loop_invariants ();
 238   return 0;
 239 }
 240
 241 struct tree_opt_pass pass_rtl_move_loop_invariants =
 242 {
 243   "loop2_invariant",                    /* name */
 244   gate_rtl_move_loop_invariants,        /* gate */
 245   rtl_move_loop_invariants,             /* execute */
 246   NULL,                                 /* sub */
 247   NULL,                                 /* next */
 248   0,                                    /* static_pass_number */
 249   TV_LOOP,                              /* tv_id */
 250   0,                                    /* properties_required */
 251   0,                                    /* properties_provided */
 252   0,                                    /* properties_destroyed */
 253   0,                                    /* todo_flags_start */
 254   TODO_df_verify |
 255   TODO_df_finish | TODO_verify_rtl_sharing |
 256   TODO_dump_func,                       /* todo_flags_finish */
 257   'L'                                   /* letter */
 258 };
 259
 260 \f
 261 /* Loop unswitching for RTL.  */
 262 static bool
 263 gate_rtl_unswitch (void)
 264 {
 265   return flag_unswitch_loops;
 266 }
 267
 268 static unsigned int
 269 rtl_unswitch (void)
 270 {
 271   if (number_of_loops () > 1)
 272     unswitch_loops ();
 273   return 0;
 274 }
 275
 276 struct tree_opt_pass pass_rtl_unswitch =
 277 {
 278   "loop2_unswitch",                      /* name */
 279   gate_rtl_unswitch,                    /* gate */
 280   rtl_unswitch,                         /* execute */
 281   NULL,                                 /* sub */
 282   NULL,                                 /* next */
 283   0,                                    /* static_pass_number */
 284   TV_LOOP,                              /* tv_id */
 285   0,                                    /* properties_required */
 286   0,                                    /* properties_provided */
 287   0,                                    /* properties_destroyed */
 288   0,                                    /* todo_flags_start */
 289   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 290   'L'                                   /* letter */
 291 };
 292
 293 \f
 294 /* Loop unswitching for RTL.  */
 295 static bool
 296 gate_rtl_unroll_and_peel_loops (void)
 297 {
 298   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 299 }
 300
 301 static unsigned int
 302 rtl_unroll_and_peel_loops (void)
 303 {
 304   if (number_of_loops () > 1)
 305     {
 306       int flags = 0;
 307       if (dump_file)
 308         df_dump (dump_file);
 309
 310       if (flag_peel_loops)
 311         flags |= UAP_PEEL;
 312       if (flag_unroll_loops)
 313         flags |= UAP_UNROLL;
 314       if (flag_unroll_all_loops)
 315         flags |= UAP_UNROLL_ALL;
 316
 317       unroll_and_peel_loops (flags);
 318     }
 319   return 0;
 320 }
 321
 322 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 323 {
 324   "loop2_unroll",                        /* name */
 325   gate_rtl_unroll_and_peel_loops,       /* gate */
 326   rtl_unroll_and_peel_loops,            /* execute */
 327   NULL,                                 /* sub */
 328   NULL,                                 /* next */
 329   0,                                    /* static_pass_number */
 330   TV_LOOP,                              /* tv_id */
 331   0,                                    /* properties_required */
 332   0,                                    /* properties_provided */
 333   0,                                    /* properties_destroyed */
 334   0,                                    /* todo_flags_start */
 335   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 336   'L'                                   /* letter */
 337 };
 338
 339 \f
 340 /* The doloop optimization.  */
 341 static bool
 342 gate_rtl_doloop (void)
 343 {
 344 #ifdef HAVE_doloop_end
 345   return (flag_branch_on_count_reg && HAVE_doloop_end);
 346 #else
 347   return 0;
 348 #endif
 349 }
 350
 351 static unsigned int
 352 rtl_doloop (void)
 353 {
 354 #ifdef HAVE_doloop_end
 355   if (number_of_loops () > 1)
 356     doloop_optimize_loops ();
 357 #endif
 358   return 0;
 359 }
 360
 361 struct tree_opt_pass pass_rtl_doloop =
 362 {
 363   "loop2_doloop",                        /* name */
 364   gate_rtl_doloop,                      /* gate */
 365   rtl_doloop,                           /* execute */
 366   NULL,                                 /* sub */
 367   NULL,                                 /* next */
 368   0,                                    /* static_pass_number */
 369   TV_LOOP,                              /* tv_id */
 370   0,                                    /* properties_required */
 371   0,                                    /* properties_provided */
 372   0,                                    /* properties_destroyed */
 373   0,                                    /* todo_flags_start */
 374   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 375   'L'                                   /* letter */
 376 };
 377