gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, 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
  53 edge
  54 ssa_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
  82 void
  83 flush_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
 106 static bool
 107 verify_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
 162 static bool
 163 verify_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
 190 err:
 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
 217 static bool
 218 verify_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
 303 static bool
 304 verify_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
 361 error:
 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
 373 static void
 374 verify_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
 420 err:
 421   debug_variable (var);
 422   internal_error ("verify_flow_insensitive_alias_info failed");
 423 }
 424
 425
 426 static void
 427 verify_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
 486 err:
 487   debug_variable (ptr);
 488   internal_error ("verify_flow_sensitive_alias_info failed");
 489 }
 490
 491 DEF_VEC_P (bitmap);
 492 DEF_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
 505 static void
 506 verify_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
 610 err:
 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 aliasing information.  */
 617
 618 static void
 619 verify_alias_info (void)
 620 {
 621   verify_flow_sensitive_alias_info ();
 622   verify_name_tags ();
 623   verify_flow_insensitive_alias_info ();
 624 }
 625
 626
 627 /* Verify common invariants in the SSA web.
 628    TODO: verify the variable annotations.  */
 629
 630 void
 631 verify_ssa (bool check_modified_stmt)
 632 {
 633   size_t i;
 634   basic_block bb;
 635   basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
 636   ssa_op_iter iter;
 637   tree op;
 638   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
 639   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
 640
 641   gcc_assert (!need_ssa_update_p ());
 642
 643   verify_stmts ();
 644
 645   timevar_push (TV_TREE_SSA_VERIFY);
 646
 647   /* Keep track of SSA names present in the IL.  */
 648   for (i = 1; i < num_ssa_names; i++)
 649     {
 650       tree name = ssa_name (i);
 651       if (name)
 652         {
 653           tree stmt;
 654           TREE_VISITED (name) = 0;
 655
 656           stmt = SSA_NAME_DEF_STMT (name);
 657           if (!IS_EMPTY_STMT (stmt))
 658             {
 659               basic_block bb = bb_for_stmt (stmt);
 660               verify_def (bb, definition_block,
 661                           name, stmt, !is_gimple_reg (name));
 662
 663             }
 664         }
 665     }
 666
 667   calculate_dominance_info (CDI_DOMINATORS);
 668
 669   /* Now verify all the uses and make sure they agree with the definitions
 670      found in the previous pass.  */
 671   FOR_EACH_BB (bb)
 672     {
 673       edge e;
 674       tree phi;
 675       edge_iterator ei;
 676       block_stmt_iterator bsi;
 677
 678       /* Make sure that all edges have a clear 'aux' field.  */
 679       FOR_EACH_EDGE (e, ei, bb->preds)
 680         {
 681           if (e->aux)
 682             {
 683               error ("AUX pointer initialized for edge %d->%d", e->src->index,
 684                       e->dest->index);
 685               goto err;
 686             }
 687         }
 688
 689       /* Verify the arguments for every PHI node in the block.  */
 690       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 691         {
 692           if (verify_phi_args (phi, bb, definition_block))
 693             goto err;
 694           bitmap_set_bit (names_defined_in_bb,
 695                           SSA_NAME_VERSION (PHI_RESULT (phi)));
 696         }
 697
 698       /* Now verify all the uses and vuses in every statement of the block.  */
 699       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 700         {
 701           tree stmt = bsi_stmt (bsi);
 702           use_operand_p use_p;
 703
 704           if (check_modified_stmt && stmt_modified_p (stmt))
 705             {
 706               error ("stmt (%p) marked modified after optimization pass : ",
 707                      (void *)stmt);
 708               print_generic_stmt (stderr, stmt, TDF_VOPS);
 709               goto err;
 710             }
 711
 712           if (TREE_CODE (stmt) == MODIFY_EXPR
 713               && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 714             {
 715               tree lhs, base_address;
 716
 717               lhs = TREE_OPERAND (stmt, 0);
 718               base_address = get_base_address (lhs);
 719
 720               if (base_address
 721                   && SSA_VAR_P (base_address)
 722                   && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
 723                 {
 724                   error ("statement makes a memory store, but has no "
 725                          "V_MAY_DEFS nor V_MUST_DEFS");
 726                   print_generic_stmt (stderr, stmt, TDF_VOPS);
 727                   goto err;
 728                 }
 729             }
 730
 731           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
 732                                     SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 733             {
 734               op = USE_FROM_PTR (use_p);
 735               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 736                               use_p, stmt, false, !is_gimple_reg (op),
 737                               names_defined_in_bb))
 738                 goto err;
 739             }
 740
 741           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 742             bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 743         }
 744
 745       bitmap_clear (names_defined_in_bb);
 746     }
 747
 748   /* Finally, verify alias information.  */
 749   verify_alias_info ();
 750
 751   free (definition_block);
 752
 753   /* Restore the dominance information to its prior known state, so
 754      that we do not perturb the compiler's subsequent behavior.  */
 755   if (orig_dom_state == DOM_NONE)
 756     free_dominance_info (CDI_DOMINATORS);
 757   else
 758     dom_computed[CDI_DOMINATORS] = orig_dom_state;
 759
 760   BITMAP_FREE (names_defined_in_bb);
 761   timevar_pop (TV_TREE_SSA_VERIFY);
 762   return;
 763
 764 err:
 765   internal_error ("verify_ssa failed");
 766 }
 767
 768 /* Return true if the uid in both int tree maps are equal.  */
 769
 770 int
 771 int_tree_map_eq (const void *va, const void *vb)
 772 {
 773   const struct int_tree_map *a = (const struct int_tree_map *) va;
 774   const struct int_tree_map *b = (const struct int_tree_map *) vb;
 775   return (a->uid == b->uid);
 776 }
 777
 778 /* Hash a UID in a int_tree_map.  */
 779
 780 unsigned int
 781 int_tree_map_hash (const void *item)
 782 {
 783   return ((const struct int_tree_map *)item)->uid;
 784 }
 785
 786
 787 /* Initialize global DFA and SSA structures.  */
 788
 789 void
 790 init_tree_ssa (void)
 791 {
 792   referenced_vars = htab_create_ggc (20, int_tree_map_hash,
 793                                      int_tree_map_eq, NULL);
 794   default_defs = htab_create_ggc (20, int_tree_map_hash, int_tree_map_eq, NULL);
 795   call_clobbered_vars = BITMAP_ALLOC (NULL);
 796   addressable_vars = BITMAP_ALLOC (NULL);
 797   init_alias_heapvars ();
 798   init_ssanames ();
 799   init_phinodes ();
 800   global_var = NULL_TREE;
 801   aliases_computed_p = false;
 802 }
 803
 804
 805 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 806
 807 void
 808 delete_tree_ssa (void)
 809 {
 810   size_t i;
 811   basic_block bb;
 812   block_stmt_iterator bsi;
 813   referenced_var_iterator rvi;
 814   tree var;
 815
 816   /* Release any ssa_names still in use.  */
 817   for (i = 0; i < num_ssa_names; i++)
 818     {
 819       tree var = ssa_name (i);
 820       if (var && TREE_CODE (var) == SSA_NAME)
 821         {
 822           SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
 823           SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
 824         }
 825       release_ssa_name (var);
 826     }
 827
 828   /* Remove annotations from every tree in the function.  */
 829   FOR_EACH_BB (bb)
 830     {
 831       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 832         {
 833           tree stmt = bsi_stmt (bsi);
 834           stmt_ann_t ann = get_stmt_ann (stmt);
 835
 836           free_ssa_operands (&ann->operands);
 837           ann->addresses_taken = 0;
 838           mark_stmt_modified (stmt);
 839         }
 840       set_phi_nodes (bb, NULL);
 841     }
 842
 843   /* Remove annotations from every referenced variable.  */
 844   FOR_EACH_REFERENCED_VAR (var, rvi)
 845     {
 846       ggc_free (var->common.ann);
 847       var->common.ann = NULL;
 848     }
 849   htab_delete (referenced_vars);
 850   referenced_vars = NULL;
 851
 852   fini_ssanames ();
 853   fini_phinodes ();
 854
 855   global_var = NULL_TREE;
 856
 857   htab_delete (default_defs);
 858   BITMAP_FREE (call_clobbered_vars);
 859   call_clobbered_vars = NULL;
 860   BITMAP_FREE (addressable_vars);
 861   addressable_vars = NULL;
 862   modified_noreturn_calls = NULL;
 863   aliases_computed_p = false;
 864   delete_alias_heapvars ();
 865   gcc_assert (!need_ssa_update_p ());
 866 }
 867
 868
 869 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
 870    useless type conversion, otherwise return false.  */
 871
 872 bool
 873 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 874 {
 875   if (inner_type == outer_type)
 876     return true;
 877
 878   /* Changes in machine mode are never useless conversions.  */
 879   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
 880     return false;
 881
 882   /* If the inner and outer types are effectively the same, then
 883      strip the type conversion and enter the equivalence into
 884      the table.  */
 885   if (lang_hooks.types_compatible_p (inner_type, outer_type))
 886     return true;
 887
 888   /* If both types are pointers and the outer type is a (void *), then
 889      the conversion is not necessary.  The opposite is not true since
 890      that conversion would result in a loss of information if the
 891      equivalence was used.  Consider an indirect function call where
 892      we need to know the exact type of the function to correctly
 893      implement the ABI.  */
 894   else if (POINTER_TYPE_P (inner_type)
 895            && POINTER_TYPE_P (outer_type)
 896            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 897               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 898            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 899     return true;
 900
 901   /* Don't lose casts between pointers to volatile and non-volatile
 902      qualified types.  Doing so would result in changing the semantics
 903      of later accesses.  */
 904   else if (POINTER_TYPE_P (inner_type)
 905            && POINTER_TYPE_P (outer_type)
 906            && TYPE_VOLATILE (TREE_TYPE (outer_type))
 907               != TYPE_VOLATILE (TREE_TYPE (inner_type)))
 908     return false;
 909
 910   /* Pointers/references are equivalent if their pointed to types
 911      are effectively the same.  This allows to strip conversions between
 912      pointer types with different type qualifiers.  */
 913   else if (POINTER_TYPE_P (inner_type)
 914            && POINTER_TYPE_P (outer_type)
 915            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 916               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 917            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 918                                              TREE_TYPE (outer_type)))
 919     return true;
 920
 921   /* If both the inner and outer types are integral types, then the
 922      conversion is not necessary if they have the same mode and
 923      signedness and precision, and both or neither are boolean.  Some
 924      code assumes an invariant that boolean types stay boolean and do
 925      not become 1-bit bit-field types.  Note that types with precision
 926      not using all bits of the mode (such as bit-field types in C)
 927      mean that testing of precision is necessary.  */
 928   else if (INTEGRAL_TYPE_P (inner_type)
 929            && INTEGRAL_TYPE_P (outer_type)
 930            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 931            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)
 932            && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type))
 933            && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type)))
 934     {
 935       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 936       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 937       if (first_boolean == second_boolean)
 938         return true;
 939     }
 940
 941   /* Recurse for complex types.  */
 942   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 943            && TREE_CODE (outer_type) == COMPLEX_TYPE
 944            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 945                                                   TREE_TYPE (inner_type)))
 946     return true;
 947
 948   return false;
 949 }
 950
 951 /* Return true if EXPR is a useless type conversion, otherwise return
 952    false.  */
 953
 954 bool
 955 tree_ssa_useless_type_conversion (tree expr)
 956 {
 957   /* If we have an assignment that merely uses a NOP_EXPR to change
 958      the top of the RHS to the type of the LHS and the type conversion
 959      is "safe", then strip away the type conversion so that we can
 960      enter LHS = RHS into the const_and_copies table.  */
 961   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 962       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 963       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 964     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 965                                                TREE_TYPE (TREE_OPERAND (expr,
 966                                                                         0)));
 967
 968
 969   return false;
 970 }
 971
 972 /* Returns true if statement STMT may read memory.  */
 973
 974 bool
 975 stmt_references_memory_p (tree stmt)
 976 {
 977   stmt_ann_t ann = stmt_ann (stmt);
 978
 979   if (ann->has_volatile_ops)
 980     return true;
 981
 982   return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
 983 }
 984
 985 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 986    described in walk_use_def_chains.
 987
 988    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
 989       infinite loops.  We used to have a bitmap for this to just mark
 990       SSA versions we had visited.  But non-sparse bitmaps are way too
 991       expensive, while sparse bitmaps may cause quadratic behavior.
 992
 993    IS_DFS is true if the caller wants to perform a depth-first search
 994       when visiting PHI nodes.  A DFS will visit each PHI argument and
 995       call FN after each one.  Otherwise, all the arguments are
 996       visited first and then FN is called with each of the visited
 997       arguments in a separate pass.  */
 998
 999 static bool
1000 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1001                        struct pointer_set_t *visited, bool is_dfs)
1002 {
1003   tree def_stmt;
1004
1005   if (pointer_set_insert (visited, var))
1006     return false;
1007
1008   def_stmt = SSA_NAME_DEF_STMT (var);
1009
1010   if (TREE_CODE (def_stmt) != PHI_NODE)
1011     {
1012       /* If we reached the end of the use-def chain, call FN.  */
1013       return fn (var, def_stmt, data);
1014     }
1015   else
1016     {
1017       int i;
1018
1019       /* When doing a breadth-first search, call FN before following the
1020          use-def links for each argument.  */
1021       if (!is_dfs)
1022         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1023           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1024             return true;
1025
1026       /* Follow use-def links out of each PHI argument.  */
1027       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1028         {
1029           tree arg = PHI_ARG_DEF (def_stmt, i);
1030           if (TREE_CODE (arg) == SSA_NAME
1031               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1032             return true;
1033         }
1034
1035       /* When doing a depth-first search, call FN after following the
1036          use-def links for each argument.  */
1037       if (is_dfs)
1038         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1039           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1040             return true;
1041     }
1042
1043   return false;
1044 }
1045
1046
1047
1048 /* Walk use-def chains starting at the SSA variable VAR.  Call
1049    function FN at each reaching definition found.  FN takes three
1050    arguments: VAR, its defining statement (DEF_STMT) and a generic
1051    pointer to whatever state information that FN may want to maintain
1052    (DATA).  FN is able to stop the walk by returning true, otherwise
1053    in order to continue the walk, FN should return false.
1054
1055    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1056    different.  The first argument to FN is no longer the original
1057    variable VAR, but the PHI argument currently being examined.  If FN
1058    wants to get at VAR, it should call PHI_RESULT (PHI).
1059
1060    If IS_DFS is true, this function will:
1061
1062         1- walk the use-def chains for all the PHI arguments, and,
1063         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1064
1065    If IS_DFS is false, the two steps above are done in reverse order
1066    (i.e., a breadth-first search).  */
1067
1068
1069 void
1070 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1071                      bool is_dfs)
1072 {
1073   tree def_stmt;
1074
1075   gcc_assert (TREE_CODE (var) == SSA_NAME);
1076
1077   def_stmt = SSA_NAME_DEF_STMT (var);
1078
1079   /* We only need to recurse if the reaching definition comes from a PHI
1080      node.  */
1081   if (TREE_CODE (def_stmt) != PHI_NODE)
1082     (*fn) (var, def_stmt, data);
1083   else
1084     {
1085       struct pointer_set_t *visited = pointer_set_create ();
1086       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1087       pointer_set_destroy (visited);
1088     }
1089 }
1090
1091 \f
1092 /* Emit warnings for uninitialized variables.  This is done in two passes.
1093
1094    The first pass notices real uses of SSA names with default definitions.
1095    Such uses are unconditionally uninitialized, and we can be certain that
1096    such a use is a mistake.  This pass is run before most optimizations,
1097    so that we catch as many as we can.
1098
1099    The second pass follows PHI nodes to find uses that are potentially
1100    uninitialized.  In this case we can't necessarily prove that the use
1101    is really uninitialized.  This pass is run after most optimizations,
1102    so that we thread as many jumps and possible, and delete as much dead
1103    code as possible, in order to reduce false positives.  We also look
1104    again for plain uninitialized variables, since optimization may have
1105    changed conditionally uninitialized to unconditionally uninitialized.  */
1106
1107 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1108    warning text is in MSGID and LOCUS may contain a location or be null.  */
1109
1110 static void
1111 warn_uninit (tree t, const char *gmsgid, void *data)
1112 {
1113   tree var = SSA_NAME_VAR (t);
1114   tree def = SSA_NAME_DEF_STMT (t);
1115   tree context = (tree) data;
1116   location_t * locus;
1117
1118   /* Default uses (indicated by an empty definition statement),
1119      are uninitialized.  */
1120   if (!IS_EMPTY_STMT (def))
1121     return;
1122
1123   /* Except for PARMs of course, which are always initialized.  */
1124   if (TREE_CODE (var) == PARM_DECL)
1125     return;
1126
1127   /* Hard register variables get their initial value from the ether.  */
1128   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1129     return;
1130
1131   /* TREE_NO_WARNING either means we already warned, or the front end
1132      wishes to suppress the warning.  */
1133   if (TREE_NO_WARNING (var))
1134     return;
1135
1136   locus = (context != NULL && EXPR_HAS_LOCATION (context)
1137            ? EXPR_LOCUS (context)
1138            : &DECL_SOURCE_LOCATION (var));
1139   warning (0, gmsgid, locus, var);
1140   TREE_NO_WARNING (var) = 1;
1141 }
1142
1143 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1144    and warn about them.  */
1145
1146 static tree
1147 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1148 {
1149   tree t = *tp;
1150
1151   switch (TREE_CODE (t))
1152     {
1153     case SSA_NAME:
1154       /* We only do data flow with SSA_NAMEs, so that's all we
1155          can warn about.  */
1156       warn_uninit (t, "%H%qD is used uninitialized in this function", data);
1157       *walk_subtrees = 0;
1158       break;
1159
1160     case REALPART_EXPR:
1161     case IMAGPART_EXPR:
1162       /* The total store transformation performed during gimplification
1163          creates uninitialized variable uses.  If all is well, these will
1164          be optimized away, so don't warn now.  */
1165       if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1166         *walk_subtrees = 0;
1167       break;
1168
1169     default:
1170       if (IS_TYPE_OR_DECL_P (t))
1171         *walk_subtrees = 0;
1172       break;
1173     }
1174
1175   return NULL_TREE;
1176 }
1177
1178 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1179    and warn about them.  */
1180
1181 static void
1182 warn_uninitialized_phi (tree phi)
1183 {
1184   int i, n = PHI_NUM_ARGS (phi);
1185
1186   /* Don't look at memory tags.  */
1187   if (!is_gimple_reg (PHI_RESULT (phi)))
1188     return;
1189
1190   for (i = 0; i < n; ++i)
1191     {
1192       tree op = PHI_ARG_DEF (phi, i);
1193       if (TREE_CODE (op) == SSA_NAME)
1194         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1195                      NULL);
1196     }
1197 }
1198
1199 static unsigned int
1200 execute_early_warn_uninitialized (void)
1201 {
1202   block_stmt_iterator bsi;
1203   basic_block bb;
1204
1205   FOR_EACH_BB (bb)
1206     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1207       {
1208         tree context = bsi_stmt (bsi);
1209         walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1210                    context, NULL);
1211       }
1212   return 0;
1213 }
1214
1215 static unsigned int
1216 execute_late_warn_uninitialized (void)
1217 {
1218   basic_block bb;
1219   tree phi;
1220
1221   /* Re-do the plain uninitialized variable check, as optimization may have
1222      straightened control flow.  Do this first so that we don't accidentally
1223      get a "may be" warning when we'd have seen an "is" warning later.  */
1224   execute_early_warn_uninitialized ();
1225
1226   FOR_EACH_BB (bb)
1227     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1228       warn_uninitialized_phi (phi);
1229   return 0;
1230 }
1231
1232 static bool
1233 gate_warn_uninitialized (void)
1234 {
1235   return warn_uninitialized != 0;
1236 }
1237
1238 struct tree_opt_pass pass_early_warn_uninitialized =
1239 {
1240   NULL,                                 /* name */
1241   gate_warn_uninitialized,              /* gate */
1242   execute_early_warn_uninitialized,     /* execute */
1243   NULL,                                 /* sub */
1244   NULL,                                 /* next */
1245   0,                                    /* static_pass_number */
1246   0,                                    /* tv_id */
1247   PROP_ssa,                             /* properties_required */
1248   0,                                    /* properties_provided */
1249   0,                                    /* properties_destroyed */
1250   0,                                    /* todo_flags_start */
1251   0,                                    /* todo_flags_finish */
1252   0                                     /* letter */
1253 };
1254
1255 struct tree_opt_pass pass_late_warn_uninitialized =
1256 {
1257   NULL,                                 /* name */
1258   gate_warn_uninitialized,              /* gate */
1259   execute_late_warn_uninitialized,      /* execute */
1260   NULL,                                 /* sub */
1261   NULL,                                 /* next */
1262   0,                                    /* static_pass_number */
1263   0,                                    /* tv_id */
1264   PROP_ssa,                             /* properties_required */
1265   0,                                    /* properties_provided */
1266   0,                                    /* properties_destroyed */
1267   0,                                    /* todo_flags_start */
1268   0,                                    /* todo_flags_finish */
1269   0                                     /* letter */
1270 };
1271