gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "tm.h"
  24 #include "rtl.h"
  25 #include "hard-reg-set.h"
  26 #include "obstack.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "tree-pass.h"
  31 #include "timevar.h"
  32 #include "flags.h"
  33 #include "df.h"
  34 #include "ggc.h"
  35
  36 \f
  37 /* Initialize loop structures.  This is used by the tree and RTL loop
  38    optimizers.  FLAGS specify what properties to compute and/or ensure for
  39    loops.  */
  40
  41 void
  42 loop_optimizer_init (unsigned flags)
  43 {
  44   struct loops *loops;
  45
  46   gcc_assert (!current_loops);
  47   loops = GGC_CNEW (struct loops);
  48
  49   /* Find the loops.  */
  50
  51   flow_loops_find (loops);
  52   current_loops = loops;
  53
  54   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  55     {
  56       /* If the loops may have multiple latches, we cannot canonicalize
  57          them further (and most of the loop manipulation functions will
  58          not work).  However, we avoid modifying cfg, which some
  59          passes may want.  */
  60       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  61                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  62       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  63     }
  64   else
  65     disambiguate_loops_with_multiple_latches ();
  66
  67   /* Create pre-headers.  */
  68   if (flags & LOOPS_HAVE_PREHEADERS)
  69     {
  70       int cp_flags = CP_SIMPLE_PREHEADERS;
  71
  72       if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
  73         cp_flags |= CP_FALLTHRU_PREHEADERS;
  74
  75       create_preheaders (cp_flags);
  76     }
  77
  78   /* Force all latches to have only single successor.  */
  79   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  80     force_single_succ_latches ();
  81
  82   /* Mark irreducible loops.  */
  83   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  84     mark_irreducible_loops ();
  85
  86   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  87     record_loop_exits ();
  88
  89   /* Dump loops.  */
  90   flow_loops_dump (dump_file, NULL, 1);
  91
  92 #ifdef ENABLE_CHECKING
  93   verify_dominators (CDI_DOMINATORS);
  94   verify_loop_structure ();
  95 #endif
  96 }
  97
  98 /* Finalize loop structures.  */
  99
 100 void
 101 loop_optimizer_finalize (void)
 102 {
 103   loop_iterator li;
 104   struct loop *loop;
 105   basic_block bb;
 106
 107   gcc_assert (current_loops != NULL);
 108
 109   FOR_EACH_LOOP (li, loop, 0)
 110     {
 111       free_simple_loop_desc (loop);
 112     }
 113
 114   /* Clean up.  */
 115   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 116     release_recorded_exits ();
 117   flow_loops_free (current_loops);
 118   ggc_free (current_loops);
 119   current_loops = NULL;
 120
 121   FOR_ALL_BB (bb)
 122     {
 123       bb->loop_father = NULL;
 124     }
 125
 126   /* Checking.  */
 127 #ifdef ENABLE_CHECKING
 128   /* FIXME: no point to verify flow info after bundling on ia64.  Use this
 129      hack for achieving this.  */
 130   if (!reload_completed)
 131     verify_flow_info ();
 132 #endif
 133 }
 134
 135 \f
 136 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 137    See passes.c for more on that.  */
 138
 139 static bool
 140 gate_handle_loop2 (void)
 141 {
 142   return (optimize > 0
 143           && (flag_move_loop_invariants
 144               || flag_unswitch_loops
 145               || flag_peel_loops
 146               || flag_unroll_loops
 147 #ifdef HAVE_doloop_end
 148               || (flag_branch_on_count_reg && HAVE_doloop_end)
 149 #endif
 150               ));
 151 }
 152
 153 struct rtl_opt_pass pass_loop2 =
 154 {
 155  {
 156   RTL_PASS,
 157   "loop2",                              /* name */
 158   gate_handle_loop2,                    /* gate */
 159   NULL,                                 /* execute */
 160   NULL,                                 /* sub */
 161   NULL,                                 /* next */
 162   0,                                    /* static_pass_number */
 163   TV_LOOP,                              /* tv_id */
 164   0,                                    /* properties_required */
 165   0,                                    /* properties_provided */
 166   0,                                    /* properties_destroyed */
 167   0,                                    /* todo_flags_start */
 168   TODO_dump_func |
 169   TODO_ggc_collect                      /* todo_flags_finish */
 170  }
 171 };
 172
 173 \f
 174 /* Initialization of the RTL loop passes.  */
 175 static unsigned int
 176 rtl_loop_init (void)
 177 {
 178   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 179
 180   if (dump_file)
 181     dump_flow_info (dump_file, dump_flags);
 182
 183   loop_optimizer_init (LOOPS_NORMAL);
 184   return 0;
 185 }
 186
 187 struct rtl_opt_pass pass_rtl_loop_init =
 188 {
 189  {
 190   RTL_PASS,
 191   "loop2_init",                           /* name */
 192   NULL,                                 /* gate */
 193   rtl_loop_init,                        /* execute */
 194   NULL,                                 /* sub */
 195   NULL,                                 /* next */
 196   0,                                    /* static_pass_number */
 197   TV_LOOP,                              /* tv_id */
 198   0,                                    /* properties_required */
 199   0,                                    /* properties_provided */
 200   0,                                    /* properties_destroyed */
 201   0,                                    /* todo_flags_start */
 202   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 203  }
 204 };
 205
 206 \f
 207 /* Finalization of the RTL loop passes.  */
 208
 209 static unsigned int
 210 rtl_loop_done (void)
 211 {
 212   loop_optimizer_finalize ();
 213   free_dominance_info (CDI_DOMINATORS);
 214
 215   cleanup_cfg (0);
 216   if (dump_file)
 217     dump_flow_info (dump_file, dump_flags);
 218
 219   return 0;
 220 }
 221
 222 struct rtl_opt_pass pass_rtl_loop_done =
 223 {
 224  {
 225   RTL_PASS,
 226   "loop2_done",                          /* name */
 227   NULL,                                 /* gate */
 228   rtl_loop_done,                        /* execute */
 229   NULL,                                 /* sub */
 230   NULL,                                 /* next */
 231   0,                                    /* static_pass_number */
 232   TV_LOOP,                              /* tv_id */
 233   0,                                    /* properties_required */
 234   0,                                    /* properties_provided */
 235   0,                                    /* properties_destroyed */
 236   0,                                    /* todo_flags_start */
 237   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 238  }
 239 };
 240
 241 \f
 242 /* Loop invariant code motion.  */
 243 static bool
 244 gate_rtl_move_loop_invariants (void)
 245 {
 246   return flag_move_loop_invariants;
 247 }
 248
 249 static unsigned int
 250 rtl_move_loop_invariants (void)
 251 {
 252   if (number_of_loops () > 1)
 253     move_loop_invariants ();
 254   return 0;
 255 }
 256
 257 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 258 {
 259  {
 260   RTL_PASS,
 261   "loop2_invariant",                    /* name */
 262   gate_rtl_move_loop_invariants,        /* gate */
 263   rtl_move_loop_invariants,             /* execute */
 264   NULL,                                 /* sub */
 265   NULL,                                 /* next */
 266   0,                                    /* static_pass_number */
 267   TV_LOOP,                              /* tv_id */
 268   0,                                    /* properties_required */
 269   0,                                    /* properties_provided */
 270   0,                                    /* properties_destroyed */
 271   0,                                    /* todo_flags_start */
 272   TODO_df_verify |
 273   TODO_df_finish | TODO_verify_rtl_sharing |
 274   TODO_dump_func                        /* todo_flags_finish */
 275  }
 276 };
 277
 278 \f
 279 /* Loop unswitching for RTL.  */
 280 static bool
 281 gate_rtl_unswitch (void)
 282 {
 283   return flag_unswitch_loops;
 284 }
 285
 286 static unsigned int
 287 rtl_unswitch (void)
 288 {
 289   if (number_of_loops () > 1)
 290     unswitch_loops ();
 291   return 0;
 292 }
 293
 294 struct rtl_opt_pass pass_rtl_unswitch =
 295 {
 296  {
 297   RTL_PASS,
 298   "loop2_unswitch",                      /* name */
 299   gate_rtl_unswitch,                    /* gate */
 300   rtl_unswitch,                         /* execute */
 301   NULL,                                 /* sub */
 302   NULL,                                 /* next */
 303   0,                                    /* static_pass_number */
 304   TV_LOOP,                              /* tv_id */
 305   0,                                    /* properties_required */
 306   0,                                    /* properties_provided */
 307   0,                                    /* properties_destroyed */
 308   0,                                    /* todo_flags_start */
 309   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 310  }
 311 };
 312
 313 \f
 314 /* Loop unswitching for RTL.  */
 315 static bool
 316 gate_rtl_unroll_and_peel_loops (void)
 317 {
 318   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 319 }
 320
 321 static unsigned int
 322 rtl_unroll_and_peel_loops (void)
 323 {
 324   if (number_of_loops () > 1)
 325     {
 326       int flags = 0;
 327       if (dump_file)
 328         df_dump (dump_file);
 329
 330       if (flag_peel_loops)
 331         flags |= UAP_PEEL;
 332       if (flag_unroll_loops)
 333         flags |= UAP_UNROLL;
 334       if (flag_unroll_all_loops)
 335         flags |= UAP_UNROLL_ALL;
 336
 337       unroll_and_peel_loops (flags);
 338     }
 339   return 0;
 340 }
 341
 342 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 343 {
 344  {
 345   RTL_PASS,
 346   "loop2_unroll",                        /* name */
 347   gate_rtl_unroll_and_peel_loops,       /* gate */
 348   rtl_unroll_and_peel_loops,            /* execute */
 349   NULL,                                 /* sub */
 350   NULL,                                 /* next */
 351   0,                                    /* static_pass_number */
 352   TV_LOOP,                              /* tv_id */
 353   0,                                    /* properties_required */
 354   0,                                    /* properties_provided */
 355   0,                                    /* properties_destroyed */
 356   0,                                    /* todo_flags_start */
 357   TODO_dump_func | TODO_verify_rtl_sharing, /* todo_flags_finish */
 358  }
 359 };
 360
 361 \f
 362 /* The doloop optimization.  */
 363 static bool
 364 gate_rtl_doloop (void)
 365 {
 366 #ifdef HAVE_doloop_end
 367   return (flag_branch_on_count_reg && HAVE_doloop_end);
 368 #else
 369   return 0;
 370 #endif
 371 }
 372
 373 static unsigned int
 374 rtl_doloop (void)
 375 {
 376 #ifdef HAVE_doloop_end
 377   if (number_of_loops () > 1)
 378     doloop_optimize_loops ();
 379 #endif
 380   return 0;
 381 }
 382
 383 struct rtl_opt_pass pass_rtl_doloop =
 384 {
 385  {
 386   RTL_PASS,
 387   "loop2_doloop",                        /* name */
 388   gate_rtl_doloop,                      /* gate */
 389   rtl_doloop,                           /* execute */
 390   NULL,                                 /* sub */
 391   NULL,                                 /* next */
 392   0,                                    /* static_pass_number */
 393   TV_LOOP,                              /* tv_id */
 394   0,                                    /* properties_required */
 395   0,                                    /* properties_provided */
 396   0,                                    /* properties_destroyed */
 397   0,                                    /* todo_flags_start */
 398   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
 399  }
 400 };
 401