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 varray_type may_aliases; 385 386 ann = var_ann (var); 387 may_aliases = ann->may_aliases; 388 389 for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++) 390 { 391 tree alias = VARRAY_TREE (may_aliases, j); 392 393 bitmap_set_bit (visited, DECL_UID (alias)); 394 395 if (!may_be_aliased (alias)) 396 { 397 error ("non-addressable variable inside an alias set"); 398 debug_variable (alias); 399 goto err; 400 } 401 } 402 } 403 404 FOR_EACH_REFERENCED_VAR (var, rvi) 405 { 406 var_ann_t ann; 407 ann = var_ann (var); 408 409 if (ann->mem_tag_kind == NOT_A_TAG 410 && ann->is_alias_tag 411 && !bitmap_bit_p (visited, DECL_UID (var))) 412 { 413 error ("addressable variable that is an alias tag but is not in any alias set"); 414 goto err; 415 } 416 } 417 418 BITMAP_FREE (visited); 419 return; 420 421err: 422 debug_variable (var); 423 internal_error ("verify_flow_insensitive_alias_info failed"); 424} 425 426 427static void 428verify_flow_sensitive_alias_info (void) 429{ 430 size_t i; 431 tree ptr; 432 433 for (i = 1; i < num_ssa_names; i++) 434 { 435 tree var; 436 var_ann_t ann; 437 struct ptr_info_def *pi; 438 439 440 ptr = ssa_name (i); 441 if (!ptr) 442 continue; 443 444 /* We only care for pointers that are actually referenced in the 445 program. */ 446 if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) 447 continue; 448 449 /* RESULT_DECL is special. If it's a GIMPLE register, then it 450 is only written-to only once in the return statement. 451 Otherwise, aggregate RESULT_DECLs may be written-to more than 452 once in virtual operands. */ 453 var = SSA_NAME_VAR (ptr); 454 if (TREE_CODE (var) == RESULT_DECL 455 && is_gimple_reg (ptr)) 456 continue; 457 458 pi = SSA_NAME_PTR_INFO (ptr); 459 if (pi == NULL) 460 continue; 461 462 ann = var_ann (var); 463 if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag) 464 { 465 error ("dereferenced pointers should have a name or a type tag"); 466 goto err; 467 } 468 469 if (pi->name_mem_tag 470 && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) 471 { 472 error ("pointers with a memory tag, should have points-to sets"); 473 goto err; 474 } 475 476 if (pi->value_escapes_p 477 && pi->name_mem_tag 478 && !is_call_clobbered (pi->name_mem_tag)) 479 { 480 error ("pointer escapes but its name tag is not call-clobbered"); 481 goto err; 482 } 483 } 484 485 return; 486 487err: 488 debug_variable (ptr); 489 internal_error ("verify_flow_sensitive_alias_info failed"); 490} 491 492DEF_VEC_P (bitmap); 493DEF_VEC_ALLOC_P (bitmap,heap); 494 495/* Verify that all name tags have different points to sets. 496 This algorithm takes advantage of the fact that every variable with the 497 same name tag must have the same points-to set. 498 So we check a single variable for each name tag, and verify that its 499 points-to set is different from every other points-to set for other name 500 tags. 501 502 Additionally, given a pointer P_i with name tag NMT and type tag 503 TMT, this function verified the alias set of TMT is a superset of 504 the alias set of NMT. */ 505 506static void 507verify_name_tags (void) 508{ 509 size_t i; 510 size_t j; 511 bitmap first, second; 512 VEC(tree,heap) *name_tag_reps = NULL; 513 VEC(bitmap,heap) *pt_vars_for_reps = NULL; 514 bitmap type_aliases = BITMAP_ALLOC (NULL); 515 516 /* First we compute the name tag representatives and their points-to sets. */ 517 for (i = 0; i < num_ssa_names; i++) 518 { 519 struct ptr_info_def *pi; 520 tree tmt, ptr = ssa_name (i); 521 522 if (ptr == NULL_TREE) 523 continue; 524 525 pi = SSA_NAME_PTR_INFO (ptr); 526 527 if (!TREE_VISITED (ptr) 528 || !POINTER_TYPE_P (TREE_TYPE (ptr)) 529 || !pi 530 || !pi->name_mem_tag 531 || TREE_VISITED (pi->name_mem_tag)) 532 continue; 533 534 TREE_VISITED (pi->name_mem_tag) = 1; 535 536 if (pi->pt_vars == NULL) 537 continue; 538 539 VEC_safe_push (tree, heap, name_tag_reps, ptr); 540 VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars); 541 542 /* Verify that alias set of PTR's type tag is a superset of the 543 alias set of PTR's name tag. */ 544 tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag; 545 if (tmt) 546 { 547 size_t i; 548 varray_type aliases = var_ann (tmt)->may_aliases; 549 bitmap_clear (type_aliases); 550 for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++) 551 { 552 tree alias = VARRAY_TREE (aliases, i); 553 bitmap_set_bit (type_aliases, DECL_UID (alias)); 554 } 555 556 /* When grouping, we may have added PTR's type tag into the 557 alias set of PTR's name tag. To prevent a false 558 positive, pretend that TMT is in its own alias set. */ 559 bitmap_set_bit (type_aliases, DECL_UID (tmt)); 560 561 if (bitmap_equal_p (type_aliases, pi->pt_vars)) 562 continue; 563 564 if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) 565 { 566 error ("alias set of a pointer's type tag should be a superset of the corresponding name tag"); 567 debug_variable (tmt); 568 debug_variable (pi->name_mem_tag); 569 goto err; 570 } 571 } 572 } 573 574 /* Now compare all the representative bitmaps with all other representative 575 bitmaps, to verify that they are all different. */ 576 for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) 577 { 578 for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) 579 { 580 if (bitmap_equal_p (first, second)) 581 { 582 error ("two different pointers with identical points-to sets but different name tags"); 583 debug_variable (VEC_index (tree, name_tag_reps, j)); 584 goto err; 585 } 586 } 587 } 588 589 /* Lastly, clear out the visited flags. */ 590 for (i = 0; i < num_ssa_names; i++) 591 { 592 if (ssa_name (i)) 593 { 594 tree ptr = ssa_name (i); 595 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 596 if (!TREE_VISITED (ptr) 597 || !POINTER_TYPE_P (TREE_TYPE (ptr)) 598 || !pi 599 || !pi->name_mem_tag) 600 continue; 601 TREE_VISITED (pi->name_mem_tag) = 0; 602 } 603 } 604 605 /* We do not have to free the bitmaps or trees in the vectors, as 606 they are not owned by us. */ 607 VEC_free (bitmap, heap, pt_vars_for_reps); 608 VEC_free (tree, heap, name_tag_reps); 609 BITMAP_FREE (type_aliases); 610 return; 611 612err: 613 debug_variable (VEC_index (tree, name_tag_reps, i)); 614 internal_error ("verify_name_tags failed"); 615} 616 617 618/* Verify the consistency of aliasing information. */ 619 620static void 621verify_alias_info (void) 622{ 623 verify_flow_sensitive_alias_info (); 624 verify_name_tags (); 625 verify_flow_insensitive_alias_info (); 626} 627 628 629/* Verify common invariants in the SSA web. 630 TODO: verify the variable annotations. */ 631 632void 633verify_ssa (bool check_modified_stmt) 634{ 635 size_t i; 636 basic_block bb; 637 basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block)); 638 ssa_op_iter iter; 639 tree op; 640 enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; 641 bitmap names_defined_in_bb = BITMAP_ALLOC (NULL); 642 643 gcc_assert (!need_ssa_update_p ()); 644 645 verify_stmts (); 646 647 timevar_push (TV_TREE_SSA_VERIFY); 648 649 /* Keep track of SSA names present in the IL. */ 650 for (i = 1; i < num_ssa_names; i++) 651 { 652 tree name = ssa_name (i); 653 if (name) 654 { 655 tree stmt; 656 TREE_VISITED (name) = 0; 657 658 stmt = SSA_NAME_DEF_STMT (name); 659 if (!IS_EMPTY_STMT (stmt)) 660 { 661 basic_block bb = bb_for_stmt (stmt); 662 verify_def (bb, definition_block, 663 name, stmt, !is_gimple_reg (name)); 664 665 } 666 } 667 } 668 669 calculate_dominance_info (CDI_DOMINATORS); 670 671 /* Now verify all the uses and make sure they agree with the definitions 672 found in the previous pass. */ 673 FOR_EACH_BB (bb) 674 { 675 edge e; 676 tree phi; 677 edge_iterator ei; 678 block_stmt_iterator bsi; 679 680 /* Make sure that all edges have a clear 'aux' field. */ 681 FOR_EACH_EDGE (e, ei, bb->preds) 682 { 683 if (e->aux) 684 { 685 error ("AUX pointer initialized for edge %d->%d", e->src->index, 686 e->dest->index); 687 goto err; 688 } 689 } 690 691 /* Verify the arguments for every PHI node in the block. */ 692 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 693 { 694 if (verify_phi_args (phi, bb, definition_block)) 695 goto err; 696 bitmap_set_bit (names_defined_in_bb, 697 SSA_NAME_VERSION (PHI_RESULT (phi))); 698 } 699 700 /* Now verify all the uses and vuses in every statement of the block. */ 701 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 702 { 703 tree stmt = bsi_stmt (bsi); 704 use_operand_p use_p; 705 706 if (check_modified_stmt && stmt_modified_p (stmt)) 707 { 708 error ("stmt (%p) marked modified after optimization pass : ", 709 (void *)stmt); 710 print_generic_stmt (stderr, stmt, TDF_VOPS); 711 goto err; 712 } 713 714 if (TREE_CODE (stmt) == MODIFY_EXPR 715 && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) 716 { 717 tree lhs, base_address; 718 719 lhs = TREE_OPERAND (stmt, 0); 720 base_address = get_base_address (lhs); 721 722 if (base_address 723 && SSA_VAR_P (base_address) 724 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 725 { 726 error ("statement makes a memory store, but has no " 727 "V_MAY_DEFS nor V_MUST_DEFS"); 728 print_generic_stmt (stderr, stmt, TDF_VOPS); 729 goto err; 730 } 731 } 732 733 734 if (stmt_ann (stmt)->makes_aliased_stores 735 && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF)) 736 { 737 error ("statement makes aliased stores, but has no V_MAY_DEFS"); 738 print_generic_stmt (stderr, stmt, TDF_VOPS); 739 goto err; 740 } 741 742 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 743 SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 744 { 745 op = USE_FROM_PTR (use_p); 746 if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], 747 use_p, stmt, false, !is_gimple_reg (op), 748 names_defined_in_bb)) 749 goto err; 750 } 751 752 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) 753 bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); 754 } 755 756 bitmap_clear (names_defined_in_bb); 757 } 758 759 /* Finally, verify alias information. */ 760 verify_alias_info (); 761 762 free (definition_block); 763 764 /* Restore the dominance information to its prior known state, so 765 that we do not perturb the compiler's subsequent behavior. */ 766 if (orig_dom_state == DOM_NONE) 767 free_dominance_info (CDI_DOMINATORS); 768 else 769 dom_computed[CDI_DOMINATORS] = orig_dom_state; 770 771 BITMAP_FREE (names_defined_in_bb); 772 timevar_pop (TV_TREE_SSA_VERIFY); 773 return; 774 775err: 776 internal_error ("verify_ssa failed"); 777} 778 779/* Return true if the uid in both int tree maps are equal. */ 780 781int 782int_tree_map_eq (const void *va, const void *vb) 783{ 784 const struct int_tree_map *a = va, *b = vb; 785 return (a->uid == b->uid); 786} 787 788/* Hash a UID in a int_tree_map. */ 789 790unsigned int 791int_tree_map_hash (const void *item) 792{ 793 return ((const struct int_tree_map *)item)->uid; 794} 795 796 797/* Initialize global DFA and SSA structures. */ 798 799void 800init_tree_ssa (void) 801{ 802 referenced_vars = htab_create_ggc (20, int_tree_map_hash, 803 int_tree_map_eq, NULL); 804 call_clobbered_vars = BITMAP_ALLOC (NULL); 805 addressable_vars = BITMAP_ALLOC (NULL); 806 init_alias_heapvars (); 807 init_ssanames (); 808 init_phinodes (); 809 global_var = NULL_TREE; 810 aliases_computed_p = false; 811} 812 813 814/* Deallocate memory associated with SSA data structures for FNDECL. */ 815 816void 817delete_tree_ssa (void) 818{ 819 size_t i; 820 basic_block bb; 821 block_stmt_iterator bsi; 822 referenced_var_iterator rvi; 823 tree var; 824 825 /* Release any ssa_names still in use. */ 826 for (i = 0; i < num_ssa_names; i++) 827 { 828 tree var = ssa_name (i); 829 if (var && TREE_CODE (var) == SSA_NAME) 830 { 831 SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var)); 832 SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var)); 833 } 834 release_ssa_name (var); 835 } 836 837 /* Remove annotations from every tree in the function. */ 838 FOR_EACH_BB (bb) 839 { 840 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 841 { 842 tree stmt = bsi_stmt (bsi); 843 stmt_ann_t ann = get_stmt_ann (stmt); 844 845 free_ssa_operands (&ann->operands); 846 ann->addresses_taken = 0; 847 mark_stmt_modified (stmt); 848 } 849 set_phi_nodes (bb, NULL); 850 } 851 852 /* Remove annotations from every referenced variable. */ 853 FOR_EACH_REFERENCED_VAR (var, rvi) 854 { 855 ggc_free (var->common.ann); 856 var->common.ann = NULL; 857 } 858 htab_delete (referenced_vars); 859 referenced_vars = NULL; 860 861 fini_ssanames (); 862 fini_phinodes (); 863 864 global_var = NULL_TREE; 865 BITMAP_FREE (call_clobbered_vars); 866 call_clobbered_vars = NULL; 867 BITMAP_FREE (addressable_vars); 868 addressable_vars = NULL; 869 modified_noreturn_calls = NULL; 870 aliases_computed_p = false; 871 delete_alias_heapvars (); 872 gcc_assert (!need_ssa_update_p ()); 873} 874 875 876/* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a 877 useless type conversion, otherwise return false. */ 878 879bool 880tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) 881{ 882 if (inner_type == outer_type) 883 return true; 884 885 /* Changes in machine mode are never useless conversions. */ 886 if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type)) 887 return false; 888 889 /* If the inner and outer types are effectively the same, then 890 strip the type conversion and enter the equivalence into 891 the table. */ 892 if (lang_hooks.types_compatible_p (inner_type, outer_type)) 893 return true; 894 895 /* If both types are pointers and the outer type is a (void *), then 896 the conversion is not necessary. The opposite is not true since 897 that conversion would result in a loss of information if the 898 equivalence was used. Consider an indirect function call where 899 we need to know the exact type of the function to correctly 900 implement the ABI. */ 901 else if (POINTER_TYPE_P (inner_type) 902 && POINTER_TYPE_P (outer_type) 903 && TYPE_REF_CAN_ALIAS_ALL (inner_type) 904 == TYPE_REF_CAN_ALIAS_ALL (outer_type) 905 && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) 906 return true; 907 908 /* Don't lose casts between pointers to volatile and non-volatile 909 qualified types. Doing so would result in changing the semantics 910 of later accesses. */ 911 else if (POINTER_TYPE_P (inner_type) 912 && POINTER_TYPE_P (outer_type) 913 && TYPE_VOLATILE (TREE_TYPE (outer_type)) 914 != TYPE_VOLATILE (TREE_TYPE (inner_type))) 915 return false; 916 917 /* Pointers/references are equivalent if their pointed to types 918 are effectively the same. This allows to strip conversions between 919 pointer types with different type qualifiers. */ 920 else if (POINTER_TYPE_P (inner_type) 921 && POINTER_TYPE_P (outer_type) 922 && TYPE_REF_CAN_ALIAS_ALL (inner_type) 923 == TYPE_REF_CAN_ALIAS_ALL (outer_type) 924 && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), 925 TREE_TYPE (outer_type))) 926 return true; 927 928 /* If both the inner and outer types are integral types, then the 929 conversion is not necessary if they have the same mode and 930 signedness and precision, and both or neither are boolean. Some 931 code assumes an invariant that boolean types stay boolean and do 932 not become 1-bit bit-field types. Note that types with precision 933 not using all bits of the mode (such as bit-field types in C) 934 mean that testing of precision is necessary. */ 935 else if (INTEGRAL_TYPE_P (inner_type) 936 && INTEGRAL_TYPE_P (outer_type) 937 && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type) 938 && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type) 939 && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type)) 940 && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type))) 941 { 942 bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE); 943 bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE); 944 if (first_boolean == second_boolean) 945 return true; 946 } 947 948 /* Recurse for complex types. */ 949 else if (TREE_CODE (inner_type) == COMPLEX_TYPE 950 && TREE_CODE (outer_type) == COMPLEX_TYPE 951 && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type), 952 TREE_TYPE (inner_type))) 953 return true; 954 955 return false; 956} 957 958/* Return true if EXPR is a useless type conversion, otherwise return 959 false. */ 960 961bool 962tree_ssa_useless_type_conversion (tree expr) 963{ 964 /* If we have an assignment that merely uses a NOP_EXPR to change 965 the top of the RHS to the type of the LHS and the type conversion 966 is "safe", then strip away the type conversion so that we can 967 enter LHS = RHS into the const_and_copies table. */ 968 if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR 969 || TREE_CODE (expr) == VIEW_CONVERT_EXPR 970 || TREE_CODE (expr) == NON_LVALUE_EXPR) 971 return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr), 972 TREE_TYPE (TREE_OPERAND (expr, 973 0))); 974 975 976 return false; 977} 978 979/* Returns true if statement STMT may read memory. */ 980 981bool 982stmt_references_memory_p (tree stmt) 983{ 984 stmt_ann_t ann = stmt_ann (stmt); 985 986 if (ann->has_volatile_ops) 987 return true; 988 989 return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)); 990} 991 992/* Internal helper for walk_use_def_chains. VAR, FN and DATA are as 993 described in walk_use_def_chains. 994 995 VISITED is a pointer set used to mark visited SSA_NAMEs to avoid 996 infinite loops. We used to have a bitmap for this to just mark 997 SSA versions we had visited. But non-sparse bitmaps are way too 998 expensive, while sparse bitmaps may cause quadratic behavior. 999 1000 IS_DFS is true if the caller wants to perform a depth-first search 1001 when visiting PHI nodes. A DFS will visit each PHI argument and 1002 call FN after each one. Otherwise, all the arguments are 1003 visited first and then FN is called with each of the visited 1004 arguments in a separate pass. */ 1005 1006static bool 1007walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, 1008 struct pointer_set_t *visited, bool is_dfs) 1009{ 1010 tree def_stmt; 1011 1012 if (pointer_set_insert (visited, var)) 1013 return false; 1014 1015 def_stmt = SSA_NAME_DEF_STMT (var); 1016 1017 if (TREE_CODE (def_stmt) != PHI_NODE) 1018 { 1019 /* If we reached the end of the use-def chain, call FN. */ 1020 return fn (var, def_stmt, data); 1021 } 1022 else 1023 { 1024 int i; 1025 1026 /* When doing a breadth-first search, call FN before following the 1027 use-def links for each argument. */ 1028 if (!is_dfs) 1029 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1030 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1031 return true; 1032 1033 /* Follow use-def links out of each PHI argument. */ 1034 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1035 { 1036 tree arg = PHI_ARG_DEF (def_stmt, i); 1037 if (TREE_CODE (arg) == SSA_NAME 1038 && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) 1039 return true; 1040 } 1041 1042 /* When doing a depth-first search, call FN after following the 1043 use-def links for each argument. */ 1044 if (is_dfs) 1045 for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1046 if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1047 return true; 1048 } 1049 1050 return false; 1051} 1052 1053 1054 1055/* Walk use-def chains starting at the SSA variable VAR. Call 1056 function FN at each reaching definition found. FN takes three 1057 arguments: VAR, its defining statement (DEF_STMT) and a generic 1058 pointer to whatever state information that FN may want to maintain 1059 (DATA). FN is able to stop the walk by returning true, otherwise 1060 in order to continue the walk, FN should return false. 1061 1062 Note, that if DEF_STMT is a PHI node, the semantics are slightly 1063 different. The first argument to FN is no longer the original 1064 variable VAR, but the PHI argument currently being examined. If FN 1065 wants to get at VAR, it should call PHI_RESULT (PHI). 1066 1067 If IS_DFS is true, this function will: 1068 1069 1- walk the use-def chains for all the PHI arguments, and, 1070 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. 1071 1072 If IS_DFS is false, the two steps above are done in reverse order 1073 (i.e., a breadth-first search). */ 1074 1075 1076void 1077walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, 1078 bool is_dfs) 1079{ 1080 tree def_stmt; 1081 1082 gcc_assert (TREE_CODE (var) == SSA_NAME); 1083 1084 def_stmt = SSA_NAME_DEF_STMT (var); 1085 1086 /* We only need to recurse if the reaching definition comes from a PHI 1087 node. */ 1088 if (TREE_CODE (def_stmt) != PHI_NODE) 1089 (*fn) (var, def_stmt, data); 1090 else 1091 { 1092 struct pointer_set_t *visited = pointer_set_create (); 1093 walk_use_def_chains_1 (var, fn, data, visited, is_dfs); 1094 pointer_set_destroy (visited); 1095 } 1096} 1097 1098 1099/* Emit warnings for uninitialized variables. This is done in two passes. 1100 1101 The first pass notices real uses of SSA names with default definitions. 1102 Such uses are unconditionally uninitialized, and we can be certain that 1103 such a use is a mistake. This pass is run before most optimizations, 1104 so that we catch as many as we can. 1105 1106 The second pass follows PHI nodes to find uses that are potentially 1107 uninitialized. In this case we can't necessarily prove that the use 1108 is really uninitialized. This pass is run after most optimizations, 1109 so that we thread as many jumps and possible, and delete as much dead 1110 code as possible, in order to reduce false positives. We also look 1111 again for plain uninitialized variables, since optimization may have 1112 changed conditionally uninitialized to unconditionally uninitialized. */ 1113 1114/* Emit a warning for T, an SSA_NAME, being uninitialized. The exact 1115 warning text is in MSGID and LOCUS may contain a location or be null. */ 1116 1117static void 1118warn_uninit (tree t, const char *gmsgid, void *data) 1119{ 1120 tree var = SSA_NAME_VAR (t); 1121 tree def = SSA_NAME_DEF_STMT (t); 1122 tree context = (tree) data; 1123 location_t * locus; 1124 1125 /* Default uses (indicated by an empty definition statement), 1126 are uninitialized. */ 1127 if (!IS_EMPTY_STMT (def)) 1128 return; 1129 1130 /* Except for PARMs of course, which are always initialized. */ 1131 if (TREE_CODE (var) == PARM_DECL) 1132 return; 1133 1134 /* Hard register variables get their initial value from the ether. */ 1135 if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) 1136 return; 1137 1138 /* TREE_NO_WARNING either means we already warned, or the front end 1139 wishes to suppress the warning. */ 1140 if (TREE_NO_WARNING (var)) 1141 return; 1142 1143 locus = (context != NULL && EXPR_HAS_LOCATION (context) 1144 ? EXPR_LOCUS (context) 1145 : &DECL_SOURCE_LOCATION (var)); 1146 warning (0, gmsgid, locus, var); 1147 TREE_NO_WARNING (var) = 1; 1148} 1149 1150/* Called via walk_tree, look for SSA_NAMEs that have empty definitions 1151 and warn about them. */ 1152 1153static tree 1154warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) 1155{ 1156 tree t = *tp; 1157 1158 switch (TREE_CODE (t)) 1159 { 1160 case SSA_NAME: 1161 /* We only do data flow with SSA_NAMEs, so that's all we 1162 can warn about. */ 1163 warn_uninit (t, "%H%qD is used uninitialized in this function", data); 1164 *walk_subtrees = 0; 1165 break; 1166 1167 case REALPART_EXPR: 1168 case IMAGPART_EXPR: 1169 /* The total store transformation performed during gimplification 1170 creates uninitialized variable uses. If all is well, these will 1171 be optimized away, so don't warn now. */ 1172 if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME) 1173 *walk_subtrees = 0; 1174 break; 1175 1176 default: 1177 if (IS_TYPE_OR_DECL_P (t)) 1178 *walk_subtrees = 0; 1179 break; 1180 } 1181 1182 return NULL_TREE; 1183} 1184 1185/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions 1186 and warn about them. */ 1187 1188static void 1189warn_uninitialized_phi (tree phi) 1190{ 1191 int i, n = PHI_NUM_ARGS (phi); 1192 1193 /* Don't look at memory tags. */ 1194 if (!is_gimple_reg (PHI_RESULT (phi))) 1195 return; 1196 1197 for (i = 0; i < n; ++i) 1198 { 1199 tree op = PHI_ARG_DEF (phi, i); 1200 if (TREE_CODE (op) == SSA_NAME) 1201 warn_uninit (op, "%H%qD may be used uninitialized in this function", 1202 NULL); 1203 } 1204} 1205 1206static void 1207execute_early_warn_uninitialized (void) 1208{ 1209 block_stmt_iterator bsi; 1210 basic_block bb; 1211 1212 FOR_EACH_BB (bb) 1213 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1214 { 1215 tree context = bsi_stmt (bsi); 1216 walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var, 1217 context, NULL); 1218 } 1219} 1220 1221static void 1222execute_late_warn_uninitialized (void) 1223{ 1224 basic_block bb; 1225 tree phi; 1226 1227 /* Re-do the plain uninitialized variable check, as optimization may have 1228 straightened control flow. Do this first so that we don't accidentally 1229 get a "may be" warning when we'd have seen an "is" warning later. */ 1230 execute_early_warn_uninitialized (); 1231 1232 FOR_EACH_BB (bb) 1233 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1234 warn_uninitialized_phi (phi); 1235} 1236 1237static bool 1238gate_warn_uninitialized (void) 1239{ 1240 return warn_uninitialized != 0; 1241} 1242 1243struct tree_opt_pass pass_early_warn_uninitialized = 1244{ 1245 NULL, /* name */ 1246 gate_warn_uninitialized, /* gate */ 1247 execute_early_warn_uninitialized, /* execute */ 1248 NULL, /* sub */ 1249 NULL, /* next */ 1250 0, /* static_pass_number */ 1251 0, /* tv_id */ 1252 PROP_ssa, /* properties_required */ 1253 0, /* properties_provided */ 1254 0, /* properties_destroyed */ 1255 0, /* todo_flags_start */ 1256 0, /* todo_flags_finish */ 1257 0 /* letter */ 1258}; 1259 1260struct tree_opt_pass pass_late_warn_uninitialized = 1261{ 1262 NULL, /* name */ 1263 gate_warn_uninitialized, /* gate */ 1264 execute_late_warn_uninitialized, /* execute */ 1265 NULL, /* sub */ 1266 NULL, /* next */ 1267 0, /* static_pass_number */ 1268 0, /* tv_id */ 1269 PROP_ssa, /* properties_required */ 1270 0, /* properties_provided */ 1271 0, /* properties_destroyed */ 1272 0, /* todo_flags_start */ 1273 0, /* todo_flags_finish */ 1274 0 /* letter */ 1275}; 1276 1277