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