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