1132718Skan/* Hooks for cfg representation specific functions. 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3132718Skan Contributed by Sebastian Pop <s.pop@laposte.net> 4132718Skan 5132718SkanThis file is part of GCC. 6132718Skan 7132718SkanGCC is free software; you can redistribute it and/or modify 8132718Skanit under the terms of the GNU General Public License as published by 9132718Skanthe Free Software Foundation; either version 2, or (at your option) 10132718Skanany later version. 11132718Skan 12132718SkanGCC is distributed in the hope that it will be useful, 13132718Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14132718SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15132718SkanGNU General Public License for more details. 16132718Skan 17132718SkanYou should have received a copy of the GNU General Public License 18132718Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21132718Skan 22132718Skan#include "config.h" 23132718Skan#include "system.h" 24132718Skan#include "coretypes.h" 25132718Skan#include "tm.h" 26132718Skan#include "tree.h" 27132718Skan#include "rtl.h" 28132718Skan#include "basic-block.h" 29169689Skan#include "tree-flow.h" 30169689Skan#include "timevar.h" 31169689Skan#include "toplev.h" 32132718Skan 33132718Skan/* A pointer to one of the hooks containers. */ 34169689Skanstatic struct cfg_hooks *cfg_hooks; 35132718Skan 36132718Skan/* Initialization of functions specific to the rtl IR. */ 37132718Skanvoid 38132718Skanrtl_register_cfg_hooks (void) 39132718Skan{ 40132718Skan cfg_hooks = &rtl_cfg_hooks; 41132718Skan} 42132718Skan 43132718Skan/* Initialization of functions specific to the rtl IR. */ 44132718Skanvoid 45132718Skancfg_layout_rtl_register_cfg_hooks (void) 46132718Skan{ 47132718Skan cfg_hooks = &cfg_layout_rtl_cfg_hooks; 48132718Skan} 49169689Skan 50169689Skan/* Initialization of functions specific to the tree IR. */ 51169689Skan 52169689Skanvoid 53169689Skantree_register_cfg_hooks (void) 54169689Skan{ 55169689Skan cfg_hooks = &tree_cfg_hooks; 56169689Skan} 57169689Skan 58169689Skan/* Returns current ir type (rtl = 0, trees = 1). */ 59169689Skan 60169689Skanint 61169689Skanir_type (void) 62169689Skan{ 63169689Skan return cfg_hooks == &tree_cfg_hooks ? 1 : 0; 64169689Skan} 65169689Skan 66169689Skan/* Verify the CFG consistency. 67169689Skan 68169689Skan Currently it does following: checks edge and basic block list correctness 69169689Skan and calls into IL dependent checking then. */ 70169689Skan 71169689Skanvoid 72169689Skanverify_flow_info (void) 73169689Skan{ 74169689Skan size_t *edge_checksum; 75169689Skan int err = 0; 76169689Skan basic_block bb, last_bb_seen; 77169689Skan basic_block *last_visited; 78169689Skan 79169689Skan timevar_push (TV_CFG_VERIFY); 80169689Skan last_visited = XCNEWVEC (basic_block, last_basic_block); 81169689Skan edge_checksum = XCNEWVEC (size_t, last_basic_block); 82169689Skan 83169689Skan /* Check bb chain & numbers. */ 84169689Skan last_bb_seen = ENTRY_BLOCK_PTR; 85169689Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb) 86169689Skan { 87169689Skan if (bb != EXIT_BLOCK_PTR 88169689Skan && bb != BASIC_BLOCK (bb->index)) 89169689Skan { 90169689Skan error ("bb %d on wrong place", bb->index); 91169689Skan err = 1; 92169689Skan } 93169689Skan 94169689Skan if (bb->prev_bb != last_bb_seen) 95169689Skan { 96169689Skan error ("prev_bb of %d should be %d, not %d", 97169689Skan bb->index, last_bb_seen->index, bb->prev_bb->index); 98169689Skan err = 1; 99169689Skan } 100169689Skan 101169689Skan last_bb_seen = bb; 102169689Skan } 103169689Skan 104169689Skan /* Now check the basic blocks (boundaries etc.) */ 105169689Skan FOR_EACH_BB_REVERSE (bb) 106169689Skan { 107169689Skan int n_fallthru = 0; 108169689Skan edge e; 109169689Skan edge_iterator ei; 110169689Skan 111169689Skan if (bb->count < 0) 112169689Skan { 113169689Skan error ("verify_flow_info: Wrong count of block %i %i", 114169689Skan bb->index, (int)bb->count); 115169689Skan err = 1; 116169689Skan } 117169689Skan if (bb->frequency < 0) 118169689Skan { 119169689Skan error ("verify_flow_info: Wrong frequency of block %i %i", 120169689Skan bb->index, bb->frequency); 121169689Skan err = 1; 122169689Skan } 123169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 124169689Skan { 125169689Skan if (last_visited [e->dest->index] == bb) 126169689Skan { 127169689Skan error ("verify_flow_info: Duplicate edge %i->%i", 128169689Skan e->src->index, e->dest->index); 129169689Skan err = 1; 130169689Skan } 131169689Skan if (e->probability < 0 || e->probability > REG_BR_PROB_BASE) 132169689Skan { 133169689Skan error ("verify_flow_info: Wrong probability of edge %i->%i %i", 134169689Skan e->src->index, e->dest->index, e->probability); 135169689Skan err = 1; 136169689Skan } 137169689Skan if (e->count < 0) 138169689Skan { 139169689Skan error ("verify_flow_info: Wrong count of edge %i->%i %i", 140169689Skan e->src->index, e->dest->index, (int)e->count); 141169689Skan err = 1; 142169689Skan } 143169689Skan 144169689Skan last_visited [e->dest->index] = bb; 145169689Skan 146169689Skan if (e->flags & EDGE_FALLTHRU) 147169689Skan n_fallthru++; 148169689Skan 149169689Skan if (e->src != bb) 150169689Skan { 151169689Skan error ("verify_flow_info: Basic block %d succ edge is corrupted", 152169689Skan bb->index); 153169689Skan fprintf (stderr, "Predecessor: "); 154169689Skan dump_edge_info (stderr, e, 0); 155169689Skan fprintf (stderr, "\nSuccessor: "); 156169689Skan dump_edge_info (stderr, e, 1); 157169689Skan fprintf (stderr, "\n"); 158169689Skan err = 1; 159169689Skan } 160169689Skan 161169689Skan edge_checksum[e->dest->index] += (size_t) e; 162169689Skan } 163169689Skan if (n_fallthru > 1) 164169689Skan { 165169689Skan error ("wrong amount of branch edges after unconditional jump %i", bb->index); 166169689Skan err = 1; 167169689Skan } 168169689Skan 169169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 170169689Skan { 171169689Skan if (e->dest != bb) 172169689Skan { 173169689Skan error ("basic block %d pred edge is corrupted", bb->index); 174169689Skan fputs ("Predecessor: ", stderr); 175169689Skan dump_edge_info (stderr, e, 0); 176169689Skan fputs ("\nSuccessor: ", stderr); 177169689Skan dump_edge_info (stderr, e, 1); 178169689Skan fputc ('\n', stderr); 179169689Skan err = 1; 180169689Skan } 181169689Skan 182169689Skan if (ei.index != e->dest_idx) 183169689Skan { 184169689Skan error ("basic block %d pred edge is corrupted", bb->index); 185169689Skan error ("its dest_idx should be %d, not %d", 186169689Skan ei.index, e->dest_idx); 187169689Skan fputs ("Predecessor: ", stderr); 188169689Skan dump_edge_info (stderr, e, 0); 189169689Skan fputs ("\nSuccessor: ", stderr); 190169689Skan dump_edge_info (stderr, e, 1); 191169689Skan fputc ('\n', stderr); 192169689Skan err = 1; 193169689Skan } 194169689Skan 195169689Skan edge_checksum[e->dest->index] -= (size_t) e; 196169689Skan } 197169689Skan } 198169689Skan 199169689Skan /* Complete edge checksumming for ENTRY and EXIT. */ 200169689Skan { 201169689Skan edge e; 202169689Skan edge_iterator ei; 203169689Skan 204169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 205169689Skan edge_checksum[e->dest->index] += (size_t) e; 206169689Skan 207169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 208169689Skan edge_checksum[e->dest->index] -= (size_t) e; 209169689Skan } 210169689Skan 211169689Skan FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb) 212169689Skan if (edge_checksum[bb->index]) 213169689Skan { 214169689Skan error ("basic block %i edge lists are corrupted", bb->index); 215169689Skan err = 1; 216169689Skan } 217169689Skan 218169689Skan last_bb_seen = ENTRY_BLOCK_PTR; 219169689Skan 220169689Skan /* Clean up. */ 221169689Skan free (last_visited); 222169689Skan free (edge_checksum); 223169689Skan 224169689Skan if (cfg_hooks->verify_flow_info) 225169689Skan err |= cfg_hooks->verify_flow_info (); 226169689Skan if (err) 227169689Skan internal_error ("verify_flow_info failed"); 228169689Skan timevar_pop (TV_CFG_VERIFY); 229169689Skan} 230169689Skan 231169689Skan/* Print out one basic block. This function takes care of the purely 232169689Skan graph related information. The cfg hook for the active representation 233169689Skan should dump representation-specific information. */ 234169689Skan 235169689Skanvoid 236169689Skandump_bb (basic_block bb, FILE *outf, int indent) 237169689Skan{ 238169689Skan edge e; 239169689Skan edge_iterator ei; 240169689Skan char *s_indent; 241169689Skan 242169689Skan s_indent = alloca ((size_t) indent + 1); 243169689Skan memset (s_indent, ' ', (size_t) indent); 244169689Skan s_indent[indent] = '\0'; 245169689Skan 246169689Skan fprintf (outf, ";;%s basic block %d, loop depth %d, count ", 247169689Skan s_indent, bb->index, bb->loop_depth); 248169689Skan fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count); 249169689Skan putc ('\n', outf); 250169689Skan 251169689Skan fprintf (outf, ";;%s prev block ", s_indent); 252169689Skan if (bb->prev_bb) 253169689Skan fprintf (outf, "%d, ", bb->prev_bb->index); 254169689Skan else 255169689Skan fprintf (outf, "(nil), "); 256169689Skan fprintf (outf, "next block "); 257169689Skan if (bb->next_bb) 258169689Skan fprintf (outf, "%d", bb->next_bb->index); 259169689Skan else 260169689Skan fprintf (outf, "(nil)"); 261169689Skan putc ('\n', outf); 262169689Skan 263169689Skan fprintf (outf, ";;%s pred: ", s_indent); 264169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 265169689Skan dump_edge_info (outf, e, 0); 266169689Skan putc ('\n', outf); 267169689Skan 268169689Skan fprintf (outf, ";;%s succ: ", s_indent); 269169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 270169689Skan dump_edge_info (outf, e, 1); 271169689Skan putc ('\n', outf); 272169689Skan 273169689Skan if (cfg_hooks->dump_bb) 274169689Skan cfg_hooks->dump_bb (bb, outf, indent); 275169689Skan} 276169689Skan 277169689Skan/* Redirect edge E to the given basic block DEST and update underlying program 278169689Skan representation. Returns edge representing redirected branch (that may not 279169689Skan be equivalent to E in the case of duplicate edges being removed) or NULL 280169689Skan if edge is not easily redirectable for whatever reason. */ 281169689Skan 282169689Skanedge 283169689Skanredirect_edge_and_branch (edge e, basic_block dest) 284169689Skan{ 285169689Skan edge ret; 286169689Skan 287169689Skan if (!cfg_hooks->redirect_edge_and_branch) 288169689Skan internal_error ("%s does not support redirect_edge_and_branch", 289169689Skan cfg_hooks->name); 290169689Skan 291169689Skan ret = cfg_hooks->redirect_edge_and_branch (e, dest); 292169689Skan 293169689Skan return ret; 294169689Skan} 295169689Skan 296169689Skan/* Redirect the edge E to basic block DEST even if it requires creating 297169689Skan of a new basic block; then it returns the newly created basic block. 298169689Skan Aborts when redirection is impossible. */ 299169689Skan 300169689Skanbasic_block 301169689Skanredirect_edge_and_branch_force (edge e, basic_block dest) 302169689Skan{ 303169689Skan basic_block ret; 304169689Skan 305169689Skan if (!cfg_hooks->redirect_edge_and_branch_force) 306169689Skan internal_error ("%s does not support redirect_edge_and_branch_force", 307169689Skan cfg_hooks->name); 308169689Skan 309169689Skan ret = cfg_hooks->redirect_edge_and_branch_force (e, dest); 310169689Skan 311169689Skan return ret; 312169689Skan} 313169689Skan 314169689Skan/* Splits basic block BB after the specified instruction I (but at least after 315169689Skan the labels). If I is NULL, splits just after labels. The newly created edge 316169689Skan is returned. The new basic block is created just after the old one. */ 317169689Skan 318169689Skanedge 319169689Skansplit_block (basic_block bb, void *i) 320169689Skan{ 321169689Skan basic_block new_bb; 322169689Skan 323169689Skan if (!cfg_hooks->split_block) 324169689Skan internal_error ("%s does not support split_block", cfg_hooks->name); 325169689Skan 326169689Skan new_bb = cfg_hooks->split_block (bb, i); 327169689Skan if (!new_bb) 328169689Skan return NULL; 329169689Skan 330169689Skan new_bb->count = bb->count; 331169689Skan new_bb->frequency = bb->frequency; 332169689Skan new_bb->loop_depth = bb->loop_depth; 333169689Skan 334169689Skan if (dom_info_available_p (CDI_DOMINATORS)) 335169689Skan { 336169689Skan redirect_immediate_dominators (CDI_DOMINATORS, bb, new_bb); 337169689Skan set_immediate_dominator (CDI_DOMINATORS, new_bb, bb); 338169689Skan } 339169689Skan 340169689Skan return make_single_succ_edge (bb, new_bb, EDGE_FALLTHRU); 341169689Skan} 342169689Skan 343169689Skan/* Splits block BB just after labels. The newly created edge is returned. */ 344169689Skan 345169689Skanedge 346169689Skansplit_block_after_labels (basic_block bb) 347169689Skan{ 348169689Skan return split_block (bb, NULL); 349169689Skan} 350169689Skan 351169689Skan/* Moves block BB immediately after block AFTER. Returns false if the 352169689Skan movement was impossible. */ 353169689Skan 354169689Skanbool 355169689Skanmove_block_after (basic_block bb, basic_block after) 356169689Skan{ 357169689Skan bool ret; 358169689Skan 359169689Skan if (!cfg_hooks->move_block_after) 360169689Skan internal_error ("%s does not support move_block_after", cfg_hooks->name); 361169689Skan 362169689Skan ret = cfg_hooks->move_block_after (bb, after); 363169689Skan 364169689Skan return ret; 365169689Skan} 366169689Skan 367169689Skan/* Deletes the basic block BB. */ 368169689Skan 369169689Skanvoid 370169689Skandelete_basic_block (basic_block bb) 371169689Skan{ 372169689Skan if (!cfg_hooks->delete_basic_block) 373169689Skan internal_error ("%s does not support delete_basic_block", cfg_hooks->name); 374169689Skan 375169689Skan cfg_hooks->delete_basic_block (bb); 376169689Skan 377169689Skan /* Remove the edges into and out of this block. Note that there may 378169689Skan indeed be edges in, if we are removing an unreachable loop. */ 379169689Skan while (EDGE_COUNT (bb->preds) != 0) 380169689Skan remove_edge (EDGE_PRED (bb, 0)); 381169689Skan while (EDGE_COUNT (bb->succs) != 0) 382169689Skan remove_edge (EDGE_SUCC (bb, 0)); 383169689Skan 384169689Skan if (dom_computed[CDI_DOMINATORS]) 385169689Skan delete_from_dominance_info (CDI_DOMINATORS, bb); 386169689Skan if (dom_computed[CDI_POST_DOMINATORS]) 387169689Skan delete_from_dominance_info (CDI_POST_DOMINATORS, bb); 388169689Skan 389169689Skan /* Remove the basic block from the array. */ 390169689Skan expunge_block (bb); 391169689Skan} 392169689Skan 393169689Skan/* Splits edge E and returns the newly created basic block. */ 394169689Skan 395169689Skanbasic_block 396169689Skansplit_edge (edge e) 397169689Skan{ 398169689Skan basic_block ret; 399169689Skan gcov_type count = e->count; 400169689Skan int freq = EDGE_FREQUENCY (e); 401169689Skan edge f; 402169689Skan bool irr = (e->flags & EDGE_IRREDUCIBLE_LOOP) != 0; 403169689Skan 404169689Skan if (!cfg_hooks->split_edge) 405169689Skan internal_error ("%s does not support split_edge", cfg_hooks->name); 406169689Skan 407169689Skan ret = cfg_hooks->split_edge (e); 408169689Skan ret->count = count; 409169689Skan ret->frequency = freq; 410169689Skan single_succ_edge (ret)->probability = REG_BR_PROB_BASE; 411169689Skan single_succ_edge (ret)->count = count; 412169689Skan 413169689Skan if (irr) 414169689Skan { 415169689Skan ret->flags |= BB_IRREDUCIBLE_LOOP; 416169689Skan single_pred_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP; 417169689Skan single_succ_edge (ret)->flags |= EDGE_IRREDUCIBLE_LOOP; 418169689Skan } 419169689Skan 420169689Skan if (dom_computed[CDI_DOMINATORS]) 421169689Skan set_immediate_dominator (CDI_DOMINATORS, ret, single_pred (ret)); 422169689Skan 423169689Skan if (dom_computed[CDI_DOMINATORS] >= DOM_NO_FAST_QUERY) 424169689Skan { 425169689Skan /* There are two cases: 426169689Skan 427169689Skan If the immediate dominator of e->dest is not e->src, it 428169689Skan remains unchanged. 429169689Skan 430169689Skan If immediate dominator of e->dest is e->src, it may become 431169689Skan ret, provided that all other predecessors of e->dest are 432169689Skan dominated by e->dest. */ 433169689Skan 434169689Skan if (get_immediate_dominator (CDI_DOMINATORS, single_succ (ret)) 435169689Skan == single_pred (ret)) 436169689Skan { 437169689Skan edge_iterator ei; 438169689Skan FOR_EACH_EDGE (f, ei, single_succ (ret)->preds) 439169689Skan { 440169689Skan if (f == single_succ_edge (ret)) 441169689Skan continue; 442169689Skan 443169689Skan if (!dominated_by_p (CDI_DOMINATORS, f->src, 444169689Skan single_succ (ret))) 445169689Skan break; 446169689Skan } 447169689Skan 448169689Skan if (!f) 449169689Skan set_immediate_dominator (CDI_DOMINATORS, single_succ (ret), ret); 450169689Skan } 451169689Skan }; 452169689Skan 453169689Skan return ret; 454169689Skan} 455169689Skan 456169689Skan/* Creates a new basic block just after the basic block AFTER. 457169689Skan HEAD and END are the first and the last statement belonging 458169689Skan to the block. If both are NULL, an empty block is created. */ 459169689Skan 460169689Skanbasic_block 461169689Skancreate_basic_block (void *head, void *end, basic_block after) 462169689Skan{ 463169689Skan basic_block ret; 464169689Skan 465169689Skan if (!cfg_hooks->create_basic_block) 466169689Skan internal_error ("%s does not support create_basic_block", cfg_hooks->name); 467169689Skan 468169689Skan ret = cfg_hooks->create_basic_block (head, end, after); 469169689Skan 470169689Skan if (dom_computed[CDI_DOMINATORS]) 471169689Skan add_to_dominance_info (CDI_DOMINATORS, ret); 472169689Skan if (dom_computed[CDI_POST_DOMINATORS]) 473169689Skan add_to_dominance_info (CDI_POST_DOMINATORS, ret); 474169689Skan 475169689Skan return ret; 476169689Skan} 477169689Skan 478169689Skan/* Creates an empty basic block just after basic block AFTER. */ 479169689Skan 480169689Skanbasic_block 481169689Skancreate_empty_bb (basic_block after) 482169689Skan{ 483169689Skan return create_basic_block (NULL, NULL, after); 484169689Skan} 485169689Skan 486169689Skan/* Checks whether we may merge blocks BB1 and BB2. */ 487169689Skan 488169689Skanbool 489169689Skancan_merge_blocks_p (basic_block bb1, basic_block bb2) 490169689Skan{ 491169689Skan bool ret; 492169689Skan 493169689Skan if (!cfg_hooks->can_merge_blocks_p) 494169689Skan internal_error ("%s does not support can_merge_blocks_p", cfg_hooks->name); 495169689Skan 496169689Skan ret = cfg_hooks->can_merge_blocks_p (bb1, bb2); 497169689Skan 498169689Skan return ret; 499169689Skan} 500169689Skan 501169689Skanvoid 502169689Skanpredict_edge (edge e, enum br_predictor predictor, int probability) 503169689Skan{ 504169689Skan if (!cfg_hooks->predict_edge) 505169689Skan internal_error ("%s does not support predict_edge", cfg_hooks->name); 506169689Skan 507169689Skan cfg_hooks->predict_edge (e, predictor, probability); 508169689Skan} 509169689Skan 510169689Skanbool 511169689Skanpredicted_by_p (basic_block bb, enum br_predictor predictor) 512169689Skan{ 513169689Skan if (!cfg_hooks->predict_edge) 514169689Skan internal_error ("%s does not support predicted_by_p", cfg_hooks->name); 515169689Skan 516169689Skan return cfg_hooks->predicted_by_p (bb, predictor); 517169689Skan} 518169689Skan 519169689Skan/* Merges basic block B into basic block A. */ 520169689Skan 521169689Skanvoid 522169689Skanmerge_blocks (basic_block a, basic_block b) 523169689Skan{ 524169689Skan edge e; 525169689Skan edge_iterator ei; 526169689Skan 527169689Skan if (!cfg_hooks->merge_blocks) 528169689Skan internal_error ("%s does not support merge_blocks", cfg_hooks->name); 529169689Skan 530169689Skan cfg_hooks->merge_blocks (a, b); 531169689Skan 532169689Skan /* Normally there should only be one successor of A and that is B, but 533169689Skan partway though the merge of blocks for conditional_execution we'll 534169689Skan be merging a TEST block with THEN and ELSE successors. Free the 535169689Skan whole lot of them and hope the caller knows what they're doing. */ 536169689Skan 537169689Skan while (EDGE_COUNT (a->succs) != 0) 538169689Skan remove_edge (EDGE_SUCC (a, 0)); 539169689Skan 540169689Skan /* Adjust the edges out of B for the new owner. */ 541169689Skan FOR_EACH_EDGE (e, ei, b->succs) 542169689Skan e->src = a; 543169689Skan a->succs = b->succs; 544169689Skan a->flags |= b->flags; 545169689Skan 546169689Skan /* B hasn't quite yet ceased to exist. Attempt to prevent mishap. */ 547169689Skan b->preds = b->succs = NULL; 548169689Skan 549169689Skan if (dom_computed[CDI_DOMINATORS]) 550169689Skan redirect_immediate_dominators (CDI_DOMINATORS, b, a); 551169689Skan 552169689Skan if (dom_computed[CDI_DOMINATORS]) 553169689Skan delete_from_dominance_info (CDI_DOMINATORS, b); 554169689Skan if (dom_computed[CDI_POST_DOMINATORS]) 555169689Skan delete_from_dominance_info (CDI_POST_DOMINATORS, b); 556169689Skan 557169689Skan expunge_block (b); 558169689Skan} 559169689Skan 560169689Skan/* Split BB into entry part and the rest (the rest is the newly created block). 561169689Skan Redirect those edges for that REDIRECT_EDGE_P returns true to the entry 562169689Skan part. Returns the edge connecting the entry part to the rest. */ 563169689Skan 564169689Skanedge 565169689Skanmake_forwarder_block (basic_block bb, bool (*redirect_edge_p) (edge), 566169689Skan void (*new_bb_cbk) (basic_block)) 567169689Skan{ 568169689Skan edge e, fallthru; 569169689Skan edge_iterator ei; 570169689Skan basic_block dummy, jump; 571169689Skan 572169689Skan if (!cfg_hooks->make_forwarder_block) 573169689Skan internal_error ("%s does not support make_forwarder_block", 574169689Skan cfg_hooks->name); 575169689Skan 576169689Skan fallthru = split_block_after_labels (bb); 577169689Skan dummy = fallthru->src; 578169689Skan bb = fallthru->dest; 579169689Skan 580169689Skan /* Redirect back edges we want to keep. */ 581169689Skan for (ei = ei_start (dummy->preds); (e = ei_safe_edge (ei)); ) 582169689Skan { 583169689Skan if (redirect_edge_p (e)) 584169689Skan { 585169689Skan ei_next (&ei); 586169689Skan continue; 587169689Skan } 588169689Skan 589169689Skan dummy->frequency -= EDGE_FREQUENCY (e); 590169689Skan dummy->count -= e->count; 591169689Skan if (dummy->frequency < 0) 592169689Skan dummy->frequency = 0; 593169689Skan if (dummy->count < 0) 594169689Skan dummy->count = 0; 595169689Skan fallthru->count -= e->count; 596169689Skan if (fallthru->count < 0) 597169689Skan fallthru->count = 0; 598169689Skan 599169689Skan jump = redirect_edge_and_branch_force (e, bb); 600169689Skan if (jump) 601169689Skan new_bb_cbk (jump); 602169689Skan } 603169689Skan 604169689Skan if (dom_info_available_p (CDI_DOMINATORS)) 605169689Skan { 606169689Skan basic_block doms_to_fix[2]; 607169689Skan 608169689Skan doms_to_fix[0] = dummy; 609169689Skan doms_to_fix[1] = bb; 610169689Skan iterate_fix_dominators (CDI_DOMINATORS, doms_to_fix, 2); 611169689Skan } 612169689Skan 613169689Skan cfg_hooks->make_forwarder_block (fallthru); 614169689Skan 615169689Skan return fallthru; 616169689Skan} 617169689Skan 618169689Skanvoid 619169689Skantidy_fallthru_edge (edge e) 620169689Skan{ 621169689Skan if (cfg_hooks->tidy_fallthru_edge) 622169689Skan cfg_hooks->tidy_fallthru_edge (e); 623169689Skan} 624169689Skan 625169689Skan/* Fix up edges that now fall through, or rather should now fall through 626169689Skan but previously required a jump around now deleted blocks. Simplify 627169689Skan the search by only examining blocks numerically adjacent, since this 628169689Skan is how find_basic_blocks created them. */ 629169689Skan 630169689Skanvoid 631169689Skantidy_fallthru_edges (void) 632169689Skan{ 633169689Skan basic_block b, c; 634169689Skan 635169689Skan if (!cfg_hooks->tidy_fallthru_edge) 636169689Skan return; 637169689Skan 638169689Skan if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR) 639169689Skan return; 640169689Skan 641169689Skan FOR_BB_BETWEEN (b, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR->prev_bb, next_bb) 642169689Skan { 643169689Skan edge s; 644169689Skan 645169689Skan c = b->next_bb; 646169689Skan 647169689Skan /* We care about simple conditional or unconditional jumps with 648169689Skan a single successor. 649169689Skan 650169689Skan If we had a conditional branch to the next instruction when 651169689Skan find_basic_blocks was called, then there will only be one 652169689Skan out edge for the block which ended with the conditional 653169689Skan branch (since we do not create duplicate edges). 654169689Skan 655169689Skan Furthermore, the edge will be marked as a fallthru because we 656169689Skan merge the flags for the duplicate edges. So we do not want to 657169689Skan check that the edge is not a FALLTHRU edge. */ 658169689Skan 659169689Skan if (single_succ_p (b)) 660169689Skan { 661169689Skan s = single_succ_edge (b); 662169689Skan if (! (s->flags & EDGE_COMPLEX) 663169689Skan && s->dest == c 664169689Skan && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)) 665169689Skan tidy_fallthru_edge (s); 666169689Skan } 667169689Skan } 668169689Skan} 669169689Skan 670169689Skan/* Returns true if we can duplicate basic block BB. */ 671169689Skan 672169689Skanbool 673169689Skancan_duplicate_block_p (basic_block bb) 674169689Skan{ 675169689Skan edge e; 676169689Skan 677169689Skan if (!cfg_hooks->can_duplicate_block_p) 678169689Skan internal_error ("%s does not support can_duplicate_block_p", 679169689Skan cfg_hooks->name); 680169689Skan 681169689Skan if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR) 682169689Skan return false; 683169689Skan 684169689Skan /* Duplicating fallthru block to exit would require adding a jump 685169689Skan and splitting the real last BB. */ 686169689Skan e = find_edge (bb, EXIT_BLOCK_PTR); 687169689Skan if (e && (e->flags & EDGE_FALLTHRU)) 688169689Skan return false; 689169689Skan 690169689Skan return cfg_hooks->can_duplicate_block_p (bb); 691169689Skan} 692169689Skan 693169689Skan/* Duplicates basic block BB and redirects edge E to it. Returns the 694169689Skan new basic block. The new basic block is placed after the basic block 695169689Skan AFTER. */ 696169689Skan 697169689Skanbasic_block 698169689Skanduplicate_block (basic_block bb, edge e, basic_block after) 699169689Skan{ 700169689Skan edge s, n; 701169689Skan basic_block new_bb; 702169689Skan gcov_type new_count = e ? e->count : 0; 703169689Skan edge_iterator ei; 704169689Skan 705169689Skan if (!cfg_hooks->duplicate_block) 706169689Skan internal_error ("%s does not support duplicate_block", 707169689Skan cfg_hooks->name); 708169689Skan 709169689Skan if (bb->count < new_count) 710169689Skan new_count = bb->count; 711169689Skan 712169689Skan#ifdef ENABLE_CHECKING 713169689Skan gcc_assert (can_duplicate_block_p (bb)); 714169689Skan#endif 715169689Skan 716169689Skan new_bb = cfg_hooks->duplicate_block (bb); 717169689Skan if (after) 718169689Skan move_block_after (new_bb, after); 719169689Skan 720169689Skan new_bb->loop_depth = bb->loop_depth; 721169689Skan new_bb->flags = bb->flags; 722169689Skan FOR_EACH_EDGE (s, ei, bb->succs) 723169689Skan { 724169689Skan /* Since we are creating edges from a new block to successors 725169689Skan of another block (which therefore are known to be disjoint), there 726169689Skan is no need to actually check for duplicated edges. */ 727169689Skan n = unchecked_make_edge (new_bb, s->dest, s->flags); 728169689Skan n->probability = s->probability; 729169689Skan if (e && bb->count) 730169689Skan { 731169689Skan /* Take care for overflows! */ 732169689Skan n->count = s->count * (new_count * 10000 / bb->count) / 10000; 733169689Skan s->count -= n->count; 734169689Skan } 735169689Skan else 736169689Skan n->count = s->count; 737169689Skan n->aux = s->aux; 738169689Skan } 739169689Skan 740169689Skan if (e) 741169689Skan { 742169689Skan new_bb->count = new_count; 743169689Skan bb->count -= new_count; 744169689Skan 745169689Skan new_bb->frequency = EDGE_FREQUENCY (e); 746169689Skan bb->frequency -= EDGE_FREQUENCY (e); 747169689Skan 748169689Skan redirect_edge_and_branch_force (e, new_bb); 749169689Skan 750169689Skan if (bb->count < 0) 751169689Skan bb->count = 0; 752169689Skan if (bb->frequency < 0) 753169689Skan bb->frequency = 0; 754169689Skan } 755169689Skan else 756169689Skan { 757169689Skan new_bb->count = bb->count; 758169689Skan new_bb->frequency = bb->frequency; 759169689Skan } 760169689Skan 761169689Skan set_bb_original (new_bb, bb); 762169689Skan set_bb_copy (bb, new_bb); 763169689Skan 764169689Skan return new_bb; 765169689Skan} 766169689Skan 767169689Skan/* Return 1 if BB ends with a call, possibly followed by some 768169689Skan instructions that must stay with the call, 0 otherwise. */ 769169689Skan 770169689Skanbool 771169689Skanblock_ends_with_call_p (basic_block bb) 772169689Skan{ 773169689Skan if (!cfg_hooks->block_ends_with_call_p) 774169689Skan internal_error ("%s does not support block_ends_with_call_p", cfg_hooks->name); 775169689Skan 776169689Skan return (cfg_hooks->block_ends_with_call_p) (bb); 777169689Skan} 778169689Skan 779169689Skan/* Return 1 if BB ends with a conditional branch, 0 otherwise. */ 780169689Skan 781169689Skanbool 782169689Skanblock_ends_with_condjump_p (basic_block bb) 783169689Skan{ 784169689Skan if (!cfg_hooks->block_ends_with_condjump_p) 785169689Skan internal_error ("%s does not support block_ends_with_condjump_p", 786169689Skan cfg_hooks->name); 787169689Skan 788169689Skan return (cfg_hooks->block_ends_with_condjump_p) (bb); 789169689Skan} 790169689Skan 791169689Skan/* Add fake edges to the function exit for any non constant and non noreturn 792169689Skan calls, volatile inline assembly in the bitmap of blocks specified by 793169689Skan BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks 794169689Skan that were split. 795169689Skan 796169689Skan The goal is to expose cases in which entering a basic block does not imply 797169689Skan that all subsequent instructions must be executed. */ 798169689Skan 799169689Skanint 800169689Skanflow_call_edges_add (sbitmap blocks) 801169689Skan{ 802169689Skan if (!cfg_hooks->flow_call_edges_add) 803169689Skan internal_error ("%s does not support flow_call_edges_add", 804169689Skan cfg_hooks->name); 805169689Skan 806169689Skan return (cfg_hooks->flow_call_edges_add) (blocks); 807169689Skan} 808169689Skan 809169689Skan/* This function is called immediately after edge E is added to the 810169689Skan edge vector E->dest->preds. */ 811169689Skan 812169689Skanvoid 813169689Skanexecute_on_growing_pred (edge e) 814169689Skan{ 815169689Skan if (cfg_hooks->execute_on_growing_pred) 816169689Skan cfg_hooks->execute_on_growing_pred (e); 817169689Skan} 818169689Skan 819169689Skan/* This function is called immediately before edge E is removed from 820169689Skan the edge vector E->dest->preds. */ 821169689Skan 822169689Skanvoid 823169689Skanexecute_on_shrinking_pred (edge e) 824169689Skan{ 825169689Skan if (cfg_hooks->execute_on_shrinking_pred) 826169689Skan cfg_hooks->execute_on_shrinking_pred (e); 827169689Skan} 828169689Skan 829169689Skan/* This is used inside loop versioning when we want to insert 830169689Skan stmts/insns on the edges, which have a different behavior 831169689Skan in tree's and in RTL, so we made a CFG hook. */ 832169689Skanvoid 833169689Skanlv_flush_pending_stmts (edge e) 834169689Skan{ 835169689Skan if (cfg_hooks->flush_pending_stmts) 836169689Skan cfg_hooks->flush_pending_stmts (e); 837169689Skan} 838169689Skan 839169689Skan/* Loop versioning uses the duplicate_loop_to_header_edge to create 840169689Skan a new version of the loop basic-blocks, the parameters here are 841169689Skan exactly the same as in duplicate_loop_to_header_edge or 842169689Skan tree_duplicate_loop_to_header_edge; while in tree-ssa there is 843169689Skan additional work to maintain ssa information that's why there is 844169689Skan a need to call the tree_duplicate_loop_to_header_edge rather 845169689Skan than duplicate_loop_to_header_edge when we are in tree mode. */ 846169689Skanbool 847169689Skancfg_hook_duplicate_loop_to_header_edge (struct loop *loop, edge e, 848169689Skan struct loops *loops, unsigned int ndupl, 849169689Skan sbitmap wont_exit, edge orig, 850169689Skan edge *to_remove, 851169689Skan unsigned int *n_to_remove, int flags) 852169689Skan{ 853169689Skan gcc_assert (cfg_hooks->cfg_hook_duplicate_loop_to_header_edge); 854169689Skan return cfg_hooks->cfg_hook_duplicate_loop_to_header_edge (loop, e, loops, 855169689Skan ndupl, wont_exit, 856169689Skan orig, to_remove, 857169689Skan n_to_remove, flags); 858169689Skan} 859169689Skan 860169689Skan/* Conditional jumps are represented differently in trees and RTL, 861169689Skan this hook takes a basic block that is known to have a cond jump 862169689Skan at its end and extracts the taken and not taken eges out of it 863169689Skan and store it in E1 and E2 respectively. */ 864169689Skanvoid 865169689Skanextract_cond_bb_edges (basic_block b, edge *e1, edge *e2) 866169689Skan{ 867169689Skan gcc_assert (cfg_hooks->extract_cond_bb_edges); 868169689Skan cfg_hooks->extract_cond_bb_edges (b, e1, e2); 869169689Skan} 870169689Skan 871169689Skan/* Responsible for updating the ssa info (PHI nodes) on the 872169689Skan new condition basic block that guards the versioned loop. */ 873169689Skanvoid 874169689Skanlv_adjust_loop_header_phi (basic_block first, basic_block second, 875169689Skan basic_block new, edge e) 876169689Skan{ 877169689Skan if (cfg_hooks->lv_adjust_loop_header_phi) 878169689Skan cfg_hooks->lv_adjust_loop_header_phi (first, second, new, e); 879169689Skan} 880169689Skan 881169689Skan/* Conditions in trees and RTL are different so we need 882169689Skan a different handling when we add the condition to the 883169689Skan versioning code. */ 884169689Skanvoid 885169689Skanlv_add_condition_to_bb (basic_block first, basic_block second, 886169689Skan basic_block new, void *cond) 887169689Skan{ 888169689Skan gcc_assert (cfg_hooks->lv_add_condition_to_bb); 889169689Skan cfg_hooks->lv_add_condition_to_bb (first, second, new, cond); 890169689Skan} 891