gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "basic-block.h"
  29 #include "tree-flow.h"
  30 #include "timevar.h"
  31 #include "toplev.h"
  32
  33 /* A pointer to one of the hooks containers.  */
  34 static struct cfg_hooks *cfg_hooks;
  35
  36 /* Initialization of functions specific to the rtl IR.  */
  37 void
  38 rtl_register_cfg_hooks (void)
  39 {
  40   cfg_hooks = &rtl_cfg_hooks;
  41 }
  42
  43 /* Initialization of functions specific to the rtl IR.  */
  44 void
  45 cfg_layout_rtl_register_cfg_hooks (void)
  46 {
  47   cfg_hooks = &cfg_layout_rtl_cfg_hooks;
  48 }
  49
  50 /* Initialization of functions specific to the tree IR.  */
  51
  52 void
  53 tree_register_cfg_hooks (void)
  54 {
  55   cfg_hooks = &tree_cfg_hooks;
  56 }
  57
  58 /* Returns current ir type (rtl = 0, trees = 1).  */
  59
  60 int
  61 ir_type (void)
  62 {
  63   return cfg_hooks == &tree_cfg_hooks ? 1 : 0;
  64 }
  65
  66 /* Verify the CFG consistency.
  67
  68    Currently it does following: checks edge and basic block list correctness
  69    and calls into IL dependent checking then.  */
  70
  71 void
  72 verify_flow_info (void)
  73 {
  74   size_t *edge_checksum;
  75   int num_bb_notes, err = 0;
  76   basic_block bb, last_bb_seen;
  77   basic_block *last_visited;
  78
  79   timevar_push (TV_CFG_VERIFY);
  80   last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block));
  81   edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t));
  82
  83   /* Check bb chain & numbers.  */
  84   last_bb_seen = ENTRY_BLOCK_PTR;
  85   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
  86     {
  87       if (bb != EXIT_BLOCK_PTR
  88           && bb != BASIC_BLOCK (bb->index))
  89         {
  90           error ("bb %d on wrong place", bb->index);
  91           err = 1;
  92         }
  93
  94       if (bb->prev_bb != last_bb_seen)
  95         {
  96           error ("prev_bb of %d should be %d, not %d",
  97                  bb->index, last_bb_seen->index, bb->prev_bb->index);
  98           err = 1;
  99         }
 100
 101       last_bb_seen = bb;
 102     }
 103
 104   /* Now check the basic blocks (boundaries etc.) */
 105   FOR_EACH_BB_REVERSE (bb)
 106     {
 107       int n_fallthru = 0;
 108       edge e;
 109       edge_iterator ei;
 110
 111       if (bb->count < 0)
 112         {
 113           error ("verify_flow_info: Wrong count of block %i %i",
 114                  bb->index, (int)bb->count);
 115           err = 1;
 116         }
 117       if (bb->frequency < 0)
 118         {
 119           error ("verify_flow_info: Wrong frequency of block %i %i",
 120                  bb->index, bb->frequency);
 121           err = 1;
 122         }
 123       FOR_EACH_EDGE (e, ei, bb->succs)
 124         {
 125           if (last_visited [e->dest->index + 2] == bb)
 126             {
 127               error ("verify_flow_info: Duplicate edge %i->%i",
 128                      e->src->index, e->dest->index);
 129               err = 1;
 130             }
 131           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 132             {
 133               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 134                      e->src->index, e->dest->index, e->probability);
 135               err = 1;
 136             }
 137           if (e->count < 0)
 138             {
 139               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 140                      e->src->index, e->dest->index, (int)e->count);
 141               err = 1;
 142             }
 143
 144           last_visited [e->dest->index + 2] = bb;
 145
 146           if (e->flags & EDGE_FALLTHRU)
 147             n_fallthru++;
 148
 149           if (e->src != bb)
 150             {
 151               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 152                      bb->index);
 153               fprintf (stderr, "Predecessor: ");
 154               dump_edge_info (stderr, e, 0);
 155               fprintf (stderr, "\nSuccessor: ");
 156               dump_edge_info (stderr, e, 1);
 157               fprintf (stderr, "\n");
 158               err = 1;
 159             }
 160
 161           edge_checksum[e->dest->index + 2] += (size_t) e;
 162         }
 163       if (n_fallthru > 1)
 164         {
 165           error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
 166           err = 1;
 167         }
 168
 169       FOR_EACH_EDGE (e, ei, bb->preds)
 170         {
 171           if (e->dest != bb)
 172             {
 173               error ("basic block %d pred edge is corrupted", bb->index);
 174               fputs ("Predecessor: ", stderr);
 175               dump_edge_info (stderr, e, 0);
 176               fputs ("\nSuccessor: ", stderr);
 177               dump_edge_info (stderr, e, 1);
 178               fputc ('\n', stderr);
 179               err = 1;
 180             }
 181
 182           if (ei.index != e->dest_idx)
 183             {
 184               error ("basic block %d pred edge is corrupted", bb->index);
 185               error ("its dest_idx should be %d, not %d",
 186                      ei.index, e->dest_idx);
 187               fputs ("Predecessor: ", stderr);
 188               dump_edge_info (stderr, e, 0);
 189               fputs ("\nSuccessor: ", stderr);
 190               dump_edge_info (stderr, e, 1);
 191               fputc ('\n', stderr);
 192               err = 1;
 193             }
 194
 195           edge_checksum[e->dest->index + 2] -= (size_t) e;
 196         }
 197     }
 198
 199   /* Complete edge checksumming for ENTRY and EXIT.  */
 200   {
 201     edge e;
 202     edge_iterator ei;
 203
 204     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 205       edge_checksum[e->dest->index + 2] += (size_t) e;
 206
 207     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 208       edge_checksum[e->dest->index + 2] -= (size_t) e;
 209   }
 210
 211   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 212     if (edge_checksum[bb->index + 2])
 213       {
 214         error ("basic block %i edge lists are corrupted", bb->index);
 215         err = 1;
 216       }
 217
 218   num_bb_notes = 0;
 219   last_bb_seen = ENTRY_BLOCK_PTR;
 220
 221   /* Clean up.  */
 222   free (last_visited);
 223   free (edge_checksum);
 224
 225   if (cfg_hooks->verify_flow_info)
 226     err |= cfg_hooks->verify_flow_info ();
 227   if (err)
 228     internal_error ("verify_flow_info failed");
 229   timevar_pop (TV_CFG_VERIFY);
 230 }
 231
 232 /* Print out one basic block.  This function takes care of the purely
 233    graph related information.  The cfg hook for the active representation
 234    should dump representation-specific information.  */
 235
 236 void
 237 dump_bb (basic_block bb, FILE *outf, int indent)
 238 {
 239   edge e;
 240   edge_iterator ei;
 241   char *s_indent;
 242
 243   s_indent = alloca ((size_t) indent + 1);
 244   memset (s_indent, ' ', (size_t) indent);
 245   s_indent[indent] = '\0';
 246
 247   fprintf (outf, ";;%s basic block %d, loop depth %d, count ",
 248            s_indent, bb->index, bb->loop_depth);
 249   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 250   putc ('\n', outf);
 251
 252   fprintf (outf, ";;%s prev block ", s_indent);
 253   if (bb->prev_bb)
 254     fprintf (outf, "%d, ", bb->prev_bb->index);
 255   else
 256     fprintf (outf, "(nil), ");
 257   fprintf (outf, "next block ");
 258   if (bb->next_bb)
 259     fprintf (outf, "%d", bb->next_bb->index);
 260   else
 261     fprintf (outf, "(nil)");
 262   putc ('\n', outf);
 263
 264   fprintf (outf, ";;%s pred:      ", s_indent);
 265   FOR_EACH_EDGE (e, ei, bb->preds)
 266     dump_edge_info (outf, e, 0);
 267   putc ('\n', outf);
 268
 269   fprintf (outf, ";;%s succ:      ", s_indent);
 270   FOR_EACH_EDGE (e, ei, bb->succs)
 271     dump_edge_info (outf, e, 1);
 272   putc ('\n', outf);
 273
 274   if (cfg_hooks->dump_bb)
 275     cfg_hooks->dump_bb (bb, outf, indent);
 276 }
 277
 278 /* Redirect edge E to the given basic block DEST and update underlying program
 279    representation.  Returns edge representing redirected branch (that may not
 280    be equivalent to E in the case of duplicate edges being removed) or NULL
 281    if edge is not easily redirectable for whatever reason.  */
 282
 283 edge
 284 redirect_edge_and_branch (edge e, basic_block dest)
 285 {
 286   edge ret;
 287
 288   if (!cfg_hooks->redirect_edge_and_branch)
 289     internal_error ("%s does not support redirect_edge_and_branch.",
 290                     cfg_hooks->name);
 291
 292   ret = cfg_hooks->redirect_edge_and_branch (e, dest);
 293
 294   return ret;
 295 }
 296
 297 /* Redirect the edge E to basic block DEST even if it requires creating
 298    of a new basic block; then it returns the newly created basic block.
 299    Aborts when redirection is impossible.  */
 300
 301 basic_block
 302 redirect_edge_and_branch_force (edge e, basic_block dest)
 303 {
 304   basic_block ret;
 305
 306   if (!cfg_hooks->redirect_edge_and_branch_force)
 307     internal_error ("%s does not support redirect_edge_and_branch_force.",
 308                     cfg_hooks->name);
 309
 310   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 311
 312   return ret;
 313 }
 314
 315 /* Splits basic block BB after the specified instruction I (but at least after
 316    the labels).  If I is NULL, splits just after labels.  The newly created edge
 317    is returned.  The new basic block is created just after the old one.  */
 318
 319 edge
 320 split_block (basic_block bb, void *i)
 321 {
 322   basic_block new_bb;
 323
 324   if (!cfg_hooks->split_block)
 325     internal_error ("%s does not support split_block.", cfg_hooks->name);
 326
 327   new_bb = cfg_hooks->split_block (bb, i);
 328   if (!new_bb)
 329     return NULL;
 330
 331   new_bb->count = bb->count;
 332   new_bb->frequency = bb->frequency;
 333   new_bb->loop_depth = bb->loop_depth;
 334
 335   if (dom_info_available_p (CDI_DOMINATORS))
 336     {
 337       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 338       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 339     }
 340
 341   return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 342 }
 343
 344 /* Splits block BB just after labels.  The newly created edge is returned.  */
 345
 346 edge
 347 split_block_after_labels (basic_block bb)
 348 {
 349   return split_block (bb, NULL);
 350 }
 351
 352 /* Moves block BB immediately after block AFTER.  Returns false if the
 353    movement was impossible.  */
 354
 355 bool
 356 move_block_after (basic_block bb, basic_block after)
 357 {
 358   bool ret;
 359
 360   if (!cfg_hooks->move_block_after)
 361     internal_error ("%s does not support move_block_after.", cfg_hooks->name);
 362
 363   ret = cfg_hooks->move_block_after (bb, after);
 364
 365   return ret;
 366 }
 367
 368 /* Deletes the basic block BB.  */
 369
 370 void
 371 delete_basic_block (basic_block bb)
 372 {
 373   if (!cfg_hooks->delete_basic_block)
 374     internal_error ("%s does not support delete_basic_block.", cfg_hooks->name);
 375
 376   cfg_hooks->delete_basic_block (bb);
 377
 378   /* Remove the edges into and out of this block.  Note that there may
 379      indeed be edges in, if we are removing an unreachable loop.  */
 380   while (EDGE_COUNT (bb->preds) != 0)
 381     remove_edge (EDGE_PRED (bb, 0));
 382   while (EDGE_COUNT (bb->succs) != 0)
 383     remove_edge (EDGE_SUCC (bb, 0));
 384
 385   if (dom_computed[CDI_DOMINATORS])
 386     delete_from_dominance_info (CDI_DOMINATORS, bb);
 387   if (dom_computed[CDI_POST_DOMINATORS])
 388     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 389
 390   /* Remove the basic block from the array.  */
 391   expunge_block (bb);
 392 }
 393
 394 /* Splits edge E and returns the newly created basic block.  */
 395
 396 basic_block
 397 split_edge (edge e)
 398 {
 399   basic_block ret;
 400   gcov_type count = e->count;
 401   int freq = EDGE_FREQUENCY (e);
 402   edge f;
 403   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
 404
 405   if (!cfg_hooks->split_edge)
 406     internal_error ("%s does not support split_edge.", cfg_hooks->name);
 407
 408   ret = cfg_hooks->split_edge (e);
 409   ret->count = count;
 410   ret->frequency = freq;
 411   EDGE_SUCC (ret, 0)->probability = REG_BR_PROB_BASE;
 412   EDGE_SUCC (ret, 0)->count = count;
 413
 414   if (irr)
 415     {
 416       ret->flags |= BB_IRREDUCIBLE_LOOP;
 417       EDGE_PRED (ret, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 418       EDGE_SUCC (ret, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
 419     }
 420
 421   if (dom_computed[CDI_DOMINATORS])
 422     set_immediate_dominator (CDI_DOMINATORS, ret, EDGE_PRED (ret, 0)->src);
 423
 424   if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY)
 425     {
 426       /* There are two cases:
 427
 428          If the immediate dominator of e->dest is not e->src, it
 429          remains unchanged.
 430
 431          If immediate dominator of e->dest is e->src, it may become
 432          ret, provided that all other predecessors of e->dest are
 433          dominated by e->dest.  */
 434
 435       if (get_immediate_dominator (CDI_DOMINATORS, EDGE_SUCC (ret, 0)->dest)
 436           == EDGE_PRED (ret, 0)->src)
 437         {
 438           edge_iterator ei;
 439           FOR_EACH_EDGE (f, ei, EDGE_SUCC (ret, 0)->dest->preds)
 440             {
 441               if (f == EDGE_SUCC (ret, 0))
 442                 continue;
 443
 444               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 445                                    EDGE_SUCC (ret, 0)->dest))
 446                 break;
 447             }
 448
 449           if (!f)
 450             set_immediate_dominator (CDI_DOMINATORS, EDGE_SUCC (ret, 0)->dest, ret);
 451         }
 452     };
 453
 454   return ret;
 455 }
 456
 457 /* Creates a new basic block just after the basic block AFTER.
 458    HEAD and END are the first and the last statement belonging
 459    to the block.  If both are NULL, an empty block is created.  */
 460
 461 basic_block
 462 create_basic_block (void *head, void *end, basic_block after)
 463 {
 464   basic_block ret;
 465
 466   if (!cfg_hooks->create_basic_block)
 467     internal_error ("%s does not support create_basic_block.", cfg_hooks->name);
 468
 469   ret = cfg_hooks->create_basic_block (head, end, after);
 470
 471   if (dom_computed[CDI_DOMINATORS])
 472     add_to_dominance_info (CDI_DOMINATORS, ret);
 473   if (dom_computed[CDI_POST_DOMINATORS])
 474     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 475
 476   return ret;
 477 }
 478
 479 /* Creates an empty basic block just after basic block AFTER.  */
 480
 481 basic_block
 482 create_empty_bb (basic_block after)
 483 {
 484   return create_basic_block (NULL, NULL, after);
 485 }
 486
 487 /* Checks whether we may merge blocks BB1 and BB2.  */
 488
 489 bool
 490 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 491 {
 492   bool ret;
 493
 494   if (!cfg_hooks->can_merge_blocks_p)
 495     internal_error ("%s does not support can_merge_blocks_p.", cfg_hooks->name);
 496
 497   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 498
 499   return ret;
 500 }
 501
 502 void
 503 predict_edge (edge e, enum br_predictor predictor, int probability)
 504 {
 505   if (!cfg_hooks->predict_edge)
 506     internal_error ("%s does not support predict_edge.", cfg_hooks->name);
 507
 508   cfg_hooks->predict_edge (e, predictor, probability);
 509 }
 510
 511 bool
 512 predicted_by_p (basic_block bb, enum br_predictor predictor)
 513 {
 514   if (!cfg_hooks->predict_edge)
 515     internal_error ("%s does not support predicted_by_p.", cfg_hooks->name);
 516
 517   return cfg_hooks->predicted_by_p (bb, predictor);
 518 }
 519
 520 /* Merges basic block B into basic block A.  */
 521
 522 void
 523 merge_blocks (basic_block a, basic_block b)
 524 {
 525   edge e;
 526   edge_iterator ei;
 527
 528   if (!cfg_hooks->merge_blocks)
 529     internal_error ("%s does not support merge_blocks.", cfg_hooks->name);
 530
 531   cfg_hooks->merge_blocks (a, b);
 532
 533   /* Normally there should only be one successor of A and that is B, but
 534      partway though the merge of blocks for conditional_execution we'll
 535      be merging a TEST block with THEN and ELSE successors.  Free the
 536      whole lot of them and hope the caller knows what they're doing.  */
 537
 538   while (EDGE_COUNT (a->succs) != 0)
 539    remove_edge (EDGE_SUCC (a, 0));
 540
 541   /* Adjust the edges out of B for the new owner.  */
 542   FOR_EACH_EDGE (e, ei, b->succs)
 543     e->src = a;
 544   a->succs = b->succs;
 545   a->flags |= b->flags;
 546
 547   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 548   b->preds = b->succs = NULL;
 549   a->global_live_at_end = b->global_live_at_end;
 550
 551   if (dom_computed[CDI_DOMINATORS])
 552     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 553
 554   if (dom_computed[CDI_DOMINATORS])
 555     delete_from_dominance_info (CDI_DOMINATORS, b);
 556   if (dom_computed[CDI_POST_DOMINATORS])
 557     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 558
 559   expunge_block (b);
 560 }
 561
 562 /* Split BB into entry part and the rest (the rest is the newly created block).
 563    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 564    part.  Returns the edge connecting the entry part to the rest.  */
 565
 566 edge
 567 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 568                       void (*new_bb_cbk) (basic_block))
 569 {
 570   edge e, fallthru;
 571   edge_iterator ei;
 572   basic_block dummy, jump;
 573
 574   if (!cfg_hooks->make_forwarder_block)
 575     internal_error ("%s does not support make_forwarder_block.",
 576                     cfg_hooks->name);
 577
 578   fallthru = split_block_after_labels (bb);
 579   dummy = fallthru->src;
 580   bb = fallthru->dest;
 581
 582   /* Redirect back edges we want to keep.  */
 583   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 584     {
 585       if (redirect_edge_p (e))
 586         {
 587           ei_next (&ei);
 588           continue;
 589         }
 590
 591       dummy->frequency -= EDGE_FREQUENCY (e);
 592       dummy->count -= e->count;
 593       if (dummy->frequency < 0)
 594         dummy->frequency = 0;
 595       if (dummy->count < 0)
 596         dummy->count = 0;
 597       fallthru->count -= e->count;
 598       if (fallthru->count < 0)
 599         fallthru->count = 0;
 600
 601       jump = redirect_edge_and_branch_force (e, bb);
 602       if (jump)
 603         new_bb_cbk (jump);
 604     }
 605
 606   if (dom_info_available_p (CDI_DOMINATORS))
 607     {
 608       basic_block doms_to_fix[2];
 609
 610       doms_to_fix[0] = dummy;
 611       doms_to_fix[1] = bb;
 612       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
 613     }
 614
 615   cfg_hooks->make_forwarder_block (fallthru);
 616
 617   return fallthru;
 618 }
 619
 620 void
 621 tidy_fallthru_edge (edge e)
 622 {
 623   if (cfg_hooks->tidy_fallthru_edge)
 624     cfg_hooks->tidy_fallthru_edge (e);
 625 }
 626
 627 /* Fix up edges that now fall through, or rather should now fall through
 628    but previously required a jump around now deleted blocks.  Simplify
 629    the search by only examining blocks numerically adjacent, since this
 630    is how find_basic_blocks created them.  */
 631
 632 void
 633 tidy_fallthru_edges (void)
 634 {
 635   basic_block b, c;
 636
 637   if (!cfg_hooks->tidy_fallthru_edge)
 638     return;
 639
 640   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 641     return;
 642
 643   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 644     {
 645       edge s;
 646
 647       c = b->next_bb;
 648
 649       /* We care about simple conditional or unconditional jumps with
 650          a single successor.
 651
 652          If we had a conditional branch to the next instruction when
 653          find_basic_blocks was called, then there will only be one
 654          out edge for the block which ended with the conditional
 655          branch (since we do not create duplicate edges).
 656
 657          Furthermore, the edge will be marked as a fallthru because we
 658          merge the flags for the duplicate edges.  So we do not want to
 659          check that the edge is not a FALLTHRU edge.  */
 660
 661       if (EDGE_COUNT (b->succs) == 1)
 662         {
 663           s = EDGE_SUCC (b, 0);
 664           if (! (s->flags & EDGE_COMPLEX)
 665               && s->dest == c
 666               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 667             tidy_fallthru_edge (s);
 668         }
 669     }
 670 }
 671
 672 /* Returns true if we can duplicate basic block BB.  */
 673
 674 bool
 675 can_duplicate_block_p (basic_block bb)
 676 {
 677   edge e;
 678
 679   if (!cfg_hooks->can_duplicate_block_p)
 680     internal_error ("%s does not support can_duplicate_block_p.",
 681                     cfg_hooks->name);
 682
 683   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 684     return false;
 685
 686   /* Duplicating fallthru block to exit would require adding a jump
 687      and splitting the real last BB.  */
 688   e = find_edge (bb, EXIT_BLOCK_PTR);
 689   if (e && (e->flags & EDGE_FALLTHRU))
 690     return false;
 691
 692   return cfg_hooks->can_duplicate_block_p (bb);
 693 }
 694
 695 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 696    new basic block.  */
 697
 698 basic_block
 699 duplicate_block (basic_block bb, edge e)
 700 {
 701   edge s, n;
 702   basic_block new_bb;
 703   gcov_type new_count = e ? e->count : 0;
 704   edge_iterator ei;
 705
 706   if (!cfg_hooks->duplicate_block)
 707     internal_error ("%s does not support duplicate_block.",
 708                     cfg_hooks->name);
 709
 710   if (bb->count < new_count)
 711     new_count = bb->count;
 712
 713 #ifdef ENABLE_CHECKING
 714   gcc_assert (can_duplicate_block_p (bb));
 715 #endif
 716
 717   new_bb = cfg_hooks->duplicate_block (bb);
 718
 719   new_bb->loop_depth = bb->loop_depth;
 720   new_bb->flags = bb->flags;
 721   FOR_EACH_EDGE (s, ei, bb->succs)
 722     {
 723       /* Since we are creating edges from a new block to successors
 724          of another block (which therefore are known to be disjoint), there
 725          is no need to actually check for duplicated edges.  */
 726       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 727       n->probability = s->probability;
 728       if (e && bb->count)
 729         {
 730           /* Take care for overflows!  */
 731           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 732           s->count -= n->count;
 733         }
 734       else
 735         n->count = s->count;
 736       n->aux = s->aux;
 737     }
 738
 739   if (e)
 740     {
 741       new_bb->count = new_count;
 742       bb->count -= new_count;
 743
 744       new_bb->frequency = EDGE_FREQUENCY (e);
 745       bb->frequency -= EDGE_FREQUENCY (e);
 746
 747       redirect_edge_and_branch_force (e, new_bb);
 748
 749       if (bb->count < 0)
 750         bb->count = 0;
 751       if (bb->frequency < 0)
 752         bb->frequency = 0;
 753     }
 754   else
 755     {
 756       new_bb->count = bb->count;
 757       new_bb->frequency = bb->frequency;
 758     }
 759
 760   new_bb->rbi->original = bb;
 761   bb->rbi->copy = new_bb;
 762
 763   return new_bb;
 764 }
 765
 766 /* Return 1 if BB ends with a call, possibly followed by some
 767    instructions that must stay with the call, 0 otherwise.  */
 768
 769 bool
 770 block_ends_with_call_p (basic_block bb)
 771 {
 772   if (!cfg_hooks->block_ends_with_call_p)
 773     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
 774
 775   return (cfg_hooks->block_ends_with_call_p) (bb);
 776 }
 777
 778 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
 779
 780 bool
 781 block_ends_with_condjump_p (basic_block bb)
 782 {
 783   if (!cfg_hooks->block_ends_with_condjump_p)
 784     internal_error ("%s does not support block_ends_with_condjump_p",
 785                     cfg_hooks->name);
 786
 787   return (cfg_hooks->block_ends_with_condjump_p) (bb);
 788 }
 789
 790 /* Add fake edges to the function exit for any non constant and non noreturn
 791    calls, volatile inline assembly in the bitmap of blocks specified by
 792    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 793    that were split.
 794
 795    The goal is to expose cases in which entering a basic block does not imply
 796    that all subsequent instructions must be executed.  */
 797
 798 int
 799 flow_call_edges_add (sbitmap blocks)
 800 {
 801   if (!cfg_hooks->flow_call_edges_add)
 802     internal_error ("%s does not support flow_call_edges_add",
 803                     cfg_hooks->name);
 804
 805   return (cfg_hooks->flow_call_edges_add) (blocks);
 806 }
 807
 808 /* This function is called immediately after edge E is added to the
 809    edge vector E->dest->preds.  */
 810
 811 void
 812 execute_on_growing_pred (edge e)
 813 {
 814   if (cfg_hooks->execute_on_growing_pred)
 815     cfg_hooks->execute_on_growing_pred (e);
 816 }
 817
 818 /* This function is called immediately before edge E is removed from
 819    the edge vector E->dest->preds.  */
 820
 821 void
 822 execute_on_shrinking_pred (edge e)
 823 {
 824   if (cfg_hooks->execute_on_shrinking_pred)
 825     cfg_hooks->execute_on_shrinking_pred (e);
 826 }