gcc/loop-init.c

   1 /* Loop optimizer initialization routines and RTL loop optimization passes.
   2    Copyright (C) 2002-2013 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 "regs.h"
  26 #include "obstack.h"
  27 #include "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "tree-pass.h"
  30 #include "flags.h"
  31 #include "df.h"
  32 #include "ggc.h"
  33
  34 \f
  35 /* Apply FLAGS to the loop state.  */
  36
  37 static void
  38 apply_loop_flags (unsigned flags)
  39 {
  40   if (flags & LOOPS_MAY_HAVE_MULTIPLE_LATCHES)
  41     {
  42       /* If the loops may have multiple latches, we cannot canonicalize
  43          them further (and most of the loop manipulation functions will
  44          not work).  However, we avoid modifying cfg, which some
  45          passes may want.  */
  46       gcc_assert ((flags & ~(LOOPS_MAY_HAVE_MULTIPLE_LATCHES
  47                              | LOOPS_HAVE_RECORDED_EXITS)) == 0);
  48       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
  49     }
  50   else
  51     disambiguate_loops_with_multiple_latches ();
  52
  53   /* Create pre-headers.  */
  54   if (flags & LOOPS_HAVE_PREHEADERS)
  55     {
  56       int cp_flags = CP_SIMPLE_PREHEADERS;
  57
  58       if (flags & LOOPS_HAVE_FALLTHRU_PREHEADERS)
  59         cp_flags |= CP_FALLTHRU_PREHEADERS;
  60
  61       create_preheaders (cp_flags);
  62     }
  63
  64   /* Force all latches to have only single successor.  */
  65   if (flags & LOOPS_HAVE_SIMPLE_LATCHES)
  66     force_single_succ_latches ();
  67
  68   /* Mark irreducible loops.  */
  69   if (flags & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
  70     mark_irreducible_loops ();
  71
  72   if (flags & LOOPS_HAVE_RECORDED_EXITS)
  73     record_loop_exits ();
  74 }
  75
  76 /* Initialize loop structures.  This is used by the tree and RTL loop
  77    optimizers.  FLAGS specify what properties to compute and/or ensure for
  78    loops.  */
  79
  80 void
  81 loop_optimizer_init (unsigned flags)
  82 {
  83   timevar_push (TV_LOOP_INIT);
  84
  85   if (!current_loops)
  86     {
  87       gcc_assert (!(cfun->curr_properties & PROP_loops));
  88
  89       /* Find the loops.  */
  90       current_loops = flow_loops_find (NULL);
  91     }
  92   else
  93     {
  94       gcc_assert (cfun->curr_properties & PROP_loops);
  95
  96       /* Ensure that the dominators are computed, like flow_loops_find does.  */
  97       calculate_dominance_info (CDI_DOMINATORS);
  98
  99 #ifdef ENABLE_CHECKING
 100       verify_loop_structure ();
 101 #endif
 102
 103       /* Clear all flags.  */
 104       loops_state_clear (~0U);
 105     }
 106
 107   /* Apply flags to loops.  */
 108   apply_loop_flags (flags);
 109
 110   /* Dump loops.  */
 111   flow_loops_dump (dump_file, NULL, 1);
 112
 113 #ifdef ENABLE_CHECKING
 114   verify_loop_structure ();
 115 #endif
 116
 117   timevar_pop (TV_LOOP_INIT);
 118 }
 119
 120 /* Finalize loop structures.  */
 121
 122 void
 123 loop_optimizer_finalize (void)
 124 {
 125   loop_iterator li;
 126   struct loop *loop;
 127   basic_block bb;
 128
 129   timevar_push (TV_LOOP_FINI);
 130
 131   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 132     release_recorded_exits ();
 133
 134   /* If we should preserve loop structure, do not free it but clear
 135      flags that advanced properties are there as we are not preserving
 136      that in full.  */
 137   if (cfun->curr_properties & PROP_loops)
 138     {
 139       loops_state_clear (LOOP_CLOSED_SSA
 140                          | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
 141                          | LOOPS_HAVE_PREHEADERS
 142                          | LOOPS_HAVE_SIMPLE_LATCHES
 143                          | LOOPS_HAVE_FALLTHRU_PREHEADERS);
 144       loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
 145       goto loop_fini_done;
 146     }
 147
 148   gcc_assert (current_loops != NULL);
 149
 150   FOR_EACH_LOOP (li, loop, 0)
 151     {
 152       free_simple_loop_desc (loop);
 153     }
 154
 155   /* Clean up.  */
 156   flow_loops_free (current_loops);
 157   ggc_free (current_loops);
 158   current_loops = NULL;
 159
 160   FOR_ALL_BB (bb)
 161     {
 162       bb->loop_father = NULL;
 163     }
 164
 165 loop_fini_done:
 166   timevar_pop (TV_LOOP_FINI);
 167 }
 168
 169 /* The structure of loops might have changed.  Some loops might get removed
 170    (and their headers and latches were set to NULL), loop exists might get
 171    removed (thus the loop nesting may be wrong), and some blocks and edges
 172    were changed (so the information about bb --> loop mapping does not have
 173    to be correct).  But still for the remaining loops the header dominates
 174    the latch, and loops did not get new subloops (new loops might possibly
 175    get created, but we are not interested in them).  Fix up the mess.
 176
 177    If CHANGED_BBS is not NULL, basic blocks whose loop depth has changed are
 178    marked in it.
 179
 180    Returns the number of new discovered loops.  */
 181
 182 unsigned
 183 fix_loop_structure (bitmap changed_bbs)
 184 {
 185   basic_block bb;
 186   int record_exits = 0;
 187   loop_iterator li;
 188   struct loop *loop;
 189   unsigned old_nloops, i;
 190
 191   timevar_push (TV_LOOP_INIT);
 192
 193   /* We need exact and fast dominance info to be available.  */
 194   gcc_assert (dom_info_state (CDI_DOMINATORS) == DOM_OK);
 195
 196   if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
 197     {
 198       release_recorded_exits ();
 199       record_exits = LOOPS_HAVE_RECORDED_EXITS;
 200     }
 201
 202   /* Remember the depth of the blocks in the loop hierarchy, so that we can
 203      recognize blocks whose loop nesting relationship has changed.  */
 204   if (changed_bbs)
 205     FOR_EACH_BB (bb)
 206       bb->aux = (void *) (size_t) loop_depth (bb->loop_father);
 207
 208   /* Remove the dead loops from structures.  We start from the innermost
 209      loops, so that when we remove the loops, we know that the loops inside
 210      are preserved, and do not waste time relinking loops that will be
 211      removed later.  */
 212   FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
 213     {
 214       /* Detect the case that the loop is no longer present even though
 215          it wasn't marked for removal.
 216          ???  If we do that we can get away with not marking loops for
 217          removal at all.  And possibly avoid some spurious removals.  */
 218       if (loop->header
 219           && bb_loop_header_p (loop->header))
 220         continue;
 221
 222       if (dump_file && (dump_flags & TDF_DETAILS))
 223         fprintf (dump_file, "fix_loop_structure: removing loop %d\n",
 224                  loop->num);
 225
 226       while (loop->inner)
 227         {
 228           struct loop *ploop = loop->inner;
 229           flow_loop_tree_node_remove (ploop);
 230           flow_loop_tree_node_add (loop_outer (loop), ploop);
 231         }
 232
 233       /* Remove the loop.  */
 234       loop->header = NULL;
 235       flow_loop_tree_node_remove (loop);
 236     }
 237
 238   /* Remember the number of loops so we can return how many new loops
 239      flow_loops_find discovered.  */
 240   old_nloops = number_of_loops ();
 241
 242   /* Re-compute loop structure in-place.  */
 243   flow_loops_find (current_loops);
 244
 245   /* Mark the blocks whose loop has changed.  */
 246   if (changed_bbs)
 247     {
 248       FOR_EACH_BB (bb)
 249         {
 250           if ((void *) (size_t) loop_depth (bb->loop_father) != bb->aux)
 251             bitmap_set_bit (changed_bbs, bb->index);
 252
 253           bb->aux = NULL;
 254         }
 255     }
 256
 257   /* Finally free deleted loops.  */
 258   FOR_EACH_VEC_ELT (*get_loops (), i, loop)
 259     if (loop && loop->header == NULL)
 260       {
 261         (*get_loops ())[i] = NULL;
 262         flow_loop_free (loop);
 263       }
 264
 265   loops_state_clear (LOOPS_NEED_FIXUP);
 266
 267   /* Apply flags to loops.  */
 268   apply_loop_flags (current_loops->state | record_exits);
 269
 270 #ifdef ENABLE_CHECKING
 271   verify_loop_structure ();
 272 #endif
 273
 274   timevar_pop (TV_LOOP_INIT);
 275
 276   return number_of_loops () - old_nloops;
 277 }
 278 \f
 279 /* Gate for the RTL loop superpass.  The actual passes are subpasses.
 280    See passes.c for more on that.  */
 281
 282 static bool
 283 gate_handle_loop2 (void)
 284 {
 285   if (optimize > 0
 286       && (flag_move_loop_invariants
 287           || flag_unswitch_loops
 288           || flag_peel_loops
 289           || flag_unroll_loops
 290 #ifdef HAVE_doloop_end
 291           || (flag_branch_on_count_reg && HAVE_doloop_end)
 292 #endif
 293          ))
 294     return true;
 295   else
 296     {
 297       /* No longer preserve loops, remove them now.  */
 298       cfun->curr_properties &= ~PROP_loops;
 299       if (current_loops)
 300         loop_optimizer_finalize ();
 301       return false;
 302     }
 303 }
 304
 305 struct rtl_opt_pass pass_loop2 =
 306 {
 307  {
 308   RTL_PASS,
 309   "loop2",                              /* name */
 310   OPTGROUP_LOOP,                        /* optinfo_flags */
 311   gate_handle_loop2,                    /* gate */
 312   NULL,                                 /* execute */
 313   NULL,                                 /* sub */
 314   NULL,                                 /* next */
 315   0,                                    /* static_pass_number */
 316   TV_LOOP,                              /* tv_id */
 317   0,                                    /* properties_required */
 318   0,                                    /* properties_provided */
 319   0,                                    /* properties_destroyed */
 320   0,                                    /* todo_flags_start */
 321   TODO_ggc_collect                      /* todo_flags_finish */
 322  }
 323 };
 324
 325 \f
 326 /* Initialization of the RTL loop passes.  */
 327 static unsigned int
 328 rtl_loop_init (void)
 329 {
 330   gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
 331
 332   if (dump_file)
 333     {
 334       dump_reg_info (dump_file);
 335       dump_flow_info (dump_file, dump_flags);
 336     }
 337
 338   loop_optimizer_init (LOOPS_NORMAL);
 339   return 0;
 340 }
 341
 342 struct rtl_opt_pass pass_rtl_loop_init =
 343 {
 344  {
 345   RTL_PASS,
 346   "loop2_init",                           /* name */
 347   OPTGROUP_LOOP,                        /* optinfo_flags */
 348   NULL,                                 /* gate */
 349   rtl_loop_init,                        /* execute */
 350   NULL,                                 /* sub */
 351   NULL,                                 /* next */
 352   0,                                    /* static_pass_number */
 353   TV_LOOP,                              /* tv_id */
 354   0,                                    /* properties_required */
 355   0,                                    /* properties_provided */
 356   0,                                    /* properties_destroyed */
 357   0,                                    /* todo_flags_start */
 358   TODO_verify_rtl_sharing               /* todo_flags_finish */
 359  }
 360 };
 361
 362 \f
 363 /* Finalization of the RTL loop passes.  */
 364
 365 static unsigned int
 366 rtl_loop_done (void)
 367 {
 368   /* No longer preserve loops, remove them now.  */
 369   cfun->curr_properties &= ~PROP_loops;
 370   loop_optimizer_finalize ();
 371   free_dominance_info (CDI_DOMINATORS);
 372
 373   cleanup_cfg (0);
 374   if (dump_file)
 375     {
 376       dump_reg_info (dump_file);
 377       dump_flow_info (dump_file, dump_flags);
 378     }
 379
 380   return 0;
 381 }
 382
 383 struct rtl_opt_pass pass_rtl_loop_done =
 384 {
 385  {
 386   RTL_PASS,
 387   "loop2_done",                          /* name */
 388   OPTGROUP_LOOP,                        /* optinfo_flags */
 389   NULL,                                 /* gate */
 390   rtl_loop_done,                        /* execute */
 391   NULL,                                 /* sub */
 392   NULL,                                 /* next */
 393   0,                                    /* static_pass_number */
 394   TV_LOOP,                              /* tv_id */
 395   0,                                    /* properties_required */
 396   0,                                    /* properties_provided */
 397   PROP_loops,                           /* properties_destroyed */
 398   0,                                    /* todo_flags_start */
 399   TODO_verify_flow
 400     | TODO_verify_rtl_sharing           /* todo_flags_finish */
 401  }
 402 };
 403
 404 \f
 405 /* Loop invariant code motion.  */
 406 static bool
 407 gate_rtl_move_loop_invariants (void)
 408 {
 409   return flag_move_loop_invariants;
 410 }
 411
 412 static unsigned int
 413 rtl_move_loop_invariants (void)
 414 {
 415   if (number_of_loops () > 1)
 416     move_loop_invariants ();
 417   return 0;
 418 }
 419
 420 struct rtl_opt_pass pass_rtl_move_loop_invariants =
 421 {
 422  {
 423   RTL_PASS,
 424   "loop2_invariant",                    /* name */
 425   OPTGROUP_LOOP,                        /* optinfo_flags */
 426   gate_rtl_move_loop_invariants,        /* gate */
 427   rtl_move_loop_invariants,             /* execute */
 428   NULL,                                 /* sub */
 429   NULL,                                 /* next */
 430   0,                                    /* static_pass_number */
 431   TV_LOOP_MOVE_INVARIANTS,              /* tv_id */
 432   0,                                    /* properties_required */
 433   0,                                    /* properties_provided */
 434   0,                                    /* properties_destroyed */
 435   0,                                    /* todo_flags_start */
 436   TODO_df_verify |
 437   TODO_df_finish | TODO_verify_rtl_sharing  /* todo_flags_finish */
 438  }
 439 };
 440
 441 \f
 442 /* Loop unswitching for RTL.  */
 443 static bool
 444 gate_rtl_unswitch (void)
 445 {
 446   return flag_unswitch_loops;
 447 }
 448
 449 static unsigned int
 450 rtl_unswitch (void)
 451 {
 452   if (number_of_loops () > 1)
 453     unswitch_loops ();
 454   return 0;
 455 }
 456
 457 struct rtl_opt_pass pass_rtl_unswitch =
 458 {
 459  {
 460   RTL_PASS,
 461   "loop2_unswitch",                      /* name */
 462   OPTGROUP_LOOP,                        /* optinfo_flags */
 463   gate_rtl_unswitch,                    /* gate */
 464   rtl_unswitch,                         /* execute */
 465   NULL,                                 /* sub */
 466   NULL,                                 /* next */
 467   0,                                    /* static_pass_number */
 468   TV_LOOP_UNSWITCH,                     /* tv_id */
 469   0,                                    /* properties_required */
 470   0,                                    /* properties_provided */
 471   0,                                    /* properties_destroyed */
 472   0,                                    /* todo_flags_start */
 473   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 474  }
 475 };
 476
 477 \f
 478 /* Loop unswitching for RTL.  */
 479 static bool
 480 gate_rtl_unroll_and_peel_loops (void)
 481 {
 482   return (flag_peel_loops || flag_unroll_loops || flag_unroll_all_loops);
 483 }
 484
 485 static unsigned int
 486 rtl_unroll_and_peel_loops (void)
 487 {
 488   if (number_of_loops () > 1)
 489     {
 490       int flags = 0;
 491       if (dump_file)
 492         df_dump (dump_file);
 493
 494       if (flag_peel_loops)
 495         flags |= UAP_PEEL;
 496       if (flag_unroll_loops)
 497         flags |= UAP_UNROLL;
 498       if (flag_unroll_all_loops)
 499         flags |= UAP_UNROLL_ALL;
 500
 501       unroll_and_peel_loops (flags);
 502     }
 503   return 0;
 504 }
 505
 506 struct rtl_opt_pass pass_rtl_unroll_and_peel_loops =
 507 {
 508  {
 509   RTL_PASS,
 510   "loop2_unroll",                        /* name */
 511   OPTGROUP_LOOP,                        /* optinfo_flags */
 512   gate_rtl_unroll_and_peel_loops,       /* gate */
 513   rtl_unroll_and_peel_loops,            /* execute */
 514   NULL,                                 /* sub */
 515   NULL,                                 /* next */
 516   0,                                    /* static_pass_number */
 517   TV_LOOP_UNROLL,                       /* tv_id */
 518   0,                                    /* properties_required */
 519   0,                                    /* properties_provided */
 520   0,                                    /* properties_destroyed */
 521   0,                                    /* todo_flags_start */
 522   TODO_verify_rtl_sharing,              /* todo_flags_finish */
 523  }
 524 };
 525
 526 \f
 527 /* The doloop optimization.  */
 528 static bool
 529 gate_rtl_doloop (void)
 530 {
 531 #ifdef HAVE_doloop_end
 532   return (flag_branch_on_count_reg && HAVE_doloop_end);
 533 #else
 534   return 0;
 535 #endif
 536 }
 537
 538 static unsigned int
 539 rtl_doloop (void)
 540 {
 541 #ifdef HAVE_doloop_end
 542   if (number_of_loops () > 1)
 543     doloop_optimize_loops ();
 544 #endif
 545   return 0;
 546 }
 547
 548 struct rtl_opt_pass pass_rtl_doloop =
 549 {
 550  {
 551   RTL_PASS,
 552   "loop2_doloop",                        /* name */
 553   OPTGROUP_LOOP,                        /* optinfo_flags */
 554   gate_rtl_doloop,                      /* gate */
 555   rtl_doloop,                           /* execute */
 556   NULL,                                 /* sub */
 557   NULL,                                 /* next */
 558   0,                                    /* static_pass_number */
 559   TV_LOOP_DOLOOP,                       /* tv_id */
 560   0,                                    /* properties_required */
 561   0,                                    /* properties_provided */
 562   0,                                    /* properties_destroyed */
 563   0,                                    /* todo_flags_start */
 564   TODO_verify_rtl_sharing               /* todo_flags_finish */
 565  }
 566 };