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