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