gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
   3    Inc.
   4    Contributed by Sebastian Pop <s.pop@laposte.net>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "rtl.h"
  28 #include "basic-block.h"
  29 #include "tree-flow.h"
  30 #include "timevar.h"
  31 #include "toplev.h"
  32 #include "cfgloop.h"
  33
  34 /* A pointer to one of the hooks containers.  */
  35 static struct cfg_hooks *cfg_hooks;
  36
  37 /* Initialization of functions specific to the rtl IR.  */
  38 void
  39 rtl_register_cfg_hooks (void)
  40 {
  41   cfg_hooks = &rtl_cfg_hooks;
  42 }
  43
  44 /* Initialization of functions specific to the rtl IR.  */
  45 void
  46 cfg_layout_rtl_register_cfg_hooks (void)
  47 {
  48   cfg_hooks = &cfg_layout_rtl_cfg_hooks;
  49 }
  50
  51 /* Initialization of functions specific to the tree IR.  */
  52
  53 void
  54 gimple_register_cfg_hooks (void)
  55 {
  56   cfg_hooks = &gimple_cfg_hooks;
  57 }
  58
  59 /* Returns current ir type.  */
  60
  61 enum ir_type
  62 current_ir_type (void)
  63 {
  64   if (cfg_hooks == &gimple_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 = (char *) 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, 0);
 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 either the redirection failed, or the edge E
 314      was removed since RET already lead to the same destination.  */
 315   if (current_loops != NULL && ret == e)
 316     rescan_loop_exit (e, false, false);
 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 (const_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   e = redirect_edge_and_branch (e, other->dest);
 354   gcc_assert (e != NULL);
 355
 356   e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 357   e->flags |= irr;
 358 }
 359
 360 /* Removes edge E from cfg.  Unlike remove_branch, it does not update IL.  */
 361
 362 void
 363 remove_edge (edge e)
 364 {
 365   if (current_loops != NULL)
 366     rescan_loop_exit (e, false, true);
 367
 368   remove_edge_raw (e);
 369 }
 370
 371 /* Redirect the edge E to basic block DEST even if it requires creating
 372    of a new basic block; then it returns the newly created basic block.
 373    Aborts when redirection is impossible.  */
 374
 375 basic_block
 376 redirect_edge_and_branch_force (edge e, basic_block dest)
 377 {
 378   basic_block ret, src = e->src;
 379   struct loop *loop;
 380
 381   if (!cfg_hooks->redirect_edge_and_branch_force)
 382     internal_error ("%s does not support redirect_edge_and_branch_force",
 383                     cfg_hooks->name);
 384
 385   if (current_loops != NULL)
 386     rescan_loop_exit (e, false, true);
 387
 388   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 389   if (ret != NULL
 390       && dom_info_available_p (CDI_DOMINATORS))
 391     set_immediate_dominator (CDI_DOMINATORS, ret, src);
 392
 393   if (current_loops != NULL)
 394     {
 395       if (ret != NULL)
 396         {
 397           loop = find_common_loop (single_pred (ret)->loop_father,
 398                                    single_succ (ret)->loop_father);
 399           add_bb_to_loop (ret, loop);
 400         }
 401       else if (find_edge (src, dest) == e)
 402         rescan_loop_exit (e, true, false);
 403     }
 404
 405   return ret;
 406 }
 407
 408 /* Splits basic block BB after the specified instruction I (but at least after
 409    the labels).  If I is NULL, splits just after labels.  The newly created edge
 410    is returned.  The new basic block is created just after the old one.  */
 411
 412 edge
 413 split_block (basic_block bb, void *i)
 414 {
 415   basic_block new_bb;
 416
 417   if (!cfg_hooks->split_block)
 418     internal_error ("%s does not support split_block", cfg_hooks->name);
 419
 420   new_bb = cfg_hooks->split_block (bb, i);
 421   if (!new_bb)
 422     return NULL;
 423
 424   new_bb->count = bb->count;
 425   new_bb->frequency = bb->frequency;
 426   new_bb->loop_depth = bb->loop_depth;
 427
 428   if (dom_info_available_p (CDI_DOMINATORS))
 429     {
 430       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 431       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 432     }
 433
 434   if (current_loops != NULL)
 435     {
 436       add_bb_to_loop (new_bb, bb->loop_father);
 437       if (bb->loop_father->latch == bb)
 438         bb->loop_father->latch = new_bb;
 439     }
 440
 441   return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 442 }
 443
 444 /* Splits block BB just after labels.  The newly created edge is returned.  */
 445
 446 edge
 447 split_block_after_labels (basic_block bb)
 448 {
 449   return split_block (bb, NULL);
 450 }
 451
 452 /* Moves block BB immediately after block AFTER.  Returns false if the
 453    movement was impossible.  */
 454
 455 bool
 456 move_block_after (basic_block bb, basic_block after)
 457 {
 458   bool ret;
 459
 460   if (!cfg_hooks->move_block_after)
 461     internal_error ("%s does not support move_block_after", cfg_hooks->name);
 462
 463   ret = cfg_hooks->move_block_after (bb, after);
 464
 465   return ret;
 466 }
 467
 468 /* Deletes the basic block BB.  */
 469
 470 void
 471 delete_basic_block (basic_block bb)
 472 {
 473   if (!cfg_hooks->delete_basic_block)
 474     internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
 475
 476   cfg_hooks->delete_basic_block (bb);
 477
 478   if (current_loops != NULL)
 479     {
 480       struct loop *loop = bb->loop_father;
 481
 482       /* If we remove the header or the latch of a loop, mark the loop for
 483          removal by setting its header and latch to NULL.  */
 484       if (loop->latch == bb
 485           || loop->header == bb)
 486         {
 487           loop->header = NULL;
 488           loop->latch = NULL;
 489         }
 490
 491       remove_bb_from_loops (bb);
 492     }
 493
 494   /* Remove the edges into and out of this block.  Note that there may
 495      indeed be edges in, if we are removing an unreachable loop.  */
 496   while (EDGE_COUNT (bb->preds) != 0)
 497     remove_edge (EDGE_PRED (bb, 0));
 498   while (EDGE_COUNT (bb->succs) != 0)
 499     remove_edge (EDGE_SUCC (bb, 0));
 500
 501   if (dom_info_available_p (CDI_DOMINATORS))
 502     delete_from_dominance_info (CDI_DOMINATORS, bb);
 503   if (dom_info_available_p (CDI_POST_DOMINATORS))
 504     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 505
 506   /* Remove the basic block from the array.  */
 507   expunge_block (bb);
 508 }
 509
 510 /* Splits edge E and returns the newly created basic block.  */
 511
 512 basic_block
 513 split_edge (edge e)
 514 {
 515   basic_block ret;
 516   gcov_type count = e->count;
 517   int freq = EDGE_FREQUENCY (e);
 518   edge f;
 519   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
 520   struct loop *loop;
 521   basic_block src = e->src, dest = e->dest;
 522
 523   if (!cfg_hooks->split_edge)
 524     internal_error ("%s does not support split_edge", cfg_hooks->name);
 525
 526   if (current_loops != NULL)
 527     rescan_loop_exit (e, false, true);
 528
 529   ret = cfg_hooks->split_edge (e);
 530   ret->count = count;
 531   ret->frequency = freq;
 532   single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
 533   single_succ_edge (ret)->count = count;
 534
 535   if (irr)
 536     {
 537       ret->flags |= BB_IRREDUCIBLE_LOOP;
 538       single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 539       single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 540     }
 541
 542   if (dom_info_available_p (CDI_DOMINATORS))
 543     set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
 544
 545   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
 546     {
 547       /* There are two cases:
 548
 549          If the immediate dominator of e->dest is not e->src, it
 550          remains unchanged.
 551
 552          If immediate dominator of e->dest is e->src, it may become
 553          ret, provided that all other predecessors of e->dest are
 554          dominated by e->dest.  */
 555
 556       if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
 557           == single_pred (ret))
 558         {
 559           edge_iterator ei;
 560           FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
 561             {
 562               if (f == single_succ_edge (ret))
 563                 continue;
 564
 565               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 566                                    single_succ (ret)))
 567                 break;
 568             }
 569
 570           if (!f)
 571             set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
 572         }
 573     }
 574
 575   if (current_loops != NULL)
 576     {
 577       loop = find_common_loop (src->loop_father, dest->loop_father);
 578       add_bb_to_loop (ret, loop);
 579
 580       if (loop->latch == src)
 581         loop->latch = ret;
 582     }
 583
 584   return ret;
 585 }
 586
 587 /* Creates a new basic block just after the basic block AFTER.
 588    HEAD and END are the first and the last statement belonging
 589    to the block.  If both are NULL, an empty block is created.  */
 590
 591 basic_block
 592 create_basic_block (void *head, void *end, basic_block after)
 593 {
 594   basic_block ret;
 595
 596   if (!cfg_hooks->create_basic_block)
 597     internal_error ("%s does not support create_basic_block", cfg_hooks->name);
 598
 599   ret = cfg_hooks->create_basic_block (head, end, after);
 600
 601   if (dom_info_available_p (CDI_DOMINATORS))
 602     add_to_dominance_info (CDI_DOMINATORS, ret);
 603   if (dom_info_available_p (CDI_POST_DOMINATORS))
 604     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 605
 606   return ret;
 607 }
 608
 609 /* Creates an empty basic block just after basic block AFTER.  */
 610
 611 basic_block
 612 create_empty_bb (basic_block after)
 613 {
 614   return create_basic_block (NULL, NULL, after);
 615 }
 616
 617 /* Checks whether we may merge blocks BB1 and BB2.  */
 618
 619 bool
 620 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 621 {
 622   bool ret;
 623
 624   if (!cfg_hooks->can_merge_blocks_p)
 625     internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
 626
 627   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 628
 629   return ret;
 630 }
 631
 632 void
 633 predict_edge (edge e, enum br_predictor predictor, int probability)
 634 {
 635   if (!cfg_hooks->predict_edge)
 636     internal_error ("%s does not support predict_edge", cfg_hooks->name);
 637
 638   cfg_hooks->predict_edge (e, predictor, probability);
 639 }
 640
 641 bool
 642 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 643 {
 644   if (!cfg_hooks->predict_edge)
 645     internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
 646
 647   return cfg_hooks->predicted_by_p (bb, predictor);
 648 }
 649
 650 /* Merges basic block B into basic block A.  */
 651
 652 void
 653 merge_blocks (basic_block a, basic_block b)
 654 {
 655   edge e;
 656   edge_iterator ei;
 657
 658   if (!cfg_hooks->merge_blocks)
 659     internal_error ("%s does not support merge_blocks", cfg_hooks->name);
 660
 661   cfg_hooks->merge_blocks (a, b);
 662
 663   if (current_loops != NULL)
 664     remove_bb_from_loops (b);
 665
 666   /* Normally there should only be one successor of A and that is B, but
 667      partway though the merge of blocks for conditional_execution we'll
 668      be merging a TEST block with THEN and ELSE successors.  Free the
 669      whole lot of them and hope the caller knows what they're doing.  */
 670
 671   while (EDGE_COUNT (a->succs) != 0)
 672     remove_edge (EDGE_SUCC (a, 0));
 673
 674   /* Adjust the edges out of B for the new owner.  */
 675   FOR_EACH_EDGE (e, ei, b->succs)
 676     {
 677       e->src = a;
 678       if (current_loops != NULL)
 679         rescan_loop_exit (e, true, false);
 680     }
 681   a->succs = b->succs;
 682   a->flags |= b->flags;
 683
 684   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 685   b->preds = b->succs = NULL;
 686
 687   if (dom_info_available_p (CDI_DOMINATORS))
 688     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 689
 690   if (dom_info_available_p (CDI_DOMINATORS))
 691     delete_from_dominance_info (CDI_DOMINATORS, b);
 692   if (dom_info_available_p (CDI_POST_DOMINATORS))
 693     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 694
 695   expunge_block (b);
 696 }
 697
 698 /* Split BB into entry part and the rest (the rest is the newly created block).
 699    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 700    part.  Returns the edge connecting the entry part to the rest.  */
 701
 702 edge
 703 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 704                       void (*new_bb_cbk) (basic_block))
 705 {
 706   edge e, fallthru;
 707   edge_iterator ei;
 708   basic_block dummy, jump;
 709   struct loop *loop, *ploop, *cloop;
 710
 711   if (!cfg_hooks->make_forwarder_block)
 712     internal_error ("%s does not support make_forwarder_block",
 713                     cfg_hooks->name);
 714
 715   fallthru = split_block_after_labels (bb);
 716   dummy = fallthru->src;
 717   bb = fallthru->dest;
 718
 719   /* Redirect back edges we want to keep.  */
 720   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 721     {
 722       if (redirect_edge_p (e))
 723         {
 724           ei_next (&ei);
 725           continue;
 726         }
 727
 728       dummy->frequency -= EDGE_FREQUENCY (e);
 729       dummy->count -= e->count;
 730       if (dummy->frequency < 0)
 731         dummy->frequency = 0;
 732       if (dummy->count < 0)
 733         dummy->count = 0;
 734       fallthru->count -= e->count;
 735       if (fallthru->count < 0)
 736         fallthru->count = 0;
 737
 738       jump = redirect_edge_and_branch_force (e, bb);
 739       if (jump != NULL
 740           && new_bb_cbk != NULL)
 741         new_bb_cbk (jump);
 742     }
 743
 744   if (dom_info_available_p (CDI_DOMINATORS))
 745     {
 746       VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
 747       VEC_quick_push (basic_block, doms_to_fix, dummy);
 748       VEC_quick_push (basic_block, doms_to_fix, bb);
 749       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
 750       VEC_free (basic_block, heap, doms_to_fix);
 751     }
 752
 753   if (current_loops != NULL)
 754     {
 755       /* If we do not split a loop header, then both blocks belong to the
 756          same loop.  In case we split loop header and do not redirect the
 757          latch edge to DUMMY, then DUMMY belongs to the outer loop, and
 758          BB becomes the new header.  If latch is not recorded for the loop,
 759          we leave this updating on the caller (this may only happen during
 760          loop analysis).  */
 761       loop = dummy->loop_father;
 762       if (loop->header == dummy
 763           && loop->latch != NULL
 764           && find_edge (loop->latch, dummy) == NULL)
 765         {
 766           remove_bb_from_loops (dummy);
 767           loop->header = bb;
 768
 769           cloop = loop;
 770           FOR_EACH_EDGE (e, ei, dummy->preds)
 771             {
 772               cloop = find_common_loop (cloop, e->src->loop_father);
 773             }
 774           add_bb_to_loop (dummy, cloop);
 775         }
 776
 777       /* In case we split loop latch, update it.  */
 778       for (ploop = loop; ploop; ploop = loop_outer (ploop))
 779         if (ploop->latch == dummy)
 780           ploop->latch = bb;
 781     }
 782
 783   cfg_hooks->make_forwarder_block (fallthru);
 784
 785   return fallthru;
 786 }
 787
 788 void
 789 tidy_fallthru_edge (edge e)
 790 {
 791   if (cfg_hooks->tidy_fallthru_edge)
 792     cfg_hooks->tidy_fallthru_edge (e);
 793 }
 794
 795 /* Fix up edges that now fall through, or rather should now fall through
 796    but previously required a jump around now deleted blocks.  Simplify
 797    the search by only examining blocks numerically adjacent, since this
 798    is how find_basic_blocks created them.  */
 799
 800 void
 801 tidy_fallthru_edges (void)
 802 {
 803   basic_block b, c;
 804
 805   if (!cfg_hooks->tidy_fallthru_edge)
 806     return;
 807
 808   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 809     return;
 810
 811   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 812     {
 813       edge s;
 814
 815       c = b->next_bb;
 816
 817       /* We care about simple conditional or unconditional jumps with
 818          a single successor.
 819
 820          If we had a conditional branch to the next instruction when
 821          find_basic_blocks was called, then there will only be one
 822          out edge for the block which ended with the conditional
 823          branch (since we do not create duplicate edges).
 824
 825          Furthermore, the edge will be marked as a fallthru because we
 826          merge the flags for the duplicate edges.  So we do not want to
 827          check that the edge is not a FALLTHRU edge.  */
 828
 829       if (single_succ_p (b))
 830         {
 831           s = single_succ_edge (b);
 832           if (! (s->flags & EDGE_COMPLEX)
 833               && s->dest == c
 834               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 835             tidy_fallthru_edge (s);
 836         }
 837     }
 838 }
 839
 840 /* Returns true if we can duplicate basic block BB.  */
 841
 842 bool
 843 can_duplicate_block_p (const_basic_block bb)
 844 {
 845   if (!cfg_hooks->can_duplicate_block_p)
 846     internal_error ("%s does not support can_duplicate_block_p",
 847                     cfg_hooks->name);
 848
 849   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 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 copy of the loop of BB, or directly to the loop
 927      of BB if the loop is not being copied.  */
 928   if (current_loops != NULL)
 929     {
 930       struct loop *cloop = bb->loop_father;
 931       struct loop *copy = get_loop_copy (cloop);
 932       add_bb_to_loop (new_bb, copy ? copy : cloop);
 933     }
 934
 935   return new_bb;
 936 }
 937
 938 /* Return 1 if BB ends with a call, possibly followed by some
 939    instructions that must stay with the call, 0 otherwise.  */
 940
 941 bool
 942 block_ends_with_call_p (basic_block bb)
 943 {
 944   if (!cfg_hooks->block_ends_with_call_p)
 945     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
 946
 947   return (cfg_hooks->block_ends_with_call_p) (bb);
 948 }
 949
 950 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
 951
 952 bool
 953 block_ends_with_condjump_p (const_basic_block bb)
 954 {
 955   if (!cfg_hooks->block_ends_with_condjump_p)
 956     internal_error ("%s does not support block_ends_with_condjump_p",
 957                     cfg_hooks->name);
 958
 959   return (cfg_hooks->block_ends_with_condjump_p) (bb);
 960 }
 961
 962 /* Add fake edges to the function exit for any non constant and non noreturn
 963    calls, volatile inline assembly in the bitmap of blocks specified by
 964    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 965    that were split.
 966
 967    The goal is to expose cases in which entering a basic block does not imply
 968    that all subsequent instructions must be executed.  */
 969
 970 int
 971 flow_call_edges_add (sbitmap blocks)
 972 {
 973   if (!cfg_hooks->flow_call_edges_add)
 974     internal_error ("%s does not support flow_call_edges_add",
 975                     cfg_hooks->name);
 976
 977   return (cfg_hooks->flow_call_edges_add) (blocks);
 978 }
 979
 980 /* This function is called immediately after edge E is added to the
 981    edge vector E->dest->preds.  */
 982
 983 void
 984 execute_on_growing_pred (edge e)
 985 {
 986   if (cfg_hooks->execute_on_growing_pred)
 987     cfg_hooks->execute_on_growing_pred (e);
 988 }
 989
 990 /* This function is called immediately before edge E is removed from
 991    the edge vector E->dest->preds.  */
 992
 993 void
 994 execute_on_shrinking_pred (edge e)
 995 {
 996   if (cfg_hooks->execute_on_shrinking_pred)
 997     cfg_hooks->execute_on_shrinking_pred (e);
 998 }
 999
1000 /* This is used inside loop versioning when we want to insert
1001    stmts/insns on the edges, which have a different behavior
1002    in tree's and in RTL, so we made a CFG hook.  */
1003 void
1004 lv_flush_pending_stmts (edge e)
1005 {
1006   if (cfg_hooks->flush_pending_stmts)
1007     cfg_hooks->flush_pending_stmts (e);
1008 }
1009
1010 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1011    a new version of the loop basic-blocks, the parameters here are
1012    exactly the same as in duplicate_loop_to_header_edge or
1013    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1014    additional work to maintain ssa information that's why there is
1015    a need to call the tree_duplicate_loop_to_header_edge rather
1016    than duplicate_loop_to_header_edge when we are in tree mode.  */
1017 bool
1018 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1019                                         unsigned int ndupl,
1020                                         sbitmap wont_exit, edge orig,
1021                                         VEC (edge, heap) **to_remove,
1022                                         int flags)
1023 {
1024   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1025   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1026                                                             ndupl, wont_exit,
1027                                                             orig, to_remove,
1028                                                             flags);
1029 }
1030
1031 /* Conditional jumps are represented differently in trees and RTL,
1032    this hook takes a basic block that is known to have a cond jump
1033    at its end and extracts the taken and not taken edges out of it
1034    and store it in E1 and E2 respectively.  */
1035 void
1036 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1037 {
1038   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1039   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1040 }
1041
1042 /* Responsible for updating the ssa info (PHI nodes) on the
1043    new condition basic block that guards the versioned loop.  */
1044 void
1045 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1046                            basic_block new_block, edge e)
1047 {
1048   if (cfg_hooks->lv_adjust_loop_header_phi)
1049     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1050 }
1051
1052 /* Conditions in trees and RTL are different so we need
1053    a different handling when we add the condition to the
1054    versioning code.  */
1055 void
1056 lv_add_condition_to_bb (basic_block first, basic_block second,
1057                         basic_block new_block, void *cond)
1058 {
1059   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1060   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1061 }