gcc/cfghooks.c

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