gcc/tree-ssa.c

   1 /* Miscellaneous SSA utility functions.
   2    Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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 "errors.h"
  35 #include "expr.h"
  36 #include "function.h"
  37 #include "diagnostic.h"
  38 #include "bitmap.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
  48
  49 /* Remove edge E and remove the corresponding arguments from the PHI nodes
  50    in E's destination block.  */
  51
  52 void
  53 ssa_remove_edge (edge e)
  54 {
  55   tree phi, next;
  56
  57   /* Remove the appropriate PHI arguments in E's destination block.  */
  58   for (phi = phi_nodes (e->dest); phi; phi = next)
  59     {
  60       next = PHI_CHAIN (phi);
  61       remove_phi_arg (phi, e->src);
  62     }
  63
  64   remove_edge (e);
  65 }
  66
  67 /* Remove the corresponding arguments from the PHI nodes in E's
  68    destination block and redirect it to DEST.  Return redirected edge.
  69    The list of removed arguments is stored in PENDING_STMT (e).  */
  70
  71 edge
  72 ssa_redirect_edge (edge e, basic_block dest)
  73 {
  74   tree phi, next;
  75   tree list = NULL, *last = &list;
  76   tree src, dst, node;
  77   int i;
  78
  79   /* Remove the appropriate PHI arguments in E's destination block.  */
  80   for (phi = phi_nodes (e->dest); phi; phi = next)
  81     {
  82       next = PHI_CHAIN (phi);
  83
  84       i = phi_arg_from_edge (phi, e);
  85       if (i < 0)
  86         continue;
  87
  88       src = PHI_ARG_DEF (phi, i);
  89       dst = PHI_RESULT (phi);
  90       node = build_tree_list (dst, src);
  91       *last = node;
  92       last = &TREE_CHAIN (node);
  93
  94       remove_phi_arg_num (phi, i);
  95     }
  96
  97   e = redirect_edge_succ_nodup (e, dest);
  98   PENDING_STMT (e) = list;
  99
 100   return e;
 101 }
 102
 103
 104 /* Return true if SSA_NAME is malformed and mark it visited.
 105
 106    IS_VIRTUAL is true if this SSA_NAME was found inside a virtual
 107       operand.  */
 108
 109 static bool
 110 verify_ssa_name (tree ssa_name, bool is_virtual)
 111 {
 112   TREE_VISITED (ssa_name) = 1;
 113
 114   if (TREE_CODE (ssa_name) != SSA_NAME)
 115     {
 116       error ("Expected an SSA_NAME object");
 117       return true;
 118     }
 119
 120   if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
 121     {
 122       error ("Type mismatch between an SSA_NAME and its symbol.");
 123       return true;
 124     }
 125
 126   if (SSA_NAME_IN_FREE_LIST (ssa_name))
 127     {
 128       error ("Found an SSA_NAME that had been released into the free pool");
 129       return true;
 130     }
 131
 132   if (is_virtual && is_gimple_reg (ssa_name))
 133     {
 134       error ("Found a virtual definition for a GIMPLE register");
 135       return true;
 136     }
 137
 138   if (!is_virtual && !is_gimple_reg (ssa_name))
 139     {
 140       error ("Found a real definition for a non-register");
 141       return true;
 142     }
 143
 144   return false;
 145 }
 146
 147
 148 /* Return true if the definition of SSA_NAME at block BB is malformed.
 149
 150    STMT is the statement where SSA_NAME is created.
 151
 152    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
 153       version numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
 154       it means that the block in that array slot contains the
 155       definition of SSA_NAME.
 156
 157    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 158       V_MUST_DEF.  */
 159
 160 static bool
 161 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 162             tree stmt, bool is_virtual)
 163 {
 164   if (verify_ssa_name (ssa_name, is_virtual))
 165     goto err;
 166
 167   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 168     {
 169       error ("SSA_NAME created in two different blocks %i and %i",
 170              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 171       goto err;
 172     }
 173
 174   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 175
 176   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 177     {
 178       error ("SSA_NAME_DEF_STMT is wrong");
 179       fprintf (stderr, "Expected definition statement:\n");
 180       debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name));
 181       fprintf (stderr, "\nActual definition statement:\n");
 182       debug_generic_stmt (stmt);
 183       goto err;
 184     }
 185
 186   return false;
 187
 188 err:
 189   fprintf (stderr, "while verifying SSA_NAME ");
 190   print_generic_expr (stderr, ssa_name, 0);
 191   fprintf (stderr, " in statement\n");
 192   debug_generic_stmt (stmt);
 193
 194   return true;
 195 }
 196
 197
 198 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 199    malformed.
 200
 201    DEF_BB is the block where SSA_NAME was found to be created.
 202
 203    IDOM contains immediate dominator information for the flowgraph.
 204
 205    CHECK_ABNORMAL is true if the caller wants to check whether this use
 206       is flowing through an abnormal edge (only used when checking PHI
 207       arguments).
 208
 209    IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
 210       V_MUST_DEF.  */
 211
 212 static bool
 213 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
 214             tree stmt, bool check_abnormal, bool is_virtual)
 215 {
 216   bool err = false;
 217
 218   err = verify_ssa_name (ssa_name, is_virtual);
 219
 220   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
 221       && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
 222     ; /* Default definitions have empty statements.  Nothing to do.  */
 223   else if (!def_bb)
 224     {
 225       error ("Missing definition");
 226       err = true;
 227     }
 228   else if (bb != def_bb
 229            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 230     {
 231       error ("Definition in block %i does not dominate use in block %i",
 232              def_bb->index, bb->index);
 233       err = true;
 234     }
 235
 236   if (check_abnormal
 237       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 238     {
 239       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 240       err = true;
 241     }
 242
 243   if (err)
 244     {
 245       fprintf (stderr, "for SSA_NAME: ");
 246       debug_generic_expr (ssa_name);
 247       fprintf (stderr, "in statement:\n");
 248       debug_generic_stmt (stmt);
 249     }
 250
 251   return err;
 252 }
 253
 254
 255 /* Return true if any of the arguments for PHI node PHI at block BB is
 256    malformed.
 257
 258    IDOM contains immediate dominator information for the flowgraph.
 259
 260    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 261       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 262       block in that array slot contains the definition of SSA_NAME.  */
 263
 264 static bool
 265 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 266 {
 267   edge e;
 268   bool err = false;
 269   int i, phi_num_args = PHI_NUM_ARGS (phi);
 270
 271   /* Mark all the incoming edges.  */
 272   for (e = bb->pred; e; e = e->pred_next)
 273     e->aux = (void *) 1;
 274
 275   for (i = 0; i < phi_num_args; i++)
 276     {
 277       tree op = PHI_ARG_DEF (phi, i);
 278
 279       e = PHI_ARG_EDGE (phi, i);
 280
 281       if (TREE_CODE (op) == SSA_NAME)
 282         err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
 283                           phi, e->flags & EDGE_ABNORMAL,
 284                           !is_gimple_reg (PHI_RESULT (phi)));
 285
 286       if (e->dest != bb)
 287         {
 288           error ("Wrong edge %d->%d for PHI argument\n",
 289                  e->src->index, e->dest->index, bb->index);
 290           err = true;
 291         }
 292
 293       if (e->aux == (void *) 0)
 294         {
 295           error ("PHI argument flowing through dead edge %d->%d\n",
 296                  e->src->index, e->dest->index);
 297           err = true;
 298         }
 299
 300       if (e->aux == (void *) 2)
 301         {
 302           error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
 303                  e->dest->index);
 304           err = true;
 305         }
 306
 307       if (err)
 308         {
 309           fprintf (stderr, "PHI argument\n");
 310           debug_generic_stmt (op);
 311           goto error;
 312         }
 313
 314       e->aux = (void *) 2;
 315     }
 316
 317   for (e = bb->pred; e; e = e->pred_next)
 318     {
 319       if (e->aux != (void *) 2)
 320         {
 321           error ("No argument flowing through edge %d->%d\n", e->src->index,
 322                  e->dest->index);
 323           err = true;
 324           goto error;
 325         }
 326       e->aux = (void *) 0;
 327     }
 328
 329 error:
 330   if (err)
 331     {
 332       fprintf (stderr, "for PHI node\n");
 333       debug_generic_stmt (phi);
 334     }
 335
 336
 337   return err;
 338 }
 339
 340
 341 static void
 342 verify_flow_insensitive_alias_info (void)
 343 {
 344   size_t i;
 345   tree var;
 346   bitmap visited = BITMAP_XMALLOC ();
 347
 348   for (i = 0; i < num_referenced_vars; i++)
 349     {
 350       size_t j;
 351       var_ann_t ann;
 352       varray_type may_aliases;
 353
 354       var = referenced_var (i);
 355       ann = var_ann (var);
 356       may_aliases = ann->may_aliases;
 357
 358       for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
 359         {
 360           tree alias = VARRAY_TREE (may_aliases, j);
 361
 362           bitmap_set_bit (visited, var_ann (alias)->uid);
 363
 364           if (!may_be_aliased (alias))
 365             {
 366               error ("Non-addressable variable inside an alias set.");
 367               debug_variable (alias);
 368               goto err;
 369             }
 370         }
 371     }
 372
 373   for (i = 0; i < num_referenced_vars; i++)
 374     {
 375       var_ann_t ann;
 376
 377       var = referenced_var (i);
 378       ann = var_ann (var);
 379
 380       if (ann->mem_tag_kind == NOT_A_TAG
 381           && ann->is_alias_tag
 382           && !bitmap_bit_p (visited, ann->uid))
 383         {
 384           error ("Addressable variable that is an alias tag but is not in any alias set.");
 385           goto err;
 386         }
 387     }
 388
 389   BITMAP_XFREE (visited);
 390   return;
 391
 392 err:
 393   debug_variable (var);
 394   internal_error ("verify_flow_insensitive_alias_info failed.");
 395 }
 396
 397
 398 static void
 399 verify_flow_sensitive_alias_info (void)
 400 {
 401   size_t i;
 402   tree ptr;
 403
 404   for (i = 1; i < num_ssa_names; i++)
 405     {
 406       var_ann_t ann;
 407       struct ptr_info_def *pi;
 408
 409       ptr = ssa_name (i);
 410       ann = var_ann (SSA_NAME_VAR (ptr));
 411       pi = SSA_NAME_PTR_INFO (ptr);
 412
 413       /* We only care for pointers that are actually referenced in the
 414          program.  */
 415       if (!TREE_VISITED (ptr) || !POINTER_TYPE_P (TREE_TYPE (ptr)))
 416         continue;
 417
 418       /* RESULT_DECL is special.  If it's a GIMPLE register, then it
 419          is only written-to only once in the return statement.
 420          Otherwise, aggregate RESULT_DECLs may be written-to more than
 421          once in virtual operands.  */
 422       if (TREE_CODE (SSA_NAME_VAR (ptr)) == RESULT_DECL
 423           && is_gimple_reg (ptr))
 424         continue;
 425
 426       if (pi == NULL)
 427         continue;
 428
 429       if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
 430         {
 431           error ("Dereferenced pointers should have a name or a type tag");
 432           goto err;
 433         }
 434
 435       if (pi->name_mem_tag
 436           && !pi->pt_malloc
 437           && (pi->pt_vars == NULL
 438               || bitmap_first_set_bit (pi->pt_vars) < 0))
 439         {
 440           error ("Pointers with a memory tag, should have points-to sets or point to malloc");
 441           goto err;
 442         }
 443
 444       if (pi->value_escapes_p
 445           && pi->name_mem_tag
 446           && !is_call_clobbered (pi->name_mem_tag))
 447         {
 448           error ("Pointer escapes but its name tag is not call-clobbered.");
 449           goto err;
 450         }
 451
 452       if (pi->name_mem_tag && pi->pt_vars)
 453         {
 454           size_t j;
 455
 456           for (j = i + 1; j < num_ssa_names; j++)
 457             {
 458               tree ptr2 = ssa_name (j);
 459               struct ptr_info_def *pi2 = SSA_NAME_PTR_INFO (ptr2);
 460
 461               if (!TREE_VISITED (ptr2) || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
 462                 continue;
 463
 464               if (pi2
 465                   && pi2->name_mem_tag
 466                   && pi2->pt_vars
 467                   && bitmap_first_set_bit (pi2->pt_vars) >= 0
 468                   && pi->name_mem_tag != pi2->name_mem_tag
 469                   && bitmap_equal_p (pi->pt_vars, pi2->pt_vars))
 470                 {
 471                   error ("Two pointers with different name tags and identical points-to sets");
 472                   debug_variable (ptr2);
 473                   goto err;
 474                 }
 475             }
 476         }
 477     }
 478
 479   return;
 480
 481 err:
 482   debug_variable (ptr);
 483   internal_error ("verify_flow_sensitive_alias_info failed.");
 484 }
 485
 486
 487 /* Verify the consistency of aliasing information.  */
 488
 489 static void
 490 verify_alias_info (void)
 491 {
 492   verify_flow_sensitive_alias_info ();
 493   verify_flow_insensitive_alias_info ();
 494 }
 495
 496
 497 /* Verify common invariants in the SSA web.
 498    TODO: verify the variable annotations.  */
 499
 500 void
 501 verify_ssa (void)
 502 {
 503   size_t i;
 504   basic_block bb;
 505   basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
 506   ssa_op_iter iter;
 507   tree op;
 508   enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
 509
 510   timevar_push (TV_TREE_SSA_VERIFY);
 511
 512   /* Keep track of SSA names present in the IL.  */
 513   for (i = 1; i < num_ssa_names; i++)
 514     TREE_VISITED (ssa_name (i)) = 0;
 515
 516   calculate_dominance_info (CDI_DOMINATORS);
 517
 518   /* Verify and register all the SSA_NAME definitions found in the
 519      function.  */
 520   FOR_EACH_BB (bb)
 521     {
 522       tree phi;
 523       block_stmt_iterator bsi;
 524
 525       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 526         if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
 527                         !is_gimple_reg (PHI_RESULT (phi))))
 528           goto err;
 529
 530       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 531         {
 532           tree stmt;
 533
 534           stmt = bsi_stmt (bsi);
 535           get_stmt_operands (stmt);
 536
 537           if (stmt_ann (stmt)->makes_aliased_stores
 538               && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
 539             {
 540               error ("Statement makes aliased stores, but has no V_MAY_DEFS");
 541               debug_generic_stmt (stmt);
 542               goto err;
 543             }
 544
 545           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 546             {
 547               if (verify_def (bb, definition_block, op, stmt, true))
 548                 goto err;
 549             }
 550
 551           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 552             {
 553               if (verify_def (bb, definition_block, op, stmt, false))
 554                 goto err;
 555             }
 556         }
 557     }
 558
 559
 560   /* Now verify all the uses and make sure they agree with the definitions
 561      found in the previous pass.  */
 562   FOR_EACH_BB (bb)
 563     {
 564       edge e;
 565       tree phi;
 566       block_stmt_iterator bsi;
 567
 568       /* Make sure that all edges have a clear 'aux' field.  */
 569       for (e = bb->pred; e; e = e->pred_next)
 570         {
 571           if (e->aux)
 572             {
 573               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 574                       e->dest->index);
 575               goto err;
 576             }
 577         }
 578
 579       /* Verify the arguments for every PHI node in the block.  */
 580       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 581         if (verify_phi_args (phi, bb, definition_block))
 582           goto err;
 583
 584       /* Now verify all the uses and vuses in every statement of the block.  */
 585       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 586         {
 587           tree stmt = bsi_stmt (bsi);
 588
 589           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES)
 590             {
 591               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 592                               op, stmt, false, true))
 593                 goto err;
 594             }
 595
 596           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
 597             {
 598               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 599                               op, stmt, false, false))
 600                 goto err;
 601             }
 602         }
 603     }
 604
 605   /* Finally, verify alias information.  */
 606   verify_alias_info ();
 607
 608   free (definition_block);
 609   /* Restore the dominance infomation to its prior known state, so
 610      that we do not perturb the compiler's subsequent behaviour.  */
 611   if (orig_dom_state == DOM_NONE)
 612     free_dominance_info (CDI_DOMINATORS);
 613   else
 614     dom_computed[CDI_DOMINATORS] = orig_dom_state;
 615
 616   timevar_pop (TV_TREE_SSA_VERIFY);
 617   return;
 618
 619 err:
 620   internal_error ("verify_ssa failed.");
 621 }
 622
 623
 624 /* Initialize global DFA and SSA structures.  */
 625
 626 void
 627 init_tree_ssa (void)
 628 {
 629   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 630   call_clobbered_vars = BITMAP_XMALLOC ();
 631   addressable_vars = BITMAP_XMALLOC ();
 632   init_ssa_operands ();
 633   init_ssanames ();
 634   init_phinodes ();
 635   global_var = NULL_TREE;
 636 }
 637
 638
 639 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 640
 641 void
 642 delete_tree_ssa (void)
 643 {
 644   size_t i;
 645   basic_block bb;
 646   block_stmt_iterator bsi;
 647
 648   /* Remove annotations from every tree in the function.  */
 649   FOR_EACH_BB (bb)
 650     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 651       {
 652         tree stmt = bsi_stmt (bsi);
 653         release_defs (stmt);
 654         ggc_free (stmt->common.ann);
 655         stmt->common.ann = NULL;
 656       }
 657
 658   /* Remove annotations from every referenced variable.  */
 659   if (referenced_vars)
 660     {
 661       for (i = 0; i < num_referenced_vars; i++)
 662         {
 663           tree var = referenced_var (i);
 664           ggc_free (var->common.ann);
 665           var->common.ann = NULL;
 666         }
 667       referenced_vars = NULL;
 668     }
 669
 670   fini_ssanames ();
 671   fini_phinodes ();
 672   fini_ssa_operands ();
 673
 674   global_var = NULL_TREE;
 675   BITMAP_XFREE (call_clobbered_vars);
 676   call_clobbered_vars = NULL;
 677   BITMAP_XFREE (addressable_vars);
 678   addressable_vars = NULL;
 679 }
 680
 681
 682 /* Return true if EXPR is a useless type conversion, otherwise return
 683    false.  */
 684
 685 bool
 686 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 687 {
 688   /* If the inner and outer types are effectively the same, then
 689      strip the type conversion and enter the equivalence into
 690      the table.  */
 691   if (inner_type == outer_type
 692      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 693     return true;
 694
 695   /* If both types are pointers and the outer type is a (void *), then
 696      the conversion is not necessary.  The opposite is not true since
 697      that conversion would result in a loss of information if the
 698      equivalence was used.  Consider an indirect function call where
 699      we need to know the exact type of the function to correctly
 700      implement the ABI.  */
 701   else if (POINTER_TYPE_P (inner_type)
 702            && POINTER_TYPE_P (outer_type)
 703            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 704     return true;
 705
 706   /* Pointers and references are equivalent once we get to GENERIC,
 707      so strip conversions that just switch between them.  */
 708   else if (POINTER_TYPE_P (inner_type)
 709            && POINTER_TYPE_P (outer_type)
 710            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 711                                              TREE_TYPE (outer_type)))
 712     return true;
 713
 714   /* If both the inner and outer types are integral types, then the
 715      conversion is not necessary if they have the same mode and
 716      signedness and precision, and both or neither are boolean.  Some
 717      code assumes an invariant that boolean types stay boolean and do
 718      not become 1-bit bit-field types.  Note that types with precision
 719      not using all bits of the mode (such as bit-field types in C)
 720      mean that testing of precision is necessary.  */
 721   else if (INTEGRAL_TYPE_P (inner_type)
 722            && INTEGRAL_TYPE_P (outer_type)
 723            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 724            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 725            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 726     {
 727       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 728       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 729       if (first_boolean == second_boolean)
 730         return true;
 731     }
 732
 733   /* Recurse for complex types.  */
 734   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 735            && TREE_CODE (outer_type) == COMPLEX_TYPE
 736            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 737                                                   TREE_TYPE (inner_type)))
 738     return true;
 739
 740   return false;
 741 }
 742
 743 /* Return true if EXPR is a useless type conversion, otherwise return
 744    false.  */
 745
 746 bool
 747 tree_ssa_useless_type_conversion (tree expr)
 748 {
 749   /* If we have an assignment that merely uses a NOP_EXPR to change
 750      the top of the RHS to the type of the LHS and the type conversion
 751      is "safe", then strip away the type conversion so that we can
 752      enter LHS = RHS into the const_and_copies table.  */
 753   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 754       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 755       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 756     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 757                                                TREE_TYPE (TREE_OPERAND (expr,
 758                                                                         0)));
 759
 760
 761   return false;
 762 }
 763
 764
 765 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 766    described in walk_use_def_chains.
 767
 768    VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
 769       infinite loops.
 770
 771    IS_DFS is true if the caller wants to perform a depth-first search
 772       when visiting PHI nodes.  A DFS will visit each PHI argument and
 773       call FN after each one.  Otherwise, all the arguments are
 774       visited first and then FN is called with each of the visited
 775       arguments in a separate pass.  */
 776
 777 static bool
 778 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 779                        bitmap visited, bool is_dfs)
 780 {
 781   tree def_stmt;
 782
 783   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 784     return false;
 785
 786   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 787
 788   def_stmt = SSA_NAME_DEF_STMT (var);
 789
 790   if (TREE_CODE (def_stmt) != PHI_NODE)
 791     {
 792       /* If we reached the end of the use-def chain, call FN.  */
 793       return fn (var, def_stmt, data);
 794     }
 795   else
 796     {
 797       int i;
 798
 799       /* When doing a breadth-first search, call FN before following the
 800          use-def links for each argument.  */
 801       if (!is_dfs)
 802         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 803           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 804             return true;
 805
 806       /* Follow use-def links out of each PHI argument.  */
 807       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 808         {
 809           tree arg = PHI_ARG_DEF (def_stmt, i);
 810           if (TREE_CODE (arg) == SSA_NAME
 811               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
 812             return true;
 813         }
 814
 815       /* When doing a depth-first search, call FN after following the
 816          use-def links for each argument.  */
 817       if (is_dfs)
 818         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 819           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 820             return true;
 821     }
 822
 823   return false;
 824 }
 825
 826
 827
 828 /* Walk use-def chains starting at the SSA variable VAR.  Call
 829    function FN at each reaching definition found.  FN takes three
 830    arguments: VAR, its defining statement (DEF_STMT) and a generic
 831    pointer to whatever state information that FN may want to maintain
 832    (DATA).  FN is able to stop the walk by returning true, otherwise
 833    in order to continue the walk, FN should return false.
 834
 835    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 836    different.  The first argument to FN is no longer the original
 837    variable VAR, but the PHI argument currently being examined.  If FN
 838    wants to get at VAR, it should call PHI_RESULT (PHI).
 839
 840    If IS_DFS is true, this function will:
 841
 842         1- walk the use-def chains for all the PHI arguments, and,
 843         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
 844
 845    If IS_DFS is false, the two steps above are done in reverse order
 846    (i.e., a breadth-first search).  */
 847
 848
 849 void
 850 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
 851                      bool is_dfs)
 852 {
 853   tree def_stmt;
 854
 855   gcc_assert (TREE_CODE (var) == SSA_NAME);
 856
 857   def_stmt = SSA_NAME_DEF_STMT (var);
 858
 859   /* We only need to recurse if the reaching definition comes from a PHI
 860      node.  */
 861   if (TREE_CODE (def_stmt) != PHI_NODE)
 862     (*fn) (var, def_stmt, data);
 863   else
 864     {
 865       bitmap visited = BITMAP_XMALLOC ();
 866       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
 867       BITMAP_XFREE (visited);
 868     }
 869 }
 870
 871
 872 /* Replaces VAR with REPL in memory reference expression *X in
 873    statement STMT.  */
 874
 875 static void
 876 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 877 {
 878   tree new_var, ass_stmt, addr_var;
 879   basic_block bb;
 880   block_stmt_iterator bsi;
 881
 882   /* There is nothing special to handle in the other cases.  */
 883   if (TREE_CODE (repl) != ADDR_EXPR)
 884     return;
 885   addr_var = TREE_OPERAND (repl, 0);
 886
 887   while (handled_component_p (*x)
 888          || TREE_CODE (*x) == REALPART_EXPR
 889          || TREE_CODE (*x) == IMAGPART_EXPR)
 890     x = &TREE_OPERAND (*x, 0);
 891
 892   if (TREE_CODE (*x) != INDIRECT_REF
 893       || TREE_OPERAND (*x, 0) != var)
 894     return;
 895
 896   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 897     {
 898       *x = addr_var;
 899       mark_new_vars_to_rename (stmt, vars_to_rename);
 900       return;
 901     }
 902
 903
 904   /* Frontends sometimes produce expressions like *&a instead of a[0].
 905      Create a temporary variable to handle this case.  */
 906   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 907   new_var = duplicate_ssa_name (var, ass_stmt);
 908   TREE_OPERAND (*x, 0) = new_var;
 909   TREE_OPERAND (ass_stmt, 0) = new_var;
 910
 911   bb = bb_for_stmt (stmt);
 912   tree_block_label (bb);
 913   bsi = bsi_after_labels (bb);
 914   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 915
 916   mark_new_vars_to_rename (stmt, vars_to_rename);
 917 }
 918
 919 /* Replaces immediate uses of VAR by REPL.  */
 920
 921 static void
 922 replace_immediate_uses (tree var, tree repl)
 923 {
 924   int i, j, n;
 925   dataflow_t df;
 926   tree stmt;
 927   bool mark_new_vars;
 928   ssa_op_iter iter;
 929   use_operand_p use_p;
 930
 931   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 932   n = num_immediate_uses (df);
 933
 934   for (i = 0; i < n; i++)
 935     {
 936       stmt = immediate_use (df, i);
 937
 938       if (TREE_CODE (stmt) == PHI_NODE)
 939         {
 940           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 941             if (PHI_ARG_DEF (stmt, j) == var)
 942               {
 943                 SET_PHI_ARG_DEF (stmt, j, repl);
 944                 if (TREE_CODE (repl) == SSA_NAME
 945                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 946                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 947               }
 948
 949           continue;
 950         }
 951
 952       get_stmt_operands (stmt);
 953       mark_new_vars = false;
 954       if (is_gimple_reg (SSA_NAME_VAR (var)))
 955         {
 956           if (TREE_CODE (stmt) == MODIFY_EXPR)
 957             {
 958               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
 959               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
 960             }
 961
 962           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 963             if (USE_FROM_PTR (use_p) == var)
 964               {
 965                 propagate_value (use_p, repl);
 966                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
 967               }
 968         }
 969       else
 970         {
 971           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
 972             if (USE_FROM_PTR (use_p) == var)
 973               propagate_value (use_p, repl);
 974         }
 975
 976       /* If REPL is a pointer, it may have different memory tags associated
 977          with it.  For instance, VAR may have had a name tag while REPL
 978          only had a type tag.  In these cases, the virtual operands (if
 979          any) in the statement will refer to different symbols which need
 980          to be renamed.  */
 981       if (mark_new_vars)
 982         mark_new_vars_to_rename (stmt, vars_to_rename);
 983       else
 984         modify_stmt (stmt);
 985     }
 986 }
 987
 988 /* Gets the value VAR is equivalent to according to EQ_TO.  */
 989
 990 static tree
 991 get_eq_name (tree *eq_to, tree var)
 992 {
 993   unsigned ver;
 994   tree val = var;
 995
 996   while (TREE_CODE (val) == SSA_NAME)
 997     {
 998       ver = SSA_NAME_VERSION (val);
 999       if (!eq_to[ver])
1000         break;
1001
1002       val = eq_to[ver];
1003     }
1004
1005   while (TREE_CODE (var) == SSA_NAME)
1006     {
1007       ver = SSA_NAME_VERSION (var);
1008       if (!eq_to[ver])
1009         break;
1010
1011       var = eq_to[ver];
1012       eq_to[ver] = val;
1013     }
1014
1015   return val;
1016 }
1017
1018 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1019    its result is redundant to to EQ_TO array.  */
1020
1021 static void
1022 check_phi_redundancy (tree phi, tree *eq_to)
1023 {
1024   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1025   unsigned i, ver = SSA_NAME_VERSION (res), n;
1026   dataflow_t df;
1027
1028   /* It is unlikely that such large phi node would be redundant.  */
1029   if (PHI_NUM_ARGS (phi) > 16)
1030     return;
1031
1032   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1033     {
1034       def = PHI_ARG_DEF (phi, i);
1035
1036       if (TREE_CODE (def) == SSA_NAME)
1037         {
1038           def = get_eq_name (eq_to, def);
1039           if (def == res)
1040             continue;
1041         }
1042
1043       if (val
1044           && !operand_equal_p (val, def, 0))
1045         return;
1046
1047       val = def;
1048     }
1049
1050   /* At least one of the arguments should not be equal to the result, or
1051      something strange is happening.  */
1052   gcc_assert (val);
1053
1054   if (get_eq_name (eq_to, res) == val)
1055     return;
1056
1057   if (!may_propagate_copy (res, val))
1058     return;
1059
1060   eq_to[ver] = val;
1061
1062   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1063   n = num_immediate_uses (df);
1064
1065   for (i = 0; i < n; i++)
1066     {
1067       stmt = immediate_use (df, i);
1068
1069       if (TREE_CODE (stmt) == PHI_NODE)
1070         check_phi_redundancy (stmt, eq_to);
1071     }
1072 }
1073
1074 /* Removes redundant phi nodes.
1075
1076    A redundant PHI node is a PHI node where all of its PHI arguments
1077    are the same value, excluding any PHI arguments which are the same
1078    as the PHI result.
1079
1080    A redundant PHI node is effectively a copy, so we forward copy propagate
1081    which removes all uses of the destination of the PHI node then
1082    finally we delete the redundant PHI node.
1083
1084    Note that if we can not copy propagate the PHI node, then the PHI
1085    will not be removed.  Thus we do not have to worry about dependencies
1086    between PHIs and the problems serializing PHIs into copies creates.
1087
1088    The most important effect of this pass is to remove degenerate PHI
1089    nodes created by removing unreachable code.  */
1090
1091 void
1092 kill_redundant_phi_nodes (void)
1093 {
1094   tree *eq_to;
1095   unsigned i, old_num_ssa_names;
1096   basic_block bb;
1097   tree phi, var, repl, stmt;
1098
1099   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1100      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
1101      other value, it may be necessary to follow the chain till the final value.
1102      We perform path shortening (replacing the entries of the EQ_TO array with
1103      heads of these chains) whenever we access the field to prevent quadratic
1104      complexity (probably would not occur in practice anyway, but let us play
1105      it safe).  */
1106   eq_to = xcalloc (num_ssa_names, sizeof (tree));
1107
1108   /* We have had cases where computing immediate uses takes a
1109      significant amount of compile time.  If we run into such
1110      problems here, we may want to only compute immediate uses for
1111      a subset of all the SSA_NAMEs instead of computing it for
1112      all of the SSA_NAMEs.  */
1113   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1114   old_num_ssa_names = num_ssa_names;
1115
1116   FOR_EACH_BB (bb)
1117     {
1118       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1119         {
1120           var = PHI_RESULT (phi);
1121           check_phi_redundancy (phi, eq_to);
1122         }
1123     }
1124
1125   /* Now propagate the values.  */
1126   for (i = 0; i < old_num_ssa_names; i++)
1127     {
1128       if (!ssa_name (i))
1129         continue;
1130
1131       repl = get_eq_name (eq_to, ssa_name (i));
1132       if (repl != ssa_name (i))
1133         replace_immediate_uses (ssa_name (i), repl);
1134     }
1135
1136   /* And remove the dead phis.  */
1137   for (i = 0; i < old_num_ssa_names; i++)
1138     {
1139       if (!ssa_name (i))
1140         continue;
1141
1142       repl = get_eq_name (eq_to, ssa_name (i));
1143       if (repl != ssa_name (i))
1144         {
1145           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1146           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1147         }
1148     }
1149
1150   free_df ();
1151   free (eq_to);
1152 }
1153
1154 struct tree_opt_pass pass_redundant_phi =
1155 {
1156   "redphi",                             /* name */
1157   NULL,                                 /* gate */
1158   kill_redundant_phi_nodes,             /* execute */
1159   NULL,                                 /* sub */
1160   NULL,                                 /* next */
1161   0,                                    /* static_pass_number */
1162   0,                                    /* tv_id */
1163   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1164   0,                                    /* properties_provided */
1165   0,                                    /* properties_destroyed */
1166   0,                                    /* todo_flags_start */
1167   TODO_dump_func | TODO_rename_vars
1168     | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1169   0                                     /* letter */
1170 };
1171 \f
1172 /* Emit warnings for uninitialized variables.  This is done in two passes.
1173
1174    The first pass notices real uses of SSA names with default definitions.
1175    Such uses are unconditionally uninitialized, and we can be certain that
1176    such a use is a mistake.  This pass is run before most optimizations,
1177    so that we catch as many as we can.
1178
1179    The second pass follows PHI nodes to find uses that are potentially
1180    uninitialized.  In this case we can't necessarily prove that the use
1181    is really uninitialized.  This pass is run after most optimizations,
1182    so that we thread as many jumps and possible, and delete as much dead
1183    code as possible, in order to reduce false positives.  We also look
1184    again for plain uninitialized variables, since optimization may have
1185    changed conditionally uninitialized to unconditionally uninitialized.  */
1186
1187 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1188    warning text is in MSGID and LOCUS may contain a location or be null.  */
1189
1190 static void
1191 warn_uninit (tree t, const char *msgid, location_t *locus)
1192 {
1193   tree var = SSA_NAME_VAR (t);
1194   tree def = SSA_NAME_DEF_STMT (t);
1195
1196   /* Default uses (indicated by an empty definition statement),
1197      are uninitialized.  */
1198   if (!IS_EMPTY_STMT (def))
1199     return;
1200
1201   /* Except for PARMs of course, which are always initialized.  */
1202   if (TREE_CODE (var) == PARM_DECL)
1203     return;
1204
1205   /* Hard register variables get their initial value from the ether.  */
1206   if (DECL_HARD_REGISTER (var))
1207     return;
1208
1209   /* TREE_NO_WARNING either means we already warned, or the front end
1210      wishes to suppress the warning.  */
1211   if (TREE_NO_WARNING (var))
1212     return;
1213
1214   if (!locus)
1215     locus = &DECL_SOURCE_LOCATION (var);
1216   warning (msgid, locus, var);
1217   TREE_NO_WARNING (var) = 1;
1218 }
1219
1220 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1221    and warn about them.  */
1222
1223 static tree
1224 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1225 {
1226   location_t *locus = data;
1227   tree t = *tp;
1228
1229   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1230   if (TREE_CODE (t) == SSA_NAME)
1231     {
1232       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1233       *walk_subtrees = 0;
1234     }
1235   else if (DECL_P (t) || TYPE_P (t))
1236     *walk_subtrees = 0;
1237
1238   return NULL_TREE;
1239 }
1240
1241 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1242    and warn about them.  */
1243
1244 static void
1245 warn_uninitialized_phi (tree phi)
1246 {
1247   int i, n = PHI_NUM_ARGS (phi);
1248
1249   /* Don't look at memory tags.  */
1250   if (!is_gimple_reg (PHI_RESULT (phi)))
1251     return;
1252
1253   for (i = 0; i < n; ++i)
1254     {
1255       tree op = PHI_ARG_DEF (phi, i);
1256       if (TREE_CODE (op) == SSA_NAME)
1257         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1258                      NULL);
1259     }
1260 }
1261
1262 static void
1263 execute_early_warn_uninitialized (void)
1264 {
1265   block_stmt_iterator bsi;
1266   basic_block bb;
1267
1268   FOR_EACH_BB (bb)
1269     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1270       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1271                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1272 }
1273
1274 static void
1275 execute_late_warn_uninitialized (void)
1276 {
1277   basic_block bb;
1278   tree phi;
1279
1280   /* Re-do the plain uninitialized variable check, as optimization may have
1281      straightened control flow.  Do this first so that we don't accidentally
1282      get a "may be" warning when we'd have seen an "is" warning later.  */
1283   execute_early_warn_uninitialized ();
1284
1285   FOR_EACH_BB (bb)
1286     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1287       warn_uninitialized_phi (phi);
1288 }
1289
1290 static bool
1291 gate_warn_uninitialized (void)
1292 {
1293   return warn_uninitialized != 0;
1294 }
1295
1296 struct tree_opt_pass pass_early_warn_uninitialized =
1297 {
1298   NULL,                                 /* name */
1299   gate_warn_uninitialized,              /* gate */
1300   execute_early_warn_uninitialized,     /* execute */
1301   NULL,                                 /* sub */
1302   NULL,                                 /* next */
1303   0,                                    /* static_pass_number */
1304   0,                                    /* tv_id */
1305   PROP_ssa,                             /* properties_required */
1306   0,                                    /* properties_provided */
1307   0,                                    /* properties_destroyed */
1308   0,                                    /* todo_flags_start */
1309   0,                                    /* todo_flags_finish */
1310   0                                     /* letter */
1311 };
1312
1313 struct tree_opt_pass pass_late_warn_uninitialized =
1314 {
1315   NULL,                                 /* name */
1316   gate_warn_uninitialized,              /* gate */
1317   execute_late_warn_uninitialized,      /* execute */
1318   NULL,                                 /* sub */
1319   NULL,                                 /* next */
1320   0,                                    /* static_pass_number */
1321   0,                                    /* tv_id */
1322   PROP_ssa,                             /* properties_required */
1323   0,                                    /* properties_provided */
1324   0,                                    /* properties_destroyed */
1325   0,                                    /* todo_flags_start */
1326   0,                                    /* todo_flags_finish */
1327   0                                     /* letter */
1328 };