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       current_loops->state = 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 (current_loops->state & 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_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_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_finish |                      /* This is shutting down the instance in loop_invariant.c  */
 255   TODO_dump_func,                       /* todo_flags_finish */
 256   'L'                                   /* letter */
 257 };
 258
 259 \f
 260 /* Loop unswitching for RTL.  */
 261 static bool
 262 gate_rtl_unswitch (void)
 263 {
 264   return flag_unswitch_loops;
 265 }
 266
 267 static unsigned int
 268 rtl_unswitch (void)
 269 {
 270   if (number_of_loops () > 1)
 271     unswitch_loops ();
 272   return 0;
 273 }
 274
 275 struct tree_opt_pass pass_rtl_unswitch =
 276 {
 277   "loop2_unswitch",                      /* name */
 278   gate_rtl_unswitch,                    /* gate */
 279   rtl_unswitch,                         /* execute */
 280   NULL,                                 /* sub */
 281   NULL,                                 /* next */
 282   0,                                    /* static_pass_number */
 283   TV_LOOP,                              /* tv_id */
 284   0,                                    /* properties_required */
 285   0,                                    /* properties_provided */
 286   0,                                    /* properties_destroyed */
 287   0,                                    /* todo_flags_start */
 288   TODO_dump_func,                       /* todo_flags_finish */
 289   'L'                                   /* letter */
 290 };
 291
 292 \f
 293 /* Loop unswitching for RTL.  */
 294 static bool
 295 gate_rtl_unroll_and_peel_loops (void)
 296 {
 297   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 298 }
 299
 300 static unsigned int
 301 rtl_unroll_and_peel_loops (void)
 302 {
 303   if (number_of_loops () > 1)
 304     {
 305       int flags = 0;
 306       if (dump_file)
 307         df_dump (dump_file);
 308
 309       if (flag_peel_loops)
 310         flags |= UAP_PEEL;
 311       if (flag_unroll_loops)
 312         flags |= UAP_UNROLL;
 313       if (flag_unroll_all_loops)
 314         flags |= UAP_UNROLL_ALL;
 315
 316       unroll_and_peel_loops (flags);
 317     }
 318   return 0;
 319 }
 320
 321 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 322 {
 323   "loop2_unroll",                        /* name */
 324   gate_rtl_unroll_and_peel_loops,       /* gate */
 325   rtl_unroll_and_peel_loops,            /* execute */
 326   NULL,                                 /* sub */
 327   NULL,                                 /* next */
 328   0,                                    /* static_pass_number */
 329   TV_LOOP,                              /* tv_id */
 330   0,                                    /* properties_required */
 331   0,                                    /* properties_provided */
 332   0,                                    /* properties_destroyed */
 333   0,                                    /* todo_flags_start */
 334   TODO_dump_func,                       /* todo_flags_finish */
 335   'L'                                   /* letter */
 336 };
 337
 338 \f
 339 /* The doloop optimization.  */
 340 static bool
 341 gate_rtl_doloop (void)
 342 {
 343 #ifdef HAVE_doloop_end
 344   return (flag_branch_on_count_reg && HAVE_doloop_end);
 345 #else
 346   return 0;
 347 #endif
 348 }
 349
 350 static unsigned int
 351 rtl_doloop (void)
 352 {
 353 #ifdef HAVE_doloop_end
 354   if (number_of_loops () > 1)
 355     doloop_optimize_loops ();
 356 #endif
 357   return 0;
 358 }
 359
 360 struct tree_opt_pass pass_rtl_doloop =
 361 {
 362   "loop2_doloop",                        /* name */
 363   gate_rtl_doloop,                      /* gate */
 364   rtl_doloop,                           /* execute */
 365   NULL,                                 /* sub */
 366   NULL,                                 /* next */
 367   0,                                    /* static_pass_number */
 368   TV_LOOP,                              /* tv_id */
 369   0,                                    /* properties_required */
 370   0,                                    /* properties_provided */
 371   0,                                    /* properties_destroyed */
 372   0,                                    /* todo_flags_start */
 373   TODO_dump_func,                       /* todo_flags_finish */
 374   'L'                                   /* letter */
 375 };
 376