gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002, 2003, 2004, 2005 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
  35 \f
  36 /* Initialize loop optimizer.  This is used by the tree and RTL loop
  37    optimizers.  FLAGS specify what properties to compute and/or ensure for
  38    loops.  */
  39
  40 struct loops *
  41 loop_optimizer_init (unsigned flags)
  42 {
  43   struct loops *loops = XCNEW (struct loops);
  44   edge e;
  45   edge_iterator ei;
  46   static bool first_time = true;
  47
  48   if (first_time)
  49     {
  50       first_time = false;
  51       init_set_costs ();
  52     }
  53
  54   /* Avoid annoying special cases of edges going to exit
  55      block.  */
  56
  57   for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
  58     if ((e->flags & EDGE_FALLTHRU) && !single_succ_p (e->src))
  59       split_edge (e);
  60     else
  61       ei_next (&ei);
  62
  63   /* Find the loops.  */
  64
  65   if (flow_loops_find (loops) <= 1)
  66     {
  67       /* No loops.  */
  68       flow_loops_free (loops);
  69       free (loops);
  70
  71       return NULL;
  72     }
  73
  74   /* Not going to update these.  */
  75   free (loops->cfg.rc_order);
  76   loops->cfg.rc_order = NULL;
  77   free (loops->cfg.dfs_order);
  78   loops->cfg.dfs_order = NULL;
  79
  80   /* Create pre-headers.  */
  81   if (flags & LOOPS_HAVE_PREHEADERS)
  82     create_preheaders (loops, CP_SIMPLE_PREHEADERS);
  83
  84   /* Force all latches to have only single successor.  */
  85   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  86     force_single_succ_latches (loops);
  87
  88   /* Mark irreducible loops.  */
  89   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  90     mark_irreducible_loops (loops);
  91
  92   if (flags & LOOPS_HAVE_MARKED_SINGLE_EXITS)
  93     mark_single_exit_loops (loops);
  94
  95   /* Dump loops.  */
  96   flow_loops_dump (loops, dump_file, NULL, 1);
  97
  98 #ifdef ENABLE_CHECKING
  99   verify_dominators (CDI_DOMINATORS);
 100   verify_loop_structure (loops);
 101 #endif
 102
 103   return loops;
 104 }
 105
 106 /* Finalize loop optimizer.  */
 107 void
 108 loop_optimizer_finalize (struct loops *loops)
 109 {
 110   unsigned i;
 111
 112   if (!loops)
 113     return;
 114
 115   for (i = 1; i < loops->num; i++)
 116     if (loops->parray[i])
 117       free_simple_loop_desc (loops->parray[i]);
 118
 119   /* Clean up.  */
 120   flow_loops_free (loops);
 121   free (loops);
 122
 123   /* Checking.  */
 124 #ifdef ENABLE_CHECKING
 125   verify_flow_info ();
 126 #endif
 127 }
 128
 129 \f
 130 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 131    See passes.c for more on that.  */
 132
 133 static bool
 134 gate_handle_loop2 (void)
 135 {
 136   return (optimize > 0
 137           && (flag_move_loop_invariants
 138               || flag_unswitch_loops
 139               || flag_peel_loops
 140               || flag_unroll_loops
 141 #ifdef HAVE_doloop_end
 142               || (flag_branch_on_count_reg && HAVE_doloop_end)
 143 #endif
 144               ));
 145 }
 146
 147 struct tree_opt_pass pass_loop2 =
 148 {
 149   "loop2",                              /* name */
 150   gate_handle_loop2,                    /* gate */
 151   NULL,                                 /* execute */
 152   NULL,                                 /* sub */
 153   NULL,                                 /* next */
 154   0,                                    /* static_pass_number */
 155   TV_LOOP,                              /* tv_id */
 156   0,                                    /* properties_required */
 157   0,                                    /* properties_provided */
 158   0,                                    /* properties_destroyed */
 159   0,                                    /* todo_flags_start */
 160   TODO_dump_func |
 161   TODO_ggc_collect,                     /* todo_flags_finish */
 162   'L'                                   /* letter */
 163 };
 164
 165 \f
 166 /* Initialization of the RTL loop passes.  */
 167 static void
 168 rtl_loop_init (void)
 169 {
 170   if (dump_file)
 171     dump_flow_info (dump_file, dump_flags);
 172
 173   /* Initialize structures for layout changes.  */
 174   cfg_layout_initialize (0);
 175
 176   current_loops = loop_optimizer_init (LOOPS_NORMAL);
 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 void
 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 }
 222
 223 struct tree_opt_pass pass_rtl_loop_done =
 224 {
 225   "loop2_done",                          /* name */
 226   NULL,                                 /* gate */
 227   rtl_loop_done,                        /* execute */
 228   NULL,                                 /* sub */
 229   NULL,                                 /* next */
 230   0,                                    /* static_pass_number */
 231   TV_LOOP,                              /* tv_id */
 232   0,                                    /* properties_required */
 233   0,                                    /* properties_provided */
 234   0,                                    /* properties_destroyed */
 235   0,                                    /* todo_flags_start */
 236   TODO_dump_func,                       /* todo_flags_finish */
 237   'L'                                   /* letter */
 238 };
 239
 240 \f
 241 /* Loop invariant code motion.  */
 242 static bool
 243 gate_rtl_move_loop_invariants (void)
 244 {
 245   return flag_move_loop_invariants;
 246 }
 247
 248 static void
 249 rtl_move_loop_invariants (void)
 250 {
 251   if (current_loops)
 252     move_loop_invariants (current_loops);
 253 }
 254
 255 struct tree_opt_pass pass_rtl_move_loop_invariants =
 256 {
 257   "loop2_invariant",                     /* name */
 258   gate_rtl_move_loop_invariants,        /* gate */
 259   rtl_move_loop_invariants,             /* execute */
 260   NULL,                                 /* sub */
 261   NULL,                                 /* next */
 262   0,                                    /* static_pass_number */
 263   TV_LOOP,                              /* tv_id */
 264   0,                                    /* properties_required */
 265   0,                                    /* properties_provided */
 266   0,                                    /* properties_destroyed */
 267   0,                                    /* todo_flags_start */
 268   TODO_dump_func,                       /* todo_flags_finish */
 269   'L'                                   /* letter */
 270 };
 271
 272 \f
 273 /* Loop unswitching for RTL.  */
 274 static bool
 275 gate_rtl_unswitch (void)
 276 {
 277   return flag_unswitch_loops;
 278 }
 279
 280 static void
 281 rtl_unswitch (void)
 282 {
 283   if (current_loops)
 284     unswitch_loops (current_loops);
 285 }
 286
 287 struct tree_opt_pass pass_rtl_unswitch =
 288 {
 289   "loop2_unswitch",                      /* name */
 290   gate_rtl_unswitch,                    /* gate */
 291   rtl_unswitch,                         /* execute */
 292   NULL,                                 /* sub */
 293   NULL,                                 /* next */
 294   0,                                    /* static_pass_number */
 295   TV_LOOP,                              /* tv_id */
 296   0,                                    /* properties_required */
 297   0,                                    /* properties_provided */
 298   0,                                    /* properties_destroyed */
 299   0,                                    /* todo_flags_start */
 300   TODO_dump_func,                       /* todo_flags_finish */
 301   'L'                                   /* letter */
 302 };
 303
 304 \f
 305 /* Loop unswitching for RTL.  */
 306 static bool
 307 gate_rtl_unroll_and_peel_loops (void)
 308 {
 309   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 310 }
 311
 312 static void
 313 rtl_unroll_and_peel_loops (void)
 314 {
 315   if (current_loops)
 316     {
 317       int flags = 0;
 318
 319       if (flag_peel_loops)
 320         flags |= UAP_PEEL;
 321       if (flag_unroll_loops)
 322         flags |= UAP_UNROLL;
 323       if (flag_unroll_all_loops)
 324         flags |= UAP_UNROLL_ALL;
 325
 326       unroll_and_peel_loops (current_loops, flags);
 327     }
 328 }
 329
 330 struct tree_opt_pass pass_rtl_unroll_and_peel_loops =
 331 {
 332   "loop2_unroll",                        /* name */
 333   gate_rtl_unroll_and_peel_loops,       /* gate */
 334   rtl_unroll_and_peel_loops,            /* execute */
 335   NULL,                                 /* sub */
 336   NULL,                                 /* next */
 337   0,                                    /* static_pass_number */
 338   TV_LOOP,                              /* tv_id */
 339   0,                                    /* properties_required */
 340   0,                                    /* properties_provided */
 341   0,                                    /* properties_destroyed */
 342   0,                                    /* todo_flags_start */
 343   TODO_dump_func,                       /* todo_flags_finish */
 344   'L'                                   /* letter */
 345 };
 346
 347 \f
 348 /* The doloop optimization.  */
 349 static bool
 350 gate_rtl_doloop (void)
 351 {
 352 #ifdef HAVE_doloop_end
 353   return (flag_branch_on_count_reg && HAVE_doloop_end);
 354 #else
 355   return 0;
 356 #endif
 357 }
 358
 359 static void
 360 rtl_doloop (void)
 361 {
 362 #ifdef HAVE_doloop_end
 363   if (current_loops)
 364     doloop_optimize_loops (current_loops);
 365 #endif
 366 }
 367
 368 struct tree_opt_pass pass_rtl_doloop =
 369 {
 370   "loop2_doloop",                        /* name */
 371   gate_rtl_doloop,                      /* gate */
 372   rtl_doloop,                           /* execute */
 373   NULL,                                 /* sub */
 374   NULL,                                 /* next */
 375   0,                                    /* static_pass_number */
 376   TV_LOOP,                              /* tv_id */
 377   0,                                    /* properties_required */
 378   0,                                    /* properties_provided */
 379   0,                                    /* properties_destroyed */
 380   0,                                    /* todo_flags_start */
 381   TODO_dump_func,                       /* todo_flags_finish */
 382   'L'                                   /* letter */
 383 };
 384