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
 509   timevar_push (TV_TREE_SSA_VERIFY);
 510
 511   /* Keep track of SSA names present in the IL.  */
 512   for (i = 1; i < num_ssa_names; i++)
 513     TREE_VISITED (ssa_name (i)) = 0;
 514
 515   calculate_dominance_info (CDI_DOMINATORS);
 516
 517   /* Verify and register all the SSA_NAME definitions found in the
 518      function.  */
 519   FOR_EACH_BB (bb)
 520     {
 521       tree phi;
 522       block_stmt_iterator bsi;
 523
 524       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 525         if (verify_def (bb, definition_block, PHI_RESULT (phi), phi,
 526                         !is_gimple_reg (PHI_RESULT (phi))))
 527           goto err;
 528
 529       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 530         {
 531           tree stmt;
 532
 533           stmt = bsi_stmt (bsi);
 534           get_stmt_operands (stmt);
 535
 536           if (stmt_ann (stmt)->makes_aliased_stores
 537               && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
 538             {
 539               error ("Statement makes aliased stores, but has no V_MAY_DEFS");
 540               debug_generic_stmt (stmt);
 541               goto err;
 542             }
 543
 544           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_DEFS)
 545             {
 546               if (verify_def (bb, definition_block, op, stmt, true))
 547                 goto err;
 548             }
 549
 550           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_DEF)
 551             {
 552               if (verify_def (bb, definition_block, op, stmt, false))
 553                 goto err;
 554             }
 555         }
 556     }
 557
 558
 559   /* Now verify all the uses and make sure they agree with the definitions
 560      found in the previous pass.  */
 561   FOR_EACH_BB (bb)
 562     {
 563       edge e;
 564       tree phi;
 565       block_stmt_iterator bsi;
 566
 567       /* Make sure that all edges have a clear 'aux' field.  */
 568       for (e = bb->pred; e; e = e->pred_next)
 569         {
 570           if (e->aux)
 571             {
 572               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 573                       e->dest->index);
 574               goto err;
 575             }
 576         }
 577
 578       /* Verify the arguments for every PHI node in the block.  */
 579       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 580         if (verify_phi_args (phi, bb, definition_block))
 581           goto err;
 582
 583       /* Now verify all the uses and vuses in every statement of the block.  */
 584       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 585         {
 586           tree stmt = bsi_stmt (bsi);
 587
 588           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_VIRTUAL_USES)
 589             {
 590               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 591                               op, stmt, false, true))
 592                 goto err;
 593             }
 594
 595           FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
 596             {
 597               if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 598                               op, stmt, false, false))
 599                 goto err;
 600             }
 601         }
 602     }
 603
 604   /* Finally, verify alias information.  */
 605   verify_alias_info ();
 606
 607   free (definition_block);
 608   timevar_pop (TV_TREE_SSA_VERIFY);
 609   return;
 610
 611 err:
 612   internal_error ("verify_ssa failed.");
 613 }
 614
 615
 616 /* Initialize global DFA and SSA structures.  */
 617
 618 void
 619 init_tree_ssa (void)
 620 {
 621   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 622   call_clobbered_vars = BITMAP_XMALLOC ();
 623   addressable_vars = BITMAP_XMALLOC ();
 624   init_ssa_operands ();
 625   init_ssanames ();
 626   init_phinodes ();
 627   global_var = NULL_TREE;
 628 }
 629
 630
 631 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 632
 633 void
 634 delete_tree_ssa (void)
 635 {
 636   size_t i;
 637   basic_block bb;
 638   block_stmt_iterator bsi;
 639
 640   /* Remove annotations from every tree in the function.  */
 641   FOR_EACH_BB (bb)
 642     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 643       {
 644         tree stmt = bsi_stmt (bsi);
 645         release_defs (stmt);
 646         ggc_free (stmt->common.ann);
 647         stmt->common.ann = NULL;
 648       }
 649
 650   /* Remove annotations from every referenced variable.  */
 651   if (referenced_vars)
 652     {
 653       for (i = 0; i < num_referenced_vars; i++)
 654         {
 655           tree var = referenced_var (i);
 656           ggc_free (var->common.ann);
 657           var->common.ann = NULL;
 658         }
 659       referenced_vars = NULL;
 660     }
 661
 662   fini_ssanames ();
 663   fini_phinodes ();
 664   fini_ssa_operands ();
 665
 666   global_var = NULL_TREE;
 667   BITMAP_XFREE (call_clobbered_vars);
 668   call_clobbered_vars = NULL;
 669   BITMAP_XFREE (addressable_vars);
 670   addressable_vars = NULL;
 671 }
 672
 673
 674 /* Return true if EXPR is a useless type conversion, otherwise return
 675    false.  */
 676
 677 bool
 678 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 679 {
 680   /* If the inner and outer types are effectively the same, then
 681      strip the type conversion and enter the equivalence into
 682      the table.  */
 683   if (inner_type == outer_type
 684      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 685     return true;
 686
 687   /* If both types are pointers and the outer type is a (void *), then
 688      the conversion is not necessary.  The opposite is not true since
 689      that conversion would result in a loss of information if the
 690      equivalence was used.  Consider an indirect function call where
 691      we need to know the exact type of the function to correctly
 692      implement the ABI.  */
 693   else if (POINTER_TYPE_P (inner_type)
 694            && POINTER_TYPE_P (outer_type)
 695            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 696     return true;
 697
 698   /* Pointers and references are equivalent once we get to GENERIC,
 699      so strip conversions that just switch between them.  */
 700   else if (POINTER_TYPE_P (inner_type)
 701            && POINTER_TYPE_P (outer_type)
 702            && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
 703                                              TREE_TYPE (outer_type)))
 704     return true;
 705
 706   /* If both the inner and outer types are integral types, then the
 707      conversion is not necessary if they have the same mode and
 708      signedness and precision, and both or neither are boolean.  Some
 709      code assumes an invariant that boolean types stay boolean and do
 710      not become 1-bit bit-field types.  Note that types with precision
 711      not using all bits of the mode (such as bit-field types in C)
 712      mean that testing of precision is necessary.  */
 713   else if (INTEGRAL_TYPE_P (inner_type)
 714            && INTEGRAL_TYPE_P (outer_type)
 715            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 716            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 717            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 718     {
 719       bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
 720       bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
 721       if (first_boolean == second_boolean)
 722         return true;
 723     }
 724
 725   /* Recurse for complex types.  */
 726   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 727            && TREE_CODE (outer_type) == COMPLEX_TYPE
 728            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 729                                                   TREE_TYPE (inner_type)))
 730     return true;
 731
 732   return false;
 733 }
 734
 735 /* Return true if EXPR is a useless type conversion, otherwise return
 736    false.  */
 737
 738 bool
 739 tree_ssa_useless_type_conversion (tree expr)
 740 {
 741   /* If we have an assignment that merely uses a NOP_EXPR to change
 742      the top of the RHS to the type of the LHS and the type conversion
 743      is "safe", then strip away the type conversion so that we can
 744      enter LHS = RHS into the const_and_copies table.  */
 745   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
 746       || TREE_CODE (expr) == VIEW_CONVERT_EXPR
 747       || TREE_CODE (expr) == NON_LVALUE_EXPR)
 748     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 749                                                TREE_TYPE (TREE_OPERAND (expr,
 750                                                                         0)));
 751
 752
 753   return false;
 754 }
 755
 756
 757 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 758    described in walk_use_def_chains.
 759
 760    VISITED is a bitmap used to mark visited SSA_NAMEs to avoid
 761       infinite loops.
 762
 763    IS_DFS is true if the caller wants to perform a depth-first search
 764       when visiting PHI nodes.  A DFS will visit each PHI argument and
 765       call FN after each one.  Otherwise, all the arguments are
 766       visited first and then FN is called with each of the visited
 767       arguments in a separate pass.  */
 768
 769 static bool
 770 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 771                        bitmap visited, bool is_dfs)
 772 {
 773   tree def_stmt;
 774
 775   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 776     return false;
 777
 778   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 779
 780   def_stmt = SSA_NAME_DEF_STMT (var);
 781
 782   if (TREE_CODE (def_stmt) != PHI_NODE)
 783     {
 784       /* If we reached the end of the use-def chain, call FN.  */
 785       return fn (var, def_stmt, data);
 786     }
 787   else
 788     {
 789       int i;
 790
 791       /* When doing a breadth-first search, call FN before following the
 792          use-def links for each argument.  */
 793       if (!is_dfs)
 794         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 795           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 796             return true;
 797
 798       /* Follow use-def links out of each PHI argument.  */
 799       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 800         {
 801           tree arg = PHI_ARG_DEF (def_stmt, i);
 802           if (TREE_CODE (arg) == SSA_NAME
 803               && walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
 804             return true;
 805         }
 806
 807       /* When doing a depth-first search, call FN after following the
 808          use-def links for each argument.  */
 809       if (is_dfs)
 810         for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 811           if (fn (PHI_ARG_DEF (def_stmt, i), def_stmt, data))
 812             return true;
 813     }
 814
 815   return false;
 816 }
 817
 818
 819
 820 /* Walk use-def chains starting at the SSA variable VAR.  Call
 821    function FN at each reaching definition found.  FN takes three
 822    arguments: VAR, its defining statement (DEF_STMT) and a generic
 823    pointer to whatever state information that FN may want to maintain
 824    (DATA).  FN is able to stop the walk by returning true, otherwise
 825    in order to continue the walk, FN should return false.
 826
 827    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 828    different.  The first argument to FN is no longer the original
 829    variable VAR, but the PHI argument currently being examined.  If FN
 830    wants to get at VAR, it should call PHI_RESULT (PHI).
 831
 832    If IS_DFS is true, this function will:
 833
 834         1- walk the use-def chains for all the PHI arguments, and,
 835         2- call (*FN) (ARG, PHI, DATA) on all the PHI arguments.
 836
 837    If IS_DFS is false, the two steps above are done in reverse order
 838    (i.e., a breadth-first search).  */
 839
 840
 841 void
 842 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
 843                      bool is_dfs)
 844 {
 845   tree def_stmt;
 846
 847   gcc_assert (TREE_CODE (var) == SSA_NAME);
 848
 849   def_stmt = SSA_NAME_DEF_STMT (var);
 850
 851   /* We only need to recurse if the reaching definition comes from a PHI
 852      node.  */
 853   if (TREE_CODE (def_stmt) != PHI_NODE)
 854     (*fn) (var, def_stmt, data);
 855   else
 856     {
 857       bitmap visited = BITMAP_XMALLOC ();
 858       walk_use_def_chains_1 (var, fn, data, visited, is_dfs);
 859       BITMAP_XFREE (visited);
 860     }
 861 }
 862
 863
 864 /* Replaces VAR with REPL in memory reference expression *X in
 865    statement STMT.  */
 866
 867 static void
 868 propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
 869 {
 870   tree new_var, ass_stmt, addr_var;
 871   basic_block bb;
 872   block_stmt_iterator bsi;
 873
 874   /* There is nothing special to handle in the other cases.  */
 875   if (TREE_CODE (repl) != ADDR_EXPR)
 876     return;
 877   addr_var = TREE_OPERAND (repl, 0);
 878
 879   while (handled_component_p (*x)
 880          || TREE_CODE (*x) == REALPART_EXPR
 881          || TREE_CODE (*x) == IMAGPART_EXPR)
 882     x = &TREE_OPERAND (*x, 0);
 883
 884   if (TREE_CODE (*x) != INDIRECT_REF
 885       || TREE_OPERAND (*x, 0) != var)
 886     return;
 887
 888   if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
 889     {
 890       *x = addr_var;
 891       mark_new_vars_to_rename (stmt, vars_to_rename);
 892       return;
 893     }
 894
 895
 896   /* Frontends sometimes produce expressions like *&a instead of a[0].
 897      Create a temporary variable to handle this case.  */
 898   ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
 899   new_var = duplicate_ssa_name (var, ass_stmt);
 900   TREE_OPERAND (*x, 0) = new_var;
 901   TREE_OPERAND (ass_stmt, 0) = new_var;
 902
 903   bb = bb_for_stmt (stmt);
 904   tree_block_label (bb);
 905   bsi = bsi_after_labels (bb);
 906   bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
 907
 908   mark_new_vars_to_rename (stmt, vars_to_rename);
 909 }
 910
 911 /* Replaces immediate uses of VAR by REPL.  */
 912
 913 static void
 914 replace_immediate_uses (tree var, tree repl)
 915 {
 916   int i, j, n;
 917   dataflow_t df;
 918   tree stmt;
 919   bool mark_new_vars;
 920   ssa_op_iter iter;
 921   use_operand_p use_p;
 922
 923   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 924   n = num_immediate_uses (df);
 925
 926   for (i = 0; i < n; i++)
 927     {
 928       stmt = immediate_use (df, i);
 929
 930       if (TREE_CODE (stmt) == PHI_NODE)
 931         {
 932           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 933             if (PHI_ARG_DEF (stmt, j) == var)
 934               {
 935                 SET_PHI_ARG_DEF (stmt, j, repl);
 936                 if (TREE_CODE (repl) == SSA_NAME
 937                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 938                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 939               }
 940
 941           continue;
 942         }
 943
 944       get_stmt_operands (stmt);
 945       mark_new_vars = false;
 946       if (is_gimple_reg (SSA_NAME_VAR (var)))
 947         {
 948           if (TREE_CODE (stmt) == MODIFY_EXPR)
 949             {
 950               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
 951               propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
 952             }
 953
 954           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 955             if (USE_FROM_PTR (use_p) == var)
 956               {
 957                 propagate_value (use_p, repl);
 958                 mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
 959               }
 960         }
 961       else
 962         {
 963           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
 964             if (USE_FROM_PTR (use_p) == var)
 965               propagate_value (use_p, repl);
 966         }
 967
 968       /* If REPL is a pointer, it may have different memory tags associated
 969          with it.  For instance, VAR may have had a name tag while REPL
 970          only had a type tag.  In these cases, the virtual operands (if
 971          any) in the statement will refer to different symbols which need
 972          to be renamed.  */
 973       if (mark_new_vars)
 974         mark_new_vars_to_rename (stmt, vars_to_rename);
 975       else
 976         modify_stmt (stmt);
 977     }
 978 }
 979
 980 /* Gets the value VAR is equivalent to according to EQ_TO.  */
 981
 982 static tree
 983 get_eq_name (tree *eq_to, tree var)
 984 {
 985   unsigned ver;
 986   tree val = var;
 987
 988   while (TREE_CODE (val) == SSA_NAME)
 989     {
 990       ver = SSA_NAME_VERSION (val);
 991       if (!eq_to[ver])
 992         break;
 993
 994       val = eq_to[ver];
 995     }
 996
 997   while (TREE_CODE (var) == SSA_NAME)
 998     {
 999       ver = SSA_NAME_VERSION (var);
1000       if (!eq_to[ver])
1001         break;
1002
1003       var = eq_to[ver];
1004       eq_to[ver] = val;
1005     }
1006
1007   return val;
1008 }
1009
1010 /* Checks whether phi node PHI is redundant and if it is, records the ssa name
1011    its result is redundant to to EQ_TO array.  */
1012
1013 static void
1014 check_phi_redundancy (tree phi, tree *eq_to)
1015 {
1016   tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
1017   unsigned i, ver = SSA_NAME_VERSION (res), n;
1018   dataflow_t df;
1019
1020   /* It is unlikely that such large phi node would be redundant.  */
1021   if (PHI_NUM_ARGS (phi) > 16)
1022     return;
1023
1024   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
1025     {
1026       def = PHI_ARG_DEF (phi, i);
1027
1028       if (TREE_CODE (def) == SSA_NAME)
1029         {
1030           def = get_eq_name (eq_to, def);
1031           if (def == res)
1032             continue;
1033         }
1034
1035       if (val
1036           && !operand_equal_p (val, def, 0))
1037         return;
1038
1039       val = def;
1040     }
1041
1042   /* At least one of the arguments should not be equal to the result, or
1043      something strange is happening.  */
1044   gcc_assert (val);
1045
1046   if (get_eq_name (eq_to, res) == val)
1047     return;
1048
1049   if (!may_propagate_copy (res, val))
1050     return;
1051
1052   eq_to[ver] = val;
1053
1054   df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
1055   n = num_immediate_uses (df);
1056
1057   for (i = 0; i < n; i++)
1058     {
1059       stmt = immediate_use (df, i);
1060
1061       if (TREE_CODE (stmt) == PHI_NODE)
1062         check_phi_redundancy (stmt, eq_to);
1063     }
1064 }
1065
1066 /* Removes redundant phi nodes.
1067
1068    A redundant PHI node is a PHI node where all of its PHI arguments
1069    are the same value, excluding any PHI arguments which are the same
1070    as the PHI result.
1071
1072    A redundant PHI node is effectively a copy, so we forward copy propagate
1073    which removes all uses of the destination of the PHI node then
1074    finally we delete the redundant PHI node.
1075
1076    Note that if we can not copy propagate the PHI node, then the PHI
1077    will not be removed.  Thus we do not have to worry about dependencies
1078    between PHIs and the problems serializing PHIs into copies creates.
1079
1080    The most important effect of this pass is to remove degenerate PHI
1081    nodes created by removing unreachable code.  */
1082
1083 void
1084 kill_redundant_phi_nodes (void)
1085 {
1086   tree *eq_to;
1087   unsigned i, old_num_ssa_names;
1088   basic_block bb;
1089   tree phi, var, repl, stmt;
1090
1091   /* The EQ_TO[VER] holds the value by that the ssa name VER should be
1092      replaced.  If EQ_TO[VER] is ssa name and it is decided to replace it by
1093      other value, it may be necessary to follow the chain till the final value.
1094      We perform path shortening (replacing the entries of the EQ_TO array with
1095      heads of these chains) whenever we access the field to prevent quadratic
1096      complexity (probably would not occur in practice anyway, but let us play
1097      it safe).  */
1098   eq_to = xcalloc (num_ssa_names, sizeof (tree));
1099
1100   /* We have had cases where computing immediate uses takes a
1101      significant amount of compile time.  If we run into such
1102      problems here, we may want to only compute immediate uses for
1103      a subset of all the SSA_NAMEs instead of computing it for
1104      all of the SSA_NAMEs.  */
1105   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
1106   old_num_ssa_names = num_ssa_names;
1107
1108   FOR_EACH_BB (bb)
1109     {
1110       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1111         {
1112           var = PHI_RESULT (phi);
1113           check_phi_redundancy (phi, eq_to);
1114         }
1115     }
1116
1117   /* Now propagate the values.  */
1118   for (i = 0; i < old_num_ssa_names; i++)
1119     {
1120       if (!ssa_name (i))
1121         continue;
1122
1123       repl = get_eq_name (eq_to, ssa_name (i));
1124       if (repl != ssa_name (i))
1125         replace_immediate_uses (ssa_name (i), repl);
1126     }
1127
1128   /* And remove the dead phis.  */
1129   for (i = 0; i < old_num_ssa_names; i++)
1130     {
1131       if (!ssa_name (i))
1132         continue;
1133
1134       repl = get_eq_name (eq_to, ssa_name (i));
1135       if (repl != ssa_name (i))
1136         {
1137           stmt = SSA_NAME_DEF_STMT (ssa_name (i));
1138           remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
1139         }
1140     }
1141
1142   free_df ();
1143   free (eq_to);
1144 }
1145
1146 struct tree_opt_pass pass_redundant_phi =
1147 {
1148   "redphi",                             /* name */
1149   NULL,                                 /* gate */
1150   kill_redundant_phi_nodes,             /* execute */
1151   NULL,                                 /* sub */
1152   NULL,                                 /* next */
1153   0,                                    /* static_pass_number */
1154   0,                                    /* tv_id */
1155   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1156   0,                                    /* properties_provided */
1157   0,                                    /* properties_destroyed */
1158   0,                                    /* todo_flags_start */
1159   TODO_dump_func | TODO_rename_vars
1160     | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
1161   0                                     /* letter */
1162 };
1163 \f
1164 /* Emit warnings for uninitialized variables.  This is done in two passes.
1165
1166    The first pass notices real uses of SSA names with default definitions.
1167    Such uses are unconditionally uninitialized, and we can be certain that
1168    such a use is a mistake.  This pass is run before most optimizations,
1169    so that we catch as many as we can.
1170
1171    The second pass follows PHI nodes to find uses that are potentially
1172    uninitialized.  In this case we can't necessarily prove that the use
1173    is really uninitialized.  This pass is run after most optimizations,
1174    so that we thread as many jumps and possible, and delete as much dead
1175    code as possible, in order to reduce false positives.  We also look
1176    again for plain uninitialized variables, since optimization may have
1177    changed conditionally uninitialized to unconditionally uninitialized.  */
1178
1179 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
1180    warning text is in MSGID and LOCUS may contain a location or be null.  */
1181
1182 static void
1183 warn_uninit (tree t, const char *msgid, location_t *locus)
1184 {
1185   tree var = SSA_NAME_VAR (t);
1186   tree def = SSA_NAME_DEF_STMT (t);
1187
1188   /* Default uses (indicated by an empty definition statement),
1189      are uninitialized.  */
1190   if (!IS_EMPTY_STMT (def))
1191     return;
1192
1193   /* Except for PARMs of course, which are always initialized.  */
1194   if (TREE_CODE (var) == PARM_DECL)
1195     return;
1196
1197   /* Hard register variables get their initial value from the ether.  */
1198   if (DECL_HARD_REGISTER (var))
1199     return;
1200
1201   /* TREE_NO_WARNING either means we already warned, or the front end
1202      wishes to suppress the warning.  */
1203   if (TREE_NO_WARNING (var))
1204     return;
1205
1206   if (!locus)
1207     locus = &DECL_SOURCE_LOCATION (var);
1208   warning (msgid, locus, var);
1209   TREE_NO_WARNING (var) = 1;
1210 }
1211
1212 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
1213    and warn about them.  */
1214
1215 static tree
1216 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
1217 {
1218   location_t *locus = data;
1219   tree t = *tp;
1220
1221   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1222   if (TREE_CODE (t) == SSA_NAME)
1223     {
1224       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1225       *walk_subtrees = 0;
1226     }
1227   else if (DECL_P (t) || TYPE_P (t))
1228     *walk_subtrees = 0;
1229
1230   return NULL_TREE;
1231 }
1232
1233 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1234    and warn about them.  */
1235
1236 static void
1237 warn_uninitialized_phi (tree phi)
1238 {
1239   int i, n = PHI_NUM_ARGS (phi);
1240
1241   /* Don't look at memory tags.  */
1242   if (!is_gimple_reg (PHI_RESULT (phi)))
1243     return;
1244
1245   for (i = 0; i < n; ++i)
1246     {
1247       tree op = PHI_ARG_DEF (phi, i);
1248       if (TREE_CODE (op) == SSA_NAME)
1249         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1250                      NULL);
1251     }
1252 }
1253
1254 static void
1255 execute_early_warn_uninitialized (void)
1256 {
1257   block_stmt_iterator bsi;
1258   basic_block bb;
1259
1260   FOR_EACH_BB (bb)
1261     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1262       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1263                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1264 }
1265
1266 static void
1267 execute_late_warn_uninitialized (void)
1268 {
1269   basic_block bb;
1270   tree phi;
1271
1272   /* Re-do the plain uninitialized variable check, as optimization may have
1273      straightened control flow.  Do this first so that we don't accidentally
1274      get a "may be" warning when we'd have seen an "is" warning later.  */
1275   execute_early_warn_uninitialized ();
1276
1277   FOR_EACH_BB (bb)
1278     for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1279       warn_uninitialized_phi (phi);
1280 }
1281
1282 static bool
1283 gate_warn_uninitialized (void)
1284 {
1285   return warn_uninitialized != 0;
1286 }
1287
1288 struct tree_opt_pass pass_early_warn_uninitialized =
1289 {
1290   NULL,                                 /* name */
1291   gate_warn_uninitialized,              /* gate */
1292   execute_early_warn_uninitialized,     /* execute */
1293   NULL,                                 /* sub */
1294   NULL,                                 /* next */
1295   0,                                    /* static_pass_number */
1296   0,                                    /* tv_id */
1297   PROP_ssa,                             /* properties_required */
1298   0,                                    /* properties_provided */
1299   0,                                    /* properties_destroyed */
1300   0,                                    /* todo_flags_start */
1301   0,                                    /* todo_flags_finish */
1302   0                                     /* letter */
1303 };
1304
1305 struct tree_opt_pass pass_late_warn_uninitialized =
1306 {
1307   NULL,                                 /* name */
1308   gate_warn_uninitialized,              /* gate */
1309   execute_late_warn_uninitialized,      /* execute */
1310   NULL,                                 /* sub */
1311   NULL,                                 /* next */
1312   0,                                    /* static_pass_number */
1313   0,                                    /* tv_id */
1314   PROP_ssa,                             /* properties_required */
1315   0,                                    /* properties_provided */
1316   0,                                    /* properties_destroyed */
1317   0,                                    /* todo_flags_start */
1318   0,                                    /* todo_flags_finish */
1319   0                                     /* letter */
1320 };