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 "hard-reg-set.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     dump_flow_info (dump_file, dump_flags);
 208
 209   loop_optimizer_init (LOOPS_NORMAL);
 210   return 0;
 211 }
 212
 213 struct rtl_opt_pass pass_rtl_loop_init =
 214 {
 215  {
 216   RTL_PASS,
 217   "loop2_init",                           /* name */
 218   NULL,                                 /* gate */
 219   rtl_loop_init,                        /* execute */
 220   NULL,                                 /* sub */
 221   NULL,                                 /* next */
 222   0,                                    /* static_pass_number */
 223   TV_LOOP,                              /* tv_id */
 224   0,                                    /* properties_required */
 225   0,                                    /* properties_provided */
 226   0,                                    /* properties_destroyed */
 227   0,                                    /* todo_flags_start */
 228   TODO_verify_rtl_sharing               /* todo_flags_finish */
 229  }
 230 };
 231
 232 \f
 233 /* Finalization of the RTL loop passes.  */
 234
 235 static unsigned int
 236 rtl_loop_done (void)
 237 {
 238   /* No longer preserve loops, remove them now.  */
 239   cfun->curr_properties &= ~PROP_loops;
 240   loop_optimizer_finalize ();
 241   free_dominance_info (CDI_DOMINATORS);
 242
 243   cleanup_cfg (0);
 244   if (dump_file)
 245     dump_flow_info (dump_file, dump_flags);
 246
 247   return 0;
 248 }
 249
 250 struct rtl_opt_pass pass_rtl_loop_done =
 251 {
 252  {
 253   RTL_PASS,
 254   "loop2_done",                          /* name */
 255   NULL,                                 /* gate */
 256   rtl_loop_done,                        /* 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   PROP_loops,                           /* properties_destroyed */
 264   0,                                    /* todo_flags_start */
 265   TODO_verify_flow
 266     | TODO_verify_rtl_sharing           /* todo_flags_finish */
 267  }
 268 };
 269
 270 \f
 271 /* Loop invariant code motion.  */
 272 static bool
 273 gate_rtl_move_loop_invariants (void)
 274 {
 275   return flag_move_loop_invariants;
 276 }
 277
 278 static unsigned int
 279 rtl_move_loop_invariants (void)
 280 {
 281   if (number_of_loops () > 1)
 282     move_loop_invariants ();
 283   return 0;
 284 }
 285
 286 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 287 {
 288  {
 289   RTL_PASS,
 290   "loop2_invariant",                    /* name */
 291   gate_rtl_move_loop_invariants,        /* gate */
 292   rtl_move_loop_invariants,             /* execute */
 293   NULL,                                 /* sub */
 294   NULL,                                 /* next */
 295   0,                                    /* static_pass_number */
 296   TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
 297   0,                                    /* properties_required */
 298   0,                                    /* properties_provided */
 299   0,                                    /* properties_destroyed */
 300   0,                                    /* todo_flags_start */
 301   TODO_df_verify |
 302   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 303  }
 304 };
 305
 306 \f
 307 /* Loop unswitching for RTL.  */
 308 static bool
 309 gate_rtl_unswitch (void)
 310 {
 311   return flag_unswitch_loops;
 312 }
 313
 314 static unsigned int
 315 rtl_unswitch (void)
 316 {
 317   if (number_of_loops () > 1)
 318     unswitch_loops ();
 319   return 0;
 320 }
 321
 322 struct rtl_opt_pass pass_rtl_unswitch =
 323 {
 324  {
 325   RTL_PASS,
 326   "loop2_unswitch",                      /* name */
 327   gate_rtl_unswitch,                    /* gate */
 328   rtl_unswitch,                         /* execute */
 329   NULL,                                 /* sub */
 330   NULL,                                 /* next */
 331   0,                                    /* static_pass_number */
 332   TV_LOOP_UNSWITCH,                     /* tv_id */
 333   0,                                    /* properties_required */
 334   0,                                    /* properties_provided */
 335   0,                                    /* properties_destroyed */
 336   0,                                    /* todo_flags_start */
 337   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 338  }
 339 };
 340
 341 \f
 342 /* Loop unswitching for RTL.  */
 343 static bool
 344 gate_rtl_unroll_and_peel_loops (void)
 345 {
 346   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 347 }
 348
 349 static unsigned int
 350 rtl_unroll_and_peel_loops (void)
 351 {
 352   if (number_of_loops () > 1)
 353     {
 354       int flags = 0;
 355       if (dump_file)
 356         df_dump (dump_file);
 357
 358       if (flag_peel_loops)
 359         flags |= UAP_PEEL;
 360       if (flag_unroll_loops)
 361         flags |= UAP_UNROLL;
 362       if (flag_unroll_all_loops)
 363         flags |= UAP_UNROLL_ALL;
 364
 365       unroll_and_peel_loops (flags);
 366     }
 367   return 0;
 368 }
 369
 370 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 371 {
 372  {
 373   RTL_PASS,
 374   "loop2_unroll",                        /* name */
 375   gate_rtl_unroll_and_peel_loops,       /* gate */
 376   rtl_unroll_and_peel_loops,            /* execute */
 377   NULL,                                 /* sub */
 378   NULL,                                 /* next */
 379   0,                                    /* static_pass_number */
 380   TV_LOOP_UNROLL,                       /* tv_id */
 381   0,                                    /* properties_required */
 382   0,                                    /* properties_provided */
 383   0,                                    /* properties_destroyed */
 384   0,                                    /* todo_flags_start */
 385   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 386  }
 387 };
 388
 389 \f
 390 /* The doloop optimization.  */
 391 static bool
 392 gate_rtl_doloop (void)
 393 {
 394 #ifdef HAVE_doloop_end
 395   return (flag_branch_on_count_reg && HAVE_doloop_end);
 396 #else
 397   return 0;
 398 #endif
 399 }
 400
 401 static unsigned int
 402 rtl_doloop (void)
 403 {
 404 #ifdef HAVE_doloop_end
 405   if (number_of_loops () > 1)
 406     doloop_optimize_loops ();
 407 #endif
 408   return 0;
 409 }
 410
 411 struct rtl_opt_pass pass_rtl_doloop =
 412 {
 413  {
 414   RTL_PASS,
 415   "loop2_doloop",                        /* name */
 416   gate_rtl_doloop,                      /* gate */
 417   rtl_doloop,                           /* execute */
 418   NULL,                                 /* sub */
 419   NULL,                                 /* next */
 420   0,                                    /* static_pass_number */
 421   TV_LOOP_DOLOOP,                       /* tv_id */
 422   0,                                    /* properties_required */
 423   0,                                    /* properties_provided */
 424   0,                                    /* properties_destroyed */
 425   0,                                    /* todo_flags_start */
 426   TODO_verify_rtl_sharing               /* todo_flags_finish */
 427  }
 428 };