gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "regs.h"
  27 #include "obstack.h"
  28 #include "basic-block.h"
  29 #include "cfgloop.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   if (!current_loops)
  45     {
  46       struct loops *loops = ggc_alloc_cleared_loops ();
  47
  48       gcc_assert (!(cfun->curr_properties & PROP_loops));
  49
  50       /* Find the loops.  */
  51
  52       flow_loops_find (loops);
  53       current_loops = loops;
  54     }
  55   else
  56     {
  57       gcc_assert (cfun->curr_properties & PROP_loops);
  58
  59       /* Ensure that the dominators are computed, like flow_loops_find does.  */
  60       calculate_dominance_info (CDI_DOMINATORS);
  61
  62 #ifdef ENABLE_CHECKING
  63       verify_loop_structure ();
  64 #endif
  65     }
  66
  67   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  68     {
  69       /* If the loops may have multiple latches, we cannot canonicalize
  70          them further (and most of the loop manipulation functions will
  71          not work).  However, we avoid modifying cfg, which some
  72          passes may want.  */
  73       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  74                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  75       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  76     }
  77   else
  78     disambiguate_loops_with_multiple_latches ();
  79
  80   /* Create pre-headers.  */
  81   if (flags & LOOPS_HAVE_PREHEADERS)
  82     {
  83       int cp_flags = CP_SIMPLE_PREHEADERS;
  84
  85       if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
  86         cp_flags |= CP_FALLTHRU_PREHEADERS;
  87
  88       create_preheaders (cp_flags);
  89     }
  90
  91   /* Force all latches to have only single successor.  */
  92   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  93     force_single_succ_latches ();
  94
  95   /* Mark irreducible loops.  */
  96   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  97     mark_irreducible_loops ();
  98
  99   if (flags & LOOPS_HAVE_RECORDED_EXITS)
 100     record_loop_exits ();
 101
 102   /* Dump loops.  */
 103   flow_loops_dump (dump_file, NULL, 1);
 104
 105 #ifdef ENABLE_CHECKING
 106   verify_loop_structure ();
 107 #endif
 108 }
 109
 110 /* Finalize loop structures.  */
 111
 112 void
 113 loop_optimizer_finalize (void)
 114 {
 115   loop_iterator li;
 116   struct loop *loop;
 117   basic_block bb;
 118
 119   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 120     release_recorded_exits ();
 121
 122   /* If we should preserve loop structure, do not free it but clear
 123      flags that advanced properties are there as we are not preserving
 124      that in full.  */
 125   if (cfun->curr_properties & PROP_loops)
 126     {
 127       loops_state_clear (LOOP_CLOSED_SSA
 128                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 129                          | LOOPS_HAVE_PREHEADERS
 130                          | LOOPS_HAVE_SIMPLE_LATCHES
 131                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 132       return;
 133     }
 134
 135   gcc_assert (current_loops != NULL);
 136
 137   FOR_EACH_LOOP (li, loop, 0)
 138     {
 139       free_simple_loop_desc (loop);
 140     }
 141
 142   /* Clean up.  */
 143   flow_loops_free (current_loops);
 144   ggc_free (current_loops);
 145   current_loops = NULL;
 146
 147   FOR_ALL_BB (bb)
 148     {
 149       bb->loop_father = NULL;
 150     }
 151 }
 152
 153 \f
 154 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 155    See passes.c for more on that.  */
 156
 157 static bool
 158 gate_handle_loop2 (void)
 159 {
 160   if (optimize > 0
 161       && (flag_move_loop_invariants
 162           || flag_unswitch_loops
 163           || flag_peel_loops
 164           || flag_unroll_loops
 165 #ifdef HAVE_doloop_end
 166           || (flag_branch_on_count_reg && HAVE_doloop_end)
 167 #endif
 168          ))
 169     return true;
 170   else
 171     {
 172       /* No longer preserve loops, remove them now.  */
 173       cfun->curr_properties &= ~PROP_loops;
 174       if (current_loops)
 175         loop_optimizer_finalize ();
 176       return false;
 177     }
 178 }
 179
 180 struct rtl_opt_pass pass_loop2 =
 181 {
 182  {
 183   RTL_PASS,
 184   "loop2",                              /* name */
 185   gate_handle_loop2,                    /* gate */
 186   NULL,                                 /* execute */
 187   NULL,                                 /* sub */
 188   NULL,                                 /* next */
 189   0,                                    /* static_pass_number */
 190   TV_LOOP,                              /* tv_id */
 191   0,                                    /* properties_required */
 192   0,                                    /* properties_provided */
 193   0,                                    /* properties_destroyed */
 194   0,                                    /* todo_flags_start */
 195   TODO_ggc_collect                      /* todo_flags_finish */
 196  }
 197 };
 198
 199 \f
 200 /* Initialization of the RTL loop passes.  */
 201 static unsigned int
 202 rtl_loop_init (void)
 203 {
 204   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 205
 206   if (dump_file)
 207     {
 208       dump_reg_info (dump_file);
 209       dump_flow_info (dump_file, dump_flags);
 210     }
 211
 212   loop_optimizer_init (LOOPS_NORMAL);
 213   return 0;
 214 }
 215
 216 struct rtl_opt_pass pass_rtl_loop_init =
 217 {
 218  {
 219   RTL_PASS,
 220   "loop2_init",                           /* name */
 221   NULL,                                 /* gate */
 222   rtl_loop_init,                        /* execute */
 223   NULL,                                 /* sub */
 224   NULL,                                 /* next */
 225   0,                                    /* static_pass_number */
 226   TV_LOOP,                              /* tv_id */
 227   0,                                    /* properties_required */
 228   0,                                    /* properties_provided */
 229   0,                                    /* properties_destroyed */
 230   0,                                    /* todo_flags_start */
 231   TODO_verify_rtl_sharing               /* todo_flags_finish */
 232  }
 233 };
 234
 235 \f
 236 /* Finalization of the RTL loop passes.  */
 237
 238 static unsigned int
 239 rtl_loop_done (void)
 240 {
 241   /* No longer preserve loops, remove them now.  */
 242   cfun->curr_properties &= ~PROP_loops;
 243   loop_optimizer_finalize ();
 244   free_dominance_info (CDI_DOMINATORS);
 245
 246   cleanup_cfg (0);
 247   if (dump_file)
 248     {
 249       dump_reg_info (dump_file);
 250       dump_flow_info (dump_file, dump_flags);
 251     }
 252
 253   return 0;
 254 }
 255
 256 struct rtl_opt_pass pass_rtl_loop_done =
 257 {
 258  {
 259   RTL_PASS,
 260   "loop2_done",                          /* name */
 261   NULL,                                 /* gate */
 262   rtl_loop_done,                        /* execute */
 263   NULL,                                 /* sub */
 264   NULL,                                 /* next */
 265   0,                                    /* static_pass_number */
 266   TV_LOOP,                              /* tv_id */
 267   0,                                    /* properties_required */
 268   0,                                    /* properties_provided */
 269   PROP_loops,                           /* properties_destroyed */
 270   0,                                    /* todo_flags_start */
 271   TODO_verify_flow
 272     | TODO_verify_rtl_sharing           /* todo_flags_finish */
 273  }
 274 };
 275
 276 \f
 277 /* Loop invariant code motion.  */
 278 static bool
 279 gate_rtl_move_loop_invariants (void)
 280 {
 281   return flag_move_loop_invariants;
 282 }
 283
 284 static unsigned int
 285 rtl_move_loop_invariants (void)
 286 {
 287   if (number_of_loops () > 1)
 288     move_loop_invariants ();
 289   return 0;
 290 }
 291
 292 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 293 {
 294  {
 295   RTL_PASS,
 296   "loop2_invariant",                    /* name */
 297   gate_rtl_move_loop_invariants,        /* gate */
 298   rtl_move_loop_invariants,             /* execute */
 299   NULL,                                 /* sub */
 300   NULL,                                 /* next */
 301   0,                                    /* static_pass_number */
 302   TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
 303   0,                                    /* properties_required */
 304   0,                                    /* properties_provided */
 305   0,                                    /* properties_destroyed */
 306   0,                                    /* todo_flags_start */
 307   TODO_df_verify |
 308   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 309  }
 310 };
 311
 312 \f
 313 /* Loop unswitching for RTL.  */
 314 static bool
 315 gate_rtl_unswitch (void)
 316 {
 317   return flag_unswitch_loops;
 318 }
 319
 320 static unsigned int
 321 rtl_unswitch (void)
 322 {
 323   if (number_of_loops () > 1)
 324     unswitch_loops ();
 325   return 0;
 326 }
 327
 328 struct rtl_opt_pass pass_rtl_unswitch =
 329 {
 330  {
 331   RTL_PASS,
 332   "loop2_unswitch",                      /* name */
 333   gate_rtl_unswitch,                    /* gate */
 334   rtl_unswitch,                         /* execute */
 335   NULL,                                 /* sub */
 336   NULL,                                 /* next */
 337   0,                                    /* static_pass_number */
 338   TV_LOOP_UNSWITCH,                     /* tv_id */
 339   0,                                    /* properties_required */
 340   0,                                    /* properties_provided */
 341   0,                                    /* properties_destroyed */
 342   0,                                    /* todo_flags_start */
 343   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 344  }
 345 };
 346
 347 \f
 348 /* Loop unswitching for RTL.  */
 349 static bool
 350 gate_rtl_unroll_and_peel_loops (void)
 351 {
 352   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 353 }
 354
 355 static unsigned int
 356 rtl_unroll_and_peel_loops (void)
 357 {
 358   if (number_of_loops () > 1)
 359     {
 360       int flags = 0;
 361       if (dump_file)
 362         df_dump (dump_file);
 363
 364       if (flag_peel_loops)
 365         flags |= UAP_PEEL;
 366       if (flag_unroll_loops)
 367         flags |= UAP_UNROLL;
 368       if (flag_unroll_all_loops)
 369         flags |= UAP_UNROLL_ALL;
 370
 371       unroll_and_peel_loops (flags);
 372     }
 373   return 0;
 374 }
 375
 376 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 377 {
 378  {
 379   RTL_PASS,
 380   "loop2_unroll",                        /* name */
 381   gate_rtl_unroll_and_peel_loops,       /* gate */
 382   rtl_unroll_and_peel_loops,            /* execute */
 383   NULL,                                 /* sub */
 384   NULL,                                 /* next */
 385   0,                                    /* static_pass_number */
 386   TV_LOOP_UNROLL,                       /* tv_id */
 387   0,                                    /* properties_required */
 388   0,                                    /* properties_provided */
 389   0,                                    /* properties_destroyed */
 390   0,                                    /* todo_flags_start */
 391   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 392  }
 393 };
 394
 395 \f
 396 /* The doloop optimization.  */
 397 static bool
 398 gate_rtl_doloop (void)
 399 {
 400 #ifdef HAVE_doloop_end
 401   return (flag_branch_on_count_reg && HAVE_doloop_end);
 402 #else
 403   return 0;
 404 #endif
 405 }
 406
 407 static unsigned int
 408 rtl_doloop (void)
 409 {
 410 #ifdef HAVE_doloop_end
 411   if (number_of_loops () > 1)
 412     doloop_optimize_loops ();
 413 #endif
 414   return 0;
 415 }
 416
 417 struct rtl_opt_pass pass_rtl_doloop =
 418 {
 419  {
 420   RTL_PASS,
 421   "loop2_doloop",                        /* name */
 422   gate_rtl_doloop,                      /* gate */
 423   rtl_doloop,                           /* execute */
 424   NULL,                                 /* sub */
 425   NULL,                                 /* next */
 426   0,                                    /* static_pass_number */
 427   TV_LOOP_DOLOOP,                       /* tv_id */
 428   0,                                    /* properties_required */
 429   0,                                    /* properties_provided */
 430   0,                                    /* properties_destroyed */
 431   0,                                    /* todo_flags_start */
 432   TODO_verify_rtl_sharing               /* todo_flags_finish */
 433  }
 434 };