gcc/cfghooks.c

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