gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Sebastian Pop <s.pop@laposte.net>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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 "diagnostic-core.h"
  32 #include "cfgloop.h"
  33
  34 /* A pointer to one of the hooks containers.  */
  35 static struct cfg_hooks *cfg_hooks;
  36
  37 /* Initialization of functions specific to the rtl IR.  */
  38 void
  39 rtl_register_cfg_hooks (void)
  40 {
  41   cfg_hooks = &rtl_cfg_hooks;
  42 }
  43
  44 /* Initialization of functions specific to the rtl IR.  */
  45 void
  46 cfg_layout_rtl_register_cfg_hooks (void)
  47 {
  48   cfg_hooks = &cfg_layout_rtl_cfg_hooks;
  49 }
  50
  51 /* Initialization of functions specific to the tree IR.  */
  52
  53 void
  54 gimple_register_cfg_hooks (void)
  55 {
  56   cfg_hooks = &gimple_cfg_hooks;
  57 }
  58
  59 struct cfg_hooks
  60 get_cfg_hooks (void)
  61 {
  62   return *cfg_hooks;
  63 }
  64
  65 void
  66 set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
  67 {
  68   *cfg_hooks = new_cfg_hooks;
  69 }
  70
  71 /* Returns current ir type.  */
  72
  73 enum ir_type
  74 current_ir_type (void)
  75 {
  76   if (cfg_hooks == &gimple_cfg_hooks)
  77     return IR_GIMPLE;
  78   else if (cfg_hooks == &rtl_cfg_hooks)
  79     return IR_RTL_CFGRTL;
  80   else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
  81     return IR_RTL_CFGLAYOUT;
  82   else
  83     gcc_unreachable ();
  84 }
  85
  86 /* Verify the CFG consistency.
  87
  88    Currently it does following: checks edge and basic block list correctness
  89    and calls into IL dependent checking then.  */
  90
  91 DEBUG_FUNCTION void
  92 verify_flow_info (void)
  93 {
  94   size_t *edge_checksum;
  95   int err = 0;
  96   basic_block bb, last_bb_seen;
  97   basic_block *last_visited;
  98
  99   timevar_push (TV_CFG_VERIFY);
 100   last_visited = XCNEWVEC (basic_block, last_basic_block);
 101   edge_checksum = XCNEWVEC (size_t, last_basic_block);
 102
 103   /* Check bb chain & numbers.  */
 104   last_bb_seen = ENTRY_BLOCK_PTR;
 105   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 106     {
 107       if (bb != EXIT_BLOCK_PTR
 108           && bb != BASIC_BLOCK (bb->index))
 109         {
 110           error ("bb %d on wrong place", bb->index);
 111           err = 1;
 112         }
 113
 114       if (bb->prev_bb != last_bb_seen)
 115         {
 116           error ("prev_bb of %d should be %d, not %d",
 117                  bb->index, last_bb_seen->index, bb->prev_bb->index);
 118           err = 1;
 119         }
 120
 121       last_bb_seen = bb;
 122     }
 123
 124   /* Now check the basic blocks (boundaries etc.) */
 125   FOR_EACH_BB_REVERSE (bb)
 126     {
 127       int n_fallthru = 0;
 128       edge e;
 129       edge_iterator ei;
 130
 131       if (bb->loop_father != NULL && current_loops == NULL)
 132         {
 133           error ("verify_flow_info: Block %i has loop_father, but there are no loops",
 134                  bb->index);
 135           err = 1;
 136         }
 137       if (bb->loop_father == NULL && current_loops != NULL)
 138         {
 139           error ("verify_flow_info: Block %i lacks loop_father", bb->index);
 140           err = 1;
 141         }
 142
 143       if (bb->count < 0)
 144         {
 145           error ("verify_flow_info: Wrong count of block %i %i",
 146                  bb->index, (int)bb->count);
 147           err = 1;
 148         }
 149       if (bb->frequency < 0)
 150         {
 151           error ("verify_flow_info: Wrong frequency of block %i %i",
 152                  bb->index, bb->frequency);
 153           err = 1;
 154         }
 155       FOR_EACH_EDGE (e, ei, bb->succs)
 156         {
 157           if (last_visited [e->dest->index] == bb)
 158             {
 159               error ("verify_flow_info: Duplicate edge %i->%i",
 160                      e->src->index, e->dest->index);
 161               err = 1;
 162             }
 163           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 164             {
 165               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 166                      e->src->index, e->dest->index, e->probability);
 167               err = 1;
 168             }
 169           if (e->count < 0)
 170             {
 171               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 172                      e->src->index, e->dest->index, (int)e->count);
 173               err = 1;
 174             }
 175
 176           last_visited [e->dest->index] = bb;
 177
 178           if (e->flags & EDGE_FALLTHRU)
 179             n_fallthru++;
 180
 181           if (e->src != bb)
 182             {
 183               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 184                      bb->index);
 185               fprintf (stderr, "Predecessor: ");
 186               dump_edge_info (stderr, e, 0);
 187               fprintf (stderr, "\nSuccessor: ");
 188               dump_edge_info (stderr, e, 1);
 189               fprintf (stderr, "\n");
 190               err = 1;
 191             }
 192
 193           edge_checksum[e->dest->index] += (size_t) e;
 194         }
 195       if (n_fallthru > 1)
 196         {
 197           error ("wrong amount of branch edges after unconditional jump %i", bb->index);
 198           err = 1;
 199         }
 200
 201       FOR_EACH_EDGE (e, ei, bb->preds)
 202         {
 203           if (e->dest != bb)
 204             {
 205               error ("basic block %d pred edge is corrupted", bb->index);
 206               fputs ("Predecessor: ", stderr);
 207               dump_edge_info (stderr, e, 0);
 208               fputs ("\nSuccessor: ", stderr);
 209               dump_edge_info (stderr, e, 1);
 210               fputc ('\n', stderr);
 211               err = 1;
 212             }
 213
 214           if (ei.index != e->dest_idx)
 215             {
 216               error ("basic block %d pred edge is corrupted", bb->index);
 217               error ("its dest_idx should be %d, not %d",
 218                      ei.index, e->dest_idx);
 219               fputs ("Predecessor: ", stderr);
 220               dump_edge_info (stderr, e, 0);
 221               fputs ("\nSuccessor: ", stderr);
 222               dump_edge_info (stderr, e, 1);
 223               fputc ('\n', stderr);
 224               err = 1;
 225             }
 226
 227           edge_checksum[e->dest->index] -= (size_t) e;
 228         }
 229     }
 230
 231   /* Complete edge checksumming for ENTRY and EXIT.  */
 232   {
 233     edge e;
 234     edge_iterator ei;
 235
 236     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 237       edge_checksum[e->dest->index] += (size_t) e;
 238
 239     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 240       edge_checksum[e->dest->index] -= (size_t) e;
 241   }
 242
 243   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 244     if (edge_checksum[bb->index])
 245       {
 246         error ("basic block %i edge lists are corrupted", bb->index);
 247         err = 1;
 248       }
 249
 250   last_bb_seen = ENTRY_BLOCK_PTR;
 251
 252   /* Clean up.  */
 253   free (last_visited);
 254   free (edge_checksum);
 255
 256   if (cfg_hooks->verify_flow_info)
 257     err |= cfg_hooks->verify_flow_info ();
 258   if (err)
 259     internal_error ("verify_flow_info failed");
 260   timevar_pop (TV_CFG_VERIFY);
 261 }
 262
 263 /* Print out one basic block.  This function takes care of the purely
 264    graph related information.  The cfg hook for the active representation
 265    should dump representation-specific information.  */
 266
 267 void
 268 dump_bb (basic_block bb, FILE *outf, int indent)
 269 {
 270   edge e;
 271   edge_iterator ei;
 272   char *s_indent;
 273
 274   s_indent = (char *) alloca ((size_t) indent + 1);
 275   memset (s_indent, ' ', (size_t) indent);
 276   s_indent[indent] = '\0';
 277
 278   fprintf (outf, ";;%s basic block %d, loop depth %d, count ",
 279            s_indent, bb->index, bb->loop_depth);
 280   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 281   putc ('\n', outf);
 282
 283   fprintf (outf, ";;%s prev block ", s_indent);
 284   if (bb->prev_bb)
 285     fprintf (outf, "%d, ", bb->prev_bb->index);
 286   else
 287     fprintf (outf, "(nil), ");
 288   fprintf (outf, "next block ");
 289   if (bb->next_bb)
 290     fprintf (outf, "%d", bb->next_bb->index);
 291   else
 292     fprintf (outf, "(nil)");
 293   putc ('\n', outf);
 294
 295   fprintf (outf, ";;%s pred:      ", s_indent);
 296   FOR_EACH_EDGE (e, ei, bb->preds)
 297     dump_edge_info (outf, e, 0);
 298   putc ('\n', outf);
 299
 300   fprintf (outf, ";;%s succ:      ", s_indent);
 301   FOR_EACH_EDGE (e, ei, bb->succs)
 302     dump_edge_info (outf, e, 1);
 303   putc ('\n', outf);
 304
 305   if (cfg_hooks->dump_bb)
 306     cfg_hooks->dump_bb (bb, outf, indent, 0);
 307 }
 308
 309 /* Redirect edge E to the given basic block DEST and update underlying program
 310    representation.  Returns edge representing redirected branch (that may not
 311    be equivalent to E in the case of duplicate edges being removed) or NULL
 312    if edge is not easily redirectable for whatever reason.  */
 313
 314 edge
 315 redirect_edge_and_branch (edge e, basic_block dest)
 316 {
 317   edge ret;
 318
 319   if (!cfg_hooks->redirect_edge_and_branch)
 320     internal_error ("%s does not support redirect_edge_and_branch",
 321                     cfg_hooks->name);
 322
 323   ret = cfg_hooks->redirect_edge_and_branch (e, dest);
 324
 325   /* If RET != E, then either the redirection failed, or the edge E
 326      was removed since RET already lead to the same destination.  */
 327   if (current_loops != NULL && ret == e)
 328     rescan_loop_exit (e, false, false);
 329
 330   return ret;
 331 }
 332
 333 /* Returns true if it is possible to remove the edge E by redirecting it
 334    to the destination of the other edge going from its source.  */
 335
 336 bool
 337 can_remove_branch_p (const_edge e)
 338 {
 339   if (!cfg_hooks->can_remove_branch_p)
 340     internal_error ("%s does not support can_remove_branch_p",
 341                     cfg_hooks->name);
 342
 343   if (EDGE_COUNT (e->src->succs) != 2)
 344     return false;
 345
 346   return cfg_hooks->can_remove_branch_p (e);
 347 }
 348
 349 /* Removes E, by redirecting it to the destination of the other edge going
 350    from its source.  Can_remove_branch_p must be true for E, hence this
 351    operation cannot fail.  */
 352
 353 void
 354 remove_branch (edge e)
 355 {
 356   edge other;
 357   basic_block src = e->src;
 358   int irr;
 359
 360   gcc_assert (EDGE_COUNT (e->src->succs) == 2);
 361
 362   other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
 363   irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
 364
 365   e = redirect_edge_and_branch (e, other->dest);
 366   gcc_assert (e != NULL);
 367
 368   e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 369   e->flags |= irr;
 370 }
 371
 372 /* Removes edge E from cfg.  Unlike remove_branch, it does not update IL.  */
 373
 374 void
 375 remove_edge (edge e)
 376 {
 377   if (current_loops != NULL)
 378     rescan_loop_exit (e, false, true);
 379
 380   remove_edge_raw (e);
 381 }
 382
 383 /* Redirect the edge E to basic block DEST even if it requires creating
 384    of a new basic block; then it returns the newly created basic block.
 385    Aborts when redirection is impossible.  */
 386
 387 basic_block
 388 redirect_edge_and_branch_force (edge e, basic_block dest)
 389 {
 390   basic_block ret, src = e->src;
 391   struct loop *loop;
 392
 393   if (!cfg_hooks->redirect_edge_and_branch_force)
 394     internal_error ("%s does not support redirect_edge_and_branch_force",
 395                     cfg_hooks->name);
 396
 397   if (current_loops != NULL)
 398     rescan_loop_exit (e, false, true);
 399
 400   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 401   if (ret != NULL
 402       && dom_info_available_p (CDI_DOMINATORS))
 403     set_immediate_dominator (CDI_DOMINATORS, ret, src);
 404
 405   if (current_loops != NULL)
 406     {
 407       if (ret != NULL)
 408         {
 409           loop = find_common_loop (single_pred (ret)->loop_father,
 410                                    single_succ (ret)->loop_father);
 411           add_bb_to_loop (ret, loop);
 412         }
 413       else if (find_edge (src, dest) == e)
 414         rescan_loop_exit (e, true, false);
 415     }
 416
 417   return ret;
 418 }
 419
 420 /* Splits basic block BB after the specified instruction I (but at least after
 421    the labels).  If I is NULL, splits just after labels.  The newly created edge
 422    is returned.  The new basic block is created just after the old one.  */
 423
 424 edge
 425 split_block (basic_block bb, void *i)
 426 {
 427   basic_block new_bb;
 428   edge res;
 429
 430   if (!cfg_hooks->split_block)
 431     internal_error ("%s does not support split_block", cfg_hooks->name);
 432
 433   new_bb = cfg_hooks->split_block (bb, i);
 434   if (!new_bb)
 435     return NULL;
 436
 437   new_bb->count = bb->count;
 438   new_bb->frequency = bb->frequency;
 439   new_bb->loop_depth = bb->loop_depth;
 440   new_bb->discriminator = bb->discriminator;
 441
 442   if (dom_info_available_p (CDI_DOMINATORS))
 443     {
 444       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 445       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 446     }
 447
 448   if (current_loops != NULL)
 449     {
 450       add_bb_to_loop (new_bb, bb->loop_father);
 451       if (bb->loop_father->latch == bb)
 452         bb->loop_father->latch = new_bb;
 453     }
 454
 455   res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 456
 457   if (bb->flags & BB_IRREDUCIBLE_LOOP)
 458     {
 459       new_bb->flags |= BB_IRREDUCIBLE_LOOP;
 460       res->flags |= EDGE_IRREDUCIBLE_LOOP;
 461     }
 462
 463   return res;
 464 }
 465
 466 /* Splits block BB just after labels.  The newly created edge is returned.  */
 467
 468 edge
 469 split_block_after_labels (basic_block bb)
 470 {
 471   return split_block (bb, NULL);
 472 }
 473
 474 /* Moves block BB immediately after block AFTER.  Returns false if the
 475    movement was impossible.  */
 476
 477 bool
 478 move_block_after (basic_block bb, basic_block after)
 479 {
 480   bool ret;
 481
 482   if (!cfg_hooks->move_block_after)
 483     internal_error ("%s does not support move_block_after", cfg_hooks->name);
 484
 485   ret = cfg_hooks->move_block_after (bb, after);
 486
 487   return ret;
 488 }
 489
 490 /* Deletes the basic block BB.  */
 491
 492 void
 493 delete_basic_block (basic_block bb)
 494 {
 495   if (!cfg_hooks->delete_basic_block)
 496     internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
 497
 498   cfg_hooks->delete_basic_block (bb);
 499
 500   if (current_loops != NULL)
 501     {
 502       struct loop *loop = bb->loop_father;
 503
 504       /* If we remove the header or the latch of a loop, mark the loop for
 505          removal by setting its header and latch to NULL.  */
 506       if (loop->latch == bb
 507           || loop->header == bb)
 508         {
 509           loop->header = NULL;
 510           loop->latch = NULL;
 511         }
 512
 513       remove_bb_from_loops (bb);
 514     }
 515
 516   /* Remove the edges into and out of this block.  Note that there may
 517      indeed be edges in, if we are removing an unreachable loop.  */
 518   while (EDGE_COUNT (bb->preds) != 0)
 519     remove_edge (EDGE_PRED (bb, 0));
 520   while (EDGE_COUNT (bb->succs) != 0)
 521     remove_edge (EDGE_SUCC (bb, 0));
 522
 523   if (dom_info_available_p (CDI_DOMINATORS))
 524     delete_from_dominance_info (CDI_DOMINATORS, bb);
 525   if (dom_info_available_p (CDI_POST_DOMINATORS))
 526     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 527
 528   /* Remove the basic block from the array.  */
 529   expunge_block (bb);
 530 }
 531
 532 /* Splits edge E and returns the newly created basic block.  */
 533
 534 basic_block
 535 split_edge (edge e)
 536 {
 537   basic_block ret;
 538   gcov_type count = e->count;
 539   int freq = EDGE_FREQUENCY (e);
 540   edge f;
 541   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
 542   struct loop *loop;
 543   basic_block src = e->src, dest = e->dest;
 544
 545   if (!cfg_hooks->split_edge)
 546     internal_error ("%s does not support split_edge", cfg_hooks->name);
 547
 548   if (current_loops != NULL)
 549     rescan_loop_exit (e, false, true);
 550
 551   ret = cfg_hooks->split_edge (e);
 552   ret->count = count;
 553   ret->frequency = freq;
 554   single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
 555   single_succ_edge (ret)->count = count;
 556
 557   if (irr)
 558     {
 559       ret->flags |= BB_IRREDUCIBLE_LOOP;
 560       single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 561       single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 562     }
 563
 564   if (dom_info_available_p (CDI_DOMINATORS))
 565     set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
 566
 567   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
 568     {
 569       /* There are two cases:
 570
 571          If the immediate dominator of e->dest is not e->src, it
 572          remains unchanged.
 573
 574          If immediate dominator of e->dest is e->src, it may become
 575          ret, provided that all other predecessors of e->dest are
 576          dominated by e->dest.  */
 577
 578       if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
 579           == single_pred (ret))
 580         {
 581           edge_iterator ei;
 582           FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
 583             {
 584               if (f == single_succ_edge (ret))
 585                 continue;
 586
 587               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 588                                    single_succ (ret)))
 589                 break;
 590             }
 591
 592           if (!f)
 593             set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
 594         }
 595     }
 596
 597   if (current_loops != NULL)
 598     {
 599       loop = find_common_loop (src->loop_father, dest->loop_father);
 600       add_bb_to_loop (ret, loop);
 601
 602       if (loop->latch == src)
 603         loop->latch = ret;
 604     }
 605
 606   return ret;
 607 }
 608
 609 /* Creates a new basic block just after the basic block AFTER.
 610    HEAD and END are the first and the last statement belonging
 611    to the block.  If both are NULL, an empty block is created.  */
 612
 613 basic_block
 614 create_basic_block (void *head, void *end, basic_block after)
 615 {
 616   basic_block ret;
 617
 618   if (!cfg_hooks->create_basic_block)
 619     internal_error ("%s does not support create_basic_block", cfg_hooks->name);
 620
 621   ret = cfg_hooks->create_basic_block (head, end, after);
 622
 623   if (dom_info_available_p (CDI_DOMINATORS))
 624     add_to_dominance_info (CDI_DOMINATORS, ret);
 625   if (dom_info_available_p (CDI_POST_DOMINATORS))
 626     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 627
 628   return ret;
 629 }
 630
 631 /* Creates an empty basic block just after basic block AFTER.  */
 632
 633 basic_block
 634 create_empty_bb (basic_block after)
 635 {
 636   return create_basic_block (NULL, NULL, after);
 637 }
 638
 639 /* Checks whether we may merge blocks BB1 and BB2.  */
 640
 641 bool
 642 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 643 {
 644   bool ret;
 645
 646   if (!cfg_hooks->can_merge_blocks_p)
 647     internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
 648
 649   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 650
 651   return ret;
 652 }
 653
 654 void
 655 predict_edge (edge e, enum br_predictor predictor, int probability)
 656 {
 657   if (!cfg_hooks->predict_edge)
 658     internal_error ("%s does not support predict_edge", cfg_hooks->name);
 659
 660   cfg_hooks->predict_edge (e, predictor, probability);
 661 }
 662
 663 bool
 664 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 665 {
 666   if (!cfg_hooks->predict_edge)
 667     internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
 668
 669   return cfg_hooks->predicted_by_p (bb, predictor);
 670 }
 671
 672 /* Merges basic block B into basic block A.  */
 673
 674 void
 675 merge_blocks (basic_block a, basic_block b)
 676 {
 677   edge e;
 678   edge_iterator ei;
 679
 680   if (!cfg_hooks->merge_blocks)
 681     internal_error ("%s does not support merge_blocks", cfg_hooks->name);
 682
 683   cfg_hooks->merge_blocks (a, b);
 684
 685   if (current_loops != NULL)
 686     remove_bb_from_loops (b);
 687
 688   /* Normally there should only be one successor of A and that is B, but
 689      partway though the merge of blocks for conditional_execution we'll
 690      be merging a TEST block with THEN and ELSE successors.  Free the
 691      whole lot of them and hope the caller knows what they're doing.  */
 692
 693   while (EDGE_COUNT (a->succs) != 0)
 694     remove_edge (EDGE_SUCC (a, 0));
 695
 696   /* Adjust the edges out of B for the new owner.  */
 697   FOR_EACH_EDGE (e, ei, b->succs)
 698     {
 699       e->src = a;
 700       if (current_loops != NULL)
 701         rescan_loop_exit (e, true, false);
 702     }
 703   a->succs = b->succs;
 704   a->flags |= b->flags;
 705
 706   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 707   b->preds = b->succs = NULL;
 708
 709   if (dom_info_available_p (CDI_DOMINATORS))
 710     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 711
 712   if (dom_info_available_p (CDI_DOMINATORS))
 713     delete_from_dominance_info (CDI_DOMINATORS, b);
 714   if (dom_info_available_p (CDI_POST_DOMINATORS))
 715     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 716
 717   expunge_block (b);
 718 }
 719
 720 /* Split BB into entry part and the rest (the rest is the newly created block).
 721    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 722    part.  Returns the edge connecting the entry part to the rest.  */
 723
 724 edge
 725 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 726                       void (*new_bb_cbk) (basic_block))
 727 {
 728   edge e, fallthru;
 729   edge_iterator ei;
 730   basic_block dummy, jump;
 731   struct loop *loop, *ploop, *cloop;
 732
 733   if (!cfg_hooks->make_forwarder_block)
 734     internal_error ("%s does not support make_forwarder_block",
 735                     cfg_hooks->name);
 736
 737   fallthru = split_block_after_labels (bb);
 738   dummy = fallthru->src;
 739   bb = fallthru->dest;
 740
 741   /* Redirect back edges we want to keep.  */
 742   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 743     {
 744       basic_block e_src;
 745
 746       if (redirect_edge_p (e))
 747         {
 748           ei_next (&ei);
 749           continue;
 750         }
 751
 752       dummy->frequency -= EDGE_FREQUENCY (e);
 753       dummy->count -= e->count;
 754       if (dummy->frequency < 0)
 755         dummy->frequency = 0;
 756       if (dummy->count < 0)
 757         dummy->count = 0;
 758       fallthru->count -= e->count;
 759       if (fallthru->count < 0)
 760         fallthru->count = 0;
 761
 762       e_src = e->src;
 763       jump = redirect_edge_and_branch_force (e, bb);
 764       if (jump != NULL)
 765         {
 766           /* If we redirected the loop latch edge, the JUMP block now acts like
 767              the new latch of the loop.  */
 768           if (current_loops != NULL
 769               && dummy->loop_father != NULL
 770               && dummy->loop_father->header == dummy
 771               && dummy->loop_father->latch == e_src)
 772             dummy->loop_father->latch = jump;
 773
 774           if (new_bb_cbk != NULL)
 775             new_bb_cbk (jump);
 776         }
 777     }
 778
 779   if (dom_info_available_p (CDI_DOMINATORS))
 780     {
 781       VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
 782       VEC_quick_push (basic_block, doms_to_fix, dummy);
 783       VEC_quick_push (basic_block, doms_to_fix, bb);
 784       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
 785       VEC_free (basic_block, heap, doms_to_fix);
 786     }
 787
 788   if (current_loops != NULL)
 789     {
 790       /* If we do not split a loop header, then both blocks belong to the
 791          same loop.  In case we split loop header and do not redirect the
 792          latch edge to DUMMY, then DUMMY belongs to the outer loop, and
 793          BB becomes the new header.  If latch is not recorded for the loop,
 794          we leave this updating on the caller (this may only happen during
 795          loop analysis).  */
 796       loop = dummy->loop_father;
 797       if (loop->header == dummy
 798           && loop->latch != NULL
 799           && find_edge (loop->latch, dummy) == NULL)
 800         {
 801           remove_bb_from_loops (dummy);
 802           loop->header = bb;
 803
 804           cloop = loop;
 805           FOR_EACH_EDGE (e, ei, dummy->preds)
 806             {
 807               cloop = find_common_loop (cloop, e->src->loop_father);
 808             }
 809           add_bb_to_loop (dummy, cloop);
 810         }
 811
 812       /* In case we split loop latch, update it.  */
 813       for (ploop = loop; ploop; ploop = loop_outer (ploop))
 814         if (ploop->latch == dummy)
 815           ploop->latch = bb;
 816     }
 817
 818   cfg_hooks->make_forwarder_block (fallthru);
 819
 820   return fallthru;
 821 }
 822
 823 void
 824 tidy_fallthru_edge (edge e)
 825 {
 826   if (cfg_hooks->tidy_fallthru_edge)
 827     cfg_hooks->tidy_fallthru_edge (e);
 828 }
 829
 830 /* Fix up edges that now fall through, or rather should now fall through
 831    but previously required a jump around now deleted blocks.  Simplify
 832    the search by only examining blocks numerically adjacent, since this
 833    is how they were created.  */
 834
 835 void
 836 tidy_fallthru_edges (void)
 837 {
 838   basic_block b, c;
 839
 840   if (!cfg_hooks->tidy_fallthru_edge)
 841     return;
 842
 843   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 844     return;
 845
 846   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 847     {
 848       edge s;
 849
 850       c = b->next_bb;
 851
 852       /* We care about simple conditional or unconditional jumps with
 853          a single successor.
 854
 855          If we had a conditional branch to the next instruction when
 856          CFG was built, then there will only be one out edge for the
 857          block which ended with the conditional branch (since we do
 858          not create duplicate edges).
 859
 860          Furthermore, the edge will be marked as a fallthru because we
 861          merge the flags for the duplicate edges.  So we do not want to
 862          check that the edge is not a FALLTHRU edge.  */
 863
 864       if (single_succ_p (b))
 865         {
 866           s = single_succ_edge (b);
 867           if (! (s->flags & EDGE_COMPLEX)
 868               && s->dest == c
 869               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 870             tidy_fallthru_edge (s);
 871         }
 872     }
 873 }
 874
 875 /* Returns true if we can duplicate basic block BB.  */
 876
 877 bool
 878 can_duplicate_block_p (const_basic_block bb)
 879 {
 880   if (!cfg_hooks->can_duplicate_block_p)
 881     internal_error ("%s does not support can_duplicate_block_p",
 882                     cfg_hooks->name);
 883
 884   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 885     return false;
 886
 887   return cfg_hooks->can_duplicate_block_p (bb);
 888 }
 889
 890 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 891    new basic block.  The new basic block is placed after the basic block
 892    AFTER.  */
 893
 894 basic_block
 895 duplicate_block (basic_block bb, edge e, basic_block after)
 896 {
 897   edge s, n;
 898   basic_block new_bb;
 899   gcov_type new_count = e ? e->count : 0;
 900   edge_iterator ei;
 901
 902   if (!cfg_hooks->duplicate_block)
 903     internal_error ("%s does not support duplicate_block",
 904                     cfg_hooks->name);
 905
 906   if (bb->count < new_count)
 907     new_count = bb->count;
 908
 909   gcc_checking_assert (can_duplicate_block_p (bb));
 910
 911   new_bb = cfg_hooks->duplicate_block (bb);
 912   if (after)
 913     move_block_after (new_bb, after);
 914
 915   new_bb->loop_depth = bb->loop_depth;
 916   new_bb->flags = bb->flags;
 917   FOR_EACH_EDGE (s, ei, bb->succs)
 918     {
 919       /* Since we are creating edges from a new block to successors
 920          of another block (which therefore are known to be disjoint), there
 921          is no need to actually check for duplicated edges.  */
 922       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 923       n->probability = s->probability;
 924       if (e && bb->count)
 925         {
 926           /* Take care for overflows!  */
 927           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 928           s->count -= n->count;
 929         }
 930       else
 931         n->count = s->count;
 932       n->aux = s->aux;
 933     }
 934
 935   if (e)
 936     {
 937       new_bb->count = new_count;
 938       bb->count -= new_count;
 939
 940       new_bb->frequency = EDGE_FREQUENCY (e);
 941       bb->frequency -= EDGE_FREQUENCY (e);
 942
 943       redirect_edge_and_branch_force (e, new_bb);
 944
 945       if (bb->count < 0)
 946         bb->count = 0;
 947       if (bb->frequency < 0)
 948         bb->frequency = 0;
 949     }
 950   else
 951     {
 952       new_bb->count = bb->count;
 953       new_bb->frequency = bb->frequency;
 954     }
 955
 956   set_bb_original (new_bb, bb);
 957   set_bb_copy (bb, new_bb);
 958
 959   /* Add the new block to the copy of the loop of BB, or directly to the loop
 960      of BB if the loop is not being copied.  */
 961   if (current_loops != NULL)
 962     {
 963       struct loop *cloop = bb->loop_father;
 964       struct loop *copy = get_loop_copy (cloop);
 965       add_bb_to_loop (new_bb, copy ? copy : cloop);
 966     }
 967
 968   return new_bb;
 969 }
 970
 971 /* Return 1 if BB ends with a call, possibly followed by some
 972    instructions that must stay with the call, 0 otherwise.  */
 973
 974 bool
 975 block_ends_with_call_p (basic_block bb)
 976 {
 977   if (!cfg_hooks->block_ends_with_call_p)
 978     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
 979
 980   return (cfg_hooks->block_ends_with_call_p) (bb);
 981 }
 982
 983 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
 984
 985 bool
 986 block_ends_with_condjump_p (const_basic_block bb)
 987 {
 988   if (!cfg_hooks->block_ends_with_condjump_p)
 989     internal_error ("%s does not support block_ends_with_condjump_p",
 990                     cfg_hooks->name);
 991
 992   return (cfg_hooks->block_ends_with_condjump_p) (bb);
 993 }
 994
 995 /* Add fake edges to the function exit for any non constant and non noreturn
 996    calls, volatile inline assembly in the bitmap of blocks specified by
 997    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 998    that were split.
 999
1000    The goal is to expose cases in which entering a basic block does not imply
1001    that all subsequent instructions must be executed.  */
1002
1003 int
1004 flow_call_edges_add (sbitmap blocks)
1005 {
1006   if (!cfg_hooks->flow_call_edges_add)
1007     internal_error ("%s does not support flow_call_edges_add",
1008                     cfg_hooks->name);
1009
1010   return (cfg_hooks->flow_call_edges_add) (blocks);
1011 }
1012
1013 /* This function is called immediately after edge E is added to the
1014    edge vector E->dest->preds.  */
1015
1016 void
1017 execute_on_growing_pred (edge e)
1018 {
1019   if (cfg_hooks->execute_on_growing_pred)
1020     cfg_hooks->execute_on_growing_pred (e);
1021 }
1022
1023 /* This function is called immediately before edge E is removed from
1024    the edge vector E->dest->preds.  */
1025
1026 void
1027 execute_on_shrinking_pred (edge e)
1028 {
1029   if (cfg_hooks->execute_on_shrinking_pred)
1030     cfg_hooks->execute_on_shrinking_pred (e);
1031 }
1032
1033 /* This is used inside loop versioning when we want to insert
1034    stmts/insns on the edges, which have a different behavior
1035    in tree's and in RTL, so we made a CFG hook.  */
1036 void
1037 lv_flush_pending_stmts (edge e)
1038 {
1039   if (cfg_hooks->flush_pending_stmts)
1040     cfg_hooks->flush_pending_stmts (e);
1041 }
1042
1043 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1044    a new version of the loop basic-blocks, the parameters here are
1045    exactly the same as in duplicate_loop_to_header_edge or
1046    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1047    additional work to maintain ssa information that's why there is
1048    a need to call the tree_duplicate_loop_to_header_edge rather
1049    than duplicate_loop_to_header_edge when we are in tree mode.  */
1050 bool
1051 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1052                                         unsigned int ndupl,
1053                                         sbitmap wont_exit, edge orig,
1054                                         VEC (edge, heap) **to_remove,
1055                                         int flags)
1056 {
1057   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1058   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1059                                                             ndupl, wont_exit,
1060                                                             orig, to_remove,
1061                                                             flags);
1062 }
1063
1064 /* Conditional jumps are represented differently in trees and RTL,
1065    this hook takes a basic block that is known to have a cond jump
1066    at its end and extracts the taken and not taken edges out of it
1067    and store it in E1 and E2 respectively.  */
1068 void
1069 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1070 {
1071   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1072   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1073 }
1074
1075 /* Responsible for updating the ssa info (PHI nodes) on the
1076    new condition basic block that guards the versioned loop.  */
1077 void
1078 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1079                            basic_block new_block, edge e)
1080 {
1081   if (cfg_hooks->lv_adjust_loop_header_phi)
1082     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1083 }
1084
1085 /* Conditions in trees and RTL are different so we need
1086    a different handling when we add the condition to the
1087    versioning code.  */
1088 void
1089 lv_add_condition_to_bb (basic_block first, basic_block second,
1090                         basic_block new_block, void *cond)
1091 {
1092   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1093   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1094 }