gcc/cfgloopmanip.c

   1 /* Loop manipulation code for GNU compiler.
   2    Copyright (C) 2002, 2003 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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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 "basic-block.h"
  28 #include "cfgloop.h"
  29 #include "cfglayout.h"
  30 #include "output.h"
  31
  32 static struct loop * duplicate_loop (struct loops *, struct loop *,
  33                                      struct loop *);
  34 static void duplicate_subloops (struct loops *, struct loop *, struct loop *);
  35 static void copy_loops_to (struct loops *, struct loop **, int,
  36                            struct loop *);
  37 static void loop_redirect_edge (edge, basic_block);
  38 static bool loop_delete_branch_edge (edge, int);
  39 static void remove_bbs (dominance_info, basic_block *, int);
  40 static bool rpe_enum_p (basic_block, void *);
  41 static int find_path (edge, dominance_info, basic_block **);
  42 static bool alp_enum_p (basic_block, void *);
  43 static void add_loop (struct loops *, struct loop *);
  44 static void fix_loop_placements (struct loop *);
  45 static bool fix_bb_placement (struct loops *, basic_block);
  46 static void fix_bb_placements (struct loops *, basic_block);
  47 static void place_new_loop (struct loops *, struct loop *);
  48 static void scale_loop_frequencies (struct loop *, int, int);
  49 static void scale_bbs_frequencies (basic_block *, int, int, int);
  50 static basic_block create_preheader (struct loop *, dominance_info, int);
  51 static void fix_irreducible_loops (basic_block);
  52
  53 /* Splits basic block BB after INSN, returns created edge.  Updates loops
  54    and dominators.  */
  55 edge
  56 split_loop_bb (struct loops *loops, basic_block bb, rtx insn)
  57 {
  58   edge e;
  59   basic_block *dom_bbs;
  60   int n_dom_bbs, i;
  61
  62   /* Split the block.  */
  63   e = split_block (bb, insn);
  64
  65   /* Add dest to loop.  */
  66   add_bb_to_loop (e->dest, e->src->loop_father);
  67
  68   /* Fix dominators.  */
  69   add_to_dominance_info (loops->cfg.dom, e->dest);
  70   n_dom_bbs = get_dominated_by (loops->cfg.dom, e->src, &dom_bbs);
  71   for (i = 0; i < n_dom_bbs; i++)
  72     set_immediate_dominator (loops->cfg.dom, dom_bbs[i], e->dest);
  73   free (dom_bbs);
  74   set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
  75
  76   return e;
  77 }
  78
  79 /* Checks whether basic block BB is dominated by RPE->DOM, where
  80    RPE is passed through DATA.  */
  81 struct rpe_data
  82  {
  83    basic_block dom;
  84    dominance_info doms;
  85  };
  86
  87 static bool
  88 rpe_enum_p (basic_block bb, void *data)
  89 {
  90   struct rpe_data *rpe = data;
  91   return dominated_by_p (rpe->doms, bb, rpe->dom);
  92 }
  93
  94 /* Remove basic blocks BBS from loop structure and dominance info,
  95    and delete them afterwards.  */
  96 static void
  97 remove_bbs (dominance_info dom, basic_block *bbs, int nbbs)
  98 {
  99   int i;
 100
 101   for (i = 0; i < nbbs; i++)
 102     {
 103       remove_bb_from_loops (bbs[i]);
 104       delete_from_dominance_info (dom, bbs[i]);
 105       delete_block (bbs[i]);
 106     }
 107 }
 108
 109 /* Find path -- i.e. the basic blocks dominated by edge E and put them
 110    into array BBS, that will be allocated large enough to contain them.
 111    E->dest must have exactly one predecessor for this to work (it is
 112    easy to achieve and we do not put it here because we do not want to
 113    alter anything by this function).  The number of basic blocks in the
 114    path is returned.  */
 115 static int
 116 find_path (edge e, dominance_info doms, basic_block **bbs)
 117 {
 118   struct rpe_data rpe;
 119
 120   if (e->dest->pred->pred_next)
 121     abort ();
 122
 123   /* Find bbs in the path.  */
 124   rpe.dom = e->dest;
 125   rpe.doms = doms;
 126   *bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 127   return dfs_enumerate_from (e->dest, 0, rpe_enum_p, *bbs,
 128                              n_basic_blocks, &rpe);
 129 }
 130
 131 /* Fix placement of basic block BB inside loop hierarchy stored in LOOPS --
 132    Let L be a loop to that BB belongs.  Then every successor of BB must either
 133      1) belong to some superloop of loop L, or
 134      2) be a header of loop K such that K->outer is superloop of L
 135    Returns true if we had to move BB into other loop to enforce this condition,
 136    false if the placement of BB was already correct (provided that placements
 137    of its successors are correct).  */
 138 static bool
 139 fix_bb_placement (struct loops *loops, basic_block bb)
 140 {
 141   edge e;
 142   struct loop *loop = loops->tree_root, *act;
 143
 144   for (e = bb->succ; e; e = e->succ_next)
 145     {
 146       if (e->dest == EXIT_BLOCK_PTR)
 147         continue;
 148
 149       act = e->dest->loop_father;
 150       if (act->header == e->dest)
 151         act = act->outer;
 152
 153       if (flow_loop_nested_p (loop, act))
 154         loop = act;
 155     }
 156
 157   if (loop == bb->loop_father)
 158     return false;
 159
 160   remove_bb_from_loops (bb);
 161   add_bb_to_loop (bb, loop);
 162
 163   return true;
 164 }
 165
 166 /* Fix placements of basic blocks inside loop hierarchy stored in loops; i.e.
 167    enforce condition condition stated in description of fix_bb_placement. We
 168    start from basic block FROM that had some of its successors removed, so that
 169    his placement no longer has to be correct, and iteratively fix placement of
 170    its predecessors that may change if placement of FROM changed.  Also fix
 171    placement of subloops of FROM->loop_father, that might also be altered due
 172    to this change; the condition for them is similar, except that instead of
 173    successors we consider edges coming out of the loops.  */
 174 static void
 175 fix_bb_placements (struct loops *loops, basic_block from)
 176 {
 177   sbitmap in_queue;
 178   basic_block *queue, *qtop, *qbeg, *qend;
 179   struct loop *base_loop;
 180   edge e;
 181
 182   /* We pass through blocks back-reachable from FROM, testing whether some
 183      of their successors moved to outer loop.  It may be necessary to
 184      iterate several times, but it is finite, as we stop unless we move
 185      the basic block up the loop structure.  The whole story is a bit
 186      more complicated due to presence of subloops, those are moved using
 187      fix_loop_placement.  */
 188
 189   base_loop = from->loop_father;
 190   if (base_loop == loops->tree_root)
 191     return;
 192
 193   in_queue = sbitmap_alloc (last_basic_block);
 194   sbitmap_zero (in_queue);
 195   SET_BIT (in_queue, from->index);
 196   /* Prevent us from going out of the base_loop.  */
 197   SET_BIT (in_queue, base_loop->header->index);
 198
 199   queue = xmalloc ((base_loop->num_nodes + 1) * sizeof (basic_block));
 200   qtop = queue + base_loop->num_nodes + 1;
 201   qbeg = queue;
 202   qend = queue + 1;
 203   *qbeg = from;
 204
 205   while (qbeg != qend)
 206     {
 207       from = *qbeg;
 208       qbeg++;
 209       if (qbeg == qtop)
 210         qbeg = queue;
 211       RESET_BIT (in_queue, from->index);
 212
 213       if (from->loop_father->header == from)
 214         {
 215           /* Subloop header, maybe move the loop upward.  */
 216           if (!fix_loop_placement (from->loop_father))
 217             continue;
 218         }
 219       else
 220         {
 221           /* Ordinary basic block.  */
 222           if (!fix_bb_placement (loops, from))
 223             continue;
 224         }
 225
 226       /* Something has changed, insert predecessors into queue.  */
 227       for (e = from->pred; e; e = e->pred_next)
 228         {
 229           basic_block pred = e->src;
 230           struct loop *nca;
 231
 232           if (TEST_BIT (in_queue, pred->index))
 233             continue;
 234
 235           /* If it is subloop, then it either was not moved, or
 236              the path up the loop tree from base_loop do not contain
 237              it.  */
 238           nca = find_common_loop (pred->loop_father, base_loop);
 239           if (pred->loop_father != base_loop
 240               && (nca == base_loop
 241                   || nca != pred->loop_father))
 242             pred = pred->loop_father->header;
 243           else if (!flow_loop_nested_p (from->loop_father, pred->loop_father))
 244             {
 245               /* No point in processing it.  */
 246               continue;
 247             }
 248
 249           if (TEST_BIT (in_queue, pred->index))
 250             continue;
 251
 252           /* Schedule the basic block.  */
 253           *qend = pred;
 254           qend++;
 255           if (qend == qtop)
 256             qend = queue;
 257           SET_BIT (in_queue, pred->index);
 258         }
 259     }
 260   free (in_queue);
 261   free (queue);
 262 }
 263
 264 /* Basic block from has lost one or more of its predecessors, so it might
 265    mo longer be part irreducible loop.  Fix it and proceed recursively
 266    for its successors if needed.  */
 267 static void
 268 fix_irreducible_loops (basic_block from)
 269 {
 270   basic_block bb;
 271   basic_block *stack;
 272   int stack_top;
 273   sbitmap on_stack;
 274   edge *edges, e;
 275   unsigned n_edges, i;
 276
 277   if (!(from->flags & BB_IRREDUCIBLE_LOOP))
 278     return;
 279
 280   on_stack = sbitmap_alloc (last_basic_block);
 281   sbitmap_zero (on_stack);
 282   SET_BIT (on_stack, from->index);
 283   stack = xmalloc (from->loop_father->num_nodes * sizeof (basic_block));
 284   stack[0] = from;
 285   stack_top = 1;
 286
 287   while (stack_top)
 288     {
 289       bb = stack[--stack_top];
 290       RESET_BIT (on_stack, bb->index);
 291
 292       for (e = bb->pred; e; e = e->pred_next)
 293         if (e->flags & EDGE_IRREDUCIBLE_LOOP)
 294           break;
 295       if (e)
 296         continue;
 297
 298       bb->flags &= ~BB_IRREDUCIBLE_LOOP;
 299       if (bb->loop_father->header == bb)
 300         edges = get_loop_exit_edges (bb->loop_father, &n_edges);
 301       else
 302         {
 303           n_edges = 0;
 304           for (e = bb->succ; e; e = e->succ_next)
 305             n_edges++;
 306           edges = xmalloc (n_edges * sizeof (edge));
 307           n_edges = 0;
 308           for (e = bb->succ; e; e = e->succ_next)
 309             edges[n_edges++] = e;
 310         }
 311
 312       for (i = 0; i < n_edges; i++)
 313         if (e->flags & EDGE_IRREDUCIBLE_LOOP)
 314           {
 315             if (!flow_bb_inside_loop_p (from->loop_father, e->dest))
 316               continue;
 317
 318             e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 319             if (TEST_BIT (on_stack, e->dest->index))
 320               continue;
 321
 322             SET_BIT (on_stack, e->dest->index);
 323             stack[stack_top++] = e->dest;
 324           }
 325       free (edges);
 326     }
 327
 328   free (on_stack);
 329   free (stack);
 330 }
 331
 332 /* Removes path beginning at edge E, i.e. remove basic blocks dominated by E
 333    and update loop structure stored in LOOPS and dominators.  Return true if
 334    we were able to remove the path, false otherwise (and nothing is affected
 335    then).  */
 336 bool
 337 remove_path (struct loops *loops, edge e)
 338 {
 339   edge ae;
 340   basic_block *rem_bbs, *bord_bbs, *dom_bbs, from, bb;
 341   int i, nrem, n_bord_bbs, n_dom_bbs;
 342   sbitmap seen;
 343
 344   if (!loop_delete_branch_edge (e, 0))
 345     return false;
 346
 347   /* We need to check whether basic blocks are dominated by the edge
 348      e, but we only have basic block dominators.  This is easy to
 349      fix -- when e->dest has exactly one predecessor, this corresponds
 350      to blocks dominated by e->dest, if not, split the edge.  */
 351   if (e->dest->pred->pred_next)
 352     e = loop_split_edge_with (e, NULL_RTX, loops)->pred;
 353
 354   /* It may happen that by removing path we remove one or more loops
 355      we belong to.  In this case first unloop the loops, then proceed
 356      normally.   We may assume that e->dest is not a header of any loop,
 357      as it now has exactly one predecessor.  */
 358   while (e->src->loop_father->outer
 359          && dominated_by_p (loops->cfg.dom,
 360                             e->src->loop_father->latch, e->dest))
 361     unloop (loops, e->src->loop_father);
 362
 363   /* Identify the path.  */
 364   nrem = find_path (e, loops->cfg.dom, &rem_bbs);
 365
 366   n_bord_bbs = 0;
 367   bord_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 368   seen = sbitmap_alloc (last_basic_block);
 369   sbitmap_zero (seen);
 370
 371   /* Find "border" hexes -- i.e. those with predecessor in removed path.  */
 372   for (i = 0; i < nrem; i++)
 373     SET_BIT (seen, rem_bbs[i]->index);
 374   for (i = 0; i < nrem; i++)
 375     {
 376       bb = rem_bbs[i];
 377       for (ae = rem_bbs[i]->succ; ae; ae = ae->succ_next)
 378         if (ae->dest != EXIT_BLOCK_PTR && !TEST_BIT (seen, ae->dest->index))
 379           {
 380             SET_BIT (seen, ae->dest->index);
 381             bord_bbs[n_bord_bbs++] = ae->dest;
 382           }
 383     }
 384
 385   /* Remove the path.  */
 386   from = e->src;
 387   if (!loop_delete_branch_edge (e, 1))
 388     abort ();
 389   dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 390
 391   /* Cancel loops contained in the path.  */
 392   for (i = 0; i < nrem; i++)
 393     if (rem_bbs[i]->loop_father->header == rem_bbs[i])
 394       cancel_loop_tree (loops, rem_bbs[i]->loop_father);
 395
 396   remove_bbs (loops->cfg.dom, rem_bbs, nrem);
 397   free (rem_bbs);
 398
 399   /* Find blocks whose dominators may be affected.  */
 400   n_dom_bbs = 0;
 401   sbitmap_zero (seen);
 402   for (i = 0; i < n_bord_bbs; i++)
 403     {
 404       int j, nldom;
 405       basic_block *ldom;
 406
 407       bb = get_immediate_dominator (loops->cfg.dom, bord_bbs[i]);
 408       if (TEST_BIT (seen, bb->index))
 409         continue;
 410       SET_BIT (seen, bb->index);
 411
 412       nldom = get_dominated_by (loops->cfg.dom, bb, &ldom);
 413       for (j = 0; j < nldom; j++)
 414         if (!dominated_by_p (loops->cfg.dom, from, ldom[j]))
 415           dom_bbs[n_dom_bbs++] = ldom[j];
 416       free(ldom);
 417     }
 418
 419   free (seen);
 420
 421   /* Recount dominators.  */
 422   iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
 423   free (dom_bbs);
 424
 425   /* These blocks have lost some predecessor(s), thus their irreducible
 426      status could be changed.  */
 427   for (i = 0; i < n_bord_bbs; i++)
 428     fix_irreducible_loops (bord_bbs[i]);
 429   free (bord_bbs);
 430
 431   /* Fix placements of basic blocks inside loops and the placement of
 432      loops in the loop tree.  */
 433   fix_bb_placements (loops, from);
 434   fix_loop_placements (from->loop_father);
 435
 436   return true;
 437 }
 438
 439 /* Predicate for enumeration in add_loop.  */
 440 static bool
 441 alp_enum_p (basic_block bb, void *alp_header)
 442 {
 443   return bb != (basic_block) alp_header;
 444 }
 445
 446 /* Given LOOP structure with filled header and latch, find the body of the
 447    corresponding loop and add it to LOOPS tree.  */
 448 static void
 449 add_loop (struct loops *loops, struct loop *loop)
 450 {
 451   basic_block *bbs;
 452   int i, n;
 453
 454   /* Add it to loop structure.  */
 455   place_new_loop (loops, loop);
 456   loop->level = 1;
 457
 458   /* Find its nodes.  */
 459   bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 460   n = dfs_enumerate_from (loop->latch, 1, alp_enum_p,
 461                           bbs, n_basic_blocks, loop->header);
 462
 463   for (i = 0; i < n; i++)
 464     add_bb_to_loop (bbs[i], loop);
 465   add_bb_to_loop (loop->header, loop);
 466
 467   free (bbs);
 468 }
 469
 470 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
 471    by NUM/DEN.  */
 472 static void
 473 scale_bbs_frequencies (basic_block *bbs, int nbbs, int num, int den)
 474 {
 475   int i;
 476   edge e;
 477
 478   for (i = 0; i < nbbs; i++)
 479     {
 480       bbs[i]->frequency = (bbs[i]->frequency * num) / den;
 481       bbs[i]->count = (bbs[i]->count * num) / den;
 482       for (e = bbs[i]->succ; e; e = e->succ_next)
 483         e->count = (e->count * num) /den;
 484     }
 485 }
 486
 487 /* Multiply all frequencies in LOOP by NUM/DEN.  */
 488 static void
 489 scale_loop_frequencies (struct loop *loop, int num, int den)
 490 {
 491   basic_block *bbs;
 492
 493   bbs = get_loop_body (loop);
 494   scale_bbs_frequencies (bbs, loop->num_nodes, num, den);
 495   free (bbs);
 496 }
 497
 498 /* Make area between HEADER_EDGE and LATCH_EDGE a loop by connecting
 499    latch to header and update loop tree stored in LOOPS and dominators
 500    accordingly. Everything between them plus LATCH_EDGE destination must
 501    be dominated by HEADER_EDGE destination, and back-reachable from
 502    LATCH_EDGE source.  HEADER_EDGE is redirected to basic block SWITCH_BB,
 503    SWITCH_BB->succ to original destination of LATCH_EDGE and
 504    SWITCH_BB->succ->succ_next to original destination of HEADER_EDGE.
 505    Returns newly created loop.  */
 506 struct loop *
 507 loopify (struct loops *loops, edge latch_edge, edge header_edge, basic_block switch_bb)
 508 {
 509   basic_block succ_bb = latch_edge->dest;
 510   basic_block pred_bb = header_edge->src;
 511   basic_block *dom_bbs, *body;
 512   unsigned n_dom_bbs, i, j;
 513   sbitmap seen;
 514   struct loop *loop = xcalloc (1, sizeof (struct loop));
 515   struct loop *outer = succ_bb->loop_father->outer;
 516   int freq, prob, tot_prob;
 517   gcov_type cnt;
 518   edge e;
 519
 520   loop->header = header_edge->dest;
 521   loop->latch = latch_edge->src;
 522
 523   freq = EDGE_FREQUENCY (header_edge);
 524   cnt = header_edge->count;
 525   prob = switch_bb->succ->probability;
 526   tot_prob = prob + switch_bb->succ->succ_next->probability;
 527   if (tot_prob == 0)
 528     tot_prob = 1;
 529
 530   /* Redirect edges.  */
 531   loop_redirect_edge (latch_edge, loop->header);
 532   loop_redirect_edge (header_edge, switch_bb);
 533   loop_redirect_edge (switch_bb->succ->succ_next, loop->header);
 534   loop_redirect_edge (switch_bb->succ, succ_bb);
 535
 536   /* Update dominators.  */
 537   set_immediate_dominator (loops->cfg.dom, switch_bb, pred_bb);
 538   set_immediate_dominator (loops->cfg.dom, loop->header, switch_bb);
 539   set_immediate_dominator (loops->cfg.dom, succ_bb, switch_bb);
 540
 541   /* Compute new loop.  */
 542   add_loop (loops, loop);
 543   flow_loop_tree_node_add (outer, loop);
 544
 545   /* Add switch_bb to appropriate loop.  */
 546   add_bb_to_loop (switch_bb, outer);
 547
 548   /* Fix frequencies.  */
 549   switch_bb->frequency = freq;
 550   switch_bb->count = cnt;
 551   for (e = switch_bb->succ; e; e = e->succ_next)
 552     e->count = (switch_bb->count * e->probability) / REG_BR_PROB_BASE;
 553   scale_loop_frequencies (loop, prob, tot_prob);
 554   scale_loop_frequencies (succ_bb->loop_father, tot_prob - prob, tot_prob);
 555
 556   /* Update dominators of blocks outside of LOOP.  */
 557   dom_bbs = xcalloc (n_basic_blocks, sizeof (basic_block));
 558   n_dom_bbs = 0;
 559   seen = sbitmap_alloc (last_basic_block);
 560   sbitmap_zero (seen);
 561   body = get_loop_body (loop);
 562
 563   for (i = 0; i < loop->num_nodes; i++)
 564     SET_BIT (seen, body[i]->index);
 565
 566   for (i = 0; i < loop->num_nodes; i++)
 567     {
 568       unsigned nldom;
 569       basic_block *ldom;
 570
 571       nldom = get_dominated_by (loops->cfg.dom, body[i], &ldom);
 572       for (j = 0; j < nldom; j++)
 573         if (!TEST_BIT (seen, ldom[j]->index))
 574           {
 575             SET_BIT (seen, ldom[j]->index);
 576             dom_bbs[n_dom_bbs++] = ldom[j];
 577           }
 578       free (ldom);
 579     }
 580
 581   iterate_fix_dominators (loops->cfg.dom, dom_bbs, n_dom_bbs);
 582
 583   free (body);
 584   free (seen);
 585   free (dom_bbs);
 586
 587   return loop;
 588 }
 589
 590 /* Remove the latch edge of a LOOP and update LOOPS tree to indicate that
 591    the LOOP was removed.  After this function, original loop latch will
 592    have no successor, which caller is expected to fix somehow.  */
 593 void
 594 unloop (struct loops *loops, struct loop *loop)
 595 {
 596   basic_block *body;
 597   struct loop *ploop;
 598   unsigned i, n;
 599   basic_block latch = loop->latch;
 600   edge *edges;
 601   unsigned n_edges;
 602
 603   /* This is relatively straightforward.  The dominators are unchanged, as
 604      loop header dominates loop latch, so the only thing we have to care of
 605      is the placement of loops and basic blocks inside the loop tree.  We
 606      move them all to the loop->outer, and then let fix_bb_placements do
 607      its work.  */
 608
 609   body = get_loop_body (loop);
 610   edges = get_loop_exit_edges (loop, &n_edges);
 611   n = loop->num_nodes;
 612   for (i = 0; i < n; i++)
 613     if (body[i]->loop_father == loop)
 614       {
 615         remove_bb_from_loops (body[i]);
 616         add_bb_to_loop (body[i], loop->outer);
 617       }
 618   free(body);
 619
 620   while (loop->inner)
 621     {
 622       ploop = loop->inner;
 623       flow_loop_tree_node_remove (ploop);
 624       flow_loop_tree_node_add (loop->outer, ploop);
 625     }
 626
 627   /* Remove the loop and free its data.  */
 628   flow_loop_tree_node_remove (loop);
 629   loops->parray[loop->num] = NULL;
 630   flow_loop_free (loop);
 631
 632   remove_edge (latch->succ);
 633   fix_bb_placements (loops, latch);
 634
 635   /* If the loop was inside an irreducible region, we would have to somehow
 636      update the irreducible marks inside its body.  While it is certainly
 637      possible to do, it is a bit complicated and this situation should be
 638      very rare, so we just remark all loops in this case.  */
 639   for (i = 0; i < n_edges; i++)
 640     if (edges[i]->flags & EDGE_IRREDUCIBLE_LOOP)
 641       break;
 642   if (i != n_edges)
 643     mark_irreducible_loops (loops);
 644   free (edges);
 645 }
 646
 647 /* Fix placement of LOOP inside loop tree, i.e. find the innermost superloop
 648    FATHER of LOOP such that all of the edges comming out of LOOP belong to
 649    FATHER, and set it as outer loop of LOOP.  Return 1 if placement of
 650    LOOP changed.  */
 651 int
 652 fix_loop_placement (struct loop *loop)
 653 {
 654   basic_block *body;
 655   unsigned i;
 656   edge e;
 657   struct loop *father = loop->pred[0], *act;
 658
 659   body = get_loop_body (loop);
 660   for (i = 0; i < loop->num_nodes; i++)
 661     for (e = body[i]->succ; e; e = e->succ_next)
 662       if (!flow_bb_inside_loop_p (loop, e->dest))
 663         {
 664           act = find_common_loop (loop, e->dest->loop_father);
 665           if (flow_loop_nested_p (father, act))
 666             father = act;
 667         }
 668   free (body);
 669
 670   if (father != loop->outer)
 671     {
 672       for (act = loop->outer; act != father; act = act->outer)
 673         act->num_nodes -= loop->num_nodes;
 674       flow_loop_tree_node_remove (loop);
 675       flow_loop_tree_node_add (father, loop);
 676       return 1;
 677     }
 678   return 0;
 679 }
 680
 681 /* Fix placement of superloops of LOOP inside loop tree, i.e. ensure that
 682    condition stated in description of fix_loop_placement holds for them.
 683    It is used in case when we removed some edges coming out of LOOP, which
 684    may cause the right placement of LOOP inside loop tree to change.  */
 685 static void
 686 fix_loop_placements (struct loop *loop)
 687 {
 688   struct loop *outer;
 689
 690   while (loop->outer)
 691     {
 692       outer = loop->outer;
 693       if (!fix_loop_placement (loop))
 694         break;
 695       loop = outer;
 696     }
 697 }
 698
 699 /* Creates place for a new LOOP in LOOPS structure.  */
 700 static void
 701 place_new_loop (struct loops *loops, struct loop *loop)
 702 {
 703   loops->parray =
 704     xrealloc (loops->parray, (loops->num + 1) * sizeof (struct loop *));
 705   loops->parray[loops->num] = loop;
 706
 707   loop->num = loops->num++;
 708 }
 709
 710 /* Copies copy of LOOP as subloop of TARGET loop, placing newly
 711    created loop into LOOPS structure.  */
 712 static struct loop *
 713 duplicate_loop (struct loops *loops, struct loop *loop, struct loop *target)
 714 {
 715   struct loop *cloop;
 716   cloop = xcalloc (1, sizeof (struct loop));
 717   place_new_loop (loops, cloop);
 718
 719   /* Initialize copied loop.  */
 720   cloop->level = loop->level;
 721
 722   /* Set it as copy of loop.  */
 723   loop->copy = cloop;
 724
 725   /* Add it to target.  */
 726   flow_loop_tree_node_add (target, cloop);
 727
 728   return cloop;
 729 }
 730
 731 /* Copies structure of subloops of LOOP into TARGET loop, placing
 732    newly created loops into loop tree stored in LOOPS.  */
 733 static void
 734 duplicate_subloops (struct loops *loops, struct loop *loop, struct loop *target)
 735 {
 736   struct loop *aloop, *cloop;
 737
 738   for (aloop = loop->inner; aloop; aloop = aloop->next)
 739     {
 740       cloop = duplicate_loop (loops, aloop, target);
 741       duplicate_subloops (loops, aloop, cloop);
 742     }
 743 }
 744
 745 /* Copies structure of subloops of N loops, stored in array COPIED_LOOPS,
 746    into TARGET loop, placing newly created loops into loop tree LOOPS.  */
 747 static void
 748 copy_loops_to (struct loops *loops, struct loop **copied_loops, int n, struct loop *target)
 749 {
 750   struct loop *aloop;
 751   int i;
 752
 753   for (i = 0; i < n; i++)
 754     {
 755       aloop = duplicate_loop (loops, copied_loops[i], target);
 756       duplicate_subloops (loops, copied_loops[i], aloop);
 757     }
 758 }
 759
 760 /* Redirects edge E to basic block DEST.  */
 761 static void
 762 loop_redirect_edge (edge e, basic_block dest)
 763 {
 764   if (e->dest == dest)
 765     return;
 766
 767   redirect_edge_and_branch_force (e, dest);
 768 }
 769
 770 /* Deletes edge E from a branch if possible.  Unless REALLY_DELETE is set,
 771    just test whether it is possible to remove the edge.  */
 772 static bool
 773 loop_delete_branch_edge (edge e, int really_delete)
 774 {
 775   basic_block src = e->src;
 776   int irr;
 777   edge snd;
 778
 779   if (src->succ->succ_next)
 780     {
 781       basic_block newdest;
 782
 783       /* Cannot handle more than two exit edges.  */
 784       if (src->succ->succ_next->succ_next)
 785         return false;
 786       /* And it must be just a simple branch.  */
 787       if (!any_condjump_p (src->end))
 788         return false;
 789
 790       snd = e == src->succ ? src->succ->succ_next : src->succ;
 791       newdest = snd->dest;
 792       if (newdest == EXIT_BLOCK_PTR)
 793         return false;
 794
 795       /* Hopefully the above conditions should suffice.  */
 796       if (!really_delete)
 797         return true;
 798
 799       /* Redirecting behaves wrongly wrto this flag.  */
 800       irr = snd->flags & EDGE_IRREDUCIBLE_LOOP;
 801
 802       if (!redirect_edge_and_branch (e, newdest))
 803         return false;
 804       src->succ->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 805       src->succ->flags |= irr;
 806
 807       return true;
 808     }
 809   else
 810     {
 811       /* Cannot happen -- we are using this only to remove an edge
 812          from branch.  */
 813       abort ();
 814     }
 815
 816   return false;  /* To avoid warning, cannot get here.  */
 817 }
 818
 819 /* Check whether LOOP's body can be duplicated.  */
 820 bool
 821 can_duplicate_loop_p (struct loop *loop)
 822 {
 823   int ret;
 824   basic_block *bbs = get_loop_body (loop);
 825
 826   ret = can_copy_bbs_p (bbs, loop->num_nodes);
 827   free (bbs);
 828
 829   return ret;
 830 }
 831
 832 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
 833
 834 /* Duplicates body of LOOP to given edge E NDUPL times.  Takes care of updating
 835    LOOPS structure and dominators.  E's destination must be LOOP header for
 836    this to work, i.e. it must be entry or latch edge of this loop; these are
 837    unique, as the loops must have preheaders for this function to work
 838    correctly (in case E is latch, the function unrolls the loop, if E is entry
 839    edge, it peels the loop).  Store edges created by copying ORIG edge from
 840    copies corresponding to set bits in WONT_EXIT bitmap (bit 0 corresponds to
 841    original LOOP body, the other copies are numbered in order given by control
 842    flow through them) into TO_REMOVE array.  Returns false if duplication is
 843    impossible.  */
 844 int
 845 duplicate_loop_to_header_edge (struct loop *loop, edge e, struct loops *loops,
 846                                unsigned int ndupl, sbitmap wont_exit,
 847                                edge orig, edge *to_remove,
 848                                unsigned int *n_to_remove, int flags)
 849 {
 850   struct loop *target, *aloop;
 851   struct loop **orig_loops;
 852   unsigned n_orig_loops;
 853   basic_block header = loop->header, latch = loop->latch;
 854   basic_block *new_bbs, *bbs, *first_active;
 855   basic_block new_bb, bb, first_active_latch = NULL;
 856   edge ae, latch_edge;
 857   edge spec_edges[2], new_spec_edges[2];
 858 #define SE_LATCH 0
 859 #define SE_ORIG 1
 860   unsigned i, j, n;
 861   int is_latch = (latch == e->src);
 862   int scale_act = 0, *scale_step = NULL, scale_main = 0;
 863   int p, freq_in, freq_le, freq_out_orig;
 864   int prob_pass_thru, prob_pass_wont_exit, prob_pass_main;
 865   int add_irreducible_flag;
 866
 867   if (e->dest != loop->header)
 868     abort ();
 869   if (ndupl <= 0)
 870     abort ();
 871
 872   if (orig)
 873     {
 874       /* Orig must be edge out of the loop.  */
 875       if (!flow_bb_inside_loop_p (loop, orig->src))
 876         abort ();
 877       if (flow_bb_inside_loop_p (loop, orig->dest))
 878         abort ();
 879     }
 880
 881   bbs = get_loop_body (loop);
 882
 883   /* Check whether duplication is possible.  */
 884   if (!can_copy_bbs_p (bbs, loop->num_nodes))
 885     {
 886       free (bbs);
 887       return false;
 888     }
 889   new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
 890
 891   /* In case we are doing loop peeling and the loop is in the middle of
 892      irreducible region, the peeled copies will be inside it too.  */
 893   add_irreducible_flag = e->flags & EDGE_IRREDUCIBLE_LOOP;
 894   if (is_latch && add_irreducible_flag)
 895     abort ();
 896
 897   /* Find edge from latch.  */
 898   latch_edge = loop_latch_edge (loop);
 899
 900   if (flags & DLTHE_FLAG_UPDATE_FREQ)
 901     {
 902       /* Calculate coefficients by that we have to scale frequencies
 903          of duplicated loop bodies.  */
 904       freq_in = header->frequency;
 905       freq_le = EDGE_FREQUENCY (latch_edge);
 906       if (freq_in == 0)
 907         freq_in = 1;
 908       if (freq_in < freq_le)
 909         freq_in = freq_le;
 910       freq_out_orig = orig ? EDGE_FREQUENCY (orig) : freq_in - freq_le;
 911       if (freq_out_orig > freq_in - freq_le)
 912         freq_out_orig = freq_in - freq_le;
 913       prob_pass_thru = RDIV (REG_BR_PROB_BASE * freq_le, freq_in);
 914       prob_pass_wont_exit =
 915               RDIV (REG_BR_PROB_BASE * (freq_le + freq_out_orig), freq_in);
 916
 917       scale_step = xmalloc (ndupl * sizeof (int));
 918
 919         for (i = 1; i <= ndupl; i++)
 920           scale_step[i - 1] = TEST_BIT (wont_exit, i)
 921                                 ? prob_pass_wont_exit
 922                                 : prob_pass_thru;
 923
 924       if (is_latch)
 925         {
 926           prob_pass_main = TEST_BIT (wont_exit, 0)
 927                                 ? prob_pass_wont_exit
 928                                 : prob_pass_thru;
 929           p = prob_pass_main;
 930           scale_main = REG_BR_PROB_BASE;
 931           for (i = 0; i < ndupl; i++)
 932             {
 933               scale_main += p;
 934               p = RDIV (p * scale_step[i], REG_BR_PROB_BASE);
 935             }
 936           scale_main = RDIV (REG_BR_PROB_BASE * REG_BR_PROB_BASE, scale_main);
 937           scale_act = RDIV (scale_main * prob_pass_main, REG_BR_PROB_BASE);
 938         }
 939       else
 940         {
 941           scale_main = REG_BR_PROB_BASE;
 942           for (i = 0; i < ndupl; i++)
 943             scale_main = RDIV (scale_main * scale_step[i], REG_BR_PROB_BASE);
 944           scale_act = REG_BR_PROB_BASE - prob_pass_thru;
 945         }
 946       for (i = 0; i < ndupl; i++)
 947         if (scale_step[i] < 0 || scale_step[i] > REG_BR_PROB_BASE)
 948           abort ();
 949       if (scale_main < 0 || scale_main > REG_BR_PROB_BASE
 950           || scale_act < 0  || scale_act > REG_BR_PROB_BASE)
 951         abort ();
 952     }
 953
 954   /* Loop the new bbs will belong to.  */
 955   target = e->src->loop_father;
 956
 957   /* Original loops.  */
 958   n_orig_loops = 0;
 959   for (aloop = loop->inner; aloop; aloop = aloop->next)
 960     n_orig_loops++;
 961   orig_loops = xcalloc (n_orig_loops, sizeof (struct loop *));
 962   for (aloop = loop->inner, i = 0; aloop; aloop = aloop->next, i++)
 963     orig_loops[i] = aloop;
 964
 965   loop->copy = target;
 966
 967   n = loop->num_nodes;
 968
 969   first_active = xmalloc (n * sizeof (basic_block));
 970   if (is_latch)
 971     {
 972       memcpy (first_active, bbs, n * sizeof (basic_block));
 973       first_active_latch = latch;
 974     }
 975
 976   /* Record exit edge in original loop body.  */
 977   if (orig && TEST_BIT (wont_exit, 0))
 978     to_remove[(*n_to_remove)++] = orig;
 979
 980   spec_edges[SE_ORIG] = orig;
 981   spec_edges[SE_LATCH] = latch_edge;
 982
 983   for (j = 0; j < ndupl; j++)
 984     {
 985       /* Copy loops.  */
 986       copy_loops_to (loops, orig_loops, n_orig_loops, target);
 987
 988       /* Copy bbs.  */
 989       copy_bbs (bbs, n, new_bbs, spec_edges, 2, new_spec_edges, loop, loops);
 990
 991       /* Note whether the blocks and edges belong to an irreducible loop.  */
 992       if (add_irreducible_flag)
 993         {
 994           for (i = 0; i < n; i++)
 995             new_bbs[i]->rbi->duplicated = 1;
 996           for (i = 0; i < n; i++)
 997             {
 998               new_bb = new_bbs[i];
 999               if (new_bb->loop_father == target)
1000                 new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1001
1002               for (ae = new_bb->succ; ae; ae = ae->succ_next)
1003                 if (ae->dest->rbi->duplicated
1004                     && (ae->src->loop_father == target
1005                         || ae->dest->loop_father == target))
1006                   ae->flags |= EDGE_IRREDUCIBLE_LOOP;
1007             }
1008           for (i = 0; i < n; i++)
1009             new_bbs[i]->rbi->duplicated = 0;
1010         }
1011
1012       /* Redirect the special edges.  */
1013       if (is_latch)
1014         {
1015           redirect_edge_and_branch_force (latch_edge, new_bbs[0]);
1016           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1017                                           loop->header);
1018           set_immediate_dominator (loops->cfg.dom, new_bbs[0], latch);
1019           latch = loop->latch = new_bbs[1];
1020           e = latch_edge = new_spec_edges[SE_LATCH];
1021         }
1022       else
1023         {
1024           redirect_edge_and_branch_force (new_spec_edges[SE_LATCH],
1025                                           loop->header);
1026           redirect_edge_and_branch_force (e, new_bbs[0]);
1027           set_immediate_dominator (loops->cfg.dom, new_bbs[0], e->src);
1028           e = new_spec_edges[SE_LATCH];
1029         }
1030
1031       /* Record exit edge in this copy.  */
1032       if (orig && TEST_BIT (wont_exit, j + 1))
1033         to_remove[(*n_to_remove)++] = new_spec_edges[SE_ORIG];
1034
1035       /* Record the first copy in the control flow order if it is not
1036          the original loop (i.e. in case of peeling).  */
1037       if (!first_active_latch)
1038         {
1039           memcpy (first_active, new_bbs, n * sizeof (basic_block));
1040           first_active_latch = new_bbs[1];
1041         }
1042
1043       /* Set counts and frequencies.  */
1044       if (flags & DLTHE_FLAG_UPDATE_FREQ)
1045         {
1046           scale_bbs_frequencies (new_bbs, n, scale_act, REG_BR_PROB_BASE);
1047           scale_act = RDIV (scale_act * scale_step[j], REG_BR_PROB_BASE);
1048         }
1049     }
1050   free (new_bbs);
1051   free (orig_loops);
1052
1053   /* Update the original loop.  */
1054   if (!is_latch)
1055     set_immediate_dominator (loops->cfg.dom, e->dest, e->src);
1056   if (flags & DLTHE_FLAG_UPDATE_FREQ)
1057     {
1058       scale_bbs_frequencies (bbs, n, scale_main, REG_BR_PROB_BASE);
1059       free (scale_step);
1060     }
1061
1062   /* Update dominators of outer blocks if affected.  */
1063   for (i = 0; i < n; i++)
1064     {
1065       basic_block dominated, dom_bb, *dom_bbs;
1066       int n_dom_bbs,j;
1067
1068       bb = bbs[i];
1069       n_dom_bbs = get_dominated_by (loops->cfg.dom, bb, &dom_bbs);
1070       for (j = 0; j < n_dom_bbs; j++)
1071         {
1072           dominated = dom_bbs[j];
1073           if (flow_bb_inside_loop_p (loop, dominated))
1074             continue;
1075           dom_bb = nearest_common_dominator (
1076                         loops->cfg.dom, first_active[i], first_active_latch);
1077           set_immediate_dominator (loops->cfg.dom, dominated, dom_bb);
1078         }
1079       free (dom_bbs);
1080     }
1081   free (first_active);
1082
1083   free (bbs);
1084
1085   return true;
1086 }
1087
1088 /* Creates a pre-header for a LOOP.  Returns newly created block.  Unless
1089    CP_SIMPLE_PREHEADERS is set in FLAGS, we only force LOOP to have single
1090    entry; otherwise we also force preheader block to have only one successor.
1091    The function also updates dominators stored in DOM.  */
1092 static basic_block
1093 create_preheader (struct loop *loop, dominance_info dom, int flags)
1094 {
1095   edge e, fallthru;
1096   basic_block dummy;
1097   basic_block jump, src = 0;
1098   struct loop *cloop, *ploop;
1099   int nentry = 0;
1100   rtx insn;
1101
1102   cloop = loop->outer;
1103
1104   for (e = loop->header->pred; e; e = e->pred_next)
1105     {
1106       if (e->src == loop->latch)
1107         continue;
1108       nentry++;
1109     }
1110   if (!nentry)
1111     abort ();
1112   if (nentry == 1)
1113     {
1114       for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next);
1115       if (!(flags & CP_SIMPLE_PREHEADERS)
1116           || !e->src->succ->succ_next)
1117         return NULL;
1118     }
1119
1120   insn = first_insn_after_basic_block_note (loop->header);
1121   if (insn)
1122     insn = PREV_INSN (insn);
1123   else
1124     insn = get_last_insn ();
1125   if (insn == loop->header->end)
1126     {
1127       /* Split_block would not split block after its end.  */
1128       emit_note_after (NOTE_INSN_DELETED, insn);
1129     }
1130   fallthru = split_block (loop->header, insn);
1131   dummy = fallthru->src;
1132   loop->header = fallthru->dest;
1133
1134   /* The header could be a latch of some superloop(s); due to design of
1135      split_block, it would now move to fallthru->dest.  */
1136   for (ploop = loop; ploop; ploop = ploop->outer)
1137     if (ploop->latch == dummy)
1138       ploop->latch = fallthru->dest;
1139
1140   add_to_dominance_info (dom, fallthru->dest);
1141
1142   /* Redirect edges.  */
1143   for (e = dummy->pred; e; e = e->pred_next)
1144     {
1145       src = e->src;
1146       if (src == loop->latch)
1147         break;
1148     }
1149   if (!e)
1150     abort ();
1151
1152   dummy->frequency -= EDGE_FREQUENCY (e);
1153   dummy->count -= e->count;
1154   fallthru->count -= e->count;
1155   jump = redirect_edge_and_branch_force (e, loop->header);
1156   if (jump)
1157     {
1158       add_to_dominance_info (dom, jump);
1159       set_immediate_dominator (dom, jump, src);
1160       add_bb_to_loop (jump, loop);
1161       loop->latch = jump;
1162     }
1163
1164   /* Update structures.  */
1165   redirect_immediate_dominators (dom, dummy, loop->header);
1166   set_immediate_dominator (dom, loop->header, dummy);
1167   loop->header->loop_father = loop;
1168   add_bb_to_loop (dummy, cloop);
1169   if (rtl_dump_file)
1170     fprintf (rtl_dump_file, "Created preheader block for loop %i\n",
1171              loop->num);
1172
1173   return dummy;
1174 }
1175
1176 /* Create preheaders for each loop from loop tree stored in LOOPS; for meaning
1177    of FLAGS see create_preheader.  */
1178 void
1179 create_preheaders (struct loops *loops, int flags)
1180 {
1181   unsigned i;
1182   for (i = 1; i < loops->num; i++)
1183     create_preheader (loops->parray[i], loops->cfg.dom, flags);
1184   loops->state |= LOOPS_HAVE_PREHEADERS;
1185 }
1186
1187 /* Forces all loop latches of loops from loop tree LOOPS to have only single
1188    successor.  */
1189 void
1190 force_single_succ_latches (struct loops *loops)
1191 {
1192   unsigned i;
1193   struct loop *loop;
1194   edge e;
1195
1196   for (i = 1; i < loops->num; i++)
1197     {
1198       loop = loops->parray[i];
1199       if (loop->latch != loop->header
1200           && !loop->latch->succ->succ_next)
1201         continue;
1202
1203       for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1204         continue;
1205
1206       loop_split_edge_with (e, NULL_RTX, loops);
1207     }
1208   loops->state |= LOOPS_HAVE_SIMPLE_LATCHES;
1209 }
1210
1211 /* A quite stupid function to put INSNS on edge E. They are supposed to form
1212    just one basic block.  Jumps in INSNS are not handled, so cfg do not have to
1213    be ok after this function.  The created block is placed on correct place
1214    in LOOPS structure and its dominator is set.  */
1215 basic_block
1216 loop_split_edge_with (edge e, rtx insns, struct loops *loops)
1217 {
1218   basic_block src, dest, new_bb;
1219   struct loop *loop_c;
1220   edge new_e;
1221
1222   src = e->src;
1223   dest = e->dest;
1224
1225   loop_c = find_common_loop (src->loop_father, dest->loop_father);
1226
1227   /* Create basic block for it.  */
1228
1229   new_bb = split_edge (e);
1230   add_to_dominance_info (loops->cfg.dom, new_bb);
1231   add_bb_to_loop (new_bb, loop_c);
1232   new_bb->flags = insns ? BB_SUPERBLOCK : 0;
1233
1234   new_e = new_bb->succ;
1235   if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1236     {
1237       new_bb->flags |= BB_IRREDUCIBLE_LOOP;
1238       new_e->flags |= EDGE_IRREDUCIBLE_LOOP;
1239     }
1240
1241   if (insns)
1242     emit_insn_after (insns, new_bb->end);
1243
1244   set_immediate_dominator (loops->cfg.dom, new_bb, src);
1245   set_immediate_dominator (loops->cfg.dom, dest,
1246     recount_dominator (loops->cfg.dom, dest));
1247
1248   if (dest->loop_father->latch == src)
1249     dest->loop_father->latch = new_bb;
1250
1251   return new_bb;
1252 }