gcc/loop-init.c

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