gcc/cfgloopmanip.c

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