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