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 2, 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 COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  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_CNEW (struct 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       current_loops->state = 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     create_preheaders (CP_SIMPLE_PREHEADERS);
  71
  72   /* Force all latches to have only single successor.  */
  73   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  74     force_single_succ_latches ();
  75
  76   /* Mark irreducible loops.  */
  77   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  78     mark_irreducible_loops ();
  79
  80   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  81     record_loop_exits ();
  82
  83   /* Dump loops.  */
  84   flow_loops_dump (dump_file, NULL, 1);
  85
  86 #ifdef ENABLE_CHECKING
  87   verify_dominators (CDI_DOMINATORS);
  88   verify_loop_structure ();
  89 #endif
  90 }
  91
  92 /* Finalize loop structures.  */
  93
  94 void
  95 loop_optimizer_finalize (void)
  96 {
  97   loop_iterator li;
  98   struct loop *loop;
  99   basic_block bb;
 100
 101   gcc_assert (current_loops != NULL);
 102
 103   FOR_EACH_LOOP (li, loop, 0)
 104     {
 105       free_simple_loop_desc (loop);
 106     }
 107
 108   /* Clean up.  */
 109   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
 110     release_recorded_exits ();
 111   flow_loops_free (current_loops);
 112   ggc_free (current_loops);
 113   current_loops = NULL;
 114
 115   FOR_ALL_BB (bb)
 116     {
 117       bb->loop_father = NULL;
 118     }
 119
 120   /* Checking.  */
 121 #ifdef ENABLE_CHECKING
 122   verify_flow_info ();
 123 #endif
 124 }
 125
 126 \f
 127 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 128    See passes.c for more on that.  */
 129
 130 static bool
 131 gate_handle_loop2 (void)
 132 {
 133   return (optimize > 0
 134           && (flag_move_loop_invariants
 135               || flag_unswitch_loops
 136               || flag_peel_loops
 137               || flag_unroll_loops
 138 #ifdef HAVE_doloop_end
 139               || (flag_branch_on_count_reg && HAVE_doloop_end)
 140 #endif
 141               ));
 142 }
 143
 144 struct tree_opt_pass pass_loop2 =
 145 {
 146   "loop2",                              /* name */
 147   gate_handle_loop2,                    /* gate */
 148   NULL,                                 /* execute */
 149   NULL,                                 /* sub */
 150   NULL,                                 /* next */
 151   0,                                    /* static_pass_number */
 152   TV_LOOP,                              /* tv_id */
 153   0,                                    /* properties_required */
 154   0,                                    /* properties_provided */
 155   0,                                    /* properties_destroyed */
 156   0,                                    /* todo_flags_start */
 157   TODO_dump_func |
 158   TODO_ggc_collect,                     /* todo_flags_finish */
 159   'L'                                   /* letter */
 160 };
 161
 162 \f
 163 /* Initialization of the RTL loop passes.  */
 164 static unsigned int
 165 rtl_loop_init (void)
 166 {
 167   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 168
 169   if (dump_file)
 170     dump_flow_info (dump_file, dump_flags);
 171
 172   loop_optimizer_init (LOOPS_NORMAL);
 173   return 0;
 174 }
 175
 176 struct tree_opt_pass pass_rtl_loop_init =
 177 {
 178   "loop2_init",                           /* name */
 179   NULL,                                 /* gate */
 180   rtl_loop_init,                        /* execute */
 181   NULL,                                 /* sub */
 182   NULL,                                 /* next */
 183   0,                                    /* static_pass_number */
 184   TV_LOOP,                              /* tv_id */
 185   0,                                    /* properties_required */
 186   0,                                    /* properties_provided */
 187   0,                                    /* properties_destroyed */
 188   0,                                    /* todo_flags_start */
 189   TODO_dump_func,                       /* todo_flags_finish */
 190   'L'                                   /* letter */
 191 };
 192
 193 \f
 194 /* Finalization of the RTL loop passes.  */
 195
 196 static unsigned int
 197 rtl_loop_done (void)
 198 {
 199   loop_optimizer_finalize ();
 200   free_dominance_info (CDI_DOMINATORS);
 201
 202   cleanup_cfg (0);
 203   if (dump_file)
 204     dump_flow_info (dump_file, dump_flags);
 205
 206   return 0;
 207 }
 208
 209 struct tree_opt_pass pass_rtl_loop_done =
 210 {
 211   "loop2_done",                          /* name */
 212   NULL,                                 /* gate */
 213   rtl_loop_done,                        /* execute */
 214   NULL,                                 /* sub */
 215   NULL,                                 /* next */
 216   0,                                    /* static_pass_number */
 217   TV_LOOP,                              /* tv_id */
 218   0,                                    /* properties_required */
 219   0,                                    /* properties_provided */
 220   0,                                    /* properties_destroyed */
 221   0,                                    /* todo_flags_start */
 222   TODO_dump_func,                       /* todo_flags_finish */
 223   'L'                                   /* letter */
 224 };
 225
 226 \f
 227 /* Loop invariant code motion.  */
 228 static bool
 229 gate_rtl_move_loop_invariants (void)
 230 {
 231   return flag_move_loop_invariants;
 232 }
 233
 234 static unsigned int
 235 rtl_move_loop_invariants (void)
 236 {
 237   if (number_of_loops () > 1)
 238     move_loop_invariants ();
 239   return 0;
 240 }
 241
 242 struct tree_opt_pass pass_rtl_move_loop_invariants =
 243 {
 244   "loop2_invariant",                    /* name */
 245   gate_rtl_move_loop_invariants,        /* gate */
 246   rtl_move_loop_invariants,             /* execute */
 247   NULL,                                 /* sub */
 248   NULL,                                 /* next */
 249   0,                                    /* static_pass_number */
 250   TV_LOOP,                              /* tv_id */
 251   0,                                    /* properties_required */
 252   0,                                    /* properties_provided */
 253   0,                                    /* properties_destroyed */
 254   0,                                    /* todo_flags_start */
 255   TODO_df_finish |                      /* This is shutting down the instance in loop_invariant.c  */
 256   TODO_dump_func,                       /* todo_flags_finish */
 257   'L'                                   /* letter */
 258 };
 259
 260 \f
 261 /* Loop unswitching for RTL.  */
 262 static bool
 263 gate_rtl_unswitch (void)
 264 {
 265   return flag_unswitch_loops;
 266 }
 267
 268 static unsigned int
 269 rtl_unswitch (void)
 270 {
 271   if (number_of_loops () > 1)
 272     unswitch_loops ();
 273   return 0;
 274 }
 275
 276 struct tree_opt_pass pass_rtl_unswitch =
 277 {
 278   "loop2_unswitch",                      /* name */
 279   gate_rtl_unswitch,                    /* gate */
 280   rtl_unswitch,                         /* execute */
 281   NULL,                                 /* sub */
 282   NULL,                                 /* next */
 283   0,                                    /* static_pass_number */
 284   TV_LOOP,                              /* tv_id */
 285   0,                                    /* properties_required */
 286   0,                                    /* properties_provided */
 287   0,                                    /* properties_destroyed */
 288   0,                                    /* todo_flags_start */
 289   TODO_dump_func,                       /* todo_flags_finish */
 290   'L'                                   /* letter */
 291 };
 292
 293 \f
 294 /* Loop unswitching for RTL.  */
 295 static bool
 296 gate_rtl_unroll_and_peel_loops (void)
 297 {
 298   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 299 }
 300
 301 static unsigned int
 302 rtl_unroll_and_peel_loops (void)
 303 {
 304   if (number_of_loops () > 1)
 305     {
 306       int flags = 0;
 307       if (dump_file)
 308         df_dump (dump_file);
 309
 310       if (flag_peel_loops)
 311         flags |= UAP_PEEL;
 312       if (flag_unroll_loops)
 313         flags |= UAP_UNROLL;
 314       if (flag_unroll_all_loops)
 315         flags |= UAP_UNROLL_ALL;
 316
 317       unroll_and_peel_loops (flags);
 318     }
 319   return 0;
 320 }
 321
 322 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 323 {
 324   "loop2_unroll",                        /* name */
 325   gate_rtl_unroll_and_peel_loops,       /* gate */
 326   rtl_unroll_and_peel_loops,            /* execute */
 327   NULL,                                 /* sub */
 328   NULL,                                 /* next */
 329   0,                                    /* static_pass_number */
 330   TV_LOOP,                              /* tv_id */
 331   0,                                    /* properties_required */
 332   0,                                    /* properties_provided */
 333   0,                                    /* properties_destroyed */
 334   0,                                    /* todo_flags_start */
 335   TODO_dump_func,                       /* todo_flags_finish */
 336   'L'                                   /* letter */
 337 };
 338
 339 \f
 340 /* The doloop optimization.  */
 341 static bool
 342 gate_rtl_doloop (void)
 343 {
 344 #ifdef HAVE_doloop_end
 345   return (flag_branch_on_count_reg && HAVE_doloop_end);
 346 #else
 347   return 0;
 348 #endif
 349 }
 350
 351 static unsigned int
 352 rtl_doloop (void)
 353 {
 354 #ifdef HAVE_doloop_end
 355   if (number_of_loops () > 1)
 356     doloop_optimize_loops ();
 357 #endif
 358   return 0;
 359 }
 360
 361 struct tree_opt_pass pass_rtl_doloop =
 362 {
 363   "loop2_doloop",                        /* name */
 364   gate_rtl_doloop,                      /* gate */
 365   rtl_doloop,                           /* execute */
 366   NULL,                                 /* sub */
 367   NULL,                                 /* next */
 368   0,                                    /* static_pass_number */
 369   TV_LOOP,                              /* tv_id */
 370   0,                                    /* properties_required */
 371   0,                                    /* properties_provided */
 372   0,                                    /* properties_destroyed */
 373   0,                                    /* todo_flags_start */
 374   TODO_dump_func,                       /* todo_flags_finish */
 375   'L'                                   /* letter */
 376 };
 377