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 = *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 = *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 = *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->addressable_vars = BITMAP_GGC_ALLOC ();
 941   init_ssanames (fn, 0);
 942   init_phinodes ();
 943 }
 944
 945
 946 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 947
 948 void
 949 delete_tree_ssa (void)
 950 {
 951   size_t i;
 952   basic_block bb;
 953   block_stmt_iterator bsi;
 954   referenced_var_iterator rvi;
 955   tree var;
 956
 957   /* Release any ssa_names still in use.  */
 958   for (i = 0; i < num_ssa_names; i++)
 959     {
 960       tree var = ssa_name (i);
 961       if (var && TREE_CODE (var) == SSA_NAME)
 962         {
 963           SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
 964           SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
 965         }
 966       release_ssa_name (var);
 967     }
 968
 969   /* Remove annotations from every tree in the function.  */
 970   FOR_EACH_BB (bb)
 971     {
 972       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 973         {
 974           tree stmt = bsi_stmt (bsi);
 975           stmt_ann_t ann = get_stmt_ann (stmt);
 976
 977           free_ssa_operands (&ann->operands);
 978           ann->addresses_taken = 0;
 979           mark_stmt_modified (stmt);
 980         }
 981       set_phi_nodes (bb, NULL);
 982     }
 983
 984   /* Remove annotations from every referenced local variable.  */
 985   FOR_EACH_REFERENCED_VAR (var, rvi)
 986     {
 987       if (!MTAG_P (var)
 988           && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
 989         {
 990           var_ann (var)->mpt = NULL_TREE;
 991           var_ann (var)->symbol_mem_tag = NULL_TREE;
 992           continue;
 993         }
 994       if (var->base.ann)
 995         ggc_free (var->base.ann);
 996       var->base.ann = NULL;
 997     }
 998   htab_delete (gimple_referenced_vars (cfun));
 999   cfun->gimple_df->referenced_vars = NULL;
1000
1001   fini_ssanames ();
1002   fini_phinodes ();
1003   /* we no longer maintain the SSA operand cache at this point.  */
1004   if (ssa_operands_active ())
1005     fini_ssa_operands ();
1006
1007   cfun->gimple_df->global_var = NULL_TREE;
1008
1009   htab_delete (cfun->gimple_df->default_defs);
1010   cfun->gimple_df->default_defs = NULL;
1011   cfun->gimple_df->call_clobbered_vars = NULL;
1012   cfun->gimple_df->addressable_vars = NULL;
1013   cfun->gimple_df->modified_noreturn_calls = NULL;
1014   if (gimple_aliases_computed_p (cfun))
1015     {
1016       delete_alias_heapvars ();
1017       gcc_assert (!need_ssa_update_p ());
1018     }
1019   cfun->gimple_df->aliases_computed_p = false;
1020   delete_mem_ref_stats (cfun);
1021
1022   cfun->gimple_df = NULL;
1023
1024   /* We no longer need the edge variable maps.  */
1025   redirect_edge_var_map_destroy ();
1026 }
1027
1028 /* Helper function for useless_type_conversion_p.  */
1029
1030 static bool
1031 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
1032 {
1033   /* Qualifiers on value types do not matter.  */
1034   inner_type = TYPE_MAIN_VARIANT (inner_type);
1035   outer_type = TYPE_MAIN_VARIANT (outer_type);
1036
1037   if (inner_type == outer_type)
1038     return true;
1039
1040   /* If we know the canonical types, compare them.  */
1041   if (TYPE_CANONICAL (inner_type)
1042       && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1043     return true;
1044
1045   /* Changes in machine mode are never useless conversions.  */
1046   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1047     return false;
1048
1049   /* If both the inner and outer types are integral types, then the
1050      conversion is not necessary if they have the same mode and
1051      signedness and precision, and both or neither are boolean.  */
1052   if (INTEGRAL_TYPE_P (inner_type)
1053       && INTEGRAL_TYPE_P (outer_type))
1054     {
1055       /* Preserve changes in signedness or precision.  */
1056       if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1057           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1058         return false;
1059
1060       /* Conversions from a non-base to a base type are not useless.
1061          This way we preserve the invariant to do arithmetic in
1062          base types only.  */
1063       if (TREE_TYPE (inner_type)
1064           && TREE_TYPE (inner_type) != inner_type
1065           && (TREE_TYPE (outer_type) == outer_type
1066               || TREE_TYPE (outer_type) == NULL_TREE))
1067         return false;
1068
1069       /* We don't need to preserve changes in the types minimum or
1070          maximum value in general as these do not generate code
1071          unless the types precisions are different.  */
1072
1073       return true;
1074     }
1075
1076   /* Scalar floating point types with the same mode are compatible.  */
1077   else if (SCALAR_FLOAT_TYPE_P (inner_type)
1078            && SCALAR_FLOAT_TYPE_P (outer_type))
1079     return true;
1080
1081   /* We need to take special care recursing to pointed-to types.  */
1082   else if (POINTER_TYPE_P (inner_type)
1083            && POINTER_TYPE_P (outer_type))
1084     {
1085       /* Don't lose casts between pointers to volatile and non-volatile
1086          qualified types.  Doing so would result in changing the semantics
1087          of later accesses.  */
1088       if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
1089            != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1090           && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1091         return false;
1092
1093       /* Do not lose casts between pointers with different
1094          TYPE_REF_CAN_ALIAS_ALL setting or alias sets.  */
1095       if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1096            != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1097           || (get_alias_set (TREE_TYPE (inner_type))
1098               != get_alias_set (TREE_TYPE (outer_type))))
1099         return false;
1100
1101       /* We do not care for const qualification of the pointed-to types
1102          as const qualification has no semantic value to the middle-end.  */
1103
1104       /* Do not lose casts to restrict qualified pointers.  */
1105       if ((TYPE_RESTRICT (outer_type)
1106            != TYPE_RESTRICT (inner_type))
1107           && TYPE_RESTRICT (outer_type))
1108         return false;
1109
1110       /* Otherwise pointers/references are equivalent if their pointed
1111          to types are effectively the same.  We can strip qualifiers
1112          on pointed-to types for further comparison, which is done in
1113          the callee.  */
1114       return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1115                                           TREE_TYPE (inner_type));
1116     }
1117
1118   /* Recurse for complex types.  */
1119   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1120            && TREE_CODE (outer_type) == COMPLEX_TYPE)
1121     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1122                                         TREE_TYPE (inner_type));
1123
1124   /* Recurse for vector types with the same number of subparts.  */
1125   else if (TREE_CODE (inner_type) == VECTOR_TYPE
1126            && TREE_CODE (outer_type) == VECTOR_TYPE
1127            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1128     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1129                                         TREE_TYPE (inner_type));
1130
1131   /* For aggregates we may need to fall back to structural equality
1132      checks.  */
1133   else if (AGGREGATE_TYPE_P (inner_type)
1134            && AGGREGATE_TYPE_P (outer_type))
1135     {
1136       /* Different types of aggregates are incompatible.  */
1137       if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1138         return false;
1139
1140       /* ???  Add structural equivalence check.  */
1141
1142       /* ???  This should eventually just return false.  */
1143       return lang_hooks.types_compatible_p (inner_type, outer_type);
1144     }
1145
1146   return false;
1147 }
1148
1149 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1150    useless type conversion, otherwise return false.
1151
1152    This function implicitly defines the middle-end type system.  With
1153    the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1154    holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1155    the following invariants shall be fulfilled:
1156
1157      1) useless_type_conversion_p is transitive.
1158         If a < b and b < c then a < c.
1159
1160      2) useless_type_conversion_p is not symmetric.
1161         From a < b does not follow a > b.
1162
1163      3) Types define the available set of operations applicable to values.
1164         A type conversion is useless if the operations for the target type
1165         is a subset of the operations for the source type.  For example
1166         casts to void* are useless, casts from void* are not (void* can't
1167         be dereferenced or offsetted, but copied, hence its set of operations
1168         is a strict subset of that of all other data pointer types).  Casts
1169         to const T* are useless (can't be written to), casts from const T*
1170         to T* are not.  */
1171
1172 bool
1173 useless_type_conversion_p (tree outer_type, tree inner_type)
1174 {
1175   /* If the outer type is (void *), then the conversion is not
1176      necessary.  We have to make sure to not apply this while
1177      recursing though.  */
1178   if (POINTER_TYPE_P (inner_type)
1179       && POINTER_TYPE_P (outer_type)
1180       && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1181     return true;
1182
1183   return useless_type_conversion_p_1 (outer_type, inner_type);
1184 }
1185
1186 /* Return true if a conversion from either type of TYPE1 and TYPE2
1187    to the other is not required.  Otherwise return false.  */
1188
1189 bool
1190 types_compatible_p (tree type1, tree type2)
1191 {
1192   return (type1 == type2
1193           || (useless_type_conversion_p (type1, type2)
1194               && useless_type_conversion_p (type2, type1)));
1195 }
1196
1197 /* Return true if EXPR is a useless type conversion, otherwise return
1198    false.  */
1199
1200 bool
1201 tree_ssa_useless_type_conversion (tree expr)
1202 {
1203   /* If we have an assignment that merely uses a NOP_EXPR to change
1204      the top of the RHS to the type of the LHS and the type conversion
1205      is "safe", then strip away the type conversion so that we can
1206      enter LHS = RHS into the const_and_copies table.  */
1207   if (CONVERT_EXPR_P (expr)
1208       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1209       || TREE_CODE (expr) == NON_LVALUE_EXPR)
1210     /* FIXME: Use of GENERIC_TREE_TYPE here is a temporary measure to work
1211        around known bugs with GIMPLE_MODIFY_STMTs appearing in places
1212        they shouldn't.  See PR 30391.  */
1213     return useless_type_conversion_p
1214       (TREE_TYPE (expr),
1215        GENERIC_TREE_TYPE (TREE_OPERAND (expr, 0)));
1216
1217   return false;
1218 }
1219
1220
1221 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
1222    described in walk_use_def_chains.
1223
1224    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1225       infinite loops.  We used to have a bitmap for this to just mark
1226       SSA versions we had visited.  But non-sparse bitmaps are way too
1227       expensive, while sparse bitmaps may cause quadratic behavior.
1228
1229    IS_DFS is true if the caller wants to perform a depth-first search
1230       when visiting PHI nodes.  A DFS will visit each PHI argument and
1231       call FN after each one.  Otherwise, all the arguments are
1232       visited first and then FN is called with each of the visited
1233       arguments in a separate pass.  */
1234
1235 static bool
1236 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1237                        struct pointer_set_t *visited, bool is_dfs)
1238 {
1239   tree def_stmt;
1240
1241   if (pointer_set_insert (visited, var))
1242     return false;
1243
1244   def_stmt = SSA_NAME_DEF_STMT (var);
1245
1246   if (TREE_CODE (def_stmt) != PHI_NODE)
1247     {
1248       /* If we reached the end of the use-def chain, call FN.  */
1249       return fn (var, def_stmt, data);
1250     }
1251   else
1252     {
1253       int i;
1254
1255       /* When doing a breadth-first search, call FN before following the
1256          use-def links for each argument.  */
1257       if (!is_dfs)
1258         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1259           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1260             return true;
1261
1262       /* Follow use-def links out of each PHI argument.  */
1263       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1264         {
1265           tree arg = PHI_ARG_DEF (def_stmt, i);
1266
1267           /* ARG may be NULL for newly introduced PHI nodes.  */
1268           if (arg
1269               && TREE_CODE (arg) == SSA_NAME
1270               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1271             return true;
1272         }
1273
1274       /* When doing a depth-first search, call FN after following the
1275          use-def links for each argument.  */
1276       if (is_dfs)
1277         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1278           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1279             return true;
1280     }
1281
1282   return false;
1283 }
1284
1285
1286
1287 /* Walk use-def chains starting at the SSA variable VAR.  Call
1288    function FN at each reaching definition found.  FN takes three
1289    arguments: VAR, its defining statement (DEF_STMT) and a generic
1290    pointer to whatever state information that FN may want to maintain
1291    (DATA).  FN is able to stop the walk by returning true, otherwise
1292    in order to continue the walk, FN should return false.
1293
1294    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1295    different.  The first argument to FN is no longer the original
1296    variable VAR, but the PHI argument currently being examined.  If FN
1297    wants to get at VAR, it should call PHI_RESULT (PHI).
1298
1299    If IS_DFS is true, this function will:
1300
1301         1- walk the use-def chains for all the PHI arguments, and,
1302         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1303
1304    If IS_DFS is false, the two steps above are done in reverse order
1305    (i.e., a breadth-first search).  */
1306
1307 void
1308 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1309                      bool is_dfs)
1310 {
1311   tree def_stmt;
1312
1313   gcc_assert (TREE_CODE (var) == SSA_NAME);
1314
1315   def_stmt = SSA_NAME_DEF_STMT (var);
1316
1317   /* We only need to recurse if the reaching definition comes from a PHI
1318      node.  */
1319   if (TREE_CODE (def_stmt) != PHI_NODE)
1320     (*fn) (var, def_stmt, data);
1321   else
1322     {
1323       struct pointer_set_t *visited = pointer_set_create ();
1324       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1325       pointer_set_destroy (visited);
1326     }
1327 }
1328
1329 \f
1330 /* Return true if T, an SSA_NAME, has an undefined value.  */
1331
1332 bool
1333 ssa_undefined_value_p (tree t)
1334 {
1335   tree var = SSA_NAME_VAR (t);
1336
1337   /* Parameters get their initial value from the function entry.  */
1338   if (TREE_CODE (var) == PARM_DECL)
1339     return false;
1340
1341   /* Hard register variables get their initial value from the ether.  */
1342   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1343     return false;
1344
1345   /* The value is undefined iff its definition statement is empty.  */
1346   return IS_EMPTY_STMT (SSA_NAME_DEF_STMT (t));
1347 }
1348
1349 /* Emit warnings for uninitialized variables.  This is done in two passes.
1350
1351    The first pass notices real uses of SSA names with undefined values.
1352    Such uses are unconditionally uninitialized, and we can be certain that
1353    such a use is a mistake.  This pass is run before most optimizations,
1354    so that we catch as many as we can.
1355
1356    The second pass follows PHI nodes to find uses that are potentially
1357    uninitialized.  In this case we can't necessarily prove that the use
1358    is really uninitialized.  This pass is run after most optimizations,
1359    so that we thread as many jumps and possible, and delete as much dead
1360    code as possible, in order to reduce false positives.  We also look
1361    again for plain uninitialized variables, since optimization may have
1362    changed conditionally uninitialized to unconditionally uninitialized.  */
1363
1364 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1365    warning text is in MSGID and LOCUS may contain a location or be null.  */
1366
1367 static void
1368 warn_uninit (tree t, const char *gmsgid, void *data)
1369 {
1370   tree var = SSA_NAME_VAR (t);
1371   tree context = (tree) data;
1372   location_t *locus;
1373   expanded_location xloc, floc;
1374
1375   if (!ssa_undefined_value_p (t))
1376     return;
1377
1378   /* TREE_NO_WARNING either means we already warned, or the front end
1379      wishes to suppress the warning.  */
1380   if (TREE_NO_WARNING (var))
1381     return;
1382
1383   locus = (context != NULL && EXPR_HAS_LOCATION (context)
1384            ? EXPR_LOCUS (context)
1385            : &DECL_SOURCE_LOCATION (var));
1386   warning (OPT_Wuninitialized, gmsgid, locus, var);
1387   xloc = expand_location (*locus);
1388   floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1389   if (xloc.file != floc.file
1390       || xloc.line < floc.line
1391       || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1392     inform ("%J%qD was declared here", var, var);
1393
1394   TREE_NO_WARNING (var) = 1;
1395 }
1396
1397 struct walk_data {
1398   tree stmt;
1399   bool always_executed;
1400 };
1401
1402 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1403    and warn about them.  */
1404
1405 static tree
1406 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1407 {
1408   struct walk_data *data = (struct walk_data *)data_;
1409   tree t = *tp;
1410
1411   switch (TREE_CODE (t))
1412     {
1413     case SSA_NAME:
1414       /* We only do data flow with SSA_NAMEs, so that's all we
1415          can warn about.  */
1416       if (data->always_executed)
1417         warn_uninit (t, "%H%qD is used uninitialized in this function",
1418                      data->stmt);
1419       else
1420         warn_uninit (t, "%H%qD may be used uninitialized in this function",
1421                      data->stmt);
1422       *walk_subtrees = 0;
1423       break;
1424
1425     case REALPART_EXPR:
1426     case IMAGPART_EXPR:
1427       /* The total store transformation performed during gimplification
1428          creates uninitialized variable uses.  If all is well, these will
1429          be optimized away, so don't warn now.  */
1430       if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1431         *walk_subtrees = 0;
1432       break;
1433
1434     default:
1435       if (IS_TYPE_OR_DECL_P (t))
1436         *walk_subtrees = 0;
1437       break;
1438     }
1439
1440   return NULL_TREE;
1441 }
1442
1443 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1444    and warn about them.  */
1445
1446 static void
1447 warn_uninitialized_phi (tree phi)
1448 {
1449   int i, n = PHI_NUM_ARGS (phi);
1450
1451   /* Don't look at memory tags.  */
1452   if (!is_gimple_reg (PHI_RESULT (phi)))
1453     return;
1454
1455   for (i = 0; i < n; ++i)
1456     {
1457       tree op = PHI_ARG_DEF (phi, i);
1458       if (TREE_CODE (op) == SSA_NAME)
1459         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1460                      NULL);
1461     }
1462 }
1463
1464 static unsigned int
1465 execute_early_warn_uninitialized (void)
1466 {
1467   block_stmt_iterator bsi;
1468   basic_block bb;
1469   struct walk_data data;
1470
1471   calculate_dominance_info (CDI_POST_DOMINATORS);
1472
1473   FOR_EACH_BB (bb)
1474     {
1475       data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1476                                              single_succ (ENTRY_BLOCK_PTR), bb);
1477       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1478         {
1479           data.stmt = bsi_stmt (bsi);
1480           walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1481                      &data, NULL);
1482         }
1483     }
1484   return 0;
1485 }
1486
1487 static unsigned int
1488 execute_late_warn_uninitialized (void)
1489 {
1490   basic_block bb;
1491   tree phi;
1492
1493   /* Re-do the plain uninitialized variable check, as optimization may have
1494      straightened control flow.  Do this first so that we don't accidentally
1495      get a "may be" warning when we'd have seen an "is" warning later.  */
1496   execute_early_warn_uninitialized ();
1497
1498   FOR_EACH_BB (bb)
1499     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1500       warn_uninitialized_phi (phi);
1501   return 0;
1502 }
1503
1504 static bool
1505 gate_warn_uninitialized (void)
1506 {
1507   return warn_uninitialized != 0;
1508 }
1509
1510 struct gimple_opt_pass pass_early_warn_uninitialized =
1511 {
1512  {
1513   GIMPLE_PASS,
1514   NULL,                                 /* name */
1515   gate_warn_uninitialized,              /* gate */
1516   execute_early_warn_uninitialized,     /* execute */
1517   NULL,                                 /* sub */
1518   NULL,                                 /* next */
1519   0,                                    /* static_pass_number */
1520   0,                                    /* tv_id */
1521   PROP_ssa,                             /* properties_required */
1522   0,                                    /* properties_provided */
1523   0,                                    /* properties_destroyed */
1524   0,                                    /* todo_flags_start */
1525   0                                     /* todo_flags_finish */
1526  }
1527 };
1528
1529 struct gimple_opt_pass pass_late_warn_uninitialized =
1530 {
1531  {
1532   GIMPLE_PASS,
1533   NULL,                                 /* name */
1534   gate_warn_uninitialized,              /* gate */
1535   execute_late_warn_uninitialized,      /* execute */
1536   NULL,                                 /* sub */
1537   NULL,                                 /* next */
1538   0,                                    /* static_pass_number */
1539   0,                                    /* tv_id */
1540   PROP_ssa,                             /* properties_required */
1541   0,                                    /* properties_provided */
1542   0,                                    /* properties_destroyed */
1543   0,                                    /* todo_flags_start */
1544   0                                     /* todo_flags_finish */
1545  }
1546 };
1547
1548 /* Compute TREE_ADDRESSABLE for local variables.  */
1549
1550 static unsigned int
1551 execute_update_addresses_taken (void)
1552 {
1553   tree var;
1554   referenced_var_iterator rvi;
1555   block_stmt_iterator bsi;
1556   basic_block bb;
1557   bitmap addresses_taken = BITMAP_ALLOC (NULL);
1558   bitmap vars_updated = BITMAP_ALLOC (NULL);
1559   bool update_vops = false;
1560   tree phi;
1561
1562   /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1563      the function body.  */
1564   FOR_EACH_BB (bb)
1565     {
1566       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1567         {
1568           stmt_ann_t s_ann = stmt_ann (bsi_stmt (bsi));
1569
1570           if (s_ann->addresses_taken)
1571             bitmap_ior_into (addresses_taken, s_ann->addresses_taken);
1572         }
1573       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1574         {
1575           unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
1576           for (i = 0; i < phi_num_args; i++)
1577             {
1578               tree op = PHI_ARG_DEF (phi, i), var;
1579               if (TREE_CODE (op) == ADDR_EXPR
1580                   && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL_TREE
1581                   && DECL_P (var))
1582                 bitmap_set_bit (addresses_taken, DECL_UID (var));
1583             }
1584         }
1585     }
1586
1587   /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1588      SSA.  */
1589   FOR_EACH_REFERENCED_VAR (var, rvi)
1590     if (!is_global_var (var)
1591         && TREE_CODE (var) != RESULT_DECL
1592         && TREE_ADDRESSABLE (var)
1593         && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
1594       {
1595         TREE_ADDRESSABLE (var) = 0;
1596         if (is_gimple_reg (var))
1597           mark_sym_for_renaming (var);
1598         update_vops = true;
1599         bitmap_set_bit (vars_updated, DECL_UID (var));
1600         if (dump_file)
1601           {
1602             fprintf (dump_file, "No longer having address taken ");
1603             print_generic_expr (dump_file, var, 0);
1604             fprintf (dump_file, "\n");
1605           }
1606       }
1607
1608   /* Operand caches needs to be recomputed for operands referencing the updated
1609      variables.  */
1610   if (update_vops)
1611     FOR_EACH_BB (bb)
1612       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1613         {
1614           tree stmt = bsi_stmt (bsi);
1615
1616           if ((LOADED_SYMS (stmt)
1617                && bitmap_intersect_p (LOADED_SYMS (stmt), vars_updated))
1618               || (STORED_SYMS (stmt)
1619                   && bitmap_intersect_p (STORED_SYMS (stmt), vars_updated)))
1620             update_stmt (stmt);
1621         }
1622   BITMAP_FREE (addresses_taken);
1623   BITMAP_FREE (vars_updated);
1624   return 0;
1625 }
1626
1627 struct gimple_opt_pass pass_update_address_taken =
1628 {
1629  {
1630   GIMPLE_PASS,
1631   "addressables",                       /* name */
1632   NULL,                                 /* gate */
1633   execute_update_addresses_taken,       /* execute */
1634   NULL,                                 /* sub */
1635   NULL,                                 /* next */
1636   0,                                    /* static_pass_number */
1637   0,                                    /* tv_id */
1638   PROP_ssa,                             /* properties_required */
1639   0,                                    /* properties_provided */
1640   0,                                    /* properties_destroyed */
1641   0,                                    /* todo_flags_start */
1642   TODO_update_ssa                       /* todo_flags_finish */
1643  }
1644 };