gcc/tree-ssa.c

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