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_dump_func |
 162   TODO_ggc_collect                      /* todo_flags_finish */
 163  }
 164 };
 165
 166 \f
 167 /* Initialization of the RTL loop passes.  */
 168 static unsigned int
 169 rtl_loop_init (void)
 170 {
 171   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 172
 173   if (dump_file)
 174     dump_flow_info (dump_file, dump_flags);
 175
 176   loop_optimizer_init (LOOPS_NORMAL);
 177   return 0;
 178 }
 179
 180 struct rtl_opt_pass pass_rtl_loop_init =
 181 {
 182  {
 183   RTL_PASS,
 184   "loop2_init",                           /* name */
 185   NULL,                                 /* gate */
 186   rtl_loop_init,                        /* execute */
 187   NULL,                                 /* sub */
 188   NULL,                                 /* next */
 189   0,                                    /* static_pass_number */
 190   TV_LOOP,                              /* tv_id */
 191   0,                                    /* properties_required */
 192   0,                                    /* properties_provided */
 193   0,                                    /* properties_destroyed */
 194   0,                                    /* todo_flags_start */
 195   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 196  }
 197 };
 198
 199 \f
 200 /* Finalization of the RTL loop passes.  */
 201
 202 static unsigned int
 203 rtl_loop_done (void)
 204 {
 205   loop_optimizer_finalize ();
 206   free_dominance_info (CDI_DOMINATORS);
 207
 208   cleanup_cfg (0);
 209   if (dump_file)
 210     dump_flow_info (dump_file, dump_flags);
 211
 212   return 0;
 213 }
 214
 215 struct rtl_opt_pass pass_rtl_loop_done =
 216 {
 217  {
 218   RTL_PASS,
 219   "loop2_done",                          /* name */
 220   NULL,                                 /* gate */
 221   rtl_loop_done,                        /* 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_flow
 231     | TODO_verify_rtl_sharing
 232     | TODO_dump_func                    /* todo_flags_finish */
 233  }
 234 };
 235
 236 \f
 237 /* Loop invariant code motion.  */
 238 static bool
 239 gate_rtl_move_loop_invariants (void)
 240 {
 241   return flag_move_loop_invariants;
 242 }
 243
 244 static unsigned int
 245 rtl_move_loop_invariants (void)
 246 {
 247   if (number_of_loops () > 1)
 248     move_loop_invariants ();
 249   return 0;
 250 }
 251
 252 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 253 {
 254  {
 255   RTL_PASS,
 256   "loop2_invariant",                    /* name */
 257   gate_rtl_move_loop_invariants,        /* gate */
 258   rtl_move_loop_invariants,             /* execute */
 259   NULL,                                 /* sub */
 260   NULL,                                 /* next */
 261   0,                                    /* static_pass_number */
 262   TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
 263   0,                                    /* properties_required */
 264   0,                                    /* properties_provided */
 265   0,                                    /* properties_destroyed */
 266   0,                                    /* todo_flags_start */
 267   TODO_df_verify |
 268   TODO_df_finish | TODO_verify_rtl_sharing |
 269   TODO_dump_func                        /* todo_flags_finish */
 270  }
 271 };
 272
 273 \f
 274 /* Loop unswitching for RTL.  */
 275 static bool
 276 gate_rtl_unswitch (void)
 277 {
 278   return flag_unswitch_loops;
 279 }
 280
 281 static unsigned int
 282 rtl_unswitch (void)
 283 {
 284   if (number_of_loops () > 1)
 285     unswitch_loops ();
 286   return 0;
 287 }
 288
 289 struct rtl_opt_pass pass_rtl_unswitch =
 290 {
 291  {
 292   RTL_PASS,
 293   "loop2_unswitch",                      /* name */
 294   gate_rtl_unswitch,                    /* gate */
 295   rtl_unswitch,                         /* execute */
 296   NULL,                                 /* sub */
 297   NULL,                                 /* next */
 298   0,                                    /* static_pass_number */
 299   TV_LOOP_UNSWITCH,                     /* tv_id */
 300   0,                                    /* properties_required */
 301   0,                                    /* properties_provided */
 302   0,                                    /* properties_destroyed */
 303   0,                                    /* todo_flags_start */
 304   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 305  }
 306 };
 307
 308 \f
 309 /* Loop unswitching for RTL.  */
 310 static bool
 311 gate_rtl_unroll_and_peel_loops (void)
 312 {
 313   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 314 }
 315
 316 static unsigned int
 317 rtl_unroll_and_peel_loops (void)
 318 {
 319   if (number_of_loops () > 1)
 320     {
 321       int flags = 0;
 322       if (dump_file)
 323         df_dump (dump_file);
 324
 325       if (flag_peel_loops)
 326         flags |= UAP_PEEL;
 327       if (flag_unroll_loops)
 328         flags |= UAP_UNROLL;
 329       if (flag_unroll_all_loops)
 330         flags |= UAP_UNROLL_ALL;
 331
 332       unroll_and_peel_loops (flags);
 333     }
 334   return 0;
 335 }
 336
 337 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 338 {
 339  {
 340   RTL_PASS,
 341   "loop2_unroll",                        /* name */
 342   gate_rtl_unroll_and_peel_loops,       /* gate */
 343   rtl_unroll_and_peel_loops,            /* execute */
 344   NULL,                                 /* sub */
 345   NULL,                                 /* next */
 346   0,                                    /* static_pass_number */
 347   TV_LOOP_UNROLL,                       /* tv_id */
 348   0,                                    /* properties_required */
 349   0,                                    /* properties_provided */
 350   0,                                    /* properties_destroyed */
 351   0,                                    /* todo_flags_start */
 352   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 353  }
 354 };
 355
 356 \f
 357 /* The doloop optimization.  */
 358 static bool
 359 gate_rtl_doloop (void)
 360 {
 361 #ifdef HAVE_doloop_end
 362   return (flag_branch_on_count_reg && HAVE_doloop_end);
 363 #else
 364   return 0;
 365 #endif
 366 }
 367
 368 static unsigned int
 369 rtl_doloop (void)
 370 {
 371 #ifdef HAVE_doloop_end
 372   if (number_of_loops () > 1)
 373     doloop_optimize_loops ();
 374 #endif
 375   return 0;
 376 }
 377
 378 struct rtl_opt_pass pass_rtl_doloop =
 379 {
 380  {
 381   RTL_PASS,
 382   "loop2_doloop",                        /* name */
 383   gate_rtl_doloop,                      /* gate */
 384   rtl_doloop,                           /* execute */
 385   NULL,                                 /* sub */
 386   NULL,                                 /* next */
 387   0,                                    /* static_pass_number */
 388   TV_LOOP_DOLOOP,                       /* tv_id */
 389   0,                                    /* properties_required */
 390   0,                                    /* properties_provided */
 391   0,                                    /* properties_destroyed */
 392   0,                                    /* todo_flags_start */
 393   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 394  }
 395 };
 396