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   /* Qualifiers on value types do not matter.  */
1075   inner_type = TYPE_MAIN_VARIANT (inner_type);
1076   outer_type = TYPE_MAIN_VARIANT (outer_type);
1077
1078   if (inner_type == outer_type)
1079     return true;
1080
1081   /* If we know the canonical types, compare them.  */
1082   if (TYPE_CANONICAL (inner_type)
1083       && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
1084     return true;
1085
1086   /* Changes in machine mode are never useless conversions.  */
1087   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
1088     return false;
1089
1090   /* If both the inner and outer types are integral types, then the
1091      conversion is not necessary if they have the same mode and
1092      signedness and precision, and both or neither are boolean.  */
1093   if (INTEGRAL_TYPE_P (inner_type)
1094       && INTEGRAL_TYPE_P (outer_type))
1095     {
1096       /* Preserve changes in signedness or precision.  */
1097       if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
1098           || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
1099         return false;
1100
1101       /* Conversions from a non-base to a base type are not useless.
1102          This way we preserve the invariant to do arithmetic in
1103          base types only.  */
1104       if (TREE_TYPE (inner_type)
1105           && TREE_TYPE (inner_type) != inner_type
1106           && (TREE_TYPE (outer_type) == outer_type
1107               || TREE_TYPE (outer_type) == NULL_TREE))
1108         return false;
1109
1110       /* We don't need to preserve changes in the types minimum or
1111          maximum value in general as these do not generate code
1112          unless the types precisions are different.  */
1113
1114       return true;
1115     }
1116
1117   /* Scalar floating point types with the same mode are compatible.  */
1118   else if (SCALAR_FLOAT_TYPE_P (inner_type)
1119            && SCALAR_FLOAT_TYPE_P (outer_type))
1120     return true;
1121
1122   /* We need to take special care recursing to pointed-to types.  */
1123   else if (POINTER_TYPE_P (inner_type)
1124            && POINTER_TYPE_P (outer_type))
1125     {
1126       /* Don't lose casts between pointers to volatile and non-volatile
1127          qualified types.  Doing so would result in changing the semantics
1128          of later accesses.  */
1129       if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
1130            != TYPE_VOLATILE (TREE_TYPE (inner_type)))
1131           && TYPE_VOLATILE (TREE_TYPE (outer_type)))
1132         return false;
1133
1134       /* Do not lose casts between pointers with different
1135          TYPE_REF_CAN_ALIAS_ALL setting or alias sets.  */
1136       if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
1137            != TYPE_REF_CAN_ALIAS_ALL (outer_type))
1138           || (get_alias_set (TREE_TYPE (inner_type))
1139               != get_alias_set (TREE_TYPE (outer_type))))
1140         return false;
1141
1142       /* We do not care for const qualification of the pointed-to types
1143          as const qualification has no semantic value to the middle-end.  */
1144
1145       /* Do not lose casts to restrict qualified pointers.  */
1146       if ((TYPE_RESTRICT (outer_type)
1147            != TYPE_RESTRICT (inner_type))
1148           && TYPE_RESTRICT (outer_type))
1149         return false;
1150
1151       /* Otherwise pointers/references are equivalent if their pointed
1152          to types are effectively the same.  We can strip qualifiers
1153          on pointed-to types for further comparison, which is done in
1154          the callee.  */
1155       return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1156                                           TREE_TYPE (inner_type));
1157     }
1158
1159   /* Recurse for complex types.  */
1160   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
1161            && TREE_CODE (outer_type) == COMPLEX_TYPE)
1162     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1163                                         TREE_TYPE (inner_type));
1164
1165   /* Recurse for vector types with the same number of subparts.  */
1166   else if (TREE_CODE (inner_type) == VECTOR_TYPE
1167            && TREE_CODE (outer_type) == VECTOR_TYPE
1168            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
1169     return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
1170                                         TREE_TYPE (inner_type));
1171
1172   /* For aggregates we may need to fall back to structural equality
1173      checks.  */
1174   else if (AGGREGATE_TYPE_P (inner_type)
1175            && AGGREGATE_TYPE_P (outer_type))
1176     {
1177       /* Different types of aggregates are incompatible.  */
1178       if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
1179         return false;
1180
1181       /* ???  This seems to be necessary even for aggregates that don't
1182          have TYPE_STRUCTURAL_EQUALITY_P set.  */
1183
1184       /* ???  This should eventually just return false.  */
1185       return lang_hooks.types_compatible_p (inner_type, outer_type);
1186     }
1187   /* Also for functions and possibly other types with
1188      TYPE_STRUCTURAL_EQUALITY_P set.  */
1189   else if (TYPE_STRUCTURAL_EQUALITY_P (inner_type)
1190            && TYPE_STRUCTURAL_EQUALITY_P (outer_type))
1191     return lang_hooks.types_compatible_p (inner_type, outer_type);
1192
1193   return false;
1194 }
1195
1196 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
1197    useless type conversion, otherwise return false.
1198
1199    This function implicitly defines the middle-end type system.  With
1200    the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
1201    holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
1202    the following invariants shall be fulfilled:
1203
1204      1) useless_type_conversion_p is transitive.
1205         If a < b and b < c then a < c.
1206
1207      2) useless_type_conversion_p is not symmetric.
1208         From a < b does not follow a > b.
1209
1210      3) Types define the available set of operations applicable to values.
1211         A type conversion is useless if the operations for the target type
1212         is a subset of the operations for the source type.  For example
1213         casts to void* are useless, casts from void* are not (void* can't
1214         be dereferenced or offsetted, but copied, hence its set of operations
1215         is a strict subset of that of all other data pointer types).  Casts
1216         to const T* are useless (can't be written to), casts from const T*
1217         to T* are not.  */
1218
1219 bool
1220 useless_type_conversion_p (tree outer_type, tree inner_type)
1221 {
1222   /* If the outer type is (void *), then the conversion is not
1223      necessary.  We have to make sure to not apply this while
1224      recursing though.  */
1225   if (POINTER_TYPE_P (inner_type)
1226       && POINTER_TYPE_P (outer_type)
1227       && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
1228     return true;
1229
1230   return useless_type_conversion_p_1 (outer_type, inner_type);
1231 }
1232
1233 /* Return true if a conversion from either type of TYPE1 and TYPE2
1234    to the other is not required.  Otherwise return false.  */
1235
1236 bool
1237 types_compatible_p (tree type1, tree type2)
1238 {
1239   return (type1 == type2
1240           || (useless_type_conversion_p (type1, type2)
1241               && useless_type_conversion_p (type2, type1)));
1242 }
1243
1244 /* Return true if EXPR is a useless type conversion, otherwise return
1245    false.  */
1246
1247 bool
1248 tree_ssa_useless_type_conversion (tree expr)
1249 {
1250   /* If we have an assignment that merely uses a NOP_EXPR to change
1251      the top of the RHS to the type of the LHS and the type conversion
1252      is "safe", then strip away the type conversion so that we can
1253      enter LHS = RHS into the const_and_copies table.  */
1254   if (CONVERT_EXPR_P (expr)
1255       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
1256       || TREE_CODE (expr) == NON_LVALUE_EXPR)
1257     return useless_type_conversion_p
1258       (TREE_TYPE (expr),
1259        TREE_TYPE (TREE_OPERAND (expr, 0)));
1260
1261   return false;
1262 }
1263
1264
1265 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
1266    described in walk_use_def_chains.
1267
1268    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
1269       infinite loops.  We used to have a bitmap for this to just mark
1270       SSA versions we had visited.  But non-sparse bitmaps are way too
1271       expensive, while sparse bitmaps may cause quadratic behavior.
1272
1273    IS_DFS is true if the caller wants to perform a depth-first search
1274       when visiting PHI nodes.  A DFS will visit each PHI argument and
1275       call FN after each one.  Otherwise, all the arguments are
1276       visited first and then FN is called with each of the visited
1277       arguments in a separate pass.  */
1278
1279 static bool
1280 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
1281                        struct pointer_set_t *visited, bool is_dfs)
1282 {
1283   gimple def_stmt;
1284
1285   if (pointer_set_insert (visited, var))
1286     return false;
1287
1288   def_stmt = SSA_NAME_DEF_STMT (var);
1289
1290   if (gimple_code (def_stmt) != GIMPLE_PHI)
1291     {
1292       /* If we reached the end of the use-def chain, call FN.  */
1293       return fn (var, def_stmt, data);
1294     }
1295   else
1296     {
1297       size_t i;
1298
1299       /* When doing a breadth-first search, call FN before following the
1300          use-def links for each argument.  */
1301       if (!is_dfs)
1302         for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1303           if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1304             return true;
1305
1306       /* Follow use-def links out of each PHI argument.  */
1307       for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1308         {
1309           tree arg = gimple_phi_arg_def (def_stmt, i);
1310
1311           /* ARG may be NULL for newly introduced PHI nodes.  */
1312           if (arg
1313               && TREE_CODE (arg) == SSA_NAME
1314               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1315             return true;
1316         }
1317
1318       /* When doing a depth-first search, call FN after following the
1319          use-def links for each argument.  */
1320       if (is_dfs)
1321         for (i = 0; i < gimple_phi_num_args (def_stmt); i++)
1322           if (fn (gimple_phi_arg_def (def_stmt, i), def_stmt, data))
1323             return true;
1324     }
1325
1326   return false;
1327 }
1328
1329
1330
1331 /* Walk use-def chains starting at the SSA variable VAR.  Call
1332    function FN at each reaching definition found.  FN takes three
1333    arguments: VAR, its defining statement (DEF_STMT) and a generic
1334    pointer to whatever state information that FN may want to maintain
1335    (DATA).  FN is able to stop the walk by returning true, otherwise
1336    in order to continue the walk, FN should return false.
1337
1338    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1339    different.  The first argument to FN is no longer the original
1340    variable VAR, but the PHI argument currently being examined.  If FN
1341    wants to get at VAR, it should call PHI_RESULT (PHI).
1342
1343    If IS_DFS is true, this function will:
1344
1345         1- walk the use-def chains for all the PHI arguments, and,
1346         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1347
1348    If IS_DFS is false, the two steps above are done in reverse order
1349    (i.e., a breadth-first search).  */
1350
1351 void
1352 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1353                      bool is_dfs)
1354 {
1355   gimple def_stmt;
1356
1357   gcc_assert (TREE_CODE (var) == SSA_NAME);
1358
1359   def_stmt = SSA_NAME_DEF_STMT (var);
1360
1361   /* We only need to recurse if the reaching definition comes from a PHI
1362      node.  */
1363   if (gimple_code (def_stmt) != GIMPLE_PHI)
1364     (*fn) (var, def_stmt, data);
1365   else
1366     {
1367       struct pointer_set_t *visited = pointer_set_create ();
1368       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1369       pointer_set_destroy (visited);
1370     }
1371 }
1372
1373 \f
1374 /* Return true if T, an SSA_NAME, has an undefined value.  */
1375
1376 bool
1377 ssa_undefined_value_p (tree t)
1378 {
1379   tree var = SSA_NAME_VAR (t);
1380
1381   /* Parameters get their initial value from the function entry.  */
1382   if (TREE_CODE (var) == PARM_DECL)
1383     return false;
1384
1385   /* Hard register variables get their initial value from the ether.  */
1386   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1387     return false;
1388
1389   /* The value is undefined iff its definition statement is empty.  */
1390   return gimple_nop_p (SSA_NAME_DEF_STMT (t));
1391 }
1392
1393 /* Emit warnings for uninitialized variables.  This is done in two passes.
1394
1395    The first pass notices real uses of SSA names with undefined values.
1396    Such uses are unconditionally uninitialized, and we can be certain that
1397    such a use is a mistake.  This pass is run before most optimizations,
1398    so that we catch as many as we can.
1399
1400    The second pass follows PHI nodes to find uses that are potentially
1401    uninitialized.  In this case we can't necessarily prove that the use
1402    is really uninitialized.  This pass is run after most optimizations,
1403    so that we thread as many jumps and possible, and delete as much dead
1404    code as possible, in order to reduce false positives.  We also look
1405    again for plain uninitialized variables, since optimization may have
1406    changed conditionally uninitialized to unconditionally uninitialized.  */
1407
1408 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1409    warning text is in MSGID and LOCUS may contain a location or be null.  */
1410
1411 static void
1412 warn_uninit (tree t, const char *gmsgid, void *data)
1413 {
1414   tree var = SSA_NAME_VAR (t);
1415   gimple context = (gimple) data;
1416   location_t location;
1417   expanded_location xloc, floc;
1418
1419   if (!ssa_undefined_value_p (t))
1420     return;
1421
1422   /* TREE_NO_WARNING either means we already warned, or the front end
1423      wishes to suppress the warning.  */
1424   if (TREE_NO_WARNING (var))
1425     return;
1426
1427   /* Do not warn if it can be initialized outside this module.  */
1428   if (is_global_var (var))
1429     return;
1430
1431   location = (context != NULL && gimple_has_location (context))
1432              ? gimple_location (context)
1433              : DECL_SOURCE_LOCATION (var);
1434   xloc = expand_location (location);
1435   floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
1436   if (warning_at (location, OPT_Wuninitialized, gmsgid, var))
1437     {
1438       TREE_NO_WARNING (var) = 1;
1439
1440       if (xloc.file != floc.file
1441           || xloc.line < floc.line
1442           || xloc.line > LOCATION_LINE (cfun->function_end_locus))
1443         inform (input_location, "%J%qD was declared here", var, var);
1444     }
1445 }
1446
1447 struct walk_data {
1448   gimple stmt;
1449   bool always_executed;
1450   bool warn_possibly_uninitialized;
1451 };
1452
1453 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1454    and warn about them.  */
1455
1456 static tree
1457 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
1458 {
1459   struct walk_stmt_info *wi = (struct walk_stmt_info *) data_;
1460   struct walk_data *data = (struct walk_data *) wi->info;
1461   tree t = *tp;
1462
1463   /* We do not care about LHS.  */
1464   if (wi->is_lhs)
1465     return NULL_TREE;
1466
1467   switch (TREE_CODE (t))
1468     {
1469     case ADDR_EXPR:
1470       /* Taking the address of an uninitialized variable does not
1471          count as using it.  */
1472       *walk_subtrees = 0;
1473       break;
1474
1475     case VAR_DECL:
1476       {
1477         /* A VAR_DECL in the RHS of a gimple statement may mean that
1478            this variable is loaded from memory.  */
1479         use_operand_p vuse;
1480         tree op;
1481
1482         /* If there is not gimple stmt,
1483            or alias information has not been computed,
1484            then we cannot check VUSE ops.  */
1485         if (data->stmt == NULL
1486             || !gimple_aliases_computed_p (cfun))
1487           return NULL_TREE;
1488
1489         vuse = SINGLE_SSA_USE_OPERAND (data->stmt, SSA_OP_VUSE);
1490         if (vuse == NULL_USE_OPERAND_P)
1491             return NULL_TREE;
1492
1493         op = USE_FROM_PTR (vuse);
1494         if (t != SSA_NAME_VAR (op)
1495             || !SSA_NAME_IS_DEFAULT_DEF (op))
1496           return NULL_TREE;
1497         /* If this is a VUSE of t and it is the default definition,
1498            then warn about op.  */
1499         t = op;
1500         /* Fall through into SSA_NAME.  */
1501       }
1502
1503     case SSA_NAME:
1504       /* We only do data flow with SSA_NAMEs, so that's all we
1505          can warn about.  */
1506       if (data->always_executed)
1507         warn_uninit (t, "%qD is used uninitialized in this function",
1508                      data->stmt);
1509       else if (data->warn_possibly_uninitialized)
1510         warn_uninit (t, "%qD may be used uninitialized in this function",
1511                      data->stmt);
1512       *walk_subtrees = 0;
1513       break;
1514
1515     case REALPART_EXPR:
1516     case IMAGPART_EXPR:
1517       /* The total store transformation performed during gimplification
1518          creates uninitialized variable uses.  If all is well, these will
1519          be optimized away, so don't warn now.  */
1520       if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
1521         *walk_subtrees = 0;
1522       break;
1523
1524     default:
1525       if (IS_TYPE_OR_DECL_P (t))
1526         *walk_subtrees = 0;
1527       break;
1528     }
1529
1530   return NULL_TREE;
1531 }
1532
1533 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1534    and warn about them.  */
1535
1536 static void
1537 warn_uninitialized_phi (gimple phi)
1538 {
1539   size_t i, n = gimple_phi_num_args (phi);
1540
1541   /* Don't look at memory tags.  */
1542   if (!is_gimple_reg (gimple_phi_result (phi)))
1543     return;
1544
1545   for (i = 0; i < n; ++i)
1546     {
1547       tree op = gimple_phi_arg_def (phi, i);
1548       if (TREE_CODE (op) == SSA_NAME)
1549         warn_uninit (op, "%qD may be used uninitialized in this function",
1550                      NULL);
1551     }
1552 }
1553
1554 static unsigned int
1555 warn_uninitialized_vars (bool warn_possibly_uninitialized)
1556 {
1557   gimple_stmt_iterator gsi;
1558   basic_block bb;
1559   struct walk_data data;
1560
1561   data.warn_possibly_uninitialized = warn_possibly_uninitialized;
1562
1563   calculate_dominance_info (CDI_POST_DOMINATORS);
1564
1565   FOR_EACH_BB (bb)
1566     {
1567       data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
1568                                              single_succ (ENTRY_BLOCK_PTR), bb);
1569       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1570         {
1571           struct walk_stmt_info wi;
1572           data.stmt = gsi_stmt (gsi);
1573           memset (&wi, 0, sizeof (wi));
1574           wi.info = &data;
1575           walk_gimple_op (gsi_stmt (gsi), warn_uninitialized_var, &wi);
1576         }
1577     }
1578   return 0;
1579 }
1580
1581 static unsigned int
1582 execute_early_warn_uninitialized (void)
1583 {
1584   /* Currently, this pass runs always but
1585      execute_late_warn_uninitialized only runs with optimization. With
1586      optimization we want to warn about possible uninitialized as late
1587      as possible, thus don't do it here.  However, without
1588      optimization we need to warn here about "may be uninitialized".
1589   */
1590   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/!optimize);
1591   return 0;
1592 }
1593
1594 static unsigned int
1595 execute_late_warn_uninitialized (void)
1596 {
1597   basic_block bb;
1598   gimple_stmt_iterator gsi;
1599
1600   /* Re-do the plain uninitialized variable check, as optimization may have
1601      straightened control flow.  Do this first so that we don't accidentally
1602      get a "may be" warning when we'd have seen an "is" warning later.  */
1603   warn_uninitialized_vars (/*warn_possibly_uninitialized=*/1);
1604
1605   FOR_EACH_BB (bb)
1606     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1607       warn_uninitialized_phi (gsi_stmt (gsi));
1608
1609   return 0;
1610 }
1611
1612 static bool
1613 gate_warn_uninitialized (void)
1614 {
1615   return warn_uninitialized != 0;
1616 }
1617
1618 struct gimple_opt_pass pass_early_warn_uninitialized =
1619 {
1620  {
1621   GIMPLE_PASS,
1622   NULL,                                 /* name */
1623   gate_warn_uninitialized,              /* gate */
1624   execute_early_warn_uninitialized,     /* execute */
1625   NULL,                                 /* sub */
1626   NULL,                                 /* next */
1627   0,                                    /* static_pass_number */
1628   0,                                    /* tv_id */
1629   PROP_ssa,                             /* properties_required */
1630   0,                                    /* properties_provided */
1631   0,                                    /* properties_destroyed */
1632   0,                                    /* todo_flags_start */
1633   0                                     /* todo_flags_finish */
1634  }
1635 };
1636
1637 struct gimple_opt_pass pass_late_warn_uninitialized =
1638 {
1639  {
1640   GIMPLE_PASS,
1641   NULL,                                 /* name */
1642   gate_warn_uninitialized,              /* gate */
1643   execute_late_warn_uninitialized,      /* execute */
1644   NULL,                                 /* sub */
1645   NULL,                                 /* next */
1646   0,                                    /* static_pass_number */
1647   0,                                    /* tv_id */
1648   PROP_ssa,                             /* properties_required */
1649   0,                                    /* properties_provided */
1650   0,                                    /* properties_destroyed */
1651   0,                                    /* todo_flags_start */
1652   0                                     /* todo_flags_finish */
1653  }
1654 };
1655
1656 /* Compute TREE_ADDRESSABLE for local variables.  */
1657
1658 static unsigned int
1659 execute_update_addresses_taken (void)
1660 {
1661   tree var;
1662   referenced_var_iterator rvi;
1663   gimple_stmt_iterator gsi;
1664   basic_block bb;
1665   bitmap addresses_taken = BITMAP_ALLOC (NULL);
1666   bitmap vars_updated = BITMAP_ALLOC (NULL);
1667   bool update_vops = false;
1668
1669   /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
1670      the function body.  */
1671   FOR_EACH_BB (bb)
1672     {
1673       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1674         {
1675           bitmap taken = gimple_addresses_taken (gsi_stmt (gsi));
1676           if (taken)
1677             bitmap_ior_into (addresses_taken, taken);
1678         }
1679
1680       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1681         {
1682           size_t i;
1683           gimple phi = gsi_stmt (gsi);
1684
1685           for (i = 0; i < gimple_phi_num_args (phi); i++)
1686             {
1687               tree op = PHI_ARG_DEF (phi, i), var;
1688               if (TREE_CODE (op) == ADDR_EXPR
1689                   && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL
1690                   && DECL_P (var))
1691                 bitmap_set_bit (addresses_taken, DECL_UID (var));
1692             }
1693         }
1694     }
1695
1696   /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
1697      SSA.  */
1698   FOR_EACH_REFERENCED_VAR (var, rvi)
1699     if (!is_global_var (var)
1700         && TREE_CODE (var) != RESULT_DECL
1701         && TREE_ADDRESSABLE (var)
1702         && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
1703       {
1704         TREE_ADDRESSABLE (var) = 0;
1705         if (is_gimple_reg (var))
1706           mark_sym_for_renaming (var);
1707         update_vops = true;
1708         bitmap_set_bit (vars_updated, DECL_UID (var));
1709         if (dump_file)
1710           {
1711             fprintf (dump_file, "No longer having address taken ");
1712             print_generic_expr (dump_file, var, 0);
1713             fprintf (dump_file, "\n");
1714           }
1715       }
1716
1717   /* Operand caches needs to be recomputed for operands referencing the updated
1718      variables.  */
1719   if (update_vops)
1720     FOR_EACH_BB (bb)
1721       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1722         {
1723           gimple stmt = gsi_stmt (gsi);
1724
1725           if ((gimple_loaded_syms (stmt)
1726                && bitmap_intersect_p (gimple_loaded_syms (stmt), vars_updated))
1727               || (gimple_stored_syms (stmt)
1728                   && bitmap_intersect_p (gimple_stored_syms (stmt), vars_updated)))
1729             update_stmt (stmt);
1730         }
1731   BITMAP_FREE (addresses_taken);
1732   BITMAP_FREE (vars_updated);
1733   return 0;
1734 }
1735
1736 struct gimple_opt_pass pass_update_address_taken =
1737 {
1738  {
1739   GIMPLE_PASS,
1740   "addressables",                       /* name */
1741   NULL,                                 /* gate */
1742   execute_update_addresses_taken,       /* execute */
1743   NULL,                                 /* sub */
1744   NULL,                                 /* next */
1745   0,                                    /* static_pass_number */
1746   0,                                    /* tv_id */
1747   PROP_ssa,                             /* properties_required */
1748   0,                                    /* properties_provided */
1749   0,                                    /* properties_destroyed */
1750   0,                                    /* todo_flags_start */
1751   TODO_update_ssa                       /* todo_flags_finish */
1752  }
1753 };