gcc/cfghooks.c

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