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
 392   if (!cfg_hooks->redirect_edge_and_branch_force)
 393     internal_error ("%s does not support redirect_edge_and_branch_force",
 394                     cfg_hooks->name);
 395
 396   if (current_loops != NULL)
 397     rescan_loop_exit (e, false, true);
 398
 399   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 400
 401   if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
 402     set_immediate_dominator (CDI_DOMINATORS, ret, src);
 403
 404   if (current_loops != NULL)
 405     {
 406       if (ret != NULL)
 407         {
 408           struct loop *loop
 409             = 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 /* Try to make the edge fallthru.  */
 824
 825 void
 826 tidy_fallthru_edge (edge e)
 827 {
 828   if (cfg_hooks->tidy_fallthru_edge)
 829     cfg_hooks->tidy_fallthru_edge (e);
 830 }
 831
 832 /* Fix up edges that now fall through, or rather should now fall through
 833    but previously required a jump around now deleted blocks.  Simplify
 834    the search by only examining blocks numerically adjacent, since this
 835    is how they were created.
 836
 837    ??? This routine is currently RTL specific.  */
 838
 839 void
 840 tidy_fallthru_edges (void)
 841 {
 842   basic_block b, c;
 843
 844   if (!cfg_hooks->tidy_fallthru_edge)
 845     return;
 846
 847   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 848     return;
 849
 850   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 851     {
 852       edge s;
 853
 854       c = b->next_bb;
 855
 856       /* We care about simple conditional or unconditional jumps with
 857          a single successor.
 858
 859          If we had a conditional branch to the next instruction when
 860          CFG was built, then there will only be one out edge for the
 861          block which ended with the conditional branch (since we do
 862          not create duplicate edges).
 863
 864          Furthermore, the edge will be marked as a fallthru because we
 865          merge the flags for the duplicate edges.  So we do not want to
 866          check that the edge is not a FALLTHRU edge.  */
 867
 868       if (single_succ_p (b))
 869         {
 870           s = single_succ_edge (b);
 871           if (! (s->flags & EDGE_COMPLEX)
 872               && s->dest == c
 873               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 874             tidy_fallthru_edge (s);
 875         }
 876     }
 877 }
 878
 879 /* Edge E is assumed to be fallthru edge.  Emit needed jump instruction
 880    (and possibly create new basic block) to make edge non-fallthru.
 881    Return newly created BB or NULL if none.  */
 882
 883 basic_block
 884 force_nonfallthru (edge e)
 885 {
 886   basic_block ret, src = e->src;
 887
 888   if (!cfg_hooks->force_nonfallthru)
 889     internal_error ("%s does not support force_nonfallthru",
 890                     cfg_hooks->name);
 891
 892   ret = cfg_hooks->force_nonfallthru (e);
 893   if (ret != NULL)
 894     {
 895       if (dom_info_available_p (CDI_DOMINATORS))
 896         set_immediate_dominator (CDI_DOMINATORS, ret, src);
 897
 898       if (current_loops != NULL)
 899         {
 900           struct loop *loop
 901             = find_common_loop (single_pred (ret)->loop_father,
 902                                 single_succ (ret)->loop_father);
 903           rescan_loop_exit (e, false, true);
 904           add_bb_to_loop (ret, loop);
 905         }
 906     }
 907
 908   return ret;
 909 }
 910
 911 /* Returns true if we can duplicate basic block BB.  */
 912
 913 bool
 914 can_duplicate_block_p (const_basic_block bb)
 915 {
 916   if (!cfg_hooks->can_duplicate_block_p)
 917     internal_error ("%s does not support can_duplicate_block_p",
 918                     cfg_hooks->name);
 919
 920   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 921     return false;
 922
 923   return cfg_hooks->can_duplicate_block_p (bb);
 924 }
 925
 926 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 927    new basic block.  The new basic block is placed after the basic block
 928    AFTER.  */
 929
 930 basic_block
 931 duplicate_block (basic_block bb, edge e, basic_block after)
 932 {
 933   edge s, n;
 934   basic_block new_bb;
 935   gcov_type new_count = e ? e->count : 0;
 936   edge_iterator ei;
 937
 938   if (!cfg_hooks->duplicate_block)
 939     internal_error ("%s does not support duplicate_block",
 940                     cfg_hooks->name);
 941
 942   if (bb->count < new_count)
 943     new_count = bb->count;
 944
 945   gcc_checking_assert (can_duplicate_block_p (bb));
 946
 947   new_bb = cfg_hooks->duplicate_block (bb);
 948   if (after)
 949     move_block_after (new_bb, after);
 950
 951   new_bb->loop_depth = bb->loop_depth;
 952   new_bb->flags = bb->flags;
 953   FOR_EACH_EDGE (s, ei, bb->succs)
 954     {
 955       /* Since we are creating edges from a new block to successors
 956          of another block (which therefore are known to be disjoint), there
 957          is no need to actually check for duplicated edges.  */
 958       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 959       n->probability = s->probability;
 960       if (e && bb->count)
 961         {
 962           /* Take care for overflows!  */
 963           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 964           s->count -= n->count;
 965         }
 966       else
 967         n->count = s->count;
 968       n->aux = s->aux;
 969     }
 970
 971   if (e)
 972     {
 973       new_bb->count = new_count;
 974       bb->count -= new_count;
 975
 976       new_bb->frequency = EDGE_FREQUENCY (e);
 977       bb->frequency -= EDGE_FREQUENCY (e);
 978
 979       redirect_edge_and_branch_force (e, new_bb);
 980
 981       if (bb->count < 0)
 982         bb->count = 0;
 983       if (bb->frequency < 0)
 984         bb->frequency = 0;
 985     }
 986   else
 987     {
 988       new_bb->count = bb->count;
 989       new_bb->frequency = bb->frequency;
 990     }
 991
 992   set_bb_original (new_bb, bb);
 993   set_bb_copy (bb, new_bb);
 994
 995   /* Add the new block to the copy of the loop of BB, or directly to the loop
 996      of BB if the loop is not being copied.  */
 997   if (current_loops != NULL)
 998     {
 999       struct loop *cloop = bb->loop_father;
1000       struct loop *copy = get_loop_copy (cloop);
1001       add_bb_to_loop (new_bb, copy ? copy : cloop);
1002     }
1003
1004   return new_bb;
1005 }
1006
1007 /* Return 1 if BB ends with a call, possibly followed by some
1008    instructions that must stay with the call, 0 otherwise.  */
1009
1010 bool
1011 block_ends_with_call_p (basic_block bb)
1012 {
1013   if (!cfg_hooks->block_ends_with_call_p)
1014     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1015
1016   return (cfg_hooks->block_ends_with_call_p) (bb);
1017 }
1018
1019 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
1020
1021 bool
1022 block_ends_with_condjump_p (const_basic_block bb)
1023 {
1024   if (!cfg_hooks->block_ends_with_condjump_p)
1025     internal_error ("%s does not support block_ends_with_condjump_p",
1026                     cfg_hooks->name);
1027
1028   return (cfg_hooks->block_ends_with_condjump_p) (bb);
1029 }
1030
1031 /* Add fake edges to the function exit for any non constant and non noreturn
1032    calls, volatile inline assembly in the bitmap of blocks specified by
1033    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
1034    that were split.
1035
1036    The goal is to expose cases in which entering a basic block does not imply
1037    that all subsequent instructions must be executed.  */
1038
1039 int
1040 flow_call_edges_add (sbitmap blocks)
1041 {
1042   if (!cfg_hooks->flow_call_edges_add)
1043     internal_error ("%s does not support flow_call_edges_add",
1044                     cfg_hooks->name);
1045
1046   return (cfg_hooks->flow_call_edges_add) (blocks);
1047 }
1048
1049 /* This function is called immediately after edge E is added to the
1050    edge vector E->dest->preds.  */
1051
1052 void
1053 execute_on_growing_pred (edge e)
1054 {
1055   if (cfg_hooks->execute_on_growing_pred)
1056     cfg_hooks->execute_on_growing_pred (e);
1057 }
1058
1059 /* This function is called immediately before edge E is removed from
1060    the edge vector E->dest->preds.  */
1061
1062 void
1063 execute_on_shrinking_pred (edge e)
1064 {
1065   if (cfg_hooks->execute_on_shrinking_pred)
1066     cfg_hooks->execute_on_shrinking_pred (e);
1067 }
1068
1069 /* This is used inside loop versioning when we want to insert
1070    stmts/insns on the edges, which have a different behavior
1071    in tree's and in RTL, so we made a CFG hook.  */
1072 void
1073 lv_flush_pending_stmts (edge e)
1074 {
1075   if (cfg_hooks->flush_pending_stmts)
1076     cfg_hooks->flush_pending_stmts (e);
1077 }
1078
1079 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1080    a new version of the loop basic-blocks, the parameters here are
1081    exactly the same as in duplicate_loop_to_header_edge or
1082    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1083    additional work to maintain ssa information that's why there is
1084    a need to call the tree_duplicate_loop_to_header_edge rather
1085    than duplicate_loop_to_header_edge when we are in tree mode.  */
1086 bool
1087 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1088                                         unsigned int ndupl,
1089                                         sbitmap wont_exit, edge orig,
1090                                         VEC (edge, heap) **to_remove,
1091                                         int flags)
1092 {
1093   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1094   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1095                                                             ndupl, wont_exit,
1096                                                             orig, to_remove,
1097                                                             flags);
1098 }
1099
1100 /* Conditional jumps are represented differently in trees and RTL,
1101    this hook takes a basic block that is known to have a cond jump
1102    at its end and extracts the taken and not taken edges out of it
1103    and store it in E1 and E2 respectively.  */
1104 void
1105 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1106 {
1107   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1108   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1109 }
1110
1111 /* Responsible for updating the ssa info (PHI nodes) on the
1112    new condition basic block that guards the versioned loop.  */
1113 void
1114 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1115                            basic_block new_block, edge e)
1116 {
1117   if (cfg_hooks->lv_adjust_loop_header_phi)
1118     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1119 }
1120
1121 /* Conditions in trees and RTL are different so we need
1122    a different handling when we add the condition to the
1123    versioning code.  */
1124 void
1125 lv_add_condition_to_bb (basic_block first, basic_block second,
1126                         basic_block new_block, void *cond)
1127 {
1128   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1129   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1130 }