gcc/cfghooks.c

   1 /* Hooks for cfg representation specific functions.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Sebastian Pop <s.pop@laposte.net>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "dumpfile.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "basic-block.h"
  30 #include "tree-flow.h"
  31 #include "timevar.h"
  32 #include "diagnostic-core.h"
  33 #include "cfgloop.h"
  34
  35 /* A pointer to one of the hooks containers.  */
  36 static struct cfg_hooks *cfg_hooks;
  37
  38 /* Initialization of functions specific to the rtl IR.  */
  39 void
  40 rtl_register_cfg_hooks (void)
  41 {
  42   cfg_hooks = &rtl_cfg_hooks;
  43 }
  44
  45 /* Initialization of functions specific to the rtl IR.  */
  46 void
  47 cfg_layout_rtl_register_cfg_hooks (void)
  48 {
  49   cfg_hooks = &cfg_layout_rtl_cfg_hooks;
  50 }
  51
  52 /* Initialization of functions specific to the tree IR.  */
  53
  54 void
  55 gimple_register_cfg_hooks (void)
  56 {
  57   cfg_hooks = &gimple_cfg_hooks;
  58 }
  59
  60 struct cfg_hooks
  61 get_cfg_hooks (void)
  62 {
  63   return *cfg_hooks;
  64 }
  65
  66 void
  67 set_cfg_hooks (struct cfg_hooks new_cfg_hooks)
  68 {
  69   *cfg_hooks = new_cfg_hooks;
  70 }
  71
  72 /* Returns current ir type.  */
  73
  74 enum ir_type
  75 current_ir_type (void)
  76 {
  77   if (cfg_hooks == &gimple_cfg_hooks)
  78     return IR_GIMPLE;
  79   else if (cfg_hooks == &rtl_cfg_hooks)
  80     return IR_RTL_CFGRTL;
  81   else if (cfg_hooks == &cfg_layout_rtl_cfg_hooks)
  82     return IR_RTL_CFGLAYOUT;
  83   else
  84     gcc_unreachable ();
  85 }
  86
  87 /* Verify the CFG consistency.
  88
  89    Currently it does following: checks edge and basic block list correctness
  90    and calls into IL dependent checking then.  */
  91
  92 DEBUG_FUNCTION void
  93 verify_flow_info (void)
  94 {
  95   size_t *edge_checksum;
  96   int err = 0;
  97   basic_block bb, last_bb_seen;
  98   basic_block *last_visited;
  99
 100   timevar_push (TV_CFG_VERIFY);
 101   last_visited = XCNEWVEC (basic_block, last_basic_block);
 102   edge_checksum = XCNEWVEC (size_t, last_basic_block);
 103
 104   /* Check bb chain & numbers.  */
 105   last_bb_seen = ENTRY_BLOCK_PTR;
 106   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 107     {
 108       if (bb != EXIT_BLOCK_PTR
 109           && bb != BASIC_BLOCK (bb->index))
 110         {
 111           error ("bb %d on wrong place", bb->index);
 112           err = 1;
 113         }
 114
 115       if (bb->prev_bb != last_bb_seen)
 116         {
 117           error ("prev_bb of %d should be %d, not %d",
 118                  bb->index, last_bb_seen->index, bb->prev_bb->index);
 119           err = 1;
 120         }
 121
 122       last_bb_seen = bb;
 123     }
 124
 125   /* Now check the basic blocks (boundaries etc.) */
 126   FOR_EACH_BB_REVERSE (bb)
 127     {
 128       int n_fallthru = 0;
 129       edge e;
 130       edge_iterator ei;
 131
 132       if (bb->loop_father != NULL && current_loops == NULL)
 133         {
 134           error ("verify_flow_info: Block %i has loop_father, but there are no loops",
 135                  bb->index);
 136           err = 1;
 137         }
 138       if (bb->loop_father == NULL && current_loops != NULL)
 139         {
 140           error ("verify_flow_info: Block %i lacks loop_father", bb->index);
 141           err = 1;
 142         }
 143
 144       if (bb->count < 0)
 145         {
 146           error ("verify_flow_info: Wrong count of block %i %i",
 147                  bb->index, (int)bb->count);
 148           err = 1;
 149         }
 150       if (bb->frequency < 0)
 151         {
 152           error ("verify_flow_info: Wrong frequency of block %i %i",
 153                  bb->index, bb->frequency);
 154           err = 1;
 155         }
 156       FOR_EACH_EDGE (e, ei, bb->succs)
 157         {
 158           if (last_visited [e->dest->index] == bb)
 159             {
 160               error ("verify_flow_info: Duplicate edge %i->%i",
 161                      e->src->index, e->dest->index);
 162               err = 1;
 163             }
 164           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 165             {
 166               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 167                      e->src->index, e->dest->index, e->probability);
 168               err = 1;
 169             }
 170           if (e->count < 0)
 171             {
 172               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 173                      e->src->index, e->dest->index, (int)e->count);
 174               err = 1;
 175             }
 176
 177           last_visited [e->dest->index] = bb;
 178
 179           if (e->flags & EDGE_FALLTHRU)
 180             n_fallthru++;
 181
 182           if (e->src != bb)
 183             {
 184               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 185                      bb->index);
 186               fprintf (stderr, "Predecessor: ");
 187               dump_edge_info (stderr, e, TDF_DETAILS, 0);
 188               fprintf (stderr, "\nSuccessor: ");
 189               dump_edge_info (stderr, e, TDF_DETAILS, 1);
 190               fprintf (stderr, "\n");
 191               err = 1;
 192             }
 193
 194           edge_checksum[e->dest->index] += (size_t) e;
 195         }
 196       if (n_fallthru > 1)
 197         {
 198           error ("wrong amount of branch edges after unconditional jump %i", bb->index);
 199           err = 1;
 200         }
 201
 202       FOR_EACH_EDGE (e, ei, bb->preds)
 203         {
 204           if (e->dest != bb)
 205             {
 206               error ("basic block %d pred edge is corrupted", bb->index);
 207               fputs ("Predecessor: ", stderr);
 208               dump_edge_info (stderr, e, TDF_DETAILS, 0);
 209               fputs ("\nSuccessor: ", stderr);
 210               dump_edge_info (stderr, e, TDF_DETAILS, 1);
 211               fputc ('\n', stderr);
 212               err = 1;
 213             }
 214
 215           if (ei.index != e->dest_idx)
 216             {
 217               error ("basic block %d pred edge is corrupted", bb->index);
 218               error ("its dest_idx should be %d, not %d",
 219                      ei.index, e->dest_idx);
 220               fputs ("Predecessor: ", stderr);
 221               dump_edge_info (stderr, e, TDF_DETAILS, 0);
 222               fputs ("\nSuccessor: ", stderr);
 223               dump_edge_info (stderr, e, TDF_DETAILS, 1);
 224               fputc ('\n', stderr);
 225               err = 1;
 226             }
 227
 228           edge_checksum[e->dest->index] -= (size_t) e;
 229         }
 230     }
 231
 232   /* Complete edge checksumming for ENTRY and EXIT.  */
 233   {
 234     edge e;
 235     edge_iterator ei;
 236
 237     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 238       edge_checksum[e->dest->index] += (size_t) e;
 239
 240     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 241       edge_checksum[e->dest->index] -= (size_t) e;
 242   }
 243
 244   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 245     if (edge_checksum[bb->index])
 246       {
 247         error ("basic block %i edge lists are corrupted", bb->index);
 248         err = 1;
 249       }
 250
 251   last_bb_seen = ENTRY_BLOCK_PTR;
 252
 253   /* Clean up.  */
 254   free (last_visited);
 255   free (edge_checksum);
 256
 257   if (cfg_hooks->verify_flow_info)
 258     err |= cfg_hooks->verify_flow_info ();
 259   if (err)
 260     internal_error ("verify_flow_info failed");
 261   timevar_pop (TV_CFG_VERIFY);
 262 }
 263
 264 /* Print out one basic block BB to file OUTF.  INDENT is printed at the
 265    start of each new line.  FLAGS are the TDF_* flags in dumpfile.h.
 266
 267    This function takes care of the purely graph related information.
 268    The cfg hook for the active representation should dump
 269    representation-specific information.  */
 270
 271 void
 272 dump_bb (FILE *outf, basic_block bb, int indent, int flags)
 273 {
 274   if (flags & TDF_BLOCKS)
 275     dump_bb_info (outf, bb, indent, flags, true, false);
 276   if (cfg_hooks->dump_bb)
 277     cfg_hooks->dump_bb (outf, bb, indent, flags);
 278   if (flags & TDF_BLOCKS)
 279     dump_bb_info (outf, bb, indent, flags, false, true);
 280   fputc ('\n', outf);
 281 }
 282
 283 /* Dump the complete CFG to FILE.  FLAGS are the TDF_* flags in dumpfile.h.  */
 284 void
 285 dump_flow_info (FILE *file, int flags)
 286 {
 287   basic_block bb;
 288
 289   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 290   FOR_ALL_BB (bb)
 291     dump_bb (file, bb, 0, flags);
 292
 293   putc ('\n', file);
 294 }
 295
 296 /* Like above, but dump to stderr.  To be called from debuggers.  */
 297 void debug_flow_info (void);
 298 DEBUG_FUNCTION void
 299 debug_flow_info (void)
 300 {
 301   dump_flow_info (stderr, TDF_DETAILS);
 302 }
 303
 304 /* Redirect edge E to the given basic block DEST and update underlying program
 305    representation.  Returns edge representing redirected branch (that may not
 306    be equivalent to E in the case of duplicate edges being removed) or NULL
 307    if edge is not easily redirectable for whatever reason.  */
 308
 309 edge
 310 redirect_edge_and_branch (edge e, basic_block dest)
 311 {
 312   edge ret;
 313
 314   if (!cfg_hooks->redirect_edge_and_branch)
 315     internal_error ("%s does not support redirect_edge_and_branch",
 316                     cfg_hooks->name);
 317
 318   ret = cfg_hooks->redirect_edge_and_branch (e, dest);
 319
 320   /* If RET != E, then either the redirection failed, or the edge E
 321      was removed since RET already lead to the same destination.  */
 322   if (current_loops != NULL && ret == e)
 323     rescan_loop_exit (e, false, false);
 324
 325   return ret;
 326 }
 327
 328 /* Returns true if it is possible to remove the edge E by redirecting it
 329    to the destination of the other edge going from its source.  */
 330
 331 bool
 332 can_remove_branch_p (const_edge e)
 333 {
 334   if (!cfg_hooks->can_remove_branch_p)
 335     internal_error ("%s does not support can_remove_branch_p",
 336                     cfg_hooks->name);
 337
 338   if (EDGE_COUNT (e->src->succs) != 2)
 339     return false;
 340
 341   return cfg_hooks->can_remove_branch_p (e);
 342 }
 343
 344 /* Removes E, by redirecting it to the destination of the other edge going
 345    from its source.  Can_remove_branch_p must be true for E, hence this
 346    operation cannot fail.  */
 347
 348 void
 349 remove_branch (edge e)
 350 {
 351   edge other;
 352   basic_block src = e->src;
 353   int irr;
 354
 355   gcc_assert (EDGE_COUNT (e->src->succs) == 2);
 356
 357   other = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
 358   irr = other->flags & EDGE_IRREDUCIBLE_LOOP;
 359
 360   e = redirect_edge_and_branch (e, other->dest);
 361   gcc_assert (e != NULL);
 362
 363   e->flags &= ~EDGE_IRREDUCIBLE_LOOP;
 364   e->flags |= irr;
 365 }
 366
 367 /* Removes edge E from cfg.  Unlike remove_branch, it does not update IL.  */
 368
 369 void
 370 remove_edge (edge e)
 371 {
 372   if (current_loops != NULL)
 373     rescan_loop_exit (e, false, true);
 374
 375   /* This is probably not needed, but it doesn't hurt.  */
 376   /* FIXME: This should be called via a remove_edge hook.  */
 377   if (current_ir_type () == IR_GIMPLE)
 378     redirect_edge_var_map_clear (e);
 379
 380   remove_edge_raw (e);
 381 }
 382
 383 /* Like redirect_edge_succ but avoid possible duplicate edge.  */
 384
 385 edge
 386 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 387 {
 388   edge s;
 389
 390   s = find_edge (e->src, new_succ);
 391   if (s && s != e)
 392     {
 393       s->flags |= e->flags;
 394       s->probability += e->probability;
 395       if (s->probability > REG_BR_PROB_BASE)
 396         s->probability = REG_BR_PROB_BASE;
 397       s->count += e->count;
 398       /* FIXME: This should be called via a hook and only for IR_GIMPLE.  */
 399       redirect_edge_var_map_dup (s, e);
 400       remove_edge (e);
 401       e = s;
 402     }
 403   else
 404     redirect_edge_succ (e, new_succ);
 405
 406   return e;
 407 }
 408
 409 /* Redirect the edge E to basic block DEST even if it requires creating
 410    of a new basic block; then it returns the newly created basic block.
 411    Aborts when redirection is impossible.  */
 412
 413 basic_block
 414 redirect_edge_and_branch_force (edge e, basic_block dest)
 415 {
 416   basic_block ret, src = e->src;
 417
 418   if (!cfg_hooks->redirect_edge_and_branch_force)
 419     internal_error ("%s does not support redirect_edge_and_branch_force",
 420                     cfg_hooks->name);
 421
 422   if (current_loops != NULL)
 423     rescan_loop_exit (e, false, true);
 424
 425   ret = cfg_hooks->redirect_edge_and_branch_force (e, dest);
 426
 427   if (ret != NULL && dom_info_available_p (CDI_DOMINATORS))
 428     set_immediate_dominator (CDI_DOMINATORS, ret, src);
 429
 430   if (current_loops != NULL)
 431     {
 432       if (ret != NULL)
 433         {
 434           struct loop *loop
 435             = find_common_loop (single_pred (ret)->loop_father,
 436                                 single_succ (ret)->loop_father);
 437           add_bb_to_loop (ret, loop);
 438         }
 439       else if (find_edge (src, dest) == e)
 440         rescan_loop_exit (e, true, false);
 441     }
 442
 443   return ret;
 444 }
 445
 446 /* Splits basic block BB after the specified instruction I (but at least after
 447    the labels).  If I is NULL, splits just after labels.  The newly created edge
 448    is returned.  The new basic block is created just after the old one.  */
 449
 450 edge
 451 split_block (basic_block bb, void *i)
 452 {
 453   basic_block new_bb;
 454   edge res;
 455
 456   if (!cfg_hooks->split_block)
 457     internal_error ("%s does not support split_block", cfg_hooks->name);
 458
 459   new_bb = cfg_hooks->split_block (bb, i);
 460   if (!new_bb)
 461     return NULL;
 462
 463   new_bb->count = bb->count;
 464   new_bb->frequency = bb->frequency;
 465   new_bb->discriminator = bb->discriminator;
 466
 467   if (dom_info_available_p (CDI_DOMINATORS))
 468     {
 469       redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb);
 470       set_immediate_dominator (CDI_DOMINATORS, new_bb, bb);
 471     }
 472
 473   if (current_loops != NULL)
 474     {
 475       add_bb_to_loop (new_bb, bb->loop_father);
 476       if (bb->loop_father->latch == bb)
 477         bb->loop_father->latch = new_bb;
 478     }
 479
 480   res = make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU);
 481
 482   if (bb->flags & BB_IRREDUCIBLE_LOOP)
 483     {
 484       new_bb->flags |= BB_IRREDUCIBLE_LOOP;
 485       res->flags |= EDGE_IRREDUCIBLE_LOOP;
 486     }
 487
 488   return res;
 489 }
 490
 491 /* Splits block BB just after labels.  The newly created edge is returned.  */
 492
 493 edge
 494 split_block_after_labels (basic_block bb)
 495 {
 496   return split_block (bb, NULL);
 497 }
 498
 499 /* Moves block BB immediately after block AFTER.  Returns false if the
 500    movement was impossible.  */
 501
 502 bool
 503 move_block_after (basic_block bb, basic_block after)
 504 {
 505   bool ret;
 506
 507   if (!cfg_hooks->move_block_after)
 508     internal_error ("%s does not support move_block_after", cfg_hooks->name);
 509
 510   ret = cfg_hooks->move_block_after (bb, after);
 511
 512   return ret;
 513 }
 514
 515 /* Deletes the basic block BB.  */
 516
 517 void
 518 delete_basic_block (basic_block bb)
 519 {
 520   if (!cfg_hooks->delete_basic_block)
 521     internal_error ("%s does not support delete_basic_block", cfg_hooks->name);
 522
 523   cfg_hooks->delete_basic_block (bb);
 524
 525   if (current_loops != NULL)
 526     {
 527       struct loop *loop = bb->loop_father;
 528
 529       /* If we remove the header or the latch of a loop, mark the loop for
 530          removal by setting its header and latch to NULL.  */
 531       if (loop->latch == bb
 532           || loop->header == bb)
 533         {
 534           loop->header = NULL;
 535           loop->latch = NULL;
 536           loops_state_set (LOOPS_NEED_FIXUP);
 537         }
 538
 539       remove_bb_from_loops (bb);
 540     }
 541
 542   /* Remove the edges into and out of this block.  Note that there may
 543      indeed be edges in, if we are removing an unreachable loop.  */
 544   while (EDGE_COUNT (bb->preds) != 0)
 545     remove_edge (EDGE_PRED (bb, 0));
 546   while (EDGE_COUNT (bb->succs) != 0)
 547     remove_edge (EDGE_SUCC (bb, 0));
 548
 549   if (dom_info_available_p (CDI_DOMINATORS))
 550     delete_from_dominance_info (CDI_DOMINATORS, bb);
 551   if (dom_info_available_p (CDI_POST_DOMINATORS))
 552     delete_from_dominance_info (CDI_POST_DOMINATORS, bb);
 553
 554   /* Remove the basic block from the array.  */
 555   expunge_block (bb);
 556 }
 557
 558 /* Splits edge E and returns the newly created basic block.  */
 559
 560 basic_block
 561 split_edge (edge e)
 562 {
 563   basic_block ret;
 564   gcov_type count = e->count;
 565   int freq = EDGE_FREQUENCY (e);
 566   edge f;
 567   bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0;
 568   struct loop *loop;
 569   basic_block src = e->src, dest = e->dest;
 570
 571   if (!cfg_hooks->split_edge)
 572     internal_error ("%s does not support split_edge", cfg_hooks->name);
 573
 574   if (current_loops != NULL)
 575     rescan_loop_exit (e, false, true);
 576
 577   ret = cfg_hooks->split_edge (e);
 578   ret->count = count;
 579   ret->frequency = freq;
 580   single_succ_edge (ret)->probability = REG_BR_PROB_BASE;
 581   single_succ_edge (ret)->count = count;
 582
 583   if (irr)
 584     {
 585       ret->flags |= BB_IRREDUCIBLE_LOOP;
 586       single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 587       single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP;
 588     }
 589
 590   if (dom_info_available_p (CDI_DOMINATORS))
 591     set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret));
 592
 593   if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY)
 594     {
 595       /* There are two cases:
 596
 597          If the immediate dominator of e->dest is not e->src, it
 598          remains unchanged.
 599
 600          If immediate dominator of e->dest is e->src, it may become
 601          ret, provided that all other predecessors of e->dest are
 602          dominated by e->dest.  */
 603
 604       if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret))
 605           == single_pred (ret))
 606         {
 607           edge_iterator ei;
 608           FOR_EACH_EDGE (f, ei, single_succ (ret)->preds)
 609             {
 610               if (f == single_succ_edge (ret))
 611                 continue;
 612
 613               if (!dominated_by_p (CDI_DOMINATORS, f->src,
 614                                    single_succ (ret)))
 615                 break;
 616             }
 617
 618           if (!f)
 619             set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret);
 620         }
 621     }
 622
 623   if (current_loops != NULL)
 624     {
 625       loop = find_common_loop (src->loop_father, dest->loop_father);
 626       add_bb_to_loop (ret, loop);
 627
 628       if (loop->latch == src)
 629         loop->latch = ret;
 630     }
 631
 632   return ret;
 633 }
 634
 635 /* Creates a new basic block just after the basic block AFTER.
 636    HEAD and END are the first and the last statement belonging
 637    to the block.  If both are NULL, an empty block is created.  */
 638
 639 basic_block
 640 create_basic_block (void *head, void *end, basic_block after)
 641 {
 642   basic_block ret;
 643
 644   if (!cfg_hooks->create_basic_block)
 645     internal_error ("%s does not support create_basic_block", cfg_hooks->name);
 646
 647   ret = cfg_hooks->create_basic_block (head, end, after);
 648
 649   if (dom_info_available_p (CDI_DOMINATORS))
 650     add_to_dominance_info (CDI_DOMINATORS, ret);
 651   if (dom_info_available_p (CDI_POST_DOMINATORS))
 652     add_to_dominance_info (CDI_POST_DOMINATORS, ret);
 653
 654   return ret;
 655 }
 656
 657 /* Creates an empty basic block just after basic block AFTER.  */
 658
 659 basic_block
 660 create_empty_bb (basic_block after)
 661 {
 662   return create_basic_block (NULL, NULL, after);
 663 }
 664
 665 /* Checks whether we may merge blocks BB1 and BB2.  */
 666
 667 bool
 668 can_merge_blocks_p (basic_block bb1, basic_block bb2)
 669 {
 670   bool ret;
 671
 672   if (!cfg_hooks->can_merge_blocks_p)
 673     internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name);
 674
 675   ret = cfg_hooks->can_merge_blocks_p (bb1, bb2);
 676
 677   return ret;
 678 }
 679
 680 void
 681 predict_edge (edge e, enum br_predictor predictor, int probability)
 682 {
 683   if (!cfg_hooks->predict_edge)
 684     internal_error ("%s does not support predict_edge", cfg_hooks->name);
 685
 686   cfg_hooks->predict_edge (e, predictor, probability);
 687 }
 688
 689 bool
 690 predicted_by_p (const_basic_block bb, enum br_predictor predictor)
 691 {
 692   if (!cfg_hooks->predict_edge)
 693     internal_error ("%s does not support predicted_by_p", cfg_hooks->name);
 694
 695   return cfg_hooks->predicted_by_p (bb, predictor);
 696 }
 697
 698 /* Merges basic block B into basic block A.  */
 699
 700 void
 701 merge_blocks (basic_block a, basic_block b)
 702 {
 703   edge e;
 704   edge_iterator ei;
 705
 706   if (!cfg_hooks->merge_blocks)
 707     internal_error ("%s does not support merge_blocks", cfg_hooks->name);
 708
 709   cfg_hooks->merge_blocks (a, b);
 710
 711   /* If we merge a loop header into its predecessor, update the loop
 712      structure.  */
 713   if (current_loops != NULL)
 714     {
 715       if (b->loop_father->header == b)
 716         {
 717           remove_bb_from_loops (a);
 718           add_bb_to_loop  (a, b->loop_father);
 719           a->loop_father->header = a;
 720         }
 721       remove_bb_from_loops (b);
 722     }
 723
 724   /* Normally there should only be one successor of A and that is B, but
 725      partway though the merge of blocks for conditional_execution we'll
 726      be merging a TEST block with THEN and ELSE successors.  Free the
 727      whole lot of them and hope the caller knows what they're doing.  */
 728
 729   while (EDGE_COUNT (a->succs) != 0)
 730     remove_edge (EDGE_SUCC (a, 0));
 731
 732   /* Adjust the edges out of B for the new owner.  */
 733   FOR_EACH_EDGE (e, ei, b->succs)
 734     {
 735       e->src = a;
 736       if (current_loops != NULL)
 737         rescan_loop_exit (e, true, false);
 738     }
 739   a->succs = b->succs;
 740   a->flags |= b->flags;
 741
 742   /* B hasn't quite yet ceased to exist.  Attempt to prevent mishap.  */
 743   b->preds = b->succs = NULL;
 744
 745   if (dom_info_available_p (CDI_DOMINATORS))
 746     redirect_immediate_dominators (CDI_DOMINATORS, b, a);
 747
 748   if (dom_info_available_p (CDI_DOMINATORS))
 749     delete_from_dominance_info (CDI_DOMINATORS, b);
 750   if (dom_info_available_p (CDI_POST_DOMINATORS))
 751     delete_from_dominance_info (CDI_POST_DOMINATORS, b);
 752
 753   expunge_block (b);
 754 }
 755
 756 /* Split BB into entry part and the rest (the rest is the newly created block).
 757    Redirect those edges for that REDIRECT_EDGE_P returns true to the entry
 758    part.  Returns the edge connecting the entry part to the rest.  */
 759
 760 edge
 761 make_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge),
 762                       void (*new_bb_cbk) (basic_block))
 763 {
 764   edge e, fallthru;
 765   edge_iterator ei;
 766   basic_block dummy, jump;
 767   struct loop *loop, *ploop, *cloop;
 768
 769   if (!cfg_hooks->make_forwarder_block)
 770     internal_error ("%s does not support make_forwarder_block",
 771                     cfg_hooks->name);
 772
 773   fallthru = split_block_after_labels (bb);
 774   dummy = fallthru->src;
 775   bb = fallthru->dest;
 776
 777   /* Redirect back edges we want to keep.  */
 778   for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); )
 779     {
 780       basic_block e_src;
 781
 782       if (redirect_edge_p (e))
 783         {
 784           ei_next (&ei);
 785           continue;
 786         }
 787
 788       dummy->frequency -= EDGE_FREQUENCY (e);
 789       dummy->count -= e->count;
 790       if (dummy->frequency < 0)
 791         dummy->frequency = 0;
 792       if (dummy->count < 0)
 793         dummy->count = 0;
 794       fallthru->count -= e->count;
 795       if (fallthru->count < 0)
 796         fallthru->count = 0;
 797
 798       e_src = e->src;
 799       jump = redirect_edge_and_branch_force (e, bb);
 800       if (jump != NULL)
 801         {
 802           /* If we redirected the loop latch edge, the JUMP block now acts like
 803              the new latch of the loop.  */
 804           if (current_loops != NULL
 805               && dummy->loop_father != NULL
 806               && dummy->loop_father->header == dummy
 807               && dummy->loop_father->latch == e_src)
 808             dummy->loop_father->latch = jump;
 809
 810           if (new_bb_cbk != NULL)
 811             new_bb_cbk (jump);
 812         }
 813     }
 814
 815   if (dom_info_available_p (CDI_DOMINATORS))
 816     {
 817       VEC (basic_block, heap) *doms_to_fix = VEC_alloc (basic_block, heap, 2);
 818       VEC_quick_push (basic_block, doms_to_fix, dummy);
 819       VEC_quick_push (basic_block, doms_to_fix, bb);
 820       iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, false);
 821       VEC_free (basic_block, heap, doms_to_fix);
 822     }
 823
 824   if (current_loops != NULL)
 825     {
 826       /* If we do not split a loop header, then both blocks belong to the
 827          same loop.  In case we split loop header and do not redirect the
 828          latch edge to DUMMY, then DUMMY belongs to the outer loop, and
 829          BB becomes the new header.  If latch is not recorded for the loop,
 830          we leave this updating on the caller (this may only happen during
 831          loop analysis).  */
 832       loop = dummy->loop_father;
 833       if (loop->header == dummy
 834           && loop->latch != NULL
 835           && find_edge (loop->latch, dummy) == NULL)
 836         {
 837           remove_bb_from_loops (dummy);
 838           loop->header = bb;
 839
 840           cloop = loop;
 841           FOR_EACH_EDGE (e, ei, dummy->preds)
 842             {
 843               cloop = find_common_loop (cloop, e->src->loop_father);
 844             }
 845           add_bb_to_loop (dummy, cloop);
 846         }
 847
 848       /* In case we split loop latch, update it.  */
 849       for (ploop = loop; ploop; ploop = loop_outer (ploop))
 850         if (ploop->latch == dummy)
 851           ploop->latch = bb;
 852     }
 853
 854   cfg_hooks->make_forwarder_block (fallthru);
 855
 856   return fallthru;
 857 }
 858
 859 /* Try to make the edge fallthru.  */
 860
 861 void
 862 tidy_fallthru_edge (edge e)
 863 {
 864   if (cfg_hooks->tidy_fallthru_edge)
 865     cfg_hooks->tidy_fallthru_edge (e);
 866 }
 867
 868 /* Fix up edges that now fall through, or rather should now fall through
 869    but previously required a jump around now deleted blocks.  Simplify
 870    the search by only examining blocks numerically adjacent, since this
 871    is how they were created.
 872
 873    ??? This routine is currently RTL specific.  */
 874
 875 void
 876 tidy_fallthru_edges (void)
 877 {
 878   basic_block b, c;
 879
 880   if (!cfg_hooks->tidy_fallthru_edge)
 881     return;
 882
 883   if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
 884     return;
 885
 886   FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb)
 887     {
 888       edge s;
 889
 890       c = b->next_bb;
 891
 892       /* We care about simple conditional or unconditional jumps with
 893          a single successor.
 894
 895          If we had a conditional branch to the next instruction when
 896          CFG was built, then there will only be one out edge for the
 897          block which ended with the conditional branch (since we do
 898          not create duplicate edges).
 899
 900          Furthermore, the edge will be marked as a fallthru because we
 901          merge the flags for the duplicate edges.  So we do not want to
 902          check that the edge is not a FALLTHRU edge.  */
 903
 904       if (single_succ_p (b))
 905         {
 906           s = single_succ_edge (b);
 907           if (! (s->flags & EDGE_COMPLEX)
 908               && s->dest == c
 909               && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 910             tidy_fallthru_edge (s);
 911         }
 912     }
 913 }
 914
 915 /* Edge E is assumed to be fallthru edge.  Emit needed jump instruction
 916    (and possibly create new basic block) to make edge non-fallthru.
 917    Return newly created BB or NULL if none.  */
 918
 919 basic_block
 920 force_nonfallthru (edge e)
 921 {
 922   basic_block ret, src = e->src;
 923
 924   if (!cfg_hooks->force_nonfallthru)
 925     internal_error ("%s does not support force_nonfallthru",
 926                     cfg_hooks->name);
 927
 928   ret = cfg_hooks->force_nonfallthru (e);
 929   if (ret != NULL)
 930     {
 931       if (dom_info_available_p (CDI_DOMINATORS))
 932         set_immediate_dominator (CDI_DOMINATORS, ret, src);
 933
 934       if (current_loops != NULL)
 935         {
 936           struct loop *loop
 937             = find_common_loop (single_pred (ret)->loop_father,
 938                                 single_succ (ret)->loop_father);
 939           rescan_loop_exit (e, false, true);
 940           add_bb_to_loop (ret, loop);
 941         }
 942     }
 943
 944   return ret;
 945 }
 946
 947 /* Returns true if we can duplicate basic block BB.  */
 948
 949 bool
 950 can_duplicate_block_p (const_basic_block bb)
 951 {
 952   if (!cfg_hooks->can_duplicate_block_p)
 953     internal_error ("%s does not support can_duplicate_block_p",
 954                     cfg_hooks->name);
 955
 956   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
 957     return false;
 958
 959   return cfg_hooks->can_duplicate_block_p (bb);
 960 }
 961
 962 /* Duplicates basic block BB and redirects edge E to it.  Returns the
 963    new basic block.  The new basic block is placed after the basic block
 964    AFTER.  */
 965
 966 basic_block
 967 duplicate_block (basic_block bb, edge e, basic_block after)
 968 {
 969   edge s, n;
 970   basic_block new_bb;
 971   gcov_type new_count = e ? e->count : 0;
 972   edge_iterator ei;
 973
 974   if (!cfg_hooks->duplicate_block)
 975     internal_error ("%s does not support duplicate_block",
 976                     cfg_hooks->name);
 977
 978   if (bb->count < new_count)
 979     new_count = bb->count;
 980
 981   gcc_checking_assert (can_duplicate_block_p (bb));
 982
 983   new_bb = cfg_hooks->duplicate_block (bb);
 984   if (after)
 985     move_block_after (new_bb, after);
 986
 987   new_bb->flags = bb->flags;
 988   FOR_EACH_EDGE (s, ei, bb->succs)
 989     {
 990       /* Since we are creating edges from a new block to successors
 991          of another block (which therefore are known to be disjoint), there
 992          is no need to actually check for duplicated edges.  */
 993       n = unchecked_make_edge (new_bb, s->dest, s->flags);
 994       n->probability = s->probability;
 995       if (e && bb->count)
 996         {
 997           /* Take care for overflows!  */
 998           n->count = s->count * (new_count * 10000 / bb->count) / 10000;
 999           s->count -= n->count;
1000         }
1001       else
1002         n->count = s->count;
1003       n->aux = s->aux;
1004     }
1005
1006   if (e)
1007     {
1008       new_bb->count = new_count;
1009       bb->count -= new_count;
1010
1011       new_bb->frequency = EDGE_FREQUENCY (e);
1012       bb->frequency -= EDGE_FREQUENCY (e);
1013
1014       redirect_edge_and_branch_force (e, new_bb);
1015
1016       if (bb->count < 0)
1017         bb->count = 0;
1018       if (bb->frequency < 0)
1019         bb->frequency = 0;
1020     }
1021   else
1022     {
1023       new_bb->count = bb->count;
1024       new_bb->frequency = bb->frequency;
1025     }
1026
1027   set_bb_original (new_bb, bb);
1028   set_bb_copy (bb, new_bb);
1029
1030   /* Add the new block to the copy of the loop of BB, or directly to the loop
1031      of BB if the loop is not being copied.  */
1032   if (current_loops != NULL)
1033     {
1034       struct loop *cloop = bb->loop_father;
1035       struct loop *copy = get_loop_copy (cloop);
1036       /* If we copied the loop header block but not the loop
1037          we have created a loop with multiple entries.  Ditch the loop,
1038          add the new block to the outer loop and arrange for a fixup.  */
1039       if (!copy
1040           && cloop->header == bb)
1041         {
1042           add_bb_to_loop (new_bb, loop_outer (cloop));
1043           cloop->header = NULL;
1044           cloop->latch = NULL;
1045           loops_state_set (LOOPS_NEED_FIXUP);
1046         }
1047       else
1048         {
1049           add_bb_to_loop (new_bb, copy ? copy : cloop);
1050           /* If we copied the loop latch block but not the loop, adjust
1051              loop state.  */
1052           if (!copy
1053               && cloop->latch == bb)
1054             {
1055               cloop->latch = NULL;
1056               loops_state_set (LOOPS_MAY_HAVE_MULTIPLE_LATCHES);
1057             }
1058         }
1059     }
1060
1061   return new_bb;
1062 }
1063
1064 /* Return 1 if BB ends with a call, possibly followed by some
1065    instructions that must stay with the call, 0 otherwise.  */
1066
1067 bool
1068 block_ends_with_call_p (basic_block bb)
1069 {
1070   if (!cfg_hooks->block_ends_with_call_p)
1071     internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name);
1072
1073   return (cfg_hooks->block_ends_with_call_p) (bb);
1074 }
1075
1076 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
1077
1078 bool
1079 block_ends_with_condjump_p (const_basic_block bb)
1080 {
1081   if (!cfg_hooks->block_ends_with_condjump_p)
1082     internal_error ("%s does not support block_ends_with_condjump_p",
1083                     cfg_hooks->name);
1084
1085   return (cfg_hooks->block_ends_with_condjump_p) (bb);
1086 }
1087
1088 /* Add fake edges to the function exit for any non constant and non noreturn
1089    calls, volatile inline assembly in the bitmap of blocks specified by
1090    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
1091    that were split.
1092
1093    The goal is to expose cases in which entering a basic block does not imply
1094    that all subsequent instructions must be executed.  */
1095
1096 int
1097 flow_call_edges_add (sbitmap blocks)
1098 {
1099   if (!cfg_hooks->flow_call_edges_add)
1100     internal_error ("%s does not support flow_call_edges_add",
1101                     cfg_hooks->name);
1102
1103   return (cfg_hooks->flow_call_edges_add) (blocks);
1104 }
1105
1106 /* This function is called immediately after edge E is added to the
1107    edge vector E->dest->preds.  */
1108
1109 void
1110 execute_on_growing_pred (edge e)
1111 {
1112   if (cfg_hooks->execute_on_growing_pred)
1113     cfg_hooks->execute_on_growing_pred (e);
1114 }
1115
1116 /* This function is called immediately before edge E is removed from
1117    the edge vector E->dest->preds.  */
1118
1119 void
1120 execute_on_shrinking_pred (edge e)
1121 {
1122   if (cfg_hooks->execute_on_shrinking_pred)
1123     cfg_hooks->execute_on_shrinking_pred (e);
1124 }
1125
1126 /* This is used inside loop versioning when we want to insert
1127    stmts/insns on the edges, which have a different behavior
1128    in tree's and in RTL, so we made a CFG hook.  */
1129 void
1130 lv_flush_pending_stmts (edge e)
1131 {
1132   if (cfg_hooks->flush_pending_stmts)
1133     cfg_hooks->flush_pending_stmts (e);
1134 }
1135
1136 /* Loop versioning uses the duplicate_loop_to_header_edge to create
1137    a new version of the loop basic-blocks, the parameters here are
1138    exactly the same as in duplicate_loop_to_header_edge or
1139    tree_duplicate_loop_to_header_edge; while in tree-ssa there is
1140    additional work to maintain ssa information that's why there is
1141    a need to call the tree_duplicate_loop_to_header_edge rather
1142    than duplicate_loop_to_header_edge when we are in tree mode.  */
1143 bool
1144 cfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e,
1145                                         unsigned int ndupl,
1146                                         sbitmap wont_exit, edge orig,
1147                                         VEC (edge, heap) **to_remove,
1148                                         int flags)
1149 {
1150   gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge);
1151   return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e,
1152                                                             ndupl, wont_exit,
1153                                                             orig, to_remove,
1154                                                             flags);
1155 }
1156
1157 /* Conditional jumps are represented differently in trees and RTL,
1158    this hook takes a basic block that is known to have a cond jump
1159    at its end and extracts the taken and not taken edges out of it
1160    and store it in E1 and E2 respectively.  */
1161 void
1162 extract_cond_bb_edges (basic_block b, edge *e1, edge *e2)
1163 {
1164   gcc_assert (cfg_hooks->extract_cond_bb_edges);
1165   cfg_hooks->extract_cond_bb_edges (b, e1, e2);
1166 }
1167
1168 /* Responsible for updating the ssa info (PHI nodes) on the
1169    new condition basic block that guards the versioned loop.  */
1170 void
1171 lv_adjust_loop_header_phi (basic_block first, basic_block second,
1172                            basic_block new_block, edge e)
1173 {
1174   if (cfg_hooks->lv_adjust_loop_header_phi)
1175     cfg_hooks->lv_adjust_loop_header_phi (first, second, new_block, e);
1176 }
1177
1178 /* Conditions in trees and RTL are different so we need
1179    a different handling when we add the condition to the
1180    versioning code.  */
1181 void
1182 lv_add_condition_to_bb (basic_block first, basic_block second,
1183                         basic_block new_block, void *cond)
1184 {
1185   gcc_assert (cfg_hooks->lv_add_condition_to_bb);
1186   cfg_hooks->lv_add_condition_to_bb (first, second, new_block, cond);
1187 }
1188
1189 /* Checks whether all N blocks in BBS array can be copied.  */
1190 bool
1191 can_copy_bbs_p (basic_block *bbs, unsigned n)
1192 {
1193   unsigned i;
1194   edge e;
1195   int ret = true;
1196
1197   for (i = 0; i < n; i++)
1198     bbs[i]->flags |= BB_DUPLICATED;
1199
1200   for (i = 0; i < n; i++)
1201     {
1202       /* In case we should redirect abnormal edge during duplication, fail.  */
1203       edge_iterator ei;
1204       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1205         if ((e->flags & EDGE_ABNORMAL)
1206             && (e->dest->flags & BB_DUPLICATED))
1207           {
1208             ret = false;
1209             goto end;
1210           }
1211
1212       if (!can_duplicate_block_p (bbs[i]))
1213         {
1214           ret = false;
1215           break;
1216         }
1217     }
1218
1219 end:
1220   for (i = 0; i < n; i++)
1221     bbs[i]->flags &= ~BB_DUPLICATED;
1222
1223   return ret;
1224 }
1225
1226 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1227    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1228    in BBS are also duplicated and copies of those of them
1229    that lead into BBS are redirected to appropriate newly created block.  The
1230    function assigns bbs into loops (copy of basic block bb is assigned to
1231    bb->loop_father->copy loop, so this must be set up correctly in advance)
1232    and updates dominators locally (LOOPS structure that contains the information
1233    about dominators is passed to enable this).
1234
1235    BASE is the superloop to that basic block belongs; if its header or latch
1236    is copied, we do not set the new blocks as header or latch.
1237
1238    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1239    also in the same order.
1240
1241    Newly created basic blocks are put after the basic block AFTER in the
1242    instruction stream, and the order of the blocks in BBS array is preserved.  */
1243
1244 void
1245 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1246           edge *edges, unsigned num_edges, edge *new_edges,
1247           struct loop *base, basic_block after)
1248 {
1249   unsigned i, j;
1250   basic_block bb, new_bb, dom_bb;
1251   edge e;
1252
1253   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1254   for (i = 0; i < n; i++)
1255     {
1256       /* Duplicate.  */
1257       bb = bbs[i];
1258       new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1259       after = new_bb;
1260       bb->flags |= BB_DUPLICATED;
1261       /* Possibly set loop header.  */
1262       if (bb->loop_father->header == bb && bb->loop_father != base)
1263         new_bb->loop_father->header = new_bb;
1264       /* Or latch.  */
1265       if (bb->loop_father->latch == bb && bb->loop_father != base)
1266         new_bb->loop_father->latch = new_bb;
1267     }
1268
1269   /* Set dominators.  */
1270   for (i = 0; i < n; i++)
1271     {
1272       bb = bbs[i];
1273       new_bb = new_bbs[i];
1274
1275       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1276       if (dom_bb->flags & BB_DUPLICATED)
1277         {
1278           dom_bb = get_bb_copy (dom_bb);
1279           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1280         }
1281     }
1282
1283   /* Redirect edges.  */
1284   for (j = 0; j < num_edges; j++)
1285     new_edges[j] = NULL;
1286   for (i = 0; i < n; i++)
1287     {
1288       edge_iterator ei;
1289       new_bb = new_bbs[i];
1290       bb = bbs[i];
1291
1292       FOR_EACH_EDGE (e, ei, new_bb->succs)
1293         {
1294           for (j = 0; j < num_edges; j++)
1295             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1296               new_edges[j] = e;
1297
1298           if (!(e->dest->flags & BB_DUPLICATED))
1299             continue;
1300           redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1301         }
1302     }
1303
1304   /* Clear information about duplicates.  */
1305   for (i = 0; i < n; i++)
1306     bbs[i]->flags &= ~BB_DUPLICATED;
1307 }
1308
1309 /* Return true if BB contains only labels or non-executable
1310    instructions */
1311 bool
1312 empty_block_p (basic_block bb)
1313 {
1314   gcc_assert (cfg_hooks->empty_block_p);
1315   return cfg_hooks->empty_block_p (bb);
1316 }
1317
1318 /* Split a basic block if it ends with a conditional branch and if
1319    the other part of the block is not empty.  */
1320 basic_block
1321 split_block_before_cond_jump (basic_block bb)
1322 {
1323   gcc_assert (cfg_hooks->split_block_before_cond_jump);
1324   return cfg_hooks->split_block_before_cond_jump (bb);
1325 }
1326