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