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