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