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