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 (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 = XCNEWVEC (basic_block, last_basic_block);
  81   edge_checksum = XCNEWVEC (size_t, last_basic_block);
  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] == 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] = 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] += (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] -= (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] += (size_t) e;
 206
 207     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 208       edge_checksum[e->dest->index] -= (size_t) e;
 209   }
 210
 211   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 212     if (edge_checksum[bb->index])
 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
 549   if (dom_computed[CDI_DOMINATORS])
 550     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 551
 552   if (dom_computed[CDI_DOMINATORS])
 553     delete_from_dominance_info (CDI_DOMINATORS, b);
 554   if (dom_computed[CDI_POST_DOMINATORS])
 555     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 556
 557   expunge_block (b);
 558 }
 559
 560 /* Split BB into entry part and the rest (the rest is the newly created block).
 561    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 562    part.  Returns the edge connecting the entry part to the rest.  */
 563
 564 edge
 565 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 566                       void (*new_bb_cbk) (basic_block))
 567 {
 568   edge e, fallthru;
 569   edge_iterator ei;
 570   basic_block dummy, jump;
 571
 572   if (!cfg_hooks->make_forwarder_block)
 573     internal_error ("%s does not support make_forwarder_block",
 574                     cfg_hooks->name);
 575
 576   fallthru = split_block_after_labels (bb);
 577   dummy = fallthru->src;
 578   bb = fallthru->dest;
 579
 580   /* Redirect back edges we want to keep.  */
 581   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 582     {
 583       if (redirect_edge_p (e))
 584         {
 585           ei_next (&ei);
 586           continue;
 587         }
 588
 589       dummy->frequency -= EDGE_FREQUENCY (e);
 590       dummy->count -= e->count;
 591       if (dummy->frequency < 0)
 592         dummy->frequency = 0;
 593       if (dummy->count < 0)
 594         dummy->count = 0;
 595       fallthru->count -= e->count;
 596       if (fallthru->count < 0)
 597         fallthru->count = 0;
 598
 599       jump = redirect_edge_and_branch_force (e, bb);
 600       if (jump)
 601         new_bb_cbk (jump);
 602     }
 603
 604   if (dom_info_available_p (CDI_DOMINATORS))
 605     {
 606       basic_block doms_to_fix[2];
 607
 608       doms_to_fix[0] = dummy;
 609       doms_to_fix[1] = bb;
 610       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2);
 611     }
 612
 613   cfg_hooks->make_forwarder_block (fallthru);
 614
 615   return fallthru;
 616 }
 617
 618 void
 619 tidy_fallthru_edge (edge e)
 620 {
 621   if (cfg_hooks->tidy_fallthru_edge)
 622     cfg_hooks->tidy_fallthru_edge (e);
 623 }
 624
 625 /* Fix up edges that now fall through, or rather should now fall through
 626    but previously required a jump around now deleted blocks.  Simplify
 627    the search by only examining blocks numerically adjacent, since this
 628    is how find_basic_blocks created them.  */
 629
 630 void
 631 tidy_fallthru_edges (void)
 632 {
 633   basic_block b, c;
 634
 635   if (!cfg_hooks->tidy_fallthru_edge)
 636     return;
 637
 638   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 639     return;
 640
 641   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 642     {
 643       edge s;
 644
 645       c = b->next_bb;
 646
 647       /* We care about simple conditional or unconditional jumps with
 648          a single successor.
 649
 650          If we had a conditional branch to the next instruction when
 651          find_basic_blocks was called, then there will only be one
 652          out edge for the block which ended with the conditional
 653          branch (since we do not create duplicate edges).
 654
 655          Furthermore, the edge will be marked as a fallthru because we
 656          merge the flags for the duplicate edges.  So we do not want to
 657          check that the edge is not a FALLTHRU edge.  */
 658
 659       if (single_succ_p (b))
 660         {
 661           s = single_succ_edge (b);
 662           if (! (s->flags & EDGE_COMPLEX)
 663               && s->dest == c
 664               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 665             tidy_fallthru_edge (s);
 666         }
 667     }
 668 }
 669
 670 /* Returns true if we can duplicate basic block BB.  */
 671
 672 bool
 673 can_duplicate_block_p (basic_block bb)
 674 {
 675   edge e;
 676
 677   if (!cfg_hooks->can_duplicate_block_p)
 678     internal_error ("%s does not support can_duplicate_block_p",
 679                     cfg_hooks->name);
 680
 681   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 682     return false;
 683
 684   /* Duplicating fallthru block to exit would require adding a jump
 685      and splitting the real last BB.  */
 686   e = find_edge (bb, EXIT_BLOCK_PTR);
 687   if (e && (e->flags & EDGE_FALLTHRU))
 688     return false;
 689
 690   return cfg_hooks->can_duplicate_block_p (bb);
 691 }
 692
 693 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 694    new basic block.  The new basic block is placed after the basic block
 695    AFTER.  */
 696
 697 basic_block
 698 duplicate_block (basic_block bb, edge e, basic_block after)
 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   if (after)
 718     move_block_after (new_bb, after);
 719
 720   new_bb->loop_depth = bb->loop_depth;
 721   new_bb->flags = bb->flags;
 722   FOR_EACH_EDGE (s, ei, bb->succs)
 723     {
 724       /* Since we are creating edges from a new block to successors
 725          of another block (which therefore are known to be disjoint), there
 726          is no need to actually check for duplicated edges.  */
 727       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 728       n->probability = s->probability;
 729       if (e && bb->count)
 730         {
 731           /* Take care for overflows!  */
 732           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 733           s->count -= n->count;
 734         }
 735       else
 736         n->count = s->count;
 737       n->aux = s->aux;
 738     }
 739
 740   if (e)
 741     {
 742       new_bb->count = new_count;
 743       bb->count -= new_count;
 744
 745       new_bb->frequency = EDGE_FREQUENCY (e);
 746       bb->frequency -= EDGE_FREQUENCY (e);
 747
 748       redirect_edge_and_branch_force (e, new_bb);
 749
 750       if (bb->count < 0)
 751         bb->count = 0;
 752       if (bb->frequency < 0)
 753         bb->frequency = 0;
 754     }
 755   else
 756     {
 757       new_bb->count = bb->count;
 758       new_bb->frequency = bb->frequency;
 759     }
 760
 761   set_bb_original (new_bb, bb);
 762   set_bb_copy (bb, new_bb);
 763
 764   return new_bb;
 765 }
 766
 767 /* Return 1 if BB ends with a call, possibly followed by some
 768    instructions that must stay with the call, 0 otherwise.  */
 769
 770 bool
 771 block_ends_with_call_p (basic_block bb)
 772 {
 773   if (!cfg_hooks->block_ends_with_call_p)
 774     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
 775
 776   return (cfg_hooks->block_ends_with_call_p) (bb);
 777 }
 778
 779 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
 780
 781 bool
 782 block_ends_with_condjump_p (basic_block bb)
 783 {
 784   if (!cfg_hooks->block_ends_with_condjump_p)
 785     internal_error ("%s does not support block_ends_with_condjump_p",
 786                     cfg_hooks->name);
 787
 788   return (cfg_hooks->block_ends_with_condjump_p) (bb);
 789 }
 790
 791 /* Add fake edges to the function exit for any non constant and non noreturn
 792    calls, volatile inline assembly in the bitmap of blocks specified by
 793    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 794    that were split.
 795
 796    The goal is to expose cases in which entering a basic block does not imply
 797    that all subsequent instructions must be executed.  */
 798
 799 int
 800 flow_call_edges_add (sbitmap blocks)
 801 {
 802   if (!cfg_hooks->flow_call_edges_add)
 803     internal_error ("%s does not support flow_call_edges_add",
 804                     cfg_hooks->name);
 805
 806   return (cfg_hooks->flow_call_edges_add) (blocks);
 807 }
 808
 809 /* This function is called immediately after edge E is added to the
 810    edge vector E->dest->preds.  */
 811
 812 void
 813 execute_on_growing_pred (edge e)
 814 {
 815   if (cfg_hooks->execute_on_growing_pred)
 816     cfg_hooks->execute_on_growing_pred (e);
 817 }
 818
 819 /* This function is called immediately before edge E is removed from
 820    the edge vector E->dest->preds.  */
 821
 822 void
 823 execute_on_shrinking_pred (edge e)
 824 {
 825   if (cfg_hooks->execute_on_shrinking_pred)
 826     cfg_hooks->execute_on_shrinking_pred (e);
 827 }
 828
 829 /* This is used inside loop versioning when we want to insert
 830    stmts/insns on the edges, which have a different behavior
 831    in tree's and in RTL, so we made a CFG hook.  */
 832 void
 833 lv_flush_pending_stmts (edge e)
 834 {
 835   if (cfg_hooks->flush_pending_stmts)
 836     cfg_hooks->flush_pending_stmts (e);
 837 }
 838
 839 /* Loop versioning uses the duplicate_loop_to_header_edge to create
 840    a new version of the loop basic-blocks, the parameters here are
 841    exactly the same as in duplicate_loop_to_header_edge or
 842    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
 843    additional work to maintain ssa information that's why there is
 844    a need to call the tree_duplicate_loop_to_header_edge rather
 845    than duplicate_loop_to_header_edge when we are in tree mode.  */
 846 bool
 847 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
 848                                         struct loops *loops, unsigned int ndupl,
 849                                         sbitmap wont_exit, edge orig,
 850                                         edge *to_remove,
 851                                         unsigned int *n_to_remove, int flags)
 852 {
 853   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
 854   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e, loops,
 855                                                             ndupl, wont_exit,
 856                                                             orig, to_remove,
 857                                                             n_to_remove, flags);
 858 }
 859
 860 /* Conditional jumps are represented differently in trees and RTL,
 861    this hook takes a basic block that is known to have a cond jump
 862    at its end and extracts the taken and not taken eges out of it
 863    and store it in E1 and E2 respectively.  */
 864 void
 865 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
 866 {
 867   gcc_assert (cfg_hooks->extract_cond_bb_edges);
 868   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
 869 }
 870
 871 /* Responsible for updating the ssa info (PHI nodes) on the
 872    new condition basic block that guards the versioned loop.  */
 873 void
 874 lv_adjust_loop_header_phi (basic_block first, basic_block second,
 875                            basic_block new, edge e)
 876 {
 877   if (cfg_hooks->lv_adjust_loop_header_phi)
 878     cfg_hooks->lv_adjust_loop_header_phi (first, second, new, e);
 879 }
 880
 881 /* Conditions in trees and RTL are different so we need
 882    a different handling when we add the condition to the
 883    versioning code.  */
 884 void
 885 lv_add_condition_to_bb (basic_block first, basic_block second,
 886                         basic_block new, void *cond)
 887 {
 888   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
 889   cfg_hooks->lv_add_condition_to_bb (first, second, new, cond);
 890 }