1169689Skan/* Miscellaneous SSA utility functions. 2169689Skan Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "flags.h" 27169689Skan#include "rtl.h" 28169689Skan#include "tm_p.h" 29169689Skan#include "ggc.h" 30169689Skan#include "langhooks.h" 31169689Skan#include "hard-reg-set.h" 32169689Skan#include "basic-block.h" 33169689Skan#include "output.h" 34169689Skan#include "expr.h" 35169689Skan#include "function.h" 36169689Skan#include "diagnostic.h" 37169689Skan#include "bitmap.h" 38169689Skan#include "pointer-set.h" 39169689Skan#include "tree-flow.h" 40169689Skan#include "tree-gimple.h" 41169689Skan#include "tree-inline.h" 42169689Skan#include "varray.h" 43169689Skan#include "timevar.h" 44169689Skan#include "hashtab.h" 45169689Skan#include "tree-dump.h" 46169689Skan#include "tree-pass.h" 47169689Skan#include "toplev.h" 48169689Skan 49169689Skan/* Remove the corresponding arguments from the PHI nodes in E's 50169689Skan destination block and redirect it to DEST. Return redirected edge. 51169689Skan The list of removed arguments is stored in PENDING_STMT (e). */ 52169689Skan 53169689Skanedge 54169689Skanssa_redirect_edge (edge e, basic_block dest) 55169689Skan{ 56169689Skan tree phi; 57169689Skan tree list = NULL, *last = &list; 58169689Skan tree src, dst, node; 59169689Skan 60169689Skan /* Remove the appropriate PHI arguments in E's destination block. */ 61169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 62169689Skan { 63169689Skan if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE) 64169689Skan continue; 65169689Skan 66169689Skan src = PHI_ARG_DEF (phi, e->dest_idx); 67169689Skan dst = PHI_RESULT (phi); 68169689Skan node = build_tree_list (dst, src); 69169689Skan *last = node; 70169689Skan last = &TREE_CHAIN (node); 71169689Skan } 72169689Skan 73169689Skan e = redirect_edge_succ_nodup (e, dest); 74169689Skan PENDING_STMT (e) = list; 75169689Skan 76169689Skan return e; 77169689Skan} 78169689Skan 79169689Skan/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge 80169689Skan E->dest. */ 81169689Skan 82169689Skanvoid 83169689Skanflush_pending_stmts (edge e) 84169689Skan{ 85169689Skan tree phi, arg; 86169689Skan 87169689Skan if (!PENDING_STMT (e)) 88169689Skan return; 89169689Skan 90169689Skan for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e); 91169689Skan phi; 92169689Skan phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg)) 93169689Skan { 94169689Skan tree def = TREE_VALUE (arg); 95169689Skan add_phi_arg (phi, def, e); 96169689Skan } 97169689Skan 98169689Skan PENDING_STMT (e) = NULL; 99169689Skan} 100169689Skan 101169689Skan/* Return true if SSA_NAME is malformed and mark it visited. 102169689Skan 103169689Skan IS_VIRTUAL is true if this SSA_NAME was found inside a virtual 104169689Skan operand. */ 105169689Skan 106169689Skanstatic bool 107169689Skanverify_ssa_name (tree ssa_name, bool is_virtual) 108169689Skan{ 109169689Skan if (TREE_CODE (ssa_name) != SSA_NAME) 110169689Skan { 111169689Skan error ("expected an SSA_NAME object"); 112169689Skan return true; 113169689Skan } 114169689Skan 115169689Skan if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name))) 116169689Skan { 117169689Skan error ("type mismatch between an SSA_NAME and its symbol"); 118169689Skan return true; 119169689Skan } 120169689Skan 121169689Skan if (SSA_NAME_IN_FREE_LIST (ssa_name)) 122169689Skan { 123169689Skan error ("found an SSA_NAME that had been released into the free pool"); 124169689Skan return true; 125169689Skan } 126169689Skan 127169689Skan if (is_virtual && is_gimple_reg (ssa_name)) 128169689Skan { 129169689Skan error ("found a virtual definition for a GIMPLE register"); 130169689Skan return true; 131169689Skan } 132169689Skan 133169689Skan if (!is_virtual && !is_gimple_reg (ssa_name)) 134169689Skan { 135169689Skan error ("found a real definition for a non-register"); 136169689Skan return true; 137169689Skan } 138169689Skan 139169689Skan if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name)) 140169689Skan && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL) 141169689Skan { 142169689Skan error ("found real variable when subvariables should have appeared"); 143169689Skan return true; 144169689Skan } 145169689Skan 146169689Skan return false; 147169689Skan} 148169689Skan 149169689Skan 150169689Skan/* Return true if the definition of SSA_NAME at block BB is malformed. 151169689Skan 152169689Skan STMT is the statement where SSA_NAME is created. 153169689Skan 154169689Skan DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME 155169689Skan version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, 156169689Skan it means that the block in that array slot contains the 157169689Skan definition of SSA_NAME. 158169689Skan 159169689Skan IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a 160169689Skan V_MUST_DEF. */ 161169689Skan 162169689Skanstatic bool 163169689Skanverify_def (basic_block bb, basic_block *definition_block, tree ssa_name, 164169689Skan tree stmt, bool is_virtual) 165169689Skan{ 166169689Skan if (verify_ssa_name (ssa_name, is_virtual)) 167169689Skan goto err; 168169689Skan 169169689Skan if (definition_block[SSA_NAME_VERSION (ssa_name)]) 170169689Skan { 171169689Skan error ("SSA_NAME created in two different blocks %i and %i", 172169689Skan definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index); 173169689Skan goto err; 174169689Skan } 175169689Skan 176169689Skan definition_block[SSA_NAME_VERSION (ssa_name)] = bb; 177169689Skan 178169689Skan if (SSA_NAME_DEF_STMT (ssa_name) != stmt) 179169689Skan { 180169689Skan error ("SSA_NAME_DEF_STMT is wrong"); 181169689Skan fprintf (stderr, "Expected definition statement:\n"); 182169689Skan print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS); 183169689Skan fprintf (stderr, "\nActual definition statement:\n"); 184169689Skan print_generic_stmt (stderr, stmt, TDF_VOPS); 185169689Skan goto err; 186169689Skan } 187169689Skan 188169689Skan return false; 189169689Skan 190169689Skanerr: 191169689Skan fprintf (stderr, "while verifying SSA_NAME "); 192169689Skan print_generic_expr (stderr, ssa_name, 0); 193169689Skan fprintf (stderr, " in statement\n"); 194169689Skan print_generic_stmt (stderr, stmt, TDF_VOPS); 195169689Skan 196169689Skan return true; 197169689Skan} 198169689Skan 199169689Skan 200169689Skan/* Return true if the use of SSA_NAME at statement STMT in block BB is 201169689Skan malformed. 202169689Skan 203169689Skan DEF_BB is the block where SSA_NAME was found to be created. 204169689Skan 205169689Skan IDOM contains immediate dominator information for the flowgraph. 206169689Skan 207169689Skan CHECK_ABNORMAL is true if the caller wants to check whether this use 208169689Skan is flowing through an abnormal edge (only used when checking PHI 209169689Skan arguments). 210169689Skan 211169689Skan IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a 212169689Skan V_MUST_DEF. 213169689Skan 214169689Skan If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names 215169689Skan that are defined before STMT in basic block BB. */ 216169689Skan 217169689Skanstatic bool 218169689Skanverify_use (basic_block bb, basic_block def_bb, use_operand_p use_p, 219169689Skan tree stmt, bool check_abnormal, bool is_virtual, 220169689Skan bitmap names_defined_in_bb) 221169689Skan{ 222169689Skan bool err = false; 223169689Skan tree ssa_name = USE_FROM_PTR (use_p); 224169689Skan 225169689Skan err = verify_ssa_name (ssa_name, is_virtual); 226169689Skan 227169689Skan if (!TREE_VISITED (ssa_name)) 228169689Skan if (verify_imm_links (stderr, ssa_name)) 229169689Skan err = true; 230169689Skan 231169689Skan TREE_VISITED (ssa_name) = 1; 232169689Skan 233169689Skan if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)) 234169689Skan && default_def (SSA_NAME_VAR (ssa_name)) == ssa_name) 235169689Skan ; /* Default definitions have empty statements. Nothing to do. */ 236169689Skan else if (!def_bb) 237169689Skan { 238169689Skan error ("missing definition"); 239169689Skan err = true; 240169689Skan } 241169689Skan else if (bb != def_bb 242169689Skan && !dominated_by_p (CDI_DOMINATORS, bb, def_bb)) 243169689Skan { 244169689Skan error ("definition in block %i does not dominate use in block %i", 245169689Skan def_bb->index, bb->index); 246169689Skan err = true; 247169689Skan } 248169689Skan else if (bb == def_bb 249169689Skan && names_defined_in_bb != NULL 250169689Skan && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name))) 251169689Skan { 252169689Skan error ("definition in block %i follows the use", def_bb->index); 253169689Skan err = true; 254169689Skan } 255169689Skan 256169689Skan if (check_abnormal 257169689Skan && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name)) 258169689Skan { 259169689Skan error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set"); 260169689Skan err = true; 261169689Skan } 262169689Skan 263169689Skan /* Make sure the use is in an appropriate list by checking the previous 264169689Skan element to make sure it's the same. */ 265169689Skan if (use_p->prev == NULL) 266169689Skan { 267169689Skan error ("no immediate_use list"); 268169689Skan err = true; 269169689Skan } 270169689Skan else 271169689Skan { 272169689Skan tree listvar ; 273169689Skan if (use_p->prev->use == NULL) 274169689Skan listvar = use_p->prev->stmt; 275169689Skan else 276169689Skan listvar = USE_FROM_PTR (use_p->prev); 277169689Skan if (listvar != ssa_name) 278169689Skan { 279169689Skan error ("wrong immediate use list"); 280169689Skan err = true; 281169689Skan } 282169689Skan } 283169689Skan 284169689Skan if (err) 285169689Skan { 286169689Skan fprintf (stderr, "for SSA_NAME: "); 287169689Skan print_generic_expr (stderr, ssa_name, TDF_VOPS); 288169689Skan fprintf (stderr, " in statement:\n"); 289169689Skan print_generic_stmt (stderr, stmt, TDF_VOPS); 290169689Skan } 291169689Skan 292169689Skan return err; 293169689Skan} 294169689Skan 295169689Skan 296169689Skan/* Return true if any of the arguments for PHI node PHI at block BB is 297169689Skan malformed. 298169689Skan 299169689Skan DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version 300169689Skan numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the 301169689Skan block in that array slot contains the definition of SSA_NAME. */ 302169689Skan 303169689Skanstatic bool 304169689Skanverify_phi_args (tree phi, basic_block bb, basic_block *definition_block) 305169689Skan{ 306169689Skan edge e; 307169689Skan bool err = false; 308169689Skan unsigned i, phi_num_args = PHI_NUM_ARGS (phi); 309169689Skan 310169689Skan if (EDGE_COUNT (bb->preds) != phi_num_args) 311169689Skan { 312169689Skan error ("incoming edge count does not match number of PHI arguments"); 313169689Skan err = true; 314169689Skan goto error; 315169689Skan } 316169689Skan 317169689Skan for (i = 0; i < phi_num_args; i++) 318169689Skan { 319169689Skan use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i); 320169689Skan tree op = USE_FROM_PTR (op_p); 321169689Skan 322169689Skan 323169689Skan e = EDGE_PRED (bb, i); 324169689Skan 325169689Skan if (op == NULL_TREE) 326169689Skan { 327169689Skan error ("PHI argument is missing for edge %d->%d", 328169689Skan e->src->index, 329169689Skan e->dest->index); 330169689Skan err = true; 331169689Skan goto error; 332169689Skan } 333169689Skan 334169689Skan if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op)) 335169689Skan { 336169689Skan error ("PHI argument is not SSA_NAME, or invariant"); 337169689Skan err = true; 338169689Skan } 339169689Skan 340169689Skan if (TREE_CODE (op) == SSA_NAME) 341169689Skan err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p, 342169689Skan phi, e->flags & EDGE_ABNORMAL, 343169689Skan !is_gimple_reg (PHI_RESULT (phi)), 344169689Skan NULL); 345169689Skan 346169689Skan if (e->dest != bb) 347169689Skan { 348169689Skan error ("wrong edge %d->%d for PHI argument", 349169689Skan e->src->index, e->dest->index); 350169689Skan err = true; 351169689Skan } 352169689Skan 353169689Skan if (err) 354169689Skan { 355169689Skan fprintf (stderr, "PHI argument\n"); 356169689Skan print_generic_stmt (stderr, op, TDF_VOPS); 357169689Skan goto error; 358169689Skan } 359169689Skan } 360169689Skan 361169689Skanerror: 362169689Skan if (err) 363169689Skan { 364169689Skan fprintf (stderr, "for PHI node\n"); 365169689Skan print_generic_stmt (stderr, phi, TDF_VOPS); 366169689Skan } 367169689Skan 368169689Skan 369169689Skan return err; 370169689Skan} 371169689Skan 372169689Skan 373169689Skanstatic void 374169689Skanverify_flow_insensitive_alias_info (void) 375169689Skan{ 376169689Skan tree var; 377169689Skan bitmap visited = BITMAP_ALLOC (NULL); 378169689Skan referenced_var_iterator rvi; 379169689Skan 380169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 381169689Skan { 382169689Skan size_t j; 383169689Skan var_ann_t ann; 384169689Skan VEC(tree,gc) *may_aliases; 385169689Skan tree alias; 386169689Skan 387169689Skan ann = var_ann (var); 388169689Skan may_aliases = ann->may_aliases; 389169689Skan 390169689Skan for (j = 0; VEC_iterate (tree, may_aliases, j, alias); j++) 391169689Skan { 392169689Skan bitmap_set_bit (visited, DECL_UID (alias)); 393169689Skan 394169689Skan if (!may_be_aliased (alias)) 395169689Skan { 396169689Skan error ("non-addressable variable inside an alias set"); 397169689Skan debug_variable (alias); 398169689Skan goto err; 399169689Skan } 400169689Skan } 401169689Skan } 402169689Skan 403169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 404169689Skan { 405169689Skan var_ann_t ann; 406169689Skan ann = var_ann (var); 407169689Skan 408169689Skan if (!MTAG_P (var) 409169689Skan && ann->is_aliased 410169689Skan && !bitmap_bit_p (visited, DECL_UID (var))) 411169689Skan { 412169689Skan error ("addressable variable that is aliased but is not in any alias set"); 413169689Skan goto err; 414169689Skan } 415169689Skan } 416169689Skan 417169689Skan BITMAP_FREE (visited); 418169689Skan return; 419169689Skan 420169689Skanerr: 421169689Skan debug_variable (var); 422169689Skan internal_error ("verify_flow_insensitive_alias_info failed"); 423169689Skan} 424169689Skan 425169689Skan 426169689Skanstatic void 427169689Skanverify_flow_sensitive_alias_info (void) 428169689Skan{ 429169689Skan size_t i; 430169689Skan tree ptr; 431169689Skan 432169689Skan for (i = 1; i < num_ssa_names; i++) 433169689Skan { 434169689Skan tree var; 435169689Skan var_ann_t ann; 436169689Skan struct ptr_info_def *pi; 437169689Skan 438169689Skan 439169689Skan ptr = ssa_name (i); 440169689Skan if (!ptr) 441169689Skan continue; 442169689Skan 443169689Skan /* We only care for pointers that are actually referenced in the 444169689Skan program. */ 445169689Skan if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr)) 446169689Skan continue; 447169689Skan 448169689Skan /* RESULT_DECL is special. If it's a GIMPLE register, then it 449169689Skan is only written-to only once in the return statement. 450169689Skan Otherwise, aggregate RESULT_DECLs may be written-to more than 451169689Skan once in virtual operands. */ 452169689Skan var = SSA_NAME_VAR (ptr); 453169689Skan if (TREE_CODE (var) == RESULT_DECL 454169689Skan && is_gimple_reg (ptr)) 455169689Skan continue; 456169689Skan 457169689Skan pi = SSA_NAME_PTR_INFO (ptr); 458169689Skan if (pi == NULL) 459169689Skan continue; 460169689Skan 461169689Skan ann = var_ann (var); 462169689Skan if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag) 463169689Skan { 464169689Skan error ("dereferenced pointers should have a name or a symbol tag"); 465169689Skan goto err; 466169689Skan } 467169689Skan 468169689Skan if (pi->name_mem_tag 469169689Skan && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars))) 470169689Skan { 471169689Skan error ("pointers with a memory tag, should have points-to sets"); 472169689Skan goto err; 473169689Skan } 474169689Skan 475169689Skan if (pi->value_escapes_p 476169689Skan && pi->name_mem_tag 477169689Skan && !is_call_clobbered (pi->name_mem_tag)) 478169689Skan { 479169689Skan error ("pointer escapes but its name tag is not call-clobbered"); 480169689Skan goto err; 481169689Skan } 482169689Skan } 483169689Skan 484169689Skan return; 485169689Skan 486169689Skanerr: 487169689Skan debug_variable (ptr); 488169689Skan internal_error ("verify_flow_sensitive_alias_info failed"); 489169689Skan} 490169689Skan 491169689SkanDEF_VEC_P (bitmap); 492169689SkanDEF_VEC_ALLOC_P (bitmap,heap); 493169689Skan 494169689Skan/* Verify that all name tags have different points to sets. 495169689Skan This algorithm takes advantage of the fact that every variable with the 496169689Skan same name tag must have the same points-to set. 497169689Skan So we check a single variable for each name tag, and verify that its 498169689Skan points-to set is different from every other points-to set for other name 499169689Skan tags. 500169689Skan 501169689Skan Additionally, given a pointer P_i with name tag NMT and symbol tag 502169689Skan SMT, this function verified the alias set of SMT is a superset of 503169689Skan the alias set of NMT. */ 504169689Skan 505169689Skanstatic void 506169689Skanverify_name_tags (void) 507169689Skan{ 508169689Skan size_t i; 509169689Skan size_t j; 510169689Skan bitmap first, second; 511169689Skan VEC(tree,heap) *name_tag_reps = NULL; 512169689Skan VEC(bitmap,heap) *pt_vars_for_reps = NULL; 513169689Skan bitmap type_aliases = BITMAP_ALLOC (NULL); 514169689Skan 515169689Skan /* First we compute the name tag representatives and their points-to sets. */ 516169689Skan for (i = 0; i < num_ssa_names; i++) 517169689Skan { 518169689Skan struct ptr_info_def *pi; 519169689Skan tree smt, ptr = ssa_name (i); 520169689Skan 521169689Skan if (ptr == NULL_TREE) 522169689Skan continue; 523169689Skan 524169689Skan pi = SSA_NAME_PTR_INFO (ptr); 525169689Skan 526169689Skan if (!TREE_VISITED (ptr) 527169689Skan || !POINTER_TYPE_P (TREE_TYPE (ptr)) 528169689Skan || !pi 529169689Skan || !pi->name_mem_tag 530169689Skan || TREE_VISITED (pi->name_mem_tag)) 531169689Skan continue; 532169689Skan 533169689Skan TREE_VISITED (pi->name_mem_tag) = 1; 534169689Skan 535169689Skan if (pi->pt_vars == NULL) 536169689Skan continue; 537169689Skan 538169689Skan VEC_safe_push (tree, heap, name_tag_reps, ptr); 539169689Skan VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars); 540169689Skan 541169689Skan /* Verify that alias set of PTR's symbol tag is a superset of the 542169689Skan alias set of PTR's name tag. */ 543169689Skan smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag; 544169689Skan if (smt) 545169689Skan { 546169689Skan size_t i; 547169689Skan VEC(tree,gc) *aliases = var_ann (smt)->may_aliases; 548169689Skan tree alias; 549169689Skan 550169689Skan bitmap_clear (type_aliases); 551169689Skan for (i = 0; VEC_iterate (tree, aliases, i, alias); i++) 552169689Skan bitmap_set_bit (type_aliases, DECL_UID (alias)); 553169689Skan 554169689Skan /* When grouping, we may have added PTR's symbol tag into the 555169689Skan alias set of PTR's name tag. To prevent a false 556169689Skan positive, pretend that SMT is in its own alias set. */ 557169689Skan bitmap_set_bit (type_aliases, DECL_UID (smt)); 558169689Skan 559169689Skan if (bitmap_equal_p (type_aliases, pi->pt_vars)) 560169689Skan continue; 561169689Skan 562169689Skan if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars)) 563169689Skan { 564169689Skan error ("alias set of a pointer's symbol tag should be a superset of the corresponding name tag"); 565169689Skan debug_variable (smt); 566169689Skan debug_variable (pi->name_mem_tag); 567169689Skan goto err; 568169689Skan } 569169689Skan } 570169689Skan } 571169689Skan 572169689Skan /* Now compare all the representative bitmaps with all other representative 573169689Skan bitmaps, to verify that they are all different. */ 574169689Skan for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++) 575169689Skan { 576169689Skan for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++) 577169689Skan { 578169689Skan if (bitmap_equal_p (first, second)) 579169689Skan { 580169689Skan error ("two different pointers with identical points-to sets but different name tags"); 581169689Skan debug_variable (VEC_index (tree, name_tag_reps, j)); 582169689Skan goto err; 583169689Skan } 584169689Skan } 585169689Skan } 586169689Skan 587169689Skan /* Lastly, clear out the visited flags. */ 588169689Skan for (i = 0; i < num_ssa_names; i++) 589169689Skan { 590169689Skan if (ssa_name (i)) 591169689Skan { 592169689Skan tree ptr = ssa_name (i); 593169689Skan struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr); 594169689Skan if (!TREE_VISITED (ptr) 595169689Skan || !POINTER_TYPE_P (TREE_TYPE (ptr)) 596169689Skan || !pi 597169689Skan || !pi->name_mem_tag) 598169689Skan continue; 599169689Skan TREE_VISITED (pi->name_mem_tag) = 0; 600169689Skan } 601169689Skan } 602169689Skan 603169689Skan /* We do not have to free the bitmaps or trees in the vectors, as 604169689Skan they are not owned by us. */ 605169689Skan VEC_free (bitmap, heap, pt_vars_for_reps); 606169689Skan VEC_free (tree, heap, name_tag_reps); 607169689Skan BITMAP_FREE (type_aliases); 608169689Skan return; 609169689Skan 610169689Skanerr: 611169689Skan debug_variable (VEC_index (tree, name_tag_reps, i)); 612169689Skan internal_error ("verify_name_tags failed"); 613169689Skan} 614169689Skan 615169689Skan 616169689Skan/* Verify the consistency of call clobbering information. */ 617169689Skanstatic void 618169689Skanverify_call_clobbering (void) 619169689Skan{ 620169689Skan unsigned int i; 621169689Skan bitmap_iterator bi; 622169689Skan tree var; 623169689Skan referenced_var_iterator rvi; 624169689Skan 625169689Skan /* At all times, the result of the DECL_CALL_CLOBBERED flag should 626169689Skan match the result of the call_clobbered_vars bitmap. Verify both 627169689Skan that everything in call_clobbered_vars is marked 628169689Skan DECL_CALL_CLOBBERED, and that everything marked 629169689Skan DECL_CALL_CLOBBERED is in call_clobbered_vars. */ 630169689Skan EXECUTE_IF_SET_IN_BITMAP (call_clobbered_vars, 0, i, bi) 631169689Skan { 632169689Skan var = referenced_var (i); 633169689Skan if (!MTAG_P (var) && !DECL_CALL_CLOBBERED (var)) 634169689Skan { 635169689Skan error ("variable in call_clobbered_vars but not marked DECL_CALL_CLOBBERED"); 636169689Skan debug_variable (var); 637169689Skan goto err; 638169689Skan } 639169689Skan } 640169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 641169689Skan { 642169689Skan if (!MTAG_P (var) && DECL_CALL_CLOBBERED (var) 643169689Skan && !bitmap_bit_p (call_clobbered_vars, DECL_UID (var))) 644169689Skan { 645169689Skan error ("variable marked DECL_CALL_CLOBBERED but not in call_clobbered_vars bitmap."); 646169689Skan debug_variable (var); 647169689Skan goto err; 648169689Skan } 649169689Skan } 650169689Skan return; 651169689Skan 652169689Skan err: 653169689Skan internal_error ("verify_call_clobbering failed"); 654169689Skan} 655169689Skan 656169689Skan/* Verify the consistency of aliasing information. */ 657169689Skan 658169689Skanstatic void 659169689Skanverify_alias_info (void) 660169689Skan{ 661169689Skan verify_flow_sensitive_alias_info (); 662169689Skan verify_name_tags (); 663169689Skan verify_call_clobbering (); 664169689Skan verify_flow_insensitive_alias_info (); 665169689Skan} 666169689Skan 667169689Skan 668169689Skan/* Verify common invariants in the SSA web. 669169689Skan TODO: verify the variable annotations. */ 670169689Skan 671169689Skanvoid 672169689Skanverify_ssa (bool check_modified_stmt) 673169689Skan{ 674169689Skan size_t i; 675169689Skan basic_block bb; 676169689Skan basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names); 677169689Skan ssa_op_iter iter; 678169689Skan tree op; 679169689Skan enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS]; 680169689Skan bitmap names_defined_in_bb = BITMAP_ALLOC (NULL); 681169689Skan 682169689Skan gcc_assert (!need_ssa_update_p ()); 683169689Skan 684169689Skan verify_stmts (); 685169689Skan 686169689Skan timevar_push (TV_TREE_SSA_VERIFY); 687169689Skan 688169689Skan /* Keep track of SSA names present in the IL. */ 689169689Skan for (i = 1; i < num_ssa_names; i++) 690169689Skan { 691169689Skan tree name = ssa_name (i); 692169689Skan if (name) 693169689Skan { 694169689Skan tree stmt; 695169689Skan TREE_VISITED (name) = 0; 696169689Skan 697169689Skan stmt = SSA_NAME_DEF_STMT (name); 698169689Skan if (!IS_EMPTY_STMT (stmt)) 699169689Skan { 700169689Skan basic_block bb = bb_for_stmt (stmt); 701169689Skan verify_def (bb, definition_block, 702169689Skan name, stmt, !is_gimple_reg (name)); 703169689Skan 704169689Skan } 705169689Skan } 706169689Skan } 707169689Skan 708169689Skan calculate_dominance_info (CDI_DOMINATORS); 709169689Skan 710169689Skan /* Now verify all the uses and make sure they agree with the definitions 711169689Skan found in the previous pass. */ 712169689Skan FOR_EACH_BB (bb) 713169689Skan { 714169689Skan edge e; 715169689Skan tree phi; 716169689Skan edge_iterator ei; 717169689Skan block_stmt_iterator bsi; 718169689Skan 719169689Skan /* Make sure that all edges have a clear 'aux' field. */ 720169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 721169689Skan { 722169689Skan if (e->aux) 723169689Skan { 724169689Skan error ("AUX pointer initialized for edge %d->%d", e->src->index, 725169689Skan e->dest->index); 726169689Skan goto err; 727169689Skan } 728169689Skan } 729169689Skan 730169689Skan /* Verify the arguments for every PHI node in the block. */ 731169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 732169689Skan { 733169689Skan if (verify_phi_args (phi, bb, definition_block)) 734169689Skan goto err; 735169689Skan bitmap_set_bit (names_defined_in_bb, 736169689Skan SSA_NAME_VERSION (PHI_RESULT (phi))); 737169689Skan } 738169689Skan 739169689Skan /* Now verify all the uses and vuses in every statement of the block. */ 740169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 741169689Skan { 742169689Skan tree stmt = bsi_stmt (bsi); 743169689Skan use_operand_p use_p; 744169689Skan 745169689Skan if (check_modified_stmt && stmt_modified_p (stmt)) 746169689Skan { 747169689Skan error ("stmt (%p) marked modified after optimization pass : ", 748169689Skan (void *)stmt); 749169689Skan print_generic_stmt (stderr, stmt, TDF_VOPS); 750169689Skan goto err; 751169689Skan } 752169689Skan 753169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 754169689Skan && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME) 755169689Skan { 756169689Skan tree lhs, base_address; 757169689Skan 758169689Skan lhs = TREE_OPERAND (stmt, 0); 759169689Skan base_address = get_base_address (lhs); 760169689Skan 761169689Skan if (base_address 762169689Skan && SSA_VAR_P (base_address) 763169689Skan && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF)) 764169689Skan { 765169689Skan error ("statement makes a memory store, but has no " 766169689Skan "V_MAY_DEFS nor V_MUST_DEFS"); 767169689Skan print_generic_stmt (stderr, stmt, TDF_VOPS); 768169689Skan goto err; 769169689Skan } 770169689Skan } 771169689Skan 772169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, 773169689Skan SSA_OP_ALL_USES | SSA_OP_ALL_KILLS) 774169689Skan { 775169689Skan op = USE_FROM_PTR (use_p); 776169689Skan if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)], 777169689Skan use_p, stmt, false, !is_gimple_reg (op), 778169689Skan names_defined_in_bb)) 779169689Skan goto err; 780169689Skan } 781169689Skan 782169689Skan FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS) 783169689Skan bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op)); 784169689Skan } 785169689Skan 786169689Skan bitmap_clear (names_defined_in_bb); 787169689Skan } 788169689Skan 789169689Skan /* Finally, verify alias information. */ 790169689Skan verify_alias_info (); 791169689Skan 792169689Skan free (definition_block); 793169689Skan 794169689Skan /* Restore the dominance information to its prior known state, so 795169689Skan that we do not perturb the compiler's subsequent behavior. */ 796169689Skan if (orig_dom_state == DOM_NONE) 797169689Skan free_dominance_info (CDI_DOMINATORS); 798169689Skan else 799169689Skan dom_computed[CDI_DOMINATORS] = orig_dom_state; 800169689Skan 801169689Skan BITMAP_FREE (names_defined_in_bb); 802169689Skan timevar_pop (TV_TREE_SSA_VERIFY); 803169689Skan return; 804169689Skan 805169689Skanerr: 806169689Skan internal_error ("verify_ssa failed"); 807169689Skan} 808169689Skan 809169689Skan/* Return true if the uid in both int tree maps are equal. */ 810169689Skan 811169689Skanint 812169689Skanint_tree_map_eq (const void *va, const void *vb) 813169689Skan{ 814169689Skan const struct int_tree_map *a = (const struct int_tree_map *) va; 815169689Skan const struct int_tree_map *b = (const struct int_tree_map *) vb; 816169689Skan return (a->uid == b->uid); 817169689Skan} 818169689Skan 819169689Skan/* Hash a UID in a int_tree_map. */ 820169689Skan 821169689Skanunsigned int 822169689Skanint_tree_map_hash (const void *item) 823169689Skan{ 824169689Skan return ((const struct int_tree_map *)item)->uid; 825169689Skan} 826169689Skan 827169689Skan 828169689Skan/* Initialize global DFA and SSA structures. */ 829169689Skan 830169689Skanvoid 831169689Skaninit_tree_ssa (void) 832169689Skan{ 833169689Skan referenced_vars = htab_create_ggc (20, int_tree_map_hash, 834169689Skan int_tree_map_eq, NULL); 835169689Skan default_defs = htab_create_ggc (20, int_tree_map_hash, int_tree_map_eq, NULL); 836169689Skan call_clobbered_vars = BITMAP_ALLOC (NULL); 837169689Skan addressable_vars = BITMAP_ALLOC (NULL); 838169689Skan init_alias_heapvars (); 839169689Skan init_ssanames (); 840169689Skan init_phinodes (); 841169689Skan global_var = NULL_TREE; 842169689Skan aliases_computed_p = false; 843169689Skan} 844169689Skan 845169689Skan 846169689Skan/* Deallocate memory associated with SSA data structures for FNDECL. */ 847169689Skan 848169689Skanvoid 849169689Skandelete_tree_ssa (void) 850169689Skan{ 851169689Skan size_t i; 852169689Skan basic_block bb; 853169689Skan block_stmt_iterator bsi; 854169689Skan referenced_var_iterator rvi; 855169689Skan tree var; 856169689Skan 857169689Skan /* Release any ssa_names still in use. */ 858169689Skan for (i = 0; i < num_ssa_names; i++) 859169689Skan { 860169689Skan tree var = ssa_name (i); 861169689Skan if (var && TREE_CODE (var) == SSA_NAME) 862169689Skan { 863169689Skan SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var)); 864169689Skan SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var)); 865169689Skan } 866169689Skan release_ssa_name (var); 867169689Skan } 868169689Skan 869169689Skan /* Remove annotations from every tree in the function. */ 870169689Skan FOR_EACH_BB (bb) 871169689Skan { 872169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 873169689Skan { 874169689Skan tree stmt = bsi_stmt (bsi); 875169689Skan stmt_ann_t ann = get_stmt_ann (stmt); 876169689Skan 877169689Skan free_ssa_operands (&ann->operands); 878169689Skan ann->addresses_taken = 0; 879169689Skan mark_stmt_modified (stmt); 880169689Skan } 881169689Skan set_phi_nodes (bb, NULL); 882169689Skan } 883169689Skan 884169689Skan /* Remove annotations from every referenced variable. */ 885169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 886169689Skan { 887169689Skan ggc_free (var->common.ann); 888169689Skan var->common.ann = NULL; 889169689Skan } 890169689Skan htab_delete (referenced_vars); 891169689Skan referenced_vars = NULL; 892169689Skan 893169689Skan fini_ssanames (); 894169689Skan fini_phinodes (); 895169689Skan 896169689Skan global_var = NULL_TREE; 897169689Skan 898169689Skan htab_delete (default_defs); 899169689Skan BITMAP_FREE (call_clobbered_vars); 900169689Skan call_clobbered_vars = NULL; 901169689Skan BITMAP_FREE (addressable_vars); 902169689Skan addressable_vars = NULL; 903169689Skan modified_noreturn_calls = NULL; 904169689Skan aliases_computed_p = false; 905169689Skan delete_alias_heapvars (); 906169689Skan gcc_assert (!need_ssa_update_p ()); 907169689Skan} 908169689Skan 909169689Skan 910169689Skan/* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a 911169689Skan useless type conversion, otherwise return false. */ 912169689Skan 913169689Skanbool 914169689Skantree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type) 915169689Skan{ 916169689Skan if (inner_type == outer_type) 917169689Skan return true; 918169689Skan 919169689Skan /* Changes in machine mode are never useless conversions. */ 920169689Skan if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type)) 921169689Skan return false; 922169689Skan 923169689Skan /* If the inner and outer types are effectively the same, then 924169689Skan strip the type conversion and enter the equivalence into 925169689Skan the table. */ 926169689Skan if (lang_hooks.types_compatible_p (inner_type, outer_type)) 927169689Skan return true; 928169689Skan 929169689Skan /* If both types are pointers and the outer type is a (void *), then 930169689Skan the conversion is not necessary. The opposite is not true since 931169689Skan that conversion would result in a loss of information if the 932169689Skan equivalence was used. Consider an indirect function call where 933169689Skan we need to know the exact type of the function to correctly 934169689Skan implement the ABI. */ 935169689Skan else if (POINTER_TYPE_P (inner_type) 936169689Skan && POINTER_TYPE_P (outer_type) 937169689Skan && TYPE_REF_CAN_ALIAS_ALL (inner_type) 938169689Skan == TYPE_REF_CAN_ALIAS_ALL (outer_type) 939169689Skan && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE) 940169689Skan return true; 941169689Skan 942169689Skan /* Don't lose casts between pointers to volatile and non-volatile 943169689Skan qualified types. Doing so would result in changing the semantics 944169689Skan of later accesses. */ 945169689Skan else if (POINTER_TYPE_P (inner_type) 946169689Skan && POINTER_TYPE_P (outer_type) 947169689Skan && TYPE_VOLATILE (TREE_TYPE (outer_type)) 948169689Skan != TYPE_VOLATILE (TREE_TYPE (inner_type))) 949169689Skan return false; 950169689Skan 951169689Skan /* Pointers/references are equivalent if their pointed to types 952169689Skan are effectively the same. This allows to strip conversions between 953169689Skan pointer types with different type qualifiers. */ 954169689Skan else if (POINTER_TYPE_P (inner_type) 955169689Skan && POINTER_TYPE_P (outer_type) 956169689Skan && TYPE_REF_CAN_ALIAS_ALL (inner_type) 957169689Skan == TYPE_REF_CAN_ALIAS_ALL (outer_type) 958169689Skan && lang_hooks.types_compatible_p (TREE_TYPE (inner_type), 959169689Skan TREE_TYPE (outer_type))) 960169689Skan return true; 961169689Skan 962169689Skan /* If both the inner and outer types are integral types, then the 963169689Skan conversion is not necessary if they have the same mode and 964169689Skan signedness and precision, and both or neither are boolean. Some 965169689Skan code assumes an invariant that boolean types stay boolean and do 966169689Skan not become 1-bit bit-field types. Note that types with precision 967169689Skan not using all bits of the mode (such as bit-field types in C) 968169689Skan mean that testing of precision is necessary. */ 969169689Skan else if (INTEGRAL_TYPE_P (inner_type) 970169689Skan && INTEGRAL_TYPE_P (outer_type) 971169689Skan && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type) 972169689Skan && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type) 973169689Skan && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type)) 974169689Skan && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type))) 975169689Skan { 976169689Skan bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE); 977169689Skan bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE); 978169689Skan if (first_boolean == second_boolean) 979169689Skan return true; 980169689Skan } 981169689Skan 982169689Skan /* Recurse for complex types. */ 983169689Skan else if (TREE_CODE (inner_type) == COMPLEX_TYPE 984169689Skan && TREE_CODE (outer_type) == COMPLEX_TYPE 985169689Skan && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type), 986169689Skan TREE_TYPE (inner_type))) 987169689Skan return true; 988169689Skan 989169689Skan return false; 990169689Skan} 991169689Skan 992169689Skan/* Return true if EXPR is a useless type conversion, otherwise return 993169689Skan false. */ 994169689Skan 995169689Skanbool 996169689Skantree_ssa_useless_type_conversion (tree expr) 997169689Skan{ 998169689Skan /* If we have an assignment that merely uses a NOP_EXPR to change 999169689Skan the top of the RHS to the type of the LHS and the type conversion 1000169689Skan is "safe", then strip away the type conversion so that we can 1001169689Skan enter LHS = RHS into the const_and_copies table. */ 1002169689Skan if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR 1003169689Skan || TREE_CODE (expr) == VIEW_CONVERT_EXPR 1004169689Skan || TREE_CODE (expr) == NON_LVALUE_EXPR) 1005169689Skan return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr), 1006169689Skan TREE_TYPE (TREE_OPERAND (expr, 1007169689Skan 0))); 1008169689Skan 1009169689Skan 1010169689Skan return false; 1011169689Skan} 1012169689Skan 1013169689Skan/* Returns true if statement STMT may read memory. */ 1014169689Skan 1015169689Skanbool 1016169689Skanstmt_references_memory_p (tree stmt) 1017169689Skan{ 1018169689Skan stmt_ann_t ann = stmt_ann (stmt); 1019169689Skan 1020169689Skan if (ann->has_volatile_ops) 1021169689Skan return true; 1022169689Skan 1023169689Skan return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)); 1024169689Skan} 1025169689Skan 1026169689Skan/* Internal helper for walk_use_def_chains. VAR, FN and DATA are as 1027169689Skan described in walk_use_def_chains. 1028169689Skan 1029169689Skan VISITED is a pointer set used to mark visited SSA_NAMEs to avoid 1030169689Skan infinite loops. We used to have a bitmap for this to just mark 1031169689Skan SSA versions we had visited. But non-sparse bitmaps are way too 1032169689Skan expensive, while sparse bitmaps may cause quadratic behavior. 1033169689Skan 1034169689Skan IS_DFS is true if the caller wants to perform a depth-first search 1035169689Skan when visiting PHI nodes. A DFS will visit each PHI argument and 1036169689Skan call FN after each one. Otherwise, all the arguments are 1037169689Skan visited first and then FN is called with each of the visited 1038169689Skan arguments in a separate pass. */ 1039169689Skan 1040169689Skanstatic bool 1041169689Skanwalk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data, 1042169689Skan struct pointer_set_t *visited, bool is_dfs) 1043169689Skan{ 1044169689Skan tree def_stmt; 1045169689Skan 1046169689Skan if (pointer_set_insert (visited, var)) 1047169689Skan return false; 1048169689Skan 1049169689Skan def_stmt = SSA_NAME_DEF_STMT (var); 1050169689Skan 1051169689Skan if (TREE_CODE (def_stmt) != PHI_NODE) 1052169689Skan { 1053169689Skan /* If we reached the end of the use-def chain, call FN. */ 1054169689Skan return fn (var, def_stmt, data); 1055169689Skan } 1056169689Skan else 1057169689Skan { 1058169689Skan int i; 1059169689Skan 1060169689Skan /* When doing a breadth-first search, call FN before following the 1061169689Skan use-def links for each argument. */ 1062169689Skan if (!is_dfs) 1063169689Skan for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1064169689Skan if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1065169689Skan return true; 1066169689Skan 1067169689Skan /* Follow use-def links out of each PHI argument. */ 1068169689Skan for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1069169689Skan { 1070169689Skan tree arg = PHI_ARG_DEF (def_stmt, i); 1071169689Skan if (TREE_CODE (arg) == SSA_NAME 1072169689Skan && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs)) 1073169689Skan return true; 1074169689Skan } 1075169689Skan 1076169689Skan /* When doing a depth-first search, call FN after following the 1077169689Skan use-def links for each argument. */ 1078169689Skan if (is_dfs) 1079169689Skan for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) 1080169689Skan if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data)) 1081169689Skan return true; 1082169689Skan } 1083169689Skan 1084169689Skan return false; 1085169689Skan} 1086169689Skan 1087169689Skan 1088169689Skan 1089169689Skan/* Walk use-def chains starting at the SSA variable VAR. Call 1090169689Skan function FN at each reaching definition found. FN takes three 1091169689Skan arguments: VAR, its defining statement (DEF_STMT) and a generic 1092169689Skan pointer to whatever state information that FN may want to maintain 1093169689Skan (DATA). FN is able to stop the walk by returning true, otherwise 1094169689Skan in order to continue the walk, FN should return false. 1095169689Skan 1096169689Skan Note, that if DEF_STMT is a PHI node, the semantics are slightly 1097169689Skan different. The first argument to FN is no longer the original 1098169689Skan variable VAR, but the PHI argument currently being examined. If FN 1099169689Skan wants to get at VAR, it should call PHI_RESULT (PHI). 1100169689Skan 1101169689Skan If IS_DFS is true, this function will: 1102169689Skan 1103169689Skan 1- walk the use-def chains for all the PHI arguments, and, 1104169689Skan 2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments. 1105169689Skan 1106169689Skan If IS_DFS is false, the two steps above are done in reverse order 1107169689Skan (i.e., a breadth-first search). */ 1108169689Skan 1109169689Skan 1110169689Skanvoid 1111169689Skanwalk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data, 1112169689Skan bool is_dfs) 1113169689Skan{ 1114169689Skan tree def_stmt; 1115169689Skan 1116169689Skan gcc_assert (TREE_CODE (var) == SSA_NAME); 1117169689Skan 1118169689Skan def_stmt = SSA_NAME_DEF_STMT (var); 1119169689Skan 1120169689Skan /* We only need to recurse if the reaching definition comes from a PHI 1121169689Skan node. */ 1122169689Skan if (TREE_CODE (def_stmt) != PHI_NODE) 1123169689Skan (*fn) (var, def_stmt, data); 1124169689Skan else 1125169689Skan { 1126169689Skan struct pointer_set_t *visited = pointer_set_create (); 1127169689Skan walk_use_def_chains_1 (var, fn, data, visited, is_dfs); 1128169689Skan pointer_set_destroy (visited); 1129169689Skan } 1130169689Skan} 1131169689Skan 1132169689Skan 1133169689Skan/* Emit warnings for uninitialized variables. This is done in two passes. 1134169689Skan 1135169689Skan The first pass notices real uses of SSA names with default definitions. 1136169689Skan Such uses are unconditionally uninitialized, and we can be certain that 1137169689Skan such a use is a mistake. This pass is run before most optimizations, 1138169689Skan so that we catch as many as we can. 1139169689Skan 1140169689Skan The second pass follows PHI nodes to find uses that are potentially 1141169689Skan uninitialized. In this case we can't necessarily prove that the use 1142169689Skan is really uninitialized. This pass is run after most optimizations, 1143169689Skan so that we thread as many jumps and possible, and delete as much dead 1144169689Skan code as possible, in order to reduce false positives. We also look 1145169689Skan again for plain uninitialized variables, since optimization may have 1146169689Skan changed conditionally uninitialized to unconditionally uninitialized. */ 1147169689Skan 1148169689Skan/* Emit a warning for T, an SSA_NAME, being uninitialized. The exact 1149169689Skan warning text is in MSGID and LOCUS may contain a location or be null. */ 1150169689Skan 1151169689Skanstatic void 1152169689Skanwarn_uninit (tree t, const char *gmsgid, void *data) 1153169689Skan{ 1154169689Skan tree var = SSA_NAME_VAR (t); 1155169689Skan tree def = SSA_NAME_DEF_STMT (t); 1156169689Skan tree context = (tree) data; 1157169689Skan location_t *locus, *fun_locus; 1158169689Skan 1159169689Skan /* Default uses (indicated by an empty definition statement), 1160169689Skan are uninitialized. */ 1161169689Skan if (!IS_EMPTY_STMT (def)) 1162169689Skan return; 1163169689Skan 1164169689Skan /* Except for PARMs of course, which are always initialized. */ 1165169689Skan if (TREE_CODE (var) == PARM_DECL) 1166169689Skan return; 1167169689Skan 1168169689Skan /* Hard register variables get their initial value from the ether. */ 1169169689Skan if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var)) 1170169689Skan return; 1171169689Skan 1172169689Skan /* TREE_NO_WARNING either means we already warned, or the front end 1173169689Skan wishes to suppress the warning. */ 1174169689Skan if (TREE_NO_WARNING (var)) 1175169689Skan return; 1176169689Skan 1177169689Skan locus = (context != NULL && EXPR_HAS_LOCATION (context) 1178169689Skan ? EXPR_LOCUS (context) 1179169689Skan : &DECL_SOURCE_LOCATION (var)); 1180169689Skan warning (0, gmsgid, locus, var); 1181169689Skan fun_locus = &DECL_SOURCE_LOCATION (cfun->decl); 1182169689Skan if (locus->file != fun_locus->file 1183169689Skan || locus->line < fun_locus->line 1184169689Skan || locus->line > cfun->function_end_locus.line) 1185169689Skan inform ("%J%qD was declared here", var, var); 1186169689Skan 1187169689Skan TREE_NO_WARNING (var) = 1; 1188169689Skan} 1189169689Skan 1190169689Skan/* Called via walk_tree, look for SSA_NAMEs that have empty definitions 1191169689Skan and warn about them. */ 1192169689Skan 1193169689Skanstatic tree 1194169689Skanwarn_uninitialized_var (tree *tp, int *walk_subtrees, void *data) 1195169689Skan{ 1196169689Skan tree t = *tp; 1197169689Skan 1198169689Skan switch (TREE_CODE (t)) 1199169689Skan { 1200169689Skan case SSA_NAME: 1201169689Skan /* We only do data flow with SSA_NAMEs, so that's all we 1202169689Skan can warn about. */ 1203169689Skan warn_uninit (t, "%H%qD is used uninitialized in this function", data); 1204169689Skan *walk_subtrees = 0; 1205169689Skan break; 1206169689Skan 1207169689Skan case REALPART_EXPR: 1208169689Skan case IMAGPART_EXPR: 1209169689Skan /* The total store transformation performed during gimplification 1210169689Skan creates uninitialized variable uses. If all is well, these will 1211169689Skan be optimized away, so don't warn now. */ 1212169689Skan if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME) 1213169689Skan *walk_subtrees = 0; 1214169689Skan break; 1215169689Skan 1216169689Skan default: 1217169689Skan if (IS_TYPE_OR_DECL_P (t)) 1218169689Skan *walk_subtrees = 0; 1219169689Skan break; 1220169689Skan } 1221169689Skan 1222169689Skan return NULL_TREE; 1223169689Skan} 1224169689Skan 1225169689Skan/* Look for inputs to PHI that are SSA_NAMEs that have empty definitions 1226169689Skan and warn about them. */ 1227169689Skan 1228169689Skanstatic void 1229169689Skanwarn_uninitialized_phi (tree phi) 1230169689Skan{ 1231169689Skan int i, n = PHI_NUM_ARGS (phi); 1232169689Skan 1233169689Skan /* Don't look at memory tags. */ 1234169689Skan if (!is_gimple_reg (PHI_RESULT (phi))) 1235169689Skan return; 1236169689Skan 1237169689Skan for (i = 0; i < n; ++i) 1238169689Skan { 1239169689Skan tree op = PHI_ARG_DEF (phi, i); 1240169689Skan if (TREE_CODE (op) == SSA_NAME) 1241169689Skan warn_uninit (op, "%H%qD may be used uninitialized in this function", 1242169689Skan NULL); 1243169689Skan } 1244169689Skan} 1245169689Skan 1246169689Skanstatic unsigned int 1247169689Skanexecute_early_warn_uninitialized (void) 1248169689Skan{ 1249169689Skan block_stmt_iterator bsi; 1250169689Skan basic_block bb; 1251169689Skan 1252169689Skan FOR_EACH_BB (bb) 1253169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1254169689Skan { 1255169689Skan tree context = bsi_stmt (bsi); 1256169689Skan walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var, 1257169689Skan context, NULL); 1258169689Skan } 1259169689Skan return 0; 1260169689Skan} 1261169689Skan 1262169689Skanstatic unsigned int 1263169689Skanexecute_late_warn_uninitialized (void) 1264169689Skan{ 1265169689Skan basic_block bb; 1266169689Skan tree phi; 1267169689Skan 1268169689Skan /* Re-do the plain uninitialized variable check, as optimization may have 1269169689Skan straightened control flow. Do this first so that we don't accidentally 1270169689Skan get a "may be" warning when we'd have seen an "is" warning later. */ 1271169689Skan execute_early_warn_uninitialized (); 1272169689Skan 1273169689Skan FOR_EACH_BB (bb) 1274169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1275169689Skan warn_uninitialized_phi (phi); 1276169689Skan return 0; 1277169689Skan} 1278169689Skan 1279169689Skanstatic bool 1280169689Skangate_warn_uninitialized (void) 1281169689Skan{ 1282169689Skan return warn_uninitialized != 0; 1283169689Skan} 1284169689Skan 1285169689Skanstruct tree_opt_pass pass_early_warn_uninitialized = 1286169689Skan{ 1287169689Skan NULL, /* name */ 1288169689Skan gate_warn_uninitialized, /* gate */ 1289169689Skan execute_early_warn_uninitialized, /* execute */ 1290169689Skan NULL, /* sub */ 1291169689Skan NULL, /* next */ 1292169689Skan 0, /* static_pass_number */ 1293169689Skan 0, /* tv_id */ 1294169689Skan PROP_ssa, /* properties_required */ 1295169689Skan 0, /* properties_provided */ 1296169689Skan 0, /* properties_destroyed */ 1297169689Skan 0, /* todo_flags_start */ 1298169689Skan 0, /* todo_flags_finish */ 1299169689Skan 0 /* letter */ 1300169689Skan}; 1301169689Skan 1302169689Skanstruct tree_opt_pass pass_late_warn_uninitialized = 1303169689Skan{ 1304169689Skan NULL, /* name */ 1305169689Skan gate_warn_uninitialized, /* gate */ 1306169689Skan execute_late_warn_uninitialized, /* execute */ 1307169689Skan NULL, /* sub */ 1308169689Skan NULL, /* next */ 1309169689Skan 0, /* static_pass_number */ 1310169689Skan 0, /* tv_id */ 1311169689Skan PROP_ssa, /* properties_required */ 1312169689Skan 0, /* properties_provided */ 1313169689Skan 0, /* properties_destroyed */ 1314169689Skan 0, /* todo_flags_start */ 1315169689Skan 0, /* todo_flags_finish */ 1316169689Skan 0 /* letter */ 1317169689Skan}; 1318169689Skan 1319