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   if (dump_file)
 175     dump_flow_info (dump_file, dump_flags);
 176
 177   /* Initialize structures for layout changes.  */
 178   cfg_layout_initialize (0);
 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   basic_block bb;
 208
 209   loop_optimizer_finalize ();
 210   free_dominance_info (CDI_DOMINATORS);
 211
 212   /* Finalize layout changes.  */
 213   FOR_EACH_BB (bb)
 214     if (bb->next_bb != EXIT_BLOCK_PTR)
 215       bb->aux = bb->next_bb;
 216   cfg_layout_finalize ();
 217
 218   cleanup_cfg (CLEANUP_EXPENSIVE);
 219   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 220   reg_scan (get_insns (), max_reg_num ());
 221   if (dump_file)
 222     dump_flow_info (dump_file, dump_flags);
 223
 224   return 0;
 225 }
 226
 227 struct tree_opt_pass pass_rtl_loop_done =
 228 {
 229   "loop2_done",                          /* name */
 230   NULL,                                 /* gate */
 231   rtl_loop_done,                        /* execute */
 232   NULL,                                 /* sub */
 233   NULL,                                 /* next */
 234   0,                                    /* static_pass_number */
 235   TV_LOOP,                              /* tv_id */
 236   0,                                    /* properties_required */
 237   0,                                    /* properties_provided */
 238   0,                                    /* properties_destroyed */
 239   0,                                    /* todo_flags_start */
 240   TODO_dump_func,                       /* todo_flags_finish */
 241   'L'                                   /* letter */
 242 };
 243
 244 \f
 245 /* Loop invariant code motion.  */
 246 static bool
 247 gate_rtl_move_loop_invariants (void)
 248 {
 249   return flag_move_loop_invariants;
 250 }
 251
 252 static unsigned int
 253 rtl_move_loop_invariants (void)
 254 {
 255   if (current_loops)
 256     move_loop_invariants ();
 257   return 0;
 258 }
 259
 260 struct tree_opt_pass pass_rtl_move_loop_invariants =
 261 {
 262   "loop2_invariant",                     /* name */
 263   gate_rtl_move_loop_invariants,        /* gate */
 264   rtl_move_loop_invariants,             /* execute */
 265   NULL,                                 /* sub */
 266   NULL,                                 /* next */
 267   0,                                    /* static_pass_number */
 268   TV_LOOP,                              /* tv_id */
 269   0,                                    /* properties_required */
 270   0,                                    /* properties_provided */
 271   0,                                    /* properties_destroyed */
 272   0,                                    /* todo_flags_start */
 273   TODO_dump_func,                       /* todo_flags_finish */
 274   'L'                                   /* letter */
 275 };
 276
 277 \f
 278 /* Loop unswitching for RTL.  */
 279 static bool
 280 gate_rtl_unswitch (void)
 281 {
 282   return flag_unswitch_loops;
 283 }
 284
 285 static unsigned int
 286 rtl_unswitch (void)
 287 {
 288   if (current_loops)
 289     unswitch_loops ();
 290   return 0;
 291 }
 292
 293 struct tree_opt_pass pass_rtl_unswitch =
 294 {
 295   "loop2_unswitch",                      /* name */
 296   gate_rtl_unswitch,                    /* gate */
 297   rtl_unswitch,                         /* execute */
 298   NULL,                                 /* sub */
 299   NULL,                                 /* next */
 300   0,                                    /* static_pass_number */
 301   TV_LOOP,                              /* tv_id */
 302   0,                                    /* properties_required */
 303   0,                                    /* properties_provided */
 304   0,                                    /* properties_destroyed */
 305   0,                                    /* todo_flags_start */
 306   TODO_dump_func,                       /* todo_flags_finish */
 307   'L'                                   /* letter */
 308 };
 309
 310 \f
 311 /* Loop unswitching for RTL.  */
 312 static bool
 313 gate_rtl_unroll_and_peel_loops (void)
 314 {
 315   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 316 }
 317
 318 static unsigned int
 319 rtl_unroll_and_peel_loops (void)
 320 {
 321   if (current_loops)
 322     {
 323       int flags = 0;
 324
 325       if (flag_peel_loops)
 326         flags |= UAP_PEEL;
 327       if (flag_unroll_loops)
 328         flags |= UAP_UNROLL;
 329       if (flag_unroll_all_loops)
 330         flags |= UAP_UNROLL_ALL;
 331
 332       unroll_and_peel_loops (flags);
 333     }
 334   return 0;
 335 }
 336
 337 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 338 {
 339   "loop2_unroll",                        /* name */
 340   gate_rtl_unroll_and_peel_loops,       /* gate */
 341   rtl_unroll_and_peel_loops,            /* execute */
 342   NULL,                                 /* sub */
 343   NULL,                                 /* next */
 344   0,                                    /* static_pass_number */
 345   TV_LOOP,                              /* tv_id */
 346   0,                                    /* properties_required */
 347   0,                                    /* properties_provided */
 348   0,                                    /* properties_destroyed */
 349   0,                                    /* todo_flags_start */
 350   TODO_dump_func,                       /* todo_flags_finish */
 351   'L'                                   /* letter */
 352 };
 353
 354 \f
 355 /* The doloop optimization.  */
 356 static bool
 357 gate_rtl_doloop (void)
 358 {
 359 #ifdef HAVE_doloop_end
 360   return (flag_branch_on_count_reg && HAVE_doloop_end);
 361 #else
 362   return 0;
 363 #endif
 364 }
 365
 366 static unsigned int
 367 rtl_doloop (void)
 368 {
 369 #ifdef HAVE_doloop_end
 370   if (current_loops)
 371     doloop_optimize_loops ();
 372 #endif
 373   return 0;
 374 }
 375
 376 struct tree_opt_pass pass_rtl_doloop =
 377 {
 378   "loop2_doloop",                        /* name */
 379   gate_rtl_doloop,                      /* gate */
 380   rtl_doloop,                           /* execute */
 381   NULL,                                 /* sub */
 382   NULL,                                 /* next */
 383   0,                                    /* static_pass_number */
 384   TV_LOOP,                              /* tv_id */
 385   0,                                    /* properties_required */
 386   0,                                    /* properties_provided */
 387   0,                                    /* properties_destroyed */
 388   0,                                    /* todo_flags_start */
 389   TODO_dump_func,                       /* todo_flags_finish */
 390   'L'                                   /* letter */
 391 };
 392