gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 2005, 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
  34 \f
  35 /* Initialize loop optimizer.  This is used by the tree and RTL loop
  36    optimizers.  FLAGS specify what properties to compute and/or ensure for
  37    loops.  */
  38
  39 struct loops *
  40 loop_optimizer_init (unsigned flags)
  41 {
  42   struct loops *loops = XCNEW (struct loops);
  43   edge e;
  44   edge_iterator ei;
  45   static bool first_time = true;
  46
  47   if (first_time)
  48     {
  49       first_time = false;
  50       init_set_costs ();
  51     }
  52
  53   /* Avoid annoying special cases of edges going to exit
  54      block.  */
  55
  56   for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
  57     if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
  58       split_edge (e);
  59     else
  60       ei_next (&ei);
  61
  62   /* Find the loops.  */
  63
  64   if (flow_loops_find (loops) <= 1)
  65     {
  66       /* No loops.  */
  67       flow_loops_free (loops);
  68       free (loops);
  69
  70       return NULL;
  71     }
  72
  73   /* Not going to update these.  */
  74   free (loops->cfg.rc_order);
  75   loops->cfg.rc_order = NULL;
  76   free (loops->cfg.dfs_order);
  77   loops->cfg.dfs_order = NULL;
  78
  79   /* Create pre-headers.  */
  80   if (flags & LOOPS_HAVE_PREHEADERS)
  81     create_preheaders (loops, CP_SIMPLE_PREHEADERS);
  82
  83   /* Force all latches to have only single successor.  */
  84   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  85     force_single_succ_latches (loops);
  86
  87   /* Mark irreducible loops.  */
  88   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  89     mark_irreducible_loops (loops);
  90
  91   if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
  92     mark_single_exit_loops (loops);
  93
  94   /* Dump loops.  */
  95   flow_loops_dump (loops, dump_file, NULL, 1);
  96
  97 #ifdef ENABLE_CHECKING
  98   verify_dominators (CDI_DOMINATORS);
  99   verify_loop_structure (loops);
 100 #endif
 101
 102   return loops;
 103 }
 104
 105 /* Finalize loop optimizer.  */
 106 void
 107 loop_optimizer_finalize (struct loops *loops)
 108 {
 109   unsigned i;
 110
 111   if (!loops)
 112     return;
 113
 114   for (i = 1; i < loops->num; i++)
 115     if (loops->parray[i])
 116       free_simple_loop_desc (loops->parray[i]);
 117
 118   /* Clean up.  */
 119   flow_loops_free (loops);
 120   free (loops);
 121
 122   /* Checking.  */
 123 #ifdef ENABLE_CHECKING
 124   verify_flow_info ();
 125 #endif
 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 tree_opt_pass pass_loop2 =
 147 {
 148   "loop2",                              /* name */
 149   gate_handle_loop2,                    /* gate */
 150   NULL,                                 /* execute */
 151   NULL,                                 /* sub */
 152   NULL,                                 /* next */
 153   0,                                    /* static_pass_number */
 154   TV_LOOP,                              /* tv_id */
 155   0,                                    /* properties_required */
 156   0,                                    /* properties_provided */
 157   0,                                    /* properties_destroyed */
 158   0,                                    /* todo_flags_start */
 159   TODO_dump_func |
 160   TODO_ggc_collect,                     /* todo_flags_finish */
 161   'L'                                   /* letter */
 162 };
 163
 164 \f
 165 /* Initialization of the RTL loop passes.  */
 166 static unsigned int
 167 rtl_loop_init (void)
 168 {
 169   if (dump_file)
 170     dump_flow_info (dump_file, dump_flags);
 171
 172   /* Initialize structures for layout changes.  */
 173   cfg_layout_initialize (0);
 174
 175   current_loops = loop_optimizer_init (LOOPS_NORMAL);
 176   return 0;
 177 }
 178
 179 struct tree_opt_pass pass_rtl_loop_init =
 180 {
 181   "loop2_init",                           /* name */
 182   NULL,                                 /* gate */
 183   rtl_loop_init,                        /* execute */
 184   NULL,                                 /* sub */
 185   NULL,                                 /* next */
 186   0,                                    /* static_pass_number */
 187   TV_LOOP,                              /* tv_id */
 188   0,                                    /* properties_required */
 189   0,                                    /* properties_provided */
 190   0,                                    /* properties_destroyed */
 191   0,                                    /* todo_flags_start */
 192   TODO_dump_func,                       /* todo_flags_finish */
 193   'L'                                   /* letter */
 194 };
 195
 196 \f
 197 /* Finalization of the RTL loop passes.  */
 198 static unsigned int
 199 rtl_loop_done (void)
 200 {
 201   basic_block bb;
 202
 203   if (current_loops)
 204     loop_optimizer_finalize (current_loops);
 205
 206   free_dominance_info (CDI_DOMINATORS);
 207
 208   /* Finalize layout changes.  */
 209   FOR_EACH_BB (bb)
 210     if (bb->next_bb != EXIT_BLOCK_PTR)
 211       bb->aux = bb->next_bb;
 212   cfg_layout_finalize ();
 213
 214   cleanup_cfg (CLEANUP_EXPENSIVE);
 215   delete_trivially_dead_insns (get_insns (), max_reg_num ());
 216   reg_scan (get_insns (), max_reg_num ());
 217   if (dump_file)
 218     dump_flow_info (dump_file, dump_flags);
 219
 220   current_loops = NULL;
 221   return 0;
 222 }
 223
 224 struct tree_opt_pass pass_rtl_loop_done =
 225 {
 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_flags_finish */
 238   'L'                                   /* letter */
 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 (current_loops)
 253     move_loop_invariants (current_loops);
 254   return 0;
 255 }
 256
 257 struct tree_opt_pass pass_rtl_move_loop_invariants =
 258 {
 259   "loop2_invariant",                     /* name */
 260   gate_rtl_move_loop_invariants,        /* gate */
 261   rtl_move_loop_invariants,             /* execute */
 262   NULL,                                 /* sub */
 263   NULL,                                 /* next */
 264   0,                                    /* static_pass_number */
 265   TV_LOOP,                              /* tv_id */
 266   0,                                    /* properties_required */
 267   0,                                    /* properties_provided */
 268   0,                                    /* properties_destroyed */
 269   0,                                    /* todo_flags_start */
 270   TODO_dump_func,                       /* todo_flags_finish */
 271   'L'                                   /* letter */
 272 };
 273
 274 \f
 275 /* Loop unswitching for RTL.  */
 276 static bool
 277 gate_rtl_unswitch (void)
 278 {
 279   return flag_unswitch_loops;
 280 }
 281
 282 static unsigned int
 283 rtl_unswitch (void)
 284 {
 285   if (current_loops)
 286     unswitch_loops (current_loops);
 287   return 0;
 288 }
 289
 290 struct tree_opt_pass pass_rtl_unswitch =
 291 {
 292   "loop2_unswitch",                      /* name */
 293   gate_rtl_unswitch,                    /* gate */
 294   rtl_unswitch,                         /* execute */
 295   NULL,                                 /* sub */
 296   NULL,                                 /* next */
 297   0,                                    /* static_pass_number */
 298   TV_LOOP,                              /* tv_id */
 299   0,                                    /* properties_required */
 300   0,                                    /* properties_provided */
 301   0,                                    /* properties_destroyed */
 302   0,                                    /* todo_flags_start */
 303   TODO_dump_func,                       /* todo_flags_finish */
 304   'L'                                   /* letter */
 305 };
 306
 307 \f
 308 /* Loop unswitching for RTL.  */
 309 static bool
 310 gate_rtl_unroll_and_peel_loops (void)
 311 {
 312   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 313 }
 314
 315 static unsigned int
 316 rtl_unroll_and_peel_loops (void)
 317 {
 318   if (current_loops)
 319     {
 320       int flags = 0;
 321
 322       if (flag_peel_loops)
 323         flags |= UAP_PEEL;
 324       if (flag_unroll_loops)
 325         flags |= UAP_UNROLL;
 326       if (flag_unroll_all_loops)
 327         flags |= UAP_UNROLL_ALL;
 328
 329       unroll_and_peel_loops (current_loops, flags);
 330     }
 331   return 0;
 332 }
 333
 334 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 335 {
 336   "loop2_unroll",                        /* name */
 337   gate_rtl_unroll_and_peel_loops,       /* gate */
 338   rtl_unroll_and_peel_loops,            /* execute */
 339   NULL,                                 /* sub */
 340   NULL,                                 /* next */
 341   0,                                    /* static_pass_number */
 342   TV_LOOP,                              /* tv_id */
 343   0,                                    /* properties_required */
 344   0,                                    /* properties_provided */
 345   0,                                    /* properties_destroyed */
 346   0,                                    /* todo_flags_start */
 347   TODO_dump_func,                       /* todo_flags_finish */
 348   'L'                                   /* letter */
 349 };
 350
 351 \f
 352 /* The doloop optimization.  */
 353 static bool
 354 gate_rtl_doloop (void)
 355 {
 356 #ifdef HAVE_doloop_end
 357   return (flag_branch_on_count_reg && HAVE_doloop_end);
 358 #else
 359   return 0;
 360 #endif
 361 }
 362
 363 static unsigned int
 364 rtl_doloop (void)
 365 {
 366 #ifdef HAVE_doloop_end
 367   if (current_loops)
 368     doloop_optimize_loops (current_loops);
 369 #endif
 370   return 0;
 371 }
 372
 373 struct tree_opt_pass pass_rtl_doloop =
 374 {
 375   "loop2_doloop",                        /* name */
 376   gate_rtl_doloop,                      /* gate */
 377   rtl_doloop,                           /* execute */
 378   NULL,                                 /* sub */
 379   NULL,                                 /* next */
 380   0,                                    /* static_pass_number */
 381   TV_LOOP,                              /* tv_id */
 382   0,                                    /* properties_required */
 383   0,                                    /* properties_provided */
 384   0,                                    /* properties_destroyed */
 385   0,                                    /* todo_flags_start */
 386   TODO_dump_func,                       /* todo_flags_finish */
 387   'L'                                   /* letter */
 388 };
 389