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 #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 (CLEANUP_EXPENSIVE);
 202   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 203   reg_scan (get_insns (), max_reg_num ());
 204   if (dump_file)
 205     dump_flow_info (dump_file, dump_flags);
 206
 207   return 0;
 208 }
 209
 210 struct tree_opt_pass pass_rtl_loop_done =
 211 {
 212   "loop2_done",                          /* name */
 213   NULL,                                 /* gate */
 214   rtl_loop_done,                        /* execute */
 215   NULL,                                 /* sub */
 216   NULL,                                 /* next */
 217   0,                                    /* static_pass_number */
 218   TV_LOOP,                              /* tv_id */
 219   0,                                    /* properties_required */
 220   0,                                    /* properties_provided */
 221   0,                                    /* properties_destroyed */
 222   0,                                    /* todo_flags_start */
 223   TODO_dump_func,                       /* todo_flags_finish */
 224   'L'                                   /* letter */
 225 };
 226
 227 \f
 228 /* Loop invariant code motion.  */
 229 static bool
 230 gate_rtl_move_loop_invariants (void)
 231 {
 232   return flag_move_loop_invariants;
 233 }
 234
 235 static unsigned int
 236 rtl_move_loop_invariants (void)
 237 {
 238   if (number_of_loops () > 1)
 239     move_loop_invariants ();
 240   return 0;
 241 }
 242
 243 struct tree_opt_pass pass_rtl_move_loop_invariants =
 244 {
 245   "loop2_invariant",                     /* name */
 246   gate_rtl_move_loop_invariants,        /* gate */
 247   rtl_move_loop_invariants,             /* execute */
 248   NULL,                                 /* sub */
 249   NULL,                                 /* next */
 250   0,                                    /* static_pass_number */
 251   TV_LOOP,                              /* tv_id */
 252   0,                                    /* properties_required */
 253   0,                                    /* properties_provided */
 254   0,                                    /* properties_destroyed */
 255   0,                                    /* todo_flags_start */
 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_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
 308       if (flag_peel_loops)
 309         flags |= UAP_PEEL;
 310       if (flag_unroll_loops)
 311         flags |= UAP_UNROLL;
 312       if (flag_unroll_all_loops)
 313         flags |= UAP_UNROLL_ALL;
 314
 315       unroll_and_peel_loops (flags);
 316     }
 317   return 0;
 318 }
 319
 320 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 321 {
 322   "loop2_unroll",                        /* name */
 323   gate_rtl_unroll_and_peel_loops,       /* gate */
 324   rtl_unroll_and_peel_loops,            /* execute */
 325   NULL,                                 /* sub */
 326   NULL,                                 /* next */
 327   0,                                    /* static_pass_number */
 328   TV_LOOP,                              /* tv_id */
 329   0,                                    /* properties_required */
 330   0,                                    /* properties_provided */
 331   0,                                    /* properties_destroyed */
 332   0,                                    /* todo_flags_start */
 333   TODO_dump_func,                       /* todo_flags_finish */
 334   'L'                                   /* letter */
 335 };
 336
 337 \f
 338 /* The doloop optimization.  */
 339 static bool
 340 gate_rtl_doloop (void)
 341 {
 342 #ifdef HAVE_doloop_end
 343   return (flag_branch_on_count_reg && HAVE_doloop_end);
 344 #else
 345   return 0;
 346 #endif
 347 }
 348
 349 static unsigned int
 350 rtl_doloop (void)
 351 {
 352 #ifdef HAVE_doloop_end
 353   if (number_of_loops () > 1)
 354     doloop_optimize_loops ();
 355 #endif
 356   return 0;
 357 }
 358
 359 struct tree_opt_pass pass_rtl_doloop =
 360 {
 361   "loop2_doloop",                        /* name */
 362   gate_rtl_doloop,                      /* gate */
 363   rtl_doloop,                           /* execute */
 364   NULL,                                 /* sub */
 365   NULL,                                 /* next */
 366   0,                                    /* static_pass_number */
 367   TV_LOOP,                              /* tv_id */
 368   0,                                    /* properties_required */
 369   0,                                    /* properties_provided */
 370   0,                                    /* properties_destroyed */
 371   0,                                    /* todo_flags_start */
 372   TODO_dump_func,                       /* todo_flags_finish */
 373   'L'                                   /* letter */
 374 };
 375