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