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 "flags.h"
  32 #include "df.h"
  33 #include "ggc.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   timevar_push (TV_LOOP_INIT);
  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   timevar_pop (TV_LOOP_INIT);
 110 }
 111
 112 /* Finalize loop structures.  */
 113
 114 void
 115 loop_optimizer_finalize (void)
 116 {
 117   loop_iterator li;
 118   struct loop *loop;
 119   basic_block bb;
 120
 121   timevar_push (TV_LOOP_FINI);
 122
 123   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 124     release_recorded_exits ();
 125
 126   /* If we should preserve loop structure, do not free it but clear
 127      flags that advanced properties are there as we are not preserving
 128      that in full.  */
 129   if (cfun->curr_properties & PROP_loops)
 130     {
 131       loops_state_clear (LOOP_CLOSED_SSA
 132                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 133                          | LOOPS_HAVE_PREHEADERS
 134                          | LOOPS_HAVE_SIMPLE_LATCHES
 135                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 136       goto loop_fini_done;
 137     }
 138
 139   gcc_assert (current_loops != NULL);
 140
 141   FOR_EACH_LOOP (li, loop, 0)
 142     {
 143       free_simple_loop_desc (loop);
 144     }
 145
 146   /* Clean up.  */
 147   flow_loops_free (current_loops);
 148   ggc_free (current_loops);
 149   current_loops = NULL;
 150
 151   FOR_ALL_BB (bb)
 152     {
 153       bb->loop_father = NULL;
 154     }
 155
 156 loop_fini_done:
 157   timevar_pop (TV_LOOP_FINI);
 158 }
 159
 160 \f
 161 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 162    See passes.c for more on that.  */
 163
 164 static bool
 165 gate_handle_loop2 (void)
 166 {
 167   if (optimize > 0
 168       && (flag_move_loop_invariants
 169           || flag_unswitch_loops
 170           || flag_peel_loops
 171           || flag_unroll_loops
 172 #ifdef HAVE_doloop_end
 173           || (flag_branch_on_count_reg && HAVE_doloop_end)
 174 #endif
 175          ))
 176     return true;
 177   else
 178     {
 179       /* No longer preserve loops, remove them now.  */
 180       cfun->curr_properties &= ~PROP_loops;
 181       if (current_loops)
 182         loop_optimizer_finalize ();
 183       return false;
 184     }
 185 }
 186
 187 struct rtl_opt_pass pass_loop2 =
 188 {
 189  {
 190   RTL_PASS,
 191   "loop2",                              /* name */
 192   gate_handle_loop2,                    /* gate */
 193   NULL,                                 /* execute */
 194   NULL,                                 /* sub */
 195   NULL,                                 /* next */
 196   0,                                    /* static_pass_number */
 197   TV_LOOP,                              /* tv_id */
 198   0,                                    /* properties_required */
 199   0,                                    /* properties_provided */
 200   0,                                    /* properties_destroyed */
 201   0,                                    /* todo_flags_start */
 202   TODO_ggc_collect                      /* todo_flags_finish */
 203  }
 204 };
 205
 206 \f
 207 /* Initialization of the RTL loop passes.  */
 208 static unsigned int
 209 rtl_loop_init (void)
 210 {
 211   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 212
 213   if (dump_file)
 214     {
 215       dump_reg_info (dump_file);
 216       dump_flow_info (dump_file, dump_flags);
 217     }
 218
 219   loop_optimizer_init (LOOPS_NORMAL);
 220   return 0;
 221 }
 222
 223 struct rtl_opt_pass pass_rtl_loop_init =
 224 {
 225  {
 226   RTL_PASS,
 227   "loop2_init",                           /* name */
 228   NULL,                                 /* gate */
 229   rtl_loop_init,                        /* execute */
 230   NULL,                                 /* sub */
 231   NULL,                                 /* next */
 232   0,                                    /* static_pass_number */
 233   TV_LOOP,                              /* tv_id */
 234   0,                                    /* properties_required */
 235   0,                                    /* properties_provided */
 236   0,                                    /* properties_destroyed */
 237   0,                                    /* todo_flags_start */
 238   TODO_verify_rtl_sharing               /* todo_flags_finish */
 239  }
 240 };
 241
 242 \f
 243 /* Finalization of the RTL loop passes.  */
 244
 245 static unsigned int
 246 rtl_loop_done (void)
 247 {
 248   /* No longer preserve loops, remove them now.  */
 249   cfun->curr_properties &= ~PROP_loops;
 250   loop_optimizer_finalize ();
 251   free_dominance_info (CDI_DOMINATORS);
 252
 253   cleanup_cfg (0);
 254   if (dump_file)
 255     {
 256       dump_reg_info (dump_file);
 257       dump_flow_info (dump_file, dump_flags);
 258     }
 259
 260   return 0;
 261 }
 262
 263 struct rtl_opt_pass pass_rtl_loop_done =
 264 {
 265  {
 266   RTL_PASS,
 267   "loop2_done",                          /* name */
 268   NULL,                                 /* gate */
 269   rtl_loop_done,                        /* execute */
 270   NULL,                                 /* sub */
 271   NULL,                                 /* next */
 272   0,                                    /* static_pass_number */
 273   TV_LOOP,                              /* tv_id */
 274   0,                                    /* properties_required */
 275   0,                                    /* properties_provided */
 276   PROP_loops,                           /* properties_destroyed */
 277   0,                                    /* todo_flags_start */
 278   TODO_verify_flow
 279     | TODO_verify_rtl_sharing           /* todo_flags_finish */
 280  }
 281 };
 282
 283 \f
 284 /* Loop invariant code motion.  */
 285 static bool
 286 gate_rtl_move_loop_invariants (void)
 287 {
 288   return flag_move_loop_invariants;
 289 }
 290
 291 static unsigned int
 292 rtl_move_loop_invariants (void)
 293 {
 294   if (number_of_loops () > 1)
 295     move_loop_invariants ();
 296   return 0;
 297 }
 298
 299 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 300 {
 301  {
 302   RTL_PASS,
 303   "loop2_invariant",                    /* name */
 304   gate_rtl_move_loop_invariants,        /* gate */
 305   rtl_move_loop_invariants,             /* execute */
 306   NULL,                                 /* sub */
 307   NULL,                                 /* next */
 308   0,                                    /* static_pass_number */
 309   TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
 310   0,                                    /* properties_required */
 311   0,                                    /* properties_provided */
 312   0,                                    /* properties_destroyed */
 313   0,                                    /* todo_flags_start */
 314   TODO_df_verify |
 315   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 316  }
 317 };
 318
 319 \f
 320 /* Loop unswitching for RTL.  */
 321 static bool
 322 gate_rtl_unswitch (void)
 323 {
 324   return flag_unswitch_loops;
 325 }
 326
 327 static unsigned int
 328 rtl_unswitch (void)
 329 {
 330   if (number_of_loops () > 1)
 331     unswitch_loops ();
 332   return 0;
 333 }
 334
 335 struct rtl_opt_pass pass_rtl_unswitch =
 336 {
 337  {
 338   RTL_PASS,
 339   "loop2_unswitch",                      /* name */
 340   gate_rtl_unswitch,                    /* gate */
 341   rtl_unswitch,                         /* execute */
 342   NULL,                                 /* sub */
 343   NULL,                                 /* next */
 344   0,                                    /* static_pass_number */
 345   TV_LOOP_UNSWITCH,                     /* tv_id */
 346   0,                                    /* properties_required */
 347   0,                                    /* properties_provided */
 348   0,                                    /* properties_destroyed */
 349   0,                                    /* todo_flags_start */
 350   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 351  }
 352 };
 353
 354 \f
 355 /* Loop unswitching for RTL.  */
 356 static bool
 357 gate_rtl_unroll_and_peel_loops (void)
 358 {
 359   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 360 }
 361
 362 static unsigned int
 363 rtl_unroll_and_peel_loops (void)
 364 {
 365   if (number_of_loops () > 1)
 366     {
 367       int flags = 0;
 368       if (dump_file)
 369         df_dump (dump_file);
 370
 371       if (flag_peel_loops)
 372         flags |= UAP_PEEL;
 373       if (flag_unroll_loops)
 374         flags |= UAP_UNROLL;
 375       if (flag_unroll_all_loops)
 376         flags |= UAP_UNROLL_ALL;
 377
 378       unroll_and_peel_loops (flags);
 379     }
 380   return 0;
 381 }
 382
 383 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 384 {
 385  {
 386   RTL_PASS,
 387   "loop2_unroll",                        /* name */
 388   gate_rtl_unroll_and_peel_loops,       /* gate */
 389   rtl_unroll_and_peel_loops,            /* execute */
 390   NULL,                                 /* sub */
 391   NULL,                                 /* next */
 392   0,                                    /* static_pass_number */
 393   TV_LOOP_UNROLL,                       /* tv_id */
 394   0,                                    /* properties_required */
 395   0,                                    /* properties_provided */
 396   0,                                    /* properties_destroyed */
 397   0,                                    /* todo_flags_start */
 398   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 399  }
 400 };
 401
 402 \f
 403 /* The doloop optimization.  */
 404 static bool
 405 gate_rtl_doloop (void)
 406 {
 407 #ifdef HAVE_doloop_end
 408   return (flag_branch_on_count_reg && HAVE_doloop_end);
 409 #else
 410   return 0;
 411 #endif
 412 }
 413
 414 static unsigned int
 415 rtl_doloop (void)
 416 {
 417 #ifdef HAVE_doloop_end
 418   if (number_of_loops () > 1)
 419     doloop_optimize_loops ();
 420 #endif
 421   return 0;
 422 }
 423
 424 struct rtl_opt_pass pass_rtl_doloop =
 425 {
 426  {
 427   RTL_PASS,
 428   "loop2_doloop",                        /* name */
 429   gate_rtl_doloop,                      /* gate */
 430   rtl_doloop,                           /* execute */
 431   NULL,                                 /* sub */
 432   NULL,                                 /* next */
 433   0,                                    /* static_pass_number */
 434   TV_LOOP_DOLOOP,                       /* tv_id */
 435   0,                                    /* properties_required */
 436   0,                                    /* properties_provided */
 437   0,                                    /* properties_destroyed */
 438   0,                                    /* todo_flags_start */
 439   TODO_verify_rtl_sharing               /* todo_flags_finish */
 440  }
 441 };