gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
   3    Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "langhooks.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "expr.h"
  35 #include "function.h"
  36 #include "diagnostic.h"
  37 #include "bitmap.h"
  38 #include "pointer-set.h"
  39 #include "tree-flow.h"
  40 #include "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 (e->dest != bb)
 482         {
 483           error ("wrong edge %d->%d for PHI argument",
 484                  e->src->index, e->dest->index);
 485           err = true;
 486         }
 487
 488       if (err)
 489         {
 490           fprintf (stderr, "PHI argument\n");
 491           print_generic_stmt (stderr, op, TDF_VOPS);
 492           goto error;
 493         }
 494     }
 495
 496 error:
 497   if (err)
 498     {
 499       fprintf (stderr, "for PHI node\n");
 500       print_gimple_stmt (stderr, phi, 0, TDF_VOPS|TDF_MEMSYMS);
 501     }
 502
 503
 504   return err;
 505 }
 506
 507
 508 static void
 509 verify_flow_insensitive_alias_info (void)
 510 {
 511   tree var;
 512   referenced_var_iterator rvi;
 513
 514   FOR_EACH_REFERENCED_VAR (var, rvi)
 515     {
 516       unsigned int j;
 517       bitmap aliases;
 518       tree alias;
 519       bitmap_iterator bi;
 520
 521       if (!MTAG_P (var) || !MTAG_ALIASES (var))
 522         continue;
 523
 524       aliases = MTAG_ALIASES (var);
 525
 526       EXECUTE_IF_SET_IN_BITMAP (aliases, 0, j, bi)
 527         {
 528           alias = referenced_var (j);
 529
 530           if (TREE_CODE (alias) != MEMORY_PARTITION_TAG
 531               && !may_be_aliased (alias))
 532             {
 533               error ("non-addressable variable inside an alias set");
 534               debug_variable (alias);
 535               goto err;
 536             }
 537         }
 538     }
 539
 540   return;
 541
 542 err:
 543   debug_variable (var);
 544   internal_error ("verify_flow_insensitive_alias_info failed");
 545 }
 546
 547
 548 static void
 549 verify_flow_sensitive_alias_info (void)
 550 {
 551   size_t i;
 552   tree ptr;
 553
 554   for (i = 1; i < num_ssa_names; i++)
 555     {
 556       tree var;
 557       var_ann_t ann;
 558       struct ptr_info_def *pi;
 559
 560
 561       ptr = ssa_name (i);
 562       if (!ptr)
 563         continue;
 564
 565       /* We only care for pointers that are actually referenced in the
 566          program.  */
 567       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
 568         continue;
 569
 570       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
 571          is only written-to only once in the return statement.
 572          Otherwise, aggregate RESULT_DECLs may be written-to more than
 573          once in virtual operands.  */
 574       var = SSA_NAME_VAR (ptr);
 575       if (TREE_CODE (var) == RESULT_DECL
 576           && is_gimple_reg (ptr))
 577         continue;
 578
 579       pi = SSA_NAME_PTR_INFO (ptr);
 580       if (pi == NULL)
 581         continue;
 582
 583       ann = var_ann (var);
 584       if (pi->memory_tag_needed && !pi->name_mem_tag && !ann->symbol_mem_tag)
 585         {
 586           error ("dereferenced pointers should have a name or a symbol tag");
 587           goto err;
 588         }
 589
 590       if (pi->name_mem_tag
 591           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
 592         {
 593           error ("pointers with a memory tag, should have points-to sets");
 594           goto err;
 595         }
 596
 597       if (pi->value_escapes_p
 598           && pi->escape_mask & ~ESCAPE_TO_RETURN
 599           && pi->name_mem_tag)
 600         {
 601           tree t = memory_partition (pi->name_mem_tag);
 602           if (t == NULL_TREE)
 603             t = pi->name_mem_tag;
 604
 605           if (!is_call_clobbered (t))
 606             {
 607               error ("pointer escapes but its name tag is not call-clobbered");
 608               goto err;
 609             }
 610         }
 611     }
 612
 613   return;
 614
 615 err:
 616   debug_variable (ptr);
 617   internal_error ("verify_flow_sensitive_alias_info failed");
 618 }
 619
 620
 621 /* Verify the consistency of call clobbering information.  */
 622
 623 static void
 624 verify_call_clobbering (void)
 625 {
 626   unsigned int i;
 627   bitmap_iterator bi;
 628   tree var;
 629   referenced_var_iterator rvi;
 630
 631   /* At all times, the result of the call_clobbered flag should
 632      match the result of the call_clobbered_vars bitmap.  Verify both
 633      that everything in call_clobbered_vars is marked
 634      call_clobbered, and that everything marked
 635      call_clobbered is in call_clobbered_vars.  */
 636   EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
 637     {
 638       var = referenced_var (i);
 639
 640       if (memory_partition (var))
 641         var = memory_partition (var);
 642
 643       if (!MTAG_P (var) && !var_ann (var)->call_clobbered)
 644         {
 645           error ("variable in call_clobbered_vars but not marked "
 646                  "call_clobbered");
 647           debug_variable (var);
 648           goto err;
 649         }
 650     }
 651
 652   FOR_EACH_REFERENCED_VAR (var, rvi)
 653     {
 654       if (is_gimple_reg (var))
 655         continue;
 656
 657       if (memory_partition (var))
 658         var = memory_partition (var);
 659
 660       if (!MTAG_P (var)
 661           && var_ann (var)->call_clobbered
 662           && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
 663         {
 664           error ("variable marked call_clobbered but not in "
 665                  "call_clobbered_vars bitmap.");
 666           debug_variable (var);
 667           goto err;
 668         }
 669     }
 670
 671   return;
 672
 673  err:
 674     internal_error ("verify_call_clobbering failed");
 675 }
 676
 677
 678 /* Verify invariants in memory partitions.  */
 679
 680 static void
 681 verify_memory_partitions (void)
 682 {
 683   unsigned i;
 684   tree mpt;
 685   VEC(tree,heap) *mpt_table = gimple_ssa_operands (cfun)->mpt_table;
 686   struct pointer_set_t *partitioned_syms = pointer_set_create ();
 687
 688   for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
 689     {
 690       unsigned j;
 691       bitmap_iterator bj;
 692
 693       if (MPT_SYMBOLS (mpt) == NULL)
 694         {
 695           error ("Memory partitions should have at least one symbol");
 696           debug_variable (mpt);
 697           goto err;
 698         }
 699
 700       EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt), 0, j, bj)
 701         {
 702           tree var = referenced_var (j);
 703           if (pointer_set_insert (partitioned_syms, var))
 704             {
 705               error ("Partitioned symbols should belong to exactly one "
 706                      "partition");
 707               debug_variable (var);
 708               goto err;
 709             }
 710         }
 711     }
 712
 713   pointer_set_destroy (partitioned_syms);
 714
 715   return;
 716
 717 err:
 718   internal_error ("verify_memory_partitions failed");
 719 }
 720
 721
 722 /* Verify the consistency of aliasing information.  */
 723
 724 static void
 725 verify_alias_info (void)
 726 {
 727   verify_flow_sensitive_alias_info ();
 728   verify_call_clobbering ();
 729   verify_flow_insensitive_alias_info ();
 730   verify_memory_partitions ();
 731 }
 732
 733
 734 /* Verify common invariants in the SSA web.
 735    TODO: verify the variable annotations.  */
 736
 737 void
 738 verify_ssa (bool check_modified_stmt)
 739 {
 740   size_t i;
 741   basic_block bb;
 742   basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
 743   ssa_op_iter iter;
 744   tree op;
 745   enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
 746   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
 747
 748   gcc_assert (!need_ssa_update_p ());
 749
 750   verify_stmts ();
 751
 752   timevar_push (TV_TREE_SSA_VERIFY);
 753
 754   /* Keep track of SSA names present in the IL.  */
 755   for (i = 1; i < num_ssa_names; i++)
 756     {
 757       tree name = ssa_name (i);
 758       if (name)
 759         {
 760           gimple stmt;
 761           TREE_VISITED (name) = 0;
 762
 763           stmt = SSA_NAME_DEF_STMT (name);
 764           if (!gimple_nop_p (stmt))
 765             {
 766               basic_block bb = gimple_bb (stmt);
 767               verify_def (bb, definition_block,
 768                           name, stmt, !is_gimple_reg (name));
 769
 770             }
 771         }
 772     }
 773
 774   calculate_dominance_info (CDI_DOMINATORS);
 775
 776   /* Now verify all the uses and make sure they agree with the definitions
 777      found in the previous pass.  */
 778   FOR_EACH_BB (bb)
 779     {
 780       edge e;
 781       gimple phi;
 782       edge_iterator ei;
 783       gimple_stmt_iterator gsi;
 784
 785       /* Make sure that all edges have a clear 'aux' field.  */
 786       FOR_EACH_EDGE (e, ei, bb->preds)
 787         {
 788           if (e->aux)
 789             {
 790               error ("AUX pointer initialized for edge %d->%d", e->src->index,
 791                       e->dest->index);
 792               goto err;
 793             }
 794         }
 795
 796       /* Verify the arguments for every PHI node in the block.  */
 797       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 798         {
 799           phi = gsi_stmt (gsi);
 800           if (verify_phi_args (phi, bb, definition_block))
 801             goto err;
 802
 803           bitmap_set_bit (names_defined_in_bb,
 804                           SSA_NAME_VERSION (gimple_phi_result (phi)));
 805         }
 806
 807       /* Now verify all the uses and vuses in every statement of the block.  */
 808       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 809         {
 810           gimple stmt = gsi_stmt (gsi);
 811           use_operand_p use_p;
 812
 813           if (check_modified_stmt && gimple_modified_p (stmt))
 814             {
 815               error ("stmt (%p) marked modified after optimization pass: ",
 816                      (void *)stmt);
 817               print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
 818               goto err;
 819             }
 820
 821           if (is_gimple_assign (stmt)
 822               && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
 823             {
 824               tree lhs, base_address;
 825
 826               lhs = gimple_assign_lhs (stmt);
 827               base_address = get_base_address (lhs);
 828
 829               if (base_address
 830                   && gimple_aliases_computed_p (cfun)
 831                   && SSA_VAR_P (base_address)
 832                   && !gimple_has_volatile_ops (stmt)
 833                   && ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
 834                 {
 835                   error ("statement makes a memory store, but has no VDEFS");
 836                   print_gimple_stmt (stderr, stmt, 0, TDF_VOPS);
 837                   goto err;
 838                 }
 839             }
 840
 841           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_VIRTUALS)
 842             {
 843               if (verify_ssa_name (op, true))
 844                 {
 845                   error ("in statement");
 846                   print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
 847                   goto err;
 848                 }
 849             }
 850
 851           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
 852             {
 853               if (verify_ssa_name (op, false))
 854                 {
 855                   error ("in statement");
 856                   print_gimple_stmt (stderr, stmt, 0, TDF_VOPS|TDF_MEMSYMS);
 857                   goto err;
 858                 }
 859             }
 860
 861           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
 862             {
 863               op = USE_FROM_PTR (use_p);
 864               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 865                               use_p, stmt, false, names_defined_in_bb))
 866                 goto err;
 867             }
 868
 869           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 870             bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 871         }
 872
 873       bitmap_clear (names_defined_in_bb);
 874     }
 875
 876   /* Finally, verify alias information.  */
 877   if (gimple_aliases_computed_p (cfun))
 878     verify_alias_info ();
 879
 880   free (definition_block);
 881
 882   /* Restore the dominance information to its prior known state, so
 883      that we do not perturb the compiler's subsequent behavior.  */
 884   if (orig_dom_state == DOM_NONE)
 885     free_dominance_info (CDI_DOMINATORS);
 886   else
 887     set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
 888
 889   BITMAP_FREE (names_defined_in_bb);
 890   timevar_pop (TV_TREE_SSA_VERIFY);
 891   return;
 892
 893 err:
 894   internal_error ("verify_ssa failed");
 895 }
 896
 897 /* Return true if the uid in both int tree maps are equal.  */
 898
 899 int
 900 int_tree_map_eq (const void *va, const void *vb)
 901 {
 902   const struct int_tree_map *a = (const struct int_tree_map *) va;
 903   const struct int_tree_map *b = (const struct int_tree_map *) vb;
 904   return (a->uid == b->uid);
 905 }
 906
 907 /* Hash a UID in a int_tree_map.  */
 908
 909 unsigned int
 910 int_tree_map_hash (const void *item)
 911 {
 912   return ((const struct int_tree_map *)item)->uid;
 913 }
 914
 915 /* Return true if the DECL_UID in both trees are equal.  */
 916
 917 int
 918 uid_decl_map_eq (const void *va, const void *vb)
 919 {
 920   const_tree a = (const_tree) va;
 921   const_tree b = (const_tree) vb;
 922   return (a->decl_minimal.uid == b->decl_minimal.uid);
 923 }
 924
 925 /* Hash a tree in a uid_decl_map.  */
 926
 927 unsigned int
 928 uid_decl_map_hash (const void *item)
 929 {
 930   return ((const_tree)item)->decl_minimal.uid;
 931 }
 932
 933 /* Return true if the DECL_UID in both trees are equal.  */
 934
 935 static int
 936 uid_ssaname_map_eq (const void *va, const void *vb)
 937 {
 938   const_tree a = (const_tree) va;
 939   const_tree b = (const_tree) vb;
 940   return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
 941 }
 942
 943 /* Hash a tree in a uid_decl_map.  */
 944
 945 static unsigned int
 946 uid_ssaname_map_hash (const void *item)
 947 {
 948   return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
 949 }
 950
 951
 952 /* Initialize global DFA and SSA structures.  */
 953
 954 void
 955 init_tree_ssa (struct function *fn)
 956 {
 957   fn->gimple_df = GGC_CNEW (struct gimple_df);
 958   fn->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
 959                                                     uid_decl_map_eq, NULL);
 960   fn->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
 961                                                  uid_ssaname_map_eq, NULL);
 962   fn->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
 963   fn->gimple_df->call_used_vars = BITMAP_GGC_ALLOC ();
 964   fn->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
 965   init_ssanames (fn, 0);
 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   gimple_stmt_iterator gsi;
 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   /* FIXME.  This may not be necessary.  We will release all this
 994      memory en masse in free_ssa_operands.  This clearing used to be
 995      necessary to avoid problems with the inliner, but it may not be
 996      needed anymore.  */
 997   FOR_EACH_BB (bb)
 998     {
 999       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1000         {
1001           gimple stmt = gsi_stmt (gsi);
1002
1003           if (gimple_has_ops (stmt))
1004             {
1005               gimple_set_def_ops (stmt, NULL);
1006               gimple_set_use_ops (stmt, NULL);
1007               gimple_set_addresses_taken (stmt, NULL);
1008             }
1009
1010           if (gimple_has_mem_ops (stmt))
1011             {
1012               gimple_set_vdef_ops (stmt, NULL);
1013               gimple_set_vuse_ops (stmt, NULL);
1014               BITMAP_FREE (stmt->gsmem.membase.stores);
1015               BITMAP_FREE (stmt->gsmem.membase.loads);
1016             }
1017
1018           gimple_set_modified (stmt, true);
1019         }
1020       set_phi_nodes (bb, NULL);
1021     }
1022
1023   /* Remove annotations from every referenced local variable.  */
1024   FOR_EACH_REFERENCED_VAR (var, rvi)
1025     {
1026       if (!MTAG_P (var)
1027           && (TREE_STATIC (var) || DECL_EXTERNAL (var)))
1028         {
1029           var_ann (var)->mpt = NULL_TREE;
1030           var_ann (var)->symbol_mem_tag = NULL_TREE;
1031           continue;
1032         }
1033       if (var->base.ann)
1034         ggc_free (var->base.ann);
1035       var->base.ann = NULL;
1036     }
1037   htab_delete (gimple_referenced_vars (cfun));
1038   cfun->gimple_df->referenced_vars = NULL;
1039
1040   fini_ssanames ();
1041   fini_phinodes ();
1042
1043   /* We no longer maintain the SSA operand cache at this point.  */
1044   if (ssa_operands_active ())
1045     fini_ssa_operands ();
1046
1047   cfun->gimple_df->global_var = NULL_TREE;
1048
1049   htab_delete (cfun->gimple_df->default_defs);
1050   cfun->gimple_df->default_defs = NULL;
1051   cfun->gimple_df->call_clobbered_vars = NULL;
1052   cfun->gimple_df->call_used_vars = NULL;
1053   cfun->gimple_df->addressable_vars = NULL;
1054   cfun->gimple_df->modified_noreturn_calls = NULL;
1055   if (gimple_aliases_computed_p (cfun))
1056     {
1057       delete_alias_heapvars ();
1058       gcc_assert (!need_ssa_update_p ());
1059     }
1060   cfun->gimple_df->aliases_computed_p = false;
1061   delete_mem_ref_stats (cfun);
1062
1063   cfun->gimple_df = NULL;
1064
1065   /* We no longer need the edge variable maps.  */
1066   redirect_edge_var_map_destroy ();
1067 }
1068
1069 /* Helper function for useless_type_conversion_p.  */
1070
1071 static bool
1072 useless_type_conversion_p_1 (tree outer_type, tree inner_type)
1073 {
1074   /* Do the following before stripping toplevel qualifiers.  */
1075   if (POINTER_TYPE_P (inner_type)
1076       && POINTER_TYPE_P (outer_type))
1077     {
1078       /* Do not lose casts to restrict qualified pointers.  */
1079       if ((TYPE_RESTRICT (outer_type)
1080            != TYPE_RESTRICT (inner_type))
1081           && TYPE_RESTRICT (outer_type))
1082         return false;
1083     }
1084
1085   /* From now on qualifiers on value types do not matter.  */
1086   inner_type = TYPE_MAIN_VARIANT (inner_type);
1087   outer_type = TYPE_MAIN_VARIANT (outer_type);
1088
1089   if (inner_type == outer_type)
1090     return true;
1091
1092   /* If we know the canonical types, compare them.  */
1093   if (TYPE_CANONICAL (inner_type)
1094       && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1095     return true;
1096
1097   /* Changes in machine mode are never useless conversions.  */
1098   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1099     return false;
1100
1101   /* If both the inner and outer types are integral types, then the
1102      conversion is not necessary if they have the same mode and
1103      signedness and precision, and both or neither are boolean.  */
1104   if (INTEGRAL_TYPE_P (inner_type)
1105       && INTEGRAL_TYPE_P (outer_type))
1106     {
1107       /* Preserve changes in signedness or precision.  */
1108       if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1109           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1110         return false;
1111
1112       /* Conversions from a non-base to a base type are not useless.
1113          This way we preserve the invariant to do arithmetic in
1114          base types only.  */
1115       if (TREE_TYPE (inner_type)
1116           && TREE_TYPE (inner_type) != inner_type
1117           && (TREE_TYPE (outer_type) == outer_type
1118               || TREE_TYPE (outer_type) == NULL_TREE))
1119         return false;
1120
1121       /* We don't need to preserve changes in the types minimum or
1122          maximum value in general as these do not generate code
1123          unless the types precisions are different.  */
1124
1125       return true;
1126     }
1127
1128   /* Scalar floating point types with the same mode are compatible.  */
1129   else if (SCALAR_FLOAT_TYPE_P (inner_type)
1130            && SCALAR_FLOAT_TYPE_P (outer_type))
1131     return true;
1132
1133   /* We need to take special care recursing to pointed-to types.  */
1134   else if (POINTER_TYPE_P (inner_type)
1135            && POINTER_TYPE_P (outer_type))
1136     {
1137       /* Don't lose casts between pointers to volatile and non-volatile
1138          qualified types.  Doing so would result in changing the semantics
1139          of later accesses.  For function types the volatile qualifier
1140          is used to indicate noreturn functions.  */
1141       if (TREE_CODE (TREE_TYPE (outer_type)) != FUNCTION_TYPE
1142           && TREE_CODE (TREE_TYPE (outer_type)) != METHOD_TYPE
1143           && TREE_CODE (TREE_TYPE (inner_type)) != FUNCTION_TYPE
1144           && TREE_CODE (TREE_TYPE (inner_type)) != METHOD_TYPE
1145           && (TYPE_VOLATILE (TREE_TYPE (outer_type))
1146               != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1147           && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1148         return false;
1149
1150       /* Do not lose casts between pointers with different
1151          TYPE_REF_CAN_ALIAS_ALL setting or alias sets.  */
1152       if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1153            != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1154           || (get_alias_set (TREE_TYPE (inner_type))
1155               != get_alias_set (TREE_TYPE (outer_type))))
1156         return false;
1157
1158       /* We do not care for const qualification of the pointed-to types
1159          as const qualification has no semantic value to the middle-end.  */
1160
1161       /* Otherwise pointers/references are equivalent if their pointed
1162          to types are effectively the same.  We can strip qualifiers
1163          on pointed-to types for further comparison, which is done in
1164          the callee.  */
1165       return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1166                                           TREE_TYPE (inner_type));
1167     }
1168
1169   /* Recurse for complex types.  */
1170   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1171            && TREE_CODE (outer_type) == COMPLEX_TYPE)
1172     return useless_type_conversion_p (TREE_TYPE (outer_type),
1173                                       TREE_TYPE (inner_type));
1174
1175   /* Recurse for vector types with the same number of subparts.  */
1176   else if (TREE_CODE (inner_type) == VECTOR_TYPE
1177            && TREE_CODE (outer_type) == VECTOR_TYPE
1178            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1179     return useless_type_conversion_p (TREE_TYPE (outer_type),
1180                                       TREE_TYPE (inner_type));
1181
1182   /* For aggregates we may need to fall back to structural equality
1183      checks.  */
1184   else if (AGGREGATE_TYPE_P (inner_type)
1185            && AGGREGATE_TYPE_P (outer_type))
1186     {
1187       /* Different types of aggregates are incompatible.  */
1188       if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1189         return false;
1190
1191       /* Conversion from an incomplete to a complete type is never
1192          useless.  */
1193       if (!COMPLETE_TYPE_P (inner_type) && COMPLETE_TYPE_P (outer_type))
1194         return false;
1195
1196       /* ???  This seems to be necessary even for aggregates that don't
1197          have TYPE_STRUCTURAL_EQUALITY_P set.  */
1198
1199       /* ???  This should eventually just return false.  */
1200       return lang_hooks.types_compatible_p (inner_type, outer_type);
1201     }
1202   /* Also for functions and possibly other types with
1203      TYPE_STRUCTURAL_EQUALITY_P set.  */
1204   else if (TYPE_STRUCTURAL_EQUALITY_P (inner_type)
1205            && TYPE_STRUCTURAL_EQUALITY_P (outer_type))
1206     return lang_hooks.types_compatible_p (inner_type, outer_type);
1207
1208   return false;
1209 }
1210
1211 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1212    useless type conversion, otherwise return false.
1213
1214    This function implicitly defines the middle-end type system.  With
1215    the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1216    holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1217    the following invariants shall be fulfilled:
1218
1219      1) useless_type_conversion_p is transitive.
1220         If a < b and b < c then a < c.
1221
1222      2) useless_type_conversion_p is not symmetric.
1223         From a < b does not follow a > b.
1224
1225      3) Types define the available set of operations applicable to values.
1226         A type conversion is useless if the operations for the target type
1227         is a subset of the operations for the source type.  For example
1228         casts to void* are useless, casts from void* are not (void* can't
1229         be dereferenced or offsetted, but copied, hence its set of operations
1230         is a strict subset of that of all other data pointer types).  Casts
1231         to const T* are useless (can't be written to), casts from const T*
1232         to T* are not.  */
1233
1234 bool
1235 useless_type_conversion_p (tree outer_type, tree inner_type)
1236 {
1237   /* If the outer type is (void *), then the conversion is not
1238      necessary.  We have to make sure to not apply this while
1239      recursing though.  */
1240   if (POINTER_TYPE_P (inner_type)
1241       && POINTER_TYPE_P (outer_type)
1242       && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1243     return true;
1244
1245   return useless_type_conversion_p_1 (outer_type, inner_type);
1246 }
1247
1248 /* Return true if a conversion from either type of TYPE1 and TYPE2
1249    to the other is not required.  Otherwise return false.  */
1250
1251 bool
1252 types_compatible_p (tree type1, tree type2)
1253 {
1254   return (type1 == type2
1255           || (useless_type_conversion_p (type1, type2)
1256               && useless_type_conversion_p (type2, type1)));
1257 }
1258
1259 /* Return true if EXPR is a useless type conversion, otherwise return
1260    false.  */
1261
1262 bool
1263 tree_ssa_useless_type_conversion (tree expr)
1264 {
1265   /* If we have an assignment that merely uses a NOP_EXPR to change
1266      the top of the RHS to the type of the LHS and the type conversion
1267      is "safe", then strip away the type conversion so that we can
1268      enter LHS = RHS into the const_and_copies table.  */
1269   if (CONVERT_EXPR_P (expr)
1270       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1271       || TREE_CODE (expr) == NON_LVALUE_EXPR)
1272     return useless_type_conversion_p
1273       (TREE_TYPE (expr),
1274        TREE_TYPE (TREE_OPERAND (expr, 0)));
1275
1276   return false;
1277 }
1278
1279
1280 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
1281    described in walk_use_def_chains.
1282
1283    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1284       infinite loops.  We used to have a bitmap for this to just mark
1285       SSA versions we had visited.  But non-sparse bitmaps are way too
1286       expensive, while sparse bitmaps may cause quadratic behavior.
1287
1288    IS_DFS is true if the caller wants to perform a depth-first search
1289       when visiting PHI nodes.  A DFS will visit each PHI argument and
1290       call FN after each one.  Otherwise, all the arguments are
1291       visited first and then FN is called with each of the visited
1292       arguments in a separate pass.  */
1293
1294 static bool
1295 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1296                        struct pointer_set_t *visited, bool is_dfs)
1297 {
1298   gimple def_stmt;
1299
1300   if (pointer_set_insert (visited, var))
1301     return false;
1302
1303   def_stmt = SSA_NAME_DEF_STMT (var);
1304
1305   if (gimple_code (def_stmt) != GIMPLE_PHI)
1306     {
1307       /* If we reached the end of the use-def chain, call FN.  */
1308       return fn (var, def_stmt, data);
1309     }
1310   else
1311     {
1312       size_t i;
1313
1314       /* When doing a breadth-first search, call FN before following the
1315          use-def links for each argument.  */
1316       if (!is_dfs)
1317         for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1318           if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1319             return true;
1320
1321       /* Follow use-def links out of each PHI argument.  */
1322       for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1323         {
1324           tree arg = gimple_phi_arg_def (def_stmt, i);
1325
1326           /* ARG may be NULL for newly introduced PHI nodes.  */
1327           if (arg
1328               && TREE_CODE (arg) == SSA_NAME
1329               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1330             return true;
1331         }
1332
1333       /* When doing a depth-first search, call FN after following the
1334          use-def links for each argument.  */
1335       if (is_dfs)
1336         for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1337           if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1338             return true;
1339     }
1340
1341   return false;
1342 }
1343
1344
1345
1346 /* Walk use-def chains starting at the SSA variable VAR.  Call
1347    function FN at each reaching definition found.  FN takes three
1348    arguments: VAR, its defining statement (DEF_STMT) and a generic
1349    pointer to whatever state information that FN may want to maintain
1350    (DATA).  FN is able to stop the walk by returning true, otherwise
1351    in order to continue the walk, FN should return false.
1352
1353    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1354    different.  The first argument to FN is no longer the original
1355    variable VAR, but the PHI argument currently being examined.  If FN
1356    wants to get at VAR, it should call PHI_RESULT (PHI).
1357
1358    If IS_DFS is true, this function will:
1359
1360         1- walk the use-def chains for all the PHI arguments, and,
1361         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1362
1363    If IS_DFS is false, the two steps above are done in reverse order
1364    (i.e., a breadth-first search).  */
1365
1366 void
1367 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1368                      bool is_dfs)
1369 {
1370   gimple def_stmt;
1371
1372   gcc_assert (TREE_CODE (var) == SSA_NAME);
1373
1374   def_stmt = SSA_NAME_DEF_STMT (var);
1375
1376   /* We only need to recurse if the reaching definition comes from a PHI
1377      node.  */
1378   if (gimple_code (def_stmt) != GIMPLE_PHI)
1379     (*fn) (var, def_stmt, data);
1380   else
1381     {
1382       struct pointer_set_t *visited = pointer_set_create ();
1383       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1384       pointer_set_destroy (visited);
1385     }
1386 }
1387
1388 \f
1389 /* Return true if T, an SSA_NAME, has an undefined value.  */
1390
1391 bool
1392 ssa_undefined_value_p (tree t)
1393 {
1394   tree var = SSA_NAME_VAR (t);
1395
1396   /* Parameters get their initial value from the function entry.  */
1397   if (TREE_CODE (var) == PARM_DECL)
1398     return false;
1399
1400   /* Hard register variables get their initial value from the ether.  */
1401   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1402     return false;
1403
1404   /* The value is undefined iff its definition statement is empty.  */
1405   return gimple_nop_p (SSA_NAME_DEF_STMT (t));
1406 }
1407
1408 /* Emit warnings for uninitialized variables.  This is done in two passes.
1409
1410    The first pass notices real uses of SSA names with undefined values.
1411    Such uses are unconditionally uninitialized, and we can be certain that
1412    such a use is a mistake.  This pass is run before most optimizations,
1413    so that we catch as many as we can.
1414
1415    The second pass follows PHI nodes to find uses that are potentially
1416    uninitialized.  In this case we can't necessarily prove that the use
1417    is really uninitialized.  This pass is run after most optimizations,
1418    so that we thread as many jumps and possible, and delete as much dead
1419    code as possible, in order to reduce false positives.  We also look
1420    again for plain uninitialized variables, since optimization may have
1421    changed conditionally uninitialized to unconditionally uninitialized.  */
1422
1423 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1424    warning text is in MSGID and LOCUS may contain a location or be null.  */
1425
1426 static void
1427 warn_uninit (tree t, const char *gmsgid, void *data)
1428 {
1429   tree var = SSA_NAME_VAR (t);
1430   gimple context = (gimple) data;
1431   location_t location;
1432   expanded_location xloc, floc;
1433
1434   if (!ssa_undefined_value_p (t))
1435     return;
1436
1437   /* TREE_NO_WARNING either means we already warned, or the front end
1438      wishes to suppress the warning.  */
1439   if (TREE_NO_WARNING (var))
1440     return;
1441
1442   /* Do not warn if it can be initialized outside this module.  */
1443   if (is_global_var (var))
1444     return;
1445
1446   location = (context != NULL && gimple_has_location (context))
1447              ? gimple_location (context)
1448              : DECL_SOURCE_LOCATION (var);
1449   xloc = expand_location (location);
1450   floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1451   if (warning_at (location, OPT_Wuninitialized, gmsgid, var))
1452     {
1453       TREE_NO_WARNING (var) = 1;
1454
1455       if (xloc.file != floc.file
1456           || xloc.line < floc.line
1457           || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1458         inform (input_location, "%J%qD was declared here", var, var);
1459     }
1460 }
1461
1462 struct walk_data {
1463   gimple stmt;
1464   bool always_executed;
1465   bool warn_possibly_uninitialized;
1466 };
1467
1468 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1469    and warn about them.  */
1470
1471 static tree
1472 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1473 {
1474   struct walk_stmt_info *wi = (struct walk_stmt_info *) data_;
1475   struct walk_data *data = (struct walk_data *) wi->info;
1476   tree t = *tp;
1477
1478   /* We do not care about LHS.  */
1479   if (wi->is_lhs)
1480     return NULL_TREE;
1481
1482   switch (TREE_CODE (t))
1483     {
1484     case ADDR_EXPR:
1485       /* Taking the address of an uninitialized variable does not
1486          count as using it.  */
1487       *walk_subtrees = 0;
1488       break;
1489
1490     case VAR_DECL:
1491       {
1492         /* A VAR_DECL in the RHS of a gimple statement may mean that
1493            this variable is loaded from memory.  */
1494         use_operand_p vuse;
1495         tree op;
1496
1497         /* If there is not gimple stmt,
1498            or alias information has not been computed,
1499            then we cannot check VUSE ops.  */
1500         if (data->stmt == NULL
1501             || !gimple_aliases_computed_p (cfun))
1502           return NULL_TREE;
1503
1504         vuse = SINGLE_SSA_USE_OPERAND (data->stmt, SSA_OP_VUSE);
1505         if (vuse == NULL_USE_OPERAND_P)
1506             return NULL_TREE;
1507
1508         op = USE_FROM_PTR (vuse);
1509         if (t != SSA_NAME_VAR (op)
1510             || !SSA_NAME_IS_DEFAULT_DEF (op))
1511           return NULL_TREE;
1512         /* If this is a VUSE of t and it is the default definition,
1513            then warn about op.  */
1514         t = op;
1515         /* Fall through into SSA_NAME.  */
1516       }
1517
1518     case SSA_NAME:
1519       /* We only do data flow with SSA_NAMEs, so that's all we
1520          can warn about.  */
1521       if (data->always_executed)
1522         warn_uninit (t, "%qD is used uninitialized in this function",
1523                      data->stmt);
1524       else if (data->warn_possibly_uninitialized)
1525         warn_uninit (t, "%qD may be used uninitialized in this function",
1526                      data->stmt);
1527       *walk_subtrees = 0;
1528       break;
1529
1530     case REALPART_EXPR:
1531     case IMAGPART_EXPR:
1532       /* The total store transformation performed during gimplification
1533          creates uninitialized variable uses.  If all is well, these will
1534          be optimized away, so don't warn now.  */
1535       if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1536         *walk_subtrees = 0;
1537       break;
1538
1539     default:
1540       if (IS_TYPE_OR_DECL_P (t))
1541         *walk_subtrees = 0;
1542       break;
1543     }
1544
1545   return NULL_TREE;
1546 }
1547
1548 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1549    and warn about them.  */
1550
1551 static void
1552 warn_uninitialized_phi (gimple phi)
1553 {
1554   size_t i, n = gimple_phi_num_args (phi);
1555
1556   /* Don't look at memory tags.  */
1557   if (!is_gimple_reg (gimple_phi_result (phi)))
1558     return;
1559
1560   for (i = 0; i < n; ++i)
1561     {
1562       tree op = gimple_phi_arg_def (phi, i);
1563       if (TREE_CODE (op) == SSA_NAME)
1564         warn_uninit (op, "%qD may be used uninitialized in this function",
1565                      NULL);
1566     }
1567 }
1568
1569 static unsigned int
1570 warn_uninitialized_vars (bool warn_possibly_uninitialized)
1571 {
1572   gimple_stmt_iterator gsi;
1573   basic_block bb;
1574   struct walk_data data;
1575
1576   data.warn_possibly_uninitialized = warn_possibly_uninitialized;
1577
1578   calculate_dominance_info (CDI_POST_DOMINATORS);
1579
1580   FOR_EACH_BB (bb)
1581     {
1582       data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1583                                              single_succ (ENTRY_BLOCK_PTR), bb);
1584       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1585         {
1586           struct walk_stmt_info wi;
1587           data.stmt = gsi_stmt (gsi);
1588           memset (&wi, 0, sizeof (wi));
1589           wi.info = &data;
1590           walk_gimple_op (gsi_stmt (gsi), warn_uninitialized_var, &wi);
1591         }
1592     }
1593   return 0;
1594 }
1595
1596 static unsigned int
1597 execute_early_warn_uninitialized (void)
1598 {
1599   /* Currently, this pass runs always but
1600      execute_late_warn_uninitialized only runs with optimization. With
1601      optimization we want to warn about possible uninitialized as late
1602      as possible, thus don't do it here.  However, without
1603      optimization we need to warn here about "may be uninitialized".
1604   */
1605   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
1606   return 0;
1607 }
1608
1609 static unsigned int
1610 execute_late_warn_uninitialized (void)
1611 {
1612   basic_block bb;
1613   gimple_stmt_iterator gsi;
1614
1615   /* Re-do the plain uninitialized variable check, as optimization may have
1616      straightened control flow.  Do this first so that we don't accidentally
1617      get a "may be" warning when we'd have seen an "is" warning later.  */
1618   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1619
1620   FOR_EACH_BB (bb)
1621     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1622       warn_uninitialized_phi (gsi_stmt (gsi));
1623
1624   return 0;
1625 }
1626
1627 static bool
1628 gate_warn_uninitialized (void)
1629 {
1630   return warn_uninitialized != 0;
1631 }
1632
1633 struct gimple_opt_pass pass_early_warn_uninitialized =
1634 {
1635  {
1636   GIMPLE_PASS,
1637   NULL,                                 /* name */
1638   gate_warn_uninitialized,              /* gate */
1639   execute_early_warn_uninitialized,     /* execute */
1640   NULL,                                 /* sub */
1641   NULL,                                 /* next */
1642   0,                                    /* static_pass_number */
1643   0,                                    /* tv_id */
1644   PROP_ssa,                             /* properties_required */
1645   0,                                    /* properties_provided */
1646   0,                                    /* properties_destroyed */
1647   0,                                    /* todo_flags_start */
1648   0                                     /* todo_flags_finish */
1649  }
1650 };
1651
1652 struct gimple_opt_pass pass_late_warn_uninitialized =
1653 {
1654  {
1655   GIMPLE_PASS,
1656   NULL,                                 /* name */
1657   gate_warn_uninitialized,              /* gate */
1658   execute_late_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 /* Compute TREE_ADDRESSABLE and DECL_GIMPLE_REG_P for local variables.  */
1672
1673 static unsigned int
1674 execute_update_addresses_taken (void)
1675 {
1676   tree var;
1677   referenced_var_iterator rvi;
1678   gimple_stmt_iterator gsi;
1679   basic_block bb;
1680   bitmap addresses_taken = BITMAP_ALLOC (NULL);
1681   bitmap not_reg_needs = BITMAP_ALLOC (NULL);
1682   bitmap vars_updated = BITMAP_ALLOC (NULL);
1683   bool update_vops = false;
1684
1685   /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1686      the function body.  */
1687   FOR_EACH_BB (bb)
1688     {
1689       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1690         {
1691           const_gimple stmt = gsi_stmt (gsi);
1692           enum gimple_code code = gimple_code (stmt);
1693           bitmap taken = gimple_addresses_taken (stmt);
1694
1695           if (taken)
1696             bitmap_ior_into (addresses_taken, taken);
1697
1698           /* If we have a call or an assignment, see if the lhs contains
1699              a local decl that requires not to be a gimple register.  */
1700           if (code == GIMPLE_ASSIGN || code == GIMPLE_CALL)
1701             {
1702               tree lhs = gimple_get_lhs (stmt);
1703               /* A plain decl does not need it set.  */
1704               if (lhs && handled_component_p (lhs))
1705                 {
1706                   var = get_base_address (lhs);
1707                   if (DECL_P (var))
1708                     bitmap_set_bit (not_reg_needs, DECL_UID (var));
1709                 }
1710             }
1711         }
1712
1713       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1714         {
1715           size_t i;
1716           gimple phi = gsi_stmt (gsi);
1717
1718           for (i = 0; i < gimple_phi_num_args (phi); i++)
1719             {
1720               tree op = PHI_ARG_DEF (phi, i), var;
1721               if (TREE_CODE (op) == ADDR_EXPR
1722                   && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL
1723                   && DECL_P (var))
1724                 bitmap_set_bit (addresses_taken, DECL_UID (var));
1725             }
1726         }
1727     }
1728
1729   /* When possible, clear ADDRESSABLE bit or set the REGISTER bit
1730      and mark variable for conversion into SSA.  */
1731   FOR_EACH_REFERENCED_VAR (var, rvi)
1732     {
1733       /* Global Variables, result decls cannot be changed.  */
1734       if (is_global_var (var)
1735           || TREE_CODE (var) == RESULT_DECL
1736           || bitmap_bit_p (addresses_taken, DECL_UID (var)))
1737         continue;
1738
1739       if (TREE_ADDRESSABLE (var))
1740         {
1741           TREE_ADDRESSABLE (var) = 0;
1742           if (is_gimple_reg (var))
1743             mark_sym_for_renaming (var);
1744           update_vops = true;
1745           bitmap_set_bit (vars_updated, DECL_UID (var));
1746           if (dump_file)
1747             {
1748               fprintf (dump_file, "No longer having address taken ");
1749               print_generic_expr (dump_file, var, 0);
1750               fprintf (dump_file, "\n");
1751             }
1752         }
1753       if (!DECL_GIMPLE_REG_P (var)
1754           && !bitmap_bit_p (not_reg_needs, DECL_UID (var))
1755           && (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE
1756               || TREE_CODE (TREE_TYPE (var)) == VECTOR_TYPE))
1757         {
1758           DECL_GIMPLE_REG_P (var) = 1;
1759           mark_sym_for_renaming (var);
1760           update_vops = true;
1761           bitmap_set_bit (vars_updated, DECL_UID (var));
1762           if (dump_file)
1763             {
1764               fprintf (dump_file, "Decl is now a gimple register ");
1765               print_generic_expr (dump_file, var, 0);
1766               fprintf (dump_file, "\n");
1767             }
1768         }
1769       }
1770
1771   /* Operand caches needs to be recomputed for operands referencing the updated
1772      variables.  */
1773   if (update_vops)
1774     FOR_EACH_BB (bb)
1775       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1776         {
1777           gimple stmt = gsi_stmt (gsi);
1778
1779           if ((gimple_loaded_syms (stmt)
1780                && bitmap_intersect_p (gimple_loaded_syms (stmt), vars_updated))
1781               || (gimple_stored_syms (stmt)
1782                   && bitmap_intersect_p (gimple_stored_syms (stmt), vars_updated)))
1783             update_stmt (stmt);
1784         }
1785   BITMAP_FREE (not_reg_needs);
1786   BITMAP_FREE (addresses_taken);
1787   BITMAP_FREE (vars_updated);
1788   return 0;
1789 }
1790
1791 struct gimple_opt_pass pass_update_address_taken =
1792 {
1793  {
1794   GIMPLE_PASS,
1795   "addressables",                       /* name */
1796   NULL,                                 /* gate */
1797   execute_update_addresses_taken,       /* execute */
1798   NULL,                                 /* sub */
1799   NULL,                                 /* next */
1800   0,                                    /* static_pass_number */
1801   0,                                    /* tv_id */
1802   PROP_ssa,                             /* properties_required */
1803   0,                                    /* properties_provided */
1804   0,                                    /* properties_destroyed */
1805   0,                                    /* todo_flags_start */
1806   TODO_update_ssa                       /* todo_flags_finish */
1807  }
1808 };