gcc/tree-ssa.c

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