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, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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 "errors.h"
  35 #include "expr.h"
  36 #include "function.h"
  37 #include "diagnostic.h"
  38 #include "bitmap.h"
  39 #include "pointer-set.h"
  40 #include "tree-flow.h"
  41 #include "tree-gimple.h"
  42 #include "tree-inline.h"
  43 #include "varray.h"
  44 #include "timevar.h"
  45 #include "hashtab.h"
  46 #include "tree-dump.h"
  47 #include "tree-pass.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, next;
  57   tree list = NULL, *last = &list;
  58   tree src, dst, node;
  59   int i;
  60
  61   /* Remove the appropriate PHI arguments in E's destination block.  */
  62   for (phi = phi_nodes (e->dest); phi; phi = next)
  63     {
  64       next = PHI_CHAIN (phi);
  65
  66       i = phi_arg_from_edge (phi, e);
  67       if (PHI_ARG_DEF (phi, i) == NULL_TREE)
  68         continue;
  69
  70       src = PHI_ARG_DEF (phi, i);
  71       dst = PHI_RESULT (phi);
  72       node = build_tree_list (dst, src);
  73       *last = node;
  74       last = &TREE_CHAIN (node);
  75     }
  76
  77   e = redirect_edge_succ_nodup (e, dest);
  78   PENDING_STMT (e) = list;
  79
  80   return e;
  81 }
  82
  83 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
  84    E->dest.  */
  85
  86 void
  87 flush_pending_stmts (edge e)
  88 {
  89   tree phi, arg;
  90
  91   if (!PENDING_STMT (e))
  92     return;
  93
  94   for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
  95        phi;
  96        phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
  97     {
  98       tree def = TREE_VALUE (arg);
  99       add_phi_arg (phi, def, e);
 100     }
 101
 102   PENDING_STMT (e) = NULL;
 103 }
 104
 105 /* Return true if SSA_NAME is malformed and mark it visited.
 106
 107    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
 108       operand.  */
 109
 110 static bool
 111 verify_ssa_name (tree ssa_name, bool is_virtual)
 112 {
 113   TREE_VISITED (ssa_name) = 1;
 114
 115   if (TREE_CODE (ssa_name) != SSA_NAME)
 116     {
 117       error ("Expected an SSA_NAME object");
 118       return true;
 119     }
 120
 121   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
 122     {
 123       error ("Type mismatch between an SSA_NAME and its symbol.");
 124       return true;
 125     }
 126
 127   if (SSA_NAME_IN_FREE_LIST (ssa_name))
 128     {
 129       error ("Found an SSA_NAME that had been released into the free pool");
 130       return true;
 131     }
 132
 133   if (is_virtual && is_gimple_reg (ssa_name))
 134     {
 135       error ("Found a virtual definition for a GIMPLE register");
 136       return true;
 137     }
 138
 139   if (!is_virtual && !is_gimple_reg (ssa_name))
 140     {
 141       error ("Found a real definition for a non-register");
 142       return true;
 143     }
 144
 145   return false;
 146 }
 147
 148
 149 /* Return true if the definition of SSA_NAME at block BB is malformed.
 150
 151    STMT is the statement where SSA_NAME is created.
 152
 153    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
 154       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
 155       it means that the block in that array slot contains the
 156       definition of SSA_NAME.
 157
 158    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 159       V_MUST_DEF.  */
 160
 161 static bool
 162 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 163             tree stmt, bool is_virtual)
 164 {
 165   if (verify_ssa_name (ssa_name, is_virtual))
 166     goto err;
 167
 168   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 169     {
 170       error ("SSA_NAME created in two different blocks %i and %i",
 171              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 172       goto err;
 173     }
 174
 175   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 176
 177   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 178     {
 179       error ("SSA_NAME_DEF_STMT is wrong");
 180       fprintf (stderr, "Expected definition statement:\n");
 181       print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
 182       fprintf (stderr, "\nActual definition statement:\n");
 183       print_generic_stmt (stderr, stmt, TDF_VOPS);
 184       goto err;
 185     }
 186
 187   return false;
 188
 189 err:
 190   fprintf (stderr, "while verifying SSA_NAME ");
 191   print_generic_expr (stderr, ssa_name, 0);
 192   fprintf (stderr, " in statement\n");
 193   print_generic_stmt (stderr, stmt, TDF_VOPS);
 194
 195   return true;
 196 }
 197
 198
 199 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 200    malformed.
 201
 202    DEF_BB is the block where SSA_NAME was found to be created.
 203
 204    IDOM contains immediate dominator information for the flowgraph.
 205
 206    CHECK_ABNORMAL is true if the caller wants to check whether this use
 207       is flowing through an abnormal edge (only used when checking PHI
 208       arguments).
 209
 210    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 211       V_MUST_DEF.
 212
 213    If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
 214      that are defined before STMT in basic block BB.  */
 215
 216 static bool
 217 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
 218             tree stmt, bool check_abnormal, bool is_virtual,
 219             bitmap names_defined_in_bb)
 220 {
 221   bool err = false;
 222
 223   err = verify_ssa_name (ssa_name, is_virtual);
 224
 225   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
 226       && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
 227     ; /* Default definitions have empty statements.  Nothing to do.  */
 228   else if (!def_bb)
 229     {
 230       error ("Missing definition");
 231       err = true;
 232     }
 233   else if (bb != def_bb
 234            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 235     {
 236       error ("Definition in block %i does not dominate use in block %i",
 237              def_bb->index, bb->index);
 238       err = true;
 239     }
 240   else if (bb == def_bb
 241            && names_defined_in_bb != NULL
 242            && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
 243     {
 244       error ("Definition in block %i follows the use", def_bb->index);
 245       err = true;
 246     }
 247
 248   if (check_abnormal
 249       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 250     {
 251       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 252       err = true;
 253     }
 254
 255   if (err)
 256     {
 257       fprintf (stderr, "for SSA_NAME: ");
 258       print_generic_expr (stderr, ssa_name, TDF_VOPS);
 259       fprintf (stderr, "in statement:\n");
 260       print_generic_stmt (stderr, stmt, TDF_VOPS);
 261     }
 262
 263   return err;
 264 }
 265
 266
 267 /* Return true if any of the arguments for PHI node PHI at block BB is
 268    malformed.
 269
 270    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 271       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 272       block in that array slot contains the definition of SSA_NAME.  */
 273
 274 static bool
 275 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 276 {
 277   edge e;
 278   bool err = false;
 279   unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
 280
 281   if (EDGE_COUNT (bb->preds) != phi_num_args)
 282     {
 283       error ("Incoming edge count does not match number of PHI arguments\n");
 284       err = true;
 285       goto error;
 286     }
 287
 288   for (i = 0; i < phi_num_args; i++)
 289     {
 290       tree op = PHI_ARG_DEF (phi, i);
 291
 292       e = EDGE_PRED (bb, i);
 293
 294       if (op == NULL_TREE)
 295         {
 296           error ("PHI argument is missing for edge %d->%d\n",
 297                  e->src->index,
 298                  e->dest->index);
 299           err = true;
 300           goto error;
 301         }
 302
 303       if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
 304         {
 305           error ("PHI argument is not SSA_NAME, or invariant");
 306           err = true;
 307         }
 308
 309       if (TREE_CODE (op) == SSA_NAME)
 310         err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
 311                           phi, e->flags & EDGE_ABNORMAL,
 312                           !is_gimple_reg (PHI_RESULT (phi)),
 313                           NULL);
 314
 315       if (e->dest != bb)
 316         {
 317           error ("Wrong edge %d->%d for PHI argument\n",
 318                  e->src->index, e->dest->index, bb->index);
 319           err = true;
 320         }
 321
 322       if (err)
 323         {
 324           fprintf (stderr, "PHI argument\n");
 325           print_generic_stmt (stderr, op, TDF_VOPS);
 326           goto error;
 327         }
 328     }
 329
 330 error:
 331   if (err)
 332     {
 333       fprintf (stderr, "for PHI node\n");
 334       print_generic_stmt (stderr, phi, TDF_VOPS);
 335     }
 336
 337
 338   return err;
 339 }
 340
 341
 342 static void
 343 verify_flow_insensitive_alias_info (void)
 344 {
 345   size_t i;
 346   tree var;
 347   bitmap visited = BITMAP_XMALLOC ();
 348
 349   for (i = 0; i < num_referenced_vars; i++)
 350     {
 351       size_t j;
 352       var_ann_t ann;
 353       varray_type may_aliases;
 354
 355       var = referenced_var (i);
 356       ann = var_ann (var);
 357       may_aliases = ann->may_aliases;
 358
 359       for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
 360         {
 361           tree alias = VARRAY_TREE (may_aliases, j);
 362
 363           bitmap_set_bit (visited, var_ann (alias)->uid);
 364
 365           if (!may_be_aliased (alias))
 366             {
 367               error ("Non-addressable variable inside an alias set.");
 368               debug_variable (alias);
 369               goto err;
 370             }
 371         }
 372     }
 373
 374   for (i = 0; i < num_referenced_vars; i++)
 375     {
 376       var_ann_t ann;
 377
 378       var = referenced_var (i);
 379       ann = var_ann (var);
 380
 381       if (ann->mem_tag_kind == NOT_A_TAG
 382           && ann->is_alias_tag
 383           && !bitmap_bit_p (visited, ann->uid))
 384         {
 385           error ("Addressable variable that is an alias tag but is not in any alias set.");
 386           goto err;
 387         }
 388     }
 389
 390   BITMAP_XFREE (visited);
 391   return;
 392
 393 err:
 394   debug_variable (var);
 395   internal_error ("verify_flow_insensitive_alias_info failed.");
 396 }
 397
 398
 399 static void
 400 verify_flow_sensitive_alias_info (void)
 401 {
 402   size_t i;
 403   tree ptr;
 404
 405   for (i = 1; i < num_ssa_names; i++)
 406     {
 407       tree var;
 408       var_ann_t ann;
 409       struct ptr_info_def *pi;
 410
 411
 412       ptr = ssa_name (i);
 413       if (!ptr)
 414         continue;
 415
 416       /* We only care for pointers that are actually referenced in the
 417          program.  */
 418       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
 419         continue;
 420
 421       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
 422          is only written-to only once in the return statement.
 423          Otherwise, aggregate RESULT_DECLs may be written-to more than
 424          once in virtual operands.  */
 425       var = SSA_NAME_VAR (ptr);
 426       if (TREE_CODE (var) == RESULT_DECL
 427           && is_gimple_reg (ptr))
 428         continue;
 429
 430       pi = SSA_NAME_PTR_INFO (ptr);
 431       if (pi == NULL)
 432         continue;
 433
 434       ann = var_ann (var);
 435       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
 436         {
 437           error ("Dereferenced pointers should have a name or a type tag");
 438           goto err;
 439         }
 440
 441       if (pi->name_mem_tag
 442           && !pi->pt_malloc
 443           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
 444         {
 445           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
 446           goto err;
 447         }
 448
 449       if (pi->value_escapes_p
 450           && pi->name_mem_tag
 451           && !is_call_clobbered (pi->name_mem_tag))
 452         {
 453           error ("Pointer escapes but its name tag is not call-clobbered.");
 454           goto err;
 455         }
 456     }
 457
 458   return;
 459
 460 err:
 461   debug_variable (ptr);
 462   internal_error ("verify_flow_sensitive_alias_info failed.");
 463 }
 464
 465 DEF_VEC_MALLOC_P (bitmap);
 466
 467 /* Verify that all name tags have different points to sets.
 468    This algorithm takes advantage of the fact that every variable with the
 469    same name tag must have the same points-to set.
 470    So we check a single variable for each name tag, and verify that its
 471    points-to set is different from every other points-to set for other name
 472    tags.
 473
 474    Additionally, given a pointer P_i with name tag NMT and type tag
 475    TMT, this function verified the alias set of TMT is a superset of
 476    the alias set of NMT.  */
 477
 478 static void
 479 verify_name_tags (void)
 480 {
 481   size_t i;
 482   size_t j;
 483   bitmap first, second;
 484   VEC (tree) *name_tag_reps = NULL;
 485   VEC (bitmap) *pt_vars_for_reps = NULL;
 486   bitmap type_aliases = BITMAP_XMALLOC ();
 487
 488   /* First we compute the name tag representatives and their points-to sets.  */
 489   for (i = 0; i < num_ssa_names; i++)
 490     {
 491       struct ptr_info_def *pi;
 492       tree tmt, ptr = ssa_name (i);
 493
 494       if (ptr == NULL_TREE)
 495         continue;
 496
 497       pi = SSA_NAME_PTR_INFO (ptr);
 498
 499       if (!TREE_VISITED (ptr)
 500           || !POINTER_TYPE_P (TREE_TYPE (ptr))
 501           || !pi
 502           || !pi->name_mem_tag
 503           || TREE_VISITED (pi->name_mem_tag))
 504         continue;
 505
 506       TREE_VISITED (pi->name_mem_tag) = 1;
 507
 508       if (pi->pt_vars == NULL)
 509         continue;
 510
 511       VEC_safe_push (tree, name_tag_reps, ptr);
 512       VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
 513
 514       /* Verify that alias set of PTR's type tag is a superset of the
 515          alias set of PTR's name tag.  */
 516       tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 517       if (tmt)
 518         {
 519           size_t i;
 520           varray_type aliases = var_ann (tmt)->may_aliases;
 521           bitmap_clear (type_aliases);
 522           for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
 523             {
 524               tree alias = VARRAY_TREE (aliases, i);
 525               bitmap_set_bit (type_aliases, var_ann (alias)->uid);
 526             }
 527
 528           /* When grouping, we may have added PTR's type tag into the
 529              alias set of PTR's name tag.  To prevent a false
 530              positive, pretend that TMT is in its own alias set.  */
 531           bitmap_set_bit (type_aliases, var_ann (tmt)->uid);
 532
 533           if (bitmap_equal_p (type_aliases, pi->pt_vars))
 534             continue;
 535
 536           if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
 537             {
 538               error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
 539               debug_variable (tmt);
 540               debug_variable (pi->name_mem_tag);
 541               goto err;
 542             }
 543         }
 544     }
 545
 546   /* Now compare all the representative bitmaps with all other representative
 547      bitmaps, to verify that they are all different.  */
 548   for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
 549     {
 550        for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
 551          {
 552            if (bitmap_equal_p (first, second))
 553              {
 554                error ("Two different pointers with identical points-to sets but different name tags");
 555                debug_variable (VEC_index (tree, name_tag_reps, j));
 556                goto err;
 557              }
 558          }
 559     }
 560
 561   /* Lastly, clear out the visited flags.  */
 562   for (i = 0; i < num_ssa_names; i++)
 563     {
 564       if (ssa_name (i))
 565         {
 566           tree ptr = ssa_name (i);
 567           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 568           if (!TREE_VISITED (ptr)
 569               || !POINTER_TYPE_P (TREE_TYPE (ptr))
 570               || !pi
 571               || !pi->name_mem_tag)
 572             continue;
 573           TREE_VISITED (pi->name_mem_tag) = 0;
 574         }
 575     }
 576
 577   VEC_free (bitmap, pt_vars_for_reps);
 578   BITMAP_FREE (type_aliases);
 579   return;
 580
 581 err:
 582   debug_variable (VEC_index (tree, name_tag_reps, i));
 583   internal_error ("verify_name_tags failed");
 584 }
 585
 586
 587 /* Verify the consistency of aliasing information.  */
 588
 589 static void
 590 verify_alias_info (void)
 591 {
 592   verify_flow_sensitive_alias_info ();
 593   verify_name_tags ();
 594   verify_flow_insensitive_alias_info ();
 595 }
 596
 597
 598 /* Verify common invariants in the SSA web.
 599    TODO: verify the variable annotations.  */
 600
 601 void
 602 verify_ssa (void)
 603 {
 604   size_t i;
 605   basic_block bb;
 606   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
 607   ssa_op_iter iter;
 608   tree op;
 609   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
 610   bitmap names_defined_in_bb = BITMAP_XMALLOC ();
 611
 612   timevar_push (TV_TREE_SSA_VERIFY);
 613
 614   /* Keep track of SSA names present in the IL.  */
 615   for (i = 1; i < num_ssa_names; i++)
 616     {
 617       tree name = ssa_name (i);
 618       if (name)
 619         {
 620           tree stmt;
 621           TREE_VISITED (name) = 0;
 622
 623           stmt = SSA_NAME_DEF_STMT (name);
 624           if (!IS_EMPTY_STMT (stmt))
 625             {
 626               basic_block bb = bb_for_stmt (stmt);
 627               verify_def (bb, definition_block,
 628                           name, stmt, !is_gimple_reg (name));
 629
 630             }
 631         }
 632     }
 633
 634   calculate_dominance_info (CDI_DOMINATORS);
 635
 636   /* Now verify all the uses and make sure they agree with the definitions
 637      found in the previous pass.  */
 638   FOR_EACH_BB (bb)
 639     {
 640       edge e;
 641       tree phi;
 642       edge_iterator ei;
 643       block_stmt_iterator bsi;
 644
 645       /* Make sure that all edges have a clear 'aux' field.  */
 646       FOR_EACH_EDGE (e, ei, bb->preds)
 647         {
 648           if (e->aux)
 649             {
 650               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 651                       e->dest->index);
 652               goto err;
 653             }
 654         }
 655
 656       /* Verify the arguments for every PHI node in the block.  */
 657       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 658         {
 659           if (verify_phi_args (phi, bb, definition_block))
 660             goto err;
 661           bitmap_set_bit (names_defined_in_bb,
 662                           SSA_NAME_VERSION (PHI_RESULT (phi)));
 663         }
 664
 665       /* Now verify all the uses and vuses in every statement of the block.  */
 666       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 667         {
 668           tree stmt = bsi_stmt (bsi);
 669
 670               get_stmt_operands (stmt);
 671
 672               if (stmt_ann (stmt)->makes_aliased_stores
 673                   && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
 674                 {
 675                   error ("Statement makes aliased stores, but has no V_MAY_DEFS");
 676                   print_generic_stmt (stderr, stmt, TDF_VOPS);
 677                   goto err;
 678                 }
 679
 680           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 681             {
 682               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 683                               op, stmt, false, !is_gimple_reg (op),
 684                               names_defined_in_bb))
 685                 goto err;
 686             }
 687
 688           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 689             {
 690               bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 691             }
 692         }
 693
 694       bitmap_clear (names_defined_in_bb);
 695     }
 696
 697   /* Finally, verify alias information.  */
 698   verify_alias_info ();
 699
 700   free (definition_block);
 701   /* Restore the dominance information to its prior known state, so
 702      that we do not perturb the compiler's subsequent behavior.  */
 703   if (orig_dom_state == DOM_NONE)
 704     free_dominance_info (CDI_DOMINATORS);
 705   else
 706     dom_computed[CDI_DOMINATORS] = orig_dom_state;
 707
 708   BITMAP_XFREE (names_defined_in_bb);
 709   timevar_pop (TV_TREE_SSA_VERIFY);
 710   return;
 711
 712 err:
 713   internal_error ("verify_ssa failed.");
 714 }
 715
 716
 717 /* Initialize global DFA and SSA structures.  */
 718
 719 void
 720 init_tree_ssa (void)
 721 {
 722   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 723   call_clobbered_vars = BITMAP_XMALLOC ();
 724   addressable_vars = BITMAP_XMALLOC ();
 725   init_ssa_operands ();
 726   init_ssanames ();
 727   init_phinodes ();
 728   global_var = NULL_TREE;
 729 }
 730
 731
 732 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 733
 734 void
 735 delete_tree_ssa (void)
 736 {
 737   size_t i;
 738   basic_block bb;
 739   block_stmt_iterator bsi;
 740
 741   /* Remove annotations from every tree in the function.  */
 742   FOR_EACH_BB (bb)
 743     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 744       {
 745         tree stmt = bsi_stmt (bsi);
 746         release_defs (stmt);
 747         ggc_free (stmt->common.ann);
 748         stmt->common.ann = NULL;
 749       }
 750
 751   /* Remove annotations from every referenced variable.  */
 752   if (referenced_vars)
 753     {
 754       for (i = 0; i < num_referenced_vars; i++)
 755         {
 756           tree var = referenced_var (i);
 757           ggc_free (var->common.ann);
 758           var->common.ann = NULL;
 759         }
 760       referenced_vars = NULL;
 761     }
 762
 763   fini_ssanames ();
 764   fini_phinodes ();
 765   fini_ssa_operands ();
 766
 767   global_var = NULL_TREE;
 768   BITMAP_XFREE (call_clobbered_vars);
 769   call_clobbered_vars = NULL;
 770   BITMAP_XFREE (addressable_vars);
 771   addressable_vars = NULL;
 772 }
 773
 774
 775 /* Return true if EXPR is a useless type conversion, otherwise return
 776    false.  */
 777
 778 bool
 779 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 780 {
 781   /* If the inner and outer types are effectively the same, then
 782      strip the type conversion and enter the equivalence into
 783      the table.  */
 784   if (inner_type == outer_type
 785      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 786     return true;
 787
 788   /* If both types are pointers and the outer type is a (void *), then
 789      the conversion is not necessary.  The opposite is not true since
 790      that conversion would result in a loss of information if the
 791      equivalence was used.  Consider an indirect function call where
 792      we need to know the exact type of the function to correctly
 793      implement the ABI.  */
 794   else if (POINTER_TYPE_P (inner_type)
 795            && POINTER_TYPE_P (outer_type)
 796            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 797            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 798               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 799            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 800     return true;
 801
 802   /* Pointers and references are equivalent once we get to GENERIC,
 803      so strip conversions that just switch between them.  */
 804   else if (POINTER_TYPE_P (inner_type)
 805            && POINTER_TYPE_P (outer_type)
 806            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 807            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 808               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 809            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 810                                              TREE_TYPE (outer_type)))
 811     return true;
 812
 813   /* If both the inner and outer types are integral types, then the
 814      conversion is not necessary if they have the same mode and
 815      signedness and precision, and both or neither are boolean.  Some
 816      code assumes an invariant that boolean types stay boolean and do
 817      not become 1-bit bit-field types.  Note that types with precision
 818      not using all bits of the mode (such as bit-field types in C)
 819      mean that testing of precision is necessary.  */
 820   else if (INTEGRAL_TYPE_P (inner_type)
 821            && INTEGRAL_TYPE_P (outer_type)
 822            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 823            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 824            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 825     {
 826       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 827       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 828       if (first_boolean == second_boolean)
 829         return true;
 830     }
 831
 832   /* Recurse for complex types.  */
 833   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 834            && TREE_CODE (outer_type) == COMPLEX_TYPE
 835            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 836                                                   TREE_TYPE (inner_type)))
 837     return true;
 838
 839   return false;
 840 }
 841
 842 /* Return true if EXPR is a useless type conversion, otherwise return
 843    false.  */
 844
 845 bool
 846 tree_ssa_useless_type_conversion (tree expr)
 847 {
 848   /* If we have an assignment that merely uses a NOP_EXPR to change
 849      the top of the RHS to the type of the LHS and the type conversion
 850      is "safe", then strip away the type conversion so that we can
 851      enter LHS = RHS into the const_and_copies table.  */
 852   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 853       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 854       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 855     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 856                                                TREE_TYPE (TREE_OPERAND (expr,
 857                                                                         0)));
 858
 859
 860   return false;
 861 }
 862
 863 /* Returns true if statement STMT may read memory.  */
 864
 865 bool
 866 stmt_references_memory_p (tree stmt)
 867 {
 868   stmt_ann_t ann;
 869
 870   get_stmt_operands (stmt);
 871   ann = stmt_ann (stmt);
 872
 873   if (ann->has_volatile_ops)
 874     return true;
 875
 876   return (NUM_VUSES (VUSE_OPS (ann)) > 0
 877           || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
 878           || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
 879 }
 880
 881 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 882    described in walk_use_def_chains.
 883
 884    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
 885       infinite loops.  We used to have a bitmap for this to just mark
 886       SSA versions we had visited.  But non-sparse bitmaps are way too
 887       expensive, while sparse bitmaps may cause quadratic behavior.
 888
 889    IS_DFS is true if the caller wants to perform a depth-first search
 890       when visiting PHI nodes.  A DFS will visit each PHI argument and
 891       call FN after each one.  Otherwise, all the arguments are
 892       visited first and then FN is called with each of the visited
 893       arguments in a separate pass.  */
 894
 895 static bool
 896 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 897                        struct pointer_set_t *visited, bool is_dfs)
 898 {
 899   tree def_stmt;
 900
 901   if (pointer_set_insert (visited, var))
 902     return false;
 903
 904   def_stmt = SSA_NAME_DEF_STMT (var);
 905
 906   if (TREE_CODE (def_stmt) != PHI_NODE)
 907     {
 908       /* If we reached the end of the use-def chain, call FN.  */
 909       return fn (var, def_stmt, data);
 910     }
 911   else
 912     {
 913       int i;
 914
 915       /* When doing a breadth-first search, call FN before following the
 916          use-def links for each argument.  */
 917       if (!is_dfs)
 918         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 919           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 920             return true;
 921
 922       /* Follow use-def links out of each PHI argument.  */
 923       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 924         {
 925           tree arg = PHI_ARG_DEF (def_stmt, i);
 926           if (TREE_CODE (arg) == SSA_NAME
 927               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
 928             return true;
 929         }
 930
 931       /* When doing a depth-first search, call FN after following the
 932          use-def links for each argument.  */
 933       if (is_dfs)
 934         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 935           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 936             return true;
 937     }
 938
 939   return false;
 940 }
 941
 942
 943
 944 /* Walk use-def chains starting at the SSA variable VAR.  Call
 945    function FN at each reaching definition found.  FN takes three
 946    arguments: VAR, its defining statement (DEF_STMT) and a generic
 947    pointer to whatever state information that FN may want to maintain
 948    (DATA).  FN is able to stop the walk by returning true, otherwise
 949    in order to continue the walk, FN should return false.
 950
 951    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 952    different.  The first argument to FN is no longer the original
 953    variable VAR, but the PHI argument currently being examined.  If FN
 954    wants to get at VAR, it should call PHI_RESULT (PHI).
 955
 956    If IS_DFS is true, this function will:
 957
 958         1- walk the use-def chains for all the PHI arguments, and,
 959         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
 960
 961    If IS_DFS is false, the two steps above are done in reverse order
 962    (i.e., a breadth-first search).  */
 963
 964
 965 void
 966 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
 967                      bool is_dfs)
 968 {
 969   tree def_stmt;
 970
 971   gcc_assert (TREE_CODE (var) == SSA_NAME);
 972
 973   def_stmt = SSA_NAME_DEF_STMT (var);
 974
 975   /* We only need to recurse if the reaching definition comes from a PHI
 976      node.  */
 977   if (TREE_CODE (def_stmt) != PHI_NODE)
 978     (*fn) (var, def_stmt, data);
 979   else
 980     {
 981       struct pointer_set_t *visited = pointer_set_create ();
 982       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
 983       pointer_set_destroy (visited);
 984     }
 985 }
 986
 987
 988 /* Replaces VAR with REPL in memory reference expression *X in
 989    statement STMT.  */
 990
 991 static void
 992 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 993 {
 994   tree new_var, ass_stmt, addr_var;
 995   basic_block bb;
 996   block_stmt_iterator bsi;
 997
 998   /* There is nothing special to handle in the other cases.  */
 999   if (TREE_CODE (repl) != ADDR_EXPR)
1000     return;
1001   addr_var = TREE_OPERAND (repl, 0);
1002
1003   while (handled_component_p (*x)
1004          || TREE_CODE (*x) == REALPART_EXPR
1005          || TREE_CODE (*x) == IMAGPART_EXPR)
1006     x = &TREE_OPERAND (*x, 0);
1007
1008   if (TREE_CODE (*x) != INDIRECT_REF
1009       || TREE_OPERAND (*x, 0) != var)
1010     return;
1011
1012   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
1013     {
1014       *x = addr_var;
1015       mark_new_vars_to_rename (stmt, vars_to_rename);
1016       return;
1017     }
1018
1019
1020   /* Frontends sometimes produce expressions like *&a instead of a[0].
1021      Create a temporary variable to handle this case.  */
1022   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
1023   new_var = duplicate_ssa_name (var, ass_stmt);
1024   TREE_OPERAND (*x, 0) = new_var;
1025   TREE_OPERAND (ass_stmt, 0) = new_var;
1026
1027   bb = bb_for_stmt (stmt);
1028   tree_block_label (bb);
1029   bsi = bsi_after_labels (bb);
1030   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
1031
1032   mark_new_vars_to_rename (stmt, vars_to_rename);
1033 }
1034
1035 /* Replaces immediate uses of VAR by REPL.  */
1036
1037 static void
1038 replace_immediate_uses (tree var, tree repl)
1039 {
1040   int i, j, n;
1041   dataflow_t df;
1042   tree stmt;
1043   bool mark_new_vars;
1044   ssa_op_iter iter;
1045   use_operand_p use_p;
1046
1047   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1048   n = num_immediate_uses (df);
1049
1050   for (i = 0; i < n; i++)
1051     {
1052       stmt = immediate_use (df, i);
1053
1054       if (TREE_CODE (stmt) == PHI_NODE)
1055         {
1056           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1057             if (PHI_ARG_DEF (stmt, j) == var)
1058               {
1059                 SET_PHI_ARG_DEF (stmt, j, repl);
1060                 if (TREE_CODE (repl) == SSA_NAME
1061                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1062                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1063               }
1064
1065           continue;
1066         }
1067
1068       get_stmt_operands (stmt);
1069       mark_new_vars = false;
1070       if (is_gimple_reg (SSA_NAME_VAR (var)))
1071         {
1072           if (TREE_CODE (stmt) == MODIFY_EXPR)
1073             {
1074               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1075               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1076             }
1077
1078           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1079             if (USE_FROM_PTR (use_p) == var)
1080               {
1081                 propagate_value (use_p, repl);
1082                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1083               }
1084         }
1085       else
1086         {
1087           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1088                                     SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1089             if (USE_FROM_PTR (use_p) == var)
1090               propagate_value (use_p, repl);
1091         }
1092
1093       /* FIXME.  If REPL is a constant, we need to fold STMT.
1094          However, fold_stmt wants a pointer to the statement, because
1095          it may happen that it needs to replace the whole statement
1096          with a new expression.  Since the current def-use machinery
1097          does not return pointers to statements, we call fold_stmt
1098          with the address of a local temporary, if that call changes
1099          the temporary then we fallback on looking for a proper
1100          pointer to STMT by scanning STMT's basic block.
1101
1102          Note that all this will become unnecessary soon.  This
1103          pass is being replaced with a proper copy propagation pass
1104          for 4.1 (dnovillo, 2004-09-17).  */
1105       if (TREE_CODE (repl) != SSA_NAME)
1106         {
1107           tree tmp = stmt;
1108           fold_stmt (&tmp);
1109           mark_new_vars = true;
1110           if (tmp != stmt)
1111             {
1112               block_stmt_iterator si = bsi_for_stmt (stmt);
1113               bsi_replace (&si, tmp, true);
1114               stmt = bsi_stmt (si);
1115             }
1116         }
1117
1118       /* If REPL is a pointer, it may have different memory tags associated
1119          with it.  For instance, VAR may have had a name tag while REPL
1120          only had a type tag.  In these cases, the virtual operands (if
1121          any) in the statement will refer to different symbols which need
1122          to be renamed.  */
1123       if (mark_new_vars)
1124         mark_new_vars_to_rename (stmt, vars_to_rename);
1125       else
1126         modify_stmt (stmt);
1127     }
1128 }
1129
1130 /* Gets the value VAR is equivalent to according to EQ_TO.  */
1131
1132 static tree
1133 get_eq_name (tree *eq_to, tree var)
1134 {
1135   unsigned ver;
1136   tree val = var;
1137
1138   while (TREE_CODE (val) == SSA_NAME)
1139     {
1140       ver = SSA_NAME_VERSION (val);
1141       if (!eq_to[ver])
1142         break;
1143
1144       val = eq_to[ver];
1145     }
1146
1147   while (TREE_CODE (var) == SSA_NAME)
1148     {
1149       ver = SSA_NAME_VERSION (var);
1150       if (!eq_to[ver])
1151         break;
1152
1153       var = eq_to[ver];
1154       eq_to[ver] = val;
1155     }
1156
1157   return val;
1158 }
1159
1160 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1161    its result is redundant to to EQ_TO array.  */
1162
1163 static void
1164 check_phi_redundancy (tree phi, tree *eq_to)
1165 {
1166   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1167   unsigned i, ver = SSA_NAME_VERSION (res), n;
1168   dataflow_t df;
1169
1170   /* It is unlikely that such large phi node would be redundant.  */
1171   if (PHI_NUM_ARGS (phi) > 16)
1172     return;
1173
1174   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1175     {
1176       def = PHI_ARG_DEF (phi, i);
1177
1178       if (TREE_CODE (def) == SSA_NAME)
1179         {
1180           def = get_eq_name (eq_to, def);
1181           if (def == res)
1182             continue;
1183         }
1184
1185       if (val
1186           && !operand_equal_for_phi_arg_p (val, def))
1187         return;
1188
1189       val = def;
1190     }
1191
1192   /* At least one of the arguments should not be equal to the result, or
1193      something strange is happening.  */
1194   gcc_assert (val);
1195
1196   if (get_eq_name (eq_to, res) == val)
1197     return;
1198
1199   if (!may_propagate_copy (res, val))
1200     return;
1201
1202   eq_to[ver] = val;
1203
1204   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1205   n = num_immediate_uses (df);
1206
1207   for (i = 0; i < n; i++)
1208     {
1209       stmt = immediate_use (df, i);
1210
1211       if (TREE_CODE (stmt) == PHI_NODE)
1212         check_phi_redundancy (stmt, eq_to);
1213     }
1214 }
1215
1216 /* Removes redundant phi nodes.
1217
1218    A redundant PHI node is a PHI node where all of its PHI arguments
1219    are the same value, excluding any PHI arguments which are the same
1220    as the PHI result.
1221
1222    A redundant PHI node is effectively a copy, so we forward copy propagate
1223    which removes all uses of the destination of the PHI node then
1224    finally we delete the redundant PHI node.
1225
1226    Note that if we can not copy propagate the PHI node, then the PHI
1227    will not be removed.  Thus we do not have to worry about dependencies
1228    between PHIs and the problems serializing PHIs into copies creates.
1229
1230    The most important effect of this pass is to remove degenerate PHI
1231    nodes created by removing unreachable code.  */
1232
1233 void
1234 kill_redundant_phi_nodes (void)
1235 {
1236   tree *eq_to;
1237   unsigned i, old_num_ssa_names;
1238   basic_block bb;
1239   tree phi, var, repl, stmt;
1240
1241   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1242      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
1243      other value, it may be necessary to follow the chain till the final value.
1244      We perform path shortening (replacing the entries of the EQ_TO array with
1245      heads of these chains) whenever we access the field to prevent quadratic
1246      complexity (probably would not occur in practice anyway, but let us play
1247      it safe).  */
1248   eq_to = xcalloc (num_ssa_names, sizeof (tree));
1249
1250   /* We have had cases where computing immediate uses takes a
1251      significant amount of compile time.  If we run into such
1252      problems here, we may want to only compute immediate uses for
1253      a subset of all the SSA_NAMEs instead of computing it for
1254      all of the SSA_NAMEs.  */
1255   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1256   old_num_ssa_names = num_ssa_names;
1257
1258   FOR_EACH_BB (bb)
1259     {
1260       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1261         {
1262           var = PHI_RESULT (phi);
1263           check_phi_redundancy (phi, eq_to);
1264         }
1265     }
1266
1267   /* Now propagate the values.  */
1268   for (i = 0; i < old_num_ssa_names; i++)
1269     {
1270       if (!ssa_name (i))
1271         continue;
1272
1273       repl = get_eq_name (eq_to, ssa_name (i));
1274       if (repl != ssa_name (i))
1275         replace_immediate_uses (ssa_name (i), repl);
1276     }
1277
1278   /* And remove the dead phis.  */
1279   for (i = 0; i < old_num_ssa_names; i++)
1280     {
1281       if (!ssa_name (i))
1282         continue;
1283
1284       repl = get_eq_name (eq_to, ssa_name (i));
1285       if (repl != ssa_name (i))
1286         {
1287           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1288           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1289         }
1290     }
1291
1292   free_df ();
1293   free (eq_to);
1294 }
1295
1296 struct tree_opt_pass pass_redundant_phi =
1297 {
1298   "redphi",                             /* name */
1299   NULL,                                 /* gate */
1300   kill_redundant_phi_nodes,             /* execute */
1301   NULL,                                 /* sub */
1302   NULL,                                 /* next */
1303   0,                                    /* static_pass_number */
1304   TV_TREE_REDPHI,                       /* tv_id */
1305   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1306   0,                                    /* properties_provided */
1307   0,                                    /* properties_destroyed */
1308   0,                                    /* todo_flags_start */
1309   TODO_dump_func | TODO_rename_vars
1310     | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1311   0                                     /* letter */
1312 };
1313 \f
1314 /* Emit warnings for uninitialized variables.  This is done in two passes.
1315
1316    The first pass notices real uses of SSA names with default definitions.
1317    Such uses are unconditionally uninitialized, and we can be certain that
1318    such a use is a mistake.  This pass is run before most optimizations,
1319    so that we catch as many as we can.
1320
1321    The second pass follows PHI nodes to find uses that are potentially
1322    uninitialized.  In this case we can't necessarily prove that the use
1323    is really uninitialized.  This pass is run after most optimizations,
1324    so that we thread as many jumps and possible, and delete as much dead
1325    code as possible, in order to reduce false positives.  We also look
1326    again for plain uninitialized variables, since optimization may have
1327    changed conditionally uninitialized to unconditionally uninitialized.  */
1328
1329 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1330    warning text is in MSGID and LOCUS may contain a location or be null.  */
1331
1332 static void
1333 warn_uninit (tree t, const char *msgid, location_t *locus)
1334 {
1335   tree var = SSA_NAME_VAR (t);
1336   tree def = SSA_NAME_DEF_STMT (t);
1337
1338   /* Default uses (indicated by an empty definition statement),
1339      are uninitialized.  */
1340   if (!IS_EMPTY_STMT (def))
1341     return;
1342
1343   /* Except for PARMs of course, which are always initialized.  */
1344   if (TREE_CODE (var) == PARM_DECL)
1345     return;
1346
1347   /* Hard register variables get their initial value from the ether.  */
1348   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1349     return;
1350
1351   /* TREE_NO_WARNING either means we already warned, or the front end
1352      wishes to suppress the warning.  */
1353   if (TREE_NO_WARNING (var))
1354     return;
1355
1356   if (!locus)
1357     locus = &DECL_SOURCE_LOCATION (var);
1358   warning (msgid, locus, var);
1359   TREE_NO_WARNING (var) = 1;
1360 }
1361
1362 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1363    and warn about them.  */
1364
1365 static tree
1366 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1367 {
1368   location_t *locus = data;
1369   tree t = *tp;
1370
1371   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1372   if (TREE_CODE (t) == SSA_NAME)
1373     {
1374       warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1375       *walk_subtrees = 0;
1376     }
1377   else if (IS_TYPE_OR_DECL_P (t))
1378     *walk_subtrees = 0;
1379
1380   return NULL_TREE;
1381 }
1382
1383 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1384    and warn about them.  */
1385
1386 static void
1387 warn_uninitialized_phi (tree phi)
1388 {
1389   int i, n = PHI_NUM_ARGS (phi);
1390
1391   /* Don't look at memory tags.  */
1392   if (!is_gimple_reg (PHI_RESULT (phi)))
1393     return;
1394
1395   for (i = 0; i < n; ++i)
1396     {
1397       tree op = PHI_ARG_DEF (phi, i);
1398       if (TREE_CODE (op) == SSA_NAME)
1399         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1400                      NULL);
1401     }
1402 }
1403
1404 static void
1405 execute_early_warn_uninitialized (void)
1406 {
1407   block_stmt_iterator bsi;
1408   basic_block bb;
1409
1410   FOR_EACH_BB (bb)
1411     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1412       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1413                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1414 }
1415
1416 static void
1417 execute_late_warn_uninitialized (void)
1418 {
1419   basic_block bb;
1420   tree phi;
1421
1422   /* Re-do the plain uninitialized variable check, as optimization may have
1423      straightened control flow.  Do this first so that we don't accidentally
1424      get a "may be" warning when we'd have seen an "is" warning later.  */
1425   execute_early_warn_uninitialized ();
1426
1427   FOR_EACH_BB (bb)
1428     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1429       warn_uninitialized_phi (phi);
1430 }
1431
1432 static bool
1433 gate_warn_uninitialized (void)
1434 {
1435   return warn_uninitialized != 0;
1436 }
1437
1438 struct tree_opt_pass pass_early_warn_uninitialized =
1439 {
1440   NULL,                                 /* name */
1441   gate_warn_uninitialized,              /* gate */
1442   execute_early_warn_uninitialized,     /* execute */
1443   NULL,                                 /* sub */
1444   NULL,                                 /* next */
1445   0,                                    /* static_pass_number */
1446   0,                                    /* tv_id */
1447   PROP_ssa,                             /* properties_required */
1448   0,                                    /* properties_provided */
1449   0,                                    /* properties_destroyed */
1450   0,                                    /* todo_flags_start */
1451   0,                                    /* todo_flags_finish */
1452   0                                     /* letter */
1453 };
1454
1455 struct tree_opt_pass pass_late_warn_uninitialized =
1456 {
1457   NULL,                                 /* name */
1458   gate_warn_uninitialized,              /* gate */
1459   execute_late_warn_uninitialized,      /* execute */
1460   NULL,                                 /* sub */
1461   NULL,                                 /* next */
1462   0,                                    /* static_pass_number */
1463   0,                                    /* tv_id */
1464   PROP_ssa,                             /* properties_required */
1465   0,                                    /* properties_provided */
1466   0,                                    /* properties_destroyed */
1467   0,                                    /* todo_flags_start */
1468   0,                                    /* todo_flags_finish */
1469   0                                     /* letter */
1470 };
1471