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