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