gcc/cfgloopmanip.c

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