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