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