tree-ssa.c revision 225736
1/* Miscellaneous SSA utility functions. 2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to 18the Free Software Foundation, 51 Franklin Street, Fifth Floor, 19Boston, MA 02110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "tree.h" 26#include "flags.h" 27#include "rtl.h" 28#include "tm_p.h" 29#include "ggc.h" 30#include "langhooks.h" 31#include "hard-reg-set.h" 32#include "basic-block.h" 33#include "output.h" 34#include "expr.h" 35#include "function.h" 36#include "diagnostic.h" 37#include "bitmap.h" 38#include "pointer-set.h" 39#include "tree-flow.h" 40#include "tree-gimple.h" 41#include "tree-inline.h" 42#include "varray.h" 43#include "timevar.h" 44#include "hashtab.h" 45#include "tree-dump.h" 46#include "tree-pass.h" 47#include "toplev.h" 48 49/* Remove the corresponding arguments from the PHI nodes in E's 50 destination block and redirect it to DEST. Return redirected edge. 51 The list of removed arguments is stored in PENDING_STMT (e). */ 52 53edge 54ssa_redirect_edge (edge e, basic_block dest) 55{ 56 tree phi; 57 tree list = NULL, *last = &list; 58 tree src, dst, node; 59 60 /* Remove the appropriate PHI arguments in E's destination block. */ 61 for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 62 { 63 if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE) 64 continue; 65 66 src = PHI_ARG_DEF (phi, e->dest_idx); 67 dst = PHI_RESULT (phi); 68 node = build_tree_list (dst, src); 69 *last = node; 70 last = &TREE_CHAIN (node); 71 } 72 73 e = redirect_edge_succ_nodup (e, dest); 74 PENDING_STMT (e) = list; 75 76 return e; 77} 78 79/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge 80 E->dest. */ 81 82void 83flush_pending_stmts (edge e) 84{ 85 tree phi, arg; 86 87 if (!PENDING_STMT (e)) 88 return; 89 90 for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e); 91 phi; 92 phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg)) 93 { 94 tree def = TREE_VALUE (arg); 95 add_phi_arg (phi, def, e); 96 } 97 98 PENDING_STMT (e) = NULL; 99} 100 101/* Return true if SSA_NAME is malformed and mark it visited. 102 103 IS_VIRTUAL is true if this SSA_NAME was found inside a virtual 104 operand. */ 105 106static bool 107verify_ssa_name (tree ssa_name, bool is_virtual) 108{ 109 if (TREE_CODE (ssa_name) != SSA_NAME) 110 { 111 error ("expected an SSA_NAME object"); 112 return true; 113 } 114 115 if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name))) 116 { 117 error ("type mismatch between an SSA_NAME and its symbol"); 118 return true; 119 } 120 121 if (SSA_NAME_IN_FREE_LIST (ssa_name)) 122 { 123 error ("found an SSA_NAME that had been released into the free pool"); 124 return true; 125 } 126 127 if (is_virtual && is_gimple_reg (ssa_name)) 128 { 129 error ("found a virtual definition for a GIMPLE register"); 130 return true; 131 } 132 133 if (!is_virtual && !is_gimple_reg (ssa_name)) 134 { 135 error ("found a real definition for a non-register"); 136 return true; 137 } 138 139 if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name)) 140 && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL) 141 { 142 error ("found real variable when subvariables should have appeared"); 143 return true; 144 } 145 146 return false; 147} 148 149 150/* Return true if the definition of SSA_NAME at block BB is malformed. 151 152 STMT is the statement where SSA_NAME is created. 153 154 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME 155 version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, 156 it means that the block in that array slot contains the 157 definition of SSA_NAME. 158 159 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a 160 V_MUST_DEF. */ 161 162static bool 163verify_def (basic_block bb, basic_block *definition_block, tree ssa_name, 164 tree stmt, bool is_virtual) 165{ 166 if (verify_ssa_name (ssa_name, is_virtual)) 167 goto err; 168 169 if (definition_block[SSA_NAME_VERSION (ssa_name)]) 170 { 171 error ("SSA_NAME created in two different blocks %i and %i", 172 definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index); 173 goto err; 174 } 175 176 definition_block[SSA_NAME_VERSION (ssa_name)] = bb; 177 178 if (SSA_NAME_DEF_STMT (ssa_name) != stmt) 179 { 180 error ("SSA_NAME_DEF_STMT is wrong"); 181 fprintf (stderr, "Expected definition statement:\n"); 182 print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS); 183 fprintf (stderr, "\nActual definition statement:\n"); 184 print_generic_stmt (stderr, stmt, TDF_VOPS); 185 goto err; 186 } 187 188 return false; 189 190err: 191 fprintf (stderr, "while verifying SSA_NAME "); 192 print_generic_expr (stderr, ssa_name, 0); 193 fprintf (stderr, " in statement\n"); 194 print_generic_stmt (stderr, stmt, TDF_VOPS); 195 196 return true; 197} 198 199 200/* Return true if the use of SSA_NAME at statement STMT in block BB is 201 malformed. 202 203 DEF_BB is the block where SSA_NAME was found to be created. 204 205 IDOM contains immediate dominator information for the flowgraph. 206 207 CHECK_ABNORMAL is true if the caller wants to check whether this use 208 is flowing through an abnormal edge (only used when checking PHI 209 arguments). 210 211 IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a 212 V_MUST_DEF. 213 214 If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names 215 that are defined before STMT in basic block BB. */ 216 217static bool 218verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p, 219 tree stmt, bool check_abnormal, bool is_virtual, 220 bitmap names_defined_in_bb) 221{ 222 bool err = false; 223 tree ssa_name = USE_FROM_PTR (use_p); 224 225 err = verify_ssa_name (ssa_name, is_virtual); 226 227 if (!TREE_VISITED (ssa_name)) 228 if (verify_imm_links (stderr, ssa_name)) 229 err = true; 230 231 TREE_VISITED (ssa_name) = 1; 232 233 if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)) 234 && default_def (SSA_NAME_VAR (ssa_name)) == ssa_name) 235 ; /* Default definitions have empty statements. Nothing to do. */ 236 else if (!def_bb) 237 { 238 error ("missing definition"); 239 err = true; 240 } 241 else if (bb != def_bb 242 && !dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 243 { 244 error ("definition in block %i does not dominate use in block %i", 245 def_bb->index, bb->index); 246 err = true; 247 } 248 else if (bb == def_bb 249 && names_defined_in_bb != NULL 250 && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name))) 251 { 252 error ("definition in block %i follows the use", def_bb->index); 253 err = true; 254 } 255 256 if (check_abnormal 257 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name)) 258 { 259 error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set"); 260 err = true; 261 } 262 263 /* Make sure the use is in an appropriate list by checking the previous 264 element to make sure it's the same. */ 265 if (use_p->prev == NULL) 266 { 267 error ("no immediate_use list"); 268 err = true; 269 } 270 else 271 { 272 tree listvar ; 273 if (use_p->prev->use == NULL) 274 listvar = use_p->prev->stmt; 275 else 276 listvar = USE_FROM_PTR (use_p->prev); 277 if (listvar != ssa_name) 278 { 279 error ("wrong immediate use list"); 280 err = true; 281 } 282 } 283 284 if (err) 285 { 286 fprintf (stderr, "for SSA_NAME: "); 287 print_generic_expr (stderr, ssa_name, TDF_VOPS); 288 fprintf (stderr, " in statement:\n"); 289 print_generic_stmt (stderr, stmt, TDF_VOPS); 290 } 291 292 return err; 293} 294 295 296/* Return true if any of the arguments for PHI node PHI at block BB is 297 malformed. 298 299 DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version 300 numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the 301 block in that array slot contains the definition of SSA_NAME. */ 302 303static bool 304verify_phi_args (tree phi, basic_block bb, basic_block *definition_block) 305{ 306 edge e; 307 bool err = false; 308 unsigned i, phi_num_args = PHI_NUM_ARGS (phi); 309 310 if (EDGE_COUNT (bb->preds) != phi_num_args) 311 { 312 error ("incoming edge count does not match number of PHI arguments"); 313 err = true; 314 goto error; 315 } 316 317 for (i = 0; i < phi_num_args; i++) 318 { 319 use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i); 320 tree op = USE_FROM_PTR (op_p); 321 322 323 e = EDGE_PRED (bb, i); 324 325 if (op == NULL_TREE) 326 { 327 error ("PHI argument is missing for edge %d->%d", 328 e->src->index, 329 e->dest->index); 330 err = true; 331 goto error; 332 } 333 334 if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op)) 335 { 336 error ("PHI argument is not SSA_NAME, or invariant"); 337 err = true; 338 } 339 340 if (TREE_CODE (op) == SSA_NAME) 341 err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p, 342 phi, e->flags & EDGE_ABNORMAL, 343 !is_gimple_reg (PHI_RESULT (phi)), 344 NULL); 345 346 if (e->dest != bb) 347 { 348 error ("wrong edge %d->%d for PHI argument", 349 e->src->index, e->dest->index); 350 err = true; 351 } 352 353 if (err) 354 { 355 fprintf (stderr, "PHI argument\n"); 356 print_generic_stmt (stderr, op, TDF_VOPS); 357 goto error; 358 } 359 } 360 361error: 362 if (err) 363 { 364 fprintf (stderr, "for PHI node\n"); 365 print_generic_stmt (stderr, phi, TDF_VOPS); 366 } 367 368 369 return err; 370} 371 372 373static void 374verify_flow_insensitive_alias_info (void) 375{ 376 tree var; 377 bitmap visited = BITMAP_ALLOC (NULL); 378 referenced_var_iterator rvi; 379 380 FOR_EACH_REFERENCED_VAR (var, rvi) 381 { 382 size_t j; 383 var_ann_t ann; 384 VEC(tree,gc) *may_aliases; 385 tree alias; 386 387 ann = var_ann (var); 388 may_aliases = ann->may_aliases; 389 390 for (j = 0; VEC_iterate (tree, may_aliases, j, alias); j++) 391 { 392 bitmap_set_bit (visited, DECL_UID (alias)); 393 394 if (!may_be_aliased (alias)) 395 { 396 error ("non-addressable variable inside an alias set"); 397 debug_variable (alias); 398 goto err; 399 } 400 } 401 } 402 403 FOR_EACH_REFERENCED_VAR (var, rvi) 404 { 405 var_ann_t ann; 406 ann = var_ann (var); 407 408 if (!MTAG_P (var) 409 && ann->is_aliased 410 && !bitmap_bit_p (visited, DECL_UID (var))) 411 { 412 error ("addressable variable that is aliased but is not in any alias set"); 413 goto err; 414 } 415 } 416 417 BITMAP_FREE (visited); 418 return; 419 420err: 421 debug_variable (var); 422 internal_error ("verify_flow_insensitive_alias_info failed"); 423} 424 425 426static void 427verify_flow_sensitive_alias_info (void) 428{ 429 size_t i; 430 tree ptr; 431 432 for (i = 1; i < num_ssa_names; i++) 433 { 434 tree var; 435 var_ann_t ann; 436 struct ptr_info_def *pi; 437 438 439 ptr = ssa_name (i); 440 if (!ptr) 441 continue; 442 443 /* We only care for pointers that are actually referenced in the 444 program. */ 445 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) 446 continue; 447 448 /* RESULT_DECL is special. If it's a GIMPLE register, then it 449 is only written-to only once in the return statement. 450 Otherwise, aggregate RESULT_DECLs may be written-to more than 451 once in virtual operands. */ 452 var = SSA_NAME_VAR (ptr); 453 if (TREE_CODE (var) == RESULT_DECL 454 && is_gimple_reg (ptr)) 455 continue; 456 457 pi = SSA_NAME_PTR_INFO (ptr); 458 if (pi == NULL) 459 continue; 460 461 ann = var_ann (var); 462 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag) 463 { 464 error ("dereferenced pointers should have a name or a symbol tag"); 465 goto err; 466 } 467 468 if (pi->name_mem_tag 469 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) 470 { 471 error ("pointers with a memory tag, should have points-to sets"); 472 goto err; 473 } 474 475 if (pi->value_escapes_p 476 && pi->name_mem_tag 477 && !is_call_clobbered (pi->name_mem_tag)) 478 { 479 error ("pointer escapes but its name tag is not call-clobbered"); 480 goto err; 481 } 482 } 483 484 return; 485 486err: 487 debug_variable (ptr); 488 internal_error ("verify_flow_sensitive_alias_info failed"); 489} 490 491DEF_VEC_P (bitmap); 492DEF_VEC_ALLOC_P (bitmap,heap); 493 494/* Verify that all name tags have different points to sets. 495 This algorithm takes advantage of the fact that every variable with the 496 same name tag must have the same points-to set. 497 So we check a single variable for each name tag, and verify that its 498 points-to set is different from every other points-to set for other name 499 tags. 500 501 Additionally, given a pointer P_i with name tag NMT and symbol tag 502 SMT, this function verified the alias set of SMT is a superset of 503 the alias set of NMT. */ 504 505static void 506verify_name_tags (void) 507{ 508 size_t i; 509 size_t j; 510 bitmap first, second; 511 VEC(tree,heap) *name_tag_reps = NULL; 512 VEC(bitmap,heap) *pt_vars_for_reps = NULL; 513 bitmap type_aliases = BITMAP_ALLOC (NULL); 514 515 /* First we compute the name tag representatives and their points-to sets. */ 516 for (i = 0; i < num_ssa_names; i++) 517 { 518 struct ptr_info_def *pi; 519 tree smt, ptr = ssa_name (i); 520 521 if (ptr == NULL_TREE) 522 continue; 523 524 pi = SSA_NAME_PTR_INFO (ptr); 525 526 if (!TREE_VISITED (ptr) 527 || !POINTER_TYPE_P (TREE_TYPE (ptr)) 528 || !pi 529 || !pi->name_mem_tag 530 || TREE_VISITED (pi->name_mem_tag)) 531 continue; 532 533 TREE_VISITED (pi->name_mem_tag) = 1; 534 535 if (pi->pt_vars == NULL) 536 continue; 537 538 VEC_safe_push (tree, heap, name_tag_reps, ptr); 539 VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars); 540 541 /* Verify that alias set of PTR's symbol tag is a superset of the 542 alias set of PTR's name tag. */ 543 smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; 544 if (smt) 545 { 546 size_t i; 547 VEC(tree,gc) *aliases = var_ann (smt)->may_aliases; 548 tree alias; 549 550 bitmap_clear (type_aliases); 551 for (i = 0; VEC_iterate (tree, aliases, i, alias); i++) 552 bitmap_set_bit (type_aliases, DECL_UID (alias)); 553 554 /* When grouping, we may have added PTR's symbol tag into the 555 alias set of PTR's name tag. To prevent a false 556 positive, pretend that SMT is in its own alias set. */ 557 bitmap_set_bit (type_aliases, DECL_UID (smt)); 558 559 if (bitmap_equal_p (type_aliases, pi->pt_vars)) 560 continue; 561 562 if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) 563 { 564 error ("alias set of a pointer's symbol tag should be a superset of the corresponding name tag"); 565 debug_variable (smt); 566 debug_variable (pi->name_mem_tag); 567 goto err; 568 } 569 } 570 } 571 572 /* Now compare all the representative bitmaps with all other representative 573 bitmaps, to verify that they are all different. */ 574 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) 575 { 576 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) 577 { 578 if (bitmap_equal_p (first, second)) 579 { 580 error ("two different pointers with identical points-to sets but different name tags"); 581 debug_variable (VEC_index (tree, name_tag_reps, j)); 582 goto err; 583 } 584 } 585 } 586 587 /* Lastly, clear out the visited flags. */ 588 for (i = 0; i < num_ssa_names; i++) 589 { 590 if (ssa_name (i)) 591 { 592 tree ptr = ssa_name (i); 593 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 594 if (!TREE_VISITED (ptr) 595 || !POINTER_TYPE_P (TREE_TYPE (ptr)) 596 || !pi 597 || !pi->name_mem_tag) 598 continue; 599 TREE_VISITED (pi->name_mem_tag) = 0; 600 } 601 } 602 603 /* We do not have to free the bitmaps or trees in the vectors, as 604 they are not owned by us. */ 605 VEC_free (bitmap, heap, pt_vars_for_reps); 606 VEC_free (tree, heap, name_tag_reps); 607 BITMAP_FREE (type_aliases); 608 return; 609 610err: 611 debug_variable (VEC_index (tree, name_tag_reps, i)); 612 internal_error ("verify_name_tags failed"); 613} 614 615 616/* Verify the consistency of call clobbering information. */ 617static void 618verify_call_clobbering (void) 619{ 620 unsigned int i; 621 bitmap_iterator bi; 622 tree var; 623 referenced_var_iterator rvi; 624 625 /* At all times, the result of the DECL_CALL_CLOBBERED flag should 626 match the result of the call_clobbered_vars bitmap. Verify both 627 that everything in call_clobbered_vars is marked 628 DECL_CALL_CLOBBERED, and that everything marked 629 DECL_CALL_CLOBBERED is in call_clobbered_vars. */ 630 EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) 631 { 632 var = referenced_var (i); 633 if (!MTAG_P (var) && !DECL_CALL_CLOBBERED (var)) 634 { 635 error ("variable in call_clobbered_vars but not marked DECL_CALL_CLOBBERED"); 636 debug_variable (var); 637 goto err; 638 } 639 } 640 FOR_EACH_REFERENCED_VAR (var, rvi) 641 { 642 if (!MTAG_P (var) && DECL_CALL_CLOBBERED (var) 643 && !bitmap_bit_p (call_clobbered_vars, DECL_UID (var))) 644 { 645 error ("variable marked DECL_CALL_CLOBBERED but not in call_clobbered_vars bitmap."); 646 debug_variable (var); 647 goto err; 648 } 649 } 650 return; 651 652 err: 653 internal_error ("verify_call_clobbering failed"); 654} 655 656/* Verify the consistency of aliasing information. */ 657 658static void 659verify_alias_info (void) 660{ 661 verify_flow_sensitive_alias_info (); 662 verify_name_tags (); 663 verify_call_clobbering (); 664 verify_flow_insensitive_alias_info (); 665} 666 667 668/* Verify common invariants in the SSA web. 669 TODO: verify the variable annotations. */ 670 671void 672verify_ssa (bool check_modified_stmt) 673{ 674 size_t i; 675 basic_block bb; 676 basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names); 677 ssa_op_iter iter; 678 tree op; 679 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; 680 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL); 681 682 gcc_assert (!need_ssa_update_p ()); 683 684 verify_stmts (); 685 686 timevar_push (TV_TREE_SSA_VERIFY); 687 688 /* Keep track of SSA names present in the IL. */ 689 for (i = 1; i < num_ssa_names; i++) 690 { 691 tree name = ssa_name (i); 692 if (name) 693 { 694 tree stmt; 695 TREE_VISITED (name) = 0; 696 697 stmt = SSA_NAME_DEF_STMT (name); 698 if (!IS_EMPTY_STMT (stmt)) 699 { 700 basic_block bb = bb_for_stmt (stmt); 701 verify_def (bb, definition_block, 702 name, stmt, !is_gimple_reg (name)); 703 704 } 705 } 706 } 707 708 calculate_dominance_info (CDI_DOMINATORS); 709 710 /* Now verify all the uses and make sure they agree with the definitions 711 found in the previous pass. */ 712 FOR_EACH_BB (bb) 713 { 714 edge e; 715 tree phi; 716 edge_iterator ei; 717 block_stmt_iterator bsi; 718 719 /* Make sure that all edges have a clear 'aux' field. */ 720 FOR_EACH_EDGE (e, ei, bb->preds) 721 { 722 if (e->aux) 723 { 724 error ("AUX pointer initialized for edge %d->%d", e->src->index, 725 e->dest->index); 726 goto err; 727 } 728 } 729 730 /* Verify the arguments for every PHI node in the block. */ 731 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 732 { 733 if (verify_phi_args (phi, bb, definition_block)) 734 goto err; 735 bitmap_set_bit (names_defined_in_bb, 736 SSA_NAME_VERSION (PHI_RESULT (phi))); 737 } 738 739 /* Now verify all the uses and vuses in every statement of the block. */ 740 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 741 { 742 tree stmt = bsi_stmt (bsi); 743 use_operand_p use_p; 744 745 if (check_modified_stmt && stmt_modified_p (stmt)) 746 { 747 error ("stmt (%p) marked modified after optimization pass : ", 748 (void *)stmt); 749 print_generic_stmt (stderr, stmt, TDF_VOPS); 750 goto err; 751 } 752 753 if (TREE_CODE (stmt) == MODIFY_EXPR 754 && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) 755 { 756 tree lhs, base_address; 757 758 lhs = TREE_OPERAND (stmt, 0); 759 base_address = get_base_address (lhs); 760 761 if (base_address 762 && SSA_VAR_P (base_address) 763 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 764 { 765 error ("statement makes a memory store, but has no " 766 "V_MAY_DEFS nor V_MUST_DEFS"); 767 print_generic_stmt (stderr, stmt, TDF_VOPS); 768 goto err; 769 } 770 } 771 772 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 773 SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 774 { 775 op = USE_FROM_PTR (use_p); 776 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], 777 use_p, stmt, false, !is_gimple_reg (op), 778 names_defined_in_bb)) 779 goto err; 780 } 781 782 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) 783 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); 784 } 785 786 bitmap_clear (names_defined_in_bb); 787 } 788 789 /* Finally, verify alias information. */ 790 verify_alias_info (); 791 792 free (definition_block); 793 794 /* Restore the dominance information to its prior known state, so 795 that we do not perturb the compiler's subsequent behavior. */ 796 if (orig_dom_state == DOM_NONE) 797 free_dominance_info (CDI_DOMINATORS); 798 else 799 dom_computed[CDI_DOMINATORS] = orig_dom_state; 800 801 BITMAP_FREE (names_defined_in_bb); 802 timevar_pop (TV_TREE_SSA_VERIFY); 803 return; 804 805err: 806 internal_error ("verify_ssa failed"); 807} 808 809/* Return true if the uid in both int tree maps are equal. */ 810 811int 812int_tree_map_eq (const void *va, const void *vb) 813{ 814 const struct int_tree_map *a = (const struct int_tree_map *) va; 815 const struct int_tree_map *b = (const struct int_tree_map *) vb; 816 return (a->uid == b->uid); 817} 818 819/* Hash a UID in a int_tree_map. */ 820 821unsigned int 822int_tree_map_hash (const void *item) 823{ 824 return ((const struct int_tree_map *)item)->uid; 825} 826 827 828/* Initialize global DFA and SSA structures. */ 829 830void 831init_tree_ssa (void) 832{ 833 referenced_vars = htab_create_ggc (20, int_tree_map_hash, 834 int_tree_map_eq, NULL); 835 default_defs = htab_create_ggc (20, int_tree_map_hash, int_tree_map_eq, NULL); 836 call_clobbered_vars = BITMAP_ALLOC (NULL); 837 addressable_vars = BITMAP_ALLOC (NULL); 838 init_alias_heapvars (); 839 init_ssanames (); 840 init_phinodes (); 841 global_var = NULL_TREE; 842 aliases_computed_p = false; 843} 844 845 846/* Deallocate memory associated with SSA data structures for FNDECL. */ 847 848void 849delete_tree_ssa (void) 850{ 851 size_t i; 852 basic_block bb; 853 block_stmt_iterator bsi; 854 referenced_var_iterator rvi; 855 tree var; 856 857 /* Release any ssa_names still in use. */ 858 for (i = 0; i < num_ssa_names; i++) 859 { 860 tree var = ssa_name (i); 861 if (var && TREE_CODE (var) == SSA_NAME) 862 { 863 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var)); 864 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var)); 865 } 866 release_ssa_name (var); 867 } 868 869 /* Remove annotations from every tree in the function. */ 870 FOR_EACH_BB (bb) 871 { 872 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 873 { 874 tree stmt = bsi_stmt (bsi); 875 stmt_ann_t ann = get_stmt_ann (stmt); 876 877 free_ssa_operands (&ann->operands); 878 ann->addresses_taken = 0; 879 mark_stmt_modified (stmt); 880 } 881 set_phi_nodes (bb, NULL); 882 } 883 884 /* Remove annotations from every referenced variable. */ 885 FOR_EACH_REFERENCED_VAR (var, rvi) 886 { 887 ggc_free (var->common.ann); 888 var->common.ann = NULL; 889 } 890 htab_delete (referenced_vars); 891 referenced_vars = NULL; 892 893 fini_ssanames (); 894 fini_phinodes (); 895 896 global_var = NULL_TREE; 897 898 htab_delete (default_defs); 899 BITMAP_FREE (call_clobbered_vars); 900 call_clobbered_vars = NULL; 901 BITMAP_FREE (addressable_vars); 902 addressable_vars = NULL; 903 modified_noreturn_calls = NULL; 904 aliases_computed_p = false; 905 delete_alias_heapvars (); 906 gcc_assert (!need_ssa_update_p ()); 907} 908 909 910/* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a 911 useless type conversion, otherwise return false. */ 912 913bool 914tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) 915{ 916 if (inner_type == outer_type) 917 return true; 918 919 /* Changes in machine mode are never useless conversions. */ 920 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type)) 921 return false; 922 923 /* If the inner and outer types are effectively the same, then 924 strip the type conversion and enter the equivalence into 925 the table. */ 926 if (lang_hooks.types_compatible_p (inner_type, outer_type)) 927 return true; 928 929 /* If both types are pointers and the outer type is a (void *), then 930 the conversion is not necessary. The opposite is not true since 931 that conversion would result in a loss of information if the 932 equivalence was used. Consider an indirect function call where 933 we need to know the exact type of the function to correctly 934 implement the ABI. */ 935 else if (POINTER_TYPE_P (inner_type) 936 && POINTER_TYPE_P (outer_type) 937 && TYPE_REF_CAN_ALIAS_ALL (inner_type) 938 == TYPE_REF_CAN_ALIAS_ALL (outer_type) 939 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) 940 return true; 941 942 /* Don't lose casts between pointers to volatile and non-volatile 943 qualified types. Doing so would result in changing the semantics 944 of later accesses. */ 945 else if (POINTER_TYPE_P (inner_type) 946 && POINTER_TYPE_P (outer_type) 947 && TYPE_VOLATILE (TREE_TYPE (outer_type)) 948 != TYPE_VOLATILE (TREE_TYPE (inner_type))) 949 return false; 950 951 /* Pointers/references are equivalent if their pointed to types 952 are effectively the same. This allows to strip conversions between 953 pointer types with different type qualifiers. */ 954 else if (POINTER_TYPE_P (inner_type) 955 && POINTER_TYPE_P (outer_type) 956 && TYPE_REF_CAN_ALIAS_ALL (inner_type) 957 == TYPE_REF_CAN_ALIAS_ALL (outer_type) 958 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), 959 TREE_TYPE (outer_type))) 960 return true; 961 962 /* If both the inner and outer types are integral types, then the 963 conversion is not necessary if they have the same mode and 964 signedness and precision, and both or neither are boolean. Some 965 code assumes an invariant that boolean types stay boolean and do 966 not become 1-bit bit-field types. Note that types with precision 967 not using all bits of the mode (such as bit-field types in C) 968 mean that testing of precision is necessary. */ 969 else if (INTEGRAL_TYPE_P (inner_type) 970 && INTEGRAL_TYPE_P (outer_type) 971 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type) 972 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type) 973 && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type)) 974 && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type))) 975 { 976 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE); 977 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE); 978 if (first_boolean == second_boolean) 979 return true; 980 } 981 982 /* Recurse for complex types. */ 983 else if (TREE_CODE (inner_type) == COMPLEX_TYPE 984 && TREE_CODE (outer_type) == COMPLEX_TYPE 985 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type), 986 TREE_TYPE (inner_type))) 987 return true; 988 989 return false; 990} 991 992/* Return true if EXPR is a useless type conversion, otherwise return 993 false. */ 994 995bool 996tree_ssa_useless_type_conversion (tree expr) 997{ 998 /* If we have an assignment that merely uses a NOP_EXPR to change 999 the top of the RHS to the type of the LHS and the type conversion 1000 is "safe", then strip away the type conversion so that we can 1001 enter LHS = RHS into the const_and_copies table. */ 1002 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR 1003 || TREE_CODE (expr) == VIEW_CONVERT_EXPR 1004 || TREE_CODE (expr) == NON_LVALUE_EXPR) 1005 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr), 1006 TREE_TYPE (TREE_OPERAND (expr, 1007 0))); 1008 1009 1010 return false; 1011} 1012 1013/* Returns true if statement STMT may read memory. */ 1014 1015bool 1016stmt_references_memory_p (tree stmt) 1017{ 1018 stmt_ann_t ann = stmt_ann (stmt); 1019 1020 if (ann->has_volatile_ops) 1021 return true; 1022 1023 return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)); 1024} 1025 1026/* Internal helper for walk_use_def_chains. VAR, FN and DATA are as 1027 described in walk_use_def_chains. 1028 1029 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid 1030 infinite loops. We used to have a bitmap for this to just mark 1031 SSA versions we had visited. But non-sparse bitmaps are way too 1032 expensive, while sparse bitmaps may cause quadratic behavior. 1033 1034 IS_DFS is true if the caller wants to perform a depth-first search 1035 when visiting PHI nodes. A DFS will visit each PHI argument and 1036 call FN after each one. Otherwise, all the arguments are 1037 visited first and then FN is called with each of the visited 1038 arguments in a separate pass. */ 1039 1040static bool 1041walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, 1042 struct pointer_set_t *visited, bool is_dfs) 1043{ 1044 tree def_stmt; 1045 1046 if (pointer_set_insert (visited, var)) 1047 return false; 1048 1049 def_stmt = SSA_NAME_DEF_STMT (var); 1050 1051 if (TREE_CODE (def_stmt) != PHI_NODE) 1052 { 1053 /* If we reached the end of the use-def chain, call FN. */ 1054 return fn (var, def_stmt, data); 1055 } 1056 else 1057 { 1058 int i; 1059 1060 /* When doing a breadth-first search, call FN before following the 1061 use-def links for each argument. */ 1062 if (!is_dfs) 1063 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1064 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1065 return true; 1066 1067 /* Follow use-def links out of each PHI argument. */ 1068 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1069 { 1070 tree arg = PHI_ARG_DEF (def_stmt, i); 1071 if (TREE_CODE (arg) == SSA_NAME 1072 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) 1073 return true; 1074 } 1075 1076 /* When doing a depth-first search, call FN after following the 1077 use-def links for each argument. */ 1078 if (is_dfs) 1079 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1080 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1081 return true; 1082 } 1083 1084 return false; 1085} 1086 1087 1088 1089/* Walk use-def chains starting at the SSA variable VAR. Call 1090 function FN at each reaching definition found. FN takes three 1091 arguments: VAR, its defining statement (DEF_STMT) and a generic 1092 pointer to whatever state information that FN may want to maintain 1093 (DATA). FN is able to stop the walk by returning true, otherwise 1094 in order to continue the walk, FN should return false. 1095 1096 Note, that if DEF_STMT is a PHI node, the semantics are slightly 1097 different. The first argument to FN is no longer the original 1098 variable VAR, but the PHI argument currently being examined. If FN 1099 wants to get at VAR, it should call PHI_RESULT (PHI). 1100 1101 If IS_DFS is true, this function will: 1102 1103 1- walk the use-def chains for all the PHI arguments, and, 1104 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. 1105 1106 If IS_DFS is false, the two steps above are done in reverse order 1107 (i.e., a breadth-first search). */ 1108 1109 1110void 1111walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, 1112 bool is_dfs) 1113{ 1114 tree def_stmt; 1115 1116 gcc_assert (TREE_CODE (var) == SSA_NAME); 1117 1118 def_stmt = SSA_NAME_DEF_STMT (var); 1119 1120 /* We only need to recurse if the reaching definition comes from a PHI 1121 node. */ 1122 if (TREE_CODE (def_stmt) != PHI_NODE) 1123 (*fn) (var, def_stmt, data); 1124 else 1125 { 1126 struct pointer_set_t *visited = pointer_set_create (); 1127 walk_use_def_chains_1 (var, fn, data, visited, is_dfs); 1128 pointer_set_destroy (visited); 1129 } 1130} 1131 1132 1133/* Emit warnings for uninitialized variables. This is done in two passes. 1134 1135 The first pass notices real uses of SSA names with default definitions. 1136 Such uses are unconditionally uninitialized, and we can be certain that 1137 such a use is a mistake. This pass is run before most optimizations, 1138 so that we catch as many as we can. 1139 1140 The second pass follows PHI nodes to find uses that are potentially 1141 uninitialized. In this case we can't necessarily prove that the use 1142 is really uninitialized. This pass is run after most optimizations, 1143 so that we thread as many jumps and possible, and delete as much dead 1144 code as possible, in order to reduce false positives. We also look 1145 again for plain uninitialized variables, since optimization may have 1146 changed conditionally uninitialized to unconditionally uninitialized. */ 1147 1148/* Emit a warning for T, an SSA_NAME, being uninitialized. The exact 1149 warning text is in MSGID and LOCUS may contain a location or be null. */ 1150 1151static void 1152warn_uninit (tree t, const char *gmsgid, void *data) 1153{ 1154 tree var = SSA_NAME_VAR (t); 1155 tree def = SSA_NAME_DEF_STMT (t); 1156 tree context = (tree) data; 1157 location_t *locus, *fun_locus; 1158 1159 /* Default uses (indicated by an empty definition statement), 1160 are uninitialized. */ 1161 if (!IS_EMPTY_STMT (def)) 1162 return; 1163 1164 /* Except for PARMs of course, which are always initialized. */ 1165 if (TREE_CODE (var) == PARM_DECL) 1166 return; 1167 1168 /* Hard register variables get their initial value from the ether. */ 1169 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) 1170 return; 1171 1172 /* TREE_NO_WARNING either means we already warned, or the front end 1173 wishes to suppress the warning. */ 1174 if (TREE_NO_WARNING (var)) 1175 return; 1176 1177 locus = (context != NULL && EXPR_HAS_LOCATION (context) 1178 ? EXPR_LOCUS (context) 1179 : &DECL_SOURCE_LOCATION (var)); 1180 warning (0, gmsgid, locus, var); 1181 fun_locus = &DECL_SOURCE_LOCATION (cfun->decl); 1182 if (locus->file != fun_locus->file 1183 || locus->line < fun_locus->line 1184 || locus->line > cfun->function_end_locus.line) 1185 inform ("%J%qD was declared here", var, var); 1186 1187 TREE_NO_WARNING (var) = 1; 1188} 1189 1190/* Called via walk_tree, look for SSA_NAMEs that have empty definitions 1191 and warn about them. */ 1192 1193static tree 1194warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) 1195{ 1196 tree t = *tp; 1197 1198 switch (TREE_CODE (t)) 1199 { 1200 case SSA_NAME: 1201 /* We only do data flow with SSA_NAMEs, so that's all we 1202 can warn about. */ 1203 warn_uninit (t, "%H%qD is used uninitialized in this function", data); 1204 *walk_subtrees = 0; 1205 break; 1206 1207 case REALPART_EXPR: 1208 case IMAGPART_EXPR: 1209 /* The total store transformation performed during gimplification 1210 creates uninitialized variable uses. If all is well, these will 1211 be optimized away, so don't warn now. */ 1212 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME) 1213 *walk_subtrees = 0; 1214 break; 1215 1216 default: 1217 if (IS_TYPE_OR_DECL_P (t)) 1218 *walk_subtrees = 0; 1219 break; 1220 } 1221 1222 return NULL_TREE; 1223} 1224 1225/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions 1226 and warn about them. */ 1227 1228static void 1229warn_uninitialized_phi (tree phi) 1230{ 1231 int i, n = PHI_NUM_ARGS (phi); 1232 1233 /* Don't look at memory tags. */ 1234 if (!is_gimple_reg (PHI_RESULT (phi))) 1235 return; 1236 1237 for (i = 0; i < n; ++i) 1238 { 1239 tree op = PHI_ARG_DEF (phi, i); 1240 if (TREE_CODE (op) == SSA_NAME) 1241 warn_uninit (op, "%H%qD may be used uninitialized in this function", 1242 NULL); 1243 } 1244} 1245 1246static unsigned int 1247execute_early_warn_uninitialized (void) 1248{ 1249 block_stmt_iterator bsi; 1250 basic_block bb; 1251 1252 FOR_EACH_BB (bb) 1253 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1254 { 1255 tree context = bsi_stmt (bsi); 1256 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var, 1257 context, NULL); 1258 } 1259 return 0; 1260} 1261 1262static unsigned int 1263execute_late_warn_uninitialized (void) 1264{ 1265 basic_block bb; 1266 tree phi; 1267 1268 /* Re-do the plain uninitialized variable check, as optimization may have 1269 straightened control flow. Do this first so that we don't accidentally 1270 get a "may be" warning when we'd have seen an "is" warning later. */ 1271 execute_early_warn_uninitialized (); 1272 1273 FOR_EACH_BB (bb) 1274 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1275 warn_uninitialized_phi (phi); 1276 return 0; 1277} 1278 1279static bool 1280gate_warn_uninitialized (void) 1281{ 1282 return warn_uninitialized != 0; 1283} 1284 1285struct tree_opt_pass pass_early_warn_uninitialized = 1286{ 1287 NULL, /* name */ 1288 gate_warn_uninitialized, /* gate */ 1289 execute_early_warn_uninitialized, /* execute */ 1290 NULL, /* sub */ 1291 NULL, /* next */ 1292 0, /* static_pass_number */ 1293 0, /* tv_id */ 1294 PROP_ssa, /* properties_required */ 1295 0, /* properties_provided */ 1296 0, /* properties_destroyed */ 1297 0, /* todo_flags_start */ 1298 0, /* todo_flags_finish */ 1299 0 /* letter */ 1300}; 1301 1302struct tree_opt_pass pass_late_warn_uninitialized = 1303{ 1304 NULL, /* name */ 1305 gate_warn_uninitialized, /* gate */ 1306 execute_late_warn_uninitialized, /* execute */ 1307 NULL, /* sub */ 1308 NULL, /* next */ 1309 0, /* static_pass_number */ 1310 0, /* tv_id */ 1311 PROP_ssa, /* properties_required */ 1312 0, /* properties_provided */ 1313 0, /* properties_destroyed */ 1314 0, /* todo_flags_start */ 1315 0, /* todo_flags_finish */ 1316 0 /* letter */ 1317}; 1318 1319