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