gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
   3    Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "langhooks.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "expr.h"
  35 #include "function.h"
  36 #include "diagnostic.h"
  37 #include "bitmap.h"
  38 #include "pointer-set.h"
  39 #include "tree-flow.h"
  40 #include "tree-gimple.h"
  41 #include "tree-inline.h"
  42 #include "varray.h"
  43 #include "timevar.h"
  44 #include "hashtab.h"
  45 #include "tree-dump.h"
  46 #include "tree-pass.h"
  47 #include "toplev.h"
  48
  49 /* Pointer map of variable mappings, keyed by edge.  */
  50 static struct pointer_map_t *edge_var_maps;
  51
  52
  53 /* Add a mapping with PHI RESULT and PHI DEF associated with edge E.  */
  54
  55 void
  56 redirect_edge_var_map_add (edge e, tree result, tree def)
  57 {
  58   void **slot;
  59   edge_var_map_vector old_head, head;
  60   edge_var_map new_node;
  61
  62   if (edge_var_maps == NULL)
  63     edge_var_maps = pointer_map_create ();
  64
  65   slot = pointer_map_insert (edge_var_maps, e);
  66   old_head = head = (edge_var_map_vector) *slot;
  67   if (!head)
  68     {
  69       head = VEC_alloc (edge_var_map, heap, 5);
  70       *slot = head;
  71     }
  72   new_node.def = def;
  73   new_node.result = result;
  74
  75   VEC_safe_push (edge_var_map, heap, head, &new_node);
  76   if (old_head != head)
  77     {
  78       /* The push did some reallocation.  Update the pointer map.  */
  79       *slot = head;
  80     }
  81 }
  82
  83
  84 /* Clear the var mappings in edge E.  */
  85
  86 void
  87 redirect_edge_var_map_clear (edge e)
  88 {
  89   void **slot;
  90   edge_var_map_vector head;
  91
  92   if (!edge_var_maps)
  93     return;
  94
  95   slot = pointer_map_contains (edge_var_maps, e);
  96
  97   if (slot)
  98     {
  99       head = (edge_var_map_vector) *slot;
 100       VEC_free (edge_var_map, heap, head);
 101       *slot = NULL;
 102     }
 103 }
 104
 105
 106 /* Duplicate the redirected var mappings in OLDE in NEWE.
 107
 108    Since we can't remove a mapping, let's just duplicate it.  This assumes a
 109    pointer_map can have multiple edges mapping to the same var_map (many to
 110    one mapping), since we don't remove the previous mappings.  */
 111
 112 void
 113 redirect_edge_var_map_dup (edge newe, edge olde)
 114 {
 115   void **new_slot, **old_slot; edge_var_map_vector head;
 116
 117   if (!edge_var_maps)
 118     return;
 119
 120   new_slot = pointer_map_insert (edge_var_maps, newe);
 121   old_slot = pointer_map_contains (edge_var_maps, olde);
 122   if (!old_slot)
 123     return;
 124   head = (edge_var_map_vector) *old_slot;
 125
 126   if (head)
 127     *new_slot = VEC_copy (edge_var_map, heap, head);
 128   else
 129     *new_slot = VEC_alloc (edge_var_map, heap, 5);
 130 }
 131
 132
 133 /* Return the variable mappings for a given edge.  If there is none, return
 134    NULL.  */
 135
 136 edge_var_map_vector
 137 redirect_edge_var_map_vector (edge e)
 138 {
 139   void **slot;
 140
 141   /* Hey, what kind of idiot would... you'd be surprised.  */
 142   if (!edge_var_maps)
 143     return NULL;
 144
 145   slot = pointer_map_contains (edge_var_maps, e);
 146   if (!slot)
 147     return NULL;
 148
 149   return (edge_var_map_vector) *slot;
 150 }
 151
 152
 153 /* Clear the edge variable mappings.  */
 154
 155 void
 156 redirect_edge_var_map_destroy (void)
 157 {
 158   if (edge_var_maps)
 159     {
 160       pointer_map_destroy (edge_var_maps);
 161       edge_var_maps = NULL;
 162     }
 163 }
 164
 165
 166 /* Remove the corresponding arguments from the PHI nodes in E's
 167    destination block and redirect it to DEST.  Return redirected edge.
 168    The list of removed arguments is stored in a vector accessed
 169    through edge_var_maps.  */
 170
 171 edge
 172 ssa_redirect_edge (edge e, basic_block dest)
 173 {
 174   tree phi;
 175
 176   redirect_edge_var_map_clear (e);
 177
 178   /* Remove the appropriate PHI arguments in E's destination block.  */
 179   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 180     {
 181       tree def = PHI_ARG_DEF (phi, e->dest_idx);
 182
 183       if (def == NULL_TREE)
 184         continue;
 185
 186       redirect_edge_var_map_add (e, PHI_RESULT (phi), def);
 187     }
 188
 189   e = redirect_edge_succ_nodup (e, dest);
 190
 191   return e;
 192 }
 193
 194 /* Add PHI arguments queued in PENDING_STMT list on edge E to edge
 195    E->dest.  */
 196
 197 void
 198 flush_pending_stmts (edge e)
 199 {
 200   tree phi;
 201   edge_var_map_vector v;
 202   edge_var_map *vm;
 203   int i;
 204
 205   v = redirect_edge_var_map_vector (e);
 206   if (!v)
 207     return;
 208
 209   for (phi = phi_nodes (e->dest), i = 0;
 210        phi && VEC_iterate (edge_var_map, v, i, vm);
 211        phi = PHI_CHAIN (phi), i++)
 212     {
 213       tree def = redirect_edge_var_map_def (vm);
 214       add_phi_arg (phi, def, e);
 215     }
 216
 217   redirect_edge_var_map_clear (e);
 218 }
 219
 220 /* Return true if SSA_NAME is malformed and mark it visited.
 221
 222    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
 223       operand.  */
 224
 225 static bool
 226 verify_ssa_name (tree ssa_name, bool is_virtual)
 227 {
 228   if (TREE_CODE (ssa_name) != SSA_NAME)
 229     {
 230       error ("expected an SSA_NAME object");
 231       return true;
 232     }
 233
 234   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
 235     {
 236       error ("type mismatch between an SSA_NAME and its symbol");
 237       return true;
 238     }
 239
 240   if (SSA_NAME_IN_FREE_LIST (ssa_name))
 241     {
 242       error ("found an SSA_NAME that had been released into the free pool");
 243       return true;
 244     }
 245
 246   if (is_virtual && is_gimple_reg (ssa_name))
 247     {
 248       error ("found a virtual definition for a GIMPLE register");
 249       return true;
 250     }
 251
 252   if (!is_virtual && !is_gimple_reg (ssa_name))
 253     {
 254       error ("found a real definition for a non-register");
 255       return true;
 256     }
 257
 258   if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
 259       && !IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
 260     {
 261       error ("found a default name with a non-empty defining statement");
 262       return true;
 263     }
 264
 265   return false;
 266 }
 267
 268
 269 /* Return true if the definition of SSA_NAME at block BB is malformed.
 270
 271    STMT is the statement where SSA_NAME is created.
 272
 273    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
 274       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
 275       it means that the block in that array slot contains the
 276       definition of SSA_NAME.
 277
 278    IS_VIRTUAL is true if SSA_NAME is created by a VDEF.  */
 279
 280 static bool
 281 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 282             tree stmt, bool is_virtual)
 283 {
 284   if (verify_ssa_name (ssa_name, is_virtual))
 285     goto err;
 286
 287   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 288     {
 289       error ("SSA_NAME created in two different blocks %i and %i",
 290              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 291       goto err;
 292     }
 293
 294   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 295
 296   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 297     {
 298       error ("SSA_NAME_DEF_STMT is wrong");
 299       fprintf (stderr, "Expected definition statement:\n");
 300       print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
 301       fprintf (stderr, "\nActual definition statement:\n");
 302       print_generic_stmt (stderr, stmt, TDF_VOPS);
 303       goto err;
 304     }
 305
 306   return false;
 307
 308 err:
 309   fprintf (stderr, "while verifying SSA_NAME ");
 310   print_generic_expr (stderr, ssa_name, 0);
 311   fprintf (stderr, " in statement\n");
 312   print_generic_stmt (stderr, stmt, TDF_VOPS);
 313
 314   return true;
 315 }
 316
 317
 318 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 319    malformed.
 320
 321    DEF_BB is the block where SSA_NAME was found to be created.
 322
 323    IDOM contains immediate dominator information for the flowgraph.
 324
 325    CHECK_ABNORMAL is true if the caller wants to check whether this use
 326       is flowing through an abnormal edge (only used when checking PHI
 327       arguments).
 328
 329    If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
 330      that are defined before STMT in basic block BB.  */
 331
 332 static bool
 333 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
 334             tree stmt, bool check_abnormal, bitmap names_defined_in_bb)
 335 {
 336   bool err = false;
 337   tree ssa_name = USE_FROM_PTR (use_p);
 338
 339   if (!TREE_VISITED (ssa_name))
 340     if (verify_imm_links (stderr, ssa_name))
 341       err = true;
 342
 343   TREE_VISITED (ssa_name) = 1;
 344
 345   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
 346       && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
 347     ; /* Default definitions have empty statements.  Nothing to do.  */
 348   else if (!def_bb)
 349     {
 350       error ("missing definition");
 351       err = true;
 352     }
 353   else if (bb != def_bb
 354            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 355     {
 356       error ("definition in block %i does not dominate use in block %i",
 357              def_bb->index, bb->index);
 358       err = true;
 359     }
 360   else if (bb == def_bb
 361            && names_defined_in_bb != NULL
 362            && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
 363     {
 364       error ("definition in block %i follows the use", def_bb->index);
 365       err = true;
 366     }
 367
 368   if (check_abnormal
 369       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 370     {
 371       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 372       err = true;
 373     }
 374
 375   /* Make sure the use is in an appropriate list by checking the previous
 376      element to make sure it's the same.  */
 377   if (use_p->prev == NULL)
 378     {
 379       error ("no immediate_use list");
 380       err = true;
 381     }
 382   else
 383     {
 384       tree listvar ;
 385       if (use_p->prev->use == NULL)
 386         listvar = use_p->prev->stmt;
 387       else
 388         listvar = USE_FROM_PTR (use_p->prev);
 389       if (listvar != ssa_name)
 390         {
 391           error ("wrong immediate use list");
 392           err = true;
 393         }
 394     }
 395
 396   if (err)
 397     {
 398       fprintf (stderr, "for SSA_NAME: ");
 399       print_generic_expr (stderr, ssa_name, TDF_VOPS);
 400       fprintf (stderr, " in statement:\n");
 401       print_generic_stmt (stderr, stmt, TDF_VOPS);
 402     }
 403
 404   return err;
 405 }
 406
 407
 408 /* Return true if any of the arguments for PHI node PHI at block BB is
 409    malformed.
 410
 411    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
 412       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
 413       it means that the block in that array slot contains the
 414       definition of SSA_NAME.  */
 415
 416 static bool
 417 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 418 {
 419   edge e;
 420   bool err = false;
 421   unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
 422
 423   if (EDGE_COUNT (bb->preds) != phi_num_args)
 424     {
 425       error ("incoming edge count does not match number of PHI arguments");
 426       err = true;
 427       goto error;
 428     }
 429
 430   for (i = 0; i < phi_num_args; i++)
 431     {
 432       use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
 433       tree op = USE_FROM_PTR (op_p);
 434
 435       e = EDGE_PRED (bb, i);
 436
 437       if (op == NULL_TREE)
 438         {
 439           error ("PHI argument is missing for edge %d->%d",
 440                  e->src->index,
 441                  e->dest->index);
 442           err = true;
 443           goto error;
 444         }
 445
 446       if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
 447         {
 448           error ("PHI argument is not SSA_NAME, or invariant");
 449           err = true;
 450         }
 451
 452       if (TREE_CODE (op) == SSA_NAME)
 453         {
 454           err = verify_ssa_name (op, !is_gimple_reg (PHI_RESULT (phi)));
 455           err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
 456                              op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
 457         }
 458
 459       if (e->dest != bb)
 460         {
 461           error ("wrong edge %d->%d for PHI argument",
 462                  e->src->index, e->dest->index);
 463           err = true;
 464         }
 465
 466       if (err)
 467         {
 468           fprintf (stderr, "PHI argument\n");
 469           print_generic_stmt (stderr, op, TDF_VOPS);
 470           goto error;
 471         }
 472     }
 473
 474 error:
 475   if (err)
 476     {
 477       fprintf (stderr, "for PHI node\n");
 478       print_generic_stmt (stderr, phi, TDF_VOPS|TDF_MEMSYMS);
 479     }
 480
 481
 482   return err;
 483 }
 484
 485
 486 static void
 487 verify_flow_insensitive_alias_info (void)
 488 {
 489   tree var;
 490   referenced_var_iterator rvi;
 491
 492   FOR_EACH_REFERENCED_VAR (var, rvi)
 493     {
 494       unsigned int j;
 495       bitmap aliases;
 496       tree alias;
 497       bitmap_iterator bi;
 498
 499       if (!MTAG_P (var) || !MTAG_ALIASES (var))
 500         continue;
 501
 502       aliases = MTAG_ALIASES (var);
 503
 504       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, j, bi)
 505         {
 506           alias = referenced_var (j);
 507
 508           if (TREE_CODE (alias) != MEMORY_PARTITION_TAG
 509               && !may_be_aliased (alias))
 510             {
 511               error ("non-addressable variable inside an alias set");
 512               debug_variable (alias);
 513               goto err;
 514             }
 515         }
 516     }
 517
 518   return;
 519
 520 err:
 521   debug_variable (var);
 522   internal_error ("verify_flow_insensitive_alias_info failed");
 523 }
 524
 525
 526 static void
 527 verify_flow_sensitive_alias_info (void)
 528 {
 529   size_t i;
 530   tree ptr;
 531
 532   for (i = 1; i < num_ssa_names; i++)
 533     {
 534       tree var;
 535       var_ann_t ann;
 536       struct ptr_info_def *pi;
 537
 538
 539       ptr = ssa_name (i);
 540       if (!ptr)
 541         continue;
 542
 543       /* We only care for pointers that are actually referenced in the
 544          program.  */
 545       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
 546         continue;
 547
 548       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
 549          is only written-to only once in the return statement.
 550          Otherwise, aggregate RESULT_DECLs may be written-to more than
 551          once in virtual operands.  */
 552       var = SSA_NAME_VAR (ptr);
 553       if (TREE_CODE (var) == RESULT_DECL
 554           && is_gimple_reg (ptr))
 555         continue;
 556
 557       pi = SSA_NAME_PTR_INFO (ptr);
 558       if (pi == NULL)
 559         continue;
 560
 561       ann = var_ann (var);
 562       if (pi->memory_tag_needed && !pi->name_mem_tag && !ann->symbol_mem_tag)
 563         {
 564           error ("dereferenced pointers should have a name or a symbol tag");
 565           goto err;
 566         }
 567
 568       if (pi->name_mem_tag
 569           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
 570         {
 571           error ("pointers with a memory tag, should have points-to sets");
 572           goto err;
 573         }
 574
 575       if (pi->value_escapes_p
 576           && pi->escape_mask & ~ESCAPE_TO_RETURN
 577           && pi->name_mem_tag)
 578         {
 579           tree t = memory_partition (pi->name_mem_tag);
 580           if (t == NULL_TREE)
 581             t = pi->name_mem_tag;
 582
 583           if (!is_call_clobbered (t))
 584             {
 585               error ("pointer escapes but its name tag is not call-clobbered");
 586               goto err;
 587             }
 588         }
 589     }
 590
 591   return;
 592
 593 err:
 594   debug_variable (ptr);
 595   internal_error ("verify_flow_sensitive_alias_info failed");
 596 }
 597
 598
 599 /* Verify the consistency of call clobbering information.  */
 600
 601 static void
 602 verify_call_clobbering (void)
 603 {
 604   unsigned int i;
 605   bitmap_iterator bi;
 606   tree var;
 607   referenced_var_iterator rvi;
 608
 609   /* At all times, the result of the call_clobbered flag should
 610      match the result of the call_clobbered_vars bitmap.  Verify both
 611      that everything in call_clobbered_vars is marked
 612      call_clobbered, and that everything marked
 613      call_clobbered is in call_clobbered_vars.  */
 614   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
 615     {
 616       var = referenced_var (i);
 617
 618       if (memory_partition (var))
 619         var = memory_partition (var);
 620
 621       if (!MTAG_P (var) && !var_ann (var)->call_clobbered)
 622         {
 623           error ("variable in call_clobbered_vars but not marked "
 624                  "call_clobbered");
 625           debug_variable (var);
 626           goto err;
 627         }
 628     }
 629
 630   FOR_EACH_REFERENCED_VAR (var, rvi)
 631     {
 632       if (is_gimple_reg (var))
 633         continue;
 634
 635       if (memory_partition (var))
 636         var = memory_partition (var);
 637
 638       if (!MTAG_P (var)
 639           && var_ann (var)->call_clobbered
 640           && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
 641         {
 642           error ("variable marked call_clobbered but not in "
 643                  "call_clobbered_vars bitmap.");
 644           debug_variable (var);
 645           goto err;
 646         }
 647     }
 648
 649   return;
 650
 651  err:
 652     internal_error ("verify_call_clobbering failed");
 653 }
 654
 655
 656 /* Verify invariants in memory partitions.  */
 657
 658 static void
 659 verify_memory_partitions (void)
 660 {
 661   unsigned i;
 662   tree mpt;
 663   VEC(tree,heap) *mpt_table = gimple_ssa_operands (cfun)->mpt_table;
 664   struct pointer_set_t *partitioned_syms = pointer_set_create ();
 665
 666   for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
 667     {
 668       unsigned j;
 669       bitmap_iterator bj;
 670
 671       if (MPT_SYMBOLS (mpt) == NULL)
 672         {
 673           error ("Memory partitions should have at least one symbol");
 674           debug_variable (mpt);
 675           goto err;
 676         }
 677
 678       EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt), 0, j, bj)
 679         {
 680           tree var = referenced_var (j);
 681           if (pointer_set_insert (partitioned_syms, var))
 682             {
 683               error ("Partitioned symbols should belong to exactly one "
 684                      "partition");
 685               debug_variable (var);
 686               goto err;
 687             }
 688         }
 689     }
 690
 691   pointer_set_destroy (partitioned_syms);
 692
 693   return;
 694
 695 err:
 696   internal_error ("verify_memory_partitions failed");
 697 }
 698
 699
 700 /* Verify the consistency of aliasing information.  */
 701
 702 static void
 703 verify_alias_info (void)
 704 {
 705   verify_flow_sensitive_alias_info ();
 706   verify_call_clobbering ();
 707   verify_flow_insensitive_alias_info ();
 708   verify_memory_partitions ();
 709 }
 710
 711
 712 /* Verify common invariants in the SSA web.
 713    TODO: verify the variable annotations.  */
 714
 715 void
 716 verify_ssa (bool check_modified_stmt)
 717 {
 718   size_t i;
 719   basic_block bb;
 720   basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
 721   ssa_op_iter iter;
 722   tree op;
 723   enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
 724   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
 725
 726   gcc_assert (!need_ssa_update_p ());
 727
 728   verify_stmts ();
 729
 730   timevar_push (TV_TREE_SSA_VERIFY);
 731
 732   /* Keep track of SSA names present in the IL.  */
 733   for (i = 1; i < num_ssa_names; i++)
 734     {
 735       tree name = ssa_name (i);
 736       if (name)
 737         {
 738           tree stmt;
 739           TREE_VISITED (name) = 0;
 740
 741           stmt = SSA_NAME_DEF_STMT (name);
 742           if (!IS_EMPTY_STMT (stmt))
 743             {
 744               basic_block bb = bb_for_stmt (stmt);
 745               verify_def (bb, definition_block,
 746                           name, stmt, !is_gimple_reg (name));
 747
 748             }
 749         }
 750     }
 751
 752   calculate_dominance_info (CDI_DOMINATORS);
 753
 754   /* Now verify all the uses and make sure they agree with the definitions
 755      found in the previous pass.  */
 756   FOR_EACH_BB (bb)
 757     {
 758       edge e;
 759       tree phi;
 760       edge_iterator ei;
 761       block_stmt_iterator bsi;
 762
 763       /* Make sure that all edges have a clear 'aux' field.  */
 764       FOR_EACH_EDGE (e, ei, bb->preds)
 765         {
 766           if (e->aux)
 767             {
 768               error ("AUX pointer initialized for edge %d->%d", e->src->index,
 769                       e->dest->index);
 770               goto err;
 771             }
 772         }
 773
 774       /* Verify the arguments for every PHI node in the block.  */
 775       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 776         {
 777           if (verify_phi_args (phi, bb, definition_block))
 778             goto err;
 779
 780           bitmap_set_bit (names_defined_in_bb,
 781                           SSA_NAME_VERSION (PHI_RESULT (phi)));
 782         }
 783
 784       /* Now verify all the uses and vuses in every statement of the block.  */
 785       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 786         {
 787           tree stmt = bsi_stmt (bsi);
 788           use_operand_p use_p;
 789
 790           if (check_modified_stmt && stmt_modified_p (stmt))
 791             {
 792               error ("stmt (%p) marked modified after optimization pass: ",
 793                      (void *)stmt);
 794               print_generic_stmt (stderr, stmt, TDF_VOPS);
 795               goto err;
 796             }
 797
 798           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 799               && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
 800             {
 801               tree lhs, base_address;
 802
 803               lhs = GIMPLE_STMT_OPERAND (stmt, 0);
 804               base_address = get_base_address (lhs);
 805
 806               if (base_address
 807                   && gimple_aliases_computed_p (cfun)
 808                   && SSA_VAR_P (base_address)
 809                   && !stmt_ann (stmt)->has_volatile_ops
 810                   && ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 811                 {
 812                   error ("statement makes a memory store, but has no VDEFS");
 813                   print_generic_stmt (stderr, stmt, TDF_VOPS);
 814                   goto err;
 815                 }
 816             }
 817
 818           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_VIRTUALS)
 819             {
 820               if (verify_ssa_name (op, true))
 821                 {
 822                   error ("in statement");
 823                   print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
 824                   goto err;
 825                 }
 826             }
 827
 828           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
 829             {
 830               if (verify_ssa_name (op, false))
 831                 {
 832                   error ("in statement");
 833                   print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
 834                   goto err;
 835                 }
 836             }
 837
 838           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
 839             {
 840               op = USE_FROM_PTR (use_p);
 841               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 842                               use_p, stmt, false, names_defined_in_bb))
 843                 goto err;
 844             }
 845
 846           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 847             bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 848         }
 849
 850       bitmap_clear (names_defined_in_bb);
 851     }
 852
 853   /* Finally, verify alias information.  */
 854   if (gimple_aliases_computed_p (cfun))
 855     verify_alias_info ();
 856
 857   free (definition_block);
 858
 859   /* Restore the dominance information to its prior known state, so
 860      that we do not perturb the compiler's subsequent behavior.  */
 861   if (orig_dom_state == DOM_NONE)
 862     free_dominance_info (CDI_DOMINATORS);
 863   else
 864     set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
 865
 866   BITMAP_FREE (names_defined_in_bb);
 867   timevar_pop (TV_TREE_SSA_VERIFY);
 868   return;
 869
 870 err:
 871   internal_error ("verify_ssa failed");
 872 }
 873
 874 /* Return true if the uid in both int tree maps are equal.  */
 875
 876 int
 877 int_tree_map_eq (const void *va, const void *vb)
 878 {
 879   const struct int_tree_map *a = (const struct int_tree_map *) va;
 880   const struct int_tree_map *b = (const struct int_tree_map *) vb;
 881   return (a->uid == b->uid);
 882 }
 883
 884 /* Hash a UID in a int_tree_map.  */
 885
 886 unsigned int
 887 int_tree_map_hash (const void *item)
 888 {
 889   return ((const struct int_tree_map *)item)->uid;
 890 }
 891
 892 /* Return true if the DECL_UID in both trees are equal.  */
 893
 894 int
 895 uid_decl_map_eq (const void *va, const void *vb)
 896 {
 897   const_tree a = (const_tree) va;
 898   const_tree b = (const_tree) vb;
 899   return (a->decl_minimal.uid == b->decl_minimal.uid);
 900 }
 901
 902 /* Hash a tree in a uid_decl_map.  */
 903
 904 unsigned int
 905 uid_decl_map_hash (const void *item)
 906 {
 907   return ((const_tree)item)->decl_minimal.uid;
 908 }
 909
 910 /* Return true if the DECL_UID in both trees are equal.  */
 911
 912 static int
 913 uid_ssaname_map_eq (const void *va, const void *vb)
 914 {
 915   const_tree a = (const_tree) va;
 916   const_tree b = (const_tree) vb;
 917   return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
 918 }
 919
 920 /* Hash a tree in a uid_decl_map.  */
 921
 922 static unsigned int
 923 uid_ssaname_map_hash (const void *item)
 924 {
 925   return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
 926 }
 927
 928
 929 /* Initialize global DFA and SSA structures.  */
 930
 931 void
 932 init_tree_ssa (struct function *fn)
 933 {
 934   fn->gimple_df = GGC_CNEW (struct gimple_df);
 935   fn->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
 936                                                     uid_decl_map_eq, NULL);
 937   fn->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
 938                                                  uid_ssaname_map_eq, NULL);
 939   fn->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
 940   fn->gimple_df->call_used_vars = BITMAP_GGC_ALLOC ();
 941   fn->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
 942   init_ssanames (fn, 0);
 943   init_phinodes ();
 944 }
 945
 946
 947 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 948
 949 void
 950 delete_tree_ssa (void)
 951 {
 952   size_t i;
 953   basic_block bb;
 954   block_stmt_iterator bsi;
 955   referenced_var_iterator rvi;
 956   tree var;
 957
 958   /* Release any ssa_names still in use.  */
 959   for (i = 0; i < num_ssa_names; i++)
 960     {
 961       tree var = ssa_name (i);
 962       if (var && TREE_CODE (var) == SSA_NAME)
 963         {
 964           SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
 965           SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
 966         }
 967       release_ssa_name (var);
 968     }
 969
 970   /* Remove annotations from every tree in the function.  */
 971   FOR_EACH_BB (bb)
 972     {
 973       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 974         {
 975           tree stmt = bsi_stmt (bsi);
 976           stmt_ann_t ann = get_stmt_ann (stmt);
 977
 978           free_ssa_operands (&ann->operands);
 979           ann->addresses_taken = 0;
 980           mark_stmt_modified (stmt);
 981         }
 982       set_phi_nodes (bb, NULL);
 983     }
 984
 985   /* Remove annotations from every referenced local variable.  */
 986   FOR_EACH_REFERENCED_VAR (var, rvi)
 987     {
 988       if (!MTAG_P (var)
 989           && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
 990         {
 991           var_ann (var)->mpt = NULL_TREE;
 992           var_ann (var)->symbol_mem_tag = NULL_TREE;
 993           continue;
 994         }
 995       if (var->base.ann)
 996         ggc_free (var->base.ann);
 997       var->base.ann = NULL;
 998     }
 999   htab_delete (gimple_referenced_vars (cfun));
1000   cfun->gimple_df->referenced_vars = NULL;
1001
1002   fini_ssanames ();
1003   fini_phinodes ();
1004   /* we no longer maintain the SSA operand cache at this point.  */
1005   if (ssa_operands_active ())
1006     fini_ssa_operands ();
1007
1008   cfun->gimple_df->global_var = NULL_TREE;
1009
1010   htab_delete (cfun->gimple_df->default_defs);
1011   cfun->gimple_df->default_defs = NULL;
1012   cfun->gimple_df->call_clobbered_vars = NULL;
1013   cfun->gimple_df->call_used_vars = NULL;
1014   cfun->gimple_df->addressable_vars = NULL;
1015   cfun->gimple_df->modified_noreturn_calls = NULL;
1016   if (gimple_aliases_computed_p (cfun))
1017     {
1018       delete_alias_heapvars ();
1019       gcc_assert (!need_ssa_update_p ());
1020     }
1021   cfun->gimple_df->aliases_computed_p = false;
1022   delete_mem_ref_stats (cfun);
1023
1024   cfun->gimple_df = NULL;
1025
1026   /* We no longer need the edge variable maps.  */
1027   redirect_edge_var_map_destroy ();
1028 }
1029
1030 /* Helper function for useless_type_conversion_p.  */
1031
1032 static bool
1033 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
1034 {
1035   /* Qualifiers on value types do not matter.  */
1036   inner_type = TYPE_MAIN_VARIANT (inner_type);
1037   outer_type = TYPE_MAIN_VARIANT (outer_type);
1038
1039   if (inner_type == outer_type)
1040     return true;
1041
1042   /* If we know the canonical types, compare them.  */
1043   if (TYPE_CANONICAL (inner_type)
1044       && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1045     return true;
1046
1047   /* Changes in machine mode are never useless conversions.  */
1048   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1049     return false;
1050
1051   /* If both the inner and outer types are integral types, then the
1052      conversion is not necessary if they have the same mode and
1053      signedness and precision, and both or neither are boolean.  */
1054   if (INTEGRAL_TYPE_P (inner_type)
1055       && INTEGRAL_TYPE_P (outer_type))
1056     {
1057       /* Preserve changes in signedness or precision.  */
1058       if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1059           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1060         return false;
1061
1062       /* Conversions from a non-base to a base type are not useless.
1063          This way we preserve the invariant to do arithmetic in
1064          base types only.  */
1065       if (TREE_TYPE (inner_type)
1066           && TREE_TYPE (inner_type) != inner_type
1067           && (TREE_TYPE (outer_type) == outer_type
1068               || TREE_TYPE (outer_type) == NULL_TREE))
1069         return false;
1070
1071       /* We don't need to preserve changes in the types minimum or
1072          maximum value in general as these do not generate code
1073          unless the types precisions are different.  */
1074
1075       return true;
1076     }
1077
1078   /* Scalar floating point types with the same mode are compatible.  */
1079   else if (SCALAR_FLOAT_TYPE_P (inner_type)
1080            && SCALAR_FLOAT_TYPE_P (outer_type))
1081     return true;
1082
1083   /* We need to take special care recursing to pointed-to types.  */
1084   else if (POINTER_TYPE_P (inner_type)
1085            && POINTER_TYPE_P (outer_type))
1086     {
1087       /* Don't lose casts between pointers to volatile and non-volatile
1088          qualified types.  Doing so would result in changing the semantics
1089          of later accesses.  */
1090       if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
1091            != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1092           && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1093         return false;
1094
1095       /* Do not lose casts between pointers with different
1096          TYPE_REF_CAN_ALIAS_ALL setting or alias sets.  */
1097       if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1098            != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1099           || (get_alias_set (TREE_TYPE (inner_type))
1100               != get_alias_set (TREE_TYPE (outer_type))))
1101         return false;
1102
1103       /* We do not care for const qualification of the pointed-to types
1104          as const qualification has no semantic value to the middle-end.  */
1105
1106       /* Do not lose casts to restrict qualified pointers.  */
1107       if ((TYPE_RESTRICT (outer_type)
1108            != TYPE_RESTRICT (inner_type))
1109           && TYPE_RESTRICT (outer_type))
1110         return false;
1111
1112       /* Otherwise pointers/references are equivalent if their pointed
1113          to types are effectively the same.  We can strip qualifiers
1114          on pointed-to types for further comparison, which is done in
1115          the callee.  */
1116       return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1117                                           TREE_TYPE (inner_type));
1118     }
1119
1120   /* Recurse for complex types.  */
1121   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1122            && TREE_CODE (outer_type) == COMPLEX_TYPE)
1123     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1124                                         TREE_TYPE (inner_type));
1125
1126   /* Recurse for vector types with the same number of subparts.  */
1127   else if (TREE_CODE (inner_type) == VECTOR_TYPE
1128            && TREE_CODE (outer_type) == VECTOR_TYPE
1129            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1130     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1131                                         TREE_TYPE (inner_type));
1132
1133   /* For aggregates we may need to fall back to structural equality
1134      checks.  */
1135   else if (AGGREGATE_TYPE_P (inner_type)
1136            && AGGREGATE_TYPE_P (outer_type))
1137     {
1138       /* Different types of aggregates are incompatible.  */
1139       if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1140         return false;
1141
1142       /* ???  Add structural equivalence check.  */
1143
1144       /* ???  This should eventually just return false.  */
1145       return lang_hooks.types_compatible_p (inner_type, outer_type);
1146     }
1147
1148   return false;
1149 }
1150
1151 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1152    useless type conversion, otherwise return false.
1153
1154    This function implicitly defines the middle-end type system.  With
1155    the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1156    holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1157    the following invariants shall be fulfilled:
1158
1159      1) useless_type_conversion_p is transitive.
1160         If a < b and b < c then a < c.
1161
1162      2) useless_type_conversion_p is not symmetric.
1163         From a < b does not follow a > b.
1164
1165      3) Types define the available set of operations applicable to values.
1166         A type conversion is useless if the operations for the target type
1167         is a subset of the operations for the source type.  For example
1168         casts to void* are useless, casts from void* are not (void* can't
1169         be dereferenced or offsetted, but copied, hence its set of operations
1170         is a strict subset of that of all other data pointer types).  Casts
1171         to const T* are useless (can't be written to), casts from const T*
1172         to T* are not.  */
1173
1174 bool
1175 useless_type_conversion_p (tree outer_type, tree inner_type)
1176 {
1177   /* If the outer type is (void *), then the conversion is not
1178      necessary.  We have to make sure to not apply this while
1179      recursing though.  */
1180   if (POINTER_TYPE_P (inner_type)
1181       && POINTER_TYPE_P (outer_type)
1182       && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1183     return true;
1184
1185   return useless_type_conversion_p_1 (outer_type, inner_type);
1186 }
1187
1188 /* Return true if a conversion from either type of TYPE1 and TYPE2
1189    to the other is not required.  Otherwise return false.  */
1190
1191 bool
1192 types_compatible_p (tree type1, tree type2)
1193 {
1194   return (type1 == type2
1195           || (useless_type_conversion_p (type1, type2)
1196               && useless_type_conversion_p (type2, type1)));
1197 }
1198
1199 /* Return true if EXPR is a useless type conversion, otherwise return
1200    false.  */
1201
1202 bool
1203 tree_ssa_useless_type_conversion (tree expr)
1204 {
1205   /* If we have an assignment that merely uses a NOP_EXPR to change
1206      the top of the RHS to the type of the LHS and the type conversion
1207      is "safe", then strip away the type conversion so that we can
1208      enter LHS = RHS into the const_and_copies table.  */
1209   if (CONVERT_EXPR_P (expr)
1210       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1211       || TREE_CODE (expr) == NON_LVALUE_EXPR)
1212     /* FIXME: Use of GENERIC_TREE_TYPE here is a temporary measure to work
1213        around known bugs with GIMPLE_MODIFY_STMTs appearing in places
1214        they shouldn't.  See PR 30391.  */
1215     return useless_type_conversion_p
1216       (TREE_TYPE (expr),
1217        GENERIC_TREE_TYPE (TREE_OPERAND (expr, 0)));
1218
1219   return false;
1220 }
1221
1222
1223 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
1224    described in walk_use_def_chains.
1225
1226    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1227       infinite loops.  We used to have a bitmap for this to just mark
1228       SSA versions we had visited.  But non-sparse bitmaps are way too
1229       expensive, while sparse bitmaps may cause quadratic behavior.
1230
1231    IS_DFS is true if the caller wants to perform a depth-first search
1232       when visiting PHI nodes.  A DFS will visit each PHI argument and
1233       call FN after each one.  Otherwise, all the arguments are
1234       visited first and then FN is called with each of the visited
1235       arguments in a separate pass.  */
1236
1237 static bool
1238 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1239                        struct pointer_set_t *visited, bool is_dfs)
1240 {
1241   tree def_stmt;
1242
1243   if (pointer_set_insert (visited, var))
1244     return false;
1245
1246   def_stmt = SSA_NAME_DEF_STMT (var);
1247
1248   if (TREE_CODE (def_stmt) != PHI_NODE)
1249     {
1250       /* If we reached the end of the use-def chain, call FN.  */
1251       return fn (var, def_stmt, data);
1252     }
1253   else
1254     {
1255       int i;
1256
1257       /* When doing a breadth-first search, call FN before following the
1258          use-def links for each argument.  */
1259       if (!is_dfs)
1260         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1261           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1262             return true;
1263
1264       /* Follow use-def links out of each PHI argument.  */
1265       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1266         {
1267           tree arg = PHI_ARG_DEF (def_stmt, i);
1268
1269           /* ARG may be NULL for newly introduced PHI nodes.  */
1270           if (arg
1271               && TREE_CODE (arg) == SSA_NAME
1272               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1273             return true;
1274         }
1275
1276       /* When doing a depth-first search, call FN after following the
1277          use-def links for each argument.  */
1278       if (is_dfs)
1279         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1280           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1281             return true;
1282     }
1283
1284   return false;
1285 }
1286
1287
1288
1289 /* Walk use-def chains starting at the SSA variable VAR.  Call
1290    function FN at each reaching definition found.  FN takes three
1291    arguments: VAR, its defining statement (DEF_STMT) and a generic
1292    pointer to whatever state information that FN may want to maintain
1293    (DATA).  FN is able to stop the walk by returning true, otherwise
1294    in order to continue the walk, FN should return false.
1295
1296    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1297    different.  The first argument to FN is no longer the original
1298    variable VAR, but the PHI argument currently being examined.  If FN
1299    wants to get at VAR, it should call PHI_RESULT (PHI).
1300
1301    If IS_DFS is true, this function will:
1302
1303         1- walk the use-def chains for all the PHI arguments, and,
1304         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1305
1306    If IS_DFS is false, the two steps above are done in reverse order
1307    (i.e., a breadth-first search).  */
1308
1309 void
1310 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1311                      bool is_dfs)
1312 {
1313   tree def_stmt;
1314
1315   gcc_assert (TREE_CODE (var) == SSA_NAME);
1316
1317   def_stmt = SSA_NAME_DEF_STMT (var);
1318
1319   /* We only need to recurse if the reaching definition comes from a PHI
1320      node.  */
1321   if (TREE_CODE (def_stmt) != PHI_NODE)
1322     (*fn) (var, def_stmt, data);
1323   else
1324     {
1325       struct pointer_set_t *visited = pointer_set_create ();
1326       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1327       pointer_set_destroy (visited);
1328     }
1329 }
1330
1331 \f
1332 /* Return true if T, an SSA_NAME, has an undefined value.  */
1333
1334 bool
1335 ssa_undefined_value_p (tree t)
1336 {
1337   tree var = SSA_NAME_VAR (t);
1338
1339   /* Parameters get their initial value from the function entry.  */
1340   if (TREE_CODE (var) == PARM_DECL)
1341     return false;
1342
1343   /* Hard register variables get their initial value from the ether.  */
1344   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1345     return false;
1346
1347   /* The value is undefined iff its definition statement is empty.  */
1348   return IS_EMPTY_STMT (SSA_NAME_DEF_STMT (t));
1349 }
1350
1351 /* Emit warnings for uninitialized variables.  This is done in two passes.
1352
1353    The first pass notices real uses of SSA names with undefined values.
1354    Such uses are unconditionally uninitialized, and we can be certain that
1355    such a use is a mistake.  This pass is run before most optimizations,
1356    so that we catch as many as we can.
1357
1358    The second pass follows PHI nodes to find uses that are potentially
1359    uninitialized.  In this case we can't necessarily prove that the use
1360    is really uninitialized.  This pass is run after most optimizations,
1361    so that we thread as many jumps and possible, and delete as much dead
1362    code as possible, in order to reduce false positives.  We also look
1363    again for plain uninitialized variables, since optimization may have
1364    changed conditionally uninitialized to unconditionally uninitialized.  */
1365
1366 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1367    warning text is in MSGID and LOCUS may contain a location or be null.  */
1368
1369 static void
1370 warn_uninit (tree t, const char *gmsgid, void *data)
1371 {
1372   tree var = SSA_NAME_VAR (t);
1373   tree context = (tree) data;
1374   location_t *locus;
1375   expanded_location xloc, floc;
1376
1377   if (!ssa_undefined_value_p (t))
1378     return;
1379
1380   /* TREE_NO_WARNING either means we already warned, or the front end
1381      wishes to suppress the warning.  */
1382   if (TREE_NO_WARNING (var))
1383     return;
1384
1385   locus = (context != NULL && EXPR_HAS_LOCATION (context)
1386            ? EXPR_LOCUS (context)
1387            : &DECL_SOURCE_LOCATION (var));
1388   warning (OPT_Wuninitialized, gmsgid, locus, var);
1389   xloc = expand_location (*locus);
1390   floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1391   if (xloc.file != floc.file
1392       || xloc.line < floc.line
1393       || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1394     inform ("%J%qD was declared here", var, var);
1395
1396   TREE_NO_WARNING (var) = 1;
1397 }
1398
1399 struct walk_data {
1400   tree stmt;
1401   bool always_executed;
1402 };
1403
1404 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1405    and warn about them.  */
1406
1407 static tree
1408 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1409 {
1410   struct walk_data *data = (struct walk_data *)data_;
1411   tree t = *tp;
1412
1413   switch (TREE_CODE (t))
1414     {
1415     case SSA_NAME:
1416       /* We only do data flow with SSA_NAMEs, so that's all we
1417          can warn about.  */
1418       if (data->always_executed)
1419         warn_uninit (t, "%H%qD is used uninitialized in this function",
1420                      data->stmt);
1421       else
1422         warn_uninit (t, "%H%qD may be used uninitialized in this function",
1423                      data->stmt);
1424       *walk_subtrees = 0;
1425       break;
1426
1427     case REALPART_EXPR:
1428     case IMAGPART_EXPR:
1429       /* The total store transformation performed during gimplification
1430          creates uninitialized variable uses.  If all is well, these will
1431          be optimized away, so don't warn now.  */
1432       if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1433         *walk_subtrees = 0;
1434       break;
1435
1436     default:
1437       if (IS_TYPE_OR_DECL_P (t))
1438         *walk_subtrees = 0;
1439       break;
1440     }
1441
1442   return NULL_TREE;
1443 }
1444
1445 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1446    and warn about them.  */
1447
1448 static void
1449 warn_uninitialized_phi (tree phi)
1450 {
1451   int i, n = PHI_NUM_ARGS (phi);
1452
1453   /* Don't look at memory tags.  */
1454   if (!is_gimple_reg (PHI_RESULT (phi)))
1455     return;
1456
1457   for (i = 0; i < n; ++i)
1458     {
1459       tree op = PHI_ARG_DEF (phi, i);
1460       if (TREE_CODE (op) == SSA_NAME)
1461         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1462                      NULL);
1463     }
1464 }
1465
1466 static unsigned int
1467 execute_early_warn_uninitialized (void)
1468 {
1469   block_stmt_iterator bsi;
1470   basic_block bb;
1471   struct walk_data data;
1472
1473   calculate_dominance_info (CDI_POST_DOMINATORS);
1474
1475   FOR_EACH_BB (bb)
1476     {
1477       data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1478                                              single_succ (ENTRY_BLOCK_PTR), bb);
1479       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1480         {
1481           data.stmt = bsi_stmt (bsi);
1482           walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1483                      &data, NULL);
1484         }
1485     }
1486   return 0;
1487 }
1488
1489 static unsigned int
1490 execute_late_warn_uninitialized (void)
1491 {
1492   basic_block bb;
1493   tree phi;
1494
1495   /* Re-do the plain uninitialized variable check, as optimization may have
1496      straightened control flow.  Do this first so that we don't accidentally
1497      get a "may be" warning when we'd have seen an "is" warning later.  */
1498   execute_early_warn_uninitialized ();
1499
1500   FOR_EACH_BB (bb)
1501     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1502       warn_uninitialized_phi (phi);
1503   return 0;
1504 }
1505
1506 static bool
1507 gate_warn_uninitialized (void)
1508 {
1509   return warn_uninitialized != 0;
1510 }
1511
1512 struct gimple_opt_pass pass_early_warn_uninitialized =
1513 {
1514  {
1515   GIMPLE_PASS,
1516   NULL,                                 /* name */
1517   gate_warn_uninitialized,              /* gate */
1518   execute_early_warn_uninitialized,     /* execute */
1519   NULL,                                 /* sub */
1520   NULL,                                 /* next */
1521   0,                                    /* static_pass_number */
1522   0,                                    /* tv_id */
1523   PROP_ssa,                             /* properties_required */
1524   0,                                    /* properties_provided */
1525   0,                                    /* properties_destroyed */
1526   0,                                    /* todo_flags_start */
1527   0                                     /* todo_flags_finish */
1528  }
1529 };
1530
1531 struct gimple_opt_pass pass_late_warn_uninitialized =
1532 {
1533  {
1534   GIMPLE_PASS,
1535   NULL,                                 /* name */
1536   gate_warn_uninitialized,              /* gate */
1537   execute_late_warn_uninitialized,      /* execute */
1538   NULL,                                 /* sub */
1539   NULL,                                 /* next */
1540   0,                                    /* static_pass_number */
1541   0,                                    /* tv_id */
1542   PROP_ssa,                             /* properties_required */
1543   0,                                    /* properties_provided */
1544   0,                                    /* properties_destroyed */
1545   0,                                    /* todo_flags_start */
1546   0                                     /* todo_flags_finish */
1547  }
1548 };
1549
1550 /* Compute TREE_ADDRESSABLE for local variables.  */
1551
1552 static unsigned int
1553 execute_update_addresses_taken (void)
1554 {
1555   tree var;
1556   referenced_var_iterator rvi;
1557   block_stmt_iterator bsi;
1558   basic_block bb;
1559   bitmap addresses_taken = BITMAP_ALLOC (NULL);
1560   bitmap vars_updated = BITMAP_ALLOC (NULL);
1561   bool update_vops = false;
1562   tree phi;
1563
1564   /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1565      the function body.  */
1566   FOR_EACH_BB (bb)
1567     {
1568       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1569         {
1570           stmt_ann_t s_ann = stmt_ann (bsi_stmt (bsi));
1571
1572           if (s_ann->addresses_taken)
1573             bitmap_ior_into (addresses_taken, s_ann->addresses_taken);
1574         }
1575       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1576         {
1577           unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
1578           for (i = 0; i < phi_num_args; i++)
1579             {
1580               tree op = PHI_ARG_DEF (phi, i), var;
1581               if (TREE_CODE (op) == ADDR_EXPR
1582                   && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL_TREE
1583                   && DECL_P (var))
1584                 bitmap_set_bit (addresses_taken, DECL_UID (var));
1585             }
1586         }
1587     }
1588
1589   /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1590      SSA.  */
1591   FOR_EACH_REFERENCED_VAR (var, rvi)
1592     if (!is_global_var (var)
1593         && TREE_CODE (var) != RESULT_DECL
1594         && TREE_ADDRESSABLE (var)
1595         && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
1596       {
1597         TREE_ADDRESSABLE (var) = 0;
1598         if (is_gimple_reg (var))
1599           mark_sym_for_renaming (var);
1600         update_vops = true;
1601         bitmap_set_bit (vars_updated, DECL_UID (var));
1602         if (dump_file)
1603           {
1604             fprintf (dump_file, "No longer having address taken ");
1605             print_generic_expr (dump_file, var, 0);
1606             fprintf (dump_file, "\n");
1607           }
1608       }
1609
1610   /* Operand caches needs to be recomputed for operands referencing the updated
1611      variables.  */
1612   if (update_vops)
1613     FOR_EACH_BB (bb)
1614       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1615         {
1616           tree stmt = bsi_stmt (bsi);
1617
1618           if ((LOADED_SYMS (stmt)
1619                && bitmap_intersect_p (LOADED_SYMS (stmt), vars_updated))
1620               || (STORED_SYMS (stmt)
1621                   && bitmap_intersect_p (STORED_SYMS (stmt), vars_updated)))
1622             update_stmt (stmt);
1623         }
1624   BITMAP_FREE (addresses_taken);
1625   BITMAP_FREE (vars_updated);
1626   return 0;
1627 }
1628
1629 struct gimple_opt_pass pass_update_address_taken =
1630 {
1631  {
1632   GIMPLE_PASS,
1633   "addressables",                       /* name */
1634   NULL,                                 /* gate */
1635   execute_update_addresses_taken,       /* execute */
1636   NULL,                                 /* sub */
1637   NULL,                                 /* next */
1638   0,                                    /* static_pass_number */
1639   0,                                    /* tv_id */
1640   PROP_ssa,                             /* properties_required */
1641   0,                                    /* properties_provided */
1642   0,                                    /* properties_destroyed */
1643   0,                                    /* todo_flags_start */
1644   TODO_update_ssa                       /* todo_flags_finish */
1645  }
1646 };