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 rtl_opt_pass pass_loop2 =
 144 {
 145  {
 146   RTL_PASS,
 147   "loop2",                              /* name */
 148   gate_handle_loop2,                    /* gate */
 149   NULL,                                 /* execute */
 150   NULL,                                 /* sub */
 151   NULL,                                 /* next */
 152   0,                                    /* static_pass_number */
 153   TV_LOOP,                              /* tv_id */
 154   0,                                    /* properties_required */
 155   0,                                    /* properties_provided */
 156   0,                                    /* properties_destroyed */
 157   0,                                    /* todo_flags_start */
 158   TODO_dump_func |
 159   TODO_ggc_collect                      /* todo_flags_finish */
 160  }
 161 };
 162
 163 \f
 164 /* Initialization of the RTL loop passes.  */
 165 static unsigned int
 166 rtl_loop_init (void)
 167 {
 168   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 169
 170   if (dump_file)
 171     dump_flow_info (dump_file, dump_flags);
 172
 173   loop_optimizer_init (LOOPS_NORMAL);
 174   return 0;
 175 }
 176
 177 struct rtl_opt_pass pass_rtl_loop_init =
 178 {
 179  {
 180   RTL_PASS,
 181   "loop2_init",                           /* name */
 182   NULL,                                 /* gate */
 183   rtl_loop_init,                        /* execute */
 184   NULL,                                 /* sub */
 185   NULL,                                 /* next */
 186   0,                                    /* static_pass_number */
 187   TV_LOOP,                              /* tv_id */
 188   0,                                    /* properties_required */
 189   0,                                    /* properties_provided */
 190   0,                                    /* properties_destroyed */
 191   0,                                    /* todo_flags_start */
 192   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 193  }
 194 };
 195
 196 \f
 197 /* Finalization of the RTL loop passes.  */
 198
 199 static unsigned int
 200 rtl_loop_done (void)
 201 {
 202   loop_optimizer_finalize ();
 203   free_dominance_info (CDI_DOMINATORS);
 204
 205   cleanup_cfg (0);
 206   if (dump_file)
 207     dump_flow_info (dump_file, dump_flags);
 208
 209   return 0;
 210 }
 211
 212 struct rtl_opt_pass pass_rtl_loop_done =
 213 {
 214  {
 215   RTL_PASS,
 216   "loop2_done",                          /* name */
 217   NULL,                                 /* gate */
 218   rtl_loop_done,                        /* execute */
 219   NULL,                                 /* sub */
 220   NULL,                                 /* next */
 221   0,                                    /* static_pass_number */
 222   TV_LOOP,                              /* tv_id */
 223   0,                                    /* properties_required */
 224   0,                                    /* properties_provided */
 225   0,                                    /* properties_destroyed */
 226   0,                                    /* todo_flags_start */
 227   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 228  }
 229 };
 230
 231 \f
 232 /* Loop invariant code motion.  */
 233 static bool
 234 gate_rtl_move_loop_invariants (void)
 235 {
 236   return flag_move_loop_invariants;
 237 }
 238
 239 static unsigned int
 240 rtl_move_loop_invariants (void)
 241 {
 242   if (number_of_loops () > 1)
 243     move_loop_invariants ();
 244   return 0;
 245 }
 246
 247 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 248 {
 249  {
 250   RTL_PASS,
 251   "loop2_invariant",                    /* name */
 252   gate_rtl_move_loop_invariants,        /* gate */
 253   rtl_move_loop_invariants,             /* execute */
 254   NULL,                                 /* sub */
 255   NULL,                                 /* next */
 256   0,                                    /* static_pass_number */
 257   TV_LOOP,                              /* tv_id */
 258   0,                                    /* properties_required */
 259   0,                                    /* properties_provided */
 260   0,                                    /* properties_destroyed */
 261   0,                                    /* todo_flags_start */
 262   TODO_df_verify |
 263   TODO_df_finish | TODO_verify_rtl_sharing |
 264   TODO_dump_func                        /* todo_flags_finish */
 265  }
 266 };
 267
 268 \f
 269 /* Loop unswitching for RTL.  */
 270 static bool
 271 gate_rtl_unswitch (void)
 272 {
 273   return flag_unswitch_loops;
 274 }
 275
 276 static unsigned int
 277 rtl_unswitch (void)
 278 {
 279   if (number_of_loops () > 1)
 280     unswitch_loops ();
 281   return 0;
 282 }
 283
 284 struct rtl_opt_pass pass_rtl_unswitch =
 285 {
 286  {
 287   RTL_PASS,
 288   "loop2_unswitch",                      /* name */
 289   gate_rtl_unswitch,                    /* gate */
 290   rtl_unswitch,                         /* execute */
 291   NULL,                                 /* sub */
 292   NULL,                                 /* next */
 293   0,                                    /* static_pass_number */
 294   TV_LOOP,                              /* tv_id */
 295   0,                                    /* properties_required */
 296   0,                                    /* properties_provided */
 297   0,                                    /* properties_destroyed */
 298   0,                                    /* todo_flags_start */
 299   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 300  }
 301 };
 302
 303 \f
 304 /* Loop unswitching for RTL.  */
 305 static bool
 306 gate_rtl_unroll_and_peel_loops (void)
 307 {
 308   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 309 }
 310
 311 static unsigned int
 312 rtl_unroll_and_peel_loops (void)
 313 {
 314   if (number_of_loops () > 1)
 315     {
 316       int flags = 0;
 317       if (dump_file)
 318         df_dump (dump_file);
 319
 320       if (flag_peel_loops)
 321         flags |= UAP_PEEL;
 322       if (flag_unroll_loops)
 323         flags |= UAP_UNROLL;
 324       if (flag_unroll_all_loops)
 325         flags |= UAP_UNROLL_ALL;
 326
 327       unroll_and_peel_loops (flags);
 328     }
 329   return 0;
 330 }
 331
 332 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 333 {
 334  {
 335   RTL_PASS,
 336   "loop2_unroll",                        /* name */
 337   gate_rtl_unroll_and_peel_loops,       /* gate */
 338   rtl_unroll_and_peel_loops,            /* execute */
 339   NULL,                                 /* sub */
 340   NULL,                                 /* next */
 341   0,                                    /* static_pass_number */
 342   TV_LOOP,                              /* tv_id */
 343   0,                                    /* properties_required */
 344   0,                                    /* properties_provided */
 345   0,                                    /* properties_destroyed */
 346   0,                                    /* todo_flags_start */
 347   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 348  }
 349 };
 350
 351 \f
 352 /* The doloop optimization.  */
 353 static bool
 354 gate_rtl_doloop (void)
 355 {
 356 #ifdef HAVE_doloop_end
 357   return (flag_branch_on_count_reg && HAVE_doloop_end);
 358 #else
 359   return 0;
 360 #endif
 361 }
 362
 363 static unsigned int
 364 rtl_doloop (void)
 365 {
 366 #ifdef HAVE_doloop_end
 367   if (number_of_loops () > 1)
 368     doloop_optimize_loops ();
 369 #endif
 370   return 0;
 371 }
 372
 373 struct rtl_opt_pass pass_rtl_doloop =
 374 {
 375  {
 376   RTL_PASS,
 377   "loop2_doloop",                        /* name */
 378   gate_rtl_doloop,                      /* gate */
 379   rtl_doloop,                           /* execute */
 380   NULL,                                 /* sub */
 381   NULL,                                 /* next */
 382   0,                                    /* static_pass_number */
 383   TV_LOOP,                              /* tv_id */
 384   0,                                    /* properties_required */
 385   0,                                    /* properties_provided */
 386   0,                                    /* properties_destroyed */
 387   0,                                    /* todo_flags_start */
 388   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 389  }
 390 };
 391