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