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