gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "langhooks.h"
  31 #include "hard-reg-set.h"
  32 #include "basic-block.h"
  33 #include "output.h"
  34 #include "expr.h"
  35 #include "function.h"
  36 #include "diagnostic.h"
  37 #include "bitmap.h"
  38 #include "pointer-set.h"
  39 #include "tree-flow.h"
  40 #include "tree-gimple.h"
  41 #include "tree-inline.h"
  42 #include "varray.h"
  43 #include "timevar.h"
  44 #include "hashtab.h"
  45 #include "tree-dump.h"
  46 #include "tree-pass.h"
  47 #include "toplev.h"
  48
  49 /* Remove the corresponding arguments from the PHI nodes in E's
  50    destination block and redirect it to DEST.  Return redirected edge.
  51    The list of removed arguments is stored in PENDING_STMT (e).  */
  52
  53 edge
  54 ssa_redirect_edge (edge e, basic_block dest)
  55 {
  56   tree phi;
  57   tree list = NULL, *last = &list;
  58   tree src, dst, node;
  59
  60   /* Remove the appropriate PHI arguments in E's destination block.  */
  61   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
  62     {
  63       if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)
  64         continue;
  65
  66       src = PHI_ARG_DEF (phi, e->dest_idx);
  67       dst = PHI_RESULT (phi);
  68       node = build_tree_list (dst, src);
  69       *last = node;
  70       last = &TREE_CHAIN (node);
  71     }
  72
  73   e = redirect_edge_succ_nodup (e, dest);
  74   PENDING_STMT (e) = list;
  75
  76   return e;
  77 }
  78
  79 /* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
  80    E->dest.  */
  81
  82 void
  83 flush_pending_stmts (edge e)
  84 {
  85   tree phi, arg;
  86
  87   if (!PENDING_STMT (e))
  88     return;
  89
  90   for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
  91        phi;
  92        phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
  93     {
  94       tree def = TREE_VALUE (arg);
  95       add_phi_arg (phi, def, e);
  96     }
  97
  98   PENDING_STMT (e) = NULL;
  99 }
 100
 101 /* Return true if SSA_NAME is malformed and mark it visited.
 102
 103    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
 104       operand.  */
 105
 106 static bool
 107 verify_ssa_name (tree ssa_name, bool is_virtual)
 108 {
 109   if (TREE_CODE (ssa_name) != SSA_NAME)
 110     {
 111       error ("Expected an SSA_NAME object");
 112       return true;
 113     }
 114
 115   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
 116     {
 117       error ("Type mismatch between an SSA_NAME and its symbol.");
 118       return true;
 119     }
 120
 121   if (SSA_NAME_IN_FREE_LIST (ssa_name))
 122     {
 123       error ("Found an SSA_NAME that had been released into the free pool");
 124       return true;
 125     }
 126
 127   if (is_virtual && is_gimple_reg (ssa_name))
 128     {
 129       error ("Found a virtual definition for a GIMPLE register");
 130       return true;
 131     }
 132
 133   if (!is_virtual && !is_gimple_reg (ssa_name))
 134     {
 135       error ("Found a real definition for a non-register");
 136       return true;
 137     }
 138
 139   if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name))
 140       && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL)
 141     {
 142       error ("Found real variable when subvariables should have appeared");
 143       return true;
 144     }
 145
 146   return false;
 147 }
 148
 149
 150 /* Return true if the definition of SSA_NAME at block BB is malformed.
 151
 152    STMT is the statement where SSA_NAME is created.
 153
 154    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
 155       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
 156       it means that the block in that array slot contains the
 157       definition of SSA_NAME.
 158
 159    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 160       V_MUST_DEF.  */
 161
 162 static bool
 163 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 164             tree stmt, bool is_virtual)
 165 {
 166   if (verify_ssa_name (ssa_name, is_virtual))
 167     goto err;
 168
 169   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 170     {
 171       error ("SSA_NAME created in two different blocks %i and %i",
 172              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 173       goto err;
 174     }
 175
 176   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 177
 178   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 179     {
 180       error ("SSA_NAME_DEF_STMT is wrong");
 181       fprintf (stderr, "Expected definition statement:\n");
 182       print_generic_stmt (stderr, SSA_NAME_DEF_STMT (ssa_name), TDF_VOPS);
 183       fprintf (stderr, "\nActual definition statement:\n");
 184       print_generic_stmt (stderr, stmt, TDF_VOPS);
 185       goto err;
 186     }
 187
 188   return false;
 189
 190 err:
 191   fprintf (stderr, "while verifying SSA_NAME ");
 192   print_generic_expr (stderr, ssa_name, 0);
 193   fprintf (stderr, " in statement\n");
 194   print_generic_stmt (stderr, stmt, TDF_VOPS);
 195
 196   return true;
 197 }
 198
 199
 200 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 201    malformed.
 202
 203    DEF_BB is the block where SSA_NAME was found to be created.
 204
 205    IDOM contains immediate dominator information for the flowgraph.
 206
 207    CHECK_ABNORMAL is true if the caller wants to check whether this use
 208       is flowing through an abnormal edge (only used when checking PHI
 209       arguments).
 210
 211    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 212       V_MUST_DEF.
 213
 214    If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
 215      that are defined before STMT in basic block BB.  */
 216
 217 static bool
 218 verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
 219             tree stmt, bool check_abnormal, bool is_virtual,
 220             bitmap names_defined_in_bb)
 221 {
 222   bool err = false;
 223   tree ssa_name = USE_FROM_PTR (use_p);
 224
 225   err = verify_ssa_name (ssa_name, is_virtual);
 226
 227   if (!TREE_VISITED (ssa_name))
 228     if (verify_imm_links (stderr, ssa_name))
 229       err = true;
 230
 231   TREE_VISITED (ssa_name) = 1;
 232
 233   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
 234       && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
 235     ; /* Default definitions have empty statements.  Nothing to do.  */
 236   else if (!def_bb)
 237     {
 238       error ("Missing definition");
 239       err = true;
 240     }
 241   else if (bb != def_bb
 242            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 243     {
 244       error ("Definition in block %i does not dominate use in block %i",
 245              def_bb->index, bb->index);
 246       err = true;
 247     }
 248   else if (bb == def_bb
 249            && names_defined_in_bb != NULL
 250            && !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
 251     {
 252       error ("Definition in block %i follows the use", def_bb->index);
 253       err = true;
 254     }
 255
 256   if (check_abnormal
 257       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 258     {
 259       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 260       err = true;
 261     }
 262
 263   /* Make sure the use is in an appropriate list by checking the previous
 264      element to make sure it's the same.  */
 265   if (use_p->prev == NULL)
 266     {
 267       error ("No immediate_use list");
 268       err = true;
 269     }
 270   else
 271     {
 272       tree listvar ;
 273       if (use_p->prev->use == NULL)
 274         listvar = use_p->prev->stmt;
 275       else
 276         listvar = USE_FROM_PTR (use_p->prev);
 277       if (listvar != ssa_name)
 278         {
 279           error ("Wrong immediate use list");
 280           err = true;
 281         }
 282     }
 283
 284   if (err)
 285     {
 286       fprintf (stderr, "for SSA_NAME: ");
 287       print_generic_expr (stderr, ssa_name, TDF_VOPS);
 288       fprintf (stderr, " in statement:\n");
 289       print_generic_stmt (stderr, stmt, TDF_VOPS);
 290     }
 291
 292   return err;
 293 }
 294
 295
 296 /* Return true if any of the arguments for PHI node PHI at block BB is
 297    malformed.
 298
 299    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 300       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 301       block in that array slot contains the definition of SSA_NAME.  */
 302
 303 static bool
 304 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 305 {
 306   edge e;
 307   bool err = false;
 308   unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
 309
 310   if (EDGE_COUNT (bb->preds) != phi_num_args)
 311     {
 312       error ("Incoming edge count does not match number of PHI arguments\n");
 313       err = true;
 314       goto error;
 315     }
 316
 317   for (i = 0; i < phi_num_args; i++)
 318     {
 319       use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
 320       tree op = USE_FROM_PTR (op_p);
 321
 322
 323       e = EDGE_PRED (bb, i);
 324
 325       if (op == NULL_TREE)
 326         {
 327           error ("PHI argument is missing for edge %d->%d\n",
 328                  e->src->index,
 329                  e->dest->index);
 330           err = true;
 331           goto error;
 332         }
 333
 334       if (TREE_CODE (op) != SSA_NAME && !is_gimple_min_invariant (op))
 335         {
 336           error ("PHI argument is not SSA_NAME, or invariant");
 337           err = true;
 338         }
 339
 340       if (TREE_CODE (op) == SSA_NAME)
 341         err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op_p,
 342                           phi, e->flags & EDGE_ABNORMAL,
 343                           !is_gimple_reg (PHI_RESULT (phi)),
 344                           NULL);
 345
 346       if (e->dest != bb)
 347         {
 348           error ("Wrong edge %d->%d for PHI argument\n",
 349                  e->src->index, e->dest->index, bb->index);
 350           err = true;
 351         }
 352
 353       if (err)
 354         {
 355           fprintf (stderr, "PHI argument\n");
 356           print_generic_stmt (stderr, op, TDF_VOPS);
 357           goto error;
 358         }
 359     }
 360
 361 error:
 362   if (err)
 363     {
 364       fprintf (stderr, "for PHI node\n");
 365       print_generic_stmt (stderr, phi, TDF_VOPS);
 366     }
 367
 368
 369   return err;
 370 }
 371
 372
 373 static void
 374 verify_flow_insensitive_alias_info (void)
 375 {
 376   tree var;
 377   bitmap visited = BITMAP_ALLOC (NULL);
 378   referenced_var_iterator rvi;
 379
 380   FOR_EACH_REFERENCED_VAR (var, rvi)
 381     {
 382       size_t j;
 383       var_ann_t ann;
 384       varray_type may_aliases;
 385
 386       ann = var_ann (var);
 387       may_aliases = ann->may_aliases;
 388
 389       for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
 390         {
 391           tree alias = VARRAY_TREE (may_aliases, j);
 392
 393           bitmap_set_bit (visited, DECL_UID (alias));
 394
 395           if (!may_be_aliased (alias))
 396             {
 397               error ("Non-addressable variable inside an alias set.");
 398               debug_variable (alias);
 399               goto err;
 400             }
 401         }
 402     }
 403
 404   FOR_EACH_REFERENCED_VAR (var, rvi)
 405     {
 406       var_ann_t ann;
 407       ann = var_ann (var);
 408
 409       if (ann->mem_tag_kind == NOT_A_TAG
 410           && ann->is_alias_tag
 411           && !bitmap_bit_p (visited, DECL_UID (var)))
 412         {
 413           error ("Addressable variable that is an alias tag but is not in any alias set.");
 414           goto err;
 415         }
 416     }
 417
 418   BITMAP_FREE (visited);
 419   return;
 420
 421 err:
 422   debug_variable (var);
 423   internal_error ("verify_flow_insensitive_alias_info failed.");
 424 }
 425
 426
 427 static void
 428 verify_flow_sensitive_alias_info (void)
 429 {
 430   size_t i;
 431   tree ptr;
 432
 433   for (i = 1; i < num_ssa_names; i++)
 434     {
 435       tree var;
 436       var_ann_t ann;
 437       struct ptr_info_def *pi;
 438
 439
 440       ptr = ssa_name (i);
 441       if (!ptr)
 442         continue;
 443
 444       /* We only care for pointers that are actually referenced in the
 445          program.  */
 446       if (!POINTER_TYPE_P (TREE_TYPE (ptr)) || !TREE_VISITED (ptr))
 447         continue;
 448
 449       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
 450          is only written-to only once in the return statement.
 451          Otherwise, aggregate RESULT_DECLs may be written-to more than
 452          once in virtual operands.  */
 453       var = SSA_NAME_VAR (ptr);
 454       if (TREE_CODE (var) == RESULT_DECL
 455           && is_gimple_reg (ptr))
 456         continue;
 457
 458       pi = SSA_NAME_PTR_INFO (ptr);
 459       if (pi == NULL)
 460         continue;
 461
 462       ann = var_ann (var);
 463       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
 464         {
 465           error ("Dereferenced pointers should have a name or a type tag");
 466           goto err;
 467         }
 468
 469       if (pi->name_mem_tag
 470           && !pi->pt_malloc
 471           && (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
 472         {
 473           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
 474           goto err;
 475         }
 476
 477       if (pi->value_escapes_p
 478           && pi->name_mem_tag
 479           && !is_call_clobbered (pi->name_mem_tag))
 480         {
 481           error ("Pointer escapes but its name tag is not call-clobbered.");
 482           goto err;
 483         }
 484     }
 485
 486   return;
 487
 488 err:
 489   debug_variable (ptr);
 490   internal_error ("verify_flow_sensitive_alias_info failed.");
 491 }
 492
 493 DEF_VEC_P (bitmap);
 494 DEF_VEC_ALLOC_P (bitmap,heap);
 495
 496 /* Verify that all name tags have different points to sets.
 497    This algorithm takes advantage of the fact that every variable with the
 498    same name tag must have the same points-to set.
 499    So we check a single variable for each name tag, and verify that its
 500    points-to set is different from every other points-to set for other name
 501    tags.
 502
 503    Additionally, given a pointer P_i with name tag NMT and type tag
 504    TMT, this function verified the alias set of TMT is a superset of
 505    the alias set of NMT.  */
 506
 507 static void
 508 verify_name_tags (void)
 509 {
 510   size_t i;
 511   size_t j;
 512   bitmap first, second;
 513   VEC(tree,heap) *name_tag_reps = NULL;
 514   VEC(bitmap,heap) *pt_vars_for_reps = NULL;
 515   bitmap type_aliases = BITMAP_ALLOC (NULL);
 516
 517   /* First we compute the name tag representatives and their points-to sets.  */
 518   for (i = 0; i < num_ssa_names; i++)
 519     {
 520       struct ptr_info_def *pi;
 521       tree tmt, ptr = ssa_name (i);
 522
 523       if (ptr == NULL_TREE)
 524         continue;
 525
 526       pi = SSA_NAME_PTR_INFO (ptr);
 527
 528       if (!TREE_VISITED (ptr)
 529           || !POINTER_TYPE_P (TREE_TYPE (ptr))
 530           || !pi
 531           || !pi->name_mem_tag
 532           || TREE_VISITED (pi->name_mem_tag))
 533         continue;
 534
 535       TREE_VISITED (pi->name_mem_tag) = 1;
 536
 537       if (pi->pt_vars == NULL)
 538         continue;
 539
 540       VEC_safe_push (tree, heap, name_tag_reps, ptr);
 541       VEC_safe_push (bitmap, heap, pt_vars_for_reps, pi->pt_vars);
 542
 543       /* Verify that alias set of PTR's type tag is a superset of the
 544          alias set of PTR's name tag.  */
 545       tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
 546       if (tmt)
 547         {
 548           size_t i;
 549           varray_type aliases = var_ann (tmt)->may_aliases;
 550           bitmap_clear (type_aliases);
 551           for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
 552             {
 553               tree alias = VARRAY_TREE (aliases, i);
 554               bitmap_set_bit (type_aliases, DECL_UID (alias));
 555             }
 556
 557           /* When grouping, we may have added PTR's type tag into the
 558              alias set of PTR's name tag.  To prevent a false
 559              positive, pretend that TMT is in its own alias set.  */
 560           bitmap_set_bit (type_aliases, DECL_UID (tmt));
 561
 562           if (bitmap_equal_p (type_aliases, pi->pt_vars))
 563             continue;
 564
 565           if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
 566             {
 567               error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
 568               debug_variable (tmt);
 569               debug_variable (pi->name_mem_tag);
 570               goto err;
 571             }
 572         }
 573     }
 574
 575   /* Now compare all the representative bitmaps with all other representative
 576      bitmaps, to verify that they are all different.  */
 577   for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
 578     {
 579        for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
 580          {
 581            if (bitmap_equal_p (first, second))
 582              {
 583                error ("Two different pointers with identical points-to sets but different name tags");
 584                debug_variable (VEC_index (tree, name_tag_reps, j));
 585                goto err;
 586              }
 587          }
 588     }
 589
 590   /* Lastly, clear out the visited flags.  */
 591   for (i = 0; i < num_ssa_names; i++)
 592     {
 593       if (ssa_name (i))
 594         {
 595           tree ptr = ssa_name (i);
 596           struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
 597           if (!TREE_VISITED (ptr)
 598               || !POINTER_TYPE_P (TREE_TYPE (ptr))
 599               || !pi
 600               || !pi->name_mem_tag)
 601             continue;
 602           TREE_VISITED (pi->name_mem_tag) = 0;
 603         }
 604     }
 605
 606   /* We do not have to free the bitmaps or trees in the vectors, as
 607      they are not owned by us.  */
 608   VEC_free (bitmap, heap, pt_vars_for_reps);
 609   VEC_free (tree, heap, name_tag_reps);
 610   BITMAP_FREE (type_aliases);
 611   return;
 612
 613 err:
 614   debug_variable (VEC_index (tree, name_tag_reps, i));
 615   internal_error ("verify_name_tags failed");
 616 }
 617
 618
 619 /* Verify the consistency of aliasing information.  */
 620
 621 static void
 622 verify_alias_info (void)
 623 {
 624   verify_flow_sensitive_alias_info ();
 625   verify_name_tags ();
 626   verify_flow_insensitive_alias_info ();
 627 }
 628
 629
 630 /* Verify common invariants in the SSA web.
 631    TODO: verify the variable annotations.  */
 632
 633 void
 634 verify_ssa (bool check_modified_stmt)
 635 {
 636   size_t i;
 637   basic_block bb;
 638   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
 639   ssa_op_iter iter;
 640   tree op;
 641   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
 642   bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
 643
 644   gcc_assert (!need_ssa_update_p ());
 645
 646   verify_stmts ();
 647
 648   timevar_push (TV_TREE_SSA_VERIFY);
 649
 650   /* Keep track of SSA names present in the IL.  */
 651   for (i = 1; i < num_ssa_names; i++)
 652     {
 653       tree name = ssa_name (i);
 654       if (name)
 655         {
 656           tree stmt;
 657           TREE_VISITED (name) = 0;
 658
 659           stmt = SSA_NAME_DEF_STMT (name);
 660           if (!IS_EMPTY_STMT (stmt))
 661             {
 662               basic_block bb = bb_for_stmt (stmt);
 663               verify_def (bb, definition_block,
 664                           name, stmt, !is_gimple_reg (name));
 665
 666             }
 667         }
 668     }
 669
 670   calculate_dominance_info (CDI_DOMINATORS);
 671
 672   /* Now verify all the uses and make sure they agree with the definitions
 673      found in the previous pass.  */
 674   FOR_EACH_BB (bb)
 675     {
 676       edge e;
 677       tree phi;
 678       edge_iterator ei;
 679       block_stmt_iterator bsi;
 680
 681       /* Make sure that all edges have a clear 'aux' field.  */
 682       FOR_EACH_EDGE (e, ei, bb->preds)
 683         {
 684           if (e->aux)
 685             {
 686               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 687                       e->dest->index);
 688               goto err;
 689             }
 690         }
 691
 692       /* Verify the arguments for every PHI node in the block.  */
 693       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 694         {
 695           if (verify_phi_args (phi, bb, definition_block))
 696             goto err;
 697           bitmap_set_bit (names_defined_in_bb,
 698                           SSA_NAME_VERSION (PHI_RESULT (phi)));
 699         }
 700
 701       /* Now verify all the uses and vuses in every statement of the block.  */
 702       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 703         {
 704           tree stmt = bsi_stmt (bsi);
 705           use_operand_p use_p;
 706
 707           if (check_modified_stmt && stmt_modified_p (stmt))
 708             {
 709               error ("Stmt (%p) marked modified after optimization pass : ",
 710                      (void *)stmt);
 711               print_generic_stmt (stderr, stmt, TDF_VOPS);
 712               goto err;
 713             }
 714
 715           if (TREE_CODE (stmt) == MODIFY_EXPR
 716               && TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 717             {
 718               tree lhs, base_address;
 719
 720               lhs = TREE_OPERAND (stmt, 0);
 721               base_address = get_base_address (lhs);
 722
 723               if (base_address
 724                   && SSA_VAR_P (base_address)
 725                   && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF|SSA_OP_VMUSTDEF))
 726                 {
 727                   error ("Statement makes a memory store, but has no "
 728                          "V_MAY_DEFS nor V_MUST_DEFS");
 729                   print_generic_stmt (stderr, stmt, TDF_VOPS);
 730                   goto err;
 731                 }
 732             }
 733
 734
 735           if (stmt_ann (stmt)->makes_aliased_stores
 736               && ZERO_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF))
 737             {
 738               error ("Statement makes aliased stores, but has no V_MAY_DEFS");
 739               print_generic_stmt (stderr, stmt, TDF_VOPS);
 740               goto err;
 741             }
 742
 743           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
 744                                     SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
 745             {
 746               op = USE_FROM_PTR (use_p);
 747               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 748                               use_p, stmt, false, !is_gimple_reg (op),
 749                               names_defined_in_bb))
 750                 goto err;
 751             }
 752
 753           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
 754             bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
 755         }
 756
 757       bitmap_clear (names_defined_in_bb);
 758     }
 759
 760   /* Finally, verify alias information.  */
 761   verify_alias_info ();
 762
 763   free (definition_block);
 764
 765   /* Restore the dominance information to its prior known state, so
 766      that we do not perturb the compiler's subsequent behavior.  */
 767   if (orig_dom_state == DOM_NONE)
 768     free_dominance_info (CDI_DOMINATORS);
 769   else
 770     dom_computed[CDI_DOMINATORS] = orig_dom_state;
 771
 772   BITMAP_FREE (names_defined_in_bb);
 773   timevar_pop (TV_TREE_SSA_VERIFY);
 774   return;
 775
 776 err:
 777   internal_error ("verify_ssa failed.");
 778 }
 779
 780 /* Return true if the uid in both int tree maps are equal.  */
 781
 782 int
 783 int_tree_map_eq (const void *va, const void *vb)
 784 {
 785   const struct int_tree_map  *a = va, *b = vb;
 786   return (a->uid == b->uid);
 787 }
 788
 789 /* Hash a UID in a int_tree_map.  */
 790
 791 unsigned int
 792 int_tree_map_hash (const void *item)
 793 {
 794   return ((const struct int_tree_map *)item)->uid;
 795 }
 796
 797
 798 /* Initialize global DFA and SSA structures.  */
 799
 800 void
 801 init_tree_ssa (void)
 802 {
 803   referenced_vars = htab_create_ggc (20, int_tree_map_hash,
 804                                      int_tree_map_eq, NULL);
 805   call_clobbered_vars = BITMAP_ALLOC (NULL);
 806   addressable_vars = BITMAP_ALLOC (NULL);
 807   init_ssanames ();
 808   init_phinodes ();
 809   global_var = NULL_TREE;
 810   aliases_computed_p = false;
 811 }
 812
 813
 814 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 815
 816 void
 817 delete_tree_ssa (void)
 818 {
 819   size_t i;
 820   basic_block bb;
 821   block_stmt_iterator bsi;
 822   referenced_var_iterator rvi;
 823   tree var;
 824
 825   /* Release any ssa_names still in use.  */
 826   for (i = 0; i < num_ssa_names; i++)
 827     {
 828       tree var = ssa_name (i);
 829       if (var && TREE_CODE (var) == SSA_NAME)
 830         {
 831           SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
 832           SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
 833         }
 834       release_ssa_name (var);
 835     }
 836
 837   /* Remove annotations from every tree in the function.  */
 838   FOR_EACH_BB (bb)
 839     {
 840       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 841         {
 842           tree stmt = bsi_stmt (bsi);
 843           stmt_ann_t ann = get_stmt_ann (stmt);
 844
 845           free_ssa_operands (&ann->operands);
 846           ann->addresses_taken = 0;
 847           mark_stmt_modified (stmt);
 848         }
 849       set_phi_nodes (bb, NULL);
 850     }
 851
 852   /* Remove annotations from every referenced variable.  */
 853   FOR_EACH_REFERENCED_VAR (var, rvi)
 854     {
 855       ggc_free (var->common.ann);
 856       var->common.ann = NULL;
 857     }
 858   htab_delete (referenced_vars);
 859   referenced_vars = NULL;
 860
 861   fini_ssanames ();
 862   fini_phinodes ();
 863
 864   global_var = NULL_TREE;
 865   BITMAP_FREE (call_clobbered_vars);
 866   call_clobbered_vars = NULL;
 867   BITMAP_FREE (addressable_vars);
 868   addressable_vars = NULL;
 869   modified_noreturn_calls = NULL;
 870   aliases_computed_p = false;
 871   gcc_assert (!need_ssa_update_p ());
 872 }
 873
 874
 875 /* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
 876    useless type conversion, otherwise return false.  */
 877
 878 bool
 879 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 880 {
 881   if (inner_type == outer_type)
 882     return true;
 883
 884   /* Changes in machine mode are never useless conversions.  */
 885   if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
 886     return false;
 887
 888   /* If the inner and outer types are effectively the same, then
 889      strip the type conversion and enter the equivalence into
 890      the table.  */
 891   if (lang_hooks.types_compatible_p (inner_type, outer_type))
 892     return true;
 893
 894   /* If both types are pointers and the outer type is a (void *), then
 895      the conversion is not necessary.  The opposite is not true since
 896      that conversion would result in a loss of information if the
 897      equivalence was used.  Consider an indirect function call where
 898      we need to know the exact type of the function to correctly
 899      implement the ABI.  */
 900   else if (POINTER_TYPE_P (inner_type)
 901            && POINTER_TYPE_P (outer_type)
 902            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 903               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 904            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 905     return true;
 906
 907   /* Pointers/references are equivalent if their pointed to types
 908      are effectively the same.  This allows to strip conversions between
 909      pointer types with different type qualifiers.  */
 910   else if (POINTER_TYPE_P (inner_type)
 911            && POINTER_TYPE_P (outer_type)
 912            && TYPE_REF_CAN_ALIAS_ALL (inner_type)
 913               == TYPE_REF_CAN_ALIAS_ALL (outer_type)
 914            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 915                                              TREE_TYPE (outer_type)))
 916     return true;
 917
 918   /* If both the inner and outer types are integral types, then the
 919      conversion is not necessary if they have the same mode and
 920      signedness and precision, and both or neither are boolean.  Some
 921      code assumes an invariant that boolean types stay boolean and do
 922      not become 1-bit bit-field types.  Note that types with precision
 923      not using all bits of the mode (such as bit-field types in C)
 924      mean that testing of precision is necessary.  */
 925   else if (INTEGRAL_TYPE_P (inner_type)
 926            && INTEGRAL_TYPE_P (outer_type)
 927            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 928            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type)
 929            && simple_cst_equal (TYPE_MAX_VALUE (inner_type), TYPE_MAX_VALUE (outer_type))
 930            && simple_cst_equal (TYPE_MIN_VALUE (inner_type), TYPE_MIN_VALUE (outer_type)))
 931     {
 932       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 933       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 934       if (first_boolean == second_boolean)
 935         return true;
 936     }
 937
 938   /* Recurse for complex types.  */
 939   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 940            && TREE_CODE (outer_type) == COMPLEX_TYPE
 941            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 942                                                   TREE_TYPE (inner_type)))
 943     return true;
 944
 945   return false;
 946 }
 947
 948 /* Return true if EXPR is a useless type conversion, otherwise return
 949    false.  */
 950
 951 bool
 952 tree_ssa_useless_type_conversion (tree expr)
 953 {
 954   /* If we have an assignment that merely uses a NOP_EXPR to change
 955      the top of the RHS to the type of the LHS and the type conversion
 956      is "safe", then strip away the type conversion so that we can
 957      enter LHS = RHS into the const_and_copies table.  */
 958   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 959       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 960       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 961     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 962                                                TREE_TYPE (TREE_OPERAND (expr,
 963                                                                         0)));
 964
 965
 966   return false;
 967 }
 968
 969 /* Returns true if statement STMT may read memory.  */
 970
 971 bool
 972 stmt_references_memory_p (tree stmt)
 973 {
 974   stmt_ann_t ann = stmt_ann (stmt);
 975
 976   if (ann->has_volatile_ops)
 977     return true;
 978
 979   return (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS));
 980 }
 981
 982 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 983    described in walk_use_def_chains.
 984
 985    VISITED is a pointer set used to mark visited SSA_NAMEs to avoid
 986       infinite loops.  We used to have a bitmap for this to just mark
 987       SSA versions we had visited.  But non-sparse bitmaps are way too
 988       expensive, while sparse bitmaps may cause quadratic behavior.
 989
 990    IS_DFS is true if the caller wants to perform a depth-first search
 991       when visiting PHI nodes.  A DFS will visit each PHI argument and
 992       call FN after each one.  Otherwise, all the arguments are
 993       visited first and then FN is called with each of the visited
 994       arguments in a separate pass.  */
 995
 996 static bool
 997 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 998                        struct pointer_set_t *visited, bool is_dfs)
 999 {
1000   tree def_stmt;
1001
1002   if (pointer_set_insert (visited, var))
1003     return false;
1004
1005   def_stmt = SSA_NAME_DEF_STMT (var);
1006
1007   if (TREE_CODE (def_stmt) != PHI_NODE)
1008     {
1009       /* If we reached the end of the use-def chain, call FN.  */
1010       return fn (var, def_stmt, data);
1011     }
1012   else
1013     {
1014       int i;
1015
1016       /* When doing a breadth-first search, call FN before following the
1017          use-def links for each argument.  */
1018       if (!is_dfs)
1019         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1020           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1021             return true;
1022
1023       /* Follow use-def links out of each PHI argument.  */
1024       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1025         {
1026           tree arg = PHI_ARG_DEF (def_stmt, i);
1027           if (TREE_CODE (arg) == SSA_NAME
1028               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
1029             return true;
1030         }
1031
1032       /* When doing a depth-first search, call FN after following the
1033          use-def links for each argument.  */
1034       if (is_dfs)
1035         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
1036           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
1037             return true;
1038     }
1039
1040   return false;
1041 }
1042
1043
1044
1045 /* Walk use-def chains starting at the SSA variable VAR.  Call
1046    function FN at each reaching definition found.  FN takes three
1047    arguments: VAR, its defining statement (DEF_STMT) and a generic
1048    pointer to whatever state information that FN may want to maintain
1049    (DATA).  FN is able to stop the walk by returning true, otherwise
1050    in order to continue the walk, FN should return false.
1051
1052    Note, that if DEF_STMT is a PHI node, the semantics are slightly
1053    different.  The first argument to FN is no longer the original
1054    variable VAR, but the PHI argument currently being examined.  If FN
1055    wants to get at VAR, it should call PHI_RESULT (PHI).
1056
1057    If IS_DFS is true, this function will:
1058
1059         1- walk the use-def chains for all the PHI arguments, and,
1060         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
1061
1062    If IS_DFS is false, the two steps above are done in reverse order
1063    (i.e., a breadth-first search).  */
1064
1065
1066 void
1067 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
1068                      bool is_dfs)
1069 {
1070   tree def_stmt;
1071
1072   gcc_assert (TREE_CODE (var) == SSA_NAME);
1073
1074   def_stmt = SSA_NAME_DEF_STMT (var);
1075
1076   /* We only need to recurse if the reaching definition comes from a PHI
1077      node.  */
1078   if (TREE_CODE (def_stmt) != PHI_NODE)
1079     (*fn) (var, def_stmt, data);
1080   else
1081     {
1082       struct pointer_set_t *visited = pointer_set_create ();
1083       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
1084       pointer_set_destroy (visited);
1085     }
1086 }
1087
1088 \f
1089 /* Emit warnings for uninitialized variables.  This is done in two passes.
1090
1091    The first pass notices real uses of SSA names with default definitions.
1092    Such uses are unconditionally uninitialized, and we can be certain that
1093    such a use is a mistake.  This pass is run before most optimizations,
1094    so that we catch as many as we can.
1095
1096    The second pass follows PHI nodes to find uses that are potentially
1097    uninitialized.  In this case we can't necessarily prove that the use
1098    is really uninitialized.  This pass is run after most optimizations,
1099    so that we thread as many jumps and possible, and delete as much dead
1100    code as possible, in order to reduce false positives.  We also look
1101    again for plain uninitialized variables, since optimization may have
1102    changed conditionally uninitialized to unconditionally uninitialized.  */
1103
1104 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1105    warning text is in MSGID and LOCUS may contain a location or be null.  */
1106
1107 static void
1108 warn_uninit (tree t, const char *gmsgid, void *data)
1109 {
1110   tree var = SSA_NAME_VAR (t);
1111   tree def = SSA_NAME_DEF_STMT (t);
1112   tree context = (tree) data;
1113   location_t * locus;
1114
1115   /* Default uses (indicated by an empty definition statement),
1116      are uninitialized.  */
1117   if (!IS_EMPTY_STMT (def))
1118     return;
1119
1120   /* Except for PARMs of course, which are always initialized.  */
1121   if (TREE_CODE (var) == PARM_DECL)
1122     return;
1123
1124   /* Hard register variables get their initial value from the ether.  */
1125   if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
1126     return;
1127
1128   /* TREE_NO_WARNING either means we already warned, or the front end
1129      wishes to suppress the warning.  */
1130   if (TREE_NO_WARNING (var))
1131     return;
1132
1133   locus = (context != NULL && EXPR_HAS_LOCATION (context)
1134            ? EXPR_LOCUS (context)
1135            : &DECL_SOURCE_LOCATION (var));
1136   warning (0, gmsgid, locus, var);
1137   TREE_NO_WARNING (var) = 1;
1138 }
1139
1140 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1141    and warn about them.  */
1142
1143 static tree
1144 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1145 {
1146   tree t = *tp;
1147
1148   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1149   if (TREE_CODE (t) == SSA_NAME)
1150     {
1151       warn_uninit (t, "%H%qD is used uninitialized in this function", data);
1152       *walk_subtrees = 0;
1153     }
1154   else if (IS_TYPE_OR_DECL_P (t))
1155     *walk_subtrees = 0;
1156
1157   return NULL_TREE;
1158 }
1159
1160 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1161    and warn about them.  */
1162
1163 static void
1164 warn_uninitialized_phi (tree phi)
1165 {
1166   int i, n = PHI_NUM_ARGS (phi);
1167
1168   /* Don't look at memory tags.  */
1169   if (!is_gimple_reg (PHI_RESULT (phi)))
1170     return;
1171
1172   for (i = 0; i < n; ++i)
1173     {
1174       tree op = PHI_ARG_DEF (phi, i);
1175       if (TREE_CODE (op) == SSA_NAME)
1176         warn_uninit (op, "%H%qD may be used uninitialized in this function",
1177                      NULL);
1178     }
1179 }
1180
1181 static void
1182 execute_early_warn_uninitialized (void)
1183 {
1184   block_stmt_iterator bsi;
1185   basic_block bb;
1186
1187   FOR_EACH_BB (bb)
1188     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1189       {
1190         tree context = bsi_stmt (bsi);
1191         walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1192                    context, NULL);
1193       }
1194 }
1195
1196 static void
1197 execute_late_warn_uninitialized (void)
1198 {
1199   basic_block bb;
1200   tree phi;
1201
1202   /* Re-do the plain uninitialized variable check, as optimization may have
1203      straightened control flow.  Do this first so that we don't accidentally
1204      get a "may be" warning when we'd have seen an "is" warning later.  */
1205   execute_early_warn_uninitialized ();
1206
1207   FOR_EACH_BB (bb)
1208     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1209       warn_uninitialized_phi (phi);
1210 }
1211
1212 static bool
1213 gate_warn_uninitialized (void)
1214 {
1215   return warn_uninitialized != 0;
1216 }
1217
1218 struct tree_opt_pass pass_early_warn_uninitialized =
1219 {
1220   NULL,                                 /* name */
1221   gate_warn_uninitialized,              /* gate */
1222   execute_early_warn_uninitialized,     /* execute */
1223   NULL,                                 /* sub */
1224   NULL,                                 /* next */
1225   0,                                    /* static_pass_number */
1226   0,                                    /* tv_id */
1227   PROP_ssa,                             /* properties_required */
1228   0,                                    /* properties_provided */
1229   0,                                    /* properties_destroyed */
1230   0,                                    /* todo_flags_start */
1231   0,                                    /* todo_flags_finish */
1232   0                                     /* letter */
1233 };
1234
1235 struct tree_opt_pass pass_late_warn_uninitialized =
1236 {
1237   NULL,                                 /* name */
1238   gate_warn_uninitialized,              /* gate */
1239   execute_late_warn_uninitialized,      /* execute */
1240   NULL,                                 /* sub */
1241   NULL,                                 /* next */
1242   0,                                    /* static_pass_number */
1243   0,                                    /* tv_id */
1244   PROP_ssa,                             /* properties_required */
1245   0,                                    /* properties_provided */
1246   0,                                    /* properties_destroyed */
1247   0,                                    /* todo_flags_start */
1248   0,                                    /* todo_flags_finish */
1249   0                                     /* letter */
1250 };
1251