1 /* Control flow functions for trees. 2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 3 2010, 2011, 2012 Free Software Foundation, Inc. 4 Contributed by Diego Novillo <dnovillo@redhat.com> 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 "tm.h" 26 #include "tree.h" 27 #include "tm_p.h" 28 #include "basic-block.h" 29 #include "output.h" 30 #include "flags.h" 31 #include "function.h" 32 #include "ggc.h" 33 #include "langhooks.h" 34 #include "tree-pretty-print.h" 35 #include "gimple-pretty-print.h" 36 #include "tree-flow.h" 37 #include "timevar.h" 38 #include "tree-dump.h" 39 #include "tree-pass.h" 40 #include "diagnostic-core.h" 41 #include "except.h" 42 #include "cfgloop.h" 43 #include "cfglayout.h" 44 #include "tree-ssa-propagate.h" 45 #include "value-prof.h" 46 #include "pointer-set.h" 47 #include "tree-inline.h" 48 49 /* This file contains functions for building the Control Flow Graph (CFG) 50 for a function tree. */ 51 52 /* Local declarations. */ 53 54 /* Initial capacity for the basic block array. */ 55 static const int initial_cfg_capacity = 20; 56 57 /* This hash table allows us to efficiently lookup all CASE_LABEL_EXPRs 58 which use a particular edge. The CASE_LABEL_EXPRs are chained together 59 via their TREE_CHAIN field, which we clear after we're done with the 60 hash table to prevent problems with duplication of GIMPLE_SWITCHes. 61 62 Access to this list of CASE_LABEL_EXPRs allows us to efficiently 63 update the case vector in response to edge redirections. 64 65 Right now this table is set up and torn down at key points in the 66 compilation process. It would be nice if we could make the table 67 more persistent. The key is getting notification of changes to 68 the CFG (particularly edge removal, creation and redirection). */ 69 70 static struct pointer_map_t *edge_to_cases; 71 72 /* If we record edge_to_cases, this bitmap will hold indexes 73 of basic blocks that end in a GIMPLE_SWITCH which we touched 74 due to edge manipulations. */ 75 76 static bitmap touched_switch_bbs; 77 78 /* CFG statistics. */ 79 struct cfg_stats_d 80 { 81 long num_merged_labels; 82 }; 83 84 static struct cfg_stats_d cfg_stats; 85 86 /* Nonzero if we found a computed goto while building basic blocks. */ 87 static bool found_computed_goto; 88 89 /* Hash table to store last discriminator assigned for each locus. */ 90 struct locus_discrim_map 91 { 92 location_t locus; 93 int discriminator; 94 }; 95 static htab_t discriminator_per_locus; 96 97 /* Basic blocks and flowgraphs. */ 98 static void make_blocks (gimple_seq); 99 static void factor_computed_gotos (void); 100 101 /* Edges. */ 102 static void make_edges (void); 103 static void make_cond_expr_edges (basic_block); 104 static void make_gimple_switch_edges (basic_block); 105 static void make_goto_expr_edges (basic_block); 106 static void make_gimple_asm_edges (basic_block); 107 static unsigned int locus_map_hash (const void *); 108 static int locus_map_eq (const void *, const void *); 109 static void assign_discriminator (location_t, basic_block); 110 static edge gimple_redirect_edge_and_branch (edge, basic_block); 111 static edge gimple_try_redirect_by_replacing_jump (edge, basic_block); 112 113 /* Various helpers. */ 114 static inline bool stmt_starts_bb_p (gimple, gimple); 115 static int gimple_verify_flow_info (void); 116 static void gimple_make_forwarder_block (edge); 117 static void gimple_cfg2vcg (FILE *); 118 static gimple first_non_label_stmt (basic_block); 119 static bool verify_gimple_transaction (gimple); 120 121 /* Flowgraph optimization and cleanup. */ 122 static void gimple_merge_blocks (basic_block, basic_block); 123 static bool gimple_can_merge_blocks_p (basic_block, basic_block); 124 static void remove_bb (basic_block); 125 static edge find_taken_edge_computed_goto (basic_block, tree); 126 static edge find_taken_edge_cond_expr (basic_block, tree); 127 static edge find_taken_edge_switch_expr (basic_block, tree); 128 static tree find_case_label_for_value (gimple, tree); 129 static void group_case_labels_stmt (gimple); 130 131 void 132 init_empty_tree_cfg_for_function (struct function *fn) 133 { 134 /* Initialize the basic block array. */ 135 init_flow (fn); 136 profile_status_for_function (fn) = PROFILE_ABSENT; 137 n_basic_blocks_for_function (fn) = NUM_FIXED_BLOCKS; 138 last_basic_block_for_function (fn) = NUM_FIXED_BLOCKS; 139 basic_block_info_for_function (fn) 140 = VEC_alloc (basic_block, gc, initial_cfg_capacity); 141 VEC_safe_grow_cleared (basic_block, gc, 142 basic_block_info_for_function (fn), 143 initial_cfg_capacity); 144 145 /* Build a mapping of labels to their associated blocks. */ 146 label_to_block_map_for_function (fn) 147 = VEC_alloc (basic_block, gc, initial_cfg_capacity); 148 VEC_safe_grow_cleared (basic_block, gc, 149 label_to_block_map_for_function (fn), 150 initial_cfg_capacity); 151 152 SET_BASIC_BLOCK_FOR_FUNCTION (fn, ENTRY_BLOCK, 153 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)); 154 SET_BASIC_BLOCK_FOR_FUNCTION (fn, EXIT_BLOCK, 155 EXIT_BLOCK_PTR_FOR_FUNCTION (fn)); 156 157 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn)->next_bb 158 = EXIT_BLOCK_PTR_FOR_FUNCTION (fn); 159 EXIT_BLOCK_PTR_FOR_FUNCTION (fn)->prev_bb 160 = ENTRY_BLOCK_PTR_FOR_FUNCTION (fn); 161 } 162 163 void 164 init_empty_tree_cfg (void) 165 { 166 init_empty_tree_cfg_for_function (cfun); 167 } 168 169 /*--------------------------------------------------------------------------- 170 Create basic blocks 171 ---------------------------------------------------------------------------*/ 172 173 /* Entry point to the CFG builder for trees. SEQ is the sequence of 174 statements to be added to the flowgraph. */ 175 176 static void 177 build_gimple_cfg (gimple_seq seq) 178 { 179 /* Register specific gimple functions. */ 180 gimple_register_cfg_hooks (); 181 182 memset ((void *) &cfg_stats, 0, sizeof (cfg_stats)); 183 184 init_empty_tree_cfg (); 185 186 found_computed_goto = 0; 187 make_blocks (seq); 188 189 /* Computed gotos are hell to deal with, especially if there are 190 lots of them with a large number of destinations. So we factor 191 them to a common computed goto location before we build the 192 edge list. After we convert back to normal form, we will un-factor 193 the computed gotos since factoring introduces an unwanted jump. */ 194 if (found_computed_goto) 195 factor_computed_gotos (); 196 197 /* Make sure there is always at least one block, even if it's empty. */ 198 if (n_basic_blocks == NUM_FIXED_BLOCKS) 199 create_empty_bb (ENTRY_BLOCK_PTR); 200 201 /* Adjust the size of the array. */ 202 if (VEC_length (basic_block, basic_block_info) < (size_t) n_basic_blocks) 203 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, n_basic_blocks); 204 205 /* To speed up statement iterator walks, we first purge dead labels. */ 206 cleanup_dead_labels (); 207 208 /* Group case nodes to reduce the number of edges. 209 We do this after cleaning up dead labels because otherwise we miss 210 a lot of obvious case merging opportunities. */ 211 group_case_labels (); 212 213 /* Create the edges of the flowgraph. */ 214 discriminator_per_locus = htab_create (13, locus_map_hash, locus_map_eq, 215 free); 216 make_edges (); 217 cleanup_dead_labels (); 218 htab_delete (discriminator_per_locus); 219 220 /* Debugging dumps. */ 221 222 /* Write the flowgraph to a VCG file. */ 223 { 224 int local_dump_flags; 225 FILE *vcg_file = dump_begin (TDI_vcg, &local_dump_flags); 226 if (vcg_file) 227 { 228 gimple_cfg2vcg (vcg_file); 229 dump_end (TDI_vcg, vcg_file); 230 } 231 } 232 } 233 234 static unsigned int 235 execute_build_cfg (void) 236 { 237 gimple_seq body = gimple_body (current_function_decl); 238 239 build_gimple_cfg (body); 240 gimple_set_body (current_function_decl, NULL); 241 if (dump_file && (dump_flags & TDF_DETAILS)) 242 { 243 fprintf (dump_file, "Scope blocks:\n"); 244 dump_scope_blocks (dump_file, dump_flags); 245 } 246 return 0; 247 } 248 249 struct gimple_opt_pass pass_build_cfg = 250 { 251 { 252 GIMPLE_PASS, 253 "cfg", /* name */ 254 NULL, /* gate */ 255 execute_build_cfg, /* execute */ 256 NULL, /* sub */ 257 NULL, /* next */ 258 0, /* static_pass_number */ 259 TV_TREE_CFG, /* tv_id */ 260 PROP_gimple_leh, /* properties_required */ 261 PROP_cfg, /* properties_provided */ 262 0, /* properties_destroyed */ 263 0, /* todo_flags_start */ 264 TODO_verify_stmts | TODO_cleanup_cfg /* todo_flags_finish */ 265 } 266 }; 267 268 269 /* Return true if T is a computed goto. */ 270 271 static bool 272 computed_goto_p (gimple t) 273 { 274 return (gimple_code (t) == GIMPLE_GOTO 275 && TREE_CODE (gimple_goto_dest (t)) != LABEL_DECL); 276 } 277 278 279 /* Search the CFG for any computed gotos. If found, factor them to a 280 common computed goto site. Also record the location of that site so 281 that we can un-factor the gotos after we have converted back to 282 normal form. */ 283 284 static void 285 factor_computed_gotos (void) 286 { 287 basic_block bb; 288 tree factored_label_decl = NULL; 289 tree var = NULL; 290 gimple factored_computed_goto_label = NULL; 291 gimple factored_computed_goto = NULL; 292 293 /* We know there are one or more computed gotos in this function. 294 Examine the last statement in each basic block to see if the block 295 ends with a computed goto. */ 296 297 FOR_EACH_BB (bb) 298 { 299 gimple_stmt_iterator gsi = gsi_last_bb (bb); 300 gimple last; 301 302 if (gsi_end_p (gsi)) 303 continue; 304 305 last = gsi_stmt (gsi); 306 307 /* Ignore the computed goto we create when we factor the original 308 computed gotos. */ 309 if (last == factored_computed_goto) 310 continue; 311 312 /* If the last statement is a computed goto, factor it. */ 313 if (computed_goto_p (last)) 314 { 315 gimple assignment; 316 317 /* The first time we find a computed goto we need to create 318 the factored goto block and the variable each original 319 computed goto will use for their goto destination. */ 320 if (!factored_computed_goto) 321 { 322 basic_block new_bb = create_empty_bb (bb); 323 gimple_stmt_iterator new_gsi = gsi_start_bb (new_bb); 324 325 /* Create the destination of the factored goto. Each original 326 computed goto will put its desired destination into this 327 variable and jump to the label we create immediately 328 below. */ 329 var = create_tmp_var (ptr_type_node, "gotovar"); 330 331 /* Build a label for the new block which will contain the 332 factored computed goto. */ 333 factored_label_decl = create_artificial_label (UNKNOWN_LOCATION); 334 factored_computed_goto_label 335 = gimple_build_label (factored_label_decl); 336 gsi_insert_after (&new_gsi, factored_computed_goto_label, 337 GSI_NEW_STMT); 338 339 /* Build our new computed goto. */ 340 factored_computed_goto = gimple_build_goto (var); 341 gsi_insert_after (&new_gsi, factored_computed_goto, GSI_NEW_STMT); 342 } 343 344 /* Copy the original computed goto's destination into VAR. */ 345 assignment = gimple_build_assign (var, gimple_goto_dest (last)); 346 gsi_insert_before (&gsi, assignment, GSI_SAME_STMT); 347 348 /* And re-vector the computed goto to the new destination. */ 349 gimple_goto_set_dest (last, factored_label_decl); 350 } 351 } 352 } 353 354 355 /* Build a flowgraph for the sequence of stmts SEQ. */ 356 357 static void 358 make_blocks (gimple_seq seq) 359 { 360 gimple_stmt_iterator i = gsi_start (seq); 361 gimple stmt = NULL; 362 bool start_new_block = true; 363 bool first_stmt_of_seq = true; 364 basic_block bb = ENTRY_BLOCK_PTR; 365 366 while (!gsi_end_p (i)) 367 { 368 gimple prev_stmt; 369 370 prev_stmt = stmt; 371 stmt = gsi_stmt (i); 372 373 /* If the statement starts a new basic block or if we have determined 374 in a previous pass that we need to create a new block for STMT, do 375 so now. */ 376 if (start_new_block || stmt_starts_bb_p (stmt, prev_stmt)) 377 { 378 if (!first_stmt_of_seq) 379 seq = gsi_split_seq_before (&i); 380 bb = create_basic_block (seq, NULL, bb); 381 start_new_block = false; 382 } 383 384 /* Now add STMT to BB and create the subgraphs for special statement 385 codes. */ 386 gimple_set_bb (stmt, bb); 387 388 if (computed_goto_p (stmt)) 389 found_computed_goto = true; 390 391 /* If STMT is a basic block terminator, set START_NEW_BLOCK for the 392 next iteration. */ 393 if (stmt_ends_bb_p (stmt)) 394 { 395 /* If the stmt can make abnormal goto use a new temporary 396 for the assignment to the LHS. This makes sure the old value 397 of the LHS is available on the abnormal edge. Otherwise 398 we will end up with overlapping life-ranges for abnormal 399 SSA names. */ 400 if (gimple_has_lhs (stmt) 401 && stmt_can_make_abnormal_goto (stmt) 402 && is_gimple_reg_type (TREE_TYPE (gimple_get_lhs (stmt)))) 403 { 404 tree lhs = gimple_get_lhs (stmt); 405 tree tmp = create_tmp_var (TREE_TYPE (lhs), NULL); 406 gimple s = gimple_build_assign (lhs, tmp); 407 gimple_set_location (s, gimple_location (stmt)); 408 gimple_set_block (s, gimple_block (stmt)); 409 gimple_set_lhs (stmt, tmp); 410 if (TREE_CODE (TREE_TYPE (tmp)) == COMPLEX_TYPE 411 || TREE_CODE (TREE_TYPE (tmp)) == VECTOR_TYPE) 412 DECL_GIMPLE_REG_P (tmp) = 1; 413 gsi_insert_after (&i, s, GSI_SAME_STMT); 414 } 415 start_new_block = true; 416 } 417 418 gsi_next (&i); 419 first_stmt_of_seq = false; 420 } 421 } 422 423 424 /* Create and return a new empty basic block after bb AFTER. */ 425 426 static basic_block 427 create_bb (void *h, void *e, basic_block after) 428 { 429 basic_block bb; 430 431 gcc_assert (!e); 432 433 /* Create and initialize a new basic block. Since alloc_block uses 434 GC allocation that clears memory to allocate a basic block, we do 435 not have to clear the newly allocated basic block here. */ 436 bb = alloc_block (); 437 438 bb->index = last_basic_block; 439 bb->flags = BB_NEW; 440 bb->il.gimple = ggc_alloc_cleared_gimple_bb_info (); 441 set_bb_seq (bb, h ? (gimple_seq) h : gimple_seq_alloc ()); 442 443 /* Add the new block to the linked list of blocks. */ 444 link_block (bb, after); 445 446 /* Grow the basic block array if needed. */ 447 if ((size_t) last_basic_block == VEC_length (basic_block, basic_block_info)) 448 { 449 size_t new_size = last_basic_block + (last_basic_block + 3) / 4; 450 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size); 451 } 452 453 /* Add the newly created block to the array. */ 454 SET_BASIC_BLOCK (last_basic_block, bb); 455 456 n_basic_blocks++; 457 last_basic_block++; 458 459 return bb; 460 } 461 462 463 /*--------------------------------------------------------------------------- 464 Edge creation 465 ---------------------------------------------------------------------------*/ 466 467 /* Fold COND_EXPR_COND of each COND_EXPR. */ 468 469 void 470 fold_cond_expr_cond (void) 471 { 472 basic_block bb; 473 474 FOR_EACH_BB (bb) 475 { 476 gimple stmt = last_stmt (bb); 477 478 if (stmt && gimple_code (stmt) == GIMPLE_COND) 479 { 480 location_t loc = gimple_location (stmt); 481 tree cond; 482 bool zerop, onep; 483 484 fold_defer_overflow_warnings (); 485 cond = fold_binary_loc (loc, gimple_cond_code (stmt), boolean_type_node, 486 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 487 if (cond) 488 { 489 zerop = integer_zerop (cond); 490 onep = integer_onep (cond); 491 } 492 else 493 zerop = onep = false; 494 495 fold_undefer_overflow_warnings (zerop || onep, 496 stmt, 497 WARN_STRICT_OVERFLOW_CONDITIONAL); 498 if (zerop) 499 gimple_cond_make_false (stmt); 500 else if (onep) 501 gimple_cond_make_true (stmt); 502 } 503 } 504 } 505 506 /* Join all the blocks in the flowgraph. */ 507 508 static void 509 make_edges (void) 510 { 511 basic_block bb; 512 struct omp_region *cur_region = NULL; 513 514 /* Create an edge from entry to the first block with executable 515 statements in it. */ 516 make_edge (ENTRY_BLOCK_PTR, BASIC_BLOCK (NUM_FIXED_BLOCKS), EDGE_FALLTHRU); 517 518 /* Traverse the basic block array placing edges. */ 519 FOR_EACH_BB (bb) 520 { 521 gimple last = last_stmt (bb); 522 bool fallthru; 523 524 if (last) 525 { 526 enum gimple_code code = gimple_code (last); 527 switch (code) 528 { 529 case GIMPLE_GOTO: 530 make_goto_expr_edges (bb); 531 fallthru = false; 532 break; 533 case GIMPLE_RETURN: 534 make_edge (bb, EXIT_BLOCK_PTR, 0); 535 fallthru = false; 536 break; 537 case GIMPLE_COND: 538 make_cond_expr_edges (bb); 539 fallthru = false; 540 break; 541 case GIMPLE_SWITCH: 542 make_gimple_switch_edges (bb); 543 fallthru = false; 544 break; 545 case GIMPLE_RESX: 546 make_eh_edges (last); 547 fallthru = false; 548 break; 549 case GIMPLE_EH_DISPATCH: 550 fallthru = make_eh_dispatch_edges (last); 551 break; 552 553 case GIMPLE_CALL: 554 /* If this function receives a nonlocal goto, then we need to 555 make edges from this call site to all the nonlocal goto 556 handlers. */ 557 if (stmt_can_make_abnormal_goto (last)) 558 make_abnormal_goto_edges (bb, true); 559 560 /* If this statement has reachable exception handlers, then 561 create abnormal edges to them. */ 562 make_eh_edges (last); 563 564 /* BUILTIN_RETURN is really a return statement. */ 565 if (gimple_call_builtin_p (last, BUILT_IN_RETURN)) 566 make_edge (bb, EXIT_BLOCK_PTR, 0), fallthru = false; 567 /* Some calls are known not to return. */ 568 else 569 fallthru = !(gimple_call_flags (last) & ECF_NORETURN); 570 break; 571 572 case GIMPLE_ASSIGN: 573 /* A GIMPLE_ASSIGN may throw internally and thus be considered 574 control-altering. */ 575 if (is_ctrl_altering_stmt (last)) 576 make_eh_edges (last); 577 fallthru = true; 578 break; 579 580 case GIMPLE_ASM: 581 make_gimple_asm_edges (bb); 582 fallthru = true; 583 break; 584 585 case GIMPLE_OMP_PARALLEL: 586 case GIMPLE_OMP_TASK: 587 case GIMPLE_OMP_FOR: 588 case GIMPLE_OMP_SINGLE: 589 case GIMPLE_OMP_MASTER: 590 case GIMPLE_OMP_ORDERED: 591 case GIMPLE_OMP_CRITICAL: 592 case GIMPLE_OMP_SECTION: 593 cur_region = new_omp_region (bb, code, cur_region); 594 fallthru = true; 595 break; 596 597 case GIMPLE_OMP_SECTIONS: 598 cur_region = new_omp_region (bb, code, cur_region); 599 fallthru = true; 600 break; 601 602 case GIMPLE_OMP_SECTIONS_SWITCH: 603 fallthru = false; 604 break; 605 606 case GIMPLE_OMP_ATOMIC_LOAD: 607 case GIMPLE_OMP_ATOMIC_STORE: 608 fallthru = true; 609 break; 610 611 case GIMPLE_OMP_RETURN: 612 /* In the case of a GIMPLE_OMP_SECTION, the edge will go 613 somewhere other than the next block. This will be 614 created later. */ 615 cur_region->exit = bb; 616 fallthru = cur_region->type != GIMPLE_OMP_SECTION; 617 cur_region = cur_region->outer; 618 break; 619 620 case GIMPLE_OMP_CONTINUE: 621 cur_region->cont = bb; 622 switch (cur_region->type) 623 { 624 case GIMPLE_OMP_FOR: 625 /* Mark all GIMPLE_OMP_FOR and GIMPLE_OMP_CONTINUE 626 succs edges as abnormal to prevent splitting 627 them. */ 628 single_succ_edge (cur_region->entry)->flags |= EDGE_ABNORMAL; 629 /* Make the loopback edge. */ 630 make_edge (bb, single_succ (cur_region->entry), 631 EDGE_ABNORMAL); 632 633 /* Create an edge from GIMPLE_OMP_FOR to exit, which 634 corresponds to the case that the body of the loop 635 is not executed at all. */ 636 make_edge (cur_region->entry, bb->next_bb, EDGE_ABNORMAL); 637 make_edge (bb, bb->next_bb, EDGE_FALLTHRU | EDGE_ABNORMAL); 638 fallthru = false; 639 break; 640 641 case GIMPLE_OMP_SECTIONS: 642 /* Wire up the edges into and out of the nested sections. */ 643 { 644 basic_block switch_bb = single_succ (cur_region->entry); 645 646 struct omp_region *i; 647 for (i = cur_region->inner; i ; i = i->next) 648 { 649 gcc_assert (i->type == GIMPLE_OMP_SECTION); 650 make_edge (switch_bb, i->entry, 0); 651 make_edge (i->exit, bb, EDGE_FALLTHRU); 652 } 653 654 /* Make the loopback edge to the block with 655 GIMPLE_OMP_SECTIONS_SWITCH. */ 656 make_edge (bb, switch_bb, 0); 657 658 /* Make the edge from the switch to exit. */ 659 make_edge (switch_bb, bb->next_bb, 0); 660 fallthru = false; 661 } 662 break; 663 664 default: 665 gcc_unreachable (); 666 } 667 break; 668 669 case GIMPLE_TRANSACTION: 670 { 671 tree abort_label = gimple_transaction_label (last); 672 if (abort_label) 673 make_edge (bb, label_to_block (abort_label), 0); 674 fallthru = true; 675 } 676 break; 677 678 default: 679 gcc_assert (!stmt_ends_bb_p (last)); 680 fallthru = true; 681 } 682 } 683 else 684 fallthru = true; 685 686 if (fallthru) 687 { 688 make_edge (bb, bb->next_bb, EDGE_FALLTHRU); 689 if (last) 690 assign_discriminator (gimple_location (last), bb->next_bb); 691 } 692 } 693 694 if (root_omp_region) 695 free_omp_regions (); 696 697 /* Fold COND_EXPR_COND of each COND_EXPR. */ 698 fold_cond_expr_cond (); 699 } 700 701 /* Trivial hash function for a location_t. ITEM is a pointer to 702 a hash table entry that maps a location_t to a discriminator. */ 703 704 static unsigned int 705 locus_map_hash (const void *item) 706 { 707 return ((const struct locus_discrim_map *) item)->locus; 708 } 709 710 /* Equality function for the locus-to-discriminator map. VA and VB 711 point to the two hash table entries to compare. */ 712 713 static int 714 locus_map_eq (const void *va, const void *vb) 715 { 716 const struct locus_discrim_map *a = (const struct locus_discrim_map *) va; 717 const struct locus_discrim_map *b = (const struct locus_discrim_map *) vb; 718 return a->locus == b->locus; 719 } 720 721 /* Find the next available discriminator value for LOCUS. The 722 discriminator distinguishes among several basic blocks that 723 share a common locus, allowing for more accurate sample-based 724 profiling. */ 725 726 static int 727 next_discriminator_for_locus (location_t locus) 728 { 729 struct locus_discrim_map item; 730 struct locus_discrim_map **slot; 731 732 item.locus = locus; 733 item.discriminator = 0; 734 slot = (struct locus_discrim_map **) 735 htab_find_slot_with_hash (discriminator_per_locus, (void *) &item, 736 (hashval_t) locus, INSERT); 737 gcc_assert (slot); 738 if (*slot == HTAB_EMPTY_ENTRY) 739 { 740 *slot = XNEW (struct locus_discrim_map); 741 gcc_assert (*slot); 742 (*slot)->locus = locus; 743 (*slot)->discriminator = 0; 744 } 745 (*slot)->discriminator++; 746 return (*slot)->discriminator; 747 } 748 749 /* Return TRUE if LOCUS1 and LOCUS2 refer to the same source line. */ 750 751 static bool 752 same_line_p (location_t locus1, location_t locus2) 753 { 754 expanded_location from, to; 755 756 if (locus1 == locus2) 757 return true; 758 759 from = expand_location (locus1); 760 to = expand_location (locus2); 761 762 if (from.line != to.line) 763 return false; 764 if (from.file == to.file) 765 return true; 766 return (from.file != NULL 767 && to.file != NULL 768 && filename_cmp (from.file, to.file) == 0); 769 } 770 771 /* Assign a unique discriminator value to block BB if it begins at the same 772 LOCUS as its predecessor block. */ 773 774 static void 775 assign_discriminator (location_t locus, basic_block bb) 776 { 777 gimple first_in_to_bb, last_in_to_bb; 778 779 if (locus == 0 || bb->discriminator != 0) 780 return; 781 782 first_in_to_bb = first_non_label_stmt (bb); 783 last_in_to_bb = last_stmt (bb); 784 if ((first_in_to_bb && same_line_p (locus, gimple_location (first_in_to_bb))) 785 || (last_in_to_bb && same_line_p (locus, gimple_location (last_in_to_bb)))) 786 bb->discriminator = next_discriminator_for_locus (locus); 787 } 788 789 /* Create the edges for a GIMPLE_COND starting at block BB. */ 790 791 static void 792 make_cond_expr_edges (basic_block bb) 793 { 794 gimple entry = last_stmt (bb); 795 gimple then_stmt, else_stmt; 796 basic_block then_bb, else_bb; 797 tree then_label, else_label; 798 edge e; 799 location_t entry_locus; 800 801 gcc_assert (entry); 802 gcc_assert (gimple_code (entry) == GIMPLE_COND); 803 804 entry_locus = gimple_location (entry); 805 806 /* Entry basic blocks for each component. */ 807 then_label = gimple_cond_true_label (entry); 808 else_label = gimple_cond_false_label (entry); 809 then_bb = label_to_block (then_label); 810 else_bb = label_to_block (else_label); 811 then_stmt = first_stmt (then_bb); 812 else_stmt = first_stmt (else_bb); 813 814 e = make_edge (bb, then_bb, EDGE_TRUE_VALUE); 815 assign_discriminator (entry_locus, then_bb); 816 e->goto_locus = gimple_location (then_stmt); 817 if (e->goto_locus) 818 e->goto_block = gimple_block (then_stmt); 819 e = make_edge (bb, else_bb, EDGE_FALSE_VALUE); 820 if (e) 821 { 822 assign_discriminator (entry_locus, else_bb); 823 e->goto_locus = gimple_location (else_stmt); 824 if (e->goto_locus) 825 e->goto_block = gimple_block (else_stmt); 826 } 827 828 /* We do not need the labels anymore. */ 829 gimple_cond_set_true_label (entry, NULL_TREE); 830 gimple_cond_set_false_label (entry, NULL_TREE); 831 } 832 833 834 /* Called for each element in the hash table (P) as we delete the 835 edge to cases hash table. 836 837 Clear all the TREE_CHAINs to prevent problems with copying of 838 SWITCH_EXPRs and structure sharing rules, then free the hash table 839 element. */ 840 841 static bool 842 edge_to_cases_cleanup (const void *key ATTRIBUTE_UNUSED, void **value, 843 void *data ATTRIBUTE_UNUSED) 844 { 845 tree t, next; 846 847 for (t = (tree) *value; t; t = next) 848 { 849 next = CASE_CHAIN (t); 850 CASE_CHAIN (t) = NULL; 851 } 852 853 *value = NULL; 854 return true; 855 } 856 857 /* Start recording information mapping edges to case labels. */ 858 859 void 860 start_recording_case_labels (void) 861 { 862 gcc_assert (edge_to_cases == NULL); 863 edge_to_cases = pointer_map_create (); 864 touched_switch_bbs = BITMAP_ALLOC (NULL); 865 } 866 867 /* Return nonzero if we are recording information for case labels. */ 868 869 static bool 870 recording_case_labels_p (void) 871 { 872 return (edge_to_cases != NULL); 873 } 874 875 /* Stop recording information mapping edges to case labels and 876 remove any information we have recorded. */ 877 void 878 end_recording_case_labels (void) 879 { 880 bitmap_iterator bi; 881 unsigned i; 882 pointer_map_traverse (edge_to_cases, edge_to_cases_cleanup, NULL); 883 pointer_map_destroy (edge_to_cases); 884 edge_to_cases = NULL; 885 EXECUTE_IF_SET_IN_BITMAP (touched_switch_bbs, 0, i, bi) 886 { 887 basic_block bb = BASIC_BLOCK (i); 888 if (bb) 889 { 890 gimple stmt = last_stmt (bb); 891 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 892 group_case_labels_stmt (stmt); 893 } 894 } 895 BITMAP_FREE (touched_switch_bbs); 896 } 897 898 /* If we are inside a {start,end}_recording_cases block, then return 899 a chain of CASE_LABEL_EXPRs from T which reference E. 900 901 Otherwise return NULL. */ 902 903 static tree 904 get_cases_for_edge (edge e, gimple t) 905 { 906 void **slot; 907 size_t i, n; 908 909 /* If we are not recording cases, then we do not have CASE_LABEL_EXPR 910 chains available. Return NULL so the caller can detect this case. */ 911 if (!recording_case_labels_p ()) 912 return NULL; 913 914 slot = pointer_map_contains (edge_to_cases, e); 915 if (slot) 916 return (tree) *slot; 917 918 /* If we did not find E in the hash table, then this must be the first 919 time we have been queried for information about E & T. Add all the 920 elements from T to the hash table then perform the query again. */ 921 922 n = gimple_switch_num_labels (t); 923 for (i = 0; i < n; i++) 924 { 925 tree elt = gimple_switch_label (t, i); 926 tree lab = CASE_LABEL (elt); 927 basic_block label_bb = label_to_block (lab); 928 edge this_edge = find_edge (e->src, label_bb); 929 930 /* Add it to the chain of CASE_LABEL_EXPRs referencing E, or create 931 a new chain. */ 932 slot = pointer_map_insert (edge_to_cases, this_edge); 933 CASE_CHAIN (elt) = (tree) *slot; 934 *slot = elt; 935 } 936 937 return (tree) *pointer_map_contains (edge_to_cases, e); 938 } 939 940 /* Create the edges for a GIMPLE_SWITCH starting at block BB. */ 941 942 static void 943 make_gimple_switch_edges (basic_block bb) 944 { 945 gimple entry = last_stmt (bb); 946 location_t entry_locus; 947 size_t i, n; 948 949 entry_locus = gimple_location (entry); 950 951 n = gimple_switch_num_labels (entry); 952 953 for (i = 0; i < n; ++i) 954 { 955 tree lab = CASE_LABEL (gimple_switch_label (entry, i)); 956 basic_block label_bb = label_to_block (lab); 957 make_edge (bb, label_bb, 0); 958 assign_discriminator (entry_locus, label_bb); 959 } 960 } 961 962 963 /* Return the basic block holding label DEST. */ 964 965 basic_block 966 label_to_block_fn (struct function *ifun, tree dest) 967 { 968 int uid = LABEL_DECL_UID (dest); 969 970 /* We would die hard when faced by an undefined label. Emit a label to 971 the very first basic block. This will hopefully make even the dataflow 972 and undefined variable warnings quite right. */ 973 if (seen_error () && uid < 0) 974 { 975 gimple_stmt_iterator gsi = gsi_start_bb (BASIC_BLOCK (NUM_FIXED_BLOCKS)); 976 gimple stmt; 977 978 stmt = gimple_build_label (dest); 979 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT); 980 uid = LABEL_DECL_UID (dest); 981 } 982 if (VEC_length (basic_block, ifun->cfg->x_label_to_block_map) 983 <= (unsigned int) uid) 984 return NULL; 985 return VEC_index (basic_block, ifun->cfg->x_label_to_block_map, uid); 986 } 987 988 /* Create edges for an abnormal goto statement at block BB. If FOR_CALL 989 is true, the source statement is a CALL_EXPR instead of a GOTO_EXPR. */ 990 991 void 992 make_abnormal_goto_edges (basic_block bb, bool for_call) 993 { 994 basic_block target_bb; 995 gimple_stmt_iterator gsi; 996 997 FOR_EACH_BB (target_bb) 998 for (gsi = gsi_start_bb (target_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 999 { 1000 gimple label_stmt = gsi_stmt (gsi); 1001 tree target; 1002 1003 if (gimple_code (label_stmt) != GIMPLE_LABEL) 1004 break; 1005 1006 target = gimple_label_label (label_stmt); 1007 1008 /* Make an edge to every label block that has been marked as a 1009 potential target for a computed goto or a non-local goto. */ 1010 if ((FORCED_LABEL (target) && !for_call) 1011 || (DECL_NONLOCAL (target) && for_call)) 1012 { 1013 make_edge (bb, target_bb, EDGE_ABNORMAL); 1014 break; 1015 } 1016 } 1017 } 1018 1019 /* Create edges for a goto statement at block BB. */ 1020 1021 static void 1022 make_goto_expr_edges (basic_block bb) 1023 { 1024 gimple_stmt_iterator last = gsi_last_bb (bb); 1025 gimple goto_t = gsi_stmt (last); 1026 1027 /* A simple GOTO creates normal edges. */ 1028 if (simple_goto_p (goto_t)) 1029 { 1030 tree dest = gimple_goto_dest (goto_t); 1031 basic_block label_bb = label_to_block (dest); 1032 edge e = make_edge (bb, label_bb, EDGE_FALLTHRU); 1033 e->goto_locus = gimple_location (goto_t); 1034 assign_discriminator (e->goto_locus, label_bb); 1035 if (e->goto_locus) 1036 e->goto_block = gimple_block (goto_t); 1037 gsi_remove (&last, true); 1038 return; 1039 } 1040 1041 /* A computed GOTO creates abnormal edges. */ 1042 make_abnormal_goto_edges (bb, false); 1043 } 1044 1045 /* Create edges for an asm statement with labels at block BB. */ 1046 1047 static void 1048 make_gimple_asm_edges (basic_block bb) 1049 { 1050 gimple stmt = last_stmt (bb); 1051 location_t stmt_loc = gimple_location (stmt); 1052 int i, n = gimple_asm_nlabels (stmt); 1053 1054 for (i = 0; i < n; ++i) 1055 { 1056 tree label = TREE_VALUE (gimple_asm_label_op (stmt, i)); 1057 basic_block label_bb = label_to_block (label); 1058 make_edge (bb, label_bb, 0); 1059 assign_discriminator (stmt_loc, label_bb); 1060 } 1061 } 1062 1063 /*--------------------------------------------------------------------------- 1064 Flowgraph analysis 1065 ---------------------------------------------------------------------------*/ 1066 1067 /* Cleanup useless labels in basic blocks. This is something we wish 1068 to do early because it allows us to group case labels before creating 1069 the edges for the CFG, and it speeds up block statement iterators in 1070 all passes later on. 1071 We rerun this pass after CFG is created, to get rid of the labels that 1072 are no longer referenced. After then we do not run it any more, since 1073 (almost) no new labels should be created. */ 1074 1075 /* A map from basic block index to the leading label of that block. */ 1076 static struct label_record 1077 { 1078 /* The label. */ 1079 tree label; 1080 1081 /* True if the label is referenced from somewhere. */ 1082 bool used; 1083 } *label_for_bb; 1084 1085 /* Given LABEL return the first label in the same basic block. */ 1086 1087 static tree 1088 main_block_label (tree label) 1089 { 1090 basic_block bb = label_to_block (label); 1091 tree main_label = label_for_bb[bb->index].label; 1092 1093 /* label_to_block possibly inserted undefined label into the chain. */ 1094 if (!main_label) 1095 { 1096 label_for_bb[bb->index].label = label; 1097 main_label = label; 1098 } 1099 1100 label_for_bb[bb->index].used = true; 1101 return main_label; 1102 } 1103 1104 /* Clean up redundant labels within the exception tree. */ 1105 1106 static void 1107 cleanup_dead_labels_eh (void) 1108 { 1109 eh_landing_pad lp; 1110 eh_region r; 1111 tree lab; 1112 int i; 1113 1114 if (cfun->eh == NULL) 1115 return; 1116 1117 for (i = 1; VEC_iterate (eh_landing_pad, cfun->eh->lp_array, i, lp); ++i) 1118 if (lp && lp->post_landing_pad) 1119 { 1120 lab = main_block_label (lp->post_landing_pad); 1121 if (lab != lp->post_landing_pad) 1122 { 1123 EH_LANDING_PAD_NR (lp->post_landing_pad) = 0; 1124 EH_LANDING_PAD_NR (lab) = lp->index; 1125 } 1126 } 1127 1128 FOR_ALL_EH_REGION (r) 1129 switch (r->type) 1130 { 1131 case ERT_CLEANUP: 1132 case ERT_MUST_NOT_THROW: 1133 break; 1134 1135 case ERT_TRY: 1136 { 1137 eh_catch c; 1138 for (c = r->u.eh_try.first_catch; c ; c = c->next_catch) 1139 { 1140 lab = c->label; 1141 if (lab) 1142 c->label = main_block_label (lab); 1143 } 1144 } 1145 break; 1146 1147 case ERT_ALLOWED_EXCEPTIONS: 1148 lab = r->u.allowed.label; 1149 if (lab) 1150 r->u.allowed.label = main_block_label (lab); 1151 break; 1152 } 1153 } 1154 1155 1156 /* Cleanup redundant labels. This is a three-step process: 1157 1) Find the leading label for each block. 1158 2) Redirect all references to labels to the leading labels. 1159 3) Cleanup all useless labels. */ 1160 1161 void 1162 cleanup_dead_labels (void) 1163 { 1164 basic_block bb; 1165 label_for_bb = XCNEWVEC (struct label_record, last_basic_block); 1166 1167 /* Find a suitable label for each block. We use the first user-defined 1168 label if there is one, or otherwise just the first label we see. */ 1169 FOR_EACH_BB (bb) 1170 { 1171 gimple_stmt_iterator i; 1172 1173 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) 1174 { 1175 tree label; 1176 gimple stmt = gsi_stmt (i); 1177 1178 if (gimple_code (stmt) != GIMPLE_LABEL) 1179 break; 1180 1181 label = gimple_label_label (stmt); 1182 1183 /* If we have not yet seen a label for the current block, 1184 remember this one and see if there are more labels. */ 1185 if (!label_for_bb[bb->index].label) 1186 { 1187 label_for_bb[bb->index].label = label; 1188 continue; 1189 } 1190 1191 /* If we did see a label for the current block already, but it 1192 is an artificially created label, replace it if the current 1193 label is a user defined label. */ 1194 if (!DECL_ARTIFICIAL (label) 1195 && DECL_ARTIFICIAL (label_for_bb[bb->index].label)) 1196 { 1197 label_for_bb[bb->index].label = label; 1198 break; 1199 } 1200 } 1201 } 1202 1203 /* Now redirect all jumps/branches to the selected label. 1204 First do so for each block ending in a control statement. */ 1205 FOR_EACH_BB (bb) 1206 { 1207 gimple stmt = last_stmt (bb); 1208 tree label, new_label; 1209 1210 if (!stmt) 1211 continue; 1212 1213 switch (gimple_code (stmt)) 1214 { 1215 case GIMPLE_COND: 1216 label = gimple_cond_true_label (stmt); 1217 if (label) 1218 { 1219 new_label = main_block_label (label); 1220 if (new_label != label) 1221 gimple_cond_set_true_label (stmt, new_label); 1222 } 1223 1224 label = gimple_cond_false_label (stmt); 1225 if (label) 1226 { 1227 new_label = main_block_label (label); 1228 if (new_label != label) 1229 gimple_cond_set_false_label (stmt, new_label); 1230 } 1231 break; 1232 1233 case GIMPLE_SWITCH: 1234 { 1235 size_t i, n = gimple_switch_num_labels (stmt); 1236 1237 /* Replace all destination labels. */ 1238 for (i = 0; i < n; ++i) 1239 { 1240 tree case_label = gimple_switch_label (stmt, i); 1241 label = CASE_LABEL (case_label); 1242 new_label = main_block_label (label); 1243 if (new_label != label) 1244 CASE_LABEL (case_label) = new_label; 1245 } 1246 break; 1247 } 1248 1249 case GIMPLE_ASM: 1250 { 1251 int i, n = gimple_asm_nlabels (stmt); 1252 1253 for (i = 0; i < n; ++i) 1254 { 1255 tree cons = gimple_asm_label_op (stmt, i); 1256 tree label = main_block_label (TREE_VALUE (cons)); 1257 TREE_VALUE (cons) = label; 1258 } 1259 break; 1260 } 1261 1262 /* We have to handle gotos until they're removed, and we don't 1263 remove them until after we've created the CFG edges. */ 1264 case GIMPLE_GOTO: 1265 if (!computed_goto_p (stmt)) 1266 { 1267 label = gimple_goto_dest (stmt); 1268 new_label = main_block_label (label); 1269 if (new_label != label) 1270 gimple_goto_set_dest (stmt, new_label); 1271 } 1272 break; 1273 1274 case GIMPLE_TRANSACTION: 1275 { 1276 tree label = gimple_transaction_label (stmt); 1277 if (label) 1278 { 1279 tree new_label = main_block_label (label); 1280 if (new_label != label) 1281 gimple_transaction_set_label (stmt, new_label); 1282 } 1283 } 1284 break; 1285 1286 default: 1287 break; 1288 } 1289 } 1290 1291 /* Do the same for the exception region tree labels. */ 1292 cleanup_dead_labels_eh (); 1293 1294 /* Finally, purge dead labels. All user-defined labels and labels that 1295 can be the target of non-local gotos and labels which have their 1296 address taken are preserved. */ 1297 FOR_EACH_BB (bb) 1298 { 1299 gimple_stmt_iterator i; 1300 tree label_for_this_bb = label_for_bb[bb->index].label; 1301 1302 if (!label_for_this_bb) 1303 continue; 1304 1305 /* If the main label of the block is unused, we may still remove it. */ 1306 if (!label_for_bb[bb->index].used) 1307 label_for_this_bb = NULL; 1308 1309 for (i = gsi_start_bb (bb); !gsi_end_p (i); ) 1310 { 1311 tree label; 1312 gimple stmt = gsi_stmt (i); 1313 1314 if (gimple_code (stmt) != GIMPLE_LABEL) 1315 break; 1316 1317 label = gimple_label_label (stmt); 1318 1319 if (label == label_for_this_bb 1320 || !DECL_ARTIFICIAL (label) 1321 || DECL_NONLOCAL (label) 1322 || FORCED_LABEL (label)) 1323 gsi_next (&i); 1324 else 1325 gsi_remove (&i, true); 1326 } 1327 } 1328 1329 free (label_for_bb); 1330 } 1331 1332 /* Scan the sorted vector of cases in STMT (a GIMPLE_SWITCH) and combine 1333 the ones jumping to the same label. 1334 Eg. three separate entries 1: 2: 3: become one entry 1..3: */ 1335 1336 static void 1337 group_case_labels_stmt (gimple stmt) 1338 { 1339 int old_size = gimple_switch_num_labels (stmt); 1340 int i, j, new_size = old_size; 1341 tree default_case = NULL_TREE; 1342 tree default_label = NULL_TREE; 1343 bool has_default; 1344 1345 /* The default label is always the first case in a switch 1346 statement after gimplification if it was not optimized 1347 away */ 1348 if (!CASE_LOW (gimple_switch_default_label (stmt)) 1349 && !CASE_HIGH (gimple_switch_default_label (stmt))) 1350 { 1351 default_case = gimple_switch_default_label (stmt); 1352 default_label = CASE_LABEL (default_case); 1353 has_default = true; 1354 } 1355 else 1356 has_default = false; 1357 1358 /* Look for possible opportunities to merge cases. */ 1359 if (has_default) 1360 i = 1; 1361 else 1362 i = 0; 1363 while (i < old_size) 1364 { 1365 tree base_case, base_label, base_high; 1366 base_case = gimple_switch_label (stmt, i); 1367 1368 gcc_assert (base_case); 1369 base_label = CASE_LABEL (base_case); 1370 1371 /* Discard cases that have the same destination as the 1372 default case. */ 1373 if (base_label == default_label) 1374 { 1375 gimple_switch_set_label (stmt, i, NULL_TREE); 1376 i++; 1377 new_size--; 1378 continue; 1379 } 1380 1381 base_high = CASE_HIGH (base_case) 1382 ? CASE_HIGH (base_case) 1383 : CASE_LOW (base_case); 1384 i++; 1385 1386 /* Try to merge case labels. Break out when we reach the end 1387 of the label vector or when we cannot merge the next case 1388 label with the current one. */ 1389 while (i < old_size) 1390 { 1391 tree merge_case = gimple_switch_label (stmt, i); 1392 tree merge_label = CASE_LABEL (merge_case); 1393 double_int bhp1 = double_int_add (tree_to_double_int (base_high), 1394 double_int_one); 1395 1396 /* Merge the cases if they jump to the same place, 1397 and their ranges are consecutive. */ 1398 if (merge_label == base_label 1399 && double_int_equal_p (tree_to_double_int (CASE_LOW (merge_case)), 1400 bhp1)) 1401 { 1402 base_high = CASE_HIGH (merge_case) ? 1403 CASE_HIGH (merge_case) : CASE_LOW (merge_case); 1404 CASE_HIGH (base_case) = base_high; 1405 gimple_switch_set_label (stmt, i, NULL_TREE); 1406 new_size--; 1407 i++; 1408 } 1409 else 1410 break; 1411 } 1412 } 1413 1414 /* Compress the case labels in the label vector, and adjust the 1415 length of the vector. */ 1416 for (i = 0, j = 0; i < new_size; i++) 1417 { 1418 while (! gimple_switch_label (stmt, j)) 1419 j++; 1420 gimple_switch_set_label (stmt, i, 1421 gimple_switch_label (stmt, j++)); 1422 } 1423 1424 gcc_assert (new_size <= old_size); 1425 gimple_switch_set_num_labels (stmt, new_size); 1426 } 1427 1428 /* Look for blocks ending in a multiway branch (a GIMPLE_SWITCH), 1429 and scan the sorted vector of cases. Combine the ones jumping to the 1430 same label. */ 1431 1432 void 1433 group_case_labels (void) 1434 { 1435 basic_block bb; 1436 1437 FOR_EACH_BB (bb) 1438 { 1439 gimple stmt = last_stmt (bb); 1440 if (stmt && gimple_code (stmt) == GIMPLE_SWITCH) 1441 group_case_labels_stmt (stmt); 1442 } 1443 } 1444 1445 /* Checks whether we can merge block B into block A. */ 1446 1447 static bool 1448 gimple_can_merge_blocks_p (basic_block a, basic_block b) 1449 { 1450 gimple stmt; 1451 gimple_stmt_iterator gsi; 1452 gimple_seq phis; 1453 1454 if (!single_succ_p (a)) 1455 return false; 1456 1457 if (single_succ_edge (a)->flags & (EDGE_ABNORMAL | EDGE_EH | EDGE_PRESERVE)) 1458 return false; 1459 1460 if (single_succ (a) != b) 1461 return false; 1462 1463 if (!single_pred_p (b)) 1464 return false; 1465 1466 if (b == EXIT_BLOCK_PTR) 1467 return false; 1468 1469 /* If A ends by a statement causing exceptions or something similar, we 1470 cannot merge the blocks. */ 1471 stmt = last_stmt (a); 1472 if (stmt && stmt_ends_bb_p (stmt)) 1473 return false; 1474 1475 /* Do not allow a block with only a non-local label to be merged. */ 1476 if (stmt 1477 && gimple_code (stmt) == GIMPLE_LABEL 1478 && DECL_NONLOCAL (gimple_label_label (stmt))) 1479 return false; 1480 1481 /* Examine the labels at the beginning of B. */ 1482 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi)) 1483 { 1484 tree lab; 1485 stmt = gsi_stmt (gsi); 1486 if (gimple_code (stmt) != GIMPLE_LABEL) 1487 break; 1488 lab = gimple_label_label (stmt); 1489 1490 /* Do not remove user forced labels or for -O0 any user labels. */ 1491 if (!DECL_ARTIFICIAL (lab) && (!optimize || FORCED_LABEL (lab))) 1492 return false; 1493 } 1494 1495 /* Protect the loop latches. */ 1496 if (current_loops && b->loop_father->latch == b) 1497 return false; 1498 1499 /* It must be possible to eliminate all phi nodes in B. If ssa form 1500 is not up-to-date and a name-mapping is registered, we cannot eliminate 1501 any phis. Symbols marked for renaming are never a problem though. */ 1502 phis = phi_nodes (b); 1503 if (!gimple_seq_empty_p (phis) 1504 && name_mappings_registered_p ()) 1505 return false; 1506 1507 /* When not optimizing, don't merge if we'd lose goto_locus. */ 1508 if (!optimize 1509 && single_succ_edge (a)->goto_locus != UNKNOWN_LOCATION) 1510 { 1511 location_t goto_locus = single_succ_edge (a)->goto_locus; 1512 gimple_stmt_iterator prev, next; 1513 prev = gsi_last_nondebug_bb (a); 1514 next = gsi_after_labels (b); 1515 if (!gsi_end_p (next) && is_gimple_debug (gsi_stmt (next))) 1516 gsi_next_nondebug (&next); 1517 if ((gsi_end_p (prev) 1518 || gimple_location (gsi_stmt (prev)) != goto_locus) 1519 && (gsi_end_p (next) 1520 || gimple_location (gsi_stmt (next)) != goto_locus)) 1521 return false; 1522 } 1523 1524 return true; 1525 } 1526 1527 /* Return true if the var whose chain of uses starts at PTR has no 1528 nondebug uses. */ 1529 bool 1530 has_zero_uses_1 (const ssa_use_operand_t *head) 1531 { 1532 const ssa_use_operand_t *ptr; 1533 1534 for (ptr = head->next; ptr != head; ptr = ptr->next) 1535 if (!is_gimple_debug (USE_STMT (ptr))) 1536 return false; 1537 1538 return true; 1539 } 1540 1541 /* Return true if the var whose chain of uses starts at PTR has a 1542 single nondebug use. Set USE_P and STMT to that single nondebug 1543 use, if so, or to NULL otherwise. */ 1544 bool 1545 single_imm_use_1 (const ssa_use_operand_t *head, 1546 use_operand_p *use_p, gimple *stmt) 1547 { 1548 ssa_use_operand_t *ptr, *single_use = 0; 1549 1550 for (ptr = head->next; ptr != head; ptr = ptr->next) 1551 if (!is_gimple_debug (USE_STMT (ptr))) 1552 { 1553 if (single_use) 1554 { 1555 single_use = NULL; 1556 break; 1557 } 1558 single_use = ptr; 1559 } 1560 1561 if (use_p) 1562 *use_p = single_use; 1563 1564 if (stmt) 1565 *stmt = single_use ? single_use->loc.stmt : NULL; 1566 1567 return !!single_use; 1568 } 1569 1570 /* Replaces all uses of NAME by VAL. */ 1571 1572 void 1573 replace_uses_by (tree name, tree val) 1574 { 1575 imm_use_iterator imm_iter; 1576 use_operand_p use; 1577 gimple stmt; 1578 edge e; 1579 1580 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, name) 1581 { 1582 FOR_EACH_IMM_USE_ON_STMT (use, imm_iter) 1583 { 1584 replace_exp (use, val); 1585 1586 if (gimple_code (stmt) == GIMPLE_PHI) 1587 { 1588 e = gimple_phi_arg_edge (stmt, PHI_ARG_INDEX_FROM_USE (use)); 1589 if (e->flags & EDGE_ABNORMAL) 1590 { 1591 /* This can only occur for virtual operands, since 1592 for the real ones SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name)) 1593 would prevent replacement. */ 1594 gcc_checking_assert (!is_gimple_reg (name)); 1595 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1; 1596 } 1597 } 1598 } 1599 1600 if (gimple_code (stmt) != GIMPLE_PHI) 1601 { 1602 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 1603 gimple orig_stmt = stmt; 1604 size_t i; 1605 1606 /* Mark the block if we changed the last stmt in it. */ 1607 if (cfgcleanup_altered_bbs 1608 && stmt_ends_bb_p (stmt)) 1609 bitmap_set_bit (cfgcleanup_altered_bbs, gimple_bb (stmt)->index); 1610 1611 /* FIXME. It shouldn't be required to keep TREE_CONSTANT 1612 on ADDR_EXPRs up-to-date on GIMPLE. Propagation will 1613 only change sth from non-invariant to invariant, and only 1614 when propagating constants. */ 1615 if (is_gimple_min_invariant (val)) 1616 for (i = 0; i < gimple_num_ops (stmt); i++) 1617 { 1618 tree op = gimple_op (stmt, i); 1619 /* Operands may be empty here. For example, the labels 1620 of a GIMPLE_COND are nulled out following the creation 1621 of the corresponding CFG edges. */ 1622 if (op && TREE_CODE (op) == ADDR_EXPR) 1623 recompute_tree_invariant_for_addr_expr (op); 1624 } 1625 1626 if (fold_stmt (&gsi)) 1627 stmt = gsi_stmt (gsi); 1628 1629 if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt)) 1630 gimple_purge_dead_eh_edges (gimple_bb (stmt)); 1631 1632 update_stmt (stmt); 1633 } 1634 } 1635 1636 gcc_checking_assert (has_zero_uses (name)); 1637 1638 /* Also update the trees stored in loop structures. */ 1639 if (current_loops) 1640 { 1641 struct loop *loop; 1642 loop_iterator li; 1643 1644 FOR_EACH_LOOP (li, loop, 0) 1645 { 1646 substitute_in_loop_info (loop, name, val); 1647 } 1648 } 1649 } 1650 1651 /* Merge block B into block A. */ 1652 1653 static void 1654 gimple_merge_blocks (basic_block a, basic_block b) 1655 { 1656 gimple_stmt_iterator last, gsi, psi; 1657 gimple_seq phis = phi_nodes (b); 1658 1659 if (dump_file) 1660 fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index); 1661 1662 /* Remove all single-valued PHI nodes from block B of the form 1663 V_i = PHI <V_j> by propagating V_j to all the uses of V_i. */ 1664 gsi = gsi_last_bb (a); 1665 for (psi = gsi_start (phis); !gsi_end_p (psi); ) 1666 { 1667 gimple phi = gsi_stmt (psi); 1668 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0); 1669 gimple copy; 1670 bool may_replace_uses = !is_gimple_reg (def) 1671 || may_propagate_copy (def, use); 1672 1673 /* In case we maintain loop closed ssa form, do not propagate arguments 1674 of loop exit phi nodes. */ 1675 if (current_loops 1676 && loops_state_satisfies_p (LOOP_CLOSED_SSA) 1677 && is_gimple_reg (def) 1678 && TREE_CODE (use) == SSA_NAME 1679 && a->loop_father != b->loop_father) 1680 may_replace_uses = false; 1681 1682 if (!may_replace_uses) 1683 { 1684 gcc_assert (is_gimple_reg (def)); 1685 1686 /* Note that just emitting the copies is fine -- there is no problem 1687 with ordering of phi nodes. This is because A is the single 1688 predecessor of B, therefore results of the phi nodes cannot 1689 appear as arguments of the phi nodes. */ 1690 copy = gimple_build_assign (def, use); 1691 gsi_insert_after (&gsi, copy, GSI_NEW_STMT); 1692 remove_phi_node (&psi, false); 1693 } 1694 else 1695 { 1696 /* If we deal with a PHI for virtual operands, we can simply 1697 propagate these without fussing with folding or updating 1698 the stmt. */ 1699 if (!is_gimple_reg (def)) 1700 { 1701 imm_use_iterator iter; 1702 use_operand_p use_p; 1703 gimple stmt; 1704 1705 FOR_EACH_IMM_USE_STMT (stmt, iter, def) 1706 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 1707 SET_USE (use_p, use); 1708 1709 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)) 1710 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use) = 1; 1711 } 1712 else 1713 replace_uses_by (def, use); 1714 1715 remove_phi_node (&psi, true); 1716 } 1717 } 1718 1719 /* Ensure that B follows A. */ 1720 move_block_after (b, a); 1721 1722 gcc_assert (single_succ_edge (a)->flags & EDGE_FALLTHRU); 1723 gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a))); 1724 1725 /* Remove labels from B and set gimple_bb to A for other statements. */ 1726 for (gsi = gsi_start_bb (b); !gsi_end_p (gsi);) 1727 { 1728 gimple stmt = gsi_stmt (gsi); 1729 if (gimple_code (stmt) == GIMPLE_LABEL) 1730 { 1731 tree label = gimple_label_label (stmt); 1732 int lp_nr; 1733 1734 gsi_remove (&gsi, false); 1735 1736 /* Now that we can thread computed gotos, we might have 1737 a situation where we have a forced label in block B 1738 However, the label at the start of block B might still be 1739 used in other ways (think about the runtime checking for 1740 Fortran assigned gotos). So we can not just delete the 1741 label. Instead we move the label to the start of block A. */ 1742 if (FORCED_LABEL (label)) 1743 { 1744 gimple_stmt_iterator dest_gsi = gsi_start_bb (a); 1745 gsi_insert_before (&dest_gsi, stmt, GSI_NEW_STMT); 1746 } 1747 /* Other user labels keep around in a form of a debug stmt. */ 1748 else if (!DECL_ARTIFICIAL (label) && MAY_HAVE_DEBUG_STMTS) 1749 { 1750 gimple dbg = gimple_build_debug_bind (label, 1751 integer_zero_node, 1752 stmt); 1753 gimple_debug_bind_reset_value (dbg); 1754 gsi_insert_before (&gsi, dbg, GSI_SAME_STMT); 1755 } 1756 1757 lp_nr = EH_LANDING_PAD_NR (label); 1758 if (lp_nr) 1759 { 1760 eh_landing_pad lp = get_eh_landing_pad_from_number (lp_nr); 1761 lp->post_landing_pad = NULL; 1762 } 1763 } 1764 else 1765 { 1766 gimple_set_bb (stmt, a); 1767 gsi_next (&gsi); 1768 } 1769 } 1770 1771 /* Merge the sequences. */ 1772 last = gsi_last_bb (a); 1773 gsi_insert_seq_after (&last, bb_seq (b), GSI_NEW_STMT); 1774 set_bb_seq (b, NULL); 1775 1776 if (cfgcleanup_altered_bbs) 1777 bitmap_set_bit (cfgcleanup_altered_bbs, a->index); 1778 } 1779 1780 1781 /* Return the one of two successors of BB that is not reachable by a 1782 complex edge, if there is one. Else, return BB. We use 1783 this in optimizations that use post-dominators for their heuristics, 1784 to catch the cases in C++ where function calls are involved. */ 1785 1786 basic_block 1787 single_noncomplex_succ (basic_block bb) 1788 { 1789 edge e0, e1; 1790 if (EDGE_COUNT (bb->succs) != 2) 1791 return bb; 1792 1793 e0 = EDGE_SUCC (bb, 0); 1794 e1 = EDGE_SUCC (bb, 1); 1795 if (e0->flags & EDGE_COMPLEX) 1796 return e1->dest; 1797 if (e1->flags & EDGE_COMPLEX) 1798 return e0->dest; 1799 1800 return bb; 1801 } 1802 1803 /* T is CALL_EXPR. Set current_function_calls_* flags. */ 1804 1805 void 1806 notice_special_calls (gimple call) 1807 { 1808 int flags = gimple_call_flags (call); 1809 1810 if (flags & ECF_MAY_BE_ALLOCA) 1811 cfun->calls_alloca = true; 1812 if (flags & ECF_RETURNS_TWICE) 1813 cfun->calls_setjmp = true; 1814 } 1815 1816 1817 /* Clear flags set by notice_special_calls. Used by dead code removal 1818 to update the flags. */ 1819 1820 void 1821 clear_special_calls (void) 1822 { 1823 cfun->calls_alloca = false; 1824 cfun->calls_setjmp = false; 1825 } 1826 1827 /* Remove PHI nodes associated with basic block BB and all edges out of BB. */ 1828 1829 static void 1830 remove_phi_nodes_and_edges_for_unreachable_block (basic_block bb) 1831 { 1832 /* Since this block is no longer reachable, we can just delete all 1833 of its PHI nodes. */ 1834 remove_phi_nodes (bb); 1835 1836 /* Remove edges to BB's successors. */ 1837 while (EDGE_COUNT (bb->succs) > 0) 1838 remove_edge (EDGE_SUCC (bb, 0)); 1839 } 1840 1841 1842 /* Remove statements of basic block BB. */ 1843 1844 static void 1845 remove_bb (basic_block bb) 1846 { 1847 gimple_stmt_iterator i; 1848 1849 if (dump_file) 1850 { 1851 fprintf (dump_file, "Removing basic block %d\n", bb->index); 1852 if (dump_flags & TDF_DETAILS) 1853 { 1854 dump_bb (bb, dump_file, 0); 1855 fprintf (dump_file, "\n"); 1856 } 1857 } 1858 1859 if (current_loops) 1860 { 1861 struct loop *loop = bb->loop_father; 1862 1863 /* If a loop gets removed, clean up the information associated 1864 with it. */ 1865 if (loop->latch == bb 1866 || loop->header == bb) 1867 free_numbers_of_iterations_estimates_loop (loop); 1868 } 1869 1870 /* Remove all the instructions in the block. */ 1871 if (bb_seq (bb) != NULL) 1872 { 1873 /* Walk backwards so as to get a chance to substitute all 1874 released DEFs into debug stmts. See 1875 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more 1876 details. */ 1877 for (i = gsi_last_bb (bb); !gsi_end_p (i);) 1878 { 1879 gimple stmt = gsi_stmt (i); 1880 if (gimple_code (stmt) == GIMPLE_LABEL 1881 && (FORCED_LABEL (gimple_label_label (stmt)) 1882 || DECL_NONLOCAL (gimple_label_label (stmt)))) 1883 { 1884 basic_block new_bb; 1885 gimple_stmt_iterator new_gsi; 1886 1887 /* A non-reachable non-local label may still be referenced. 1888 But it no longer needs to carry the extra semantics of 1889 non-locality. */ 1890 if (DECL_NONLOCAL (gimple_label_label (stmt))) 1891 { 1892 DECL_NONLOCAL (gimple_label_label (stmt)) = 0; 1893 FORCED_LABEL (gimple_label_label (stmt)) = 1; 1894 } 1895 1896 new_bb = bb->prev_bb; 1897 new_gsi = gsi_start_bb (new_bb); 1898 gsi_remove (&i, false); 1899 gsi_insert_before (&new_gsi, stmt, GSI_NEW_STMT); 1900 } 1901 else 1902 { 1903 /* Release SSA definitions if we are in SSA. Note that we 1904 may be called when not in SSA. For example, 1905 final_cleanup calls this function via 1906 cleanup_tree_cfg. */ 1907 if (gimple_in_ssa_p (cfun)) 1908 release_defs (stmt); 1909 1910 gsi_remove (&i, true); 1911 } 1912 1913 if (gsi_end_p (i)) 1914 i = gsi_last_bb (bb); 1915 else 1916 gsi_prev (&i); 1917 } 1918 } 1919 1920 remove_phi_nodes_and_edges_for_unreachable_block (bb); 1921 bb->il.gimple = NULL; 1922 } 1923 1924 1925 /* Given a basic block BB ending with COND_EXPR or SWITCH_EXPR, and a 1926 predicate VAL, return the edge that will be taken out of the block. 1927 If VAL does not match a unique edge, NULL is returned. */ 1928 1929 edge 1930 find_taken_edge (basic_block bb, tree val) 1931 { 1932 gimple stmt; 1933 1934 stmt = last_stmt (bb); 1935 1936 gcc_assert (stmt); 1937 gcc_assert (is_ctrl_stmt (stmt)); 1938 1939 if (val == NULL) 1940 return NULL; 1941 1942 if (!is_gimple_min_invariant (val)) 1943 return NULL; 1944 1945 if (gimple_code (stmt) == GIMPLE_COND) 1946 return find_taken_edge_cond_expr (bb, val); 1947 1948 if (gimple_code (stmt) == GIMPLE_SWITCH) 1949 return find_taken_edge_switch_expr (bb, val); 1950 1951 if (computed_goto_p (stmt)) 1952 { 1953 /* Only optimize if the argument is a label, if the argument is 1954 not a label then we can not construct a proper CFG. 1955 1956 It may be the case that we only need to allow the LABEL_REF to 1957 appear inside an ADDR_EXPR, but we also allow the LABEL_REF to 1958 appear inside a LABEL_EXPR just to be safe. */ 1959 if ((TREE_CODE (val) == ADDR_EXPR || TREE_CODE (val) == LABEL_EXPR) 1960 && TREE_CODE (TREE_OPERAND (val, 0)) == LABEL_DECL) 1961 return find_taken_edge_computed_goto (bb, TREE_OPERAND (val, 0)); 1962 return NULL; 1963 } 1964 1965 gcc_unreachable (); 1966 } 1967 1968 /* Given a constant value VAL and the entry block BB to a GOTO_EXPR 1969 statement, determine which of the outgoing edges will be taken out of the 1970 block. Return NULL if either edge may be taken. */ 1971 1972 static edge 1973 find_taken_edge_computed_goto (basic_block bb, tree val) 1974 { 1975 basic_block dest; 1976 edge e = NULL; 1977 1978 dest = label_to_block (val); 1979 if (dest) 1980 { 1981 e = find_edge (bb, dest); 1982 gcc_assert (e != NULL); 1983 } 1984 1985 return e; 1986 } 1987 1988 /* Given a constant value VAL and the entry block BB to a COND_EXPR 1989 statement, determine which of the two edges will be taken out of the 1990 block. Return NULL if either edge may be taken. */ 1991 1992 static edge 1993 find_taken_edge_cond_expr (basic_block bb, tree val) 1994 { 1995 edge true_edge, false_edge; 1996 1997 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 1998 1999 gcc_assert (TREE_CODE (val) == INTEGER_CST); 2000 return (integer_zerop (val) ? false_edge : true_edge); 2001 } 2002 2003 /* Given an INTEGER_CST VAL and the entry block BB to a SWITCH_EXPR 2004 statement, determine which edge will be taken out of the block. Return 2005 NULL if any edge may be taken. */ 2006 2007 static edge 2008 find_taken_edge_switch_expr (basic_block bb, tree val) 2009 { 2010 basic_block dest_bb; 2011 edge e; 2012 gimple switch_stmt; 2013 tree taken_case; 2014 2015 switch_stmt = last_stmt (bb); 2016 taken_case = find_case_label_for_value (switch_stmt, val); 2017 dest_bb = label_to_block (CASE_LABEL (taken_case)); 2018 2019 e = find_edge (bb, dest_bb); 2020 gcc_assert (e); 2021 return e; 2022 } 2023 2024 2025 /* Return the CASE_LABEL_EXPR that SWITCH_STMT will take for VAL. 2026 We can make optimal use here of the fact that the case labels are 2027 sorted: We can do a binary search for a case matching VAL. */ 2028 2029 static tree 2030 find_case_label_for_value (gimple switch_stmt, tree val) 2031 { 2032 size_t low, high, n = gimple_switch_num_labels (switch_stmt); 2033 tree default_case = gimple_switch_default_label (switch_stmt); 2034 2035 for (low = 0, high = n; high - low > 1; ) 2036 { 2037 size_t i = (high + low) / 2; 2038 tree t = gimple_switch_label (switch_stmt, i); 2039 int cmp; 2040 2041 /* Cache the result of comparing CASE_LOW and val. */ 2042 cmp = tree_int_cst_compare (CASE_LOW (t), val); 2043 2044 if (cmp > 0) 2045 high = i; 2046 else 2047 low = i; 2048 2049 if (CASE_HIGH (t) == NULL) 2050 { 2051 /* A singe-valued case label. */ 2052 if (cmp == 0) 2053 return t; 2054 } 2055 else 2056 { 2057 /* A case range. We can only handle integer ranges. */ 2058 if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0) 2059 return t; 2060 } 2061 } 2062 2063 return default_case; 2064 } 2065 2066 2067 /* Dump a basic block on stderr. */ 2068 2069 void 2070 gimple_debug_bb (basic_block bb) 2071 { 2072 gimple_dump_bb (bb, stderr, 0, TDF_VOPS|TDF_MEMSYMS); 2073 } 2074 2075 2076 /* Dump basic block with index N on stderr. */ 2077 2078 basic_block 2079 gimple_debug_bb_n (int n) 2080 { 2081 gimple_debug_bb (BASIC_BLOCK (n)); 2082 return BASIC_BLOCK (n); 2083 } 2084 2085 2086 /* Dump the CFG on stderr. 2087 2088 FLAGS are the same used by the tree dumping functions 2089 (see TDF_* in tree-pass.h). */ 2090 2091 void 2092 gimple_debug_cfg (int flags) 2093 { 2094 gimple_dump_cfg (stderr, flags); 2095 } 2096 2097 2098 /* Dump the program showing basic block boundaries on the given FILE. 2099 2100 FLAGS are the same used by the tree dumping functions (see TDF_* in 2101 tree.h). */ 2102 2103 void 2104 gimple_dump_cfg (FILE *file, int flags) 2105 { 2106 if (flags & TDF_DETAILS) 2107 { 2108 dump_function_header (file, current_function_decl, flags); 2109 fprintf (file, ";; \n%d basic blocks, %d edges, last basic block %d.\n\n", 2110 n_basic_blocks, n_edges, last_basic_block); 2111 2112 brief_dump_cfg (file); 2113 fprintf (file, "\n"); 2114 } 2115 2116 if (flags & TDF_STATS) 2117 dump_cfg_stats (file); 2118 2119 dump_function_to_file (current_function_decl, file, flags | TDF_BLOCKS); 2120 } 2121 2122 2123 /* Dump CFG statistics on FILE. */ 2124 2125 void 2126 dump_cfg_stats (FILE *file) 2127 { 2128 static long max_num_merged_labels = 0; 2129 unsigned long size, total = 0; 2130 long num_edges; 2131 basic_block bb; 2132 const char * const fmt_str = "%-30s%-13s%12s\n"; 2133 const char * const fmt_str_1 = "%-30s%13d%11lu%c\n"; 2134 const char * const fmt_str_2 = "%-30s%13ld%11lu%c\n"; 2135 const char * const fmt_str_3 = "%-43s%11lu%c\n"; 2136 const char *funcname 2137 = lang_hooks.decl_printable_name (current_function_decl, 2); 2138 2139 2140 fprintf (file, "\nCFG Statistics for %s\n\n", funcname); 2141 2142 fprintf (file, "---------------------------------------------------------\n"); 2143 fprintf (file, fmt_str, "", " Number of ", "Memory"); 2144 fprintf (file, fmt_str, "", " instances ", "used "); 2145 fprintf (file, "---------------------------------------------------------\n"); 2146 2147 size = n_basic_blocks * sizeof (struct basic_block_def); 2148 total += size; 2149 fprintf (file, fmt_str_1, "Basic blocks", n_basic_blocks, 2150 SCALE (size), LABEL (size)); 2151 2152 num_edges = 0; 2153 FOR_EACH_BB (bb) 2154 num_edges += EDGE_COUNT (bb->succs); 2155 size = num_edges * sizeof (struct edge_def); 2156 total += size; 2157 fprintf (file, fmt_str_2, "Edges", num_edges, SCALE (size), LABEL (size)); 2158 2159 fprintf (file, "---------------------------------------------------------\n"); 2160 fprintf (file, fmt_str_3, "Total memory used by CFG data", SCALE (total), 2161 LABEL (total)); 2162 fprintf (file, "---------------------------------------------------------\n"); 2163 fprintf (file, "\n"); 2164 2165 if (cfg_stats.num_merged_labels > max_num_merged_labels) 2166 max_num_merged_labels = cfg_stats.num_merged_labels; 2167 2168 fprintf (file, "Coalesced label blocks: %ld (Max so far: %ld)\n", 2169 cfg_stats.num_merged_labels, max_num_merged_labels); 2170 2171 fprintf (file, "\n"); 2172 } 2173 2174 2175 /* Dump CFG statistics on stderr. Keep extern so that it's always 2176 linked in the final executable. */ 2177 2178 DEBUG_FUNCTION void 2179 debug_cfg_stats (void) 2180 { 2181 dump_cfg_stats (stderr); 2182 } 2183 2184 2185 /* Dump the flowgraph to a .vcg FILE. */ 2186 2187 static void 2188 gimple_cfg2vcg (FILE *file) 2189 { 2190 edge e; 2191 edge_iterator ei; 2192 basic_block bb; 2193 const char *funcname 2194 = lang_hooks.decl_printable_name (current_function_decl, 2); 2195 2196 /* Write the file header. */ 2197 fprintf (file, "graph: { title: \"%s\"\n", funcname); 2198 fprintf (file, "node: { title: \"ENTRY\" label: \"ENTRY\" }\n"); 2199 fprintf (file, "node: { title: \"EXIT\" label: \"EXIT\" }\n"); 2200 2201 /* Write blocks and edges. */ 2202 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 2203 { 2204 fprintf (file, "edge: { sourcename: \"ENTRY\" targetname: \"%d\"", 2205 e->dest->index); 2206 2207 if (e->flags & EDGE_FAKE) 2208 fprintf (file, " linestyle: dotted priority: 10"); 2209 else 2210 fprintf (file, " linestyle: solid priority: 100"); 2211 2212 fprintf (file, " }\n"); 2213 } 2214 fputc ('\n', file); 2215 2216 FOR_EACH_BB (bb) 2217 { 2218 enum gimple_code head_code, end_code; 2219 const char *head_name, *end_name; 2220 int head_line = 0; 2221 int end_line = 0; 2222 gimple first = first_stmt (bb); 2223 gimple last = last_stmt (bb); 2224 2225 if (first) 2226 { 2227 head_code = gimple_code (first); 2228 head_name = gimple_code_name[head_code]; 2229 head_line = get_lineno (first); 2230 } 2231 else 2232 head_name = "no-statement"; 2233 2234 if (last) 2235 { 2236 end_code = gimple_code (last); 2237 end_name = gimple_code_name[end_code]; 2238 end_line = get_lineno (last); 2239 } 2240 else 2241 end_name = "no-statement"; 2242 2243 fprintf (file, "node: { title: \"%d\" label: \"#%d\\n%s (%d)\\n%s (%d)\"}\n", 2244 bb->index, bb->index, head_name, head_line, end_name, 2245 end_line); 2246 2247 FOR_EACH_EDGE (e, ei, bb->succs) 2248 { 2249 if (e->dest == EXIT_BLOCK_PTR) 2250 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"EXIT\"", bb->index); 2251 else 2252 fprintf (file, "edge: { sourcename: \"%d\" targetname: \"%d\"", bb->index, e->dest->index); 2253 2254 if (e->flags & EDGE_FAKE) 2255 fprintf (file, " priority: 10 linestyle: dotted"); 2256 else 2257 fprintf (file, " priority: 100 linestyle: solid"); 2258 2259 fprintf (file, " }\n"); 2260 } 2261 2262 if (bb->next_bb != EXIT_BLOCK_PTR) 2263 fputc ('\n', file); 2264 } 2265 2266 fputs ("}\n\n", file); 2267 } 2268 2269 2270 2271 /*--------------------------------------------------------------------------- 2272 Miscellaneous helpers 2273 ---------------------------------------------------------------------------*/ 2274 2275 /* Return true if T, a GIMPLE_CALL, can make an abnormal transfer of control 2276 flow. Transfers of control flow associated with EH are excluded. */ 2277 2278 static bool 2279 call_can_make_abnormal_goto (gimple t) 2280 { 2281 /* If the function has no non-local labels, then a call cannot make an 2282 abnormal transfer of control. */ 2283 if (!cfun->has_nonlocal_label) 2284 return false; 2285 2286 /* Likewise if the call has no side effects. */ 2287 if (!gimple_has_side_effects (t)) 2288 return false; 2289 2290 /* Likewise if the called function is leaf. */ 2291 if (gimple_call_flags (t) & ECF_LEAF) 2292 return false; 2293 2294 return true; 2295 } 2296 2297 2298 /* Return true if T can make an abnormal transfer of control flow. 2299 Transfers of control flow associated with EH are excluded. */ 2300 2301 bool 2302 stmt_can_make_abnormal_goto (gimple t) 2303 { 2304 if (computed_goto_p (t)) 2305 return true; 2306 if (is_gimple_call (t)) 2307 return call_can_make_abnormal_goto (t); 2308 return false; 2309 } 2310 2311 2312 /* Return true if T represents a stmt that always transfers control. */ 2313 2314 bool 2315 is_ctrl_stmt (gimple t) 2316 { 2317 switch (gimple_code (t)) 2318 { 2319 case GIMPLE_COND: 2320 case GIMPLE_SWITCH: 2321 case GIMPLE_GOTO: 2322 case GIMPLE_RETURN: 2323 case GIMPLE_RESX: 2324 return true; 2325 default: 2326 return false; 2327 } 2328 } 2329 2330 2331 /* Return true if T is a statement that may alter the flow of control 2332 (e.g., a call to a non-returning function). */ 2333 2334 bool 2335 is_ctrl_altering_stmt (gimple t) 2336 { 2337 gcc_assert (t); 2338 2339 switch (gimple_code (t)) 2340 { 2341 case GIMPLE_CALL: 2342 { 2343 int flags = gimple_call_flags (t); 2344 2345 /* A call alters control flow if it can make an abnormal goto. */ 2346 if (call_can_make_abnormal_goto (t)) 2347 return true; 2348 2349 /* A call also alters control flow if it does not return. */ 2350 if (flags & ECF_NORETURN) 2351 return true; 2352 2353 /* TM ending statements have backedges out of the transaction. 2354 Return true so we split the basic block containing them. 2355 Note that the TM_BUILTIN test is merely an optimization. */ 2356 if ((flags & ECF_TM_BUILTIN) 2357 && is_tm_ending_fndecl (gimple_call_fndecl (t))) 2358 return true; 2359 2360 /* BUILT_IN_RETURN call is same as return statement. */ 2361 if (gimple_call_builtin_p (t, BUILT_IN_RETURN)) 2362 return true; 2363 } 2364 break; 2365 2366 case GIMPLE_EH_DISPATCH: 2367 /* EH_DISPATCH branches to the individual catch handlers at 2368 this level of a try or allowed-exceptions region. It can 2369 fallthru to the next statement as well. */ 2370 return true; 2371 2372 case GIMPLE_ASM: 2373 if (gimple_asm_nlabels (t) > 0) 2374 return true; 2375 break; 2376 2377 CASE_GIMPLE_OMP: 2378 /* OpenMP directives alter control flow. */ 2379 return true; 2380 2381 case GIMPLE_TRANSACTION: 2382 /* A transaction start alters control flow. */ 2383 return true; 2384 2385 default: 2386 break; 2387 } 2388 2389 /* If a statement can throw, it alters control flow. */ 2390 return stmt_can_throw_internal (t); 2391 } 2392 2393 2394 /* Return true if T is a simple local goto. */ 2395 2396 bool 2397 simple_goto_p (gimple t) 2398 { 2399 return (gimple_code (t) == GIMPLE_GOTO 2400 && TREE_CODE (gimple_goto_dest (t)) == LABEL_DECL); 2401 } 2402 2403 2404 /* Return true if STMT should start a new basic block. PREV_STMT is 2405 the statement preceding STMT. It is used when STMT is a label or a 2406 case label. Labels should only start a new basic block if their 2407 previous statement wasn't a label. Otherwise, sequence of labels 2408 would generate unnecessary basic blocks that only contain a single 2409 label. */ 2410 2411 static inline bool 2412 stmt_starts_bb_p (gimple stmt, gimple prev_stmt) 2413 { 2414 if (stmt == NULL) 2415 return false; 2416 2417 /* Labels start a new basic block only if the preceding statement 2418 wasn't a label of the same type. This prevents the creation of 2419 consecutive blocks that have nothing but a single label. */ 2420 if (gimple_code (stmt) == GIMPLE_LABEL) 2421 { 2422 /* Nonlocal and computed GOTO targets always start a new block. */ 2423 if (DECL_NONLOCAL (gimple_label_label (stmt)) 2424 || FORCED_LABEL (gimple_label_label (stmt))) 2425 return true; 2426 2427 if (prev_stmt && gimple_code (prev_stmt) == GIMPLE_LABEL) 2428 { 2429 if (DECL_NONLOCAL (gimple_label_label (prev_stmt))) 2430 return true; 2431 2432 cfg_stats.num_merged_labels++; 2433 return false; 2434 } 2435 else 2436 return true; 2437 } 2438 2439 return false; 2440 } 2441 2442 2443 /* Return true if T should end a basic block. */ 2444 2445 bool 2446 stmt_ends_bb_p (gimple t) 2447 { 2448 return is_ctrl_stmt (t) || is_ctrl_altering_stmt (t); 2449 } 2450 2451 /* Remove block annotations and other data structures. */ 2452 2453 void 2454 delete_tree_cfg_annotations (void) 2455 { 2456 label_to_block_map = NULL; 2457 } 2458 2459 2460 /* Return the first statement in basic block BB. */ 2461 2462 gimple 2463 first_stmt (basic_block bb) 2464 { 2465 gimple_stmt_iterator i = gsi_start_bb (bb); 2466 gimple stmt = NULL; 2467 2468 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i)))) 2469 { 2470 gsi_next (&i); 2471 stmt = NULL; 2472 } 2473 return stmt; 2474 } 2475 2476 /* Return the first non-label statement in basic block BB. */ 2477 2478 static gimple 2479 first_non_label_stmt (basic_block bb) 2480 { 2481 gimple_stmt_iterator i = gsi_start_bb (bb); 2482 while (!gsi_end_p (i) && gimple_code (gsi_stmt (i)) == GIMPLE_LABEL) 2483 gsi_next (&i); 2484 return !gsi_end_p (i) ? gsi_stmt (i) : NULL; 2485 } 2486 2487 /* Return the last statement in basic block BB. */ 2488 2489 gimple 2490 last_stmt (basic_block bb) 2491 { 2492 gimple_stmt_iterator i = gsi_last_bb (bb); 2493 gimple stmt = NULL; 2494 2495 while (!gsi_end_p (i) && is_gimple_debug ((stmt = gsi_stmt (i)))) 2496 { 2497 gsi_prev (&i); 2498 stmt = NULL; 2499 } 2500 return stmt; 2501 } 2502 2503 /* Return the last statement of an otherwise empty block. Return NULL 2504 if the block is totally empty, or if it contains more than one 2505 statement. */ 2506 2507 gimple 2508 last_and_only_stmt (basic_block bb) 2509 { 2510 gimple_stmt_iterator i = gsi_last_nondebug_bb (bb); 2511 gimple last, prev; 2512 2513 if (gsi_end_p (i)) 2514 return NULL; 2515 2516 last = gsi_stmt (i); 2517 gsi_prev_nondebug (&i); 2518 if (gsi_end_p (i)) 2519 return last; 2520 2521 /* Empty statements should no longer appear in the instruction stream. 2522 Everything that might have appeared before should be deleted by 2523 remove_useless_stmts, and the optimizers should just gsi_remove 2524 instead of smashing with build_empty_stmt. 2525 2526 Thus the only thing that should appear here in a block containing 2527 one executable statement is a label. */ 2528 prev = gsi_stmt (i); 2529 if (gimple_code (prev) == GIMPLE_LABEL) 2530 return last; 2531 else 2532 return NULL; 2533 } 2534 2535 /* Reinstall those PHI arguments queued in OLD_EDGE to NEW_EDGE. */ 2536 2537 static void 2538 reinstall_phi_args (edge new_edge, edge old_edge) 2539 { 2540 edge_var_map_vector v; 2541 edge_var_map *vm; 2542 int i; 2543 gimple_stmt_iterator phis; 2544 2545 v = redirect_edge_var_map_vector (old_edge); 2546 if (!v) 2547 return; 2548 2549 for (i = 0, phis = gsi_start_phis (new_edge->dest); 2550 VEC_iterate (edge_var_map, v, i, vm) && !gsi_end_p (phis); 2551 i++, gsi_next (&phis)) 2552 { 2553 gimple phi = gsi_stmt (phis); 2554 tree result = redirect_edge_var_map_result (vm); 2555 tree arg = redirect_edge_var_map_def (vm); 2556 2557 gcc_assert (result == gimple_phi_result (phi)); 2558 2559 add_phi_arg (phi, arg, new_edge, redirect_edge_var_map_location (vm)); 2560 } 2561 2562 redirect_edge_var_map_clear (old_edge); 2563 } 2564 2565 /* Returns the basic block after which the new basic block created 2566 by splitting edge EDGE_IN should be placed. Tries to keep the new block 2567 near its "logical" location. This is of most help to humans looking 2568 at debugging dumps. */ 2569 2570 static basic_block 2571 split_edge_bb_loc (edge edge_in) 2572 { 2573 basic_block dest = edge_in->dest; 2574 basic_block dest_prev = dest->prev_bb; 2575 2576 if (dest_prev) 2577 { 2578 edge e = find_edge (dest_prev, dest); 2579 if (e && !(e->flags & EDGE_COMPLEX)) 2580 return edge_in->src; 2581 } 2582 return dest_prev; 2583 } 2584 2585 /* Split a (typically critical) edge EDGE_IN. Return the new block. 2586 Abort on abnormal edges. */ 2587 2588 static basic_block 2589 gimple_split_edge (edge edge_in) 2590 { 2591 basic_block new_bb, after_bb, dest; 2592 edge new_edge, e; 2593 2594 /* Abnormal edges cannot be split. */ 2595 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL)); 2596 2597 dest = edge_in->dest; 2598 2599 after_bb = split_edge_bb_loc (edge_in); 2600 2601 new_bb = create_empty_bb (after_bb); 2602 new_bb->frequency = EDGE_FREQUENCY (edge_in); 2603 new_bb->count = edge_in->count; 2604 new_edge = make_edge (new_bb, dest, EDGE_FALLTHRU); 2605 new_edge->probability = REG_BR_PROB_BASE; 2606 new_edge->count = edge_in->count; 2607 2608 e = redirect_edge_and_branch (edge_in, new_bb); 2609 gcc_assert (e == edge_in); 2610 reinstall_phi_args (new_edge, e); 2611 2612 return new_bb; 2613 } 2614 2615 2616 /* Verify properties of the address expression T with base object BASE. */ 2617 2618 static tree 2619 verify_address (tree t, tree base) 2620 { 2621 bool old_constant; 2622 bool old_side_effects; 2623 bool new_constant; 2624 bool new_side_effects; 2625 2626 old_constant = TREE_CONSTANT (t); 2627 old_side_effects = TREE_SIDE_EFFECTS (t); 2628 2629 recompute_tree_invariant_for_addr_expr (t); 2630 new_side_effects = TREE_SIDE_EFFECTS (t); 2631 new_constant = TREE_CONSTANT (t); 2632 2633 if (old_constant != new_constant) 2634 { 2635 error ("constant not recomputed when ADDR_EXPR changed"); 2636 return t; 2637 } 2638 if (old_side_effects != new_side_effects) 2639 { 2640 error ("side effects not recomputed when ADDR_EXPR changed"); 2641 return t; 2642 } 2643 2644 if (!(TREE_CODE (base) == VAR_DECL 2645 || TREE_CODE (base) == PARM_DECL 2646 || TREE_CODE (base) == RESULT_DECL)) 2647 return NULL_TREE; 2648 2649 if (DECL_GIMPLE_REG_P (base)) 2650 { 2651 error ("DECL_GIMPLE_REG_P set on a variable with address taken"); 2652 return base; 2653 } 2654 2655 return NULL_TREE; 2656 } 2657 2658 /* Callback for walk_tree, check that all elements with address taken are 2659 properly noticed as such. The DATA is an int* that is 1 if TP was seen 2660 inside a PHI node. */ 2661 2662 static tree 2663 verify_expr (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) 2664 { 2665 tree t = *tp, x; 2666 2667 if (TYPE_P (t)) 2668 *walk_subtrees = 0; 2669 2670 /* Check operand N for being valid GIMPLE and give error MSG if not. */ 2671 #define CHECK_OP(N, MSG) \ 2672 do { if (!is_gimple_val (TREE_OPERAND (t, N))) \ 2673 { error (MSG); return TREE_OPERAND (t, N); }} while (0) 2674 2675 switch (TREE_CODE (t)) 2676 { 2677 case SSA_NAME: 2678 if (SSA_NAME_IN_FREE_LIST (t)) 2679 { 2680 error ("SSA name in freelist but still referenced"); 2681 return *tp; 2682 } 2683 break; 2684 2685 case INDIRECT_REF: 2686 error ("INDIRECT_REF in gimple IL"); 2687 return t; 2688 2689 case MEM_REF: 2690 x = TREE_OPERAND (t, 0); 2691 if (!POINTER_TYPE_P (TREE_TYPE (x)) 2692 || !is_gimple_mem_ref_addr (x)) 2693 { 2694 error ("invalid first operand of MEM_REF"); 2695 return x; 2696 } 2697 if (TREE_CODE (TREE_OPERAND (t, 1)) != INTEGER_CST 2698 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 1)))) 2699 { 2700 error ("invalid offset operand of MEM_REF"); 2701 return TREE_OPERAND (t, 1); 2702 } 2703 if (TREE_CODE (x) == ADDR_EXPR 2704 && (x = verify_address (x, TREE_OPERAND (x, 0)))) 2705 return x; 2706 *walk_subtrees = 0; 2707 break; 2708 2709 case ASSERT_EXPR: 2710 x = fold (ASSERT_EXPR_COND (t)); 2711 if (x == boolean_false_node) 2712 { 2713 error ("ASSERT_EXPR with an always-false condition"); 2714 return *tp; 2715 } 2716 break; 2717 2718 case MODIFY_EXPR: 2719 error ("MODIFY_EXPR not expected while having tuples"); 2720 return *tp; 2721 2722 case ADDR_EXPR: 2723 { 2724 tree tem; 2725 2726 gcc_assert (is_gimple_address (t)); 2727 2728 /* Skip any references (they will be checked when we recurse down the 2729 tree) and ensure that any variable used as a prefix is marked 2730 addressable. */ 2731 for (x = TREE_OPERAND (t, 0); 2732 handled_component_p (x); 2733 x = TREE_OPERAND (x, 0)) 2734 ; 2735 2736 if ((tem = verify_address (t, x))) 2737 return tem; 2738 2739 if (!(TREE_CODE (x) == VAR_DECL 2740 || TREE_CODE (x) == PARM_DECL 2741 || TREE_CODE (x) == RESULT_DECL)) 2742 return NULL; 2743 2744 if (!TREE_ADDRESSABLE (x)) 2745 { 2746 error ("address taken, but ADDRESSABLE bit not set"); 2747 return x; 2748 } 2749 2750 break; 2751 } 2752 2753 case COND_EXPR: 2754 x = COND_EXPR_COND (t); 2755 if (!INTEGRAL_TYPE_P (TREE_TYPE (x))) 2756 { 2757 error ("non-integral used in condition"); 2758 return x; 2759 } 2760 if (!is_gimple_condexpr (x)) 2761 { 2762 error ("invalid conditional operand"); 2763 return x; 2764 } 2765 break; 2766 2767 case NON_LVALUE_EXPR: 2768 case TRUTH_NOT_EXPR: 2769 gcc_unreachable (); 2770 2771 CASE_CONVERT: 2772 case FIX_TRUNC_EXPR: 2773 case FLOAT_EXPR: 2774 case NEGATE_EXPR: 2775 case ABS_EXPR: 2776 case BIT_NOT_EXPR: 2777 CHECK_OP (0, "invalid operand to unary operator"); 2778 break; 2779 2780 case REALPART_EXPR: 2781 case IMAGPART_EXPR: 2782 case COMPONENT_REF: 2783 case ARRAY_REF: 2784 case ARRAY_RANGE_REF: 2785 case BIT_FIELD_REF: 2786 case VIEW_CONVERT_EXPR: 2787 /* We have a nest of references. Verify that each of the operands 2788 that determine where to reference is either a constant or a variable, 2789 verify that the base is valid, and then show we've already checked 2790 the subtrees. */ 2791 while (handled_component_p (t)) 2792 { 2793 if (TREE_CODE (t) == COMPONENT_REF && TREE_OPERAND (t, 2)) 2794 CHECK_OP (2, "invalid COMPONENT_REF offset operator"); 2795 else if (TREE_CODE (t) == ARRAY_REF 2796 || TREE_CODE (t) == ARRAY_RANGE_REF) 2797 { 2798 CHECK_OP (1, "invalid array index"); 2799 if (TREE_OPERAND (t, 2)) 2800 CHECK_OP (2, "invalid array lower bound"); 2801 if (TREE_OPERAND (t, 3)) 2802 CHECK_OP (3, "invalid array stride"); 2803 } 2804 else if (TREE_CODE (t) == BIT_FIELD_REF) 2805 { 2806 if (!host_integerp (TREE_OPERAND (t, 1), 1) 2807 || !host_integerp (TREE_OPERAND (t, 2), 1)) 2808 { 2809 error ("invalid position or size operand to BIT_FIELD_REF"); 2810 return t; 2811 } 2812 else if (INTEGRAL_TYPE_P (TREE_TYPE (t)) 2813 && (TYPE_PRECISION (TREE_TYPE (t)) 2814 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1)))) 2815 { 2816 error ("integral result type precision does not match " 2817 "field size of BIT_FIELD_REF"); 2818 return t; 2819 } 2820 if (!INTEGRAL_TYPE_P (TREE_TYPE (t)) 2821 && (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (t))) 2822 != TREE_INT_CST_LOW (TREE_OPERAND (t, 1)))) 2823 { 2824 error ("mode precision of non-integral result does not " 2825 "match field size of BIT_FIELD_REF"); 2826 return t; 2827 } 2828 } 2829 2830 t = TREE_OPERAND (t, 0); 2831 } 2832 2833 if (!is_gimple_min_invariant (t) && !is_gimple_lvalue (t)) 2834 { 2835 error ("invalid reference prefix"); 2836 return t; 2837 } 2838 *walk_subtrees = 0; 2839 break; 2840 case PLUS_EXPR: 2841 case MINUS_EXPR: 2842 /* PLUS_EXPR and MINUS_EXPR don't work on pointers, they should be done using 2843 POINTER_PLUS_EXPR. */ 2844 if (POINTER_TYPE_P (TREE_TYPE (t))) 2845 { 2846 error ("invalid operand to plus/minus, type is a pointer"); 2847 return t; 2848 } 2849 CHECK_OP (0, "invalid operand to binary operator"); 2850 CHECK_OP (1, "invalid operand to binary operator"); 2851 break; 2852 2853 case POINTER_PLUS_EXPR: 2854 /* Check to make sure the first operand is a pointer or reference type. */ 2855 if (!POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (t, 0)))) 2856 { 2857 error ("invalid operand to pointer plus, first operand is not a pointer"); 2858 return t; 2859 } 2860 /* Check to make sure the second operand is a ptrofftype. */ 2861 if (!ptrofftype_p (TREE_TYPE (TREE_OPERAND (t, 1)))) 2862 { 2863 error ("invalid operand to pointer plus, second operand is not an " 2864 "integer type of appropriate width"); 2865 return t; 2866 } 2867 /* FALLTHROUGH */ 2868 case LT_EXPR: 2869 case LE_EXPR: 2870 case GT_EXPR: 2871 case GE_EXPR: 2872 case EQ_EXPR: 2873 case NE_EXPR: 2874 case UNORDERED_EXPR: 2875 case ORDERED_EXPR: 2876 case UNLT_EXPR: 2877 case UNLE_EXPR: 2878 case UNGT_EXPR: 2879 case UNGE_EXPR: 2880 case UNEQ_EXPR: 2881 case LTGT_EXPR: 2882 case MULT_EXPR: 2883 case TRUNC_DIV_EXPR: 2884 case CEIL_DIV_EXPR: 2885 case FLOOR_DIV_EXPR: 2886 case ROUND_DIV_EXPR: 2887 case TRUNC_MOD_EXPR: 2888 case CEIL_MOD_EXPR: 2889 case FLOOR_MOD_EXPR: 2890 case ROUND_MOD_EXPR: 2891 case RDIV_EXPR: 2892 case EXACT_DIV_EXPR: 2893 case MIN_EXPR: 2894 case MAX_EXPR: 2895 case LSHIFT_EXPR: 2896 case RSHIFT_EXPR: 2897 case LROTATE_EXPR: 2898 case RROTATE_EXPR: 2899 case BIT_IOR_EXPR: 2900 case BIT_XOR_EXPR: 2901 case BIT_AND_EXPR: 2902 CHECK_OP (0, "invalid operand to binary operator"); 2903 CHECK_OP (1, "invalid operand to binary operator"); 2904 break; 2905 2906 case CONSTRUCTOR: 2907 if (TREE_CONSTANT (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE) 2908 *walk_subtrees = 0; 2909 break; 2910 2911 case CASE_LABEL_EXPR: 2912 if (CASE_CHAIN (t)) 2913 { 2914 error ("invalid CASE_CHAIN"); 2915 return t; 2916 } 2917 break; 2918 2919 default: 2920 break; 2921 } 2922 return NULL; 2923 2924 #undef CHECK_OP 2925 } 2926 2927 2928 /* Verify if EXPR is either a GIMPLE ID or a GIMPLE indirect reference. 2929 Returns true if there is an error, otherwise false. */ 2930 2931 static bool 2932 verify_types_in_gimple_min_lval (tree expr) 2933 { 2934 tree op; 2935 2936 if (is_gimple_id (expr)) 2937 return false; 2938 2939 if (TREE_CODE (expr) != TARGET_MEM_REF 2940 && TREE_CODE (expr) != MEM_REF) 2941 { 2942 error ("invalid expression for min lvalue"); 2943 return true; 2944 } 2945 2946 /* TARGET_MEM_REFs are strange beasts. */ 2947 if (TREE_CODE (expr) == TARGET_MEM_REF) 2948 return false; 2949 2950 op = TREE_OPERAND (expr, 0); 2951 if (!is_gimple_val (op)) 2952 { 2953 error ("invalid operand in indirect reference"); 2954 debug_generic_stmt (op); 2955 return true; 2956 } 2957 /* Memory references now generally can involve a value conversion. */ 2958 2959 return false; 2960 } 2961 2962 /* Verify if EXPR is a valid GIMPLE reference expression. If 2963 REQUIRE_LVALUE is true verifies it is an lvalue. Returns true 2964 if there is an error, otherwise false. */ 2965 2966 static bool 2967 verify_types_in_gimple_reference (tree expr, bool require_lvalue) 2968 { 2969 while (handled_component_p (expr)) 2970 { 2971 tree op = TREE_OPERAND (expr, 0); 2972 2973 if (TREE_CODE (expr) == ARRAY_REF 2974 || TREE_CODE (expr) == ARRAY_RANGE_REF) 2975 { 2976 if (!is_gimple_val (TREE_OPERAND (expr, 1)) 2977 || (TREE_OPERAND (expr, 2) 2978 && !is_gimple_val (TREE_OPERAND (expr, 2))) 2979 || (TREE_OPERAND (expr, 3) 2980 && !is_gimple_val (TREE_OPERAND (expr, 3)))) 2981 { 2982 error ("invalid operands to array reference"); 2983 debug_generic_stmt (expr); 2984 return true; 2985 } 2986 } 2987 2988 /* Verify if the reference array element types are compatible. */ 2989 if (TREE_CODE (expr) == ARRAY_REF 2990 && !useless_type_conversion_p (TREE_TYPE (expr), 2991 TREE_TYPE (TREE_TYPE (op)))) 2992 { 2993 error ("type mismatch in array reference"); 2994 debug_generic_stmt (TREE_TYPE (expr)); 2995 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op))); 2996 return true; 2997 } 2998 if (TREE_CODE (expr) == ARRAY_RANGE_REF 2999 && !useless_type_conversion_p (TREE_TYPE (TREE_TYPE (expr)), 3000 TREE_TYPE (TREE_TYPE (op)))) 3001 { 3002 error ("type mismatch in array range reference"); 3003 debug_generic_stmt (TREE_TYPE (TREE_TYPE (expr))); 3004 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op))); 3005 return true; 3006 } 3007 3008 if ((TREE_CODE (expr) == REALPART_EXPR 3009 || TREE_CODE (expr) == IMAGPART_EXPR) 3010 && !useless_type_conversion_p (TREE_TYPE (expr), 3011 TREE_TYPE (TREE_TYPE (op)))) 3012 { 3013 error ("type mismatch in real/imagpart reference"); 3014 debug_generic_stmt (TREE_TYPE (expr)); 3015 debug_generic_stmt (TREE_TYPE (TREE_TYPE (op))); 3016 return true; 3017 } 3018 3019 if (TREE_CODE (expr) == COMPONENT_REF 3020 && !useless_type_conversion_p (TREE_TYPE (expr), 3021 TREE_TYPE (TREE_OPERAND (expr, 1)))) 3022 { 3023 error ("type mismatch in component reference"); 3024 debug_generic_stmt (TREE_TYPE (expr)); 3025 debug_generic_stmt (TREE_TYPE (TREE_OPERAND (expr, 1))); 3026 return true; 3027 } 3028 3029 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR) 3030 { 3031 /* For VIEW_CONVERT_EXPRs which are allowed here too, we only check 3032 that their operand is not an SSA name or an invariant when 3033 requiring an lvalue (this usually means there is a SRA or IPA-SRA 3034 bug). Otherwise there is nothing to verify, gross mismatches at 3035 most invoke undefined behavior. */ 3036 if (require_lvalue 3037 && (TREE_CODE (op) == SSA_NAME 3038 || is_gimple_min_invariant (op))) 3039 { 3040 error ("conversion of an SSA_NAME on the left hand side"); 3041 debug_generic_stmt (expr); 3042 return true; 3043 } 3044 else if (TREE_CODE (op) == SSA_NAME 3045 && TYPE_SIZE (TREE_TYPE (expr)) != TYPE_SIZE (TREE_TYPE (op))) 3046 { 3047 error ("conversion of register to a different size"); 3048 debug_generic_stmt (expr); 3049 return true; 3050 } 3051 else if (!handled_component_p (op)) 3052 return false; 3053 } 3054 3055 expr = op; 3056 } 3057 3058 if (TREE_CODE (expr) == MEM_REF) 3059 { 3060 if (!is_gimple_mem_ref_addr (TREE_OPERAND (expr, 0))) 3061 { 3062 error ("invalid address operand in MEM_REF"); 3063 debug_generic_stmt (expr); 3064 return true; 3065 } 3066 if (TREE_CODE (TREE_OPERAND (expr, 1)) != INTEGER_CST 3067 || !POINTER_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 1)))) 3068 { 3069 error ("invalid offset operand in MEM_REF"); 3070 debug_generic_stmt (expr); 3071 return true; 3072 } 3073 } 3074 else if (TREE_CODE (expr) == TARGET_MEM_REF) 3075 { 3076 if (!TMR_BASE (expr) 3077 || !is_gimple_mem_ref_addr (TMR_BASE (expr))) 3078 { 3079 error ("invalid address operand in TARGET_MEM_REF"); 3080 return true; 3081 } 3082 if (!TMR_OFFSET (expr) 3083 || TREE_CODE (TMR_OFFSET (expr)) != INTEGER_CST 3084 || !POINTER_TYPE_P (TREE_TYPE (TMR_OFFSET (expr)))) 3085 { 3086 error ("invalid offset operand in TARGET_MEM_REF"); 3087 debug_generic_stmt (expr); 3088 return true; 3089 } 3090 } 3091 3092 return ((require_lvalue || !is_gimple_min_invariant (expr)) 3093 && verify_types_in_gimple_min_lval (expr)); 3094 } 3095 3096 /* Returns true if there is one pointer type in TYPE_POINTER_TO (SRC_OBJ) 3097 list of pointer-to types that is trivially convertible to DEST. */ 3098 3099 static bool 3100 one_pointer_to_useless_type_conversion_p (tree dest, tree src_obj) 3101 { 3102 tree src; 3103 3104 if (!TYPE_POINTER_TO (src_obj)) 3105 return true; 3106 3107 for (src = TYPE_POINTER_TO (src_obj); src; src = TYPE_NEXT_PTR_TO (src)) 3108 if (useless_type_conversion_p (dest, src)) 3109 return true; 3110 3111 return false; 3112 } 3113 3114 /* Return true if TYPE1 is a fixed-point type and if conversions to and 3115 from TYPE2 can be handled by FIXED_CONVERT_EXPR. */ 3116 3117 static bool 3118 valid_fixed_convert_types_p (tree type1, tree type2) 3119 { 3120 return (FIXED_POINT_TYPE_P (type1) 3121 && (INTEGRAL_TYPE_P (type2) 3122 || SCALAR_FLOAT_TYPE_P (type2) 3123 || FIXED_POINT_TYPE_P (type2))); 3124 } 3125 3126 /* Verify the contents of a GIMPLE_CALL STMT. Returns true when there 3127 is a problem, otherwise false. */ 3128 3129 static bool 3130 verify_gimple_call (gimple stmt) 3131 { 3132 tree fn = gimple_call_fn (stmt); 3133 tree fntype, fndecl; 3134 unsigned i; 3135 3136 if (gimple_call_internal_p (stmt)) 3137 { 3138 if (fn) 3139 { 3140 error ("gimple call has two targets"); 3141 debug_generic_stmt (fn); 3142 return true; 3143 } 3144 } 3145 else 3146 { 3147 if (!fn) 3148 { 3149 error ("gimple call has no target"); 3150 return true; 3151 } 3152 } 3153 3154 if (fn && !is_gimple_call_addr (fn)) 3155 { 3156 error ("invalid function in gimple call"); 3157 debug_generic_stmt (fn); 3158 return true; 3159 } 3160 3161 if (fn 3162 && (!POINTER_TYPE_P (TREE_TYPE (fn)) 3163 || (TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != FUNCTION_TYPE 3164 && TREE_CODE (TREE_TYPE (TREE_TYPE (fn))) != METHOD_TYPE))) 3165 { 3166 error ("non-function in gimple call"); 3167 return true; 3168 } 3169 3170 fndecl = gimple_call_fndecl (stmt); 3171 if (fndecl 3172 && TREE_CODE (fndecl) == FUNCTION_DECL 3173 && DECL_LOOPING_CONST_OR_PURE_P (fndecl) 3174 && !DECL_PURE_P (fndecl) 3175 && !TREE_READONLY (fndecl)) 3176 { 3177 error ("invalid pure const state for function"); 3178 return true; 3179 } 3180 3181 if (gimple_call_lhs (stmt) 3182 && (!is_gimple_lvalue (gimple_call_lhs (stmt)) 3183 || verify_types_in_gimple_reference (gimple_call_lhs (stmt), true))) 3184 { 3185 error ("invalid LHS in gimple call"); 3186 return true; 3187 } 3188 3189 if (gimple_call_lhs (stmt) && gimple_call_noreturn_p (stmt)) 3190 { 3191 error ("LHS in noreturn call"); 3192 return true; 3193 } 3194 3195 fntype = gimple_call_fntype (stmt); 3196 if (fntype 3197 && gimple_call_lhs (stmt) 3198 && !useless_type_conversion_p (TREE_TYPE (gimple_call_lhs (stmt)), 3199 TREE_TYPE (fntype)) 3200 /* ??? At least C++ misses conversions at assignments from 3201 void * call results. 3202 ??? Java is completely off. Especially with functions 3203 returning java.lang.Object. 3204 For now simply allow arbitrary pointer type conversions. */ 3205 && !(POINTER_TYPE_P (TREE_TYPE (gimple_call_lhs (stmt))) 3206 && POINTER_TYPE_P (TREE_TYPE (fntype)))) 3207 { 3208 error ("invalid conversion in gimple call"); 3209 debug_generic_stmt (TREE_TYPE (gimple_call_lhs (stmt))); 3210 debug_generic_stmt (TREE_TYPE (fntype)); 3211 return true; 3212 } 3213 3214 if (gimple_call_chain (stmt) 3215 && !is_gimple_val (gimple_call_chain (stmt))) 3216 { 3217 error ("invalid static chain in gimple call"); 3218 debug_generic_stmt (gimple_call_chain (stmt)); 3219 return true; 3220 } 3221 3222 /* If there is a static chain argument, this should not be an indirect 3223 call, and the decl should have DECL_STATIC_CHAIN set. */ 3224 if (gimple_call_chain (stmt)) 3225 { 3226 if (!gimple_call_fndecl (stmt)) 3227 { 3228 error ("static chain in indirect gimple call"); 3229 return true; 3230 } 3231 fn = TREE_OPERAND (fn, 0); 3232 3233 if (!DECL_STATIC_CHAIN (fn)) 3234 { 3235 error ("static chain with function that doesn%'t use one"); 3236 return true; 3237 } 3238 } 3239 3240 /* ??? The C frontend passes unpromoted arguments in case it 3241 didn't see a function declaration before the call. So for now 3242 leave the call arguments mostly unverified. Once we gimplify 3243 unit-at-a-time we have a chance to fix this. */ 3244 3245 for (i = 0; i < gimple_call_num_args (stmt); ++i) 3246 { 3247 tree arg = gimple_call_arg (stmt, i); 3248 if ((is_gimple_reg_type (TREE_TYPE (arg)) 3249 && !is_gimple_val (arg)) 3250 || (!is_gimple_reg_type (TREE_TYPE (arg)) 3251 && !is_gimple_lvalue (arg))) 3252 { 3253 error ("invalid argument to gimple call"); 3254 debug_generic_expr (arg); 3255 return true; 3256 } 3257 } 3258 3259 return false; 3260 } 3261 3262 /* Verifies the gimple comparison with the result type TYPE and 3263 the operands OP0 and OP1. */ 3264 3265 static bool 3266 verify_gimple_comparison (tree type, tree op0, tree op1) 3267 { 3268 tree op0_type = TREE_TYPE (op0); 3269 tree op1_type = TREE_TYPE (op1); 3270 3271 if (!is_gimple_val (op0) || !is_gimple_val (op1)) 3272 { 3273 error ("invalid operands in gimple comparison"); 3274 return true; 3275 } 3276 3277 /* For comparisons we do not have the operations type as the 3278 effective type the comparison is carried out in. Instead 3279 we require that either the first operand is trivially 3280 convertible into the second, or the other way around. 3281 Because we special-case pointers to void we allow 3282 comparisons of pointers with the same mode as well. */ 3283 if (!useless_type_conversion_p (op0_type, op1_type) 3284 && !useless_type_conversion_p (op1_type, op0_type) 3285 && (!POINTER_TYPE_P (op0_type) 3286 || !POINTER_TYPE_P (op1_type) 3287 || TYPE_MODE (op0_type) != TYPE_MODE (op1_type))) 3288 { 3289 error ("mismatching comparison operand types"); 3290 debug_generic_expr (op0_type); 3291 debug_generic_expr (op1_type); 3292 return true; 3293 } 3294 3295 /* The resulting type of a comparison may be an effective boolean type. */ 3296 if (INTEGRAL_TYPE_P (type) 3297 && (TREE_CODE (type) == BOOLEAN_TYPE 3298 || TYPE_PRECISION (type) == 1)) 3299 ; 3300 /* Or an integer vector type with the same size and element count 3301 as the comparison operand types. */ 3302 else if (TREE_CODE (type) == VECTOR_TYPE 3303 && TREE_CODE (TREE_TYPE (type)) == INTEGER_TYPE) 3304 { 3305 if (TREE_CODE (op0_type) != VECTOR_TYPE 3306 || TREE_CODE (op1_type) != VECTOR_TYPE) 3307 { 3308 error ("non-vector operands in vector comparison"); 3309 debug_generic_expr (op0_type); 3310 debug_generic_expr (op1_type); 3311 return true; 3312 } 3313 3314 if (TYPE_VECTOR_SUBPARTS (type) != TYPE_VECTOR_SUBPARTS (op0_type) 3315 || (GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (type))) 3316 != GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0_type))))) 3317 { 3318 error ("invalid vector comparison resulting type"); 3319 debug_generic_expr (type); 3320 return true; 3321 } 3322 } 3323 else 3324 { 3325 error ("bogus comparison result type"); 3326 debug_generic_expr (type); 3327 return true; 3328 } 3329 3330 return false; 3331 } 3332 3333 /* Verify a gimple assignment statement STMT with an unary rhs. 3334 Returns true if anything is wrong. */ 3335 3336 static bool 3337 verify_gimple_assign_unary (gimple stmt) 3338 { 3339 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3340 tree lhs = gimple_assign_lhs (stmt); 3341 tree lhs_type = TREE_TYPE (lhs); 3342 tree rhs1 = gimple_assign_rhs1 (stmt); 3343 tree rhs1_type = TREE_TYPE (rhs1); 3344 3345 if (!is_gimple_reg (lhs)) 3346 { 3347 error ("non-register as LHS of unary operation"); 3348 return true; 3349 } 3350 3351 if (!is_gimple_val (rhs1)) 3352 { 3353 error ("invalid operand in unary operation"); 3354 return true; 3355 } 3356 3357 /* First handle conversions. */ 3358 switch (rhs_code) 3359 { 3360 CASE_CONVERT: 3361 { 3362 /* Allow conversions from pointer type to integral type only if 3363 there is no sign or zero extension involved. 3364 For targets were the precision of ptrofftype doesn't match that 3365 of pointers we need to allow arbitrary conversions to ptrofftype. */ 3366 if ((POINTER_TYPE_P (lhs_type) 3367 && INTEGRAL_TYPE_P (rhs1_type)) 3368 || (POINTER_TYPE_P (rhs1_type) 3369 && INTEGRAL_TYPE_P (lhs_type) 3370 && (TYPE_PRECISION (rhs1_type) >= TYPE_PRECISION (lhs_type) 3371 || ptrofftype_p (sizetype)))) 3372 return false; 3373 3374 /* Allow conversion from integer to offset type and vice versa. */ 3375 if ((TREE_CODE (lhs_type) == OFFSET_TYPE 3376 && TREE_CODE (rhs1_type) == INTEGER_TYPE) 3377 || (TREE_CODE (lhs_type) == INTEGER_TYPE 3378 && TREE_CODE (rhs1_type) == OFFSET_TYPE)) 3379 return false; 3380 3381 /* Otherwise assert we are converting between types of the 3382 same kind. */ 3383 if (INTEGRAL_TYPE_P (lhs_type) != INTEGRAL_TYPE_P (rhs1_type)) 3384 { 3385 error ("invalid types in nop conversion"); 3386 debug_generic_expr (lhs_type); 3387 debug_generic_expr (rhs1_type); 3388 return true; 3389 } 3390 3391 return false; 3392 } 3393 3394 case ADDR_SPACE_CONVERT_EXPR: 3395 { 3396 if (!POINTER_TYPE_P (rhs1_type) || !POINTER_TYPE_P (lhs_type) 3397 || (TYPE_ADDR_SPACE (TREE_TYPE (rhs1_type)) 3398 == TYPE_ADDR_SPACE (TREE_TYPE (lhs_type)))) 3399 { 3400 error ("invalid types in address space conversion"); 3401 debug_generic_expr (lhs_type); 3402 debug_generic_expr (rhs1_type); 3403 return true; 3404 } 3405 3406 return false; 3407 } 3408 3409 case FIXED_CONVERT_EXPR: 3410 { 3411 if (!valid_fixed_convert_types_p (lhs_type, rhs1_type) 3412 && !valid_fixed_convert_types_p (rhs1_type, lhs_type)) 3413 { 3414 error ("invalid types in fixed-point conversion"); 3415 debug_generic_expr (lhs_type); 3416 debug_generic_expr (rhs1_type); 3417 return true; 3418 } 3419 3420 return false; 3421 } 3422 3423 case FLOAT_EXPR: 3424 { 3425 if ((!INTEGRAL_TYPE_P (rhs1_type) || !SCALAR_FLOAT_TYPE_P (lhs_type)) 3426 && (!VECTOR_INTEGER_TYPE_P (rhs1_type) 3427 || !VECTOR_FLOAT_TYPE_P(lhs_type))) 3428 { 3429 error ("invalid types in conversion to floating point"); 3430 debug_generic_expr (lhs_type); 3431 debug_generic_expr (rhs1_type); 3432 return true; 3433 } 3434 3435 return false; 3436 } 3437 3438 case FIX_TRUNC_EXPR: 3439 { 3440 if ((!INTEGRAL_TYPE_P (lhs_type) || !SCALAR_FLOAT_TYPE_P (rhs1_type)) 3441 && (!VECTOR_INTEGER_TYPE_P (lhs_type) 3442 || !VECTOR_FLOAT_TYPE_P(rhs1_type))) 3443 { 3444 error ("invalid types in conversion to integer"); 3445 debug_generic_expr (lhs_type); 3446 debug_generic_expr (rhs1_type); 3447 return true; 3448 } 3449 3450 return false; 3451 } 3452 3453 case VEC_UNPACK_HI_EXPR: 3454 case VEC_UNPACK_LO_EXPR: 3455 case REDUC_MAX_EXPR: 3456 case REDUC_MIN_EXPR: 3457 case REDUC_PLUS_EXPR: 3458 case VEC_UNPACK_FLOAT_HI_EXPR: 3459 case VEC_UNPACK_FLOAT_LO_EXPR: 3460 /* FIXME. */ 3461 return false; 3462 3463 case NEGATE_EXPR: 3464 case ABS_EXPR: 3465 case BIT_NOT_EXPR: 3466 case PAREN_EXPR: 3467 case NON_LVALUE_EXPR: 3468 case CONJ_EXPR: 3469 break; 3470 3471 default: 3472 gcc_unreachable (); 3473 } 3474 3475 /* For the remaining codes assert there is no conversion involved. */ 3476 if (!useless_type_conversion_p (lhs_type, rhs1_type)) 3477 { 3478 error ("non-trivial conversion in unary operation"); 3479 debug_generic_expr (lhs_type); 3480 debug_generic_expr (rhs1_type); 3481 return true; 3482 } 3483 3484 return false; 3485 } 3486 3487 /* Verify a gimple assignment statement STMT with a binary rhs. 3488 Returns true if anything is wrong. */ 3489 3490 static bool 3491 verify_gimple_assign_binary (gimple stmt) 3492 { 3493 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3494 tree lhs = gimple_assign_lhs (stmt); 3495 tree lhs_type = TREE_TYPE (lhs); 3496 tree rhs1 = gimple_assign_rhs1 (stmt); 3497 tree rhs1_type = TREE_TYPE (rhs1); 3498 tree rhs2 = gimple_assign_rhs2 (stmt); 3499 tree rhs2_type = TREE_TYPE (rhs2); 3500 3501 if (!is_gimple_reg (lhs)) 3502 { 3503 error ("non-register as LHS of binary operation"); 3504 return true; 3505 } 3506 3507 if (!is_gimple_val (rhs1) 3508 || !is_gimple_val (rhs2)) 3509 { 3510 error ("invalid operands in binary operation"); 3511 return true; 3512 } 3513 3514 /* First handle operations that involve different types. */ 3515 switch (rhs_code) 3516 { 3517 case COMPLEX_EXPR: 3518 { 3519 if (TREE_CODE (lhs_type) != COMPLEX_TYPE 3520 || !(INTEGRAL_TYPE_P (rhs1_type) 3521 || SCALAR_FLOAT_TYPE_P (rhs1_type)) 3522 || !(INTEGRAL_TYPE_P (rhs2_type) 3523 || SCALAR_FLOAT_TYPE_P (rhs2_type))) 3524 { 3525 error ("type mismatch in complex expression"); 3526 debug_generic_expr (lhs_type); 3527 debug_generic_expr (rhs1_type); 3528 debug_generic_expr (rhs2_type); 3529 return true; 3530 } 3531 3532 return false; 3533 } 3534 3535 case LSHIFT_EXPR: 3536 case RSHIFT_EXPR: 3537 case LROTATE_EXPR: 3538 case RROTATE_EXPR: 3539 { 3540 /* Shifts and rotates are ok on integral types, fixed point 3541 types and integer vector types. */ 3542 if ((!INTEGRAL_TYPE_P (rhs1_type) 3543 && !FIXED_POINT_TYPE_P (rhs1_type) 3544 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE 3545 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type)))) 3546 || (!INTEGRAL_TYPE_P (rhs2_type) 3547 /* Vector shifts of vectors are also ok. */ 3548 && !(TREE_CODE (rhs1_type) == VECTOR_TYPE 3549 && INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type)) 3550 && TREE_CODE (rhs2_type) == VECTOR_TYPE 3551 && INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type)))) 3552 || !useless_type_conversion_p (lhs_type, rhs1_type)) 3553 { 3554 error ("type mismatch in shift expression"); 3555 debug_generic_expr (lhs_type); 3556 debug_generic_expr (rhs1_type); 3557 debug_generic_expr (rhs2_type); 3558 return true; 3559 } 3560 3561 return false; 3562 } 3563 3564 case VEC_LSHIFT_EXPR: 3565 case VEC_RSHIFT_EXPR: 3566 { 3567 if (TREE_CODE (rhs1_type) != VECTOR_TYPE 3568 || !(INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type)) 3569 || POINTER_TYPE_P (TREE_TYPE (rhs1_type)) 3570 || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1_type)) 3571 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs1_type))) 3572 || (!INTEGRAL_TYPE_P (rhs2_type) 3573 && (TREE_CODE (rhs2_type) != VECTOR_TYPE 3574 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs2_type)))) 3575 || !useless_type_conversion_p (lhs_type, rhs1_type)) 3576 { 3577 error ("type mismatch in vector shift expression"); 3578 debug_generic_expr (lhs_type); 3579 debug_generic_expr (rhs1_type); 3580 debug_generic_expr (rhs2_type); 3581 return true; 3582 } 3583 /* For shifting a vector of non-integral components we 3584 only allow shifting by a constant multiple of the element size. */ 3585 if (!INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type)) 3586 && (TREE_CODE (rhs2) != INTEGER_CST 3587 || !div_if_zero_remainder (EXACT_DIV_EXPR, rhs2, 3588 TYPE_SIZE (TREE_TYPE (rhs1_type))))) 3589 { 3590 error ("non-element sized vector shift of floating point vector"); 3591 return true; 3592 } 3593 3594 return false; 3595 } 3596 3597 case WIDEN_LSHIFT_EXPR: 3598 { 3599 if (!INTEGRAL_TYPE_P (lhs_type) 3600 || !INTEGRAL_TYPE_P (rhs1_type) 3601 || TREE_CODE (rhs2) != INTEGER_CST 3602 || (2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type))) 3603 { 3604 error ("type mismatch in widening vector shift expression"); 3605 debug_generic_expr (lhs_type); 3606 debug_generic_expr (rhs1_type); 3607 debug_generic_expr (rhs2_type); 3608 return true; 3609 } 3610 3611 return false; 3612 } 3613 3614 case VEC_WIDEN_LSHIFT_HI_EXPR: 3615 case VEC_WIDEN_LSHIFT_LO_EXPR: 3616 { 3617 if (TREE_CODE (rhs1_type) != VECTOR_TYPE 3618 || TREE_CODE (lhs_type) != VECTOR_TYPE 3619 || !INTEGRAL_TYPE_P (TREE_TYPE (rhs1_type)) 3620 || !INTEGRAL_TYPE_P (TREE_TYPE (lhs_type)) 3621 || TREE_CODE (rhs2) != INTEGER_CST 3622 || (2 * TYPE_PRECISION (TREE_TYPE (rhs1_type)) 3623 > TYPE_PRECISION (TREE_TYPE (lhs_type)))) 3624 { 3625 error ("type mismatch in widening vector shift expression"); 3626 debug_generic_expr (lhs_type); 3627 debug_generic_expr (rhs1_type); 3628 debug_generic_expr (rhs2_type); 3629 return true; 3630 } 3631 3632 return false; 3633 } 3634 3635 case PLUS_EXPR: 3636 case MINUS_EXPR: 3637 { 3638 /* We use regular PLUS_EXPR and MINUS_EXPR for vectors. 3639 ??? This just makes the checker happy and may not be what is 3640 intended. */ 3641 if (TREE_CODE (lhs_type) == VECTOR_TYPE 3642 && POINTER_TYPE_P (TREE_TYPE (lhs_type))) 3643 { 3644 if (TREE_CODE (rhs1_type) != VECTOR_TYPE 3645 || TREE_CODE (rhs2_type) != VECTOR_TYPE) 3646 { 3647 error ("invalid non-vector operands to vector valued plus"); 3648 return true; 3649 } 3650 lhs_type = TREE_TYPE (lhs_type); 3651 rhs1_type = TREE_TYPE (rhs1_type); 3652 rhs2_type = TREE_TYPE (rhs2_type); 3653 /* PLUS_EXPR is commutative, so we might end up canonicalizing 3654 the pointer to 2nd place. */ 3655 if (POINTER_TYPE_P (rhs2_type)) 3656 { 3657 tree tem = rhs1_type; 3658 rhs1_type = rhs2_type; 3659 rhs2_type = tem; 3660 } 3661 goto do_pointer_plus_expr_check; 3662 } 3663 if (POINTER_TYPE_P (lhs_type) 3664 || POINTER_TYPE_P (rhs1_type) 3665 || POINTER_TYPE_P (rhs2_type)) 3666 { 3667 error ("invalid (pointer) operands to plus/minus"); 3668 return true; 3669 } 3670 3671 /* Continue with generic binary expression handling. */ 3672 break; 3673 } 3674 3675 case POINTER_PLUS_EXPR: 3676 { 3677 do_pointer_plus_expr_check: 3678 if (!POINTER_TYPE_P (rhs1_type) 3679 || !useless_type_conversion_p (lhs_type, rhs1_type) 3680 || !ptrofftype_p (rhs2_type)) 3681 { 3682 error ("type mismatch in pointer plus expression"); 3683 debug_generic_stmt (lhs_type); 3684 debug_generic_stmt (rhs1_type); 3685 debug_generic_stmt (rhs2_type); 3686 return true; 3687 } 3688 3689 return false; 3690 } 3691 3692 case TRUTH_ANDIF_EXPR: 3693 case TRUTH_ORIF_EXPR: 3694 case TRUTH_AND_EXPR: 3695 case TRUTH_OR_EXPR: 3696 case TRUTH_XOR_EXPR: 3697 3698 gcc_unreachable (); 3699 3700 case LT_EXPR: 3701 case LE_EXPR: 3702 case GT_EXPR: 3703 case GE_EXPR: 3704 case EQ_EXPR: 3705 case NE_EXPR: 3706 case UNORDERED_EXPR: 3707 case ORDERED_EXPR: 3708 case UNLT_EXPR: 3709 case UNLE_EXPR: 3710 case UNGT_EXPR: 3711 case UNGE_EXPR: 3712 case UNEQ_EXPR: 3713 case LTGT_EXPR: 3714 /* Comparisons are also binary, but the result type is not 3715 connected to the operand types. */ 3716 return verify_gimple_comparison (lhs_type, rhs1, rhs2); 3717 3718 case WIDEN_MULT_EXPR: 3719 if (TREE_CODE (lhs_type) != INTEGER_TYPE) 3720 return true; 3721 return ((2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type)) 3722 || (TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type))); 3723 3724 case WIDEN_SUM_EXPR: 3725 case VEC_WIDEN_MULT_HI_EXPR: 3726 case VEC_WIDEN_MULT_LO_EXPR: 3727 case VEC_PACK_TRUNC_EXPR: 3728 case VEC_PACK_SAT_EXPR: 3729 case VEC_PACK_FIX_TRUNC_EXPR: 3730 /* FIXME. */ 3731 return false; 3732 3733 case MULT_EXPR: 3734 case TRUNC_DIV_EXPR: 3735 case CEIL_DIV_EXPR: 3736 case FLOOR_DIV_EXPR: 3737 case ROUND_DIV_EXPR: 3738 case TRUNC_MOD_EXPR: 3739 case CEIL_MOD_EXPR: 3740 case FLOOR_MOD_EXPR: 3741 case ROUND_MOD_EXPR: 3742 case RDIV_EXPR: 3743 case EXACT_DIV_EXPR: 3744 case MIN_EXPR: 3745 case MAX_EXPR: 3746 case BIT_IOR_EXPR: 3747 case BIT_XOR_EXPR: 3748 case BIT_AND_EXPR: 3749 /* Continue with generic binary expression handling. */ 3750 break; 3751 3752 default: 3753 gcc_unreachable (); 3754 } 3755 3756 if (!useless_type_conversion_p (lhs_type, rhs1_type) 3757 || !useless_type_conversion_p (lhs_type, rhs2_type)) 3758 { 3759 error ("type mismatch in binary expression"); 3760 debug_generic_stmt (lhs_type); 3761 debug_generic_stmt (rhs1_type); 3762 debug_generic_stmt (rhs2_type); 3763 return true; 3764 } 3765 3766 return false; 3767 } 3768 3769 /* Verify a gimple assignment statement STMT with a ternary rhs. 3770 Returns true if anything is wrong. */ 3771 3772 static bool 3773 verify_gimple_assign_ternary (gimple stmt) 3774 { 3775 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3776 tree lhs = gimple_assign_lhs (stmt); 3777 tree lhs_type = TREE_TYPE (lhs); 3778 tree rhs1 = gimple_assign_rhs1 (stmt); 3779 tree rhs1_type = TREE_TYPE (rhs1); 3780 tree rhs2 = gimple_assign_rhs2 (stmt); 3781 tree rhs2_type = TREE_TYPE (rhs2); 3782 tree rhs3 = gimple_assign_rhs3 (stmt); 3783 tree rhs3_type = TREE_TYPE (rhs3); 3784 3785 if (!is_gimple_reg (lhs)) 3786 { 3787 error ("non-register as LHS of ternary operation"); 3788 return true; 3789 } 3790 3791 if (((rhs_code == VEC_COND_EXPR || rhs_code == COND_EXPR) 3792 ? !is_gimple_condexpr (rhs1) : !is_gimple_val (rhs1)) 3793 || !is_gimple_val (rhs2) 3794 || !is_gimple_val (rhs3)) 3795 { 3796 error ("invalid operands in ternary operation"); 3797 return true; 3798 } 3799 3800 /* First handle operations that involve different types. */ 3801 switch (rhs_code) 3802 { 3803 case WIDEN_MULT_PLUS_EXPR: 3804 case WIDEN_MULT_MINUS_EXPR: 3805 if ((!INTEGRAL_TYPE_P (rhs1_type) 3806 && !FIXED_POINT_TYPE_P (rhs1_type)) 3807 || !useless_type_conversion_p (rhs1_type, rhs2_type) 3808 || !useless_type_conversion_p (lhs_type, rhs3_type) 3809 || 2 * TYPE_PRECISION (rhs1_type) > TYPE_PRECISION (lhs_type) 3810 || TYPE_PRECISION (rhs1_type) != TYPE_PRECISION (rhs2_type)) 3811 { 3812 error ("type mismatch in widening multiply-accumulate expression"); 3813 debug_generic_expr (lhs_type); 3814 debug_generic_expr (rhs1_type); 3815 debug_generic_expr (rhs2_type); 3816 debug_generic_expr (rhs3_type); 3817 return true; 3818 } 3819 break; 3820 3821 case FMA_EXPR: 3822 if (!useless_type_conversion_p (lhs_type, rhs1_type) 3823 || !useless_type_conversion_p (lhs_type, rhs2_type) 3824 || !useless_type_conversion_p (lhs_type, rhs3_type)) 3825 { 3826 error ("type mismatch in fused multiply-add expression"); 3827 debug_generic_expr (lhs_type); 3828 debug_generic_expr (rhs1_type); 3829 debug_generic_expr (rhs2_type); 3830 debug_generic_expr (rhs3_type); 3831 return true; 3832 } 3833 break; 3834 3835 case COND_EXPR: 3836 case VEC_COND_EXPR: 3837 if (!useless_type_conversion_p (lhs_type, rhs2_type) 3838 || !useless_type_conversion_p (lhs_type, rhs3_type)) 3839 { 3840 error ("type mismatch in conditional expression"); 3841 debug_generic_expr (lhs_type); 3842 debug_generic_expr (rhs2_type); 3843 debug_generic_expr (rhs3_type); 3844 return true; 3845 } 3846 break; 3847 3848 case VEC_PERM_EXPR: 3849 if (!useless_type_conversion_p (lhs_type, rhs1_type) 3850 || !useless_type_conversion_p (lhs_type, rhs2_type)) 3851 { 3852 error ("type mismatch in vector permute expression"); 3853 debug_generic_expr (lhs_type); 3854 debug_generic_expr (rhs1_type); 3855 debug_generic_expr (rhs2_type); 3856 debug_generic_expr (rhs3_type); 3857 return true; 3858 } 3859 3860 if (TREE_CODE (rhs1_type) != VECTOR_TYPE 3861 || TREE_CODE (rhs2_type) != VECTOR_TYPE 3862 || TREE_CODE (rhs3_type) != VECTOR_TYPE) 3863 { 3864 error ("vector types expected in vector permute expression"); 3865 debug_generic_expr (lhs_type); 3866 debug_generic_expr (rhs1_type); 3867 debug_generic_expr (rhs2_type); 3868 debug_generic_expr (rhs3_type); 3869 return true; 3870 } 3871 3872 if (TYPE_VECTOR_SUBPARTS (rhs1_type) != TYPE_VECTOR_SUBPARTS (rhs2_type) 3873 || TYPE_VECTOR_SUBPARTS (rhs2_type) 3874 != TYPE_VECTOR_SUBPARTS (rhs3_type) 3875 || TYPE_VECTOR_SUBPARTS (rhs3_type) 3876 != TYPE_VECTOR_SUBPARTS (lhs_type)) 3877 { 3878 error ("vectors with different element number found " 3879 "in vector permute expression"); 3880 debug_generic_expr (lhs_type); 3881 debug_generic_expr (rhs1_type); 3882 debug_generic_expr (rhs2_type); 3883 debug_generic_expr (rhs3_type); 3884 return true; 3885 } 3886 3887 if (TREE_CODE (TREE_TYPE (rhs3_type)) != INTEGER_TYPE 3888 || GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs3_type))) 3889 != GET_MODE_BITSIZE (TYPE_MODE (TREE_TYPE (rhs1_type)))) 3890 { 3891 error ("invalid mask type in vector permute expression"); 3892 debug_generic_expr (lhs_type); 3893 debug_generic_expr (rhs1_type); 3894 debug_generic_expr (rhs2_type); 3895 debug_generic_expr (rhs3_type); 3896 return true; 3897 } 3898 3899 return false; 3900 3901 case DOT_PROD_EXPR: 3902 case REALIGN_LOAD_EXPR: 3903 /* FIXME. */ 3904 return false; 3905 3906 default: 3907 gcc_unreachable (); 3908 } 3909 return false; 3910 } 3911 3912 /* Verify a gimple assignment statement STMT with a single rhs. 3913 Returns true if anything is wrong. */ 3914 3915 static bool 3916 verify_gimple_assign_single (gimple stmt) 3917 { 3918 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 3919 tree lhs = gimple_assign_lhs (stmt); 3920 tree lhs_type = TREE_TYPE (lhs); 3921 tree rhs1 = gimple_assign_rhs1 (stmt); 3922 tree rhs1_type = TREE_TYPE (rhs1); 3923 bool res = false; 3924 3925 if (!useless_type_conversion_p (lhs_type, rhs1_type)) 3926 { 3927 error ("non-trivial conversion at assignment"); 3928 debug_generic_expr (lhs_type); 3929 debug_generic_expr (rhs1_type); 3930 return true; 3931 } 3932 3933 if (handled_component_p (lhs)) 3934 res |= verify_types_in_gimple_reference (lhs, true); 3935 3936 /* Special codes we cannot handle via their class. */ 3937 switch (rhs_code) 3938 { 3939 case ADDR_EXPR: 3940 { 3941 tree op = TREE_OPERAND (rhs1, 0); 3942 if (!is_gimple_addressable (op)) 3943 { 3944 error ("invalid operand in unary expression"); 3945 return true; 3946 } 3947 3948 /* Technically there is no longer a need for matching types, but 3949 gimple hygiene asks for this check. In LTO we can end up 3950 combining incompatible units and thus end up with addresses 3951 of globals that change their type to a common one. */ 3952 if (!in_lto_p 3953 && !types_compatible_p (TREE_TYPE (op), 3954 TREE_TYPE (TREE_TYPE (rhs1))) 3955 && !one_pointer_to_useless_type_conversion_p (TREE_TYPE (rhs1), 3956 TREE_TYPE (op))) 3957 { 3958 error ("type mismatch in address expression"); 3959 debug_generic_stmt (TREE_TYPE (rhs1)); 3960 debug_generic_stmt (TREE_TYPE (op)); 3961 return true; 3962 } 3963 3964 return verify_types_in_gimple_reference (op, true); 3965 } 3966 3967 /* tcc_reference */ 3968 case INDIRECT_REF: 3969 error ("INDIRECT_REF in gimple IL"); 3970 return true; 3971 3972 case COMPONENT_REF: 3973 case BIT_FIELD_REF: 3974 case ARRAY_REF: 3975 case ARRAY_RANGE_REF: 3976 case VIEW_CONVERT_EXPR: 3977 case REALPART_EXPR: 3978 case IMAGPART_EXPR: 3979 case TARGET_MEM_REF: 3980 case MEM_REF: 3981 if (!is_gimple_reg (lhs) 3982 && is_gimple_reg_type (TREE_TYPE (lhs))) 3983 { 3984 error ("invalid rhs for gimple memory store"); 3985 debug_generic_stmt (lhs); 3986 debug_generic_stmt (rhs1); 3987 return true; 3988 } 3989 return res || verify_types_in_gimple_reference (rhs1, false); 3990 3991 /* tcc_constant */ 3992 case SSA_NAME: 3993 case INTEGER_CST: 3994 case REAL_CST: 3995 case FIXED_CST: 3996 case COMPLEX_CST: 3997 case VECTOR_CST: 3998 case STRING_CST: 3999 return res; 4000 4001 /* tcc_declaration */ 4002 case CONST_DECL: 4003 return res; 4004 case VAR_DECL: 4005 case PARM_DECL: 4006 if (!is_gimple_reg (lhs) 4007 && !is_gimple_reg (rhs1) 4008 && is_gimple_reg_type (TREE_TYPE (lhs))) 4009 { 4010 error ("invalid rhs for gimple memory store"); 4011 debug_generic_stmt (lhs); 4012 debug_generic_stmt (rhs1); 4013 return true; 4014 } 4015 return res; 4016 4017 case CONSTRUCTOR: 4018 case OBJ_TYPE_REF: 4019 case ASSERT_EXPR: 4020 case WITH_SIZE_EXPR: 4021 /* FIXME. */ 4022 return res; 4023 4024 default:; 4025 } 4026 4027 return res; 4028 } 4029 4030 /* Verify the contents of a GIMPLE_ASSIGN STMT. Returns true when there 4031 is a problem, otherwise false. */ 4032 4033 static bool 4034 verify_gimple_assign (gimple stmt) 4035 { 4036 switch (gimple_assign_rhs_class (stmt)) 4037 { 4038 case GIMPLE_SINGLE_RHS: 4039 return verify_gimple_assign_single (stmt); 4040 4041 case GIMPLE_UNARY_RHS: 4042 return verify_gimple_assign_unary (stmt); 4043 4044 case GIMPLE_BINARY_RHS: 4045 return verify_gimple_assign_binary (stmt); 4046 4047 case GIMPLE_TERNARY_RHS: 4048 return verify_gimple_assign_ternary (stmt); 4049 4050 default: 4051 gcc_unreachable (); 4052 } 4053 } 4054 4055 /* Verify the contents of a GIMPLE_RETURN STMT. Returns true when there 4056 is a problem, otherwise false. */ 4057 4058 static bool 4059 verify_gimple_return (gimple stmt) 4060 { 4061 tree op = gimple_return_retval (stmt); 4062 tree restype = TREE_TYPE (TREE_TYPE (cfun->decl)); 4063 4064 /* We cannot test for present return values as we do not fix up missing 4065 return values from the original source. */ 4066 if (op == NULL) 4067 return false; 4068 4069 if (!is_gimple_val (op) 4070 && TREE_CODE (op) != RESULT_DECL) 4071 { 4072 error ("invalid operand in return statement"); 4073 debug_generic_stmt (op); 4074 return true; 4075 } 4076 4077 if ((TREE_CODE (op) == RESULT_DECL 4078 && DECL_BY_REFERENCE (op)) 4079 || (TREE_CODE (op) == SSA_NAME 4080 && TREE_CODE (SSA_NAME_VAR (op)) == RESULT_DECL 4081 && DECL_BY_REFERENCE (SSA_NAME_VAR (op)))) 4082 op = TREE_TYPE (op); 4083 4084 if (!useless_type_conversion_p (restype, TREE_TYPE (op))) 4085 { 4086 error ("invalid conversion in return statement"); 4087 debug_generic_stmt (restype); 4088 debug_generic_stmt (TREE_TYPE (op)); 4089 return true; 4090 } 4091 4092 return false; 4093 } 4094 4095 4096 /* Verify the contents of a GIMPLE_GOTO STMT. Returns true when there 4097 is a problem, otherwise false. */ 4098 4099 static bool 4100 verify_gimple_goto (gimple stmt) 4101 { 4102 tree dest = gimple_goto_dest (stmt); 4103 4104 /* ??? We have two canonical forms of direct goto destinations, a 4105 bare LABEL_DECL and an ADDR_EXPR of a LABEL_DECL. */ 4106 if (TREE_CODE (dest) != LABEL_DECL 4107 && (!is_gimple_val (dest) 4108 || !POINTER_TYPE_P (TREE_TYPE (dest)))) 4109 { 4110 error ("goto destination is neither a label nor a pointer"); 4111 return true; 4112 } 4113 4114 return false; 4115 } 4116 4117 /* Verify the contents of a GIMPLE_SWITCH STMT. Returns true when there 4118 is a problem, otherwise false. */ 4119 4120 static bool 4121 verify_gimple_switch (gimple stmt) 4122 { 4123 if (!is_gimple_val (gimple_switch_index (stmt))) 4124 { 4125 error ("invalid operand to switch statement"); 4126 debug_generic_stmt (gimple_switch_index (stmt)); 4127 return true; 4128 } 4129 4130 return false; 4131 } 4132 4133 /* Verify a gimple debug statement STMT. 4134 Returns true if anything is wrong. */ 4135 4136 static bool 4137 verify_gimple_debug (gimple stmt ATTRIBUTE_UNUSED) 4138 { 4139 /* There isn't much that could be wrong in a gimple debug stmt. A 4140 gimple debug bind stmt, for example, maps a tree, that's usually 4141 a VAR_DECL or a PARM_DECL, but that could also be some scalarized 4142 component or member of an aggregate type, to another tree, that 4143 can be an arbitrary expression. These stmts expand into debug 4144 insns, and are converted to debug notes by var-tracking.c. */ 4145 return false; 4146 } 4147 4148 /* Verify a gimple label statement STMT. 4149 Returns true if anything is wrong. */ 4150 4151 static bool 4152 verify_gimple_label (gimple stmt) 4153 { 4154 tree decl = gimple_label_label (stmt); 4155 int uid; 4156 bool err = false; 4157 4158 if (TREE_CODE (decl) != LABEL_DECL) 4159 return true; 4160 4161 uid = LABEL_DECL_UID (decl); 4162 if (cfun->cfg 4163 && (uid == -1 4164 || VEC_index (basic_block, 4165 label_to_block_map, uid) != gimple_bb (stmt))) 4166 { 4167 error ("incorrect entry in label_to_block_map"); 4168 err |= true; 4169 } 4170 4171 uid = EH_LANDING_PAD_NR (decl); 4172 if (uid) 4173 { 4174 eh_landing_pad lp = get_eh_landing_pad_from_number (uid); 4175 if (decl != lp->post_landing_pad) 4176 { 4177 error ("incorrect setting of landing pad number"); 4178 err |= true; 4179 } 4180 } 4181 4182 return err; 4183 } 4184 4185 /* Verify the GIMPLE statement STMT. Returns true if there is an 4186 error, otherwise false. */ 4187 4188 static bool 4189 verify_gimple_stmt (gimple stmt) 4190 { 4191 switch (gimple_code (stmt)) 4192 { 4193 case GIMPLE_ASSIGN: 4194 return verify_gimple_assign (stmt); 4195 4196 case GIMPLE_LABEL: 4197 return verify_gimple_label (stmt); 4198 4199 case GIMPLE_CALL: 4200 return verify_gimple_call (stmt); 4201 4202 case GIMPLE_COND: 4203 if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison) 4204 { 4205 error ("invalid comparison code in gimple cond"); 4206 return true; 4207 } 4208 if (!(!gimple_cond_true_label (stmt) 4209 || TREE_CODE (gimple_cond_true_label (stmt)) == LABEL_DECL) 4210 || !(!gimple_cond_false_label (stmt) 4211 || TREE_CODE (gimple_cond_false_label (stmt)) == LABEL_DECL)) 4212 { 4213 error ("invalid labels in gimple cond"); 4214 return true; 4215 } 4216 4217 return verify_gimple_comparison (boolean_type_node, 4218 gimple_cond_lhs (stmt), 4219 gimple_cond_rhs (stmt)); 4220 4221 case GIMPLE_GOTO: 4222 return verify_gimple_goto (stmt); 4223 4224 case GIMPLE_SWITCH: 4225 return verify_gimple_switch (stmt); 4226 4227 case GIMPLE_RETURN: 4228 return verify_gimple_return (stmt); 4229 4230 case GIMPLE_ASM: 4231 return false; 4232 4233 case GIMPLE_TRANSACTION: 4234 return verify_gimple_transaction (stmt); 4235 4236 /* Tuples that do not have tree operands. */ 4237 case GIMPLE_NOP: 4238 case GIMPLE_PREDICT: 4239 case GIMPLE_RESX: 4240 case GIMPLE_EH_DISPATCH: 4241 case GIMPLE_EH_MUST_NOT_THROW: 4242 return false; 4243 4244 CASE_GIMPLE_OMP: 4245 /* OpenMP directives are validated by the FE and never operated 4246 on by the optimizers. Furthermore, GIMPLE_OMP_FOR may contain 4247 non-gimple expressions when the main index variable has had 4248 its address taken. This does not affect the loop itself 4249 because the header of an GIMPLE_OMP_FOR is merely used to determine 4250 how to setup the parallel iteration. */ 4251 return false; 4252 4253 case GIMPLE_DEBUG: 4254 return verify_gimple_debug (stmt); 4255 4256 default: 4257 gcc_unreachable (); 4258 } 4259 } 4260 4261 /* Verify the contents of a GIMPLE_PHI. Returns true if there is a problem, 4262 and false otherwise. */ 4263 4264 static bool 4265 verify_gimple_phi (gimple phi) 4266 { 4267 bool err = false; 4268 unsigned i; 4269 tree phi_result = gimple_phi_result (phi); 4270 bool virtual_p; 4271 4272 if (!phi_result) 4273 { 4274 error ("invalid PHI result"); 4275 return true; 4276 } 4277 4278 virtual_p = !is_gimple_reg (phi_result); 4279 if (TREE_CODE (phi_result) != SSA_NAME 4280 || (virtual_p 4281 && SSA_NAME_VAR (phi_result) != gimple_vop (cfun))) 4282 { 4283 error ("invalid PHI result"); 4284 err = true; 4285 } 4286 4287 for (i = 0; i < gimple_phi_num_args (phi); i++) 4288 { 4289 tree t = gimple_phi_arg_def (phi, i); 4290 4291 if (!t) 4292 { 4293 error ("missing PHI def"); 4294 err |= true; 4295 continue; 4296 } 4297 /* Addressable variables do have SSA_NAMEs but they 4298 are not considered gimple values. */ 4299 else if ((TREE_CODE (t) == SSA_NAME 4300 && virtual_p != !is_gimple_reg (t)) 4301 || (virtual_p 4302 && (TREE_CODE (t) != SSA_NAME 4303 || SSA_NAME_VAR (t) != gimple_vop (cfun))) 4304 || (!virtual_p 4305 && !is_gimple_val (t))) 4306 { 4307 error ("invalid PHI argument"); 4308 debug_generic_expr (t); 4309 err |= true; 4310 } 4311 #ifdef ENABLE_TYPES_CHECKING 4312 if (!useless_type_conversion_p (TREE_TYPE (phi_result), TREE_TYPE (t))) 4313 { 4314 error ("incompatible types in PHI argument %u", i); 4315 debug_generic_stmt (TREE_TYPE (phi_result)); 4316 debug_generic_stmt (TREE_TYPE (t)); 4317 err |= true; 4318 } 4319 #endif 4320 } 4321 4322 return err; 4323 } 4324 4325 /* Verify the GIMPLE statements inside the sequence STMTS. */ 4326 4327 static bool 4328 verify_gimple_in_seq_2 (gimple_seq stmts) 4329 { 4330 gimple_stmt_iterator ittr; 4331 bool err = false; 4332 4333 for (ittr = gsi_start (stmts); !gsi_end_p (ittr); gsi_next (&ittr)) 4334 { 4335 gimple stmt = gsi_stmt (ittr); 4336 4337 switch (gimple_code (stmt)) 4338 { 4339 case GIMPLE_BIND: 4340 err |= verify_gimple_in_seq_2 (gimple_bind_body (stmt)); 4341 break; 4342 4343 case GIMPLE_TRY: 4344 err |= verify_gimple_in_seq_2 (gimple_try_eval (stmt)); 4345 err |= verify_gimple_in_seq_2 (gimple_try_cleanup (stmt)); 4346 break; 4347 4348 case GIMPLE_EH_FILTER: 4349 err |= verify_gimple_in_seq_2 (gimple_eh_filter_failure (stmt)); 4350 break; 4351 4352 case GIMPLE_EH_ELSE: 4353 err |= verify_gimple_in_seq_2 (gimple_eh_else_n_body (stmt)); 4354 err |= verify_gimple_in_seq_2 (gimple_eh_else_e_body (stmt)); 4355 break; 4356 4357 case GIMPLE_CATCH: 4358 err |= verify_gimple_in_seq_2 (gimple_catch_handler (stmt)); 4359 break; 4360 4361 case GIMPLE_TRANSACTION: 4362 err |= verify_gimple_transaction (stmt); 4363 break; 4364 4365 default: 4366 { 4367 bool err2 = verify_gimple_stmt (stmt); 4368 if (err2) 4369 debug_gimple_stmt (stmt); 4370 err |= err2; 4371 } 4372 } 4373 } 4374 4375 return err; 4376 } 4377 4378 /* Verify the contents of a GIMPLE_TRANSACTION. Returns true if there 4379 is a problem, otherwise false. */ 4380 4381 static bool 4382 verify_gimple_transaction (gimple stmt) 4383 { 4384 tree lab = gimple_transaction_label (stmt); 4385 if (lab != NULL && TREE_CODE (lab) != LABEL_DECL) 4386 return true; 4387 return verify_gimple_in_seq_2 (gimple_transaction_body (stmt)); 4388 } 4389 4390 4391 /* Verify the GIMPLE statements inside the statement list STMTS. */ 4392 4393 DEBUG_FUNCTION void 4394 verify_gimple_in_seq (gimple_seq stmts) 4395 { 4396 timevar_push (TV_TREE_STMT_VERIFY); 4397 if (verify_gimple_in_seq_2 (stmts)) 4398 internal_error ("verify_gimple failed"); 4399 timevar_pop (TV_TREE_STMT_VERIFY); 4400 } 4401 4402 /* Return true when the T can be shared. */ 4403 4404 bool 4405 tree_node_can_be_shared (tree t) 4406 { 4407 if (IS_TYPE_OR_DECL_P (t) 4408 || is_gimple_min_invariant (t) 4409 || TREE_CODE (t) == SSA_NAME 4410 || t == error_mark_node 4411 || TREE_CODE (t) == IDENTIFIER_NODE) 4412 return true; 4413 4414 if (TREE_CODE (t) == CASE_LABEL_EXPR) 4415 return true; 4416 4417 while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF) 4418 && is_gimple_min_invariant (TREE_OPERAND (t, 1))) 4419 || TREE_CODE (t) == COMPONENT_REF 4420 || TREE_CODE (t) == REALPART_EXPR 4421 || TREE_CODE (t) == IMAGPART_EXPR) 4422 t = TREE_OPERAND (t, 0); 4423 4424 if (DECL_P (t)) 4425 return true; 4426 4427 return false; 4428 } 4429 4430 /* Called via walk_gimple_stmt. Verify tree sharing. */ 4431 4432 static tree 4433 verify_node_sharing (tree *tp, int *walk_subtrees, void *data) 4434 { 4435 struct walk_stmt_info *wi = (struct walk_stmt_info *) data; 4436 struct pointer_set_t *visited = (struct pointer_set_t *) wi->info; 4437 4438 if (tree_node_can_be_shared (*tp)) 4439 { 4440 *walk_subtrees = false; 4441 return NULL; 4442 } 4443 4444 if (pointer_set_insert (visited, *tp)) 4445 return *tp; 4446 4447 return NULL; 4448 } 4449 4450 static bool eh_error_found; 4451 static int 4452 verify_eh_throw_stmt_node (void **slot, void *data) 4453 { 4454 struct throw_stmt_node *node = (struct throw_stmt_node *)*slot; 4455 struct pointer_set_t *visited = (struct pointer_set_t *) data; 4456 4457 if (!pointer_set_contains (visited, node->stmt)) 4458 { 4459 error ("dead STMT in EH table"); 4460 debug_gimple_stmt (node->stmt); 4461 eh_error_found = true; 4462 } 4463 return 1; 4464 } 4465 4466 /* Verify the GIMPLE statements in the CFG of FN. */ 4467 4468 DEBUG_FUNCTION void 4469 verify_gimple_in_cfg (struct function *fn) 4470 { 4471 basic_block bb; 4472 bool err = false; 4473 struct pointer_set_t *visited, *visited_stmts; 4474 4475 timevar_push (TV_TREE_STMT_VERIFY); 4476 visited = pointer_set_create (); 4477 visited_stmts = pointer_set_create (); 4478 4479 FOR_EACH_BB_FN (bb, fn) 4480 { 4481 gimple_stmt_iterator gsi; 4482 4483 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 4484 { 4485 gimple phi = gsi_stmt (gsi); 4486 bool err2 = false; 4487 unsigned i; 4488 4489 pointer_set_insert (visited_stmts, phi); 4490 4491 if (gimple_bb (phi) != bb) 4492 { 4493 error ("gimple_bb (phi) is set to a wrong basic block"); 4494 err2 = true; 4495 } 4496 4497 err2 |= verify_gimple_phi (phi); 4498 4499 for (i = 0; i < gimple_phi_num_args (phi); i++) 4500 { 4501 tree arg = gimple_phi_arg_def (phi, i); 4502 tree addr = walk_tree (&arg, verify_node_sharing, visited, NULL); 4503 if (addr) 4504 { 4505 error ("incorrect sharing of tree nodes"); 4506 debug_generic_expr (addr); 4507 err2 |= true; 4508 } 4509 } 4510 4511 if (err2) 4512 debug_gimple_stmt (phi); 4513 err |= err2; 4514 } 4515 4516 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 4517 { 4518 gimple stmt = gsi_stmt (gsi); 4519 bool err2 = false; 4520 struct walk_stmt_info wi; 4521 tree addr; 4522 int lp_nr; 4523 4524 pointer_set_insert (visited_stmts, stmt); 4525 4526 if (gimple_bb (stmt) != bb) 4527 { 4528 error ("gimple_bb (stmt) is set to a wrong basic block"); 4529 err2 = true; 4530 } 4531 4532 err2 |= verify_gimple_stmt (stmt); 4533 4534 memset (&wi, 0, sizeof (wi)); 4535 wi.info = (void *) visited; 4536 addr = walk_gimple_op (stmt, verify_node_sharing, &wi); 4537 if (addr) 4538 { 4539 error ("incorrect sharing of tree nodes"); 4540 debug_generic_expr (addr); 4541 err2 |= true; 4542 } 4543 4544 /* ??? Instead of not checking these stmts at all the walker 4545 should know its context via wi. */ 4546 if (!is_gimple_debug (stmt) 4547 && !is_gimple_omp (stmt)) 4548 { 4549 memset (&wi, 0, sizeof (wi)); 4550 addr = walk_gimple_op (stmt, verify_expr, &wi); 4551 if (addr) 4552 { 4553 debug_generic_expr (addr); 4554 inform (gimple_location (stmt), "in statement"); 4555 err2 |= true; 4556 } 4557 } 4558 4559 /* If the statement is marked as part of an EH region, then it is 4560 expected that the statement could throw. Verify that when we 4561 have optimizations that simplify statements such that we prove 4562 that they cannot throw, that we update other data structures 4563 to match. */ 4564 lp_nr = lookup_stmt_eh_lp (stmt); 4565 if (lp_nr != 0) 4566 { 4567 if (!stmt_could_throw_p (stmt)) 4568 { 4569 error ("statement marked for throw, but doesn%'t"); 4570 err2 |= true; 4571 } 4572 else if (lp_nr > 0 4573 && !gsi_one_before_end_p (gsi) 4574 && stmt_can_throw_internal (stmt)) 4575 { 4576 error ("statement marked for throw in middle of block"); 4577 err2 |= true; 4578 } 4579 } 4580 4581 if (err2) 4582 debug_gimple_stmt (stmt); 4583 err |= err2; 4584 } 4585 } 4586 4587 eh_error_found = false; 4588 if (get_eh_throw_stmt_table (cfun)) 4589 htab_traverse (get_eh_throw_stmt_table (cfun), 4590 verify_eh_throw_stmt_node, 4591 visited_stmts); 4592 4593 if (err || eh_error_found) 4594 internal_error ("verify_gimple failed"); 4595 4596 pointer_set_destroy (visited); 4597 pointer_set_destroy (visited_stmts); 4598 verify_histograms (); 4599 timevar_pop (TV_TREE_STMT_VERIFY); 4600 } 4601 4602 4603 /* Verifies that the flow information is OK. */ 4604 4605 static int 4606 gimple_verify_flow_info (void) 4607 { 4608 int err = 0; 4609 basic_block bb; 4610 gimple_stmt_iterator gsi; 4611 gimple stmt; 4612 edge e; 4613 edge_iterator ei; 4614 4615 if (ENTRY_BLOCK_PTR->il.gimple) 4616 { 4617 error ("ENTRY_BLOCK has IL associated with it"); 4618 err = 1; 4619 } 4620 4621 if (EXIT_BLOCK_PTR->il.gimple) 4622 { 4623 error ("EXIT_BLOCK has IL associated with it"); 4624 err = 1; 4625 } 4626 4627 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 4628 if (e->flags & EDGE_FALLTHRU) 4629 { 4630 error ("fallthru to exit from bb %d", e->src->index); 4631 err = 1; 4632 } 4633 4634 FOR_EACH_BB (bb) 4635 { 4636 bool found_ctrl_stmt = false; 4637 4638 stmt = NULL; 4639 4640 /* Skip labels on the start of basic block. */ 4641 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 4642 { 4643 tree label; 4644 gimple prev_stmt = stmt; 4645 4646 stmt = gsi_stmt (gsi); 4647 4648 if (gimple_code (stmt) != GIMPLE_LABEL) 4649 break; 4650 4651 label = gimple_label_label (stmt); 4652 if (prev_stmt && DECL_NONLOCAL (label)) 4653 { 4654 error ("nonlocal label "); 4655 print_generic_expr (stderr, label, 0); 4656 fprintf (stderr, " is not first in a sequence of labels in bb %d", 4657 bb->index); 4658 err = 1; 4659 } 4660 4661 if (prev_stmt && EH_LANDING_PAD_NR (label) != 0) 4662 { 4663 error ("EH landing pad label "); 4664 print_generic_expr (stderr, label, 0); 4665 fprintf (stderr, " is not first in a sequence of labels in bb %d", 4666 bb->index); 4667 err = 1; 4668 } 4669 4670 if (label_to_block (label) != bb) 4671 { 4672 error ("label "); 4673 print_generic_expr (stderr, label, 0); 4674 fprintf (stderr, " to block does not match in bb %d", 4675 bb->index); 4676 err = 1; 4677 } 4678 4679 if (decl_function_context (label) != current_function_decl) 4680 { 4681 error ("label "); 4682 print_generic_expr (stderr, label, 0); 4683 fprintf (stderr, " has incorrect context in bb %d", 4684 bb->index); 4685 err = 1; 4686 } 4687 } 4688 4689 /* Verify that body of basic block BB is free of control flow. */ 4690 for (; !gsi_end_p (gsi); gsi_next (&gsi)) 4691 { 4692 gimple stmt = gsi_stmt (gsi); 4693 4694 if (found_ctrl_stmt) 4695 { 4696 error ("control flow in the middle of basic block %d", 4697 bb->index); 4698 err = 1; 4699 } 4700 4701 if (stmt_ends_bb_p (stmt)) 4702 found_ctrl_stmt = true; 4703 4704 if (gimple_code (stmt) == GIMPLE_LABEL) 4705 { 4706 error ("label "); 4707 print_generic_expr (stderr, gimple_label_label (stmt), 0); 4708 fprintf (stderr, " in the middle of basic block %d", bb->index); 4709 err = 1; 4710 } 4711 } 4712 4713 gsi = gsi_last_bb (bb); 4714 if (gsi_end_p (gsi)) 4715 continue; 4716 4717 stmt = gsi_stmt (gsi); 4718 4719 if (gimple_code (stmt) == GIMPLE_LABEL) 4720 continue; 4721 4722 err |= verify_eh_edges (stmt); 4723 4724 if (is_ctrl_stmt (stmt)) 4725 { 4726 FOR_EACH_EDGE (e, ei, bb->succs) 4727 if (e->flags & EDGE_FALLTHRU) 4728 { 4729 error ("fallthru edge after a control statement in bb %d", 4730 bb->index); 4731 err = 1; 4732 } 4733 } 4734 4735 if (gimple_code (stmt) != GIMPLE_COND) 4736 { 4737 /* Verify that there are no edges with EDGE_TRUE/FALSE_FLAG set 4738 after anything else but if statement. */ 4739 FOR_EACH_EDGE (e, ei, bb->succs) 4740 if (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)) 4741 { 4742 error ("true/false edge after a non-GIMPLE_COND in bb %d", 4743 bb->index); 4744 err = 1; 4745 } 4746 } 4747 4748 switch (gimple_code (stmt)) 4749 { 4750 case GIMPLE_COND: 4751 { 4752 edge true_edge; 4753 edge false_edge; 4754 4755 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 4756 4757 if (!true_edge 4758 || !false_edge 4759 || !(true_edge->flags & EDGE_TRUE_VALUE) 4760 || !(false_edge->flags & EDGE_FALSE_VALUE) 4761 || (true_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL)) 4762 || (false_edge->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL)) 4763 || EDGE_COUNT (bb->succs) >= 3) 4764 { 4765 error ("wrong outgoing edge flags at end of bb %d", 4766 bb->index); 4767 err = 1; 4768 } 4769 } 4770 break; 4771 4772 case GIMPLE_GOTO: 4773 if (simple_goto_p (stmt)) 4774 { 4775 error ("explicit goto at end of bb %d", bb->index); 4776 err = 1; 4777 } 4778 else 4779 { 4780 /* FIXME. We should double check that the labels in the 4781 destination blocks have their address taken. */ 4782 FOR_EACH_EDGE (e, ei, bb->succs) 4783 if ((e->flags & (EDGE_FALLTHRU | EDGE_TRUE_VALUE 4784 | EDGE_FALSE_VALUE)) 4785 || !(e->flags & EDGE_ABNORMAL)) 4786 { 4787 error ("wrong outgoing edge flags at end of bb %d", 4788 bb->index); 4789 err = 1; 4790 } 4791 } 4792 break; 4793 4794 case GIMPLE_CALL: 4795 if (!gimple_call_builtin_p (stmt, BUILT_IN_RETURN)) 4796 break; 4797 /* ... fallthru ... */ 4798 case GIMPLE_RETURN: 4799 if (!single_succ_p (bb) 4800 || (single_succ_edge (bb)->flags 4801 & (EDGE_FALLTHRU | EDGE_ABNORMAL 4802 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 4803 { 4804 error ("wrong outgoing edge flags at end of bb %d", bb->index); 4805 err = 1; 4806 } 4807 if (single_succ (bb) != EXIT_BLOCK_PTR) 4808 { 4809 error ("return edge does not point to exit in bb %d", 4810 bb->index); 4811 err = 1; 4812 } 4813 break; 4814 4815 case GIMPLE_SWITCH: 4816 { 4817 tree prev; 4818 edge e; 4819 size_t i, n; 4820 4821 n = gimple_switch_num_labels (stmt); 4822 4823 /* Mark all the destination basic blocks. */ 4824 for (i = 0; i < n; ++i) 4825 { 4826 tree lab = CASE_LABEL (gimple_switch_label (stmt, i)); 4827 basic_block label_bb = label_to_block (lab); 4828 gcc_assert (!label_bb->aux || label_bb->aux == (void *)1); 4829 label_bb->aux = (void *)1; 4830 } 4831 4832 /* Verify that the case labels are sorted. */ 4833 prev = gimple_switch_label (stmt, 0); 4834 for (i = 1; i < n; ++i) 4835 { 4836 tree c = gimple_switch_label (stmt, i); 4837 if (!CASE_LOW (c)) 4838 { 4839 error ("found default case not at the start of " 4840 "case vector"); 4841 err = 1; 4842 continue; 4843 } 4844 if (CASE_LOW (prev) 4845 && !tree_int_cst_lt (CASE_LOW (prev), CASE_LOW (c))) 4846 { 4847 error ("case labels not sorted: "); 4848 print_generic_expr (stderr, prev, 0); 4849 fprintf (stderr," is greater than "); 4850 print_generic_expr (stderr, c, 0); 4851 fprintf (stderr," but comes before it.\n"); 4852 err = 1; 4853 } 4854 prev = c; 4855 } 4856 /* VRP will remove the default case if it can prove it will 4857 never be executed. So do not verify there always exists 4858 a default case here. */ 4859 4860 FOR_EACH_EDGE (e, ei, bb->succs) 4861 { 4862 if (!e->dest->aux) 4863 { 4864 error ("extra outgoing edge %d->%d", 4865 bb->index, e->dest->index); 4866 err = 1; 4867 } 4868 4869 e->dest->aux = (void *)2; 4870 if ((e->flags & (EDGE_FALLTHRU | EDGE_ABNORMAL 4871 | EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))) 4872 { 4873 error ("wrong outgoing edge flags at end of bb %d", 4874 bb->index); 4875 err = 1; 4876 } 4877 } 4878 4879 /* Check that we have all of them. */ 4880 for (i = 0; i < n; ++i) 4881 { 4882 tree lab = CASE_LABEL (gimple_switch_label (stmt, i)); 4883 basic_block label_bb = label_to_block (lab); 4884 4885 if (label_bb->aux != (void *)2) 4886 { 4887 error ("missing edge %i->%i", bb->index, label_bb->index); 4888 err = 1; 4889 } 4890 } 4891 4892 FOR_EACH_EDGE (e, ei, bb->succs) 4893 e->dest->aux = (void *)0; 4894 } 4895 break; 4896 4897 case GIMPLE_EH_DISPATCH: 4898 err |= verify_eh_dispatch_edge (stmt); 4899 break; 4900 4901 default: 4902 break; 4903 } 4904 } 4905 4906 if (dom_info_state (CDI_DOMINATORS) >= DOM_NO_FAST_QUERY) 4907 verify_dominators (CDI_DOMINATORS); 4908 4909 return err; 4910 } 4911 4912 4913 /* Updates phi nodes after creating a forwarder block joined 4914 by edge FALLTHRU. */ 4915 4916 static void 4917 gimple_make_forwarder_block (edge fallthru) 4918 { 4919 edge e; 4920 edge_iterator ei; 4921 basic_block dummy, bb; 4922 tree var; 4923 gimple_stmt_iterator gsi; 4924 4925 dummy = fallthru->src; 4926 bb = fallthru->dest; 4927 4928 if (single_pred_p (bb)) 4929 return; 4930 4931 /* If we redirected a branch we must create new PHI nodes at the 4932 start of BB. */ 4933 for (gsi = gsi_start_phis (dummy); !gsi_end_p (gsi); gsi_next (&gsi)) 4934 { 4935 gimple phi, new_phi; 4936 4937 phi = gsi_stmt (gsi); 4938 var = gimple_phi_result (phi); 4939 new_phi = create_phi_node (var, bb); 4940 SSA_NAME_DEF_STMT (var) = new_phi; 4941 gimple_phi_set_result (phi, make_ssa_name (SSA_NAME_VAR (var), phi)); 4942 add_phi_arg (new_phi, gimple_phi_result (phi), fallthru, 4943 UNKNOWN_LOCATION); 4944 } 4945 4946 /* Add the arguments we have stored on edges. */ 4947 FOR_EACH_EDGE (e, ei, bb->preds) 4948 { 4949 if (e == fallthru) 4950 continue; 4951 4952 flush_pending_stmts (e); 4953 } 4954 } 4955 4956 4957 /* Return a non-special label in the head of basic block BLOCK. 4958 Create one if it doesn't exist. */ 4959 4960 tree 4961 gimple_block_label (basic_block bb) 4962 { 4963 gimple_stmt_iterator i, s = gsi_start_bb (bb); 4964 bool first = true; 4965 tree label; 4966 gimple stmt; 4967 4968 for (i = s; !gsi_end_p (i); first = false, gsi_next (&i)) 4969 { 4970 stmt = gsi_stmt (i); 4971 if (gimple_code (stmt) != GIMPLE_LABEL) 4972 break; 4973 label = gimple_label_label (stmt); 4974 if (!DECL_NONLOCAL (label)) 4975 { 4976 if (!first) 4977 gsi_move_before (&i, &s); 4978 return label; 4979 } 4980 } 4981 4982 label = create_artificial_label (UNKNOWN_LOCATION); 4983 stmt = gimple_build_label (label); 4984 gsi_insert_before (&s, stmt, GSI_NEW_STMT); 4985 return label; 4986 } 4987 4988 4989 /* Attempt to perform edge redirection by replacing a possibly complex 4990 jump instruction by a goto or by removing the jump completely. 4991 This can apply only if all edges now point to the same block. The 4992 parameters and return values are equivalent to 4993 redirect_edge_and_branch. */ 4994 4995 static edge 4996 gimple_try_redirect_by_replacing_jump (edge e, basic_block target) 4997 { 4998 basic_block src = e->src; 4999 gimple_stmt_iterator i; 5000 gimple stmt; 5001 5002 /* We can replace or remove a complex jump only when we have exactly 5003 two edges. */ 5004 if (EDGE_COUNT (src->succs) != 2 5005 /* Verify that all targets will be TARGET. Specifically, the 5006 edge that is not E must also go to TARGET. */ 5007 || EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target) 5008 return NULL; 5009 5010 i = gsi_last_bb (src); 5011 if (gsi_end_p (i)) 5012 return NULL; 5013 5014 stmt = gsi_stmt (i); 5015 5016 if (gimple_code (stmt) == GIMPLE_COND || gimple_code (stmt) == GIMPLE_SWITCH) 5017 { 5018 gsi_remove (&i, true); 5019 e = ssa_redirect_edge (e, target); 5020 e->flags = EDGE_FALLTHRU; 5021 return e; 5022 } 5023 5024 return NULL; 5025 } 5026 5027 5028 /* Redirect E to DEST. Return NULL on failure. Otherwise, return the 5029 edge representing the redirected branch. */ 5030 5031 static edge 5032 gimple_redirect_edge_and_branch (edge e, basic_block dest) 5033 { 5034 basic_block bb = e->src; 5035 gimple_stmt_iterator gsi; 5036 edge ret; 5037 gimple stmt; 5038 5039 if (e->flags & EDGE_ABNORMAL) 5040 return NULL; 5041 5042 if (e->dest == dest) 5043 return NULL; 5044 5045 if (e->flags & EDGE_EH) 5046 return redirect_eh_edge (e, dest); 5047 5048 if (e->src != ENTRY_BLOCK_PTR) 5049 { 5050 ret = gimple_try_redirect_by_replacing_jump (e, dest); 5051 if (ret) 5052 return ret; 5053 } 5054 5055 gsi = gsi_last_bb (bb); 5056 stmt = gsi_end_p (gsi) ? NULL : gsi_stmt (gsi); 5057 5058 switch (stmt ? gimple_code (stmt) : GIMPLE_ERROR_MARK) 5059 { 5060 case GIMPLE_COND: 5061 /* For COND_EXPR, we only need to redirect the edge. */ 5062 break; 5063 5064 case GIMPLE_GOTO: 5065 /* No non-abnormal edges should lead from a non-simple goto, and 5066 simple ones should be represented implicitly. */ 5067 gcc_unreachable (); 5068 5069 case GIMPLE_SWITCH: 5070 { 5071 tree label = gimple_block_label (dest); 5072 tree cases = get_cases_for_edge (e, stmt); 5073 5074 /* If we have a list of cases associated with E, then use it 5075 as it's a lot faster than walking the entire case vector. */ 5076 if (cases) 5077 { 5078 edge e2 = find_edge (e->src, dest); 5079 tree last, first; 5080 5081 first = cases; 5082 while (cases) 5083 { 5084 last = cases; 5085 CASE_LABEL (cases) = label; 5086 cases = CASE_CHAIN (cases); 5087 } 5088 5089 /* If there was already an edge in the CFG, then we need 5090 to move all the cases associated with E to E2. */ 5091 if (e2) 5092 { 5093 tree cases2 = get_cases_for_edge (e2, stmt); 5094 5095 CASE_CHAIN (last) = CASE_CHAIN (cases2); 5096 CASE_CHAIN (cases2) = first; 5097 } 5098 bitmap_set_bit (touched_switch_bbs, gimple_bb (stmt)->index); 5099 } 5100 else 5101 { 5102 size_t i, n = gimple_switch_num_labels (stmt); 5103 5104 for (i = 0; i < n; i++) 5105 { 5106 tree elt = gimple_switch_label (stmt, i); 5107 if (label_to_block (CASE_LABEL (elt)) == e->dest) 5108 CASE_LABEL (elt) = label; 5109 } 5110 } 5111 } 5112 break; 5113 5114 case GIMPLE_ASM: 5115 { 5116 int i, n = gimple_asm_nlabels (stmt); 5117 tree label = NULL; 5118 5119 for (i = 0; i < n; ++i) 5120 { 5121 tree cons = gimple_asm_label_op (stmt, i); 5122 if (label_to_block (TREE_VALUE (cons)) == e->dest) 5123 { 5124 if (!label) 5125 label = gimple_block_label (dest); 5126 TREE_VALUE (cons) = label; 5127 } 5128 } 5129 5130 /* If we didn't find any label matching the former edge in the 5131 asm labels, we must be redirecting the fallthrough 5132 edge. */ 5133 gcc_assert (label || (e->flags & EDGE_FALLTHRU)); 5134 } 5135 break; 5136 5137 case GIMPLE_RETURN: 5138 gsi_remove (&gsi, true); 5139 e->flags |= EDGE_FALLTHRU; 5140 break; 5141 5142 case GIMPLE_OMP_RETURN: 5143 case GIMPLE_OMP_CONTINUE: 5144 case GIMPLE_OMP_SECTIONS_SWITCH: 5145 case GIMPLE_OMP_FOR: 5146 /* The edges from OMP constructs can be simply redirected. */ 5147 break; 5148 5149 case GIMPLE_EH_DISPATCH: 5150 if (!(e->flags & EDGE_FALLTHRU)) 5151 redirect_eh_dispatch_edge (stmt, e, dest); 5152 break; 5153 5154 case GIMPLE_TRANSACTION: 5155 /* The ABORT edge has a stored label associated with it, otherwise 5156 the edges are simply redirectable. */ 5157 if (e->flags == 0) 5158 gimple_transaction_set_label (stmt, gimple_block_label (dest)); 5159 break; 5160 5161 default: 5162 /* Otherwise it must be a fallthru edge, and we don't need to 5163 do anything besides redirecting it. */ 5164 gcc_assert (e->flags & EDGE_FALLTHRU); 5165 break; 5166 } 5167 5168 /* Update/insert PHI nodes as necessary. */ 5169 5170 /* Now update the edges in the CFG. */ 5171 e = ssa_redirect_edge (e, dest); 5172 5173 return e; 5174 } 5175 5176 /* Returns true if it is possible to remove edge E by redirecting 5177 it to the destination of the other edge from E->src. */ 5178 5179 static bool 5180 gimple_can_remove_branch_p (const_edge e) 5181 { 5182 if (e->flags & (EDGE_ABNORMAL | EDGE_EH)) 5183 return false; 5184 5185 return true; 5186 } 5187 5188 /* Simple wrapper, as we can always redirect fallthru edges. */ 5189 5190 static basic_block 5191 gimple_redirect_edge_and_branch_force (edge e, basic_block dest) 5192 { 5193 e = gimple_redirect_edge_and_branch (e, dest); 5194 gcc_assert (e); 5195 5196 return NULL; 5197 } 5198 5199 5200 /* Splits basic block BB after statement STMT (but at least after the 5201 labels). If STMT is NULL, BB is split just after the labels. */ 5202 5203 static basic_block 5204 gimple_split_block (basic_block bb, void *stmt) 5205 { 5206 gimple_stmt_iterator gsi; 5207 gimple_stmt_iterator gsi_tgt; 5208 gimple act; 5209 gimple_seq list; 5210 basic_block new_bb; 5211 edge e; 5212 edge_iterator ei; 5213 5214 new_bb = create_empty_bb (bb); 5215 5216 /* Redirect the outgoing edges. */ 5217 new_bb->succs = bb->succs; 5218 bb->succs = NULL; 5219 FOR_EACH_EDGE (e, ei, new_bb->succs) 5220 e->src = new_bb; 5221 5222 if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL) 5223 stmt = NULL; 5224 5225 /* Move everything from GSI to the new basic block. */ 5226 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 5227 { 5228 act = gsi_stmt (gsi); 5229 if (gimple_code (act) == GIMPLE_LABEL) 5230 continue; 5231 5232 if (!stmt) 5233 break; 5234 5235 if (stmt == act) 5236 { 5237 gsi_next (&gsi); 5238 break; 5239 } 5240 } 5241 5242 if (gsi_end_p (gsi)) 5243 return new_bb; 5244 5245 /* Split the statement list - avoid re-creating new containers as this 5246 brings ugly quadratic memory consumption in the inliner. 5247 (We are still quadratic since we need to update stmt BB pointers, 5248 sadly.) */ 5249 list = gsi_split_seq_before (&gsi); 5250 set_bb_seq (new_bb, list); 5251 for (gsi_tgt = gsi_start (list); 5252 !gsi_end_p (gsi_tgt); gsi_next (&gsi_tgt)) 5253 gimple_set_bb (gsi_stmt (gsi_tgt), new_bb); 5254 5255 return new_bb; 5256 } 5257 5258 5259 /* Moves basic block BB after block AFTER. */ 5260 5261 static bool 5262 gimple_move_block_after (basic_block bb, basic_block after) 5263 { 5264 if (bb->prev_bb == after) 5265 return true; 5266 5267 unlink_block (bb); 5268 link_block (bb, after); 5269 5270 return true; 5271 } 5272 5273 5274 /* Return true if basic_block can be duplicated. */ 5275 5276 static bool 5277 gimple_can_duplicate_bb_p (const_basic_block bb ATTRIBUTE_UNUSED) 5278 { 5279 return true; 5280 } 5281 5282 /* Create a duplicate of the basic block BB. NOTE: This does not 5283 preserve SSA form. */ 5284 5285 static basic_block 5286 gimple_duplicate_bb (basic_block bb) 5287 { 5288 basic_block new_bb; 5289 gimple_stmt_iterator gsi, gsi_tgt; 5290 gimple_seq phis = phi_nodes (bb); 5291 gimple phi, stmt, copy; 5292 5293 new_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb); 5294 5295 /* Copy the PHI nodes. We ignore PHI node arguments here because 5296 the incoming edges have not been setup yet. */ 5297 for (gsi = gsi_start (phis); !gsi_end_p (gsi); gsi_next (&gsi)) 5298 { 5299 phi = gsi_stmt (gsi); 5300 copy = create_phi_node (gimple_phi_result (phi), new_bb); 5301 create_new_def_for (gimple_phi_result (copy), copy, 5302 gimple_phi_result_ptr (copy)); 5303 } 5304 5305 gsi_tgt = gsi_start_bb (new_bb); 5306 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 5307 { 5308 def_operand_p def_p; 5309 ssa_op_iter op_iter; 5310 tree lhs; 5311 5312 stmt = gsi_stmt (gsi); 5313 if (gimple_code (stmt) == GIMPLE_LABEL) 5314 continue; 5315 5316 /* Don't duplicate label debug stmts. */ 5317 if (gimple_debug_bind_p (stmt) 5318 && TREE_CODE (gimple_debug_bind_get_var (stmt)) 5319 == LABEL_DECL) 5320 continue; 5321 5322 /* Create a new copy of STMT and duplicate STMT's virtual 5323 operands. */ 5324 copy = gimple_copy (stmt); 5325 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); 5326 5327 maybe_duplicate_eh_stmt (copy, stmt); 5328 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); 5329 5330 /* When copying around a stmt writing into a local non-user 5331 aggregate, make sure it won't share stack slot with other 5332 vars. */ 5333 lhs = gimple_get_lhs (stmt); 5334 if (lhs && TREE_CODE (lhs) != SSA_NAME) 5335 { 5336 tree base = get_base_address (lhs); 5337 if (base 5338 && (TREE_CODE (base) == VAR_DECL 5339 || TREE_CODE (base) == RESULT_DECL) 5340 && DECL_IGNORED_P (base) 5341 && !TREE_STATIC (base) 5342 && !DECL_EXTERNAL (base) 5343 && (TREE_CODE (base) != VAR_DECL 5344 || !DECL_HAS_VALUE_EXPR_P (base))) 5345 DECL_NONSHAREABLE (base) = 1; 5346 } 5347 5348 /* Create new names for all the definitions created by COPY and 5349 add replacement mappings for each new name. */ 5350 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) 5351 create_new_def_for (DEF_FROM_PTR (def_p), copy, def_p); 5352 } 5353 5354 return new_bb; 5355 } 5356 5357 /* Adds phi node arguments for edge E_COPY after basic block duplication. */ 5358 5359 static void 5360 add_phi_args_after_copy_edge (edge e_copy) 5361 { 5362 basic_block bb, bb_copy = e_copy->src, dest; 5363 edge e; 5364 edge_iterator ei; 5365 gimple phi, phi_copy; 5366 tree def; 5367 gimple_stmt_iterator psi, psi_copy; 5368 5369 if (gimple_seq_empty_p (phi_nodes (e_copy->dest))) 5370 return; 5371 5372 bb = bb_copy->flags & BB_DUPLICATED ? get_bb_original (bb_copy) : bb_copy; 5373 5374 if (e_copy->dest->flags & BB_DUPLICATED) 5375 dest = get_bb_original (e_copy->dest); 5376 else 5377 dest = e_copy->dest; 5378 5379 e = find_edge (bb, dest); 5380 if (!e) 5381 { 5382 /* During loop unrolling the target of the latch edge is copied. 5383 In this case we are not looking for edge to dest, but to 5384 duplicated block whose original was dest. */ 5385 FOR_EACH_EDGE (e, ei, bb->succs) 5386 { 5387 if ((e->dest->flags & BB_DUPLICATED) 5388 && get_bb_original (e->dest) == dest) 5389 break; 5390 } 5391 5392 gcc_assert (e != NULL); 5393 } 5394 5395 for (psi = gsi_start_phis (e->dest), 5396 psi_copy = gsi_start_phis (e_copy->dest); 5397 !gsi_end_p (psi); 5398 gsi_next (&psi), gsi_next (&psi_copy)) 5399 { 5400 phi = gsi_stmt (psi); 5401 phi_copy = gsi_stmt (psi_copy); 5402 def = PHI_ARG_DEF_FROM_EDGE (phi, e); 5403 add_phi_arg (phi_copy, def, e_copy, 5404 gimple_phi_arg_location_from_edge (phi, e)); 5405 } 5406 } 5407 5408 5409 /* Basic block BB_COPY was created by code duplication. Add phi node 5410 arguments for edges going out of BB_COPY. The blocks that were 5411 duplicated have BB_DUPLICATED set. */ 5412 5413 void 5414 add_phi_args_after_copy_bb (basic_block bb_copy) 5415 { 5416 edge e_copy; 5417 edge_iterator ei; 5418 5419 FOR_EACH_EDGE (e_copy, ei, bb_copy->succs) 5420 { 5421 add_phi_args_after_copy_edge (e_copy); 5422 } 5423 } 5424 5425 /* Blocks in REGION_COPY array of length N_REGION were created by 5426 duplication of basic blocks. Add phi node arguments for edges 5427 going from these blocks. If E_COPY is not NULL, also add 5428 phi node arguments for its destination.*/ 5429 5430 void 5431 add_phi_args_after_copy (basic_block *region_copy, unsigned n_region, 5432 edge e_copy) 5433 { 5434 unsigned i; 5435 5436 for (i = 0; i < n_region; i++) 5437 region_copy[i]->flags |= BB_DUPLICATED; 5438 5439 for (i = 0; i < n_region; i++) 5440 add_phi_args_after_copy_bb (region_copy[i]); 5441 if (e_copy) 5442 add_phi_args_after_copy_edge (e_copy); 5443 5444 for (i = 0; i < n_region; i++) 5445 region_copy[i]->flags &= ~BB_DUPLICATED; 5446 } 5447 5448 /* Duplicates a REGION (set of N_REGION basic blocks) with just a single 5449 important exit edge EXIT. By important we mean that no SSA name defined 5450 inside region is live over the other exit edges of the region. All entry 5451 edges to the region must go to ENTRY->dest. The edge ENTRY is redirected 5452 to the duplicate of the region. SSA form, dominance and loop information 5453 is updated. The new basic blocks are stored to REGION_COPY in the same 5454 order as they had in REGION, provided that REGION_COPY is not NULL. 5455 The function returns false if it is unable to copy the region, 5456 true otherwise. */ 5457 5458 bool 5459 gimple_duplicate_sese_region (edge entry, edge exit, 5460 basic_block *region, unsigned n_region, 5461 basic_block *region_copy) 5462 { 5463 unsigned i; 5464 bool free_region_copy = false, copying_header = false; 5465 struct loop *loop = entry->dest->loop_father; 5466 edge exit_copy; 5467 VEC (basic_block, heap) *doms; 5468 edge redirected; 5469 int total_freq = 0, entry_freq = 0; 5470 gcov_type total_count = 0, entry_count = 0; 5471 5472 if (!can_copy_bbs_p (region, n_region)) 5473 return false; 5474 5475 /* Some sanity checking. Note that we do not check for all possible 5476 missuses of the functions. I.e. if you ask to copy something weird, 5477 it will work, but the state of structures probably will not be 5478 correct. */ 5479 for (i = 0; i < n_region; i++) 5480 { 5481 /* We do not handle subloops, i.e. all the blocks must belong to the 5482 same loop. */ 5483 if (region[i]->loop_father != loop) 5484 return false; 5485 5486 if (region[i] != entry->dest 5487 && region[i] == loop->header) 5488 return false; 5489 } 5490 5491 set_loop_copy (loop, loop); 5492 5493 /* In case the function is used for loop header copying (which is the primary 5494 use), ensure that EXIT and its copy will be new latch and entry edges. */ 5495 if (loop->header == entry->dest) 5496 { 5497 copying_header = true; 5498 set_loop_copy (loop, loop_outer (loop)); 5499 5500 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src)) 5501 return false; 5502 5503 for (i = 0; i < n_region; i++) 5504 if (region[i] != exit->src 5505 && dominated_by_p (CDI_DOMINATORS, region[i], exit->src)) 5506 return false; 5507 } 5508 5509 if (!region_copy) 5510 { 5511 region_copy = XNEWVEC (basic_block, n_region); 5512 free_region_copy = true; 5513 } 5514 5515 gcc_assert (!need_ssa_update_p (cfun)); 5516 5517 /* Record blocks outside the region that are dominated by something 5518 inside. */ 5519 doms = NULL; 5520 initialize_original_copy_tables (); 5521 5522 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region); 5523 5524 if (entry->dest->count) 5525 { 5526 total_count = entry->dest->count; 5527 entry_count = entry->count; 5528 /* Fix up corner cases, to avoid division by zero or creation of negative 5529 frequencies. */ 5530 if (entry_count > total_count) 5531 entry_count = total_count; 5532 } 5533 else 5534 { 5535 total_freq = entry->dest->frequency; 5536 entry_freq = EDGE_FREQUENCY (entry); 5537 /* Fix up corner cases, to avoid division by zero or creation of negative 5538 frequencies. */ 5539 if (total_freq == 0) 5540 total_freq = 1; 5541 else if (entry_freq > total_freq) 5542 entry_freq = total_freq; 5543 } 5544 5545 copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop, 5546 split_edge_bb_loc (entry)); 5547 if (total_count) 5548 { 5549 scale_bbs_frequencies_gcov_type (region, n_region, 5550 total_count - entry_count, 5551 total_count); 5552 scale_bbs_frequencies_gcov_type (region_copy, n_region, entry_count, 5553 total_count); 5554 } 5555 else 5556 { 5557 scale_bbs_frequencies_int (region, n_region, total_freq - entry_freq, 5558 total_freq); 5559 scale_bbs_frequencies_int (region_copy, n_region, entry_freq, total_freq); 5560 } 5561 5562 if (copying_header) 5563 { 5564 loop->header = exit->dest; 5565 loop->latch = exit->src; 5566 } 5567 5568 /* Redirect the entry and add the phi node arguments. */ 5569 redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest)); 5570 gcc_assert (redirected != NULL); 5571 flush_pending_stmts (entry); 5572 5573 /* Concerning updating of dominators: We must recount dominators 5574 for entry block and its copy. Anything that is outside of the 5575 region, but was dominated by something inside needs recounting as 5576 well. */ 5577 set_immediate_dominator (CDI_DOMINATORS, entry->dest, entry->src); 5578 VEC_safe_push (basic_block, heap, doms, get_bb_original (entry->dest)); 5579 iterate_fix_dominators (CDI_DOMINATORS, doms, false); 5580 VEC_free (basic_block, heap, doms); 5581 5582 /* Add the other PHI node arguments. */ 5583 add_phi_args_after_copy (region_copy, n_region, NULL); 5584 5585 /* Update the SSA web. */ 5586 update_ssa (TODO_update_ssa); 5587 5588 if (free_region_copy) 5589 free (region_copy); 5590 5591 free_original_copy_tables (); 5592 return true; 5593 } 5594 5595 /* Duplicates REGION consisting of N_REGION blocks. The new blocks 5596 are stored to REGION_COPY in the same order in that they appear 5597 in REGION, if REGION_COPY is not NULL. ENTRY is the entry to 5598 the region, EXIT an exit from it. The condition guarding EXIT 5599 is moved to ENTRY. Returns true if duplication succeeds, false 5600 otherwise. 5601 5602 For example, 5603 5604 some_code; 5605 if (cond) 5606 A; 5607 else 5608 B; 5609 5610 is transformed to 5611 5612 if (cond) 5613 { 5614 some_code; 5615 A; 5616 } 5617 else 5618 { 5619 some_code; 5620 B; 5621 } 5622 */ 5623 5624 bool 5625 gimple_duplicate_sese_tail (edge entry ATTRIBUTE_UNUSED, edge exit ATTRIBUTE_UNUSED, 5626 basic_block *region ATTRIBUTE_UNUSED, unsigned n_region ATTRIBUTE_UNUSED, 5627 basic_block *region_copy ATTRIBUTE_UNUSED) 5628 { 5629 unsigned i; 5630 bool free_region_copy = false; 5631 struct loop *loop = exit->dest->loop_father; 5632 struct loop *orig_loop = entry->dest->loop_father; 5633 basic_block switch_bb, entry_bb, nentry_bb; 5634 VEC (basic_block, heap) *doms; 5635 int total_freq = 0, exit_freq = 0; 5636 gcov_type total_count = 0, exit_count = 0; 5637 edge exits[2], nexits[2], e; 5638 gimple_stmt_iterator gsi; 5639 gimple cond_stmt; 5640 edge sorig, snew; 5641 basic_block exit_bb; 5642 gimple_stmt_iterator psi; 5643 gimple phi; 5644 tree def; 5645 5646 gcc_assert (EDGE_COUNT (exit->src->succs) == 2); 5647 exits[0] = exit; 5648 exits[1] = EDGE_SUCC (exit->src, EDGE_SUCC (exit->src, 0) == exit); 5649 5650 if (!can_copy_bbs_p (region, n_region)) 5651 return false; 5652 5653 initialize_original_copy_tables (); 5654 set_loop_copy (orig_loop, loop); 5655 duplicate_subloops (orig_loop, loop); 5656 5657 if (!region_copy) 5658 { 5659 region_copy = XNEWVEC (basic_block, n_region); 5660 free_region_copy = true; 5661 } 5662 5663 gcc_assert (!need_ssa_update_p (cfun)); 5664 5665 /* Record blocks outside the region that are dominated by something 5666 inside. */ 5667 doms = get_dominated_by_region (CDI_DOMINATORS, region, n_region); 5668 5669 if (exit->src->count) 5670 { 5671 total_count = exit->src->count; 5672 exit_count = exit->count; 5673 /* Fix up corner cases, to avoid division by zero or creation of negative 5674 frequencies. */ 5675 if (exit_count > total_count) 5676 exit_count = total_count; 5677 } 5678 else 5679 { 5680 total_freq = exit->src->frequency; 5681 exit_freq = EDGE_FREQUENCY (exit); 5682 /* Fix up corner cases, to avoid division by zero or creation of negative 5683 frequencies. */ 5684 if (total_freq == 0) 5685 total_freq = 1; 5686 if (exit_freq > total_freq) 5687 exit_freq = total_freq; 5688 } 5689 5690 copy_bbs (region, n_region, region_copy, exits, 2, nexits, orig_loop, 5691 split_edge_bb_loc (exit)); 5692 if (total_count) 5693 { 5694 scale_bbs_frequencies_gcov_type (region, n_region, 5695 total_count - exit_count, 5696 total_count); 5697 scale_bbs_frequencies_gcov_type (region_copy, n_region, exit_count, 5698 total_count); 5699 } 5700 else 5701 { 5702 scale_bbs_frequencies_int (region, n_region, total_freq - exit_freq, 5703 total_freq); 5704 scale_bbs_frequencies_int (region_copy, n_region, exit_freq, total_freq); 5705 } 5706 5707 /* Create the switch block, and put the exit condition to it. */ 5708 entry_bb = entry->dest; 5709 nentry_bb = get_bb_copy (entry_bb); 5710 if (!last_stmt (entry->src) 5711 || !stmt_ends_bb_p (last_stmt (entry->src))) 5712 switch_bb = entry->src; 5713 else 5714 switch_bb = split_edge (entry); 5715 set_immediate_dominator (CDI_DOMINATORS, nentry_bb, switch_bb); 5716 5717 gsi = gsi_last_bb (switch_bb); 5718 cond_stmt = last_stmt (exit->src); 5719 gcc_assert (gimple_code (cond_stmt) == GIMPLE_COND); 5720 cond_stmt = gimple_copy (cond_stmt); 5721 5722 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); 5723 5724 sorig = single_succ_edge (switch_bb); 5725 sorig->flags = exits[1]->flags; 5726 snew = make_edge (switch_bb, nentry_bb, exits[0]->flags); 5727 5728 /* Register the new edge from SWITCH_BB in loop exit lists. */ 5729 rescan_loop_exit (snew, true, false); 5730 5731 /* Add the PHI node arguments. */ 5732 add_phi_args_after_copy (region_copy, n_region, snew); 5733 5734 /* Get rid of now superfluous conditions and associated edges (and phi node 5735 arguments). */ 5736 exit_bb = exit->dest; 5737 5738 e = redirect_edge_and_branch (exits[0], exits[1]->dest); 5739 PENDING_STMT (e) = NULL; 5740 5741 /* The latch of ORIG_LOOP was copied, and so was the backedge 5742 to the original header. We redirect this backedge to EXIT_BB. */ 5743 for (i = 0; i < n_region; i++) 5744 if (get_bb_original (region_copy[i]) == orig_loop->latch) 5745 { 5746 gcc_assert (single_succ_edge (region_copy[i])); 5747 e = redirect_edge_and_branch (single_succ_edge (region_copy[i]), exit_bb); 5748 PENDING_STMT (e) = NULL; 5749 for (psi = gsi_start_phis (exit_bb); 5750 !gsi_end_p (psi); 5751 gsi_next (&psi)) 5752 { 5753 phi = gsi_stmt (psi); 5754 def = PHI_ARG_DEF (phi, nexits[0]->dest_idx); 5755 add_phi_arg (phi, def, e, gimple_phi_arg_location_from_edge (phi, e)); 5756 } 5757 } 5758 e = redirect_edge_and_branch (nexits[0], nexits[1]->dest); 5759 PENDING_STMT (e) = NULL; 5760 5761 /* Anything that is outside of the region, but was dominated by something 5762 inside needs to update dominance info. */ 5763 iterate_fix_dominators (CDI_DOMINATORS, doms, false); 5764 VEC_free (basic_block, heap, doms); 5765 /* Update the SSA web. */ 5766 update_ssa (TODO_update_ssa); 5767 5768 if (free_region_copy) 5769 free (region_copy); 5770 5771 free_original_copy_tables (); 5772 return true; 5773 } 5774 5775 /* Add all the blocks dominated by ENTRY to the array BBS_P. Stop 5776 adding blocks when the dominator traversal reaches EXIT. This 5777 function silently assumes that ENTRY strictly dominates EXIT. */ 5778 5779 void 5780 gather_blocks_in_sese_region (basic_block entry, basic_block exit, 5781 VEC(basic_block,heap) **bbs_p) 5782 { 5783 basic_block son; 5784 5785 for (son = first_dom_son (CDI_DOMINATORS, entry); 5786 son; 5787 son = next_dom_son (CDI_DOMINATORS, son)) 5788 { 5789 VEC_safe_push (basic_block, heap, *bbs_p, son); 5790 if (son != exit) 5791 gather_blocks_in_sese_region (son, exit, bbs_p); 5792 } 5793 } 5794 5795 /* Replaces *TP with a duplicate (belonging to function TO_CONTEXT). 5796 The duplicates are recorded in VARS_MAP. */ 5797 5798 static void 5799 replace_by_duplicate_decl (tree *tp, struct pointer_map_t *vars_map, 5800 tree to_context) 5801 { 5802 tree t = *tp, new_t; 5803 struct function *f = DECL_STRUCT_FUNCTION (to_context); 5804 void **loc; 5805 5806 if (DECL_CONTEXT (t) == to_context) 5807 return; 5808 5809 loc = pointer_map_contains (vars_map, t); 5810 5811 if (!loc) 5812 { 5813 loc = pointer_map_insert (vars_map, t); 5814 5815 if (SSA_VAR_P (t)) 5816 { 5817 new_t = copy_var_decl (t, DECL_NAME (t), TREE_TYPE (t)); 5818 add_local_decl (f, new_t); 5819 } 5820 else 5821 { 5822 gcc_assert (TREE_CODE (t) == CONST_DECL); 5823 new_t = copy_node (t); 5824 } 5825 DECL_CONTEXT (new_t) = to_context; 5826 5827 *loc = new_t; 5828 } 5829 else 5830 new_t = (tree) *loc; 5831 5832 *tp = new_t; 5833 } 5834 5835 5836 /* Creates an ssa name in TO_CONTEXT equivalent to NAME. 5837 VARS_MAP maps old ssa names and var_decls to the new ones. */ 5838 5839 static tree 5840 replace_ssa_name (tree name, struct pointer_map_t *vars_map, 5841 tree to_context) 5842 { 5843 void **loc; 5844 tree new_name, decl = SSA_NAME_VAR (name); 5845 5846 gcc_assert (is_gimple_reg (name)); 5847 5848 loc = pointer_map_contains (vars_map, name); 5849 5850 if (!loc) 5851 { 5852 replace_by_duplicate_decl (&decl, vars_map, to_context); 5853 5854 push_cfun (DECL_STRUCT_FUNCTION (to_context)); 5855 if (gimple_in_ssa_p (cfun)) 5856 add_referenced_var (decl); 5857 5858 new_name = make_ssa_name (decl, SSA_NAME_DEF_STMT (name)); 5859 if (SSA_NAME_IS_DEFAULT_DEF (name)) 5860 set_default_def (decl, new_name); 5861 pop_cfun (); 5862 5863 loc = pointer_map_insert (vars_map, name); 5864 *loc = new_name; 5865 } 5866 else 5867 new_name = (tree) *loc; 5868 5869 return new_name; 5870 } 5871 5872 struct move_stmt_d 5873 { 5874 tree orig_block; 5875 tree new_block; 5876 tree from_context; 5877 tree to_context; 5878 struct pointer_map_t *vars_map; 5879 htab_t new_label_map; 5880 struct pointer_map_t *eh_map; 5881 bool remap_decls_p; 5882 }; 5883 5884 /* Helper for move_block_to_fn. Set TREE_BLOCK in every expression 5885 contained in *TP if it has been ORIG_BLOCK previously and change the 5886 DECL_CONTEXT of every local variable referenced in *TP. */ 5887 5888 static tree 5889 move_stmt_op (tree *tp, int *walk_subtrees, void *data) 5890 { 5891 struct walk_stmt_info *wi = (struct walk_stmt_info *) data; 5892 struct move_stmt_d *p = (struct move_stmt_d *) wi->info; 5893 tree t = *tp; 5894 5895 if (EXPR_P (t)) 5896 /* We should never have TREE_BLOCK set on non-statements. */ 5897 gcc_assert (!TREE_BLOCK (t)); 5898 5899 else if (DECL_P (t) || TREE_CODE (t) == SSA_NAME) 5900 { 5901 if (TREE_CODE (t) == SSA_NAME) 5902 *tp = replace_ssa_name (t, p->vars_map, p->to_context); 5903 else if (TREE_CODE (t) == LABEL_DECL) 5904 { 5905 if (p->new_label_map) 5906 { 5907 struct tree_map in, *out; 5908 in.base.from = t; 5909 out = (struct tree_map *) 5910 htab_find_with_hash (p->new_label_map, &in, DECL_UID (t)); 5911 if (out) 5912 *tp = t = out->to; 5913 } 5914 5915 DECL_CONTEXT (t) = p->to_context; 5916 } 5917 else if (p->remap_decls_p) 5918 { 5919 /* Replace T with its duplicate. T should no longer appear in the 5920 parent function, so this looks wasteful; however, it may appear 5921 in referenced_vars, and more importantly, as virtual operands of 5922 statements, and in alias lists of other variables. It would be 5923 quite difficult to expunge it from all those places. ??? It might 5924 suffice to do this for addressable variables. */ 5925 if ((TREE_CODE (t) == VAR_DECL 5926 && !is_global_var (t)) 5927 || TREE_CODE (t) == CONST_DECL) 5928 replace_by_duplicate_decl (tp, p->vars_map, p->to_context); 5929 5930 if (SSA_VAR_P (t) 5931 && gimple_in_ssa_p (cfun)) 5932 { 5933 push_cfun (DECL_STRUCT_FUNCTION (p->to_context)); 5934 add_referenced_var (*tp); 5935 pop_cfun (); 5936 } 5937 } 5938 *walk_subtrees = 0; 5939 } 5940 else if (TYPE_P (t)) 5941 *walk_subtrees = 0; 5942 5943 return NULL_TREE; 5944 } 5945 5946 /* Helper for move_stmt_r. Given an EH region number for the source 5947 function, map that to the duplicate EH regio number in the dest. */ 5948 5949 static int 5950 move_stmt_eh_region_nr (int old_nr, struct move_stmt_d *p) 5951 { 5952 eh_region old_r, new_r; 5953 void **slot; 5954 5955 old_r = get_eh_region_from_number (old_nr); 5956 slot = pointer_map_contains (p->eh_map, old_r); 5957 new_r = (eh_region) *slot; 5958 5959 return new_r->index; 5960 } 5961 5962 /* Similar, but operate on INTEGER_CSTs. */ 5963 5964 static tree 5965 move_stmt_eh_region_tree_nr (tree old_t_nr, struct move_stmt_d *p) 5966 { 5967 int old_nr, new_nr; 5968 5969 old_nr = tree_low_cst (old_t_nr, 0); 5970 new_nr = move_stmt_eh_region_nr (old_nr, p); 5971 5972 return build_int_cst (integer_type_node, new_nr); 5973 } 5974 5975 /* Like move_stmt_op, but for gimple statements. 5976 5977 Helper for move_block_to_fn. Set GIMPLE_BLOCK in every expression 5978 contained in the current statement in *GSI_P and change the 5979 DECL_CONTEXT of every local variable referenced in the current 5980 statement. */ 5981 5982 static tree 5983 move_stmt_r (gimple_stmt_iterator *gsi_p, bool *handled_ops_p, 5984 struct walk_stmt_info *wi) 5985 { 5986 struct move_stmt_d *p = (struct move_stmt_d *) wi->info; 5987 gimple stmt = gsi_stmt (*gsi_p); 5988 tree block = gimple_block (stmt); 5989 5990 if (p->orig_block == NULL_TREE 5991 || block == p->orig_block 5992 || block == NULL_TREE) 5993 gimple_set_block (stmt, p->new_block); 5994 #ifdef ENABLE_CHECKING 5995 else if (block != p->new_block) 5996 { 5997 while (block && block != p->orig_block) 5998 block = BLOCK_SUPERCONTEXT (block); 5999 gcc_assert (block); 6000 } 6001 #endif 6002 6003 switch (gimple_code (stmt)) 6004 { 6005 case GIMPLE_CALL: 6006 /* Remap the region numbers for __builtin_eh_{pointer,filter}. */ 6007 { 6008 tree r, fndecl = gimple_call_fndecl (stmt); 6009 if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) 6010 switch (DECL_FUNCTION_CODE (fndecl)) 6011 { 6012 case BUILT_IN_EH_COPY_VALUES: 6013 r = gimple_call_arg (stmt, 1); 6014 r = move_stmt_eh_region_tree_nr (r, p); 6015 gimple_call_set_arg (stmt, 1, r); 6016 /* FALLTHRU */ 6017 6018 case BUILT_IN_EH_POINTER: 6019 case BUILT_IN_EH_FILTER: 6020 r = gimple_call_arg (stmt, 0); 6021 r = move_stmt_eh_region_tree_nr (r, p); 6022 gimple_call_set_arg (stmt, 0, r); 6023 break; 6024 6025 default: 6026 break; 6027 } 6028 } 6029 break; 6030 6031 case GIMPLE_RESX: 6032 { 6033 int r = gimple_resx_region (stmt); 6034 r = move_stmt_eh_region_nr (r, p); 6035 gimple_resx_set_region (stmt, r); 6036 } 6037 break; 6038 6039 case GIMPLE_EH_DISPATCH: 6040 { 6041 int r = gimple_eh_dispatch_region (stmt); 6042 r = move_stmt_eh_region_nr (r, p); 6043 gimple_eh_dispatch_set_region (stmt, r); 6044 } 6045 break; 6046 6047 case GIMPLE_OMP_RETURN: 6048 case GIMPLE_OMP_CONTINUE: 6049 break; 6050 default: 6051 if (is_gimple_omp (stmt)) 6052 { 6053 /* Do not remap variables inside OMP directives. Variables 6054 referenced in clauses and directive header belong to the 6055 parent function and should not be moved into the child 6056 function. */ 6057 bool save_remap_decls_p = p->remap_decls_p; 6058 p->remap_decls_p = false; 6059 *handled_ops_p = true; 6060 6061 walk_gimple_seq (gimple_omp_body (stmt), move_stmt_r, 6062 move_stmt_op, wi); 6063 6064 p->remap_decls_p = save_remap_decls_p; 6065 } 6066 break; 6067 } 6068 6069 return NULL_TREE; 6070 } 6071 6072 /* Move basic block BB from function CFUN to function DEST_FN. The 6073 block is moved out of the original linked list and placed after 6074 block AFTER in the new list. Also, the block is removed from the 6075 original array of blocks and placed in DEST_FN's array of blocks. 6076 If UPDATE_EDGE_COUNT_P is true, the edge counts on both CFGs is 6077 updated to reflect the moved edges. 6078 6079 The local variables are remapped to new instances, VARS_MAP is used 6080 to record the mapping. */ 6081 6082 static void 6083 move_block_to_fn (struct function *dest_cfun, basic_block bb, 6084 basic_block after, bool update_edge_count_p, 6085 struct move_stmt_d *d) 6086 { 6087 struct control_flow_graph *cfg; 6088 edge_iterator ei; 6089 edge e; 6090 gimple_stmt_iterator si; 6091 unsigned old_len, new_len; 6092 6093 /* Remove BB from dominance structures. */ 6094 delete_from_dominance_info (CDI_DOMINATORS, bb); 6095 if (current_loops) 6096 remove_bb_from_loops (bb); 6097 6098 /* Link BB to the new linked list. */ 6099 move_block_after (bb, after); 6100 6101 /* Update the edge count in the corresponding flowgraphs. */ 6102 if (update_edge_count_p) 6103 FOR_EACH_EDGE (e, ei, bb->succs) 6104 { 6105 cfun->cfg->x_n_edges--; 6106 dest_cfun->cfg->x_n_edges++; 6107 } 6108 6109 /* Remove BB from the original basic block array. */ 6110 VEC_replace (basic_block, cfun->cfg->x_basic_block_info, bb->index, NULL); 6111 cfun->cfg->x_n_basic_blocks--; 6112 6113 /* Grow DEST_CFUN's basic block array if needed. */ 6114 cfg = dest_cfun->cfg; 6115 cfg->x_n_basic_blocks++; 6116 if (bb->index >= cfg->x_last_basic_block) 6117 cfg->x_last_basic_block = bb->index + 1; 6118 6119 old_len = VEC_length (basic_block, cfg->x_basic_block_info); 6120 if ((unsigned) cfg->x_last_basic_block >= old_len) 6121 { 6122 new_len = cfg->x_last_basic_block + (cfg->x_last_basic_block + 3) / 4; 6123 VEC_safe_grow_cleared (basic_block, gc, cfg->x_basic_block_info, 6124 new_len); 6125 } 6126 6127 VEC_replace (basic_block, cfg->x_basic_block_info, 6128 bb->index, bb); 6129 6130 /* Remap the variables in phi nodes. */ 6131 for (si = gsi_start_phis (bb); !gsi_end_p (si); ) 6132 { 6133 gimple phi = gsi_stmt (si); 6134 use_operand_p use; 6135 tree op = PHI_RESULT (phi); 6136 ssa_op_iter oi; 6137 6138 if (!is_gimple_reg (op)) 6139 { 6140 /* Remove the phi nodes for virtual operands (alias analysis will be 6141 run for the new function, anyway). */ 6142 remove_phi_node (&si, true); 6143 continue; 6144 } 6145 6146 SET_PHI_RESULT (phi, 6147 replace_ssa_name (op, d->vars_map, dest_cfun->decl)); 6148 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) 6149 { 6150 op = USE_FROM_PTR (use); 6151 if (TREE_CODE (op) == SSA_NAME) 6152 SET_USE (use, replace_ssa_name (op, d->vars_map, dest_cfun->decl)); 6153 } 6154 6155 gsi_next (&si); 6156 } 6157 6158 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 6159 { 6160 gimple stmt = gsi_stmt (si); 6161 struct walk_stmt_info wi; 6162 6163 memset (&wi, 0, sizeof (wi)); 6164 wi.info = d; 6165 walk_gimple_stmt (&si, move_stmt_r, move_stmt_op, &wi); 6166 6167 if (gimple_code (stmt) == GIMPLE_LABEL) 6168 { 6169 tree label = gimple_label_label (stmt); 6170 int uid = LABEL_DECL_UID (label); 6171 6172 gcc_assert (uid > -1); 6173 6174 old_len = VEC_length (basic_block, cfg->x_label_to_block_map); 6175 if (old_len <= (unsigned) uid) 6176 { 6177 new_len = 3 * uid / 2 + 1; 6178 VEC_safe_grow_cleared (basic_block, gc, 6179 cfg->x_label_to_block_map, new_len); 6180 } 6181 6182 VEC_replace (basic_block, cfg->x_label_to_block_map, uid, bb); 6183 VEC_replace (basic_block, cfun->cfg->x_label_to_block_map, uid, NULL); 6184 6185 gcc_assert (DECL_CONTEXT (label) == dest_cfun->decl); 6186 6187 if (uid >= dest_cfun->cfg->last_label_uid) 6188 dest_cfun->cfg->last_label_uid = uid + 1; 6189 } 6190 6191 maybe_duplicate_eh_stmt_fn (dest_cfun, stmt, cfun, stmt, d->eh_map, 0); 6192 remove_stmt_from_eh_lp_fn (cfun, stmt); 6193 6194 gimple_duplicate_stmt_histograms (dest_cfun, stmt, cfun, stmt); 6195 gimple_remove_stmt_histograms (cfun, stmt); 6196 6197 /* We cannot leave any operands allocated from the operand caches of 6198 the current function. */ 6199 free_stmt_operands (stmt); 6200 push_cfun (dest_cfun); 6201 update_stmt (stmt); 6202 pop_cfun (); 6203 } 6204 6205 FOR_EACH_EDGE (e, ei, bb->succs) 6206 if (e->goto_locus) 6207 { 6208 tree block = e->goto_block; 6209 if (d->orig_block == NULL_TREE 6210 || block == d->orig_block) 6211 e->goto_block = d->new_block; 6212 #ifdef ENABLE_CHECKING 6213 else if (block != d->new_block) 6214 { 6215 while (block && block != d->orig_block) 6216 block = BLOCK_SUPERCONTEXT (block); 6217 gcc_assert (block); 6218 } 6219 #endif 6220 } 6221 } 6222 6223 /* Examine the statements in BB (which is in SRC_CFUN); find and return 6224 the outermost EH region. Use REGION as the incoming base EH region. */ 6225 6226 static eh_region 6227 find_outermost_region_in_block (struct function *src_cfun, 6228 basic_block bb, eh_region region) 6229 { 6230 gimple_stmt_iterator si; 6231 6232 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 6233 { 6234 gimple stmt = gsi_stmt (si); 6235 eh_region stmt_region; 6236 int lp_nr; 6237 6238 lp_nr = lookup_stmt_eh_lp_fn (src_cfun, stmt); 6239 stmt_region = get_eh_region_from_lp_number_fn (src_cfun, lp_nr); 6240 if (stmt_region) 6241 { 6242 if (region == NULL) 6243 region = stmt_region; 6244 else if (stmt_region != region) 6245 { 6246 region = eh_region_outermost (src_cfun, stmt_region, region); 6247 gcc_assert (region != NULL); 6248 } 6249 } 6250 } 6251 6252 return region; 6253 } 6254 6255 static tree 6256 new_label_mapper (tree decl, void *data) 6257 { 6258 htab_t hash = (htab_t) data; 6259 struct tree_map *m; 6260 void **slot; 6261 6262 gcc_assert (TREE_CODE (decl) == LABEL_DECL); 6263 6264 m = XNEW (struct tree_map); 6265 m->hash = DECL_UID (decl); 6266 m->base.from = decl; 6267 m->to = create_artificial_label (UNKNOWN_LOCATION); 6268 LABEL_DECL_UID (m->to) = LABEL_DECL_UID (decl); 6269 if (LABEL_DECL_UID (m->to) >= cfun->cfg->last_label_uid) 6270 cfun->cfg->last_label_uid = LABEL_DECL_UID (m->to) + 1; 6271 6272 slot = htab_find_slot_with_hash (hash, m, m->hash, INSERT); 6273 gcc_assert (*slot == NULL); 6274 6275 *slot = m; 6276 6277 return m->to; 6278 } 6279 6280 /* Change DECL_CONTEXT of all BLOCK_VARS in block, including 6281 subblocks. */ 6282 6283 static void 6284 replace_block_vars_by_duplicates (tree block, struct pointer_map_t *vars_map, 6285 tree to_context) 6286 { 6287 tree *tp, t; 6288 6289 for (tp = &BLOCK_VARS (block); *tp; tp = &DECL_CHAIN (*tp)) 6290 { 6291 t = *tp; 6292 if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != CONST_DECL) 6293 continue; 6294 replace_by_duplicate_decl (&t, vars_map, to_context); 6295 if (t != *tp) 6296 { 6297 if (TREE_CODE (*tp) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*tp)) 6298 { 6299 SET_DECL_VALUE_EXPR (t, DECL_VALUE_EXPR (*tp)); 6300 DECL_HAS_VALUE_EXPR_P (t) = 1; 6301 } 6302 DECL_CHAIN (t) = DECL_CHAIN (*tp); 6303 *tp = t; 6304 } 6305 } 6306 6307 for (block = BLOCK_SUBBLOCKS (block); block; block = BLOCK_CHAIN (block)) 6308 replace_block_vars_by_duplicates (block, vars_map, to_context); 6309 } 6310 6311 /* Move a single-entry, single-exit region delimited by ENTRY_BB and 6312 EXIT_BB to function DEST_CFUN. The whole region is replaced by a 6313 single basic block in the original CFG and the new basic block is 6314 returned. DEST_CFUN must not have a CFG yet. 6315 6316 Note that the region need not be a pure SESE region. Blocks inside 6317 the region may contain calls to abort/exit. The only restriction 6318 is that ENTRY_BB should be the only entry point and it must 6319 dominate EXIT_BB. 6320 6321 Change TREE_BLOCK of all statements in ORIG_BLOCK to the new 6322 functions outermost BLOCK, move all subblocks of ORIG_BLOCK 6323 to the new function. 6324 6325 All local variables referenced in the region are assumed to be in 6326 the corresponding BLOCK_VARS and unexpanded variable lists 6327 associated with DEST_CFUN. */ 6328 6329 basic_block 6330 move_sese_region_to_fn (struct function *dest_cfun, basic_block entry_bb, 6331 basic_block exit_bb, tree orig_block) 6332 { 6333 VEC(basic_block,heap) *bbs, *dom_bbs; 6334 basic_block dom_entry = get_immediate_dominator (CDI_DOMINATORS, entry_bb); 6335 basic_block after, bb, *entry_pred, *exit_succ, abb; 6336 struct function *saved_cfun = cfun; 6337 int *entry_flag, *exit_flag; 6338 unsigned *entry_prob, *exit_prob; 6339 unsigned i, num_entry_edges, num_exit_edges; 6340 edge e; 6341 edge_iterator ei; 6342 htab_t new_label_map; 6343 struct pointer_map_t *vars_map, *eh_map; 6344 struct loop *loop = entry_bb->loop_father; 6345 struct move_stmt_d d; 6346 6347 /* If ENTRY does not strictly dominate EXIT, this cannot be an SESE 6348 region. */ 6349 gcc_assert (entry_bb != exit_bb 6350 && (!exit_bb 6351 || dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb))); 6352 6353 /* Collect all the blocks in the region. Manually add ENTRY_BB 6354 because it won't be added by dfs_enumerate_from. */ 6355 bbs = NULL; 6356 VEC_safe_push (basic_block, heap, bbs, entry_bb); 6357 gather_blocks_in_sese_region (entry_bb, exit_bb, &bbs); 6358 6359 /* The blocks that used to be dominated by something in BBS will now be 6360 dominated by the new block. */ 6361 dom_bbs = get_dominated_by_region (CDI_DOMINATORS, 6362 VEC_address (basic_block, bbs), 6363 VEC_length (basic_block, bbs)); 6364 6365 /* Detach ENTRY_BB and EXIT_BB from CFUN->CFG. We need to remember 6366 the predecessor edges to ENTRY_BB and the successor edges to 6367 EXIT_BB so that we can re-attach them to the new basic block that 6368 will replace the region. */ 6369 num_entry_edges = EDGE_COUNT (entry_bb->preds); 6370 entry_pred = (basic_block *) xcalloc (num_entry_edges, sizeof (basic_block)); 6371 entry_flag = (int *) xcalloc (num_entry_edges, sizeof (int)); 6372 entry_prob = XNEWVEC (unsigned, num_entry_edges); 6373 i = 0; 6374 for (ei = ei_start (entry_bb->preds); (e = ei_safe_edge (ei)) != NULL;) 6375 { 6376 entry_prob[i] = e->probability; 6377 entry_flag[i] = e->flags; 6378 entry_pred[i++] = e->src; 6379 remove_edge (e); 6380 } 6381 6382 if (exit_bb) 6383 { 6384 num_exit_edges = EDGE_COUNT (exit_bb->succs); 6385 exit_succ = (basic_block *) xcalloc (num_exit_edges, 6386 sizeof (basic_block)); 6387 exit_flag = (int *) xcalloc (num_exit_edges, sizeof (int)); 6388 exit_prob = XNEWVEC (unsigned, num_exit_edges); 6389 i = 0; 6390 for (ei = ei_start (exit_bb->succs); (e = ei_safe_edge (ei)) != NULL;) 6391 { 6392 exit_prob[i] = e->probability; 6393 exit_flag[i] = e->flags; 6394 exit_succ[i++] = e->dest; 6395 remove_edge (e); 6396 } 6397 } 6398 else 6399 { 6400 num_exit_edges = 0; 6401 exit_succ = NULL; 6402 exit_flag = NULL; 6403 exit_prob = NULL; 6404 } 6405 6406 /* Switch context to the child function to initialize DEST_FN's CFG. */ 6407 gcc_assert (dest_cfun->cfg == NULL); 6408 push_cfun (dest_cfun); 6409 6410 init_empty_tree_cfg (); 6411 6412 /* Initialize EH information for the new function. */ 6413 eh_map = NULL; 6414 new_label_map = NULL; 6415 if (saved_cfun->eh) 6416 { 6417 eh_region region = NULL; 6418 6419 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) 6420 region = find_outermost_region_in_block (saved_cfun, bb, region); 6421 6422 init_eh_for_function (); 6423 if (region != NULL) 6424 { 6425 new_label_map = htab_create (17, tree_map_hash, tree_map_eq, free); 6426 eh_map = duplicate_eh_regions (saved_cfun, region, 0, 6427 new_label_mapper, new_label_map); 6428 } 6429 } 6430 6431 pop_cfun (); 6432 6433 /* Move blocks from BBS into DEST_CFUN. */ 6434 gcc_assert (VEC_length (basic_block, bbs) >= 2); 6435 after = dest_cfun->cfg->x_entry_block_ptr; 6436 vars_map = pointer_map_create (); 6437 6438 memset (&d, 0, sizeof (d)); 6439 d.orig_block = orig_block; 6440 d.new_block = DECL_INITIAL (dest_cfun->decl); 6441 d.from_context = cfun->decl; 6442 d.to_context = dest_cfun->decl; 6443 d.vars_map = vars_map; 6444 d.new_label_map = new_label_map; 6445 d.eh_map = eh_map; 6446 d.remap_decls_p = true; 6447 6448 FOR_EACH_VEC_ELT (basic_block, bbs, i, bb) 6449 { 6450 /* No need to update edge counts on the last block. It has 6451 already been updated earlier when we detached the region from 6452 the original CFG. */ 6453 move_block_to_fn (dest_cfun, bb, after, bb != exit_bb, &d); 6454 after = bb; 6455 } 6456 6457 /* Rewire BLOCK_SUBBLOCKS of orig_block. */ 6458 if (orig_block) 6459 { 6460 tree block; 6461 gcc_assert (BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl)) 6462 == NULL_TREE); 6463 BLOCK_SUBBLOCKS (DECL_INITIAL (dest_cfun->decl)) 6464 = BLOCK_SUBBLOCKS (orig_block); 6465 for (block = BLOCK_SUBBLOCKS (orig_block); 6466 block; block = BLOCK_CHAIN (block)) 6467 BLOCK_SUPERCONTEXT (block) = DECL_INITIAL (dest_cfun->decl); 6468 BLOCK_SUBBLOCKS (orig_block) = NULL_TREE; 6469 } 6470 6471 replace_block_vars_by_duplicates (DECL_INITIAL (dest_cfun->decl), 6472 vars_map, dest_cfun->decl); 6473 6474 if (new_label_map) 6475 htab_delete (new_label_map); 6476 if (eh_map) 6477 pointer_map_destroy (eh_map); 6478 pointer_map_destroy (vars_map); 6479 6480 /* Rewire the entry and exit blocks. The successor to the entry 6481 block turns into the successor of DEST_FN's ENTRY_BLOCK_PTR in 6482 the child function. Similarly, the predecessor of DEST_FN's 6483 EXIT_BLOCK_PTR turns into the predecessor of EXIT_BLOCK_PTR. We 6484 need to switch CFUN between DEST_CFUN and SAVED_CFUN so that the 6485 various CFG manipulation function get to the right CFG. 6486 6487 FIXME, this is silly. The CFG ought to become a parameter to 6488 these helpers. */ 6489 push_cfun (dest_cfun); 6490 make_edge (ENTRY_BLOCK_PTR, entry_bb, EDGE_FALLTHRU); 6491 if (exit_bb) 6492 make_edge (exit_bb, EXIT_BLOCK_PTR, 0); 6493 pop_cfun (); 6494 6495 /* Back in the original function, the SESE region has disappeared, 6496 create a new basic block in its place. */ 6497 bb = create_empty_bb (entry_pred[0]); 6498 if (current_loops) 6499 add_bb_to_loop (bb, loop); 6500 for (i = 0; i < num_entry_edges; i++) 6501 { 6502 e = make_edge (entry_pred[i], bb, entry_flag[i]); 6503 e->probability = entry_prob[i]; 6504 } 6505 6506 for (i = 0; i < num_exit_edges; i++) 6507 { 6508 e = make_edge (bb, exit_succ[i], exit_flag[i]); 6509 e->probability = exit_prob[i]; 6510 } 6511 6512 set_immediate_dominator (CDI_DOMINATORS, bb, dom_entry); 6513 FOR_EACH_VEC_ELT (basic_block, dom_bbs, i, abb) 6514 set_immediate_dominator (CDI_DOMINATORS, abb, bb); 6515 VEC_free (basic_block, heap, dom_bbs); 6516 6517 if (exit_bb) 6518 { 6519 free (exit_prob); 6520 free (exit_flag); 6521 free (exit_succ); 6522 } 6523 free (entry_prob); 6524 free (entry_flag); 6525 free (entry_pred); 6526 VEC_free (basic_block, heap, bbs); 6527 6528 return bb; 6529 } 6530 6531 6532 /* Dump FUNCTION_DECL FN to file FILE using FLAGS (see TDF_* in tree-pass.h) 6533 */ 6534 6535 void 6536 dump_function_to_file (tree fn, FILE *file, int flags) 6537 { 6538 tree arg, var; 6539 struct function *dsf; 6540 bool ignore_topmost_bind = false, any_var = false; 6541 basic_block bb; 6542 tree chain; 6543 bool tmclone = TREE_CODE (fn) == FUNCTION_DECL && decl_is_tm_clone (fn); 6544 6545 fprintf (file, "%s %s(", lang_hooks.decl_printable_name (fn, 2), 6546 tmclone ? "[tm-clone] " : ""); 6547 6548 arg = DECL_ARGUMENTS (fn); 6549 while (arg) 6550 { 6551 print_generic_expr (file, TREE_TYPE (arg), dump_flags); 6552 fprintf (file, " "); 6553 print_generic_expr (file, arg, dump_flags); 6554 if (flags & TDF_VERBOSE) 6555 print_node (file, "", arg, 4); 6556 if (DECL_CHAIN (arg)) 6557 fprintf (file, ", "); 6558 arg = DECL_CHAIN (arg); 6559 } 6560 fprintf (file, ")\n"); 6561 6562 if (flags & TDF_VERBOSE) 6563 print_node (file, "", fn, 2); 6564 6565 dsf = DECL_STRUCT_FUNCTION (fn); 6566 if (dsf && (flags & TDF_EH)) 6567 dump_eh_tree (file, dsf); 6568 6569 if (flags & TDF_RAW && !gimple_has_body_p (fn)) 6570 { 6571 dump_node (fn, TDF_SLIM | flags, file); 6572 return; 6573 } 6574 6575 /* Switch CFUN to point to FN. */ 6576 push_cfun (DECL_STRUCT_FUNCTION (fn)); 6577 6578 /* When GIMPLE is lowered, the variables are no longer available in 6579 BIND_EXPRs, so display them separately. */ 6580 if (cfun && cfun->decl == fn && !VEC_empty (tree, cfun->local_decls)) 6581 { 6582 unsigned ix; 6583 ignore_topmost_bind = true; 6584 6585 fprintf (file, "{\n"); 6586 FOR_EACH_LOCAL_DECL (cfun, ix, var) 6587 { 6588 print_generic_decl (file, var, flags); 6589 if (flags & TDF_VERBOSE) 6590 print_node (file, "", var, 4); 6591 fprintf (file, "\n"); 6592 6593 any_var = true; 6594 } 6595 } 6596 6597 if (cfun && cfun->decl == fn && cfun->cfg && basic_block_info) 6598 { 6599 /* If the CFG has been built, emit a CFG-based dump. */ 6600 check_bb_profile (ENTRY_BLOCK_PTR, file); 6601 if (!ignore_topmost_bind) 6602 fprintf (file, "{\n"); 6603 6604 if (any_var && n_basic_blocks) 6605 fprintf (file, "\n"); 6606 6607 FOR_EACH_BB (bb) 6608 gimple_dump_bb (bb, file, 2, flags); 6609 6610 fprintf (file, "}\n"); 6611 check_bb_profile (EXIT_BLOCK_PTR, file); 6612 } 6613 else if (DECL_SAVED_TREE (fn) == NULL) 6614 { 6615 /* The function is now in GIMPLE form but the CFG has not been 6616 built yet. Emit the single sequence of GIMPLE statements 6617 that make up its body. */ 6618 gimple_seq body = gimple_body (fn); 6619 6620 if (gimple_seq_first_stmt (body) 6621 && gimple_seq_first_stmt (body) == gimple_seq_last_stmt (body) 6622 && gimple_code (gimple_seq_first_stmt (body)) == GIMPLE_BIND) 6623 print_gimple_seq (file, body, 0, flags); 6624 else 6625 { 6626 if (!ignore_topmost_bind) 6627 fprintf (file, "{\n"); 6628 6629 if (any_var) 6630 fprintf (file, "\n"); 6631 6632 print_gimple_seq (file, body, 2, flags); 6633 fprintf (file, "}\n"); 6634 } 6635 } 6636 else 6637 { 6638 int indent; 6639 6640 /* Make a tree based dump. */ 6641 chain = DECL_SAVED_TREE (fn); 6642 6643 if (chain && TREE_CODE (chain) == BIND_EXPR) 6644 { 6645 if (ignore_topmost_bind) 6646 { 6647 chain = BIND_EXPR_BODY (chain); 6648 indent = 2; 6649 } 6650 else 6651 indent = 0; 6652 } 6653 else 6654 { 6655 if (!ignore_topmost_bind) 6656 fprintf (file, "{\n"); 6657 indent = 2; 6658 } 6659 6660 if (any_var) 6661 fprintf (file, "\n"); 6662 6663 print_generic_stmt_indented (file, chain, flags, indent); 6664 if (ignore_topmost_bind) 6665 fprintf (file, "}\n"); 6666 } 6667 6668 if (flags & TDF_ENUMERATE_LOCALS) 6669 dump_enumerated_decls (file, flags); 6670 fprintf (file, "\n\n"); 6671 6672 /* Restore CFUN. */ 6673 pop_cfun (); 6674 } 6675 6676 6677 /* Dump FUNCTION_DECL FN to stderr using FLAGS (see TDF_* in tree.h) */ 6678 6679 DEBUG_FUNCTION void 6680 debug_function (tree fn, int flags) 6681 { 6682 dump_function_to_file (fn, stderr, flags); 6683 } 6684 6685 6686 /* Print on FILE the indexes for the predecessors of basic_block BB. */ 6687 6688 static void 6689 print_pred_bbs (FILE *file, basic_block bb) 6690 { 6691 edge e; 6692 edge_iterator ei; 6693 6694 FOR_EACH_EDGE (e, ei, bb->preds) 6695 fprintf (file, "bb_%d ", e->src->index); 6696 } 6697 6698 6699 /* Print on FILE the indexes for the successors of basic_block BB. */ 6700 6701 static void 6702 print_succ_bbs (FILE *file, basic_block bb) 6703 { 6704 edge e; 6705 edge_iterator ei; 6706 6707 FOR_EACH_EDGE (e, ei, bb->succs) 6708 fprintf (file, "bb_%d ", e->dest->index); 6709 } 6710 6711 /* Print to FILE the basic block BB following the VERBOSITY level. */ 6712 6713 void 6714 print_loops_bb (FILE *file, basic_block bb, int indent, int verbosity) 6715 { 6716 char *s_indent = (char *) alloca ((size_t) indent + 1); 6717 memset ((void *) s_indent, ' ', (size_t) indent); 6718 s_indent[indent] = '\0'; 6719 6720 /* Print basic_block's header. */ 6721 if (verbosity >= 2) 6722 { 6723 fprintf (file, "%s bb_%d (preds = {", s_indent, bb->index); 6724 print_pred_bbs (file, bb); 6725 fprintf (file, "}, succs = {"); 6726 print_succ_bbs (file, bb); 6727 fprintf (file, "})\n"); 6728 } 6729 6730 /* Print basic_block's body. */ 6731 if (verbosity >= 3) 6732 { 6733 fprintf (file, "%s {\n", s_indent); 6734 gimple_dump_bb (bb, file, indent + 4, TDF_VOPS|TDF_MEMSYMS); 6735 fprintf (file, "%s }\n", s_indent); 6736 } 6737 } 6738 6739 static void print_loop_and_siblings (FILE *, struct loop *, int, int); 6740 6741 /* Pretty print LOOP on FILE, indented INDENT spaces. Following 6742 VERBOSITY level this outputs the contents of the loop, or just its 6743 structure. */ 6744 6745 static void 6746 print_loop (FILE *file, struct loop *loop, int indent, int verbosity) 6747 { 6748 char *s_indent; 6749 basic_block bb; 6750 6751 if (loop == NULL) 6752 return; 6753 6754 s_indent = (char *) alloca ((size_t) indent + 1); 6755 memset ((void *) s_indent, ' ', (size_t) indent); 6756 s_indent[indent] = '\0'; 6757 6758 /* Print loop's header. */ 6759 fprintf (file, "%sloop_%d (header = %d, latch = %d", s_indent, 6760 loop->num, loop->header->index, loop->latch->index); 6761 fprintf (file, ", niter = "); 6762 print_generic_expr (file, loop->nb_iterations, 0); 6763 6764 if (loop->any_upper_bound) 6765 { 6766 fprintf (file, ", upper_bound = "); 6767 dump_double_int (file, loop->nb_iterations_upper_bound, true); 6768 } 6769 6770 if (loop->any_estimate) 6771 { 6772 fprintf (file, ", estimate = "); 6773 dump_double_int (file, loop->nb_iterations_estimate, true); 6774 } 6775 fprintf (file, ")\n"); 6776 6777 /* Print loop's body. */ 6778 if (verbosity >= 1) 6779 { 6780 fprintf (file, "%s{\n", s_indent); 6781 FOR_EACH_BB (bb) 6782 if (bb->loop_father == loop) 6783 print_loops_bb (file, bb, indent, verbosity); 6784 6785 print_loop_and_siblings (file, loop->inner, indent + 2, verbosity); 6786 fprintf (file, "%s}\n", s_indent); 6787 } 6788 } 6789 6790 /* Print the LOOP and its sibling loops on FILE, indented INDENT 6791 spaces. Following VERBOSITY level this outputs the contents of the 6792 loop, or just its structure. */ 6793 6794 static void 6795 print_loop_and_siblings (FILE *file, struct loop *loop, int indent, int verbosity) 6796 { 6797 if (loop == NULL) 6798 return; 6799 6800 print_loop (file, loop, indent, verbosity); 6801 print_loop_and_siblings (file, loop->next, indent, verbosity); 6802 } 6803 6804 /* Follow a CFG edge from the entry point of the program, and on entry 6805 of a loop, pretty print the loop structure on FILE. */ 6806 6807 void 6808 print_loops (FILE *file, int verbosity) 6809 { 6810 basic_block bb; 6811 6812 bb = ENTRY_BLOCK_PTR; 6813 if (bb && bb->loop_father) 6814 print_loop_and_siblings (file, bb->loop_father, 0, verbosity); 6815 } 6816 6817 6818 /* Debugging loops structure at tree level, at some VERBOSITY level. */ 6819 6820 DEBUG_FUNCTION void 6821 debug_loops (int verbosity) 6822 { 6823 print_loops (stderr, verbosity); 6824 } 6825 6826 /* Print on stderr the code of LOOP, at some VERBOSITY level. */ 6827 6828 DEBUG_FUNCTION void 6829 debug_loop (struct loop *loop, int verbosity) 6830 { 6831 print_loop (stderr, loop, 0, verbosity); 6832 } 6833 6834 /* Print on stderr the code of loop number NUM, at some VERBOSITY 6835 level. */ 6836 6837 DEBUG_FUNCTION void 6838 debug_loop_num (unsigned num, int verbosity) 6839 { 6840 debug_loop (get_loop (num), verbosity); 6841 } 6842 6843 /* Return true if BB ends with a call, possibly followed by some 6844 instructions that must stay with the call. Return false, 6845 otherwise. */ 6846 6847 static bool 6848 gimple_block_ends_with_call_p (basic_block bb) 6849 { 6850 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); 6851 return !gsi_end_p (gsi) && is_gimple_call (gsi_stmt (gsi)); 6852 } 6853 6854 6855 /* Return true if BB ends with a conditional branch. Return false, 6856 otherwise. */ 6857 6858 static bool 6859 gimple_block_ends_with_condjump_p (const_basic_block bb) 6860 { 6861 gimple stmt = last_stmt (CONST_CAST_BB (bb)); 6862 return (stmt && gimple_code (stmt) == GIMPLE_COND); 6863 } 6864 6865 6866 /* Return true if we need to add fake edge to exit at statement T. 6867 Helper function for gimple_flow_call_edges_add. */ 6868 6869 static bool 6870 need_fake_edge_p (gimple t) 6871 { 6872 tree fndecl = NULL_TREE; 6873 int call_flags = 0; 6874 6875 /* NORETURN and LONGJMP calls already have an edge to exit. 6876 CONST and PURE calls do not need one. 6877 We don't currently check for CONST and PURE here, although 6878 it would be a good idea, because those attributes are 6879 figured out from the RTL in mark_constant_function, and 6880 the counter incrementation code from -fprofile-arcs 6881 leads to different results from -fbranch-probabilities. */ 6882 if (is_gimple_call (t)) 6883 { 6884 fndecl = gimple_call_fndecl (t); 6885 call_flags = gimple_call_flags (t); 6886 } 6887 6888 if (is_gimple_call (t) 6889 && fndecl 6890 && DECL_BUILT_IN (fndecl) 6891 && (call_flags & ECF_NOTHROW) 6892 && !(call_flags & ECF_RETURNS_TWICE) 6893 /* fork() doesn't really return twice, but the effect of 6894 wrapping it in __gcov_fork() which calls __gcov_flush() 6895 and clears the counters before forking has the same 6896 effect as returning twice. Force a fake edge. */ 6897 && !(DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL 6898 && DECL_FUNCTION_CODE (fndecl) == BUILT_IN_FORK)) 6899 return false; 6900 6901 if (is_gimple_call (t)) 6902 { 6903 edge_iterator ei; 6904 edge e; 6905 basic_block bb; 6906 6907 if (!(call_flags & ECF_NORETURN)) 6908 return true; 6909 6910 bb = gimple_bb (t); 6911 FOR_EACH_EDGE (e, ei, bb->succs) 6912 if ((e->flags & EDGE_FAKE) == 0) 6913 return true; 6914 } 6915 6916 if (gimple_code (t) == GIMPLE_ASM 6917 && (gimple_asm_volatile_p (t) || gimple_asm_input_p (t))) 6918 return true; 6919 6920 return false; 6921 } 6922 6923 6924 /* Add fake edges to the function exit for any non constant and non 6925 noreturn calls (or noreturn calls with EH/abnormal edges), 6926 volatile inline assembly in the bitmap of blocks specified by BLOCKS 6927 or to the whole CFG if BLOCKS is zero. Return the number of blocks 6928 that were split. 6929 6930 The goal is to expose cases in which entering a basic block does 6931 not imply that all subsequent instructions must be executed. */ 6932 6933 static int 6934 gimple_flow_call_edges_add (sbitmap blocks) 6935 { 6936 int i; 6937 int blocks_split = 0; 6938 int last_bb = last_basic_block; 6939 bool check_last_block = false; 6940 6941 if (n_basic_blocks == NUM_FIXED_BLOCKS) 6942 return 0; 6943 6944 if (! blocks) 6945 check_last_block = true; 6946 else 6947 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index); 6948 6949 /* In the last basic block, before epilogue generation, there will be 6950 a fallthru edge to EXIT. Special care is required if the last insn 6951 of the last basic block is a call because make_edge folds duplicate 6952 edges, which would result in the fallthru edge also being marked 6953 fake, which would result in the fallthru edge being removed by 6954 remove_fake_edges, which would result in an invalid CFG. 6955 6956 Moreover, we can't elide the outgoing fake edge, since the block 6957 profiler needs to take this into account in order to solve the minimal 6958 spanning tree in the case that the call doesn't return. 6959 6960 Handle this by adding a dummy instruction in a new last basic block. */ 6961 if (check_last_block) 6962 { 6963 basic_block bb = EXIT_BLOCK_PTR->prev_bb; 6964 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb); 6965 gimple t = NULL; 6966 6967 if (!gsi_end_p (gsi)) 6968 t = gsi_stmt (gsi); 6969 6970 if (t && need_fake_edge_p (t)) 6971 { 6972 edge e; 6973 6974 e = find_edge (bb, EXIT_BLOCK_PTR); 6975 if (e) 6976 { 6977 gsi_insert_on_edge (e, gimple_build_nop ()); 6978 gsi_commit_edge_inserts (); 6979 } 6980 } 6981 } 6982 6983 /* Now add fake edges to the function exit for any non constant 6984 calls since there is no way that we can determine if they will 6985 return or not... */ 6986 for (i = 0; i < last_bb; i++) 6987 { 6988 basic_block bb = BASIC_BLOCK (i); 6989 gimple_stmt_iterator gsi; 6990 gimple stmt, last_stmt; 6991 6992 if (!bb) 6993 continue; 6994 6995 if (blocks && !TEST_BIT (blocks, i)) 6996 continue; 6997 6998 gsi = gsi_last_nondebug_bb (bb); 6999 if (!gsi_end_p (gsi)) 7000 { 7001 last_stmt = gsi_stmt (gsi); 7002 do 7003 { 7004 stmt = gsi_stmt (gsi); 7005 if (need_fake_edge_p (stmt)) 7006 { 7007 edge e; 7008 7009 /* The handling above of the final block before the 7010 epilogue should be enough to verify that there is 7011 no edge to the exit block in CFG already. 7012 Calling make_edge in such case would cause us to 7013 mark that edge as fake and remove it later. */ 7014 #ifdef ENABLE_CHECKING 7015 if (stmt == last_stmt) 7016 { 7017 e = find_edge (bb, EXIT_BLOCK_PTR); 7018 gcc_assert (e == NULL); 7019 } 7020 #endif 7021 7022 /* Note that the following may create a new basic block 7023 and renumber the existing basic blocks. */ 7024 if (stmt != last_stmt) 7025 { 7026 e = split_block (bb, stmt); 7027 if (e) 7028 blocks_split++; 7029 } 7030 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE); 7031 } 7032 gsi_prev (&gsi); 7033 } 7034 while (!gsi_end_p (gsi)); 7035 } 7036 } 7037 7038 if (blocks_split) 7039 verify_flow_info (); 7040 7041 return blocks_split; 7042 } 7043 7044 /* Removes edge E and all the blocks dominated by it, and updates dominance 7045 information. The IL in E->src needs to be updated separately. 7046 If dominance info is not available, only the edge E is removed.*/ 7047 7048 void 7049 remove_edge_and_dominated_blocks (edge e) 7050 { 7051 VEC (basic_block, heap) *bbs_to_remove = NULL; 7052 VEC (basic_block, heap) *bbs_to_fix_dom = NULL; 7053 bitmap df, df_idom; 7054 edge f; 7055 edge_iterator ei; 7056 bool none_removed = false; 7057 unsigned i; 7058 basic_block bb, dbb; 7059 bitmap_iterator bi; 7060 7061 if (!dom_info_available_p (CDI_DOMINATORS)) 7062 { 7063 remove_edge (e); 7064 return; 7065 } 7066 7067 /* No updating is needed for edges to exit. */ 7068 if (e->dest == EXIT_BLOCK_PTR) 7069 { 7070 if (cfgcleanup_altered_bbs) 7071 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index); 7072 remove_edge (e); 7073 return; 7074 } 7075 7076 /* First, we find the basic blocks to remove. If E->dest has a predecessor 7077 that is not dominated by E->dest, then this set is empty. Otherwise, 7078 all the basic blocks dominated by E->dest are removed. 7079 7080 Also, to DF_IDOM we store the immediate dominators of the blocks in 7081 the dominance frontier of E (i.e., of the successors of the 7082 removed blocks, if there are any, and of E->dest otherwise). */ 7083 FOR_EACH_EDGE (f, ei, e->dest->preds) 7084 { 7085 if (f == e) 7086 continue; 7087 7088 if (!dominated_by_p (CDI_DOMINATORS, f->src, e->dest)) 7089 { 7090 none_removed = true; 7091 break; 7092 } 7093 } 7094 7095 df = BITMAP_ALLOC (NULL); 7096 df_idom = BITMAP_ALLOC (NULL); 7097 7098 if (none_removed) 7099 bitmap_set_bit (df_idom, 7100 get_immediate_dominator (CDI_DOMINATORS, e->dest)->index); 7101 else 7102 { 7103 bbs_to_remove = get_all_dominated_blocks (CDI_DOMINATORS, e->dest); 7104 FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb) 7105 { 7106 FOR_EACH_EDGE (f, ei, bb->succs) 7107 { 7108 if (f->dest != EXIT_BLOCK_PTR) 7109 bitmap_set_bit (df, f->dest->index); 7110 } 7111 } 7112 FOR_EACH_VEC_ELT (basic_block, bbs_to_remove, i, bb) 7113 bitmap_clear_bit (df, bb->index); 7114 7115 EXECUTE_IF_SET_IN_BITMAP (df, 0, i, bi) 7116 { 7117 bb = BASIC_BLOCK (i); 7118 bitmap_set_bit (df_idom, 7119 get_immediate_dominator (CDI_DOMINATORS, bb)->index); 7120 } 7121 } 7122 7123 if (cfgcleanup_altered_bbs) 7124 { 7125 /* Record the set of the altered basic blocks. */ 7126 bitmap_set_bit (cfgcleanup_altered_bbs, e->src->index); 7127 bitmap_ior_into (cfgcleanup_altered_bbs, df); 7128 } 7129 7130 /* Remove E and the cancelled blocks. */ 7131 if (none_removed) 7132 remove_edge (e); 7133 else 7134 { 7135 /* Walk backwards so as to get a chance to substitute all 7136 released DEFs into debug stmts. See 7137 eliminate_unnecessary_stmts() in tree-ssa-dce.c for more 7138 details. */ 7139 for (i = VEC_length (basic_block, bbs_to_remove); i-- > 0; ) 7140 delete_basic_block (VEC_index (basic_block, bbs_to_remove, i)); 7141 } 7142 7143 /* Update the dominance information. The immediate dominator may change only 7144 for blocks whose immediate dominator belongs to DF_IDOM: 7145 7146 Suppose that idom(X) = Y before removal of E and idom(X) != Y after the 7147 removal. Let Z the arbitrary block such that idom(Z) = Y and 7148 Z dominates X after the removal. Before removal, there exists a path P 7149 from Y to X that avoids Z. Let F be the last edge on P that is 7150 removed, and let W = F->dest. Before removal, idom(W) = Y (since Y 7151 dominates W, and because of P, Z does not dominate W), and W belongs to 7152 the dominance frontier of E. Therefore, Y belongs to DF_IDOM. */ 7153 EXECUTE_IF_SET_IN_BITMAP (df_idom, 0, i, bi) 7154 { 7155 bb = BASIC_BLOCK (i); 7156 for (dbb = first_dom_son (CDI_DOMINATORS, bb); 7157 dbb; 7158 dbb = next_dom_son (CDI_DOMINATORS, dbb)) 7159 VEC_safe_push (basic_block, heap, bbs_to_fix_dom, dbb); 7160 } 7161 7162 iterate_fix_dominators (CDI_DOMINATORS, bbs_to_fix_dom, true); 7163 7164 BITMAP_FREE (df); 7165 BITMAP_FREE (df_idom); 7166 VEC_free (basic_block, heap, bbs_to_remove); 7167 VEC_free (basic_block, heap, bbs_to_fix_dom); 7168 } 7169 7170 /* Purge dead EH edges from basic block BB. */ 7171 7172 bool 7173 gimple_purge_dead_eh_edges (basic_block bb) 7174 { 7175 bool changed = false; 7176 edge e; 7177 edge_iterator ei; 7178 gimple stmt = last_stmt (bb); 7179 7180 if (stmt && stmt_can_throw_internal (stmt)) 7181 return false; 7182 7183 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 7184 { 7185 if (e->flags & EDGE_EH) 7186 { 7187 remove_edge_and_dominated_blocks (e); 7188 changed = true; 7189 } 7190 else 7191 ei_next (&ei); 7192 } 7193 7194 return changed; 7195 } 7196 7197 /* Purge dead EH edges from basic block listed in BLOCKS. */ 7198 7199 bool 7200 gimple_purge_all_dead_eh_edges (const_bitmap blocks) 7201 { 7202 bool changed = false; 7203 unsigned i; 7204 bitmap_iterator bi; 7205 7206 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 7207 { 7208 basic_block bb = BASIC_BLOCK (i); 7209 7210 /* Earlier gimple_purge_dead_eh_edges could have removed 7211 this basic block already. */ 7212 gcc_assert (bb || changed); 7213 if (bb != NULL) 7214 changed |= gimple_purge_dead_eh_edges (bb); 7215 } 7216 7217 return changed; 7218 } 7219 7220 /* Purge dead abnormal call edges from basic block BB. */ 7221 7222 bool 7223 gimple_purge_dead_abnormal_call_edges (basic_block bb) 7224 { 7225 bool changed = false; 7226 edge e; 7227 edge_iterator ei; 7228 gimple stmt = last_stmt (bb); 7229 7230 if (!cfun->has_nonlocal_label) 7231 return false; 7232 7233 if (stmt && stmt_can_make_abnormal_goto (stmt)) 7234 return false; 7235 7236 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ) 7237 { 7238 if (e->flags & EDGE_ABNORMAL) 7239 { 7240 remove_edge_and_dominated_blocks (e); 7241 changed = true; 7242 } 7243 else 7244 ei_next (&ei); 7245 } 7246 7247 return changed; 7248 } 7249 7250 /* Purge dead abnormal call edges from basic block listed in BLOCKS. */ 7251 7252 bool 7253 gimple_purge_all_dead_abnormal_call_edges (const_bitmap blocks) 7254 { 7255 bool changed = false; 7256 unsigned i; 7257 bitmap_iterator bi; 7258 7259 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i, bi) 7260 { 7261 basic_block bb = BASIC_BLOCK (i); 7262 7263 /* Earlier gimple_purge_dead_abnormal_call_edges could have removed 7264 this basic block already. */ 7265 gcc_assert (bb || changed); 7266 if (bb != NULL) 7267 changed |= gimple_purge_dead_abnormal_call_edges (bb); 7268 } 7269 7270 return changed; 7271 } 7272 7273 /* This function is called whenever a new edge is created or 7274 redirected. */ 7275 7276 static void 7277 gimple_execute_on_growing_pred (edge e) 7278 { 7279 basic_block bb = e->dest; 7280 7281 if (!gimple_seq_empty_p (phi_nodes (bb))) 7282 reserve_phi_args_for_new_edge (bb); 7283 } 7284 7285 /* This function is called immediately before edge E is removed from 7286 the edge vector E->dest->preds. */ 7287 7288 static void 7289 gimple_execute_on_shrinking_pred (edge e) 7290 { 7291 if (!gimple_seq_empty_p (phi_nodes (e->dest))) 7292 remove_phi_args (e); 7293 } 7294 7295 /*--------------------------------------------------------------------------- 7296 Helper functions for Loop versioning 7297 ---------------------------------------------------------------------------*/ 7298 7299 /* Adjust phi nodes for 'first' basic block. 'second' basic block is a copy 7300 of 'first'. Both of them are dominated by 'new_head' basic block. When 7301 'new_head' was created by 'second's incoming edge it received phi arguments 7302 on the edge by split_edge(). Later, additional edge 'e' was created to 7303 connect 'new_head' and 'first'. Now this routine adds phi args on this 7304 additional edge 'e' that new_head to second edge received as part of edge 7305 splitting. */ 7306 7307 static void 7308 gimple_lv_adjust_loop_header_phi (basic_block first, basic_block second, 7309 basic_block new_head, edge e) 7310 { 7311 gimple phi1, phi2; 7312 gimple_stmt_iterator psi1, psi2; 7313 tree def; 7314 edge e2 = find_edge (new_head, second); 7315 7316 /* Because NEW_HEAD has been created by splitting SECOND's incoming 7317 edge, we should always have an edge from NEW_HEAD to SECOND. */ 7318 gcc_assert (e2 != NULL); 7319 7320 /* Browse all 'second' basic block phi nodes and add phi args to 7321 edge 'e' for 'first' head. PHI args are always in correct order. */ 7322 7323 for (psi2 = gsi_start_phis (second), 7324 psi1 = gsi_start_phis (first); 7325 !gsi_end_p (psi2) && !gsi_end_p (psi1); 7326 gsi_next (&psi2), gsi_next (&psi1)) 7327 { 7328 phi1 = gsi_stmt (psi1); 7329 phi2 = gsi_stmt (psi2); 7330 def = PHI_ARG_DEF (phi2, e2->dest_idx); 7331 add_phi_arg (phi1, def, e, gimple_phi_arg_location_from_edge (phi2, e2)); 7332 } 7333 } 7334 7335 7336 /* Adds a if else statement to COND_BB with condition COND_EXPR. 7337 SECOND_HEAD is the destination of the THEN and FIRST_HEAD is 7338 the destination of the ELSE part. */ 7339 7340 static void 7341 gimple_lv_add_condition_to_bb (basic_block first_head ATTRIBUTE_UNUSED, 7342 basic_block second_head ATTRIBUTE_UNUSED, 7343 basic_block cond_bb, void *cond_e) 7344 { 7345 gimple_stmt_iterator gsi; 7346 gimple new_cond_expr; 7347 tree cond_expr = (tree) cond_e; 7348 edge e0; 7349 7350 /* Build new conditional expr */ 7351 new_cond_expr = gimple_build_cond_from_tree (cond_expr, 7352 NULL_TREE, NULL_TREE); 7353 7354 /* Add new cond in cond_bb. */ 7355 gsi = gsi_last_bb (cond_bb); 7356 gsi_insert_after (&gsi, new_cond_expr, GSI_NEW_STMT); 7357 7358 /* Adjust edges appropriately to connect new head with first head 7359 as well as second head. */ 7360 e0 = single_succ_edge (cond_bb); 7361 e0->flags &= ~EDGE_FALLTHRU; 7362 e0->flags |= EDGE_FALSE_VALUE; 7363 } 7364 7365 struct cfg_hooks gimple_cfg_hooks = { 7366 "gimple", 7367 gimple_verify_flow_info, 7368 gimple_dump_bb, /* dump_bb */ 7369 create_bb, /* create_basic_block */ 7370 gimple_redirect_edge_and_branch, /* redirect_edge_and_branch */ 7371 gimple_redirect_edge_and_branch_force, /* redirect_edge_and_branch_force */ 7372 gimple_can_remove_branch_p, /* can_remove_branch_p */ 7373 remove_bb, /* delete_basic_block */ 7374 gimple_split_block, /* split_block */ 7375 gimple_move_block_after, /* move_block_after */ 7376 gimple_can_merge_blocks_p, /* can_merge_blocks_p */ 7377 gimple_merge_blocks, /* merge_blocks */ 7378 gimple_predict_edge, /* predict_edge */ 7379 gimple_predicted_by_p, /* predicted_by_p */ 7380 gimple_can_duplicate_bb_p, /* can_duplicate_block_p */ 7381 gimple_duplicate_bb, /* duplicate_block */ 7382 gimple_split_edge, /* split_edge */ 7383 gimple_make_forwarder_block, /* make_forward_block */ 7384 NULL, /* tidy_fallthru_edge */ 7385 NULL, /* force_nonfallthru */ 7386 gimple_block_ends_with_call_p,/* block_ends_with_call_p */ 7387 gimple_block_ends_with_condjump_p, /* block_ends_with_condjump_p */ 7388 gimple_flow_call_edges_add, /* flow_call_edges_add */ 7389 gimple_execute_on_growing_pred, /* execute_on_growing_pred */ 7390 gimple_execute_on_shrinking_pred, /* execute_on_shrinking_pred */ 7391 gimple_duplicate_loop_to_header_edge, /* duplicate loop for trees */ 7392 gimple_lv_add_condition_to_bb, /* lv_add_condition_to_bb */ 7393 gimple_lv_adjust_loop_header_phi, /* lv_adjust_loop_header_phi*/ 7394 extract_true_false_edges_from_block, /* extract_cond_bb_edges */ 7395 flush_pending_stmts /* flush_pending_stmts */ 7396 }; 7397 7398 7399 /* Split all critical edges. */ 7400 7401 unsigned int 7402 split_critical_edges (void) 7403 { 7404 basic_block bb; 7405 edge e; 7406 edge_iterator ei; 7407 7408 /* split_edge can redirect edges out of SWITCH_EXPRs, which can get 7409 expensive. So we want to enable recording of edge to CASE_LABEL_EXPR 7410 mappings around the calls to split_edge. */ 7411 start_recording_case_labels (); 7412 FOR_ALL_BB (bb) 7413 { 7414 FOR_EACH_EDGE (e, ei, bb->succs) 7415 { 7416 if (EDGE_CRITICAL_P (e) && !(e->flags & EDGE_ABNORMAL)) 7417 split_edge (e); 7418 /* PRE inserts statements to edges and expects that 7419 since split_critical_edges was done beforehand, committing edge 7420 insertions will not split more edges. In addition to critical 7421 edges we must split edges that have multiple successors and 7422 end by control flow statements, such as RESX. 7423 Go ahead and split them too. This matches the logic in 7424 gimple_find_edge_insert_loc. */ 7425 else if ((!single_pred_p (e->dest) 7426 || !gimple_seq_empty_p (phi_nodes (e->dest)) 7427 || e->dest == EXIT_BLOCK_PTR) 7428 && e->src != ENTRY_BLOCK_PTR 7429 && !(e->flags & EDGE_ABNORMAL)) 7430 { 7431 gimple_stmt_iterator gsi; 7432 7433 gsi = gsi_last_bb (e->src); 7434 if (!gsi_end_p (gsi) 7435 && stmt_ends_bb_p (gsi_stmt (gsi)) 7436 && (gimple_code (gsi_stmt (gsi)) != GIMPLE_RETURN 7437 && !gimple_call_builtin_p (gsi_stmt (gsi), 7438 BUILT_IN_RETURN))) 7439 split_edge (e); 7440 } 7441 } 7442 } 7443 end_recording_case_labels (); 7444 return 0; 7445 } 7446 7447 struct gimple_opt_pass pass_split_crit_edges = 7448 { 7449 { 7450 GIMPLE_PASS, 7451 "crited", /* name */ 7452 NULL, /* gate */ 7453 split_critical_edges, /* execute */ 7454 NULL, /* sub */ 7455 NULL, /* next */ 7456 0, /* static_pass_number */ 7457 TV_TREE_SPLIT_EDGES, /* tv_id */ 7458 PROP_cfg, /* properties required */ 7459 PROP_no_crit_edges, /* properties_provided */ 7460 0, /* properties_destroyed */ 7461 0, /* todo_flags_start */ 7462 TODO_verify_flow /* todo_flags_finish */ 7463 } 7464 }; 7465 7466 7467 /* Build a ternary operation and gimplify it. Emit code before GSI. 7468 Return the gimple_val holding the result. */ 7469 7470 tree 7471 gimplify_build3 (gimple_stmt_iterator *gsi, enum tree_code code, 7472 tree type, tree a, tree b, tree c) 7473 { 7474 tree ret; 7475 location_t loc = gimple_location (gsi_stmt (*gsi)); 7476 7477 ret = fold_build3_loc (loc, code, type, a, b, c); 7478 STRIP_NOPS (ret); 7479 7480 return force_gimple_operand_gsi (gsi, ret, true, NULL, true, 7481 GSI_SAME_STMT); 7482 } 7483 7484 /* Build a binary operation and gimplify it. Emit code before GSI. 7485 Return the gimple_val holding the result. */ 7486 7487 tree 7488 gimplify_build2 (gimple_stmt_iterator *gsi, enum tree_code code, 7489 tree type, tree a, tree b) 7490 { 7491 tree ret; 7492 7493 ret = fold_build2_loc (gimple_location (gsi_stmt (*gsi)), code, type, a, b); 7494 STRIP_NOPS (ret); 7495 7496 return force_gimple_operand_gsi (gsi, ret, true, NULL, true, 7497 GSI_SAME_STMT); 7498 } 7499 7500 /* Build a unary operation and gimplify it. Emit code before GSI. 7501 Return the gimple_val holding the result. */ 7502 7503 tree 7504 gimplify_build1 (gimple_stmt_iterator *gsi, enum tree_code code, tree type, 7505 tree a) 7506 { 7507 tree ret; 7508 7509 ret = fold_build1_loc (gimple_location (gsi_stmt (*gsi)), code, type, a); 7510 STRIP_NOPS (ret); 7511 7512 return force_gimple_operand_gsi (gsi, ret, true, NULL, true, 7513 GSI_SAME_STMT); 7514 } 7515 7516 7517 7518 /* Emit return warnings. */ 7519 7520 static unsigned int 7521 execute_warn_function_return (void) 7522 { 7523 source_location location; 7524 gimple last; 7525 edge e; 7526 edge_iterator ei; 7527 7528 /* If we have a path to EXIT, then we do return. */ 7529 if (TREE_THIS_VOLATILE (cfun->decl) 7530 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0) 7531 { 7532 location = UNKNOWN_LOCATION; 7533 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 7534 { 7535 last = last_stmt (e->src); 7536 if ((gimple_code (last) == GIMPLE_RETURN 7537 || gimple_call_builtin_p (last, BUILT_IN_RETURN)) 7538 && (location = gimple_location (last)) != UNKNOWN_LOCATION) 7539 break; 7540 } 7541 if (location == UNKNOWN_LOCATION) 7542 location = cfun->function_end_locus; 7543 warning_at (location, 0, "%<noreturn%> function does return"); 7544 } 7545 7546 /* If we see "return;" in some basic block, then we do reach the end 7547 without returning a value. */ 7548 else if (warn_return_type 7549 && !TREE_NO_WARNING (cfun->decl) 7550 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) > 0 7551 && !VOID_TYPE_P (TREE_TYPE (TREE_TYPE (cfun->decl)))) 7552 { 7553 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 7554 { 7555 gimple last = last_stmt (e->src); 7556 if (gimple_code (last) == GIMPLE_RETURN 7557 && gimple_return_retval (last) == NULL 7558 && !gimple_no_warning_p (last)) 7559 { 7560 location = gimple_location (last); 7561 if (location == UNKNOWN_LOCATION) 7562 location = cfun->function_end_locus; 7563 warning_at (location, OPT_Wreturn_type, "control reaches end of non-void function"); 7564 TREE_NO_WARNING (cfun->decl) = 1; 7565 break; 7566 } 7567 } 7568 } 7569 return 0; 7570 } 7571 7572 7573 /* Given a basic block B which ends with a conditional and has 7574 precisely two successors, determine which of the edges is taken if 7575 the conditional is true and which is taken if the conditional is 7576 false. Set TRUE_EDGE and FALSE_EDGE appropriately. */ 7577 7578 void 7579 extract_true_false_edges_from_block (basic_block b, 7580 edge *true_edge, 7581 edge *false_edge) 7582 { 7583 edge e = EDGE_SUCC (b, 0); 7584 7585 if (e->flags & EDGE_TRUE_VALUE) 7586 { 7587 *true_edge = e; 7588 *false_edge = EDGE_SUCC (b, 1); 7589 } 7590 else 7591 { 7592 *false_edge = e; 7593 *true_edge = EDGE_SUCC (b, 1); 7594 } 7595 } 7596 7597 struct gimple_opt_pass pass_warn_function_return = 7598 { 7599 { 7600 GIMPLE_PASS, 7601 "*warn_function_return", /* name */ 7602 NULL, /* gate */ 7603 execute_warn_function_return, /* execute */ 7604 NULL, /* sub */ 7605 NULL, /* next */ 7606 0, /* static_pass_number */ 7607 TV_NONE, /* tv_id */ 7608 PROP_cfg, /* properties_required */ 7609 0, /* properties_provided */ 7610 0, /* properties_destroyed */ 7611 0, /* todo_flags_start */ 7612 0 /* todo_flags_finish */ 7613 } 7614 }; 7615 7616 /* Emit noreturn warnings. */ 7617 7618 static unsigned int 7619 execute_warn_function_noreturn (void) 7620 { 7621 if (!TREE_THIS_VOLATILE (current_function_decl) 7622 && EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 0) 7623 warn_function_noreturn (current_function_decl); 7624 return 0; 7625 } 7626 7627 static bool 7628 gate_warn_function_noreturn (void) 7629 { 7630 return warn_suggest_attribute_noreturn; 7631 } 7632 7633 struct gimple_opt_pass pass_warn_function_noreturn = 7634 { 7635 { 7636 GIMPLE_PASS, 7637 "*warn_function_noreturn", /* name */ 7638 gate_warn_function_noreturn, /* gate */ 7639 execute_warn_function_noreturn, /* execute */ 7640 NULL, /* sub */ 7641 NULL, /* next */ 7642 0, /* static_pass_number */ 7643 TV_NONE, /* tv_id */ 7644 PROP_cfg, /* properties_required */ 7645 0, /* properties_provided */ 7646 0, /* properties_destroyed */ 7647 0, /* todo_flags_start */ 7648 0 /* todo_flags_finish */ 7649 } 7650 }; 7651 7652 7653 /* Walk a gimplified function and warn for functions whose return value is 7654 ignored and attribute((warn_unused_result)) is set. This is done before 7655 inlining, so we don't have to worry about that. */ 7656 7657 static void 7658 do_warn_unused_result (gimple_seq seq) 7659 { 7660 tree fdecl, ftype; 7661 gimple_stmt_iterator i; 7662 7663 for (i = gsi_start (seq); !gsi_end_p (i); gsi_next (&i)) 7664 { 7665 gimple g = gsi_stmt (i); 7666 7667 switch (gimple_code (g)) 7668 { 7669 case GIMPLE_BIND: 7670 do_warn_unused_result (gimple_bind_body (g)); 7671 break; 7672 case GIMPLE_TRY: 7673 do_warn_unused_result (gimple_try_eval (g)); 7674 do_warn_unused_result (gimple_try_cleanup (g)); 7675 break; 7676 case GIMPLE_CATCH: 7677 do_warn_unused_result (gimple_catch_handler (g)); 7678 break; 7679 case GIMPLE_EH_FILTER: 7680 do_warn_unused_result (gimple_eh_filter_failure (g)); 7681 break; 7682 7683 case GIMPLE_CALL: 7684 if (gimple_call_lhs (g)) 7685 break; 7686 if (gimple_call_internal_p (g)) 7687 break; 7688 7689 /* This is a naked call, as opposed to a GIMPLE_CALL with an 7690 LHS. All calls whose value is ignored should be 7691 represented like this. Look for the attribute. */ 7692 fdecl = gimple_call_fndecl (g); 7693 ftype = gimple_call_fntype (g); 7694 7695 if (lookup_attribute ("warn_unused_result", TYPE_ATTRIBUTES (ftype))) 7696 { 7697 location_t loc = gimple_location (g); 7698 7699 if (fdecl) 7700 warning_at (loc, OPT_Wunused_result, 7701 "ignoring return value of %qD, " 7702 "declared with attribute warn_unused_result", 7703 fdecl); 7704 else 7705 warning_at (loc, OPT_Wunused_result, 7706 "ignoring return value of function " 7707 "declared with attribute warn_unused_result"); 7708 } 7709 break; 7710 7711 default: 7712 /* Not a container, not a call, or a call whose value is used. */ 7713 break; 7714 } 7715 } 7716 } 7717 7718 static unsigned int 7719 run_warn_unused_result (void) 7720 { 7721 do_warn_unused_result (gimple_body (current_function_decl)); 7722 return 0; 7723 } 7724 7725 static bool 7726 gate_warn_unused_result (void) 7727 { 7728 return flag_warn_unused_result; 7729 } 7730 7731 struct gimple_opt_pass pass_warn_unused_result = 7732 { 7733 { 7734 GIMPLE_PASS, 7735 "*warn_unused_result", /* name */ 7736 gate_warn_unused_result, /* gate */ 7737 run_warn_unused_result, /* execute */ 7738 NULL, /* sub */ 7739 NULL, /* next */ 7740 0, /* static_pass_number */ 7741 TV_NONE, /* tv_id */ 7742 PROP_gimple_any, /* properties_required */ 7743 0, /* properties_provided */ 7744 0, /* properties_destroyed */ 7745 0, /* todo_flags_start */ 7746 0, /* todo_flags_finish */ 7747 } 7748 }; 7749