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