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