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