gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
   3    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 "toplev.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 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
 429   if (!cfg_hooks->split_block)
 430     internal_error ("%s does not support split_block", cfg_hooks->name);
 431
 432   new_bb = cfg_hooks->split_block (bb, i);
 433   if (!new_bb)
 434     return NULL;
 435
 436   new_bb->count = bb->count;
 437   new_bb->frequency = bb->frequency;
 438   new_bb->loop_depth = bb->loop_depth;
 439
 440   if (dom_info_available_p (CDI_DOMINATORS))
 441     {
 442       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 443       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 444     }
 445
 446   if (current_loops != NULL)
 447     {
 448       add_bb_to_loop (new_bb, bb->loop_father);
 449       if (bb->loop_father->latch == bb)
 450         bb->loop_father->latch = new_bb;
 451     }
 452
 453   return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 454 }
 455
 456 /* Splits block BB just after labels.  The newly created edge is returned.  */
 457
 458 edge
 459 split_block_after_labels (basic_block bb)
 460 {
 461   return split_block (bb, NULL);
 462 }
 463
 464 /* Moves block BB immediately after block AFTER.  Returns false if the
 465    movement was impossible.  */
 466
 467 bool
 468 move_block_after (basic_block bb, basic_block after)
 469 {
 470   bool ret;
 471
 472   if (!cfg_hooks->move_block_after)
 473     internal_error ("%s does not support move_block_after", cfg_hooks->name);
 474
 475   ret = cfg_hooks->move_block_after (bb, after);
 476
 477   return ret;
 478 }
 479
 480 /* Deletes the basic block BB.  */
 481
 482 void
 483 delete_basic_block (basic_block bb)
 484 {
 485   if (!cfg_hooks->delete_basic_block)
 486     internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
 487
 488   cfg_hooks->delete_basic_block (bb);
 489
 490   if (current_loops != NULL)
 491     {
 492       struct loop *loop = bb->loop_father;
 493
 494       /* If we remove the header or the latch of a loop, mark the loop for
 495          removal by setting its header and latch to NULL.  */
 496       if (loop->latch == bb
 497           || loop->header == bb)
 498         {
 499           loop->header = NULL;
 500           loop->latch = NULL;
 501         }
 502
 503       remove_bb_from_loops (bb);
 504     }
 505
 506   /* Remove the edges into and out of this block.  Note that there may
 507      indeed be edges in, if we are removing an unreachable loop.  */
 508   while (EDGE_COUNT (bb->preds) != 0)
 509     remove_edge (EDGE_PRED (bb, 0));
 510   while (EDGE_COUNT (bb->succs) != 0)
 511     remove_edge (EDGE_SUCC (bb, 0));
 512
 513   if (dom_info_available_p (CDI_DOMINATORS))
 514     delete_from_dominance_info (CDI_DOMINATORS, bb);
 515   if (dom_info_available_p (CDI_POST_DOMINATORS))
 516     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 517
 518   /* Remove the basic block from the array.  */
 519   expunge_block (bb);
 520 }
 521
 522 /* Splits edge E and returns the newly created basic block.  */
 523
 524 basic_block
 525 split_edge (edge e)
 526 {
 527   basic_block ret;
 528   gcov_type count = e->count;
 529   int freq = EDGE_FREQUENCY (e);
 530   edge f;
 531   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
 532   struct loop *loop;
 533   basic_block src = e->src, dest = e->dest;
 534
 535   if (!cfg_hooks->split_edge)
 536     internal_error ("%s does not support split_edge", cfg_hooks->name);
 537
 538   if (current_loops != NULL)
 539     rescan_loop_exit (e, false, true);
 540
 541   ret = cfg_hooks->split_edge (e);
 542   ret->count = count;
 543   ret->frequency = freq;
 544   single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
 545   single_succ_edge (ret)->count = count;
 546
 547   if (irr)
 548     {
 549       ret->flags |= BB_IRREDUCIBLE_LOOP;
 550       single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 551       single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 552     }
 553
 554   if (dom_info_available_p (CDI_DOMINATORS))
 555     set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
 556
 557   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
 558     {
 559       /* There are two cases:
 560
 561          If the immediate dominator of e->dest is not e->src, it
 562          remains unchanged.
 563
 564          If immediate dominator of e->dest is e->src, it may become
 565          ret, provided that all other predecessors of e->dest are
 566          dominated by e->dest.  */
 567
 568       if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
 569           == single_pred (ret))
 570         {
 571           edge_iterator ei;
 572           FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
 573             {
 574               if (f == single_succ_edge (ret))
 575                 continue;
 576
 577               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 578                                    single_succ (ret)))
 579                 break;
 580             }
 581
 582           if (!f)
 583             set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
 584         }
 585     }
 586
 587   if (current_loops != NULL)
 588     {
 589       loop = find_common_loop (src->loop_father, dest->loop_father);
 590       add_bb_to_loop (ret, loop);
 591
 592       if (loop->latch == src)
 593         loop->latch = ret;
 594     }
 595
 596   return ret;
 597 }
 598
 599 /* Creates a new basic block just after the basic block AFTER.
 600    HEAD and END are the first and the last statement belonging
 601    to the block.  If both are NULL, an empty block is created.  */
 602
 603 basic_block
 604 create_basic_block (void *head, void *end, basic_block after)
 605 {
 606   basic_block ret;
 607
 608   if (!cfg_hooks->create_basic_block)
 609     internal_error ("%s does not support create_basic_block", cfg_hooks->name);
 610
 611   ret = cfg_hooks->create_basic_block (head, end, after);
 612
 613   if (dom_info_available_p (CDI_DOMINATORS))
 614     add_to_dominance_info (CDI_DOMINATORS, ret);
 615   if (dom_info_available_p (CDI_POST_DOMINATORS))
 616     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 617
 618   return ret;
 619 }
 620
 621 /* Creates an empty basic block just after basic block AFTER.  */
 622
 623 basic_block
 624 create_empty_bb (basic_block after)
 625 {
 626   return create_basic_block (NULL, NULL, after);
 627 }
 628
 629 /* Checks whether we may merge blocks BB1 and BB2.  */
 630
 631 bool
 632 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 633 {
 634   bool ret;
 635
 636   if (!cfg_hooks->can_merge_blocks_p)
 637     internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
 638
 639   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 640
 641   return ret;
 642 }
 643
 644 void
 645 predict_edge (edge e, enum br_predictor predictor, int probability)
 646 {
 647   if (!cfg_hooks->predict_edge)
 648     internal_error ("%s does not support predict_edge", cfg_hooks->name);
 649
 650   cfg_hooks->predict_edge (e, predictor, probability);
 651 }
 652
 653 bool
 654 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 655 {
 656   if (!cfg_hooks->predict_edge)
 657     internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
 658
 659   return cfg_hooks->predicted_by_p (bb, predictor);
 660 }
 661
 662 /* Merges basic block B into basic block A.  */
 663
 664 void
 665 merge_blocks (basic_block a, basic_block b)
 666 {
 667   edge e;
 668   edge_iterator ei;
 669
 670   if (!cfg_hooks->merge_blocks)
 671     internal_error ("%s does not support merge_blocks", cfg_hooks->name);
 672
 673   cfg_hooks->merge_blocks (a, b);
 674
 675   if (current_loops != NULL)
 676     remove_bb_from_loops (b);
 677
 678   /* Normally there should only be one successor of A and that is B, but
 679      partway though the merge of blocks for conditional_execution we'll
 680      be merging a TEST block with THEN and ELSE successors.  Free the
 681      whole lot of them and hope the caller knows what they're doing.  */
 682
 683   while (EDGE_COUNT (a->succs) != 0)
 684     remove_edge (EDGE_SUCC (a, 0));
 685
 686   /* Adjust the edges out of B for the new owner.  */
 687   FOR_EACH_EDGE (e, ei, b->succs)
 688     {
 689       e->src = a;
 690       if (current_loops != NULL)
 691         rescan_loop_exit (e, true, false);
 692     }
 693   a->succs = b->succs;
 694   a->flags |= b->flags;
 695
 696   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 697   b->preds = b->succs = NULL;
 698
 699   if (dom_info_available_p (CDI_DOMINATORS))
 700     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 701
 702   if (dom_info_available_p (CDI_DOMINATORS))
 703     delete_from_dominance_info (CDI_DOMINATORS, b);
 704   if (dom_info_available_p (CDI_POST_DOMINATORS))
 705     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 706
 707   expunge_block (b);
 708 }
 709
 710 /* Split BB into entry part and the rest (the rest is the newly created block).
 711    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 712    part.  Returns the edge connecting the entry part to the rest.  */
 713
 714 edge
 715 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 716                       void (*new_bb_cbk) (basic_block))
 717 {
 718   edge e, fallthru;
 719   edge_iterator ei;
 720   basic_block dummy, jump;
 721   struct loop *loop, *ploop, *cloop;
 722
 723   if (!cfg_hooks->make_forwarder_block)
 724     internal_error ("%s does not support make_forwarder_block",
 725                     cfg_hooks->name);
 726
 727   fallthru = split_block_after_labels (bb);
 728   dummy = fallthru->src;
 729   bb = fallthru->dest;
 730
 731   /* Redirect back edges we want to keep.  */
 732   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 733     {
 734       basic_block e_src;
 735
 736       if (redirect_edge_p (e))
 737         {
 738           ei_next (&ei);
 739           continue;
 740         }
 741
 742       dummy->frequency -= EDGE_FREQUENCY (e);
 743       dummy->count -= e->count;
 744       if (dummy->frequency < 0)
 745         dummy->frequency = 0;
 746       if (dummy->count < 0)
 747         dummy->count = 0;
 748       fallthru->count -= e->count;
 749       if (fallthru->count < 0)
 750         fallthru->count = 0;
 751
 752       e_src = e->src;
 753       jump = redirect_edge_and_branch_force (e, bb);
 754       if (jump != NULL)
 755         {
 756           /* If we redirected the loop latch edge, the JUMP block now acts like
 757              the new latch of the loop.  */
 758           if (current_loops != NULL
 759               && dummy->loop_father != NULL
 760               && dummy->loop_father->header == dummy
 761               && dummy->loop_father->latch == e_src)
 762             dummy->loop_father->latch = jump;
 763
 764           if (new_bb_cbk != NULL)
 765             new_bb_cbk (jump);
 766         }
 767     }
 768
 769   if (dom_info_available_p (CDI_DOMINATORS))
 770     {
 771       VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
 772       VEC_quick_push (basic_block, doms_to_fix, dummy);
 773       VEC_quick_push (basic_block, doms_to_fix, bb);
 774       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
 775       VEC_free (basic_block, heap, doms_to_fix);
 776     }
 777
 778   if (current_loops != NULL)
 779     {
 780       /* If we do not split a loop header, then both blocks belong to the
 781          same loop.  In case we split loop header and do not redirect the
 782          latch edge to DUMMY, then DUMMY belongs to the outer loop, and
 783          BB becomes the new header.  If latch is not recorded for the loop,
 784          we leave this updating on the caller (this may only happen during
 785          loop analysis).  */
 786       loop = dummy->loop_father;
 787       if (loop->header == dummy
 788           && loop->latch != NULL
 789           && find_edge (loop->latch, dummy) == NULL)
 790         {
 791           remove_bb_from_loops (dummy);
 792           loop->header = bb;
 793
 794           cloop = loop;
 795           FOR_EACH_EDGE (e, ei, dummy->preds)
 796             {
 797               cloop = find_common_loop (cloop, e->src->loop_father);
 798             }
 799           add_bb_to_loop (dummy, cloop);
 800         }
 801
 802       /* In case we split loop latch, update it.  */
 803       for (ploop = loop; ploop; ploop = loop_outer (ploop))
 804         if (ploop->latch == dummy)
 805           ploop->latch = bb;
 806     }
 807
 808   cfg_hooks->make_forwarder_block (fallthru);
 809
 810   return fallthru;
 811 }
 812
 813 void
 814 tidy_fallthru_edge (edge e)
 815 {
 816   if (cfg_hooks->tidy_fallthru_edge)
 817     cfg_hooks->tidy_fallthru_edge (e);
 818 }
 819
 820 /* Fix up edges that now fall through, or rather should now fall through
 821    but previously required a jump around now deleted blocks.  Simplify
 822    the search by only examining blocks numerically adjacent, since this
 823    is how find_basic_blocks created them.  */
 824
 825 void
 826 tidy_fallthru_edges (void)
 827 {
 828   basic_block b, c;
 829
 830   if (!cfg_hooks->tidy_fallthru_edge)
 831     return;
 832
 833   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 834     return;
 835
 836   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 837     {
 838       edge s;
 839
 840       c = b->next_bb;
 841
 842       /* We care about simple conditional or unconditional jumps with
 843          a single successor.
 844
 845          If we had a conditional branch to the next instruction when
 846          find_basic_blocks was called, then there will only be one
 847          out edge for the block which ended with the conditional
 848          branch (since we do not create duplicate edges).
 849
 850          Furthermore, the edge will be marked as a fallthru because we
 851          merge the flags for the duplicate edges.  So we do not want to
 852          check that the edge is not a FALLTHRU edge.  */
 853
 854       if (single_succ_p (b))
 855         {
 856           s = single_succ_edge (b);
 857           if (! (s->flags & EDGE_COMPLEX)
 858               && s->dest == c
 859               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 860             tidy_fallthru_edge (s);
 861         }
 862     }
 863 }
 864
 865 /* Returns true if we can duplicate basic block BB.  */
 866
 867 bool
 868 can_duplicate_block_p (const_basic_block bb)
 869 {
 870   if (!cfg_hooks->can_duplicate_block_p)
 871     internal_error ("%s does not support can_duplicate_block_p",
 872                     cfg_hooks->name);
 873
 874   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 875     return false;
 876
 877   return cfg_hooks->can_duplicate_block_p (bb);
 878 }
 879
 880 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 881    new basic block.  The new basic block is placed after the basic block
 882    AFTER.  */
 883
 884 basic_block
 885 duplicate_block (basic_block bb, edge e, basic_block after)
 886 {
 887   edge s, n;
 888   basic_block new_bb;
 889   gcov_type new_count = e ? e->count : 0;
 890   edge_iterator ei;
 891
 892   if (!cfg_hooks->duplicate_block)
 893     internal_error ("%s does not support duplicate_block",
 894                     cfg_hooks->name);
 895
 896   if (bb->count < new_count)
 897     new_count = bb->count;
 898
 899 #ifdef ENABLE_CHECKING
 900   gcc_assert (can_duplicate_block_p (bb));
 901 #endif
 902
 903   new_bb = cfg_hooks->duplicate_block (bb);
 904   if (after)
 905     move_block_after (new_bb, after);
 906
 907   new_bb->loop_depth = bb->loop_depth;
 908   new_bb->flags = bb->flags;
 909   FOR_EACH_EDGE (s, ei, bb->succs)
 910     {
 911       /* Since we are creating edges from a new block to successors
 912          of another block (which therefore are known to be disjoint), there
 913          is no need to actually check for duplicated edges.  */
 914       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 915       n->probability = s->probability;
 916       if (e && bb->count)
 917         {
 918           /* Take care for overflows!  */
 919           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 920           s->count -= n->count;
 921         }
 922       else
 923         n->count = s->count;
 924       n->aux = s->aux;
 925     }
 926
 927   if (e)
 928     {
 929       new_bb->count = new_count;
 930       bb->count -= new_count;
 931
 932       new_bb->frequency = EDGE_FREQUENCY (e);
 933       bb->frequency -= EDGE_FREQUENCY (e);
 934
 935       redirect_edge_and_branch_force (e, new_bb);
 936
 937       if (bb->count < 0)
 938         bb->count = 0;
 939       if (bb->frequency < 0)
 940         bb->frequency = 0;
 941     }
 942   else
 943     {
 944       new_bb->count = bb->count;
 945       new_bb->frequency = bb->frequency;
 946     }
 947
 948   set_bb_original (new_bb, bb);
 949   set_bb_copy (bb, new_bb);
 950
 951   /* Add the new block to the copy of the loop of BB, or directly to the loop
 952      of BB if the loop is not being copied.  */
 953   if (current_loops != NULL)
 954     {
 955       struct loop *cloop = bb->loop_father;
 956       struct loop *copy = get_loop_copy (cloop);
 957       add_bb_to_loop (new_bb, copy ? copy : cloop);
 958     }
 959
 960   return new_bb;
 961 }
 962
 963 /* Return 1 if BB ends with a call, possibly followed by some
 964    instructions that must stay with the call, 0 otherwise.  */
 965
 966 bool
 967 block_ends_with_call_p (basic_block bb)
 968 {
 969   if (!cfg_hooks->block_ends_with_call_p)
 970     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
 971
 972   return (cfg_hooks->block_ends_with_call_p) (bb);
 973 }
 974
 975 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
 976
 977 bool
 978 block_ends_with_condjump_p (const_basic_block bb)
 979 {
 980   if (!cfg_hooks->block_ends_with_condjump_p)
 981     internal_error ("%s does not support block_ends_with_condjump_p",
 982                     cfg_hooks->name);
 983
 984   return (cfg_hooks->block_ends_with_condjump_p) (bb);
 985 }
 986
 987 /* Add fake edges to the function exit for any non constant and non noreturn
 988    calls, volatile inline assembly in the bitmap of blocks specified by
 989    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 990    that were split.
 991
 992    The goal is to expose cases in which entering a basic block does not imply
 993    that all subsequent instructions must be executed.  */
 994
 995 int
 996 flow_call_edges_add (sbitmap blocks)
 997 {
 998   if (!cfg_hooks->flow_call_edges_add)
 999     internal_error ("%s does not support flow_call_edges_add",
1000                     cfg_hooks->name);
1001
1002   return (cfg_hooks->flow_call_edges_add) (blocks);
1003 }
1004
1005 /* This function is called immediately after edge E is added to the
1006    edge vector E->dest->preds.  */
1007
1008 void
1009 execute_on_growing_pred (edge e)
1010 {
1011   if (cfg_hooks->execute_on_growing_pred)
1012     cfg_hooks->execute_on_growing_pred (e);
1013 }
1014
1015 /* This function is called immediately before edge E is removed from
1016    the edge vector E->dest->preds.  */
1017
1018 void
1019 execute_on_shrinking_pred (edge e)
1020 {
1021   if (cfg_hooks->execute_on_shrinking_pred)
1022     cfg_hooks->execute_on_shrinking_pred (e);
1023 }
1024
1025 /* This is used inside loop versioning when we want to insert
1026    stmts/insns on the edges, which have a different behavior
1027    in tree's and in RTL, so we made a CFG hook.  */
1028 void
1029 lv_flush_pending_stmts (edge e)
1030 {
1031   if (cfg_hooks->flush_pending_stmts)
1032     cfg_hooks->flush_pending_stmts (e);
1033 }
1034
1035 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1036    a new version of the loop basic-blocks, the parameters here are
1037    exactly the same as in duplicate_loop_to_header_edge or
1038    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1039    additional work to maintain ssa information that's why there is
1040    a need to call the tree_duplicate_loop_to_header_edge rather
1041    than duplicate_loop_to_header_edge when we are in tree mode.  */
1042 bool
1043 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1044                                         unsigned int ndupl,
1045                                         sbitmap wont_exit, edge orig,
1046                                         VEC (edge, heap) **to_remove,
1047                                         int flags)
1048 {
1049   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1050   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1051                                                             ndupl, wont_exit,
1052                                                             orig, to_remove,
1053                                                             flags);
1054 }
1055
1056 /* Conditional jumps are represented differently in trees and RTL,
1057    this hook takes a basic block that is known to have a cond jump
1058    at its end and extracts the taken and not taken edges out of it
1059    and store it in E1 and E2 respectively.  */
1060 void
1061 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1062 {
1063   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1064   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1065 }
1066
1067 /* Responsible for updating the ssa info (PHI nodes) on the
1068    new condition basic block that guards the versioned loop.  */
1069 void
1070 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1071                            basic_block new_block, edge e)
1072 {
1073   if (cfg_hooks->lv_adjust_loop_header_phi)
1074     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1075 }
1076
1077 /* Conditions in trees and RTL are different so we need
1078    a different handling when we add the condition to the
1079    versioning code.  */
1080 void
1081 lv_add_condition_to_bb (basic_block first, basic_block second,
1082                         basic_block new_block, void *cond)
1083 {
1084   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1085   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1086 }