gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004 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 = PHI_ARG_EDGE (phi, 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       var_ann_t ann;
 408       struct ptr_info_def *pi;
 409
 410       ptr = ssa_name (i);
 411       if (!ptr)
 412         continue;
 413       ann = var_ann (SSA_NAME_VAR (ptr));
 414       pi = SSA_NAME_PTR_INFO (ptr);
 415
 416       /* We only care for pointers that are actually referenced in the
 417          program.  */
 418       if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (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       if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
 426           && is_gimple_reg (ptr))
 427         continue;
 428
 429       if (pi == NULL)
 430         continue;
 431
 432       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
 433         {
 434           error ("Dereferenced pointers should have a name or a type tag");
 435           goto err;
 436         }
 437
 438       if (pi->name_mem_tag
 439           && !pi->pt_malloc
 440           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
 441         {
 442           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
 443           goto err;
 444         }
 445
 446       if (pi->value_escapes_p
 447           && pi->name_mem_tag
 448           && !is_call_clobbered (pi->name_mem_tag))
 449         {
 450           error ("Pointer escapes but its name tag is not call-clobbered.");
 451           goto err;
 452         }
 453     }
 454
 455   return;
 456
 457 err:
 458   debug_variable (ptr);
 459   internal_error ("verify_flow_sensitive_alias_info failed.");
 460 }
 461
 462 DEF_VEC_MALLOC_P (bitmap);
 463
 464 /* Verify that all name tags have different points to sets.
 465    This algorithm takes advantage of the fact that every variable with the
 466    same name tag must have the same points-to set.
 467    So we check a single variable for each name tag, and verify that its
 468    points-to set is different from every other points-to set for other name
 469    tags.  */
 470
 471 static void
 472 verify_name_tags (void)
 473 {
 474   size_t i;
 475   size_t j;
 476   bitmap first, second;
 477   VEC (tree) *name_tag_reps = NULL;
 478   VEC (bitmap) *pt_vars_for_reps = NULL;
 479
 480   /* First we compute the name tag representatives and their points-to sets.  */
 481   for (i = 0; i < num_ssa_names; i++)
 482     {
 483       if (ssa_name (i))
 484         {
 485           tree ptr = ssa_name (i);
 486           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 487           if (!TREE_VISITED (ptr)
 488               || !POINTER_TYPE_P (TREE_TYPE (ptr))
 489               || !pi
 490               || !pi->name_mem_tag
 491               || TREE_VISITED (pi->name_mem_tag))
 492             continue;
 493           TREE_VISITED (pi->name_mem_tag) = 1;
 494           if (pi->pt_vars != NULL)
 495             {
 496               VEC_safe_push (tree, name_tag_reps, ptr);
 497               VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
 498             }
 499         }
 500     }
 501
 502   /* Now compare all the representative bitmaps with all other representative
 503      bitmaps, to verify that they are all different.  */
 504   for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
 505     {
 506        for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
 507          {
 508            if (bitmap_equal_p (first, second))
 509              {
 510                error ("Two different pointers with identical points-to sets but different name tags");
 511                debug_variable (VEC_index (tree, name_tag_reps, j));
 512                goto err;
 513              }
 514          }
 515     }
 516
 517   /* Lastly, clear out the visited flags.  */
 518   for (i = 0; i < num_ssa_names; i++)
 519     {
 520       if (ssa_name (i))
 521         {
 522           tree ptr = ssa_name (i);
 523           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 524           if (!TREE_VISITED (ptr)
 525               || !POINTER_TYPE_P (TREE_TYPE (ptr))
 526               || !pi
 527               || !pi->name_mem_tag)
 528             continue;
 529           TREE_VISITED (pi->name_mem_tag) = 0;
 530         }
 531     }
 532   VEC_free (bitmap, pt_vars_for_reps);
 533   return;
 534
 535 err:
 536   debug_variable (VEC_index (tree, name_tag_reps, i));
 537   internal_error ("verify_name_tags failed");
 538 }
 539 /* Verify the consistency of aliasing information.  */
 540
 541 static void
 542 verify_alias_info (void)
 543 {
 544   verify_flow_sensitive_alias_info ();
 545   verify_name_tags ();
 546   verify_flow_insensitive_alias_info ();
 547 }
 548
 549
 550 /* Verify common invariants in the SSA web.
 551    TODO: verify the variable annotations.  */
 552
 553 void
 554 verify_ssa (void)
 555 {
 556   size_t i;
 557   basic_block bb;
 558   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
 559   ssa_op_iter iter;
 560   tree op;
 561   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
 562   bitmap names_defined_in_bb = BITMAP_XMALLOC ();
 563
 564   timevar_push (TV_TREE_SSA_VERIFY);
 565
 566   /* Keep track of SSA names present in the IL.  */
 567   for (i = 1; i < num_ssa_names; i++)
 568     {
 569       tree name = ssa_name (i);
 570       if (name)
 571         {
 572           tree stmt;
 573           TREE_VISITED (name) = 0;
 574
 575           stmt = SSA_NAME_DEF_STMT (name);
 576           if (!IS_EMPTY_STMT (stmt))
 577             {
 578               basic_block bb = bb_for_stmt (stmt);
 579               verify_def (bb, definition_block,
 580                           name, stmt, !is_gimple_reg (name));
 581
 582             }
 583         }
 584     }
 585
 586   calculate_dominance_info (CDI_DOMINATORS);
 587
 588   /* Now verify all the uses and make sure they agree with the definitions
 589      found in the previous pass.  */
 590   FOR_EACH_BB (bb)
 591     {
 592       edge e;
 593       tree phi;
 594       edge_iterator ei;
 595       block_stmt_iterator bsi;
 596
 597       /* Make sure that all edges have a clear 'aux' field.  */
 598       FOR_EACH_EDGE (e, ei, bb->preds)
 599         {
 600           if (e->aux)
 601             {
 602               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 603                       e->dest->index);
 604               goto err;
 605             }
 606         }
 607
 608       /* Verify the arguments for every PHI node in the block.  */
 609       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 610         {
 611           if (verify_phi_args (phi, bb, definition_block))
 612             goto err;
 613           bitmap_set_bit (names_defined_in_bb,
 614                           SSA_NAME_VERSION (PHI_RESULT (phi)));
 615         }
 616
 617       /* Now verify all the uses and vuses in every statement of the block.  */
 618       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 619         {
 620           tree stmt = bsi_stmt (bsi);
 621
 622               get_stmt_operands (stmt);
 623
 624               if (stmt_ann (stmt)->makes_aliased_stores
 625                   && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
 626                 {
 627                   error ("Statement makes aliased stores, but has no V_MAY_DEFS");
 628                   print_generic_stmt (stderr, stmt, TDF_VOPS);
 629                   goto err;
 630                 }
 631
 632           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 633             {
 634               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 635                               op, stmt, false, !is_gimple_reg (op),
 636                               names_defined_in_bb))
 637                 goto err;
 638             }
 639
 640           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 641             {
 642               bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 643             }
 644         }
 645
 646       bitmap_clear (names_defined_in_bb);
 647     }
 648
 649   /* Finally, verify alias information.  */
 650   verify_alias_info ();
 651
 652   free (definition_block);
 653   /* Restore the dominance information to its prior known state, so
 654      that we do not perturb the compiler's subsequent behavior.  */
 655   if (orig_dom_state == DOM_NONE)
 656     free_dominance_info (CDI_DOMINATORS);
 657   else
 658     dom_computed[CDI_DOMINATORS] = orig_dom_state;
 659
 660   BITMAP_XFREE (names_defined_in_bb);
 661   timevar_pop (TV_TREE_SSA_VERIFY);
 662   return;
 663
 664 err:
 665   internal_error ("verify_ssa failed.");
 666 }
 667
 668
 669 /* Initialize global DFA and SSA structures.  */
 670
 671 void
 672 init_tree_ssa (void)
 673 {
 674   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 675   call_clobbered_vars = BITMAP_XMALLOC ();
 676   addressable_vars = BITMAP_XMALLOC ();
 677   init_ssa_operands ();
 678   init_ssanames ();
 679   init_phinodes ();
 680   global_var = NULL_TREE;
 681 }
 682
 683
 684 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 685
 686 void
 687 delete_tree_ssa (void)
 688 {
 689   size_t i;
 690   basic_block bb;
 691   block_stmt_iterator bsi;
 692
 693   /* Remove annotations from every tree in the function.  */
 694   FOR_EACH_BB (bb)
 695     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 696       {
 697         tree stmt = bsi_stmt (bsi);
 698         release_defs (stmt);
 699         ggc_free (stmt->common.ann);
 700         stmt->common.ann = NULL;
 701       }
 702
 703   /* Remove annotations from every referenced variable.  */
 704   if (referenced_vars)
 705     {
 706       for (i = 0; i < num_referenced_vars; i++)
 707         {
 708           tree var = referenced_var (i);
 709           ggc_free (var->common.ann);
 710           var->common.ann = NULL;
 711         }
 712       referenced_vars = NULL;
 713     }
 714
 715   fini_ssanames ();
 716   fini_phinodes ();
 717   fini_ssa_operands ();
 718
 719   global_var = NULL_TREE;
 720   BITMAP_XFREE (call_clobbered_vars);
 721   call_clobbered_vars = NULL;
 722   BITMAP_XFREE (addressable_vars);
 723   addressable_vars = NULL;
 724 }
 725
 726
 727 /* Return true if EXPR is a useless type conversion, otherwise return
 728    false.  */
 729
 730 bool
 731 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 732 {
 733   /* If the inner and outer types are effectively the same, then
 734      strip the type conversion and enter the equivalence into
 735      the table.  */
 736   if (inner_type == outer_type
 737      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 738     return true;
 739
 740   /* If both types are pointers and the outer type is a (void *), then
 741      the conversion is not necessary.  The opposite is not true since
 742      that conversion would result in a loss of information if the
 743      equivalence was used.  Consider an indirect function call where
 744      we need to know the exact type of the function to correctly
 745      implement the ABI.  */
 746   else if (POINTER_TYPE_P (inner_type)
 747            && POINTER_TYPE_P (outer_type)
 748            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 749            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 750               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 751            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 752     return true;
 753
 754   /* Pointers and references are equivalent once we get to GENERIC,
 755      so strip conversions that just switch between them.  */
 756   else if (POINTER_TYPE_P (inner_type)
 757            && POINTER_TYPE_P (outer_type)
 758            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 759            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 760               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 761            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 762                                              TREE_TYPE (outer_type)))
 763     return true;
 764
 765   /* If both the inner and outer types are integral types, then the
 766      conversion is not necessary if they have the same mode and
 767      signedness and precision, and both or neither are boolean.  Some
 768      code assumes an invariant that boolean types stay boolean and do
 769      not become 1-bit bit-field types.  Note that types with precision
 770      not using all bits of the mode (such as bit-field types in C)
 771      mean that testing of precision is necessary.  */
 772   else if (INTEGRAL_TYPE_P (inner_type)
 773            && INTEGRAL_TYPE_P (outer_type)
 774            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 775            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 776            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 777     {
 778       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 779       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 780       if (first_boolean == second_boolean)
 781         return true;
 782     }
 783
 784   /* Recurse for complex types.  */
 785   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 786            && TREE_CODE (outer_type) == COMPLEX_TYPE
 787            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 788                                                   TREE_TYPE (inner_type)))
 789     return true;
 790
 791   return false;
 792 }
 793
 794 /* Return true if EXPR is a useless type conversion, otherwise return
 795    false.  */
 796
 797 bool
 798 tree_ssa_useless_type_conversion (tree expr)
 799 {
 800   /* If we have an assignment that merely uses a NOP_EXPR to change
 801      the top of the RHS to the type of the LHS and the type conversion
 802      is "safe", then strip away the type conversion so that we can
 803      enter LHS = RHS into the const_and_copies table.  */
 804   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 805       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 806       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 807     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 808                                                TREE_TYPE (TREE_OPERAND (expr,
 809                                                                         0)));
 810
 811
 812   return false;
 813 }
 814
 815 /* Returns true if statement STMT may read memory.  */
 816
 817 bool
 818 stmt_references_memory_p (tree stmt)
 819 {
 820   stmt_ann_t ann;
 821
 822   get_stmt_operands (stmt);
 823   ann = stmt_ann (stmt);
 824
 825   if (ann->has_volatile_ops)
 826     return true;
 827
 828   return (NUM_VUSES (VUSE_OPS (ann)) > 0
 829           || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
 830           || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
 831 }
 832
 833 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 834    described in walk_use_def_chains.
 835
 836    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
 837       infinite loops.  We used to have a bitmap for this to just mark
 838       SSA versions we had visited.  But non-sparse bitmaps are way too
 839       expensive, while sparse bitmaps may cause quadratic behavior.
 840
 841    IS_DFS is true if the caller wants to perform a depth-first search
 842       when visiting PHI nodes.  A DFS will visit each PHI argument and
 843       call FN after each one.  Otherwise, all the arguments are
 844       visited first and then FN is called with each of the visited
 845       arguments in a separate pass.  */
 846
 847 static bool
 848 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 849                        struct pointer_set_t *visited, bool is_dfs)
 850 {
 851   tree def_stmt;
 852
 853   if (pointer_set_insert (visited, var))
 854     return false;
 855
 856   def_stmt = SSA_NAME_DEF_STMT (var);
 857
 858   if (TREE_CODE (def_stmt) != PHI_NODE)
 859     {
 860       /* If we reached the end of the use-def chain, call FN.  */
 861       return fn (var, def_stmt, data);
 862     }
 863   else
 864     {
 865       int i;
 866
 867       /* When doing a breadth-first search, call FN before following the
 868          use-def links for each argument.  */
 869       if (!is_dfs)
 870         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 871           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 872             return true;
 873
 874       /* Follow use-def links out of each PHI argument.  */
 875       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 876         {
 877           tree arg = PHI_ARG_DEF (def_stmt, i);
 878           if (TREE_CODE (arg) == SSA_NAME
 879               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
 880             return true;
 881         }
 882
 883       /* When doing a depth-first search, call FN after following the
 884          use-def links for each argument.  */
 885       if (is_dfs)
 886         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 887           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 888             return true;
 889     }
 890
 891   return false;
 892 }
 893
 894
 895
 896 /* Walk use-def chains starting at the SSA variable VAR.  Call
 897    function FN at each reaching definition found.  FN takes three
 898    arguments: VAR, its defining statement (DEF_STMT) and a generic
 899    pointer to whatever state information that FN may want to maintain
 900    (DATA).  FN is able to stop the walk by returning true, otherwise
 901    in order to continue the walk, FN should return false.
 902
 903    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 904    different.  The first argument to FN is no longer the original
 905    variable VAR, but the PHI argument currently being examined.  If FN
 906    wants to get at VAR, it should call PHI_RESULT (PHI).
 907
 908    If IS_DFS is true, this function will:
 909
 910         1- walk the use-def chains for all the PHI arguments, and,
 911         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
 912
 913    If IS_DFS is false, the two steps above are done in reverse order
 914    (i.e., a breadth-first search).  */
 915
 916
 917 void
 918 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
 919                      bool is_dfs)
 920 {
 921   tree def_stmt;
 922
 923   gcc_assert (TREE_CODE (var) == SSA_NAME);
 924
 925   def_stmt = SSA_NAME_DEF_STMT (var);
 926
 927   /* We only need to recurse if the reaching definition comes from a PHI
 928      node.  */
 929   if (TREE_CODE (def_stmt) != PHI_NODE)
 930     (*fn) (var, def_stmt, data);
 931   else
 932     {
 933       struct pointer_set_t *visited = pointer_set_create ();
 934       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
 935       pointer_set_destroy (visited);
 936     }
 937 }
 938
 939
 940 /* Replaces VAR with REPL in memory reference expression *X in
 941    statement STMT.  */
 942
 943 static void
 944 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 945 {
 946   tree new_var, ass_stmt, addr_var;
 947   basic_block bb;
 948   block_stmt_iterator bsi;
 949
 950   /* There is nothing special to handle in the other cases.  */
 951   if (TREE_CODE (repl) != ADDR_EXPR)
 952     return;
 953   addr_var = TREE_OPERAND (repl, 0);
 954
 955   while (handled_component_p (*x)
 956          || TREE_CODE (*x) == REALPART_EXPR
 957          || TREE_CODE (*x) == IMAGPART_EXPR)
 958     x = &TREE_OPERAND (*x, 0);
 959
 960   if (TREE_CODE (*x) != INDIRECT_REF
 961       || TREE_OPERAND (*x, 0) != var)
 962     return;
 963
 964   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 965     {
 966       *x = addr_var;
 967       mark_new_vars_to_rename (stmt, vars_to_rename);
 968       return;
 969     }
 970
 971
 972   /* Frontends sometimes produce expressions like *&a instead of a[0].
 973      Create a temporary variable to handle this case.  */
 974   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 975   new_var = duplicate_ssa_name (var, ass_stmt);
 976   TREE_OPERAND (*x, 0) = new_var;
 977   TREE_OPERAND (ass_stmt, 0) = new_var;
 978
 979   bb = bb_for_stmt (stmt);
 980   tree_block_label (bb);
 981   bsi = bsi_after_labels (bb);
 982   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 983
 984   mark_new_vars_to_rename (stmt, vars_to_rename);
 985 }
 986
 987 /* Replaces immediate uses of VAR by REPL.  */
 988
 989 static void
 990 replace_immediate_uses (tree var, tree repl)
 991 {
 992   int i, j, n;
 993   dataflow_t df;
 994   tree stmt;
 995   bool mark_new_vars;
 996   ssa_op_iter iter;
 997   use_operand_p use_p;
 998
 999   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
1000   n = num_immediate_uses (df);
1001
1002   for (i = 0; i < n; i++)
1003     {
1004       stmt = immediate_use (df, i);
1005
1006       if (TREE_CODE (stmt) == PHI_NODE)
1007         {
1008           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
1009             if (PHI_ARG_DEF (stmt, j) == var)
1010               {
1011                 SET_PHI_ARG_DEF (stmt, j, repl);
1012                 if (TREE_CODE (repl) == SSA_NAME
1013                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
1014                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
1015               }
1016
1017           continue;
1018         }
1019
1020       get_stmt_operands (stmt);
1021       mark_new_vars = false;
1022       if (is_gimple_reg (SSA_NAME_VAR (var)))
1023         {
1024           if (TREE_CODE (stmt) == MODIFY_EXPR)
1025             {
1026               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
1027               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
1028             }
1029
1030           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1031             if (USE_FROM_PTR (use_p) == var)
1032               {
1033                 propagate_value (use_p, repl);
1034                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
1035               }
1036         }
1037       else
1038         {
1039           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1040                                     SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1041             if (USE_FROM_PTR (use_p) == var)
1042               propagate_value (use_p, repl);
1043         }
1044
1045       /* FIXME.  If REPL is a constant, we need to fold STMT.
1046          However, fold_stmt wants a pointer to the statement, because
1047          it may happen that it needs to replace the whole statement
1048          with a new expression.  Since the current def-use machinery
1049          does not return pointers to statements, we call fold_stmt
1050          with the address of a local temporary, if that call changes
1051          the temporary then we fallback on looking for a proper
1052          pointer to STMT by scanning STMT's basic block.
1053
1054          Note that all this will become unnecessary soon.  This
1055          pass is being replaced with a proper copy propagation pass
1056          for 4.1 (dnovillo, 2004-09-17).  */
1057       if (TREE_CODE (repl) != SSA_NAME)
1058         {
1059           tree tmp = stmt;
1060           fold_stmt (&tmp);
1061           mark_new_vars = true;
1062           if (tmp != stmt)
1063             {
1064               block_stmt_iterator si = bsi_for_stmt (stmt);
1065               bsi_replace (&si, tmp, true);
1066               stmt = bsi_stmt (si);
1067             }
1068         }
1069
1070       /* If REPL is a pointer, it may have different memory tags associated
1071          with it.  For instance, VAR may have had a name tag while REPL
1072          only had a type tag.  In these cases, the virtual operands (if
1073          any) in the statement will refer to different symbols which need
1074          to be renamed.  */
1075       if (mark_new_vars)
1076         mark_new_vars_to_rename (stmt, vars_to_rename);
1077       else
1078         modify_stmt (stmt);
1079     }
1080 }
1081
1082 /* Gets the value VAR is equivalent to according to EQ_TO.  */
1083
1084 static tree
1085 get_eq_name (tree *eq_to, tree var)
1086 {
1087   unsigned ver;
1088   tree val = var;
1089
1090   while (TREE_CODE (val) == SSA_NAME)
1091     {
1092       ver = SSA_NAME_VERSION (val);
1093       if (!eq_to[ver])
1094         break;
1095
1096       val = eq_to[ver];
1097     }
1098
1099   while (TREE_CODE (var) == SSA_NAME)
1100     {
1101       ver = SSA_NAME_VERSION (var);
1102       if (!eq_to[ver])
1103         break;
1104
1105       var = eq_to[ver];
1106       eq_to[ver] = val;
1107     }
1108
1109   return val;
1110 }
1111
1112 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1113    its result is redundant to to EQ_TO array.  */
1114
1115 static void
1116 check_phi_redundancy (tree phi, tree *eq_to)
1117 {
1118   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1119   unsigned i, ver = SSA_NAME_VERSION (res), n;
1120   dataflow_t df;
1121
1122   /* It is unlikely that such large phi node would be redundant.  */
1123   if (PHI_NUM_ARGS (phi) > 16)
1124     return;
1125
1126   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1127     {
1128       def = PHI_ARG_DEF (phi, i);
1129
1130       if (TREE_CODE (def) == SSA_NAME)
1131         {
1132           def = get_eq_name (eq_to, def);
1133           if (def == res)
1134             continue;
1135         }
1136
1137       if (val
1138           && !operand_equal_p (val, def, 0))
1139         return;
1140
1141       val = def;
1142     }
1143
1144   /* At least one of the arguments should not be equal to the result, or
1145      something strange is happening.  */
1146   gcc_assert (val);
1147
1148   if (get_eq_name (eq_to, res) == val)
1149     return;
1150
1151   if (!may_propagate_copy (res, val))
1152     return;
1153
1154   eq_to[ver] = val;
1155
1156   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1157   n = num_immediate_uses (df);
1158
1159   for (i = 0; i < n; i++)
1160     {
1161       stmt = immediate_use (df, i);
1162
1163       if (TREE_CODE (stmt) == PHI_NODE)
1164         check_phi_redundancy (stmt, eq_to);
1165     }
1166 }
1167
1168 /* Removes redundant phi nodes.
1169
1170    A redundant PHI node is a PHI node where all of its PHI arguments
1171    are the same value, excluding any PHI arguments which are the same
1172    as the PHI result.
1173
1174    A redundant PHI node is effectively a copy, so we forward copy propagate
1175    which removes all uses of the destination of the PHI node then
1176    finally we delete the redundant PHI node.
1177
1178    Note that if we can not copy propagate the PHI node, then the PHI
1179    will not be removed.  Thus we do not have to worry about dependencies
1180    between PHIs and the problems serializing PHIs into copies creates.
1181
1182    The most important effect of this pass is to remove degenerate PHI
1183    nodes created by removing unreachable code.  */
1184
1185 void
1186 kill_redundant_phi_nodes (void)
1187 {
1188   tree *eq_to;
1189   unsigned i, old_num_ssa_names;
1190   basic_block bb;
1191   tree phi, var, repl, stmt;
1192
1193   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1194      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
1195      other value, it may be necessary to follow the chain till the final value.
1196      We perform path shortening (replacing the entries of the EQ_TO array with
1197      heads of these chains) whenever we access the field to prevent quadratic
1198      complexity (probably would not occur in practice anyway, but let us play
1199      it safe).  */
1200   eq_to = xcalloc (num_ssa_names, sizeof (tree));
1201
1202   /* We have had cases where computing immediate uses takes a
1203      significant amount of compile time.  If we run into such
1204      problems here, we may want to only compute immediate uses for
1205      a subset of all the SSA_NAMEs instead of computing it for
1206      all of the SSA_NAMEs.  */
1207   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1208   old_num_ssa_names = num_ssa_names;
1209
1210   FOR_EACH_BB (bb)
1211     {
1212       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1213         {
1214           var = PHI_RESULT (phi);
1215           check_phi_redundancy (phi, eq_to);
1216         }
1217     }
1218
1219   /* Now propagate the values.  */
1220   for (i = 0; i < old_num_ssa_names; i++)
1221     {
1222       if (!ssa_name (i))
1223         continue;
1224
1225       repl = get_eq_name (eq_to, ssa_name (i));
1226       if (repl != ssa_name (i))
1227         replace_immediate_uses (ssa_name (i), repl);
1228     }
1229
1230   /* And remove the dead phis.  */
1231   for (i = 0; i < old_num_ssa_names; i++)
1232     {
1233       if (!ssa_name (i))
1234         continue;
1235
1236       repl = get_eq_name (eq_to, ssa_name (i));
1237       if (repl != ssa_name (i))
1238         {
1239           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1240           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1241         }
1242     }
1243
1244   free_df ();
1245   free (eq_to);
1246 }
1247
1248 struct tree_opt_pass pass_redundant_phi =
1249 {
1250   "redphi",                             /* name */
1251   NULL,                                 /* gate */
1252   kill_redundant_phi_nodes,             /* execute */
1253   NULL,                                 /* sub */
1254   NULL,                                 /* next */
1255   0,                                    /* static_pass_number */
1256   0,                                    /* tv_id */
1257   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1258   0,                                    /* properties_provided */
1259   0,                                    /* properties_destroyed */
1260   0,                                    /* todo_flags_start */
1261   TODO_dump_func | TODO_rename_vars
1262     | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1263   0                                     /* letter */
1264 };
1265 \f
1266 /* Emit warnings for uninitialized variables.  This is done in two passes.
1267
1268    The first pass notices real uses of SSA names with default definitions.
1269    Such uses are unconditionally uninitialized, and we can be certain that
1270    such a use is a mistake.  This pass is run before most optimizations,
1271    so that we catch as many as we can.
1272
1273    The second pass follows PHI nodes to find uses that are potentially
1274    uninitialized.  In this case we can't necessarily prove that the use
1275    is really uninitialized.  This pass is run after most optimizations,
1276    so that we thread as many jumps and possible, and delete as much dead
1277    code as possible, in order to reduce false positives.  We also look
1278    again for plain uninitialized variables, since optimization may have
1279    changed conditionally uninitialized to unconditionally uninitialized.  */
1280
1281 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1282    warning text is in MSGID and LOCUS may contain a location or be null.  */
1283
1284 static void
1285 warn_uninit (tree t, const char *msgid, location_t *locus)
1286 {
1287   tree var = SSA_NAME_VAR (t);
1288   tree def = SSA_NAME_DEF_STMT (t);
1289
1290   /* Default uses (indicated by an empty definition statement),
1291      are uninitialized.  */
1292   if (!IS_EMPTY_STMT (def))
1293     return;
1294
1295   /* Except for PARMs of course, which are always initialized.  */
1296   if (TREE_CODE (var) == PARM_DECL)
1297     return;
1298
1299   /* Hard register variables get their initial value from the ether.  */
1300   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1301     return;
1302
1303   /* TREE_NO_WARNING either means we already warned, or the front end
1304      wishes to suppress the warning.  */
1305   if (TREE_NO_WARNING (var))
1306     return;
1307
1308   if (!locus)
1309     locus = &DECL_SOURCE_LOCATION (var);
1310   warning (msgid, locus, var);
1311   TREE_NO_WARNING (var) = 1;
1312 }
1313
1314 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1315    and warn about them.  */
1316
1317 static tree
1318 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1319 {
1320   location_t *locus = data;
1321   tree t = *tp;
1322
1323   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1324   if (TREE_CODE (t) == SSA_NAME)
1325     {
1326       warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
1327       *walk_subtrees = 0;
1328     }
1329   else if (IS_TYPE_OR_DECL_P (t))
1330     *walk_subtrees = 0;
1331
1332   return NULL_TREE;
1333 }
1334
1335 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1336    and warn about them.  */
1337
1338 static void
1339 warn_uninitialized_phi (tree phi)
1340 {
1341   int i, n = PHI_NUM_ARGS (phi);
1342
1343   /* Don't look at memory tags.  */
1344   if (!is_gimple_reg (PHI_RESULT (phi)))
1345     return;
1346
1347   for (i = 0; i < n; ++i)
1348     {
1349       tree op = PHI_ARG_DEF (phi, i);
1350       if (TREE_CODE (op) == SSA_NAME)
1351         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1352                      NULL);
1353     }
1354 }
1355
1356 static void
1357 execute_early_warn_uninitialized (void)
1358 {
1359   block_stmt_iterator bsi;
1360   basic_block bb;
1361
1362   FOR_EACH_BB (bb)
1363     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1364       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1365                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1366 }
1367
1368 static void
1369 execute_late_warn_uninitialized (void)
1370 {
1371   basic_block bb;
1372   tree phi;
1373
1374   /* Re-do the plain uninitialized variable check, as optimization may have
1375      straightened control flow.  Do this first so that we don't accidentally
1376      get a "may be" warning when we'd have seen an "is" warning later.  */
1377   execute_early_warn_uninitialized ();
1378
1379   FOR_EACH_BB (bb)
1380     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1381       warn_uninitialized_phi (phi);
1382 }
1383
1384 static bool
1385 gate_warn_uninitialized (void)
1386 {
1387   return warn_uninitialized != 0;
1388 }
1389
1390 struct tree_opt_pass pass_early_warn_uninitialized =
1391 {
1392   NULL,                                 /* name */
1393   gate_warn_uninitialized,              /* gate */
1394   execute_early_warn_uninitialized,     /* execute */
1395   NULL,                                 /* sub */
1396   NULL,                                 /* next */
1397   0,                                    /* static_pass_number */
1398   0,                                    /* tv_id */
1399   PROP_ssa,                             /* properties_required */
1400   0,                                    /* properties_provided */
1401   0,                                    /* properties_destroyed */
1402   0,                                    /* todo_flags_start */
1403   0,                                    /* todo_flags_finish */
1404   0                                     /* letter */
1405 };
1406
1407 struct tree_opt_pass pass_late_warn_uninitialized =
1408 {
1409   NULL,                                 /* name */
1410   gate_warn_uninitialized,              /* gate */
1411   execute_late_warn_uninitialized,      /* execute */
1412   NULL,                                 /* sub */
1413   NULL,                                 /* next */
1414   0,                                    /* static_pass_number */
1415   0,                                    /* tv_id */
1416   PROP_ssa,                             /* properties_required */
1417   0,                                    /* properties_provided */
1418   0,                                    /* properties_destroyed */
1419   0,                                    /* todo_flags_start */
1420   0,                                    /* todo_flags_finish */
1421   0                                     /* letter */
1422 };
1423